In libobjc/:

[pf3gnuchains/gcc-fork.git] / gcc / dominance.c

diff --git a/gcc/dominance.c b/gcc/dominance.c
index f93c4dc..b0b97c6 100644 (file)
--- a/gcc/dominance.c
+++ b/gcc/dominance.c
@@ -1,6 +1,6 @@
 /* Calculate (post)dominators in slightly super-linear time.
-   Copyright (C) 2000, 2003, 2004, 2005, 2006, 2007, 2008 Free
-   Software Foundation, Inc.
+   Copyright (C) 2000, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
+   Free Software Foundation, Inc.
    Contributed by Michael Matz (matz@ifh.de).
 
    This file is part of GCC.
@@ -41,12 +41,14 @@
 #include "hard-reg-set.h"
 #include "obstack.h"
 #include "basic-block.h"
+#include "diagnostic-core.h"
 #include "toplev.h"
 #include "et-forest.h"
 #include "timevar.h"
 #include "vecprim.h"
 #include "pointer-set.h"
 #include "graphds.h"
+#include "bitmap.h"
 
 /* We name our nodes with integers, beginning with 1.  Zero is reserved for
    'undefined' or 'end of list'.  The name of each node is given by the dfs
@@ -711,7 +713,7 @@ get_immediate_dominator (enum cdi_direction dir, basic_block bb)
 
 /* Set the immediate dominator of the block possibly removing
    existing edge.  NULL can be used to remove any edge.  */
-inline void
+void
 set_immediate_dominator (enum cdi_direction dir, basic_block bb,
                         basic_block dominated_by)
 {
@@ -782,16 +784,20 @@ get_dominated_by_region (enum cdi_direction dir, basic_block *region,
 }
 
 /* Returns the list of basic blocks including BB dominated by BB, in the
-   direction DIR.  The vector will be sorted in preorder.  */
+   direction DIR up to DEPTH in the dominator tree.  The DEPTH of zero will
+   produce a vector containing all dominated blocks.  The vector will be sorted
+   in preorder.  */
 
 VEC (basic_block, heap) *
-get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
+get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
 {
   VEC(basic_block, heap) *bbs = NULL;
   unsigned i;
+  unsigned next_level_start;
 
   i = 0;
   VEC_safe_push (basic_block, heap, bbs, bb);
+  next_level_start = 1; /* = VEC_length (basic_block, bbs); */
 
   do
     {
@@ -802,12 +808,24 @@ get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
           son;
           son = next_dom_son (dir, son))
        VEC_safe_push (basic_block, heap, bbs, son);
+
+      if (i == next_level_start && --depth)
+       next_level_start = VEC_length (basic_block, bbs);
     }
-  while (i < VEC_length (basic_block, bbs));
+  while (i < next_level_start);
 
   return bbs;
 }
 
+/* Returns the list of basic blocks including BB dominated by BB, in the
+   direction DIR.  The vector will be sorted in preorder.  */
+
+VEC (basic_block, heap) *
+get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
+{
+  return get_dominated_to_depth (dir, bb, 0);
+}
+
 /* Redirect all edges pointing to BB to TO.  */
 void
 redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
@@ -988,7 +1006,7 @@ bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
 }
 
 /* Verify invariants of dominator structure.  */
-void
+DEBUG_FUNCTION void
 verify_dominators (enum cdi_direction dir)
 {
   int err = 0;
@@ -1180,7 +1198,7 @@ determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs,
   for (i = nc - 1; i >= 0; i--)
     {
       dom = NULL;
-      for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
+      FOR_EACH_VEC_ELT (int, sccs[i], si, a)
        {
          bb = VEC_index (basic_block, bbs, a);
          FOR_EACH_EDGE (e, ei, bb->preds)
@@ -1193,7 +1211,7 @@ determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs,
        }
 
       gcc_assert (dom != NULL);
-      for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
+      FOR_EACH_VEC_ELT (int, sccs[i], si, a)
        {
          bb = VEC_index (basic_block, bbs, a);
          set_immediate_dominator (CDI_DOMINATORS, bb, dom);
@@ -1296,7 +1314,7 @@ iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
         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++)
+      FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
        set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
     }
 
@@ -1316,7 +1334,7 @@ iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
 
   /* Construct the graph G.  */
   map = pointer_map_create ();
-  for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+  FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
     {
       /* If the dominance tree is conservatively correct, split it now.  */
       if (conservative)
@@ -1328,7 +1346,7 @@ iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
   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_VEC_ELT (basic_block, bbs, i, bb)
     {
       FOR_EACH_EDGE (e, ei, bb->preds)
        {
@@ -1339,10 +1357,9 @@ iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
          dom_i = (size_t) *pointer_map_contains (map, dom);
 
          /* Do not include parallel edges to G.  */
-         if (bitmap_bit_p ((bitmap) g->vertices[dom_i].data, i))
+         if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
            continue;
 
-         bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i);
          add_edge (g, dom_i, i);
        }
     }
@@ -1465,7 +1482,7 @@ dom_info_available_p (enum cdi_direction dir)
   return dom_computed[dir_index] != DOM_NONE;
 }
 
-void
+DEBUG_FUNCTION void
 debug_dominance_info (enum cdi_direction dir)
 {
   basic_block bb, bb2;
@@ -1506,7 +1523,7 @@ debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
 /* Prints to stderr representation of the dominance tree (for direction DIR)
    rooted in ROOT.  */
 
-void
+DEBUG_FUNCTION void
 debug_dominance_tree (enum cdi_direction dir, basic_block root)
 {
   debug_dominance_tree_1 (dir, root, 0, false);