* 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.



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

1 files changed, 7 insertions, 211 deletions

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;
 }