| <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> | |
| <html><head><title>Writing an LLVM Pass</title></head> | |
| <body bgcolor=white> | |
| <table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td> <font size=+3 color="#EEEEFF" face="Georgia,Palatino,Times,Roman"><b>Writing an LLVM Pass</b></font></td> | |
| </tr></table> | |
| <ol> | |
| <li><a href="#introduction">Introduction - What is a pass?</a> | |
| <li><a href="#quickstart">Quick Start - Writing hello world</a> | |
| <ul> | |
| <li><a href="#makefile">Setting up the build environment</a> | |
| <li><a href="#basiccode">Basic code required</a> | |
| <li><a href="#running">Running a pass with <tt>opt</tt> | |
| or <tt>analyze</tt></a> | |
| </ul> | |
| <li><a href="#passtype">Pass classes and requirements</a> | |
| <ul> | |
| <li><a href="#ImmutablePass">The <tt>ImmutablePass</tt> class</a> | |
| <li><a href="#Pass">The <tt>Pass</tt> class</a> | |
| <ul> | |
| <li><a href="#run">The <tt>run</tt> method</a> | |
| </ul> | |
| <li><a href="#FunctionPass">The <tt>FunctionPass</tt> class</a> | |
| <ul> | |
| <li><a href="#doInitialization_mod">The <tt>doInitialization(Module | |
| &)</tt> method</a> | |
| <li><a href="#runOnFunction">The <tt>runOnFunction</tt> method</a> | |
| <li><a href="#doFinalization_mod">The <tt>doFinalization(Module | |
| &)</tt> method</a> | |
| </ul> | |
| <li><a href="#BasicBlockPass">The <tt>BasicBlockPass</tt> class</a> | |
| <ul> | |
| <li><a href="#doInitialization_fn">The <tt>doInitialization(Function | |
| &)</tt> method</a> | |
| <li><a href="#runOnBasicBlock">The <tt>runOnBasicBlock</tt> method</a> | |
| <li><a href="#doFinalization_fn">The <tt>doFinalization(Function | |
| &)</tt> method</a> | |
| </ul> | |
| <li><a href="#MachineFunctionPass">The <tt>MachineFunctionPass</tt> | |
| class</a> | |
| <ul> | |
| <li><a href="#runOnMachineFunction">The | |
| <tt>runOnMachineFunction(MachineFunction &)</tt> method</a> | |
| </ul> | |
| </ul> | |
| <li><a href="#registration">Pass Registration</a> | |
| <ul> | |
| <li><a href="#print">The <tt>print</tt> method</a> | |
| </ul> | |
| <li><a href="#interaction">Specifying interactions between passes</a> | |
| <ul> | |
| <li><a href="#getAnalysisUsage">The <tt>getAnalysisUsage</tt> method</a> | |
| <li><a href="#getAnalysis">The <tt>getAnalysis</tt> method</a> | |
| </ul> | |
| <li><a href="#analysisgroup">Implementing Analysis Groups</a> | |
| <ul> | |
| <li><a href="#agconcepts">Analysis Group Concepts</a> | |
| <li><a href="#registerag">Using <tt>RegisterAnalysisGroup</tt></a> | |
| </ul> | |
| <li><a href="#passmanager">What PassManager does</a> | |
| <ul> | |
| <li><a href="#releaseMemory">The <tt>releaseMemory</tt> method</a> | |
| </ul> | |
| <li><a href="#debughints">Using GDB with dynamically loaded passes</a> | |
| <ul> | |
| <li><a href="#breakpoint">Setting a breakpoint in your pass | |
| <li><a href="#debugmisc">Miscellaneous Problems | |
| </ul> | |
| <li><a href="#future">Future extensions planned</a> | |
| <ul> | |
| <li><a href="#SMP">Multithreaded LLVM</a> | |
| <li><a href="#ModuleSource">A new <tt>ModuleSource</tt> interface</a> | |
| <li><a href="#PassFunctionPass"><tt>Pass</tt>'s requiring <tt>FunctionPass</tt>'s</a> | |
| </ul> | |
| <p><b>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></b><p> | |
| </ol><p> | |
| <!-- *********************************************************************** --> | |
| <table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b> | |
| <a name="introduction">Introduction - What is a pass? | |
| </b></font></td></tr></table><ul> | |
| <!-- *********************************************************************** --> | |
| The LLVM Pass Framework is an important part of the LLVM system, because LLVM | |
| passes are where the interesting parts of the compiler exist. Passes perform | |
| the transformations and optimizations that make up the compiler, they build | |
| the analysis results that are used by these transformations, and they are, above | |
| all, a structuring technique for compiler code.<p> | |
| All LLVM passes are subclasses of the <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt> class, which | |
| implement functionality by overriding virtual methods inherited from | |
| <tt>Pass</tt>. Depending on how your pass works, you may be able to inherit | |
| from the <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/structFunctionPass.html">FunctionPass</a></tt> | |
| or <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/structBasicBlockPass.html">BasicBlockPass</a></tt>, | |
| which gives the system more information about what your pass does, and how it | |
| can be combined with other passes. One of the main features of the LLVM Pass | |
| Framework is that it schedules passes to run in an efficient way based on the | |
| constraints that your pass has.<p> | |
| We start by showing you how to construct a pass, everything from setting up the | |
| code, to compiling, loading, and executing it. After the basics are down, more | |
| advanced features are discussed.<p> | |
| <!-- *********************************************************************** --> | |
| </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b> | |
| <a name="quickstart">Quick Start - Writing hello world | |
| </b></font></td></tr></table><ul> | |
| <!-- *********************************************************************** --> | |
| Here we describe how to write the "hello world" of passes. The "Hello" pass is | |
| designed to simply print out the name of non-external functions that exist in | |
| the program being compiled. It does not modify the program at all, just | |
| inspects it. The source code and files for this pass are available in the LLVM | |
| source tree in the <tt>lib/Transforms/Hello</tt> directory.<p> | |
| <!-- ======================================================================= --> | |
| </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td> </td><td width="100%"> | |
| <font color="#EEEEFF" face="Georgia,Palatino"><b> | |
| <a name="makefile">Setting up the build environment | |
| </b></font></td></tr></table><ul> | |
| First thing you need to do is create a new directory somewhere in the LLVM | |
| source base. For this example, we'll assume that you made | |
| "<tt>lib/Transforms/Hello</tt>". The first thing you must do is set up a build | |
| script (Makefile) that will compile the source code for the new pass. To do | |
| this, copy this into "<tt>Makefile</tt>":<p> | |
| </ul><hr><ul><pre> | |
| # Makefile for hello pass | |
| # Path to top level of LLVM heirarchy | |
| LEVEL = ../../.. | |
| # Name of the library to build | |
| LIBRARYNAME = hello | |
| # Build a dynamically loadable shared object | |
| SHARED_LIBRARY = 1 | |
| # Include the makefile implementation stuff | |
| include $(LEVEL)/Makefile.common | |
| </pre></ul><hr><ul><p> | |
| This makefile specifies that all of the <tt>.cpp</tt> files in the current | |
| directory are to be compiled and linked together into a | |
| <tt>lib/Debug/libhello.so</tt> shared object that can be dynamically loaded by | |
| the <tt>opt</tt> or <tt>analyze</tt> tools.<p> | |
| Now that we have the build scripts set up, we just need to write the code for | |
| the pass itself.<p> | |
| <!-- ======================================================================= --> | |
| </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td> </td><td width="100%"> | |
| <font color="#EEEEFF" face="Georgia,Palatino"><b> | |
| <a name="basiccode">Basic code required | |
| </b></font></td></tr></table><ul> | |
| Now that we have a way to compile our new pass, we just have to write it. Start | |
| out with:<p> | |
| <pre> | |
| <b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Pass_8h-source.html">llvm/Pass.h</a>" | |
| <b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Function_8h-source.html">llvm/Function.h</a>" | |
| </pre> | |
| Which are needed because we are writing a <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt>, and we are | |
| operating on <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/classFunction.html">Function</a></tt>'s.<p> | |
| Next we have:<p> | |
| <pre> | |
| <b>namespace</b> { | |
| </pre><p> | |
| ... which starts out an anonymous namespace. Anonymous namespaces are to C++ | |
| what the "<tt>static</tt>" keyword is to C (at global scope). It makes the | |
| things declared inside of the anonymous namespace only visible to the current | |
| file. If you're not familiar with them, consult a decent C++ book for more | |
| information.<p> | |
| Next, we declare our pass itself:<p> | |
| <pre> | |
| <b>struct</b> Hello : <b>public</b> <a href="#FunctionPass">FunctionPass</a> { | |
| </pre><p> | |
| This declares a "<tt>Hello</tt>" class that is a subclass of <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/structFunctionPass.html">FunctionPass</a></tt>. | |
| The different builtin pass subclasses are described in detail <a | |
| href="#passtype">later</a>, but for now, know that <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s | |
| operate a function at a time.<p> | |
| <pre> | |
| <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &F) { | |
| std::cerr << "<i>Hello: </i>" << F.getName() << "\n"; | |
| <b>return false</b>; | |
| } | |
| }; <i>// end of struct Hello</i> | |
| </pre> | |
| We declare a "<a href="#runOnFunction"><tt>runOnFunction</tt></a>" method, which | |
| overloads an abstract virtual method inherited from <a | |
| href="#FunctionPass"><tt>FunctionPass</tt></a>. This is where we are supposed | |
| to do our thing, so we just print out our message with the name of each | |
| function.<p> | |
| <pre> | |
| RegisterOpt<Hello> X("<i>hello</i>", "<i>Hello World Pass</i>"); | |
| } <i>// end of anonymous namespace</i> | |
| </pre><p> | |
| Lastly, we register our class <tt>Hello</tt>, giving it a command line argument | |
| "<tt>hello</tt>", and a name "<tt>Hello World Pass</tt>". There are several | |
| different ways of <a href="#registration">registering your pass</a>, depending | |
| on what it is to be used for. For "optimizations" we use the | |
| <tt>RegisterOpt</tt> template.<p> | |
| As a whole, the <tt>.cpp</tt> file looks like:<p> | |
| <pre> | |
| <b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Pass_8h-source.html">llvm/Pass.h</a>" | |
| <b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Function_8h-source.html">llvm/Function.h</a>" | |
| <b>namespace</b> { | |
| <b>struct Hello</b> : <b>public</b> <a href="#FunctionPass">FunctionPass</a> { | |
| <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &F) { | |
| std::cerr << "<i>Hello: </i>" << F.getName() << "\n"; | |
| <b>return false</b>; | |
| } | |
| }; | |
| RegisterOpt<Hello> X("<i>hello</i>", "<i>Hello World Pass</i>"); | |
| } | |
| </pre><p> | |
| Now that it's all together, compile the file with a simple "<tt>gmake</tt>" | |
| command in the local directory and you should get a new | |
| "<tt>lib/Debug/libhello.so</tt> file. Note that everything in this file is | |
| contained in an anonymous namespace: this reflects the fact that passes are self | |
| contained units that do not need external interfaces (although they can have | |
| them) to be useful.<p> | |
| <!-- ======================================================================= --> | |
| </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td> </td><td width="100%"> | |
| <font color="#EEEEFF" face="Georgia,Palatino"><b> | |
| <a name="running">Running a pass with <tt>opt</tt> or <tt>analyze</tt> | |
| </b></font></td></tr></table><ul> | |
| Now that you have a brand new shiny <tt>.so</tt> file, we can use the | |
| <tt>opt</tt> command to run an LLVM program through your pass. Because you | |
| registered your pass with the <tt>RegisterOpt</tt> template, you will be able to | |
| use the <tt>opt</tt> tool to access it, once loaded.<p> | |
| To test it, follow the example at the end of the <a | |
| href="GettingStarted.html">Getting Started Guide</a> to compile "Hello World" to | |
| LLVM. We can now run the bytecode file (<tt>hello.bc</tt>) for the program | |
| through our transformation like this (or course, any bytecode file will | |
| work):<p> | |
| <pre> | |
| $ opt -load ../../../lib/Debug/libhello.so -hello < hello.bc > /dev/null | |
| Hello: __main | |
| Hello: puts | |
| Hello: main | |
| </pre><p> | |
| The '<tt>-load</tt>' option specifies that '<tt>opt</tt>' should load your pass | |
| as a shared object, which makes '<tt>-hello</tt>' a valid command line argument | |
| (which is one reason you need to <a href="#registration">register your | |
| pass</a>). Because the hello pass does not modify the program in any | |
| interesting way, we just throw away the result of <tt>opt</tt> (sending it to | |
| <tt>/dev/null</tt>).<p> | |
| To see what happened to the other string you registered, try running | |
| <tt>opt</tt> with the <tt>--help</tt> option:<p> | |
| <pre> | |
| $ opt -load ../../../lib/Debug/libhello.so --help | |
| OVERVIEW: llvm .bc -> .bc modular optimizer | |
| USAGE: opt [options] <input bytecode> | |
| OPTIONS: | |
| Optimizations available: | |
| ... | |
| -funcresolve - Resolve Functions | |
| -gcse - Global Common Subexpression Elimination | |
| -globaldce - Dead Global Elimination | |
| <b>-hello - Hello World Pass</b> | |
| -indvars - Canonicalize Induction Variables | |
| -inline - Function Integration/Inlining | |
| -instcombine - Combine redundant instructions | |
| ... | |
| </pre><p> | |
| The pass name get added as the information string for your pass, giving some | |
| documentation to users of <tt>opt</tt>. Now that you have a working pass, you | |
| would go ahead and make it do the cool transformations you want. Once you get | |
| it all working and tested, it may become useful to find out how fast your pass | |
| is. The <a href="#passManager"><tt>PassManager</tt></a> provides a nice command | |
| line option (<tt>--time-passes</tt>) that allows you to get information about | |
| the execution time of your pass along with the other passes you queue up. For | |
| example:<p> | |
| <pre> | |
| $ opt -load ../../../lib/Debug/libhello.so -hello -time-passes < hello.bc > /dev/null | |
| Hello: __main | |
| Hello: puts | |
| Hello: main | |
| =============================================================================== | |
| ... Pass execution timing report ... | |
| =============================================================================== | |
| Total Execution Time: 0.02 seconds (0.0479059 wall clock) | |
| ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Pass Name --- | |
| 0.0100 (100.0%) 0.0000 ( 0.0%) 0.0100 ( 50.0%) 0.0402 ( 84.0%) Bytecode Writer | |
| 0.0000 ( 0.0%) 0.0100 (100.0%) 0.0100 ( 50.0%) 0.0031 ( 6.4%) Dominator Set Construction | |
| 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0013 ( 2.7%) Module Verifier | |
| <b> 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0033 ( 6.9%) Hello World Pass</b> | |
| 0.0100 (100.0%) 0.0100 (100.0%) 0.0200 (100.0%) 0.0479 (100.0%) TOTAL | |
| </pre><p> | |
| As you can see, our implementation above is pretty fast :). The additional | |
| passes listed are automatically inserted by the '<tt>opt</tt>' tool to verify | |
| that the LLVM emitted by your pass is still valid and well formed LLVM, which | |
| hasn't been broken somehow. | |
| Now that you have seen the basics of the mechanics behind passes, we can talk | |
| about some more details of how they work and how to use them.<p> | |
| <!-- *********************************************************************** --> | |
| </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b> | |
| <a name="passtype">Pass classes and requirements | |
| </b></font></td></tr></table><ul> | |
| <!-- *********************************************************************** --> | |
| One of the first things that you should do when designing a new pass is to | |
| decide what class you should subclass for your pass. The <a | |
| href="#basiccode">Hello World</a> example uses the <tt><a | |
| href="#FunctionPass">FunctionPass</a></tt> class for its implementation, but we | |
| did not discuss why or when this should occur. Here we talk about the classes | |
| available, from the most general to the most specific.<p> | |
| When choosing a superclass for your Pass, you should choose the <b>most | |
| specific</b> class possible, while still being able to meet the requirements | |
| listed. This gives the LLVM Pass Infrastructure information necessary to | |
| optimize how passes are run, so that the resultant compiler isn't unneccesarily | |
| slow.<p> | |
| <!-- ======================================================================= --> | |
| </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td> </td><td width="100%"> | |
| <font color="#EEEEFF" face="Georgia,Palatino"><b> | |
| <a name="ImmutablePass">The <tt>ImmutablePass</tt> class | |
| </b></font></td></tr></table><ul> | |
| The most plain and boring type of pass is the "<tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/structImmutablePass.html">ImmutablePass</a></tt>" | |
| class. This pass type is used for passes that do not have to be run, do not | |
| change state, and never need to be updated. This is not a normal type of | |
| transformation or analysis, but can provide information about the current | |
| compiler configuration.<p> | |
| Although this pass class is very infrequently used, it is important for | |
| providing information about the current target machine being compiled for, and | |
| other static information that can affect the various transformations.<p> | |
| <tt>ImmutablePass</tt>'s never invalidate other transformations, are never | |
| invalidated, and are never "run".<p> | |
| <!-- ======================================================================= --> | |
| </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td> </td><td width="100%"> | |
| <font color="#EEEEFF" face="Georgia,Palatino"><b> | |
| <a name="Pass">The <tt>Pass</tt> class | |
| </b></font></td></tr></table><ul> | |
| The "<tt><a href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt>" | |
| class is the most general of all superclasses that you can use. Deriving from | |
| <tt>Pass</tt> indicates that your pass uses the entire program as a unit, | |
| refering to function bodies in no predictable order, or adding and removing | |
| functions. Because nothing is known about the behavior of direct <tt>Pass</tt> | |
| subclasses, no optimization can be done for their execution.<p> | |
| To write a correct <tt>Pass</tt> subclass, derive from <tt>Pass</tt> and | |
| overload the <tt>run</tt> method with the following signature:<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="run"><hr size=0>The <tt>run</tt> method</h4><ul> | |
| <pre> | |
| <b>virtual bool</b> run(Module &M) = 0; | |
| </pre><p> | |
| The <tt>run</tt> method performs the interesting work of the pass, and should | |
| return true if the module was modified by the transformation, false | |
| otherwise.<p> | |
| <!-- ======================================================================= --> | |
| </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td> </td><td width="100%"> | |
| <font color="#EEEEFF" face="Georgia,Palatino"><b> | |
| <a name="FunctionPass">The <tt>FunctionPass</tt> class | |
| </b></font></td></tr></table><ul> | |
| In contrast to direct <tt>Pass</tt> subclasses, direct <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">FunctionPass</a></tt> | |
| subclasses do have a predictable, local behavior that can be expected by the | |
| system. All <tt>FunctionPass</tt> execute on each function in the program | |
| independent of all of the other functions in the program. | |
| <tt>FunctionPass</tt>'s do not require that they are executed in a particular | |
| order, and <tt>FunctionPass</tt>'s do not modify external functions.<p> | |
| To be explicit, <tt>FunctionPass</tt> subclasses are not allowed to:<p> | |
| <ol> | |
| <li>Modify a Function other than the one currently being processed. | |
| <li>Add or remove Function's from the current Module. | |
| <li>Add or remove global variables from the current Module. | |
| <li>Maintain state across invocations of | |
| <a href="#runOnFunction"><tt>runOnFunction</tt></a> (including global data) | |
| </ol><p> | |
| Implementing a <tt>FunctionPass</tt> is usually straightforward (See the <a | |
| href="#basiccode">Hello World</a> pass for example). <tt>FunctionPass</tt>'s | |
| may overload three virtual methods to do their work. All of these methods | |
| should return true if they modified the program, or false if they didn't.<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="doInitialization_mod"><hr size=0>The | |
| <tt>doInitialization(Module &)</tt> method</h4><ul> | |
| <pre> | |
| <b>virtual bool</b> doInitialization(Module &M); | |
| </pre><p> | |
| The <tt>doIninitialize</tt> method is allowed to do most of the things that | |
| <tt>FunctionPass</tt>'s are not allowed to do. They can add and remove | |
| functions, get pointers to functions, etc. The <tt>doInitialization</tt> method | |
| is designed to do simple initialization type of stuff that does not depend on | |
| the functions being processed. The <tt>doInitialization</tt> method call is not | |
| scheduled to overlap with any other pass executions (thus it should be very | |
| fast).<p> | |
| A good example of how this method should be used is the <a | |
| href="http://llvm.cs.uiuc.edu/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations</a> | |
| pass. This pass converts <tt>malloc</tt> and <tt>free</tt> instructions into | |
| platform dependent <tt>malloc()</tt> and <tt>free()</tt> function calls. It | |
| uses the <tt>doInitialization</tt> method to get a reference to the malloc and | |
| free functions that it needs, adding prototypes to the module if necessary.<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="runOnFunction"><hr size=0>The <tt>runOnFunction</tt> method</h4><ul> | |
| <pre> | |
| <b>virtual bool</b> runOnFunction(Function &F) = 0; | |
| </pre><p> | |
| The <tt>runOnFunction</tt> method must be implemented by your subclass to do the | |
| transformation or analysis work of your pass. As usual, a true value should be | |
| returned if the function is modified.<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="doFinalization_mod"><hr size=0>The <tt>doFinalization(Module &)</tt> method</h4><ul> | |
| <pre> | |
| <b>virtual bool</b> doFinalization(Module &M); | |
| </pre></p> | |
| The <tt>doFinalization</tt> method is an infrequently used method that is called | |
| when the pass framework has finished calling <a | |
| href="#runOnFunction"><tt>runOnFunction</tt></a> for every function in the | |
| program being compiled.<p> | |
| <!-- ======================================================================= --> | |
| </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td> </td><td width="100%"> | |
| <font color="#EEEEFF" face="Georgia,Palatino"><b> | |
| <a name="BasicBlockPass">The <tt>BasicBlockPass</tt> class</a> | |
| </b></font></td></tr></table><ul> | |
| <tt>BasicBlockPass</tt>'s are just like <a | |
| href="#FunctionPass"><tt>FunctionPass</tt></a>'s, except that they must limit | |
| their scope of inspection and modification to a single basic block at a time. | |
| As such, they are <b>not</b> allowed to do any of the following:<p> | |
| <ol> | |
| <li>Modify or inspect any basic blocks outside of the current one | |
| <li>Maintain state across invocations of | |
| <a href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a> | |
| <li>Modify the constrol flow graph (by altering terminator instructions) | |
| <li>Any of the things verboten for | |
| <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s. | |
| </ol><p> | |
| <tt>BasicBlockPass</tt>'s are useful for traditional local and "peephole" | |
| optimizations. They may override the same <a | |
| href="#doInitialization_mod"><tt>doInitialization(Module &)</tt></a> and <a | |
| href="#doFinalization_mod"><tt>doFinalization(Module &)</tt></a> methods that <a | |
| href="#FunctionPass"><tt>FunctionPass</tt></a>'s have, but also have the following virtual methods that may also be implemented:<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="doInitialization_fn"><hr size=0>The | |
| <tt>doInitialization(Function &)</tt> method</h4><ul> | |
| <pre> | |
| <b>virtual bool</b> doInitialization(Function &F); | |
| </pre><p> | |
| The <tt>doIninitialize</tt> method is allowed to do most of the things that | |
| <tt>BasicBlockPass</tt>'s are not allowed to do, but that | |
| <tt>FunctionPass</tt>'s can. The <tt>doInitialization</tt> method is designed | |
| to do simple initialization type of stuff that does not depend on the | |
| BasicBlocks being processed. The <tt>doInitialization</tt> method call is not | |
| scheduled to overlap with any other pass executions (thus it should be very | |
| fast).<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="runOnBasicBlock"><hr size=0>The <tt>runOnBasicBlock</tt> method</h4><ul> | |
| <pre> | |
| <b>virtual bool</b> runOnBasicBlock(BasicBlock &BB) = 0; | |
| </pre><p> | |
| Override this function to do the work of the <tt>BasicBlockPass</tt>. This | |
| function is not allowed to inspect or modify basic blocks other than the | |
| parameter, and are not allowed to modify the CFG. A true value must be returned | |
| if the basic block is modified.<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="doFinalization_fn"><hr size=0>The <tt>doFinalization(Function | |
| &)</tt> method</h4><ul> | |
| <pre> | |
| <b>virtual bool</b> doFinalization(Function &F); | |
| </pre></p> | |
| The <tt>doFinalization</tt> method is an infrequently used method that is called | |
| when the pass framework has finished calling <a | |
| href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a> for every BasicBlock in the | |
| program being compiled. This can be used to perform per-function | |
| finalization.<p> | |
| <!-- ======================================================================= --> | |
| </ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td> </td><td width="100%"> | |
| <font color="#EEEEFF" face="Georgia,Palatino"><b> | |
| <a name="MachineFunctionPass">The <tt>MachineFunctionPass</tt> class | |
| </b></font></td></tr></table><ul> | |
| A <tt>MachineFunctionPass</tt> executes on the machine-dependent | |
| representation of each LLVM function in the program, | |
| independent of all of the other functions in the program. | |
| A <tt>MachineFunctionPass</tt> is also a <tt>FunctionPass</tt>, so all | |
| the restrictions that apply to a <tt>FunctionPass</tt> also apply to it. | |
| <tt>MachineFunctionPass</tt>es also have additional restrictions. In | |
| particular, <tt>MachineFunctionPass</tt>es are not allowed to do any of | |
| the following: | |
| <ol> | |
| <li>Modify any LLVM Instructions, BasicBlocks or Functions. | |
| <li>Modify a MachineFunction other than the one currently being processed. | |
| <li>Add or remove MachineFunctions from the current Module. | |
| <li>Add or remove global variables from the current Module. | |
| <li>Maintain state across invocations of | |
| <a href="#runOnMachineFunction"><tt>runOnMachineFunction</tt></a> (including global data) | |
| </ol><p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="runOnMachineFunction"><hr size=0>The | |
| <tt>runOnMachineFunction(MachineFunction &MF)</tt> method</h4><ul> | |
| <pre> | |
| <b>virtual bool</b> runOnMachineFunction(MachineFunction &MF) = 0; | |
| </pre></p> | |
| <tt>runOnMachineFunction</tt> can be considered the main entry point | |
| of a <tt>MachineFunctionPass</tt>; that is, you should override this | |
| method to do the work of your <tt>MachineFunctionPass</tt>. <p> | |
| The <tt>runOnMachineFunction</tt> method is called on every | |
| <tt>MachineFunction</tt> in a <tt>Module</tt>, so that the | |
| <tt>MachineFunctionPass</tt> may perform optimizations on the | |
| machine-dependent representation of the function. If you want to get | |
| at the LLVM <tt>Function</tt> for the <tt>MachineFunction</tt> you're | |
| working on, use <tt>MachineFunction</tt>'s <tt>getFunction()</tt> | |
| accessor method -- but remember, you may not modify the LLVM | |
| <tt>Function</tt> or its contents from a | |
| <tt>MachineFunctionPass</tt>. <p> | |
| <!-- *********************************************************************** --> | |
| </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b> | |
| <a name="registration">Pass registration | |
| </b></font></td></tr></table><ul> | |
| <!-- *********************************************************************** --> | |
| In the <a href="#basiccode">Hello World</a> example pass we illustrated how pass | |
| registration works, and discussed some of the reasons that it is used and what | |
| it does. Here we discuss how and why passes are registered.<p> | |
| Passes can be registered in several different ways. Depending on the general | |
| classification of the pass, you should use one of the following templates to | |
| register the pass:<p> | |
| <ul> | |
| <li><b><tt>RegisterOpt</tt></b> - This template should be used when you are | |
| registering a pass that logically should be available for use in the | |
| '<tt>opt</tt>' utility.<p> | |
| <li><b><tt>RegisterAnalysis</tt></b> - This template should be used when you are | |
| registering a pass that logically should be available for use in the | |
| '<tt>analysis</tt>' utility.<p> | |
| <li><b><tt>RegisterLLC</tt></b> - This template should be used when you are | |
| registering a pass that logically should be available for use in the | |
| '<tt>llc</tt>' utility.<p> | |
| <li><b><tt>RegisterPass</tt></b> - This is the generic form of the | |
| <tt>Register*</tt> templates that should be used if you want your pass listed by | |
| multiple or no utilities. This template takes an extra third argument that | |
| specifies which tools it should be listed in. See the <a | |
| href="http://llvm.cs.uiuc.edu/doxygen/PassSupport_8h-source.html">PassSupport.h</a> | |
| file for more information.<p> | |
| </ul><p> | |
| Regardless of how you register your pass, you must specify at least two | |
| parameters. The first parameter is the name of the pass that is to be used on | |
| the command line to specify that the pass should be added to a program (for | |
| example <tt>opt</tt> or <tt>analyze</tt>). The second argument is the name of | |
| the pass, which is to be used for the <tt>--help</tt> output of programs, as | |
| well as for debug output generated by the <tt>--debug-pass</tt> option.<p> | |
| If you pass is constructed by its default constructor, you only ever have to | |
| pass these two arguments. If, on the other hand, you require other information | |
| (like target specific information), you must pass an additional argument. This | |
| argument is a pointer to a function used to create the pass. For an example of | |
| how this works, look at the <a | |
| href="http://llvm.cs.uiuc.edu/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations.cpp</a> | |
| file.<p> | |
| If a pass is registered to be used by the <tt>analyze</tt> utility, you should | |
| implement the virtual <tt>print</tt> method:<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="print"><hr size=0>The <tt>print</tt> method</h4><ul> | |
| <pre> | |
| <b>virtual void</b> print(std::ostream &O, <b>const</b> Module *M) <b>const</b>; | |
| </pre><p> | |
| The <tt>print</tt> method must be implemented by "analyses" in order to print a | |
| human readable version of the analysis results. This is useful for debugging an | |
| analysis itself, as well as for other people to figure out how an analysis | |
| works. The <tt>analyze</tt> tool uses this method to generate its output.<p> | |
| The <tt>ostream</tt> parameter specifies the stream to write the results on, and | |
| the <tt>Module</tt> parameter gives a pointer to the top level module of the | |
| program that has been analyzed. Note however that this pointer may be null in | |
| certain circumstances (such as calling the <tt>Pass::dump()</tt> from a | |
| debugger), so it should only be used to enhance debug output, it should not be | |
| depended on.<p> | |
| <!-- *********************************************************************** --> | |
| </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b> | |
| <a name="interaction">Specifying interactions between passes | |
| </b></font></td></tr></table><ul> | |
| <!-- *********************************************************************** --> | |
| One of the main responsibilities of the <tt>PassManager</tt> is the make sure | |
| that passes interact with each other correctly. Because <tt>PassManager</tt> | |
| tries to <a href="#passmanager">optimize the execution of passes</a> it must | |
| know how the passes interact with each other and what dependencies exist between | |
| the various passes. To track this, each pass can declare the set of passes that | |
| are required to be executed before the current pass, and the passes which are | |
| invalidated by the current pass.<p> | |
| Typically this functionality is used to require that analysis results are | |
| computed before your pass is run. Running arbitrary transformation passes can | |
| invalidate the computed analysis results, which is what the invalidation set | |
| specifies. If a pass does not implement the <tt><a | |
| href="#getAnalysisUsage">getAnalysisUsage</a></tt> method, it defaults to not | |
| having any prerequisite passes, and invalidating <b>all</b> other passes.<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="getAnalysisUsage"><hr size=0>The <tt>getAnalysisUsage</tt> method</h4><ul> | |
| <pre> | |
| <b>virtual void</b> getAnalysisUsage(AnalysisUsage &Info) <b>const</b>; | |
| </pre><p> | |
| By implementing the <tt>getAnalysisUsage</tt> method, the required and | |
| invalidated sets may be specified for your transformation. The implementation | |
| should fill in the <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/classAnalysisUsage.html">AnalysisUsage</a></tt> | |
| object with information about which passes are required and not invalidated. To do this, the following set methods are provided by the <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/classAnalysisUsage.html">AnalysisUsage</a></tt> class:<p> | |
| <pre> | |
| <i>// addRequires - Add the specified pass to the required set for your pass.</i> | |
| <b>template</b><<b>class</b> PassClass> | |
| AnalysisUsage &AnalysisUsage::addRequired(); | |
| <i>// addPreserved - Add the specified pass to the set of analyses preserved by | |
| // this pass</i> | |
| <b>template</b><<b>class</b> PassClass> | |
| AnalysisUsage &AnalysisUsage::addPreserved(); | |
| <i>// setPreservesAll - Call this if the pass does not modify its input at all</i> | |
| <b>void</b> AnalysisUsage::setPreservesAll(); | |
| <i>// setPreservesCFG - This function should be called by the pass, iff they do not: | |
| // | |
| // 1. Add or remove basic blocks from the function | |
| // 2. Modify terminator instructions in any way. | |
| // | |
| // This is automatically implied for <a href="#BasicBlockPass">BasicBlockPass</a>'s | |
| //</i> | |
| <b>void</b> AnalysisUsage::setPreservesCFG(); | |
| </pre><p> | |
| Some examples of how to use these methods are:<p> | |
| <pre> | |
| <i>// This is an example implementation from an analysis, which does not modify | |
| // the program at all, yet has a prerequisite.</i> | |
| <b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/structPostDominanceFrontier.html">PostDominanceFrontier</a>::getAnalysisUsage(AnalysisUsage &AU) <b>const</b> { | |
| AU.setPreservesAll(); | |
| AU.addRequired<<a href="http://llvm.cs.uiuc.edu/doxygen/structPostDominatorTree.html">PostDominatorTree</a>>(); | |
| } | |
| </pre><p> | |
| and:<p> | |
| <pre> | |
| <i>// This example modifies the program, but does not modify the CFG</i> | |
| <b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/structLICM.html">LICM</a>::getAnalysisUsage(AnalysisUsage &AU) <b>const</b> { | |
| AU.setPreservesCFG(); | |
| AU.addRequired<<a href="http://llvm.cs.uiuc.edu/doxygen/classLoopInfo.html">LoopInfo</a>>(); | |
| } | |
| </pre><p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="getAnalysis"><hr size=0>The <tt>getAnalysis<></tt> method</h4><ul> | |
| The <tt>Pass::getAnalysis<></tt> method is inherited by your class, | |
| providing you with access to the passes that you declared that you required with | |
| the <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method. It takes | |
| a single template argument that specifies which pass class you want, and returns | |
| a reference to that pass.<p> | |
| <pre> | |
| <b>template</b><<b>typename</b> PassClass> | |
| AnalysisType &getAnalysis(); | |
| </pre><p> | |
| This method call returns a reference to the pass desired. You may get a runtime | |
| assertion failure if you attempt to get an analysis that you did not declare as | |
| required in your <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> | |
| implementation. This method can be called by your <tt>run*</tt> method | |
| implementation, or by any other local method invoked by your <tt>run*</tt> | |
| method.<p> | |
| <!-- *********************************************************************** --> | |
| </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b> | |
| <a name="analysisgroup">Implementing Analysis Groups | |
| </b></font></td></tr></table><ul> | |
| <!-- *********************************************************************** --> | |
| Now that we understand the basics of how passes are defined, how the are used, | |
| and how they are required from other passes, it's time to get a little bit | |
| fancier. All of the pass relationships that we have seen so far are very | |
| simple: one pass depends on one other specific pass to be run before it can run. | |
| For many applications, this is great, for others, more flexibility is | |
| required.<p> | |
| In particular, some analyses are defined such that there is a single simple | |
| interface to the analysis results, but multiple ways of calculating them. | |
| Consider alias analysis for example. The most trivial alias analysis returns | |
| "may alias" for any alias query. The most sophisticated analysis a | |
| flow-sensitive, context-sensitive interprocedural analysis that can take a | |
| significant amount of time to execute (and obviously, there is a lot of room | |
| between these two extremes for other implementations). To cleanly support | |
| situations like this, the LLVM Pass Infrastructure supports the notion of | |
| Analysis Groups.<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="agconcepts"><hr size=0>Analysis Group Concepts</h4><ul> | |
| An Analysis Group is a single simple interface that may be implemented by | |
| multiple different passes. Analysis Groups can be given human readable names | |
| just like passes, but unlike passes, they need not derive from the <tt>Pass</tt> | |
| class. An analysis group may have one or more implementations, one of which is | |
| the "default" implementation.<p> | |
| Analysis groups are used by client passes just like other passes are: the | |
| <tt>AnalysisUsage::addRequired()</tt> and <tt>Pass::getAnalysis()</tt> methods. | |
| In order to resolve this requirement, the <a href="#passmanager">PassManager</a> | |
| scans the available passes to see if any implementations of the analysis group | |
| are available. If none is available, the default implementation is created for | |
| the pass to use. All standard rules for <A href="#interaction">interaction | |
| between passes</a> still apply.<p> | |
| Although <a href="#registration">Pass Registration</a> is optional for normal | |
| passes, all analysis group implementations must be registered, and must use the | |
| <A href="#registerag"><tt>RegisterAnalysisGroup</tt></a> template to join the | |
| implementation pool. Also, a default implementation of the interface | |
| <b>must</b> be registered with <A | |
| href="#registerag"><tt>RegisterAnalysisGroup</tt></a>.<p> | |
| As a concrete example of an Analysis Group in action, consider the <a | |
| href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a> | |
| analysis group. The default implementation of the alias analysis interface (the | |
| <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">basicaa</a></tt> | |
| pass) just does a few simple checks that don't require significant analysis to | |
| compute (such as: two different globals can never alias each other, etc). | |
| Passes that use the <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a></tt> | |
| interface (for example the <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/classGCSE.html">gcse</a></tt> pass), do not care which implementation | |
| of alias analysis is actually provided, they just use the designated | |
| interface.<p> | |
| From the user's perspective, commands work just like normal. Issuing the | |
| command '<tt>opt -gcse ...</tt>' will cause the <tt>basicaa</tt> class to be | |
| instantiated and added to the pass sequence. Issuing the command '<tt>opt | |
| -somefancyaa -gcse ...</tt>' will cause the <tt>gcse</tt> pass to use the | |
| <tt>somefancyaa</tt> alias analysis (which doesn't actually exist, it's just a | |
| hypothetical example) instead.<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="registerag"><hr size=0>Using <tt>RegisterAnalysisGroup</tt></h4><ul> | |
| The <tt>RegisterAnalysisGroup</tt> template is used to register the analysis | |
| group itself as well as add pass implementations to the analysis group. First, | |
| an analysis should be registered, with a human readable name provided for it. | |
| Unlike registration of passes, there is no command line argument to be specified | |
| for the Analysis Group Interface itself, because it is "abstract":<p> | |
| <pre> | |
| <b>static</b> RegisterAnalysisGroup<<a href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a>> A("<i>Alias Analysis</i>"); | |
| </pre><p> | |
| Once the analysis is registered, passes can declare that they are valid | |
| implementations of the interface by using the following code:<p> | |
| <pre> | |
| <b>namespace</b> { | |
| //<i> Analysis Group implementations <b>must</b> be registered normally...</i> | |
| RegisterOpt<FancyAA> | |
| B("<i>somefancyaa</i>", "<i>A more complex alias analysis implementation</i>"); | |
| //<i> Declare that we implement the AliasAnalysis interface</i> | |
| RegisterAnalysisGroup<<a href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a>, FancyAA> C; | |
| } | |
| </pre><p> | |
| This just shows a class <tt>FancyAA</tt> that is registered normally, then uses | |
| the <tt>RegisterAnalysisGroup</tt> template to "join" the <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a></tt> | |
| analysis group. Every implementation of an analysis group should join using | |
| this template. A single pass may join multiple different analysis groups with | |
| no problem.<p> | |
| <pre> | |
| <b>namespace</b> { | |
| //<i> Analysis Group implementations <b>must</b> be registered normally...</i> | |
| RegisterOpt<<a href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a>> | |
| D("<i>basicaa</i>", "<i>Basic Alias Analysis (default AA impl)</i>"); | |
| //<i> Declare that we implement the AliasAnalysis interface</i> | |
| RegisterAnalysisGroup<<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>> E; | |
| } | |
| </pre><p> | |
| Here we show how the default implementation is specified (using the extra | |
| argument to the <tt>RegisterAnalysisGroup</tt> template). There must be exactly | |
| one default implementation available at all times for an Analysis Group to be | |
| used. Here we declare that the <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a></tt> | |
| pass is the default implementation for the interface.<p> | |
| <!-- *********************************************************************** --> | |
| </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b> | |
| <a name="passmanager">What PassManager does | |
| </b></font></td></tr></table><ul> | |
| <!-- *********************************************************************** --> | |
| The <a | |
| href="http://llvm.cs.uiuc.edu/doxygen/PassManager_8h-source.html"><tt>PassManager</tt></a> | |
| <a href="http://llvm.cs.uiuc.edu/doxygen/classPassManager.html">class</a> takes | |
| a list of passes, ensures their <a href="#interaction">prerequisites</a> are set | |
| up correctly, and then schedules passes to run efficiently. All of the LLVM | |
| tools that run passes use the <tt>PassManager</tt> for execution of these | |
| passes.<p> | |
| The <tt>PassManager</tt> does two main things to try to reduce the execution | |
| time of a series of passes:<p> | |
| <ol> | |
| <li><b>Share analysis results</b> - The PassManager attempts to avoid | |
| recomputing analysis results as much as possible. This means keeping track of | |
| which analyses are available already, which analyses get invalidated, and which | |
| analyses are needed to be run for a pass. An important part of work is that the | |
| <tt>PassManager</tt> tracks the exact lifetime of all analysis results, allowing | |
| it to <a href="#releaseMemory">free memory</a> allocated to holding analysis | |
| results as soon as they are no longer needed.<p> | |
| <li><b>Pipeline the execution of passes on the program</b> - The | |
| <tt>PassManager</tt> attempts to get better cache and memory usage behavior out | |
| of a series of passes by pipelining the passes together. This means that, given | |
| a series of consequtive <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s, it | |
| will execute all of the <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s on | |
| the first function, then all of the <a | |
| href="#FunctionPass"><tt>FunctionPass</tt></a>'s on the second function, | |
| etc... until the entire program has been run through the passes.<p> | |
| This improves the cache behavior of the compiler, because it is only touching | |
| the LLVM program representation for a single function at a time, instead of | |
| traversing the entire program. It reduces the memory consumption of compiler, | |
| because, for example, only one <a | |
| href="http://llvm.cs.uiuc.edu/doxygen/structDominatorSet.html"><tt>DominatorSet</tt></a> | |
| needs to be calculated at a time. This also makes it possible some <a | |
| href="#SMP">interesting enhancements</a> in the future.<p> | |
| </ol><p> | |
| The effectiveness of the <tt>PassManager</tt> is influenced directly by how much | |
| information it has about the behaviors of the passes it is scheduling. For | |
| example, the "preserved" set is intentionally conservative in the face of an | |
| unimplemented <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method. | |
| Not implementing when it should be implemented will have the effect of not | |
| allowing any analysis results to live across the execution of your pass.<p> | |
| The <tt>PassManager</tt> class exposes a <tt>--debug-pass</tt> command line | |
| options that is useful for debugging pass execution, seeing how things work, and | |
| diagnosing when you should be preserving more analyses than you currently are | |
| (To get information about all of the variants of the <tt>--debug-pass</tt> | |
| option, just type '<tt>opt --help-hidden</tt>').<p> | |
| By using the <tt>--debug-pass=Structure</tt> option, for example, we can see how | |
| our <a href="#basiccode">Hello World</a> pass interacts with other passes. Lets | |
| try it out with the <tt>gcse</tt> and <tt>licm</tt> passes:<p> | |
| <pre> | |
| $ opt -load ../../../lib/Debug/libhello.so -gcse -licm --debug-pass=Structure < hello.bc > /dev/null | |
| Module Pass Manager | |
| Function Pass Manager | |
| Dominator Set Construction | |
| Immediate Dominators Construction | |
| Global Common Subexpression Elimination | |
| -- Immediate Dominators Construction | |
| -- Global Common Subexpression Elimination | |
| Natural Loop Construction | |
| Loop Invariant Code Motion | |
| -- Natural Loop Construction | |
| -- Loop Invariant Code Motion | |
| Module Verifier | |
| -- Dominator Set Construction | |
| -- Module Verifier | |
| Bytecode Writer | |
| --Bytecode Writer | |
| </pre><p> | |
| This output shows us when passes are constructed and when the analysis results | |
| are known to be dead (prefixed with '<tt>--</tt>'). Here we see that GCSE uses | |
| dominator and immediate dominator information to do its job. The LICM pass uses | |
| natural loop information, which uses dominator sets, but not immediate | |
| dominators. Because immediate dominators are no longer useful after the GCSE | |
| pass, it is immediately destroyed. The dominator sets are then reused to | |
| compute natural loop information, which is then used by the LICM pass.<p> | |
| After the LICM pass, the module verifier runs (which is automatically added by | |
| the '<tt>opt</tt>' tool), which uses the dominator set to check that the | |
| resultant LLVM code is well formed. After it finishes, the dominator set | |
| information is destroyed, after being computed once, and shared by three | |
| passes.<p> | |
| Lets see how this changes when we run the <a href="#basiccode">Hello World</a> | |
| pass in between the two passes:<p> | |
| <pre> | |
| $ opt -load ../../../lib/Debug/libhello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null | |
| Module Pass Manager | |
| Function Pass Manager | |
| Dominator Set Construction | |
| Immediate Dominators Construction | |
| Global Common Subexpression Elimination | |
| <b>-- Dominator Set Construction</b> | |
| -- Immediate Dominators Construction | |
| -- Global Common Subexpression Elimination | |
| <b> Hello World Pass | |
| -- Hello World Pass | |
| Dominator Set Construction</b> | |
| Natural Loop Construction | |
| Loop Invariant Code Motion | |
| -- Natural Loop Construction | |
| -- Loop Invariant Code Motion | |
| Module Verifier | |
| -- Dominator Set Construction | |
| -- Module Verifier | |
| Bytecode Writer | |
| --Bytecode Writer | |
| Hello: __main | |
| Hello: puts | |
| Hello: main | |
| </pre><p> | |
| Here we see that the <a href="#basiccode">Hello World</a> pass has killed the | |
| Dominator Set pass, even though it doesn't modify the code at all! To fix this, | |
| we need to add the following <a | |
| href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method to our pass:<p> | |
| <pre> | |
| <i>// We don't modify the program, so we preserve all analyses</i> | |
| <b>virtual void</b> getAnalysisUsage(AnalysisUsage &AU) <b>const</b> { | |
| AU.setPreservesAll(); | |
| } | |
| </pre><p> | |
| Now when we run our pass, we get this output:<p> | |
| <pre> | |
| $ opt -load ../../../lib/Debug/libhello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null | |
| Pass Arguments: -gcse -hello -licm | |
| Module Pass Manager | |
| Function Pass Manager | |
| Dominator Set Construction | |
| Immediate Dominators Construction | |
| Global Common Subexpression Elimination | |
| -- Immediate Dominators Construction | |
| -- Global Common Subexpression Elimination | |
| Hello World Pass | |
| -- Hello World Pass | |
| Natural Loop Construction | |
| Loop Invariant Code Motion | |
| -- Loop Invariant Code Motion | |
| -- Natural Loop Construction | |
| Module Verifier | |
| -- Dominator Set Construction | |
| -- Module Verifier | |
| Bytecode Writer | |
| --Bytecode Writer | |
| Hello: __main | |
| Hello: puts | |
| Hello: main | |
| </pre><p> | |
| Which shows that we don't accidentally invalidate dominator information | |
| anymore, and therefore do not have to compute it twice.<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="releaseMemory"><hr size=0>The <tt>releaseMemory</tt> method</h4><ul> | |
| <pre> | |
| <b>virtual void</b> releaseMemory(); | |
| </pre><p> | |
| The <tt>PassManager</tt> automatically determines when to compute analysis | |
| results, and how long to keep them around for. Because the lifetime of the pass | |
| object itself is effectively the entire duration of the compilation process, we | |
| need some way to free analysis results when they are no longer useful. The | |
| <tt>releaseMemory</tt> virtual method is the way to do this.<p> | |
| If you are writing an analysis or any other pass that retains a significant | |
| amount of state (for use by another pass which "requires" your pass and uses the | |
| <a href="#getAnalysis">getAnalysis</a> method) you should implement | |
| <tt>releaseMEmory</tt> to, well, release the memory allocated to maintain this | |
| internal state. This method is called after the <tt>run*</tt> method for the | |
| class, before the next call of <tt>run*</tt> in your pass.<p> | |
| <!-- *********************************************************************** --> | |
| </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b> | |
| <a name="debughints">Using GDB with dynamically loaded passes | |
| </b></font></td></tr></table><ul> | |
| <!-- *********************************************************************** --> | |
| Unfortunately, using GDB with dynamically loaded passes is not as easy as it | |
| should be. First of all, you can't set a breakpoint in a shared object that has | |
| not been loaded yet, and second of all there are problems with inlined functions | |
| in shared objects. Here are some suggestions to debugging your pass with | |
| GDB.<p> | |
| For sake of discussion, I'm going to assume that you are debugging a | |
| transformation invoked by <tt>opt</tt>, although nothing described here depends | |
| on that.<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="breakpoint"><hr size=0>Setting a breakpoint in your pass</h4><ul> | |
| First thing you do is start <tt>gdb</tt> on the <tt>opt</tt> process:<p> | |
| <pre> | |
| $ <b>gdb opt</b> | |
| GNU gdb 5.0 | |
| Copyright 2000 Free Software Foundation, Inc. | |
| GDB is free software, covered by the GNU General Public License, and you are | |
| welcome to change it and/or distribute copies of it under certain conditions. | |
| Type "show copying" to see the conditions. | |
| There is absolutely no warranty for GDB. Type "show warranty" for details. | |
| This GDB was configured as "sparc-sun-solaris2.6"... | |
| (gdb) | |
| </pre><p> | |
| Note that <tt>opt</tt> has a lot of debugging information in it, so it takes | |
| time to load. Be patient. Since we cannot set a breakpoint in our pass yet | |
| (the shared object isn't loaded until runtime), we must execute the process, and | |
| have it stop before it invokes our pass, but after it has loaded the shared | |
| object. The most foolproof way of doing this is to set a breakpoint in | |
| <tt>PassManager::run</tt> and then run the process with the arguments you | |
| want:<p> | |
| <pre> | |
| (gdb) <b>break PassManager::run</b> | |
| Breakpoint 1 at 0x2413bc: file Pass.cpp, line 70. | |
| (gdb) <b>run test.bc -load /shared/lattner/cvs/llvm/lib/Debug/[libname].so -[passoption]</b> | |
| Starting program: /shared/lattner/cvs/llvm/tools/Debug/opt test.bc | |
| -load /shared/lattner/cvs/llvm/lib/Debug/[libname].so -[passoption] | |
| Breakpoint 1, PassManager::run (this=0xffbef174, M=@0x70b298) at Pass.cpp:70 | |
| 70 bool PassManager::run(Module &M) { return PM->run(M); } | |
| (gdb) | |
| </pre></p> | |
| Once the <tt>opt</tt> stops in the <tt>PassManager::run</tt> method you are now | |
| free to set breakpoints in your pass so that you can trace through execution or | |
| do other standard debugging stuff.<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="debugmisc"><hr size=0>Miscellaneous Problems</h4><ul> | |
| Once you have the basics down, there are a couple of problems that GDB has, some | |
| with solutions, some without.<p> | |
| <ul> | |
| <li>Inline functions have bogus stack information. In general, GDB does a | |
| pretty good job getting stack traces and stepping through inline functions. | |
| When a pass is dynamically loaded however, it somehow completely loses this | |
| capability. The only solution I know of is to de-inline a function (move it | |
| from the body of a class to a .cpp file).<p> | |
| <li>Restarting the program breaks breakpoints. After following the information | |
| above, you have succeeded in getting some breakpoints planted in your pass. Nex | |
| thing you know, you restart the program (i.e., you type '<tt>run</tt>' again), | |
| and you start getting errors about breakpoints being unsettable. The only way I | |
| have found to "fix" this problem is to <tt>delete</tt> the breakpoints that are | |
| already set in your pass, run the program, and re-set the breakpoints once | |
| execution stops in <tt>PassManager::run</tt>.<p> | |
| </ul> | |
| Hopefully these tips will help with common case debugging situations. If you'd | |
| like to contribute some tips of your own, just contact <a | |
| href="mailto:sabre@nondot.org">Chris</a>.<p> | |
| <!-- *********************************************************************** --> | |
| </ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0> | |
| <tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b> | |
| <a name="future">Future extensions planned | |
| </b></font></td></tr></table><ul> | |
| <!-- *********************************************************************** --> | |
| Although the LLVM Pass Infrastructure is very capable as it stands, and does | |
| some nifty stuff, there are things we'd like to add in the future. Here is | |
| where we are going:<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="SMP"><hr size=0>Multithreaded LLVM</h4><ul> | |
| Multiple CPU machines are becoming more common and compilation can never be | |
| fast enough: obviously we should allow for a multithreaded compiler. Because of | |
| the semantics defined for passes above (specifically they cannot maintain state | |
| across invocations of their <tt>run*</tt> methods), a nice clean way to | |
| implement a multithreaded compiler would be for the <tt>PassManager</tt> class | |
| to create multiple instances of each pass object, and allow the separate | |
| instances to be hacking on different parts of the program at the same time.<p> | |
| This implementation would prevent each of the passes from having to implement | |
| multithreaded constructs, requiring only the LLVM core to have locking in a few | |
| places (for global resources). Although this is a simple extension, we simply | |
| haven't had time (or multiprocessor machines, thus a reason) to implement this. | |
| Despite that, we have kept the LLVM passes SMP ready, and you should too.<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="ModuleSource"><hr size=0>A new <tt>ModuleSource</tt> interface</h4><ul> | |
| Currently, the <tt>PassManager</tt>'s <tt>run</tt> method takes a <tt><a | |
| href="http://llvm.cs.uiuc.edu/doxygen/classModule.html">Module</a></tt> as | |
| input, and runs all of the passes on this module. The problem with this | |
| approach is that none of the <tt>PassManager</tt> features can be used for | |
| timing and debugging the actual <b>loading</b> of the module from disk or | |
| standard input.<p> | |
| To solve this problem, eventually the <tt>PassManger</tt> class will accept a | |
| <tt>ModuleSource</tt> object instead of a Module itself. When complete, this | |
| will also allow for streaming of functions out of the bytecode representation, | |
| allowing us to avoid holding the entire program in memory at once if we only are | |
| dealing with <a href="#FunctionPass">FunctionPass</a>'s.<p> | |
| As part of a different issue, eventually the bytecode loader will be extended to | |
| allow on-demand loading of functions from the bytecode representation, in order | |
| to better support the runtime reoptimizer. The bytecode format is already | |
| capable of this, the loader just needs to be reworked a bit.<p> | |
| <!-- _______________________________________________________________________ --> | |
| </ul><h4><a name="PassFunctionPass"><hr size=0><tt>Pass</tt>'s requiring <tt>FunctionPass</tt>'s</h4><ul> | |
| Currently it is illegal for a <a href="#Pass"><tt>Pass</tt></a> to require a <a | |
| href="#FunctionPass"><tt>FunctionPass</tt></a>. This is because there is only | |
| one instance of the <a href="#FunctionPass"><tt>FunctionPass</tt></a> object | |
| ever created, thus nowhere to store information for all of the functions in the | |
| program at the same time. Although this has come up a couple of times before, | |
| this has always been worked around by factoring one big complicated pass into a | |
| global and an interprocedural part, both of which are distinct. In the future, | |
| it would be nice to have this though.<p> | |
| Note that it is no problem for a <a | |
| href="#FunctionPass"><tt>FunctionPass</tt></a> to require the results of a <a | |
| href="#Pass"><tt>Pass</tt></a>, only the other way around.<p> | |
| <!-- *********************************************************************** --> | |
| </ul> | |
| <!-- *********************************************************************** --> | |
| <hr><font size-1> | |
| <address><a href="mailto:sabre@nondot.org">Chris Lattner</a></address> | |
| <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a> | |
| <br> | |
| <!-- Created: Tue Aug 6 15:00:33 CDT 2002 --> | |
| <!-- hhmts start --> | |
| Last modified: Tue Jul 22 15:52:30 CDT 2003 | |
| <!-- hhmts end --> | |
| </font></body></html> |