Marking a register as reserved midway through register allocation

Hey all,

I’m attempting to rewrite something that the AVR backend used to support (through an extremely dirty hack that was reverted before the upstreaming of the target).

The removal of the hack can be seen on GitHub

https://github.com/avr-llvm/llvm/pull/226/files

On the AVR architecture, the stack pointer is not in a standard register, but rather it is a special register which can only be accessed via I/O instructions. In order to implement stack spilling/restoring we need to adjust the stack pointer, which is a problem because we need the value of SP to be in a general purpose register for us to perform arithmetic on it.

In AVR-GCC, a frame pointer (the ‘Y’ register) is reserved if there are any spills in a method. This works fine because we can easily perform arithmetic on it and then save it into the real stack pointer via IO instructions.

I would like to do the same for LLVM. This is tricky however, because we don’t know if we need a frame pointer until we’ve finished register allocation and we’ve seen a spill.

In the event that we do see a spill, it is likely that the ‘Y’ register has already been allocated to some other variable, and so we somehow need to deallocate it and then rewind the regalloc. That is what the old hack above does.

Is there any way today I can deallocate a register and rewind allocation upon spilling?

Why not do it the other way around?

Mark Y as reserved, and then at the end of the function if there was exactly one spill then put that variable in Y instead.

If there were no spills then you lost nothing by reserving Y. If there were more than one then you need Y for this stack adjustment. So exactly one spill is the only case where you lost anything by reserving Y.

Which is probably pretty rare, to be honest.

I think that the “one spill” case might be a little less restrictive than that. If you have N spills, but the live ranges for the spills do not overlap then you could just spill to Y instead of the stack.

-Daniel

This is what most llvm CPU targets do:

  • Perform register allocation with all registers available
  • PrologEpilogInsertion will determine the final positions for the spill/reload stack slots. If we require additional instructions/registers to actually compute the addresses for the spills/reload then we use vregs for that. [1]
  • doScavengeFrameVirtualRegs() will use a RegisterScavenger instance to allocate the vregs: If there is a free register around it is used; Otherwise we do an emergency spill around the vreg lifetime. Targets have to ensure they reserved an emergency spillslot that can be accessed without additional registers in advance if there is a possibility that we need it.

If I understand you correct that strategy does not work on AVR somehow? Then you are probably out of luck and need to extend llvms CodeGen with new strategies.

  • Matthias

[1] There’s some restrictions on how vregs may be used here, like the defs/uses must stay within the same block.

Why not do it the other way around?
Mark Y as reserved, and then at the end of the function if there was exactly one spill then put that variable in Y instead.
If there were no spills then you lost nothing by reserving Y. If there were more than one then you need Y for this stack adjustment. So exactly one spill is the only case where you lost anything by reserving Y.
Which is probably pretty rare, to be honest.

This is definitely an interesting idea. I think this would be doable, but it would be a little dirtier than I’d like. We’d probably need to add a custom pass, and we’d also need to persist some spilling information on a TargetMachineFunction.

This is what most llvm CPU targets do:

  • Perform register allocation with all registers available
  • PrologEpilogInsertion will determine the final positions for the spill/reload stack slots. If we require additional instructions/registers to actually compute the addresses for the spills/reload then we use vregs for that. [1]
  • doScavengeFrameVirtualRegs() will use a RegisterScavenger instance to allocate the vregs: If there is a free register around it is used; Otherwise we do an emergency spill around the vreg lifetime. Targets have to ensure they reserved an emergency spillslot that can be accessed without additional registers in advance if there is a possibility that we need it.
    If I understand you correct that strategy does not work on AVR somehow? Then you are probably out of luck and need to extend llvms CodeGen with new strategies.

That sounds like a very similar situation to what I have, but I think that you’re right in that we would not be able to guarantee a free emergency spillslot because we’d need SP in the Y register in order to store the current value in the Y register, which is impossible.

I think I can see three different options

  1. Implement Bruce’s idea of always reserving the Y register and converting a spill (if we have one) to use it so that we do not waste a register
  • Upsides

  • Works for all register allocators at all optimisation levels

  • Does not change behaviour for any other targets- Downsides

  • A small amount of support code required1. Teach the register allocator to check reserved registers after performing the first spill (or maybe at the end of allocation of a function) and see if any more registers have been reserved. It could then use similar code to the GitHub PR I posted above to unassign any newly-reserved registers and rewind back.

  • Upsides

  • Will work for all targets

  • Is the most general solution- Downsides

  • More corner cases the register allocator is handling1. Subclass the register allocators specifically for AVR and add the functionality to a register allocator specifically for AVR

  • Upsides

  • All code required self-contained in one file- Downsides

  • Need to add subclasses for all register allocators

  • No other target subclasses a register allocator
    Thoughts welcome (and wanted)!

I assumed in that situation all those “spills” with non-overlapping ranges will have been consolidated into a single stack slot? i.e. “the maximum deficit of registers vs live values at any point in execution of the function is one”

But I didn’t look at the spilling logic.