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