llvm dev - May 2017 - 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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170501/d4f6a0a0/attachment-0001.html>

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.

On Mon, May 1, 2017 at 6:27 AM, 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?
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170501/b89a0b7f/attachment.html>

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


On May 1, 2017, at 2:19 AM, Bruce Hoult via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:

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.

On Mon, May 1, 2017 at 6:27 AM, Dylan McKay via llvm-dev <llvm-dev at
lists.llvm.org<mailto: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?



_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170501/ed3a80ed/attachment.html>

> 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
<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/20170501/2f0c440c/attachment.html>

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