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

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