docs/WritingAnLLVMPass.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   <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
   6   <title>Writing an LLVM Pass</title>
   7   <link rel="stylesheet" href="llvm.css" type="text/css">
   8 </head>
   9 <body>
  10
  11 <div class="doc_title">
  12   Writing an LLVM Pass
  13 </div>
  14
  15 <ol>
  16   <li><a href="#introduction">Introduction - What is a pass?</a></li>
  17   <li><a href="#quickstart">Quick Start - Writing hello world</a>
  18     <ul>
  19     <li><a href="#makefile">Setting up the build environment</a></li>
  20     <li><a href="#basiccode">Basic code required</a></li>
  21     <li><a href="#running">Running a pass with <tt>opt</tt></a></li>
  22     </ul></li>
  23   <li><a href="#passtype">Pass classes and requirements</a>
  24      <ul>
  25      <li><a href="#ImmutablePass">The <tt>ImmutablePass</tt> class</a></li>
  26      <li><a href="#ModulePass">The <tt>ModulePass</tt> class</a>
  27         <ul>
  28         <li><a href="#runOnModule">The <tt>runOnModule</tt> method</a></li>
  29         </ul></li>
  30      <li><a href="#CallGraphSCCPass">The <tt>CallGraphSCCPass</tt> class</a>
  31         <ul>
  32         <li><a href="#doInitialization_scc">The <tt>doInitialization(CallGraph
  33                                            &amp;)</tt> method</a></li>
  34         <li><a href="#runOnSCC">The <tt>runOnSCC</tt> method</a></li>
  35         <li><a href="#doFinalization_scc">The <tt>doFinalization(CallGraph
  36                                            &amp;)</tt> method</a></li>
  37         </ul></li>
  38      <li><a href="#FunctionPass">The <tt>FunctionPass</tt> class</a>
  39         <ul>
  40         <li><a href="#doInitialization_mod">The <tt>doInitialization(Module
  41                                             &amp;)</tt> method</a></li>
  42         <li><a href="#runOnFunction">The <tt>runOnFunction</tt> method</a></li>
  43         <li><a href="#doFinalization_mod">The <tt>doFinalization(Module
  44                                             &amp;)</tt> method</a></li>
  45         </ul></li>
  46      <li><a href="#LoopPass">The <tt>LoopPass</tt> class</a>
  47         <ul>
  48         <li><a href="#doInitialization_loop">The <tt>doInitialization(Loop *,
  49                                             LPPassManager &amp;)</tt> method</a></li>
  50         <li><a href="#runOnLoop">The <tt>runOnLoop</tt> method</a></li>
  51         <li><a href="#doFinalization_loop">The <tt>doFinalization()
  52                                             </tt> method</a></li>
  53         </ul></li>
  54      <li><a href="#RegionPass">The <tt>RegionPass</tt> class</a>
  55         <ul>
  56         <li><a href="#doInitialization_region">The <tt>doInitialization(Region *,
  57                                             RGPassManager &amp;)</tt> method</a></li>
  58         <li><a href="#runOnRegion">The <tt>runOnRegion</tt> method</a></li>
  59         <li><a href="#doFinalization_region">The <tt>doFinalization()
  60                                             </tt> method</a></li>
  61         </ul></li>
  62      <li><a href="#BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
  63         <ul>
  64         <li><a href="#doInitialization_fn">The <tt>doInitialization(Function
  65                                              &amp;)</tt> method</a></li>
  66         <li><a href="#runOnBasicBlock">The <tt>runOnBasicBlock</tt>
  67                                        method</a></li>
  68         <li><a href="#doFinalization_fn">The <tt>doFinalization(Function
  69                                          &amp;)</tt> method</a></li>
  70         </ul></li>
  71      <li><a href="#MachineFunctionPass">The <tt>MachineFunctionPass</tt>
  72                                         class</a>
  73         <ul>
  74         <li><a href="#runOnMachineFunction">The
  75             <tt>runOnMachineFunction(MachineFunction &amp;)</tt> method</a></li>
  76         </ul></li>
  77      </ul>
  78   <li><a href="#registration">Pass Registration</a>
  79      <ul>
  80      <li><a href="#print">The <tt>print</tt> method</a></li>
  81      </ul></li>
  82   <li><a href="#interaction">Specifying interactions between passes</a>
  83      <ul>
  84      <li><a href="#getAnalysisUsage">The <tt>getAnalysisUsage</tt>
  85                                      method</a></li>
  86      <li><a href="#AU::addRequired">The <tt>AnalysisUsage::addRequired&lt;&gt;</tt> and <tt>AnalysisUsage::addRequiredTransitive&lt;&gt;</tt> methods</a></li>
  87      <li><a href="#AU::addPreserved">The <tt>AnalysisUsage::addPreserved&lt;&gt;</tt> method</a></li>
  88      <li><a href="#AU::examples">Example implementations of <tt>getAnalysisUsage</tt></a></li>
  89      <li><a href="#getAnalysis">The <tt>getAnalysis&lt;&gt;</tt> and
  90 <tt>getAnalysisIfAvailable&lt;&gt;</tt> methods</a></li>
  91      </ul></li>
  92   <li><a href="#analysisgroup">Implementing Analysis Groups</a>
  93      <ul>
  94      <li><a href="#agconcepts">Analysis Group Concepts</a></li>
  95      <li><a href="#registerag">Using <tt>RegisterAnalysisGroup</tt></a></li>
  96      </ul></li>
  97   <li><a href="#passStatistics">Pass Statistics</a>
  98   <li><a href="#passmanager">What PassManager does</a>
  99     <ul>
 100     <li><a href="#releaseMemory">The <tt>releaseMemory</tt> method</a></li>
 101     </ul></li>
 102   <li><a href="#registering">Registering dynamically loaded passes</a>
 103     <ul>
 104       <li><a href="#registering_existing">Using existing registries</a></li>
 105       <li><a href="#registering_new">Creating new registries</a></li>
 106     </ul></li>
 107   <li><a href="#debughints">Using GDB with dynamically loaded passes</a>
 108     <ul>
 109     <li><a href="#breakpoint">Setting a breakpoint in your pass</a></li>
 110     <li><a href="#debugmisc">Miscellaneous Problems</a></li>
 111     </ul></li>
 112   <li><a href="#future">Future extensions planned</a>
 113     <ul>
 114     <li><a href="#SMP">Multithreaded LLVM</a></li>
 115     </ul></li>
 116 </ol>
 117
 118 <div class="doc_author">
 119   <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a> and
 120   <a href="mailto:jlaskey@mac.com">Jim Laskey</a></p>
 121 </div>
 122
 123 <!-- *********************************************************************** -->
 124 <div class="doc_section">
 125   <a name="introduction">Introduction - What is a pass?</a>
 126 </div>
 127 <!-- *********************************************************************** -->
 128
 129 <div class="doc_text">
 130
 131 <p>The LLVM Pass Framework is an important part of the LLVM system, because LLVM
 132 passes are where most of the interesting parts of the compiler exist.  Passes
 133 perform the transformations and optimizations that make up the compiler, they
 134 build the analysis results that are used by these transformations, and they are,
 135 above all, a structuring technique for compiler code.</p>
 136
 137 <p>All LLVM passes are subclasses of the <tt><a
 138 href="http://llvm.org/doxygen/classllvm_1_1Pass.html">Pass</a></tt>
 139 class, which implement functionality by overriding virtual methods inherited
 140 from <tt>Pass</tt>.  Depending on how your pass works, you should inherit from
 141 the <tt><a href="#ModulePass">ModulePass</a></tt>, <tt><a
 142 href="#CallGraphSCCPass">CallGraphSCCPass</a></tt>, <tt><a
 143 href="#FunctionPass">FunctionPass</a></tt>, or <tt><a
 144 href="#LoopPass">LoopPass</a></tt>, or <tt><a
 145 href="#RegionPass">RegionPass</a></tt>, or <tt><a
 146 href="#BasicBlockPass">BasicBlockPass</a></tt> classes, which gives the system
 147 more information about what your pass does, and how it can be combined with
 148 other passes.  One of the main features of the LLVM Pass Framework is that it
 149 schedules passes to run in an efficient way based on the constraints that your
 150 pass meets (which are indicated by which class they derive from).</p>
 151
 152 <p>We start by showing you how to construct a pass, everything from setting up
 153 the code, to compiling, loading, and executing it.  After the basics are down,
 154 more advanced features are discussed.</p>
 155
 156 </div>
 157
 158 <!-- *********************************************************************** -->
 159 <div class="doc_section">
 160   <a name="quickstart">Quick Start - Writing hello world</a>
 161 </div>
 162 <!-- *********************************************************************** -->
 163
 164 <div class="doc_text">
 165
 166 <p>Here we describe how to write the "hello world" of passes.  The "Hello" pass
 167 is designed to simply print out the name of non-external functions that exist in
 168 the program being compiled.  It does not modify the program at all, it just
 169 inspects it.  The source code and files for this pass are available in the LLVM
 170 source tree in the <tt>lib/Transforms/Hello</tt> directory.</p>
 171
 172 </div>
 173
 174 <!-- ======================================================================= -->
 175 <div class="doc_subsection">
 176   <a name="makefile">Setting up the build environment</a>
 177 </div>
 178
 179 <div class="doc_text">
 180
 181   <p>First, you need to create a new directory somewhere in the LLVM source
 182   base.  For this example, we'll assume that you made
 183   <tt>lib/Transforms/Hello</tt>.  Next, you must set up a build script
 184   (Makefile) that will compile the source code for the new pass.  To do this,
 185   copy the following into <tt>Makefile</tt>:</p>
 186   <hr/>
 187
 188 <div class="doc_code"><pre>
 189 # Makefile for hello pass
 190
 191 # Path to top level of LLVM hierarchy
 192 LEVEL = ../../..
 193
 194 # Name of the library to build
 195 LIBRARYNAME = Hello
 196
 197 # Make the shared library become a loadable module so the tools can
 198 # dlopen/dlsym on the resulting library.
 199 LOADABLE_MODULE = 1
 200
 201 # Include the makefile implementation stuff
 202 include $(LEVEL)/Makefile.common
 203 </pre></div>
 204
 205 <p>This makefile specifies that all of the <tt>.cpp</tt> files in the current
 206 directory are to be compiled and linked together into a
 207 <tt>Debug+Asserts/lib/Hello.so</tt> shared object that can be dynamically loaded by
 208 the <tt>opt</tt> or <tt>bugpoint</tt> tools via their <tt>-load</tt> options.
 209 If your operating system uses a suffix other than .so (such as windows or
 210 Mac OS/X), the appropriate extension will be used.</p>
 211
 212 <p>Now that we have the build scripts set up, we just need to write the code for
 213 the pass itself.</p>
 214
 215 </div>
 216
 217 <!-- ======================================================================= -->
 218 <div class="doc_subsection">
 219   <a name="basiccode">Basic code required</a>
 220 </div>
 221
 222 <div class="doc_text">
 223
 224 <p>Now that we have a way to compile our new pass, we just have to write it.
 225 Start out with:</p>
 226
 227 <div class="doc_code"><pre>
 228 <b>#include</b> "<a href="http://llvm.org/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
 229 <b>#include</b> "<a href="http://llvm.org/doxygen/Function_8h-source.html">llvm/Function.h</a>"
 230 <b>#include</b> "<a href="http://llvm.org/doxygen/raw__ostream_8h.html">llvm/Support/raw_ostream.h</a>"
 231 </pre></div>
 232
 233 <p>Which are needed because we are writing a <tt><a
 234 href="http://llvm.org/doxygen/classllvm_1_1Pass.html">Pass</a></tt>,
 235 we are operating on <tt><a
 236 href="http://llvm.org/doxygen/classllvm_1_1Function.html">Function</a></tt>'s,
 237 and we will be doing some printing.</p>
 238
 239 <p>Next we have:</p>
 240 <div class="doc_code"><pre>
 241 <b>using namespace llvm;</b>
 242 </pre></div>
 243 <p>... which is required because the functions from the include files
 244 live in the llvm namespace.
 245 </p>
 246
 247 <p>Next we have:</p>
 248
 249 <div class="doc_code"><pre>
 250 <b>namespace</b> {
 251 </pre></div>
 252
 253 <p>... which starts out an anonymous namespace.  Anonymous namespaces are to C++
 254 what the "<tt>static</tt>" keyword is to C (at global scope).  It makes the
 255 things declared inside of the anonymous namespace only visible to the current
 256 file.  If you're not familiar with them, consult a decent C++ book for more
 257 information.</p>
 258
 259 <p>Next, we declare our pass itself:</p>
 260
 261 <div class="doc_code"><pre>
 262   <b>struct</b> Hello : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
 263 </pre></div><p>
 264
 265 <p>This declares a "<tt>Hello</tt>" class that is a subclass of <tt><a
 266 href="http://llvm.org/doxygen/classllvm_1_1FunctionPass.html">FunctionPass</a></tt>.
 267 The different builtin pass subclasses are described in detail <a
 268 href="#passtype">later</a>, but for now, know that <a
 269 href="#FunctionPass"><tt>FunctionPass</tt></a>'s operate a function at a
 270 time.</p>
 271
 272 <div class="doc_code"><pre>
 273      static char ID;
 274      Hello() : FunctionPass(&amp;ID) {}
 275 </pre></div><p>
 276
 277 <p> This declares pass identifier used by LLVM to identify pass. This allows LLVM to
 278 avoid using expensive C++ runtime information.</p>
 279
 280 <div class="doc_code"><pre>
 281     <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &amp;F) {
 282       errs() &lt;&lt; "<i>Hello: </i>" &lt;&lt; F.getName() &lt;&lt; "\n";
 283       <b>return false</b>;
 284     }
 285   };  <i>// end of struct Hello</i>
 286 </pre></div>
 287
 288 <p>We declare a "<a href="#runOnFunction"><tt>runOnFunction</tt></a>" method,
 289 which overloads an abstract virtual method inherited from <a
 290 href="#FunctionPass"><tt>FunctionPass</tt></a>.  This is where we are supposed
 291 to do our thing, so we just print out our message with the name of each
 292 function.</p>
 293
 294 <div class="doc_code"><pre>
 295   char Hello::ID = 0;
 296 </pre></div>
 297
 298 <p> We initialize pass ID here. LLVM uses ID's address to identify pass so
 299 initialization value is not important.</p>
 300
 301 <div class="doc_code"><pre>
 302   INITIALIZE_PASS(Hello, "<i>hello</i>", "<i>Hello World Pass</i>",
 303                         false /* Only looks at CFG */,
 304                         false /* Analysis Pass */);
 305 }  <i>// end of anonymous namespace</i>
 306 </pre></div>
 307
 308 <p>Lastly, we <a href="#registration">register our class</a> <tt>Hello</tt>,
 309 giving it a command line
 310 argument "<tt>hello</tt>", and a name "<tt>Hello World Pass</tt>".
 311 Last two arguments describe its behavior.
 312 If a pass walks CFG without modifying it then third argument is set to true.
 313 If  a pass is an analysis pass, for example dominator tree pass, then true
 314 is supplied as fourth argument. </p>
 315
 316 <p>As a whole, the <tt>.cpp</tt> file looks like:</p>
 317
 318 <div class="doc_code"><pre>
 319 <b>#include</b> "<a href="http://llvm.org/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
 320 <b>#include</b> "<a href="http://llvm.org/doxygen/Function_8h-source.html">llvm/Function.h</a>"
 321 <b>#include</b> "<a href="http://llvm.org/doxygen/raw__ostream_8h.html">llvm/Support/raw_ostream.h</a>"
 322
 323 <b>using namespace llvm;</b>
 324
 325 <b>namespace</b> {
 326   <b>struct Hello</b> : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
 327
 328     static char ID;
 329     Hello() : FunctionPass(&amp;ID) {}
 330
 331     <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &amp;F) {
 332       errs() &lt;&lt; "<i>Hello: </i>" &lt;&lt; F.getName() &lt;&lt; "\n";
 333       <b>return false</b>;
 334     }
 335   };
 336
 337   char Hello::ID = 0;
 338   INITIALIZE_PASS(Hello, "<i>Hello</i>", "<i>Hello World Pass</i>", false, false);
 339 }
 340
 341 </pre></div>
 342
 343 <p>Now that it's all together, compile the file with a simple "<tt>gmake</tt>"
 344 command in the local directory and you should get a new
 345 "<tt>Debug+Asserts/lib/Hello.so</tt> file.  Note that everything in this file is
 346 contained in an anonymous namespace: this reflects the fact that passes are self
 347 contained units that do not need external interfaces (although they can have
 348 them) to be useful.</p>
 349
 350 </div>
 351
 352 <!-- ======================================================================= -->
 353 <div class="doc_subsection">
 354   <a name="running">Running a pass with <tt>opt</tt></a>
 355 </div>
 356
 357 <div class="doc_text">
 358
 359 <p>Now that you have a brand new shiny shared object file, we can use the
 360 <tt>opt</tt> command to run an LLVM program through your pass.  Because you
 361 registered your pass with the <tt>INITIALIZE_PASS</tt> macro, you will be able to
 362 use the <tt>opt</tt> tool to access it, once loaded.</p>
 363
 364 <p>To test it, follow the example at the end of the <a
 365 href="GettingStarted.html">Getting Started Guide</a> to compile "Hello World" to
 366 LLVM.  We can now run the bitcode file (<tt>hello.bc</tt>) for the program
 367 through our transformation like this (or course, any bitcode file will
 368 work):</p>
 369
 370 <div class="doc_code"><pre>
 371 $ opt -load ../../../Debug+Asserts/lib/Hello.so -hello &lt; hello.bc &gt; /dev/null
 372 Hello: __main
 373 Hello: puts
 374 Hello: main
 375 </pre></div>
 376
 377 <p>The '<tt>-load</tt>' option specifies that '<tt>opt</tt>' should load your
 378 pass as a shared object, which makes '<tt>-hello</tt>' a valid command line
 379 argument (which is one reason you need to <a href="#registration">register your
 380 pass</a>).  Because the hello pass does not modify the program in any
 381 interesting way, we just throw away the result of <tt>opt</tt> (sending it to
 382 <tt>/dev/null</tt>).</p>
 383
 384 <p>To see what happened to the other string you registered, try running
 385 <tt>opt</tt> with the <tt>-help</tt> option:</p>
 386
 387 <div class="doc_code"><pre>
 388 $ opt -load ../../../Debug+Asserts/lib/Hello.so -help
 389 OVERVIEW: llvm .bc -&gt; .bc modular optimizer
 390
 391 USAGE: opt [options] &lt;input bitcode&gt;
 392
 393 OPTIONS:
 394   Optimizations available:
 395 ...
 396     -funcresolve    - Resolve Functions
 397     -gcse           - Global Common Subexpression Elimination
 398     -globaldce      - Dead Global Elimination
 399     <b>-hello          - Hello World Pass</b>
 400     -indvars        - Canonicalize Induction Variables
 401     -inline         - Function Integration/Inlining
 402     -instcombine    - Combine redundant instructions
 403 ...
 404 </pre></div>
 405
 406 <p>The pass name get added as the information string for your pass, giving some
 407 documentation to users of <tt>opt</tt>.  Now that you have a working pass, you
 408 would go ahead and make it do the cool transformations you want.  Once you get
 409 it all working and tested, it may become useful to find out how fast your pass
 410 is.  The <a href="#passManager"><tt>PassManager</tt></a> provides a nice command
 411 line option (<tt>--time-passes</tt>) that allows you to get information about
 412 the execution time of your pass along with the other passes you queue up.  For
 413 example:</p>
 414
 415 <div class="doc_code"><pre>
 416 $ opt -load ../../../Debug+Asserts/lib/Hello.so -hello -time-passes &lt; hello.bc &gt; /dev/null
 417 Hello: __main
 418 Hello: puts
 419 Hello: main
 420 ===============================================================================
 421                       ... Pass execution timing report ...
 422 ===============================================================================
 423   Total Execution Time: 0.02 seconds (0.0479059 wall clock)
 424
 425    ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Pass Name ---
 426    0.0100 (100.0%)   0.0000 (  0.0%)   0.0100 ( 50.0%)   0.0402 ( 84.0%)  Bitcode Writer
 427    0.0000 (  0.0%)   0.0100 (100.0%)   0.0100 ( 50.0%)   0.0031 (  6.4%)  Dominator Set Construction
 428    0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0013 (  2.7%)  Module Verifier
 429  <b>  0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0033 (  6.9%)  Hello World Pass</b>
 430    0.0100 (100.0%)   0.0100 (100.0%)   0.0200 (100.0%)   0.0479 (100.0%)  TOTAL
 431 </pre></div>
 432
 433 <p>As you can see, our implementation above is pretty fast :).  The additional
 434 passes listed are automatically inserted by the '<tt>opt</tt>' tool to verify
 435 that the LLVM emitted by your pass is still valid and well formed LLVM, which
 436 hasn't been broken somehow.</p>
 437
 438 <p>Now that you have seen the basics of the mechanics behind passes, we can talk
 439 about some more details of how they work and how to use them.</p>
 440
 441 </div>
 442
 443 <!-- *********************************************************************** -->
 444 <div class="doc_section">
 445   <a name="passtype">Pass classes and requirements</a>
 446 </div>
 447 <!-- *********************************************************************** -->
 448
 449 <div class="doc_text">
 450
 451 <p>One of the first things that you should do when designing a new pass is to
 452 decide what class you should subclass for your pass.  The <a
 453 href="#basiccode">Hello World</a> example uses the <tt><a
 454 href="#FunctionPass">FunctionPass</a></tt> class for its implementation, but we
 455 did not discuss why or when this should occur.  Here we talk about the classes
 456 available, from the most general to the most specific.</p>
 457
 458 <p>When choosing a superclass for your Pass, you should choose the <b>most
 459 specific</b> class possible, while still being able to meet the requirements
 460 listed.  This gives the LLVM Pass Infrastructure information necessary to
 461 optimize how passes are run, so that the resultant compiler isn't unnecessarily
 462 slow.</p>
 463
 464 </div>
 465
 466 <!-- ======================================================================= -->
 467 <div class="doc_subsection">
 468   <a name="ImmutablePass">The <tt>ImmutablePass</tt> class</a>
 469 </div>
 470
 471 <div class="doc_text">
 472
 473 <p>The most plain and boring type of pass is the "<tt><a
 474 href="http://llvm.org/doxygen/classllvm_1_1ImmutablePass.html">ImmutablePass</a></tt>"
 475 class.  This pass type is used for passes that do not have to be run, do not
 476 change state, and never need to be updated.  This is not a normal type of
 477 transformation or analysis, but can provide information about the current
 478 compiler configuration.</p>
 479
 480 <p>Although this pass class is very infrequently used, it is important for
 481 providing information about the current target machine being compiled for, and
 482 other static information that can affect the various transformations.</p>
 483
 484 <p><tt>ImmutablePass</tt>es never invalidate other transformations, are never
 485 invalidated, and are never "run".</p>
 486
 487 </div>
 488
 489 <!-- ======================================================================= -->
 490 <div class="doc_subsection">
 491   <a name="ModulePass">The <tt>ModulePass</tt> class</a>
 492 </div>
 493
 494 <div class="doc_text">
 495
 496 <p>The "<tt><a
 497 href="http://llvm.org/doxygen/classllvm_1_1ModulePass.html">ModulePass</a></tt>"
 498 class is the most general of all superclasses that you can use.  Deriving from
 499 <tt>ModulePass</tt> indicates that your pass uses the entire program as a unit,
 500 referring to function bodies in no predictable order, or adding and removing
 501 functions.  Because nothing is known about the behavior of <tt>ModulePass</tt>
 502 subclasses, no optimization can be done for their execution.</p>
 503
 504 <p>A module pass can use function level passes (e.g. dominators) using
 505 the getAnalysis interface
 506 <tt>getAnalysis&lt;DominatorTree&gt;(llvm::Function *)</tt> to provide the
 507 function to retrieve analysis result for, if the function pass does not require
 508 any module or immutable passes. Note that this can only be done for functions for which the
 509 analysis ran, e.g. in the case of dominators you should only ask for the
 510 DominatorTree for function definitions, not declarations.</p>
 511
 512 <p>To write a correct <tt>ModulePass</tt> subclass, derive from
 513 <tt>ModulePass</tt> and overload the <tt>runOnModule</tt> method with the
 514 following signature:</p>
 515
 516 </div>
 517
 518 <!-- _______________________________________________________________________ -->
 519 <div class="doc_subsubsection">
 520   <a name="runOnModule">The <tt>runOnModule</tt> method</a>
 521 </div>
 522
 523 <div class="doc_text">
 524
 525 <div class="doc_code"><pre>
 526   <b>virtual bool</b> runOnModule(Module &amp;M) = 0;
 527 </pre></div>
 528
 529 <p>The <tt>runOnModule</tt> method performs the interesting work of the pass.
 530 It should return true if the module was modified by the transformation and
 531 false otherwise.</p>
 532
 533 </div>
 534
 535 <!-- ======================================================================= -->
 536 <div class="doc_subsection">
 537   <a name="CallGraphSCCPass">The <tt>CallGraphSCCPass</tt> class</a>
 538 </div>
 539
 540 <div class="doc_text">
 541
 542 <p>The "<tt><a
 543 href="http://llvm.org/doxygen/classllvm_1_1CallGraphSCCPass.html">CallGraphSCCPass</a></tt>"
 544 is used by passes that need to traverse the program bottom-up on the call graph
 545 (callees before callers).  Deriving from CallGraphSCCPass provides some
 546 mechanics for building and traversing the CallGraph, but also allows the system
 547 to optimize execution of CallGraphSCCPass's.  If your pass meets the
 548 requirements outlined below, and doesn't meet the requirements of a <tt><a
 549 href="#FunctionPass">FunctionPass</a></tt> or <tt><a
 550 href="#BasicBlockPass">BasicBlockPass</a></tt>, you should derive from
 551 <tt>CallGraphSCCPass</tt>.</p>
 552
 553 <p><b>TODO</b>: explain briefly what SCC, Tarjan's algo, and B-U mean.</p>
 554
 555 <p>To be explicit, <tt>CallGraphSCCPass</tt> subclasses are:</p>
 556
 557 <ol>
 558
 559 <li>... <em>not allowed</em> to modify any <tt>Function</tt>s that are not in
 560 the current SCC.</li>
 561
 562 <li>... <em>not allowed</em> to inspect any Function's other than those in the
 563 current SCC and the direct callees of the SCC.</li>
 564
 565 <li>... <em>required</em> to preserve the current CallGraph object, updating it
 566 to reflect any changes made to the program.</li>
 567
 568 <li>... <em>not allowed</em> to add or remove SCC's from the current Module,
 569 though they may change the contents of an SCC.</li>
 570
 571 <li>... <em>allowed</em> to add or remove global variables from the current
 572 Module.</li>
 573
 574 <li>... <em>allowed</em> to maintain state across invocations of
 575     <a href="#runOnSCC"><tt>runOnSCC</tt></a> (including global data).</li>
 576 </ol>
 577
 578 <p>Implementing a <tt>CallGraphSCCPass</tt> is slightly tricky in some cases
 579 because it has to handle SCCs with more than one node in it.  All of the virtual
 580 methods described below should return true if they modified the program, or
 581 false if they didn't.</p>
 582
 583 </div>
 584
 585 <!-- _______________________________________________________________________ -->
 586 <div class="doc_subsubsection">
 587   <a name="doInitialization_scc">The <tt>doInitialization(CallGraph &amp;)</tt>
 588   method</a>
 589 </div>
 590
 591 <div class="doc_text">
 592
 593 <div class="doc_code"><pre>
 594   <b>virtual bool</b> doInitialization(CallGraph &amp;CG);
 595 </pre></div>
 596
 597 <p>The <tt>doIninitialize</tt> method is allowed to do most of the things that
 598 <tt>CallGraphSCCPass</tt>'s are not allowed to do.  They can add and remove
 599 functions, get pointers to functions, etc.  The <tt>doInitialization</tt> method
 600 is designed to do simple initialization type of stuff that does not depend on
 601 the SCCs being processed.  The <tt>doInitialization</tt> method call is not
 602 scheduled to overlap with any other pass executions (thus it should be very
 603 fast).</p>
 604
 605 </div>
 606
 607 <!-- _______________________________________________________________________ -->
 608 <div class="doc_subsubsection">
 609   <a name="runOnSCC">The <tt>runOnSCC</tt> method</a>
 610 </div>
 611
 612 <div class="doc_text">
 613
 614 <div class="doc_code"><pre>
 615   <b>virtual bool</b> runOnSCC(CallGraphSCC &amp;SCC) = 0;
 616 </pre></div>
 617
 618 <p>The <tt>runOnSCC</tt> method performs the interesting work of the pass, and
 619 should return true if the module was modified by the transformation, false
 620 otherwise.</p>
 621
 622 </div>
 623
 624 <!-- _______________________________________________________________________ -->
 625 <div class="doc_subsubsection">
 626   <a name="doFinalization_scc">The <tt>doFinalization(CallGraph
 627    &amp;)</tt> method</a>
 628 </div>
 629
 630 <div class="doc_text">
 631
 632 <div class="doc_code"><pre>
 633   <b>virtual bool</b> doFinalization(CallGraph &amp;CG);
 634 </pre></div>
 635
 636 <p>The <tt>doFinalization</tt> method is an infrequently used method that is
 637 called when the pass framework has finished calling <a
 638 href="#runOnFunction"><tt>runOnFunction</tt></a> for every function in the
 639 program being compiled.</p>
 640
 641 </div>
 642
 643 <!-- ======================================================================= -->
 644 <div class="doc_subsection">
 645   <a name="FunctionPass">The <tt>FunctionPass</tt> class</a>
 646 </div>
 647
 648 <div class="doc_text">
 649
 650 <p>In contrast to <tt>ModulePass</tt> subclasses, <tt><a
 651 href="http://llvm.org/doxygen/classllvm_1_1Pass.html">FunctionPass</a></tt>
 652 subclasses do have a predictable, local behavior that can be expected by the
 653 system.  All <tt>FunctionPass</tt> execute on each function in the program
 654 independent of all of the other functions in the program.
 655 <tt>FunctionPass</tt>'s do not require that they are executed in a particular
 656 order, and <tt>FunctionPass</tt>'s do not modify external functions.</p>
 657
 658 <p>To be explicit, <tt>FunctionPass</tt> subclasses are not allowed to:</p>
 659
 660 <ol>
 661 <li>Modify a Function other than the one currently being processed.</li>
 662 <li>Add or remove Function's from the current Module.</li>
 663 <li>Add or remove global variables from the current Module.</li>
 664 <li>Maintain state across invocations of
 665     <a href="#runOnFunction"><tt>runOnFunction</tt></a> (including global data)</li>
 666 </ol>
 667
 668 <p>Implementing a <tt>FunctionPass</tt> is usually straightforward (See the <a
 669 href="#basiccode">Hello World</a> pass for example).  <tt>FunctionPass</tt>'s
 670 may overload three virtual methods to do their work.  All of these methods
 671 should return true if they modified the program, or false if they didn't.</p>
 672
 673 </div>
 674
 675 <!-- _______________________________________________________________________ -->
 676 <div class="doc_subsubsection">
 677   <a name="doInitialization_mod">The <tt>doInitialization(Module &amp;)</tt>
 678   method</a>
 679 </div>
 680
 681 <div class="doc_text">
 682
 683 <div class="doc_code"><pre>
 684   <b>virtual bool</b> doInitialization(Module &amp;M);
 685 </pre></div>
 686
 687 <p>The <tt>doIninitialize</tt> method is allowed to do most of the things that
 688 <tt>FunctionPass</tt>'s are not allowed to do.  They can add and remove
 689 functions, get pointers to functions, etc.  The <tt>doInitialization</tt> method
 690 is designed to do simple initialization type of stuff that does not depend on
 691 the functions being processed.  The <tt>doInitialization</tt> method call is not
 692 scheduled to overlap with any other pass executions (thus it should be very
 693 fast).</p>
 694
 695 <p>A good example of how this method should be used is the <a
 696 href="http://llvm.org/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations</a>
 697 pass.  This pass converts <tt>malloc</tt> and <tt>free</tt> instructions into
 698 platform dependent <tt>malloc()</tt> and <tt>free()</tt> function calls.  It
 699 uses the <tt>doInitialization</tt> method to get a reference to the malloc and
 700 free functions that it needs, adding prototypes to the module if necessary.</p>
 701
 702 </div>
 703
 704 <!-- _______________________________________________________________________ -->
 705 <div class="doc_subsubsection">
 706   <a name="runOnFunction">The <tt>runOnFunction</tt> method</a>
 707 </div>
 708
 709 <div class="doc_text">
 710
 711 <div class="doc_code"><pre>
 712   <b>virtual bool</b> runOnFunction(Function &amp;F) = 0;
 713 </pre></div><p>
 714
 715 <p>The <tt>runOnFunction</tt> method must be implemented by your subclass to do
 716 the transformation or analysis work of your pass.  As usual, a true value should
 717 be returned if the function is modified.</p>
 718
 719 </div>
 720
 721 <!-- _______________________________________________________________________ -->
 722 <div class="doc_subsubsection">
 723   <a name="doFinalization_mod">The <tt>doFinalization(Module
 724   &amp;)</tt> method</a>
 725 </div>
 726
 727 <div class="doc_text">
 728
 729 <div class="doc_code"><pre>
 730   <b>virtual bool</b> doFinalization(Module &amp;M);
 731 </pre></div>
 732
 733 <p>The <tt>doFinalization</tt> method is an infrequently used method that is
 734 called when the pass framework has finished calling <a
 735 href="#runOnFunction"><tt>runOnFunction</tt></a> for every function in the
 736 program being compiled.</p>
 737
 738 </div>
 739
 740 <!-- ======================================================================= -->
 741 <div class="doc_subsection">
 742   <a name="LoopPass">The <tt>LoopPass</tt> class </a>
 743 </div>
 744
 745 <div class="doc_text">
 746
 747 <p> All <tt>LoopPass</tt> execute on each loop in the function independent of
 748 all of the other loops in the function. <tt>LoopPass</tt> processes loops in
 749 loop nest order such that outer most loop is processed last. </p>
 750
 751 <p> <tt>LoopPass</tt> subclasses are allowed to update loop nest using
 752 <tt>LPPassManager</tt> interface. Implementing a loop pass is usually
 753 straightforward. <tt>Looppass</tt>'s may overload three virtual methods to
 754 do their work. All these methods should return true if they modified the
 755 program, or false if they didn't. </p>
 756 </div>
 757
 758 <!-- _______________________________________________________________________ -->
 759 <div class="doc_subsubsection">
 760   <a name="doInitialization_loop">The <tt>doInitialization(Loop *,
 761                                                  LPPassManager &amp;)</tt>
 762   method</a>
 763 </div>
 764
 765 <div class="doc_text">
 766
 767 <div class="doc_code"><pre>
 768   <b>virtual bool</b> doInitialization(Loop *, LPPassManager &amp;LPM);
 769 </pre></div>
 770
 771 <p>The <tt>doInitialization</tt> method is designed to do simple initialization
 772 type of stuff that does not depend on the functions being processed.  The
 773 <tt>doInitialization</tt> method call is not scheduled to overlap with any
 774 other pass executions (thus it should be very fast). LPPassManager
 775 interface should be used to access Function or Module level analysis
 776 information.</p>
 777
 778 </div>
 779
 780
 781 <!-- _______________________________________________________________________ -->
 782 <div class="doc_subsubsection">
 783   <a name="runOnLoop">The <tt>runOnLoop</tt> method</a>
 784 </div>
 785
 786 <div class="doc_text">
 787
 788 <div class="doc_code"><pre>
 789   <b>virtual bool</b> runOnLoop(Loop *, LPPassManager &amp;LPM) = 0;
 790 </pre></div><p>
 791
 792 <p>The <tt>runOnLoop</tt> method must be implemented by your subclass to do
 793 the transformation or analysis work of your pass.  As usual, a true value should
 794 be returned if the function is modified. <tt>LPPassManager</tt> interface
 795 should be used to update loop nest.</p>
 796
 797 </div>
 798
 799 <!-- _______________________________________________________________________ -->
 800 <div class="doc_subsubsection">
 801   <a name="doFinalization_loop">The <tt>doFinalization()</tt> method</a>
 802 </div>
 803
 804 <div class="doc_text">
 805
 806 <div class="doc_code"><pre>
 807   <b>virtual bool</b> doFinalization();
 808 </pre></div>
 809
 810 <p>The <tt>doFinalization</tt> method is an infrequently used method that is
 811 called when the pass framework has finished calling <a
 812 href="#runOnLoop"><tt>runOnLoop</tt></a> for every loop in the
 813 program being compiled. </p>
 814
 815 </div>
 816
 817 <!-- ======================================================================= -->
 818 <div class="doc_subsection">
 819   <a name="RegionPass">The <tt>RegionPass</tt> class </a>
 820 </div>
 821
 822 <div class="doc_text">
 823
 824 <p> <tt>RegionPass</tt> is similar to <a href="#LoopPass"><tt>LoopPass</tt></a>,
 825 but executes on each single entry single exit region in the function.
 826 <tt>RegionPass</tt> processes regions in nested order such that the outer most
 827 region is processed last.  </p>
 828
 829 <p> <tt>RegionPass</tt> subclasses are allowed to update the region tree by using
 830 the <tt>RGPassManager</tt> interface. You may overload three virtual methods of
 831 <tt>RegionPass</tt> to implementing your own region pass is usually. All these
 832 methods should return true if they modified the program, or false if they didn not.
 833 </p>
 834 </div>
 835
 836 <!-- _______________________________________________________________________ -->
 837 <div class="doc_subsubsection">
 838   <a name="doInitialization_region">The <tt>doInitialization(Region *,
 839                                                  RGPassManager &amp;)</tt>
 840   method</a>
 841 </div>
 842
 843 <div class="doc_text">
 844
 845 <div class="doc_code"><pre>
 846   <b>virtual bool</b> doInitialization(Region *, RGPassManager &amp;RGM);
 847 </pre></div>
 848
 849 <p>The <tt>doInitialization</tt> method is designed to do simple initialization
 850 type of stuff that does not depend on the functions being processed.  The
 851 <tt>doInitialization</tt> method call is not scheduled to overlap with any
 852 other pass executions (thus it should be very fast). RPPassManager
 853 interface should be used to access Function or Module level analysis
 854 information.</p>
 855
 856 </div>
 857
 858
 859 <!-- _______________________________________________________________________ -->
 860 <div class="doc_subsubsection">
 861   <a name="runOnRegion">The <tt>runOnRegion</tt> method</a>
 862 </div>
 863
 864 <div class="doc_text">
 865
 866 <div class="doc_code"><pre>
 867   <b>virtual bool</b> runOnRegion(Region *, RGPassManager &amp;RGM) = 0;
 868 </pre></div><p>
 869
 870 <p>The <tt>runOnRegion</tt> method must be implemented by your subclass to do
 871 the transformation or analysis work of your pass.  As usual, a true value should
 872 be returned if the region is modified. <tt>RGPassManager</tt> interface
 873 should be used to update region tree.</p>
 874
 875 </div>
 876
 877 <!-- _______________________________________________________________________ -->
 878 <div class="doc_subsubsection">
 879   <a name="doFinalization_region">The <tt>doFinalization()</tt> method</a>
 880 </div>
 881
 882 <div class="doc_text">
 883
 884 <div class="doc_code"><pre>
 885   <b>virtual bool</b> doFinalization();
 886 </pre></div>
 887
 888 <p>The <tt>doFinalization</tt> method is an infrequently used method that is
 889 called when the pass framework has finished calling <a
 890 href="#runOnRegion"><tt>runOnRegion</tt></a> for every region in the
 891 program being compiled. </p>
 892
 893 </div>
 894
 895
 896
 897 <!-- ======================================================================= -->
 898 <div class="doc_subsection">
 899   <a name="BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
 900 </div>
 901
 902 <div class="doc_text">
 903
 904 <p><tt>BasicBlockPass</tt>'s are just like <a
 905 href="#FunctionPass"><tt>FunctionPass</tt></a>'s, except that they must limit
 906 their scope of inspection and modification to a single basic block at a time.
 907 As such, they are <b>not</b> allowed to do any of the following:</p>
 908
 909 <ol>
 910 <li>Modify or inspect any basic blocks outside of the current one</li>
 911 <li>Maintain state across invocations of
 912     <a href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a></li>
 913 <li>Modify the control flow graph (by altering terminator instructions)</li>
 914 <li>Any of the things forbidden for
 915     <a href="#FunctionPass"><tt>FunctionPass</tt></a>es.</li>
 916 </ol>
 917
 918 <p><tt>BasicBlockPass</tt>es are useful for traditional local and "peephole"
 919 optimizations.  They may override the same <a
 920 href="#doInitialization_mod"><tt>doInitialization(Module &amp;)</tt></a> and <a
 921 href="#doFinalization_mod"><tt>doFinalization(Module &amp;)</tt></a> methods that <a
 922 href="#FunctionPass"><tt>FunctionPass</tt></a>'s have, but also have the following virtual methods that may also be implemented:</p>
 923
 924 </div>
 925
 926 <!-- _______________________________________________________________________ -->
 927 <div class="doc_subsubsection">
 928   <a name="doInitialization_fn">The <tt>doInitialization(Function
 929   &amp;)</tt> method</a>
 930 </div>
 931
 932 <div class="doc_text">
 933
 934 <div class="doc_code"><pre>
 935   <b>virtual bool</b> doInitialization(Function &amp;F);
 936 </pre></div>
 937
 938 <p>The <tt>doIninitialize</tt> method is allowed to do most of the things that
 939 <tt>BasicBlockPass</tt>'s are not allowed to do, but that
 940 <tt>FunctionPass</tt>'s can.  The <tt>doInitialization</tt> method is designed
 941 to do simple initialization that does not depend on the
 942 BasicBlocks being processed.  The <tt>doInitialization</tt> method call is not
 943 scheduled to overlap with any other pass executions (thus it should be very
 944 fast).</p>
 945
 946 </div>
 947
 948 <!-- _______________________________________________________________________ -->
 949 <div class="doc_subsubsection">
 950   <a name="runOnBasicBlock">The <tt>runOnBasicBlock</tt> method</a>
 951 </div>
 952
 953 <div class="doc_text">
 954
 955 <div class="doc_code"><pre>
 956   <b>virtual bool</b> runOnBasicBlock(BasicBlock &amp;BB) = 0;
 957 </pre></div>
 958
 959 <p>Override this function to do the work of the <tt>BasicBlockPass</tt>.  This
 960 function is not allowed to inspect or modify basic blocks other than the
 961 parameter, and are not allowed to modify the CFG.  A true value must be returned
 962 if the basic block is modified.</p>
 963
 964 </div>
 965
 966 <!-- _______________________________________________________________________ -->
 967 <div class="doc_subsubsection">
 968   <a name="doFinalization_fn">The <tt>doFinalization(Function &amp;)</tt>
 969   method</a>
 970 </div>
 971
 972 <div class="doc_text">
 973
 974 <div class="doc_code"><pre>
 975   <b>virtual bool</b> doFinalization(Function &amp;F);
 976 </pre></div>
 977
 978 <p>The <tt>doFinalization</tt> method is an infrequently used method that is
 979 called when the pass framework has finished calling <a
 980 href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a> for every BasicBlock in the
 981 program being compiled.  This can be used to perform per-function
 982 finalization.</p>
 983
 984 </div>
 985
 986 <!-- ======================================================================= -->
 987 <div class="doc_subsection">
 988   <a name="MachineFunctionPass">The <tt>MachineFunctionPass</tt> class</a>
 989 </div>
 990
 991 <div class="doc_text">
 992
 993 <p>A <tt>MachineFunctionPass</tt> is a part of the LLVM code generator that
 994 executes on the machine-dependent representation of each LLVM function in the
 995 program.</p>
 996
 997 <p>Code generator passes are registered and initialized specially by
 998 <tt>TargetMachine::addPassesToEmitFile</tt> and similar routines, so they
 999 cannot generally be run from the <tt>opt</tt> or <tt>bugpoint</tt>
1000 commands.</p>
1001
1002 <p>A <tt>MachineFunctionPass</tt> is also a <tt>FunctionPass</tt>, so all
1003 the restrictions that apply to a <tt>FunctionPass</tt> also apply to it.
1004 <tt>MachineFunctionPass</tt>es also have additional restrictions. In particular,
1005 <tt>MachineFunctionPass</tt>es are not allowed to do any of the following:</p>
1006
1007 <ol>
1008 <li>Modify or create any LLVM IR Instructions, BasicBlocks, Arguments,
1009     Functions, GlobalVariables, GlobalAliases, or Modules.</li>
1010 <li>Modify a MachineFunction other than the one currently being processed.</li>
1011 <li>Maintain state across invocations of <a
1012 href="#runOnMachineFunction"><tt>runOnMachineFunction</tt></a> (including global
1013 data)</li>
1014 </ol>
1015
1016 </div>
1017
1018 <!-- _______________________________________________________________________ -->
1019 <div class="doc_subsubsection">
1020   <a name="runOnMachineFunction">The <tt>runOnMachineFunction(MachineFunction
1021   &amp;MF)</tt> method</a>
1022 </div>
1023
1024 <div class="doc_text">
1025
1026 <div class="doc_code"><pre>
1027   <b>virtual bool</b> runOnMachineFunction(MachineFunction &amp;MF) = 0;
1028 </pre></div>
1029
1030 <p><tt>runOnMachineFunction</tt> can be considered the main entry point of a
1031 <tt>MachineFunctionPass</tt>; that is, you should override this method to do the
1032 work of your <tt>MachineFunctionPass</tt>.</p>
1033
1034 <p>The <tt>runOnMachineFunction</tt> method is called on every
1035 <tt>MachineFunction</tt> in a <tt>Module</tt>, so that the
1036 <tt>MachineFunctionPass</tt> may perform optimizations on the machine-dependent
1037 representation of the function. If you want to get at the LLVM <tt>Function</tt>
1038 for the <tt>MachineFunction</tt> you're working on, use
1039 <tt>MachineFunction</tt>'s <tt>getFunction()</tt> accessor method -- but
1040 remember, you may not modify the LLVM <tt>Function</tt> or its contents from a
1041 <tt>MachineFunctionPass</tt>.</p>
1042
1043 </div>
1044
1045 <!-- *********************************************************************** -->
1046 <div class="doc_section">
1047   <a name="registration">Pass registration</a>
1048 </div>
1049 <!-- *********************************************************************** -->
1050
1051 <div class="doc_text">
1052
1053 <p>In the <a href="#basiccode">Hello World</a> example pass we illustrated how
1054 pass registration works, and discussed some of the reasons that it is used and
1055 what it does.  Here we discuss how and why passes are registered.</p>
1056
1057 <p>As we saw above, passes are registered with the <b><tt>INITIALIZE_PASS</tt></b>
1058 macro.  The first parameter is the name of the pass that is to be used on
1059 the command line to specify that the pass should be added to a program (for
1060 example, with <tt>opt</tt> or <tt>bugpoint</tt>).  The second argument is the
1061 name of the pass, which is to be used for the <tt>-help</tt> output of
1062 programs, as
1063 well as for debug output generated by the <tt>--debug-pass</tt> option.</p>
1064
1065 <p>If you want your pass to be easily dumpable, you should
1066 implement the virtual <tt>print</tt> method:</p>
1067
1068 </div>
1069
1070 <!-- _______________________________________________________________________ -->
1071 <div class="doc_subsubsection">
1072   <a name="print">The <tt>print</tt> method</a>
1073 </div>
1074
1075 <div class="doc_text">
1076
1077 <div class="doc_code"><pre>
1078   <b>virtual void</b> print(std::ostream &amp;O, <b>const</b> Module *M) <b>const</b>;
1079 </pre></div>
1080
1081 <p>The <tt>print</tt> method must be implemented by "analyses" in order to print
1082 a human readable version of the analysis results.  This is useful for debugging
1083 an analysis itself, as well as for other people to figure out how an analysis
1084 works.  Use the <tt>opt -analyze</tt> argument to invoke this method.</p>
1085
1086 <p>The <tt>llvm::OStream</tt> parameter specifies the stream to write the results on,
1087 and the <tt>Module</tt> parameter gives a pointer to the top level module of the
1088 program that has been analyzed.  Note however that this pointer may be null in
1089 certain circumstances (such as calling the <tt>Pass::dump()</tt> from a
1090 debugger), so it should only be used to enhance debug output, it should not be
1091 depended on.</p>
1092
1093 </div>
1094
1095 <!-- *********************************************************************** -->
1096 <div class="doc_section">
1097   <a name="interaction">Specifying interactions between passes</a>
1098 </div>
1099 <!-- *********************************************************************** -->
1100
1101 <div class="doc_text">
1102
1103 <p>One of the main responsibilities of the <tt>PassManager</tt> is to make sure
1104 that passes interact with each other correctly.  Because <tt>PassManager</tt>
1105 tries to <a href="#passmanager">optimize the execution of passes</a> it must
1106 know how the passes interact with each other and what dependencies exist between
1107 the various passes.  To track this, each pass can declare the set of passes that
1108 are required to be executed before the current pass, and the passes which are
1109 invalidated by the current pass.</p>
1110
1111 <p>Typically this functionality is used to require that analysis results are
1112 computed before your pass is run.  Running arbitrary transformation passes can
1113 invalidate the computed analysis results, which is what the invalidation set
1114 specifies.  If a pass does not implement the <tt><a
1115 href="#getAnalysisUsage">getAnalysisUsage</a></tt> method, it defaults to not
1116 having any prerequisite passes, and invalidating <b>all</b> other passes.</p>
1117
1118 </div>
1119
1120 <!-- _______________________________________________________________________ -->
1121 <div class="doc_subsubsection">
1122   <a name="getAnalysisUsage">The <tt>getAnalysisUsage</tt> method</a>
1123 </div>
1124
1125 <div class="doc_text">
1126
1127 <div class="doc_code"><pre>
1128   <b>virtual void</b> getAnalysisUsage(AnalysisUsage &amp;Info) <b>const</b>;
1129 </pre></div>
1130
1131 <p>By implementing the <tt>getAnalysisUsage</tt> method, the required and
1132 invalidated sets may be specified for your transformation.  The implementation
1133 should fill in the <tt><a
1134 href="http://llvm.org/doxygen/classllvm_1_1AnalysisUsage.html">AnalysisUsage</a></tt>
1135 object with information about which passes are required and not invalidated.  To
1136 do this, a pass may call any of the following methods on the AnalysisUsage
1137 object:</p>
1138 </div>
1139
1140 <!-- _______________________________________________________________________ -->
1141 <div class="doc_subsubsection">
1142   <a name="AU::addRequired">The <tt>AnalysisUsage::addRequired&lt;&gt;</tt> and <tt>AnalysisUsage::addRequiredTransitive&lt;&gt;</tt> methods</a>
1143 </div>
1144
1145 <div class="doc_text">
1146 <p>
1147 If your pass requires a previous pass to be executed (an analysis for example),
1148 it can use one of these methods to arrange for it to be run before your pass.
1149 LLVM has many different types of analyses and passes that can be required,
1150 spanning the range from <tt>DominatorSet</tt> to <tt>BreakCriticalEdges</tt>.
1151 Requiring <tt>BreakCriticalEdges</tt>, for example, guarantees that there will
1152 be no critical edges in the CFG when your pass has been run.
1153 </p>
1154
1155 <p>
1156 Some analyses chain to other analyses to do their job.  For example, an <a
1157 href="AliasAnalysis.html">AliasAnalysis</a> implementation is required to <a
1158 href="AliasAnalysis.html#chaining">chain</a> to other alias analysis passes.  In
1159 cases where analyses chain, the <tt>addRequiredTransitive</tt> method should be
1160 used instead of the <tt>addRequired</tt> method.  This informs the PassManager
1161 that the transitively required pass should be alive as long as the requiring
1162 pass is.
1163 </p>
1164 </div>
1165
1166 <!-- _______________________________________________________________________ -->
1167 <div class="doc_subsubsection">
1168   <a name="AU::addPreserved">The <tt>AnalysisUsage::addPreserved&lt;&gt;</tt> method</a>
1169 </div>
1170
1171 <div class="doc_text">
1172 <p>
1173 One of the jobs of the PassManager is to optimize how and when analyses are run.
1174 In particular, it attempts to avoid recomputing data unless it needs to.  For
1175 this reason, passes are allowed to declare that they preserve (i.e., they don't
1176 invalidate) an existing analysis if it's available.  For example, a simple
1177 constant folding pass would not modify the CFG, so it can't possibly affect the
1178 results of dominator analysis.  By default, all passes are assumed to invalidate
1179 all others.
1180 </p>
1181
1182 <p>
1183 The <tt>AnalysisUsage</tt> class provides several methods which are useful in
1184 certain circumstances that are related to <tt>addPreserved</tt>.  In particular,
1185 the <tt>setPreservesAll</tt> method can be called to indicate that the pass does
1186 not modify the LLVM program at all (which is true for analyses), and the
1187 <tt>setPreservesCFG</tt> method can be used by transformations that change
1188 instructions in the program but do not modify the CFG or terminator instructions
1189 (note that this property is implicitly set for <a
1190 href="#BasicBlockPass">BasicBlockPass</a>'s).
1191 </p>
1192
1193 <p>
1194 <tt>addPreserved</tt> is particularly useful for transformations like
1195 <tt>BreakCriticalEdges</tt>.  This pass knows how to update a small set of loop
1196 and dominator related analyses if they exist, so it can preserve them, despite
1197 the fact that it hacks on the CFG.
1198 </p>
1199 </div>
1200
1201 <!-- _______________________________________________________________________ -->
1202 <div class="doc_subsubsection">
1203   <a name="AU::examples">Example implementations of <tt>getAnalysisUsage</tt></a>
1204 </div>
1205
1206 <div class="doc_text">
1207
1208 <div class="doc_code"><pre>
1209   <i>// This is an example implementation from an analysis, which does not modify
1210   // the program at all, yet has a prerequisite.</i>
1211   <b>void</b> <a href="http://llvm.org/doxygen/classllvm_1_1PostDominanceFrontier.html">PostDominanceFrontier</a>::getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
1212     AU.setPreservesAll();
1213     AU.addRequired&lt;<a href="http://llvm.org/doxygen/classllvm_1_1PostDominatorTree.html">PostDominatorTree</a>&gt;();
1214   }
1215 </pre></div>
1216
1217 <p>and:</p>
1218
1219 <div class="doc_code"><pre>
1220   <i>// This example modifies the program, but does not modify the CFG</i>
1221   <b>void</b> <a href="http://llvm.org/doxygen/structLICM.html">LICM</a>::getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
1222     AU.setPreservesCFG();
1223     AU.addRequired&lt;<a href="http://llvm.org/doxygen/classllvm_1_1LoopInfo.html">LoopInfo</a>&gt;();
1224   }
1225 </pre></div>
1226
1227 </div>
1228
1229 <!-- _______________________________________________________________________ -->
1230 <div class="doc_subsubsection">
1231   <a name="getAnalysis">The <tt>getAnalysis&lt;&gt;</tt> and
1232 <tt>getAnalysisIfAvailable&lt;&gt;</tt> methods</a>
1233 </div>
1234
1235 <div class="doc_text">
1236
1237 <p>The <tt>Pass::getAnalysis&lt;&gt;</tt> method is automatically inherited by
1238 your class, providing you with access to the passes that you declared that you
1239 required with the <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a>
1240 method.  It takes a single template argument that specifies which pass class you
1241 want, and returns a reference to that pass.  For example:</p>
1242
1243 <div class="doc_code"><pre>
1244    bool LICM::runOnFunction(Function &amp;F) {
1245      LoopInfo &amp;LI = getAnalysis&lt;LoopInfo&gt;();
1246      ...
1247    }
1248 </pre></div>
1249
1250 <p>This method call returns a reference to the pass desired.  You may get a
1251 runtime assertion failure if you attempt to get an analysis that you did not
1252 declare as required in your <a
1253 href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> implementation.  This
1254 method can be called by your <tt>run*</tt> method implementation, or by any
1255 other local method invoked by your <tt>run*</tt> method.
1256
1257 A module level pass can use function level analysis info using this interface.
1258 For example:</p>
1259
1260 <div class="doc_code"><pre>
1261    bool ModuleLevelPass::runOnModule(Module &amp;M) {
1262      ...
1263      DominatorTree &amp;DT = getAnalysis&lt;DominatorTree&gt;(Func);
1264      ...
1265    }
1266 </pre></div>
1267
1268 <p>In above example, runOnFunction for DominatorTree is called by pass manager
1269 before returning a reference to the desired pass.</p>
1270
1271 <p>
1272 If your pass is capable of updating analyses if they exist (e.g.,
1273 <tt>BreakCriticalEdges</tt>, as described above), you can use the
1274 <tt>getAnalysisIfAvailable</tt> method, which returns a pointer to the analysis
1275 if it is active.  For example:</p>
1276
1277 <div class="doc_code"><pre>
1278   ...
1279   if (DominatorSet *DS = getAnalysisIfAvailable&lt;DominatorSet&gt;()) {
1280     <i>// A DominatorSet is active.  This code will update it.</i>
1281   }
1282   ...
1283 </pre></div>
1284
1285 </div>
1286
1287 <!-- *********************************************************************** -->
1288 <div class="doc_section">
1289   <a name="analysisgroup">Implementing Analysis Groups</a>
1290 </div>
1291 <!-- *********************************************************************** -->
1292
1293 <div class="doc_text">
1294
1295 <p>Now that we understand the basics of how passes are defined, how they are
1296 used, and how they are required from other passes, it's time to get a little bit
1297 fancier.  All of the pass relationships that we have seen so far are very
1298 simple: one pass depends on one other specific pass to be run before it can run.
1299 For many applications, this is great, for others, more flexibility is
1300 required.</p>
1301
1302 <p>In particular, some analyses are defined such that there is a single simple
1303 interface to the analysis results, but multiple ways of calculating them.
1304 Consider alias analysis for example.  The most trivial alias analysis returns
1305 "may alias" for any alias query.  The most sophisticated analysis a
1306 flow-sensitive, context-sensitive interprocedural analysis that can take a
1307 significant amount of time to execute (and obviously, there is a lot of room
1308 between these two extremes for other implementations).  To cleanly support
1309 situations like this, the LLVM Pass Infrastructure supports the notion of
1310 Analysis Groups.</p>
1311
1312 </div>
1313
1314 <!-- _______________________________________________________________________ -->
1315 <div class="doc_subsubsection">
1316   <a name="agconcepts">Analysis Group Concepts</a>
1317 </div>
1318
1319 <div class="doc_text">
1320
1321 <p>An Analysis Group is a single simple interface that may be implemented by
1322 multiple different passes.  Analysis Groups can be given human readable names
1323 just like passes, but unlike passes, they need not derive from the <tt>Pass</tt>
1324 class.  An analysis group may have one or more implementations, one of which is
1325 the "default" implementation.</p>
1326
1327 <p>Analysis groups are used by client passes just like other passes are: the
1328 <tt>AnalysisUsage::addRequired()</tt> and <tt>Pass::getAnalysis()</tt> methods.
1329 In order to resolve this requirement, the <a href="#passmanager">PassManager</a>
1330 scans the available passes to see if any implementations of the analysis group
1331 are available.  If none is available, the default implementation is created for
1332 the pass to use.  All standard rules for <A href="#interaction">interaction
1333 between passes</a> still apply.</p>
1334
1335 <p>Although <a href="#registration">Pass Registration</a> is optional for normal
1336 passes, all analysis group implementations must be registered, and must use the
1337 <A href="#registerag"><tt>INITIALIZE_AG_PASS</tt></a> template to join the
1338 implementation pool.  Also, a default implementation of the interface
1339 <b>must</b> be registered with <A
1340 href="#registerag"><tt>RegisterAnalysisGroup</tt></a>.</p>
1341
1342 <p>As a concrete example of an Analysis Group in action, consider the <a
1343 href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>
1344 analysis group.  The default implementation of the alias analysis interface (the
1345 <tt><a
1346 href="http://llvm.org/doxygen/structBasicAliasAnalysis.html">basicaa</a></tt>
1347 pass) just does a few simple checks that don't require significant analysis to
1348 compute (such as: two different globals can never alias each other, etc).
1349 Passes that use the <tt><a
1350 href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a></tt>
1351 interface (for example the <tt><a
1352 href="http://llvm.org/doxygen/structGCSE.html">gcse</a></tt> pass), do
1353 not care which implementation of alias analysis is actually provided, they just
1354 use the designated interface.</p>
1355
1356 <p>From the user's perspective, commands work just like normal.  Issuing the
1357 command '<tt>opt -gcse ...</tt>' will cause the <tt>basicaa</tt> class to be
1358 instantiated and added to the pass sequence.  Issuing the command '<tt>opt
1359 -somefancyaa -gcse ...</tt>' will cause the <tt>gcse</tt> pass to use the
1360 <tt>somefancyaa</tt> alias analysis (which doesn't actually exist, it's just a
1361 hypothetical example) instead.</p>
1362
1363 </div>
1364
1365 <!-- _______________________________________________________________________ -->
1366 <div class="doc_subsubsection">
1367   <a name="registerag">Using <tt>RegisterAnalysisGroup</tt></a>
1368 </div>
1369
1370 <div class="doc_text">
1371
1372 <p>The <tt>RegisterAnalysisGroup</tt> template is used to register the analysis
1373 group itself, while the <tt>INITIALIZE_AG_PASS</tt> is used to add pass
1374 implementations to the analysis group.  First,
1375 an analysis group should be registered, with a human readable name
1376 provided for it.
1377 Unlike registration of passes, there is no command line argument to be specified
1378 for the Analysis Group Interface itself, because it is "abstract":</p>
1379
1380 <div class="doc_code"><pre>
1381   <b>static</b> RegisterAnalysisGroup&lt;<a href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>&gt; A("<i>Alias Analysis</i>");
1382 </pre></div>
1383
1384 <p>Once the analysis is registered, passes can declare that they are valid
1385 implementations of the interface by using the following code:</p>
1386
1387 <div class="doc_code"><pre>
1388 <b>namespace</b> {
1389   //<i> Declare that we implement the AliasAnalysis interface</i>
1390   INITIALIZE_AG_PASS(FancyAA, <a href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>, "<i>somefancyaa</i>",
1391                      "<i>A more complex alias analysis implementation</i>",
1392                      false, // <i>Is CFG Only?</i>
1393                      true,  // <i>Is Analysis?</i>
1394                      false, // <i>Is default Analysis Group implementation?</i>
1395                     );
1396 }
1397 </pre></div>
1398
1399 <p>This just shows a class <tt>FancyAA</tt> that
1400 uses the <tt>INITIALIZE_AG_PASS</tt> macro both to register and
1401 to "join" the <tt><a href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a></tt>
1402 analysis group.  Every implementation of an analysis group should join using
1403 this macro.</p>
1404
1405 <div class="doc_code"><pre>
1406 <b>namespace</b> {
1407   //<i> Declare that we implement the AliasAnalysis interface</i>
1408   INITIALIZE_AG_PASS(BasicAA, <a href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>, "<i>basicaa</i>",
1409                      "<i>Basic Alias Analysis (default AA impl)</i>",
1410                      false, // <i>Is CFG Only?</i>
1411                      true,  // <i>Is Analysis?</i>
1412                      true, // <i>Is default Analysis Group implementation?</i>
1413                     );
1414 }
1415 </pre></div>
1416
1417 <p>Here we show how the default implementation is specified (using the final
1418 argument to the <tt>INITIALIZE_AG_PASS</tt> template).  There must be exactly
1419 one default implementation available at all times for an Analysis Group to be
1420 used.  Only default implementation can derive from <tt>ImmutablePass</tt>.
1421 Here we declare that the
1422  <tt><a href="http://llvm.org/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a></tt>
1423 pass is the default implementation for the interface.</p>
1424
1425 </div>
1426
1427 <!-- *********************************************************************** -->
1428 <div class="doc_section">
1429   <a name="passStatistics">Pass Statistics</a>
1430 </div>
1431 <!-- *********************************************************************** -->
1432
1433 <div class="doc_text">
1434 <p>The <a
1435 href="http://llvm.org/doxygen/Statistic_8h-source.html"><tt>Statistic</tt></a>
1436 class is designed to be an easy way to expose various success
1437 metrics from passes.  These statistics are printed at the end of a
1438 run, when the -stats command line option is enabled on the command
1439 line. See the <a href="http://llvm.org/docs/ProgrammersManual.html#Statistic">Statistics section</a> in the Programmer's Manual for details.
1440
1441 </div>
1442
1443
1444 <!-- *********************************************************************** -->
1445 <div class="doc_section">
1446   <a name="passmanager">What PassManager does</a>
1447 </div>
1448 <!-- *********************************************************************** -->
1449
1450 <div class="doc_text">
1451
1452 <p>The <a
1453 href="http://llvm.org/doxygen/PassManager_8h-source.html"><tt>PassManager</tt></a>
1454 <a
1455 href="http://llvm.org/doxygen/classllvm_1_1PassManager.html">class</a>
1456 takes a list of passes, ensures their <a href="#interaction">prerequisites</a>
1457 are set up correctly, and then schedules passes to run efficiently.  All of the
1458 LLVM tools that run passes use the <tt>PassManager</tt> for execution of these
1459 passes.</p>
1460
1461 <p>The <tt>PassManager</tt> does two main things to try to reduce the execution
1462 time of a series of passes:</p>
1463
1464 <ol>
1465 <li><b>Share analysis results</b> - The PassManager attempts to avoid
1466 recomputing analysis results as much as possible.  This means keeping track of
1467 which analyses are available already, which analyses get invalidated, and which
1468 analyses are needed to be run for a pass.  An important part of work is that the
1469 <tt>PassManager</tt> tracks the exact lifetime of all analysis results, allowing
1470 it to <a href="#releaseMemory">free memory</a> allocated to holding analysis
1471 results as soon as they are no longer needed.</li>
1472
1473 <li><b>Pipeline the execution of passes on the program</b> - The
1474 <tt>PassManager</tt> attempts to get better cache and memory usage behavior out
1475 of a series of passes by pipelining the passes together.  This means that, given
1476 a series of consequtive <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s, it
1477 will execute all of the <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s on
1478 the first function, then all of the <a
1479 href="#FunctionPass"><tt>FunctionPass</tt></a>es on the second function,
1480 etc... until the entire program has been run through the passes.
1481
1482 <p>This improves the cache behavior of the compiler, because it is only touching
1483 the LLVM program representation for a single function at a time, instead of
1484 traversing the entire program.  It reduces the memory consumption of compiler,
1485 because, for example, only one <a
1486 href="http://llvm.org/doxygen/classllvm_1_1DominatorSet.html"><tt>DominatorSet</tt></a>
1487 needs to be calculated at a time.  This also makes it possible to implement
1488 some <a
1489 href="#SMP">interesting enhancements</a> in the future.</p></li>
1490
1491 </ol>
1492
1493 <p>The effectiveness of the <tt>PassManager</tt> is influenced directly by how
1494 much information it has about the behaviors of the passes it is scheduling.  For
1495 example, the "preserved" set is intentionally conservative in the face of an
1496 unimplemented <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method.
1497 Not implementing when it should be implemented will have the effect of not
1498 allowing any analysis results to live across the execution of your pass.</p>
1499
1500 <p>The <tt>PassManager</tt> class exposes a <tt>--debug-pass</tt> command line
1501 options that is useful for debugging pass execution, seeing how things work, and
1502 diagnosing when you should be preserving more analyses than you currently are
1503 (To get information about all of the variants of the <tt>--debug-pass</tt>
1504 option, just type '<tt>opt -help-hidden</tt>').</p>
1505
1506 <p>By using the <tt>--debug-pass=Structure</tt> option, for example, we can see
1507 how our <a href="#basiccode">Hello World</a> pass interacts with other passes.
1508 Lets try it out with the <tt>gcse</tt> and <tt>licm</tt> passes:</p>
1509
1510 <div class="doc_code"><pre>
1511 $ opt -load ../../../Debug+Asserts/lib/Hello.so -gcse -licm --debug-pass=Structure &lt; hello.bc &gt; /dev/null
1512 Module Pass Manager
1513   Function Pass Manager
1514     Dominator Set Construction
1515     Immediate Dominators Construction
1516     Global Common Subexpression Elimination
1517 --  Immediate Dominators Construction
1518 --  Global Common Subexpression Elimination
1519     Natural Loop Construction
1520     Loop Invariant Code Motion
1521 --  Natural Loop Construction
1522 --  Loop Invariant Code Motion
1523     Module Verifier
1524 --  Dominator Set Construction
1525 --  Module Verifier
1526   Bitcode Writer
1527 --Bitcode Writer
1528 </pre></div>
1529
1530 <p>This output shows us when passes are constructed and when the analysis
1531 results are known to be dead (prefixed with '<tt>--</tt>').  Here we see that
1532 GCSE uses dominator and immediate dominator information to do its job.  The LICM
1533 pass uses natural loop information, which uses dominator sets, but not immediate
1534 dominators.  Because immediate dominators are no longer useful after the GCSE
1535 pass, it is immediately destroyed.  The dominator sets are then reused to
1536 compute natural loop information, which is then used by the LICM pass.</p>
1537
1538 <p>After the LICM pass, the module verifier runs (which is automatically added
1539 by the '<tt>opt</tt>' tool), which uses the dominator set to check that the
1540 resultant LLVM code is well formed.  After it finishes, the dominator set
1541 information is destroyed, after being computed once, and shared by three
1542 passes.</p>
1543
1544 <p>Lets see how this changes when we run the <a href="#basiccode">Hello
1545 World</a> pass in between the two passes:</p>
1546
1547 <div class="doc_code"><pre>
1548 $ opt -load ../../../Debug+Asserts/lib/Hello.so -gcse -hello -licm --debug-pass=Structure &lt; hello.bc &gt; /dev/null
1549 Module Pass Manager
1550   Function Pass Manager
1551     Dominator Set Construction
1552     Immediate Dominators Construction
1553     Global Common Subexpression Elimination
1554 <b>--  Dominator Set Construction</b>
1555 --  Immediate Dominators Construction
1556 --  Global Common Subexpression Elimination
1557 <b>    Hello World Pass
1558 --  Hello World Pass
1559     Dominator Set Construction</b>
1560     Natural Loop Construction
1561     Loop Invariant Code Motion
1562 --  Natural Loop Construction
1563 --  Loop Invariant Code Motion
1564     Module Verifier
1565 --  Dominator Set Construction
1566 --  Module Verifier
1567   Bitcode Writer
1568 --Bitcode Writer
1569 Hello: __main
1570 Hello: puts
1571 Hello: main
1572 </pre></div>
1573
1574 <p>Here we see that the <a href="#basiccode">Hello World</a> pass has killed the
1575 Dominator Set pass, even though it doesn't modify the code at all!  To fix this,
1576 we need to add the following <a
1577 href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method to our pass:</p>
1578
1579 <div class="doc_code"><pre>
1580     <i>// We don't modify the program, so we preserve all analyses</i>
1581     <b>virtual void</b> getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
1582       AU.setPreservesAll();
1583     }
1584 </pre></div>
1585
1586 <p>Now when we run our pass, we get this output:</p>
1587
1588 <div class="doc_code"><pre>
1589 $ opt -load ../../../Debug+Asserts/lib/Hello.so -gcse -hello -licm --debug-pass=Structure &lt; hello.bc &gt; /dev/null
1590 Pass Arguments:  -gcse -hello -licm
1591 Module Pass Manager
1592   Function Pass Manager
1593     Dominator Set Construction
1594     Immediate Dominators Construction
1595     Global Common Subexpression Elimination
1596 --  Immediate Dominators Construction
1597 --  Global Common Subexpression Elimination
1598     Hello World Pass
1599 --  Hello World Pass
1600     Natural Loop Construction
1601     Loop Invariant Code Motion
1602 --  Loop Invariant Code Motion
1603 --  Natural Loop Construction
1604     Module Verifier
1605 --  Dominator Set Construction
1606 --  Module Verifier
1607   Bitcode Writer
1608 --Bitcode Writer
1609 Hello: __main
1610 Hello: puts
1611 Hello: main
1612 </pre></div>
1613
1614 <p>Which shows that we don't accidentally invalidate dominator information
1615 anymore, and therefore do not have to compute it twice.</p>
1616
1617 </div>
1618
1619 <!-- _______________________________________________________________________ -->
1620 <div class="doc_subsubsection">
1621   <a name="releaseMemory">The <tt>releaseMemory</tt> method</a>
1622 </div>
1623
1624 <div class="doc_text">
1625
1626 <div class="doc_code"><pre>
1627   <b>virtual void</b> releaseMemory();
1628 </pre></div>
1629
1630 <p>The <tt>PassManager</tt> automatically determines when to compute analysis
1631 results, and how long to keep them around for.  Because the lifetime of the pass
1632 object itself is effectively the entire duration of the compilation process, we
1633 need some way to free analysis results when they are no longer useful.  The
1634 <tt>releaseMemory</tt> virtual method is the way to do this.</p>
1635
1636 <p>If you are writing an analysis or any other pass that retains a significant
1637 amount of state (for use by another pass which "requires" your pass and uses the
1638 <a href="#getAnalysis">getAnalysis</a> method) you should implement
1639 <tt>releaseMemory</tt> to, well, release the memory allocated to maintain this
1640 internal state.  This method is called after the <tt>run*</tt> method for the
1641 class, before the next call of <tt>run*</tt> in your pass.</p>
1642
1643 </div>
1644
1645 <!-- *********************************************************************** -->
1646 <div class="doc_section">
1647   <a name="registering">Registering dynamically loaded passes</a>
1648 </div>
1649 <!-- *********************************************************************** -->
1650
1651 <div class="doc_text">
1652
1653 <p><i>Size matters</i> when constructing production quality tools using llvm,
1654 both for the purposes of distribution, and for regulating the resident code size
1655 when running on the target system. Therefore, it becomes desirable to
1656 selectively use some passes, while omitting others and maintain the flexibility
1657 to change configurations later on. You want to be able to do all this, and,
1658 provide feedback to the user. This is where pass registration comes into
1659 play.</p>
1660
1661 <p>The fundamental mechanisms for pass registration are the
1662 <tt>MachinePassRegistry</tt> class and subclasses of
1663 <tt>MachinePassRegistryNode</tt>.</p>
1664
1665 <p>An instance of <tt>MachinePassRegistry</tt> is used to maintain a list of
1666 <tt>MachinePassRegistryNode</tt> objects.  This instance maintains the list and
1667 communicates additions and deletions to the command line interface.</p>
1668
1669 <p>An instance of <tt>MachinePassRegistryNode</tt> subclass is used to maintain
1670 information provided about a particular pass.  This information includes the
1671 command line name, the command help string and the address of the function used
1672 to create an instance of the pass.  A global static constructor of one of these
1673 instances <i>registers</i> with a corresponding <tt>MachinePassRegistry</tt>,
1674 the static destructor <i>unregisters</i>. Thus a pass that is statically linked
1675 in the tool will be registered at start up. A dynamically loaded pass will
1676 register on load and unregister at unload.</p>
1677
1678 </div>
1679
1680 <!-- _______________________________________________________________________ -->
1681 <div class="doc_subsection">
1682   <a name="registering_existing">Using existing registries</a>
1683 </div>
1684
1685 <div class="doc_text">
1686
1687 <p>There are predefined registries to track instruction scheduling
1688 (<tt>RegisterScheduler</tt>) and register allocation (<tt>RegisterRegAlloc</tt>)
1689 machine passes.  Here we will describe how to <i>register</i> a register
1690 allocator machine pass.</p>
1691
1692 <p>Implement your register allocator machine pass.  In your register allocator
1693 .cpp file add the following include;</p>
1694
1695 <div class="doc_code"><pre>
1696   #include "llvm/CodeGen/RegAllocRegistry.h"
1697 </pre></div>
1698
1699 <p>Also in your register allocator .cpp file, define a creator function in the
1700 form; </p>
1701
1702 <div class="doc_code"><pre>
1703   FunctionPass *createMyRegisterAllocator() {
1704     return new MyRegisterAllocator();
1705   }
1706 </pre></div>
1707
1708 <p>Note that the signature of this function should match the type of
1709 <tt>RegisterRegAlloc::FunctionPassCtor</tt>.  In the same file add the
1710 "installing" declaration, in the form;</p>
1711
1712 <div class="doc_code"><pre>
1713   static RegisterRegAlloc myRegAlloc("myregalloc",
1714     "  my register allocator help string",
1715     createMyRegisterAllocator);
1716 </pre></div>
1717
1718 <p>Note the two spaces prior to the help string produces a tidy result on the
1719 -help query.</p>
1720
1721 <div class="doc_code"><pre>
1722 $ llc -help
1723   ...
1724   -regalloc                    - Register allocator to use (default=linearscan)
1725     =linearscan                -   linear scan register allocator
1726     =local                     -   local register allocator
1727     =simple                    -   simple register allocator
1728     =myregalloc                -   my register allocator help string
1729   ...
1730 </pre></div>
1731
1732 <p>And that's it.  The user is now free to use <tt>-regalloc=myregalloc</tt> as
1733 an option.  Registering instruction schedulers is similar except use the
1734 <tt>RegisterScheduler</tt> class.  Note that the
1735 <tt>RegisterScheduler::FunctionPassCtor</tt> is significantly different from
1736 <tt>RegisterRegAlloc::FunctionPassCtor</tt>.</p>
1737
1738 <p>To force the load/linking of your register allocator into the llc/lli tools,
1739 add your creator function's global declaration to "Passes.h" and add a "pseudo"
1740 call line to <tt>llvm/Codegen/LinkAllCodegenComponents.h</tt>.</p>
1741
1742 </div>
1743
1744
1745 <!-- _______________________________________________________________________ -->
1746 <div class="doc_subsection">
1747   <a name="registering_new">Creating new registries</a>
1748 </div>
1749
1750 <div class="doc_text">
1751
1752 <p>The easiest way to get started is to clone one of the existing registries; we
1753 recommend <tt>llvm/CodeGen/RegAllocRegistry.h</tt>.  The key things to modify
1754 are the class name and the <tt>FunctionPassCtor</tt> type.</p>
1755
1756 <p>Then you need to declare the registry.  Example: if your pass registry is
1757 <tt>RegisterMyPasses</tt> then define;</p>
1758
1759 <div class="doc_code"><pre>
1760 MachinePassRegistry RegisterMyPasses::Registry;
1761 </pre></div>
1762
1763 <p>And finally, declare the command line option for your passes.  Example:</p>
1764
1765 <div class="doc_code"><pre>
1766   cl::opt&lt;RegisterMyPasses::FunctionPassCtor, false,
1767           RegisterPassParser&lt;RegisterMyPasses&gt; &gt;
1768   MyPassOpt("mypass",
1769             cl::init(&amp;createDefaultMyPass),
1770             cl::desc("my pass option help"));
1771 </pre></div>
1772
1773 <p>Here the command option is "mypass", with createDefaultMyPass as the default
1774 creator.</p>
1775
1776 </div>
1777
1778 <!-- *********************************************************************** -->
1779 <div class="doc_section">
1780   <a name="debughints">Using GDB with dynamically loaded passes</a>
1781 </div>
1782 <!-- *********************************************************************** -->
1783
1784 <div class="doc_text">
1785
1786 <p>Unfortunately, using GDB with dynamically loaded passes is not as easy as it
1787 should be.  First of all, you can't set a breakpoint in a shared object that has
1788 not been loaded yet, and second of all there are problems with inlined functions
1789 in shared objects.  Here are some suggestions to debugging your pass with
1790 GDB.</p>
1791
1792 <p>For sake of discussion, I'm going to assume that you are debugging a
1793 transformation invoked by <tt>opt</tt>, although nothing described here depends
1794 on that.</p>
1795
1796 </div>
1797
1798 <!-- _______________________________________________________________________ -->
1799 <div class="doc_subsubsection">
1800   <a name="breakpoint">Setting a breakpoint in your pass</a>
1801 </div>
1802
1803 <div class="doc_text">
1804
1805 <p>First thing you do is start <tt>gdb</tt> on the <tt>opt</tt> process:</p>
1806
1807 <div class="doc_code"><pre>
1808 $ <b>gdb opt</b>
1809 GNU gdb 5.0
1810 Copyright 2000 Free Software Foundation, Inc.
1811 GDB is free software, covered by the GNU General Public License, and you are
1812 welcome to change it and/or distribute copies of it under certain conditions.
1813 Type "show copying" to see the conditions.
1814 There is absolutely no warranty for GDB.  Type "show warranty" for details.
1815 This GDB was configured as "sparc-sun-solaris2.6"...
1816 (gdb)
1817 </pre></div>
1818
1819 <p>Note that <tt>opt</tt> has a lot of debugging information in it, so it takes
1820 time to load.  Be patient.  Since we cannot set a breakpoint in our pass yet
1821 (the shared object isn't loaded until runtime), we must execute the process, and
1822 have it stop before it invokes our pass, but after it has loaded the shared
1823 object.  The most foolproof way of doing this is to set a breakpoint in
1824 <tt>PassManager::run</tt> and then run the process with the arguments you
1825 want:</p>
1826
1827 <div class="doc_code"><pre>
1828 (gdb) <b>break llvm::PassManager::run</b>
1829 Breakpoint 1 at 0x2413bc: file Pass.cpp, line 70.
1830 (gdb) <b>run test.bc -load $(LLVMTOP)/llvm/Debug+Asserts/lib/[libname].so -[passoption]</b>
1831 Starting program: opt test.bc -load $(LLVMTOP)/llvm/Debug+Asserts/lib/[libname].so -[passoption]
1832 Breakpoint 1, PassManager::run (this=0xffbef174, M=@0x70b298) at Pass.cpp:70
1833 70      bool PassManager::run(Module &amp;M) { return PM-&gt;run(M); }
1834 (gdb)
1835 </pre></div>
1836
1837 <p>Once the <tt>opt</tt> stops in the <tt>PassManager::run</tt> method you are
1838 now free to set breakpoints in your pass so that you can trace through execution
1839 or do other standard debugging stuff.</p>
1840
1841 </div>
1842
1843 <!-- _______________________________________________________________________ -->
1844 <div class="doc_subsubsection">
1845   <a name="debugmisc">Miscellaneous Problems</a>
1846 </div>
1847
1848 <div class="doc_text">
1849
1850 <p>Once you have the basics down, there are a couple of problems that GDB has,
1851 some with solutions, some without.</p>
1852
1853 <ul>
1854 <li>Inline functions have bogus stack information.  In general, GDB does a
1855 pretty good job getting stack traces and stepping through inline functions.
1856 When a pass is dynamically loaded however, it somehow completely loses this
1857 capability.  The only solution I know of is to de-inline a function (move it
1858 from the body of a class to a .cpp file).</li>
1859
1860 <li>Restarting the program breaks breakpoints.  After following the information
1861 above, you have succeeded in getting some breakpoints planted in your pass.  Nex
1862 thing you know, you restart the program (i.e., you type '<tt>run</tt>' again),
1863 and you start getting errors about breakpoints being unsettable.  The only way I
1864 have found to "fix" this problem is to <tt>delete</tt> the breakpoints that are
1865 already set in your pass, run the program, and re-set the breakpoints once
1866 execution stops in <tt>PassManager::run</tt>.</li>
1867
1868 </ul>
1869
1870 <p>Hopefully these tips will help with common case debugging situations.  If
1871 you'd like to contribute some tips of your own, just contact <a
1872 href="mailto:sabre@nondot.org">Chris</a>.</p>
1873
1874 </div>
1875
1876 <!-- *********************************************************************** -->
1877 <div class="doc_section">
1878   <a name="future">Future extensions planned</a>
1879 </div>
1880 <!-- *********************************************************************** -->
1881
1882 <div class="doc_text">
1883
1884 <p>Although the LLVM Pass Infrastructure is very capable as it stands, and does
1885 some nifty stuff, there are things we'd like to add in the future.  Here is
1886 where we are going:</p>
1887
1888 </div>
1889
1890 <!-- _______________________________________________________________________ -->
1891 <div class="doc_subsubsection">
1892   <a name="SMP">Multithreaded LLVM</a>
1893 </div>
1894
1895 <div class="doc_text">
1896
1897 <p>Multiple CPU machines are becoming more common and compilation can never be
1898 fast enough: obviously we should allow for a multithreaded compiler.  Because of
1899 the semantics defined for passes above (specifically they cannot maintain state
1900 across invocations of their <tt>run*</tt> methods), a nice clean way to
1901 implement a multithreaded compiler would be for the <tt>PassManager</tt> class
1902 to create multiple instances of each pass object, and allow the separate
1903 instances to be hacking on different parts of the program at the same time.</p>
1904
1905 <p>This implementation would prevent each of the passes from having to implement
1906 multithreaded constructs, requiring only the LLVM core to have locking in a few
1907 places (for global resources).  Although this is a simple extension, we simply
1908 haven't had time (or multiprocessor machines, thus a reason) to implement this.
1909 Despite that, we have kept the LLVM passes SMP ready, and you should too.</p>
1910
1911 </div>
1912
1913 <!-- *********************************************************************** -->
1914 <hr>
1915 <address>
1916   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1917   src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
1918   <a href="http://validator.w3.org/check/referer"><img
1919   src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
1920
1921   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1922   <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1923   Last modified: $Date$
1924 </address>
1925
1926 </body>
1927 </html>