docs/WritingAnLLVMPass.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2 <html><head><title>Writing an LLVM Pass</title></head>
   3
   4 <body bgcolor=white>
   5
   6 <table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
   7 <tr><td>&nbsp; <font size=+3 color="#EEEEFF" face="Georgia,Palatino,Times,Roman"><b>Writing an LLVM Pass</b></font></td>
   8 </tr></table>
   9
  10
  11 <ol>
  12   <li><a href="#introduction">Introduction - What is a pass?</a>
  13   <li><a href="#quickstart">Quick Start - Writing hello world</a>
  14     <ul>
  15     <li><a href="#makefile">Setting up the build environment</a>
  16     <li><a href="#basiccode">Basic code required</a>
  17     <li><a href="#running">Running a pass with <tt>opt</tt>
  18          or <tt>analyze</tt></a>
  19     </ul>
  20   <li><a href="#passtype">Pass classes and requirements</a>
  21      <ul>
  22      <li><a href="#ImmutablePass">The <tt>ImmutablePass</tt> class</a>
  23      <li><a href="#Pass">The <tt>Pass</tt> class</a>
  24         <ul>
  25         <li><a href="#run">The <tt>run</tt> method</a>
  26         </ul>
  27      <li><a href="#FunctionPass">The <tt>FunctionPass</tt> class</a>
  28         <ul>
  29         <li><a href="#doInitialization_mod">The <tt>doInitialization(Module
  30                                             &amp;)</tt> method</a>
  31         <li><a href="#runOnFunction">The <tt>runOnFunction</tt> method</a>
  32         <li><a href="#doFinalization_mod">The <tt>doFinalization(Module
  33                                             &amp;)</tt> method</a>
  34         </ul>
  35      <li><a href="#BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
  36         <ul>
  37         <li><a href="#doInitialization_fn">The <tt>doInitialization(Function
  38                                              &amp;)</tt> method</a>
  39         <li><a href="#runOnBasicBlock">The <tt>runOnBasicBlock</tt> method</a>
  40         <li><a href="#doFinalization_fn">The <tt>doFinalization(Function
  41                                              &amp;)</tt> method</a>
  42         </ul>
  43      </ul>
  44   <li><a href="#registration">Pass Registration</a>
  45      <ul>
  46      <li><a href="#print">The <tt>print</tt> method</a>
  47      </ul>
  48   <li><a href="#interaction">Specifying interactions between passes</a>
  49      <ul>
  50      <li><a href="#getAnalysisUsage">The <tt>getAnalysisUsage</tt> method</a>
  51      <li><a href="#getAnalysis">The <tt>getAnalysis</tt> method</a>
  52      </ul>
  53   <li><a href="#analysisgroup">Implementing Analysis Groups</a>
  54      <ul>
  55      <li><a href="#agconcepts">Analysis Group Concepts</a>
  56      <li><a href="#registerag">Using <tt>RegisterAnalysisGroup</tt></a>
  57      </ul>
  58   <li><a href="#passmanager">What PassManager does</a>
  59     <ul>
  60     <li><a href="#releaseMemory">The <tt>releaseMemory</tt> method</a>
  61     </ul>
  62   <li><a href="#debughints">Using GDB with dynamically loaded passes</a>
  63     <ul>
  64     <li><a href="#breakpoint">Setting a breakpoint in your pass
  65     <li><a href="#debugmisc">Miscellaneous Problems
  66     </ul>
  67   <li><a href="#future">Future extensions planned</a>
  68     <ul>
  69     <li><a href="#SMP">Multithreaded LLVM</a>
  70     <li><a href="#ModuleSource">A new <tt>ModuleSource</tt> interface</a>
  71     <li><a href="#PassFunctionPass"><tt>Pass</tt>'s requiring <tt>FunctionPass</tt>'s</a>
  72     </ul>
  73
  74   <p><b>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></b><p>
  75 </ol><p>
  76
  77
  78
  79 <!-- *********************************************************************** -->
  80 <table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
  81 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
  82 <a name="introduction">Introduction - What is a pass?
  83 </b></font></td></tr></table><ul>
  84 <!-- *********************************************************************** -->
  85
  86 The LLVM Pass Framework is an important part of the LLVM system, because LLVM
  87 passes are where the interesting parts of the compiler exist.  Passes perform
  88 the transformations and optimizations that make up the compiler, they build
  89 the analysis results that are used by these transformations, and they are, above
  90 all, a structuring technique for compiler code.<p>
  91
  92 All LLVM passes are subclasses of the <tt><a
  93 href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt> class, which
  94 implement functionality by overriding virtual methods inherited from
  95 <tt>Pass</tt>.  Depending on how your pass works, you may be able to inherit
  96 from the <tt><a
  97 href="http://llvm.cs.uiuc.edu/doxygen/structFunctionPass.html">FunctionPass</a></tt>
  98 or <tt><a
  99 href="http://llvm.cs.uiuc.edu/doxygen/structBasicBlockPass.html">BasicBlockPass</a></tt>,
 100 which gives the system more information about what your pass does, and how it
 101 can be combined with other passes.  One of the main features of the LLVM Pass
 102 Framework is that it schedules passes to run in an efficient way based on the
 103 constraints that your pass has.<p>
 104
 105 We start by showing you how to construct a pass, everything from setting up the
 106 code, to compiling, loading, and executing it.  After the basics are down, more
 107 advanced features are discussed.<p>
 108
 109
 110 <!-- *********************************************************************** -->
 111 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
 112 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
 113 <a name="quickstart">Quick Start - Writing hello world
 114 </b></font></td></tr></table><ul>
 115 <!-- *********************************************************************** -->
 116
 117 Here we describe how to write the "hello world" of passes.  The "Hello" pass is
 118 designed to simply print out the name of non-external functions that exist in
 119 the program being compiled.  It does not modify the program at all, just
 120 inspects it.  The source code and files for this pass are available in the LLVM
 121 source tree in the <tt>lib/Transforms/Hello</tt> directory.<p>
 122
 123
 124 <!-- ======================================================================= -->
 125 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 126 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 127 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 128 <a name="makefile">Setting up the build environment
 129 </b></font></td></tr></table><ul>
 130
 131 First thing you need to do is create a new directory somewhere in the LLVM
 132 source base.  For this example, we'll assume that you made
 133 "<tt>lib/Transforms/Hello</tt>".  The first thing you must do is set up a build
 134 script (Makefile) that will compile the source code for the new pass.  To do
 135 this, copy this into "<tt>Makefile</tt>":<p>
 136
 137 </ul><hr><ul><pre>
 138 # Makefile for hello pass
 139
 140 # Path to top level of LLVM heirarchy
 141 LEVEL = ../../..
 142
 143 # Name of the library to build
 144 LIBRARYNAME = hello
 145
 146 # Build a dynamically loadable shared object
 147 SHARED_LIBRARY = 1
 148
 149 # Include the makefile implementation stuff
 150 include $(LEVEL)/Makefile.common
 151 </pre></ul><hr><ul><p>
 152
 153 This makefile specifies that all of the <tt>.cpp</tt> files in the current
 154 directory are to be compiled and linked together into a
 155 <tt>lib/Debug/libhello.so</tt> shared object that can be dynamically loaded by
 156 the <tt>opt</tt> or <tt>analyze</tt> tools.<p>
 157
 158 Now that we have the build scripts set up, we just need to write the code for
 159 the pass itself.<p>
 160
 161
 162 <!-- ======================================================================= -->
 163 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 164 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 165 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 166 <a name="basiccode">Basic code required
 167 </b></font></td></tr></table><ul>
 168
 169 Now that we have a way to compile our new pass, we just have to write it.  Start
 170 out with:<p>
 171
 172 <pre>
 173 <b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
 174 <b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Function_8h-source.html">llvm/Function.h</a>"
 175 </pre>
 176
 177 Which are needed because we are writing a <tt><a
 178 href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt>, and we are
 179 operating on <tt><a
 180 href="http://llvm.cs.uiuc.edu/doxygen/classFunction.html">Function</a></tt>'s.<p>
 181
 182 Next we have:<p>
 183
 184 <pre>
 185 <b>namespace</b> {
 186 </pre><p>
 187
 188 ... which starts out an anonymous namespace.  Anonymous namespaces are to C++
 189 what the "<tt>static</tt>" keyword is to C (at global scope).  It makes the
 190 things declared inside of the anonymous namespace only visible to the current
 191 file.  If you're not familiar with them, consult a decent C++ book for more
 192 information.<p>
 193
 194 Next, we declare our pass itself:<p>
 195
 196 <pre>
 197   <b>struct</b> Hello : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
 198 </pre><p>
 199
 200 This declares a "<tt>Hello</tt>" class that is a subclass of <tt><a
 201 href="http://llvm.cs.uiuc.edu/doxygen/structFunctionPass.html">FunctionPass</a></tt>.
 202 The different builtin pass subclasses are described in detail <a
 203 href="#passtype">later</a>, but for now, know that <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s
 204 operate a function at a time.<p>
 205
 206 <pre>
 207     <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &F) {
 208       std::cerr &lt;&lt; "<i>Hello: </i>" &lt;&lt; F.getName() &lt;&lt; "\n";
 209       <b>return false</b>;
 210     }
 211   };  <i>// end of struct Hello</i>
 212 </pre>
 213
 214 We declare a "<a href="#runOnFunction"><tt>runOnFunction</tt></a>" method, which
 215 overloads an abstract virtual method inherited from <a
 216 href="#FunctionPass"><tt>FunctionPass</tt></a>.  This is where we are supposed
 217 to do our thing, so we just print out our message with the name of each
 218 function.<p>
 219
 220 <pre>
 221   RegisterOpt&lt;Hello&gt; X("<i>hello</i>", "<i>Hello World Pass</i>");
 222 }  <i>// end of anonymous namespace</i>
 223 </pre><p>
 224
 225 Lastly, we register our class <tt>Hello</tt>, giving it a command line argument
 226 "<tt>hello</tt>", and a name "<tt>Hello World Pass</tt>".  There are several
 227 different ways of <a href="#registration">registering your pass</a>, depending
 228 on what it is to be used for.  For "optimizations" we use the
 229 <tt>RegisterOpt</tt> template.<p>
 230
 231 As a whole, the <tt>.cpp</tt> file looks like:<p>
 232
 233 <pre>
 234 <b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
 235 <b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Function_8h-source.html">llvm/Function.h</a>"
 236
 237 <b>namespace</b> {
 238   <b>struct Hello</b> : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
 239     <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &F) {
 240       std::cerr &lt;&lt; "<i>Hello: </i>" &lt;&lt; F.getName() &lt;&lt; "\n";
 241       <b>return false</b>;
 242     }
 243   };
 244
 245   RegisterOpt&lt;Hello&gt; X("<i>hello</i>", "<i>Hello World Pass</i>");
 246 }
 247 </pre><p>
 248
 249 Now that it's all together, compile the file with a simple "<tt>gmake</tt>"
 250 command in the local directory and you should get a new
 251 "<tt>lib/Debug/libhello.so</tt> file.  Note that everything in this file is
 252 contained in an anonymous namespace: this reflects the fact that passes are self
 253 contained units that do not need external interfaces (although they can have
 254 them) to be useful.<p>
 255
 256
 257 <!-- ======================================================================= -->
 258 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 259 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 260 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 261 <a name="running">Running a pass with <tt>opt</tt> or <tt>analyze</tt>
 262 </b></font></td></tr></table><ul>
 263
 264 Now that you have a brand new shiny <tt>.so</tt> file, we can use the
 265 <tt>opt</tt> command to run an LLVM program through your pass.  Because you
 266 registered your pass with the <tt>RegisterOpt</tt> template, you will be able to
 267 use the <tt>opt</tt> tool to access it, once loaded.<p>
 268
 269 To test it, follow the example at the end of the <a
 270 href="GettingStarted.html">Getting Started Guide</a> to compile "Hello World" to
 271 LLVM.  We can now run the bytecode file (<tt>hello.bc</tt>) for the program
 272 through our transformation like this (or course, any bytecode file will
 273 work):<p>
 274
 275 <pre>
 276 $ opt -load ../../../lib/Debug/libhello.so -hello &lt; hello.bc &gt; /dev/null
 277 Hello: __main
 278 Hello: puts
 279 Hello: main
 280 </pre><p>
 281
 282 The '<tt>-load</tt>' option specifies that '<tt>opt</tt>' should load your pass
 283 as a shared object, which makes '<tt>-hello</tt>' a valid command line argument
 284 (which is one reason you need to <a href="#registration">register your
 285 pass</a>).  Because the hello pass does not modify the program in any
 286 interesting way, we just throw away the result of <tt>opt</tt> (sending it to
 287 <tt>/dev/null</tt>).<p>
 288
 289 To see what happened to the other string you registered, try running
 290 <tt>opt</tt> with the <tt>--help</tt> option:<p>
 291
 292 <pre>
 293 $ opt -load ../../../lib/Debug/libhello.so --help
 294 OVERVIEW: llvm .bc -&gt; .bc modular optimizer
 295
 296 USAGE: opt [options] &lt;input bytecode&gt;
 297
 298 OPTIONS:
 299   Optimizations available:
 300 ...
 301     -funcresolve    - Resolve Functions
 302     -gcse           - Global Common Subexpression Elimination
 303     -globaldce      - Dead Global Elimination
 304     <b>-hello          - Hello World Pass</b>
 305     -indvars        - Cannonicalize Induction Variables
 306     -inline         - Function Integration/Inlining
 307     -instcombine    - Combine redundant instructions
 308 ...
 309 </pre><p>
 310
 311 The pass name get added as the information string for your pass, giving some
 312 documentation to users of <tt>opt</tt>.  Now that you have a working pass, you
 313 would go ahead and make it do the cool transformations you want.  Once you get
 314 it all working and tested, it may become useful to find out how fast your pass
 315 is.  The <a href="#passManager"><tt>PassManager</tt></a> provides a nice command
 316 line option (<tt>--time-passes</tt>) that allows you to get information about
 317 the execution time of your pass along with the other passes you queue up.  For
 318 example:<p>
 319
 320 <pre>
 321 $ opt -load ../../../lib/Debug/libhello.so -hello -time-passes &lt; hello.bc &gt; /dev/null
 322 Hello: __main
 323 Hello: puts
 324 Hello: main
 325 ===============================================================================
 326                       ... Pass execution timing report ...
 327 ===============================================================================
 328   Total Execution Time: 0.02 seconds (0.0479059 wall clock)
 329
 330    ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Pass Name ---
 331    0.0100 (100.0%)   0.0000 (  0.0%)   0.0100 ( 50.0%)   0.0402 ( 84.0%)  Bytecode Writer
 332    0.0000 (  0.0%)   0.0100 (100.0%)   0.0100 ( 50.0%)   0.0031 (  6.4%)  Dominator Set Construction
 333    0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0013 (  2.7%)  Module Verifier
 334  <b>  0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0033 (  6.9%)  Hello World Pass</b>
 335    0.0100 (100.0%)   0.0100 (100.0%)   0.0200 (100.0%)   0.0479 (100.0%)  TOTAL
 336 </pre><p>
 337
 338 As you can see, our implementation above is pretty fast :).  The additional
 339 passes listed are automatically inserted by the '<tt>opt</tt>' tool to verify
 340 that the LLVM emitted by your pass is still valid and well formed LLVM, which
 341 hasn't been broken somehow.
 342
 343 Now that you have seen the basics of the mechanics behind passes, we can talk
 344 about some more details of how they work and how to use them.<p>
 345
 346
 347
 348 <!-- *********************************************************************** -->
 349 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
 350 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
 351 <a name="passtype">Pass classes and requirements
 352 </b></font></td></tr></table><ul>
 353 <!-- *********************************************************************** -->
 354
 355 One of the first things that you should do when designing a new pass is to
 356 decide what class you should subclass for your pass.  The <a
 357 href="#basiccode">Hello World</a> example uses the <tt><a
 358 href="#FunctionPass">FunctionPass</a></tt> class for its implementation, but we
 359 did not discuss why or when this should occur.  Here we talk about the classes
 360 available, from the most general to the most specific.<p>
 361
 362 When choosing a superclass for your Pass, you should choose the <b>most
 363 specific</b> class possible, while still being able to meet the requirements
 364 listed.  This gives the LLVM Pass Infrastructure information neccesary to
 365 optimize how passes are run, so that the resultant compiler isn't unneccesarily
 366 slow.<p>
 367
 368
 369 <!-- ======================================================================= -->
 370 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 371 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 372 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 373 <a name="ImmutablePass">The <tt>ImmutablePass</tt> class
 374 </b></font></td></tr></table><ul>
 375
 376 The most plain and boring type of pass is the "<tt><a
 377 href="http://llvm.cs.uiuc.edu/doxygen/structImmutablePass.html">ImmutablePass</a></tt>"
 378 class.  This pass type is used for passes that do not have to be run, do not
 379 change state, and never need to be updated.  This is not a normal type of
 380 transformation or analysis, but can provide information about the current
 381 compiler configuration.<p>
 382
 383 Although this pass class is very infrequently used, it is important for
 384 providing information about the current target machine being compiled for, and
 385 other static information that can affect the various transformations.<p>
 386
 387 <tt>ImmutablePass</tt>'s never invalidate other transformations, are never
 388 invalidated, and are never "run".<p>
 389
 390
 391 <!-- ======================================================================= -->
 392 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 393 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 394 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 395 <a name="Pass">The <tt>Pass</tt> class
 396 </b></font></td></tr></table><ul>
 397
 398 The "<tt><a href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt>"
 399 class is the most general of all superclasses that you can use.  Deriving from
 400 <tt>Pass</tt> indicates that your pass uses the entire program as a unit,
 401 refering to function bodies in no predictable order, or adding and removing
 402 functions.  Because nothing is known about the behavior of direct <tt>Pass</tt>
 403 subclasses, no optimization can be done for their execution.<p>
 404
 405 To write a correct <tt>Pass</tt> subclass, derive from <tt>Pass</tt> and
 406 overload the <tt>run</tt> method with the following signature:<p>
 407
 408 <!-- _______________________________________________________________________ -->
 409 </ul><h4><a name="run"><hr size=0>The <tt>run</tt> method</h4><ul>
 410
 411
 412 <pre>
 413   <b>virtual bool</b> run(Module &amp;M) = 0;
 414 </pre><p>
 415
 416 The <tt>run</tt> method performs the interesting work of the pass, and should
 417 return true if the module was modified by the transformation, false
 418 otherwise.<p>
 419
 420
 421
 422 <!-- ======================================================================= -->
 423 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 424 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 425 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 426 <a name="FunctionPass">The <tt>FunctionPass</tt> class
 427 </b></font></td></tr></table><ul>
 428
 429 In contrast to direct <tt>Pass</tt> subclasses, direct <tt><a
 430 href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">FunctionPass</a></tt>
 431 subclasses do have a predictable, local behavior that can be expected by the
 432 system.  All <tt>FunctionPass</tt> execute on each function in the program
 433 independant of all of the other functions in the program.
 434 <tt>FunctionPass</tt>'s do not require that they are executed in a particular
 435 order, and <tt>FunctionPass</tt>'s do not modify external functions.<p>
 436
 437 To be explicit, <tt>FunctionPass</tt> subclasses are not allowed to:<p>
 438
 439 <ol>
 440 <li>Modify a Function other than the one currently being processed.
 441 <li>Add or remove Function's from the current Module.
 442 <li>Add or remove global variables from the current Module.
 443 <li>Maintain state across invocations of
 444     <a href="#runOnFunction"><tt>runOnFunction</tt></a> (including global data)
 445 </ol><p>
 446
 447 Implementing a <tt>FunctionPass</tt> is usually straightforward (See the <a
 448 href="#basiccode">Hello World</a> pass for example).  <tt>FunctionPass</tt>'s
 449 may overload three virtual methods to do their work.  All of these methods
 450 should return true if they modified the program, or false if they didn't.<p>
 451
 452 <!-- _______________________________________________________________________ -->
 453 </ul><h4><a name="doInitialization_mod"><hr size=0>The
 454 <tt>doInitialization(Module &amp;)</tt> method</h4><ul>
 455
 456 <pre>
 457   <b>virtual bool</b> doInitialization(Module &amp;M);
 458 </pre><p>
 459
 460 The <tt>doIninitialize</tt> method is allowed to do most of the things that
 461 <tt>FunctionPass</tt>'s are not allowed to do.  They can add and remove
 462 functions, get pointers to functions, etc.  The <tt>doInitialization</tt> method
 463 is designed to do simple initialization type of stuff that does not depend on
 464 the functions being processed.  The <tt>doInitialization</tt> method call is not
 465 scheduled to overlap with any other pass executions (thus it should be very
 466 fast).<p>
 467
 468 A good example of how this method should be used is the <a
 469 href="http://llvm.cs.uiuc.edu/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations</a>
 470 pass.  This pass converts <tt>malloc</tt> and <tt>free</tt> instructions into
 471 platform dependant <tt>malloc()</tt> and <tt>free()</tt> function calls.  It
 472 uses the <tt>doInitialization</tt> method to get a reference to the malloc and
 473 free functions that it needs, adding prototypes to the module if neccesary.<p>
 474
 475 <!-- _______________________________________________________________________ -->
 476 </ul><h4><a name="runOnFunction"><hr size=0>The <tt>runOnFunction</tt> method</h4><ul>
 477
 478 <pre>
 479   <b>virtual bool</b> runOnFunction(Function &amp;F) = 0;
 480 </pre><p>
 481
 482 The <tt>runOnFunction</tt> method must be implemented by your subclass to do the
 483 transformation or analysis work of your pass.  As usual, a true value should be
 484 returned if the function is modified.<p>
 485
 486 <!-- _______________________________________________________________________ -->
 487 </ul><h4><a name="doFinalization_mod"><hr size=0>The <tt>doFinalization(Module &amp;)</tt> method</h4><ul>
 488
 489 <pre>
 490   <b>virtual bool</b> doFinalization(Module &amp;M);
 491 </pre</p>
 492
 493 The <tt>doFinalization</tt> method is an infrequently used method that is called
 494 when the pass framework has finished calling <a
 495 href="#runOnFunction"><tt>runOnFunction</tt></a> for every function in the
 496 program being compiled.<p>
 497
 498
 499
 500 <!-- ======================================================================= -->
 501 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 502 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 503 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 504 <a name="BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
 505 </b></font></td></tr></table><ul>
 506
 507 <tt>BasicBlockPass</tt>'s are just like <a
 508 href="#FunctionPass"><tt>FunctionPass</tt></a>'s, except that they must limit
 509 their scope of inspection and modification to a single basic block at a time.
 510 As such, they are <b>not</b> allowed to do any of the following:<p>
 511
 512 <ol>
 513 <li>Modify or inspect any basic blocks outside of the current one
 514 <li>Maintain state across invocations of
 515     <a href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a>
 516 <li>Modify the constrol flow graph (by altering terminator instructions)
 517 <li>Any of the things verboten for
 518     <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s.
 519 </ol><p>
 520
 521 <tt>BasicBlockPass</tt>'s are useful for traditional local and "peephole"
 522 optimizations.  They may override the same <a
 523 href="#doInitialization_mod"><tt>doInitialization(Module &amp;)</tt></a> and <a
 524 href="#doFinalization_mod"><tt>doFinalization(Module &amp;)</tt></a> methods that <a
 525 href="#FunctionPass"><tt>FunctionPass</tt></a>'s have, but also have the following virtual methods that may also be implemented:<p>
 526
 527 <!-- _______________________________________________________________________ -->
 528 </ul><h4><a name="doInitialization_fn"><hr size=0>The
 529 <tt>doInitialization(Function &amp;)</tt> method</h4><ul>
 530
 531 <pre>
 532   <b>virtual bool</b> doInitialization(Function &amp;F);
 533 </pre><p>
 534
 535 The <tt>doIninitialize</tt> method is allowed to do most of the things that
 536 <tt>BasicBlockPass</tt>'s are not allowed to do, but that
 537 <tt>FunctionPass</tt>'s can.  The <tt>doInitialization</tt> method is designed
 538 to do simple initialization type of stuff that does not depend on the
 539 BasicBlocks being processed.  The <tt>doInitialization</tt> method call is not
 540 scheduled to overlap with any other pass executions (thus it should be very
 541 fast).<p>
 542
 543
 544 <!-- _______________________________________________________________________ -->
 545 </ul><h4><a name="runOnBasicBlock"><hr size=0>The <tt>runOnBasicBlock</tt> method</h4><ul>
 546
 547 <pre>
 548   <b>virtual bool</b> runOnBasicBlock(BasicBlock &amp;BB) = 0;
 549 </pre><p>
 550
 551 Override this function to do the work of the <tt>BasicBlockPass</tt>.  This
 552 function is not allowed to inspect or modify basic blocks other than the
 553 parameter, and are not allowed to modify the CFG.  A true value must be returned
 554 if the basic block is modified.<p>
 555
 556
 557 <!-- _______________________________________________________________________ -->
 558 </ul><h4><a name="doFinalization_fn"><hr size=0>The <tt>doFinalization(Function
 559 &amp;)</tt> method</h4><ul>
 560
 561 <pre>
 562   <b>virtual bool</b> doFinalization(Function &amp;F);
 563 </pre</p>
 564
 565 The <tt>doFinalization</tt> method is an infrequently used method that is called
 566 when the pass framework has finished calling <a
 567 href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a> for every BasicBlock in the
 568 program being compiled.  This can be used to perform per-function
 569 finalization.<p>
 570
 571
 572
 573 <!-- *********************************************************************** -->
 574 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
 575 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
 576 <a name="registration">Pass registration
 577 </b></font></td></tr></table><ul>
 578 <!-- *********************************************************************** -->
 579
 580 In the <a href="#basiccode">Hello World</a> example pass we illustrated how pass
 581 registration works, and discussed some of the reasons that it is used and what
 582 it does.  Here we discuss how and why passes are registered.<p>
 583
 584 Passes can be registered in several different ways.  Depending on the general
 585 classification of the pass, you should use one of the following templates to
 586 register the pass:<p>
 587
 588 <ul>
 589 <li><b><tt>RegisterOpt</tt></b> - This template should be used when you are
 590 registering a pass that logically should be available for use in the
 591 '<tt>opt</tt>' utility.<p>
 592
 593 <li><b><tt>RegisterAnalysis</tt></b> - This template should be used when you are
 594 registering a pass that logically should be available for use in the
 595 '<tt>analysis</tt>' utility.<p>
 596
 597 <li><b><tt>RegisterLLC</tt></b> - This template should be used when you are
 598 registering a pass that logically should be available for use in the
 599 '<tt>llc</tt>' utility.<p>
 600
 601 <li><b><tt>RegisterPass</tt></b> - This is the generic form of the
 602 <tt>Register*</tt> templates that should be used if you want your pass listed by
 603 multiple or no utilities.  This template takes an extra third argument that
 604 specifies which tools it should be listed in.  See the <a
 605 href="http://llvm.cs.uiuc.edu/doxygen/PassSupport_8h-source.html">PassSupport.h</a>
 606 file for more information.<p>
 607 </ul><p>
 608
 609 Regardless of how you register your pass, you must specify at least two
 610 parameters.  The first parameter is the name of the pass that is to be used on
 611 the command line to specify that the pass should be added to a program (for
 612 example <tt>opt</tt> or <tt>analyze</tt>).  The second argument is the name of
 613 the pass, which is to be used for the <tt>--help</tt> output of programs, as
 614 well as for debug output generated by the <tt>--debug-pass</tt> option.<p>
 615
 616 If you pass is constructed by its default constructor, you only ever have to
 617 pass these two arguments.  If, on the other hand, you require other information
 618 (like target specific information), you must pass an additional argument.  This
 619 argument is a pointer to a function used to create the pass.  For an example of
 620 how this works, look at the <a
 621 href="http://llvm.cs.uiuc.edu/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations.cpp</a>
 622 file.<p>
 623
 624 If a pass is registered to be used by the <tt>analyze</tt> utility, you should
 625 implement the virtual <tt>print</tt> method:<p>
 626
 627 <!-- _______________________________________________________________________ -->
 628 </ul><h4><a name="print"><hr size=0>The <tt>print</tt> method</h4><ul>
 629
 630 <pre>
 631   <b>virtual void</b> print(std::ostream &amp;O, <b>const</b> Module *M) <b>const</b>;
 632 </pre><p>
 633
 634 The <tt>print</tt> method must be implemented by "analyses" in order to print a
 635 human readable version of the analysis results.  This is useful for debugging an
 636 analysis itself, as well as for other people to figure out how an analysis
 637 works.  The <tt>analyze</tt> tool uses this method to generate its output.<p>
 638
 639 The <tt>ostream</tt> parameter specifies the stream to write the results on, and
 640 the <tt>Module</tt> parameter gives a pointer to the top level module of the
 641 program that has been analyzed.  Note however that this pointer may be null in
 642 certain circumstances (such as calling the <tt>Pass::dump()</tt> from a
 643 debugger), so it should only be used to enhance debug output, it should not be
 644 depended on.<p>
 645
 646
 647 <!-- *********************************************************************** -->
 648 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
 649 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
 650 <a name="interaction">Specifying interactions between passes
 651 </b></font></td></tr></table><ul>
 652 <!-- *********************************************************************** -->
 653
 654 One of the main responsibilities of the <tt>PassManager</tt> is the make sure
 655 that passes interact with each other correctly.  Because <tt>PassManager</tt>
 656 tries to <a href="#passmanager">optimize the execution of passes</a> it must
 657 know how the passes interact with each other and what dependencies exist between
 658 the various passes.  To track this, each pass can declare the set of passes that
 659 are required to be executed before the current pass, and the passes which are
 660 invalidated by the current pass.<p>
 661
 662 Typically this functionality is used to require that analysis results are
 663 computed before your pass is run.  Running arbitrary transformation passes can
 664 invalidate the computed analysis results, which is what the invalidation set
 665 specifies.  If a pass does not implement the <tt><a
 666 href="#getAnalysisUsage">getAnalysisUsage</a></tt> method, it defaults to not
 667 having any prerequisite passes, and invalidating <b>all</b> other passes.<p>
 668
 669
 670 <!-- _______________________________________________________________________ -->
 671 </ul><h4><a name="getAnalysisUsage"><hr size=0>The <tt>getAnalysisUsage</tt> method</h4><ul>
 672
 673 <pre>
 674   <b>virtual void</b> getAnalysisUsage(AnalysisUsage &amp;Info) <b>const</b>;
 675 </pre><p>
 676
 677 By implementing the <tt>getAnalysisUsage</tt> method, the required and
 678 invalidated sets may be specified for your transformation.  The implementation
 679 should fill in the <tt><a
 680 href="http://llvm.cs.uiuc.edu/doxygen/classAnalysisUsage.html">AnalysisUsage</a></tt>
 681 object with information about which passes are required and not invalidated.  To do this, the following set methods are provided by the <tt><a
 682 href="http://llvm.cs.uiuc.edu/doxygen/classAnalysisUsage.html">AnalysisUsage</a></tt> class:<p>
 683
 684 <pre>
 685   <i>// addRequires - Add the specified pass to the required set for your pass.</i>
 686   <b>template</b>&lt;<b>class</b> PassClass&gt;
 687   AnalysisUsage &amp;AnalysisUsage::addRequired();
 688
 689   <i>// addPreserved - Add the specified pass to the set of analyses preserved by
 690   // this pass</i>
 691   <b>template</b>&lt;<b>class</b> PassClass&gt;
 692   AnalysisUsage &amp;AnalysisUsage::addPreserved();
 693
 694   <i>// setPreservesAll - Call this if the pass does not modify its input at all</i>
 695   <b>void</b> AnalysisUsage::setPreservesAll();
 696
 697   <i>// setPreservesCFG - This function should be called by the pass, iff they do not:
 698   //
 699   //  1. Add or remove basic blocks from the function
 700   //  2. Modify terminator instructions in any way.
 701   //
 702   //  This is automatically implied for <a href="#BasicBlockPass">BasicBlockPass</a>'s
 703   //</i>
 704   <b>void</b> AnalysisUsage::setPreservesCFG();
 705 </pre><p>
 706
 707 Some examples of how to use these methods are:<p>
 708
 709 <pre>
 710   <i>// This is an example implementation from an analysis, which does not modify
 711   // the program at all, yet has a prerequisite.</i>
 712   <b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/structPostDominanceFrontier.html">PostDominanceFrontier</a>::getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
 713     AU.setPreservesAll();
 714     AU.addRequired&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structPostDominatorTree.html">PostDominatorTree</a>&gt;();
 715   }
 716 </pre><p>
 717
 718 and:<p>
 719
 720 <pre>
 721   <i>// This example modifies the program, but does not modify the CFG</i>
 722   <b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/structLICM.html">LICM</a>::getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
 723     AU.setPreservesCFG();
 724     AU.addRequired&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/classLoopInfo.html">LoopInfo</a>&gt;();
 725   }
 726 </pre><p>
 727
 728 <!-- _______________________________________________________________________ -->
 729 </ul><h4><a name="getAnalysis"><hr size=0>The <tt>getAnalysis&lt;&gt;</tt> method</h4><ul>
 730
 731 The <tt>Pass::getAnalysis&lt;&gt;</tt> method is inherited by your class,
 732 providing you with access to the passes that you declared that you required with
 733 the <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method.  It takes
 734 a single template argument that specifies which pass class you want, and returns
 735 a reference to that pass.<p>
 736
 737 <pre>
 738   <b>template</b>&lt;<b>typename</b> PassClass&gt;
 739   AnalysisType &amp;getAnalysis();
 740 </pre><p>
 741
 742 This method call returns a reference to the pass desired.  You may get a runtime
 743 assertion failure if you attempt to get an analysis that you did not declare as
 744 required in your <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a>
 745 implementation.  This method can be called by your <tt>run*</tt> method
 746 implementation, or by any other local method invoked by your <tt>run*</tt>
 747 method.<p>
 748
 749 <!-- *********************************************************************** -->
 750 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
 751 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
 752 <a name="analysisgroup">Implementing Analysis Groups
 753 </b></font></td></tr></table><ul>
 754 <!-- *********************************************************************** -->
 755
 756 Now that we understand the basics of how passes are defined, how the are used,
 757 and how they are required from other passes, it's time to get a little bit
 758 fancier.  All of the pass relationships that we have seen so far are very
 759 simple: one pass depends on one other specific pass to be run before it can run.
 760 For many applications, this is great, for others, more flexibility is
 761 required.<p>
 762
 763 In particular, some analyses are defined such that there is a single simple
 764 interface to the analysis results, but multiple ways of calculating them.
 765 Consider alias analysis for example.  The most trivial alias analysis returns
 766 "may alias" for any alias query.  The most sophisticated analysis a
 767 flow-sensitive, context-sensitive interprocedural analysis that can take a
 768 significant amount of time to execute (and obviously, there is a lot of room
 769 between these two extremes for other implementations).  To cleanly support
 770 situations like this, the LLVM Pass Infrastructure supports the notion of
 771 Analysis Groups.<p>
 772
 773 <!-- _______________________________________________________________________ -->
 774 </ul><h4><a name="agconcepts"><hr size=0>Analysis Group Concepts</h4><ul>
 775
 776 An Analysis Group is a single simple interface that may be implemented by
 777 multiple different passes.  Analysis Groups can be given human readable names
 778 just like passes, but unlike passes, they need not derive from the <tt>Pass</tt>
 779 class.  An analysis group may have one or more implementations, one of which is
 780 the "default" implementation.<p>
 781
 782 Analysis groups are used by client passes just like other passes are: the
 783 <tt>AnalysisUsage::addRequired()</tt> and <tt>Pass::getAnalysis()</tt> methods.
 784 In order to resolve this requirement, the <a href="#passmanager">PassManager</a>
 785 scans the available passes to see if any implementations of the analysis group
 786 are available.  If none is available, the default implementation is created for
 787 the pass to use.  All standard rules for <A href="#interaction">interaction
 788 between passes</a> still apply.<p>
 789
 790 Although <a href="#registration">Pass Registration</a> is optional for normal
 791 passes, all analysis group implementations must be registered, and must use the
 792 <A href="#registerag"><tt>RegisterAnalysisGroup</tt></a> template to join the
 793 implementation pool.  Also, a default implementation of the interface
 794 <b>must</b> be registered with <A
 795 href="#registerag"><tt>RegisterAnalysisGroup</tt></a>.<p>
 796
 797 As a concrete example of an Analysis Group in action, consider the <a
 798 href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a>
 799 analysis group.  The default implementation of the alias analysis interface (the
 800 <tt><a
 801 href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">basicaa</a></tt>
 802 pass) just does a few simple checks that don't require significant analysis to
 803 compute (such as: two different globals can never alias each other, etc).
 804 Passes that use the <tt><a
 805 href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a></tt>
 806 interface (for example the <tt><a
 807 href="http://llvm.cs.uiuc.edu/doxygen/classGCSE.html">gcse</a></tt> pass), do not care which implementation
 808 of alias analysis is actually provided, they just use the designated
 809 interface.<p>
 810
 811 From the user's perspective, commands work just like normal.  Issuing the
 812 command '<tt>opt -gcse ...</tt>' will cause the <tt>basicaa</tt> class to be
 813 instantiated and added to the pass sequence.  Issuing the command '<tt>opt
 814 -somefancyaa -gcse ...</tt>' will cause the <tt>gcse</tt> pass to use the
 815 <tt>somefancyaa</tt> alias analysis (which doesn't actually exist, it's just a
 816 hypothetical example) instead.<p>
 817
 818
 819 <!-- _______________________________________________________________________ -->
 820 </ul><h4><a name="registerag"><hr size=0>Using <tt>RegisterAnalysisGroup</tt></h4><ul>
 821
 822 The <tt>RegisterAnalysisGroup</tt> template is used to register the analysis
 823 group itself as well as add pass implementations to the analysis group.  First,
 824 an analysis should be registered, with a human readable name provided for it.
 825 Unlike registration of passes, there is no command line argument to be specified
 826 for the Analysis Group Interface itself, because it is "abstract":<p>
 827
 828 <pre>
 829   <b>static</b> RegisterAnalysisGroup&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a>&gt; A("<i>Alias Analysis</i>");
 830 </pre><p>
 831
 832 Once the analysis is registered, passes can declare that they are valid
 833 implementations of the interface by using the following code:<p>
 834
 835 <pre>
 836 <b>namespace</b> {
 837   //<i> Analysis Group implementations <b>must</b> be registered normally...</i>
 838   RegisterOpt&lt;FancyAA&gt;
 839   B("<i>somefancyaa</i>", "<i>A more complex alias analysis implementation</i>");
 840
 841   //<i> Declare that we implement the AliasAnalysis interface</i>
 842   RegisterAnalysisGroup&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a>, FancyAA&gt; C;
 843 }
 844 </pre><p>
 845
 846 This just shows a class <tt>FancyAA</tt> that is registered normally, then uses
 847 the <tt>RegisterAnalysisGroup</tt> template to "join" the <tt><a
 848 href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a></tt>
 849 analysis group.  Every implementation of an analysis group should join using
 850 this template.  A single pass may join multiple different analysis groups with
 851 no problem.<p>
 852
 853 <pre>
 854 <b>namespace</b> {
 855   //<i> Analysis Group implementations <b>must</b> be registered normally...</i>
 856   RegisterOpt&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a>&gt;
 857   D("<i>basicaa</i>", "<i>Basic Alias Analysis (default AA impl)</i>");
 858
 859   //<i> Declare that we implement the AliasAnalysis interface</i>
 860   RegisterAnalysisGroup&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a>, <a href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a>, <b>true</b>&gt; E;
 861 }
 862 </pre><p>
 863
 864 Here we show how the default implementation is specified (using the extra
 865 argument to the <tt>RegisterAnalysisGroup</tt> template).  There must be exactly
 866 one default implementation available at all times for an Analysis Group to be
 867 used.  Here we declare that the <tt><a
 868 href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a></tt>
 869 pass is the default implementation for the interface.<p>
 870
 871
 872 <!-- *********************************************************************** -->
 873 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
 874 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
 875 <a name="passmanager">What PassManager does
 876 </b></font></td></tr></table><ul>
 877 <!-- *********************************************************************** -->
 878
 879 The <a
 880 href="http://llvm.cs.uiuc.edu/doxygen/PassManager_8h-source.html"><tt>PassManager</tt></a>
 881 <a href="http://llvm.cs.uiuc.edu/doxygen/classPassManager.html">class</a> takes
 882 a list of passes, ensures their <a href="#interaction">prerequisites</a> are set
 883 up correctly, and then schedules passes to run efficiently.  All of the LLVM
 884 tools that run passes use the <tt>PassManager</tt> for execution of these
 885 passes.<p>
 886
 887 The <tt>PassManager</tt> does two main things to try to reduce the execution
 888 time of a series of passes:<p>
 889
 890 <ol>
 891 <li><b>Share analysis results</b> - The PassManager attempts to avoid
 892 recomputing analysis results as much as possible.  This means keeping track of
 893 which analyses are available already, which analyses get invalidated, and which
 894 analyses are needed to be run for a pass.  An important part of work is that the
 895 <tt>PassManager</tt> tracks the exact lifetime of all analysis results, allowing
 896 it to <a href="#releaseMemory">free memory</a> allocated to holding analysis
 897 results as soon as they are no longer needed.<p>
 898
 899 <li><b>Pipeline the execution of passes on the program</b> - The
 900 <tt>PassManager</tt> attempts to get better cache and memory usage behavior out
 901 of a series of passes by pipelining the passes together.  This means that, given
 902 a series of consequtive <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s, it
 903 will execute all of the <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s on
 904 the first function, then all of the <a
 905 href="#FunctionPass"><tt>FunctionPass</tt></a>'s on the second function,
 906 etc... until the entire program has been run through the passes.<p>
 907
 908 This improves the cache behavior of the compiler, because it is only touching
 909 the LLVM program representation for a single function at a time, instead of
 910 traversing the entire program.  It reduces the memory consumption of compiler,
 911 because, for example, only one <a
 912 href="http://llvm.cs.uiuc.edu/doxygen/structDominatorSet.html"><tt>DominatorSet</tt></a>
 913 needs to be calculated at a time.  This also makes it possible some <a
 914 href="#SMP">interesting enhancements</a> in the future.<p>
 915
 916 </ol><p>
 917
 918 The effectiveness of the <tt>PassManager</tt> is influenced directly by how much
 919 information it has about the behaviors of the passes it is scheduling.  For
 920 example, the "preserved" set is intentionally conservative in the face of an
 921 unimplemented <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method.
 922 Not implementing when it should be implemented will have the effect of not
 923 allowing any analysis results to live across the execution of your pass.<p>
 924
 925 The <tt>PassManager</tt> class exposes a <tt>--debug-pass</tt> command line
 926 options that is useful for debugging pass execution, seeing how things work, and
 927 diagnosing when you should be preserving more analyses than you currently are
 928 (To get information about all of the variants of the <tt>--debug-pass</tt>
 929 option, just type '<tt>opt --help-hidden</tt>').<p>
 930
 931 By using the <tt>--debug-pass=Structure</tt> option, for example, we can see how
 932 our <a href="#basiccode">Hello World</a> pass interacts with other passes.  Lets
 933 try it out with the <tt>gcse</tt> and <tt>licm</tt> passes:<p>
 934
 935 <pre>
 936 $ opt -load ../../../lib/Debug/libhello.so -gcse -licm --debug-pass=Structure &lt; hello.bc &gt; /dev/null
 937 Module Pass Manager
 938   Function Pass Manager
 939     Dominator Set Construction
 940     Immediate Dominators Construction
 941     Global Common Subexpression Elimination
 942 --  Immediate Dominators Construction
 943 --  Global Common Subexpression Elimination
 944     Natural Loop Construction
 945     Loop Invariant Code Motion
 946 --  Natural Loop Construction
 947 --  Loop Invariant Code Motion
 948     Module Verifier
 949 --  Dominator Set Construction
 950 --  Module Verifier
 951   Bytecode Writer
 952 --Bytecode Writer
 953 </pre><p>
 954
 955 This output shows us when passes are constructed and when the analysis results
 956 are known to be dead (prefixed with '<tt>--</tt>').  Here we see that GCSE uses
 957 dominator and immediate dominator information to do its job.  The LICM pass uses
 958 natural loop information, which uses dominator sets, but not immediate
 959 dominators.  Because immediate dominators are no longer useful after the GCSE
 960 pass, it is immediately destroyed.  The dominator sets are then reused to
 961 compute natural loop information, which is then used by the LICM pass.<p>
 962
 963 After the LICM pass, the module verifier runs (which is automatically added by
 964 the '<tt>opt</tt>' tool), which uses the dominator set to check that the
 965 resultant LLVM code is well formed.  After it finishes, the dominator set
 966 information is destroyed, after being computed once, and shared by three
 967 passes.<p>
 968
 969 Lets see how this changes when we run the <a href="#basiccode">Hello World</a>
 970 pass in between the two passes:<p>
 971
 972 <pre>
 973 $ opt -load ../../../lib/Debug/libhello.so -gcse -hello -licm --debug-pass=Structure &lt; hello.bc &gt; /dev/null
 974 Module Pass Manager
 975   Function Pass Manager
 976     Dominator Set Construction
 977     Immediate Dominators Construction
 978     Global Common Subexpression Elimination
 979 <b>--  Dominator Set Construction</b>
 980 --  Immediate Dominators Construction
 981 --  Global Common Subexpression Elimination
 982 <b>    Hello World Pass
 983 --  Hello World Pass
 984     Dominator Set Construction</b>
 985     Natural Loop Construction
 986     Loop Invariant Code Motion
 987 --  Natural Loop Construction
 988 --  Loop Invariant Code Motion
 989     Module Verifier
 990 --  Dominator Set Construction
 991 --  Module Verifier
 992   Bytecode Writer
 993 --Bytecode Writer
 994 Hello: __main
 995 Hello: puts
 996 Hello: main
 997 </pre><p>
 998
 999 Here we see that the <a href="#basiccode">Hello World</a> pass has killed the
1000 Dominator Set pass, even though it doesn't modify the code at all!  To fix this,
1001 we need to add the following <a
1002 href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method to our pass:<p>
1003
1004 <pre>
1005     <i>// We don't modify the program, so we preserve all analyses</i>
1006     <b>virtual void</b> getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
1007       AU.setPreservesAll();
1008     }
1009 </pre><p>
1010
1011 Now when we run our pass, we get this output:<p>
1012
1013 <pre>
1014 $ opt -load ../../../lib/Debug/libhello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null
1015 Pass Arguments:  -gcse -hello -licm
1016 Module Pass Manager
1017   Function Pass Manager
1018     Dominator Set Construction
1019     Immediate Dominators Construction
1020     Global Common Subexpression Elimination
1021 --  Immediate Dominators Construction
1022 --  Global Common Subexpression Elimination
1023     Hello World Pass
1024 --  Hello World Pass
1025     Natural Loop Construction
1026     Loop Invariant Code Motion
1027 --  Loop Invariant Code Motion
1028 --  Natural Loop Construction
1029     Module Verifier
1030 --  Dominator Set Construction
1031 --  Module Verifier
1032   Bytecode Writer
1033 --Bytecode Writer
1034 Hello: __main
1035 Hello: puts
1036 Hello: main
1037 </pre><p>
1038
1039 Which shows that we don't accidentally invalidate dominator information
1040 anymore, and therefore do not have to compute it twice.<p>
1041
1042
1043 <!-- _______________________________________________________________________ -->
1044 </ul><h4><a name="releaseMemory"><hr size=0>The <tt>releaseMemory</tt> method</h4><ul>
1045
1046 <pre>
1047   <b>virtual void</b> releaseMemory();
1048 </pre><p>
1049
1050 The <tt>PassManager</tt> automatically determines when to compute analysis
1051 results, and how long to keep them around for.  Because the lifetime of the pass
1052 object itself is effectively the entire duration of the compilation process, we
1053 need some way to free analysis results when they are no longer useful.  The
1054 <tt>releaseMemory</tt> virtual method is the way to do this.<p>
1055
1056 If you are writing an analysis or any other pass that retains a significant
1057 amount of state (for use by another pass which "requires" your pass and uses the
1058 <a href="#getAnalysis">getAnalysis</a> method) you should implement
1059 <tt>releaseMEmory</tt> to, well, release the memory allocated to maintain this
1060 internal state.  This method is called after the <tt>run*</tt> method for the
1061 class, before the next call of <tt>run*</tt> in your pass.<p>
1062
1063
1064 <!-- *********************************************************************** -->
1065 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
1066 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
1067 <a name="debughints">Using GDB with dynamically loaded passes
1068 </b></font></td></tr></table><ul>
1069 <!-- *********************************************************************** -->
1070
1071 Unfortunately, using GDB with dynamically loaded passes is not as easy as it
1072 should be.  First of all, you can't set a breakpoint in a shared object that has
1073 not been loaded yet, and second of all there are problems with inlined functions
1074 in shared objects.  Here are some suggestions to debugging your pass with
1075 GDB.<p>
1076
1077 For sake of discussion, I'm going to assume that you are debugging a
1078 transformation invoked by <tt>opt</tt>, although nothing described here depends
1079 on that.<p>
1080
1081 <!-- _______________________________________________________________________ -->
1082 </ul><h4><a name="breakpoint"><hr size=0>Setting a breakpoint in your pass</h4><ul>
1083
1084 First thing you do is start <tt>gdb</tt> on the <tt>opt</tt> process:<p>
1085
1086 <pre>
1087 $ <b>gdb opt</b>
1088 GNU gdb 5.0
1089 Copyright 2000 Free Software Foundation, Inc.
1090 GDB is free software, covered by the GNU General Public License, and you are
1091 welcome to change it and/or distribute copies of it under certain conditions.
1092 Type "show copying" to see the conditions.
1093 There is absolutely no warranty for GDB.  Type "show warranty" for details.
1094 This GDB was configured as "sparc-sun-solaris2.6"...
1095 (gdb)
1096 </pre><p>
1097
1098 Note that <tt>opt</tt> has a lot of debugging information in it, so it takes
1099 time to load.  Be patient.  Since we cannot set a breakpoint in our pass yet
1100 (the shared object isn't loaded until runtime), we must execute the process, and
1101 have it stop before it invokes our pass, but after it has loaded the shared
1102 object.  The most foolproof way of doing this is to set a breakpoint in
1103 <tt>PassManager::run</tt> and then run the process with the arguments you
1104 want:<p>
1105
1106 <pre>
1107 (gdb) <b>break PassManager::run</b>
1108 Breakpoint 1 at 0x2413bc: file Pass.cpp, line 70.
1109 (gdb) <b>run test.bc -load /shared/lattner/cvs/llvm/lib/Debug/[libname].so -[passoption]</b>
1110 Starting program: /shared/lattner/cvs/llvm/tools/Debug/opt test.bc
1111     -load /shared/lattner/cvs/llvm/lib/Debug/[libname].so -[passoption]
1112 Breakpoint 1, PassManager::run (this=0xffbef174, M=@0x70b298) at Pass.cpp:70
1113 70      bool PassManager::run(Module &amp;M) { return PM-&gt;run(M); }
1114 (gdb)
1115 </pre></p>
1116
1117 Once the <tt>opt</tt> stops in the <tt>PassManager::run</tt> method you are now
1118 free to set breakpoints in your pass so that you can trace through execution or
1119 do other standard debugging stuff.<p>
1120
1121
1122 <!-- _______________________________________________________________________ -->
1123 </ul><h4><a name="debugmisc"><hr size=0>Miscellaneous Problems</h4><ul>
1124
1125 Once you have the basics down, there are a couple of problems that GDB has, some
1126 with solutions, some without.<p>
1127
1128 <ul>
1129 <li>Inline functions have bogus stack information.  In general, GDB does a
1130 pretty good job getting stack traces and stepping through inline functions.
1131 When a pass is dynamically loaded however, it somehow completely loses this
1132 capability.  The only solution I know of is to de-inline a function (move it
1133 from the body of a class to a .cpp file).<p>
1134
1135 <li>Restarting the program breaks breakpoints.  After following the information
1136 above, you have succeeded in getting some breakpoints planted in your pass.  Nex
1137 thing you know, you restart the program (i.e., you type '<tt>run</tt>' again),
1138 and you start getting errors about breakpoints being unsettable.  The only way I
1139 have found to "fix" this problem is to <tt>delete</tt> the breakpoints that are
1140 already set in your pass, run the program, and re-set the breakpoints once
1141 execution stops in <tt>PassManager::run</tt>.<p>
1142
1143 </ul>
1144
1145 Hopefully these tips will help with common case debugging situations.  If you'd
1146 like to contribute some tips of your own, just contact <a
1147 href="mailto:sabre@nondot.org">Chris</a>.<p>
1148
1149
1150 <!-- *********************************************************************** -->
1151 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
1152 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
1153 <a name="future">Future extensions planned
1154 </b></font></td></tr></table><ul>
1155 <!-- *********************************************************************** -->
1156
1157 Although the LLVM Pass Infrastructure is very capable as it stands, and does
1158 some nifty stuff, there are things we'd like to add in the future.  Here is
1159 where we are going:<p>
1160
1161 <!-- _______________________________________________________________________ -->
1162 </ul><h4><a name="SMP"><hr size=0>Multithreaded LLVM</h4><ul>
1163
1164 Multiple CPU machines are becoming more common and compilation can never be
1165 fast enough: obviously we should allow for a multithreaded compiler.  Because of
1166 the semantics defined for passes above (specifically they cannot maintain state
1167 across invocations of their <tt>run*</tt> methods), a nice clean way to
1168 implement a multithreaded compiler would be for the <tt>PassManager</tt> class
1169 to create multiple instances of each pass object, and allow the seperate
1170 instances to be hacking on different parts of the program at the same time.<p>
1171
1172 This implementation would prevent each of the passes from having to implement
1173 multithreaded constructs, requiring only the LLVM core to have locking in a few
1174 places (for global resources).  Although this is a simple extension, we simply
1175 haven't had time (or multiprocessor machines, thus a reason) to implement this.
1176 Despite that, we have kept the LLVM passes SMP ready, and you should too.<p>
1177
1178
1179 <!-- _______________________________________________________________________ -->
1180 </ul><h4><a name="ModuleSource"><hr size=0>A new <tt>ModuleSource</tt> interface</h4><ul>
1181
1182 Currently, the <tt>PassManager</tt>'s <tt>run</tt> method takes a <tt><a
1183 href="http://llvm.cs.uiuc.edu/doxygen/classModule.html">Module</a></tt> as
1184 input, and runs all of the passes on this module.  The problem with this
1185 approach is that none of the <tt>PassManager</tt> features can be used for
1186 timing and debugging the actual <b>loading</b> of the module from disk or
1187 standard input.<p>
1188
1189 To solve this problem, eventually the <tt>PassManger</tt> class will accept a
1190 <tt>ModuleSource</tt> object instead of a Module itself.  When complete, this
1191 will also allow for streaming of functions out of the bytecode representation,
1192 allowing us to avoid holding the entire program in memory at once if we only are
1193 dealing with <a href="#FunctionPass">FunctionPass</a>'s.<p>
1194
1195 As part of a different issue, eventually the bytecode loader will be extended to
1196 allow on-demand loading of functions from the bytecode representation, in order
1197 to better support the runtime reoptimizer.  The bytecode format is already
1198 capable of this, the loader just needs to be reworked a bit.<p>
1199
1200
1201 <!-- _______________________________________________________________________ -->
1202 </ul><h4><a name="PassFunctionPass"><hr size=0><tt>Pass</tt>'s requiring <tt>FunctionPass</tt>'s</h4><ul>
1203
1204 Currently it is illegal for a <a href="#Pass"><tt>Pass</tt></a> to require a <a
1205 href="#FunctionPass"><tt>FunctionPass</tt></a>.  This is because there is only
1206 one instance of the <a href="#FunctionPass"><tt>FunctionPass</tt></a> object
1207 ever created, thus nowhere to store information for all of the functions in the
1208 program at the same time.  Although this has come up a couple of times before,
1209 this has always been worked around by factoring one big complicated pass into a
1210 global and an interprocedural part, both of which are distinct.  In the future,
1211 it would be nice to have this though.<p>
1212
1213 Note that it is no problem for a <a
1214 href="#FunctionPass"><tt>FunctionPass</tt></a> to require the results of a <a
1215 href="#Pass"><tt>Pass</tt></a>, only the other way around.<p>
1216
1217
1218 <!-- *********************************************************************** -->
1219 </ul>
1220 <!-- *********************************************************************** -->
1221
1222 <hr><font size-1>
1223 <address><a href="mailto:sabre@nondot.org">Chris Lattner</a></address>
1224 <!-- Created: Tue Aug  6 15:00:33 CDT 2002 -->
1225 <!-- hhmts start -->
1226 Last modified: Mon Oct 21 14:52:55 CDT 2002
1227 <!-- hhmts end -->
1228 </font></body></html>