[LLVMdev] LiveInterval spilling (was LiveInterval Splitting & SubRegisters)

[Evan Cheng]

This is how the allocator was originally designed. Basically spilling  
a live interval is simply to split it many smaller pieces, one per  
define and use. Therefore, the allocator must guarantee every little  
piece is assigned a register right away to prevent further spilling  
(this is ensured by assigning them infinite spill weight). It is not  
designed with iterative spilling in mind.

Obviously this approach can sometimes cause performance issue. That's  
why we are starting to introduce live interval splitting after 2.1 and  
you can expect more changes along the line in the not too distant  
future.

Evan

On Feb 15, 2008, at 3:13 PM, Roman Levenstein wrote:

> Hi Fernando,
>
> --- Fernando Magno Quintao Pereira <fernando at cs.ucla.edu> wrote:
>>
>> Hi, Roman,
>>
>>     maybe I can try to answer this. I think that all boils down to
>> having  register to reload spilled values.
>
> Ok. That I can follow.
>
>> Once a register is spilled, its live  range is split into smaller
>> pieces. These pieces most be contained into registers, and it is the
>> task of the allocator to find  these registers.
>
> I'm not quite sure about the last statement. See below.
>
>> Imagine that you have something like:
>>
>> Before           After
>> allocation:      allocation:
>> a := 1           a(R1) := 1 // a is assigned to R1
>>   |              // store R1 into M1
>>   |
>>   |              // 'a' is spilled into stack slot M1
>>   |
>>   |              // assign 'a' to R2, and load M1 into R2
>> b := a           b(Rx) := a(R2)
>>   |
>>   |
>>   |
>>   |
>>   |              // assign 'a' to R3, and load M1 into R3
>> c := a           c(Ry) := a(R3)
>>
>> So, the register is necessary for doing the reloading.
>
> Yes. But as you show above, it may happen that the same spilled  
> virtual
> interval is reloaded into _multiple different_ physical registers
> during its lifetime. So, what is the reason to assign only one (!)
> physical register to the virtual interval by means of
> VRM.assignVirt2Phys() and to do it actually in advance? What is the
> semantics of it? I'd really like to understand it better. How does  
> this
> solve the problem described above? Wouldn't it be better if the  
> spiller
> or code rewriter (that replaces virtual regs with the corresponding
> allocated physical regs) would decide dynamically (after regalloc
> finished doing its decisions about non-spilled intervals) based on
> case-by-case approach and taking into account current set of free
> physical registers which of them could be used for reloading the
> spilled register at a given point of execution? So, every time there  
> is
> a use of a spilled register, such a spiller/rewriter would try to find
> a free physical register, where it could load the spilled value from
> memory. Once the operation with this reloaded value is over, it could
> eventually free this physical register for other purposes.
>
> Of course, it can happen that in some high register pressure  
> situations
> you cannot dynamically find a free physical register to reload a
> spilled value, because all of them are occupied. But then you could
> temporarily evict one of them into memory or other location, use the
> freed physical register for the reload of spilled value and operations
> on it, and once it is done, restore the evicted register back into the
> physical one.
>
> Does it make some sense? Or do I still miss something very obvious?
>
>> Sometimes it
>> is possible to avoid the reloading with instruction folding, but this
>
>> is not  always the case.
>
> Yes. Sometimes you really need it to be in a physical register.
>
>> Also, in the new allocator used in LLVM, I
>> believe that some live ranges may be split into bigger pieces, and
>> this would save some  reloads.
>
> Seems so.
>
> Best,
>  Roman
>
>>> When I look at the code, it seems that when linear scan
>> regalloc
>>> decides to spill a given live interval, it calls
>> addIntervalsForSpills.
>>> This function would split the original live interval into several
>>> intervals according to the principle described by you above. Each
>> of
>>> this intervals (split children) then gets a stack slot allocated
>> (and
>>> all these split intervals get the same stack slot?) and then those
>> new
>>> splitted intervals are added to unhandled set. Thus they get a
>> chance
>>> to get physical registers assigned to them, independently. So,
>>> actually, they are not quite "spilled" intervals (since they are
>> not
>>> really spilled and located in memory) and may get a physical
>> register.
>>> Is my understanding of the algorithm correct so far?
>>>
>>> What I don't quite understand is the following:
>>> Why do live intervals with an allocated stack slot should also
>> always
>>> have a physical register assigned to them? How should a register
>>> allocator decide, which physical register should be used for that?
>>>
>>> For example, in my version of Sarkar's Extended Linear Scan I
>> sometimes
>>> spill the whole live interval. So, I assign a stack slot to it. But
>>> LLVM requires also a physical register to be assigned to each such
>> live
>>> interval as well. How do I decide which physical register should be
>>> taken? Why can't the local spiller or the former rewriteFunction()
>> part
>>> of the RegAllocLinearScan find out on their own which of the
>> currently
>>> available for allocation physical registers should be taken at a
>> given
>>> point for a reload or for a spilling operation for a given spilled
>> live
>>> interval? Wouldn't it be more convenient? You just say that the
>>> interval is spilled and the rest is done "by magic"? Or may be I'm
>>> missing something about how spilling currently works in LLVM?
>>>
>>> Thanks in advance for any clarification of this issue.
>>>
>>> -Roman
>>>
>
>
>
>      Machen Sie Yahoo! zu Ihrer Startseite. Los geht's:
> http://de.yahoo.com/set
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev