[PATCH][RFC] Unify MAX_NUM_CHAINS and MAX_CHAIN_LEN to --param uninit-max-predicate-size

[PATCH][RFC] Unify MAX_NUM_CHAINS and MAX_CHAIN_LEN to --param uninit-max-predicate-size

[Richard Biener]

The following exposes the MAX_NUM_CHAINS and MAX_CHAIN_LEN to the user
by adding a --param uninit-max-predicate-size and re-doing the
limits on the whole predicate expression size rather than limiting
the number of OR and AND elements separately.  The following goes
a step further and for a single AND chain allows an arbitrary size,
limiting that only with the computational --param
uninit-control-dep-attempts parameter.  That might be a bit high
in practice, but it seems odd to continue searching for smaller and
smaller paths until we exhaust the search space or
uninit-control-dep-attempts.

I'm testing this on x86_64-unknown-linux-gnu at the moment.

Any comments?

Thanks,
Richard.

	* params.opt (uninit-max-predicate-size): New.
	* doc/invoke.texi (--param uninit-max-predicate-size): Document.
	* gimple-predicate-analysis.h
	(predicate::init_from_control_deps): Adjust.
	* gimple-predicate-analysis.cc (MAX_NUM_CHAINS, MAX_CHAIN_LEN):
	Remove.
	(format_edge_vecs): Adjust.
	(simple_control_dep_chain): Do not limit.
	(compute_control_dep_chain): Adjust limiting to the overall
	predicate expression size _after_ adding an element to the
	vector of AND chains.
	(predicate::init_from_control_deps): Adjust.
	(uninit_analysis::init_use_preds): Likewise.
	(uninit_analysis::init_from_phi_def): Likewise.
---
 gcc/doc/invoke.texi              |   3 +
 gcc/gimple-predicate-analysis.cc | 113 ++++++++++++++++---------------
 gcc/gimple-predicate-analysis.h  |   2 +-
 gcc/params.opt                   |   4 ++
 4 files changed, 65 insertions(+), 57 deletions(-)

diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 9d662e35316..f7e791224dc 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -15537,6 +15537,9 @@ when comparing to the number of (scaled) blocks.
 Maximum number of nested calls to search for control dependencies
 during uninitialized variable analysis.
 
+@item uninit-max-predicate-size
+The maximum size of a predicate recorded during uninitialized variable analysis.
+
 @item fsm-scale-path-blocks
 Scale factor to apply to the number of blocks in a threading path
 when comparing to the number of (scaled) statements.
diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index 681047deee7..3b92bc5f505 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -47,10 +47,13 @@
 
 #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
+/* In our predicate normal form we have a vector of OR predicates
+   and in those a vector of (inverted) AND predicates.  Limit the
+   total amount of predicates to --param uninit-max-predicate-size
+   since we do O(n^2) operations on them.  Note we apply this limit
+   only after discovering the first sub-predicate, the whole
+   discovery process is limited by --param uninit-control-dep-attempts
+   which limits the computational work done during discovery.  */
 
 /* Return true if X1 is the negation of X2.  */
 
@@ -123,20 +126,19 @@ format_edge_vec (const vec<edge> &ev)
   return str;
 }
 
-/* Format the first N elements of the array of vector of edges EVA as
-   a string.  */
+/* Format the elements of the array of vector of edges EVA as a string.  */
 
 static std::string
-format_edge_vecs (const vec<edge> eva[], unsigned n)
+format_edge_vecs (const vec<vec<edge> > &eva)
 {
   std::string str;
 
-  for (unsigned i = 0; i != n; ++i)
+  for (unsigned i = 0; i != eva.length (); ++i)
     {
       str += '{';
       str += format_edge_vec (eva[i]);
       str += '}';
-      if (i + 1 < n)
+      if (i + 1 < eva.length ())
 	str += ", ";
     }
   return str;
@@ -921,8 +923,7 @@ simple_control_dep_chain (vec<edge>& chain, basic_block from, basic_block to)
     return;
 
   basic_block src = to;
-  while (src != from
-	 && chain.length () <= MAX_CHAIN_LEN)
+  while (src != from)
     {
       basic_block dest = src;
       src = get_immediate_dominator (CDI_DOMINATORS, src);
@@ -994,7 +995,7 @@ dfs_mark_dominating_region (edge exit, basic_block dom, int flag,
 
 static bool
 compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
-			   vec<edge> cd_chains[], unsigned *num_chains,
+			   vec<vec<edge> > &cd_chains, unsigned *chains_size,
 			   vec<edge> &cur_cd_chain, unsigned *num_calls,
 			   unsigned in_region = 0, unsigned depth = 0)
 {
@@ -1004,25 +1005,12 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
 
   /* 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);
-    }
 
   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 ());
+	     format_edge_vecs (cd_chains).c_str ());
 
   bool found_cd_chain = false;
 
@@ -1056,10 +1044,13 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
 	  if (cd_bb == dep_bb)
 	    {
 	      /* Found a direct control dependence.  */
-	      if (*num_chains < MAX_NUM_CHAINS)
+	      cd_chains.safe_push (cur_cd_chain.copy ());
+	      *chains_size += cur_cd_chain.length ();
+	      if (*chains_size >= param_uninit_max_predicate_size)
 		{
-		  cd_chains[*num_chains] = cur_cd_chain.copy ();
-		  (*num_chains)++;
+		  if (dump_file)
+		    fprintf (dump_file, "--param uninit-max-predicate-size "
+			     "reached: %u\n", cur_chain_len);
 		}
 	      found_cd_chain = true;
 	      /* Check path from next edge.  */
@@ -1084,12 +1075,15 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
 	  /* Check if DEP_BB is indirectly control-dependent on DOM_BB.  */
 	  if (!single_succ_p (cd_bb)
 	      && compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
-					    num_chains, cur_cd_chain,
+					    chains_size, cur_cd_chain,
 					    num_calls, in_region, depth + 1))
 	    {
 	      found_cd_chain = true;
 	      break;
 	    }
+	  /* Quickly terminate the walk.  */
+	  if (*chains_size >= param_uninit_max_predicate_size)
+	    break;
 
 	  /* The post-dominator walk will reach a backedge only
 	     from a forwarder, otherwise it should choose to exit
@@ -1103,6 +1097,10 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
 	}
       cur_cd_chain.pop ();
       gcc_assert (cur_cd_chain.length () == cur_chain_len);
+
+      /* Quickly terminate the walk.  */
+      if (*chains_size >= param_uninit_max_predicate_size)
+	break;
     }
 
   gcc_assert (cur_cd_chain.length () == cur_chain_len);
@@ -1111,13 +1109,13 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
 
 static bool
 compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
-			   vec<edge> cd_chains[], unsigned *num_chains,
-			   unsigned in_region = 0)
+			   vec<vec<edge> > &cd_chains, unsigned in_region = 0)
 {
-  auto_vec<edge, MAX_CHAIN_LEN + 1> cur_cd_chain;
+  auto_vec<edge, 10> cur_cd_chain;
   unsigned num_calls = 0;
+  unsigned chains_size = 0;
   unsigned depth = 0;
-  return compute_control_dep_chain (dom_bb, dep_bb, cd_chains, num_chains,
+  return compute_control_dep_chain (dom_bb, dep_bb, cd_chains, &chains_size,
 				    cur_cd_chain, &num_calls, in_region, depth);
 }
 
@@ -1655,7 +1653,7 @@ predicate::normalize (gimple *use_or_def, bool is_use)
 
 /* 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
+   is an array of 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
@@ -1663,18 +1661,19 @@ predicate::normalize (gimple *use_or_def, bool is_use)
    pred_info.  Sets M_PREDS to the resulting composite predicates.  */
 
 void
-predicate::init_from_control_deps (const vec<edge> *dep_chains,
-				   unsigned num_chains, bool is_use)
+predicate::init_from_control_deps (const vec<vec<edge> > &dep_chains,
+				   bool is_use)
 {
   gcc_assert (is_empty ());
 
+  unsigned num_chains = dep_chains.length ();
   if (num_chains == 0)
     return;
 
   if (DEBUG_PREDICATE_ANALYZER && dump_file)
     fprintf (dump_file, "init_from_control_deps [%s] {%s}:\n",
 	     is_use ? "USE" : "DEF",
-	     format_edge_vecs (dep_chains, num_chains).c_str ());
+	     format_edge_vecs (dep_chains).c_str ());
 
   /* Convert the control dependency chain into a set of predicates.  */
   m_preds.reserve (num_chains);
@@ -1768,9 +1767,8 @@ predicate::init_from_control_deps (const vec<edge> *dep_chains,
 	      else
 		{
 		  /* Support a case label with a range with
-		     two predicates.  We're overcommitting on
-		     the MAX_CHAIN_LEN budget by at most a factor
-		     of two here.  */
+		     two predicates.  This at most doubles the
+		     number of predicates.  */
 		  pred_info one_pred;
 		  one_pred.pred_lhs = gimple_switch_index (gs);
 		  one_pred.pred_rhs = CASE_LOW (l);
@@ -1916,14 +1914,13 @@ uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_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_chains = 0;
-  auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
+  auto_vec<vec<edge>, 8> dep_chains;
 
-  if (!compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains))
+  if (!compute_control_dep_chain (cd_root, use_bb, dep_chains))
     {
-      gcc_assert (num_chains == 0);
+      gcc_assert (dep_chains.length () == 0);
+      dep_chains.safe_push (vNULL);
       simple_control_dep_chain (dep_chains[0], cd_root, use_bb);
-      num_chains++;
     }
 
   if (DEBUG_PREDICATE_ANALYZER && dump_file)
@@ -1934,7 +1931,11 @@ uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb,
      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.  */
-  use_preds.init_from_control_deps (dep_chains, num_chains, true);
+  use_preds.init_from_control_deps (dep_chains, true);
+
+  for (auto v : dep_chains)
+    v.release ();
+
   return !use_preds.is_empty ();
 }
 
@@ -2015,21 +2016,19 @@ uninit_analysis::init_from_phi_def (gphi *phi)
     if (!dfs_mark_dominating_region (def_edges[i], cd_root, in_region, region))
       break;
 
-  unsigned num_chains = 0;
-  auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
+  auto_vec<vec<edge>, 8> dep_chains;
   for (unsigned i = 0; i < nedges; i++)
     {
       edge e = def_edges[i];
-      unsigned prev_nc = num_chains;
-      compute_control_dep_chain (cd_root, e->src, dep_chains,
-				 &num_chains, in_region);
+      unsigned prev_nc = dep_chains.length ();
+      compute_control_dep_chain (cd_root, e->src, dep_chains, in_region);
 
       /* 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++)
+	  if (prev_nc == dep_chains.length ())
+	    dep_chains.safe_push (vNULL);
+	  for (unsigned j = prev_nc; j < dep_chains.length (); j++)
 	    dep_chains[j].safe_push (e);
 	}
     }
@@ -2041,7 +2040,9 @@ uninit_analysis::init_from_phi_def (gphi *phi)
   /* Convert control dependence chains to the predicate in *THIS under
      which the PHI operands are defined to values for which M_EVAL is
      false.  */
-  m_phi_def_preds.init_from_control_deps (dep_chains, num_chains, false);
+  m_phi_def_preds.init_from_control_deps (dep_chains, false);
+  for (auto v : dep_chains)
+    v.release ();
   return !m_phi_def_preds.is_empty ();
 }
 
diff --git a/gcc/gimple-predicate-analysis.h b/gcc/gimple-predicate-analysis.h
index 972af5e0b2d..6474eaf3afb 100644
--- a/gcc/gimple-predicate-analysis.h
+++ b/gcc/gimple-predicate-analysis.h
@@ -65,7 +65,7 @@ class predicate
     return m_preds;
   }
 
-  void init_from_control_deps (const vec<edge> *, unsigned, bool);
+  void init_from_control_deps (const vec<vec<edge> >&, bool);
 
   void dump (FILE *) const;
   void dump (FILE *, gimple *, const char *) const;
diff --git a/gcc/params.opt b/gcc/params.opt
index 3001566e641..e8e264dcb45 100644
--- a/gcc/params.opt
+++ b/gcc/params.opt
@@ -1097,6 +1097,10 @@ Emit instrumentation calls to __tsan_func_entry() and __tsan_func_exit().
 Common Joined UInteger Var(param_uninit_control_dep_attempts) Init(1000) IntegerRange(1, 65536) Param Optimization
 Maximum number of nested calls to search for control dependencies during uninitialized variable analysis.
 
+-param=uninit-max-predicate-size=
+Common Joined UInteger Var(param_uninit_max_predicate_size) Init(40) IntegerRange(1, 65536) Param Optimization
+Maximum size of a predicate recorded during uninitialized variable analysis.
+
 -param=uninlined-function-insns=
 Common Joined UInteger Var(param_uninlined_function_insns) Init(2) Optimization IntegerRange(0, 1000000) Param
 Instruction accounted for function prologue, epilogue and other overhead.
-- 
2.35.3

Re: [PATCH][RFC] Unify MAX_NUM_CHAINS and MAX_CHAIN_LEN to --param uninit-max-predicate-size

[Jeff Law]

On 9/5/22 07:25, Richard Biener via Gcc-patches wrote:
> The following exposes the MAX_NUM_CHAINS and MAX_CHAIN_LEN to the user
> by adding a --param uninit-max-predicate-size and re-doing the
> limits on the whole predicate expression size rather than limiting
> the number of OR and AND elements separately.  The following goes
> a step further and for a single AND chain allows an arbitrary size,
> limiting that only with the computational --param
> uninit-control-dep-attempts parameter.  That might be a bit high
> in practice, but it seems odd to continue searching for smaller and
> smaller paths until we exhaust the search space or
> uninit-control-dep-attempts.
>
> I'm testing this on x86_64-unknown-linux-gnu at the moment.
>
> Any comments?
>
> Thanks,
> Richard.
>
> 	* params.opt (uninit-max-predicate-size): New.
> 	* doc/invoke.texi (--param uninit-max-predicate-size): Document.
> 	* gimple-predicate-analysis.h
> 	(predicate::init_from_control_deps): Adjust.
> 	* gimple-predicate-analysis.cc (MAX_NUM_CHAINS, MAX_CHAIN_LEN):
> 	Remove.
> 	(format_edge_vecs): Adjust.
> 	(simple_control_dep_chain): Do not limit.
> 	(compute_control_dep_chain): Adjust limiting to the overall
> 	predicate expression size _after_ adding an element to the
> 	vector of AND chains.
> 	(predicate::init_from_control_deps): Adjust.
> 	(uninit_analysis::init_use_preds): Likewise.
> 	(uninit_analysis::init_from_phi_def): Likewise.

I think we probably have too many knobs already, though magic numbers 
are even worse.  I suspect we (gcc develoeprs) will be the biggest user 
of this if we go forward.  Essentially given a testcase we can crank up 
the limits to see if the test is hitting limits or exposing a deeper 
problem.

So based on removal of the magic #s, it looks good to me.


jeff