This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Avoid possible overflow in register allocator
- To: gcc-patches at gcc dot gnu dot org, rth at cygnus dot com, patches at x86-64 dot org
- Subject: Avoid possible overflow in register allocator
- From: Jan Hubicka <jh at suse dot cz>
- Date: Mon, 30 Jul 2001 12:47:58 +0200
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. */