Blame - docs/WritingAnLLVMPass.html - fp2-dev/platform/external/llvm

blob: 3cef2c934482485586b113e27b6416bc2f288734 [file] [log] [blame]

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