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

blob: c80fd848c50b965d34b30ce0b8a2e312d13096cc [file] [log] [blame]

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