* cfgloopmanip.c (remove_path, loopify, duplicate_loop_to_header_edge):

	Change dom_bbs to vector.  Add argument to iterate_fix_dominators call.
	* loop-unroll.c (unroll_loop_runtime_iterations): Ditto.
	* tree-cfg.c (tree_duplicate_sese_region): Change doms to vector.
	Add argument to iterate_fix_dominators call.
	(remove_edge_and_dominated_blocks): Pass vector to bbs_to_fix_dom.
	* gcse.c (hoist_code): Change domby to vector.
	* cfghooks.c (make_forwarder_block): Change doms_to_fix to vector.
	Add argument to iterate_fix_dominators call.
	* loop-doloop.c (doloop_modify): Changed recount_dominator to
	recompute_dominator.
	* lambda-code.c (perfect_nestify): Ditto.
	* cfgloopanal.c: Include graphds.h.
	(struct edge, struct vertex, struct graph, dump_graph, new_graph,
	add_edge, dfs, for_each_edge, free_graph): Moved to graphds.c.
	(mark_irreducible_loops): Use graphds_scc.  Remove argument from
	add_edge call.
	* graphds.c: New file.
	* graphds.h: New file.
	* dominance.c: Include vecprim.h, pointer-set.h and graphds.h.
	(get_dominated_by, get_dominated_by_region): Change return type to
	vector.
	(verify_dominators): Recompute all dominators and compare the results.
	(recount_dominator): Renamed to ...
	(recompute_dominator): ... this.  Do not check that the block is
	dominated by entry.
	(iterate_fix_dominators): Reimplemented.
	(prune_bbs_to_update_dominators, root_of_dom_tree,
	determine_dominators_for_sons): New functions.
	* et-forest.c (et_root): New function.
	* et-forest.h (et_root): Declare.
	* Makefile.in (graphds.o): Add.
	(cfgloopanal.o): Add graphds.h dependency.
	(dominance.o): Add graphds.h, vecprim.h and pointer-set.h dependency.
	* basic-block.h (get_dominated_by, get_dominated_by_region,
	iterate_fix_dominators): Declaration changed.
	(recount_dominator): Renamed to ...
	(recompute_dominator): ... this.
	* tree-ssa-threadupdate.c (thread_block): Free dominance info.
	(thread_through_all_blocks): Do not free dominance info.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@125297 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 347 insertions, 70 deletions

diff --git a/gcc/dominance.c b/gcc/dominance.c
index a9af9d52d15..57a9df6baa4 100644
--- a/gcc/dominance.c
+++ b/gcc/dominance.c
@@ -44,6 +44,9 @@
 #include "toplev.h"
 #include "et-forest.h"
 #include "timevar.h"
+#include "vecprim.h"
+#include "pointer-set.h"
+#include "graphds.h"
 
 /* Whether the dominators and the postdominators are available.  */
 static enum dom_state dom_computed[2];
@@ -735,45 +738,39 @@ set_immediate_dominator (enum cdi_direction dir, basic_block bb,
     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
 }
 
-/* Store all basic blocks immediately dominated by BB into BBS and return
-   their number.  */
-int
-get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs)
+/* Returns the list of basic blocks immediately dominated by BB, in the
+   direction DIR.  */
+VEC (basic_block, heap) *
+get_dominated_by (enum cdi_direction dir, basic_block bb)
 {
-  unsigned int dir_index = dom_convert_dir_to_idx (dir);
   int n;
+  unsigned int dir_index = dom_convert_dir_to_idx (dir);
   struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
- 
+  VEC (basic_block, heap) *bbs = NULL;
+
   gcc_assert (dom_computed[dir_index]);
 
   if (!son)
-    {
-      *bbs = NULL;
-      return 0;
-    }
-
-  for (ason = son->right, n = 1; ason != son; ason = ason->right)
-    n++;
+    return NULL;
 
-  *bbs = XNEWVEC (basic_block, n);
-  (*bbs)[0] = son->data;
+  VEC_safe_push (basic_block, heap, bbs, son->data);
   for (ason = son->right, n = 1; ason != son; ason = ason->right)
-    (*bbs)[n++] = ason->data;
+    VEC_safe_push (basic_block, heap, bbs, ason->data);
 
-  return n;
+  return bbs;
 }
 
-/* Find all basic blocks that are immediately dominated (in direction DIR)
-   by some block between N_REGION ones stored in REGION, except for blocks
-   in the REGION itself.  The found blocks are stored to DOMS and their number
-   is returned.  */
-
-unsigned
+/* Returns the list of basic blocks that are immediately dominated (in
+   direction DIR) by some block between N_REGION ones stored in REGION,
+   except for blocks in the REGION itself.  */
+  
+VEC (basic_block, heap) *
 get_dominated_by_region (enum cdi_direction dir, basic_block *region,
-			 unsigned n_region, basic_block *doms)
+			 unsigned n_region)
 {
-  unsigned n_doms = 0, i;
+  unsigned i;
   basic_block dom;
+  VEC (basic_block, heap) *doms = NULL;
 
   for (i = 0; i < n_region; i++)
     region[i]->flags |= BB_DUPLICATED;
@@ -782,11 +779,11 @@ get_dominated_by_region (enum cdi_direction dir, basic_block *region,
 	 dom;
 	 dom = next_dom_son (dir, dom))
       if (!(dom->flags & BB_DUPLICATED))
-	doms[n_doms++] = dom;
+	VEC_safe_push (basic_block, heap, doms, dom);
   for (i = 0; i < n_region; i++)
     region[i]->flags &= ~BB_DUPLICATED;
 
-  return n_doms;
+  return doms;
 }
 
 /* Redirect all edges pointing to BB to TO.  */
@@ -973,40 +970,37 @@ void
 verify_dominators (enum cdi_direction dir)
 {
   int err = 0;
-  basic_block bb;
+  basic_block *old_dom = XNEWVEC (basic_block, last_basic_block);
+  basic_block bb, imm_bb;
 
   gcc_assert (dom_info_available_p (dir));
 
   FOR_EACH_BB (bb)
     {
-      basic_block dom_bb;
-      basic_block imm_bb;
+      old_dom[bb->index] = get_immediate_dominator (dir, bb);
 
-      dom_bb = recount_dominator (dir, bb);
-      imm_bb = get_immediate_dominator (dir, bb);
-      if (dom_bb != imm_bb)
+      if (!old_dom[bb->index])
 	{
-	  if ((dom_bb == NULL) || (imm_bb == NULL))
-	    error ("dominator of %d status unknown", bb->index);
-	  else
-	    error ("dominator of %d should be %d, not %d",
-		   bb->index, dom_bb->index, imm_bb->index);
+	  error ("dominator of %d status unknown", bb->index);
 	  err = 1;
 	}
     }
 
-  if (dir == CDI_DOMINATORS)
+  free_dominance_info (dir);
+  calculate_dominance_info (dir);
+
+  FOR_EACH_BB (bb)
     {
-      FOR_EACH_BB (bb)
+      imm_bb = get_immediate_dominator (dir, bb);
+      if (old_dom[bb->index] != imm_bb)
 	{
-	  if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR))
-	    {
-	      error ("ENTRY does not dominate bb %d", bb->index);
-	      err = 1;
-	    }
+	  error ("dominator of %d should be %d, not %d",
+		 bb->index, imm_bb->index, old_dom[bb->index]->index);
+	  err = 1;
 	}
     }
 
+  free (old_dom);
   gcc_assert (!err);
 }
 
@@ -1016,7 +1010,7 @@ verify_dominators (enum cdi_direction dir)
    reaches a fixed point.  */
 
 basic_block
-recount_dominator (enum cdi_direction dir, basic_block bb)
+recompute_dominator (enum cdi_direction dir, basic_block bb)
 {
   unsigned int dir_index = dom_convert_dir_to_idx (dir);
   basic_block dom_bb = NULL;
@@ -1029,11 +1023,6 @@ recount_dominator (enum cdi_direction dir, basic_block bb)
     {
       FOR_EACH_EDGE (e, ei, bb->preds)
 	{
-	  /* Ignore the predecessors that either are not reachable from
-	     the entry block, or whose dominator was not determined yet.  */
-	  if (!dominated_by_p (dir, e->src, ENTRY_BLOCK_PTR))
-	    continue;
-
 	  if (!dominated_by_p (dir, e->src, bb))
 	    dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
 	}
@@ -1050,37 +1039,325 @@ recount_dominator (enum cdi_direction dir, basic_block bb)
   return dom_bb;
 }
 
-/* Iteratively recount dominators of BBS. The change is supposed to be local
-   and not to grow further.  */
+/* Use simple heuristics (see iterate_fix_dominators) to determine dominators
+   of BBS.  We assume that all the immediate dominators except for those of the
+   blocks in BBS are correct.  If CONSERVATIVE is true, we also assume that the
+   currently recorded immediate dominators of blocks in BBS really dominate the
+   blocks.  The basic blocks for that we determine the dominator are removed
+   from BBS.  */
+
+static void
+prune_bbs_to_update_dominators (VEC (basic_block, heap) *bbs,
+				bool conservative)
+{
+  unsigned i;
+  bool single;
+  basic_block bb, dom = NULL;
+  edge_iterator ei;
+  edge e;
+
+  for (i = 0; VEC_iterate (basic_block, bbs, i, bb);)
+    {
+      if (bb == ENTRY_BLOCK_PTR)
+	goto succeed;
+
+      if (single_pred_p (bb))
+	{
+	  set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
+	  goto succeed;
+	}
+
+      if (!conservative)
+	goto fail;
+
+      single = true;
+      dom = NULL;
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	{
+	  if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
+	    continue;
+
+	  if (!dom)
+	    dom = e->src;
+	  else
+	    {
+	      single = false;
+	      dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
+	    }
+	}
+
+      gcc_assert (dom != NULL);
+      if (single
+	  || find_edge (dom, bb))
+	{
+	  set_immediate_dominator (CDI_DOMINATORS, bb, dom);
+	  goto succeed;
+	}
+
+fail:
+      i++;
+      continue;
+
+succeed:
+      VEC_unordered_remove (basic_block, bbs, i);
+    }
+}
+
+/* Returns root of the dominance tree in the direction DIR that contains
+   BB.  */
+
+static basic_block
+root_of_dom_tree (enum cdi_direction dir, basic_block bb)
+{
+  return et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
+}
+
+/* See the comment in iterate_fix_dominators.  Finds the immediate dominators
+   for the sons of Y, found using the SON and BROTHER arrays representing
+   the dominance tree of graph G.  BBS maps the vertices of G to the basic
+   blocks.  */
+
+static void
+determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs,
+			       int y, int *son, int *brother)
+{
+  bitmap gprime;
+  int i, a, nc;
+  VEC (int, heap) **sccs;
+  basic_block bb, dom, ybb;
+  unsigned si;
+  edge e;
+  edge_iterator ei;
+
+  if (son[y] == -1)
+    return;
+  if (y == (int) VEC_length (basic_block, bbs))
+    ybb = ENTRY_BLOCK_PTR;
+  else
+    ybb = VEC_index (basic_block, bbs, y);
+
+  if (brother[son[y]] == -1)
+    {
+      /* Handle the common case Y has just one son specially.  */
+      bb = VEC_index (basic_block, bbs, son[y]);
+      set_immediate_dominator (CDI_DOMINATORS, bb,
+			       recompute_dominator (CDI_DOMINATORS, bb));
+      identify_vertices (g, y, son[y]);
+      return;
+    }
+
+  gprime = BITMAP_ALLOC (NULL);
+  for (a = son[y]; a != -1; a = brother[a])
+    bitmap_set_bit (gprime, a);
+
+  nc = graphds_scc (g, gprime);
+  BITMAP_FREE (gprime);
+
+  sccs = XCNEWVEC (VEC (int, heap) *, nc);
+  for (a = son[y]; a != -1; a = brother[a])
+    VEC_safe_push (int, heap, sccs[g->vertices[a].component], a);
+
+  for (i = nc - 1; i >= 0; i--)
+    {
+      dom = NULL;
+      for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
+	{
+	  bb = VEC_index (basic_block, bbs, a);
+	  FOR_EACH_EDGE (e, ei, bb->preds)
+	    {
+	      if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
+		continue;
+
+	      dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
+	    }
+	}
+
+      gcc_assert (dom != NULL);
+      for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
+	{
+	  bb = VEC_index (basic_block, bbs, a);
+	  set_immediate_dominator (CDI_DOMINATORS, bb, dom);
+	}
+    }
+
+  for (i = 0; i < nc; i++)
+    VEC_free (int, heap, sccs[i]);
+  free (sccs);
+
+  for (a = son[y]; a != -1; a = brother[a])
+    identify_vertices (g, y, a);
+}
+
+/* Recompute dominance information for basic blocks in the set BBS.  The
+   function assumes that the immediate dominators of all the other blocks
+   in CFG are correct, and that there are no unreachable blocks.
+
+   If CONSERVATIVE is true, we additionally assume that all the ancestors of
+   a block of BBS in the current dominance tree dominate it.  */
+
 void
-iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n)
+iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
+			bool conservative)
 {
+  unsigned i;
+  basic_block bb, dom;
+  struct graph *g;
+  int n, y;
+  size_t dom_i;
+  edge e;
+  edge_iterator ei;
+  struct pointer_map_t *map;
+  int *parent, *son, *brother;
   unsigned int dir_index = dom_convert_dir_to_idx (dir);
-  int i, changed = 1;
-  basic_block old_dom, new_dom;
 
+  /* We only support updating dominators.  There are some problems with
+     updating postdominators (need to add fake edges from infinite loops
+     and noreturn functions), and since we do not currently use
+     iterate_fix_dominators for postdominators, any attempt to handle these
+     problems would be unused, untested, and almost surely buggy.  We keep
+     the DIR argument for consistency with the rest of the dominator analysis
+     interface.  */
+  gcc_assert (dir == CDI_DOMINATORS);
   gcc_assert (dom_computed[dir_index]);
 
-  for (i = 0; i < n; i++)
-    set_immediate_dominator (dir, bbs[i], NULL);
+  /* The algorithm we use takes inspiration from the following papers, although
+     the details are quite different from any of them:
+
+     [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
+	 Dominator Tree of a Reducible Flowgraph
+     [2]  V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
+	  dominator trees
+     [3]  K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
+	  Algorithm
+
+     First, we use the following heuristics to decrease the size of the BBS
+     set:
+       a) if BB has a single predecessor, then its immediate dominator is this
+	  predecessor
+       additionally, if CONSERVATIVE is true:
+       b) if all the predecessors of BB except for one (X) are dominated by BB,
+	  then X is the immediate dominator of BB
+       c) if the nearest common ancestor of the predecessors of BB is X and
+	  X -> BB is an edge in CFG, then X is the immediate dominator of BB
+
+     Then, we need to establish the dominance relation among the basic blocks
+     in BBS.  We split the dominance tree by removing the immediate dominator
+     edges from BBS, creating a forrest F.  We form a graph G whose vertices
+     are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
+     X' -> Y in CFG such that X' belongs to the tree of the dominance forrest
+     whose root is X.  We then determine dominance tree of G.  Note that
+     for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
+     In this step, we can use arbitrary algorithm to determine dominators.
+     We decided to prefer the algorithm [3] to the algorithm of
+     Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
+     10 during gcc bootstrap), and [3] should perform better in this case.
+
+     Finally, we need to determine the immediate dominators for the basic
+     blocks of BBS.  If the immediate dominator of X in G is Y, then
+     the immediate dominator of X in CFG belongs to the tree of F rooted in
+     Y.  We process the dominator tree T of G recursively, starting from leaves.
+     Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
+     subtrees of the dominance tree of CFG rooted in X_i are already correct.
+     Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}.  We make
+     the following observations:
+       (i) the immediate dominator of all blocks in a strongly connected
+	   component of G' is the same
+       (ii) if X has no predecessors in G', then the immediate dominator of X
+	    is the nearest common ancestor of the predecessors of X in the
+	    subtree of F rooted in Y
+     Therefore, it suffices to find the topological ordering of G', and
+     process the nodes X_i in this order using the rules (i) and (ii).
+     Then, we contract all the nodes X_i with Y in G, so that the further
+     steps work correctly.  */
+
+  if (!conservative)
+    {
+      /* Split the tree now.  If the idoms of blocks in BBS are not
+	 conservatively correct, setting the dominators using the
+	 heuristics in prune_bbs_to_update_dominators could
+	 create cycles in the dominance "tree", and cause ICE.  */
+      for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+	set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
+    }
+
+  prune_bbs_to_update_dominators (bbs, conservative);
+  n = VEC_length (basic_block, bbs);
+
+  if (n == 0)
+    return;
 
-  while (changed)
+  if (n == 1)
     {
-      changed = 0;
-      for (i = 0; i < n; i++)
+      bb = VEC_index (basic_block, bbs, 0);
+      set_immediate_dominator (CDI_DOMINATORS, bb,
+			       recompute_dominator (CDI_DOMINATORS, bb));
+      return;
+    }
+
+  /* Construct the graph G.  */
+  map = pointer_map_create ();
+  for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+    {
+      /* If the dominance tree is conservatively correct, split it now.  */
+      if (conservative)
+	set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
+      *pointer_map_insert (map, bb) = (void *) (size_t) i;
+    }
+  *pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n;
+
+  g = new_graph (n + 1);
+  for (y = 0; y < g->n_vertices; y++)
+    g->vertices[y].data = BITMAP_ALLOC (NULL);
+  for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+    {
+      FOR_EACH_EDGE (e, ei, bb->preds)
 	{
-	  old_dom = get_immediate_dominator (dir, bbs[i]);
-	  new_dom = recount_dominator (dir, bbs[i]);
-	  if (old_dom != new_dom)
-	    {
-	      changed = 1;
-	      set_immediate_dominator (dir, bbs[i], new_dom);
-	    }
+	  dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
+	  if (dom == bb)
+	    continue;
+
+	  dom_i = (size_t) *pointer_map_contains (map, dom);
+
+	  /* Do not include parallel edges to G.  */
+	  if (bitmap_bit_p (g->vertices[dom_i].data, i))
+	    continue;
+
+	  bitmap_set_bit (g->vertices[dom_i].data, i);
+	  add_edge (g, dom_i, i);
 	}
     }
+  for (y = 0; y < g->n_vertices; y++)
+    BITMAP_FREE (g->vertices[y].data);
+  pointer_map_destroy (map);
+
+  /* Find the dominator tree of G.  */
+  son = XNEWVEC (int, n + 1);
+  brother = XNEWVEC (int, n + 1);
+  parent = XNEWVEC (int, n + 1);
+  graphds_domtree (g, n, parent, son, brother);
+
+  /* Finally, traverse the tree and find the immediate dominators.  */
+  for (y = n; son[y] != -1; y = son[y])
+    continue;
+  while (y != -1)
+    {
+      determine_dominators_for_sons (g, bbs, y, son, brother);
+
+      if (brother[y] != -1)
+	{
+	  y = brother[y];
+	  while (son[y] != -1)
+	    y = son[y];
+	}
+      else
+	y = parent[y];
+    }
+
+  free (son);
+  free (brother);
+  free (parent);
 
-  for (i = 0; i < n; i++)
-    gcc_assert (get_immediate_dominator (dir, bbs[i]));
+  free_graph (g);
 }
 
 void