X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FAliasSetTracker.h;h=d9e45ce9a1c46682360ba6a3f2b580681099c7dd;hb=43d1fd449f1a0ac9d9dafa0b9569bb6b2e976198;hp=ad71d99ca27d9773cfb4ee9e71d5b9a03df5e39a;hpb=9971ac4a36c54488bcdf55d7e493ac0cd6dc168a;p=oota-llvm.git diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index ad71d99ca27..d9e45ce9a1c 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -1,48 +1,72 @@ //===- 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 "llvm/Support/CallSite.h" -#include "Support/iterator" -#include "Support/hash_map" -#include "Support/ilist" +#include "llvm/Support/Streams.h" +#include "llvm/ADT/iterator.h" +#include "llvm/ADT/hash_map.h" +#include "llvm/ADT/ilist.h" + +namespace llvm { + class AliasAnalysis; class LoadInst; class StoreInst; +class FreeInst; +class VAArgInst; class AliasSetTracker; class AliasSet; class AliasSet { friend class AliasSetTracker; - struct PointerRec; + class PointerRec; typedef std::pair HashNodePair; class PointerRec { - HashNodePair *NextInList; + HashNodePair **PrevInList, *NextInList; AliasSet *AS; + unsigned Size; public: - PointerRec() : NextInList(0), AS(0) {} + PointerRec() : PrevInList(0), NextInList(0), AS(0), Size(0) {} HashNodePair *getNext() const { return NextInList; } bool hasAliasSet() const { return AS != 0; } - AliasSet *getAliasSet(AliasSetTracker &AST) { + HashNodePair** setPrevInList(HashNodePair **PIL) { + PrevInList = PIL; + return &NextInList; + } + + void updateSize(unsigned NewSize) { + if (NewSize > Size) Size = NewSize; + } + + unsigned getSize() const { return Size; } + + 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; } @@ -51,13 +75,18 @@ class AliasSet { assert(AS == 0 && "Already have an alias set!"); AS = as; } - void setTail(HashNodePair *T) { - assert(NextInList == 0 && "Already have tail!"); - NextInList = T; + + void removeFromList() { + if (NextInList) NextInList->second.PrevInList = PrevInList; + *PrevInList = NextInList; + if (AS->PtrListEnd == &NextInList) { + AS->PtrListEnd = PrevInList; + assert(*AS->PtrListEnd == 0 && "List not terminated right!"); + } } }; - HashNodePair *PtrListHead, *PtrListTail; // Singly linked list of nodes + HashNodePair *PtrList, **PtrListEnd; // Doubly linked list of nodes AliasSet *Forward; // Forwarding pointer AliasSet *Next, *Prev; // Doubly linked list of AliasSets @@ -65,12 +94,12 @@ class AliasSet { // 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. + /// ModRef as necessary. /// enum AccessType { NoModRef = 0, Refs = 1, // Ref = bit 1 @@ -86,44 +115,22 @@ class AliasSet { }; unsigned AliasTy : 1; - /// Define an iterator for alias sets... this is just a forward iterator. - class iterator : public forward_iterator { - HashNodePair *CurNode; - public: - iterator(HashNodePair *CN = 0) : CurNode(CN) {} - - bool operator==(const iterator& x) const { - return CurNode == x.CurNode; - } - bool operator!=(const iterator& x) const { return !operator==(x); } + // Volatile - True if this alias set contains volatile loads or stores. + bool Volatile : 1; - const iterator &operator=(const iterator &I) { - CurNode = I.CurNode; - return *this; - } - - value_type operator*() const { - assert(CurNode && "Dereferencing AliasSet.end()!"); - return CurNode->first; - } - value_type operator->() const { return operator*(); } - - iterator& operator++() { // Preincrement - assert(CurNode && "Advancing past AliasSet.end()!"); - CurNode = CurNode->second.getNext(); - return *this; - } - iterator operator++(int) { // Postincrement - iterator tmp = *this; ++*this; return tmp; - } - }; - - friend class ilist_traits; + 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!"); + if (--RefCount == 0) + removeFromTracker(AST); + } + public: /// Accessors... bool isRef() const { return AccessTy & Refs; } @@ -131,25 +138,77 @@ public: bool isMustAlias() const { return AliasTy == MustAlias; } bool isMayAlias() const { return AliasTy == MayAlias; } + // 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. + bool isForwardingAliasSet() const { return Forward; } + /// 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... - iterator begin() const { return iterator(PtrListHead); } + class iterator; + iterator begin() const { return iterator(PtrList); } 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 dump() const; + /// Define an iterator for alias sets... this is just a forward iterator. + class iterator : public forward_iterator { + HashNodePair *CurNode; + public: + explicit iterator(HashNodePair *CN = 0) : 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->first; } + unsigned getSize() const { return CurNode->second.getSize(); } + + iterator& operator++() { // Preincrement + assert(CurNode && "Advancing past AliasSet.end()!"); + CurNode = CurNode->second.getNext(); + return *this; + } + iterator operator++(int) { // Postincrement + 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) { + AliasSet() : PtrList(0), PtrListEnd(&PtrList), Forward(0), RefCount(0), + AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) { } - Value *getSomePointer() const { - return PtrListHead ? PtrListHead->first : 0; + + AliasSet(const AliasSet &AS) { + assert(0 && "Copy ctor called!?!?!"); + abort(); + } + + HashNodePair *getSomePointer() const { + return PtrList; } /// getForwardedTarget - Return the real alias set this represents. If this @@ -160,9 +219,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; @@ -170,13 +228,22 @@ private: void removeFromTracker(AliasSetTracker &AST); - void addPointer(AliasSetTracker &AST, HashNodePair &Entry); - void addCallSite(CallSite CS); + void addPointer(AliasSetTracker &AST, HashNodePair &Entry, unsigned Size, + 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 setVolatile() { Volatile = true; } /// aliasesPointer - Return true if the specified pointer "may" (or must) /// alias one of the members in the set. /// - bool aliasesPointer(const Value *Ptr, AliasAnalysis &AA) const; + bool aliasesPointer(const Value *Ptr, unsigned Size, AliasAnalysis &AA) const; bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const; }; @@ -196,7 +263,8 @@ 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 @@ -207,24 +275,81 @@ 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, unsigned Size); // 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 + + /// 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 + 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); + + void clear() { + PointerMap.clear(); + AliasSets.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); + /// 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); + + /// 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); + } + + /// 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; /// 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; @@ -235,6 +360,7 @@ public: iterator end() { return AliasSets.end(); } void print(std::ostream &OS) const; + void print(std::ostream *OS) const { if (OS) print(*OS); } void dump() const; private: @@ -248,11 +374,14 @@ private: AliasSet::PointerRec())).first; } - void addPointer(Value *P, AliasSet::AccessType E) { - AliasSet &AS = getAliasSetForPointer(P); + AliasSet &addPointer(Value *P, unsigned Size, AliasSet::AccessType E, + bool &NewSet) { + NewSet = false; + AliasSet &AS = getAliasSetForPointer(P, Size, &NewSet); AS.AccessTy |= E; + return AS; } - AliasSet *findAliasSetForPointer(const Value *Ptr); + AliasSet *findAliasSetForPointer(const Value *Ptr, unsigned Size); AliasSet *findAliasSetForCallSite(CallSite CS); }; @@ -262,4 +391,6 @@ inline std::ostream& operator<<(std::ostream &OS, const AliasSetTracker &AST) { return OS; } +} // End llvm namespace + #endif