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