1 ==========================
2 Auto-Vectorization in LLVM
3 ==========================
8 LLVM has two vectorizers: The :ref:`Loop Vectorizer <loop-vectorizer>`,
9 which operates on Loops, and the :ref:`Basic Block Vectorizer
10 <bb-vectorizer>`, which optimizes straight-line code. These vectorizers
11 focus on different optimization opportunities and use different techniques.
12 The BB vectorizer merges multiple scalars that are found in the code into
13 vectors while the Loop Vectorizer widens instructions in the original loop
14 to operate on multiple consecutive loop iterations.
24 LLVM's Loop Vectorizer is now available and will be useful for many people.
25 It is not enabled by default, but can be enabled through clang using the
28 .. code-block:: console
30 $ clang -fvectorize -O3 file.c
32 If the ``-fvectorize`` flag is used then the loop vectorizer will be enabled
33 when running with ``-O3``, ``-O2``. When ``-Os`` is used, the loop vectorizer
34 will only vectorize loops that do not require a major increase in code size.
36 We plan to enable the Loop Vectorizer by default as part of the LLVM 3.3 release.
41 The loop vectorizer uses a cost model to decide on the optimal vectorization factor
42 and unroll factor. However, users of the vectorizer can force the vectorizer to use
43 specific values. Both 'clang' and 'opt' support the flags below.
45 Users can control the vectorization SIMD width using the command line flag "-force-vector-width".
47 .. code-block:: console
49 $ clang -mllvm -force-vector-width=8 ...
50 $ opt -loop-vectorize -force-vector-width=8 ...
52 Users can control the unroll factor using the command line flag "-force-vector-unroll"
54 .. code-block:: console
56 $ clang -mllvm -force-vector-unroll=2 ...
57 $ opt -loop-vectorize -force-vector-unroll=2 ...
62 The LLVM Loop Vectorizer has a number of features that allow it to vectorize
65 Loops with unknown trip count
66 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
68 The Loop Vectorizer supports loops with an unknown trip count.
69 In the loop below, the iteration ``start`` and ``finish`` points are unknown,
70 and the Loop Vectorizer has a mechanism to vectorize loops that do not start
71 at zero. In this example, 'n' may not be a multiple of the vector width, and
72 the vectorizer has to execute the last few iterations as scalar code. Keeping
73 a scalar copy of the loop increases the code size.
77 void bar(float *A, float* B, float K, int start, int end) {
78 for (int i = start; i < end; ++i)
82 Runtime Checks of Pointers
83 ^^^^^^^^^^^^^^^^^^^^^^^^^^
85 In the example below, if the pointers A and B point to consecutive addresses,
86 then it is illegal to vectorize the code because some elements of A will be
87 written before they are read from array B.
89 Some programmers use the 'restrict' keyword to notify the compiler that the
90 pointers are disjointed, but in our example, the Loop Vectorizer has no way of
91 knowing that the pointers A and B are unique. The Loop Vectorizer handles this
92 loop by placing code that checks, at runtime, if the arrays A and B point to
93 disjointed memory locations. If arrays A and B overlap, then the scalar version
94 of the loop is executed.
98 void bar(float *A, float* B, float K, int n) {
99 for (int i = 0; i < n; ++i)
107 In this example the ``sum`` variable is used by consecutive iterations of
108 the loop. Normally, this would prevent vectorization, but the vectorizer can
109 detect that 'sum' is a reduction variable. The variable 'sum' becomes a vector
110 of integers, and at the end of the loop the elements of the array are added
111 together to create the correct result. We support a number of different
112 reduction operations, such as addition, multiplication, XOR, AND and OR.
116 int foo(int *A, int *B, int n) {
118 for (int i = 0; i < n; ++i)
123 We support floating point reduction operations when `-ffast-math` is used.
128 In this example the value of the induction variable ``i`` is saved into an
129 array. The Loop Vectorizer knows to vectorize induction variables.
133 void bar(float *A, float* B, float K, int n) {
134 for (int i = 0; i < n; ++i)
141 The Loop Vectorizer is able to "flatten" the IF statement in the code and
142 generate a single stream of instructions. The Loop Vectorizer supports any
143 control flow in the innermost loop. The innermost loop may contain complex
144 nesting of IFs, ELSEs and even GOTOs.
148 int foo(int *A, int *B, int n) {
150 for (int i = 0; i < n; ++i)
156 Pointer Induction Variables
157 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
159 This example uses the "accumulate" function of the standard c++ library. This
160 loop uses C++ iterators, which are pointers, and not integer indices.
161 The Loop Vectorizer detects pointer induction variables and can vectorize
162 this loop. This feature is important because many C++ programs use iterators.
166 int baz(int *A, int n) {
167 return std::accumulate(A, A + n, 0);
173 The Loop Vectorizer can vectorize loops that count backwards.
177 int foo(int *A, int *B, int n) {
178 for (int i = n; i > 0; --i)
185 The Loop Vectorizer can vectorize code that becomes a sequence of scalar instructions
186 that scatter/gathers memory.
190 int foo(int *A, int *B, int n, int k) {
191 for (int i = 0; i < n; ++i)
195 Vectorization of Mixed Types
196 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
198 The Loop Vectorizer can vectorize programs with mixed types. The Vectorizer
199 cost model can estimate the cost of the type conversion and decide if
200 vectorization is profitable.
204 int foo(int *A, char *B, int n, int k) {
205 for (int i = 0; i < n; ++i)
209 Vectorization of function calls
210 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
212 The Loop Vectorize can vectorize intrinsic math functions.
213 See the table below for a list of these functions.
215 +-----+-----+---------+
217 +-----+-----+---------+
219 +-----+-----+---------+
220 | log |log2 | log10 |
221 +-----+-----+---------+
223 +-----+-----+---------+
224 |fma |trunc|nearbyint|
225 +-----+-----+---------+
227 +-----+-----+---------+
230 Partial unrolling during vectorization
231 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
233 Modern processors feature multiple execution units, and only programs that contain a
234 high degree of parallelism can fully utilize the entire width of the machine.
235 The Loop Vectorizer increases the instruction level parallelism (ILP) by
236 performing partial-unrolling of loops.
238 In the example below the entire array is accumulated into the variable 'sum'.
239 This is inefficient because only a single execution port can be used by the processor.
240 By unrolling the code the Loop Vectorizer allows two or more execution ports
241 to be used simultaneously.
245 int foo(int *A, int *B, int n) {
247 for (int i = 0; i < n; ++i)
252 The Loop Vectorizer uses a cost model to decide when it is profitable to unroll loops.
253 The decision to unroll the loop depends on the register pressure and the generated code size.
258 This section shows the the execution time of Clang on a simple benchmark:
259 `gcc-loops <http://llvm.org/viewvc/llvm-project/test-suite/trunk/SingleSource/UnitTests/Vectorizer/>`_.
260 This benchmarks is a collection of loops from the GCC autovectorization
261 `page <http://gcc.gnu.org/projects/tree-ssa/vectorization.html>`_ by Dorit Nuzman.
263 The chart below compares GCC-4.7, ICC-13, and Clang-SVN with and without loop vectorization at -O3, tuned for "corei7-avx", running on a Sandybridge iMac.
264 The Y-axis shows the time in msec. Lower is better. The last column shows the geomean of all the kernels.
266 .. image:: gcc-loops.png
268 And Linpack-pc with the same configuration. Result is Mflops, higher is better.
270 .. image:: linpack-pc.png
274 The Basic Block Vectorizer
275 ==========================
280 The Basic Block Vectorizer is not enabled by default, but it can be enabled
281 through clang using the command line flag:
283 .. code-block:: console
285 $ clang -fslp-vectorize file.c
290 The goal of basic-block vectorization (a.k.a. superword-level parallelism) is
291 to combine similar independent instructions within simple control-flow regions
292 into vector instructions. Memory accesses, arithemetic operations, comparison
293 operations and some math functions can all be vectorized using this technique
294 (subject to the capabilities of the target architecture).
296 For example, the following function performs very similar operations on its
297 inputs (a1, b1) and (a2, b2). The basic-block vectorizer may combine these
298 into vector operations.
302 int foo(int a1, int a2, int b1, int b2) {
303 int r1 = a1*(a1 + b1)/b1 + 50*b1/a1;
304 int r2 = a2*(a2 + b2)/b2 + 50*b2/a2;