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

[Roman Levenstein]

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