<!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>
<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>
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>
+this, copy this into "<tt>Makefile</tt>" (be very careful that there are no
+extra space characters at the end of the lines though... that seems to confuse
+<tt>gmake</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
+# 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
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
g pass subclasses are described in detail <a
+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>
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>
+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 neccesary to
+optimize how passes are run, so that the resultant compiler isn't unneccesarily
+slow.<p>
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>
<!-- *********************************************************************** -->
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>
<!-- *********************************************************************** -->
<hr><font size-1>
-<address><a href="mailto:sabre@nondot.org">Christopher Lattner</a></address>
+<address><a href="mailto:sabre@nondot.org">Chris Lattner</a></address>
<!-- Created: Tue Aug 6 15:00:33 CDT 2002 -->
<!-- hhmts start -->
-Last modified: Thu Aug 8 15:16:18 CDT 2002
+Last modified: Thu Sep 5 15:06:01 CDT 2002
<!-- hhmts end -->
</font></body></html>
projects / oota-llvm.git / blobdiff