docs/Vectorizers.rst

   1 ==========================
   2 Auto-Vectorization in LLVM
   3 ==========================
   4
   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.
  11
  12 The Loop Vectorizer
  13 ===================
  14
  15 LLVM’s Loop Vectorizer is now available and will be useful for many people.
  16 It is not enabled by default, but can be enabled through clang using the
  17 command line flag:
  18
  19 .. code-block:: console
  20
  21    $ clang -fvectorize file.c
  22
  23 We plan to enable the Loop Vectorizer by default as part of the LLVM 3.3 release.
  24
  25 Features
  26 ^^^^^^^^^
  27
  28 The LLVM Loop Vectorizer has a number of features that allow it to vectorize
  29 complex loops.
  30
  31 Loops with unknown trip count
  32 ------------------------------
  33
  34 The Loop Vectorizer supports loops with an unknown trip count.
  35 In the loop below, the iteration ``start`` and ``finish`` points are unknown,
  36 and the Loop Vectorizer has a mechanism to vectorize loops that do not start
  37 at zero. In this example, ‘n’ may not be a multiple of the vector width, and
  38 the vectorizer has to execute the last few iterations as scalar code. Keeping
  39 a scalar copy of the loop increases the code size.
  40
  41 .. code-block:: c++
  42
  43   void bar(float *A, float* B, float K, int start, int end) {
  44    for (int i = start; i < end; ++i)
  45      A[i] *= B[i] + K;
  46   }
  47
  48 Runtime Checks of Pointers
  49 --------------------------
  50
  51 In the example below, if the pointers A and B point to consecutive addresses,
  52 then it is illegal to vectorize the code because some elements of A will be
  53 written before they are read from array B.
  54
  55 Some programmers use the 'restrict' keyword to notify the compiler that the
  56 pointers are disjointed, but in our example, the Loop Vectorizer has no way of
  57 knowing that the pointers A and B are unique. The Loop Vectorizer handles this
  58 loop by placing code that checks, at runtime, if the arrays A and B point to
  59 disjointed memory locations. If arrays A and B overlap, then the scalar version
  60 of the loop is executed.
  61
  62 .. code-block:: c++
  63
  64   void bar(float *A, float* B, float K, int n) {
  65    for (int i = 0; i < n; ++i)
  66      A[i] *= B[i] + K;
  67   }
  68
  69
  70 Reductions
  71 --------------------------
  72
  73 In this example the ``sum`` variable is used by consecutive iterations of
  74 the loop. Normally, this would prevent vectorization, but the vectorizer can
  75 detect that ‘sum’ is a reduction variable. The variable ‘sum’ becomes a vector
  76 of integers, and at the end of the loop the elements of the array are added
  77 together to create the correct result. We support a number of different
  78 reduction operations, such as addition, multiplication, XOR, AND and OR.
  79
  80 .. code-block:: c++
  81
  82   int foo(int *A, int *B, int n) {
  83     unsigned sum = 0;
  84     for (int i = 0; i < n; ++i)
  85         sum += A[i] + 5;
  86     return sum;
  87   }
  88
  89 Inductions
  90 --------------------------
  91
  92 In this example the value of the induction variable ``i`` is saved into an
  93 array. The Loop Vectorizer knows to vectorize induction variables.
  94
  95 .. code-block:: c++
  96
  97   void bar(float *A, float* B, float K, int n) {
  98    for (int i = 0; i < n; ++i)
  99      A[i] = i;
 100   }
 101
 102 If Conversion
 103 --------------------------
 104
 105 The Loop Vectorizer is able to "flatten" the IF statement in the code and
 106 generate a single stream of instructions. The Loop Vectorizer supports any
 107 control flow in the innermost loop. The innermost loop may contain complex
 108 nesting of IFs, ELSEs and even GOTOs.
 109
 110 .. code-block:: c++
 111
 112   int foo(int *A, int *B, int n) {
 113     unsigned sum = 0;
 114     for (int i = 0; i < n; ++i)
 115       if (A[i] > B[i])
 116         sum += A[i] + 5;
 117     return sum;
 118   }
 119
 120 Pointer Induction Variables
 121 --------------------------
 122
 123 This example uses the "accumulate" function of the standard c++ library. This
 124 loop uses C++ iterators, which are pointers, and not integer indices.
 125 The Loop Vectorizer detects pointer induction variables and can vectorize
 126 this loop. This feature is important because many C++ programs use iterators.
 127
 128 .. code-block:: c++
 129
 130   int baz(int *A, int n) {
 131     return std::accumulate(A, A + n, 0);
 132   }
 133
 134 Reverse Iterators
 135 --------------------------
 136
 137 The Loop Vectorizer can vectorize loops that count backwards.
 138
 139 .. code-block:: c++
 140
 141   int foo(int *A, int *B, int n) {
 142     for (int i = n; i > 0; --i)
 143       A[i] +=1;
 144   }
 145
 146 Scatter / Gather
 147 --------------------------
 148
 149 The Loop Vectorizer can generate code diverging memory indices that result in
 150 scatter/gather memory accesses.
 151
 152 .. code-block:: c++
 153
 154   int foo(int *A, int *B, int n, int k) {
 155   for (int i = 0; i < n; ++i)
 156       A[i*7] += B[i*k];
 157   }
 158
 159 Vectorization of programs with Mixed Types
 160 --------------------------
 161
 162 The Loop Vectorizer can vectorize programs with mixed types. The Vectorizer
 163 cost model can estimate the cost of the type conversion and decide if
 164 vectorization is profitable.
 165
 166 .. code-block:: c++
 167
 168   int foo(int *A, char *B, int n, int k) {
 169   for (int i = 0; i < n; ++i)
 170       A[i] += 4 * B[i];
 171   }
 172
 173 Vectorization of function calls
 174 --------------------------
 175
 176 The Loop Vectorize can vectorize intrinsic math functions.
 177 See the table below for a list of these functions.
 178
 179 +-----+-----+---------+
 180 | pow | exp |  exp2   |
 181 +-----+-----+---------+
 182 | sin | cos |  sqrt   |
 183 +-----+-----+---------+
 184 | log |log2 |  log10  |
 185 +-----+-----+---------+
 186 |fabs |floor|  ceil   |
 187 +-----+-----+---------+
 188 |fma  |trunc|nearbyint|
 189 +-----+-----+---------+
 190
 191 The Basic Block Vectorizer
 192 ==========================
 193
 194 The Basic Block Vectorizer is not enabled by default, but it can be enabled
 195 through clang using the command line flag:
 196
 197 .. code-block:: console
 198
 199    $ clang -fslp-vectorize file.c
 200
 201 The goal of basic-block vectorization (a.k.a. superword-level parallelism) is
 202 to combine similar independent instructions within simple control-flow regions
 203 into vector instructions. Memory accesses, arithemetic operations, comparison
 204 operations and some math functions can all be vectorized using this technique
 205 (subject to the capabilities of the target architecture).
 206
 207 For example, the following function performs very similar operations on its
 208 inputs (a1, b1) and (a2, b2). The basic-block vectorizer may combine these
 209 into vector operations.
 210
 211 .. code-block:: c++
 212
 213   int foo(int a1, int a2, int b1, int b2) {
 214     int r1 = a1*(a1 + b1)/b1 + 50*b1/a1;
 215     int r2 = a2*(a2 + b2)/b2 + 50*b2/a2;
 216     return r1 + r2;
 217   }
 218
 219