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