tree-optimization/106722 - uninit analysis with long def -> use path

The following applies similar measures as r13-2133-ge66cf626c72d58
to the computation of the use predicate when the path from PHI def
to use is too long and we run into compute_control_dep_chain limits.

It also moves the preprocessor define limits internal.

This resolves the reduced testcase but not the original one.

	PR tree-optimization/106722
	* gimple-predicate-analysis.h (MAX_NUM_CHAINS, MAX_CHAIN_LEN,
	MAX_POSTDOM_CHECK, MAX_SWITCH_CASES): Move ...
	* gimple-predicate-analysis.cc: ... here and document.
	(simple_control_dep_chain): New function, factored from
	predicate::use_cannot_happen.
	(predicate::use_cannot_happen): Adjust.
	(predicate::predicate): Use simple_control_dep_chain as fallback.

	* g++.dg/uninit-pr106722-1.C: New testcase.

3 files changed, 117 insertions, 20 deletions

diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index e8e2dbf..a429165 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -46,6 +46,19 @@
 
 #define DEBUG_PREDICATE_ANALYZER 1
 
+/* In our predicate normal form we have MAX_NUM_CHAINS or predicates
+   and in those MAX_CHAIN_LEN (inverted) and predicates.  */
+#define MAX_NUM_CHAINS 8
+#define MAX_CHAIN_LEN 5
+
+/* When enumerating paths between two blocks this limits the number of
+   post-dominator skips between two edges possibly defining a predicate.  */
+#define MAX_POSTDOM_CHECK 8
+
+/* The limit for the number of switch cases when we do the linear search
+   for the case corresponding to an edge.  */
+#define MAX_SWITCH_CASES 40
+
 /* Return true if, when BB1 is postdominating BB2, BB1 is a loop exit.  */
 
 static bool
@@ -1034,6 +1047,36 @@ is_degenerate_phi (gimple *phi, pred_info *pred)
   return true;
 }
 
+/* If compute_control_dep_chain bailed out due to limits this routine
+   tries to build a partial sparse path using dominators.  Returns
+   path edges whose predicates are always true when reaching E.  */
+
+static void
+simple_control_dep_chain (vec<edge>& chain, basic_block from, basic_block to)
+{
+  if (!dominated_by_p (CDI_DOMINATORS, to, from))
+    return;
+
+  basic_block src = to;
+  while (src != from
+	 && chain.length () <= MAX_CHAIN_LEN)
+    {
+      basic_block dest = src;
+      src = get_immediate_dominator (CDI_DOMINATORS, src);
+      edge pred_e;
+      if (single_pred_p (dest)
+	  && (pred_e = find_edge (src, dest)))
+	chain.safe_push (pred_e);
+    }
+}
+
+static void
+simple_control_dep_chain (vec<edge>& chain, basic_block from, edge to)
+{
+  chain.safe_push (to);
+  simple_control_dep_chain (chain, from, to->src);
+}
+
 /* 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),
@@ -1273,20 +1316,8 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
 	  /* If compute_control_dep_chain bailed out due to limits
 	     build a partial sparse path using dominators.  Collect
 	     only edges whose predicates are always true when reaching E.  */
-	  cur_chain.truncate (0);
-	  cur_chain.quick_push (e);
-	  basic_block src = e->src;
-	  while (src->index != ENTRY_BLOCK
-		 && cur_chain.length () <= MAX_CHAIN_LEN)
-	    {
-	      basic_block dest = src;
-	      src = get_immediate_dominator (CDI_DOMINATORS, src);
-	      edge pred_e;
-	      if (single_pred_p (dest)
-		  && (pred_e = find_edge (src, dest)))
-		cur_chain.quick_push (pred_e);
-	    }
-	  dep_chains[0] = cur_chain.copy ();
+	  simple_control_dep_chain (dep_chains[0],
+				    ENTRY_BLOCK_PTR_FOR_FN (cfun), e);
 	  num_chains++;
 	}
 
@@ -1737,8 +1768,13 @@ predicate::predicate (basic_block def_bb, basic_block use_bb, func_t &eval)
   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 (!compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
+				  cur_chain, &num_calls))
+    {
+      gcc_assert (num_chains == 0);
+      simple_control_dep_chain (dep_chains[0], cd_root, use_bb);
+      num_chains++;
+    }
 
   if (DEBUG_PREDICATE_ANALYZER && dump_file)
     {
diff --git a/gcc/gimple-predicate-analysis.h b/gcc/gimple-predicate-analysis.h
index 204cdbc..7767229 100644
--- a/gcc/gimple-predicate-analysis.h
+++ b/gcc/gimple-predicate-analysis.h
@@ -22,10 +22,6 @@
 #ifndef GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
 #define GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
 
-#define MAX_NUM_CHAINS 8
-#define MAX_CHAIN_LEN 5
-#define MAX_POSTDOM_CHECK 8
-#define MAX_SWITCH_CASES 40
 
 /* Represents a simple Boolean predicate.  */
 struct pred_info
diff --git a/gcc/testsuite/g++.dg/uninit-pr106722-1.C b/gcc/testsuite/g++.dg/uninit-pr106722-1.C
new file mode 100644
index 0000000..a10f8dd
--- /dev/null
+++ b/gcc/testsuite/g++.dg/uninit-pr106722-1.C
@@ -0,0 +1,65 @@
+// { dg-do compile }
+// { dg-require-effective-target c++11 }
+// { dg-options "-O2 -Wmaybe-uninitialized --param logical-op-non-short-circuit=0" }
+long pow2p_hwi_x;
+bool exact_log2___trans_tmp_5, exact_log2___trans_tmp_4;
+int exact_log2(long x) {
+  exact_log2___trans_tmp_5 = pow2p_hwi_x && exact_log2___trans_tmp_4;
+  return exact_log2___trans_tmp_5 ? x : 1;
+}
+enum signop {};
+template <typename T1, typename T2> void rshift(T1, T2, signop);
+struct generic_wide_int {
+  template <typename T> generic_wide_int(T);
+};
+template <unsigned N, typename> struct poly_int_pod {
+  bool is_constant() const;
+  template <typename T> bool is_constant(T *) const;
+  int coeffs[N];
+};
+template <unsigned N, typename C>
+template <typename T>
+bool poly_int_pod<N, C>::is_constant(T *const_value) const {
+  if (is_constant()) {
+    *const_value = coeffs[0];
+    return true;
+  }
+  return false;
+}
+struct poly_int : poly_int_pod<1, int> {
+  template <typename C0> poly_int(C0);
+};
+enum tree_code_class {} tree_code_type;
+void tree_class_check_failed(int *, tree_code_class, char *, int, char *)
+    __attribute__((__noreturn__));
+int tree_class_check___t, tree_class_check___l,
+    vect_gen_vector_loop_niters_loop_vinfo;
+char tree_class_check___f, tree_class_check___g;
+tree_code_class tree_class_check___class;
+int *tree_class_check() {
+  if (tree_code_type)
+    tree_class_check_failed(&tree_class_check___t, tree_class_check___class,
+                            &tree_class_check___f, tree_class_check___l,
+                            &tree_class_check___g);
+  return &tree_class_check___t;
+}
+int *build_int_cst(int, long);
+bool is_gimple_val(int);
+void force_gimple_operand(int, int *, bool, int);
+void vect_gen_vector_loop_niters(bool niters_no_overflow) {
+  poly_int vf(vect_gen_vector_loop_niters_loop_vinfo);
+  int *log_vf = nullptr;
+  long const_vf;
+  if (vf.is_constant(&const_vf))
+    log_vf = build_int_cst(0, 0);
+  if (is_gimple_val(0)) {
+    int stmts;
+    force_gimple_operand(0, &stmts, true, 0);
+    if (stmts && log_vf)
+      if (niters_no_overflow) {
+        generic_wide_int __trans_tmp_1(tree_class_check());
+        int __trans_tmp_2 = exact_log2(const_vf); // { dg-bogus "uninitialized" }
+        rshift(__trans_tmp_1, __trans_tmp_2, (signop)0);
+      }
+  }
+}