<head>
<title>LLVM's Analysis and Transform Passes</title>
<link rel="stylesheet" href="llvm.css" type="text/css">
+ <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
m:^<tr><td><a href="#(.*)">-.*</a></td><td>.*</td></tr>$: or next;
$order{$1} = sprintf("%03d", 1 + int %order);
}
-open HELP, "../Release/bin/opt --help|" or die "open: opt --help: $!\n";
+open HELP, "../Release/bin/opt -help|" or die "open: opt -help: $!\n";
while (<HELP>) {
m:^ -([^ ]+) +- (.*)$: or next;
my $o = $order{$1};
print @x, @y;
EOT
+This (real) one-liner can also be helpful when converting comments to HTML:
+
+perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print " <p>\n" if !$on && $_ =~ /\S/; print " </p>\n" if $on && $_ =~ /^\s*$/; print " $_\n"; $on = ($_ =~ /\S/); } print " </p>\n" if $on'
+
-->
<div class="doc_title">LLVM's Analysis and Transform Passes</div>
</ol>
<div class="doc_author">
- <p>Written by <a href="mailto:rspencer@x10sys.com">Reid Spencer</a></p>
+ <p>Written by <a href="mailto:rspencer@x10sys.com">Reid Spencer</a>
+ and Gordon Henriksen</p>
</div>
<!-- ======================================================================= -->
</div>
<div class="doc_text" >
<table>
-<tr><th colspan="3"><b>ANALYSIS PASSES</b></th></tr>
-<tr><th>Option</th><th>Name</th><th>Directory</th></tr>
+<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="#domtree">-domtree</a></td><td>Dominator Tree Construction</td></tr>
<tr><td><a href="#externalfnconstants">-externalfnconstants</a></td><td>Print external fn callsites passed constants</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="#gvn">-gvn</a></td><td>Global Value Numbering</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="#targetdata">-targetdata</a></td><td>Target Data Layout</td></tr>
-<tr><th colspan="3"><b>TRANSFORM PASSES</b></th></tr>
-<tr><th>Option</th><th>Name</th><th>Directory</th></tr>
+<tr><th colspan="2"><b>TRANSFORM PASSES</b></th></tr>
+<tr><th>Option</th><th>Name</th></tr>
<tr><td><a href="#adce">-adce</a></td><td>Aggressive Dead Code Elimination</td></tr>
<tr><td><a href="#argpromotion">-argpromotion</a></td><td>Promote 'by reference' arguments to scalars</td></tr>
<tr><td><a href="#block-placement">-block-placement</a></td><td>Profile Guided Basic Block Placement</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="#tailduplicate">-tailduplicate</a></td><td>Tail Duplication</td></tr>
-<tr><th colspan="3"><b>UTILITY PASSES</b></th></tr>
-<tr><th>Option</th><th>Name</th><th>Directory</th></tr>
+<tr><th colspan="2"><b>UTILITY PASSES</b></th></tr>
+<tr><th>Option</th><th>Name</th></tr>
<tr><td><a href="#deadarghaX0r">-deadarghaX0r</a></td><td>Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)</td></tr>
<tr><td><a href="#extract-blocks">-extract-blocks</a></td><td>Extract Basic Blocks From Module (for bugpoint use)</td></tr>
<tr><td><a href="#emitbitcode">-emitbitcode</a></td><td>Bitcode Writer</td></tr>
<a name="aa-eval">Exhaustive Alias Analysis Precision Evaluator</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>This is a simple N^2 alias analysis accuracy evaluator.
+ Basically, for each function in the program, it simply queries to see how the
+ alias analysis implementation answers alias queries between each pair of
+ pointers in the function.</p>
+
+ <p>This is inspired and adapted from code by: Naveen Neelakantam, Francesco
+ Spadini, and Wojciech Stryjewski.</p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="anders-aa">Andersen's Interprocedural Alias Analysis</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <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>
<!-------------------------------------------------------------------------- -->
<a name="basicaa">Basic Alias Analysis (default AA impl)</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This is the default implementation of the Alias Analysis interface
+ that simply implements a few identities (two different globals cannot alias,
+ etc), but otherwise does no analysis.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="basicvn">Basic Value Numbering (default GVN impl)</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <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>
</div>
<!-------------------------------------------------------------------------- -->
<a name="callgraph">Print a call graph</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass, only available in <code>opt</code>, prints the call graph to
+ standard output in a human-readable form.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="callscc">Print SCCs of the Call Graph</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass, only available in <code>opt</code>, prints the SCCs of the call
+ graph to standard output in a human-readable form.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="cfgscc">Print SCCs of each function CFG</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass, only available in <code>opt</code>, prints the SCCs of each
+ function CFG to standard output in a human-readable form.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="codegenprepare">Optimize for code generation</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass munges the code in the input function to better prepare it for
+ SelectionDAG-based code generation. This works around limitations in it's
+ basic-block-at-a-time approach. It should eventually be removed.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="count-aa">Count Alias Analysis Query Responses</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ A pass which can be used to count how many alias queries
+ are being made and how the alias analysis implementation being used responds.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="debug-aa">AA use debugger</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This simple pass checks alias analysis users to ensure that if they
+ create a new value, they do not query AA without informing it of the value.
+ It acts as a shim over any other AA pass you want.
+ </p>
+
+ <p>
+ Yes keeping track of every value in the program is expensive, but this is
+ a debugging pass.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="domfrontier">Dominance Frontier Construction</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass is a simple dominator construction algorithm for finding forward
+ dominator frontiers.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="domtree">Dominator Tree Construction</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass is a simple dominator construction algorithm for finding forward
+ dominators.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="externalfnconstants">Print external fn callsites passed constants</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass, only available in <code>opt</code>, prints out call sites to
+ external functions that are called with constant arguments. This can be
+ useful when looking for standard library functions we should constant fold
+ or handle in alias analyses.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="globalsmodref-aa">Simple mod/ref analysis for globals</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
-</div>
-
-<!-------------------------------------------------------------------------- -->
-<div class="doc_subsection">
- <a name="gvn">Global Value Numbering</a>
-</div>
-<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This simple pass provides alias and mod/ref information for global values
+ that do not have their address taken, and keeps track of whether functions
+ read or write memory (are "pure"). For this simple (but very common) case,
+ we can provide pretty accurate and useful information.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="instcount">Counts the various types of Instructions</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass collects the count of all instructions and reports them
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="intervals">Interval Partition Construction</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This analysis calculates and represents the interval partition of a function,
+ or a preexisting interval partition.
+ </p>
+
+ <p>
+ In this way, the interval partition may be used to reduce a flow graph down
+ to its degenerate single node interval partition (unless it is irreducible).
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="load-vn">Load Value Numbering</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <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>
<!-------------------------------------------------------------------------- -->
<a name="loops">Natural Loop Construction</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This analysis is used to identify natural loops and determine the loop depth
+ of various nodes of the CFG. Note that the loops identified may actually be
+ several natural loops that share the same header node... not just a single
+ natural loop.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="memdep">Memory Dependence Analysis</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ An analysis that determines, for a given memory operation, what preceding
+ memory operations it depends on. It builds on alias analysis information, and
+ tries to provide a lazy, caching interface to a common kind of alias
+ information query.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="no-aa">No Alias Analysis (always returns 'may' alias)</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Always returns "I don't know" for alias queries. NoAA is unlike other alias
+ analysis implementations, in that it does not chain to a previous analysis. As
+ such it doesn't follow many of the rules that other alias analyses must.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="no-profile">No Profile Information</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ The default "no profile" implementation of the abstract
+ <code>ProfileInfo</code> interface.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="postdomfrontier">Post-Dominance Frontier Construction</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass is a simple post-dominator construction algorithm for finding
+ post-dominator frontiers.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="postdomtree">Post-Dominator Tree Construction</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass is a simple post-dominator construction algorithm for finding
+ post-dominators.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="print">Print function to stderr</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ The <code>PrintFunctionPass</code> class is designed to be pipelined with
+ other <code>FunctionPass</code>es, and prints out the functions of the module
+ as they are processed.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="print-callgraph">Print Call Graph to 'dot' file</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass, only available in <code>opt</code>, prints the call graph into a
+ <code>.dot</code> graph. This graph can then be processed with the "dot" tool
+ to convert it to postscript or some other suitable format.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="print-cfg">Print CFG of function to 'dot' file</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass, only available in <code>opt</code>, prints the control flow graph
+ into a <code>.dot</code> graph. This graph can then be processed with the
+ "dot" tool to convert it to postscript or some other suitable format.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="print-cfg-only">Print CFG of function to 'dot' file (with no function bodies)</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass, only available in <code>opt</code>, prints the control flow graph
+ into a <code>.dot</code> graph, omitting the function bodies. This graph can
+ then be processed with the "dot" tool to convert it to postscript or some
+ other suitable format.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="printm">Print module to stderr</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass simply prints out the entire module when it is executed.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="printusedtypes">Find Used Types</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass is used to seek out all of the types in use by the program. Note
+ that this analysis explicitly does not include types only used by the symbol
+ table.
</div>
<!-------------------------------------------------------------------------- -->
<a name="profile-loader">Load profile information from llvmprof.out</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ A concrete implementation of profiling information that loads the information
+ from a profile dump file.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="scalar-evolution">Scalar Evolution Analysis</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ The <code>ScalarEvolution</code> analysis can be used to analyze and
+ catagorize scalar expressions in loops. It specializes in recognizing general
+ induction variables, representing them with the abstract and opaque
+ <code>SCEV</code> class. Given this analysis, trip counts of loops and other
+ important properties can be obtained.
+ </p>
+
+ <p>
+ This analysis is primarily useful for induction variable substitution and
+ strength reduction.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="targetdata">Target Data Layout</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>Provides other passes access to information on how the size and alignment
+ required by the the target ABI for various data types.</p>
</div>
<!-- ======================================================================= -->
<a name="argpromotion">Promote 'by reference' arguments to scalars</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass promotes "by reference" arguments to be "by value" arguments. In
+ practice, this means looking for internal functions that have pointer
+ arguments. If it can prove, through the use of alias analysis, that an
+ argument is *only* loaded, then it can pass the value into the function
+ instead of the address of the value. This can cause recursive simplification
+ of code and lead to the elimination of allocas (especially in C++ template
+ code like the STL).
+ </p>
+
+ <p>
+ This pass also handles aggregate arguments that are passed into a function,
+ scalarizing them if the elements of the aggregate are only loaded. Note that
+ it refuses to scalarize aggregates which would require passing in more than
+ three operands to the function, because passing thousands of operands for a
+ large array or structure is unprofitable!
+ </p>
+
+ <p>
+ Note that this transformation could also be done for arguments that are only
+ stored to (returning the value instead), but does not currently. This case
+ would be best handled when and if LLVM starts supporting multiple return
+ values from functions.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="block-placement">Profile Guided Basic Block Placement</a>
</div>
<div class="doc_text">
- <p>This pass implements a very simple profile guided basic block placement
- algorithm. The idea is to put frequently executed blocks together at the
- start of the function, and hopefully increase the number of fall-through
- conditional branches. If there is no profile information for a particular
- function, this pass basically orders blocks in depth-first order.</p>
- <p>The algorithm implemented here is basically "Algo1" from "Profile Guided
- Code Positioning" by Pettis and Hansen, except that it uses basic block
- counts instead of edge counts. This could be improved in many ways, but is
- very simple for now.</p>
- <p>Basically we "place" the entry block, then loop over all successors in a
- DFO, placing the most frequently executed successor until we run out of
- blocks. Did we mention that this was <b>extremely</b> simplistic? This is
- also much slower than it could be. When it becomes important, this pass
- will be rewritten to use a better algorithm, and then we can worry about
- efficiency.</p>
+ <p>This pass is a very simple profile guided basic block placement algorithm.
+ The idea is to put frequently executed blocks together at the start of the
+ function and hopefully increase the number of fall-through conditional
+ branches. If there is no profile information for a particular function, this
+ pass basically orders blocks in depth-first order.</p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="break-crit-edges">Break critical edges in CFG</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Break all of the critical edges in the CFG by inserting a dummy basic block.
+ It may be "required" by passes that cannot deal with critical edges. This
+ transformation obviously invalidates the CFG, but can update forward dominator
+ (set, immediate dominators, tree, and frontier) information.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<p>Correlated Expression Elimination propagates information from conditional
branches to blocks dominated by destinations of the branch. It propagates
information from the condition check itself into the body of the branch,
- allowing transformations like these for example:
- <pre>
- if (i == 7)
- ... 4*i; // constant propagation
+ allowing transformations like these for example:</p>
+
+<blockquote><pre>
+if (i == 7)
+ ... 4*i; // constant propagation
- M = i+1; N = j+1;
- if (i == j)
- X = M-N; // = M-M == 0;
- </pre></p>
+M = i+1; N = j+1;
+if (i == j)
+ X = M-N; // = M-M == 0;
+</pre></blockquote>
<p>This is called Correlated Expression Elimination because we eliminate or
simplify expressions that are correlated with the direction of a branch. In
<a name="constmerge">Merge Duplicate Global Constants</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Merges duplicate global constants together into a single constant that is
+ shared. This is useful because some passes (ie TraceValues) insert a lot of
+ string constants into the program, regardless of whether or not an existing
+ string is available.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<div class="doc_text">
<p>This file implements constant propagation and merging. It looks for
instructions involving only constant operands and replaces them with a
- constant value instead of an instruction. For example:
- <pre>add i32 1, 2</pre><br/>
- becomes
- <pre>i32 3</pre></p>
+ constant value instead of an instruction. For example:</p>
+ <blockquote><pre>add i32 1, 2</pre></blockquote>
+ <p>becomes</p>
+ <blockquote><pre>i32 3</pre></blockquote>
<p>NOTE: this pass has a habit of making definitions be dead. It is a good
idea to to run a <a href="#die">DIE</a> (Dead Instruction Elimination) pass
sometime after running this pass.</p>
<a name="dce">Dead Code Elimination</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Dead code elimination is similar to <a href="#die">dead instruction
+ elimination</a>, but it rechecks instructions that were used by removed
+ instructions to see if they are newly dead.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="deadargelim">Dead Argument Elimination</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass deletes dead arguments from internal functions. Dead argument
+ elimination removes arguments which are directly dead, as well as arguments
+ only passed into function calls as dead arguments of other functions. This
+ pass also deletes dead arguments in a similar way.
+ </p>
+
+ <p>
+ This pass is often useful as a cleanup pass to run after aggressive
+ interprocedural passes, which add possibly-dead arguments.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="deadtypeelim">Dead Type Elimination</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass is used to cleanup the output of GCC. It eliminate names for types
+ that are unused in the entire translation unit, using the <a
+ href="#findusedtypes">find used types</a> pass.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="die">Dead Instruction Elimination</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Dead instruction elimination performs a single pass over the function,
+ removing instructions that are obviously dead.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="dse">Dead Store Elimination</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ A trivial dead store elimination that only considers basic-block local
+ redundant stores.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="gcse">Global Common Subexpression Elimination</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <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 implementation to identify the common
+ subexpressions, eliminating them when possible.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="globaldce">Dead Global Elimination</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This transform is designed to eliminate unreachable internal globals from the
+ program. It uses an aggressive algorithm, searching out globals that are
+ known to be alive. After it finds all of the globals which are needed, it
+ deletes whatever is left over. This allows it to delete recursive chunks of
+ the program which are unreachable.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="globalopt">Global Variable Optimizer</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass transforms simple global variables that never have their address
+ taken. If obviously true, it marks read/write globals as constant, deletes
+ variables only stored to, etc.
+ </p>
+</div>
+
+<!-------------------------------------------------------------------------- -->
+<div class="doc_subsection">
+ <a name="gvn">Global Value Numbering</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>
</div>
<!-------------------------------------------------------------------------- -->
<a name="gvnpre">Global Value Numbering/Partial Redundancy Elimination</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <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>
</div>
<!-------------------------------------------------------------------------- -->
<a name="indmemrem">Indirect Malloc and Free Removal</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass finds places where memory allocation functions may escape into
+ indirect land. Some transforms are much easier (aka possible) only if free
+ or malloc are not called indirectly.
+ </p>
+
+ <p>
+ Thus find places where the address of memory functions are taken and construct
+ bounce functions with direct calls of those functions.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="indvars">Canonicalize Induction Variables</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This transformation analyzes and transforms the induction variables (and
+ computations derived from them) into simpler forms suitable for subsequent
+ analysis and transformation.
+ </p>
+
+ <p>
+ This transformation makes the following changes to each loop with an
+ identifiable induction variable:
+ </p>
+
+ <ol>
+ <li>All loops are transformed to have a <em>single</em> canonical
+ induction variable which starts at zero and steps by one.</li>
+ <li>The canonical induction variable is guaranteed to be the first PHI node
+ in the loop header block.</li>
+ <li>Any pointer arithmetic recurrences are raised to use array
+ subscripts.</li>
+ </ol>
+
+ <p>
+ If the trip count of a loop is computable, this pass also makes the following
+ changes:
+ </p>
+
+ <ol>
+ <li>The exit condition for the loop is canonicalized to compare the
+ induction value against the exit value. This turns loops like:
+ <blockquote><pre>for (i = 7; i*i < 1000; ++i)</pre></blockquote>
+ into
+ <blockquote><pre>for (i = 0; i != 25; ++i)</pre></blockquote></li>
+ <li>Any use outside of the loop of an expression derived from the indvar
+ is changed to compute the derived value outside of the loop, eliminating
+ the dependence on the exit value of the induction variable. If the only
+ purpose of the loop is to compute the exit value of some derived
+ expression, this transformation will make the loop dead.</li>
+ </p>
+
+ <p>
+ This transformation should be followed by strength reduction after all of the
+ desired loop transformations have been performed. Additionally, on targets
+ where it is profitable, the loop could be transformed to count down to zero
+ (the "do loop" optimization).
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="inline">Function Integration/Inlining</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Bottom-up inlining of functions into callees.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="insert-block-profiling">Insert instrumentation for block profiling</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass instruments the specified program with counters for basic block
+ profiling, which counts the number of times each basic block executes. This
+ is the most basic form of profiling, which can tell which blocks are hot, but
+ cannot reliably detect hot paths through the CFG.
+ </p>
+
+ <p>
+ Note that this implementation is very naïve. Control equivalent regions of
+ the CFG should not require duplicate counters, but it does put duplicate
+ counters in.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="insert-edge-profiling">Insert instrumentation for edge profiling</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass instruments the specified program with counters for edge profiling.
+ Edge profiling can give a reasonable approximation of the hot paths through a
+ program, and is used for a wide variety of program transformations.
+ </p>
+
+ <p>
+ Note that this implementation is very naïve. It inserts a counter for
+ <em>every</em> edge in the program, instead of using control flow information
+ to prune the number of counters inserted.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="insert-function-profiling">Insert instrumentation for function profiling</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass instruments the specified program with counters for function
+ profiling, which counts the number of times each function is called.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="insert-null-profiling-rs">Measure profiling framework overhead</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ The basic profiler that does nothing. It is the default profiler and thus
+ terminates <code>RSProfiler</code> chains. It is useful for measuring
+ framework overhead.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="insert-rs-profiling-framework">Insert random sampling instrumentation framework</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ The second stage of the random-sampling instrumentation framework, duplicates
+ all instructions in a function, ignoring the profiling code, then connects the
+ two versions together at the entry and at backedges. At each connection point
+ a choice is made as to whether to jump to the profiled code (take a sample) or
+ execute the unprofiled code.
+ </p>
+
+ <p>
+ After this pass, it is highly recommended to run<a href="#mem2reg">mem2reg</a>
+ and <a href="#adce">adce</a>. <a href="#instcombine">instcombine</a>,
+ <a href="#load-vn">load-vn</a>, <a href="#gdce">gdce</a>, and
+ <a href="#dse">dse</a> also are good to run afterwards.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="instcombine">Combine redundant instructions</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Combine instructions to form fewer, simple
+ instructions. This pass does not modify the CFG This pass is where algebraic
+ simplification happens.
+ </p>
+
+ <p>
+ This pass combines things like:
+ </p>
+
+<blockquote><pre
+>%Y = add i32 %X, 1
+%Z = add i32 %Y, 1</pre></blockquote>
+
+ <p>
+ into:
+ </p>
+
+<blockquote><pre
+>%Z = add i32 %X, 2</pre></blockquote>
+
+ <p>
+ This is a simple worklist driven algorithm.
+ </p>
+
+ <p>
+ This pass guarantees that the following canonicalizations are performed on
+ the program:
+ </p>
+
+ <ul>
+ <li>If a binary operator has a constant operand, it is moved to the right-
+ hand side.</li>
+ <li>Bitwise operators with constant operands are always grouped so that
+ shifts are performed first, then <code>or</code>s, then
+ <code>and</code>s, then <code>xor</code>s.</li>
+ <li>Compare instructions are converted from <code><</code>,
+ <code>></code>, <code>≤</code>, or <code>≥</code> to
+ <code>=</code> or <code>≠</code> if possible.</li>
+ <li>All <code>cmp</code> instructions on boolean values are replaced with
+ logical operations.</li>
+ <li><code>add <var>X</var>, <var>X</var></code> is represented as
+ <code>mul <var>X</var>, 2</code> ⇒ <code>shl <var>X</var>, 1</code></li>
+ <li>Multiplies with a constant power-of-two argument are transformed into
+ shifts.</li>
+ <li>… etc.</li>
+ </ul>
</div>
<!-------------------------------------------------------------------------- -->
projects / oota-llvm.git / blobdiff