Bill Wendling | 5cda901 | 2012-06-20 10:36:41 +0000 | [diff] [blame] | 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 | |
Sean Silva | ccb51f9 | 2013-02-13 21:17:20 +0000 | [diff] [blame] | 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 | |
Bill Wendling | 5cda901 | 2012-06-20 10:36:41 +0000 | [diff] [blame] | 33 | B |
| 34 | - |
| 35 | |
Dmitri Gribenko | 76a130b | 2012-12-11 23:13:23 +0000 | [diff] [blame] | 36 | .. _lexicon-bb-vectorization: |
| 37 | |
Dmitri Gribenko | 549ea3a | 2012-10-13 17:34:49 +0000 | [diff] [blame] | 38 | **BB Vectorization** |
Dmitri Gribenko | 76a130b | 2012-12-11 23:13:23 +0000 | [diff] [blame] | 39 | Basic-Block Vectorization |
Bill Wendling | 5cda901 | 2012-06-20 10:36:41 +0000 | [diff] [blame] | 40 | |
Dmitri Gribenko | 549ea3a | 2012-10-13 17:34:49 +0000 | [diff] [blame] | 41 | **BURS** |
Bill Wendling | 5cda901 | 2012-06-20 10:36:41 +0000 | [diff] [blame] | 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 |
Dmitri Gribenko | 549ea3a | 2012-10-13 17:34:49 +0000 | [diff] [blame] | 176 | temporary variable within an executing function. |
Bill Wendling | 5cda901 | 2012-06-20 10:36:41 +0000 | [diff] [blame] | 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 | |
Dmitri Gribenko | 76a130b | 2012-12-11 23:13:23 +0000 | [diff] [blame] | 203 | **SLP** |
| 204 | Superword-Level Parallelism, same as :ref:`Basic-Block Vectorization |
| 205 | <lexicon-bb-vectorization>`. |
| 206 | |
Bill Wendling | 5cda901 | 2012-06-20 10:36:41 +0000 | [diff] [blame] | 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. |
Dmitri Gribenko | 549ea3a | 2012-10-13 17:34:49 +0000 | [diff] [blame] | 216 | |
| 217 | T |
| 218 | - |
| 219 | |
| 220 | **TBAA** |
| 221 | Type-Based Alias Analysis |
| 222 | |