Michael Matz <matzmich@cs.tu-berlin.de>

        * dominance.c: New file.
        * Makefile.in (OBJS): Add dominance.o.

        * flow.c (compute_flow_dominators): Remove.
        (compute_immediate_dominators): Remove.
        (compute_immediate_postdominators): Remove.
        * basic-block.h: Remove their prototypes.
        (calculate_dominance_info): Add prototype.

        * dce.c (eliminate_dead_code): Change calls to above functions.
        Don't compute dominators but only immediate dominators.
        * flow.c (flow_loops_find): Change callers.
        * gcse.c (compute_code_hoist_data): Likewise.
        * haifa-sched.c (schedule_insns): Likewise.
        * ifcvt.c (if_convert): Likewise.
        * ssa.c (convert_to_ssa): Likewise, and only compute immediate
        dominators.

From-SVN: r37449

10 files changed, 663 insertions, 269 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d9794e1..ace6a89 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,23 @@
+2000-11-14  Michael Matz  <matzmich@cs.tu-berlin.de>
+
+	* dominance.c: New file.
+	* Makefile.in (OBJS): Add dominance.o.
+
+	* flow.c (compute_flow_dominators): Remove.
+	(compute_immediate_dominators): Remove.
+	(compute_immediate_postdominators): Remove.
+	* basic-block.h: Remove their prototypes.
+	(calculate_dominance_info): Add prototype.
+
+	* dce.c (eliminate_dead_code): Change calls to above functions.
+	Don't compute dominators but only immediate dominators.
+	* flow.c (flow_loops_find): Change callers.
+	* gcse.c (compute_code_hoist_data): Likewise.
+	* haifa-sched.c (schedule_insns): Likewise.
+	* ifcvt.c (if_convert): Likewise.
+	* ssa.c (convert_to_ssa): Likewise, and only compute immediate
+	dominators.
+
 2000-11-14  Richard Henderson  <rth@redhat.com>
 
 	* stmt.c (warn_if_unused_value): Don't warn if the expression
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 1550ec7..ff820d8 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -735,7 +735,7 @@ OBJS = diagnostic.o version.o tree.o print-tree.o stor-layout.o fold-const.o  \
  profile.o insn-attrtab.o $(out_object_file) $(EXTRA_OBJS) convert.o	      \
  mbchar.o splay-tree.o graph.o sbitmap.o resource.o hash.o predict.o	      \
  lists.o ggc-common.o $(GGC) simplify-rtx.o ssa.o bb-reorder.o		      \
- sibcall.o conflict.o timevar.o ifcvt.o dependence.o dce.o
+ sibcall.o conflict.o timevar.o ifcvt.o dominance.o dependence.o dce.o
 
 BACKEND = toplev.o libbackend.a
 
@@ -1403,6 +1403,8 @@ unroll.o : unroll.c $(CONFIG_H) system.h $(RTL_H) insn-config.h function.h \
 flow.o : flow.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h insn-config.h \
    $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
    insn-flags.h function.h except.h $(EXPR_H) ssa.h $(GGC_H)
+dominance.o : dominance.c $(CONFIG_H) system.h $(RTL_H) hard-reg-set.h \
+   $(BASIC_BLOCK_H)
 combine.o : combine.c $(CONFIG_H) system.h $(RTL_H) flags.h function.h \
    insn-config.h insn-flags.h insn-codes.h $(INSN_ATTR_H) $(REGS_H) $(EXPR_H) \
    $(BASIC_BLOCK_H) $(RECOG_H) real.h hard-reg-set.h toplev.h
diff --git a/gcc/basic-block.h b/gcc/basic-block.h
index 04177eb..f3ed1a9 100644
--- a/gcc/basic-block.h
+++ b/gcc/basic-block.h
@@ -458,10 +458,6 @@ void verify_edge_list			PARAMS ((FILE *, struct edge_list *));
 int find_edge_index			PARAMS ((struct edge_list *, 
 						 basic_block, basic_block));
 
-extern void compute_flow_dominators	PARAMS ((sbitmap *, sbitmap *));
-extern void compute_immediate_dominators	PARAMS ((int *, sbitmap *));
-extern void compute_immediate_postdominators	PARAMS ((int *, sbitmap *));
-
 
 enum update_life_extent
 {
@@ -565,4 +561,15 @@ extern conflict_graph conflict_graph_compute
                                         PARAMS ((regset,
 						 partition));
 
+/* In dominance.c */
+
+enum cdi_direction
+{
+  CDI_DOMINATORS,
+  CDI_POST_DOMINATORS
+};
+
+extern void calculate_dominance_info	PARAMS ((int *, sbitmap *,
+						 enum cdi_direction));
+
 #endif /* _BASIC_BLOCK_H */
diff --git a/gcc/dce.c b/gcc/dce.c
index ddd2cd0..3a83d7a 100644
--- a/gcc/dce.c
+++ b/gcc/dce.c
@@ -485,7 +485,6 @@ eliminate_dead_code ()
   /* Map element (b,e) is nonzero if the block is control dependent on
      edge.  "cdbte" abbreviates control dependent block to edge.  */
   control_dependent_block_to_edge_map cdbte;
-  sbitmap *postdominators;
  /* Element I is the immediate postdominator of block I.  */
   int *pdom;
   struct edge_list *el;
@@ -504,17 +503,14 @@ eliminate_dead_code ()
   compute_bb_for_insn (max_insn_uid);
 
   /* Compute control dependence.  */
-  postdominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-  compute_flow_dominators (NULL, postdominators);
   pdom = (int *) xmalloc (n_basic_blocks * sizeof (int));
   for (i = 0; i < n_basic_blocks; ++i)
     pdom[i] = INVALID_BLOCK;
-  compute_immediate_postdominators (pdom, postdominators);
+  calculate_dominance_info (pdom, NULL, CDI_POST_DOMINATORS);
   /* Assume there is a path from each node to the exit block.  */
   for (i = 0; i < n_basic_blocks; ++i)
     if (pdom[i] == INVALID_BLOCK)
       pdom[i] = EXIT_BLOCK;
-  sbitmap_vector_free (postdominators);
   el = create_edge_list();
   find_all_control_dependences (el, pdom, cdbte);
 
diff --git a/gcc/dominance.c b/gcc/dominance.c
new file mode 100644
index 0000000..66ff11e
--- /dev/null
+++ b/gcc/dominance.c
@@ -0,0 +1,622 @@
+/* Calculate (post)dominators in slightly super-linear time.
+   Copyright (C) 2000 Free Software Foundation, Inc.
+   Contributed by Michael Matz (matz@ifh.de).
+  
+   This file is part of GNU CC.
+ 
+   GNU CC is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   GNU CC is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with GNU CC; see the file COPYING.  If not, write to
+   the Free Software Foundation, 59 Temple Place - Suite 330,
+   Boston, MA 02111-1307, 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
+   to dominate another block X, when all paths from the entry node of the CFG
+   to X go also over D.  The dominance relation is a transitive reflexive
+   relation and its minimal transitive reduction is a tree, called the
+   dominator tree.  So for each block X besides the entry block exists a
+   block I(X), called the immediate dominator of X, which is the parent of X
+   in the dominator tree.
+
+   The algorithm computes this dominator tree implicitely 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
+   slowly growing functional inverse of the Ackerman function.  */
+
+#include "config.h"
+#include "system.h"
+#include "rtl.h"
+#include "hard-reg-set.h"
+#include "basic-block.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
+   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
+   'n_basic_blocks' for that.  Its dfs number is of course 1.  */
+
+/* Type of Basic Block aka. TBB */
+typedef unsigned int TBB;
+
+/* We work in a poor-mans object oriented fashion, and carry an instance of
+   this structure through all our 'methods'.  It holds various arrays
+   reflecting the (sub)structure of the flowgraph.  Most of them are of type
+   TBB and are also indexed by TBB.  */
+
+struct dom_info
+{
+  /* The parent of a node in the DFS tree.  */
+  TBB *dfs_parent;
+  /* For a node x key[x] is roughly the node nearest to the root from which
+     exists a way to x only over nodes behind x.  Such a node is also called
+     semidominator.  */
+  TBB *key;
+  /* The value in path_min[x] is the node y on the path from x to the root of
+     the tree x is in with the smallest key[y].  */
+  TBB *path_min;
+  /* bucket[x] points to the first node of the set of nodes having x as key.  */
+  TBB *bucket;
+  /* And next_bucket[x] points to the next node.  */
+  TBB *next_bucket;
+  /* After the algorithm is done, dom[x] contains the immediate dominator
+     of x.  */
+  TBB *dom;
+
+  /* The following few fields implement the structures needed for disjoint
+     sets.  */
+  /* set_chain[x] is the next node on the path from x to the representant
+     of the set containing x.  If set_chain[x]==0 then x is a root.  */
+  TBB *set_chain;
+  /* set_size[x] is the number of elements in the set named by x.  */
+  unsigned int *set_size;
+  /* set_child[x] is used for balancing the tree representing a set.  It can
+     be understood as the next sibling of x.  */
+  TBB *set_child;
+
+  /* If b is the number of a basic block (BB->index), dfs_order[b] is the
+     number of that node in DFS order counted from 1.  This is an index
+     into most of the other arrays in this structure.  */
+  TBB *dfs_order;
+  /* If x is the DFS-index of a node which correspondends with an basic block,
+     dfs_to_bb[x] is that basic block.  Note, that in our structure there are
+     more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
+     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. */
+  unsigned int dfsnum;
+  /* The number of nodes in the DFS tree (==dfsnum-1).  */
+  unsigned int nodes;
+};
+
+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));
+static void idoms_to_doms		PARAMS ((struct dom_info *,
+						 sbitmap *));
+
+/* Helper macro for allocating and initializing an array,
+   for aesthetic reasons.  */
+#define init_ar(var, type, num, content)			\
+  do {								\
+    unsigned int i = 1;    /* Catch content == i.  */		\
+    if (! (content))						\
+      (var) = (type *) xcalloc ((num), sizeof (type));		\
+    else							\
+      {								\
+        (var) = (type *) xmalloc ((num) * sizeof (type));	\
+	for (i = 0; i < num; i++)				\
+	  (var)[i] = (content);					\
+      }								\
+  } while (0)
+
+/* Allocate all needed memory in a pessimistic fashion (so we round up).
+   This initialises the contents of DI, which already must be allocated.  */
+
+static void
+init_dom_info (di)
+     struct dom_info *di;
+{
+  /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or
+     EXIT_BLOCK.  */
+  unsigned int num = n_basic_blocks + 1 + 1;
+  init_ar (di->dfs_parent, TBB, num, 0);
+  init_ar (di->path_min, TBB, num, i);
+  init_ar (di->key, TBB, num, i);
+  init_ar (di->dom, TBB, num, 0);
+
+  init_ar (di->bucket, TBB, num, 0);
+  init_ar (di->next_bucket, TBB, num, 0);
+
+  init_ar (di->set_chain, TBB, num, 0);
+  init_ar (di->set_size, unsigned int, num, 1);
+  init_ar (di->set_child, TBB, num, 0);
+
+  init_ar (di->dfs_order, TBB, (unsigned int) n_basic_blocks + 1, 0);
+  init_ar (di->dfs_to_bb, basic_block, num, 0);
+
+  di->dfsnum = 1;
+  di->nodes = 0;
+}
+
+#undef init_ar
+
+/* Free all allocated memory in DI, but not DI itself.  */
+
+static void
+free_dom_info (di)
+     struct dom_info *di;
+{
+  free (di->dfs_parent);
+  free (di->path_min);
+  free (di->key);
+  free (di->dom);
+  free (di->bucket);
+  free (di->next_bucket);
+  free (di->set_chain);
+  free (di->set_size);
+  free (di->set_child);
+  free (di->dfs_order);
+  free (di->dfs_to_bb);
+}
+
+/* The nonrecursive variant of creating a DFS tree.  DI is our working
+   structure, BB the starting basic block for this tree and REVERSE
+   is true, if predecessors should be visited instead of successors of a
+   node.  After this is done all nodes reachable from BB were visited, have
+   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;
+{
+  /* 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;
+  int sp;
+  /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
+     problem).  */
+  basic_block en_block;
+  /* Ending block.  */
+  basic_block ex_block;
+
+  stack = (edge *) xmalloc ((n_basic_blocks + 3) * sizeof (edge));
+  sp = 0;
+
+  /* Initialize our border blocks, and the first edge.  */
+  if (reverse)
+    {
+      e = bb->pred;
+      en_block = EXIT_BLOCK_PTR;
+      ex_block = ENTRY_BLOCK_PTR;
+    }
+  else
+    {
+      e = bb->succ;
+      en_block = ENTRY_BLOCK_PTR;
+      ex_block = EXIT_BLOCK_PTR;
+    }
+
+  /* When the stack is empty we break out of this loop.  */
+  while (1)
+    {
+      basic_block bn;
+
+      /* This loop traverses edges e in depth first manner, and fills the
+         stack.  */
+      while (e)
+	{
+	  edge e_next;
+
+	  /* Deduce from E the current and the next block (BB and BN), and the
+	     next edge.  */
+	  if (reverse)
+	    {
+	      bn = e->src;
+
+	      /* If the next node BN is either already visited or a border
+	         block the current edge is useless, and simply overwritten
+	         with the next edge out of the current node.  */
+	      if (di->dfs_order[bn->index] || bn == ex_block)
+		{
+		  e = e->pred_next;
+		  continue;
+		}
+	      bb = e->dest;
+	      e_next = bn->pred;
+	    }
+	  else
+	    {
+	      bn = e->dest;
+	      if (di->dfs_order[bn->index] || bn == ex_block)
+		{
+		  e = e->succ_next;
+		  continue;
+		}
+	      bb = e->src;
+	      e_next = bn->succ;
+	    }
+
+	  if (bn == en_block)
+	    abort ();
+
+	  /* Fill the DFS tree info calculatable _before_ recursing.  */
+	  if (bb != en_block)
+	    my_i = di->dfs_order[bb->index];
+	  else
+	    my_i = di->dfs_order[n_basic_blocks];
+	  child_i = di->dfs_order[bn->index] = di->dfsnum++;
+	  di->dfs_to_bb[child_i] = bn;
+	  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;
+	}
+
+      if (!sp)
+	break;
+      e = stack[--sp];
+
+      /* OK.  The edge-list was exhausted, meaning normally we would
+         end the recursion.  After returning from the recursive call,
+         there were (may be) other statements which were run after a
+         child node was completely considered by DFS.  Here is the
+         point to do it in the non-recursive variant.
+         E.g. The block just completed is in e->dest for forward DFS,
+         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;
+    }
+  free (stack);
+}
+
+/* The main entry for calculating the DFS tree or forest.  DI is our working
+   structure and REVERSE is true, if we are interested in the reverse flow
+   graph.  In that case the result is not necessarily a tree but a forest,
+   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;
+{
+  /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE).  */
+  basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
+  di->dfs_order[n_basic_blocks] = di->dfsnum;
+  di->dfs_to_bb[di->dfsnum] = begin;
+  di->dfsnum++;
+
+  calc_dfs_tree_nonrec (di, begin, reverse);
+
+  if (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.  */
+      int i;
+      for (i = n_basic_blocks - 1; i >= 0; i--)
+	{
+	  basic_block b = BASIC_BLOCK (i);
+	  if (di->dfs_order[b->index])
+	    continue;
+	  di->dfs_order[b->index] = di->dfsnum;
+	  di->dfs_to_bb[di->dfsnum] = b;
+	  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 ();
+}
+
+/* Compress the path from V to the root of its set and update path_min at the
+   same time.  After compress(di, V) set_chain[V] is the root of the set V is
+   in and path_min[V] is the node with the smallest key[] value on the path
+   from V to that root.  */
+
+static void
+compress (di, v)
+     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).
+     Also performance wise compress() ranges _far_ behind eval().  */
+  TBB parent = di->set_chain[v];
+  if (di->set_chain[parent])
+    {
+      compress (di, parent);
+      if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
+	di->path_min[v] = di->path_min[parent];
+      di->set_chain[v] = di->set_chain[parent];
+    }
+}
+
+/* Compress the path from V to the set root of V if needed (when the root has
+   changed since the last call).  Returns the node with the smallest key[]
+   value on the path from V to the root.  */
+
+static inline TBB
+eval (di, v)
+     struct dom_info *di;
+     TBB v;
+{
+  /* The representant of the set V is in, also called root (as the set
+     representation is a tree).  */
+  TBB rep = di->set_chain[v];
+
+  /* V itself is the root.  */
+  if (!rep)
+    return di->path_min[v];
+
+  /* Compress only if necessary.  */
+  if (di->set_chain[rep])
+    {
+      compress (di, v);
+      rep = di->set_chain[v];
+    }
+
+  if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
+    return di->path_min[v];
+  else
+    return di->path_min[rep];
+}
+
+/* This essentially merges the two sets of V and W, giving a single set with
+   the new root V.  The internal representation of these disjoint sets is a
+   balanced tree.  Currently link(V,W) is only used with V being the parent
+   of W.  */
+
+static void
+link_roots (di, v, w)
+     struct dom_info *di;
+     TBB v, w;
+{
+  TBB s = w;
+
+  /* Rebalance the tree.  */
+  while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]])
+    {
+      if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]]
+	  >= 2 * di->set_size[di->set_child[s]])
+	{
+	  di->set_chain[di->set_child[s]] = s;
+	  di->set_child[s] = di->set_child[di->set_child[s]];
+	}
+      else
+	{
+	  di->set_size[di->set_child[s]] = di->set_size[s];
+	  s = di->set_chain[s] = di->set_child[s];
+	}
+    }
+
+  di->path_min[s] = di->path_min[w];
+  di->set_size[v] += di->set_size[w];
+  if (di->set_size[v] < 2 * di->set_size[w])
+    {
+      TBB tmp = s;
+      s = di->set_child[v];
+      di->set_child[v] = tmp;
+    }
+
+  /* Merge all subtrees.  */
+  while (s)
+    {
+      di->set_chain[s] = v;
+      s = di->set_child[s];
+    }
+}
+
+/* This calculates the immediate dominators (or post-dominators if REVERSE is
+   true).  DI is our working structure and should hold the DFS forest.
+   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;
+{
+  TBB v, w, k, par;
+  basic_block en_block;
+  if (reverse)
+    en_block = EXIT_BLOCK_PTR;
+  else
+    en_block = ENTRY_BLOCK_PTR;
+
+  /* Go backwards in DFS order, to first look at the leafs.  */
+  v = di->nodes;
+  while (v > 1)
+    {
+      basic_block bb = di->dfs_to_bb[v];
+      edge e, e_next;
+
+      par = di->dfs_parent[v];
+      k = v;
+      if (reverse)
+	e = bb->succ;
+      else
+	e = bb->pred;
+
+      /* 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)
+	{
+	  TBB k1;
+	  basic_block b;
+
+	  if (reverse)
+	    {
+	      b = e->dest;
+	      e_next = e->succ_next;
+	    }
+	  else
+	    {
+	      b = e->src;
+	      e_next = e->pred_next;
+	    }
+	  if (b == en_block)
+	    k1 = di->dfs_order[n_basic_blocks];
+	  else
+	    k1 = di->dfs_order[b->index];
+
+	  /* Call eval() only if really needed.  If k1 is above V in DFS tree,
+	     then we know, that eval(k1) == k1 and key[k1] == k1.  */
+	  if (k1 > v)
+	    k1 = di->key[eval (di, k1)];
+	  if (k1 < k)
+	    k = k1;
+	}
+
+      di->key[v] = k;
+      link_roots (di, par, v);
+      di->next_bucket[v] = di->bucket[k];
+      di->bucket[k] = v;
+
+      /* Transform semidominators into dominators.  */
+      for (w = di->bucket[par]; w; w = di->next_bucket[w])
+	{
+	  k = eval (di, w);
+	  if (di->key[k] < di->key[w])
+	    di->dom[w] = k;
+	  else
+	    di->dom[w] = par;
+	}
+      /* We don't need to cleanup next_bucket[].  */
+      di->bucket[par] = 0;
+      v--;
+    }
+
+  /* Explicitely define the dominators.  */
+  di->dom[1] = 0;
+  for (v = 2; v <= di->nodes; v++)
+    if (di->dom[v] != di->key[v])
+      di->dom[v] = di->dom[di->dom[v]];
+}
+
+/* Convert the information about immediate dominators (in DI) to sets of all
+   dominators (in DOMINATORS).  */
+
+static void
+idoms_to_doms (di, dominators)
+     struct dom_info *di;
+     sbitmap *dominators;
+{
+  TBB i, e_index;
+  int bb, bb_idom;
+  sbitmap_vector_zero (dominators, n_basic_blocks);
+  /* We have to be careful, to not include the ENTRY_BLOCK or EXIT_BLOCK
+     in the list of (post)-doms, so remember that in e_index.  */
+  e_index = di->dfs_order[n_basic_blocks];
+
+  for (i = 1; i <= di->nodes; i++)
+    {
+      if (i == e_index)
+	continue;
+      bb = di->dfs_to_bb[i]->index;
+
+      if (di->dom[i] && (di->dom[i] != e_index))
+	{
+	  bb_idom = di->dfs_to_bb[di->dom[i]]->index;
+	  sbitmap_copy (dominators[bb], dominators[bb_idom]);
+	}
+      else
+	{
+	  /* It has no immediate dom or only ENTRY_BLOCK or EXIT_BLOCK.
+	     If it is a child of ENTRY_BLOCK that's OK, and it's only
+	     dominated by itself; if it's _not_ a child of ENTRY_BLOCK, it
+	     means, it is unreachable.  That case has been disallowed in the
+	     building of the DFS tree, so we are save here.  For the reverse
+	     flow graph it means, it has no children, so, to be compatible
+	     with the old code, we set the post_dominators to all one.  */
+	  if (!di->dom[i])
+	    {
+	      sbitmap_ones (dominators[bb]);
+	    }
+	}
+      SET_BIT (dominators[bb], bb);
+    }
+}
+
+/* The main entry point into this module.  IDOM is an integer array with room
+   for n_basic_blocks integers, DOMS is a preallocated sbitmap array having
+   room for n_basic_blocks^2 bits, and POST is true if the caller wants to
+   know post-dominators.
+
+   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.
+
+   Either IDOM or DOMS may be NULL (meaning the caller is not interested in
+   immediate resp. all dominators).  */
+
+void
+calculate_dominance_info (idom, doms, reverse)
+     int *idom;
+     sbitmap *doms;
+     enum cdi_direction reverse;
+{
+  struct dom_info di;
+
+  if (!doms && !idom)
+    return;
+  init_dom_info (&di);
+  calc_dfs_tree (&di, reverse);
+  calc_idoms (&di, reverse);
+
+  if (idom)
+    {
+      int i;
+      for (i = 0; i < n_basic_blocks; i++)
+	{
+	  basic_block b = BASIC_BLOCK (i);
+	  TBB d = di.dom[di.dfs_order[b->index]];
+
+	  /* The old code didn't modify array elements of nodes having only
+	     itself as dominator (d==0) or only ENTRY_BLOCK (resp. EXIT_BLOCK)
+	     (d==1).  */
+	  if (d > 1)
+	    idom[i] = di.dfs_to_bb[d]->index;
+	}
+    }
+  if (doms)
+    idoms_to_doms (&di, doms);
+
+  free_dom_info (&di);
+}
diff --git a/gcc/flow.c b/gcc/flow.c
index 4fc8ac3..23f3236 100644
--- a/gcc/flow.c
+++ b/gcc/flow.c
@@ -6247,250 +6247,6 @@ print_rtl_with_bb (outf, rtx_first)
     }
 }
 
-/* Compute dominator relationships using new flow graph structures.  */
-
-void
-compute_flow_dominators (dominators, post_dominators)
-     sbitmap *dominators;
-     sbitmap *post_dominators;
-{
-  int bb;
-  sbitmap *temp_bitmap;
-  edge e;
-  basic_block *worklist, *workend, *qin, *qout;
-  int qlen;
-
-  /* Allocate a worklist array/queue.  Entries are only added to the
-     list if they were not already on the list.  So the size is
-     bounded by the number of basic blocks.  */
-  worklist = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
-  workend = &worklist[n_basic_blocks];
-
-  temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-  sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
-
-  if (dominators)
-    {
-      /* The optimistic setting of dominators requires us to put every
-	 block on the work list initially.  */
-      qin = qout = worklist;
-      for (bb = 0; bb < n_basic_blocks; bb++)
-	{
-	  *qin++ = BASIC_BLOCK (bb);
-	  BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
-	}
-      qlen = n_basic_blocks;
-      qin = worklist;
-
-      /* We want a maximal solution, so initially assume everything dominates
-	 everything else.  */
-      sbitmap_vector_ones (dominators, n_basic_blocks);
-
-      /* Mark successors of the entry block so we can identify them below.  */
-      for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
-	e->dest->aux = ENTRY_BLOCK_PTR;
-
-      /* Iterate until the worklist is empty.  */
-      while (qlen)
-	{
-	  /* Take the first entry off the worklist.  */
-	  basic_block b = *qout++;
-	  if (qout >= workend)
-	    qout = worklist;
-	  qlen--;
-
-	  bb = b->index;
-
-	  /* Compute the intersection of the dominators of all the
-	     predecessor blocks.
-
-	     If one of the predecessor blocks is the ENTRY block, then the
-	     intersection of the dominators of the predecessor blocks is
-	     defined as the null set.  We can identify such blocks by the
-	     special value in the AUX field in the block structure.  */
-	  if (b->aux == ENTRY_BLOCK_PTR)
-	    {
-	      /* Do not clear the aux field for blocks which are
-		 successors of the ENTRY block.  That way we never add
-		 them to the worklist again.
-
-		 The intersect of dominators of the preds of this block is
-		 defined as the null set.  */
-	      sbitmap_zero (temp_bitmap[bb]);
-	    }
-	  else
-	    {
-	      /* Clear the aux field of this block so it can be added to
-		 the worklist again if necessary.  */
-	      b->aux = NULL;
-	      sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
-	    }
-
-	  /* Make sure each block always dominates itself.  */
-	  SET_BIT (temp_bitmap[bb], bb);
-
-	  /* If the out state of this block changed, then we need to
-	     add the successors of this block to the worklist if they
-	     are not already on the worklist.  */
-	  if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb]))
-	    {
-	      for (e = b->succ; e; e = e->succ_next)
-		{
-		  if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
-		    {
-		      *qin++ = e->dest;
-		      if (qin >= workend)
-			qin = worklist;
-		      qlen++;
-
-		      e->dest->aux = e;
-		    }
-		}
-	    }
-	}
-    }
-
-  if (post_dominators)
-    {
-      /* The optimistic setting of dominators requires us to put every
-	 block on the work list initially.  */
-      qin = qout = worklist;
-      for (bb = 0; bb < n_basic_blocks; bb++)
-	{
-	  *qin++ = BASIC_BLOCK (bb);
-	  BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
-	}
-      qlen = n_basic_blocks;
-      qin = worklist;
-
-      /* We want a maximal solution, so initially assume everything post
-	 dominates everything else.  */
-      sbitmap_vector_ones (post_dominators, n_basic_blocks);
-
-      /* Mark predecessors of the exit block so we can identify them below.  */
-      for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
-	e->src->aux = EXIT_BLOCK_PTR;
-
-      /* Iterate until the worklist is empty.  */
-      while (qlen)
-	{
-	  /* Take the first entry off the worklist.  */
-	  basic_block b = *qout++;
-	  if (qout >= workend)
-	    qout = worklist;
-	  qlen--;
-
-	  bb = b->index;
-
-	  /* Compute the intersection of the post dominators of all the
-	     successor blocks.
-
-	     If one of the successor blocks is the EXIT block, then the
-	     intersection of the dominators of the successor blocks is
-	     defined as the null set.  We can identify such blocks by the
-	     special value in the AUX field in the block structure.  */
-	  if (b->aux == EXIT_BLOCK_PTR)
-	    {
-	      /* Do not clear the aux field for blocks which are
-		 predecessors of the EXIT block.  That way we we never
-		 add them to the worklist again.
-
-		 The intersect of dominators of the succs of this block is
-		 defined as the null set.  */
-	      sbitmap_zero (temp_bitmap[bb]);
-	    }
-	  else
-	    {
-	      /* Clear the aux field of this block so it can be added to
-		 the worklist again if necessary.  */
-	      b->aux = NULL;
-	      sbitmap_intersection_of_succs (temp_bitmap[bb],
-					     post_dominators, bb);
-	    }
-
-	  /* Make sure each block always post dominates itself.  */
-	  SET_BIT (temp_bitmap[bb], bb);
-
-	  /* If the out state of this block changed, then we need to
-	     add the successors of this block to the worklist if they
-	     are not already on the worklist.  */
-	  if (sbitmap_a_and_b (post_dominators[bb],
-			       post_dominators[bb],
-			       temp_bitmap[bb]))
-	    {
-	      for (e = b->pred; e; e = e->pred_next)
-		{
-		  if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
-		    {
-		      *qin++ = e->src;
-		      if (qin >= workend)
-			qin = worklist;
-		      qlen++;
-
-		      e->src->aux = e;
-		    }
-		}
-	    }
-	}
-    }
-
-  free (worklist);
-  free (temp_bitmap);
-}
-
-/* Given DOMINATORS, compute the immediate dominators into IDOM.  If a
-   block dominates only itself, its entry remains as INVALID_BLOCK.  */
-
-void
-compute_immediate_dominators (idom, dominators)
-     int *idom;
-     sbitmap *dominators;
-{
-  sbitmap *tmp;
-  int b;
-
-  tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-
-  /* Begin with tmp(n) = dom(n) - { n }.  */
-  for (b = n_basic_blocks; --b >= 0;)
-    {
-      sbitmap_copy (tmp[b], dominators[b]);
-      RESET_BIT (tmp[b], b);
-    }
-
-  /* Subtract out all of our dominator's dominators.  */
-  for (b = n_basic_blocks; --b >= 0;)
-    {
-      sbitmap tmp_b = tmp[b];
-      int s;
-
-      for (s = n_basic_blocks; --s >= 0;)
-	if (TEST_BIT (tmp_b, s))
-	  sbitmap_difference (tmp_b, tmp_b, tmp[s]);
-    }
-
-  /* Find the one bit set in the bitmap and put it in the output array.  */
-  for (b = n_basic_blocks; --b >= 0;)
-    {
-      int t;
-      EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
-    }
-
-  sbitmap_vector_free (tmp);
-}
-
-/* Given POSTDOMINATORS, compute the immediate postdominators into
-   IDOM.  If a block is only dominated by itself, its entry remains as
-   INVALID_BLOCK.  */
-
-void
-compute_immediate_postdominators (idom, postdominators)
-     int *idom;
-     sbitmap *postdominators;
-{
-  compute_immediate_dominators (idom, postdominators);
-}
-
 /* Recompute register set/reference counts immediately prior to register
    allocation.
 
@@ -8151,7 +7907,7 @@ flow_loops_find (loops, flags)
 
   /* Compute the dominators.  */
   dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-  compute_flow_dominators (dom, NULL);
+  calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
 
   /* Count the number of loop edges (back edges).  This should be the
      same as the number of natural loops.  */
diff --git a/gcc/gcse.c b/gcc/gcse.c
index 2938597..ac87c93 100644
--- a/gcc/gcse.c
+++ b/gcc/gcse.c
@@ -5292,7 +5292,7 @@ compute_code_hoist_data ()
   compute_local_properties (transp, comp, antloc, 0);
   compute_transpout ();
   compute_code_hoist_vbeinout ();
-  compute_flow_dominators (dominators, NULL);
+  calculate_dominance_info (NULL, dominators, CDI_DOMINATORS);
   if (gcse_file)
     fprintf (gcse_file, "\n");
 }
diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index 2ab6377..01f08b5 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -7001,10 +7001,8 @@ schedule_insns (dump_file)
 	     so may even be beneficial.  */
 	  edge_list = create_edge_list ();
 
-	  /* Compute the dominators and post dominators.  We don't
-	     currently use post dominators, but we should for
-	     speculative motion analysis.  */
-	  compute_flow_dominators (dom, NULL);
+	  /* Compute the dominators and post dominators.  */
+	  calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
 
 	  /* build_control_flow will return nonzero if it detects unreachable
 	     blocks or any other irregularity with the cfg which prevents
diff --git a/gcc/ifcvt.c b/gcc/ifcvt.c
index 3ca0e6c..6ad1d35 100644
--- a/gcc/ifcvt.c
+++ b/gcc/ifcvt.c
@@ -2104,7 +2104,7 @@ if_convert (life_data_ok)
   if (HAVE_conditional_execution || life_data_ok)
     {
       post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-      compute_flow_dominators (NULL, post_dominators);
+      calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
     }
 
   /* Record initial block numbers.  */
diff --git a/gcc/ssa.c b/gcc/ssa.c
index 0bc6dc8..3dabc62 100644
--- a/gcc/ssa.c
+++ b/gcc/ssa.c
@@ -1148,7 +1148,6 @@ convert_to_ssa ()
   sbitmap *evals;
 
   /* Dominator bitmaps.  */
-  sbitmap *dominators;
   sbitmap *dfs;
   sbitmap *idfs;
 
@@ -1164,15 +1163,9 @@ convert_to_ssa ()
   /* Need global_live_at_{start,end} up to date.  */
   life_analysis (get_insns (), NULL, PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE);
 
-  /* Compute dominators.  */
-  dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-  compute_flow_dominators (dominators, NULL);
-
   idom = (int *) alloca (n_basic_blocks * sizeof (int));
   memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int));
-  compute_immediate_dominators (idom, dominators);
-
-  sbitmap_vector_free (dominators);
+  calculate_dominance_info (idom, NULL, CDI_DOMINATORS);
 
   if (rtl_dump_file)
     {