Hi!
I’m developing a register allocator that works iteratively. It spills some virtual registers on each iteration until all the rest have physical ones assigned.
How can I spill some live intervals at the end of each iteration with new live intervals having correct weights?
Thanks.
I'm developing a register allocator that works iteratively. It spills some
virtual registers on each iteration until all the rest have physical ones
assigned.
Take a look at the linear scan allocator. It is also iterative: it uses the spiller interface to insert spill code, which creates (unspillable) intervals for the spill code it inserts.
How can I spill some live intervals at the end of each iteration with new
live intervals having correct weights?
The linscan allocator inserts spill code with infinite weight, take a look at how it works.
-Chris
So, as far as I understood live intervals with weight equal to HUGE_VAL are spilled and I don’t need to allocate physical registers for them, right? Shoud hasStackSlot method of VirtRegMap return true for these intervals’ reg members?
Well, someone correct me if am wrong, but, you still have to allocate
physical registers to them, because their values must be reloaded before
been used. But after you spill a register, you break its live ranges, so,
each use of that register can be loaded into a different physical. In my
register allocator, after I spill reg_v:
For each use of reg_v:
create a new reg_v'
replace reg_v by reg_v'
If the instruction containing reg_v' hasn't been scanned by the register
allocator, when it happens, reg_v' will receive a physical register. You
must assign to reg_v' a weight such that is is not spilled again,
otherwise you may enter on an infinite loop, always spilling the same
spilled register.
Fernando
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?
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);
}
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?
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
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
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_2In 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
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.
Hey, Daniel,
I am using the spiller from LLVM in order to insert spill code. My
register allocator decides which registers to spill, breaks its live range
by replacing each of its use by a new virtual register, and assign
physical registers to each of these virtuals. This information is passed
to the spiller via two methods of the VirtRegMap class: assignVirt2Phys,
that maps a virtual to a particular physical, and assignVirt2StackSlot,
that maps a virtual to a stack position. After register allocation is
done, the spiller inserts the loads and stores. This insertion is always
possible, because all the virtual registers, even those generated after
spilling, are mapped to some physical register.
Fernando