Alias Analysis (aka Pointer Analysis) is a class of techniques which attempt to determine whether or not two pointers ever can point to the same object in @@ -95,12 +96,12 @@ know.
The AliasAnalysis @@ -116,14 +117,17 @@ as the actual call or invoke instructions that performs the call. The AliasAnalysis interface also exposes some helper methods which allow you to get mod/ref information for arbitrary instructions.
-All AliasAnalysis interfaces require that in queries involving +multiple values, values which are not +constants are all defined within the +same function.
- + -Most importantly, the AliasAnalysis class provides several methods which are used to query whether or not two memory objects alias, whether @@ -175,32 +179,44 @@ that the accesses alias.
The alias 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.
+ +Like all AliasAnalysis interfaces, the alias method requires +that either the two pointer values be defined within the same function, or at +least one of the values is a constant.
- - -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.
+ + +The NoAlias response may be used when there is never an immediate dependence +between any memory reference based on one pointer and any memory +reference based 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.
+ +As an exception to this is with the +noalias keyword; the "irrelevant" +dependencies are ignored.
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.
+same object. + +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.
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 @@ -208,12 +224,14 @@ implies that the pointers compare equal.
The getModRefInfo methods return information about whether the execution of an instruction can read or modify a memory location. Mod/Ref @@ -222,34 +240,32 @@ a location, ModRef is returned.
The AliasAnalysis class also provides a getModRefInfo 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.
+call sites (CS1 & 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.Several other tidbits of information are often collected by various alias analysis implementations and can be put to good use by various clients.
-The pointsToConstantMemory method returns true if and only if the analysis can prove that the pointer only points to unchanging memory locations @@ -260,12 +276,12 @@ memory location to be modified.
These methods are used to provide very simple mod/ref information for function calls. The doesNotAccessMemory method returns true for a @@ -288,13 +304,17 @@ functions that satisfy the doesNotAccessMemory method also satisfies
Writing a new alias analysis implementation for LLVM is quite straight-forward. There are already several implementations that you can use @@ -302,14 +322,12 @@ for examples, and the following information should help fill in any details. For a examples, take a look at the various alias analysis implementations included with LLVM.
-The first step to determining what type of LLVM pass you need to use for your Alias @@ -333,11 +351,11 @@ solve:
Your subclass of AliasAnalysis is required to invoke two methods on the AliasAnalysis base class: getAnalysisUsage and @@ -374,11 +392,11 @@ bool run(Module &M) {
All of the AliasAnalysis @@ -393,11 +411,11 @@ implementing, you just override the interfaces you can improve.
- + -With only two special exceptions (the basicaa and no-aa @@ -432,11 +450,11 @@ updated.
- + -Alias analysis information is initially computed for a static snapshot of the program, but clients will use this information to make transformations to the @@ -445,19 +463,18 @@ analysis results updated to reflect the changes made by these transformations.
-The AliasAnalysis interface exposes two methods which are used to +The AliasAnalysis 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 example, when an instruction is deleted), and clients of alias analysis must be sure to call these interfaces appropriately.
-The addEscapingUse 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.
+ +In general, any new use of a pointer value is considered an escaping use, +and must be reported through this callback, except for the +uses below:
+ +From the LLVM perspective, the only thing you need to do to provide an efficient alias analysis is to make sure that alias analysis queries are @@ -502,25 +543,98 @@ method as possible (within reason).
The AliasAnalysis infrastructure has several limitations which make +writing a new AliasAnalysis implementation difficult.
+ +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.
+ +There is no way for transform passes to declare that they preserve +AliasAnalysis implementations. The AliasAnalysis +interface includes deleteValue and copyValue 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 +getAnalysisUsage that it does so. Some passes attempt to use +AU.addPreserved<AliasAnalysis>, however this doesn't +actually have any effect.
+ +AliasAnalysisCounter (-count-aa) and AliasDebugger +(-debug-aa) are implemented as ModulePass classes, so if your +alias analysis uses FunctionPass, 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 +BasicAliasAnalysis instead.
+ +Similarly, the opt -p option introduces ModulePass +passes between each pass, which prevents the use of FunctionPass +alias analysis passes.
+ +The AliasAnalysis 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 AliasAnalysis +implementations which can not be expressed.
+ +The AliasAnalysisDebugger utility seems to suggest that +AliasAnalysis implementations can expect that they will be +informed of any relevant Value before it appears in an +alias query. However, popular clients such as GVN don't +support this, and are known to trigger errors when run with the +AliasAnalysisDebugger.
+ +Due to several of the above limitations, the most obvious use for +the AliasAnalysisCounter utility, collecting stats on all +alias queries in a compilation, doesn't work, even if the +AliasAnalysis implementations don't use FunctionPass. +There's no way to set a default, much less a default sequence, +and there's no way to preserve it.
+ +The AliasSetTracker class (which is used by LICM +makes a non-deterministic number of alias queries. This can cause stats +collected by AliasAnalysisCounter 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.
+ +Many alias queries can be reformulated in terms of other alias +queries. When multiple AliasAnalysis 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.
+ +There are several different ways to use alias analysis results. In order of preference, these are...
-The memdep pass uses alias analysis to provide high-level dependence information about memory-using instructions. This will tell you which store @@ -531,11 +645,11 @@ efficient, and is used by Dead Store Elimination, GVN, and memcpy optimizations.
Many transformations need information about alias sets that are active in some scope, rather than information about pairwise aliasing. The -
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 @@ -592,12 +704,14 @@ are.
If neither of these utility class are what your pass needs, you should use the interfaces exposed by the AliasAnalysis class directly. Try to use @@ -607,13 +721,15 @@ best precision and efficiency.
If you're going to be working with the LLVM alias analysis infrastructure, you should know what clients and implementations of alias analysis are @@ -621,28 +737,24 @@ available. In particular, if you are implementing an alias analysis, you should be aware of the the clients that are useful for monitoring and evaluating different implementations.
-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.
- -The -no-aa pass is just like what it sounds: an alias analysis that never returns any useful information. This pass can be useful if you think that @@ -652,14 +764,14 @@ problem.
The -basicaa pass is the default LLVM alias analysis. It is an -aggressive local analysis that "knows" many important facts:
+The -basicaa pass is an 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 @@ -704,11 +816,11 @@ non-address taken globals), but is very quick analysis.
The -steens-aa pass implements a variation on the well-known "Steensgaard's algorithm" for interprocedural alias analysis. Steensgaard's @@ -727,11 +839,11 @@ module, it is not part of the LLVM core.
The -ds-aa pass implements the full Data Structure Analysis algorithm. Data Structure Analysis is a modular unification-based, @@ -749,23 +861,37 @@ module, it is not part of the LLVM core.
The -scev-aa pass implements AliasAnalysis queries by +translating them into ScalarEvolution queries. This gives it a +more complete understanding of getelementptr instructions +and loop induction variables than other alias analyses have.
+ +The -adce pass, which implements Aggressive Dead Code Elimination uses the AliasAnalysis interface to delete calls to functions that do @@ -775,11 +901,11 @@ not have side-effects and are not used.
-The -licm pass implements various Loop Invariant Code Motion related transformations. It uses the AliasAnalysis interface for several @@ -800,11 +926,11 @@ no may aliases to the loaded/stored memory location.
The -argpromotion pass promotes by-reference arguments to be passed in by-value instead. In particular, if pointer arguments are only loaded from it @@ -815,38 +941,38 @@ pointer.
These passes use AliasAnalysis information to reason about loads and stores.
These passes are useful for evaluating the various alias analysis implementations. You can use them with commands like 'opt -ds-aa -aa-eval foo.bc -disable-output -stats'.
-The -print-alias-sets pass is exposed as part of the opt tool to print out the Alias Sets formed by the AliasSetTracker class. To use it, use something like:
- + -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. As an @@ -887,11 +1013,11 @@ when debugging a transformation or an alias analysis implementation.
The -aa-eval pass simply iterates through all pairs of pointers in a function and asks an alias analysis whether or not the pointers alias. This @@ -901,13 +1027,17 @@ 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, @@ -929,7 +1059,7 @@ analysis directly.
src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"> Chris Lattner