llvm dev - Dec 2015 - 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).

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

>-----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.  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.
>
>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

----- 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