"http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
- <link rel="stylesheet" href="llvm.css" type="text/css">
<title>Alias Analysis Infrastructure in LLVM</title>
+ <link rel="stylesheet" href="llvm.css" type="text/css">
</head>
<body>
pointers do point to the same object, might point to the same object, or are
known not to point to the same object.</p>
-<p>The <a href="/doxygen/classAliasAnalysis.html">AliasAnalysis</a> class is the
+<p>The <a href="/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a> class is the
centerpiece of the LLVM Alias Analysis related infrastructure. This class is
the common interface between clients of alias analysis information and the
implementations providing it. In addition to simple alias analysis information,
<div class="doc_text">
-<p>The <a href="/doxygen/classAliasAnalysis.html">AliasAnalysis</a> class
+<p>The <a href="/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a> class
defines the interface that 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 mod/ref
straight-forward. There are already several implementations that you can use
for examples, and the following information should help fill in any details.
For a minimal example, take a look at the <a
-href="/doxygen/structNoAA.html"><tt>no-aa</tt></a> implementation.</p>
+href="/doxygen/structllvm_1_1NoAA.html"><tt>no-aa</tt></a> implementation.</p>
</div>
<div class="doc_text">
-<p>All of the <a href="/doxygen/classAliasAnalysis.html">AliasAnalysis</a>
+<p>All of the <a href="/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a>
virtual methods default to providing conservatively correct information
(returning "May" Alias and "Mod/Ref" for alias and mod/ref queries
respectively). Depending on the capabilities of the analysis you are
<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/classAliasSetTracker.html">AliasSetTracker</a></tt> class is used
+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 AliasAnalysis interface.</p>
<tt>begin()</tt>/<tt>end()</tt> methods.</p>
<p>The <tt>AliasSet</tt>s formed by the <tt>AliasSetTracker</tt> are guaranteed
-to be disjoint, calculate mod/ref information for the set, and keep track of
-whether or not all of the pointers in the set are Must aliases. The
-AliasSetTracker also makes sure that sets are properly folded due to call
+to be disjoint, calculate mod/ref information and volatility for the set, and
+keep track of whether or not all of the pointers in the set are Must aliases.
+The AliasSetTracker also makes sure that sets are properly folded due to call
instructions, and can provide a list of pointers in each set.</p>
<p>As an example user of this, the <a href="/doxygen/structLICM.html">Loop
about each loop nest. If an AliasSet in a loop is not modified, then all load
instructions from that set may be hoisted out of the loop. If any alias sets
are stored <b>and</b> are must alias sets, then the stores may be sunk to
-outside of the loop. Both of these transformations obviously only apply if the
-pointer argument is loop-invariant.</p>
+outside of the loop, promoting the memory location to a register for the
+duration of the loop nest. Both of these transformations obviously only apply
+if the pointer argument is loop-invariant.</p>
+
+</div>
+
+<div class="doc_subsubsection">
+ The AliasSetTracker implementation
+</div>
+
+<div class="doc_text">
+
+<p>The AliasSetTracker class is implemented to be as efficient as possible. It
+uses the union-find algorithm to efficiently merge AliasSets when a pointer is
+inserted into the AliasSetTracker that aliases multiple sets. The primary data
+structure is a hash table mapping pointers to the AliasSet they are in.</p>
+
+<p>The AliasSetTracker class must maintain a list of all of the LLVM Value*'s
+that are in each AliasSet. Since the hash table already has entries for each
+LLVM Value* of interest, the AliasesSets thread the linked list through these
+hash-table nodes to avoid having to allocate memory unnecessarily, and to make
+merging alias sets extremely efficient (the linked list merge is constant time).
+</p>
+
+<p>You shouldn't need to understand these details if you are just a client of
+the AliasSetTracker, but if you look at the code, hopefully this brief
+description will help make sense of why things are designed the way they
+are.</p>
</div>
+
<!-- ======================================================================= -->
<div class="doc_subsection">
<a name="direct">Using the AliasAnalysis interface directly</a>
<hr>
<address>
- <a href="http://jigsaw.w3.org/css-validator/"><img
+ <a href="http://jigsaw.w3.org/css-validator/
check/referer"><img
src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
<a href="http://validator.w3.org/check/referer"><img
src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
projects / oota-llvm.git / blobdiff