491 lines · plain
1==========================2Auto-Vectorization in LLVM3==========================4 5.. contents::6 :local:7 8LLVM has two vectorizers: The :ref:`Loop Vectorizer <loop-vectorizer>`,9which operates on Loops, and the :ref:`SLP Vectorizer10<slp-vectorizer>`. These vectorizers11focus on different optimization opportunities and use different techniques.12The SLP vectorizer merges multiple scalars that are found in the code into13vectors while the Loop Vectorizer widens instructions in loops14to operate on multiple consecutive iterations.15 16Both the Loop Vectorizer and the SLP Vectorizer are enabled by default.17 18.. _loop-vectorizer:19 20The Loop Vectorizer21===================22 23Usage24-----25 26The Loop Vectorizer is enabled by default, but it can be disabled27through clang using the command line flag:28 29.. code-block:: console30 31 $ clang ... -fno-vectorize file.c32 33Command line flags34^^^^^^^^^^^^^^^^^^35 36The loop vectorizer uses a cost model to decide on the optimal vectorization factor37and unroll factor. However, users of the vectorizer can force the vectorizer to use38specific values. Both 'clang' and 'opt' support the flags below.39 40Users can control the vectorization SIMD width using the command line flag "-force-vector-width".41 42.. code-block:: console43 44 $ clang -mllvm -force-vector-width=8 ...45 $ opt -loop-vectorize -force-vector-width=8 ...46 47Users can control the unroll factor using the command line flag "-force-vector-interleave"48 49.. code-block:: console50 51 $ clang -mllvm -force-vector-interleave=2 ...52 $ opt -loop-vectorize -force-vector-interleave=2 ...53 54Pragma loop hint directives55^^^^^^^^^^^^^^^^^^^^^^^^^^^56 57The ``#pragma clang loop`` directive allows loop vectorization hints to be58specified for the subsequent for, while, do-while, or c++11 range-based for59loop. The directive allows vectorization and interleaving to be enabled or60disabled. Vector width as well as interleave count can also be manually61specified. The following example explicitly enables vectorization and62interleaving:63 64.. code-block:: c++65 66 #pragma clang loop vectorize(enable) interleave(enable)67 while(...) {68 ...69 }70 71The following example implicitly enables vectorization and interleaving by72specifying a vector width and interleaving count:73 74.. code-block:: c++75 76 #pragma clang loop vectorize_width(2) interleave_count(2)77 for(...) {78 ...79 }80 81See the Clang82`language extensions83<https://clang.llvm.org/docs/LanguageExtensions.html#extensions-for-loop-hint-optimizations>`_84for details.85 86Diagnostics87-----------88 89Many loops cannot be vectorized including loops with complicated control flow,90unvectorizable types, and unvectorizable calls. The loop vectorizer generates91optimization remarks which can be queried using command line options to identify92and diagnose loops that are skipped by the loop-vectorizer.93 94Optimization remarks are enabled using:95 96``-Rpass=loop-vectorize`` identifies loops that were successfully vectorized.97 98``-Rpass-missed=loop-vectorize`` identifies loops that failed vectorization and99indicates if vectorization was specified.100 101``-Rpass-analysis=loop-vectorize`` identifies the statements that caused102vectorization to fail. If in addition ``-fsave-optimization-record`` is103provided, multiple causes of vectorization failure may be listed (this behavior104might change in the future).105 106Consider the following loop:107 108.. code-block:: c++109 110 #pragma clang loop vectorize(enable)111 for (int i = 0; i < Length; i++) {112 switch(A[i]) {113 case 0: A[i] = i*2; break;114 case 1: A[i] = i; break;115 default: A[i] = 0;116 }117 }118 119The command line ``-Rpass-missed=loop-vectorize`` prints the remark:120 121.. code-block:: console122 123 no_switch.cpp:4:5: remark: loop not vectorized: vectorization is explicitly enabled [-Rpass-missed=loop-vectorize]124 125And the command line ``-Rpass-analysis=loop-vectorize`` indicates that the126switch statement cannot be vectorized.127 128.. code-block:: console129 130 no_switch.cpp:4:5: remark: loop not vectorized: loop contains a switch statement [-Rpass-analysis=loop-vectorize]131 switch(A[i]) {132 ^133 134To ensure line and column numbers are produced include the command line options135``-gline-tables-only`` and ``-gcolumn-info``. See the Clang `user manual136<https://clang.llvm.org/docs/UsersManual.html#options-to-emit-optimization-reports>`_137for details138 139Features140--------141 142The LLVM Loop Vectorizer has a number of features that allow it to vectorize143complex loops.144 145Loops with unknown trip count146^^^^^^^^^^^^^^^^^^^^^^^^^^^^^147 148The Loop Vectorizer supports loops with an unknown trip count.149In the loop below, the iteration ``start`` and ``finish`` points are unknown,150and the Loop Vectorizer has a mechanism to vectorize loops that do not start151at zero. In this example, 'n' may not be a multiple of the vector width, and152the vectorizer has to execute the last few iterations as scalar code. Keeping153a scalar copy of the loop increases the code size.154 155.. code-block:: c++156 157 void bar(float *A, float* B, float K, int start, int end) {158 for (int i = start; i < end; ++i)159 A[i] *= B[i] + K;160 }161 162Runtime Checks of Pointers163^^^^^^^^^^^^^^^^^^^^^^^^^^164 165In the example below, if the pointers A and B point to consecutive addresses,166then it is illegal to vectorize the code because some elements of A will be167written before they are read from array B.168 169Some programmers use the 'restrict' keyword to notify the compiler that the170pointers are disjointed, but in our example, the Loop Vectorizer has no way of171knowing that the pointers A and B are unique. The Loop Vectorizer handles this172loop by placing code that checks, at runtime, if the arrays A and B point to173disjointed memory locations. If arrays A and B overlap, then the scalar version174of the loop is executed.175 176.. code-block:: c++177 178 void bar(float *A, float* B, float K, int n) {179 for (int i = 0; i < n; ++i)180 A[i] *= B[i] + K;181 }182 183 184Reductions185^^^^^^^^^^186 187In this example the ``sum`` variable is used by consecutive iterations of188the loop. Normally, this would prevent vectorization, but the vectorizer can189detect that 'sum' is a reduction variable. The variable 'sum' becomes a vector190of integers, and at the end of the loop the elements of the array are added191together to create the correct result. We support a number of different192reduction operations, such as addition, multiplication, XOR, AND and OR.193 194.. code-block:: c++195 196 int foo(int *A, int n) {197 unsigned sum = 0;198 for (int i = 0; i < n; ++i)199 sum += A[i] + 5;200 return sum;201 }202 203We support floating point reduction operations when `-ffast-math` is used.204 205Inductions206^^^^^^^^^^207 208In this example the value of the induction variable ``i`` is saved into an209array. The Loop Vectorizer knows to vectorize induction variables.210 211.. code-block:: c++212 213 void bar(float *A, int n) {214 for (int i = 0; i < n; ++i)215 A[i] = i;216 }217 218If Conversion219^^^^^^^^^^^^^220 221The Loop Vectorizer is able to "flatten" the IF statement in the code and222generate a single stream of instructions. The Loop Vectorizer supports any223control flow in the innermost loop. The innermost loop may contain complex224nesting of IFs, ELSEs and even GOTOs.225 226.. code-block:: c++227 228 int foo(int *A, int *B, int n) {229 unsigned sum = 0;230 for (int i = 0; i < n; ++i)231 if (A[i] > B[i])232 sum += A[i] + 5;233 return sum;234 }235 236Pointer Induction Variables237^^^^^^^^^^^^^^^^^^^^^^^^^^^238 239This example uses the "accumulate" function of the standard c++ library. This240loop uses C++ iterators, which are pointers, and not integer indices.241The Loop Vectorizer detects pointer induction variables and can vectorize242this loop. This feature is important because many C++ programs use iterators.243 244.. code-block:: c++245 246 int baz(int *A, int n) {247 return std::accumulate(A, A + n, 0);248 }249 250Reverse Iterators251^^^^^^^^^^^^^^^^^252 253The Loop Vectorizer can vectorize loops that count backwards.254 255.. code-block:: c++256 257 void foo(int *A, int n) {258 for (int i = n; i > 0; --i)259 A[i] +=1;260 }261 262Scatter / Gather263^^^^^^^^^^^^^^^^264 265The Loop Vectorizer can vectorize code that becomes a sequence of scalar instructions266that scatter/gathers memory.267 268.. code-block:: c++269 270 void foo(int * A, int * B, int n) {271 for (intptr_t i = 0; i < n; ++i)272 A[i] += B[i * 4];273 }274 275In many situations the cost model will inform LLVM that this is not beneficial276and LLVM will only vectorize such code if forced with "-mllvm -force-vector-width=#".277 278Vectorization of Mixed Types279^^^^^^^^^^^^^^^^^^^^^^^^^^^^280 281The Loop Vectorizer can vectorize programs with mixed types. The Vectorizer282cost model can estimate the cost of the type conversion and decide if283vectorization is profitable.284 285.. code-block:: c++286 287 void foo(int *A, char *B, int n) {288 for (int i = 0; i < n; ++i)289 A[i] += 4 * B[i];290 }291 292Global Structures Alias Analysis293^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^294 295Access to global structures can also be vectorized, with alias analysis being296used to make sure accesses don't alias. Run-time checks can also be added on297pointer access to structure members.298 299Many variations are supported, but some that rely on undefined behaviour being300ignored (as other compilers do) are still being left un-vectorized.301 302.. code-block:: c++303 304 struct { int A[100], K, B[100]; } Foo;305 306 void foo() {307 for (int i = 0; i < 100; ++i)308 Foo.A[i] = Foo.B[i] + 100;309 }310 311Vectorization of function calls312^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^313 314The Loop Vectorizer can vectorize intrinsic math functions.315See the table below for a list of these functions.316 317+-----+-----+---------+318| pow | exp | exp2 |319+-----+-----+---------+320| sin | cos | sqrt |321+-----+-----+---------+322| log |log2 | log10 |323+-----+-----+---------+324|fabs |floor| ceil |325+-----+-----+---------+326|fma |trunc|nearbyint|327+-----+-----+---------+328| | | fmuladd |329+-----+-----+---------+330 331Note that the optimizer may not be able to vectorize math library functions332that correspond to these intrinsics if the library calls access external state333such as "errno". To allow better optimization of C/C++ math library functions,334use "-fno-math-errno".335 336The loop vectorizer knows about special instructions on the target and will337vectorize a loop containing a function call that maps to the instructions. For338example, the loop below will be vectorized on Intel x86 if the SSE4.1 roundps339instruction is available.340 341.. code-block:: c++342 343 void foo(float *f) {344 for (int i = 0; i != 1024; ++i)345 f[i] = floorf(f[i]);346 }347 348Many of these math functions are only vectorizable if the file has been built349with a specified target vector library that provides a vector implementation350of that math function. Using clang, this is handled by the "-fveclib" command351line option with one of the following vector libraries:352"Accelerate,libmvec,MASSV,SVML,SLEEF,Darwin_libsystem_m,ArmPL,AMDLIBM"353 354.. code-block:: console355 356 $ clang ... -fno-math-errno -fveclib=libmvec file.c357 358Partial unrolling during vectorization359^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^360 361Modern processors feature multiple execution units, and only programs that contain a362high degree of parallelism can fully utilize the entire width of the machine.363The Loop Vectorizer increases the instruction level parallelism (ILP) by364performing partial-unrolling of loops.365 366In the example below the entire array is accumulated into the variable 'sum'.367This is inefficient because only a single execution port can be used by the processor.368By unrolling the code the Loop Vectorizer allows two or more execution ports369to be used simultaneously.370 371.. code-block:: c++372 373 int foo(int *A, int n) {374 unsigned sum = 0;375 for (int i = 0; i < n; ++i)376 sum += A[i];377 return sum;378 }379 380The Loop Vectorizer uses a cost model to decide when it is profitable to unroll loops.381The decision to unroll the loop depends on the register pressure and the generated code size.382 383Epilogue Vectorization384^^^^^^^^^^^^^^^^^^^^^^385 386When vectorizing a loop, often a scalar remainder (epilogue) loop is necessary387to execute tail iterations of the loop if the loop trip count is unknown or it388does not evenly divide the vectorization and unroll factors. When the389vectorization and unroll factors are large, it's possible for loops with smaller390trip counts to end up spending most of their time in the scalar (rather than391the vector) code. In order to address this issue, the inner loop vectorizer is392enhanced with a feature that allows it to vectorize epilogue loops with a393vectorization and unroll factor combination that makes it more likely for small394trip count loops to still execute in vectorized code. The diagram below shows395the CFG for a typical epilogue vectorized loop with runtime checks. As396illustrated the control flow is structured in a way that avoids duplicating the397runtime pointer checks and optimizes the path length for loops that have very398small trip counts.399 400.. image:: epilogue-vectorization-cfg.png401 402Early Exit Vectorization403^^^^^^^^^^^^^^^^^^^^^^^^404 405When vectorizing a loop with a single early exit, the loop blocks following the406early exit are predicated and the vector loop will always exit via the latch.407If the early exit has been taken, the vector loop's successor block408(``middle.split`` below) branches to the early exit block via an intermediate409block (``vector.early.exit`` below). This intermediate block is responsible for410calculating any exit values of loop-defined variables that are used in the411early exit block. Otherwise, ``middle.block`` selects between the exit block412from the latch or the scalar remainder loop.413 414.. image:: vplan-early-exit.png415 416 417Performance418-----------419 420This section shows the execution time of Clang on a simple benchmark:421`gcc-loops <https://github.com/llvm/llvm-test-suite/tree/main/SingleSource/UnitTests/Vectorizer>`_.422This benchmarks is a collection of loops from the GCC autovectorization423`page <http://gcc.gnu.org/projects/tree-ssa/vectorization.html>`_ by Dorit Nuzman.424 425The 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.426The Y-axis shows the time in msec. Lower is better. The last column shows the geomean of all the kernels.427 428.. image:: gcc-loops.png429 430And Linpack-pc with the same configuration. Result is Mflops, higher is better.431 432.. image:: linpack-pc.png433 434Ongoing Development Directions435------------------------------436 437.. toctree::438 :hidden:439 440 VectorizationPlan441 442:doc:`VectorizationPlan`443 Modeling the process and upgrading the infrastructure of LLVM's Loop Vectorizer.444 445.. _slp-vectorizer:446 447The SLP Vectorizer448==================449 450Details451-------452 453The goal of SLP vectorization (a.k.a. superword-level parallelism) is454to combine similar independent instructions455into vector instructions. Memory accesses, arithmetic operations, comparison456operations, PHI-nodes, can all be vectorized using this technique.457 458For example, the following function performs very similar operations on its459inputs (a1, b1) and (a2, b2). The basic-block vectorizer may combine these460into vector operations.461 462.. code-block:: c++463 464 void foo(int a1, int a2, int b1, int b2, int *A) {465 A[0] = a1*(a1 + b1);466 A[1] = a2*(a2 + b2);467 A[2] = a1*(a1 + b1);468 A[3] = a2*(a2 + b2);469 }470 471The SLP-vectorizer processes the code bottom-up, across basic blocks, in search of scalars to combine.472 473Usage474------475 476The SLP Vectorizer is enabled by default, but it can be disabled477through clang using the command line flag:478 479.. code-block:: console480 481 $ clang -fno-slp-vectorize file.c482 483The Sandbox Vectorizer484======================485.. toctree::486 :hidden:487 488 SandboxVectorizer489 490The :doc:`Sandbox Vectorizer <SandboxVectorizer>` is an experimental framework for building modular vectorization pipelines on top of :doc:`Sandbox IR <SandboxIR>`, with a focus on ease of testing and ease of development.491