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