llvm dev - Dec 2015 - Allowing virtual registers after register allocation

To say this first: This whole discussion about using virtregs until emit or
having growable physregs is hard to argue without actually having experience
trying to go either way.

Problems when using virtregs throughout the backend until emit time:
- The MC layer is using MCPhysReg (which is an uint16_t) and would need
retrofitting to support virtregs
- VirtRegs are assumed to have a definition, physregs can appear "out of
thin air" in some situations like function parameters, or exception objects
appearing in a register when going to a landingpad.
- VirtRegs are assumed to be interchangeable, replaceing vreg5 with vreg42
shouldn't affect the program semanic (given they both have the same register
class and we have no other defs/uses of vreg42), if you use virtregs for
parameter passing this won't be true anymore
- regmask clobbers only affect physregs
(- You cannot reuse the existing regalloc infrastructure, but IMO that's not
a good idea anyway for virtual ISAs)

Problems when allowing the dynamic creation of physregs:
- The current assumption of all register being known at tbalegen time will mean
that we probably need bigger changes to support dynamically growing physreg
lists and it may take a while until we have flushed out all places that relied
on a fixed-register number assumption.
- You probably do not want to compute/modify some information like register
class subsets/supersets. However as far as I can see we do not need subregister
support for the virtual ISA usecase and may be fine just not allowing the
combination of subregs with dynamic physreg creation.

Non-Issues:
- Liveness calculation should work as well with virtregs as with physregs

All in all it seems to me like using virtregs until emission time may take less
engineering effort to a point where it is 95% working, but will be a pain to
maintain in the long term because we suddenly have physreg like semantics on
virtregs for some targets (but not for "normal" ones).

- Matthias
> On Dec 10, 2015, at 1:13 PM, JF Bastien via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> > Whether it’s a hack or not depends on the sizes in question. Existing
> > X86 already has this property for 64 bit, there are registers which
> > simply don't exist
> > unless the target arch is 64 bit.  If WebASM folks are thinking of
> > allocating down to something like 32 or 64 registers, with maybe a
> > maximum of 128 or 256, then
> > making some portion of this reserved when a tighter allocation (only
> > coloring to 16 or 32) seems completely doable (and natural) using
> > all existing infrastructure, with nothing
> > special needed.
> 
> No argument from me on this point, however, whether or not a
relatively-small fixed number is acceptable I don't know. What does seem to
be the case, however, is that they need some kind of register use cost function
which makes the use of each new register increasingly expensive and/or the
ability to dynamically change the number of registers that are reserved at any
given time. The former is probably better.
> 
> > If getting into significantly larger numbers, then I
> > can see where this might be considered a hack.  But unless you are
> > talking about multi-thousands,
> > it does beg the question about what the extra generality is worth
> > compared to the engineering effort to design, implement and support
> > it.
> 
> This is exactly why I was in favor of reusing the existing infrastructure
for virtual registers.
> 
> We aren't talking about have 32 or 64 virtual registers. Most functions
should have just a few, but we are talking about having as many as the compiled
code needs: the VM will spill what's needed to a shadow stack that's not
user-accessible. This has interesting security properties, lets the VM do this
as optimally as it sees fit for the target ISA, and would otherwise require the
LLVM backend to emit an alloca which we then translate to a heap allocation to
the user-accessible "stack" (which lives in their heap).
> 
> Put another way: it seems sensible for a virtual ISA to have virtual
registers ;-)
> 
> I think Derek's proposal is sensible in that it doesn't have much
cost to the LLVM code base, and NVPTX shows precedent for working around that
limitation. We'd like virtual ISAs to be supported as first-class targets,
that has a small cost in LLVM's generality but should help remove hacks in
other virtual ISA implementations.
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

> On Dec 10, 2015, at 2:45 PM, Matthias Braun via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> To say this first: This whole discussion about using virtregs until emit or
having growable physregs is hard to argue without actually having experience
trying to go either way.
> 
> Problems when using virtregs throughout the backend until emit time:
> - The MC layer is using MCPhysReg (which is an uint16_t) and would need
retrofitting to support virtregs
> - VirtRegs are assumed to have a definition, physregs can appear "out
of thin air" in some situations like function parameters, or exception
objects appearing in a register when going to a landingpad.
> - VirtRegs are assumed to be interchangeable, replaceing vreg5 with vreg42
shouldn't affect the program semanic (given they both have the same register
class and we have no other defs/uses of vreg42), if you use virtregs for
parameter passing this won't be true anymore
> - regmask clobbers only affect physregs
> (- You cannot reuse the existing regalloc infrastructure, but IMO
that's not a good idea anyway for virtual ISAs)
> 
> Problems when allowing the dynamic creation of physregs:
> - The current assumption of all register being known at tbalegen time will
mean that we probably need bigger changes to support dynamically growing physreg
lists and it may take a while until we have flushed out all places that relied
on a fixed-register number assumption.
> - You probably do not want to compute/modify some information like register
class subsets/supersets. However as far as I can see we do not need subregister
support for the virtual ISA usecase and may be fine just not allowing the
combination of subregs with dynamic physreg creation.
> 
> Non-Issues:
> - Liveness calculation should work as well with virtregs as with physregs
> 
> All in all it seems to me like using virtregs until emission time may take
less engineering effort to a point where it is 95% working, but will be a pain
to maintain in the long term because we suddenly have physreg like semantics on
virtregs for some targets (but not for "normal" ones).

I agree with this (and with Quentin). Perpetuating virtual registers further
down the is pretty deeply troubling to me. It could certainly be made to work,
but I don’t think it’s the right way to go.
> 
> - Matthias
> 
>> On Dec 10, 2015, at 1:13 PM, JF Bastien via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>> 
>>> Whether it’s a hack or not depends on the sizes in question.
Existing
>>> X86 already has this property for 64 bit, there are registers which
>>> simply don't exist
>>> unless the target arch is 64 bit.  If WebASM folks are thinking of
>>> allocating down to something like 32 or 64 registers, with maybe a
>>> maximum of 128 or 256, then
>>> making some portion of this reserved when a tighter allocation
(only
>>> coloring to 16 or 32) seems completely doable (and natural) using
>>> all existing infrastructure, with nothing
>>> special needed.
>> 
>> No argument from me on this point, however, whether or not a
relatively-small fixed number is acceptable I don't know. What does seem to
be the case, however, is that they need some kind of register use cost function
which makes the use of each new register increasingly expensive and/or the
ability to dynamically change the number of registers that are reserved at any
given time. The former is probably better.
>> 
>>> If getting into significantly larger numbers, then I
>>> can see where this might be considered a hack.  But unless you are
>>> talking about multi-thousands,
>>> it does beg the question about what the extra generality is worth
>>> compared to the engineering effort to design, implement and support
>>> it.
>> 
>> This is exactly why I was in favor of reusing the existing
infrastructure for virtual registers.
>> 
>> We aren't talking about have 32 or 64 virtual registers. Most
functions should have just a few, but we are talking about having as many as the
compiled code needs: the VM will spill what's needed to a shadow stack
that's not user-accessible. This has interesting security properties, lets
the VM do this as optimally as it sees fit for the target ISA, and would
otherwise require the LLVM backend to emit an alloca which we then translate to
a heap allocation to the user-accessible "stack" (which lives in their
heap).
>> 
>> Put another way: it seems sensible for a virtual ISA to have virtual
registers ;-)
>> 
>> I think Derek's proposal is sensible in that it doesn't have
much cost to the LLVM code base, and NVPTX shows precedent for working around
that limitation. We'd like virtual ISAs to be supported as first-class
targets, that has a small cost in LLVM's generality but should help remove
hacks in other virtual ISA implementations.
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> 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
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On Thu, Dec 10, 2015 at 2:46 PM Matthias Braun via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> To say this first: This whole discussion about using virtregs until emit
> or having growable physregs is hard to argue without actually having
> experience trying to go either way.
>
Indeed, we are accumulating exactly this experience now, having started
with VRegs, as that seems like a more natural fit conceptually. The problem
is that we are essentially blocked on this (obviously lack of
PEI/frameindex elimination blocks a lot of things) so in order to make
further progress and get further experience we will need either a simple
change something like the one proposed or to do what NVPTX did and just
make our own copy of PEI.

>
> Problems when using virtregs throughout the backend until emit time:
> - The MC layer is using MCPhysReg (which is an uint16_t) and would need
> retrofitting to support virtregs
> - VirtRegs are assumed to have a definition, physregs can appear "out
of
> thin air" in some situations like function parameters, or exception
objects
> appearing in a register when going to a landingpad.
>
This is what Dan is trying to address with http://reviews.llvm.org/D14750.
The discussion on that change is essentially the same as the one going on
here.

> - VirtRegs are assumed to be interchangeable, replaceing vreg5 with vreg42
> shouldn't affect the program semanic (given they both have the same
> register class and we have no other defs/uses of vreg42), if you use
> virtregs for parameter passing this won't be true anymore
>
I believe this would be addressed for wasm with a mechanism like that in
D14750 (or the current special ARGUMENT pseudos we have now) in combination
with the fact that we remap the virtual registers into a different number
space in a way that takes the arguments into account, just before emission.

- regmask clobbers only affect physregs
> (- You cannot reuse the existing regalloc infrastructure, but IMO
that's
> not a good idea anyway for virtual ISAs)
>
Agreed.

>
> Problems when allowing the dynamic creation of physregs:
> - The current assumption of all register being known at tbalegen time will
> mean that we probably need bigger changes to support dynamically growing
> physreg lists and it may take a while until we have flushed out all places
> that relied on a fixed-register number assumption.
>
This seems like a really big deal to me; plus a lot of the discussion above
e.g. with regard to what the behavior of the pysical register classes, is
about properties which are really only relevant for register allocation
(and again I think we agree that we probably don't want to be using the
normal register allocator anyway).

> - You probably do not want to compute/modify some information like
> register class subsets/supersets. However as far as I can see we do not
> need subregister support for the virtual ISA usecase and may be fine just
> not allowing the combination of subregs with dynamic physreg creation.
>
> I think you are right.
> Non-Issues:
> - Liveness calculation should work as well with virtregs as with physregs
>
> All in all it seems to me like using virtregs until emission time may take
> less engineering effort to a point where it is 95% working, but will be a
> pain to maintain in the long term because we suddenly have physreg like
> semantics on virtregs for some targets (but not for "normal"
ones).
>
>
 Perhaps it would be worthwhile to flesh out a bit more precisely what
semantics are required.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151210/127018a1/attachment.html>

We had some additional discussion on this. There is a lot of concern
generally about post-RA passes which do not expect to have to handle
virtual registers; specifically if they unexpectedly start seeing virtual
registers, or if they work today but start making assumptions in the
future. We discussed considering a mechanism that would require
MachineFunctionPasses to "opt-in" and declare that they support
virtual
registers; this could be enforced via an assert or whatever, and it would
be clear and obvious (both for new and existing passes) whether a pass
should expect to deal with vregs or not. This kind of thing might also be
useful for the purposes MachineRegisterInfo::isSSA() and/or
MachineRegisterInfo::tracksLiveness() serve as well

I've been experimenting with such a mechanism (the details of how it would
be implemented could be a separate discussion) with X86 and WebAssembly,
and looking at what passes run, what would need to be modified, the effects
of disabling them, etc.

Currently the following target-independent passes run after register
allocation (ordered and categorized according to how they appear in
lib/CodeGen/Passes.cpp):

OptimizedRegAlloc: (run only if there is a RegAllocPass, which is not true
for wasm)
 StackSlotColoring
 PostRAMachineLICM
ShrinkWrap
PrologEpilogInserter
Machine late optimization:
 BranchFolderPass
 TailDuplicate
 MachineCopyPropagation
 PostRAScheduler
ExpandPostRAPseudos
ImplicitNullChecks (optional)
PostMachineScheduler or PostRAScheduler
GC:
 GCMachineCodeAnalysis
 GC info printer
Block Placement:
 MachineBlockPlacement
 MachineBlockPlacementStats
FuncletLayout
StackMapLiveness
LiveDebugValues

All of the pre-regalloc passes (and analyses) would just get marked as
supporting virtual registers.


Here are some notes about passes of interest:

PostRAMachineLICM (if not overriden by the target) is just the same
MachineLICM which runs before regalloc and so handles vregs already.

PrologEpilogInserter has some analysis phases (calculating CSR and frame
information, assigning spill slots, calculating frame offsets) and some
code insertion phases (inserting CSR spills/restores and prologs/epilogs,
eliminating FrameIndex), and finally a scavenging phase. Any of the
insertion phases can introduce virtual new registers, after which all
subsequent phases must be prepared to handle them. So it might make sense
to declare that this pass must support vregs anyway, or try to split it up
or otherwise more clearly define which parts must or need not have that
support.

BranchFolder already handles vregs. A comment at the top of the file
mentions that it should stay that way (suggesting that it was fixed up for
NVPTX), but that it can't handle SSA.

TailDuplicate is currently disabled for wasm via
TargetMachine::RequiresStructuredCFG()

MachineCopyPropagation: currently has checks (even for release builds) that
there are no vregs, and is currently disabled manually for wasm and NVPTX.

ExpandPostRAPseudos has 2 parts: LowerSubregToReg expects only physregs and
has asserts to ensure it.
LowerCopy simply calls TargetInstrInfo::copyPhysReg() to emit the
instructions for lowering COPYs (wasm's implementation of copyPhysReg()
just handles vregs) and is otherwise agnostic.

MachineBlockPlacement doesn't do anything at all to any MachineInstrs
itself, but just relies on TargetInstrInfo methods to update the branches.

I'll post again later with the prototype code.


On Thu, Dec 10, 2015 at 3:52 PM Derek Schuff <dschuff at google.com>
wrote:
> On Thu, Dec 10, 2015 at 2:46 PM Matthias Braun via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> To say this first: This whole discussion about using virtregs until
emit
>> or having growable physregs is hard to argue without actually having
>> experience trying to go either way.
>>
>
> Indeed, we are accumulating exactly this experience now, having started
> with VRegs, as that seems like a more natural fit conceptually. The problem
> is that we are essentially blocked on this (obviously lack of
> PEI/frameindex elimination blocks a lot of things) so in order to make
> further progress and get further experience we will need either a simple
> change something like the one proposed or to do what NVPTX did and just
> make our own copy of PEI.
>
>
>>
>> Problems when using virtregs throughout the backend until emit time:
>> - The MC layer is using MCPhysReg (which is an uint16_t) and would need
>> retrofitting to support virtregs
>> - VirtRegs are assumed to have a definition, physregs can appear
"out of
>> thin air" in some situations like function parameters, or
exception objects
>> appearing in a register when going to a landingpad.
>>
>
> This is what Dan is trying to address with http://reviews.llvm.org/D14750.
> The discussion on that change is essentially the same as the one going on
> here.
>
>
>> - VirtRegs are assumed to be interchangeable, replaceing vreg5 with
>> vreg42 shouldn't affect the program semanic (given they both have
the same
>> register class and we have no other defs/uses of vreg42), if you use
>> virtregs for parameter passing this won't be true anymore
>>
>
> I believe this would be addressed for wasm with a mechanism like that in
> D14750 (or the current special ARGUMENT pseudos we have now) in combination
> with the fact that we remap the virtual registers into a different number
> space in a way that takes the arguments into account, just before emission.
>
> - regmask clobbers only affect physregs
>> (- You cannot reuse the existing regalloc infrastructure, but IMO
that's
>> not a good idea anyway for virtual ISAs)
>>
>
> Agreed.
>
>
>>
>> Problems when allowing the dynamic creation of physregs:
>> - The current assumption of all register being known at tbalegen time
>> will mean that we probably need bigger changes to support dynamically
>> growing physreg lists and it may take a while until we have flushed out
all
>> places that relied on a fixed-register number assumption.
>>
>
> This seems like a really big deal to me; plus a lot of the discussion
> above e.g. with regard to what the behavior of the pysical register
> classes, is about properties which are really only relevant for register
> allocation (and again I think we agree that we probably don't want to
be
> using the normal register allocator anyway).
>
>
>> - You probably do not want to compute/modify some information like
>> register class subsets/supersets. However as far as I can see we do not
>> need subregister support for the virtual ISA usecase and may be fine
just
>> not allowing the combination of subregs with dynamic physreg creation.
>>
>> I think you are right.
>
>
>> Non-Issues:
>> - Liveness calculation should work as well with virtregs as with
physregs
>>
>> All in all it seems to me like using virtregs until emission time may
>> take less engineering effort to a point where it is 95% working, but
will
>> be a pain to maintain in the long term because we suddenly have physreg
>> like semantics on virtregs for some targets (but not for
"normal" ones).
>>
>>
>  Perhaps it would be worthwhile to flesh out a bit more precisely what
> semantics are required.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160113/9c8e6f28/attachment.html>