<div dir="ltr">I think that you're interested in a more general tutorial on how to vectorize code. I'm sorry I'm going to plug in my own articles [1] [2], but I've just tried to write a short version here and I basically almost rewrote them so there was<div>no point. For your case, I'd read at least the first half of "Residual Iterations" from Part 1 and most of part 2. The concept of residual iterations and reductions is something you'll see over and over and it happens</div><div>in your example too. Let me explain the use of shufflevector pretty quick and then I'll explain some specifics in your example. Also, before we move any further, I recommend that we turn off loop unrolling in your</div><div>example because it doesn't add educational value and just clutters the code, so here's your updated version [3].<br><div><br></div><div>--- Shufflevector ---</div><div><br></div><div>If you are not sure whether you understand what the instruction alone does, let me know. You can also play with this LLVM IR [4]. I recommend that you _run_ this code and change the mask in line 24.</div><div>The reason it's used in your example (see [3]) is because the compiler wants to create a vector which has `arr[0]` (referring to the C++ entity) in all its lanes. In line 4 (see [2]) it's loaded into %0, in line 17 it inserts</div><div>it only to the 0th (first) lane of a vector (and for the time being, we don't care about the other lanes which is why the first arg to `insertelement` is `poison`) and in line 18, it shuffles the value. The shuffle mask is the vector [0, 0, 0, 0]</div><div>(in short, zeroinitializer) which means in the 0th lane of the _result_ vector (%minmax.ident.splat) insert the value of the 0th lane of the _input_ vector (%minmax.ident.splatinsert). In the 1st lane of the _result_</div><div>vector, insert the value of the 0th lane of the _input_ vector etc. So, all lanes of the result vector get the 0th lane of the input vector.</div><div><br></div><div>--- Residual Iterations ---</div><div><br></div><div><div>Assuming that you have understood the use of residual iterations, let's see where it happens in your example. First of all, notice that in `entry`, there is a check whether `n` is bigger than 1, because if it's not, there are no</div><div>iterations to do at all and in this case, the result, i.e., `max`, is `arr[0]`, which is why it's loaded so early. Check the phi at line 45. Then, if we make it to `for.body.preheader`, there is a check whether we have at least</div><div>4 iterations (the fact that this loop starts from one makes the computations somewhat more complicated but not a lot). Because if we don't, then there's no point going into the vectorized version. Then, skipping what the vectorized</div><div>code does exactly for now (but check how the iteration count is rounded down to the nearest multiple of 4 in line 15), check that _after_ the vectorized code, the flow moves to `middle.block`,</div><div>which essentially checks whether there are any more iterations to do and if so, jumps to the serial version of the loop (this is where the residual iterations happen).</div></div><div><br></div><div>--- Reduction ---</div><div><br></div><div>In the article, I explain reductions using accumulation as an example, but in your example there's another reduction, namely, finding the maximum element. Notice that this is also a reduction: new_value = max_of(old_value, data).</div><div>The reduction variable (acting as both old and new value) is `max` in your example. The operation is max_of and the continuously new data is arr[i].</div><div><br></div><div>Finding the maximum element is a commutative operation. For instance, to find the maximum element among 4, you can split them in two pairs _any_ way you want, find the maximum of each pair _independently_</div><div>of the other pair (those two maximums are partial results and since their computation is independent of each other, it can be done in parallel), and finally find the maximum among these two maximums.</div><div><br></div><div>What happens in the vectorized code is that each lane finds a partial maximum. In line 27 it loads 4 elements and in the next two lines, it "compares" them with the previous 4 elements (%vec.phi, which keeps the 4 partial maximums which are updated</div><div>in every iteration). It computes a vector which has 4 maximums, one for each pair of lanes (between the new 4 elements in %wide.load, in %wide.load, and %vec.phi). You might want to run an example in paper to see the effect. Consider that you want to compute</div><div>the maximum of 9 numbers, in this order: 2, 10, 7, 3, 1, 8, 9, 11, 4</div><div><br></div><div>First, you get 2 (arr[0]) and broadcast it in a vector: <2, 2, 2, 2>. This is the starting value of %vec.phi. Then, you load 4 values: %wide.load = <10, 7, 3, 1></div><div>Then, you do an element-wise comparison of the two and for each pair of lanes, you keep the maximum. In this case, 10 > 2, 7 > 2, 3 > 2 but 1 < 2. So, %5 = <10, 7, 3, 2>, which becomes the new %vec.phi.</div><div>Next iteration, you load another 4: %wide.load = <8, 9, 11, 4> and you compare with (the new) %vec.phi: 8 < 10, 9 > 7, 11 > 3, 4 > 2. So, %5 = <10, 9, 11, 4>. Now, you have computed 4 partial maximums</div><div>and you only need to find the maximum among those 4 to find the total maximum. That happens in line 35 and you're done.</div><div><br></div><div>Hope this helps! Let me know if there are any questions.</div><div><br></div><div>Best,</div><div>Stefanos</div><div><br></div><div>[1] <a href="http://users.uoa.gr/~sdi1600105/performance/a-beginners-guide-to-vectorization-by-hand-part-1.html" target="_blank">http://users.uoa.gr/~sdi1600105/performance/a-beginners-guide-to-vectorization-by-hand-part-1.html</a></div><div>[2] <a href="http://users.uoa.gr/~sdi1600105/performance/a-beginners-guide-to-vectorization-by-hand-part-2.html" target="_blank">http://users.uoa.gr/~sdi1600105/performance/a-beginners-guide-to-vectorization-by-hand-part-2.html</a></div><div>[3] <a href="https://godbolt.org/z/nMe9a6YWa" target="_blank">https://godbolt.org/z/nMe9a6YWa</a></div><div>[4] <a href="https://godbolt.org/z/Wf9fTq53G" target="_blank">https://godbolt.org/z/Wf9fTq53G</a></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Δευ, 7 Ιουν 2021 στις 8:49 π.μ., ο/η Craig Topper <<a href="mailto:craig.topper@gmail.com" target="_blank">craig.topper@gmail.com</a>> έγραψε:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Shufflevector is a powerful instruction that can be used to copy a scalar to every elements of a vector, concatenate smaller vectors into a larger vector, rearrange elements one or two vectors, etc. Without example code I can't say for sure what the use of shufflevector in your case is for.<div><br clear="all"><div><div dir="ltr">~Craig</div></div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Jun 6, 2021 at 10:44 PM Sudakshina Dutta <<a href="mailto:sudakshina@iitgoa.ac.in" target="_blank">sudakshina@iitgoa.ac.in</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto">Dear Craig,<div dir="auto"><br></div><div dir="auto">Thanks for your reply. It seems the control flow of the vectorized program is very different from that of the source code. Is there any document describing difference in control flow, the reason for using shufflevector, etc ?</div><div dir="auto"><br></div><div dir="auto">Sudakshina </div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, 7 Jun 2021, 07:41 Craig Topper, <<a href="mailto:craig.topper@gmail.com" target="_blank">craig.topper@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">There's some notes here <a href="https://llvm.org/docs/Vectorizers.html" rel="noreferrer" target="_blank">https://llvm.org/docs/Vectorizers.html</a> but I didn't look too closely at it.  If you compile with -fno-discard-values names or use a debug build, some of the basic blocks will be named similar to the CFG diagram in this section <a href="https://llvm.org/docs/Vectorizers.html#epilogue-vectorization" rel="noreferrer" target="_blank">https://llvm.org/docs/Vectorizers.html#epilogue-vectorization</a> <div><br></div><div><div><div dir="ltr">~Craig</div></div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Jun 6, 2021 at 7:04 PM Sudakshina Dutta via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" rel="noreferrer" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Dear Stefanos,</div><div><br></div><div>I want to understand how the generated code works. For example, the code that I generated using -Rpass=loop-vectorize -Rpass-analysis=loop-vectorize has many shufflevector and other instructions. I wanted to have a document (if there exists any) where an example on loop-vectorization is done with some explanation on the workflow of the code.</div><div><br></div><div>Thanks,</div><div>Sudakshina<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Jun 7, 2021 at 7:03 AM Stefanos Baziotis <<a href="mailto:stefanos.baziotis@gmail.com" rel="noreferrer" target="_blank">stefanos.baziotis@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr">Hi Sudakshina,<div><br></div><div>First, it helps if you can put your code in a godbolt snippet, like this [1]. It helps people in multiple ways (e.g., they don't have to download files, they can see exactly what cmd arguments you used, they can</div><div>tweak the cmd arguments without having LLVM on their machine etc.).</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">Is there any comprehensive tutorial/document to understand generated instructions or the semantics of the vectorized code ?</blockquote><div><br></div><div>This is quite generic, what is more specifically that you want to understand? Do you want to understand what each individual instruction does? Do you maybe understand that but</div><div>you don't know what is the general method to generate, let's say by hand, vectorized code (or more specifically, branching vectorized code). Or maybe, you want to understand</div><div>how _LLVM_ generates this code, i.e., the inner workings of the vectorization passes.</div><div><br></div><div>Best,</div><div>Stefanos</div><div><br></div><div>[1] <a href="https://godbolt.org/z/8eKqnrMPn" rel="noreferrer" target="_blank">https://godbolt.org/z/8eKqnrMPn</a><br></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Κυρ, 6 Ιουν 2021 στις 6:17 π.μ., ο/η Sudakshina Dutta via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" rel="noreferrer" target="_blank">llvm-dev@lists.llvm.org</a>> έγραψε:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Dear all,</div><div><br></div><div>Greetings. I have generated a vectorized code from a C source file (attached). Is there any comprehensive tutorial/document to understand generated instructions or the semantics of the vectorized code ?</div><div><br></div><div>Thanks,</div><div>Sudakshina<br></div></div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" rel="noreferrer" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>
</blockquote></div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" rel="noreferrer" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>
</blockquote></div>
</blockquote></div>
</blockquote></div>