1================ 2The LLVM Lexicon 3================ 4 5.. note:: 6 7 This document is a work in progress! 8 9Definitions 10=========== 11 12A 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 33B 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 46C 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 computationally 54 correct/safe). 55 56D 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 79F 80- 81 82**FCA** 83 First Class Aggregate 84 85G 86- 87 88**GC** 89 Garbage Collection. The practice of using reachability analysis instead of 90 explicit memory management to reclaim unused memory. 91 92H 93- 94 95.. _heap: 96 97**Heap** 98 In garbage collection, the region of memory which is managed using 99 reachability analysis. 100 101I 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 115L 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 130M 131- 132 133**MC** 134 Machine Code 135 136O 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 146P 147- 148 149**PRE** 150 Partial Redundancy Elimination 151 152R 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 181S 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 217T 218- 219 220**TBAA** 221 Type-Based Alias Analysis 222 223