[cfg-branch] STC - avoid infinite loop in copy_bb_p

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

Hi,

this patch fixes bug in copy_bb_p that caused infinite loop, when there was a loop in CFG that did not have any instructions (jumps were removed by cfg_layout_initialize (); ).
It also fixes the situation when calling copy_bb_p(A):

 A
 |
 B
 |
 C<<
 | ^
 \_/

When the sum of instructions of A+B+C is quite small, the trace should be copied and it is copied by this patch. Previous version counted A+B+C+C+C+C+C+C+C...... and the size grew over the limit and copy_bb_p returned false.

Bootstrapped on i686.

Joe


2002-01-23  Josef Zlomek  <zlomek@matfyz.cz>

	bb-reorder.c (copy_bb_p): bug fix: avoid infinite loop.


*** gcc-old/gcc/bb-reorder.c	Mon Jan 14 22:49:21 2002
--- gcc-new/gcc/bb-reorder.c	Wed Jan 23 11:29:09 2002
*************** static int exec_threshold[N_ROUNDS] = {5
*** 52,57 ****
--- 52,64 ----
  /* Length of unconditional jump instruction.  */
  static int uncond_jump_length;
  
+ /* Array of flags that the bb was visited in copy_bb_p to avoid infinite
+    loop.  */
+ static unsigned int *copy_bb_p_visited;
+ 
+ /* The size of the previous array.  */
+ static int copy_bb_p_visited_size;
+ 
  struct trace
  {
    /* First and last basic block of the trace.  */
*************** find_traces_1_round (branch_th, exec_th,
*** 378,383 ****
--- 385,402 ----
  		  RBI (bb)->next = new_bb;
  		  RBI (bb)->visited = *n_traces;
  		  bb = new_bb;
+ 
+ 		  if (n_basic_blocks > copy_bb_p_visited_size)
+ 		    {
+ 		      /* Realloc the COPY_BB_P_VISITED array, copying of data
+ 		         is not necessary.  */
+ 		      free (copy_bb_p_visited);
+   		      copy_bb_p_visited_size = 4 * n_basic_blocks / 3;
+ 		      copy_bb_p_visited = xcalloc (copy_bb_p_visited_size,
+ 			  			   sizeof (unsigned int));
+ 		      if (!copy_bb_p_visited)
+ 			abort ();
+ 		    }
  		}
  	      else
  		{
*************** copy_bb_p (bb, trace, size_can_grow)
*** 484,491 ****
  {
    int size = 0;
    rtx insn;
!   basic_block first = bb;
  
    if (!bb->frequency)
      return false;
    if (!bb->pred || !bb->pred->pred_next)
--- 503,523 ----
  {
    int size = 0;
    rtx insn;
!   static unsigned int id;
! 
!   if (id == UINT_MAX)
!     {
!       int i;
  
+       id = 1;
+       /* We are starting again with ID 1 so clear the flags.  */
+       for (i = 0; i < copy_bb_p_visited_size; i++)
+ 	copy_bb_p_visited[i] = 0;
+     }
+   else
+     id++;
+     
+   
    if (!bb->frequency)
      return false;
    if (!bb->pred || !bb->pred->pred_next)
*************** copy_bb_p (bb, trace, size_can_grow)
*** 496,501 ****
--- 528,535 ----
        int prob_lower, prob_higher;
        int freq_lower, freq_higher;
  
+       copy_bb_p_visited[bb->index] = id;
+ 
        if (RBI (bb)->visited == trace)
  	return false;
        if (!cfg_layout_can_duplicate_bb_p (bb))
*************** copy_bb_p (bb, trace, size_can_grow)
*** 529,538 ****
  	    best_edge = e;
  	}
        if (!best_edge || !RBI (best_edge->dest)->visited
! 	  || RBI (best_edge->dest)->visited == trace)
  	/* All edges point to EXIT_BLOCK or to the same trace
  	   OR the selected successor has not been visited yet
! 	   OR we have found a loop (so the trace will be terminated).  */
  	{
  	  if (size_can_grow || size <= uncond_jump_length)
  	    return true;
--- 563,575 ----
  	    best_edge = e;
  	}
        if (!best_edge || !RBI (best_edge->dest)->visited
! 	  || RBI (best_edge->dest)->visited == trace
! 	  || copy_bb_p_visited[best_edge->dest->index] == id)
  	/* All edges point to EXIT_BLOCK or to the same trace
  	   OR the selected successor has not been visited yet
! 	   OR we have found a loop (so the trace will be terminated)
! 	   OR we have reached the bb that was already visited
! 	      in this run of copy_bb_p.  */
  	{
  	  if (size_can_grow || size <= uncond_jump_length)
  	    return true;
*************** copy_bb_p (bb, trace, size_can_grow)
*** 540,547 ****
  	    return false;
  	}
        bb = best_edge->dest;
-       if (bb == first)
- 	return false;
      }
    return false;
  }
--- 577,582 ----
*************** reorder_basic_blocks ()
*** 574,583 ****
--- 609,625 ----
  
    cfg_layout_initialize ();
  
+   copy_bb_p_visited_size = MAX (4 * n_basic_blocks / 3, 10);
+   copy_bb_p_visited = xcalloc (copy_bb_p_visited_size, sizeof (unsigned int));
+   if (!copy_bb_p_visited)
+     abort ();
+   
    set_edge_can_fallthru_flag ();
    uncond_jump_length = get_uncond_jump_length ();
    find_traces ();
  
+   free (copy_bb_p_visited);
+ 
    if (rtl_dump_file)
      dump_flow_info (rtl_dump_file);