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 **AST**
  19     Abstract Syntax Tree.
  20
  21     Due to Clang's influence (mostly the fact that parsing and semantic
  22     analysis are so intertwined for C and especially C++), the typical
  23     working definition of AST in the LLVM community is roughly "the
  24     compiler's first complete symbolic (as opposed to textual)
  25     representation of an input program".
  26     As such, an "AST" might be a more general graph instead of a "tree"
  27     (consider the symbolic representation for the type of a typical "linked
  28     list node"). This working definition is closer to what some authors
  29     call an "annotated abstract syntax tree".
  30
  31     Consult your favorite compiler book or search engine for more details.
  32
  33 B
  34 -
  35
  36 .. _lexicon-bb-vectorization:
  37
  38 **BB Vectorization**
  39     Basic-Block Vectorization
  40
  41 **BURS**
  42     Bottom Up Rewriting System --- A method of instruction selection for code
  43     generation.  An example is the `BURG
  44     <http://www.program-transformation.org/Transform/BURG>`_ tool.
  45
  46 C
  47 -
  48
  49 **CFI**
  50     Call Frame Information. Used in DWARF debug info and in C++ unwind info
  51     to show how the function prolog lays out the stack frame.
  52
  53 **CIE**
  54     Common Information Entry.  A kind of CFI used to reduce the size of FDEs.
  55     The compiler creates a CIE which contains the information common across all
  56     the FDEs.  Each FDE then points to its CIE.
  57
  58 **CSE**
  59     Common Subexpression Elimination. An optimization that removes common
  60     subexpression compuation. For example ``(a+b)*(a+b)`` has two subexpressions
  61     that are the same: ``(a+b)``. This optimization would perform the addition
  62     only once and then perform the multiply (but only if it's computationally
  63     correct/safe).
  64
  65 D
  66 -
  67
  68 **DAG**
  69     Directed Acyclic Graph
  70
  71 .. _derived pointer:
  72 .. _derived pointers:
  73
  74 **Derived Pointer**
  75     A pointer to the interior of an object, such that a garbage collector is
  76     unable to use the pointer for reachability analysis. While a derived pointer
  77     is live, the corresponding object pointer must be kept in a root, otherwise
  78     the collector might free the referenced object. With copying collectors,
  79     derived pointers pose an additional hazard that they may be invalidated at
  80     any `safe point`_. This term is used in opposition to `object pointer`_.
  81
  82 **DSA**
  83     Data Structure Analysis
  84
  85 **DSE**
  86     Dead Store Elimination
  87
  88 F
  89 -
  90
  91 **FCA**
  92     First Class Aggregate
  93
  94 **FDE**
  95     Frame Description Entry. A kind of CFI used to describe the stack frame of
  96     one function.
  97
  98 G
  99 -
 100
 101 **GC**
 102     Garbage Collection. The practice of using reachability analysis instead of
 103     explicit memory management to reclaim unused memory.
 104
 105 H
 106 -
 107
 108 .. _heap:
 109
 110 **Heap**
 111     In garbage collection, the region of memory which is managed using
 112     reachability analysis.
 113
 114 I
 115 -
 116
 117 **IPA**
 118     Inter-Procedural Analysis. Refers to any variety of code analysis that
 119     occurs between procedures, functions or compilation units (modules).
 120
 121 **IPO**
 122     Inter-Procedural Optimization. Refers to any variety of code optimization
 123     that occurs between procedures, functions or compilation units (modules).
 124
 125 **ISel**
 126     Instruction Selection
 127
 128 L
 129 -
 130
 131 **LCSSA**
 132     Loop-Closed Static Single Assignment Form
 133
 134 **LGTM**
 135     "Looks Good To Me". In a review thread, this indicates that the
 136     reviewer thinks that the patch is okay to commit.
 137
 138 **LICM**
 139     Loop Invariant Code Motion
 140
 141 **LSDA**
 142     Language Specific Data Area.  C++ "zero cost" unwinding is built on top a
 143     generic unwinding mechanism.  As the unwinder walks each frame, it calls
 144     a "personality" function to do language specific analysis.  Each function's
 145     FDE points to an optional LSDA which is passed to the personality function.
 146     For C++, the LSDA contain info about the type and location of catch
 147     statements in that function.
 148
 149 **Load-VN**
 150     Load Value Numbering
 151
 152 **LTO**
 153     Link-Time Optimization
 154
 155 M
 156 -
 157
 158 **MC**
 159     Machine Code
 160
 161 N
 162 -
 163
 164 **NFC**
 165   "No functional change". Used in a commit message to indicate that a patch
 166   is a pure refactoring/cleanup.
 167   Usually used in the first line, so it is visible without opening the
 168   actual commit email.
 169
 170 O
 171 -
 172 .. _object pointer:
 173 .. _object pointers:
 174
 175 **Object Pointer**
 176     A pointer to an object such that the garbage collector is able to trace
 177     references contained within the object. This term is used in opposition to
 178     `derived pointer`_.
 179
 180 P
 181 -
 182
 183 **PRE**
 184     Partial Redundancy Elimination
 185
 186 R
 187 -
 188
 189 **RAUW**
 190
 191     Replace All Uses With. The functions ``User::replaceUsesOfWith()``,
 192     ``Value::replaceAllUsesWith()``, and
 193     ``Constant::replaceUsesOfWithOnConstant()`` implement the replacement of one
 194     Value with another by iterating over its def/use chain and fixing up all of
 195     the pointers to point to the new value.  See
 196     also `def/use chains <ProgrammersManual.html#iterating-over-def-use-use-def-chains>`_.
 197
 198 **Reassociation**
 199     Rearranging associative expressions to promote better redundancy elimination
 200     and other optimization.  For example, changing ``(A+B-A)`` into ``(B+A-A)``,
 201     permitting it to be optimized into ``(B+0)`` then ``(B)``.
 202
 203 .. _roots:
 204 .. _stack roots:
 205
 206 **Root**
 207     In garbage collection, a pointer variable lying outside of the `heap`_ from
 208     which the collector begins its reachability analysis. In the context of code
 209     generation, "root" almost always refers to a "stack root" --- a local or
 210     temporary variable within an executing function.
 211
 212 **RPO**
 213     Reverse postorder
 214
 215 S
 216 -
 217
 218 .. _safe point:
 219
 220 **Safe Point**
 221     In garbage collection, it is necessary to identify `stack roots`_ so that
 222     reachability analysis may proceed. It may be infeasible to provide this
 223     information for every instruction, so instead the information may is
 224     calculated only at designated safe points. With a copying collector,
 225     `derived pointers`_ must not be retained across safe points and `object
 226     pointers`_ must be reloaded from stack roots.
 227
 228 **SDISel**
 229     Selection DAG Instruction Selection.
 230
 231 **SCC**
 232     Strongly Connected Component
 233
 234 **SCCP**
 235     Sparse Conditional Constant Propagation
 236
 237 **SLP**
 238     Superword-Level Parallelism, same as :ref:`Basic-Block Vectorization
 239     <lexicon-bb-vectorization>`.
 240
 241 **SRoA**
 242     Scalar Replacement of Aggregates
 243
 244 **SSA**
 245     Static Single Assignment
 246
 247 **Stack Map**
 248     In garbage collection, metadata emitted by the code generator which
 249     identifies `roots`_ within the stack frame of an executing function.
 250
 251 T
 252 -
 253
 254 **TBAA**
 255     Type-Based Alias Analysis
 256