number of spills and reloads

number of spills and reloads

[Qiong Cai]

Hi,

I'd like to know the number of spills and reloads generated by
register allocator in GCC.   After having a look at the dump after
global register allocation, I found something like the following:
...
Spilling for insn ...
Using reg 1 for reload 0 ...
....

So I add the counter "num_spills" in function "find_reload_regs" and the counter
"num_reloads" in "find_reg" in "reload1.c" just after the instructions
printing out the above information.  Is this correct?  Because the
reload phase is complicated, I'm quite suspicious what I did.

thanks
Qiong

Re: number of spills and reloads

[James E Wilson]

Qiong Cai wrote:
> I'd like to know the number of spills and reloads generated by
> register allocator in GCC.

You need to define exactly what you mean by "spills" and "reloads" 
before those questions can be answered.  And you may not be able to 
define those terms exactly if you don't know how reload works.

> So I add the counter "num_spills" in function "find_reload_regs" and the counter
> "num_reloads" in "find_reg" in "reload1.c" just after the instructions
> printing out the above information.  Is this correct?  Because the
> reload phase is complicated, I'm quite suspicious what I did.

find_reload_regs gets called once for every instruction that needs a 
reload.  find_reg gets called once for every operand of every 
instruction that needs a spill register allocated to satisfy a reload. 
But we only reach the place where we emit the message if we choose to 
allocate a new spill register.

Counting the instructions that need a reload is a very poor measure of 
the number of spills.  There is n_spills which counts the number of hard 
registers allocated for use as spill registers which is one reasonable 
measure.  n_spills is probably very close to your num_reloads.  The 
different is probably eliminable registers like the frame pointer. 
Another measure might be the number of pseudos that get forced to stack 
slots in order to free up hard registers for use as spill registers. 
This can be computed by counting the number of registers in spilled_pseudos.

For the number of reloads, there is n_reloads computed by find_reloads. 
  This is a per instruction count.  You would have to sum it over all 
instructions to get a count for the entire function.  But there are a 
number of ambiguities here.

We sometimes create what is known as "optional" reloads.  These are 
things that don't need a reload, but might result in better code if they 
do get a reload.  Sometimes we perform them.  Sometimes we don't.  You 
may or not want to count them.

We also have secondary reloads.  Sometimes a single reload needs two 
registers, which we handle by creating two reloads, one of which is a 
secondary reload.  So is that 1 reload or 2?  Depends on how you want to 
count them.

Some reloads need a spill register, some don't.  If a reload can never 
result in a spill, do you still want to count it?

Some reloads involve multi-word values which may require multiple spill 
registers.

Etc.

Maybe what you really want is the number of reloads that require use of 
a spill register, which I think you could get by putting a counter at 
the top of find_reg.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

Re: number of spills and reloads

[Qiong Cai]

Hi James,

Thanks for the reply.

> find_reload_regs gets called once for every instruction that needs a
> reload.  find_reg gets called once for every operand of every
> instruction that needs a spill register allocated to satisfy a reload.
> But we only reach the place where we emit the message if we choose to
> allocate a new spill register.

I'm a bit confused with "spill register". Consider the following example,
r0 <- [sp+4] + [sp + 8]
then operand 1 must be the register. so reload into register r1 first
r1 <- [sp+4]

Is the register r1 a "spill" register?

> 
> Counting the instructions that need a reload is a very poor measure of
> the number of spills.  There is n_spills which counts the number of hard
> registers allocated for use as spill registers which is one reasonable
> measure.  n_spills is probably very close to your num_reloads.  The
> different is probably eliminable registers like the frame pointer.
> Another measure might be the number of pseudos that get forced to stack
> slots in order to free up hard registers for use as spill registers.
> This can be computed by counting the number of registers in spilled_pseudos.
> 
I need the number of "stores" or "spills" to memory caused by register
allocation.
It seems that this is close to your second measure.  Also I'd like to know the 
dyanmic counts of "stores".  For example, 
x = a + b  [ dynamic count = 10000 from edge profiling]
If the pseduos "a" and "b" must be forced to stack:
[sp + 4] <- a
[sp + b] <- b
So the dyanmic count is  10000+10000 = 20000.
Is this the reasonable measure of dynamic counts of "stores" or "spills" 
introduced by register allocation?


> For the number of reloads, there is n_reloads computed by find_reloads.
>   This is a per instruction count.  You would have to sum it over all
> instructions to get a count for the entire function.  But there are a
> number of ambiguities here.
> 
> We sometimes create what is known as "optional" reloads.  These are
> things that don't need a reload, but might result in better code if they
> do get a reload.  Sometimes we perform them.  Sometimes we don't.  You
> may or not want to count them.
> 
> We also have secondary reloads.  Sometimes a single reload needs two
> registers, which we handle by creating two reloads, one of which is a
> secondary reload.  So is that 1 reload or 2?  Depends on how you want to
> count them.
> 
> Some reloads need a spill register, some don't.  If a reload can never
> result in a spill, do you still want to count it?
> 
> Some reloads involve multi-word values which may require multiple spill
> registers.

Where's the place in which the final reload is emitted?  If I know the place,
then I just count the number of reload there.



-- 
Qiong Cai
www.cse.unsw.edu.au/~qiongc

Re: number of spills and reloads

[James E Wilson]

On Wed, 2004-08-25 at 22:45, Qiong Cai wrote:
> I'm a bit confused with "spill register". Consider the following example,
> r0 <- [sp+4] + [sp + 8]
> then operand 1 must be the register. so reload into register r1 first
> r1 <- [sp+4]
> Is the register r1 a "spill" register?

A spill register is an allocatable register that the reload pass can use
for resolving reloads.  Preferably this is a register that wasn't used
by the local or global register allocation passes.  But if we need a
reg, and there isn't one free, we can make one free by picking a hard
reg, and then for every pseudo reg allocated to that hard reg, we spill
it to the stack.  Since this is expensive, the reload pass tries to
compute the minimum number of spill regs needed.

For your example, yes, in the common case, r1 will be a spill reg. 
However, it isn't guaranteed to be a spill reg.  There is quite a bit of
complexity in reload to try to avoid using a spill reg when we don't
need one, so in complicated cases we might be able to reuse a register
from elsewhere.  For instance, if the previous instruction was
	[sp+4] <- r1
then we will use r1 instead of a spill reg.  (Though of course, r1 could
itself be a spill reg if the previous instruction needed a spill reg.)

> I need the number of "stores" or "spills" to memory caused by register
> allocation.
> It seems that this is close to your second measure.

There are actually two things here.  There are pseudos which get
assigned to a hard reg in local/global, and then spilled to the stack in
reload.  And there are pseudos which never get assigned to a hard reg. 
You may have to count these separately, as they may be handled in
different places.

A pseudo may be used in more than one place, which means you have to
find all of the places where they are used.  Reload doesn't track this
info because it doesn't need to know.  We modify a REG to a MEM in
place, so there is no need to know where all of the uses are.  It just
needs to know that every instruction is fixed.  It doesn't need to know
how many uses there are of each pseudo.  You might need a separate scan
over all of the instructions to compute this.

Then of course you need the dynamic count calculation for every use of a
pseudo.

> Where's the place in which the final reload is emitted?  If I know the place,
> then I just count the number of reload there.

reload_as_needed.  It calls find_reloads to compute the number of
reloads needed for each instruction, and then emit_reload_insns to emit
the instructions needed to perform the reloads.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

Re: number of spills and reloads

[Qiong Cai]

Hi James,

I'm doing some experiments on Pentium machines, and basically I need 3 kinds 
of statistics after reloading:
1) number of memory stores, eg. [sp+4] <- r1
2) number of memory loads, eg. r1 <- [sp+4]
3) number of combined stores and loads with addressing mode available
on CISC-like architectures: eg. [sp+4] <- [sp+4] + r1, or r1 <- [sp+4]
+ r1
where r1 is the hardware register.

From your previous email,  I think  the place in which REG is modifed
into MEM is only for case 3)??    Could you please tell me which
functions in the codes does this modification?

From the greg dump, it seems that the memory stores is related to
RELOAD_FOR_OUTPUT.  Is it possible to obtain (1) from the function
"emit_output_reload_insns"?

For case (2), I don't have much clue.  Is it related to RELOAD_FOR_INPUT? 
For the dump, it seems that for any non-optional RELOAD_FOR_INPUT or
RELOAD_FOR_OPERAND_ADDRESS, a "memory load" will be generated.
Is it correct?

Thanks.

On Mon, 30 Aug 2004 17:14:08 -0700, James E Wilson
<wilson@specifixinc.com> wrote:
> On Wed, 2004-08-25 at 22:45, Qiong Cai wrote:
> > I'm a bit confused with "spill register". Consider the following example,
> > r0 <- [sp+4] + [sp + 8]
> > then operand 1 must be the register. so reload into register r1 first
> > r1 <- [sp+4]
> > Is the register r1 a "spill" register?
> 
> A spill register is an allocatable register that the reload pass can use
> for resolving reloads.  Preferably this is a register that wasn't used
> by the local or global register allocation passes.  But if we need a
> reg, and there isn't one free, we can make one free by picking a hard
> reg, and then for every pseudo reg allocated to that hard reg, we spill
> it to the stack.  Since this is expensive, the reload pass tries to
> compute the minimum number of spill regs needed.
> 
> For your example, yes, in the common case, r1 will be a spill reg.
> However, it isn't guaranteed to be a spill reg.  There is quite a bit of
> complexity in reload to try to avoid using a spill reg when we don't
> need one, so in complicated cases we might be able to reuse a register
> from elsewhere.  For instance, if the previous instruction was
>        [sp+4] <- r1
> then we will use r1 instead of a spill reg.  (Though of course, r1 could
> itself be a spill reg if the previous instruction needed a spill reg.)
> 
> > I need the number of "stores" or "spills" to memory caused by register
> > allocation.
> > It seems that this is close to your second measure.
> 
> There are actually two things here.  There are pseudos which get
> assigned to a hard reg in local/global, and then spilled to the stack in
> reload.  And there are pseudos which never get assigned to a hard reg.
> You may have to count these separately, as they may be handled in
> different places.
> 
> A pseudo may be used in more than one place, which means you have to
> find all of the places where they are used.  Reload doesn't track this
> info because it doesn't need to know.  We modify a REG to a MEM in
> place, so there is no need to know where all of the uses are.  It just
> needs to know that every instruction is fixed.  It doesn't need to know
> how many uses there are of each pseudo.  You might need a separate scan
> over all of the instructions to compute this.
> 
> Then of course you need the dynamic count calculation for every use of a
> pseudo.
> 
> > Where's the place in which the final reload is emitted?  If I know the place,
> > then I just count the number of reload there.
> 
> reload_as_needed.  It calls find_reloads to compute the number of
> reloads needed for each instruction, and then emit_reload_insns to emit
> the instructions needed to perform the reloads.
> 
> 
> --
> Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com
> 
> 


-- 
Qiong Cai
www.cse.unsw.edu.au/~qiongc

Re: number of spills and reloads

[Joern Rennecke]

> I'm doing some experiments on Pentium machines, and basically I need 3 kinds 
> of statistics after reloading:
> 1) number of memory stores, eg. [sp+4] <- r1
> 2) number of memory loads, eg. r1 <- [sp+4]
> 3) number of combined stores and loads with addressing mode available
> on CISC-like architectures: eg. [sp+4] <- [sp+4] + r1, or r1 <- [sp+4]
> + r1
> where r1 is the hardware register.
> 
> >From your previous email,  I think  the place in which REG is modifed
> into MEM is only for case 3)??    Could you please tell me which

No, a reg->reg move can have either or both operands changed to a MEM,
thus making it a load, a store, or a memory-memory move (where available).

> functions in the codes does this modification?

Look at alter_reg.

> >From the greg dump, it seems that the memory stores is related to
> RELOAD_FOR_OUTPUT.  Is it possible to obtain (1) from the function
> "emit_output_reload_insns"?
> 
> For case (2), I don't have much clue.  Is it related to RELOAD_FOR_INPUT? 
> For the dump, it seems that for any non-optional RELOAD_FOR_INPUT or
> RELOAD_FOR_OPERAND_ADDRESS, a "memory load" will be generated.
> Is it correct?

A memory access need not have been generated by reload changing a register
into a memory reference; it might also be a result of rtl generation.

Re: number of spills and reloads

[Qiong Cai]

On Wed, 1 Sep 2004 13:38:40 +0100 (BST), Joern Rennecke
<joern.rennecke@superh.com> wrote:
> > I'm doing some experiments on Pentium machines, and basically I need 3 kinds
> > of statistics after reloading:
> > 1) number of memory stores, eg. [sp+4] <- r1
> > 2) number of memory loads, eg. r1 <- [sp+4]
> > 3) number of combined stores and loads with addressing mode available
> > on CISC-like architectures: eg. [sp+4] <- [sp+4] + r1, or r1 <- [sp+4]
> > + r1
> > where r1 is the hardware register.
> >
> > >From your previous email,  I think  the place in which REG is modifed
> > into MEM is only for case 3)??    Could you please tell me which
> 
> No, a reg->reg move can have either or both operands changed to a MEM,
> thus making it a load, a store, or a memory-memory move (where available).
> 
> > functions in the codes does this modification?
> 
> Look at alter_reg.

Ok. I will have a close look at this function. But it seems that no
actual code of the modification is generated in this function. Will
the spill decision made in this function be changed in later steps of
the reload?


> > For case (2), I don't have much clue.  Is it related to RELOAD_FOR_INPUT?
> > For the dump, it seems that for any non-optional RELOAD_FOR_INPUT or
> > RELOAD_FOR_OPERAND_ADDRESS, a "memory load" will be generated.
> > Is it correct?
> 
> A memory access need not have been generated by reload changing a register
> into a memory reference; it might also be a result of rtl generation.
> 
I know.  But I like to know the number of "new" load/store/memory
instructions genereated by register allocation/reload pass.


-- 
Qiong Cai
www.cse.unsw.edu.au/~qiongc

Re: number of spills and reloads

[Joern Rennecke]

> Ok. I will have a close look at this function. But it seems that no
> actual code of the modification is generated in this function.

The actual modification of the reg is done in reload.  The
register is changed in place, chaninging all its uses simultanously.
Look for this line:

              PUT_CODE (reg, MEM);

>                                                                Will
> the spill decision made in this function be changed in later steps of
> the reload?

After a pseudo has been spilled using alter_reg, it might be reallocated
to a different hard register by retry_global_alloc.
Also, due to reload inheritance and reload_cse, not every access of a pseudo
that got spilled to a stack slot will actually use the stack slot.

Before the post_reload passes (like reload_cse), the number of memory
accesses generated by reload for a pseudo register that has been allocated
to a stack slot or other memory location can can be estimated by 
the number of references to the pseudo, minus the ones where reload_as_needed
finds non-mmeory replacements for, times the number of memory accesses
needed per register access (in case of multi-word pseudos).
Some fuzzyness comes in in how much references you want to count for SUBREG
references and other read-modify-write constructs.
On other architectures, more complications arise from secondary reloads
for out-of-range offsets that require memory loads for the constants,
or using secondary memory to move between certain register classes.

Re: number of spills and reloads

[James E Wilson]

Qiong Cai wrote:
> 1) number of memory stores, eg. [sp+4] <- r1
> 2) number of memory loads, eg. r1 <- [sp+4]
> 3) number of combined stores and loads with addressing mode available
> on CISC-like architectures: eg. [sp+4] <- [sp+4] + r1, or r1 <- [sp+4]
> + r1
> where r1 is the hardware register.

I don't think you can get the numbers you want by instrumenting reload. 
  reload is a very complicated pass that does not match your model.

I'd suggest instead that you add before and after reload passes, that 
count the number of memory loads and stores by scanning all of the 
instructions in a function.  Thus the number of loads/stores emitted by 
reload is the difference between the two.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com