[PATCH] Improve updating of frequencies in unswitching

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

this patch improves updating of frequencies of blocks when a path
is removed, which helps to keep them consistent after unswitching.

Bootstrapped in i686.

Zdenek

	* basic-block.h (RDIV): New.
	(EDGE_FREQUENCY): Use it.
	* cfgloopmanip.c (remove_path): Update frequencies on the other
	path.
	(scale_bbs_frequencies): Use RDIV.
	(RDIV): Moved to basic-block.h.

Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.179
diff -c -3 -p -r1.179 basic-block.h
*** basic-block.h	26 Jun 2003 06:13:27 -0000	1.179
--- basic-block.h	26 Jun 2003 15:24:04 -0000
*************** struct edge_list
*** 444,454 ****
  #define BRANCH_EDGE(bb)			((bb)->succ->flags & EDGE_FALLTHRU \
  					 ? (bb)->succ->succ_next : (bb)->succ)
  
  /* Return expected execution frequency of the edge E.  */
! #define EDGE_FREQUENCY(e)		(((e)->src->frequency \
! 					  * (e)->probability \
! 					  + REG_BR_PROB_BASE / 2) \
! 					 / REG_BR_PROB_BASE)
  
  /* Return nonzero if edge is critical.  */
  #define EDGE_CRITICAL_P(e)		((e)->src->succ->succ_next \
--- 444,455 ----
  #define BRANCH_EDGE(bb)			((bb)->succ->flags & EDGE_FALLTHRU \
  					 ? (bb)->succ->succ_next : (bb)->succ)
  
+ /* round (X/Y) */
+ #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
+ 
  /* Return expected execution frequency of the edge E.  */
! #define EDGE_FREQUENCY(e) (RDIV ((e)->src->frequency * (e)->probability, \
! 				 REG_BR_PROB_BASE))
  
  /* Return nonzero if edge is critical.  */
  #define EDGE_CRITICAL_P(e)		((e)->src->succ->succ_next \
Index: cfgloopmanip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopmanip.c,v
retrieving revision 1.9
diff -c -3 -p -r1.9 cfgloopmanip.c
*** cfgloopmanip.c	22 Jun 2003 15:03:26 -0000	1.9
--- cfgloopmanip.c	26 Jun 2003 15:24:04 -0000
*************** fix_irreducible_loops (basic_block from)
*** 340,349 ****
  bool
  remove_path (struct loops *loops, edge e)
  {
!   edge ae;
!   basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
!   int i, nrem, n_bord_bbs, n_dom_bbs;
    sbitmap seen;
  
    if (!loop_delete_branch_edge (e, 0))
      return false;
--- 340,350 ----
  bool
  remove_path (struct loops *loops, edge e)
  {
!   edge ae, other;
!   basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb, *other_part;
!   int i, nrem, n_bord_bbs, n_dom_bbs, n_other_part;
    sbitmap seen;
+   int scale;
  
    if (!loop_delete_branch_edge (e, 0))
      return false;
*************** remove_path (struct loops *loops, edge e
*** 364,371 ****
--- 365,387 ----
  			    e->src->loop_father->latch, e->dest))
      unloop (loops, e->src->loop_father);
  
+   /* We can only be called for simple conditional jumps; not really a
+      principial restriction, but it makes things a bit simpler.  */
+   if (e->src->succ->succ_next->succ_next)
+     abort ();
+   other = e->src->succ;
+   if (other == e)
+     other = other->succ_next;
+   if (other->dest->pred->pred_next)
+     other = loop_split_edge_with (other, NULL_RTX, loops)->pred;
+   if (other->probability == 0)
+     scale = 10;
+   else
+     scale = RDIV (10 * REG_BR_PROB_BASE, other->probability);
+ 
    /* Identify the path.  */
    nrem = find_path (e, loops->cfg.dom, &rem_bbs);
+   n_other_part = find_path (other, loops->cfg.dom, &other_part);
  
    n_bord_bbs = 0;
    bord_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
*************** remove_path (struct loops *loops, edge e
*** 437,442 ****
--- 453,462 ----
    fix_bb_placements (loops, from);
    fix_loop_placements (from->loop_father);
  
+   /* Fix frequencies of other affected blocks.  */
+   scale_bbs_frequencies (other_part, n_other_part, scale, 10);
+   free (other_part);
+ 
    return true;
  }
  
*************** scale_bbs_frequencies (basic_block *bbs,
*** 481,490 ****
  
    for (i = 0; i < nbbs; i++)
      {
!       bbs[i]->frequency = (bbs[i]->frequency * num) / den;
!       bbs[i]->count = (bbs[i]->count * num) / den;
        for (e = bbs[i]->succ; e; e = e->succ_next)
! 	e->count = (e->count * num) /den;
      }
  }
  
--- 501,510 ----
  
    for (i = 0; i < nbbs; i++)
      {
!       bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
!       bbs[i]->count = RDIV (bbs[i]->count * num, den);
        for (e = bbs[i]->succ; e; e = e->succ_next)
! 	e->count = RDIV (e->count * num, den);
      }
  }
  
*************** record_exit_edges (edge orig, basic_bloc
*** 1019,1027 ****
        free (my_blocks);
      }
  }
- 
- 
- #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
  
  /* Duplicates body of LOOP to given edge E NDUPL times.  Takes care of
     updating LOOPS structure and dominators.  E's destination must be LOOP
--- 1039,1044 ----