[patch] Fix mark_irreducible_loops

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

yet another bug in mark_irreducible_loops showed up during specint
testing with profiling.  This time I have finally done what I should
do ages ago, rewrite the function into a more readable and understandable form.

Bootstrapped (with -funroll-all-loops -funswitch-loops) and regtested on i686.

Zdenek

	* cfgloopanal.c (mark_irreducible_loops): Rewriten.
	(struct edge, struct vertex, struct graph): New.
	(dump_graph, new_graph, add_edge, dfs, check_irred, for_each_edge,
	free_graph): New functions.

Index: cfgloopanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopanal.c,v
retrieving revision 1.18
diff -c -3 -p -r1.18 cfgloopanal.c
*** cfgloopanal.c	30 Dec 2003 10:40:51 -0000	1.18
--- cfgloopanal.c	14 Jan 2004 15:56:59 -0000
*************** simple_loop_p (struct loop *loop, struct
*** 1111,1131 ****
    return any;
  }
  
  /* 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
     for parts of cycles that only "pass" through some loop -- i.e. for
     each cycle, we want to mark blocks that belong directly to innermost
!    loop containing the whole cycle.  */
  void
  mark_irreducible_loops (struct loops *loops)
  {
-   int *dfs_in, *closed, *mr, *mri, *n_edges, *stack;
-   unsigned i;
-   edge **edges, e;
-   edge *estack;
    basic_block act;
!   int stack_top, tick, depth;
    struct loop *cloop;
  
    /* Reset the flags.  */
--- 1111,1340 ----
    return any;
  }
  
+ /* 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 = xmalloc (sizeof (struct graph));
+ 
+   g->n_vertices = n_vertices;
+   g->vertices = xcalloc (n_vertices, sizeof (struct vertex));
+ 
+   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.  */
+ 
+ static void
+ check_irred (struct graph *g, struct edge *e)
+ {
+   edge real = e->data;
+ 
+   /* All edges should lead from a component with higher number to the
+      one with lower one.  */
+   if (g->vertices[e->src].component < g->vertices[e->dest].component)
+     abort ();
+ 
+   if (g->vertices[e->src].component != g->vertices[e->dest].component)
+     return;
+ 
+   real->flags |= EDGE_IRREDUCIBLE_LOOP;
+   if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
+     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
     for parts of cycles that only "pass" through some loop -- i.e. for
     each cycle, we want to mark blocks that belong directly to innermost
!    loop containing the whole cycle.
!    
!    LOOPS is the loop tree.  */
! 
! #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
! #define BB_REPR(BB) ((BB)->index + 1)
! 
  void
  mark_irreducible_loops (struct loops *loops)
  {
    basic_block act;
!   edge e;
!   int i, src, dest;
!   struct graph *g;
!   int *queue1 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
!   int *queue2 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
!   int nq, depth;
    struct loop *cloop;
  
    /* Reset the flags.  */
*************** mark_irreducible_loops (struct loops *lo
*** 1136,1311 ****
  	e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
      }
  
-   /* The first last_basic_block + 1 entries are for real blocks (including
-      entry); then we have loops->num - 1 fake blocks for loops to that we
-      assign edges leading from loops (fake loop 0 is not interesting).  */
-   dfs_in = xmalloc ((last_basic_block + loops->num) * sizeof (int));
-   closed = xmalloc ((last_basic_block + loops->num) * sizeof (int));
-   mr = xmalloc ((last_basic_block + loops->num) * sizeof (int));
-   mri = xmalloc ((last_basic_block + loops->num) * sizeof (int));
-   n_edges = xmalloc ((last_basic_block + loops->num) * sizeof (int));
-   edges = xmalloc ((last_basic_block + loops->num) * sizeof (edge *));
-   stack = xmalloc ((n_basic_blocks + loops->num) * sizeof (int));
-   estack = xmalloc ((n_basic_blocks + loops->num) * sizeof (edge));
- 
    /* Create the edge lists.  */
!   for (i = 0; i < last_basic_block + loops->num; i++)
!     n_edges[i] = 0;
    FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
      for (e = act->succ; e; e = e->succ_next)
        {
          /* Ignore edges to exit.  */
          if (e->dest == EXIT_BLOCK_PTR)
  	  continue;
  	/* And latch edges.  */
  	if (e->dest->loop_father->header == e->dest
  	    && e->dest->loop_father->latch == act)
  	  continue;
  	/* Edges inside a single loop should be left where they are.  Edges
  	   to subloop headers should lead to representative of the subloop,
! 	   but from the same place.  */
! 	if (act->loop_father == e->dest->loop_father
! 	    || act->loop_father == e->dest->loop_father->outer)
! 	  {
! 	    n_edges[act->index + 1]++;
! 	    continue;
! 	  }
! 	/* Edges exiting loops remain.  They should lead from representative
  	   of the son of nearest common ancestor of the loops in that
  	   act lays.  */
- 	depth = find_common_loop (act->loop_father, e->dest->loop_father)->depth + 1;
- 	if (depth == act->loop_father->depth)
- 	  cloop = act->loop_father;
- 	else
- 	  cloop = act->loop_father->pred[depth];
- 	n_edges[cloop->num + last_basic_block]++;
-       }
  
!   for (i = 0; i < last_basic_block + loops->num; i++)
!     {
!       edges[i] = xmalloc (n_edges[i] * sizeof (edge));
!       n_edges[i] = 0;
!     }
  
!   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
!     for (e = act->succ; e; e = e->succ_next)
!       {
!         if (e->dest == EXIT_BLOCK_PTR)
! 	  continue;
! 	if (e->dest->loop_father->header == e->dest
! 	    && e->dest->loop_father->latch == act)
! 	  continue;
! 	if (act->loop_father == e->dest->loop_father
! 	    || act->loop_father == e->dest->loop_father->outer)
  	  {
! 	    edges[act->index + 1][n_edges[act->index + 1]++] = e;
! 	    continue;
! 	  }
! 	depth = find_common_loop (act->loop_father, e->dest->loop_father)->depth + 1;
! 	if (depth == act->loop_father->depth)
! 	  cloop = act->loop_father;
! 	else
! 	  cloop = act->loop_father->pred[depth];
! 	i = cloop->num + last_basic_block;
! 	edges[i][n_edges[i]++] = e;
!       }
  
!   /* Compute dfs numbering, starting from loop headers, and mark found
!      loops.  */
!   tick = 0;
!   for (i = 0; i < last_basic_block + loops->num; i++)
!     {
!       dfs_in[i] = -1;
!       closed[i] = 0;
!       mr[i] = last_basic_block + loops->num;
!       mri[i] = -1;
!     }
  
!   stack_top = 0;
!   for (i = 0; i < loops->num; i++)
!     if (loops->parray[i])
!       {
! 	stack[stack_top] = loops->parray[i]->header->index + 1;
! 	estack[stack_top] = NULL;
! 	stack_top++;
        }
  
!   while (stack_top)
      {
!       int idx, sidx;
! 
!       idx = stack[stack_top - 1];
!       if (dfs_in[idx] < 0)
! 	dfs_in[idx] = tick++;
! 
!       while (n_edges[idx])
! 	{
! 	  e = edges[idx][--n_edges[idx]];
! 	  sidx = e->dest->loop_father->header == e->dest
! 	           ? e->dest->loop_father->num + last_basic_block
! 	           : e->dest->index + 1;
!           if (closed[sidx])
! 	    {
! 	      if (mri[sidx] != -1 && !closed[mri[sidx]])
! 		{
! 		  if (mr[sidx] < mr[idx])
! 		    {
! 		      mr[idx] = mr[sidx];
! 		      mri[idx] = mri[sidx];
! 		    }
! 
! 		  if (mr[sidx] <= dfs_in[idx])
! 		    e->flags |= EDGE_IRREDUCIBLE_LOOP;
! 		}
! 	      continue;
! 	    }
! 	  if (dfs_in[sidx] < 0)
! 	    {
! 	      stack[stack_top] = sidx;
! 	      estack[stack_top] = e;
! 	      stack_top++;
! 	      goto next;
! 	    }
! 	  if (dfs_in[sidx] < mr[idx])
! 	    {
! 	      mr[idx] = dfs_in[sidx];
! 	      mri[idx] = sidx;
! 	    }
! 	  e->flags |= EDGE_IRREDUCIBLE_LOOP;
! 	}
! 
!       /* Return back.  */
!       closed[idx] = 1;
!       e = estack[stack_top - 1];
!       stack_top--;
!       if (e)
!         {
! 	  /* Propagate information back.  */
! 	  sidx = stack[stack_top - 1];
! 	  if (mr[sidx] > mr[idx])
! 	    {
! 	      mr[sidx] = mr[idx];
! 	      mri[sidx] = mri[idx];
! 	    }
! 	  if (mr[idx] <= dfs_in[sidx])
! 	    e->flags |= EDGE_IRREDUCIBLE_LOOP;
! 	}
!       /* Mark the block if relevant.  */
!       if (idx && idx <= last_basic_block && mr[idx] <= dfs_in[idx])
!         BASIC_BLOCK (idx - 1)->flags |= BB_IRREDUCIBLE_LOOP;
! next:;
      }
  
-   free (stack);
-   free (estack);
-   free (dfs_in);
-   free (closed);
-   free (mr);
-   free (mri);
-   for (i = 0; i < last_basic_block + loops->num; i++)
-     free (edges[i]);
-   free (edges);
-   free (n_edges);
    loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
  }
  
--- 1345,1418 ----
  	e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
      }
  
    /* Create the edge lists.  */
!   g = new_graph (last_basic_block + loops->num);
! 
    FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
      for (e = act->succ; e; e = e->succ_next)
        {
          /* Ignore edges to exit.  */
          if (e->dest == EXIT_BLOCK_PTR)
  	  continue;
+ 
  	/* And latch edges.  */
  	if (e->dest->loop_father->header == e->dest
  	    && e->dest->loop_father->latch == act)
  	  continue;
+ 
  	/* Edges inside a single loop should be left where they are.  Edges
  	   to subloop headers should lead to representative of the subloop,
! 	   but from the same place.
! 
! 	   Edges exiting loops should lead from representative
  	   of the son of nearest common ancestor of the loops in that
  	   act lays.  */
  
! 	src = BB_REPR (act);
! 	dest = BB_REPR (e->dest);
  
! 	if (e->dest->loop_father->header == e->dest)
! 	  dest = LOOP_REPR (e->dest->loop_father);
! 
! 	if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
  	  {
! 	    depth = find_common_loop (act->loop_father,
! 				      e->dest->loop_father)->depth + 1;
! 	    if (depth == act->loop_father->depth)
! 	      cloop = act->loop_father;
! 	    else
! 	      cloop = act->loop_father->pred[depth];
  
! 	    src = LOOP_REPR (cloop);
! 	  }
  
! 	add_edge (g, src, dest, 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 (i = 1; i < (int) loops->num; i++)
+     if (loops->parray[i])
+       queue1[nq++] = LOOP_REPR (loops->parray[i]);
+   dfs (g, queue1, nq, queue2, false);
+   for (i = 0; i < nq; i++)
+     queue1[i] = queue2[nq - i - 1];
+   dfs (g, queue1, nq, NULL, true);
+ 
+   /* Mark the irreducible loops.  */
+   for_each_edge (g, check_irred);
+ 
+   free_graph (g);
+   free (queue1);
+   free (queue2);
  
    loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
  }