<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="#0563C1" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal">Paul,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> Really, the two big use cases for scalable vectors are stepvector and enabling more uses of shufflevector. shufflevector is the one constant expression that “doesn’t work” for scalable vectors yet. Realistically, it can
never be made to work with arbitrary constant scalable vectors without a fundamental redesign. Another use case is that we could simplify more constant expressions if they are written in terms of ConstantStepVector. Using the original proposed stepvector literal,
(here, `splat(1)` is the insertelement/shufflevector thing; I’m not going to write it out) `splat(1) + stepvector` is as simplified as it can get, but `splat(1) + <0, 1, …>` can be simplified to `<1, 2, …>`.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> That said, there are other uses for fixed width vectors. It would enable writing more compact LLVM IR code, which is useful in test cases (stepvector of type <64 x i8> would span multiple lines). Additionally, pattern matching
on a stepvector is linear in the width of the vector, but for ConstantStepVector it will have constant time. These are, admittedly, minor advantages. However, I think the level of effort in implementing ConstantStepVector with a start/stride pair vs ConstantStepVector
that starts at zero and increments by one is not that great.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
<p class="MsoNormal"> Christopher Tetreault<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> Paul Walker <Paul.Walker@arm.com> <br>
<b>Sent:</b> Wednesday, January 27, 2021 4:36 AM<br>
<b>To:</b> Chris Tetreault <ctetreau@quicinc.com>; David Sherwood <David.Sherwood@arm.com>; llvm-dev@lists.llvm.org<br>
<b>Cc:</b> Sander De Smalen <Sander.DeSmalen@arm.com>; Eli Friedman <efriedma@quicinc.com>; cameron.mcinally@nyu.edu<br>
<b>Subject:</b> [EXT] Re: [RFC] Introduce a new stepvector operation<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span lang="EN-GB">Hi Chris,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">I just wanted to say that I like this idea (i.e. <i32 0, i32 1, …>) very much but wonder how much of it is reliant on its potential uses by shufflevector. I ask because the shufflevector problem has extra pitfalls and
I'm not convinced opening up a handful of extra shuffles (beyond the current splat support, which I consider a bit of a hack) is that great long term.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Essentially, I'm not a fan of having a nobbled shufflevector for scalable vectors as compared to fixed length vectors. Taking your splat example, I would much prefer a dedicated splat instruction that works for all vector
types and be just as pretty for constant and variable splats, whereas ConstantStepVector only helps with constant splats.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">As I say, I like the idea and so am really just asking if you think there'll be enough pull to make it happen without tying it to shufflevector?<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Paul!!!<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span lang="EN-GB" style="font-size:12.0pt;color:black">From:
</span></b><span lang="EN-GB" style="font-size:12.0pt;color:black">Chris Tetreault <</span><a href="mailto:ctetreau@quicinc.com"><span lang="EN-GB" style="font-size:12.0pt">ctetreau@quicinc.com</span></a><span lang="EN-GB" style="font-size:12.0pt;color:black">><br>
<b>Date: </b>Tuesday, 26 January 2021 at 17:34<br>
<b>To: </b>David Sherwood <</span><a href="mailto:David.Sherwood@arm.com"><span lang="EN-GB" style="font-size:12.0pt">David.Sherwood@arm.com</span></a><span lang="EN-GB" style="font-size:12.0pt;color:black">>, "</span><a href="mailto:llvm-dev@lists.llvm.org"><span lang="EN-GB" style="font-size:12.0pt">llvm-dev@lists.llvm.org</span></a><span lang="EN-GB" style="font-size:12.0pt;color:black">"
<</span><a href="mailto:llvm-dev@lists.llvm.org"><span lang="EN-GB" style="font-size:12.0pt">llvm-dev@lists.llvm.org</span></a><span lang="EN-GB" style="font-size:12.0pt;color:black">><br>
<b>Cc: </b>Sander De Smalen <</span><a href="mailto:Sander.DeSmalen@arm.com"><span lang="EN-GB" style="font-size:12.0pt">Sander.DeSmalen@arm.com</span></a><span lang="EN-GB" style="font-size:12.0pt;color:black">>, Paul Walker <</span><a href="mailto:Paul.Walker@arm.com"><span lang="EN-GB" style="font-size:12.0pt">Paul.Walker@arm.com</span></a><span lang="EN-GB" style="font-size:12.0pt;color:black">>,
Eli Friedman <</span><a href="mailto:efriedma@quicinc.com"><span lang="EN-GB" style="font-size:12.0pt">efriedma@quicinc.com</span></a><span lang="EN-GB" style="font-size:12.0pt;color:black">>, "</span><a href="mailto:cameron.mcinally@nyu.edu"><span lang="EN-GB" style="font-size:12.0pt">cameron.mcinally@nyu.edu</span></a><span lang="EN-GB" style="font-size:12.0pt;color:black">"
<</span><a href="mailto:cameron.mcinally@nyu.edu"><span lang="EN-GB" style="font-size:12.0pt">cameron.mcinally@nyu.edu</span></a><span lang="EN-GB" style="font-size:12.0pt;color:black">><br>
<b>Subject: </b>RE: [RFC] Introduce a new stepvector operation<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
</div>
<p class="MsoNormal"><span lang="EN-GB">David,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> I am proposing a new C++ class (ConstantStepVector is fine; I don’t really care what color the bike shed is). In my scheme, there would be no `stepvector` literal, but you could write <0, 1, …> in IR and
get the stepvector returned by llvm::InnerLoopVectorizer::getStepVector().<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> I would expect that you could write these ConstantStepVector literals directly in statements, so instead of:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">vector.body:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> %vec.ind = phi <4 x i32> [ <i32 0, i32 1, i32 2, i32 3>, %vector.ph ], …<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> you would have:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">vector.body:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> %vec.ind = phi <4 x i32> [ <i32 0, i32 1, …>, %vector.ph ], …<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> … and it would also allow you to have:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">vector.body:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> %vec.ind = phi <vscale x 4 x i32> [ <i32 0, i32 1, …>, %vector.ph ], …<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> At some point, I think it would probably make sense to start canonicalizing to it. As you know, for scalable splats we do this horrible insertelement/shufflevector thing, that should be replaced by <n,
n, …> (for all splats except zero and undef). Scalable stepvector would have to use it, but it may make sense to have fixed width stepvector use it. I mentioned downthread several potential uses for it. For shufflevector, we currently allow zeroinitializer
and undef for scalable shuffle masks. We could allow ConstantStepVector, and internally in C++ code produce the fixed subvector mask, and special case it for scalable shuffles (that code is already a bit gross).<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> Overall, I think having a constant literal is useful. However, if we’re going to add complexity to the language, let’s do it in the most flexible way possible. It would be silly to have the stepvector
literal, and then decide to also have ConstantStepVector at some point in the future.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Thanks,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> Christopher Tetreault<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span lang="EN-GB">From:</span></b><span lang="EN-GB"> David Sherwood <</span><a href="mailto:David.Sherwood@arm.com"><span lang="EN-GB">David.Sherwood@arm.com</span></a><span lang="EN-GB">>
<br>
<b>Sent:</b> Tuesday, January 26, 2021 8:15 AM<br>
<b>To:</b> Chris Tetreault <</span><a href="mailto:ctetreau@quicinc.com"><span lang="EN-GB">ctetreau@quicinc.com</span></a><span lang="EN-GB">>;
</span><a href="mailto:llvm-dev@lists.llvm.org"><span lang="EN-GB">llvm-dev@lists.llvm.org</span></a><span lang="EN-GB"><br>
<b>Cc:</b> Sander De Smalen <</span><a href="mailto:Sander.DeSmalen@arm.com"><span lang="EN-GB">Sander.DeSmalen@arm.com</span></a><span lang="EN-GB">>; Paul Walker <</span><a href="mailto:Paul.Walker@arm.com"><span lang="EN-GB">Paul.Walker@arm.com</span></a><span lang="EN-GB">>;
Eli Friedman <</span><a href="mailto:efriedma@quicinc.com"><span lang="EN-GB">efriedma@quicinc.com</span></a><span lang="EN-GB">>;
</span><a href="mailto:cameron.mcinally@nyu.edu"><span lang="EN-GB">cameron.mcinally@nyu.edu</span></a><span lang="EN-GB"><br>
<b>Subject:</b> [EXT] RE: [RFC] Introduce a new stepvector operation<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Hi Chris,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">I’ve been following the discussions between you and Cameron and just so I understand<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">things correctly it looks like you’re proposing a new way of writing vector literals in IR<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">where the start and stride are determined from the first two values, i.e. <1, 3, …><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">has a start of 1 and stride of 2. I quite like the idea of a vector literal, but are you<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">proposing that internally in C++ we have some sort of ConstantStepVector that contains<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">a start/stride pair? Or when parsing this vector literal do you expect us to internally<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">represent this as something like:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">splat(1) + 2 * stepvector<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">where stepvector would be fixed as <0, 1, 2, 3, …>?<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">When emitting LLVM IR with something like “clang -S -emit-llvm” would you also<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">expect to see these vector literals being emitted too? I’m just thinking about how<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">this would look in vectorised code, for example normally when vectorising an<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">induction variable we’d see something like this:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">vector.ph:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">…<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">vector.body:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> %vec.ind = phi <4 x i32> [ <i32 0, i32 1, i32 2, i32 3>, %vector.ph ], …<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Are you suggesting the vector literal would be created in it’s own statement<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">in the preheader, or directly as a constant like before:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">vector.body:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> %vec.ind = phi <4 x i32> [ <i32 0, i32 1, …>, %vector.ph ], …<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Kind Regards,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">David.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span lang="EN-GB">From:</span></b><span lang="EN-GB"> Chris Tetreault <</span><a href="mailto:ctetreau@quicinc.com"><span lang="EN-GB">ctetreau@quicinc.com</span></a><span lang="EN-GB">>
<br>
<b>Sent:</b> 20 January 2021 21:33<br>
<b>To:</b> David Sherwood <</span><a href="mailto:David.Sherwood@arm.com"><span lang="EN-GB">David.Sherwood@arm.com</span></a><span lang="EN-GB">>;
</span><a href="mailto:llvm-dev@lists.llvm.org"><span lang="EN-GB">llvm-dev@lists.llvm.org</span></a><span lang="EN-GB"><br>
<b>Cc:</b> Sander De Smalen <</span><a href="mailto:Sander.DeSmalen@arm.com"><span lang="EN-GB">Sander.DeSmalen@arm.com</span></a><span lang="EN-GB">>; Paul Walker <</span><a href="mailto:Paul.Walker@arm.com"><span lang="EN-GB">Paul.Walker@arm.com</span></a><span lang="EN-GB">>;
Eli Friedman <</span><a href="mailto:efriedma@quicinc.com"><span lang="EN-GB">efriedma@quicinc.com</span></a><span lang="EN-GB">><br>
<b>Subject:</b> RE: [RFC] Introduce a new stepvector operation<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">David,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> Thanks for writing this up. I’d just like to speak to some concerns I have regarding shufflevector. As many of us know, shufflevector takes two vectors and a constant vector of i32, and does stuff. The constant shuffle
mask can be scalable or fixed width. The shuffle mask is supposed to be an arbitrary constant vector, however for scalable vectors only zeroinitializer or undef are accepted. There are reasonable technical reasons for this state of affairs, but it reveals
an issue: we don't really handle constant scalable vectors very well. Surely there are other similar issues throughout the codebase, but this is one I struggle with regularly so it sticks out in my mind.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> However, we probably want to be able to use the stepvector in shufflevector. For instance, if we had a stepvector literal, then we could implement vector concatenation in terms of shufflevector:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-family:"Courier New"">%a_concat_b = shufflevector <4 x i16> %a, <4 x i16> %b, <8 x i32> stepvector</span><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> In fact, a lot of useful shuffles can be implemented in terms of stepvector multiplied or added to some constants. Pulling from Eli's list in
</span><a href="https://lists.llvm.org/pipermail/llvm-dev/2020-January/138762.html">https://lists.llvm.org/pipermail/llvm-dev/2020-January/138762.html</a><span lang="EN-GB">, I can see:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">“<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span><span lang="EN-GB" style="font-family:"Courier New"">%result = shufflevector <vscale x 4 x i32> %v1, <vscale x 4 x i32> %v2, SHUFFLE_NAME</span><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> SHUFFLE_NAME can be one of the following (with examples of the equivalent <4 x i32> shuffles):<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> concat - Concatenate the two operands (<0, 1, 2, 3, 4, 5, 6, 7>) -> see above<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> split_low - Return the low half of the first operand (<0, 1>) -> stepvector of type <vscale x n/2 x i32><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> split_high - Return the high half of the first operand (<2, 3>) -> (stepvector + splat(n/2)) of type <vscale x n/2 x i32><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> zip_low - Zip together the low halves of the two operands (<0, 4, 1, 5>)<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> zip_high - Zip together the high halves of the two operands (<2, 6, 3, 7>)<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> unzip_even - Unzip the even elements of the two operands (<0, 2, 4, 6>) (stepvector + stepvector) of type <vscale x n x i32><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> unzip_odd - unzip the odd elements of the two operands (<1, 3, 5, 7>) (stepvector + stepvector + splat(1)) of type <vscale x n x i32><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">“<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> Unfortunately, all of these cannot be done because shufflevector only supports scalable undef or zeroinitializer. In order to support these cases, we would need to extend shufflevector to support stepvector (for concat),
and arbitrary constant expressions for the rest. Supporting stepvector might not be so hard with the current scheme: if the shuffle is scalable, and the mask is <0, 1, ..., n - 1>, then the input mask was a scalable stepvector. However, I think this illustrates
my proposal: <b>vector pattern literals</b>. They could look like this in IR:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span><b><span lang="EN-GB" style="font-family:"Courier New""><0, 1, ...></span></b><span lang="EN-GB"> ; stepvector<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> This is also more flexible, because it enables lots of other scalable vector literals:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span><span lang="EN-GB" style="font-family:"Courier New""><7, 7, ...></span><span lang="EN-GB"> ; splat(7) without writing that horrid insertelement/shufflevector thing<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span><span lang="EN-GB" style="font-family:"Courier New""><0, 2, ...></span><span lang="EN-GB"> ; unzip_even mask<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span><span lang="EN-GB" style="font-family:"Courier New""><1, 3, ...></span><span lang="EN-GB"> ; unzip_odd mask<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> The implementation for shufflevector would be straightforward because the mask for the two currently supported cases of zeroinitializer and undef (<0, 0, ...> <=> zeroinitializer and <undef, undef, ...> <=> undef)
already follow the proposed scheme. This could also have the side benefits of making some IR easier to read (for very wide vectors, the fixed width stepvector could be more than 80 columns wide), and might result in efficiency gains in the compiler (don't
need to walk a very wide vector to see if it is a stepvector; can just canonicalize <0, 1, 2, 3, 4, 5, 6, 7, ..., 2048> once to ConstantPatternVector(0, 1)).<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> Sorry for rambling. I think I’ve personally come around to the idea that a constant would be good. However, a more flexible constant would be best if we’re going to use it to add a bunch of special cases to the codebase.
Most special cases for scalable undef and zeroinitializer can be replaced with equivalent code that also handles vector pattern literals.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Thanks,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> Christopher Tetreault<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span lang="EN-GB">From:</span></b><span lang="EN-GB"> David Sherwood <</span><a href="mailto:David.Sherwood@arm.com">David.Sherwood@arm.com</a><span lang="EN-GB">>
<br>
<b>Sent:</b> Wednesday, January 20, 2021 8:04 AM<br>
<b>To:</b> </span><a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><span lang="EN-GB"><br>
<b>Cc:</b> Sander De Smalen <</span><a href="mailto:Sander.DeSmalen@arm.com">Sander.DeSmalen@arm.com</a><span lang="EN-GB">>; Paul Walker <</span><a href="mailto:Paul.Walker@arm.com">Paul.Walker@arm.com</a><span lang="EN-GB">>; Chris Tetreault <</span><a href="mailto:ctetreau@quicinc.com">ctetreau@quicinc.com</a><span lang="EN-GB">><br>
<b>Subject:</b> [EXT] [RFC] Introduce a new stepvector operation<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">Hi,</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">As part of adding support for scalable vectorization we need to update llvm::InnerLoopVectorizer::getStepVector for scalable vectors. Currently
this just returns a constant vector with the sequence <0, 1, 2, 3, ..>, however this assumes we are using fixed length vectors. For scalable vectors we need an operation that does the same thing, but without having to explicitly initalise all the elements.
Any new stepvector operation we provide could also be used for fixed length vectors too if desired.</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">I believe the desirable properties of the operation should be:</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">1. The operation requires no arguments and simply returns a vector with the numeric sequence <0, 1, 2, …></span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">2. For types with a large number of elements, e.g. <vscale x 32 x i8> (vscale = 16), there is the possibility of the sequence value exceeding the
limit of the type midway through the vector. In such cases we define the operation such that those elements are undefined or poison values.</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">A simple ‘stepvector’ operation (however we choose to implement it) with the properties described above can then be used together with additional
‘mul’ and ‘add’ instructions to create any arbitrary linear sequence, i.e. <0, 2, 4, 6, …> or <1, 3, 5, 7, …></span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">The first possible implementation with the properties as described above involves using a new llvm.stepvector() intrinsic with no arguments that
simply returns a vector sequence <0, 1, 2, …> of the requested type, i.e.</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> declare <vscale x 4 x i32> @llvm.stepvector.nxv4i32()</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">Introducing a new intrinsic is simple to implement and we can easily come up with an appropriate cost model – cheap for fixed width vectors or
scalable vectors using SVE where we have the ‘index’ instruction.</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">However, since such an intrinsic is effectively returning a constant vector sequence we could instead implement it using a new ‘stepvector’ constant
in a similar way to how ‘zeroinitializer’ works. This would be done using a new ConstantStepVector class similar to ConstantAggregateZero and would return a vector with the numeric sequence <0, 1, 2, …>. The main advantages of using a constant over an intrinsic
are:</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">1. It is easy to write tests in LLVM IR since ‘stepvector’ would work in the same way as ‘zeroinitializer’, i.e. “%1 = add <4 x i32> %0, stepvector”</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">2. Creation of the node is easy with the simple interface:</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> static Constant *ConstantStepVector::get(Type Ty)</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">3. It is easy to do optimisations, e.g. CSE, and pattern matching in IR.</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">The main disadvantages are:</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">1. A scalable constant cannot be represented as well in the .data section, although we can still create a constant based on the architectural maximum
for vscale. It’s worth pointing out that this problem also exists for zeroinitializer too – we’re just more likely to have cheap instructions to do the job.</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">2. Harder to fit into the cost model due to it being a constant.</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">3. There are some concerns that we might then have to support stepvector as a constant in the shufflevector operation too and that it should be
restricted to zeroinitializer only.</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">Any thoughts or feedback you have would be much appreciated!</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">Kind Regards,</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB" style="font-family:"Arial",sans-serif;color:black">David Sherwood.</span><span lang="EN-GB"><o:p></o:p></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span lang="EN-GB"> <o:p></o:p></span></p>
</div>
</body>
</html>