[cfg-branch] bb-reorder - connecting traces fix

[Josef Zlomek]

Hi,

this patch fixes the connection of traces in STC.
The connecting starts in bb 0. Given a chain of connected traces, if there is an edge from the last
block of the trace to the first block of another unconnected trace it is connected to chunk (if there are more such traces the most probable is selected).
If there is no such a trace the trace which was found earliest from all
unconnected traces is connected to chain.

Bootstrapped i686

Joe


Sun Apr  7 18:22:35 CEST 2002  Josef Zlomek <zlomek@matfyz.cz>

	* bb-reorder.c (find_traces): Fix connecting traces.

*** gcc-old/gcc/bb-reorder.c	Sun Apr  7 15:07:07 2002
--- gcc-new/gcc/bb-reorder.c	Sun Apr  7 16:05:39 2002
*************** find_traces ()
*** 128,133 ****
--- 128,135 ----
    basic_block bb0;
    fibheap_t heap;
    int *start_of_trace;
+   bool *connected;
+   int last_trace;
  
    /* There will be at most N_BASIC_BLOCKS traces because trace can start only
       in an original (not duplicated) basic block.  */
*************** find_traces ()
*** 171,204 ****
      start_of_trace[traces[i].first->index] = i;
  
    /* Connect traces.  */
!   for (i = 0; i < n_traces - 1; i++)
      {
!       edge e, best = NULL;
! 
!       for (e = traces[i].last->succ; e; e = e->succ_next)
! 	if (e->dest != EXIT_BLOCK_PTR
! 	    && (e->flags & EDGE_CAN_FALLTHRU)
! 	    && start_of_trace[e->dest->index] >= i + 1
! 	    && (!best || e->probability > best->probability))
! 	  best = e;
! 
!       if (best && start_of_trace[best->dest->index] != i + 1)
  	{
! 	  int t = start_of_trace[best->dest->index];
! 	  struct trace temp;
  
! 	  temp = traces[t];
! 	  traces[t] = traces[i + 1];
! 	  traces[i + 1] = temp;
! 	  start_of_trace[traces[i + 1].first->index] = i + 1;
! 	  start_of_trace[traces[t].first->index] = t;
  	}
- 
-       RBI (traces[i].last)->next = traces[i+1].first;
      }
  
!   free (traces);
    free (start_of_trace);
  }
  
  /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
--- 173,222 ----
      start_of_trace[traces[i].first->index] = i;
  
    /* Connect traces.  */
!   connected = xcalloc (n_traces, sizeof (bool));
!   last_trace = -1;
!   for (i = 0; i < n_traces; i++)
      {
!       if (!connected[i])
  	{
! 	  edge e, best;
  
! 	  /* Connect actual trace to a chain of already connected traces.  */
! 	  if (last_trace >= 0)
! 	    RBI (traces[last_trace].last)->next = traces[i].first;
! 	  connected[i] = true;
! 	  last_trace = i;
! 
! 	  /* Connect a chain of traces that concur.  */
! 	  for (;;)
! 	    {
! 	      int next_trace;
! 
! 	      best = NULL;
! 	      for (e = traces[i].last->succ; e; e = e->succ_next)
! 		{
! 		  if (e->dest != EXIT_BLOCK_PTR
! 		      && (e->flags & EDGE_CAN_FALLTHRU)
! 		      && start_of_trace[e->dest->index] >= 0
! 		      && !connected[start_of_trace[e->dest->index]]
! 		      && (!best || e->probability > best->probability))
! 		    best = e;
! 		}
! 
! 	      if (!best)
! 		break;
! 
! 	      next_trace = start_of_trace[best->dest->index];
! 	      RBI (traces[last_trace].last)->next = traces[next_trace].first;
! 	      connected[next_trace] = true;
! 	      last_trace = next_trace;
! 	    }
  	}
      }
  
!   free (connected);
    free (start_of_trace);
+   free (traces);
  }
  
  /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do