X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FAliasSetTracker.h;h=163331c262c1c75ab55cf0a13fb83baf197f2910;hb=b09c146b116359616f6cbd4c8b3328607e00ff42;hp=082d89910b84e5a2df8d3f6ab0c46e49c8b7d07f;hpb=69fd7a3973a5c4ba4fb883b836fd0b84c046d10c;p=oota-llvm.git diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index 082d89910b8..163331c262c 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -17,46 +17,68 @@ #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H #define LLVM_ANALYSIS_ALIASSETTRACKER_H +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" #include "llvm/Support/CallSite.h" -#include "llvm/ADT/iterator" -#include "llvm/ADT/hash_map" -#include "llvm/ADT/ilist" +#include "llvm/Support/ValueHandle.h" +#include namespace llvm { class AliasAnalysis; class LoadInst; class StoreInst; -class FreeInst; +class VAArgInst; class AliasSetTracker; class AliasSet; -class AliasSet { +class AliasSet : public ilist_node { friend class AliasSetTracker; - class PointerRec; - typedef std::pair HashNodePair; - class PointerRec { - HashNodePair **PrevInList, *NextInList; + Value *Val; // The pointer this record corresponds to. + PointerRec **PrevInList, *NextInList; AliasSet *AS; - unsigned Size; + uint64_t Size; + const MDNode *TBAAInfo; public: - PointerRec() : PrevInList(0), NextInList(0), AS(0), Size(0) {} + PointerRec(Value *V) + : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0), + TBAAInfo(DenseMapInfo::getEmptyKey()) {} - HashNodePair *getNext() const { return NextInList; } + Value *getValue() const { return Val; } + + PointerRec *getNext() const { return NextInList; } bool hasAliasSet() const { return AS != 0; } - HashNodePair** setPrevInList(HashNodePair **PIL) { + PointerRec** setPrevInList(PointerRec **PIL) { PrevInList = PIL; 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!"); @@ -74,21 +96,22 @@ class AliasSet { AS = as; } - void removeFromList() { - if (NextInList) NextInList->second.PrevInList = PrevInList; + void eraseFromList() { + if (NextInList) NextInList->PrevInList = PrevInList; *PrevInList = NextInList; if (AS->PtrListEnd == &NextInList) { AS->PtrListEnd = PrevInList; assert(*AS->PtrListEnd == 0 && "List not terminated right!"); } + delete this; } }; - HashNodePair *PtrList, **PtrListEnd; // Doubly linked list of nodes - AliasSet *Forward; // Forwarding pointer - AliasSet *Next, *Prev; // Doubly linked list of AliasSets + PointerRec *PtrList, **PtrListEnd; // Doubly linked list of nodes. + AliasSet *Forward; // Forwarding pointer. - std::vector CallSites; // All calls & invokes in this node + // 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. @@ -116,12 +139,6 @@ class AliasSet { // Volatile - True if this alias set contains volatile loads or stores. bool Volatile : 1; - friend struct ilist_traits; - AliasSet *getPrev() const { return Prev; } - AliasSet *getNext() const { return Next; } - void setPrev(AliasSet *P) { Prev = P; } - void setNext(AliasSet *N) { Next = N; } - void addRef() { ++RefCount; } void dropRef(AliasSetTracker &AST) { assert(RefCount >= 1 && "Invalid reference count detected!"); @@ -129,6 +146,11 @@ class AliasSet { removeFromTracker(AST); } + Instruction *getUnknownInst(unsigned i) const { + assert(i < UnknownInsts.size()); + return UnknownInsts[i]; + } + public: /// Accessors... bool isRef() const { return AccessTy & Refs; } @@ -155,14 +177,15 @@ public: iterator end() const { return iterator(); } bool empty() const { return PtrList == 0; } - void print(std::ostream &OS) const; + 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 { - HashNodePair *CurNode; + class iterator : public std::iterator { + PointerRec *CurNode; public: - iterator(HashNodePair *CN = 0) : CurNode(CN) {} + explicit iterator(PointerRec *CN = 0) : CurNode(CN) {} bool operator==(const iterator& x) const { return CurNode == x.CurNode; @@ -180,12 +203,13 @@ public: } value_type *operator->() const { return &operator*(); } - Value *getPointer() const { return CurNode->first; } - unsigned getSize() const { return CurNode->second.getSize(); } + Value *getPointer() const { return CurNode->getValue(); } + uint64_t getSize() const { return CurNode->getSize(); } + const MDNode *getTBAAInfo() const { return CurNode->getTBAAInfo(); } iterator& operator++() { // Preincrement assert(CurNode && "Advancing past AliasSet.end()!"); - CurNode = CurNode->second.getNext(); + CurNode = CurNode->getNext(); return *this; } iterator operator++(int) { // Postincrement @@ -194,17 +218,17 @@ public: }; private: - // Can only be created by AliasSetTracker + // 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(const AliasSet &AS) { - assert(0 && "Copy ctor called!?!?!"); - abort(); - } + AliasSet(const AliasSet &AS) LLVM_DELETED_FUNCTION; + void operator=(const AliasSet &AS) LLVM_DELETED_FUNCTION; - HashNodePair *getSomePointer() const { + PointerRec *getSomePointer() const { return PtrList; } @@ -225,42 +249,66 @@ private: void removeFromTracker(AliasSetTracker &AST); - void addPointer(AliasSetTracker &AST, HashNodePair &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 (unsigned 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 - hash_map PointerMap; + PointerMapType PointerMap; + public: /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use /// the specified alias analysis object to disambiguate load and store /// addresses. - AliasSetTracker(AliasAnalysis &aa) : AA(aa) {} + explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {} + ~AliasSetTracker() { clear(); } /// add methods - These methods are used to add different types of /// instructions to the alias sets. Adding a new instruction can result in @@ -274,34 +322,28 @@ 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(CallSite CS); // Call/Invoke instructions - bool add(CallInst *CI) { return add(CallSite(CI)); } - bool add(InvokeInst *II) { return add(CallSite(II)); } + bool add(VAArgInst *VAAI); 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(CallSite CS); - bool remove(CallInst *CI) { return remove(CallSite(CI)); } - bool remove(InvokeInst *II) { return remove(CallSite(II)); } + bool remove(VAArgInst *VAAI); bool remove(Instruction *I); void remove(AliasSet &AS); + bool removeUnknown(Instruction *I); - void clear() { - PointerMap.clear(); - AliasSets.clear(); - } + void clear(); /// getAliasSets - Return the alias sets that are active. /// @@ -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,33 +398,37 @@ public: iterator begin() { return AliasSets.begin(); } iterator end() { return AliasSets.end(); } - void print(std::ostream &OS) const; + void print(raw_ostream &OS) const; void dump() const; private: friend class AliasSet; void removeAliasSet(AliasSet *AS); - AliasSet::HashNodePair &getEntryFor(Value *V) { - // Standard operator[], except that it returns the whole pair, not just - // ->second. - return *PointerMap.insert(AliasSet::HashNodePair(V, - AliasSet::PointerRec())).first; + // 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[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; }