X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FAliasAnalysis.h;h=7f037fb5e813d8c967c596e899e55b6376dec38e;hb=cf0db29df20d9c665da7e82bb261bdd7cf7f1b2b;hp=885286604ccbe20db9bc6eeccf5214a119a3c3e0;hpb=5508cfd02ca7d568782e84b9f6fc99ad1dcc4947;p=oota-llvm.git diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index 885286604cc..7f037fb5e81 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -16,11 +16,12 @@ // which automatically provides functionality for the entire suite of client // APIs. // -// This API identifies memory regions with the Location class. The pointer +// This API identifies memory regions with the MemoryLocation 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. +// the maximum size (in address units) of the memory region, or +// MemoryLocation::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 @@ -39,6 +40,8 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/IR/CallSite.h" +#include "llvm/IR/Metadata.h" +#include "llvm/Analysis/MemoryLocation.h" namespace llvm { @@ -67,7 +70,7 @@ protected: /// typically called by the run* methods of these subclasses. This may be /// called multiple times. /// - void InitializeAliasAnalysis(Pass *P); + void InitializeAliasAnalysis(Pass *P, const DataLayout *DL); /// getAnalysisUsage - All alias analysis implementations should invoke this /// directly (using AliasAnalysis::getAnalysisUsage(AU)). @@ -78,16 +81,6 @@ public: AliasAnalysis() : DL(nullptr), TLI(nullptr), AA(nullptr) {} virtual ~AliasAnalysis(); // We want to be subclassed - /// 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 DataLayout *getDataLayout() const { return DL; } - /// getTargetLibraryInfo - Return a pointer to the current TargetLibraryInfo /// object, or null if no TargetLibraryInfo object is available. /// @@ -102,53 +95,6 @@ public: /// 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 = nullptr, uint64_t S = UnknownSize, - const MDNode *N = nullptr) - : 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 = nullptr; - 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: @@ -169,38 +115,40 @@ public: /// 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); + virtual AliasResult alias(const MemoryLocation &LocA, + const MemoryLocation &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)); + return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); } /// alias - A convenience wrapper. AliasResult alias(const Value *V1, const Value *V2) { - return alias(V1, UnknownSize, V2, UnknownSize); + return alias(V1, MemoryLocation::UnknownSize, V2, + MemoryLocation::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) { + bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &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)); + return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); } /// isNoAlias - A convenience wrapper. bool isNoAlias(const Value *V1, const Value *V2) { - return isNoAlias(Location(V1), Location(V2)); + return isNoAlias(MemoryLocation(V1), MemoryLocation(V2)); } /// isMustAlias - A convenience wrapper. - bool isMustAlias(const Location &LocA, const Location &LocB) { + bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { return alias(LocA, LocB) == MustAlias; } @@ -213,12 +161,12 @@ public: /// 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, + virtual bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false); /// pointsToConstantMemory - A convenient wrapper. bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { - return pointsToConstantMemory(Location(P), OrLocal); + return pointsToConstantMemory(MemoryLocation(P), OrLocal); } //===--------------------------------------------------------------------===// @@ -274,6 +222,13 @@ public: UnknownModRefBehavior = Anywhere | ModRef }; + /// Get the ModRef info associated with a pointer argument of a callsite. The + /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note + /// that these bits do not necessarily account for the overall behavior of + /// the function, but rather only provide additional per-argument + /// information. + virtual ModRefResult getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx); + /// getModRefBehavior - Return the behavior when calling the given call site. virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); @@ -347,11 +302,28 @@ public: return (MRB & ModRef) && (MRB & ArgumentPointees); } + /// getModRefInfo - Return information about whether or not an + /// instruction may read or write memory (without regard to a + /// specific location) + ModRefResult getModRefInfo(const Instruction *I) { + if (auto CS = ImmutableCallSite(I)) { + auto MRB = getModRefBehavior(CS); + if (MRB & ModRef) + return ModRef; + else if (MRB & Ref) + return Ref; + else if (MRB & Mod) + return Mod; + return NoModRef; + } + + return getModRefInfo(I, MemoryLocation()); + } + /// getModRefInfo - Return information about whether or not an instruction may /// 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) { + ModRefResult getModRefInfo(const Instruction *I, const MemoryLocation &Loc) { switch (I->getOpcode()) { case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc); case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc); @@ -370,65 +342,64 @@ public: /// getModRefInfo - A convenience wrapper. ModRefResult getModRefInfo(const Instruction *I, const Value *P, uint64_t Size) { - return getModRefInfo(I, Location(P, Size)); + return getModRefInfo(I, MemoryLocation(P, Size)); } /// 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); + const MemoryLocation &Loc); /// getModRefInfo (for call sites) - A convenience wrapper. ModRefResult getModRefInfo(ImmutableCallSite CS, const Value *P, uint64_t Size) { - return getModRefInfo(CS, Location(P, Size)); + return getModRefInfo(CS, MemoryLocation(P, Size)); } /// 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) { + ModRefResult getModRefInfo(const CallInst *C, const MemoryLocation &Loc) { return getModRefInfo(ImmutableCallSite(C), Loc); } /// getModRefInfo (for calls) - A convenience wrapper. ModRefResult getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) { - return getModRefInfo(C, Location(P, Size)); + return getModRefInfo(C, MemoryLocation(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) { + ModRefResult getModRefInfo(const InvokeInst *I, const MemoryLocation &Loc) { return getModRefInfo(ImmutableCallSite(I), Loc); } /// getModRefInfo (for invokes) - A convenience wrapper. ModRefResult getModRefInfo(const InvokeInst *I, const Value *P, uint64_t Size) { - return getModRefInfo(I, Location(P, Size)); + return getModRefInfo(I, MemoryLocation(P, Size)); } /// 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); + ModRefResult getModRefInfo(const LoadInst *L, const MemoryLocation &Loc); /// getModRefInfo (for loads) - A convenience wrapper. ModRefResult getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) { - return getModRefInfo(L, Location(P, Size)); + return getModRefInfo(L, MemoryLocation(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); + ModRefResult getModRefInfo(const StoreInst *S, const MemoryLocation &Loc); /// getModRefInfo (for stores) - A convenience wrapper. ModRefResult getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size){ - return getModRefInfo(S, Location(P, Size)); + return getModRefInfo(S, MemoryLocation(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) { + ModRefResult getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) { // Conservatively correct. (We could possibly be a bit smarter if // Loc is a alloca that doesn't escape.) return ModRef; @@ -436,37 +407,43 @@ public: /// getModRefInfo (for fences) - A convenience wrapper. ModRefResult getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size){ - return getModRefInfo(S, Location(P, Size)); + return getModRefInfo(S, MemoryLocation(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); + ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX, + const MemoryLocation &Loc); /// getModRefInfo (for cmpxchges) - A convenience wrapper. ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P, unsigned Size) { - return getModRefInfo(CX, Location(P, Size)); + return getModRefInfo(CX, MemoryLocation(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); + ModRefResult getModRefInfo(const AtomicRMWInst *RMW, + const MemoryLocation &Loc); /// getModRefInfo (for atomicrmws) - A convenience wrapper. ModRefResult getModRefInfo(const AtomicRMWInst *RMW, const Value *P, unsigned Size) { - return getModRefInfo(RMW, Location(P, Size)); + return getModRefInfo(RMW, MemoryLocation(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); + ModRefResult getModRefInfo(const VAArgInst *I, const MemoryLocation &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)); + return getModRefInfo(I, MemoryLocation(P, Size)); } + /// getModRefInfo - Return information about whether a call and an instruction + /// may refer to the same memory locations. + ModRefResult getModRefInfo(Instruction *I, + ImmutableCallSite Call); /// getModRefInfo - Return information about whether two call sites may refer /// to the same set of memory locations. See @@ -478,13 +455,13 @@ public: /// 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, + const MemoryLocation &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); + return callCapturesBefore(I, MemoryLocation(P, Size), DT); } //===--------------------------------------------------------------------===// @@ -492,25 +469,28 @@ 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 Location &Loc); + /// specified basic block to modify the location Loc. + bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc); /// canBasicBlockModify - A convenience wrapper. bool canBasicBlockModify(const BasicBlock &BB, const Value *P, uint64_t Size){ - return canBasicBlockModify(BB, Location(P, Size)); + return canBasicBlockModify(BB, MemoryLocation(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 Location &Loc); + /// canInstructionRangeModRef - Return true if it is possible for the + /// execution of the specified instructions to mod\ref (according to the + /// mode) the location Loc. 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 canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, + const MemoryLocation &Loc, + const ModRefResult Mode); - /// 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)); + /// canInstructionRangeModRef - A convenience wrapper. + bool canInstructionRangeModRef(const Instruction &I1, + const Instruction &I2, const Value *Ptr, + uint64_t Size, const ModRefResult Mode) { + return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode); } //===--------------------------------------------------------------------===// @@ -554,32 +534,6 @@ public: } }; -// Specialize DenseMapInfo for Location. -template<> -struct DenseMapInfo { - static inline AliasAnalysis::Location getEmptyKey() { - return - AliasAnalysis::Location(DenseMapInfo::getEmptyKey(), - 0, nullptr); - } - static inline AliasAnalysis::Location getTombstoneKey() { - return - AliasAnalysis::Location(DenseMapInfo::getTombstoneKey(), - 0, nullptr); - } - 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); @@ -597,6 +551,13 @@ bool isNoAliasArgument(const Value *V); /// bool isIdentifiedObject(const Value *V); -} // End llvm namespace +/// isIdentifiedFunctionLocal - Return true if V is umabigously identified +/// at the function-level. Different IdentifiedFunctionLocals can't alias. +/// Further, an IdentifiedFunctionLocal can not alias with any function +/// arguments other than itself, which is not necessarily true for +/// IdentifiedObjects. +bool isIdentifiedFunctionLocal(const Value *V); + +} // namespace llvm #endif