loop exit predictor tweek

[Jan Hubicka <jh at suse dot cz>]

Hi,
our current code to propagate edge probabilities into bb frequencies has one
interesting property - the loops decrease number of iteration exponentially
according to the number of exit edges.  This is bit unfortunate, as we
predict loop to iterate about 8 times at average and thus loop with 4 exit
edges is already predicted to iterate less than once making some later
optimizations to jump into strange conclusions.

This patch solves it by decreasing the probability of exit edge according to
the number of exits so each loop is predicted to iterate approx. equivalent
amount of times.  This is consistent to what is done in Wu and Larus paper.

Andreas has benchmarked it and got slight improvements and since it makes
the profiles to look saner, I would install it even when it does not
perfectly fit the teoretical background.

Bootstrapped/regtested mainline, installed to branch.

Wed Dec 12 14:15:48 CET 2001  Jan Hubicka  <jh@suse.cz>

	* predict.c (estimate_probability): Distribute the loop exit
	probability according to number of exit edges.

Index: predict.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.c,v
retrieving revision 1.44.2.11
diff -c -3 -p -r1.44.2.11 predict.c
*** predict.c	2001/12/12 12:58:42	1.44.2.11
--- predict.c	2001/12/12 13:17:09
*************** estimate_probability (loops_info)
*** 353,364 ****
    for (i = 0; i < loops_info->num; i++)
      {
        int j;
  
!       for (j = loops_info->array[i].first->index;
! 	   j <= loops_info->array[i].last->index;
  	   ++j)
  	{
! 	  if (TEST_BIT (loops_info->array[i].nodes, j))
  	    {
  	      int header_found = 0;
  	      edge e;
--- 353,369 ----
    for (i = 0; i < loops_info->num; i++)
      {
        int j;
+       int exits;
+       struct loop *loop = &loops_info->array[i];
  
!       flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES);
!       exits = loop->num_exits;
! 
!       for (j = loop->first->index;
! 	   j <= loop->last->index;
  	   ++j)
  	{
! 	  if (TEST_BIT (loop->nodes, j))
  	    {
  	      int header_found = 0;
  	      edge e;
*************** estimate_probability (loops_info)
*** 373,380 ****
  	      /* Loop branch heuristics - predict as taken an edge back to
  	         a loop's head.  */
  	      for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
! 		if (e->dest == loops_info->array[i].header
! 		    && e->src == loops_info->array[i].latch)
  		  {
  		    header_found = 1;
  		    predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
--- 378,385 ----
  	      /* Loop branch heuristics - predict as taken an edge back to
  	         a loop's head.  */
  	      for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
! 		if (e->dest == loop->header
! 		    && e->src == loop->latch)
  		  {
  		    header_found = 1;
  		    predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
*************** estimate_probability (loops_info)
*** 385,392 ****
  	      if (!header_found)
  		for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
  		  if (e->dest->index <= 0
! 		      || !TEST_BIT (loops_info->array[i].nodes, e->dest->index))
! 		    predict_edge_def (e, PRED_LOOP_EXIT, NOT_TAKEN);
  	    }
  	}
      }
--- 390,400 ----
  	      if (!header_found)
  		for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
  		  if (e->dest->index <= 0
! 		      || !TEST_BIT (loop->nodes, e->dest->index))
! 		    predict_edge (e, PRED_LOOP_EXIT,
! 				  (REG_BR_PROB_BASE
! 				   - predictor_info [(int)PRED_LOOP_EXIT].hitrate)
! 				  / exits);
  	    }
  	}
      }