llvm dev - Jun 2018 - [RFC][SVE] Supporting SIMD instruction sets with variable vector lengths

Hi Robin,

responses inline.

-Graham
> On 11 Jun 2018, at 16:47, Robin Kruppe <robin.kruppe at gmail.com>
wrote:
> 
> Hi Graham,
> Hi David,
> 
> glad to hear other people are thinking about RVV codegen!
> 
> On 7 June 2018 at 18:10, Graham Hunter <Graham.Hunter at arm.com>
wrote:
>> 
>> Hi,
>> 
>>> On 6 Jun 2018, at 17:36, David A. Greene <dag at cray.com>
wrote:
>>> 
>>> Graham Hunter via llvm-dev <llvm-dev at lists.llvm.org>
writes:
>>>>> Is there anything about vscale or a scalable vector that
requires a
>>>>> minimum bit width?  For example, is this legal?
>>>>> 
>>>>> <scalable 1 x double>
>>>>> 
>>>>> I know it won't map to an SVE type.  I'm simply
curious because
>>>>> traditionally Cray machines defined vectors in terms of
>>>>> machine-dependent "maxvl" with an element type,
so with the above vscale
>>>>> would == maxvl.  Not that we make any such things anymore. 
But maybe
>>>>> someone else does?
>>>> 
>>>> That's legal in IR, yes, and we believe it should be usable
to represent the vectors for
>>>> RISC-V's 'V' extension. The main problem there is
that they have a dynamic vector
>>>> length within the loop so that they can perform the last
iterations of a loop within vector
>>>> registers when there's less than a full register worth of
data remaining. SVE uses
>>>> predication (masking) to achieve the same effect.
> 
> 
> Yes, <scalable 1 x T> should be allowed in the IR type system (even
<1
> x T> is currently allowed and unlike the scalable variant that's not
> even useful) and it would be the sole legal vector types in the RISCV
> backend.
> 
>> 
>>>> For the 'V' extension, vscale would indeed correspond
to 'maxvl', and I'm hoping that a
>>>> 'setvl' intrinsic that provides a predicate will avoid
the need for modelling a change in
>>>> dynamic vector length -- reducing the vector length is
effectively equivalent to an implied
>>>> predicate on all operations. This avoids needing to add a token
operand to all existing
>>>> instructions that work on vector types.
> 
> Yes, vscale would be the *maximum* vector length (how many elements
> fit into each register), not the *active* vector length (how many
> elements are operated on in the current loop iteration).
> 
> This has nothing to do with tokens, though. The tokens I proposed were
> to encode the fact that even 'maxvl' varies on a function by
function
> basis. This RFC approaches the same issue differently, but it's still
> there -- in terms of this RFC, operations on scalable vectors depend
> on `vscale`, which is "not necessarily [constant] across
functions".
> That implies, for example, that an unmasked <scalable 4 x i32> load
or
> store (which accesses vscale * 16 bytes of memory) can't generally be
> moved from one function to another unless it's somehow ensured that
> both functions will have the same vscale. For that matter, the same
> restriction applies to calls to `vscale` itself.
> 
> The evolution of the active vector length is a separate problem and
> one that doesn't really impact the IR type system (nor one that can
> easily be solved by tokens).
Agreed.
> 
>>> 
>>> Right.  In that way the RISC V method is very much like what the
old
>>> Cray machines did with the Vector Length register.
>>> 
>>> So in LLVM IR you would have "setvl" return a predicate
and then apply
>>> that predicate to operations using the current select method?  How
does
>>> instruction selection map that back onto a simple setvl +
unpredicated
>>> vector instructions?
>>> 
>>> For conditional code both vector length and masking must be taken
into
>>> account.  If "setvl" returns a predicate then that
predicate would have
>>> to be combined in some way with the conditional predicate
(typically via
>>> an AND operation in an IR that directly supports predicates). 
Since
>>> LLVM IR doesn't have predicates _per_se_, would it turn into
nested
>>> selects or something?  Untangling that in instruction selection
seems
>>> difficult but perhaps I'm missing something.
>> 
>> My idea is for the RISC-V backend to recognize when a setvl intrinsic
has
>> been used, and replace the use of its value in AND operations with an
>> all-true value (with constant folding to remove unnecessary ANDs) then
>> replace any masked instructions (generally loads, stores, anything else
>> that might generate an exception or modify state that it shouldn't)
with
>> target-specific nodes that understand the dynamic vlen.
> 
> I am not quite so sure about turning the active vector length into
> just another mask. It's true that the effects on arithmetic, load,
> stores, etc. are the same as if everything executed under a mask like
> <1, 1, ..., 1, 0, 0, ..., 0> with the number of ones equal to the
> active vector length. However, actually materializing the masks in the
> IR means the RISCV backend has to reverse-engineer what it must do
> with the vl register for any given (masked or unmasked) vector
> operation. The stakes for that are rather high, because (1) it applies
> to pretty much every single vector operation ever, and (2) when it
> fails, the codegen impact is incredibly bad.
I can see where the concern comes from; we had problems reconstructing
semantics when experimenting with search loop vectorization and often
had to fall back on default (slow) generic cases.

My main reason for proposing this was to try and ensure that the size was
consistent from the point of view of the query functions we were discussing
in the main thread. If you're fine with all size queries assuming maxvl (so
things like stack slots would always use the current configured maximum
length), then I don't think there's a problem with dropping this part of
the
proposal and letting you find a better representation of active length.
> (1) The vl register affects not only loads, stores and other
> operations with side effects, but all vector instructions, even pure
> computation (and reg-reg moves, but that's not relevant for IR). An
> integer vector add, for example, only computes src1[i] + src2[i] for 0
> <= i < vl and the remaining elements of the destination register
(from
> vl upwards) are zeroed. This is very natural for strip-mined loops
> (you'll never need those elements), but it means an unmasked IR level
> vector add is a really bad fit for the RISC-V 'vadd' instruction.
> Unless the backend can prove that only the first vl elements of the
> result will ever be observed, it will have to temporarily set vl to
> MAXVL so that the RVV instruction will actually compute the
"full"
> result. Establishing that seems like it will require at least some
> custom data flow analysis, and it's unclear how robust it can be made.
> 
> (2) Failing to properly use vl for some vector operation is worse than
> e.g. materializing a mask you wouldn't otherwise need. It requires
> that too (if the operation is masked), but more importantly it needs
> to save vl, change it to MAXVL, and finally restore the old value.
> That's quite expensive: besides the ca. 3 extra instructions and the
> scratch GPR required, this save/restore dance can have other nasty
> effects depending on uarch style. I'd have to consult the hardware
> people to be sure, but from my understanding risks include pipeline
> stalls and expensive roundtrips between decoupled vector and scalar
> units.
Ah, I hadn't appreciated you might need to save/restore the VL like that.
I'd worked through a couple of small example loops and it seemed fine,
but hadn't looked at more complicated cases.
> To be clear: I have not yet experimented with any of this, so I'm not
> saying this is a deal breaker. A well-engineered "demanded
elements"
> analysis may very well be good enough in practice. But since we
> broached the subject, I wanted to mention this challenge. (I'm
> currently side stepping it by not using built-in vector instructions
> but instead intrinsics that treat vl as magic extra state.)
> 
>> This could be part of lowering, or maybe a separate IR pass, rather
than ISel.
>> I *think* this will work, but if someone can come up with some IR where
it
>> wouldn't work then please let me know (e.g. global-state-changing
instructions
>> that could move out of blocks where one setvl predicate is used and
into one
>> where another is used).
> 
> There are some operations that use vl for things other than simple
> masking. To give one example, "speculative" loads (which
silencing
> some exceptions to safely permit vectorization of some loops with
> data-dependent exits, such as strlen) can shrink vl as a side effect.
> I believe this can be handled by modelling all relevant operations
> (including setvl itself) as intrinsics that have side effects or
> read/write inaccessible memory. However, if you want to have the
> "current" vl (or equivalent mask) around as SSA value, you need
to
> "reload" it after any operation that updates vl. That seems like
it
> could get a bit complex if you want to do it efficiently (in the
> limit, it seems equivalent to SSA construction).
Ok; the fact that there's more instructions that can change vl and that you
might
need to reload it is useful to know.

SVE uses predication to achieve the same via the first-faulting/no-faulting
load instructions and the ffr register.

I think SVE having 16 predicate registers (vs. 8 for RVV and AVX-512) has led
to us using the feature quite widely with our own experiments; I'll try
looking for
non-predicated solutions as well when we try to expand scalable vectorization
capabilities.
>> Unfortunately, I can't find a description of the instructions
included in
>> the 'V' extension in the online manual (other than setvl or
configuring
>> registers), so I can't tell if there's something I'm
missing.
> 
> I'm very sorry for that, I know how frustrating it can be. I hope the
> above gives a clearer picture of the constraints involved. Exact
> instructions, let alone encodings, are still in flux as Bruce said.
Yes, the above information is definitely useful, even if I don't have a
complete
picture yet. Thanks.

Hi,

Just to clarify the part below about changing the proposal, this means that a
<scalable n x ty> vector:

* Has a size of vscale * sizeof(ty) when reasoning about sizes within llvm
* Potentially has a smaller size of active_vscale * sizeof(ty) depending on the
current
  processor state at runtime.

For SVE, active_vscale == vscale. For RVV (and potentially others), it can be
smaller based
on the VL state generated by setvl or similar.

-Graham


I am not quite so sure about turning the active vector length into
just another mask. It's true that the effects on arithmetic, load,
stores, etc. are the same as if everything executed under a mask like
<1, 1, ..., 1, 0, 0, ..., 0> with the number of ones equal to the
active vector length. However, actually materializing the masks in the
IR means the RISCV backend has to reverse-engineer what it must do
with the vl register for any given (masked or unmasked) vector
operation. The stakes for that are rather high, because (1) it applies
to pretty much every single vector operation ever, and (2) when it
fails, the codegen impact is incredibly bad.

I can see where the concern comes from; we had problems reconstructing
semantics when experimenting with search loop vectorization and often
had to fall back on default (slow) generic cases.

My main reason for proposing this was to try and ensure that the size was
consistent from the point of view of the query functions we were discussing
in the main thread. If you're fine with all size queries assuming maxvl (so
things like stack slots would always use the current configured maximum
length), then I don't think there's a problem with dropping this part of
the
proposal and letting you find a better representation of active length.

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180612/ebfd6c63/attachment-0001.html>

Oops, vscale * n * sizeof(ty).

:)


On 12 Jun 2018, at 18:18, Graham Hunter <Graham.Hunter at
arm.com<mailto:Graham.Hunter at arm.com>> wrote:

Hi,

Just to clarify the part below about changing the proposal, this means that a
<scalable n x ty> vector:

* Has a size of vscale * sizeof(ty) when reasoning about sizes within llvm
* Potentially has a smaller size of active_vscale * sizeof(ty) depending on the
current
  processor state at runtime.

For SVE, active_vscale == vscale. For RVV (and potentially others), it can be
smaller based
on the VL state generated by setvl or similar.

-Graham


I am not quite so sure about turning the active vector length into
just another mask. It's true that the effects on arithmetic, load,
stores, etc. are the same as if everything executed under a mask like
<1, 1, ..., 1, 0, 0, ..., 0> with the number of ones equal to the
active vector length. However, actually materializing the masks in the
IR means the RISCV backend has to reverse-engineer what it must do
with the vl register for any given (masked or unmasked) vector
operation. The stakes for that are rather high, because (1) it applies
to pretty much every single vector operation ever, and (2) when it
fails, the codegen impact is incredibly bad.

I can see where the concern comes from; we had problems reconstructing
semantics when experimenting with search loop vectorization and often
had to fall back on default (slow) generic cases.

My main reason for proposing this was to try and ensure that the size was
consistent from the point of view of the query functions we were discussing
in the main thread. If you're fine with all size queries assuming maxvl (so
things like stack slots would always use the current configured maximum
length), then I don't think there's a problem with dropping this part of
the
proposal and letting you find a better representation of active length.


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180612/047ffd7c/attachment.html>

On 12 June 2018 at 14:47, Graham Hunter <Graham.Hunter at arm.com>
wrote:
>
> Hi Robin,
>
> responses inline.
>
> -Graham
>
> > On 11 Jun 2018, at 16:47, Robin Kruppe <robin.kruppe at
gmail.com> wrote:
> >
> > Hi Graham,
> > Hi David,
> >
> > glad to hear other people are thinking about RVV codegen!
> >
> > On 7 June 2018 at 18:10, Graham Hunter <Graham.Hunter at
arm.com> wrote:
> >>
> >> Hi,
> >>
> >>> On 6 Jun 2018, at 17:36, David A. Greene <dag at
cray.com> wrote:
> >>>
> >>> Graham Hunter via llvm-dev <llvm-dev at lists.llvm.org>
writes:
> >>>>> Is there anything about vscale or a scalable vector
that requires a
> >>>>> minimum bit width?  For example, is this legal?
> >>>>>
> >>>>> <scalable 1 x double>
> >>>>>
> >>>>> I know it won't map to an SVE type.  I'm
simply curious because
> >>>>> traditionally Cray machines defined vectors in terms
of
> >>>>> machine-dependent "maxvl" with an element
type, so with the above vscale
> >>>>> would == maxvl.  Not that we make any such things
anymore.  But maybe
> >>>>> someone else does?
> >>>>
> >>>> That's legal in IR, yes, and we believe it should be
usable to represent the vectors for
> >>>> RISC-V's 'V' extension. The main problem there
is that they have a dynamic vector
> >>>> length within the loop so that they can perform the last
iterations of a loop within vector
> >>>> registers when there's less than a full register worth
of data remaining. SVE uses
> >>>> predication (masking) to achieve the same effect.
> >
> >
> > Yes, <scalable 1 x T> should be allowed in the IR type system
(even <1
> > x T> is currently allowed and unlike the scalable variant
that's not
> > even useful) and it would be the sole legal vector types in the RISCV
> > backend.
> >
> >>
> >>>> For the 'V' extension, vscale would indeed
correspond to 'maxvl', and I'm hoping that a
> >>>> 'setvl' intrinsic that provides a predicate will
avoid the need for modelling a change in
> >>>> dynamic vector length -- reducing the vector length is
effectively equivalent to an implied
> >>>> predicate on all operations. This avoids needing to add a
token operand to all existing
> >>>> instructions that work on vector types.
> >
> > Yes, vscale would be the *maximum* vector length (how many elements
> > fit into each register), not the *active* vector length (how many
> > elements are operated on in the current loop iteration).
> >
> > This has nothing to do with tokens, though. The tokens I proposed were
> > to encode the fact that even 'maxvl' varies on a function by
function
> > basis. This RFC approaches the same issue differently, but it's
still
> > there -- in terms of this RFC, operations on scalable vectors depend
> > on `vscale`, which is "not necessarily [constant] across
functions".
> > That implies, for example, that an unmasked <scalable 4 x i32>
load or
> > store (which accesses vscale * 16 bytes of memory) can't generally
be
> > moved from one function to another unless it's somehow ensured
that
> > both functions will have the same vscale. For that matter, the same
> > restriction applies to calls to `vscale` itself.
> >
> > The evolution of the active vector length is a separate problem and
> > one that doesn't really impact the IR type system (nor one that
can
> > easily be solved by tokens).
>
> Agreed.
>
> >
> >>>
> >>> Right.  In that way the RISC V method is very much like what
the old
> >>> Cray machines did with the Vector Length register.
> >>>
> >>> So in LLVM IR you would have "setvl" return a
predicate and then apply
> >>> that predicate to operations using the current select method? 
How does
> >>> instruction selection map that back onto a simple setvl +
unpredicated
> >>> vector instructions?
> >>>
> >>> For conditional code both vector length and masking must be
taken into
> >>> account.  If "setvl" returns a predicate then that
predicate would have
> >>> to be combined in some way with the conditional predicate
(typically via
> >>> an AND operation in an IR that directly supports predicates). 
Since
> >>> LLVM IR doesn't have predicates _per_se_, would it turn
into nested
> >>> selects or something?  Untangling that in instruction
selection seems
> >>> difficult but perhaps I'm missing something.
> >>
> >> My idea is for the RISC-V backend to recognize when a setvl
intrinsic has
> >> been used, and replace the use of its value in AND operations with
an
> >> all-true value (with constant folding to remove unnecessary ANDs)
then
> >> replace any masked instructions (generally loads, stores, anything
else
> >> that might generate an exception or modify state that it
shouldn't) with
> >> target-specific nodes that understand the dynamic vlen.
> >
> > I am not quite so sure about turning the active vector length into
> > just another mask. It's true that the effects on arithmetic, load,
> > stores, etc. are the same as if everything executed under a mask like
> > <1, 1, ..., 1, 0, 0, ..., 0> with the number of ones equal to
the
> > active vector length. However, actually materializing the masks in the
> > IR means the RISCV backend has to reverse-engineer what it must do
> > with the vl register for any given (masked or unmasked) vector
> > operation. The stakes for that are rather high, because (1) it applies
> > to pretty much every single vector operation ever, and (2) when it
> > fails, the codegen impact is incredibly bad.
>
> I can see where the concern comes from; we had problems reconstructing
> semantics when experimenting with search loop vectorization and often
> had to fall back on default (slow) generic cases.
>
> My main reason for proposing this was to try and ensure that the size was
> consistent from the point of view of the query functions we were discussing
> in the main thread. If you're fine with all size queries assuming maxvl
(so
> things like stack slots would always use the current configured maximum
> length), then I don't think there's a problem with dropping this
part of the
> proposal and letting you find a better representation of active length.
Oh yeah, sure. The size of a vector is in terms of vscale, even from
the perspective of the RISC-V ISA. The active vector length just
modifies *operations* to produce partially-zero results and access
less memory. It's also perfectly reasonable to "mix" vectors
computed
with different active vector lengths. For example, it might be useful
to create a loop-invariant vector in full before the loop and keep
using it in the loop body with varying vl. Add to that IR design
considerations and it's clear-cut to me that scalable vectors should
have *one* size and all operations should produce "full-width" (but
maybe partially-zeroed) vector results.

Partly for that reason (and also out of general hesitation to commit
to *any* model at this stage) I am lukewarm to the "active_vscale"
concept you outlined in a later email.

So, agreed, let's completely leave that part out for now. I'll come
back with specific proposals when the RVV work has matured and we have
more experience with this issue.
> > (1) The vl register affects not only loads, stores and other
> > operations with side effects, but all vector instructions, even pure
> > computation (and reg-reg moves, but that's not relevant for IR).
An
> > integer vector add, for example, only computes src1[i] + src2[i] for 0
> > <= i < vl and the remaining elements of the destination register
(from
> > vl upwards) are zeroed. This is very natural for strip-mined loops
> > (you'll never need those elements), but it means an unmasked IR
level
> > vector add is a really bad fit for the RISC-V 'vadd'
instruction.
> > Unless the backend can prove that only the first vl elements of the
> > result will ever be observed, it will have to temporarily set vl to
> > MAXVL so that the RVV instruction will actually compute the
"full"
> > result. Establishing that seems like it will require at least some
> > custom data flow analysis, and it's unclear how robust it can be
made.
> >
> > (2) Failing to properly use vl for some vector operation is worse than
> > e.g. materializing a mask you wouldn't otherwise need. It requires
> > that too (if the operation is masked), but more importantly it needs
> > to save vl, change it to MAXVL, and finally restore the old value.
> > That's quite expensive: besides the ca. 3 extra instructions and
the
> > scratch GPR required, this save/restore dance can have other nasty
> > effects depending on uarch style. I'd have to consult the hardware
> > people to be sure, but from my understanding risks include pipeline
> > stalls and expensive roundtrips between decoupled vector and scalar
> > units.
>
> Ah, I hadn't appreciated you might need to save/restore the VL like
that.
> I'd worked through a couple of small example loops and it seemed fine,
> but hadn't looked at more complicated cases.
>
> > To be clear: I have not yet experimented with any of this, so I'm
not
> > saying this is a deal breaker. A well-engineered "demanded
elements"
> > analysis may very well be good enough in practice. But since we
> > broached the subject, I wanted to mention this challenge. (I'm
> > currently side stepping it by not using built-in vector instructions
> > but instead intrinsics that treat vl as magic extra state.)
> >
> >> This could be part of lowering, or maybe a separate IR pass,
rather than ISel.
> >> I *think* this will work, but if someone can come up with some IR
where it
> >> wouldn't work then please let me know (e.g.
global-state-changing instructions
> >> that could move out of blocks where one setvl predicate is used
and into one
> >> where another is used).
> >
> > There are some operations that use vl for things other than simple
> > masking. To give one example, "speculative" loads (which
silencing
> > some exceptions to safely permit vectorization of some loops with
> > data-dependent exits, such as strlen) can shrink vl as a side effect.
> > I believe this can be handled by modelling all relevant operations
> > (including setvl itself) as intrinsics that have side effects or
> > read/write inaccessible memory. However, if you want to have the
> > "current" vl (or equivalent mask) around as SSA value, you
need to
> > "reload" it after any operation that updates vl. That seems
like it
> > could get a bit complex if you want to do it efficiently (in the
> > limit, it seems equivalent to SSA construction).
>
> Ok; the fact that there's more instructions that can change vl and that
you might
> need to reload it is useful to know.
>
> SVE uses predication to achieve the same via the first-faulting/no-faulting
> load instructions and the ffr register.
>
> I think SVE having 16 predicate registers (vs. 8 for RVV and AVX-512) has
led
> to us using the feature quite widely with our own experiments; I'll try
looking for
> non-predicated solutions as well when we try to expand scalable
vectorization
> capabilities.
>
> >> Unfortunately, I can't find a description of the instructions
included in
> >> the 'V' extension in the online manual (other than setvl
or configuring
> >> registers), so I can't tell if there's something I'm
missing.
> >
> > I'm very sorry for that, I know how frustrating it can be. I hope
the
> > above gives a clearer picture of the constraints involved. Exact
> > instructions, let alone encodings, are still in flux as Bruce said.
>
> Yes, the above information is definitely useful, even if I don't have a
complete
> picture yet. Thanks.