[LLVMdev] register scavenger

Arnold Schwaighofer arnold.schwaighofer at gmail.com
Sat Nov 10 15:12:50 PST 2012


Hi Reed,

the register scavenger (RS) also keeps track of live registers. This
way it "knows" that the register that was spilled/restored far apart
is available.

Let say you had the following code. You need to find a register to
keep vreg1 and vreg2 in.

R1 = .... // <- RS current liveness state; we have called
RS->forward(It) where It points to here
vreg1 = add SP, 1000
 ... = load vreg1
... // more code
vreg2 = add SP, 2000
... = load vreg
... = R1

When you come to the definition of vreg1 you (or lets say the
scavengeFrameVirtualRegs function) call the RS to scavenge a register.
The current internal state (the liveness information) is the liveness
up to (including) the definition of R1.
The register scavenger will look for a register - and so lets assume
there is none free. Next it looks for one that it can spill and
restore far apart (you don't want two spills/restores happening).
Let's say this register turns out to be R1. So the scavenger will
insert a spill before vreg1 (the current instruction) and will return
R1 as a free register. The client can then use this register to
replace vreg1 with. Then the client is expected to call RS->forward(I)
which will update the current liveness state (include the store of
R1). R1 will then be available for the next time you call RS->scavenge
- in our example for vreg2.

R1 = ...
store R1, ScavengeSlot // Spill
vreg1 = add SP, 1000
 ... = load vreg1 <kill>
... // more code
vreg2 = add SP, 2000
... = load vreg2 <kill>
R1 = load ScavengeSlot // Restore
... = R1

===> we replace vreg1 with R1 and advance the RS' state by calling
RS->forward(It)

R1 = ...
store R1, ScavengeSlot // Spill
R1 = add SP, 1000
 ... = load R1 <kill>  <-- It   AvailRegs {R1}
... // more code
vreg2 = add SP, 2000
... = load vreg2 <kill>
R1 = load ScavengeSlot // Restore
... = R1

The client has to keep liveness current by calling
RS->forward(MachineBasicBlock::iterator).


On Sat, Nov 10, 2012 at 4:17 PM, Reed Kotler <rkotler at mips.com> wrote:
> I'm confused as to the logic used in the register scavenger when it cannot
> find a free register.
>
> I would think that it would want to free up the emergency spill slot
> immediately after it's use, because otherwise there is a chance of needing
> to use the emergency slot again and not be able to.
>
> Instead it tries to restore it only right before register it is freeing up.
>
> Maybe I'm misunderstanding this code.
>
>   // If the target knows how to save/restore the register, let it do so;
>   // otherwise, use the emergency stack spill slot.
>   if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
>     // Spill the scavenged register before I.
>     assert(ScavengingFrameIndex >= 0 &&
>            "Cannot scavenge register without an emergency spill slot!");
>     TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex,
> RC,TRI);
>     MachineBasicBlock::iterator II = prior(I);
>     TRI->eliminateFrameIndex(II, SPAdj, this);
>
>     // Restore the scavenged register before its use (or first terminator).
>     TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC,
> TRI);
>     II = prior(UseMI);
>     TRI->eliminateFrameIndex(II, SPAdj, this);
>   }
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev



More information about the llvm-dev mailing list