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 .. _lexicon-bb-vectorization:
  24
  25 **BB Vectorization**
  26     Basic-Block Vectorization
  27
  28 **BURS**
  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.
  32
  33 C
  34 -
  35
  36 **CSE**
  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
  41     correct/safe).
  42
  43 D
  44 -
  45
  46 **DAG**
  47     Directed Acyclic Graph
  48
  49 .. _derived pointer:
  50 .. _derived pointers:
  51
  52 **Derived Pointer**
  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`_.
  59
  60 **DSA**
  61     Data Structure Analysis
  62
  63 **DSE**
  64     Dead Store Elimination
  65
  66 F
  67 -
  68
  69 **FCA**
  70     First Class Aggregate
  71
  72 G
  73 -
  74
  75 **GC**
  76     Garbage Collection. The practice of using reachability analysis instead of
  77     explicit memory management to reclaim unused memory.
  78
  79 H
  80 -
  81
  82 .. _heap:
  83
  84 **Heap**
  85     In garbage collection, the region of memory which is managed using
  86     reachability analysis.
  87
  88 I
  89 -
  90
  91 **IPA**
  92     Inter-Procedural Analysis. Refers to any variety of code analysis that
  93     occurs between procedures, functions or compilation units (modules).
  94
  95 **IPO**
  96     Inter-Procedural Optimization. Refers to any variety of code optimization
  97     that occurs between procedures, functions or compilation units (modules).
  98
  99 **ISel**
 100     Instruction Selection
 101
 102 L
 103 -
 104
 105 **LCSSA**
 106     Loop-Closed Static Single Assignment Form
 107
 108 **LICM**
 109     Loop Invariant Code Motion
 110
 111 **Load-VN**
 112     Load Value Numbering
 113
 114 **LTO**
 115     Link-Time Optimization
 116
 117 M
 118 -
 119
 120 **MC**
 121     Machine Code
 122
 123 O
 124 -
 125 .. _object pointer:
 126 .. _object pointers:
 127
 128 **Object Pointer**
 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
 131     `derived pointer`_.
 132
 133 P
 134 -
 135
 136 **PRE**
 137     Partial Redundancy Elimination
 138
 139 R
 140 -
 141
 142 **RAUW**
 143
 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>`_.
 150
 151 **Reassociation**
 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)``.
 155
 156 .. _roots:
 157 .. _stack roots:
 158
 159 **Root**
 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.
 164
 165 **RPO**
 166     Reverse postorder
 167
 168 S
 169 -
 170
 171 .. _safe point:
 172
 173 **Safe Point**
 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.
 180
 181 **SDISel**
 182     Selection DAG Instruction Selection.
 183
 184 **SCC**
 185     Strongly Connected Component
 186
 187 **SCCP**
 188     Sparse Conditional Constant Propagation
 189
 190 **SLP**
 191     Superword-Level Parallelism, same as :ref:`Basic-Block Vectorization
 192     <lexicon-bb-vectorization>`.
 193
 194 **SRoA**
 195     Scalar Replacement of Aggregates
 196
 197 **SSA**
 198     Static Single Assignment
 199
 200 **Stack Map**
 201     In garbage collection, metadata emitted by the code generator which
 202     identifies `roots`_ within the stack frame of an executing function.
 203
 204 T
 205 -
 206
 207 **TBAA**
 208     Type-Based Alias Analysis
 209