1===================================== 2Performance Tips for Frontend Authors 3===================================== 4 5.. contents:: 6 :local: 7 :depth: 2 8 9Abstract 10======== 11 12The intended audience of this document is developers of language frontends 13targeting LLVM IR. This document is home to a collection of tips on how to 14generate IR that optimizes well. 15 16IR Best Practices 17================= 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 the 21generated code. 22 23Beyond the specific items on the list below, it's worth noting that the most 24mature frontend for LLVM is Clang. As a result, the further your IR gets from 25what Clang might emit, the less likely it is to be effectively optimized. It 26can often be useful to write a quick C program with the semantics you're trying 27to 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. Note 29that Clang and LLVM are explicitly version locked so you'll need to make sure 30you're using a Clang built from the same svn revision or release as the LLVM 31library you're using. As always, it's *strongly* recommended that you track 32tip of tree development, particularly during bring up of a new project. 33 34The Basics 35^^^^^^^^^^^ 36 37#. Make sure that your Modules contain both a data layout specification and 38 target triple. Without these pieces, non of the target specific optimization 39 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 type 42 possible (private, internal or linkonce_odr preferably). Doing so will 43 make LLVM's inter-procedural optimizations much more effective. 44 45#. Avoid high in-degree basic blocks (e.g. basic blocks with dozens or hundreds 46 of predecessors). Among other issues, the register allocator is known to 47 perform badly with confronted with such structures. The only exception to 48 this guidance is that a unified return block with high in-degree is fine. 49 50Use of allocas 51^^^^^^^^^^^^^^ 52 53An alloca instruction can be used to represent a function scoped stack slot, 54but can also represent dynamic frame expansion. When representing function 55scoped variables or locations, placing alloca instructions at the beginning of 56the entry block should be preferred. In particular, place them before any 57call instructions. Call instructions might get inlined and replaced with 58multiple basic blocks. The end result is that a following alloca instruction 59would no longer be in the entry basic block afterward. 60 61The SROA (Scalar Replacement Of Aggregates) and Mem2Reg passes only attempt 62to eliminate alloca instructions that are in the entry basic block. Given 63SSA is the canonical form expected by much of the optimizer; if allocas can 64not be eliminated by Mem2Reg or SROA, the optimizer is likely to be less 65effective than it could be. 66 67Avoid loads and stores of large aggregate type 68^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 69 70LLVM currently does not optimize well loads and stores of large :ref:`aggregate 71types <t_aggregate>` (i.e. structs and arrays). As an alternative, consider 72loading individual fields from memory. 73 74Aggregates that are smaller than the largest (performant) load or store 75instruction supported by the targeted hardware are well supported. These can 76be an effective way to represent collections of small packed fields. 77 78Prefer zext over sext when legal 79^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 80 81On some architectures (X86_64 is one), sign extension can involve an extra 82instruction whereas zero extension can be folded into a load. LLVM will try to 83replace a sext with a zext when it can be proven safe, but if you have 84information in your source language about the range of a integer value, it can 85be profitable to use a zext rather than a sext. 86 87Alternatively, you can :ref:`specify the range of the value using metadata 88<range-metadata>` and LLVM can do the sext to zext conversion for you. 89 90Zext GEP indices to machine register width 91^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 92 93Internally, LLVM often promotes the width of GEP indices to machine register 94width. When it does so, it will default to using sign extension (sext) 95operations for safety. If your source language provides information about 96the range of the index, you may wish to manually extend indices to machine 97register width using a zext instruction. 98 99When to specify alignment 100^^^^^^^^^^^^^^^^^^^^^^^^^^ 101LLVM will always generate correct code if you don’t specify alignment, but may 102generate inefficient code. For example, if you are targeting MIPS (or older 103ARM ISAs) then the hardware does not handle unaligned loads and stores, and 104so you will enter a trap-and-emulate path if you do a load or store with 105lower-than-natural alignment. To avoid this, LLVM will emit a slower 106sequence of loads, shifts and masks (or load-right + load-left on MIPS) for 107all cases where the load / store does not have a sufficiently high alignment 108in the IR. 109 110The alignment is used to guarantee the alignment on allocas and globals, 111though in most cases this is unnecessary (most targets have a sufficiently 112high default alignment that they’ll be fine). It is also used to provide a 113contract to the back end saying ‘either this load/store has this alignment, or 114it is undefined behavior’. This means that the back end is free to emit 115instructions that rely on that alignment (and mid-level optimizers are free to 116perform transforms that require that alignment). For x86, it doesn’t make 117much difference, as almost all instructions are alignment-independent. For 118MIPS, it can make a big difference. 119 120Note that if your loads and stores are atomic, the backend will be unable to 121lower an under aligned access into a sequence of natively aligned accesses. 122As a result, alignment is mandatory for atomic loads and stores. 123 124Other Things to Consider 125^^^^^^^^^^^^^^^^^^^^^^^^ 126 127#. Use ptrtoint/inttoptr sparingly (they interfere with pointer aliasing 128 analysis), prefer GEPs 129 130#. Prefer globals over inttoptr of a constant address - this gives you 131 dereferencability information. In MCJIT, use getSymbolAddress to provide 132 actual address. 133 134#. Be wary of ordered and atomic memory operations. They are hard to optimize 135 and may not be well optimized by the current optimizer. Depending on your 136 source language, you may consider using fences instead. 137 138#. If calling a function which is known to throw an exception (unwind), use 139 an invoke with a normal destination which contains an unreachable 140 instruction. This form conveys to the optimizer that the call returns 141 abnormally. For an invoke which neither returns normally or requires unwind 142 code in the current function, you can use a noreturn call instruction if 143 desired. This is generally not required because the optimizer will convert 144 an invoke with an unreachable unwind destination to a call instruction. 145 146#. Use profile metadata to indicate statically known cold paths, even if 147 dynamic profiling information is not available. This can make a large 148 difference in code placement and thus the performance of tight loops. 149 150#. When generating code for loops, try to avoid terminating the header block of 151 the loop earlier than necessary. If the terminator of the loop header 152 block is a loop exiting conditional branch, the effectiveness of LICM will 153 be limited for loads not in the header. (This is due to the fact that LLVM 154 may not know such a load is safe to speculatively execute and thus can't 155 lift an otherwise loop invariant load unless it can prove the exiting 156 condition is not taken.) It can be profitable, in some cases, to emit such 157 instructions into the header even if they are not used along a rarely 158 executed path that exits the loop. This guidance specifically does not 159 apply if the condition which terminates the loop header is itself invariant, 160 or can be easily discharged by inspecting the loop index variables. 161 162#. In hot loops, consider duplicating instructions from small basic blocks 163 which end in highly predictable terminators into their successor blocks. 164 If a hot successor block contains instructions which can be vectorized 165 with the duplicated ones, this can provide a noticeable throughput 166 improvement. Note that this is not always profitable and does involve a 167 potentially large increase in code size. 168 169#. When checking a value against a constant, emit the check using a consistent 170 comparison type. The GVN pass *will* optimize redundant equalities even if 171 the type of comparison is inverted, but GVN only runs late in the pipeline. 172 As a result, you may miss the opportunity to run other important 173 optimizations. Improvements to EarlyCSE to remove this issue are tracked in 174 Bug 23333. 175 176#. Avoid using arithmetic intrinsics unless you are *required* by your source 177 language specification to emit a particular code sequence. The optimizer 178 is quite good at reasoning about general control flow and arithmetic, it is 179 not anywhere near as strong at reasoning about the various intrinsics. If 180 profitable for code generation purposes, the optimizer will likely form the 181 intrinsics itself late in the optimization pipeline. It is *very* rarely 182 profitable to emit these directly in the language frontend. This item 183 explicitly includes the use of the :ref:`overflow intrinsics <int_overflow>`. 184 185#. Avoid using the :ref:`assume intrinsic <int_assume>` until you've 186 established that a) there's no other way to express the given fact and b) 187 that fact is critical for optimization purposes. Assumes are a great 188 prototyping mechanism, but they can have negative effects on both compile 189 time and optimization effectiveness. The former is fixable with enough 190 effort, but the later is fairly fundamental to their designed purpose. 191 192 193Describing Language Specific Properties 194======================================= 195 196When translating a source language to LLVM, finding ways to express concepts 197and guarantees available in your source language which are not natively 198provided by LLVM IR will greatly improve LLVM's ability to optimize your code. 199As an example, C/C++'s ability to mark every add as "no signed wrap (nsw)" goes 200a long way to assisting the optimizer in reasoning about loop induction 201variables and thus generating more optimal code for loops. 202 203The LLVM LangRef includes a number of mechanisms for annotating the IR with 204additional semantic information. It is *strongly* recommended that you become 205highly familiar with this document. The list below is intended to highlight a 206couple of items of particular interest, but is by no means exhaustive. 207 208Restricted Operation Semantics 209^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 210#. Add nsw/nuw flags as appropriate. Reasoning about overflow is 211 generally hard for an optimizer so providing these facts from the frontend 212 can be very impactful. 213 214#. Use fast-math flags on floating point operations if legal. If you don't 215 need strict IEEE floating point semantics, there are a number of additional 216 optimizations that can be performed. This can be highly impactful for 217 floating point intensive computations. 218 219Describing Aliasing Properties 220^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 221 222#. Add noalias/align/dereferenceable/nonnull to function arguments and return 223 values as appropriate 224 225#. Use pointer aliasing metadata, especially tbaa metadata, to communicate 226 otherwise-non-deducible pointer aliasing facts 227 228#. Use inbounds on geps. This can help to disambiguate some aliasing queries. 229 230 231Modeling Memory Effects 232^^^^^^^^^^^^^^^^^^^^^^^^ 233 234#. Mark functions as readnone/readonly/argmemonly or noreturn/nounwind when 235 known. The optimizer will try to infer these flags, but may not always be 236 able to. Manual annotations are particularly important for external 237 functions that the optimizer can not analyze. 238 239#. Use the lifetime.start/lifetime.end and invariant.start/invariant.end 240 intrinsics where possible. Common profitable uses are for stack like data 241 structures (thus allowing dead store elimination) and for describing 242 life times of allocas (thus allowing smaller stack sizes). 243 244#. Mark invariant locations using !invariant.load and TBAA's constant flags 245 246Pass Ordering 247^^^^^^^^^^^^^ 248 249One of the most common mistakes made by new language frontend projects is to 250use the existing -O2 or -O3 pass pipelines as is. These pass pipelines make a 251good starting point for an optimizing compiler for any language, but they have 252been carefully tuned for C and C++, not your target language. You will almost 253certainly need to use a custom pass order to achieve optimal performance. A 254couple specific suggestions: 255 256#. For languages with numerous rarely executed guard conditions (e.g. null 257 checks, type checks, range checks) consider adding an extra execution or 258 two of LoopUnswith and LICM to your pass order. The standard pass order, 259 which is tuned for C and C++ applications, may not be sufficient to remove 260 all dischargeable checks from loops. 261 262#. If you language uses range checks, consider using the IRCE pass. It is not 263 currently part of the standard pass order. 264 265#. A useful sanity check to run is to run your optimized IR back through the 266 -O2 pipeline again. If you see noticeable improvement in the resulting IR, 267 you likely need to adjust your pass order. 268 269 270I Still Can't Find What I'm Looking For 271^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 272 273If you didn't find what you were looking for above, consider proposing an piece 274of metadata which provides the optimization hint you need. Such extensions are 275relatively common and are generally well received by the community. You will 276need to ensure that your proposal is sufficiently general so that it benefits 277others if you wish to contribute it upstream. 278 279You should also consider describing the problem you're facing on `llvm-dev 280<http://lists.llvm.org/mailman/listinfo/llvm-dev>`_ and asking for advice. 281It's entirely possible someone has encountered your problem before and can 282give good advice. If there are multiple interested parties, that also 283increases the chances that a metadata extension would be well received by the 284community as a whole. 285 286Adding to this document 287======================= 288 289If you run across a case that you feel deserves to be covered here, please send 290a patch to `llvm-commits 291<http://lists.llvm.org/mailman/listinfo/llvm-commits>`_ for review. 292 293If you have questions on these items, please direct them to `llvm-dev 294<http://lists.llvm.org/mailman/listinfo/llvm-dev>`_. The more relevant 295context you are able to give to your question, the more likely it is to be 296answered. 297 298