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