[llvm-dev] Marking a register as reserved midway through register allocation

[Dylan McKay via llvm-dev]

>
> 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 required
      2. 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 handling
      3. 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)!

On Tue, May 2, 2017 at 8:23 AM, Matthias Braun <mbraun at apple.com> wrote:

>
> On Apr 30, 2017, at 8:27 PM, Dylan McKay via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> 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?
>
>
> 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170502/2e36ab30/attachment.html>