cfgloopmanip.c (remove_path, [...]): Change dom_bbs to vector.

	* cfgloopmanip.c (remove_path, loopify, duplicate_loop_to_header_edge):
	Change dom_bbs to vector.  Add argument to iterate_fix_dominators call.
	* loop-unroll.c (unroll_loop_runtime_iterations): Ditto.
	* tree-cfg.c (tree_duplicate_sese_region): Change doms to vector.
	Add argument to iterate_fix_dominators call.
	(remove_edge_and_dominated_blocks): Pass vector to bbs_to_fix_dom.
	* gcse.c (hoist_code): Change domby to vector.
	* cfghooks.c (make_forwarder_block): Change doms_to_fix to vector.
	Add argument to iterate_fix_dominators call.
	* loop-doloop.c (doloop_modify): Changed recount_dominator to
	recompute_dominator.
	* lambda-code.c (perfect_nestify): Ditto.
	* cfgloopanal.c: Include graphds.h.
	(struct edge, struct vertex, struct graph, dump_graph, new_graph,
	add_edge, dfs, for_each_edge, free_graph): Moved to graphds.c.
	(mark_irreducible_loops): Use graphds_scc.  Remove argument from
	add_edge call.
	* graphds.c: New file.
	* graphds.h: New file.
	* dominance.c: Include vecprim.h, pointer-set.h and graphds.h.
	(get_dominated_by, get_dominated_by_region): Change return type to
	vector.
	(verify_dominators): Recompute all dominators and compare the results.
	(recount_dominator): Renamed to ...
	(recompute_dominator): ... this.  Do not check that the block is
	dominated by entry.
	(iterate_fix_dominators): Reimplemented.
	(prune_bbs_to_update_dominators, root_of_dom_tree,
	determine_dominators_for_sons): New functions.
	* et-forest.c (et_root): New function.
	* et-forest.h (et_root): Declare.
	* Makefile.in (graphds.o): Add.
	(cfgloopanal.o): Add graphds.h dependency.
	(dominance.o): Add graphds.h, vecprim.h and pointer-set.h dependency.
	* basic-block.h (get_dominated_by, get_dominated_by_region,
	iterate_fix_dominators): Declaration changed.
	(recount_dominator): Renamed to ...
	(recompute_dominator): ... this.
	* tree-ssa-threadupdate.c (thread_block): Free dominance info.
	(thread_through_all_blocks): Do not free dominance info.

From-SVN: r125297

17 files changed, 1023 insertions, 354 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index a336afc5fc1..2214ddf712a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,46 @@
+2007-06-03  Zdenek Dvorak  <dvorakz@suse.cz>
+
+	* cfgloopmanip.c (remove_path, loopify, duplicate_loop_to_header_edge):
+	Change dom_bbs to vector.  Add argument to iterate_fix_dominators call.
+	* loop-unroll.c (unroll_loop_runtime_iterations): Ditto.
+	* tree-cfg.c (tree_duplicate_sese_region): Change doms to vector.
+	Add argument to iterate_fix_dominators call.
+	(remove_edge_and_dominated_blocks): Pass vector to bbs_to_fix_dom.
+	* gcse.c (hoist_code): Change domby to vector.
+	* cfghooks.c (make_forwarder_block): Change doms_to_fix to vector.
+	Add argument to iterate_fix_dominators call.
+	* loop-doloop.c (doloop_modify): Changed recount_dominator to
+	recompute_dominator.
+	* lambda-code.c (perfect_nestify): Ditto.
+	* cfgloopanal.c: Include graphds.h.
+	(struct edge, struct vertex, struct graph, dump_graph, new_graph,
+	add_edge, dfs, for_each_edge, free_graph): Moved to graphds.c.
+	(mark_irreducible_loops): Use graphds_scc.  Remove argument from
+	add_edge call.
+	* graphds.c: New file.
+	* graphds.h: New file.
+	* dominance.c: Include vecprim.h, pointer-set.h and graphds.h.
+	(get_dominated_by, get_dominated_by_region): Change return type to
+	vector.
+	(verify_dominators): Recompute all dominators and compare the results.
+	(recount_dominator): Renamed to ...
+	(recompute_dominator): ... this.  Do not check that the block is
+	dominated by entry.
+	(iterate_fix_dominators): Reimplemented.
+	(prune_bbs_to_update_dominators, root_of_dom_tree,
+	determine_dominators_for_sons): New functions.
+	* et-forest.c (et_root): New function.
+	* et-forest.h (et_root): Declare.
+	* Makefile.in (graphds.o): Add.
+	(cfgloopanal.o): Add graphds.h dependency.
+	(dominance.o): Add graphds.h, vecprim.h and pointer-set.h dependency.
+	* basic-block.h (get_dominated_by, get_dominated_by_region,
+	iterate_fix_dominators): Declaration changed.
+	(recount_dominator): Renamed to ...
+	(recompute_dominator): ... this.
+	* tree-ssa-threadupdate.c (thread_block): Free dominance info.
+	(thread_through_all_blocks): Do not free dominance info.
+
 2007-06-03  Andreas Schwab  <schwab@suse.de>
 
 	* config/m68k/m68k.c (override_options): Don't override
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 605a0bdff4d..a8d5046f62a 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1009,6 +1009,7 @@ OBJS-common = \
 	gimplify.o \
 	global.o \
 	graph.o \
+	graphds.o \
 	gtype-desc.o \
 	haifa-sched.o \
 	hooks.o \
@@ -2556,7 +2557,9 @@ cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) coretypes.h $(TM_H) \
    $(GGC_H)
 cfgloopanal.o : cfgloopanal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
    $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(EXPR_H) coretypes.h $(TM_H) \
-   $(OBSTACK_H) output.h
+   $(OBSTACK_H) output.h graphds.h
+graphds.o : graphds.c graphds.h $(CONFIG_H) $(SYSTEM_H) bitmap.h $(OBSTACK_H) \
+   coretypes.h vec.h vecprim.h
 struct-equiv.o : struct-equiv.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(RTL_H) hard-reg-set.h output.h $(FLAGS_H) $(RECOG_H) \
    insn-config.h $(TARGET_H) $(TM_P_H) $(PARAMS_H) \
@@ -2582,7 +2585,8 @@ loop-unroll.o: loop-unroll.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TM_H) \
    output.h $(EXPR_H) coretypes.h $(TM_H) $(HASHTAB_H) $(RECOG_H) \
    $(OBSTACK_H)
 dominance.o : dominance.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
-   hard-reg-set.h $(BASIC_BLOCK_H) et-forest.h $(OBSTACK_H) toplev.h $(TIMEVAR_H)
+   hard-reg-set.h $(BASIC_BLOCK_H) et-forest.h $(OBSTACK_H) toplev.h \
+   $(TIMEVAR_H) graphds.h vecprim.h pointer-set.h
 et-forest.o : et-forest.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    et-forest.h alloc-pool.h $(BASIC_BLOCK_H)
 combine.o : combine.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
diff --git a/gcc/basic-block.h b/gcc/basic-block.h
index dd3bc1a2825..8d7dbe322b0 100644
--- a/gcc/basic-block.h
+++ b/gcc/basic-block.h
@@ -959,15 +959,17 @@ extern void set_immediate_dominator (enum cdi_direction, basic_block,
 				     basic_block);
 extern basic_block get_immediate_dominator (enum cdi_direction, basic_block);
 extern bool dominated_by_p (enum cdi_direction, basic_block, basic_block);
-extern int get_dominated_by (enum cdi_direction, basic_block, basic_block **);
-extern unsigned get_dominated_by_region (enum cdi_direction, basic_block *,
-					 unsigned, basic_block *);
+extern VEC (basic_block, heap) *get_dominated_by (enum cdi_direction, basic_block);
+extern VEC (basic_block, heap) *get_dominated_by_region (enum cdi_direction,
+							 basic_block *,
+							 unsigned);
 extern void add_to_dominance_info (enum cdi_direction, basic_block);
 extern void delete_from_dominance_info (enum cdi_direction, basic_block);
-basic_block recount_dominator (enum cdi_direction, basic_block);
+basic_block recompute_dominator (enum cdi_direction, basic_block);
 extern void redirect_immediate_dominators (enum cdi_direction, basic_block,
 					   basic_block);
-extern void iterate_fix_dominators (enum cdi_direction, basic_block *, int);
+extern void iterate_fix_dominators (enum cdi_direction,
+				    VEC (basic_block, heap) *, bool);
 extern void verify_dominators (enum cdi_direction);
 extern basic_block first_dom_son (enum cdi_direction, basic_block);
 extern basic_block next_dom_son (enum cdi_direction, basic_block);
diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c
index 51405bb923a..beb377bd1e4 100644
--- a/gcc/cfghooks.c
+++ b/gcc/cfghooks.c
@@ -735,11 +735,11 @@ make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
 
   if (dom_info_available_p (CDI_DOMINATORS))
     {
-      basic_block doms_to_fix[2];
-
-      doms_to_fix[0] = dummy;
-      doms_to_fix[1] = bb;
-      iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, 2);
+      VEC (basic_block, heap) *doms_to_fix = VEC_alloc (basic_block, heap, 2);
+      VEC_quick_push (basic_block, doms_to_fix, dummy);
+      VEC_quick_push (basic_block, doms_to_fix, bb);
+      iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
+      VEC_free (basic_block, heap, doms_to_fix);
     }
 
   if (current_loops != NULL)
diff --git a/gcc/cfgloopanal.c b/gcc/cfgloopanal.c
index 760542a0ba8..30c871860f4 100644
--- a/gcc/cfgloopanal.c
+++ b/gcc/cfgloopanal.c
@@ -29,6 +29,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "cfgloop.h"
 #include "expr.h"
 #include "output.h"
+#include "graphds.h"
 
 /* Checks whether BB is executed exactly once in each LOOP iteration.  */
 
@@ -50,157 +51,6 @@ just_once_each_iteration_p (const struct loop *loop, basic_block bb)
   return true;
 }
 
-/* Structure representing edge of a graph.  */
-
-struct edge
-{
-  int src, dest;	/* Source and destination.  */
-  struct edge *pred_next, *succ_next;
-			/* Next edge in predecessor and successor lists.  */
-  void *data;		/* Data attached to the edge.  */
-};
-
-/* Structure representing vertex of a graph.  */
-
-struct vertex
-{
-  struct edge *pred, *succ;
-			/* Lists of predecessors and successors.  */
-  int component;	/* Number of dfs restarts before reaching the
-			   vertex.  */
-  int post;		/* Postorder number.  */
-};
-
-/* Structure representing a graph.  */
-
-struct graph
-{
-  int n_vertices;	/* Number of vertices.  */
-  struct vertex *vertices;
-			/* The vertices.  */
-};
-
-/* Dumps graph G into F.  */
-
-extern void dump_graph (FILE *, struct graph *);
-
-void
-dump_graph (FILE *f, struct graph *g)
-{
-  int i;
-  struct edge *e;
-
-  for (i = 0; i < g->n_vertices; i++)
-    {
-      if (!g->vertices[i].pred
-	  && !g->vertices[i].succ)
-	continue;
-
-      fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
-      for (e = g->vertices[i].pred; e; e = e->pred_next)
-	fprintf (f, " %d", e->src);
-      fprintf (f, "\n");
-
-      fprintf (f, "\t->");
-      for (e = g->vertices[i].succ; e; e = e->succ_next)
-	fprintf (f, " %d", e->dest);
-      fprintf (f, "\n");
-    }
-}
-
-/* Creates a new graph with N_VERTICES vertices.  */
-
-static struct graph *
-new_graph (int n_vertices)
-{
-  struct graph *g = XNEW (struct graph);
-
-  g->n_vertices = n_vertices;
-  g->vertices = XCNEWVEC (struct vertex, n_vertices);
-
-  return g;
-}
-
-/* Adds an edge from F to T to graph G, with DATA attached.  */
-
-static void
-add_edge (struct graph *g, int f, int t, void *data)
-{
-  struct edge *e = xmalloc (sizeof (struct edge));
-
-  e->src = f;
-  e->dest = t;
-  e->data = data;
-
-  e->pred_next = g->vertices[t].pred;
-  g->vertices[t].pred = e;
-
-  e->succ_next = g->vertices[f].succ;
-  g->vertices[f].succ = e;
-}
-
-/* Runs dfs search over vertices of G, from NQ vertices in queue QS.
-   The vertices in postorder are stored into QT.  If FORWARD is false,
-   backward dfs is run.  */
-
-static void
-dfs (struct graph *g, int *qs, int nq, int *qt, bool forward)
-{
-  int i, tick = 0, v, comp = 0, top;
-  struct edge *e;
-  struct edge **stack = xmalloc (sizeof (struct edge *) * g->n_vertices);
-
-  for (i = 0; i < g->n_vertices; i++)
-    {
-      g->vertices[i].component = -1;
-      g->vertices[i].post = -1;
-    }
-
-#define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred)
-#define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next)
-#define EDGE_SRC(E) (forward ? (E)->src : (E)->dest)
-#define EDGE_DEST(E) (forward ? (E)->dest : (E)->src)
-
-  for (i = 0; i < nq; i++)
-    {
-      v = qs[i];
-      if (g->vertices[v].post != -1)
-	continue;
-
-      g->vertices[v].component = comp++;
-      e = FST_EDGE (v);
-      top = 0;
-
-      while (1)
-	{
-	  while (e && g->vertices[EDGE_DEST (e)].component != -1)
-	    e = NEXT_EDGE (e);
-
-	  if (!e)
-	    {
-	      if (qt)
-		qt[tick] = v;
-	      g->vertices[v].post = tick++;
-
-	      if (!top)
-		break;
-
-	      e = stack[--top];
-	      v = EDGE_SRC (e);
-	      e = NEXT_EDGE (e);
-	      continue;
-	    }
-
-	  stack[top++] = e;
-	  v = EDGE_DEST (e);
-	  e = FST_EDGE (v);
-	  g->vertices[v].component = comp - 1;
-	}
-    }
-
-  free (stack);
-}
-
 /* Marks the edge E in graph G irreducible if it connects two vertices in the
    same scc.  */
 
@@ -221,38 +71,6 @@ check_irred (struct graph *g, struct edge *e)
     real->src->flags |= BB_IRREDUCIBLE_LOOP;
 }
 
-/* Runs CALLBACK for all edges in G.  */
-
-static void
-for_each_edge (struct graph *g,
-	       void (callback) (struct graph *, struct edge *))
-{
-  struct edge *e;
-  int i;
-
-  for (i = 0; i < g->n_vertices; i++)
-    for (e = g->vertices[i].succ; e; e = e->succ_next)
-      callback (g, e);
-}
-
-/* Releases the memory occupied by G.  */
-
-static void
-free_graph (struct graph *g)
-{
-  struct edge *e, *n;
-  int i;
-
-  for (i = 0; i < g->n_vertices; i++)
-    for (e = g->vertices[i].succ; e; e = n)
-      {
-	n = e->succ_next;
-	free (e);
-      }
-  free (g->vertices);
-  free (g);
-}
-
 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
    throw away all latch edges and mark blocks inside any remaining cycle.
    Everything is a bit complicated due to fact we do not want to do this
@@ -271,15 +89,11 @@ mark_irreducible_loops (void)
   basic_block act;
   edge e;
   edge_iterator ei;
-  int i, src, dest;
+  int src, dest;
+  unsigned depth;
   struct graph *g;
   int num = number_of_loops ();
-  int *queue1 = XNEWVEC (int, last_basic_block + num);
-  int *queue2 = XNEWVEC (int, last_basic_block + num);
-  int nq;
-  unsigned depth;
-  struct loop *cloop, *loop;
-  loop_iterator li;
+  struct loop *cloop;
 
   gcc_assert (current_loops != NULL);
 
@@ -332,34 +146,16 @@ mark_irreducible_loops (void)
 	    src = LOOP_REPR (cloop);
 	  }
 
-	add_edge (g, src, dest, e);
+	add_edge (g, src, dest)->data = e;
       }
 
-  /* Find the strongly connected components.  Use the algorithm of Tarjan --
-     first determine the postorder dfs numbering in reversed graph, then
-     run the dfs on the original graph in the order given by decreasing
-     numbers assigned by the previous pass.  */
-  nq = 0;
-  FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
-    {
-      queue1[nq++] = BB_REPR (act);
-    }
-
-  FOR_EACH_LOOP (li, loop, 0)
-    {
-      queue1[nq++] = LOOP_REPR (loop);
-    }
-  dfs (g, queue1, nq, queue2, false);
-  for (i = 0; i < nq; i++)
-    queue1[i] = queue2[nq - i - 1];
-  dfs (g, queue1, nq, NULL, true);
+  /* Find the strongly connected components.  */
+  graphds_scc (g, NULL);
 
   /* Mark the irreducible loops.  */
   for_each_edge (g, check_irred);
 
   free_graph (g);
-  free (queue1);
-  free (queue2);
 
   current_loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
 }
diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c
index 99b41d7ceae..4568833065b 100644
--- a/gcc/cfgloopmanip.c
+++ b/gcc/cfgloopmanip.c
@@ -276,8 +276,9 @@ bool
 remove_path (edge e)
 {
   edge ae;
-  basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
-  int i, nrem, n_bord_bbs, n_dom_bbs, nreml;
+  basic_block *rem_bbs, *bord_bbs, from, bb;
+  VEC (basic_block, heap) *dom_bbs;
+  int i, nrem, n_bord_bbs, nreml;
   sbitmap seen;
   bool irred_invalidated = false;
   struct loop **deleted_loop;
@@ -338,7 +339,7 @@ remove_path (edge e)
   /* Remove the path.  */
   from = e->src;
   remove_branch (e);
-  dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
+  dom_bbs = NULL;
 
   /* Cancel loops contained in the path.  */
   deleted_loop = XNEWVEC (struct loop *, nrem);
@@ -355,7 +356,6 @@ remove_path (edge e)
   free (deleted_loop);
 
   /* Find blocks whose dominators may be affected.  */
-  n_dom_bbs = 0;
   sbitmap_zero (seen);
   for (i = 0; i < n_bord_bbs; i++)
     {
@@ -370,14 +370,14 @@ remove_path (edge e)
 	   ldom;
 	   ldom = next_dom_son (CDI_DOMINATORS, ldom))
 	if (!dominated_by_p (CDI_DOMINATORS, from, ldom))
-	  dom_bbs[n_dom_bbs++] = ldom;
+	  VEC_safe_push (basic_block, heap, dom_bbs, ldom);
     }
 
   free (seen);
 
   /* Recount dominators.  */
-  iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
-  free (dom_bbs);
+  iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, true);
+  VEC_free (basic_block, heap, dom_bbs);
   free (bord_bbs);
 
   /* Fix placements of basic blocks inside loops and the placement of
@@ -472,8 +472,9 @@ loopify (edge latch_edge, edge header_edge,
 {
   basic_block succ_bb = latch_edge->dest;
   basic_block pred_bb = header_edge->src;
-  basic_block *dom_bbs, *body;
-  unsigned n_dom_bbs, i;
+  basic_block *body;
+  VEC (basic_block, heap) *dom_bbs;
+  unsigned i;
   sbitmap seen;
   struct loop *loop = alloc_loop ();
   struct loop *outer = loop_outer (succ_bb->loop_father);
@@ -528,8 +529,7 @@ loopify (edge latch_edge, edge header_edge,
   scale_loop_frequencies (succ_bb->loop_father, true_scale, REG_BR_PROB_BASE);
 
   /* Update dominators of blocks outside of LOOP.  */
-  dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
-  n_dom_bbs = 0;
+  dom_bbs = NULL;
   seen = sbitmap_alloc (last_basic_block);
   sbitmap_zero (seen);
   body = get_loop_body (loop);
@@ -547,15 +547,15 @@ loopify (edge latch_edge, edge header_edge,
 	if (!TEST_BIT (seen, ldom->index))
 	  {
 	    SET_BIT (seen, ldom->index);
-	    dom_bbs[n_dom_bbs++] = ldom;
+	    VEC_safe_push (basic_block, heap, dom_bbs, ldom);
 	  }
     }
 
-  iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
+  iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
 
   free (body);
   free (seen);
-  free (dom_bbs);
+  VEC_free (basic_block, heap, dom_bbs);
 
   return loop;
 }
@@ -1054,23 +1054,23 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e,
   /* Update dominators of outer blocks if affected.  */
   for (i = 0; i < n; i++)
     {
-      basic_block dominated, dom_bb, *dom_bbs;
-      int n_dom_bbs,j;
+      basic_block dominated, dom_bb;
+      VEC (basic_block, heap) *dom_bbs;
+      unsigned j;
 
       bb = bbs[i];
       bb->aux = 0;
 
-      n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs);
-      for (j = 0; j < n_dom_bbs; j++)
+      dom_bbs = get_dominated_by (CDI_DOMINATORS, bb);
+      for (j = 0; VEC_iterate (basic_block, dom_bbs, j, dominated); j++)
 	{
-	  dominated = dom_bbs[j];
 	  if (flow_bb_inside_loop_p (loop, dominated))
 	    continue;
 	  dom_bb = nearest_common_dominator (
 			CDI_DOMINATORS, first_active[i], first_active_latch);
 	  set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb);
 	}
-      free (dom_bbs);
+      VEC_free (basic_block, heap, dom_bbs);
     }
   free (first_active);
 
diff --git a/gcc/dominance.c b/gcc/dominance.c
index a9af9d52d15..57a9df6baa4 100644
--- a/gcc/dominance.c
+++ b/gcc/dominance.c
@@ -44,6 +44,9 @@
 #include "toplev.h"
 #include "et-forest.h"
 #include "timevar.h"
+#include "vecprim.h"
+#include "pointer-set.h"
+#include "graphds.h"
 
 /* Whether the dominators and the postdominators are available.  */
 static enum dom_state dom_computed[2];
@@ -735,45 +738,39 @@ set_immediate_dominator (enum cdi_direction dir, basic_block bb,
     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
 }
 
-/* Store all basic blocks immediately dominated by BB into BBS and return
-   their number.  */
-int
-get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs)
+/* Returns the list of basic blocks immediately dominated by BB, in the
+   direction DIR.  */
+VEC (basic_block, heap) *
+get_dominated_by (enum cdi_direction dir, basic_block bb)
 {
-  unsigned int dir_index = dom_convert_dir_to_idx (dir);
   int n;
+  unsigned int dir_index = dom_convert_dir_to_idx (dir);
   struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
- 
+  VEC (basic_block, heap) *bbs = NULL;
+
   gcc_assert (dom_computed[dir_index]);
 
   if (!son)
-    {
-      *bbs = NULL;
-      return 0;
-    }
-
-  for (ason = son->right, n = 1; ason != son; ason = ason->right)
-    n++;
+    return NULL;
 
-  *bbs = XNEWVEC (basic_block, n);
-  (*bbs)[0] = son->data;
+  VEC_safe_push (basic_block, heap, bbs, son->data);
   for (ason = son->right, n = 1; ason != son; ason = ason->right)
-    (*bbs)[n++] = ason->data;
+    VEC_safe_push (basic_block, heap, bbs, ason->data);
 
-  return n;
+  return bbs;
 }
 
-/* Find all basic blocks that are immediately dominated (in direction DIR)
-   by some block between N_REGION ones stored in REGION, except for blocks
-   in the REGION itself.  The found blocks are stored to DOMS and their number
-   is returned.  */
-
-unsigned
+/* Returns the list of basic blocks that are immediately dominated (in
+   direction DIR) by some block between N_REGION ones stored in REGION,
+   except for blocks in the REGION itself.  */
+  
+VEC (basic_block, heap) *
 get_dominated_by_region (enum cdi_direction dir, basic_block *region,
-			 unsigned n_region, basic_block *doms)
+			 unsigned n_region)
 {
-  unsigned n_doms = 0, i;
+  unsigned i;
   basic_block dom;
+  VEC (basic_block, heap) *doms = NULL;
 
   for (i = 0; i < n_region; i++)
     region[i]->flags |= BB_DUPLICATED;
@@ -782,11 +779,11 @@ get_dominated_by_region (enum cdi_direction dir, basic_block *region,
 	 dom;
 	 dom = next_dom_son (dir, dom))
       if (!(dom->flags & BB_DUPLICATED))
-	doms[n_doms++] = dom;
+	VEC_safe_push (basic_block, heap, doms, dom);
   for (i = 0; i < n_region; i++)
     region[i]->flags &= ~BB_DUPLICATED;
 
-  return n_doms;
+  return doms;
 }
 
 /* Redirect all edges pointing to BB to TO.  */
@@ -973,40 +970,37 @@ void
 verify_dominators (enum cdi_direction dir)
 {
   int err = 0;
-  basic_block bb;
+  basic_block *old_dom = XNEWVEC (basic_block, last_basic_block);
+  basic_block bb, imm_bb;
 
   gcc_assert (dom_info_available_p (dir));
 
   FOR_EACH_BB (bb)
     {
-      basic_block dom_bb;
-      basic_block imm_bb;
+      old_dom[bb->index] = get_immediate_dominator (dir, bb);
 
-      dom_bb = recount_dominator (dir, bb);
-      imm_bb = get_immediate_dominator (dir, bb);
-      if (dom_bb != imm_bb)
+      if (!old_dom[bb->index])
 	{
-	  if ((dom_bb == NULL) || (imm_bb == NULL))
-	    error ("dominator of %d status unknown", bb->index);
-	  else
-	    error ("dominator of %d should be %d, not %d",
-		   bb->index, dom_bb->index, imm_bb->index);
+	  error ("dominator of %d status unknown", bb->index);
 	  err = 1;
 	}
     }
 
-  if (dir == CDI_DOMINATORS)
+  free_dominance_info (dir);
+  calculate_dominance_info (dir);
+
+  FOR_EACH_BB (bb)
     {
-      FOR_EACH_BB (bb)
+      imm_bb = get_immediate_dominator (dir, bb);
+      if (old_dom[bb->index] != imm_bb)
 	{
-	  if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR))
-	    {
-	      error ("ENTRY does not dominate bb %d", bb->index);
-	      err = 1;
-	    }
+	  error ("dominator of %d should be %d, not %d",
+		 bb->index, imm_bb->index, old_dom[bb->index]->index);
+	  err = 1;
 	}
     }
 
+  free (old_dom);
   gcc_assert (!err);
 }
 
@@ -1016,7 +1010,7 @@ verify_dominators (enum cdi_direction dir)
    reaches a fixed point.  */
 
 basic_block
-recount_dominator (enum cdi_direction dir, basic_block bb)
+recompute_dominator (enum cdi_direction dir, basic_block bb)
 {
   unsigned int dir_index = dom_convert_dir_to_idx (dir);
   basic_block dom_bb = NULL;
@@ -1029,11 +1023,6 @@ recount_dominator (enum cdi_direction dir, basic_block bb)
     {
       FOR_EACH_EDGE (e, ei, bb->preds)
 	{
-	  /* Ignore the predecessors that either are not reachable from
-	     the entry block, or whose dominator was not determined yet.  */
-	  if (!dominated_by_p (dir, e->src, ENTRY_BLOCK_PTR))
-	    continue;
-
 	  if (!dominated_by_p (dir, e->src, bb))
 	    dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
 	}
@@ -1050,37 +1039,325 @@ recount_dominator (enum cdi_direction dir, basic_block bb)
   return dom_bb;
 }
 
-/* Iteratively recount dominators of BBS. The change is supposed to be local
-   and not to grow further.  */
+/* Use simple heuristics (see iterate_fix_dominators) to determine dominators
+   of BBS.  We assume that all the immediate dominators except for those of the
+   blocks in BBS are correct.  If CONSERVATIVE is true, we also assume that the
+   currently recorded immediate dominators of blocks in BBS really dominate the
+   blocks.  The basic blocks for that we determine the dominator are removed
+   from BBS.  */
+
+static void
+prune_bbs_to_update_dominators (VEC (basic_block, heap) *bbs,
+				bool conservative)
+{
+  unsigned i;
+  bool single;
+  basic_block bb, dom = NULL;
+  edge_iterator ei;
+  edge e;
+
+  for (i = 0; VEC_iterate (basic_block, bbs, i, bb);)
+    {
+      if (bb == ENTRY_BLOCK_PTR)
+	goto succeed;
+
+      if (single_pred_p (bb))
+	{
+	  set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
+	  goto succeed;
+	}
+
+      if (!conservative)
+	goto fail;
+
+      single = true;
+      dom = NULL;
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	{
+	  if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
+	    continue;
+
+	  if (!dom)
+	    dom = e->src;
+	  else
+	    {
+	      single = false;
+	      dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
+	    }
+	}
+
+      gcc_assert (dom != NULL);
+      if (single
+	  || find_edge (dom, bb))
+	{
+	  set_immediate_dominator (CDI_DOMINATORS, bb, dom);
+	  goto succeed;
+	}
+
+fail:
+      i++;
+      continue;
+
+succeed:
+      VEC_unordered_remove (basic_block, bbs, i);
+    }
+}
+
+/* Returns root of the dominance tree in the direction DIR that contains
+   BB.  */
+
+static basic_block
+root_of_dom_tree (enum cdi_direction dir, basic_block bb)
+{
+  return et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
+}
+
+/* See the comment in iterate_fix_dominators.  Finds the immediate dominators
+   for the sons of Y, found using the SON and BROTHER arrays representing
+   the dominance tree of graph G.  BBS maps the vertices of G to the basic
+   blocks.  */
+
+static void
+determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs,
+			       int y, int *son, int *brother)
+{
+  bitmap gprime;
+  int i, a, nc;
+  VEC (int, heap) **sccs;
+  basic_block bb, dom, ybb;
+  unsigned si;
+  edge e;
+  edge_iterator ei;
+
+  if (son[y] == -1)
+    return;
+  if (y == (int) VEC_length (basic_block, bbs))
+    ybb = ENTRY_BLOCK_PTR;
+  else
+    ybb = VEC_index (basic_block, bbs, y);
+
+  if (brother[son[y]] == -1)
+    {
+      /* Handle the common case Y has just one son specially.  */
+      bb = VEC_index (basic_block, bbs, son[y]);
+      set_immediate_dominator (CDI_DOMINATORS, bb,
+			       recompute_dominator (CDI_DOMINATORS, bb));
+      identify_vertices (g, y, son[y]);
+      return;
+    }
+
+  gprime = BITMAP_ALLOC (NULL);
+  for (a = son[y]; a != -1; a = brother[a])
+    bitmap_set_bit (gprime, a);
+
+  nc = graphds_scc (g, gprime);
+  BITMAP_FREE (gprime);
+
+  sccs = XCNEWVEC (VEC (int, heap) *, nc);
+  for (a = son[y]; a != -1; a = brother[a])
+    VEC_safe_push (int, heap, sccs[g->vertices[a].component], a);
+
+  for (i = nc - 1; i >= 0; i--)
+    {
+      dom = NULL;
+      for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
+	{
+	  bb = VEC_index (basic_block, bbs, a);
+	  FOR_EACH_EDGE (e, ei, bb->preds)
+	    {
+	      if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
+		continue;
+
+	      dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
+	    }
+	}
+
+      gcc_assert (dom != NULL);
+      for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
+	{
+	  bb = VEC_index (basic_block, bbs, a);
+	  set_immediate_dominator (CDI_DOMINATORS, bb, dom);
+	}
+    }
+
+  for (i = 0; i < nc; i++)
+    VEC_free (int, heap, sccs[i]);
+  free (sccs);
+
+  for (a = son[y]; a != -1; a = brother[a])
+    identify_vertices (g, y, a);
+}
+
+/* Recompute dominance information for basic blocks in the set BBS.  The
+   function assumes that the immediate dominators of all the other blocks
+   in CFG are correct, and that there are no unreachable blocks.
+
+   If CONSERVATIVE is true, we additionally assume that all the ancestors of
+   a block of BBS in the current dominance tree dominate it.  */
+
 void
-iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n)
+iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
+			bool conservative)
 {
+  unsigned i;
+  basic_block bb, dom;
+  struct graph *g;
+  int n, y;
+  size_t dom_i;
+  edge e;
+  edge_iterator ei;
+  struct pointer_map_t *map;
+  int *parent, *son, *brother;
   unsigned int dir_index = dom_convert_dir_to_idx (dir);
-  int i, changed = 1;
-  basic_block old_dom, new_dom;
 
+  /* We only support updating dominators.  There are some problems with
+     updating postdominators (need to add fake edges from infinite loops
+     and noreturn functions), and since we do not currently use
+     iterate_fix_dominators for postdominators, any attempt to handle these
+     problems would be unused, untested, and almost surely buggy.  We keep
+     the DIR argument for consistency with the rest of the dominator analysis
+     interface.  */
+  gcc_assert (dir == CDI_DOMINATORS);
   gcc_assert (dom_computed[dir_index]);
 
-  for (i = 0; i < n; i++)
-    set_immediate_dominator (dir, bbs[i], NULL);
+  /* The algorithm we use takes inspiration from the following papers, although
+     the details are quite different from any of them:
+
+     [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
+	 Dominator Tree of a Reducible Flowgraph
+     [2]  V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
+	  dominator trees
+     [3]  K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
+	  Algorithm
+
+     First, we use the following heuristics to decrease the size of the BBS
+     set:
+       a) if BB has a single predecessor, then its immediate dominator is this
+	  predecessor
+       additionally, if CONSERVATIVE is true:
+       b) if all the predecessors of BB except for one (X) are dominated by BB,
+	  then X is the immediate dominator of BB
+       c) if the nearest common ancestor of the predecessors of BB is X and
+	  X -> BB is an edge in CFG, then X is the immediate dominator of BB
+
+     Then, we need to establish the dominance relation among the basic blocks
+     in BBS.  We split the dominance tree by removing the immediate dominator
+     edges from BBS, creating a forrest F.  We form a graph G whose vertices
+     are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
+     X' -> Y in CFG such that X' belongs to the tree of the dominance forrest
+     whose root is X.  We then determine dominance tree of G.  Note that
+     for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
+     In this step, we can use arbitrary algorithm to determine dominators.
+     We decided to prefer the algorithm [3] to the algorithm of
+     Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
+     10 during gcc bootstrap), and [3] should perform better in this case.
+
+     Finally, we need to determine the immediate dominators for the basic
+     blocks of BBS.  If the immediate dominator of X in G is Y, then
+     the immediate dominator of X in CFG belongs to the tree of F rooted in
+     Y.  We process the dominator tree T of G recursively, starting from leaves.
+     Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
+     subtrees of the dominance tree of CFG rooted in X_i are already correct.
+     Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}.  We make
+     the following observations:
+       (i) the immediate dominator of all blocks in a strongly connected
+	   component of G' is the same
+       (ii) if X has no predecessors in G', then the immediate dominator of X
+	    is the nearest common ancestor of the predecessors of X in the
+	    subtree of F rooted in Y
+     Therefore, it suffices to find the topological ordering of G', and
+     process the nodes X_i in this order using the rules (i) and (ii).
+     Then, we contract all the nodes X_i with Y in G, so that the further
+     steps work correctly.  */
+
+  if (!conservative)
+    {
+      /* Split the tree now.  If the idoms of blocks in BBS are not
+	 conservatively correct, setting the dominators using the
+	 heuristics in prune_bbs_to_update_dominators could
+	 create cycles in the dominance "tree", and cause ICE.  */
+      for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+	set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
+    }
+
+  prune_bbs_to_update_dominators (bbs, conservative);
+  n = VEC_length (basic_block, bbs);
+
+  if (n == 0)
+    return;
 
-  while (changed)
+  if (n == 1)
     {
-      changed = 0;
-      for (i = 0; i < n; i++)
+      bb = VEC_index (basic_block, bbs, 0);
+      set_immediate_dominator (CDI_DOMINATORS, bb,
+			       recompute_dominator (CDI_DOMINATORS, bb));
+      return;
+    }
+
+  /* Construct the graph G.  */
+  map = pointer_map_create ();
+  for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+    {
+      /* If the dominance tree is conservatively correct, split it now.  */
+      if (conservative)
+	set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
+      *pointer_map_insert (map, bb) = (void *) (size_t) i;
+    }
+  *pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n;
+
+  g = new_graph (n + 1);
+  for (y = 0; y < g->n_vertices; y++)
+    g->vertices[y].data = BITMAP_ALLOC (NULL);
+  for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+    {
+      FOR_EACH_EDGE (e, ei, bb->preds)
 	{
-	  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 (dir, bbs[i], new_dom);
-	    }
+	  dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
+	  if (dom == bb)
+	    continue;
+
+	  dom_i = (size_t) *pointer_map_contains (map, dom);
+
+	  /* Do not include parallel edges to G.  */
+	  if (bitmap_bit_p (g->vertices[dom_i].data, i))
+	    continue;
+
+	  bitmap_set_bit (g->vertices[dom_i].data, i);
+	  add_edge (g, dom_i, i);
 	}
     }
+  for (y = 0; y < g->n_vertices; y++)
+    BITMAP_FREE (g->vertices[y].data);
+  pointer_map_destroy (map);
+
+  /* Find the dominator tree of G.  */
+  son = XNEWVEC (int, n + 1);
+  brother = XNEWVEC (int, n + 1);
+  parent = XNEWVEC (int, n + 1);
+  graphds_domtree (g, n, parent, son, brother);
+
+  /* Finally, traverse the tree and find the immediate dominators.  */
+  for (y = n; son[y] != -1; y = son[y])
+    continue;
+  while (y != -1)
+    {
+      determine_dominators_for_sons (g, bbs, y, son, brother);
+
+      if (brother[y] != -1)
+	{
+	  y = brother[y];
+	  while (son[y] != -1)
+	    y = son[y];
+	}
+      else
+	y = parent[y];
+    }
+
+  free (son);
+  free (brother);
+  free (parent);
 
-  for (i = 0; i < n; i++)
-    gcc_assert (get_immediate_dominator (dir, bbs[i]));
+  free_graph (g);
 }
 
 void
diff --git a/gcc/et-forest.c b/gcc/et-forest.c
index b8e55274109..b9dacc9b3e3 100644
--- a/gcc/et-forest.c
+++ b/gcc/et-forest.c
@@ -747,3 +747,20 @@ et_below (struct et_node *down, struct et_node *up)
 
   return !d->next || d->next->min + d->depth >= 0;
 }
+
+/* Returns the root of the tree that contains NODE.  */
+
+struct et_node *
+et_root (struct et_node *node)
+{
+  struct et_occ *occ = node->rightmost_occ, *r;
+
+  /* The root of the tree corresponds to the rightmost occurence in the
+     represented path.  */
+  et_splay (occ);
+  for (r = occ; r->next; r = r->next)
+    continue;
+  et_splay (r);
+
+  return r->of;
+}
diff --git a/gcc/et-forest.h b/gcc/et-forest.h
index 1de715f40b5..fd25cbed194 100644
--- a/gcc/et-forest.h
+++ b/gcc/et-forest.h
@@ -79,6 +79,7 @@ void et_set_father (struct et_node *, struct et_node *);
 void et_split (struct et_node *);
 struct et_node *et_nca (struct et_node *, struct et_node *);
 bool et_below (struct et_node *, struct et_node *);
+struct et_node *et_root (struct et_node *);
 
 #ifdef __cplusplus
 }
diff --git a/gcc/gcse.c b/gcc/gcse.c
index dd80e754454..461e26c855c 100644
--- a/gcc/gcse.c
+++ b/gcc/gcse.c
@@ -4829,8 +4829,7 @@ static void
 hoist_code (void)
 {
   basic_block bb, dominated;
-  basic_block *domby;
-  unsigned int domby_len;
+  VEC (basic_block, heap) *domby;
   unsigned int i,j;
   struct expr **index_map;
   struct expr *expr;
@@ -4852,7 +4851,7 @@ hoist_code (void)
       int found = 0;
       int insn_inserted_p;
 
-      domby_len = get_dominated_by (CDI_DOMINATORS, bb, &domby);
+      domby = get_dominated_by (CDI_DOMINATORS, bb);
       /* Examine each expression that is very busy at the exit of this
 	 block.  These are the potentially hoistable expressions.  */
       for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++)
@@ -4865,9 +4864,8 @@ hoist_code (void)
 	      /* We've found a potentially hoistable expression, now
 		 we look at every block BB dominates to see if it
 		 computes the expression.  */
-	      for (j = 0; j < domby_len; j++)
+	      for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++)
 		{
-		  dominated = domby[j];
 		  /* Ignore self dominance.  */
 		  if (bb == dominated)
 		    continue;
@@ -4906,8 +4904,8 @@ hoist_code (void)
       /* If we found nothing to hoist, then quit now.  */
       if (! found)
         {
-	  free (domby);
-	continue;
+	  VEC_free (basic_block, heap, domby);
+	  continue;
 	}
 
       /* Loop over all the hoistable expressions.  */
@@ -4923,9 +4921,8 @@ hoist_code (void)
 	      /* We've found a potentially hoistable expression, now
 		 we look at every block BB dominates to see if it
 		 computes the expression.  */
-	      for (j = 0; j < domby_len; j++)
+	      for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++)
 		{
-		  dominated = domby[j];
 		  /* Ignore self dominance.  */
 		  if (bb == dominated)
 		    continue;
@@ -4976,7 +4973,7 @@ hoist_code (void)
 		}
 	    }
 	}
-      free (domby);
+      VEC_free (basic_block, heap, domby);
     }
 
   free (index_map);
diff --git a/gcc/graphds.c b/gcc/graphds.c
new file mode 100644
index 00000000000..1496e09a028
--- /dev/null
+++ b/gcc/graphds.c
@@ -0,0 +1,473 @@
+/* Graph representation and manipulation functions.
+   Copyright (C) 2007
+   Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC 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.
+
+GCC 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 GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "obstack.h"
+#include "bitmap.h"
+#include "vec.h"
+#include "vecprim.h"
+#include "graphds.h"
+
+/* Dumps graph G into F.  */
+
+void
+dump_graph (FILE *f, struct graph *g)
+{
+  int i;
+  struct edge *e;
+
+  for (i = 0; i < g->n_vertices; i++)
+    {
+      if (!g->vertices[i].pred
+	  && !g->vertices[i].succ)
+	continue;
+
+      fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
+      for (e = g->vertices[i].pred; e; e = e->pred_next)
+	fprintf (f, " %d", e->src);
+      fprintf (f, "\n");
+
+      fprintf (f, "\t->");
+      for (e = g->vertices[i].succ; e; e = e->succ_next)
+	fprintf (f, " %d", e->dest);
+      fprintf (f, "\n");
+    }
+}
+
+/* Creates a new graph with N_VERTICES vertices.  */
+
+struct graph *
+new_graph (int n_vertices)
+{
+  struct graph *g = XNEW (struct graph);
+
+  g->n_vertices = n_vertices;
+  g->vertices = XCNEWVEC (struct vertex, n_vertices);
+
+  return g;
+}
+
+/* Adds an edge from F to T to graph G.  The new edge is returned.  */
+
+struct edge *
+add_edge (struct graph *g, int f, int t)
+{
+  struct edge *e = XNEW (struct edge);
+  struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
+
+
+  e->src = f;
+  e->dest = t;
+
+  e->pred_next = vt->pred;
+  vt->pred = e;
+
+  e->succ_next = vf->succ;
+  vf->succ = e;
+
+  return e;
+}
+
+/* Moves all the edges incident with U to V.  */
+
+void
+identify_vertices (struct graph *g, int v, int u)
+{
+  struct vertex *vv = &g->vertices[v];
+  struct vertex *uu = &g->vertices[u];
+  struct edge *e, *next;
+
+  for (e = uu->succ; e; e = next)
+    {
+      next = e->succ_next;
+
+      e->src = v;
+      e->succ_next = vv->succ;
+      vv->succ = e;
+    }
+  uu->succ = NULL;
+
+  for (e = uu->pred; e; e = next)
+    {
+      next = e->pred_next;
+
+      e->dest = v;
+      e->pred_next = vv->pred;
+      vv->pred = e;
+    }
+  uu->pred = NULL;
+}
+
+/* Helper function for graphds_dfs.  Returns the source vertex of E, in the
+   direction given by FORWARD.  */
+
+static inline int
+dfs_edge_src (struct edge *e, bool forward)
+{
+  return forward ? e->src : e->dest;
+}
+
+/* Helper function for graphds_dfs.  Returns the destination vertex of E, in
+   the direction given by FORWARD.  */
+
+static inline int
+dfs_edge_dest (struct edge *e, bool forward)
+{
+  return forward ? e->dest : e->src;
+}
+
+/* Helper function for graphds_dfs.  Returns the first edge after E (including
+   E), in the graph direction given by FORWARD, that belongs to SUBGRAPH.  */
+
+static inline struct edge *
+foll_in_subgraph (struct edge *e, bool forward, bitmap subgraph)
+{
+  int d;
+
+  if (!subgraph)
+    return e;
+
+  while (e)
+    {
+      d = dfs_edge_dest (e, forward);
+      if (bitmap_bit_p (subgraph, d))
+	return e;
+
+      e = forward ? e->succ_next : e->pred_next;
+    }
+
+  return e;
+}
+
+/* Helper function for graphds_dfs.  Select the first edge from V in G, in the
+   direction given by FORWARD, that belongs to SUBGRAPH.  */
+
+static inline struct edge *
+dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph)
+{
+  struct edge *e;
+
+  e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
+  return foll_in_subgraph (e, forward, subgraph);
+}
+
+/* Helper function for graphds_dfs.  Returns the next edge after E, in the
+   graph direction given by FORWARD, that belongs to SUBGRAPH.  */
+
+static inline struct edge *
+dfs_next_edge (struct edge *e, bool forward, bitmap subgraph)
+{
+  return foll_in_subgraph (forward ? e->succ_next : e->pred_next,
+			   forward, subgraph);
+}
+
+/* Runs dfs search over vertices of G, from NQ vertices in queue QS.
+   The vertices in postorder are stored into QT.  If FORWARD is false,
+   backward dfs is run.  If SUBGRAPH is not NULL, it specifies the
+   subgraph of G to run DFS on.  Returns the number of the components
+   of the graph (number of the restarts of DFS).  */
+
+int
+graphds_dfs (struct graph *g, int *qs, int nq, VEC (int, heap) **qt,
+	     bool forward, bitmap subgraph)
+{
+  int i, tick = 0, v, comp = 0, top;
+  struct edge *e;
+  struct edge **stack = XNEWVEC (struct edge *, g->n_vertices);
+  bitmap_iterator bi;
+  unsigned av;
+
+  if (subgraph)
+    {
+      EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi)
+	{
+	  g->vertices[av].component = -1;
+	  g->vertices[av].post = -1;
+	}
+    }
+  else
+    {
+      for (i = 0; i < g->n_vertices; i++)
+	{
+	  g->vertices[i].component = -1;
+	  g->vertices[i].post = -1;
+	}
+    }
+
+  for (i = 0; i < nq; i++)
+    {
+      v = qs[i];
+      if (g->vertices[v].post != -1)
+	continue;
+
+      g->vertices[v].component = comp++;
+      e = dfs_fst_edge (g, v, forward, subgraph);
+      top = 0;
+
+      while (1)
+	{
+	  while (e)
+	    {
+	      if (g->vertices[dfs_edge_dest (e, forward)].component
+		  == -1)
+		break;
+	      e = dfs_next_edge (e, forward, subgraph);
+	    }
+
+	  if (!e)
+	    {
+	      if (qt)
+		VEC_safe_push (int, heap, *qt, v);
+	      g->vertices[v].post = tick++;
+
+	      if (!top)
+		break;
+
+	      e = stack[--top];
+	      v = dfs_edge_src (e, forward);
+	      e = dfs_next_edge (e, forward, subgraph);
+	      continue;
+	    }
+
+	  stack[top++] = e;
+	  v = dfs_edge_dest (e, forward);
+	  e = dfs_fst_edge (g, v, forward, subgraph);
+	  g->vertices[v].component = comp - 1;
+	}
+    }
+
+  free (stack);
+
+  return comp;
+}
+
+/* Determines the strongly connected components of G, using the algorithm of
+   Tarjan -- first determine the postorder dfs numbering in reversed graph,
+   then run the dfs on the original graph in the order given by decreasing
+   numbers assigned by the previous pass.  If SUBGRAPH is not NULL, it
+   specifies the subgraph of G whose strongly connected components we want
+   to determine.
+   
+   After running this function, v->component is the number of the strongly
+   connected component for each vertex of G.  Returns the number of the
+   sccs of G.  */
+
+int
+graphds_scc (struct graph *g, bitmap subgraph)
+{
+  int *queue = XNEWVEC (int, g->n_vertices);
+  VEC (int, heap) *postorder = NULL;
+  int nq, i, comp;
+  unsigned v;
+  bitmap_iterator bi;
+
+  if (subgraph)
+    {
+      nq = 0;
+      EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
+	{
+	  queue[nq++] = v;
+	}
+    }
+  else
+    {
+      for (i = 0; i < g->n_vertices; i++)
+	queue[i] = i;
+      nq = g->n_vertices;
+    }
+
+  graphds_dfs (g, queue, nq, &postorder, false, subgraph);
+  gcc_assert (VEC_length (int, postorder) == (unsigned) nq);
+
+  for (i = 0; i < nq; i++)
+    queue[i] = VEC_index (int, postorder, nq - i - 1);
+  comp = graphds_dfs (g, queue, nq, NULL, true, subgraph);
+
+  free (queue);
+  VEC_free (int, heap, postorder);
+
+  return comp;
+}
+
+/* Runs CALLBACK for all edges in G.  */
+
+void
+for_each_edge (struct graph *g, graphds_edge_callback callback)
+{
+  struct edge *e;
+  int i;
+
+  for (i = 0; i < g->n_vertices; i++)
+    for (e = g->vertices[i].succ; e; e = e->succ_next)
+      callback (g, e);
+}
+
+/* Releases the memory occupied by G.  */
+
+void
+free_graph (struct graph *g)
+{
+  struct edge *e, *n;
+  struct vertex *v;
+  int i;
+
+  for (i = 0; i < g->n_vertices; i++)
+    {
+      v = &g->vertices[i];
+      for (e = v->succ; e; e = n)
+	{
+	  n = e->succ_next;
+	  free (e);
+	}
+    }
+  free (g->vertices);
+  free (g);
+}
+
+/* Returns the nearest common ancestor of X and Y in tree whose parent
+   links are given by PARENT.  MARKS is the array used to mark the
+   vertices of the tree, and MARK is the number currently used as a mark.  */
+
+static int
+tree_nca (int x, int y, int *parent, int *marks, int mark)
+{
+  if (x == -1 || x == y)
+    return y;
+
+  /* We climb with X and Y up the tree, marking the visited nodes.  When
+     we first arrive to a marked node, it is the common ancestor.  */
+  marks[x] = mark;
+  marks[y] = mark;
+
+  while (1)
+    {
+      x = parent[x];
+      if (x == -1)
+	break;
+      if (marks[x] == mark)
+	return x;
+      marks[x] = mark;
+
+      y = parent[y];
+      if (y == -1)
+	break;
+      if (marks[y] == mark)
+	return y;
+      marks[y] = mark;
+    }
+
+  /* If we reached the root with one of the vertices, continue
+     with the other one till we reach the marked part of the
+     tree.  */
+  if (x == -1)
+    {
+      for (y = parent[y]; marks[y] != mark; y = parent[y])
+	continue;
+
+      return y;
+    }
+  else
+    {
+      for (x = parent[x]; marks[x] != mark; x = parent[x])
+	continue;
+
+      return x;
+    }
+}
+
+/* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
+   arrays), where the entry node is ENTRY.  */
+
+void
+graphds_domtree (struct graph *g, int entry,
+		 int *parent, int *son, int *brother)
+{
+  VEC (int, heap) *postorder = NULL;
+  int *marks = XCNEWVEC (int, g->n_vertices);
+  int mark = 1, i, v, idom;
+  bool changed = true;
+  struct edge *e;
+
+  /* We use a slight modification of the standard iterative algorithm, as
+     described in
+     
+     K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
+	Algorithm
+
+     sort vertices in reverse postorder
+     foreach v
+       dom(v) = everything
+     dom(entry) = entry;
+
+     while (anything changes)
+       foreach v
+         dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
+
+     The sets dom(v) are represented by the parent links in the current version
+     of the dominance tree.  */
+
+  for (i = 0; i < g->n_vertices; i++)
+    {
+      parent[i] = -1;
+      son[i] = -1;
+      brother[i] = -1;
+    }
+  graphds_dfs (g, &entry, 1, &postorder, true, NULL);
+  gcc_assert (VEC_length (int, postorder) == (unsigned) g->n_vertices);
+  gcc_assert (VEC_index (int, postorder, g->n_vertices - 1) == entry);
+
+  while (changed)
+    {
+      changed = false;
+
+      for (i = g->n_vertices - 2; i >= 0; i--)
+	{
+	  v = VEC_index (int, postorder, i);
+	  idom = -1;
+	  for (e = g->vertices[v].pred; e; e = e->pred_next)
+	    {
+	      if (e->src != entry
+		  && parent[e->src] == -1)
+		continue;
+
+	      idom = tree_nca (idom, e->src, parent, marks, mark++);
+	    }
+
+	  if (idom != parent[v])
+	    {
+	      parent[v] = idom;
+	      changed = true;
+	    }
+	}
+    }
+
+  free (marks);
+  VEC_free (int, heap, postorder);
+
+  for (i = 0; i < g->n_vertices; i++)
+    if (parent[i] != -1)
+      {
+	brother[i] = son[parent[i]];
+	son[parent[i]] = i;
+      }
+}
diff --git a/gcc/graphds.h b/gcc/graphds.h
new file mode 100644
index 00000000000..2aad4b00a73
--- /dev/null
+++ b/gcc/graphds.h
@@ -0,0 +1,63 @@
+/* Graph representation.
+   Copyright (C) 2007
+   Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC 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.
+
+GCC 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 GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
+
+/* Structure representing edge of a graph.  */
+
+struct edge
+{
+  int src, dest;	/* Source and destination.  */
+  struct edge *pred_next, *succ_next;
+			/* Next edge in predecessor and successor lists.  */
+  void *data;		/* Data attached to the edge.  */
+};
+
+/* Structure representing vertex of a graph.  */
+
+struct vertex
+{
+  struct edge *pred, *succ;
+			/* Lists of predecessors and successors.  */
+  int component;	/* Number of dfs restarts before reaching the
+			   vertex.  */
+  int post;		/* Postorder number.  */
+  void *data;		/* Data attached to the vertex.  */
+};
+
+/* Structure representing a graph.  */
+
+struct graph
+{
+  int n_vertices;	/* Number of vertices.  */
+  struct vertex *vertices;
+			/* The vertices.  */
+};
+
+struct graph *new_graph (int);
+void dump_graph (FILE *, struct graph *);
+struct edge *add_edge (struct graph *, int, int);
+void identify_vertices (struct graph *, int, int);
+int graphds_dfs (struct graph *, int *, int,
+		 VEC (int, heap) **, bool, bitmap);
+int graphds_scc (struct graph *, bitmap);
+void graphds_domtree (struct graph *, int, int *, int *, int *);
+typedef void (*graphds_edge_callback) (struct graph *, struct edge *);
+void for_each_edge (struct graph *, graphds_edge_callback);
+void free_graph (struct graph *g);
diff --git a/gcc/lambda-code.c b/gcc/lambda-code.c
index 62fd245b235..291d1d91e5b 100644
--- a/gcc/lambda-code.c
+++ b/gcc/lambda-code.c
@@ -2521,7 +2521,7 @@ perfect_nestify (struct loop *loop,
 			   single_exit (loop)->src);
   set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb);
   set_immediate_dominator (CDI_DOMINATORS, olddest,
-			   recount_dominator (CDI_DOMINATORS, olddest));
+			   recompute_dominator (CDI_DOMINATORS, olddest));
   /* Create the new iv.  */
   oldivvar = VEC_index (tree, loopivs, 0);
   ivvar = create_tmp_var (TREE_TYPE (oldivvar), "perfectiv");
diff --git a/gcc/loop-doloop.c b/gcc/loop-doloop.c
index ef42c609198..f59feae78ad 100644
--- a/gcc/loop-doloop.c
+++ b/gcc/loop-doloop.c
@@ -422,13 +422,13 @@ doloop_modify (struct loop *loop, struct niter_desc *desc,
 	  emit_insn_after (sequence, BB_END (set_zero));
       
 	  set_immediate_dominator (CDI_DOMINATORS, set_zero,
-				   recount_dominator (CDI_DOMINATORS,
-						      set_zero));
+				   recompute_dominator (CDI_DOMINATORS,
+							set_zero));
 	}
 
       set_immediate_dominator (CDI_DOMINATORS, new_preheader,
-			       recount_dominator (CDI_DOMINATORS,
-						  new_preheader));
+			       recompute_dominator (CDI_DOMINATORS,
+						    new_preheader));
     }
 
   /* Some targets (eg, C4x) need to initialize special looping
diff --git a/gcc/loop-unroll.c b/gcc/loop-unroll.c
index c5653b2c051..77d454f35bc 100644
--- a/gcc/loop-unroll.c
+++ b/gcc/loop-unroll.c
@@ -953,8 +953,8 @@ unroll_loop_runtime_iterations (struct loop *loop)
 {
   rtx old_niter, niter, init_code, branch_code, tmp;
   unsigned i, j, p;
-  basic_block preheader, *body, *dom_bbs, swtch, ezc_swtch;
-  unsigned n_dom_bbs;
+  basic_block preheader, *body, swtch, ezc_swtch;
+  VEC (basic_block, heap) *dom_bbs;
   sbitmap wont_exit;
   int may_exit_copy;
   unsigned n_peel;
@@ -972,21 +972,20 @@ unroll_loop_runtime_iterations (struct loop *loop)
     opt_info = analyze_insns_in_loop (loop);
   
   /* Remember blocks whose dominators will have to be updated.  */
-  dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
-  n_dom_bbs = 0;
+  dom_bbs = NULL;
 
   body = get_loop_body (loop);
   for (i = 0; i < loop->num_nodes; i++)
     {
-      unsigned nldom;
-      basic_block *ldom;
+      VEC (basic_block, heap) *ldom;
+      basic_block bb;
 
-      nldom = get_dominated_by (CDI_DOMINATORS, body[i], &ldom);
-      for (j = 0; j < nldom; j++)
-	if (!flow_bb_inside_loop_p (loop, ldom[j]))
-	  dom_bbs[n_dom_bbs++] = ldom[j];
+      ldom = get_dominated_by (CDI_DOMINATORS, body[i]);
+      for (j = 0; VEC_iterate (basic_block, ldom, j, bb); j++)
+	if (!flow_bb_inside_loop_p (loop, bb))
+	  VEC_safe_push (basic_block, heap, dom_bbs, bb);
 
-      free (ldom);
+      VEC_free (basic_block, heap, ldom);
     }
   free (body);
 
@@ -1105,7 +1104,7 @@ unroll_loop_runtime_iterations (struct loop *loop)
     }
 
   /* Recount dominators for outer blocks.  */
-  iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
+  iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
 
   /* And unroll loop.  */
 
@@ -1177,8 +1176,7 @@ unroll_loop_runtime_iterations (struct loop *loop)
 	     "in runtime, %i insns\n",
 	     max_unroll, num_loop_insns (loop));
 
-  if (dom_bbs)
-    free (dom_bbs);
+  VEC_free (basic_block, heap, dom_bbs);
 }
 
 /* Decide whether to simply peel LOOP and how much.  */
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 7bd4496cf83..6dc0d3e4203 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -4336,11 +4336,11 @@ tree_duplicate_sese_region (edge entry, edge exit,
 			    basic_block *region, unsigned n_region,
 			    basic_block *region_copy)
 {
-  unsigned i, n_doms;
+  unsigned i;
   bool free_region_copy = false, copying_header = false;
   struct loop *loop = entry->dest->loop_father;
   edge exit_copy;
-  basic_block *doms;
+  VEC (basic_block, heap) *doms;
   edge redirected;
   int total_freq = 0, entry_freq = 0;
   gcov_type total_count = 0, entry_count = 0;
@@ -4392,10 +4392,10 @@ tree_duplicate_sese_region (edge entry, edge exit,
 
   /* Record blocks outside the region that are dominated by something
      inside.  */
-  doms = XNEWVEC (basic_block, n_basic_blocks);
+  doms = NULL;
   initialize_original_copy_tables ();
 
-  n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
+  doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
 
   if (entry->dest->count)
     {
@@ -4451,8 +4451,8 @@ tree_duplicate_sese_region (edge entry, edge exit,
      region, but was dominated by something inside needs recounting as
      well.  */
   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
-  doms[n_doms++] = get_bb_original (entry->dest);
-  iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
+  VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
+  iterate_fix_dominators (CDI_DOMINATORS, doms, false);
   free (doms);
 
   /* Add the other PHI node arguments.  */
@@ -5476,9 +5476,7 @@ remove_edge_and_dominated_blocks (edge e)
 	VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
     }
 
-  iterate_fix_dominators (CDI_DOMINATORS,
-			  VEC_address (basic_block, bbs_to_fix_dom),
-			  VEC_length (basic_block, bbs_to_fix_dom));
+  iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
 
   BITMAP_FREE (df);
   BITMAP_FREE (df_idom);
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 815c84fb7b3..e8a05ed857b 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -577,6 +577,9 @@ thread_block (basic_block bb, bool noloop_only)
       lookup_redirection_data (e, NULL, NO_INSERT)->do_not_duplicate = true;
     }
 
+  /* We do not update dominance info.  */
+  free_dominance_info (CDI_DOMINATORS);
+
   /* Now create duplicates of BB.
 
      Note that for a block with a high outgoing degree we can waste
@@ -1057,9 +1060,6 @@ thread_through_all_blocks (bool may_peel_loop_headers)
       retval |= thread_through_loop_header (loop, may_peel_loop_headers);
     }
 
-  if (retval)
-    free_dominance_info (CDI_DOMINATORS);
-
   if (dump_file && (dump_flags & TDF_STATS))
     fprintf (dump_file, "\nJumps threaded: %lu\n",
 	     thread_stats.num_threaded_edges);