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 **BDCE**
  42     Bit-tracking dead code elimination. Some bit-wise instructions (shifts,
  43     ands, ors, etc.) "kill" some of their input bits -- that is, they make it
  44     such that those bits can be either zero or one without affecting control or
  45     data flow of a program. The BDCE pass removes instructions that only
  46     compute these dead bits.
  47
  48 **BURS**
  49     Bottom Up Rewriting System --- A method of instruction selection for code
  50     generation.  An example is the `BURG
  51     <http://www.program-transformation.org/Transform/BURG>`_ tool.
  52
  53 C
  54 -
  55
  56 **CFI**
  57     Call Frame Information. Used in DWARF debug info and in C++ unwind info
  58     to show how the function prolog lays out the stack frame.
  59
  60 **CIE**
  61     Common Information Entry.  A kind of CFI used to reduce the size of FDEs.
  62     The compiler creates a CIE which contains the information common across all
  63     the FDEs.  Each FDE then points to its CIE.
  64
  65 **CSE**
  66     Common Subexpression Elimination. An optimization that removes common
  67     subexpression compuation. For example ``(a+b)*(a+b)`` has two subexpressions
  68     that are the same: ``(a+b)``. This optimization would perform the addition
  69     only once and then perform the multiply (but only if it's computationally
  70     correct/safe).
  71
  72 D
  73 -
  74
  75 **DAG**
  76     Directed Acyclic Graph
  77
  78 .. _derived pointer:
  79 .. _derived pointers:
  80
  81 **Derived Pointer**
  82     A pointer to the interior of an object, such that a garbage collector is
  83     unable to use the pointer for reachability analysis. While a derived pointer
  84     is live, the corresponding object pointer must be kept in a root, otherwise
  85     the collector might free the referenced object. With copying collectors,
  86     derived pointers pose an additional hazard that they may be invalidated at
  87     any `safe point`_. This term is used in opposition to `object pointer`_.
  88
  89 **DSA**
  90     Data Structure Analysis
  91
  92 **DSE**
  93     Dead Store Elimination
  94
  95 F
  96 -
  97
  98 **FCA**
  99     First Class Aggregate
 100
 101 **FDE**
 102     Frame Description Entry. A kind of CFI used to describe the stack frame of
 103     one function.
 104
 105 G
 106 -
 107
 108 **GC**
 109     Garbage Collection. The practice of using reachability analysis instead of
 110     explicit memory management to reclaim unused memory.
 111
 112 **GEP**
 113     ``GetElementPtr``. An LLVM IR instruction that is used to get the address
 114     of a subelement of an aggregate data structure. It is documented in detail
 115     `here <http://llvm.org/docs/GetElementPtr.html>`_.
 116
 117 **GVN**
 118     Global Value Numbering. GVN is a pass that partitions values computed by a
 119     function into congruence classes. Values ending up in the same congruence
 120     class are guaranteed to be the same for every execution of the program.
 121     In that respect, congruency is a compile-time approximation of equivalence
 122     of values at runtime.
 123
 124 H
 125 -
 126
 127 .. _heap:
 128
 129 **Heap**
 130     In garbage collection, the region of memory which is managed using
 131     reachability analysis.
 132
 133 I
 134 -
 135
 136 **IPA**
 137     Inter-Procedural Analysis. Refers to any variety of code analysis that
 138     occurs between procedures, functions or compilation units (modules).
 139
 140 **IPO**
 141     Inter-Procedural Optimization. Refers to any variety of code optimization
 142     that occurs between procedures, functions or compilation units (modules).
 143
 144 **ISel**
 145     Instruction Selection
 146
 147 L
 148 -
 149
 150 **LCSSA**
 151     Loop-Closed Static Single Assignment Form
 152
 153 **LGTM**
 154     "Looks Good To Me". In a review thread, this indicates that the
 155     reviewer thinks that the patch is okay to commit.
 156
 157 **LICM**
 158     Loop Invariant Code Motion
 159
 160 **LSDA**
 161     Language Specific Data Area.  C++ "zero cost" unwinding is built on top a
 162     generic unwinding mechanism.  As the unwinder walks each frame, it calls
 163     a "personality" function to do language specific analysis.  Each function's
 164     FDE points to an optional LSDA which is passed to the personality function.
 165     For C++, the LSDA contain info about the type and location of catch
 166     statements in that function.
 167
 168 **Load-VN**
 169     Load Value Numbering
 170
 171 **LTO**
 172     Link-Time Optimization
 173
 174 M
 175 -
 176
 177 **MC**
 178     Machine Code
 179
 180 N
 181 -
 182
 183 **NFC**
 184   "No functional change". Used in a commit message to indicate that a patch
 185   is a pure refactoring/cleanup.
 186   Usually used in the first line, so it is visible without opening the
 187   actual commit email.
 188
 189 O
 190 -
 191 .. _object pointer:
 192 .. _object pointers:
 193
 194 **Object Pointer**
 195     A pointer to an object such that the garbage collector is able to trace
 196     references contained within the object. This term is used in opposition to
 197     `derived pointer`_.
 198
 199 P
 200 -
 201
 202 **PR**
 203     Problem report. A bug filed on `the LLVM Bug Tracking System
 204     <https://bugs.llvm.org/enter_bug.cgi>`_.
 205
 206 **PRE**
 207     Partial Redundancy Elimination
 208
 209 R
 210 -
 211
 212 **RAUW**
 213
 214     Replace All Uses With. The functions ``User::replaceUsesOfWith()``,
 215     ``Value::replaceAllUsesWith()``, and
 216     ``Constant::replaceUsesOfWithOnConstant()`` implement the replacement of one
 217     Value with another by iterating over its def/use chain and fixing up all of
 218     the pointers to point to the new value.  See
 219     also `def/use chains <ProgrammersManual.html#iterating-over-def-use-use-def-chains>`_.
 220
 221 **Reassociation**
 222     Rearranging associative expressions to promote better redundancy elimination
 223     and other optimization.  For example, changing ``(A+B-A)`` into ``(B+A-A)``,
 224     permitting it to be optimized into ``(B+0)`` then ``(B)``.
 225
 226 .. _roots:
 227 .. _stack roots:
 228
 229 **Root**
 230     In garbage collection, a pointer variable lying outside of the `heap`_ from
 231     which the collector begins its reachability analysis. In the context of code
 232     generation, "root" almost always refers to a "stack root" --- a local or
 233     temporary variable within an executing function.
 234
 235 **RPO**
 236     Reverse postorder
 237
 238 S
 239 -
 240
 241 .. _safe point:
 242
 243 **Safe Point**
 244     In garbage collection, it is necessary to identify `stack roots`_ so that
 245     reachability analysis may proceed. It may be infeasible to provide this
 246     information for every instruction, so instead the information may is
 247     calculated only at designated safe points. With a copying collector,
 248     `derived pointers`_ must not be retained across safe points and `object
 249     pointers`_ must be reloaded from stack roots.
 250
 251 **SDISel**
 252     Selection DAG Instruction Selection.
 253
 254 **SCC**
 255     Strongly Connected Component
 256
 257 **SCCP**
 258     Sparse Conditional Constant Propagation
 259
 260 **SLP**
 261     Superword-Level Parallelism, same as :ref:`Basic-Block Vectorization
 262     <lexicon-bb-vectorization>`.
 263
 264 **Splat**
 265     Splat refers to a vector of identical scalar elements.
 266
 267     The term is based on the PowerPC Altivec instructions that provided
 268     this functionality in hardware. For example, "vsplth" and the corresponding
 269     software intrinsic "vec_splat()". Examples of other hardware names for this
 270     action include "duplicate" (ARM) and "broadcast" (x86).
 271
 272 **SRoA**
 273     Scalar Replacement of Aggregates
 274
 275 **SSA**
 276     Static Single Assignment
 277
 278 **Stack Map**
 279     In garbage collection, metadata emitted by the code generator which
 280     identifies `roots`_ within the stack frame of an executing function.
 281
 282 T
 283 -
 284
 285 **TBAA**
 286     Type-Based Alias Analysis
 287