Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" |
| 2 | "http://www.w3.org/TR/html4/strict.dtd"> |
| 3 | <html> |
| 4 | <head> |
| 5 | <title>LLVM's Analysis and Transform Passes</title> |
| 6 | <link rel="stylesheet" href="llvm.css" type="text/css"> |
Gordon Henriksen | ddaa61d | 2007-10-25 08:58:56 +0000 | [diff] [blame] | 7 | <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 8 | </head> |
| 9 | <body> |
| 10 | |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 11 | <!-- |
| 12 | |
| 13 | If Passes.html is up to date, the following "one-liner" should print |
| 14 | an empty diff. |
| 15 | |
| 16 | egrep -e '^<tr><td><a href="#.*">-.*</a></td><td>.*</td></tr>$' \ |
| 17 | -e '^ <a name=".*">.*</a>$' < Passes.html >html; \ |
| 18 | perl >help <<'EOT' && diff -u help html; rm -f help html |
| 19 | open HTML, "<Passes.html" or die "open: Passes.html: $!\n"; |
| 20 | while (<HTML>) { |
| 21 | m:^<tr><td><a href="#(.*)">-.*</a></td><td>.*</td></tr>$: or next; |
| 22 | $order{$1} = sprintf("%03d", 1 + int %order); |
| 23 | } |
Gordon Henriksen | ddaa61d | 2007-10-25 08:58:56 +0000 | [diff] [blame] | 24 | open HELP, "../Release/bin/opt -help|" or die "open: opt -help: $!\n"; |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 25 | while (<HELP>) { |
| 26 | m:^ -([^ ]+) +- (.*)$: or next; |
| 27 | my $o = $order{$1}; |
| 28 | $o = "000" unless defined $o; |
| 29 | push @x, "$o<tr><td><a href=\"#$1\">-$1</a></td><td>$2</td></tr>\n"; |
| 30 | push @y, "$o <a name=\"$1\">$2</a>\n"; |
| 31 | } |
| 32 | @x = map { s/^\d\d\d//; $_ } sort @x; |
| 33 | @y = map { s/^\d\d\d//; $_ } sort @y; |
| 34 | print @x, @y; |
| 35 | EOT |
| 36 | |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 37 | This (real) one-liner can also be helpful when converting comments to HTML: |
| 38 | |
| 39 | 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' |
| 40 | |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 41 | --> |
| 42 | |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 43 | <div class="doc_title">LLVM's Analysis and Transform Passes</div> |
| 44 | |
| 45 | <ol> |
| 46 | <li><a href="#intro">Introduction</a></li> |
| 47 | <li><a href="#analyses">Analysis Passes</a> |
| 48 | <li><a href="#transforms">Transform Passes</a></li> |
| 49 | <li><a href="#utilities">Utility Passes</a></li> |
| 50 | </ol> |
| 51 | |
| 52 | <div class="doc_author"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 53 | <p>Written by <a href="mailto:rspencer@x10sys.com">Reid Spencer</a> |
| 54 | and Gordon Henriksen</p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 55 | </div> |
| 56 | |
| 57 | <!-- ======================================================================= --> |
| 58 | <div class="doc_section"> <a name="intro">Introduction</a> </div> |
| 59 | <div class="doc_text"> |
| 60 | <p>This document serves as a high level summary of the optimization features |
| 61 | that LLVM provides. Optimizations are implemented as Passes that traverse some |
| 62 | portion of a program to either collect information or transform the program. |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 63 | The table below divides the passes that LLVM provides into three categories. |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 64 | Analysis passes compute information that other passes can use or for debugging |
| 65 | or program visualization purposes. Transform passes can use (or invalidate) |
| 66 | the analysis passes. Transform passes all mutate the program in some way. |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 67 | Utility passes provides some utility but don't otherwise fit categorization. |
Gabor Greif | 04367bf | 2007-07-06 22:07:22 +0000 | [diff] [blame] | 68 | For example passes to extract functions to bitcode or write a module to |
| 69 | bitcode are neither analysis nor transform passes. |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 70 | <p>The table below provides a quick summary of each pass and links to the more |
| 71 | complete pass description later in the document.</p> |
| 72 | </div> |
| 73 | <div class="doc_text" > |
| 74 | <table> |
Gordon Henriksen | ddaa61d | 2007-10-25 08:58:56 +0000 | [diff] [blame] | 75 | <tr><th colspan="2"><b>ANALYSIS PASSES</b></th></tr> |
| 76 | <tr><th>Option</th><th>Name</th></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 77 | <tr><td><a href="#aa-eval">-aa-eval</a></td><td>Exhaustive Alias Analysis Precision Evaluator</td></tr> |
| 78 | <tr><td><a href="#anders-aa">-anders-aa</a></td><td>Andersen's Interprocedural Alias Analysis</td></tr> |
| 79 | <tr><td><a href="#basicaa">-basicaa</a></td><td>Basic Alias Analysis (default AA impl)</td></tr> |
| 80 | <tr><td><a href="#basiccg">-basiccg</a></td><td>Basic CallGraph Construction</td></tr> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 81 | <tr><td><a href="#codegenprepare">-codegenprepare</a></td><td>Optimize for code generation</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 82 | <tr><td><a href="#count-aa">-count-aa</a></td><td>Count Alias Analysis Query Responses</td></tr> |
| 83 | <tr><td><a href="#debug-aa">-debug-aa</a></td><td>AA use debugger</td></tr> |
| 84 | <tr><td><a href="#domfrontier">-domfrontier</a></td><td>Dominance Frontier Construction</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 85 | <tr><td><a href="#domtree">-domtree</a></td><td>Dominator Tree Construction</td></tr> |
Duncan Sands | 3ee8fc9 | 2008-09-23 12:47:39 +0000 | [diff] [blame] | 86 | <tr><td><a href="#dot-callgraph">-dot-callgraph</a></td><td>Print Call Graph to 'dot' file</td></tr> |
| 87 | <tr><td><a href="#dot-cfg">-dot-cfg</a></td><td>Print CFG of function to 'dot' file</td></tr> |
| 88 | <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> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 89 | <tr><td><a href="#globalsmodref-aa">-globalsmodref-aa</a></td><td>Simple mod/ref analysis for globals</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 90 | <tr><td><a href="#instcount">-instcount</a></td><td>Counts the various types of Instructions</td></tr> |
| 91 | <tr><td><a href="#intervals">-intervals</a></td><td>Interval Partition Construction</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 92 | <tr><td><a href="#loops">-loops</a></td><td>Natural Loop Construction</td></tr> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 93 | <tr><td><a href="#memdep">-memdep</a></td><td>Memory Dependence Analysis</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 94 | <tr><td><a href="#no-aa">-no-aa</a></td><td>No Alias Analysis (always returns 'may' alias)</td></tr> |
| 95 | <tr><td><a href="#no-profile">-no-profile</a></td><td>No Profile Information</td></tr> |
| 96 | <tr><td><a href="#postdomfrontier">-postdomfrontier</a></td><td>Post-Dominance Frontier Construction</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 97 | <tr><td><a href="#postdomtree">-postdomtree</a></td><td>Post-Dominator Tree Construction</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 98 | <tr><td><a href="#print-alias-sets">-print-alias-sets</a></td><td>Alias Set Printer</td></tr> |
Duncan Sands | 3ee8fc9 | 2008-09-23 12:47:39 +0000 | [diff] [blame] | 99 | <tr><td><a href="#print-callgraph">-print-callgraph</a></td><td>Print a call graph</td></tr> |
| 100 | <tr><td><a href="#print-callgraph-sccs">-print-callgraph-sccs</a></td><td>Print SCCs of the Call Graph</td></tr> |
| 101 | <tr><td><a href="#print-cfg-sccs">-print-cfg-sccs</a></td><td>Print SCCs of each function CFG</td></tr> |
| 102 | <tr><td><a href="#print-externalfnconstants">-print-externalfnconstants</a></td><td>Print external fn callsites passed constants</td></tr> |
| 103 | <tr><td><a href="#print-function">-print-function</a></td><td>Print function to stderr</td></tr> |
| 104 | <tr><td><a href="#print-module">-print-module</a></td><td>Print module to stderr</td></tr> |
| 105 | <tr><td><a href="#print-used-types">-print-used-types</a></td><td>Find Used Types</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 106 | <tr><td><a href="#profile-loader">-profile-loader</a></td><td>Load profile information from llvmprof.out</td></tr> |
| 107 | <tr><td><a href="#scalar-evolution">-scalar-evolution</a></td><td>Scalar Evolution Analysis</td></tr> |
| 108 | <tr><td><a href="#targetdata">-targetdata</a></td><td>Target Data Layout</td></tr> |
| 109 | |
| 110 | |
Gordon Henriksen | ddaa61d | 2007-10-25 08:58:56 +0000 | [diff] [blame] | 111 | <tr><th colspan="2"><b>TRANSFORM PASSES</b></th></tr> |
| 112 | <tr><th>Option</th><th>Name</th></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 113 | <tr><td><a href="#adce">-adce</a></td><td>Aggressive Dead Code Elimination</td></tr> |
| 114 | <tr><td><a href="#argpromotion">-argpromotion</a></td><td>Promote 'by reference' arguments to scalars</td></tr> |
| 115 | <tr><td><a href="#block-placement">-block-placement</a></td><td>Profile Guided Basic Block Placement</td></tr> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 116 | <tr><td><a href="#break-crit-edges">-break-crit-edges</a></td><td>Break critical edges in CFG</td></tr> |
Gordon Henriksen | a8a118b | 2008-05-08 17:46:35 +0000 | [diff] [blame] | 117 | <tr><td><a href="#codegenprepare">-codegenprepare</a></td><td>Prepare a function for code generation </td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 118 | <tr><td><a href="#condprop">-condprop</a></td><td>Conditional Propagation</td></tr> |
| 119 | <tr><td><a href="#constmerge">-constmerge</a></td><td>Merge Duplicate Global Constants</td></tr> |
| 120 | <tr><td><a href="#constprop">-constprop</a></td><td>Simple constant propagation</td></tr> |
| 121 | <tr><td><a href="#dce">-dce</a></td><td>Dead Code Elimination</td></tr> |
| 122 | <tr><td><a href="#deadargelim">-deadargelim</a></td><td>Dead Argument Elimination</td></tr> |
| 123 | <tr><td><a href="#deadtypeelim">-deadtypeelim</a></td><td>Dead Type Elimination</td></tr> |
| 124 | <tr><td><a href="#die">-die</a></td><td>Dead Instruction Elimination</td></tr> |
| 125 | <tr><td><a href="#dse">-dse</a></td><td>Dead Store Elimination</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 126 | <tr><td><a href="#globaldce">-globaldce</a></td><td>Dead Global Elimination</td></tr> |
| 127 | <tr><td><a href="#globalopt">-globalopt</a></td><td>Global Variable Optimizer</td></tr> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 128 | <tr><td><a href="#gvn">-gvn</a></td><td>Global Value Numbering</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 129 | <tr><td><a href="#indmemrem">-indmemrem</a></td><td>Indirect Malloc and Free Removal</td></tr> |
| 130 | <tr><td><a href="#indvars">-indvars</a></td><td>Canonicalize Induction Variables</td></tr> |
| 131 | <tr><td><a href="#inline">-inline</a></td><td>Function Integration/Inlining</td></tr> |
| 132 | <tr><td><a href="#insert-block-profiling">-insert-block-profiling</a></td><td>Insert instrumentation for block profiling</td></tr> |
| 133 | <tr><td><a href="#insert-edge-profiling">-insert-edge-profiling</a></td><td>Insert instrumentation for edge profiling</td></tr> |
| 134 | <tr><td><a href="#insert-function-profiling">-insert-function-profiling</a></td><td>Insert instrumentation for function profiling</td></tr> |
| 135 | <tr><td><a href="#insert-null-profiling-rs">-insert-null-profiling-rs</a></td><td>Measure profiling framework overhead</td></tr> |
| 136 | <tr><td><a href="#insert-rs-profiling-framework">-insert-rs-profiling-framework</a></td><td>Insert random sampling instrumentation framework</td></tr> |
| 137 | <tr><td><a href="#instcombine">-instcombine</a></td><td>Combine redundant instructions</td></tr> |
| 138 | <tr><td><a href="#internalize">-internalize</a></td><td>Internalize Global Symbols</td></tr> |
| 139 | <tr><td><a href="#ipconstprop">-ipconstprop</a></td><td>Interprocedural constant propagation</td></tr> |
| 140 | <tr><td><a href="#ipsccp">-ipsccp</a></td><td>Interprocedural Sparse Conditional Constant Propagation</td></tr> |
Gordon Henriksen | a8a118b | 2008-05-08 17:46:35 +0000 | [diff] [blame] | 141 | <tr><td><a href="#jump-threading">-jump-threading</a></td><td>Thread control through conditional blocks </td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 142 | <tr><td><a href="#lcssa">-lcssa</a></td><td>Loop-Closed SSA Form Pass</td></tr> |
| 143 | <tr><td><a href="#licm">-licm</a></td><td>Loop Invariant Code Motion</td></tr> |
Gordon Henriksen | a8a118b | 2008-05-08 17:46:35 +0000 | [diff] [blame] | 144 | <tr><td><a href="#loop-deletion">-loop-deletion</a></td><td>Dead Loop Deletion Pass </td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 145 | <tr><td><a href="#loop-extract">-loop-extract</a></td><td>Extract loops into new functions</td></tr> |
| 146 | <tr><td><a href="#loop-extract-single">-loop-extract-single</a></td><td>Extract at most one loop into a new function</td></tr> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 147 | <tr><td><a href="#loop-index-split">-loop-index-split</a></td><td>Index Split Loops</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 148 | <tr><td><a href="#loop-reduce">-loop-reduce</a></td><td>Loop Strength Reduction</td></tr> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 149 | <tr><td><a href="#loop-rotate">-loop-rotate</a></td><td>Rotate Loops</td></tr> |
| 150 | <tr><td><a href="#loop-unroll">-loop-unroll</a></td><td>Unroll loops</td></tr> |
| 151 | <tr><td><a href="#loop-unswitch">-loop-unswitch</a></td><td>Unswitch loops</td></tr> |
| 152 | <tr><td><a href="#loopsimplify">-loopsimplify</a></td><td>Canonicalize natural loops</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 153 | <tr><td><a href="#lowerallocs">-lowerallocs</a></td><td>Lower allocations from instructions to calls</td></tr> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 154 | <tr><td><a href="#lowerinvoke">-lowerinvoke</a></td><td>Lower invoke and unwind, for unwindless code generators</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 155 | <tr><td><a href="#lowersetjmp">-lowersetjmp</a></td><td>Lower Set Jump</td></tr> |
| 156 | <tr><td><a href="#lowerswitch">-lowerswitch</a></td><td>Lower SwitchInst's to branches</td></tr> |
| 157 | <tr><td><a href="#mem2reg">-mem2reg</a></td><td>Promote Memory to Register</td></tr> |
Gordon Henriksen | a8a118b | 2008-05-08 17:46:35 +0000 | [diff] [blame] | 158 | <tr><td><a href="#memcpyopt">-memcpyopt</a></td><td>Optimize use of memcpy and friends</td></tr> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 159 | <tr><td><a href="#mergereturn">-mergereturn</a></td><td>Unify function exit nodes</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 160 | <tr><td><a href="#prune-eh">-prune-eh</a></td><td>Remove unused exception handling info</td></tr> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 161 | <tr><td><a href="#reassociate">-reassociate</a></td><td>Reassociate expressions</td></tr> |
| 162 | <tr><td><a href="#reg2mem">-reg2mem</a></td><td>Demote all values to stack slots</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 163 | <tr><td><a href="#scalarrepl">-scalarrepl</a></td><td>Scalar Replacement of Aggregates</td></tr> |
| 164 | <tr><td><a href="#sccp">-sccp</a></td><td>Sparse Conditional Constant Propagation</td></tr> |
| 165 | <tr><td><a href="#simplify-libcalls">-simplify-libcalls</a></td><td>Simplify well-known library calls</td></tr> |
| 166 | <tr><td><a href="#simplifycfg">-simplifycfg</a></td><td>Simplify the CFG</td></tr> |
| 167 | <tr><td><a href="#strip">-strip</a></td><td>Strip all symbols from a module</td></tr> |
Gordon Henriksen | a8a118b | 2008-05-08 17:46:35 +0000 | [diff] [blame] | 168 | <tr><td><a href="#strip-dead-prototypes">-strip-dead-prototypes</a></td><td>Remove unused function declarations</td></tr> |
| 169 | <tr><td><a href="#sretpromotion">-sretpromotion</a></td><td>Promote sret arguments</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 170 | <tr><td><a href="#tailcallelim">-tailcallelim</a></td><td>Tail Call Elimination</td></tr> |
| 171 | <tr><td><a href="#tailduplicate">-tailduplicate</a></td><td>Tail Duplication</td></tr> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 172 | |
| 173 | |
Gordon Henriksen | ddaa61d | 2007-10-25 08:58:56 +0000 | [diff] [blame] | 174 | <tr><th colspan="2"><b>UTILITY PASSES</b></th></tr> |
| 175 | <tr><th>Option</th><th>Name</th></tr> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 176 | <tr><td><a href="#deadarghaX0r">-deadarghaX0r</a></td><td>Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)</td></tr> |
| 177 | <tr><td><a href="#extract-blocks">-extract-blocks</a></td><td>Extract Basic Blocks From Module (for bugpoint use)</td></tr> |
Gordon Henriksen | 90a5214 | 2007-11-05 02:05:35 +0000 | [diff] [blame] | 178 | <tr><td><a href="#preverify">-preverify</a></td><td>Preliminary module verification</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 179 | <tr><td><a href="#verify">-verify</a></td><td>Module Verifier</td></tr> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 180 | <tr><td><a href="#view-cfg">-view-cfg</a></td><td>View CFG of function</td></tr> |
| 181 | <tr><td><a href="#view-cfg-only">-view-cfg-only</a></td><td>View CFG of function (with no function bodies)</td></tr> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 182 | </table> |
| 183 | </div> |
| 184 | |
| 185 | <!-- ======================================================================= --> |
| 186 | <div class="doc_section"> <a name="example">Analysis Passes</a></div> |
| 187 | <div class="doc_text"> |
| 188 | <p>This section describes the LLVM Analysis Passes.</p> |
| 189 | </div> |
| 190 | |
| 191 | <!-------------------------------------------------------------------------- --> |
| 192 | <div class="doc_subsection"> |
| 193 | <a name="aa-eval">Exhaustive Alias Analysis Precision Evaluator</a> |
| 194 | </div> |
| 195 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 196 | <p>This is a simple N^2 alias analysis accuracy evaluator. |
| 197 | Basically, for each function in the program, it simply queries to see how the |
| 198 | alias analysis implementation answers alias queries between each pair of |
| 199 | pointers in the function.</p> |
| 200 | |
| 201 | <p>This is inspired and adapted from code by: Naveen Neelakantam, Francesco |
| 202 | Spadini, and Wojciech Stryjewski.</p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 203 | </div> |
| 204 | |
| 205 | <!-------------------------------------------------------------------------- --> |
| 206 | <div class="doc_subsection"> |
| 207 | <a name="anders-aa">Andersen's Interprocedural Alias Analysis</a> |
| 208 | </div> |
| 209 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 210 | <p> |
| 211 | This is an implementation of Andersen's interprocedural alias |
| 212 | analysis |
| 213 | </p> |
| 214 | |
| 215 | <p> |
| 216 | In pointer analysis terms, this is a subset-based, flow-insensitive, |
| 217 | field-sensitive, and context-insensitive algorithm pointer algorithm. |
| 218 | </p> |
| 219 | |
| 220 | <p> |
| 221 | This algorithm is implemented as three stages: |
| 222 | </p> |
| 223 | |
| 224 | <ol> |
| 225 | <li>Object identification.</li> |
| 226 | <li>Inclusion constraint identification.</li> |
| 227 | <li>Offline constraint graph optimization.</li> |
| 228 | <li>Inclusion constraint solving.</li> |
| 229 | </ol> |
| 230 | |
| 231 | <p> |
| 232 | The object identification stage identifies all of the memory objects in the |
| 233 | program, which includes globals, heap allocated objects, and stack allocated |
| 234 | objects. |
| 235 | </p> |
| 236 | |
| 237 | <p> |
| 238 | The inclusion constraint identification stage finds all inclusion constraints |
| 239 | in the program by scanning the program, looking for pointer assignments and |
| 240 | other statements that effect the points-to graph. For a statement like |
| 241 | <code><var>A</var> = <var>B</var></code>, this statement is processed to |
| 242 | indicate that <var>A</var> can point to anything that <var>B</var> can point |
| 243 | to. Constraints can handle copies, loads, and stores, and address taking. |
| 244 | </p> |
| 245 | |
| 246 | <p> |
| 247 | The offline constraint graph optimization portion includes offline variable |
| 248 | substitution algorithms intended to computer pointer and location |
| 249 | equivalences. Pointer equivalences are those pointers that will have the |
| 250 | same points-to sets, and location equivalences are those variables that |
| 251 | always appear together in points-to sets. |
| 252 | </p> |
| 253 | |
| 254 | <p> |
| 255 | The inclusion constraint solving phase iteratively propagates the inclusion |
| 256 | constraints until a fixed point is reached. This is an O(<var>n</var>³) |
| 257 | algorithm. |
| 258 | </p> |
| 259 | |
| 260 | <p> |
| 261 | Function constraints are handled as if they were structs with <var>X</var> |
| 262 | fields. Thus, an access to argument <var>X</var> of function <var>Y</var> is |
| 263 | an access to node index <code>getNode(<var>Y</var>) + <var>X</var></code>. |
| 264 | This representation allows handling of indirect calls without any issues. To |
| 265 | wit, an indirect call <code><var>Y</var>(<var>a</var>,<var>b</var>)</code> is |
| 266 | equivalent to <code>*(<var>Y</var> + 1) = <var>a</var>, *(<var>Y</var> + 2) = |
| 267 | <var>b</var></code>. The return node for a function <var>F</var> is always |
| 268 | located at <code>getNode(<var>F</var>) + CallReturnPos</code>. The arguments |
| 269 | start at <code>getNode(<var>F</var>) + CallArgPos</code>. |
| 270 | </p> |
Chris Lattner | b80e1ab | 2009-08-28 00:45:47 +0000 | [diff] [blame] | 271 | |
| 272 | <p> |
| 273 | Please keep in mind that the current andersen's pass has many known |
| 274 | problems and bugs. It should be considered "research quality". |
| 275 | </p> |
| 276 | |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 277 | </div> |
| 278 | |
| 279 | <!-------------------------------------------------------------------------- --> |
| 280 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 281 | <a name="basicaa">Basic Alias Analysis (default AA impl)</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 282 | </div> |
| 283 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 284 | <p> |
| 285 | This is the default implementation of the Alias Analysis interface |
| 286 | that simply implements a few identities (two different globals cannot alias, |
| 287 | etc), but otherwise does no analysis. |
| 288 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 289 | </div> |
| 290 | |
| 291 | <!-------------------------------------------------------------------------- --> |
| 292 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 293 | <a name="basiccg">Basic CallGraph Construction</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 294 | </div> |
| 295 | <div class="doc_text"> |
| 296 | <p>Yet to be written.</p> |
| 297 | </div> |
| 298 | |
| 299 | <!-------------------------------------------------------------------------- --> |
| 300 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 301 | <a name="codegenprepare">Optimize for code generation</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 302 | </div> |
| 303 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 304 | <p> |
| 305 | This pass munges the code in the input function to better prepare it for |
| 306 | SelectionDAG-based code generation. This works around limitations in it's |
| 307 | basic-block-at-a-time approach. It should eventually be removed. |
| 308 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 309 | </div> |
| 310 | |
| 311 | <!-------------------------------------------------------------------------- --> |
| 312 | <div class="doc_subsection"> |
| 313 | <a name="count-aa">Count Alias Analysis Query Responses</a> |
| 314 | </div> |
| 315 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 316 | <p> |
| 317 | A pass which can be used to count how many alias queries |
| 318 | are being made and how the alias analysis implementation being used responds. |
| 319 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 320 | </div> |
| 321 | |
| 322 | <!-------------------------------------------------------------------------- --> |
| 323 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 324 | <a name="debug-aa">AA use debugger</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 325 | </div> |
| 326 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 327 | <p> |
| 328 | This simple pass checks alias analysis users to ensure that if they |
| 329 | create a new value, they do not query AA without informing it of the value. |
| 330 | It acts as a shim over any other AA pass you want. |
| 331 | </p> |
| 332 | |
| 333 | <p> |
| 334 | Yes keeping track of every value in the program is expensive, but this is |
| 335 | a debugging pass. |
| 336 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 337 | </div> |
| 338 | |
| 339 | <!-------------------------------------------------------------------------- --> |
| 340 | <div class="doc_subsection"> |
| 341 | <a name="domfrontier">Dominance Frontier Construction</a> |
| 342 | </div> |
| 343 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 344 | <p> |
| 345 | This pass is a simple dominator construction algorithm for finding forward |
| 346 | dominator frontiers. |
| 347 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 348 | </div> |
| 349 | |
| 350 | <!-------------------------------------------------------------------------- --> |
| 351 | <div class="doc_subsection"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 352 | <a name="domtree">Dominator Tree Construction</a> |
| 353 | </div> |
| 354 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 355 | <p> |
| 356 | This pass is a simple dominator construction algorithm for finding forward |
| 357 | dominators. |
| 358 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 359 | </div> |
| 360 | |
| 361 | <!-------------------------------------------------------------------------- --> |
| 362 | <div class="doc_subsection"> |
Duncan Sands | 3ee8fc9 | 2008-09-23 12:47:39 +0000 | [diff] [blame] | 363 | <a name="dot-callgraph">Print Call Graph to 'dot' file</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 364 | </div> |
| 365 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 366 | <p> |
Duncan Sands | 3ee8fc9 | 2008-09-23 12:47:39 +0000 | [diff] [blame] | 367 | This pass, only available in <code>opt</code>, prints the call graph into a |
| 368 | <code>.dot</code> graph. This graph can then be processed with the "dot" tool |
| 369 | to convert it to postscript or some other suitable format. |
| 370 | </p> |
| 371 | </div> |
| 372 | |
| 373 | <!-------------------------------------------------------------------------- --> |
| 374 | <div class="doc_subsection"> |
| 375 | <a name="dot-cfg">Print CFG of function to 'dot' file</a> |
| 376 | </div> |
| 377 | <div class="doc_text"> |
| 378 | <p> |
| 379 | This pass, only available in <code>opt</code>, prints the control flow graph |
| 380 | into a <code>.dot</code> graph. This graph can then be processed with the |
| 381 | "dot" tool to convert it to postscript or some other suitable format. |
| 382 | </p> |
| 383 | </div> |
| 384 | |
| 385 | <!-------------------------------------------------------------------------- --> |
| 386 | <div class="doc_subsection"> |
| 387 | <a name="dot-cfg-only">Print CFG of function to 'dot' file (with no function bodies)</a> |
| 388 | </div> |
| 389 | <div class="doc_text"> |
| 390 | <p> |
| 391 | This pass, only available in <code>opt</code>, prints the control flow graph |
| 392 | into a <code>.dot</code> graph, omitting the function bodies. This graph can |
| 393 | then be processed with the "dot" tool to convert it to postscript or some |
| 394 | other suitable format. |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 395 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 396 | </div> |
| 397 | |
| 398 | <!-------------------------------------------------------------------------- --> |
| 399 | <div class="doc_subsection"> |
| 400 | <a name="globalsmodref-aa">Simple mod/ref analysis for globals</a> |
| 401 | </div> |
| 402 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 403 | <p> |
| 404 | This simple pass provides alias and mod/ref information for global values |
| 405 | that do not have their address taken, and keeps track of whether functions |
| 406 | read or write memory (are "pure"). For this simple (but very common) case, |
| 407 | we can provide pretty accurate and useful information. |
| 408 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 409 | </div> |
| 410 | |
| 411 | <!-------------------------------------------------------------------------- --> |
| 412 | <div class="doc_subsection"> |
| 413 | <a name="instcount">Counts the various types of Instructions</a> |
| 414 | </div> |
| 415 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 416 | <p> |
| 417 | This pass collects the count of all instructions and reports them |
| 418 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 419 | </div> |
| 420 | |
| 421 | <!-------------------------------------------------------------------------- --> |
| 422 | <div class="doc_subsection"> |
| 423 | <a name="intervals">Interval Partition Construction</a> |
| 424 | </div> |
| 425 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 426 | <p> |
| 427 | This analysis calculates and represents the interval partition of a function, |
| 428 | or a preexisting interval partition. |
| 429 | </p> |
| 430 | |
| 431 | <p> |
| 432 | In this way, the interval partition may be used to reduce a flow graph down |
| 433 | to its degenerate single node interval partition (unless it is irreducible). |
| 434 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 435 | </div> |
| 436 | |
| 437 | <!-------------------------------------------------------------------------- --> |
| 438 | <div class="doc_subsection"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 439 | <a name="loops">Natural Loop Construction</a> |
| 440 | </div> |
| 441 | <div class="doc_text"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 442 | <p> |
| 443 | This analysis is used to identify natural loops and determine the loop depth |
| 444 | of various nodes of the CFG. Note that the loops identified may actually be |
| 445 | several natural loops that share the same header node... not just a single |
| 446 | natural loop. |
| 447 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 448 | </div> |
| 449 | |
| 450 | <!-------------------------------------------------------------------------- --> |
| 451 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 452 | <a name="memdep">Memory Dependence Analysis</a> |
| 453 | </div> |
| 454 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 455 | <p> |
| 456 | An analysis that determines, for a given memory operation, what preceding |
| 457 | memory operations it depends on. It builds on alias analysis information, and |
| 458 | tries to provide a lazy, caching interface to a common kind of alias |
| 459 | information query. |
| 460 | </p> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 461 | </div> |
| 462 | |
| 463 | <!-------------------------------------------------------------------------- --> |
| 464 | <div class="doc_subsection"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 465 | <a name="no-aa">No Alias Analysis (always returns 'may' alias)</a> |
| 466 | </div> |
| 467 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 468 | <p> |
| 469 | Always returns "I don't know" for alias queries. NoAA is unlike other alias |
| 470 | analysis implementations, in that it does not chain to a previous analysis. As |
| 471 | such it doesn't follow many of the rules that other alias analyses must. |
| 472 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 473 | </div> |
| 474 | |
| 475 | <!-------------------------------------------------------------------------- --> |
| 476 | <div class="doc_subsection"> |
| 477 | <a name="no-profile">No Profile Information</a> |
| 478 | </div> |
| 479 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 480 | <p> |
| 481 | The default "no profile" implementation of the abstract |
| 482 | <code>ProfileInfo</code> interface. |
| 483 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 484 | </div> |
| 485 | |
| 486 | <!-------------------------------------------------------------------------- --> |
| 487 | <div class="doc_subsection"> |
| 488 | <a name="postdomfrontier">Post-Dominance Frontier Construction</a> |
| 489 | </div> |
| 490 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 491 | <p> |
| 492 | This pass is a simple post-dominator construction algorithm for finding |
| 493 | post-dominator frontiers. |
| 494 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 495 | </div> |
| 496 | |
| 497 | <!-------------------------------------------------------------------------- --> |
| 498 | <div class="doc_subsection"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 499 | <a name="postdomtree">Post-Dominator Tree Construction</a> |
| 500 | </div> |
| 501 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 502 | <p> |
| 503 | This pass is a simple post-dominator construction algorithm for finding |
| 504 | post-dominators. |
| 505 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 506 | </div> |
| 507 | |
| 508 | <!-------------------------------------------------------------------------- --> |
| 509 | <div class="doc_subsection"> |
Duncan Sands | 3ee8fc9 | 2008-09-23 12:47:39 +0000 | [diff] [blame] | 510 | <a name="print-alias-sets">Alias Set Printer</a> |
| 511 | </div> |
| 512 | <div class="doc_text"> |
| 513 | <p>Yet to be written.</p> |
| 514 | </div> |
| 515 | |
| 516 | <!-------------------------------------------------------------------------- --> |
| 517 | <div class="doc_subsection"> |
| 518 | <a name="print-callgraph">Print a call graph</a> |
| 519 | </div> |
| 520 | <div class="doc_text"> |
| 521 | <p> |
| 522 | This pass, only available in <code>opt</code>, prints the call graph to |
| 523 | standard output in a human-readable form. |
| 524 | </p> |
| 525 | </div> |
| 526 | |
| 527 | <!-------------------------------------------------------------------------- --> |
| 528 | <div class="doc_subsection"> |
| 529 | <a name="print-callgraph-sccs">Print SCCs of the Call Graph</a> |
| 530 | </div> |
| 531 | <div class="doc_text"> |
| 532 | <p> |
| 533 | This pass, only available in <code>opt</code>, prints the SCCs of the call |
| 534 | graph to standard output in a human-readable form. |
| 535 | </p> |
| 536 | </div> |
| 537 | |
| 538 | <!-------------------------------------------------------------------------- --> |
| 539 | <div class="doc_subsection"> |
| 540 | <a name="print-cfg-sccs">Print SCCs of each function CFG</a> |
| 541 | </div> |
| 542 | <div class="doc_text"> |
| 543 | <p> |
| 544 | This pass, only available in <code>opt</code>, prints the SCCs of each |
| 545 | function CFG to standard output in a human-readable form. |
| 546 | </p> |
| 547 | </div> |
| 548 | |
| 549 | <!-------------------------------------------------------------------------- --> |
| 550 | <div class="doc_subsection"> |
| 551 | <a name="print-externalfnconstants">Print external fn callsites passed constants</a> |
| 552 | </div> |
| 553 | <div class="doc_text"> |
| 554 | <p> |
| 555 | This pass, only available in <code>opt</code>, prints out call sites to |
| 556 | external functions that are called with constant arguments. This can be |
| 557 | useful when looking for standard library functions we should constant fold |
| 558 | or handle in alias analyses. |
| 559 | </p> |
| 560 | </div> |
| 561 | |
| 562 | <!-------------------------------------------------------------------------- --> |
| 563 | <div class="doc_subsection"> |
| 564 | <a name="print-function">Print function to stderr</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 565 | </div> |
| 566 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 567 | <p> |
| 568 | The <code>PrintFunctionPass</code> class is designed to be pipelined with |
| 569 | other <code>FunctionPass</code>es, and prints out the functions of the module |
| 570 | as they are processed. |
| 571 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 572 | </div> |
| 573 | |
| 574 | <!-------------------------------------------------------------------------- --> |
| 575 | <div class="doc_subsection"> |
Duncan Sands | 3ee8fc9 | 2008-09-23 12:47:39 +0000 | [diff] [blame] | 576 | <a name="print-module">Print module to stderr</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 577 | </div> |
| 578 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 579 | <p> |
| 580 | This pass simply prints out the entire module when it is executed. |
| 581 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 582 | </div> |
| 583 | |
| 584 | <!-------------------------------------------------------------------------- --> |
| 585 | <div class="doc_subsection"> |
Duncan Sands | 3ee8fc9 | 2008-09-23 12:47:39 +0000 | [diff] [blame] | 586 | <a name="print-used-types">Find Used Types</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 587 | </div> |
| 588 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 589 | <p> |
| 590 | This pass is used to seek out all of the types in use by the program. Note |
| 591 | that this analysis explicitly does not include types only used by the symbol |
| 592 | table. |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 593 | </div> |
| 594 | |
| 595 | <!-------------------------------------------------------------------------- --> |
| 596 | <div class="doc_subsection"> |
| 597 | <a name="profile-loader">Load profile information from llvmprof.out</a> |
| 598 | </div> |
| 599 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 600 | <p> |
| 601 | A concrete implementation of profiling information that loads the information |
| 602 | from a profile dump file. |
| 603 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 604 | </div> |
| 605 | |
| 606 | <!-------------------------------------------------------------------------- --> |
| 607 | <div class="doc_subsection"> |
| 608 | <a name="scalar-evolution">Scalar Evolution Analysis</a> |
| 609 | </div> |
| 610 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 611 | <p> |
| 612 | The <code>ScalarEvolution</code> analysis can be used to analyze and |
| 613 | catagorize scalar expressions in loops. It specializes in recognizing general |
| 614 | induction variables, representing them with the abstract and opaque |
| 615 | <code>SCEV</code> class. Given this analysis, trip counts of loops and other |
| 616 | important properties can be obtained. |
| 617 | </p> |
| 618 | |
| 619 | <p> |
| 620 | This analysis is primarily useful for induction variable substitution and |
| 621 | strength reduction. |
| 622 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 623 | </div> |
| 624 | |
| 625 | <!-------------------------------------------------------------------------- --> |
| 626 | <div class="doc_subsection"> |
| 627 | <a name="targetdata">Target Data Layout</a> |
| 628 | </div> |
| 629 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 630 | <p>Provides other passes access to information on how the size and alignment |
| 631 | required by the the target ABI for various data types.</p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 632 | </div> |
| 633 | |
| 634 | <!-- ======================================================================= --> |
| 635 | <div class="doc_section"> <a name="transform">Transform Passes</a></div> |
| 636 | <div class="doc_text"> |
| 637 | <p>This section describes the LLVM Transform Passes.</p> |
| 638 | </div> |
| 639 | |
| 640 | <!-------------------------------------------------------------------------- --> |
| 641 | <div class="doc_subsection"> |
| 642 | <a name="adce">Aggressive Dead Code Elimination</a> |
| 643 | </div> |
| 644 | <div class="doc_text"> |
Reid Spencer | af4af3a | 2007-03-27 02:49:31 +0000 | [diff] [blame] | 645 | <p>ADCE aggressively tries to eliminate code. This pass is similar to |
| 646 | <a href="#dce">DCE</a> but it assumes that values are dead until proven |
| 647 | otherwise. This is similar to <a href="#sccp">SCCP</a>, except applied to |
| 648 | the liveness of values.</p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 649 | </div> |
| 650 | |
| 651 | <!-------------------------------------------------------------------------- --> |
| 652 | <div class="doc_subsection"> |
| 653 | <a name="argpromotion">Promote 'by reference' arguments to scalars</a> |
| 654 | </div> |
| 655 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 656 | <p> |
| 657 | This pass promotes "by reference" arguments to be "by value" arguments. In |
| 658 | practice, this means looking for internal functions that have pointer |
| 659 | arguments. If it can prove, through the use of alias analysis, that an |
| 660 | argument is *only* loaded, then it can pass the value into the function |
| 661 | instead of the address of the value. This can cause recursive simplification |
| 662 | of code and lead to the elimination of allocas (especially in C++ template |
| 663 | code like the STL). |
| 664 | </p> |
| 665 | |
| 666 | <p> |
| 667 | This pass also handles aggregate arguments that are passed into a function, |
| 668 | scalarizing them if the elements of the aggregate are only loaded. Note that |
| 669 | it refuses to scalarize aggregates which would require passing in more than |
| 670 | three operands to the function, because passing thousands of operands for a |
| 671 | large array or structure is unprofitable! |
| 672 | </p> |
| 673 | |
| 674 | <p> |
| 675 | Note that this transformation could also be done for arguments that are only |
| 676 | stored to (returning the value instead), but does not currently. This case |
| 677 | would be best handled when and if LLVM starts supporting multiple return |
| 678 | values from functions. |
| 679 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 680 | </div> |
| 681 | |
| 682 | <!-------------------------------------------------------------------------- --> |
| 683 | <div class="doc_subsection"> |
| 684 | <a name="block-placement">Profile Guided Basic Block Placement</a> |
| 685 | </div> |
| 686 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 687 | <p>This pass is a very simple profile guided basic block placement algorithm. |
| 688 | The idea is to put frequently executed blocks together at the start of the |
| 689 | function and hopefully increase the number of fall-through conditional |
| 690 | branches. If there is no profile information for a particular function, this |
| 691 | pass basically orders blocks in depth-first order.</p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 692 | </div> |
| 693 | |
| 694 | <!-------------------------------------------------------------------------- --> |
| 695 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 696 | <a name="break-crit-edges">Break critical edges in CFG</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 697 | </div> |
| 698 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 699 | <p> |
| 700 | Break all of the critical edges in the CFG by inserting a dummy basic block. |
| 701 | It may be "required" by passes that cannot deal with critical edges. This |
| 702 | transformation obviously invalidates the CFG, but can update forward dominator |
| 703 | (set, immediate dominators, tree, and frontier) information. |
| 704 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 705 | </div> |
| 706 | |
| 707 | <!-------------------------------------------------------------------------- --> |
| 708 | <div class="doc_subsection"> |
Gordon Henriksen | a8a118b | 2008-05-08 17:46:35 +0000 | [diff] [blame] | 709 | <a name="codegenprepare">Prepare a function for code generation</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 710 | </div> |
| 711 | <div class="doc_text"> |
Gordon Henriksen | a8a118b | 2008-05-08 17:46:35 +0000 | [diff] [blame] | 712 | This pass munges the code in the input function to better prepare it for |
| 713 | SelectionDAG-based code generation. This works around limitations in it's |
| 714 | basic-block-at-a-time approach. It should eventually be removed. |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 715 | </div> |
| 716 | |
| 717 | <!-------------------------------------------------------------------------- --> |
| 718 | <div class="doc_subsection"> |
| 719 | <a name="condprop">Conditional Propagation</a> |
| 720 | </div> |
| 721 | <div class="doc_text"> |
Reid Spencer | af4af3a | 2007-03-27 02:49:31 +0000 | [diff] [blame] | 722 | <p>This pass propagates information about conditional expressions through the |
| 723 | program, allowing it to eliminate conditional branches in some cases.</p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 724 | </div> |
| 725 | |
| 726 | <!-------------------------------------------------------------------------- --> |
| 727 | <div class="doc_subsection"> |
| 728 | <a name="constmerge">Merge Duplicate Global Constants</a> |
| 729 | </div> |
| 730 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 731 | <p> |
| 732 | Merges duplicate global constants together into a single constant that is |
| 733 | shared. This is useful because some passes (ie TraceValues) insert a lot of |
| 734 | string constants into the program, regardless of whether or not an existing |
| 735 | string is available. |
| 736 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 737 | </div> |
| 738 | |
| 739 | <!-------------------------------------------------------------------------- --> |
| 740 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 741 | <a name="constprop">Simple constant propagation</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 742 | </div> |
| 743 | <div class="doc_text"> |
Reid Spencer | af4af3a | 2007-03-27 02:49:31 +0000 | [diff] [blame] | 744 | <p>This file implements constant propagation and merging. It looks for |
| 745 | instructions involving only constant operands and replaces them with a |
Gordon Henriksen | ddaa61d | 2007-10-25 08:58:56 +0000 | [diff] [blame] | 746 | constant value instead of an instruction. For example:</p> |
| 747 | <blockquote><pre>add i32 1, 2</pre></blockquote> |
| 748 | <p>becomes</p> |
| 749 | <blockquote><pre>i32 3</pre></blockquote> |
Reid Spencer | af4af3a | 2007-03-27 02:49:31 +0000 | [diff] [blame] | 750 | <p>NOTE: this pass has a habit of making definitions be dead. It is a good |
| 751 | idea to to run a <a href="#die">DIE</a> (Dead Instruction Elimination) pass |
| 752 | sometime after running this pass.</p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 753 | </div> |
| 754 | |
| 755 | <!-------------------------------------------------------------------------- --> |
| 756 | <div class="doc_subsection"> |
| 757 | <a name="dce">Dead Code Elimination</a> |
| 758 | </div> |
| 759 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 760 | <p> |
| 761 | Dead code elimination is similar to <a href="#die">dead instruction |
| 762 | elimination</a>, but it rechecks instructions that were used by removed |
| 763 | instructions to see if they are newly dead. |
| 764 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 765 | </div> |
| 766 | |
| 767 | <!-------------------------------------------------------------------------- --> |
| 768 | <div class="doc_subsection"> |
| 769 | <a name="deadargelim">Dead Argument Elimination</a> |
| 770 | </div> |
| 771 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 772 | <p> |
| 773 | This pass deletes dead arguments from internal functions. Dead argument |
| 774 | elimination removes arguments which are directly dead, as well as arguments |
| 775 | only passed into function calls as dead arguments of other functions. This |
| 776 | pass also deletes dead arguments in a similar way. |
| 777 | </p> |
| 778 | |
| 779 | <p> |
| 780 | This pass is often useful as a cleanup pass to run after aggressive |
| 781 | interprocedural passes, which add possibly-dead arguments. |
| 782 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 783 | </div> |
| 784 | |
| 785 | <!-------------------------------------------------------------------------- --> |
| 786 | <div class="doc_subsection"> |
| 787 | <a name="deadtypeelim">Dead Type Elimination</a> |
| 788 | </div> |
| 789 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 790 | <p> |
| 791 | This pass is used to cleanup the output of GCC. It eliminate names for types |
| 792 | that are unused in the entire translation unit, using the <a |
| 793 | href="#findusedtypes">find used types</a> pass. |
| 794 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 795 | </div> |
| 796 | |
| 797 | <!-------------------------------------------------------------------------- --> |
| 798 | <div class="doc_subsection"> |
| 799 | <a name="die">Dead Instruction Elimination</a> |
| 800 | </div> |
| 801 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 802 | <p> |
| 803 | Dead instruction elimination performs a single pass over the function, |
| 804 | removing instructions that are obviously dead. |
| 805 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 806 | </div> |
| 807 | |
| 808 | <!-------------------------------------------------------------------------- --> |
| 809 | <div class="doc_subsection"> |
| 810 | <a name="dse">Dead Store Elimination</a> |
| 811 | </div> |
| 812 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 813 | <p> |
| 814 | A trivial dead store elimination that only considers basic-block local |
| 815 | redundant stores. |
| 816 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 817 | </div> |
| 818 | |
| 819 | <!-------------------------------------------------------------------------- --> |
| 820 | <div class="doc_subsection"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 821 | <a name="globaldce">Dead Global Elimination</a> |
| 822 | </div> |
| 823 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 824 | <p> |
| 825 | This transform is designed to eliminate unreachable internal globals from the |
| 826 | program. It uses an aggressive algorithm, searching out globals that are |
| 827 | known to be alive. After it finds all of the globals which are needed, it |
| 828 | deletes whatever is left over. This allows it to delete recursive chunks of |
| 829 | the program which are unreachable. |
| 830 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 831 | </div> |
| 832 | |
| 833 | <!-------------------------------------------------------------------------- --> |
| 834 | <div class="doc_subsection"> |
| 835 | <a name="globalopt">Global Variable Optimizer</a> |
| 836 | </div> |
| 837 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 838 | <p> |
| 839 | This pass transforms simple global variables that never have their address |
| 840 | taken. If obviously true, it marks read/write globals as constant, deletes |
| 841 | variables only stored to, etc. |
| 842 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 843 | </div> |
| 844 | |
| 845 | <!-------------------------------------------------------------------------- --> |
| 846 | <div class="doc_subsection"> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 847 | <a name="gvn">Global Value Numbering</a> |
| 848 | </div> |
| 849 | <div class="doc_text"> |
| 850 | <p> |
Chris Lattner | 60f0340 | 2009-10-10 18:40:48 +0000 | [diff] [blame] | 851 | This pass performs global value numbering to eliminate fully and partially |
| 852 | redundant instructions. It also performs redundant load elimination. |
Matthijs Kooijman | 845f524 | 2008-06-05 07:55:49 +0000 | [diff] [blame] | 853 | </p> |
Gordon Henriksen | 0e15dc2 | 2007-10-25 10:18:27 +0000 | [diff] [blame] | 854 | </div> |
| 855 | |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 856 | |
| 857 | <!-------------------------------------------------------------------------- --> |
| 858 | <div class="doc_subsection"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 859 | <a name="indmemrem">Indirect Malloc and Free Removal</a> |
| 860 | </div> |
| 861 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 862 | <p> |
| 863 | This pass finds places where memory allocation functions may escape into |
| 864 | indirect land. Some transforms are much easier (aka possible) only if free |
| 865 | or malloc are not called indirectly. |
| 866 | </p> |
| 867 | |
| 868 | <p> |
| 869 | Thus find places where the address of memory functions are taken and construct |
| 870 | bounce functions with direct calls of those functions. |
| 871 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 872 | </div> |
| 873 | |
| 874 | <!-------------------------------------------------------------------------- --> |
| 875 | <div class="doc_subsection"> |
| 876 | <a name="indvars">Canonicalize Induction Variables</a> |
| 877 | </div> |
| 878 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 879 | <p> |
| 880 | This transformation analyzes and transforms the induction variables (and |
| 881 | computations derived from them) into simpler forms suitable for subsequent |
| 882 | analysis and transformation. |
| 883 | </p> |
| 884 | |
| 885 | <p> |
| 886 | This transformation makes the following changes to each loop with an |
| 887 | identifiable induction variable: |
| 888 | </p> |
| 889 | |
| 890 | <ol> |
| 891 | <li>All loops are transformed to have a <em>single</em> canonical |
| 892 | induction variable which starts at zero and steps by one.</li> |
| 893 | <li>The canonical induction variable is guaranteed to be the first PHI node |
| 894 | in the loop header block.</li> |
| 895 | <li>Any pointer arithmetic recurrences are raised to use array |
| 896 | subscripts.</li> |
| 897 | </ol> |
| 898 | |
| 899 | <p> |
| 900 | If the trip count of a loop is computable, this pass also makes the following |
| 901 | changes: |
| 902 | </p> |
| 903 | |
| 904 | <ol> |
| 905 | <li>The exit condition for the loop is canonicalized to compare the |
| 906 | induction value against the exit value. This turns loops like: |
| 907 | <blockquote><pre>for (i = 7; i*i < 1000; ++i)</pre></blockquote> |
| 908 | into |
| 909 | <blockquote><pre>for (i = 0; i != 25; ++i)</pre></blockquote></li> |
| 910 | <li>Any use outside of the loop of an expression derived from the indvar |
| 911 | is changed to compute the derived value outside of the loop, eliminating |
| 912 | the dependence on the exit value of the induction variable. If the only |
| 913 | purpose of the loop is to compute the exit value of some derived |
| 914 | expression, this transformation will make the loop dead.</li> |
Gordon Henriksen | e626bbe | 2007-11-04 16:17:00 +0000 | [diff] [blame] | 915 | </ol> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 916 | |
| 917 | <p> |
| 918 | This transformation should be followed by strength reduction after all of the |
| 919 | desired loop transformations have been performed. Additionally, on targets |
| 920 | where it is profitable, the loop could be transformed to count down to zero |
| 921 | (the "do loop" optimization). |
| 922 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 923 | </div> |
| 924 | |
| 925 | <!-------------------------------------------------------------------------- --> |
| 926 | <div class="doc_subsection"> |
| 927 | <a name="inline">Function Integration/Inlining</a> |
| 928 | </div> |
| 929 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 930 | <p> |
| 931 | Bottom-up inlining of functions into callees. |
| 932 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 933 | </div> |
| 934 | |
| 935 | <!-------------------------------------------------------------------------- --> |
| 936 | <div class="doc_subsection"> |
| 937 | <a name="insert-block-profiling">Insert instrumentation for block profiling</a> |
| 938 | </div> |
| 939 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 940 | <p> |
| 941 | This pass instruments the specified program with counters for basic block |
| 942 | profiling, which counts the number of times each basic block executes. This |
| 943 | is the most basic form of profiling, which can tell which blocks are hot, but |
| 944 | cannot reliably detect hot paths through the CFG. |
| 945 | </p> |
| 946 | |
| 947 | <p> |
| 948 | Note that this implementation is very naïve. Control equivalent regions of |
| 949 | the CFG should not require duplicate counters, but it does put duplicate |
| 950 | counters in. |
| 951 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 952 | </div> |
| 953 | |
| 954 | <!-------------------------------------------------------------------------- --> |
| 955 | <div class="doc_subsection"> |
| 956 | <a name="insert-edge-profiling">Insert instrumentation for edge profiling</a> |
| 957 | </div> |
| 958 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 959 | <p> |
| 960 | This pass instruments the specified program with counters for edge profiling. |
| 961 | Edge profiling can give a reasonable approximation of the hot paths through a |
| 962 | program, and is used for a wide variety of program transformations. |
| 963 | </p> |
| 964 | |
| 965 | <p> |
| 966 | Note that this implementation is very naïve. It inserts a counter for |
| 967 | <em>every</em> edge in the program, instead of using control flow information |
| 968 | to prune the number of counters inserted. |
| 969 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 970 | </div> |
| 971 | |
| 972 | <!-------------------------------------------------------------------------- --> |
| 973 | <div class="doc_subsection"> |
| 974 | <a name="insert-function-profiling">Insert instrumentation for function profiling</a> |
| 975 | </div> |
| 976 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 977 | <p> |
| 978 | This pass instruments the specified program with counters for function |
| 979 | profiling, which counts the number of times each function is called. |
| 980 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 981 | </div> |
| 982 | |
| 983 | <!-------------------------------------------------------------------------- --> |
| 984 | <div class="doc_subsection"> |
| 985 | <a name="insert-null-profiling-rs">Measure profiling framework overhead</a> |
| 986 | </div> |
| 987 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 988 | <p> |
| 989 | The basic profiler that does nothing. It is the default profiler and thus |
| 990 | terminates <code>RSProfiler</code> chains. It is useful for measuring |
| 991 | framework overhead. |
| 992 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 993 | </div> |
| 994 | |
| 995 | <!-------------------------------------------------------------------------- --> |
| 996 | <div class="doc_subsection"> |
| 997 | <a name="insert-rs-profiling-framework">Insert random sampling instrumentation framework</a> |
| 998 | </div> |
| 999 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 1000 | <p> |
| 1001 | The second stage of the random-sampling instrumentation framework, duplicates |
| 1002 | all instructions in a function, ignoring the profiling code, then connects the |
| 1003 | two versions together at the entry and at backedges. At each connection point |
| 1004 | a choice is made as to whether to jump to the profiled code (take a sample) or |
| 1005 | execute the unprofiled code. |
| 1006 | </p> |
| 1007 | |
| 1008 | <p> |
| 1009 | After this pass, it is highly recommended to run<a href="#mem2reg">mem2reg</a> |
| 1010 | and <a href="#adce">adce</a>. <a href="#instcombine">instcombine</a>, |
| 1011 | <a href="#load-vn">load-vn</a>, <a href="#gdce">gdce</a>, and |
| 1012 | <a href="#dse">dse</a> also are good to run afterwards. |
| 1013 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1014 | </div> |
| 1015 | |
| 1016 | <!-------------------------------------------------------------------------- --> |
| 1017 | <div class="doc_subsection"> |
| 1018 | <a name="instcombine">Combine redundant instructions</a> |
| 1019 | </div> |
| 1020 | <div class="doc_text"> |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 1021 | <p> |
| 1022 | Combine instructions to form fewer, simple |
| 1023 | instructions. This pass does not modify the CFG This pass is where algebraic |
| 1024 | simplification happens. |
| 1025 | </p> |
| 1026 | |
| 1027 | <p> |
| 1028 | This pass combines things like: |
| 1029 | </p> |
| 1030 | |
| 1031 | <blockquote><pre |
| 1032 | >%Y = add i32 %X, 1 |
| 1033 | %Z = add i32 %Y, 1</pre></blockquote> |
| 1034 | |
| 1035 | <p> |
| 1036 | into: |
| 1037 | </p> |
| 1038 | |
| 1039 | <blockquote><pre |
| 1040 | >%Z = add i32 %X, 2</pre></blockquote> |
| 1041 | |
| 1042 | <p> |
| 1043 | This is a simple worklist driven algorithm. |
| 1044 | </p> |
| 1045 | |
| 1046 | <p> |
| 1047 | This pass guarantees that the following canonicalizations are performed on |
| 1048 | the program: |
| 1049 | </p> |
| 1050 | |
| 1051 | <ul> |
| 1052 | <li>If a binary operator has a constant operand, it is moved to the right- |
| 1053 | hand side.</li> |
| 1054 | <li>Bitwise operators with constant operands are always grouped so that |
| 1055 | shifts are performed first, then <code>or</code>s, then |
| 1056 | <code>and</code>s, then <code>xor</code>s.</li> |
| 1057 | <li>Compare instructions are converted from <code><</code>, |
| 1058 | <code>></code>, <code>≤</code>, or <code>≥</code> to |
| 1059 | <code>=</code> or <code>≠</code> if possible.</li> |
| 1060 | <li>All <code>cmp</code> instructions on boolean values are replaced with |
| 1061 | logical operations.</li> |
| 1062 | <li><code>add <var>X</var>, <var>X</var></code> is represented as |
| 1063 | <code>mul <var>X</var>, 2</code> ⇒ <code>shl <var>X</var>, 1</code></li> |
| 1064 | <li>Multiplies with a constant power-of-two argument are transformed into |
| 1065 | shifts.</li> |
| 1066 | <li>… etc.</li> |
| 1067 | </ul> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1068 | </div> |
| 1069 | |
| 1070 | <!-------------------------------------------------------------------------- --> |
| 1071 | <div class="doc_subsection"> |
| 1072 | <a name="internalize">Internalize Global Symbols</a> |
| 1073 | </div> |
| 1074 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1075 | <p> |
| 1076 | This pass loops over all of the functions in the input module, looking for a |
| 1077 | main function. If a main function is found, all other functions and all |
| 1078 | global variables with initializers are marked as internal. |
| 1079 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1080 | </div> |
| 1081 | |
| 1082 | <!-------------------------------------------------------------------------- --> |
| 1083 | <div class="doc_subsection"> |
| 1084 | <a name="ipconstprop">Interprocedural constant propagation</a> |
| 1085 | </div> |
| 1086 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1087 | <p> |
| 1088 | This pass implements an <em>extremely</em> simple interprocedural constant |
| 1089 | propagation pass. It could certainly be improved in many different ways, |
| 1090 | like using a worklist. This pass makes arguments dead, but does not remove |
| 1091 | them. The existing dead argument elimination pass should be run after this |
| 1092 | to clean up the mess. |
| 1093 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1094 | </div> |
| 1095 | |
| 1096 | <!-------------------------------------------------------------------------- --> |
| 1097 | <div class="doc_subsection"> |
| 1098 | <a name="ipsccp">Interprocedural Sparse Conditional Constant Propagation</a> |
| 1099 | </div> |
| 1100 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1101 | <p> |
| 1102 | An interprocedural variant of <a href="#sccp">Sparse Conditional Constant |
| 1103 | Propagation</a>. |
| 1104 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1105 | </div> |
| 1106 | |
| 1107 | <!-------------------------------------------------------------------------- --> |
| 1108 | <div class="doc_subsection"> |
Gordon Henriksen | a8a118b | 2008-05-08 17:46:35 +0000 | [diff] [blame] | 1109 | <a name="jump-threading">Thread control through conditional blocks</a> |
| 1110 | </div> |
| 1111 | <div class="doc_text"> |
| 1112 | <p> |
| 1113 | Jump threading tries to find distinct threads of control flow running through |
| 1114 | a basic block. This pass looks at blocks that have multiple predecessors and |
| 1115 | multiple successors. If one or more of the predecessors of the block can be |
| 1116 | proven to always cause a jump to one of the successors, we forward the edge |
| 1117 | from the predecessor to the successor by duplicating the contents of this |
| 1118 | block. |
| 1119 | </p> |
| 1120 | <p> |
| 1121 | An example of when this can occur is code like this: |
| 1122 | </p> |
| 1123 | |
| 1124 | <pre |
| 1125 | >if () { ... |
| 1126 | X = 4; |
| 1127 | } |
| 1128 | if (X < 3) {</pre> |
| 1129 | |
| 1130 | <p> |
| 1131 | In this case, the unconditional branch at the end of the first if can be |
| 1132 | revectored to the false side of the second if. |
| 1133 | </p> |
| 1134 | </div> |
| 1135 | |
| 1136 | <!-------------------------------------------------------------------------- --> |
| 1137 | <div class="doc_subsection"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1138 | <a name="lcssa">Loop-Closed SSA Form Pass</a> |
| 1139 | </div> |
| 1140 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1141 | <p> |
| 1142 | This pass transforms loops by placing phi nodes at the end of the loops for |
| 1143 | all values that are live across the loop boundary. For example, it turns |
| 1144 | the left into the right code: |
| 1145 | </p> |
| 1146 | |
| 1147 | <pre |
| 1148 | >for (...) for (...) |
| 1149 | if (c) if (c) |
| 1150 | X1 = ... X1 = ... |
| 1151 | else else |
| 1152 | X2 = ... X2 = ... |
| 1153 | X3 = phi(X1, X2) X3 = phi(X1, X2) |
| 1154 | ... = X3 + 4 X4 = phi(X3) |
| 1155 | ... = X4 + 4</pre> |
| 1156 | |
| 1157 | <p> |
| 1158 | This is still valid LLVM; the extra phi nodes are purely redundant, and will |
| 1159 | be trivially eliminated by <code>InstCombine</code>. The major benefit of |
| 1160 | this transformation is that it makes many other loop optimizations, such as |
| 1161 | LoopUnswitching, simpler. |
| 1162 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1163 | </div> |
| 1164 | |
| 1165 | <!-------------------------------------------------------------------------- --> |
| 1166 | <div class="doc_subsection"> |
| 1167 | <a name="licm">Loop Invariant Code Motion</a> |
| 1168 | </div> |
| 1169 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1170 | <p> |
| 1171 | This pass performs loop invariant code motion, attempting to remove as much |
| 1172 | code from the body of a loop as possible. It does this by either hoisting |
| 1173 | code into the preheader block, or by sinking code to the exit blocks if it is |
| 1174 | safe. This pass also promotes must-aliased memory locations in the loop to |
| 1175 | live in registers, thus hoisting and sinking "invariant" loads and stores. |
| 1176 | </p> |
| 1177 | |
| 1178 | <p> |
| 1179 | This pass uses alias analysis for two purposes: |
| 1180 | </p> |
| 1181 | |
| 1182 | <ul> |
| 1183 | <li>Moving loop invariant loads and calls out of loops. If we can determine |
| 1184 | that a load or call inside of a loop never aliases anything stored to, |
| 1185 | we can hoist it or sink it like any other instruction.</li> |
| 1186 | <li>Scalar Promotion of Memory - If there is a store instruction inside of |
| 1187 | the loop, we try to move the store to happen AFTER the loop instead of |
| 1188 | inside of the loop. This can only happen if a few conditions are true: |
| 1189 | <ul> |
| 1190 | <li>The pointer stored through is loop invariant.</li> |
| 1191 | <li>There are no stores or loads in the loop which <em>may</em> alias |
| 1192 | the pointer. There are no calls in the loop which mod/ref the |
| 1193 | pointer.</li> |
| 1194 | </ul> |
| 1195 | If these conditions are true, we can promote the loads and stores in the |
| 1196 | loop of the pointer to use a temporary alloca'd variable. We then use |
| 1197 | the mem2reg functionality to construct the appropriate SSA form for the |
| 1198 | variable.</li> |
| 1199 | </ul> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1200 | </div> |
Gordon Henriksen | a8a118b | 2008-05-08 17:46:35 +0000 | [diff] [blame] | 1201 | <!-------------------------------------------------------------------------- --> |
| 1202 | <div class="doc_subsection"> |
| 1203 | <a name="loop-deletion">Dead Loop Deletion Pass</a> |
| 1204 | </div> |
| 1205 | <div class="doc_text"> |
| 1206 | <p> |
| 1207 | This file implements the Dead Loop Deletion Pass. This pass is responsible |
| 1208 | for eliminating loops with non-infinite computable trip counts that have no |
| 1209 | side effects or volatile instructions, and do not contribute to the |
| 1210 | computation of the function's return value. |
| 1211 | </p> |
| 1212 | </div> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1213 | |
| 1214 | <!-------------------------------------------------------------------------- --> |
| 1215 | <div class="doc_subsection"> |
| 1216 | <a name="loop-extract">Extract loops into new functions</a> |
| 1217 | </div> |
| 1218 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1219 | <p> |
| 1220 | A pass wrapper around the <code>ExtractLoop()</code> scalar transformation to |
| 1221 | extract each top-level loop into its own new function. If the loop is the |
| 1222 | <em>only</em> loop in a given function, it is not touched. This is a pass most |
| 1223 | useful for debugging via bugpoint. |
| 1224 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1225 | </div> |
| 1226 | |
| 1227 | <!-------------------------------------------------------------------------- --> |
| 1228 | <div class="doc_subsection"> |
| 1229 | <a name="loop-extract-single">Extract at most one loop into a new function</a> |
| 1230 | </div> |
| 1231 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1232 | <p> |
| 1233 | Similar to <a href="#loop-extract">Extract loops into new functions</a>, |
| 1234 | this pass extracts one natural loop from the program into a function if it |
| 1235 | can. This is used by bugpoint. |
| 1236 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1237 | </div> |
| 1238 | |
| 1239 | <!-------------------------------------------------------------------------- --> |
| 1240 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1241 | <a name="loop-index-split">Index Split Loops</a> |
| 1242 | </div> |
| 1243 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1244 | <p> |
| 1245 | This pass divides loop's iteration range by spliting loop such that each |
| 1246 | individual loop is executed efficiently. |
| 1247 | </p> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1248 | </div> |
| 1249 | |
| 1250 | <!-------------------------------------------------------------------------- --> |
| 1251 | <div class="doc_subsection"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1252 | <a name="loop-reduce">Loop Strength Reduction</a> |
| 1253 | </div> |
| 1254 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1255 | <p> |
| 1256 | This pass performs a strength reduction on array references inside loops that |
| 1257 | have as one or more of their components the loop induction variable. This is |
| 1258 | accomplished by creating a new value to hold the initial value of the array |
| 1259 | access for the first iteration, and then creating a new GEP instruction in |
| 1260 | the loop to increment the value by the appropriate amount. |
| 1261 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1262 | </div> |
| 1263 | |
| 1264 | <!-------------------------------------------------------------------------- --> |
| 1265 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1266 | <a name="loop-rotate">Rotate Loops</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1267 | </div> |
| 1268 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1269 | <p>A simple loop rotation transformation.</p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1270 | </div> |
| 1271 | |
| 1272 | <!-------------------------------------------------------------------------- --> |
| 1273 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1274 | <a name="loop-unroll">Unroll loops</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1275 | </div> |
| 1276 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1277 | <p> |
| 1278 | This pass implements a simple loop unroller. It works best when loops have |
| 1279 | been canonicalized by the <a href="#indvars"><tt>-indvars</tt></a> pass, |
| 1280 | allowing it to determine the trip counts of loops easily. |
| 1281 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1282 | </div> |
| 1283 | |
| 1284 | <!-------------------------------------------------------------------------- --> |
| 1285 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1286 | <a name="loop-unswitch">Unswitch loops</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1287 | </div> |
| 1288 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1289 | <p> |
| 1290 | This pass transforms loops that contain branches on loop-invariant conditions |
| 1291 | to have multiple loops. For example, it turns the left into the right code: |
| 1292 | </p> |
| 1293 | |
| 1294 | <pre |
| 1295 | >for (...) if (lic) |
| 1296 | A for (...) |
| 1297 | if (lic) A; B; C |
| 1298 | B else |
| 1299 | C for (...) |
| 1300 | A; C</pre> |
| 1301 | |
| 1302 | <p> |
| 1303 | This can increase the size of the code exponentially (doubling it every time |
| 1304 | a loop is unswitched) so we only unswitch if the resultant code will be |
| 1305 | smaller than a threshold. |
| 1306 | </p> |
| 1307 | |
| 1308 | <p> |
| 1309 | This pass expects LICM to be run before it to hoist invariant conditions out |
| 1310 | of the loop, to make the unswitching opportunity obvious. |
| 1311 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1312 | </div> |
| 1313 | |
| 1314 | <!-------------------------------------------------------------------------- --> |
| 1315 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1316 | <a name="loopsimplify">Canonicalize natural loops</a> |
| 1317 | </div> |
| 1318 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1319 | <p> |
| 1320 | This pass performs several transformations to transform natural loops into a |
| 1321 | simpler form, which makes subsequent analyses and transformations simpler and |
| 1322 | more effective. |
| 1323 | </p> |
| 1324 | |
| 1325 | <p> |
| 1326 | Loop pre-header insertion guarantees that there is a single, non-critical |
| 1327 | entry edge from outside of the loop to the loop header. This simplifies a |
| 1328 | number of analyses and transformations, such as LICM. |
| 1329 | </p> |
| 1330 | |
| 1331 | <p> |
| 1332 | Loop exit-block insertion guarantees that all exit blocks from the loop |
| 1333 | (blocks which are outside of the loop that have predecessors inside of the |
| 1334 | loop) only have predecessors from inside of the loop (and are thus dominated |
| 1335 | by the loop header). This simplifies transformations such as store-sinking |
| 1336 | that are built into LICM. |
| 1337 | </p> |
| 1338 | |
| 1339 | <p> |
| 1340 | This pass also guarantees that loops will have exactly one backedge. |
| 1341 | </p> |
| 1342 | |
| 1343 | <p> |
| 1344 | Note that the simplifycfg pass will clean up blocks which are split out but |
| 1345 | end up being unnecessary, so usage of this pass should not pessimize |
| 1346 | generated code. |
| 1347 | </p> |
| 1348 | |
| 1349 | <p> |
| 1350 | This pass obviously modifies the CFG, but updates loop information and |
| 1351 | dominator information. |
| 1352 | </p> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1353 | </div> |
| 1354 | |
| 1355 | <!-------------------------------------------------------------------------- --> |
| 1356 | <div class="doc_subsection"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1357 | <a name="lowerallocs">Lower allocations from instructions to calls</a> |
| 1358 | </div> |
| 1359 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1360 | <p> |
| 1361 | Turn <tt>malloc</tt> and <tt>free</tt> instructions into <tt>@malloc</tt> and |
| 1362 | <tt>@free</tt> calls. |
| 1363 | </p> |
| 1364 | |
| 1365 | <p> |
| 1366 | This is a target-dependent tranformation because it depends on the size of |
| 1367 | data types and alignment constraints. |
| 1368 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1369 | </div> |
| 1370 | |
| 1371 | <!-------------------------------------------------------------------------- --> |
| 1372 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1373 | <a name="lowerinvoke">Lower invoke and unwind, for unwindless code generators</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1374 | </div> |
| 1375 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1376 | <p> |
| 1377 | This transformation is designed for use by code generators which do not yet |
| 1378 | support stack unwinding. This pass supports two models of exception handling |
| 1379 | lowering, the 'cheap' support and the 'expensive' support. |
| 1380 | </p> |
| 1381 | |
| 1382 | <p> |
| 1383 | 'Cheap' exception handling support gives the program the ability to execute |
| 1384 | any program which does not "throw an exception", by turning 'invoke' |
| 1385 | instructions into calls and by turning 'unwind' instructions into calls to |
| 1386 | abort(). If the program does dynamically use the unwind instruction, the |
| 1387 | program will print a message then abort. |
| 1388 | </p> |
| 1389 | |
| 1390 | <p> |
| 1391 | 'Expensive' exception handling support gives the full exception handling |
| 1392 | support to the program at the cost of making the 'invoke' instruction |
| 1393 | really expensive. It basically inserts setjmp/longjmp calls to emulate the |
| 1394 | exception handling as necessary. |
| 1395 | </p> |
| 1396 | |
| 1397 | <p> |
| 1398 | Because the 'expensive' support slows down programs a lot, and EH is only |
| 1399 | used for a subset of the programs, it must be specifically enabled by the |
| 1400 | <tt>-enable-correct-eh-support</tt> option. |
| 1401 | </p> |
| 1402 | |
| 1403 | <p> |
| 1404 | Note that after this pass runs the CFG is not entirely accurate (exceptional |
| 1405 | control flow edges are not correct anymore) so only very simple things should |
| 1406 | be done after the lowerinvoke pass has run (like generation of native code). |
| 1407 | This should not be used as a general purpose "my LLVM-to-LLVM pass doesn't |
| 1408 | support the invoke instruction yet" lowering pass. |
| 1409 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1410 | </div> |
| 1411 | |
| 1412 | <!-------------------------------------------------------------------------- --> |
| 1413 | <div class="doc_subsection"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1414 | <a name="lowersetjmp">Lower Set Jump</a> |
| 1415 | </div> |
| 1416 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1417 | <p> |
| 1418 | Lowers <tt>setjmp</tt> and <tt>longjmp</tt> to use the LLVM invoke and unwind |
| 1419 | instructions as necessary. |
| 1420 | </p> |
| 1421 | |
| 1422 | <p> |
| 1423 | Lowering of <tt>longjmp</tt> is fairly trivial. We replace the call with a |
| 1424 | call to the LLVM library function <tt>__llvm_sjljeh_throw_longjmp()</tt>. |
| 1425 | This unwinds the stack for us calling all of the destructors for |
| 1426 | objects allocated on the stack. |
| 1427 | </p> |
| 1428 | |
| 1429 | <p> |
| 1430 | At a <tt>setjmp</tt> call, the basic block is split and the <tt>setjmp</tt> |
| 1431 | removed. The calls in a function that have a <tt>setjmp</tt> are converted to |
| 1432 | invoke where the except part checks to see if it's a <tt>longjmp</tt> |
| 1433 | exception and, if so, if it's handled in the function. If it is, then it gets |
| 1434 | the value returned by the <tt>longjmp</tt> and goes to where the basic block |
| 1435 | was split. <tt>invoke</tt> instructions are handled in a similar fashion with |
| 1436 | the original except block being executed if it isn't a <tt>longjmp</tt> |
| 1437 | except that is handled by that function. |
| 1438 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1439 | </div> |
| 1440 | |
| 1441 | <!-------------------------------------------------------------------------- --> |
| 1442 | <div class="doc_subsection"> |
| 1443 | <a name="lowerswitch">Lower SwitchInst's to branches</a> |
| 1444 | </div> |
| 1445 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1446 | <p> |
| 1447 | Rewrites <tt>switch</tt> instructions with a sequence of branches, which |
| 1448 | allows targets to get away with not implementing the switch instruction until |
| 1449 | it is convenient. |
| 1450 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1451 | </div> |
| 1452 | |
| 1453 | <!-------------------------------------------------------------------------- --> |
| 1454 | <div class="doc_subsection"> |
| 1455 | <a name="mem2reg">Promote Memory to Register</a> |
| 1456 | </div> |
| 1457 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1458 | <p> |
| 1459 | This file promotes memory references to be register references. It promotes |
| 1460 | <tt>alloca</tt> instructions which only have <tt>load</tt>s and |
| 1461 | <tt>store</tt>s as uses. An <tt>alloca</tt> is transformed by using dominator |
| 1462 | frontiers to place <tt>phi</tt> nodes, then traversing the function in |
| 1463 | depth-first order to rewrite <tt>load</tt>s and <tt>store</tt>s as |
| 1464 | appropriate. This is just the standard SSA construction algorithm to construct |
| 1465 | "pruned" SSA form. |
| 1466 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1467 | </div> |
| 1468 | |
| 1469 | <!-------------------------------------------------------------------------- --> |
| 1470 | <div class="doc_subsection"> |
Gordon Henriksen | a8a118b | 2008-05-08 17:46:35 +0000 | [diff] [blame] | 1471 | <a name="memcpyopt">Optimize use of memcpy and friend</a> |
| 1472 | </div> |
| 1473 | <div class="doc_text"> |
| 1474 | <p> |
| 1475 | This pass performs various transformations related to eliminating memcpy |
| 1476 | calls, or transforming sets of stores into memset's. |
| 1477 | </p> |
| 1478 | </div> |
| 1479 | |
| 1480 | <!-------------------------------------------------------------------------- --> |
| 1481 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1482 | <a name="mergereturn">Unify function exit nodes</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1483 | </div> |
| 1484 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1485 | <p> |
| 1486 | Ensure that functions have at most one <tt>ret</tt> instruction in them. |
| 1487 | Additionally, it keeps track of which node is the new exit node of the CFG. |
| 1488 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1489 | </div> |
| 1490 | |
| 1491 | <!-------------------------------------------------------------------------- --> |
| 1492 | <div class="doc_subsection"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1493 | <a name="prune-eh">Remove unused exception handling info</a> |
| 1494 | </div> |
| 1495 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1496 | <p> |
| 1497 | This file implements a simple interprocedural pass which walks the call-graph, |
| 1498 | turning <tt>invoke</tt> instructions into <tt>call</tt> instructions if and |
| 1499 | only if the callee cannot throw an exception. It implements this as a |
| 1500 | bottom-up traversal of the call-graph. |
| 1501 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1502 | </div> |
| 1503 | |
| 1504 | <!-------------------------------------------------------------------------- --> |
| 1505 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1506 | <a name="reassociate">Reassociate expressions</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1507 | </div> |
| 1508 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1509 | <p> |
| 1510 | This pass reassociates commutative expressions in an order that is designed |
| 1511 | to promote better constant propagation, GCSE, LICM, PRE, etc. |
| 1512 | </p> |
| 1513 | |
| 1514 | <p> |
| 1515 | For example: 4 + (<var>x</var> + 5) ⇒ <var>x</var> + (4 + 5) |
| 1516 | </p> |
| 1517 | |
| 1518 | <p> |
| 1519 | In the implementation of this algorithm, constants are assigned rank = 0, |
| 1520 | function arguments are rank = 1, and other values are assigned ranks |
| 1521 | corresponding to the reverse post order traversal of current function |
| 1522 | (starting at 2), which effectively gives values in deep loops higher rank |
| 1523 | than values not in loops. |
| 1524 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1525 | </div> |
| 1526 | |
| 1527 | <!-------------------------------------------------------------------------- --> |
| 1528 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1529 | <a name="reg2mem">Demote all values to stack slots</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1530 | </div> |
| 1531 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1532 | <p> |
| 1533 | This file demotes all registers to memory references. It is intented to be |
| 1534 | the inverse of <a href="#mem2reg"><tt>-mem2reg</tt></a>. By converting to |
Benjamin Kramer | 8040cd3 | 2009-10-12 14:46:08 +0000 | [diff] [blame] | 1535 | <tt>load</tt> instructions, the only values live across basic blocks are |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1536 | <tt>alloca</tt> instructions and <tt>load</tt> instructions before |
| 1537 | <tt>phi</tt> nodes. It is intended that this should make CFG hacking much |
| 1538 | easier. To make later hacking easier, the entry block is split into two, such |
| 1539 | that all introduced <tt>alloca</tt> instructions (and nothing else) are in the |
| 1540 | entry block. |
| 1541 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1542 | </div> |
| 1543 | |
| 1544 | <!-------------------------------------------------------------------------- --> |
| 1545 | <div class="doc_subsection"> |
| 1546 | <a name="scalarrepl">Scalar Replacement of Aggregates</a> |
| 1547 | </div> |
| 1548 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1549 | <p> |
| 1550 | The well-known scalar replacement of aggregates transformation. This |
| 1551 | transform breaks up <tt>alloca</tt> instructions of aggregate type (structure |
| 1552 | or array) into individual <tt>alloca</tt> instructions for each member if |
| 1553 | possible. Then, if possible, it transforms the individual <tt>alloca</tt> |
| 1554 | instructions into nice clean scalar SSA form. |
| 1555 | </p> |
| 1556 | |
| 1557 | <p> |
| 1558 | This combines a simple scalar replacement of aggregates algorithm with the <a |
| 1559 | href="#mem2reg"><tt>mem2reg</tt></a> algorithm because often interact, |
| 1560 | especially for C++ programs. As such, iterating between <tt>scalarrepl</tt>, |
| 1561 | then <a href="#mem2reg"><tt>mem2reg</tt></a> until we run out of things to |
| 1562 | promote works well. |
| 1563 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1564 | </div> |
| 1565 | |
| 1566 | <!-------------------------------------------------------------------------- --> |
| 1567 | <div class="doc_subsection"> |
| 1568 | <a name="sccp">Sparse Conditional Constant Propagation</a> |
| 1569 | </div> |
| 1570 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1571 | <p> |
| 1572 | Sparse conditional constant propagation and merging, which can be summarized |
| 1573 | as: |
| 1574 | </p> |
| 1575 | |
| 1576 | <ol> |
| 1577 | <li>Assumes values are constant unless proven otherwise</li> |
| 1578 | <li>Assumes BasicBlocks are dead unless proven otherwise</li> |
| 1579 | <li>Proves values to be constant, and replaces them with constants</li> |
| 1580 | <li>Proves conditional branches to be unconditional</li> |
| 1581 | </ol> |
| 1582 | |
| 1583 | <p> |
| 1584 | Note that this pass has a habit of making definitions be dead. It is a good |
| 1585 | idea to to run a DCE pass sometime after running this pass. |
| 1586 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1587 | </div> |
| 1588 | |
| 1589 | <!-------------------------------------------------------------------------- --> |
| 1590 | <div class="doc_subsection"> |
| 1591 | <a name="simplify-libcalls">Simplify well-known library calls</a> |
| 1592 | </div> |
| 1593 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1594 | <p> |
| 1595 | Applies a variety of small optimizations for calls to specific well-known |
| 1596 | function calls (e.g. runtime library functions). For example, a call |
| 1597 | <tt>exit(3)</tt> that occurs within the <tt>main()</tt> function can be |
| 1598 | transformed into simply <tt>return 3</tt>. |
| 1599 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1600 | </div> |
| 1601 | |
| 1602 | <!-------------------------------------------------------------------------- --> |
| 1603 | <div class="doc_subsection"> |
| 1604 | <a name="simplifycfg">Simplify the CFG</a> |
| 1605 | </div> |
| 1606 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1607 | <p> |
| 1608 | Performs dead code elimination and basic block merging. Specifically: |
| 1609 | </p> |
| 1610 | |
| 1611 | <ol> |
| 1612 | <li>Removes basic blocks with no predecessors.</li> |
| 1613 | <li>Merges a basic block into its predecessor if there is only one and the |
| 1614 | predecessor only has one successor.</li> |
| 1615 | <li>Eliminates PHI nodes for basic blocks with a single predecessor.</li> |
| 1616 | <li>Eliminates a basic block that only contains an unconditional |
| 1617 | branch.</li> |
| 1618 | </ol> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1619 | </div> |
| 1620 | |
| 1621 | <!-------------------------------------------------------------------------- --> |
| 1622 | <div class="doc_subsection"> |
| 1623 | <a name="strip">Strip all symbols from a module</a> |
| 1624 | </div> |
| 1625 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1626 | <p> |
| 1627 | Performs code stripping. This transformation can delete: |
| 1628 | </p> |
| 1629 | |
| 1630 | <ol> |
| 1631 | <li>names for virtual registers</li> |
| 1632 | <li>symbols for internal globals and functions</li> |
| 1633 | <li>debug information</li> |
| 1634 | </ol> |
| 1635 | |
| 1636 | <p> |
| 1637 | Note that this transformation makes code much less readable, so it should |
| 1638 | only be used in situations where the <tt>strip</tt> utility would be used, |
| 1639 | such as reducing code size or making it harder to reverse engineer code. |
| 1640 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1641 | </div> |
| 1642 | |
| 1643 | <!-------------------------------------------------------------------------- --> |
| 1644 | <div class="doc_subsection"> |
Gordon Henriksen | a8a118b | 2008-05-08 17:46:35 +0000 | [diff] [blame] | 1645 | <a name="strip-dead-prototypes">Remove unused function declarations</a> |
| 1646 | </div> |
| 1647 | <div class="doc_text"> |
| 1648 | <p> |
| 1649 | This pass loops over all of the functions in the input module, looking for |
| 1650 | dead declarations and removes them. Dead declarations are declarations of |
| 1651 | functions for which no implementation is available (i.e., declarations for |
| 1652 | unused library functions). |
| 1653 | </p> |
| 1654 | </div> |
| 1655 | |
| 1656 | <!-------------------------------------------------------------------------- --> |
| 1657 | <div class="doc_subsection"> |
| 1658 | <a name="sretpromotion">Promote sret arguments</a> |
| 1659 | </div> |
| 1660 | <div class="doc_text"> |
| 1661 | <p> |
| 1662 | This pass finds functions that return a struct (using a pointer to the struct |
| 1663 | as the first argument of the function, marked with the '<tt>sret</tt>' attribute) and |
| 1664 | replaces them with a new function that simply returns each of the elements of |
| 1665 | that struct (using multiple return values). |
| 1666 | </p> |
| 1667 | |
| 1668 | <p> |
| 1669 | This pass works under a number of conditions: |
| 1670 | </p> |
| 1671 | |
| 1672 | <ul> |
| 1673 | <li>The returned struct must not contain other structs</li> |
| 1674 | <li>The returned struct must only be used to load values from</li> |
| 1675 | <li>The placeholder struct passed in is the result of an <tt>alloca</tt></li> |
| 1676 | </ul> |
| 1677 | </div> |
| 1678 | |
| 1679 | <!-------------------------------------------------------------------------- --> |
| 1680 | <div class="doc_subsection"> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1681 | <a name="tailcallelim">Tail Call Elimination</a> |
| 1682 | </div> |
| 1683 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1684 | <p> |
| 1685 | This file transforms calls of the current function (self recursion) followed |
| 1686 | by a return instruction with a branch to the entry of the function, creating |
| 1687 | a loop. This pass also implements the following extensions to the basic |
| 1688 | algorithm: |
| 1689 | </p> |
| 1690 | |
| 1691 | <ul> |
| 1692 | <li>Trivial instructions between the call and return do not prevent the |
| 1693 | transformation from taking place, though currently the analysis cannot |
| 1694 | support moving any really useful instructions (only dead ones). |
| 1695 | <li>This pass transforms functions that are prevented from being tail |
| 1696 | recursive by an associative expression to use an accumulator variable, |
| 1697 | thus compiling the typical naive factorial or <tt>fib</tt> implementation |
| 1698 | into efficient code. |
| 1699 | <li>TRE is performed if the function returns void, if the return |
| 1700 | returns the result returned by the call, or if the function returns a |
| 1701 | run-time constant on all exits from the function. It is possible, though |
| 1702 | unlikely, that the return returns something else (like constant 0), and |
| 1703 | can still be TRE'd. It can be TRE'd if <em>all other</em> return |
| 1704 | instructions in the function return the exact same value. |
| 1705 | <li>If it can prove that callees do not access theier caller stack frame, |
| 1706 | they are marked as eligible for tail call elimination (by the code |
| 1707 | generator). |
| 1708 | </ul> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1709 | </div> |
| 1710 | |
| 1711 | <!-------------------------------------------------------------------------- --> |
| 1712 | <div class="doc_subsection"> |
| 1713 | <a name="tailduplicate">Tail Duplication</a> |
| 1714 | </div> |
| 1715 | <div class="doc_text"> |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 1716 | <p> |
| 1717 | This pass performs a limited form of tail duplication, intended to simplify |
| 1718 | CFGs by removing some unconditional branches. This pass is necessary to |
| 1719 | straighten out loops created by the C front-end, but also is capable of |
| 1720 | making other code nicer. After this pass is run, the CFG simplify pass |
| 1721 | should be run to clean up the mess. |
| 1722 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1723 | </div> |
| 1724 | |
| 1725 | <!-- ======================================================================= --> |
| 1726 | <div class="doc_section"> <a name="transform">Utility Passes</a></div> |
| 1727 | <div class="doc_text"> |
| 1728 | <p>This section describes the LLVM Utility Passes.</p> |
| 1729 | </div> |
| 1730 | |
| 1731 | <!-------------------------------------------------------------------------- --> |
| 1732 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1733 | <a name="deadarghaX0r">Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1734 | </div> |
| 1735 | <div class="doc_text"> |
Gordon Henriksen | 75ff18e | 2007-11-04 18:10:18 +0000 | [diff] [blame] | 1736 | <p> |
| 1737 | Same as dead argument elimination, but deletes arguments to functions which |
| 1738 | are external. This is only for use by <a |
| 1739 | href="Bugpoint.html">bugpoint</a>.</p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1740 | </div> |
| 1741 | |
| 1742 | <!-------------------------------------------------------------------------- --> |
| 1743 | <div class="doc_subsection"> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1744 | <a name="extract-blocks">Extract Basic Blocks From Module (for bugpoint use)</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1745 | </div> |
| 1746 | <div class="doc_text"> |
Gordon Henriksen | 75ff18e | 2007-11-04 18:10:18 +0000 | [diff] [blame] | 1747 | <p> |
| 1748 | This pass is used by bugpoint to extract all blocks from the module into their |
| 1749 | own functions.</p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1750 | </div> |
| 1751 | |
| 1752 | <!-------------------------------------------------------------------------- --> |
| 1753 | <div class="doc_subsection"> |
Gordon Henriksen | 90a5214 | 2007-11-05 02:05:35 +0000 | [diff] [blame] | 1754 | <a name="preverify">Preliminary module verification</a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1755 | </div> |
| 1756 | <div class="doc_text"> |
Gordon Henriksen | 90a5214 | 2007-11-05 02:05:35 +0000 | [diff] [blame] | 1757 | <p> |
| 1758 | Ensures that the module is in the form required by the <a |
| 1759 | href="#verifier">Module Verifier</a> pass. |
| 1760 | </p> |
| 1761 | |
| 1762 | <p> |
| 1763 | Running the verifier runs this pass automatically, so there should be no need |
| 1764 | to use it directly. |
| 1765 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1766 | </div> |
| 1767 | |
| 1768 | <!-------------------------------------------------------------------------- --> |
| 1769 | <div class="doc_subsection"> |
| 1770 | <a name="verify">Module Verifier</a> |
| 1771 | </div> |
| 1772 | <div class="doc_text"> |
Gordon Henriksen | 75ff18e | 2007-11-04 18:10:18 +0000 | [diff] [blame] | 1773 | <p> |
| 1774 | Verifies an LLVM IR code. This is useful to run after an optimization which is |
| 1775 | undergoing testing. Note that <tt>llvm-as</tt> verifies its input before |
| 1776 | emitting bitcode, and also that malformed bitcode is likely to make LLVM |
| 1777 | crash. All language front-ends are therefore encouraged to verify their output |
| 1778 | before performing optimizing transformations. |
| 1779 | </p> |
| 1780 | |
Gordon Henriksen | 23a8ce5 | 2007-11-04 18:14:08 +0000 | [diff] [blame] | 1781 | <ul> |
Gordon Henriksen | 75ff18e | 2007-11-04 18:10:18 +0000 | [diff] [blame] | 1782 | <li>Both of a binary operator's parameters are of the same type.</li> |
| 1783 | <li>Verify that the indices of mem access instructions match other |
| 1784 | operands.</li> |
| 1785 | <li>Verify that arithmetic and other things are only performed on |
| 1786 | first-class types. Verify that shifts and logicals only happen on |
| 1787 | integrals f.e.</li> |
| 1788 | <li>All of the constants in a switch statement are of the correct type.</li> |
| 1789 | <li>The code is in valid SSA form.</li> |
Chris Lattner | 46b3abc | 2009-10-28 04:47:06 +0000 | [diff] [blame] | 1790 | <li>It is illegal to put a label into any other type (like a structure) or |
| 1791 | to return one.</li> |
Nick Lewycky | 0c78ac1 | 2008-03-28 06:46:51 +0000 | [diff] [blame] | 1792 | <li>Only phi nodes can be self referential: <tt>%x = add i32 %x, %x</tt> is |
Gordon Henriksen | 873390e | 2007-11-04 18:17:58 +0000 | [diff] [blame] | 1793 | invalid.</li> |
Gordon Henriksen | 75ff18e | 2007-11-04 18:10:18 +0000 | [diff] [blame] | 1794 | <li>PHI nodes must have an entry for each predecessor, with no extras.</li> |
| 1795 | <li>PHI nodes must be the first thing in a basic block, all grouped |
| 1796 | together.</li> |
| 1797 | <li>PHI nodes must have at least one entry.</li> |
| 1798 | <li>All basic blocks should only end with terminator insts, not contain |
| 1799 | them.</li> |
| 1800 | <li>The entry node to a function must not have predecessors.</li> |
| 1801 | <li>All Instructions must be embedded into a basic block.</li> |
| 1802 | <li>Functions cannot take a void-typed parameter.</li> |
| 1803 | <li>Verify that a function's argument list agrees with its declared |
| 1804 | type.</li> |
| 1805 | <li>It is illegal to specify a name for a void value.</li> |
| 1806 | <li>It is illegal to have a internal global value with no initializer.</li> |
| 1807 | <li>It is illegal to have a ret instruction that returns a value that does |
| 1808 | not agree with the function return value type.</li> |
| 1809 | <li>Function call argument types match the function prototype.</li> |
| 1810 | <li>All other things that are tested by asserts spread about the code.</li> |
Gordon Henriksen | 23a8ce5 | 2007-11-04 18:14:08 +0000 | [diff] [blame] | 1811 | </ul> |
Gordon Henriksen | 75ff18e | 2007-11-04 18:10:18 +0000 | [diff] [blame] | 1812 | |
| 1813 | <p> |
| 1814 | Note that this does not provide full security verification (like Java), but |
| 1815 | instead just tries to ensure that code is well-formed. |
| 1816 | </p> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1817 | </div> |
| 1818 | |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1819 | <!-------------------------------------------------------------------------- --> |
| 1820 | <div class="doc_subsection"> |
| 1821 | <a name="view-cfg">View CFG of function</a> |
| 1822 | </div> |
| 1823 | <div class="doc_text"> |
Gordon Henriksen | 75ff18e | 2007-11-04 18:10:18 +0000 | [diff] [blame] | 1824 | <p> |
| 1825 | Displays the control flow graph using the GraphViz tool. |
| 1826 | </p> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1827 | </div> |
| 1828 | |
| 1829 | <!-------------------------------------------------------------------------- --> |
| 1830 | <div class="doc_subsection"> |
| 1831 | <a name="view-cfg-only">View CFG of function (with no function bodies)</a> |
| 1832 | </div> |
| 1833 | <div class="doc_text"> |
Gordon Henriksen | 75ff18e | 2007-11-04 18:10:18 +0000 | [diff] [blame] | 1834 | <p> |
| 1835 | Displays the control flow graph using the GraphViz tool, but omitting function |
| 1836 | bodies. |
| 1837 | </p> |
Gordon Henriksen | 1f5cce0 | 2007-10-25 08:46:12 +0000 | [diff] [blame] | 1838 | </div> |
| 1839 | |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1840 | <!-- *********************************************************************** --> |
| 1841 | |
| 1842 | <hr> |
| 1843 | <address> |
| 1844 | <a href="http://jigsaw.w3.org/css-validator/check/referer"><img |
Misha Brukman | 4440870 | 2008-12-11 17:34:48 +0000 | [diff] [blame] | 1845 | src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1846 | <a href="http://validator.w3.org/check/referer"><img |
Misha Brukman | 4440870 | 2008-12-11 17:34:48 +0000 | [diff] [blame] | 1847 | src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a> |
Reid Spencer | d9aac12 | 2007-03-26 09:32:31 +0000 | [diff] [blame] | 1848 | |
| 1849 | <a href="mailto:rspencer@x10sys.com">Reid Spencer</a><br> |
| 1850 | <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br> |
| 1851 | Last modified: $Date$ |
| 1852 | </address> |
| 1853 | |
| 1854 | </body> |
| 1855 | </html> |