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 <!--
   5 I. General Structure of an LLVM Program
   6
   7 I.1 "What is a 'Value'?": Value & User class
   8 I.2 Type & Derived Types
   9 I.3 GlobalVariable, Function
  10 I.4 BasicBlock
  11 I.5 Instruction & Subclasses
  12 1.6 Argument
  13 1.7 Constants
  14
  15 III. Useful things to know about the LLVM source base:
  16
  17 III.1 Useful links that introduce the STL
  18 III.2 isa<>, cast<>, dyn_cast<>
  19 III.3 Makefiles, useful options
  20 III.4 How to use opt & analyze to debug stuff
  21 III.5 How to write a regression test
  22 III.6 DEBUG() and Statistics (-debug & -stats)
  23 III.7 The -time-passes option
  24 III.8 ... more as needed ...
  25
  26 I think that writing Section #1 would be very helpful and that's the most
  27 stable portion of the sourcebase.  #3 can be started on, but will probably
  28 just grow as time goes on.  I'd like to do Section #2 once I finish some
  29 changes up that effect it.
  30
  31 -->
  32
  33 <body bgcolor=white>
  34
  35 <table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
  36 <tr><td>&nbsp; <font size=+3 color="#EEEEFF" face="Georgia,Palatino,Times,Roman"><b>Writing an LLVM Pass</b></font></td>
  37 </tr></table>
  38
  39
  40 <ol>
  41   <li><a href="#introduction">Introduction - What is a pass?</a>
  42   <li><a href="#quickstart">Quick Start - Writing hello world</a>
  43     <ul>
  44     <li><a href="#makefile">Setting up the build environment</a>
  45     <li><a href="#basiccode">Basic code required</a>
  46     <li><a href="#running">Running a pass with <tt>opt</tt>
  47          or <tt>analyze</tt></a>
  48     </ul>
  49   <li><a href="#passtype">Pass classes and requirements</a>
  50      <ul>
  51      <li><a href="#Pass">The <tt>Pass</tt> class</a>
  52         <ul>
  53         <li><a href="#run">The <tt>run</tt> method</a>
  54         </ul>
  55      <li><a href="#FunctionPass">The <tt>FunctionPass</tt> class</a>
  56         <ul>
  57         <li><a href="#doInitialization">The <tt>doInitialization</tt> method</a>
  58         <li><a href="#runOnFunction">The <tt>runOnFunction</tt> method</a>
  59         <li><a href="#doFinalization">The <tt>doFinalization</tt> method</a>
  60         </ul>
  61      <li><a href="#BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
  62         <ul>
  63         <li><a href="#runOnBasicBlock">The <tt>runOnBasicBlock</tt> method</a>
  64         </ul>
  65      </ul>
  66   <li><a href="#registration">Pass Registration</a>
  67      <ul>
  68      <li><a href="#print">The <tt>print</tt> method</a>
  69      </ul>
  70   <li><a href="#interaction">Specifying interactions between passes</a>
  71      <ul>
  72      <li><a href="#getAnalysisUsage">The <tt>getAnalysisUsage</tt> method</a>
  73      <li><a href="#getAnalysis">The <tt>getAnalysis</tt> method</a>
  74      </ul>
  75   <li><a href="#passmanager">What PassManager does</a>
  76     <ul>
  77     <li><a href="#releaseMemory">The <tt>releaseMemory</tt> method</a>
  78     </ul>
  79   <li><a href="#future">Future extensions planned</a>
  80     <ul>
  81     <li><a href="#SMP">Multithreaded LLVM</a>
  82     <li><a href="#ModuleSource">A new <tt>ModuleSource</tt> interface</a>
  83     <li><a href="#PassFunctionPass"><tt>Pass</tt>'s requiring <tt>FunctionPass</tt>'s</a>
  84     </ul>
  85 </ol><p>
  86
  87
  88
  89 <!-- *********************************************************************** -->
  90 <table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
  91 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
  92 <a name="introduction">Introduction - What is a pass?
  93 </b></font></td></tr></table><ul>
  94 <!-- *********************************************************************** -->
  95
  96 The LLVM Pass Framework is an important part of the LLVM system, because LLVM
  97 passes are where the interesting parts of the compiler exist.  Passes perform
  98 the transformations and optimizations that make up the compiler, they build
  99 the analysis results that are used by these transformations, and they are, above
 100 all, a structuring technique for compiler code.<p>
 101
 102 All LLVM passes are subclasses of the <tt><a
 103 href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt> class, which
 104 implement functionality by overriding virtual methods inherited from
 105 <tt>Pass</tt>.  Depending on how your pass works, you may be able to inherit
 106 from the <tt><a
 107 href="http://llvm.cs.uiuc.edu/doxygen/structFunctionPass.html">FunctionPass</a></tt>
 108 or <tt><a
 109 href="http://llvm.cs.uiuc.edu/doxygen/structBasicBlockPass.html">BasicBlockPass</a></tt>,
 110 which gives the system more information about what your pass does, and how it
 111 can be combined with other passes.  One of the main features of the LLVM Pass
 112 Framework is that it schedules passes to run in an efficient way based on the
 113 constraints that your pass has.<p>
 114
 115 We start by showing you how to construct a pass, everything from setting up the
 116 code, to compiling, loading, and executing it.  After the basics are down, more
 117 advanced features are discussed.<p>
 118
 119
 120 <!-- *********************************************************************** -->
 121 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
 122 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
 123 <a name="quickstart">Quick Start - Writing hello world
 124 </b></font></td></tr></table><ul>
 125 <!-- *********************************************************************** -->
 126
 127 Here we describe how to write the "hello world" of passes.  The "Hello" pass is
 128 designed to simply print out the name of non-external functions that exist in
 129 the program being compiled.  It does not modify the program at all, just
 130 inspects it.  The source code and files for this pass are available in the LLVM
 131 source tree in the <tt>lib/Transforms/Hello</tt> directory.<p>
 132
 133
 134 <!-- ======================================================================= -->
 135 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 136 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 137 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 138 <a name="makefile">Setting up the build environment
 139 </b></font></td></tr></table><ul>
 140
 141 First thing you need to do is create a new directory somewhere in the LLVM
 142 source base.  For this example, we'll assume that you made
 143 "<tt>lib/Transforms/Hello</tt>".  The first thing you must do is set up a build
 144 script (Makefile) that will compile the source code for the new pass.  To do
 145 this, copy this into "<tt>Makefile</tt>":<p>
 146
 147 </ul><hr><ul><pre>
 148 # Makefile for hello pass
 149 LEVEL = ../../..                    # Path to top level of LLVM heirarchy
 150 LIBRARYNAME = hello                 # Name of the library to build
 151 SHARED_LIBRARY = 1                  # Build a dynamically loadable shared object
 152
 153 include $(LEVEL)/Makefile.common    # Include the makefile implementation stuff
 154 </pre></ul><hr><ul><p>
 155
 156 This makefile specifies that all of the <tt>.cpp</tt> files in the current
 157 directory are to be compiled and linked together into a
 158 <tt>lib/Debug/libhello.so</tt> shared object that can be dynamically loaded by
 159 the <tt>opt</tt> or <tt>analyze</tt> tools.<p>
 160
 161 Now that we have the build scripts set up, we just need to write the code for
 162 the pass itself.<p>
 163
 164
 165 <!-- ======================================================================= -->
 166 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 167 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 168 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 169 <a name="basiccode">Basic code required
 170 </b></font></td></tr></table><ul>
 171
 172 Now that we have a way to compile our new pass, we just have to write it.  Start
 173 out with:<p>
 174
 175 <pre>
 176 <b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
 177 <b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Function_8h-source.html">llvm/Function.h</a>"
 178 </pre>
 179
 180 Which are needed because we are writing a <tt><a
 181 href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt>, and we are
 182 operating on <tt><a
 183 href="http://llvm.cs.uiuc.edu/doxygen/classFunction.html">Function</a></tt>'s.<p>
 184
 185 Next we have:<p>
 186
 187 <pre>
 188 <b>namespace</b> {
 189 </pre><p>
 190
 191 ... which starts out an anonymous namespace.  Anonymous namespaces are to C++
 192 what the "<tt>static</tt>" keyword is to C (at global scope).  It makes the
 193 things declared inside of the anonymous namespace only visible to the current
 194 file.  If you're not familiar with them, consult a decent C++ book for more
 195 information.<p>
 196
 197 Next, we declare our pass itself:<p>
 198
 199 <pre>
 200   <b>struct</b> Hello : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
 201 </pre><p>
 202
 203 This declares a "<tt>Hello</tt>" class that is a subclass of <tt><a
 204 href="http://llvm.cs.uiuc.edu/doxygen/structFunctionPass.html">FunctionPass</a></tt>.
 205 The different builting pass subclasses are described in detail <a
 206 href="#passtype">later</a>, but for now, know that <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s
 207 operate a function at a time.<p>
 208
 209 <pre>
 210     <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &F) {
 211       std::cerr &lt;&lt; "<i>Hello: </i>" &lt;&lt; F.getName() &lt;&lt; "\n";
 212       <b>return false</b>;
 213     }
 214   };  <i>// end of struct Hello</i>
 215 </pre>
 216
 217 We declare a "<a href="#runOnFunction"><tt>runOnFunction</tt></a>" method, which
 218 overloads an abstract virtual method inherited from <a
 219 href="#FunctionPass"><tt>FunctionPass</tt></a>.  This is where we are supposed
 220 to do our thing, so we just print out our message with the name of each
 221 function.<p>
 222
 223 <pre>
 224   RegisterOpt&lt;Hello&gt; X("<i>hello</i>", "<i>Hello World Pass</i>");
 225 }  <i>// end of anonymous namespace</i>
 226 </pre><p>
 227
 228 Lastly, we register our class <tt>Hello</tt>, giving it a command line argument
 229 "<tt>hello</tt>", and a name "<tt>Hello World Pass</tt>".  There are several
 230 different ways of <a href="#registration">registering your pass</a>, depending
 231 on what it is to be used for.  For "optimizations" we use the
 232 <tt>RegisterOpt</tt> template.<p>
 233
 234 As a whole, the <tt>.cpp</tt> file looks like:<p>
 235
 236 <pre>
 237 <b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
 238 <b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Function_8h-source.html">llvm/Function.h</a>"
 239
 240 <b>namespace</b> {
 241   <b>struct Hello</b> : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
 242     <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &F) {
 243       std::cerr &lt;&lt; "<i>Hello: </i>" &lt;&lt; F.getName() &lt;&lt; "\n";
 244       <b>return false</b>;
 245     }
 246   };
 247
 248   RegisterOpt&lt;Hello&gt; X("<i>hello</i>", "<i>Hello World Pass</i>");
 249 }
 250 </pre><p>
 251
 252 Now that it's all together, compile the file with a simple "<tt>gmake</tt>"
 253 command in the local directory and you should get a new
 254 "<tt>lib/Debug/libhello.so</tt> file.  Note that everything in this file is
 255 contained in an anonymous namespace: this reflects the fact that passes are self
 256 contained units that do not need external interfaces (although they can have
 257 them) to be useful.<p>
 258
 259
 260 <!-- ======================================================================= -->
 261 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 262 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 263 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 264 <a name="running">Running a pass with <tt>opt</tt> or <tt>analyze</tt>
 265 </b></font></td></tr></table><ul>
 266
 267 Now that you have a brand new shiny <tt>.so</tt> file, we can use the
 268 <tt>opt</tt> command to run an LLVM program through your pass.  Because you
 269 registered your pass with the <tt>RegisterOpt</tt> template, you will be able to
 270 use the <tt>opt</tt> tool to access it, once loaded.<p>
 271
 272 To test it, follow the example at the end of the <a
 273 href="GettingStarted.html">Getting Started Guide</a> to compile "Hello World" to
 274 LLVM.  We can now run the bytecode file (<tt>hello.bc</tt>) for the program
 275 through our transformation like this (or course, any bytecode file will
 276 work):<p>
 277
 278 <pre>
 279 $ opt -load ../../../lib/Debug/libhello.so -hello &lt; hello.bc &gt; /dev/null
 280 Hello: __main
 281 Hello: puts
 282 Hello: main
 283 </pre><p>
 284
 285 The '<tt>-load</tt>' option specifies that '<tt>opt</tt>' should load your pass
 286 as a shared object, which makes '<tt>-hello</tt>' a valid command line argument
 287 (which is one reason you need to <a href="#registration">register your
 288 pass</a>).  Because the hello pass does not modify the program in any
 289 interesting way, we just throw away the result of <tt>opt</tt> (sending it to
 290 <tt>/dev/null</tt>).<p>
 291
 292 To see what happened to the other string you registered, try running
 293 <tt>opt</tt> with the <tt>--help</tt> option:<p>
 294
 295 <pre>
 296 $ opt -load ../../../lib/Debug/libhello.so --help
 297 OVERVIEW: llvm .bc -&gt; .bc modular optimizer
 298
 299 USAGE: opt [options] &lt;input bytecode&gt;
 300
 301 OPTIONS:
 302   Optimizations available:
 303 ...
 304     -funcresolve    - Resolve Functions
 305     -gcse           - Global Common Subexpression Elimination
 306     -globaldce      - Dead Global Elimination
 307     <b>-hello          - Hello World Pass</b>
 308     -indvars        - Cannonicalize Induction Variables
 309     -inline         - Function Integration/Inlining
 310     -instcombine    - Combine redundant instructions
 311 ...
 312 </pre><p>
 313
 314 The pass name get added as the information string for your pass, giving some
 315 documentation to users of <tt>opt</tt>.  Now that you have a working pass, you
 316 would go ahead and make it do the cool transformations you want.  Once you get
 317 it all working and tested, it may become useful to find out how fast your pass
 318 is.  The <a href="#passManager"><tt>PassManager</tt></a> provides a nice command
 319 line option (<tt>--time-passes</tt>) that allows you to get information about
 320 the execution time of your pass along with the other passes you queue up.  For
 321 example:<p>
 322
 323 <pre>
 324 $ opt -load ../../../lib/Debug/libhello.so -hello -time-passes &lt; hello.bc &gt; /dev/null
 325 Hello: __main
 326 Hello: puts
 327 Hello: main
 328 ===============================================================================
 329                       ... Pass execution timing report ...
 330 ===============================================================================
 331   Total Execution Time: 0.02 seconds (0.0479059 wall clock)
 332
 333    ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Pass Name ---
 334    0.0100 (100.0%)   0.0000 (  0.0%)   0.0100 ( 50.0%)   0.0402 ( 84.0%)  Bytecode Writer
 335    0.0000 (  0.0%)   0.0100 (100.0%)   0.0100 ( 50.0%)   0.0031 (  6.4%)  Dominator Set Construction
 336    0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0013 (  2.7%)  Module Verifier
 337  <b>  0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0033 (  6.9%)  Hello World Pass</b>
 338    0.0100 (100.0%)   0.0100 (100.0%)   0.0200 (100.0%)   0.0479 (100.0%)  TOTAL
 339 </pre><p>
 340
 341 As you can see, our implementation above is pretty fast :).  The additional
 342 passes listed are automatically inserted by the '<tt>opt</tt>' tool to verify
 343 that the LLVM emitted by your pass is still valid and well formed LLVM, which
 344 hasn't been broken somehow.
 345
 346 Now that you have seen the basics of the mechanics behind passes, we can talk
 347 about some more details of how they work and how to use them.<p>
 348
 349
 350
 351 <!-- *********************************************************************** -->
 352 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
 353 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
 354 <a name="passtype">Pass classes and requirements
 355 </b></font></td></tr></table><ul>
 356 <!-- *********************************************************************** -->
 357
 358 One of the first things that you should do when designing a new pass is to
 359 decide what class you should subclass for your pass.  The <a
 360 href="#basiccode">Hello World</a> example uses the <tt><a
 361 href="#FunctionPass">FunctionPass</a></tt> class for its implementation, but we
 362 did not discuss why or when this should occur.  Here we talk about the classes
 363 available, from the most general to the most specific.<p>
 364
 365 When choosing a superclass for your Pass, you should choose the most specific
 366 class possible, while still being able to meet the requirements listed.  This
 367 gives the LLVM Pass Infrastructure information neccesary to optimize how passes
 368 are run, so that the resultant compiler isn't unneccesarily slow.<p>
 369
 370
 371
 372 <!-- ======================================================================= -->
 373 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 374 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 375 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 376 <a name="Pass">The <tt>Pass</tt> class
 377 </b></font></td></tr></table><ul>
 378
 379 The "<tt><a href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt>"
 380 class is the most general of all superclasses that you can use.  Deriving from
 381 <tt>Pass</tt> indicates that your pass uses the entire program as a unit,
 382 refering to function bodies in no predictable order, or adding and removing
 383 functions.  Because nothing is known about the behavior of direct <tt>Pass</tt>
 384 subclasses, no optimization can be done for their execution.<p>
 385
 386 To write a correct <tt>Pass</tt> subclass, derive from <tt>Pass</tt> and
 387 overload the <tt>run</tt> method with the following signature:<p>
 388
 389 <!-- _______________________________________________________________________ -->
 390 </ul><h4><a name="run"><hr size=0>The <tt>run</tt> method</h4><ul>
 391
 392
 393 <pre>
 394   <b>virtual bool</b> run(Module &amp;M) = 0;
 395 </pre><p>
 396
 397 The <tt>run</tt> method performs the interesting work of the pass, and should
 398 return true if the module was modified by the transformation, false
 399 otherwise.<p>
 400
 401
 402
 403 <!-- ======================================================================= -->
 404 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 405 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 406 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 407 <a name="FunctionPass">The <tt>FunctionPass</tt> class
 408 </b></font></td></tr></table><ul>
 409
 410 In contrast to direct <tt>Pass</tt> subclasses, direct <tt><a
 411 href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">FunctionPass</a></tt>
 412 subclasses do have a predictable, local behavior that can be expected by the
 413 system.  All <tt>FunctionPass</tt> execute on each function in the program
 414 independant of all of the other functions in the program.
 415 <tt>FunctionPass</tt>'s do not require that they are executed in a particular
 416 order, and <tt>FunctionPass</tt>'s do not modify external functions.<p>
 417
 418 To be explicit, <tt>FunctionPass</tt> subclasses are not allowed to:<p>
 419
 420 <ol>
 421 <li>Modify a Function other than the one currently being processed.
 422 <li>Add or remove Function's from the current Module.
 423 <li>Add or remove global variables from the current Module.
 424 <li>Maintain state across invocations of
 425     <a href="#runOnFunction"><tt>runOnFunction</tt></a> (including global data)
 426 </ol><p>
 427
 428 Implementing a <tt>FunctionPass</tt> is usually straightforward (See the <a
 429 href="#basiccode">Hello World</a> pass for example).  <tt>FunctionPass</tt>'s
 430 may overload three virtual methods to do their work.  All of these methods
 431 should return true if they modified the program, or false if they didn't.<p>
 432
 433 <!-- _______________________________________________________________________ -->
 434 </ul><h4><a name="doInitialization"><hr size=0>The <tt>doInitialization</tt>
 435 method</h4><ul>
 436
 437 <pre>
 438   <b>virtual bool</b> doInitialization(Module &amp;M);
 439 </pre><p>
 440
 441 The <tt>doIninitialize</tt> method is allowed to do most of the things that
 442 <tt>FunctionPass</tt>'s are not allowed to do.  They can add and remove
 443 functions, get pointers to functions, etc.  The <tt>doInitialize</tt> method is
 444 designed to do simple initialization type of stuff that does not depend on the
 445 functions being processed.  The <tt>doInitialization</tt> function call is not
 446 scheduled to overlap with any other pass executions.<p>
 447
 448 A good example of how this method should be used is the <a
 449 href="http://llvm.cs.uiuc.edu/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations</a>
 450 pass.  This pass converts <tt>malloc</tt> and <tt>free</tt> instructions into
 451 platform dependant <tt>malloc()</tt> and <tt>free()</tt> function calls.  It
 452 uses the <tt>doInitialization</tt> method to get a reference to the malloc and
 453 free functions that it needs, adding prototypes to the module if neccesary.<p>
 454
 455 <!-- _______________________________________________________________________ -->
 456 </ul><h4><a name="runOnFunction"><hr size=0>The <tt>runOnFunction</tt> method</h4><ul>
 457
 458 <pre>
 459   <b>virtual bool</b> runOnFunction(Function &amp;F) = 0;
 460 </pre><p>
 461
 462 The <tt>runOnFunction</tt> method must be implemented by your subclass to do the
 463 transformation or analysis work of your pass.  As usual, a true value should be
 464 returned if the function is modified.<p>
 465
 466 <!-- _______________________________________________________________________ -->
 467 </ul><h4><a name="doFinalization"><hr size=0>The <tt>doFinalization</tt> method</h4><ul>
 468
 469 <pre>
 470   <b>virtual bool</b> doFinalization(Module &amp;M);
 471 </pre</p>
 472
 473 The <tt>doFinalization</tt> method is an infrequently used method that is called
 474 when the pass framework has finished calling <a
 475 href="#runOnFunction"><tt>runOnFunction</tt></a> for every function in the
 476 program being compiled.<p>
 477
 478
 479
 480 <!-- ======================================================================= -->
 481 </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
 482 <tr><td>&nbsp;</td><td width="100%">&nbsp;
 483 <font color="#EEEEFF" face="Georgia,Palatino"><b>
 484 <a name="BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
 485 </b></font></td></tr></table><ul>
 486
 487 <tt>BasicBlockPass</tt>'s are just like <a
 488 href="#FunctionPass"><tt>FunctionPass</tt></a>'s, except that they must limit
 489 their scope of inspection and modification to a single basic block at a time.
 490 As such, they are <b>not</b> allowed to do any of the following:<p>
 491
 492 <ol>
 493 <li>Modify or inspect any basic blocks outside of the current one
 494 <li>Maintain state across invocations of
 495     <a href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a>
 496 <li>Modify the constrol flow graph (by altering terminator instructions)
 497 <li>Any of the things verboten for
 498     <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s.
 499 </ol><p>
 500
 501 <tt>BasicBlockPass</tt>'s are useful for traditional local and "peephole"
 502 optimizations.  They may override the same <a
 503 href="#doInitialization"><tt>doInitialization</tt></a> and <a
 504 href="#doFinalization"><tt>doFinalization</tt></a> methods that <a
 505 href="#FunctionPass"><tt>FunctionPass</tt></a>'s have, but also have a
 506 <tt>runOnBasicBlock</tt> method:<p>
 507
 508 <!-- _______________________________________________________________________ -->
 509 </ul><h4><a name="runOnBasicBlock"><hr size=0>The <tt>runOnBasicBlock</tt> method</h4><ul>
 510
 511 <pre>
 512   <b>virtual bool</b> runOnBasicBlock(BasicBlock &amp;BB) = 0;
 513 </pre><p>
 514
 515 Override this function to do the work of the <tt>BasicBlockPass</tt>.  This
 516 function is not allowed to inspect or modify basic blocks other than the
 517 parameter, and are not allowed to modify the CFG.  A true value must be returned
 518 if the basic block is modified.<p>
 519
 520
 521 <!-- *********************************************************************** -->
 522 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
 523 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
 524 <a name="registration">Pass registration
 525 </b></font></td></tr></table><ul>
 526 <!-- *********************************************************************** -->
 527
 528 In the <a href="#basiccode">Hello World</a> example pass we illustrated how pass
 529 registration works, and discussed some of the reasons that it is used and what
 530 it does.  Here we discuss how and why passes are registered.<p>
 531
 532 Passes can be registered in several different ways.  Depending on the general
 533 classification of the pass, you should use one of the following templates to
 534 register the pass:<p>
 535
 536 <ul>
 537 <li><b><tt>RegisterOpt</tt></b> - This template should be used when you are
 538 registering a pass that logically should be available for use in the
 539 '<tt>opt</tt>' utility.<p>
 540
 541 <li><b><tt>RegisterAnalysis</tt></b> - This template should be used when you are
 542 registering a pass that logically should be available for use in the
 543 '<tt>analysis</tt>' utility.<p>
 544
 545 <li><b><tt>RegisterLLC</tt></b> - This template should be used when you are
 546 registering a pass that logically should be available for use in the
 547 '<tt>llc</tt>' utility.<p>
 548
 549 <li><b><tt>RegisterPass</tt></b> - This is the generic form of the
 550 <tt>Register*</tt> templates that should be used if you want your pass listed by
 551 multiple or no utilities.  This template takes an extra third argument that
 552 specifies which tools it should be listed in.  See the <a
 553 href="http://llvm.cs.uiuc.edu/doxygen/PassSupport_8h-source.html">PassSupport.h</a>
 554 file for more information.<p>
 555 </ul><p>
 556
 557 Regardless of how you register your pass, you must specify at least two
 558 parameters.  The first parameter is the name of the pass that is to be used on
 559 the command line to specify that the pass should be added to a program (for
 560 example <tt>opt</tt> or <tt>analyze</tt>).  The second argument is the name of
 561 the pass, which is to be used for the <tt>--help</tt> output of programs, as
 562 well as for debug output generated by the <tt>--debug-pass</tt> option.<p>
 563
 564 If you pass is constructed by its default constructor, you only ever have to
 565 pass these two arguments.  If, on the other hand, you require other information
 566 (like target specific information), you must pass an additional argument.  This
 567 argument is a pointer to a function used to create the pass.  For an example of
 568 how this works, look at the <a
 569 href="http://llvm.cs.uiuc.edu/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations.cpp</a>
 570 file.<p>
 571
 572 If a pass is registered to be used by the <tt>analyze</tt> utility, you should
 573 implement the virtual <tt>print</tt> method:<p>
 574
 575 <!-- _______________________________________________________________________ -->
 576 </ul><h4><a name="print"><hr size=0>The <tt>print</tt> method</h4><ul>
 577
 578 <pre>
 579   <b>virtual void</b> print(std::ostream &amp;O, <b>const</b> Module *M) <b>const</b>;
 580 </pre><p>
 581
 582 The <tt>print</tt> method must be implemented by "analyses" in order to print a
 583 human readable version of the analysis results.  This is useful for debugging an
 584 analysis itself, as well as for other people to figure out how an analysis
 585 works.  The <tt>analyze</tt> tool uses this method to generate its output.<p>
 586
 587 The <tt>ostream</tt> parameter specifies the stream to write the results on, and
 588 the <tt>Module</tt> parameter gives a pointer to the top level module of the
 589 program that has been analyzed.  Note however that this pointer may be null in
 590 certain circumstances (such as calling the <tt>Pass::dump()</tt> from a
 591 debugger), so it should only be used to enhance debug output, it should not be
 592 depended on.<p>
 593
 594
 595 <!-- *********************************************************************** -->
 596 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
 597 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
 598 <a name="interaction">Specifying interactions between passes
 599 </b></font></td></tr></table><ul>
 600 <!-- *********************************************************************** -->
 601
 602 One of the main responsibilities of the <tt>PassManager</tt> is the make sure
 603 that passes interact with each other correctly.  Because <tt>PassManager</tt>
 604 tries to <a href="#passmanager">optimize the execution of passes</a> it must
 605 know how the passes interact with each other and what dependencies exist between
 606 the various passes.  To track this, each pass can declare the set of passes that
 607 are required to be executed before the current pass, and the passes which are
 608 invalidated by the current pass.<p>
 609
 610 Typically this functionality is used to require that analysis results are
 611 computed before your pass is run.  Running arbitrary transformation passes can
 612 invalidate the computed analysis results, which is what the invalidation set
 613 specifies.  If a pass does not implement the <tt><a
 614 href="#getAnalysisUsage">getAnalysisUsage</a></tt> method, it defaults to not
 615 having any prerequisite passes, and invalidating <b>all</b> other passes.<p>
 616
 617
 618 <!-- _______________________________________________________________________ -->
 619 </ul><h4><a name="getAnalysisUsage"><hr size=0>The <tt>getAnalysisUsage</tt> method</h4><ul>
 620
 621 <pre>
 622   <b>virtual void</b> getAnalysisUsage(AnalysisUsage &amp;Info) <b>const</b>;
 623 </pre><p>
 624
 625 By implementing the <tt>getAnalysisUsage</tt> method, the required and
 626 invalidated sets may be specified for your transformation.  The implementation
 627 should fill in the <tt><a
 628 href="http://llvm.cs.uiuc.edu/doxygen/classAnalysisUsage.html">AnalysisUsage</a></tt>
 629 object with information about which passes are required and not invalidated.  To do this, the following set methods are provided by the <tt><a
 630 href="http://llvm.cs.uiuc.edu/doxygen/classAnalysisUsage.html">AnalysisUsage</a></tt> class:<p>
 631
 632 <pre>
 633   <i>// addRequires - Add the specified pass to the required set for your pass.</i>
 634   <b>template</b>&lt;<b>class</b> PassClass&gt;
 635   AnalysisUsage &amp;AnalysisUsage::addRequired();
 636
 637   <i>// addPreserved - Add the specified pass to the set of analyses preserved by
 638   // this pass</i>
 639   <b>template</b>&lt;<b>class</b> PassClass&gt;
 640   AnalysisUsage &amp;AnalysisUsage::addPreserved();
 641
 642   <i>// setPreservesAll - Call this if the pass does not modify its input at all</i>
 643   <b>void</b> AnalysisUsage::setPreservesAll();
 644
 645   <i>// preservesCFG - This function should be called by the pass, iff they do not:
 646   //
 647   //  1. Add or remove basic blocks from the function
 648   //  2. Modify terminator instructions in any way.
 649   //
 650   //  This is automatically implied for <a href="#BasicBlockPass">BasicBlockPass</a>'s
 651   //</i>
 652   <b>void</b> AnalysisUsage::preservesCFG();
 653 </pre><p>
 654
 655 Some examples of how to use these methods are:<p>
 656
 657 <pre>
 658   <i>// This is an example implementation from an analysis, which does not modify
 659   // the program at all, yet has a prerequisite.</i>
 660   <b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/structPostDominanceFrontier.html">PostDominanceFrontier</a>::getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
 661     AU.setPreservesAll();
 662     AU.addRequired&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structPostDominatorTree.html">PostDominatorTree</a>&gt;();
 663   }
 664 </pre><p>
 665
 666 and:<p>
 667
 668 <pre>
 669   <i>// This example modifies the program, but does not modify the CFG</i>
 670   <b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/structLICM.html">LICM</a>::getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
 671     AU.preservesCFG();
 672     AU.addRequired&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/classLoopInfo.html">LoopInfo</a>&gt;();
 673   }
 674 </pre><p>
 675
 676 <!-- _______________________________________________________________________ -->
 677 </ul><h4><a name="getAnalysis"><hr size=0>The <tt>getAnalysis&lt;&gt;</tt> method</h4><ul>
 678
 679 The <tt>Pass::getAnalysis&lt;&gt;</tt> method is inherited by your class,
 680 providing you with access to the passes that you declared that you required with
 681 the <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method.  It takes
 682 a single template argument that specifies which pass class you want, and returns
 683 a reference to that pass.<p>
 684
 685 <pre>
 686   <b>template</b>&lt;<b>typename</b> PassClass&gt;
 687   AnalysisType &amp;getAnalysis();
 688 </pre><p>
 689
 690 This method call returns a reference to the pass desired.  You may get a runtime
 691 assertion failure if you attempt to get an analysis that you did not declare as
 692 required in your <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a>
 693 implementation.  This method can be called by your <tt>run*</tt> method
 694 implementation, or by any other local method invoked by your <tt>run*</tt>
 695 method.<p>
 696
 697
 698
 699 <!-- *********************************************************************** -->
 700 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
 701 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
 702 <a name="passmanager">What PassManager does
 703 </b></font></td></tr></table><ul>
 704 <!-- *********************************************************************** -->
 705
 706 The <a
 707 href="http://llvm.cs.uiuc.edu/doxygen/PassManager_8h-source.html"><tt>PassManager</tt></a>
 708 <a href="http://llvm.cs.uiuc.edu/doxygen/classPassManager.html">class</a> takes
 709 a list of passes, ensures their <a href="#interaction">prerequisites</a> are set
 710 up correctly, and then schedules passes to run efficiently.  All of the LLVM
 711 tools that run passes use the <tt>PassManager</tt> for execution of these
 712 passes.<p>
 713
 714 The <tt>PassManager</tt> does two main things to try to reduce the execution
 715 time of a series of passes:<p>
 716
 717 <ol>
 718 <li><b>Share analysis results</b> - The PassManager attempts to avoid
 719 recomputing analysis results as much as possible.  This means keeping track of
 720 which analyses are available already, which analyses get invalidated, and which
 721 analyses are needed to be run for a pass.  An important part of work is that the
 722 <tt>PassManager</tt> tracks the exact lifetime of all analysis results, allowing
 723 it to <a href="#releaseMemory">free memory</a> allocated to holding analysis
 724 results as soon as they are no longer needed.<p>
 725
 726 <li><b>Pipeline the execution of passes on the program</b> - The
 727 <tt>PassManager</tt> attempts to get better cache and memory usage behavior out
 728 of a series of passes by pipelining the passes together.  This means that, given
 729 a series of consequtive <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s, it
 730 will execute all of the <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s on
 731 the first function, then all of the <a
 732 href="#FunctionPass"><tt>FunctionPass</tt></a>'s on the second function,
 733 etc... until the entire program has been run through the passes.<p>
 734
 735 This improves the cache behavior of the compiler, because it is only touching
 736 the LLVM program representation for a single function at a time, instead of
 737 traversing the entire program.  It reduces the memory consumption of compiler,
 738 because, for example, only one <a
 739 href="http://llvm.cs.uiuc.edu/doxygen/structDominatorSet.html"><tt>DominatorSet</tt></a>
 740 needs to be calculated at a time.  This also makes it possible some <a
 741 href="#SMP">interesting enhancements</a> in the future.<p>
 742
 743 </ol><p>
 744
 745 The effectiveness of the <tt>PassManager</tt> is influenced directly by how much
 746 information it has about the behaviors of the passes it is scheduling.  For
 747 example, the "preserved" set is intentionally conservative in the face of an
 748 unimplemented <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method.
 749 Not implementing when it should be implemented will have the effect of not
 750 allowing any analysis results to live across the execution of your pass.<p>
 751
 752 The <tt>PassManager</tt> class exposes a <tt>--debug-pass</tt> command line
 753 options that is useful for debugging pass execution, seeing how things work, and
 754 diagnosing when you should be preserving more analyses than you currently are
 755 (To get information about all of the variants of the <tt>--debug-pass</tt>
 756 option, just type '<tt>opt --help-hidden</tt>').<p>
 757
 758 By using the <tt>--debug-pass=Structure</tt> option, for example, we can see how
 759 our <a href="#basiccode">Hello World</a> pass interacts with other passes.  Lets
 760 try it out with the <tt>gcse</tt> and <tt>licm</tt> passes:<p>
 761
 762 <pre>
 763 $ opt -load ../../../lib/Debug/libhello.so -gcse -licm --debug-pass=Structure &lt; hello.bc &gt; /dev/null
 764 Module Pass Manager
 765   Function Pass Manager
 766     Dominator Set Construction
 767     Immediate Dominators Construction
 768     Global Common Subexpression Elimination
 769 --  Immediate Dominators Construction
 770 --  Global Common Subexpression Elimination
 771     Natural Loop Construction
 772     Loop Invariant Code Motion
 773 --  Natural Loop Construction
 774 --  Loop Invariant Code Motion
 775     Module Verifier
 776 --  Dominator Set Construction
 777 --  Module Verifier
 778   Bytecode Writer
 779 --Bytecode Writer
 780 </pre><p>
 781
 782 This output shows us when passes are constructed and when the analysis results
 783 are known to be dead (prefixed with '<tt>--</tt>').  Here we see that GCSE uses
 784 dominator and immediate dominator information to do its job.  The LICM pass uses
 785 natural loop information, which uses dominator sets, but not immediate
 786 dominators.  Because immediate dominators are no longer useful after the GCSE
 787 pass, it is immediately destroyed.  The dominator sets are then reused to
 788 compute natural loop information, which is then used by the LICM pass.<p>
 789
 790 After the LICM pass, the module verifier runs (which is automatically added by
 791 the '<tt>opt</tt>' tool), which uses the dominator set to check that the
 792 resultant LLVM code is well formed.  After it finishes, the dominator set
 793 information is destroyed, after being computed once, and shared by three
 794 passes.<p>
 795
 796 Lets see how this changes when we run the <a href="#basiccode">Hello World</a>
 797 pass in between the two passes:<p>
 798
 799 <pre>
 800 $ opt -load ../../../lib/Debug/libhello.so -gcse -hello -licm --debug-pass=Structure &lt; hello.bc &gt; /dev/null
 801 Module Pass Manager
 802   Function Pass Manager
 803     Dominator Set Construction
 804     Immediate Dominators Construction
 805     Global Common Subexpression Elimination
 806 <b>--  Dominator Set Construction</b>
 807 --  Immediate Dominators Construction
 808 --  Global Common Subexpression Elimination
 809 <b>    Hello World Pass
 810 --  Hello World Pass
 811     Dominator Set Construction</b>
 812     Natural Loop Construction
 813     Loop Invariant Code Motion
 814 --  Natural Loop Construction
 815 --  Loop Invariant Code Motion
 816     Module Verifier
 817 --  Dominator Set Construction
 818 --  Module Verifier
 819   Bytecode Writer
 820 --Bytecode Writer
 821 Hello: __main
 822 Hello: puts
 823 Hello: main
 824 </pre><p>
 825
 826 Here we see that the <a href="#basiccode">Hello World</a> pass has killed the
 827 Dominator Set pass, even though it doesn't modify the code at all!  To fix this,
 828 we need to add the following <a
 829 href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method to our pass:<p>
 830
 831 <pre>
 832     <i>// We don't modify the program, so we preserve all analyses</i>
 833     <b>virtual void</b> getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
 834       AU.setPreservesAll();
 835     }
 836 </pre><p>
 837
 838 Now when we run our pass, we get this output:<p>
 839
 840 <pre>
 841 $ opt -load ../../../lib/Debug/libhello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null
 842 Pass Arguments:  -gcse -hello -licm
 843 Module Pass Manager
 844   Function Pass Manager
 845     Dominator Set Construction
 846     Immediate Dominators Construction
 847     Global Common Subexpression Elimination
 848 --  Immediate Dominators Construction
 849 --  Global Common Subexpression Elimination
 850     Hello World Pass
 851 --  Hello World Pass
 852     Natural Loop Construction
 853     Loop Invariant Code Motion
 854 --  Loop Invariant Code Motion
 855 --  Natural Loop Construction
 856     Module Verifier
 857 --  Dominator Set Construction
 858 --  Module Verifier
 859   Bytecode Writer
 860 --Bytecode Writer
 861 Hello: __main
 862 Hello: puts
 863 Hello: main
 864 </pre><p>
 865
 866 Which shows that we don't accidentally invalidate dominator information
 867 anymore, and therefore do not have to compute it twice.<p>
 868
 869
 870 <!-- _______________________________________________________________________ -->
 871 </ul><h4><a name="releaseMemory"><hr size=0>The <tt>releaseMemory</tt> method</h4><ul>
 872
 873 <pre>
 874   <b>virtual void</b> releaseMemory();
 875 </pre><p>
 876
 877 The <tt>PassManager</tt> automatically determines when to compute analysis
 878 results, and how long to keep them around for.  Because the lifetime of the pass
 879 object itself is effectively the entire duration of the compilation process, we
 880 need some way to free analysis results when they are no longer useful.  The
 881 <tt>releaseMemory</tt> virtual method is the way to do this.<p>
 882
 883 If you are writing an analysis or any other pass that retains a significant
 884 amount of state (for use by another pass which "requires" your pass and uses the
 885 <a href="#getAnalysis">getAnalysis</a> method) you should implement
 886 <tt>releaseMEmory</tt> to, well, release the memory allocated to maintain this
 887 internal state.  This method is called after the <tt>run*</tt> method for the
 888 class, before the next call of <tt>run*</tt> in your pass.<p>
 889
 890
 891 <!-- *********************************************************************** -->
 892 </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
 893 <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
 894 <a name="future">Future extensions planned
 895 </b></font></td></tr></table><ul>
 896 <!-- *********************************************************************** -->
 897
 898 Although the LLVM Pass Infrastructure is very capable as it stands, and does
 899 some nifty stuff, there are things we'd like to add in the future.  Here is
 900 where we are going:<p>
 901
 902 <!-- _______________________________________________________________________ -->
 903 </ul><h4><a name="SMP"><hr size=0>Multithreaded LLVM</h4><ul>
 904
 905 Multiple CPU machines are becoming more command and compilation can never be
 906 fast enough: obviously we should allow for a multithreaded compiler.  Because of
 907 the semantics defined for passes above (specifically they cannot maintain state
 908 across invocations of their <tt>run*</tt> methods), a nice clean way to
 909 implement a multithreaded compiler would be for the <tt>PassManager</tt> class
 910 to create multiple instances of each pass object, and allow the seperate
 911 instances to be hacking on different parts of the program at the same time.<p>
 912
 913 This implementation would prevent each of the passes from having to implement
 914 multithreaded constructs, requiring only the LLVM core to have locking in a few
 915 places (for global resources).  Although this is a simple extension, we simply
 916 haven't had time (or multiprocessor machines, thus a reason) to implement this.
 917 Despite that, we have kept the LLVM passes SMP ready, and you should too.<p>
 918
 919
 920 <!-- _______________________________________________________________________ -->
 921 </ul><h4><a name="ModuleSource"><hr size=0>A new <tt>ModuleSource</tt> interface</h4><ul>
 922
 923 Currently, the <tt>PassManager</tt>'s <tt>run</tt> method takes a <tt><a
 924 href="http://llvm.cs.uiuc.edu/doxygen/classModule.html">Module</a></tt> as
 925 input, and runs all of the passes on this module.  The problem with this
 926 approach is that none of the <tt>PassManager</tt> features can be used for
 927 timing and debugging the actual <b>loading</b> of the module from disk or
 928 standard input.<p>
 929
 930 To solve this problem, eventually the <tt>PassManger</tt> class will accept a
 931 <tt>ModuleSource</tt> object instead of a Module itself.  When complete, this
 932 will also allow for streaming of functions out of the bytecode representation,
 933 allowing us to avoid holding the entire program in memory at once if we only are
 934 dealing with <a href="#FunctionPass">FunctionPass</a>'s.<p>
 935
 936 As part of a different issue, eventually the bytecode loader will be extended to
 937 allow on-demand loading of functions from the bytecode representation, in order
 938 to better support the runtime reoptimizer.  The bytecode format is already
 939 capable of this, the loader just needs to be reworked a bit.<p>
 940
 941
 942 <!-- _______________________________________________________________________ -->
 943 </ul><h4><a name="PassFunctionPass"><hr size=0><tt>Pass</tt>'s requiring <tt>FunctionPass</tt>'s</h4><ul>
 944
 945 Currently it is illegal for a <a href="#Pass"><tt>Pass</tt></a> to require a <a
 946 href="#FunctionPass"><tt>FunctionPass</tt></a>.  This is because there is only
 947 one instance of the <a href="#FunctionPass"><tt>FunctionPass</tt></a> object
 948 ever created, thus nowhere to store information for all of the functions in the
 949 program at the same time.  Although this has come up a couple of times before,
 950 this has always been worked around by factoring one big complicated pass into a
 951 global and an interprocedural part, both of which are distinct.  In the future,
 952 it would be nice to have this though.<p>
 953
 954 Note that it is no problem for a <a
 955 href="#FunctionPass"><tt>FunctionPass</tt></a> to require the results of a <a
 956 href="#Pass"><tt>Pass</tt></a>, only the other way around.<p>
 957
 958
 959 <!-- *********************************************************************** -->
 960 </ul>
 961 <!-- *********************************************************************** -->
 962
 963 <hr><font size-1>
 964 <address><a href="mailto:sabre@nondot.org">Christopher Lattner</a></address>
 965 <!-- Created: Tue Aug  6 15:00:33 CDT 2002 -->
 966 <!-- hhmts start -->
 967 Last modified: Thu Aug  8 15:07:23 CDT 2002
 968 <!-- hhmts end -->
 969 </font></body></html>