Mon Jun 10 20:42:34 CEST 2002 Jan Hubicka <jh@suse.cz>

	* basic-block.h: Do not include et-forest.h
	(dominance_info): Declare as struct dominance-info.
	* cfglayout.c (cleanup_unconditional_jumps): Remove the edge before
	deleting block.
	* dominance.c (struct dominance_info): Define.
	(BB_NODE, SET_BB_NODE): New macros.
	(bb_hash_func, bb_eq_func): Kill.
	(calculate_dominace_info, free_dominacne_info, set_immediate_dominator,
	nearest_common_dominator, dominated_by_p, recount_dominator,
	add_to_dominance_info, delete_from_dominance_info): update for new
	representation.
	(get_dominated_by, redirect_immediate_dominators): Rewrite using
	enumerate_sons.
	* ifcvt.c (process_double_test_block, merge_if_block, find_cond_trap,
	find_if_case_1, find_if_case_2): Remove killed blocks from dominance
	structure.

	* et-forest.h: Update copyright; revamp all function to operate on
	nodes
	(et_forest_value): Kill.
	(et_forest_enumerate_sons, et_forest_node_value): New.
	* et-forest.c: Update copyright.
	* et-forest.h: Update copyright; revamp all function to operate on
	nodes
	(et_forest_value): Kill.
	(et_forest_enumerate_sons, et_forest_node_value): New.

	Thu Jun  6 22:43:43 CEST 2002  Jan Hubicka  <jh@suse.cz>

	* basic-block.h: Inlude et-forest.h
	(basic_block_def): Kill dominator.
	(dominance_info): New type.
	(loops): Use dominace_info.
	(dominace handling functions): Take dominace_info as argument
	instead of bitmaps.
	(create_preheader): Likewise.
	* cfg.c (entry_exit_blocks): Kill dominator.
	(dump_flow_info): Do not dump dominators.
	* cfglayout.c (cleanup_unconditonal_jumps): Delete deleted block from
	dominators.
	* cfgloop.c (flow_pre_header_find): Use dominacne_info.
	(flow_loops_pre_header_scan, make_forwarder_block,
	canonicale_loop_headers, flow_loops_find): Likewise.
	* dominance.c: Include error.h
	(idoms_to_doms): Kill.
	(bb_hash_func, bb_eq_func): New static functions.
	(debug_dominace_info): New global function.
	(calculate_dominance_info): Use new et forest structure.
	(free_dominace_info, get_immediate_dominator, set_immediate_dominator,
	get_dominated_by, redirect_immediate_dominators,
	nearest_common_dominator, dominated_by_p, verify_dominators,
	recount_dominator, iterate_fix_dominators, add_to_dominace_info,
	delete_from_dominance_info): New global functions.
	* gcse.c (domnators): CHange to dominance_info.
	(alloc_hoist_mem): Do not alloc dominators
	(free_code_hoist_mem): Use free_dominance_info.
	(compute_code_hoist_data): Use dominance_info.
	(hoist_code): Likewise.
	* ifcvt.c (post_dominators): Likewise.
	(find_if_case_2, if_convert): Likewise.
	* predict.c (process_note_predictions, process_note_prediction,
	estimate-probability): Likewise.
	* sched-rgn.c (find_rgns, init_regions): Likewise.
	* ssa-dce.c (find_all_control_dependences, fint_control_depemndence,
	find_pdom, delete_insn_bb, ssa_eliminate_dead_code): Likewise.
	* ssa.c (compute_dominance_frontiers_1, rename_block, rename_registers,
	find_evaluations, convert_to_ssa): Likewise.
	* ssa.h (compute_dominance_frontiers): Likewise.

	Thu Jun  6 22:57:34 CEST 2002  Pavel Nejedly <bim@atrey.karlin.mff.cuni.cz>

	* Makefile.in (et-forest.c): Add.
	* et-forest.c: New file.
	* at-forest.h: New file.


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

12 files changed, 478 insertions, 183 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index f3796e22084..3394b045365 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,83 @@
+Thu Jun 20 19:42:21 CEST 2002  Jan Hubicka  <jh@suse.cz>
+			       Pavel Nejedly  <bim@atrey.karlin.mff.cuni.cz>
+
+	Mon Jun 10 20:42:34 CEST 2002  Jan Hubicka  <jh@suse.cz>
+
+	* basic-block.h: Do not include et-forest.h
+	(dominance_info): Declare as struct dominance-info.
+	* cfglayout.c (cleanup_unconditional_jumps): Remove the edge before
+	deleting block.
+	* dominance.c (struct dominance_info): Define.
+	(BB_NODE, SET_BB_NODE): New macros.
+	(bb_hash_func, bb_eq_func): Kill.
+	(calculate_dominace_info, free_dominacne_info, set_immediate_dominator,
+	nearest_common_dominator, dominated_by_p, recount_dominator,
+	add_to_dominance_info, delete_from_dominance_info): update for new
+	representation.
+	(get_dominated_by, redirect_immediate_dominators): Rewrite using
+	enumerate_sons.
+	* ifcvt.c (process_double_test_block, merge_if_block, find_cond_trap,
+	find_if_case_1, find_if_case_2): Remove killed blocks from dominance
+	structure.
+
+	* et-forest.h: Update copyright; revamp all function to operate on
+	nodes
+	(et_forest_value): Kill.
+	(et_forest_enumerate_sons, et_forest_node_value): New.
+	* et-forest.c: Update copyright.
+	* et-forest.h: Update copyright; revamp all function to operate on
+	nodes
+	(et_forest_value): Kill.
+	(et_forest_enumerate_sons, et_forest_node_value): New.
+
+	Thu Jun  6 22:43:43 CEST 2002  Jan Hubicka  <jh@suse.cz>
+
+	* basic-block.h: Inlude et-forest.h
+	(basic_block_def): Kill dominator.
+	(dominance_info): New type.
+	(loops): Use dominace_info.
+	(dominace handling functions): Take dominace_info as argument
+	instead of bitmaps.
+	(create_preheader): Likewise.
+	* cfg.c (entry_exit_blocks): Kill dominator.
+	(dump_flow_info): Do not dump dominators.
+	* cfglayout.c (cleanup_unconditonal_jumps): Delete deleted block from
+	dominators.
+	* cfgloop.c (flow_pre_header_find): Use dominacne_info.
+	(flow_loops_pre_header_scan, make_forwarder_block,
+	canonicale_loop_headers, flow_loops_find): Likewise.
+	* dominance.c: Include error.h
+	(idoms_to_doms): Kill.
+	(bb_hash_func, bb_eq_func): New static functions.
+	(debug_dominace_info): New global function.
+	(calculate_dominance_info): Use new et forest structure.
+	(free_dominace_info, get_immediate_dominator, set_immediate_dominator,
+	get_dominated_by, redirect_immediate_dominators,
+	nearest_common_dominator, dominated_by_p, verify_dominators,
+	recount_dominator, iterate_fix_dominators, add_to_dominace_info,
+	delete_from_dominance_info): New global functions.
+	* gcse.c (domnators): CHange to dominance_info.
+	(alloc_hoist_mem): Do not alloc dominators
+	(free_code_hoist_mem): Use free_dominance_info.
+	(compute_code_hoist_data): Use dominance_info.
+	(hoist_code): Likewise.
+	* ifcvt.c (post_dominators): Likewise.
+	(find_if_case_2, if_convert): Likewise.
+	* predict.c (process_note_predictions, process_note_prediction,
+	estimate-probability): Likewise.
+	* sched-rgn.c (find_rgns, init_regions): Likewise.
+	* ssa-dce.c (find_all_control_dependences, fint_control_depemndence,
+	find_pdom, delete_insn_bb, ssa_eliminate_dead_code): Likewise.
+	* ssa.c (compute_dominance_frontiers_1, rename_block, rename_registers,
+	find_evaluations, convert_to_ssa): Likewise.
+	* ssa.h (compute_dominance_frontiers): Likewise.
+
+	Thu Jun  6 22:57:34 CEST 2002  Pavel Nejedly <bim@atrey.karlin.mff.cuni.cz>
+
+	* Makefile.in (et-forest.c): Add.
+	* et-forest.c: New file.
+	* at-forest.h: New file.
+
 2002-06-20  Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>
 
 	* c-decl.c (c_decode_option): Use ARRAY_SIZE in lieu of explicit
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 46d42530b8f..07a3b8c1808 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -736,7 +736,7 @@ OBJS = alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	   \
  sibcall.o simplify-rtx.o ssa.o ssa-ccp.o ssa-dce.o stmt.o		   \
  stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
  tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
- $(GGC) $(out_object_file) $(EXTRA_OBJS)
+ et-forest.o $(GGC) $(out_object_file) $(EXTRA_OBJS)
 
 BACKEND = main.o libbackend.a
 
@@ -1543,7 +1543,8 @@ cfgcleanup.o : cfgcleanup.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TIMEVAR_H)\
 cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
    $(BASIC_BLOCK_H) hard-reg-set.h
 dominance.o : dominance.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) hard-reg-set.h \
-   $(BASIC_BLOCK_H)
+   $(BASIC_BLOCK_H) et-forest.h
+et-forest.o : et-forest.c $(CONFIG_H) $(SYSTEM_H) et-forest.h
 combine.o : combine.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h function.h \
    insn-config.h $(INSN_ATTR_H) $(REGS_H) $(EXPR_H) \
    $(BASIC_BLOCK_H) $(RECOG_H) real.h hard-reg-set.h toplev.h $(TM_P_H)
diff --git a/gcc/basic-block.h b/gcc/basic-block.h
index e50c020dc55..9e3e7a54683 100644
--- a/gcc/basic-block.h
+++ b/gcc/basic-block.h
@@ -350,6 +350,10 @@ extern void clear_edges			PARAMS ((void));
 extern void mark_critical_edges		PARAMS ((void));
 extern rtx first_insn_after_basic_block_note	PARAMS ((basic_block));
 
+/* Dominator information for basic blocks.  */
+
+typedef struct dominance_info *dominance_info;
+
 /* Structure to hold information for each natural loop.  */
 struct loop
 {
@@ -498,7 +502,7 @@ struct loops
   struct cfg
   {
     /* The bitmap vector of dominators or NULL if not computed.  */
-    sbitmap *dom;
+    dominance_info dom;
 
     /* The ordering of the basic blocks in a depth first search.  */
     int *dfs_order;
@@ -770,7 +774,21 @@ enum cdi_direction
   CDI_POST_DOMINATORS
 };
 
-extern void calculate_dominance_info	PARAMS ((int *, sbitmap *,
-						 enum cdi_direction));
-
+extern dominance_info calculate_dominance_info	PARAMS ((enum cdi_direction));
+extern void free_dominance_info			PARAMS ((dominance_info));
+extern basic_block nearest_common_dominator	PARAMS ((dominance_info,
+						 basic_block, basic_block));
+extern void set_immediate_dominator	PARAMS ((dominance_info,
+						 basic_block, basic_block));
+extern basic_block get_immediate_dominator	PARAMS ((dominance_info,
+						 basic_block));
+extern bool dominated_by_p	PARAMS ((dominance_info, basic_block, basic_block));
+extern int get_dominated_by PARAMS ((dominance_info, basic_block, basic_block **));
+extern void add_to_dominance_info PARAMS ((dominance_info, basic_block));
+extern void delete_from_dominance_info PARAMS ((dominance_info, basic_block));
+basic_block recount_dominator PARAMS ((dominance_info, basic_block));
+extern void redirect_immediate_dominators PARAMS ((dominance_info, basic_block,
+						 basic_block));
+void iterate_fix_dominators PARAMS ((dominance_info, basic_block *, int));
+extern void verify_dominators PARAMS ((dominance_info));
 #endif /* GCC_BASIC_BLOCK_H */
diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c
index e5cc41b4131..09a1fb24a1e 100644
--- a/gcc/cfgloop.c
+++ b/gcc/cfgloop.c
@@ -36,7 +36,7 @@ static void flow_loop_exit_edges_find	PARAMS ((struct loop *));
 static int flow_loop_nodes_find		PARAMS ((basic_block, struct loop *));
 static void flow_loop_pre_header_scan	PARAMS ((struct loop *));
 static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
-						      const sbitmap *));
+						      dominance_info));
 static int flow_loop_level_compute	PARAMS ((struct loop *));
 static int flow_loops_level_compute	PARAMS ((struct loops *));
 static basic_block make_forwarder_block PARAMS ((basic_block, int, int,
@@ -224,7 +224,7 @@ flow_loops_free (loops)
       loops->parray = NULL;
 
       if (loops->cfg.dom)
-	sbitmap_vector_free (loops->cfg.dom);
+	free_dominance_info (loops->cfg.dom);
 
       if (loops->cfg.dfs_order)
 	free (loops->cfg.dfs_order);
@@ -415,7 +415,7 @@ flow_loop_pre_header_scan (loop)
 static basic_block
 flow_loop_pre_header_find (header, dom)
      basic_block header;
-     const sbitmap *dom;
+     dominance_info dom;
 {
   basic_block pre_header;
   edge e;
@@ -428,7 +428,7 @@ flow_loop_pre_header_find (header, dom)
       basic_block node = e->src;
 
       if (node != ENTRY_BLOCK_PTR
-	  && ! TEST_BIT (dom[node->index], header->index))
+	  && ! dominated_by_p (dom, node, header))
 	{
 	  if (pre_header == NULL)
 	    pre_header = node;
@@ -645,13 +645,12 @@ make_forwarder_block (bb, redirect_latch, redirect_nonlatch, except,
 static void
 canonicalize_loop_headers ()
 {
-  sbitmap *dom;
+  dominance_info dom;
   basic_block header;
   edge e;
   
   /* Compute the dominators.  */
-  dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
-  calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
+  dom = calculate_dominance_info (CDI_DOMINATORS);
 
   alloc_aux_for_blocks (sizeof (int));
   alloc_aux_for_edges (sizeof (int));
@@ -670,7 +669,7 @@ canonicalize_loop_headers ()
 	    have_abnormal_edge = 1;
 
 	  if (latch != ENTRY_BLOCK_PTR
-	      && TEST_BIT (dom[latch->index], header->index))
+	      && dominated_by_p (dom, latch, header))
 	    {
 	      num_latches++;
 	      LATCH_EDGE (e) = 1;
@@ -747,7 +746,7 @@ canonicalize_loop_headers ()
 
   free_aux_for_blocks ();
   free_aux_for_edges ();
-  sbitmap_vector_free (dom);
+  free_dominance_info (dom);
 }
 
 /* Find all the natural loops in the function and save in LOOPS structure and
@@ -765,10 +764,11 @@ flow_loops_find (loops, flags)
   int num_loops;
   edge e;
   sbitmap headers;
-  sbitmap *dom;
+  dominance_info dom;
   int *dfs_order;
   int *rc_order;
-  basic_block header, bb;
+  basic_block header;
+  basic_block bb;
 
   /* This function cannot be repeatedly called with different
      flags to build up the loop information.  The loop tree
@@ -790,8 +790,7 @@ flow_loops_find (loops, flags)
   canonicalize_loop_headers ();
 
   /* Compute the dominators.  */
-  loops->cfg.dom = dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
-  calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
+  dom = loops->cfg.dom = calculate_dominance_info (CDI_DOMINATORS);
 
   /* Count the number of loop headers.  This should be the
      same as the number of natural loops.  */
@@ -824,8 +823,7 @@ flow_loops_find (loops, flags)
 	     node (header) that dominates all the nodes in the
 	     loop.  It also has single back edge to the header
 	     from a latch node.  */
-	  if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index],
-						    header->index))
+	  if (latch != ENTRY_BLOCK_PTR && dominated_by_p (dom, latch, header))
 	    {
 	      /* Shared headers should be eliminated by now.  */
 	      if (more_latches)
@@ -899,7 +897,7 @@ flow_loops_find (loops, flags)
 	      basic_block latch = e->src;
 
 	      if (latch != ENTRY_BLOCK_PTR
-		  && TEST_BIT (dom[latch->index], header->index))
+		  && dominated_by_p (dom, latch, header))
 		{
 		  loop->latch = latch;
 		  break;
@@ -925,7 +923,7 @@ flow_loops_find (loops, flags)
   else
     {
       loops->cfg.dom = NULL;
-      sbitmap_vector_free (dom);
+      free_dominance_info (dom);
     }
 #ifdef ENABLE_CHECKING
   verify_flow_info ();
diff --git a/gcc/dominance.c b/gcc/dominance.c
index 0ba90dbad68..d080957eb46 100644
--- a/gcc/dominance.c
+++ b/gcc/dominance.c
@@ -38,7 +38,19 @@
 #include "rtl.h"
 #include "hard-reg-set.h"
 #include "basic-block.h"
+#include "error.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))
 
 /* 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
@@ -113,8 +125,7 @@ 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 *));
+void debug_dominance_info		PARAMS ((dominance_info));
 
 /* Helper macro for allocating and initializing an array,
    for aesthetic reasons.  */
@@ -531,50 +542,6 @@ calc_idoms (di, reverse)
       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, last_basic_block);
-  /* 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[last_basic_block];
-
-  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 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
@@ -587,37 +554,259 @@ idoms_to_doms (di, dominators)
    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;
+dominance_info
+calculate_dominance_info (reverse)
      enum cdi_direction reverse;
 {
   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");
+
+  /* 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 (!doms && !idom)
-    return;
   init_dom_info (&di);
   calc_dfs_tree (&di, reverse);
   calc_idoms (&di, reverse);
 
-  if (idom)
+
+  FOR_EACH_BB (b)
     {
-      basic_block b;
+      TBB d = di.dom[di.dfs_order[b->index]];
 
-      FOR_EACH_BB (b)
+      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);
+  return info;
+}
+
+/* Free dominance information.  */
+void
+free_dominance_info (info)
+     dominance_info info;
+{
+  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);
+}
+
+/* Return the immediate dominator of basic block BB.  */
+basic_block
+get_immediate_dominator (dom, bb)
+     dominance_info dom;
+     basic_block bb;
+{
+  return et_forest_node_value (dom->forest,
+			       et_forest_parent (dom->forest,
+						 BB_NODE (dom, bb)));
+}
+
+/* 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;
+{
+  void *aux_bb_node;
+  et_forest_node_t bb_node = BB_NODE (dom, bb);
+
+  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 (bb == dominated_by)
+	abort ();
+      if (!et_forest_add_edge (dom->forest, BB_NODE (dom, dominated_by), bb_node))
+	abort ();
+    }
+}
+
+/* Store all basic blocks 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;
+{
+  int n, i;
+
+  *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;
+{
+  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;
+
+  for (i = 0; i < n; i++)
+    {
+      et_forest_remove_edge (dom->forest, node, bbs[i]);
+      et_forest_add_edge (dom->forest, node2, bbs[i]);
+    }
+  free (bbs);
+}
+
+/* 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;
+{
+  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 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;
+}
+
+/* Verify invariants of dominator structure.  */
+void
+verify_dominators (dom)
+     dominance_info dom;
+{
+  int err = 0;
+  basic_block bb;
+
+  FOR_EACH_BB (bb)
+    {
+      basic_block dom_bb;
+
+      dom_bb = recount_dominator (dom, bb);
+      if (dom_bb != get_immediate_dominator (dom, bb))
 	{
-	  TBB d = di.dom[di.dfs_order[b->index]];
+	  error ("dominator of %d should be %d, not %d",
+	   bb->index, dom_bb->index, get_immediate_dominator(dom, bb)->index);
+	  err = 1;
+	}
+    }
+  if (err)
+    abort ();
+}
+
+/* Recount dominator of BB.  */
+basic_block
+recount_dominator (dom, bb)
+     dominance_info dom;
+     basic_block bb;
+{
+   basic_block dom_bb = NULL;
+   edge e;
+
+   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);
+     }
 
-	  /* 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[b->index] = di.dfs_to_bb[d]->index;
+   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;
+{
+  int i, changed = 1;
+  basic_block old_dom, new_dom;
+
+  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]);
+	  if (old_dom != new_dom)
+	    {
+	      changed = 1;
+	      set_immediate_dominator (dom, bbs[i], new_dom);
+	    }
 	}
     }
-  if (doms)
-    idoms_to_doms (&di, doms);
+}
 
-  free_dom_info (&di);
+void
+add_to_dominance_info (dom, bb)
+     dominance_info dom;
+     basic_block bb;
+{
+  VARRAY_GROW (dom->varray, last_basic_block + 3);
+#ifdef ENABLE_CHECKING
+  if (BB_NODE (dom, bb))
+    abort ();
+#endif
+  SET_BB_NODE (dom, bb, et_forest_add_node (dom->forest, bb));
+}
+
+void
+delete_from_dominance_info (dom, bb)
+     dominance_info dom;
+     basic_block bb;
+{
+  et_forest_remove_node (dom->forest, BB_NODE (dom, bb));
+  SET_BB_NODE (dom, bb, NULL);
+}
+
+void
+debug_dominance_info (dom)
+  dominance_info dom;
+{
+  basic_block bb, bb2;
+  FOR_EACH_BB (bb)
+    if ((bb2 = get_immediate_dominator (dom, bb)))
+      fprintf (stderr, "%i %i\n", bb->index, bb2->index);
 }
diff --git a/gcc/gcse.c b/gcc/gcse.c
index f0a7d3bff84..e73200840a2 100644
--- a/gcc/gcse.c
+++ b/gcc/gcse.c
@@ -5752,7 +5752,7 @@ static sbitmap *hoist_vbeout;
 static sbitmap *hoist_exprs;
 
 /* Dominator bitmaps.  */
-static sbitmap *dominators;
+dominance_info dominators;
 
 /* ??? We could compute post dominators and run this algorithm in
    reverse to to perform tail merging, doing so would probably be
@@ -5775,8 +5775,6 @@ alloc_code_hoist_mem (n_blocks, n_exprs)
   hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
   hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs);
   transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
-
-  dominators = sbitmap_vector_alloc (n_blocks, n_blocks);
 }
 
 /* Free vars used for code hoisting analysis.  */
@@ -5793,7 +5791,7 @@ free_code_hoist_mem ()
   sbitmap_vector_free (hoist_exprs);
   sbitmap_vector_free (transpout);
 
-  sbitmap_vector_free (dominators);
+  free_dominance_info (dominators);
 }
 
 /* Compute the very busy expressions at entry/exit from each block.
@@ -5842,7 +5840,7 @@ compute_code_hoist_data ()
   compute_local_properties (transp, comp, antloc, 0);
   compute_transpout ();
   compute_code_hoist_vbeinout ();
-  calculate_dominance_info (NULL, dominators, CDI_DOMINATORS);
+  dominators = calculate_dominance_info (CDI_DOMINATORS);
   if (gcse_file)
     fprintf (gcse_file, "\n");
 }
@@ -5949,7 +5947,7 @@ hoist_code ()
 		{
 		  /* Ignore self dominance.  */
 		  if (bb == dominated
-		      || ! TEST_BIT (dominators[dominated->index], bb->index))
+		      || dominated_by_p (dominators, dominated, bb))
 		    continue;
 
 		  /* We've found a dominated block, now see if it computes
@@ -6006,7 +6004,7 @@ hoist_code ()
 		{
 		  /* Ignore self dominance.  */
 		  if (bb == dominated
-		      || ! TEST_BIT (dominators[dominated->index], bb->index))
+		      || ! dominated_by_p (dominators, dominated, bb))
 		    continue;
 
 		  /* We've found a dominated block, now see if it computes
diff --git a/gcc/ifcvt.c b/gcc/ifcvt.c
index bd9d7da7d8e..6bc522d0fe6 100644
--- a/gcc/ifcvt.c
+++ b/gcc/ifcvt.c
@@ -77,7 +77,7 @@ static int num_removed_blocks;
 static bool life_data_ok;
 
 /* The post-dominator relation on the original block numbers.  */
-static sbitmap *post_dominators;
+static dominance_info post_dominators;
 
 /* Forward references.  */
 static int count_bb_insns		PARAMS ((basic_block));
@@ -1814,6 +1814,8 @@ merge_if_block (test_bb, then_bb, else_bb, join_bb)
       if (combo_bb->global_live_at_end)
 	COPY_REG_SET (combo_bb->global_live_at_end,
 		      then_bb->global_live_at_end);
+      if (post_dominators)
+	delete_from_dominance_info (post_dominators, then_bb);
       merge_blocks_nomove (combo_bb, then_bb);
       num_removed_blocks++;
     }
@@ -1823,6 +1825,8 @@ merge_if_block (test_bb, then_bb, else_bb, join_bb)
      get their addresses taken.  */
   if (else_bb)
     {
+      if (post_dominators)
+	delete_from_dominance_info (post_dominators, else_bb);
       merge_blocks_nomove (combo_bb, else_bb);
       num_removed_blocks++;
     }
@@ -1877,6 +1881,8 @@ merge_if_block (test_bb, then_bb, else_bb, join_bb)
       if (combo_bb->global_live_at_end)
 	COPY_REG_SET (combo_bb->global_live_at_end,
 		      join_bb->global_live_at_end);
+      if (post_dominators)
+	delete_from_dominance_info (post_dominators, join_bb);
       merge_blocks_nomove (combo_bb, join_bb);
       num_removed_blocks++;
     }
@@ -2135,6 +2141,8 @@ find_cond_trap (test_bb, then_edge, else_edge)
   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
   if (trap_bb->pred == NULL)
     {
+      if (post_dominators)
+	delete_from_dominance_info (post_dominators, trap_bb);
       flow_delete_block (trap_bb);
       num_removed_blocks++;
     }
@@ -2316,6 +2324,8 @@ find_if_case_1 (test_bb, then_edge, else_edge)
   
   new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
   then_bb_index = then_bb->index;
+  if (post_dominators)
+    delete_from_dominance_info (post_dominators, then_bb);
   flow_delete_block (then_bb);
   /* Make rest of code believe that the newly created block is the THEN_BB
      block we removed.  */
@@ -2366,8 +2376,8 @@ find_if_case_2 (test_bb, then_edge, else_edge)
   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
     ;
   else if (else_succ->dest->index < 0
-	   || TEST_BIT (post_dominators[then_bb->index], 
-			else_succ->dest->index))
+	   || dominated_by_p (post_dominators, then_bb, 
+			      else_succ->dest))
     ;
   else
     return FALSE;
@@ -2393,6 +2403,8 @@ find_if_case_2 (test_bb, then_edge, else_edge)
 		    then_bb->global_live_at_start,
 		    else_bb->global_live_at_end, BITMAP_IOR);
   
+  if (post_dominators)
+    delete_from_dominance_info (post_dominators, else_bb);
   flow_delete_block (else_bb);
 
   num_removed_blocks++;
@@ -2700,8 +2712,7 @@ if_convert (x_life_data_ok)
   post_dominators = NULL;
   if (HAVE_conditional_execution || life_data_ok)
     {
-      post_dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
-      calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
+      post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
     }
   if (life_data_ok)
     clear_bb_flags ();
@@ -2712,7 +2723,7 @@ if_convert (x_life_data_ok)
       continue;
 
   if (post_dominators)
-    sbitmap_vector_free (post_dominators);
+    free_dominance_info (post_dominators);
 
   if (rtl_dump_file)
     fflush (rtl_dump_file);
diff --git a/gcc/predict.c b/gcc/predict.c
index c00c86409f3..71950ee6766 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -49,6 +49,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "real.h"
 #include "params.h"
 #include "target.h"
+#include "loop.h"
 
 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, 0.5,
                    REAL_BB_FREQ_MAX.  */
@@ -73,10 +74,12 @@ static void estimate_loops_at_level	 PARAMS ((struct loop *loop));
 static void propagate_freq		 PARAMS ((struct loop *));
 static void estimate_bb_frequencies	 PARAMS ((struct loops *));
 static void counts_to_freqs		 PARAMS ((void));
-static void process_note_predictions	 PARAMS ((basic_block, int *, int *,
-						  sbitmap *));
-static void process_note_prediction	 PARAMS ((basic_block, int *, int *,
-						  sbitmap *, int, int));
+static void process_note_predictions	 PARAMS ((basic_block, int *,
+						  dominance_info,
+						  dominance_info));
+static void process_note_prediction	 PARAMS ((basic_block, int *, 
+						  dominance_info,
+						  dominance_info, int, int));
 static bool last_basic_block_p           PARAMS ((basic_block));
 static void compute_function_frequency	 PARAMS ((void));
 static void choose_function_section	 PARAMS ((void));
@@ -408,14 +411,13 @@ void
 estimate_probability (loops_info)
      struct loops *loops_info;
 {
-  sbitmap *dominators, *post_dominators;
+  dominance_info dominators, post_dominators;
   basic_block bb;
   int i;
 
-  dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
-  post_dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
-  calculate_dominance_info (NULL, dominators, CDI_DOMINATORS);
-  calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
+  connect_infinite_loops_to_exit ();
+  dominators = calculate_dominance_info (CDI_DOMINATORS);
+  post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
 
   /* Try to predict out blocks in a loop that are not part of a
      natural loop.  */
@@ -495,8 +497,8 @@ estimate_probability (loops_info)
 	  /* Look for block we are guarding (ie we dominate it,
 	     but it doesn't postdominate us).  */
 	  if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
-	      && TEST_BIT (dominators[e->dest->index], e->src->index)
-	      && !TEST_BIT (post_dominators[e->src->index], e->dest->index))
+	      && dominated_by_p (dominators, e->dest, e->src)
+	      && !dominated_by_p (post_dominators, e->src, e->dest))
 	    {
 	      rtx insn;
 
@@ -613,9 +615,10 @@ estimate_probability (loops_info)
 	&& bb->succ->succ_next != NULL)
       combine_predictions_for_insn (bb->end, bb);
 
-  sbitmap_vector_free (post_dominators);
-  sbitmap_vector_free (dominators);
+  free_dominance_info (post_dominators);
+  free_dominance_info (dominators);
 
+  remove_fake_edges ();
   estimate_bb_frequencies (loops_info);
 }
 
@@ -717,8 +720,8 @@ static void
 process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
      basic_block bb;
      int *heads;
-     int *dominators;
-     sbitmap *post_dominators;
+     dominance_info dominators;
+     dominance_info post_dominators;
      int pred;
      int flags;
 {
@@ -733,27 +736,30 @@ process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
       /* This is first time we need this field in heads array; so
          find first dominator that we do not post-dominate (we are
          using already known members of heads array).  */
-      int ai = bb->index;
-      int next_ai = dominators[bb->index];
+      basic_block ai = bb;
+      basic_block next_ai = get_immediate_dominator (dominators, bb);
       int head;
 
-      while (heads[next_ai] < 0)
+      while (heads[next_ai->index] < 0)
 	{
-	  if (!TEST_BIT (post_dominators[next_ai], bb->index))
+	  if (!dominated_by_p (post_dominators, next_ai, bb))
 	    break;
-	  heads[next_ai] = ai;
+	  heads[next_ai->index] = ai->index;
 	  ai = next_ai;
-	  next_ai = dominators[next_ai];
+	  next_ai = get_immediate_dominator (dominators, next_ai);
 	}
-      if (!TEST_BIT (post_dominators[next_ai], bb->index))
-	head = next_ai;
+      if (!dominated_by_p (post_dominators, next_ai, bb))
+	head = next_ai->index;
       else
-	head = heads[next_ai];
-      while (next_ai != bb->index)
+	head = heads[next_ai->index];
+      while (next_ai != bb)
 	{
 	  next_ai = ai;
-	  ai = heads[ai];
-	  heads[next_ai] = head;
+	  if (heads[ai->index] == ENTRY_BLOCK)
+	    ai = ENTRY_BLOCK_PTR;
+	  else
+	    ai = BASIC_BLOCK (heads[ai->index]);
+	  heads[next_ai->index] = head;
 	}
     }
   y = heads[bb->index];
@@ -764,7 +770,7 @@ process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
     return;
   for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
     if (e->dest->index >= 0
-	&& TEST_BIT (post_dominators[e->dest->index], bb->index))
+	&& dominated_by_p (post_dominators, e->dest, bb))
       predict_edge_def (e, pred, taken);
 }
 
@@ -776,8 +782,8 @@ static void
 process_note_predictions (bb, heads, dominators, post_dominators)
      basic_block bb;
      int *heads;
-     int *dominators;
-     sbitmap *post_dominators;
+     dominance_info dominators;
+     dominance_info post_dominators;
 {
   rtx insn;
   edge e;
@@ -838,18 +844,15 @@ void
 note_prediction_to_br_prob ()
 {
   basic_block bb;
-  sbitmap *post_dominators;
-  int *dominators, *heads;
+  dominance_info post_dominators, dominators;
+  int *heads;
 
   /* To enable handling of noreturn blocks.  */
   add_noreturn_fake_exit_edges ();
   connect_infinite_loops_to_exit ();
 
-  dominators = xmalloc (sizeof (int) * last_basic_block);
-  memset (dominators, -1, sizeof (int) * last_basic_block);
-  post_dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
-  calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
-  calculate_dominance_info (dominators, NULL, CDI_DOMINATORS);
+  post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
+  dominators = calculate_dominance_info (CDI_DOMINATORS);
 
   heads = xmalloc (sizeof (int) * last_basic_block);
   memset (heads, -1, sizeof (int) * last_basic_block);
@@ -860,8 +863,8 @@ note_prediction_to_br_prob ()
   FOR_EACH_BB (bb)
     process_note_predictions (bb, heads, dominators, post_dominators);
 
-  sbitmap_vector_free (post_dominators);
-  free (dominators);
+  free_dominance_info (post_dominators);
+  free_dominance_info (dominators);
   free (heads);
 
   remove_fake_edges ();
diff --git a/gcc/sched-rgn.c b/gcc/sched-rgn.c
index 6227645651b..4a9989758c8 100644
--- a/gcc/sched-rgn.c
+++ b/gcc/sched-rgn.c
@@ -153,7 +153,7 @@ static int *containing_rgn;
 
 void debug_regions PARAMS ((void));
 static void find_single_block_region PARAMS ((void));
-static void find_rgns PARAMS ((struct edge_list *, sbitmap *));
+static void find_rgns PARAMS ((struct edge_list *, dominance_info));
 static int too_large PARAMS ((int, int *, int *));
 
 extern void debug_live PARAMS ((int, int));
@@ -624,7 +624,7 @@ too_large (block, num_bbs, num_insns)
 static void
 find_rgns (edge_list, dom)
      struct edge_list *edge_list;
-     sbitmap *dom;
+     dominance_info dom;
 {
   int *max_hdr, *dfs_nr, *stack, *degree;
   char no_loops = 1;
@@ -837,7 +837,7 @@ find_rgns (edge_list, dom)
 		    {
 		      /* Now verify that the block is dominated by the loop
 			 header.  */
-		      if (!TEST_BIT (dom[jbb->index], bb->index))
+		      if (!dominated_by_p (dom, jbb, bb))
 			break;
 		    }
 		}
@@ -2909,11 +2909,9 @@ init_regions ()
 	}
       else
 	{
-	  sbitmap *dom;
+	  dominance_info dom;
 	  struct edge_list *edge_list;
 
-	  dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
-
 	  /* The scheduler runs after flow; therefore, we can't blindly call
 	     back into find_basic_blocks since doing so could invalidate the
 	     info in global_live_at_start.
@@ -2928,7 +2926,7 @@ init_regions ()
 	  edge_list = create_edge_list ();
 
 	  /* Compute the dominators and post dominators.  */
-	  calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
+	  dom = calculate_dominance_info (CDI_DOMINATORS);
 
 	  /* build_control_flow will return nonzero if it detects unreachable
 	     blocks or any other irregularity with the cfg which prevents
@@ -2946,7 +2944,7 @@ init_regions ()
 
 	  /* For now.  This will move as more and more of haifa is converted
 	     to using the cfg code in flow.c.  */
-	  free (dom);
+	  free_dominance_info (dom);
 	}
     }
 
diff --git a/gcc/ssa-dce.c b/gcc/ssa-dce.c
index ffee1c9b5c0..09fcc7ad65a 100644
--- a/gcc/ssa-dce.c
+++ b/gcc/ssa-dce.c
@@ -98,13 +98,13 @@ static void set_control_dependent_block_to_edge_map_bit
 static void control_dependent_block_to_edge_map_free
   PARAMS ((control_dependent_block_to_edge_map c));
 static void find_all_control_dependences
-  PARAMS ((struct edge_list *el, int *pdom,
+  PARAMS ((struct edge_list *el, dominance_info pdom,
 	   control_dependent_block_to_edge_map cdbte));
 static void find_control_dependence
-  PARAMS ((struct edge_list *el, int edge_index, int *pdom,
+  PARAMS ((struct edge_list *el, int edge_index, dominance_info pdom,
 	   control_dependent_block_to_edge_map cdbte));
 static basic_block find_pdom
-  PARAMS ((int *pdom, basic_block block));
+  PARAMS ((dominance_info pdom, basic_block block));
 static int inherently_necessary_register_1
   PARAMS ((rtx *current_rtx, void *data));
 static int inherently_necessary_register
@@ -218,7 +218,7 @@ control_dependent_block_to_edge_map_free (c)
 static void
 find_all_control_dependences (el, pdom, cdbte)
    struct edge_list *el;
-   int *pdom;
+   dominance_info pdom;
    control_dependent_block_to_edge_map cdbte;
 {
   int i;
@@ -237,7 +237,7 @@ static void
 find_control_dependence (el, edge_index, pdom, cdbte)
    struct edge_list *el;
    int edge_index;
-   int *pdom;
+   dominance_info pdom;
    control_dependent_block_to_edge_map cdbte;
 {
   basic_block current_block;
@@ -266,7 +266,7 @@ find_control_dependence (el, edge_index, pdom, cdbte)
 
 static basic_block
 find_pdom (pdom, block)
-     int *pdom;
+     dominance_info pdom;
      basic_block block;
 {
   if (!block)
@@ -276,10 +276,15 @@ find_pdom (pdom, block)
 
   if (block == ENTRY_BLOCK_PTR)
     return ENTRY_BLOCK_PTR->next_bb;
-  else if (block == EXIT_BLOCK_PTR || pdom[block->index] == EXIT_BLOCK)
+  else if (block == EXIT_BLOCK_PTR)
     return EXIT_BLOCK_PTR;
   else
-    return BASIC_BLOCK (pdom[block->index]);
+    {
+      basic_block bb = get_immediate_dominator (pdom, block);
+      if (!bb)
+	return EXIT_BLOCK_PTR;
+      return bb;
+    }
 }
 
 /* Determine if the given CURRENT_RTX uses a hard register not
@@ -488,7 +493,6 @@ delete_insn_bb (insn)
 void
 ssa_eliminate_dead_code ()
 {
-  int i;
   rtx insn;
   basic_block bb;
   /* Necessary instructions with operands to explore.  */
@@ -497,7 +501,7 @@ ssa_eliminate_dead_code ()
      edge.  "cdbte" abbreviates control dependent block to edge.  */
   control_dependent_block_to_edge_map cdbte;
  /* Element I is the immediate postdominator of block I.  */
-  int *pdom;
+  dominance_info pdom;
   struct edge_list *el;
 
   /* Initialize the data structures.  */
@@ -510,14 +514,7 @@ ssa_eliminate_dead_code ()
   connect_infinite_loops_to_exit ();
 
   /* Compute control dependence.  */
-  pdom = (int *) xmalloc (last_basic_block * sizeof (int));
-  for (i = 0; i < last_basic_block; ++i)
-    pdom[i] = INVALID_BLOCK;
-  calculate_dominance_info (pdom, NULL, CDI_POST_DOMINATORS);
-  /* Assume there is a path from each node to the exit block.  */
-  for (i = 0; i < last_basic_block; ++i)
-    if (pdom[i] == INVALID_BLOCK)
-      pdom[i] = EXIT_BLOCK;
+  pdom = calculate_dominance_info (CDI_POST_DOMINATORS);
   el = create_edge_list ();
   find_all_control_dependences (el, pdom, cdbte);
 
diff --git a/gcc/ssa.c b/gcc/ssa.c
index c18f3b9e2f6..71be1a9d957 100644
--- a/gcc/ssa.c
+++ b/gcc/ssa.c
@@ -165,7 +165,7 @@ struct rename_context;
 static inline rtx * phi_alternative
   PARAMS ((rtx, int));
 static void compute_dominance_frontiers_1
-  PARAMS ((sbitmap *frontiers, int *idom, int bb, sbitmap done));
+  PARAMS ((sbitmap *frontiers, dominance_info idom, int bb, sbitmap done));
 static void find_evaluations_1
   PARAMS ((rtx dest, rtx set, void *data));
 static void find_evaluations
@@ -183,9 +183,9 @@ static void apply_delayed_renames
 static int rename_insn_1
   PARAMS ((rtx *ptr, void *data));
 static void rename_block
-  PARAMS ((int b, int *idom));
+  PARAMS ((int b, dominance_info dom));
 static void rename_registers
-  PARAMS ((int nregs, int *idom));
+  PARAMS ((int nregs, dominance_info idom));
 
 static inline int ephi_add_node
   PARAMS ((rtx reg, rtx *nodes, int *n_nodes));
@@ -516,7 +516,7 @@ find_evaluations (evals, nregs)
 static void
 compute_dominance_frontiers_1 (frontiers, idom, bb, done)
      sbitmap *frontiers;
-     int *idom;
+     dominance_info idom;
      int bb;
      sbitmap done;
 {
@@ -531,7 +531,8 @@ compute_dominance_frontiers_1 (frontiers, idom, bb, done)
      dominator tree (blocks dominated by this one) are children in the
      CFG, so check all blocks.  */
   FOR_EACH_BB (c)
-    if (idom[c->index] == bb && ! TEST_BIT (done, c->index))
+    if (get_immediate_dominator (idom, c)->index == bb
+	&& ! TEST_BIT (done, c->index))
       compute_dominance_frontiers_1 (frontiers, idom, c->index, done);
 
   /* Find blocks conforming to rule (1) above.  */
@@ -539,18 +540,18 @@ compute_dominance_frontiers_1 (frontiers, idom, bb, done)
     {
       if (e->dest == EXIT_BLOCK_PTR)
 	continue;
-      if (idom[e->dest->index] != bb)
+      if (get_immediate_dominator (idom, e->dest)->index != bb)
 	SET_BIT (frontiers[bb], e->dest->index);
     }
 
   /* Find blocks conforming to rule (2).  */
   FOR_EACH_BB (c)
-    if (idom[c->index] == bb)
+    if (get_immediate_dominator (idom, c)->index == bb)
       {
 	int x;
 	EXECUTE_IF_SET_IN_SBITMAP (frontiers[c->index], 0, x,
 	  {
-	    if (idom[x] != bb)
+	    if (get_immediate_dominator (idom, BASIC_BLOCK (x))->index != bb)
 	      SET_BIT (frontiers[bb], x);
 	  });
       }
@@ -559,7 +560,7 @@ compute_dominance_frontiers_1 (frontiers, idom, bb, done)
 void
 compute_dominance_frontiers (frontiers, idom)
      sbitmap *frontiers;
-     int *idom;
+     dominance_info idom;
 {
   sbitmap done = sbitmap_alloc (last_basic_block);
   sbitmap_zero (done);
@@ -1001,7 +1002,7 @@ gen_sequence ()
 static void
 rename_block (bb, idom)
      int bb;
-     int *idom;
+     dominance_info idom;
 {
   basic_block b = BASIC_BLOCK (bb);
   edge e;
@@ -1111,7 +1112,7 @@ rename_block (bb, idom)
      dominator order.  */
 
   FOR_EACH_BB (c)
-    if (idom[c->index] == bb)
+    if (get_immediate_dominator (idom, c)->index == bb)
       rename_block (c->index, idom);
 
   /* Step Four: Update the sets to refer to their new register,
@@ -1137,7 +1138,7 @@ rename_block (bb, idom)
 static void
 rename_registers (nregs, idom)
      int nregs;
-     int *idom;
+     dominance_info idom;
 {
   VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
   ssa_rename_from_initialize ();
@@ -1168,7 +1169,7 @@ convert_to_ssa ()
   sbitmap *idfs;
 
   /* Element I is the immediate dominator of block I.  */
-  int *idom;
+  dominance_info idom;
 
   int nregs;
 
@@ -1182,15 +1183,14 @@ convert_to_ssa ()
      dead code.  We'll let the SSA optimizers do that.  */
   life_analysis (get_insns (), NULL, 0);
 
-  idom = (int *) alloca (last_basic_block * sizeof (int));
-  memset ((void *) idom, -1, (size_t) last_basic_block * sizeof (int));
-  calculate_dominance_info (idom, NULL, CDI_DOMINATORS);
+  idom = calculate_dominance_info (CDI_DOMINATORS);
 
   if (rtl_dump_file)
     {
       fputs (";; Immediate Dominators:\n", rtl_dump_file);
       FOR_EACH_BB (bb)
-	fprintf (rtl_dump_file, ";\t%3d = %3d\n", bb->index, idom[bb->index]);
+	fprintf (rtl_dump_file, ";\t%3d = %3d\n", bb->index,
+		 get_immediate_dominator (idom, bb)->index);
       fflush (rtl_dump_file);
     }
 
@@ -1241,6 +1241,7 @@ convert_to_ssa ()
   in_ssa_form = 1;
 
   reg_scan (get_insns (), max_reg_num (), 1);
+  free_dominance_info (idom);
 }
 
 /* REG is the representative temporary of its partition.  Add it to the
diff --git a/gcc/ssa.h b/gcc/ssa.h
index cbea11c3d5c..115f77d74d8 100644
--- a/gcc/ssa.h
+++ b/gcc/ssa.h
@@ -27,7 +27,8 @@ typedef int (*successor_phi_fn)         PARAMS ((rtx, int, int, void *));
 extern int for_each_successor_phi       PARAMS ((basic_block bb,
 						 successor_phi_fn,
 						 void *));
-void compute_dominance_frontiers	PARAMS ((sbitmap *frontiers, int *idom));
+void compute_dominance_frontiers	PARAMS ((sbitmap *frontiers,
+						 dominance_info idom));
 extern int remove_phi_alternative	PARAMS ((rtx, basic_block));