llvm dev - Feb 2008 - [LLVMdev] LiveInterval spilling (was LiveInterval Splitting & SubRegisters)

Hi Evan,

I have a few questions about current implementation of live intervals
spilling, which is required for the implementation of Extended Linear
Scan algorithm.

--- Evan Cheng <evan.cheng at apple.com> wrote:
> > On Wednesday 23 January 2008 02:01, Evan Cheng wrote:
> >> On Jan 22, 2008, at 12:23 PM, David Greene wrote:
> >>> Evan,
> >>>
> >>> Can you explain the basic mechanics of the live interval
> splitting code?
> >>> Is it all in LiveIntervalAnalysis.cpp under
addIntervalsForSpills
> >>> and child routines?  What is it trying to do?
> >>
> >> It's splitting live intervals that span multiple basic blocks.
> That is, when an interval is spilled, it introduce a single reload
per
>>> basic block and retarget all the uses to use the result of the
> single reload. It does not (yet) split intra-bb intervals.
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

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
>

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