LLVM API Documentation

AliasSetTracker.h

Go to the documentation of this file.
00001 //===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines two classes: AliasSetTracker and AliasSet.  These interface
00011 // are used to classify a collection of pointer references into a maximal number
00012 // of disjoint sets.  Each AliasSet object constructed by the AliasSetTracker
00013 // object refers to memory disjoint from the other sets.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H
00018 #define LLVM_ANALYSIS_ALIASSETTRACKER_H
00019 
00020 #include "llvm/Support/CallSite.h"
00021 #include "llvm/Support/ValueHandle.h"
00022 #include "llvm/ADT/DenseMap.h"
00023 #include "llvm/ADT/iterator.h"
00024 #include "llvm/ADT/ilist.h"
00025 #include "llvm/ADT/ilist_node.h"
00026 #include <vector>
00027 
00028 namespace llvm {
00029 
00030 class AliasAnalysis;
00031 class LoadInst;
00032 class StoreInst;
00033 class FreeInst;
00034 class VAArgInst;
00035 class AliasSetTracker;
00036 class AliasSet;
00037 
00038 class AliasSet : public ilist_node<AliasSet> {
00039   friend class AliasSetTracker;
00040 
00041   class PointerRec {
00042     Value *Val;  // The pointer this record corresponds to.
00043     PointerRec **PrevInList, *NextInList;
00044     AliasSet *AS;
00045     unsigned Size;
00046   public:
00047     PointerRec(Value *V)
00048       : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0) {}
00049 
00050     Value *getValue() const { return Val; }
00051     
00052     PointerRec *getNext() const { return NextInList; }
00053     bool hasAliasSet() const { return AS != 0; }
00054 
00055     PointerRec** setPrevInList(PointerRec **PIL) {
00056       PrevInList = PIL;
00057       return &NextInList;
00058     }
00059 
00060     void updateSize(unsigned NewSize) {
00061       if (NewSize > Size) Size = NewSize;
00062     }
00063 
00064     unsigned getSize() const { return Size; }
00065 
00066     AliasSet *getAliasSet(AliasSetTracker &AST) {
00067       assert(AS && "No AliasSet yet!");
00068       if (AS->Forward) {
00069         AliasSet *OldAS = AS;
00070         AS = OldAS->getForwardedTarget(AST);
00071         AS->addRef();
00072         OldAS->dropRef(AST);
00073       }
00074       return AS;
00075     }
00076 
00077     void setAliasSet(AliasSet *as) {
00078       assert(AS == 0 && "Already have an alias set!");
00079       AS = as;
00080     }
00081 
00082     void eraseFromList() {
00083       if (NextInList) NextInList->PrevInList = PrevInList;
00084       *PrevInList = NextInList;
00085       if (AS->PtrListEnd == &NextInList) {
00086         AS->PtrListEnd = PrevInList;
00087         assert(*AS->PtrListEnd == 0 && "List not terminated right!");
00088       }
00089       delete this;
00090     }
00091   };
00092 
00093   PointerRec *PtrList, **PtrListEnd;  // Doubly linked list of nodes.
00094   AliasSet *Forward;             // Forwarding pointer.
00095   AliasSet *Next, *Prev;         // Doubly linked list of AliasSets.
00096 
00097   std::vector<CallSite> CallSites; // All calls & invokes in this alias set.
00098 
00099   // RefCount - Number of nodes pointing to this AliasSet plus the number of
00100   // AliasSets forwarding to it.
00101   unsigned RefCount : 28;
00102 
00103   /// AccessType - Keep track of whether this alias set merely refers to the
00104   /// locations of memory, whether it modifies the memory, or whether it does
00105   /// both.  The lattice goes from "NoModRef" to either Refs or Mods, then to
00106   /// ModRef as necessary.
00107   ///
00108   enum AccessType {
00109     NoModRef = 0, Refs = 1,         // Ref = bit 1
00110     Mods     = 2, ModRef = 3        // Mod = bit 2
00111   };
00112   unsigned AccessTy : 2;
00113 
00114   /// AliasType - Keep track the relationships between the pointers in the set.
00115   /// Lattice goes from MustAlias to MayAlias.
00116   ///
00117   enum AliasType {
00118     MustAlias = 0, MayAlias = 1
00119   };
00120   unsigned AliasTy : 1;
00121 
00122   // Volatile - True if this alias set contains volatile loads or stores.
00123   bool Volatile : 1;
00124 
00125   void addRef() { ++RefCount; }
00126   void dropRef(AliasSetTracker &AST) {
00127     assert(RefCount >= 1 && "Invalid reference count detected!");
00128     if (--RefCount == 0)
00129       removeFromTracker(AST);
00130   }
00131 
00132 public:
00133   /// Accessors...
00134   bool isRef() const { return AccessTy & Refs; }
00135   bool isMod() const { return AccessTy & Mods; }
00136   bool isMustAlias() const { return AliasTy == MustAlias; }
00137   bool isMayAlias()  const { return AliasTy == MayAlias; }
00138 
00139   // isVolatile - Return true if this alias set contains volatile loads or
00140   // stores.
00141   bool isVolatile() const { return Volatile; }
00142 
00143   /// isForwardingAliasSet - Return true if this alias set should be ignored as
00144   /// part of the AliasSetTracker object.
00145   bool isForwardingAliasSet() const { return Forward; }
00146 
00147   /// mergeSetIn - Merge the specified alias set into this alias set...
00148   ///
00149   void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
00150 
00151   // Alias Set iteration - Allow access to all of the pointer which are part of
00152   // this alias set...
00153   class iterator;
00154   iterator begin() const { return iterator(PtrList); }
00155   iterator end()   const { return iterator(); }
00156   bool empty() const { return PtrList == 0; }
00157 
00158   void print(std::ostream &OS) const;
00159   void print(std::ostream *OS) const { if (OS) print(*OS); }
00160   void dump() const;
00161 
00162   /// Define an iterator for alias sets... this is just a forward iterator.
00163   class iterator : public forward_iterator<PointerRec, ptrdiff_t> {
00164     PointerRec *CurNode;
00165   public:
00166     explicit iterator(PointerRec *CN = 0) : CurNode(CN) {}
00167 
00168     bool operator==(const iterator& x) const {
00169       return CurNode == x.CurNode;
00170     }
00171     bool operator!=(const iterator& x) const { return !operator==(x); }
00172 
00173     const iterator &operator=(const iterator &I) {
00174       CurNode = I.CurNode;
00175       return *this;
00176     }
00177 
00178     value_type &operator*() const {
00179       assert(CurNode && "Dereferencing AliasSet.end()!");
00180       return *CurNode;
00181     }
00182     value_type *operator->() const { return &operator*(); }
00183 
00184     Value *getPointer() const { return CurNode->getValue(); }
00185     unsigned getSize() const { return CurNode->getSize(); }
00186 
00187     iterator& operator++() {                // Preincrement
00188       assert(CurNode && "Advancing past AliasSet.end()!");
00189       CurNode = CurNode->getNext();
00190       return *this;
00191     }
00192     iterator operator++(int) { // Postincrement
00193       iterator tmp = *this; ++*this; return tmp;
00194     }
00195   };
00196 
00197 private:
00198   // Can only be created by AliasSetTracker. Also, ilist creates one
00199   // to serve as a sentinel.
00200   friend struct ilist_sentinel_traits<AliasSet>;
00201   AliasSet() : PtrList(0), PtrListEnd(&PtrList), Forward(0), RefCount(0),
00202                AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) {
00203   }
00204 
00205   AliasSet(const AliasSet &AS);        // do not implement
00206   void operator=(const AliasSet &AS);  // do not implement
00207 
00208   PointerRec *getSomePointer() const {
00209     return PtrList;
00210   }
00211 
00212   /// getForwardedTarget - Return the real alias set this represents.  If this
00213   /// has been merged with another set and is forwarding, return the ultimate
00214   /// destination set.  This also implements the union-find collapsing as well.
00215   AliasSet *getForwardedTarget(AliasSetTracker &AST) {
00216     if (!Forward) return this;
00217 
00218     AliasSet *Dest = Forward->getForwardedTarget(AST);
00219     if (Dest != Forward) {
00220       Dest->addRef();
00221       Forward->dropRef(AST);
00222       Forward = Dest;
00223     }
00224     return Dest;
00225   }
00226 
00227   void removeFromTracker(AliasSetTracker &AST);
00228 
00229   void addPointer(AliasSetTracker &AST, PointerRec &Entry, unsigned Size,
00230                   bool KnownMustAlias = false);
00231   void addCallSite(CallSite CS, AliasAnalysis &AA);
00232   void removeCallSite(CallSite CS) {
00233     for (size_t i = 0, e = CallSites.size(); i != e; ++i)
00234       if (CallSites[i].getInstruction() == CS.getInstruction()) {
00235         CallSites[i] = CallSites.back();
00236         CallSites.pop_back();
00237       }
00238   }
00239   void setVolatile() { Volatile = true; }
00240 
00241   /// aliasesPointer - Return true if the specified pointer "may" (or must)
00242   /// alias one of the members in the set.
00243   ///
00244   bool aliasesPointer(const Value *Ptr, unsigned Size, AliasAnalysis &AA) const;
00245   bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const;
00246 };
00247 
00248 inline std::ostream& operator<<(std::ostream &OS, const AliasSet &AS) {
00249   AS.print(OS);
00250   return OS;
00251 }
00252 
00253 
00254 class AliasSetTracker {
00255   /// CallbackVH - A CallbackVH to arrange for AliasSetTracker to be
00256   /// notified whenever a Value is deleted.
00257   class ASTCallbackVH : public CallbackVH {
00258     AliasSetTracker *AST;
00259     virtual void deleted();
00260   public:
00261     ASTCallbackVH(Value *V, AliasSetTracker *AST = 0);
00262     ASTCallbackVH &operator=(Value *V);
00263   };
00264   /// ASTCallbackVHDenseMapInfo - Traits to tell DenseMap that ASTCallbackVH
00265   /// is not a POD (it needs its destructor called).
00266   struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {
00267     static bool isPod() { return false; }
00268   };
00269 
00270   AliasAnalysis &AA;
00271   ilist<AliasSet> AliasSets;
00272 
00273   typedef DenseMap<ASTCallbackVH, AliasSet::PointerRec*,
00274                    ASTCallbackVHDenseMapInfo>
00275     PointerMapType;
00276 
00277   // Map from pointers to their node
00278   PointerMapType PointerMap;
00279 
00280 public:
00281   /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use
00282   /// the specified alias analysis object to disambiguate load and store
00283   /// addresses.
00284   explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
00285   ~AliasSetTracker() { clear(); }
00286 
00287   /// add methods - These methods are used to add different types of
00288   /// instructions to the alias sets.  Adding a new instruction can result in
00289   /// one of three actions happening:
00290   ///
00291   ///   1. If the instruction doesn't alias any other sets, create a new set.
00292   ///   2. If the instruction aliases exactly one set, add it to the set
00293   ///   3. If the instruction aliases multiple sets, merge the sets, and add
00294   ///      the instruction to the result.
00295   ///
00296   /// These methods return true if inserting the instruction resulted in the
00297   /// addition of a new alias set (i.e., the pointer did not alias anything).
00298   ///
00299   bool add(Value *Ptr, unsigned Size);  // Add a location
00300   bool add(LoadInst *LI);
00301   bool add(StoreInst *SI);
00302   bool add(FreeInst *FI);
00303   bool add(VAArgInst *VAAI);
00304   bool add(CallSite CS);          // Call/Invoke instructions
00305   bool add(CallInst *CI)   { return add(CallSite(CI)); }
00306   bool add(InvokeInst *II) { return add(CallSite(II)); }
00307   bool add(Instruction *I);       // Dispatch to one of the other add methods...
00308   void add(BasicBlock &BB);       // Add all instructions in basic block
00309   void add(const AliasSetTracker &AST); // Add alias relations from another AST
00310 
00311   /// remove methods - These methods are used to remove all entries that might
00312   /// be aliased by the specified instruction.  These methods return true if any
00313   /// alias sets were eliminated.
00314   bool remove(Value *Ptr, unsigned Size);  // Remove a location
00315   bool remove(LoadInst *LI);
00316   bool remove(StoreInst *SI);
00317   bool remove(FreeInst *FI);
00318   bool remove(VAArgInst *VAAI);
00319   bool remove(CallSite CS);
00320   bool remove(CallInst *CI)   { return remove(CallSite(CI)); }
00321   bool remove(InvokeInst *II) { return remove(CallSite(II)); }
00322   bool remove(Instruction *I);
00323   void remove(AliasSet &AS);
00324   
00325   void clear();
00326 
00327   /// getAliasSets - Return the alias sets that are active.
00328   ///
00329   const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
00330 
00331   /// getAliasSetForPointer - Return the alias set that the specified pointer
00332   /// lives in.  If the New argument is non-null, this method sets the value to
00333   /// true if a new alias set is created to contain the pointer (because the
00334   /// pointer didn't alias anything).
00335   AliasSet &getAliasSetForPointer(Value *P, unsigned Size, bool *New = 0);
00336 
00337   /// getAliasSetForPointerIfExists - Return the alias set containing the
00338   /// location specified if one exists, otherwise return null.
00339   AliasSet *getAliasSetForPointerIfExists(Value *P, unsigned Size) {
00340     return findAliasSetForPointer(P, Size);
00341   }
00342 
00343   /// containsPointer - Return true if the specified location is represented by
00344   /// this alias set, false otherwise.  This does not modify the AST object or
00345   /// alias sets.
00346   bool containsPointer(Value *P, unsigned Size) const;
00347 
00348   /// getAliasAnalysis - Return the underlying alias analysis object used by
00349   /// this tracker.
00350   AliasAnalysis &getAliasAnalysis() const { return AA; }
00351 
00352   /// deleteValue method - This method is used to remove a pointer value from
00353   /// the AliasSetTracker entirely.  It should be used when an instruction is
00354   /// deleted from the program to update the AST.  If you don't use this, you
00355   /// would have dangling pointers to deleted instructions.
00356   ///
00357   void deleteValue(Value *PtrVal);
00358 
00359   /// copyValue - This method should be used whenever a preexisting value in the
00360   /// program is copied or cloned, introducing a new value.  Note that it is ok
00361   /// for clients that use this method to introduce the same value multiple
00362   /// times: if the tracker already knows about a value, it will ignore the
00363   /// request.
00364   ///
00365   void copyValue(Value *From, Value *To);
00366 
00367 
00368   typedef ilist<AliasSet>::iterator iterator;
00369   typedef ilist<AliasSet>::const_iterator const_iterator;
00370 
00371   const_iterator begin() const { return AliasSets.begin(); }
00372   const_iterator end()   const { return AliasSets.end(); }
00373 
00374   iterator begin() { return AliasSets.begin(); }
00375   iterator end()   { return AliasSets.end(); }
00376 
00377   void print(std::ostream &OS) const;
00378   void print(std::ostream *OS) const { if (OS) print(*OS); }
00379   void dump() const;
00380 
00381 private:
00382   friend class AliasSet;
00383   void removeAliasSet(AliasSet *AS);
00384 
00385   // getEntryFor - Just like operator[] on the map, except that it creates an
00386   // entry for the pointer if it doesn't already exist.
00387   AliasSet::PointerRec &getEntryFor(Value *V) {
00388     AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
00389     if (Entry == 0)
00390       Entry = new AliasSet::PointerRec(V);
00391     return *Entry;
00392   }
00393 
00394   AliasSet &addPointer(Value *P, unsigned Size, AliasSet::AccessType E,
00395                        bool &NewSet) {
00396     NewSet = false;
00397     AliasSet &AS = getAliasSetForPointer(P, Size, &NewSet);
00398     AS.AccessTy |= E;
00399     return AS;
00400   }
00401   AliasSet *findAliasSetForPointer(const Value *Ptr, unsigned Size);
00402 
00403   AliasSet *findAliasSetForCallSite(CallSite CS);
00404 };
00405 
00406 inline std::ostream& operator<<(std::ostream &OS, const AliasSetTracker &AST) {
00407   AST.print(OS);
00408   return OS;
00409 }
00410 
00411 } // End llvm namespace
00412 
00413 #endif