Blame - docs/ProgrammersManual.html - platform/external/llvm

blob: dba721369709ff7c1fe60e28cfb56df812710a48 [file] [log] [blame]

Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
				2	"http://www.w3.org/TR/html4/strict.dtd">
				3	<html>
				4	<head>
Owen Anderson	60f8757	2009-06-16 17:40:28 +0000	[diff] [blame]	5	<meta http-equiv="Content-type" content="text/html;charset=UTF-8">
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	6	<title>LLVM Programmer's Manual</title>
				7	<link rel="stylesheet" href="llvm.css" type="text/css">
				8	</head>
				9	<body>
				10
				11	<div class="doc_title">
				12	LLVM Programmer's Manual
				13	</div>
				14
				15	<ol>
				16	<li><a href="#introduction">Introduction</a></li>
				17	<li><a href="#general">General Information</a>
				18	<ul>
				19	<li><a href="#stl">The C++ Standard Template Library</a></li>
				20	<!--
				21	<li>The <tt>-time-passes</tt> option</li>
				22	<li>How to use the LLVM Makefile system</li>
				23	<li>How to write a regression test</li>
				24
				25	-->
				26	</ul>
				27	</li>
				28	<li><a href="#apis">Important and useful LLVM APIs</a>
				29	<ul>
				30	<li><a href="#isa">The <tt>isa<></tt>, <tt>cast<></tt>
				31	and <tt>dyn_cast<></tt> templates</a> </li>
				32	<li><a href="#DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt>
				33	option</a>
				34	<ul>
				35	<li><a href="#DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE</tt>
				36	and the <tt>-debug-only</tt> option</a> </li>
				37	</ul>
				38	</li>
				39	<li><a href="#Statistic">The <tt>Statistic</tt> class & <tt>-stats</tt>
				40	option</a></li>
				41	<!--
				42	<li>The <tt>InstVisitor</tt> template
				43	<li>The general graph API
				44	-->
				45	<li><a href="#ViewGraph">Viewing graphs while debugging code</a></li>
				46	</ul>
				47	</li>
				48	<li><a href="#datastructure">Picking the Right Data Structure for a Task</a>
				49	<ul>
				50	<li><a href="#ds_sequential">Sequential Containers (std::vector, std::list, etc)</a>
				51	<ul>
				52	<li><a href="#dss_fixedarrays">Fixed Size Arrays</a></li>
				53	<li><a href="#dss_heaparrays">Heap Allocated Arrays</a></li>
				54	<li><a href="#dss_smallvector">"llvm/ADT/SmallVector.h"</a></li>
				55	<li><a href="#dss_vector"><vector></a></li>
				56	<li><a href="#dss_deque"><deque></a></li>
				57	<li><a href="#dss_list"><list></a></li>
Gabor Greif	bb17f65	2009-02-27 11:37:41 +0000	[diff] [blame]	58	<li><a href="#dss_ilist">llvm/ADT/ilist.h</a></li>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	59	<li><a href="#dss_other">Other Sequential Container Options</a></li>
				60	</ul></li>
				61	<li><a href="#ds_set">Set-Like Containers (std::set, SmallSet, SetVector, etc)</a>
				62	<ul>
				63	<li><a href="#dss_sortedvectorset">A sorted 'vector'</a></li>
				64	<li><a href="#dss_smallset">"llvm/ADT/SmallSet.h"</a></li>
				65	<li><a href="#dss_smallptrset">"llvm/ADT/SmallPtrSet.h"</a></li>
Chris Lattner	77ab46d	2007-09-30 00:58:59 +0000	[diff] [blame]	66	<li><a href="#dss_denseset">"llvm/ADT/DenseSet.h"</a></li>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	67	<li><a href="#dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a></li>
				68	<li><a href="#dss_set"><set></a></li>
				69	<li><a href="#dss_setvector">"llvm/ADT/SetVector.h"</a></li>
				70	<li><a href="#dss_uniquevector">"llvm/ADT/UniqueVector.h"</a></li>
				71	<li><a href="#dss_otherset">Other Set-Like ContainerOptions</a></li>
				72	</ul></li>
				73	<li><a href="#ds_map">Map-Like Containers (std::map, DenseMap, etc)</a>
				74	<ul>
				75	<li><a href="#dss_sortedvectormap">A sorted 'vector'</a></li>
				76	<li><a href="#dss_stringmap">"llvm/ADT/StringMap.h"</a></li>
				77	<li><a href="#dss_indexedmap">"llvm/ADT/IndexedMap.h"</a></li>
				78	<li><a href="#dss_densemap">"llvm/ADT/DenseMap.h"</a></li>
				79	<li><a href="#dss_map"><map></a></li>
				80	<li><a href="#dss_othermap">Other Map-Like Container Options</a></li>
				81	</ul></li>
Daniel Berlin	7ea44dc	2007-09-24 17:52:25 +0000	[diff] [blame]	82	<li><a href="#ds_bit">BitVector-like containers</a>
				83	<ul>
				84	<li><a href="#dss_bitvector">A dense bitvector</a></li>
				85	<li><a href="#dss_sparsebitvector">A sparse bitvector</a></li>
				86	</ul></li>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	87	</ul>
				88	</li>
				89	<li><a href="#common">Helpful Hints for Common Operations</a>
				90	<ul>
				91	<li><a href="#inspection">Basic Inspection and Traversal Routines</a>
				92	<ul>
				93	<li><a href="#iterate_function">Iterating over the <tt>BasicBlock</tt>s
				94	in a <tt>Function</tt></a> </li>
				95	<li><a href="#iterate_basicblock">Iterating over the <tt>Instruction</tt>s
				96	in a <tt>BasicBlock</tt></a> </li>
				97	<li><a href="#iterate_institer">Iterating over the <tt>Instruction</tt>s
				98	in a <tt>Function</tt></a> </li>
				99	<li><a href="#iterate_convert">Turning an iterator into a
				100	class pointer</a> </li>
				101	<li><a href="#iterate_complex">Finding call sites: a more
				102	complex example</a> </li>
				103	<li><a href="#calls_and_invokes">Treating calls and invokes
				104	the same way</a> </li>
				105	<li><a href="#iterate_chains">Iterating over def-use &
				106	use-def chains</a> </li>
Chris Lattner	0665e1f	2008-01-03 16:56:04 +0000	[diff] [blame]	107	<li><a href="#iterate_preds">Iterating over predecessors &
				108	successors of blocks</a></li>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	109	</ul>
				110	</li>
				111	<li><a href="#simplechanges">Making simple changes</a>
				112	<ul>
				113	<li><a href="#schanges_creating">Creating and inserting new
				114	<tt>Instruction</tt>s</a> </li>
				115	<li><a href="#schanges_deleting">Deleting <tt>Instruction</tt>s</a> </li>
				116	<li><a href="#schanges_replacing">Replacing an <tt>Instruction</tt>
				117	with another <tt>Value</tt></a> </li>
				118	<li><a href="#schanges_deletingGV">Deleting <tt>GlobalVariable</tt>s</a> </li>
				119	</ul>
				120	</li>
Jeffrey Yasskin	7ebb6ac	2009-04-30 22:33:41 +0000	[diff] [blame]	121	<li><a href="#create_types">How to Create Types</a></li>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	122	<!--
				123	<li>Working with the Control Flow Graph
				124	<ul>
				125	<li>Accessing predecessors and successors of a <tt>BasicBlock</tt>
				126	<li>
				127	<li>
				128	</ul>
				129	-->
				130	</ul>
				131	</li>
				132
Owen Anderson	e8370c0	2009-06-16 01:17:16 +0000	[diff] [blame]	133	<li><a href="#threading">Threads and LLVM</a>
				134	<ul>
Owen Anderson	b418690	2009-06-16 18:04:19 +0000	[diff] [blame]	135	<li><a href="#startmultithreaded">Entering and Exiting Multithreaded Mode
				136	</a></li>
Owen Anderson	e8370c0	2009-06-16 01:17:16 +0000	[diff] [blame]	137	<li><a href="#shutdown">Ending execution with <tt>llvm_shutdown()</tt></a></li>
				138	<li><a href="#managedstatic">Lazy initialization with <tt>ManagedStatic</tt></a></li>
				139	</ul>
				140	</li>
				141
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	142	<li><a href="#advanced">Advanced Topics</a>
				143	<ul>
				144	<li><a href="#TypeResolve">LLVM Type Resolution</a>
				145	<ul>
				146	<li><a href="#BuildRecType">Basic Recursive Type Construction</a></li>
				147	<li><a href="#refineAbstractTypeTo">The <tt>refineAbstractTypeTo</tt> method</a></li>
				148	<li><a href="#PATypeHolder">The PATypeHolder Class</a></li>
				149	<li><a href="#AbstractTypeUser">The AbstractTypeUser Class</a></li>
				150	</ul></li>
				151
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	152	<li><a href="#SymbolTable">The <tt>ValueSymbolTable</tt> and <tt>TypeSymbolTable</tt> classes</a></li>
				153	<li><a href="#UserLayout">The <tt>User</tt> and owned <tt>Use</tt> classes' memory layout</a></li>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	154	</ul></li>
				155
				156	<li><a href="#coreclasses">The Core LLVM Class Hierarchy Reference</a>
				157	<ul>
				158	<li><a href="#Type">The <tt>Type</tt> class</a> </li>
				159	<li><a href="#Module">The <tt>Module</tt> class</a></li>
				160	<li><a href="#Value">The <tt>Value</tt> class</a>
				161	<ul>
				162	<li><a href="#User">The <tt>User</tt> class</a>
				163	<ul>
				164	<li><a href="#Instruction">The <tt>Instruction</tt> class</a></li>
				165	<li><a href="#Constant">The <tt>Constant</tt> class</a>
				166	<ul>
				167	<li><a href="#GlobalValue">The <tt>GlobalValue</tt> class</a>
				168	<ul>
				169	<li><a href="#Function">The <tt>Function</tt> class</a></li>
				170	<li><a href="#GlobalVariable">The <tt>GlobalVariable</tt> class</a></li>
				171	</ul>
				172	</li>
				173	</ul>
				174	</li>
				175	</ul>
				176	</li>
				177	<li><a href="#BasicBlock">The <tt>BasicBlock</tt> class</a></li>
				178	<li><a href="#Argument">The <tt>Argument</tt> class</a></li>
				179	</ul>
				180	</li>
				181	</ul>
				182	</li>
				183	</ol>
				184
				185	<div class="doc_author">
				186	<p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>,
				187	<a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a>,
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	188	<a href="mailto:ggreif@gmail.com">Gabor Greif</a>,
Owen Anderson	e8370c0	2009-06-16 01:17:16 +0000	[diff] [blame]	189	<a href="mailto:jstanley@cs.uiuc.edu">Joel Stanley</a>,
				190	<a href="mailto:rspencer@x10sys.com">Reid Spencer</a> and
				191	<a href="mailto:owen@apple.com">Owen Anderson</a></p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	192	</div>
				193
				194	<!-- *********************************************************************** -->
				195	<div class="doc_section">
				196	<a name="introduction">Introduction </a>
				197	</div>
				198	<!-- *********************************************************************** -->
				199
				200	<div class="doc_text">
				201
				202	<p>This document is meant to highlight some of the important classes and
				203	interfaces available in the LLVM source-base. This manual is not
				204	intended to explain what LLVM is, how it works, and what LLVM code looks
				205	like. It assumes that you know the basics of LLVM and are interested
				206	in writing transformations or otherwise analyzing or manipulating the
				207	code.</p>
				208
				209	<p>This document should get you oriented so that you can find your
				210	way in the continuously growing source code that makes up the LLVM
				211	infrastructure. Note that this manual is not intended to serve as a
				212	replacement for reading the source code, so if you think there should be
				213	a method in one of these classes to do something, but it's not listed,
				214	check the source. Links to the <a href="/doxygen/">doxygen</a> sources
				215	are provided to make this as easy as possible.</p>
				216
				217	<p>The first section of this document describes general information that is
				218	useful to know when working in the LLVM infrastructure, and the second describes
				219	the Core LLVM classes. In the future this manual will be extended with
				220	information describing how to use extension libraries, such as dominator
				221	information, CFG traversal routines, and useful utilities like the <tt><a
				222	href="/doxygen/InstVisitor_8h-source.html">InstVisitor</a></tt> template.</p>
				223
				224	</div>
				225
				226	<!-- *********************************************************************** -->
				227	<div class="doc_section">
				228	<a name="general">General Information</a>
				229	</div>
				230	<!-- *********************************************************************** -->
				231
				232	<div class="doc_text">
				233
				234	<p>This section contains general information that is useful if you are working
				235	in the LLVM source-base, but that isn't specific to any particular API.</p>
				236
				237	</div>
				238
				239	<!-- ======================================================================= -->
				240	<div class="doc_subsection">
				241	<a name="stl">The C++ Standard Template Library</a>
				242	</div>
				243
				244	<div class="doc_text">
				245
				246	<p>LLVM makes heavy use of the C++ Standard Template Library (STL),
				247	perhaps much more than you are used to, or have seen before. Because of
				248	this, you might want to do a little background reading in the
				249	techniques used and capabilities of the library. There are many good
				250	pages that discuss the STL, and several books on the subject that you
				251	can get, so it will not be discussed in this document.</p>
				252
				253	<p>Here are some useful links:</p>
				254
				255	<ol>
				256
				257	<li><a href="http://www.dinkumware.com/refxcpp.html">Dinkumware C++ Library
				258	reference</a> - an excellent reference for the STL and other parts of the
				259	standard C++ library.</li>
				260
				261	<li><a href="http://www.tempest-sw.com/cpp/">C++ In a Nutshell</a> - This is an
Gabor Greif	e39f0e7	2009-03-12 09:47:03 +0000	[diff] [blame]	262	O'Reilly book in the making. It has a decent Standard Library
				263	Reference that rivals Dinkumware's, and is unfortunately no longer free since the
				264	book has been published.</li>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	265
				266	<li><a href="http://www.parashift.com/c++-faq-lite/">C++ Frequently Asked
				267	Questions</a></li>
				268
				269	<li><a href="http://www.sgi.com/tech/stl/">SGI's STL Programmer's Guide</a> -
				270	Contains a useful <a
				271	href="http://www.sgi.com/tech/stl/stl_introduction.html">Introduction to the
				272	STL</a>.</li>
				273
				274	<li><a href="http://www.research.att.com/%7Ebs/C++.html">Bjarne Stroustrup's C++
				275	Page</a></li>
				276
				277	<li><a href="http://64.78.49.204/">
				278	Bruce Eckel's Thinking in C++, 2nd ed. Volume 2 Revision 4.0 (even better, get
				279	the book).</a></li>
				280
				281	</ol>
				282
				283	<p>You are also encouraged to take a look at the <a
				284	href="CodingStandards.html">LLVM Coding Standards</a> guide which focuses on how
				285	to write maintainable code more than where to put your curly braces.</p>
				286
				287	</div>
				288
				289	<!-- ======================================================================= -->
				290	<div class="doc_subsection">
				291	<a name="stl">Other useful references</a>
				292	</div>
				293
				294	<div class="doc_text">
				295
				296	<ol>
				297	<li><a href="http://www.psc.edu/%7Esemke/cvs_branches.html">CVS
				298	Branch and Tag Primer</a></li>
				299	<li><a href="http://www.fortran-2000.com/ArnaudRecipes/sharedlib.html">Using
				300	static and shared libraries across platforms</a></li>
				301	</ol>
				302
				303	</div>
				304
				305	<!-- *********************************************************************** -->
				306	<div class="doc_section">
				307	<a name="apis">Important and useful LLVM APIs</a>
				308	</div>
				309	<!-- *********************************************************************** -->
				310
				311	<div class="doc_text">
				312
				313	<p>Here we highlight some LLVM APIs that are generally useful and good to
				314	know about when writing transformations.</p>
				315
				316	</div>
				317
				318	<!-- ======================================================================= -->
				319	<div class="doc_subsection">
				320	<a name="isa">The <tt>isa<></tt>, <tt>cast<></tt> and
				321	<tt>dyn_cast<></tt> templates</a>
				322	</div>
				323
				324	<div class="doc_text">
				325
				326	<p>The LLVM source-base makes extensive use of a custom form of RTTI.
				327	These templates have many similarities to the C++ <tt>dynamic_cast<></tt>
				328	operator, but they don't have some drawbacks (primarily stemming from
				329	the fact that <tt>dynamic_cast<></tt> only works on classes that
				330	have a v-table). Because they are used so often, you must know what they
				331	do and how they work. All of these templates are defined in the <a
				332	href="/doxygen/Casting_8h-source.html"><tt>llvm/Support/Casting.h</tt></a>
				333	file (note that you very rarely have to include this file directly).</p>
				334
				335	<dl>
				336	<dt><tt>isa<></tt>: </dt>
				337
				338	<dd><p>The <tt>isa<></tt> operator works exactly like the Java
				339	"<tt>instanceof</tt>" operator. It returns true or false depending on whether
				340	a reference or pointer points to an instance of the specified class. This can
				341	be very useful for constraint checking of various sorts (example below).</p>
				342	</dd>
				343
				344	<dt><tt>cast<></tt>: </dt>
				345
				346	<dd><p>The <tt>cast<></tt> operator is a "checked cast" operation. It
Chris Lattner	1d5610a	2008-06-20 05:03:17 +0000	[diff] [blame]	347	converts a pointer or reference from a base class to a derived class, causing
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	348	an assertion failure if it is not really an instance of the right type. This
				349	should be used in cases where you have some information that makes you believe
				350	that something is of the right type. An example of the <tt>isa<></tt>
				351	and <tt>cast<></tt> template is:</p>
				352
				353	<div class="doc_code">
				354	<pre>
				355	static bool isLoopInvariant(const <a href="#Value">Value</a> V, const Loop L) {
				356	if (isa<<a href="#Constant">Constant</a>>(V) \|\| isa<<a href="#Argument">Argument</a>>(V) \|\| isa<<a href="#GlobalValue">GlobalValue</a>>(V))
				357	return true;
				358
				359	// <i>Otherwise, it must be an instruction...</i>
				360	return !L->contains(cast<<a href="#Instruction">Instruction</a>>(V)->getParent());
				361	}
				362	</pre>
				363	</div>
				364
				365	<p>Note that you should <b>not</b> use an <tt>isa<></tt> test followed
				366	by a <tt>cast<></tt>, for that use the <tt>dyn_cast<></tt>
				367	operator.</p>
				368
				369	</dd>
				370
				371	<dt><tt>dyn_cast<></tt>:</dt>
				372
				373	<dd><p>The <tt>dyn_cast<></tt> operator is a "checking cast" operation.
				374	It checks to see if the operand is of the specified type, and if so, returns a
				375	pointer to it (this operator does not work with references). If the operand is
				376	not of the correct type, a null pointer is returned. Thus, this works very
				377	much like the <tt>dynamic_cast<></tt> operator in C++, and should be
				378	used in the same circumstances. Typically, the <tt>dyn_cast<></tt>
				379	operator is used in an <tt>if</tt> statement or some other flow control
				380	statement like this:</p>
				381
				382	<div class="doc_code">
				383	<pre>
				384	if (<a href="#AllocationInst">AllocationInst</a> *AI = dyn_cast<<a href="#AllocationInst">AllocationInst</a>>(Val)) {
				385	// <i>...</i>
				386	}
				387	</pre>
				388	</div>
				389
				390	<p>This form of the <tt>if</tt> statement effectively combines together a call
				391	to <tt>isa<></tt> and a call to <tt>cast<></tt> into one
				392	statement, which is very convenient.</p>
				393
				394	<p>Note that the <tt>dyn_cast<></tt> operator, like C++'s
				395	<tt>dynamic_cast<></tt> or Java's <tt>instanceof</tt> operator, can be
				396	abused. In particular, you should not use big chained <tt>if/then/else</tt>
				397	blocks to check for lots of different variants of classes. If you find
				398	yourself wanting to do this, it is much cleaner and more efficient to use the
				399	<tt>InstVisitor</tt> class to dispatch over the instruction type directly.</p>
				400
				401	</dd>
				402
				403	<dt><tt>cast_or_null<></tt>: </dt>
				404
				405	<dd><p>The <tt>cast_or_null<></tt> operator works just like the
				406	<tt>cast<></tt> operator, except that it allows for a null pointer as an
				407	argument (which it then propagates). This can sometimes be useful, allowing
				408	you to combine several null checks into one.</p></dd>
				409
				410	<dt><tt>dyn_cast_or_null<></tt>: </dt>
				411
				412	<dd><p>The <tt>dyn_cast_or_null<></tt> operator works just like the
				413	<tt>dyn_cast<></tt> operator, except that it allows for a null pointer
				414	as an argument (which it then propagates). This can sometimes be useful,
				415	allowing you to combine several null checks into one.</p></dd>
				416
				417	</dl>
				418
				419	<p>These five templates can be used with any classes, whether they have a
				420	v-table or not. To add support for these templates, you simply need to add
				421	<tt>classof</tt> static methods to the class you are interested casting
				422	to. Describing this is currently outside the scope of this document, but there
				423	are lots of examples in the LLVM source base.</p>
				424
				425	</div>
				426
				427	<!-- ======================================================================= -->
				428	<div class="doc_subsection">
				429	<a name="DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt> option</a>
				430	</div>
				431
				432	<div class="doc_text">
				433
				434	<p>Often when working on your pass you will put a bunch of debugging printouts
				435	and other code into your pass. After you get it working, you want to remove
				436	it, but you may need it again in the future (to work out new bugs that you run
				437	across).</p>
				438
				439	<p> Naturally, because of this, you don't want to delete the debug printouts,
				440	but you don't want them to always be noisy. A standard compromise is to comment
				441	them out, allowing you to enable them if you need them in the future.</p>
				442
				443	<p>The "<tt><a href="/doxygen/Debug_8h-source.html">llvm/Support/Debug.h</a></tt>"
				444	file provides a macro named <tt>DEBUG()</tt> that is a much nicer solution to
				445	this problem. Basically, you can put arbitrary code into the argument of the
				446	<tt>DEBUG</tt> macro, and it is only executed if '<tt>opt</tt>' (or any other
				447	tool) is run with the '<tt>-debug</tt>' command line argument:</p>
				448
				449	<div class="doc_code">
				450	<pre>
Daniel Dunbar	e32f9b2	2009-07-25 01:55:32 +0000	[diff] [blame]	451	DEBUG(errs() << "I am here!\n");
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	452	</pre>
				453	</div>
				454
				455	<p>Then you can run your pass like this:</p>
				456
				457	<div class="doc_code">
				458	<pre>
				459	$ opt < a.bc > /dev/null -mypass
				460	<i><no output></i>
				461	$ opt < a.bc > /dev/null -mypass -debug
				462	I am here!
				463	</pre>
				464	</div>
				465
				466	<p>Using the <tt>DEBUG()</tt> macro instead of a home-brewed solution allows you
				467	to not have to create "yet another" command line option for the debug output for
				468	your pass. Note that <tt>DEBUG()</tt> macros are disabled for optimized builds,
				469	so they do not cause a performance impact at all (for the same reason, they
				470	should also not contain side-effects!).</p>
				471
				472	<p>One additional nice thing about the <tt>DEBUG()</tt> macro is that you can
				473	enable or disable it directly in gdb. Just use "<tt>set DebugFlag=0</tt>" or
				474	"<tt>set DebugFlag=1</tt>" from the gdb if the program is running. If the
				475	program hasn't been started yet, you can always just run it with
				476	<tt>-debug</tt>.</p>
				477
				478	</div>
				479
				480	<!-- _______________________________________________________________________ -->
				481	<div class="doc_subsubsection">
				482	<a name="DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE</tt> and
				483	the <tt>-debug-only</tt> option</a>
				484	</div>
				485
				486	<div class="doc_text">
				487
				488	<p>Sometimes you may find yourself in a situation where enabling <tt>-debug</tt>
				489	just turns on <b>too much</b> information (such as when working on the code
				490	generator). If you want to enable debug information with more fine-grained
				491	control, you define the <tt>DEBUG_TYPE</tt> macro and the <tt>-debug</tt> only
				492	option as follows:</p>
				493
				494	<div class="doc_code">
				495	<pre>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	496	#undef DEBUG_TYPE
Daniel Dunbar	e32f9b2	2009-07-25 01:55:32 +0000	[diff] [blame]	497	DEBUG(errs() << "No debug type\n");
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	498	#define DEBUG_TYPE "foo"
Daniel Dunbar	e32f9b2	2009-07-25 01:55:32 +0000	[diff] [blame]	499	DEBUG(errs() << "'foo' debug type\n");
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	500	#undef DEBUG_TYPE
				501	#define DEBUG_TYPE "bar"
Daniel Dunbar	e32f9b2	2009-07-25 01:55:32 +0000	[diff] [blame]	502	DEBUG(errs() << "'bar' debug type\n"));
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	503	#undef DEBUG_TYPE
				504	#define DEBUG_TYPE ""
Daniel Dunbar	e32f9b2	2009-07-25 01:55:32 +0000	[diff] [blame]	505	DEBUG(errs() << "No debug type (2)\n");
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	506	</pre>
				507	</div>
				508
				509	<p>Then you can run your pass like this:</p>
				510
				511	<div class="doc_code">
				512	<pre>
				513	$ opt < a.bc > /dev/null -mypass
				514	<i><no output></i>
				515	$ opt < a.bc > /dev/null -mypass -debug
				516	No debug type
				517	'foo' debug type
				518	'bar' debug type
				519	No debug type (2)
				520	$ opt < a.bc > /dev/null -mypass -debug-only=foo
				521	'foo' debug type
				522	$ opt < a.bc > /dev/null -mypass -debug-only=bar
				523	'bar' debug type
				524	</pre>
				525	</div>
				526
				527	<p>Of course, in practice, you should only set <tt>DEBUG_TYPE</tt> at the top of
				528	a file, to specify the debug type for the entire module (if you do this before
				529	you <tt>#include "llvm/Support/Debug.h"</tt>, you don't have to insert the ugly
				530	<tt>#undef</tt>'s). Also, you should use names more meaningful than "foo" and
				531	"bar", because there is no system in place to ensure that names do not
				532	conflict. If two different modules use the same string, they will all be turned
				533	on when the name is specified. This allows, for example, all debug information
				534	for instruction scheduling to be enabled with <tt>-debug-type=InstrSched</tt>,
				535	even if the source lives in multiple files.</p>
				536
				537	</div>
				538
				539	<!-- ======================================================================= -->
				540	<div class="doc_subsection">
				541	<a name="Statistic">The <tt>Statistic</tt> class & <tt>-stats</tt>
				542	option</a>
				543	</div>
				544
				545	<div class="doc_text">
				546
				547	<p>The "<tt><a
				548	href="/doxygen/Statistic_8h-source.html">llvm/ADT/Statistic.h</a></tt>" file
				549	provides a class named <tt>Statistic</tt> that is used as a unified way to
				550	keep track of what the LLVM compiler is doing and how effective various
				551	optimizations are. It is useful to see what optimizations are contributing to
				552	making a particular program run faster.</p>
				553
				554	<p>Often you may run your pass on some big program, and you're interested to see
				555	how many times it makes a certain transformation. Although you can do this with
				556	hand inspection, or some ad-hoc method, this is a real pain and not very useful
				557	for big programs. Using the <tt>Statistic</tt> class makes it very easy to
				558	keep track of this information, and the calculated information is presented in a
				559	uniform manner with the rest of the passes being executed.</p>
				560
				561	<p>There are many examples of <tt>Statistic</tt> uses, but the basics of using
				562	it are as follows:</p>
				563
				564	<ol>
				565	<li><p>Define your statistic like this:</p>
				566
				567	<div class="doc_code">
				568	<pre>
				569	#define <a href="#DEBUG_TYPE">DEBUG_TYPE</a> "mypassname" <i>// This goes before any #includes.</i>
				570	STATISTIC(NumXForms, "The # of times I did stuff");
				571	</pre>
				572	</div>
				573
				574	<p>The <tt>STATISTIC</tt> macro defines a static variable, whose name is
				575	specified by the first argument. The pass name is taken from the DEBUG_TYPE
				576	macro, and the description is taken from the second argument. The variable
				577	defined ("NumXForms" in this case) acts like an unsigned integer.</p></li>
				578
				579	<li><p>Whenever you make a transformation, bump the counter:</p>
				580
				581	<div class="doc_code">
				582	<pre>
				583	++NumXForms; // <i>I did stuff!</i>
				584	</pre>
				585	</div>
				586
				587	</li>
				588	</ol>
				589
				590	<p>That's all you have to do. To get '<tt>opt</tt>' to print out the
				591	statistics gathered, use the '<tt>-stats</tt>' option:</p>
				592
				593	<div class="doc_code">
				594	<pre>
				595	$ opt -stats -mypassname < program.bc > /dev/null
				596	<i>... statistics output ...</i>
				597	</pre>
				598	</div>
				599
				600	<p> When running <tt>opt</tt> on a C file from the SPEC benchmark
				601	suite, it gives a report that looks like this:</p>
				602
				603	<div class="doc_code">
				604	<pre>
				605	7646 bitcodewriter - Number of normal instructions
				606	725 bitcodewriter - Number of oversized instructions
				607	129996 bitcodewriter - Number of bitcode bytes written
				608	2817 raise - Number of insts DCEd or constprop'd
				609	3213 raise - Number of cast-of-self removed
				610	5046 raise - Number of expression trees converted
				611	75 raise - Number of other getelementptr's formed
				612	138 raise - Number of load/store peepholes
				613	42 deadtypeelim - Number of unused typenames removed from symtab
				614	392 funcresolve - Number of varargs functions resolved
				615	27 globaldce - Number of global variables removed
				616	2 adce - Number of basic blocks removed
				617	134 cee - Number of branches revectored
				618	49 cee - Number of setcc instruction eliminated
				619	532 gcse - Number of loads removed
				620	2919 gcse - Number of instructions removed
				621	86 indvars - Number of canonical indvars added
				622	87 indvars - Number of aux indvars removed
				623	25 instcombine - Number of dead inst eliminate
				624	434 instcombine - Number of insts combined
				625	248 licm - Number of load insts hoisted
				626	1298 licm - Number of insts hoisted to a loop pre-header
				627	3 licm - Number of insts hoisted to multiple loop preds (bad, no loop pre-header)
				628	75 mem2reg - Number of alloca's promoted
				629	1444 cfgsimplify - Number of blocks simplified
				630	</pre>
				631	</div>
				632
				633	<p>Obviously, with so many optimizations, having a unified framework for this
				634	stuff is very nice. Making your pass fit well into the framework makes it more
				635	maintainable and useful.</p>
				636
				637	</div>
				638
				639	<!-- ======================================================================= -->
				640	<div class="doc_subsection">
				641	<a name="ViewGraph">Viewing graphs while debugging code</a>
				642	</div>
				643
				644	<div class="doc_text">
				645
				646	<p>Several of the important data structures in LLVM are graphs: for example
				647	CFGs made out of LLVM <a href="#BasicBlock">BasicBlock</a>s, CFGs made out of
				648	LLVM <a href="CodeGenerator.html#machinebasicblock">MachineBasicBlock</a>s, and
				649	<a href="CodeGenerator.html#selectiondag_intro">Instruction Selection
				650	DAGs</a>. In many cases, while debugging various parts of the compiler, it is
				651	nice to instantly visualize these graphs.</p>
				652
				653	<p>LLVM provides several callbacks that are available in a debug build to do
				654	exactly that. If you call the <tt>Function::viewCFG()</tt> method, for example,
				655	the current LLVM tool will pop up a window containing the CFG for the function
				656	where each basic block is a node in the graph, and each node contains the
				657	instructions in the block. Similarly, there also exists
				658	<tt>Function::viewCFGOnly()</tt> (does not include the instructions), the
				659	<tt>MachineFunction::viewCFG()</tt> and <tt>MachineFunction::viewCFGOnly()</tt>,
				660	and the <tt>SelectionDAG::viewGraph()</tt> methods. Within GDB, for example,
				661	you can usually use something like <tt>call DAG.viewGraph()</tt> to pop
				662	up a window. Alternatively, you can sprinkle calls to these functions in your
				663	code in places you want to debug.</p>
				664
				665	<p>Getting this to work requires a small amount of configuration. On Unix
				666	systems with X11, install the <a href="http://www.graphviz.org">graphviz</a>
				667	toolkit, and make sure 'dot' and 'gv' are in your path. If you are running on
				668	Mac OS/X, download and install the Mac OS/X <a
				669	href="http://www.pixelglow.com/graphviz/">Graphviz program</a>, and add
				670	<tt>/Applications/Graphviz.app/Contents/MacOS/</tt> (or wherever you install
				671	it) to your path. Once in your system and path are set up, rerun the LLVM
				672	configure script and rebuild LLVM to enable this functionality.</p>
				673
				674	<p><tt>SelectionDAG</tt> has been extended to make it easier to locate
				675	<i>interesting</i> nodes in large complex graphs. From gdb, if you
				676	<tt>call DAG.setGraphColor(<i>node</i>, "<i>color</i>")</tt>, then the
				677	next <tt>call DAG.viewGraph()</tt> would highlight the node in the
				678	specified color (choices of colors can be found at <a
				679	href="http://www.graphviz.org/doc/info/colors.html">colors</a>.) More
				680	complex node attributes can be provided with <tt>call
				681	DAG.setGraphAttrs(<i>node</i>, "<i>attributes</i>")</tt> (choices can be
				682	found at <a href="http://www.graphviz.org/doc/info/attrs.html">Graph
				683	Attributes</a>.) If you want to restart and clear all the current graph
				684	attributes, then you can <tt>call DAG.clearGraphAttrs()</tt>. </p>
				685
				686	</div>
				687
				688	<!-- *********************************************************************** -->
				689	<div class="doc_section">
				690	<a name="datastructure">Picking the Right Data Structure for a Task</a>
				691	</div>
				692	<!-- *********************************************************************** -->
				693
				694	<div class="doc_text">
				695
				696	<p>LLVM has a plethora of data structures in the <tt>llvm/ADT/</tt> directory,
				697	and we commonly use STL data structures. This section describes the trade-offs
				698	you should consider when you pick one.</p>
				699
				700	<p>
				701	The first step is a choose your own adventure: do you want a sequential
				702	container, a set-like container, or a map-like container? The most important
				703	thing when choosing a container is the algorithmic properties of how you plan to
				704	access the container. Based on that, you should use:</p>
				705
				706	<ul>
				707	<li>a <a href="#ds_map">map-like</a> container if you need efficient look-up
				708	of an value based on another value. Map-like containers also support
				709	efficient queries for containment (whether a key is in the map). Map-like
				710	containers generally do not support efficient reverse mapping (values to
				711	keys). If you need that, use two maps. Some map-like containers also
				712	support efficient iteration through the keys in sorted order. Map-like
				713	containers are the most expensive sort, only use them if you need one of
				714	these capabilities.</li>
				715
				716	<li>a <a href="#ds_set">set-like</a> container if you need to put a bunch of
				717	stuff into a container that automatically eliminates duplicates. Some
				718	set-like containers support efficient iteration through the elements in
				719	sorted order. Set-like containers are more expensive than sequential
				720	containers.
				721	</li>
				722
				723	<li>a <a href="#ds_sequential">sequential</a> container provides
				724	the most efficient way to add elements and keeps track of the order they are
				725	added to the collection. They permit duplicates and support efficient
				726	iteration, but do not support efficient look-up based on a key.
				727	</li>
				728
Daniel Berlin	7ea44dc	2007-09-24 17:52:25 +0000	[diff] [blame]	729	<li>a <a href="#ds_bit">bit</a> container provides an efficient way to store and
				730	perform set operations on sets of numeric id's, while automatically
				731	eliminating duplicates. Bit containers require a maximum of 1 bit for each
				732	identifier you want to store.
				733	</li>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	734	</ul>
				735
				736	<p>
				737	Once the proper category of container is determined, you can fine tune the
				738	memory use, constant factors, and cache behaviors of access by intelligently
				739	picking a member of the category. Note that constant factors and cache behavior
				740	can be a big deal. If you have a vector that usually only contains a few
				741	elements (but could contain many), for example, it's much better to use
				742	<a href="#dss_smallvector">SmallVector</a> than <a href="#dss_vector">vector</a>
				743	. Doing so avoids (relatively) expensive malloc/free calls, which dwarf the
				744	cost of adding the elements to the container. </p>
				745
				746	</div>
				747
				748	<!-- ======================================================================= -->
				749	<div class="doc_subsection">
				750	<a name="ds_sequential">Sequential Containers (std::vector, std::list, etc)</a>
				751	</div>
				752
				753	<div class="doc_text">
				754	There are a variety of sequential containers available for you, based on your
				755	needs. Pick the first in this section that will do what you want.
				756	</div>
				757
				758	<!-- _______________________________________________________________________ -->
				759	<div class="doc_subsubsection">
				760	<a name="dss_fixedarrays">Fixed Size Arrays</a>
				761	</div>
				762
				763	<div class="doc_text">
				764	<p>Fixed size arrays are very simple and very fast. They are good if you know
				765	exactly how many elements you have, or you have a (low) upper bound on how many
				766	you have.</p>
				767	</div>
				768
				769	<!-- _______________________________________________________________________ -->
				770	<div class="doc_subsubsection">
				771	<a name="dss_heaparrays">Heap Allocated Arrays</a>
				772	</div>
				773
				774	<div class="doc_text">
				775	<p>Heap allocated arrays (new[] + delete[]) are also simple. They are good if
				776	the number of elements is variable, if you know how many elements you will need
				777	before the array is allocated, and if the array is usually large (if not,
				778	consider a <a href="#dss_smallvector">SmallVector</a>). The cost of a heap
				779	allocated array is the cost of the new/delete (aka malloc/free). Also note that
				780	if you are allocating an array of a type with a constructor, the constructor and
				781	destructors will be run for every element in the array (re-sizable vectors only
				782	construct those elements actually used).</p>
				783	</div>
				784
				785	<!-- _______________________________________________________________________ -->
				786	<div class="doc_subsubsection">
				787	<a name="dss_smallvector">"llvm/ADT/SmallVector.h"</a>
				788	</div>
				789
				790	<div class="doc_text">
				791	<p><tt>SmallVector<Type, N></tt> is a simple class that looks and smells
				792	just like <tt>vector<Type></tt>:
				793	it supports efficient iteration, lays out elements in memory order (so you can
				794	do pointer arithmetic between elements), supports efficient push_back/pop_back
				795	operations, supports efficient random access to its elements, etc.</p>
				796
				797	<p>The advantage of SmallVector is that it allocates space for
				798	some number of elements (N) <b>in the object itself</b>. Because of this, if
				799	the SmallVector is dynamically smaller than N, no malloc is performed. This can
				800	be a big win in cases where the malloc/free call is far more expensive than the
				801	code that fiddles around with the elements.</p>
				802
				803	<p>This is good for vectors that are "usually small" (e.g. the number of
				804	predecessors/successors of a block is usually less than 8). On the other hand,
				805	this makes the size of the SmallVector itself large, so you don't want to
				806	allocate lots of them (doing so will waste a lot of space). As such,
				807	SmallVectors are most useful when on the stack.</p>
				808
				809	<p>SmallVector also provides a nice portable and efficient replacement for
				810	<tt>alloca</tt>.</p>
				811
				812	</div>
				813
				814	<!-- _______________________________________________________________________ -->
				815	<div class="doc_subsubsection">
				816	<a name="dss_vector"><vector></a>
				817	</div>
				818
				819	<div class="doc_text">
				820	<p>
				821	std::vector is well loved and respected. It is useful when SmallVector isn't:
				822	when the size of the vector is often large (thus the small optimization will
				823	rarely be a benefit) or if you will be allocating many instances of the vector
				824	itself (which would waste space for elements that aren't in the container).
				825	vector is also useful when interfacing with code that expects vectors :).
				826	</p>
				827
				828	<p>One worthwhile note about std::vector: avoid code like this:</p>
				829
				830	<div class="doc_code">
				831	<pre>
				832	for ( ... ) {
				833	std::vector<foo> V;
				834	use V;
				835	}
				836	</pre>
				837	</div>
				838
				839	<p>Instead, write this as:</p>
				840
				841	<div class="doc_code">
				842	<pre>
				843	std::vector<foo> V;
				844	for ( ... ) {
				845	use V;
				846	V.clear();
				847	}
				848	</pre>
				849	</div>
				850
				851	<p>Doing so will save (at least) one heap allocation and free per iteration of
				852	the loop.</p>
				853
				854	</div>
				855
				856	<!-- _______________________________________________________________________ -->
				857	<div class="doc_subsubsection">
				858	<a name="dss_deque"><deque></a>
				859	</div>
				860
				861	<div class="doc_text">
				862	<p>std::deque is, in some senses, a generalized version of std::vector. Like
				863	std::vector, it provides constant time random access and other similar
				864	properties, but it also provides efficient access to the front of the list. It
				865	does not guarantee continuity of elements within memory.</p>
				866
				867	<p>In exchange for this extra flexibility, std::deque has significantly higher
				868	constant factor costs than std::vector. If possible, use std::vector or
				869	something cheaper.</p>
				870	</div>
				871
				872	<!-- _______________________________________________________________________ -->
				873	<div class="doc_subsubsection">
				874	<a name="dss_list"><list></a>
				875	</div>
				876
				877	<div class="doc_text">
				878	<p>std::list is an extremely inefficient class that is rarely useful.
				879	It performs a heap allocation for every element inserted into it, thus having an
				880	extremely high constant factor, particularly for small data types. std::list
				881	also only supports bidirectional iteration, not random access iteration.</p>
				882
				883	<p>In exchange for this high cost, std::list supports efficient access to both
				884	ends of the list (like std::deque, but unlike std::vector or SmallVector). In
				885	addition, the iterator invalidation characteristics of std::list are stronger
				886	than that of a vector class: inserting or removing an element into the list does
				887	not invalidate iterator or pointers to other elements in the list.</p>
				888	</div>
				889
				890	<!-- _______________________________________________________________________ -->
				891	<div class="doc_subsubsection">
Gabor Greif	bb17f65	2009-02-27 11:37:41 +0000	[diff] [blame]	892	<a name="dss_ilist">llvm/ADT/ilist.h</a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	893	</div>
				894
				895	<div class="doc_text">
				896	<p><tt>ilist<T></tt> implements an 'intrusive' doubly-linked list. It is
				897	intrusive, because it requires the element to store and provide access to the
				898	prev/next pointers for the list.</p>
				899
Gabor Greif	b6b21ec	2009-02-27 12:02:19 +0000	[diff] [blame]	900	<p><tt>ilist</tt> has the same drawbacks as <tt>std::list</tt>, and additionally
				901	requires an <tt>ilist_traits</tt> implementation for the element type, but it
				902	provides some novel characteristics. In particular, it can efficiently store
				903	polymorphic objects, the traits class is informed when an element is inserted or
Gabor Greif	e39f0e7	2009-03-12 09:47:03 +0000	[diff] [blame]	904	removed from the list, and <tt>ilist</tt>s are guaranteed to support a
				905	constant-time splice operation.</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	906
Gabor Greif	e39f0e7	2009-03-12 09:47:03 +0000	[diff] [blame]	907	<p>These properties are exactly what we want for things like
				908	<tt>Instruction</tt>s and basic blocks, which is why these are implemented with
				909	<tt>ilist</tt>s.</p>
Gabor Greif	bb17f65	2009-02-27 11:37:41 +0000	[diff] [blame]	910
				911	Related classes of interest are explained in the following subsections:
				912	<ul>
Gabor Greif	a17abe1	2009-02-27 13:28:07 +0000	[diff] [blame]	913	<li><a href="#dss_ilist_traits">ilist_traits</a></li>
Gabor Greif	b6b21ec	2009-02-27 12:02:19 +0000	[diff] [blame]	914	<li><a href="#dss_iplist">iplist</a></li>
Gabor Greif	bb17f65	2009-02-27 11:37:41 +0000	[diff] [blame]	915	<li><a href="#dss_ilist_node">llvm/ADT/ilist_node.h</a></li>
Gabor Greif	d970d69	2009-03-12 10:30:31 +0000	[diff] [blame]	916	<li><a href="#dss_ilist_sentinel">Sentinels</a></li>
Gabor Greif	bb17f65	2009-02-27 11:37:41 +0000	[diff] [blame]	917	</ul>
				918	</div>
				919
				920	<!-- _______________________________________________________________________ -->
				921	<div class="doc_subsubsection">
Gabor Greif	a17abe1	2009-02-27 13:28:07 +0000	[diff] [blame]	922	<a name="dss_ilist_traits">ilist_traits</a>
				923	</div>
				924
				925	<div class="doc_text">
				926	<p><tt>ilist_traits<T></tt> is <tt>ilist<T></tt>'s customization
				927	mechanism. <tt>iplist<T></tt> (and consequently <tt>ilist<T></tt>)
				928	publicly derive from this traits class.</p>
				929	</div>
				930
				931	<!-- _______________________________________________________________________ -->
				932	<div class="doc_subsubsection">
Gabor Greif	b6b21ec	2009-02-27 12:02:19 +0000	[diff] [blame]	933	<a name="dss_iplist">iplist</a>
				934	</div>
				935
				936	<div class="doc_text">
				937	<p><tt>iplist<T></tt> is <tt>ilist<T></tt>'s base and as such
Gabor Greif	e39f0e7	2009-03-12 09:47:03 +0000	[diff] [blame]	938	supports a slightly narrower interface. Notably, inserters from
				939	<tt>T&</tt> are absent.</p>
Gabor Greif	a17abe1	2009-02-27 13:28:07 +0000	[diff] [blame]	940
				941	<p><tt>ilist_traits<T></tt> is a public base of this class and can be
				942	used for a wide variety of customizations.</p>
Gabor Greif	b6b21ec	2009-02-27 12:02:19 +0000	[diff] [blame]	943	</div>
				944
				945	<!-- _______________________________________________________________________ -->
				946	<div class="doc_subsubsection">
Gabor Greif	bb17f65	2009-02-27 11:37:41 +0000	[diff] [blame]	947	<a name="dss_ilist_node">llvm/ADT/ilist_node.h</a>
				948	</div>
				949
				950	<div class="doc_text">
				951	<p><tt>ilist_node<T></tt> implements a the forward and backward links
				952	that are expected by the <tt>ilist<T></tt> (and analogous containers)
				953	in the default manner.</p>
				954
				955	<p><tt>ilist_node<T></tt>s are meant to be embedded in the node type
Gabor Greif	e39f0e7	2009-03-12 09:47:03 +0000	[diff] [blame]	956	<tt>T</tt>, usually <tt>T</tt> publicly derives from
				957	<tt>ilist_node<T></tt>.</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	958	</div>
				959
				960	<!-- _______________________________________________________________________ -->
				961	<div class="doc_subsubsection">
Gabor Greif	d970d69	2009-03-12 10:30:31 +0000	[diff] [blame]	962	<a name="dss_ilist_sentinel">Sentinels</a>
				963	</div>
				964
				965	<div class="doc_text">
				966	<p><tt>ilist</tt>s have another speciality that must be considered. To be a good
				967	citizen in the C++ ecosystem, it needs to support the standard container
				968	operations, such as <tt>begin</tt> and <tt>end</tt> iterators, etc. Also, the
				969	<tt>operator--</tt> must work correctly on the <tt>end</tt> iterator in the
				970	case of non-empty <tt>ilist</tt>s.</p>
				971
				972	<p>The only sensible solution to this problem is to allocate a so-called
				973	<i>sentinel</i> along with the intrusive list, which serves as the <tt>end</tt>
				974	iterator, providing the back-link to the last element. However conforming to the
				975	C++ convention it is illegal to <tt>operator++</tt> beyond the sentinel and it
				976	also must not be dereferenced.</p>
				977
				978	<p>These constraints allow for some implementation freedom to the <tt>ilist</tt>
				979	how to allocate and store the sentinel. The corresponding policy is dictated
				980	by <tt>ilist_traits<T></tt>. By default a <tt>T</tt> gets heap-allocated
				981	whenever the need for a sentinel arises.</p>
				982
				983	<p>While the default policy is sufficient in most cases, it may break down when
				984	<tt>T</tt> does not provide a default constructor. Also, in the case of many
				985	instances of <tt>ilist</tt>s, the memory overhead of the associated sentinels
				986	is wasted. To alleviate the situation with numerous and voluminous
				987	<tt>T</tt>-sentinels, sometimes a trick is employed, leading to <i>ghostly
				988	sentinels</i>.</p>
				989
				990	<p>Ghostly sentinels are obtained by specially-crafted <tt>ilist_traits<T></tt>
				991	which superpose the sentinel with the <tt>ilist</tt> instance in memory. Pointer
				992	arithmetic is used to obtain the sentinel, which is relative to the
				993	<tt>ilist</tt>'s <tt>this</tt> pointer. The <tt>ilist</tt> is augmented by an
				994	extra pointer, which serves as the back-link of the sentinel. This is the only
				995	field in the ghostly sentinel which can be legally accessed.</p>
				996	</div>
				997
				998	<!-- _______________________________________________________________________ -->
				999	<div class="doc_subsubsection">
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1000	<a name="dss_other">Other Sequential Container options</a>
				1001	</div>
				1002
				1003	<div class="doc_text">
				1004	<p>Other STL containers are available, such as std::string.</p>
				1005
				1006	<p>There are also various STL adapter classes such as std::queue,
				1007	std::priority_queue, std::stack, etc. These provide simplified access to an
				1008	underlying container but don't affect the cost of the container itself.</p>
				1009
				1010	</div>
				1011
				1012
				1013	<!-- ======================================================================= -->
				1014	<div class="doc_subsection">
				1015	<a name="ds_set">Set-Like Containers (std::set, SmallSet, SetVector, etc)</a>
				1016	</div>
				1017
				1018	<div class="doc_text">
				1019
				1020	<p>Set-like containers are useful when you need to canonicalize multiple values
				1021	into a single representation. There are several different choices for how to do
				1022	this, providing various trade-offs.</p>
				1023
				1024	</div>
				1025
				1026
				1027	<!-- _______________________________________________________________________ -->
				1028	<div class="doc_subsubsection">
				1029	<a name="dss_sortedvectorset">A sorted 'vector'</a>
				1030	</div>
				1031
				1032	<div class="doc_text">
				1033
				1034	<p>If you intend to insert a lot of elements, then do a lot of queries, a
				1035	great approach is to use a vector (or other sequential container) with
				1036	std::sort+std::unique to remove duplicates. This approach works really well if
				1037	your usage pattern has these two distinct phases (insert then query), and can be
				1038	coupled with a good choice of <a href="#ds_sequential">sequential container</a>.
				1039	</p>
				1040
				1041	<p>
				1042	This combination provides the several nice properties: the result data is
				1043	contiguous in memory (good for cache locality), has few allocations, is easy to
				1044	address (iterators in the final vector are just indices or pointers), and can be
				1045	efficiently queried with a standard binary or radix search.</p>
				1046
				1047	</div>
				1048
				1049	<!-- _______________________________________________________________________ -->
				1050	<div class="doc_subsubsection">
				1051	<a name="dss_smallset">"llvm/ADT/SmallSet.h"</a>
				1052	</div>
				1053
				1054	<div class="doc_text">
				1055
				1056	<p>If you have a set-like data structure that is usually small and whose elements
				1057	are reasonably small, a <tt>SmallSet<Type, N></tt> is a good choice. This set
				1058	has space for N elements in place (thus, if the set is dynamically smaller than
				1059	N, no malloc traffic is required) and accesses them with a simple linear search.
				1060	When the set grows beyond 'N' elements, it allocates a more expensive representation that
				1061	guarantees efficient access (for most types, it falls back to std::set, but for
				1062	pointers it uses something far better, <a
				1063	href="#dss_smallptrset">SmallPtrSet</a>).</p>
				1064
				1065	<p>The magic of this class is that it handles small sets extremely efficiently,
				1066	but gracefully handles extremely large sets without loss of efficiency. The
				1067	drawback is that the interface is quite small: it supports insertion, queries
				1068	and erasing, but does not support iteration.</p>
				1069
				1070	</div>
				1071
				1072	<!-- _______________________________________________________________________ -->
				1073	<div class="doc_subsubsection">
				1074	<a name="dss_smallptrset">"llvm/ADT/SmallPtrSet.h"</a>
				1075	</div>
				1076
				1077	<div class="doc_text">
				1078
				1079	<p>SmallPtrSet has all the advantages of SmallSet (and a SmallSet of pointers is
				1080	transparently implemented with a SmallPtrSet), but also supports iterators. If
				1081	more than 'N' insertions are performed, a single quadratically
				1082	probed hash table is allocated and grows as needed, providing extremely
				1083	efficient access (constant time insertion/deleting/queries with low constant
				1084	factors) and is very stingy with malloc traffic.</p>
				1085
				1086	<p>Note that, unlike std::set, the iterators of SmallPtrSet are invalidated
				1087	whenever an insertion occurs. Also, the values visited by the iterators are not
				1088	visited in sorted order.</p>
				1089
				1090	</div>
				1091
				1092	<!-- _______________________________________________________________________ -->
				1093	<div class="doc_subsubsection">
Chris Lattner	77ab46d	2007-09-30 00:58:59 +0000	[diff] [blame]	1094	<a name="dss_denseset">"llvm/ADT/DenseSet.h"</a>
				1095	</div>
				1096
				1097	<div class="doc_text">
				1098
				1099	<p>
				1100	DenseSet is a simple quadratically probed hash table. It excels at supporting
				1101	small values: it uses a single allocation to hold all of the pairs that
				1102	are currently inserted in the set. DenseSet is a great way to unique small
				1103	values that are not simple pointers (use <a
				1104	href="#dss_smallptrset">SmallPtrSet</a> for pointers). Note that DenseSet has
				1105	the same requirements for the value type that <a
				1106	href="#dss_densemap">DenseMap</a> has.
				1107	</p>
				1108
				1109	</div>
				1110
				1111	<!-- _______________________________________________________________________ -->
				1112	<div class="doc_subsubsection">
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1113	<a name="dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a>
				1114	</div>
				1115
				1116	<div class="doc_text">
				1117
				1118	<p>
				1119	FoldingSet is an aggregate class that is really good at uniquing
				1120	expensive-to-create or polymorphic objects. It is a combination of a chained
				1121	hash table with intrusive links (uniqued objects are required to inherit from
				1122	FoldingSetNode) that uses <a href="#dss_smallvector">SmallVector</a> as part of
				1123	its ID process.</p>
				1124
				1125	<p>Consider a case where you want to implement a "getOrCreateFoo" method for
				1126	a complex object (for example, a node in the code generator). The client has a
				1127	description of what it wants to generate (it knows the opcode and all the
				1128	operands), but we don't want to 'new' a node, then try inserting it into a set
				1129	only to find out it already exists, at which point we would have to delete it
				1130	and return the node that already exists.
				1131	</p>
				1132
				1133	<p>To support this style of client, FoldingSet perform a query with a
				1134	FoldingSetNodeID (which wraps SmallVector) that can be used to describe the
				1135	element that we want to query for. The query either returns the element
				1136	matching the ID or it returns an opaque ID that indicates where insertion should
				1137	take place. Construction of the ID usually does not require heap traffic.</p>
				1138
				1139	<p>Because FoldingSet uses intrusive links, it can support polymorphic objects
				1140	in the set (for example, you can have SDNode instances mixed with LoadSDNodes).
				1141	Because the elements are individually allocated, pointers to the elements are
				1142	stable: inserting or removing elements does not invalidate any pointers to other
				1143	elements.
				1144	</p>
				1145
				1146	</div>
				1147
				1148	<!-- _______________________________________________________________________ -->
				1149	<div class="doc_subsubsection">
				1150	<a name="dss_set"><set></a>
				1151	</div>
				1152
				1153	<div class="doc_text">
				1154
				1155	<p><tt>std::set</tt> is a reasonable all-around set class, which is decent at
				1156	many things but great at nothing. std::set allocates memory for each element
				1157	inserted (thus it is very malloc intensive) and typically stores three pointers
				1158	per element in the set (thus adding a large amount of per-element space
				1159	overhead). It offers guaranteed log(n) performance, which is not particularly
				1160	fast from a complexity standpoint (particularly if the elements of the set are
				1161	expensive to compare, like strings), and has extremely high constant factors for
				1162	lookup, insertion and removal.</p>
				1163
				1164	<p>The advantages of std::set are that its iterators are stable (deleting or
				1165	inserting an element from the set does not affect iterators or pointers to other
				1166	elements) and that iteration over the set is guaranteed to be in sorted order.
				1167	If the elements in the set are large, then the relative overhead of the pointers
				1168	and malloc traffic is not a big deal, but if the elements of the set are small,
				1169	std::set is almost never a good choice.</p>
				1170
				1171	</div>
				1172
				1173	<!-- _______________________________________________________________________ -->
				1174	<div class="doc_subsubsection">
				1175	<a name="dss_setvector">"llvm/ADT/SetVector.h"</a>
				1176	</div>
				1177
				1178	<div class="doc_text">
				1179	<p>LLVM's SetVector<Type> is an adapter class that combines your choice of
				1180	a set-like container along with a <a href="#ds_sequential">Sequential
				1181	Container</a>. The important property
				1182	that this provides is efficient insertion with uniquing (duplicate elements are
				1183	ignored) with iteration support. It implements this by inserting elements into
				1184	both a set-like container and the sequential container, using the set-like
				1185	container for uniquing and the sequential container for iteration.
				1186	</p>
				1187
				1188	<p>The difference between SetVector and other sets is that the order of
				1189	iteration is guaranteed to match the order of insertion into the SetVector.
				1190	This property is really important for things like sets of pointers. Because
				1191	pointer values are non-deterministic (e.g. vary across runs of the program on
				1192	different machines), iterating over the pointers in the set will
				1193	not be in a well-defined order.</p>
				1194
				1195	<p>
				1196	The drawback of SetVector is that it requires twice as much space as a normal
				1197	set and has the sum of constant factors from the set-like container and the
				1198	sequential container that it uses. Use it only if you need to iterate over
				1199	the elements in a deterministic order. SetVector is also expensive to delete
				1200	elements out of (linear time), unless you use it's "pop_back" method, which is
				1201	faster.
				1202	</p>
				1203
				1204	<p>SetVector is an adapter class that defaults to using std::vector and std::set
				1205	for the underlying containers, so it is quite expensive. However,
				1206	<tt>"llvm/ADT/SetVector.h"</tt> also provides a SmallSetVector class, which
				1207	defaults to using a SmallVector and SmallSet of a specified size. If you use
				1208	this, and if your sets are dynamically smaller than N, you will save a lot of
				1209	heap traffic.</p>
				1210
				1211	</div>
				1212
				1213	<!-- _______________________________________________________________________ -->
				1214	<div class="doc_subsubsection">
				1215	<a name="dss_uniquevector">"llvm/ADT/UniqueVector.h"</a>
				1216	</div>
				1217
				1218	<div class="doc_text">
				1219
				1220	<p>
				1221	UniqueVector is similar to <a href="#dss_setvector">SetVector</a>, but it
				1222	retains a unique ID for each element inserted into the set. It internally
				1223	contains a map and a vector, and it assigns a unique ID for each value inserted
				1224	into the set.</p>
				1225
				1226	<p>UniqueVector is very expensive: its cost is the sum of the cost of
				1227	maintaining both the map and vector, it has high complexity, high constant
				1228	factors, and produces a lot of malloc traffic. It should be avoided.</p>
				1229
				1230	</div>
				1231
				1232
				1233	<!-- _______________________________________________________________________ -->
				1234	<div class="doc_subsubsection">
				1235	<a name="dss_otherset">Other Set-Like Container Options</a>
				1236	</div>
				1237
				1238	<div class="doc_text">
				1239
				1240	<p>
				1241	The STL provides several other options, such as std::multiset and the various
Chris Lattner	86a63d0	2009-03-09 05:20:45 +0000	[diff] [blame]	1242	"hash_set" like containers (whether from C++ TR1 or from the SGI library). We
				1243	never use hash_set and unordered_set because they are generally very expensive
				1244	(each insertion requires a malloc) and very non-portable.
				1245	</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1246
				1247	<p>std::multiset is useful if you're not interested in elimination of
				1248	duplicates, but has all the drawbacks of std::set. A sorted vector (where you
				1249	don't delete duplicate entries) or some other approach is almost always
				1250	better.</p>
				1251
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1252	</div>
				1253
				1254	<!-- ======================================================================= -->
				1255	<div class="doc_subsection">
				1256	<a name="ds_map">Map-Like Containers (std::map, DenseMap, etc)</a>
				1257	</div>
				1258
				1259	<div class="doc_text">
				1260	Map-like containers are useful when you want to associate data to a key. As
				1261	usual, there are a lot of different ways to do this. :)
				1262	</div>
				1263
				1264	<!-- _______________________________________________________________________ -->
				1265	<div class="doc_subsubsection">
				1266	<a name="dss_sortedvectormap">A sorted 'vector'</a>
				1267	</div>
				1268
				1269	<div class="doc_text">
				1270
				1271	<p>
				1272	If your usage pattern follows a strict insert-then-query approach, you can
				1273	trivially use the same approach as <a href="#dss_sortedvectorset">sorted vectors
				1274	for set-like containers</a>. The only difference is that your query function
				1275	(which uses std::lower_bound to get efficient log(n) lookup) should only compare
				1276	the key, not both the key and value. This yields the same advantages as sorted
				1277	vectors for sets.
				1278	</p>
				1279	</div>
				1280
				1281	<!-- _______________________________________________________________________ -->
				1282	<div class="doc_subsubsection">
				1283	<a name="dss_stringmap">"llvm/ADT/StringMap.h"</a>
				1284	</div>
				1285
				1286	<div class="doc_text">
				1287
				1288	<p>
				1289	Strings are commonly used as keys in maps, and they are difficult to support
				1290	efficiently: they are variable length, inefficient to hash and compare when
				1291	long, expensive to copy, etc. StringMap is a specialized container designed to
				1292	cope with these issues. It supports mapping an arbitrary range of bytes to an
				1293	arbitrary other object.</p>
				1294
				1295	<p>The StringMap implementation uses a quadratically-probed hash table, where
				1296	the buckets store a pointer to the heap allocated entries (and some other
				1297	stuff). The entries in the map must be heap allocated because the strings are
				1298	variable length. The string data (key) and the element object (value) are
				1299	stored in the same allocation with the string data immediately after the element
				1300	object. This container guarantees the "<tt>(char*)(&Value+1)</tt>" points
				1301	to the key string for a value.</p>
				1302
				1303	<p>The StringMap is very fast for several reasons: quadratic probing is very
				1304	cache efficient for lookups, the hash value of strings in buckets is not
				1305	recomputed when lookup up an element, StringMap rarely has to touch the
				1306	memory for unrelated objects when looking up a value (even when hash collisions
				1307	happen), hash table growth does not recompute the hash values for strings
				1308	already in the table, and each pair in the map is store in a single allocation
				1309	(the string data is stored in the same allocation as the Value of a pair).</p>
				1310
				1311	<p>StringMap also provides query methods that take byte ranges, so it only ever
				1312	copies a string if a value is inserted into the table.</p>
				1313	</div>
				1314
				1315	<!-- _______________________________________________________________________ -->
				1316	<div class="doc_subsubsection">
				1317	<a name="dss_indexedmap">"llvm/ADT/IndexedMap.h"</a>
				1318	</div>
				1319
				1320	<div class="doc_text">
				1321	<p>
				1322	IndexedMap is a specialized container for mapping small dense integers (or
				1323	values that can be mapped to small dense integers) to some other type. It is
				1324	internally implemented as a vector with a mapping function that maps the keys to
				1325	the dense integer range.
				1326	</p>
				1327
				1328	<p>
				1329	This is useful for cases like virtual registers in the LLVM code generator: they
				1330	have a dense mapping that is offset by a compile-time constant (the first
				1331	virtual register ID).</p>
				1332
				1333	</div>
				1334
				1335	<!-- _______________________________________________________________________ -->
				1336	<div class="doc_subsubsection">
				1337	<a name="dss_densemap">"llvm/ADT/DenseMap.h"</a>
				1338	</div>
				1339
				1340	<div class="doc_text">
				1341
				1342	<p>
				1343	DenseMap is a simple quadratically probed hash table. It excels at supporting
				1344	small keys and values: it uses a single allocation to hold all of the pairs that
				1345	are currently inserted in the map. DenseMap is a great way to map pointers to
				1346	pointers, or map other small types to each other.
				1347	</p>
				1348
				1349	<p>
				1350	There are several aspects of DenseMap that you should be aware of, however. The
				1351	iterators in a densemap are invalidated whenever an insertion occurs, unlike
				1352	map. Also, because DenseMap allocates space for a large number of key/value
				1353	pairs (it starts with 64 by default), it will waste a lot of space if your keys
				1354	or values are large. Finally, you must implement a partial specialization of
Chris Lattner	92eea07	2007-09-17 18:34:04 +0000	[diff] [blame]	1355	DenseMapInfo for the key that you want, if it isn't already supported. This
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1356	is required to tell DenseMap about two special marker values (which can never be
				1357	inserted into the map) that it needs internally.</p>
				1358
				1359	</div>
				1360
				1361	<!-- _______________________________________________________________________ -->
				1362	<div class="doc_subsubsection">
				1363	<a name="dss_map"><map></a>
				1364	</div>
				1365
				1366	<div class="doc_text">
				1367
				1368	<p>
				1369	std::map has similar characteristics to <a href="#dss_set">std::set</a>: it uses
				1370	a single allocation per pair inserted into the map, it offers log(n) lookup with
				1371	an extremely large constant factor, imposes a space penalty of 3 pointers per
				1372	pair in the map, etc.</p>
				1373
				1374	<p>std::map is most useful when your keys or values are very large, if you need
				1375	to iterate over the collection in sorted order, or if you need stable iterators
				1376	into the map (i.e. they don't get invalidated if an insertion or deletion of
				1377	another element takes place).</p>
				1378
				1379	</div>
				1380
				1381	<!-- _______________________________________________________________________ -->
				1382	<div class="doc_subsubsection">
				1383	<a name="dss_othermap">Other Map-Like Container Options</a>
				1384	</div>
				1385
				1386	<div class="doc_text">
				1387
				1388	<p>
				1389	The STL provides several other options, such as std::multimap and the various
Chris Lattner	86a63d0	2009-03-09 05:20:45 +0000	[diff] [blame]	1390	"hash_map" like containers (whether from C++ TR1 or from the SGI library). We
				1391	never use hash_set and unordered_set because they are generally very expensive
				1392	(each insertion requires a malloc) and very non-portable.</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1393
				1394	<p>std::multimap is useful if you want to map a key to multiple values, but has
				1395	all the drawbacks of std::map. A sorted vector or some other approach is almost
				1396	always better.</p>
				1397
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1398	</div>
				1399
Daniel Berlin	7ea44dc	2007-09-24 17:52:25 +0000	[diff] [blame]	1400	<!-- ======================================================================= -->
				1401	<div class="doc_subsection">
				1402	<a name="ds_bit">Bit storage containers (BitVector, SparseBitVector)</a>
				1403	</div>
				1404
				1405	<div class="doc_text">
Chris Lattner	62a4eae	2007-09-25 22:37:50 +0000	[diff] [blame]	1406	<p>Unlike the other containers, there are only two bit storage containers, and
				1407	choosing when to use each is relatively straightforward.</p>
				1408
				1409	<p>One additional option is
				1410	<tt>std::vector<bool></tt>: we discourage its use for two reasons 1) the
				1411	implementation in many common compilers (e.g. commonly available versions of
				1412	GCC) is extremely inefficient and 2) the C++ standards committee is likely to
				1413	deprecate this container and/or change it significantly somehow. In any case,
				1414	please don't use it.</p>
Daniel Berlin	7ea44dc	2007-09-24 17:52:25 +0000	[diff] [blame]	1415	</div>
				1416
				1417	<!-- _______________________________________________________________________ -->
				1418	<div class="doc_subsubsection">
				1419	<a name="dss_bitvector">BitVector</a>
				1420	</div>
				1421
				1422	<div class="doc_text">
				1423	<p> The BitVector container provides a fixed size set of bits for manipulation.
				1424	It supports individual bit setting/testing, as well as set operations. The set
				1425	operations take time O(size of bitvector), but operations are performed one word
				1426	at a time, instead of one bit at a time. This makes the BitVector very fast for
				1427	set operations compared to other containers. Use the BitVector when you expect
				1428	the number of set bits to be high (IE a dense set).
				1429	</p>
				1430	</div>
				1431
				1432	<!-- _______________________________________________________________________ -->
				1433	<div class="doc_subsubsection">
				1434	<a name="dss_sparsebitvector">SparseBitVector</a>
				1435	</div>
				1436
				1437	<div class="doc_text">
				1438	<p> The SparseBitVector container is much like BitVector, with one major
				1439	difference: Only the bits that are set, are stored. This makes the
				1440	SparseBitVector much more space efficient than BitVector when the set is sparse,
				1441	as well as making set operations O(number of set bits) instead of O(size of
				1442	universe). The downside to the SparseBitVector is that setting and testing of random bits is O(N), and on large SparseBitVectors, this can be slower than BitVector. In our implementation, setting or testing bits in sorted order
				1443	(either forwards or reverse) is O(1) worst case. Testing and setting bits within 128 bits (depends on size) of the current bit is also O(1). As a general statement, testing/setting bits in a SparseBitVector is O(distance away from last set bit).
				1444	</p>
				1445	</div>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1446
				1447	<!-- *********************************************************************** -->
				1448	<div class="doc_section">
				1449	<a name="common">Helpful Hints for Common Operations</a>
				1450	</div>
				1451	<!-- *********************************************************************** -->
				1452
				1453	<div class="doc_text">
				1454
				1455	<p>This section describes how to perform some very simple transformations of
				1456	LLVM code. This is meant to give examples of common idioms used, showing the
				1457	practical side of LLVM transformations. <p> Because this is a "how-to" section,
				1458	you should also read about the main classes that you will be working with. The
				1459	<a href="#coreclasses">Core LLVM Class Hierarchy Reference</a> contains details
				1460	and descriptions of the main classes that you should know about.</p>
				1461
				1462	</div>
				1463
				1464	<!-- NOTE: this section should be heavy on example code -->
				1465	<!-- ======================================================================= -->
				1466	<div class="doc_subsection">
				1467	<a name="inspection">Basic Inspection and Traversal Routines</a>
				1468	</div>
				1469
				1470	<div class="doc_text">
				1471
				1472	<p>The LLVM compiler infrastructure have many different data structures that may
				1473	be traversed. Following the example of the C++ standard template library, the
				1474	techniques used to traverse these various data structures are all basically the
				1475	same. For a enumerable sequence of values, the <tt>XXXbegin()</tt> function (or
				1476	method) returns an iterator to the start of the sequence, the <tt>XXXend()</tt>
				1477	function returns an iterator pointing to one past the last valid element of the
				1478	sequence, and there is some <tt>XXXiterator</tt> data type that is common
				1479	between the two operations.</p>
				1480
				1481	<p>Because the pattern for iteration is common across many different aspects of
				1482	the program representation, the standard template library algorithms may be used
				1483	on them, and it is easier to remember how to iterate. First we show a few common
				1484	examples of the data structures that need to be traversed. Other data
				1485	structures are traversed in very similar ways.</p>
				1486
				1487	</div>
				1488
				1489	<!-- _______________________________________________________________________ -->
				1490	<div class="doc_subsubsection">
				1491	<a name="iterate_function">Iterating over the </a><a
				1492	href="#BasicBlock"><tt>BasicBlock</tt></a>s in a <a
				1493	href="#Function"><tt>Function</tt></a>
				1494	</div>
				1495
				1496	<div class="doc_text">
				1497
				1498	<p>It's quite common to have a <tt>Function</tt> instance that you'd like to
				1499	transform in some way; in particular, you'd like to manipulate its
				1500	<tt>BasicBlock</tt>s. To facilitate this, you'll need to iterate over all of
				1501	the <tt>BasicBlock</tt>s that constitute the <tt>Function</tt>. The following is
				1502	an example that prints the name of a <tt>BasicBlock</tt> and the number of
				1503	<tt>Instruction</tt>s it contains:</p>
				1504
				1505	<div class="doc_code">
				1506	<pre>
				1507	// <i>func is a pointer to a Function instance</i>
				1508	for (Function::iterator i = func->begin(), e = func->end(); i != e; ++i)
				1509	// <i>Print out the name of the basic block if it has one, and then the</i>
				1510	// <i>number of instructions that it contains</i>
				1511	llvm::cerr << "Basic block (name=" << i->getName() << ") has "
				1512	<< i->size() << " instructions.\n";
				1513	</pre>
				1514	</div>
				1515
				1516	<p>Note that i can be used as if it were a pointer for the purposes of
				1517	invoking member functions of the <tt>Instruction</tt> class. This is
				1518	because the indirection operator is overloaded for the iterator
				1519	classes. In the above code, the expression <tt>i->size()</tt> is
				1520	exactly equivalent to <tt>(*i).size()</tt> just like you'd expect.</p>
				1521
				1522	</div>
				1523
				1524	<!-- _______________________________________________________________________ -->
				1525	<div class="doc_subsubsection">
				1526	<a name="iterate_basicblock">Iterating over the </a><a
				1527	href="#Instruction"><tt>Instruction</tt></a>s in a <a
				1528	href="#BasicBlock"><tt>BasicBlock</tt></a>
				1529	</div>
				1530
				1531	<div class="doc_text">
				1532
				1533	<p>Just like when dealing with <tt>BasicBlock</tt>s in <tt>Function</tt>s, it's
				1534	easy to iterate over the individual instructions that make up
				1535	<tt>BasicBlock</tt>s. Here's a code snippet that prints out each instruction in
				1536	a <tt>BasicBlock</tt>:</p>
				1537
				1538	<div class="doc_code">
				1539	<pre>
				1540	// <i>blk is a pointer to a BasicBlock instance</i>
				1541	for (BasicBlock::iterator i = blk->begin(), e = blk->end(); i != e; ++i)
				1542	// <i>The next statement works since operator<<(ostream&,...)</i>
				1543	// <i>is overloaded for Instruction&</i>
				1544	llvm::cerr << *i << "\n";
				1545	</pre>
				1546	</div>
				1547
				1548	<p>However, this isn't really the best way to print out the contents of a
				1549	<tt>BasicBlock</tt>! Since the ostream operators are overloaded for virtually
				1550	anything you'll care about, you could have just invoked the print routine on the
				1551	basic block itself: <tt>llvm::cerr << *blk << "\n";</tt>.</p>
				1552
				1553	</div>
				1554
				1555	<!-- _______________________________________________________________________ -->
				1556	<div class="doc_subsubsection">
				1557	<a name="iterate_institer">Iterating over the </a><a
				1558	href="#Instruction"><tt>Instruction</tt></a>s in a <a
				1559	href="#Function"><tt>Function</tt></a>
				1560	</div>
				1561
				1562	<div class="doc_text">
				1563
				1564	<p>If you're finding that you commonly iterate over a <tt>Function</tt>'s
				1565	<tt>BasicBlock</tt>s and then that <tt>BasicBlock</tt>'s <tt>Instruction</tt>s,
				1566	<tt>InstIterator</tt> should be used instead. You'll need to include <a
				1567	href="/doxygen/InstIterator_8h-source.html"><tt>llvm/Support/InstIterator.h</tt></a>,
				1568	and then instantiate <tt>InstIterator</tt>s explicitly in your code. Here's a
				1569	small example that shows how to dump all instructions in a function to the standard error stream:<p>
				1570
				1571	<div class="doc_code">
				1572	<pre>
				1573	#include "<a href="/doxygen/InstIterator_8h-source.html">llvm/Support/InstIterator.h</a>"
				1574
				1575	// <i>F is a pointer to a Function instance</i>
Chris Lattner	fd62ee7	2008-06-04 18:20:42 +0000	[diff] [blame]	1576	for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
				1577	llvm::cerr << *I << "\n";
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1578	</pre>
				1579	</div>
				1580
				1581	<p>Easy, isn't it? You can also use <tt>InstIterator</tt>s to fill a
				1582	work list with its initial contents. For example, if you wanted to
				1583	initialize a work list to contain all instructions in a <tt>Function</tt>
				1584	F, all you would need to do is something like:</p>
				1585
				1586	<div class="doc_code">
				1587	<pre>
				1588	std::set<Instruction*> worklist;
Chris Lattner	fd62ee7	2008-06-04 18:20:42 +0000	[diff] [blame]	1589	// or better yet, SmallPtrSet<Instruction*, 64> worklist;
				1590
				1591	for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
				1592	worklist.insert(&*I);
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1593	</pre>
				1594	</div>
				1595
				1596	<p>The STL set <tt>worklist</tt> would now contain all instructions in the
				1597	<tt>Function</tt> pointed to by F.</p>
				1598
				1599	</div>
				1600
				1601	<!-- _______________________________________________________________________ -->
				1602	<div class="doc_subsubsection">
				1603	<a name="iterate_convert">Turning an iterator into a class pointer (and
				1604	vice-versa)</a>
				1605	</div>
				1606
				1607	<div class="doc_text">
				1608
				1609	<p>Sometimes, it'll be useful to grab a reference (or pointer) to a class
				1610	instance when all you've got at hand is an iterator. Well, extracting
				1611	a reference or a pointer from an iterator is very straight-forward.
				1612	Assuming that <tt>i</tt> is a <tt>BasicBlock::iterator</tt> and <tt>j</tt>
				1613	is a <tt>BasicBlock::const_iterator</tt>:</p>
				1614
				1615	<div class="doc_code">
				1616	<pre>
				1617	Instruction& inst = *i; // <i>Grab reference to instruction reference</i>
				1618	Instruction* pinst = &*i; // <i>Grab pointer to instruction reference</i>
				1619	const Instruction& inst = *j;
				1620	</pre>
				1621	</div>
				1622
				1623	<p>However, the iterators you'll be working with in the LLVM framework are
				1624	special: they will automatically convert to a ptr-to-instance type whenever they
				1625	need to. Instead of dereferencing the iterator and then taking the address of
				1626	the result, you can simply assign the iterator to the proper pointer type and
				1627	you get the dereference and address-of operation as a result of the assignment
				1628	(behind the scenes, this is a result of overloading casting mechanisms). Thus
				1629	the last line of the last example,</p>
				1630
				1631	<div class="doc_code">
				1632	<pre>
Chris Lattner	0665e1f	2008-01-03 16:56:04 +0000	[diff] [blame]	1633	Instruction pinst = &i;
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1634	</pre>
				1635	</div>
				1636
				1637	<p>is semantically equivalent to</p>
				1638
				1639	<div class="doc_code">
				1640	<pre>
Chris Lattner	0665e1f	2008-01-03 16:56:04 +0000	[diff] [blame]	1641	Instruction *pinst = i;
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1642	</pre>
				1643	</div>
				1644
				1645	<p>It's also possible to turn a class pointer into the corresponding iterator,
				1646	and this is a constant time operation (very efficient). The following code
				1647	snippet illustrates use of the conversion constructors provided by LLVM
				1648	iterators. By using these, you can explicitly grab the iterator of something
				1649	without actually obtaining it via iteration over some structure:</p>
				1650
				1651	<div class="doc_code">
				1652	<pre>
				1653	void printNextInstruction(Instruction* inst) {
				1654	BasicBlock::iterator it(inst);
				1655	++it; // <i>After this line, it refers to the instruction after *inst</i>
				1656	if (it != inst->getParent()->end()) llvm::cerr << *it << "\n";
				1657	}
				1658	</pre>
				1659	</div>
				1660
				1661	</div>
				1662
				1663	<!--_______________________________________________________________________-->
				1664	<div class="doc_subsubsection">
				1665	<a name="iterate_complex">Finding call sites: a slightly more complex
				1666	example</a>
				1667	</div>
				1668
				1669	<div class="doc_text">
				1670
				1671	<p>Say that you're writing a FunctionPass and would like to count all the
				1672	locations in the entire module (that is, across every <tt>Function</tt>) where a
				1673	certain function (i.e., some <tt>Function</tt>*) is already in scope. As you'll
				1674	learn later, you may want to use an <tt>InstVisitor</tt> to accomplish this in a
				1675	much more straight-forward manner, but this example will allow us to explore how
				1676	you'd do it if you didn't have <tt>InstVisitor</tt> around. In pseudo-code, this
				1677	is what we want to do:</p>
				1678
				1679	<div class="doc_code">
				1680	<pre>
				1681	initialize callCounter to zero
				1682	for each Function f in the Module
				1683	for each BasicBlock b in f
				1684	for each Instruction i in b
				1685	if (i is a CallInst and calls the given function)
				1686	increment callCounter
				1687	</pre>
				1688	</div>
				1689
				1690	<p>And the actual code is (remember, because we're writing a
				1691	<tt>FunctionPass</tt>, our <tt>FunctionPass</tt>-derived class simply has to
				1692	override the <tt>runOnFunction</tt> method):</p>
				1693
				1694	<div class="doc_code">
				1695	<pre>
				1696	Function* targetFunc = ...;
				1697
				1698	class OurFunctionPass : public FunctionPass {
				1699	public:
				1700	OurFunctionPass(): callCounter(0) { }
				1701
				1702	virtual runOnFunction(Function& F) {
				1703	for (Function::iterator b = F.begin(), be = F.end(); b != be; ++b) {
Eric Christopher	5fbecf7	2008-11-08 08:20:49 +0000	[diff] [blame]	1704	for (BasicBlock::iterator i = b->begin(), ie = b->end(); i != ie; ++i) {
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1705	if (<a href="#CallInst">CallInst</a>* callInst = <a href="#isa">dyn_cast</a><<a
				1706	href="#CallInst">CallInst</a>>(&*i)) {
				1707	// <i>We know we've encountered a call instruction, so we</i>
				1708	// <i>need to determine if it's a call to the</i>
Chris Lattner	0665e1f	2008-01-03 16:56:04 +0000	[diff] [blame]	1709	// <i>function pointed to by m_func or not.</i>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1710	if (callInst->getCalledFunction() == targetFunc)
				1711	++callCounter;
				1712	}
				1713	}
				1714	}
				1715	}
				1716
				1717	private:
Chris Lattner	0665e1f	2008-01-03 16:56:04 +0000	[diff] [blame]	1718	unsigned callCounter;
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1719	};
				1720	</pre>
				1721	</div>
				1722
				1723	</div>
				1724
				1725	<!--_______________________________________________________________________-->
				1726	<div class="doc_subsubsection">
				1727	<a name="calls_and_invokes">Treating calls and invokes the same way</a>
				1728	</div>
				1729
				1730	<div class="doc_text">
				1731
				1732	<p>You may have noticed that the previous example was a bit oversimplified in
				1733	that it did not deal with call sites generated by 'invoke' instructions. In
				1734	this, and in other situations, you may find that you want to treat
				1735	<tt>CallInst</tt>s and <tt>InvokeInst</tt>s the same way, even though their
				1736	most-specific common base class is <tt>Instruction</tt>, which includes lots of
				1737	less closely-related things. For these cases, LLVM provides a handy wrapper
				1738	class called <a
				1739	href="http://llvm.org/doxygen/classllvm_1_1CallSite.html"><tt>CallSite</tt></a>.
				1740	It is essentially a wrapper around an <tt>Instruction</tt> pointer, with some
				1741	methods that provide functionality common to <tt>CallInst</tt>s and
				1742	<tt>InvokeInst</tt>s.</p>
				1743
				1744	<p>This class has "value semantics": it should be passed by value, not by
				1745	reference and it should not be dynamically allocated or deallocated using
				1746	<tt>operator new</tt> or <tt>operator delete</tt>. It is efficiently copyable,
				1747	assignable and constructable, with costs equivalents to that of a bare pointer.
				1748	If you look at its definition, it has only a single pointer member.</p>
				1749
				1750	</div>
				1751
				1752	<!--_______________________________________________________________________-->
				1753	<div class="doc_subsubsection">
				1754	<a name="iterate_chains">Iterating over def-use & use-def chains</a>
				1755	</div>
				1756
				1757	<div class="doc_text">
				1758
				1759	<p>Frequently, we might have an instance of the <a
				1760	href="/doxygen/classllvm_1_1Value.html">Value Class</a> and we want to
				1761	determine which <tt>User</tt>s use the <tt>Value</tt>. The list of all
				1762	<tt>User</tt>s of a particular <tt>Value</tt> is called a <i>def-use</i> chain.
				1763	For example, let's say we have a <tt>Function*</tt> named <tt>F</tt> to a
				1764	particular function <tt>foo</tt>. Finding all of the instructions that
				1765	<i>use</i> <tt>foo</tt> is as simple as iterating over the <i>def-use</i> chain
				1766	of <tt>F</tt>:</p>
				1767
				1768	<div class="doc_code">
				1769	<pre>
Chris Lattner	0665e1f	2008-01-03 16:56:04 +0000	[diff] [blame]	1770	Function *F = ...;
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1771
				1772	for (Value::use_iterator i = F->use_begin(), e = F->use_end(); i != e; ++i)
				1773	if (Instruction Inst = dyn_cast<Instruction>(i)) {
				1774	llvm::cerr << "F is used in instruction:\n";
				1775	llvm::cerr << *Inst << "\n";
				1776	}
				1777	</pre>
				1778	</div>
				1779
				1780	<p>Alternately, it's common to have an instance of the <a
				1781	href="/doxygen/classllvm_1_1User.html">User Class</a> and need to know what
				1782	<tt>Value</tt>s are used by it. The list of all <tt>Value</tt>s used by a
				1783	<tt>User</tt> is known as a <i>use-def</i> chain. Instances of class
				1784	<tt>Instruction</tt> are common <tt>User</tt>s, so we might want to iterate over
				1785	all of the values that a particular instruction uses (that is, the operands of
				1786	the particular <tt>Instruction</tt>):</p>
				1787
				1788	<div class="doc_code">
				1789	<pre>
Chris Lattner	0665e1f	2008-01-03 16:56:04 +0000	[diff] [blame]	1790	Instruction *pi = ...;
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1791
				1792	for (User::op_iterator i = pi->op_begin(), e = pi->op_end(); i != e; ++i) {
Chris Lattner	0665e1f	2008-01-03 16:56:04 +0000	[diff] [blame]	1793	Value v = i;
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1794	// <i>...</i>
				1795	}
				1796	</pre>
				1797	</div>
				1798
				1799	<!--
				1800	def-use chains ("finding all users of"): Value::use_begin/use_end
				1801	use-def chains ("finding all values used"): User::op_begin/op_end [op=operand]
				1802	-->
				1803
				1804	</div>
				1805
Chris Lattner	0665e1f	2008-01-03 16:56:04 +0000	[diff] [blame]	1806	<!--_______________________________________________________________________-->
				1807	<div class="doc_subsubsection">
				1808	<a name="iterate_preds">Iterating over predecessors &
				1809	successors of blocks</a>
				1810	</div>
				1811
				1812	<div class="doc_text">
				1813
				1814	<p>Iterating over the predecessors and successors of a block is quite easy
				1815	with the routines defined in <tt>"llvm/Support/CFG.h"</tt>. Just use code like
				1816	this to iterate over all predecessors of BB:</p>
				1817
				1818	<div class="doc_code">
				1819	<pre>
				1820	#include "llvm/Support/CFG.h"
				1821	BasicBlock *BB = ...;
				1822
				1823	for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
				1824	BasicBlock Pred = PI;
				1825	// <i>...</i>
				1826	}
				1827	</pre>
				1828	</div>
				1829
				1830	<p>Similarly, to iterate over successors use
				1831	succ_iterator/succ_begin/succ_end.</p>
				1832
				1833	</div>
				1834
				1835
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1836	<!-- ======================================================================= -->
				1837	<div class="doc_subsection">
				1838	<a name="simplechanges">Making simple changes</a>
				1839	</div>
				1840
				1841	<div class="doc_text">
				1842
				1843	<p>There are some primitive transformation operations present in the LLVM
				1844	infrastructure that are worth knowing about. When performing
				1845	transformations, it's fairly common to manipulate the contents of basic
				1846	blocks. This section describes some of the common methods for doing so
				1847	and gives example code.</p>
				1848
				1849	</div>
				1850
				1851	<!--_______________________________________________________________________-->
				1852	<div class="doc_subsubsection">
				1853	<a name="schanges_creating">Creating and inserting new
				1854	<tt>Instruction</tt>s</a>
				1855	</div>
				1856
				1857	<div class="doc_text">
				1858
				1859	<p><i>Instantiating Instructions</i></p>
				1860
				1861	<p>Creation of <tt>Instruction</tt>s is straight-forward: simply call the
				1862	constructor for the kind of instruction to instantiate and provide the necessary
				1863	parameters. For example, an <tt>AllocaInst</tt> only <i>requires</i> a
				1864	(const-ptr-to) <tt>Type</tt>. Thus:</p>
				1865
				1866	<div class="doc_code">
				1867	<pre>
Nick Lewycky	c004e5b	2007-12-03 01:52:52 +0000	[diff] [blame]	1868	AllocaInst* ai = new AllocaInst(Type::Int32Ty);
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1869	</pre>
				1870	</div>
				1871
				1872	<p>will create an <tt>AllocaInst</tt> instance that represents the allocation of
				1873	one integer in the current stack frame, at run time. Each <tt>Instruction</tt>
				1874	subclass is likely to have varying default parameters which change the semantics
				1875	of the instruction, so refer to the <a
				1876	href="/doxygen/classllvm_1_1Instruction.html">doxygen documentation for the subclass of
				1877	Instruction</a> that you're interested in instantiating.</p>
				1878
				1879	<p><i>Naming values</i></p>
				1880
				1881	<p>It is very useful to name the values of instructions when you're able to, as
				1882	this facilitates the debugging of your transformations. If you end up looking
				1883	at generated LLVM machine code, you definitely want to have logical names
				1884	associated with the results of instructions! By supplying a value for the
				1885	<tt>Name</tt> (default) parameter of the <tt>Instruction</tt> constructor, you
				1886	associate a logical name with the result of the instruction's execution at
				1887	run time. For example, say that I'm writing a transformation that dynamically
				1888	allocates space for an integer on the stack, and that integer is going to be
				1889	used as some kind of index by some other code. To accomplish this, I place an
				1890	<tt>AllocaInst</tt> at the first point in the first <tt>BasicBlock</tt> of some
				1891	<tt>Function</tt>, and I'm intending to use it within the same
				1892	<tt>Function</tt>. I might do:</p>
				1893
				1894	<div class="doc_code">
				1895	<pre>
Nick Lewycky	c004e5b	2007-12-03 01:52:52 +0000	[diff] [blame]	1896	AllocaInst* pa = new AllocaInst(Type::Int32Ty, 0, "indexLoc");
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1897	</pre>
				1898	</div>
				1899
				1900	<p>where <tt>indexLoc</tt> is now the logical name of the instruction's
				1901	execution value, which is a pointer to an integer on the run time stack.</p>
				1902
				1903	<p><i>Inserting instructions</i></p>
				1904
				1905	<p>There are essentially two ways to insert an <tt>Instruction</tt>
				1906	into an existing sequence of instructions that form a <tt>BasicBlock</tt>:</p>
				1907
				1908	<ul>
				1909	<li>Insertion into an explicit instruction list
				1910
				1911	<p>Given a <tt>BasicBlock* pb</tt>, an <tt>Instruction* pi</tt> within that
				1912	<tt>BasicBlock</tt>, and a newly-created instruction we wish to insert
				1913	before <tt>*pi</tt>, we do the following: </p>
				1914
				1915	<div class="doc_code">
				1916	<pre>
				1917	BasicBlock *pb = ...;
				1918	Instruction *pi = ...;
				1919	Instruction *newInst = new Instruction(...);
				1920
				1921	pb->getInstList().insert(pi, newInst); // <i>Inserts newInst before pi in pb</i>
				1922	</pre>
				1923	</div>
				1924
				1925	<p>Appending to the end of a <tt>BasicBlock</tt> is so common that
				1926	the <tt>Instruction</tt> class and <tt>Instruction</tt>-derived
				1927	classes provide constructors which take a pointer to a
				1928	<tt>BasicBlock</tt> to be appended to. For example code that
				1929	looked like: </p>
				1930
				1931	<div class="doc_code">
				1932	<pre>
				1933	BasicBlock *pb = ...;
				1934	Instruction *newInst = new Instruction(...);
				1935
				1936	pb->getInstList().push_back(newInst); // <i>Appends newInst to pb</i>
				1937	</pre>
				1938	</div>
				1939
				1940	<p>becomes: </p>
				1941
				1942	<div class="doc_code">
				1943	<pre>
				1944	BasicBlock *pb = ...;
				1945	Instruction *newInst = new Instruction(..., pb);
				1946	</pre>
				1947	</div>
				1948
				1949	<p>which is much cleaner, especially if you are creating
				1950	long instruction streams.</p></li>
				1951
				1952	<li>Insertion into an implicit instruction list
				1953
				1954	<p><tt>Instruction</tt> instances that are already in <tt>BasicBlock</tt>s
				1955	are implicitly associated with an existing instruction list: the instruction
				1956	list of the enclosing basic block. Thus, we could have accomplished the same
				1957	thing as the above code without being given a <tt>BasicBlock</tt> by doing:
				1958	</p>
				1959
				1960	<div class="doc_code">
				1961	<pre>
				1962	Instruction *pi = ...;
				1963	Instruction *newInst = new Instruction(...);
				1964
				1965	pi->getParent()->getInstList().insert(pi, newInst);
				1966	</pre>
				1967	</div>
				1968
				1969	<p>In fact, this sequence of steps occurs so frequently that the
				1970	<tt>Instruction</tt> class and <tt>Instruction</tt>-derived classes provide
				1971	constructors which take (as a default parameter) a pointer to an
				1972	<tt>Instruction</tt> which the newly-created <tt>Instruction</tt> should
				1973	precede. That is, <tt>Instruction</tt> constructors are capable of
				1974	inserting the newly-created instance into the <tt>BasicBlock</tt> of a
				1975	provided instruction, immediately before that instruction. Using an
				1976	<tt>Instruction</tt> constructor with a <tt>insertBefore</tt> (default)
				1977	parameter, the above code becomes:</p>
				1978
				1979	<div class="doc_code">
				1980	<pre>
				1981	Instruction* pi = ...;
				1982	Instruction* newInst = new Instruction(..., pi);
				1983	</pre>
				1984	</div>
				1985
				1986	<p>which is much cleaner, especially if you're creating a lot of
				1987	instructions and adding them to <tt>BasicBlock</tt>s.</p></li>
				1988	</ul>
				1989
				1990	</div>
				1991
				1992	<!--_______________________________________________________________________-->
				1993	<div class="doc_subsubsection">
				1994	<a name="schanges_deleting">Deleting <tt>Instruction</tt>s</a>
				1995	</div>
				1996
				1997	<div class="doc_text">
				1998
				1999	<p>Deleting an instruction from an existing sequence of instructions that form a
				2000	<a href="#BasicBlock"><tt>BasicBlock</tt></a> is very straight-forward. First,
				2001	you must have a pointer to the instruction that you wish to delete. Second, you
				2002	need to obtain the pointer to that instruction's basic block. You use the
				2003	pointer to the basic block to get its list of instructions and then use the
				2004	erase function to remove your instruction. For example:</p>
				2005
				2006	<div class="doc_code">
				2007	<pre>
				2008	<a href="#Instruction">Instruction</a> *I = .. ;
Chris Lattner	3db8f77	2008-02-15 22:57:17 +0000	[diff] [blame]	2009	I->eraseFromParent();
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	2010	</pre>
				2011	</div>
				2012
				2013	</div>
				2014
				2015	<!--_______________________________________________________________________-->
				2016	<div class="doc_subsubsection">
				2017	<a name="schanges_replacing">Replacing an <tt>Instruction</tt> with another
				2018	<tt>Value</tt></a>
				2019	</div>
				2020
				2021	<div class="doc_text">
				2022
				2023	<p><i>Replacing individual instructions</i></p>
				2024
				2025	<p>Including "<a href="/doxygen/BasicBlockUtils_8h-source.html">llvm/Transforms/Utils/BasicBlockUtils.h</a>"
				2026	permits use of two very useful replace functions: <tt>ReplaceInstWithValue</tt>
				2027	and <tt>ReplaceInstWithInst</tt>.</p>
				2028
				2029	<h4><a name="schanges_deleting">Deleting <tt>Instruction</tt>s</a></h4>
				2030
				2031	<ul>
				2032	<li><tt>ReplaceInstWithValue</tt>
				2033
Nick Lewycky	48d4b03	2008-09-15 06:31:52 +0000	[diff] [blame]	2034	<p>This function replaces all uses of a given instruction with a value,
				2035	and then removes the original instruction. The following example
				2036	illustrates the replacement of the result of a particular
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	2037	<tt>AllocaInst</tt> that allocates memory for a single integer with a null
				2038	pointer to an integer.</p>
				2039
				2040	<div class="doc_code">
				2041	<pre>
				2042	AllocaInst* instToReplace = ...;
				2043	BasicBlock::iterator ii(instToReplace);
				2044
				2045	ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii,
Daniel Dunbar	8ce7962	2008-10-03 22:17:25 +0000	[diff] [blame]	2046	Constant::getNullValue(PointerType::getUnqual(Type::Int32Ty)));
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	2047	</pre></div></li>
				2048
				2049	<li><tt>ReplaceInstWithInst</tt>
				2050
				2051	<p>This function replaces a particular instruction with another
Nick Lewycky	48d4b03	2008-09-15 06:31:52 +0000	[diff] [blame]	2052	instruction, inserting the new instruction into the basic block at the
				2053	location where the old instruction was, and replacing any uses of the old
				2054	instruction with the new instruction. The following example illustrates
				2055	the replacement of one <tt>AllocaInst</tt> with another.</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	2056
				2057	<div class="doc_code">
				2058	<pre>
				2059	AllocaInst* instToReplace = ...;
				2060	BasicBlock::iterator ii(instToReplace);
				2061
				2062	ReplaceInstWithInst(instToReplace->getParent()->getInstList(), ii,
Nick Lewycky	c004e5b	2007-12-03 01:52:52 +0000	[diff] [blame]	2063	new AllocaInst(Type::Int32Ty, 0, "ptrToReplacedInt"));
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	2064	</pre></div></li>
				2065	</ul>
				2066
				2067	<p><i>Replacing multiple uses of <tt>User</tt>s and <tt>Value</tt>s</i></p>
				2068
				2069	<p>You can use <tt>Value::replaceAllUsesWith</tt> and
				2070	<tt>User::replaceUsesOfWith</tt> to change more than one use at a time. See the
				2071	doxygen documentation for the <a href="/doxygen/classllvm_1_1Value.html">Value Class</a>
				2072	and <a href="/doxygen/classllvm_1_1User.html">User Class</a>, respectively, for more
				2073	information.</p>
				2074
				2075	<!-- Value::replaceAllUsesWith User::replaceUsesOfWith Point out:
				2076	include/llvm/Transforms/Utils/ especially BasicBlockUtils.h with:
				2077	ReplaceInstWithValue, ReplaceInstWithInst -->
				2078
				2079	</div>
				2080
				2081	<!--_______________________________________________________________________-->
				2082	<div class="doc_subsubsection">
				2083	<a name="schanges_deletingGV">Deleting <tt>GlobalVariable</tt>s</a>
				2084	</div>
				2085
				2086	<div class="doc_text">
				2087
				2088	<p>Deleting a global variable from a module is just as easy as deleting an
				2089	Instruction. First, you must have a pointer to the global variable that you wish
				2090	to delete. You use this pointer to erase it from its parent, the module.
				2091	For example:</p>
				2092
				2093	<div class="doc_code">
				2094	<pre>
				2095	<a href="#GlobalVariable">GlobalVariable</a> *GV = .. ;
				2096
				2097	GV->eraseFromParent();
				2098	</pre>
				2099	</div>
				2100
				2101	</div>
				2102
Jeffrey Yasskin	7ebb6ac	2009-04-30 22:33:41 +0000	[diff] [blame]	2103	<!-- ======================================================================= -->
				2104	<div class="doc_subsection">
				2105	<a name="create_types">How to Create Types</a>
				2106	</div>
				2107
				2108	<div class="doc_text">
				2109
				2110	<p>In generating IR, you may need some complex types. If you know these types
Misha Brukman	0672513	2009-05-01 20:40:51 +0000	[diff] [blame]	2111	statically, you can use <tt>TypeBuilder<...>::get()</tt>, defined
Jeffrey Yasskin	7ebb6ac	2009-04-30 22:33:41 +0000	[diff] [blame]	2112	in <tt>llvm/Support/TypeBuilder.h</tt>, to retrieve them. <tt>TypeBuilder</tt>
				2113	has two forms depending on whether you're building types for cross-compilation
Misha Brukman	0672513	2009-05-01 20:40:51 +0000	[diff] [blame]	2114	or native library use. <tt>TypeBuilder<T, true></tt> requires
Jeffrey Yasskin	7ebb6ac	2009-04-30 22:33:41 +0000	[diff] [blame]	2115	that <tt>T</tt> be independent of the host environment, meaning that it's built
				2116	out of types from
				2117	the <a href="/doxygen/namespacellvm_1_1types.html"><tt>llvm::types</tt></a>
				2118	namespace and pointers, functions, arrays, etc. built of
Misha Brukman	0672513	2009-05-01 20:40:51 +0000	[diff] [blame]	2119	those. <tt>TypeBuilder<T, false></tt> additionally allows native C types
Jeffrey Yasskin	7ebb6ac	2009-04-30 22:33:41 +0000	[diff] [blame]	2120	whose size may depend on the host compiler. For example,</p>
				2121
				2122	<div class="doc_code">
				2123	<pre>
Misha Brukman	0672513	2009-05-01 20:40:51 +0000	[diff] [blame]	2124	FunctionType ft = TypeBuilder<types::i<8>(types::i<32>), true>::get();
Jeffrey Yasskin	7ebb6ac	2009-04-30 22:33:41 +0000	[diff] [blame]	2125	</pre>
				2126	</div>
				2127
				2128	<p>is easier to read and write than the equivalent</p>
				2129
				2130	<div class="doc_code">
				2131	<pre>
Owen Anderson	60f8757	2009-06-16 17:40:28 +0000	[diff] [blame]	2132	std::vector<const Type*> params;
Jeffrey Yasskin	7ebb6ac	2009-04-30 22:33:41 +0000	[diff] [blame]	2133	params.push_back(PointerType::getUnqual(Type::Int32Ty));
				2134	FunctionType *ft = FunctionType::get(Type::Int8Ty, params, false);
				2135	</pre>
				2136	</div>
				2137
				2138	<p>See the <a href="/doxygen/TypeBuilder_8h-source.html#l00001">class
				2139	comment</a> for more details.</p>
				2140
				2141	</div>
				2142
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	2143	<!-- *********************************************************************** -->
				2144	<div class="doc_section">
Owen Anderson	e8370c0	2009-06-16 01:17:16 +0000	[diff] [blame]	2145	<a name="threading">Threads and LLVM</a>
				2146	</div>
				2147	<!-- *********************************************************************** -->
				2148
				2149	<div class="doc_text">
				2150	<p>
				2151	This section describes the interaction of the LLVM APIs with multithreading,
				2152	both on the part of client applications, and in the JIT, in the hosted
				2153	application.
				2154	</p>
				2155
				2156	<p>
				2157	Note that LLVM's support for multithreading is still relatively young. Up
				2158	through version 2.5, the execution of threaded hosted applications was
				2159	supported, but not threaded client access to the APIs. While this use case is
				2160	now supported, clients <em>must</em> adhere to the guidelines specified below to
				2161	ensure proper operation in multithreaded mode.
				2162	</p>
				2163
				2164	<p>
				2165	Note that, on Unix-like platforms, LLVM requires the presence of GCC's atomic
				2166	intrinsics in order to support threaded operation. If you need a
				2167	multhreading-capable LLVM on a platform without a suitably modern system
				2168	compiler, consider compiling LLVM and LLVM-GCC in single-threaded mode, and
				2169	using the resultant compiler to build a copy of LLVM with multithreading
				2170	support.
				2171	</p>
				2172	</div>
				2173
				2174	<!-- ======================================================================= -->
				2175	<div class="doc_subsection">
Owen Anderson	b418690	2009-06-16 18:04:19 +0000	[diff] [blame]	2176	<a name="startmultithreaded">Entering and Exiting Multithreaded Mode</a>
Owen Anderson	e8370c0	2009-06-16 01:17:16 +0000	[diff] [blame]	2177	</div>
				2178
				2179	<div class="doc_text">
				2180
				2181	<p>
				2182	In order to properly protect its internal data structures while avoiding
Owen Anderson	b418690	2009-06-16 18:04:19 +0000	[diff] [blame]	2183	excessive locking overhead in the single-threaded case, the LLVM must intialize
				2184	certain data structures necessary to provide guards around its internals. To do
				2185	so, the client program must invoke <tt>llvm_start_multithreaded()</tt> before
				2186	making any concurrent LLVM API calls. To subsequently tear down these
				2187	structures, use the <tt>llvm_stop_multithreaded()</tt> call. You can also use
				2188	the <tt>llvm_is_multithreaded()</tt> call to check the status of multithreaded
				2189	mode.
Owen Anderson	e8370c0	2009-06-16 01:17:16 +0000	[diff] [blame]	2190	</p>
				2191
				2192	<p>
Owen Anderson	b418690	2009-06-16 18:04:19 +0000	[diff] [blame]	2193	Note that both of these calls must be made <em>in isolation</em>. That is to
				2194	say that no other LLVM API calls may be executing at any time during the
				2195	execution of <tt>llvm_start_multithreaded()</tt> or <tt>llvm_stop_multithreaded
				2196	</tt>. It's is the client's responsibility to enforce this isolation.
				2197	</p>
				2198
				2199	<p>
				2200	The return value of <tt>llvm_start_multithreaded()</tt> indicates the success or
				2201	failure of the initialization. Failure typically indicates that your copy of
				2202	LLVM was built without multithreading support, typically because GCC atomic
				2203	intrinsics were not found in your system compiler. In this case, the LLVM API
				2204	will not be safe for concurrent calls. However, it <em>will</em> be safe for
				2205	hosting threaded applications in the JIT, though care must be taken to ensure
				2206	that side exits and the like do not accidentally result in concurrent LLVM API
				2207	calls.
Owen Anderson	e8370c0	2009-06-16 01:17:16 +0000	[diff] [blame]	2208	</p>
				2209	</div>
				2210
				2211	<!-- ======================================================================= -->
				2212	<div class="doc_subsection">
				2213	<a name="shutdown">Ending Execution with <tt>llvm_shutdown()</tt></a>
				2214	</div>
				2215
				2216	<div class="doc_text">
				2217	<p>
				2218	When you are done using the LLVM APIs, you should call <tt>llvm_shutdown()</tt>
Owen Anderson	b418690	2009-06-16 18:04:19 +0000	[diff] [blame]	2219	to deallocate memory used for internal structures. This will also invoke
				2220	<tt>llvm_stop_multithreaded()</tt> if LLVM is operating in multithreaded mode.
				2221	As such, <tt>llvm_shutdown()</tt> requires the same isolation guarantees as
				2222	<tt>llvm_stop_multithreaded()</tt>.
Owen Anderson	e8370c0	2009-06-16 01:17:16 +0000	[diff] [blame]	2223	</p>
				2224
				2225	<p>
				2226	Note that, if you use scope-based shutdown, you can use the
				2227	<tt>llvm_shutdown_obj</tt> class, which calls <tt>llvm_shutdown()</tt> in its
				2228	destructor.
				2229	</div>
				2230
				2231	<!-- ======================================================================= -->
				2232	<div class="doc_subsection">
				2233	<a name="managedstatic">Lazy Initialization with <tt>ManagedStatic</tt></a>
				2234	</div>
				2235
				2236	<div class="doc_text">
				2237	<p>
				2238	<tt>ManagedStatic</tt> is a utility class in LLVM used to implement static
				2239	initialization of static resources, such as the global type tables. Before the
				2240	invocation of <tt>llvm_shutdown()</tt>, it implements a simple lazy
				2241	initialization scheme. Once <tt>llvm_start_multithreaded()</tt> returns,
				2242	however, it uses double-checked locking to implement thread-safe lazy
				2243	initialization.
				2244	</p>
				2245
				2246	<p>
				2247	Note that, because no other threads are allowed to issue LLVM API calls before
				2248	<tt>llvm_start_multithreaded()</tt> returns, it is possible to have
				2249	<tt>ManagedStatic</tt>s of <tt>llvm::sys::Mutex</tt>s.
				2250	</p>
Owen Anderson	b418690	2009-06-16 18:04:19 +0000	[diff] [blame]	2251
				2252	<p>
				2253	The <tt>llvm_acquire_global_lock()</tt> and <tt>llvm_release_global_lock</tt>
				2254	APIs provide access to the global lock used to implement the double-checked
				2255	locking for lazy initialization. These should only be used internally to LLVM,
				2256	and only if you know what you're doing!
				2257	</p>
Owen Anderson	e8370c0	2009-06-16 01:17:16 +0000	[diff] [blame]	2258	</div>
				2259
				2260	<!-- *********************************************************************** -->
				2261	<div class="doc_section">
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	2262	<a name="advanced">Advanced Topics</a>
				2263	</div>
				2264	<!-- *********************************************************************** -->
				2265
				2266	<div class="doc_text">
				2267	<p>
				2268	This section describes some of the advanced or obscure API's that most clients
				2269	do not need to be aware of. These API's tend manage the inner workings of the
				2270	LLVM system, and only need to be accessed in unusual circumstances.
				2271	</p>
				2272	</div>
				2273
				2274	<!-- ======================================================================= -->
				2275	<div class="doc_subsection">
				2276	<a name="TypeResolve">LLVM Type Resolution</a>
				2277	</div>
				2278
				2279	<div class="doc_text">
				2280
				2281	<p>
				2282	The LLVM type system has a very simple goal: allow clients to compare types for
				2283	structural equality with a simple pointer comparison (aka a shallow compare).
				2284	This goal makes clients much simpler and faster, and is used throughout the LLVM
				2285	system.
				2286	</p>
				2287
				2288	<p>
				2289	Unfortunately achieving this goal is not a simple matter. In particular,
				2290	recursive types and late resolution of opaque types makes the situation very
				2291	difficult to handle. Fortunately, for the most part, our implementation makes
				2292	most clients able to be completely unaware of the nasty internal details. The
				2293	primary case where clients are exposed to the inner workings of it are when
				2294	building a recursive type. In addition to this case, the LLVM bitcode reader,
				2295	assembly parser, and linker also have to be aware of the inner workings of this
				2296	system.
				2297	</p>
				2298
				2299	<p>
				2300	For our purposes below, we need three concepts. First, an "Opaque Type" is
				2301	exactly as defined in the <a href="LangRef.html#t_opaque">language
				2302	reference</a>. Second an "Abstract Type" is any type which includes an
				2303	opaque type as part of its type graph (for example "<tt>{ opaque, i32 }</tt>").
				2304	Third, a concrete type is a type that is not an abstract type (e.g. "<tt>{ i32,
				2305	float }</tt>").
				2306	</p>
				2307
				2308	</div>
				2309
				2310	<!-- ______________________________________________________________________ -->
				2311	<div class="doc_subsubsection">
				2312	<a name="BuildRecType">Basic Recursive Type Construction</a>
				2313	</div>
				2314
				2315	<div class="doc_text">
				2316
				2317	<p>
				2318	Because the most common question is "how do I build a recursive type with LLVM",
				2319	we answer it now and explain it as we go. Here we include enough to cause this
				2320	to be emitted to an output .ll file:
				2321	</p>
				2322
				2323	<div class="doc_code">
				2324	<pre>
				2325	%mylist = type { %mylist*, i32 }
				2326	</pre>
				2327	</div>
				2328
				2329	<p>
				2330	To build this, use the following LLVM APIs:
				2331	</p>
				2332
				2333	<div class="doc_code">
				2334	<pre>
				2335	// <i>Create the initial outer struct</i>
				2336	<a href="#PATypeHolder">PATypeHolder</a> StructTy = OpaqueType::get();
				2337	std::vector<const Type*> Elts;
Daniel Dunbar	8ce7962	2008-10-03 22:17:25 +0000	[diff] [blame]	2338	Elts.push_back(PointerType::getUnqual(StructTy));
Nick Lewycky	c004e5b	2007-12-03 01:52:52 +0000	[diff] [blame]	2339	Elts.push_back(Type::Int32Ty);
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	2340	StructType *NewSTy = StructType::get(Elts);
				2341
				2342	// <i>At this point, NewSTy = "{ opaque*, i32 }". Tell VMCore that</i>
				2343	// <i>the struct and the opaque type are actually the same.</i>
				2344	cast<OpaqueType>(StructTy.get())-><a href="#refineAbstractTypeTo">refineAbstractTypeTo</a>(NewSTy);
				2345
				2346	// <i>NewSTy is potentially invalidated, but StructTy (a <a href="#PATypeHolder">PATypeHolder</a>) is</i>
				2347	// <i>kept up-to-date</i>
				2348	NewSTy = cast<StructType>(StructTy.get());
				2349
				2350	// <i>Add a name for the type to the module symbol table (optional)</i>
				2351	MyModule->addTypeName("mylist", NewSTy);
				2352	</pre>
				2353	</div>
				2354
				2355	<p>
				2356	This code shows the basic approach used to build recursive types: build a
				2357	non-recursive type using 'opaque', then use type unification to close the cycle.
				2358	The type unification step is performed by the <tt><a
				2359	href="#refineAbstractTypeTo">refineAbstractTypeTo</a></tt> method, which is
				2360	described next. After that, we describe the <a
				2361	href="#PATypeHolder">PATypeHolder class</a>.
				2362	</p>
				2363
				2364	</div>
				2365
				2366	<!-- ______________________________________________________________________ -->
				2367	<div class="doc_subsubsection">
				2368	<a name="refineAbstractTypeTo">The <tt>refineAbstractTypeTo</tt> method</a>
				2369	</div>
				2370
				2371	<div class="doc_text">
				2372	<p>
				2373	The <tt>refineAbstractTypeTo</tt> method starts the type unification process.
				2374	While this method is actually a member of the DerivedType class, it is most
				2375	often used on OpaqueType instances. Type unification is actually a recursive
				2376	process. After unification, types can become structurally isomorphic to
				2377	existing types, and all duplicates are deleted (to preserve pointer equality).
				2378	</p>
				2379
				2380	<p>
				2381	In the example above, the OpaqueType object is definitely deleted.
				2382	Additionally, if there is an "{ \2*, i32}" type already created in the system,
				2383	the pointer and struct type created are <b>also</b> deleted. Obviously whenever
				2384	a type is deleted, any "Type*" pointers in the program are invalidated. As
				2385	such, it is safest to avoid having <i>any</i> "Type*" pointers to abstract types
				2386	live across a call to <tt>refineAbstractTypeTo</tt> (note that non-abstract
				2387	types can never move or be deleted). To deal with this, the <a
				2388	href="#PATypeHolder">PATypeHolder</a> class is used to maintain a stable
				2389	reference to a possibly refined type, and the <a
				2390	href="#AbstractTypeUser">AbstractTypeUser</a> class is used to update more
				2391	complex datastructures.
				2392	</p>
				2393
				2394	</div>
				2395
				2396	<!-- ______________________________________________________________________ -->
				2397	<div class="doc_subsubsection">
				2398	<a name="PATypeHolder">The PATypeHolder Class</a>
				2399	</div>
				2400
				2401	<div class="doc_text">
				2402	<p>
				2403	PATypeHolder is a form of a "smart pointer" for Type objects. When VMCore
				2404	happily goes about nuking types that become isomorphic to existing types, it
				2405	automatically updates all PATypeHolder objects to point to the new type. In the
				2406	example above, this allows the code to maintain a pointer to the resultant
				2407	resolved recursive type, even though the Type*'s are potentially invalidated.
				2408	</p>
				2409
				2410	<p>
				2411	PATypeHolder is an extremely light-weight object that uses a lazy union-find
				2412	implementation to update pointers. For example the pointer from a Value to its
				2413	Type is maintained by PATypeHolder objects.
				2414	</p>
				2415
				2416	</div>
				2417
				2418	<!-- ______________________________________________________________________ -->
				2419	<div class="doc_subsubsection">
				2420	<a name="AbstractTypeUser">The AbstractTypeUser Class</a>
				2421	</div>
				2422
				2423	<div class="doc_text">
				2424
				2425	<p>
				2426	Some data structures need more to perform more complex updates when types get
				2427	resolved. To support this, a class can derive from the AbstractTypeUser class.
				2428	This class
				2429	allows it to get callbacks when certain types are resolved. To register to get
				2430	callbacks for a particular type, the DerivedType::{add/remove}AbstractTypeUser
				2431	methods can be called on a type. Note that these methods only work for <i>
				2432	abstract</i> types. Concrete types (those that do not include any opaque
				2433	objects) can never be refined.
				2434	</p>
				2435	</div>
				2436
				2437
				2438	<!-- ======================================================================= -->
				2439	<div class="doc_subsection">
				2440	<a name="SymbolTable">The <tt>ValueSymbolTable</tt> and
				2441	<tt>TypeSymbolTable</tt> classes</a>
				2442	</div>
				2443
				2444	<div class="doc_text">
				2445	<p>The <tt><a href="http://llvm.org/doxygen/classllvm_1_1ValueSymbolTable.html">
				2446	ValueSymbolTable</a></tt> class provides a symbol table that the <a
				2447	href="#Function"><tt>Function</tt></a> and <a href="#Module">
				2448	<tt>Module</tt></a> classes use for naming value definitions. The symbol table
				2449	can provide a name for any <a href="#Value"><tt>Value</tt></a>.
				2450	The <tt><a href="http://llvm.org/doxygen/classllvm_1_1TypeSymbolTable.html">
				2451	TypeSymbolTable</a></tt> class is used by the <tt>Module</tt> class to store
				2452	names for types.</p>
				2453
				2454	<p>Note that the <tt>SymbolTable</tt> class should not be directly accessed
				2455	by most clients. It should only be used when iteration over the symbol table
				2456	names themselves are required, which is very special purpose. Note that not
				2457	all LLVM
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2458	<tt><a href="#Value">Value</a></tt>s have names, and those without names (i.e. they have
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	2459	an empty name) do not exist in the symbol table.
				2460	</p>
				2461
				2462	<p>These symbol tables support iteration over the values/types in the symbol
				2463	table with <tt>begin/end/iterator</tt> and supports querying to see if a
				2464	specific name is in the symbol table (with <tt>lookup</tt>). The
				2465	<tt>ValueSymbolTable</tt> class exposes no public mutator methods, instead,
				2466	simply call <tt>setName</tt> on a value, which will autoinsert it into the
				2467	appropriate symbol table. For types, use the Module::addTypeName method to
				2468	insert entries into the symbol table.</p>
				2469
				2470	</div>
				2471
				2472
				2473
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2474	<!-- ======================================================================= -->
				2475	<div class="doc_subsection">
				2476	<a name="UserLayout">The <tt>User</tt> and owned <tt>Use</tt> classes' memory layout</a>
				2477	</div>
				2478
				2479	<div class="doc_text">
				2480	<p>The <tt><a href="http://llvm.org/doxygen/classllvm_1_1User.html">
Gabor Greif	50626fc	2009-01-05 16:05:32 +0000	[diff] [blame]	2481	User</a></tt> class provides a basis for expressing the ownership of <tt>User</tt>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2482	towards other <tt><a href="http://llvm.org/doxygen/classllvm_1_1Value.html">
				2483	Value</a></tt>s. The <tt><a href="http://llvm.org/doxygen/classllvm_1_1Use.html">
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2484	Use</a></tt> helper class is employed to do the bookkeeping and to facilitate <i>O(1)</i>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2485	addition and removal.</p>
				2486
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2487	<!-- ______________________________________________________________________ -->
				2488	<div class="doc_subsubsection">
Gabor Greif	50626fc	2009-01-05 16:05:32 +0000	[diff] [blame]	2489	<a name="Use2User">Interaction and relationship between <tt>User</tt> and <tt>Use</tt> objects</a>
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2490	</div>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2491
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2492	<div class="doc_text">
				2493	<p>
				2494	A subclass of <tt>User</tt> can choose between incorporating its <tt>Use</tt> objects
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2495	or refer to them out-of-line by means of a pointer. A mixed variant
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2496	(some <tt>Use</tt>s inline others hung off) is impractical and breaks the invariant
				2497	that the <tt>Use</tt> objects belonging to the same <tt>User</tt> form a contiguous array.
				2498	</p>
				2499	</div>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2500
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2501	<p>
				2502	We have 2 different layouts in the <tt>User</tt> (sub)classes:
				2503	<ul>
				2504	<li><p>Layout a)
				2505	The <tt>Use</tt> object(s) are inside (resp. at fixed offset) of the <tt>User</tt>
				2506	object and there are a fixed number of them.</p>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2507
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2508	<li><p>Layout b)
				2509	The <tt>Use</tt> object(s) are referenced by a pointer to an
				2510	array from the <tt>User</tt> object and there may be a variable
				2511	number of them.</p>
				2512	</ul>
				2513	<p>
Gabor Greif	e247e36	2008-06-25 00:10:22 +0000	[diff] [blame]	2514	As of v2.4 each layout still possesses a direct pointer to the
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2515	start of the array of <tt>Use</tt>s. Though not mandatory for layout a),
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2516	we stick to this redundancy for the sake of simplicity.
Gabor Greif	e247e36	2008-06-25 00:10:22 +0000	[diff] [blame]	2517	The <tt>User</tt> object also stores the number of <tt>Use</tt> objects it
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2518	has. (Theoretically this information can also be calculated
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2519	given the scheme presented below.)</p>
				2520	<p>
				2521	Special forms of allocation operators (<tt>operator new</tt>)
Gabor Greif	e247e36	2008-06-25 00:10:22 +0000	[diff] [blame]	2522	enforce the following memory layouts:</p>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2523
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2524	<ul>
Gabor Greif	e247e36	2008-06-25 00:10:22 +0000	[diff] [blame]	2525	<li><p>Layout a) is modelled by prepending the <tt>User</tt> object by the <tt>Use[]</tt> array.</p>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2526
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2527	<pre>
				2528	...---.---.---.---.-------...
				2529	\| P \| P \| P \| P \| User
				2530	'''---'---'---'---'-------'''
				2531	</pre>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2532
Gabor Greif	e247e36	2008-06-25 00:10:22 +0000	[diff] [blame]	2533	<li><p>Layout b) is modelled by pointing at the <tt>Use[]</tt> array.</p>
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2534	<pre>
				2535	.-------...
				2536	\| User
				2537	'-------'''
				2538	\|
				2539	v
				2540	.---.---.---.---...
				2541	\| P \| P \| P \| P \|
				2542	'---'---'---'---'''
				2543	</pre>
				2544	</ul>
				2545	<i>(In the above figures '<tt>P</tt>' stands for the <tt>Use**</tt> that
				2546	is stored in each <tt>Use</tt> object in the member <tt>Use::Prev</tt>)</i>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2547
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2548	<!-- ______________________________________________________________________ -->
				2549	<div class="doc_subsubsection">
Gabor Greif	50626fc	2009-01-05 16:05:32 +0000	[diff] [blame]	2550	<a name="Waymarking">The waymarking algorithm</a>
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2551	</div>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2552
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2553	<div class="doc_text">
				2554	<p>
Gabor Greif	e247e36	2008-06-25 00:10:22 +0000	[diff] [blame]	2555	Since the <tt>Use</tt> objects are deprived of the direct (back)pointer to
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2556	their <tt>User</tt> objects, there must be a fast and exact method to
				2557	recover it. This is accomplished by the following scheme:</p>
				2558	</div>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2559
Gabor Greif	e247e36	2008-06-25 00:10:22 +0000	[diff] [blame]	2560	A bit-encoding in the 2 LSBits (least significant bits) of the <tt>Use::Prev</tt> allows to find the
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2561	start of the <tt>User</tt> object:
				2562	<ul>
				2563	<li><tt>00</tt> —> binary digit 0</li>
				2564	<li><tt>01</tt> —> binary digit 1</li>
				2565	<li><tt>10</tt> —> stop and calculate (<tt>s</tt>)</li>
				2566	<li><tt>11</tt> —> full stop (<tt>S</tt>)</li>
				2567	</ul>
				2568	<p>
				2569	Given a <tt>Use*</tt>, all we have to do is to walk till we get
				2570	a stop and we either have a <tt>User</tt> immediately behind or
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2571	we have to walk to the next stop picking up digits
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2572	and calculating the offset:</p>
				2573	<pre>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2574	.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.----------------
				2575	\| 1 \| s \| 1 \| 0 \| 1 \| 0 \| s \| 1 \| 1 \| 0 \| s \| 1 \| 1 \| s \| 1 \| S \| User (or User*)
				2576	'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'----------------
				2577	\|+15 \|+10 \|+6 \|+3 \|+1
				2578	\| \| \| \| \|__>
				2579	\| \| \| \|__________>
				2580	\| \| \|______________________>
				2581	\| \|______________________________________>
				2582	\|__________________________________________________________>
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2583	</pre>
				2584	<p>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2585	Only the significant number of bits need to be stored between the
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2586	stops, so that the <i>worst case is 20 memory accesses</i> when there are
				2587	1000 <tt>Use</tt> objects associated with a <tt>User</tt>.</p>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2588
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2589	<!-- ______________________________________________________________________ -->
				2590	<div class="doc_subsubsection">
Gabor Greif	50626fc	2009-01-05 16:05:32 +0000	[diff] [blame]	2591	<a name="ReferenceImpl">Reference implementation</a>
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2592	</div>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2593
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2594	<div class="doc_text">
				2595	<p>
				2596	The following literate Haskell fragment demonstrates the concept:</p>
				2597	</div>
				2598
				2599	<div class="doc_code">
				2600	<pre>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2601	> import Test.QuickCheck
				2602	>
				2603	> digits :: Int -> [Char] -> [Char]
				2604	> digits 0 acc = '0' : acc
				2605	> digits 1 acc = '1' : acc
				2606	> digits n acc = digits (n `div` 2) $ digits (n `mod` 2) acc
				2607	>
				2608	> dist :: Int -> [Char] -> [Char]
				2609	> dist 0 [] = ['S']
				2610	> dist 0 acc = acc
				2611	> dist 1 acc = let r = dist 0 acc in 's' : digits (length r) r
				2612	> dist n acc = dist (n - 1) $ dist 1 acc
				2613	>
				2614	> takeLast n ss = reverse $ take n $ reverse ss
				2615	>
				2616	> test = takeLast 40 $ dist 20 []
				2617	>
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2618	</pre>
				2619	</div>
				2620	<p>
				2621	Printing <test> gives: <tt>"1s100000s11010s10100s1111s1010s110s11s1S"</tt></p>
				2622	<p>
				2623	The reverse algorithm computes the length of the string just by examining
				2624	a certain prefix:</p>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2625
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2626	<div class="doc_code">
				2627	<pre>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2628	> pref :: [Char] -> Int
				2629	> pref "S" = 1
				2630	> pref ('s':'1':rest) = decode 2 1 rest
				2631	> pref (_:rest) = 1 + pref rest
				2632	>
				2633	> decode walk acc ('0':rest) = decode (walk + 1) (acc * 2) rest
				2634	> decode walk acc ('1':rest) = decode (walk + 1) (acc * 2 + 1) rest
				2635	> decode walk acc _ = walk + acc
				2636	>
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2637	</pre>
				2638	</div>
				2639	<p>
				2640	Now, as expected, printing <pref test> gives <tt>40</tt>.</p>
				2641	<p>
				2642	We can <i>quickCheck</i> this with following property:</p>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2643
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2644	<div class="doc_code">
				2645	<pre>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2646	> testcase = dist 2000 []
				2647	> testcaseLength = length testcase
				2648	>
				2649	> identityProp n = n > 0 && n <= testcaseLength ==> length arr == pref arr
				2650	> where arr = takeLast n testcase
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2651	>
				2652	</pre>
				2653	</div>
				2654	<p>
				2655	As expected <quickCheck identityProp> gives:</p>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2656
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2657	<pre>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2658	*Main> quickCheck identityProp
				2659	OK, passed 100 tests.
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2660	</pre>
				2661	<p>
				2662	Let's be a bit more exhaustive:</p>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2663
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2664	<div class="doc_code">
				2665	<pre>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2666	>
				2667	> deepCheck p = check (defaultConfig { configMaxTest = 500 }) p
				2668	>
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2669	</pre>
				2670	</div>
				2671	<p>
				2672	And here is the result of <deepCheck identityProp>:</p>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2673
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2674	<pre>
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2675	*Main> deepCheck identityProp
				2676	OK, passed 500 tests.
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2677	</pre>
				2678
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2679	<!-- ______________________________________________________________________ -->
				2680	<div class="doc_subsubsection">
Gabor Greif	50626fc	2009-01-05 16:05:32 +0000	[diff] [blame]	2681	<a name="Tagging">Tagging considerations</a>
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2682	</div>
				2683
				2684	<p>
				2685	To maintain the invariant that the 2 LSBits of each <tt>Use**</tt> in <tt>Use</tt>
				2686	never change after being set up, setters of <tt>Use::Prev</tt> must re-tag the
				2687	new <tt>Use**</tt> on every modification. Accordingly getters must strip the
				2688	tag bits.</p>
				2689	<p>
Gabor Greif	e247e36	2008-06-25 00:10:22 +0000	[diff] [blame]	2690	For layout b) instead of the <tt>User</tt> we find a pointer (<tt>User*</tt> with LSBit set).
				2691	Following this pointer brings us to the <tt>User</tt>. A portable trick ensures
				2692	that the first bytes of <tt>User</tt> (if interpreted as a pointer) never has
Gabor Greif	50626fc	2009-01-05 16:05:32 +0000	[diff] [blame]	2693	the LSBit set. (Portability is relying on the fact that all known compilers place the
				2694	<tt>vptr</tt> in the first word of the instances.)</p>
Gabor Greif	93b462b	2008-06-18 13:44:57 +0000	[diff] [blame]	2695
Gabor Greif	92e8776	2008-06-16 21:06:12 +0000	[diff] [blame]	2696	</div>
				2697
				2698	<!-- *********************************************************************** -->
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	2699	<div class="doc_section">
				2700	<a name="coreclasses">The Core LLVM Class Hierarchy Reference </a>
				2701	</div>
				2702	<!-- *********************************************************************** -->
				2703
				2704	<div class="doc_text">
				2705	<p><tt>#include "<a href="/doxygen/Type_8h-source.html">llvm/Type.h</a>"</tt>
				2706	<br>doxygen info: <a href="/doxygen/classllvm_1_1Type.html">Type Class</a></p>
				2707
				2708	<p>The Core LLVM classes are the primary means of representing the program
				2709	being inspected or transformed. The core LLVM classes are defined in
				2710	header files in the <tt>include/llvm/</tt> directory, and implemented in
				2711	the <tt>lib/VMCore</tt> directory.</p>
				2712
				2713	</div>
				2714
				2715	<!-- ======================================================================= -->
				2716	<div class="doc_subsection">
				2717	<a name="Type">The <tt>Type</tt> class and Derived Types</a>
				2718	</div>
				2719
				2720	<div class="doc_text">
				2721
				2722	<p><tt>Type</tt> is a superclass of all type classes. Every <tt>Value</tt> has
				2723	a <tt>Type</tt>. <tt>Type</tt> cannot be instantiated directly but only
				2724	through its subclasses. Certain primitive types (<tt>VoidType</tt>,
				2725	<tt>LabelType</tt>, <tt>FloatType</tt> and <tt>DoubleType</tt>) have hidden
				2726	subclasses. They are hidden because they offer no useful functionality beyond
				2727	what the <tt>Type</tt> class offers except to distinguish themselves from
				2728	other subclasses of <tt>Type</tt>.</p>
				2729	<p>All other types are subclasses of <tt>DerivedType</tt>. Types can be
				2730	named, but this is not a requirement. There exists exactly
				2731	one instance of a given shape at any one time. This allows type equality to
				2732	be performed with address equality of the Type Instance. That is, given two
				2733	<tt>Type*</tt> values, the types are identical if the pointers are identical.
				2734	</p>
				2735	</div>
				2736
				2737	<!-- _______________________________________________________________________ -->
				2738	<div class="doc_subsubsection">
Gabor Greif	50626fc	2009-01-05 16:05:32 +0000	[diff] [blame]	2739	<a name="m_Type">Important Public Methods</a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	2740	</div>
				2741
				2742	<div class="doc_text">
				2743
				2744	<ul>
				2745	<li><tt>bool isInteger() const</tt>: Returns true for any integer type.</li>
				2746
				2747	<li><tt>bool isFloatingPoint()</tt>: Return true if this is one of the two
				2748	floating point types.</li>
				2749
				2750	<li><tt>bool isAbstract()</tt>: Return true if the type is abstract (contains
				2751	an OpaqueType anywhere in its definition).</li>
				2752
				2753	<li><tt>bool isSized()</tt>: Return true if the type has known size. Things
				2754	that don't have a size are abstract types, labels and void.</li>
				2755
				2756	</ul>
				2757	</div>
				2758
				2759	<!-- _______________________________________________________________________ -->
				2760	<div class="doc_subsubsection">
Gabor Greif	50626fc	2009-01-05 16:05:32 +0000	[diff] [blame]	2761	<a name="derivedtypes">Important Derived Types</a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	2762	</div>
				2763	<div class="doc_text">
				2764	<dl>
				2765	<dt><tt>IntegerType</tt></dt>
				2766	<dd>Subclass of DerivedType that represents integer types of any bit width.
				2767	Any bit width between <tt>IntegerType::MIN_INT_BITS</tt> (1) and
				2768	<tt>IntegerType::MAX_INT_BITS</tt> (~8 million) can be represented.
				2769	<ul>
				2770	<li><tt>static const IntegerType* get(unsigned NumBits)</tt>: get an integer
				2771	type of a specific bit width.</li>
				2772	<li><tt>unsigned getBitWidth() const</tt>: Get the bit width of an integer
				2773	type.</li>
				2774	</ul>
				2775	</dd>
				2776	<dt><tt>SequentialType</tt></dt>
				2777	<dd>This is subclassed by ArrayType and PointerType
				2778	<ul>
				2779	<li><tt>const Type * getElementType() const</tt>: Returns the type of each
				2780	of the elements in the sequential type. </li>
				2781	</ul>
				2782	</dd>
				2783	<dt><tt>ArrayType</tt></dt>
				2784	<dd>This is a subclass of SequentialType and defines the interface for array
				2785	types.
				2786	<ul>
				2787	<li><tt>unsigned getNumElements() const</tt>: Returns the number of
				2788	elements in the array. </li>
				2789	</ul>
				2790	</dd>
				2791	<dt><tt>PointerType</tt></dt>
				2792	<dd>Subclass of SequentialType for pointer types.</dd>
				2793	<dt><tt>VectorType</tt></dt>
				2794	<dd>Subclass of SequentialType for vector types. A
				2795	vector type is similar to an ArrayType but is distinguished because it is
				2796	a first class type wherease ArrayType is not. Vector types are used for
				2797	vector operations and are usually small vectors of of an integer or floating
				2798	point type.</dd>
				2799	<dt><tt>StructType</tt></dt>
				2800	<dd>Subclass of DerivedTypes for struct types.</dd>
				2801	<dt><tt><a name="FunctionType">FunctionType</a></tt></dt>
				2802	<dd>Subclass of DerivedTypes for function types.
				2803	<ul>
				2804	<li><tt>bool isVarArg() const</tt>: Returns true if its a vararg
				2805	function</li>
				2806	<li><tt> const Type * getReturnType() const</tt>: Returns the
				2807	return type of the function.</li>
				2808	<li><tt>const Type * getParamType (unsigned i)</tt>: Returns
				2809	the type of the ith parameter.</li>
				2810	<li><tt> const unsigned getNumParams() const</tt>: Returns the
				2811	number of formal parameters.</li>
				2812	</ul>
				2813	</dd>
				2814	<dt><tt>OpaqueType</tt></dt>
				2815	<dd>Sublcass of DerivedType for abstract types. This class
				2816	defines no content and is used as a placeholder for some other type. Note
				2817	that OpaqueType is used (temporarily) during type resolution for forward
				2818	references of types. Once the referenced type is resolved, the OpaqueType
				2819	is replaced with the actual type. OpaqueType can also be used for data
				2820	abstraction. At link time opaque types can be resolved to actual types
				2821	of the same name.</dd>
				2822	</dl>
				2823	</div>
				2824
				2825
				2826
				2827	<!-- ======================================================================= -->
				2828	<div class="doc_subsection">
				2829	<a name="Module">The <tt>Module</tt> class</a>
				2830	</div>
				2831
				2832	<div class="doc_text">
				2833
				2834	<p><tt>#include "<a
				2835	href="/doxygen/Module_8h-source.html">llvm/Module.h</a>"</tt><br> doxygen info:
				2836	<a href="/doxygen/classllvm_1_1Module.html">Module Class</a></p>
				2837
				2838	<p>The <tt>Module</tt> class represents the top level structure present in LLVM
				2839	programs. An LLVM module is effectively either a translation unit of the
				2840	original program or a combination of several translation units merged by the
				2841	linker. The <tt>Module</tt> class keeps track of a list of <a
				2842	href="#Function"><tt>Function</tt></a>s, a list of <a
				2843	href="#GlobalVariable"><tt>GlobalVariable</tt></a>s, and a <a
				2844	href="#SymbolTable"><tt>SymbolTable</tt></a>. Additionally, it contains a few
				2845	helpful member functions that try to make common operations easy.</p>
				2846
				2847	</div>
				2848
				2849	<!-- _______________________________________________________________________ -->
				2850	<div class="doc_subsubsection">
				2851	<a name="m_Module">Important Public Members of the <tt>Module</tt> class</a>
				2852	</div>
				2853
				2854	<div class="doc_text">
				2855
				2856	<ul>
				2857	<li><tt>Module::Module(std::string name = "")</tt></li>
				2858	</ul>
				2859
				2860	<p>Constructing a <a href="#Module">Module</a> is easy. You can optionally
				2861	provide a name for it (probably based on the name of the translation unit).</p>
				2862
				2863	<ul>
				2864	<li><tt>Module::iterator</tt> - Typedef for function list iterator<br>
				2865	<tt>Module::const_iterator</tt> - Typedef for const_iterator.<br>
				2866
				2867	<tt>begin()</tt>, <tt>end()</tt>
				2868	<tt>size()</tt>, <tt>empty()</tt>
				2869
				2870	<p>These are forwarding methods that make it easy to access the contents of
				2871	a <tt>Module</tt> object's <a href="#Function"><tt>Function</tt></a>
				2872	list.</p></li>
				2873
				2874	<li><tt>Module::FunctionListType &getFunctionList()</tt>
				2875
				2876	<p> Returns the list of <a href="#Function"><tt>Function</tt></a>s. This is
				2877	necessary to use when you need to update the list or perform a complex
				2878	action that doesn't have a forwarding method.</p>
				2879
				2880	<p><!-- Global Variable --></p></li>
				2881	</ul>
				2882
				2883	<hr>
				2884
				2885	<ul>
				2886	<li><tt>Module::global_iterator</tt> - Typedef for global variable list iterator<br>
				2887
				2888	<tt>Module::const_global_iterator</tt> - Typedef for const_iterator.<br>
				2889
				2890	<tt>global_begin()</tt>, <tt>global_end()</tt>
				2891	<tt>global_size()</tt>, <tt>global_empty()</tt>
				2892
				2893	<p> These are forwarding methods that make it easy to access the contents of
				2894	a <tt>Module</tt> object's <a
				2895	href="#GlobalVariable"><tt>GlobalVariable</tt></a> list.</p></li>
				2896
				2897	<li><tt>Module::GlobalListType &getGlobalList()</tt>
				2898
				2899	<p>Returns the list of <a
				2900	href="#GlobalVariable"><tt>GlobalVariable</tt></a>s. This is necessary to
				2901	use when you need to update the list or perform a complex action that
				2902	doesn't have a forwarding method.</p>
				2903
				2904	<p><!-- Symbol table stuff --> </p></li>
				2905	</ul>
				2906
				2907	<hr>
				2908
				2909	<ul>
				2910	<li><tt><a href="#SymbolTable">SymbolTable</a> *getSymbolTable()</tt>
				2911
				2912	<p>Return a reference to the <a href="#SymbolTable"><tt>SymbolTable</tt></a>
				2913	for this <tt>Module</tt>.</p>
				2914
				2915	<p><!-- Convenience methods --></p></li>
				2916	</ul>
				2917
				2918	<hr>
				2919
				2920	<ul>
				2921	<li><tt><a href="#Function">Function</a> *getFunction(const std::string
				2922	&Name, const <a href="#FunctionType">FunctionType</a> *Ty)</tt>
				2923
				2924	<p>Look up the specified function in the <tt>Module</tt> <a
				2925	href="#SymbolTable"><tt>SymbolTable</tt></a>. If it does not exist, return
				2926	<tt>null</tt>.</p></li>
				2927
				2928	<li><tt><a href="#Function">Function</a> *getOrInsertFunction(const
				2929	std::string &Name, const <a href="#FunctionType">FunctionType</a> *T)</tt>
				2930
				2931	<p>Look up the specified function in the <tt>Module</tt> <a
				2932	href="#SymbolTable"><tt>SymbolTable</tt></a>. If it does not exist, add an
				2933	external declaration for the function and return it.</p></li>
				2934
				2935	<li><tt>std::string getTypeName(const <a href="#Type">Type</a> *Ty)</tt>
				2936
				2937	<p>If there is at least one entry in the <a
				2938	href="#SymbolTable"><tt>SymbolTable</tt></a> for the specified <a
				2939	href="#Type"><tt>Type</tt></a>, return it. Otherwise return the empty
				2940	string.</p></li>
				2941
				2942	<li><tt>bool addTypeName(const std::string &Name, const <a
				2943	href="#Type">Type</a> *Ty)</tt>
				2944
				2945	<p>Insert an entry in the <a href="#SymbolTable"><tt>SymbolTable</tt></a>
				2946	mapping <tt>Name</tt> to <tt>Ty</tt>. If there is already an entry for this
				2947	name, true is returned and the <a
				2948	href="#SymbolTable"><tt>SymbolTable</tt></a> is not modified.</p></li>
				2949	</ul>
				2950
				2951	</div>
				2952
				2953
				2954	<!-- ======================================================================= -->
				2955	<div class="doc_subsection">
				2956	<a name="Value">The <tt>Value</tt> class</a>
				2957	</div>
				2958
				2959	<div class="doc_text">
				2960
				2961	<p><tt>#include "<a href="/doxygen/Value_8h-source.html">llvm/Value.h</a>"</tt>
				2962	<br>
				2963	doxygen info: <a href="/doxygen/classllvm_1_1Value.html">Value Class</a></p>
				2964
				2965	<p>The <tt>Value</tt> class is the most important class in the LLVM Source
				2966	base. It represents a typed value that may be used (among other things) as an
				2967	operand to an instruction. There are many different types of <tt>Value</tt>s,
				2968	such as <a href="#Constant"><tt>Constant</tt></a>s,<a
				2969	href="#Argument"><tt>Argument</tt></a>s. Even <a
				2970	href="#Instruction"><tt>Instruction</tt></a>s and <a
				2971	href="#Function"><tt>Function</tt></a>s are <tt>Value</tt>s.</p>
				2972
				2973	<p>A particular <tt>Value</tt> may be used many times in the LLVM representation
				2974	for a program. For example, an incoming argument to a function (represented
				2975	with an instance of the <a href="#Argument">Argument</a> class) is "used" by
				2976	every instruction in the function that references the argument. To keep track
				2977	of this relationship, the <tt>Value</tt> class keeps a list of all of the <a
				2978	href="#User"><tt>User</tt></a>s that is using it (the <a
				2979	href="#User"><tt>User</tt></a> class is a base class for all nodes in the LLVM
				2980	graph that can refer to <tt>Value</tt>s). This use list is how LLVM represents
				2981	def-use information in the program, and is accessible through the <tt>use_</tt>*
				2982	methods, shown below.</p>
				2983
				2984	<p>Because LLVM is a typed representation, every LLVM <tt>Value</tt> is typed,
				2985	and this <a href="#Type">Type</a> is available through the <tt>getType()</tt>
				2986	method. In addition, all LLVM values can be named. The "name" of the
				2987	<tt>Value</tt> is a symbolic string printed in the LLVM code:</p>
				2988
				2989	<div class="doc_code">
				2990	<pre>
				2991	%<b>foo</b> = add i32 1, 2
				2992	</pre>
				2993	</div>
				2994
				2995	<p><a name="nameWarning">The name of this instruction is "foo".</a> <b>NOTE</b>
				2996	that the name of any value may be missing (an empty string), so names should
				2997	<b>ONLY</b> be used for debugging (making the source code easier to read,
				2998	debugging printouts), they should not be used to keep track of values or map
				2999	between them. For this purpose, use a <tt>std::map</tt> of pointers to the
				3000	<tt>Value</tt> itself instead.</p>
				3001
				3002	<p>One important aspect of LLVM is that there is no distinction between an SSA
				3003	variable and the operation that produces it. Because of this, any reference to
				3004	the value produced by an instruction (or the value available as an incoming
				3005	argument, for example) is represented as a direct pointer to the instance of
				3006	the class that
				3007	represents this value. Although this may take some getting used to, it
				3008	simplifies the representation and makes it easier to manipulate.</p>
				3009
				3010	</div>
				3011
				3012	<!-- _______________________________________________________________________ -->
				3013	<div class="doc_subsubsection">
				3014	<a name="m_Value">Important Public Members of the <tt>Value</tt> class</a>
				3015	</div>
				3016
				3017	<div class="doc_text">
				3018
				3019	<ul>
				3020	<li><tt>Value::use_iterator</tt> - Typedef for iterator over the
				3021	use-list<br>
				3022	<tt>Value::use_const_iterator</tt> - Typedef for const_iterator over
				3023	the use-list<br>
				3024	<tt>unsigned use_size()</tt> - Returns the number of users of the
				3025	value.<br>
				3026	<tt>bool use_empty()</tt> - Returns true if there are no users.<br>
				3027	<tt>use_iterator use_begin()</tt> - Get an iterator to the start of
				3028	the use-list.<br>
				3029	<tt>use_iterator use_end()</tt> - Get an iterator to the end of the
				3030	use-list.<br>
				3031	<tt><a href="#User">User</a> *use_back()</tt> - Returns the last
				3032	element in the list.
				3033	<p> These methods are the interface to access the def-use
				3034	information in LLVM. As with all other iterators in LLVM, the naming
				3035	conventions follow the conventions defined by the <a href="#stl">STL</a>.</p>
				3036	</li>
				3037	<li><tt><a href="#Type">Type</a> *getType() const</tt>
				3038	<p>This method returns the Type of the Value.</p>
				3039	</li>
				3040	<li><tt>bool hasName() const</tt><br>
				3041	<tt>std::string getName() const</tt><br>
				3042	<tt>void setName(const std::string &Name)</tt>
				3043	<p> This family of methods is used to access and assign a name to a <tt>Value</tt>,
				3044	be aware of the <a href="#nameWarning">precaution above</a>.</p>
				3045	</li>
				3046	<li><tt>void replaceAllUsesWith(Value *V)</tt>
				3047
				3048	<p>This method traverses the use list of a <tt>Value</tt> changing all <a
				3049	href="#User"><tt>User</tt>s</a> of the current value to refer to
				3050	"<tt>V</tt>" instead. For example, if you detect that an instruction always
				3051	produces a constant value (for example through constant folding), you can
				3052	replace all uses of the instruction with the constant like this:</p>
				3053
				3054	<div class="doc_code">
				3055	<pre>
				3056	Inst->replaceAllUsesWith(ConstVal);
				3057	</pre>
				3058	</div>
				3059
				3060	</ul>
				3061
				3062	</div>
				3063
				3064	<!-- ======================================================================= -->
				3065	<div class="doc_subsection">
				3066	<a name="User">The <tt>User</tt> class</a>
				3067	</div>
				3068
				3069	<div class="doc_text">
				3070
				3071	<p>
				3072	<tt>#include "<a href="/doxygen/User_8h-source.html">llvm/User.h</a>"</tt><br>
				3073	doxygen info: <a href="/doxygen/classllvm_1_1User.html">User Class</a><br>
				3074	Superclass: <a href="#Value"><tt>Value</tt></a></p>
				3075
				3076	<p>The <tt>User</tt> class is the common base class of all LLVM nodes that may
				3077	refer to <a href="#Value"><tt>Value</tt></a>s. It exposes a list of "Operands"
				3078	that are all of the <a href="#Value"><tt>Value</tt></a>s that the User is
				3079	referring to. The <tt>User</tt> class itself is a subclass of
				3080	<tt>Value</tt>.</p>
				3081
				3082	<p>The operands of a <tt>User</tt> point directly to the LLVM <a
				3083	href="#Value"><tt>Value</tt></a> that it refers to. Because LLVM uses Static
				3084	Single Assignment (SSA) form, there can only be one definition referred to,
				3085	allowing this direct connection. This connection provides the use-def
				3086	information in LLVM.</p>
				3087
				3088	</div>
				3089
				3090	<!-- _______________________________________________________________________ -->
				3091	<div class="doc_subsubsection">
				3092	<a name="m_User">Important Public Members of the <tt>User</tt> class</a>
				3093	</div>
				3094
				3095	<div class="doc_text">
				3096
				3097	<p>The <tt>User</tt> class exposes the operand list in two ways: through
				3098	an index access interface and through an iterator based interface.</p>
				3099
				3100	<ul>
				3101	<li><tt>Value *getOperand(unsigned i)</tt><br>
				3102	<tt>unsigned getNumOperands()</tt>
				3103	<p> These two methods expose the operands of the <tt>User</tt> in a
				3104	convenient form for direct access.</p></li>
				3105
				3106	<li><tt>User::op_iterator</tt> - Typedef for iterator over the operand
				3107	list<br>
				3108	<tt>op_iterator op_begin()</tt> - Get an iterator to the start of
				3109	the operand list.<br>
				3110	<tt>op_iterator op_end()</tt> - Get an iterator to the end of the
				3111	operand list.
				3112	<p> Together, these methods make up the iterator based interface to
				3113	the operands of a <tt>User</tt>.</p></li>
				3114	</ul>
				3115
				3116	</div>
				3117
				3118	<!-- ======================================================================= -->
				3119	<div class="doc_subsection">
				3120	<a name="Instruction">The <tt>Instruction</tt> class</a>
				3121	</div>
				3122
				3123	<div class="doc_text">
				3124
				3125	<p><tt>#include "</tt><tt><a
				3126	href="/doxygen/Instruction_8h-source.html">llvm/Instruction.h</a>"</tt><br>
				3127	doxygen info: <a href="/doxygen/classllvm_1_1Instruction.html">Instruction Class</a><br>
				3128	Superclasses: <a href="#User"><tt>User</tt></a>, <a
				3129	href="#Value"><tt>Value</tt></a></p>
				3130
				3131	<p>The <tt>Instruction</tt> class is the common base class for all LLVM
				3132	instructions. It provides only a few methods, but is a very commonly used
				3133	class. The primary data tracked by the <tt>Instruction</tt> class itself is the
				3134	opcode (instruction type) and the parent <a
				3135	href="#BasicBlock"><tt>BasicBlock</tt></a> the <tt>Instruction</tt> is embedded
				3136	into. To represent a specific type of instruction, one of many subclasses of
				3137	<tt>Instruction</tt> are used.</p>
				3138
				3139	<p> Because the <tt>Instruction</tt> class subclasses the <a
				3140	href="#User"><tt>User</tt></a> class, its operands can be accessed in the same
				3141	way as for other <a href="#User"><tt>User</tt></a>s (with the
				3142	<tt>getOperand()</tt>/<tt>getNumOperands()</tt> and
				3143	<tt>op_begin()</tt>/<tt>op_end()</tt> methods).</p> <p> An important file for
				3144	the <tt>Instruction</tt> class is the <tt>llvm/Instruction.def</tt> file. This
				3145	file contains some meta-data about the various different types of instructions
				3146	in LLVM. It describes the enum values that are used as opcodes (for example
				3147	<tt>Instruction::Add</tt> and <tt>Instruction::ICmp</tt>), as well as the
				3148	concrete sub-classes of <tt>Instruction</tt> that implement the instruction (for
				3149	example <tt><a href="#BinaryOperator">BinaryOperator</a></tt> and <tt><a
				3150	href="#CmpInst">CmpInst</a></tt>). Unfortunately, the use of macros in
				3151	this file confuses doxygen, so these enum values don't show up correctly in the
				3152	<a href="/doxygen/classllvm_1_1Instruction.html">doxygen output</a>.</p>
				3153
				3154	</div>
				3155
				3156	<!-- _______________________________________________________________________ -->
				3157	<div class="doc_subsubsection">
				3158	<a name="s_Instruction">Important Subclasses of the <tt>Instruction</tt>
				3159	class</a>
				3160	</div>
				3161	<div class="doc_text">
				3162	<ul>
				3163	<li><tt><a name="BinaryOperator">BinaryOperator</a></tt>
				3164	<p>This subclasses represents all two operand instructions whose operands
				3165	must be the same type, except for the comparison instructions.</p></li>
				3166	<li><tt><a name="CastInst">CastInst</a></tt>
				3167	<p>This subclass is the parent of the 12 casting instructions. It provides
				3168	common operations on cast instructions.</p>
				3169	<li><tt><a name="CmpInst">CmpInst</a></tt>
				3170	<p>This subclass respresents the two comparison instructions,
				3171	<a href="LangRef.html#i_icmp">ICmpInst</a> (integer opreands), and
				3172	<a href="LangRef.html#i_fcmp">FCmpInst</a> (floating point operands).</p>
				3173	<li><tt><a name="TerminatorInst">TerminatorInst</a></tt>
				3174	<p>This subclass is the parent of all terminator instructions (those which
				3175	can terminate a block).</p>
				3176	</ul>
				3177	</div>
				3178
				3179	<!-- _______________________________________________________________________ -->
				3180	<div class="doc_subsubsection">
				3181	<a name="m_Instruction">Important Public Members of the <tt>Instruction</tt>
				3182	class</a>
				3183	</div>
				3184
				3185	<div class="doc_text">
				3186
				3187	<ul>
				3188	<li><tt><a href="#BasicBlock">BasicBlock</a> *getParent()</tt>
				3189	<p>Returns the <a href="#BasicBlock"><tt>BasicBlock</tt></a> that
				3190	this <tt>Instruction</tt> is embedded into.</p></li>
				3191	<li><tt>bool mayWriteToMemory()</tt>
				3192	<p>Returns true if the instruction writes to memory, i.e. it is a
				3193	<tt>call</tt>,<tt>free</tt>,<tt>invoke</tt>, or <tt>store</tt>.</p></li>
				3194	<li><tt>unsigned getOpcode()</tt>
				3195	<p>Returns the opcode for the <tt>Instruction</tt>.</p></li>
				3196	<li><tt><a href="#Instruction">Instruction</a> *clone() const</tt>
				3197	<p>Returns another instance of the specified instruction, identical
				3198	in all ways to the original except that the instruction has no parent
				3199	(ie it's not embedded into a <a href="#BasicBlock"><tt>BasicBlock</tt></a>),
				3200	and it has no name</p></li>
				3201	</ul>
				3202
				3203	</div>
				3204
				3205	<!-- ======================================================================= -->
				3206	<div class="doc_subsection">
				3207	<a name="Constant">The <tt>Constant</tt> class and subclasses</a>
				3208	</div>
				3209
				3210	<div class="doc_text">
				3211
				3212	<p>Constant represents a base class for different types of constants. It
				3213	is subclassed by ConstantInt, ConstantArray, etc. for representing
				3214	the various types of Constants. <a href="#GlobalValue">GlobalValue</a> is also
				3215	a subclass, which represents the address of a global variable or function.
				3216	</p>
				3217
				3218	</div>
				3219
				3220	<!-- _______________________________________________________________________ -->
				3221	<div class="doc_subsubsection">Important Subclasses of Constant </div>
				3222	<div class="doc_text">
				3223	<ul>
				3224	<li>ConstantInt : This subclass of Constant represents an integer constant of
				3225	any width.
				3226	<ul>
				3227	<li><tt>const APInt& getValue() const</tt>: Returns the underlying
				3228	value of this constant, an APInt value.</li>
				3229	<li><tt>int64_t getSExtValue() const</tt>: Converts the underlying APInt
				3230	value to an int64_t via sign extension. If the value (not the bit width)
				3231	of the APInt is too large to fit in an int64_t, an assertion will result.
				3232	For this reason, use of this method is discouraged.</li>
				3233	<li><tt>uint64_t getZExtValue() const</tt>: Converts the underlying APInt
				3234	value to a uint64_t via zero extension. IF the value (not the bit width)
				3235	of the APInt is too large to fit in a uint64_t, an assertion will result.
				3236	For this reason, use of this method is discouraged.</li>
				3237	<li><tt>static ConstantInt* get(const APInt& Val)</tt>: Returns the
				3238	ConstantInt object that represents the value provided by <tt>Val</tt>.
				3239	The type is implied as the IntegerType that corresponds to the bit width
				3240	of <tt>Val</tt>.</li>
				3241	<li><tt>static ConstantInt* get(const Type *Ty, uint64_t Val)</tt>:
				3242	Returns the ConstantInt object that represents the value provided by
				3243	<tt>Val</tt> for integer type <tt>Ty</tt>.</li>
				3244	</ul>
				3245	</li>
				3246	<li>ConstantFP : This class represents a floating point constant.
				3247	<ul>
				3248	<li><tt>double getValue() const</tt>: Returns the underlying value of
				3249	this constant. </li>
				3250	</ul>
				3251	</li>
				3252	<li>ConstantArray : This represents a constant array.
				3253	<ul>
				3254	<li><tt>const std::vector<Use> &getValues() const</tt>: Returns
				3255	a vector of component constants that makeup this array. </li>
				3256	</ul>
				3257	</li>
				3258	<li>ConstantStruct : This represents a constant struct.
				3259	<ul>
				3260	<li><tt>const std::vector<Use> &getValues() const</tt>: Returns
				3261	a vector of component constants that makeup this array. </li>
				3262	</ul>
				3263	</li>
				3264	<li>GlobalValue : This represents either a global variable or a function. In
				3265	either case, the value is a constant fixed address (after linking).
				3266	</li>
				3267	</ul>
				3268	</div>
				3269
				3270
				3271	<!-- ======================================================================= -->
				3272	<div class="doc_subsection">
				3273	<a name="GlobalValue">The <tt>GlobalValue</tt> class</a>
				3274	</div>
				3275
				3276	<div class="doc_text">
				3277
				3278	<p><tt>#include "<a
				3279	href="/doxygen/GlobalValue_8h-source.html">llvm/GlobalValue.h</a>"</tt><br>
				3280	doxygen info: <a href="/doxygen/classllvm_1_1GlobalValue.html">GlobalValue
				3281	Class</a><br>
				3282	Superclasses: <a href="#Constant"><tt>Constant</tt></a>,
				3283	<a href="#User"><tt>User</tt></a>, <a href="#Value"><tt>Value</tt></a></p>
				3284
				3285	<p>Global values (<a href="#GlobalVariable"><tt>GlobalVariable</tt></a>s or <a
				3286	href="#Function"><tt>Function</tt></a>s) are the only LLVM values that are
				3287	visible in the bodies of all <a href="#Function"><tt>Function</tt></a>s.
				3288	Because they are visible at global scope, they are also subject to linking with
				3289	other globals defined in different translation units. To control the linking
				3290	process, <tt>GlobalValue</tt>s know their linkage rules. Specifically,
				3291	<tt>GlobalValue</tt>s know whether they have internal or external linkage, as
				3292	defined by the <tt>LinkageTypes</tt> enumeration.</p>
				3293
				3294	<p>If a <tt>GlobalValue</tt> has internal linkage (equivalent to being
				3295	<tt>static</tt> in C), it is not visible to code outside the current translation
				3296	unit, and does not participate in linking. If it has external linkage, it is
				3297	visible to external code, and does participate in linking. In addition to
				3298	linkage information, <tt>GlobalValue</tt>s keep track of which <a
				3299	href="#Module"><tt>Module</tt></a> they are currently part of.</p>
				3300
				3301	<p>Because <tt>GlobalValue</tt>s are memory objects, they are always referred to
				3302	by their <b>address</b>. As such, the <a href="#Type"><tt>Type</tt></a> of a
				3303	global is always a pointer to its contents. It is important to remember this
				3304	when using the <tt>GetElementPtrInst</tt> instruction because this pointer must
				3305	be dereferenced first. For example, if you have a <tt>GlobalVariable</tt> (a
				3306	subclass of <tt>GlobalValue)</tt> that is an array of 24 ints, type <tt>[24 x
				3307	i32]</tt>, then the <tt>GlobalVariable</tt> is a pointer to that array. Although
				3308	the address of the first element of this array and the value of the
				3309	<tt>GlobalVariable</tt> are the same, they have different types. The
				3310	<tt>GlobalVariable</tt>'s type is <tt>[24 x i32]</tt>. The first element's type
				3311	is <tt>i32.</tt> Because of this, accessing a global value requires you to
				3312	dereference the pointer with <tt>GetElementPtrInst</tt> first, then its elements
				3313	can be accessed. This is explained in the <a href="LangRef.html#globalvars">LLVM
				3314	Language Reference Manual</a>.</p>
				3315
				3316	</div>
				3317
				3318	<!-- _______________________________________________________________________ -->
				3319	<div class="doc_subsubsection">
				3320	<a name="m_GlobalValue">Important Public Members of the <tt>GlobalValue</tt>
				3321	class</a>
				3322	</div>
				3323
				3324	<div class="doc_text">
				3325
				3326	<ul>
				3327	<li><tt>bool hasInternalLinkage() const</tt><br>
				3328	<tt>bool hasExternalLinkage() const</tt><br>
				3329	<tt>void setInternalLinkage(bool HasInternalLinkage)</tt>
				3330	<p> These methods manipulate the linkage characteristics of the <tt>GlobalValue</tt>.</p>
				3331	<p> </p>
				3332	</li>
				3333	<li><tt><a href="#Module">Module</a> *getParent()</tt>
				3334	<p> This returns the <a href="#Module"><tt>Module</tt></a> that the
				3335	GlobalValue is currently embedded into.</p></li>
				3336	</ul>
				3337
				3338	</div>
				3339
				3340	<!-- ======================================================================= -->
				3341	<div class="doc_subsection">
				3342	<a name="Function">The <tt>Function</tt> class</a>
				3343	</div>
				3344
				3345	<div class="doc_text">
				3346
				3347	<p><tt>#include "<a
				3348	href="/doxygen/Function_8h-source.html">llvm/Function.h</a>"</tt><br> doxygen
				3349	info: <a href="/doxygen/classllvm_1_1Function.html">Function Class</a><br>
				3350	Superclasses: <a href="#GlobalValue"><tt>GlobalValue</tt></a>,
				3351	<a href="#Constant"><tt>Constant</tt></a>,
				3352	<a href="#User"><tt>User</tt></a>,
				3353	<a href="#Value"><tt>Value</tt></a></p>
				3354
				3355	<p>The <tt>Function</tt> class represents a single procedure in LLVM. It is
				3356	actually one of the more complex classes in the LLVM heirarchy because it must
				3357	keep track of a large amount of data. The <tt>Function</tt> class keeps track
				3358	of a list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s, a list of formal
				3359	<a href="#Argument"><tt>Argument</tt></a>s, and a
				3360	<a href="#SymbolTable"><tt>SymbolTable</tt></a>.</p>
				3361
				3362	<p>The list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s is the most
				3363	commonly used part of <tt>Function</tt> objects. The list imposes an implicit
				3364	ordering of the blocks in the function, which indicate how the code will be
				3365	layed out by the backend. Additionally, the first <a
				3366	href="#BasicBlock"><tt>BasicBlock</tt></a> is the implicit entry node for the
				3367	<tt>Function</tt>. It is not legal in LLVM to explicitly branch to this initial
				3368	block. There are no implicit exit nodes, and in fact there may be multiple exit
				3369	nodes from a single <tt>Function</tt>. If the <a
				3370	href="#BasicBlock"><tt>BasicBlock</tt></a> list is empty, this indicates that
				3371	the <tt>Function</tt> is actually a function declaration: the actual body of the
				3372	function hasn't been linked in yet.</p>
				3373
				3374	<p>In addition to a list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s, the
				3375	<tt>Function</tt> class also keeps track of the list of formal <a
				3376	href="#Argument"><tt>Argument</tt></a>s that the function receives. This
				3377	container manages the lifetime of the <a href="#Argument"><tt>Argument</tt></a>
				3378	nodes, just like the <a href="#BasicBlock"><tt>BasicBlock</tt></a> list does for
				3379	the <a href="#BasicBlock"><tt>BasicBlock</tt></a>s.</p>
				3380
				3381	<p>The <a href="#SymbolTable"><tt>SymbolTable</tt></a> is a very rarely used
				3382	LLVM feature that is only used when you have to look up a value by name. Aside
				3383	from that, the <a href="#SymbolTable"><tt>SymbolTable</tt></a> is used
				3384	internally to make sure that there are not conflicts between the names of <a
				3385	href="#Instruction"><tt>Instruction</tt></a>s, <a
				3386	href="#BasicBlock"><tt>BasicBlock</tt></a>s, or <a
				3387	href="#Argument"><tt>Argument</tt></a>s in the function body.</p>
				3388
				3389	<p>Note that <tt>Function</tt> is a <a href="#GlobalValue">GlobalValue</a>
				3390	and therefore also a <a href="#Constant">Constant</a>. The value of the function
				3391	is its address (after linking) which is guaranteed to be constant.</p>
				3392	</div>
				3393
				3394	<!-- _______________________________________________________________________ -->
				3395	<div class="doc_subsubsection">
				3396	<a name="m_Function">Important Public Members of the <tt>Function</tt>
				3397	class</a>
				3398	</div>
				3399
				3400	<div class="doc_text">
				3401
				3402	<ul>
				3403	<li><tt>Function(const </tt><tt><a href="#FunctionType">FunctionType</a>
				3404	Ty, LinkageTypes Linkage, const std::string &N = "", Module Parent = 0)</tt>
				3405
				3406	<p>Constructor used when you need to create new <tt>Function</tt>s to add
				3407	the the program. The constructor must specify the type of the function to
				3408	create and what type of linkage the function should have. The <a
				3409	href="#FunctionType"><tt>FunctionType</tt></a> argument
				3410	specifies the formal arguments and return value for the function. The same
				3411	<a href="#FunctionType"><tt>FunctionType</tt></a> value can be used to
				3412	create multiple functions. The <tt>Parent</tt> argument specifies the Module
				3413	in which the function is defined. If this argument is provided, the function
				3414	will automatically be inserted into that module's list of
				3415	functions.</p></li>
				3416
Chris Lattner	5e70957	2008-11-25 18:34:50 +0000	[diff] [blame]	3417	<li><tt>bool isDeclaration()</tt>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	3418
				3419	<p>Return whether or not the <tt>Function</tt> has a body defined. If the
				3420	function is "external", it does not have a body, and thus must be resolved
				3421	by linking with a function defined in a different translation unit.</p></li>
				3422
				3423	<li><tt>Function::iterator</tt> - Typedef for basic block list iterator<br>
				3424	<tt>Function::const_iterator</tt> - Typedef for const_iterator.<br>
				3425
				3426	<tt>begin()</tt>, <tt>end()</tt>
				3427	<tt>size()</tt>, <tt>empty()</tt>
				3428
				3429	<p>These are forwarding methods that make it easy to access the contents of
				3430	a <tt>Function</tt> object's <a href="#BasicBlock"><tt>BasicBlock</tt></a>
				3431	list.</p></li>
				3432
				3433	<li><tt>Function::BasicBlockListType &getBasicBlockList()</tt>
				3434
				3435	<p>Returns the list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s. This
				3436	is necessary to use when you need to update the list or perform a complex
				3437	action that doesn't have a forwarding method.</p></li>
				3438
				3439	<li><tt>Function::arg_iterator</tt> - Typedef for the argument list
				3440	iterator<br>
				3441	<tt>Function::const_arg_iterator</tt> - Typedef for const_iterator.<br>
				3442
				3443	<tt>arg_begin()</tt>, <tt>arg_end()</tt>
				3444	<tt>arg_size()</tt>, <tt>arg_empty()</tt>
				3445
				3446	<p>These are forwarding methods that make it easy to access the contents of
				3447	a <tt>Function</tt> object's <a href="#Argument"><tt>Argument</tt></a>
				3448	list.</p></li>
				3449
				3450	<li><tt>Function::ArgumentListType &getArgumentList()</tt>
				3451
				3452	<p>Returns the list of <a href="#Argument"><tt>Argument</tt></a>s. This is
				3453	necessary to use when you need to update the list or perform a complex
				3454	action that doesn't have a forwarding method.</p></li>
				3455
				3456	<li><tt><a href="#BasicBlock">BasicBlock</a> &getEntryBlock()</tt>
				3457
				3458	<p>Returns the entry <a href="#BasicBlock"><tt>BasicBlock</tt></a> for the
				3459	function. Because the entry block for the function is always the first
				3460	block, this returns the first block of the <tt>Function</tt>.</p></li>
				3461
				3462	<li><tt><a href="#Type">Type</a> *getReturnType()</tt><br>
				3463	<tt><a href="#FunctionType">FunctionType</a> *getFunctionType()</tt>
				3464
				3465	<p>This traverses the <a href="#Type"><tt>Type</tt></a> of the
				3466	<tt>Function</tt> and returns the return type of the function, or the <a
				3467	href="#FunctionType"><tt>FunctionType</tt></a> of the actual
				3468	function.</p></li>
				3469
				3470	<li><tt><a href="#SymbolTable">SymbolTable</a> *getSymbolTable()</tt>
				3471
				3472	<p> Return a pointer to the <a href="#SymbolTable"><tt>SymbolTable</tt></a>
				3473	for this <tt>Function</tt>.</p></li>
				3474	</ul>
				3475
				3476	</div>
				3477
				3478	<!-- ======================================================================= -->
				3479	<div class="doc_subsection">
				3480	<a name="GlobalVariable">The <tt>GlobalVariable</tt> class</a>
				3481	</div>
				3482
				3483	<div class="doc_text">
				3484
				3485	<p><tt>#include "<a
				3486	href="/doxygen/GlobalVariable_8h-source.html">llvm/GlobalVariable.h</a>"</tt>
				3487	<br>
				3488	doxygen info: <a href="/doxygen/classllvm_1_1GlobalVariable.html">GlobalVariable
				3489	Class</a><br>
				3490	Superclasses: <a href="#GlobalValue"><tt>GlobalValue</tt></a>,
				3491	<a href="#Constant"><tt>Constant</tt></a>,
				3492	<a href="#User"><tt>User</tt></a>,
				3493	<a href="#Value"><tt>Value</tt></a></p>
				3494
				3495	<p>Global variables are represented with the (suprise suprise)
				3496	<tt>GlobalVariable</tt> class. Like functions, <tt>GlobalVariable</tt>s are also
				3497	subclasses of <a href="#GlobalValue"><tt>GlobalValue</tt></a>, and as such are
				3498	always referenced by their address (global values must live in memory, so their
				3499	"name" refers to their constant address). See
				3500	<a href="#GlobalValue"><tt>GlobalValue</tt></a> for more on this. Global
				3501	variables may have an initial value (which must be a
				3502	<a href="#Constant"><tt>Constant</tt></a>), and if they have an initializer,
				3503	they may be marked as "constant" themselves (indicating that their contents
				3504	never change at runtime).</p>
				3505	</div>
				3506
				3507	<!-- _______________________________________________________________________ -->
				3508	<div class="doc_subsubsection">
				3509	<a name="m_GlobalVariable">Important Public Members of the
				3510	<tt>GlobalVariable</tt> class</a>
				3511	</div>
				3512
				3513	<div class="doc_text">
				3514
				3515	<ul>
				3516	<li><tt>GlobalVariable(const </tt><tt><a href="#Type">Type</a> *Ty, bool
				3517	isConstant, LinkageTypes& Linkage, <a href="#Constant">Constant</a>
				3518	Initializer = 0, const std::string &Name = "", Module Parent = 0)</tt>
				3519
				3520	<p>Create a new global variable of the specified type. If
				3521	<tt>isConstant</tt> is true then the global variable will be marked as
				3522	unchanging for the program. The Linkage parameter specifies the type of
Duncan Sands	19d161f	2009-03-07 15:45:40 +0000	[diff] [blame]	3523	linkage (internal, external, weak, linkonce, appending) for the variable.
				3524	If the linkage is InternalLinkage, WeakAnyLinkage, WeakODRLinkage,
				3525	LinkOnceAnyLinkage or LinkOnceODRLinkage,  then the resultant
				3526	global variable will have internal linkage. AppendingLinkage concatenates
				3527	together all instances (in different translation units) of the variable
				3528	into a single variable but is only applicable to arrays.  See
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	3529	the <a href="LangRef.html#modulestructure">LLVM Language Reference</a> for
				3530	further details on linkage types. Optionally an initializer, a name, and the
				3531	module to put the variable into may be specified for the global variable as
				3532	well.</p></li>
				3533
				3534	<li><tt>bool isConstant() const</tt>
				3535
				3536	<p>Returns true if this is a global variable that is known not to
				3537	be modified at runtime.</p></li>
				3538
				3539	<li><tt>bool hasInitializer()</tt>
				3540
				3541	<p>Returns true if this <tt>GlobalVariable</tt> has an intializer.</p></li>
				3542
				3543	<li><tt><a href="#Constant">Constant</a> *getInitializer()</tt>
				3544
				3545	<p>Returns the intial value for a <tt>GlobalVariable</tt>. It is not legal
				3546	to call this method if there is no initializer.</p></li>
				3547	</ul>
				3548
				3549	</div>
				3550
				3551
				3552	<!-- ======================================================================= -->
				3553	<div class="doc_subsection">
				3554	<a name="BasicBlock">The <tt>BasicBlock</tt> class</a>
				3555	</div>
				3556
				3557	<div class="doc_text">
				3558
				3559	<p><tt>#include "<a
				3560	href="/doxygen/BasicBlock_8h-source.html">llvm/BasicBlock.h</a>"</tt><br>
Stefanus Du Toit	f017c85	2009-06-17 21:12:26 +0000	[diff] [blame]	3561	doxygen info: <a href="/doxygen/classllvm_1_1BasicBlock.html">BasicBlock
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	3562	Class</a><br>
				3563	Superclass: <a href="#Value"><tt>Value</tt></a></p>
				3564
				3565	<p>This class represents a single entry multiple exit section of the code,
				3566	commonly known as a basic block by the compiler community. The
				3567	<tt>BasicBlock</tt> class maintains a list of <a
				3568	href="#Instruction"><tt>Instruction</tt></a>s, which form the body of the block.
				3569	Matching the language definition, the last element of this list of instructions
				3570	is always a terminator instruction (a subclass of the <a
				3571	href="#TerminatorInst"><tt>TerminatorInst</tt></a> class).</p>
				3572
				3573	<p>In addition to tracking the list of instructions that make up the block, the
				3574	<tt>BasicBlock</tt> class also keeps track of the <a
				3575	href="#Function"><tt>Function</tt></a> that it is embedded into.</p>
				3576
				3577	<p>Note that <tt>BasicBlock</tt>s themselves are <a
				3578	href="#Value"><tt>Value</tt></a>s, because they are referenced by instructions
				3579	like branches and can go in the switch tables. <tt>BasicBlock</tt>s have type
				3580	<tt>label</tt>.</p>
				3581
				3582	</div>
				3583
				3584	<!-- _______________________________________________________________________ -->
				3585	<div class="doc_subsubsection">
				3586	<a name="m_BasicBlock">Important Public Members of the <tt>BasicBlock</tt>
				3587	class</a>
				3588	</div>
				3589
				3590	<div class="doc_text">
				3591	<ul>
				3592
				3593	<li><tt>BasicBlock(const std::string &Name = "", </tt><tt><a
				3594	href="#Function">Function</a> *Parent = 0)</tt>
				3595
				3596	<p>The <tt>BasicBlock</tt> constructor is used to create new basic blocks for
				3597	insertion into a function. The constructor optionally takes a name for the new
				3598	block, and a <a href="#Function"><tt>Function</tt></a> to insert it into. If
				3599	the <tt>Parent</tt> parameter is specified, the new <tt>BasicBlock</tt> is
				3600	automatically inserted at the end of the specified <a
				3601	href="#Function"><tt>Function</tt></a>, if not specified, the BasicBlock must be
				3602	manually inserted into the <a href="#Function"><tt>Function</tt></a>.</p></li>
				3603
				3604	<li><tt>BasicBlock::iterator</tt> - Typedef for instruction list iterator<br>
				3605	<tt>BasicBlock::const_iterator</tt> - Typedef for const_iterator.<br>
				3606	<tt>begin()</tt>, <tt>end()</tt>, <tt>front()</tt>, <tt>back()</tt>,
				3607	<tt>size()</tt>, <tt>empty()</tt>
				3608	STL-style functions for accessing the instruction list.
				3609
				3610	<p>These methods and typedefs are forwarding functions that have the same
				3611	semantics as the standard library methods of the same names. These methods
				3612	expose the underlying instruction list of a basic block in a way that is easy to
				3613	manipulate. To get the full complement of container operations (including
				3614	operations to update the list), you must use the <tt>getInstList()</tt>
				3615	method.</p></li>
				3616
				3617	<li><tt>BasicBlock::InstListType &getInstList()</tt>
				3618
				3619	<p>This method is used to get access to the underlying container that actually
				3620	holds the Instructions. This method must be used when there isn't a forwarding
				3621	function in the <tt>BasicBlock</tt> class for the operation that you would like
				3622	to perform. Because there are no forwarding functions for "updating"
				3623	operations, you need to use this if you want to update the contents of a
				3624	<tt>BasicBlock</tt>.</p></li>
				3625
				3626	<li><tt><a href="#Function">Function</a> *getParent()</tt>
				3627
				3628	<p> Returns a pointer to <a href="#Function"><tt>Function</tt></a> the block is
				3629	embedded into, or a null pointer if it is homeless.</p></li>
				3630
				3631	<li><tt><a href="#TerminatorInst">TerminatorInst</a> *getTerminator()</tt>
				3632
				3633	<p> Returns a pointer to the terminator instruction that appears at the end of
				3634	the <tt>BasicBlock</tt>. If there is no terminator instruction, or if the last
				3635	instruction in the block is not a terminator, then a null pointer is
				3636	returned.</p></li>
				3637
				3638	</ul>
				3639
				3640	</div>
				3641
				3642
				3643	<!-- ======================================================================= -->
				3644	<div class="doc_subsection">
				3645	<a name="Argument">The <tt>Argument</tt> class</a>
				3646	</div>
				3647
				3648	<div class="doc_text">
				3649
				3650	<p>This subclass of Value defines the interface for incoming formal
				3651	arguments to a function. A Function maintains a list of its formal
				3652	arguments. An argument has a pointer to the parent Function.</p>
				3653
				3654	</div>
				3655
				3656	<!-- *********************************************************************** -->
				3657	<hr>
				3658	<address>
				3659	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
Misha Brukman	947321d	2008-12-11 17:34:48 +0000	[diff] [blame]	3660	src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	3661	<a href="http://validator.w3.org/check/referer"><img
Gabor Greif	7dabe38	2008-06-18 14:05:31 +0000	[diff] [blame]	3662	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01 Strict"></a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	3663
				3664	<a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a> and
				3665	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				3666	<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
				3667	Last modified: $Date$
				3668	</address>
				3669
				3670	</body>
				3671	</html>