Patch to implement flow_preorder_transversal_compute for VRP

[John Wehle <john at feith dot com>]

flow_preorder_transversal_compute is a generic support routine
used by VRP to compute a preorder transversal ordering which
(among other things) can be used for easy detection of all the
entry blocks for a loop.  It may be useful elsewhere.

This patch (combined with VRP) passes make bootstrap and make check
on Dec Alpha 4.0f, Solaris 7 SPARC, and Solaris 7 x86.

ChangeLog:

Mon Dec 10 13:04:38 EST 2001  John Wehle  (john@feith.com)

	* basic-block.h (flow_preorder_transversal_compute): Declare.
	* cfganal.c (flow_preorder_transversal_compute): Implement.

Enjoy!

-- John Wehle
------------------8<------------------------8<------------------------
*** gcc/basic-block.h.ORIGINAL	Thu Nov 29 12:26:10 2001
--- gcc/basic-block.h	Mon Dec 10 13:10:48 2001
*************** extern void tidy_fallthru_edge		PARAMS (
*** 321,326 ****
--- 321,327 ----
  extern void tidy_fallthru_edges		PARAMS ((void));
  extern void flow_reverse_top_sort_order_compute	PARAMS ((int *));
  extern int flow_depth_first_order_compute	PARAMS ((int *, int *));
+ extern void flow_preorder_transversal_compute	PARAMS ((int *));
  extern void dump_edge_info		PARAMS ((FILE *, edge, int));
  extern void clear_edges			PARAMS ((void));
  extern void mark_critical_edges		PARAMS ((void));
*** gcc/cfganal.c.ORIGINAL	Thu Nov 29 12:26:11 2001
--- gcc/cfganal.c	Mon Dec 10 13:14:22 2001
*************** flow_depth_first_order_compute (dfs_orde
*** 919,924 ****
--- 921,1052 ----
    if (dfsnum < n_basic_blocks)
      abort ();
    return dfsnum;
+ }
+ 
+ struct dfst_node {
+     unsigned nnodes;
+     struct dfst_node **node;
+     struct dfst_node *up;
+ };
+ 
+ /* Compute a preorder transversal ordering such that a sub-tree which
+    is the source of a cross edge appears before the sub-tree which is
+    the destination of the cross edge.  This allows for easy detection
+    of all the entry blocks for a loop.
+ 
+    The ordering is compute by:
+ 
+      1) Generating a depth first spanning tree.
+ 
+      2) Walking the resulting tree from right to left.  */
+ 
+ void
+ flow_preorder_transversal_compute (pot_order)
+      int *pot_order;
+ {
+   edge e;
+   edge *stack;
+   int i;
+   int max_successors;
+   int sp;
+   sbitmap visited;
+   struct dfst_node *node;
+   struct dfst_node *dfst;
+ 
+   /* Allocate stack for back-tracking up CFG.  */
+   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+   sp = 0;
+ 
+   /* Allocate the tree.  */
+   dfst
+     = (struct dfst_node *) xcalloc (n_basic_blocks, sizeof (struct dfst_node));
+   for (i = 0; i < n_basic_blocks; i++)
+     {
+       max_successors = 0;
+       for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
+ 	max_successors++;
+       dfst[i].node = max_successors ? (struct dfst_node **)
+ 				      xcalloc (max_successors,
+ 					       sizeof (struct dfst_node *))
+ 			    : NULL;
+     }
+ 
+   /* 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)
+     {
+       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);
+ 
+ 	  /* Add the destination to the preorder tree.  */
+ 	  if (src != ENTRY_BLOCK_PTR)
+ 	    {
+ 	      dfst[src->index].node[dfst[src->index].nnodes++]
+ 		= &dfst[dest->index];
+ 	      dfst[dest->index].up = &dfst[src->index];
+ 	    }
+ 
+ 	  if (dest->succ)
+ 	    {
+ 	      /* Since the DEST node has been visited for the first
+ 		 time, check its successors.  */
+ 	      stack[sp++] = dest->succ;
+ 	    }
+ 	}
+       else
+ 	{
+ 	  if (e->succ_next)
+ 	    stack[sp - 1] = e->succ_next;
+ 	  else
+ 	    sp--;
+ 	}
+     }
+ 
+   free (stack);
+   sbitmap_free (visited);
+ 
+   /* Record the preorder transversal order by
+      walking the tree from right to left.  */
+ 
+   i = 0;
+   node = &dfst[0];
+   pot_order[i++] = 0;
+ 
+   while (node)
+     {
+       if (node->nnodes)
+ 	{
+ 	  node = node->node[--node->nnodes];
+ 	  pot_order[i++] = node - dfst;
+ 	}
+       else
+ 	node = node->up;
+     }
+ 
+   /* Free the tree.  */
+ 
+   for (i = 0; i < n_basic_blocks; i++)
+     if (dfst[i].node)
+       free (dfst[i].node);
+   free (dfst);
  }
  
  /* Compute the depth first search order on the _reverse_ graph and
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------