/* Support for simple predicate analysis.

   Copyright (C) 2001-2022 Free Software Foundation, Inc.
   Contributed by Xinliang David Li <davidxl@google.com>
   Generalized by Martin Sebor <msebor@redhat.com>

   This file is part of GCC.

   GCC is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3, or (at your option)
   any later version.

   GCC is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with GCC; see the file COPYING3.  If not see
   <http://www.gnu.org/licenses/>.  */

#define INCLUDE_STRING
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "gimple-pretty-print.h"
#include "diagnostic-core.h"
#include "fold-const.h"
#include "gimple-iterator.h"
#include "tree-ssa.h"
#include "tree-cfg.h"
#include "cfghooks.h"
#include "attribs.h"
#include "builtins.h"
#include "calls.h"
#include "value-query.h"

#include "gimple-predicate-analysis.h"

#define DEBUG_PREDICATE_ANALYZER 1

/* Return true if BB1 is postdominating BB2 and BB1 is not a loop exit
   bb.  The loop exit bb check is simple and does not cover all cases.  */

static bool
is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
{
  if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
    return false;

  if (single_pred_p (bb1) && !single_succ_p (bb2))
    return false;

  return true;
}

/* Find BB's closest postdominator that is its control equivalent (i.e.,
   that's controlled by the same predicate).  */

static inline basic_block
find_control_equiv_block (basic_block bb)
{
  basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb);

  /* Skip the postdominating bb that is also a loop exit.  */
  if (!is_non_loop_exit_postdominating (pdom, bb))
    return NULL;

  /* If the postdominator is dominated by BB, return it.  */
  if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
    return pdom;

  return NULL;
}

/* Return true if X1 is the negation of X2.  */

static inline bool
pred_neg_p (const pred_info &x1, const pred_info &x2)
{
  if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
      || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
    return false;

  tree_code c1 = x1.cond_code, c2;
  if (x1.invert == x2.invert)
    c2 = invert_tree_comparison (x2.cond_code, false);
  else
    c2 = x2.cond_code;

  return c1 == c2;
}

/* Return whether the condition (VAL CMPC BOUNDARY) is true.  */

static bool
is_value_included_in (tree val, tree boundary, tree_code cmpc)
{
  /* Only handle integer constant here.  */
  if (TREE_CODE (val) != INTEGER_CST || TREE_CODE (boundary) != INTEGER_CST)
    return true;

  bool inverted = false;
  if (cmpc == GE_EXPR || cmpc == GT_EXPR || cmpc == NE_EXPR)
    {
      cmpc = invert_tree_comparison (cmpc, false);
      inverted = true;
    }

  bool result;
  if (cmpc == EQ_EXPR)
    result = tree_int_cst_equal (val, boundary);
  else if (cmpc == LT_EXPR)
    result = tree_int_cst_lt (val, boundary);
  else
    {
      gcc_assert (cmpc == LE_EXPR);
      result = tree_int_cst_le (val, boundary);
    }

  if (inverted)
    result ^= 1;

  return result;
}

/* Format the vector of edges EV as a string.  */

static std::string
format_edge_vec (const vec<edge> &ev)
{
  std::string str;

  unsigned n = ev.length ();
  for (unsigned i = 0; i < n; ++i)
    {
      char es[32];
      const_edge e = ev[i];
      sprintf (es, "%u", e->src->index);
      str += es;
      if (i + 1 < n)
	str += " -> ";
    }
  return str;
}

/* Format the first N elements of the array of vector of edges EVA as
   a string.  */

static std::string
format_edge_vecs (const vec<edge> eva[], unsigned n)
{
  std::string str;

  for (unsigned i = 0; i != n; ++i)
    {
      str += '{';
      str += format_edge_vec (eva[i]);
      str += '}';
      if (i + 1 < n)
	str += ", ";
    }
  return str;
}

/* Dump a single pred_info to DUMP_FILE.  */

static void
dump_pred_info (const pred_info &pred)
{
  if (pred.invert)
    fprintf (dump_file, "NOT (");
  print_generic_expr (dump_file, pred.pred_lhs);
  fprintf (dump_file, " %s ", op_symbol_code (pred.cond_code));
  print_generic_expr (dump_file, pred.pred_rhs);
  if (pred.invert)
    fputc (')', dump_file);
}

/* Dump a pred_chain to DUMP_FILE.  */

static void
dump_pred_chain (const pred_chain &chain)
{
  unsigned np = chain.length ();
  if (np > 1)
    fprintf (dump_file, "AND (");

  for (unsigned j = 0; j < np; j++)
    {
      dump_pred_info (chain[j]);
      if (j < np - 1)
	fprintf (dump_file, ", ");
      else if (j > 0)
	fputc (')', dump_file);
    }
}

/* Dump the predicate chain PREDS for STMT, prefixed by MSG.  */

static void
dump_predicates (gimple *stmt, const pred_chain_union &preds, const char *msg)
{
  fprintf (dump_file, "%s", msg);
  if (stmt)
    {
      print_gimple_stmt (dump_file, stmt, 0);
      fprintf (dump_file, "is guarded by:\n");
    }

  unsigned np = preds.length ();
  if (np > 1)
    fprintf (dump_file, "OR (");
  for (unsigned i = 0; i < np; i++)
    {
      dump_pred_chain (preds[i]);
      if (i < np - 1)
	fprintf (dump_file, ", ");
      else if (i > 0)
	fputc (')', dump_file);
    }
  fputc ('\n', dump_file);
}

/* Dump the first NCHAINS elements of the DEP_CHAINS array into DUMP_FILE.  */

static void
dump_dep_chains (const auto_vec<edge> dep_chains[], unsigned nchains)
{
  if (!dump_file)
    return;

  for (unsigned i = 0; i != nchains; ++i)
    {
      const auto_vec<edge> &v = dep_chains[i];
      unsigned n = v.length ();
      for (unsigned j = 0; j != n; ++j)
	{
	  fprintf (dump_file, "%u", v[j]->src->index);
	  if (j + 1 < n)
	    fprintf (dump_file, " -> ");
	}
      fputc ('\n', dump_file);
    }
}

/* Return the 'normalized' conditional code with operand swapping
   and condition inversion controlled by SWAP_COND and INVERT.  */

static tree_code
get_cmp_code (tree_code orig_cmp_code, bool swap_cond, bool invert)
{
  tree_code tc = orig_cmp_code;

  if (swap_cond)
    tc = swap_tree_comparison (orig_cmp_code);
  if (invert)
    tc = invert_tree_comparison (tc, false);

  switch (tc)
    {
    case LT_EXPR:
    case LE_EXPR:
    case GT_EXPR:
    case GE_EXPR:
    case EQ_EXPR:
    case NE_EXPR:
      break;
    default:
      return ERROR_MARK;
    }
  return tc;
}

/* Return true if PRED is common among all predicate chains in PREDS
   (and therefore can be factored out).  */

static bool
find_matching_predicate_in_rest_chains (const pred_info &pred,
					const pred_chain_union &preds)
{
  /* Trival case.  */
  if (preds.length () == 1)
    return true;

  for (unsigned i = 1; i < preds.length (); i++)
    {
      bool found = false;
      const pred_chain &chain = preds[i];
      unsigned n = chain.length ();
      for (unsigned j = 0; j < n; j++)
	{
	  const pred_info &pred2 = chain[j];
	  /* Can relax the condition comparison to not use address
	     comparison.  However, the most common case is that
	     multiple control dependent paths share a common path
	     prefix, so address comparison should be ok.  */
	  if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0)
	      && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0)
	      && pred2.invert == pred.invert)
	    {
	      found = true;
	      break;
	    }
	}
      if (!found)
	return false;
    }
  return true;
}

/* Find a predicate to examine against paths of interest.  If there
   is no predicate of the "FLAG_VAR CMP CONST" form, try to find one
   of that's the form "FLAG_VAR CMP FLAG_VAR" with value range info.
   PHI is the phi node whose incoming (interesting) paths need to be
   examined.  On success, return the comparison code, set defintion
   gimple of FLAG_DEF and BOUNDARY_CST.  Otherwise return ERROR_MARK.  */

static tree_code
find_var_cmp_const (pred_chain_union preds, gphi *phi, gimple **flag_def,
		    tree *boundary_cst)
{
  tree_code vrinfo_code = ERROR_MARK;
  gimple *vrinfo_def = NULL;
  tree vrinfo_cst = NULL;

  gcc_assert (preds.length () > 0);
  pred_chain chain = preds[0];
  for (unsigned i = 0; i < chain.length (); i++)
    {
      bool use_vrinfo_p = false;
      const pred_info &pred = chain[i];
      tree cond_lhs = pred.pred_lhs;
      tree cond_rhs = pred.pred_rhs;
      if (cond_lhs == NULL_TREE || cond_rhs == NULL_TREE)
	continue;

      tree_code code = get_cmp_code (pred.cond_code, false, pred.invert);
      if (code == ERROR_MARK)
	continue;

      /* Convert to the canonical form SSA_NAME CMP CONSTANT.  */
      if (TREE_CODE (cond_lhs) == SSA_NAME
	  && is_gimple_constant (cond_rhs))
	;
      else if (TREE_CODE (cond_rhs) == SSA_NAME
	       && is_gimple_constant (cond_lhs))
	{
	  std::swap (cond_lhs, cond_rhs);
	  if ((code = get_cmp_code (code, true, false)) == ERROR_MARK)
	    continue;
	}
      /* Check if we can take advantage of FLAG_VAR COMP FLAG_VAR predicate
	 with value range info.  Note only first of such case is handled.  */
      else if (vrinfo_code == ERROR_MARK
	       && TREE_CODE (cond_lhs) == SSA_NAME
	       && TREE_CODE (cond_rhs) == SSA_NAME)
	{
	  gimple* lhs_def = SSA_NAME_DEF_STMT (cond_lhs);
	  if (!lhs_def || gimple_code (lhs_def) != GIMPLE_PHI
	      || gimple_bb (lhs_def) != gimple_bb (phi))
	    {
	      std::swap (cond_lhs, cond_rhs);
	      if ((code = get_cmp_code (code, true, false)) == ERROR_MARK)
		continue;
	    }

	  /* Check value range info of rhs, do following transforms:
	       flag_var < [min, max]  ->  flag_var < max
	       flag_var > [min, max]  ->  flag_var > min

	     We can also transform LE_EXPR/GE_EXPR to LT_EXPR/GT_EXPR:
	       flag_var <= [min, max] ->  flag_var < [min, max+1]
	       flag_var >= [min, max] ->  flag_var > [min-1, max]
	     if no overflow/wrap.  */
	  tree type = TREE_TYPE (cond_lhs);
	  value_range r;
	  if (!INTEGRAL_TYPE_P (type)
	      || !get_range_query (cfun)->range_of_expr (r, cond_rhs)
	      || r.kind () != VR_RANGE)
	    continue;

	  wide_int min = r.lower_bound ();
	  wide_int max = r.upper_bound ();
	  if (code == LE_EXPR
	      && max != wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
	    {
	      code = LT_EXPR;
	      max = max + 1;
	    }
	  if (code == GE_EXPR
	      && min != wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
	    {
	      code = GT_EXPR;
	      min = min - 1;
	    }
	  if (code == LT_EXPR)
	    cond_rhs = wide_int_to_tree (type, max);
	  else if (code == GT_EXPR)
	    cond_rhs = wide_int_to_tree (type, min);
	  else
	    continue;

	  use_vrinfo_p = true;
	}
      else
	continue;

      if ((*flag_def = SSA_NAME_DEF_STMT (cond_lhs)) == NULL)
	continue;

      if (gimple_code (*flag_def) != GIMPLE_PHI
	  || gimple_bb (*flag_def) != gimple_bb (phi)
	  || !find_matching_predicate_in_rest_chains (pred, preds))
	continue;

      /* Return if any "flag_var comp const" predicate is found.  */
      if (!use_vrinfo_p)
	{
	  *boundary_cst = cond_rhs;
	  return code;
	}
      /* Record if any "flag_var comp flag_var[vinfo]" predicate is found.  */
      else if (vrinfo_code == ERROR_MARK)
	{
	  vrinfo_code = code;
	  vrinfo_def = *flag_def;
	  vrinfo_cst = cond_rhs;
	}
    }
  /* Return the "flag_var cmp flag_var[vinfo]" predicate we found.  */
  if (vrinfo_code != ERROR_MARK)
    {
      *flag_def = vrinfo_def;
      *boundary_cst = vrinfo_cst;
    }
  return vrinfo_code;
}

/* Return true if all interesting opnds are pruned, false otherwise.
   PHI is the phi node with interesting operands, OPNDS is the bitmap
   of the interesting operand positions, FLAG_DEF is the statement
   defining the flag guarding the use of the PHI output, BOUNDARY_CST
   is the const value used in the predicate associated with the flag,
   CMP_CODE is the comparison code used in the predicate, VISITED_PHIS
   is the pointer set of phis visited, and VISITED_FLAG_PHIS is
   the pointer to the pointer set of flag definitions that are also
   phis.

   Example scenario:

   BB1:
     flag_1 = phi <0, 1>			// (1)
     var_1  = phi <undef, some_val>


   BB2:
     flag_2 = phi <0,   flag_1, flag_1>		// (2)
     var_2  = phi <undef, var_1, var_1>
     if (flag_2 == 1)
       goto BB3;

   BB3:
     use of var_2				// (3)

   Because some flag arg in (1) is not constant, if we do not look into
   the flag phis recursively, it is conservatively treated as unknown and
   var_1 is thought to flow into use at (3).  Since var_1 is potentially
   uninitialized a false warning will be emitted.
   Checking recursively into (1), the compiler can find out that only
   some_val (which is defined) can flow into (3) which is OK.  */

static bool
prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def,
		 tree boundary_cst, tree_code cmp_code,
		 predicate::func_t &eval,
		 hash_set<gphi *> *visited_phis,
		 bitmap *visited_flag_phis)
{
  /* The Boolean predicate guarding the PHI definition.  Initialized
     lazily from PHI in the first call to is_use_guarded() and cached
     for subsequent iterations.  */
  predicate def_preds (eval);

  unsigned n = MIN (eval.max_phi_args, gimple_phi_num_args (flag_def));
  for (unsigned i = 0; i < n; i++)
    {
      if (!MASK_TEST_BIT (opnds, i))
	continue;

      tree flag_arg = gimple_phi_arg_def (flag_def, i);
      if (!is_gimple_constant (flag_arg))
	{
	  if (TREE_CODE (flag_arg) != SSA_NAME)
	    return false;

	  gphi *flag_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (flag_arg));
	  if (!flag_arg_def)
	    return false;

	  tree phi_arg = gimple_phi_arg_def (phi, i);
	  if (TREE_CODE (phi_arg) != SSA_NAME)
	    return false;

	  gphi *phi_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_arg));
	  if (!phi_arg_def)
	    return false;

	  if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
	    return false;

	  if (!*visited_flag_phis)
	    *visited_flag_phis = BITMAP_ALLOC (NULL);

	  tree phi_result = gimple_phi_result (flag_arg_def);
	  if (bitmap_bit_p (*visited_flag_phis, SSA_NAME_VERSION (phi_result)))
	    return false;

	  bitmap_set_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));

	  /* Now recursively try to prune the interesting phi args.  */
	  unsigned opnds_arg_phi = eval.phi_arg_set (phi_arg_def);
	  if (!prune_phi_opnds (phi_arg_def, opnds_arg_phi, flag_arg_def,
				boundary_cst, cmp_code, eval, visited_phis,
				visited_flag_phis))
	    return false;

	  bitmap_clear_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
	  continue;
	}

      /* Now check if the constant is in the guarded range.  */
      if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
	{
	  /* Now that we know that this undefined edge is not pruned.
	     If the operand is defined by another phi, we can further
	     prune the incoming edges of that phi by checking
	     the predicates of this operands.  */

	  tree opnd = gimple_phi_arg_def (phi, i);
	  gimple *opnd_def = SSA_NAME_DEF_STMT (opnd);
	  if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def))
	    {
	      unsigned opnds2 = eval.phi_arg_set (opnd_def_phi);
	      if (!MASK_EMPTY (opnds2))
		{
		  edge opnd_edge = gimple_phi_arg_edge (phi, i);
		  if (def_preds.is_use_guarded (phi, opnd_edge->src,
						opnd_def_phi, opnds2,
						visited_phis))
		    return false;
		}
	    }
	  else
	    return false;
	}
    }

  return true;
}

/* Recursively compute the set PHI's incoming edges with "uninteresting"
   operands of a phi chain, i.e., those for which EVAL returns false.
   CD_ROOT is the control dependence root from which edges are collected
   up the CFG nodes that it's dominated by.  *EDGES holds the result, and
   VISITED is used for detecting cycles.  */

static void
collect_phi_def_edges (gphi *phi, basic_block cd_root, auto_vec<edge> *edges,
		       predicate::func_t &eval, hash_set<gimple *> *visited)
{
  if (visited->elements () == 0
      && DEBUG_PREDICATE_ANALYZER
      && dump_file)
    {
      fprintf (dump_file, "%s for cd_root %u and ",
	       __func__, cd_root->index);
      print_gimple_stmt (dump_file, phi, 0);

    }

  if (visited->add (phi))
    return;

  unsigned n = gimple_phi_num_args (phi);
  for (unsigned i = 0; i < n; i++)
    {
      edge opnd_edge = gimple_phi_arg_edge (phi, i);
      tree opnd = gimple_phi_arg_def (phi, i);

      if (TREE_CODE (opnd) == SSA_NAME)
	{
	  gimple *def = SSA_NAME_DEF_STMT (opnd);

	  if (gimple_code (def) == GIMPLE_PHI
	      && dominated_by_p (CDI_DOMINATORS, gimple_bb (def), cd_root))
	    collect_phi_def_edges (as_a<gphi *> (def), cd_root, edges, eval,
				   visited);
	  else if (!eval (opnd))
	    {
	      if (dump_file && (dump_flags & TDF_DETAILS))
		{
		  fprintf (dump_file,
			   "\tFound def edge %i -> %i for cd_root %i "
			   "and operand %u of: ",
			   opnd_edge->src->index, opnd_edge->dest->index,
			   cd_root->index, i);
		  print_gimple_stmt (dump_file, phi, 0);
		}
	      edges->safe_push (opnd_edge);
	    }
	}
      else
	{
	  if (dump_file && (dump_flags & TDF_DETAILS))
	    {
	      fprintf (dump_file,
		       "\tFound def edge %i -> %i for cd_root %i "
		       "and operand %u of: ",
		       opnd_edge->src->index, opnd_edge->dest->index,
		       cd_root->index, i);
	      print_gimple_stmt (dump_file, phi, 0);
	    }

	  if (!eval (opnd))
	    edges->safe_push (opnd_edge);
	}
    }
}

/* Return an expression corresponding to the predicate PRED.  */

static tree
build_pred_expr (const pred_info &pred)
{
  tree_code cond_code = pred.cond_code;
  tree lhs = pred.pred_lhs;
  tree rhs = pred.pred_rhs;

  if (pred.invert)
    cond_code = invert_tree_comparison (cond_code, false);

  return build2 (cond_code, TREE_TYPE (lhs), lhs, rhs);
}

/* Return an expression corresponding to PREDS.  */

static tree
build_pred_expr (const pred_chain_union &preds, bool invert = false)
{
  tree_code code = invert ? TRUTH_AND_EXPR : TRUTH_OR_EXPR;
  tree_code subcode = invert ? TRUTH_OR_EXPR : TRUTH_AND_EXPR;

  tree expr = NULL_TREE;
  for (unsigned i = 0; i != preds.length (); ++i)
    {
      tree subexpr = NULL_TREE;
      for (unsigned j = 0; j != preds[i].length (); ++j)
       {
         const pred_info &pi = preds[i][j];
         tree cond = build_pred_expr (pi);
	 if (invert)
	   cond = invert_truthvalue (cond);
         subexpr = subexpr ? build2 (subcode, boolean_type_node,
                                     subexpr, cond) : cond;
       }
      if (expr)
       expr = build2 (code, boolean_type_node, expr, subexpr);
      else
       expr = subexpr;
    }

  return expr;
}

/* Return a bitset of all PHI arguments or zero if there are too many.  */

unsigned
predicate::func_t::phi_arg_set (gphi *phi)
{
  unsigned n = gimple_phi_num_args (phi);

  if (max_phi_args < n)
    return 0;

  /* Set the least significant N bits.  */
  return (1U << n) - 1;
}

/* Determine if the predicate set of the use does not overlap with that
   of the interesting paths.  The most common senario of guarded use is
   in Example 1:
     Example 1:
	   if (some_cond)
	   {
	      x = ...;   // set x to valid
	      flag = true;
	   }

	    ... some code ...

	   if (flag)
	      use (x);   // use when x is valid

     The real world examples are usually more complicated, but similar
     and usually result from inlining:

	 bool init_func (int * x)
	 {
	     if (some_cond)
		return false;
	     *x  =  ...;   // set *x to valid
	     return true;
	 }

	 void foo (..)
	 {
	     int x;

	     if (!init_func (&x))
		return;

	     .. some_code ...
	     use (x);      // use when x is valid
	 }

     Another possible use scenario is in the following trivial example:

     Example 2:
	  if (n > 0)
	     x = 1;
	  ...
	  if (n > 0)
	    {
	      if (m < 2)
		 ... = x;
	    }

     Predicate analysis needs to compute the composite predicate:

       1) 'x' use predicate: (n > 0) .AND. (m < 2)
       2) 'x' default value  (non-def) predicate: .NOT. (n > 0)
       (the predicate chain for phi operand defs can be computed
       starting from a bb that is control equivalent to the phi's
       bb and is dominating the operand def.)

       and check overlapping:
	  (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
	<==> false

     This implementation provides a framework that can handle different
     scenarios.  (Note that many simple cases are handled properly without
     the predicate analysis if jump threading eliminates the merge point
     thus makes path-sensitive analysis unnecessary.)

     PHI is the phi node whose incoming (undefined) paths need to be
     pruned, and OPNDS is the bitmap holding interesting operand
     positions.  VISITED is the pointer set of phi stmts being
     checked.  */

bool
predicate::overlap (gphi *phi, unsigned opnds, hash_set<gphi *> *visited)
{
  gimple *flag_def = NULL;
  tree boundary_cst = NULL_TREE;
  bitmap visited_flag_phis = NULL;

  /* Find within the common prefix of multiple predicate chains
     a predicate that is a comparison of a flag variable against
     a constant.  */
  tree_code cmp_code = find_var_cmp_const (m_preds, phi, &flag_def,
					   &boundary_cst);
  if (cmp_code == ERROR_MARK)
    return true;

  /* Now check all the uninit incoming edges have a constant flag
     value that is in conflict with the use guard/predicate.  */
  gphi *phi_def = as_a<gphi *> (flag_def);
  bool all_pruned = prune_phi_opnds (phi, opnds, phi_def, boundary_cst,
				     cmp_code, m_eval, visited,
				     &visited_flag_phis);

  if (visited_flag_phis)
    BITMAP_FREE (visited_flag_phis);

  return !all_pruned;
}

/* Return true if two predicates PRED1 and X2 are equivalent.  Assume
   the expressions have already properly re-associated.  */

static inline bool
pred_equal_p (const pred_info &pred1, const pred_info &pred2)
{
  if (!operand_equal_p (pred1.pred_lhs, pred2.pred_lhs, 0)
      || !operand_equal_p (pred1.pred_rhs, pred2.pred_rhs, 0))
    return false;

  tree_code c1 = pred1.cond_code, c2;
  if (pred1.invert != pred2.invert
      && TREE_CODE_CLASS (pred2.cond_code) == tcc_comparison)
    c2 = invert_tree_comparison (pred2.cond_code, false);
  else
    c2 = pred2.cond_code;

  return c1 == c2;
}

/* Return true if PRED tests inequality (i.e., X != Y).  */

static inline bool
is_neq_relop_p (const pred_info &pred)
{

  return ((pred.cond_code == NE_EXPR && !pred.invert)
	  || (pred.cond_code == EQ_EXPR && pred.invert));
}

/* Returns true if PRED is of the form X != 0.  */

static inline bool
is_neq_zero_form_p (const pred_info &pred)
{
  if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
      || TREE_CODE (pred.pred_lhs) != SSA_NAME)
    return false;
  return true;
}

/* Return true if PRED is equivalent to X != 0.  */

static inline bool
pred_expr_equal_p (const pred_info &pred, tree expr)
{
  if (!is_neq_zero_form_p (pred))
    return false;

  return operand_equal_p (pred.pred_lhs, expr, 0);
}

/* Return true if VAL satisfies (x CMPC BOUNDARY) predicate.  CMPC can
   be either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and
   the like), or BIT_AND_EXPR.  EXACT_P is only meaningful for the latter.
   Modify the question from VAL & BOUNDARY != 0 to VAL & BOUNDARY == VAL.
   For other values of CMPC, EXACT_P is ignored.  */

static bool
value_sat_pred_p (tree val, tree boundary, tree_code cmpc,
		  bool exact_p = false)
{
  if (cmpc != BIT_AND_EXPR)
    return is_value_included_in (val, boundary, cmpc);

  wide_int andw = wi::to_wide (val) & wi::to_wide (boundary);
  if (exact_p)
    return andw == wi::to_wide (val);

  return andw.to_uhwi ();
}

/* Return true if the domain of single predicate expression PRED1
   is a subset of that of PRED2, and false if it cannot be proved.  */

static bool
subset_of (const pred_info &pred1, const pred_info &pred2)
{
  if (pred_equal_p (pred1, pred2))
    return true;

  if ((TREE_CODE (pred1.pred_rhs) != INTEGER_CST)
      || (TREE_CODE (pred2.pred_rhs) != INTEGER_CST))
    return false;

  if (!operand_equal_p (pred1.pred_lhs, pred2.pred_lhs, 0))
    return false;

  tree_code code1 = pred1.cond_code;
  if (pred1.invert)
    code1 = invert_tree_comparison (code1, false);
  tree_code code2 = pred2.cond_code;
  if (pred2.invert)
    code2 = invert_tree_comparison (code2, false);

  if (code2 == NE_EXPR && code1 == NE_EXPR)
    return false;

  if (code2 == NE_EXPR)
    return !value_sat_pred_p (pred2.pred_rhs, pred1.pred_rhs, code1);

  if (code1 == EQ_EXPR)
    return value_sat_pred_p (pred1.pred_rhs, pred2.pred_rhs, code2);

  if (code1 == code2)
    return value_sat_pred_p (pred1.pred_rhs, pred2.pred_rhs, code2,
			     code1 == BIT_AND_EXPR);

  return false;
}

/* Return true if the domain of CHAIN1 is a subset of that of CHAIN2.
   Return false if it cannot be proven so.  */

static bool
subset_of (const pred_chain &chain1, const pred_chain &chain2)
{
  unsigned np1 = chain1.length ();
  unsigned np2 = chain2.length ();
  for (unsigned i2 = 0; i2 < np2; i2++)
    {
      bool found = false;
      const pred_info &info2 = chain2[i2];
      for (unsigned i1 = 0; i1 < np1; i1++)
	{
	  const pred_info &info1 = chain1[i1];
	  if (subset_of (info1, info2))
	    {
	      found = true;
	      break;
	    }
	}
      if (!found)
	return false;
    }
  return true;
}

/* Return true if the domain defined by the predicate chain PREDS is
   a subset of the domain of *THIS.  Return false if PREDS's domain
   is not a subset of any of the sub-domains of *THIS (corresponding
   to each individual chains in it), even though it may be still be
   a subset of whole domain of *THIS which is the union (ORed) of all
   its subdomains.  In other words, the result is conservative.  */

bool
predicate::includes (const pred_chain &chain) const
{
  for (unsigned i = 0; i < m_preds.length (); i++)
    if (subset_of (chain, m_preds[i]))
      return true;

  return false;
}

/* Return true if the domain defined by *THIS is a superset of PREDS's
   domain.
   Avoid building generic trees (and rely on the folding capability
   of the compiler), and instead perform brute force comparison of
   individual predicate chains (this won't be a computationally costly
   since the chains are pretty short).  Returning false does not
   necessarily mean *THIS is not a superset of *PREDS, only that
   it need not be since the analysis cannot prove it.  */

bool
predicate::superset_of (const predicate &preds) const
{
  for (unsigned i = 0; i < preds.m_preds.length (); i++)
    if (!includes (preds.m_preds[i]))
      return false;

  return true;
}

/* Create a predicate of the form OP != 0 and push it the work list CHAIN.  */

static void
push_to_worklist (tree op, pred_chain *chain, hash_set<tree> *mark_set)
{
  if (mark_set->contains (op))
    return;
  mark_set->add (op);

  pred_info arg_pred;
  arg_pred.pred_lhs = op;
  arg_pred.pred_rhs = integer_zero_node;
  arg_pred.cond_code = NE_EXPR;
  arg_pred.invert = false;
  chain->safe_push (arg_pred);
}

/* Return a pred_info for a gimple assignment CMP_ASSIGN with comparison
   rhs.  */

static pred_info
get_pred_info_from_cmp (const gimple *cmp_assign)
{
  pred_info pred;
  pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
  pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
  pred.cond_code = gimple_assign_rhs_code (cmp_assign);
  pred.invert = false;
  return pred;
}

/* If PHI is a degenerate phi with all operands having the same value (relop)
   update *PRED to that value and return true.  Otherwise return false.  */

static bool
is_degenerate_phi (gimple *phi, pred_info *pred)
{
  tree op0 = gimple_phi_arg_def (phi, 0);

  if (TREE_CODE (op0) != SSA_NAME)
    return false;

  gimple *def0 = SSA_NAME_DEF_STMT (op0);
  if (gimple_code (def0) != GIMPLE_ASSIGN)
    return false;

  if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0)) != tcc_comparison)
    return false;

  pred_info pred0 = get_pred_info_from_cmp (def0);

  unsigned n = gimple_phi_num_args (phi);
  for (unsigned i = 1; i < n; ++i)
    {
      tree op = gimple_phi_arg_def (phi, i);
      if (TREE_CODE (op) != SSA_NAME)
	return false;

      gimple *def = SSA_NAME_DEF_STMT (op);
      if (gimple_code (def) != GIMPLE_ASSIGN)
	return false;

      if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
	return false;

      pred_info pred = get_pred_info_from_cmp (def);
      if (!pred_equal_p (pred, pred0))
	return false;
    }

  *pred = pred0;
  return true;
}

/* Recursively compute the control dependence chains (paths of edges)
   from the dependent basic block, DEP_BB, up to the dominating basic
   block, DOM_BB (the head node of a chain should be dominated by it),
   storing them in the CD_CHAINS array.
   CUR_CD_CHAIN is the current chain being computed.
   *NUM_CHAINS is total number of chains in the CD_CHAINS array.
   *NUM_CALLS is the number of recursive calls to control unbounded
   recursion.
   Return true if the information is successfully computed, false if
   there is no control dependence or not computed.  */

static bool
compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
			   vec<edge> cd_chains[], unsigned *num_chains,
			   vec<edge> &cur_cd_chain, unsigned *num_calls,
			   unsigned depth = 0)
{
  if (*num_calls > (unsigned)param_uninit_control_dep_attempts)
    {
      if (dump_file)
	fprintf (dump_file, "param_uninit_control_dep_attempts exceeded: %u\n",
		 *num_calls);
      return false;
    }
  ++*num_calls;

  /* FIXME: Use a set instead.  */
  unsigned cur_chain_len = cur_cd_chain.length ();
  if (cur_chain_len > MAX_CHAIN_LEN)
    {
      if (dump_file)
	fprintf (dump_file, "MAX_CHAIN_LEN exceeded: %u\n", cur_chain_len);

      return false;
    }

  if (cur_chain_len > 5)
    {
      if (dump_file)
	fprintf (dump_file, "chain length exceeds 5: %u\n", cur_chain_len);
    }

  for (unsigned i = 0; i < cur_chain_len; i++)
    {
      edge e = cur_cd_chain[i];
      /* Cycle detected.  */
      if (e->src == dom_bb)
	{
	  if (dump_file)
	    fprintf (dump_file, "cycle detected\n");
	  return false;
	}
    }

  if (DEBUG_PREDICATE_ANALYZER && dump_file)
    fprintf (dump_file,
	     "%*s%s (dom_bb = %u, dep_bb = %u, cd_chains = { %s }, ...)\n",
	     depth, "", __func__, dom_bb->index, dep_bb->index,
	     format_edge_vecs (cd_chains, *num_chains).c_str ());

  bool found_cd_chain = false;

  /* Iterate over DOM_BB's successors.  */
  edge e;
  edge_iterator ei;
  FOR_EACH_EDGE (e, ei, dom_bb->succs)
    {
      int post_dom_check = 0;
      if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
	continue;

      basic_block cd_bb = e->dest;
      cur_cd_chain.safe_push (e);
      while (!is_non_loop_exit_postdominating (cd_bb, dom_bb))
	{
	  if (cd_bb == dep_bb)
	    {
	      /* Found a direct control dependence.  */
	      if (*num_chains < MAX_NUM_CHAINS)
		{
		  cd_chains[*num_chains] = cur_cd_chain.copy ();
		  (*num_chains)++;
		}
	      found_cd_chain = true;
	      /* Check path from next edge.  */
	      break;
	    }

	  /* Check if DEP_BB is indirectly control-dependent on DOM_BB.  */
	  if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
					 num_chains, cur_cd_chain,
					 num_calls, depth + 1))
	    {
	      found_cd_chain = true;
	      break;
	    }

	  cd_bb = get_immediate_dominator (CDI_POST_DOMINATORS, cd_bb);
	  post_dom_check++;
	  if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
	      || post_dom_check > MAX_POSTDOM_CHECK)
	    break;
	}
      cur_cd_chain.pop ();
      gcc_assert (cur_cd_chain.length () == cur_chain_len);
    }

  gcc_assert (cur_cd_chain.length () == cur_chain_len);
  return found_cd_chain;
}

/* Return true if PRED can be invalidated by any predicate in GUARD.  */

static bool
can_be_invalidated_p (const pred_info &pred, const pred_chain &guard)
{
  if (dump_file && dump_flags & TDF_DETAILS)
    {
      fprintf (dump_file, "Testing if predicate: ");
      dump_pred_info (pred);
      fprintf (dump_file, "\n...can be invalidated by a USE guard of: ");
      dump_pred_chain (guard);
      fputc ('\n', dump_file);
    }

  unsigned n = guard.length ();
  for (unsigned i = 0; i < n; ++i)
    {
      if (pred_neg_p (pred, guard[i]))
	{
	  if (dump_file && dump_flags & TDF_DETAILS)
	    {
	      fprintf (dump_file, "  Predicate invalidated by: ");
	      dump_pred_info (guard[i]);
	      fputc ('\n', dump_file);
	    }
	  return true;
	}
    }

  return false;
}

/* Return true if all predicates in PREDS are invalidated by GUARD being
   true.  */

static bool
can_be_invalidated_p (const pred_chain_union &preds, const pred_chain &guard)
{
  if (preds.is_empty ())
    return false;

  if (dump_file && dump_flags & TDF_DETAILS)
    dump_predicates (NULL, preds,
		     "Testing if anything here can be invalidated: ");

  for (unsigned i = 0; i < preds.length (); ++i)
    {
      const pred_chain &chain = preds[i];
      unsigned j;
      for (j = 0; j < chain.length (); ++j)
	if (can_be_invalidated_p (chain[j], guard))
	  break;

      /* If we were unable to invalidate any predicate in C, then there
	 is a viable path from entry to the PHI where the PHI takes
	 an interesting value and continues to a use of the PHI.  */
      if (j == chain.length ())
	return false;
    }
  return true;
}

/* Return true if none of the PHI arguments in OPNDS is used given
   the use guards in *THIS that guard the PHI's use.  */

bool
predicate::use_cannot_happen (gphi *phi, unsigned opnds)
{
  if (!m_eval.phi_arg_set (phi))
    return false;

  /* PHI_USE_GUARDS are OR'ed together.  If we have more than one
     possible guard, there's no way of knowing which guard was true.
     Since we need to be absolutely sure that the uninitialized
     operands will be invalidated, bail.  */
  const pred_chain_union &phi_use_guards = m_preds;
  if (phi_use_guards.length () != 1)
    return false;

  const pred_chain &use_guard = phi_use_guards[0];

  /* Look for the control dependencies of all the interesting operands
     and build guard predicates describing them.  */
  unsigned n = gimple_phi_num_args (phi);
  for (unsigned i = 0; i < n; ++i)
    {
      if (!MASK_TEST_BIT (opnds, i))
	continue;

      edge e = gimple_phi_arg_edge (phi, i);
      auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
      auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
      unsigned num_chains = 0;
      unsigned num_calls = 0;

      /* Build the control dependency chain for the PHI argument...  */
      if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun),
				      e->src, dep_chains, &num_chains,
				      cur_chain, &num_calls))
	return false;

      if (DEBUG_PREDICATE_ANALYZER && dump_file)
	{
	  fprintf (dump_file, "predicate::use_cannot_happen (...) "
		   "dep_chains for arg %u:\n\t", i);
	  dump_dep_chains (dep_chains, num_chains);
	}

      /* ...and convert it into a set of predicates guarding its
	 definition.  */
      predicate def_preds (m_eval);
      def_preds.init_from_control_deps (dep_chains, num_chains);
      if (def_preds.is_empty ())
	/* If there's no predicate there's no basis to rule the use out.  */
	return false;

      def_preds.simplify ();
      def_preds.normalize ();

      /* Can the guard for this PHI argument be negated by the one
	 guarding the PHI use?  */
      if (!can_be_invalidated_p (def_preds.chain (), use_guard))
	return false;
    }

  return true;
}

/* Implemented simplifications:

   1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
   2) (X AND Y) OR (!X AND Y) is equivalent to Y;
   3) X OR (!X AND Y) is equivalent to (X OR Y);
   4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
      (x != 0 AND y != 0)
   5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
      (X AND Y) OR Z

   PREDS is the predicate chains, and N is the number of chains.  */

/* Implement rule 1 above.  PREDS is the AND predicate to simplify
   in place.  */

static void
simplify_1 (pred_chain &chain)
{
  bool simplified = false;
  pred_chain s_chain = vNULL;

  unsigned n = chain.length ();
  for (unsigned i = 0; i < n; i++)
    {
      pred_info &a_pred = chain[i];

      if (!a_pred.pred_lhs
	  || !is_neq_zero_form_p (a_pred))
	continue;

      gimple *def_stmt = SSA_NAME_DEF_STMT (a_pred.pred_lhs);
      if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
	continue;

      if (gimple_assign_rhs_code (def_stmt) != BIT_IOR_EXPR)
	continue;

      for (unsigned j = 0; j < n; j++)
	{
	  const pred_info &b_pred = chain[j];

	  if (!b_pred.pred_lhs
	      || !is_neq_zero_form_p (b_pred))
	    continue;

	  if (pred_expr_equal_p (b_pred, gimple_assign_rhs1 (def_stmt))
	      || pred_expr_equal_p (b_pred, gimple_assign_rhs2 (def_stmt)))
	    {
	      /* Mark A_PRED for removal from PREDS.  */
	      a_pred.pred_lhs = NULL;
	      a_pred.pred_rhs = NULL;
	      simplified = true;
	      break;
	    }
	}
    }

  if (!simplified)
    return;

  /* Remove predicates marked above.  */
  for (unsigned i = 0; i < n; i++)
    {
      pred_info &a_pred = chain[i];
      if (!a_pred.pred_lhs)
	continue;
      s_chain.safe_push (a_pred);
    }

  chain.release ();
  chain = s_chain;
}

/* Implements rule 2 for the OR predicate PREDS:

   2) (X AND Y) OR (!X AND Y) is equivalent to Y.  */

bool
predicate::simplify_2 ()
{
  bool simplified = false;

  /* (X AND Y) OR (!X AND Y) is equivalent to Y.
     (X AND Y) OR (X AND !Y) is equivalent to X.  */

  unsigned n = m_preds.length ();
  for (unsigned i = 0; i < n; i++)
    {
      pred_chain &a_chain = m_preds[i];
      if (a_chain.length () != 2)
	continue;

      /* Create copies since the chain may be released below before
	 the copy is added to the other chain.  */
      const pred_info x = a_chain[0];
      const pred_info y = a_chain[1];

      for (unsigned j = 0; j < n; j++)
	{
	  if (j == i)
	    continue;

	  pred_chain &b_chain = m_preds[j];
	  if (b_chain.length () != 2)
	    continue;

	  const pred_info &x2 = b_chain[0];
	  const pred_info &y2 = b_chain[1];

	  if (pred_equal_p (x, x2) && pred_neg_p (y, y2))
	    {
	      /* Kill a_chain.  */
	      b_chain.release ();
	      a_chain.release ();
	      b_chain.safe_push (x);
	      simplified = true;
	      break;
	    }
	  if (pred_neg_p (x, x2) && pred_equal_p (y, y2))
	    {
	      /* Kill a_chain.  */
	      a_chain.release ();
	      b_chain.release ();
	      b_chain.safe_push (y);
	      simplified = true;
	      break;
	    }
	}
    }
  /* Now clean up the chain.  */
  if (simplified)
    {
      pred_chain_union s_preds = vNULL;
      for (unsigned i = 0; i < n; i++)
	{
	  if (m_preds[i].is_empty ())
	    continue;
	  s_preds.safe_push (m_preds[i]);
	}
      m_preds.release ();
      m_preds = s_preds;
      s_preds = vNULL;
    }

  return simplified;
}

/* Implement rule 3 for the OR predicate PREDS:

   3) x OR (!x AND y) is equivalent to x OR y.  */

bool
predicate::simplify_3 ()
{
  /* Now iteratively simplify X OR (!X AND Z ..)
       into X OR (Z ...).  */

  unsigned n = m_preds.length ();
  if (n < 2)
    return false;

  bool simplified = false;
  for (unsigned i = 0; i < n; i++)
    {
      const pred_chain &a_chain = m_preds[i];

      if (a_chain.length () != 1)
	continue;

      const pred_info &x = a_chain[0];
      for (unsigned j = 0; j < n; j++)
	{
	  if (j == i)
	    continue;

	  pred_chain b_chain = m_preds[j];
	  if (b_chain.length () < 2)
	    continue;

	  for (unsigned k = 0; k < b_chain.length (); k++)
	    {
	      const pred_info &x2 = b_chain[k];
	      if (pred_neg_p (x, x2))
		{
		  b_chain.unordered_remove (k);
		  simplified = true;
		  break;
		}
	    }
	}
    }
  return simplified;
}

/* Implement rule 4 for the OR predicate PREDS:

   2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
       (x != 0 ANd y != 0).   */

bool
predicate::simplify_4 ()
{
  bool simplified = false;
  pred_chain_union s_preds = vNULL;

  unsigned n = m_preds.length ();
  for (unsigned i = 0; i < n; i++)
    {
      pred_chain a_chain = m_preds[i];
      if (a_chain.length () != 1)
	continue;

      const pred_info &z = a_chain[0];
      if (!is_neq_zero_form_p (z))
	continue;

      gimple *def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
      if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
	continue;

      if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
	continue;

      for (unsigned j = 0; j < n; j++)
	{
	  if (j == i)
	    continue;

	  pred_chain b_chain = m_preds[j];
	  if (b_chain.length () != 2)
	    continue;

	  const pred_info &x2 = b_chain[0];
	  const pred_info &y2 = b_chain[1];
	  if (!is_neq_zero_form_p (x2) || !is_neq_zero_form_p (y2))
	    continue;

	  if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
	       && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
	      || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
		  && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
	    {
	      /* Kill a_chain.  */
	      a_chain.release ();
	      simplified = true;
	      break;
	    }
	}
    }
  /* Now clean up the chain.  */
  if (simplified)
    {
      for (unsigned i = 0; i < n; i++)
	{
	  if (m_preds[i].is_empty ())
	    continue;
	  s_preds.safe_push (m_preds[i]);
	}

      m_preds.release ();
      m_preds = s_preds;
      s_preds = vNULL;
    }

  return simplified;
}

/* Simplify predicates in *THIS.  */

void
predicate::simplify (gimple *use_or_def, bool is_use)
{
  if (dump_file && dump_flags & TDF_DETAILS)
    {
      fprintf (dump_file, "Before simplication ");
      dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
    }

  unsigned n = m_preds.length ();
  for (unsigned i = 0; i < n; i++)
    ::simplify_1 (m_preds[i]);

  if (n < 2)
    return;

  bool changed;
  do
    {
      changed = false;
      if (simplify_2 ())
	changed = true;

      if (simplify_3 ())
	changed = true;

      if (simplify_4 ())
	changed = true;
    }
  while (changed);
}

/* Attempt to normalize predicate chains by following UD chains by
   building up a big tree of either IOR operations or AND operations,
   and converting the IOR tree into a pred_chain_union or the BIT_AND
   tree into a pred_chain.
   Example:

  _3 = _2 RELOP1 _1;
  _6 = _5 RELOP2 _4;
  _9 = _8 RELOP3 _7;
  _10 = _3 | _6;
  _12 = _9 | _0;
  _t = _10 | _12;

  then _t != 0 will be normalized into a pred_chain_union

   (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)

   Similarly given:

  _3 = _2 RELOP1 _1;
  _6 = _5 RELOP2 _4;
  _9 = _8 RELOP3 _7;
  _10 = _3 & _6;
  _12 = _9 & _0;

  then _t != 0 will be normalized into a pred_chain:
  (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
  */

/* Store a PRED in *THIS.  */

void
predicate::push_pred (const pred_info &pred)
{
  pred_chain chain = vNULL;
  chain.safe_push (pred);
  m_preds.safe_push (chain);
}

/* Dump predicates in *THIS for STMT prepended by MSG.  */

void
predicate::dump (gimple *stmt, const char *msg) const
{
  fprintf (dump_file, "%s", msg);
  if (stmt)
    {
      fputc ('\t', dump_file);
      print_gimple_stmt (dump_file, stmt, 0);
      fprintf (dump_file, "  is conditional on:\n");
    }

  unsigned np = m_preds.length ();
  if (np == 0)
    {
      fprintf (dump_file, "\t(empty)\n");
      return;
    }

  {
    tree expr = build_pred_expr (m_preds);
    char *str = print_generic_expr_to_str (expr);
    fprintf (dump_file, "\t%s (expanded)\n", str);
    free (str);
  }

  if (np > 1)
    fprintf (dump_file, "\tOR (");
  else
    fputc ('\t', dump_file);
  for (unsigned i = 0; i < np; i++)
    {
      dump_pred_chain (m_preds[i]);
      if (i < np - 1)
	fprintf (dump_file, ", ");
      else if (i > 0)
	fputc (')', dump_file);
    }
  fputc ('\n', dump_file);
}

/* Initialize *THIS with the predicates of the control dependence chains
   between the basic block DEF_BB that defines a variable of interst and
   USE_BB that uses the variable, respectively.  */

predicate::predicate (basic_block def_bb, basic_block use_bb, func_t &eval)
  : m_preds (vNULL), m_eval (eval)
{
  /* Set CD_ROOT to the basic block closest to USE_BB that is the control
     equivalent of (is guarded by the same predicate as) DEF_BB that also
     dominates USE_BB.  */
  basic_block cd_root = def_bb;
  while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
    {
      /* Find CD_ROOT's closest postdominator that's its control
	 equivalent.  */
      if (basic_block bb = find_control_equiv_block (cd_root))
	if (dominated_by_p (CDI_DOMINATORS, use_bb, bb))
	  {
	    cd_root = bb;
	    continue;
	  }

      break;
    }

  /* Set DEP_CHAINS to the set of edges between CD_ROOT and USE_BB.
     Each DEP_CHAINS element is a series of edges whose conditions
     are logical conjunctions.  Together, the DEP_CHAINS vector is
     used below to initialize an OR expression of the conjunctions.  */
  unsigned num_calls = 0;
  unsigned num_chains = 0;
  auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
  auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;

  compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
			     cur_chain, &num_calls);

  if (DEBUG_PREDICATE_ANALYZER && dump_file)
    {
      fprintf (dump_file, "predicate::predicate (def_bb = %u, use_bb = %u, func_t) "
	       "initialized from %u dep_chains:\n\t",
	       def_bb->index, use_bb->index, num_chains);
      dump_dep_chains (dep_chains, num_chains);
    }

  /* From the set of edges computed above initialize *THIS as the OR
     condition under which the definition in DEF_BB is used in USE_BB.
     Each OR subexpression is represented by one element of DEP_CHAINS,
     where each element consists of a series of AND subexpressions.  */
  init_from_control_deps (dep_chains, num_chains);
}

/* Release resources in *THIS.  */

predicate::~predicate ()
{
  unsigned n = m_preds.length ();
  for (unsigned i = 0; i != n; ++i)
    m_preds[i].release ();
  m_preds.release ();
}

/* Copy-assign RHS to *THIS.  */

predicate&
predicate::operator= (const predicate &rhs)
{
  if (this == &rhs)
    return *this;

  /* FIXME: Make this a compile-time constraint?  */
  gcc_assert (&m_eval == &rhs.m_eval);

  unsigned n = m_preds.length ();
  for (unsigned i = 0; i != n; ++i)
    m_preds[i].release ();
  m_preds.release ();

  n = rhs.m_preds.length ();
  for (unsigned i = 0; i != n; ++i)
    {
      const pred_chain &chain = rhs.m_preds[i];
      m_preds.safe_push (chain.copy ());
    }

  return *this;
}

/* For each use edge of PHI, compute all control dependence chains
   and convert those to the composite predicates in M_PREDS.
   Return true if a nonempty predicate has been obtained.  */

bool
predicate::init_from_phi_def (gphi *phi)
{
  gcc_assert (is_empty ());

  basic_block phi_bb = gimple_bb (phi);
  /* Find the closest dominating bb to be the control dependence root.  */
  basic_block cd_root = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
  if (!cd_root)
    return false;

  /* Set DEF_EDGES to the edges to the PHI from the bb's that provide
     definitions of each of the PHI operands for which M_EVAL is false.  */
  auto_vec<edge> def_edges;
  hash_set<gimple *> visited_phis;
  collect_phi_def_edges (phi, cd_root, &def_edges, m_eval, &visited_phis);

  unsigned nedges = def_edges.length ();
  if (nedges == 0)
    return false;

  unsigned num_chains = 0;
  auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
  auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
  for (unsigned i = 0; i < nedges; i++)
    {
      edge e = def_edges[i];
      unsigned num_calls = 0;
      unsigned prev_nc = num_chains;
      compute_control_dep_chain (cd_root, e->src, dep_chains,
				 &num_chains, cur_chain, &num_calls);

      /* Update the newly added chains with the phi operand edge.  */
      if (EDGE_COUNT (e->src->succs) > 1)
	{
	  if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
	    dep_chains[num_chains++] = vNULL;
	  for (unsigned j = prev_nc; j < num_chains; j++)
	    dep_chains[j].safe_push (e);
	}
    }

  /* Convert control dependence chains to the predicate in *THIS under
     which the PHI operands are defined to values for which M_EVAL is
     false.  */
  init_from_control_deps (dep_chains, num_chains);
  return !is_empty ();
}

/* Compute the predicates that guard the use USE_STMT and check if
   the incoming paths that have an empty (or possibly empty) definition
   can be pruned.  Return true if it can be determined that the use of
   PHI's def in USE_STMT is guarded by a predicate set that does not
   overlap with the predicate sets of all runtime paths that do not
   have a definition.

   Return false if the use is not guarded or if it cannot be determined.
   USE_BB is the bb of the use (for phi operand use, the bb is not the bb
   of the phi stmt, but the source bb of the operand edge).

   OPNDS is a bitmap with a bit set for each PHI operand of interest.

   THIS->M_PREDS contains the (memoized) defining predicate chains of
   a PHI.  If THIS->M_PREDS is empty, the PHI's defining predicate
   chains are computed and stored into THIS->M_PREDS as needed.

   VISITED_PHIS is a pointer set of phis being visited.  */

bool
predicate::is_use_guarded (gimple *use_stmt, basic_block use_bb,
			   gphi *phi, unsigned opnds,
			   hash_set<gphi *> *visited)
{
  if (visited->add (phi))
    return false;

  /* The basic block where the PHI is defined.  */
  basic_block def_bb = gimple_bb (phi);

  /* Try to build the predicate expression under which the PHI flows
     into its use.  This will be empty if the PHI is defined and used
     in the same bb.  */
  predicate use_preds (def_bb, use_bb, m_eval);

  if (is_non_loop_exit_postdominating (use_bb, def_bb))
    {
      if (is_empty ())
	{
	  /* Lazily initialize *THIS from the PHI and build its use
	     expression.  */
	  init_from_phi_def (phi);
	  m_use_expr = build_pred_expr (use_preds.m_preds);
	}

      /* The use is not guarded.  */
      return false;
    }

  if (use_preds.is_empty ())
    return false;

  /* Try to prune the dead incoming phi edges.  */
  if (!use_preds.overlap (phi, opnds, visited))
    {
      if (DEBUG_PREDICATE_ANALYZER && dump_file)
	fputs ("found predicate overlap\n", dump_file);

      return true;
    }

  /* We might be able to prove that if the control dependencies for OPNDS
     are true, the control dependencies for USE_STMT can never be true.  */
  if (use_preds.use_cannot_happen (phi, opnds))
    return true;

  if (is_empty ())
    {
      /* Lazily initialize *THIS from PHI.  */
      if (!init_from_phi_def (phi))
	{
	  m_use_expr = build_pred_expr (use_preds.m_preds);
	  return false;
	}

      simplify (phi);
      normalize (phi);
    }

  use_preds.simplify (use_stmt, /*is_use=*/true);
  use_preds.normalize (use_stmt, /*is_use=*/true);

  /* Return true if the predicate guarding the valid definition (i.e.,
     *THIS) is a superset of the predicate guarding the use (i.e.,
     USE_PREDS).  */
  if (superset_of (use_preds))
    return true;

  m_use_expr = build_pred_expr (use_preds.m_preds);

  return false;
}

/* Public interface to the above. */

bool
predicate::is_use_guarded (gimple *stmt, basic_block use_bb, gphi *phi,
			   unsigned opnds)
{
  hash_set<gphi *> visited;
  return is_use_guarded (stmt, use_bb, phi, opnds, &visited);
}

/* Normalize predicate PRED:
   1) if PRED can no longer be normalized, append it to *THIS.
   2) otherwise if PRED is of the form x != 0, follow x's definition
      and put normalized predicates into WORK_LIST.  */

void
predicate::normalize (pred_chain *norm_chain,
		      pred_info pred,
		      tree_code and_or_code,
		      pred_chain *work_list,
		      hash_set<tree> *mark_set)
{
  if (!is_neq_zero_form_p (pred))
    {
      if (and_or_code == BIT_IOR_EXPR)
	push_pred (pred);
      else
	norm_chain->safe_push (pred);
      return;
    }

  gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);

  if (gimple_code (def_stmt) == GIMPLE_PHI
      && is_degenerate_phi (def_stmt, &pred))
    /* PRED has been modified above.  */
    work_list->safe_push (pred);
  else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR)
    {
      unsigned n = gimple_phi_num_args (def_stmt);

      /* Punt for a nonzero constant.  The predicate should be one guarding
	 the phi edge.  */
      for (unsigned i = 0; i < n; ++i)
	{
	  tree op = gimple_phi_arg_def (def_stmt, i);
	  if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
	    {
	      push_pred (pred);
	      return;
	    }
	}

      for (unsigned i = 0; i < n; ++i)
	{
	  tree op = gimple_phi_arg_def (def_stmt, i);
	  if (integer_zerop (op))
	    continue;

	  push_to_worklist (op, work_list, mark_set);
	}
    }
  else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
    {
      if (and_or_code == BIT_IOR_EXPR)
	push_pred (pred);
      else
	norm_chain->safe_push (pred);
    }
  else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
    {
      /* Avoid splitting up bit manipulations like x & 3 or y | 1.  */
      if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt)))
	{
	  /* But treat x & 3 as a condition.  */
	  if (and_or_code == BIT_AND_EXPR)
	    {
	      pred_info n_pred;
	      n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt);
	      n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt);
	      n_pred.cond_code = and_or_code;
	      n_pred.invert = false;
	      norm_chain->safe_push (n_pred);
	    }
	}
      else
	{
	  push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
	  push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
	}
    }
  else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
	   == tcc_comparison)
    {
      pred_info n_pred = get_pred_info_from_cmp (def_stmt);
      if (and_or_code == BIT_IOR_EXPR)
	push_pred (n_pred);
      else
	norm_chain->safe_push (n_pred);
    }
  else
    {
      if (and_or_code == BIT_IOR_EXPR)
	push_pred (pred);
      else
	norm_chain->safe_push (pred);
    }
}

/* Normalize PRED and store the normalized predicates in THIS->M_PREDS.  */

void
predicate::normalize (const pred_info &pred)
{
  if (!is_neq_zero_form_p (pred))
    {
      push_pred (pred);
      return;
    }

  tree_code and_or_code = ERROR_MARK;

  gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
  if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
    and_or_code = gimple_assign_rhs_code (def_stmt);
  if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR)
    {
      if (TREE_CODE_CLASS (and_or_code) == tcc_comparison)
	{
	  pred_info n_pred = get_pred_info_from_cmp (def_stmt);
	  push_pred (n_pred);
	}
      else
	push_pred (pred);
      return;
    }


  pred_chain norm_chain = vNULL;
  pred_chain work_list = vNULL;
  work_list.safe_push (pred);
  hash_set<tree> mark_set;

  while (!work_list.is_empty ())
    {
      pred_info a_pred = work_list.pop ();
      normalize (&norm_chain, a_pred, and_or_code, &work_list, &mark_set);
    }

  if (and_or_code == BIT_AND_EXPR)
    m_preds.safe_push (norm_chain);

  work_list.release ();
}

/* Normalize a single predicate PRED_CHAIN and append it to *THIS.  */

void
predicate::normalize (const pred_chain &chain)
{
  pred_chain work_list = vNULL;
  hash_set<tree> mark_set;
  for (unsigned i = 0; i < chain.length (); i++)
    {
      work_list.safe_push (chain[i]);
      mark_set.add (chain[i].pred_lhs);
    }

  /* Normalized chain of predicates built up below.  */
  pred_chain norm_chain = vNULL;
  while (!work_list.is_empty ())
    {
      pred_info pi = work_list.pop ();
      predicate pred (m_eval);
      /* The predicate object is not modified here, only NORM_CHAIN and
	 WORK_LIST are appended to.  */
      pred.normalize (&norm_chain, pi, BIT_AND_EXPR, &work_list, &mark_set);
    }

  m_preds.safe_push (norm_chain);
  work_list.release ();
}

/* Normalize predicate chains in THIS.  */

void
predicate::normalize (gimple *use_or_def, bool is_use)
{
  if (dump_file && dump_flags & TDF_DETAILS)
    {
      fprintf (dump_file, "Before normalization ");
      dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
    }

  predicate norm_preds (m_eval);
  for (unsigned i = 0; i < m_preds.length (); i++)
    {
      if (m_preds[i].length () != 1)
	norm_preds.normalize (m_preds[i]);
      else
	norm_preds.normalize (m_preds[i][0]);
    }

  *this = norm_preds;

  if (dump_file)
    {
      fprintf (dump_file, "After normalization ");
      dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
    }
}

/* Convert the chains of control dependence edges into a set of predicates.
   A control dependence chain is represented by a vector edges.  DEP_CHAINS
   points to an array of NUM_CHAINS dependence chains. One edge in
   a dependence chain is mapped to predicate expression represented by
   pred_info type.  One dependence chain is converted to a composite
   predicate that is the result of AND operation of pred_info mapped to
   each edge.  A composite predicate is represented by a vector of
   pred_info.  Sets M_PREDS to the resulting composite predicates.  */

void
predicate::init_from_control_deps (const vec<edge> *dep_chains,
				   unsigned num_chains)
{
  gcc_assert (is_empty ());

  bool has_valid_pred = false;
  if (num_chains == 0)
    return;

  if (num_chains >= MAX_NUM_CHAINS)
    {
      if (dump_file)
	fprintf (dump_file, "MAX_NUM_CHAINS exceeded: %u\n", num_chains);
      return;
    }

  /* Convert the control dependency chain into a set of predicates.  */
  m_preds.reserve (num_chains);

  for (unsigned i = 0; i < num_chains; i++)
    {
      /* One path through the CFG represents a logical conjunction
	 of the predicates.  */
      const vec<edge> &path = dep_chains[i];

      has_valid_pred = false;
      /* The chain of predicates guarding the definition along this path.  */
      pred_chain t_chain{ };
      for (unsigned j = 0; j < path.length (); j++)
	{
	  edge e = path[j];
	  basic_block guard_bb = e->src;
	  /* Ignore empty forwarder blocks.  */
	  if (empty_block_p (guard_bb) && single_succ_p (guard_bb))
	    continue;

	  /* An empty basic block here is likely a PHI, and is not one
	     of the cases we handle below.  */
	  gimple_stmt_iterator gsi = gsi_last_bb (guard_bb);
	  if (gsi_end_p (gsi))
	    {
	      has_valid_pred = false;
	      break;
	    }
	  /* Get the conditional controlling the bb exit edge.  */
	  gimple *cond_stmt = gsi_stmt (gsi);
	  if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
	    /* Ignore EH edge.  Can add assertion on the other edge's flag.  */
	    continue;
	  /* Skip if there is essentially one succesor.  */
	  if (EDGE_COUNT (e->src->succs) == 2)
	    {
	      edge e1;
	      edge_iterator ei1;
	      bool skip = false;

	      FOR_EACH_EDGE (e1, ei1, e->src->succs)
		{
		  if (EDGE_COUNT (e1->dest->succs) == 0)
		    {
		      skip = true;
		      break;
		    }
		}
	      if (skip)
		continue;
	    }
	  if (gimple_code (cond_stmt) == GIMPLE_COND)
	    {
	      /* The true edge corresponds to the uninteresting condition.
		 Add the negated predicate(s) for the edge to record
		 the interesting condition.  */
	      pred_info one_pred;
	      one_pred.pred_lhs = gimple_cond_lhs (cond_stmt);
	      one_pred.pred_rhs = gimple_cond_rhs (cond_stmt);
	      one_pred.cond_code = gimple_cond_code (cond_stmt);
	      one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE);

	      t_chain.safe_push (one_pred);

	      if (DEBUG_PREDICATE_ANALYZER && dump_file)
		{
		  fprintf (dump_file, "one_pred = ");
		  dump_pred_info (one_pred);
		  fputc ('\n', dump_file);
		}

	      has_valid_pred = true;
	    }
	  else if (gswitch *gs = dyn_cast<gswitch *> (cond_stmt))
	    {
	      /* Avoid quadratic behavior.  */
	      if (gimple_switch_num_labels (gs) > MAX_SWITCH_CASES)
		{
		  has_valid_pred = false;
		  break;
		}
	      /* Find the case label.  */
	      tree l = NULL_TREE;
	      unsigned idx;
	      for (idx = 0; idx < gimple_switch_num_labels (gs); ++idx)
		{
		  tree tl = gimple_switch_label (gs, idx);
		  if (e->dest == label_to_block (cfun, CASE_LABEL (tl)))
		    {
		      if (!l)
			l = tl;
		      else
			{
			  l = NULL_TREE;
			  break;
			}
		    }
		}
	      /* If more than one label reaches this block or the case
		 label doesn't have a single value (like the default one)
		 fail.  */
	      if (!l
		  || !CASE_LOW (l)
		  || (CASE_HIGH (l)
		      && !operand_equal_p (CASE_LOW (l), CASE_HIGH (l), 0)))
		{
		  has_valid_pred = false;
		  break;
		}

	      pred_info one_pred;
	      one_pred.pred_lhs = gimple_switch_index (gs);
	      one_pred.pred_rhs = CASE_LOW (l);
	      one_pred.cond_code = EQ_EXPR;
	      one_pred.invert = false;
	      t_chain.safe_push (one_pred);
	      has_valid_pred = true;
	    }
	  else
	    {
	      /* Disabled.  See PR 90994.
		 has_valid_pred = false;  */
	      break;
	    }
	}

      if (!has_valid_pred)
	break;
      else
	m_preds.safe_push (t_chain);
    }

  if (DEBUG_PREDICATE_ANALYZER && dump_file)
    {
      fprintf (dump_file, "init_from_control_deps {%s}:\n",
	       format_edge_vecs (dep_chains, num_chains).c_str ());
      dump (NULL, "");
    }

  if (has_valid_pred)
    gcc_assert (m_preds.length () != 0);
  else
    /* Clear M_PREDS to indicate failure.  */
    m_preds.release ();
}

/* Return the predicate expression guarding the definition of
   the interesting variable.  When INVERT is set, return the logical
   NOT of the predicate.  */

tree
predicate::def_expr (bool invert /* = false */) const
{
  /* The predicate is stored in an inverted form.  */
  return build_pred_expr (m_preds, !invert);
}

/* Return the predicate expression guarding the use of the interesting
   variable or null if the use predicate hasn't been determined yet.  */

tree
predicate::use_expr () const
{
  return m_use_expr;
}

/* Return a logical AND expression with the (optionally inverted) predicate
   expression guarding the definition of the interesting variable and one
   guarding its use.  Return null if the use predicate hasn't yet been
   determined.  */

tree
predicate::expr (bool invert /* = false */) const
{
  if (!m_use_expr)
    return NULL_TREE;

  tree expr = build_pred_expr (m_preds, !invert);
  return build2 (TRUTH_AND_EXPR, boolean_type_node, expr, m_use_expr);
}