llvm/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 computation. For example ``(a+b)*(a+b)`` has two
  68     subexpressions that are the same: ``(a+b)``. This optimization would
  69     perform the addition only once and then perform the multiply (but only if
  70     it's computationally 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 E
  96 -
  97
  98 **ento**
  99     This namespace houses the
 100     `Clang Static Analyzer <https://clang.llvm.org/docs/ClangStaticAnalyzer.html>`_.
 101     It is an abbreviation of `entomology <https://en.wikipedia.org/wiki/Entomology>`_.
 102
 103       *"Entomology is the scientific study of insects."*
 104
 105     In the past, this namespace had not only the name `GR` (aka. Graph Reachability)
 106     but also `entoSA`.
 107
 108 F
 109 -
 110
 111 **FCA**
 112     First Class Aggregate
 113
 114 **FDE**
 115     Frame Description Entry. A kind of CFI used to describe the stack frame of
 116     one function.
 117
 118 G
 119 -
 120
 121 **GC**
 122     Garbage Collection. The practice of using reachability analysis instead of
 123     explicit memory management to reclaim unused memory.
 124
 125 **GEP**
 126     ``GetElementPtr``. An LLVM IR instruction that is used to get the address
 127     of a subelement of an aggregate data structure. It is documented in detail
 128     `here <https://llvm.org/docs/GetElementPtr.html>`_.
 129
 130 **GVN**
 131     Global Value Numbering. GVN is a pass that partitions values computed by a
 132     function into congruence classes. Values ending up in the same congruence
 133     class are guaranteed to be the same for every execution of the program.
 134     In that respect, congruency is a compile-time approximation of equivalence
 135     of values at runtime.
 136
 137 H
 138 -
 139
 140 .. _heap:
 141
 142 **Heap**
 143     In garbage collection, the region of memory which is managed using
 144     reachability analysis.
 145
 146 I
 147 -
 148
 149 **ICE**
 150     Internal Compiler Error. This abbreviation is used to describe errors
 151     that occur in LLVM or Clang as they are compiling source code. For example,
 152     if a valid C++ source program were to trigger an assert in Clang when
 153     compiled, that could be referred to as an "ICE".
 154
 155 **IPA**
 156     Inter-Procedural Analysis. Refers to any variety of code analysis that
 157     occurs between procedures, functions or compilation units (modules).
 158
 159 **IPO**
 160     Inter-Procedural Optimization. Refers to any variety of code optimization
 161     that occurs between procedures, functions or compilation units (modules).
 162
 163 **ISel**
 164     Instruction Selection
 165
 166 L
 167 -
 168
 169 **LCSSA**
 170     Loop-Closed Static Single Assignment Form
 171
 172 **LGTM**
 173     "Looks Good To Me". In a review thread, this indicates that the
 174     reviewer thinks that the patch is okay to commit.
 175
 176 **LICM**
 177     Loop Invariant Code Motion
 178
 179 **LSDA**
 180     Language Specific Data Area.  C++ "zero cost" unwinding is built on top a
 181     generic unwinding mechanism.  As the unwinder walks each frame, it calls
 182     a "personality" function to do language specific analysis.  Each function's
 183     FDE points to an optional LSDA which is passed to the personality function.
 184     For C++, the LSDA contain info about the type and location of catch
 185     statements in that function.
 186
 187 **Load-VN**
 188     Load Value Numbering
 189
 190 **LTO**
 191     Link-Time Optimization
 192
 193 M
 194 -
 195
 196 **MC**
 197     Machine Code
 198
 199 N
 200 -
 201 .. _nfc:
 202
 203 **NFC**
 204   "No functional change". Used in a commit message to indicate that a patch
 205   is a pure refactoring/cleanup.
 206   Usually used in the first line, so it is visible without opening the
 207   actual commit email.
 208
 209 O
 210 -
 211 .. _object pointer:
 212 .. _object pointers:
 213
 214 **Object Pointer**
 215     A pointer to an object such that the garbage collector is able to trace
 216     references contained within the object. This term is used in opposition to
 217     `derived pointer`_.
 218
 219 P
 220 -
 221
 222 **PR**
 223     Problem report. A bug filed on `the LLVM Bug Tracking System
 224     <https://bugs.llvm.org/enter_bug.cgi>`_.
 225
 226 **PRE**
 227     Partial Redundancy Elimination
 228
 229 R
 230 -
 231
 232 **RAUW**
 233
 234     Replace All Uses With. The functions ``User::replaceUsesOfWith()``,
 235     ``Value::replaceAllUsesWith()``, and
 236     ``Constant::replaceUsesOfWithOnConstant()`` implement the replacement of one
 237     Value with another by iterating over its def/use chain and fixing up all of
 238     the pointers to point to the new value.  See
 239     also `def/use chains <ProgrammersManual.html#iterating-over-def-use-use-def-chains>`_.
 240
 241 **Reassociation**
 242     Rearranging associative expressions to promote better redundancy elimination
 243     and other optimization.  For example, changing ``(A+B-A)`` into ``(B+A-A)``,
 244     permitting it to be optimized into ``(B+0)`` then ``(B)``.
 245
 246 **RFC**
 247   Request for Comment. An email sent to a project mailing list in order to
 248   solicit feedback on a proposed change.
 249
 250 .. _roots:
 251 .. _stack roots:
 252
 253 **Root**
 254     In garbage collection, a pointer variable lying outside of the `heap`_ from
 255     which the collector begins its reachability analysis. In the context of code
 256     generation, "root" almost always refers to a "stack root" --- a local or
 257     temporary variable within an executing function.
 258
 259 **RPO**
 260     Reverse postorder
 261
 262 S
 263 -
 264
 265 .. _safe point:
 266
 267 **Safe Point**
 268     In garbage collection, it is necessary to identify `stack roots`_ so that
 269     reachability analysis may proceed. It may be infeasible to provide this
 270     information for every instruction, so instead the information is
 271     calculated only at designated safe points. With a copying collector,
 272     `derived pointers`_ must not be retained across safe points and `object
 273     pointers`_ must be reloaded from stack roots.
 274
 275 **SDISel**
 276     Selection DAG Instruction Selection.
 277
 278 **SCC**
 279     Strongly Connected Component
 280
 281 **SCCP**
 282     Sparse Conditional Constant Propagation
 283
 284 **SLP**
 285     Superword-Level Parallelism, same as :ref:`Basic-Block Vectorization
 286     <lexicon-bb-vectorization>`.
 287
 288 **Splat**
 289     Splat refers to a vector of identical scalar elements.
 290
 291     The term is based on the PowerPC Altivec instructions that provided
 292     this functionality in hardware. For example, "vsplth" and the corresponding
 293     software intrinsic "vec_splat()". Examples of other hardware names for this
 294     action include "duplicate" (ARM) and "broadcast" (x86).
 295
 296 **SRoA**
 297     Scalar Replacement of Aggregates
 298
 299 **SSA**
 300     Static Single Assignment
 301
 302 **Stack Map**
 303     In garbage collection, metadata emitted by the code generator which
 304     identifies `roots`_ within the stack frame of an executing function.
 305
 306 T
 307 -
 308
 309 **TBAA**
 310     Type-Based Alias Analysis
 311