It is possible for SimplifyCFG to cause PHI nodes to become redundant too late in...
[oota-llvm.git] / docs / AliasAnalysis.html
index 10227fb90a51e29084dd8fef57871b295a2bb9c4..6962a3f27d6a8d8b9fe6cce1568d9fde0df71b2d 100644 (file)
     <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="#limitations">Limitations</a></li>
     </ul>
   </li>
 
   <li><a href="#using">Using alias analysis results</a>
     <ul>
-    <li><a href="#loadvn">Using the <tt>-load-vn</tt> Pass</a></li>
+    <li><a href="#memdep">Using the <tt>MemoryDependenceAnalysis</tt> Pass</a></li>
     <li><a href="#ast">Using the <tt>AliasSetTracker</tt> class</a></li>
     <li><a href="#direct">Using the <tt>AliasAnalysis</tt> interface directly</a></li>
     </ul>
@@ -50,6 +51,7 @@
     implementations</a></li>
     </ul>
   </li>
+  <li><a href="#memdep">Memory Dependence Analysis</a></li>
 </ol>
 
 <div class="doc_author">
@@ -70,12 +72,12 @@ memory.  There are many different algorithms for alias analysis and many
 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
@@ -102,7 +104,7 @@ know</a>.</p>
 <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
@@ -115,6 +117,11 @@ as the actual <tt>call</tt> or <tt>invoke</tt> instructions that performs the
 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>
 
 <!-- ======================================================================= -->
@@ -134,16 +141,18 @@ symbolic LLVM <tt>Value*</tt>) and a static size.</p>
 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
@@ -151,16 +160,18 @@ locations one byte apart, and the accesses are each one byte.  In this case, the
 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>&amp;C[0]</tt> element is a two byte access.  If size information wasn't
@@ -175,9 +186,14 @@ that the accesses alias.</p>
 </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>
 
 <!-- _______________________________________________________________________ -->
@@ -186,16 +202,28 @@ and returns MustAlias, MayAlias, or NoAlias as appropriate.
 </div>
 
 <div class="doc_text">
+<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>An Alias Analysis implementation can return one of three responses:
-MustAlias, MayAlias, and NoAlias.  The No and May alias results are obvious: if
-the two pointers can never equal each other, return NoAlias, if they might,
-return MayAlias.</p>
+<p>The MayAlias response is used whenever the two pointers might refer to the
+same object.</p>
 
-<p>The MustAlias response is trickier though.  In LLVM, the Must Alias response
-may only be returned if the two memory objects are guaranteed to always start at
-exactly the same location.  If two memory objects overlap, but do not start at
-the same location, return MayAlias.</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
+implies that the pointers compare equal.</p>
 
 </div>
 
@@ -213,15 +241,10 @@ a location, ModRef is returned.</p>
 
 <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 &amp; 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.  Clients that use
-this method should be predicated on the <tt>hasNoModRefInfoForCalls()</tt>
-method, which indicates whether or not an analysis can provide mod/ref
-information for function call pairs (most can not).  If this predicate is false,
-the client shouldn't waste analysis time querying the <tt>getModRefInfo</tt>
-method many times.</p>
+call sites (CS1 &amp; 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>
 
@@ -240,21 +263,6 @@ analysis implementations and can be put to good use by various clients.
 
 </div>
 
-<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
-  The <tt>getMustAliases</tt> method
-</div>
-
-<div class="doc_text">
-
-<p>The <tt>getMustAliases</tt> method returns all values that are known to
-always must alias a pointer.  This information can be provided in some cases for
-important objects like the null pointer and global values.  Knowing that a
-pointer always points to a particular function allows indirect calls to be
-turned into direct calls, for example.</p>
-
-</div>
-
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsubsection">
   The <tt>pointsToConstantMemory</tt> method
@@ -270,7 +278,6 @@ memory location to be modified.</p>
 
 </div>
 
-
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsubsection">
   <a name="simplemodref">The <tt>doesNotAccessMemory</tt> and
@@ -300,8 +307,6 @@ functions that satisfy the <tt>doesNotAccessMemory</tt> method also satisfies
 
 </div>
 
-
-
 <!-- *********************************************************************** -->
 <div class="doc_section">
   <a name="writingnew">Writing a new <tt>AliasAnalysis</tt> Implementation</a>
@@ -361,25 +366,29 @@ the <tt>AliasAnalysis</tt> base class: <tt>getAnalysisUsage</tt> and
 declaring any pass dependencies your pass has.  Thus you should have something
 like this:</p>
 
+<div class="doc_code">
 <pre>
-    void getAnalysisUsage(AnalysisUsage &amp;AU) const {
-      AliasAnalysis::getAnalysisUsage(AU);
-      <i>// declare your dependencies here.</i>
-    }
+void getAnalysisUsage(AnalysisUsage &amp;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 &amp;M) {
-      InitializeAliasAnalysis(this);
-      <i>// Perform analysis here...</i>
-      return false;
-    }
+bool run(Module &amp;M) {
+  InitializeAliasAnalysis(this);
+  <i>// Perform analysis here...</i>
+  return false;
+}
 </pre>
+</div>
 
 </div>
 
@@ -413,23 +422,25 @@ implementing, you just override the interfaces you can improve.</p>
 href="#basic-aa">basicaa</a></tt> and <a href="#no-aa"><tt>no-aa</tt></a>
 passes) every alias analysis pass chains to another alias analysis
 implementation (for example, the user can specify "<tt>-basicaa -ds-aa
--anders-aa -licm</tt>" to get the maximum benefit from the three alias
+-licm</tt>" to get the maximum benefit from both alias
 analyses).  The alias analysis class automatically takes care of most of this
 for methods that you don't override.  For methods that you do override, in code
 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
@@ -473,7 +484,6 @@ for each value in the program.  When this method is called, they should remove
 any entries for the specified value, if they exist.
 </div>
 
-
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsubsection">The <tt>copyValue</tt> method</div>
 
@@ -485,7 +495,6 @@ this is the only way to introduce a new value.  This method indicates that the
 new value has exactly the same properties as the value being copied.
 </div>
 
-
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsubsection">The <tt>replaceWithNewValue</tt> method</div>
 
@@ -512,6 +521,79 @@ method as possible (within reason).</p>
 
 </div>
 
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+  <a name="limitations">Limitations</a>
+</div>
+
+<div class="doc_text">
+
+<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
+have it use -my-aa for all passes which need AliasAnalysis, but there
+is currently no support for that, short of changing the source code
+and recompiling. Similarly, there is also no way of setting a chain
+of analyses as the default.</p>
+
+<p>There is no way for transform passes to declare that they preserve
+<tt>AliasAnalysis</tt> implementations. The <tt>AliasAnalysis</tt>
+interface includes <tt>deleteValue</tt> and <tt>copyValue</tt> methods
+which are intended to allow a pass to keep an AliasAnalysis consistent,
+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&lt;AliasAnalysis&gt;</tt>, however this doesn't
+actually have any effect.</tt>
+
+<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
+alias analysis uses <tt>FunctionPass</tt>, it won't be able to use
+these utilities. If you try to use them, the pass manager will
+silently route alias analysis queries directly to
+<tt>BasicAliasAnalysis</tt> instead.</p>
+
+<p>Similarly, the <tt>opt -p</tt> option introduces <tt>ModulePass</tt>
+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_section">
   <a name="using">Using alias analysis results</a>
@@ -527,16 +609,16 @@ preference, these are...</p>
 
 <!-- ======================================================================= -->
 <div class="doc_subsection">
-  <a name="loadvn">Using the <tt>-load-vn</tt> Pass</a>
+  <a name="memdep">Using the <tt>MemoryDependenceAnalysis</tt> Pass</a>
 </div>
 
 <div class="doc_text">
 
-<p>The <tt>load-vn</tt> pass uses alias analysis to provide value numbering
-information for <tt>load</tt> instructions and pointer values.  If your analysis
-or transformation can be modeled in a form that uses value numbering
-information, you don't have to do anything special to handle load instructions:
-just use the <tt>load-vn</tt> pass, which uses alias analysis.</p>
+<p>The <tt>memdep</tt> pass uses alias analysis to provide high-level dependence
+information about memory-using instructions.  This will tell you which store
+feeds into a load, for example.  It uses caching and other techniques to be
+efficient, and is used by Dead Store Elimination, GVN, and memcpy optimizations.
+</p>
 
 </div>
 
@@ -549,8 +631,8 @@ just use the <tt>load-vn</tt> pass, which uses alias analysis.</p>
 
 <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
@@ -602,7 +684,6 @@ are.</p>
 
 </div>
 
-
 <!-- ======================================================================= -->
 <div class="doc_subsection">
   <a name="direct">Using the <tt>AliasAnalysis</tt> interface directly</a>
@@ -662,7 +743,6 @@ problem.</p>
 
 </div>
 
-
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsubsection">
   <a name="basic-aa">The <tt>-basicaa</tt> pass</a>
@@ -670,8 +750,8 @@ problem.</p>
 
 <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
@@ -702,7 +782,7 @@ aggressive local analysis that "knows" many important facts:</p>
 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
+memory or never read memory.  This allows certain optimizations (e.g. GVN) to
 eliminate call instructions entirely.
 </p>
 
@@ -715,25 +795,6 @@ loads and stores to be eliminated.</p>
 non-address taken globals), but is very quick analysis.</p>
 </div>
 
-<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
-  <a name="anders-aa">The <tt>-anders-aa</tt> pass</a>
-</div>
-
-<div class="doc_text">
-
-<p>The <tt>-anders-aa</tt> pass implements the well-known "Andersen's algorithm"
-for interprocedural alias analysis.  This algorithm is a subset-based,
-flow-insensitive, context-insensitive, and field-insensitive alias analysis that
-is widely believed to be fairly precise.  Unfortunately, this algorithm is also
-O(N<sup>3</sup>).  The LLVM implementation currently does not implement any of
-the refinements (such as "online cycle elimination" or "offline variable
-substitution") to improve its efficiency, so it can be quite slow in common
-cases.
-</p>
-
-</div>
-
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsubsection">
   <a name="steens-aa">The <tt>-steens-aa</tt> pass</a>
@@ -752,6 +813,9 @@ field-<b>sensitive</b>" version of Steensgaard's algorithm using the Data
 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>
 
 <!-- _______________________________________________________________________ -->
@@ -772,8 +836,24 @@ queries, and can provide context-sensitive mod/ref information as well.  The
 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 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">
@@ -841,41 +921,30 @@ pointer.</p>
 
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsubsection">
-  <a name="gcseloadvn">The <tt>-load-vn</tt> &amp; <tt>-gcse</tt> passes</a>
+  <a name="gvn">The <tt>-gvn</tt>, <tt>-memcpyopt</tt>, and <tt>-dse</tt>
+     passes</a>
 </div>
 
 <div class="doc_text">
-<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
-transformations:</p>
 
-<ul>
-<li>Redundant load instructions are eliminated.</li>
-<li>Load instructions that follow a store to the same location are replaced with
-the stored value ("store forwarding").</li>
-<li>Pointers values (e.g. formal arguments) that must-alias simpler expressions
-(e.g. global variables or the null pointer) are replaced.  Note that this
-implements transformations like "virtual method resolution", turning indirect
-calls into direct calls.</li>
-</ul>
+<p>These passes use AliasAnalysis information to reason about loads and stores.
+</p>
 
 </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
-implementations.  You can use them with commands like '<tt>opt -anders-aa -ds-aa
--aa-eval foo.bc -disable-output -stats</tt>'.
+<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 -ds-aa
+-aa-eval foo.bc -disable-output -stats</tt>'.</p>
+
+</div>
 
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsubsection">
@@ -885,9 +954,15 @@ implementations.  You can use them with commands like '<tt>opt -anders-aa -ds-aa
 <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>
 
@@ -900,17 +975,19 @@ the <tt>AliasSetTracker</tt> class.</p>
 <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>
 
@@ -929,17 +1006,35 @@ algorithm will have a lower number of may aliases).</p>
 
 </div>
 
+<!-- *********************************************************************** -->
+<div class="doc_section">
+  <a name="memdep">Memory Dependence Analysis</a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+
+<p>If you're just looking to be a client of alias analysis information, consider
+using the Memory Dependence Analysis interface instead.  MemDep is a lazy, 
+caching layer on top of alias analysis that is able to answer the question of
+what preceding memory operations a given instruction depends on, either at an
+intra- or inter-block level.  Because of its laziness and caching 
+policy, using MemDep can be a significant performance win over accessing alias
+analysis directly.</p>
+
+</div>
+
 <!-- *********************************************************************** -->
 
 <hr>
 <address>
   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
-  src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
+  src="http://jigsaw.w3.org/css-validator/images/vcss-blue" 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>
+  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.cs.uiuc.edu">LLVM Compiler Infrastructure</a><br>
+  <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
   Last modified: $Date$
 </address>