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

blob: 7c3fa81d443af95208045478c18cadf7feeefb01 [file] [log] [blame]

Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
				2	"http://www.w3.org/TR/html4/strict.dtd">
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	3	<html>
				4	<head>
Misha Brukman	3eef5d4	2004-07-01 15:33:24 +0000	[diff] [blame]	5	<title>LLVM Alias Analysis Infrastructure</title>
Misha Brukman	c6ef559	2004-01-15 19:04:12 +0000	[diff] [blame]	6	<link rel="stylesheet" href="llvm.css" type="text/css">
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	7	</head>
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	8	<body>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	9
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	10	<div class="doc_title">
Misha Brukman	3eef5d4	2004-07-01 15:33:24 +0000	[diff] [blame]	11	LLVM Alias Analysis Infrastructure
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	12	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	13
				14	<ol>
Misha Brukman	9782b03	2003-10-23 02:29:42 +0000	[diff] [blame]	15	<li><a href="#introduction">Introduction</a></li>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	16
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	17	<li><a href="#overview"><tt>AliasAnalysis</tt> Class Overview</a>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	18	<ul>
Misha Brukman	9782b03	2003-10-23 02:29:42 +0000	[diff] [blame]	19	<li><a href="#pointers">Representation of Pointers</a></li>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	20	<li><a href="#alias">The <tt>alias</tt> method</a></li>
Misha Brukman	9782b03	2003-10-23 02:29:42 +0000	[diff] [blame]	21	<li><a href="#ModRefInfo">The <tt>getModRefInfo</tt> methods</a></li>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	22	<li><a href="#OtherItfs">Other useful <tt>AliasAnalysis</tt> methods</a></li>
				23	</ul>
				24	</li>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	25
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	26	<li><a href="#writingnew">Writing a new <tt>AliasAnalysis</tt> Implementation</a>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	27	<ul>
Misha Brukman	9782b03	2003-10-23 02:29:42 +0000	[diff] [blame]	28	<li><a href="#passsubclasses">Different Pass styles</a></li>
				29	<li><a href="#requiredcalls">Required initialization calls</a></li>
				30	<li><a href="#interfaces">Interfaces which may be specified</a></li>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	31	<li><a href="#chaining"><tt>AliasAnalysis</tt> chaining behavior</a></li>
				32	<li><a href="#updating">Updating analysis results for transformations</a></li>
Misha Brukman	9782b03	2003-10-23 02:29:42 +0000	[diff] [blame]	33	<li><a href="#implefficiency">Efficiency Issues</a></li>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	34	</ul>
				35	</li>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	36
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	37	<li><a href="#using">Using alias analysis results</a>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	38	<ul>
Misha Brukman	9782b03	2003-10-23 02:29:42 +0000	[diff] [blame]	39	<li><a href="#loadvn">Using the <tt>-load-vn</tt> Pass</a></li>
				40	<li><a href="#ast">Using the <tt>AliasSetTracker</tt> class</a></li>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	41	<li><a href="#direct">Using the <tt>AliasAnalysis</tt> interface directly</a></li>
				42	</ul>
				43	</li>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	44
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	45	<li><a href="#exist">Existing alias analysis implementations and clients</a>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	46	<ul>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	47	<li><a href="#impls">Available <tt>AliasAnalysis</tt> implementations</a></li>
				48	<li><a href="#aliasanalysis-xforms">Alias analysis driven transformations</a></li>
Misha Brukman	3eef5d4	2004-07-01 15:33:24 +0000	[diff] [blame]	49	<li><a href="#aliasanalysis-debug">Clients for debugging and evaluation of
				50	implementations</a></li>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	51	</ul>
				52	</li>
Owen Anderson	d263cfa	2007-10-02 00:43:25 +0000	[diff] [blame^]	53	<li><a hread="#memdep">Memory Dependence Analysis</a></li>
Misha Brukman	9782b03	2003-10-23 02:29:42 +0000	[diff] [blame]	54	</ol>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	55
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	56	<div class="doc_author">
				57	<p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	58	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	59
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	60	<!-- *********************************************************************** -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	61	<div class="doc_section">
				62	<a name="introduction">Introduction</a>
				63	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	64	<!-- *********************************************************************** -->
				65
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	66	<div class="doc_text">
Misha Brukman	bc2d330	2003-11-21 22:30:25 +0000	[diff] [blame]	67
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	68	<p>Alias Analysis (aka Pointer Analysis) is a class of techniques which attempt
				69	to determine whether or not two pointers ever can point to the same object in
				70	memory. There are many different algorithms for alias analysis and many
				71	different ways of classifying them: flow-sensitive vs flow-insensitive,
				72	context-sensitive vs context-insensitive, field-sensitive vs field-insensitive,
				73	unification-based vs subset-based, etc. Traditionally, alias analyses respond
Duncan Sands	16f122e	2007-03-30 12:22:09 +0000	[diff] [blame]	74	to a query with a <a href="#MustMayNo">Must, May, or No</a> alias response,
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	75	indicating that two pointers always point to the same object, might point to the
				76	same object, or are known to never point to the same object.</p>
Misha Brukman	bc2d330	2003-11-21 22:30:25 +0000	[diff] [blame]	77
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	78	<p>The LLVM <a
Reid Spencer	ca05854	2006-03-14 05:39:39 +0000	[diff] [blame]	79	href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	80	class is the primary interface used by clients and implementations of alias
				81	analyses in the LLVM system. This class is the common interface between clients
				82	of alias analysis information and the implementations providing it, and is
				83	designed to support a wide range of implementations and clients (but currently
				84	all clients are assumed to be flow-insensitive). In addition to simple alias
				85	analysis information, this class exposes Mod/Ref information from those
				86	implementations which can provide it, allowing for powerful analyses and
				87	transformations to work well together.</p>
Misha Brukman	bc2d330	2003-11-21 22:30:25 +0000	[diff] [blame]	88
				89	<p>This document contains information necessary to successfully implement this
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	90	interface, use it, and to test both sides. It also explains some of the finer
				91	points about what exactly results mean. If you feel that something is unclear
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	92	or should be added, please <a href="mailto:sabre@nondot.org">let me
Misha Brukman	bc2d330	2003-11-21 22:30:25 +0000	[diff] [blame]	93	know</a>.</p>
				94
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	95	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	96
				97	<!-- *********************************************************************** -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	98	<div class="doc_section">
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	99	<a name="overview"><tt>AliasAnalysis</tt> Class Overview</a>
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	100	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	101	<!-- *********************************************************************** -->
				102
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	103	<div class="doc_text">
Misha Brukman	bc2d330	2003-11-21 22:30:25 +0000	[diff] [blame]	104
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	105	<p>The <a
Reid Spencer	ca05854	2006-03-14 05:39:39 +0000	[diff] [blame]	106	href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	107	class defines the interface that the various alias analysis implementations
				108	should support. This class exports two important enums: <tt>AliasResult</tt>
				109	and <tt>ModRefResult</tt> which represent the result of an alias query or a
				110	mod/ref query, respectively.</p>
Misha Brukman	bc2d330	2003-11-21 22:30:25 +0000	[diff] [blame]	111
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	112	<p>The <tt>AliasAnalysis</tt> interface exposes information about memory,
				113	represented in several different ways. In particular, memory objects are
				114	represented as a starting address and size, and function calls are represented
				115	as the actual <tt>call</tt> or <tt>invoke</tt> instructions that performs the
				116	call. The <tt>AliasAnalysis</tt> interface also exposes some helper methods
				117	which allow you to get mod/ref information for arbitrary instructions.</p>
Misha Brukman	bc2d330	2003-11-21 22:30:25 +0000	[diff] [blame]	118
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	119	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	120
				121	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	122	<div class="doc_subsection">
				123	<a name="pointers">Representation of Pointers</a>
				124	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	125
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	126	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	127
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	128	<p>Most importantly, the <tt>AliasAnalysis</tt> class provides several methods
				129	which are used to query whether or not two memory objects alias, whether
				130	function calls can modify or read a memory object, etc. For all of these
				131	queries, memory objects are represented as a pair of their starting address (a
				132	symbolic LLVM <tt>Value*</tt>) and a static size.</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	133
				134	<p>Representing memory objects as a starting address and a size is critically
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	135	important for correct Alias Analyses. For example, consider this (silly, but
				136	possible) C code:</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	137
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	138	<div class="doc_code">
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	139	<pre>
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	140	int i;
				141	char C[2];
				142	char A[10];
				143	/* ... */
				144	for (i = 0; i != 10; ++i) {
				145	C[0] = A[i]; /* One byte store */
				146	C[1] = A[9-i]; /* One byte store */
				147	}
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	148	</pre>
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	149	</div>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	150
				151	<p>In this case, the <tt>basicaa</tt> pass will disambiguate the stores to
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	152	<tt>C[0]</tt> and <tt>C[1]</tt> because they are accesses to two distinct
				153	locations one byte apart, and the accesses are each one byte. In this case, the
				154	LICM pass can use store motion to remove the stores from the loop. In
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	155	constrast, the following code:</p>
				156
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	157	<div class="doc_code">
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	158	<pre>
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	159	int i;
				160	char C[2];
				161	char A[10];
				162	/* ... */
				163	for (i = 0; i != 10; ++i) {
				164	((short)C)[0] = A[i]; / Two byte store! */
				165	C[1] = A[9-i]; /* One byte store */
				166	}
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	167	</pre>
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	168	</div>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	169
				170	<p>In this case, the two stores to C do alias each other, because the access to
				171	the <tt>&C[0]</tt> element is a two byte access. If size information wasn't
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	172	available in the query, even the first case would have to conservatively assume
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	173	that the accesses alias.</p>
				174
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	175	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	176
				177	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	178	<div class="doc_subsection">
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	179	<a name="alias">The <tt>alias</tt> method</a>
				180	</div>
				181
				182	<div class="doc_text">
				183	The <tt>alias</tt> method is the primary interface used to determine whether or
				184	not two memory objects alias each other. It takes two memory objects as input
				185	and returns MustAlias, MayAlias, or NoAlias as appropriate.
				186	</div>
				187
				188	<!-- _______________________________________________________________________ -->
				189	<div class="doc_subsubsection">
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	190	<a name="MustMayNo">Must, May, and No Alias Responses</a>
				191	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	192
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	193	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	194
				195	<p>An Alias Analysis implementation can return one of three responses:
				196	MustAlias, MayAlias, and NoAlias. The No and May alias results are obvious: if
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	197	the two pointers can never equal each other, return NoAlias, if they might,
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	198	return MayAlias.</p>
				199
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	200	<p>The MustAlias response is trickier though. In LLVM, the Must Alias response
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	201	may only be returned if the two memory objects are guaranteed to always start at
				202	exactly the same location. If two memory objects overlap, but do not start at
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	203	the same location, return MayAlias.</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	204
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	205	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	206
				207	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	208	<div class="doc_subsection">
				209	<a name="ModRefInfo">The <tt>getModRefInfo</tt> methods</a>
				210	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	211
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	212	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	213
				214	<p>The <tt>getModRefInfo</tt> methods return information about whether the
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	215	execution of an instruction can read or modify a memory location. Mod/Ref
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	216	information is always conservative: if an instruction <b>might</b> read or write
				217	a location, ModRef is returned.</p>
				218
				219	<p>The <tt>AliasAnalysis</tt> class also provides a <tt>getModRefInfo</tt>
				220	method for testing dependencies between function calls. This method takes two
				221	call sites (CS1 & CS2), returns NoModRef if the two calls refer to disjoint
				222	memory locations, Ref if CS1 reads memory written by CS2, Mod if CS1 writes to
				223	memory read or written by CS2, or ModRef if CS1 might read or write memory
				224	accessed by CS2. Note that this relation is not commutative. Clients that use
				225	this method should be predicated on the <tt>hasNoModRefInfoForCalls()</tt>
				226	method, which indicates whether or not an analysis can provide mod/ref
				227	information for function call pairs (most can not). If this predicate is false,
				228	the client shouldn't waste analysis time querying the <tt>getModRefInfo</tt>
				229	method many times.</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	230
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	231	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	232
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	233
				234	<!-- ======================================================================= -->
				235	<div class="doc_subsection">
				236	<a name="OtherItfs">Other useful <tt>AliasAnalysis</tt> methods</a>
				237	</div>
				238
				239	<div class="doc_text">
				240
				241	<p>
				242	Several other tidbits of information are often collected by various alias
				243	analysis implementations and can be put to good use by various clients.
				244	</p>
				245
				246	</div>
				247
				248	<!-- _______________________________________________________________________ -->
				249	<div class="doc_subsubsection">
				250	The <tt>getMustAliases</tt> method
				251	</div>
				252
				253	<div class="doc_text">
				254
				255	<p>The <tt>getMustAliases</tt> method returns all values that are known to
				256	always must alias a pointer. This information can be provided in some cases for
				257	important objects like the null pointer and global values. Knowing that a
				258	pointer always points to a particular function allows indirect calls to be
				259	turned into direct calls, for example.</p>
				260
				261	</div>
				262
				263	<!-- _______________________________________________________________________ -->
				264	<div class="doc_subsubsection">
				265	The <tt>pointsToConstantMemory</tt> method
				266	</div>
				267
				268	<div class="doc_text">
				269
				270	<p>The <tt>pointsToConstantMemory</tt> method returns true if and only if the
				271	analysis can prove that the pointer only points to unchanging memory locations
				272	(functions, constant global variables, and the null pointer). This information
				273	can be used to refine mod/ref information: it is impossible for an unchanging
				274	memory location to be modified.</p>
				275
				276	</div>
				277
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	278	<!-- _______________________________________________________________________ -->
				279	<div class="doc_subsubsection">
				280	<a name="simplemodref">The <tt>doesNotAccessMemory</tt> and
				281	<tt>onlyReadsMemory</tt> methods</a>
				282	</div>
				283
				284	<div class="doc_text">
				285
				286	<p>These methods are used to provide very simple mod/ref information for
				287	function calls. The <tt>doesNotAccessMemory</tt> method returns true for a
				288	function if the analysis can prove that the function never reads or writes to
				289	memory, or if the function only reads from constant memory. Functions with this
				290	property are side-effect free and only depend on their input arguments, allowing
				291	them to be eliminated if they form common subexpressions or be hoisted out of
				292	loops. Many common functions behave this way (e.g., <tt>sin</tt> and
				293	<tt>cos</tt>) but many others do not (e.g., <tt>acos</tt>, which modifies the
				294	<tt>errno</tt> variable).</p>
				295
				296	<p>The <tt>onlyReadsMemory</tt> method returns true for a function if analysis
				297	can prove that (at most) the function only reads from non-volatile memory.
				298	Functions with this property are side-effect free, only depending on their input
				299	arguments and the state of memory when they are called. This property allows
				300	calls to these functions to be eliminated and moved around, as long as there is
				301	no store instruction that changes the contents of memory. Note that all
				302	functions that satisfy the <tt>doesNotAccessMemory</tt> method also satisfies
				303	<tt>onlyReadsMemory</tt>.</p>
				304
				305	</div>
				306
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	307	<!-- *********************************************************************** -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	308	<div class="doc_section">
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	309	<a name="writingnew">Writing a new <tt>AliasAnalysis</tt> Implementation</a>
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	310	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	311	<!-- *********************************************************************** -->
				312
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	313	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	314
				315	<p>Writing a new alias analysis implementation for LLVM is quite
				316	straight-forward. There are already several implementations that you can use
				317	for examples, and the following information should help fill in any details.
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	318	For a examples, take a look at the <a href="#impls">various alias analysis
				319	implementations</a> included with LLVM.</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	320
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	321	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	322
				323	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	324	<div class="doc_subsection">
				325	<a name="passsubclasses">Different Pass styles</a>
				326	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	327
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	328	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	329
				330	<p>The first step to determining what type of <a
				331	href="WritingAnLLVMPass.html">LLVM pass</a> you need to use for your Alias
				332	Analysis. As is the case with most other analyses and transformations, the
				333	answer should be fairly obvious from what type of problem you are trying to
				334	solve:</p>
				335
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	336	<ol>
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	337	<li>If you require interprocedural analysis, it should be a
				338	<tt>Pass</tt>.</li>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	339	<li>If you are a function-local analysis, subclass <tt>FunctionPass</tt>.</li>
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	340	<li>If you don't need to look at the program at all, subclass
				341	<tt>ImmutablePass</tt>.</li>
				342	</ol>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	343
				344	<p>In addition to the pass that you subclass, you should also inherit from the
Misha Brukman	b4dd539	2003-05-07 21:47:16 +0000	[diff] [blame]	345	<tt>AliasAnalysis</tt> interface, of course, and use the
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	346	<tt>RegisterAnalysisGroup</tt> template to register as an implementation of
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	347	<tt>AliasAnalysis</tt>.</p>
				348
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	349	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	350
				351	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	352	<div class="doc_subsection">
				353	<a name="requiredcalls">Required initialization calls</a>
				354	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	355
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	356	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	357
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	358	<p>Your subclass of <tt>AliasAnalysis</tt> is required to invoke two methods on
				359	the <tt>AliasAnalysis</tt> base class: <tt>getAnalysisUsage</tt> and
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	360	<tt>InitializeAliasAnalysis</tt>. In particular, your implementation of
				361	<tt>getAnalysisUsage</tt> should explicitly call into the
				362	<tt>AliasAnalysis::getAnalysisUsage</tt> method in addition to doing any
				363	declaring any pass dependencies your pass has. Thus you should have something
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	364	like this:</p>
				365
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	366	<div class="doc_code">
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	367	<pre>
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	368	void getAnalysisUsage(AnalysisUsage &AU) const {
				369	AliasAnalysis::getAnalysisUsage(AU);
				370	<i>// declare your dependencies here.</i>
				371	}
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	372	</pre>
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	373	</div>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	374
				375	<p>Additionally, your must invoke the <tt>InitializeAliasAnalysis</tt> method
				376	from your analysis run method (<tt>run</tt> for a <tt>Pass</tt>,
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	377	<tt>runOnFunction</tt> for a <tt>FunctionPass</tt>, or <tt>InitializePass</tt>
				378	for an <tt>ImmutablePass</tt>). For example (as part of a <tt>Pass</tt>):</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	379
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	380	<div class="doc_code">
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	381	<pre>
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	382	bool run(Module &M) {
				383	InitializeAliasAnalysis(this);
				384	<i>// Perform analysis here...</i>
				385	return false;
				386	}
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	387	</pre>
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	388	</div>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	389
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	390	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	391
				392	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	393	<div class="doc_subsection">
				394	<a name="interfaces">Interfaces which may be specified</a>
				395	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	396
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	397	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	398
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	399	<p>All of the <a
				400	href="/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a>
				401	virtual methods default to providing <a href="#chaining">chaining</a> to another
				402	alias analysis implementation, which ends up returning conservatively correct
				403	information (returning "May" Alias and "Mod/Ref" for alias and mod/ref queries
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	404	respectively). Depending on the capabilities of the analysis you are
				405	implementing, you just override the interfaces you can improve.</p>
				406
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	407	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	408
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	409
				410
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	411	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	412	<div class="doc_subsection">
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	413	<a name="chaining"><tt>AliasAnalysis</tt> chaining behavior</a>
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	414	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	415
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	416	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	417
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	418	<p>With only two special exceptions (the <tt><a
				419	href="#basic-aa">basicaa</a></tt> and <a href="#no-aa"><tt>no-aa</tt></a>
				420	passes) every alias analysis pass chains to another alias analysis
				421	implementation (for example, the user can specify "<tt>-basicaa -ds-aa
				422	-anders-aa -licm</tt>" to get the maximum benefit from the three alias
				423	analyses). The alias analysis class automatically takes care of most of this
				424	for methods that you don't override. For methods that you do override, in code
				425	paths that return a conservative MayAlias or Mod/Ref result, simply return
				426	whatever the superclass computes. For example:</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	427
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	428	<div class="doc_code">
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	429	<pre>
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	430	AliasAnalysis::AliasResult alias(const Value *V1, unsigned V1Size,
				431	const Value *V2, unsigned V2Size) {
				432	if (...)
				433	return NoAlias;
				434	...
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	435
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	436	<i>// Couldn't determine a must or no-alias result.</i>
				437	return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
				438	}
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	439	</pre>
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	440	</div>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	441
				442	<p>In addition to analysis queries, you must make sure to unconditionally pass
				443	LLVM <a href="#updating">update notification</a> methods to the superclass as
				444	well if you override them, which allows all alias analyses in a change to be
				445	updated.</p>
				446
				447	</div>
				448
				449
				450	<!-- ======================================================================= -->
				451	<div class="doc_subsection">
				452	<a name="updating">Updating analysis results for transformations</a>
				453	</div>
				454
				455	<div class="doc_text">
				456	<p>
				457	Alias analysis information is initially computed for a static snapshot of the
				458	program, but clients will use this information to make transformations to the
				459	code. All but the most trivial forms of alias analysis will need to have their
				460	analysis results updated to reflect the changes made by these transformations.
				461	</p>
				462
				463	<p>
				464	The <tt>AliasAnalysis</tt> interface exposes two methods which are used to
				465	communicate program changes from the clients to the analysis implementations.
				466	Various alias analysis implementations should use these methods to ensure that
				467	their internal data structures are kept up-to-date as the program changes (for
				468	example, when an instruction is deleted), and clients of alias analysis must be
				469	sure to call these interfaces appropriately.
				470	</p>
				471	</div>
				472
				473	<!-- _______________________________________________________________________ -->
				474	<div class="doc_subsubsection">The <tt>deleteValue</tt> method</div>
				475
				476	<div class="doc_text">
				477	The <tt>deleteValue</tt> method is called by transformations when they remove an
				478	instruction or any other value from the program (including values that do not
				479	use pointers). Typically alias analyses keep data structures that have entries
				480	for each value in the program. When this method is called, they should remove
				481	any entries for the specified value, if they exist.
				482	</div>
				483
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	484	<!-- _______________________________________________________________________ -->
				485	<div class="doc_subsubsection">The <tt>copyValue</tt> method</div>
				486
				487	<div class="doc_text">
				488	The <tt>copyValue</tt> method is used when a new value is introduced into the
				489	program. There is no way to introduce a value into the program that did not
				490	exist before (this doesn't make sense for a safe compiler transformation), so
				491	this is the only way to introduce a new value. This method indicates that the
				492	new value has exactly the same properties as the value being copied.
				493	</div>
				494
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	495	<!-- _______________________________________________________________________ -->
				496	<div class="doc_subsubsection">The <tt>replaceWithNewValue</tt> method</div>
				497
				498	<div class="doc_text">
				499	This method is a simple helper method that is provided to make clients easier to
				500	use. It is implemented by copying the old analysis information to the new
				501	value, then deleting the old value. This method cannot be overridden by alias
				502	analysis implementations.
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	503	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	504
				505	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	506	<div class="doc_subsection">
				507	<a name="implefficiency">Efficiency Issues</a>
				508	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	509
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	510	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	511
				512	<p>From the LLVM perspective, the only thing you need to do to provide an
				513	efficient alias analysis is to make sure that alias analysis <b>queries</b> are
				514	serviced quickly. The actual calculation of the alias analysis results (the
				515	"run" method) is only performed once, but many (perhaps duplicate) queries may
				516	be performed. Because of this, try to move as much computation to the run
				517	method as possible (within reason).</p>
				518
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	519	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	520
				521	<!-- *********************************************************************** -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	522	<div class="doc_section">
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	523	<a name="using">Using alias analysis results</a>
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	524	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	525	<!-- *********************************************************************** -->
				526
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	527	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	528
				529	<p>There are several different ways to use alias analysis results. In order of
				530	preference, these are...</p>
				531
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	532	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	533
				534	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	535	<div class="doc_subsection">
				536	<a name="loadvn">Using the <tt>-load-vn</tt> Pass</a>
				537	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	538
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	539	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	540
				541	<p>The <tt>load-vn</tt> pass uses alias analysis to provide value numbering
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	542	information for <tt>load</tt> instructions and pointer values. If your analysis
				543	or transformation can be modeled in a form that uses value numbering
				544	information, you don't have to do anything special to handle load instructions:
				545	just use the <tt>load-vn</tt> pass, which uses alias analysis.</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	546
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	547	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	548
				549	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	550	<div class="doc_subsection">
				551	<a name="ast">Using the <tt>AliasSetTracker</tt> class</a>
				552	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	553
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	554	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	555
				556	<p>Many transformations need information about alias <b>sets</b> that are active
				557	in some scope, rather than information about pairwise aliasing. The <tt><a
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	558	href="/doxygen/classllvm_1_1AliasSetTracker.html">AliasSetTracker</a></tt> class
				559	is used to efficiently build these Alias Sets from the pairwise alias analysis
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	560	information provided by the <tt>AliasAnalysis</tt> interface.</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	561
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	562	<p>First you initialize the AliasSetTracker by using the "<tt>add</tt>" methods
				563	to add information about various potentially aliasing instructions in the scope
				564	you are interested in. Once all of the alias sets are completed, your pass
				565	should simply iterate through the constructed alias sets, using the
				566	<tt>AliasSetTracker</tt> <tt>begin()</tt>/<tt>end()</tt> methods.</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	567
				568	<p>The <tt>AliasSet</tt>s formed by the <tt>AliasSetTracker</tt> are guaranteed
Chris Lattner	b8b9163a	2003-12-19 08:43:07 +0000	[diff] [blame]	569	to be disjoint, calculate mod/ref information and volatility for the set, and
				570	keep track of whether or not all of the pointers in the set are Must aliases.
				571	The AliasSetTracker also makes sure that sets are properly folded due to call
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	572	instructions, and can provide a list of pointers in each set.</p>
				573
				574	<p>As an example user of this, the <a href="/doxygen/structLICM.html">Loop
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	575	Invariant Code Motion</a> pass uses <tt>AliasSetTracker</tt>s to calculate alias
				576	sets for each loop nest. If an <tt>AliasSet</tt> in a loop is not modified,
				577	then all load instructions from that set may be hoisted out of the loop. If any
				578	alias sets are stored to <b>and</b> are must alias sets, then the stores may be
				579	sunk to outside of the loop, promoting the memory location to a register for the
				580	duration of the loop nest. Both of these transformations only apply if the
				581	pointer argument is loop-invariant.</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	582
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	583	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	584
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	585	<!-- _______________________________________________________________________ -->
Chris Lattner	b8b9163a	2003-12-19 08:43:07 +0000	[diff] [blame]	586	<div class="doc_subsubsection">
				587	The AliasSetTracker implementation
				588	</div>
				589
				590	<div class="doc_text">
				591
				592	<p>The AliasSetTracker class is implemented to be as efficient as possible. It
				593	uses the union-find algorithm to efficiently merge AliasSets when a pointer is
				594	inserted into the AliasSetTracker that aliases multiple sets. The primary data
				595	structure is a hash table mapping pointers to the AliasSet they are in.</p>
				596
				597	<p>The AliasSetTracker class must maintain a list of all of the LLVM Value*'s
				598	that are in each AliasSet. Since the hash table already has entries for each
				599	LLVM Value* of interest, the AliasesSets thread the linked list through these
				600	hash-table nodes to avoid having to allocate memory unnecessarily, and to make
				601	merging alias sets extremely efficient (the linked list merge is constant time).
				602	</p>
				603
				604	<p>You shouldn't need to understand these details if you are just a client of
				605	the AliasSetTracker, but if you look at the code, hopefully this brief
				606	description will help make sense of why things are designed the way they
				607	are.</p>
				608
				609	</div>
				610
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	611	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	612	<div class="doc_subsection">
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	613	<a name="direct">Using the <tt>AliasAnalysis</tt> interface directly</a>
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	614	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	615
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	616	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	617
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	618	<p>If neither of these utility class are what your pass needs, you should use
				619	the interfaces exposed by the <tt>AliasAnalysis</tt> class directly. Try to use
				620	the higher-level methods when possible (e.g., use mod/ref information instead of
				621	the <a href="#alias"><tt>alias</tt></a> method directly if possible) to get the
				622	best precision and efficiency.</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	623
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	624	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	625
				626	<!-- *********************************************************************** -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	627	<div class="doc_section">
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	628	<a name="exist">Existing alias analysis implementations and clients</a>
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	629	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	630	<!-- *********************************************************************** -->
				631
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	632	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	633
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	634	<p>If you're going to be working with the LLVM alias analysis infrastructure,
				635	you should know what clients and implementations of alias analysis are
				636	available. In particular, if you are implementing an alias analysis, you should
				637	be aware of the <a href="#aliasanalysis-debug">the clients</a> that are useful
				638	for monitoring and evaluating different implementations.</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	639
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	640	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	641
				642	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	643	<div class="doc_subsection">
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	644	<a name="impls">Available <tt>AliasAnalysis</tt> implementations</a>
				645	</div>
				646
				647	<div class="doc_text">
				648
				649	<p>This section lists the various implementations of the <tt>AliasAnalysis</tt>
				650	interface. With the exception of the <a href="#no-aa"><tt>-no-aa</tt></a> and
				651	<a href="#basic-aa"><tt>-basicaa</tt></a> implementations, all of these <a
Chris Lattner	53e5e2a	2004-06-21 22:52:48 +0000	[diff] [blame]	652	href="#chaining">chain</a> to other alias analysis implementations.</p>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	653
				654	</div>
				655
				656	<!-- _______________________________________________________________________ -->
				657	<div class="doc_subsubsection">
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	658	<a name="no-aa">The <tt>-no-aa</tt> pass</a>
				659	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	660
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	661	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	662
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	663	<p>The <tt>-no-aa</tt> pass is just like what it sounds: an alias analysis that
				664	never returns any useful information. This pass can be useful if you think that
				665	alias analysis is doing something wrong and are trying to narrow down a
				666	problem.</p>
				667
				668	</div>
				669
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	670	<!-- _______________________________________________________________________ -->
				671	<div class="doc_subsubsection">
				672	<a name="basic-aa">The <tt>-basicaa</tt> pass</a>
				673	</div>
				674
				675	<div class="doc_text">
				676
				677	<p>The <tt>-basicaa</tt> pass is the default LLVM alias analysis. It is an
				678	aggressive local analysis that "knows" many important facts:</p>
				679
				680	<ul>
				681	<li>Distinct globals, stack allocations, and heap allocations can never
				682	alias.</li>
				683	<li>Globals, stack allocations, and heap allocations never alias the null
				684	pointer.</li>
				685	<li>Different fields of a structure do not alias.</li>
				686	<li>Indexes into arrays with statically differing subscripts cannot alias.</li>
				687	<li>Many common standard C library functions <a
				688	href="#simplemodref">never access memory or only read memory</a>.</li>
				689	<li>Pointers that obviously point to constant globals
				690	"<tt>pointToConstantMemory</tt>".</li>
				691	<li>Function calls can not modify or references stack allocations if they never
				692	escape from the function that allocates them (a common case for automatic
				693	arrays).</li>
				694	</ul>
				695
				696	</div>
				697
Chris Lattner	9475b96	2004-06-28 19:19:47 +0000	[diff] [blame]	698	<!-- _______________________________________________________________________ -->
				699	<div class="doc_subsubsection">
				700	<a name="globalsmodref">The <tt>-globalsmodref-aa</tt> pass</a>
				701	</div>
				702
				703	<div class="doc_text">
				704
				705	<p>This pass implements a simple context-sensitive mod/ref and alias analysis
Chris Lattner	d138437	2004-07-27 07:50:07 +0000	[diff] [blame]	706	for internal global variables that don't "have their address taken". If a
				707	global does not have its address taken, the pass knows that no pointers alias
				708	the global. This pass also keeps track of functions that it knows never access
				709	memory or never read memory. This allows certain optimizations (e.g. GCSE) to
				710	eliminate call instructions entirely.
Chris Lattner	9475b96	2004-06-28 19:19:47 +0000	[diff] [blame]	711	</p>
				712
				713	<p>The real power of this pass is that it provides context-sensitive mod/ref
				714	information for call instructions. This allows the optimizer to know that
				715	calls to a function do not clobber or read the value of the global, allowing
				716	loads and stores to be eliminated.</p>
				717
				718	<p>Note that this pass is somewhat limited in its scope (only support
				719	non-address taken globals), but is very quick analysis.</p>
				720	</div>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	721
				722	<!-- _______________________________________________________________________ -->
				723	<div class="doc_subsubsection">
				724	<a name="anders-aa">The <tt>-anders-aa</tt> pass</a>
				725	</div>
				726
				727	<div class="doc_text">
				728
				729	<p>The <tt>-anders-aa</tt> pass implements the well-known "Andersen's algorithm"
				730	for interprocedural alias analysis. This algorithm is a subset-based,
				731	flow-insensitive, context-insensitive, and field-insensitive alias analysis that
				732	is widely believed to be fairly precise. Unfortunately, this algorithm is also
				733	O(N<sup>3</sup>). The LLVM implementation currently does not implement any of
				734	the refinements (such as "online cycle elimination" or "offline variable
				735	substitution") to improve its efficiency, so it can be quite slow in common
				736	cases.
				737	</p>
				738
				739	</div>
				740
				741	<!-- _______________________________________________________________________ -->
				742	<div class="doc_subsubsection">
				743	<a name="steens-aa">The <tt>-steens-aa</tt> pass</a>
				744	</div>
				745
				746	<div class="doc_text">
				747
				748	<p>The <tt>-steens-aa</tt> pass implements a variation on the well-known
				749	"Steensgaard's algorithm" for interprocedural alias analysis. Steensgaard's
				750	algorithm is a unification-based, flow-insensitive, context-insensitive, and
				751	field-insensitive alias analysis that is also very scalable (effectively linear
				752	time).</p>
				753
				754	<p>The LLVM <tt>-steens-aa</tt> pass implements a "speculatively
				755	field-<b>sensitive</b>" version of Steensgaard's algorithm using the Data
				756	Structure Analysis framework. This gives it substantially more precision than
				757	the standard algorithm while maintaining excellent analysis scalability.</p>
				758
Chris Lattner	4b32528	2007-07-03 04:41:50 +0000	[diff] [blame]	759	<p>Note that <tt>-steens-aa</tt> is available in the optional "poolalloc"
				760	module, it is not part of the LLVM core.</p>
				761
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	762	</div>
				763
				764	<!-- _______________________________________________________________________ -->
				765	<div class="doc_subsubsection">
				766	<a name="ds-aa">The <tt>-ds-aa</tt> pass</a>
				767	</div>
				768
				769	<div class="doc_text">
				770
				771	<p>The <tt>-ds-aa</tt> pass implements the full Data Structure Analysis
				772	algorithm. Data Structure Analysis is a modular unification-based,
				773	flow-insensitive, context-<b>sensitive</b>, and speculatively
				774	field-<b>sensitive</b> alias analysis that is also quite scalable, usually at
				775	O(n*log(n)).</p>
				776
				777	<p>This algorithm is capable of responding to a full variety of alias analysis
				778	queries, and can provide context-sensitive mod/ref information as well. The
				779	only major facility not implemented so far is support for must-alias
				780	information.</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	781
Chris Lattner	4b32528	2007-07-03 04:41:50 +0000	[diff] [blame]	782	<p>Note that <tt>-ds-aa</tt> is available in the optional "poolalloc"
				783	module, it is not part of the LLVM core.</p>
				784
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	785	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	786
				787
				788	<!-- ======================================================================= -->
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	789	<div class="doc_subsection">
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	790	<a name="aliasanalysis-xforms">Alias analysis driven transformations</a>
				791	</div>
				792
				793	<div class="doc_text">
				794	LLVM includes several alias-analysis driven transformations which can be used
				795	with any of the implementations above.
				796	</div>
				797
				798	<!-- _______________________________________________________________________ -->
				799	<div class="doc_subsubsection">
				800	<a name="adce">The <tt>-adce</tt> pass</a>
				801	</div>
				802
				803	<div class="doc_text">
				804
				805	<p>The <tt>-adce</tt> pass, which implements Aggressive Dead Code Elimination
				806	uses the <tt>AliasAnalysis</tt> interface to delete calls to functions that do
				807	not have side-effects and are not used.</p>
				808
				809	</div>
				810
				811
				812	<!-- _______________________________________________________________________ -->
				813	<div class="doc_subsubsection">
				814	<a name="licm">The <tt>-licm</tt> pass</a>
				815	</div>
				816
				817	<div class="doc_text">
				818
				819	<p>The <tt>-licm</tt> pass implements various Loop Invariant Code Motion related
				820	transformations. It uses the <tt>AliasAnalysis</tt> interface for several
				821	different transformations:</p>
				822
				823	<ul>
				824	<li>It uses mod/ref information to hoist or sink load instructions out of loops
				825	if there are no instructions in the loop that modifies the memory loaded.</li>
				826
				827	<li>It uses mod/ref information to hoist function calls out of loops that do not
				828	write to memory and are loop-invariant.</li>
				829
				830	<li>If uses alias information to promote memory objects that are loaded and
				831	stored to in loops to live in a register instead. It can do this if there are
				832	no may aliases to the loaded/stored memory location.</li>
				833	</ul>
				834
				835	</div>
				836
				837	<!-- _______________________________________________________________________ -->
				838	<div class="doc_subsubsection">
				839	<a name="argpromotion">The <tt>-argpromotion</tt> pass</a>
				840	</div>
				841
				842	<div class="doc_text">
				843	<p>
				844	The <tt>-argpromotion</tt> pass promotes by-reference arguments to be passed in
				845	by-value instead. In particular, if pointer arguments are only loaded from it
				846	passes in the value loaded instead of the address to the function. This pass
				847	uses alias information to make sure that the value loaded from the argument
				848	pointer is not modified between the entry of the function and any load of the
				849	pointer.</p>
				850	</div>
				851
				852	<!-- _______________________________________________________________________ -->
				853	<div class="doc_subsubsection">
				854	<a name="gcseloadvn">The <tt>-load-vn</tt> & <tt>-gcse</tt> passes</a>
				855	</div>
				856
				857	<div class="doc_text">
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	858
				859	<p>The <tt>-load-vn</tt> pass uses alias analysis to "<a href="#loadvn">value
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	860	number</a>" loads and pointers values, which is used by the GCSE pass to
				861	eliminate instructions. The <tt>-load-vn</tt> pass relies on alias information
				862	and must-alias information. This combination of passes can make the following
				863	transformations:</p>
				864
				865	<ul>
				866	<li>Redundant load instructions are eliminated.</li>
				867	<li>Load instructions that follow a store to the same location are replaced with
				868	the stored value ("store forwarding").</li>
				869	<li>Pointers values (e.g. formal arguments) that must-alias simpler expressions
				870	(e.g. global variables or the null pointer) are replaced. Note that this
				871	implements transformations like "virtual method resolution", turning indirect
				872	calls into direct calls.</li>
				873	</ul>
				874
				875	</div>
				876
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	877	<!-- ======================================================================= -->
				878	<div class="doc_subsection">
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	879	<a name="aliasanalysis-debug">Clients for debugging and evaluation of
				880	implementations</a>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	881	</div>
				882
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	883	<div class="doc_text">
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	884
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	885	<p>These passes are useful for evaluating the various alias analysis
				886	implementations. You can use them with commands like '<tt>opt -anders-aa -ds-aa
				887	-aa-eval foo.bc -disable-output -stats</tt>'.</p>
				888
				889	</div>
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	890
				891	<!-- _______________________________________________________________________ -->
				892	<div class="doc_subsubsection">
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	893	<a name="print-alias-sets">The <tt>-print-alias-sets</tt> pass</a>
				894	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	895
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	896	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	897
				898	<p>The <tt>-print-alias-sets</tt> pass is exposed as part of the
Chris Lattner	2e6f448	2006-01-03 06:04:48 +0000	[diff] [blame]	899	<tt>opt</tt> tool to print out the Alias Sets formed by the <a
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	900	href="#ast"><tt>AliasSetTracker</tt></a> class. This is useful if you're using
Chris Lattner	2e6f448	2006-01-03 06:04:48 +0000	[diff] [blame]	901	the <tt>AliasSetTracker</tt> class. To use it, use something like:</p>
				902
				903	<div class="doc_code">
				904	<pre>
				905	% opt -ds-aa -print-alias-sets -disable-output
				906	</pre>
				907	</div>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	908
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	909	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	910
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	911
				912	<!-- _______________________________________________________________________ -->
				913	<div class="doc_subsubsection">
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	914	<a name="count-aa">The <tt>-count-aa</tt> pass</a>
				915	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	916
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	917	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	918
				919	<p>The <tt>-count-aa</tt> pass is useful to see how many queries a particular
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	920	pass is making and what responses are returned by the alias analysis. As an
				921	example,</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	922
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	923	<div class="doc_code">
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	924	<pre>
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	925	% opt -basicaa -count-aa -ds-aa -count-aa -licm
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	926	</pre>
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	927	</div>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	928
Misha Brukman	2361fcf	2004-07-28 22:18:33 +0000	[diff] [blame]	929	<p>will print out how many queries (and what responses are returned) by the
				930	<tt>-licm</tt> pass (of the <tt>-ds-aa</tt> pass) and how many queries are made
				931	of the <tt>-basicaa</tt> pass by the <tt>-ds-aa</tt> pass. This can be useful
				932	when debugging a transformation or an alias analysis implementation.</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	933
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	934	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	935
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	936	<!-- _______________________________________________________________________ -->
				937	<div class="doc_subsubsection">
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	938	<a name="aa-eval">The <tt>-aa-eval</tt> pass</a>
				939	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	940
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	941	<div class="doc_text">
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	942
				943	<p>The <tt>-aa-eval</tt> pass simply iterates through all pairs of pointers in a
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	944	function and asks an alias analysis whether or not the pointers alias. This
				945	gives an indication of the precision of the alias analysis. Statistics are
Chris Lattner	2a19d83	2004-05-23 21:04:01 +0000	[diff] [blame]	946	printed indicating the percent of no/may/must aliases found (a more precise
				947	algorithm will have a lower number of may aliases).</p>
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	948
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	949	</div>
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	950
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	951	<!-- *********************************************************************** -->
Owen Anderson	d263cfa	2007-10-02 00:43:25 +0000	[diff] [blame^]	952	<div class="doc_section">
				953	<a name="memdep">Memory Dependence Analysis</a>
				954	</div>
				955	<!-- *********************************************************************** -->
				956
				957	<div class="doc_text">
				958
				959	<p>If you're just looking to be a client of alias analysis information, consider
				960	using the Memory Dependence Analysis interface instead. MemDep is a lazy,
				961	caching layer on top of alias analysis that is able to answer the question of
				962	what preceding memory operations a given instruction depends on, either at an
				963	intra- or inter-block level. Because of its laziness and caching
				964	policy, using MemDep can be a significant performance win over accessing alias
				965	analysis directly.</p>
				966
				967	</div>
				968
				969	<!-- *********************************************************************** -->
Chris Lattner	b512e9f	2003-03-04 19:37:49 +0000	[diff] [blame]	970
Misha Brukman	084a3a07	2003-10-24 18:06:11 +0000	[diff] [blame]	971	<hr>
Misha Brukman	e8e932a	2003-11-22 01:26:21 +0000	[diff] [blame]	972	<address>
Misha Brukman	8834af9	2003-12-21 22:53:21 +0000	[diff] [blame]	973	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
Misha Brukman	58ec434	2003-11-22 01:07:30 +0000	[diff] [blame]	974	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
Misha Brukman	e8e932a	2003-11-22 01:26:21 +0000	[diff] [blame]	975	<a href="http://validator.w3.org/check/referer"><img
Misha Brukman	55ba220	2004-05-12 18:02:00 +0000	[diff] [blame]	976	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
Misha Brukman	e8e932a	2003-11-22 01:26:21 +0000	[diff] [blame]	977
				978	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
Reid Spencer	ca05854	2006-03-14 05:39:39 +0000	[diff] [blame]	979	<a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
Misha Brukman	e8e932a	2003-11-22 01:26:21 +0000	[diff] [blame]	980	Last modified: $Date$
				981	</address>
Misha Brukman	283ff69	2003-10-22 23:27:16 +0000	[diff] [blame]	982
				983	</body>
				984	</html>