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

[Fernando Magno Quintao Pereira]

I see your issues.

(I will be talking about LLVM 2.1, before Evan added the live range 
splitting thing).

Once a register is spilled, LLVM replaces each use of it 
with a new, fresh virtual, so, my code before was, indeed, an abuse of 
notation. The new code would be like:

a := 1      a := 1               a(R1) := 1 // a is assigned to R1
    |        M1 := store a        M1 := store R1
    |        |                    |
    |        |                    // 'a' is spilled into stack slot M1.
    |        |                    // new registers a1 and a2, also
    |        |                    // sharing M1 are created.
    |        |                    |
    |        |                    |
    |        a1 := load M1        R2 := load from M1
b := a      b := a1              b(Rx) := a1(R2)
    |        |                    |
    |        |                    |
    |        a2 := load M1        R3 := load from M1
c := a      c := a2              c(Ry) := a2(R3)

So, after the spill is detected, the source code will change a little bit, 
to reflect this. Once the allocator finds, say, a1, it treats is as an 
ordinary virtual. Notice that those load instructions are, indeed, 
inserted by the Spiller, after register allocation is over. So, each of 
these registers a, a1 and a2 can be assigned to different registers.

best,

Fernando

>> 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.