<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>
+<tr><td><a href="#preverify">-preverify</a></td><td>Preliminary module verification</td></tr>
<tr><td><a href="#verify">-verify</a></td><td>Module Verifier</td></tr>
<tr><td><a href="#view-cfg">-view-cfg</a></td><td>View CFG of function</td></tr>
<tr><td><a href="#view-cfg-only">-view-cfg-only</a></td><td>View CFG of function (with no function bodies)</td></tr>
</div>
<div class="doc_text">
<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.
+ This pass, only available in <code>opt</code>, prints the call graph to
+ standard output in a human-readable form.
</p>
</div>
</div>
<div class="doc_text">
<p>
- This pass, only available in <code>opt</code>, prints
- the SCCs of the call graph to standard output in a human-readable form.
+ 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>
</div>
<div class="doc_text">
<p>
- This pass, only available in <code>opt</code>, prints
- the SCCs of each function CFG to standard output in a human-readable form.
+ 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="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>
<!-------------------------------------------------------------------------- -->
<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>
<!-------------------------------------------------------------------------- -->
<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>
<!-------------------------------------------------------------------------- -->
<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>
+ </ol>
+
+ <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>
<!-------------------------------------------------------------------------- -->
<a name="internalize">Internalize Global Symbols</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass loops over all of the functions in the input module, looking for a
+ main function. If a main function is found, all other functions and all
+ global variables with initializers are marked as internal.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="ipconstprop">Interprocedural constant propagation</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass implements an <em>extremely</em> simple interprocedural constant
+ propagation pass. It could certainly be improved in many different ways,
+ like using a worklist. This pass makes arguments dead, but does not remove
+ them. The existing dead argument elimination pass should be run after this
+ to clean up the mess.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="ipsccp">Interprocedural Sparse Conditional Constant Propagation</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ An interprocedural variant of <a href="#sccp">Sparse Conditional Constant
+ Propagation</a>.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="lcssa">Loop-Closed SSA Form Pass</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass transforms loops by placing phi nodes at the end of the loops for
+ all values that are live across the loop boundary. For example, it turns
+ the left into the right code:
+ </p>
+
+ <pre
+>for (...) for (...)
+ if (c) if (c)
+ X1 = ... X1 = ...
+ else else
+ X2 = ... X2 = ...
+ X3 = phi(X1, X2) X3 = phi(X1, X2)
+... = X3 + 4 X4 = phi(X3)
+ ... = X4 + 4</pre>
+
+ <p>
+ This is still valid LLVM; the extra phi nodes are purely redundant, and will
+ be trivially eliminated by <code>InstCombine</code>. The major benefit of
+ this transformation is that it makes many other loop optimizations, such as
+ LoopUnswitching, simpler.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="licm">Loop Invariant Code Motion</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass performs loop invariant code motion, attempting to remove as much
+ code from the body of a loop as possible. It does this by either hoisting
+ code into the preheader block, or by sinking code to the exit blocks if it is
+ safe. This pass also promotes must-aliased memory locations in the loop to
+ live in registers, thus hoisting and sinking "invariant" loads and stores.
+ </p>
+
+ <p>
+ This pass uses alias analysis for two purposes:
+ </p>
+
+ <ul>
+ <li>Moving loop invariant loads and calls out of loops. If we can determine
+ that a load or call inside of a loop never aliases anything stored to,
+ we can hoist it or sink it like any other instruction.</li>
+ <li>Scalar Promotion of Memory - If there is a store instruction inside of
+ the loop, we try to move the store to happen AFTER the loop instead of
+ inside of the loop. This can only happen if a few conditions are true:
+ <ul>
+ <li>The pointer stored through is loop invariant.</li>
+ <li>There are no stores or loads in the loop which <em>may</em> alias
+ the pointer. There are no calls in the loop which mod/ref the
+ pointer.</li>
+ </ul>
+ If these conditions are true, we can promote the loads and stores in the
+ loop of the pointer to use a temporary alloca'd variable. We then use
+ the mem2reg functionality to construct the appropriate SSA form for the
+ variable.</li>
+ </ul>
</div>
<!-------------------------------------------------------------------------- -->
<a name="loop-extract">Extract loops into new functions</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ A pass wrapper around the <code>ExtractLoop()</code> scalar transformation to
+ extract each top-level loop into its own new function. If the loop is the
+ <em>only</em> loop in a given function, it is not touched. This is a pass most
+ useful for debugging via bugpoint.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="loop-extract-single">Extract at most one loop into a new function</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Similar to <a href="#loop-extract">Extract loops into new functions</a>,
+ this pass extracts one natural loop from the program into a function if it
+ can. This is used by bugpoint.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="loop-index-split">Index Split Loops</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass divides loop's iteration range by spliting loop such that each
+ individual loop is executed efficiently.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="loop-reduce">Loop Strength Reduction</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass performs a strength reduction on array references inside loops that
+ have as one or more of their components the loop induction variable. This is
+ accomplished by creating a new value to hold the initial value of the array
+ access for the first iteration, and then creating a new GEP instruction in
+ the loop to increment the value by the appropriate amount.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="loop-rotate">Rotate Loops</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>A simple loop rotation transformation.</p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="loop-unroll">Unroll loops</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass implements a simple loop unroller. It works best when loops have
+ been canonicalized by the <a href="#indvars"><tt>-indvars</tt></a> pass,
+ allowing it to determine the trip counts of loops easily.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="loop-unswitch">Unswitch loops</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass transforms loops that contain branches on loop-invariant conditions
+ to have multiple loops. For example, it turns the left into the right code:
+ </p>
+
+ <pre
+>for (...) if (lic)
+ A for (...)
+ if (lic) A; B; C
+ B else
+ C for (...)
+ A; C</pre>
+
+ <p>
+ This can increase the size of the code exponentially (doubling it every time
+ a loop is unswitched) so we only unswitch if the resultant code will be
+ smaller than a threshold.
+ </p>
+
+ <p>
+ This pass expects LICM to be run before it to hoist invariant conditions out
+ of the loop, to make the unswitching opportunity obvious.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="loopsimplify">Canonicalize natural loops</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass performs several transformations to transform natural loops into a
+ simpler form, which makes subsequent analyses and transformations simpler and
+ more effective.
+ </p>
+
+ <p>
+ Loop pre-header insertion guarantees that there is a single, non-critical
+ entry edge from outside of the loop to the loop header. This simplifies a
+ number of analyses and transformations, such as LICM.
+ </p>
+
+ <p>
+ Loop exit-block insertion guarantees that all exit blocks from the loop
+ (blocks which are outside of the loop that have predecessors inside of the
+ loop) only have predecessors from inside of the loop (and are thus dominated
+ by the loop header). This simplifies transformations such as store-sinking
+ that are built into LICM.
+ </p>
+
+ <p>
+ This pass also guarantees that loops will have exactly one backedge.
+ </p>
+
+ <p>
+ Note that the simplifycfg pass will clean up blocks which are split out but
+ end up being unnecessary, so usage of this pass should not pessimize
+ generated code.
+ </p>
+
+ <p>
+ This pass obviously modifies the CFG, but updates loop information and
+ dominator information.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="lower-packed">lowers packed operations to operations on smaller packed datatypes</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Lowers operations on vector datatypes into operations on more primitive vector
+ datatypes, and finally to scalar operations.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="lowerallocs">Lower allocations from instructions to calls</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Turn <tt>malloc</tt> and <tt>free</tt> instructions into <tt>@malloc</tt> and
+ <tt>@free</tt> calls.
+ </p>
+
+ <p>
+ This is a target-dependent tranformation because it depends on the size of
+ data types and alignment constraints.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="lowergc">Lower GC intrinsics, for GCless code generators</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This file implements lowering for the <tt>llvm.gc*</tt> intrinsics for targets
+ that do not natively support them (which includes the C backend). Note that
+ the code generated is not as efficient as it would be for targets that
+ natively support the GC intrinsics, but it is useful for getting new targets
+ up-and-running quickly.
+ </p>
+
+ <p>
+ This pass implements the code transformation described in this paper:
+ </p>
+
+ <blockquote><p>
+ "Accurate Garbage Collection in an Uncooperative Environment"
+ Fergus Henderson, ISMM, 2002
+ </p></blockquote>
</div>
<!-------------------------------------------------------------------------- -->
<a name="lowerinvoke">Lower invoke and unwind, for unwindless code generators</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This transformation is designed for use by code generators which do not yet
+ support stack unwinding. This pass supports two models of exception handling
+ lowering, the 'cheap' support and the 'expensive' support.
+ </p>
+
+ <p>
+ 'Cheap' exception handling support gives the program the ability to execute
+ any program which does not "throw an exception", by turning 'invoke'
+ instructions into calls and by turning 'unwind' instructions into calls to
+ abort(). If the program does dynamically use the unwind instruction, the
+ program will print a message then abort.
+ </p>
+
+ <p>
+ 'Expensive' exception handling support gives the full exception handling
+ support to the program at the cost of making the 'invoke' instruction
+ really expensive. It basically inserts setjmp/longjmp calls to emulate the
+ exception handling as necessary.
+ </p>
+
+ <p>
+ Because the 'expensive' support slows down programs a lot, and EH is only
+ used for a subset of the programs, it must be specifically enabled by the
+ <tt>-enable-correct-eh-support</tt> option.
+ </p>
+
+ <p>
+ Note that after this pass runs the CFG is not entirely accurate (exceptional
+ control flow edges are not correct anymore) so only very simple things should
+ be done after the lowerinvoke pass has run (like generation of native code).
+ This should not be used as a general purpose "my LLVM-to-LLVM pass doesn't
+ support the invoke instruction yet" lowering pass.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="lowerselect">Lower select instructions to branches</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Lowers select instructions into conditional branches for targets that do not
+ have conditional moves or that have not implemented the select instruction
+ yet.
+ </p>
+
+ <p>
+ Note that this pass could be improved. In particular it turns every select
+ instruction into a new conditional branch, even though some common cases have
+ select instructions on the same predicate next to each other. It would be
+ better to use the same branch for the whole group of selects.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="lowersetjmp">Lower Set Jump</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Lowers <tt>setjmp</tt> and <tt>longjmp</tt> to use the LLVM invoke and unwind
+ instructions as necessary.
+ </p>
+
+ <p>
+ Lowering of <tt>longjmp</tt> is fairly trivial. We replace the call with a
+ call to the LLVM library function <tt>__llvm_sjljeh_throw_longjmp()</tt>.
+ This unwinds the stack for us calling all of the destructors for
+ objects allocated on the stack.
+ </p>
+
+ <p>
+ At a <tt>setjmp</tt> call, the basic block is split and the <tt>setjmp</tt>
+ removed. The calls in a function that have a <tt>setjmp</tt> are converted to
+ invoke where the except part checks to see if it's a <tt>longjmp</tt>
+ exception and, if so, if it's handled in the function. If it is, then it gets
+ the value returned by the <tt>longjmp</tt> and goes to where the basic block
+ was split. <tt>invoke</tt> instructions are handled in a similar fashion with
+ the original except block being executed if it isn't a <tt>longjmp</tt>
+ except that is handled by that function.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="lowerswitch">Lower SwitchInst's to branches</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Rewrites <tt>switch</tt> instructions with a sequence of branches, which
+ allows targets to get away with not implementing the switch instruction until
+ it is convenient.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="mem2reg">Promote Memory to Register</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This file promotes memory references to be register references. It promotes
+ <tt>alloca</tt> instructions which only have <tt>load</tt>s and
+ <tt>store</tt>s as uses. An <tt>alloca</tt> is transformed by using dominator
+ frontiers to place <tt>phi</tt> nodes, then traversing the function in
+ depth-first order to rewrite <tt>load</tt>s and <tt>store</tt>s as
+ appropriate. This is just the standard SSA construction algorithm to construct
+ "pruned" SSA form.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="mergereturn">Unify function exit nodes</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Ensure that functions have at most one <tt>ret</tt> instruction in them.
+ Additionally, it keeps track of which node is the new exit node of the CFG.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="predsimplify">Predicate Simplifier</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <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>
<!-------------------------------------------------------------------------- -->
<a name="prune-eh">Remove unused exception handling info</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This file implements a simple interprocedural pass which walks the call-graph,
+ turning <tt>invoke</tt> instructions into <tt>call</tt> instructions if and
+ only if the callee cannot throw an exception. It implements this as a
+ bottom-up traversal of the call-graph.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="raiseallocs">Raise allocations from calls to instructions</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Converts <tt>@malloc</tt> and <tt>@free</tt> calls to <tt>malloc</tt> and
+ <tt>free</tt> instructions.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="reassociate">Reassociate expressions</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass reassociates commutative expressions in an order that is designed
+ to promote better constant propagation, GCSE, LICM, PRE, etc.
+ </p>
+
+ <p>
+ For example: 4 + (<var>x</var> + 5) ⇒ <var>x</var> + (4 + 5)
+ </p>
+
+ <p>
+ In the implementation of this algorithm, constants are assigned rank = 0,
+ function arguments are rank = 1, and other values are assigned ranks
+ corresponding to the reverse post order traversal of current function
+ (starting at 2), which effectively gives values in deep loops higher rank
+ than values not in loops.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="reg2mem">Demote all values to stack slots</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <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>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
+ that all introduced <tt>alloca</tt> instructions (and nothing else) are in the
+ entry block.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="scalarrepl">Scalar Replacement of Aggregates</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ The well-known scalar replacement of aggregates transformation. This
+ transform breaks up <tt>alloca</tt> instructions of aggregate type (structure
+ or array) into individual <tt>alloca</tt> instructions for each member if
+ possible. Then, if possible, it transforms the individual <tt>alloca</tt>
+ instructions into nice clean scalar SSA form.
+ </p>
+
+ <p>
+ This combines a simple scalar replacement of aggregates algorithm with the <a
+ href="#mem2reg"><tt>mem2reg</tt></a> algorithm because often interact,
+ especially for C++ programs. As such, iterating between <tt>scalarrepl</tt>,
+ then <a href="#mem2reg"><tt>mem2reg</tt></a> until we run out of things to
+ promote works well.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="sccp">Sparse Conditional Constant Propagation</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Sparse conditional constant propagation and merging, which can be summarized
+ as:
+ </p>
+
+ <ol>
+ <li>Assumes values are constant unless proven otherwise</li>
+ <li>Assumes BasicBlocks are dead unless proven otherwise</li>
+ <li>Proves values to be constant, and replaces them with constants</li>
+ <li>Proves conditional branches to be unconditional</li>
+ </ol>
+
+ <p>
+ Note that this pass has a habit of making definitions be dead. It is a good
+ idea to to run a DCE pass sometime after running this pass.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="simplify-libcalls">Simplify well-known library calls</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Applies a variety of small optimizations for calls to specific well-known
+ function calls (e.g. runtime library functions). For example, a call
+ <tt>exit(3)</tt> that occurs within the <tt>main()</tt> function can be
+ transformed into simply <tt>return 3</tt>.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="simplifycfg">Simplify the CFG</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Performs dead code elimination and basic block merging. Specifically:
+ </p>
+
+ <ol>
+ <li>Removes basic blocks with no predecessors.</li>
+ <li>Merges a basic block into its predecessor if there is only one and the
+ predecessor only has one successor.</li>
+ <li>Eliminates PHI nodes for basic blocks with a single predecessor.</li>
+ <li>Eliminates a basic block that only contains an unconditional
+ branch.</li>
+ </ol>
</div>
<!-------------------------------------------------------------------------- -->
<a name="strip">Strip all symbols from a module</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Performs code stripping. This transformation can delete:
+ </p>
+
+ <ol>
+ <li>names for virtual registers</li>
+ <li>symbols for internal globals and functions</li>
+ <li>debug information</li>
+ </ol>
+
+ <p>
+ Note that this transformation makes code much less readable, so it should
+ only be used in situations where the <tt>strip</tt> utility would be used,
+ such as reducing code size or making it harder to reverse engineer code.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="tailcallelim">Tail Call Elimination</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This file transforms calls of the current function (self recursion) followed
+ by a return instruction with a branch to the entry of the function, creating
+ a loop. This pass also implements the following extensions to the basic
+ algorithm:
+ </p>
+
+ <ul>
+ <li>Trivial instructions between the call and return do not prevent the
+ transformation from taking place, though currently the analysis cannot
+ support moving any really useful instructions (only dead ones).
+ <li>This pass transforms functions that are prevented from being tail
+ recursive by an associative expression to use an accumulator variable,
+ thus compiling the typical naive factorial or <tt>fib</tt> implementation
+ into efficient code.
+ <li>TRE is performed if the function returns void, if the return
+ returns the result returned by the call, or if the function returns a
+ run-time constant on all exits from the function. It is possible, though
+ unlikely, that the return returns something else (like constant 0), and
+ can still be TRE'd. It can be TRE'd if <em>all other</em> return
+ instructions in the function return the exact same value.
+ <li>If it can prove that callees do not access theier caller stack frame,
+ they are marked as eligible for tail call elimination (by the code
+ generator).
+ </ul>
</div>
<!-------------------------------------------------------------------------- -->
<a name="tailduplicate">Tail Duplication</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass performs a limited form of tail duplication, intended to simplify
+ CFGs by removing some unconditional branches. This pass is necessary to
+ straighten out loops created by the C front-end, but also is capable of
+ making other code nicer. After this pass is run, the CFG simplify pass
+ should be run to clean up the mess.
+ </p>
</div>
<!-- ======================================================================= -->
<a name="deadarghaX0r">Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Same as dead argument elimination, but deletes arguments to functions which
+ are external. This is only for use by <a
+ href="Bugpoint.html">bugpoint</a>.</p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="extract-blocks">Extract Basic Blocks From Module (for bugpoint use)</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ This pass is used by bugpoint to extract all blocks from the module into their
+ own functions.</p>
</div>
<!-------------------------------------------------------------------------- -->
<div class="doc_subsection">
- <a name="emitbitcode">Bitcode Writer</a>
+ <a name="preverify">Preliminary module verification</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Ensures that the module is in the form required by the <a
+ href="#verifier">Module Verifier</a> pass.
+ </p>
+
+ <p>
+ Running the verifier runs this pass automatically, so there should be no need
+ to use it directly.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="verify">Module Verifier</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Verifies an LLVM IR code. This is useful to run after an optimization which is
+ undergoing testing. Note that <tt>llvm-as</tt> verifies its input before
+ emitting bitcode, and also that malformed bitcode is likely to make LLVM
+ crash. All language front-ends are therefore encouraged to verify their output
+ before performing optimizing transformations.
+ </p>
+
+ <ul>
+ <li>Both of a binary operator's parameters are of the same type.</li>
+ <li>Verify that the indices of mem access instructions match other
+ operands.</li>
+ <li>Verify that arithmetic and other things are only performed on
+ first-class types. Verify that shifts and logicals only happen on
+ 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>Only phi nodes can be self referential: <tt>%x = add int %x, %x</tt> is
+ invalid.</li>
+ <li>PHI nodes must have an entry for each predecessor, with no extras.</li>
+ <li>PHI nodes must be the first thing in a basic block, all grouped
+ together.</li>
+ <li>PHI nodes must have at least one entry.</li>
+ <li>All basic blocks should only end with terminator insts, not contain
+ them.</li>
+ <li>The entry node to a function must not have predecessors.</li>
+ <li>All Instructions must be embedded into a basic block.</li>
+ <li>Functions cannot take a void-typed parameter.</li>
+ <li>Verify that a function's argument list agrees with its declared
+ type.</li>
+ <li>It is illegal to specify a name for a void value.</li>
+ <li>It is illegal to have a internal global value with no initializer.</li>
+ <li>It is illegal to have a ret instruction that returns a value that does
+ not agree with the function return value type.</li>
+ <li>Function call argument types match the function prototype.</li>
+ <li>All other things that are tested by asserts spread about the code.</li>
+ </ul>
+
+ <p>
+ Note that this does not provide full security verification (like Java), but
+ instead just tries to ensure that code is well-formed.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="view-cfg">View CFG of function</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Displays the control flow graph using the GraphViz tool.
+ </p>
</div>
<!-------------------------------------------------------------------------- -->
<a name="view-cfg-only">View CFG of function (with no function bodies)</a>
</div>
<div class="doc_text">
- <p>Yet to be written.</p>
+ <p>
+ Displays the control flow graph using the GraphViz tool, but omitting function
+ bodies.
+ </p>
</div>
<!-- *********************************************************************** -->