Spilling register and frame indices

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Spilling register and frame indices

Bugzilla from ghost@cs.msu.su

Hi,
right now, LLVM does register spilling by:

1. Creating stack object
2. Passing index of that stack object to MRegisterInfo::storeRegToStackSlot
3. At later stage, frame indices are replaced by calling to
MRegisterInfo::eliminateFrameIndex.

This works for me, but there's slight problem. The target does not have
"register + contant" addressing mode, so accessing frame index should be
done like this:

   some_register = frame_pointer + offset
         ...... [some_register]

Since frame index eliminations happens after register allocation, I must
make sure 'some_register' does not participate in normal register
allocation.

That approach sounds suboptimal. By "reserving" one register we can already
cause some values to be spilled, that otherwise would be stored in
register.

The lifetimes of those 'some_register' is likely to be very small (1
instruction), so "reserving" it everywhere is not good.

Ideal approach would be to add a method to MRegisterInfo to spill specific
virtual register. The implementation can then create code like:
 
   virtual_register = frame_pointer + offset
         [virtual_register]

and then have 'virtual_register' allocated on next iteration of register
allocator?

Also, while RegAllocLocal and RegAllocSimple directly call
storeRegToStackSlot, I would not found any calls to that method in
RegAllocLinearScan. Am I missing something?

- Volodya

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Spilling register and frame indices

Evan Cheng-2
Yeah, a iterative approach, i.e. while (...) { RegisterAllocate();  
InsertSpills(); } should work well for your target (and others!).  
Feel free to contribute. :-)

storeRegToStackSlot is also called from VirtRegMap.cpp which does  
some of spilling / restoring work.

Evan

On May 23, 2006, at 6:33 AM, Vladimir Prus wrote:

>
> Hi,
> right now, LLVM does register spilling by:
>
> 1. Creating stack object
> 2. Passing index of that stack object to  
> MRegisterInfo::storeRegToStackSlot
> 3. At later stage, frame indices are replaced by calling to
> MRegisterInfo::eliminateFrameIndex.
>
> This works for me, but there's slight problem. The target does not  
> have
> "register + contant" addressing mode, so accessing frame index  
> should be
> done like this:
>
>    some_register = frame_pointer + offset
>          ...... [some_register]
>
> Since frame index eliminations happens after register allocation, I  
> must
> make sure 'some_register' does not participate in normal register
> allocation.
>
> That approach sounds suboptimal. By "reserving" one register we can  
> already
> cause some values to be spilled, that otherwise would be stored in
> register.
>
> The lifetimes of those 'some_register' is likely to be very small (1
> instruction), so "reserving" it everywhere is not good.
>
> Ideal approach would be to add a method to MRegisterInfo to spill  
> specific
> virtual register. The implementation can then create code like:
>
>    virtual_register = frame_pointer + offset
>          [virtual_register]
>
> and then have 'virtual_register' allocated on next iteration of  
> register
> allocator?
>
> Also, while RegAllocLocal and RegAllocSimple directly call
> storeRegToStackSlot, I would not found any calls to that method in
> RegAllocLinearScan. Am I missing something?
>
> - Volodya
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Spilling register and frame indices

Chris Lattner
In reply to this post by Bugzilla from ghost@cs.msu.su
On Tue, 23 May 2006, Vladimir Prus wrote:

> right now, LLVM does register spilling by:
>
> 1. Creating stack object
> 2. Passing index of that stack object to MRegisterInfo::storeRegToStackSlot
> 3. At later stage, frame indices are replaced by calling to
> MRegisterInfo::eliminateFrameIndex.
>
> This works for me, but there's slight problem. The target does not have
> "register + contant" addressing mode, so accessing frame index should be
> done like this:
>
>   some_register = frame_pointer + offset
>         ...... [some_register]
>
> Since frame index eliminations happens after register allocation, I must
> make sure 'some_register' does not participate in normal register
> allocation.

Right.

> That approach sounds suboptimal. By "reserving" one register we can already
> cause some values to be spilled, that otherwise would be stored in
> register.

Right.

PowerPC has the same problem in certain cases.  For example, vector loads
only support reg+reg addressing, which means you have to load the offset
from the stack pointer into a register before doing the load.

In the case of PPC, we currently just reserve a register for this purpose.
This is suboptimal, but doesn't cause a significant performance issue
normally.

> The lifetimes of those 'some_register' is likely to be very small (1
> instruction), so "reserving" it everywhere is not good.
>
> Ideal approach would be to add a method to MRegisterInfo to spill specific
> virtual register. The implementation can then create code like:
>
>   virtual_register = frame_pointer + offset
>         [virtual_register]
>
> and then have 'virtual_register' allocated on next iteration of register
> allocator?

This is one approach.  Another approach is to have to spiller scavange
registers, which is the subject of this enhancement request:
http://llvm.org/PR768

> Also, while RegAllocLocal and RegAllocSimple directly call
> storeRegToStackSlot, I would not found any calls to that method in
> RegAllocLinearScan. Am I missing something?

RegAllocLinearScan just does register assignment, then the code in
VirtRegMap.cpp (poorly named) actually takes the register assignment and
inserts/optimizes the spill code.

Depending on how severe this problem is for your target, I'd suggest just
reserving a register for this for now.  When you get to performance
tuning, and when this bubbles up to the top of the list, I'd suggest
working on PR768.

-Chris

--
http://nondot.org/sabre/
http://llvm.org/

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Spilling register and frame indices

Andrew Lenharth-3
On Tue, 2006-05-23 at 13:04 -0500, Chris Lattner wrote:

> > That approach sounds suboptimal. By "reserving" one register we can already
> > cause some values to be spilled, that otherwise would be stored in
> > register.
>
> Right.
>
> PowerPC has the same problem in certain cases.  For example, vector loads
> only support reg+reg addressing, which means you have to load the offset
> from the stack pointer into a register before doing the load.
>
> In the case of PPC, we currently just reserve a register for this purpose.
> This is suboptimal, but doesn't cause a significant performance issue
> normally.

Alpha also has this problem for some offsets.  I haven't looked at what
PPC does, but alpha has the loads and stores that might need the
indexing kill an extra register, thus ensuring it is available for the
inserted instruction.  You don't need to reserve a register (globally)
only for these cases, just make sure you have it available when you need
it.

Andrew

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Spilling register and frame indices

Bugzilla from ghost@cs.msu.su
Andrew Lenharth wrote:

> On Tue, 2006-05-23 at 13:04 -0500, Chris Lattner wrote:
>> > That approach sounds suboptimal. By "reserving" one register we can
>> > already cause some values to be spilled, that otherwise would be stored
>> > in register.
>>
>> Right.
>>
>> PowerPC has the same problem in certain cases.  For example, vector loads
>> only support reg+reg addressing, which means you have to load the offset
>> from the stack pointer into a register before doing the load.
>>
>> In the case of PPC, we currently just reserve a register for this
>> purpose. This is suboptimal, but doesn't cause a significant performance
>> issue normally.
>
> Alpha also has this problem for some offsets.  I haven't looked at what
> PPC does, but alpha has the loads and stores that might need the
> indexing kill an extra register, thus ensuring it is available for the
> inserted instruction.  You don't need to reserve a register (globally)
> only for these cases, just make sure you have it available when you need
> it.

I'm sorry I don't understand your suggestion. Unless I reserve a register
globally, I might not have any register at all to use for addressing.

- Volodya

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Spilling register and frame indices

Bugzilla from ghost@cs.msu.su
In reply to this post by Chris Lattner
Chris Lattner wrote:


>> and then have 'virtual_register' allocated on next iteration of register
>> allocator?
>
> This is one approach.  Another approach is to have to spiller scavange
> registers, which is the subject of this enhancement request:
> http://llvm.org/PR768

Can you given some references for this "scavange" thing? Google and
ResearchIndex are silent on the topic.

>> Also, while RegAllocLocal and RegAllocSimple directly call
>> storeRegToStackSlot, I would not found any calls to that method in
>> RegAllocLinearScan. Am I missing something?
>
> RegAllocLinearScan just does register assignment, then the code in
> VirtRegMap.cpp (poorly named) actually takes the register assignment and
> inserts/optimizes the spill code.

Yea, now that you mention this I see the 'spiller_' member of linear scan
register allocator.

- Volodya

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Re: Spilling register and frame indices

Andrew Lenharth-3
In reply to this post by Bugzilla from ghost@cs.msu.su
On Wed, 2006-05-24 at 10:07 +0400, Vladimir Prus wrote:

> Andrew Lenharth wrote:
> > Alpha also has this problem for some offsets.  I haven't looked at what
> > PPC does, but alpha has the loads and stores that might need the
> > indexing kill an extra register, thus ensuring it is available for the
> > inserted instruction.  You don't need to reserve a register (globally)
> > only for these cases, just make sure you have it available when you need
> > it.
>
> I'm sorry I don't understand your suggestion. Unless I reserve a register
> globally, I might not have any register at all to use for addressing.
> - Volodya

If you look in AlphaInstrFormats.td the MForm class reserves R28 for
index calculations.  It does this by adding it to the Defs set for those
instructions.  Thus since the instruction is set as killing R28, it is
available for use if I insert an instruction immediately before the
ld/st.  Thus R28 can be used by the register allocator, but the RA makes
sure it is unused when there is an ld/st, thus giving me a scratch
register to use for index calculations with out completely reserving
R28.

Andrew

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Re: Spilling register and frame indices

Chris Lattner
In reply to this post by Bugzilla from ghost@cs.msu.su
On Wed, 24 May 2006, Vladimir Prus wrote:
> Chris Lattner wrote:
>> This is one approach.  Another approach is to have to spiller scavange
>> registers, which is the subject of this enhancement request:
>> http://llvm.org/PR768
>
> Can you given some references for this "scavange" thing? Google and
> ResearchIndex are silent on the topic.

It's not a very deep concept. :)  The basic idea is that, when you find
that you need to insert a reload for spill code, you look to see if there
are any unused registers.  If so, use one.

Otherwise, you need to find one to spill to memory, and do so in a way
that you can spill and reload without also needing a register for THAT
reload.  :)

-Chris

--
http://nondot.org/sabre/
http://llvm.org/

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev