docs/Passes.html

   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">
   7   <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
   8 </head>
   9 <body>
  10
  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 }
  24 open HELP, "../Release/bin/opt -help|" or die "open: opt -help: $!\n";
  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
  37   -->
  38
  39 <div class="doc_title">LLVM's Analysis and Transform Passes</div>
  40
  41 <ol>
  42   <li><a href="#intro">Introduction</a></li>
  43   <li><a href="#analyses">Analysis Passes</a>
  44   <li><a href="#transforms">Transform Passes</a></li>
  45   <li><a href="#utilities">Utility Passes</a></li>
  46 </ol>
  47
  48 <div class="doc_author">
  49   <p>Written by <a href="mailto:rspencer@x10sys.com">Reid Spencer</a></p>
  50 </div>
  51
  52 <!-- ======================================================================= -->
  53 <div class="doc_section"> <a name="intro">Introduction</a> </div>
  54 <div class="doc_text">
  55   <p>This document serves as a high level summary of the optimization features
  56   that LLVM provides. Optimizations are implemented as Passes that traverse some
  57   portion of a program to either collect information or transform the program.
  58   The table below divides the passes that LLVM provides into three categories.
  59   Analysis passes compute information that other passes can use or for debugging
  60   or program visualization purposes. Transform passes can use (or invalidate)
  61   the analysis passes. Transform passes all mutate the program in some way.
  62   Utility passes provides some utility but don't otherwise fit categorization.
  63   For example passes to extract functions to bitcode or write a module to
  64   bitcode are neither analysis nor transform passes.
  65   <p>The table below provides a quick summary of each pass and links to the more
  66   complete pass description later in the document.</p>
  67 </div>
  68 <div class="doc_text" >
  69 <table>
  70 <tr><th colspan="2"><b>ANALYSIS PASSES</b></th></tr>
  71 <tr><th>Option</th><th>Name</th></tr>
  72 <tr><td><a href="#aa-eval">-aa-eval</a></td><td>Exhaustive Alias Analysis Precision Evaluator</td></tr>
  73 <tr><td><a href="#anders-aa">-anders-aa</a></td><td>Andersen's Interprocedural Alias Analysis</td></tr>
  74 <tr><td><a href="#basicaa">-basicaa</a></td><td>Basic Alias Analysis (default AA impl)</td></tr>
  75 <tr><td><a href="#basiccg">-basiccg</a></td><td>Basic CallGraph Construction</td></tr>
  76 <tr><td><a href="#basicvn">-basicvn</a></td><td>Basic Value Numbering (default GVN impl)</td></tr>
  77 <tr><td><a href="#callgraph">-callgraph</a></td><td>Print a call graph</td></tr>
  78 <tr><td><a href="#callscc">-callscc</a></td><td>Print SCCs of the Call Graph</td></tr>
  79 <tr><td><a href="#cfgscc">-cfgscc</a></td><td>Print SCCs of each function CFG</td></tr>
  80 <tr><td><a href="#codegenprepare">-codegenprepare</a></td><td>Optimize for code generation</td></tr>
  81 <tr><td><a href="#count-aa">-count-aa</a></td><td>Count Alias Analysis Query Responses</td></tr>
  82 <tr><td><a href="#debug-aa">-debug-aa</a></td><td>AA use debugger</td></tr>
  83 <tr><td><a href="#domfrontier">-domfrontier</a></td><td>Dominance Frontier Construction</td></tr>
  84 <tr><td><a href="#domtree">-domtree</a></td><td>Dominator Tree Construction</td></tr>
  85 <tr><td><a href="#externalfnconstants">-externalfnconstants</a></td><td>Print external fn callsites passed constants</td></tr>
  86 <tr><td><a href="#globalsmodref-aa">-globalsmodref-aa</a></td><td>Simple mod/ref analysis for globals</td></tr>
  87 <tr><td><a href="#gvn">-gvn</a></td><td>Global Value Numbering</td></tr>
  88 <tr><td><a href="#instcount">-instcount</a></td><td>Counts the various types of Instructions</td></tr>
  89 <tr><td><a href="#intervals">-intervals</a></td><td>Interval Partition Construction</td></tr>
  90 <tr><td><a href="#load-vn">-load-vn</a></td><td>Load Value Numbering</td></tr>
  91 <tr><td><a href="#loops">-loops</a></td><td>Natural Loop Construction</td></tr>
  92 <tr><td><a href="#memdep">-memdep</a></td><td>Memory Dependence Analysis</td></tr>
  93 <tr><td><a href="#no-aa">-no-aa</a></td><td>No Alias Analysis (always returns 'may' alias)</td></tr>
  94 <tr><td><a href="#no-profile">-no-profile</a></td><td>No Profile Information</td></tr>
  95 <tr><td><a href="#postdomfrontier">-postdomfrontier</a></td><td>Post-Dominance Frontier Construction</td></tr>
  96 <tr><td><a href="#postdomtree">-postdomtree</a></td><td>Post-Dominator Tree Construction</td></tr>
  97 <tr><td><a href="#print">-print</a></td><td>Print function to stderr</td></tr>
  98 <tr><td><a href="#print-alias-sets">-print-alias-sets</a></td><td>Alias Set Printer</td></tr>
  99 <tr><td><a href="#print-callgraph">-print-callgraph</a></td><td>Print Call Graph to 'dot' file</td></tr>
 100 <tr><td><a href="#print-cfg">-print-cfg</a></td><td>Print CFG of function to 'dot' file</td></tr>
 101 <tr><td><a href="#print-cfg-only">-print-cfg-only</a></td><td>Print CFG of function to 'dot' file (with no function bodies)</td></tr>
 102 <tr><td><a href="#printm">-printm</a></td><td>Print module to stderr</td></tr>
 103 <tr><td><a href="#printusedtypes">-printusedtypes</a></td><td>Find Used Types</td></tr>
 104 <tr><td><a href="#profile-loader">-profile-loader</a></td><td>Load profile information from llvmprof.out</td></tr>
 105 <tr><td><a href="#scalar-evolution">-scalar-evolution</a></td><td>Scalar Evolution Analysis</td></tr>
 106 <tr><td><a href="#targetdata">-targetdata</a></td><td>Target Data Layout</td></tr>
 107
 108
 109 <tr><th colspan="2"><b>TRANSFORM PASSES</b></th></tr>
 110 <tr><th>Option</th><th>Name</th></tr>
 111 <tr><td><a href="#adce">-adce</a></td><td>Aggressive Dead Code Elimination</td></tr>
 112 <tr><td><a href="#argpromotion">-argpromotion</a></td><td>Promote 'by reference' arguments to scalars</td></tr>
 113 <tr><td><a href="#block-placement">-block-placement</a></td><td>Profile Guided Basic Block Placement</td></tr>
 114 <tr><td><a href="#break-crit-edges">-break-crit-edges</a></td><td>Break critical edges in CFG</td></tr>
 115 <tr><td><a href="#cee">-cee</a></td><td>Correlated Expression Elimination</td></tr>
 116 <tr><td><a href="#condprop">-condprop</a></td><td>Conditional Propagation</td></tr>
 117 <tr><td><a href="#constmerge">-constmerge</a></td><td>Merge Duplicate Global Constants</td></tr>
 118 <tr><td><a href="#constprop">-constprop</a></td><td>Simple constant propagation</td></tr>
 119 <tr><td><a href="#dce">-dce</a></td><td>Dead Code Elimination</td></tr>
 120 <tr><td><a href="#deadargelim">-deadargelim</a></td><td>Dead Argument Elimination</td></tr>
 121 <tr><td><a href="#deadtypeelim">-deadtypeelim</a></td><td>Dead Type Elimination</td></tr>
 122 <tr><td><a href="#die">-die</a></td><td>Dead Instruction Elimination</td></tr>
 123 <tr><td><a href="#dse">-dse</a></td><td>Dead Store Elimination</td></tr>
 124 <tr><td><a href="#gcse">-gcse</a></td><td>Global Common Subexpression Elimination</td></tr>
 125 <tr><td><a href="#globaldce">-globaldce</a></td><td>Dead Global Elimination</td></tr>
 126 <tr><td><a href="#globalopt">-globalopt</a></td><td>Global Variable Optimizer</td></tr>
 127 <tr><td><a href="#gvnpre">-gvnpre</a></td><td>Global Value Numbering/Partial Redundancy Elimination</td></tr>
 128 <tr><td><a href="#indmemrem">-indmemrem</a></td><td>Indirect Malloc and Free Removal</td></tr>
 129 <tr><td><a href="#indvars">-indvars</a></td><td>Canonicalize Induction Variables</td></tr>
 130 <tr><td><a href="#inline">-inline</a></td><td>Function Integration/Inlining</td></tr>
 131 <tr><td><a href="#insert-block-profiling">-insert-block-profiling</a></td><td>Insert instrumentation for block profiling</td></tr>
 132 <tr><td><a href="#insert-edge-profiling">-insert-edge-profiling</a></td><td>Insert instrumentation for edge profiling</td></tr>
 133 <tr><td><a href="#insert-function-profiling">-insert-function-profiling</a></td><td>Insert instrumentation for function profiling</td></tr>
 134 <tr><td><a href="#insert-null-profiling-rs">-insert-null-profiling-rs</a></td><td>Measure profiling framework overhead</td></tr>
 135 <tr><td><a href="#insert-rs-profiling-framework">-insert-rs-profiling-framework</a></td><td>Insert random sampling instrumentation framework</td></tr>
 136 <tr><td><a href="#instcombine">-instcombine</a></td><td>Combine redundant instructions</td></tr>
 137 <tr><td><a href="#internalize">-internalize</a></td><td>Internalize Global Symbols</td></tr>
 138 <tr><td><a href="#ipconstprop">-ipconstprop</a></td><td>Interprocedural constant propagation</td></tr>
 139 <tr><td><a href="#ipsccp">-ipsccp</a></td><td>Interprocedural Sparse Conditional Constant Propagation</td></tr>
 140 <tr><td><a href="#lcssa">-lcssa</a></td><td>Loop-Closed SSA Form Pass</td></tr>
 141 <tr><td><a href="#licm">-licm</a></td><td>Loop Invariant Code Motion</td></tr>
 142 <tr><td><a href="#loop-extract">-loop-extract</a></td><td>Extract loops into new functions</td></tr>
 143 <tr><td><a href="#loop-extract-single">-loop-extract-single</a></td><td>Extract at most one loop into a new function</td></tr>
 144 <tr><td><a href="#loop-index-split">-loop-index-split</a></td><td>Index Split Loops</td></tr>
 145 <tr><td><a href="#loop-reduce">-loop-reduce</a></td><td>Loop Strength Reduction</td></tr>
 146 <tr><td><a href="#loop-rotate">-loop-rotate</a></td><td>Rotate Loops</td></tr>
 147 <tr><td><a href="#loop-unroll">-loop-unroll</a></td><td>Unroll loops</td></tr>
 148 <tr><td><a href="#loop-unswitch">-loop-unswitch</a></td><td>Unswitch loops</td></tr>
 149 <tr><td><a href="#loopsimplify">-loopsimplify</a></td><td>Canonicalize natural loops</td></tr>
 150 <tr><td><a href="#lower-packed">-lower-packed</a></td><td>lowers packed operations to operations on smaller packed datatypes</td></tr>
 151 <tr><td><a href="#lowerallocs">-lowerallocs</a></td><td>Lower allocations from instructions to calls</td></tr>
 152 <tr><td><a href="#lowergc">-lowergc</a></td><td>Lower GC intrinsics, for GCless code generators</td></tr>
 153 <tr><td><a href="#lowerinvoke">-lowerinvoke</a></td><td>Lower invoke and unwind, for unwindless code generators</td></tr>
 154 <tr><td><a href="#lowerselect">-lowerselect</a></td><td>Lower select instructions to branches</td></tr>
 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>
 158 <tr><td><a href="#mergereturn">-mergereturn</a></td><td>Unify function exit nodes</td></tr>
 159 <tr><td><a href="#predsimplify">-predsimplify</a></td><td>Predicate Simplifier</td></tr>
 160 <tr><td><a href="#prune-eh">-prune-eh</a></td><td>Remove unused exception handling info</td></tr>
 161 <tr><td><a href="#raiseallocs">-raiseallocs</a></td><td>Raise allocations from calls to instructions</td></tr>
 162 <tr><td><a href="#reassociate">-reassociate</a></td><td>Reassociate expressions</td></tr>
 163 <tr><td><a href="#reg2mem">-reg2mem</a></td><td>Demote all values to stack slots</td></tr>
 164 <tr><td><a href="#scalarrepl">-scalarrepl</a></td><td>Scalar Replacement of Aggregates</td></tr>
 165 <tr><td><a href="#sccp">-sccp</a></td><td>Sparse Conditional Constant Propagation</td></tr>
 166 <tr><td><a href="#simplify-libcalls">-simplify-libcalls</a></td><td>Simplify well-known library calls</td></tr>
 167 <tr><td><a href="#simplifycfg">-simplifycfg</a></td><td>Simplify the CFG</td></tr>
 168 <tr><td><a href="#strip">-strip</a></td><td>Strip all symbols from a module</td></tr>
 169 <tr><td><a href="#tailcallelim">-tailcallelim</a></td><td>Tail Call Elimination</td></tr>
 170 <tr><td><a href="#tailduplicate">-tailduplicate</a></td><td>Tail Duplication</td></tr>
 171
 172
 173 <tr><th colspan="2"><b>UTILITY PASSES</b></th></tr>
 174 <tr><th>Option</th><th>Name</th></tr>
 175 <tr><td><a href="#deadarghaX0r">-deadarghaX0r</a></td><td>Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)</td></tr>
 176 <tr><td><a href="#extract-blocks">-extract-blocks</a></td><td>Extract Basic Blocks From Module (for bugpoint use)</td></tr>
 177 <tr><td><a href="#emitbitcode">-emitbitcode</a></td><td>Bitcode Writer</td></tr>
 178 <tr><td><a href="#verify">-verify</a></td><td>Module Verifier</td></tr>
 179 <tr><td><a href="#view-cfg">-view-cfg</a></td><td>View CFG of function</td></tr>
 180 <tr><td><a href="#view-cfg-only">-view-cfg-only</a></td><td>View CFG of function (with no function bodies)</td></tr>
 181 </table>
 182 </div>
 183
 184 <!-- ======================================================================= -->
 185 <div class="doc_section"> <a name="example">Analysis Passes</a></div>
 186 <div class="doc_text">
 187   <p>This section describes the LLVM Analysis Passes.</p>
 188 </div>
 189
 190 <!-------------------------------------------------------------------------- -->
 191 <div class="doc_subsection">
 192   <a name="aa-eval">Exhaustive Alias Analysis Precision Evaluator</a>
 193 </div>
 194 <div class="doc_text">
 195   <p>Yet to be written.</p>
 196 </div>
 197
 198 <!-------------------------------------------------------------------------- -->
 199 <div class="doc_subsection">
 200   <a name="anders-aa">Andersen's Interprocedural Alias Analysis</a>
 201 </div>
 202 <div class="doc_text">
 203   <p>Yet to be written.</p>
 204 </div>
 205
 206 <!-------------------------------------------------------------------------- -->
 207 <div class="doc_subsection">
 208   <a name="basicaa">Basic Alias Analysis (default AA impl)</a>
 209 </div>
 210 <div class="doc_text">
 211   <p>Yet to be written.</p>
 212 </div>
 213
 214 <!-------------------------------------------------------------------------- -->
 215 <div class="doc_subsection">
 216   <a name="basiccg">Basic CallGraph Construction</a>
 217 </div>
 218 <div class="doc_text">
 219   <p>Yet to be written.</p>
 220 </div>
 221
 222 <!-------------------------------------------------------------------------- -->
 223 <div class="doc_subsection">
 224   <a name="basicvn">Basic Value Numbering (default GVN impl)</a>
 225 </div>
 226 <div class="doc_text">
 227   <p>Yet to be written.</p>
 228 </div>
 229
 230 <!-------------------------------------------------------------------------- -->
 231 <div class="doc_subsection">
 232   <a name="callgraph">Print a call graph</a>
 233 </div>
 234 <div class="doc_text">
 235   <p>Yet to be written.</p>
 236 </div>
 237
 238 <!-------------------------------------------------------------------------- -->
 239 <div class="doc_subsection">
 240   <a name="callscc">Print SCCs of the Call Graph</a>
 241 </div>
 242 <div class="doc_text">
 243   <p>Yet to be written.</p>
 244 </div>
 245
 246 <!-------------------------------------------------------------------------- -->
 247 <div class="doc_subsection">
 248   <a name="cfgscc">Print SCCs of each function CFG</a>
 249 </div>
 250 <div class="doc_text">
 251   <p>Yet to be written.</p>
 252 </div>
 253
 254 <!-------------------------------------------------------------------------- -->
 255 <div class="doc_subsection">
 256   <a name="codegenprepare">Optimize for code generation</a>
 257 </div>
 258 <div class="doc_text">
 259   <p>Yet to be written.</p>
 260 </div>
 261
 262 <!-------------------------------------------------------------------------- -->
 263 <div class="doc_subsection">
 264   <a name="count-aa">Count Alias Analysis Query Responses</a>
 265 </div>
 266 <div class="doc_text">
 267   <p>Yet to be written.</p>
 268 </div>
 269
 270 <!-------------------------------------------------------------------------- -->
 271 <div class="doc_subsection">
 272   <a name="debug-aa">AA use debugger</a>
 273 </div>
 274 <div class="doc_text">
 275   <p>Yet to be written.</p>
 276 </div>
 277
 278 <!-------------------------------------------------------------------------- -->
 279 <div class="doc_subsection">
 280   <a name="domfrontier">Dominance Frontier Construction</a>
 281 </div>
 282 <div class="doc_text">
 283   <p>Yet to be written.</p>
 284 </div>
 285
 286 <!-------------------------------------------------------------------------- -->
 287 <div class="doc_subsection">
 288   <a name="domtree">Dominator Tree Construction</a>
 289 </div>
 290 <div class="doc_text">
 291   <p>Yet to be written.</p>
 292 </div>
 293
 294 <!-------------------------------------------------------------------------- -->
 295 <div class="doc_subsection">
 296   <a name="externalfnconstants">Print external fn callsites passed constants</a>
 297 </div>
 298 <div class="doc_text">
 299   <p>Yet to be written.</p>
 300 </div>
 301
 302 <!-------------------------------------------------------------------------- -->
 303 <div class="doc_subsection">
 304   <a name="globalsmodref-aa">Simple mod/ref analysis for globals</a>
 305 </div>
 306 <div class="doc_text">
 307   <p>Yet to be written.</p>
 308 </div>
 309
 310 <!-------------------------------------------------------------------------- -->
 311 <div class="doc_subsection">
 312   <a name="gvn">Global Value Numbering</a>
 313 </div>
 314 <div class="doc_text">
 315   <p>Yet to be written.</p>
 316 </div>
 317
 318 <!-------------------------------------------------------------------------- -->
 319 <div class="doc_subsection">
 320   <a name="instcount">Counts the various types of Instructions</a>
 321 </div>
 322 <div class="doc_text">
 323   <p>Yet to be written.</p>
 324 </div>
 325
 326 <!-------------------------------------------------------------------------- -->
 327 <div class="doc_subsection">
 328   <a name="intervals">Interval Partition Construction</a>
 329 </div>
 330 <div class="doc_text">
 331   <p>Yet to be written.</p>
 332 </div>
 333
 334 <!-------------------------------------------------------------------------- -->
 335 <div class="doc_subsection">
 336   <a name="load-vn">Load Value Numbering</a>
 337 </div>
 338 <div class="doc_text">
 339   <p>Yet to be written.</p>
 340 </div>
 341
 342 <!-------------------------------------------------------------------------- -->
 343 <div class="doc_subsection">
 344   <a name="loops">Natural Loop Construction</a>
 345 </div>
 346 <div class="doc_text">
 347   <p>Yet to be written.</p>
 348 </div>
 349
 350 <!-------------------------------------------------------------------------- -->
 351 <div class="doc_subsection">
 352   <a name="memdep">Memory Dependence Analysis</a>
 353 </div>
 354 <div class="doc_text">
 355   <p>Yet to be written.</p>
 356 </div>
 357
 358 <!-------------------------------------------------------------------------- -->
 359 <div class="doc_subsection">
 360   <a name="no-aa">No Alias Analysis (always returns 'may' alias)</a>
 361 </div>
 362 <div class="doc_text">
 363   <p>Yet to be written.</p>
 364 </div>
 365
 366 <!-------------------------------------------------------------------------- -->
 367 <div class="doc_subsection">
 368   <a name="no-profile">No Profile Information</a>
 369 </div>
 370 <div class="doc_text">
 371   <p>Yet to be written.</p>
 372 </div>
 373
 374 <!-------------------------------------------------------------------------- -->
 375 <div class="doc_subsection">
 376   <a name="postdomfrontier">Post-Dominance Frontier Construction</a>
 377 </div>
 378 <div class="doc_text">
 379   <p>Yet to be written.</p>
 380 </div>
 381
 382 <!-------------------------------------------------------------------------- -->
 383 <div class="doc_subsection">
 384   <a name="postdomtree">Post-Dominator Tree Construction</a>
 385 </div>
 386 <div class="doc_text">
 387   <p>Yet to be written.</p>
 388 </div>
 389
 390 <!-------------------------------------------------------------------------- -->
 391 <div class="doc_subsection">
 392   <a name="print">Print function to stderr</a>
 393 </div>
 394 <div class="doc_text">
 395   <p>Yet to be written.</p>
 396 </div>
 397
 398 <!-------------------------------------------------------------------------- -->
 399 <div class="doc_subsection">
 400   <a name="print-alias-sets">Alias Set Printer</a>
 401 </div>
 402 <div class="doc_text">
 403   <p>Yet to be written.</p>
 404 </div>
 405
 406 <!-------------------------------------------------------------------------- -->
 407 <div class="doc_subsection">
 408   <a name="print-callgraph">Print Call Graph to 'dot' file</a>
 409 </div>
 410 <div class="doc_text">
 411   <p>Yet to be written.</p>
 412 </div>
 413
 414 <!-------------------------------------------------------------------------- -->
 415 <div class="doc_subsection">
 416   <a name="print-cfg">Print CFG of function to 'dot' file</a>
 417 </div>
 418 <div class="doc_text">
 419   <p>Yet to be written.</p>
 420 </div>
 421
 422 <!-------------------------------------------------------------------------- -->
 423 <div class="doc_subsection">
 424   <a name="print-cfg-only">Print CFG of function to 'dot' file (with no function bodies)</a>
 425 </div>
 426 <div class="doc_text">
 427   <p>Yet to be written.</p>
 428 </div>
 429
 430 <!-------------------------------------------------------------------------- -->
 431 <div class="doc_subsection">
 432   <a name="printm">Print module to stderr</a>
 433 </div>
 434 <div class="doc_text">
 435   <p>Yet to be written.</p>
 436 </div>
 437
 438 <!-------------------------------------------------------------------------- -->
 439 <div class="doc_subsection">
 440   <a name="printusedtypes">Find Used Types</a>
 441 </div>
 442 <div class="doc_text">
 443   <p>Yet to be written.</p>
 444 </div>
 445
 446 <!-------------------------------------------------------------------------- -->
 447 <div class="doc_subsection">
 448   <a name="profile-loader">Load profile information from llvmprof.out</a>
 449 </div>
 450 <div class="doc_text">
 451   <p>Yet to be written.</p>
 452 </div>
 453
 454 <!-------------------------------------------------------------------------- -->
 455 <div class="doc_subsection">
 456   <a name="scalar-evolution">Scalar Evolution Analysis</a>
 457 </div>
 458 <div class="doc_text">
 459   <p>Yet to be written.</p>
 460 </div>
 461
 462 <!-------------------------------------------------------------------------- -->
 463 <div class="doc_subsection">
 464   <a name="targetdata">Target Data Layout</a>
 465 </div>
 466 <div class="doc_text">
 467   <p>Yet to be written.</p>
 468 </div>
 469
 470 <!-- ======================================================================= -->
 471 <div class="doc_section"> <a name="transform">Transform Passes</a></div>
 472 <div class="doc_text">
 473   <p>This section describes the LLVM Transform Passes.</p>
 474 </div>
 475
 476 <!-------------------------------------------------------------------------- -->
 477 <div class="doc_subsection">
 478   <a name="adce">Aggressive Dead Code Elimination</a>
 479 </div>
 480 <div class="doc_text">
 481   <p>ADCE aggressively tries to eliminate code. This pass is similar to
 482   <a href="#dce">DCE</a> but it assumes that values are dead until proven
 483   otherwise. This is similar to <a href="#sccp">SCCP</a>, except applied to
 484   the liveness of values.</p>
 485 </div>
 486
 487 <!-------------------------------------------------------------------------- -->
 488 <div class="doc_subsection">
 489   <a name="argpromotion">Promote 'by reference' arguments to scalars</a>
 490 </div>
 491 <div class="doc_text">
 492   <p>Yet to be written.</p>
 493 </div>
 494
 495 <!-------------------------------------------------------------------------- -->
 496 <div class="doc_subsection">
 497   <a name="block-placement">Profile Guided Basic Block Placement</a>
 498 </div>
 499 <div class="doc_text">
 500   <p>This pass implements a very simple profile guided basic block placement
 501   algorithm.  The idea is to put frequently executed blocks together at the
 502   start of the function, and hopefully increase the number of fall-through
 503   conditional branches.  If there is no profile information for a particular
 504   function, this pass basically orders blocks in depth-first order.</p>
 505   <p>The algorithm implemented here is basically "Algo1" from "Profile Guided
 506   Code Positioning" by Pettis and Hansen, except that it uses basic block
 507   counts instead of edge counts.  This could be improved in many ways, but is
 508   very simple for now.</p>
 509   <p>Basically we "place" the entry block, then loop over all successors in a
 510   DFO, placing the most frequently executed successor until we run out of
 511   blocks.  Did we mention that this was <b>extremely</b> simplistic? This is
 512   also much slower than it could be.  When it becomes important, this pass
 513   will be rewritten to use a better algorithm, and then we can worry about
 514   efficiency.</p>
 515 </div>
 516
 517 <!-------------------------------------------------------------------------- -->
 518 <div class="doc_subsection">
 519   <a name="break-crit-edges">Break critical edges in CFG</a>
 520 </div>
 521 <div class="doc_text">
 522   <p>Yet to be written.</p>
 523 </div>
 524
 525 <!-------------------------------------------------------------------------- -->
 526 <div class="doc_subsection">
 527   <a name="cee">Correlated Expression Elimination</a>
 528 </div>
 529 <div class="doc_text">
 530   <p>Correlated Expression Elimination propagates information from conditional
 531   branches to blocks dominated by destinations of the branch.  It propagates
 532   information from the condition check itself into the body of the branch,
 533   allowing transformations like these for example:</p>
 534
 535 <blockquote><pre>
 536 if (i == 7)
 537   ... 4*i;  // constant propagation
 538
 539 M = i+1; N = j+1;
 540 if (i == j)
 541   X = M-N;  // = M-M == 0;
 542 </pre></blockquote>
 543
 544    <p>This is called Correlated Expression Elimination because we eliminate or
 545    simplify expressions that are correlated with the direction of a branch. In
 546    this way we use static information to give us some information about the
 547    dynamic value of a variable.</p>
 548 </div>
 549
 550 <!-------------------------------------------------------------------------- -->
 551 <div class="doc_subsection">
 552   <a name="condprop">Conditional Propagation</a>
 553 </div>
 554 <div class="doc_text">
 555   <p>This pass propagates information about conditional expressions through the
 556   program, allowing it to eliminate conditional branches in some cases.</p>
 557 </div>
 558
 559 <!-------------------------------------------------------------------------- -->
 560 <div class="doc_subsection">
 561   <a name="constmerge">Merge Duplicate Global Constants</a>
 562 </div>
 563 <div class="doc_text">
 564   <p>Yet to be written.</p>
 565 </div>
 566
 567 <!-------------------------------------------------------------------------- -->
 568 <div class="doc_subsection">
 569   <a name="constprop">Simple constant propagation</a>
 570 </div>
 571 <div class="doc_text">
 572   <p>This file implements constant propagation and merging. It looks for
 573   instructions involving only constant operands and replaces them with a
 574   constant value instead of an instruction. For example:</p>
 575   <blockquote><pre>add i32 1, 2</pre></blockquote>
 576   <p>becomes</p>
 577   <blockquote><pre>i32 3</pre></blockquote>
 578   <p>NOTE: this pass has a habit of making definitions be dead.  It is a good
 579   idea to to run a <a href="#die">DIE</a> (Dead Instruction Elimination) pass
 580   sometime after running this pass.</p>
 581 </div>
 582
 583 <!-------------------------------------------------------------------------- -->
 584 <div class="doc_subsection">
 585   <a name="dce">Dead Code Elimination</a>
 586 </div>
 587 <div class="doc_text">
 588   <p>Yet to be written.</p>
 589 </div>
 590
 591 <!-------------------------------------------------------------------------- -->
 592 <div class="doc_subsection">
 593   <a name="deadargelim">Dead Argument Elimination</a>
 594 </div>
 595 <div class="doc_text">
 596   <p>Yet to be written.</p>
 597 </div>
 598
 599 <!-------------------------------------------------------------------------- -->
 600 <div class="doc_subsection">
 601   <a name="deadtypeelim">Dead Type Elimination</a>
 602 </div>
 603 <div class="doc_text">
 604   <p>Yet to be written.</p>
 605 </div>
 606
 607 <!-------------------------------------------------------------------------- -->
 608 <div class="doc_subsection">
 609   <a name="die">Dead Instruction Elimination</a>
 610 </div>
 611 <div class="doc_text">
 612   <p>Yet to be written.</p>
 613 </div>
 614
 615 <!-------------------------------------------------------------------------- -->
 616 <div class="doc_subsection">
 617   <a name="dse">Dead Store Elimination</a>
 618 </div>
 619 <div class="doc_text">
 620   <p>Yet to be written.</p>
 621 </div>
 622
 623 <!-------------------------------------------------------------------------- -->
 624 <div class="doc_subsection">
 625   <a name="gcse">Global Common Subexpression Elimination</a>
 626 </div>
 627 <div class="doc_text">
 628   <p>Yet to be written.</p>
 629 </div>
 630
 631 <!-------------------------------------------------------------------------- -->
 632 <div class="doc_subsection">
 633   <a name="globaldce">Dead Global Elimination</a>
 634 </div>
 635 <div class="doc_text">
 636   <p>Yet to be written.</p>
 637 </div>
 638
 639 <!-------------------------------------------------------------------------- -->
 640 <div class="doc_subsection">
 641   <a name="globalopt">Global Variable Optimizer</a>
 642 </div>
 643 <div class="doc_text">
 644   <p>Yet to be written.</p>
 645 </div>
 646
 647 <!-------------------------------------------------------------------------- -->
 648 <div class="doc_subsection">
 649   <a name="gvnpre">Global Value Numbering/Partial Redundancy Elimination</a>
 650 </div>
 651 <div class="doc_text">
 652   <p>Yet to be written.</p>
 653 </div>
 654
 655 <!-------------------------------------------------------------------------- -->
 656 <div class="doc_subsection">
 657   <a name="indmemrem">Indirect Malloc and Free Removal</a>
 658 </div>
 659 <div class="doc_text">
 660   <p>Yet to be written.</p>
 661 </div>
 662
 663 <!-------------------------------------------------------------------------- -->
 664 <div class="doc_subsection">
 665   <a name="indvars">Canonicalize Induction Variables</a>
 666 </div>
 667 <div class="doc_text">
 668   <p>Yet to be written.</p>
 669 </div>
 670
 671 <!-------------------------------------------------------------------------- -->
 672 <div class="doc_subsection">
 673   <a name="inline">Function Integration/Inlining</a>
 674 </div>
 675 <div class="doc_text">
 676   <p>Yet to be written.</p>
 677 </div>
 678
 679 <!-------------------------------------------------------------------------- -->
 680 <div class="doc_subsection">
 681   <a name="insert-block-profiling">Insert instrumentation for block profiling</a>
 682 </div>
 683 <div class="doc_text">
 684   <p>Yet to be written.</p>
 685 </div>
 686
 687 <!-------------------------------------------------------------------------- -->
 688 <div class="doc_subsection">
 689   <a name="insert-edge-profiling">Insert instrumentation for edge profiling</a>
 690 </div>
 691 <div class="doc_text">
 692   <p>Yet to be written.</p>
 693 </div>
 694
 695 <!-------------------------------------------------------------------------- -->
 696 <div class="doc_subsection">
 697   <a name="insert-function-profiling">Insert instrumentation for function profiling</a>
 698 </div>
 699 <div class="doc_text">
 700   <p>Yet to be written.</p>
 701 </div>
 702
 703 <!-------------------------------------------------------------------------- -->
 704 <div class="doc_subsection">
 705   <a name="insert-null-profiling-rs">Measure profiling framework overhead</a>
 706 </div>
 707 <div class="doc_text">
 708   <p>Yet to be written.</p>
 709 </div>
 710
 711 <!-------------------------------------------------------------------------- -->
 712 <div class="doc_subsection">
 713   <a name="insert-rs-profiling-framework">Insert random sampling instrumentation framework</a>
 714 </div>
 715 <div class="doc_text">
 716   <p>Yet to be written.</p>
 717 </div>
 718
 719 <!-------------------------------------------------------------------------- -->
 720 <div class="doc_subsection">
 721   <a name="instcombine">Combine redundant instructions</a>
 722 </div>
 723 <div class="doc_text">
 724   <p>Yet to be written.</p>
 725 </div>
 726
 727 <!-------------------------------------------------------------------------- -->
 728 <div class="doc_subsection">
 729   <a name="internalize">Internalize Global Symbols</a>
 730 </div>
 731 <div class="doc_text">
 732   <p>Yet to be written.</p>
 733 </div>
 734
 735 <!-------------------------------------------------------------------------- -->
 736 <div class="doc_subsection">
 737   <a name="ipconstprop">Interprocedural constant propagation</a>
 738 </div>
 739 <div class="doc_text">
 740   <p>Yet to be written.</p>
 741 </div>
 742
 743 <!-------------------------------------------------------------------------- -->
 744 <div class="doc_subsection">
 745   <a name="ipsccp">Interprocedural Sparse Conditional Constant Propagation</a>
 746 </div>
 747 <div class="doc_text">
 748   <p>Yet to be written.</p>
 749 </div>
 750
 751 <!-------------------------------------------------------------------------- -->
 752 <div class="doc_subsection">
 753   <a name="lcssa">Loop-Closed SSA Form Pass</a>
 754 </div>
 755 <div class="doc_text">
 756   <p>Yet to be written.</p>
 757 </div>
 758
 759 <!-------------------------------------------------------------------------- -->
 760 <div class="doc_subsection">
 761   <a name="licm">Loop Invariant Code Motion</a>
 762 </div>
 763 <div class="doc_text">
 764   <p>Yet to be written.</p>
 765 </div>
 766
 767 <!-------------------------------------------------------------------------- -->
 768 <div class="doc_subsection">
 769   <a name="loop-extract">Extract loops into new functions</a>
 770 </div>
 771 <div class="doc_text">
 772   <p>Yet to be written.</p>
 773 </div>
 774
 775 <!-------------------------------------------------------------------------- -->
 776 <div class="doc_subsection">
 777   <a name="loop-extract-single">Extract at most one loop into a new function</a>
 778 </div>
 779 <div class="doc_text">
 780   <p>Yet to be written.</p>
 781 </div>
 782
 783 <!-------------------------------------------------------------------------- -->
 784 <div class="doc_subsection">
 785   <a name="loop-index-split">Index Split Loops</a>
 786 </div>
 787 <div class="doc_text">
 788   <p>Yet to be written.</p>
 789 </div>
 790
 791 <!-------------------------------------------------------------------------- -->
 792 <div class="doc_subsection">
 793   <a name="loop-reduce">Loop Strength Reduction</a>
 794 </div>
 795 <div class="doc_text">
 796   <p>Yet to be written.</p>
 797 </div>
 798
 799 <!-------------------------------------------------------------------------- -->
 800 <div class="doc_subsection">
 801   <a name="loop-rotate">Rotate Loops</a>
 802 </div>
 803 <div class="doc_text">
 804   <p>Yet to be written.</p>
 805 </div>
 806
 807 <!-------------------------------------------------------------------------- -->
 808 <div class="doc_subsection">
 809   <a name="loop-unroll">Unroll loops</a>
 810 </div>
 811 <div class="doc_text">
 812   <p>Yet to be written.</p>
 813 </div>
 814
 815 <!-------------------------------------------------------------------------- -->
 816 <div class="doc_subsection">
 817   <a name="loop-unswitch">Unswitch loops</a>
 818 </div>
 819 <div class="doc_text">
 820   <p>Yet to be written.</p>
 821 </div>
 822
 823 <!-------------------------------------------------------------------------- -->
 824 <div class="doc_subsection">
 825   <a name="loopsimplify">Canonicalize natural loops</a>
 826 </div>
 827 <div class="doc_text">
 828   <p>Yet to be written.</p>
 829 </div>
 830
 831 <!-------------------------------------------------------------------------- -->
 832 <div class="doc_subsection">
 833   <a name="lower-packed">lowers packed operations to operations on smaller packed datatypes</a>
 834 </div>
 835 <div class="doc_text">
 836   <p>Yet to be written.</p>
 837 </div>
 838
 839 <!-------------------------------------------------------------------------- -->
 840 <div class="doc_subsection">
 841   <a name="lowerallocs">Lower allocations from instructions to calls</a>
 842 </div>
 843 <div class="doc_text">
 844   <p>Yet to be written.</p>
 845 </div>
 846
 847 <!-------------------------------------------------------------------------- -->
 848 <div class="doc_subsection">
 849   <a name="lowergc">Lower GC intrinsics, for GCless code generators</a>
 850 </div>
 851 <div class="doc_text">
 852   <p>Yet to be written.</p>
 853 </div>
 854
 855 <!-------------------------------------------------------------------------- -->
 856 <div class="doc_subsection">
 857   <a name="lowerinvoke">Lower invoke and unwind, for unwindless code generators</a>
 858 </div>
 859 <div class="doc_text">
 860   <p>Yet to be written.</p>
 861 </div>
 862
 863 <!-------------------------------------------------------------------------- -->
 864 <div class="doc_subsection">
 865   <a name="lowerselect">Lower select instructions to branches</a>
 866 </div>
 867 <div class="doc_text">
 868   <p>Yet to be written.</p>
 869 </div>
 870
 871 <!-------------------------------------------------------------------------- -->
 872 <div class="doc_subsection">
 873   <a name="lowersetjmp">Lower Set Jump</a>
 874 </div>
 875 <div class="doc_text">
 876   <p>Yet to be written.</p>
 877 </div>
 878
 879 <!-------------------------------------------------------------------------- -->
 880 <div class="doc_subsection">
 881   <a name="lowerswitch">Lower SwitchInst's to branches</a>
 882 </div>
 883 <div class="doc_text">
 884   <p>Yet to be written.</p>
 885 </div>
 886
 887 <!-------------------------------------------------------------------------- -->
 888 <div class="doc_subsection">
 889   <a name="mem2reg">Promote Memory to Register</a>
 890 </div>
 891 <div class="doc_text">
 892   <p>Yet to be written.</p>
 893 </div>
 894
 895 <!-------------------------------------------------------------------------- -->
 896 <div class="doc_subsection">
 897   <a name="mergereturn">Unify function exit nodes</a>
 898 </div>
 899 <div class="doc_text">
 900   <p>Yet to be written.</p>
 901 </div>
 902
 903 <!-------------------------------------------------------------------------- -->
 904 <div class="doc_subsection">
 905   <a name="predsimplify">Predicate Simplifier</a>
 906 </div>
 907 <div class="doc_text">
 908   <p>Yet to be written.</p>
 909 </div>
 910
 911 <!-------------------------------------------------------------------------- -->
 912 <div class="doc_subsection">
 913   <a name="prune-eh">Remove unused exception handling info</a>
 914 </div>
 915 <div class="doc_text">
 916   <p>Yet to be written.</p>
 917 </div>
 918
 919 <!-------------------------------------------------------------------------- -->
 920 <div class="doc_subsection">
 921   <a name="raiseallocs">Raise allocations from calls to instructions</a>
 922 </div>
 923 <div class="doc_text">
 924   <p>Yet to be written.</p>
 925 </div>
 926
 927 <!-------------------------------------------------------------------------- -->
 928 <div class="doc_subsection">
 929   <a name="reassociate">Reassociate expressions</a>
 930 </div>
 931 <div class="doc_text">
 932   <p>Yet to be written.</p>
 933 </div>
 934
 935 <!-------------------------------------------------------------------------- -->
 936 <div class="doc_subsection">
 937   <a name="reg2mem">Demote all values to stack slots</a>
 938 </div>
 939 <div class="doc_text">
 940   <p>Yet to be written.</p>
 941 </div>
 942
 943 <!-------------------------------------------------------------------------- -->
 944 <div class="doc_subsection">
 945   <a name="scalarrepl">Scalar Replacement of Aggregates</a>
 946 </div>
 947 <div class="doc_text">
 948   <p>Yet to be written.</p>
 949 </div>
 950
 951 <!-------------------------------------------------------------------------- -->
 952 <div class="doc_subsection">
 953   <a name="sccp">Sparse Conditional Constant Propagation</a>
 954 </div>
 955 <div class="doc_text">
 956   <p>Yet to be written.</p>
 957 </div>
 958
 959 <!-------------------------------------------------------------------------- -->
 960 <div class="doc_subsection">
 961   <a name="simplify-libcalls">Simplify well-known library calls</a>
 962 </div>
 963 <div class="doc_text">
 964   <p>Yet to be written.</p>
 965 </div>
 966
 967 <!-------------------------------------------------------------------------- -->
 968 <div class="doc_subsection">
 969   <a name="simplifycfg">Simplify the CFG</a>
 970 </div>
 971 <div class="doc_text">
 972   <p>Yet to be written.</p>
 973 </div>
 974
 975 <!-------------------------------------------------------------------------- -->
 976 <div class="doc_subsection">
 977   <a name="strip">Strip all symbols from a module</a>
 978 </div>
 979 <div class="doc_text">
 980   <p>Yet to be written.</p>
 981 </div>
 982
 983 <!-------------------------------------------------------------------------- -->
 984 <div class="doc_subsection">
 985   <a name="tailcallelim">Tail Call Elimination</a>
 986 </div>
 987 <div class="doc_text">
 988   <p>Yet to be written.</p>
 989 </div>
 990
 991 <!-------------------------------------------------------------------------- -->
 992 <div class="doc_subsection">
 993   <a name="tailduplicate">Tail Duplication</a>
 994 </div>
 995 <div class="doc_text">
 996   <p>Yet to be written.</p>
 997 </div>
 998
 999 <!-- ======================================================================= -->
1000 <div class="doc_section"> <a name="transform">Utility Passes</a></div>
1001 <div class="doc_text">
1002   <p>This section describes the LLVM Utility Passes.</p>
1003 </div>
1004
1005 <!-------------------------------------------------------------------------- -->
1006 <div class="doc_subsection">
1007   <a name="deadarghaX0r">Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)</a>
1008 </div>
1009 <div class="doc_text">
1010   <p>Yet to be written.</p>
1011 </div>
1012
1013 <!-------------------------------------------------------------------------- -->
1014 <div class="doc_subsection">
1015   <a name="extract-blocks">Extract Basic Blocks From Module (for bugpoint use)</a>
1016 </div>
1017 <div class="doc_text">
1018   <p>Yet to be written.</p>
1019 </div>
1020
1021 <!-------------------------------------------------------------------------- -->
1022 <div class="doc_subsection">
1023   <a name="emitbitcode">Bitcode Writer</a>
1024 </div>
1025 <div class="doc_text">
1026   <p>Yet to be written.</p>
1027 </div>
1028
1029 <!-------------------------------------------------------------------------- -->
1030 <div class="doc_subsection">
1031   <a name="verify">Module Verifier</a>
1032 </div>
1033 <div class="doc_text">
1034   <p>Yet to be written.</p>
1035 </div>
1036
1037 <!-------------------------------------------------------------------------- -->
1038 <div class="doc_subsection">
1039   <a name="view-cfg">View CFG of function</a>
1040 </div>
1041 <div class="doc_text">
1042   <p>Yet to be written.</p>
1043 </div>
1044
1045 <!-------------------------------------------------------------------------- -->
1046 <div class="doc_subsection">
1047   <a name="view-cfg-only">View CFG of function (with no function bodies)</a>
1048 </div>
1049 <div class="doc_text">
1050   <p>Yet to be written.</p>
1051 </div>
1052
1053 <!-- *********************************************************************** -->
1054
1055 <hr>
1056 <address>
1057   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1058   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1059   <a href="http://validator.w3.org/check/referer"><img
1060   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1061
1062   <a href="mailto:rspencer@x10sys.com">Reid Spencer</a><br>
1063   <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
1064   Last modified: $Date$
1065 </address>
1066
1067 </body>
1068 </html>