include/llvm/Analysis/AliasSetTracker.h

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