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

blob: 306a3f4393c5722fd044f76fe0cdbcd6f4c9c426 [file] [log] [blame]

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