X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FAliasSetTracker.h;h=163331c262c1c75ab55cf0a13fb83baf197f2910;hb=255f89faee13dc491cb64fbeae3c763e7e2ea4e6;hp=0a9e278b4d96d9dc87fb79b102080d7c2a42b438;hpb=688ed8583eaa1544e8e53b039b2b8284d2e9268a;p=oota-llvm.git diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index 0a9e278b4d9..163331c262c 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -17,11 +17,11 @@ #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H #define LLVM_ANALYSIS_ALIASSETTRACKER_H -#include "llvm/Support/CallSite.h" #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/iterator.h" #include "llvm/ADT/ilist.h" #include "llvm/ADT/ilist_node.h" +#include "llvm/Support/CallSite.h" +#include "llvm/Support/ValueHandle.h" #include namespace llvm { @@ -29,7 +29,6 @@ namespace llvm { class AliasAnalysis; class LoadInst; class StoreInst; -class FreeInst; class VAArgInst; class AliasSetTracker; class AliasSet; @@ -41,10 +40,12 @@ class AliasSet : public ilist_node { Value *Val; // The pointer this record corresponds to. PointerRec **PrevInList, *NextInList; AliasSet *AS; - unsigned Size; + uint64_t Size; + const MDNode *TBAAInfo; public: PointerRec(Value *V) - : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0) {} + : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0), + TBAAInfo(DenseMapInfo::getEmptyKey()) {} Value *getValue() const { return Val; } @@ -56,11 +57,28 @@ class AliasSet : public ilist_node { return &NextInList; } - void updateSize(unsigned NewSize) { + void updateSizeAndTBAAInfo(uint64_t NewSize, const MDNode *NewTBAAInfo) { if (NewSize > Size) Size = NewSize; + + if (TBAAInfo == DenseMapInfo::getEmptyKey()) + // We don't have a TBAAInfo yet. Set it to NewTBAAInfo. + TBAAInfo = NewTBAAInfo; + else if (TBAAInfo != NewTBAAInfo) + // NewTBAAInfo conflicts with TBAAInfo. + TBAAInfo = DenseMapInfo::getTombstoneKey(); } - unsigned getSize() const { return Size; } + uint64_t getSize() const { return Size; } + + /// getTBAAInfo - Return the TBAAInfo, or null if there is no + /// information or conflicting information. + const MDNode *getTBAAInfo() const { + // If we have missing or conflicting TBAAInfo, return null. + if (TBAAInfo == DenseMapInfo::getEmptyKey() || + TBAAInfo == DenseMapInfo::getTombstoneKey()) + return 0; + return TBAAInfo; + } AliasSet *getAliasSet(AliasSetTracker &AST) { assert(AS && "No AliasSet yet!"); @@ -91,9 +109,9 @@ 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. @@ -128,6 +146,11 @@ 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; } @@ -154,12 +177,12 @@ public: iterator end() const { return iterator(); } bool empty() const { return PtrList == 0; } - void print(std::ostream &OS) const; - void print(std::ostream *OS) const { if (OS) print(*OS); } + void print(raw_ostream &OS) const; void dump() const; /// Define an iterator for alias sets... this is just a forward iterator. - class iterator : public forward_iterator { + class iterator : public std::iterator { PointerRec *CurNode; public: explicit iterator(PointerRec *CN = 0) : CurNode(CN) {} @@ -181,7 +204,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(); } + const MDNode *getTBAAInfo() const { return CurNode->getTBAAInfo(); } iterator& operator++() { // Preincrement assert(CurNode && "Advancing past AliasSet.end()!"); @@ -201,8 +225,8 @@ private: AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) { } - AliasSet(const AliasSet &AS); // do not implement - void operator=(const AliasSet &AS); // do not implement + AliasSet(const AliasSet &AS) LLVM_DELETED_FUNCTION; + void operator=(const AliasSet &AS) LLVM_DELETED_FUNCTION; PointerRec *getSomePointer() const { return PtrList; @@ -225,37 +249,60 @@ private: void removeFromTracker(AliasSetTracker &AST); - void addPointer(AliasSetTracker &AST, PointerRec &Entry, unsigned Size, + void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size, + const MDNode *TBAAInfo, 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(Instruction *I) { + 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. } } 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 MDNode *TBAAInfo, + AliasAnalysis &AA) const; + bool aliasesUnknownInst(Instruction *Inst, AliasAnalysis &AA) const; }; -inline std::ostream& operator<<(std::ostream &OS, const AliasSet &AS) { +inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) { AS.print(OS); return OS; } class AliasSetTracker { + /// CallbackVH - A CallbackVH to arrange for AliasSetTracker to be + /// notified whenever a Value is deleted. + class ASTCallbackVH : public CallbackVH { + AliasSetTracker *AST; + virtual void deleted(); + virtual void allUsesReplacedWith(Value *); + public: + ASTCallbackVH(Value *V, AliasSetTracker *AST = 0); + ASTCallbackVH &operator=(Value *V); + }; + /// ASTCallbackVHDenseMapInfo - Traits to tell DenseMap that tell us how to + /// compare and hash the value handle. + struct ASTCallbackVHDenseMapInfo : public DenseMapInfo {}; + AliasAnalysis &AA; ilist AliasSets; + typedef DenseMap + PointerMapType; + // Map from pointers to their node - DenseMap PointerMap; + PointerMapType PointerMap; + public: /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use /// the specified alias analysis object to disambiguate load and store @@ -275,31 +322,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 MDNode *TBAAInfo); // Add a location bool add(LoadInst *LI); bool add(StoreInst *SI); - bool add(FreeInst *FI); 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 MDNode *TBAAInfo); bool remove(LoadInst *LI); bool remove(StoreInst *SI); - bool remove(FreeInst *FI); 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(); @@ -311,18 +353,21 @@ 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 MDNode *TBAAInfo, + bool *New = 0); /// 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(Value *P, uint64_t Size, + const MDNode *TBAAInfo) { + return findAliasSetForPointer(P, Size, TBAAInfo); } /// 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(Value *P, uint64_t Size, const MDNode *TBAAInfo) const; /// getAliasAnalysis - Return the underlying alias analysis object used by /// this tracker. @@ -353,8 +398,7 @@ public: iterator begin() { return AliasSets.begin(); } iterator end() { return AliasSets.end(); } - void print(std::ostream &OS) const; - void print(std::ostream *OS) const { if (OS) print(*OS); } + void print(raw_ostream &OS) const; void dump() const; private: @@ -364,25 +408,27 @@ private: // getEntryFor - Just like operator[] on the map, except that it creates an // entry for the pointer if it doesn't already exist. AliasSet::PointerRec &getEntryFor(Value *V) { - AliasSet::PointerRec *&Entry = PointerMap[V]; + AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)]; if (Entry == 0) Entry = new AliasSet::PointerRec(V); return *Entry; } - AliasSet &addPointer(Value *P, unsigned Size, AliasSet::AccessType E, + AliasSet &addPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo, + AliasSet::AccessType E, bool &NewSet) { NewSet = false; - AliasSet &AS = getAliasSetForPointer(P, Size, &NewSet); + AliasSet &AS = getAliasSetForPointer(P, Size, TBAAInfo, &NewSet); AS.AccessTy |= E; return AS; } - AliasSet *findAliasSetForPointer(const Value *Ptr, unsigned Size); + AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size, + const MDNode *TBAAInfo); - AliasSet *findAliasSetForCallSite(CallSite CS); + AliasSet *findAliasSetForUnknownInst(Instruction *Inst); }; -inline std::ostream& operator<<(std::ostream &OS, const AliasSetTracker &AST) { +inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) { AST.print(OS); return OS; }