-
The AliasAnalysis class is the +
The AliasAnalysis class is the centerpiece of the LLVM Alias Analysis related infrastructure. This class is the common interface between clients of alias analysis information and the implementations providing it. In addition to simple alias analysis information, @@ -89,7 +89,7 @@ know.
The AliasAnalysis class +
The AliasAnalysis class defines the interface that Alias Analysis implementations should support. This class exports two important enums: AliasResult and ModRefResult which represent the result of an alias query or a mod/ref @@ -199,7 +199,7 @@ is returned.
straight-forward. There are already several implementations that you can use for examples, and the following information should help fill in any details. For a minimal example, take a look at the no-aa implementation. +href="/doxygen/structllvm_1_1NoAA.html">no-aa implementation.All of the AliasAnalysis +
All of the AliasAnalysis virtual methods default to providing conservatively correct information (returning "May" Alias and "Mod/Ref" for alias and mod/ref queries respectively). Depending on the capabilities of the analysis you are @@ -355,7 +355,7 @@ to do anything special to handle load instructions: just use the
Many transformations need information about alias sets that are active in some scope, rather than information about pairwise aliasing. The AliasSetTracker class is used +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.
@@ -366,9 +366,9 @@ simply iterate through the constructed alias sets, using the AliasSetTracker begin()/end() methods.The AliasSets formed by the AliasSetTracker are guaranteed -to be disjoint, calculate mod/ref information for the set, and keep track of -whether or not all of the pointers in the set are Must aliases. The -AliasSetTracker also makes sure that sets are properly folded due to call +to be disjoint, calculate mod/ref information and volatility for the set, and +keep track of whether or not all of the pointers in the set are Must aliases. +The AliasSetTracker also makes sure that sets are properly folded due to call instructions, and can provide a list of pointers in each set.
As an example user of this, the Loop @@ -376,11 +376,38 @@ Invariant Code Motion pass uses AliasSetTrackers to build alias information about each loop nest. If an AliasSet in a loop is not modified, then all load instructions from that set may be hoisted out of the loop. If any alias sets are stored and are must alias sets, then the stores may be sunk to -outside of the loop. Both of these transformations obviously only apply if the -pointer argument is loop-invariant.
+outside of the loop, promoting the memory location to a register for the +duration of the loop nest. Both of these transformations obviously only apply +if the pointer argument is loop-invariant. + +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 +inserted into the AliasSetTracker that aliases multiple sets. The primary data +structure is a hash table mapping pointers to the AliasSet they are in.
+ +The AliasSetTracker class must maintain a list of all of the LLVM Value*'s +that are in each AliasSet. Since the hash table already has entries for each +LLVM Value* of interest, the AliasesSets thread the linked list through these +hash-table nodes to avoid having to allocate memory unnecessarily, and to make +merging alias sets extremely efficient (the linked list merge is constant time). +
+ +You shouldn't need to understand these details if you are just a client of +the AliasSetTracker, but if you look at the code, hopefully this brief +description will help make sense of why things are designed the way they +are.