Blame - llvm/docs/WritingAnLLVMPass.html - toolchain/llvm-project

blob: 9f5dff4d31deb32e00f126274ba6514ae5a602de [file] [log] [blame]

Chris Lattner	34ceebe	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
				4	<!--
				5	I. General Structure of an LLVM Program
				6
				7	I.1 "What is a 'Value'?": Value & User class
				8	I.2 Type & Derived Types
				9	I.3 GlobalVariable, Function
				10	I.4 BasicBlock
				11	I.5 Instruction & Subclasses
				12	1.6 Argument
				13	1.7 Constants
				14
				15	III. Useful things to know about the LLVM source base:
				16
				17	III.1 Useful links that introduce the STL
				18	III.2 isa<>, cast<>, dyn_cast<>
				19	III.3 Makefiles, useful options
				20	III.4 How to use opt & analyze to debug stuff
				21	III.5 How to write a regression test
				22	III.6 DEBUG() and Statistics (-debug & -stats)
				23	III.7 The -time-passes option
				24	III.8 ... more as needed ...
				25
				26	I think that writing Section #1 would be very helpful and that's the most
				27	stable portion of the sourcebase. #3 can be started on, but will probably
				28	just grow as time goes on. I'd like to do Section #2 once I finish some
				29	changes up that effect it.
				30
				31	-->
				32
				33	<body bgcolor=white>
				34
				35	<table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
				36	<tr><td>  <font size=+3 color="#EEEEFF" face="Georgia,Palatino,Times,Roman"><b>Writing an LLVM Pass</b></font></td>
				37	</tr></table>
				38
				39
				40	<ol>
				41	<li><a href="#introduction">Introduction - What is a pass?</a>
				42	<li><a href="#quickstart">Quick Start - Writing hello world</a>
				43	<ul>
				44	<li><a href="#makefile">Setting up the build environment</a>
				45	<li><a href="#basiccode">Basic code required</a>
				46	<li><a href="#running">Running a pass with <tt>opt</tt>
				47	or <tt>analyze</tt></a>
				48	</ul>
				49	<li><a href="#passtype">Pass classes and requirements</a>
				50	<ul>
				51	<li><a href="#Pass">The <tt>Pass</tt> class</a>
				52	<ul>
				53	<li><a href="#run">The <tt>run</tt> method</a>
				54	</ul>
				55	<li><a href="#FunctionPass">The <tt>FunctionPass</tt> class</a>
				56	<ul>
				57	<li><a href="#doInitialization">The <tt>doInitialization</tt> method</a>
				58	<li><a href="#runOnFunction">The <tt>runOnFunction</tt> method</a>
				59	<li><a href="#doFinalization">The <tt>doFinalization</tt> method</a>
				60	</ul>
				61	<li><a href="#BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
				62	<ul>
				63	<li><a href="#runOnBasicBlock">The <tt>runOnBasicBlock</tt> method</a>
				64	</ul>
				65	</ul>
				66	<li><a href="#registration">Pass Registration</a>
				67	<ul>
				68	<li><a href="#print">The <tt>print</tt> method</a>
				69	</ul>
				70	<li><a href="#interaction">Specifying interactions between passes</a>
				71	<ul>
				72	<li><a href="#getAnalysisUsage">The <tt>getAnalysisUsage</tt> method</a>
				73	<li><a href="#getAnalysis">The <tt>getAnalysis</tt> method</a>
				74	</ul>
				75	<li><a href="#passmanager">What PassManager does</a>
				76	<ul>
				77	<li><a href="#releaseMemory">The <tt>releaseMemory</tt> method</a>
				78	</ul>
				79	<li><a href="#future">Future extensions planned</a>
				80	<ul>
				81	<li><a href="#SMP">Multithreaded LLVM</a>
				82	<li><a href="#ModuleSource">A new <tt>ModuleSource</tt> interface</a>
				83	<li><a href="#PassFunctionPass"><tt>Pass</tt>'s requiring <tt>FunctionPass</tt>'s</a>
				84	</ul>
				85	</ol><p>
				86
				87
				88
				89	<!-- *********************************************************************** -->
				90	<table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
				91	<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
				92	<a name="introduction">Introduction - What is a pass?
				93	</b></font></td></tr></table><ul>
				94	<!-- *********************************************************************** -->
				95
				96	The LLVM Pass Framework is an important part of the LLVM system, because LLVM
				97	passes are where the interesting parts of the compiler exist. Passes perform
				98	the transformations and optimizations that make up the compiler, they build
				99	the analysis results that are used by these transformations, and they are, above
				100	all, a structuring technique for compiler code.<p>
				101
				102	All LLVM passes are subclasses of the <tt><a
				103	href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt> class, which
				104	implement functionality by overriding virtual methods inherited from
				105	<tt>Pass</tt>. Depending on how your pass works, you may be able to inherit
				106	from the <tt><a
				107	href="http://llvm.cs.uiuc.edu/doxygen/structFunctionPass.html">FunctionPass</a></tt>
				108	or <tt><a
				109	href="http://llvm.cs.uiuc.edu/doxygen/structBasicBlockPass.html">BasicBlockPass</a></tt>,
				110	which gives the system more information about what your pass does, and how it
				111	can be combined with other passes. One of the main features of the LLVM Pass
				112	Framework is that it schedules passes to run in an efficient way based on the
				113	constraints that your pass has.<p>
				114
				115	We start by showing you how to construct a pass, everything from setting up the
				116	code, to compiling, loading, and executing it. After the basics are down, more
				117	advanced features are discussed.<p>
				118
				119
				120	<!-- *********************************************************************** -->
				121	</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
				122	<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
				123	<a name="quickstart">Quick Start - Writing hello world
				124	</b></font></td></tr></table><ul>
				125	<!-- *********************************************************************** -->
				126
				127	Here we describe how to write the "hello world" of passes. The "Hello" pass is
				128	designed to simply print out the name of non-external functions that exist in
				129	the program being compiled. It does not modify the program at all, just
				130	inspects it. The source code and files for this pass are available in the LLVM
				131	source tree in the <tt>lib/Transforms/Hello</tt> directory.<p>
				132
				133
				134	<!-- ======================================================================= -->
				135	</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
				136	<tr><td> </td><td width="100%">
				137	<font color="#EEEEFF" face="Georgia,Palatino"><b>
				138	<a name="makefile">Setting up the build environment
				139	</b></font></td></tr></table><ul>
				140
				141	First thing you need to do is create a new directory somewhere in the LLVM
				142	source base. For this example, we'll assume that you made
				143	"<tt>lib/Transforms/Hello</tt>". The first thing you must do is set up a build
				144	script (Makefile) that will compile the source code for the new pass. To do
				145	this, copy this into "<tt>Makefile</tt>":<p>
				146
				147	</ul><hr><ul><pre>
				148	# Makefile for hello pass
				149	LEVEL = ../../.. # Path to top level of LLVM heirarchy
				150	LIBRARYNAME = hello # Name of the library to build
				151	SHARED_LIBRARY = 1 # Build a dynamically loadable shared object
				152
				153	include $(LEVEL)/Makefile.common # Include the makefile implementation stuff
				154	</pre></ul><hr><ul><p>
				155
				156	This makefile specifies that all of the <tt>.cpp</tt> files in the current
				157	directory are to be compiled and linked together into a
				158	<tt>lib/Debug/libhello.so</tt> shared object that can be dynamically loaded by
				159	the <tt>opt</tt> or <tt>analyze</tt> tools.<p>
				160
				161	Now that we have the build scripts set up, we just need to write the code for
				162	the pass itself.<p>
				163
				164
				165	<!-- ======================================================================= -->
				166	</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
				167	<tr><td> </td><td width="100%">
				168	<font color="#EEEEFF" face="Georgia,Palatino"><b>
				169	<a name="basiccode">Basic code required
				170	</b></font></td></tr></table><ul>
				171
				172	Now that we have a way to compile our new pass, we just have to write it. Start
				173	out with:<p>
				174
				175	<pre>
				176	<b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
				177	<b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Function_8h-source.html">llvm/Function.h</a>"
				178	</pre>
				179
				180	Which are needed because we are writing a <tt><a
				181	href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt>, and we are
				182	operating on <tt><a
				183	href="http://llvm.cs.uiuc.edu/doxygen/classFunction.html">Function</a></tt>'s.<p>
				184
				185	Next we have:<p>
				186
				187	<pre>
				188	<b>namespace</b> {
				189	</pre><p>
				190
				191	... which starts out an anonymous namespace. Anonymous namespaces are to C++
				192	what the "<tt>static</tt>" keyword is to C (at global scope). It makes the
				193	things declared inside of the anonymous namespace only visible to the current
				194	file. If you're not familiar with them, consult a decent C++ book for more
				195	information.<p>
				196
				197	Next, we declare our pass itself:<p>
				198
				199	<pre>
				200	<b>struct</b> Hello : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
				201	</pre><p>
				202
				203	This declares a "<tt>Hello</tt>" class that is a subclass of <tt><a
				204	href="http://llvm.cs.uiuc.edu/doxygen/structFunctionPass.html">FunctionPass</a></tt>.
				205	The different builting pass subclasses are described in detail <a
				206	href="#passtype">later</a>, but for now, know that <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s
				207	operate a function at a time.<p>
				208
				209	<pre>
				210	<b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &F) {
				211	std::cerr << "<i>Hello: </i>" << F.getName() << "\n";
				212	<b>return false</b>;
				213	}
				214	}; <i>// end of struct Hello</i>
				215	</pre>
				216
				217	We declare a "<a href="#runOnFunction"><tt>runOnFunction</tt></a>" method, which
				218	overloads an abstract virtual method inherited from <a
				219	href="#FunctionPass"><tt>FunctionPass</tt></a>. This is where we are supposed
				220	to do our thing, so we just print out our message with the name of each
				221	function.<p>
				222
				223	<pre>
				224	RegisterOpt<Hello> X("<i>hello</i>", "<i>Hello World Pass</i>");
				225	} <i>// end of anonymous namespace</i>
				226	</pre><p>
				227
				228	Lastly, we register our class <tt>Hello</tt>, giving it a command line argument
				229	"<tt>hello</tt>", and a name "<tt>Hello World Pass</tt>". There are several
				230	different ways of <a href="#registration">registering your pass</a>, depending
				231	on what it is to be used for. For "optimizations" we use the
				232	<tt>RegisterOpt</tt> template.<p>
				233
				234	As a whole, the <tt>.cpp</tt> file looks like:<p>
				235
				236	<pre>
				237	<b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Pass_8h-source.html">llvm/Pass.h</a>"
				238	<b>#include</b> "<a href="http://llvm.cs.uiuc.edu/doxygen/Function_8h-source.html">llvm/Function.h</a>"
				239
				240	<b>namespace</b> {
				241	<b>struct Hello</b> : <b>public</b> <a href="#FunctionPass">FunctionPass</a> {
				242	<b>virtual bool</b> <a href="#runOnFunction">runOnFunction</a>(Function &F) {
				243	std::cerr << "<i>Hello: </i>" << F.getName() << "\n";
				244	<b>return false</b>;
				245	}
				246	};
				247
				248	RegisterOpt<Hello> X("<i>hello</i>", "<i>Hello World Pass</i>");
				249	}
				250	</pre><p>
				251
				252	Now that it's all together, compile the file with a simple "<tt>gmake</tt>"
				253	command in the local directory and you should get a new
				254	"<tt>lib/Debug/libhello.so</tt> file. Note that everything in this file is
				255	contained in an anonymous namespace: this reflects the fact that passes are self
				256	contained units that do not need external interfaces (although they can have
				257	them) to be useful.<p>
				258
				259
				260	<!-- ======================================================================= -->
				261	</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
				262	<tr><td> </td><td width="100%">
				263	<font color="#EEEEFF" face="Georgia,Palatino"><b>
				264	<a name="running">Running a pass with <tt>opt</tt> or <tt>analyze</tt>
				265	</b></font></td></tr></table><ul>
				266
				267	Now that you have a brand new shiny <tt>.so</tt> file, we can use the
				268	<tt>opt</tt> command to run an LLVM program through your pass. Because you
				269	registered your pass with the <tt>RegisterOpt</tt> template, you will be able to
				270	use the <tt>opt</tt> tool to access it, once loaded.<p>
				271
				272	To test it, follow the example at the end of the <a
				273	href="GettingStarted.html">Getting Started Guide</a> to compile "Hello World" to
				274	LLVM. We can now run the bytecode file (<tt>hello.bc</tt>) for the program
				275	through our transformation like this (or course, any bytecode file will
				276	work):<p>
				277
				278	<pre>
				279	$ opt -load ../../../lib/Debug/libhello.so -hello < hello.bc > /dev/null
				280	Hello: __main
				281	Hello: puts
				282	Hello: main
				283	</pre><p>
				284
				285	The '<tt>-load</tt>' option specifies that '<tt>opt</tt>' should load your pass
				286	as a shared object, which makes '<tt>-hello</tt>' a valid command line argument
				287	(which is one reason you need to <a href="#registration">register your
				288	pass</a>). Because the hello pass does not modify the program in any
				289	interesting way, we just throw away the result of <tt>opt</tt> (sending it to
				290	<tt>/dev/null</tt>).<p>
				291
				292	To see what happened to the other string you registered, try running
				293	<tt>opt</tt> with the <tt>--help</tt> option:<p>
				294
				295	<pre>
				296	$ opt -load ../../../lib/Debug/libhello.so --help
				297	OVERVIEW: llvm .bc -> .bc modular optimizer
				298
				299	USAGE: opt [options] <input bytecode>
				300
				301	OPTIONS:
				302	Optimizations available:
				303	...
				304	-funcresolve - Resolve Functions
				305	-gcse - Global Common Subexpression Elimination
				306	-globaldce - Dead Global Elimination
				307	<b>-hello - Hello World Pass</b>
				308	-indvars - Cannonicalize Induction Variables
				309	-inline - Function Integration/Inlining
				310	-instcombine - Combine redundant instructions
				311	...
				312	</pre><p>
				313
				314	The pass name get added as the information string for your pass, giving some
				315	documentation to users of <tt>opt</tt>. Now that you have a working pass, you
				316	would go ahead and make it do the cool transformations you want. Once you get
				317	it all working and tested, it may become useful to find out how fast your pass
				318	is. The <a href="#passManager"><tt>PassManager</tt></a> provides a nice command
				319	line option (<tt>--time-passes</tt>) that allows you to get information about
				320	the execution time of your pass along with the other passes you queue up. For
				321	example:<p>
				322
				323	<pre>
				324	$ opt -load ../../../lib/Debug/libhello.so -hello -time-passes < hello.bc > /dev/null
				325	Hello: __main
				326	Hello: puts
				327	Hello: main
				328	===============================================================================
				329	... Pass execution timing report ...
				330	===============================================================================
				331	Total Execution Time: 0.02 seconds (0.0479059 wall clock)
				332
				333	---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Pass Name ---
				334	0.0100 (100.0%) 0.0000 ( 0.0%) 0.0100 ( 50.0%) 0.0402 ( 84.0%) Bytecode Writer
				335	0.0000 ( 0.0%) 0.0100 (100.0%) 0.0100 ( 50.0%) 0.0031 ( 6.4%) Dominator Set Construction
				336	0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0013 ( 2.7%) Module Verifier
				337	<b> 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0033 ( 6.9%) Hello World Pass</b>
				338	0.0100 (100.0%) 0.0100 (100.0%) 0.0200 (100.0%) 0.0479 (100.0%) TOTAL
				339	</pre><p>
				340
				341	As you can see, our implementation above is pretty fast :). The additional
				342	passes listed are automatically inserted by the '<tt>opt</tt>' tool to verify
				343	that the LLVM emitted by your pass is still valid and well formed LLVM, which
				344	hasn't been broken somehow.
				345
				346	Now that you have seen the basics of the mechanics behind passes, we can talk
				347	about some more details of how they work and how to use them.<p>
				348
				349
				350
				351	<!-- *********************************************************************** -->
				352	</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
				353	<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
				354	<a name="passtype">Pass classes and requirements
				355	</b></font></td></tr></table><ul>
				356	<!-- *********************************************************************** -->
				357
				358	One of the first things that you should do when designing a new pass is to
				359	decide what class you should subclass for your pass. The <a
				360	href="#basiccode">Hello World</a> example uses the <tt><a
				361	href="#FunctionPass">FunctionPass</a></tt> class for its implementation, but we
				362	did not discuss why or when this should occur. Here we talk about the classes
				363	available, from the most general to the most specific.<p>
				364
				365	When choosing a superclass for your Pass, you should choose the most specific
				366	class possible, while still being able to meet the requirements listed. This
				367	gives the LLVM Pass Infrastructure information neccesary to optimize how passes
				368	are run, so that the resultant compiler isn't unneccesarily slow.<p>
				369
				370
				371
				372	<!-- ======================================================================= -->
				373	</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
				374	<tr><td> </td><td width="100%">
				375	<font color="#EEEEFF" face="Georgia,Palatino"><b>
				376	<a name="Pass">The <tt>Pass</tt> class
				377	</b></font></td></tr></table><ul>
				378
				379	The "<tt><a href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">Pass</a></tt>"
				380	class is the most general of all superclasses that you can use. Deriving from
				381	<tt>Pass</tt> indicates that your pass uses the entire program as a unit,
				382	refering to function bodies in no predictable order, or adding and removing
				383	functions. Because nothing is known about the behavior of direct <tt>Pass</tt>
				384	subclasses, no optimization can be done for their execution.<p>
				385
				386	To write a correct <tt>Pass</tt> subclass, derive from <tt>Pass</tt> and
				387	overload the <tt>run</tt> method with the following signature:<p>
				388
				389	<!-- _______________________________________________________________________ -->
				390	</ul><h4><a name="run"><hr size=0>The <tt>run</tt> method</h4><ul>
				391
				392
				393	<pre>
				394	<b>virtual bool</b> run(Module &M) = 0;
				395	</pre><p>
				396
				397	The <tt>run</tt> method performs the interesting work of the pass, and should
				398	return true if the module was modified by the transformation, false
				399	otherwise.<p>
				400
				401
				402
				403	<!-- ======================================================================= -->
				404	</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
				405	<tr><td> </td><td width="100%">
				406	<font color="#EEEEFF" face="Georgia,Palatino"><b>
				407	<a name="FunctionPass">The <tt>FunctionPass</tt> class
				408	</b></font></td></tr></table><ul>
				409
				410	In contrast to direct <tt>Pass</tt> subclasses, direct <tt><a
				411	href="http://llvm.cs.uiuc.edu/doxygen/classPass.html">FunctionPass</a></tt>
				412	subclasses do have a predictable, local behavior that can be expected by the
				413	system. All <tt>FunctionPass</tt> execute on each function in the program
				414	independant of all of the other functions in the program.
				415	<tt>FunctionPass</tt>'s do not require that they are executed in a particular
				416	order, and <tt>FunctionPass</tt>'s do not modify external functions.<p>
				417
				418	To be explicit, <tt>FunctionPass</tt> subclasses are not allowed to:<p>
				419
				420	<ol>
				421	<li>Modify a Function other than the one currently being processed.
				422	<li>Add or remove Function's from the current Module.
				423	<li>Add or remove global variables from the current Module.
				424	<li>Maintain state across invocations of
				425	<a href="#runOnFunction"><tt>runOnFunction</tt></a> (including global data)
				426	</ol><p>
				427
				428	Implementing a <tt>FunctionPass</tt> is usually straightforward (See the <a
				429	href="#basiccode">Hello World</a> pass for example). <tt>FunctionPass</tt>'s
				430	may overload three virtual methods to do their work. All of these methods
				431	should return true if they modified the program, or false if they didn't.<p>
				432
				433	<!-- _______________________________________________________________________ -->
				434	</ul><h4><a name="doInitialization"><hr size=0>The <tt>doInitialization</tt>
				435	method</h4><ul>
				436
				437	<pre>
				438	<b>virtual bool</b> doInitialization(Module &M);
				439	</pre><p>
				440
				441	The <tt>doIninitialize</tt> method is allowed to do most of the things that
				442	<tt>FunctionPass</tt>'s are not allowed to do. They can add and remove
				443	functions, get pointers to functions, etc. The <tt>doInitialize</tt> method is
				444	designed to do simple initialization type of stuff that does not depend on the
				445	functions being processed. The <tt>doInitialization</tt> function call is not
				446	scheduled to overlap with any other pass executions.<p>
				447
				448	A good example of how this method should be used is the <a
				449	href="http://llvm.cs.uiuc.edu/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations</a>
				450	pass. This pass converts <tt>malloc</tt> and <tt>free</tt> instructions into
				451	platform dependant <tt>malloc()</tt> and <tt>free()</tt> function calls. It
				452	uses the <tt>doInitialization</tt> method to get a reference to the malloc and
				453	free functions that it needs, adding prototypes to the module if neccesary.<p>
				454
				455	<!-- _______________________________________________________________________ -->
				456	</ul><h4><a name="runOnFunction"><hr size=0>The <tt>runOnFunction</tt> method</h4><ul>
				457
				458	<pre>
				459	<b>virtual bool</b> runOnFunction(Function &F) = 0;
				460	</pre><p>
				461
				462	The <tt>runOnFunction</tt> method must be implemented by your subclass to do the
				463	transformation or analysis work of your pass. As usual, a true value should be
				464	returned if the function is modified.<p>
				465
				466	<!-- _______________________________________________________________________ -->
				467	</ul><h4><a name="doFinalization"><hr size=0>The <tt>doFinalization</tt> method</h4><ul>
				468
				469	<pre>
				470	<b>virtual bool</b> doFinalization(Module &M);
				471	</pre</p>
				472
				473	The <tt>doFinalization</tt> method is an infrequently used method that is called
				474	when the pass framework has finished calling <a
				475	href="#runOnFunction"><tt>runOnFunction</tt></a> for every function in the
				476	program being compiled.<p>
				477
				478
				479
				480	<!-- ======================================================================= -->
				481	</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
				482	<tr><td> </td><td width="100%">
				483	<font color="#EEEEFF" face="Georgia,Palatino"><b>
				484	<a name="BasicBlockPass">The <tt>BasicBlockPass</tt> class</a>
				485	</b></font></td></tr></table><ul>
				486
				487	<tt>BasicBlockPass</tt>'s are just like <a
				488	href="#FunctionPass"><tt>FunctionPass</tt></a>'s, except that they must limit
				489	their scope of inspection and modification to a single basic block at a time.
				490	As such, they are <b>not</b> allowed to do any of the following:<p>
				491
				492	<ol>
				493	<li>Modify or inspect any basic blocks outside of the current one
				494	<li>Maintain state across invocations of
				495	<a href="#runOnBasicBlock"><tt>runOnBasicBlock</tt></a>
				496	<li>Modify the constrol flow graph (by altering terminator instructions)
				497	<li>Any of the things verboten for
				498	<a href="#FunctionPass"><tt>FunctionPass</tt></a>'s.
				499	</ol><p>
				500
				501	<tt>BasicBlockPass</tt>'s are useful for traditional local and "peephole"
				502	optimizations. They may override the same <a
				503	href="#doInitialization"><tt>doInitialization</tt></a> and <a
				504	href="#doFinalization"><tt>doFinalization</tt></a> methods that <a
				505	href="#FunctionPass"><tt>FunctionPass</tt></a>'s have, but also have a
				506	<tt>runOnBasicBlock</tt> method:<p>
				507
				508	<!-- _______________________________________________________________________ -->
				509	</ul><h4><a name="runOnBasicBlock"><hr size=0>The <tt>runOnBasicBlock</tt> method</h4><ul>
				510
				511	<pre>
				512	<b>virtual bool</b> runOnBasicBlock(BasicBlock &BB) = 0;
				513	</pre><p>
				514
				515	Override this function to do the work of the <tt>BasicBlockPass</tt>. This
				516	function is not allowed to inspect or modify basic blocks other than the
				517	parameter, and are not allowed to modify the CFG. A true value must be returned
				518	if the basic block is modified.<p>
				519
				520
				521	<!-- *********************************************************************** -->
				522	</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
				523	<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
				524	<a name="registration">Pass registration
				525	</b></font></td></tr></table><ul>
				526	<!-- *********************************************************************** -->
				527
				528	In the <a href="#basiccode">Hello World</a> example pass we illustrated how pass
				529	registration works, and discussed some of the reasons that it is used and what
				530	it does. Here we discuss how and why passes are registered.<p>
				531
				532	Passes can be registered in several different ways. Depending on the general
				533	classification of the pass, you should use one of the following templates to
				534	register the pass:<p>
				535
				536	<ul>
				537	<li><b><tt>RegisterOpt</tt></b> - This template should be used when you are
				538	registering a pass that logically should be available for use in the
				539	'<tt>opt</tt>' utility.<p>
				540
				541	<li><b><tt>RegisterAnalysis</tt></b> - This template should be used when you are
				542	registering a pass that logically should be available for use in the
				543	'<tt>analysis</tt>' utility.<p>
				544
				545	<li><b><tt>RegisterLLC</tt></b> - This template should be used when you are
				546	registering a pass that logically should be available for use in the
				547	'<tt>llc</tt>' utility.<p>
				548
				549	<li><b><tt>RegisterPass</tt></b> - This is the generic form of the
				550	<tt>Register*</tt> templates that should be used if you want your pass listed by
				551	multiple or no utilities. This template takes an extra third argument that
				552	specifies which tools it should be listed in. See the <a
				553	href="http://llvm.cs.uiuc.edu/doxygen/PassSupport_8h-source.html">PassSupport.h</a>
				554	file for more information.<p>
				555	</ul><p>
				556
				557	Regardless of how you register your pass, you must specify at least two
				558	parameters. The first parameter is the name of the pass that is to be used on
				559	the command line to specify that the pass should be added to a program (for
				560	example <tt>opt</tt> or <tt>analyze</tt>). The second argument is the name of
				561	the pass, which is to be used for the <tt>--help</tt> output of programs, as
				562	well as for debug output generated by the <tt>--debug-pass</tt> option.<p>
				563
				564	If you pass is constructed by its default constructor, you only ever have to
				565	pass these two arguments. If, on the other hand, you require other information
				566	(like target specific information), you must pass an additional argument. This
				567	argument is a pointer to a function used to create the pass. For an example of
				568	how this works, look at the <a
				569	href="http://llvm.cs.uiuc.edu/doxygen/LowerAllocations_8cpp-source.html">LowerAllocations.cpp</a>
				570	file.<p>
				571
				572	If a pass is registered to be used by the <tt>analyze</tt> utility, you should
				573	implement the virtual <tt>print</tt> method:<p>
				574
				575	<!-- _______________________________________________________________________ -->
				576	</ul><h4><a name="print"><hr size=0>The <tt>print</tt> method</h4><ul>
				577
				578	<pre>
				579	<b>virtual void</b> print(std::ostream &O, <b>const</b> Module *M) <b>const</b>;
				580	</pre><p>
				581
				582	The <tt>print</tt> method must be implemented by "analyses" in order to print a
				583	human readable version of the analysis results. This is useful for debugging an
				584	analysis itself, as well as for other people to figure out how an analysis
				585	works. The <tt>analyze</tt> tool uses this method to generate its output.<p>
				586
				587	The <tt>ostream</tt> parameter specifies the stream to write the results on, and
				588	the <tt>Module</tt> parameter gives a pointer to the top level module of the
				589	program that has been analyzed. Note however that this pointer may be null in
				590	certain circumstances (such as calling the <tt>Pass::dump()</tt> from a
				591	debugger), so it should only be used to enhance debug output, it should not be
				592	depended on.<p>
				593
				594
				595	<!-- *********************************************************************** -->
				596	</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
				597	<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
				598	<a name="interaction">Specifying interactions between passes
				599	</b></font></td></tr></table><ul>
				600	<!-- *********************************************************************** -->
				601
				602	One of the main responsibilities of the <tt>PassManager</tt> is the make sure
				603	that passes interact with each other correctly. Because <tt>PassManager</tt>
				604	tries to <a href="#passmanager">optimize the execution of passes</a> it must
				605	know how the passes interact with each other and what dependencies exist between
				606	the various passes. To track this, each pass can declare the set of passes that
				607	are required to be executed before the current pass, and the passes which are
				608	invalidated by the current pass.<p>
				609
				610	Typically this functionality is used to require that analysis results are
				611	computed before your pass is run. Running arbitrary transformation passes can
				612	invalidate the computed analysis results, which is what the invalidation set
				613	specifies. If a pass does not implement the <tt><a
				614	href="#getAnalysisUsage">getAnalysisUsage</a></tt> method, it defaults to not
				615	having any prerequisite passes, and invalidating <b>all</b> other passes.<p>
				616
				617
				618	<!-- _______________________________________________________________________ -->
				619	</ul><h4><a name="getAnalysisUsage"><hr size=0>The <tt>getAnalysisUsage</tt> method</h4><ul>
				620
				621	<pre>
				622	<b>virtual void</b> getAnalysisUsage(AnalysisUsage &Info) <b>const</b>;
				623	</pre><p>
				624
				625	By implementing the <tt>getAnalysisUsage</tt> method, the required and
				626	invalidated sets may be specified for your transformation. The implementation
				627	should fill in the <tt><a
				628	href="http://llvm.cs.uiuc.edu/doxygen/classAnalysisUsage.html">AnalysisUsage</a></tt>
				629	object with information about which passes are required and not invalidated. To do this, the following set methods are provided by the <tt><a
				630	href="http://llvm.cs.uiuc.edu/doxygen/classAnalysisUsage.html">AnalysisUsage</a></tt> class:<p>
				631
				632	<pre>
				633	<i>// addRequires - Add the specified pass to the required set for your pass.</i>
				634	<b>template</b><<b>class</b> PassClass>
				635	AnalysisUsage &AnalysisUsage::addRequired();
				636
				637	<i>// addPreserved - Add the specified pass to the set of analyses preserved by
				638	// this pass</i>
				639	<b>template</b><<b>class</b> PassClass>
				640	AnalysisUsage &AnalysisUsage::addPreserved();
				641
				642	<i>// setPreservesAll - Call this if the pass does not modify its input at all</i>
				643	<b>void</b> AnalysisUsage::setPreservesAll();
				644
				645	<i>// preservesCFG - This function should be called by the pass, iff they do not:
				646	//
				647	// 1. Add or remove basic blocks from the function
				648	// 2. Modify terminator instructions in any way.
				649	//
				650	// This is automatically implied for <a href="#BasicBlockPass">BasicBlockPass</a>'s
				651	//</i>
				652	<b>void</b> AnalysisUsage::preservesCFG();
				653	</pre><p>
				654
				655	Some examples of how to use these methods are:<p>
				656
				657	<pre>
				658	<i>// This is an example implementation from an analysis, which does not modify
				659	// the program at all, yet has a prerequisite.</i>
				660	<b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/structPostDominanceFrontier.html">PostDominanceFrontier</a>::getAnalysisUsage(AnalysisUsage &AU) <b>const</b> {
				661	AU.setPreservesAll();
				662	AU.addRequired<<a href="http://llvm.cs.uiuc.edu/doxygen/structPostDominatorTree.html">PostDominatorTree</a>>();
				663	}
				664	</pre><p>
				665
				666	and:<p>
				667
				668	<pre>
				669	<i>// This example modifies the program, but does not modify the CFG</i>
				670	<b>void</b> <a href="http://llvm.cs.uiuc.edu/doxygen/structLICM.html">LICM</a>::getAnalysisUsage(AnalysisUsage &AU) <b>const</b> {
				671	AU.preservesCFG();
				672	AU.addRequired<<a href="http://llvm.cs.uiuc.edu/doxygen/classLoopInfo.html">LoopInfo</a>>();
				673	}
				674	</pre><p>
				675
				676	<!-- _______________________________________________________________________ -->
				677	</ul><h4><a name="getAnalysis"><hr size=0>The <tt>getAnalysis<></tt> method</h4><ul>
				678
				679	The <tt>Pass::getAnalysis<></tt> method is inherited by your class,
				680	providing you with access to the passes that you declared that you required with
				681	the <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method. It takes
				682	a single template argument that specifies which pass class you want, and returns
				683	a reference to that pass.<p>
				684
				685	<pre>
				686	<b>template</b><<b>typename</b> PassClass>
				687	AnalysisType &getAnalysis();
				688	</pre><p>
				689
				690	This method call returns a reference to the pass desired. You may get a runtime
				691	assertion failure if you attempt to get an analysis that you did not declare as
				692	required in your <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a>
				693	implementation. This method can be called by your <tt>run*</tt> method
				694	implementation, or by any other local method invoked by your <tt>run*</tt>
				695	method.<p>
				696
				697
				698
				699	<!-- *********************************************************************** -->
				700	</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
				701	<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
				702	<a name="passmanager">What PassManager does
				703	</b></font></td></tr></table><ul>
				704	<!-- *********************************************************************** -->
				705
				706	The <a
				707	href="http://llvm.cs.uiuc.edu/doxygen/PassManager_8h-source.html"><tt>PassManager</tt></a>
				708	<a href="http://llvm.cs.uiuc.edu/doxygen/classPassManager.html">class</a> takes
				709	a list of passes, ensures their <a href="#interaction">prerequisites</a> are set
				710	up correctly, and then schedules passes to run efficiently. All of the LLVM
				711	tools that run passes use the <tt>PassManager</tt> for execution of these
				712	passes.<p>
				713
				714	The <tt>PassManager</tt> does two main things to try to reduce the execution
				715	time of a series of passes:<p>
				716
				717	<ol>
				718	<li><b>Share analysis results</b> - The PassManager attempts to avoid
				719	recomputing analysis results as much as possible. This means keeping track of
				720	which analyses are available already, which analyses get invalidated, and which
				721	analyses are needed to be run for a pass. An important part of work is that the
				722	<tt>PassManager</tt> tracks the exact lifetime of all analysis results, allowing
				723	it to <a href="#releaseMemory">free memory</a> allocated to holding analysis
				724	results as soon as they are no longer needed.<p>
				725
				726	<li><b>Pipeline the execution of passes on the program</b> - The
				727	<tt>PassManager</tt> attempts to get better cache and memory usage behavior out
				728	of a series of passes by pipelining the passes together. This means that, given
				729	a series of consequtive <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s, it
				730	will execute all of the <a href="#FunctionPass"><tt>FunctionPass</tt></a>'s on
				731	the first function, then all of the <a
				732	href="#FunctionPass"><tt>FunctionPass</tt></a>'s on the second function,
				733	etc... until the entire program has been run through the passes.<p>
				734
				735	This improves the cache behavior of the compiler, because it is only touching
				736	the LLVM program representation for a single function at a time, instead of
				737	traversing the entire program. It reduces the memory consumption of compiler,
				738	because, for example, only one <a
				739	href="http://llvm.cs.uiuc.edu/doxygen/structDominatorSet.html"><tt>DominatorSet</tt></a>
				740	needs to be calculated at a time. This also makes it possible some <a
				741	href="#SMP">interesting enhancements</a> in the future.<p>
				742
				743	</ol><p>
				744
				745	The effectiveness of the <tt>PassManager</tt> is influenced directly by how much
				746	information it has about the behaviors of the passes it is scheduling. For
				747	example, the "preserved" set is intentionally conservative in the face of an
				748	unimplemented <a href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method.
				749	Not implementing when it should be implemented will have the effect of not
				750	allowing any analysis results to live across the execution of your pass.<p>
				751
				752	The <tt>PassManager</tt> class exposes a <tt>--debug-pass</tt> command line
				753	options that is useful for debugging pass execution, seeing how things work, and
				754	diagnosing when you should be preserving more analyses than you currently are
				755	(To get information about all of the variants of the <tt>--debug-pass</tt>
				756	option, just type '<tt>opt --help-hidden</tt>').<p>
				757
				758	By using the <tt>--debug-pass=Structure</tt> option, for example, we can see how
				759	our <a href="#basiccode">Hello World</a> pass interacts with other passes. Lets
				760	try it out with the <tt>gcse</tt> and <tt>licm</tt> passes:<p>
				761
				762	<pre>
				763	$ opt -load ../../../lib/Debug/libhello.so -gcse -licm --debug-pass=Structure < hello.bc > /dev/null
				764	Module Pass Manager
				765	Function Pass Manager
				766	Dominator Set Construction
				767	Immediate Dominators Construction
				768	Global Common Subexpression Elimination
				769	-- Immediate Dominators Construction
				770	-- Global Common Subexpression Elimination
				771	Natural Loop Construction
				772	Loop Invariant Code Motion
				773	-- Natural Loop Construction
				774	-- Loop Invariant Code Motion
				775	Module Verifier
				776	-- Dominator Set Construction
				777	-- Module Verifier
				778	Bytecode Writer
				779	--Bytecode Writer
				780	</pre><p>
				781
				782	This output shows us when passes are constructed and when the analysis results
				783	are known to be dead (prefixed with '<tt>--</tt>'). Here we see that GCSE uses
				784	dominator and immediate dominator information to do its job. The LICM pass uses
				785	natural loop information, which uses dominator sets, but not immediate
				786	dominators. Because immediate dominators are no longer useful after the GCSE
				787	pass, it is immediately destroyed. The dominator sets are then reused to
				788	compute natural loop information, which is then used by the LICM pass.<p>
				789
				790	After the LICM pass, the module verifier runs (which is automatically added by
				791	the '<tt>opt</tt>' tool), which uses the dominator set to check that the
				792	resultant LLVM code is well formed. After it finishes, the dominator set
				793	information is destroyed, after being computed once, and shared by three
				794	passes.<p>
				795
				796	Lets see how this changes when we run the <a href="#basiccode">Hello World</a>
				797	pass in between the two passes:<p>
				798
				799	<pre>
				800	$ opt -load ../../../lib/Debug/libhello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null
				801	Module Pass Manager
				802	Function Pass Manager
				803	Dominator Set Construction
				804	Immediate Dominators Construction
				805	Global Common Subexpression Elimination
				806	<b>-- Dominator Set Construction</b>
				807	-- Immediate Dominators Construction
				808	-- Global Common Subexpression Elimination
				809	<b> Hello World Pass
				810	-- Hello World Pass
				811	Dominator Set Construction</b>
				812	Natural Loop Construction
				813	Loop Invariant Code Motion
				814	-- Natural Loop Construction
				815	-- Loop Invariant Code Motion
				816	Module Verifier
				817	-- Dominator Set Construction
				818	-- Module Verifier
				819	Bytecode Writer
				820	--Bytecode Writer
				821	Hello: __main
				822	Hello: puts
				823	Hello: main
				824	</pre><p>
				825
				826	Here we see that the <a href="#basiccode">Hello World</a> pass has killed the
				827	Dominator Set pass, even though it doesn't modify the code at all! To fix this,
				828	we need to add the following <a
				829	href="#getAnalysisUsage"><tt>getAnalysisUsage</tt></a> method to our pass:<p>
				830
				831	<pre>
				832	<i>// We don't modify the program, so we preserve all analyses</i>
				833	<b>virtual void</b> getAnalysisUsage(AnalysisUsage &AU) <b>const</b> {
				834	AU.setPreservesAll();
				835	}
				836	</pre><p>
				837
				838	Now when we run our pass, we get this output:<p>
				839
				840	<pre>
				841	$ opt -load ../../../lib/Debug/libhello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null
				842	Pass Arguments: -gcse -hello -licm
				843	Module Pass Manager
				844	Function Pass Manager
				845	Dominator Set Construction
				846	Immediate Dominators Construction
				847	Global Common Subexpression Elimination
				848	-- Immediate Dominators Construction
				849	-- Global Common Subexpression Elimination
				850	Hello World Pass
				851	-- Hello World Pass
				852	Natural Loop Construction
				853	Loop Invariant Code Motion
				854	-- Loop Invariant Code Motion
				855	-- Natural Loop Construction
				856	Module Verifier
				857	-- Dominator Set Construction
				858	-- Module Verifier
				859	Bytecode Writer
				860	--Bytecode Writer
				861	Hello: __main
				862	Hello: puts
				863	Hello: main
				864	</pre><p>
				865
				866	Which shows that we don't accidentally invalidate dominator information
				867	anymore, and therefore do not have to compute it twice.<p>
				868
				869
				870	<!-- _______________________________________________________________________ -->
				871	</ul><h4><a name="releaseMemory"><hr size=0>The <tt>releaseMemory</tt> method</h4><ul>
				872
				873	<pre>
				874	<b>virtual void</b> releaseMemory();
				875	</pre><p>
				876
				877	The <tt>PassManager</tt> automatically determines when to compute analysis
				878	results, and how long to keep them around for. Because the lifetime of the pass
				879	object itself is effectively the entire duration of the compilation process, we
				880	need some way to free analysis results when they are no longer useful. The
				881	<tt>releaseMemory</tt> virtual method is the way to do this.<p>
				882
				883	If you are writing an analysis or any other pass that retains a significant
				884	amount of state (for use by another pass which "requires" your pass and uses the
				885	<a href="#getAnalysis">getAnalysis</a> method) you should implement
				886	<tt>releaseMEmory</tt> to, well, release the memory allocated to maintain this
				887	internal state. This method is called after the <tt>run*</tt> method for the
				888	class, before the next call of <tt>run*</tt> in your pass.<p>
				889
				890
				891	<!-- *********************************************************************** -->
				892	</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
				893	<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
				894	<a name="future">Future extensions planned
				895	</b></font></td></tr></table><ul>
				896	<!-- *********************************************************************** -->
				897
				898	Although the LLVM Pass Infrastructure is very capable as it stands, and does
				899	some nifty stuff, there are things we'd like to add in the future. Here is
				900	where we are going:<p>
				901
				902	<!-- _______________________________________________________________________ -->
				903	</ul><h4><a name="SMP"><hr size=0>Multithreaded LLVM</h4><ul>
				904
				905	Multiple CPU machines are becoming more command and compilation can never be
				906	fast enough: obviously we should allow for a multithreaded compiler. Because of
				907	the semantics defined for passes above (specifically they cannot maintain state
				908	across invocations of their <tt>run*</tt> methods), a nice clean way to
				909	implement a multithreaded compiler would be for the <tt>PassManager</tt> class
				910	to create multiple instances of each pass object, and allow the seperate
				911	instances to be hacking on different parts of the program at the same time.<p>
				912
				913	This implementation would prevent each of the passes from having to implement
				914	multithreaded constructs, requiring only the LLVM core to have locking in a few
				915	places (for global resources). Although this is a simple extension, we simply
				916	haven't had time (or multiprocessor machines, thus a reason) to implement this.
				917	Despite that, we have kept the LLVM passes SMP ready, and you should too.<p>
				918
				919
				920	<!-- _______________________________________________________________________ -->
				921	</ul><h4><a name="ModuleSource"><hr size=0>A new <tt>ModuleSource</tt> interface</h4><ul>
				922
				923	Currently, the <tt>PassManager</tt>'s <tt>run</tt> method takes a <tt><a
				924	href="http://llvm.cs.uiuc.edu/doxygen/classModule.html">Module</a></tt> as
				925	input, and runs all of the passes on this module. The problem with this
				926	approach is that none of the <tt>PassManager</tt> features can be used for
				927	timing and debugging the actual <b>loading</b> of the module from disk or
				928	standard input.<p>
				929
				930	To solve this problem, eventually the <tt>PassManger</tt> class will accept a
				931	<tt>ModuleSource</tt> object instead of a Module itself. When complete, this
				932	will also allow for streaming of functions out of the bytecode representation,
				933	allowing us to avoid holding the entire program in memory at once if we only are
				934	dealing with <a href="#FunctionPass">FunctionPass</a>'s.<p>
				935
				936	As part of a different issue, eventually the bytecode loader will be extended to
				937	allow on-demand loading of functions from the bytecode representation, in order
				938	to better support the runtime reoptimizer. The bytecode format is already
				939	capable of this, the loader just needs to be reworked a bit.<p>
				940
				941
				942	<!-- _______________________________________________________________________ -->
				943	</ul><h4><a name="PassFunctionPass"><hr size=0><tt>Pass</tt>'s requiring <tt>FunctionPass</tt>'s</h4><ul>
				944
				945	Currently it is illegal for a <a href="#Pass"><tt>Pass</tt></a> to require a <a
				946	href="#FunctionPass"><tt>FunctionPass</tt></a>. This is because there is only
				947	one instance of the <a href="#FunctionPass"><tt>FunctionPass</tt></a> object
				948	ever created, thus nowhere to store information for all of the functions in the
				949	program at the same time. Although this has come up a couple of times before,
				950	this has always been worked around by factoring one big complicated pass into a
				951	global and an interprocedural part, both of which are distinct. In the future,
				952	it would be nice to have this though.<p>
				953
				954	Note that it is no problem for a <a
				955	href="#FunctionPass"><tt>FunctionPass</tt></a> to require the results of a <a
				956	href="#Pass"><tt>Pass</tt></a>, only the other way around.<p>
				957
				958
				959	<!-- *********************************************************************** -->
				960	</ul>
				961	<!-- *********************************************************************** -->
				962
				963	<hr><font size-1>
				964	<address><a href="mailto:sabre@nondot.org">Christopher Lattner</a></address>
				965	<!-- Created: Tue Aug 6 15:00:33 CDT 2002 -->
				966	<!-- hhmts start -->
				967	Last modified: Thu Aug 8 15:07:23 CDT 2002
				968	<!-- hhmts end -->
				969	</font></body></html>