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 LLVM Loop Vectorizer has a number of features that allow it to vectorize
44 Loops with unknown trip count
45 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
47 The Loop Vectorizer supports loops with an unknown trip count.
48 In the loop below, the iteration ``start`` and ``finish`` points are unknown,
49 and the Loop Vectorizer has a mechanism to vectorize loops that do not start
50 at zero. In this example, 'n' may not be a multiple of the vector width, and
51 the vectorizer has to execute the last few iterations as scalar code. Keeping
52 a scalar copy of the loop increases the code size.
56 void bar(float *A, float* B, float K, int start, int end) {
57 for (int i = start; i < end; ++i)
61 Runtime Checks of Pointers
62 ^^^^^^^^^^^^^^^^^^^^^^^^^^
64 In the example below, if the pointers A and B point to consecutive addresses,
65 then it is illegal to vectorize the code because some elements of A will be
66 written before they are read from array B.
68 Some programmers use the 'restrict' keyword to notify the compiler that the
69 pointers are disjointed, but in our example, the Loop Vectorizer has no way of
70 knowing that the pointers A and B are unique. The Loop Vectorizer handles this
71 loop by placing code that checks, at runtime, if the arrays A and B point to
72 disjointed memory locations. If arrays A and B overlap, then the scalar version
73 of the loop is executed.
77 void bar(float *A, float* B, float K, int n) {
78 for (int i = 0; i < n; ++i)
86 In this example the ``sum`` variable is used by consecutive iterations of
87 the loop. Normally, this would prevent vectorization, but the vectorizer can
88 detect that 'sum' is a reduction variable. The variable 'sum' becomes a vector
89 of integers, and at the end of the loop the elements of the array are added
90 together to create the correct result. We support a number of different
91 reduction operations, such as addition, multiplication, XOR, AND and OR.
95 int foo(int *A, int *B, int n) {
97 for (int i = 0; i < n; ++i)
105 In this example the value of the induction variable ``i`` is saved into an
106 array. The Loop Vectorizer knows to vectorize induction variables.
110 void bar(float *A, float* B, float K, int n) {
111 for (int i = 0; i < n; ++i)
118 The Loop Vectorizer is able to "flatten" the IF statement in the code and
119 generate a single stream of instructions. The Loop Vectorizer supports any
120 control flow in the innermost loop. The innermost loop may contain complex
121 nesting of IFs, ELSEs and even GOTOs.
125 int foo(int *A, int *B, int n) {
127 for (int i = 0; i < n; ++i)
133 Pointer Induction Variables
134 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
136 This example uses the "accumulate" function of the standard c++ library. This
137 loop uses C++ iterators, which are pointers, and not integer indices.
138 The Loop Vectorizer detects pointer induction variables and can vectorize
139 this loop. This feature is important because many C++ programs use iterators.
143 int baz(int *A, int n) {
144 return std::accumulate(A, A + n, 0);
150 The Loop Vectorizer can vectorize loops that count backwards.
154 int foo(int *A, int *B, int n) {
155 for (int i = n; i > 0; --i)
162 The Loop Vectorizer can vectorize code that becomes scatter/gather
167 int foo(int *A, int *B, int n, int k) {
168 for (int i = 0; i < n; ++i)
172 Vectorization of Mixed Types
173 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
175 The Loop Vectorizer can vectorize programs with mixed types. The Vectorizer
176 cost model can estimate the cost of the type conversion and decide if
177 vectorization is profitable.
181 int foo(int *A, char *B, int n, int k) {
182 for (int i = 0; i < n; ++i)
186 Vectorization of function calls
187 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
189 The Loop Vectorize can vectorize intrinsic math functions.
190 See the table below for a list of these functions.
192 +-----+-----+---------+
194 +-----+-----+---------+
196 +-----+-----+---------+
197 | log |log2 | log10 |
198 +-----+-----+---------+
200 +-----+-----+---------+
201 |fma |trunc|nearbyint|
202 +-----+-----+---------+
204 +-----+-----+---------+
209 This section shows the the execution time of Clang on a simple benchmark:
210 `gcc-loops <http://llvm.org/viewvc/llvm-project/test-suite/trunk/SingleSource/UnitTests/Vectorizer/>`_.
211 This benchmarks is a collection of loops from the GCC autovectorization
212 `page <http://gcc.gnu.org/projects/tree-ssa/vectorization.html>`_ by Dorit Nuzman.
214 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.
215 The Y-axis shows the time in msec. Lower is better. The last column shows the geomean of all the kernels.
217 .. image:: gcc-loops.png
221 The Basic Block Vectorizer
222 ==========================
227 The Basic Block Vectorizer is not enabled by default, but it can be enabled
228 through clang using the command line flag:
230 .. code-block:: console
232 $ clang -fslp-vectorize file.c
237 The goal of basic-block vectorization (a.k.a. superword-level parallelism) is
238 to combine similar independent instructions within simple control-flow regions
239 into vector instructions. Memory accesses, arithemetic operations, comparison
240 operations and some math functions can all be vectorized using this technique
241 (subject to the capabilities of the target architecture).
243 For example, the following function performs very similar operations on its
244 inputs (a1, b1) and (a2, b2). The basic-block vectorizer may combine these
245 into vector operations.
249 int foo(int a1, int a2, int b1, int b2) {
250 int r1 = a1*(a1 + b1)/b1 + 50*b1/a1;
251 int r2 = a2*(a2 + b2)/b2 + 50*b2/a2;