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

[Fernando Magno Quintao Pereira]

Hi, Roman,

     maybe I can try to answer this. I think that all boils down to having 
register to reload spilled values. 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. 
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. Sometimes it is 
possible to avoid the reloading with instruction folding, but this is not 
always the case. 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.

best,

Fernando

> 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
>
>
>      Lesen Sie Ihre E-Mails auf dem Handy.
> www.yahoo.de/go
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>