<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Hi Graham,</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
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.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Thanks,</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
JinGu Kang<br>
</div>
<div>
<div id="appendonsend"></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="divRplyFwdMsg" dir="ltr"><font style="font-size:11pt" face="Calibri, sans-serif" color="#000000"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> on behalf of Graham Hunter via llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Sent:</b> 05 June 2018 14:15<br>
<b>To:</b> Chris Lattner; Hal Finkel; Jones, Joel; dag@cray.com; Renato Golin; Kristof Beyls; Amara Emerson; Florian Hahn; Sander De Smalen; Robin Kruppe; llvm-dev@lists.llvm.org; mkuper@google.com; Sjoerd Meijer; Sam Parker<br>
<b>Cc:</b> nd<br>
<b>Subject:</b> [llvm-dev] [RFC][SVE] Supporting SIMD instruction sets with variable vector lengths</font>
<div> </div>
</div>
<div class="BodyFragment"><font size="2"><span style="font-size:11pt">
<div class="PlainText">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>
=============================================================<br>
Supporting SIMD instruction sets with variable vector lengths<br>
=============================================================<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">https://developer.arm.com/docs/ddi0584/latest/arm-architecture-reference-manual-supplement-the-scalable-vector-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>
<br>
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>
<br>
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*)'.<br>
<br>
========================================<br>
3. Representing Vector Length at Runtime<br>
========================================<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.vscale.64()<br>
%index.next = add i64 %index, mul (i64 %vscale64, i64 4)<br>
;; <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>
<br>
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.stepvector.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.stepvector.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.vscale.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">https://reviews.llvm.org/D32530</a><br>
2. Vector element type Tablegen constraint: <a href="https://reviews.llvm.org/D47768">
https://reviews.llvm.org/D47768</a><br>
3. LLT support for scalable vectors: <a href="https://reviews.llvm.org/D47769">https://reviews.llvm.org/D47769</a><br>
4. EVT strings and Type mapping: <a href="https://reviews.llvm.org/D47770">https://reviews.llvm.org/D47770</a><br>
5. SVE Calling Convention: <a href="https://reviews.llvm.org/D47771">https://reviews.llvm.org/D47771</a><br>
6. Intrinsic lowering cleanup: <a href="https://reviews.llvm.org/D47772">https://reviews.llvm.org/D47772</a><br>
7. Add VScale intrinsic: <a href="https://reviews.llvm.org/D47773">https://reviews.llvm.org/D47773</a><br>
8. Add StepVector intrinsic: <a href="https://reviews.llvm.org/D47774">https://reviews.llvm.org/D47774</a><br>
9. Add SplatVector intrinsic: <a href="https://reviews.llvm.org/D47775">https://reviews.llvm.org/D47775</a><br>
10. Initial store patterns: <a href="https://reviews.llvm.org/D47776">https://reviews.llvm.org/D47776</a><br>
11. Initial addition patterns: <a href="https://reviews.llvm.org/D47777">https://reviews.llvm.org/D47777</a><br>
12. Initial left-shift patterns: <a href="https://reviews.llvm.org/D47778">https://reviews.llvm.org/D47778</a><br>
13. Implement copy logic for Z regs: <a href="https://reviews.llvm.org/D47779">https://reviews.llvm.org/D47779</a><br>
14. Prevectorized loop unit test: <a href="https://reviews.llvm.org/D47780">https://reviews.llvm.org/D47780</a><br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
llvm-dev@lists.llvm.org<br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</div>
</span></font></div>
</div>
</body>
</html>