* basic-block.h (struct loops): New field rc_order.

	* flow.c (flow_loops_cfg_dump): Dump rc_order if computed.
	(flow_loops_free): Free rc_order.
	(flow_depth_first_order_compute): New parameter rc_order.
	(flow_loops_find): Allocate rc_order and swap usage with
 	dfs_order.


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

3 files changed, 49 insertions, 12 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 59352704489..a90b9fc426f 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,12 @@
+2000-07-25  Michael Hayes  <mph@paradise.net.nz>
+
+	* basic-block.h (struct loops): New field rc_order.
+	* flow.c (flow_loops_cfg_dump): Dump rc_order if computed.
+	(flow_loops_free): Free rc_order.
+	(flow_depth_first_order_compute): New parameter rc_order.
+	(flow_loops_find): Allocate rc_order and swap usage with
+ 	dfs_order.
+
 2000-07-30 Herman A.J. ten Brugge <Haj.Ten.Brugge@net.HCC.nl>
 	   Michael Hayes  <m.hayes@elec.canterbury.ac.nz>
 
diff --git a/gcc/basic-block.h b/gcc/basic-block.h
index 633bdafdb20..084d56d5281 100644
--- a/gcc/basic-block.h
+++ b/gcc/basic-block.h
@@ -246,6 +246,7 @@ extern void tidy_fallthru_edge		PARAMS ((edge, basic_block,
 /* Structure to hold information for each natural loop.  */
 struct loop
 {
+  /* Index into loops array.  */
   int num;
 
   /* Basic block of loop header.  */
@@ -369,6 +370,10 @@ struct loops
 
     /* The ordering of the basic blocks in a depth first search.  */
     int *dfs_order;
+
+    /* The reverse completion ordering of the basic blocks found in a
+       depth first search.  */
+    int *rc_order;
   } cfg;
 
   /* Headers shared by multiple loops that should be merged.  */
diff --git a/gcc/flow.c b/gcc/flow.c
index 7749d89bc98..0d27ed9a977 100644
--- a/gcc/flow.c
+++ b/gcc/flow.c
@@ -397,7 +397,7 @@ static void flow_loops_cfg_dump		PARAMS ((const struct loops *, FILE *));
 static int flow_loop_nested_p		PARAMS ((struct loop *, struct loop *));
 static int flow_loop_exits_find		PARAMS ((const sbitmap, edge **));
 static int flow_loop_nodes_find	PARAMS ((basic_block, basic_block, sbitmap));
-static int flow_depth_first_order_compute PARAMS ((int *));
+static int flow_depth_first_order_compute PARAMS ((int *, int *));
 static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *));
 static void flow_loop_tree_node_add	PARAMS ((struct loop *, struct loop *));
 static void flow_loops_tree_build	PARAMS ((struct loops *));
@@ -7070,6 +7070,14 @@ flow_loops_cfg_dump (loops, file)
 	fprintf (file, "%d ", loops->cfg.dfs_order[i]);
       fputs ("\n", file);
     }
+  /* Dump the reverse completion node order.  */
+  if (loops->cfg.rc_order)
+    {
+      fputs (";; RC order: ", file);
+      for (i = 0; i < n_basic_blocks; i++)
+	fprintf (file, "%d ", loops->cfg.rc_order[i]);
+      fputs ("\n", file);
+    }
 }
 
 
@@ -7135,7 +7143,8 @@ flow_loops_dump (loops, file, verbose)
 		     must be disjoint.  */
 		  disjoint = ! flow_loop_nested_p (smaller ? loop : oloop,
 						   smaller ? oloop : loop);
-		  fprintf (file, ";; loop header %d shared by loops %d, %d %s\n",
+		  fprintf (file, 
+			   ";; loop header %d shared by loops %d, %d %s\n",
 			   loop->header->index, i, j,
 			   disjoint ? "disjoint" : "nested");
 		}
@@ -7307,16 +7316,20 @@ flow_loop_nodes_find (header, latch, nodes)
 
 
 /* Compute the depth first search order and store in the array
-   DFS_ORDER, marking the nodes visited in VISITED.  Returns the
-   number of nodes visited.  A depth first search tries to get as far
-   away from the starting point as quickly as possible.  */
+  DFS_ORDER if non-zero, marking the nodes visited in VISITED.  If
+  RC_ORDER is non-zero, return the reverse completion number for each
+  node.  Returns the number of nodes visited.  A depth first search
+  tries to get as far away from the starting point as quickly as
+  possible.  */
 static int
-flow_depth_first_order_compute (dfs_order)
+flow_depth_first_order_compute (dfs_order, rc_order)
      int *dfs_order;
+     int *rc_order;
 {
   edge *stack;
   int sp;
   int dfsnum = 0;
+  int rcnum = n_basic_blocks - 1;
   sbitmap visited;
 
   /* Allocate stack for back-tracking up CFG.  */
@@ -7348,6 +7361,9 @@ flow_depth_first_order_compute (dfs_order)
 	{
 	  /* Mark that we have visited the destination.  */
 	  SET_BIT (visited, dest->index);
+	  
+	  if (dfs_order)
+	    dfs_order[dfsnum++] = dest->index;
 
  	  if (dest->succ)
  	    {
@@ -7358,8 +7374,9 @@ flow_depth_first_order_compute (dfs_order)
  	  else
  	    {
  	      /* There are no successors for the DEST node so assign
- 		 its DFS number.  */
- 	      dfs_order[n_basic_blocks - ++dfsnum] = dest->index;
+ 		 its reverse completion number.  */
+	      if (rc_order)
+		rc_order[rcnum--] = dest->index;
  	    }
 	}
       else
@@ -7367,8 +7384,9 @@ flow_depth_first_order_compute (dfs_order)
 	  if (! e->succ_next && src != ENTRY_BLOCK_PTR)
   	    {
  	      /* There are no more successors for the SRC node
- 		 so assign its DFS number.  */
- 	      dfs_order[n_basic_blocks - ++dfsnum] = src->index;
+ 		 so assign its reverse completion number.  */
+	      if (rc_order)
+		rc_order[rcnum--] = src->index;
   	    }
 	  
 	  if (e->succ_next)
@@ -7557,11 +7575,13 @@ flow_loops_find (loops)
   sbitmap headers;
   sbitmap *dom;
   int *dfs_order;
+  int *rc_order;
   
   loops->num = 0;
   loops->array = NULL;
   loops->tree = NULL;
   dfs_order = NULL;
+  rc_order = NULL;
 
   /* Taking care of this degenerate case makes the rest of
      this code simpler.  */
@@ -7602,7 +7622,8 @@ flow_loops_find (loops)
       /* Compute depth first search order of the CFG so that outer
 	 natural loops will be found before inner natural loops.  */
       dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
-      flow_depth_first_order_compute (dfs_order);
+      rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
+      flow_depth_first_order_compute (dfs_order, rc_order);
 
       /* Allocate loop structures.  */
       loops->array
@@ -7623,7 +7644,7 @@ flow_loops_find (loops)
 
 	  /* Search the nodes of the CFG in DFS order that we can find
 	     outer loops first.  */
-	  header = BASIC_BLOCK (dfs_order[b]);
+	  header = BASIC_BLOCK (rc_order[b]);
 	  
 	  /* Look for all the possible latch blocks for this header.  */
 	  for (e = header->pred; e; e = e->pred_next)
@@ -7645,6 +7666,7 @@ flow_loops_find (loops)
 		  
 		  loop->header = header;
 		  loop->latch = latch;
+		  loop->num = num_loops;
 		  
 		  /* Keep track of blocks that are loop headers so
 		     that we can tell which loops should be merged.  */
@@ -7696,6 +7718,7 @@ flow_loops_find (loops)
   /* Save CFG derived information to avoid recomputing it.  */
   loops->cfg.dom = dom;
   loops->cfg.dfs_order = dfs_order;
+  loops->cfg.rc_order = rc_order;
 
   /* Build the loop hierarchy tree.  */
   flow_loops_tree_build (loops);