1.. _lexicon:
2
3================
4The LLVM Lexicon
5================
6
7.. note::
8
9    This document is a work in progress!
10
11Definitions
12===========
13
14A
15-
16
17**ADCE**
18    Aggressive Dead Code Elimination
19
20B
21-
22
23**BURS**
24
25    Bottom Up Rewriting System --- A method of instruction selection for code
26    generation.  An example is the `BURG
27    <http://www.program-transformation.org/Transform/BURG>`_ tool.
28
29C
30-
31
32**CSE**
33    Common Subexpression Elimination. An optimization that removes common
34    subexpression compuation. For example ``(a+b)*(a+b)`` has two subexpressions
35    that are the same: ``(a+b)``. This optimization would perform the addition
36    only once and then perform the multiply (but only if it's compulationally
37    correct/safe).
38
39D
40-
41
42**DAG**
43    Directed Acyclic Graph
44
45.. _derived pointer:
46.. _derived pointers:
47
48**Derived Pointer**
49    A pointer to the interior of an object, such that a garbage collector is
50    unable to use the pointer for reachability analysis. While a derived pointer
51    is live, the corresponding object pointer must be kept in a root, otherwise
52    the collector might free the referenced object. With copying collectors,
53    derived pointers pose an additional hazard that they may be invalidated at
54    any `safe point`_. This term is used in opposition to `object pointer`_.
55
56**DSA**
57    Data Structure Analysis
58
59**DSE**
60    Dead Store Elimination
61
62F
63-
64
65**FCA**
66    First Class Aggregate
67
68G
69-
70
71**GC**
72    Garbage Collection. The practice of using reachability analysis instead of
73    explicit memory management to reclaim unused memory.
74
75H
76-
77
78.. _heap:
79
80**Heap**
81    In garbage collection, the region of memory which is managed using
82    reachability analysis.
83
84I
85-
86
87**IPA**
88    Inter-Procedural Analysis. Refers to any variety of code analysis that
89    occurs between procedures, functions or compilation units (modules).
90
91**IPO**
92    Inter-Procedural Optimization. Refers to any variety of code optimization
93    that occurs between procedures, functions or compilation units (modules).
94
95**ISel**
96    Instruction Selection
97
98L
99-
100
101**LCSSA**
102    Loop-Closed Static Single Assignment Form
103
104**LICM**
105    Loop Invariant Code Motion
106
107**Load-VN**
108    Load Value Numbering
109
110**LTO**
111    Link-Time Optimization
112
113M
114-
115
116**MC**
117    Machine Code
118
119O
120-
121.. _object pointer:
122.. _object pointers:
123
124**Object Pointer**
125    A pointer to an object such that the garbage collector is able to trace
126    references contained within the object. This term is used in opposition to
127    `derived pointer`_.
128
129P
130-
131
132**PRE**
133    Partial Redundancy Elimination
134
135R
136-
137
138**RAUW**
139
140    Replace All Uses With. The functions ``User::replaceUsesOfWith()``,
141    ``Value::replaceAllUsesWith()``, and
142    ``Constant::replaceUsesOfWithOnConstant()`` implement the replacement of one
143    Value with another by iterating over its def/use chain and fixing up all of
144    the pointers to point to the new value.  See
145    also `def/use chains <ProgrammersManual.html#iterate_chains>`_.
146
147**Reassociation**
148    Rearranging associative expressions to promote better redundancy elimination
149    and other optimization.  For example, changing ``(A+B-A)`` into ``(B+A-A)``,
150    permitting it to be optimized into ``(B+0)`` then ``(B)``.
151
152.. _roots:
153.. _stack roots:
154
155**Root**
156    In garbage collection, a pointer variable lying outside of the `heap`_ from
157    which the collector begins its reachability analysis. In the context of code
158    generation, "root" almost always refers to a "stack root" --- a local or
159    temporary variable within an executing function.</dd>
160
161**RPO**
162    Reverse postorder
163
164S
165-
166
167.. _safe point:
168
169**Safe Point**
170    In garbage collection, it is necessary to identify `stack roots`_ so that
171    reachability analysis may proceed. It may be infeasible to provide this
172    information for every instruction, so instead the information may is
173    calculated only at designated safe points. With a copying collector,
174    `derived pointers`_ must not be retained across safe points and `object
175    pointers`_ must be reloaded from stack roots.
176
177**SDISel**
178    Selection DAG Instruction Selection.
179
180**SCC**
181    Strongly Connected Component
182
183**SCCP**
184    Sparse Conditional Constant Propagation
185
186**SRoA**
187    Scalar Replacement of Aggregates
188
189**SSA**
190    Static Single Assignment
191
192**Stack Map**
193    In garbage collection, metadata emitted by the code generator which
194    identifies `roots`_ within the stack frame of an executing function.
195