docs/Frontend/PerformanceTips.rst

   1 =====================================
   2 Performance Tips for Frontend Authors
   3 =====================================
   4
   5 .. contents::
   6    :local:
   7    :depth: 2
   8
   9 Abstract
  10 ========
  11
  12 The intended audience of this document is developers of language frontends
  13 targeting LLVM IR. This document is home to a collection of tips on how to
  14 generate IR that optimizes well.  As with any optimizer, LLVM has its strengths
  15 and weaknesses.  In some cases, surprisingly small changes in the source IR
  16 can have a large effect on the generated code.
  17
  18 IR Best Practices
  19 =================
  20
  21 Avoid loads and stores of large aggregate type
  22 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  23
  24 LLVM currently does not optimize well loads and stores of large :ref:`aggregate
  25 types <t_aggregate>` (i.e. structs and arrays).  As an alternative, consider
  26 loading individual fields from memory.
  27
  28 Aggregates that are smaller than the largest (performant) load or store
  29 instruction supported by the targeted hardware are well supported.  These can
  30 be an effective way to represent collections of small packed fields.
  31
  32 Prefer zext over sext when legal
  33 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  34
  35 On some architectures (X86_64 is one), sign extension can involve an extra
  36 instruction whereas zero extension can be folded into a load.  LLVM will try to
  37 replace a sext with a zext when it can be proven safe, but if you have
  38 information in your source language about the range of a integer value, it can
  39 be profitable to use a zext rather than a sext.
  40
  41 Alternatively, you can :ref:`specify the range of the value using metadata
  42 <range-metadata>` and LLVM can do the sext to zext conversion for you.
  43
  44 Zext GEP indices to machine register width
  45 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  46
  47 Internally, LLVM often promotes the width of GEP indices to machine register
  48 width.  When it does so, it will default to using sign extension (sext)
  49 operations for safety.  If your source language provides information about
  50 the range of the index, you may wish to manually extend indices to machine
  51 register width using a zext instruction.
  52
  53 Other Things to Consider
  54 ^^^^^^^^^^^^^^^^^^^^^^^^
  55
  56 #. Make sure that a DataLayout is provided (this will likely become required in
  57    the near future, but is certainly important for optimization).
  58
  59 #. Use ptrtoint/inttoptr sparingly (they interfere with pointer aliasing
  60    analysis), prefer GEPs
  61
  62 #. Use the "most-private" possible linkage types for the functions being defined
  63    (private, internal or linkonce_odr preferably)
  64
  65 #. Prefer globals over inttoptr of a constant address - this gives you
  66    dereferencability information.  In MCJIT, use getSymbolAddress to provide
  67    actual address.
  68
  69 #. Be wary of ordered and atomic memory operations.  They are hard to optimize
  70    and may not be well optimized by the current optimizer.  Depending on your
  71    source language, you may consider using fences instead.
  72
  73 #. If calling a function which is known to throw an exception (unwind), use
  74    an invoke with a normal destination which contains an unreachable
  75    instruction.  This form conveys to the optimizer that the call returns
  76    abnormally.  For an invoke which neither returns normally or requires unwind
  77    code in the current function, you can use a noreturn call instruction if
  78    desired.  This is generally not required because the optimizer will convert
  79    an invoke with an unreachable unwind destination to a call instruction.
  80
  81 #. Use profile metadata to indicate statically known cold paths, even if
  82    dynamic profiling information is not available.  This can make a large
  83    difference in code placement and thus the performance of tight loops.
  84
  85 #. When generating code for loops, try to avoid terminating the header block of
  86    the loop earlier than necessary.  If the terminator of the loop header
  87    block is a loop exiting conditional branch, the effectiveness of LICM will
  88    be limited for loads not in the header.  (This is due to the fact that LLVM
  89    may not know such a load is safe to speculatively execute and thus can't
  90    lift an otherwise loop invariant load unless it can prove the exiting
  91    condition is not taken.)  It can be profitable, in some cases, to emit such
  92    instructions into the header even if they are not used along a rarely
  93    executed path that exits the loop.  This guidance specifically does not
  94    apply if the condition which terminates the loop header is itself invariant,
  95    or can be easily discharged by inspecting the loop index variables.
  96
  97 #. In hot loops, consider duplicating instructions from small basic blocks
  98    which end in highly predictable terminators into their successor blocks.
  99    If a hot successor block contains instructions which can be vectorized
 100    with the duplicated ones, this can provide a noticeable throughput
 101    improvement.  Note that this is not always profitable and does involve a
 102    potentially large increase in code size.
 103
 104 #. Avoid high in-degree basic blocks (e.g. basic blocks with dozens or hundreds
 105    of predecessors).  Among other issues, the register allocator is known to
 106    perform badly with confronted with such structures.  The only exception to
 107    this guidance is that a unified return block with high in-degree is fine.
 108
 109 #. When checking a value against a constant, emit the check using a consistent
 110    comparison type.  The GVN pass *will* optimize redundant equalities even if
 111    the type of comparison is inverted, but GVN only runs late in the pipeline.
 112    As a result, you may miss the opportunity to run other important
 113    optimizations.  Improvements to EarlyCSE to remove this issue are tracked in
 114    Bug 23333.
 115
 116 #. Avoid using arithmetic intrinsics unless you are *required* by your source
 117    language specification to emit a particular code sequence.  The optimizer
 118    is quite good at reasoning about general control flow and arithmetic, it is
 119    not anywhere near as strong at reasoning about the various intrinsics.  If
 120    profitable for code generation purposes, the optimizer will likely form the
 121    intrinsics itself late in the optimization pipeline.  It is *very* rarely
 122    profitable to emit these directly in the language frontend.  This item
 123    explicitly includes the use of the :ref:`overflow intrinsics <int_overflow>`.
 124
 125 #. Avoid using the :ref:`assume intrinsic <int_assume>` until you've
 126    established that a) there's no other way to express the given fact and b)
 127    that fact is critical for optimization purposes.  Assumes are a great
 128    prototyping mechanism, but they can have negative effects on both compile
 129    time and optimization effectiveness.  The former is fixable with enough
 130    effort, but the later is fairly fundamental to their designed purpose.
 131
 132
 133 Describing Language Specific Properties
 134 =======================================
 135
 136 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 along way to assisting the optimizer in reasoning about loop induction variables.
 137
 138 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.
 139
 140 #. Add nsw/nuw flags as appropriate.  Reasoning about overflow is
 141    generally hard for an optimizer so providing these facts from the frontend
 142    can be very impactful.
 143
 144 #. Use fast-math flags on floating point operations if legal.  If you don't
 145    need strict IEEE floating point semantics, there are a number of additional
 146    optimizations that can be performed.  This can be highly impactful for
 147    floating point intensive computations.
 148
 149 #. Use inbounds on geps.  This can help to disambiguate some aliasing queries.
 150
 151 #. Add noalias/align/dereferenceable/nonnull to function arguments and return
 152    values as appropriate
 153
 154 #. Mark functions as readnone/readonly or noreturn/nounwind when known.  The
 155    optimizer will try to infer these flags, but may not always be able to.
 156    Manual annotations are particularly important for external functions that
 157    the optimizer can not analyze.
 158
 159 #. Use the lifetime.start/lifetime.end and invariant.start/invariant.end
 160    intrinsics where possible.  Common profitable uses are for stack like data
 161    structures (thus allowing dead store elimination) and for describing
 162    life times of allocas (thus allowing smaller stack sizes).
 163
 164 #. Use pointer aliasing metadata, especially tbaa metadata, to communicate
 165    otherwise-non-deducible pointer aliasing facts
 166
 167 #. Mark invariant locations using !invariant.load and TBAA's constant flags
 168
 169 #. If you language uses range checks, consider using the IRCE pass.  It is not
 170    currently part of the standard pass order.
 171
 172 #. For languages with numerous rarely executed guard conditions (e.g. null
 173    checks, type checks, range checks) consider adding an extra execution or
 174    two of LoopUnswith and LICM to your pass order.  The standard pass order,
 175    which is tuned for C and C++ applications, may not be sufficient to remove
 176    all dischargeable checks from loops.
 177
 178 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.
 179
 180 Adding to this document
 181 =======================
 182
 183 If you run across a case that you feel deserves to be covered here, please send
 184 a patch to `llvm-commits
 185 <http://lists.llvm.org/mailman/listinfo/llvm-commits>`_ for review.
 186
 187 If you have questions on these items, please direct them to `llvm-dev
 188 <http://lists.llvm.org/mailman/listinfo/llvm-dev>`_.  The more relevant
 189 context you are able to give to your question, the more likely it is to be
 190 answered.
 191