<div dir="ltr"><div>Hi Graham,</div><div><br></div>First of all, thanks a lot for updating the RFC and also for putting up the<br>patches, they are quite interesting and illuminate some details I was curious<br>about. I have some minor questions and comments inline below but overall I<br>believe this is both a reasonably small extension of LLVM IR and powerful<br>enough to support SVE, RVV, and hopefully future ISAs with variable length<br><div>vectors. Details may change as we gather more experience, but it's a very<br></div><div>good starting point.<br></div><div><br></div><div>
<div></div><div>One thing I am missing is a discussion of how stack frame layout will be<br>handled. Earlier RFCs mentioned a concept called "Stack Regions" but (IIRC)<br>gave little details and it was a long time ago anyway. What are your current<br>plans here?<br></div>
</div><div><br></div>I'll reply
separately
to the sub-thread about RISC-V codegen.<br><div><br></div><div>Cheers,</div><div>Robin<br></div><div class="gmail_extra"><br><div class="gmail_quote">On 5 June 2018 at 15:15, Graham Hunter <span dir="ltr"><<a href="mailto:Graham.Hunter@arm.com" target="_blank">Graham.Hunter@arm.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi,<br>
<br>
Now that Sander has committed enough MC support for SVE, here's an updated<br>
RFC for variable length vector support with a set of 14 patches (listed at the end)<br>
to demonstrate code generation for SVE using the extensions proposed in the RFC.<br>
<br>
I have some ideas about how to support RISC-V's upcoming extension alongside<br>
SVE; I'll send an email with some additional comments on Robin's RFC later.<br>
<br>
Feedback and questions welcome.<br>
<br>
-Graham<br>
<br>
==============================<wbr>==============================<wbr>=<br>
Supporting SIMD instruction sets with variable vector lengths<br>
==============================<wbr>==============================<wbr>=<br>
<br>
In this RFC we propose extending LLVM IR to support code-generation for variable<br>
length vector architectures like Arm's SVE or RISC-V's 'V' extension. Our<br>
approach is backwards compatible and should be as non-intrusive as possible; the<br>
only change needed in other backends is how size is queried on vector types, and<br>
it only requires a change in which function is called. We have created a set of<br>
proof-of-concept patches to represent a simple vectorized loop in IR and<br>
generate SVE instructions from that IR. These patches (listed in section 7 of<br>
this rfc) can be found on Phabricator and are intended to illustrate the scope<br>
of changes required by the general approach described in this RFC.<br>
<br>
==========<br>
Background<br>
==========<br>
<br>
*ARMv8-A Scalable Vector Extensions* (SVE) is a new vector ISA extension for<br>
AArch64 which is intended to scale with hardware such that the same binary<br>
running on a processor with longer vector registers can take advantage of the<br>
increased compute power without recompilation.<br>
<br>
As the vector length is no longer a compile-time known value, the way in which<br>
the LLVM vectorizer generates code requires modifications such that certain<br>
values are now runtime evaluated expressions instead of compile-time constants.<br>
<br>
Documentation for SVE can be found at<br>
<a href="https://developer.arm.com/docs/ddi0584/latest/arm-architecture-reference-manual-supplement-the-scalable-vector-extension-sve-for-armv8-a" rel="noreferrer" target="_blank">https://developer.arm.com/docs<wbr>/ddi0584/latest/arm-architectu<wbr>re-reference-manual-supplement<wbr>-the-scalable-vector-<wbr>extension-sve-for-armv8-a</a><br>
<br>
========<br>
Contents<br>
========<br>
<br>
The rest of this RFC covers the following topics:<br>
<br>
1. Types -- a proposal to extend VectorType to be able to represent vectors that<br>
have a length which is a runtime-determined multiple of a known base length.<br>
<br>
2. Size Queries - how to reason about the size of types for which the size isn't<br>
fully known at compile time.<br>
<br>
3. Representing the runtime multiple of vector length in IR for use in address<br>
calculations and induction variable comparisons.<br>
<br>
4. Generating 'constant' values in IR for vectors with a runtime-determined<br>
number of elements.<br>
<br>
5. A brief note on code generation of these new operations for AArch64.<br>
<br>
6. An example of C code and matching IR using the proposed extensions.<br>
<br>
7. A list of patches demonstrating the changes required to emit SVE instructions<br>
for a loop that has already been vectorized using the extensions described<br>
in this RFC.<br>
<br>
========<br>
1. Types<br>
========<br>
<br>
To represent a vector of unknown length a boolean `Scalable` property has been<br>
added to the `VectorType` class, which indicates that the number of elements in<br>
the vector is a runtime-determined integer multiple of the `NumElements` field.<br>
Most code that deals with vectors doesn't need to know the exact length, but<br>
does need to know relative lengths -- e.g. get a vector with the same number of<br>
elements but a different element type, or with half or double the number of<br>
elements.<br>
<br>
In order to allow code to transparently support scalable vectors, we introduce<br>
an `ElementCount` class with two members:<br>
<br>
- `unsigned Min`: the minimum number of elements.<br>
- `bool Scalable`: is the element count an unknown multiple of `Min`?<br>
<br>
For non-scalable vectors (``Scalable=false``) the scale is considered to be<br>
equal to one and thus `Min` represents the exact number of elements in the<br>
vector.<br>
<br>
The intent for code working with vectors is to use convenience methods and avoid<br>
directly dealing with the number of elements. If needed, calling<br>
`getElementCount` on a vector type instead of `getVectorNumElements` can be used<br>
to obtain the (potentially scalable) number of elements. Overloaded division and<br>
multiplication operators allow an ElementCount instance to be used in much the<br>
same manner as an integer for most cases.<br>
<br>
This mixture of compile-time and runtime quantities allow us to reason about the<br>
relationship between different scalable vector types without knowing their<br>
exact length.<br>
<br>
The runtime multiple is not expected to change during program execution for SVE,<br>
but it is possible. The model of scalable vectors presented in this RFC assumes<br>
that the multiple will be constant within a function but not necessarily across<br>
functions. As suggested in the recent RISC-V rfc, a new function attribute to<br>
inherit the multiple across function calls will allow for function calls with<br>
vector arguments/return values and inlining/outlining optimizations.<br>
<br>
IR Textual Form<br>
---------------<br>
<br>
The textual form for a scalable vector is:<br>
<br>
``<scalable <n> x <type>>``<br>
<br>
where `type` is the scalar type of each element, `n` is the minimum number of<br>
elements, and the string literal `scalable` indicates that the total number of<br>
elements is an unknown multiple of `n`; `scalable` is just an arbitrary choice<br>
for indicating that the vector is scalable, and could be substituted by another.<br>
For fixed-length vectors, the `scalable` is omitted, so there is no change in<br>
the format for existing vectors.<br>
<br>
Scalable vectors with the same `Min` value have the same number of elements, and<br>
the same number of bytes if `Min * sizeof(type)` is the same (assuming they are<br>
used within the same function):<br>
<br>
``<scalable 4 x i32>`` and ``<scalable 4 x i8>`` have the same number of<br>
elements.<br>
<br>
``<scalable x 4 x i32>`` and ``<scalable x 8 x i16>`` have the same number of<br>
bytes.<br>
<br>
IR Bitcode Form<br>
---------------<br>
<br>
To serialize scalable vectors to bitcode, a new boolean field is added to the<br>
type record. If the field is not present the type will default to a fixed-length<br>
vector type, preserving backwards compatibility.<br>
<br>
Alternatives Considered<br>
-----------------------<br>
<br>
We did consider one main alternative -- a dedicated target type, like the<br>
x86_mmx type.<br>
<br>
A dedicated target type would either need to extend all existing passes that<br>
work with vectors to recognize the new type, or to duplicate all that code<br>
in order to get reasonable code generation and autovectorization.<br>
<br>
This hasn't been done for the x86_mmx type, and so it is only capable of<br>
providing support for C-level intrinsics instead of being used and recognized by<br>
passes inside llvm.<br>
<br>
Although our current solution will need to change some of the code that creates<br>
new VectorTypes, much of that code doesn't need to care about whether the types<br>
are scalable or not -- they can use preexisting methods like<br>
`getHalfElementsVectorType`. If the code is a little more complex,<br>
`ElementCount` structs can be used instead of an `unsigned` value to represent<br>
the number of elements.<br>
<br>
===============<br>
2. Size Queries<br>
===============<br>
<br>
This is a proposal for how to deal with querying the size of scalable types.<br>
While it has not been implemented in full, the general approach works well<br>
for calculating offsets into structures with scalable types in a modified<br>
version of ComputeValueVTs in our downstream compiler.<br>
<br>
Current IR types that have a known size all return a single integer constant.<br>
For scalable types a second integer is needed to indicate the number of bytes<br>
which need to be scaled by the runtime multiple to obtain the actual length.<br>
<br>
For primitive types, getPrimitiveSizeInBits will function as it does today,<br>
except that it will no longer return a size for vector types (it will return 0,<br>
as it does for other derived types). The majority of calls to this function are<br>
already for scalar rather than vector types.<br>
<br>
For derived types, a function (getSizeExpressionInBits) to return a pair of<br>
integers (one to indicate unscaled bits, the other for bits that need to be<br>
scaled by the runtime multiple) will be added. For backends that do not need to<br>
deal with scalable types, another function (getFixedSizeExpressionInBits) that<br>
only returns unscaled bits will be provided, with a debug assert that the type<br>
isn't scalable.<br>
<br>
Similar functionality will be added to DataLayout.<br>
<br>
Comparing two of these sizes together is straightforward if only unscaled sizes<br>
are used. Comparisons between scaled sizes is also simple when comparing sizes<br>
within a function (or across functions with the inherit flag mentioned in the<br>
changes to the type), but cannot be compared otherwise. If a mix is present,<br>
then any number of unscaled bits will not be considered to have a greater size<br>
than a smaller number of scaled bits, but a smaller number of unscaled bits<br>
will be considered to have a smaller size than a greater number of scaled bits<br>
(since the runtime multiple is at least one).<br></blockquote><div><br></div><div>You mention it's not fully implemented yet, but perhaps you have some thoughts<br>on what the APIs for this should look like?<br><br>For size comparisons it's concerning that it could silently give misleading<br>results when operating across function boundaries. One solution could be a<br>function-specific API like `compareSizesIn(Type *, Type *, Function *)`, but<br>that extra parameter may turn out to be very viral. OTOH, maybe that's<br>unavoidable complexity from having type "sizes" vary between functions.<br></div><div><br></div><div>Alternatively, general size queries could return "incomparable" and "only if<br>in the same function" results in addition to smaller/larger/equal. This might<br>nudge code to handling all these possibilities as well as it can.<br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Future Work<br>
-----------<br>
<br>
Since we cannot determine the exact size of a scalable vector, the<br>
existing logic for alias detection won't work when multiple accesses<br>
share a common base pointer with different offsets.<br>
<br>
However, SVE's predication will mean that a dynamic 'safe' vector length<br>
can be determined at runtime, so after initial support has been added we<br>
can work on vectorizing loops using runtime predication to avoid aliasing<br>
problems.<br>
<br>
Alternatives Considered<br>
-----------------------<br>
<br>
Marking scalable vectors as unsized doesn't work well, as many parts of<br>
llvm dealing with loads and stores assert that 'isSized()' returns true<br>
and make use of the size when calculating offsets.<br></blockquote><div><br></div><div>Seconded, I encountered those as well.<br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
We have considered introducing multiple helper functions instead of<br>
using direct size queries, but that doesn't cover all cases. It may<br>
still be a good idea to introduce them to make the purpose in a given<br>
case more obvious, e.g. 'isBitCastableTo(Type*,Type*)'<wbr>.<br></blockquote><div> </div>+1 for clear helpers, but this sentiment is somewhat independent of the<br>changes to type sizes. For example, `isBitCastableTo` seems appealing to me<br>not just because it clarifies the intent of the size comparison but also<br>because it can encapsulate all the cases where types have the same size but<br>bitcasts still aren't allowed (ptr<->int, aggregates). With a good API for the<br>{scaled, unscaled} pairs, the size comparison should not be much more complex<br>than today.<br><div><br>Aside: I was curious, so I grepped and found that this specific predicate<br>already exists under the name CastInst::isBitCastable.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
==============================<wbr>==========<br>
3. Representing Vector Length at Runtime<br>
==============================<wbr>==========<br>
<br>
With a scalable vector type defined, we now need a way to represent the runtime<br>
length in IR in order to generate addresses for consecutive vectors in memory<br>
and determine how many elements have been processed in an iteration of a loop.<br>
<br>
We have added an experimental `vscale` intrinsic to represent the runtime<br>
multiple. Multiplying the result of this intrinsic by the minimum number of<br>
elements in a vector gives the total number of elements in a scalable vector.<br>
<br>
Fixed-Length Code<br>
-----------------<br>
<br>
Assuming a vector type of <4 x <ty>><br>
``<br>
vector.body:<br>
%index = phi i64 [ %index.next, %vector.body ], [ 0, %vector.body.preheader ]<br>
;; <loop body><br>
;; Increment induction var<br>
%index.next = add i64 %index, 4<br>
;; <check and branch><br>
``<br>
Scalable Equivalent<br>
-------------------<br>
<br>
Assuming a vector type of <scalable 4 x <ty>><br>
``<br>
vector.body:<br>
%index = phi i64 [ %index.next, %vector.body ], [ 0, %vector.body.preheader ]<br>
;; <loop body><br>
;; Increment induction var<br>
%vscale64 = call i64 @llvm.experimental.vector.vsca<wbr>le.64()<br></blockquote><div><br>I didn't see anything about this in the text (apologies if I missed<br>something), but it appears this intrinsic is overloaded to be able to return<br>any integer width. It's not a big deal either way, but is there a particular<br>reason for doing that, rather than picking one sufficiently large integer type<br>and combining it with trunc/zext as appropriate?<br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> %index.next = add i64 %index, mul (i64 %vscale64, i64 4)<br></blockquote><div> </div><div>Just to check, is the nesting `add i64 %index, mul (i64 %vscale64, i64 4)` a<br>pseudo-IR shorthand or an artifact from when vscale was proposed as a constant<br>expression or something? I would have expected:<br><br>```<br>%vscale64 = call i64 @llvm.experimental.vector.<wbr>vscale.64()<br>%vscale64.x4 = mul i64 %vscale64, 4<br>%index.next = add i64 %index, %vscale64.x4<br>```<br><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
;; <check and branch><br>
``<br>
===========================<br>
4. Generating Vector Values<br>
===========================<br>
For constant vector values, we cannot specify all the elements as we can for<br>
fixed-length vectors; fortunately only a small number of easily synthesized<br>
patterns are required for autovectorization. The `zeroinitializer` constant<br>
can be used in the same manner as fixed-length vectors for a constant zero<br>
splat. This can then be combined with `insertelement` and `shufflevector`<br>
to create arbitrary value splats in the same manner as fixed-length vectors.<br>
<br>
For constants consisting of a sequence of values, an experimental `stepvector`<br>
intrinsic has been added to represent a simple constant of the form<br>
`<0, 1, 2... num_elems-1>`. To change the starting value a splat of the new<br>
start can be added, and changing the step requires multiplying by a splat.<br></blockquote><div><br></div><div>+1 for making this intrinsic minimal and having canonical IR instruction<br>sequences for things like stride and starting offset.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Fixed-Length Code<br>
-----------------<br>
``<br>
;; Splat a value<br>
%insert = insertelement <4 x i32> undef, i32 %value, i32 0<br>
%splat = shufflevector <4 x i32> %insert, <4 x i32> undef, <4 x i32> zeroinitializer<br>
;; Add a constant sequence<br>
%add = add <4 x i32> %splat, <i32 2, i32 4, i32 6, i32 8><br>
``<br>
Scalable Equivalent<br>
-------------------<br>
``<br>
;; Splat a value<br>
%insert = insertelement <scalable 4 x i32> undef, i32 %value, i32 0<br>
%splat = shufflevector <scalable 4 x i32> %insert, <scalable 4 x i32> undef, <scalable 4 x i32> zeroinitializer<br>
;; Splat offset + stride (the same in this case)<br>
%insert2 = insertelement <scalable 4 x i32> under, i32 2, i32 0<br>
%str_off = shufflevector <scalable 4 x i32> %insert2, <scalable 4 x i32> undef, <scalable 4 x i32> zeroinitializer<br>
;; Create sequence for scalable vector<br>
%stepvector = call <scalable 4 x i32> @llvm.experimental.vector.step<wbr>vector.nxv4i32()<br>
%mulbystride = mul <scalable 4 x i32> %stepvector, %str_off<br>
%addoffset = add <scalable 4 x i32> %mulbystride, %str_off<br>
;; Add the runtime-generated sequence<br>
%add = add <scalable 4 x i32> %splat, %addoffset<br>
``<br>
Future Work<br>
-----------<br>
<br>
Intrinsics cannot currently be used for constant folding. Our downstream<br>
compiler (using Constants instead of intrinsics) relies quite heavily on this<br>
for good code generation, so we will need to find new ways to recognize and<br>
fold these values.<br>
<br>
==================<br>
5. Code Generation<br>
==================<br>
<br>
IR splats will be converted to an experimental splatvector intrinsic in<br>
SelectionDAGBuilder.<br>
<br>
All three intrinsics are custom lowered and legalized in the AArch64 backend.<br>
<br>
Two new AArch64ISD nodes have been added to represent the same concepts<br>
at the SelectionDAG level, while splatvector maps onto the existing<br>
AArch64ISD::DUP.<br>
<br>
GlobalISel<br>
----------<br>
<br>
Since GlobalISel was enabled by default on AArch64, it was necessary to add<br>
scalable vector support to the LowLevelType implementation. A single bit was<br>
added to the raw_data representation for vectors and vectors of pointers.<br>
<br>
In addition, types that only exist in destination patterns are planted in<br>
the enumeration of available types for generated code. While this may not be<br>
necessary in future, generating an all-true 'ptrue' value was necessary to<br>
convert a predicated instruction into an unpredicated one.<br>
<br>
==========<br>
6. Example<br>
==========<br>
<br>
The following example shows a simple C loop which assigns the array index to<br>
the array elements matching that index. The IR shows how vscale and stepvector<br>
are used to create the needed values and to advance the index variable in the<br>
loop.<br>
<br>
C Code<br>
------<br>
<br>
``<br>
void IdentityArrayInit(int *a, int count) {<br>
for (int i = 0; i < count; ++i)<br>
a[i] = i;<br>
}<br>
``<br>
<br>
Scalable IR Vector Body<br>
-----------------------<br>
<br>
``<br>
vector.body.preheader:<br>
;; Other setup<br>
;; Stepvector used to create initial identity vector<br>
%stepvector = call <scalable 4 x i32> @llvm.experimental.vector.step<wbr>vector.nxv4i32()<br>
br vector.body<br>
<br>
vector.body<br>
%index = phi i64 [ %index.next, %vector.body ], [ 0, %vector.body.preheader ]<br>
%0 = phi i64 [ %1, %vector.body ], [ 0, %vector.body.preheader ]<br>
<br>
;; stepvector used for index identity on entry to loop body ;;<br>
%vec.ind7 = phi <scalable 4 x i32> [ %step.add8, %vector.body ],<br>
[ %stepvector, %vector.body.preheader ]<br>
%vscale64 = call i64 @llvm.experimental.vector.vsca<wbr>le.64()<br>
%vscale32 = trunc i64 %vscale64 to i32<br>
%1 = add i64 %0, mul (i64 %vscale64, i64 4)<br>
<br>
;; vscale splat used to increment identity vector ;;<br>
%insert = insertelement <scalable 4 x i32> undef, i32 mul (i32 %vscale32, i32 4), i32 0<br>
%splat shufflevector <scalable 4 x i32> %insert, <scalable 4 x i32> undef, <scalable 4 x i32> zeroinitializer<br>
%step.add8 = add <scalable 4 x i32> %vec.ind7, %splat<br>
%2 = getelementptr inbounds i32, i32* %a, i64 %0<br>
%3 = bitcast i32* %2 to <scalable 4 x i32>*<br>
store <scalable 4 x i32> %vec.ind7, <scalable 4 x i32>* %3, align 4<br>
<br>
;; vscale used to increment loop index<br>
%index.next = add i64 %index, mul (i64 %vscale64, i64 4)<br>
%4 = icmp eq i64 %index.next, %n.vec<br>
br i1 %4, label %middle.block, label %vector.body, !llvm.loop !5<br>
``<br>
<br>
==========<br>
7. Patches<br>
==========<br>
<br>
List of patches:<br>
<br>
1. Extend VectorType: <a href="https://reviews.llvm.org/D32530" rel="noreferrer" target="_blank">https://reviews.llvm.org/D3253<wbr>0</a><br>
2. Vector element type Tablegen constraint: <a href="https://reviews.llvm.org/D47768" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4776<wbr>8</a><br>
3. LLT support for scalable vectors: <a href="https://reviews.llvm.org/D47769" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4776<wbr>9</a><br>
4. EVT strings and Type mapping: <a href="https://reviews.llvm.org/D47770" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4777<wbr>0</a><br>
5. SVE Calling Convention: <a href="https://reviews.llvm.org/D47771" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4777<wbr>1</a><br>
6. Intrinsic lowering cleanup: <a href="https://reviews.llvm.org/D47772" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4777<wbr>2</a><br>
7. Add VScale intrinsic: <a href="https://reviews.llvm.org/D47773" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4777<wbr>3</a><br>
8. Add StepVector intrinsic: <a href="https://reviews.llvm.org/D47774" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4777<wbr>4</a><br>
9. Add SplatVector intrinsic: <a href="https://reviews.llvm.org/D47775" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4777<wbr>5</a><br>
10. Initial store patterns: <a href="https://reviews.llvm.org/D47776" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4777<wbr>6</a><br>
11. Initial addition patterns: <a href="https://reviews.llvm.org/D47777" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4777<wbr>7</a><br>
12. Initial left-shift patterns: <a href="https://reviews.llvm.org/D47778" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4777<wbr>8</a><br>
13. Implement copy logic for Z regs: <a href="https://reviews.llvm.org/D47779" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4777<wbr>9</a><br>
14. Prevectorized loop unit test: <a href="https://reviews.llvm.org/D47780" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4778<wbr>0</a><br>
<br>
</blockquote></div><br></div></div>