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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
23 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [RFC][SVE] Supporting SIMD instruction sets with variable vector lengths

Tim Northover via llvm-dev
Oops, vscale * n * sizeof(ty).

:)


On 12 Jun 2018, at 18:18, Graham Hunter <[hidden email]> 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.



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [RFC][SVE] Supporting SIMD instruction sets with variable vector lengths

Tim Northover via llvm-dev
In reply to this post by Tim Northover via llvm-dev
Hi David,

Responses below.

-Graham

On 11 Jun 2018, at 22:19, David A. Greene <[hidden email]> wrote:

Graham Hunter <[hidden email]> writes:

========
1. Types
========

To represent a vector of unknown length a boolean `Scalable` property has been
added to the `VectorType` class, which indicates that the number of elements in
the vector is a runtime-determined integer multiple of the `NumElements` field.
Most code that deals with vectors doesn't need to know the exact length, but
does need to know relative lengths -- e.g. get a vector with the same number of
elements but a different element type, or with half or double the number of
elements.

In order to allow code to transparently support scalable vectors, we introduce
an `ElementCount` class with two members:

- `unsigned Min`: the minimum number of elements.
- `bool Scalable`: is the element count an unknown multiple of `Min`?

For non-scalable vectors (``Scalable=false``) the scale is considered to be
equal to one and thus `Min` represents the exact number of elements in the
vector.

The intent for code working with vectors is to use convenience methods and avoid
directly dealing with the number of elements. If needed, calling
`getElementCount` on a vector type instead of `getVectorNumElements` can be used
to obtain the (potentially scalable) number of elements. Overloaded division and
multiplication operators allow an ElementCount instance to be used in much the
same manner as an integer for most cases.

This mixture of compile-time and runtime quantities allow us to reason about the
relationship between different scalable vector types without knowing their
exact length.

How does this work in practice?  Let's say I populate a vector with a
splat.  Presumably, that gives me a "full length" vector.  Let's say the
type is <scalable 2 x double>.  How do I split the vector and get
something half the width?  What is its type?  How do I split it again
and get something a quarter of the width?  What is its type?  How do I
use half- and quarter-width vectors?  Must I resort to predication?

To split a <scalable 2 x double> in half, you'd use a shufflevector in much the
same way you would for fixed-length vector types.

e.g.
``
  %sv = call <scalable 1 x i32> @llvm.experimental.vector.stepvector.nxv1i32()
  %halfvec = shufflevector <scalable 2 x double> %fullvec, <scalable 2 x double> undef, <scalable 1 x i32> %sv
``

You can't split it any further than a <scalable 1 x <ty>>, since there may only be
one element in the actual hardware vector at runtime. The same restriction applies to
a <1 x <ty>>. This is why we have a minimum number of lanes in addition to the
scalable flag so that we can concatenate and split vectors, since SVE registers have
the same number of bytes and will therefore decrease the number of elements per
register as the element type increases in size.

If you want to extract something other than the first part of a vector, you need to add
offsets based on a calculation from vscale (e.g. adding vscale * (min_elts/2) allows you
to reach the high half of a larger register).

If you check the patch which introduces splatvector (https://reviews.llvm.org/D47775),
you can see a line which currently produces an error if changing the size of a vector
is required, and notes that VECTOR_SHUFFLE_VAR hasn't been implemented yet.

In our downstream compiler, this is an ISD alongside VECTOR_SHUFFLE which
allows a shuffle with a variable mask instead of a constant.

If people feel it would be useful, I can prepare another patch which implements these
shuffles (as an intrinsic rather than a common ISD) for review now instead of later;
I tried to keep the initial patch set small so didn't cover all cases.

In terms of using predication, that's generally not required for the legal integer types;
normal promotion via sign or zero extension work. We've tried to reuse existing
mechanisms wherever possible.

For floating point types, we do use predication to allow the use of otherwise illegal
types like <scalable 1 x double>, but that's limited to the AArch64 backend and does
not need to be represented in IR.


Ths split question comes into play for backward compatibility.  How
would one take a scalable vector and pass it into a NEON library?  It is
likely that some math functions, for example, will not have SVE versions
available.

I don't believe we intend to support this, but instead provide libraries with
SVE versions of functions instead. The problem is that you don't know how
many NEON-size subvectors exist within an SVE vector at compile time.
While you could create a loop with 'vscale' number of iterations and try to
extract those subvectors, I suspect the IR would end up being quite messy
and potentially hard to recognize and optimize.

The other problem with calling non-SVE functions is that any live SVE
registers must be spilled to the stack and filled after the call, which is
likely to be quite expensive.

Is there a way to represent "double width" vectors?  In mixed-data-size
loops it is sometimes convenient to reason about double-width vectors
rather than having to split them (to legalize for the target
architecture) and keep track of their parts early on.  I guess the more
fundamental question is about how such loops should be handled.

For SVE, it's fine to generate IR with types that are 'double size' or larger,
and just leave it to legalization at SelectionDAG level to split into multiple
legal size registers.

Again, if people would like me to create a patch to illustrate legalization sooner
rather than later to help understand what's needed to support these types, let
me know.


What do insertelement and extractelement mean for scalable vectors?
Your examples showed insertelement at index zero.  How would I, say,
insertelement into the upper half of the vector?  Or any arbitrary
place?  Does insertelement at index 10 of a <scalable 2 x double> work,
assuming vscale is large enough?  It is sometimes useful to constitute a
vector out of various scalar pieces and insertelement is a convenient
way to do it.

So you can insert or extract any element known to exist (in other words, it's
within the minimum number of elements). Using a constant index outside
that range will fail, as we won't know whether the element actually exists
until we're running on a cpu.

Our downstream compiler supports inserting and extracting arbitrary elements
from calculated offsets as part of our experiment on search loop vectorization,
but that generates the offsets based on a count of true bits within partitioned
predicates. I was planning on proposing new intrinsics to improve predicate use
within llvm at a later date.

We have been able to implement various types of known shuffles (like the high/low
half extract, zip, concatention, etc) with vscale, stepvector, and the existing IR
instructions.



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [RFC][SVE] Supporting SIMD instruction sets with variable vector lengths

Tim Northover via llvm-dev
Graham Hunter via llvm-dev <[hidden email]> writes:

> To split a <scalable 2 x double> in half, you'd use a shufflevector in much the
> same way you would for fixed-length vector types.
>
> e.g.
> ``
> %sv = call <scalable 1 x i32> @llvm.experimental.vector.stepvector.nxv1i32()
> %halfvec = shufflevector <scalable 2 x double> %fullvec, <scalable 2 x double> undef, <scalable 1 x i32> %sv
> ``
>
> You can't split it any further than a <scalable 1 x <ty>>, since there may only be
> one element in the actual hardware vector at runtime. The same restriction applies to
> a <1 x <ty>>. This is why we have a minimum number of lanes in addition to the
> scalable flag so that we can concatenate and split vectors, since SVE registers have
> the same number of bytes and will therefore decrease the number of elements per
> register as the element type increases in size.

Right.  So let's say the hardware width is 1024.  If I have a
<scalable 2 x double> it is 1024 bits.  If I split it, it's a
<scalable 1 x double> (right?) with 512 bits.  There is no
way to create a 256-bit vector.

It's probably the case that for pure VL-agnostic code, this is ok.  Our
experience with the X1/X2, which also supported VL-agnostic code, was
that at times compiler awareness of the hardware MAXVL allowed us to
generate better code, better enough that we "cheated" regularly.  The
hardware guys loved us.  :)

I'm not at all saying that's a good idea for SVE, just recounting
experience and wondering what the implications would be for SVE and more
generally, LLVM IR.  Would the MIPS V people be interested in a
non-VL-agnostic compilation mode?

> If you want to extract something other than the first part of a vector, you need to add
> offsets based on a calculation from vscale (e.g. adding vscale * (min_elts/2) allows you
> to reach the high half of a larger register).

Sure, that makes semse.

> For floating point types, we do use predication to allow the use of otherwise illegal
> types like <scalable 1 x double>, but that's limited to the AArch64 backend and does
> not need to be represented in IR.

This is something done during or after isel?

>  Ths split question comes into play for backward compatibility. How
>  would one take a scalable vector and pass it into a NEON library? It is
>  likely that some math functions, for example, will not have SVE versions
>  available.
>
> I don't believe we intend to support this, but instead provide libraries with
> SVE versions of functions instead. The problem is that you don't know how
> many NEON-size subvectors exist within an SVE vector at compile time.
> While you could create a loop with 'vscale' number of iterations and try to
> extract those subvectors, I suspect the IR would end up being quite messy
> and potentially hard to recognize and optimize.

Yes, that was my concern.  The vscale loop is what I came up with as
well.  It is technically feasible, but ugly.  I'm a little concerned
about what vendors will do with this.  Not everyone is going to have the
resources to convert all of their NEON libraries, certainly not all at
once.

Just something to think about.

> The other problem with calling non-SVE functions is that any live SVE
> registers must be spilled to the stack and filled after the call, which is
> likely to be quite expensive.

Understood.

>  Is there a way to represent "double width" vectors? In mixed-data-size
>  loops it is sometimes convenient to reason about double-width vectors
>  rather than having to split them (to legalize for the target
>  architecture) and keep track of their parts early on. I guess the more
>  fundamental question is about how such loops should be handled.
>
> For SVE, it's fine to generate IR with types that are 'double size' or larger,
> and just leave it to legalization at SelectionDAG level to split into multiple
> legal size registers.

Ok, great.  If something is larger than "double size," how can it be
split, given the "split once" restriction above?

>  What do insertelement and extractelement mean for scalable vectors?
>  Your examples showed insertelement at index zero. How would I, say,
>  insertelement into the upper half of the vector? Or any arbitrary
>  place? Does insertelement at index 10 of a <scalable 2 x double> work,
>  assuming vscale is large enough? It is sometimes useful to constitute a
>  vector out of various scalar pieces and insertelement is a convenient
>  way to do it.
>
> So you can insert or extract any element known to exist (in other words, it's
> within the minimum number of elements). Using a constant index outside
> that range will fail, as we won't know whether the element actually exists
> until we're running on a cpu.

In that case to "insert" into the higher elements one would insert into
the known range and then shufflevector, I suppose.  Ok.

> Our downstream compiler supports inserting and extracting arbitrary elements
> from calculated offsets as part of our experiment on search loop vectorization,
> but that generates the offsets based on a count of true bits within partitioned
> predicates. I was planning on proposing new intrinsics to improve predicate use
> within llvm at a later date.

Ok, I look forward to seeing them!

> We have been able to implement various types of known shuffles (like the high/low
> half extract, zip, concatention, etc) with vscale, stepvector, and the existing IR
> instructions.

Yes, I can certainly see how all of those would be implemented.  The
main case I'm thinking about is something that is "scalarized" within a
vector loop context.  I'm wondering about the best way to reconstitute a
vector from scalar pieces (or vice-versa).

Thanks for the explanations!

                          -David

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
12