register scavenger

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).

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.

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

CC the list.

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.

I ran into another issue with register scavenger.

In my case, I don't need a place on the stack for an emergency spill slot.

I have these free mips32 registers, that are not in general very useful for other things, for the emergency spill slot. I can move to and from mips16 (subset of mips32) registers and mips32 registers.

I also have a situation where I need two free registers so then the
possibility that two emergency storage places are needed. This can
occur during prologue/epilogue and in some unusual cases during function call.

In turns out to be not be simple to add/subtract a large (>16 bit constant) to/from SP using one register.

SP is not a mips16 register and there is no way to add another register or large constant to it. You have to move SP to a mips 16 register and then add the value of another register which has already been loaded
with a large constant. So that means that two registers are needed.

I'm wondering if my version of saveScavengerRegister uses say T0 and T1 (mips32 registers) for emergency spill slots will work. The usual inline code which goes to the emergency slot only
allows for one emergency spill slot. But my routine would only fail if
more than two emergency slots were needed but maybe other things would be messed up.

I can work around the problem without register scavenger but in that case, I'm just pessimistically planning for the case where two emergency slots are needed.

This function which adjusts the stack pointer is called from the prologue and epilogue code. I don't know the size of the stack instruction selection and register allocation has taken place so
I don't know if I need to go to this special mode for adjusting the stack early on.

As I'm writing this, I realize that there is a hack that may be safe that I could use but would still be interested to know the answer to my question.

The hack that may be okay is this:

When the stack pointer needs to be incremented during function entry (prologue generation), I know that registers v0 and v1 (scratch registers except at function return) are free.

Similarly, when the stack pointer needs to be incremented during function return, I know that registers a0, a1 (argument registers are free).

So I may be able to just know that there will be no problem, i.e. there will not even be any call to register scavenger during prologue and epilogue. I have to think about this.

There is another such place where a large stack adjustment could be needed, besides prologue and epilogue and I'd have to think more about this to know if I could make this work there; but that is such a rare
occurrence that I could take a more pessimistic approach in that one case.

I ran into another issue with register scavenger.
I'm wondering if my version of saveScavengerRegister uses say T0 and T1
(mips32 registers) for emergency spill slots will work. The usual inline
code which goes to the emergency slot only
allows for one emergency spill slot. But my routine would only fail if
more than two emergency slots were needed but maybe other things would be
messed up.

Currently, PEI::scavengeFrameVirtualRegs is not set up to handle 2
concurrently live vregs (easy to fix, change the code in PEI to use an
array of - instead of the two variables - VirtReg, ScratchReg). Also,
the RegisterScavenger does not support scavenging for 2 live regs.
This one would be a little more involved to fix I think. You would
have to change the logic in RegisterScavenger involving ScavengedReg
to also use an array, then in your TRI->saveScavengerRegister
implementation you would have to check the liveness of the first spill
register when you scavenge, and if it is live use the second. You
might be able to use RegisterScavengers internal liveness state for
this. I think it tracks registers that are not allocatable and not
reserved - I am not sure about this though.

I can work around the problem without register scavenger but in that case,
I'm just pessimistically planning for the case where two emergency slots are
needed.

This function which adjusts the stack pointer is called from the prologue
and epilogue code. I don't know the size of the stack instruction selection
and register allocation has taken place so
I don't know if I need to go to this special mode for adjusting the stack
early on.

As I'm writing this, I realize that there is a hack that may be safe that I
could use but would still be interested to know the answer to my question.

The hack that may be okay is this:

When the stack pointer needs to be incremented during function entry
(prologue generation), I know that registers v0 and v1 (scratch registers
except at function return) are free.

Similarly, when the stack pointer needs to be incremented during function
return, I know that registers a0, a1 (argument registers are free).

So I may be able to just know that there will be no problem, i.e. there will
not even be any call to register scavenger during prologue and epilogue. I
have to think about this.

We are doing something similar for hexagon (I don't think the code is
in tree, though) for function prolog/epilog code.