2001-08-28 Daniel Berlin <dan@cgsoftware.com>

	* df.h (struct df): Add rts_order variable.

	* df.c (df_visit_next_rts): New function.
	(df_visit_next): Renamed to df_visit_next_rc
	(df_analyse_1): Allocate/compute/free rts_order as well.
	(df_rd_global_compute): Use df_visit_next_rc instead of
	df_visit_next.
	(df_ru_global_compute): Use df_visit_next_rts instead of
	df_visit_next.

	* flow.c (flow_reverse_top_sort_order_compute): New function.

	* basic-block.h: Add prototype.


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

5 files changed, 108 insertions, 6 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 7ecd770706d..648b5f5cef6 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,21 @@
 2001-08-28  Daniel Berlin  <dan@cgsoftware.com>
 
+	* df.h (struct df): Add rts_order variable.
+
+	* df.c (df_visit_next_rts): New function.
+	(df_visit_next): Renamed to df_visit_next_rc
+	(df_analyse_1): Allocate/compute/free rts_order as well.
+	(df_rd_global_compute): Use df_visit_next_rc instead of
+	df_visit_next.
+	(df_ru_global_compute): Use df_visit_next_rts instead of
+	df_visit_next.
+	
+	* flow.c (flow_reverse_top_sort_order_compute): New function.
+
+	* basic-block.h: Add prototype.
+
+2001-08-28  Daniel Berlin  <dan@cgsoftware.com>
+
 	* ssa-ccp.c (ssa_ccp_df_delete_unreachable_insns): For unreachable
 	blocks, the BB_REACHABLE is now set, rather than aux being
 	non-NULL. Update the test to reflect this.
diff --git a/gcc/basic-block.h b/gcc/basic-block.h
index 295748b3034..b8754948fec 100644
--- a/gcc/basic-block.h
+++ b/gcc/basic-block.h
@@ -310,6 +310,7 @@ extern int flow_delete_block		PARAMS ((basic_block));
 extern void merge_blocks_nomove		PARAMS ((basic_block, basic_block));
 extern void tidy_fallthru_edge		PARAMS ((edge, basic_block,
 						 basic_block));
+extern void flow_reverse_top_sort_order_compute	PARAMS ((int *));
 extern int flow_depth_first_order_compute	PARAMS ((int *, int *));
 extern void dump_edge_info		PARAMS ((FILE *, edge, int));
 extern void clear_edges			PARAMS ((void));
diff --git a/gcc/df.c b/gcc/df.c
index 6f1b18f952e..177da105126 100644
--- a/gcc/df.c
+++ b/gcc/df.c
@@ -238,7 +238,8 @@ static void df_insn_refs_record PARAMS((struct df *, basic_block, rtx));
 static void df_bb_refs_record PARAMS((struct df *, basic_block));
 static void df_refs_record PARAMS((struct df *, bitmap));
 
-static int df_visit_next PARAMS ((struct df *, sbitmap));
+static int df_visit_next_rc PARAMS ((struct df *, sbitmap));
+static int df_visit_next_rts PARAMS ((struct df *, sbitmap));
 static void df_bb_reg_def_chain_create PARAMS((struct df *, basic_block));
 static void df_reg_def_chain_create PARAMS((struct df *, bitmap));
 static void df_bb_reg_use_chain_create PARAMS((struct df *, basic_block));
@@ -1600,11 +1601,11 @@ df_ud_chain_create (df, blocks)
 }
 
 
-/* Use depth first order, and the worklist, to figure out what block
+/* Use reverse completion order, and the worklist, to figure out what block
    to look at next.  */
 
 static int
-df_visit_next (df, blocks)
+df_visit_next_rc (df, blocks)
      struct df *df ATTRIBUTE_UNUSED;
      sbitmap blocks;
 {
@@ -1615,6 +1616,22 @@ df_visit_next (df, blocks)
   return sbitmap_first_set_bit (blocks);
 }
 
+/* Use reverse topsort order, and the worklist, to figure out what block
+   to look at next.  */
+
+static int
+df_visit_next_rts (df, blocks)
+     struct df *df ATTRIBUTE_UNUSED;
+     sbitmap blocks;
+{
+  int i=0;
+  for (i = 0; i < n_basic_blocks; i++)
+    if (TEST_BIT (blocks, df->rts_order[i]))
+      return df->rts_order[i];
+  return sbitmap_first_set_bit (blocks);
+}
+
+
 /* Calculate reaching defs for each basic block in BLOCKS, i.e., the
    defs that are live at the start of a basic block.  */
 static void
@@ -1644,7 +1661,7 @@ df_rd_global_compute (df, blocks)
       bitmap_copy (bb_info->rd_out, bb_info->rd_gen);
     });
   
-  while ((i = df_visit_next (df, worklist)) >= 0)
+  while ((i = df_visit_next_rc (df, worklist)) >= 0)
     {
       struct bb_info *bb_info;
       edge e;
@@ -1722,7 +1739,7 @@ df_ru_global_compute (df, blocks)
     });
 
 
-  while ((i = df_visit_next (df, worklist)) >= 0)
+  while ((i = df_visit_next_rts (df, worklist)) >= 0)
     {
       struct bb_info *bb_info;
       edge e;
@@ -2221,9 +2238,10 @@ df_analyse_1 (df, blocks, flags, update)
 
   df->dfs_order = xmalloc (sizeof(int) * n_basic_blocks);
   df->rc_order = xmalloc (sizeof(int) * n_basic_blocks);
+  df->rts_order = xmalloc (sizeof(int) * n_basic_blocks);
   
   flow_depth_first_order_compute (df->dfs_order, df->rc_order);
-
+  flow_reverse_top_sort_order_compute (df->rts_order);
   if (aflags & DF_RD)
     {
       /* Compute the sets of gens and kills for the defs of each bb.  */
@@ -2280,6 +2298,7 @@ df_analyse_1 (df, blocks, flags, update)
     } 
   free (df->dfs_order);
   free (df->rc_order);
+  free (df->rts_order);
 }
 
 
diff --git a/gcc/df.h b/gcc/df.h
index 3169e3faae0..c550afaee67 100644
--- a/gcc/df.h
+++ b/gcc/df.h
@@ -140,6 +140,7 @@ struct df
   bitmap *dom;
   int * dfs_order;
   int * rc_order;
+  int * rts_order;
 };
 
 
diff --git a/gcc/flow.c b/gcc/flow.c
index d2f37e5f2d4..8ca087757dd 100644
--- a/gcc/flow.c
+++ b/gcc/flow.c
@@ -9466,6 +9466,71 @@ flow_loop_nodes_find (header, latch, nodes)
   return num_nodes;
 }
 
+/* Compute reverse top sort order */
+void
+flow_reverse_top_sort_order_compute (rts_order)
+     int *rts_order;
+{
+  edge *stack;
+  int sp;
+  int postnum = 0;
+  sbitmap visited;
+
+  /* Allocate stack for back-tracking up CFG.  */
+  stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+  sp = 0;
+
+  /* Allocate bitmap to track nodes that have been visited.  */
+  visited = sbitmap_alloc (n_basic_blocks);
+
+  /* None of the nodes in the CFG have been visited yet.  */
+  sbitmap_zero (visited);
+
+  /* Push the first edge on to the stack.  */
+  stack[sp++] = ENTRY_BLOCK_PTR->succ;
+
+  while (sp)
+    {
+      edge e;
+      basic_block src;
+      basic_block dest;
+
+      /* Look at the edge on the top of the stack.  */
+      e = stack[sp - 1];
+      src = e->src;
+      dest = e->dest;
+
+      /* Check if the edge destination has been visited yet.  */
+      if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
+	{
+	  /* Mark that we have visited the destination.  */
+	  SET_BIT (visited, dest->index);
+
+	  if (dest->succ)
+	    {
+	      /* Since the DEST node has been visited for the first
+		 time, check its successors.  */
+	      stack[sp++] = dest->succ;
+	    }
+	  else
+	    rts_order[postnum++] = dest->index;
+	}
+      else
+	{
+	  if (! e->succ_next && src != ENTRY_BLOCK_PTR)
+	   rts_order[postnum++] = src->index;
+
+	  if (e->succ_next)
+	    stack[sp - 1] = e->succ_next;
+	  else
+	    sp--;
+	}
+    }
+
+  free (stack);
+  sbitmap_free (visited);
+}
+
 /* Compute the depth first search order and store in the array
   DFS_ORDER if non-zero, marking the nodes visited in VISITED.  If
   RC_ORDER is non-zero, return the reverse completion number for each