[llvm-dev] Allowing virtual registers after register allocation

[Derek Schuff via llvm-dev]

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>