This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[rtlopt] Fix bb count updating


Hello,

this patch fixes completely broken updating of basic block frequencies
and counts during loop peeling/unrolling.

Zdenek

Changelog:
	* cfgloopmanip.c (duplicate_loop_to_header_edge): Fix count &
	frequencies updating.
	* loop-unroll.c (unroll_loop_runtime_iterations): Fix edge probabilities.

Index: loop-unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/loop-unroll.c,v
retrieving revision 1.1.2.8
diff -c -3 -p -r1.1.2.8 loop-unroll.c
*** loop-unroll.c	1 Nov 2002 19:20:57 -0000	1.1.2.8
--- loop-unroll.c	3 Nov 2002 00:31:26 -0000
*************** unroll_loop_runtime_iterations (loops, l
*** 267,278 ****
       struct loop_desc *desc;
  {
    rtx niter, init_code, branch_code, jump, label;
!   int i, j;
    basic_block preheader, *body, *dom_bbs, swtch, ezc_swtch;
    int n_dom_bbs;
    sbitmap wont_exit;
    int may_exit_copy, n_peel, n_remove_edges;
!   edge *remove_edges;
    bool extra_zero_check, last_may_exit;
  
    /* Remember blocks whose dominators will have to be updated.  */
--- 267,278 ----
       struct loop_desc *desc;
  {
    rtx niter, init_code, branch_code, jump, label;
!   int i, j, p;
    basic_block preheader, *body, *dom_bbs, swtch, ezc_swtch;
    int n_dom_bbs;
    sbitmap wont_exit;
    int may_exit_copy, n_peel, n_remove_edges;
!   edge *remove_edges, e;
    bool extra_zero_check, last_may_exit;
  
    /* Remember blocks whose dominators will have to be updated.  */
*************** unroll_loop_runtime_iterations (loops, l
*** 373,378 ****
--- 373,379 ----
  	{
  	  /* Create item for switch.  */
  	  j = n_peel - i - (extra_zero_check ? 0 : 1);
+ 	  p = REG_BR_PROB_BASE / (i + 2);
  	  preheader = loop_split_edge_with (loop_preheader_edge (loop),
  					    NULL_RTX, loops);
  	  label = block_label (preheader);
*************** unroll_loop_runtime_iterations (loops, l
*** 384,390 ****
  	  JUMP_LABEL (jump) = label;
  	  REG_NOTES (jump)
  		  = gen_rtx_EXPR_LIST (REG_BR_PROB,
! 			    	       GEN_INT (REG_BR_PROB_BASE / (n_peel - i + 1)), REG_NOTES (jump));
  	
  	  LABEL_NUSES (label)++;
  	  branch_code = get_insns ();
--- 385,391 ----
  	  JUMP_LABEL (jump) = label;
  	  REG_NOTES (jump)
  		  = gen_rtx_EXPR_LIST (REG_BR_PROB,
! 			    	       GEN_INT (p), REG_NOTES (jump));
  	
  	  LABEL_NUSES (label)++;
  	  branch_code = get_insns ();
*************** unroll_loop_runtime_iterations (loops, l
*** 392,404 ****
  
  	  swtch = loop_split_edge_with (swtch->pred, branch_code, loops);
  	  set_immediate_dominator (loops->cfg.dom, preheader, swtch);
! 	  make_edge (swtch, preheader, 0);
  	}
      }
  
    if (extra_zero_check)
      {
        /* Add branch for zero iterations.  */
        swtch = ezc_swtch;
        preheader = loop_split_edge_with (loop_preheader_edge (loop),
  					NULL_RTX, loops);
--- 393,408 ----
  
  	  swtch = loop_split_edge_with (swtch->pred, branch_code, loops);
  	  set_immediate_dominator (loops->cfg.dom, preheader, swtch);
! 	  swtch->succ->probability = REG_BR_PROB_BASE - p;
! 	  e = make_edge (swtch, preheader, 0);
! 	  e->probability = p;
  	}
      }
  
    if (extra_zero_check)
      {
        /* Add branch for zero iterations.  */
+       p = REG_BR_PROB_BASE / (max_unroll + 1);
        swtch = ezc_swtch;
        preheader = loop_split_edge_with (loop_preheader_edge (loop),
  					NULL_RTX, loops);
*************** unroll_loop_runtime_iterations (loops, l
*** 411,417 ****
        JUMP_LABEL (jump) = label;
        REG_NOTES (jump)
  	      = gen_rtx_EXPR_LIST (REG_BR_PROB,
! 				   GEN_INT (REG_BR_PROB_BASE / (n_peel - i + 1)), REG_NOTES (jump));
        
        LABEL_NUSES (label)++;
        branch_code = get_insns ();
--- 415,421 ----
        JUMP_LABEL (jump) = label;
        REG_NOTES (jump)
  	      = gen_rtx_EXPR_LIST (REG_BR_PROB,
! 				   GEN_INT (p), REG_NOTES (jump));
        
        LABEL_NUSES (label)++;
        branch_code = get_insns ();
*************** unroll_loop_runtime_iterations (loops, l
*** 419,425 ****
  
        swtch = loop_split_edge_with (swtch->succ, branch_code, loops);
        set_immediate_dominator (loops->cfg.dom, preheader, swtch);
!       make_edge (swtch, preheader, 0);
      }
  
    /* Recount dominators for outer blocks.  */
--- 423,431 ----
  
        swtch = loop_split_edge_with (swtch->succ, branch_code, loops);
        set_immediate_dominator (loops->cfg.dom, preheader, swtch);
!       swtch->succ->probability = REG_BR_PROB_BASE - p;
!       e = make_edge (swtch, preheader, 0);
!       e->probability = p;
      }
  
    /* Recount dominators for outer blocks.  */
Index: cfgloopmanip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/cfgloopmanip.c,v
retrieving revision 1.1.2.2
diff -c -3 -p -r1.1.2.2 cfgloopmanip.c
*** cfgloopmanip.c	20 Oct 2002 17:49:18 -0000	1.1.2.2
--- cfgloopmanip.c	3 Nov 2002 00:31:26 -0000
*************** record_exit_edges (orig, bbs, nbbs, to_r
*** 891,896 ****
--- 891,899 ----
      }
  }
  
+ 
+ #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
+ 
  /* Duplicates body of LOOP to given edge E NDUPL times.  Takes care of
     updating LOOPS structure.  E's destination must be LOOP header for this to
     work.  Store edges created by copying ORIG edge (if NULL, then all exit
*************** duplicate_loop_to_header_edge (loop, e, 
*** 919,925 ****
    edge ae, latch_edge, he;
    int i, j, n;
    int is_latch = (latch == e->src);
!   int k0, k, kk, freq_in, freq_e, freq_le;
    int add_irreducible_flag;
  
    if (e->dest != loop->header)
--- 922,929 ----
    edge ae, latch_edge, he;
    int i, j, n;
    int is_latch = (latch == e->src);
!   int scale_act, scale_step, scale_main, p, freq_in, freq_le;
!   int prob_pass_thru;
    int add_irreducible_flag;
  
    if (e->dest != loop->header)
*************** duplicate_loop_to_header_edge (loop, e, 
*** 955,1012 ****
    latch_edge = loop_latch_edge (loop);
  
    /* For updating frequencies.  */
-   freq_e = EDGE_FREQUENCY (e);
    freq_in = header->frequency;
    freq_le = EDGE_FREQUENCY (latch_edge);
  
    if (is_latch)
      {
        /* Should work well unless something inside depends on parity of
  	 iteration counter.  */
!       if (freq_in > freq_e)
  	{
! 	  k0 = REG_BR_PROB_BASE;
! 	  for (i = 0; i < ndupl + 1; i++)
! 	    k0 = (k0 * freq_e) / freq_in;
! 	  k0 = REG_BR_PROB_BASE - k0;
! 	  k0 = (((REG_BR_PROB_BASE * REG_BR_PROB_BASE) / freq_in) * 
! 		(freq_in - freq_e)) / k0;
! 	  k = (REG_BR_PROB_BASE * freq_e) / freq_in;
  	}
!       else
! 	{
! 	  k0 = REG_BR_PROB_BASE / (ndupl + 1);
! 	  k = REG_BR_PROB_BASE;
! 	}
!       kk = k0;
      }
    else
      {
!       /* Count probability that we will get to latch from header.
! 	 This is wrong; first iteration of cycle is certainly somewhat
  	 special.  But I cannot do anything with it. */
  
!       /* Strange things may happen to frequencies.  :-(  */
!       if (freq_le == 0)
! 	freq_le = 1;
!       if (freq_in <= freq_le)
! 	freq_in = freq_le + 1;
!       if (freq_in < freq_le + freq_e)
! 	freq_e = freq_in - freq_le;
! 
!       k = (REG_BR_PROB_BASE * freq_le) / freq_in;
!       kk = (REG_BR_PROB_BASE * freq_e) / freq_le;
!       k0 = kk;
        for (i = 0; i < ndupl; i++)
! 	k0 = (k0 * k) / REG_BR_PROB_BASE;
!       k0 = (k0 * freq_le) / REG_BR_PROB_BASE + freq_in - freq_le - freq_e;
!       k0 = (REG_BR_PROB_BASE * k0) / (freq_in - freq_le);
!       if (k0 < 0)
! 	k0 = 0;
!     }
!   if (k0 < 0 || k0 > REG_BR_PROB_BASE ||
!       k < 0  || k > REG_BR_PROB_BASE ||
!       kk < 0 || kk * k > REG_BR_PROB_BASE * REG_BR_PROB_BASE)
      {
        /* Something is wrong.  */
        abort ();
--- 959,1001 ----
    latch_edge = loop_latch_edge (loop);
  
    /* For updating frequencies.  */
    freq_in = header->frequency;
    freq_le = EDGE_FREQUENCY (latch_edge);
+   if (freq_in == 0)
+     freq_in = 1;
+   if (freq_in < freq_le)
+     freq_in = freq_le;
+ 
+   prob_pass_thru = RDIV (REG_BR_PROB_BASE * freq_le, freq_in);
+   scale_step = prob_pass_thru;
  
    if (is_latch)
      {
        /* Should work well unless something inside depends on parity of
  	 iteration counter.  */
!       p = REG_BR_PROB_BASE;
!       scale_main = 0;
!       for (i = 0; i < ndupl + 1; i++)
  	{
! 	  scale_main += p;
! 	  p = RDIV (p * scale_step, REG_BR_PROB_BASE);
  	}
!       scale_main = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE, scale_main);
!       scale_act = RDIV (scale_main * scale_step, REG_BR_PROB_BASE);
      }
    else
      {
!       /* This is wrong; first iteration of cycle is certainly somewhat
  	 special.  But I cannot do anything with it. */
  
!       scale_main = REG_BR_PROB_BASE;
        for (i = 0; i < ndupl; i++)
! 	scale_main = RDIV (scale_main * scale_step, REG_BR_PROB_BASE);
!       scale_act = REG_BR_PROB_BASE - scale_step;
!     }
!   if (scale_main < 0 || scale_main > REG_BR_PROB_BASE ||
!       scale_act < 0  || scale_act > REG_BR_PROB_BASE ||
!       scale_step < 0 || scale_step > REG_BR_PROB_BASE)
      {
        /* Something is wrong.  */
        abort ();
*************** duplicate_loop_to_header_edge (loop, e, 
*** 1054,1083 ****
  	record_exit_edges (orig, new_bbs, n, to_remove, n_to_remove, false);
    
        /* Set counts and frequencies.  */
-       kk = (kk * k) / REG_BR_PROB_BASE;
        for (i = 0; i < n; i++)
  	{
  	  new_bb = new_bbs[i];
  	  bb = bbs[i];
  	  if (flags & DLTHE_FLAG_UPDATE_FREQ)
  	    {
! 	      new_bb->count = (kk * bb->count +
! 			       REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
! 	      new_bb->frequency = (bb->frequency * kk +
! 				   REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
! 	      for (ae = new_bb->succ; ae; ae = ae->succ_next)
! 		ae->count = (new_bb->count * ae->probability +
! 			 REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
  	    }
  	  else
  	    {
  	      new_bb->count = bb->count;
  	      new_bb->frequency = bb->frequency;
- 	      for (ae = new_bb->succ; ae; ae = ae->succ_next)
- 		ae->count = (new_bb->count * ae->probability +
- 			 REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
  	    }
  	}
  
        if (!first_active_latch)
  	{
--- 1043,1070 ----
  	record_exit_edges (orig, new_bbs, n, to_remove, n_to_remove, false);
    
        /* Set counts and frequencies.  */
        for (i = 0; i < n; i++)
  	{
  	  new_bb = new_bbs[i];
  	  bb = bbs[i];
+ 
  	  if (flags & DLTHE_FLAG_UPDATE_FREQ)
  	    {
! 	      new_bb->count = RDIV (scale_act * bb->count, REG_BR_PROB_BASE);
! 	      new_bb->frequency = RDIV (scale_act * bb->frequency,
!      					REG_BR_PROB_BASE);
  	    }
  	  else
  	    {
  	      new_bb->count = bb->count;
  	      new_bb->frequency = bb->frequency;
  	    }
+ 
+ 	  for (ae = new_bb->succ; ae; ae = ae->succ_next)
+     	    ae->count = RDIV (new_bb->count * ae->probability,
+ 			      REG_BR_PROB_BASE);
  	}
+       scale_act = RDIV (scale_act * scale_step, REG_BR_PROB_BASE);
  
        if (!first_active_latch)
  	{
*************** duplicate_loop_to_header_edge (loop, e, 
*** 1085,1099 ****
  	  first_active_latch = RBI (latch)->copy;
  	}
        
-       /* Update edge counts.  */
-       for (i = 0; i < n; i++)
- 	{
- 	  bb = new_bbs[i];
- 	  for (ae = bb->succ; ae; ae = ae->succ_next)
- 	    ae->count = (bb->count * ae->probability +
- 			 REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
- 	}
- 
        free (new_bbs);
  
        /* Original loop header is dominated by latch copy
--- 1072,1077 ----
*************** duplicate_loop_to_header_edge (loop, e, 
*** 1118,1130 ****
        for (i = 0; i < n; i++)
  	{
  	  bb = bbs[i];
! 	  bb->count = (k0 * bb->count +
! 		       REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
! 	  bb->frequency = (bb->frequency * k0 +
! 			   REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
  	  for (ae = bb->succ; ae; ae = ae->succ_next)
! 	    ae->count = (bb->count * ae->probability +
! 			 REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
  	}
      }
  
--- 1096,1105 ----
        for (i = 0; i < n; i++)
  	{
  	  bb = bbs[i];
! 	  bb->count = RDIV (scale_main * bb->count, REG_BR_PROB_BASE);
! 	  bb->frequency = RDIV (scale_main * bb->frequency, REG_BR_PROB_BASE);
  	  for (ae = bb->succ; ae; ae = ae->succ_next)
! 	    ae->count = RDIV (bb->count * ae->probability, REG_BR_PROB_BASE);
  	}
      }
  


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]