X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fdominance.c;h=d46d8f56ecdd4cff044f6ee75833541b241fdf74;hb=9a5e8086de4743586d52ab102990455554db39db;hp=82562cfd49dd44c9fb60947e66eaaed5777d4133;hpb=805e22b2051e9c6a75377ea6599654d7415da483;p=pf3gnuchains%2Fgcc-fork.git

diff --git a/gcc/dominance.c b/gcc/dominance.c
index 82562cfd49d..d46d8f56ecd 100644
--- a/gcc/dominance.c
+++ b/gcc/dominance.c
@@ -1,5 +1,5 @@
 /* Calculate (post)dominators in slightly super-linear time.
-   Copyright (C) 2000 Free Software Foundation, Inc.
+   Copyright (C) 2000, 2003, 2004 Free Software Foundation, Inc.
    Contributed by Michael Matz (matz@ifh.de).
 
    This file is part of GCC.
@@ -43,16 +43,8 @@
 #include "errors.h"
 #include "et-forest.h"
 
-struct dominance_info
-{
-  et_forest_t forest;
-  varray_type varray;
-};
-
-#define BB_NODE(info, bb) \
-  ((et_forest_node_t)VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2))
-#define SET_BB_NODE(info, bb, node) \
-  (VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2) = (node))
+/* Whether the dominators and the postdominators are available.  */
+enum dom_state dom_computed[2];
 
 /* 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
@@ -109,25 +101,29 @@ 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		PARAMS ((struct dom_info *));
-static void free_dom_info		PARAMS ((struct dom_info *));
-static void calc_dfs_tree_nonrec	PARAMS ((struct dom_info *,
-						 basic_block,
-						 enum cdi_direction));
-static void calc_dfs_tree		PARAMS ((struct dom_info *,
-						 enum cdi_direction));
-static void compress			PARAMS ((struct dom_info *, TBB));
-static TBB eval				PARAMS ((struct dom_info *, TBB));
-static void link_roots			PARAMS ((struct dom_info *, TBB, TBB));
-static void calc_idoms			PARAMS ((struct dom_info *,
-						 enum cdi_direction));
-void debug_dominance_info		PARAMS ((dominance_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);
+static void calc_dfs_tree (struct dom_info *, enum cdi_direction);
+static void compress (struct dom_info *, TBB);
+static TBB eval (struct dom_info *, TBB);
+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.  */
@@ -136,10 +132,10 @@ void debug_dominance_info		PARAMS ((dominance_info));
     {								\
       unsigned int i = 1;    /* Catch content == i.  */		\
       if (! (content))						\
-	(var) = (type *) xcalloc ((num), sizeof (type));	\
+	(var) = xcalloc ((num), sizeof (type));			\
       else							\
 	{							\
-	  (var) = (type *) xmalloc ((num) * sizeof (type));	\
+	  (var) = xmalloc ((num) * sizeof (type));		\
 	  for (i = 0; i < num; i++)				\
 	    (var)[i] = (content);				\
 	}							\
@@ -150,8 +146,7 @@ void debug_dominance_info		PARAMS ((dominance_info));
    This initializes the contents of DI, which already must be allocated.  */
 
 static void
-init_dom_info (di)
-     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.  */
@@ -173,6 +168,8 @@ init_dom_info (di)
 
   di->dfsnum = 1;
   di->nodes = 0;
+
+  di->fake_exit_edge = dir ? BITMAP_XMALLOC () : NULL;
 }
 
 #undef init_ar
@@ -180,8 +177,7 @@ init_dom_info (di)
 /* Free all allocated memory in DI, but not DI itself.  */
 
 static void
-free_dom_info (di)
-     struct dom_info *di;
+free_dom_info (struct dom_info *di)
 {
   free (di->dfs_parent);
   free (di->path_min);
@@ -194,6 +190,7 @@ free_dom_info (di)
   free (di->set_child);
   free (di->dfs_order);
   free (di->dfs_to_bb);
+  BITMAP_XFREE (di->fake_exit_edge);
 }
 
 /* The nonrecursive variant of creating a DFS tree.  DI is our working
@@ -203,12 +200,9 @@ free_dom_info (di)
    assigned their dfs number and are linked together to form a tree.  */
 
 static void
-calc_dfs_tree_nonrec (di, bb, reverse)
-     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;
@@ -220,7 +214,7 @@ calc_dfs_tree_nonrec (di, bb, reverse)
   /* Ending block.  */
   basic_block ex_block;
 
-  stack = (edge *) xmalloc ((n_basic_blocks + 3) * sizeof (edge));
+  stack = xmalloc ((n_basic_blocks + 3) * sizeof (edge));
   sp = 0;
 
   /* Initialize our border blocks, and the first edge.  */
@@ -321,9 +315,7 @@ calc_dfs_tree_nonrec (di, bb, reverse)
    because there may be nodes from which the EXIT_BLOCK is unreachable.  */
 
 static void
-calc_dfs_tree (di, reverse)
-     struct dom_info *di;
-     enum cdi_direction reverse;
+calc_dfs_tree (struct dom_info *di, enum cdi_direction reverse)
 {
   /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE).  */
   basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
@@ -337,18 +329,47 @@ calc_dfs_tree (di, 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 (b->succ)
+	    {
+	      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;
@@ -364,9 +385,7 @@ calc_dfs_tree (di, reverse)
    from V to that root.  */
 
 static void
-compress (di, v)
-     struct dom_info *di;
-     TBB v;
+compress (struct dom_info *di, TBB v)
 {
   /* Btw. It's not worth to unrecurse compress() as the depth is usually not
      greater than 5 even for huge graphs (I've not seen call depth > 4).
@@ -386,9 +405,7 @@ compress (di, v)
    value on the path from V to the root.  */
 
 static inline TBB
-eval (di, v)
-     struct dom_info *di;
-     TBB v;
+eval (struct dom_info *di, TBB v)
 {
   /* The representant of the set V is in, also called root (as the set
      representation is a tree).  */
@@ -417,9 +434,7 @@ eval (di, v)
    of W.  */
 
 static void
-link_roots (di, v, w)
-     struct dom_info *di;
-     TBB v, w;
+link_roots (struct dom_info *di, TBB v, TBB w)
 {
   TBB s = w;
 
@@ -461,9 +476,7 @@ link_roots (di, v, w)
    On return the immediate dominator to node V is in di->dom[V].  */
 
 static void
-calc_idoms (di, reverse)
-     struct dom_info *di;
-     enum cdi_direction reverse;
+calc_idoms (struct dom_info *di, enum cdi_direction reverse)
 {
   TBB v, w, k, par;
   basic_block en_block;
@@ -482,7 +495,16 @@ calc_idoms (di, reverse)
       par = di->dfs_parent[v];
       k = v;
       if (reverse)
-	e = bb->succ;
+	{
+	  e = bb->succ;
+
+	  /* If this block has a fake edge to exit, process that first.  */
+	  if (bitmap_bit_p (di->fake_exit_edge, bb->index))
+	    {
+	      e_next = e;
+	      goto do_fake_exit_edge;
+	    }
+	}
       else
 	e = bb->pred;
 
@@ -490,7 +512,7 @@ calc_idoms (di, reverse)
          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)
+      for (; e ; e = e_next)
 	{
 	  TBB k1;
 	  basic_block b;
@@ -506,7 +528,10 @@ calc_idoms (di, reverse)
 	      e_next = e->pred_next;
 	    }
 	  if (b == en_block)
-	    k1 = di->dfs_order[last_basic_block];
+	    {
+	    do_fake_exit_edge:
+	      k1 = di->dfs_order[last_basic_block];
+	    }
 	  else
 	    k1 = di->dfs_order[b->index];
 
@@ -544,271 +569,410 @@ calc_idoms (di, reverse)
       di->dom[v] = di->dom[di->dom[v]];
 }
 
-/* The main entry point into this module.  IDOM is an integer array with room
-   for last_basic_block integers, DOMS is a preallocated sbitmap array having
-   room for last_basic_block^2 bits, and POST is true if the caller wants to
-   know post-dominators.
+/* Assign dfs numbers starting from NUM to NODE and its sons.  */
+
+static void
+assign_dfs_numbers (struct et_node *node, int *num)
+{
+  struct et_node *son;
+
+  node->dfs_num_in = (*num)++;
+
+  if (node->son)
+    {
+      assign_dfs_numbers (node->son, num);
+      for (son = node->son->right; son != node->son; son = son->right)
+	assign_dfs_numbers (son, num);
+    }
+
+  node->dfs_num_out = (*num)++;
+}
+
+/* Compute the data necessary for fast resolving of dominator queries in a
+   static dominator tree.  */
+
+static void
+compute_dom_fast_query (enum cdi_direction dir)
+{
+  int num = 0;
+  basic_block bb;
+
+  if (dom_computed[dir] < DOM_NO_FAST_QUERY)
+    abort ();
+
+  if (dom_computed[dir] == DOM_OK)
+    return;
 
-   On return IDOM[i] will be the BB->index of the immediate (post) dominator
-   of basic block i, and DOMS[i] will have set bit j if basic block j is a
-   (post)dominator for block i.
+  FOR_ALL_BB (bb)
+    {
+      if (!bb->dom[dir]->father)
+	assign_dfs_numbers (bb->dom[dir], &num);
+    }
+
+  dom_computed[dir] = DOM_OK;
+}
 
-   Either IDOM or DOMS may be NULL (meaning the caller is not interested in
-   immediate resp. all dominators).  */
+/* The main entry point into this module.  DIR is set depending on whether
+   we want to compute dominators or postdominators.  */
 
-dominance_info
-calculate_dominance_info (reverse)
-     enum cdi_direction reverse;
+void
+calculate_dominance_info (enum cdi_direction dir)
 {
   struct dom_info di;
-  dominance_info info;
   basic_block b;
 
-  /* allocate structure for dominance information.  */
-  info = xmalloc (sizeof (struct dominance_info));
-  info->forest = et_forest_create ();
-  VARRAY_GENERIC_PTR_INIT (info->varray, last_basic_block + 3, "dominance info");
+  if (dom_computed[dir] == DOM_OK)
+    return;
 
-  /* Add the two well-known basic blocks.  */
-  SET_BB_NODE (info, ENTRY_BLOCK_PTR, et_forest_add_node (info->forest,
-							  ENTRY_BLOCK_PTR));
-  SET_BB_NODE (info, EXIT_BLOCK_PTR, et_forest_add_node (info->forest,
-							 EXIT_BLOCK_PTR));
-  FOR_EACH_BB (b)
-    SET_BB_NODE (info, b, et_forest_add_node (info->forest, b));
+  if (dom_computed[dir] != DOM_NO_FAST_QUERY)
+    {
+      if (dom_computed[dir] != DOM_NONE)
+	free_dominance_info (dir);
 
-  init_dom_info (&di);
-  calc_dfs_tree (&di, reverse);
-  calc_idoms (&di, reverse);
+      if (n_bbs_in_dom_tree[dir])
+	abort ();
 
+      FOR_ALL_BB (b)
+	{
+	  b->dom[dir] = et_new_tree (b);
+	}
+      n_bbs_in_dom_tree[dir] = n_basic_blocks + 2;
 
-  FOR_EACH_BB (b)
-    {
-      TBB d = di.dom[di.dfs_order[b->index]];
+      init_dom_info (&di, dir);
+      calc_dfs_tree (&di, dir);
+      calc_idoms (&di, dir);
+
+      FOR_EACH_BB (b)
+	{
+	  TBB d = di.dom[di.dfs_order[b->index]];
+
+	  if (di.dfs_to_bb[d])
+	    et_set_father (b->dom[dir], di.dfs_to_bb[d]->dom[dir]);
+	}
 
-      if (di.dfs_to_bb[d])
-        et_forest_add_edge (info->forest, BB_NODE (info, di.dfs_to_bb[d]), BB_NODE (info, b));
+      free_dom_info (&di);
+      dom_computed[dir] = DOM_NO_FAST_QUERY;
     }
 
-  free_dom_info (&di);
-  return info;
+  compute_dom_fast_query (dir);
 }
 
-/* Free dominance information.  */
+/* Free dominance information for direction DIR.  */
 void
-free_dominance_info (info)
-     dominance_info info;
+free_dominance_info (enum cdi_direction dir)
 {
   basic_block bb;
 
-  /* Allow users to create new basic block without setting up the dominance
-     information for them.  */
-  FOR_EACH_BB (bb)
-    if (bb->index < (int)(info->varray->num_elements - 2)
-	&& BB_NODE (info, bb))
-      delete_from_dominance_info (info, bb);
-  delete_from_dominance_info (info, ENTRY_BLOCK_PTR);
-  delete_from_dominance_info (info, EXIT_BLOCK_PTR);
-  et_forest_delete (info->forest);
-  VARRAY_GROW (info->varray, 0);
-  free (info);
+  if (!dom_computed[dir])
+    return;
+
+  FOR_ALL_BB (bb)
+    {
+      delete_from_dominance_info (dir, bb);
+    }
+
+  /* If there are any nodes left, something is wrong.  */
+  if (n_bbs_in_dom_tree[dir])
+    abort ();
+
+  dom_computed[dir] = DOM_NONE;
 }
 
 /* Return the immediate dominator of basic block BB.  */
 basic_block
-get_immediate_dominator (dom, bb)
-     dominance_info dom;
-     basic_block bb;
+get_immediate_dominator (enum cdi_direction dir, basic_block bb)
 {
-  return et_forest_node_value (dom->forest,
-			       et_forest_parent (dom->forest,
-						 BB_NODE (dom, bb)));
+  struct et_node *node = bb->dom[dir];
+
+  if (!dom_computed[dir])
+    abort ();
+
+  if (!node->father)
+    return NULL;
+
+  return node->father->data;
 }
 
 /* Set the immediate dominator of the block possibly removing
    existing edge.  NULL can be used to remove any edge.  */
 inline void
-set_immediate_dominator (dom, bb, dominated_by)
-     dominance_info dom;
-     basic_block bb, dominated_by;
+set_immediate_dominator (enum cdi_direction dir, basic_block bb,
+			 basic_block dominated_by)
 {
-  void *aux_bb_node;
-  et_forest_node_t bb_node = BB_NODE (dom, bb);
+  struct et_node *node = bb->dom[dir];
+
+  if (!dom_computed[dir])
+    abort ();
 
-  aux_bb_node = et_forest_parent (dom->forest, bb_node);
-  if (aux_bb_node)
-    et_forest_remove_edge (dom->forest, aux_bb_node, bb_node);
-  if (dominated_by != NULL)
+  if (node->father)
     {
-      if (bb == dominated_by)
-	abort ();
-      if (!et_forest_add_edge (dom->forest, BB_NODE (dom, dominated_by), bb_node))
-	abort ();
+      if (node->father->data == dominated_by)
+	return;
+      et_split (node);
     }
+
+  if (dominated_by)
+    et_set_father (node, dominated_by->dom[dir]);
+
+  if (dom_computed[dir] == DOM_OK)
+    dom_computed[dir] = DOM_NO_FAST_QUERY;
 }
 
-/* Store all basic blocks dominated by BB into BBS and return their number.  */
+/* Store all basic blocks immediately dominated by BB into BBS and return
+   their number.  */
 int
-get_dominated_by (dom, bb, bbs)
-     dominance_info dom;
-     basic_block bb;
-     basic_block **bbs;
+get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs)
 {
-  int n, i;
+  int n;
+  struct et_node *node = bb->dom[dir], *son = node->son, *ason;
+
+  if (!dom_computed[dir])
+    abort ();
+
+  if (!son)
+    {
+      *bbs = NULL;
+      return 0;
+    }
+
+  for (ason = son->right, n = 1; ason != son; ason = ason->right)
+    n++;
+
+  *bbs = xmalloc (n * sizeof (basic_block));
+  (*bbs)[0] = son->data;
+  for (ason = son->right, n = 1; ason != son; ason = ason->right)
+    (*bbs)[n++] = ason->data;
 
-  *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
-  n = et_forest_enumerate_sons (dom->forest, BB_NODE (dom, bb), (et_forest_node_t *)*bbs);
-  for (i = 0; i < n; i++)
-   (*bbs)[i] = et_forest_node_value (dom->forest, (et_forest_node_t)(*bbs)[i]);
   return n;
 }
 
 /* Redirect all edges pointing to BB to TO.  */
 void
-redirect_immediate_dominators (dom, bb, to)
-     dominance_info dom;
-     basic_block bb;
-     basic_block to;
+redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
+			       basic_block to)
 {
-  et_forest_node_t *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
-  et_forest_node_t node = BB_NODE (dom, bb);
-  et_forest_node_t node2 = BB_NODE (dom, to);
-  int n = et_forest_enumerate_sons (dom->forest, node, bbs);
-  int i;
+  struct et_node *bb_node = bb->dom[dir], *to_node = to->dom[dir], *son;
 
-  for (i = 0; i < n; i++)
+  if (!dom_computed[dir])
+    abort ();
+
+  if (!bb_node->son)
+    return;
+
+  while (bb_node->son)
     {
-      et_forest_remove_edge (dom->forest, node, bbs[i]);
-      et_forest_add_edge (dom->forest, node2, bbs[i]);
+      son = bb_node->son;
+
+      et_split (son);
+      et_set_father (son, to_node);
     }
-  free (bbs);
+
+  if (dom_computed[dir] == DOM_OK)
+    dom_computed[dir] = DOM_NO_FAST_QUERY;
 }
 
 /* Find first basic block in the tree dominating both BB1 and BB2.  */
 basic_block
-nearest_common_dominator (dom, bb1, bb2)
-     dominance_info dom;
-     basic_block bb1;
-     basic_block bb2;
+nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
 {
+  if (!dom_computed[dir])
+    abort ();
+
   if (!bb1)
     return bb2;
   if (!bb2)
     return bb1;
-  return et_forest_node_value (dom->forest,
-			       et_forest_common_ancestor (dom->forest,
-							  BB_NODE (dom, bb1),
-							  BB_NODE (dom,
-								   bb2)));
+
+  return et_nca (bb1->dom[dir], bb2->dom[dir])->data;
 }
 
 /* Return TRUE in case BB1 is dominated by BB2.  */
 bool
-dominated_by_p (dom, bb1, bb2)
-     dominance_info dom;
-     basic_block bb1;
-     basic_block bb2;
-{
-  return nearest_common_dominator (dom, bb1, bb2) == bb2;
+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 ();
+
+  if (dom_computed[dir] == DOM_OK)
+    return (n1->dfs_num_in >= n2->dfs_num_in
+  	    && n1->dfs_num_out <= n2->dfs_num_out);
+
+  return et_below (n1, n2);
 }
 
 /* Verify invariants of dominator structure.  */
 void
-verify_dominators (dom)
-     dominance_info dom;
+verify_dominators (enum cdi_direction dir)
 {
   int err = 0;
   basic_block bb;
 
+  if (!dom_computed[dir])
+    abort ();
+
   FOR_EACH_BB (bb)
     {
       basic_block dom_bb;
 
-      dom_bb = recount_dominator (dom, bb);
-      if (dom_bb != get_immediate_dominator (dom, bb))
+      dom_bb = recount_dominator (dir, bb);
+      if (dom_bb != get_immediate_dominator (dir, bb))
 	{
 	  error ("dominator of %d should be %d, not %d",
-	   bb->index, dom_bb->index, get_immediate_dominator(dom, bb)->index);
+	   bb->index, dom_bb->index, get_immediate_dominator(dir, bb)->index);
 	  err = 1;
 	}
     }
+
+  if (dir == CDI_DOMINATORS
+      && dom_computed[dir] >= DOM_NO_FAST_QUERY)
+    {
+      FOR_EACH_BB (bb)
+	{
+	  if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR))
+	    {
+	      error ("ENTRY does not dominate bb %d", bb->index);
+	      err = 1;
+	    }
+	}
+    }
+
   if (err)
     abort ();
 }
 
-/* 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 (dom, bb)
-     dominance_info dom;
-     basic_block bb;
+recount_dominator (enum cdi_direction dir, basic_block bb)
 {
-   basic_block dom_bb = NULL;
-   edge e;
+  basic_block dom_bb = NULL;
+  edge e;
+
+  if (!dom_computed[dir])
+    abort ();
 
-   for (e = bb->pred; e; e = e->pred_next)
-     {
-       if (!dominated_by_p (dom, e->src, bb))
-         dom_bb = nearest_common_dominator (dom, dom_bb, e->src);
-     }
+  if (dir == CDI_DOMINATORS)
+    {
+      for (e = bb->pred; e; e = e->pred_next)
+	{
+	  /* 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;
+
+	  if (!dominated_by_p (dir, e->src, bb))
+	    dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
+	}
+    }
+  else
+    {
+      for (e = bb->succ; e; e = e->succ_next)
+	{
+	  if (!dominated_by_p (dir, e->dest, bb))
+	    dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
+	}
+    }
 
-   return dom_bb;
+  return dom_bb;
 }
 
 /* Iteratively recount dominators of BBS. The change is supposed to be local
    and not to grow further.  */
 void
-iterate_fix_dominators (dom, bbs, n)
-     dominance_info dom;
-     basic_block *bbs;
-     int n;
+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 ();
+
+  for (i = 0; i < n; i++)
+    set_immediate_dominator (dir, bbs[i], NULL);
+
   while (changed)
     {
       changed = 0;
       for (i = 0; i < n; i++)
 	{
-	  old_dom = get_immediate_dominator (dom, bbs[i]);
-	  new_dom = recount_dominator (dom, bbs[i]);
+	  old_dom = get_immediate_dominator (dir, bbs[i]);
+	  new_dom = recount_dominator (dir, bbs[i]);
 	  if (old_dom != new_dom)
 	    {
 	      changed = 1;
-	      set_immediate_dominator (dom, bbs[i], new_dom);
+	      set_immediate_dominator (dir, bbs[i], new_dom);
 	    }
 	}
     }
+
+  for (i = 0; i < n; i++)
+    if (!get_immediate_dominator (dir, bbs[i]))
+      abort ();
 }
 
 void
-add_to_dominance_info (dom, bb)
-     dominance_info dom;
-     basic_block bb;
+add_to_dominance_info (enum cdi_direction dir, basic_block bb)
 {
-  VARRAY_GROW (dom->varray, last_basic_block + 3);
-#ifdef ENABLE_CHECKING
-  if (BB_NODE (dom, bb))
+  if (!dom_computed[dir])
+    abort ();
+
+  if (bb->dom[dir])
     abort ();
-#endif
-  SET_BB_NODE (dom, bb, et_forest_add_node (dom->forest, bb));
+
+  n_bbs_in_dom_tree[dir]++;
+  
+  bb->dom[dir] = et_new_tree (bb);
+
+  if (dom_computed[dir] == DOM_OK)
+    dom_computed[dir] = DOM_NO_FAST_QUERY;
 }
 
 void
-delete_from_dominance_info (dom, bb)
-     dominance_info dom;
-     basic_block bb;
+delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
+{
+  if (!dom_computed[dir])
+    abort ();
+
+  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;
+}
+
+/* Returns the first son of BB in the dominator or postdominator tree
+   as determined by DIR.  */
+
+basic_block
+first_dom_son (enum cdi_direction dir, basic_block bb)
 {
-  et_forest_remove_node (dom->forest, BB_NODE (dom, bb));
-  SET_BB_NODE (dom, bb, NULL);
+  struct et_node *son = bb->dom[dir]->son;
+
+  return son ? son->data : NULL;
+}
+
+/* Returns the next dominance son after BB in the dominator or postdominator
+   tree as determined by DIR, or NULL if it was the last one.  */
+
+basic_block
+next_dom_son (enum cdi_direction dir, basic_block bb)
+{
+  struct et_node *next = bb->dom[dir]->right;
+
+  return next->father->son == next ? NULL : next->data;
 }
 
 void
-debug_dominance_info (dom)
-  dominance_info dom;
+debug_dominance_info (enum cdi_direction dir)
 {
   basic_block bb, bb2;
   FOR_EACH_BB (bb)
-    if ((bb2 = get_immediate_dominator (dom, bb)))
+    if ((bb2 = get_immediate_dominator (dir, bb)))
       fprintf (stderr, "%i %i\n", bb->index, bb2->index);
 }