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 **LICM**
 135     Loop Invariant Code Motion
 136
 137 **LSDA**
 138     Language Specific Data Area.  C++ "zero cost" unwinding is built on top a
 139     generic unwinding mechanism.  As the unwinder walks each frame, it calls
 140     a "personality" function to do language specific analysis.  Each function's
 141     FDE points to an optional LSDA which is passed to the personality function.
 142     For C++, the LSDA contain info about the type and location of catch
 143     statements in that function.
 144
 145 **Load-VN**
 146     Load Value Numbering
 147
 148 **LTO**
 149     Link-Time Optimization
 150
 151 M
 152 -
 153
 154 **MC**
 155     Machine Code
 156
 157 N
 158 -
 159
 160 **NFC**
 161   "No functional change". Used in a commit message to indicate that a patch
 162   is a pure refactoring/cleanup.
 163   Usually used in the first line, so it is visible without opening the
 164   actual commit email.
 165
 166 O
 167 -
 168 .. _object pointer:
 169 .. _object pointers:
 170
 171 **Object Pointer**
 172     A pointer to an object such that the garbage collector is able to trace
 173     references contained within the object. This term is used in opposition to
 174     `derived pointer`_.
 175
 176 P
 177 -
 178
 179 **PRE**
 180     Partial Redundancy Elimination
 181
 182 R
 183 -
 184
 185 **RAUW**
 186
 187     Replace All Uses With. The functions ``User::replaceUsesOfWith()``,
 188     ``Value::replaceAllUsesWith()``, and
 189     ``Constant::replaceUsesOfWithOnConstant()`` implement the replacement of one
 190     Value with another by iterating over its def/use chain and fixing up all of
 191     the pointers to point to the new value.  See
 192     also `def/use chains <ProgrammersManual.html#iterating-over-def-use-use-def-chains>`_.
 193
 194 **Reassociation**
 195     Rearranging associative expressions to promote better redundancy elimination
 196     and other optimization.  For example, changing ``(A+B-A)`` into ``(B+A-A)``,
 197     permitting it to be optimized into ``(B+0)`` then ``(B)``.
 198
 199 .. _roots:
 200 .. _stack roots:
 201
 202 **Root**
 203     In garbage collection, a pointer variable lying outside of the `heap`_ from
 204     which the collector begins its reachability analysis. In the context of code
 205     generation, "root" almost always refers to a "stack root" --- a local or
 206     temporary variable within an executing function.
 207
 208 **RPO**
 209     Reverse postorder
 210
 211 S
 212 -
 213
 214 .. _safe point:
 215
 216 **Safe Point**
 217     In garbage collection, it is necessary to identify `stack roots`_ so that
 218     reachability analysis may proceed. It may be infeasible to provide this
 219     information for every instruction, so instead the information may is
 220     calculated only at designated safe points. With a copying collector,
 221     `derived pointers`_ must not be retained across safe points and `object
 222     pointers`_ must be reloaded from stack roots.
 223
 224 **SDISel**
 225     Selection DAG Instruction Selection.
 226
 227 **SCC**
 228     Strongly Connected Component
 229
 230 **SCCP**
 231     Sparse Conditional Constant Propagation
 232
 233 **SLP**
 234     Superword-Level Parallelism, same as :ref:`Basic-Block Vectorization
 235     <lexicon-bb-vectorization>`.
 236
 237 **SRoA**
 238     Scalar Replacement of Aggregates
 239
 240 **SSA**
 241     Static Single Assignment
 242
 243 **Stack Map**
 244     In garbage collection, metadata emitted by the code generator which
 245     identifies `roots`_ within the stack frame of an executing function.
 246
 247 T
 248 -
 249
 250 **TBAA**
 251     Type-Based Alias Analysis
 252