1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
| =====================================
Performance Tips for Frontend Authors
=====================================
.. contents::
:local:
:depth: 2
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.
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
loading individual fields from memory.
Aggregates that are smaller than the largest (performant) load or store
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
replace a sext with a zext when it can be proven safe, but if you have
information in your source language about the range of a integer value, it can
be profitable to use a zext rather than a sext.
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)
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.
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.
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.
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.
Other Things to Consider
^^^^^^^^^^^^^^^^^^^^^^^^
#. Use ptrtoint/inttoptr sparingly (they interfere with pointer aliasing
analysis), prefer GEPs
#. Prefer globals over inttoptr of a constant address - this gives you
dereferencability information. In MCJIT, use getSymbolAddress to provide
actual address.
#. Be wary of ordered and atomic memory operations. They are hard to optimize
and may not be well optimized by the current optimizer. Depending on your
source language, you may consider using fences instead.
#. If calling a function which is known to throw an exception (unwind), use
an invoke with a normal destination which contains an unreachable
instruction. This form conveys to the optimizer that the call returns
abnormally. For an invoke which neither returns normally or requires unwind
code in the current function, you can use a noreturn call instruction if
desired. This is generally not required because the optimizer will convert
an invoke with an unreachable unwind destination to a call instruction.
#. 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.
#. When generating code for loops, try to avoid terminating the header block of
the loop earlier than necessary. If the terminator of the loop header
block is a loop exiting conditional branch, the effectiveness of LICM will
be limited for loads not in the header. (This is due to the fact that LLVM
may not know such a load is safe to speculatively execute and thus can't
lift an otherwise loop invariant load unless it can prove the exiting
condition is not taken.) It can be profitable, in some cases, to emit such
instructions into the header even if they are not used along a rarely
executed path that exits the loop. This guidance specifically does not
apply if the condition which terminates the loop header is itself invariant,
or can be easily discharged by inspecting the loop index variables.
#. In hot loops, consider duplicating instructions from small basic blocks
which end in highly predictable terminators into their successor blocks.
If a hot successor block contains instructions which can be vectorized
with the duplicated ones, this can provide a noticeable throughput
improvement. Note that this is not always profitable and does involve a
potentially large increase in code size.
#. 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.
As a result, you may miss the opportunity to run other important
optimizations. Improvements to EarlyCSE to remove this issue are tracked in
Bug 23333.
#. Avoid using arithmetic intrinsics unless you are *required* by your source
language specification to emit a particular code sequence. The optimizer
is quite good at reasoning about general control flow and arithmetic, it is
not anywhere near as strong at reasoning about the various intrinsics. If
profitable for code generation purposes, the optimizer will likely form the
intrinsics itself late in the optimization pipeline. It is *very* rarely
profitable to emit these directly in the language frontend. This item
explicitly includes the use of the :ref:`overflow intrinsics <int_overflow>`.
#. Avoid using the :ref:`assume intrinsic <int_assume>` until you've
established that a) there's no other way to express the given fact and b)
that fact is critical for optimization purposes. Assumes are a great
prototyping mechanism, but they can have negative effects on both compile
time and optimization effectiveness. The former is fixable with enough
effort, but the later is fairly fundamental to their designed purpose.
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
=======================
If you run across a case that you feel deserves to be covered here, please send
a patch to `llvm-commits
<http://lists.llvm.org/mailman/listinfo/llvm-commits>`_ for review.
If you have questions on these items, please direct them to `llvm-dev
<http://lists.llvm.org/mailman/listinfo/llvm-dev>`_. The more relevant
context you are able to give to your question, the more likely it is to be
answered.
|