1================
2The LLVM Lexicon
3================
4
5.. note::
6
7    This document is a work in progress!
8
9Definitions
10===========
11
12A
13-
14
15**ADCE**
16    Aggressive Dead Code Elimination
17
18**AST**
19    Abstract Syntax Tree.
20
21    Due to Clang's influence (mostly the fact that parsing and semantic
22    analysis are so intertwined for C and especially C++), the typical
23    working definition of AST in the LLVM community is roughly "the
24    compiler's first complete symbolic (as opposed to textual)
25    representation of an input program".
26    As such, an "AST" might be a more general graph instead of a "tree"
27    (consider the symbolic representation for the type of a typical "linked
28    list node"). This working definition is closer to what some authors
29    call an "annotated abstract syntax tree".
30
31    Consult your favorite compiler book or search engine for more details.
32
33B
34-
35
36.. _lexicon-bb-vectorization:
37
38**BB Vectorization**
39    Basic-Block Vectorization
40
41**BURS**
42    Bottom Up Rewriting System --- A method of instruction selection for code
43    generation.  An example is the `BURG
44    <http://www.program-transformation.org/Transform/BURG>`_ tool.
45
46C
47-
48
49**CFI**
50    Call Frame Information. Used in DWARF debug info and in C++ unwind info
51    to show how the function prolog lays out the stack frame.
52
53**CIE**
54    Common Information Entry.  A kind of CFI used to reduce the size of FDEs.
55    The compiler creates a CIE which contains the information common across all
56    the FDEs.  Each FDE then points to its CIE.
57
58**CSE**
59    Common Subexpression Elimination. An optimization that removes common
60    subexpression compuation. For example ``(a+b)*(a+b)`` has two subexpressions
61    that are the same: ``(a+b)``. This optimization would perform the addition
62    only once and then perform the multiply (but only if it's computationally
63    correct/safe).
64
65D
66-
67
68**DAG**
69    Directed Acyclic Graph
70
71.. _derived pointer:
72.. _derived pointers:
73
74**Derived Pointer**
75    A pointer to the interior of an object, such that a garbage collector is
76    unable to use the pointer for reachability analysis. While a derived pointer
77    is live, the corresponding object pointer must be kept in a root, otherwise
78    the collector might free the referenced object. With copying collectors,
79    derived pointers pose an additional hazard that they may be invalidated at
80    any `safe point`_. This term is used in opposition to `object pointer`_.
81
82**DSA**
83    Data Structure Analysis
84
85**DSE**
86    Dead Store Elimination
87
88F
89-
90
91**FCA**
92    First Class Aggregate
93
94**FDE**
95    Frame Description Entry. A kind of CFI used to describe the stack frame of
96    one function.
97
98G
99-
100
101**GC**
102    Garbage Collection. The practice of using reachability analysis instead of
103    explicit memory management to reclaim unused memory.
104
105H
106-
107
108.. _heap:
109
110**Heap**
111    In garbage collection, the region of memory which is managed using
112    reachability analysis.
113
114I
115-
116
117**IPA**
118    Inter-Procedural Analysis. Refers to any variety of code analysis that
119    occurs between procedures, functions or compilation units (modules).
120
121**IPO**
122    Inter-Procedural Optimization. Refers to any variety of code optimization
123    that occurs between procedures, functions or compilation units (modules).
124
125**ISel**
126    Instruction Selection
127
128L
129-
130
131**LCSSA**
132    Loop-Closed Static Single Assignment Form
133
134**LGTM**
135    "Looks Good To Me". In a review thread, this indicates that the
136    reviewer thinks that the patch is okay to commit.
137
138**LICM**
139    Loop Invariant Code Motion
140
141**LSDA**
142    Language Specific Data Area.  C++ "zero cost" unwinding is built on top a
143    generic unwinding mechanism.  As the unwinder walks each frame, it calls
144    a "personality" function to do language specific analysis.  Each function's
145    FDE points to an optional LSDA which is passed to the personality function.
146    For C++, the LSDA contain info about the type and location of catch
147    statements in that function.
148
149**Load-VN**
150    Load Value Numbering
151
152**LTO**
153    Link-Time Optimization
154
155M
156-
157
158**MC**
159    Machine Code
160
161N
162-
163
164**NFC**
165  "No functional change". Used in a commit message to indicate that a patch
166  is a pure refactoring/cleanup.
167  Usually used in the first line, so it is visible without opening the
168  actual commit email.
169
170O
171-
172.. _object pointer:
173.. _object pointers:
174
175**Object Pointer**
176    A pointer to an object such that the garbage collector is able to trace
177    references contained within the object. This term is used in opposition to
178    `derived pointer`_.
179
180P
181-
182
183**PRE**
184    Partial Redundancy Elimination
185
186R
187-
188
189**RAUW**
190
191    Replace All Uses With. The functions ``User::replaceUsesOfWith()``,
192    ``Value::replaceAllUsesWith()``, and
193    ``Constant::replaceUsesOfWithOnConstant()`` implement the replacement of one
194    Value with another by iterating over its def/use chain and fixing up all of
195    the pointers to point to the new value.  See
196    also `def/use chains <ProgrammersManual.html#iterating-over-def-use-use-def-chains>`_.
197
198**Reassociation**
199    Rearranging associative expressions to promote better redundancy elimination
200    and other optimization.  For example, changing ``(A+B-A)`` into ``(B+A-A)``,
201    permitting it to be optimized into ``(B+0)`` then ``(B)``.
202
203.. _roots:
204.. _stack roots:
205
206**Root**
207    In garbage collection, a pointer variable lying outside of the `heap`_ from
208    which the collector begins its reachability analysis. In the context of code
209    generation, "root" almost always refers to a "stack root" --- a local or
210    temporary variable within an executing function.
211
212**RPO**
213    Reverse postorder
214
215S
216-
217
218.. _safe point:
219
220**Safe Point**
221    In garbage collection, it is necessary to identify `stack roots`_ so that
222    reachability analysis may proceed. It may be infeasible to provide this
223    information for every instruction, so instead the information may is
224    calculated only at designated safe points. With a copying collector,
225    `derived pointers`_ must not be retained across safe points and `object
226    pointers`_ must be reloaded from stack roots.
227
228**SDISel**
229    Selection DAG Instruction Selection.
230
231**SCC**
232    Strongly Connected Component
233
234**SCCP**
235    Sparse Conditional Constant Propagation
236
237**SLP**
238    Superword-Level Parallelism, same as :ref:`Basic-Block Vectorization
239    <lexicon-bb-vectorization>`.
240
241**SRoA**
242    Scalar Replacement of Aggregates
243
244**SSA**
245    Static Single Assignment
246
247**Stack Map**
248    In garbage collection, metadata emitted by the code generator which
249    identifies `roots`_ within the stack frame of an executing function.
250
251T
252-
253
254**TBAA**
255    Type-Based Alias Analysis
256
257