1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
5 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
6 <title>Writing an LLVM Pass</title>
7 <link rel="stylesheet" href="llvm.css" type="text/css">
11 <div class="doc_title">
16 <li><a href="#introduction">Introduction - What is a pass?</a></li>
17 <li><a href="#quickstart">Quick Start - Writing hello world</a>
19 <li><a href="#makefile">Setting up the build environment</a></li>
20 <li><a href="#basiccode">Basic code required</a></li>
21 <li><a href="#running">Running a pass with <tt>opt</tt>
22 or <tt>analyze</tt></a></li>
24 <li><a href="#passtype">Pass classes and requirements</a>
26 <li><a href="#ImmutablePass">The <tt>ImmutablePass</tt> class</a></li>
27 <li><a href="#ModulePass">The <tt>ModulePass</tt> class</a>
29 <li><a href="#runOnModule">The <tt>runOnModule</tt> method</a></li>
31 <li><a href="#CallGraphSCCPass">The <tt>CallGraphSCCPass</tt> class</a>
33 <li><a href="#doInitialization_scc">The <tt>doInitialization(Module
34 &)</tt> method</a></li>
35 <li><a href="#runOnSCC">The <tt>runOnSCC</tt> method</a></li>
36 <li><a href="#doFinalization_scc">The <tt>doFinalization(Module
37 &)</tt> method</a></li>
39 <li><a href="#FunctionPass">The <tt>FunctionPass</tt> class</a>
41 <li><a href="#doInitialization_mod">The <tt>doInitialization(Module
42 &)</tt> method</a></li>
43 <li><a href="#runOnFunction">The <tt>runOnFunction</tt> method</a></li>
44 <li><a href="#doFinalization_mod">The <tt>doFinalization(Module
45 &)</tt> method</a></li>
47 <li><a href="#BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
49 <li><a href="#doInitialization_fn">The <tt>doInitialization(Function
50 &)</tt> method</a></li>
51 <li><a href="#runOnBasicBlock">The <tt>runOnBasicBlock</tt>
53 <li><a href="#doFinalization_fn">The <tt>doFinalization(Function
54 &)</tt> method</a></li>
56 <li><a href="#MachineFunctionPass">The <tt>MachineFunctionPass</tt>
59 <li><a href="#runOnMachineFunction">The
60 <tt>runOnMachineFunction(MachineFunction &)</tt> method</a></li>
63 <li><a href="#registration">Pass Registration</a>
65 <li><a href="#print">The <tt>print</tt> method</a></li>
67 <li><a href="#interaction">Specifying interactions between passes</a>
69 <li><a href="#getAnalysisUsage">The <tt>getAnalysisUsage</tt>
71 <li><a href="#AU::addRequired">The <tt>AnalysisUsage::addRequired<></tt> and <tt>AnalysisUsage::addRequiredTransitive<></tt> methods</a></li>
72 <li><a href="#AU::addPreserved">The <tt>AnalysisUsage::addPreserved<></tt> method</a></li>
73 <li><a href="#AU::examples">Example implementations of <tt>getAnalysisUsage</tt></a></li>
74 <li><a href="#getAnalysis">The <tt>getAnalysis<></tt> and <tt>getAnalysisToUpdate<></tt> methods</a></li>
76 <li><a href="#analysisgroup">Implementing Analysis Groups</a>
78 <li><a href="#agconcepts">Analysis Group Concepts</a></li>
79 <li><a href="#registerag">Using <tt>RegisterAnalysisGroup</tt></a></li>
81 <li><a href="#passStatistics">Pass Statistics</a>
82 <li><a href="#passmanager">What PassManager does</a>
84 <li><a href="#releaseMemory">The <tt>releaseMemory</tt> method</a></li>
86 <li><a href="#registering">Registering dynamically loaded passes</a>
88 <li><a href="#registering_existing">Using existing registries</a></li>
89 <li><a href="#registering_new">Creating new registries</a></li>
91 <li><a href="#debughints">Using GDB with dynamically loaded passes</a>
93 <li><a href="#breakpoint">Setting a breakpoint in your pass</a></li>
94 <li><a href="#debugmisc">Miscellaneous Problems</a></li>
96 <li><a href="#future">Future extensions planned</a>
98 <li><a href="#SMP">Multithreaded LLVM</a></li>
99 <li><a href="#PassFunctionPass"><tt>ModulePass</tt>es requiring
100 <tt>FunctionPass</tt>es</a></li>
104 <div class="doc_author">
105 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>,
106 <a href="mailto:jlaskey@apple.com">Jim Laskey</a></p>
109 <!-- *********************************************************************** -->
110 <div class="doc_section">
111 <a name="introduction">Introduction - What is a pass?</a>
113 <!-- *********************************************************************** -->
115 <div class="doc_text">
117 <p>The LLVM Pass Framework is an important part of the LLVM system, because LLVM
118 passes are where most of the interesting parts of the compiler exist. Passes
119 perform the transformations and optimizations that make up the compiler, they
120 build the analysis results that are used by these transformations, and they are,
121 above all, a structuring technique for compiler code.</p>
123 <p>All LLVM passes are subclasses of the <tt><a
124 href="http://llvm.org/doxygen/classllvm_1_1Pass.html">Pass</a></tt>
125 class, which implement functionality by overriding virtual methods inherited
126 from <tt>Pass</tt>. Depending on how your pass works, you should inherit from
127 the <tt><a href="#ModulePass">ModulePass</a></tt>, <tt><a
128 href="#CallGraphSCCPass">CallGraphSCCPass</a></tt>, <tt><a
129 href="#FunctionPass">FunctionPass</a></tt>, or <tt><a
130 href="#BasicBlockPass">BasicBlockPass</a></tt> classes, which gives the system
131 more information about what your pass does, and how it can be combined with
132 other passes. One of the main features of the LLVM Pass Framework is that it
133 schedules passes to run in an efficient way based on the constraints that your
134 pass meets (which are indicated by which class they derive from).</p>
136 <p>We start by showing you how to construct a pass, everything from setting up
137 the code, to compiling, loading, and executing it. After the basics are down,
138 more advanced features are discussed.</p>
142 <!-- *********************************************************************** -->
143 <div class="doc_section">
144 <a name="quickstart">Quick Start - Writing hello world</a>
146 <!-- *********************************************************************** -->
148 <div class="doc_text">
150 <p>Here we describe how to write the "hello world" of passes. The "Hello" pass
151 is designed to simply print out the name of non-external functions that exist in
152 the program being compiled. It does not modify the program at all, it just
153 inspects it. The source code and files for this pass are available in the LLVM
154 source tree in the <tt>lib/Transforms/Hello</tt> directory.</p>
158 <!-- ======================================================================= -->
159 <div class="doc_subsection">
160 <a name="makefile">Setting up the build environment</a>
163 <div class="doc_text">
165 <p>First, you need to create a new directory somewhere in the LLVM source
166 base. For this example, we'll assume that you made
167 <tt>lib/Transforms/Hello</tt>. Next, you must set up a build script
168 (Makefile) that will compile the source code for the new pass. To do this,
169 copy the following into <tt>Makefile</tt>:</p>
172 <div class="doc_code"><pre>
173 # Makefile for hello pass
175 # Path to top level of LLVM heirarchy
178 # Name of the library to build
181 # Make the shared library become a loadable module so the tools can
182 # dlopen/dlsym on the resulting library.
185 # Tell the build system which LLVM libraries your pass needs. You'll probably
186 # need at least LLVMSystem.a, LLVMSupport.a, LLVMCore.a but possibly several
188 LLVMLIBS = LLVMCore.a LLVMSupport.a LLVMSystem.a
190 # Include the makefile implementation stuff
191 include $(LEVEL)/Makefile.common
194 <p>This makefile specifies that all of the <tt>.cpp</tt> files in the current
195 directory are to be compiled and linked together into a
196 <tt>Debug/lib/Hello.so</tt> shared object that can be dynamically loaded by
197 the <tt>opt</tt> or <tt>analyze</tt> tools via their <tt>-load</tt> options.
198 If your operating system uses a suffix other than .so (such as windows or
199 Mac OS/X), the appropriate extension will be used.</p>
201 <p>Now that we have the build scripts set up, we just need to write the code for
206 <!-- ======================================================================= -->
207 <div class="doc_subsection">
208 <a name="basiccode">Basic code required</a>
211 <div class="doc_text">
213 <p>Now that we have a way to compile our new pass, we just have to write it.
216 <div class="doc_code"><pre>
217 <b>#include</b> "<a href="http://llvm.org/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
218 <b>#include</b> "<a href="http://llvm.org/doxygen/Function_8h-source.html">llvm/Function.h</a>"
221 <p>Which are needed because we are writing a <tt><a
222 href="http://llvm.org/doxygen/classllvm_1_1Pass.html">Pass</a></tt>, and
223 we are operating on <tt><a
224 href="http://llvm.org/doxygen/classllvm_1_1Function.html">Function</a></tt>'s.</p>
227 <div class="doc_code"><pre>
228 <b>using namespace llvm;</b>
230 <p>... which is required because the functions from the include files
231 live in the llvm namespace.
236 <div class="doc_code"><pre>
240 <p>... which starts out an anonymous namespace. Anonymous namespaces are to C++
241 what the "<tt>static</tt>" keyword is to C (at global scope). It makes the
242 things declared inside of the anonymous namespace only visible to the current
243 file. If you're not familiar with them, consult a decent C++ book for more
246 <p>Next, we declare our pass itself:</p>
248 <div class="doc_code"><pre>
249 <b>struct</b> Hello : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
252 <p>This declares a "<tt>Hello</tt>" class that is a subclass of <tt><a
253 href="http://llvm.org/doxygen/classllvm_1_1FunctionPass.html">FunctionPass</a></tt>.
254 The different builtin pass subclasses are described in detail <a
255 href="#passtype">later</a>, but for now, know that <a
256 href="#FunctionPass"><tt>FunctionPass</tt></a>'s operate a function at a
259 <div class="doc_code"><pre>
260 <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &F) {
261 std::cerr << "<i>Hello: </i>" << F.getName() << "\n";
264 }; <i>// end of struct Hello</i>
267 <p>We declare a "<a href="#runOnFunction"><tt>runOnFunction</tt></a>" method,
268 which overloads an abstract virtual method inherited from <a
269 href="#FunctionPass"><tt>FunctionPass</tt></a>. This is where we are supposed
270 to do our thing, so we just print out our message with the name of each
273 <div class="doc_code"><pre>
274 RegisterOpt<Hello> X("<i>hello</i>", "<i>Hello World Pass</i>");
275 } <i>// end of anonymous namespace</i>
278 <p>Lastly, we register our class <tt>Hello</tt>, giving it a command line
279 argument "<tt>hello</tt>", and a name "<tt>Hello World Pass</tt>". There are
280 several different ways of <a href="#registration">registering your pass</a>,
281 depending on what it is to be used for. For "optimizations" we use the
282 <tt>RegisterOpt</tt> template.</p>
284 <p>As a whole, the <tt>.cpp</tt> file looks like:</p>
286 <div class="doc_code"><pre>
287 <b>#include</b> "<a href="http://llvm.org/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
288 <b>#include</b> "<a href="http://llvm.org/doxygen/Function_8h-source.html">llvm/Function.h</a>"
290 <b>using namespace llvm;</b>
293 <b>struct Hello</b> : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
294 <b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &F) {
295 std::cerr << "<i>Hello: </i>" << F.getName() << "\n";
300 RegisterOpt<Hello> X("<i>hello</i>", "<i>Hello World Pass</i>");
304 <p>Now that it's all together, compile the file with a simple "<tt>gmake</tt>"
305 command in the local directory and you should get a new
306 "<tt>Debug/lib/Hello.so</tt> file. Note that everything in this file is
307 contained in an anonymous namespace: this reflects the fact that passes are self
308 contained units that do not need external interfaces (although they can have
309 them) to be useful.</p>
313 <!-- ======================================================================= -->
314 <div class="doc_subsection">
315 <a name="running">Running a pass with <tt>opt</tt> or <tt>analyze</tt></a>
318 <div class="doc_text">
320 <p>Now that you have a brand new shiny shared object file, we can use the
321 <tt>opt</tt> command to run an LLVM program through your pass. Because you
322 registered your pass with the <tt>RegisterOpt</tt> template, you will be able to
323 use the <tt>opt</tt> tool to access it, once loaded.</p>
325 <p>To test it, follow the example at the end of the <a
326 href="GettingStarted.html">Getting Started Guide</a> to compile "Hello World" to
327 LLVM. We can now run the bytecode file (<tt>hello.bc</tt>) for the program
328 through our transformation like this (or course, any bytecode file will
331 <div class="doc_code"><pre>
332 $ opt -load ../../../Debug/lib/Hello.so -hello < hello.bc > /dev/null
338 <p>The '<tt>-load</tt>' option specifies that '<tt>opt</tt>' should load your
339 pass as a shared object, which makes '<tt>-hello</tt>' a valid command line
340 argument (which is one reason you need to <a href="#registration">register your
341 pass</a>). Because the hello pass does not modify the program in any
342 interesting way, we just throw away the result of <tt>opt</tt> (sending it to
343 <tt>/dev/null</tt>).</p>
345 <p>To see what happened to the other string you registered, try running
346 <tt>opt</tt> with the <tt>--help</tt> option:</p>
348 <div class="doc_code"><pre>
349 $ opt -load ../../../Debug/lib/Hello.so --help
350 OVERVIEW: llvm .bc -> .bc modular optimizer
352 USAGE: opt [options] <input bytecode>
355 Optimizations available:
357 -funcresolve - Resolve Functions
358 -gcse - Global Common Subexpression Elimination
359 -globaldce - Dead Global Elimination
360 <b>-hello - Hello World Pass</b>
361 -indvars - Canonicalize Induction Variables
362 -inline - Function Integration/Inlining
363 -instcombine - Combine redundant instructions
367 <p>The pass name get added as the information string for your pass, giving some
368 documentation to users of <tt>opt</tt>. Now that you have a working pass, you
369 would go ahead and make it do the cool transformations you want. Once you get
370 it all working and tested, it may become useful to find out how fast your pass
371 is. The <a href="#passManager"><tt>PassManager</tt></a> provides a nice command
372 line option (<tt>--time-passes</tt>) that allows you to get information about
373 the execution time of your pass along with the other passes you queue up. For
376 <div class="doc_code"><pre>
377 $ opt -load ../../../Debug/lib/Hello.so -hello -time-passes < hello.bc > /dev/null
381 ===============================================================================
382 ... Pass execution timing report ...
383 ===============================================================================
384 Total Execution Time: 0.02 seconds (0.0479059 wall clock)
386 ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Pass Name ---
387 0.0100 (100.0%) 0.0000 ( 0.0%) 0.0100 ( 50.0%) 0.0402 ( 84.0%) Bytecode Writer
388 0.0000 ( 0.0%) 0.0100 (100.0%) 0.0100 ( 50.0%) 0.0031 ( 6.4%) Dominator Set Construction
389 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0013 ( 2.7%) Module Verifier
390 <b> 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0033 ( 6.9%) Hello World Pass</b>
391 0.0100 (100.0%) 0.0100 (100.0%) 0.0200 (100.0%) 0.0479 (100.0%) TOTAL
394 <p>As you can see, our implementation above is pretty fast :). The additional
395 passes listed are automatically inserted by the '<tt>opt</tt>' tool to verify
396 that the LLVM emitted by your pass is still valid and well formed LLVM, which
397 hasn't been broken somehow.</p>
399 <p>Now that you have seen the basics of the mechanics behind passes, we can talk
400 about some more details of how they work and how to use them.</p>
404 <!-- *********************************************************************** -->
405 <div class="doc_section">
406 <a name="passtype">Pass classes and requirements</a>
408 <!-- *********************************************************************** -->
410 <div class="doc_text">
412 <p>One of the first things that you should do when designing a new pass is to
413 decide what class you should subclass for your pass. The <a
414 href="#basiccode">Hello World</a> example uses the <tt><a
415 href="#FunctionPass">FunctionPass</a></tt> class for its implementation, but we
416 did not discuss why or when this should occur. Here we talk about the classes
417 available, from the most general to the most specific.</p>
419 <p>When choosing a superclass for your Pass, you should choose the <b>most
420 specific</b> class possible, while still being able to meet the requirements
421 listed. This gives the LLVM Pass Infrastructure information necessary to
422 optimize how passes are run, so that the resultant compiler isn't unneccesarily
427 <!-- ======================================================================= -->
428 <div class="doc_subsection">
429 <a name="ImmutablePass">The <tt>ImmutablePass</tt> class</a>
432 <div class="doc_text">
434 <p>The most plain and boring type of pass is the "<tt><a
435 href="http://llvm.org/doxygen/classllvm_1_1ImmutablePass.html">ImmutablePass</a></tt>"
436 class. This pass type is used for passes that do not have to be run, do not
437 change state, and never need to be updated. This is not a normal type of
438 transformation or analysis, but can provide information about the current
439 compiler configuration.</p>
441 <p>Although this pass class is very infrequently used, it is important for
442 providing information about the current target machine being compiled for, and
443 other static information that can affect the various transformations.</p>
445 <p><tt>ImmutablePass</tt>es never invalidate other transformations, are never
446 invalidated, and are never "run".</p>
450 <!-- ======================================================================= -->
451 <div class="doc_subsection">
452 <a name="ModulePass">The <tt>ModulePass</tt> class</a>
455 <div class="doc_text">
458 href="http://llvm.org/doxygen/classllvm_1_1ModulePass.html">ModulePass</a></tt>"
459 class is the most general of all superclasses that you can use. Deriving from
460 <tt>ModulePass</tt> indicates that your pass uses the entire program as a unit,
461 refering to function bodies in no predictable order, or adding and removing
462 functions. Because nothing is known about the behavior of <tt>ModulePass</tt>
463 subclasses, no optimization can be done for their execution.</p>
465 <p>To write a correct <tt>ModulePass</tt> subclass, derive from
466 <tt>ModulePass</tt> and overload the <tt>runOnModule</tt> method with the
467 following signature:</p>
471 <!-- _______________________________________________________________________ -->
472 <div class="doc_subsubsection">
473 <a name="runOnModule">The <tt>runOnModule</tt> method</a>
476 <div class="doc_text">
478 <div class="doc_code"><pre>
479 <b>virtual bool</b> runOnModule(Module &M) = 0;
482 <p>The <tt>runOnModule</tt> method performs the interesting work of the pass.
483 It should return true if the module was modified by the transformation and
488 <!-- ======================================================================= -->
489 <div class="doc_subsection">
490 <a name="CallGraphSCCPass">The <tt>CallGraphSCCPass</tt> class</a>
493 <div class="doc_text">
496 href="http://llvm.org/doxygen/classllvm_1_1CallGraphSCCPass.html">CallGraphSCCPass</a></tt>"
497 is used by passes that need to traverse the program bottom-up on the call graph
498 (callees before callers). Deriving from CallGraphSCCPass provides some
499 mechanics for building and traversing the CallGraph, but also allows the system
500 to optimize execution of CallGraphSCCPass's. If your pass meets the
501 requirements outlined below, and doesn't meet the requirements of a <tt><a
502 href="#FunctionPass">FunctionPass</a></tt> or <tt><a
503 href="#BasicBlockPass">BasicBlockPass</a></tt>, you should derive from
504 <tt>CallGraphSCCPass</tt>.</p>
506 <p><b>TODO</b>: explain briefly what SCC, Tarjan's algo, and B-U mean.</p>
508 <p>To be explicit, <tt>CallGraphSCCPass</tt> subclasses are:</p>
512 <li>... <em>not allowed</em> to modify any <tt>Function</tt>s that are not in
513 the current SCC.</li>
515 <li>... <em>allowed</em> to inspect any Function's other than those in the
516 current SCC and the direct callees of the SCC.</li>
518 <li>... <em>required</em> to preserve the current CallGraph object, updating it
519 to reflect any changes made to the program.</li>
521 <li>... <em>not allowed</em> to add or remove SCC's from the current Module,
522 though they may change the contents of an SCC.</li>
524 <li>... <em>allowed</em> to add or remove global variables from the current
527 <li>... <em>allowed</em> to maintain state across invocations of
528 <a href="#runOnSCC"><tt>runOnSCC</tt></a> (including global data).</li>
531 <p>Implementing a <tt>CallGraphSCCPass</tt> is slightly tricky in some cases
532 because it has to handle SCCs with more than one node in it. All of the virtual
533 methods described below should return true if they modified the program, or
534 false if they didn't.</p>
538 <!-- _______________________________________________________________________ -->
539 <div class="doc_subsubsection">
540 <a name="doInitialization_scc">The <tt>doInitialization(Module &)</tt>
544 <div class="doc_text">
546 <div class="doc_code"><pre>
547 <b>virtual bool</b> doInitialization(Module &M);
550 <p>The <tt>doIninitialize</tt> method is allowed to do most of the things that
551 <tt>CallGraphSCCPass</tt>'s are not allowed to do. They can add and remove
552 functions, get pointers to functions, etc. The <tt>doInitialization</tt> method
553 is designed to do simple initialization type of stuff that does not depend on
554 the SCCs being processed. The <tt>doInitialization</tt> method call is not
555 scheduled to overlap with any other pass executions (thus it should be very
560 <!-- _______________________________________________________________________ -->
561 <div class="doc_subsubsection">
562 <a name="runOnSCC">The <tt>runOnSCC</tt> method</a>
565 <div class="doc_text">
567 <div class="doc_code"><pre>
568 <b>virtual bool</b> runOnSCC(const std::vector<CallGraphNode *> &SCCM) = 0;
571 <p>The <tt>runOnSCC</tt> method performs the interesting work of the pass, and
572 should return true if the module was modified by the transformation, false
577 <!-- _______________________________________________________________________ -->
578 <div class="doc_subsubsection">
579 <a name="doFinalization_scc">The <tt>doFinalization(Module
580 &)</tt> method</a>
583 <div class="doc_text">
585 <div class="doc_code"><pre>
586 <b>virtual bool</b> doFinalization(Module &M);
589 <p>The <tt>doFinalization</tt> method is an infrequently used method that is
590 called when the pass framework has finished calling <a
591 href="#runOnFunction"><tt>runOnFunction</tt></a> for every function in the
592 program being compiled.</p>
596 <!-- ======================================================================= -->
597 <div class="doc_subsection">
598 <a name="FunctionPass">The <tt>FunctionPass</tt> class</a>
601 <div class="doc_text">
603 <p>In contrast to <tt>ModulePass</tt> subclasses, <tt><a
604 href="http://llvm.org/doxygen/classllvm_1_1Pass.html">FunctionPass</a></tt>
605 subclasses do have a predictable, local behavior that can be expected by the
606 system. All <tt>FunctionPass</tt> execute on each function in the program
607 independent of all of the other functions in the program.
608 <tt>FunctionPass</tt>'s do not require that they are executed in a particular
609 order, and <tt>FunctionPass</tt>'s do not modify external functions.</p>
611 <p>To be explicit, <tt>FunctionPass</tt> subclasses are not allowed to:</p>
614 <li>Modify a Function other than the one currently being processed.</li>
615 <li>Add or remove Function's from the current Module.</li>
616 <li>Add or remove global variables from the current Module.</li>
617 <li>Maintain state across invocations of
618 <a href="#runOnFunction"><tt>runOnFunction</tt></a> (including global data)</li>
621 <p>Implementing a <tt>FunctionPass</tt> is usually straightforward (See the <a
622 href="#basiccode">Hello World</a> pass for example). <tt>FunctionPass</tt>'s
623 may overload three virtual methods to do their work. All of these methods
624 should return true if they modified the program, or false if they didn't.</p>
628 <!-- _______________________________________________________________________ -->
629 <div class="doc_subsubsection">
630 <a name="doInitialization_mod">The <tt>doInitialization(Module &)</tt>
634 <div class="doc_text">
636 <div class="doc_code"><pre>
637 <b>virtual bool</b> doInitialization(Module &M);
640 <p>The <tt>doIninitialize</tt> method is allowed to do most of the things that
641 <tt>FunctionPass</tt>'s are not allowed to do. They can add and remove
642 functions, get pointers to functions, etc. The <tt>doInitialization</tt> method
643 is designed to do simple initialization type of stuff that does not depend on
644 the functions being processed. The <tt>doInitialization</tt> method call is not
645 scheduled to overlap with any other pass executions (thus it should be very
648 <p>A good example of how this method should be used is the <a
649 href="http://llvm.org/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations</a>
650 pass. This pass converts <tt>malloc</tt> and <tt>free</tt> instructions into
651 platform dependent <tt>malloc()</tt> and <tt>free()</tt> function calls. It
652 uses the <tt>doInitialization</tt> method to get a reference to the malloc and
653 free functions that it needs, adding prototypes to the module if necessary.</p>
657 <!-- _______________________________________________________________________ -->
658 <div class="doc_subsubsection">
659 <a name="runOnFunction">The <tt>runOnFunction</tt> method</a>
662 <div class="doc_text">
664 <div class="doc_code"><pre>
665 <b>virtual bool</b> runOnFunction(Function &F) = 0;
668 <p>The <tt>runOnFunction</tt> method must be implemented by your subclass to do
669 the transformation or analysis work of your pass. As usual, a true value should
670 be returned if the function is modified.</p>
674 <!-- _______________________________________________________________________ -->
675 <div class="doc_subsubsection">
676 <a name="doFinalization_mod">The <tt>doFinalization(Module
677 &)</tt> method</a>
680 <div class="doc_text">
682 <div class="doc_code"><pre>
683 <b>virtual bool</b> doFinalization(Module &M);
686 <p>The <tt>doFinalization</tt> method is an infrequently used method that is
687 called when the pass framework has finished calling <a
688 href="#runOnFunction"><tt>runOnFunction</tt></a> for every function in the
689 program being compiled.</p>
693 <!-- ======================================================================= -->
694 <div class="doc_subsection">
695 <a name="BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
698 <div class="doc_text">
700 <p><tt>BasicBlockPass</tt>'s are just like <a
701 href="#FunctionPass"><tt>FunctionPass</tt></a>'s, except that they must limit
702 their scope of inspection and modification to a single basic block at a time.
703 As such, they are <b>not</b> allowed to do any of the following:</p>
706 <li>Modify or inspect any basic blocks outside of the current one</li>
707 <li>Maintain state across invocations of
708 <a href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a></li>
709 <li>Modify the control flow graph (by altering terminator instructions)</li>
710 <li>Any of the things forbidden for
711 <a href="#FunctionPass"><tt>FunctionPass</tt></a>es.</li>
714 <p><tt>BasicBlockPass</tt>es are useful for traditional local and "peephole"
715 optimizations. They may override the same <a
716 href="#doInitialization_mod"><tt>doInitialization(Module &)</tt></a> and <a
717 href="#doFinalization_mod"><tt>doFinalization(Module &)</tt></a> methods that <a
718 href="#FunctionPass"><tt>FunctionPass</tt></a>'s have, but also have the following virtual methods that may also be implemented:</p>
722 <!-- _______________________________________________________________________ -->
723 <div class="doc_subsubsection">
724 <a name="doInitialization_fn">The <tt>doInitialization(Function
725 &)</tt> method</a>
728 <div class="doc_text">
730 <div class="doc_code"><pre>
731 <b>virtual bool</b> doInitialization(Function &F);
734 <p>The <tt>doIninitialize</tt> method is allowed to do most of the things that
735 <tt>BasicBlockPass</tt>'s are not allowed to do, but that
736 <tt>FunctionPass</tt>'s can. The <tt>doInitialization</tt> method is designed
737 to do simple initialization that does not depend on the
738 BasicBlocks being processed. The <tt>doInitialization</tt> method call is not
739 scheduled to overlap with any other pass executions (thus it should be very
744 <!-- _______________________________________________________________________ -->
745 <div class="doc_subsubsection">
746 <a name="runOnBasicBlock">The <tt>runOnBasicBlock</tt> method</a>
749 <div class="doc_text">
751 <div class="doc_code"><pre>
752 <b>virtual bool</b> runOnBasicBlock(BasicBlock &BB) = 0;
755 <p>Override this function to do the work of the <tt>BasicBlockPass</tt>. This
756 function is not allowed to inspect or modify basic blocks other than the
757 parameter, and are not allowed to modify the CFG. A true value must be returned
758 if the basic block is modified.</p>
762 <!-- _______________________________________________________________________ -->
763 <div class="doc_subsubsection">
764 <a name="doFinalization_fn">The <tt>doFinalization(Function &)</tt>
768 <div class="doc_text">
770 <div class="doc_code"><pre>
771 <b>virtual bool</b> doFinalization(Function &F);
774 <p>The <tt>doFinalization</tt> method is an infrequently used method that is
775 called when the pass framework has finished calling <a
776 href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a> for every BasicBlock in the
777 program being compiled. This can be used to perform per-function
782 <!-- ======================================================================= -->
783 <div class="doc_subsection">
784 <a name="MachineFunctionPass">The <tt>MachineFunctionPass</tt> class</a>
787 <div class="doc_text">
789 <p>A <tt>MachineFunctionPass</tt> is a part of the LLVM code generator that
790 executes on the machine-dependent representation of each LLVM function in the
791 program. A <tt>MachineFunctionPass</tt> is also a <tt>FunctionPass</tt>, so all
792 the restrictions that apply to a <tt>FunctionPass</tt> also apply to it.
793 <tt>MachineFunctionPass</tt>es also have additional restrictions. In particular,
794 <tt>MachineFunctionPass</tt>es are not allowed to do any of the following:</p>
797 <li>Modify any LLVM Instructions, BasicBlocks or Functions.</li>
798 <li>Modify a MachineFunction other than the one currently being processed.</li>
799 <li>Add or remove MachineFunctions from the current Module.</li>
800 <li>Add or remove global variables from the current Module.</li>
801 <li>Maintain state across invocations of <a
802 href="#runOnMachineFunction"><tt>runOnMachineFunction</tt></a> (including global
808 <!-- _______________________________________________________________________ -->
809 <div class="doc_subsubsection">
810 <a name="runOnMachineFunction">The <tt>runOnMachineFunction(MachineFunction
811 &MF)</tt> method</a>
814 <div class="doc_text">
816 <div class="doc_code"><pre>
817 <b>virtual bool</b> runOnMachineFunction(MachineFunction &MF) = 0;
820 <p><tt>runOnMachineFunction</tt> can be considered the main entry point of a
821 <tt>MachineFunctionPass</tt>; that is, you should override this method to do the
822 work of your <tt>MachineFunctionPass</tt>.</p>
824 <p>The <tt>runOnMachineFunction</tt> method is called on every
825 <tt>MachineFunction</tt> in a <tt>Module</tt>, so that the
826 <tt>MachineFunctionPass</tt> may perform optimizations on the machine-dependent
827 representation of the function. If you want to get at the LLVM <tt>Function</tt>
828 for the <tt>MachineFunction</tt> you're working on, use
829 <tt>MachineFunction</tt>'s <tt>getFunction()</tt> accessor method -- but
830 remember, you may not modify the LLVM <tt>Function</tt> or its contents from a
831 <tt>MachineFunctionPass</tt>.</p>
835 <!-- *********************************************************************** -->
836 <div class="doc_section">
837 <a name="registration">Pass registration</a>
839 <!-- *********************************************************************** -->
841 <div class="doc_text">
843 <p>In the <a href="#basiccode">Hello World</a> example pass we illustrated how
844 pass registration works, and discussed some of the reasons that it is used and
845 what it does. Here we discuss how and why passes are registered.</p>
847 <p>Passes can be registered in several different ways. Depending on the general
848 classification of the pass, you should use one of the following templates to
849 register the pass:</p>
852 <li><b><tt>RegisterOpt</tt></b> - This template should be used when you are
853 registering a pass that logically should be available for use in the
854 '<tt>opt</tt>' utility.</li>
856 <li><b><tt>RegisterAnalysis</tt></b> - This template should be used when you are
857 registering a pass that logically should be available for use in the
858 '<tt>analyze</tt>' utility.</li>
860 <li><b><tt>RegisterPass</tt></b> - This is the generic form of the
861 <tt>Register*</tt> templates that should be used if you want your pass listed by
862 multiple or no utilities. This template takes an extra third argument that
863 specifies which tools it should be listed in. See the <a
864 href="http://llvm.org/doxygen/PassSupport_8h-source.html">PassSupport.h</a>
865 file for more information.</li>
869 <p>Regardless of how you register your pass, you must specify at least two
870 parameters. The first parameter is the name of the pass that is to be used on
871 the command line to specify that the pass should be added to a program (for
872 example <tt>opt</tt> or <tt>analyze</tt>). The second argument is the name of
873 the pass, which is to be used for the <tt>--help</tt> output of programs, as
874 well as for debug output generated by the <tt>--debug-pass</tt> option.</p>
876 <p>If a pass is registered to be used by the <tt>analyze</tt> utility, you
877 should implement the virtual <tt>print</tt> method:</p>
881 <!-- _______________________________________________________________________ -->
882 <div class="doc_subsubsection">
883 <a name="print">The <tt>print</tt> method</a>
886 <div class="doc_text">
888 <div class="doc_code"><pre>
889 <b>virtual void</b> print(std::ostream &O, <b>const</b> Module *M) <b>const</b>;
892 <p>The <tt>print</tt> method must be implemented by "analyses" in order to print
893 a human readable version of the analysis results. This is useful for debugging
894 an analysis itself, as well as for other people to figure out how an analysis
895 works. The <tt>analyze</tt> tool uses this method to generate its output.</p>
897 <p>The <tt>ostream</tt> parameter specifies the stream to write the results on,
898 and the <tt>Module</tt> parameter gives a pointer to the top level module of the
899 program that has been analyzed. Note however that this pointer may be null in
900 certain circumstances (such as calling the <tt>Pass::dump()</tt> from a
901 debugger), so it should only be used to enhance debug output, it should not be
906 <!-- *********************************************************************** -->
907 <div class="doc_section">
908 <a name="interaction">Specifying interactions between passes</a>
910 <!-- *********************************************************************** -->
912 <div class="doc_text">
914 <p>One of the main responsibilities of the <tt>PassManager</tt> is the make sure
915 that passes interact with each other correctly. Because <tt>PassManager</tt>
916 tries to <a href="#passmanager">optimize the execution of passes</a> it must
917 know how the passes interact with each other and what dependencies exist between
918 the various passes. To track this, each pass can declare the set of passes that
919 are required to be executed before the current pass, and the passes which are
920 invalidated by the current pass.</p>
922 <p>Typically this functionality is used to require that analysis results are
923 computed before your pass is run. Running arbitrary transformation passes can
924 invalidate the computed analysis results, which is what the invalidation set
925 specifies. If a pass does not implement the <tt><a
926 href="#getAnalysisUsage">getAnalysisUsage</a></tt> method, it defaults to not
927 having any prerequisite passes, and invalidating <b>all</b> other passes.</p>
931 <!-- _______________________________________________________________________ -->
932 <div class="doc_subsubsection">
933 <a name="getAnalysisUsage">The <tt>getAnalysisUsage</tt> method</a>
936 <div class="doc_text">
938 <div class="doc_code"><pre>
939 <b>virtual void</b> getAnalysisUsage(AnalysisUsage &Info) <b>const</b>;
942 <p>By implementing the <tt>getAnalysisUsage</tt> method, the required and
943 invalidated sets may be specified for your transformation. The implementation
944 should fill in the <tt><a
945 href="http://llvm.org/doxygen/classllvm_1_1AnalysisUsage.html">AnalysisUsage</a></tt>
946 object with information about which passes are required and not invalidated. To
947 do this, a pass may call any of the following methods on the AnalysisUsage
951 <!-- _______________________________________________________________________ -->
952 <div class="doc_subsubsection">
953 <a name="AU::addRequired">The <tt>AnalysisUsage::addRequired<></tt> and <tt>AnalysisUsage::addRequiredTransitive<></tt> methods</a>
956 <div class="doc_text">
958 If your pass requires a previous pass to be executed (an analysis for example),
959 it can use one of these methods to arrange for it to be run before your pass.
960 LLVM has many different types of analyses and passes that can be required,
961 spanning the range from <tt>DominatorSet</tt> to <tt>BreakCriticalEdges</tt>.
962 Requiring <tt>BreakCriticalEdges</tt>, for example, guarantees that there will
963 be no critical edges in the CFG when your pass has been run.
967 Some analyses chain to other analyses to do their job. For example, an <a
968 href="AliasAnalysis.html">AliasAnalysis</a> implementation is required to <a
969 href="AliasAnalysis.html#chaining">chain</a> to other alias analysis passes. In
970 cases where analyses chain, the <tt>addRequiredTransitive</tt> method should be
971 used instead of the <tt>addRequired</tt> method. This informs the PassManager
972 that the transitively required pass should be alive as long as the requiring
977 <!-- _______________________________________________________________________ -->
978 <div class="doc_subsubsection">
979 <a name="AU::addPreserved">The <tt>AnalysisUsage::addPreserved<></tt> method</a>
982 <div class="doc_text">
984 One of the jobs of the PassManager is to optimize how and when analyses are run.
985 In particular, it attempts to avoid recomputing data unless it needs to. For
986 this reason, passes are allowed to declare that they preserve (i.e., they don't
987 invalidate) an existing analysis if it's available. For example, a simple
988 constant folding pass would not modify the CFG, so it can't possibly affect the
989 results of dominator analysis. By default, all passes are assumed to invalidate
994 The <tt>AnalysisUsage</tt> class provides several methods which are useful in
995 certain circumstances that are related to <tt>addPreserved</tt>. In particular,
996 the <tt>setPreservesAll</tt> method can be called to indicate that the pass does
997 not modify the LLVM program at all (which is true for analyses), and the
998 <tt>setPreservesCFG</tt> method can be used by transformations that change
999 instructions in the program but do not modify the CFG or terminator instructions
1000 (note that this property is implicitly set for <a
1001 href="#BasicBlockPass">BasicBlockPass</a>'s).
1005 <tt>addPreserved</tt> is particularly useful for transformations like
1006 <tt>BreakCriticalEdges</tt>. This pass knows how to update a small set of loop
1007 and dominator related analyses if they exist, so it can preserve them, despite
1008 the fact that it hacks on the CFG.
1012 <!-- _______________________________________________________________________ -->
1013 <div class="doc_subsubsection">
1014 <a name="AU::examples">Example implementations of <tt>getAnalysisUsage</tt></a>
1017 <div class="doc_text">
1019 <div class="doc_code"><pre>
1020 <i>// This is an example implementation from an analysis, which does not modify
1021 // the program at all, yet has a prerequisite.</i>
1022 <b>void</b> <a href="http://llvm.org/doxygen/classllvm_1_1PostDominanceFrontier.html">PostDominanceFrontier</a>::getAnalysisUsage(AnalysisUsage &AU) <b>const</b> {
1023 AU.setPreservesAll();
1024 AU.addRequired<<a href="http://llvm.org/doxygen/classllvm_1_1PostDominatorTree.html">PostDominatorTree</a>>();
1030 <div class="doc_code"><pre>
1031 <i>// This example modifies the program, but does not modify the CFG</i>
1032 <b>void</b> <a href="http://llvm.org/doxygen/structLICM.html">LICM</a>::getAnalysisUsage(AnalysisUsage &AU) <b>const</b> {
1033 AU.setPreservesCFG();
1034 AU.addRequired<<a href="http://llvm.org/doxygen/classllvm_1_1LoopInfo.html">LoopInfo</a>>();
1040 <!-- _______________________________________________________________________ -->
1041 <div class="doc_subsubsection">
1042 <a name="getAnalysis">The <tt>getAnalysis<></tt> and <tt>getAnalysisToUpdate<></tt> methods</a>
1045 <div class="doc_text">
1047 <p>The <tt>Pass::getAnalysis<></tt> method is automatically inherited by
1048 your class, providing you with access to the passes that you declared that you
1049 required with the <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a>
1050 method. It takes a single template argument that specifies which pass class you
1051 want, and returns a reference to that pass. For example:</p>
1053 <div class="doc_code"><pre>
1054 bool LICM::runOnFunction(Function &F) {
1055 LoopInfo &LI = getAnalysis<LoopInfo>();
1060 <p>This method call returns a reference to the pass desired. You may get a
1061 runtime assertion failure if you attempt to get an analysis that you did not
1062 declare as required in your <a
1063 href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> implementation. This
1064 method can be called by your <tt>run*</tt> method implementation, or by any
1065 other local method invoked by your <tt>run*</tt> method.</p>
1068 If your pass is capable of updating analyses if they exist (e.g.,
1069 <tt>BreakCriticalEdges</tt>, as described above), you can use the
1070 <tt>getAnalysisToUpdate</tt> method, which returns a pointer to the analysis if
1071 it is active. For example:</p>
1073 <div class="doc_code"><pre>
1075 if (DominatorSet *DS = getAnalysisToUpdate<DominatorSet>()) {
1076 <i>// A DominatorSet is active. This code will update it.</i>
1083 <!-- *********************************************************************** -->
1084 <div class="doc_section">
1085 <a name="analysisgroup">Implementing Analysis Groups</a>
1087 <!-- *********************************************************************** -->
1089 <div class="doc_text">
1091 <p>Now that we understand the basics of how passes are defined, how the are
1092 used, and how they are required from other passes, it's time to get a little bit
1093 fancier. All of the pass relationships that we have seen so far are very
1094 simple: one pass depends on one other specific pass to be run before it can run.
1095 For many applications, this is great, for others, more flexibility is
1098 <p>In particular, some analyses are defined such that there is a single simple
1099 interface to the analysis results, but multiple ways of calculating them.
1100 Consider alias analysis for example. The most trivial alias analysis returns
1101 "may alias" for any alias query. The most sophisticated analysis a
1102 flow-sensitive, context-sensitive interprocedural analysis that can take a
1103 significant amount of time to execute (and obviously, there is a lot of room
1104 between these two extremes for other implementations). To cleanly support
1105 situations like this, the LLVM Pass Infrastructure supports the notion of
1106 Analysis Groups.</p>
1110 <!-- _______________________________________________________________________ -->
1111 <div class="doc_subsubsection">
1112 <a name="agconcepts">Analysis Group Concepts</a>
1115 <div class="doc_text">
1117 <p>An Analysis Group is a single simple interface that may be implemented by
1118 multiple different passes. Analysis Groups can be given human readable names
1119 just like passes, but unlike passes, they need not derive from the <tt>Pass</tt>
1120 class. An analysis group may have one or more implementations, one of which is
1121 the "default" implementation.</p>
1123 <p>Analysis groups are used by client passes just like other passes are: the
1124 <tt>AnalysisUsage::addRequired()</tt> and <tt>Pass::getAnalysis()</tt> methods.
1125 In order to resolve this requirement, the <a href="#passmanager">PassManager</a>
1126 scans the available passes to see if any implementations of the analysis group
1127 are available. If none is available, the default implementation is created for
1128 the pass to use. All standard rules for <A href="#interaction">interaction
1129 between passes</a> still apply.</p>
1131 <p>Although <a href="#registration">Pass Registration</a> is optional for normal
1132 passes, all analysis group implementations must be registered, and must use the
1133 <A href="#registerag"><tt>RegisterAnalysisGroup</tt></a> template to join the
1134 implementation pool. Also, a default implementation of the interface
1135 <b>must</b> be registered with <A
1136 href="#registerag"><tt>RegisterAnalysisGroup</tt></a>.</p>
1138 <p>As a concrete example of an Analysis Group in action, consider the <a
1139 href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>
1140 analysis group. The default implementation of the alias analysis interface (the
1142 href="http://llvm.org/doxygen/structBasicAliasAnalysis.html">basicaa</a></tt>
1143 pass) just does a few simple checks that don't require significant analysis to
1144 compute (such as: two different globals can never alias each other, etc).
1145 Passes that use the <tt><a
1146 href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a></tt>
1147 interface (for example the <tt><a
1148 href="http://llvm.org/doxygen/structGCSE.html">gcse</a></tt> pass), do
1149 not care which implementation of alias analysis is actually provided, they just
1150 use the designated interface.</p>
1152 <p>From the user's perspective, commands work just like normal. Issuing the
1153 command '<tt>opt -gcse ...</tt>' will cause the <tt>basicaa</tt> class to be
1154 instantiated and added to the pass sequence. Issuing the command '<tt>opt
1155 -somefancyaa -gcse ...</tt>' will cause the <tt>gcse</tt> pass to use the
1156 <tt>somefancyaa</tt> alias analysis (which doesn't actually exist, it's just a
1157 hypothetical example) instead.</p>
1161 <!-- _______________________________________________________________________ -->
1162 <div class="doc_subsubsection">
1163 <a name="registerag">Using <tt>RegisterAnalysisGroup</tt></a>
1166 <div class="doc_text">
1168 <p>The <tt>RegisterAnalysisGroup</tt> template is used to register the analysis
1169 group itself as well as add pass implementations to the analysis group. First,
1170 an analysis should be registered, with a human readable name provided for it.
1171 Unlike registration of passes, there is no command line argument to be specified
1172 for the Analysis Group Interface itself, because it is "abstract":</p>
1174 <div class="doc_code"><pre>
1175 <b>static</b> RegisterAnalysisGroup<<a href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>> A("<i>Alias Analysis</i>");
1178 <p>Once the analysis is registered, passes can declare that they are valid
1179 implementations of the interface by using the following code:</p>
1181 <div class="doc_code"><pre>
1183 //<i> Analysis Group implementations <b>must</b> be registered normally...</i>
1184 RegisterOpt<FancyAA>
1185 B("<i>somefancyaa</i>", "<i>A more complex alias analysis implementation</i>");
1187 //<i> Declare that we implement the AliasAnalysis interface</i>
1188 RegisterAnalysisGroup<<a href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>, FancyAA> C;
1192 <p>This just shows a class <tt>FancyAA</tt> that is registered normally, then
1193 uses the <tt>RegisterAnalysisGroup</tt> template to "join" the <tt><a
1194 href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a></tt>
1195 analysis group. Every implementation of an analysis group should join using
1196 this template. A single pass may join multiple different analysis groups with
1199 <div class="doc_code"><pre>
1201 //<i> Analysis Group implementations <b>must</b> be registered normally...</i>
1202 RegisterOpt<<a href="http://llvm.org/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a>>
1203 D("<i>basicaa</i>", "<i>Basic Alias Analysis (default AA impl)</i>");
1205 //<i> Declare that we implement the AliasAnalysis interface</i>
1206 RegisterAnalysisGroup<<a href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>, <a href="http://llvm.org/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a>, <b>true</b>> E;
1210 <p>Here we show how the default implementation is specified (using the extra
1211 argument to the <tt>RegisterAnalysisGroup</tt> template). There must be exactly
1212 one default implementation available at all times for an Analysis Group to be
1213 used. Here we declare that the <tt><a
1214 href="http://llvm.org/doxygen/structBasicAliasAnalysis.html">BasicAliasAnalysis</a></tt>
1215 pass is the default implementation for the interface.</p>
1219 <!-- *********************************************************************** -->
1220 <div class="doc_section">
1221 <a name="passStatistics">Pass Statistics</a>
1223 <!-- *********************************************************************** -->
1225 <div class="doc_text">
1227 href="http://llvm.org/doxygen/Statistic_8h-source.html"><tt>Statistic</tt></a>
1228 class is designed to be an easy way to expose various success
1229 metrics from passes. These statistics are printed at the end of a
1230 run, when the -stats command line option is enabled on the command
1231 line. See the <a href="http://llvm.org/docs/ProgrammersManual.html#Statistic">Statistics section</a> in the Programmer's Manual for details.
1236 <!-- *********************************************************************** -->
1237 <div class="doc_section">
1238 <a name="passmanager">What PassManager does</a>
1240 <!-- *********************************************************************** -->
1242 <div class="doc_text">
1245 href="http://llvm.org/doxygen/PassManager_8h-source.html"><tt>PassManager</tt></a>
1247 href="http://llvm.org/doxygen/classllvm_1_1PassManager.html">class</a>
1248 takes a list of passes, ensures their <a href="#interaction">prerequisites</a>
1249 are set up correctly, and then schedules passes to run efficiently. All of the
1250 LLVM tools that run passes use the <tt>PassManager</tt> for execution of these
1253 <p>The <tt>PassManager</tt> does two main things to try to reduce the execution
1254 time of a series of passes:</p>
1257 <li><b>Share analysis results</b> - The PassManager attempts to avoid
1258 recomputing analysis results as much as possible. This means keeping track of
1259 which analyses are available already, which analyses get invalidated, and which
1260 analyses are needed to be run for a pass. An important part of work is that the
1261 <tt>PassManager</tt> tracks the exact lifetime of all analysis results, allowing
1262 it to <a href="#releaseMemory">free memory</a> allocated to holding analysis
1263 results as soon as they are no longer needed.</li>
1265 <li><b>Pipeline the execution of passes on the program</b> - The
1266 <tt>PassManager</tt> attempts to get better cache and memory usage behavior out
1267 of a series of passes by pipelining the passes together. This means that, given
1268 a series of consequtive <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s, it
1269 will execute all of the <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s on
1270 the first function, then all of the <a
1271 href="#FunctionPass"><tt>FunctionPass</tt></a>es on the second function,
1272 etc... until the entire program has been run through the passes.
1274 <p>This improves the cache behavior of the compiler, because it is only touching
1275 the LLVM program representation for a single function at a time, instead of
1276 traversing the entire program. It reduces the memory consumption of compiler,
1277 because, for example, only one <a
1278 href="http://llvm.org/doxygen/classllvm_1_1DominatorSet.html"><tt>DominatorSet</tt></a>
1279 needs to be calculated at a time. This also makes it possible some <a
1280 href="#SMP">interesting enhancements</a> in the future.</p></li>
1284 <p>The effectiveness of the <tt>PassManager</tt> is influenced directly by how
1285 much information it has about the behaviors of the passes it is scheduling. For
1286 example, the "preserved" set is intentionally conservative in the face of an
1287 unimplemented <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method.
1288 Not implementing when it should be implemented will have the effect of not
1289 allowing any analysis results to live across the execution of your pass.</p>
1291 <p>The <tt>PassManager</tt> class exposes a <tt>--debug-pass</tt> command line
1292 options that is useful for debugging pass execution, seeing how things work, and
1293 diagnosing when you should be preserving more analyses than you currently are
1294 (To get information about all of the variants of the <tt>--debug-pass</tt>
1295 option, just type '<tt>opt --help-hidden</tt>').</p>
1297 <p>By using the <tt>--debug-pass=Structure</tt> option, for example, we can see
1298 how our <a href="#basiccode">Hello World</a> pass interacts with other passes.
1299 Lets try it out with the <tt>gcse</tt> and <tt>licm</tt> passes:</p>
1301 <div class="doc_code"><pre>
1302 $ opt -load ../../../Debug/lib/Hello.so -gcse -licm --debug-pass=Structure < hello.bc > /dev/null
1304 Function Pass Manager
1305 Dominator Set Construction
1306 Immediate Dominators Construction
1307 Global Common Subexpression Elimination
1308 -- Immediate Dominators Construction
1309 -- Global Common Subexpression Elimination
1310 Natural Loop Construction
1311 Loop Invariant Code Motion
1312 -- Natural Loop Construction
1313 -- Loop Invariant Code Motion
1315 -- Dominator Set Construction
1321 <p>This output shows us when passes are constructed and when the analysis
1322 results are known to be dead (prefixed with '<tt>--</tt>'). Here we see that
1323 GCSE uses dominator and immediate dominator information to do its job. The LICM
1324 pass uses natural loop information, which uses dominator sets, but not immediate
1325 dominators. Because immediate dominators are no longer useful after the GCSE
1326 pass, it is immediately destroyed. The dominator sets are then reused to
1327 compute natural loop information, which is then used by the LICM pass.</p>
1329 <p>After the LICM pass, the module verifier runs (which is automatically added
1330 by the '<tt>opt</tt>' tool), which uses the dominator set to check that the
1331 resultant LLVM code is well formed. After it finishes, the dominator set
1332 information is destroyed, after being computed once, and shared by three
1335 <p>Lets see how this changes when we run the <a href="#basiccode">Hello
1336 World</a> pass in between the two passes:</p>
1338 <div class="doc_code"><pre>
1339 $ opt -load ../../../Debug/lib/Hello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null
1341 Function Pass Manager
1342 Dominator Set Construction
1343 Immediate Dominators Construction
1344 Global Common Subexpression Elimination
1345 <b>-- Dominator Set Construction</b>
1346 -- Immediate Dominators Construction
1347 -- Global Common Subexpression Elimination
1348 <b> Hello World Pass
1350 Dominator Set Construction</b>
1351 Natural Loop Construction
1352 Loop Invariant Code Motion
1353 -- Natural Loop Construction
1354 -- Loop Invariant Code Motion
1356 -- Dominator Set Construction
1365 <p>Here we see that the <a href="#basiccode">Hello World</a> pass has killed the
1366 Dominator Set pass, even though it doesn't modify the code at all! To fix this,
1367 we need to add the following <a
1368 href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method to our pass:</p>
1370 <div class="doc_code"><pre>
1371 <i>// We don't modify the program, so we preserve all analyses</i>
1372 <b>virtual void</b> getAnalysisUsage(AnalysisUsage &AU) <b>const</b> {
1373 AU.setPreservesAll();
1377 <p>Now when we run our pass, we get this output:</p>
1379 <div class="doc_code"><pre>
1380 $ opt -load ../../../Debug/lib/Hello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null
1381 Pass Arguments: -gcse -hello -licm
1383 Function Pass Manager
1384 Dominator Set Construction
1385 Immediate Dominators Construction
1386 Global Common Subexpression Elimination
1387 -- Immediate Dominators Construction
1388 -- Global Common Subexpression Elimination
1391 Natural Loop Construction
1392 Loop Invariant Code Motion
1393 -- Loop Invariant Code Motion
1394 -- Natural Loop Construction
1396 -- Dominator Set Construction
1405 <p>Which shows that we don't accidentally invalidate dominator information
1406 anymore, and therefore do not have to compute it twice.</p>
1410 <!-- _______________________________________________________________________ -->
1411 <div class="doc_subsubsection">
1412 <a name="releaseMemory">The <tt>releaseMemory</tt> method</a>
1415 <div class="doc_text">
1417 <div class="doc_code"><pre>
1418 <b>virtual void</b> releaseMemory();
1421 <p>The <tt>PassManager</tt> automatically determines when to compute analysis
1422 results, and how long to keep them around for. Because the lifetime of the pass
1423 object itself is effectively the entire duration of the compilation process, we
1424 need some way to free analysis results when they are no longer useful. The
1425 <tt>releaseMemory</tt> virtual method is the way to do this.</p>
1427 <p>If you are writing an analysis or any other pass that retains a significant
1428 amount of state (for use by another pass which "requires" your pass and uses the
1429 <a href="#getAnalysis">getAnalysis</a> method) you should implement
1430 <tt>releaseMEmory</tt> to, well, release the memory allocated to maintain this
1431 internal state. This method is called after the <tt>run*</tt> method for the
1432 class, before the next call of <tt>run*</tt> in your pass.</p>
1436 <!-- *********************************************************************** -->
1437 <div class="doc_section">
1438 <a name="registering">Registering dynamically loaded passes</a>
1440 <!-- *********************************************************************** -->
1442 <div class="doc_text">
1444 <p><i>Size matters</i> when constructing production quality tools using llvm,
1445 both for the purposes of distribution, and for regulating the resident code size
1446 when running on the target system. Therefore, it becomes desirable to
1447 selectively use some passes, while omitting others and maintain the flexibility
1448 to change configurations later on. You want to be able to do all this, and,
1449 provide feedback to the user. This is where pass registration comes into
1452 <p>The fundamental mechanisms for pass registration are the
1453 <tt>MachinePassRegistry</tt> class and subclasses of
1454 <tt>MachinePassRegistryNode</tt>.</p>
1456 <p>An instance of <tt>MachinePassRegistry</tt> is used to maintain a list of
1457 <tt>MachinePassRegistryNode</tt> objects. This instance maintains the list and
1458 communicates additions and deletions to the command line interface.</p>
1460 <p>An instance of <tt>MachinePassRegistryNode</tt> subclass is used to maintain
1461 information provided about a particular pass. This information includes the
1462 command line name, the command help string and the address of the function used
1463 to create an instance of the pass. A global static constructor of one of these
1464 instances <i>registers</i> with a corresponding <tt>MachinePassRegistry</tt>,
1465 the static destructor <i>unregisters</i>. Thus a pass that is statically linked
1466 in the tool will be registered at start up. A dynamically loaded pass will
1467 register on load and unregister at unload.</p>
1471 <!-- _______________________________________________________________________ -->
1472 <div class="doc_subsection">
1473 <a name="registering_existing">Using existing registries</a>
1476 <div class="doc_text">
1478 <p>There are predefined registries to track instruction scheduling
1479 (<tt>RegisterScheduler</tt>) and register allocation (<tt>RegisterRegAlloc</tt>)
1480 machine passes. Here we will describe how to <i>register</i> a register
1481 allocator machine pass.</p>
1483 <p>Implement your register allocator machine pass. In your register allocator
1484 .cpp file add the following include;</p>
1486 <div class="doc_code"><pre>
1487 #include ""llvm/CodeGen/RegAllocRegistry.h""
1490 <p>Also in your register allocator .cpp file, define a creator function in the
1493 <div class="doc_code"><pre>
1494 FunctionPass *createMyRegisterAllocator() {
1495 return new MyRegisterAllocator();
1499 <p>Note that the signature of this function should match the type of
1500 <tt>RegisterRegAlloc::FunctionPassCtor</tt>. In the same file add the
1501 "installing" declaration, in the form;</p>
1503 <div class="doc_code"><pre>
1504 static RegisterRegAlloc myRegAlloc("myregalloc",
1505 " my register allocator help string",
1506 createMyRegisterAllocator);
1509 <p>Note the two spaces prior to the help string produces a tidy result on the
1512 <div class="doc_code"><pre>
1515 -regalloc - Register allocator to use: (default = linearscan)
1516 =linearscan - linear scan register allocator
1517 =local - local register allocator
1518 =simple - simple register allocator
1519 =myregalloc - my register allocator help string
1523 <p>And that's it. The user is now free to use <tt>-regalloc=myregalloc</tt> as
1524 an option. Registering instruction schedulers is similar except use the
1525 <tt>RegisterRegAlloc</tt> class. Note that the
1526 <tt>RegisterRegAlloc::FunctionPassCtor</tt> is significantly different from
1527 <tt>RegisterRegAlloc::FunctionPassCtor</tt>.</p>
1529 <p>To force the load/linking of your register allocator into the llc/lli tools,
1530 add your creator function's global declaration to "Passes.h" and add a "pseudo"
1531 call line to <tt>llvm/Codegen/LinkAllCodegenComponents.h</tt>.</p>
1536 <!-- _______________________________________________________________________ -->
1537 <div class="doc_subsection">
1538 <a name="registering_new">Creating new registries</a>
1541 <div class="doc_text">
1543 <p>The easiest way to get started is to clone one of the existing registries; we
1544 recommend <tt>llvm/CodeGen/RegAllocRegistry.h</tt>. The key things to modify
1545 are the class name and the <tt>FunctionPassCtor</tt> type.</p>
1547 <p>Then you need to declare the registry. Example: if your pass registry is
1548 <tt>RegisterMyPasses</tt> then define;</p>
1550 <div class="doc_code"><pre>
1551 MachinePassRegistry RegisterMyPasses::Registry;
1554 <p>And finally, declare the command line option for your passes. Example:</p>
1556 <div class="doc_code"><pre>
1557 cl::opt<RegisterMyPasses::FunctionPassCtor, false,
1558 RegisterPassParser<RegisterMyPasses> >
1560 cl::init(&createDefaultMyPass),
1561 cl::desc("my pass option help"));
1564 <p>Here the command option is "mypass", with createDefaultMyPass as the default
1569 <!-- *********************************************************************** -->
1570 <div class="doc_section">
1571 <a name="debughints">Using GDB with dynamically loaded passes</a>
1573 <!-- *********************************************************************** -->
1575 <div class="doc_text">
1577 <p>Unfortunately, using GDB with dynamically loaded passes is not as easy as it
1578 should be. First of all, you can't set a breakpoint in a shared object that has
1579 not been loaded yet, and second of all there are problems with inlined functions
1580 in shared objects. Here are some suggestions to debugging your pass with
1583 <p>For sake of discussion, I'm going to assume that you are debugging a
1584 transformation invoked by <tt>opt</tt>, although nothing described here depends
1589 <!-- _______________________________________________________________________ -->
1590 <div class="doc_subsubsection">
1591 <a name="breakpoint">Setting a breakpoint in your pass</a>
1594 <div class="doc_text">
1596 <p>First thing you do is start <tt>gdb</tt> on the <tt>opt</tt> process:</p>
1598 <div class="doc_code"><pre>
1601 Copyright 2000 Free Software Foundation, Inc.
1602 GDB is free software, covered by the GNU General Public License, and you are
1603 welcome to change it and/or distribute copies of it under certain conditions.
1604 Type "show copying" to see the conditions.
1605 There is absolutely no warranty for GDB. Type "show warranty" for details.
1606 This GDB was configured as "sparc-sun-solaris2.6"...
1610 <p>Note that <tt>opt</tt> has a lot of debugging information in it, so it takes
1611 time to load. Be patient. Since we cannot set a breakpoint in our pass yet
1612 (the shared object isn't loaded until runtime), we must execute the process, and
1613 have it stop before it invokes our pass, but after it has loaded the shared
1614 object. The most foolproof way of doing this is to set a breakpoint in
1615 <tt>PassManager::run</tt> and then run the process with the arguments you
1618 <div class="doc_code"><pre>
1619 (gdb) <b>break PassManager::run</b>
1620 Breakpoint 1 at 0x2413bc: file Pass.cpp, line 70.
1621 (gdb) <b>run test.bc -load $(LLVMTOP)/llvm/Debug/lib/[libname].so -[passoption]</b>
1622 Starting program: opt test.bc -load $(LLVMTOP)/llvm/Debug/lib/[libname].so -[passoption]
1623 Breakpoint 1, PassManager::run (this=0xffbef174, M=@0x70b298) at Pass.cpp:70
1624 70 bool PassManager::run(Module &M) { return PM->run(M); }
1628 <p>Once the <tt>opt</tt> stops in the <tt>PassManager::run</tt> method you are
1629 now free to set breakpoints in your pass so that you can trace through execution
1630 or do other standard debugging stuff.</p>
1634 <!-- _______________________________________________________________________ -->
1635 <div class="doc_subsubsection">
1636 <a name="debugmisc">Miscellaneous Problems</a>
1639 <div class="doc_text">
1641 <p>Once you have the basics down, there are a couple of problems that GDB has,
1642 some with solutions, some without.</p>
1645 <li>Inline functions have bogus stack information. In general, GDB does a
1646 pretty good job getting stack traces and stepping through inline functions.
1647 When a pass is dynamically loaded however, it somehow completely loses this
1648 capability. The only solution I know of is to de-inline a function (move it
1649 from the body of a class to a .cpp file).</li>
1651 <li>Restarting the program breaks breakpoints. After following the information
1652 above, you have succeeded in getting some breakpoints planted in your pass. Nex
1653 thing you know, you restart the program (i.e., you type '<tt>run</tt>' again),
1654 and you start getting errors about breakpoints being unsettable. The only way I
1655 have found to "fix" this problem is to <tt>delete</tt> the breakpoints that are
1656 already set in your pass, run the program, and re-set the breakpoints once
1657 execution stops in <tt>PassManager::run</tt>.</li>
1661 <p>Hopefully these tips will help with common case debugging situations. If
1662 you'd like to contribute some tips of your own, just contact <a
1663 href="mailto:sabre@nondot.org">Chris</a>.</p>
1667 <!-- *********************************************************************** -->
1668 <div class="doc_section">
1669 <a name="future">Future extensions planned</a>
1671 <!-- *********************************************************************** -->
1673 <div class="doc_text">
1675 <p>Although the LLVM Pass Infrastructure is very capable as it stands, and does
1676 some nifty stuff, there are things we'd like to add in the future. Here is
1677 where we are going:</p>
1681 <!-- _______________________________________________________________________ -->
1682 <div class="doc_subsubsection">
1683 <a name="SMP">Multithreaded LLVM</a>
1686 <div class="doc_text">
1688 <p>Multiple CPU machines are becoming more common and compilation can never be
1689 fast enough: obviously we should allow for a multithreaded compiler. Because of
1690 the semantics defined for passes above (specifically they cannot maintain state
1691 across invocations of their <tt>run*</tt> methods), a nice clean way to
1692 implement a multithreaded compiler would be for the <tt>PassManager</tt> class
1693 to create multiple instances of each pass object, and allow the separate
1694 instances to be hacking on different parts of the program at the same time.</p>
1696 <p>This implementation would prevent each of the passes from having to implement
1697 multithreaded constructs, requiring only the LLVM core to have locking in a few
1698 places (for global resources). Although this is a simple extension, we simply
1699 haven't had time (or multiprocessor machines, thus a reason) to implement this.
1700 Despite that, we have kept the LLVM passes SMP ready, and you should too.</p>
1704 <!-- _______________________________________________________________________ -->
1705 <div class="doc_subsubsection">
1706 <a name="PassFunctionPass"><tt>ModulePass</tt>es requiring <tt>FunctionPass</tt>es</a>
1709 <div class="doc_text">
1711 <p>Currently it is illegal for a <a href="#ModulePass"><tt>ModulePass</tt></a>
1712 to require a <a href="#FunctionPass"><tt>FunctionPass</tt></a>. This is because
1713 there is only one instance of the <a
1714 href="#FunctionPass"><tt>FunctionPass</tt></a> object ever created, thus nowhere
1715 to store information for all of the functions in the program at the same time.
1716 Although this has come up a couple of times before, this has always been worked
1717 around by factoring one big complicated pass into a global and an
1718 interprocedural part, both of which are distinct. In the future, it would be
1719 nice to have this though.</p>
1721 <p>Note that it is no problem for a <a
1722 href="#FunctionPass"><tt>FunctionPass</tt></a> to require the results of a <a
1723 href="#ModulePass"><tt>ModulePass</tt></a>, only the other way around.</p>
1727 <!-- *********************************************************************** -->
1730 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1731 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1732 <a href="http://validator.w3.org/check/referer"><img
1733 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
1735 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1736 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1737 Last modified: $Date$