"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="#makefile">Setting up the build environment</a></li>
<li><a href="#basiccode">Basic code required</a></li>
<li><a href="#running">Running a pass with <tt>opt</tt>
- or <tt>analyze</tt></a></li>
+ or <tt>analyze</tt></a></li>
</ul></li>
<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="#doInitialization_scc">The <tt>doInitialization(Module
+ &)</tt> method</a></li>
+ <li><a href="#runOnSCC">The <tt>runOnSCC</tt> method</a></li>
+ <li><a href="#doFinalization_scc">The <tt>doFinalization(Module
+ &)</tt> method</a></li>
</ul></li>
<li><a href="#FunctionPass">The <tt>FunctionPass</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="#ModuleSource">A new <tt>ModuleSource</tt> interface</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>
-<div class="doc_text">
- <p><b>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></b><p>
+<div class="doc_author">
+ <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
</div>
<!-- *********************************************************************** -->
<div class="doc_text">
<p>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>
+passes are where most of 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>
<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="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1FunctionPass.html">FunctionPass</a></tt>
-or <tt><a
-href="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1BasicBlockPass.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>
+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
+schedules passes to run in an efficient way based on the constraints that your
+pass meets (which are indicated by which class they derive from).</p>
<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,
<p>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
+the program being compiled. It does not modify the program at all, it 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>
<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 of 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>
we are operating on <tt><a
href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1Function.html">Function</a></tt>'s.</p>
+<p>Next we have:</p>
+<pre>
+<b>using namespace llvm;</b>
+</pre>
+<p>... which is required because the functions from the include files
+live in the llvm namespace.
+</p>
+
<p>Next we have:</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>using namespace llvm;</b>
+
<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) {
<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_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="runOnModule">The <tt>runOnModule</tt> method</a>
+</div>
+
+<div class="doc_text">
+
+<pre>
+ <b>virtual bool</b> runOnModule(Module &M) = 0;
+</pre>
+
+<p>The <tt>runOnModule</tt> method performs the interesting work of the pass,
+and should return true if the module was modified by the transformation, false
+otherwise.</p>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="CallGraphSCCPass">The <tt>CallGraphSCCPass</tt> class</a>
+</div>
+
+<div class="doc_text">
+
+<p>The "<tt><a
+href="http://llvm.cs.uiuc.edu/doxygen/structllvm_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
+to optimize execution of CallGraphSCCPass's. If your pass meets the
+requirements outlined below, and doesn't meet the requirements of a <tt><a
+href="#FunctionPass">FunctionPass</a></tt> or <tt><a
+href="#BasicBlockPass">BasicBlockPass</a></tt>, you should derive from
+<tt>CallGraphSCCPass</tt>.</p>
+
+<p><b>TODO</b>: explain briefly what SCC, Tarjan's algo, and B-U mean.</p>
+
+<p>To be explicit, <tt>CallGraphSCCPass</tt> subclasses are:</p>
+
+<ol>
+
+<li>... <em>not allowed</em> to modify any <tt>Function</tt>s that are not in
+the current SCC.</li>
+
+<li>... <em>allowed</em> to inspect any Function's other than those in the
+current SCC and the direct callees of the SCC.</li>
+
+<li>... <em>required</em> to preserve the current CallGraph object, updating it
+to reflect any changes made to the program.</li>
+
+<li>... <em>not allowed</em> to add or remove SCC's from the current Module,
+though they may change the contents of an SCC.</li>
+
+<li>... <em>allowed</em> to add or remove global variables from the current
+Module.</li>
+
+<li>... <em>allowed</em> to maintain state across invocations of
+ <a href="#runOnSCC"><tt>runOnSCC</tt></a> (including global data).</li>
+</ol>
+
+<p>Implementing a <tt>CallGraphSCCPass</tt> is slightly tricky in some cases
+because it has to handle SCCs with more than one node in it. All of the virtual
+methods described below should return true if they modified the program, or
+false if they didn't.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="doInitialization_scc">The <tt>doInitialization(Module &)</tt>
+ method</a>
+</div>
+
+<div class="doc_text">
+
+<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>CallGraphSCCPass</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 SCCs 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>
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
- <a name="run">The <tt>run</tt> method</a>
+ <a name="runOnSCC">The <tt>runOnSCC</tt> method</a>
</div>
<div class="doc_text">
<pre>
- <b>virtual bool</b> run(Module &M) = 0;
+ <b>virtual bool</b> runOnSCC(const std::vector<CallGraphNode *> &SCCM) = 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
+<p>The <tt>runOnSCC</tt> method performs the interesting work of the pass, and
+should return true if the module was modified by the transformation, false
otherwise.</p>
</div>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="doFinalization_scc">The <tt>doFinalization(Module
+ &)</tt> method</a>
+</div>
+
+<div class="doc_text">
+
+<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>
+
+</div>
+
<!-- ======================================================================= -->
<div class="doc_subsection">
<a name="FunctionPass">The <tt>FunctionPass</tt> class</a>
<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>
want, and returns a reference to that pass. For example:</p>
<pre>
- bool LICM::runOnFunction(Function &F) {
+ bool LICM::runOnFunction(Function &F) {
LoopInfo &LI = getAnalysis<LoopInfo>();
...
}
Passes that use the <tt><a
href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a></tt>
interface (for example the <tt><a
-href="http://llvm.cs.uiuc.edu/doxygen/classGCSE.html">gcse</a></tt> pass), do
+href="http://llvm.cs.uiuc.edu/doxygen/structGCSE.html">gcse</a></tt> pass), do
not care which implementation of alias analysis is actually provided, they just
use the designated interface.</p>
</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>
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
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
- <a name="ModuleSource">A new <tt>ModuleSource</tt> interface</a>
-</div>
-
-<div class="doc_text">
-
-<p>Currently, the <tt>PassManager</tt>'s <tt>run</tt> method takes a <tt><a
-href="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1Module.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>
-
-<p>To solve this problem, eventually the <tt>PassManager</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>es.</p>
-
-<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>
-
-</div>
-
-<!-- _______________________________________________________________________ -->
-<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>