[TCWG CI] Regression caused by gcc: Factor predidacte analysis out of tree-ssa-uninit.c into its own module. - linaro-toolchain

21 Sep 2021

[TCWG CI] Regression caused by gcc: Factor predidacte analysis out of tree-ssa-uninit.c into its own module.:
commit 94c12ffac234b29a702aa7b6730f2678265857c8
Author: Martin Sebor msebor@redhat.com
Factor predidacte analysis out of tree-ssa-uninit.c into its own module.
Results regressed to
# reset_artifacts:
-10
# build_abe binutils:
-9
# build_abe stage1:
-5
# build_abe qemu:
-2
# linux_n_obj:
6240
# First few build errors in logs:
from
# reset_artifacts:
-10
# build_abe binutils:
-9
# build_abe stage1:
-5
# build_abe qemu:
-2
# linux_n_obj:
6999
# linux build successful:
all
# linux boot successful:
boot
THIS IS THE END OF INTERESTING STUFF.  BELOW ARE LINKS TO BUILDS, REPRODUCTION INSTRUCTIONS, AND THE RAW COMMIT.
This commit has regressed these CI configurations:
 - tcwg_kernel/gnu-master-arm-mainline-defconfig
First_bad build: https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def...
Last_good build: https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def...
Baseline build: https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def...
Even more details: https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def...
Reproduce builds:
<cut>
mkdir investigate-gcc-94c12ffac234b29a702aa7b6730f2678265857c8
cd investigate-gcc-94c12ffac234b29a702aa7b6730f2678265857c8
# Fetch scripts
git clone https://git.linaro.org/toolchain/jenkins-scripts
# Fetch manifests and test.sh script
mkdir -p artifacts/manifests
curl -o artifacts/manifests/build-baseline.sh https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def... --fail
curl -o artifacts/manifests/build-parameters.sh https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def... --fail
curl -o artifacts/test.sh https://ci.linaro.org/job/tcwg_kernel-gnu-bisect-gnu-master-arm-mainline-def... --fail
chmod +x artifacts/test.sh
# Reproduce the baseline build (build all pre-requisites)
./jenkins-scripts/tcwg_kernel-build.sh @@ artifacts/manifests/build-baseline.sh
# Save baseline build state (which is then restored in artifacts/test.sh)
mkdir -p ./bisect
rsync -a --del --delete-excluded --exclude /bisect/ --exclude /artifacts/ --exclude /gcc/ ./ ./bisect/baseline/
cd gcc
# Reproduce first_bad build
git checkout --detach 94c12ffac234b29a702aa7b6730f2678265857c8
../artifacts/test.sh
# Reproduce last_good build
git checkout --detach 51166eb2c534692c3c7779def24f83c8c3811b98
../artifacts/test.sh
cd ..
</cut>
Full commit (up to 1000 lines):
<cut>
commit 94c12ffac234b29a702aa7b6730f2678265857c8
Author: Martin Sebor msebor@redhat.com
Date:   Fri Sep 17 15:39:13 2021 -0600
Factor predidacte analysis out of tree-ssa-uninit.c into its own module.
gcc/ChangeLog:
* Makefile.in (OBJS): Add gimple-predicate-analysis.o.
            * tree-ssa-uninit.c (max_phi_args): Move to gimple-predicate-analysis.
            (MASK_SET_BIT, MASK_TEST_BIT, MASK_EMPTY): Same.
            (check_defs): Add comment.
            (can_skip_redundant_opnd): Update comment.
            (compute_uninit_opnds_pos): Adjust to namespace change.
            (find_pdom): Move to gimple-predicate-analysis.cc.
            (find_dom): Same.
            (struct uninit_undef_val_t): New.
            (is_non_loop_exit_postdominating): Move to gimple-predicate-analysis.cc.
            (find_control_equiv_block): Same.
            (MAX_NUM_CHAINS, MAX_CHAIN_LEN, MAX_POSTDOM_CHECK): Same.
            (MAX_SWITCH_CASES): Same.
            (compute_control_dep_chain): Same.
            (find_uninit_use): Use predicate analyzer.
            (struct pred_info): Move to gimple-predicate-analysis.
            (convert_control_dep_chain_into_preds): Same.
            (find_predicates): Same.
            (collect_phi_def_edges): Same.
            (warn_uninitialized_phi): Use predicate analyzer.
            (find_def_preds): Move to gimple-predicate-analysis.
            (dump_pred_info): Same.
            (dump_pred_chain): Same.
            (dump_predicates): Same.
            (destroy_predicate_vecs): Remove.
            (execute_late_warn_uninitialized): New.
            (get_cmp_code): Move to gimple-predicate-analysis.
            (is_value_included_in): Same.
            (value_sat_pred_p): Same.
            (find_matching_predicate_in_rest_chains): Same.
            (is_use_properly_guarded): Same.
            (prune_uninit_phi_opnds): Same.
            (find_var_cmp_const): Same.
            (use_pred_not_overlap_with_undef_path_pred): Same.
            (pred_equal_p): Same.
            (is_neq_relop_p): Same.
            (is_neq_zero_form_p): Same.
            (pred_expr_equal_p): Same.
            (is_pred_expr_subset_of): Same.
            (is_pred_chain_subset_of): Same.
            (is_included_in): Same.
            (is_superset_of): Same.
            (pred_neg_p): Same.
            (simplify_pred): Same.
            (simplify_preds_2): Same.
            (simplify_preds_3): Same.
            (simplify_preds_4): Same.
            (simplify_preds): Same.
            (push_pred): Same.
            (push_to_worklist): Same.
            (get_pred_info_from_cmp): Same.
            (is_degenerated_phi): Same.
            (normalize_one_pred_1): Same.
            (normalize_one_pred): Same.
            (normalize_one_pred_chain): Same.
            (normalize_preds): Same.
            (can_one_predicate_be_invalidated_p): Same.
            (can_chain_union_be_invalidated_p): Same.
            (uninit_uses_cannot_happen): Same.
            (pass_late_warn_uninitialized::execute): Define.
            * gimple-predicate-analysis.cc: New file.
            * gimple-predicate-analysis.h: New file.
---
 gcc/Makefile.in                  |    1 +
 gcc/gimple-predicate-analysis.cc | 2400 +++++++++++++++++++++++++++++++++++++
 gcc/gimple-predicate-analysis.h  |  158 +++
 gcc/tree-ssa-uninit.c            | 2431 +++-----------------------------------
 4 files changed, 2741 insertions(+), 2249 deletions(-)

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index b8229adf580..f36ffa4740b 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1394,6 +1394,7 @@ OBJS = \
    gimple-loop-jam.o \
    gimple-loop-versioning.o \
    gimple-low.o \
+	gimple-predicate-analysis.o \
    gimple-pretty-print.o \
    gimple-range.o \
    gimple-range-cache.o \
diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
new file mode 100644
index 00000000000..3404f2d630a
--- /dev/null
+++ b/gcc/gimple-predicate-analysis.cc
@@ -0,0 +1,2400 @@
+/* Support for simple predicate analysis.
+
+   Copyright (C) 2001-2021 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
+
+/* Find the immediate postdominator of the specified basic block BB.  */
+
+static inline basic_block
+find_pdom (basic_block bb)
+{
+  basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
+  if (bb == exit_bb)
+    return exit_bb;
+
+  if (basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb))
+    return pdom;
+
+  return exit_bb;
+}
+
+/* Find the immediate dominator of the specified basic block BB.  */
+
+static inline basic_block
+find_dom (basic_block bb)
+{
+  basic_block entry_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+  if (bb == entry_bb)
+    return entry_bb;
+
+  if (basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb))
+    return dom;
+
+  return entry_bb;
+}
+
+/* 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 = find_pdom (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;
+
</cut>

    