1.. _lexicon: 2 3================ 4The LLVM Lexicon 5================ 6 7.. note:: 8 9 This document is a work in progress! 10 11Definitions 12=========== 13 14A 15- 16 17**ADCE** 18 Aggressive Dead Code Elimination 19 20B 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 29C 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 39D 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 62F 63- 64 65**FCA** 66 First Class Aggregate 67 68G 69- 70 71**GC** 72 Garbage Collection. The practice of using reachability analysis instead of 73 explicit memory management to reclaim unused memory. 74 75H 76- 77 78.. _heap: 79 80**Heap** 81 In garbage collection, the region of memory which is managed using 82 reachability analysis. 83 84I 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 98L 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 113M 114- 115 116**MC** 117 Machine Code 118 119O 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 129P 130- 131 132**PRE** 133 Partial Redundancy Elimination 134 135R 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 164S 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