9 This document is a work in progress!
18 Aggressive Dead Code Elimination
23 .. _lexicon-bb-vectorization:
26 Basic-Block Vectorization
29 Bottom Up Rewriting System --- A method of instruction selection for code
30 generation. An example is the `BURG
31 <http://www.program-transformation.org/Transform/BURG>`_ tool.
37 Common Subexpression Elimination. An optimization that removes common
38 subexpression compuation. For example ``(a+b)*(a+b)`` has two subexpressions
39 that are the same: ``(a+b)``. This optimization would perform the addition
40 only once and then perform the multiply (but only if it's compulationally
47 Directed Acyclic Graph
53 A pointer to the interior of an object, such that a garbage collector is
54 unable to use the pointer for reachability analysis. While a derived pointer
55 is live, the corresponding object pointer must be kept in a root, otherwise
56 the collector might free the referenced object. With copying collectors,
57 derived pointers pose an additional hazard that they may be invalidated at
58 any `safe point`_. This term is used in opposition to `object pointer`_.
61 Data Structure Analysis
64 Dead Store Elimination
76 Garbage Collection. The practice of using reachability analysis instead of
77 explicit memory management to reclaim unused memory.
85 In garbage collection, the region of memory which is managed using
86 reachability analysis.
92 Inter-Procedural Analysis. Refers to any variety of code analysis that
93 occurs between procedures, functions or compilation units (modules).
96 Inter-Procedural Optimization. Refers to any variety of code optimization
97 that occurs between procedures, functions or compilation units (modules).
100 Instruction Selection
106 Loop-Closed Static Single Assignment Form
109 Loop Invariant Code Motion
115 Link-Time Optimization
129 A pointer to an object such that the garbage collector is able to trace
130 references contained within the object. This term is used in opposition to
137 Partial Redundancy Elimination
144 Replace All Uses With. The functions ``User::replaceUsesOfWith()``,
145 ``Value::replaceAllUsesWith()``, and
146 ``Constant::replaceUsesOfWithOnConstant()`` implement the replacement of one
147 Value with another by iterating over its def/use chain and fixing up all of
148 the pointers to point to the new value. See
149 also `def/use chains <ProgrammersManual.html#iterate_chains>`_.
152 Rearranging associative expressions to promote better redundancy elimination
153 and other optimization. For example, changing ``(A+B-A)`` into ``(B+A-A)``,
154 permitting it to be optimized into ``(B+0)`` then ``(B)``.
160 In garbage collection, a pointer variable lying outside of the `heap`_ from
161 which the collector begins its reachability analysis. In the context of code
162 generation, "root" almost always refers to a "stack root" --- a local or
163 temporary variable within an executing function.
174 In garbage collection, it is necessary to identify `stack roots`_ so that
175 reachability analysis may proceed. It may be infeasible to provide this
176 information for every instruction, so instead the information may is
177 calculated only at designated safe points. With a copying collector,
178 `derived pointers`_ must not be retained across safe points and `object
179 pointers`_ must be reloaded from stack roots.
182 Selection DAG Instruction Selection.
185 Strongly Connected Component
188 Sparse Conditional Constant Propagation
191 Superword-Level Parallelism, same as :ref:`Basic-Block Vectorization
192 <lexicon-bb-vectorization>`.
195 Scalar Replacement of Aggregates
198 Static Single Assignment
201 In garbage collection, metadata emitted by the code generator which
202 identifies `roots`_ within the stack frame of an executing function.
208 Type-Based Alias Analysis