docs/Lexicon.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
   2 <html>
   3 <head>
   4   <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
   5   <title>The LLVM Lexicon</title>
   6   <link rel="stylesheet" href="llvm.css" type="text/css">
   7   <meta name="author" content="Various">
   8   <meta name="description"
   9   content="A glossary of terms used with the LLVM project.">
  10 </head>
  11 <body>
  12 <h1>The LLVM Lexicon</h1>
  13 <p class="doc_warning">NOTE: This document is a work in progress!</p>
  14 <!-- *********************************************************************** -->
  15 <h2>Table Of Contents</h2>
  16 <!-- *********************************************************************** -->
  17 <div>
  18   <table>
  19     <tr><th colspan="8"><b>- <a href="#A">A</a> -</b></th></tr>
  20     <tr>
  21       <td><a href="#ADCE">ADCE</a></td>
  22     </tr>
  23     <tr><th colspan="8"><b>- <a href="#B">B</a> -</b></th></tr>
  24     <tr>
  25       <td><a href="#BURS">BURS</a></td>
  26     </tr>
  27     <tr><th colspan="8"><b>- <a href="#C">C</a> -</b></th></tr>
  28     <tr>
  29       <td><a href="#CSE">CSE</a></td>
  30     </tr>
  31     <tr><th colspan="8"><b>- <a href="#D">D</a> -</b></th></tr>
  32     <tr>
  33       <td><a href="#DAG">DAG</a></td>
  34       <td><a href="#Derived_Pointer">Derived Pointer</a></td>
  35       <td><a href="#DSA">DSA</a></td>
  36       <td><a href="#DSE">DSE</a></td>
  37     </tr>
  38     <tr><th colspan="8"><b>- <a href="#G">G</a> -</b></th></tr>
  39     <tr>
  40       <td><a href="#GC">GC</a></td>
  41     </tr>
  42     <tr><th colspan="8"><b>- <a href="#I">I</a> -</b></th></tr>
  43     <tr>
  44       <td><a href="#IPA">IPA</a></td>
  45       <td><a href="#IPO">IPO</a></td>
  46       <td><a href="#ISel">ISel</a></td>
  47     </tr>
  48     <tr><th colspan="8"><b>- <a href="#L">L</a> -</b></th></tr>
  49     <tr>
  50       <td><a href="#LCSSA">LCSSA</a></td>
  51       <td><a href="#LICM">LICM</a></td>
  52       <td><a href="#Load-VN">Load-VN</a></td>
  53       <td><a href="#LTO">LTO</a></td>
  54     </tr>
  55     <tr><th colspan="8"><b>- <a href="#M">M</a> -</b></th></tr>
  56     <tr>
  57       <td><a href="#MC">MC</a></td>
  58     </tr>
  59     <tr><th colspan="8"><b>- <a href="#O">O</a> -</b></th></tr>
  60     <tr>
  61       <td><a href="#Object_Pointer">Object Pointer</a></td>
  62     </tr>
  63     <tr><th colspan="8"><b>- <a href="#P">P</a> -</b></th></tr>
  64     <tr>
  65       <td><a href="#PRE">PRE</a></td>
  66     </tr>
  67     <tr><th colspan="8"><b>- <a href="#R">R</a> -</b></th></tr>
  68     <tr>
  69       <td><a href="#RAUW">RAUW</a></td>
  70       <td><a href="#Reassociation">Reassociation</a></td>
  71       <td><a href="#Root">Root</a></td>
  72     </tr>
  73     <tr><th colspan="8"><b>- <a href="#S">S</a> -</b></th></tr>
  74     <tr>
  75       <td><a href="#Safe_Point">Safe Point</a></td>
  76       <td><a href="#SCC">SCC</a></td>
  77       <td><a href="#SCCP">SCCP</a></td>
  78       <td><a href="#SDISel">SDISel</a></td>
  79       <td><a href="#SRoA">SRoA</a></td>
  80       <td><a href="#Stack_Map">Stack Map</a></td>
  81     </tr>
  82   </table>
  83 </div>
  84
  85 <!-- *********************************************************************** -->
  86 <h2>Definitions</h2>
  87 <!-- *********************************************************************** -->
  88 <div>
  89 <!-- _______________________________________________________________________ -->
  90 <h3><a name="A">- A -</a></h3>
  91 <div>
  92   <dl>
  93     <dt><a name="ADCE"><b>ADCE</b></a></dt>
  94     <dd>Aggressive Dead Code Elimination</dd>
  95   </dl>
  96 </div>
  97 <!-- _______________________________________________________________________ -->
  98 <h3><a name="B">- B -</a></h3>
  99 <div>
 100   <dl>
 101     <dt><a name="BURS"><b>BURS</b></a></dt>
 102     <dd>Bottom Up Rewriting System&mdash;A method of instruction selection for
 103         code generation.  An example is the <a
 104 href="http://www.program-transformation.org/Transform/BURG">BURG</a> tool.</dd>
 105   </dl>
 106 </div>
 107 <!-- _______________________________________________________________________ -->
 108 <h3><a name="C">- C -</a></h3>
 109 <div>
 110   <dl>
 111     <dt><a name="CSE"><b>CSE</b></a></dt>
 112     <dd>Common Subexpression Elimination. An optimization that removes common
 113     subexpression compuation. For example <tt>(a+b)*(a+b)</tt> has two
 114     subexpressions that are the same: <tt>(a+b)</tt>. This optimization would
 115     perform the addition only once and then perform the multiply (but only if
 116     it's compulationally correct/safe).
 117   </dl>
 118 </div>
 119 <!-- _______________________________________________________________________ -->
 120 <h3><a name="D">- D -</a></h3>
 121 <div>
 122   <dl>
 123     <dt><a name="DAG"><b>DAG</b></a></dt>
 124     <dd>Directed Acyclic Graph</dd>
 125     <dt><a name="Derived_Pointer"><b>Derived Pointer</b></a></dt>
 126     <dd>A pointer to the interior of an object, such that a garbage collector
 127     is unable to use the pointer for reachability analysis. While a derived
 128     pointer is live, the corresponding object pointer must be kept in a root,
 129     otherwise the collector might free the referenced object. With copying
 130     collectors, derived pointers pose an additional hazard that they may be
 131     invalidated at any <a href="Safe_Point">safe point</a>. This term is used in
 132     opposition to <a href="#Object_Pointer">object pointer</a>.</dd>
 133     <dt><a name="DSA"><b>DSA</b></a></dt>
 134     <dd>Data Structure Analysis</dd>
 135     <dt><a name="DSE"><b>DSE</b></a></dt>
 136     <dd>Dead Store Elimination</dd>
 137   </dl>
 138 </div>
 139 <!-- _______________________________________________________________________ -->
 140 <h3><a name="G">- G -</a></h3>
 141 <div>
 142   <dl>
 143     <dt><a name="GC"><b>GC</b></a></dt>
 144     <dd>Garbage Collection. The practice of using reachability analysis instead
 145     of explicit memory management to reclaim unused memory.</dd>
 146   </dl>
 147 </div>
 148 <!-- _______________________________________________________________________ -->
 149 <h3><a name="H">- H -</a></h3>
 150 <div>
 151   <dl>
 152     <dt><a name="Heap"><b>Heap</b></a></dt>
 153     <dd>In garbage collection, the region of memory which is managed using
 154     reachability analysis.</dd>
 155   </dl>
 156 </div>
 157 <!-- _______________________________________________________________________ -->
 158 <h3><a name="I">- I -</a></h3>
 159 <div>
 160   <dl>
 161     <dt><a name="IPA"><b>IPA</b></a></dt>
 162     <dd>Inter-Procedural Analysis. Refers to any variety of code analysis that
 163     occurs between procedures, functions or compilation units (modules).</dd>
 164     <dt><a name="IPO"><b>IPO</b></a></dt>
 165     <dd>Inter-Procedural Optimization. Refers to any variety of code
 166     optimization that occurs between procedures, functions or compilation units
 167     (modules).</dd>
 168     <dt><a name="ISel"><b>ISel</b></a></dt>
 169     <dd>Instruction Selection.</dd>
 170   </dl>
 171 </div>
 172 <!-- _______________________________________________________________________ -->
 173 <h3><a name="L">- L -</a></h3>
 174 <div>
 175   <dl>
 176     <dt><a name="LCSSA"><b>LCSSA</b></a></dt>
 177     <dd>Loop-Closed Static Single Assignment Form</dd>
 178     <dt><a name="LICM"><b>LICM</b></a></dt>
 179     <dd>Loop Invariant Code Motion</dd>
 180     <dt><a name="Load-VN"><b>Load-VN</b></a></dt>
 181     <dd>Load Value Numbering</dd>
 182     <dt><a name="LTO"><b>LTO</b></a></dt>
 183     <dd>Link-Time Optimization</dd>
 184   </dl>
 185 </div>
 186 <!-- _______________________________________________________________________ -->
 187 <h3><a name="M">- M -</a></h3>
 188 <div>
 189   <dl>
 190     <dt><a name="MC"><b>MC</b></a></dt>
 191     <dd>Machine Code</dd>
 192   </dl>
 193 </div>
 194 <!-- _______________________________________________________________________ -->
 195 <h3><a name="O">- O -</a></h3>
 196 <div>
 197   <dl>
 198     <dt><a name="Object_Pointer"><b>Object Pointer</b></a></dt>
 199     <dd>A pointer to an object such that the garbage collector is able to trace
 200     references contained within the object. This term is used in opposition to
 201     <a href="#Derived_Pointer">derived pointer</a>.</dd>
 202   </dl>
 203 </div>
 204
 205 <!-- _______________________________________________________________________ -->
 206 <h3><a name="P">- P -</a></h3>
 207 <div>
 208   <dl>
 209     <dt><a name="PRE"><b>PRE</b></a></dt>
 210     <dd>Partial Redundancy Elimination</dd>
 211   </dl>
 212 </div>
 213
 214 <!-- _______________________________________________________________________ -->
 215 <h3><a name="R">- R -</a></h3>
 216 <div>
 217   <dl>
 218         <dt><a name="RAUW"><b>RAUW</b></a></dt> <dd>An abbreviation for Replace
 219         All Uses With. The functions User::replaceUsesOfWith(),
 220         Value::replaceAllUsesWith(), and Constant::replaceUsesOfWithOnConstant()
 221         implement the replacement of one Value with another by iterating over its
 222         def/use chain and fixing up all of the pointers to point to the new value.
 223         See also <a href="ProgrammersManual.html#iterate_chains">def/use chains</a>.
 224         </dd>
 225     <dt><a name="Reassociation"><b>Reassociation</b></a></dt> <dd>Rearranging
 226     associative expressions to promote better redundancy elimination and other
 227     optimization.  For example, changing (A+B-A) into (B+A-A), permitting it to
 228     be optimized into (B+0) then (B).</dd>
 229     <dt><a name="Root"><b>Root</b></a></dt> <dd>In garbage collection, a
 230     pointer variable lying outside of the <a href="#Heap">heap</a> from which
 231     the collector begins its reachability analysis. In the context of code
 232     generation, "root" almost always refers to a "stack root" -- a local or
 233     temporary variable within an executing function.</dd>
 234   </dl>
 235 </div>
 236
 237 <!-- _______________________________________________________________________ -->
 238 <h3><a name="S">- S -</a></h3>
 239 <div>
 240   <dl>
 241     <dt><a name="Safe_Point"><b>Safe Point</b></a></dt>
 242     <dd>In garbage collection, it is necessary to identify <a href="#Root">stack
 243     roots</a> so that reachability analysis may proceed. It may be infeasible to
 244     provide this information for every instruction, so instead the information
 245     may is calculated only at designated safe points. With a copying collector,
 246     <a href="#Derived_Pointers">derived pointers</a> must not be retained across
 247     safe points and <a href="#Object_Pointers">object pointers</a> must be
 248     reloaded from stack roots.</dd>
 249     <dt><a name="SDISel"><b>SDISel</b></a></dt>
 250     <dd>Selection DAG Instruction Selection.</dd>
 251     <dt><a name="SCC"><b>SCC</b></a></dt>
 252     <dd>Strongly Connected Component</dd>
 253     <dt><a name="SCCP"><b>SCCP</b></a></dt>
 254     <dd>Sparse Conditional Constant Propagation</dd>
 255     <dt><a name="SRoA"><b>SRoA</b></a></dt>
 256     <dd>Scalar Replacement of Aggregates</dd>
 257     <dt><a name="SSA"><b>SSA</b></a></dt>
 258     <dd>Static Single Assignment</dd>
 259     <dt><a name="Stack_Map"><b>Stack Map</b></a></dt>
 260     <dd>In garbage collection, metadata emitted by the code generator which
 261     identifies <a href="#Root">roots</a> within the stack frame of an executing
 262     function.</dd>
 263   </dl>
 264 </div>
 265
 266 </div>
 267 <!-- *********************************************************************** -->
 268 <hr>
 269 <address> <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 270  src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a><a
 271  href="http://validator.w3.org/check/referer"><img
 272  src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a><a
 273  href="http://llvm.org/">The LLVM Team</a><br>
 274 <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
 275 Last modified: $Date$
 276 </address>
 277 <!-- vim: sw=2
 278 -->
 279 </body>
 280 </html>