docs/Lexicon.rst

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