llvm dev - Jan 2016 - Allowing virtual registers after register allocation

Here are 2 patches, which are independent of each other.

The first splits PrologEpilogInserter into 2 parts :
http://reviews.llvm.org/D16481
After looking at the code I thought it made more sense for the major split
to include whether callee-saved register spills are supported. So for
non-virtual targets, virtual registers are not supported and scavenging is
optionally supported, and vice versa for virtual targets. The base case
includes just frame finalization, prolog/epilog code insertion and
FrameIndex elimination. The CSR-supporting case includes CSR spilling and
optionally scavenging.
It's a little bit ugly because e.g. most of the target hooks (even those
used in the core pieces like FI elimination) take a pointer to a
RegScavenger object which could be null, and there's still a little bit of
code in the FI elimination code that takes CSR spilling into account. But I
do think it is an improvement, and I'd be interested in feedback. This
patch could be ready to land if people are happy with the design.

The other (http://reviews.llvm.org/D16483 )is the aforementioned prototype
for requiring MachineFunctionPasses to opt-in to supporting virtual
registers. It's only done for WebAssembly and X86 so far as a proof of
concept. The interesting bit to look at is the way it's implemented (right
now it's just a virtual method that's called inside an assert which can
be
compiled away) and the passes that will opt-in. It's mostly a concrete
version of the info I put in my previous post. Before it lands I'll have to
update the rest of the targets, and will probably manually expand the
SUPPORTS_VIRTUAL_REGISTERS macro which I used for my experimental
convenience (unless you think it's actually better that way).

Thanks for your help,
-Derek

On Wed, Jan 13, 2016 at 3:40 PM Quentin Colombet <qcolombet at apple.com>
wrote:
> Hi Derek,
>
> Thanks for tackling this.
>
> On Jan 13, 2016, at 3:32 PM, Derek Schuff <dschuff at google.com>
wrote:
>
> 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.
>
>
> When we discussed with JF and Dan, we agreed that split it up was the best
> solution. The split could be a class specialization for instance. E.g., the
> main class would not run the scavenger, whereas the specialized class
would.
>
> Cheers,
> -Quentin
>
>
> 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/20160122/0c129934/attachment.html>

> On Jan 22, 2016, at 12:29 PM, Derek Schuff <dschuff at google.com>
wrote:
> 
> Here are 2 patches, which are independent of each other.
> 
> The first splits PrologEpilogInserter into 2 parts :
http://reviews.llvm.org/D16481 <http://reviews.llvm.org/D16481>
> After looking at the code I thought it made more sense for the major split
to include whether callee-saved register spills are supported. So for
non-virtual targets, virtual registers are not supported and scavenging is
optionally supported, and vice versa for virtual targets. The base case includes
just frame finalization, prolog/epilog code insertion and FrameIndex
elimination. The CSR-supporting case includes CSR spilling and optionally
scavenging.
> It's a little bit ugly because e.g. most of the target hooks (even
those used in the core pieces like FI elimination) take a pointer to a
RegScavenger object which could be null, and there's still a little bit of
code in the FI elimination code that takes CSR spilling into account. But I do
think it is an improvement, and I'd be interested in feedback. This patch
could be ready to land if people are happy with the design.
> 
> The other (http://reviews.llvm.org/D16483
<http://reviews.llvm.org/D16483> )is the aforementioned prototype for
requiring MachineFunctionPasses to opt-in to supporting virtual registers.
It's only done for WebAssembly and X86 so far as a proof of concept. The
interesting bit to look at is the way it's implemented (right now it's
just a virtual method that's called inside an assert which can be compiled
away) and the passes that will opt-in. It's mostly a concrete version of the
info I put in my previous post. Before it lands I'll have to update the rest
of the targets, and will probably manually expand the SUPPORTS_VIRTUAL_REGISTERS
macro which I used for my experimental convenience (unless you think it's
actually better that way).
Thanks for working on this.

In my opinion the important thing with the (not) supporting vregs in a pass was
that I would have liked to make it explicit if a target wants to use vregs after
regalloc. This way we can actually differentiate the cases where vregs appear
after register allocation because of a bug and the case where they are
intentional. The important thing would be to add something like
MachineRegisterInfo::setVirtRegsAfterRegalloc() and
MachineRegisterInfo::getVirtRegsAfterRegalloc(). Because I would assume that we
will find more examples like the following (from MachineBasicBlock):

  void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask = ~0u) {
    LiveIns.push_back(RegisterMaskPair(PhysReg, LaneMask));
  }

this needs to be changed to support VRegs. But if we do that change, I'd
like to change it to something like this:

  void addLiveIn(unsigned Reg, LaneBitmask LaneMask = ~0u) {
    assert(TargetRegisterInfo::isPhysReg(Reg) ||
getParent()->getRegInfo().getVirtRegsAfterRegalloc());
    LiveIns.push_back(RegisterMaskPair(Reg, LaneMask));
  }

The fact that a pass does or does not support virtual registers is in my opinion
not important enough to warrant adding an extra line to nearly every
MachineFunctionPass, simply adding an assert(MRI.getNumVirtRegs() == 0); into
runOnMachineFunction() for passes that do not support vregs would be enough IMO
but I remember that we were talking about the scheme presented in this pass so
correct me if I miss something.

- Matthias
> 
> Thanks for your help,
> -Derek
> 
> On Wed, Jan 13, 2016 at 3:40 PM Quentin Colombet <qcolombet at apple.com
<mailto:qcolombet at apple.com>> wrote:
> Hi Derek,
> 
> Thanks for tackling this.
> 
>> On Jan 13, 2016, at 3:32 PM, Derek Schuff <dschuff at google.com
<mailto:dschuff at google.com>> wrote:
>> 
>> 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.
> 
> When we discussed with JF and Dan, we agreed that split it up was the best
solution. The split could be a class specialization for instance. E.g., the main
class would not run the scavenger, whereas the specialized class would.
> 
> Cheers,
> -Quentin
> 
>> 
>> 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
<mailto: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 <mailto: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 <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/20160122/69d3d8de/attachment.html>

> On Jan 22, 2016, at 1:23 PM, Matthias Braun <mbraun at apple.com>
wrote:
> 
>> 
>> On Jan 22, 2016, at 12:29 PM, Derek Schuff <dschuff at google.com
<mailto:dschuff at google.com>> wrote:
>> 
>> Here are 2 patches, which are independent of each other.
>> 
>> The first splits PrologEpilogInserter into 2 parts :
http://reviews.llvm.org/D16481 <http://reviews.llvm.org/D16481>
>> After looking at the code I thought it made more sense for the major
split to include whether callee-saved register spills are supported. So for
non-virtual targets, virtual registers are not supported and scavenging is
optionally supported, and vice versa for virtual targets. The base case includes
just frame finalization, prolog/epilog code insertion and FrameIndex
elimination. The CSR-supporting case includes CSR spilling and optionally
scavenging.
>> It's a little bit ugly because e.g. most of the target hooks (even
those used in the core pieces like FI elimination) take a pointer to a
RegScavenger object which could be null, and there's still a little bit of
code in the FI elimination code that takes CSR spilling into account. But I do
think it is an improvement, and I'd be interested in feedback. This patch
could be ready to land if people are happy with the design.
>> 
>> The other (http://reviews.llvm.org/D16483
<http://reviews.llvm.org/D16483> )is the aforementioned prototype for
requiring MachineFunctionPasses to opt-in to supporting virtual registers.
It's only done for WebAssembly and X86 so far as a proof of concept. The
interesting bit to look at is the way it's implemented (right now it's
just a virtual method that's called inside an assert which can be compiled
away) and the passes that will opt-in. It's mostly a concrete version of the
info I put in my previous post. Before it lands I'll have to update the rest
of the targets, and will probably manually expand the SUPPORTS_VIRTUAL_REGISTERS
macro which I used for my experimental convenience (unless you think it's
actually better that way).
> Thanks for working on this.
> 
> In my opinion the important thing with the (not) supporting vregs in a pass
was that I would have liked to make it explicit if a target wants to use vregs
after regalloc.
> This way we can actually differentiate the cases where vregs appear after
register allocation because of a bug and the case where they are intentional.
The important thing would be to add something like
MachineRegisterInfo::setVirtRegsAfterRegalloc() and
MachineRegisterInfo::getVirtRegsAfterRegalloc(). Because I would assume that we
will find more examples like the following (from MachineBasicBlock):
> 
>   void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask = ~0u) {
>     LiveIns.push_back(RegisterMaskPair(PhysReg, LaneMask));
>   }
> 
> this needs to be changed to support VRegs. But if we do that change,
I'd like to change it to something like this:
> 
>   void addLiveIn(unsigned Reg, LaneBitmask LaneMask = ~0u) {
>     assert(TargetRegisterInfo::isPhysReg(Reg) ||
getParent()->getRegInfo().getVirtRegsAfterRegalloc());
>     LiveIns.push_back(RegisterMaskPair(Reg, LaneMask));
>   }
I haven’t looked at the patch, just commenting on that example. My understanding
was that supporting both virtual and physical registers should not have any
impact on anything else, but the pass itself. I.e., if the pass updates the
liveIns, in that example, it does that only for physical registers. I.e., we do
not push for changes like this.

What you’re suggesting below (an assert like mechanism) if sufficient IMHO.
> 
> The fact that a pass does or does not support virtual registers is in my
opinion not important enough to warrant adding an extra line to nearly every
MachineFunctionPass, simply adding an assert(MRI.getNumVirtRegs() == 0); into
runOnMachineFunction() for passes that do not support vregs would be enough IMO
but I remember that we were talking about the scheme presented in this pass so
correct me if I miss something.
I agree, but I don’t see how this is different from having one line in every
MachineFunctionPass :).

Cheers,
-Quentin
> 
> - Matthias
> 
>> 
>> Thanks for your help,
>> -Derek
>> 
>> On Wed, Jan 13, 2016 at 3:40 PM Quentin Colombet <qcolombet at
apple.com <mailto:qcolombet at apple.com>> wrote:
>> Hi Derek,
>> 
>> Thanks for tackling this.
>> 
>>> On Jan 13, 2016, at 3:32 PM, Derek Schuff <dschuff at google.com
<mailto:dschuff at google.com>> wrote:
>>> 
>>> 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.
>> 
>> When we discussed with JF and Dan, we agreed that split it up was the
best solution. The split could be a class specialization for instance. E.g., the
main class would not run the scavenger, whereas the specialized class would.
>> 
>> Cheers,
>> -Quentin
>> 
>>> 
>>> 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 <mailto: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 <mailto: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 <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/20160122/a45f6730/attachment-0001.html>