<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>
<!-- ======================================================================= -->
<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
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">
projects / oota-llvm.git / blobdiff