"http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
+ <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Writing an LLVM Pass</title>
<link rel="stylesheet" href="llvm.css" type="text/css">
</head>
<li><a href="#passtype">Pass classes and requirements</a>
<ul>
<li><a href="#ImmutablePass">The <tt>ImmutablePass</tt> class</a></li>
- <li><a href="#Pass">The <tt>Pass</tt> class</a>
+ <li><a href="#ModulePass">The <tt>ModulePass</tt> class</a>
<ul>
- <li><a href="#run">The <tt>run</tt> method</a></li>
+ <li><a href="#runOnModule">The <tt>runOnModule</tt> method</a></li>
</ul></li>
<li><a href="#CallGraphSCCPass">The <tt>CallGraphSCCPass</tt> class</a>
<ul>
<li><a href="#agconcepts">Analysis Group Concepts</a></li>
<li><a href="#registerag">Using <tt>RegisterAnalysisGroup</tt></a></li>
</ul></li>
+ <li><a href="#passStatistics">Pass Statistics</a>
<li><a href="#passmanager">What PassManager does</a>
<ul>
<li><a href="#releaseMemory">The <tt>releaseMemory</tt> method</a></li>
<li><a href="#future">Future extensions planned</a>
<ul>
<li><a href="#SMP">Multithreaded LLVM</a></li>
- <li><a href="#PassFunctionPass"><tt>Pass</tt>es requiring
+ <li><a href="#PassFunctionPass"><tt>ModulePass</tt>es requiring
<tt>FunctionPass</tt>es</a></li>
</ul></li>
</ol>
<p>All LLVM passes are subclasses of the <tt><a
href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1Pass.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="#CallGraphSCCPass">CallGraphSCCPass</a></tt>,
-<tt><a href="#FunctionPass">FunctionPass</a></tt>, or <tt><a
+from <tt>Pass</tt>. Depending on how your pass works, you should inherit from
+the <tt><a href="#ModulePass">ModulePass</a></tt>, <tt><a
+href="#CallGraphSCCPass">CallGraphSCCPass</a></tt>, <tt><a
+href="#FunctionPass">FunctionPass</a></tt>, or <tt><a
href="#BasicBlockPass">BasicBlockPass</a></tt> classes, 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
<div class="doc_text">
-<p>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>
-
-<hr>
+ <p>First, you need to create a new directory somewhere in the LLVM source
+ base. For this example, we'll assume that you made
+ <tt>lib/Transforms/Hello</tt>. Next, you must set up a build script
+ (Makefile) that will compile the source code for the new pass. To do this,
+ copy the following into <tt>Makefile</tt>:</p>
+ <hr/>
<pre>
# Makefile for hello pass
LEVEL = ../../..
# Name of the library to build
-LIBRARYNAME = hello
+LIBRARYNAME = Hello
-# Build a dynamically loadable shared object
+# Build a dynamically linkable shared object
SHARED_LIBRARY = 1
+# Make the shared library become a loadable module so the tools can
+# dlopen/dlsym on the resulting library.
+LOADABLE_MODULE
+
# Include the makefile implementation stuff
include $(LEVEL)/Makefile.common
</pre>
<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. If your operating system uses a
-suffix other than .so (such as windows or Mac OS/X), the appropriate extension
-will be used.</p>
+<tt>Debug/lib/Hello.so</tt> shared object that can be dynamically loaded by
+the <tt>opt</tt> or <tt>analyze</tt> tools via their <tt>-load</tt> options.
+If your operating system uses a suffix other than .so (such as windows or
+Mac OS/X), the appropriate extension will be used.</p>
<p>Now that we have the build scripts set up, we just need to write the code for
the pass itself.</p>
</pre><p>
<p>This declares a "<tt>Hello</tt>" class that is a subclass of <tt><a
-href="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1FunctionPass.html">FunctionPass</a></tt>.
+href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1FunctionPass.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
<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
+"<tt>Debug/lib/Hello.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>
work):</p>
<pre>
-$ opt -load ../../../lib/Debug/libhello.so -hello < hello.bc > /dev/null
+$ opt -load ../../../Debug/lib/Hello.so -hello < hello.bc > /dev/null
Hello: __main
Hello: puts
Hello: main
<tt>opt</tt> with the <tt>--help</tt> option:</p>
<pre>
-$ opt -load ../../../lib/Debug/libhello.so --help
+$ opt -load ../../../Debug/lib/Hello.so --help
OVERVIEW: llvm .bc -> .bc modular optimizer
USAGE: opt [options] <input bytecode>
example:</p>
<pre>
-$ opt -load ../../../lib/Debug/libhello.so -hello -time-passes < hello.bc > /dev/null
+$ opt -load ../../../Debug/lib/Hello.so -hello -time-passes < hello.bc > /dev/null
Hello: __main
Hello: puts
Hello: main
<div class="doc_text">
<p>The most plain and boring type of pass is the "<tt><a
-href="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1ImmutablePass.html">ImmutablePass</a></tt>"
+href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1ImmutablePass.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
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="Pass">The <tt>Pass</tt> class</a>
+ <a name="ModulePass">The <tt>ModulePass</tt> class</a>
</div>
<div class="doc_text">
<p>The "<tt><a
-href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1Pass.html">Pass</a></tt>"
+href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1ModulePass.html">ModulePass</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,
+<tt>ModulePass</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>
+functions. Because nothing is known about the behavior of <tt>ModulePass</tt>
subclasses, no optimization can be done for their execution.</p>
-<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>
+<p>To write a correct <tt>ModulePass</tt> subclass, derive from
+<tt>ModulePass</tt> and overload the <tt>runOnModule</tt> method with the
+following signature:</p>
</div>
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
- <a name="run">The <tt>run</tt> method</a>
+ <a name="runOnModule">The <tt>runOnModule</tt> method</a>
</div>
<div class="doc_text">
<pre>
- <b>virtual bool</b> run(Module &M) = 0;
+ <b>virtual bool</b> runOnModule(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>
+<p>The <tt>runOnModule</tt> method performs the interesting work of the pass.
+It should return true if the module was modified by the transformation and
+false otherwise.</p>
</div>
<div class="doc_text">
<p>The "<tt><a
-href="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1CallGraphSCCPass.html">CallGraphSCCPass</a></tt>"
+href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1CallGraphSCCPass.html">CallGraphSCCPass</a></tt>"
is used by passes that need to traverse the program bottom-up on the call graph
(callees before callers). Deriving from CallGraphSCCPass provides some
mechanics for building and traversing the CallGraph, but also allows the system
<div class="doc_text">
-<p>In contrast to direct <tt>Pass</tt> subclasses, direct <tt><a
+<p>In contrast to <tt>ModulePass</tt> subclasses, <tt><a
href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1Pass.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
<li>Modify or inspect any basic blocks outside of the current one</li>
<li>Maintain state across invocations of
<a href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a></li>
-<li>Modify the constrol flow graph (by altering terminator instructions)</li>
-<li>Any of the things verboten for
+<li>Modify the control flow graph (by altering terminator instructions)</li>
+<li>Any of the things forbidden for
<a href="#FunctionPass"><tt>FunctionPass</tt></a>es.</li>
</ol>
<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
+to do simple initialization 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>
<div class="doc_text">
<p>
-If you pass requires a previous pass to be executed (an analysis for example),
+If your pass requires a previous pass to be executed (an analysis for example),
it can use one of these methods to arrange for it to be run before your pass.
LLVM has many different types of analyses and passes that can be required,
-spaning the range from <tt>DominatorSet</tt> to <tt>BreakCriticalEdges</tt>.
-requiring <tt>BreakCriticalEdges</tt>, for example, guarantees that there will
+spanning the range from <tt>DominatorSet</tt> to <tt>BreakCriticalEdges</tt>.
+Requiring <tt>BreakCriticalEdges</tt>, for example, guarantees that there will
be no critical edges in the CFG when your pass has been run.
</p>
In particular, it attempts to avoid recomputing data unless it needs to. For
this reason, passes are allowed to declare that they preserve (i.e., they don't
invalidate) an existing analysis if it's available. For example, a simple
-constant folding pass would not modify the CFG, so it can't possible effect the
+constant folding pass would not modify the CFG, so it can't possibly affect the
results of dominator analysis. By default, all passes are assumed to invalidate
all others.
</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/structllvm_1_1PostDominanceFrontier.html">PostDominanceFrontier</a>::getAnalysisUsage(AnalysisUsage &AU) <b>const</b> {
+ <b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1PostDominanceFrontier.html">PostDominanceFrontier</a>::getAnalysisUsage(AnalysisUsage &AU) <b>const</b> {
AU.setPreservesAll();
- AU.addRequired<<a href="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1PostDominatorTree.html">PostDominatorTree</a>>();
+ AU.addRequired<<a href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1PostDominatorTree.html">PostDominatorTree</a>>();
}
</pre>
</div>
+<!-- *********************************************************************** -->
+<div class="doc_section">
+ <a name="passStatistics">Pass Statistics</a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+<p>The <a
+href="http://llvm.cs.uiuc.edu/doxygen/Statistic_8h-source.html"><tt>Statistic</tt></a>
+class, is designed to be an easy way to expose various success
+metrics from passes. These statistics are printed at the end of a
+run, when the -stats command line option is enabled on the command
+line. See the <a href="http://llvm.org/docs/ProgrammersManual.html#Statistic">Statistics section</a> in the Programmer's Manual for details.
+
+</div>
+
+
<!-- *********************************************************************** -->
<div class="doc_section">
<a name="passmanager">What PassManager does</a>
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/structllvm_1_1DominatorSet.html"><tt>DominatorSet</tt></a>
+href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1DominatorSet.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></li>
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
+$ opt -load ../../../Debug/lib/Hello.so -gcse -licm --debug-pass=Structure < hello.bc > /dev/null
Module Pass Manager
Function Pass Manager
Dominator Set Construction
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
+$ opt -load ../../../Debug/lib/Hello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null
Module Pass Manager
Function Pass Manager
Dominator Set Construction
<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
+$ opt -load ../../../Debug/lib/Hello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null
Pass Arguments: -gcse -hello -licm
Module Pass Manager
Function Pass Manager
<pre>
(gdb) <b>break PassManager::run</b>
Breakpoint 1 at 0x2413bc: file Pass.cpp, line 70.
-(gdb) <b>run test.bc -load $(LLVMTOP)/llvm/lib/Debug/[libname].so -[passoption]</b>
-Starting program: opt test.bc -load $(LLVMTOP)/llvm/lib/Debug/[libname].so -[passoption]
+(gdb) <b>run test.bc -load $(LLVMTOP)/llvm/Debug/lib/[libname].so -[passoption]</b>
+Starting program: opt test.bc -load $(LLVMTOP)/llvm/Debug/lib/[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)
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
-<a name="PassFunctionPass"><tt>Pass</tt>es requiring <tt>FunctionPass</tt>es</a>
+<a name="PassFunctionPass"><tt>ModulePass</tt>es requiring <tt>FunctionPass</tt>es</a>
</div>
<div class="doc_text">
-<p>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>
+<p>Currently it is illegal for a <a href="#ModulePass"><tt>ModulePass</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>
<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>
+href="#ModulePass"><tt>ModulePass</tt></a>, only the other way around.</p>
</div>