X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FAliasSetTracker.h;h=37fd69b081ccb604d30bbb1f98be51ac0b6db2cb;hb=2b762697564ca1e12e0e974e93ceeb4c3420505c;hp=d2f22f36bbb9dbea1b7dff5abbab11f4016ee4c3;hpb=be583b914d8156b99d3da264d5adca37fee8dbc9;p=oota-llvm.git diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index d2f22f36bbb..37fd69b081c 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -1,112 +1,173 @@ //===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===// // +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// // This file defines two classes: AliasSetTracker and AliasSet. These interface // are used to classify a collection of pointer references into a maximal number // of disjoint sets. Each AliasSet object constructed by the AliasSetTracker // object refers to memory disjoint from the other sets. -// +// //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H #define LLVM_ANALYSIS_ALIASSETTRACKER_H -#include +#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 { -#include "llvm/Support/CallSite.h" -#include "Support/iterator" -#include "Support/hash_map" -#include "Support/ilist" -class AliasAnalysis; class LoadInst; class StoreInst; +class VAArgInst; class AliasSetTracker; class AliasSet; -class AliasSet { +class AliasSet : public ilist_node { friend class AliasSetTracker; - struct PointerRec; - typedef std::pair HashNodePair; - class PointerRec { - HashNodePair *NextInList; + Value *Val; // The pointer this record corresponds to. + PointerRec **PrevInList, *NextInList; AliasSet *AS; - unsigned Size; + uint64_t Size; + AAMDNodes AAInfo; + public: - PointerRec() : NextInList(0), AS(0), Size(0) {} + PointerRec(Value *V) + : 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 != nullptr; } - HashNodePair *getNext() const { return NextInList; } - bool hasAliasSet() const { return AS != 0; } + 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; } - AliasSet *getAliasSet(AliasSetTracker &AST) { + /// 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!"); if (AS->Forward) { AliasSet *OldAS = AS; AS = OldAS->getForwardedTarget(AST); - if (--OldAS->RefCount == 0) - OldAS->removeFromTracker(AST); - AS->RefCount++; + AS->addRef(); + OldAS->dropRef(AST); } return AS; } void setAliasSet(AliasSet *as) { - assert(AS == 0 && "Already have an alias set!"); + assert(!AS && "Already have an alias set!"); AS = as; } - void setTail(HashNodePair *T) { - assert(NextInList == 0 && "Already have tail!"); - NextInList = T; + + void eraseFromList() { + if (NextInList) NextInList->PrevInList = PrevInList; + *PrevInList = NextInList; + if (AS->PtrListEnd == &NextInList) { + AS->PtrListEnd = PrevInList; + assert(*AS->PtrListEnd == nullptr && "List not terminated right!"); + } + delete this; } }; - HashNodePair *PtrListHead, *PtrListTail; // Singly 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. - unsigned RefCount : 29; + 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 neccesary. + /// 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; + + void addRef() { ++RefCount; } + void dropRef(AliasSetTracker &AST) { + assert(RefCount >= 1 && "Invalid reference count detected!"); + if (--RefCount == 0) + removeFromTracker(AST); + } - friend class ilist_traits; - AliasSet *getPrev() const { return Prev; } - AliasSet *getNext() const { return Next; } - void setPrev(AliasSet *P) { Prev = P; } - void setNext(AliasSet *N) { Next = N; } + 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. + bool isVolatile() const { return Volatile; } /// isForwardingAliasSet - Return true if this alias set should be ignored as /// part of the AliasSetTracker object. @@ -114,56 +175,65 @@ public: /// mergeSetIn - Merge the specified alias set into this alias set... /// - void mergeSetIn(AliasSet &AS); + void mergeSetIn(AliasSet &AS, AliasSetTracker &AST); // Alias Set iteration - Allow access to all of the pointer which are part of // this alias set... class iterator; - iterator begin() const { return iterator(PtrListHead); } + iterator begin() const { return iterator(PtrList); } iterator end() const { return iterator(); } + bool empty() const { return PtrList == nullptr; } - 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 = 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; } value_type *operator->() const { return &operator*(); } - + + Value *getPointer() const { return CurNode->getValue(); } + uint64_t getSize() const { return CurNode->getSize(); } + AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); } + iterator& operator++() { // Preincrement assert(CurNode && "Advancing past AliasSet.end()!"); - CurNode = CurNode->second.getNext(); + CurNode = CurNode->getNext(); return *this; } iterator operator++(int) { // Postincrement - iterator tmp = *this; ++*this; return tmp; + iterator tmp = *this; ++*this; return tmp; } }; private: - // Can only be created by AliasSetTracker - AliasSet() : PtrListHead(0), PtrListTail(0), Forward(0), RefCount(0), - AccessTy(NoModRef), AliasTy(MustAlias) { + // Can only be created by AliasSetTracker. Also, ilist creates one + // to serve as a sentinel. + friend struct ilist_sentinel_traits; + AliasSet() + : PtrList(nullptr), PtrListEnd(&PtrList), Forward(nullptr), RefCount(0), + Access(NoAccess), Alias(SetMustAlias), Volatile(false) { } - HashNodePair *getSomePointer() const { - return PtrListHead ? PtrListHead : 0; + + AliasSet(const AliasSet &AS) = delete; + void operator=(const AliasSet &AS) = delete; + + PointerRec *getSomePointer() const { + return PtrList; } /// getForwardedTarget - Return the real alias set this represents. If this @@ -174,9 +244,8 @@ private: AliasSet *Dest = Forward->getForwardedTarget(AST); if (Dest != Forward) { - Dest->RefCount++; - if (--Forward->RefCount == 0) - Forward->removeFromTracker(AST); + Dest->addRef(); + Forward->dropRef(AST); Forward = Dest; } return Dest; @@ -184,33 +253,69 @@ private: void removeFromTracker(AliasSetTracker &AST); - void addPointer(AliasSetTracker &AST, HashNodePair &Entry, unsigned Size); - void addCallSite(CallSite CS); + void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size, + const AAMDNodes &AAInfo, + bool KnownMustAlias = false); + 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 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 final : public CallbackVH { + AliasSetTracker *AST; + void deleted() override; + void allUsesReplacedWith(Value *) override; + + public: + ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr); + 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 @@ -221,26 +326,80 @@ public: /// 3. If the instruction aliases multiple sets, merge the sets, and add /// the instruction to the result. /// - void add(LoadInst *LI); - void add(StoreInst *SI); - void add(CallSite CS); // Call/Invoke instructions - void add(CallInst *CI) { add(CallSite(CI)); } - void add(InvokeInst *II) { add(CallSite(II)); } - void add(Instruction *I); // Dispatch to one of the other add methods... + /// 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, uint64_t Size, const AAMDNodes &AAInfo); // Add a loc. + bool add(LoadInst *LI); + bool add(StoreInst *SI); + 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. + // 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(Instruction *I); + void remove(AliasSet &AS); + bool removeUnknown(Instruction *I); + + void clear(); /// getAliasSets - Return the alias sets that are active. + /// const ilist &getAliasSets() const { return AliasSets; } /// getAliasSetForPointer - Return the alias set that the specified pointer - /// lives in... - AliasSet &getAliasSetForPointer(Value *P, unsigned Size); + /// 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, 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(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(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. AliasAnalysis &getAliasAnalysis() const { return AA; } + /// deleteValue method - This method is used to remove a pointer value from + /// the AliasSetTracker entirely. It should be used when an instruction is + /// deleted from the program to update the AST. If you don't use this, you + /// would have dangling pointers to deleted instructions. + /// + void deleteValue(Value *PtrVal); + + /// copyValue - This method should be used whenever a preexisting value in the + /// program is copied or cloned, introducing a new value. Note that it is ok + /// for clients that use this method to introduce the same value multiple + /// times: if the tracker already knows about a value, it will ignore the + /// request. + /// + void copyValue(Value *From, Value *To); + typedef ilist::iterator iterator; typedef ilist::const_iterator const_iterator; @@ -250,32 +409,41 @@ 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) + Entry = new AliasSet::PointerRec(V); + return *Entry; } - void addPointer(Value *P, unsigned Size, AliasSet::AccessType E) { - AliasSet &AS = getAliasSetForPointer(P, Size); - AS.AccessTy |= E; + AliasSet &addPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo, + AliasSet::AccessLattice E, + bool &NewSet) { + NewSet = false; + 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 std::ostream& operator<<(std::ostream &OS, const AliasSetTracker &AST) { +inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) { AST.print(OS); return OS; } +} // End llvm namespace + #endif