diff options
author | Chris Lattner <sabre@nondot.org> | 2002-08-08 20:11:18 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2002-08-08 20:11:18 +0000 |
commit | c6bb82495c90574195049cc5aae8a4ff6ae57e6b (patch) | |
tree | 8bce7bb7737c5a90f2db2c3e135aa993b9e241d7 /docs/WritingAnLLVMPass.html | |
parent | 180e568a70580e177cda71e354f6620aeaaa1b63 (diff) | |
download | llvm-c6bb82495c90574195049cc5aae8a4ff6ae57e6b.tar.gz llvm-c6bb82495c90574195049cc5aae8a4ff6ae57e6b.tar.bz2 llvm-c6bb82495c90574195049cc5aae8a4ff6ae57e6b.tar.xz |
Initial checkin of the "Writting an LLVM Pass" document
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3267 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'docs/WritingAnLLVMPass.html')
-rw-r--r-- | docs/WritingAnLLVMPass.html | 969 |
1 files changed, 969 insertions, 0 deletions
diff --git a/docs/WritingAnLLVMPass.html b/docs/WritingAnLLVMPass.html new file mode 100644 index 0000000000..9f5dff4d31 --- /dev/null +++ b/docs/WritingAnLLVMPass.html @@ -0,0 +1,969 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> +<html><head><title>Writing an LLVM Pass</title></head> + +<!-- +I. General Structure of an LLVM Program + +I.1 "What is a 'Value'?": Value & User class +I.2 Type & Derived Types +I.3 GlobalVariable, Function +I.4 BasicBlock +I.5 Instruction & Subclasses +1.6 Argument +1.7 Constants + +III. Useful things to know about the LLVM source base: + +III.1 Useful links that introduce the STL +III.2 isa<>, cast<>, dyn_cast<> +III.3 Makefiles, useful options +III.4 How to use opt & analyze to debug stuff +III.5 How to write a regression test +III.6 DEBUG() and Statistics (-debug & -stats) +III.7 The -time-passes option +III.8 ... more as needed ... + +I think that writing Section #1 would be very helpful and that's the most +stable portion of the sourcebase. #3 can be started on, but will probably +just grow as time goes on. I'd like to do Section #2 once I finish some +changes up that effect it. + +--> + +<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="#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">The <tt>doInitialization</tt> method</a> + <li><a href="#runOnFunction">The <tt>runOnFunction</tt> method</a> + <li><a href="#doFinalization">The <tt>doFinalization</tt> method</a> + </ul> + <li><a href="#BasicBlockPass">The <tt>BasicBlockPass</tt> class</a> + <ul> + <li><a href="#runOnBasicBlock">The <tt>runOnBasicBlock</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="#passmanager">What PassManager does</a> + <ul> + <li><a href="#releaseMemory">The <tt>releaseMemory</tt> method</a> + </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> +</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 +LEVEL = ../../.. # Path to top level of LLVM heirarchy +LIBRARYNAME = hello # Name of the library to build +SHARED_LIBRARY = 1 # Build a dynamically loadable shared object + +include $(LEVEL)/Makefile.common # Include the makefile implementation stuff +</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 builting 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 - Cannonicalize 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 most specific +class possible, while still being able to meet the requirements listed. This +gives the LLVM Pass Infrastructure information neccesary 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="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 +independant 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"><hr size=0>The <tt>doInitialization</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>doInitialize</tt> method is +designed to do simple initialization type of stuff that does not depend on the +functions being processed. The <tt>doInitialization</tt> function call is not +scheduled to overlap with any other pass executions.<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 dependant <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 neccesary.<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"><hr size=0>The <tt>doFinalization</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"><tt>doInitialization</tt></a> and <a +href="#doFinalization"><tt>doFinalization</tt></a> methods that <a +href="#FunctionPass"><tt>FunctionPass</tt></a>'s have, but also have a +<tt>runOnBasicBlock</tt> method:<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><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>// preservesCFG - 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::preservesCFG(); +</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.preservesCFG(); + 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="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="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 command 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 seperate +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">Christopher Lattner</a></address> +<!-- Created: Tue Aug 6 15:00:33 CDT 2002 --> +<!-- hhmts start --> +Last modified: Thu Aug 8 15:07:23 CDT 2002 +<!-- hhmts end --> +</font></body></html> |