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

In the RISC-V V extension, there is no upper limit to the size vector
registers can be in a future CPU. (Formally, the upper limit is at
least 2^31 bytes)

Generic code can enquire the size, dynamically allocate space, and
transparently save and restore the contents of a vector register or
registers.

On Fri, May 24, 2019 at 11:28 AM JinGu Kang via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>
> Hi Graham,
>
> I am working on a custom target and it is considering scalable vector type
representation in programming language. While I am collecting the information
about it, I have met your RFC. I have a question. I think the one of fundamental
issues is that we do not know the memory layout of the type at compile time. I
am not sure whether the RFC covers this issue or not. Conservatively, I imagined
the memory layout of biggest type which the scalable vector type can support. I
could miss some discussions about it. If I missed something, please let me know.
>
> Thanks,
> JinGu Kang
>
> ________________________________
> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of
Graham Hunter via llvm-dev <llvm-dev at lists.llvm.org>
> Sent: 05 June 2018 14:15
> To: Chris Lattner; Hal Finkel; Jones, Joel; dag at cray.com; Renato Golin;
Kristof Beyls; Amara Emerson; Florian Hahn; Sander De Smalen; Robin Kruppe;
llvm-dev at lists.llvm.org; mkuper at google.com; Sjoerd Meijer; Sam Parker
> Cc: nd
> Subject: [llvm-dev] [RFC][SVE] Supporting SIMD instruction sets with
variable vector lengths
>
> Hi,
>
> Now that Sander has committed enough MC support for SVE, here's an
updated
> RFC for variable length vector support with a set of 14 patches (listed at
the end)
> to demonstrate code generation for SVE using the extensions proposed in the
RFC.
>
> I have some ideas about how to support RISC-V's upcoming extension
alongside
> SVE; I'll send an email with some additional comments on Robin's
RFC later.
>
> Feedback and questions welcome.
>
> -Graham
>
> ============================================================> Supporting
SIMD instruction sets with variable vector lengths
> ============================================================>
> In this RFC we propose extending LLVM IR to support code-generation for
variable
> length vector architectures like Arm's SVE or RISC-V's 'V'
extension. Our
> approach is backwards compatible and should be as non-intrusive as
possible; the
> only change needed in other backends is how size is queried on vector
types, and
> it only requires a change in which function is called. We have created a
set of
> proof-of-concept patches to represent a simple vectorized loop in IR and
> generate SVE instructions from that IR. These patches (listed in section 7
of
> this rfc) can be found on Phabricator and are intended to illustrate the
scope
> of changes required by the general approach described in this RFC.
>
> =========> Background
> =========>
> *ARMv8-A Scalable Vector Extensions* (SVE) is a new vector ISA extension
for
> AArch64 which is intended to scale with hardware such that the same binary
> running on a processor with longer vector registers can take advantage of
the
> increased compute power without recompilation.
>
> As the vector length is no longer a compile-time known value, the way in
which
> the LLVM vectorizer generates code requires modifications such that certain
> values are now runtime evaluated expressions instead of compile-time
constants.
>
> Documentation for SVE can be found at
>
https://developer.arm.com/docs/ddi0584/latest/arm-architecture-reference-manual-supplement-the-scalable-vector-extension-sve-for-armv8-a
>
> =======> Contents
> =======>
> The rest of this RFC covers the following topics:
>
> 1. Types -- a proposal to extend VectorType to be able to represent vectors
that
>    have a length which is a runtime-determined multiple of a known base
length.
>
> 2. Size Queries - how to reason about the size of types for which the size
isn't
>    fully known at compile time.
>
> 3. Representing the runtime multiple of vector length in IR for use in
address
>    calculations and induction variable comparisons.
>
> 4. Generating 'constant' values in IR for vectors with a
runtime-determined
>    number of elements.
>
> 5. A brief note on code generation of these new operations for AArch64.
>
> 6. An example of C code and matching IR using the proposed extensions.
>
> 7. A list of patches demonstrating the changes required to emit SVE
instructions
>    for a loop that has already been vectorized using the extensions
described
>    in this RFC.
>
> =======> 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.
>
> The runtime multiple is not expected to change during program execution for
SVE,
> but it is possible. The model of scalable vectors presented in this RFC
assumes
> that the multiple will be constant within a function but not necessarily
across
> functions. As suggested in the recent RISC-V rfc, a new function attribute
to
> inherit the multiple across function calls will allow for function calls
with
> vector arguments/return values and inlining/outlining optimizations.
>
> IR Textual Form
> ---------------
>
> The textual form for a scalable vector is:
>
> ``<scalable <n> x <type>>``
>
> where `type` is the scalar type of each element, `n` is the minimum number
of
> elements, and the string literal `scalable` indicates that the total number
of
> elements is an unknown multiple of `n`; `scalable` is just an arbitrary
choice
> for indicating that the vector is scalable, and could be substituted by
another.
> For fixed-length vectors, the `scalable` is omitted, so there is no change
in
> the format for existing vectors.
>
> Scalable vectors with the same `Min` value have the same number of
elements, and
> the same number of bytes if `Min * sizeof(type)` is the same (assuming they
are
> used within the same function):
>
> ``<scalable 4 x i32>`` and ``<scalable 4 x i8>`` have the same
number of
>   elements.
>
> ``<scalable x 4 x i32>`` and ``<scalable x 8 x i16>`` have the
same number of
>   bytes.
>
> IR Bitcode Form
> ---------------
>
> To serialize scalable vectors to bitcode, a new boolean field is added to
the
> type record. If the field is not present the type will default to a
fixed-length
> vector type, preserving backwards compatibility.
>
> Alternatives Considered
> -----------------------
>
> We did consider one main alternative -- a dedicated target type, like the
> x86_mmx type.
>
> A dedicated target type would either need to extend all existing passes
that
> work with vectors to recognize the new type, or to duplicate all that code
> in order to get reasonable code generation and autovectorization.
>
> This hasn't been done for the x86_mmx type, and so it is only capable
of
> providing support for C-level intrinsics instead of being used and
recognized by
> passes inside llvm.
>
> Although our current solution will need to change some of the code that
creates
> new VectorTypes, much of that code doesn't need to care about whether
the types
> are scalable or not -- they can use preexisting methods like
> `getHalfElementsVectorType`. If the code is a little more complex,
> `ElementCount` structs can be used instead of an `unsigned` value to
represent
> the number of elements.
>
> ==============> 2. Size Queries
> ==============>
> This is a proposal for how to deal with querying the size of scalable
types.
> While it has not been implemented in full, the general approach works well
> for calculating offsets into structures with scalable types in a modified
> version of ComputeValueVTs in our downstream compiler.
>
> Current IR types that have a known size all return a single integer
constant.
> For scalable types a second integer is needed to indicate the number of
bytes
> which need to be scaled by the runtime multiple to obtain the actual
length.
>
> For primitive types, getPrimitiveSizeInBits will function as it does today,
> except that it will no longer return a size for vector types (it will
return 0,
> as it does for other derived types). The majority of calls to this function
are
> already for scalar rather than vector types.
>
> For derived types, a function (getSizeExpressionInBits) to return a pair of
> integers (one to indicate unscaled bits, the other for bits that need to be
> scaled by the runtime multiple) will be added. For backends that do not
need to
> deal with scalable types, another function (getFixedSizeExpressionInBits)
that
> only returns unscaled bits will be provided, with a debug assert that the
type
> isn't scalable.
>
> Similar functionality will be added to DataLayout.
>
> Comparing two of these sizes together is straightforward if only unscaled
sizes
> are used. Comparisons between scaled sizes is also simple when comparing
sizes
> within a function (or across functions with the inherit flag mentioned in
the
> changes to the type), but cannot be compared otherwise. If a mix is
present,
> then any number of unscaled bits will not be considered to have a greater
size
> than a smaller number of scaled bits, but a smaller number of unscaled bits
> will be considered to have a smaller size than a greater number of scaled
bits
> (since the runtime multiple is at least one).
>
> Future Work
> -----------
>
> Since we cannot determine the exact size of a scalable vector, the
> existing logic for alias detection won't work when multiple accesses
> share a common base pointer with different offsets.
>
> However, SVE's predication will mean that a dynamic 'safe'
vector length
> can be determined at runtime, so after initial support has been added we
> can work on vectorizing loops using runtime predication to avoid aliasing
> problems.
>
> Alternatives Considered
> -----------------------
>
> Marking scalable vectors as unsized doesn't work well, as many parts of
> llvm dealing with loads and stores assert that 'isSized()' returns
true
> and make use of the size when calculating offsets.
>
> We have considered introducing multiple helper functions instead of
> using direct size queries, but that doesn't cover all cases. It may
> still be a good idea to introduce them to make the purpose in a given
> case more obvious, e.g. 'isBitCastableTo(Type*,Type*)'.
>
> =======================================> 3. Representing Vector Length
at Runtime
> =======================================>
> With a scalable vector type defined, we now need a way to represent the
runtime
> length in IR in order to generate addresses for consecutive vectors in
memory
> and determine how many elements have been processed in an iteration of a
loop.
>
> We have added an experimental `vscale` intrinsic to represent the runtime
> multiple. Multiplying the result of this intrinsic by the minimum number of
> elements in a vector gives the total number of elements in a scalable
vector.
>
> Fixed-Length Code
> -----------------
>
> Assuming a vector type of <4 x <ty>>
> ``
> vector.body:
>   %index = phi i64 [ %index.next, %vector.body ], [ 0,
%vector.body.preheader ]
>   ;; <loop body>
>   ;; Increment induction var
>   %index.next = add i64 %index, 4
>   ;; <check and branch>
> ``
> Scalable Equivalent
> -------------------
>
> Assuming a vector type of <scalable 4 x <ty>>
> ``
> vector.body:
>   %index = phi i64 [ %index.next, %vector.body ], [ 0,
%vector.body.preheader ]
>   ;; <loop body>
>   ;; Increment induction var
>   %vscale64 = call i64 @llvm.experimental.vector.vscale.64()
>   %index.next = add i64 %index, mul (i64 %vscale64, i64 4)
>   ;; <check and branch>
> ``
> ==========================> 4. Generating Vector Values
> ==========================> For constant vector values, we cannot
specify all the elements as we can for
> fixed-length vectors; fortunately only a small number of easily synthesized
> patterns are required for autovectorization. The `zeroinitializer` constant
> can be used in the same manner as fixed-length vectors for a constant zero
> splat. This can then be combined with `insertelement` and `shufflevector`
> to create arbitrary value splats in the same manner as fixed-length
vectors.
>
> For constants consisting of a sequence of values, an experimental
`stepvector`
> intrinsic has been added to represent a simple constant of the form
> `<0, 1, 2... num_elems-1>`. To change the starting value a splat of
the new
> start can be added, and changing the step requires multiplying by a splat.
>
> Fixed-Length Code
> -----------------
> ``
>   ;; Splat a value
>   %insert = insertelement <4 x i32> undef, i32 %value, i32 0
>   %splat = shufflevector <4 x i32> %insert, <4 x i32> undef,
<4 x i32> zeroinitializer
>   ;; Add a constant sequence
>   %add = add <4 x i32> %splat, <i32 2, i32 4, i32 6, i32 8>
> ``
> Scalable Equivalent
> -------------------
> ``
>   ;; Splat a value
>   %insert = insertelement <scalable 4 x i32> undef, i32 %value, i32 0
>   %splat = shufflevector <scalable 4 x i32> %insert, <scalable 4 x
i32> undef, <scalable 4 x i32> zeroinitializer
>   ;; Splat offset + stride (the same in this case)
>   %insert2 = insertelement <scalable 4 x i32> under, i32 2, i32 0
>   %str_off = shufflevector <scalable 4 x i32> %insert2, <scalable
4 x i32> undef, <scalable 4 x i32> zeroinitializer
>   ;; Create sequence for scalable vector
>   %stepvector = call <scalable 4 x i32>
@llvm.experimental.vector.stepvector.nxv4i32()
>   %mulbystride = mul <scalable 4 x i32> %stepvector, %str_off
>   %addoffset = add <scalable 4 x i32> %mulbystride, %str_off
>   ;; Add the runtime-generated sequence
>   %add = add <scalable 4 x i32> %splat, %addoffset
> ``
> Future Work
> -----------
>
> Intrinsics cannot currently be used for constant folding. Our downstream
> compiler (using Constants instead of intrinsics) relies quite heavily on
this
> for good code generation, so we will need to find new ways to recognize and
> fold these values.
>
> =================> 5. Code Generation
> =================>
> IR splats will be converted to an experimental splatvector intrinsic in
> SelectionDAGBuilder.
>
> All three intrinsics are custom lowered and legalized in the AArch64
backend.
>
> Two new AArch64ISD nodes have been added to represent the same concepts
> at the SelectionDAG level, while splatvector maps onto the existing
> AArch64ISD::DUP.
>
> GlobalISel
> ----------
>
> Since GlobalISel was enabled by default on AArch64, it was necessary to add
> scalable vector support to the LowLevelType implementation. A single bit
was
> added to the raw_data representation for vectors and vectors of pointers.
>
> In addition, types that only exist in destination patterns are planted in
> the enumeration of available types for generated code. While this may not
be
> necessary in future, generating an all-true 'ptrue' value was
necessary to
> convert a predicated instruction into an unpredicated one.
>
> =========> 6. Example
> =========>
> The following example shows a simple C loop which assigns the array index
to
> the array elements matching that index. The IR shows how vscale and
stepvector
> are used to create the needed values and to advance the index variable in
the
> loop.
>
> C Code
> ------
>
> ``
> void IdentityArrayInit(int *a, int count) {
>   for (int i = 0; i < count; ++i)
>     a[i] = i;
> }
> ``
>
> Scalable IR Vector Body
> -----------------------
>
> ``
> vector.body.preheader:
>   ;; Other setup
>   ;; Stepvector used to create initial identity vector
>   %stepvector = call <scalable 4 x i32>
@llvm.experimental.vector.stepvector.nxv4i32()
>   br vector.body
>
> vector.body
>   %index = phi i64 [ %index.next, %vector.body ], [ 0,
%vector.body.preheader ]
>   %0 = phi i64 [ %1, %vector.body ], [ 0, %vector.body.preheader ]
>
>            ;; stepvector used for index identity on entry to loop body ;;
>   %vec.ind7 = phi <scalable 4 x i32> [ %step.add8, %vector.body ],
>                                      [ %stepvector, %vector.body.preheader
]
>   %vscale64 = call i64 @llvm.experimental.vector.vscale.64()
>   %vscale32 = trunc i64 %vscale64 to i32
>   %1 = add i64 %0, mul (i64 %vscale64, i64 4)
>
>            ;; vscale splat used to increment identity vector ;;
>   %insert = insertelement <scalable 4 x i32> undef, i32 mul (i32
%vscale32, i32 4), i32 0
>   %splat shufflevector <scalable 4 x i32> %insert, <scalable 4 x
i32> undef, <scalable 4 x i32> zeroinitializer
>   %step.add8 = add <scalable 4 x i32> %vec.ind7, %splat
>   %2 = getelementptr inbounds i32, i32* %a, i64 %0
>   %3 = bitcast i32* %2 to <scalable 4 x i32>*
>   store <scalable 4 x i32> %vec.ind7, <scalable 4 x i32>* %3,
align 4
>
>            ;; vscale used to increment loop index
>   %index.next = add i64 %index, mul (i64 %vscale64, i64 4)
>   %4 = icmp eq i64 %index.next, %n.vec
>   br i1 %4, label %middle.block, label %vector.body, !llvm.loop !5
> ``
>
> =========> 7. Patches
> =========>
> List of patches:
>
> 1. Extend VectorType: https://reviews.llvm.org/D32530
> 2. Vector element type Tablegen constraint: https://reviews.llvm.org/D47768
> 3. LLT support for scalable vectors: https://reviews.llvm.org/D47769
> 4. EVT strings and Type mapping: https://reviews.llvm.org/D47770
> 5. SVE Calling Convention: https://reviews.llvm.org/D47771
> 6. Intrinsic lowering cleanup: https://reviews.llvm.org/D47772
> 7. Add VScale intrinsic: https://reviews.llvm.org/D47773
> 8. Add StepVector intrinsic: https://reviews.llvm.org/D47774
> 9. Add SplatVector intrinsic: https://reviews.llvm.org/D47775
> 10. Initial store patterns: https://reviews.llvm.org/D47776
> 11. Initial addition patterns: https://reviews.llvm.org/D47777
> 12. Initial left-shift patterns: https://reviews.llvm.org/D47778
> 13. Implement copy logic for Z regs: https://reviews.llvm.org/D47779
> 14. Prevectorized loop unit test: https://reviews.llvm.org/D47780
>
> _______________________________________________
> 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
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Hi Bruce,

Thanks for your comment.
> Generic code can enquire the size, dynamically allocate space, and
transparently save and restore the contents of a vector register or
registers.

I am not sure what the Generic code is. It seems it uses similar way as the
implementation of variable length array. If so, I think it could be one way to
support it.

Thanks,
JinGu Kang

________________________________
From: Bruce Hoult <brucehoult at sifive.com>
Sent: 24 May 2019 20:12
To: JinGu Kang
Cc: Chris Lattner; Hal Finkel; Jones, Joel; dag at cray.com; Renato Golin;
Kristof Beyls; Amara Emerson; Florian Hahn; Sander De Smalen; Robin Kruppe;
llvm-dev at lists.llvm.org; mkuper at google.com; Sjoerd Meijer; Sam Parker;
Graham Hunter; nd
Subject: Re: [llvm-dev] [RFC][SVE] Supporting SIMD instruction sets with
variable vector lengths

In the RISC-V V extension, there is no upper limit to the size vector
registers can be in a future CPU. (Formally, the upper limit is at
least 2^31 bytes)

Generic code can enquire the size, dynamically allocate space, and
transparently save and restore the contents of a vector register or
registers.

On Fri, May 24, 2019 at 11:28 AM JinGu Kang via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>
> Hi Graham,
>
> I am working on a custom target and it is considering scalable vector type
representation in programming language. While I am collecting the information
about it, I have met your RFC. I have a question. I think the one of fundamental
issues is that we do not know the memory layout of the type at compile time. I
am not sure whether the RFC covers this issue or not. Conservatively, I imagined
the memory layout of biggest type which the scalable vector type can support. I
could miss some discussions about it. If I missed something, please let me know.
>
> Thanks,
> JinGu Kang
>
> ________________________________
> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of
Graham Hunter via llvm-dev <llvm-dev at lists.llvm.org>
> Sent: 05 June 2018 14:15
> To: Chris Lattner; Hal Finkel; Jones, Joel; dag at cray.com; Renato Golin;
Kristof Beyls; Amara Emerson; Florian Hahn; Sander De Smalen; Robin Kruppe;
llvm-dev at lists.llvm.org; mkuper at google.com; Sjoerd Meijer; Sam Parker
> Cc: nd
> Subject: [llvm-dev] [RFC][SVE] Supporting SIMD instruction sets with
variable vector lengths
>
> Hi,
>
> Now that Sander has committed enough MC support for SVE, here's an
updated
> RFC for variable length vector support with a set of 14 patches (listed at
the end)
> to demonstrate code generation for SVE using the extensions proposed in the
RFC.
>
> I have some ideas about how to support RISC-V's upcoming extension
alongside
> SVE; I'll send an email with some additional comments on Robin's
RFC later.
>
> Feedback and questions welcome.
>
> -Graham
>
> ============================================================> Supporting
SIMD instruction sets with variable vector lengths
> ============================================================>
> In this RFC we propose extending LLVM IR to support code-generation for
variable
> length vector architectures like Arm's SVE or RISC-V's 'V'
extension. Our
> approach is backwards compatible and should be as non-intrusive as
possible; the
> only change needed in other backends is how size is queried on vector
types, and
> it only requires a change in which function is called. We have created a
set of
> proof-of-concept patches to represent a simple vectorized loop in IR and
> generate SVE instructions from that IR. These patches (listed in section 7
of
> this rfc) can be found on Phabricator and are intended to illustrate the
scope
> of changes required by the general approach described in this RFC.
>
> =========> Background
> =========>
> *ARMv8-A Scalable Vector Extensions* (SVE) is a new vector ISA extension
for
> AArch64 which is intended to scale with hardware such that the same binary
> running on a processor with longer vector registers can take advantage of
the
> increased compute power without recompilation.
>
> As the vector length is no longer a compile-time known value, the way in
which
> the LLVM vectorizer generates code requires modifications such that certain
> values are now runtime evaluated expressions instead of compile-time
constants.
>
> Documentation for SVE can be found at
>
https://developer.arm.com/docs/ddi0584/latest/arm-architecture-reference-manual-supplement-the-scalable-vector-extension-sve-for-armv8-a
>
> =======> Contents
> =======>
> The rest of this RFC covers the following topics:
>
> 1. Types -- a proposal to extend VectorType to be able to represent vectors
that
>    have a length which is a runtime-determined multiple of a known base
length.
>
> 2. Size Queries - how to reason about the size of types for which the size
isn't
>    fully known at compile time.
>
> 3. Representing the runtime multiple of vector length in IR for use in
address
>    calculations and induction variable comparisons.
>
> 4. Generating 'constant' values in IR for vectors with a
runtime-determined
>    number of elements.
>
> 5. A brief note on code generation of these new operations for AArch64.
>
> 6. An example of C code and matching IR using the proposed extensions.
>
> 7. A list of patches demonstrating the changes required to emit SVE
instructions
>    for a loop that has already been vectorized using the extensions
described
>    in this RFC.
>
> =======> 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.
>
> The runtime multiple is not expected to change during program execution for
SVE,
> but it is possible. The model of scalable vectors presented in this RFC
assumes
> that the multiple will be constant within a function but not necessarily
across
> functions. As suggested in the recent RISC-V rfc, a new function attribute
to
> inherit the multiple across function calls will allow for function calls
with
> vector arguments/return values and inlining/outlining optimizations.
>
> IR Textual Form
> ---------------
>
> The textual form for a scalable vector is:
>
> ``<scalable <n> x <type>>``
>
> where `type` is the scalar type of each element, `n` is the minimum number
of
> elements, and the string literal `scalable` indicates that the total number
of
> elements is an unknown multiple of `n`; `scalable` is just an arbitrary
choice
> for indicating that the vector is scalable, and could be substituted by
another.
> For fixed-length vectors, the `scalable` is omitted, so there is no change
in
> the format for existing vectors.
>
> Scalable vectors with the same `Min` value have the same number of
elements, and
> the same number of bytes if `Min * sizeof(type)` is the same (assuming they
are
> used within the same function):
>
> ``<scalable 4 x i32>`` and ``<scalable 4 x i8>`` have the same
number of
>   elements.
>
> ``<scalable x 4 x i32>`` and ``<scalable x 8 x i16>`` have the
same number of
>   bytes.
>
> IR Bitcode Form
> ---------------
>
> To serialize scalable vectors to bitcode, a new boolean field is added to
the
> type record. If the field is not present the type will default to a
fixed-length
> vector type, preserving backwards compatibility.
>
> Alternatives Considered
> -----------------------
>
> We did consider one main alternative -- a dedicated target type, like the
> x86_mmx type.
>
> A dedicated target type would either need to extend all existing passes
that
> work with vectors to recognize the new type, or to duplicate all that code
> in order to get reasonable code generation and autovectorization.
>
> This hasn't been done for the x86_mmx type, and so it is only capable
of
> providing support for C-level intrinsics instead of being used and
recognized by
> passes inside llvm.
>
> Although our current solution will need to change some of the code that
creates
> new VectorTypes, much of that code doesn't need to care about whether
the types
> are scalable or not -- they can use preexisting methods like
> `getHalfElementsVectorType`. If the code is a little more complex,
> `ElementCount` structs can be used instead of an `unsigned` value to
represent
> the number of elements.
>
> ==============> 2. Size Queries
> ==============>
> This is a proposal for how to deal with querying the size of scalable
types.
> While it has not been implemented in full, the general approach works well
> for calculating offsets into structures with scalable types in a modified
> version of ComputeValueVTs in our downstream compiler.
>
> Current IR types that have a known size all return a single integer
constant.
> For scalable types a second integer is needed to indicate the number of
bytes
> which need to be scaled by the runtime multiple to obtain the actual
length.
>
> For primitive types, getPrimitiveSizeInBits will function as it does today,
> except that it will no longer return a size for vector types (it will
return 0,
> as it does for other derived types). The majority of calls to this function
are
> already for scalar rather than vector types.
>
> For derived types, a function (getSizeExpressionInBits) to return a pair of
> integers (one to indicate unscaled bits, the other for bits that need to be
> scaled by the runtime multiple) will be added. For backends that do not
need to
> deal with scalable types, another function (getFixedSizeExpressionInBits)
that
> only returns unscaled bits will be provided, with a debug assert that the
type
> isn't scalable.
>
> Similar functionality will be added to DataLayout.
>
> Comparing two of these sizes together is straightforward if only unscaled
sizes
> are used. Comparisons between scaled sizes is also simple when comparing
sizes
> within a function (or across functions with the inherit flag mentioned in
the
> changes to the type), but cannot be compared otherwise. If a mix is
present,
> then any number of unscaled bits will not be considered to have a greater
size
> than a smaller number of scaled bits, but a smaller number of unscaled bits
> will be considered to have a smaller size than a greater number of scaled
bits
> (since the runtime multiple is at least one).
>
> Future Work
> -----------
>
> Since we cannot determine the exact size of a scalable vector, the
> existing logic for alias detection won't work when multiple accesses
> share a common base pointer with different offsets.
>
> However, SVE's predication will mean that a dynamic 'safe'
vector length
> can be determined at runtime, so after initial support has been added we
> can work on vectorizing loops using runtime predication to avoid aliasing
> problems.
>
> Alternatives Considered
> -----------------------
>
> Marking scalable vectors as unsized doesn't work well, as many parts of
> llvm dealing with loads and stores assert that 'isSized()' returns
true
> and make use of the size when calculating offsets.
>
> We have considered introducing multiple helper functions instead of
> using direct size queries, but that doesn't cover all cases. It may
> still be a good idea to introduce them to make the purpose in a given
> case more obvious, e.g. 'isBitCastableTo(Type*,Type*)'.
>
> =======================================> 3. Representing Vector Length
at Runtime
> =======================================>
> With a scalable vector type defined, we now need a way to represent the
runtime
> length in IR in order to generate addresses for consecutive vectors in
memory
> and determine how many elements have been processed in an iteration of a
loop.
>
> We have added an experimental `vscale` intrinsic to represent the runtime
> multiple. Multiplying the result of this intrinsic by the minimum number of
> elements in a vector gives the total number of elements in a scalable
vector.
>
> Fixed-Length Code
> -----------------
>
> Assuming a vector type of <4 x <ty>>
> ``
> vector.body:
>   %index = phi i64 [ %index.next, %vector.body ], [ 0,
%vector.body.preheader ]
>   ;; <loop body>
>   ;; Increment induction var
>   %index.next = add i64 %index, 4
>   ;; <check and branch>
> ``
> Scalable Equivalent
> -------------------
>
> Assuming a vector type of <scalable 4 x <ty>>
> ``
> vector.body:
>   %index = phi i64 [ %index.next, %vector.body ], [ 0,
%vector.body.preheader ]
>   ;; <loop body>
>   ;; Increment induction var
>   %vscale64 = call i64 @llvm.experimental.vector.vscale.64()
>   %index.next = add i64 %index, mul (i64 %vscale64, i64 4)
>   ;; <check and branch>
> ``
> ==========================> 4. Generating Vector Values
> ==========================> For constant vector values, we cannot
specify all the elements as we can for
> fixed-length vectors; fortunately only a small number of easily synthesized
> patterns are required for autovectorization. The `zeroinitializer` constant
> can be used in the same manner as fixed-length vectors for a constant zero
> splat. This can then be combined with `insertelement` and `shufflevector`
> to create arbitrary value splats in the same manner as fixed-length
vectors.
>
> For constants consisting of a sequence of values, an experimental
`stepvector`
> intrinsic has been added to represent a simple constant of the form
> `<0, 1, 2... num_elems-1>`. To change the starting value a splat of
the new
> start can be added, and changing the step requires multiplying by a splat.
>
> Fixed-Length Code
> -----------------
> ``
>   ;; Splat a value
>   %insert = insertelement <4 x i32> undef, i32 %value, i32 0
>   %splat = shufflevector <4 x i32> %insert, <4 x i32> undef,
<4 x i32> zeroinitializer
>   ;; Add a constant sequence
>   %add = add <4 x i32> %splat, <i32 2, i32 4, i32 6, i32 8>
> ``
> Scalable Equivalent
> -------------------
> ``
>   ;; Splat a value
>   %insert = insertelement <scalable 4 x i32> undef, i32 %value, i32 0
>   %splat = shufflevector <scalable 4 x i32> %insert, <scalable 4 x
i32> undef, <scalable 4 x i32> zeroinitializer
>   ;; Splat offset + stride (the same in this case)
>   %insert2 = insertelement <scalable 4 x i32> under, i32 2, i32 0
>   %str_off = shufflevector <scalable 4 x i32> %insert2, <scalable
4 x i32> undef, <scalable 4 x i32> zeroinitializer
>   ;; Create sequence for scalable vector
>   %stepvector = call <scalable 4 x i32>
@llvm.experimental.vector.stepvector.nxv4i32()
>   %mulbystride = mul <scalable 4 x i32> %stepvector, %str_off
>   %addoffset = add <scalable 4 x i32> %mulbystride, %str_off
>   ;; Add the runtime-generated sequence
>   %add = add <scalable 4 x i32> %splat, %addoffset
> ``
> Future Work
> -----------
>
> Intrinsics cannot currently be used for constant folding. Our downstream
> compiler (using Constants instead of intrinsics) relies quite heavily on
this
> for good code generation, so we will need to find new ways to recognize and
> fold these values.
>
> =================> 5. Code Generation
> =================>
> IR splats will be converted to an experimental splatvector intrinsic in
> SelectionDAGBuilder.
>
> All three intrinsics are custom lowered and legalized in the AArch64
backend.
>
> Two new AArch64ISD nodes have been added to represent the same concepts
> at the SelectionDAG level, while splatvector maps onto the existing
> AArch64ISD::DUP.
>
> GlobalISel
> ----------
>
> Since GlobalISel was enabled by default on AArch64, it was necessary to add
> scalable vector support to the LowLevelType implementation. A single bit
was
> added to the raw_data representation for vectors and vectors of pointers.
>
> In addition, types that only exist in destination patterns are planted in
> the enumeration of available types for generated code. While this may not
be
> necessary in future, generating an all-true 'ptrue' value was
necessary to
> convert a predicated instruction into an unpredicated one.
>
> =========> 6. Example
> =========>
> The following example shows a simple C loop which assigns the array index
to
> the array elements matching that index. The IR shows how vscale and
stepvector
> are used to create the needed values and to advance the index variable in
the
> loop.
>
> C Code
> ------
>
> ``
> void IdentityArrayInit(int *a, int count) {
>   for (int i = 0; i < count; ++i)
>     a[i] = i;
> }
> ``
>
> Scalable IR Vector Body
> -----------------------
>
> ``
> vector.body.preheader:
>   ;; Other setup
>   ;; Stepvector used to create initial identity vector
>   %stepvector = call <scalable 4 x i32>
@llvm.experimental.vector.stepvector.nxv4i32()
>   br vector.body
>
> vector.body
>   %index = phi i64 [ %index.next, %vector.body ], [ 0,
%vector.body.preheader ]
>   %0 = phi i64 [ %1, %vector.body ], [ 0, %vector.body.preheader ]
>
>            ;; stepvector used for index identity on entry to loop body ;;
>   %vec.ind7 = phi <scalable 4 x i32> [ %step.add8, %vector.body ],
>                                      [ %stepvector, %vector.body.preheader
]
>   %vscale64 = call i64 @llvm.experimental.vector.vscale.64()
>   %vscale32 = trunc i64 %vscale64 to i32
>   %1 = add i64 %0, mul (i64 %vscale64, i64 4)
>
>            ;; vscale splat used to increment identity vector ;;
>   %insert = insertelement <scalable 4 x i32> undef, i32 mul (i32
%vscale32, i32 4), i32 0
>   %splat shufflevector <scalable 4 x i32> %insert, <scalable 4 x
i32> undef, <scalable 4 x i32> zeroinitializer
>   %step.add8 = add <scalable 4 x i32> %vec.ind7, %splat
>   %2 = getelementptr inbounds i32, i32* %a, i64 %0
>   %3 = bitcast i32* %2 to <scalable 4 x i32>*
>   store <scalable 4 x i32> %vec.ind7, <scalable 4 x i32>* %3,
align 4
>
>            ;; vscale used to increment loop index
>   %index.next = add i64 %index, mul (i64 %vscale64, i64 4)
>   %4 = icmp eq i64 %index.next, %n.vec
>   br i1 %4, label %middle.block, label %vector.body, !llvm.loop !5
> ``
>
> =========> 7. Patches
> =========>
> List of patches:
>
> 1. Extend VectorType: https://reviews.llvm.org/D32530
> 2. Vector element type Tablegen constraint: https://reviews.llvm.org/D47768
> 3. LLT support for scalable vectors: https://reviews.llvm.org/D47769
> 4. EVT strings and Type mapping: https://reviews.llvm.org/D47770
> 5. SVE Calling Convention: https://reviews.llvm.org/D47771
> 6. Intrinsic lowering cleanup: https://reviews.llvm.org/D47772
> 7. Add VScale intrinsic: https://reviews.llvm.org/D47773
> 8. Add StepVector intrinsic: https://reviews.llvm.org/D47774
> 9. Add SplatVector intrinsic: https://reviews.llvm.org/D47775
> 10. Initial store patterns: https://reviews.llvm.org/D47776
> 11. Initial addition patterns: https://reviews.llvm.org/D47777
> 12. Initial left-shift patterns: https://reviews.llvm.org/D47778
> 13. Implement copy logic for Z regs: https://reviews.llvm.org/D47779
> 14. Prevectorized loop unit test: https://reviews.llvm.org/D47780
>
> _______________________________________________
> 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
> https://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/20190524/97c6eaf3/attachment-0001.html>

By "generic code" I mean program instructions that is guaranteed to
run correctly on any RISC-V CPU with the V extension, now or in the
far future.

On Fri, May 24, 2019 at 1:47 PM JinGu Kang <jingu at codeplay.com>
wrote:
>
> Hi Bruce,
>
> Thanks for your comment.
>
> > Generic code can enquire the size, dynamically allocate space, and
> transparently save and restore the contents of a vector register or
> registers.
>
> I am not sure what the Generic code is. It seems it uses similar way as the
implementation of variable length array. If so, I think it could be one way to
support it.
>
> Thanks,
> JinGu Kang
>
> ________________________________
> From: Bruce Hoult <brucehoult at sifive.com>
> Sent: 24 May 2019 20:12
> To: JinGu Kang
> Cc: Chris Lattner; Hal Finkel; Jones, Joel; dag at cray.com; Renato Golin;
Kristof Beyls; Amara Emerson; Florian Hahn; Sander De Smalen; Robin Kruppe;
llvm-dev at lists.llvm.org; mkuper at google.com; Sjoerd Meijer; Sam Parker;
Graham Hunter; nd
> Subject: Re: [llvm-dev] [RFC][SVE] Supporting SIMD instruction sets with
variable vector lengths
>
> In the RISC-V V extension, there is no upper limit to the size vector
> registers can be in a future CPU. (Formally, the upper limit is at
> least 2^31 bytes)
>
> Generic code can enquire the size, dynamically allocate space, and
> transparently save and restore the contents of a vector register or
> registers.
>
> On Fri, May 24, 2019 at 11:28 AM JinGu Kang via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> >
> > Hi Graham,
> >
> > I am working on a custom target and it is considering scalable vector
type representation in programming language. While I am collecting the
information about it, I have met your RFC. I have a question. I think the one of
fundamental issues is that we do not know the memory layout of the type at
compile time. I am not sure whether the RFC covers this issue or not.
Conservatively, I imagined the memory layout of biggest type which the scalable
vector type can support. I could miss some discussions about it. If I missed
something, please let me know.
> >
> > Thanks,
> > JinGu Kang
> >
> > ________________________________
> > From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of
Graham Hunter via llvm-dev <llvm-dev at lists.llvm.org>
> > Sent: 05 June 2018 14:15
> > To: Chris Lattner; Hal Finkel; Jones, Joel; dag at cray.com; Renato
Golin; Kristof Beyls; Amara Emerson; Florian Hahn; Sander De Smalen; Robin
Kruppe; llvm-dev at lists.llvm.org; mkuper at google.com; Sjoerd Meijer; Sam
Parker
> > Cc: nd
> > Subject: [llvm-dev] [RFC][SVE] Supporting SIMD instruction sets with
variable vector lengths
> >
> > Hi,
> >
> > Now that Sander has committed enough MC support for SVE, here's an
updated
> > RFC for variable length vector support with a set of 14 patches
(listed at the end)
> > to demonstrate code generation for SVE using the extensions proposed
in the RFC.
> >
> > I have some ideas about how to support RISC-V's upcoming extension
alongside
> > SVE; I'll send an email with some additional comments on
Robin's RFC later.
> >
> > Feedback and questions welcome.
> >
> > -Graham
> >
> > ============================================================> >
Supporting SIMD instruction sets with variable vector lengths
> > ============================================================> >
> > In this RFC we propose extending LLVM IR to support code-generation
for variable
> > length vector architectures like Arm's SVE or RISC-V's
'V' extension. Our
> > approach is backwards compatible and should be as non-intrusive as
possible; the
> > only change needed in other backends is how size is queried on vector
types, and
> > it only requires a change in which function is called. We have created
a set of
> > proof-of-concept patches to represent a simple vectorized loop in IR
and
> > generate SVE instructions from that IR. These patches (listed in
section 7 of
> > this rfc) can be found on Phabricator and are intended to illustrate
the scope
> > of changes required by the general approach described in this RFC.
> >
> > =========> > Background
> > =========> >
> > *ARMv8-A Scalable Vector Extensions* (SVE) is a new vector ISA
extension for
> > AArch64 which is intended to scale with hardware such that the same
binary
> > running on a processor with longer vector registers can take advantage
of the
> > increased compute power without recompilation.
> >
> > As the vector length is no longer a compile-time known value, the way
in which
> > the LLVM vectorizer generates code requires modifications such that
certain
> > values are now runtime evaluated expressions instead of compile-time
constants.
> >
> > Documentation for SVE can be found at
> >
https://developer.arm.com/docs/ddi0584/latest/arm-architecture-reference-manual-supplement-the-scalable-vector-extension-sve-for-armv8-a
> >
> > =======> > Contents
> > =======> >
> > The rest of this RFC covers the following topics:
> >
> > 1. Types -- a proposal to extend VectorType to be able to represent
vectors that
> >    have a length which is a runtime-determined multiple of a known
base length.
> >
> > 2. Size Queries - how to reason about the size of types for which the
size isn't
> >    fully known at compile time.
> >
> > 3. Representing the runtime multiple of vector length in IR for use in
address
> >    calculations and induction variable comparisons.
> >
> > 4. Generating 'constant' values in IR for vectors with a
runtime-determined
> >    number of elements.
> >
> > 5. A brief note on code generation of these new operations for
AArch64.
> >
> > 6. An example of C code and matching IR using the proposed extensions.
> >
> > 7. A list of patches demonstrating the changes required to emit SVE
instructions
> >    for a loop that has already been vectorized using the extensions
described
> >    in this RFC.
> >
> > =======> > 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.
> >
> > The runtime multiple is not expected to change during program
execution for SVE,
> > but it is possible. The model of scalable vectors presented in this
RFC assumes
> > that the multiple will be constant within a function but not
necessarily across
> > functions. As suggested in the recent RISC-V rfc, a new function
attribute to
> > inherit the multiple across function calls will allow for function
calls with
> > vector arguments/return values and inlining/outlining optimizations.
> >
> > IR Textual Form
> > ---------------
> >
> > The textual form for a scalable vector is:
> >
> > ``<scalable <n> x <type>>``
> >
> > where `type` is the scalar type of each element, `n` is the minimum
number of
> > elements, and the string literal `scalable` indicates that the total
number of
> > elements is an unknown multiple of `n`; `scalable` is just an
arbitrary choice
> > for indicating that the vector is scalable, and could be substituted
by another.
> > For fixed-length vectors, the `scalable` is omitted, so there is no
change in
> > the format for existing vectors.
> >
> > Scalable vectors with the same `Min` value have the same number of
elements, and
> > the same number of bytes if `Min * sizeof(type)` is the same (assuming
they are
> > used within the same function):
> >
> > ``<scalable 4 x i32>`` and ``<scalable 4 x i8>`` have the
same number of
> >   elements.
> >
> > ``<scalable x 4 x i32>`` and ``<scalable x 8 x i16>`` have
the same number of
> >   bytes.
> >
> > IR Bitcode Form
> > ---------------
> >
> > To serialize scalable vectors to bitcode, a new boolean field is added
to the
> > type record. If the field is not present the type will default to a
fixed-length
> > vector type, preserving backwards compatibility.
> >
> > Alternatives Considered
> > -----------------------
> >
> > We did consider one main alternative -- a dedicated target type, like
the
> > x86_mmx type.
> >
> > A dedicated target type would either need to extend all existing
passes that
> > work with vectors to recognize the new type, or to duplicate all that
code
> > in order to get reasonable code generation and autovectorization.
> >
> > This hasn't been done for the x86_mmx type, and so it is only
capable of
> > providing support for C-level intrinsics instead of being used and
recognized by
> > passes inside llvm.
> >
> > Although our current solution will need to change some of the code
that creates
> > new VectorTypes, much of that code doesn't need to care about
whether the types
> > are scalable or not -- they can use preexisting methods like
> > `getHalfElementsVectorType`. If the code is a little more complex,
> > `ElementCount` structs can be used instead of an `unsigned` value to
represent
> > the number of elements.
> >
> > ==============> > 2. Size Queries
> > ==============> >
> > This is a proposal for how to deal with querying the size of scalable
types.
> > While it has not been implemented in full, the general approach works
well
> > for calculating offsets into structures with scalable types in a
modified
> > version of ComputeValueVTs in our downstream compiler.
> >
> > Current IR types that have a known size all return a single integer
constant.
> > For scalable types a second integer is needed to indicate the number
of bytes
> > which need to be scaled by the runtime multiple to obtain the actual
length.
> >
> > For primitive types, getPrimitiveSizeInBits will function as it does
today,
> > except that it will no longer return a size for vector types (it will
return 0,
> > as it does for other derived types). The majority of calls to this
function are
> > already for scalar rather than vector types.
> >
> > For derived types, a function (getSizeExpressionInBits) to return a
pair of
> > integers (one to indicate unscaled bits, the other for bits that need
to be
> > scaled by the runtime multiple) will be added. For backends that do
not need to
> > deal with scalable types, another function
(getFixedSizeExpressionInBits) that
> > only returns unscaled bits will be provided, with a debug assert that
the type
> > isn't scalable.
> >
> > Similar functionality will be added to DataLayout.
> >
> > Comparing two of these sizes together is straightforward if only
unscaled sizes
> > are used. Comparisons between scaled sizes is also simple when
comparing sizes
> > within a function (or across functions with the inherit flag mentioned
in the
> > changes to the type), but cannot be compared otherwise. If a mix is
present,
> > then any number of unscaled bits will not be considered to have a
greater size
> > than a smaller number of scaled bits, but a smaller number of unscaled
bits
> > will be considered to have a smaller size than a greater number of
scaled bits
> > (since the runtime multiple is at least one).
> >
> > Future Work
> > -----------
> >
> > Since we cannot determine the exact size of a scalable vector, the
> > existing logic for alias detection won't work when multiple
accesses
> > share a common base pointer with different offsets.
> >
> > However, SVE's predication will mean that a dynamic 'safe'
vector length
> > can be determined at runtime, so after initial support has been added
we
> > can work on vectorizing loops using runtime predication to avoid
aliasing
> > problems.
> >
> > Alternatives Considered
> > -----------------------
> >
> > Marking scalable vectors as unsized doesn't work well, as many
parts of
> > llvm dealing with loads and stores assert that 'isSized()'
returns true
> > and make use of the size when calculating offsets.
> >
> > We have considered introducing multiple helper functions instead of
> > using direct size queries, but that doesn't cover all cases. It
may
> > still be a good idea to introduce them to make the purpose in a given
> > case more obvious, e.g. 'isBitCastableTo(Type*,Type*)'.
> >
> > =======================================> > 3. Representing
Vector Length at Runtime
> > =======================================> >
> > With a scalable vector type defined, we now need a way to represent
the runtime
> > length in IR in order to generate addresses for consecutive vectors in
memory
> > and determine how many elements have been processed in an iteration of
a loop.
> >
> > We have added an experimental `vscale` intrinsic to represent the
runtime
> > multiple. Multiplying the result of this intrinsic by the minimum
number of
> > elements in a vector gives the total number of elements in a scalable
vector.
> >
> > Fixed-Length Code
> > -----------------
> >
> > Assuming a vector type of <4 x <ty>>
> > ``
> > vector.body:
> >   %index = phi i64 [ %index.next, %vector.body ], [ 0,
%vector.body.preheader ]
> >   ;; <loop body>
> >   ;; Increment induction var
> >   %index.next = add i64 %index, 4
> >   ;; <check and branch>
> > ``
> > Scalable Equivalent
> > -------------------
> >
> > Assuming a vector type of <scalable 4 x <ty>>
> > ``
> > vector.body:
> >   %index = phi i64 [ %index.next, %vector.body ], [ 0,
%vector.body.preheader ]
> >   ;; <loop body>
> >   ;; Increment induction var
> >   %vscale64 = call i64 @llvm.experimental.vector.vscale.64()
> >   %index.next = add i64 %index, mul (i64 %vscale64, i64 4)
> >   ;; <check and branch>
> > ``
> > ==========================> > 4. Generating Vector Values
> > ==========================> > For constant vector values, we
cannot specify all the elements as we can for
> > fixed-length vectors; fortunately only a small number of easily
synthesized
> > patterns are required for autovectorization. The `zeroinitializer`
constant
> > can be used in the same manner as fixed-length vectors for a constant
zero
> > splat. This can then be combined with `insertelement` and
`shufflevector`
> > to create arbitrary value splats in the same manner as fixed-length
vectors.
> >
> > For constants consisting of a sequence of values, an experimental
`stepvector`
> > intrinsic has been added to represent a simple constant of the form
> > `<0, 1, 2... num_elems-1>`. To change the starting value a splat
of the new
> > start can be added, and changing the step requires multiplying by a
splat.
> >
> > Fixed-Length Code
> > -----------------
> > ``
> >   ;; Splat a value
> >   %insert = insertelement <4 x i32> undef, i32 %value, i32 0
> >   %splat = shufflevector <4 x i32> %insert, <4 x i32>
undef, <4 x i32> zeroinitializer
> >   ;; Add a constant sequence
> >   %add = add <4 x i32> %splat, <i32 2, i32 4, i32 6, i32
8>
> > ``
> > Scalable Equivalent
> > -------------------
> > ``
> >   ;; Splat a value
> >   %insert = insertelement <scalable 4 x i32> undef, i32 %value,
i32 0
> >   %splat = shufflevector <scalable 4 x i32> %insert,
<scalable 4 x i32> undef, <scalable 4 x i32> zeroinitializer
> >   ;; Splat offset + stride (the same in this case)
> >   %insert2 = insertelement <scalable 4 x i32> under, i32 2, i32
0
> >   %str_off = shufflevector <scalable 4 x i32> %insert2,
<scalable 4 x i32> undef, <scalable 4 x i32> zeroinitializer
> >   ;; Create sequence for scalable vector
> >   %stepvector = call <scalable 4 x i32>
@llvm.experimental.vector.stepvector.nxv4i32()
> >   %mulbystride = mul <scalable 4 x i32> %stepvector, %str_off
> >   %addoffset = add <scalable 4 x i32> %mulbystride, %str_off
> >   ;; Add the runtime-generated sequence
> >   %add = add <scalable 4 x i32> %splat, %addoffset
> > ``
> > Future Work
> > -----------
> >
> > Intrinsics cannot currently be used for constant folding. Our
downstream
> > compiler (using Constants instead of intrinsics) relies quite heavily
on this
> > for good code generation, so we will need to find new ways to
recognize and
> > fold these values.
> >
> > =================> > 5. Code Generation
> > =================> >
> > IR splats will be converted to an experimental splatvector intrinsic
in
> > SelectionDAGBuilder.
> >
> > All three intrinsics are custom lowered and legalized in the AArch64
backend.
> >
> > Two new AArch64ISD nodes have been added to represent the same
concepts
> > at the SelectionDAG level, while splatvector maps onto the existing
> > AArch64ISD::DUP.
> >
> > GlobalISel
> > ----------
> >
> > Since GlobalISel was enabled by default on AArch64, it was necessary
to add
> > scalable vector support to the LowLevelType implementation. A single
bit was
> > added to the raw_data representation for vectors and vectors of
pointers.
> >
> > In addition, types that only exist in destination patterns are planted
in
> > the enumeration of available types for generated code. While this may
not be
> > necessary in future, generating an all-true 'ptrue' value was
necessary to
> > convert a predicated instruction into an unpredicated one.
> >
> > =========> > 6. Example
> > =========> >
> > The following example shows a simple C loop which assigns the array
index to
> > the array elements matching that index. The IR shows how vscale and
stepvector
> > are used to create the needed values and to advance the index variable
in the
> > loop.
> >
> > C Code
> > ------
> >
> > ``
> > void IdentityArrayInit(int *a, int count) {
> >   for (int i = 0; i < count; ++i)
> >     a[i] = i;
> > }
> > ``
> >
> > Scalable IR Vector Body
> > -----------------------
> >
> > ``
> > vector.body.preheader:
> >   ;; Other setup
> >   ;; Stepvector used to create initial identity vector
> >   %stepvector = call <scalable 4 x i32>
@llvm.experimental.vector.stepvector.nxv4i32()
> >   br vector.body
> >
> > vector.body
> >   %index = phi i64 [ %index.next, %vector.body ], [ 0,
%vector.body.preheader ]
> >   %0 = phi i64 [ %1, %vector.body ], [ 0, %vector.body.preheader ]
> >
> >            ;; stepvector used for index identity on entry to loop body
;;
> >   %vec.ind7 = phi <scalable 4 x i32> [ %step.add8, %vector.body
],
> >                                      [ %stepvector,
%vector.body.preheader ]
> >   %vscale64 = call i64 @llvm.experimental.vector.vscale.64()
> >   %vscale32 = trunc i64 %vscale64 to i32
> >   %1 = add i64 %0, mul (i64 %vscale64, i64 4)
> >
> >            ;; vscale splat used to increment identity vector ;;
> >   %insert = insertelement <scalable 4 x i32> undef, i32 mul (i32
%vscale32, i32 4), i32 0
> >   %splat shufflevector <scalable 4 x i32> %insert, <scalable
4 x i32> undef, <scalable 4 x i32> zeroinitializer
> >   %step.add8 = add <scalable 4 x i32> %vec.ind7, %splat
> >   %2 = getelementptr inbounds i32, i32* %a, i64 %0
> >   %3 = bitcast i32* %2 to <scalable 4 x i32>*
> >   store <scalable 4 x i32> %vec.ind7, <scalable 4 x i32>*
%3, align 4
> >
> >            ;; vscale used to increment loop index
> >   %index.next = add i64 %index, mul (i64 %vscale64, i64 4)
> >   %4 = icmp eq i64 %index.next, %n.vec
> >   br i1 %4, label %middle.block, label %vector.body, !llvm.loop !5
> > ``
> >
> > =========> > 7. Patches
> > =========> >
> > List of patches:
> >
> > 1. Extend VectorType: https://reviews.llvm.org/D32530
> > 2. Vector element type Tablegen constraint:
https://reviews.llvm.org/D47768
> > 3. LLT support for scalable vectors: https://reviews.llvm.org/D47769
> > 4. EVT strings and Type mapping: https://reviews.llvm.org/D47770
> > 5. SVE Calling Convention: https://reviews.llvm.org/D47771
> > 6. Intrinsic lowering cleanup: https://reviews.llvm.org/D47772
> > 7. Add VScale intrinsic: https://reviews.llvm.org/D47773
> > 8. Add StepVector intrinsic: https://reviews.llvm.org/D47774
> > 9. Add SplatVector intrinsic: https://reviews.llvm.org/D47775
> > 10. Initial store patterns: https://reviews.llvm.org/D47776
> > 11. Initial addition patterns: https://reviews.llvm.org/D47777
> > 12. Initial left-shift patterns: https://reviews.llvm.org/D47778
> > 13. Implement copy logic for Z regs: https://reviews.llvm.org/D47779
> > 14. Prevectorized loop unit test: https://reviews.llvm.org/D47780
> >
> > _______________________________________________
> > 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
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev