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