| <!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\">-$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' | |
| --> | |
| <h1>LLVM's Analysis and Transform Passes</h1> | |
| <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> | |
| <!-- ======================================================================= --> | |
| <h2><a name="intro">Introduction</a></h2> | |
| <div> | |
| <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> | |
| <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="#basicaa">-basicaa</a></td><td>Basic Alias Analysis (stateless AA impl)</td></tr> | |
| <tr><td><a href="#basiccg">-basiccg</a></td><td>Basic CallGraph Construction</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="#dot-dom">-dot-dom</a></td><td>Print dominance tree of function to 'dot' file</td></tr> | |
| <tr><td><a href="#dot-dom-only">-dot-dom-only</a></td><td>Print dominance tree of function to 'dot' file (with no function bodies)</td></tr> | |
| <tr><td><a href="#dot-postdom">-dot-postdom</a></td><td>Print postdominance tree of function to 'dot' file</td></tr> | |
| <tr><td><a href="#dot-postdom-only">-dot-postdom-only</a></td><td>Print postdominance tree 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="#iv-users">-iv-users</a></td><td>Induction Variable Users</td></tr> | |
| <tr><td><a href="#lazy-value-info">-lazy-value-info</a></td><td>Lazy Value Information Analysis</td></tr> | |
| <tr><td><a href="#lda">-lda</a></td><td>Loop Dependence Analysis</td></tr> | |
| <tr><td><a href="#libcall-aa">-libcall-aa</a></td><td>LibCall Alias Analysis</td></tr> | |
| <tr><td><a href="#lint">-lint</a></td><td>Statically lint-checks LLVM IR</td></tr> | |
| <tr><td><a href="#loops">-loops</a></td><td>Natural Loop Information</td></tr> | |
| <tr><td><a href="#memdep">-memdep</a></td><td>Memory Dependence Analysis</td></tr> | |
| <tr><td><a href="#module-debuginfo">-module-debuginfo</a></td><td>Decodes module-level debug info</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-dbginfo">-print-dbginfo</a></td><td>Print debug info in human readable form</td></tr> | |
| <tr><td><a href="#print-dom-info">-print-dom-info</a></td><td>Dominator Info Printer</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-estimator">-profile-estimator</a></td><td>Estimate profiling information</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="#profile-verifier">-profile-verifier</a></td><td>Verify profiling information</td></tr> | |
| <tr><td><a href="#regions">-regions</a></td><td>Detect single entry single exit regions</td></tr> | |
| <tr><td><a href="#scalar-evolution">-scalar-evolution</a></td><td>Scalar Evolution Analysis</td></tr> | |
| <tr><td><a href="#scev-aa">-scev-aa</a></td><td>ScalarEvolution-based Alias 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="#always-inline">-always-inline</a></td><td>Inliner for always_inline functions</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>Optimize for code generation</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="#functionattrs">-functionattrs</a></td><td>Deduce function attributes</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="#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-edge-profiling">-insert-edge-profiling</a></td><td>Insert instrumentation for edge profiling</td></tr> | |
| <tr><td><a href="#insert-optimal-edge-profiling">-insert-optimal-edge-profiling</a></td><td>Insert optimal instrumentation for edge profiling</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>Jump Threading</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>Delete dead loops</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-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-simplify">-loop-simplify</a></td><td>Canonicalize natural 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="#loweratomic">-loweratomic</a></td><td>Lower atomic intrinsics to non-atomic form</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="#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>MemCpy Optimization</td></tr> | |
| <tr><td><a href="#mergefunc">-mergefunc</a></td><td>Merge Functions</td></tr> | |
| <tr><td><a href="#mergereturn">-mergereturn</a></td><td>Unify function exit nodes</td></tr> | |
| <tr><td><a href="#partial-inliner">-partial-inliner</a></td><td>Partial Inliner</td></tr> | |
| <tr><td><a href="#prune-eh">-prune-eh</a></td><td>Remove unused exception handling info</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 (DT)</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="#sink">-sink</a></td><td>Code sinking</td></tr> | |
| <tr><td><a href="#sretpromotion">-sretpromotion</a></td><td>Promote sret arguments to multiple ret values</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-debug-info">-strip-dead-debug-info</a></td><td>Strip debug info for unused symbols</td></tr> | |
| <tr><td><a href="#strip-dead-prototypes">-strip-dead-prototypes</a></td><td>Strip Unused Function Prototypes</td></tr> | |
| <tr><td><a href="#strip-debug-declare">-strip-debug-declare</a></td><td>Strip all llvm.dbg.declare intrinsics</td></tr> | |
| <tr><td><a href="#strip-nondebug">-strip-nondebug</a></td><td>Strip all symbols, except dbg symbols, from a module</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="#instnamer">-instnamer</a></td><td>Assign names to anonymous instructions</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> | |
| <tr><td><a href="#view-dom">-view-dom</a></td><td>View dominance tree of function</td></tr> | |
| <tr><td><a href="#view-dom-only">-view-dom-only</a></td><td>View dominance tree of function (with no function bodies)</td></tr> | |
| <tr><td><a href="#view-postdom">-view-postdom</a></td><td>View postdominance tree of function</td></tr> | |
| <tr><td><a href="#view-postdom-only">-view-postdom-only</a></td><td>View postdominance tree of function (with no function bodies)</td></tr> | |
| </table> | |
| </div> | |
| <!-- ======================================================================= --> | |
| <h2><a name="analyses">Analysis Passes</a></h2> | |
| <div> | |
| <p>This section describes the LLVM Analysis Passes.</p> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="aa-eval">-aa-eval: Exhaustive Alias Analysis Precision Evaluator</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="basicaa">-basicaa: Basic Alias Analysis (stateless AA impl)</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="basiccg">-basiccg: Basic CallGraph Construction</a> | |
| </h3> | |
| <div> | |
| <p>Yet to be written.</p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="count-aa">-count-aa: Count Alias Analysis Query Responses</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="debug-aa">-debug-aa: AA use debugger</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="domfrontier">-domfrontier: Dominance Frontier Construction</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass is a simple dominator construction algorithm for finding forward | |
| dominator frontiers. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="domtree">-domtree: Dominator Tree Construction</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass is a simple dominator construction algorithm for finding forward | |
| dominators. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="dot-callgraph">-dot-callgraph: Print Call Graph to 'dot' file</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="dot-cfg">-dot-cfg: Print CFG of function to 'dot' file</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="dot-cfg-only">-dot-cfg-only: Print CFG of function to 'dot' file (with no function bodies)</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="dot-dom">-dot-dom: Print dominance tree of function to 'dot' file</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass, only available in <code>opt</code>, prints the dominator tree | |
| 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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="dot-dom-only">-dot-dom-only: Print dominance tree of function to 'dot' file (with no function bodies)</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass, only available in <code>opt</code>, prints the dominator tree | |
| 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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="dot-postdom">-dot-postdom: Print postdominance tree of function to 'dot' file</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass, only available in <code>opt</code>, prints the post dominator tree | |
| 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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="dot-postdom-only">-dot-postdom-only: Print postdominance tree of function to 'dot' file (with no function bodies)</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass, only available in <code>opt</code>, prints the post dominator tree | |
| 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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="globalsmodref-aa">-globalsmodref-aa: Simple mod/ref analysis for globals</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="instcount">-instcount: Counts the various types of Instructions</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass collects the count of all instructions and reports them | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="intervals">-intervals: Interval Partition Construction</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="iv-users">-iv-users: Induction Variable Users</a> | |
| </h3> | |
| <div> | |
| <p>Bookkeeping for "interesting" users of expressions computed from | |
| induction variables.</p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="lazy-value-info">-lazy-value-info: Lazy Value Information Analysis</a> | |
| </h3> | |
| <div> | |
| <p>Interface for lazy computation of value constraint information.</p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="lda">-lda: Loop Dependence Analysis</a> | |
| </h3> | |
| <div> | |
| <p>Loop dependence analysis framework, which is used to detect dependences in | |
| memory accesses in loops.</p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="libcall-aa">-libcall-aa: LibCall Alias Analysis</a> | |
| </h3> | |
| <div> | |
| <p>LibCall Alias Analysis.</p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="lint">-lint: Statically lint-checks LLVM IR</a> | |
| </h3> | |
| <div> | |
| <p>This pass statically checks for common and easily-identified constructs | |
| which produce undefined or likely unintended behavior in LLVM IR.</p> | |
| <p>It is not a guarantee of correctness, in two ways. First, it isn't | |
| comprehensive. There are checks which could be done statically which are | |
| not yet implemented. Some of these are indicated by TODO comments, but | |
| those aren't comprehensive either. Second, many conditions cannot be | |
| checked statically. This pass does no dynamic instrumentation, so it | |
| can't check for all possible problems.</p> | |
| <p>Another limitation is that it assumes all code will be executed. A store | |
| through a null pointer in a basic block which is never reached is harmless, | |
| but this pass will warn about it anyway.</p> | |
| <p>Optimization passes may make conditions that this pass checks for more or | |
| less obvious. If an optimization pass appears to be introducing a warning, | |
| it may be that the optimization pass is merely exposing an existing | |
| condition in the code.</p> | |
| <p>This code may be run before instcombine. In many cases, instcombine checks | |
| for the same kinds of things and turns instructions with undefined behavior | |
| into unreachable (or equivalent). Because of this, this pass makes some | |
| effort to look through bitcasts and so on. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="loops">-loops: Natural Loop Information</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="memdep">-memdep: Memory Dependence Analysis</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="module-debuginfo">-module-debuginfo: Decodes module-level debug info</a> | |
| </h3> | |
| <div> | |
| <p>This pass decodes the debug info metadata in a module and prints in a | |
| (sufficiently-prepared-) human-readable form. | |
| For example, run this pass from opt along with the -analyze option, and | |
| it'll print to standard output. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="no-aa">-no-aa: No Alias Analysis (always returns 'may' alias)</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="no-profile">-no-profile: No Profile Information</a> | |
| </h3> | |
| <div> | |
| <p> | |
| The default "no profile" implementation of the abstract | |
| <code>ProfileInfo</code> interface. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="postdomfrontier">-postdomfrontier: Post-Dominance Frontier Construction</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass is a simple post-dominator construction algorithm for finding | |
| post-dominator frontiers. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="postdomtree">-postdomtree: Post-Dominator Tree Construction</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass is a simple post-dominator construction algorithm for finding | |
| post-dominators. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="print-alias-sets">-print-alias-sets: Alias Set Printer</a> | |
| </h3> | |
| <div> | |
| <p>Yet to be written.</p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="print-callgraph">-print-callgraph: Print a call graph</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass, only available in <code>opt</code>, prints the call graph to | |
| standard error in a human-readable form. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="print-callgraph-sccs">-print-callgraph-sccs: Print SCCs of the Call Graph</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass, only available in <code>opt</code>, prints the SCCs of the call | |
| graph to standard error in a human-readable form. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="print-cfg-sccs">-print-cfg-sccs: Print SCCs of each function CFG</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass, only available in <code>opt</code>, prints the SCCs of each | |
| function CFG to standard error in a human-readable form. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="print-dbginfo">-print-dbginfo: Print debug info in human readable form</a> | |
| </h3> | |
| <div> | |
| <p>Pass that prints instructions, and associated debug info:</p> | |
| <ul> | |
| <li>source/line/col information</li> | |
| <li>original variable name</li> | |
| <li>original type name</li> | |
| </ul> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="print-dom-info">-print-dom-info: Dominator Info Printer</a> | |
| </h3> | |
| <div> | |
| <p>Dominator Info Printer.</p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="print-externalfnconstants">-print-externalfnconstants: Print external fn callsites passed constants</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="print-function">-print-function: Print function to stderr</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="print-module">-print-module: Print module to stderr</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass simply prints out the entire module when it is executed. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="print-used-types">-print-used-types: Find Used Types</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="profile-estimator">-profile-estimator: Estimate profiling information</a> | |
| </h3> | |
| <div> | |
| <p>Profiling information that estimates the profiling information | |
| in a very crude and unimaginative way. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="profile-loader">-profile-loader: Load profile information from llvmprof.out</a> | |
| </h3> | |
| <div> | |
| <p> | |
| A concrete implementation of profiling information that loads the information | |
| from a profile dump file. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="profile-verifier">-profile-verifier: Verify profiling information</a> | |
| </h3> | |
| <div> | |
| <p>Pass that checks profiling information for plausibility.</p> | |
| </div> | |
| <h3> | |
| <a name="regions">-regions: Detect single entry single exit regions</a> | |
| </h3> | |
| <div> | |
| <p> | |
| The <code>RegionInfo</code> pass detects single entry single exit regions in a | |
| function, where a region is defined as any subgraph that is connected to the | |
| remaining graph at only two spots. Furthermore, an hierarchical region tree is | |
| built. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="scalar-evolution">-scalar-evolution: Scalar Evolution Analysis</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="scev-aa">-scev-aa: ScalarEvolution-based Alias Analysis</a> | |
| </h3> | |
| <div> | |
| <p>Simple alias analysis implemented in terms of ScalarEvolution queries. | |
| This differs from traditional loop dependence analysis in that it tests | |
| for dependencies within a single iteration of a loop, rather than | |
| dependencies between different iterations. | |
| ScalarEvolution has a more complete understanding of pointer arithmetic | |
| than BasicAliasAnalysis' collection of ad-hoc analyses. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="targetdata">-targetdata: Target Data Layout</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-- ======================================================================= --> | |
| <h2><a name="transforms">Transform Passes</a></h2> | |
| <div> | |
| <p>This section describes the LLVM Transform Passes.</p> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="adce">-adce: Aggressive Dead Code Elimination</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="always-inline">-always-inline: Inliner for always_inline functions</a> | |
| </h3> | |
| <div> | |
| <p>A custom inliner that handles only functions that are marked as | |
| "always inline".</p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="argpromotion">-argpromotion: Promote 'by reference' arguments to scalars</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="block-placement">-block-placement: Profile Guided Basic Block Placement</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="break-crit-edges">-break-crit-edges: Break critical edges in CFG</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="codegenprepare">-codegenprepare: Optimize for code generation</a> | |
| </h3> | |
| <div> | |
| 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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="constmerge">-constmerge: Merge Duplicate Global Constants</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="constprop">-constprop: Simple constant propagation</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="dce">-dce: Dead Code Elimination</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="deadargelim">-deadargelim: Dead Argument Elimination</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="deadtypeelim">-deadtypeelim: Dead Type Elimination</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="die">-die: Dead Instruction Elimination</a> | |
| </h3> | |
| <div> | |
| <p> | |
| Dead instruction elimination performs a single pass over the function, | |
| removing instructions that are obviously dead. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="dse">-dse: Dead Store Elimination</a> | |
| </h3> | |
| <div> | |
| <p> | |
| A trivial dead store elimination that only considers basic-block local | |
| redundant stores. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="functionattrs">-functionattrs: Deduce function attributes</a> | |
| </h3> | |
| <div> | |
| <p>A simple interprocedural pass which walks the call-graph, looking for | |
| functions which do not access or only read non-local memory, and marking them | |
| readnone/readonly. In addition, it marks function arguments (of pointer type) | |
| 'nocapture' if a call to the function does not create any copies of the pointer | |
| value that outlive the call. This more or less means that the pointer is only | |
| dereferenced, and not returned from the function or stored in a global. | |
| This pass is implemented as a bottom-up traversal of the call-graph. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="globaldce">-globaldce: Dead Global Elimination</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="globalopt">-globalopt: Global Variable Optimizer</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="gvn">-gvn: Global Value Numbering</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass performs global value numbering to eliminate fully and partially | |
| redundant instructions. It also performs redundant load elimination. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="indvars">-indvars: Canonicalize Induction Variables</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="inline">-inline: Function Integration/Inlining</a> | |
| </h3> | |
| <div> | |
| <p> | |
| Bottom-up inlining of functions into callees. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="insert-edge-profiling">-insert-edge-profiling: Insert instrumentation for edge profiling</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="insert-optimal-edge-profiling">-insert-optimal-edge-profiling: Insert optimal instrumentation for edge profiling</a> | |
| </h3> | |
| <div> | |
| <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> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="instcombine">-instcombine: Combine redundant instructions</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="internalize">-internalize: Internalize Global Symbols</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="ipconstprop">-ipconstprop: Interprocedural constant propagation</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="ipsccp">-ipsccp: Interprocedural Sparse Conditional Constant Propagation</a> | |
| </h3> | |
| <div> | |
| <p> | |
| An interprocedural variant of <a href="#sccp">Sparse Conditional Constant | |
| Propagation</a>. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="jump-threading">-jump-threading: Jump Threading</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="lcssa">-lcssa: Loop-Closed SSA Form Pass</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="licm">-licm: Loop Invariant Code Motion</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="loop-deletion">-loop-deletion: Delete dead loops</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="loop-extract">-loop-extract: Extract loops into new functions</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="loop-extract-single">-loop-extract-single: Extract at most one loop into a new function</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="loop-reduce">-loop-reduce: Loop Strength Reduction</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="loop-rotate">-loop-rotate: Rotate Loops</a> | |
| </h3> | |
| <div> | |
| <p>A simple loop rotation transformation.</p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="loop-simplify">-loop-simplify: Canonicalize natural loops</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="loop-unroll">-loop-unroll: Unroll loops</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="loop-unswitch">-loop-unswitch: Unswitch loops</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="loweratomic">-loweratomic: Lower atomic intrinsics to non-atomic form</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass lowers atomic intrinsics to non-atomic form for use in a known | |
| non-preemptible environment. | |
| </p> | |
| <p> | |
| The pass does not verify that the environment is non-preemptible (in | |
| general this would require knowledge of the entire call graph of the | |
| program including any libraries which may not be available in bitcode form); | |
| it simply lowers every atomic intrinsic. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="lowerinvoke">-lowerinvoke: Lower invoke and unwind, for unwindless code generators</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="lowerswitch">-lowerswitch: Lower SwitchInst's to branches</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="mem2reg">-mem2reg: Promote Memory to Register</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="memcpyopt">-memcpyopt: MemCpy Optimization</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass performs various transformations related to eliminating memcpy | |
| calls, or transforming sets of stores into memset's. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="mergefunc">-mergefunc: Merge Functions</a> | |
| </h3> | |
| <div> | |
| <p>This pass looks for equivalent functions that are mergable and folds them. | |
| A hash is computed from the function, based on its type and number of | |
| basic blocks. | |
| Once all hashes are computed, we perform an expensive equality comparison | |
| on each function pair. This takes n^2/2 comparisons per bucket, so it's | |
| important that the hash function be high quality. The equality comparison | |
| iterates through each instruction in each basic block. | |
| When a match is found the functions are folded. If both functions are | |
| overridable, we move the functionality into a new internal function and | |
| leave two overridable thunks to it. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="mergereturn">-mergereturn: Unify function exit nodes</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="partial-inliner">-partial-inliner: Partial Inliner</a> | |
| </h3> | |
| <div> | |
| <p>This pass performs partial inlining, typically by inlining an if | |
| statement that surrounds the body of the function. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="prune-eh">-prune-eh: Remove unused exception handling info</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="reassociate">-reassociate: Reassociate expressions</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="reg2mem">-reg2mem: Demote all values to stack slots</a> | |
| </h3> | |
| <div> | |
| <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 across basic blocks are | |
| <tt>alloca</tt> instructions and <tt>load</tt> instructions before | |
| <tt>phi</tt> nodes. It is intended that this should make CFG hacking much | |
| easier. To make later hacking easier, the entry block is split into two, such | |
| that all introduced <tt>alloca</tt> instructions (and nothing else) are in the | |
| entry block. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="scalarrepl">-scalarrepl: Scalar Replacement of Aggregates (DT)</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="sccp">-sccp: Sparse Conditional Constant Propagation</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="simplify-libcalls">-simplify-libcalls: Simplify well-known library calls</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="simplifycfg">-simplifycfg: Simplify the CFG</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="sink">-sink: Code sinking</a> | |
| </h3> | |
| <div> | |
| <p>This pass moves instructions into successor blocks, when possible, so that | |
| they aren't executed on paths where their results aren't needed. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="sretpromotion">-sretpromotion: Promote sret arguments to multiple ret values</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="strip">-strip: Strip all symbols from a module</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="strip-dead-debug-info">-strip-dead-debug-info: Strip debug info for unused symbols</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="strip-dead-prototypes">-strip-dead-prototypes: Strip Unused Function Prototypes</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="strip-debug-declare">-strip-debug-declare: Strip all llvm.dbg.declare intrinsics</a> | |
| </h3> | |
| <div> | |
| <p>This pass implements code stripping. Specifically, it can delete:</p> | |
| <ul> | |
| <li>names for virtual registers</li> | |
| <li>symbols for internal globals and functions</li> | |
| <li>debug information</li> | |
| </ul> | |
| <p> | |
| Note that this transformation makes code much less readable, so it should | |
| only be used in situations where the 'strip' utility would be used, such as | |
| reducing code size or making it harder to reverse engineer code. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="strip-nondebug">-strip-nondebug: Strip all symbols, except dbg symbols, from a module</a> | |
| </h3> | |
| <div> | |
| <p>This pass implements code stripping. Specifically, it can delete:</p> | |
| <ul> | |
| <li>names for virtual registers</li> | |
| <li>symbols for internal globals and functions</li> | |
| <li>debug information</li> | |
| </ul> | |
| <p> | |
| Note that this transformation makes code much less readable, so it should | |
| only be used in situations where the 'strip' utility would be used, such as | |
| reducing code size or making it harder to reverse engineer code. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="tailcallelim">-tailcallelim: Tail Call Elimination</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="tailduplicate">-tailduplicate: Tail Duplication</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-- ======================================================================= --> | |
| <h2><a name="utilities">Utility Passes</a></h2> | |
| <div> | |
| <p>This section describes the LLVM Utility Passes.</p> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="deadarghaX0r">-deadarghaX0r: Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="extract-blocks">-extract-blocks: Extract Basic Blocks From Module (for bugpoint use)</a> | |
| </h3> | |
| <div> | |
| <p> | |
| This pass is used by bugpoint to extract all blocks from the module into their | |
| own functions.</p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="instnamer">-instnamer: Assign names to anonymous instructions</a> | |
| </h3> | |
| <div> | |
| <p>This is a little utility pass that gives instructions names, this is mostly | |
| useful when diffing the effect of an optimization because deleting an | |
| unnamed instruction can change all other instruction numbering, making the | |
| diff very noisy. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="preverify">-preverify: Preliminary module verification</a> | |
| </h3> | |
| <div> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="verify">-verify: Module Verifier</a> | |
| </h3> | |
| <div> | |
| <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 is illegal to put a label into any other type (like a structure) or | |
| to return one.</li> | |
| <li>Only phi nodes can be self referential: <tt>%x = add i32 %x, %x</tt> is | |
| invalid.</li> | |
| <li>PHI nodes must have an entry for each predecessor, with no extras.</li> | |
| <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> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="view-cfg">-view-cfg: View CFG of function</a> | |
| </h3> | |
| <div> | |
| <p> | |
| Displays the control flow graph using the GraphViz tool. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="view-cfg-only">-view-cfg-only: View CFG of function (with no function bodies)</a> | |
| </h3> | |
| <div> | |
| <p> | |
| Displays the control flow graph using the GraphViz tool, but omitting function | |
| bodies. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="view-dom">-view-dom: View dominance tree of function</a> | |
| </h3> | |
| <div> | |
| <p> | |
| Displays the dominator tree using the GraphViz tool. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="view-dom-only">-view-dom-only: View dominance tree of function (with no function bodies)</a> | |
| </h3> | |
| <div> | |
| <p> | |
| Displays the dominator tree using the GraphViz tool, but omitting function | |
| bodies. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="view-postdom">-view-postdom: View postdominance tree of function</a> | |
| </h3> | |
| <div> | |
| <p> | |
| Displays the post dominator tree using the GraphViz tool. | |
| </p> | |
| </div> | |
| <!-------------------------------------------------------------------------- --> | |
| <h3> | |
| <a name="view-postdom-only">-view-postdom-only: View postdominance tree of function (with no function bodies)</a> | |
| </h3> | |
| <div> | |
| <p> | |
| Displays the post dominator tree using the GraphViz tool, but omitting | |
| function bodies. | |
| </p> | |
| </div> | |
| </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: 2011-08-03 18:18:20 -0400 (Wed, 03 Aug 2011) $ | |
| </address> | |
| </body> | |
| </html> |