1 files changed, 79 insertions, 0 deletions
diff --git a/gcc/cfganal.c b/gcc/cfganal.c
index db0238c..58745d0 100644
--- a/gcc/cfganal.c
+++ b/gcc/cfganal.c
@@ -31,6 +31,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "recog.h"
 #include "toplev.h"
 #include "tm_p.h"
+#include "timevar.h"
 
 /* Store the data structures necessary for depth-first search.  */
 struct depth_first_search_dsS {
@@ -1041,3 +1042,81 @@ dfs_enumerate_from (basic_block bb, int reverse,
     rslt[sp]->flags &= ~BB_VISITED;
   return tv;
 }
+
+
+/* Computing the Dominance Frontier:
+
+   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)
+{
+  edge e;
+  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 (e = bb->succ; e; e = e->succ_next)
+    {
+      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))
+    {
+      int x;
+
+      EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x,
+	{
+	  if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb)
+	    bitmap_set_bit (frontiers[bb->index], x);
+	});
+    }
+}
+
+
+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, ENTRY_BLOCK_PTR->succ->dest, done);
+
+  sbitmap_free (done);
+
+  timevar_pop (TV_DOM_FRONTIERS);
+}
+