[LLVMdev] Recalculating live intervals

[Chris Lattner]

On Tue, 22 Aug 2006, Anton Vayvod wrote:
> I'm not sure about one thing: you assign stack slot to each new register you
> replace the spilled one with. And then you need to allocate physical
> registers to them. Is it possible to assign physical register to the virtual
> one which has a stack slot already?

The spiller is very simple, it basically works like this (at a high 
level):

1. Your RA decides that it has to spill a live interval.  It tells the
    spiller to spill the live interval.
2. The spiller (actually the addIntervalsForSpills method) inserts a
    number of very small live ranges that are unspillable into the
    LiveIntervalAnalysis set.  It inserts one for each def of the value and
    one for each use of it.
3. These intervals come back to your RA, and they *must* be assigned
    physregs.  Worst case, these registers will be used to insert reload
    code that either loads the value before a use, or are the destination
    register for a store.  These values are unspillable because they have
    trivially small live ranges (just the one instruction).
4. Once all registers are assigned, the spiller runs.  There are multiple
    spiller implementations, but the default uses local analysis to
    optimize spill code.  For example, if you have:

... = X + 4
... = X - 1

instead of inserting:

R = load [Xslot]
... = R + 4
R2 = load [Xslot]
... = R2 - 1

it will insert:

R = load [Xslot]
... = R + 4
... = R - 1

The spiller requires that you assign a reg to each of the small, 
unspillable, liveranges, so that it is guaranteed to have a register that 
can be used for the reload.  Once the original liverange is spilled, it is 
only ever associated with the stack slot, these small live ranges are 
always assigned registers, and it is up to the spiller to ensure the spill 
code is optimized reasonably well.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/