* basic-block.h (struct edge_def): Remove crossing_edge.

	(EDGE_CROSSING): New define.
	(EDGE_ALL_FLAGS): Update.
	* bb-reorder.c (find_traces_1_round, better_edge_p,
	find_rarely_executed_basic_blocks_and_cr, fix_up_fall_thru_edges,
	find_jump_block, fix_crossing_conditional_branches,
	fix_crossing_unconditional_branches, add_reg_crossing_jump_notes):
	Replace all occurences of crossing_edge with an edge flag check
	or set/reset.
	* cfgcleanup.c (try_simplify_condjump, try_forward_edges,
	try_crossjump_bb): Likewise.
	* cfglayout.c (fixup_reorder_chain): Likewise.
	* cfgrtl.c (force_nonfallthru_and_redirect,
	commit_one_edge_insertion): Likewise.

	* Makefile.in (cfganal.o): Depend on TIMEVAR_H.
	* tree-flow.h (compute_dominance_frontiers): Move prototype...
	* basic-block.h:  ...here.
	* tree-cfg.c (compute_dominance_frontiers_1,
	compute_dominance_frontiers): Move from here...
	* cfganal.c: ...to here.  Include timevar.h.


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

1 files changed, 79 insertions, 0 deletions

diff --git a/gcc/cfganal.c b/gcc/cfganal.c
index db0238c68eb..58745d0ff09 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);
+}
+