Register allocation in two passes

Hello,

I’m having a curious design conflict related to reserving registers before the register allocator pass is executed with the backend I’m writing. Basically, what I need is to reserve a certain register only if frame space is allocated in the stack, more precisely I’m interested in the case where a register spill occurs.
In order to know if a register is spilled the register allocator has to be executed so i can reserve this special reg, but since the register reservation occurs before the allocator is executed there’s no way to get this info in only a single pass.
The only solution i can think of is running the regalloc twice, first to see if any regs are spilled without performing any changes and a second one for doing the real allocation. As a test I’ve managed to do this with the Greedy regalloc by making the first regalloc execution to not perform a virtreg rewrite at the end of the function pass. But i really want to know if this is safe and if there’s a better way of doing it.

Thanks for any suggestions

The best solution is probably to convert your "reserved" register into an "allocatable" register that is forced to allocate to certain operands (presumably involved in spill code) by defining physical register operands. When live ranges for those special operands are created (on-the-fly), they would need to "evict" any other live ranges currently allocated to their special register with overlapping live ranges. The existing eviction mechanism might even be sufficient to handle it.

But if you really want to reserve the register, you could do that as well. You would do an "en masse" eviction of any live ranges allocated to that register at the time of the first spill. Then prevent anyone else from allocating it, for example by creating a fake live range that spans the entire function.

Neither of these solutions is currently implemented, but the new design supports this sort of thing well, and it's not an uncommon problem to face when porting a backend. I think it would be neat to support this, but Jakob may have a better how it should be done.

-Andy

Yes, I want the register to be allocatable when there are no stack frames used in the function so it can be used for other purposes. In fact, I looked at how other backends solve this problem, but they are all too conservative by always reserving the register which in my case it is not a good solution because of the performance impact of not having this register available.

I find very interesting what you mentioned of tying the physical reg to spill code. I’ve created a pseudo instruction for spill code and i’ve tied this physical reg as one of its operands (this register is sort of a shadow reg of the stack pointer where it can be used as a normal reg when there’s no stack manipulation in the function or as the SP when regs are spilled).
Then if I understood correctly the second part is making the regalloc aware of this so it can evict other live ranges using this register to avoid the conflict of both using this register freely and in the spill code which is what is happening to me, however I’m not very confident with myself on touching the regalloc.

I’ve also added Jakob (i hope he doesn’t mind :slight_smile: ) to this thread so he can give his point of view.

Thanks for the reply Andy.

It's not really clear if you actually need that register to be reserved throughout the function, or if you just need it to be available around spill code. Both are possible, though.

Note that this is a bit of a hack, since it won't work with the fast register allocator. You will need some custom code in RAGreedy since the current target APIs don't support this.

When you spill, you can evict live ranges assigned to your 'reserved' register and put them back on the work queue. See for example the RAGreedy::LRE_WillShrinkVirtReg() callback.

You can choose to evict all live ranges assigned to that register and reserve it, or you can just evict the single live range crossing your spill code if you just need the register to be available for spilling.

You can also use the PBQP register allocator which already supports multi-pass allocation. It's probably quite simple to reserve a register after pass 1 spills.

/jakob

Thanks for all the hints Jakob, I’ve added the following piece of code after the spill code handling inside selectOrSplit() (ignoring some control logic):

for (LiveIntervals::const_iterator I = LIS->begin(), E = LIS->end(); I != E;
++I)
{
unsigned VirtReg = I->first;
if ((TargetRegisterInfo::isVirtualRegister(VirtReg))
&& (VRM->getPhys(VirtReg) == REG_Y))
{
LiveInterval &LI = LIS->getInterval(VirtReg);
unassign(LI, REG_Y);
enqueue(&LI);
}
}
RegClassInfo.runOnMachineFunction(VRM->getMachineFunction()); // update reserve reglist

So similar to what’s done in LRE_WillShrinkVirtReg(), it searches for live intervals where REG_Y is allocated and evicts them for reallocation. I don’t know if there’s a faster way of doing this but it’s working :slight_smile:
About your first question: the register has to be reserved throughout the whole function.

Thanks for the help

Thanks for all the hints Jakob, I've added the following piece of code after the spill code handling inside selectOrSplit() (ignoring some control logic):

  for (LiveIntervals::const_iterator I = LIS->begin(), E = LIS->end(); I != E;
       ++I)
  {
    unsigned VirtReg = I->first;
    if ((TargetRegisterInfo::isVirtualRegister(VirtReg))
        && (VRM->getPhys(VirtReg) == REG_Y))
    {
      LiveInterval &LI = LIS->getInterval(VirtReg);
      unassign(LI, REG_Y);
      enqueue(&LI);
    }
  }
RegClassInfo.runOnMachineFunction(VRM->getMachineFunction()); // update reserve reglist

So similar to what's done in LRE_WillShrinkVirtReg(), it searches for live intervals where REG_Y is allocated and evicts them for reallocation. I don't know if there's a faster way of doing this but it's working :slight_smile:

Looks good.

It is probably faster to scan the LiveIntervalUnion for REG_Y for assigned virtual registers, but the above code will work just fine.

Technically, you should also check REG_Y's aliases, but there probably aren't any.

About your first question: the register has to be reserved throughout the whole function.

Thanks for the help

Glad to help.

/jakob

Jakob I’ve just noticed that I’m getting false positives about spills when there are actually none.
What is happening is that although execution reaches to the line spiller().spill(LRE); inside RAGreedy::selectOrSplit() the insertion of the spill is avoided because the register gets rematted. This is the debug output I’m getting to show what I mean:

Inline spilling DLDREGS:%vreg25,1.436782e-03 = [344r,640r:0) 0@344r
From original %vreg8,1.838235e-03 = [224r,640r:0) 0@224r
Value %vreg25:0@344r may remat from %vreg25 = LDIWRdK 2; DLDREGS:%vreg25
remat: 632r %vreg28 = LDIWRdK 2; DLDREGS:%vreg28
640e %R15R14 = COPY %vreg28; DLDREGS:%vreg28
interval: %vreg28,inf = [632r,640r:0) 0@632r
All defs dead: %vreg25<def,dead> = LDIWRdK 2; DLDREGS:%vreg25
Remat created 1 dead defs.
Deleting dead def 344r %vreg25<def,dead> = LDIWRdK 2; DLDREGS:%vreg25
0 registers to spill after remat. <----- NO SPILL

My question is how could I detect this behaviour so i don’t get any false positives? I’ve thought of checking if the variable NewVRegs increases in size after the call to the spill() method meaning that a remat happened, but I don’t know if this is always correct in all situation and another important thing, are there any more cases where a spill could be avoided getting more false positives?

Thanks for your help.

The spiller will be calling into your target's storeRegToStackSlot hook when it actually inserts a spill. Make a note then.

/jakob

Ohh true, that did it, thanks Jakob!