include/llvm/Analysis/AliasSetTracker.h

   1 //===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===//
   2 //
   3 // This file defines two classes: AliasSetTracker and AliasSet.  These interface
   4 // are used to classify a collection of pointer references into a maximal number
   5 // of disjoint sets.  Each AliasSet object constructed by the AliasSetTracker
   6 // object refers to memory disjoint from the other sets.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H
  11 #define LLVM_ANALYSIS_ALIASSETTRACKER_H
  12
  13 #include <assert.h>
  14
  15 #include "llvm/Support/CallSite.h"
  16 #include "Support/iterator"
  17 #include "Support/hash_map"
  18 #include "Support/ilist"
  19 class AliasAnalysis;
  20 class LoadInst;
  21 class StoreInst;
  22 class AliasSetTracker;
  23 class AliasSet;
  24
  25 class AliasSet {
  26   friend class AliasSetTracker;
  27
  28   struct PointerRec;
  29   typedef std::pair<Value* const, PointerRec> HashNodePair;
  30
  31   class PointerRec {
  32     HashNodePair *NextInList;
  33     AliasSet *AS;
  34     unsigned Size;
  35   public:
  36     PointerRec() : NextInList(0), AS(0), Size(0) {}
  37
  38     HashNodePair *getNext() const { return NextInList; }
  39     bool hasAliasSet() const { return AS != 0; }
  40
  41     void updateSize(unsigned NewSize) {
  42       if (NewSize > Size) Size = NewSize;
  43     }
  44
  45     unsigned getSize() const { return Size; }
  46
  47     AliasSet *getAliasSet(AliasSetTracker &AST) {
  48       assert(AS && "No AliasSet yet!");
  49       if (AS->Forward) {
  50         AliasSet *OldAS = AS;
  51         AS = OldAS->getForwardedTarget(AST);
  52         if (--OldAS->RefCount == 0)
  53           OldAS->removeFromTracker(AST);
  54         AS->RefCount++;
  55       }
  56       return AS;
  57     }
  58
  59     void setAliasSet(AliasSet *as) {
  60       assert(AS == 0 && "Already have an alias set!");
  61       AS = as;
  62     }
  63     void setTail(HashNodePair *T) {
  64       assert(NextInList == 0 && "Already have tail!");
  65       NextInList = T;
  66     }
  67   };
  68
  69   HashNodePair *PtrListHead, *PtrListTail; // Singly linked list of nodes
  70   AliasSet *Forward;             // Forwarding pointer
  71   AliasSet *Next, *Prev;         // Doubly linked list of AliasSets
  72
  73   std::vector<CallSite> CallSites; // All calls & invokes in this node
  74
  75   // RefCount - Number of nodes pointing to this AliasSet plus the number of
  76   // AliasSets forwarding to it.
  77   unsigned RefCount : 29;
  78
  79   /// AccessType - Keep track of whether this alias set merely refers to the
  80   /// locations of memory, whether it modifies the memory, or whether it does
  81   /// both.  The lattice goes from "NoModRef" to either Refs or Mods, then to
  82   /// ModRef as neccesary.
  83   ///
  84   enum AccessType {
  85     NoModRef = 0, Refs = 1,         // Ref = bit 1
  86     Mods     = 2, ModRef = 3        // Mod = bit 2
  87   };
  88   unsigned AccessTy : 2;
  89
  90   /// AliasType - Keep track the relationships between the pointers in the set.
  91   /// Lattice goes from MustAlias to MayAlias.
  92   ///
  93   enum AliasType {
  94     MustAlias = 0, MayAlias = 1
  95   };
  96   unsigned AliasTy : 1;
  97
  98   friend class ilist_traits<AliasSet>;
  99   AliasSet *getPrev() const { return Prev; }
 100   AliasSet *getNext() const { return Next; }
 101   void setPrev(AliasSet *P) { Prev = P; }
 102   void setNext(AliasSet *N) { Next = N; }
 103
 104 public:
 105   /// Accessors...
 106   bool isRef() const { return AccessTy & Refs; }
 107   bool isMod() const { return AccessTy & Mods; }
 108   bool isMustAlias() const { return AliasTy == MustAlias; }
 109   bool isMayAlias()  const { return AliasTy == MayAlias; }
 110
 111   /// isForwardingAliasSet - Return true if this alias set should be ignored as
 112   /// part of the AliasSetTracker object.
 113   bool isForwardingAliasSet() const { return Forward; }
 114
 115   /// mergeSetIn - Merge the specified alias set into this alias set...
 116   ///
 117   void mergeSetIn(AliasSet &AS);
 118
 119   // Alias Set iteration - Allow access to all of the pointer which are part of
 120   // this alias set...
 121   class iterator;
 122   iterator begin() const { return iterator(PtrListHead); }
 123   iterator end()   const { return iterator(); }
 124
 125   void print(std::ostream &OS) const;
 126   void dump() const;
 127
 128   /// Define an iterator for alias sets... this is just a forward iterator.
 129   class iterator : public forward_iterator<HashNodePair, ptrdiff_t> {
 130     HashNodePair *CurNode;
 131   public:
 132     iterator(HashNodePair *CN = 0) : CurNode(CN) {}
 133
 134     bool operator==(const iterator& x) const {
 135       return CurNode == x.CurNode;
 136     }
 137     bool operator!=(const iterator& x) const { return !operator==(x); }
 138
 139     const iterator &operator=(const iterator &I) {
 140       CurNode = I.CurNode;
 141       return *this;
 142     }
 143
 144     value_type &operator*() const {
 145       assert(CurNode && "Dereferencing AliasSet.end()!");
 146       return *CurNode;
 147     }
 148     value_type *operator->() const { return &operator*(); }
 149
 150     iterator& operator++() {                // Preincrement
 151       assert(CurNode && "Advancing past AliasSet.end()!");
 152       CurNode = CurNode->second.getNext();
 153       return *this;
 154     }
 155     iterator operator++(int) { // Postincrement
 156       iterator tmp = *this; ++*this; return tmp;
 157     }
 158   };
 159
 160 private:
 161   // Can only be created by AliasSetTracker
 162   AliasSet() : PtrListHead(0), PtrListTail(0), Forward(0), RefCount(0),
 163                AccessTy(NoModRef), AliasTy(MustAlias) {
 164   }
 165   HashNodePair *getSomePointer() const {
 166     return PtrListHead ? PtrListHead : 0;
 167   }
 168
 169   /// getForwardedTarget - Return the real alias set this represents.  If this
 170   /// has been merged with another set and is forwarding, return the ultimate
 171   /// destination set.  This also implements the union-find collapsing as well.
 172   AliasSet *getForwardedTarget(AliasSetTracker &AST) {
 173     if (!Forward) return this;
 174
 175     AliasSet *Dest = Forward->getForwardedTarget(AST);
 176     if (Dest != Forward) {
 177       Dest->RefCount++;
 178       if (--Forward->RefCount == 0)
 179         Forward->removeFromTracker(AST);
 180       Forward = Dest;
 181     }
 182     return Dest;
 183   }
 184
 185   void removeFromTracker(AliasSetTracker &AST);
 186
 187   void addPointer(AliasSetTracker &AST, HashNodePair &Entry, unsigned Size);
 188   void addCallSite(CallSite CS);
 189
 190   /// aliasesPointer - Return true if the specified pointer "may" (or must)
 191   /// alias one of the members in the set.
 192   ///
 193   bool aliasesPointer(const Value *Ptr, unsigned Size, AliasAnalysis &AA) const;
 194   bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const;
 195 };
 196
 197 inline std::ostream& operator<<(std::ostream &OS, const AliasSet &AS) {
 198   AS.print(OS);
 199   return OS;
 200 }
 201
 202
 203 class AliasSetTracker {
 204   AliasAnalysis &AA;
 205   ilist<AliasSet> AliasSets;
 206
 207   // Map from pointers to their node
 208   hash_map<Value*, AliasSet::PointerRec> PointerMap;
 209 public:
 210   /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use
 211   /// the specified alias analysis object to disambiguate load and store
 212   /// addresses.
 213   AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
 214
 215   /// add methods - These methods are used to add different types of
 216   /// instructions to the alias sets.  Adding a new instruction can result in
 217   /// one of three actions happening:
 218   ///
 219   ///   1. If the instruction doesn't alias any other sets, create a new set.
 220   ///   2. If the instruction aliases exactly one set, add it to the set
 221   ///   3. If the instruction aliases multiple sets, merge the sets, and add
 222   ///      the instruction to the result.
 223   ///
 224   void add(LoadInst *LI);
 225   void add(StoreInst *SI);
 226   void add(CallSite CS);          // Call/Invoke instructions
 227   void add(CallInst *CI)   { add(CallSite(CI)); }
 228   void add(InvokeInst *II) { add(CallSite(II)); }
 229   void add(Instruction *I);       // Dispatch to one of the other add methods...
 230   void add(BasicBlock &BB);       // Add all instructions in basic block
 231   void add(const AliasSetTracker &AST); // Add alias relations from another AST
 232
 233   /// getAliasSets - Return the alias sets that are active.
 234   const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
 235
 236   /// getAliasSetForPointer - Return the alias set that the specified pointer
 237   /// lives in...
 238   AliasSet &getAliasSetForPointer(Value *P, unsigned Size);
 239
 240   /// getAliasAnalysis - Return the underlying alias analysis object used by
 241   /// this tracker.
 242   AliasAnalysis &getAliasAnalysis() const { return AA; }
 243
 244   typedef ilist<AliasSet>::iterator iterator;
 245   typedef ilist<AliasSet>::const_iterator const_iterator;
 246
 247   const_iterator begin() const { return AliasSets.begin(); }
 248   const_iterator end()   const { return AliasSets.end(); }
 249
 250   iterator begin() { return AliasSets.begin(); }
 251   iterator end()   { return AliasSets.end(); }
 252
 253   void print(std::ostream &OS) const;
 254   void dump() const;
 255
 256 private:
 257   friend class AliasSet;
 258   void removeAliasSet(AliasSet *AS);
 259
 260   AliasSet::HashNodePair &getEntryFor(Value *V) {
 261     // Standard operator[], except that it returns the whole pair, not just
 262     // ->second.
 263     return *PointerMap.insert(AliasSet::HashNodePair(V,
 264                                             AliasSet::PointerRec())).first;
 265   }
 266
 267   void addPointer(Value *P, unsigned Size, AliasSet::AccessType E) {
 268     AliasSet &AS = getAliasSetForPointer(P, Size);
 269     AS.AccessTy |= E;
 270   }
 271   AliasSet *findAliasSetForPointer(const Value *Ptr, unsigned Size);
 272
 273   AliasSet *findAliasSetForCallSite(CallSite CS);
 274 };
 275
 276 inline std::ostream& operator<<(std::ostream &OS, const AliasSetTracker &AST) {
 277   AST.print(OS);
 278   return OS;
 279 }
 280
 281 #endif