blob: 353fe6e366fdc8814272dd8d81260cbc85df55d6 [file] [log] [blame]
Chris Lattnerc6bb8242002-08-08 20:11:18 +00001<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2<html><head><title>Writing an LLVM Pass</title></head>
3
Chris Lattnerc6bb8242002-08-08 20:11:18 +00004<body bgcolor=white>
5
6<table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
7<tr><td>&nbsp; <font size=+3 color="#EEEEFF" face="Georgia,Palatino,Times,Roman"><b>Writing an LLVM Pass</b></font></td>
8</tr></table>
9
10
11<ol>
12 <li><a href="#introduction">Introduction - What is a pass?</a>
13 <li><a href="#quickstart">Quick Start - Writing hello world</a>
14 <ul>
15 <li><a href="#makefile">Setting up the build environment</a>
16 <li><a href="#basiccode">Basic code required</a>
17 <li><a href="#running">Running a pass with <tt>opt</tt>
18 or <tt>analyze</tt></a>
19 </ul>
20 <li><a href="#passtype">Pass classes and requirements</a>
21 <ul>
22 <li><a href="#Pass">The <tt>Pass</tt> class</a>
23 <ul>
24 <li><a href="#run">The <tt>run</tt> method</a>
25 </ul>
26 <li><a href="#FunctionPass">The <tt>FunctionPass</tt> class</a>
27 <ul>
28 <li><a href="#doInitialization">The <tt>doInitialization</tt> method</a>
29 <li><a href="#runOnFunction">The <tt>runOnFunction</tt> method</a>
30 <li><a href="#doFinalization">The <tt>doFinalization</tt> method</a>
31 </ul>
32 <li><a href="#BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
33 <ul>
34 <li><a href="#runOnBasicBlock">The <tt>runOnBasicBlock</tt> method</a>
35 </ul>
36 </ul>
37 <li><a href="#registration">Pass Registration</a>
38 <ul>
39 <li><a href="#print">The <tt>print</tt> method</a>
40 </ul>
41 <li><a href="#interaction">Specifying interactions between passes</a>
42 <ul>
43 <li><a href="#getAnalysisUsage">The <tt>getAnalysisUsage</tt> method</a>
44 <li><a href="#getAnalysis">The <tt>getAnalysis</tt> method</a>
45 </ul>
Chris Lattner79910702002-08-22 19:21:04 +000046 <li><a href="#analysisgroup">Implementing Analysis Groups</a>
47 <ul>
48 <li><a href="#agconcepts">Analysis Group Concepts</a>
49 <li><a href="#registerag">Using <tt>RegisterAnalysisGroup</tt></a>
50 </ul>
Chris Lattnerc6bb8242002-08-08 20:11:18 +000051 <li><a href="#passmanager">What PassManager does</a>
52 <ul>
53 <li><a href="#releaseMemory">The <tt>releaseMemory</tt> method</a>
54 </ul>
Chris Lattner480e2ef2002-09-06 02:02:58 +000055 <li><a href="#debughints">Using GDB with dynamically loaded passes</a>
56 <ul>
57 <li><a href="#breakpoint">Setting a breakpoint in your pass
58 <li><a href="#debugmisc">Miscellaneous Problems
59 </ul>
Chris Lattnerc6bb8242002-08-08 20:11:18 +000060 <li><a href="#future">Future extensions planned</a>
61 <ul>
62 <li><a href="#SMP">Multithreaded LLVM</a>
63 <li><a href="#ModuleSource">A new <tt>ModuleSource</tt> interface</a>
64 <li><a href="#PassFunctionPass"><tt>Pass</tt>'s requiring <tt>FunctionPass</tt>'s</a>
65 </ul>
Chris Lattner38c633d2002-08-08 20:23:41 +000066
67 <p><b>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></b><p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +000068</ol><p>
69
70
71
72<!-- *********************************************************************** -->
73<table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
74<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
75<a name="introduction">Introduction - What is a pass?
76</b></font></td></tr></table><ul>
77<!-- *********************************************************************** -->
78
79The LLVM Pass Framework is an important part of the LLVM system, because LLVM
80passes are where the interesting parts of the compiler exist. Passes perform
81the transformations and optimizations that make up the compiler, they build
82the analysis results that are used by these transformations, and they are, above
83all, a structuring technique for compiler code.<p>
84
85All LLVM passes are subclasses of the <tt><a
86href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt> class, which
87implement functionality by overriding virtual methods inherited from
88<tt>Pass</tt>. Depending on how your pass works, you may be able to inherit
89from the <tt><a
90href="http://llvm.cs.uiuc.edu/doxygen/structFunctionPass.html">FunctionPass</a></tt>
91or <tt><a
92href="http://llvm.cs.uiuc.edu/doxygen/structBasicBlockPass.html">BasicBlockPass</a></tt>,
93which gives the system more information about what your pass does, and how it
94can be combined with other passes. One of the main features of the LLVM Pass
95Framework is that it schedules passes to run in an efficient way based on the
96constraints that your pass has.<p>
97
98We start by showing you how to construct a pass, everything from setting up the
99code, to compiling, loading, and executing it. After the basics are down, more
100advanced features are discussed.<p>
101
102
103<!-- *********************************************************************** -->
104</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
105<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
106<a name="quickstart">Quick Start - Writing hello world
107</b></font></td></tr></table><ul>
108<!-- *********************************************************************** -->
109
110Here we describe how to write the "hello world" of passes. The "Hello" pass is
111designed to simply print out the name of non-external functions that exist in
112the program being compiled. It does not modify the program at all, just
113inspects it. The source code and files for this pass are available in the LLVM
114source tree in the <tt>lib/Transforms/Hello</tt> directory.<p>
115
116
117<!-- ======================================================================= -->
118</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
119<tr><td>&nbsp;</td><td width="100%">&nbsp;
120<font color="#EEEEFF" face="Georgia,Palatino"><b>
121<a name="makefile">Setting up the build environment
122</b></font></td></tr></table><ul>
123
124First thing you need to do is create a new directory somewhere in the LLVM
125source base. For this example, we'll assume that you made
126"<tt>lib/Transforms/Hello</tt>". The first thing you must do is set up a build
127script (Makefile) that will compile the source code for the new pass. To do
Chris Lattner17a4c3e2002-08-14 20:06:13 +0000128this, copy this into "<tt>Makefile</tt>" (be very careful that there are no
129extra space characters at the end of the lines though... that seems to confuse
130<tt>gmake</tt>):<p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000131
132</ul><hr><ul><pre>
133# Makefile for hello pass
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000134
Chris Lattner17a4c3e2002-08-14 20:06:13 +0000135# Path to top level of LLVM heirarchy
Chris Lattner7ce83e52002-08-14 20:07:01 +0000136LEVEL = ../../..
Chris Lattner17a4c3e2002-08-14 20:06:13 +0000137
138# Name of the library to build
Chris Lattner7ce83e52002-08-14 20:07:01 +0000139LIBRARYNAME = hello
Chris Lattner17a4c3e2002-08-14 20:06:13 +0000140
141# Build a dynamically loadable shared object
142SHARED_LIBRARY = 1
143
144# Include the makefile implementation stuff
145include $(LEVEL)/Makefile.common
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000146</pre></ul><hr><ul><p>
147
148This makefile specifies that all of the <tt>.cpp</tt> files in the current
149directory are to be compiled and linked together into a
150<tt>lib/Debug/libhello.so</tt> shared object that can be dynamically loaded by
151the <tt>opt</tt> or <tt>analyze</tt> tools.<p>
152
153Now that we have the build scripts set up, we just need to write the code for
154the pass itself.<p>
155
156
157<!-- ======================================================================= -->
158</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
159<tr><td>&nbsp;</td><td width="100%">&nbsp;
160<font color="#EEEEFF" face="Georgia,Palatino"><b>
161<a name="basiccode">Basic code required
162</b></font></td></tr></table><ul>
163
164Now that we have a way to compile our new pass, we just have to write it. Start
165out with:<p>
166
167<pre>
168<b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
169<b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Function_8h-source.html">llvm/Function.h</a>"
170</pre>
171
172Which are needed because we are writing a <tt><a
173href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt>, and we are
174operating on <tt><a
175href="http://llvm.cs.uiuc.edu/doxygen/classFunction.html">Function</a></tt>'s.<p>
176
177Next we have:<p>
178
179<pre>
180<b>namespace</b> {
181</pre><p>
182
183... which starts out an anonymous namespace. Anonymous namespaces are to C++
184what the "<tt>static</tt>" keyword is to C (at global scope). It makes the
185things declared inside of the anonymous namespace only visible to the current
186file. If you're not familiar with them, consult a decent C++ book for more
187information.<p>
188
189Next, we declare our pass itself:<p>
190
191<pre>
192 <b>struct</b> Hello : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
193</pre><p>
194
195This declares a "<tt>Hello</tt>" class that is a subclass of <tt><a
196href="http://llvm.cs.uiuc.edu/doxygen/structFunctionPass.html">FunctionPass</a></tt>.
Chris Lattnerd6ea9262002-09-09 03:48:46 +0000197The different builtin pass subclasses are described in detail <a
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000198href="#passtype">later</a>, but for now, know that <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s
199operate a function at a time.<p>
200
201<pre>
202 <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &F) {
203 std::cerr &lt;&lt; "<i>Hello: </i>" &lt;&lt; F.getName() &lt;&lt; "\n";
204 <b>return false</b>;
205 }
206 }; <i>// end of struct Hello</i>
207</pre>
208
209We declare a "<a href="#runOnFunction"><tt>runOnFunction</tt></a>" method, which
210overloads an abstract virtual method inherited from <a
211href="#FunctionPass"><tt>FunctionPass</tt></a>. This is where we are supposed
212to do our thing, so we just print out our message with the name of each
213function.<p>
214
215<pre>
216 RegisterOpt&lt;Hello&gt; X("<i>hello</i>", "<i>Hello World Pass</i>");
217} <i>// end of anonymous namespace</i>
218</pre><p>
219
220Lastly, we register our class <tt>Hello</tt>, giving it a command line argument
221"<tt>hello</tt>", and a name "<tt>Hello World Pass</tt>". There are several
222different ways of <a href="#registration">registering your pass</a>, depending
223on what it is to be used for. For "optimizations" we use the
224<tt>RegisterOpt</tt> template.<p>
225
226As a whole, the <tt>.cpp</tt> file looks like:<p>
227
228<pre>
229<b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
230<b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Function_8h-source.html">llvm/Function.h</a>"
231
232<b>namespace</b> {
233 <b>struct Hello</b> : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
234 <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &F) {
235 std::cerr &lt;&lt; "<i>Hello: </i>" &lt;&lt; F.getName() &lt;&lt; "\n";
236 <b>return false</b>;
237 }
238 };
239
240 RegisterOpt&lt;Hello&gt; X("<i>hello</i>", "<i>Hello World Pass</i>");
241}
242</pre><p>
243
244Now that it's all together, compile the file with a simple "<tt>gmake</tt>"
245command in the local directory and you should get a new
246"<tt>lib/Debug/libhello.so</tt> file. Note that everything in this file is
247contained in an anonymous namespace: this reflects the fact that passes are self
248contained units that do not need external interfaces (although they can have
249them) to be useful.<p>
250
251
252<!-- ======================================================================= -->
253</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
254<tr><td>&nbsp;</td><td width="100%">&nbsp;
255<font color="#EEEEFF" face="Georgia,Palatino"><b>
256<a name="running">Running a pass with <tt>opt</tt> or <tt>analyze</tt>
257</b></font></td></tr></table><ul>
258
259Now that you have a brand new shiny <tt>.so</tt> file, we can use the
260<tt>opt</tt> command to run an LLVM program through your pass. Because you
261registered your pass with the <tt>RegisterOpt</tt> template, you will be able to
262use the <tt>opt</tt> tool to access it, once loaded.<p>
263
264To test it, follow the example at the end of the <a
265href="GettingStarted.html">Getting Started Guide</a> to compile "Hello World" to
266LLVM. We can now run the bytecode file (<tt>hello.bc</tt>) for the program
267through our transformation like this (or course, any bytecode file will
268work):<p>
269
270<pre>
271$ opt -load ../../../lib/Debug/libhello.so -hello &lt; hello.bc &gt; /dev/null
272Hello: __main
273Hello: puts
274Hello: main
275</pre><p>
276
277The '<tt>-load</tt>' option specifies that '<tt>opt</tt>' should load your pass
278as a shared object, which makes '<tt>-hello</tt>' a valid command line argument
279(which is one reason you need to <a href="#registration">register your
280pass</a>). Because the hello pass does not modify the program in any
281interesting way, we just throw away the result of <tt>opt</tt> (sending it to
282<tt>/dev/null</tt>).<p>
283
284To see what happened to the other string you registered, try running
285<tt>opt</tt> with the <tt>--help</tt> option:<p>
286
287<pre>
288$ opt -load ../../../lib/Debug/libhello.so --help
289OVERVIEW: llvm .bc -&gt; .bc modular optimizer
290
291USAGE: opt [options] &lt;input bytecode&gt;
292
293OPTIONS:
294 Optimizations available:
295...
296 -funcresolve - Resolve Functions
297 -gcse - Global Common Subexpression Elimination
298 -globaldce - Dead Global Elimination
299 <b>-hello - Hello World Pass</b>
300 -indvars - Cannonicalize Induction Variables
301 -inline - Function Integration/Inlining
302 -instcombine - Combine redundant instructions
303...
304</pre><p>
305
306The pass name get added as the information string for your pass, giving some
307documentation to users of <tt>opt</tt>. Now that you have a working pass, you
308would go ahead and make it do the cool transformations you want. Once you get
309it all working and tested, it may become useful to find out how fast your pass
310is. The <a href="#passManager"><tt>PassManager</tt></a> provides a nice command
311line option (<tt>--time-passes</tt>) that allows you to get information about
312the execution time of your pass along with the other passes you queue up. For
313example:<p>
314
315<pre>
316$ opt -load ../../../lib/Debug/libhello.so -hello -time-passes &lt; hello.bc &gt; /dev/null
317Hello: __main
318Hello: puts
319Hello: main
320===============================================================================
321 ... Pass execution timing report ...
322===============================================================================
323 Total Execution Time: 0.02 seconds (0.0479059 wall clock)
324
325 ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Pass Name ---
326 0.0100 (100.0%) 0.0000 ( 0.0%) 0.0100 ( 50.0%) 0.0402 ( 84.0%) Bytecode Writer
327 0.0000 ( 0.0%) 0.0100 (100.0%) 0.0100 ( 50.0%) 0.0031 ( 6.4%) Dominator Set Construction
328 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0013 ( 2.7%) Module Verifier
329 <b> 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0033 ( 6.9%) Hello World Pass</b>
330 0.0100 (100.0%) 0.0100 (100.0%) 0.0200 (100.0%) 0.0479 (100.0%) TOTAL
331</pre><p>
332
333As you can see, our implementation above is pretty fast :). The additional
334passes listed are automatically inserted by the '<tt>opt</tt>' tool to verify
335that the LLVM emitted by your pass is still valid and well formed LLVM, which
336hasn't been broken somehow.
337
338Now that you have seen the basics of the mechanics behind passes, we can talk
339about some more details of how they work and how to use them.<p>
340
341
342
343<!-- *********************************************************************** -->
344</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
345<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
346<a name="passtype">Pass classes and requirements
347</b></font></td></tr></table><ul>
348<!-- *********************************************************************** -->
349
350One of the first things that you should do when designing a new pass is to
351decide what class you should subclass for your pass. The <a
352href="#basiccode">Hello World</a> example uses the <tt><a
353href="#FunctionPass">FunctionPass</a></tt> class for its implementation, but we
354did not discuss why or when this should occur. Here we talk about the classes
355available, from the most general to the most specific.<p>
356
Chris Lattner79910702002-08-22 19:21:04 +0000357When choosing a superclass for your Pass, you should choose the <b>most
358specific</b> class possible, while still being able to meet the requirements
359listed. This gives the LLVM Pass Infrastructure information neccesary to
360optimize how passes are run, so that the resultant compiler isn't unneccesarily
361slow.<p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000362
363
364
365<!-- ======================================================================= -->
366</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
367<tr><td>&nbsp;</td><td width="100%">&nbsp;
368<font color="#EEEEFF" face="Georgia,Palatino"><b>
369<a name="Pass">The <tt>Pass</tt> class
370</b></font></td></tr></table><ul>
371
372The "<tt><a href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt>"
373class is the most general of all superclasses that you can use. Deriving from
374<tt>Pass</tt> indicates that your pass uses the entire program as a unit,
375refering to function bodies in no predictable order, or adding and removing
376functions. Because nothing is known about the behavior of direct <tt>Pass</tt>
377subclasses, no optimization can be done for their execution.<p>
378
379To write a correct <tt>Pass</tt> subclass, derive from <tt>Pass</tt> and
380overload the <tt>run</tt> method with the following signature:<p>
381
382<!-- _______________________________________________________________________ -->
383</ul><h4><a name="run"><hr size=0>The <tt>run</tt> method</h4><ul>
384
385
386<pre>
387 <b>virtual bool</b> run(Module &amp;M) = 0;
388</pre><p>
389
390The <tt>run</tt> method performs the interesting work of the pass, and should
391return true if the module was modified by the transformation, false
392otherwise.<p>
393
394
395
396<!-- ======================================================================= -->
397</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
398<tr><td>&nbsp;</td><td width="100%">&nbsp;
399<font color="#EEEEFF" face="Georgia,Palatino"><b>
400<a name="FunctionPass">The <tt>FunctionPass</tt> class
401</b></font></td></tr></table><ul>
402
403In contrast to direct <tt>Pass</tt> subclasses, direct <tt><a
404href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">FunctionPass</a></tt>
405subclasses do have a predictable, local behavior that can be expected by the
406system. All <tt>FunctionPass</tt> execute on each function in the program
407independant of all of the other functions in the program.
408<tt>FunctionPass</tt>'s do not require that they are executed in a particular
409order, and <tt>FunctionPass</tt>'s do not modify external functions.<p>
410
411To be explicit, <tt>FunctionPass</tt> subclasses are not allowed to:<p>
412
413<ol>
414<li>Modify a Function other than the one currently being processed.
415<li>Add or remove Function's from the current Module.
416<li>Add or remove global variables from the current Module.
417<li>Maintain state across invocations of
418 <a href="#runOnFunction"><tt>runOnFunction</tt></a> (including global data)
419</ol><p>
420
421Implementing a <tt>FunctionPass</tt> is usually straightforward (See the <a
422href="#basiccode">Hello World</a> pass for example). <tt>FunctionPass</tt>'s
423may overload three virtual methods to do their work. All of these methods
424should return true if they modified the program, or false if they didn't.<p>
425
426<!-- _______________________________________________________________________ -->
427</ul><h4><a name="doInitialization"><hr size=0>The <tt>doInitialization</tt>
428method</h4><ul>
429
430<pre>
431 <b>virtual bool</b> doInitialization(Module &amp;M);
432</pre><p>
433
434The <tt>doIninitialize</tt> method is allowed to do most of the things that
435<tt>FunctionPass</tt>'s are not allowed to do. They can add and remove
436functions, get pointers to functions, etc. The <tt>doInitialize</tt> method is
437designed to do simple initialization type of stuff that does not depend on the
438functions being processed. The <tt>doInitialization</tt> function call is not
439scheduled to overlap with any other pass executions.<p>
440
441A good example of how this method should be used is the <a
442href="http://llvm.cs.uiuc.edu/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations</a>
443pass. This pass converts <tt>malloc</tt> and <tt>free</tt> instructions into
444platform dependant <tt>malloc()</tt> and <tt>free()</tt> function calls. It
445uses the <tt>doInitialization</tt> method to get a reference to the malloc and
446free functions that it needs, adding prototypes to the module if neccesary.<p>
447
448<!-- _______________________________________________________________________ -->
449</ul><h4><a name="runOnFunction"><hr size=0>The <tt>runOnFunction</tt> method</h4><ul>
450
451<pre>
452 <b>virtual bool</b> runOnFunction(Function &amp;F) = 0;
453</pre><p>
454
455The <tt>runOnFunction</tt> method must be implemented by your subclass to do the
456transformation or analysis work of your pass. As usual, a true value should be
457returned if the function is modified.<p>
458
459<!-- _______________________________________________________________________ -->
460</ul><h4><a name="doFinalization"><hr size=0>The <tt>doFinalization</tt> method</h4><ul>
461
462<pre>
463 <b>virtual bool</b> doFinalization(Module &amp;M);
464</pre</p>
465
466The <tt>doFinalization</tt> method is an infrequently used method that is called
467when the pass framework has finished calling <a
468href="#runOnFunction"><tt>runOnFunction</tt></a> for every function in the
469program being compiled.<p>
470
471
472
473<!-- ======================================================================= -->
474</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
475<tr><td>&nbsp;</td><td width="100%">&nbsp;
476<font color="#EEEEFF" face="Georgia,Palatino"><b>
477<a name="BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
478</b></font></td></tr></table><ul>
479
480<tt>BasicBlockPass</tt>'s are just like <a
481href="#FunctionPass"><tt>FunctionPass</tt></a>'s, except that they must limit
482their scope of inspection and modification to a single basic block at a time.
483As such, they are <b>not</b> allowed to do any of the following:<p>
484
485<ol>
486<li>Modify or inspect any basic blocks outside of the current one
487<li>Maintain state across invocations of
488 <a href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a>
489<li>Modify the constrol flow graph (by altering terminator instructions)
490<li>Any of the things verboten for
491 <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s.
492</ol><p>
493
494<tt>BasicBlockPass</tt>'s are useful for traditional local and "peephole"
495optimizations. They may override the same <a
496href="#doInitialization"><tt>doInitialization</tt></a> and <a
497href="#doFinalization"><tt>doFinalization</tt></a> methods that <a
498href="#FunctionPass"><tt>FunctionPass</tt></a>'s have, but also have a
499<tt>runOnBasicBlock</tt> method:<p>
500
501<!-- _______________________________________________________________________ -->
502</ul><h4><a name="runOnBasicBlock"><hr size=0>The <tt>runOnBasicBlock</tt> method</h4><ul>
503
504<pre>
505 <b>virtual bool</b> runOnBasicBlock(BasicBlock &amp;BB) = 0;
506</pre><p>
507
508Override this function to do the work of the <tt>BasicBlockPass</tt>. This
509function is not allowed to inspect or modify basic blocks other than the
510parameter, and are not allowed to modify the CFG. A true value must be returned
511if the basic block is modified.<p>
512
513
514<!-- *********************************************************************** -->
515</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
516<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
517<a name="registration">Pass registration
518</b></font></td></tr></table><ul>
519<!-- *********************************************************************** -->
520
521In the <a href="#basiccode">Hello World</a> example pass we illustrated how pass
522registration works, and discussed some of the reasons that it is used and what
523it does. Here we discuss how and why passes are registered.<p>
524
525Passes can be registered in several different ways. Depending on the general
526classification of the pass, you should use one of the following templates to
527register the pass:<p>
528
529<ul>
530<li><b><tt>RegisterOpt</tt></b> - This template should be used when you are
531registering a pass that logically should be available for use in the
532'<tt>opt</tt>' utility.<p>
533
534<li><b><tt>RegisterAnalysis</tt></b> - This template should be used when you are
535registering a pass that logically should be available for use in the
536'<tt>analysis</tt>' utility.<p>
537
538<li><b><tt>RegisterLLC</tt></b> - This template should be used when you are
539registering a pass that logically should be available for use in the
540'<tt>llc</tt>' utility.<p>
541
542<li><b><tt>RegisterPass</tt></b> - This is the generic form of the
543<tt>Register*</tt> templates that should be used if you want your pass listed by
544multiple or no utilities. This template takes an extra third argument that
545specifies which tools it should be listed in. See the <a
546href="http://llvm.cs.uiuc.edu/doxygen/PassSupport_8h-source.html">PassSupport.h</a>
547file for more information.<p>
548</ul><p>
549
550Regardless of how you register your pass, you must specify at least two
551parameters. The first parameter is the name of the pass that is to be used on
552the command line to specify that the pass should be added to a program (for
553example <tt>opt</tt> or <tt>analyze</tt>). The second argument is the name of
554the pass, which is to be used for the <tt>--help</tt> output of programs, as
555well as for debug output generated by the <tt>--debug-pass</tt> option.<p>
556
557If you pass is constructed by its default constructor, you only ever have to
558pass these two arguments. If, on the other hand, you require other information
559(like target specific information), you must pass an additional argument. This
560argument is a pointer to a function used to create the pass. For an example of
561how this works, look at the <a
562href="http://llvm.cs.uiuc.edu/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations.cpp</a>
563file.<p>
564
565If a pass is registered to be used by the <tt>analyze</tt> utility, you should
566implement the virtual <tt>print</tt> method:<p>
567
568<!-- _______________________________________________________________________ -->
569</ul><h4><a name="print"><hr size=0>The <tt>print</tt> method</h4><ul>
570
571<pre>
572 <b>virtual void</b> print(std::ostream &amp;O, <b>const</b> Module *M) <b>const</b>;
573</pre><p>
574
575The <tt>print</tt> method must be implemented by "analyses" in order to print a
576human readable version of the analysis results. This is useful for debugging an
577analysis itself, as well as for other people to figure out how an analysis
578works. The <tt>analyze</tt> tool uses this method to generate its output.<p>
579
580The <tt>ostream</tt> parameter specifies the stream to write the results on, and
581the <tt>Module</tt> parameter gives a pointer to the top level module of the
582program that has been analyzed. Note however that this pointer may be null in
583certain circumstances (such as calling the <tt>Pass::dump()</tt> from a
584debugger), so it should only be used to enhance debug output, it should not be
585depended on.<p>
586
587
588<!-- *********************************************************************** -->
589</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
590<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
591<a name="interaction">Specifying interactions between passes
592</b></font></td></tr></table><ul>
593<!-- *********************************************************************** -->
594
595One of the main responsibilities of the <tt>PassManager</tt> is the make sure
596that passes interact with each other correctly. Because <tt>PassManager</tt>
597tries to <a href="#passmanager">optimize the execution of passes</a> it must
598know how the passes interact with each other and what dependencies exist between
599the various passes. To track this, each pass can declare the set of passes that
600are required to be executed before the current pass, and the passes which are
601invalidated by the current pass.<p>
602
603Typically this functionality is used to require that analysis results are
604computed before your pass is run. Running arbitrary transformation passes can
605invalidate the computed analysis results, which is what the invalidation set
606specifies. If a pass does not implement the <tt><a
607href="#getAnalysisUsage">getAnalysisUsage</a></tt> method, it defaults to not
608having any prerequisite passes, and invalidating <b>all</b> other passes.<p>
609
610
611<!-- _______________________________________________________________________ -->
612</ul><h4><a name="getAnalysisUsage"><hr size=0>The <tt>getAnalysisUsage</tt> method</h4><ul>
613
614<pre>
615 <b>virtual void</b> getAnalysisUsage(AnalysisUsage &amp;Info) <b>const</b>;
616</pre><p>
617
618By implementing the <tt>getAnalysisUsage</tt> method, the required and
619invalidated sets may be specified for your transformation. The implementation
620should fill in the <tt><a
621href="http://llvm.cs.uiuc.edu/doxygen/classAnalysisUsage.html">AnalysisUsage</a></tt>
622object with information about which passes are required and not invalidated. To do this, the following set methods are provided by the <tt><a
623href="http://llvm.cs.uiuc.edu/doxygen/classAnalysisUsage.html">AnalysisUsage</a></tt> class:<p>
624
625<pre>
626 <i>// addRequires - Add the specified pass to the required set for your pass.</i>
627 <b>template</b>&lt;<b>class</b> PassClass&gt;
628 AnalysisUsage &amp;AnalysisUsage::addRequired();
629
630 <i>// addPreserved - Add the specified pass to the set of analyses preserved by
631 // this pass</i>
632 <b>template</b>&lt;<b>class</b> PassClass&gt;
633 AnalysisUsage &amp;AnalysisUsage::addPreserved();
634
635 <i>// setPreservesAll - Call this if the pass does not modify its input at all</i>
636 <b>void</b> AnalysisUsage::setPreservesAll();
637
638 <i>// preservesCFG - This function should be called by the pass, iff they do not:
639 //
640 // 1. Add or remove basic blocks from the function
641 // 2. Modify terminator instructions in any way.
642 //
643 // This is automatically implied for <a href="#BasicBlockPass">BasicBlockPass</a>'s
644 //</i>
645 <b>void</b> AnalysisUsage::preservesCFG();
646</pre><p>
647
648Some examples of how to use these methods are:<p>
649
650<pre>
651 <i>// This is an example implementation from an analysis, which does not modify
652 // the program at all, yet has a prerequisite.</i>
653 <b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/structPostDominanceFrontier.html">PostDominanceFrontier</a>::getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
654 AU.setPreservesAll();
655 AU.addRequired&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structPostDominatorTree.html">PostDominatorTree</a>&gt;();
656 }
657</pre><p>
658
659and:<p>
660
661<pre>
662 <i>// This example modifies the program, but does not modify the CFG</i>
663 <b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/structLICM.html">LICM</a>::getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
664 AU.preservesCFG();
665 AU.addRequired&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/classLoopInfo.html">LoopInfo</a>&gt;();
666 }
667</pre><p>
668
669<!-- _______________________________________________________________________ -->
670</ul><h4><a name="getAnalysis"><hr size=0>The <tt>getAnalysis&lt;&gt;</tt> method</h4><ul>
671
672The <tt>Pass::getAnalysis&lt;&gt;</tt> method is inherited by your class,
673providing you with access to the passes that you declared that you required with
674the <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method. It takes
675a single template argument that specifies which pass class you want, and returns
676a reference to that pass.<p>
677
678<pre>
679 <b>template</b>&lt;<b>typename</b> PassClass&gt;
680 AnalysisType &amp;getAnalysis();
681</pre><p>
682
683This method call returns a reference to the pass desired. You may get a runtime
684assertion failure if you attempt to get an analysis that you did not declare as
685required in your <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a>
686implementation. This method can be called by your <tt>run*</tt> method
687implementation, or by any other local method invoked by your <tt>run*</tt>
688method.<p>
689
Chris Lattner79910702002-08-22 19:21:04 +0000690<!-- *********************************************************************** -->
691</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
692<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
693<a name="analysisgroup">Implementing Analysis Groups
694</b></font></td></tr></table><ul>
695<!-- *********************************************************************** -->
696
697Now that we understand the basics of how passes are defined, how the are used,
698and how they are required from other passes, it's time to get a little bit
699fancier. All of the pass relationships that we have seen so far are very
700simple: one pass depends on one other specific pass to be run before it can run.
701For many applications, this is great, for others, more flexibility is
702required.<p>
703
704In particular, some analyses are defined such that there is a single simple
705interface to the analysis results, but multiple ways of calculating them.
706Consider alias analysis for example. The most trivial alias analysis returns
707"may alias" for any alias query. The most sophisticated analysis a
708flow-sensitive, context-sensitive interprocedural analysis that can take a
709significant amount of time to execute (and obviously, there is a lot of room
710between these two extremes for other implementations). To cleanly support
711situations like this, the LLVM Pass Infrastructure supports the notion of
712Analysis Groups.<p>
713
714<!-- _______________________________________________________________________ -->
715</ul><h4><a name="agconcepts"><hr size=0>Analysis Group Concepts</h4><ul>
716
717An Analysis Group is a single simple interface that may be implemented by
718multiple different passes. Analysis Groups can be given human readable names
719just like passes, but unlike passes, they need not derive from the <tt>Pass</tt>
720class. An analysis group may have one or more implementations, one of which is
721the "default" implementation.<p>
722
723Analysis groups are used by client passes just like other passes are: the
724<tt>AnalysisUsage::addRequired()</tt> and <tt>Pass::getAnalysis()</tt> methods.
725In order to resolve this requirement, the <a href="#passmanager">PassManager</a>
726scans the available passes to see if any implementations of the analysis group
727are available. If none is available, the default implementation is created for
728the pass to use. All standard rules for <A href="#interaction">interaction
729between passes</a> still apply.<p>
730
731Although <a href="#registration">Pass Registration</a> is optional for normal
732passes, all analysis group implementations must be registered, and must use the
733<A href="#registerag"><tt>RegisterAnalysisGroup</tt></a> template to join the
734implementation pool. Also, a default implementation of the interface
735<b>must</b> be registered with <A
736href="#registerag"><tt>RegisterAnalysisGroup</tt></a>.<p>
737
738As a concrete example of an Analysis Group in action, consider the <a
739href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a>
740analysis group. The default implementation of the alias analysis interface (the
741<tt><a
742href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">basicaa</a></tt>
743pass) just does a few simple checks that don't require significant analysis to
744compute (such as: two different globals can never alias each other, etc).
745Passes that use the <tt><a
746href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a></tt>
747interface (for example the <tt><a
748href="http://llvm.cs.uiuc.edu/doxygen/classGCSE.html">gcse</a></tt> pass), do not care which implementation
749of alias analysis is actually provided, they just use the designated
750interface.<p>
751
752From the user's perspective, commands work just like normal. Issuing the
753command '<tt>opt -gcse ...</tt>' will cause the <tt>basicaa</tt> class to be
754instantiated and added to the pass sequence. Issuing the command '<tt>opt
755-somefancyaa -gcse ...</tt>' will cause the <tt>gcse</tt> pass to use the
756<tt>somefancyaa</tt> alias analysis (which doesn't actually exist, it's just a
757hypothetical example) instead.<p>
758
759
760<!-- _______________________________________________________________________ -->
761</ul><h4><a name="registerag"><hr size=0>Using <tt>RegisterAnalysisGroup</tt></h4><ul>
762
763The <tt>RegisterAnalysisGroup</tt> template is used to register the analysis
764group itself as well as add pass implementations to the analysis group. First,
765an analysis should be registered, with a human readable name provided for it.
766Unlike registration of passes, there is no command line argument to be specified
767for the Analysis Group Interface itself, because it is "abstract":<p>
768
769<pre>
770 <b>static</b> RegisterAnalysisGroup&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a>&gt; A("<i>Alias Analysis</i>");
771</pre><p>
772
773Once the analysis is registered, passes can declare that they are valid
774implementations of the interface by using the following code:<p>
775
776<pre>
777<b>namespace</b> {
778 //<i> Analysis Group implementations <b>must</b> be registered normally...</i>
779 RegisterOpt&lt;FancyAA&gt;
780 B("<i>somefancyaa</i>", "<i>A more complex alias analysis implementation</i>");
781
782 //<i> Declare that we implement the AliasAnalysis interface</i>
783 RegisterAnalysisGroup&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a>, FancyAA&gt; C;
784}
785</pre><p>
786
787This just shows a class <tt>FancyAA</tt> that is registered normally, then uses
788the <tt>RegisterAnalysisGroup</tt> template to "join" the <tt><a
789href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a></tt>
790analysis group. Every implementation of an analysis group should join using
791this template. A single pass may join multiple different analysis groups with
792no problem.<p>
793
794<pre>
795<b>namespace</b> {
796 //<i> Analysis Group implementations <b>must</b> be registered normally...</i>
797 RegisterOpt&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a>&gt;
798 D("<i>basicaa</i>", "<i>Basic Alias Analysis (default AA impl)</i>");
799
800 //<i> Declare that we implement the AliasAnalysis interface</i>
801 RegisterAnalysisGroup&lt;<a href="http://llvm.cs.uiuc.edu/doxygen/structAliasAnalysis.html">AliasAnalysis</a>, <a href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a>, <b>true</b>&gt; E;
802}
803</pre><p>
804
805Here we show how the default implementation is specified (using the extra
806argument to the <tt>RegisterAnalysisGroup</tt> template). There must be exactly
807one default implementation available at all times for an Analysis Group to be
808used. Here we declare that the <tt><a
809href="http://llvm.cs.uiuc.edu/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a></tt>
810pass is the default implementation for the interface.<p>
Chris Lattnerc6bb8242002-08-08 20:11:18 +0000811
812
813<!-- *********************************************************************** -->
814</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
815<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
816<a name="passmanager">What PassManager does
817</b></font></td></tr></table><ul>
818<!-- *********************************************************************** -->
819
820The <a
821href="http://llvm.cs.uiuc.edu/doxygen/PassManager_8h-source.html"><tt>PassManager</tt></a>
822<a href="http://llvm.cs.uiuc.edu/doxygen/classPassManager.html">class</a> takes
823a list of passes, ensures their <a href="#interaction">prerequisites</a> are set
824up correctly, and then schedules passes to run efficiently. All of the LLVM
825tools that run passes use the <tt>PassManager</tt> for execution of these
826passes.<p>
827
828The <tt>PassManager</tt> does two main things to try to reduce the execution
829time of a series of passes:<p>
830
831<ol>
832<li><b>Share analysis results</b> - The PassManager attempts to avoid
833recomputing analysis results as much as possible. This means keeping track of
834which analyses are available already, which analyses get invalidated, and which
835analyses are needed to be run for a pass. An important part of work is that the
836<tt>PassManager</tt> tracks the exact lifetime of all analysis results, allowing
837it to <a href="#releaseMemory">free memory</a> allocated to holding analysis
838results as soon as they are no longer needed.<p>
839
840<li><b>Pipeline the execution of passes on the program</b> - The
841<tt>PassManager</tt> attempts to get better cache and memory usage behavior out
842of a series of passes by pipelining the passes together. This means that, given
843a series of consequtive <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s, it
844will execute all of the <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s on
845the first function, then all of the <a
846href="#FunctionPass"><tt>FunctionPass</tt></a>'s on the second function,
847etc... until the entire program has been run through the passes.<p>
848
849This improves the cache behavior of the compiler, because it is only touching
850the LLVM program representation for a single function at a time, instead of
851traversing the entire program. It reduces the memory consumption of compiler,
852because, for example, only one <a
853href="http://llvm.cs.uiuc.edu/doxygen/structDominatorSet.html"><tt>DominatorSet</tt></a>
854needs to be calculated at a time. This also makes it possible some <a
855href="#SMP">interesting enhancements</a> in the future.<p>
856
857</ol><p>
858
859The effectiveness of the <tt>PassManager</tt> is influenced directly by how much
860information it has about the behaviors of the passes it is scheduling. For
861example, the "preserved" set is intentionally conservative in the face of an
862unimplemented <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method.
863Not implementing when it should be implemented will have the effect of not
864allowing any analysis results to live across the execution of your pass.<p>
865
866The <tt>PassManager</tt> class exposes a <tt>--debug-pass</tt> command line
867options that is useful for debugging pass execution, seeing how things work, and
868diagnosing when you should be preserving more analyses than you currently are
869(To get information about all of the variants of the <tt>--debug-pass</tt>
870option, just type '<tt>opt --help-hidden</tt>').<p>
871
872By using the <tt>--debug-pass=Structure</tt> option, for example, we can see how
873our <a href="#basiccode">Hello World</a> pass interacts with other passes. Lets
874try it out with the <tt>gcse</tt> and <tt>licm</tt> passes:<p>
875
876<pre>
877$ opt -load ../../../lib/Debug/libhello.so -gcse -licm --debug-pass=Structure &lt; hello.bc &gt; /dev/null
878Module Pass Manager
879 Function Pass Manager
880 Dominator Set Construction
881 Immediate Dominators Construction
882 Global Common Subexpression Elimination
883-- Immediate Dominators Construction
884-- Global Common Subexpression Elimination
885 Natural Loop Construction
886 Loop Invariant Code Motion
887-- Natural Loop Construction
888-- Loop Invariant Code Motion
889 Module Verifier
890-- Dominator Set Construction
891-- Module Verifier
892 Bytecode Writer
893--Bytecode Writer
894</pre><p>
895
896This output shows us when passes are constructed and when the analysis results
897are known to be dead (prefixed with '<tt>--</tt>'). Here we see that GCSE uses
898dominator and immediate dominator information to do its job. The LICM pass uses
899natural loop information, which uses dominator sets, but not immediate
900dominators. Because immediate dominators are no longer useful after the GCSE
901pass, it is immediately destroyed. The dominator sets are then reused to
902compute natural loop information, which is then used by the LICM pass.<p>
903
904After the LICM pass, the module verifier runs (which is automatically added by
905the '<tt>opt</tt>' tool), which uses the dominator set to check that the
906resultant LLVM code is well formed. After it finishes, the dominator set
907information is destroyed, after being computed once, and shared by three
908passes.<p>
909
910Lets see how this changes when we run the <a href="#basiccode">Hello World</a>
911pass in between the two passes:<p>
912
913<pre>
914$ opt -load ../../../lib/Debug/libhello.so -gcse -hello -licm --debug-pass=Structure &lt; hello.bc &gt; /dev/null
915Module Pass Manager
916 Function Pass Manager
917 Dominator Set Construction
918 Immediate Dominators Construction
919 Global Common Subexpression Elimination
920<b>-- Dominator Set Construction</b>
921-- Immediate Dominators Construction
922-- Global Common Subexpression Elimination
923<b> Hello World Pass
924-- Hello World Pass
925 Dominator Set Construction</b>
926 Natural Loop Construction
927 Loop Invariant Code Motion
928-- Natural Loop Construction
929-- Loop Invariant Code Motion
930 Module Verifier
931-- Dominator Set Construction
932-- Module Verifier
933 Bytecode Writer
934--Bytecode Writer
935Hello: __main
936Hello: puts
937Hello: main
938</pre><p>
939
940Here we see that the <a href="#basiccode">Hello World</a> pass has killed the
941Dominator Set pass, even though it doesn't modify the code at all! To fix this,
942we need to add the following <a
943href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method to our pass:<p>
944
945<pre>
946 <i>// We don't modify the program, so we preserve all analyses</i>
947 <b>virtual void</b> getAnalysisUsage(AnalysisUsage &amp;AU) <b>const</b> {
948 AU.setPreservesAll();
949 }
950</pre><p>
951
952Now when we run our pass, we get this output:<p>
953
954<pre>
955$ opt -load ../../../lib/Debug/libhello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null
956Pass Arguments: -gcse -hello -licm
957Module Pass Manager
958 Function Pass Manager
959 Dominator Set Construction
960 Immediate Dominators Construction
961 Global Common Subexpression Elimination
962-- Immediate Dominators Construction
963-- Global Common Subexpression Elimination
964 Hello World Pass
965-- Hello World Pass
966 Natural Loop Construction
967 Loop Invariant Code Motion
968-- Loop Invariant Code Motion
969-- Natural Loop Construction
970 Module Verifier
971-- Dominator Set Construction
972-- Module Verifier
973 Bytecode Writer
974--Bytecode Writer
975Hello: __main
976Hello: puts
977Hello: main
978</pre><p>
979
980Which shows that we don't accidentally invalidate dominator information
981anymore, and therefore do not have to compute it twice.<p>
982
983
984<!-- _______________________________________________________________________ -->
985</ul><h4><a name="releaseMemory"><hr size=0>The <tt>releaseMemory</tt> method</h4><ul>
986
987<pre>
988 <b>virtual void</b> releaseMemory();
989</pre><p>
990
991The <tt>PassManager</tt> automatically determines when to compute analysis
992results, and how long to keep them around for. Because the lifetime of the pass
993object itself is effectively the entire duration of the compilation process, we
994need some way to free analysis results when they are no longer useful. The
995<tt>releaseMemory</tt> virtual method is the way to do this.<p>
996
997If you are writing an analysis or any other pass that retains a significant
998amount of state (for use by another pass which "requires" your pass and uses the
999<a href="#getAnalysis">getAnalysis</a> method) you should implement
1000<tt>releaseMEmory</tt> to, well, release the memory allocated to maintain this
1001internal state. This method is called after the <tt>run*</tt> method for the
1002class, before the next call of <tt>run*</tt> in your pass.<p>
1003
1004
1005<!-- *********************************************************************** -->
1006</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
1007<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
Chris Lattner480e2ef2002-09-06 02:02:58 +00001008<a name="debughints">Using GDB with dynamically loaded passes
1009</b></font></td></tr></table><ul>
1010<!-- *********************************************************************** -->
1011
1012Unfortunately, using GDB with dynamically loaded passes is not as easy as it
1013should be. First of all, you can't set a breakpoint in a shared object that has
1014not been loaded yet, and second of all there are problems with inlined functions
1015in shared objects. Here are some suggestions to debugging your pass with
1016GDB.<p>
1017
1018For sake of discussion, I'm going to assume that you are debugging a
1019transformation invoked by <tt>opt</tt>, although nothing described here depends
1020on that.<p>
1021
1022<!-- _______________________________________________________________________ -->
1023</ul><h4><a name="breakpoint"><hr size=0>Setting a breakpoint in your pass</h4><ul>
1024
1025First thing you do is start <tt>gdb</tt> on the <tt>opt</tt> process:<p>
1026
1027<pre>
1028$ <b>gdb opt</b>
1029GNU gdb 5.0
1030Copyright 2000 Free Software Foundation, Inc.
1031GDB is free software, covered by the GNU General Public License, and you are
1032welcome to change it and/or distribute copies of it under certain conditions.
1033Type "show copying" to see the conditions.
1034There is absolutely no warranty for GDB. Type "show warranty" for details.
1035This GDB was configured as "sparc-sun-solaris2.6"...
1036(gdb)
1037</pre><p>
1038
1039Note that <tt>opt</tt> has a lot of debugging information in it, so it takes
1040time to load. Be patient. Since we cannot set a breakpoint in our pass yet
1041(the shared object isn't loaded until runtime), we must execute the process, and
1042have it stop before it invokes our pass, but after it has loaded the shared
1043object. The most foolproof way of doing this is to set a breakpoint in
1044<tt>PassManager::run</tt> and then run the process with the arguments you
1045want:<p>
1046
1047<pre>
1048(gdb) <b>break PassManager::run</b>
1049Breakpoint 1 at 0x2413bc: file Pass.cpp, line 70.
1050(gdb) <b>run test.bc -load /shared/lattner/cvs/llvm/lib/Debug/[libname].so -[passoption]</b>
1051Starting program: /shared/lattner/cvs/llvm/tools/Debug/opt test.bc
1052 -load /shared/lattner/cvs/llvm/lib/Debug/[libname].so -[passoption]
1053Breakpoint 1, PassManager::run (this=0xffbef174, M=@0x70b298) at Pass.cpp:70
105470 bool PassManager::run(Module &amp;M) { return PM-&gt;run(M); }
1055(gdb)
1056</pre></p>
1057
1058Once the <tt>opt</tt> stops in the <tt>PassManager::run</tt> method you are now
1059free to set breakpoints in your pass so that you can trace through execution or
1060do other standard debugging stuff.<p>
1061
1062
1063<!-- _______________________________________________________________________ -->
1064</ul><h4><a name="debugmisc"><hr size=0>Miscellaneous Problems</h4><ul>
1065
1066Once you have the basics down, there are a couple of problems that GDB has, some
1067with solutions, some without.<p>
1068
1069<ul>
1070<li>Inline functions have bogus stack information. In general, GDB does a
1071pretty good job getting stack traces and stepping through inline functions.
1072When a pass is dynamically loaded however, it somehow completely loses this
1073capability. The only solution I know of is to de-inline a function (move it
1074from the body of a class to a .cpp file).<p>
1075
1076<li>Restarting the program breaks breakpoints. After following the information
1077above, you have succeeded in getting some breakpoints planted in your pass. Nex
1078thing you know, you restart the program (i.e., you type '<tt>run</tt>' again),
1079and you start getting errors about breakpoints being unsettable. The only way I
1080have found to "fix" this problem is to <tt>delete</tt> the breakpoints that are
1081already set in your pass, run the program, and re-set the breakpoints once
1082execution stops in <tt>PassManager::run</tt>.<p>
1083
1084</ul>
1085
1086Hopefully these tips will help with common case debugging situations. If you'd
1087like to contribute some tips of your own, just contact <a
1088href="mailto:sabre@nondot.org">Chris</a>.<p>
1089
1090
1091<!-- *********************************************************************** -->
1092</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
1093<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
Chris Lattnerc6bb8242002-08-08 20:11:18 +00001094<a name="future">Future extensions planned
1095</b></font></td></tr></table><ul>
1096<!-- *********************************************************************** -->
1097
1098Although the LLVM Pass Infrastructure is very capable as it stands, and does
1099some nifty stuff, there are things we'd like to add in the future. Here is
1100where we are going:<p>
1101
1102<!-- _______________________________________________________________________ -->
1103</ul><h4><a name="SMP"><hr size=0>Multithreaded LLVM</h4><ul>
1104
1105Multiple CPU machines are becoming more command and compilation can never be
1106fast enough: obviously we should allow for a multithreaded compiler. Because of
1107the semantics defined for passes above (specifically they cannot maintain state
1108across invocations of their <tt>run*</tt> methods), a nice clean way to
1109implement a multithreaded compiler would be for the <tt>PassManager</tt> class
1110to create multiple instances of each pass object, and allow the seperate
1111instances to be hacking on different parts of the program at the same time.<p>
1112
1113This implementation would prevent each of the passes from having to implement
1114multithreaded constructs, requiring only the LLVM core to have locking in a few
1115places (for global resources). Although this is a simple extension, we simply
1116haven't had time (or multiprocessor machines, thus a reason) to implement this.
1117Despite that, we have kept the LLVM passes SMP ready, and you should too.<p>
1118
1119
1120<!-- _______________________________________________________________________ -->
1121</ul><h4><a name="ModuleSource"><hr size=0>A new <tt>ModuleSource</tt> interface</h4><ul>
1122
1123Currently, the <tt>PassManager</tt>'s <tt>run</tt> method takes a <tt><a
1124href="http://llvm.cs.uiuc.edu/doxygen/classModule.html">Module</a></tt> as
1125input, and runs all of the passes on this module. The problem with this
1126approach is that none of the <tt>PassManager</tt> features can be used for
1127timing and debugging the actual <b>loading</b> of the module from disk or
1128standard input.<p>
1129
1130To solve this problem, eventually the <tt>PassManger</tt> class will accept a
1131<tt>ModuleSource</tt> object instead of a Module itself. When complete, this
1132will also allow for streaming of functions out of the bytecode representation,
1133allowing us to avoid holding the entire program in memory at once if we only are
1134dealing with <a href="#FunctionPass">FunctionPass</a>'s.<p>
1135
1136As part of a different issue, eventually the bytecode loader will be extended to
1137allow on-demand loading of functions from the bytecode representation, in order
1138to better support the runtime reoptimizer. The bytecode format is already
1139capable of this, the loader just needs to be reworked a bit.<p>
1140
1141
1142<!-- _______________________________________________________________________ -->
1143</ul><h4><a name="PassFunctionPass"><hr size=0><tt>Pass</tt>'s requiring <tt>FunctionPass</tt>'s</h4><ul>
1144
1145Currently it is illegal for a <a href="#Pass"><tt>Pass</tt></a> to require a <a
1146href="#FunctionPass"><tt>FunctionPass</tt></a>. This is because there is only
1147one instance of the <a href="#FunctionPass"><tt>FunctionPass</tt></a> object
1148ever created, thus nowhere to store information for all of the functions in the
1149program at the same time. Although this has come up a couple of times before,
1150this has always been worked around by factoring one big complicated pass into a
1151global and an interprocedural part, both of which are distinct. In the future,
1152it would be nice to have this though.<p>
1153
1154Note that it is no problem for a <a
1155href="#FunctionPass"><tt>FunctionPass</tt></a> to require the results of a <a
1156href="#Pass"><tt>Pass</tt></a>, only the other way around.<p>
1157
1158
1159<!-- *********************************************************************** -->
1160</ul>
1161<!-- *********************************************************************** -->
1162
1163<hr><font size-1>
Chris Lattner480e2ef2002-09-06 02:02:58 +00001164<address><a href="mailto:sabre@nondot.org">Chris Lattner</a></address>
Chris Lattnerc6bb8242002-08-08 20:11:18 +00001165<!-- Created: Tue Aug 6 15:00:33 CDT 2002 -->
1166<!-- hhmts start -->
Chris Lattner480e2ef2002-09-06 02:02:58 +00001167Last modified: Thu Sep 5 15:06:01 CDT 2002
Chris Lattnerc6bb8242002-08-08 20:11:18 +00001168<!-- hhmts end -->
1169</font></body></html>