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

> On Dec 9, 2015, at 4:13 PM, Quentin Colombet <qcolombet at apple.com>
wrote:
> 
> Hi,
> 
> I would actually go the other direction, i.e., stick to physical registers
but with an infinite number.
> The rational is that after register allocation we broke all the nice
properties of the pre-alloc virtual registers. For instance, the existing
liveness algorithm cannot be used on those virtual registers. On the other hand,
all the infrastructure we have in place for physical registers would be suited.
(modulo supporting a dynamic number of physical registers)
> 
> Cheers,
> Q.
>  
>> On Dec 9, 2015, at 4:04 PM, Derek Schuff via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>> 
>> 
>> 
>> On Wed, Dec 9, 2015 at 3:02 PM Hal Finkel <hfinkel at anl.gov
<mailto:hfinkel at anl.gov>> wrote:
>> ----- Original Message -----
>> > From: "Derek Schuff via llvm-dev" <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>
>> > To: llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>
>> > Sent: Wednesday, December 9, 2015 4:31:31 PM
>> > Subject: [llvm-dev] Allowing virtual registers after register
allocation
>> >
>> >
>> > Hi all,
>> > Virtual ISAs such as WebAssembly and NVPTX use infinite virtual
>> > register sets instead of traditional phsyical registers.
>> > PrologEpilogInserter is run after register allocation and asserts
>> > that all virtuals have been allocated but doesn't otherwise
depend
>> > on this if scavenging is not needed. We'd like to use the
>> > target-independent PEI code for WebAssembly, so we're
proposing a
>> > TargetRegisterInfo hook for targets to indicate that they use
>> > virtual registers in this way (currently called
>> > usesVirtualRegstersAfterRegAlloc(), other suggestions welcome).
The
>> > code is at http://reviews.llvm.org/D15394
<http://reviews.llvm.org/D15394> and an example of the
>> > intended use for WebAssembly is at http://reviews.llvm.org/D15344
<http://reviews.llvm.org/D15344> .
>> >
>> 
>> I think this makes sense, and generally speaking, I think it will be
good for us to have better support for VM targets without fixed-sized register
sets.
>> 
>> Bikeshedding: usesVirtualRegstersAfterRegAlloc() - Are you actually
"allocating" virtual registers, or just using the ones that the
infrastructure already provides?
>> 
>> Not exactly; the actual register allocation does nothing (i.e. 
WebAssemblyPassConfig::createTargetRegisterAllocator() returns nullptr) and we
just use the regular infrastructure virtual registers. However we do run a
custom register coloring pass which reduces the total number of virtual
registers used.
>>  
>> Is the answer the same for the NVPTX backend?
>> 
>> Yes (at least, they have a null TargetRegisterAllocator too).
>>  
>> Maybe something like: targetLacksPhysicalRegissters() would be better?
>> 
>> Maybe. We actually do have "physical" registers called SP and
FP (returned by TargetRegisterInfo::getFrameRegister() and used by some default
ISel lowerings and by FrameIndex elimination) but of course they aren't
really physical registers either.
>> 
>>  
>> _______________________________________________
>> 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/20151209/5703af3d/attachment.html>

----- Original Message -----
> From: "Quentin Colombet" <qcolombet at apple.com>
> To: "Derek Schuff" <dschuff at google.com>
> Cc: "Hal Finkel" <hfinkel at anl.gov>, llvm-dev at
lists.llvm.org
> Sent: Wednesday, December 9, 2015 6:14:33 PM
> Subject: Re: [llvm-dev] Allowing virtual registers after register
allocation
> 
> 
> On Dec 9, 2015, at 4:13 PM, Quentin Colombet < qcolombet at apple.com
>
> wrote:
> 
> 
> Hi,
> 
> 
> I would actually go the other direction, i.e., stick to physical
> registers but with an infinite number.
> The rational is that after register allocation we broke all the nice
> properties of the pre-alloc virtual registers. For instance, the
> existing liveness algorithm cannot be used on those virtual
> registers.
Why? Is this just related to the fact that we've dropped them out of SSA
form?
> On the other hand, all the infrastructure we have in
> place for physical registers would be suited.
> 
> 
> (modulo supporting a dynamic number of physical registers)
> 
But there is lots of code that assumes that it can iterate over all physical
registers in some class. My thought had been that you don't want to
introduce infinite physical register sets because this assumption of
enumerability is broken (as is the assumption that the size does not dynamically
change). Thoughts?

 -Hal
> Cheers,
> Q.
> 
> On Dec 9, 2015, at 4:04 PM, Derek Schuff via llvm-dev <
> llvm-dev at lists.llvm.org > wrote:
> 
> 
> On Wed, Dec 9, 2015 at 3:02 PM Hal Finkel < hfinkel at anl.gov >
wrote:
> 
> 
> ----- Original Message -----
> > From: "Derek Schuff via llvm-dev" < llvm-dev at
lists.llvm.org >
> > To: llvm-dev at lists.llvm.org
> > Sent: Wednesday, December 9, 2015 4:31:31 PM
> > Subject: [llvm-dev] Allowing virtual registers after register
> > allocation
> > 
> > 
> > Hi all,
> > Virtual ISAs such as WebAssembly and NVPTX use infinite virtual
> > register sets instead of traditional phsyical registers.
> > PrologEpilogInserter is run after register allocation and asserts
> > that all virtuals have been allocated but doesn't otherwise depend
> > on this if scavenging is not needed. We'd like to use the
> > target-independent PEI code for WebAssembly, so we're proposing a
> > TargetRegisterInfo hook for targets to indicate that they use
> > virtual registers in this way (currently called
> > usesVirtualRegstersAfterRegAlloc(), other suggestions welcome). The
> > code is at http://reviews.llvm.org/D15394 and an example of the
> > intended use for WebAssembly is at http://reviews.llvm.org/D15344 .
> > 
> 
> I think this makes sense, and generally speaking, I think it will be
> good for us to have better support for VM targets without
> fixed-sized register sets.
> 
> Bikeshedding: usesVirtualRegstersAfterRegAlloc() - Are you actually
> "allocating" virtual registers, or just using the ones that the
> infrastructure already provides?
> 
> 
> Not exactly; the actual register allocation does nothing (i.e.
> WebAssemblyPassConfig::createTargetRegisterAllocator() returns
> nullptr) and we just use the regular infrastructure virtual
> registers. However we do run a custom register coloring pass which
> reduces the total number of virtual registers used.
> 
> 
> Is the answer the same for the NVPTX backend?
> 
> 
> Yes (at least, they have a null TargetRegisterAllocator too).
> 
> 
> Maybe something like: targetLacksPhysicalRegissters() would be
> better?
> 
> 
> 
> Maybe. We actually do have "physical" registers called SP and FP
> (returned by TargetRegisterInfo::getFrameRegister() and used by some
> default ISel lowerings and by FrameIndex elimination) but of course
> they aren't really physical registers either.
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On 12/10/2015 11:39 AM, Hal Finkel via llvm-dev wrote:
>
> But there is lots of code that assumes that it can iterate over all
physical registers in some class. My thought had been that you don't want to
introduce infinite physical register sets because this assumption of
enumerability is broken (as is the assumption that the size does not dynamically
change). Thoughts?
The post-RA code may not be free from assumptions that all virtual 
registers are gone.  For example, such code may not handle subregisters, 
since PhysReg:Sub can always be collapsed to another physical register. 
  For virtual registers, there is no such guarantee.

I think it would be a lot clearer if we introduced infinite register 
classes, with all the properties of physical registers (except those 
obviously related to finiteness).  Having virtual registers after RA 
sounds like a huge hack.

-Krzysztof

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

> On Dec 10, 2015, at 9:39 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> 
> 
> ----- Original Message -----
>> From: "Quentin Colombet" <qcolombet at apple.com>
>> To: "Derek Schuff" <dschuff at google.com>
>> Cc: "Hal Finkel" <hfinkel at anl.gov>, llvm-dev at
lists.llvm.org
>> Sent: Wednesday, December 9, 2015 6:14:33 PM
>> Subject: Re: [llvm-dev] Allowing virtual registers after register
allocation
>> 
>> 
>> On Dec 9, 2015, at 4:13 PM, Quentin Colombet < qcolombet at
apple.com >
>> wrote:
>> 
>> 
>> Hi,
>> 
>> 
>> I would actually go the other direction, i.e., stick to physical
>> registers but with an infinite number.
>> The rational is that after register allocation we broke all the nice
>> properties of the pre-alloc virtual registers. For instance, the
>> existing liveness algorithm cannot be used on those virtual
>> registers.
> 
> Why? Is this just related to the fact that we've dropped them out of
SSA form?
The rough answer is yes.
The more precise answer is that virtual registers are supported out of SSA form,
but if you want to use the liveness infrastructure for them (I mean the
LiveInterval class and such), you need to maintain the SSA form behind the scene
with the VNIs and other related objects. This is usually complicated and error
prone. Moreover recomputing that information from scratch in the out of SSA form
is not supported and is basically the same as reconstructing SSA (+implict def
and fun for sub registers) and that does not seem worth to me.
> 
>> On the other hand, all the infrastructure we have in
>> place for physical registers would be suited.
>> 
>> 
>> (modulo supporting a dynamic number of physical registers)
>> 
> 
> But there is lots of code that assumes that it can iterate over all
physical registers in some class. My thought had been that you don't want to
introduce infinite physical register sets because this assumption of
enumerability is broken (as is the assumption that the size does not dynamically
change). Thoughts?
That is a good point and I imagine that the solution of such problems depends on
what the related algorithms are trying to do.
My thought for enumeration, but again may not be applicable for every cases, was
that we stick to the number of physical registers we currently need. The fact
that the set is infinite means that you can make it grow as much as you need,
but at a given time it has a finite size.

Honestly, I think that we could get the proper answer only when we see the
actual problems.
Moreover, if we want to stick to virtual registers, what is the point in trying
to run post-RA passes anyway?

In other words, do we actually have to go in either directions: support
“infinite” phys reg or add virtual reg support in post-RA passes?

I am tempted to think no, we don’t, but I don’t know the use cases.
What post-RA passes with want to run with virtual regs?

Cheers,
-Quentin
> 
> -Hal
> 
>> Cheers,
>> Q.
>> 
>> On Dec 9, 2015, at 4:04 PM, Derek Schuff via llvm-dev <
>> llvm-dev at lists.llvm.org > wrote:
>> 
>> 
>> On Wed, Dec 9, 2015 at 3:02 PM Hal Finkel < hfinkel at anl.gov >
wrote:
>> 
>> 
>> ----- Original Message -----
>>> From: "Derek Schuff via llvm-dev" < llvm-dev at
lists.llvm.org >
>>> To: llvm-dev at lists.llvm.org
>>> Sent: Wednesday, December 9, 2015 4:31:31 PM
>>> Subject: [llvm-dev] Allowing virtual registers after register
>>> allocation
>>> 
>>> 
>>> Hi all,
>>> Virtual ISAs such as WebAssembly and NVPTX use infinite virtual
>>> register sets instead of traditional phsyical registers.
>>> PrologEpilogInserter is run after register allocation and asserts
>>> that all virtuals have been allocated but doesn't otherwise
depend
>>> on this if scavenging is not needed. We'd like to use the
>>> target-independent PEI code for WebAssembly, so we're proposing
a
>>> TargetRegisterInfo hook for targets to indicate that they use
>>> virtual registers in this way (currently called
>>> usesVirtualRegstersAfterRegAlloc(), other suggestions welcome). The
>>> code is at http://reviews.llvm.org/D15394 and an example of the
>>> intended use for WebAssembly is at http://reviews.llvm.org/D15344 .
>>> 
>> 
>> I think this makes sense, and generally speaking, I think it will be
>> good for us to have better support for VM targets without
>> fixed-sized register sets.
>> 
>> Bikeshedding: usesVirtualRegstersAfterRegAlloc() - Are you actually
>> "allocating" virtual registers, or just using the ones that
the
>> infrastructure already provides?
>> 
>> 
>> Not exactly; the actual register allocation does nothing (i.e.
>> WebAssemblyPassConfig::createTargetRegisterAllocator() returns
>> nullptr) and we just use the regular infrastructure virtual
>> registers. However we do run a custom register coloring pass which
>> reduces the total number of virtual registers used.
>> 
>> 
>> Is the answer the same for the NVPTX backend?
>> 
>> 
>> Yes (at least, they have a null TargetRegisterAllocator too).
>> 
>> 
>> Maybe something like: targetLacksPhysicalRegissters() would be
>> better?
>> 
>> 
>> 
>> Maybe. We actually do have "physical" registers called SP and
FP
>> (returned by TargetRegisterInfo::getFrameRegister() and used by some
>> default ISel lowerings and by FrameIndex elimination) but of course
>> they aren't really physical registers either.
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> 
>> 
>> 
> 
> -- 
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151210/134abb65/attachment.html>