[cfg-branch] bb-reorder: do not connect traces too early

[Josef Zlomek <josef dot zlomek at email dot cz>]

Hello,

this patch removes the early trace connecting that was added to avoid
unnecesary duplication of multiple function exits. But it has slowed
down egcs benchmark. So I'm removing it again. The speedup is about 3%
on egcs benchmark with K6-2 procesor (there is almost no effect on SPEC2000
with athlon as measured several months ago when early connecting was added).

For Honza:
I'm thinking about a partial rewrite of bb-reorder.
First it would find simple traces (i.e. perform no duplication in this stage)
and then connect the traces directly, or by duplication of 1 bb between the end
of one trace and the beginning of another or the end of function.
I think duplication of 1 bb is enough and it would work well for branches, I'm
not sure about loops, especially difficult ones - with several exits and back
edges (break and continue statements).

Branches:
original CFG    Simple traces         Connected traces
  
  A             A                       A
 / \            |                       |
B   C           B  C                    B  C
 \ /            |                       |  |
  D      ===>   D              ====>    D  D
 / \            |                       |  |
E   F           E     F                 E  F
 \ /            |                       |  |
  G             G                       G  G

                Some edges are not shown to make picture clear.

simple loop:
   A               A                     A
   |               |                     |
/->H--\            H                     H
|  |  |   ====>    |           ===>      |
\--L  |            L                     L
      |                  E               |
      E                                  H
                                         |
                                         E
Of course, we can rotate the loop before.

Bootstrapped i386 (K6-2)

Josef


Mon Aug 19 16:13:24 CEST 2002
Josef Zlomek <josef.zlomek@email.cz>

	* bb-reorder.c (find_traces_1_round): remove early trace connecting

*** gcc-old/gcc/bb-reorder.c	Mon Aug 19 15:36:57 2002
--- gcc-new/gcc/bb-reorder.c	Mon Aug 19 15:40:57 2002
*************** find_traces_1_round (branch_th, exec_th,
*** 546,572 ****
  		}
  	      else if (RBI (best_edge->dest)->visited)
  		{
- 		  /* We don't want to insert something before first BB of the
- 		     function.  */
- 		  if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb
- 		      /* start_of_trace is not initialized for new blocks,
- 		         but this is not problem, since new blocks are not
- 		         first blocks of any trace anyway.  */
- 		      && best_edge->dest->index < original_last_basic_block
- 		      && start_of_trace[best_edge->dest->index] >= 0)
- 		    {
- 		      int succ = start_of_trace[best_edge->dest->index];
- 
- 		      /* Link the traces.  */
- 		      trace->succ = succ;
- 		      traces[succ].pred = *n_traces - 1;
- 		      start_of_trace[best_edge->dest->index] = -1;
- 
- 		      /* Terminate the trace.  */
- 		      trace->last = bb;
- 		      break;
- 		    }
- 
  		  bb = duplicate_basic_block (best_edge->dest, best_edge, bb,
  					*n_traces);
  		}
--- 546,551 ----