"http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
- <title>The LLVM Alias Analysis Infrastructure</title>
+ <title>LLVM Alias Analysis Infrastructure</title>
<link rel="stylesheet" href="llvm.css" type="text/css">
</head>
<body>
<div class="doc_title">
- The LLVM Alias Analysis Infrastructure
+ LLVM Alias Analysis Infrastructure
</div>
<ol>
<ul>
<li><a href="#impls">Available <tt>AliasAnalysis</tt> implementations</a></li>
<li><a href="#aliasanalysis-xforms">Alias analysis driven transformations</a></li>
- <li><a href="#aliasanalysis-debug">Clients for debugging and evaluation of implementations</a></li>
+ <li><a href="#aliasanalysis-debug">Clients for debugging and evaluation of
+ implementations</a></li>
</ul>
</li>
</ol>
different ways of classifying them: flow-sensitive vs flow-insensitive,
context-sensitive vs context-insensitive, field-sensitive vs field-insensitive,
unification-based vs subset-based, etc. Traditionally, alias analyses respond
-to a query with a <a href="#MustNoMay">Must, May, or No</a> alias response,
+to a query with a <a href="#MustMayNo">Must, May, or No</a> alias response,
indicating that two pointers always point to the same object, might point to the
same object, or are known to never point to the same object.</p>
<p>The LLVM <a
-href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a>
+href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a>
class is the primary interface used by clients and implementations of alias
analyses in the LLVM system. This class is the common interface between clients
of alias analysis information and the implementations providing it, and is
<div class="doc_text">
<p>The <a
-href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a>
+href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a>
class defines the interface that the various alias analysis implementations
should support. This class exports two important enums: <tt>AliasResult</tt>
and <tt>ModRefResult</tt> which represent the result of an alias query or a
important for correct Alias Analyses. For example, consider this (silly, but
possible) C code:</p>
+<div class="doc_code">
<pre>
- int i;
- char C[2];
- char A[10];
- /* ... */
- for (i = 0; i != 10; ++i) {
- C[0] = A[i]; /* One byte store */
- C[1] = A[9-i]; /* One byte store */
- }
+int i;
+char C[2];
+char A[10];
+/* ... */
+for (i = 0; i != 10; ++i) {
+ C[0] = A[i]; /* One byte store */
+ C[1] = A[9-i]; /* One byte store */
+}
</pre>
+</div>
<p>In this case, the <tt>basicaa</tt> pass will disambiguate the stores to
<tt>C[0]</tt> and <tt>C[1]</tt> because they are accesses to two distinct
LICM pass can use store motion to remove the stores from the loop. In
constrast, the following code:</p>
+<div class="doc_code">
<pre>
- int i;
- char C[2];
- char A[10];
- /* ... */
- for (i = 0; i != 10; ++i) {
- ((short*)C)[0] = A[i]; /* Two byte store! */
- C[1] = A[9-i]; /* One byte store */
- }
+int i;
+char C[2];
+char A[10];
+/* ... */
+for (i = 0; i != 10; ++i) {
+ ((short*)C)[0] = A[i]; /* Two byte store! */
+ C[1] = A[9-i]; /* One byte store */
+}
</pre>
+</div>
<p>In this case, the two stores to C do alias each other, because the access to
the <tt>&C[0]</tt> element is a two byte access. If size information wasn't
</div>
-
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
<a name="simplemodref">The <tt>doesNotAccessMemory</tt> and
</div>
-
-
<!-- *********************************************************************** -->
<div class="doc_section">
<a name="writingnew">Writing a new <tt>AliasAnalysis</tt> Implementation</a>
declaring any pass dependencies your pass has. Thus you should have something
like this:</p>
+<div class="doc_code">
<pre>
- void getAnalysisUsage(AnalysisUsage &AU) const {
- AliasAnalysis::getAnalysisUsage(AU);
- <i>// declare your dependencies here.</i>
- }
+void getAnalysisUsage(AnalysisUsage &AU) const {
+ AliasAnalysis::getAnalysisUsage(AU);
+ <i>// declare your dependencies here.</i>
+}
</pre>
+</div>
<p>Additionally, your must invoke the <tt>InitializeAliasAnalysis</tt> method
from your analysis run method (<tt>run</tt> for a <tt>Pass</tt>,
<tt>runOnFunction</tt> for a <tt>FunctionPass</tt>, or <tt>InitializePass</tt>
for an <tt>ImmutablePass</tt>). For example (as part of a <tt>Pass</tt>):</p>
+<div class="doc_code">
<pre>
- bool run(Module &M) {
- InitializeAliasAnalysis(this);
- <i>// Perform analysis here...</i>
- return false;
- }
+bool run(Module &M) {
+ InitializeAliasAnalysis(this);
+ <i>// Perform analysis here...</i>
+ return false;
+}
</pre>
+</div>
</div>
paths that return a conservative MayAlias or Mod/Ref result, simply return
whatever the superclass computes. For example:</p>
+<div class="doc_code">
<pre>
- AliasAnalysis::AliasResult alias(const Value *V1, unsigned V1Size,
- const Value *V2, unsigned V2Size) {
- if (...)
- return NoAlias;
- ...
-
- <i>// Couldn't determine a must or no-alias result.</i>
- return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
- }
+AliasAnalysis::AliasResult alias(const Value *V1, unsigned V1Size,
+ const Value *V2, unsigned V2Size) {
+ if (...)
+ return NoAlias;
+ ...
+
+ <i>// Couldn't determine a must or no-alias result.</i>
+ return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
+}
</pre>
+</div>
<p>In addition to analysis queries, you must make sure to unconditionally pass
LLVM <a href="#updating">update notification</a> methods to the superclass as
any entries for the specified value, if they exist.
</div>
-
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">The <tt>copyValue</tt> method</div>
new value has exactly the same properties as the value being copied.
</div>
-
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">The <tt>replaceWithNewValue</tt> method</div>
<p>Many transformations need information about alias <b>sets</b> that are active
in some scope, rather than information about pairwise aliasing. The <tt><a
-href="/doxygen/classllvm_1_1AliasSetTracker.html">AliasSetTracker</a></tt> class is used
-to efficiently build these Alias Sets from the pairwise alias analysis
+href="/doxygen/classllvm_1_1AliasSetTracker.html">AliasSetTracker</a></tt> class
+is used to efficiently build these Alias Sets from the pairwise alias analysis
information provided by the <tt>AliasAnalysis</tt> interface.</p>
<p>First you initialize the AliasSetTracker by using the "<tt>add</tt>" methods
</div>
-
<!-- ======================================================================= -->
<div class="doc_subsection">
<a name="direct">Using the <tt>AliasAnalysis</tt> interface directly</a>
<p>This section lists the various implementations of the <tt>AliasAnalysis</tt>
interface. With the exception of the <a href="#no-aa"><tt>-no-aa</tt></a> and
<a href="#basic-aa"><tt>-basicaa</tt></a> implementations, all of these <a
-href="chaining">chain</a> to other alias analysis implementations.</p>
+href="#chaining">chain</a> to other alias analysis implementations.</p>
</div>
</div>
-
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
<a name="basic-aa">The <tt>-basicaa</tt> pass</a>
</div>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="globalsmodref">The <tt>-globalsmodref-aa</tt> pass</a>
+</div>
+
+<div class="doc_text">
+
+<p>This pass implements a simple context-sensitive mod/ref and alias analysis
+for internal global variables that don't "have their address taken". If a
+global does not have its address taken, the pass knows that no pointers alias
+the global. This pass also keeps track of functions that it knows never access
+memory or never read memory. This allows certain optimizations (e.g. GCSE) to
+eliminate call instructions entirely.
+</p>
+
+<p>The real power of this pass is that it provides context-sensitive mod/ref
+information for call instructions. This allows the optimizer to know that
+calls to a function do not clobber or read the value of the global, allowing
+loads and stores to be eliminated.</p>
+
+<p>Note that this pass is somewhat limited in its scope (only support
+non-address taken globals), but is very quick analysis.</p>
+</div>
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
Structure Analysis framework. This gives it substantially more precision than
the standard algorithm while maintaining excellent analysis scalability.</p>
+<p>Note that <tt>-steens-aa</tt> is available in the optional "poolalloc"
+module, it is not part of the LLVM core.</p>
+
</div>
<!-- _______________________________________________________________________ -->
only major facility not implemented so far is support for must-alias
information.</p>
+<p>Note that <tt>-ds-aa</tt> is available in the optional "poolalloc"
+module, it is not part of the LLVM core.</p>
+
</div>
</div>
<div class="doc_text">
-<p>
-The <tt>-load-vn</tt> pass uses alias analysis to "<a href="#loadvn">value
+
+
<p>The <tt>-load-vn</tt> pass uses alias analysis to "<a href="#loadvn">value
number</a>" loads and pointers values, which is used by the GCSE pass to
eliminate instructions. The <tt>-load-vn</tt> pass relies on alias information
and must-alias information. This combination of passes can make the following
</div>
-
-
-
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="aliasanalysis-debug">Clients for debugging and evaluation of implementations</a>
+ <a name="aliasanalysis-debug">Clients for debugging and evaluation of
+ implementations</a>
</div>
-These passes are useful for evaluating the various alias analysis
+<div class="doc_text">
+
+<p>These passes are useful for evaluating the various alias analysis
implementations. You can use them with commands like '<tt>opt -anders-aa -ds-aa
--aa-eval foo.bc -disable-output -stats</tt>'.
+-aa-eval foo.bc -disable-output -stats</tt>'.</p>
+</div>
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
<div class="doc_text">
<p>The <tt>-print-alias-sets</tt> pass is exposed as part of the
-<tt>
analyze</tt> tool to print out the Alias Sets formed by the <a
+<tt>
opt</tt> tool to print out the Alias Sets formed by the <a
href="#ast"><tt>AliasSetTracker</tt></a> class. This is useful if you're using
-the <tt>AliasSetTracker</tt> class.</p>
+the <tt>AliasSetTracker</tt> class. To use it, use something like:</p>
+
+<div class="doc_code">
+<pre>
+% opt -ds-aa -print-alias-sets -disable-output
+</pre>
+</div>
</div>
<div class="doc_text">
<p>The <tt>-count-aa</tt> pass is useful to see how many queries a particular
-pass is making and what responses are returned by the alias analysis. An
-example usage is:</p>
+pass is making and what responses are returned by the alias analysis. As an
+example,</p>
+<div class="doc_code">
<pre>
- $ opt -basicaa -count-aa -ds-aa -count-aa -licm
+% opt -basicaa -count-aa -ds-aa -count-aa -licm
</pre>
+</div>
-<p>Which will print out how many queries (and what responses are returned) by
-the <tt>-licm</tt> pass (of the <tt>-ds-aa</tt> pass) and how many queries are
-made of the <tt>-basicaa</tt> pass by the <tt>-ds-aa</tt> pass. This can be
-useful when debugging a transformation or an alias analysis implementation.</p>
+<p>will print out how many queries (and what responses are returned) by the
+<tt>-licm</tt> pass (of the <tt>-ds-aa</tt> pass) and how many queries are made
+of the <tt>-basicaa</tt> pass by the <tt>-ds-aa</tt> pass. This can be useful
+when debugging a transformation or an alias analysis implementation.</p>
</div>
src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
- <a href="http://llvm.cs.uiuc.edu">LLVM Compiler Infrastructure</a><br>
+ <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
Last modified: $Date$
</address>
projects / oota-llvm.git / blobdiff