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 **ICE**
 137     Internal Compiler Error. This abbreviation is used to describe errors
 138     that occur in LLVM or Clang as they are compiling source code. For example,
 139     if a valid C++ source program were to trigger an assert in Clang when
 140     compiled, that could be referred to as an "ICE".
 141
 142 **IPA**
 143     Inter-Procedural Analysis. Refers to any variety of code analysis that
 144     occurs between procedures, functions or compilation units (modules).
 145
 146 **IPO**
 147     Inter-Procedural Optimization. Refers to any variety of code optimization
 148     that occurs between procedures, functions or compilation units (modules).
 149
 150 **ISel**
 151     Instruction Selection
 152
 153 L
 154 -
 155
 156 **LCSSA**
 157     Loop-Closed Static Single Assignment Form
 158
 159 **LGTM**
 160     "Looks Good To Me". In a review thread, this indicates that the
 161     reviewer thinks that the patch is okay to commit.
 162
 163 **LICM**
 164     Loop Invariant Code Motion
 165
 166 **LSDA**
 167     Language Specific Data Area.  C++ "zero cost" unwinding is built on top a
 168     generic unwinding mechanism.  As the unwinder walks each frame, it calls
 169     a "personality" function to do language specific analysis.  Each function's
 170     FDE points to an optional LSDA which is passed to the personality function.
 171     For C++, the LSDA contain info about the type and location of catch
 172     statements in that function.
 173
 174 **Load-VN**
 175     Load Value Numbering
 176
 177 **LTO**
 178     Link-Time Optimization
 179
 180 M
 181 -
 182
 183 **MC**
 184     Machine Code
 185
 186 N
 187 -
 188 .. _nfc:
 189
 190 **NFC**
 191   "No functional change". Used in a commit message to indicate that a patch
 192   is a pure refactoring/cleanup.
 193   Usually used in the first line, so it is visible without opening the
 194   actual commit email.
 195
 196 O
 197 -
 198 .. _object pointer:
 199 .. _object pointers:
 200
 201 **Object Pointer**
 202     A pointer to an object such that the garbage collector is able to trace
 203     references contained within the object. This term is used in opposition to
 204     `derived pointer`_.
 205
 206 P
 207 -
 208
 209 **PR**
 210     Problem report. A bug filed on `the LLVM Bug Tracking System
 211     <https://bugs.llvm.org/enter_bug.cgi>`_.
 212
 213 **PRE**
 214     Partial Redundancy Elimination
 215
 216 R
 217 -
 218
 219 **RAUW**
 220
 221     Replace All Uses With. The functions ``User::replaceUsesOfWith()``,
 222     ``Value::replaceAllUsesWith()``, and
 223     ``Constant::replaceUsesOfWithOnConstant()`` implement the replacement of one
 224     Value with another by iterating over its def/use chain and fixing up all of
 225     the pointers to point to the new value.  See
 226     also `def/use chains <ProgrammersManual.html#iterating-over-def-use-use-def-chains>`_.
 227
 228 **Reassociation**
 229     Rearranging associative expressions to promote better redundancy elimination
 230     and other optimization.  For example, changing ``(A+B-A)`` into ``(B+A-A)``,
 231     permitting it to be optimized into ``(B+0)`` then ``(B)``.
 232
 233 .. _roots:
 234 .. _stack roots:
 235
 236 **Root**
 237     In garbage collection, a pointer variable lying outside of the `heap`_ from
 238     which the collector begins its reachability analysis. In the context of code
 239     generation, "root" almost always refers to a "stack root" --- a local or
 240     temporary variable within an executing function.
 241
 242 **RPO**
 243     Reverse postorder
 244
 245 S
 246 -
 247
 248 .. _safe point:
 249
 250 **Safe Point**
 251     In garbage collection, it is necessary to identify `stack roots`_ so that
 252     reachability analysis may proceed. It may be infeasible to provide this
 253     information for every instruction, so instead the information may is
 254     calculated only at designated safe points. With a copying collector,
 255     `derived pointers`_ must not be retained across safe points and `object
 256     pointers`_ must be reloaded from stack roots.
 257
 258 **SDISel**
 259     Selection DAG Instruction Selection.
 260
 261 **SCC**
 262     Strongly Connected Component
 263
 264 **SCCP**
 265     Sparse Conditional Constant Propagation
 266
 267 **SLP**
 268     Superword-Level Parallelism, same as :ref:`Basic-Block Vectorization
 269     <lexicon-bb-vectorization>`.
 270
 271 **Splat**
 272     Splat refers to a vector of identical scalar elements.
 273
 274     The term is based on the PowerPC Altivec instructions that provided
 275     this functionality in hardware. For example, "vsplth" and the corresponding
 276     software intrinsic "vec_splat()". Examples of other hardware names for this
 277     action include "duplicate" (ARM) and "broadcast" (x86).
 278
 279 **SRoA**
 280     Scalar Replacement of Aggregates
 281
 282 **SSA**
 283     Static Single Assignment
 284
 285 **Stack Map**
 286     In garbage collection, metadata emitted by the code generator which
 287     identifies `roots`_ within the stack frame of an executing function.
 288
 289 T
 290 -
 291
 292 **TBAA**
 293     Type-Based Alias Analysis
 294