docs/Lexicon.rst

   1 .. _lexicon:
   2
   3 ================
   4 The LLVM Lexicon
   5 ================
   6
   7 .. note::
   8
   9     This document is a work in progress!
  10
  11 Definitions
  12 ===========
  13
  14 A
  15 -
  16
  17 **ADCE**
  18     Aggressive Dead Code Elimination
  19
  20 B
  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
  29 C
  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
  39 D
  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
  62 F
  63 -
  64
  65 **FCA**
  66     First Class Aggregate
  67
  68 G
  69 -
  70
  71 **GC**
  72     Garbage Collection. The practice of using reachability analysis instead of
  73     explicit memory management to reclaim unused memory.
  74
  75 H
  76 -
  77
  78 .. _heap:
  79
  80 **Heap**
  81     In garbage collection, the region of memory which is managed using
  82     reachability analysis.
  83
  84 I
  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
  98 L
  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
 113 M
 114 -
 115
 116 **MC**
 117     Machine Code
 118
 119 O
 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
 129 P
 130 -
 131
 132 **PRE**
 133     Partial Redundancy Elimination
 134
 135 R
 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
 164 S
 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.