+
+/* Performs dfs search from BB over vertices satisfying PREDICATE;
+ if REVERSE, go against direction of edges. Returns number of blocks
+ found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
+int
+dfs_enumerate_from (basic_block bb, int reverse,
+ bool (*predicate) (basic_block, void *),
+ basic_block *rslt, int rslt_max, void *data)
+{
+ basic_block *st, lbb;
+ int sp = 0, tv = 0;
+
+ st = xcalloc (rslt_max, sizeof (basic_block));
+ rslt[tv++] = st[sp++] = bb;
+ bb->flags |= BB_VISITED;
+ while (sp)
+ {
+ edge e;
+ edge_iterator ei;
+ lbb = st[--sp];
+ if (reverse)
+ {
+ FOR_EACH_EDGE (e, ei, lbb->preds)
+ if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
+ {
+ gcc_assert (tv != rslt_max);
+ rslt[tv++] = st[sp++] = e->src;
+ e->src->flags |= BB_VISITED;
+ }
+ }
+ else
+ {
+ FOR_EACH_EDGE (e, ei, lbb->succs)
+ if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
+ {
+ gcc_assert (tv != rslt_max);
+ rslt[tv++] = st[sp++] = e->dest;
+ e->dest->flags |= BB_VISITED;
+ }
+ }
+ }
+ free (st);
+ for (sp = 0; sp < tv; sp++)
+ 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;
+ 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))
+ {
+ unsigned x;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x, bi)
+ {
+ 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, EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest, done);
+
+ sbitmap_free (done);
+
+ timevar_pop (TV_DOM_FRONTIERS);
+}
+