X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FAliasAnalysis.h;h=3ce4732eca12ddd0dc5259ea13811f00b0412a91;hb=b09c146b116359616f6cbd4c8b3328607e00ff42;hp=6333a5c85cb8b0dab09eb34a1d76e0573bbd52a9;hpb=babf11f249c7c6399c66f2567d4e7efa9c37a9c3;p=oota-llvm.git diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index 6333a5c85cb..3ce4732eca1 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -16,38 +16,52 @@ // which automatically provides functionality for the entire suite of client // APIs. // -// This API represents memory as a (Pointer, Size) pair. The Pointer component -// specifies the base memory address of the region, the Size specifies how large -// of an area is being queried. If Size is 0, two pointers only alias if they -// are exactly equal. If size is greater than zero, but small, the two pointers -// alias if the areas pointed to overlap. If the size is very large (ie, ~0U), -// then the two pointers alias if they may be pointing to components of the same -// memory object. Pointers that point to two completely different objects in -// memory never alias, regardless of the value of the Size component. +// This API identifies memory regions with the Location class. The pointer +// component specifies the base memory address of the region. The Size specifies +// the maximum size (in address units) of the memory region, or UnknownSize if +// the size is not known. The TBAA tag identifies the "type" of the memory +// reference; see the TypeBasedAliasAnalysis class for details. +// +// Some non-obvious details include: +// - Pointers that point to two completely different objects in memory never +// alias, regardless of the value of the Size component. +// - NoAlias doesn't imply inequal pointers. The most obvious example of this +// is two pointers to constant memory. Even if they are equal, constant +// memory is never stored to, so there will never be any dependencies. +// In this and other situations, the pointers may be both NoAlias and +// MustAlias at the same time. The current API can only return one result, +// though this is rarely a problem in practice. // //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H #define LLVM_ANALYSIS_ALIAS_ANALYSIS_H +#include "llvm/ADT/DenseMap.h" #include "llvm/Support/CallSite.h" -#include "llvm/System/IncludeFile.h" -#include namespace llvm { class LoadInst; class StoreInst; class VAArgInst; -class TargetData; +class DataLayout; +class TargetLibraryInfo; class Pass; class AnalysisUsage; +class MemTransferInst; +class MemIntrinsic; +class DominatorTree; class AliasAnalysis { protected: - const TargetData *TD; + const DataLayout *TD; + const TargetLibraryInfo *TLI; + +private: AliasAnalysis *AA; // Previous Alias Analysis to chain to. +protected: /// InitializeAliasAnalysis - Subclasses must call this method to initialize /// the AliasAnalysis interface before any other methods are called. This is /// typically called by the run* methods of these subclasses. This may be @@ -56,54 +70,156 @@ protected: void InitializeAliasAnalysis(Pass *P); /// getAnalysisUsage - All alias analysis implementations should invoke this - /// directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that - /// TargetData is required by the pass. + /// directly (using AliasAnalysis::getAnalysisUsage(AU)). virtual void getAnalysisUsage(AnalysisUsage &AU) const; public: static char ID; // Class identification, replacement for typeinfo - AliasAnalysis() : TD(0), AA(0) {} + AliasAnalysis() : TD(0), TLI(0), AA(0) {} virtual ~AliasAnalysis(); // We want to be subclassed - /// getTargetData - Every alias analysis implementation depends on the size of - /// data items in the current Target. This provides a uniform way to handle - /// it. + /// UnknownSize - This is a special value which can be used with the + /// size arguments in alias queries to indicate that the caller does not + /// know the sizes of the potential memory references. + static uint64_t const UnknownSize = ~UINT64_C(0); + + /// getDataLayout - Return a pointer to the current DataLayout object, or + /// null if no DataLayout object is available. /// - const TargetData &getTargetData() const { return *TD; } + const DataLayout *getDataLayout() const { return TD; } + + /// getTargetLibraryInfo - Return a pointer to the current TargetLibraryInfo + /// object, or null if no TargetLibraryInfo object is available. + /// + const TargetLibraryInfo *getTargetLibraryInfo() const { return TLI; } + + /// getTypeStoreSize - Return the DataLayout store size for the given type, + /// if known, or a conservative value otherwise. + /// + uint64_t getTypeStoreSize(Type *Ty); //===--------------------------------------------------------------------===// /// Alias Queries... /// + /// Location - A description of a memory location. + struct Location { + /// Ptr - The address of the start of the location. + const Value *Ptr; + /// Size - The maximum size of the location, in address-units, or + /// UnknownSize if the size is not known. Note that an unknown size does + /// not mean the pointer aliases the entire virtual address space, because + /// there are restrictions on stepping out of one object and into another. + /// See http://llvm.org/docs/LangRef.html#pointeraliasing + uint64_t Size; + /// TBAATag - The metadata node which describes the TBAA type of + /// the location, or null if there is no known unique tag. + const MDNode *TBAATag; + + explicit Location(const Value *P = 0, uint64_t S = UnknownSize, + const MDNode *N = 0) + : Ptr(P), Size(S), TBAATag(N) {} + + Location getWithNewPtr(const Value *NewPtr) const { + Location Copy(*this); + Copy.Ptr = NewPtr; + return Copy; + } + + Location getWithNewSize(uint64_t NewSize) const { + Location Copy(*this); + Copy.Size = NewSize; + return Copy; + } + + Location getWithoutTBAATag() const { + Location Copy(*this); + Copy.TBAATag = 0; + return Copy; + } + }; + + /// getLocation - Fill in Loc with information about the memory reference by + /// the given instruction. + Location getLocation(const LoadInst *LI); + Location getLocation(const StoreInst *SI); + Location getLocation(const VAArgInst *VI); + Location getLocation(const AtomicCmpXchgInst *CXI); + Location getLocation(const AtomicRMWInst *RMWI); + static Location getLocationForSource(const MemTransferInst *MTI); + static Location getLocationForDest(const MemIntrinsic *MI); + /// Alias analysis result - Either we know for sure that it does not alias, we /// know for sure it must alias, or we don't know anything: The two pointers /// _might_ alias. This enum is designed so you can do things like: /// if (AA.alias(P1, P2)) { ... } /// to check to see if two pointers might alias. /// - enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 }; + /// See docs/AliasAnalysis.html for more information on the specific meanings + /// of these values. + /// + enum AliasResult { + NoAlias = 0, ///< No dependencies. + MayAlias, ///< Anything goes. + PartialAlias, ///< Pointers differ, but pointees overlap. + MustAlias ///< Pointers are equal. + }; /// alias - The main low level interface to the alias analysis implementation. - /// Returns a Result indicating whether the two pointers are aliased to each - /// other. This is the interface that must be implemented by specific alias - /// analysis implementations. - /// - virtual AliasResult alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size); - - /// getMustAliases - If there are any pointers known that must alias this - /// pointer, return them now. This allows alias-set based alias analyses to - /// perform a form a value numbering (which is exposed by load-vn). If an - /// alias analysis supports this, it should ADD any must aliased pointers to - /// the specified vector. - /// - virtual void getMustAliases(Value *P, std::vector &RetVals); + /// Returns an AliasResult indicating whether the two pointers are aliased to + /// each other. This is the interface that must be implemented by specific + /// alias analysis implementations. + virtual AliasResult alias(const Location &LocA, const Location &LocB); + + /// alias - A convenience wrapper. + AliasResult alias(const Value *V1, uint64_t V1Size, + const Value *V2, uint64_t V2Size) { + return alias(Location(V1, V1Size), Location(V2, V2Size)); + } - /// pointsToConstantMemory - If the specified pointer is known to point into - /// constant global memory, return true. This allows disambiguation of store - /// instructions from constant pointers. - /// - virtual bool pointsToConstantMemory(const Value *P); + /// alias - A convenience wrapper. + AliasResult alias(const Value *V1, const Value *V2) { + return alias(V1, UnknownSize, V2, UnknownSize); + } + + /// isNoAlias - A trivial helper function to check to see if the specified + /// pointers are no-alias. + bool isNoAlias(const Location &LocA, const Location &LocB) { + return alias(LocA, LocB) == NoAlias; + } + + /// isNoAlias - A convenience wrapper. + bool isNoAlias(const Value *V1, uint64_t V1Size, + const Value *V2, uint64_t V2Size) { + return isNoAlias(Location(V1, V1Size), Location(V2, V2Size)); + } + + /// isNoAlias - A convenience wrapper. + bool isNoAlias(const Value *V1, const Value *V2) { + return isNoAlias(Location(V1), Location(V2)); + } + + /// isMustAlias - A convenience wrapper. + bool isMustAlias(const Location &LocA, const Location &LocB) { + return alias(LocA, LocB) == MustAlias; + } + + /// isMustAlias - A convenience wrapper. + bool isMustAlias(const Value *V1, const Value *V2) { + return alias(V1, 1, V2, 1) == MustAlias; + } + + /// pointsToConstantMemory - If the specified memory location is + /// known to be constant, return true. If OrLocal is true and the + /// specified memory location is known to be "local" (derived from + /// an alloca), return true. Otherwise return false. + virtual bool pointsToConstantMemory(const Location &Loc, + bool OrLocal = false); + + /// pointsToConstantMemory - A convenient wrapper. + bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { + return pointsToConstantMemory(Location(P), OrLocal); + } //===--------------------------------------------------------------------===// /// Simple mod/ref information... @@ -114,86 +230,56 @@ public: /// enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 }; + /// These values define additional bits used to define the + /// ModRefBehavior values. + enum { Nowhere = 0, ArgumentPointees = 4, Anywhere = 8 | ArgumentPointees }; /// ModRefBehavior - Summary of how a function affects memory in the program. /// Loads from constant globals are not considered memory accesses for this /// interface. Also, functions may freely modify stack space local to their /// invocation without having to report it through these interfaces. enum ModRefBehavior { - // DoesNotAccessMemory - This function does not perform any non-local loads - // or stores to memory. - // - // This property corresponds to the GCC 'const' attribute. - DoesNotAccessMemory, - - // AccessesArguments - This function accesses function arguments in - // non-volatile and well known ways, but does not access any other memory. - // - // Clients may call getArgumentAccesses to get specific information about - // how pointer arguments are used. - AccessesArguments, - - // AccessesArgumentsAndGlobals - This function has accesses function - // arguments and global variables in non-volatile and well-known ways, but - // does not access any other memory. - // - // Clients may call getArgumentAccesses to get specific information about - // how pointer arguments and globals are used. - AccessesArgumentsAndGlobals, - - // OnlyReadsMemory - This function does not perform any non-local stores or - // volatile loads, but may read from any memory location. - // - // This property corresponds to the GCC 'pure' attribute. - OnlyReadsMemory, - - // UnknownModRefBehavior - This indicates that the function could not be - // classified into one of the behaviors above. - UnknownModRefBehavior - }; + /// DoesNotAccessMemory - This function does not perform any non-local loads + /// or stores to memory. + /// + /// This property corresponds to the GCC 'const' attribute. + /// This property corresponds to the LLVM IR 'readnone' attribute. + /// This property corresponds to the IntrNoMem LLVM intrinsic flag. + DoesNotAccessMemory = Nowhere | NoModRef, + + /// OnlyReadsArgumentPointees - The only memory references in this function + /// (if it has any) are non-volatile loads from objects pointed to by its + /// pointer-typed arguments, with arbitrary offsets. + /// + /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag. + OnlyReadsArgumentPointees = ArgumentPointees | Ref, - /// PointerAccessInfo - This struct is used to return results for pointers, - /// globals, and the return value of a function. - struct PointerAccessInfo { - /// V - The value this record corresponds to. This may be an Argument for - /// the function, a GlobalVariable, or null, corresponding to the return - /// value for the function. - Value *V; + /// OnlyAccessesArgumentPointees - The only memory references in this + /// function (if it has any) are non-volatile loads and stores from objects + /// pointed to by its pointer-typed arguments, with arbitrary offsets. + /// + /// This property corresponds to the IntrReadWriteArgMem LLVM intrinsic flag. + OnlyAccessesArgumentPointees = ArgumentPointees | ModRef, - /// ModRefInfo - Whether the pointer is loaded or stored to/from. + /// OnlyReadsMemory - This function does not perform any non-local stores or + /// volatile loads, but may read from any memory location. /// - ModRefResult ModRefInfo; - - /// AccessType - Specific fine-grained access information for the argument. - /// If none of these classifications is general enough, the - /// getModRefBehavior method should not return AccessesArguments*. If a - /// record is not returned for a particular argument, the argument is never - /// dead and never dereferenced. - enum AccessType { - /// ScalarAccess - The pointer is dereferenced. - /// - ScalarAccess, - - /// ArrayAccess - The pointer is indexed through as an array of elements. - /// - ArrayAccess, - - /// ElementAccess ?? P->F only? - - /// CallsThrough - Indirect calls are made through the specified function - /// pointer. - CallsThrough - }; + /// This property corresponds to the GCC 'pure' attribute. + /// This property corresponds to the LLVM IR 'readonly' attribute. + /// This property corresponds to the IntrReadMem LLVM intrinsic flag. + OnlyReadsMemory = Anywhere | Ref, + + /// UnknownModRefBehavior - This indicates that the function could not be + /// classified into one of the behaviors above. + UnknownModRefBehavior = Anywhere | ModRef }; /// getModRefBehavior - Return the behavior when calling the given call site. - ModRefBehavior getModRefBehavior(CallSite cs, - std::vector *Info = 0); + virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); /// getModRefBehavior - Return the behavior when calling the given function. /// For use when the call site is not known. - ModRefBehavior getModRefBehavior(Function *F, - std::vector *Info = 0); + virtual ModRefBehavior getModRefBehavior(const Function *F); /// doesNotAccessMemory - If the specified call is known to never read or /// write memory, return true. If the call only reads from known-constant @@ -206,14 +292,14 @@ public: /// /// This property corresponds to the GCC 'const' attribute. /// - bool doesNotAccessMemory(CallSite cs) { - return getModRefBehavior(cs) == DoesNotAccessMemory; + bool doesNotAccessMemory(ImmutableCallSite CS) { + return getModRefBehavior(CS) == DoesNotAccessMemory; } /// doesNotAccessMemory - If the specified function is known to never read or /// write memory, return true. For use when the call site is not known. /// - bool doesNotAccessMemory(Function *F) { + bool doesNotAccessMemory(const Function *F) { return getModRefBehavior(F) == DoesNotAccessMemory; } @@ -226,76 +312,179 @@ public: /// /// This property corresponds to the GCC 'pure' attribute. /// - bool onlyReadsMemory(CallSite cs) { - ModRefBehavior MRB = getModRefBehavior(cs); - return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory; + bool onlyReadsMemory(ImmutableCallSite CS) { + return onlyReadsMemory(getModRefBehavior(CS)); } /// onlyReadsMemory - If the specified function is known to only read from /// non-volatile memory (or not access memory at all), return true. For use /// when the call site is not known. /// - bool onlyReadsMemory(Function *F) { - ModRefBehavior MRB = getModRefBehavior(F); - return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory; + bool onlyReadsMemory(const Function *F) { + return onlyReadsMemory(getModRefBehavior(F)); } + /// onlyReadsMemory - Return true if functions with the specified behavior are + /// known to only read from non-volatile memory (or not access memory at all). + /// + static bool onlyReadsMemory(ModRefBehavior MRB) { + return !(MRB & Mod); + } + + /// onlyAccessesArgPointees - Return true if functions with the specified + /// behavior are known to read and write at most from objects pointed to by + /// their pointer-typed arguments (with arbitrary offsets). + /// + static bool onlyAccessesArgPointees(ModRefBehavior MRB) { + return !(MRB & Anywhere & ~ArgumentPointees); + } + + /// doesAccessArgPointees - Return true if functions with the specified + /// behavior are known to potentially read or write from objects pointed + /// to be their pointer-typed arguments (with arbitrary offsets). + /// + static bool doesAccessArgPointees(ModRefBehavior MRB) { + return (MRB & ModRef) && (MRB & ArgumentPointees); + } /// getModRefInfo - Return information about whether or not an instruction may - /// read or write memory specified by the pointer operand. An instruction + /// read or write the specified memory location. An instruction /// that doesn't read or write memory may be trivially LICM'd for example. + ModRefResult getModRefInfo(const Instruction *I, + const Location &Loc) { + switch (I->getOpcode()) { + case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc); + case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc); + case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc); + case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc); + case Instruction::AtomicCmpXchg: + return getModRefInfo((const AtomicCmpXchgInst*)I, Loc); + case Instruction::AtomicRMW: + return getModRefInfo((const AtomicRMWInst*)I, Loc); + case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc); + case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc); + default: return NoModRef; + } + } - /// getModRefInfo (for call sites) - Return whether information about whether - /// a particular call site modifies or reads the memory specified by the - /// pointer. - /// - virtual ModRefResult getModRefInfo(CallSite cs, Value *P, unsigned Size); + /// getModRefInfo - A convenience wrapper. + ModRefResult getModRefInfo(const Instruction *I, + const Value *P, uint64_t Size) { + return getModRefInfo(I, Location(P, Size)); + } - /// getModRefInfo - Return information about whether two call sites may refer - /// to the same set of memory locations. This function 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. - /// - virtual ModRefResult getModRefInfo(CallSite cs1, CallSite cs2); + /// getModRefInfo (for call sites) - Return information about whether + /// a particular call site modifies or reads the specified memory location. + virtual ModRefResult getModRefInfo(ImmutableCallSite CS, + const Location &Loc); - /// hasNoModRefInfoForCalls - Return true if the analysis has no mod/ref - /// information for pairs of function calls (other than "pure" and "const" - /// functions). This can be used by clients to avoid many pointless queries. - /// Remember that if you override this and chain to another analysis, you must - /// make sure that it doesn't have mod/ref info either. - /// - virtual bool hasNoModRefInfoForCalls() const; + /// getModRefInfo (for call sites) - A convenience wrapper. + ModRefResult getModRefInfo(ImmutableCallSite CS, + const Value *P, uint64_t Size) { + return getModRefInfo(CS, Location(P, Size)); + } -protected: - /// getModRefBehavior - Return the behavior of the specified function if - /// called from the specified call site. The call site may be null in which - /// case the most generic behavior of this function should be returned. - virtual ModRefBehavior getModRefBehavior(Function *F, CallSite cs, - std::vector *Info = 0); + /// getModRefInfo (for calls) - Return information about whether + /// a particular call modifies or reads the specified memory location. + ModRefResult getModRefInfo(const CallInst *C, const Location &Loc) { + return getModRefInfo(ImmutableCallSite(C), Loc); + } -public: - /// Convenience functions... - ModRefResult getModRefInfo(LoadInst *L, Value *P, unsigned Size); - ModRefResult getModRefInfo(StoreInst *S, Value *P, unsigned Size); - ModRefResult getModRefInfo(CallInst *C, Value *P, unsigned Size) { - return getModRefInfo(CallSite(C), P, Size); + /// getModRefInfo (for calls) - A convenience wrapper. + ModRefResult getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) { + return getModRefInfo(C, Location(P, Size)); } - ModRefResult getModRefInfo(InvokeInst *I, Value *P, unsigned Size) { - return getModRefInfo(CallSite(I), P, Size); + + /// getModRefInfo (for invokes) - Return information about whether + /// a particular invoke modifies or reads the specified memory location. + ModRefResult getModRefInfo(const InvokeInst *I, + const Location &Loc) { + return getModRefInfo(ImmutableCallSite(I), Loc); } - ModRefResult getModRefInfo(VAArgInst* I, Value* P, unsigned Size) { - return AliasAnalysis::ModRef; + + /// getModRefInfo (for invokes) - A convenience wrapper. + ModRefResult getModRefInfo(const InvokeInst *I, + const Value *P, uint64_t Size) { + return getModRefInfo(I, Location(P, Size)); } - ModRefResult getModRefInfo(Instruction *I, Value *P, unsigned Size) { - switch (I->getOpcode()) { - case Instruction::VAArg: return getModRefInfo((VAArgInst*)I, P, Size); - case Instruction::Load: return getModRefInfo((LoadInst*)I, P, Size); - case Instruction::Store: return getModRefInfo((StoreInst*)I, P, Size); - case Instruction::Call: return getModRefInfo((CallInst*)I, P, Size); - case Instruction::Invoke: return getModRefInfo((InvokeInst*)I, P, Size); - default: return NoModRef; - } + + /// getModRefInfo (for loads) - Return information about whether + /// a particular load modifies or reads the specified memory location. + ModRefResult getModRefInfo(const LoadInst *L, const Location &Loc); + + /// getModRefInfo (for loads) - A convenience wrapper. + ModRefResult getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) { + return getModRefInfo(L, Location(P, Size)); + } + + /// getModRefInfo (for stores) - Return information about whether + /// a particular store modifies or reads the specified memory location. + ModRefResult getModRefInfo(const StoreInst *S, const Location &Loc); + + /// getModRefInfo (for stores) - A convenience wrapper. + ModRefResult getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size){ + return getModRefInfo(S, Location(P, Size)); + } + + /// getModRefInfo (for fences) - Return information about whether + /// a particular store modifies or reads the specified memory location. + ModRefResult getModRefInfo(const FenceInst *S, const Location &Loc) { + // Conservatively correct. (We could possibly be a bit smarter if + // Loc is a alloca that doesn't escape.) + return ModRef; + } + + /// getModRefInfo (for fences) - A convenience wrapper. + ModRefResult getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size){ + return getModRefInfo(S, Location(P, Size)); + } + + /// getModRefInfo (for cmpxchges) - Return information about whether + /// a particular cmpxchg modifies or reads the specified memory location. + ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc); + + /// getModRefInfo (for cmpxchges) - A convenience wrapper. + ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX, + const Value *P, unsigned Size) { + return getModRefInfo(CX, Location(P, Size)); + } + + /// getModRefInfo (for atomicrmws) - Return information about whether + /// a particular atomicrmw modifies or reads the specified memory location. + ModRefResult getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc); + + /// getModRefInfo (for atomicrmws) - A convenience wrapper. + ModRefResult getModRefInfo(const AtomicRMWInst *RMW, + const Value *P, unsigned Size) { + return getModRefInfo(RMW, Location(P, Size)); + } + + /// getModRefInfo (for va_args) - Return information about whether + /// a particular va_arg modifies or reads the specified memory location. + ModRefResult getModRefInfo(const VAArgInst* I, const Location &Loc); + + /// getModRefInfo (for va_args) - A convenience wrapper. + ModRefResult getModRefInfo(const VAArgInst* I, const Value* P, uint64_t Size){ + return getModRefInfo(I, Location(P, Size)); + } + + /// getModRefInfo - Return information about whether two call sites may refer + /// to the same set of memory locations. See + /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo + /// for details. + virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, + ImmutableCallSite CS2); + + /// callCapturesBefore - Return information about whether a particular call + /// site modifies or reads the specified memory location. + ModRefResult callCapturesBefore(const Instruction *I, + const AliasAnalysis::Location &MemLoc, + DominatorTree *DT); + + /// callCapturesBefore - A convenience wrapper. + ModRefResult callCapturesBefore(const Instruction *I, const Value *P, + uint64_t Size, DominatorTree *DT) { + return callCapturesBefore(I, Location(P, Size), DT); } //===--------------------------------------------------------------------===// @@ -304,16 +493,25 @@ public: /// canBasicBlockModify - Return true if it is possible for execution of the /// specified basic block to modify the value pointed to by Ptr. - /// - bool canBasicBlockModify(const BasicBlock &BB, const Value *P, unsigned Size); + bool canBasicBlockModify(const BasicBlock &BB, const Location &Loc); + + /// canBasicBlockModify - A convenience wrapper. + bool canBasicBlockModify(const BasicBlock &BB, const Value *P, uint64_t Size){ + return canBasicBlockModify(BB, Location(P, Size)); + } /// canInstructionRangeModify - Return true if it is possible for the /// execution of the specified instructions to modify the value pointed to by /// Ptr. The instructions to consider are all of the instructions in the /// range of [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. - /// bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, - const Value *Ptr, unsigned Size); + const Location &Loc); + + /// canInstructionRangeModify - A convenience wrapper. + bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, + const Value *Ptr, uint64_t Size) { + return canInstructionRangeModify(I1, I2, Location(Ptr, Size)); + } //===--------------------------------------------------------------------===// /// Methods that clients should call when they transform the program to allow @@ -336,6 +534,17 @@ public: /// virtual void copyValue(Value *From, Value *To); + /// addEscapingUse - This method should be used whenever an escaping use is + /// added to a pointer value. Analysis implementations may either return + /// conservative responses for that value in the future, or may recompute + /// some or all internal state to continue providing precise responses. + /// + /// Escaping uses are considered by anything _except_ the following: + /// - GEPs or bitcasts of the pointer + /// - Loads through the pointer + /// - Stores through (but not of) the pointer + virtual void addEscapingUse(Use &U); + /// replaceWithNewValue - This method is the obvious combination of the two /// above, and it provided as a helper to simplify client code. /// @@ -345,13 +554,50 @@ public: } }; -} // End llvm namespace +// Specialize DenseMapInfo for Location. +template<> +struct DenseMapInfo { + static inline AliasAnalysis::Location getEmptyKey() { + return + AliasAnalysis::Location(DenseMapInfo::getEmptyKey(), + 0, 0); + } + static inline AliasAnalysis::Location getTombstoneKey() { + return + AliasAnalysis::Location(DenseMapInfo::getTombstoneKey(), + 0, 0); + } + static unsigned getHashValue(const AliasAnalysis::Location &Val) { + return DenseMapInfo::getHashValue(Val.Ptr) ^ + DenseMapInfo::getHashValue(Val.Size) ^ + DenseMapInfo::getHashValue(Val.TBAATag); + } + static bool isEqual(const AliasAnalysis::Location &LHS, + const AliasAnalysis::Location &RHS) { + return LHS.Ptr == RHS.Ptr && + LHS.Size == RHS.Size && + LHS.TBAATag == RHS.TBAATag; + } +}; + +/// isNoAliasCall - Return true if this pointer is returned by a noalias +/// function. +bool isNoAliasCall(const Value *V); -// Because of the way .a files work, we must force the BasicAA implementation to -// be pulled in if the AliasAnalysis header is included. Otherwise we run -// the risk of AliasAnalysis being used, but the default implementation not -// being linked into the tool that uses it. -FORCE_DEFINING_FILE_TO_BE_LINKED(AliasAnalysis) -FORCE_DEFINING_FILE_TO_BE_LINKED(BasicAliasAnalysis) +/// isIdentifiedObject - Return true if this pointer refers to a distinct and +/// identifiable object. This returns true for: +/// Global Variables and Functions (but not Global Aliases) +/// Allocas +/// ByVal and NoAlias Arguments +/// NoAlias returns (e.g. calls to malloc) +/// +bool isIdentifiedObject(const Value *V); + +/// isKnownNonNull - Return true if this pointer couldn't possibly be null by +/// its definition. This returns true for allocas, non-extern-weak globals and +/// byval arguments. +bool isKnownNonNull(const Value *V); + +} // End llvm namespace #endif