The LLVM Alias Analysis Infrastructure

@@ -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 @@ -185,16 +191,20 @@ and returns MustAlias, MayAlias, or NoAlias as appropriate.

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.

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.

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.

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.

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.

@@ -215,12 +225,7 @@ 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. Clients that use -this method should be predicated on the hasNoModRefInfoForCalls() -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 getModRefInfo -method many times.

+accessed by CS2. Note that this relation is not commutative.

Writing a new AliasAnalysis Implementation @@ -360,25 +347,29 @@ the AliasAnalysis base class: getAnalysisUsage and declaring any pass dependencies your pass has. Thus you should have something like this:

-    void getAnalysisUsage(AnalysisUsage &AU) const {
-      AliasAnalysis::getAnalysisUsage(AU);
-      // declare your dependencies here.
-    }
+void getAnalysisUsage(AnalysisUsage &AU) const {
+  AliasAnalysis::getAnalysisUsage(AU);
+  // declare your dependencies here.
+}

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):

-    bool run(Module &M) {
-      InitializeAliasAnalysis(this);
-      // Perform analysis here...
-      return false;
-    }
+bool run(Module &M) {
+  InitializeAliasAnalysis(this);
+  // Perform analysis here...
+  return false;
+}

In addition to analysis queries, you must make sure to unconditionally pass LLVM update notification methods to the superclass as @@ -472,7 +465,6 @@ for each value in the program. When this method is called, they should remove any entries for the specified value, if they exist. -

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 +592,6 @@ are.

The -basicaa pass @@ -698,9 +687,11 @@ 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. +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. GVN) to +eliminate call instructions entirely.

The real power of this pass is that it provides context-sensitive mod/ref @@ -712,25 +703,6 @@ loads and stores to be eliminated.

non-address taken globals), but is very quick analysis.

- -

- The -anders-aa pass -

- -

The -anders-aa 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³). 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. -

- -

The -steens-aa pass @@ -749,6 +721,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.

@@ -769,6 +744,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.

@@ -882,9 +849,15 @@ implementations. You can use them with commands like 'opt -anders-aa -ds-aa

The -print-alias-sets pass is exposed as part of the -analyze tool to print out the Alias Sets formed by the opt tool to print out the Alias Sets formed by the AliasSetTracker class. This is useful if you're using -the AliasSetTracker class.

+the AliasSetTracker class. To use it, use something like:

+ +

+% opt -ds-aa -print-alias-sets -disable-output
+

@@ -897,17 +870,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,

-  $ opt -basicaa -count-aa -ds-aa -count-aa -licm
+% opt -basicaa -count-aa -ds-aa -count-aa -licm

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.

@@ -926,17 +901,35 @@ algorithm will have a lower number of may aliases).