<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Mon, Oct 10, 2016 at 1:14 PM, Renato Golin <span dir="ltr"><<a href="mailto:renato.golin@linaro.org" target="_blank">renato.golin@linaro.org</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"><span>On 10 October 2016 at 19:39, Alina Sbirlea <<a href="mailto:alina.sbirlea@gmail.com" target="_blank">alina.sbirlea@gmail.com</a>> wrote:<br>
> Now, for ARM archs Halide is currently generating explicit VSTn intrinsics,<br>
> with some of the patterns I described, and I found no reason why Halide<br>
> shouldn't generate a single shuffle, followed by a generic vector store and<br>
> rely on the interleaved access pass to generate the right intrinsic.<br>
<br>
</span>IIRC, the shuffle that unscrambles the interleaved pattern <0, 4, 8, 1<br>
...> -> <0, 1, 2 ...> is how the strided algorithm works, so that the<br>
back-end can match the patterns and emit a VSTn / STn because the<br>
access is "sequential" in a n-hop way.<br>
<br>
If the shuffle doesn't present itself in that way, the back-end<br>
doesn't match and you end up with a long list of VMOVs.<br></blockquote><div><br></div><div>That's what the patch addresses. It generalizes the algorithm to accept a more generic interleaved pattern and emit a VSTn/STn.<br>The access no longer needs to be sequential in an n-hop way, but a pattern amenable to the use of the store intrinsic:<br>[x, y, ... z, x+1, y+1, ...z+1, x+2, y+2, ...z+2, ...]</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">
<br>
Also, the vectorisers today make sure that the sequence is continuous<br>
and contiguous, which doesn't seem to be a hard requirement for<br>
Halide. I don't think there's a better reason than "we haven't thought<br>
about the general case yet".<br></blockquote><div><br></div><div>That's right, perhaps because Halide is not a regular vectorizer, which opens up new cases.</div><div>To give a bit more insight, here's a simple example of where the data is still continuous: [0 .. 32) , but it needs to be split to use multiple VSTns/STns. This is what Halide generates for aarch64:<span style="font-size:x-small"> </span></div><div><span style="font-size:x-small"> </span></div><font size="1"> %uglygep242243 = bitcast i8* %uglygep242 to <16 x i32>* <br> %114 = shufflevector <16 x i32> %112, <16 x i32> %113, <4 x i32> <i32 0, i32 1, i32 2, i32 3> <br> %115 = shufflevector <16 x i32> %112, <16 x i32> %113, <4 x i32> <i32 8, i32 9, i32 10, i32 11> <br> %116 = shufflevector <16 x i32> %112, <16 x i32> %113, <4 x i32> <i32 16, i32 17, i32 18, i32 19> <br> %117 = shufflevector <16 x i32> %112, <16 x i32> %113, <4 x i32> <i32 24, i32 25, i32 26, i32 27> <br> %118 = bitcast <16 x i32>* %uglygep242243 to <4 x i32>*<br> call void @llvm.aarch64.neon.st4.v4i32.<wbr>p0v4i32(<4 x i32> %114, <4 x i32> %115, <4 x i32> %116, <4 x i32> %117, <4 x i32>* %118)<br> %scevgep241 = getelementptr <16 x i32>, <16 x i32>* %uglygep242243, i64 1 <br> %119 = shufflevector <16 x i32> %112, <16 x i32> %113, <4 x i32> <i32 4, i32 5, i32 6, i32 7> <br> %120 = shufflevector <16 x i32> %112, <16 x i32> %113, <4 x i32> <i32 12, i32 13, i32 14, i32 15> <br> %121 = shufflevector <16 x i32> %112, <16 x i32> %113, <4 x i32> <i32 20, i32 21, i32 22, i32 23> <br> %122 = shufflevector <16 x i32> %112, <16 x i32> %113, <4 x i32> <i32 28, i32 29, i32 30, i32 31> <br> %123 = bitcast <16 x i32>* %scevgep241 to <4 x i32>*<br> call void @llvm.aarch64.neon.st4.v4i32.<wbr>p0v4i32(<4 x i32> %119, <4 x i32> %120, <4 x i32> %121, <4 x i32> %122, <4 x i32>* %123)</font><div><br></div><div>IMO, it makes sense to have Halide generate this instead:</div><font size="1">%114 = shufflevector <16 x i32> %112, <16 x i32> %113, <16 x i32> <i32 0, i32 8, i32 16, i32 24, i32 1, i32 9, i32 17, i32 25, i32 2, i32 10, i32 18, i32 26, i32 3, i32 11, i32 19, i32 27> <br>store <16 x i32> %114, <16 x i32>* %sunkaddr262<br> %115 = shufflevector <16 x i32> %112, <16 x i32> %113, <16 x i32> <i32 4, i32 12, i32 20, i32 28, i32 5, i32 13, i32 21, i32 29, i32 6, i32 14, i32 22, i32 30, i32 7, i32 15, i32 23, i32 31> <br>store <16 x i32> %115, <16 x i32>* %scevgep241</font></div><div class="gmail_quote">With the changes from the patch, this translates to the code above, and it is arch independent.</div><div class="gmail_quote"><br></div><div class="gmail_quote">AFAIK there isn't an LLVM pass going one step further to do such splits if given a single store.</div><div class="gmail_quote"><br></div><div class="gmail_quote">But, you're right that in general, the data is not necessarily continuous and contiguous in Halide, and I think the pass should address those cases as well.<br><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">
<br>
One way to test the back-end pattern matching is to emit textual IR<br>
and manually change it, removing the intrinsics, or changing the<br>
shuffles and see what happens after `opt`.<br></blockquote><div><br></div><div>Yes, I did that with some of the codes generated by Halide, it's what led to patch D23646 to extend the patterns. The new code being generated is the "expected" one.</div><div>Also, benchmarking some of their apps showed that llvm's pass (after the patch) does the job as well as the custom code generation they were using before. (Note, that Halide's code generation was written before the interleaved access pass was added, so it made sense at the time.)</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">
<span><br>
<br>
> Performance-wise, it is worth using the VSTns in the scenarios they<br>
> encounter, it's mostly a question of where they get generated.<br>
<br>
</span>I'm confused. AFAIK, VSTn is AArch32 while STn is AArch64, and for the<br>
one lane variant, the latency and throughput seem to be identical.<br></blockquote><div><br></div><div>That's right, the aim is to have llvm generate VSTn/STn depending on the arch.</div></div><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">Best,</div><div class="gmail_extra">Alina</div></div>