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

blob: b33edb0eb6899a0c221144582e778b8d092eaa9c [file] [log] [blame]

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