[PATCH]: Speed up dominance frontiers computation

[Daniel Berlin <dberlin at dberlin dot org>]

The attached patch replaces the dominance frontier algorithm with one
that 
1. Is faster in all cases
2. Is simpler, smaller, and more intuitive
3. Is non-recursive

The old algorithm used to walk blocks that weren't going to end up in
the dominance frontier of any block (IE it was the O(sum of the size of
the dominance frontiers), and grew with the size of the dominance
frontiers, and the size of the CFG).

The new algorithm grows only with the size of the CFG.  The inner loop
only touches blocks that will be in the dominance frontier of some
block, rather than blocks that *could* be in the dominance frontier of
some block.

It is roughly 30% faster in all cases, and moreso on large testcases
where dominance frontier computation was taking any significant amount
of time (via into-ssa).  It is also a win when you are compiling large
numbers of functions with small numbers of basic blocks, since it
doesn't do as much work in these cases as the old one, either.

Bootstrapped and regtested on i686-pc-linux-gnu and powerpc-darwin.

I also bootstrapped and regtested on these two platforms by running both
the old algorithm and the new algorithm, and verifying the resulting
frontiers matched exactly.

Okay for mainline?



2005-01-17  Daniel Berlin  <dberlin@dberlin.org>

	* cfganal.c (compute_dominance_frontiers_1): Replace with new algorithm
	(compute_dominance_frontiers): Ditto.
Index: cfganal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfganal.c,v
retrieving revision 1.47.2.6
diff -u -p -r1.47.2.6 cfganal.c
--- cfganal.c	23 Nov 2004 00:11:15 -0000	1.47.2.6
+++ cfganal.c	14 Jan 2005 20:19:13 -0000
@@ -933,80 +933,62 @@ dfs_enumerate_from (basic_block bb, int 
 }
 
 
-/* Computing the Dominance Frontier:
+/* Compute dominance frontiers, ala Harvey.
+   
+   First, we identify each join point, j (any node with more than one
+   incoming edge is a join point). 
+
+   We then examine each predecessor, p, of j and walk up the dominator tree
+   starting at p. 
+   
+   We stop the walk when we reach j's immediate dominator - j is in the
+   dominance frontier of each of  the nodes in the walk, except for j's
+   immediate dominator. Intuitively, all of the rest of j's dominators are
+   shared by j's predecessors as well.
+   Since they dominate j, they will not have j in their dominance frontiers.
+
+   The number of nodes touched by this algorithm is equal to the size 
+   of the dominance frontiers, no more, no less.
+*/
 
-   As described in Morgan, section 3.5, this may be done simply by
-   walking the dominator tree bottom-up, computing the frontier for
-   the children before the parent.  When considering a block B,
-   there are two cases:
-
-   (1) A flow graph edge leaving B that does not lead to a child
-   of B in the dominator tree must be a block that is either equal
-   to B or not dominated by B.  Such blocks belong in the frontier
-   of B.
-
-   (2) Consider a block X in the frontier of one of the children C
-   of B.  If X is not equal to B and is not dominated by B, it
-   is in the frontier of B.  */
 
 static void
-compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done)
+compute_dominance_frontiers_1 (bitmap *frontiers)
 {
-  edge e;
+  edge p;
   edge_iterator ei;
-  basic_block c;
-
-  SET_BIT (done, bb->index);
-
-  /* Do the frontier of the children first.  Not all children in the
-     dominator tree (blocks dominated by this one) are children in the
-     CFG, so check all blocks.  */
-  for (c = first_dom_son (CDI_DOMINATORS, bb);
-       c;
-       c = next_dom_son (CDI_DOMINATORS, c))
-    {
-      if (! TEST_BIT (done, c->index))
-    	compute_dominance_frontiers_1 (frontiers, c, done);
-    }
-      
-  /* Find blocks conforming to rule (1) above.  */
-  FOR_EACH_EDGE (e, ei, bb->succs)
-    {
-      if (e->dest == EXIT_BLOCK_PTR)
-	continue;
-      if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb)
-	bitmap_set_bit (frontiers[bb->index], e->dest->index);
-    }
-
-  /* Find blocks conforming to rule (2).  */
-  for (c = first_dom_son (CDI_DOMINATORS, bb);
-       c;
-       c = next_dom_son (CDI_DOMINATORS, c))
+  basic_block b;
+  FOR_EACH_BB (b)
     {
-      unsigned x;
-      bitmap_iterator bi;
-
-      EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x, bi)
+      if (EDGE_COUNT (b->preds) >= 2)
 	{
-	  if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb)
-	    bitmap_set_bit (frontiers[bb->index], x);
+	  FOR_EACH_EDGE (p, ei, b->preds)
+	    {
+	      basic_block runner = p->src;
+	      basic_block domsb;
+	      if (runner == ENTRY_BLOCK_PTR)
+		continue;
+	      
+	      domsb = get_immediate_dominator (CDI_DOMINATORS, b);
+	      while (runner != domsb)
+		{
+		  bitmap_set_bit (frontiers[runner->index], 
+				  b->index);
+		  runner = get_immediate_dominator (CDI_DOMINATORS,
+						    runner);
+		}
+	    }
 	}
     }
-}
-
+}	      
+  
 
 void
 compute_dominance_frontiers (bitmap *frontiers)
 {
-  sbitmap done = sbitmap_alloc (last_basic_block);
-
   timevar_push (TV_DOM_FRONTIERS);
 
-  sbitmap_zero (done);
-
-  compute_dominance_frontiers_1 (frontiers, EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest, done);
-
-  sbitmap_free (done);
+  compute_dominance_frontiers_1 (frontiers);
 
   timevar_pop (TV_DOM_FRONTIERS);
 }