1 ==========================
2 Auto-Vectorization in LLVM
3 ==========================
5 LLVM has two vectorizers: The *Loop Vectorizer*, which operates on Loops,
6 and the *Basic Block Vectorizer*, which optimizes straight-line code. These
7 vectorizers focus on different optimization opportunities and use different
8 techniques. The BB vectorizer merges multiple scalars that are found in the
9 code into vectors while the Loop Vectorizer widens instructions in the
10 original loop to operate on multiple consecutive loop iterations.
18 LLVM’s Loop Vectorizer is now available and will be useful for many people.
19 It is not enabled by default, but can be enabled through clang using the
22 .. code-block:: console
24 $ clang -fvectorize -O3 file.c
26 If the ``-fvectorize`` flag is used then the loop vectorizer will be enabled
27 when running with ``-O3``, ``-O2``. When ``-Os`` is used, the loop vectorizer
28 will only vectorize loops that do not require a major increase in code size.
30 We plan to enable the Loop Vectorizer by default as part of the LLVM 3.3 release.
35 The LLVM Loop Vectorizer has a number of features that allow it to vectorize
38 Loops with unknown trip count
39 ------------------------------
41 The Loop Vectorizer supports loops with an unknown trip count.
42 In the loop below, the iteration ``start`` and ``finish`` points are unknown,
43 and the Loop Vectorizer has a mechanism to vectorize loops that do not start
44 at zero. In this example, ‘n’ may not be a multiple of the vector width, and
45 the vectorizer has to execute the last few iterations as scalar code. Keeping
46 a scalar copy of the loop increases the code size.
50 void bar(float *A, float* B, float K, int start, int end) {
51 for (int i = start; i < end; ++i)
55 Runtime Checks of Pointers
56 --------------------------
58 In the example below, if the pointers A and B point to consecutive addresses,
59 then it is illegal to vectorize the code because some elements of A will be
60 written before they are read from array B.
62 Some programmers use the 'restrict' keyword to notify the compiler that the
63 pointers are disjointed, but in our example, the Loop Vectorizer has no way of
64 knowing that the pointers A and B are unique. The Loop Vectorizer handles this
65 loop by placing code that checks, at runtime, if the arrays A and B point to
66 disjointed memory locations. If arrays A and B overlap, then the scalar version
67 of the loop is executed.
71 void bar(float *A, float* B, float K, int n) {
72 for (int i = 0; i < n; ++i)
78 --------------------------
80 In this example the ``sum`` variable is used by consecutive iterations of
81 the loop. Normally, this would prevent vectorization, but the vectorizer can
82 detect that ‘sum’ is a reduction variable. The variable ‘sum’ becomes a vector
83 of integers, and at the end of the loop the elements of the array are added
84 together to create the correct result. We support a number of different
85 reduction operations, such as addition, multiplication, XOR, AND and OR.
89 int foo(int *A, int *B, int n) {
91 for (int i = 0; i < n; ++i)
97 --------------------------
99 In this example the value of the induction variable ``i`` is saved into an
100 array. The Loop Vectorizer knows to vectorize induction variables.
104 void bar(float *A, float* B, float K, int n) {
105 for (int i = 0; i < n; ++i)
110 --------------------------
112 The Loop Vectorizer is able to "flatten" the IF statement in the code and
113 generate a single stream of instructions. The Loop Vectorizer supports any
114 control flow in the innermost loop. The innermost loop may contain complex
115 nesting of IFs, ELSEs and even GOTOs.
119 int foo(int *A, int *B, int n) {
121 for (int i = 0; i < n; ++i)
127 Pointer Induction Variables
128 ---------------------------
130 This example uses the "accumulate" function of the standard c++ library. This
131 loop uses C++ iterators, which are pointers, and not integer indices.
132 The Loop Vectorizer detects pointer induction variables and can vectorize
133 this loop. This feature is important because many C++ programs use iterators.
137 int baz(int *A, int n) {
138 return std::accumulate(A, A + n, 0);
142 --------------------------
144 The Loop Vectorizer can vectorize loops that count backwards.
148 int foo(int *A, int *B, int n) {
149 for (int i = n; i > 0; --i)
156 The Loop Vectorizer can vectorize code that becomes scatter/gather
161 int foo(int *A, int *B, int n, int k) {
162 for (int i = 0; i < n; ++i)
166 Vectorization of Mixed Types
167 ----------------------------
169 The Loop Vectorizer can vectorize programs with mixed types. The Vectorizer
170 cost model can estimate the cost of the type conversion and decide if
171 vectorization is profitable.
175 int foo(int *A, char *B, int n, int k) {
176 for (int i = 0; i < n; ++i)
180 Vectorization of function calls
181 -------------------------------
183 The Loop Vectorize can vectorize intrinsic math functions.
184 See the table below for a list of these functions.
186 +-----+-----+---------+
188 +-----+-----+---------+
190 +-----+-----+---------+
191 | log |log2 | log10 |
192 +-----+-----+---------+
194 +-----+-----+---------+
195 |fma |trunc|nearbyint|
196 +-----+-----+---------+
201 This section shows the the execution time of Clang on a simple benchmark:
202 `gcc-loops <http://llvm.org/viewvc/llvm-project/test-suite/trunk/SingleSource/UnitTests/Vectorizer/>`_.
203 This benchmarks is a collection of loops from the GCC autovectorization
204 `page <http://gcc.gnu.org/projects/tree-ssa/vectorization.html>`_ by Dorit Nuzman.
206 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.
207 The Y-axis shows the time in msec. Lower is better. The last column shows the geomean of all the kernels.
209 .. image:: gcc-loops.png
211 The Basic Block Vectorizer
212 ==========================
217 The Basic Block Vectorizer is not enabled by default, but it can be enabled
218 through clang using the command line flag:
220 .. code-block:: console
222 $ clang -fslp-vectorize file.c
227 The goal of basic-block vectorization (a.k.a. superword-level parallelism) is
228 to combine similar independent instructions within simple control-flow regions
229 into vector instructions. Memory accesses, arithemetic operations, comparison
230 operations and some math functions can all be vectorized using this technique
231 (subject to the capabilities of the target architecture).
233 For example, the following function performs very similar operations on its
234 inputs (a1, b1) and (a2, b2). The basic-block vectorizer may combine these
235 into vector operations.
239 int foo(int a1, int a2, int b1, int b2) {
240 int r1 = a1*(a1 + b1)/b1 + 50*b1/a1;
241 int r2 = a2*(a2 + b2)/b2 + 50*b2/a2;