All AliasAnalysis interfaces require that in queries involving +multiple values, values which are not +constants are all defined within the +same function.
+ @@ -180,9 +186,14 @@ 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, -even 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 @@ -222,15 +241,10 @@ 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. 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.
+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.The getMustAliases 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.
- -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.
+ +The load-vn pass uses alias analysis to provide value numbering -information for load 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 load-vn pass, which uses alias analysis.
+The memdep 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. +
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:
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(N3). 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 -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 -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 -transformations:
- -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 -anders-aa -ds-aa +implementations. You can use them with commands like 'opt -ds-aa -aa-eval foo.bc -disable-output -stats'.