324 lines · plain
1=====================================2Performance Tips for Frontend Authors3=====================================4 5.. contents::6 :local:7 :depth: 28 9Abstract10========11 12The intended audience of this document is developers of language frontends13targeting LLVM IR. This document is home to a collection of tips on how to14generate IR that optimizes well.15 16IR Best Practices17=================18 19As with any optimizer, LLVM has its strengths and weaknesses. In some cases,20surprisingly small changes in the source IR can have a large effect on the21generated code.22 23Beyond the specific items on the list below, it's worth noting that the most24mature frontend for LLVM is Clang. As a result, the further your IR gets from25what Clang might emit, the less likely it is to be effectively optimized. It26can often be useful to write a quick C program with the semantics you're trying27to model and see what decisions Clang's IRGen makes about what IR to emit.28Studying Clang's CodeGen directory can also be a good source of ideas. Note29that Clang and LLVM are explicitly version locked so you'll need to make sure30you're using a Clang built from the same git revision or release as the LLVM31library you're using. As always, it's *strongly* recommended that you track32tip of tree development, particularly during bring up of a new project.33 34The Basics35^^^^^^^^^^^36 37#. Make sure that your Modules contain both a data layout specification and38 target triple. Without these pieces, non of the target-specific optimization39 will be enabled. This can have a major effect on the generated code quality.40 41#. For each function or global emitted, use the most private linkage type42 possible (private, internal or linkonce_odr preferably). Doing so will43 make LLVM's inter-procedural optimizations much more effective.44 45#. Avoid high in-degree basic blocks (e.g. basic blocks with dozens or hundreds46 of predecessors). Among other issues, the register allocator is known to47 perform badly with confronted with such structures. The only exception to48 this guidance is that a unified return block with high in-degree is fine.49 50Use of allocas51^^^^^^^^^^^^^^52 53An alloca instruction can be used to represent a function scoped stack slot,54but can also represent dynamic frame expansion. When representing function55scoped variables or locations, placing alloca instructions at the beginning of56the entry block should be preferred. In particular, place them before any57call instructions. Call instructions might get inlined and replaced with58multiple basic blocks. The end result is that a following alloca instruction59would no longer be in the entry basic block afterward.60 61The SROA (Scalar Replacement Of Aggregates) and Mem2Reg passes only attempt62to eliminate alloca instructions that are in the entry basic block. Given63SSA is the canonical form expected by much of the optimizer; if allocas can64not be eliminated by Mem2Reg or SROA, the optimizer is likely to be less65effective than it could be.66 67Avoid creating values of aggregate type68^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^69 70Avoid creating values of :ref:`aggregate types <t_aggregate>` (i.e. structs and71arrays). In particular, avoid loading and storing them, or manipulating them72with insertvalue and extractvalue instructions. Instead, only load and store73individual fields of the aggregate.74 75There are some exceptions to this rule:76 77* It is fine to use values of aggregate type in global variable initializers.78* It is fine to return structs, if this is done to represent the return of79 multiple values in registers.80* It is fine to work with structs returned by LLVM intrinsics, such as the81 ``with.overflow`` family of intrinsics.82* It is fine to use aggregate *types* without creating values. For example,83 they are commonly used in ``getelementptr`` instructions or attributes like84 ``sret``.85 86Avoid loads and stores of non-byte-sized types87^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^88 89Avoid loading or storing non-byte-sized types like ``i1``. Instead,90appropriately extend them to the next byte-sized type.91 92For example, when working with boolean values, store them by zero-extending93``i1`` to ``i8`` and load them by loading ``i8`` and truncating to ``i1``.94 95If you do use loads/stores on non-byte-sized types, make sure that you *always*96use those types. For example, do not first store ``i8`` and then load ``i1``.97 98Prefer zext over sext when legal99^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^100 101On some architectures (X86_64 is one), sign extension can involve an extra102instruction whereas zero extension can be folded into a load. LLVM will try to103replace a sext with a zext when it can be proven safe, but if you have104information in your source language about the range of an integer value, it can105be profitable to use a zext rather than a sext.106 107Alternatively, you can :ref:`specify the range of the value using metadata108<range-metadata>` and LLVM can do the sext to zext conversion for you.109 110Zext GEP indices to machine register width111^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^112 113Internally, LLVM often promotes the width of GEP indices to machine register114width. When it does so, it will default to using sign extension (sext)115operations for safety. If your source language provides information about116the range of the index, you may wish to manually extend indices to machine117register width using a zext instruction.118 119When to specify alignment120^^^^^^^^^^^^^^^^^^^^^^^^^^121LLVM will always generate correct code if you don’t specify alignment, but may122generate inefficient code. For example, if you are targeting MIPS (or older123ARM ISAs) then the hardware does not handle unaligned loads and stores, and124so you will enter a trap-and-emulate path if you do a load or store with125lower-than-natural alignment. To avoid this, LLVM will emit a slower126sequence of loads, shifts and masks (or load-right + load-left on MIPS) for127all cases where the load / store does not have a sufficiently high alignment128in the IR.129 130The alignment is used to guarantee the alignment on allocas and globals,131though in most cases this is unnecessary (most targets have a sufficiently132high default alignment that they’ll be fine). It is also used to provide a133contract to the back end saying ‘either this load/store has this alignment, or134it is undefined behavior’. This means that the back end is free to emit135instructions that rely on that alignment (and mid-level optimizers are free to136perform transforms that require that alignment). For x86, it doesn’t make137much difference, as almost all instructions are alignment-independent. For138MIPS, it can make a big difference.139 140Note that if your loads and stores are atomic, the backend will be unable to141lower an under aligned access into a sequence of natively aligned accesses.142As a result, alignment is mandatory for atomic loads and stores.143 144Other Things to Consider145^^^^^^^^^^^^^^^^^^^^^^^^146 147#. Use ptrtoint/inttoptr sparingly (they interfere with pointer aliasing148 analysis), prefer GEPs149 150#. Prefer globals over inttoptr of a constant address - this gives you151 dereferencability information. In MCJIT, use getSymbolAddress to provide152 actual address.153 154#. Be wary of ordered and atomic memory operations. They are hard to optimize155 and may not be well optimized by the current optimizer. Depending on your156 source language, you may consider using fences instead.157 158#. If calling a function which is known to throw an exception (unwind), use159 an invoke with a normal destination which contains an unreachable160 instruction. This form conveys to the optimizer that the call returns161 abnormally. For an invoke which neither returns normally or requires unwind162 code in the current function, you can use a noreturn call instruction if163 desired. This is generally not required because the optimizer will convert164 an invoke with an unreachable unwind destination to a call instruction.165 166#. Use profile metadata to indicate statically known cold paths, even if167 dynamic profiling information is not available. This can make a large168 difference in code placement and thus the performance of tight loops.169 170#. When generating code for loops, try to avoid terminating the header block of171 the loop earlier than necessary. If the terminator of the loop header172 block is a loop exiting conditional branch, the effectiveness of LICM will173 be limited for loads not in the header. (This is due to the fact that LLVM174 may not know such a load is safe to speculatively execute and thus can't175 lift an otherwise loop invariant load unless it can prove the exiting176 condition is not taken.) It can be profitable, in some cases, to emit such177 instructions into the header even if they are not used along a rarely178 executed path that exits the loop. This guidance specifically does not179 apply if the condition which terminates the loop header is itself invariant,180 or can be easily discharged by inspecting the loop index variables.181 182#. In hot loops, consider duplicating instructions from small basic blocks183 which end in highly predictable terminators into their successor blocks.184 If a hot successor block contains instructions which can be vectorized185 with the duplicated ones, this can provide a noticeable throughput186 improvement. Note that this is not always profitable and does involve a187 potentially large increase in code size.188 189#. When checking a value against a constant, emit the check using a consistent190 comparison type. The GVN pass *will* optimize redundant equalities even if191 the type of comparison is inverted, but GVN only runs late in the pipeline.192 As a result, you may miss the opportunity to run other important193 optimizations.194 195#. Avoid using arithmetic intrinsics unless you are *required* by your source196 language specification to emit a particular code sequence. The optimizer197 is quite good at reasoning about general control flow and arithmetic, it is198 not anywhere near as strong at reasoning about the various intrinsics. If199 profitable for code generation purposes, the optimizer will likely form the200 intrinsics itself late in the optimization pipeline. It is *very* rarely201 profitable to emit these directly in the language frontend. This item202 explicitly includes the use of the :ref:`overflow intrinsics <int_overflow>`.203 204#. Avoid using the :ref:`assume intrinsic <int_assume>` until you've205 established that a) there's no other way to express the given fact and b)206 that fact is critical for optimization purposes. Assumes are a great207 prototyping mechanism, but they can have negative effects on both compile208 time and optimization effectiveness. The former is fixable with enough209 effort, but the later is fairly fundamental to their designed purpose. If210 you are creating a non-terminator unreachable instruction or passing a false211 value, use the ``store i1 true, ptr poison, align 1`` canonical form.212 213 214Describing Language Specific Properties215=======================================216 217When translating a source language to LLVM, finding ways to express concepts218and guarantees available in your source language which are not natively219provided by LLVM IR will greatly improve LLVM's ability to optimize your code.220As an example, C/C++'s ability to mark every add as "no signed wrap (nsw)" goes221a long way to assisting the optimizer in reasoning about loop induction222variables and thus generating more optimal code for loops.223 224The LLVM LangRef includes a number of mechanisms for annotating the IR with225additional semantic information. It is *strongly* recommended that you become226highly familiar with this document. The list below is intended to highlight a227couple of items of particular interest, but is by no means exhaustive.228 229Restricted Operation Semantics230^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^231#. Add nsw/nuw flags as appropriate. Reasoning about overflow is232 generally hard for an optimizer so providing these facts from the frontend233 can be very impactful.234 235#. Use fast-math flags on floating point operations if legal. If you don't236 need strict IEEE floating point semantics, there are a number of additional237 optimizations that can be performed. This can be highly impactful for238 floating point intensive computations.239 240Describing Aliasing Properties241^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^242 243#. Add noalias/align/dereferenceable/nonnull to function arguments and return244 values as appropriate245 246#. Use pointer aliasing metadata, especially tbaa metadata, to communicate247 otherwise-non-deducible pointer aliasing facts248 249#. Use inbounds on geps. This can help to disambiguate some aliasing queries.250 251Undefined Values252^^^^^^^^^^^^^^^^253 254#. Use poison values instead of undef values whenever possible.255 256#. Tag function parameters with the noundef attribute whenever possible.257 258Modeling Memory Effects259^^^^^^^^^^^^^^^^^^^^^^^^260 261#. Mark functions as readnone/readonly/argmemonly or noreturn/nounwind when262 known. The optimizer will try to infer these flags, but may not always be263 able to. Manual annotations are particularly important for external264 functions that the optimizer can not analyze.265 266#. Use the lifetime.start/lifetime.end and invariant.start/invariant.end267 intrinsics where possible. Common profitable uses are for stack like data268 structures (thus allowing dead store elimination) and for describing269 life times of allocas (thus allowing smaller stack sizes).270 271#. Mark invariant locations using !invariant.load and TBAA's constant flags272 273Pass Ordering274^^^^^^^^^^^^^275 276One of the most common mistakes made by new language frontend projects is to277use the existing -O2 or -O3 pass pipelines as is. These pass pipelines make a278good starting point for an optimizing compiler for any language, but they have279been carefully tuned for C and C++, not your target language. You will almost280certainly need to use a custom pass order to achieve optimal performance. A281couple specific suggestions:282 283#. For languages with numerous rarely executed guard conditions (e.g. null284 checks, type checks, range checks) consider adding an extra execution or285 two of LoopUnswitch and LICM to your pass order. The standard pass order,286 which is tuned for C and C++ applications, may not be sufficient to remove287 all dischargeable checks from loops.288 289#. If your language uses range checks, consider using the IRCE pass. It is not290 currently part of the standard pass order.291 292#. A useful sanity check to run is to run your optimized IR back through the293 -O2 pipeline again. If you see noticeable improvement in the resulting IR,294 you likely need to adjust your pass order.295 296 297I Still Can't Find What I'm Looking For298^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^299 300If you didn't find what you were looking for above, consider proposing a piece301of metadata which provides the optimization hint you need. Such extensions are302relatively common and are generally well received by the community. You will303need to ensure that your proposal is sufficiently general so that it benefits304others if you wish to contribute it upstream.305 306You should also consider describing the problem you're facing on `Discourse307<https://discourse.llvm.org>`_ and asking for advice.308It's entirely possible someone has encountered your problem before and can309give good advice. If there are multiple interested parties, that also310increases the chances that a metadata extension would be well received by the311community as a whole.312 313Adding to this document314=======================315 316If you run across a case that you feel deserves to be covered here, please send317a patch to `llvm-commits318<http://lists.llvm.org/mailman/listinfo/llvm-commits>`_ for review.319 320If you have questions on these items, please ask them on `Discourse321<https://discourse.llvm.org>`_. The more relevant322context you are able to give to your question, the more likely it is to be323answered.324