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