[PATCH] Improve compute_control_dep_chain path finding

[PATCH] Improve compute_control_dep_chain path finding

[Richard Biener]

This improves the compute_control_dep_chain path finding by first
marking the dominating region we search and then making sure to
not walk outside if it when enumerating all paths from the dominating
block to the interesting PHI edge source.  I have limited the DFS
walk done for the marking in similar ways as we limit the walking
in compute_control_dep_chain, more careful limiting might be
necessary though - the --param uninit-control-dep-attempts param
I re-use has a rather high default of 1000 which we might be able
to reduce with this patch as well (I think we'll usually hit some of the
other limits before ever reaching this).

Bootstrap & regtest running on x86_64-unknown-linux-gnu.

The true benefit will only be there when we can combine the
multiple compute_control_dep_chain done from
uninit_analysis::init_from_phi_def, but I've not yet managed to
make that work.  I guess I have to fully understand
compute_control_dep_chain first ...

	* gimple-predicate-analysis.cc (dfs_mark_dominating_region):
	New helper.
	(compute_control_dep_chain): Adjust to honor marked region
	if provided.
	(uninit_analysis::init_from_phi_def): Pre-mark the dominating
	region to improve compute_control_dep_chain walking.
	* vec.h (vec<T, va_heap, vl_ptr>::allocated): Add forwarder.
---
 gcc/gimple-predicate-analysis.cc | 81 ++++++++++++++++++++++++++++++--
 gcc/vec.h                        |  3 ++
 2 files changed, 81 insertions(+), 3 deletions(-)

diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index 0d973a9e25a..e395c1b7052 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -1078,6 +1078,54 @@ simple_control_dep_chain (vec<edge>& chain, basic_block from, edge to)
   simple_control_dep_chain (chain, from, to->src);
 }
 
+/* Perform a DFS walk on predecessor edges to mark the region denoted
+   by the EXIT edge and DOM which dominates EXIT->src, including DOM.
+   Blocks in the region are marked with FLAG and added to BBS.  BBS is
+   filled up to its capacity only after which the walk is terminated
+   and false is returned.  If the whole region was marked, true is returned.  */
+
+static bool
+dfs_mark_dominating_region (edge exit, basic_block dom, int flag,
+			    vec<basic_block> &bbs)
+{
+  if (exit->src == dom || exit->src->flags & flag)
+    return true;
+  if (!bbs.space (1))
+    return false;
+  bbs.quick_push (exit->src);
+  exit->src->flags |= flag;
+  auto_vec<edge_iterator, 20> stack (bbs.allocated () - bbs.length () + 1);
+  stack.quick_push (ei_start (exit->src->preds));
+  while (!stack.is_empty ())
+    {
+      /* Look at the edge on the top of the stack.  */
+      edge_iterator ei = stack.last ();
+      basic_block src = ei_edge (ei)->src;
+
+      /* Check if the edge source has been visited yet.  */
+      if (!(src->flags & flag))
+	{
+	  /* Mark the source if there's still space.  If not, return early.  */
+	  if (!bbs.space (1))
+	    return false;
+	  src->flags |= flag;
+	  bbs.quick_push (src);
+
+	  /* Queue its predecessors if we didn't reach DOM.  */
+	  if (src != dom && EDGE_COUNT (src->preds) > 0)
+	    stack.quick_push (ei_start (src->preds));
+	}
+      else
+	{
+	  if (!ei_one_before_end_p (ei))
+	    ei_next (&stack.last ());
+	  else
+	    stack.pop ();
+	}
+    }
+  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),
@@ -1093,7 +1141,7 @@ 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)
+			   unsigned in_region = 0, unsigned depth = 0)
 {
   if (*num_calls > (unsigned)param_uninit_control_dep_attempts)
     {
@@ -1167,10 +1215,14 @@ compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
 	      break;
 	    }
 
+	  /* If the dominating region has been marked avoid walking outside.  */
+	  if (in_region != 0 && !(cd_bb->flags & in_region))
+	    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))
+					 num_calls, in_region, depth + 1))
 	    {
 	      found_cd_chain = true;
 	      break;
@@ -2238,6 +2290,25 @@ uninit_analysis::init_from_phi_def (gphi *phi)
   if (nedges == 0)
     return false;
 
+  auto_bb_flag in_region (cfun);
+  auto_vec<basic_block, 20> region (MIN (n_basic_blocks_for_fn (cfun),
+					 param_uninit_control_dep_attempts));
+  /* Pre-mark the PHI incoming edges PHI block to make sure we only walk
+     interesting edges from there.  */
+  for (unsigned i = 0; i < nedges; i++)
+    {
+      if (!(def_edges[i]->dest->flags & in_region))
+	{
+	  if (!region.space (1))
+	    break;
+	  def_edges[i]->dest->flags |= in_region;
+	  region.quick_push (def_edges[i]->dest);
+	}
+    }
+  for (unsigned i = 0; i < nedges; i++)
+    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<edge, MAX_CHAIN_LEN + 1> cur_chain;
@@ -2247,7 +2318,7 @@ uninit_analysis::init_from_phi_def (gphi *phi)
       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);
+				 &num_chains, cur_chain, &num_calls, in_region);
 
       /* Update the newly added chains with the phi operand edge.  */
       if (EDGE_COUNT (e->src->succs) > 1)
@@ -2259,6 +2330,10 @@ uninit_analysis::init_from_phi_def (gphi *phi)
 	}
     }
 
+  /* Unmark the region.  */
+  for (auto bb : region)
+    bb->flags &= ~in_region;
+
   /* Convert control dependence chains to the predicate in *THIS under
      which the PHI operands are defined to values for which M_EVAL is
      false.  */
diff --git a/gcc/vec.h b/gcc/vec.h
index eed075addc9..d048fa54ce8 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -1469,6 +1469,9 @@ public:
   bool is_empty (void) const
   { return m_vec ? m_vec->is_empty () : true; }
 
+  unsigned allocated (void) const
+  { return m_vec ? m_vec->allocated () : 0; }
+
   unsigned length (void) const
   { return m_vec ? m_vec->length () : 0; }
 
-- 
2.35.3