<li><a href="#chaining"><tt>AliasAnalysis</tt> chaining behavior</a></li>
<li><a href="#updating">Updating analysis results for transformations</a></li>
<li><a href="#implefficiency">Efficiency Issues</a></li>
- <li><a href="#passmanager">Pass Manager Issues</a></li>
+ <li><a href="#limitations">Limitations</a></li>
</ul>
</li>
call. The <tt>AliasAnalysis</tt> interface also exposes some helper methods
which allow you to get mod/ref information for arbitrary instructions.</p>
+<p>All <tt>AliasAnalysis</tt> interfaces require that in queries involving
+multiple values, values which are not
+<a href="LangRef.html#constants">constants</a> are all defined within the
+same function.</p>
+
</div>
<!-- ======================================================================= -->
</div>
<div class="doc_text">
-The <tt>alias</tt> method is the primary interface used to determine whether or
-not two memory objects alias each other. It takes two memory objects as input
-and returns MustAlias, MayAlias, or NoAlias as appropriate.
+<p>The <tt>alias</tt> method is the primary interface used to determine whether
+or not two memory objects alias each other. It takes two memory objects as
+input and returns MustAlias, PartialAlias, MayAlias, or NoAlias as
+appropriate.</p>
+
+<p>Like all <tt>AliasAnalysis</tt> interfaces, the <tt>alias</tt> method requires
+that either the two pointer values be defined within the same function, or at
+least one of the values is a <a href="LangRef.html#constants">constant</a>.</p>
</div>
<!-- _______________________________________________________________________ -->
</div>
<div class="doc_text">
-<p>The NoAlias response is used when the two pointers refer to distinct objects,
-regardless of whether the pointers compare equal. For example, freed pointers
-don't alias any pointers that were allocated afterwards. As a degenerate case,
-pointers returned by malloc(0) have no bytes for an object, and are considered
-NoAlias even when malloc returns the same pointer. The same rule applies to
-NULL pointers.</p>
+<p>The NoAlias response may be used when there is never an immediate dependence
+between any memory reference <i>based</i> on one pointer and any memory
+reference <i>based</i> the other. The most obvious example is when the two
+pointers point to non-overlapping memory ranges. Another is when the two
+pointers are only ever used for reading memory. Another is when the memory is
+freed and reallocated between accesses through one pointer and accesses through
+the other -- in this case, there is a dependence, but it's mediated by the free
+and reallocation.</p>
+
+<p>As an exception to this is with the
+<a href="LangRef.html#noalias"><tt>noalias</tt></a> keyword; the "irrelevant"
+dependencies are ignored.</p>
<p>The MayAlias response is used whenever the two pointers might refer to the
-same object. If the two memory objects overlap, but do not start at the same
-location, return MayAlias.</p>
+same object.</p>
+
+<p>The PartialAlias response is used when the two memory objects are known
+to be overlapping in some way, but do not start at the same address.</p>
<p>The MustAlias response may only be returned if the two memory objects are
guaranteed to always start at exactly the same location. A MustAlias response
<p>The <tt>AliasAnalysis</tt> class also provides a <tt>getModRefInfo</tt>
method for testing dependencies between function calls. This method takes two
-call sites (CS1 & CS2), returns NoModRef if the two calls refer to disjoint
-memory locations, Ref if CS1 reads memory written by CS2, Mod if CS1 writes to
-memory read or written by CS2, or ModRef if CS1 might read or write memory
-accessed by CS2. Note that this relation is not commutative.</p>
+call sites (CS1 & CS2), returns NoModRef if neither call writes to memory
+read or written by the other, Ref if CS1 reads memory written by CS2, Mod if CS1
+writes to memory read or written by CS2, or ModRef if CS1 might read or write
+memory written to by CS2. Note that this relation is not commutative.</p>
</div>
</p>
<p>
-The <tt>AliasAnalysis</tt> interface exposes two methods which are used to
+The <tt>AliasAnalysis</tt> interface exposes four methods which are used to
communicate program changes from the clients to the analysis implementations.
Various alias analysis implementations should use these methods to ensure that
their internal data structures are kept up-to-date as the program changes (for
analysis implementations.
</div>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">The <tt>addEscapingUse</tt> method</div>
+
+<div class="doc_text">
+<p>The <tt>addEscapingUse</tt> method is used when the uses of a pointer
+value have changed in ways that may invalidate precomputed analysis information.
+Implementations may either use this callback to provide conservative responses
+for points whose uses have change since analysis time, or may recompute some
+or all of their internal state to continue providing accurate responses.</p>
+
+<p>In general, any new use of a pointer value is considered an escaping use,
+and must be reported through this callback, <em>except</em> for the
+uses below:</p>
+
+<ul>
+ <li>A <tt>bitcast</tt> or <tt>getelementptr</tt> of the pointer</li>
+ <li>A <tt>store</tt> through the pointer (but not a <tt>store</tt>
+ <em>of</em> the pointer)</li>
+ <li>A <tt>load</tt> through the pointer</li>
+</ul>
+</div>
+
<!-- ======================================================================= -->
<div class="doc_subsection">
<a name="implefficiency">Efficiency Issues</a>
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="passmanager">Pass Manager Issues</a>
+ <a name="limitations">Limitations</a>
</div>
<div class="doc_text">
-<p>PassManager support for alternative AliasAnalysis implementation
-has some issues.</p>
+<p>The AliasAnalysis infrastructure has several limitations which make
+writing a new <tt>AliasAnalysis</tt> implementation difficult.</p>
<p>There is no way to override the default alias analysis. It would
be very useful to be able to do something like "opt -my-aa -O2" and
however there's no way for a pass to declare in its
<tt>getAnalysisUsage</tt> that it does so. Some passes attempt to use
<tt>AU.addPreserved<AliasAnalysis></tt>, however this doesn't
-actually have any effect.</tt>
+actually have any effect.</p>
<p><tt>AliasAnalysisCounter</tt> (<tt>-count-aa</tt>) and <tt>AliasDebugger</tt>
(<tt>-debug-aa</tt>) are implemented as <tt>ModulePass</tt> classes, so if your
passes between each pass, which prevents the use of <tt>FunctionPass</tt>
alias analysis passes.</p>
+<p>The <tt>AliasAnalysis</tt> API does have functions for notifying
+implementations when values are deleted or copied, however these
+aren't sufficient. There are many other ways that LLVM IR can be
+modified which could be relevant to <tt>AliasAnalysis</tt>
+implementations which can not be expressed.</p>
+
+<p>The <tt>AliasAnalysisDebugger</tt> utility seems to suggest that
+<tt>AliasAnalysis</tt> implementations can expect that they will be
+informed of any relevant <tt>Value</tt> before it appears in an
+alias query. However, popular clients such as <tt>GVN</tt> don't
+support this, and are known to trigger errors when run with the
+<tt>AliasAnalysisDebugger</tt>.</p>
+
+<p>Due to several of the above limitations, the most obvious use for
+the <tt>AliasAnalysisCounter</tt> utility, collecting stats on all
+alias queries in a compilation, doesn't work, even if the
+<tt>AliasAnalysis</tt> implementations don't use <tt>FunctionPass</tt>.
+There's no way to set a default, much less a default sequence,
+and there's no way to preserve it.</p>
+
+<p>The <tt>AliasSetTracker</tt> class (which is used by <tt>LICM</tt>
+makes a non-deterministic number of alias queries. This can cause stats
+collected by <tt>AliasAnalysisCounter</tt> to have fluctuations among
+identical runs, for example. Another consequence is that debugging
+techniques involving pausing execution after a predetermined number
+of queries can be unreliable.</p>
+
+<p>Many alias queries can be reformulated in terms of other alias
+queries. When multiple <tt>AliasAnalysis</tt> queries are chained together,
+it would make sense to start those queries from the beginning of the chain,
+with care taken to avoid infinite looping, however currently an
+implementation which wants to do this can only start such queries
+from itself.</p>
+
</div>
<!-- *********************************************************************** -->
<div class="doc_text">
-<p>The <tt>-basicaa</tt> pass is the default LLVM alias analysis. It is an
-aggressive local analysis that "knows" many important facts:</p>
+<p>The <tt>-basicaa</tt> pass is an aggressive local analysis that "knows"
+many important facts:</p>
<ul>
<li>Distinct globals, stack allocations, and heap allocations can never
</div>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="scev-aa">The <tt>-scev-aa</tt> pass</a>
+</div>
+
+<div class="doc_text">
+
+<p>The <tt>-scev-aa</tt> pass implements AliasAnalysis queries by
+translating them into ScalarEvolution queries. This gives it a
+more complete understanding of <tt>getelementptr</tt> instructions
+and loop induction variables than other alias analyses have.</p>
+
+</div>
<!-- ======================================================================= -->
<div class="doc_subsection">
src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
- <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
+ <a href="http://llvm.org/">LLVM Compiler Infrastructure</a><br>
Last modified: $Date$
</address>
projects / oota-llvm.git / blobdiff