<!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.
-
--->
-
<body bgcolor=white>
<table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
</ul>
<li><a href="#passtype">Pass classes and requirements</a>
<ul>
+ <li><a href="#ImmutablePass">The <tt>ImmutablePass</tt> class</a>
<li><a href="#Pass">The <tt>Pass</tt> class</a>
<ul>
<li><a href="#run">The <tt>run</tt> method</a>
</ul>
<li><a href="#FunctionPass">The <tt>FunctionPass</tt> class</a>
<ul>
- <li><a href="#doInitialization">The <tt>doInitialization</tt> method</a>
+ <li><a href="#doInitialization_mod">The <tt>doInitialization(Module
+ &)</tt> method</a>
<li><a href="#runOnFunction">The <tt>runOnFunction</tt> method</a>
- <li><a href="#doFinalization">The <tt>doFinalization</tt> method</a>
+ <li><a href="#doFinalization_mod">The <tt>doFinalization(Module
+ &)</tt> method</a>
</ul>
<li><a href="#BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
<ul>
+ <li><a href="#doInitialization_fn">The <tt>doInitialization(Function
+ &)</tt> method</a>
<li><a href="#runOnBasicBlock">The <tt>runOnBasicBlock</tt> method</a>
+ <li><a href="#doFinalization_fn">The <tt>doFinalization(Function
+ &)</tt> method</a>
+ </ul>
+ <li><a href="#MachineFunctionPass">The <tt>MachineFunctionPass</tt>
+ class</a>
+ <ul>
+ <li><a href="#runOnMachineFunction">The
+ <tt>runOnMachineFunction(MachineFunction &)</tt> method</a>
</ul>
</ul>
<li><a href="#registration">Pass Registration</a>
<ul>
<li><a href="#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>" (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>
+this, copy this into "<tt>Makefile</tt>":<p>
</ul><hr><ul><pre>
# Makefile for hello pass
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
+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>
-gcse - Global Common Subexpression Elimination
-globaldce - Dead Global Elimination
<b>-hello - Hello World Pass</b>
- -indvars - Cannonicalize Induction Variables
+ -indvars - Canonicalize Induction Variables
-inline - Function Integration/Inlining
-instcombine - Combine redundant instructions
...
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
+listed. This gives the LLVM Pass Infrastructure information necessary to
optimize how passes are run, so that the resultant compiler isn't unneccesarily
slow.<p>
+<!-- ======================================================================= -->
+</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
+<tr><td> </td><td width="100%">
+<font color="#EEEEFF" face="Georgia,Palatino"><b>
+<a name="ImmutablePass">The <tt>ImmutablePass</tt> class
+</b></font></td></tr></table><ul>
+
+The most plain and boring type of pass is the "<tt><a
+href="http://llvm.cs.uiuc.edu/doxygen/structImmutablePass.html">ImmutablePass</a></tt>"
+class. This pass type is used for passes that do not have to be run, do not
+change state, and never need to be updated. This is not a normal type of
+transformation or analysis, but can provide information about the current
+compiler configuration.<p>
+
+Although this pass class is very infrequently used, it is important for
+providing information about the current target machine being compiled for, and
+other static information that can affect the various transformations.<p>
+
+<tt>ImmutablePass</tt>'s never invalidate other transformations, are never
+invalidated, and are never "run".<p>
+
<!-- ======================================================================= -->
</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
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.
+independent of all of the other functions in the program.
<tt>FunctionPass</tt>'s do not require that they are executed in a particular
order, and <tt>FunctionPass</tt>'s do not modify external functions.<p>
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>
+</ul><h4><a name="doInitialization_mod"><hr size=0>The
+<tt>doInitialization(Module &)</tt> method</h4><ul>
<pre>
<b>virtual bool</b> doInitialization(Module &M);
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>
+functions, get pointers to functions, etc. The <tt>doInitialization</tt> method
+is designed to do simple initialization type of stuff that does not depend on
+the functions being processed. The <tt>doInitialization</tt> method call is not
+scheduled to overlap with any other pass executions (thus it should be very
+fast).<p>
A good example of how this method should be used is the <a
href="http://llvm.cs.uiuc.edu/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations</a>
pass. This pass converts <tt>malloc</tt> and <tt>free</tt> instructions into
-platform dependant <tt>malloc()</tt> and <tt>free()</tt> function calls. It
+platform dependent <tt>malloc()</tt> and <tt>free()</tt> function calls. It
uses the <tt>doInitialization</tt> method to get a reference to the malloc and
-free functions that it needs, adding prototypes to the module if neccesary.<p>
+free functions that it needs, adding prototypes to the module if necessary.<p>
<!-- _______________________________________________________________________ -->
</ul><h4><a name="runOnFunction"><hr size=0>The <tt>runOnFunction</tt> method</h4><ul>
returned if the function is modified.<p>
<!-- _______________________________________________________________________ -->
-</ul><h4><a name="doFinalization"><hr size=0>The <tt>doFinalization</tt> method</h4><ul>
+</ul><h4><a name="doFinalization_mod"><hr size=0>The <tt>doFinalization(Module &)</tt> method</h4><ul>
<pre>
<b>virtual bool</b> doFinalization(Module &M);
-</pre</p>
+</pre></p>
The <tt>doFinalization</tt> method is an infrequently used method that is called
when the pass framework has finished calling <a
<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>
+href="#doInitialization_mod"><tt>doInitialization(Module &)</tt></a> and <a
+href="#doFinalization_mod"><tt>doFinalization(Module &)</tt></a> methods that <a
+href="#FunctionPass"><tt>FunctionPass</tt></a>'s have, but also have the following virtual methods that may also be implemented:<p>
+
+<!-- _______________________________________________________________________ -->
+</ul><h4><a name="doInitialization_fn"><hr size=0>The
+<tt>doInitialization(Function &)</tt> method</h4><ul>
+
+<pre>
+ <b>virtual bool</b> doInitialization(Function &F);
+</pre><p>
+
+The <tt>doIninitialize</tt> method is allowed to do most of the things that
+<tt>BasicBlockPass</tt>'s are not allowed to do, but that
+<tt>FunctionPass</tt>'s can. The <tt>doInitialization</tt> method is designed
+to do simple initialization type of stuff that does not depend on the
+BasicBlocks being processed. The <tt>doInitialization</tt> method call is not
+scheduled to overlap with any other pass executions (thus it should be very
+fast).<p>
+
<!-- _______________________________________________________________________ -->
</ul><h4><a name="runOnBasicBlock"><hr size=0>The <tt>runOnBasicBlock</tt> method</h4><ul>
if the basic block is modified.<p>
+<!-- _______________________________________________________________________ -->
+</ul><h4><a name="doFinalization_fn"><hr size=0>The <tt>doFinalization(Function
+&)</tt> method</h4><ul>
+
+<pre>
+ <b>virtual bool</b> doFinalization(Function &F);
+</pre></p>
+
+The <tt>doFinalization</tt> method is an infrequently used method that is called
+when the pass framework has finished calling <a
+href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a> for every BasicBlock in the
+program being compiled. This can be used to perform per-function
+finalization.<p>
+
+
+<!-- ======================================================================= -->
+</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
+<tr><td> </td><td width="100%">
+<font color="#EEEEFF" face="Georgia,Palatino"><b>
+<a name="MachineFunctionPass">The <tt>MachineFunctionPass</tt> class
+</b></font></td></tr></table><ul>
+
+A <tt>MachineFunctionPass</tt> executes on the machine-dependent
+representation of each LLVM function in the program,
+independent of all of the other functions in the program.
+A <tt>MachineFunctionPass</tt> is also a <tt>FunctionPass</tt>, so all
+the restrictions that apply to a <tt>FunctionPass</tt> also apply to it.
+<tt>MachineFunctionPass</tt>es also have additional restrictions. In
+particular, <tt>MachineFunctionPass</tt>es are not allowed to do any of
+the following:
+
+<ol>
+<li>Modify any LLVM Instructions, BasicBlocks or Functions.
+<li>Modify a MachineFunction other than the one currently being processed.
+<li>Add or remove MachineFunctions from the current Module.
+<li>Add or remove global variables from the current Module.
+<li>Maintain state across invocations of
+ <a href="#runOnMachineFunction"><tt>runOnMachineFunction</tt></a> (including global data)
+</ol><p>
+
+
+<!-- _______________________________________________________________________ -->
+</ul><h4><a name="runOnMachineFunction"><hr size=0>The
+<tt>runOnMachineFunction(MachineFunction &MF)</tt> method</h4><ul>
+
+<pre>
+ <b>virtual bool</b> runOnMachineFunction(MachineFunction &MF) = 0;
+</pre></p>
+
+<tt>runOnMachineFunction</tt> can be considered the main entry point
+of a <tt>MachineFunctionPass</tt>; that is, you should override this
+method to do the work of your <tt>MachineFunctionPass</tt>. <p>
+
+The <tt>runOnMachineFunction</tt> method is called on every
+<tt>MachineFunction</tt> in a <tt>Module</tt>, so that the
+<tt>MachineFunctionPass</tt> may perform optimizations on the
+machine-dependent representation of the function. If you want to get
+at the LLVM <tt>Function</tt> for the <tt>MachineFunction</tt> you're
+working on, use <tt>MachineFunction</tt>'s <tt>getFunction()</tt>
+accessor method -- but remember, you may not modify the LLVM
+<tt>Function</tt> or its contents from a
+<tt>MachineFunctionPass</tt>. <p>
+
<!-- *********************************************************************** -->
</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
<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:
+ <i>// setPreservesCFG - This function should be called by the pass, iff they do not:
//
// 1. Add or remove basic blocks from the function
// 2. Modify terminator instructions in any way.
//
// This is automatically implied for <a href="#BasicBlockPass">BasicBlockPass</a>'s
//</i>
- <b>void</b> AnalysisUsage::preservesCFG();
+ <b>void</b> AnalysisUsage::setPreservesCFG();
</pre><p>
Some examples of how to use these methods are:<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.setPreservesCFG();
AU.addRequired<<a href="http://llvm.cs.uiuc.edu/doxygen/classLoopInfo.html">LoopInfo</a>>();
}
</pre><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>
<!-- _______________________________________________________________________ -->
</ul><h4><a name="SMP"><hr size=0>Multithreaded LLVM</h4><ul>
-Multiple CPU machines are becoming more command and compilation can never be
+Multiple CPU machines are becoming more common and compilation can never be
fast enough: obviously we should allow for a multithreaded compiler. Because of
the semantics defined for passes above (specifically they cannot maintain state
across invocations of their <tt>run*</tt> methods), a nice clean way to
implement a multithreaded compiler would be for the <tt>PassManager</tt> class
-to create multiple instances of each pass object, and allow the seperate
+to create multiple instances of each pass object, and allow the separate
instances to be hacking on different parts of the program at the same time.<p>
This implementation would prevent each of the passes from having to implement
<!-- *********************************************************************** -->
<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 22 14:19:43 CDT 2002
+Last modified: Tue Jul 22 15:52:30 CDT 2003
<!-- hhmts end -->
</font></body></html>