<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>
</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>
<!-- *********************************************************************** -->
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