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);
}
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
I think I answered my own question. When you use the scavenged register, you set it to kill and now it's available as a free register for further needs , until it has to be restored. So that is the reason for chosing the register needed the furthest away from the original place; because no further emergency slot manimupatation will be needed as long as possible. On 11/10/2012 02:17 PM, Reed Kotler 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); > }
Thanks! When you say that the client calls "forward", who do you mean? Do I need to call forward in addition to marking the use "kill"? Reed On 11/10/2012 03:12 PM, Arnold Schwaighofer wrote:> 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
CC the list. On Sat, Nov 10, 2012 at 6:30 PM, Arnold Schwaighofer <arnold.schwaighofer at gmail.com> wrote:> Assuming you use the scavenger in your own code yes. > > A usage could look like: > > for all basic blocks BB: > RS->enter(BB) > for all instructions CurrInst in block order: > if CurrInst has virtual def > CurrReg = RS->scavenge(CurrInst) > replace virtual def by CurReg > else if Insts has virtual use > replace virtual use by CurReg > RS->forward(CurrInst) > > > Look at scavengeFrameVirtualRegs in PrologEpilogInserter.cpp for more > detail (I left out some, error checking, etc). > > On Sat, Nov 10, 2012 at 6:15 PM, Reed Kotler <rkotler at mips.com> wrote: >> Thanks! >> >> When you say that the client calls "forward", who do you mean? >> >> Do I need to call forward in addition to marking the use "kill"? >> >> Reed
You mean when I "explicity" use it by calling methods of register scavenger? Right now I'm just allocating virtual registers that will be resolved by the use of register scavenger and I'm also providing an override of the virtual method saveScavengerRegister. In Mips16, I have an extra mips 32 register (not usually very useful since it can only be used in a move instruction) I can use instead of having to go to the stack for an emergency slot. On 11/10/2012 04:39 PM, Arnold Schwaighofer wrote:> CC the list. > > On Sat, Nov 10, 2012 at 6:30 PM, Arnold Schwaighofer > <arnold.schwaighofer at gmail.com> wrote: >> Assuming you use the scavenger in your own code yes. >> >> A usage could look like: >> >> for all basic blocks BB: >> RS->enter(BB) >> for all instructions CurrInst in block order: >> if CurrInst has virtual def >> CurrReg = RS->scavenge(CurrInst) >> replace virtual def by CurReg >> else if Insts has virtual use >> replace virtual use by CurReg >> RS->forward(CurrInst) >> >> >> Look at scavengeFrameVirtualRegs in PrologEpilogInserter.cpp for more >> detail (I left out some, error checking, etc). >> >> On Sat, Nov 10, 2012 at 6:15 PM, Reed Kotler <rkotler at mips.com> wrote: >>> Thanks! >>> >>> When you say that the client calls "forward", who do you mean? >>> >>> Do I need to call forward in addition to marking the use "kill"? >>> >>> Reed