Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / d55c9bf318ceb5c1f3a0a31b2e5e2bf1ad5db2b7 / . / docs / WritingAnLLVMPass.html
blob: 0cc779243e4261a179bc635cf44d3583c656e323 [file] [log] [blame]
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3<html>
4<head>
5 <title>Writing an LLVM Pass</title>
6 <link rel="stylesheet" href="llvm.css" type="text/css">
7</head>
8<body>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]9
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]10<div class="doc_title">
11 Writing an LLVM Pass
12</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]13
14<ol>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]15 <li><a href="#introduction">Introduction - What is a pass?</a></li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]16 <li><a href="#quickstart">Quick Start - Writing hello world</a>
17 <ul>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]18 <li><a href="#makefile">Setting up the build environment</a></li>
19 <li><a href="#basiccode">Basic code required</a></li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]20 <li><a href="#running">Running a pass with <tt>opt</tt>
Chris Lattner8fdb2462004-09-18 06:39:35 +0000[diff] [blame]21 or <tt>analyze</tt></a></li>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]22 </ul></li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]23 <li><a href="#passtype">Pass classes and requirements</a>
24 <ul>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]25 <li><a href="#ImmutablePass">The <tt>ImmutablePass</tt> class</a></li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]26 <li><a href="#Pass">The <tt>Pass</tt> class</a>
27 <ul>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]28 <li><a href="#run">The <tt>run</tt> method</a></li>
29 </ul></li>
Chris Lattner8fdb2462004-09-18 06:39:35 +0000[diff] [blame]30 <li><a href="#CallGraphSCCPass">The <tt>CallGraphSCCPass</tt> class</a>
31 <ul>
32 <li><a href="#doInitialization_scc">The <tt>doInitialization(Module
33 &amp;)</tt> method</a></li>
34 <li><a href="#runOnSCC">The <tt>runOnSCC</tt> method</a></li>
35 <li><a href="#doFinalization_scc">The <tt>doFinalization(Module
36 &amp;)</tt> method</a></li>
37 </ul></li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]38 <li><a href="#FunctionPass">The <tt>FunctionPass</tt> class</a>
39 <ul>
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]40 <li><a href="#doInitialization_mod">The <tt>doInitialization(Module
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]41 &amp;)</tt> method</a></li>
42 <li><a href="#runOnFunction">The <tt>runOnFunction</tt> method</a></li>
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]43 <li><a href="#doFinalization_mod">The <tt>doFinalization(Module
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]44 &amp;)</tt> method</a></li>
45 </ul></li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]46 <li><a href="#BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
47 <ul>
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]48 <li><a href="#doInitialization_fn">The <tt>doInitialization(Function
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]49 &amp;)</tt> method</a></li>
50 <li><a href="#runOnBasicBlock">The <tt>runOnBasicBlock</tt>
51 method</a></li>
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]52 <li><a href="#doFinalization_fn">The <tt>doFinalization(Function
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]53 &amp;)</tt> method</a></li>
54 </ul></li>
Brian Gaekecab8b6f2003-07-17 18:53:20 +0000[diff] [blame]55 <li><a href="#MachineFunctionPass">The <tt>MachineFunctionPass</tt>
56 class</a>
Brian Gaeke6a33f362003-07-22 20:53:20 +0000[diff] [blame]57 <ul>
58 <li><a href="#runOnMachineFunction">The
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]59 <tt>runOnMachineFunction(MachineFunction &amp;)</tt> method</a></li>
60 </ul></li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]61 </ul>
62 <li><a href="#registration">Pass Registration</a>
63 <ul>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]64 <li><a href="#print">The <tt>print</tt> method</a></li>
65 </ul></li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]66 <li><a href="#interaction">Specifying interactions between passes</a>
67 <ul>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]68 <li><a href="#getAnalysisUsage">The <tt>getAnalysisUsage</tt>
69 method</a></li>
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]70 <li><a href="#AU::addRequired">The <tt>AnalysisUsage::addRequired&lt;&gt;</tt> and <tt>AnalysisUsage::addRequiredTransitive&lt;&gt;</tt> methods</a></li>
71 <li><a href="#AU::addPreserved">The <tt>AnalysisUsage::addPreserved&lt;&gt;</tt> method</a></li>
72 <li><a href="#AU::examples">Example implementations of <tt>getAnalysisUsage</tt></a></li>
73 <li><a href="#getAnalysis">The <tt>getAnalysis&lt;&gt;</tt> and <tt>getAnalysisToUpdate&lt;&gt;</tt> methods</a></li>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]74 </ul></li>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]75 <li><a href="#analysisgroup">Implementing Analysis Groups</a>
76 <ul>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]77 <li><a href="#agconcepts">Analysis Group Concepts</a></li>
78 <li><a href="#registerag">Using <tt>RegisterAnalysisGroup</tt></a></li>
79 </ul></li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]80 <li><a href="#passmanager">What PassManager does</a>
81 <ul>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]82 <li><a href="#releaseMemory">The <tt>releaseMemory</tt> method</a></li>
83 </ul></li>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]84 <li><a href="#debughints">Using GDB with dynamically loaded passes</a>
85 <ul>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]86 <li><a href="#breakpoint">Setting a breakpoint in your pass</a></li>
87 <li><a href="#debugmisc">Miscellaneous Problems</a></li>
88 </ul></li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]89 <li><a href="#future">Future extensions planned</a>
90 <ul>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]91 <li><a href="#SMP">Multithreaded LLVM</a></li>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]92 <li><a href="#PassFunctionPass"><tt>Pass</tt>es requiring
93 <tt>FunctionPass</tt>es</a></li>
94 </ul></li>
95</ol>
Chris Lattner38c633d2002-08-08 20:23:41 +0000[diff] [blame]96
Chris Lattner7911ce22004-05-23 21:07:27 +0000[diff] [blame]97<div class="doc_author">
98 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]99</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]100
101<!-- *********************************************************************** -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]102<div class="doc_section">
103 <a name="introduction">Introduction - What is a pass?</a>
104</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]105<!-- *********************************************************************** -->
106
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]107<div class="doc_text">
108
109<p>The LLVM Pass Framework is an important part of the LLVM system, because LLVM
Chris Lattner8fdb2462004-09-18 06:39:35 +0000[diff] [blame]110passes are where most of the interesting parts of the compiler exist. Passes
111perform the transformations and optimizations that make up the compiler, they
112build the analysis results that are used by these transformations, and they are,
113above all, a structuring technique for compiler code.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]114
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]115<p>All LLVM passes are subclasses of the <tt><a
116href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1Pass.html">Pass</a></tt>
117class, which implement functionality by overriding virtual methods inherited
118from <tt>Pass</tt>. Depending on how your pass works, you may be able to
Chris Lattner8fdb2462004-09-18 06:39:35 +0000[diff] [blame]119inherit from the <tt><a href="#CallGraphSCCPass">CallGraphSCCPass</a></tt>,
120<tt><a href="#FunctionPass">FunctionPass</a></tt>, or <tt><a
121href="#BasicBlockPass">BasicBlockPass</a></tt> classes, which gives the system
122more information about what your pass does, and how it can be combined with
123other passes. One of the main features of the LLVM Pass Framework is that it
124schedules passes to run in an efficient way based on the constraints that your
125pass meets (which are indicated by which class they derive from).</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]126
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]127<p>We start by showing you how to construct a pass, everything from setting up
128the code, to compiling, loading, and executing it. After the basics are down,
129more advanced features are discussed.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]130
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]131</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]132
133<!-- *********************************************************************** -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]134<div class="doc_section">
135 <a name="quickstart">Quick Start - Writing hello world</a>
136</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]137<!-- *********************************************************************** -->
138
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]139<div class="doc_text">
140
141<p>Here we describe how to write the "hello world" of passes. The "Hello" pass
142is designed to simply print out the name of non-external functions that exist in
Chris Lattner8fdb2462004-09-18 06:39:35 +0000[diff] [blame]143the program being compiled. It does not modify the program at all, it just
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]144inspects it. The source code and files for this pass are available in the LLVM
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]145source tree in the <tt>lib/Transforms/Hello</tt> directory.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]146
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]147</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]148
149<!-- ======================================================================= -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]150<div class="doc_subsection">
151 <a name="makefile">Setting up the build environment</a>
152</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]153
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]154<div class="doc_text">
155
156<p>First thing you need to do is create a new directory somewhere in the LLVM
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]157source base. For this example, we'll assume that you made
158"<tt>lib/Transforms/Hello</tt>". The first thing you must do is set up a build
159script (Makefile) that will compile the source code for the new pass. To do
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]160this, copy this into "<tt>Makefile</tt>":</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]161
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]162<hr>
163
164<pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]165# Makefile for hello pass
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]166
Chris Lattner17a4c3e2002-08-14 20:06:13 +0000[diff] [blame]167# Path to top level of LLVM heirarchy
Chris Lattner7ce83e52002-08-14 20:07:01 +0000[diff] [blame]168LEVEL = ../../..
Chris Lattner17a4c3e2002-08-14 20:06:13 +0000[diff] [blame]169
170# Name of the library to build
Chris Lattner7ce83e52002-08-14 20:07:01 +0000[diff] [blame]171LIBRARYNAME = hello
Chris Lattner17a4c3e2002-08-14 20:06:13 +0000[diff] [blame]172
173# Build a dynamically loadable shared object
174SHARED_LIBRARY = 1
175
176# Include the makefile implementation stuff
177include $(LEVEL)/Makefile.common
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]178</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]179
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]180<p>This makefile specifies that all of the <tt>.cpp</tt> files in the current
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]181directory are to be compiled and linked together into a
182<tt>lib/Debug/libhello.so</tt> shared object that can be dynamically loaded by
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]183the <tt>opt</tt> or <tt>analyze</tt> tools. If your operating system uses a
Chris Lattner8fdb2462004-09-18 06:39:35 +0000[diff] [blame]184suffix other than .so (such as windows or Mac OS/X), the appropriate extension
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]185will be used.</p>
John Criswellf9c78652004-01-26 21:26:54 +0000[diff] [blame]186
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]187<p>Now that we have the build scripts set up, we just need to write the code for
188the pass itself.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]189
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]190</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]191
192<!-- ======================================================================= -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]193<div class="doc_subsection">
194 <a name="basiccode">Basic code required</a>
195</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]196
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]197<div class="doc_text">
198
199<p>Now that we have a way to compile our new pass, we just have to write it.
200Start out with:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]201
202<pre>
203<b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
204<b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Function_8h-source.html">llvm/Function.h</a>"
205</pre>
206
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]207<p>Which are needed because we are writing a <tt><a
208href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1Pass.html">Pass</a></tt>, and
209we are operating on <tt><a
210href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1Function.html">Function</a></tt>'s.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]211
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]212<p>Next we have:</p>
Jonathan Manton65acb302004-06-30 18:10:30 +0000[diff] [blame]213<pre>
214<b>using namespace llvm;</b>
215</pre>
216<p>... which is required because the functions from the include files
217live in the llvm namespace.
218</p>
219
220<p>Next we have:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]221
222<pre>
223<b>namespace</b> {
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]224</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]225
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]226<p>... which starts out an anonymous namespace. Anonymous namespaces are to C++
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]227what the "<tt>static</tt>" keyword is to C (at global scope). It makes the
228things declared inside of the anonymous namespace only visible to the current
229file. If you're not familiar with them, consult a decent C++ book for more
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]230information.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]231
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]232<p>Next, we declare our pass itself:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]233
234<pre>
235 <b>struct</b> Hello : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
236</pre><p>
237
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]238<p>This declares a "<tt>Hello</tt>" class that is a subclass of <tt><a
239href="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1FunctionPass.html">FunctionPass</a></tt>.
Chris Lattnerd6ea9262002-09-09 03:48:46 +0000[diff] [blame]240The different builtin pass subclasses are described in detail <a
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]241href="#passtype">later</a>, but for now, know that <a
242href="#FunctionPass"><tt>FunctionPass</tt></a>'s operate a function at a
243time.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]244
245<pre>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]246 <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &amp;F) {
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]247 std::cerr &lt;&lt; "<i>Hello: </i>" &lt;&lt; F.getName() &lt;&lt; "\n";
248 <b>return false</b>;
249 }
250 }; <i>// end of struct Hello</i>
251</pre>
252
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]253<p>We declare a "<a href="#runOnFunction"><tt>runOnFunction</tt></a>" method,
254which overloads an abstract virtual method inherited from <a
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]255href="#FunctionPass"><tt>FunctionPass</tt></a>. This is where we are supposed
256to do our thing, so we just print out our message with the name of each
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]257function.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]258
259<pre>
260 RegisterOpt&lt;Hello&gt; X("<i>hello</i>", "<i>Hello World Pass</i>");
261} <i>// end of anonymous namespace</i>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]262</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]263
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]264<p>Lastly, we register our class <tt>Hello</tt>, giving it a command line
265argument "<tt>hello</tt>", and a name "<tt>Hello World Pass</tt>". There are
266several different ways of <a href="#registration">registering your pass</a>,
267depending on what it is to be used for. For "optimizations" we use the
268<tt>RegisterOpt</tt> template.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]269
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]270<p>As a whole, the <tt>.cpp</tt> file looks like:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]271
272<pre>
273<b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
274<b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Function_8h-source.html">llvm/Function.h</a>"
275
Jonathan Manton65acb302004-06-30 18:10:30 +0000[diff] [blame]276<b>using namespace llvm;</b>
277
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]278<b>namespace</b> {
279 <b>struct Hello</b> : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]280 <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &amp;F) {
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]281 std::cerr &lt;&lt; "<i>Hello: </i>" &lt;&lt; F.getName() &lt;&lt; "\n";
282 <b>return false</b>;
283 }
284 };
285
286 RegisterOpt&lt;Hello&gt; X("<i>hello</i>", "<i>Hello World Pass</i>");
287}
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]288</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]289
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]290<p>Now that it's all together, compile the file with a simple "<tt>gmake</tt>"
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]291command in the local directory and you should get a new
292"<tt>lib/Debug/libhello.so</tt> file. Note that everything in this file is
293contained in an anonymous namespace: this reflects the fact that passes are self
294contained units that do not need external interfaces (although they can have
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]295them) to be useful.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]296
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]297</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]298
299<!-- ======================================================================= -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]300<div class="doc_subsection">
301 <a name="running">Running a pass with <tt>opt</tt> or <tt>analyze</tt></a>
302</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]303
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]304<div class="doc_text">
305
John Criswellf9c78652004-01-26 21:26:54 +0000[diff] [blame]306<p>Now that you have a brand new shiny shared object file, we can use the
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]307<tt>opt</tt> command to run an LLVM program through your pass. Because you
308registered your pass with the <tt>RegisterOpt</tt> template, you will be able to
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]309use the <tt>opt</tt> tool to access it, once loaded.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]310
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]311<p>To test it, follow the example at the end of the <a
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]312href="GettingStarted.html">Getting Started Guide</a> to compile "Hello World" to
313LLVM. We can now run the bytecode file (<tt>hello.bc</tt>) for the program
314through our transformation like this (or course, any bytecode file will
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]315work):</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]316
317<pre>
318$ opt -load ../../../lib/Debug/libhello.so -hello &lt; hello.bc &gt; /dev/null
319Hello: __main
320Hello: puts
321Hello: main
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]322</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]323
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]324<p>The '<tt>-load</tt>' option specifies that '<tt>opt</tt>' should load your
325pass as a shared object, which makes '<tt>-hello</tt>' a valid command line
326argument (which is one reason you need to <a href="#registration">register your
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]327pass</a>). Because the hello pass does not modify the program in any
328interesting way, we just throw away the result of <tt>opt</tt> (sending it to
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]329<tt>/dev/null</tt>).</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]330
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]331<p>To see what happened to the other string you registered, try running
332<tt>opt</tt> with the <tt>--help</tt> option:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]333
334<pre>
335$ opt -load ../../../lib/Debug/libhello.so --help
336OVERVIEW: llvm .bc -&gt; .bc modular optimizer
337
338USAGE: opt [options] &lt;input bytecode&gt;
339
340OPTIONS:
341 Optimizations available:
342...
343 -funcresolve - Resolve Functions
344 -gcse - Global Common Subexpression Elimination
345 -globaldce - Dead Global Elimination
346 <b>-hello - Hello World Pass</b>
Chris Lattner065a6162003-09-10 05:29:43 +0000[diff] [blame]347 -indvars - Canonicalize Induction Variables
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]348 -inline - Function Integration/Inlining
349 -instcombine - Combine redundant instructions
350...
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]351</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]352
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]353<p>The pass name get added as the information string for your pass, giving some
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]354documentation to users of <tt>opt</tt>. Now that you have a working pass, you
355would go ahead and make it do the cool transformations you want. Once you get
356it all working and tested, it may become useful to find out how fast your pass
357is. The <a href="#passManager"><tt>PassManager</tt></a> provides a nice command
358line option (<tt>--time-passes</tt>) that allows you to get information about
359the execution time of your pass along with the other passes you queue up. For
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]360example:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]361
362<pre>
363$ opt -load ../../../lib/Debug/libhello.so -hello -time-passes &lt; hello.bc &gt; /dev/null
364Hello: __main
365Hello: puts
366Hello: main
367===============================================================================
368 ... Pass execution timing report ...
369===============================================================================
370 Total Execution Time: 0.02 seconds (0.0479059 wall clock)
371
372 ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Pass Name ---
373 0.0100 (100.0%) 0.0000 ( 0.0%) 0.0100 ( 50.0%) 0.0402 ( 84.0%) Bytecode Writer
374 0.0000 ( 0.0%) 0.0100 (100.0%) 0.0100 ( 50.0%) 0.0031 ( 6.4%) Dominator Set Construction
375 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0013 ( 2.7%) Module Verifier
376 <b> 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0033 ( 6.9%) Hello World Pass</b>
377 0.0100 (100.0%) 0.0100 (100.0%) 0.0200 (100.0%) 0.0479 (100.0%) TOTAL
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]378</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]379
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]380<p>As you can see, our implementation above is pretty fast :). The additional
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]381passes listed are automatically inserted by the '<tt>opt</tt>' tool to verify
382that the LLVM emitted by your pass is still valid and well formed LLVM, which
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]383hasn't been broken somehow.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]384
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]385<p>Now that you have seen the basics of the mechanics behind passes, we can talk
386about some more details of how they work and how to use them.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]387
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]388</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]389
390<!-- *********************************************************************** -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]391<div class="doc_section">
392 <a name="passtype">Pass classes and requirements</a>
393</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]394<!-- *********************************************************************** -->
395
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]396<div class="doc_text">
397
398<p>One of the first things that you should do when designing a new pass is to
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]399decide what class you should subclass for your pass. The <a
400href="#basiccode">Hello World</a> example uses the <tt><a
401href="#FunctionPass">FunctionPass</a></tt> class for its implementation, but we
402did not discuss why or when this should occur. Here we talk about the classes
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]403available, from the most general to the most specific.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]404
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]405<p>When choosing a superclass for your Pass, you should choose the <b>most
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]406specific</b> class possible, while still being able to meet the requirements
Misha Brukman5560c9d2003-08-18 14:43:39 +0000[diff] [blame]407listed. This gives the LLVM Pass Infrastructure information necessary to
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]408optimize how passes are run, so that the resultant compiler isn't unneccesarily
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]409slow.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]410
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]411</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]412
Chris Lattnerf004f9a2002-09-25 22:31:38 +0000[diff] [blame]413<!-- ======================================================================= -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]414<div class="doc_subsection">
415 <a name="ImmutablePass">The <tt>ImmutablePass</tt> class</a>
416</div>
Chris Lattnerf004f9a2002-09-25 22:31:38 +0000[diff] [blame]417
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]418<div class="doc_text">
419
420<p>The most plain and boring type of pass is the "<tt><a
421href="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1ImmutablePass.html">ImmutablePass</a></tt>"
Chris Lattnerf004f9a2002-09-25 22:31:38 +0000[diff] [blame]422class. This pass type is used for passes that do not have to be run, do not
423change state, and never need to be updated. This is not a normal type of
424transformation or analysis, but can provide information about the current
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]425compiler configuration.</p>
Chris Lattnerf004f9a2002-09-25 22:31:38 +0000[diff] [blame]426
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]427<p>Although this pass class is very infrequently used, it is important for
Chris Lattnerf004f9a2002-09-25 22:31:38 +0000[diff] [blame]428providing information about the current target machine being compiled for, and
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]429other static information that can affect the various transformations.</p>
Chris Lattnerf004f9a2002-09-25 22:31:38 +0000[diff] [blame]430
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]431<p><tt>ImmutablePass</tt>es never invalidate other transformations, are never
432invalidated, and are never "run".</p>
Chris Lattnerf004f9a2002-09-25 22:31:38 +0000[diff] [blame]433
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]434</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]435
436<!-- ======================================================================= -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]437<div class="doc_subsection">
438 <a name="Pass">The <tt>Pass</tt> class</a>
439</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]440
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]441<div class="doc_text">
442
443<p>The "<tt><a
444href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1Pass.html">Pass</a></tt>"
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]445class is the most general of all superclasses that you can use. Deriving from
446<tt>Pass</tt> indicates that your pass uses the entire program as a unit,
447refering to function bodies in no predictable order, or adding and removing
448functions. Because nothing is known about the behavior of direct <tt>Pass</tt>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]449subclasses, no optimization can be done for their execution.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]450
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]451<p>To write a correct <tt>Pass</tt> subclass, derive from <tt>Pass</tt> and
452overload the <tt>run</tt> method with the following signature:</p>
453
454</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]455
456<!-- _______________________________________________________________________ -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]457<div class="doc_subsubsection">
458 <a name="run">The <tt>run</tt> method</a>
459</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]460
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]461<div class="doc_text">
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]462
463<pre>
464 <b>virtual bool</b> run(Module &amp;M) = 0;
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]465</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]466
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]467<p>The <tt>run</tt> method performs the interesting work of the pass, and should
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]468return true if the module was modified by the transformation, false
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]469otherwise.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]470
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]471</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]472
473<!-- ======================================================================= -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]474<div class="doc_subsection">
Chris Lattner8fdb2462004-09-18 06:39:35 +0000[diff] [blame]475 <a name="CallGraphSCCPass">The <tt>CallGraphSCCPass</tt> class</a>
476</div>
477
478<div class="doc_text">
479
480<p>The "<tt><a
481href="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1CallGraphSCCPass.html">CallGraphSCCPass</a></tt>"
482is used by passes that need to traverse the program bottom-up on the call graph
483(callees before callers). Deriving from CallGraphSCCPass provides some
484mechanics for building and traversing the CallGraph, but also allows the system
485to optimize execution of CallGraphSCCPass's. If your pass meets the
486requirements outlined below, and doesn't meet the requirements of a <tt><a
487href="#FunctionPass">FunctionPass</a></tt> or <tt><a
488href="#BasicBlockPass">BasicBlockPass</a></tt>, you should derive from
489<tt>CallGraphSCCPass</tt>.</p>
490
491<p><b>TODO</b>: explain briefly what SCC, Tarjan's algo, and B-U mean.</p>
492
493<p>To be explicit, <tt>CallGraphSCCPass</tt> subclasses are:</p>
494
495<ol>
496
497<li>... <em>not allowed</em> to modify any <tt>Function</tt>s that are not in
498the current SCC.</li>
499
500<li>... <em>allowed</em> to inspect any Function's other than those in the
501current SCC and the direct callees of the SCC.</li>
502
503<li>... <em>required</em> to preserve the current CallGraph object, updating it
504to reflect any changes made to the program.</li>
505
506<li>... <em>not allowed</em> to add or remove SCC's from the current Module,
507though they may change the contents of an SCC.</li>
508
509<li>... <em>allowed</em> to add or remove global variables from the current
510Module.</li>
511
512<li>... <em>allowed</em> to maintain state across invocations of
513 <a href="#runOnSCC"><tt>runOnSCC</tt></a> (including global data).</li>
514</ol>
515
516<p>Implementing a <tt>CallGraphSCCPass</tt> is slightly tricky in some cases
517because it has to handle SCCs with more than one node in it. All of the virtual
518methods described below should return true if they modified the program, or
519false if they didn't.</p>
520
521</div>
522
523<!-- _______________________________________________________________________ -->
524<div class="doc_subsubsection">
525 <a name="doInitialization_scc">The <tt>doInitialization(Module &amp;)</tt>
526 method</a>
527</div>
528
529<div class="doc_text">
530
531<pre>
532 <b>virtual bool</b> doInitialization(Module &amp;M);
533</pre>
534
535<p>The <tt>doIninitialize</tt> method is allowed to do most of the things that
536<tt>CallGraphSCCPass</tt>'s are not allowed to do. They can add and remove
537functions, get pointers to functions, etc. The <tt>doInitialization</tt> method
538is designed to do simple initialization type of stuff that does not depend on
539the SCCs being processed. The <tt>doInitialization</tt> method call is not
540scheduled to overlap with any other pass executions (thus it should be very
541fast).</p>
542
543</div>
544
545<!-- _______________________________________________________________________ -->
546<div class="doc_subsubsection">
547 <a name="runOnSCC">The <tt>runOnSCC</tt> method</a>
548</div>
549
550<div class="doc_text">
551
552<pre>
553 <b>virtual bool</b> runOnSCC(const std::vector&lt;CallGraphNode *&gt; &amp;SCCM) = 0;
554</pre>
555
556<p>The <tt>runOnSCC</tt> method performs the interesting work of the pass, and
557should return true if the module was modified by the transformation, false
558otherwise.</p>
559
560</div>
561
562<!-- _______________________________________________________________________ -->
563<div class="doc_subsubsection">
564 <a name="doFinalization_scc">The <tt>doFinalization(Module
565 &amp;)</tt> method</a>
566</div>
567
568<div class="doc_text">
569
570<pre>
571 <b>virtual bool</b> doFinalization(Module &amp;M);
572</pre>
573
574<p>The <tt>doFinalization</tt> method is an infrequently used method that is
575called when the pass framework has finished calling <a
576href="#runOnFunction"><tt>runOnFunction</tt></a> for every function in the
577program being compiled.</p>
578
579</div>
580
581<!-- ======================================================================= -->
582<div class="doc_subsection">
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]583 <a name="FunctionPass">The <tt>FunctionPass</tt> class</a>
584</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]585
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]586<div class="doc_text">
587
588<p>In contrast to direct <tt>Pass</tt> subclasses, direct <tt><a
589href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1Pass.html">FunctionPass</a></tt>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]590subclasses do have a predictable, local behavior that can be expected by the
591system. All <tt>FunctionPass</tt> execute on each function in the program
Misha Brukmanef6a6a62003-08-21 22:14:26 +0000[diff] [blame]592independent of all of the other functions in the program.
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]593<tt>FunctionPass</tt>'s do not require that they are executed in a particular
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]594order, and <tt>FunctionPass</tt>'s do not modify external functions.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]595
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]596<p>To be explicit, <tt>FunctionPass</tt> subclasses are not allowed to:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]597
598<ol>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]599<li>Modify a Function other than the one currently being processed.</li>
600<li>Add or remove Function's from the current Module.</li>
601<li>Add or remove global variables from the current Module.</li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]602<li>Maintain state across invocations of
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]603 <a href="#runOnFunction"><tt>runOnFunction</tt></a> (including global data)</li>
604</ol>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]605
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]606<p>Implementing a <tt>FunctionPass</tt> is usually straightforward (See the <a
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]607href="#basiccode">Hello World</a> pass for example). <tt>FunctionPass</tt>'s
608may overload three virtual methods to do their work. All of these methods
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]609should return true if they modified the program, or false if they didn't.</p>
610
611</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]612
613<!-- _______________________________________________________________________ -->
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]614<div class="doc_subsubsection">
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]615 <a name="doInitialization_mod">The <tt>doInitialization(Module &amp;)</tt>
616 method</a>
617</div>
618
619<div class="doc_text">
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]620
621<pre>
622 <b>virtual bool</b> doInitialization(Module &amp;M);
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]623</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]624
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]625<p>The <tt>doIninitialize</tt> method is allowed to do most of the things that
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]626<tt>FunctionPass</tt>'s are not allowed to do. They can add and remove
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]627functions, get pointers to functions, etc. The <tt>doInitialization</tt> method
628is designed to do simple initialization type of stuff that does not depend on
629the functions being processed. The <tt>doInitialization</tt> method call is not
630scheduled to overlap with any other pass executions (thus it should be very
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]631fast).</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]632
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]633<p>A good example of how this method should be used is the <a
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]634href="http://llvm.cs.uiuc.edu/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations</a>
635pass. This pass converts <tt>malloc</tt> and <tt>free</tt> instructions into
Misha Brukmanef6a6a62003-08-21 22:14:26 +0000[diff] [blame]636platform dependent <tt>malloc()</tt> and <tt>free()</tt> function calls. It
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]637uses the <tt>doInitialization</tt> method to get a reference to the malloc and
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]638free functions that it needs, adding prototypes to the module if necessary.</p>
639
640</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]641
642<!-- _______________________________________________________________________ -->
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]643<div class="doc_subsubsection">
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]644 <a name="runOnFunction">The <tt>runOnFunction</tt> method</a>
645</div>
646
647<div class="doc_text">
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]648
649<pre>
650 <b>virtual bool</b> runOnFunction(Function &amp;F) = 0;
651</pre><p>
652
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]653<p>The <tt>runOnFunction</tt> method must be implemented by your subclass to do
654the transformation or analysis work of your pass. As usual, a true value should
655be returned if the function is modified.</p>
656
657</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]658
659<!-- _______________________________________________________________________ -->
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]660<div class="doc_subsubsection">
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]661 <a name="doFinalization_mod">The <tt>doFinalization(Module
662 &amp;)</tt> method</a>
663</div>
664
665<div class="doc_text">
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]666
667<pre>
668 <b>virtual bool</b> doFinalization(Module &amp;M);
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]669</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]670
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]671<p>The <tt>doFinalization</tt> method is an infrequently used method that is
672called when the pass framework has finished calling <a
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]673href="#runOnFunction"><tt>runOnFunction</tt></a> for every function in the
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]674program being compiled.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]675
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]676</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]677
678<!-- ======================================================================= -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]679<div class="doc_subsection">
680 <a name="BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
681</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]682
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]683<div class="doc_text">
684
685<p><tt>BasicBlockPass</tt>'s are just like <a
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]686href="#FunctionPass"><tt>FunctionPass</tt></a>'s, except that they must limit
687their scope of inspection and modification to a single basic block at a time.
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]688As such, they are <b>not</b> allowed to do any of the following:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]689
690<ol>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]691<li>Modify or inspect any basic blocks outside of the current one</li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]692<li>Maintain state across invocations of
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]693 <a href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a></li>
694<li>Modify the constrol flow graph (by altering terminator instructions)</li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]695<li>Any of the things verboten for
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]696 <a href="#FunctionPass"><tt>FunctionPass</tt></a>es.</li>
697</ol>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]698
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]699<p><tt>BasicBlockPass</tt>es are useful for traditional local and "peephole"
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]700optimizations. They may override the same <a
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]701href="#doInitialization_mod"><tt>doInitialization(Module &amp;)</tt></a> and <a
702href="#doFinalization_mod"><tt>doFinalization(Module &amp;)</tt></a> methods that <a
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]703href="#FunctionPass"><tt>FunctionPass</tt></a>'s have, but also have the following virtual methods that may also be implemented:</p>
704
705</div>
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]706
707<!-- _______________________________________________________________________ -->
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]708<div class="doc_subsubsection">
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]709 <a name="doInitialization_fn">The <tt>doInitialization(Function
710 &amp;)</tt> method</a>
711</div>
712
713<div class="doc_text">
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]714
715<pre>
716 <b>virtual bool</b> doInitialization(Function &amp;F);
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]717</pre>
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]718
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]719<p>The <tt>doIninitialize</tt> method is allowed to do most of the things that
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]720<tt>BasicBlockPass</tt>'s are not allowed to do, but that
721<tt>FunctionPass</tt>'s can. The <tt>doInitialization</tt> method is designed
722to do simple initialization type of stuff that does not depend on the
723BasicBlocks being processed. The <tt>doInitialization</tt> method call is not
724scheduled to overlap with any other pass executions (thus it should be very
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]725fast).</p>
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]726
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]727</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]728
729<!-- _______________________________________________________________________ -->
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]730<div class="doc_subsubsection">
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]731 <a name="runOnBasicBlock">The <tt>runOnBasicBlock</tt> method</a>
732</div>
733
734<div class="doc_text">
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]735
736<pre>
737 <b>virtual bool</b> runOnBasicBlock(BasicBlock &amp;BB) = 0;
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]738</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]739
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]740<p>Override this function to do the work of the <tt>BasicBlockPass</tt>. This
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]741function is not allowed to inspect or modify basic blocks other than the
742parameter, and are not allowed to modify the CFG. A true value must be returned
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]743if the basic block is modified.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]744
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]745</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]746
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]747<!-- _______________________________________________________________________ -->
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]748<div class="doc_subsubsection">
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]749 <a name="doFinalization_fn">The <tt>doFinalization(Function &amp;)</tt>
750 method</a>
751</div>
752
753<div class="doc_text">
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]754
755<pre>
756 <b>virtual bool</b> doFinalization(Function &amp;F);
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]757</pre>
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]758
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]759<p>The <tt>doFinalization</tt> method is an infrequently used method that is
760called when the pass framework has finished calling <a
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]761href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a> for every BasicBlock in the
762program being compiled. This can be used to perform per-function
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]763finalization.</p>
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]764
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]765</div>
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]766
Brian Gaekecab8b6f2003-07-17 18:53:20 +0000[diff] [blame]767<!-- ======================================================================= -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]768<div class="doc_subsection">
769 <a name="MachineFunctionPass">The <tt>MachineFunctionPass</tt> class</a>
770</div>
Brian Gaekecab8b6f2003-07-17 18:53:20 +0000[diff] [blame]771
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]772<div class="doc_text">
773
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]774<p>A <tt>MachineFunctionPass</tt> is a part of the LLVM code generator that
775executes on the machine-dependent representation of each LLVM function in the
776program. A <tt>MachineFunctionPass</tt> is also a <tt>FunctionPass</tt>, so all
Brian Gaekecab8b6f2003-07-17 18:53:20 +0000[diff] [blame]777the restrictions that apply to a <tt>FunctionPass</tt> also apply to it.
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]778<tt>MachineFunctionPass</tt>es also have additional restrictions. In particular,
779<tt>MachineFunctionPass</tt>es are not allowed to do any of the following:</p>
Brian Gaekecab8b6f2003-07-17 18:53:20 +0000[diff] [blame]780
781<ol>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]782<li>Modify any LLVM Instructions, BasicBlocks or Functions.</li>
783<li>Modify a MachineFunction other than the one currently being processed.</li>
784<li>Add or remove MachineFunctions from the current Module.</li>
785<li>Add or remove global variables from the current Module.</li>
786<li>Maintain state across invocations of <a
787href="#runOnMachineFunction"><tt>runOnMachineFunction</tt></a> (including global
788data)</li>
789</ol>
Brian Gaekecab8b6f2003-07-17 18:53:20 +0000[diff] [blame]790
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]791</div>
Chris Lattnerd0713f92002-09-12 17:06:43 +0000[diff] [blame]792
Brian Gaeke6a33f362003-07-22 20:53:20 +0000[diff] [blame]793<!-- _______________________________________________________________________ -->
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]794<div class="doc_subsubsection">
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]795 <a name="runOnMachineFunction">The <tt>runOnMachineFunction(MachineFunction
796 &amp;MF)</tt> method</a>
797</div>
798
799<div class="doc_text">
Brian Gaeke6a33f362003-07-22 20:53:20 +0000[diff] [blame]800
801<pre>
802 <b>virtual bool</b> runOnMachineFunction(MachineFunction &amp;MF) = 0;
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]803</pre>
Brian Gaeke6a33f362003-07-22 20:53:20 +0000[diff] [blame]804
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]805<p><tt>runOnMachineFunction</tt> can be considered the main entry point of a
806<tt>MachineFunctionPass</tt>; that is, you should override this method to do the
807work of your <tt>MachineFunctionPass</tt>.</p>
Brian Gaeke6a33f362003-07-22 20:53:20 +0000[diff] [blame]808
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]809<p>The <tt>runOnMachineFunction</tt> method is called on every
Brian Gaeke6a33f362003-07-22 20:53:20 +0000[diff] [blame]810<tt>MachineFunction</tt> in a <tt>Module</tt>, so that the
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]811<tt>MachineFunctionPass</tt> may perform optimizations on the machine-dependent
812representation of the function. If you want to get at the LLVM <tt>Function</tt>
813for the <tt>MachineFunction</tt> you're working on, use
814<tt>MachineFunction</tt>'s <tt>getFunction()</tt> accessor method -- but
815remember, you may not modify the LLVM <tt>Function</tt> or its contents from a
816<tt>MachineFunctionPass</tt>.</p>
817
818</div>
Brian Gaeke6a33f362003-07-22 20:53:20 +0000[diff] [blame]819
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]820<!-- *********************************************************************** -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]821<div class="doc_section">
822 <a name="registration">Pass registration</a>
823</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]824<!-- *********************************************************************** -->
825
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]826<div class="doc_text">
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]827
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]828<p>In the <a href="#basiccode">Hello World</a> example pass we illustrated how
829pass registration works, and discussed some of the reasons that it is used and
830what it does. Here we discuss how and why passes are registered.</p>
831
832<p>Passes can be registered in several different ways. Depending on the general
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]833classification of the pass, you should use one of the following templates to
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]834register the pass:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]835
836<ul>
837<li><b><tt>RegisterOpt</tt></b> - This template should be used when you are
838registering a pass that logically should be available for use in the
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]839'<tt>opt</tt>' utility.</li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]840
841<li><b><tt>RegisterAnalysis</tt></b> - This template should be used when you are
842registering a pass that logically should be available for use in the
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]843'<tt>analyze</tt>' utility.</li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]844
845<li><b><tt>RegisterPass</tt></b> - This is the generic form of the
846<tt>Register*</tt> templates that should be used if you want your pass listed by
847multiple or no utilities. This template takes an extra third argument that
848specifies which tools it should be listed in. See the <a
849href="http://llvm.cs.uiuc.edu/doxygen/PassSupport_8h-source.html">PassSupport.h</a>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]850file for more information.</li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]851
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]852</ul>
853
854<p>Regardless of how you register your pass, you must specify at least two
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]855parameters. The first parameter is the name of the pass that is to be used on
856the command line to specify that the pass should be added to a program (for
857example <tt>opt</tt> or <tt>analyze</tt>). The second argument is the name of
858the pass, which is to be used for the <tt>--help</tt> output of programs, as
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]859well as for debug output generated by the <tt>--debug-pass</tt> option.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]860
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]861<p>If a pass is registered to be used by the <tt>analyze</tt> utility, you
862should implement the virtual <tt>print</tt> method:</p>
863
864</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]865
866<!-- _______________________________________________________________________ -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]867<div class="doc_subsubsection">
868 <a name="print">The <tt>print</tt> method</a>
869</div>
870
871<div class="doc_text">
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]872
873<pre>
874 <b>virtual void</b> print(std::ostream &amp;O, <b>const</b> Module *M) <b>const</b>;
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]875</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]876
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]877<p>The <tt>print</tt> method must be implemented by "analyses" in order to print
878a human readable version of the analysis results. This is useful for debugging
879an analysis itself, as well as for other people to figure out how an analysis
880works. The <tt>analyze</tt> tool uses this method to generate its output.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]881
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]882<p>The <tt>ostream</tt> parameter specifies the stream to write the results on,
883and the <tt>Module</tt> parameter gives a pointer to the top level module of the
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]884program that has been analyzed. Note however that this pointer may be null in
885certain circumstances (such as calling the <tt>Pass::dump()</tt> from a
886debugger), so it should only be used to enhance debug output, it should not be
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]887depended on.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]888
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]889</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]890
891<!-- *********************************************************************** -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]892<div class="doc_section">
893 <a name="interaction">Specifying interactions between passes</a>
894</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]895<!-- *********************************************************************** -->
896
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]897<div class="doc_text">
898
899<p>One of the main responsibilities of the <tt>PassManager</tt> is the make sure
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]900that passes interact with each other correctly. Because <tt>PassManager</tt>
901tries to <a href="#passmanager">optimize the execution of passes</a> it must
902know how the passes interact with each other and what dependencies exist between
903the various passes. To track this, each pass can declare the set of passes that
904are required to be executed before the current pass, and the passes which are
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]905invalidated by the current pass.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]906
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]907<p>Typically this functionality is used to require that analysis results are
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]908computed before your pass is run. Running arbitrary transformation passes can
909invalidate the computed analysis results, which is what the invalidation set
910specifies. If a pass does not implement the <tt><a
911href="#getAnalysisUsage">getAnalysisUsage</a></tt> method, it defaults to not
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]912having any prerequisite passes, and invalidating <b>all</b> other passes.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]913
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]914</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]915
916<!-- _______________________________________________________________________ -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]917<div class="doc_subsubsection">
918 <a name="getAnalysisUsage">The <tt>getAnalysisUsage</tt> method</a>
919</div>
920
921<div class="doc_text">
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]922
923<pre>
924 <b>virtual void</b> getAnalysisUsage(AnalysisUsage &amp;Info) <b>const</b>;
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]925</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]926
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]927<p>By implementing the <tt>getAnalysisUsage</tt> method, the required and
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]928invalidated sets may be specified for your transformation. The implementation
929should fill in the <tt><a
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]930href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AnalysisUsage.html">AnalysisUsage</a></tt>
931object with information about which passes are required and not invalidated. To
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]932do this, a pass may call any of the following methods on the AnalysisUsage
933object:</p>
934</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]935
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]936<!-- _______________________________________________________________________ -->
937<div class="doc_subsubsection">
938 <a name="AU::addRequired">The <tt>AnalysisUsage::addRequired&lt;&gt;</tt> and <tt>AnalysisUsage::addRequiredTransitive&lt;&gt;</tt> methods</a>
939</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]940
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]941<div class="doc_text">
942<p>
943If you pass requires a previous pass to be executed (an analysis for example),
944it can use one of these methods to arrange for it to be run before your pass.
945LLVM has many different types of analyses and passes that can be required,
946spaning the range from <tt>DominatorSet</tt> to <tt>BreakCriticalEdges</tt>.
947requiring <tt>BreakCriticalEdges</tt>, for example, guarantees that there will
948be no critical edges in the CFG when your pass has been run.
949</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]950
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]951<p>
952Some analyses chain to other analyses to do their job. For example, an <a
953href="AliasAnalysis.html">AliasAnalysis</a> implementation is required to <a
954href="AliasAnalysis.html#chaining">chain</a> to other alias analysis passes. In
955cases where analyses chain, the <tt>addRequiredTransitive</tt> method should be
956used instead of the <tt>addRequired</tt> method. This informs the PassManager
957that the transitively required pass should be alive as long as the requiring
958pass is.
959</p>
960</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]961
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]962<!-- _______________________________________________________________________ -->
963<div class="doc_subsubsection">
964 <a name="AU::addPreserved">The <tt>AnalysisUsage::addPreserved&lt;&gt;</tt> method</a>
965</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]966
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]967<div class="doc_text">
968<p>
969One of the jobs of the PassManager is to optimize how and when analyses are run.
970In particular, it attempts to avoid recomputing data unless it needs to. For
971this reason, passes are allowed to declare that they preserve (i.e., they don't
972invalidate) an existing analysis if it's available. For example, a simple
973constant folding pass would not modify the CFG, so it can't possible effect the
974results of dominator analysis. By default, all passes are assumed to invalidate
975all others.
976</p>
977
978<p>
979The <tt>AnalysisUsage</tt> class provides several methods which are useful in
980certain circumstances that are related to <tt>addPreserved</tt>. In particular,
981the <tt>setPreservesAll</tt> method can be called to indicate that the pass does
982not modify the LLVM program at all (which is true for analyses), and the
983<tt>setPreservesCFG</tt> method can be used by transformations that change
984instructions in the program but do not modify the CFG or terminator instructions
985(note that this property is implicitly set for <a
986href="#BasicBlockPass">BasicBlockPass</a>'s).
987</p>
988
989<p>
990<tt>addPreserved</tt> is particularly useful for transformations like
991<tt>BreakCriticalEdges</tt>. This pass knows how to update a small set of loop
992and dominator related analyses if they exist, so it can preserve them, despite
993the fact that it hacks on the CFG.
994</p>
995</div>
996
997<!-- _______________________________________________________________________ -->
998<div class="doc_subsubsection">
999 <a name="AU::examples">Example implementations of <tt>getAnalysisUsage</tt></a>
1000</div>
1001
1002<div class="doc_text">
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1003
1004<pre>
1005 <i>// This is an example implementation from an analysis, which does not modify
1006 // the program at all, yet has a prerequisite.</i>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1007 <b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1PostDominanceFrontier.html">PostDominanceFrontier</a>::getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1008 AU.setPreservesAll();
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1009 AU.addRequired&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1PostDominatorTree.html">PostDominatorTree</a>&gt;();
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1010 }
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1011</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1012
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1013<p>and:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1014
1015<pre>
1016 <i>// This example modifies the program, but does not modify the CFG</i>
1017 <b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/structLICM.html">LICM</a>::getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
Chris Lattner8291e042002-10-21 19:57:59 +0000[diff] [blame]1018 AU.setPreservesCFG();
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1019 AU.addRequired&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1LoopInfo.html">LoopInfo</a>&gt;();
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1020 }
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1021</pre>
1022
1023</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1024
1025<!-- _______________________________________________________________________ -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1026<div class="doc_subsubsection">
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]1027 <a name="getAnalysis">The <tt>getAnalysis&lt;&gt;</tt> and <tt>getAnalysisToUpdate&lt;&gt;</tt> methods</a>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1028</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1029
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1030<div class="doc_text">
1031
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]1032<p>The <tt>Pass::getAnalysis&lt;&gt;</tt> method is automatically inherited by
1033your class, providing you with access to the passes that you declared that you
1034required with the <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a>
1035method. It takes a single template argument that specifies which pass class you
1036want, and returns a reference to that pass. For example:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1037
1038<pre>
Chris Lattnera5776302004-03-17 21:33:32 +0000[diff] [blame]1039 bool LICM::runOnFunction(Function &amp;F) {
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]1040 LoopInfo &amp;LI = getAnalysis&lt;LoopInfo&gt;();
1041 ...
1042 }
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1043</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1044
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1045<p>This method call returns a reference to the pass desired. You may get a
1046runtime assertion failure if you attempt to get an analysis that you did not
1047declare as required in your <a
1048href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> implementation. This
1049method can be called by your <tt>run*</tt> method implementation, or by any
1050other local method invoked by your <tt>run*</tt> method.</p>
1051
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]1052<p>
1053If your pass is capable of updating analyses if they exist (e.g.,
1054<tt>BreakCriticalEdges</tt>, as described above), you can use the
1055<tt>getAnalysisToUpdate</tt> method, which returns a pointer to the analysis if
1056it is active. For example:</p>
1057
1058<pre>
1059 ...
1060 if (DominatorSet *DS = getAnalysisToUpdate&lt;DominatorSet&gt;()) {
1061 <i>// A DominatorSet is active. This code will update it.</i>
1062 }
1063 ...
1064</pre>
1065
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1066</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1067
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1068<!-- *********************************************************************** -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1069<div class="doc_section">
1070 <a name="analysisgroup">Implementing Analysis Groups</a>
1071</div>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1072<!-- *********************************************************************** -->
1073
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1074<div class="doc_text">
1075
1076<p>Now that we understand the basics of how passes are defined, how the are
1077used, and how they are required from other passes, it's time to get a little bit
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1078fancier. All of the pass relationships that we have seen so far are very
1079simple: one pass depends on one other specific pass to be run before it can run.
1080For many applications, this is great, for others, more flexibility is
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1081required.</p>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1082
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1083<p>In particular, some analyses are defined such that there is a single simple
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1084interface to the analysis results, but multiple ways of calculating them.
1085Consider alias analysis for example. The most trivial alias analysis returns
1086"may alias" for any alias query. The most sophisticated analysis a
1087flow-sensitive, context-sensitive interprocedural analysis that can take a
1088significant amount of time to execute (and obviously, there is a lot of room
1089between these two extremes for other implementations). To cleanly support
1090situations like this, the LLVM Pass Infrastructure supports the notion of
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1091Analysis Groups.</p>
1092
1093</div>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1094
1095<!-- _______________________________________________________________________ -->
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]1096<div class="doc_subsubsection">
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1097 <a name="agconcepts">Analysis Group Concepts</a>
1098</div>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1099
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1100<div class="doc_text">
1101
1102<p>An Analysis Group is a single simple interface that may be implemented by
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1103multiple different passes. Analysis Groups can be given human readable names
1104just like passes, but unlike passes, they need not derive from the <tt>Pass</tt>
1105class. An analysis group may have one or more implementations, one of which is
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1106the "default" implementation.</p>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1107
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1108<p>Analysis groups are used by client passes just like other passes are: the
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1109<tt>AnalysisUsage::addRequired()</tt> and <tt>Pass::getAnalysis()</tt> methods.
1110In order to resolve this requirement, the <a href="#passmanager">PassManager</a>
1111scans the available passes to see if any implementations of the analysis group
1112are available. If none is available, the default implementation is created for
1113the pass to use. All standard rules for <A href="#interaction">interaction
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1114between passes</a> still apply.</p>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1115
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1116<p>Although <a href="#registration">Pass Registration</a> is optional for normal
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1117passes, all analysis group implementations must be registered, and must use the
1118<A href="#registerag"><tt>RegisterAnalysisGroup</tt></a> template to join the
1119implementation pool. Also, a default implementation of the interface
1120<b>must</b> be registered with <A
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1121href="#registerag"><tt>RegisterAnalysisGroup</tt></a>.</p>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1122
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1123<p>As a concrete example of an Analysis Group in action, consider the <a
1124href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1125analysis group. The default implementation of the alias analysis interface (the
1126<tt><a
1127href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">basicaa</a></tt>
1128pass) just does a few simple checks that don't require significant analysis to
1129compute (such as: two different globals can never alias each other, etc).
1130Passes that use the <tt><a
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1131href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a></tt>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1132interface (for example the <tt><a
Misha Brukmand15516e2004-06-03 23:39:36 +0000[diff] [blame]1133href="http://llvm.cs.uiuc.edu/doxygen/structGCSE.html">gcse</a></tt> pass), do
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1134not care which implementation of alias analysis is actually provided, they just
1135use the designated interface.</p>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1136
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1137<p>From the user's perspective, commands work just like normal. Issuing the
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1138command '<tt>opt -gcse ...</tt>' will cause the <tt>basicaa</tt> class to be
1139instantiated and added to the pass sequence. Issuing the command '<tt>opt
1140-somefancyaa -gcse ...</tt>' will cause the <tt>gcse</tt> pass to use the
1141<tt>somefancyaa</tt> alias analysis (which doesn't actually exist, it's just a
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1142hypothetical example) instead.</p>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1143
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1144</div>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1145
1146<!-- _______________________________________________________________________ -->
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]1147<div class="doc_subsubsection">
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1148 <a name="registerag">Using <tt>RegisterAnalysisGroup</tt></a>
1149</div>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1150
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1151<div class="doc_text">
1152
1153<p>The <tt>RegisterAnalysisGroup</tt> template is used to register the analysis
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1154group itself as well as add pass implementations to the analysis group. First,
1155an analysis should be registered, with a human readable name provided for it.
1156Unlike registration of passes, there is no command line argument to be specified
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1157for the Analysis Group Interface itself, because it is "abstract":</p>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1158
1159<pre>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1160 <b>static</b> RegisterAnalysisGroup&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>&gt; A("<i>Alias Analysis</i>");
1161</pre>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1162
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1163<p>Once the analysis is registered, passes can declare that they are valid
1164implementations of the interface by using the following code:</p>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1165
1166<pre>
1167<b>namespace</b> {
1168 //<i> Analysis Group implementations <b>must</b> be registered normally...</i>
1169 RegisterOpt&lt;FancyAA&gt;
1170 B("<i>somefancyaa</i>", "<i>A more complex alias analysis implementation</i>");
1171
1172 //<i> Declare that we implement the AliasAnalysis interface</i>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1173 RegisterAnalysisGroup&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>, FancyAA&gt; C;
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1174}
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1175</pre>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1176
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1177<p>This just shows a class <tt>FancyAA</tt> that is registered normally, then
1178uses the <tt>RegisterAnalysisGroup</tt> template to "join" the <tt><a
1179href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a></tt>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1180analysis group. Every implementation of an analysis group should join using
1181this template. A single pass may join multiple different analysis groups with
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1182no problem.</p>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1183
1184<pre>
1185<b>namespace</b> {
1186 //<i> Analysis Group implementations <b>must</b> be registered normally...</i>
1187 RegisterOpt&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a>&gt;
1188 D("<i>basicaa</i>", "<i>Basic Alias Analysis (default AA impl)</i>");
1189
1190 //<i> Declare that we implement the AliasAnalysis interface</i>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1191 RegisterAnalysisGroup&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>, <a href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a>, <b>true</b>&gt; E;
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1192}
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1193</pre>
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1194
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1195<p>Here we show how the default implementation is specified (using the extra
Chris Lattner79910702002-08-22 19:21:04 +0000[diff] [blame]1196argument to the <tt>RegisterAnalysisGroup</tt> template). There must be exactly
1197one default implementation available at all times for an Analysis Group to be
1198used. Here we declare that the <tt><a
1199href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a></tt>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1200pass is the default implementation for the interface.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1201
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1202</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1203
1204<!-- *********************************************************************** -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1205<div class="doc_section">
1206 <a name="passmanager">What PassManager does</a>
1207</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1208<!-- *********************************************************************** -->
1209
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1210<div class="doc_text">
1211
1212<p>The <a
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1213href="http://llvm.cs.uiuc.edu/doxygen/PassManager_8h-source.html"><tt>PassManager</tt></a>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1214<a
1215href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1PassManager.html">class</a>
1216takes a list of passes, ensures their <a href="#interaction">prerequisites</a>
1217are set up correctly, and then schedules passes to run efficiently. All of the
1218LLVM tools that run passes use the <tt>PassManager</tt> for execution of these
1219passes.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1220
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1221<p>The <tt>PassManager</tt> does two main things to try to reduce the execution
1222time of a series of passes:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1223
1224<ol>
1225<li><b>Share analysis results</b> - The PassManager attempts to avoid
1226recomputing analysis results as much as possible. This means keeping track of
1227which analyses are available already, which analyses get invalidated, and which
1228analyses are needed to be run for a pass. An important part of work is that the
1229<tt>PassManager</tt> tracks the exact lifetime of all analysis results, allowing
1230it to <a href="#releaseMemory">free memory</a> allocated to holding analysis
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1231results as soon as they are no longer needed.</li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1232
1233<li><b>Pipeline the execution of passes on the program</b> - The
1234<tt>PassManager</tt> attempts to get better cache and memory usage behavior out
1235of a series of passes by pipelining the passes together. This means that, given
1236a series of consequtive <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s, it
1237will execute all of the <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s on
1238the first function, then all of the <a
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1239href="#FunctionPass"><tt>FunctionPass</tt></a>es on the second function,
1240etc... until the entire program has been run through the passes.
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1241
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1242<p>This improves the cache behavior of the compiler, because it is only touching
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1243the LLVM program representation for a single function at a time, instead of
1244traversing the entire program. It reduces the memory consumption of compiler,
1245because, for example, only one <a
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1246href="http://llvm.cs.uiuc.edu/doxygen/structllvm_1_1DominatorSet.html"><tt>DominatorSet</tt></a>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1247needs to be calculated at a time. This also makes it possible some <a
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1248href="#SMP">interesting enhancements</a> in the future.</p></li>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1249
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1250</ol>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1251
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1252<p>The effectiveness of the <tt>PassManager</tt> is influenced directly by how
1253much information it has about the behaviors of the passes it is scheduling. For
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1254example, the "preserved" set is intentionally conservative in the face of an
1255unimplemented <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method.
1256Not implementing when it should be implemented will have the effect of not
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1257allowing any analysis results to live across the execution of your pass.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1258
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1259<p>The <tt>PassManager</tt> class exposes a <tt>--debug-pass</tt> command line
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1260options that is useful for debugging pass execution, seeing how things work, and
1261diagnosing when you should be preserving more analyses than you currently are
1262(To get information about all of the variants of the <tt>--debug-pass</tt>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1263option, just type '<tt>opt --help-hidden</tt>').</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1264
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1265<p>By using the <tt>--debug-pass=Structure</tt> option, for example, we can see
1266how our <a href="#basiccode">Hello World</a> pass interacts with other passes.
1267Lets try it out with the <tt>gcse</tt> and <tt>licm</tt> passes:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1268
1269<pre>
1270$ opt -load ../../../lib/Debug/libhello.so -gcse -licm --debug-pass=Structure &lt; hello.bc &gt; /dev/null
1271Module Pass Manager
1272 Function Pass Manager
1273 Dominator Set Construction
1274 Immediate Dominators Construction
1275 Global Common Subexpression Elimination
1276-- Immediate Dominators Construction
1277-- Global Common Subexpression Elimination
1278 Natural Loop Construction
1279 Loop Invariant Code Motion
1280-- Natural Loop Construction
1281-- Loop Invariant Code Motion
1282 Module Verifier
1283-- Dominator Set Construction
1284-- Module Verifier
1285 Bytecode Writer
1286--Bytecode Writer
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1287</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1288
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1289<p>This output shows us when passes are constructed and when the analysis
1290results are known to be dead (prefixed with '<tt>--</tt>'). Here we see that
1291GCSE uses dominator and immediate dominator information to do its job. The LICM
1292pass uses natural loop information, which uses dominator sets, but not immediate
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1293dominators. Because immediate dominators are no longer useful after the GCSE
1294pass, it is immediately destroyed. The dominator sets are then reused to
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1295compute natural loop information, which is then used by the LICM pass.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1296
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1297<p>After the LICM pass, the module verifier runs (which is automatically added
1298by the '<tt>opt</tt>' tool), which uses the dominator set to check that the
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1299resultant LLVM code is well formed. After it finishes, the dominator set
1300information is destroyed, after being computed once, and shared by three
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1301passes.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1302
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1303<p>Lets see how this changes when we run the <a href="#basiccode">Hello
1304World</a> pass in between the two passes:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1305
1306<pre>
1307$ opt -load ../../../lib/Debug/libhello.so -gcse -hello -licm --debug-pass=Structure &lt; hello.bc &gt; /dev/null
1308Module Pass Manager
1309 Function Pass Manager
1310 Dominator Set Construction
1311 Immediate Dominators Construction
1312 Global Common Subexpression Elimination
1313<b>-- Dominator Set Construction</b>
1314-- Immediate Dominators Construction
1315-- Global Common Subexpression Elimination
1316<b> Hello World Pass
1317-- Hello World Pass
1318 Dominator Set Construction</b>
1319 Natural Loop Construction
1320 Loop Invariant Code Motion
1321-- Natural Loop Construction
1322-- Loop Invariant Code Motion
1323 Module Verifier
1324-- Dominator Set Construction
1325-- Module Verifier
1326 Bytecode Writer
1327--Bytecode Writer
1328Hello: __main
1329Hello: puts
1330Hello: main
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1331</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1332
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1333<p>Here we see that the <a href="#basiccode">Hello World</a> pass has killed the
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1334Dominator Set pass, even though it doesn't modify the code at all! To fix this,
1335we need to add the following <a
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1336href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method to our pass:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1337
1338<pre>
1339 <i>// We don't modify the program, so we preserve all analyses</i>
1340 <b>virtual void</b> getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
1341 AU.setPreservesAll();
1342 }
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1343</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1344
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1345<p>Now when we run our pass, we get this output:</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1346
1347<pre>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1348$ opt -load ../../../lib/Debug/libhello.so -gcse -hello -licm --debug-pass=Structure &lt; hello.bc &gt; /dev/null
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1349Pass Arguments: -gcse -hello -licm
1350Module Pass Manager
1351 Function Pass Manager
1352 Dominator Set Construction
1353 Immediate Dominators Construction
1354 Global Common Subexpression Elimination
1355-- Immediate Dominators Construction
1356-- Global Common Subexpression Elimination
1357 Hello World Pass
1358-- Hello World Pass
1359 Natural Loop Construction
1360 Loop Invariant Code Motion
1361-- Loop Invariant Code Motion
1362-- Natural Loop Construction
1363 Module Verifier
1364-- Dominator Set Construction
1365-- Module Verifier
1366 Bytecode Writer
1367--Bytecode Writer
1368Hello: __main
1369Hello: puts
1370Hello: main
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1371</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1372
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1373<p>Which shows that we don't accidentally invalidate dominator information
1374anymore, and therefore do not have to compute it twice.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1375
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1376</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1377
1378<!-- _______________________________________________________________________ -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1379<div class="doc_subsubsection">
1380 <a name="releaseMemory">The <tt>releaseMemory</tt> method</a>
1381</div>
1382
1383<div class="doc_text">
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1384
1385<pre>
1386 <b>virtual void</b> releaseMemory();
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1387</pre>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1388
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1389<p>The <tt>PassManager</tt> automatically determines when to compute analysis
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1390results, and how long to keep them around for. Because the lifetime of the pass
1391object itself is effectively the entire duration of the compilation process, we
1392need some way to free analysis results when they are no longer useful. The
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1393<tt>releaseMemory</tt> virtual method is the way to do this.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1394
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1395<p>If you are writing an analysis or any other pass that retains a significant
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1396amount of state (for use by another pass which "requires" your pass and uses the
1397<a href="#getAnalysis">getAnalysis</a> method) you should implement
1398<tt>releaseMEmory</tt> to, well, release the memory allocated to maintain this
1399internal state. This method is called after the <tt>run*</tt> method for the
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1400class, before the next call of <tt>run*</tt> in your pass.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1401
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1402</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1403
1404<!-- *********************************************************************** -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1405<div class="doc_section">
1406 <a name="debughints">Using GDB with dynamically loaded passes</a>
1407</div>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1408<!-- *********************************************************************** -->
1409
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1410<div class="doc_text">
1411
1412<p>Unfortunately, using GDB with dynamically loaded passes is not as easy as it
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1413should be. First of all, you can't set a breakpoint in a shared object that has
1414not been loaded yet, and second of all there are problems with inlined functions
1415in shared objects. Here are some suggestions to debugging your pass with
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1416GDB.</p>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1417
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1418<p>For sake of discussion, I'm going to assume that you are debugging a
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1419transformation invoked by <tt>opt</tt>, although nothing described here depends
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1420on that.</p>
1421
1422</div>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1423
1424<!-- _______________________________________________________________________ -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1425<div class="doc_subsubsection">
1426 <a name="breakpoint">Setting a breakpoint in your pass</a>
1427</div>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1428
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1429<div class="doc_text">
1430
1431<p>First thing you do is start <tt>gdb</tt> on the <tt>opt</tt> process:</p>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1432
1433<pre>
1434$ <b>gdb opt</b>
1435GNU gdb 5.0
1436Copyright 2000 Free Software Foundation, Inc.
1437GDB is free software, covered by the GNU General Public License, and you are
1438welcome to change it and/or distribute copies of it under certain conditions.
1439Type "show copying" to see the conditions.
1440There is absolutely no warranty for GDB. Type "show warranty" for details.
1441This GDB was configured as "sparc-sun-solaris2.6"...
1442(gdb)
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1443</pre>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1444
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1445<p>Note that <tt>opt</tt> has a lot of debugging information in it, so it takes
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1446time to load. Be patient. Since we cannot set a breakpoint in our pass yet
1447(the shared object isn't loaded until runtime), we must execute the process, and
1448have it stop before it invokes our pass, but after it has loaded the shared
1449object. The most foolproof way of doing this is to set a breakpoint in
1450<tt>PassManager::run</tt> and then run the process with the arguments you
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1451want:</p>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1452
1453<pre>
1454(gdb) <b>break PassManager::run</b>
1455Breakpoint 1 at 0x2413bc: file Pass.cpp, line 70.
Chris Lattnerfafe6302003-10-23 19:48:11 +0000[diff] [blame]1456(gdb) <b>run test.bc -load $(LLVMTOP)/llvm/lib/Debug/[libname].so -[passoption]</b>
1457Starting program: opt test.bc -load $(LLVMTOP)/llvm/lib/Debug/[libname].so -[passoption]
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1458Breakpoint 1, PassManager::run (this=0xffbef174, M=@0x70b298) at Pass.cpp:70
145970 bool PassManager::run(Module &amp;M) { return PM-&gt;run(M); }
1460(gdb)
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1461</pre>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1462
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1463<p>Once the <tt>opt</tt> stops in the <tt>PassManager::run</tt> method you are
1464now free to set breakpoints in your pass so that you can trace through execution
1465or do other standard debugging stuff.</p>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1466
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1467</div>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1468
1469<!-- _______________________________________________________________________ -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1470<div class="doc_subsubsection">
1471 <a name="debugmisc">Miscellaneous Problems</a>
1472</div>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1473
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1474<div class="doc_text">
1475
1476<p>Once you have the basics down, there are a couple of problems that GDB has,
1477some with solutions, some without.</p>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1478
1479<ul>
1480<li>Inline functions have bogus stack information. In general, GDB does a
1481pretty good job getting stack traces and stepping through inline functions.
1482When a pass is dynamically loaded however, it somehow completely loses this
1483capability. The only solution I know of is to de-inline a function (move it
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1484from the body of a class to a .cpp file).</li>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1485
1486<li>Restarting the program breaks breakpoints. After following the information
1487above, you have succeeded in getting some breakpoints planted in your pass. Nex
1488thing you know, you restart the program (i.e., you type '<tt>run</tt>' again),
1489and you start getting errors about breakpoints being unsettable. The only way I
1490have found to "fix" this problem is to <tt>delete</tt> the breakpoints that are
1491already set in your pass, run the program, and re-set the breakpoints once
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1492execution stops in <tt>PassManager::run</tt>.</li>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1493
1494</ul>
1495
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1496<p>Hopefully these tips will help with common case debugging situations. If
1497you'd like to contribute some tips of your own, just contact <a
1498href="mailto:sabre@nondot.org">Chris</a>.</p>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1499
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1500</div>
Chris Lattner480e2ef2002-09-06 02:02:58 +0000[diff] [blame]1501
1502<!-- *********************************************************************** -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1503<div class="doc_section">
1504 <a name="future">Future extensions planned</a>
1505</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1506<!-- *********************************************************************** -->
1507
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1508<div class="doc_text">
1509
1510<p>Although the LLVM Pass Infrastructure is very capable as it stands, and does
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1511some nifty stuff, there are things we'd like to add in the future. Here is
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1512where we are going:</p>
1513
1514</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1515
1516<!-- _______________________________________________________________________ -->
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]1517<div class="doc_subsubsection">
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1518 <a name="SMP">Multithreaded LLVM</a>
1519</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1520
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1521<div class="doc_text">
1522
1523<p>Multiple CPU machines are becoming more common and compilation can never be
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1524fast enough: obviously we should allow for a multithreaded compiler. Because of
1525the semantics defined for passes above (specifically they cannot maintain state
1526across invocations of their <tt>run*</tt> methods), a nice clean way to
1527implement a multithreaded compiler would be for the <tt>PassManager</tt> class
Misha Brukmanbc0e9982003-07-14 17:20:40 +0000[diff] [blame]1528to create multiple instances of each pass object, and allow the separate
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1529instances to be hacking on different parts of the program at the same time.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1530
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1531<p>This implementation would prevent each of the passes from having to implement
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1532multithreaded constructs, requiring only the LLVM core to have locking in a few
1533places (for global resources). Although this is a simple extension, we simply
1534haven't had time (or multiprocessor machines, thus a reason) to implement this.
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1535Despite that, we have kept the LLVM passes SMP ready, and you should too.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1536
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1537</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1538
1539<!-- _______________________________________________________________________ -->
Chris Lattner89256272004-03-17 21:09:55 +0000[diff] [blame]1540<div class="doc_subsubsection">
Misha Brukmanefc182e2004-03-08 23:06:46 +0000[diff] [blame]1541<a name="PassFunctionPass"><tt>Pass</tt>es requiring <tt>FunctionPass</tt>es</a>
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1542</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1543
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1544<div class="doc_text">
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1545
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1546<p>Currently it is illegal for a <a href="#Pass"><tt>Pass</tt></a> to require a
1547<a href="#FunctionPass"><tt>FunctionPass</tt></a>. This is because there is
1548only one instance of the <a href="#FunctionPass"><tt>FunctionPass</tt></a>
1549object ever created, thus nowhere to store information for all of the functions
1550in the program at the same time. Although this has come up a couple of times
1551before, this has always been worked around by factoring one big complicated pass
1552into a global and an interprocedural part, both of which are distinct. In the
1553future, it would be nice to have this though.</p>
1554
1555<p>Note that it is no problem for a <a
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1556href="#FunctionPass"><tt>FunctionPass</tt></a> to require the results of a <a
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1557href="#Pass"><tt>Pass</tt></a>, only the other way around.</p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1558
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1559</div>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1560
1561<!-- *********************************************************************** -->
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1562<hr>
1563<address>
1564 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1565 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1566 <a href="http://validator.w3.org/check/referer"><img
1567 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000[diff] [blame]1568
Misha Brukmanc5402402004-01-15 18:34:11 +0000[diff] [blame]1569 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1570 <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a><br>
1571 Last modified: $Date$
1572</address>
1573
1574</body>
1575</html>