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
 189 **NFC**
 190   "No functional change". Used in a commit message to indicate that a patch
 191   is a pure refactoring/cleanup.
 192   Usually used in the first line, so it is visible without opening the
 193   actual commit email.
 194
 195 O
 196 -
 197 .. _object pointer:
 198 .. _object pointers:
 199
 200 **Object Pointer**
 201     A pointer to an object such that the garbage collector is able to trace
 202     references contained within the object. This term is used in opposition to
 203     `derived pointer`_.
 204
 205 P
 206 -
 207
 208 **PR**
 209     Problem report. A bug filed on `the LLVM Bug Tracking System
 210     <https://bugs.llvm.org/enter_bug.cgi>`_.
 211
 212 **PRE**
 213     Partial Redundancy Elimination
 214
 215 R
 216 -
 217
 218 **RAUW**
 219
 220     Replace All Uses With. The functions ``User::replaceUsesOfWith()``,
 221     ``Value::replaceAllUsesWith()``, and
 222     ``Constant::replaceUsesOfWithOnConstant()`` implement the replacement of one
 223     Value with another by iterating over its def/use chain and fixing up all of
 224     the pointers to point to the new value.  See
 225     also `def/use chains <ProgrammersManual.html#iterating-over-def-use-use-def-chains>`_.
 226
 227 **Reassociation**
 228     Rearranging associative expressions to promote better redundancy elimination
 229     and other optimization.  For example, changing ``(A+B-A)`` into ``(B+A-A)``,
 230     permitting it to be optimized into ``(B+0)`` then ``(B)``.
 231
 232 .. _roots:
 233 .. _stack roots:
 234
 235 **Root**
 236     In garbage collection, a pointer variable lying outside of the `heap`_ from
 237     which the collector begins its reachability analysis. In the context of code
 238     generation, "root" almost always refers to a "stack root" --- a local or
 239     temporary variable within an executing function.
 240
 241 **RPO**
 242     Reverse postorder
 243
 244 S
 245 -
 246
 247 .. _safe point:
 248
 249 **Safe Point**
 250     In garbage collection, it is necessary to identify `stack roots`_ so that
 251     reachability analysis may proceed. It may be infeasible to provide this
 252     information for every instruction, so instead the information may is
 253     calculated only at designated safe points. With a copying collector,
 254     `derived pointers`_ must not be retained across safe points and `object
 255     pointers`_ must be reloaded from stack roots.
 256
 257 **SDISel**
 258     Selection DAG Instruction Selection.
 259
 260 **SCC**
 261     Strongly Connected Component
 262
 263 **SCCP**
 264     Sparse Conditional Constant Propagation
 265
 266 **SLP**
 267     Superword-Level Parallelism, same as :ref:`Basic-Block Vectorization
 268     <lexicon-bb-vectorization>`.
 269
 270 **Splat**
 271     Splat refers to a vector of identical scalar elements.
 272
 273     The term is based on the PowerPC Altivec instructions that provided
 274     this functionality in hardware. For example, "vsplth" and the corresponding
 275     software intrinsic "vec_splat()". Examples of other hardware names for this
 276     action include "duplicate" (ARM) and "broadcast" (x86).
 277
 278 **SRoA**
 279     Scalar Replacement of Aggregates
 280
 281 **SSA**
 282     Static Single Assignment
 283
 284 **Stack Map**
 285     In garbage collection, metadata emitted by the code generator which
 286     identifies `roots`_ within the stack frame of an executing function.
 287
 288 T
 289 -
 290
 291 **TBAA**
 292     Type-Based Alias Analysis
 293