LLVM API Documentation

AliasAnalysis.h

Go to the documentation of this file.
00001 //===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the generic AliasAnalysis interface, which is used as the
00011 // common interface used by all clients of alias analysis information, and
00012 // implemented by all alias analysis implementations.  Mod/Ref information is
00013 // also captured by this interface.
00014 //
00015 // Implementations of this interface must implement the various virtual methods,
00016 // which automatically provides functionality for the entire suite of client
00017 // APIs.
00018 //
00019 // This API represents memory as a (Pointer, Size) pair.  The Pointer component
00020 // specifies the base memory address of the region, the Size specifies how large
00021 // of an area is being queried.  If Size is 0, two pointers only alias if they
00022 // are exactly equal.  If size is greater than zero, but small, the two pointers
00023 // alias if the areas pointed to overlap.  If the size is very large (ie, ~0U),
00024 // then the two pointers alias if they may be pointing to components of the same
00025 // memory object.  Pointers that point to two completely different objects in
00026 // memory never alias, regardless of the value of the Size component.
00027 //
00028 //===----------------------------------------------------------------------===//
00029 
00030 #ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H
00031 #define LLVM_ANALYSIS_ALIAS_ANALYSIS_H
00032 
00033 #include "llvm/Support/CallSite.h"
00034 #include "llvm/System/IncludeFile.h"
00035 
00036 namespace llvm {
00037 
00038 class LoadInst;
00039 class StoreInst;
00040 class VAArgInst;
00041 class TargetData;
00042 class Pass;
00043 class AnalysisUsage;
00044 
00045 class AliasAnalysis {
00046 protected:
00047   const TargetData *TD;
00048   AliasAnalysis *AA;       // Previous Alias Analysis to chain to.
00049 
00050   /// InitializeAliasAnalysis - Subclasses must call this method to initialize
00051   /// the AliasAnalysis interface before any other methods are called.  This is
00052   /// typically called by the run* methods of these subclasses.  This may be
00053   /// called multiple times.
00054   ///
00055   void InitializeAliasAnalysis(Pass *P);
00056 
00057   // getAnalysisUsage - All alias analysis implementations should invoke this
00058   // directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that
00059   // TargetData is required by the pass.
00060   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
00061 
00062 public:
00063   AliasAnalysis() : TD(0), AA(0) {}
00064   virtual ~AliasAnalysis();  // We want to be subclassed
00065 
00066   /// getTargetData - Every alias analysis implementation depends on the size of
00067   /// data items in the current Target.  This provides a uniform way to handle
00068   /// it.
00069   ///
00070   const TargetData &getTargetData() const { return *TD; }
00071 
00072   //===--------------------------------------------------------------------===//
00073   /// Alias Queries...
00074   ///
00075 
00076   /// Alias analysis result - Either we know for sure that it does not alias, we
00077   /// know for sure it must alias, or we don't know anything: The two pointers
00078   /// _might_ alias.  This enum is designed so you can do things like:
00079   ///     if (AA.alias(P1, P2)) { ... }
00080   /// to check to see if two pointers might alias.
00081   ///
00082   enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 };
00083 
00084   /// alias - The main low level interface to the alias analysis implementation.
00085   /// Returns a Result indicating whether the two pointers are aliased to each
00086   /// other.  This is the interface that must be implemented by specific alias
00087   /// analysis implementations.
00088   ///
00089   virtual AliasResult alias(const Value *V1, unsigned V1Size,
00090                             const Value *V2, unsigned V2Size);
00091 
00092   /// getMustAliases - If there are any pointers known that must alias this
00093   /// pointer, return them now.  This allows alias-set based alias analyses to
00094   /// perform a form a value numbering (which is exposed by load-vn).  If an
00095   /// alias analysis supports this, it should ADD any must aliased pointers to
00096   /// the specified vector.
00097   ///
00098   virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals);
00099 
00100   /// pointsToConstantMemory - If the specified pointer is known to point into
00101   /// constant global memory, return true.  This allows disambiguation of store
00102   /// instructions from constant pointers.
00103   ///
00104   virtual bool pointsToConstantMemory(const Value *P);
00105 
00106   //===--------------------------------------------------------------------===//
00107   /// Simple mod/ref information...
00108   ///
00109 
00110   /// ModRefResult - Represent the result of a mod/ref query.  Mod and Ref are
00111   /// bits which may be or'd together.
00112   ///
00113   enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 };
00114 
00115 
00116   /// ModRefBehavior - Summary of how a function affects memory in the program.
00117   /// Loads from constant globals are not considered memory accesses for this
00118   /// interface.  Also, functions may freely modify stack space local to their
00119   /// invocation without having to report it through these interfaces.
00120   enum ModRefBehavior {
00121     // DoesNotAccessMemory - This function does not perform any non-local loads
00122     // or stores to memory.
00123     //
00124     // This property corresponds to the GCC 'const' attribute.
00125     DoesNotAccessMemory,
00126 
00127     // AccessesArguments - This function accesses function arguments in
00128     // non-volatile and well known ways, but does not access any other memory.
00129     //
00130     // Clients may call getArgumentAccesses to get specific information about
00131     // how pointer arguments are used.
00132     AccessesArguments,
00133 
00134     // AccessesArgumentsAndGlobals - This function has accesses function
00135     // arguments and global variables in non-volatile and well-known ways, but
00136     // does not access any other memory.
00137     //
00138     // Clients may call getArgumentAccesses to get specific information about
00139     // how pointer arguments and globals are used.
00140     AccessesArgumentsAndGlobals,
00141 
00142     // OnlyReadsMemory - This function does not perform any non-local stores or
00143     // volatile loads, but may read from any memory location.
00144     //
00145     // This property corresponds to the GCC 'pure' attribute.
00146     OnlyReadsMemory,
00147 
00148     // UnknownModRefBehavior - This indicates that the function could not be
00149     // classified into one of the behaviors above.
00150     UnknownModRefBehavior
00151   };
00152 
00153   /// PointerAccessInfo - This struct is used to return results for pointers,
00154   /// globals, and the return value of a function.
00155   struct PointerAccessInfo {
00156     /// V - The value this record corresponds to.  This may be an Argument for
00157     /// the function, a GlobalVariable, or null, corresponding to the return
00158     /// value for the function.
00159     Value *V;
00160 
00161     /// ModRefInfo - Whether the pointer is loaded or stored to/from.
00162     ///
00163     ModRefResult ModRefInfo;
00164 
00165     /// AccessType - Specific fine-grained access information for the argument.
00166     /// If none of these classifications is general enough, the
00167     /// getModRefBehavior method should not return AccessesArguments*.  If a
00168     /// record is not returned for a particular argument, the argument is never
00169     /// dead and never dereferenced.
00170     enum AccessType {
00171       /// ScalarAccess - The pointer is dereferenced.
00172       ///
00173       ScalarAccess,
00174 
00175       /// ArrayAccess - The pointer is indexed through as an array of elements.
00176       ///
00177       ArrayAccess,
00178 
00179       /// ElementAccess ?? P->F only?
00180 
00181       /// CallsThrough - Indirect calls are made through the specified function
00182       /// pointer.
00183       CallsThrough
00184     };
00185   };
00186 
00187   /// getModRefBehavior - Return the behavior of the specified function if
00188   /// called from the specified call site.  The call site may be null in which
00189   /// case the most generic behavior of this function should be returned.
00190   virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
00191                                      std::vector<PointerAccessInfo> *Info = 0);
00192 
00193   /// doesNotAccessMemory - If the specified function is known to never read or
00194   /// write memory, return true.  If the function only reads from known-constant
00195   /// memory, it is also legal to return true.  Functions that unwind the stack
00196   /// are not legal for this predicate.
00197   ///
00198   /// Many optimizations (such as CSE and LICM) can be performed on calls to it,
00199   /// without worrying about aliasing properties, and many functions have this
00200   /// property (e.g. 'sin' and 'cos').
00201   ///
00202   /// This property corresponds to the GCC 'const' attribute.
00203   ///
00204   bool doesNotAccessMemory(Function *F) {
00205     return getModRefBehavior(F, CallSite()) == DoesNotAccessMemory;
00206   }
00207 
00208   /// onlyReadsMemory - If the specified function is known to only read from
00209   /// non-volatile memory (or not access memory at all), return true.  Functions
00210   /// that unwind the stack are not legal for this predicate.
00211   ///
00212   /// This property allows many common optimizations to be performed in the
00213   /// absence of interfering store instructions, such as CSE of strlen calls.
00214   ///
00215   /// This property corresponds to the GCC 'pure' attribute.
00216   ///
00217   bool onlyReadsMemory(Function *F) {
00218     /// FIXME: If the analysis returns more precise info, we can reduce it to
00219     /// this.
00220     ModRefBehavior MRB = getModRefBehavior(F, CallSite());
00221     return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory;
00222   }
00223 
00224 
00225   /// getModRefInfo - Return information about whether or not an instruction may
00226   /// read or write memory specified by the pointer operand.  An instruction
00227   /// that doesn't read or write memory may be trivially LICM'd for example.
00228 
00229   /// getModRefInfo (for call sites) - Return whether information about whether
00230   /// a particular call site modifies or reads the memory specified by the
00231   /// pointer.
00232   ///
00233   virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
00234 
00235   /// getModRefInfo - Return information about whether two call sites may refer
00236   /// to the same set of memory locations.  This function returns NoModRef if
00237   /// the two calls refer to disjoint memory locations, Ref if CS1 reads memory
00238   /// written by CS2, Mod if CS1 writes to memory read or written by CS2, or
00239   /// ModRef if CS1 might read or write memory accessed by CS2.
00240   ///
00241   virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2);
00242 
00243   /// hasNoModRefInfoForCalls - Return true if the analysis has no mod/ref
00244   /// information for pairs of function calls (other than "pure" and "const"
00245   /// functions).  This can be used by clients to avoid many pointless queries.
00246   /// Remember that if you override this and chain to another analysis, you must
00247   /// make sure that it doesn't have mod/ref info either.
00248   ///
00249   virtual bool hasNoModRefInfoForCalls() const;
00250 
00251   /// Convenience functions...
00252   ModRefResult getModRefInfo(LoadInst *L, Value *P, unsigned Size);
00253   ModRefResult getModRefInfo(StoreInst *S, Value *P, unsigned Size);
00254   ModRefResult getModRefInfo(CallInst *C, Value *P, unsigned Size) {
00255     return getModRefInfo(CallSite(C), P, Size);
00256   }
00257   ModRefResult getModRefInfo(InvokeInst *I, Value *P, unsigned Size) {
00258     return getModRefInfo(CallSite(I), P, Size);
00259   }
00260   ModRefResult getModRefInfo(VAArgInst* I, Value* P, unsigned Size) {
00261     return AliasAnalysis::Mod;
00262   }
00263   ModRefResult getModRefInfo(Instruction *I, Value *P, unsigned Size) {
00264     switch (I->getOpcode()) {
00265     case Instruction::VAArg:  return getModRefInfo((VAArgInst*)I, P, Size);
00266     case Instruction::Load:   return getModRefInfo((LoadInst*)I, P, Size);
00267     case Instruction::Store:  return getModRefInfo((StoreInst*)I, P, Size);
00268     case Instruction::Call:   return getModRefInfo((CallInst*)I, P, Size);
00269     case Instruction::Invoke: return getModRefInfo((InvokeInst*)I, P, Size);
00270     default:                  return NoModRef;
00271     }
00272   }
00273 
00274   //===--------------------------------------------------------------------===//
00275   /// Higher level methods for querying mod/ref information.
00276   ///
00277 
00278   /// canBasicBlockModify - Return true if it is possible for execution of the
00279   /// specified basic block to modify the value pointed to by Ptr.
00280   ///
00281   bool canBasicBlockModify(const BasicBlock &BB, const Value *P, unsigned Size);
00282 
00283   /// canInstructionRangeModify - Return true if it is possible for the
00284   /// execution of the specified instructions to modify the value pointed to by
00285   /// Ptr.  The instructions to consider are all of the instructions in the
00286   /// range of [I1,I2] INCLUSIVE.  I1 and I2 must be in the same basic block.
00287   ///
00288   bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2,
00289                                  const Value *Ptr, unsigned Size);
00290 
00291   //===--------------------------------------------------------------------===//
00292   /// Methods that clients should call when they transform the program to allow
00293   /// alias analyses to update their internal data structures.  Note that these
00294   /// methods may be called on any instruction, regardless of whether or not
00295   /// they have pointer-analysis implications.
00296   ///
00297 
00298   /// deleteValue - This method should be called whenever an LLVM Value is
00299   /// deleted from the program, for example when an instruction is found to be
00300   /// redundant and is eliminated.
00301   ///
00302   virtual void deleteValue(Value *V);
00303 
00304   /// copyValue - This method should be used whenever a preexisting value in the
00305   /// program is copied or cloned, introducing a new value.  Note that analysis
00306   /// implementations should tolerate clients that use this method to introduce
00307   /// the same value multiple times: if the analysis already knows about a
00308   /// value, it should ignore the request.
00309   ///
00310   virtual void copyValue(Value *From, Value *To);
00311 
00312   /// replaceWithNewValue - This method is the obvious combination of the two
00313   /// above, and it provided as a helper to simplify client code.
00314   ///
00315   void replaceWithNewValue(Value *Old, Value *New) {
00316     copyValue(Old, New);
00317     deleteValue(Old);
00318   }
00319 };
00320 
00321 } // End llvm namespace
00322 
00323 // Because of the way .a files work, we must force the BasicAA implementation to
00324 // be pulled in if the AliasAnalysis header is included.  Otherwise we run
00325 // the risk of AliasAnalysis being used, but the default implementation not
00326 // being linked into the tool that uses it.
00327 FORCE_DEFINING_FILE_TO_BE_LINKED(AliasAnalysis)
00328 FORCE_DEFINING_FILE_TO_BE_LINKED(BasicAliasAnalysis)
00329 
00330 #endif