<tr><th colspan="2"><b>ANALYSIS PASSES</b></th></tr>
<tr><th>Option</th><th>Name</th></tr>
<tr><td><a href="#aa-eval">-aa-eval</a></td><td>Exhaustive Alias Analysis Precision Evaluator</td></tr>
-<tr><td><a href="#anders-aa">-anders-aa</a></td><td>Andersen's Interprocedural Alias Analysis</td></tr>
<tr><td><a href="#basicaa">-basicaa</a></td><td>Basic Alias Analysis (default AA impl)</td></tr>
<tr><td><a href="#basiccg">-basiccg</a></td><td>Basic CallGraph Construction</td></tr>
-<tr><td><a href="#basicvn">-basicvn</a></td><td>Basic Value Numbering (default GVN impl)</td></tr>
<tr><td><a href="#codegenprepare">-codegenprepare</a></td><td>Optimize for code generation</td></tr>
<tr><td><a href="#count-aa">-count-aa</a></td><td>Count Alias Analysis Query Responses</td></tr>
<tr><td><a href="#debug-aa">-debug-aa</a></td><td>AA use debugger</td></tr>
<tr><td><a href="#globalsmodref-aa">-globalsmodref-aa</a></td><td>Simple mod/ref analysis for globals</td></tr>
<tr><td><a href="#instcount">-instcount</a></td><td>Counts the various types of Instructions</td></tr>
<tr><td><a href="#intervals">-intervals</a></td><td>Interval Partition Construction</td></tr>
-<tr><td><a href="#load-vn">-load-vn</a></td><td>Load Value Numbering</td></tr>
<tr><td><a href="#loops">-loops</a></td><td>Natural Loop Construction</td></tr>
<tr><td><a href="#memdep">-memdep</a></td><td>Memory Dependence Analysis</td></tr>
<tr><td><a href="#no-aa">-no-aa</a></td><td>No Alias Analysis (always returns 'may' alias)</td></tr>
<tr><td><a href="#deadtypeelim">-deadtypeelim</a></td><td>Dead Type Elimination</td></tr>
<tr><td><a href="#die">-die</a></td><td>Dead Instruction Elimination</td></tr>
<tr><td><a href="#dse">-dse</a></td><td>Dead Store Elimination</td></tr>
-<tr><td><a href="#gcse">-gcse</a></td><td>Global Common Subexpression Elimination</td></tr>
<tr><td><a href="#globaldce">-globaldce</a></td><td>Dead Global Elimination</td></tr>
<tr><td><a href="#globalopt">-globalopt</a></td><td>Global Variable Optimizer</td></tr>
<tr><td><a href="#gvn">-gvn</a></td><td>Global Value Numbering</td></tr>
-<tr><td><a href="#gvnpre">-gvnpre</a></td><td>Global Value Numbering/Partial Redundancy Elimination</td></tr>
<tr><td><a href="#indmemrem">-indmemrem</a></td><td>Indirect Malloc and Free Removal</td></tr>
<tr><td><a href="#indvars">-indvars</a></td><td>Canonicalize Induction Variables</td></tr>
<tr><td><a href="#inline">-inline</a></td><td>Function Integration/Inlining</td></tr>
<tr><td><a href="#mem2reg">-mem2reg</a></td><td>Promote Memory to Register</td></tr>
<tr><td><a href="#memcpyopt">-memcpyopt</a></td><td>Optimize use of memcpy and friends</td></tr>
<tr><td><a href="#mergereturn">-mergereturn</a></td><td>Unify function exit nodes</td></tr>
-<tr><td><a href="#predsimplify">-predsimplify</a></td><td>Predicate Simplifier</td></tr>
<tr><td><a href="#prune-eh">-prune-eh</a></td><td>Remove unused exception handling info</td></tr>
-<tr><td><a href="#raiseallocs">-raiseallocs</a></td><td>Raise allocations from calls to instructions</td></tr>
<tr><td><a href="#reassociate">-reassociate</a></td><td>Reassociate expressions</td></tr>
<tr><td><a href="#reg2mem">-reg2mem</a></td><td>Demote all values to stack slots</td></tr>
<tr><td><a href="#scalarrepl">-scalarrepl</a></td><td>Scalar Replacement of Aggregates</td></tr>
Spadini, and Wojciech Stryjewski.</p>
</div>
-<!-------------------------------------------------------------------------- -->
-<div class="doc_subsection">
- <a name="anders-aa">Andersen's Interprocedural Alias Analysis</a>
-</div>
-<div class="doc_text">
- <p>
- This is an implementation of Andersen's interprocedural alias
- analysis
- </p>
-
- <p>
- In pointer analysis terms, this is a subset-based, flow-insensitive,
- field-sensitive, and context-insensitive algorithm pointer algorithm.
- </p>
-
- <p>
- This algorithm is implemented as three stages:
- </p>
-
- <ol>
- <li>Object identification.</li>
- <li>Inclusion constraint identification.</li>
- <li>Offline constraint graph optimization.</li>
- <li>Inclusion constraint solving.</li>
- </ol>
-
- <p>
- The object identification stage identifies all of the memory objects in the
- program, which includes globals, heap allocated objects, and stack allocated
- objects.
- </p>
-
- <p>
- The inclusion constraint identification stage finds all inclusion constraints
- in the program by scanning the program, looking for pointer assignments and
- other statements that effect the points-to graph. For a statement like
- <code><var>A</var> = <var>B</var></code>, this statement is processed to
- indicate that <var>A</var> can point to anything that <var>B</var> can point
- to. Constraints can handle copies, loads, and stores, and address taking.
- </p>
-
- <p>
- The offline constraint graph optimization portion includes offline variable
- substitution algorithms intended to computer pointer and location
- equivalences. Pointer equivalences are those pointers that will have the
- same points-to sets, and location equivalences are those variables that
- always appear together in points-to sets.
- </p>
-
- <p>
- The inclusion constraint solving phase iteratively propagates the inclusion
- constraints until a fixed point is reached. This is an O(<var>n</var>³)
- algorithm.
- </p>
-
- <p>
- Function constraints are handled as if they were structs with <var>X</var>
- fields. Thus, an access to argument <var>X</var> of function <var>Y</var> is
- an access to node index <code>getNode(<var>Y</var>) + <var>X</var></code>.
- This representation allows handling of indirect calls without any issues. To
- wit, an indirect call <code><var>Y</var>(<var>a</var>,<var>b</var>)</code> is
- equivalent to <code>*(<var>Y</var> + 1) = <var>a</var>, *(<var>Y</var> + 2) =
- <var>b</var></code>. The return node for a function <var>F</var> is always
- located at <code>getNode(<var>F</var>) + CallReturnPos</code>. The arguments
- start at <code>getNode(<var>F</var>) + CallArgPos</code>.
- </p>
-</div>
-
<!-------------------------------------------------------------------------- -->
<div class="doc_subsection">
<a name="basicaa">Basic Alias Analysis (default AA impl)</a>
<p>Yet to be written.</p>
</div>
-<!-------------------------------------------------------------------------- -->
-<div class="doc_subsection">
- <a name="basicvn">Basic Value Numbering (default Value Numbering impl)</a>
-</div>
-<div class="doc_text">
- <p>
- This is the default implementation of the <code>ValueNumbering</code>
- interface. It walks the SSA def-use chains to trivially identify
- lexically identical expressions. This does not require any ahead of time
- analysis, so it is a very fast default implementation.
- </p>
- <p>
- The ValueNumbering analysis passes are mostly deprecated. They are only used
- by the <a href="#gcse">Global Common Subexpression Elimination pass</a>, which
- is deprecated by the <a href="#gvn">Global Value Numbering pass</a> (which
- does its value numbering on its own).
- </p>
-</div>
-
<!-------------------------------------------------------------------------- -->
<div class="doc_subsection">
<a name="codegenprepare">Optimize for code generation</a>
</p>
</div>
-<!-------------------------------------------------------------------------- -->
-<div class="doc_subsection">
- <a name="load-vn">Load Value Numbering</a>
-</div>
-<div class="doc_text">
- <p>
- This pass value numbers load and call instructions. To do this, it finds
- lexically identical load instructions, and uses alias analysis to determine
- which loads are guaranteed to produce the same value. To value number call
- instructions, it looks for calls to functions that do not write to memory
- which do not have intervening instructions that clobber the memory that is
- read from.
- </p>
-
- <p>
- This pass builds off of another value numbering pass to implement value
- numbering for non-load and non-call instructions. It uses Alias Analysis so
- that it can disambiguate the load instructions. The more powerful these base
- analyses are, the more powerful the resultant value numbering will be.
- </p>
-</div>
-
<!-------------------------------------------------------------------------- -->
<div class="doc_subsection">
<a name="loops">Natural Loop Construction</a>
</p>
</div>
-<!-------------------------------------------------------------------------- -->
-<div class="doc_subsection">
- <a name="gcse">Global Common Subexpression Elimination</a>
-</div>
-<div class="doc_text">
- <p>
- This pass is designed to be a very quick global transformation that
- eliminates global common subexpressions from a function. It does this by
- using an existing value numbering analysis pass to identify the common
- subexpressions, eliminating them when possible.
- </p>
- <p>
- This pass is deprecated by the <a href="#gvn">Global Value Numbering pass</a>
- (which does a better job with its own value numbering).
- </p>
-</div>
-
<!-------------------------------------------------------------------------- -->
<div class="doc_subsection">
<a name="globaldce">Dead Global Elimination</a>
</div>
<div class="doc_text">
<p>
- This pass performs global value numbering to eliminate fully redundant
- instructions. It also performs simple dead load elimination.
- </p>
- <p>
- Note that this pass does the value numbering itself, it does not use the
- ValueNumbering analysis passes.
+ This pass performs global value numbering to eliminate fully and partially
+ redundant instructions. It also performs redundant load elimination.
</p>
</div>
-<!-------------------------------------------------------------------------- -->
-<div class="doc_subsection">
- <a name="gvnpre">Global Value Numbering/Partial Redundancy Elimination</a>
-</div>
-<div class="doc_text">
- <p>
- This pass performs a hybrid of global value numbering and partial redundancy
- elimination, known as GVN-PRE. It performs partial redundancy elimination on
- values, rather than lexical expressions, allowing a more comprehensive view
- the optimization. It replaces redundant values with uses of earlier
- occurences of the same value. While this is beneficial in that it eliminates
- unneeded computation, it also increases register pressure by creating large
- live ranges, and should be used with caution on platforms that are very
- sensitive to register pressure.
- </p>
- <p>
- Note that this pass does the value numbering itself, it does not use the
- ValueNumbering analysis passes.
- </p>
-</div>
<!-------------------------------------------------------------------------- -->
<div class="doc_subsection">
</p>
</div>
-<!-------------------------------------------------------------------------- -->
-<div class="doc_subsection">
- <a name="predsimplify">Predicate Simplifier</a>
-</div>
-<div class="doc_text">
- <p>
- Path-sensitive optimizer. In a branch where <tt>x == y</tt>, replace uses of
- <tt>x</tt> with <tt>y</tt>. Permits further optimization, such as the
- elimination of the unreachable call:
- </p>
-
-<blockquote><pre
->void test(int *p, int *q)
-{
- if (p != q)
- return;
-
- if (*p != *q)
- foo(); // unreachable
-}</pre></blockquote>
-</div>
-
<!-------------------------------------------------------------------------- -->
<div class="doc_subsection">
<a name="prune-eh">Remove unused exception handling info</a>
</p>
</div>
-<!-------------------------------------------------------------------------- -->
-<div class="doc_subsection">
- <a name="raiseallocs">Raise allocations from calls to instructions</a>
-</div>
-<div class="doc_text">
- <p>
- Converts <tt>@malloc</tt> and <tt>@free</tt> calls to <tt>malloc</tt> and
- <tt>free</tt> instructions.
- </p>
-</div>
-
<!-------------------------------------------------------------------------- -->
<div class="doc_subsection">
<a name="reassociate">Reassociate expressions</a>
<p>
This file demotes all registers to memory references. It is intented to be
the inverse of <a href="#mem2reg"><tt>-mem2reg</tt></a>. By converting to
- <tt>load</tt> instructions, the only values live accross basic blocks are
+ <tt>load</tt> instructions, the only values live across basic blocks are
<tt>alloca</tt> instructions and <tt>load</tt> instructions before
<tt>phi</tt> nodes. It is intended that this should make CFG hacking much
easier. To make later hacking easier, the entry block is split into two, such
integrals f.e.</li>
<li>All of the constants in a switch statement are of the correct type.</li>
<li>The code is in valid SSA form.</li>
- <li>It should be illegal to put a label into any other type (like a
- structure) or to return one. [except constant arrays!]</li>
+ <li>It is illegal to put a label into any other type (like a structure) or
+ to return one.</li>
<li>Only phi nodes can be self referential: <tt>%x = add i32 %x, %x</tt> is
invalid.</li>
<li>PHI nodes must have an entry for each predecessor, with no extras.</li>
<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>
+ src="http://jigsaw.w3.org/css-validator/images/vcss-blue" 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>
+ src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
<a href="mailto:rspencer@x10sys.com">Reid Spencer</a><br>
<a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
projects / oota-llvm.git / blobdiff