Home | History | Annotate | Download | only in docs 
      1 .. _lexicon:
      2 
      3 ================
      4 The LLVM Lexicon
      5 ================
      6 
      7 .. note::
      8 
      9     This document is a work in progress!
     10 
     11 Definitions
     12 ===========
     13 
     14 A
     15 -
     16 
     17 **ADCE**
     18     Aggressive Dead Code Elimination
     19 
     20 B
     21 -
     22 
     23 **BURS**
     24 
     25     Bottom Up Rewriting System --- A method of instruction selection for code
     26     generation.  An example is the `BURG
     27     <http://www.program-transformation.org/Transform/BURG>`_ tool.
     28 
     29 C
     30 -
     31 
     32 **CSE**
     33     Common Subexpression Elimination. An optimization that removes common
     34     subexpression compuation. For example ``(a+b)*(a+b)`` has two subexpressions
     35     that are the same: ``(a+b)``. This optimization would perform the addition
     36     only once and then perform the multiply (but only if it's compulationally
     37     correct/safe).
     38 
     39 D
     40 -
     41 
     42 **DAG**
     43     Directed Acyclic Graph
     44 
     45 .. _derived pointer:
     46 .. _derived pointers:
     47 
     48 **Derived Pointer**
     49     A pointer to the interior of an object, such that a garbage collector is
     50     unable to use the pointer for reachability analysis. While a derived pointer
     51     is live, the corresponding object pointer must be kept in a root, otherwise
     52     the collector might free the referenced object. With copying collectors,
     53     derived pointers pose an additional hazard that they may be invalidated at
     54     any `safe point`_. This term is used in opposition to `object pointer`_.
     55 
     56 **DSA**
     57     Data Structure Analysis
     58 
     59 **DSE**
     60     Dead Store Elimination
     61 
     62 F
     63 -
     64 
     65 **FCA**
     66     First Class Aggregate
     67 
     68 G
     69 -
     70 
     71 **GC**
     72     Garbage Collection. The practice of using reachability analysis instead of
     73     explicit memory management to reclaim unused memory.
     74 
     75 H
     76 -
     77 
     78 .. _heap:
     79 
     80 **Heap**
     81     In garbage collection, the region of memory which is managed using
     82     reachability analysis.
     83 
     84 I
     85 -
     86 
     87 **IPA**
     88     Inter-Procedural Analysis. Refers to any variety of code analysis that
     89     occurs between procedures, functions or compilation units (modules).
     90 
     91 **IPO**
     92     Inter-Procedural Optimization. Refers to any variety of code optimization
     93     that occurs between procedures, functions or compilation units (modules).
     94 
     95 **ISel**
     96     Instruction Selection
     97 
     98 L
     99 -
    100 
    101 **LCSSA**
    102     Loop-Closed Static Single Assignment Form
    103 
    104 **LICM**
    105     Loop Invariant Code Motion
    106 
    107 **Load-VN**
    108     Load Value Numbering
    109 
    110 **LTO**
    111     Link-Time Optimization
    112 
    113 M
    114 -
    115 
    116 **MC**
    117     Machine Code
    118 
    119 O
    120 -
    121 .. _object pointer:
    122 .. _object pointers:
    123 
    124 **Object Pointer**
    125     A pointer to an object such that the garbage collector is able to trace
    126     references contained within the object. This term is used in opposition to
    127     `derived pointer`_.
    128 
    129 P
    130 -
    131 
    132 **PRE**
    133     Partial Redundancy Elimination
    134 
    135 R
    136 -
    137 
    138 **RAUW**
    139 
    140     Replace All Uses With. The functions ``User::replaceUsesOfWith()``,
    141     ``Value::replaceAllUsesWith()``, and
    142     ``Constant::replaceUsesOfWithOnConstant()`` implement the replacement of one
    143     Value with another by iterating over its def/use chain and fixing up all of
    144     the pointers to point to the new value.  See
    145     also `def/use chains <ProgrammersManual.html#iterate_chains>`_.
    146 
    147 **Reassociation**
    148     Rearranging associative expressions to promote better redundancy elimination
    149     and other optimization.  For example, changing ``(A+B-A)`` into ``(B+A-A)``,
    150     permitting it to be optimized into ``(B+0)`` then ``(B)``.
    151 
    152 .. _roots:
    153 .. _stack roots:
    154 
    155 **Root**
    156     In garbage collection, a pointer variable lying outside of the `heap`_ from
    157     which the collector begins its reachability analysis. In the context of code
    158     generation, "root" almost always refers to a "stack root" --- a local or
    159     temporary variable within an executing function.</dd>
    160 
    161 **RPO**
    162     Reverse postorder
    163 
    164 S
    165 -
    166 
    167 .. _safe point:
    168 
    169 **Safe Point**
    170     In garbage collection, it is necessary to identify `stack roots`_ so that
    171     reachability analysis may proceed. It may be infeasible to provide this
    172     information for every instruction, so instead the information may is
    173     calculated only at designated safe points. With a copying collector,
    174     `derived pointers`_ must not be retained across safe points and `object
    175     pointers`_ must be reloaded from stack roots.
    176 
    177 **SDISel**
    178     Selection DAG Instruction Selection.
    179 
    180 **SCC**
    181     Strongly Connected Component
    182 
    183 **SCCP**
    184     Sparse Conditional Constant Propagation
    185 
    186 **SRoA**
    187     Scalar Replacement of Aggregates
    188 
    189 **SSA**
    190     Static Single Assignment
    191 
    192 **Stack Map**
    193     In garbage collection, metadata emitted by the code generator which
    194     identifies `roots`_ within the stack frame of an executing function.
    195