diff options
Diffstat (limited to 'docs/Passes.html')
| -rw-r--r-- | docs/Passes.html | 1970 |
1 files changed, 1970 insertions, 0 deletions
diff --git a/docs/Passes.html b/docs/Passes.html new file mode 100644 index 000000000000..5406be5e2df6 --- /dev/null +++ b/docs/Passes.html @@ -0,0 +1,1970 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" + "http://www.w3.org/TR/html4/strict.dtd"> +<html> +<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> + +<!-- + +If Passes.html is up to date, the following "one-liner" should print +an empty diff. + +egrep -e '^<tr><td><a href="#.*">-.*</a></td><td>.*</td></tr>$' \ + -e '^ <a name=".*">.*</a>$' < Passes.html >html; \ +perl >help <<'EOT' && diff -u help html; rm -f help html +open HTML, "<Passes.html" or die "open: Passes.html: $!\n"; +while (<HTML>) { + 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"; +while (<HELP>) { + m:^ -([^ ]+) +- (.*)$: or next; + my $o = $order{$1}; + $o = "000" unless defined $o; + push @x, "$o<tr><td><a href=\"#$1\">-$1</a></td><td>$2</td></tr>\n"; + push @y, "$o <a name=\"$1\">$2</a>\n"; +} +@x = map { s/^\d\d\d//; $_ } sort @x; +@y = map { s/^\d\d\d//; $_ } sort @y; +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> + <li><a href="#intro">Introduction</a></li> + <li><a href="#analyses">Analysis Passes</a> + <li><a href="#transforms">Transform Passes</a></li> + <li><a href="#utilities">Utility Passes</a></li> +</ol> + +<div class="doc_author"> + <p>Written by <a href="mailto:rspencer@x10sys.com">Reid Spencer</a> + and Gordon Henriksen</p> +</div> + +<!-- ======================================================================= --> +<div class="doc_section"> <a name="intro">Introduction</a> </div> +<div class="doc_text"> + <p>This document serves as a high level summary of the optimization features + that LLVM provides. Optimizations are implemented as Passes that traverse some + portion of a program to either collect information or transform the program. + The table below divides the passes that LLVM provides into three categories. + Analysis passes compute information that other passes can use or for debugging + or program visualization purposes. Transform passes can use (or invalidate) + the analysis passes. Transform passes all mutate the program in some way. + Utility passes provides some utility but don't otherwise fit categorization. + For example passes to extract functions to bitcode or write a module to + bitcode are neither analysis nor transform passes. + <p>The table below provides a quick summary of each pass and links to the more + complete pass description later in the document.</p> +</div> +<div class="doc_text" > +<table> +<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="#domfrontier">-domfrontier</a></td><td>Dominance Frontier Construction</td></tr> +<tr><td><a href="#domtree">-domtree</a></td><td>Dominator Tree Construction</td></tr> +<tr><td><a href="#dot-callgraph">-dot-callgraph</a></td><td>Print Call Graph to 'dot' file</td></tr> +<tr><td><a href="#dot-cfg">-dot-cfg</a></td><td>Print CFG of function to 'dot' file</td></tr> +<tr><td><a href="#dot-cfg-only">-dot-cfg-only</a></td><td>Print CFG of function to 'dot' file (with no function bodies)</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="#no-profile">-no-profile</a></td><td>No Profile Information</td></tr> +<tr><td><a href="#postdomfrontier">-postdomfrontier</a></td><td>Post-Dominance Frontier Construction</td></tr> +<tr><td><a href="#postdomtree">-postdomtree</a></td><td>Post-Dominator Tree Construction</td></tr> +<tr><td><a href="#print-alias-sets">-print-alias-sets</a></td><td>Alias Set Printer</td></tr> +<tr><td><a href="#print-callgraph">-print-callgraph</a></td><td>Print a call graph</td></tr> +<tr><td><a href="#print-callgraph-sccs">-print-callgraph-sccs</a></td><td>Print SCCs of the Call Graph</td></tr> +<tr><td><a href="#print-cfg-sccs">-print-cfg-sccs</a></td><td>Print SCCs of each function CFG</td></tr> +<tr><td><a href="#print-externalfnconstants">-print-externalfnconstants</a></td><td>Print external fn callsites passed constants</td></tr> +<tr><td><a href="#print-function">-print-function</a></td><td>Print function to stderr</td></tr> +<tr><td><a href="#print-module">-print-module</a></td><td>Print module to stderr</td></tr> +<tr><td><a href="#print-used-types">-print-used-types</a></td><td>Find Used Types</td></tr> +<tr><td><a href="#profile-loader">-profile-loader</a></td><td>Load profile information from llvmprof.out</td></tr> +<tr><td><a href="#scalar-evolution">-scalar-evolution</a></td><td>Scalar Evolution Analysis</td></tr> +<tr><td><a href="#targetdata">-targetdata</a></td><td>Target Data Layout</td></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="#break-crit-edges">-break-crit-edges</a></td><td>Break critical edges in CFG</td></tr> +<tr><td><a href="#codegenprepare">-codegenprepare</a></td><td>Prepare a function for code generation </td></tr> +<tr><td><a href="#condprop">-condprop</a></td><td>Conditional Propagation</td></tr> +<tr><td><a href="#constmerge">-constmerge</a></td><td>Merge Duplicate Global Constants</td></tr> +<tr><td><a href="#constprop">-constprop</a></td><td>Simple constant propagation</td></tr> +<tr><td><a href="#dce">-dce</a></td><td>Dead Code Elimination</td></tr> +<tr><td><a href="#deadargelim">-deadargelim</a></td><td>Dead Argument Elimination</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="#insert-block-profiling">-insert-block-profiling</a></td><td>Insert instrumentation for block profiling</td></tr> +<tr><td><a href="#insert-edge-profiling">-insert-edge-profiling</a></td><td>Insert instrumentation for edge profiling</td></tr> +<tr><td><a href="#insert-function-profiling">-insert-function-profiling</a></td><td>Insert instrumentation for function profiling</td></tr> +<tr><td><a href="#insert-null-profiling-rs">-insert-null-profiling-rs</a></td><td>Measure profiling framework overhead</td></tr> +<tr><td><a href="#insert-rs-profiling-framework">-insert-rs-profiling-framework</a></td><td>Insert random sampling instrumentation framework</td></tr> +<tr><td><a href="#instcombine">-instcombine</a></td><td>Combine redundant instructions</td></tr> +<tr><td><a href="#internalize">-internalize</a></td><td>Internalize Global Symbols</td></tr> +<tr><td><a href="#ipconstprop">-ipconstprop</a></td><td>Interprocedural constant propagation</td></tr> +<tr><td><a href="#ipsccp">-ipsccp</a></td><td>Interprocedural Sparse Conditional Constant Propagation</td></tr> +<tr><td><a href="#jump-threading">-jump-threading</a></td><td>Thread control through conditional blocks </td></tr> +<tr><td><a href="#lcssa">-lcssa</a></td><td>Loop-Closed SSA Form Pass</td></tr> +<tr><td><a href="#licm">-licm</a></td><td>Loop Invariant Code Motion</td></tr> +<tr><td><a href="#loop-deletion">-loop-deletion</a></td><td>Dead Loop Deletion Pass </td></tr> +<tr><td><a href="#loop-extract">-loop-extract</a></td><td>Extract loops into new functions</td></tr> +<tr><td><a href="#loop-extract-single">-loop-extract-single</a></td><td>Extract at most one loop into a new function</td></tr> +<tr><td><a href="#loop-index-split">-loop-index-split</a></td><td>Index Split Loops</td></tr> +<tr><td><a href="#loop-reduce">-loop-reduce</a></td><td>Loop Strength Reduction</td></tr> +<tr><td><a href="#loop-rotate">-loop-rotate</a></td><td>Rotate Loops</td></tr> +<tr><td><a href="#loop-unroll">-loop-unroll</a></td><td>Unroll loops</td></tr> +<tr><td><a href="#loop-unswitch">-loop-unswitch</a></td><td>Unswitch loops</td></tr> +<tr><td><a href="#loopsimplify">-loopsimplify</a></td><td>Canonicalize natural loops</td></tr> +<tr><td><a href="#lowerallocs">-lowerallocs</a></td><td>Lower allocations from instructions to calls</td></tr> +<tr><td><a href="#lowerinvoke">-lowerinvoke</a></td><td>Lower invoke and unwind, for unwindless code generators</td></tr> +<tr><td><a href="#lowersetjmp">-lowersetjmp</a></td><td>Lower Set Jump</td></tr> +<tr><td><a href="#lowerswitch">-lowerswitch</a></td><td>Lower SwitchInst's to branches</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> +<tr><td><a href="#sccp">-sccp</a></td><td>Sparse Conditional Constant Propagation</td></tr> +<tr><td><a href="#simplify-libcalls">-simplify-libcalls</a></td><td>Simplify well-known library calls</td></tr> +<tr><td><a href="#simplifycfg">-simplifycfg</a></td><td>Simplify the CFG</td></tr> +<tr><td><a href="#strip">-strip</a></td><td>Strip all symbols from a module</td></tr> +<tr><td><a href="#strip-dead-prototypes">-strip-dead-prototypes</a></td><td>Remove unused function declarations</td></tr> +<tr><td><a href="#sretpromotion">-sretpromotion</a></td><td>Promote sret arguments</td></tr> +<tr><td><a href="#tailcallelim">-tailcallelim</a></td><td>Tail Call Elimination</td></tr> +<tr><td><a href="#tailduplicate">-tailduplicate</a></td><td>Tail Duplication</td></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="#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> +</table> +</div> + +<!-- ======================================================================= --> +<div class="doc_section"> <a name="example">Analysis Passes</a></div> +<div class="doc_text"> + <p>This section describes the LLVM Analysis Passes.</p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="aa-eval">Exhaustive Alias Analysis Precision Evaluator</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<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> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="basiccg">Basic CallGraph Construction</a> +</div> +<div class="doc_text"> + <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> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="count-aa">Count Alias Analysis Query Responses</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="debug-aa">AA use debugger</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="domfrontier">Dominance Frontier Construction</a> +</div> +<div class="doc_text"> + <p> + This pass is a simple dominator construction algorithm for finding forward + dominator frontiers. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="domtree">Dominator Tree Construction</a> +</div> +<div class="doc_text"> + <p> + This pass is a simple dominator construction algorithm for finding forward + dominators. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="dot-callgraph">Print Call Graph to 'dot' file</a> +</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. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="dot-cfg">Print CFG of function to 'dot' file</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="dot-cfg-only">Print CFG of function to 'dot' file (with no function bodies)</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="globalsmodref-aa">Simple mod/ref analysis for globals</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="instcount">Counts the various types of Instructions</a> +</div> +<div class="doc_text"> + <p> + This pass collects the count of all instructions and reports them + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="intervals">Interval Partition Construction</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<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> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="memdep">Memory Dependence Analysis</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="no-aa">No Alias Analysis (always returns 'may' alias)</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="no-profile">No Profile Information</a> +</div> +<div class="doc_text"> + <p> + The default "no profile" implementation of the abstract + <code>ProfileInfo</code> interface. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="postdomfrontier">Post-Dominance Frontier Construction</a> +</div> +<div class="doc_text"> + <p> + This pass is a simple post-dominator construction algorithm for finding + post-dominator frontiers. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="postdomtree">Post-Dominator Tree Construction</a> +</div> +<div class="doc_text"> + <p> + This pass is a simple post-dominator construction algorithm for finding + post-dominators. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="print-alias-sets">Alias Set Printer</a> +</div> +<div class="doc_text"> + <p>Yet to be written.</p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="print-callgraph">Print a call graph</a> +</div> +<div class="doc_text"> + <p> + This pass, only available in <code>opt</code>, prints the call graph to + standard output in a human-readable form. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="print-callgraph-sccs">Print SCCs of the Call Graph</a> +</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. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="print-cfg-sccs">Print SCCs of each function CFG</a> +</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. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="print-externalfnconstants">Print external fn callsites passed constants</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="print-function">Print function to stderr</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="print-module">Print module to stderr</a> +</div> +<div class="doc_text"> + <p> + This pass simply prints out the entire module when it is executed. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="print-used-types">Find Used Types</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="profile-loader">Load profile information from llvmprof.out</a> +</div> +<div class="doc_text"> + <p> + A concrete implementation of profiling information that loads the information + from a profile dump file. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="scalar-evolution">Scalar Evolution Analysis</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="targetdata">Target Data Layout</a> +</div> +<div class="doc_text"> + <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> + +<!-- ======================================================================= --> +<div class="doc_section"> <a name="transform">Transform Passes</a></div> +<div class="doc_text"> + <p>This section describes the LLVM Transform Passes.</p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="adce">Aggressive Dead Code Elimination</a> +</div> +<div class="doc_text"> + <p>ADCE aggressively tries to eliminate code. This pass is similar to + <a href="#dce">DCE</a> but it assumes that values are dead until proven + otherwise. This is similar to <a href="#sccp">SCCP</a>, except applied to + the liveness of values.</p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="argpromotion">Promote 'by reference' arguments to scalars</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="block-placement">Profile Guided Basic Block Placement</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="break-crit-edges">Break critical edges in CFG</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="codegenprepare">Prepare a function for code generation</a> +</div> +<div class="doc_text"> + 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. +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="condprop">Conditional Propagation</a> +</div> +<div class="doc_text"> + <p>This pass propagates information about conditional expressions through the + program, allowing it to eliminate conditional branches in some cases.</p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="constmerge">Merge Duplicate Global Constants</a> +</div> +<div class="doc_text"> + <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_subsection"> + <a name="constprop">Simple constant propagation</a> +</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:</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> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="dce">Dead Code Elimination</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="deadargelim">Dead Argument Elimination</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="deadtypeelim">Dead Type Elimination</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="die">Dead Instruction Elimination</a> +</div> +<div class="doc_text"> + <p> + Dead instruction elimination performs a single pass over the function, + removing instructions that are obviously dead. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="dse">Dead Store Elimination</a> +</div> +<div class="doc_text"> + <p> + A trivial dead store elimination that only considers basic-block local + redundant stores. + </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 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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="globalopt">Global Variable Optimizer</a> +</div> +<div class="doc_text"> + <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> + <p> + Note that this pass does the value numbering itself, it does not use the + ValueNumbering analysis passes. + </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"> + <a name="indmemrem">Indirect Malloc and Free Removal</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="indvars">Canonicalize Induction Variables</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="inline">Function Integration/Inlining</a> +</div> +<div class="doc_text"> + <p> + Bottom-up inlining of functions into callees. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="insert-block-profiling">Insert instrumentation for block profiling</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="insert-edge-profiling">Insert instrumentation for edge profiling</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="insert-function-profiling">Insert instrumentation for function profiling</a> +</div> +<div class="doc_text"> + <p> + This pass instruments the specified program with counters for function + profiling, which counts the number of times each function is called. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="insert-null-profiling-rs">Measure profiling framework overhead</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="insert-rs-profiling-framework">Insert random sampling instrumentation framework</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="instcombine">Combine redundant instructions</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="internalize">Internalize Global Symbols</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="ipconstprop">Interprocedural constant propagation</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="ipsccp">Interprocedural Sparse Conditional Constant Propagation</a> +</div> +<div class="doc_text"> + <p> + An interprocedural variant of <a href="#sccp">Sparse Conditional Constant + Propagation</a>. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="jump-threading">Thread control through conditional blocks</a> +</div> +<div class="doc_text"> + <p> + Jump threading tries to find distinct threads of control flow running through + a basic block. This pass looks at blocks that have multiple predecessors and + multiple successors. If one or more of the predecessors of the block can be + proven to always cause a jump to one of the successors, we forward the edge + from the predecessor to the successor by duplicating the contents of this + block. + </p> + <p> + An example of when this can occur is code like this: + </p> + + <pre +>if () { ... + X = 4; +} +if (X < 3) {</pre> + + <p> + In this case, the unconditional branch at the end of the first if can be + revectored to the false side of the second if. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="lcssa">Loop-Closed SSA Form Pass</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="licm">Loop Invariant Code Motion</a> +</div> +<div class="doc_text"> + <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> +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="loop-deletion">Dead Loop Deletion Pass</a> +</div> +<div class="doc_text"> + <p> + This file implements the Dead Loop Deletion Pass. This pass is responsible + for eliminating loops with non-infinite computable trip counts that have no + side effects or volatile instructions, and do not contribute to the + computation of the function's return value. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="loop-extract">Extract loops into new functions</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="loop-extract-single">Extract at most one loop into a new function</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="loop-index-split">Index Split Loops</a> +</div> +<div class="doc_text"> + <p> + This pass divides loop's iteration range by spliting loop such that each + individual loop is executed efficiently. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="loop-reduce">Loop Strength Reduction</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="loop-rotate">Rotate Loops</a> +</div> +<div class="doc_text"> + <p>A simple loop rotation transformation.</p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="loop-unroll">Unroll loops</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="loop-unswitch">Unswitch loops</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="loopsimplify">Canonicalize natural loops</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="lowerallocs">Lower allocations from instructions to calls</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="lowerinvoke">Lower invoke and unwind, for unwindless code generators</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="lowersetjmp">Lower Set Jump</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="lowerswitch">Lower SwitchInst's to branches</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="mem2reg">Promote Memory to Register</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="memcpyopt">Optimize use of memcpy and friend</a> +</div> +<div class="doc_text"> + <p> + This pass performs various transformations related to eliminating memcpy + calls, or transforming sets of stores into memset's. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="mergereturn">Unify function exit nodes</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<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> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<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> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="reg2mem">Demote all values to stack slots</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="scalarrepl">Scalar Replacement of Aggregates</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="sccp">Sparse Conditional Constant Propagation</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="simplify-libcalls">Simplify well-known library calls</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="simplifycfg">Simplify the CFG</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="strip">Strip all symbols from a module</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="strip-dead-prototypes">Remove unused function declarations</a> +</div> +<div class="doc_text"> + <p> + This pass loops over all of the functions in the input module, looking for + dead declarations and removes them. Dead declarations are declarations of + functions for which no implementation is available (i.e., declarations for + unused library functions). + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="sretpromotion">Promote sret arguments</a> +</div> +<div class="doc_text"> + <p> + This pass finds functions that return a struct (using a pointer to the struct + as the first argument of the function, marked with the '<tt>sret</tt>' attribute) and + replaces them with a new function that simply returns each of the elements of + that struct (using multiple return values). + </p> + + <p> + This pass works under a number of conditions: + </p> + + <ul> + <li>The returned struct must not contain other structs</li> + <li>The returned struct must only be used to load values from</li> + <li>The placeholder struct passed in is the result of an <tt>alloca</tt></li> + </ul> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="tailcallelim">Tail Call Elimination</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="tailduplicate">Tail Duplication</a> +</div> +<div class="doc_text"> + <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> + +<!-- ======================================================================= --> +<div class="doc_section"> <a name="transform">Utility Passes</a></div> +<div class="doc_text"> + <p>This section describes the LLVM Utility Passes.</p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="deadarghaX0r">Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="extract-blocks">Extract Basic Blocks From Module (for bugpoint use)</a> +</div> +<div class="doc_text"> + <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="preverify">Preliminary module verification</a> +</div> +<div class="doc_text"> + <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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="verify">Module Verifier</a> +</div> +<div class="doc_text"> + <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 i32 %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> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="view-cfg">View CFG of function</a> +</div> +<div class="doc_text"> + <p> + Displays the control flow graph using the GraphViz tool. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> + <a name="view-cfg-only">View CFG of function (with no function bodies)</a> +</div> +<div class="doc_text"> + <p> + Displays the control flow graph using the GraphViz tool, but omitting function + bodies. + </p> +</div> + +<!-- *********************************************************************** --> + +<hr> +<address> + <a href="http://jigsaw.w3.org/css-validator/check/referer"><img + 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-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> + Last modified: $Date: 2008-12-11 18:34:48 +0100 (Thu, 11 Dec 2008) $ +</address> + +</body> +</html> |