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