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]

Avoid possible overflow in register allocator


Hi,
the register allocator computes the register priority and has comment
why value does not overflow.  My REG_FREQ changes multiplied that value
by 10000 making the comment wrong and overflows possible.  My initial idea
was to remove the multiplication by 10000, but it does not work well with -Os,
as the register is counted as 1 making precisity to be lost.

Proper solution seems to be to rescale the priorities in lower range 
(this works well, as we now de-facto optimize for size in the less commonly
executed regions), and decrease the multiplication factor in the allocator.

Bootstrapped/regtested i686

Honza

Mon Jul 30 12:14:02 CEST 2001  Jan Hubicka  <jh@shuse.cz>
	* flow.c (mark_set_1): Use REG_FREQ_FROM_BB.
	(attempt_auto_inc): LIkewise.
	(mark_used_reg): Likewise.
	(try_pre_increment_1): Likewise.
	* regclass.c (regclass): Likewise.
	* global.c (allocno_compare): Update comment; change scaling factor.
	* local-alloc.c (QTY_CMP_PRI): Likewise.
	* regs.h (REG_FREQ_FROM_BB): New.
	(REG_FREQ_MAX): Likewise.
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.435
diff -c -3 -p -r1.435 flow.c
*** flow.c	2001/07/23 14:08:11	1.435
--- flow.c	2001/07/30 09:52:26
*************** mark_set_1 (pbi, code, reg, cond, insn, 
*** 6024,6031 ****
  		     register twice if it is modified, but that is correct.  */
  		  REG_N_SETS (i) += 1;
  		  REG_N_REFS (i) += 1;
! 		  REG_FREQ (i) += (optimize_size || !pbi->bb->frequency
! 				   ? 1 : pbi->bb->frequency);
  
  	          /* The insns where a reg is live are normally counted
  		     elsewhere, but we want the count to include the insn
--- 6227,6233 ----
  		     register twice if it is modified, but that is correct.  */
  		  REG_N_SETS (i) += 1;
  		  REG_N_REFS (i) += 1;
! 		  REG_FREQ (i) += REG_FREQ_FROM_BB (pbi->bb);
  
  	          /* The insns where a reg is live are normally counted
  		     elsewhere, but we want the count to include the insn
*************** attempt_auto_inc (pbi, inc, insn, mem, i
*** 6692,6699 ****
        /* Count an extra reference to the reg.  When a reg is
  	 incremented, spilling it is worse, so we want to make
  	 that less likely.  */
!       REG_FREQ (regno) += (optimize_size || !pbi->bb->frequency
! 		           ? 1 : pbi->bb->frequency);
  
        /* Count the increment as a setting of the register,
  	 even though it isn't a SET in rtl.  */
--- 6894,6900 ----
        /* Count an extra reference to the reg.  When a reg is
  	 incremented, spilling it is worse, so we want to make
  	 that less likely.  */
!       REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb);
  
        /* Count the increment as a setting of the register,
  	 even though it isn't a SET in rtl.  */
*************** mark_used_reg (pbi, reg, cond, insn)
*** 6858,6865 ****
  	    REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
  
  	  /* Count (weighted) number of uses of each reg.  */
! 	  REG_FREQ (regno_first)
! 	    += (optimize_size || !pbi->bb->frequency ? 1 : pbi->bb->frequency);
  	  REG_N_REFS (regno_first)++;
  	}
      }
--- 7059,7065 ----
  	    REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
  
  	  /* Count (weighted) number of uses of each reg.  */
! 	  REG_FREQ (regno_first) += REG_FREQ_FROM_BB (pbi->bb);
  	  REG_N_REFS (regno_first)++;
  	}
      }
*************** try_pre_increment_1 (pbi, insn)
*** 7281,7288 ****
  	 so we want to make that less likely.  */
        if (regno >= FIRST_PSEUDO_REGISTER)
  	{
! 	  REG_FREQ (regno) += (optimize_size || !pbi->bb->frequency
! 			       ? 1 : pbi->bb->frequency);
  	  REG_N_SETS (regno)++;
  	}
  
--- 7481,7487 ----
  	 so we want to make that less likely.  */
        if (regno >= FIRST_PSEUDO_REGISTER)
  	{
! 	  REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb);
  	  REG_N_SETS (regno)++;
  	}
  
Index: global.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/global.c,v
retrieving revision 1.68
diff -c -3 -p -r1.68 global.c
*** global.c	2001/06/22 17:18:20	1.68
--- global.c	2001/07/30 09:52:36
*************** allocno_compare (v1p, v2p)
*** 611,626 ****
    int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
    /* Note that the quotient will never be bigger than
       the value of floor_log2 times the maximum number of
!      times a register can occur in one insn (surely less than 100).
!      Multiplying this by 10000 can't overflow.  */
    register int pri1
      = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq)
  	/ allocno[v1].live_length)
!        * 10000 * allocno[v1].size);
    register int pri2
      = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq)
  	/ allocno[v2].live_length)
!        * 10000 * allocno[v2].size);
    if (pri2 - pri1)
      return pri2 - pri1;
  
--- 611,627 ----
    int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
    /* Note that the quotient will never be bigger than
       the value of floor_log2 times the maximum number of
!      times a register can occur in one insn (surely less than 100)
!      weighted by the frequency (maximally REG_FREQ_MAX).
!      Multiplying this by 10000/REG_FREQ_MAX can't overflow.  */
    register int pri1
      = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq)
  	/ allocno[v1].live_length)
!        * (10000 / REG_FREQ_MAX) * allocno[v1].size);
    register int pri2
      = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq)
  	/ allocno[v2].live_length)
!        * (10000 / REG_FREQ_MAX) * allocno[v2].size);
    if (pri2 - pri1)
      return pri2 - pri1;
  
Index: local-alloc.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/local-alloc.c,v
retrieving revision 1.81
diff -c -3 -p -r1.81 local-alloc.c
*** local-alloc.c	2001/06/22 17:18:20	1.81
--- local-alloc.c	2001/07/30 09:52:40
*************** block_alloc (b)
*** 1698,1710 ****
  
  /* Note that the quotient will never be bigger than
     the value of floor_log2 times the maximum number of
!    times a register can occur in one insn (surely less than 100).
!    Multiplying this by 10000 can't overflow.
     QTY_CMP_PRI is also used by qty_sugg_compare.  */
  
  #define QTY_CMP_PRI(q)		\
    ((int) (((double) (floor_log2 (qty[q].n_refs) * qty[q].freq * qty[q].size) \
! 	  / (qty[q].death - qty[q].birth)) * 10000))
  
  static int
  qty_compare (q1, q2)
--- 1698,1711 ----
  
  /* Note that the quotient will never be bigger than
     the value of floor_log2 times the maximum number of
!    times a register can occur in one insn (surely less than 100)
!    weighted by frequency (max REG_FREQ_MAX).
!    Multiplying this by 10000/REG_FREQ_MAX can't overflow.
     QTY_CMP_PRI is also used by qty_sugg_compare.  */
  
  #define QTY_CMP_PRI(q)		\
    ((int) (((double) (floor_log2 (qty[q].n_refs) * qty[q].freq * qty[q].size) \
! 	  / (qty[q].death - qty[q].birth)) * (10000 / REG_FREQ_MAX)))
  
  static int
  qty_compare (q1, q2)
Index: regclass.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/regclass.c,v
retrieving revision 1.124
diff -c -3 -p -r1.124 regclass.c
*** regclass.c	2001/07/20 16:55:03	1.124
--- regclass.c	2001/07/30 09:52:50
*************** regclass (f, nregs, dump)
*** 1233,1239 ****
  
        if (!optimize)
  	{
! 	  frequency = 1;
  	  for (insn = f; insn; insn = NEXT_INSN (insn))
  	    insn = scan_one_insn (insn, pass);
  	}
--- 1233,1239 ----
  
        if (!optimize)
  	{
! 	  frequency = REG_FREQ_MAX;
  	  for (insn = f; insn; insn = NEXT_INSN (insn))
  	    insn = scan_one_insn (insn, pass);
  	}
*************** regclass (f, nregs, dump)
*** 1246,1255 ****
  	       times more than insns outside a loop.  This is much more
  	       aggressive than the assumptions made elsewhere and is being
  	       tried as an experiment.  */
! 	    if (optimize_size)
! 	      frequency = 1;
! 	    else
! 	      frequency = bb->frequency ? bb->frequency : 1;
  	    for (insn = bb->head; ; insn = NEXT_INSN (insn))
  	      {
  		insn = scan_one_insn (insn, pass);
--- 1246,1252 ----
  	       times more than insns outside a loop.  This is much more
  	       aggressive than the assumptions made elsewhere and is being
  	       tried as an experiment.  */
! 	    frequency = REG_FREQ_FROM_BB (bb);
  	    for (insn = bb->head; ; insn = NEXT_INSN (insn))
  	      {
  		insn = scan_one_insn (insn, pass);
Index: regs.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/regs.h,v
retrieving revision 1.22
diff -c -3 -p -r1.22 regs.h
*** regs.h	2001/06/22 17:18:19	1.22
--- regs.h	2001/07/30 09:52:51
*************** extern varray_type reg_n_info;
*** 86,91 ****
--- 86,109 ----
  
  #define REG_FREQ(N) (VARRAY_REG (reg_n_info, N)->freq)
  
+ /* The weights for each insn varries from 0 to REG_FREQ_BASE. 
+    This constant does not need to be high, as in infrequently executed
+    regions we want to count instructions equivalently to optimize for
+    size instead of speed.  */
+ #define REG_FREQ_MAX 1000
+ 
+ /* Compute register frequency from the BB frequency.  When optimizing for size,
+    or profile driven feedback is available and the function is never executed,
+    frequency is always equivalent.  Otherwise rescale the basic block
+    frequency.  */
+ #define REG_FREQ_FROM_BB(bb) (optimize_size				      \
+ 			      || (flag_branch_probabilities		      \
+ 				  && !ENTRY_BLOCK_PTR->count)		      \
+ 			      ? REG_FREQ_MAX				      \
+ 			      : ((bb)->frequency * REG_FREQ_MAX / BB_FREQ_MAX)\
+ 			      ? ((bb)->frequency * REG_FREQ_MAX / BB_FREQ_MAX)\
+ 			      : 1)
+ 
  /* Indexed by n, gives number of times (REG n) is set.
     ??? both regscan and flow allocate space for this.  We should settle
     on just copy.  */


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