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 **CSE**
     50     Common Subexpression Elimination. An optimization that removes common
     51     subexpression compuation. For example ``(a+b)*(a+b)`` has two subexpressions
     52     that are the same: ``(a+b)``. This optimization would perform the addition
     53     only once and then perform the multiply (but only if it's compulationally
     54     correct/safe).
     55 
     56 D
     57 -
     58 
     59 **DAG**
     60     Directed Acyclic Graph
     61 
     62 .. _derived pointer:
     63 .. _derived pointers:
     64 
     65 **Derived Pointer**
     66     A pointer to the interior of an object, such that a garbage collector is
     67     unable to use the pointer for reachability analysis. While a derived pointer
     68     is live, the corresponding object pointer must be kept in a root, otherwise
     69     the collector might free the referenced object. With copying collectors,
     70     derived pointers pose an additional hazard that they may be invalidated at
     71     any `safe point`_. This term is used in opposition to `object pointer`_.
     72 
     73 **DSA**
     74     Data Structure Analysis
     75 
     76 **DSE**
     77     Dead Store Elimination
     78 
     79 F
     80 -
     81 
     82 **FCA**
     83     First Class Aggregate
     84 
     85 G
     86 -
     87 
     88 **GC**
     89     Garbage Collection. The practice of using reachability analysis instead of
     90     explicit memory management to reclaim unused memory.
     91 
     92 H
     93 -
     94 
     95 .. _heap:
     96 
     97 **Heap**
     98     In garbage collection, the region of memory which is managed using
     99     reachability analysis.
    100 
    101 I
    102 -
    103 
    104 **IPA**
    105     Inter-Procedural Analysis. Refers to any variety of code analysis that
    106     occurs between procedures, functions or compilation units (modules).
    107 
    108 **IPO**
    109     Inter-Procedural Optimization. Refers to any variety of code optimization
    110     that occurs between procedures, functions or compilation units (modules).
    111 
    112 **ISel**
    113     Instruction Selection
    114 
    115 L
    116 -
    117 
    118 **LCSSA**
    119     Loop-Closed Static Single Assignment Form
    120 
    121 **LICM**
    122     Loop Invariant Code Motion
    123 
    124 **Load-VN**
    125     Load Value Numbering
    126 
    127 **LTO**
    128     Link-Time Optimization
    129 
    130 M
    131 -
    132 
    133 **MC**
    134     Machine Code
    135 
    136 O
    137 -
    138 .. _object pointer:
    139 .. _object pointers:
    140 
    141 **Object Pointer**
    142     A pointer to an object such that the garbage collector is able to trace
    143     references contained within the object. This term is used in opposition to
    144     `derived pointer`_.
    145 
    146 P
    147 -
    148 
    149 **PRE**
    150     Partial Redundancy Elimination
    151 
    152 R
    153 -
    154 
    155 **RAUW**
    156 
    157     Replace All Uses With. The functions ``User::replaceUsesOfWith()``,
    158     ``Value::replaceAllUsesWith()``, and
    159     ``Constant::replaceUsesOfWithOnConstant()`` implement the replacement of one
    160     Value with another by iterating over its def/use chain and fixing up all of
    161     the pointers to point to the new value.  See
    162     also `def/use chains <ProgrammersManual.html#iterate_chains>`_.
    163 
    164 **Reassociation**
    165     Rearranging associative expressions to promote better redundancy elimination
    166     and other optimization.  For example, changing ``(A+B-A)`` into ``(B+A-A)``,
    167     permitting it to be optimized into ``(B+0)`` then ``(B)``.
    168 
    169 .. _roots:
    170 .. _stack roots:
    171 
    172 **Root**
    173     In garbage collection, a pointer variable lying outside of the `heap`_ from
    174     which the collector begins its reachability analysis. In the context of code
    175     generation, "root" almost always refers to a "stack root" --- a local or
    176     temporary variable within an executing function.
    177 
    178 **RPO**
    179     Reverse postorder
    180 
    181 S
    182 -
    183 
    184 .. _safe point:
    185 
    186 **Safe Point**
    187     In garbage collection, it is necessary to identify `stack roots`_ so that
    188     reachability analysis may proceed. It may be infeasible to provide this
    189     information for every instruction, so instead the information may is
    190     calculated only at designated safe points. With a copying collector,
    191     `derived pointers`_ must not be retained across safe points and `object
    192     pointers`_ must be reloaded from stack roots.
    193 
    194 **SDISel**
    195     Selection DAG Instruction Selection.
    196 
    197 **SCC**
    198     Strongly Connected Component
    199 
    200 **SCCP**
    201     Sparse Conditional Constant Propagation
    202 
    203 **SLP**
    204     Superword-Level Parallelism, same as :ref:`Basic-Block Vectorization
    205     <lexicon-bb-vectorization>`.
    206 
    207 **SRoA**
    208     Scalar Replacement of Aggregates
    209 
    210 **SSA**
    211     Static Single Assignment
    212 
    213 **Stack Map**
    214     In garbage collection, metadata emitted by the code generator which
    215     identifies `roots`_ within the stack frame of an executing function.
    216 
    217 T
    218 -
    219 
    220 **TBAA**
    221     Type-Based Alias Analysis
    222 
    223