[rtlopt] bb-reorder: prefer successors of last block of a trace

[Josef Zlomek <zlomj9am at artax dot karlin dot mff dot cuni dot cz>]

Hi,

this patch changes the order of selecting seeds (startpoints) for
constructing traces (it changes the computation of the heap key).
Now the basic blocks that are successors of the last block of some
trace are prefered.

This should fix majority of regressions of STC (the flowgraphs of hot
functions look better with this patch).

Bootstrapped i386.

Andreas, please could you benchmark it?
Base: rtlopt-branch
Peak: rtlopt-branch + this patch
Flags: -O2 -march=athlon -malign-double -funroll-all-loops
Once without PDO, once with PDO.

Josef


Wed Nov 27 18:24:30 CET 2002  Josef Zlomek <zlomj9am@artax.karlin.mff.cuni.cz>

	* bb-reorder.c (bb_to_key): prefer successors of the last block of
	some trace.

Index: gcc/bb-reorder.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/bb-reorder.c,v
retrieving revision 1.50.2.7
diff -u -c -3 -p -r1.50.2.7 bb-reorder.c
*** gcc/bb-reorder.c	26 Nov 2002 15:27:09 -0000	1.50.2.7
--- gcc/bb-reorder.c	27 Nov 2002 17:18:39 -0000
*************** find_traces_1_round (branch_th, exec_th,
*** 259,264 ****
--- 259,266 ----
        basic_block bb;
        struct trace *trace;
        edge best_edge, e;
+       int bb_index;
+       fibheapkey_t key;
  
        bb = fibheap_extract_min (*heap);
        bb_heap[bb->index] = NULL;
*************** find_traces_1_round (branch_th, exec_th,
*** 338,352 ****
  	  /* Add all nonselected successors to the heaps.  */
  	  for (e = bb->succ; e; e = e->succ_next)
  	    {
- 	      int bb_index = e->dest->index;
- 	      fibheapkey_t key;
- 
  	      if (e == best_edge
  		  || e->dest == EXIT_BLOCK_PTR
  		  || RBI (e->dest)->visited)
  		continue;
  
  	      key = bb_to_key (e->dest);
  
  	      if (bb_heap[bb_index])
  		{
--- 340,352 ----
  	  /* Add all nonselected successors to the heaps.  */
  	  for (e = bb->succ; e; e = e->succ_next)
  	    {
  	      if (e == best_edge
  		  || e->dest == EXIT_BLOCK_PTR
  		  || RBI (e->dest)->visited)
  		continue;
  
  	      key = bb_to_key (e->dest);
+ 	      bb_index = e->dest->index;
  
  	      if (bb_heap[bb_index])
  		{
*************** find_traces_1_round (branch_th, exec_th,
*** 512,517 ****
--- 512,544 ----
        trace->last = bb;
        start_of_trace[trace->first->index] = *n_traces - 1;
        end_of_trace[trace->last->index] = *n_traces - 1;
+ 
+       /* The trace is derminated so we have to recount the keys in heap
+ 	 (some block can have a lower key because now one of its predecessors is
+ 	 an end of trace.  */
+       for (e = bb->succ; e; e = e->succ_next)
+ 	{
+ 	  if (e->dest == EXIT_BLOCK_PTR
+ 	      || RBI (e->dest)->visited)
+ 	    continue;
+ 	  
+ 	  bb_index = e->dest->index;
+ 	  if (bb_heap[bb_index])
+ 	    {
+ 	      key = bb_to_key (e->dest);
+ 	      if (key != bb_node[bb_index]->key)
+ 		{
+ 		  if (rtl_dump_file)
+ 		    {
+ 		      fprintf (rtl_dump_file,
+ 			       "Changing key for bb %d from %ld to %ld.\n",
+ 			       bb_index, (long) bb_node[bb_index]->key, key);
+ 		    }
+ 		  fibheap_replace_key (bb_heap[bb_index], bb_node[bb_index],
+ 				       key);
+ 		}
+ 	    }
+ 	}
      }
  
    fibheap_delete (*heap);
*************** bb_to_key (bb)
*** 555,586 ****
       basic_block bb;
  {
    edge e;
! 
!   int priority = 2;
  
    if (probably_never_executed_bb_p (bb))
      return BB_FREQ_MAX;
  
!   for (e = bb->pred; e; e = e->pred_next)
!     if (!(e->flags & EDGE_DFS_BACK) && !RBI (e->src)->visited)
!       {
! 	priority = 0;
! 	break;
!       }
! 
    for (e = bb->pred; e; e = e->pred_next)
      {
        int index = e->src->index;
        if (end_of_trace[index] >= 0)
  	{
! 	  priority++;
! 	  break;
  	}
      }
  
!   /* All edges from predecessors of BB are DFS back edges or the predecessors
!      of BB are visited.  I want such basic blocks first.  */
!   return -100 * BB_FREQ_MAX * priority - bb->frequency;
  }
  
  /* Return true when the edge E from basic block BB is better than the temporary
--- 582,609 ----
       basic_block bb;
  {
    edge e;
!   int priority = 0;
  
    if (probably_never_executed_bb_p (bb))
      return BB_FREQ_MAX;
  
!   /* Prefer blocks whose predecessor is an end of some trace.  */
    for (e = bb->pred; e; e = e->pred_next)
      {
        int index = e->src->index;
        if (end_of_trace[index] >= 0)
  	{
! 	  int edge_freq = EDGE_FREQUENCY (e);
! 
! 	  if (edge_freq > priority)
! 	    priority = edge_freq;
  	}
      }
  
!   if (priority)		
!     /* The block with priority should have significantly lower key.  */
!     return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
!   return -bb->frequency;
  }
  
  /* Return true when the edge E from basic block BB is better than the temporary