[llvm-dev] Document to understand vectorized code

Mon Jun 7 10:27:01 PDT 2021

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
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
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
example because it doesn't add educational value and just clutters the
code, so here's your updated version [3].

--- Shufflevector ---

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.
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
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]
(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_
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.

--- Residual Iterations ---

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
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
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
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`,
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).

--- Reduction ---

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).
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].

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_
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.

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
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
the maximum of 9 numbers, in this order: 2, 10, 7, 3, 1, 8, 9, 11, 4

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>
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.
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
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.

Hope this helps! Let me know if there are any questions.

Best,
Stefanos

[1]
http://users.uoa.gr/~sdi1600105/performance/a-beginners-guide-to-vectorization-by-hand-part-1.html
[2]
http://users.uoa.gr/~sdi1600105/performance/a-beginners-guide-to-vectorization-by-hand-part-2.html
[3] https://godbolt.org/z/nMe9a6YWa
[4] https://godbolt.org/z/Wf9fTq53G

Στις Δευ, 7 Ιουν 2021 στις 8:49 π.μ., ο/η Craig Topper <
craig.topper at gmail.com> έγραψε:

> 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.
>
> ~Craig
>
>
> On Sun, Jun 6, 2021 at 10:44 PM Sudakshina Dutta <sudakshina at iitgoa.ac.in>
> wrote:
>
>> Dear Craig,
>>
>> 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 ?
>>
>> Sudakshina
>>
>> On Mon, 7 Jun 2021, 07:41 Craig Topper, <craig.topper at gmail.com> wrote:
>>
>>> There's some notes here https://llvm.org/docs/Vectorizers.html 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
>>> https://llvm.org/docs/Vectorizers.html#epilogue-vectorization
>>>
>>> ~Craig
>>>
>>>
>>> On Sun, Jun 6, 2021 at 7:04 PM Sudakshina Dutta via llvm-dev <
>>> llvm-dev at lists.llvm.org> wrote:
>>>
>>>> Dear Stefanos,
>>>>
>>>> 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.
>>>>
>>>> Thanks,
>>>> Sudakshina
>>>>
>>>> On Mon, Jun 7, 2021 at 7:03 AM Stefanos Baziotis <
>>>> stefanos.baziotis at gmail.com> wrote:
>>>>
>>>>> Hi Sudakshina,
>>>>>
>>>>> 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
>>>>> tweak the cmd arguments without having LLVM on their machine etc.).
>>>>>
>>>>> Is there any comprehensive tutorial/document to understand generated
>>>>>> instructions or the semantics of the vectorized code ?
>>>>>
>>>>>
>>>>> 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
>>>>> 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
>>>>> how _LLVM_ generates this code, i.e., the inner workings of the
>>>>> vectorization passes.
>>>>>
>>>>> Best,
>>>>> Stefanos
>>>>>
>>>>> [1] https://godbolt.org/z/8eKqnrMPn
>>>>>
>>>>> Στις Κυρ, 6 Ιουν 2021 στις 6:17 π.μ., ο/η Sudakshina Dutta via
>>>>> llvm-dev <llvm-dev at lists.llvm.org> έγραψε:
>>>>>
>>>>>> Dear all,
>>>>>>
>>>>>> 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 ?
>>>>>>
>>>>>> Thanks,
>>>>>> Sudakshina
>>>>>> _______________________________________________
>>>>>> LLVM Developers mailing list
>>>>>> llvm-dev at lists.llvm.org
>>>>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>>
>>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210607/04487f4f/attachment.html>