llvm dev - Sep 2015 - Register spilling in caller saved backend

Hey,

I'm playing around with a backend with no callee saved registers and
noticed more spilling than seems needed. I tried digging into the spilling
code but with limited success. I also tried removing all the callee saved
registers in the X86 backend and saw the same effect (basically making CSRs
equal to CSR_NoRegs). So I seem to be misunderstanding something or missing
something simple, and thought I'd ask.

Consider this program as an example:

volatile int x;

int __attribute__((noinline)) foo() { return x; }

int main() {
  for (int i = 0; i < 10; ++i) {
    foo();
  }
}

The resultant output code spills 'i' within the loop (I have to compile
with -fno-unroll-loops else the loop and 'i' gets optimized away) while
'i'
is assigned to a register that is used nowhere else in the generated
program and I would consider 'foo' easy to analyse. At the call site of
'foo' the debugging output reports that the stack pointer and return
value
registers are "imp-use" and "imp-def" and no other registers
are used.

Should the spilling have occurred? Or this due to some feature in the
backend that is missing?

Thanks,

Jacques
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150901/09633b6f/attachment.html>

On Tue, 2015-09-01 at 08:52 -0700, Jacques Pienaar via llvm-dev wrote:
> int main() {
>   for (int i = 0; i < 10; ++i) {
>     foo();
>   }
> }
> 
> 
> The resultant output code spills 'i' within the loop (I have to
> compile with -fno-unroll-loops else the loop and 'i' gets optimi!
zed
> away) while 'i' is assigned to a register that is used nowhere else
in
> the generated program and I would consider 'foo' easy to analyse.
At
> the call site of 'foo' the debugging output reports that the stack
> pointer and return value registers are "imp-use" and
"imp-def" and no
> other registers are used.
When a function (such as main() in this case) is compiled, all calls to
functions are assumed to clobber all caller saved registers.  Since your
backend said that all registers are caller saved, then the compiler has
not choice but to spill 'i' around the call to foo(), since it may
trash the register 'i' is allocated to.

> Should the spilling have occurred? Or this due to some feature in the
> backend that is missing?
This is totally as expected when you have no callee saved registers.


Peter

Hi Jacques,

Could you attach the MachineInstr before and after register allocation?

This is hard to give an answer without seeing the actual CFG and live-ranges.

Thanks,
Q.
> On Sep 1, 2015, at 8:52 AM, Jacques Pienaar via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hey,
> 
> I'm playing around with a backend with no callee saved registers and
noticed more spilling than seems needed. I tried digging into the spilling code
but with limited success. I also tried removing all the callee saved registers
in the X86 backend and saw the same effect (basically making CSRs equal to
CSR_NoRegs). So I seem to be misunderstanding something or missing something
simple, and thought I'd ask.
> 
> Consider this program as an example:
> 
> volatile int x;
> 
> int __attribute__((noinline)) foo() { return x; }
> 
> int main() {
>   for (int i = 0; i < 10; ++i) {
>     foo();
>   }
> }
> 
> The resultant output code spills 'i' within the loop (I have to
compile with -fno-unroll-loops else the loop and 'i' gets optimized
away) while 'i' is assigned to a register that is used nowhere else in
the generated program and I would consider 'foo' easy to analyse. At the
call site of 'foo' the debugging output reports that the stack pointer
and return value registers are "imp-use" and "imp-def" and
no other registers are used.
> 
> Should the spilling have occurred? Or this due to some feature in the
backend that is missing?
> 
> Thanks,
> 
> Jacques
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On 09/01/2015 08:52 AM, Jacques Pienaar via llvm-dev
wrote:
> Hey,
>
> I'm playing around with a backend with no callee saved registers and 
> noticed more spilling than seems needed. I tried digging into the 
> spilling code but with limited success. I also tried removing all the 
> callee saved registers in the X86 backend and saw the same effect 
> (basically making CSRs equal to CSR_NoRegs). So I seem to be 
> misunderstanding something or missing something simple, and thought 
> I'd ask.
>
> Consider this program as an example:
>
> volatile int x;
>
> int __attribute__((noinline)) foo() { return x; }
>
> int main() {
>   for (int i = 0; i < 10; ++i) {
>     foo();
>   }
> }
>
> The resultant output code spills 'i' within the loop (I have to 
> compile with -fno-unroll-loops else the loop and 'i' gets optimized
> away) while 'i' is assigned to a register that is used nowhere else
in
> the generated program and I would consider 'foo' easy to analyse.
At
> the call site of 'foo' the debugging output reports that the stack 
> pointer and return value registers are "imp-use" and
"imp-def" and no
> other registers are used.
>
> Should the spilling have occurred? Or this due to some feature in the 
> backend that is missing?
What are you expectating here?  Are you expecting the backend to 
recognize that foo doesn't actually clobber any registers?  I don't 
believe we do that today.  Without callee saved registers, if the value 
'i' needs to be preserved across the call, it will need to be spilled.  
There's no register we can put it in without it being
clobbered.
>
> Thanks,
>
> Jacques
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150901/29961d13/attachment.html>

On Tue, Sep 1, 2015 at 9:13 AM, Philip Reames <listmail at
philipreames.com>
wrote:
>
>
> On 09/01/2015 08:52 AM, Jacques Pienaar via llvm-dev wrote:
>
> Hey,
>
> I'm playing around with a backend with no callee saved registers and
> noticed more spilling than seems needed. I tried digging into the spilling
> code but with limited success. I also tried removing all the callee saved
> registers in the X86 backend and saw the same effect (basically making CSRs
> equal to CSR_NoRegs). So I seem to be misunderstanding something or missing
> something simple, and thought I'd ask.
>
> Consider this program as an example:
>
> volatile int x;
>
> int __attribute__((noinline)) foo() { return x; }
>
> int main() {
>   for (int i = 0; i < 10; ++i) {
>     foo();
>   }
> }
>
> The resultant output code spills 'i' within the loop (I have to
compile
> with -fno-unroll-loops else the loop and 'i' gets optimized away)
while 'i'
> is assigned to a register that is used nowhere else in the generated
> program and I would consider 'foo' easy to analyse. At the call
site of
> 'foo' the debugging output reports that the stack pointer and
return value
> registers are "imp-use" and "imp-def" and no other
registers are used.
>
> Should the spilling have occurred? Or this due to some feature in the
> backend that is missing?
>
> What are you expectating here?  Are you expecting the backend to recognize
> that foo doesn't actually clobber any registers?  I don't believe
we do
> that today.  Without callee saved registers, if the value 'i' needs
to be
> preserved across the call, it will need to be spilled.  There's no
register
> we can put it in without it being clobbered.
>
Yes that was what I was hoping for as it seems that all the information is
there to do that. So at the moment if there is a case such as this then the
backend should have some designated callee saved registers. That makes
sense if that information isn't being used at the moment then we can't
know
if the register will be clobbered or not and have to assume it will.

Thanks
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150901/98718c59/attachment.html>

Hi Jacques,

Looked at the MIs you sent me and +1 to all that Philip said.
I is live across the call of foo, and since we do not have any CSR to preserve
it, we must spill.

Cheers,
Q.
> On Sep 1, 2015, at 9:13 AM, Philip Reames via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> 
> 
> On 09/01/2015 08:52 AM, Jacques Pienaar via llvm-dev wrote:
>> Hey,
>> 
>> I'm playing around with a backend with no callee saved registers
and noticed more spilling than seems needed. I tried digging into the spilling
code but with limited success. I also tried removing all the callee saved
registers in the X86 backend and saw the same effect (basically making CSRs
equal to CSR_NoRegs). So I seem to be misunderstanding something or missing
something simple, and thought I'd ask.
>> 
>> Consider this program as an example:
>> 
>> volatile int x;
>> 
>> int __attribute__((noinline)) foo() { return x; }
>> 
>> int main() {
>>   for (int i = 0; i < 10; ++i) {
>>     foo();
>>   }
>> }
>> 
>> The resultant output code spills 'i' within the loop (I have to
compile with -fno-unroll-loops else the loop and 'i' gets optimized
away) while 'i' is assigned to a register that is used nowhere else in
the generated program and I would consider 'foo' easy to analyse. At the
call site of 'foo' the debugging output reports that the stack pointer
and return value registers are "imp-use" and "imp-def" and
no other registers are used.
>> 
>> Should the spilling have occurred? Or this due to some feature in the
backend that is missing?
> What are you expectating here?  Are you expecting the backend to recognize
that foo doesn't actually clobber any registers?  I don't believe we do
that today.  Without callee saved registers, if the value 'i' needs to
be preserved across the call, it will need to be spilled.  There's no
register we can put it in without it being clobbered.
>> 
>> Thanks,
>> 
>> Jacques
>> 
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150901/95f226d9/attachment.html>

Note that it would be very unusual to have no callee saved registers.

Historically (pre-RISC), it was normal to pass arguments on the stack and
have ALL registers callee saved. Or maybe to have just one or two registers
that could be clobbered by the called function, or linkage code.

On Tue, Sep 1, 2015 at 7:01 PM, Peter Bergner via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> On Tue, 2015-09-01 at 08:52 -0700, Jacques Pienaar via llvm-dev wrote:
>
> > int main() {
> >   for (int i = 0; i < 10; ++i) {
> >     foo();
> >   }
> > }
> >
> >
> > The resultant output code spills 'i' within the loop (I have
to
> > compile with -fno-unroll-loops else the loop and 'i' gets
optimi! zed
> > away) while 'i' is assigned to a register that is used nowhere
else in
> > the generated program and I would consider 'foo' easy to
analyse. At
> > the call site of 'foo' the debugging output reports that the
stack
> > pointer and return value registers are "imp-use" and
"imp-def" and no
> > other registers are used.
>
> When a function (such as main() in this case) is compiled, all calls to
> functions are assumed to clobber all caller saved registers.  Since your
> backend said that all registers are caller saved, then the compiler has
> not choice but to spill 'i' around the call to foo(), since it may
> trash the register 'i' is allocated to.
>
>
> > Should the spilling have occurred? Or this due to some feature in the
> > backend that is missing?
>
> This is totally as expected when you have no callee saved registers.
>
>
> Peter
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150901/b1a78918/attachment.html>