X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FAliasSetTracker.h;h=5adfb4f74d63f3b1251987cac38d2097977d38a0;hb=9146833fa313fb0339355f9ca8b63122dd73ba88;hp=09f12ad281ac6087e00f9bcde56a1606e6b46ec7;hpb=4bbf4ee1491637c247e195e19e3e4a8ee5ad72fa;p=oota-llvm.git diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index 09f12ad281a..5adfb4f74d6 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -17,16 +17,16 @@ #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H #define LLVM_ANALYSIS_ALIASSETTRACKER_H -#include "llvm/Support/CallSite.h" -#include "llvm/Support/ValueHandle.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/ilist.h" #include "llvm/ADT/ilist_node.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/IR/Metadata.h" +#include "llvm/IR/ValueHandle.h" #include namespace llvm { -class AliasAnalysis; class LoadInst; class StoreInst; class VAArgInst; @@ -40,26 +40,45 @@ class AliasSet : public ilist_node { Value *Val; // The pointer this record corresponds to. PointerRec **PrevInList, *NextInList; AliasSet *AS; - unsigned Size; + uint64_t Size; + AAMDNodes AAInfo; public: PointerRec(Value *V) - : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0) {} + : Val(V), PrevInList(nullptr), NextInList(nullptr), AS(nullptr), Size(0), + AAInfo(DenseMapInfo::getEmptyKey()) {} Value *getValue() const { return Val; } PointerRec *getNext() const { return NextInList; } - bool hasAliasSet() const { return AS != 0; } + bool hasAliasSet() const { return AS != nullptr; } PointerRec** setPrevInList(PointerRec **PIL) { PrevInList = PIL; return &NextInList; } - void updateSize(unsigned NewSize) { + void updateSizeAndAAInfo(uint64_t NewSize, const AAMDNodes &NewAAInfo) { if (NewSize > Size) Size = NewSize; + + if (AAInfo == DenseMapInfo::getEmptyKey()) + // We don't have a AAInfo yet. Set it to NewAAInfo. + AAInfo = NewAAInfo; + else if (AAInfo != NewAAInfo) + // NewAAInfo conflicts with AAInfo. + AAInfo = DenseMapInfo::getTombstoneKey(); } - unsigned getSize() const { return Size; } + uint64_t getSize() const { return Size; } + + /// getAAInfo - Return the AAInfo, or null if there is no + /// information or conflicting information. + AAMDNodes getAAInfo() const { + // If we have missing or conflicting AAInfo, return null. + if (AAInfo == DenseMapInfo::getEmptyKey() || + AAInfo == DenseMapInfo::getTombstoneKey()) + return AAMDNodes(); + return AAInfo; + } AliasSet *getAliasSet(AliasSetTracker &AST) { assert(AS && "No AliasSet yet!"); @@ -73,7 +92,7 @@ class AliasSet : public ilist_node { } void setAliasSet(AliasSet *as) { - assert(AS == 0 && "Already have an alias set!"); + assert(!AS && "Already have an alias set!"); AS = as; } @@ -82,7 +101,7 @@ class AliasSet : public ilist_node { *PrevInList = NextInList; if (AS->PtrListEnd == &NextInList) { AS->PtrListEnd = PrevInList; - assert(*AS->PtrListEnd == 0 && "List not terminated right!"); + assert(*AS->PtrListEnd == nullptr && "List not terminated right!"); } delete this; } @@ -90,32 +109,38 @@ class AliasSet : public ilist_node { PointerRec *PtrList, **PtrListEnd; // Doubly linked list of nodes. AliasSet *Forward; // Forwarding pointer. - AliasSet *Next, *Prev; // Doubly linked list of AliasSets. - std::vector CallSites; // All calls & invokes in this alias set. + // All instructions without a specific address in this alias set. + std::vector > UnknownInsts; // RefCount - Number of nodes pointing to this AliasSet plus the number of // AliasSets forwarding to it. unsigned RefCount : 28; - /// AccessType - Keep track of whether this alias set merely refers to the - /// locations of memory, whether it modifies the memory, or whether it does - /// both. The lattice goes from "NoModRef" to either Refs or Mods, then to - /// ModRef as necessary. + /// The kinds of access this alias set models. /// - enum AccessType { - NoModRef = 0, Refs = 1, // Ref = bit 1 - Mods = 2, ModRef = 3 // Mod = bit 2 + /// We keep track of whether this alias set merely refers to the locations of + /// memory (and not any particular access), whether it modifies or references + /// the memory, or whether it does both. The lattice goes from "NoAccess" to + /// either RefAccess or ModAccess, then to ModRefAccess as necessary. + enum AccessLattice { + NoAccess = 0, + RefAccess = 1, + ModAccess = 2, + ModRefAccess = RefAccess | ModAccess }; - unsigned AccessTy : 2; + unsigned Access : 2; - /// AliasType - Keep track the relationships between the pointers in the set. - /// Lattice goes from MustAlias to MayAlias. + /// The kind of alias relationship between pointers of the set. /// - enum AliasType { - MustAlias = 0, MayAlias = 1 + /// These represent conservatively correct alias results between any members + /// of the set. We represent these independently of the values of alias + /// results in order to pack it into a single bit. Lattice goes from + /// MustAlias to MayAlias. + enum AliasLattice { + SetMustAlias = 0, SetMayAlias = 1 }; - unsigned AliasTy : 1; + unsigned Alias : 1; // Volatile - True if this alias set contains volatile loads or stores. bool Volatile : 1; @@ -127,12 +152,17 @@ class AliasSet : public ilist_node { removeFromTracker(AST); } + Instruction *getUnknownInst(unsigned i) const { + assert(i < UnknownInsts.size()); + return UnknownInsts[i]; + } + public: /// Accessors... - bool isRef() const { return AccessTy & Refs; } - bool isMod() const { return AccessTy & Mods; } - bool isMustAlias() const { return AliasTy == MustAlias; } - bool isMayAlias() const { return AliasTy == MayAlias; } + bool isRef() const { return Access & RefAccess; } + bool isMod() const { return Access & ModAccess; } + bool isMustAlias() const { return Alias == SetMustAlias; } + bool isMayAlias() const { return Alias == SetMayAlias; } // isVolatile - Return true if this alias set contains volatile loads or // stores. @@ -151,7 +181,7 @@ public: class iterator; iterator begin() const { return iterator(PtrList); } iterator end() const { return iterator(); } - bool empty() const { return PtrList == 0; } + bool empty() const { return PtrList == nullptr; } void print(raw_ostream &OS) const; void dump() const; @@ -161,18 +191,13 @@ public: PointerRec, ptrdiff_t> { PointerRec *CurNode; public: - explicit iterator(PointerRec *CN = 0) : CurNode(CN) {} + explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {} bool operator==(const iterator& x) const { return CurNode == x.CurNode; } bool operator!=(const iterator& x) const { return !operator==(x); } - const iterator &operator=(const iterator &I) { - CurNode = I.CurNode; - return *this; - } - value_type &operator*() const { assert(CurNode && "Dereferencing AliasSet.end()!"); return *CurNode; @@ -180,7 +205,8 @@ public: value_type *operator->() const { return &operator*(); } Value *getPointer() const { return CurNode->getValue(); } - unsigned getSize() const { return CurNode->getSize(); } + uint64_t getSize() const { return CurNode->getSize(); } + AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); } iterator& operator++() { // Preincrement assert(CurNode && "Advancing past AliasSet.end()!"); @@ -196,12 +222,13 @@ private: // Can only be created by AliasSetTracker. Also, ilist creates one // to serve as a sentinel. friend struct ilist_sentinel_traits; - AliasSet() : PtrList(0), PtrListEnd(&PtrList), Forward(0), RefCount(0), - AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) { + AliasSet() + : PtrList(nullptr), PtrListEnd(&PtrList), Forward(nullptr), RefCount(0), + Access(NoAccess), Alias(SetMustAlias), Volatile(false) { } - AliasSet(const AliasSet &AS); // do not implement - void operator=(const AliasSet &AS); // do not implement + AliasSet(const AliasSet &AS) = delete; + void operator=(const AliasSet &AS) = delete; PointerRec *getSomePointer() const { return PtrList; @@ -224,23 +251,30 @@ private: void removeFromTracker(AliasSetTracker &AST); - void addPointer(AliasSetTracker &AST, PointerRec &Entry, unsigned Size, + void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size, + const AAMDNodes &AAInfo, bool KnownMustAlias = false); - void addCallSite(CallSite CS, AliasAnalysis &AA); - void removeCallSite(CallSite CS) { - for (size_t i = 0, e = CallSites.size(); i != e; ++i) - if (CallSites[i].getInstruction() == CS.getInstruction()) { - CallSites[i] = CallSites.back(); - CallSites.pop_back(); + void addUnknownInst(Instruction *I, AliasAnalysis &AA); + void removeUnknownInst(AliasSetTracker &AST, Instruction *I) { + bool WasEmpty = UnknownInsts.empty(); + for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i) + if (UnknownInsts[i] == I) { + UnknownInsts[i] = UnknownInsts.back(); + UnknownInsts.pop_back(); + --i; --e; // Revisit the moved entry. } + if (!WasEmpty && UnknownInsts.empty()) + dropRef(AST); } void setVolatile() { Volatile = true; } +public: /// aliasesPointer - Return true if the specified pointer "may" (or must) /// alias one of the members in the set. /// - bool aliasesPointer(const Value *Ptr, unsigned Size, AliasAnalysis &AA) const; - bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const; + bool aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo, + AliasAnalysis &AA) const; + bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const; }; inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) { @@ -252,11 +286,12 @@ inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) { class AliasSetTracker { /// CallbackVH - A CallbackVH to arrange for AliasSetTracker to be /// notified whenever a Value is deleted. - class ASTCallbackVH : public CallbackVH { + class ASTCallbackVH final : public CallbackVH { AliasSetTracker *AST; - virtual void deleted(); + void deleted() override; + void allUsesReplacedWith(Value *) override; public: - ASTCallbackVH(Value *V, AliasSetTracker *AST = 0); + ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr); ASTCallbackVH &operator=(Value *V); }; /// ASTCallbackVHDenseMapInfo - Traits to tell DenseMap that tell us how to @@ -292,29 +327,26 @@ public: /// These methods return true if inserting the instruction resulted in the /// addition of a new alias set (i.e., the pointer did not alias anything). /// - bool add(Value *Ptr, unsigned Size); // Add a location + bool add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo); // Add a loc. bool add(LoadInst *LI); bool add(StoreInst *SI); bool add(VAArgInst *VAAI); - bool add(CallSite CS); // Call/Invoke instructions - bool add(CallInst *CI) { return add(CallSite(CI)); } - bool add(InvokeInst *II) { return add(CallSite(II)); } bool add(Instruction *I); // Dispatch to one of the other add methods... void add(BasicBlock &BB); // Add all instructions in basic block void add(const AliasSetTracker &AST); // Add alias relations from another AST + bool addUnknown(Instruction *I); /// remove methods - These methods are used to remove all entries that might /// be aliased by the specified instruction. These methods return true if any /// alias sets were eliminated. - bool remove(Value *Ptr, unsigned Size); // Remove a location + // Remove a location + bool remove(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo); bool remove(LoadInst *LI); bool remove(StoreInst *SI); bool remove(VAArgInst *VAAI); - bool remove(CallSite CS); - bool remove(CallInst *CI) { return remove(CallSite(CI)); } - bool remove(InvokeInst *II) { return remove(CallSite(II)); } bool remove(Instruction *I); void remove(AliasSet &AS); + bool removeUnknown(Instruction *I); void clear(); @@ -326,18 +358,26 @@ public: /// lives in. If the New argument is non-null, this method sets the value to /// true if a new alias set is created to contain the pointer (because the /// pointer didn't alias anything). - AliasSet &getAliasSetForPointer(Value *P, unsigned Size, bool *New = 0); + AliasSet &getAliasSetForPointer(Value *P, uint64_t Size, + const AAMDNodes &AAInfo, + bool *New = nullptr); /// getAliasSetForPointerIfExists - Return the alias set containing the /// location specified if one exists, otherwise return null. - AliasSet *getAliasSetForPointerIfExists(Value *P, unsigned Size) { - return findAliasSetForPointer(P, Size); + AliasSet *getAliasSetForPointerIfExists(const Value *P, uint64_t Size, + const AAMDNodes &AAInfo) { + return findAliasSetForPointer(P, Size, AAInfo); } /// containsPointer - Return true if the specified location is represented by /// this alias set, false otherwise. This does not modify the AST object or /// alias sets. - bool containsPointer(Value *P, unsigned Size) const; + bool containsPointer(const Value *P, uint64_t Size, + const AAMDNodes &AAInfo) const; + + /// Return true if the specified instruction "may" (or must) alias one of the + /// members in any of the sets. + bool containsUnknown(const Instruction *I) const; /// getAliasAnalysis - Return the underlying alias analysis object used by /// this tracker. @@ -379,21 +419,23 @@ private: // entry for the pointer if it doesn't already exist. AliasSet::PointerRec &getEntryFor(Value *V) { AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)]; - if (Entry == 0) + if (!Entry) Entry = new AliasSet::PointerRec(V); return *Entry; } - AliasSet &addPointer(Value *P, unsigned Size, AliasSet::AccessType E, + AliasSet &addPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo, + AliasSet::AccessLattice E, bool &NewSet) { NewSet = false; - AliasSet &AS = getAliasSetForPointer(P, Size, &NewSet); - AS.AccessTy |= E; + AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo, &NewSet); + AS.Access |= E; return AS; } - AliasSet *findAliasSetForPointer(const Value *Ptr, unsigned Size); + AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size, + const AAMDNodes &AAInfo); - AliasSet *findAliasSetForCallSite(CallSite CS); + AliasSet *findAliasSetForUnknownInst(Instruction *Inst); }; inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {