Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 1 | ========================== |
| 2 | Auto-Vectorization in LLVM |
| 3 | ========================== |
| 4 | |
Sean Silva | 12ae515 | 2012-12-20 22:42:20 +0000 | [diff] [blame] | 5 | .. contents:: |
| 6 | :local: |
| 7 | |
Nadav Rotem | 3fe91a4 | 2013-04-15 22:21:25 +0000 | [diff] [blame] | 8 | LLVM has two vectorizers: The :ref:`Loop Vectorizer <loop-vectorizer>`, |
Nadav Rotem | 96e0b96 | 2013-04-15 22:11:07 +0000 | [diff] [blame] | 9 | which operates on Loops, and the :ref:`SLP Vectorizer |
Nadav Rotem | b5a8a90 | 2013-06-26 17:59:35 +0000 | [diff] [blame] | 10 | <slp-vectorizer>`. These vectorizers |
Sean Silva | 12ae515 | 2012-12-20 22:42:20 +0000 | [diff] [blame] | 11 | focus on different optimization opportunities and use different techniques. |
Nadav Rotem | 3fe91a4 | 2013-04-15 22:21:25 +0000 | [diff] [blame] | 12 | The SLP vectorizer merges multiple scalars that are found in the code into |
Nadav Rotem | b5a8a90 | 2013-06-26 17:59:35 +0000 | [diff] [blame] | 13 | vectors while the Loop Vectorizer widens instructions in loops |
| 14 | to operate on multiple consecutive iterations. |
Sean Silva | 12ae515 | 2012-12-20 22:42:20 +0000 | [diff] [blame] | 15 | |
| 16 | .. _loop-vectorizer: |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 17 | |
| 18 | The Loop Vectorizer |
| 19 | =================== |
| 20 | |
Nadav Rotem | 649a33e | 2012-12-19 18:04:44 +0000 | [diff] [blame] | 21 | Usage |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 22 | ----- |
Nadav Rotem | 649a33e | 2012-12-19 18:04:44 +0000 | [diff] [blame] | 23 | |
Nadav Rotem | df4381b | 2013-04-08 21:34:49 +0000 | [diff] [blame] | 24 | LLVM's Loop Vectorizer is now enabled by default for -O3. |
Nadav Rotem | 2f7ce45 | 2013-04-15 05:56:55 +0000 | [diff] [blame] | 25 | We plan to enable parts of the Loop Vectorizer on -O2 and -Os in future releases. |
Nadav Rotem | df4381b | 2013-04-08 21:34:49 +0000 | [diff] [blame] | 26 | The vectorizer can be disabled using the command line: |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 27 | |
| 28 | .. code-block:: console |
| 29 | |
Nadav Rotem | df4381b | 2013-04-08 21:34:49 +0000 | [diff] [blame] | 30 | $ clang ... -fno-vectorize file.c |
Nadav Rotem | 3e6da7e | 2012-12-19 18:02:36 +0000 | [diff] [blame] | 31 | |
Nadav Rotem | 4aa55bb | 2013-01-04 17:49:45 +0000 | [diff] [blame] | 32 | Command line flags |
| 33 | ^^^^^^^^^^^^^^^^^^ |
| 34 | |
| 35 | The loop vectorizer uses a cost model to decide on the optimal vectorization factor |
| 36 | and unroll factor. However, users of the vectorizer can force the vectorizer to use |
| 37 | specific values. Both 'clang' and 'opt' support the flags below. |
| 38 | |
| 39 | Users can control the vectorization SIMD width using the command line flag "-force-vector-width". |
| 40 | |
| 41 | .. code-block:: console |
| 42 | |
| 43 | $ clang -mllvm -force-vector-width=8 ... |
| 44 | $ opt -loop-vectorize -force-vector-width=8 ... |
| 45 | |
| 46 | Users can control the unroll factor using the command line flag "-force-vector-unroll" |
| 47 | |
| 48 | .. code-block:: console |
| 49 | |
| 50 | $ clang -mllvm -force-vector-unroll=2 ... |
| 51 | $ opt -loop-vectorize -force-vector-unroll=2 ... |
| 52 | |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 53 | Features |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 54 | -------- |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 55 | |
| 56 | The LLVM Loop Vectorizer has a number of features that allow it to vectorize |
| 57 | complex loops. |
| 58 | |
| 59 | Loops with unknown trip count |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 60 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 61 | |
| 62 | The Loop Vectorizer supports loops with an unknown trip count. |
| 63 | In the loop below, the iteration ``start`` and ``finish`` points are unknown, |
| 64 | and the Loop Vectorizer has a mechanism to vectorize loops that do not start |
Sean Silva | 68d5b27 | 2012-12-20 02:23:25 +0000 | [diff] [blame] | 65 | at zero. In this example, 'n' may not be a multiple of the vector width, and |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 66 | the vectorizer has to execute the last few iterations as scalar code. Keeping |
| 67 | a scalar copy of the loop increases the code size. |
| 68 | |
| 69 | .. code-block:: c++ |
| 70 | |
| 71 | void bar(float *A, float* B, float K, int start, int end) { |
Sean Silva | 9baa6e4 | 2012-12-20 22:47:41 +0000 | [diff] [blame] | 72 | for (int i = start; i < end; ++i) |
| 73 | A[i] *= B[i] + K; |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 74 | } |
| 75 | |
| 76 | Runtime Checks of Pointers |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 77 | ^^^^^^^^^^^^^^^^^^^^^^^^^^ |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 78 | |
| 79 | In the example below, if the pointers A and B point to consecutive addresses, |
| 80 | then it is illegal to vectorize the code because some elements of A will be |
| 81 | written before they are read from array B. |
| 82 | |
| 83 | Some programmers use the 'restrict' keyword to notify the compiler that the |
| 84 | pointers are disjointed, but in our example, the Loop Vectorizer has no way of |
| 85 | knowing that the pointers A and B are unique. The Loop Vectorizer handles this |
| 86 | loop by placing code that checks, at runtime, if the arrays A and B point to |
| 87 | disjointed memory locations. If arrays A and B overlap, then the scalar version |
Sean Silva | 689858b | 2012-12-20 22:59:36 +0000 | [diff] [blame] | 88 | of the loop is executed. |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 89 | |
| 90 | .. code-block:: c++ |
| 91 | |
| 92 | void bar(float *A, float* B, float K, int n) { |
Sean Silva | 9baa6e4 | 2012-12-20 22:47:41 +0000 | [diff] [blame] | 93 | for (int i = 0; i < n; ++i) |
| 94 | A[i] *= B[i] + K; |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 95 | } |
| 96 | |
| 97 | |
| 98 | Reductions |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 99 | ^^^^^^^^^^ |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 100 | |
Sean Silva | 689858b | 2012-12-20 22:59:36 +0000 | [diff] [blame] | 101 | In this example the ``sum`` variable is used by consecutive iterations of |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 102 | the loop. Normally, this would prevent vectorization, but the vectorizer can |
Sean Silva | 68d5b27 | 2012-12-20 02:23:25 +0000 | [diff] [blame] | 103 | detect that 'sum' is a reduction variable. The variable 'sum' becomes a vector |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 104 | of integers, and at the end of the loop the elements of the array are added |
Sean Silva | 689858b | 2012-12-20 22:59:36 +0000 | [diff] [blame] | 105 | together to create the correct result. We support a number of different |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 106 | reduction operations, such as addition, multiplication, XOR, AND and OR. |
| 107 | |
| 108 | .. code-block:: c++ |
| 109 | |
| 110 | int foo(int *A, int *B, int n) { |
| 111 | unsigned sum = 0; |
| 112 | for (int i = 0; i < n; ++i) |
Sean Silva | 689858b | 2012-12-20 22:59:36 +0000 | [diff] [blame] | 113 | sum += A[i] + 5; |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 114 | return sum; |
| 115 | } |
| 116 | |
Nadav Rotem | 2a92c10 | 2013-01-08 17:46:30 +0000 | [diff] [blame] | 117 | We support floating point reduction operations when `-ffast-math` is used. |
| 118 | |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 119 | Inductions |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 120 | ^^^^^^^^^^ |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 121 | |
| 122 | In this example the value of the induction variable ``i`` is saved into an |
| 123 | array. The Loop Vectorizer knows to vectorize induction variables. |
| 124 | |
| 125 | .. code-block:: c++ |
| 126 | |
| 127 | void bar(float *A, float* B, float K, int n) { |
Sean Silva | 9baa6e4 | 2012-12-20 22:47:41 +0000 | [diff] [blame] | 128 | for (int i = 0; i < n; ++i) |
| 129 | A[i] = i; |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 130 | } |
| 131 | |
| 132 | If Conversion |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 133 | ^^^^^^^^^^^^^ |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 134 | |
| 135 | The Loop Vectorizer is able to "flatten" the IF statement in the code and |
| 136 | generate a single stream of instructions. The Loop Vectorizer supports any |
| 137 | control flow in the innermost loop. The innermost loop may contain complex |
| 138 | nesting of IFs, ELSEs and even GOTOs. |
| 139 | |
| 140 | .. code-block:: c++ |
| 141 | |
| 142 | int foo(int *A, int *B, int n) { |
| 143 | unsigned sum = 0; |
| 144 | for (int i = 0; i < n; ++i) |
| 145 | if (A[i] > B[i]) |
| 146 | sum += A[i] + 5; |
| 147 | return sum; |
| 148 | } |
| 149 | |
| 150 | Pointer Induction Variables |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 151 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 152 | |
| 153 | This example uses the "accumulate" function of the standard c++ library. This |
| 154 | loop uses C++ iterators, which are pointers, and not integer indices. |
| 155 | The Loop Vectorizer detects pointer induction variables and can vectorize |
| 156 | this loop. This feature is important because many C++ programs use iterators. |
| 157 | |
| 158 | .. code-block:: c++ |
| 159 | |
| 160 | int baz(int *A, int n) { |
| 161 | return std::accumulate(A, A + n, 0); |
| 162 | } |
| 163 | |
| 164 | Reverse Iterators |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 165 | ^^^^^^^^^^^^^^^^^ |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 166 | |
| 167 | The Loop Vectorizer can vectorize loops that count backwards. |
| 168 | |
| 169 | .. code-block:: c++ |
| 170 | |
| 171 | int foo(int *A, int *B, int n) { |
| 172 | for (int i = n; i > 0; --i) |
| 173 | A[i] +=1; |
| 174 | } |
| 175 | |
| 176 | Scatter / Gather |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 177 | ^^^^^^^^^^^^^^^^ |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 178 | |
Nadav Rotem | f574b88 | 2013-01-03 01:47:02 +0000 | [diff] [blame] | 179 | The Loop Vectorizer can vectorize code that becomes a sequence of scalar instructions |
| 180 | that scatter/gathers memory. |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 181 | |
| 182 | .. code-block:: c++ |
| 183 | |
| 184 | int foo(int *A, int *B, int n, int k) { |
Sean Silva | 9baa6e4 | 2012-12-20 22:47:41 +0000 | [diff] [blame] | 185 | for (int i = 0; i < n; ++i) |
Sean Silva | 5e81633 | 2012-12-20 22:49:13 +0000 | [diff] [blame] | 186 | A[i*7] += B[i*k]; |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 187 | } |
| 188 | |
Nadav Rotem | af08627 | 2012-12-19 07:36:35 +0000 | [diff] [blame] | 189 | Vectorization of Mixed Types |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 190 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 191 | |
| 192 | The Loop Vectorizer can vectorize programs with mixed types. The Vectorizer |
| 193 | cost model can estimate the cost of the type conversion and decide if |
| 194 | vectorization is profitable. |
| 195 | |
| 196 | .. code-block:: c++ |
| 197 | |
| 198 | int foo(int *A, char *B, int n, int k) { |
Sean Silva | 9baa6e4 | 2012-12-20 22:47:41 +0000 | [diff] [blame] | 199 | for (int i = 0; i < n; ++i) |
Sean Silva | 5e81633 | 2012-12-20 22:49:13 +0000 | [diff] [blame] | 200 | A[i] += 4 * B[i]; |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 201 | } |
| 202 | |
Renato Golin | abafaba | 2013-02-23 13:25:41 +0000 | [diff] [blame] | 203 | Global Structures Alias Analysis |
| 204 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
| 205 | |
| 206 | Access to global structures can also be vectorized, with alias analysis being |
| 207 | used to make sure accesses don't alias. Run-time checks can also be added on |
| 208 | pointer access to structure members. |
| 209 | |
| 210 | Many variations are supported, but some that rely on undefined behaviour being |
| 211 | ignored (as other compilers do) are still being left un-vectorized. |
| 212 | |
| 213 | .. code-block:: c++ |
| 214 | |
| 215 | struct { int A[100], K, B[100]; } Foo; |
| 216 | |
| 217 | int foo() { |
| 218 | for (int i = 0; i < 100; ++i) |
| 219 | Foo.A[i] = Foo.B[i] + 100; |
| 220 | } |
| 221 | |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 222 | Vectorization of function calls |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 223 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 224 | |
| 225 | The Loop Vectorize can vectorize intrinsic math functions. |
| 226 | See the table below for a list of these functions. |
| 227 | |
| 228 | +-----+-----+---------+ |
| 229 | | pow | exp | exp2 | |
| 230 | +-----+-----+---------+ |
| 231 | | sin | cos | sqrt | |
| 232 | +-----+-----+---------+ |
| 233 | | log |log2 | log10 | |
| 234 | +-----+-----+---------+ |
| 235 | |fabs |floor| ceil | |
| 236 | +-----+-----+---------+ |
| 237 | |fma |trunc|nearbyint| |
| 238 | +-----+-----+---------+ |
Nadav Rotem | f7769e3 | 2012-12-26 06:03:35 +0000 | [diff] [blame] | 239 | | | | fmuladd | |
| 240 | +-----+-----+---------+ |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 241 | |
Benjamin Kramer | 19949d8 | 2013-02-28 19:33:46 +0000 | [diff] [blame] | 242 | The loop vectorizer knows about special instructions on the target and will |
| 243 | vectorize a loop containing a function call that maps to the instructions. For |
| 244 | example, the loop below will be vectorized on Intel x86 if the SSE4.1 roundps |
| 245 | instruction is available. |
| 246 | |
| 247 | .. code-block:: c++ |
| 248 | |
| 249 | void foo(float *f) { |
| 250 | for (int i = 0; i != 1024; ++i) |
| 251 | f[i] = floorf(f[i]); |
| 252 | } |
Nadav Rotem | f574b88 | 2013-01-03 01:47:02 +0000 | [diff] [blame] | 253 | |
| 254 | Partial unrolling during vectorization |
| 255 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
| 256 | |
| 257 | Modern processors feature multiple execution units, and only programs that contain a |
Nadav Rotem | 43f3928 | 2013-01-03 01:56:33 +0000 | [diff] [blame] | 258 | high degree of parallelism can fully utilize the entire width of the machine. |
Nadav Rotem | f574b88 | 2013-01-03 01:47:02 +0000 | [diff] [blame] | 259 | The Loop Vectorizer increases the instruction level parallelism (ILP) by |
| 260 | performing partial-unrolling of loops. |
| 261 | |
| 262 | In the example below the entire array is accumulated into the variable 'sum'. |
Nadav Rotem | 43f3928 | 2013-01-03 01:56:33 +0000 | [diff] [blame] | 263 | This is inefficient because only a single execution port can be used by the processor. |
Nadav Rotem | f574b88 | 2013-01-03 01:47:02 +0000 | [diff] [blame] | 264 | By unrolling the code the Loop Vectorizer allows two or more execution ports |
Nadav Rotem | 43f3928 | 2013-01-03 01:56:33 +0000 | [diff] [blame] | 265 | to be used simultaneously. |
Nadav Rotem | f574b88 | 2013-01-03 01:47:02 +0000 | [diff] [blame] | 266 | |
| 267 | .. code-block:: c++ |
| 268 | |
| 269 | int foo(int *A, int *B, int n) { |
| 270 | unsigned sum = 0; |
| 271 | for (int i = 0; i < n; ++i) |
| 272 | sum += A[i]; |
| 273 | return sum; |
| 274 | } |
| 275 | |
Nadav Rotem | 4aa55bb | 2013-01-04 17:49:45 +0000 | [diff] [blame] | 276 | The Loop Vectorizer uses a cost model to decide when it is profitable to unroll loops. |
| 277 | The decision to unroll the loop depends on the register pressure and the generated code size. |
Nadav Rotem | f574b88 | 2013-01-03 01:47:02 +0000 | [diff] [blame] | 278 | |
Nadav Rotem | 67a6ec8 | 2012-12-19 08:28:24 +0000 | [diff] [blame] | 279 | Performance |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 280 | ----------- |
Nadav Rotem | 67a6ec8 | 2012-12-19 08:28:24 +0000 | [diff] [blame] | 281 | |
Sean Silva | 689858b | 2012-12-20 22:59:36 +0000 | [diff] [blame] | 282 | This section shows the the execution time of Clang on a simple benchmark: |
Nadav Rotem | 0575429 | 2012-12-19 08:43:05 +0000 | [diff] [blame] | 283 | `gcc-loops <http://llvm.org/viewvc/llvm-project/test-suite/trunk/SingleSource/UnitTests/Vectorizer/>`_. |
Sean Silva | 689858b | 2012-12-20 22:59:36 +0000 | [diff] [blame] | 284 | This benchmarks is a collection of loops from the GCC autovectorization |
Nadav Rotem | 3e6da7e | 2012-12-19 18:02:36 +0000 | [diff] [blame] | 285 | `page <http://gcc.gnu.org/projects/tree-ssa/vectorization.html>`_ by Dorit Nuzman. |
Nadav Rotem | 67a6ec8 | 2012-12-19 08:28:24 +0000 | [diff] [blame] | 286 | |
Nadav Rotem | 6d1fc53 | 2012-12-20 00:03:36 +0000 | [diff] [blame] | 287 | 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. |
Sean Silva | 689858b | 2012-12-20 22:59:36 +0000 | [diff] [blame] | 288 | The Y-axis shows the time in msec. Lower is better. The last column shows the geomean of all the kernels. |
Nadav Rotem | 67a6ec8 | 2012-12-19 08:28:24 +0000 | [diff] [blame] | 289 | |
| 290 | .. image:: gcc-loops.png |
| 291 | |
Nadav Rotem | 13410a1 | 2013-01-04 19:00:42 +0000 | [diff] [blame] | 292 | And Linpack-pc with the same configuration. Result is Mflops, higher is better. |
| 293 | |
| 294 | .. image:: linpack-pc.png |
| 295 | |
Nadav Rotem | fc175d9 | 2013-04-15 05:53:23 +0000 | [diff] [blame] | 296 | .. _slp-vectorizer: |
Sean Silva | 12ae515 | 2012-12-20 22:42:20 +0000 | [diff] [blame] | 297 | |
Nadav Rotem | fc175d9 | 2013-04-15 05:53:23 +0000 | [diff] [blame] | 298 | The SLP Vectorizer |
| 299 | ================== |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 300 | |
Nadav Rotem | 649a33e | 2012-12-19 18:04:44 +0000 | [diff] [blame] | 301 | Details |
Sean Silva | 6241703 | 2012-12-20 02:40:45 +0000 | [diff] [blame] | 302 | ------- |
Nadav Rotem | 649a33e | 2012-12-19 18:04:44 +0000 | [diff] [blame] | 303 | |
Nadav Rotem | fc175d9 | 2013-04-15 05:53:23 +0000 | [diff] [blame] | 304 | The goal of SLP vectorization (a.k.a. superword-level parallelism) is |
Nadav Rotem | b5a8a90 | 2013-06-26 17:59:35 +0000 | [diff] [blame] | 305 | to combine similar independent instructions |
| 306 | into vector instructions. Memory accesses, arithmetic operations, comparison |
| 307 | operations, PHI-nodes, can all be vectorized using this technique. |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 308 | |
| 309 | For example, the following function performs very similar operations on its |
| 310 | inputs (a1, b1) and (a2, b2). The basic-block vectorizer may combine these |
| 311 | into vector operations. |
| 312 | |
| 313 | .. code-block:: c++ |
| 314 | |
Nadav Rotem | fc175d9 | 2013-04-15 05:53:23 +0000 | [diff] [blame] | 315 | void foo(int a1, int a2, int b1, int b2, int *A) { |
| 316 | A[0] = a1*(a1 + b1)/b1 + 50*b1/a1; |
| 317 | A[1] = a2*(a2 + b2)/b2 + 50*b2/a2; |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 318 | } |
| 319 | |
Nadav Rotem | b5a8a90 | 2013-06-26 17:59:35 +0000 | [diff] [blame] | 320 | The SLP-vectorizer processes the code bottom-up, across basic blocks, in search of scalars to combine. |
Nadav Rotem | 59f2af9 | 2012-12-19 07:22:24 +0000 | [diff] [blame] | 321 | |
Nadav Rotem | fc175d9 | 2013-04-15 05:53:23 +0000 | [diff] [blame] | 322 | Usage |
| 323 | ------ |
Nadav Rotem | a15dedb | 2013-04-14 07:42:25 +0000 | [diff] [blame] | 324 | |
Nadav Rotem | fc175d9 | 2013-04-15 05:53:23 +0000 | [diff] [blame] | 325 | The SLP Vectorizer is not enabled by default, but it can be enabled |
| 326 | through clang using the command line flag: |
Nadav Rotem | a15dedb | 2013-04-14 07:42:25 +0000 | [diff] [blame] | 327 | |
Nadav Rotem | fc175d9 | 2013-04-15 05:53:23 +0000 | [diff] [blame] | 328 | .. code-block:: console |
| 329 | |
| 330 | $ clang -fslp-vectorize file.c |
| 331 | |
Nadav Rotem | 3fe91a4 | 2013-04-15 22:21:25 +0000 | [diff] [blame] | 332 | LLVM has a second basic block vectorization phase |
Nadav Rotem | fc175d9 | 2013-04-15 05:53:23 +0000 | [diff] [blame] | 333 | which is more compile-time intensive (The BB vectorizer). This optimization |
| 334 | can be enabled through clang using the command line flag: |
| 335 | |
| 336 | .. code-block:: console |
| 337 | |
| 338 | $ clang -fslp-vectorize-aggressive file.c |
| 339 | |
Nadav Rotem | a15dedb | 2013-04-14 07:42:25 +0000 | [diff] [blame] | 340 | |
| 341 | The SLP vectorizer is in early development stages but can already vectorize |
| 342 | and accelerate many programs in the LLVM test suite. |
| 343 | |
| 344 | ======================= ============ |
| 345 | Benchmark Name Gain |
| 346 | ======================= ============ |
| 347 | Misc/flops-7 -32.70% |
| 348 | Misc/matmul_f64_4x4 -23.23% |
| 349 | Olden/power -21.45% |
| 350 | Misc/flops-4 -14.90% |
| 351 | ASC_Sequoia/AMGmk -13.85% |
| 352 | TSVC/LoopRerolling-flt -11.76% |
| 353 | Misc/flops-6 -9.70% |
| 354 | Misc/flops-5 -8.54% |
| 355 | Misc/flops -8.12% |
| 356 | TSVC/NodeSplitting-dbl -6.96% |
| 357 | Misc-C++/sphereflake -6.74% |
| 358 | Ptrdist/yacr2 -6.31% |
| 359 | ======================= ============ |
| 360 | |