<html>
<head>
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
</head>
<body>
<p>Just a thought on another approach.</p>
<p>Unless I'm missing something, a step vector is simply a prefix
sum over a constant vector. Do we have clean ways with scalable
vectors of representing those concepts? If we do, we don't need a
separate intrinsic. If we don't, we probably need them anyways?</p>
<p>Slightly more specifically:<br>
allones = broadcast 0<br>
sum = prefix_sum allones<br>
stepvec = sum - allones</p>
<p>Out of those, the only tricky one is the prefix sum. Have we
explored that?<br>
</p>
<p>Philip<br>
</p>
<div class="moz-cite-prefix">On 1/20/21 8:03 AM, David Sherwood via
llvm-dev wrote:<br>
</div>
<blockquote type="cite"
cite="mid:DBBPR08MB46792D011459C7F52B7F9A1B84A20@DBBPR08MB4679.eurprd08.prod.outlook.com">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<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 */
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;
font-weight:normal;
font-style:normal;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
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]-->
<div class="WordSection1">
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black">Hi,<o:p></o:p></span></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"><o:p> </o:p></span></p>
<p style="margin:0cm"><span
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><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black">I
believe the desirable properties of the operation should be:</span><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0cm"><span
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><o:p></o:p></p>
<p style="margin:0cm"><span
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><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0cm"><span
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><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0cm"><span
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><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"> declare
<vscale x 4 x i32> @llvm.stepvector.nxv4i32()</span><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0cm"><span
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><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0cm"><span
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><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0cm"><span
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><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black">2.
Creation of the node is easy with the simple interface:</span><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"> static
Constant *ConstantStepVector::get(Type Ty)</span><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black">3.
It is easy to do optimisations, e.g. CSE, and pattern
matching in IR.</span><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black">The
main disadvantages are:</span><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0cm"><span
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><o:p></o:p></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black">2.
Harder to fit into the cost model due to it being a
constant.<o:p></o:p></span></p>
<p style="margin:0cm"><span
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.<o:p></o:p></span></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"><o:p> </o:p></span></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"><o:p> </o:p></span></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black">Any
thoughts or feedback you have would be much appreciated!<o:p></o:p></span></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black"><o:p> </o:p></span></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black">Kind
Regards,<o:p></o:p></span></p>
<p style="margin:0cm"><span
style="font-family:"Arial",sans-serif;color:black">David
Sherwood.<o:p></o:p></span></p>
<p style="margin:0cm"><o:p> </o:p></p>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
</body>
</html>