GCC 4.2.0 release.

1 files changed, 347 insertions, 111 deletions

diff --git a/contrib/gcc/dominance.c b/contrib/gcc/dominance.c
index d608391..819e7d4 100644
--- a/contrib/gcc/dominance.c
+++ b/contrib/gcc/dominance.c
@@ -1,5 +1,5 @@
 /* Calculate (post)dominators in slightly super-linear time.
-   Copyright (C) 2000, 2003, 2004 Free Software Foundation, Inc.
+   Copyright (C) 2000, 2003, 2004, 2005 Free Software Foundation, Inc.
    Contributed by Michael Matz (matz@ifh.de).
 
    This file is part of GCC.
@@ -16,8 +16,8 @@
 
    You should have received a copy of the GNU General Public License
    along with GCC; see the file COPYING.  If not, write to the Free
-   Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-   02111-1307, USA.  */
+   Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+   02110-1301, USA.  */
 
 /* This file implements the well known algorithm from Lengauer and Tarjan
    to compute the dominators in a control flow graph.  A basic block D is said
@@ -30,7 +30,7 @@
 
    The algorithm computes this dominator tree implicitly by computing for
    each block its immediate dominator.  We use tree balancing and path
-   compression, so its the O(e*a(e,v)) variant, where a(e,v) is the very
+   compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very
    slowly growing functional inverse of the Ackerman function.  */
 
 #include "config.h"
@@ -39,9 +39,11 @@
 #include "tm.h"
 #include "rtl.h"
 #include "hard-reg-set.h"
+#include "obstack.h"
 #include "basic-block.h"
-#include "errors.h"
+#include "toplev.h"
 #include "et-forest.h"
+#include "timevar.h"
 
 /* Whether the dominators and the postdominators are available.  */
 enum dom_state dom_computed[2];
@@ -50,8 +52,7 @@ enum dom_state dom_computed[2];
    'undefined' or 'end of list'.  The name of each node is given by the dfs
    number of the corresponding basic block.  Please note, that we include the
    artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
-   support multiple entry points.  As it has no real basic block index we use
-   'last_basic_block' for that.  Its dfs number is of course 1.  */
+   support multiple entry points.  Its dfs number is of course 1.  */
 
 /* Type of Basic Block aka. TBB */
 typedef unsigned int TBB;
@@ -101,13 +102,17 @@ struct dom_info
      is true for every basic block bb, but not the opposite.  */
   basic_block *dfs_to_bb;
 
-  /* This is the next free DFS number when creating the DFS tree or forest.  */
+  /* This is the next free DFS number when creating the DFS tree.  */
   unsigned int dfsnum;
   /* The number of nodes in the DFS tree (==dfsnum-1).  */
   unsigned int nodes;
+
+  /* Blocks with bits set here have a fake edge to EXIT.  These are used
+     to turn a DFS forest into a proper tree.  */
+  bitmap fake_exit_edge;
 };
 
-static void init_dom_info (struct dom_info *);
+static void init_dom_info (struct dom_info *, enum cdi_direction);
 static void free_dom_info (struct dom_info *);
 static void calc_dfs_tree_nonrec (struct dom_info *, basic_block,
 				  enum cdi_direction);
@@ -118,6 +123,9 @@ static void link_roots (struct dom_info *, TBB, TBB);
 static void calc_idoms (struct dom_info *, enum cdi_direction);
 void debug_dominance_info (enum cdi_direction);
 
+/* Keeps track of the*/
+static unsigned n_bbs_in_dom_tree[2];
+
 /* Helper macro for allocating and initializing an array,
    for aesthetic reasons.  */
 #define init_ar(var, type, num, content)			\
@@ -125,10 +133,10 @@ void debug_dominance_info (enum cdi_direction);
     {								\
       unsigned int i = 1;    /* Catch content == i.  */		\
       if (! (content))						\
-	(var) = xcalloc ((num), sizeof (type));			\
+	(var) = XCNEWVEC (type, num);				\
       else							\
 	{							\
-	  (var) = xmalloc ((num) * sizeof (type));		\
+	  (var) = XNEWVEC (type, (num));			\
 	  for (i = 0; i < num; i++)				\
 	    (var)[i] = (content);				\
 	}							\
@@ -139,11 +147,9 @@ void debug_dominance_info (enum cdi_direction);
    This initializes the contents of DI, which already must be allocated.  */
 
 static void
-init_dom_info (struct dom_info *di)
+init_dom_info (struct dom_info *di, enum cdi_direction dir)
 {
-  /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or
-     EXIT_BLOCK.  */
-  unsigned int num = n_basic_blocks + 1 + 1;
+  unsigned int num = n_basic_blocks;
   init_ar (di->dfs_parent, TBB, num, 0);
   init_ar (di->path_min, TBB, num, i);
   init_ar (di->key, TBB, num, i);
@@ -161,6 +167,8 @@ init_dom_info (struct dom_info *di)
 
   di->dfsnum = 1;
   di->nodes = 0;
+
+  di->fake_exit_edge = dir ? BITMAP_ALLOC (NULL) : NULL;
 }
 
 #undef init_ar
@@ -181,6 +189,7 @@ free_dom_info (struct dom_info *di)
   free (di->set_child);
   free (di->dfs_order);
   free (di->dfs_to_bb);
+  BITMAP_FREE (di->fake_exit_edge);
 }
 
 /* The nonrecursive variant of creating a DFS tree.  DI is our working
@@ -190,13 +199,14 @@ free_dom_info (struct dom_info *di)
    assigned their dfs number and are linked together to form a tree.  */
 
 static void
-calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, enum cdi_direction reverse)
+calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb,
+		      enum cdi_direction reverse)
 {
-  /* We never call this with bb==EXIT_BLOCK_PTR (ENTRY_BLOCK_PTR if REVERSE).  */
   /* We call this _only_ if bb is not already visited.  */
   edge e;
   TBB child_i, my_i = 0;
-  edge *stack;
+  edge_iterator *stack;
+  edge_iterator ei, einext;
   int sp;
   /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
      problem).  */
@@ -204,19 +214,19 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, enum cdi_direction re
   /* Ending block.  */
   basic_block ex_block;
 
-  stack = xmalloc ((n_basic_blocks + 3) * sizeof (edge));
+  stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
   sp = 0;
 
   /* Initialize our border blocks, and the first edge.  */
   if (reverse)
     {
-      e = bb->pred;
+      ei = ei_start (bb->preds);
       en_block = EXIT_BLOCK_PTR;
       ex_block = ENTRY_BLOCK_PTR;
     }
   else
     {
-      e = bb->succ;
+      ei = ei_start (bb->succs);
       en_block = ENTRY_BLOCK_PTR;
       ex_block = EXIT_BLOCK_PTR;
     }
@@ -228,9 +238,9 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, enum cdi_direction re
 
       /* This loop traverses edges e in depth first manner, and fills the
          stack.  */
-      while (e)
+      while (!ei_end_p (ei))
 	{
-	  edge e_next;
+	  e = ei_edge (ei);
 
 	  /* Deduce from E the current and the next block (BB and BN), and the
 	     next edge.  */
@@ -243,26 +253,25 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, enum cdi_direction re
 	         with the next edge out of the current node.  */
 	      if (bn == ex_block || di->dfs_order[bn->index])
 		{
-		  e = e->pred_next;
+		  ei_next (&ei);
 		  continue;
 		}
 	      bb = e->dest;
-	      e_next = bn->pred;
+	      einext = ei_start (bn->preds);
 	    }
 	  else
 	    {
 	      bn = e->dest;
 	      if (bn == ex_block || di->dfs_order[bn->index])
 		{
-		  e = e->succ_next;
+		  ei_next (&ei);
 		  continue;
 		}
 	      bb = e->src;
-	      e_next = bn->succ;
+	      einext = ei_start (bn->succs);
 	    }
 
-	  if (bn == en_block)
-	    abort ();
+	  gcc_assert (bn != en_block);
 
 	  /* Fill the DFS tree info calculatable _before_ recursing.  */
 	  if (bb != en_block)
@@ -274,13 +283,13 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, enum cdi_direction re
 	  di->dfs_parent[child_i] = my_i;
 
 	  /* Save the current point in the CFG on the stack, and recurse.  */
-	  stack[sp++] = e;
-	  e = e_next;
+	  stack[sp++] = ei;
+	  ei = einext;
 	}
 
       if (!sp)
 	break;
-      e = stack[--sp];
+      ei = stack[--sp];
 
       /* OK.  The edge-list was exhausted, meaning normally we would
          end the recursion.  After returning from the recursive call,
@@ -291,10 +300,7 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, enum cdi_direction re
          the block not yet completed (the parent of the one above)
          in e->src.  This could be used e.g. for computing the number of
          descendants or the tree depth.  */
-      if (reverse)
-	e = e->pred_next;
-      else
-	e = e->succ_next;
+      ei_next (&ei);
     }
   free (stack);
 }
@@ -319,25 +325,53 @@ calc_dfs_tree (struct dom_info *di, enum cdi_direction reverse)
     {
       /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
          They are reverse-unreachable.  In the dom-case we disallow such
-         nodes, but in post-dom we have to deal with them, so we simply
-         include them in the DFS tree which actually becomes a forest.  */
+         nodes, but in post-dom we have to deal with them.
+
+	 There are two situations in which this occurs.  First, noreturn
+	 functions.  Second, infinite loops.  In the first case we need to
+	 pretend that there is an edge to the exit block.  In the second
+	 case, we wind up with a forest.  We need to process all noreturn
+	 blocks before we know if we've got any infinite loops.  */
+
       basic_block b;
+      bool saw_unconnected = false;
+
       FOR_EACH_BB_REVERSE (b)
 	{
-	  if (di->dfs_order[b->index])
-	    continue;
+	  if (EDGE_COUNT (b->succs) > 0)
+	    {
+	      if (di->dfs_order[b->index] == 0)
+		saw_unconnected = true;
+	      continue;
+	    }
+	  bitmap_set_bit (di->fake_exit_edge, b->index);
 	  di->dfs_order[b->index] = di->dfsnum;
 	  di->dfs_to_bb[di->dfsnum] = b;
+	  di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
 	  di->dfsnum++;
 	  calc_dfs_tree_nonrec (di, b, reverse);
 	}
+
+      if (saw_unconnected)
+	{
+	  FOR_EACH_BB_REVERSE (b)
+	    {
+	      if (di->dfs_order[b->index])
+		continue;
+	      bitmap_set_bit (di->fake_exit_edge, b->index);
+	      di->dfs_order[b->index] = di->dfsnum;
+	      di->dfs_to_bb[di->dfsnum] = b;
+	      di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
+	      di->dfsnum++;
+	      calc_dfs_tree_nonrec (di, b, reverse);
+	    }
+	}
     }
 
   di->nodes = di->dfsnum - 1;
 
   /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all.  */
-  if (di->nodes != (unsigned int) n_basic_blocks + 1)
-    abort ();
+  gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
 }
 
 /* Compress the path from V to the root of its set and update path_min at the
@@ -441,6 +475,8 @@ calc_idoms (struct dom_info *di, enum cdi_direction reverse)
 {
   TBB v, w, k, par;
   basic_block en_block;
+  edge_iterator ei, einext;
+
   if (reverse)
     en_block = EXIT_BLOCK_PTR;
   else
@@ -451,36 +487,43 @@ calc_idoms (struct dom_info *di, enum cdi_direction reverse)
   while (v > 1)
     {
       basic_block bb = di->dfs_to_bb[v];
-      edge e, e_next;
+      edge e;
 
       par = di->dfs_parent[v];
       k = v;
+
+      ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
+
       if (reverse)
-	e = bb->succ;
-      else
-	e = bb->pred;
+	{
+	  /* If this block has a fake edge to exit, process that first.  */
+	  if (bitmap_bit_p (di->fake_exit_edge, bb->index))
+	    {
+	      einext = ei;
+	      einext.index = 0;
+	      goto do_fake_exit_edge;
+	    }
+	}
 
       /* Search all direct predecessors for the smallest node with a path
          to them.  That way we have the smallest node with also a path to
          us only over nodes behind us.  In effect we search for our
          semidominator.  */
-      for (; e; e = e_next)
+      while (!ei_end_p (ei))
 	{
 	  TBB k1;
 	  basic_block b;
 
-	  if (reverse)
-	    {
-	      b = e->dest;
-	      e_next = e->succ_next;
-	    }
-	  else
+	  e = ei_edge (ei);
+	  b = (reverse) ? e->dest : e->src;
+	  einext = ei;
+	  ei_next (&einext);
+
+	  if (b == en_block)
 	    {
-	      b = e->src;
-	      e_next = e->pred_next;
+	    do_fake_exit_edge:
+	      k1 = di->dfs_order[last_basic_block];
 	    }
-	  if (b == en_block)
-	    k1 = di->dfs_order[last_basic_block];
 	  else
 	    k1 = di->dfs_order[b->index];
 
@@ -490,6 +533,8 @@ calc_idoms (struct dom_info *di, enum cdi_direction reverse)
 	    k1 = di->key[eval (di, k1)];
 	  if (k1 < k)
 	    k = k1;
+
+	  ei = einext;
 	}
 
       di->key[v] = k;
@@ -531,7 +576,7 @@ assign_dfs_numbers (struct et_node *node, int *num)
     {
       assign_dfs_numbers (node->son, num);
       for (son = node->son->right; son != node->son; son = son->right)
-      assign_dfs_numbers (son, num);
+	assign_dfs_numbers (son, num);
     }
 
   node->dfs_num_out = (*num)++;
@@ -546,8 +591,7 @@ compute_dom_fast_query (enum cdi_direction dir)
   int num = 0;
   basic_block bb;
 
-  if (dom_computed[dir] < DOM_NO_FAST_QUERY)
-    abort ();
+  gcc_assert (dom_info_available_p (dir));
 
   if (dom_computed[dir] == DOM_OK)
     return;
@@ -555,7 +599,7 @@ compute_dom_fast_query (enum cdi_direction dir)
   FOR_ALL_BB (bb)
     {
       if (!bb->dom[dir]->father)
-      assign_dfs_numbers (bb->dom[dir], &num);
+	assign_dfs_numbers (bb->dom[dir], &num);
     }
 
   dom_computed[dir] = DOM_OK;
@@ -573,17 +617,18 @@ calculate_dominance_info (enum cdi_direction dir)
   if (dom_computed[dir] == DOM_OK)
     return;
 
-  if (dom_computed[dir] != DOM_NO_FAST_QUERY)
+  timevar_push (TV_DOMINANCE);
+  if (!dom_info_available_p (dir))
     {
-      if (dom_computed[dir] != DOM_NONE)
-      free_dominance_info (dir);
+      gcc_assert (!n_bbs_in_dom_tree[dir]);
 
       FOR_ALL_BB (b)
 	{
 	  b->dom[dir] = et_new_tree (b);
 	}
+      n_bbs_in_dom_tree[dir] = n_basic_blocks;
 
-      init_dom_info (&di);
+      init_dom_info (&di, dir);
       calc_dfs_tree (&di, dir);
       calc_idoms (&di, dir);
 
@@ -600,6 +645,8 @@ calculate_dominance_info (enum cdi_direction dir)
     }
 
   compute_dom_fast_query (dir);
+
+  timevar_pop (TV_DOMINANCE);
 }
 
 /* Free dominance information for direction DIR.  */
@@ -608,13 +655,17 @@ free_dominance_info (enum cdi_direction dir)
 {
   basic_block bb;
 
-  if (!dom_computed[dir])
+  if (!dom_info_available_p (dir))
     return;
 
   FOR_ALL_BB (bb)
     {
-      delete_from_dominance_info (dir, bb);
+      et_free_tree_force (bb->dom[dir]);
+      bb->dom[dir] = NULL;
     }
+  et_free_pools ();
+
+  n_bbs_in_dom_tree[dir] = 0;
 
   dom_computed[dir] = DOM_NONE;
 }
@@ -625,13 +676,12 @@ get_immediate_dominator (enum cdi_direction dir, basic_block bb)
 {
   struct et_node *node = bb->dom[dir];
 
-  if (!dom_computed[dir])
-    abort ();
+  gcc_assert (dom_computed[dir]);
 
   if (!node->father)
     return NULL;
 
-  return node->father->data; 
+  return node->father->data;
 }
 
 /* Set the immediate dominator of the block possibly removing
@@ -642,13 +692,12 @@ set_immediate_dominator (enum cdi_direction dir, basic_block bb,
 {
   struct et_node *node = bb->dom[dir];
 
-  if (!dom_computed[dir])
-    abort ();
+  gcc_assert (dom_computed[dir]);
 
   if (node->father)
     {
       if (node->father->data == dominated_by)
-      return;
+	return;
       et_split (node);
     }
 
@@ -667,8 +716,7 @@ get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs)
   int n;
   struct et_node *node = bb->dom[dir], *son = node->son, *ason;
 
-  if (!dom_computed[dir])
-    abort ();
+  gcc_assert (dom_computed[dir]);
 
   if (!son)
     {
@@ -679,7 +727,7 @@ get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs)
   for (ason = son->right, n = 1; ason != son; ason = ason->right)
     n++;
 
-  *bbs = xmalloc (n * sizeof (basic_block));
+  *bbs = XNEWVEC (basic_block, n);
   (*bbs)[0] = son->data;
   for (ason = son->right, n = 1; ason != son; ason = ason->right)
     (*bbs)[n++] = ason->data;
@@ -687,6 +735,32 @@ get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs)
   return n;
 }
 
+/* Find all basic blocks that are immediately dominated (in direction DIR)
+   by some block between N_REGION ones stored in REGION, except for blocks
+   in the REGION itself.  The found blocks are stored to DOMS and their number
+   is returned.  */
+
+unsigned
+get_dominated_by_region (enum cdi_direction dir, basic_block *region,
+			 unsigned n_region, basic_block *doms)
+{
+  unsigned n_doms = 0, i;
+  basic_block dom;
+
+  for (i = 0; i < n_region; i++)
+    region[i]->flags |= BB_DUPLICATED;
+  for (i = 0; i < n_region; i++)
+    for (dom = first_dom_son (dir, region[i]);
+	 dom;
+	 dom = next_dom_son (dir, dom))
+      if (!(dom->flags & BB_DUPLICATED))
+	doms[n_doms++] = dom;
+  for (i = 0; i < n_region; i++)
+    region[i]->flags &= ~BB_DUPLICATED;
+
+  return n_doms;
+}
+
 /* Redirect all edges pointing to BB to TO.  */
 void
 redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
@@ -694,8 +768,7 @@ redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
 {
   struct et_node *bb_node = bb->dom[dir], *to_node = to->dom[dir], *son;
 
-  if (!dom_computed[dir])
-    abort ();
+  gcc_assert (dom_computed[dir]);
 
   if (!bb_node->son)
     return;
@@ -716,8 +789,7 @@ redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
 basic_block
 nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
 {
-  if (!dom_computed[dir])
-    abort ();
+  gcc_assert (dom_computed[dir]);
 
   if (!bb1)
     return bb2;
@@ -727,22 +799,138 @@ nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block b
   return et_nca (bb1->dom[dir], bb2->dom[dir])->data;
 }
 
+
+/* Find the nearest common dominator for the basic blocks in BLOCKS,
+   using dominance direction DIR.  */
+
+basic_block
+nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
+{
+  unsigned i, first;
+  bitmap_iterator bi;
+  basic_block dom;
+  
+  first = bitmap_first_set_bit (blocks);
+  dom = BASIC_BLOCK (first);
+  EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
+    if (dom != BASIC_BLOCK (i))
+      dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i));
+
+  return dom;
+}
+
+/*  Given a dominator tree, we can determine whether one thing
+    dominates another in constant time by using two DFS numbers:
+
+    1. The number for when we visit a node on the way down the tree
+    2. The number for when we visit a node on the way back up the tree
+
+    You can view these as bounds for the range of dfs numbers the
+    nodes in the subtree of the dominator tree rooted at that node
+    will contain.
+    
+    The dominator tree is always a simple acyclic tree, so there are
+    only three possible relations two nodes in the dominator tree have
+    to each other:
+    
+    1. Node A is above Node B (and thus, Node A dominates node B)
+
+     A
+     |
+     C
+    / \
+   B   D
+
+
+   In the above case, DFS_Number_In of A will be <= DFS_Number_In of
+   B, and DFS_Number_Out of A will be >= DFS_Number_Out of B.  This is
+   because we must hit A in the dominator tree *before* B on the walk
+   down, and we will hit A *after* B on the walk back up
+   
+   2. Node A is below node B (and thus, node B dominates node A)
+   
+   
+     B
+     |
+     A
+    / \
+   C   D
+
+   In the above case, DFS_Number_In of A will be >= DFS_Number_In of
+   B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
+   
+   This is because we must hit A in the dominator tree *after* B on
+   the walk down, and we will hit A *before* B on the walk back up
+   
+   3. Node A and B are siblings (and thus, neither dominates the other)
+
+     C
+     |
+     D
+    / \
+   A   B
+
+   In the above case, DFS_Number_In of A will *always* be <=
+   DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
+   DFS_Number_Out of B.  This is because we will always finish the dfs
+   walk of one of the subtrees before the other, and thus, the dfs
+   numbers for one subtree can't intersect with the range of dfs
+   numbers for the other subtree.  If you swap A and B's position in
+   the dominator tree, the comparison changes direction, but the point
+   is that both comparisons will always go the same way if there is no
+   dominance relationship.
+
+   Thus, it is sufficient to write
+
+   A_Dominates_B (node A, node B)
+   {
+     return DFS_Number_In(A) <= DFS_Number_In(B) 
+            && DFS_Number_Out (A) >= DFS_Number_Out(B);
+   }
+
+   A_Dominated_by_B (node A, node B)
+   {
+     return DFS_Number_In(A) >= DFS_Number_In(A)
+            && DFS_Number_Out (A) <= DFS_Number_Out(B);
+   }  */
+
 /* Return TRUE in case BB1 is dominated by BB2.  */
 bool
 dominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2)
-{
+{ 
   struct et_node *n1 = bb1->dom[dir], *n2 = bb2->dom[dir];
 
-  if (!dom_computed[dir])
-    abort ();
+  gcc_assert (dom_computed[dir]);
 
   if (dom_computed[dir] == DOM_OK)
     return (n1->dfs_num_in >= n2->dfs_num_in
-	    && n1->dfs_num_out <= n2->dfs_num_out);
+  	    && n1->dfs_num_out <= n2->dfs_num_out);
 
   return et_below (n1, n2);
 }
 
+/* Returns the entry dfs number for basic block BB, in the direction DIR.  */
+
+unsigned
+bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
+{
+  struct et_node *n = bb->dom[dir];
+
+  gcc_assert (dom_computed[dir] == DOM_OK);
+  return n->dfs_num_in;
+}
+
+/* Returns the exit dfs number for basic block BB, in the direction DIR.  */
+
+unsigned
+bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
+{
+  struct et_node *n = bb->dom[dir];
+
+  gcc_assert (dom_computed[dir] == DOM_OK);
+  return n->dfs_num_out;
+}
+
 /* Verify invariants of dominator structure.  */
 void
 verify_dominators (enum cdi_direction dir)
@@ -750,42 +938,78 @@ verify_dominators (enum cdi_direction dir)
   int err = 0;
   basic_block bb;
 
-  if (!dom_computed[dir])
-    abort ();
+  gcc_assert (dom_info_available_p (dir));
 
   FOR_EACH_BB (bb)
     {
       basic_block dom_bb;
+      basic_block imm_bb;
 
       dom_bb = recount_dominator (dir, bb);
-      if (dom_bb != get_immediate_dominator (dir, bb))
+      imm_bb = get_immediate_dominator (dir, bb);
+      if (dom_bb != imm_bb)
 	{
-	  error ("dominator of %d should be %d, not %d",
-	   bb->index, dom_bb->index, get_immediate_dominator(dir, bb)->index);
+	  if ((dom_bb == NULL) || (imm_bb == NULL))
+	    error ("dominator of %d status unknown", bb->index);
+	  else
+	    error ("dominator of %d should be %d, not %d",
+		   bb->index, dom_bb->index, imm_bb->index);
 	  err = 1;
 	}
     }
-  if (err)
-    abort ();
+
+  if (dir == CDI_DOMINATORS)
+    {
+      FOR_EACH_BB (bb)
+	{
+	  if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR))
+	    {
+	      error ("ENTRY does not dominate bb %d", bb->index);
+	      err = 1;
+	    }
+	}
+    }
+
+  gcc_assert (!err);
 }
 
-/* Recount dominator of BB.  */
+/* Determine immediate dominator (or postdominator, according to DIR) of BB,
+   assuming that dominators of other blocks are correct.  We also use it to
+   recompute the dominators in a restricted area, by iterating it until it
+   reaches a fixed point.  */
+
 basic_block
 recount_dominator (enum cdi_direction dir, basic_block bb)
 {
-   basic_block dom_bb = NULL;
-   edge e;
+  basic_block dom_bb = NULL;
+  edge e;
+  edge_iterator ei;
 
-  if (!dom_computed[dir])
-    abort ();
+  gcc_assert (dom_computed[dir]);
 
-   for (e = bb->pred; e; e = e->pred_next)
-     {
-       if (!dominated_by_p (dir, e->src, bb))
-         dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
-     }
+  if (dir == CDI_DOMINATORS)
+    {
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	{
+	  /* Ignore the predecessors that either are not reachable from
+	     the entry block, or whose dominator was not determined yet.  */
+	  if (!dominated_by_p (dir, e->src, ENTRY_BLOCK_PTR))
+	    continue;
 
-   return dom_bb;
+	  if (!dominated_by_p (dir, e->src, bb))
+	    dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
+	}
+    }
+  else
+    {
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	{
+	  if (!dominated_by_p (dir, e->dest, bb))
+	    dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
+	}
+    }
+
+  return dom_bb;
 }
 
 /* Iteratively recount dominators of BBS. The change is supposed to be local
@@ -796,8 +1020,10 @@ iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n)
   int i, changed = 1;
   basic_block old_dom, new_dom;
 
-  if (!dom_computed[dir])
-    abort ();
+  gcc_assert (dom_computed[dir]);
+
+  for (i = 0; i < n; i++)
+    set_immediate_dominator (dir, bbs[i], NULL);
 
   while (changed)
     {
@@ -813,17 +1039,19 @@ iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n)
 	    }
 	}
     }
+
+  for (i = 0; i < n; i++)
+    gcc_assert (get_immediate_dominator (dir, bbs[i]));
 }
 
 void
 add_to_dominance_info (enum cdi_direction dir, basic_block bb)
 {
-  if (!dom_computed[dir])
-    abort ();
-
-  if (bb->dom[dir])
-    abort ();
+  gcc_assert (dom_computed[dir]);
+  gcc_assert (!bb->dom[dir]);
 
+  n_bbs_in_dom_tree[dir]++;
+  
   bb->dom[dir] = et_new_tree (bb);
 
   if (dom_computed[dir] == DOM_OK)
@@ -833,11 +1061,11 @@ add_to_dominance_info (enum cdi_direction dir, basic_block bb)
 void
 delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
 {
-  if (!dom_computed[dir])
-    abort ();
+  gcc_assert (dom_computed[dir]);
 
   et_free_tree (bb->dom[dir]);
   bb->dom[dir] = NULL;
+  n_bbs_in_dom_tree[dir]--;
 
   if (dom_computed[dir] == DOM_OK)
     dom_computed[dir] = DOM_NO_FAST_QUERY;
@@ -865,6 +1093,14 @@ next_dom_son (enum cdi_direction dir, basic_block bb)
   return next->father->son == next ? NULL : next->data;
 }
 
+/* Returns true if dominance information for direction DIR is available.  */
+
+bool
+dom_info_available_p (enum cdi_direction dir)
+{
+  return dom_computed[dir] != DOM_NONE;
+}
+
 void
 debug_dominance_info (enum cdi_direction dir)
 {