X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FAliasAnalysis.h;h=3ce4732eca12ddd0dc5259ea13811f00b0412a91;hb=b09c146b116359616f6cbd4c8b3328607e00ff42;hp=8fd6d2fc2c35d13084b1da3570decd87f295091a;hpb=3da848bbda62b25c12335998aaa44ab361f0bf15;p=oota-llvm.git diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index 8fd6d2fc2c3..3ce4732eca1 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -16,33 +16,47 @@ // 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, or UnknownSize if the size is not known. -// 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. @@ -61,7 +75,7 @@ protected: 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 /// UnknownSize - This is a special value which can be used with the @@ -69,15 +83,20 @@ public: /// know the sizes of the potential memory references. static uint64_t const UnknownSize = ~UINT64_C(0); - /// getTargetData - Return a pointer to the current TargetData object, or - /// null if no TargetData object is available. + /// getDataLayout - Return a pointer to the current DataLayout object, or + /// null if no DataLayout object is available. + /// + const DataLayout *getDataLayout() const { return TD; } + + /// getTargetLibraryInfo - Return a pointer to the current TargetLibraryInfo + /// object, or null if no TargetLibraryInfo object is available. /// - const TargetData *getTargetData() const { return TD; } + const TargetLibraryInfo *getTargetLibraryInfo() const { return TLI; } - /// getTypeStoreSize - Return the TargetData store size for the given type, + /// getTypeStoreSize - Return the DataLayout store size for the given type, /// if known, or a conservative value otherwise. /// - uint64_t getTypeStoreSize(const Type *Ty); + uint64_t getTypeStoreSize(Type *Ty); //===--------------------------------------------------------------------===// /// Alias Queries... @@ -87,14 +106,17 @@ public: struct Location { /// Ptr - The address of the start of the location. const Value *Ptr; - /// Size - The size of the location. + /// 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 (unique) tag. + /// the location, or null if there is no known unique tag. const MDNode *TBAATag; - explicit Location(const Value *P = 0, - uint64_t S = UnknownSize, + explicit Location(const Value *P = 0, uint64_t S = UnknownSize, const MDNode *N = 0) : Ptr(P), Size(S), TBAATag(N) {} @@ -104,6 +126,12 @@ public: 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; @@ -111,6 +139,16 @@ public: } }; + /// 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: @@ -120,12 +158,17 @@ public: /// See docs/AliasAnalysis.html for more information on the specific meanings /// of these values. /// - enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 }; + 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. + /// 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. @@ -150,16 +193,32 @@ public: 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; + } - /// pointsToConstantMemory - If the specified memory location is known to be - /// constant, return true. This allows disambiguation of store - /// instructions from constant pointers. - /// - virtual bool pointsToConstantMemory(const Location &Loc); + /// 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) { - return pointsToConstantMemory(Location(P)); + bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { + return pointsToConstantMemory(Location(P), OrLocal); } //===--------------------------------------------------------------------===// @@ -171,36 +230,48 @@ 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 well - // known (possibly volatile) ways, but does not access any other memory. - AccessesArguments, - - // AccessesArgumentsAndGlobals - This function has accesses function - // arguments and global variables well known (possibly volatile) ways, but - // does not access any other memory. - 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, + + /// 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, + + /// 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. + /// 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. @@ -210,11 +281,6 @@ public: /// For use when the call site is not known. virtual ModRefBehavior getModRefBehavior(const Function *F); - /// getIntrinsicModRefBehavior - Return the modref behavior of the intrinsic - /// with the given id. Most clients won't need this, because the regular - /// getModRefBehavior incorporates this information. - static ModRefBehavior getIntrinsicModRefBehavior(unsigned iid); - /// doesNotAccessMemory - If the specified call is known to never read or /// write memory, return true. If the call only reads from known-constant /// memory, it is also legal to return true. Calls that unwind the stack @@ -247,8 +313,7 @@ public: /// This property corresponds to the GCC 'pure' attribute. /// bool onlyReadsMemory(ImmutableCallSite CS) { - ModRefBehavior MRB = getModRefBehavior(CS); - return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory; + return onlyReadsMemory(getModRefBehavior(CS)); } /// onlyReadsMemory - If the specified function is known to only read from @@ -256,10 +321,31 @@ public: /// when the call site is not known. /// bool onlyReadsMemory(const Function *F) { - ModRefBehavior MRB = getModRefBehavior(F); - return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory; + 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 the specified memory location. An instruction @@ -270,6 +356,11 @@ public: 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; @@ -282,7 +373,7 @@ public: return getModRefInfo(I, Location(P, Size)); } - /// getModRefInfo (for call sites) - Return whether information about whether + /// 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); @@ -293,7 +384,7 @@ public: return getModRefInfo(CS, Location(P, Size)); } - /// getModRefInfo (for calls) - Return whether information about whether + /// 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); @@ -304,7 +395,7 @@ public: return getModRefInfo(C, Location(P, Size)); } - /// getModRefInfo (for invokes) - Return whether information about whether + /// 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) { @@ -317,7 +408,7 @@ public: return getModRefInfo(I, Location(P, Size)); } - /// getModRefInfo (for loads) - Return whether information about whether + /// 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); @@ -326,21 +417,54 @@ public: return getModRefInfo(L, Location(P, Size)); } - /// getModRefInfo (for stores) - Return whether information about whether + /// 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) { + 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 va_args) - Return whether information about whether + /// 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) { + ModRefResult getModRefInfo(const VAArgInst* I, const Value* P, uint64_t Size){ return getModRefInfo(I, Location(P, Size)); } @@ -351,6 +475,18 @@ public: 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); + } + //===--------------------------------------------------------------------===// /// Higher level methods for querying mod/ref information. /// @@ -398,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. /// @@ -407,6 +554,32 @@ public: } }; +// 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); @@ -414,19 +587,17 @@ bool isNoAliasCall(const Value *V); /// 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 and Mallocs +/// Allocas /// ByVal and NoAlias Arguments -/// NoAlias returns +/// NoAlias returns (e.g. calls to malloc) /// bool isIdentifiedObject(const Value *V); -} // End llvm namespace +/// 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); -// 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) +} // End llvm namespace #endif