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

----- Original Message -----
> From: "Kevin B Smith" <kevin.b.smith at intel.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Krzysztof Parzyszek" <kparzysz at codeaurora.org>,
llvm-dev at lists.llvm.org
> Sent: Thursday, December 10, 2015 2:32:36 PM
> Subject: RE: [llvm-dev] Allowing virtual registers after register
allocation
> 
> >-----Original Message-----
> >From: Hal Finkel [mailto:hfinkel at anl.gov]
> >Sent: Thursday, December 10, 2015 12:11 PM
> >To: Smith, Kevin B <kevin.b.smith at intel.com>
> >Cc: Krzysztof Parzyszek <kparzysz at codeaurora.org>; llvm-
> >dev at lists.llvm.org
> >Subject: Re: [llvm-dev] Allowing virtual registers after register
> >allocation
> >
> >----- Original Message -----
> >> From: "Kevin B via llvm-dev Smith" <llvm-dev at
lists.llvm.org>
> >> To: "Krzysztof Parzyszek" <kparzysz at
codeaurora.org>, llvm-
> >dev at lists.llvm.org
> >> Sent: Thursday, December 10, 2015 12:04:49 PM
> >> Subject: Re: [llvm-dev] Allowing virtual registers after register
> >> allocation
> >>
> >> >-----Original Message-----
> >> >From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On
Behalf
> >> >Of
> >> >Krzysztof Parzyszek via llvm-dev
> >> >Sent: Thursday, December 10, 2015 9:47 AM
> >> >To: llvm-dev at lists.llvm.org
> >> >Subject: Re: [llvm-dev] Allowing virtual registers after
register
> >> >allocation
> >> >
> >> >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.
> >>
> >> I definitely agree that having virtual regs after RA sounds like a
> >> hack.
> >>
> >> But I also don't know why it would be desirable to introduce
> >> infinite
> >> register classes. The WebAsm folks are already saying that they
> >> would like to do register allocation to target a fixed/limited
> >> number (might be large though) of "virtual registers". 
So,
> >> instead
> >> of calling these virtual registers, why not call them physical
> >> registers, and have a fixed number of them, that corresponds to
> >> the
> >> number that is desired to allocate to.  Or, you could have the
> >> number of registers to use be run-time selectable in some manner
> >> by
> >> just having the physical register set be larger than is ever
> >> planned
> >> to be used by that particular CG, and having run-time controls to
> >> restrict the set of allocatable physical registers.
> >
> >You're right that we don't really want infinite register
classes,
> >but rather, we
> >want "expandable" ones. Making extra-large register classes
that are
> >restricted by having most of the registers in the reserved set,
> >however,
> >seems just as much a hack (and a worse one in many ways).
> 
> 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.

 -Hal
> 
> >
> >I'd certainly not object to some kind of dynamically-sized
> >"physical" register
> >class concept.
> >
> > -Hal
> >
> >>
> >> Kevin Smith
> >>
> >> >
> >> >-Krzysztof
> >> >
> >> >--
> >> >Qualcomm Innovation Center, Inc. is a member of Code Aurora
> >> >Forum,
> >> >hosted by The Linux Foundation
> >> >_______________________________________________
> >> >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
> >>
> >
> >--
> >Hal Finkel
> >Assistant Computational Scientist
> >Leadership Computing Facility
> >Argonne National Laboratory
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On Thu, Dec 10, 2015 at 3:38 PM, Hal Finkel via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> > >You're right that we don't really want infinite register
classes,
> > >but rather, we
> > >want "expandable" ones. Making extra-large register
classes that are
> > >restricted by having most of the registers in the reserved set,
> > >however,
> > >seems just as much a hack (and a worse one in many ways).
> >
> > 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.
>
A relatively-small fixed number is indeed not acceptable. We have a virtual
ISA which is general-purpose and is not inherently afraid of having
thousands of registers and perhaps more, if that's what the program
actually needs. We do use coloring to reduce the number as we can, but
coloring can't always fix everything without spilling.

And whether we ever have LLVM spill, as opposed to just using more
registers, is a decision we'd like to make based on the needs of the
platform, not based on any limitations of LLVM. Right now, the working
assumption is that LLVM should not spill.

>
> > 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.
>
The virtual register infrastructure in LLVM turns out to be a very close
fit for our needs. The main alternative is effectively to take LLVM's
physical register concept and evolve it in the direction of being more like
its virtual register concept in several significant ways. It's not clear
that LLVM should really want two different concepts with so much
similarity, but also numerous subtle differences.

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

>
> > 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151210/53b6c6ff/attachment.html>

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