docs/Lexicon.html - platform/external/llvm - Gitiles

 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
 <html>
 <head>
   <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
   <title>The LLVM Lexicon</title>
   <link rel="stylesheet" href="llvm.css" type="text/css">
   <meta name="author" content="Various">
   <meta name="description"
   content="A glossary of terms used with the LLVM project.">
 </head>
 <body>
 <div class="doc_title">The LLVM Lexicon</div>
 <p class="doc_warning">NOTE: This document is a work in progress!</p>
 <!-- *********************************************************************** -->
 <div class="doc_section">Table Of Contents</div>
 <!-- *********************************************************************** -->
 <div class="doc_text">
   <table>
     <tr><th colspan="8"><b>- <a href="#A">A</a> -</b></th></tr>
     <tr>
       <td><a href="#ADCE">ADCE</a></td>
     </tr>
     <tr><th colspan="8"><b>- <a href="#B">B</a> -</b></th></tr>
     <tr>
       <td><a href="#BURS">BURS</a></td>
     </tr>
     <tr><th colspan="8"><b>- <a href="#C">C</a> -</b></th></tr>
     <tr>
       <td><a href="#CSE">CSE</a></td>
     </tr>
     <tr><th colspan="8"><b>- <a href="#D">D</a> -</b></th></tr>
     <tr>
       <td><a href="#DAG">DAG</a></td>
       <td><a href="#Derived_Pointer">Derived Pointer</a></td>
       <td><a href="#DSA">DSA</a></td>
       <td><a href="#DSE">DSE</a></td>
     </tr>
     <tr><th colspan="8"><b>- <a href="#G">G</a> -</b></th></tr>
       <td><a href="#GC">GC</a></td>
     </tr>
     <tr><th colspan="8"><b>- <a href="#I">I</a> -</b></th></tr>
     <tr>
       <td><a href="#IPA">IPA</a></td>
       <td><a href="#IPO">IPO</a></td>
       <td><a href="#ISel">ISel</a></td>
     </tr>
     <tr><th colspan="8"><b>- <a href="#L">L</a> -</b></th></tr>
     <tr>
       <td><a href="#LCSSA">LCSSA</a></td>
       <td><a href="#LICM">LICM</a></td>
       <td><a href="#Load-VN">Load-VN</a></td>
     </tr>
     <tr><th colspan="8"><b>- <a href="#O">O</a> -</b></th></tr>
     <tr>
       <td><a href="#Object_Pointer">Object Pointer</a></td>
     </tr>
     <tr><th colspan="8"><b>- <a href="#P">P</a> -</b></th></tr>
     <tr>
       <td><a href="#PRE">PRE</a></td>
     </tr>
     <tr><th colspan="8"><b>- <a href="#R">R</a> -</b></th></tr>
     <tr>
       <td><a href="#Reassociation">Reassociation</a></td>
       <td><a href="#Root">Root</a></td>
     </tr>
     <tr><th colspan="8"><b>- <a href="#S">S</a> -</b></th></tr>
     <tr>
       <td><a href="#Safe_Point">Safe Point</a></td>
       <td><a href="#SCC">SCC</a></td>
       <td><a href="#SCCP">SCCP</a></td>
       <td><a href="#SDISel">SDISel</a></td>
       <td><a href="#SRoA">SRoA</a></td>
       <td><a href="#Stack_Map">Stack Map</a></td>
     </tr>
   </table>
 </div>

 <!-- *********************************************************************** -->
 <div class="doc_section">Definitions</div>
 <!-- *********************************************************************** -->
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="A">- A -</a></div>
 <div class="doc_text">
   <dl>
     <dt><a name="ADCE"><b>ADCE</b></a></dt>
     <dd>Aggressive Dead Code Elimination</dd>
   </dl>
 </div>
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="B">- B -</a></div>
 <div class="doc_text">
   <dl>
     <dt><a name="BURS"><b>BURS</b></a></dt>
     <dd>Bottom Up Rewriting System - A method of instruction selection for
         code generation.  An example is the <a
 href="http://www.program-transformation.org/Transform/BURG">BURG</a> tool.</dd>
   </dl>
 </div>
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="C">- C -</a></div>
 <div class="doc_text">
   <dl>
     <dt><a name="CSE"><b>CSE</b></a></dt>
     <dd>Common Subexpression Elimination. An optimization that removes common
     subexpression compuation. For example <tt>(a+b)*(a+b)</tt> has two
     subexpressions that are the same: <tt>(a+b)</tt>. This optimization would
     perform the addition only once and then perform the multiply (but only if
     it's compulationally correct/safe).
   </dl>
 </div>
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="D">- D -</a></div>
 <div class="doc_text">
   <dl>
     <dt><a name="DAG"><b>DAG</b></a></dt>
     <dd>Directed Acyclic Graph</dd>
     <dt><a name="Derived_Pointer"><b>Derived Pointer</b></a></dt>
     <dd>A pointer to the interior of an object, such that a garbage collector
     is unable to use the pointer for reachability analysis. While a derived
     pointer is live, the corresponding object pointer must be kept in a root,
     otherwise the collector might free the referenced object. With copying
     collectors, derived pointers pose an additional hazard that they may be
     invalidated at any <a href="Safe_Point">safe point</a>. This term is used in
     opposition to <a href="#Object_Pointer">object pointer</a>.</dd>
     <dt><a name="DSA"><b>DSA</b></a></dt>
     <dd>Data Structure Analysis</dd>
     <dt><a name="DSE"><b>DSE</b></a></dt>
     <dd>Dead Store Elimination</dd>
   </dl>
 </div>
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="G">- G -</a></div>
 <div class="doc_text">
   <dl>
     <dt><a name="GC"><b>GC</b></a></dt>
     <dd>Garbage Collection. The practice of using reachability analysis instead
     of explicit memory management to reclaim unused memory.</dd>
   </dl>
 </div>
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="H">- H -</a></div>
 <div class="doc_text">
   <dl>
     <dt><a name="Heap"><b>Heap</b></a></dt>
     <dd>In garbage collection, the region of memory which is managed using
     reachability analysis.</dd>
   </dl>
 </div>
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="I">- I -</a></div>
 <div class="doc_text">
   <dl>
     <dt><a name="IPA"><b>IPA</b></a></dt>
     <dd>Inter-Procedural Analysis. Refers to any variety of code analysis that
     occurs between procedures, functions or compilation units (modules).</dd>
     <dt><a name="IPO"><b>IPO</b></a></dt>
     <dd>Inter-Procedural Optimization. Refers to any variety of code
     optimization that occurs between procedures, functions or compilation units
     (modules).</dd>
     <dt><a name="IPO"><b>ISel</b></a></dt>
     <dd>Instruction Selection.</dd>
   </dl>
 </div>
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="L">- L -</a></div>
 <div class="doc_text">
   <dl>
   	<dt><a name="LCSSA"><b>LCSSA</b></a></dt>
   	<dd>Loop-Closed Static Single Assignment Form</dd>
     <dt><a name="LICM"><b>LICM</b></a></dt>
     <dd>Loop Invariant Code Motion</dd>
     <dt><a name="Load-VN"><b>Load-VN</b></a></dt>
     <dd>Load Value Numbering</dd>
   </dl>
 </div>

 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="P">- O -</a></div>
 <div class="doc_text">
   <dl>
     <dt><a name="Object_Pointer"><b>Object Pointer</b></a></dt>
     <dd>A pointer to an object such that the garbage collector is able to trace
     references contained within the object. This term is used in opposition to
     <a href="#Derived_Pointer">derived pointer</a>.</dd>
   </dl>
 </div>

 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="P">- P -</a></div>
 <div class="doc_text">
   <dl>
     <dt><a name="PRE"><b>PRE</b></a></dt>
     <dd>Partial Redundancy Elimination</dd>
   </dl>
 </div>

 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="R">- R -</a></div>
 <div class="doc_text">
   <dl>
     <dt><a name="Reassociation"><b>Reassociation</b></a></dt> <dd>Rearranging
     associative expressions to promote better redundancy elimination and other
     optimization.  For example, changing (A+B-A) into (B+A-A), permitting it to
     be optimized into (B+0) then (B).</dd>
     <dt><a name="Root"><b>Root</b></a></dt> <dd>In garbage collection, a
     pointer variable lying outside of the <a href="#Heap">heap</a> from which
     the collector begins its reachability analysis. In the context of code
     generation, "root" almost always refers to a "stack root"&#151;a local or
     temporary variable within an executing function.</dd>
   </dl>
 </div>

 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="S">- S -</a></div>
 <div class="doc_text">
   <dl>
     <dt><a name="SCC"><b>Safe Point</b></a></dt>
     <dd>In garbage collection, it is necessary to identify <a href="#Root">stack
     roots</a> so that reachability analysis may proceed. It may be infeasible to
     provide this information for every instruction, so instead the information
     may is calculated only at designated safe points. With a copying collector,
     <a href="#Derived_Pointers">derived pointers</a> must not be retained across
     safe points and <a href="#Object_Pointers">object pointers</a> must be
     reloaded from stack roots.</dd>
     <dt><a name="SDISel"><b>SDISel</b></a></dt>
     <dd>Selection DAG Instruction Selection.</dd>
     <dt><a name="SCC"><b>SCC</b></a></dt>
     <dd>Strongly Connected Component</dd>
     <dt><a name="SCCP"><b>SCCP</b></a></dt>
     <dd>Sparse Conditional Constant Propagation</dd>
     <dt><a name="SRoA"><b>SRoA</b></a></dt>
     <dd>Scalar Replacement of Aggregates</dd>
     <dt><a name="SSA"><b>SSA</b></a></dt>
     <dd>Static Single Assignment</dd>
     <dt><a name="Stack_Map"><b>Stack Map</b></a></dt>
     <dd>In garbage collection, metadata emitted by the code generator which
     identifies <a href="#Root">roots</a> within the stack frame of an executing
     function.</dd>
   </dl>
 </div>
 <!-- *********************************************************************** -->
 <hr>
 <address> <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
  src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a><a
  href="http://validator.w3.org/check/referer"><img
  src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a><a
  href="http://llvm.org/">The LLVM Team</a><br>
 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
 Last modified: $Date$
 </address>
 <!-- vim: sw=2
 -->
 </body>
 </html>
	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
	<html>
	<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<title>The LLVM Lexicon</title>
	<link rel="stylesheet" href="llvm.css" type="text/css">
	<meta name="author" content="Various">
	<meta name="description"
	content="A glossary of terms used with the LLVM project.">
	</head>
	<body>
	<div class="doc_title">The LLVM Lexicon</div>
	<p class="doc_warning">NOTE: This document is a work in progress!</p>
	<!-- *********************************************************************** -->
	<div class="doc_section">Table Of Contents</div>
	<!-- *********************************************************************** -->
	<div class="doc_text">
	<table>
	<tr><th colspan="8"><b>- <a href="#A">A</a> -</b></th></tr>
	<tr>
	<td><a href="#ADCE">ADCE</a></td>
	</tr>
	<tr><th colspan="8"><b>- <a href="#B">B</a> -</b></th></tr>
	<tr>
	<td><a href="#BURS">BURS</a></td>
	</tr>
	<tr><th colspan="8"><b>- <a href="#C">C</a> -</b></th></tr>
	<tr>
	<td><a href="#CSE">CSE</a></td>
	</tr>
	<tr><th colspan="8"><b>- <a href="#D">D</a> -</b></th></tr>
	<tr>
	<td><a href="#DAG">DAG</a></td>
	<td><a href="#Derived_Pointer">Derived Pointer</a></td>
	<td><a href="#DSA">DSA</a></td>
	<td><a href="#DSE">DSE</a></td>
	</tr>
	<tr><th colspan="8"><b>- <a href="#G">G</a> -</b></th></tr>
	<td><a href="#GC">GC</a></td>
	</tr>
	<tr><th colspan="8"><b>- <a href="#I">I</a> -</b></th></tr>
	<tr>
	<td><a href="#IPA">IPA</a></td>
	<td><a href="#IPO">IPO</a></td>
	<td><a href="#ISel">ISel</a></td>
	</tr>
	<tr><th colspan="8"><b>- <a href="#L">L</a> -</b></th></tr>
	<tr>
	<td><a href="#LCSSA">LCSSA</a></td>
	<td><a href="#LICM">LICM</a></td>
	<td><a href="#Load-VN">Load-VN</a></td>
	</tr>
	<tr><th colspan="8"><b>- <a href="#O">O</a> -</b></th></tr>
	<tr>
	<td><a href="#Object_Pointer">Object Pointer</a></td>
	</tr>
	<tr><th colspan="8"><b>- <a href="#P">P</a> -</b></th></tr>
	<tr>
	<td><a href="#PRE">PRE</a></td>
	</tr>
	<tr><th colspan="8"><b>- <a href="#R">R</a> -</b></th></tr>
	<tr>
	<td><a href="#Reassociation">Reassociation</a></td>
	<td><a href="#Root">Root</a></td>
	</tr>
	<tr><th colspan="8"><b>- <a href="#S">S</a> -</b></th></tr>
	<tr>
	<td><a href="#Safe_Point">Safe Point</a></td>
	<td><a href="#SCC">SCC</a></td>
	<td><a href="#SCCP">SCCP</a></td>
	<td><a href="#SDISel">SDISel</a></td>
	<td><a href="#SRoA">SRoA</a></td>
	<td><a href="#Stack_Map">Stack Map</a></td>
	</tr>
	</table>
	</div>

	<!-- *********************************************************************** -->
	<div class="doc_section">Definitions</div>
	<!-- *********************************************************************** -->
	<!-- _______________________________________________________________________ -->
	<div class="doc_subsection"><a name="A">- A -</a></div>
	<div class="doc_text">
	<dl>
	<dt><a name="ADCE"><b>ADCE</b></a></dt>
	<dd>Aggressive Dead Code Elimination</dd>
	</dl>
	</div>
	<!-- _______________________________________________________________________ -->
	<div class="doc_subsection"><a name="B">- B -</a></div>
	<div class="doc_text">
	<dl>
	<dt><a name="BURS"><b>BURS</b></a></dt>
	<dd>Bottom Up Rewriting System - A method of instruction selection for
	code generation. An example is the <a
	href="http://www.program-transformation.org/Transform/BURG">BURG</a> tool.</dd>
	</dl>
	</div>
	<!-- _______________________________________________________________________ -->
	<div class="doc_subsection"><a name="C">- C -</a></div>
	<div class="doc_text">
	<dl>
	<dt><a name="CSE"><b>CSE</b></a></dt>
	<dd>Common Subexpression Elimination. An optimization that removes common
	subexpression compuation. For example <tt>(a+b)*(a+b)</tt> has two
	subexpressions that are the same: <tt>(a+b)</tt>. This optimization would
	perform the addition only once and then perform the multiply (but only if
	it's compulationally correct/safe).
	</dl>
	</div>
	<!-- _______________________________________________________________________ -->
	<div class="doc_subsection"><a name="D">- D -</a></div>
	<div class="doc_text">
	<dl>
	<dt><a name="DAG"><b>DAG</b></a></dt>
	<dd>Directed Acyclic Graph</dd>
	<dt><a name="Derived_Pointer"><b>Derived Pointer</b></a></dt>
	<dd>A pointer to the interior of an object, such that a garbage collector
	is unable to use the pointer for reachability analysis. While a derived
	pointer is live, the corresponding object pointer must be kept in a root,
	otherwise the collector might free the referenced object. With copying
	collectors, derived pointers pose an additional hazard that they may be
	invalidated at any <a href="Safe_Point">safe point</a>. This term is used in
	opposition to <a href="#Object_Pointer">object pointer</a>.</dd>
	<dt><a name="DSA"><b>DSA</b></a></dt>
	<dd>Data Structure Analysis</dd>
	<dt><a name="DSE"><b>DSE</b></a></dt>
	<dd>Dead Store Elimination</dd>
	</dl>
	</div>
	<!-- _______________________________________________________________________ -->
	<div class="doc_subsection"><a name="G">- G -</a></div>
	<div class="doc_text">
	<dl>
	<dt><a name="GC"><b>GC</b></a></dt>
	<dd>Garbage Collection. The practice of using reachability analysis instead
	of explicit memory management to reclaim unused memory.</dd>
	</dl>
	</div>
	<!-- _______________________________________________________________________ -->
	<div class="doc_subsection"><a name="H">- H -</a></div>
	<div class="doc_text">
	<dl>
	<dt><a name="Heap"><b>Heap</b></a></dt>
	<dd>In garbage collection, the region of memory which is managed using
	reachability analysis.</dd>
	</dl>
	</div>
	<!-- _______________________________________________________________________ -->
	<div class="doc_subsection"><a name="I">- I -</a></div>
	<div class="doc_text">
	<dl>
	<dt><a name="IPA"><b>IPA</b></a></dt>
	<dd>Inter-Procedural Analysis. Refers to any variety of code analysis that
	occurs between procedures, functions or compilation units (modules).</dd>
	<dt><a name="IPO"><b>IPO</b></a></dt>
	<dd>Inter-Procedural Optimization. Refers to any variety of code
	optimization that occurs between procedures, functions or compilation units
	(modules).</dd>
	<dt><a name="IPO"><b>ISel</b></a></dt>
	<dd>Instruction Selection.</dd>
	</dl>
	</div>
	<!-- _______________________________________________________________________ -->
	<div class="doc_subsection"><a name="L">- L -</a></div>
	<div class="doc_text">
	<dl>
	<dt><a name="LCSSA"><b>LCSSA</b></a></dt>
	<dd>Loop-Closed Static Single Assignment Form</dd>
	<dt><a name="LICM"><b>LICM</b></a></dt>
	<dd>Loop Invariant Code Motion</dd>
	<dt><a name="Load-VN"><b>Load-VN</b></a></dt>
	<dd>Load Value Numbering</dd>
	</dl>
	</div>

	<!-- _______________________________________________________________________ -->
	<div class="doc_subsection"><a name="P">- O -</a></div>
	<div class="doc_text">
	<dl>
	<dt><a name="Object_Pointer"><b>Object Pointer</b></a></dt>
	<dd>A pointer to an object such that the garbage collector is able to trace
	references contained within the object. This term is used in opposition to
	<a href="#Derived_Pointer">derived pointer</a>.</dd>
	</dl>
	</div>

	<!-- _______________________________________________________________________ -->
	<div class="doc_subsection"><a name="P">- P -</a></div>
	<div class="doc_text">
	<dl>
	<dt><a name="PRE"><b>PRE</b></a></dt>
	<dd>Partial Redundancy Elimination</dd>
	</dl>
	</div>

	<!-- _______________________________________________________________________ -->
	<div class="doc_subsection"><a name="R">- R -</a></div>
	<div class="doc_text">
	<dl>
	<dt><a name="Reassociation"><b>Reassociation</b></a></dt> <dd>Rearranging
	associative expressions to promote better redundancy elimination and other
	optimization. For example, changing (A+B-A) into (B+A-A), permitting it to
	be optimized into (B+0) then (B).</dd>
	<dt><a name="Root"><b>Root</b></a></dt> <dd>In garbage collection, a
	pointer variable lying outside of the <a href="#Heap">heap</a> from which
	the collector begins its reachability analysis. In the context of code
	generation, "root" almost always refers to a "stack root"a local or
	temporary variable within an executing function.</dd>
	</dl>
	</div>

	<!-- _______________________________________________________________________ -->
	<div class="doc_subsection"><a name="S">- S -</a></div>
	<div class="doc_text">
	<dl>
	<dt><a name="SCC"><b>Safe Point</b></a></dt>
	<dd>In garbage collection, it is necessary to identify <a href="#Root">stack
	roots</a> so that reachability analysis may proceed. It may be infeasible to
	provide this information for every instruction, so instead the information
	may is calculated only at designated safe points. With a copying collector,
	<a href="#Derived_Pointers">derived pointers</a> must not be retained across
	safe points and <a href="#Object_Pointers">object pointers</a> must be
	reloaded from stack roots.</dd>
	<dt><a name="SDISel"><b>SDISel</b></a></dt>
	<dd>Selection DAG Instruction Selection.</dd>
	<dt><a name="SCC"><b>SCC</b></a></dt>
	<dd>Strongly Connected Component</dd>
	<dt><a name="SCCP"><b>SCCP</b></a></dt>
	<dd>Sparse Conditional Constant Propagation</dd>
	<dt><a name="SRoA"><b>SRoA</b></a></dt>
	<dd>Scalar Replacement of Aggregates</dd>
	<dt><a name="SSA"><b>SSA</b></a></dt>
	<dd>Static Single Assignment</dd>
	<dt><a name="Stack_Map"><b>Stack Map</b></a></dt>
	<dd>In garbage collection, metadata emitted by the code generator which
	identifies <a href="#Root">roots</a> within the stack frame of an executing
	function.</dd>
	</dl>
	</div>
	<!-- *********************************************************************** -->
	<hr>
	<address> <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a><a
	href="http://validator.w3.org/check/referer"><img
	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a><a
	href="http://llvm.org/">The LLVM Team</a><br>
	<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
	Last modified: $Date$
	</address>
	<!-- vim: sw=2
	-->
	</body>
	</html>