X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=docs%2FVectorizers.rst;h=221fb2949f8124f4a8cd883c35e788296d348d84;hb=11eb51e23935e22e1cb7b346c45713e8c9169c84;hp=b4c5458953b37a5dbb437811c16e2bc801bfe760;hpb=f574b88adbb81c7262e236f8fb5aa662eb544a27;p=oota-llvm.git diff --git a/docs/Vectorizers.rst b/docs/Vectorizers.rst index b4c5458953b..221fb2949f8 100644 --- a/docs/Vectorizers.rst +++ b/docs/Vectorizers.rst @@ -6,12 +6,12 @@ Auto-Vectorization in LLVM :local: LLVM has two vectorizers: The :ref:`Loop Vectorizer `, -which operates on Loops, and the :ref:`Basic Block Vectorizer -`, which optimizes straight-line code. These vectorizers +which operates on Loops, and the :ref:`SLP Vectorizer +`. These vectorizers focus on different optimization opportunities and use different techniques. -The BB vectorizer merges multiple scalars that are found in the code into -vectors while the Loop Vectorizer widens instructions in the original loop -to operate on multiple consecutive loop iterations. +The SLP vectorizer merges multiple scalars that are found in the code into +vectors while the Loop Vectorizer widens instructions in loops +to operate on multiple consecutive iterations. .. _loop-vectorizer: @@ -21,19 +21,34 @@ The Loop Vectorizer Usage ----- -LLVM's Loop Vectorizer is now available and will be useful for many people. -It is not enabled by default, but can be enabled through clang using the -command line flag: +LLVM's Loop Vectorizer is now enabled by default for -O3. +We plan to enable parts of the Loop Vectorizer on -O2 and -Os in future releases. +The vectorizer can be disabled using the command line: .. code-block:: console - $ clang -fvectorize -O3 file.c + $ clang ... -fno-vectorize file.c -If the ``-fvectorize`` flag is used then the loop vectorizer will be enabled -when running with ``-O3``, ``-O2``. When ``-Os`` is used, the loop vectorizer -will only vectorize loops that do not require a major increase in code size. +Command line flags +^^^^^^^^^^^^^^^^^^ -We plan to enable the Loop Vectorizer by default as part of the LLVM 3.3 release. +The loop vectorizer uses a cost model to decide on the optimal vectorization factor +and unroll factor. However, users of the vectorizer can force the vectorizer to use +specific values. Both 'clang' and 'opt' support the flags below. + +Users can control the vectorization SIMD width using the command line flag "-force-vector-width". + +.. code-block:: console + + $ clang -mllvm -force-vector-width=8 ... + $ opt -loop-vectorize -force-vector-width=8 ... + +Users can control the unroll factor using the command line flag "-force-vector-unroll" + +.. code-block:: console + + $ clang -mllvm -force-vector-unroll=2 ... + $ opt -loop-vectorize -force-vector-unroll=2 ... Features -------- @@ -99,6 +114,8 @@ reduction operations, such as addition, multiplication, XOR, AND and OR. return sum; } +We support floating point reduction operations when `-ffast-math` is used. + Inductions ^^^^^^^^^^ @@ -183,6 +200,25 @@ vectorization is profitable. A[i] += 4 * B[i]; } +Global Structures Alias Analysis +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +Access to global structures can also be vectorized, with alias analysis being +used to make sure accesses don't alias. Run-time checks can also be added on +pointer access to structure members. + +Many variations are supported, but some that rely on undefined behaviour being +ignored (as other compilers do) are still being left un-vectorized. + +.. code-block:: c++ + + struct { int A[100], K, B[100]; } Foo; + + int foo() { + for (int i = 0; i < 100; ++i) + Foo.A[i] = Foo.B[i] + 100; + } + Vectorization of function calls ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -203,20 +239,30 @@ See the table below for a list of these functions. | | | fmuladd | +-----+-----+---------+ +The loop vectorizer knows about special instructions on the target and will +vectorize a loop containing a function call that maps to the instructions. For +example, the loop below will be vectorized on Intel x86 if the SSE4.1 roundps +instruction is available. + +.. code-block:: c++ + + void foo(float *f) { + for (int i = 0; i != 1024; ++i) + f[i] = floorf(f[i]); + } Partial unrolling during vectorization ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Modern processors feature multiple execution units, and only programs that contain a -high degree of parallelism can fully utilize the entire width of the machine. - +high degree of parallelism can fully utilize the entire width of the machine. The Loop Vectorizer increases the instruction level parallelism (ILP) by performing partial-unrolling of loops. In the example below the entire array is accumulated into the variable 'sum'. -This is inefficient because only a single 'adder' can be used by the processor. +This is inefficient because only a single execution port can be used by the processor. By unrolling the code the Loop Vectorizer allows two or more execution ports -to be used. +to be used simultaneously. .. code-block:: c++ @@ -227,13 +273,8 @@ to be used. return sum; } -At the moment the unrolling feature is not enabled by default and needs to be enabled -in opt or clang using the following flag: - -.. code-block:: console - - -force-vector-unroll=2 - +The Loop Vectorizer uses a cost model to decide when it is profitable to unroll loops. +The decision to unroll the loop depends on the register pressure and the generated code size. Performance ----------- @@ -248,29 +289,22 @@ The Y-axis shows the time in msec. Lower is better. The last column shows the ge .. image:: gcc-loops.png -.. _bb-vectorizer: - -The Basic Block Vectorizer -========================== - -Usage ------- +And Linpack-pc with the same configuration. Result is Mflops, higher is better. -The Basic Block Vectorizer is not enabled by default, but it can be enabled -through clang using the command line flag: +.. image:: linpack-pc.png -.. code-block:: console +.. _slp-vectorizer: - $ clang -fslp-vectorize file.c +The SLP Vectorizer +================== Details ------- -The goal of basic-block vectorization (a.k.a. superword-level parallelism) is -to combine similar independent instructions within simple control-flow regions -into vector instructions. Memory accesses, arithemetic operations, comparison -operations and some math functions can all be vectorized using this technique -(subject to the capabilities of the target architecture). +The goal of SLP vectorization (a.k.a. superword-level parallelism) is +to combine similar independent instructions +into vector instructions. Memory accesses, arithmetic operations, comparison +operations, PHI-nodes, can all be vectorized using this technique. For example, the following function performs very similar operations on its inputs (a1, b1) and (a2, b2). The basic-block vectorizer may combine these @@ -278,10 +312,49 @@ into vector operations. .. code-block:: c++ - int foo(int a1, int a2, int b1, int b2) { - int r1 = a1*(a1 + b1)/b1 + 50*b1/a1; - int r2 = a2*(a2 + b2)/b2 + 50*b2/a2; - return r1 + r2; + void foo(int a1, int a2, int b1, int b2, int *A) { + A[0] = a1*(a1 + b1)/b1 + 50*b1/a1; + A[1] = a2*(a2 + b2)/b2 + 50*b2/a2; } +The SLP-vectorizer processes the code bottom-up, across basic blocks, in search of scalars to combine. + +Usage +------ + +The SLP Vectorizer is not enabled by default, but it can be enabled +through clang using the command line flag: + +.. code-block:: console + + $ clang -fslp-vectorize file.c + +LLVM has a second basic block vectorization phase +which is more compile-time intensive (The BB vectorizer). This optimization +can be enabled through clang using the command line flag: + +.. code-block:: console + + $ clang -fslp-vectorize-aggressive file.c + + +The SLP vectorizer is in early development stages but can already vectorize +and accelerate many programs in the LLVM test suite. + +======================= ============ +Benchmark Name Gain +======================= ============ +Misc/flops-7 -32.70% +Misc/matmul_f64_4x4 -23.23% +Olden/power -21.45% +Misc/flops-4 -14.90% +ASC_Sequoia/AMGmk -13.85% +TSVC/LoopRerolling-flt -11.76% +Misc/flops-6 -9.70% +Misc/flops-5 -8.54% +Misc/flops -8.12% +TSVC/NodeSplitting-dbl -6.96% +Misc-C++/sphereflake -6.74% +Ptrdist/yacr2 -6.31% +======================= ============