diff options
Diffstat (limited to 'docs/Frontend/PerformanceTips.rst')
| -rw-r--r-- | docs/Frontend/PerformanceTips.rst | 227 |
1 files changed, 170 insertions, 57 deletions
diff --git a/docs/Frontend/PerformanceTips.rst b/docs/Frontend/PerformanceTips.rst index 8d0abcd1c172c..142d262eb6573 100644 --- a/docs/Frontend/PerformanceTips.rst +++ b/docs/Frontend/PerformanceTips.rst @@ -11,12 +11,60 @@ Abstract The intended audience of this document is developers of language frontends targeting LLVM IR. This document is home to a collection of tips on how to -generate IR that optimizes well. As with any optimizer, LLVM has its strengths -and weaknesses. In some cases, surprisingly small changes in the source IR -can have a large effect on the generated code. +generate IR that optimizes well. + +IR Best Practices +================= + +As with any optimizer, LLVM has its strengths and weaknesses. In some cases, +surprisingly small changes in the source IR can have a large effect on the +generated code. + +Beyond the specific items on the list below, it's worth noting that the most +mature frontend for LLVM is Clang. As a result, the further your IR gets from what Clang might emit, the less likely it is to be effectively optimized. It +can often be useful to write a quick C program with the semantics you're trying +to model and see what decisions Clang's IRGen makes about what IR to emit. +Studying Clang's CodeGen directory can also be a good source of ideas. Note +that Clang and LLVM are explicitly version locked so you'll need to make sure +you're using a Clang built from the same svn revision or release as the LLVM +library you're using. As always, it's *strongly* recommended that you track +tip of tree development, particularly during bring up of a new project. + +The Basics +^^^^^^^^^^^ + +#. Make sure that your Modules contain both a data layout specification and + target triple. Without these pieces, non of the target specific optimization + will be enabled. This can have a major effect on the generated code quality. + +#. For each function or global emitted, use the most private linkage type + possible (private, internal or linkonce_odr preferably). Doing so will + make LLVM's inter-procedural optimizations much more effective. + +#. Avoid high in-degree basic blocks (e.g. basic blocks with dozens or hundreds + of predecessors). Among other issues, the register allocator is known to + perform badly with confronted with such structures. The only exception to + this guidance is that a unified return block with high in-degree is fine. + +Use of allocas +^^^^^^^^^^^^^^ + +An alloca instruction can be used to represent a function scoped stack slot, +but can also represent dynamic frame expansion. When representing function +scoped variables or locations, placing alloca instructions at the beginning of +the entry block should be preferred. In particular, place them before any +call instructions. Call instructions might get inlined and replaced with +multiple basic blocks. The end result is that a following alloca instruction +would no longer be in the entry basic block afterward. + +The SROA (Scalar Replacement Of Aggregates) and Mem2Reg passes only attempt +to eliminate alloca instructions that are in the entry basic block. Given +SSA is the canonical form expected by much of the optimizer; if allocas can +not be eliminated by Mem2Reg or SROA, the optimizer is likely to be less +effective than it could be. Avoid loads and stores of large aggregate type -================================================ +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ LLVM currently does not optimize well loads and stores of large :ref:`aggregate types <t_aggregate>` (i.e. structs and arrays). As an alternative, consider @@ -27,7 +75,7 @@ instruction supported by the targeted hardware are well supported. These can be an effective way to represent collections of small packed fields. Prefer zext over sext when legal -================================== +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ On some architectures (X86_64 is one), sign extension can involve an extra instruction whereas zero extension can be folded into a load. LLVM will try to @@ -39,7 +87,7 @@ Alternatively, you can :ref:`specify the range of the value using metadata <range-metadata>` and LLVM can do the sext to zext conversion for you. Zext GEP indices to machine register width -============================================ +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Internally, LLVM often promotes the width of GEP indices to machine register width. When it does so, it will default to using sign extension (sext) @@ -47,47 +95,37 @@ operations for safety. If your source language provides information about the range of the index, you may wish to manually extend indices to machine register width using a zext instruction. -Other things to consider -========================= - -#. Make sure that a DataLayout is provided (this will likely become required in - the near future, but is certainly important for optimization). +When to specify alignment +^^^^^^^^^^^^^^^^^^^^^^^^^^ +LLVM will always generate correct code if you don’t specify alignment, but may +generate inefficient code. For example, if you are targeting MIPS (or older +ARM ISAs) then the hardware does not handle unaligned loads and stores, and +so you will enter a trap-and-emulate path if you do a load or store with +lower-than-natural alignment. To avoid this, LLVM will emit a slower +sequence of loads, shifts and masks (or load-right + load-left on MIPS) for +all cases where the load / store does not have a sufficiently high alignment +in the IR. -#. Add nsw/nuw flags as appropriate. Reasoning about overflow is - generally hard for an optimizer so providing these facts from the frontend - can be very impactful. +The alignment is used to guarantee the alignment on allocas and globals, +though in most cases this is unnecessary (most targets have a sufficiently +high default alignment that they’ll be fine). It is also used to provide a +contract to the back end saying ‘either this load/store has this alignment, or +it is undefined behavior’. This means that the back end is free to emit +instructions that rely on that alignment (and mid-level optimizers are free to +perform transforms that require that alignment). For x86, it doesn’t make +much difference, as almost all instructions are alignment-independent. For +MIPS, it can make a big difference. -#. Use fast-math flags on floating point operations if legal. If you don't - need strict IEEE floating point semantics, there are a number of additional - optimizations that can be performed. This can be highly impactful for - floating point intensive computations. +Note that if your loads and stores are atomic, the backend will be unable to +lower an under aligned access into a sequence of natively aligned accesses. +As a result, alignment is mandatory for atomic loads and stores. -#. Use inbounds on geps. This can help to disambiguate some aliasing queries. - -#. Add noalias/align/dereferenceable/nonnull to function arguments and return - values as appropriate - -#. Mark functions as readnone/readonly or noreturn/nounwind when known. The - optimizer will try to infer these flags, but may not always be able to. - Manual annotations are particularly important for external functions that - the optimizer can not analyze. +Other Things to Consider +^^^^^^^^^^^^^^^^^^^^^^^^ #. Use ptrtoint/inttoptr sparingly (they interfere with pointer aliasing analysis), prefer GEPs -#. Use the lifetime.start/lifetime.end and invariant.start/invariant.end - intrinsics where possible. Common profitable uses are for stack like data - structures (thus allowing dead store elimination) and for describing - life times of allocas (thus allowing smaller stack sizes). - -#. Use pointer aliasing metadata, especially tbaa metadata, to communicate - otherwise-non-deducible pointer aliasing facts - -#. Use the "most-private" possible linkage types for the functions being defined - (private, internal or linkonce_odr preferably) - -#. Mark invariant locations using !invariant.load and TBAA's constant flags - #. Prefer globals over inttoptr of a constant address - this gives you dereferencability information. In MCJIT, use getSymbolAddress to provide actual address. @@ -104,15 +142,6 @@ Other things to consider desired. This is generally not required because the optimizer will convert an invoke with an unreachable unwind destination to a call instruction. -#. If you language uses range checks, consider using the IRCE pass. It is not - currently part of the standard pass order. - -#. For languages with numerous rarely executed guard conditions (e.g. null - checks, type checks, range checks) consider adding an extra execution or - two of LoopUnswith and LICM to your pass order. The standard pass order, - which is tuned for C and C++ applications, may not be sufficient to remove - all dischargeable checks from loops. - #. Use profile metadata to indicate statically known cold paths, even if dynamic profiling information is not available. This can make a large difference in code placement and thus the performance of tight loops. @@ -136,11 +165,6 @@ Other things to consider improvement. Note that this is not always profitable and does involve a potentially large increase in code size. -#. Avoid high in-degree basic blocks (e.g. basic blocks with dozens or hundreds - of predecessors). Among other issues, the register allocator is known to - perform badly with confronted with such structures. The only exception to - this guidance is that a unified return block with high in-degree is fine. - #. When checking a value against a constant, emit the check using a consistent comparison type. The GVN pass *will* optimize redundant equalities even if the type of comparison is inverted, but GVN only runs late in the pipeline. @@ -164,10 +188,99 @@ Other things to consider time and optimization effectiveness. The former is fixable with enough effort, but the later is fairly fundamental to their designed purpose. -p.s. If you want to help improve this document, patches expanding any of the -above items into standalone sections of their own with a more complete -discussion would be very welcome. +Describing Language Specific Properties +======================================= + +When translating a source language to LLVM, finding ways to express concepts +and guarantees available in your source language which are not natively +provided by LLVM IR will greatly improve LLVM's ability to optimize your code. +As an example, C/C++'s ability to mark every add as "no signed wrap (nsw)" goes +a long way to assisting the optimizer in reasoning about loop induction +variables and thus generating more optimal code for loops. + +The LLVM LangRef includes a number of mechanisms for annotating the IR with +additional semantic information. It is *strongly* recommended that you become +highly familiar with this document. The list below is intended to highlight a +couple of items of particular interest, but is by no means exhaustive. + +Restricted Operation Semantics +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +#. Add nsw/nuw flags as appropriate. Reasoning about overflow is + generally hard for an optimizer so providing these facts from the frontend + can be very impactful. + +#. Use fast-math flags on floating point operations if legal. If you don't + need strict IEEE floating point semantics, there are a number of additional + optimizations that can be performed. This can be highly impactful for + floating point intensive computations. + +Describing Aliasing Properties +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +#. Add noalias/align/dereferenceable/nonnull to function arguments and return + values as appropriate + +#. Use pointer aliasing metadata, especially tbaa metadata, to communicate + otherwise-non-deducible pointer aliasing facts + +#. Use inbounds on geps. This can help to disambiguate some aliasing queries. + + +Modeling Memory Effects +^^^^^^^^^^^^^^^^^^^^^^^^ + +#. Mark functions as readnone/readonly/argmemonly or noreturn/nounwind when + known. The optimizer will try to infer these flags, but may not always be + able to. Manual annotations are particularly important for external + functions that the optimizer can not analyze. + +#. Use the lifetime.start/lifetime.end and invariant.start/invariant.end + intrinsics where possible. Common profitable uses are for stack like data + structures (thus allowing dead store elimination) and for describing + life times of allocas (thus allowing smaller stack sizes). + +#. Mark invariant locations using !invariant.load and TBAA's constant flags + +Pass Ordering +^^^^^^^^^^^^^ + +One of the most common mistakes made by new language frontend projects is to +use the existing -O2 or -O3 pass pipelines as is. These pass pipelines make a +good starting point for an optimizing compiler for any language, but they have +been carefully tuned for C and C++, not your target language. You will almost +certainly need to use a custom pass order to achieve optimal performance. A +couple specific suggestions: + +#. For languages with numerous rarely executed guard conditions (e.g. null + checks, type checks, range checks) consider adding an extra execution or + two of LoopUnswith and LICM to your pass order. The standard pass order, + which is tuned for C and C++ applications, may not be sufficient to remove + all dischargeable checks from loops. + +#. If you language uses range checks, consider using the IRCE pass. It is not + currently part of the standard pass order. + +#. A useful sanity check to run is to run your optimized IR back through the + -O2 pipeline again. If you see noticeable improvement in the resulting IR, + you likely need to adjust your pass order. + + +I Still Can't Find What I'm Looking For +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +If you didn't find what you were looking for above, consider proposing an piece +of metadata which provides the optimization hint you need. Such extensions are +relatively common and are generally well received by the community. You will +need to ensure that your proposal is sufficiently general so that it benefits +others if you wish to contribute it upstream. + +You should also consider describing the problem you're facing on `llvm-dev +<http://lists.llvm.org/mailman/listinfo/llvm-dev>`_ and asking for advice. +It's entirely possible someone has encountered your problem before and can +give good advice. If there are multiple interested parties, that also +increases the chances that a metadata extension would be well received by the +community as a whole. Adding to this document ======================= |