X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=docs%2FAliasAnalysis.html;h=c6330a946956edd771204f0dade2b71a268889c9;hb=3850f5cedad95e6062671d66b08e1a29e7d5e20f;hp=748b3cb30eb9c958fb426ffeefe6276849153cef;hpb=d6e0dd1db6c54aab3f76c4189686a881616f73c1;p=oota-llvm.git diff --git a/docs/AliasAnalysis.html b/docs/AliasAnalysis.html index 748b3cb30eb..c6330a94695 100644 --- a/docs/AliasAnalysis.html +++ b/docs/AliasAnalysis.html @@ -31,12 +31,13 @@
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, 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 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.
-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.
+As an exception to this is with the +noalias keyword; the "irrelevant" +dependencies are ignored.
-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 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 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.
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.
- -PassManager support for alternative AliasAnalysis implementation +has some issues.
+ +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 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 -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'.
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.
+ +