@@ -69,12 +71,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 Must, May, or No alias response,
+to a query with a Must, May, or No 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.
The LLVM AliasAnalysis
+href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis
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
@@ -101,7 +103,7 @@ know.
The AliasAnalysis
+href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis
class defines the interface that the various alias analysis implementations
should support. This class exports two important enums: AliasResult
and ModRefResult which represent the result of an alias query or a
@@ -133,16 +135,18 @@ symbolic LLVM Value*) and a static size.
important for correct Alias Analyses. For example, consider this (silly, but
possible) C code:
+
- 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 */
+}
+
In this case, the basicaa pass will disambiguate the stores to
C[0] and C[1] because they are accesses to two distinct
@@ -150,16 +154,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:
+
- 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 */
+}
+
In this case, the two stores to C do alias each other, because the access to
the &C[0] element is a two byte access. If size information wasn't
@@ -269,7 +275,6 @@ memory location to be modified.
Writing a new AliasAnalysis Implementation
@@ -360,25 +363,29 @@ the AliasAnalysis base class: getAnalysisUsage and
declaring any pass dependencies your pass has. Thus you should have something
like this:
+
Additionally, your must invoke the InitializeAliasAnalysis method
from your analysis run method (run for a Pass,
runOnFunction for a FunctionPass, or InitializePass
for an ImmutablePass). For example (as part of a Pass):
@@ -418,17 +425,19 @@ 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:
+
- AliasAnalysis::AliasResult alias(const Value *V1, unsigned V1Size,
- const Value *V2, unsigned V2Size) {
- if (...)
- return NoAlias;
- ...
-
- // Couldn't determine a must or no-alias result.
- return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
- }
+AliasAnalysis::AliasResult alias(const Value *V1, unsigned V1Size,
+ const Value *V2, unsigned V2Size) {
+ if (...)
+ return NoAlias;
+ ...
+
+ // Couldn't determine a must or no-alias result.
+ return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
+}
+
In addition to analysis queries, you must make sure to unconditionally pass
LLVM update notification methods to the superclass as
@@ -472,7 +481,6 @@ for each value in the program. When this method is called, they should remove
any entries for the specified value, if they exist.
-
The copyValue method
@@ -484,7 +492,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.
-
The replaceWithNewValue method
@@ -548,8 +555,8 @@ just use the load-vn pass, which uses alias analysis.
Many transformations need information about alias sets that are active
in some scope, rather than information about pairwise aliasing. The AliasSetTracker class is used
-to efficiently build these Alias Sets from the pairwise alias analysis
+href="/doxygen/classllvm_1_1AliasSetTracker.html">AliasSetTracker class
+is used to efficiently build these Alias Sets from the pairwise alias analysis
information provided by the AliasAnalysis interface.
First you initialize the AliasSetTracker by using the "add" methods
@@ -601,7 +608,6 @@ are.
This section lists the various implementations of the AliasAnalysis
interface. With the exception of the -no-aa and
-basicaa implementations, all of these chain to other alias analysis implementations.
+href="#chaining">chain to other alias analysis implementations.
@@ -661,7 +667,6 @@ problem.
-
The -basicaa pass
@@ -690,6 +695,29 @@ aggressive local analysis that "knows" many important facts:
This pass implements a simple context-sensitive mod/ref and alias analysis
+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
+eliminate call instructions entirely.
+
+
+
The real power of this pass is that it provides context-sensitive mod/ref
+information for call instructions. This allows the optimizer to know that
+calls to a function do not clobber or read the value of the global, allowing
+loads and stores to be eliminated.
+
+
Note that this pass is somewhat limited in its scope (only support
+non-address taken globals), but is very quick analysis.
+
@@ -728,6 +756,9 @@ field-sensitive" 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.
+
Note that -steens-aa is available in the optional "poolalloc"
+module, it is not part of the LLVM core.
+
@@ -748,6 +779,9 @@ 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.
+
Note that -ds-aa is available in the optional "poolalloc"
+module, it is not part of the LLVM core.
+
@@ -821,8 +855,8 @@ pointer.
-
-The -load-vn pass uses alias analysis to "value
+
+
The -load-vn pass uses alias analysis to "value
number" loads and pointers values, which is used by the GCSE pass to
eliminate instructions. The -load-vn pass relies on alias information
and must-alias information. This combination of passes can make the following
@@ -840,18 +874,19 @@ calls into direct calls.
-These passes are useful for evaluating the various alias analysis
+
+
+
These passes are useful for evaluating the various alias analysis
implementations. You can use them with commands like 'opt -anders-aa -ds-aa
--aa-eval foo.bc -disable-output -stats'.
+-aa-eval foo.bc -disable-output -stats'.
+
@@ -861,9 +896,15 @@ implementations. You can use them with commands like 'opt -anders-aa -ds-aa
+the AliasSetTracker class. To use it, use something like:
+
+
+
+% opt -ds-aa -print-alias-sets -disable-output
+
+
@@ -876,17 +917,19 @@ the AliasSetTracker class.
The -count-aa 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:
+pass is making and what responses are returned by the alias analysis. As an
+example,
+
Which will print out how many queries (and what responses are returned) by
-the -licm pass (of the -ds-aa pass) and how many queries are
-made of the -basicaa pass by the -ds-aa pass. This can be
-useful when debugging a transformation or an alias analysis implementation.
+
will print out how many queries (and what responses are returned) by the
+-licm pass (of the -ds-aa pass) and how many queries are made
+of the -basicaa pass by the -ds-aa pass. This can be useful
+when debugging a transformation or an alias analysis implementation.
@@ -905,6 +948,24 @@ algorithm will have a lower number of may aliases).
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.