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