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