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

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.
How is this different from the way the spiller used to work, looking
for reloads it could reuse?  Didn't that have the same goal of not
reloading a spilled value multiple times in a basic block?

                                            -Dave

On Jan 23, 2008, at 2:40 PM, David Greene <dag at cray.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.
>
> How is this different from the way the spiller used to work, looking
> for reloads it could reuse?  Didn't that have the same goal of not
> reloading a spilled value multiple times in a basic block?
Right. But that should not be spiller's job. It's also dependent on  
arbitrary register allocation order. Reload and spill folding makes it  
more complicated.

Evan
>
>
>                                            -Dave
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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