X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FAliasSetTracker.h;h=786c1d15ba1ab0a8d4a2e7ae7c23047a22ab0afe;hb=c23197a26f34f559ea9797de51e187087c039c42;hp=fe3e60c62bbd615837ed238441b8e5650f02e14e;hpb=7e0e9c635f5439426252bd1ccbfa90b878ba0ca6;p=oota-llvm.git diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index fe3e60c62bb..786c1d15ba1 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -1,26 +1,29 @@ //===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===// -// +// // 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. +// //===----------------------------------------------------------------------===// // // 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 "llvm/ADT/iterator" -#include "llvm/ADT/hash_map" -#include "llvm/ADT/ilist" +#include "llvm/Support/Streams.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/iterator.h" +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" +#include namespace llvm { @@ -28,26 +31,28 @@ class AliasAnalysis; class LoadInst; class StoreInst; class FreeInst; +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 **PrevInList, *NextInList; + Value *Val; // The pointer this record corresponds to. + PointerRec **PrevInList, *NextInList; AliasSet *AS; unsigned Size; public: - PointerRec() : PrevInList(0), NextInList(0), AS(0), Size(0) {} + PointerRec(Value *V) + : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0) {} - 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; } @@ -58,7 +63,7 @@ class AliasSet { unsigned getSize() const { return Size; } - AliasSet *getAliasSet(AliasSetTracker &AST) { + AliasSet *getAliasSet(AliasSetTracker &AST) { assert(AS && "No AliasSet yet!"); if (AS->Forward) { AliasSet *OldAS = AS; @@ -74,21 +79,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. + AliasSet *Next, *Prev; // Doubly linked list of AliasSets. - std::vector CallSites; // All calls & invokes in this node + std::vector CallSites; // All calls & invokes in this alias set. // RefCount - Number of nodes pointing to this AliasSet plus the number of // AliasSets forwarding to it. @@ -116,12 +122,6 @@ class AliasSet { // Volatile - True if this alias set contains volatile loads or stores. bool Volatile : 1; - 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; } - void addRef() { ++RefCount; } void dropRef(AliasSetTracker &AST) { assert(RefCount >= 1 && "Invalid reference count detected!"); @@ -146,7 +146,7 @@ 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... @@ -156,14 +156,15 @@ public: 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; + class iterator : public forward_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; } @@ -173,38 +174,38 @@ public: 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(); } - + Value *getPointer() const { return CurNode->getValue(); } + unsigned getSize() const { return CurNode->getSize(); } + 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 + // 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); // do not implement + void operator=(const AliasSet &AS); // do not implement - HashNodePair *getSomePointer() const { + PointerRec *getSomePointer() const { return PtrList; } @@ -225,9 +226,16 @@ private: void removeFromTracker(AliasSetTracker &AST); - void addPointer(AliasSetTracker &AST, HashNodePair &Entry, unsigned Size, + void addPointer(AliasSetTracker &AST, PointerRec &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) @@ -248,12 +256,13 @@ class AliasSetTracker { ilist AliasSets; // Map from pointers to their node - hash_map PointerMap; + DenseMap 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 @@ -271,6 +280,7 @@ public: 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)); } @@ -285,11 +295,14 @@ public: 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(); /// getAliasSets - Return the alias sets that are active. /// @@ -307,6 +320,11 @@ public: 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; } @@ -337,17 +355,20 @@ 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: 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[V]; + if (Entry == 0) + Entry = new AliasSet::PointerRec(V); + return *Entry; } AliasSet &addPointer(Value *P, unsigned Size, AliasSet::AccessType E,