llvm dev - Aug 2006 - [LLVMdev] Recalculating live intervals

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?

On 8/21/06, Fernando Magno Quintao Pereira <fernando at cs.ucla.edu>
wrote:
>
>
> > So what addIntervalsToSpills returns are new intervals to allocate
with
> > infinite weights, right?
> > And I need not to allocate the old interval. Should hasStackSlot
return
> true
> > on its register then?
> >
>
> I am not very sure about addIntervalsToSpill, but, for all the registers
> created to replace a spilled registers, they must have a stack slot
> assigned to them. I am sending you my spilling method, so you can have an
> example:
>
>
>
//===--------------------------------------------------------------------------
> // This method performs register spilling. The parameter indicates a class
> of
> // registers. The spilling algorithm must evict a register from the same
> class
> // as the parameter. I am using the VirtRegMap class to place loads and
> stores.
>
>
//===--------------------------------------------------------------------------
> void RegAllocChordal_Fer::spill(
>    unsigned v_reg,
>    KillingSites_Fer & ks,
>    const MachineBasicBlock & mbb
> ) {
>    // First, find a place to store this register. Of course, this will be
> done
>    // by the implementation of vrm. We just have to ask it.
>    int slot = vrm->assignVirt2StackSlot(v_reg);
>    unsigned p_reg = this->reg_mapping->get_physical_location(v_reg);
>
>    // Now, it is necessary to break the live range of the spilled
> register.
>    // This is done by creating new virtual registers, and substituting
> the
>    // spilled register by the new registers.
>    MachineInstr * last_seen;
>    std::vector< MachineInstr * > & use_sites >
> this->def_use_sites->get_use_sites(v_reg);
>    for(unsigned u = 0; u < use_sites.size(); u++) {
>        MachineInstr * mi = use_sites[u];
>        if(mi == last_seen) {
>            continue; // this happens when the same virtual is used
> multiple
>                      // times in the same instruction.
>        }
>        unsigned new_reg = create_new_virtual_register(v_reg);
>        if(mi->getParent()->getNumber() =>
ks.get_basic_block()->getNumber()) {
>            ks.replace_used_reg(mi, new_reg, v_reg);
>        }
>        this->vrm->grow();
>        this->reg_mapping->grow();
>        this->vrm->assignVirt2StackSlot(new_reg, slot);
>        for(unsigned t = 0; t < mi->getNumOperands(); t++) {
>            MachineOperand & mo_aux = mi->getOperand(t);
>            if(mo_aux.isRegister() && mo_aux.getReg() &&
mo_aux.isUse()) {
>                if(mo_aux.getReg() == v_reg) {
>                    mo_aux.setReg(new_reg);
>                    this->reg_mapping->set_color_spilled_register
>                                                           (new_reg,
> p_reg);
>                }
>            }
>        }
>        last_seen = mi;
>    }
>
>    // this method will clean the machine register, e.g. p_reg, that is
> been
>    // currently used to hold the color of v_reg.
>    this->reg_mapping->liberate_color(p_reg);
>
>    clean_live_range(ks, v_reg, mbb);
> }
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>


-- 
Nae king! Nae quin! Nae laird! Nae master! We willnae be fooled again!
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20060822/d6f2cc53/attachment.html>

> 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?
>
Yes. The stack slot is the place where the value will be stored in memory,
but, when that value is effectively used in the code, you must load it
into a physical register. Assume that reg_v is mapped to stack slot x, and
there is an instruction such as add reg_1 := reg_v reg_2, where reg_1 is
mapped to phys_1, reg_v is mapped to phys_v, and reg_2 is mapped to
phys_2. Your final code will be like:

load phys_v, x
add phys_1 := phys_v, phys_2

In order to insert load/store instructions, you can use the VirtRegMap
class. The spiller, that is implemented in VirtRegMap.cpp will do that.
For an example, see RegAllocLinearscan.cpp. Another way is to insert
the load/store instructions yourself. This is done in RegAllocLocal.cpp,
for example.

Best,

Fernando

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/

Fernando Magno Quintao Pereira 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?
>>
> 
> Yes. The stack slot is the place where the value will be stored in memory,
> but, when that value is effectively used in the code, you must load it
> into a physical register. Assume that reg_v is mapped to stack slot x, and
> there is an instruction such as add reg_1 := reg_v reg_2, where reg_1 is
> mapped to phys_1, reg_v is mapped to phys_v, and reg_2 is mapped to
> phys_2. Your final code will be like:
> 
> load phys_v, x
> add phys_1 := phys_v, phys_2
> 
> In order to insert load/store instructions, you can use the VirtRegMap
> class. The spiller, that is implemented in VirtRegMap.cpp will do that.
> For an example, see RegAllocLinearscan.cpp. Another way is to insert
> the load/store instructions yourself. This is done in RegAllocLocal.cpp,
> for example.
By the by, I don't remember whether you are inserting spills yourself or
not, but you really should try to not do that if you are.

It's much better to have an interface that knows how to spill things in
a good way, and how to place code for spills, and just use that, instead
of tying all the knowledge about how to spill directly into the allocator.

--Dan