Home | History | Annotate | Download | only in Analysis
      1 //===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // 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 "llvm/Support/ValueHandle.h"
     22 #include "llvm/ADT/DenseMap.h"
     23 #include "llvm/ADT/ilist.h"
     24 #include "llvm/ADT/ilist_node.h"
     25 #include <vector>
     26 
     27 namespace llvm {
     28 
     29 class AliasAnalysis;
     30 class LoadInst;
     31 class StoreInst;
     32 class VAArgInst;
     33 class AliasSetTracker;
     34 class AliasSet;
     35 
     36 class AliasSet : public ilist_node<AliasSet> {
     37   friend class AliasSetTracker;
     38 
     39   class PointerRec {
     40     Value *Val;  // The pointer this record corresponds to.
     41     PointerRec **PrevInList, *NextInList;
     42     AliasSet *AS;
     43     uint64_t Size;
     44     const MDNode *TBAAInfo;
     45   public:
     46     PointerRec(Value *V)
     47       : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0),
     48         TBAAInfo(DenseMapInfo<const MDNode *>::getEmptyKey()) {}
     49 
     50     Value *getValue() const { return Val; }
     51 
     52     PointerRec *getNext() const { return NextInList; }
     53     bool hasAliasSet() const { return AS != 0; }
     54 
     55     PointerRec** setPrevInList(PointerRec **PIL) {
     56       PrevInList = PIL;
     57       return &NextInList;
     58     }
     59 
     60     void updateSizeAndTBAAInfo(uint64_t NewSize, const MDNode *NewTBAAInfo) {
     61       if (NewSize > Size) Size = NewSize;
     62 
     63       if (TBAAInfo == DenseMapInfo<const MDNode *>::getEmptyKey())
     64         // We don't have a TBAAInfo yet. Set it to NewTBAAInfo.
     65         TBAAInfo = NewTBAAInfo;
     66       else if (TBAAInfo != NewTBAAInfo)
     67         // NewTBAAInfo conflicts with TBAAInfo.
     68         TBAAInfo = DenseMapInfo<const MDNode *>::getTombstoneKey();
     69     }
     70 
     71     uint64_t getSize() const { return Size; }
     72 
     73     /// getTBAAInfo - Return the TBAAInfo, or null if there is no
     74     /// information or conflicting information.
     75     const MDNode *getTBAAInfo() const {
     76       // If we have missing or conflicting TBAAInfo, return null.
     77       if (TBAAInfo == DenseMapInfo<const MDNode *>::getEmptyKey() ||
     78           TBAAInfo == DenseMapInfo<const MDNode *>::getTombstoneKey())
     79         return 0;
     80       return TBAAInfo;
     81     }
     82 
     83     AliasSet *getAliasSet(AliasSetTracker &AST) {
     84       assert(AS && "No AliasSet yet!");
     85       if (AS->Forward) {
     86         AliasSet *OldAS = AS;
     87         AS = OldAS->getForwardedTarget(AST);
     88         AS->addRef();
     89         OldAS->dropRef(AST);
     90       }
     91       return AS;
     92     }
     93 
     94     void setAliasSet(AliasSet *as) {
     95       assert(AS == 0 && "Already have an alias set!");
     96       AS = as;
     97     }
     98 
     99     void eraseFromList() {
    100       if (NextInList) NextInList->PrevInList = PrevInList;
    101       *PrevInList = NextInList;
    102       if (AS->PtrListEnd == &NextInList) {
    103         AS->PtrListEnd = PrevInList;
    104         assert(*AS->PtrListEnd == 0 && "List not terminated right!");
    105       }
    106       delete this;
    107     }
    108   };
    109 
    110   PointerRec *PtrList, **PtrListEnd;  // Doubly linked list of nodes.
    111   AliasSet *Forward;             // Forwarding pointer.
    112   AliasSet *Next, *Prev;         // Doubly linked list of AliasSets.
    113 
    114   // All instructions without a specific address in this alias set.
    115   std::vector<AssertingVH<Instruction> > UnknownInsts;
    116 
    117   // RefCount - Number of nodes pointing to this AliasSet plus the number of
    118   // AliasSets forwarding to it.
    119   unsigned RefCount : 28;
    120 
    121   /// AccessType - Keep track of whether this alias set merely refers to the
    122   /// locations of memory, whether it modifies the memory, or whether it does
    123   /// both.  The lattice goes from "NoModRef" to either Refs or Mods, then to
    124   /// ModRef as necessary.
    125   ///
    126   enum AccessType {
    127     NoModRef = 0, Refs = 1,         // Ref = bit 1
    128     Mods     = 2, ModRef = 3        // Mod = bit 2
    129   };
    130   unsigned AccessTy : 2;
    131 
    132   /// AliasType - Keep track the relationships between the pointers in the set.
    133   /// Lattice goes from MustAlias to MayAlias.
    134   ///
    135   enum AliasType {
    136     MustAlias = 0, MayAlias = 1
    137   };
    138   unsigned AliasTy : 1;
    139 
    140   // Volatile - True if this alias set contains volatile loads or stores.
    141   bool Volatile : 1;
    142 
    143   void addRef() { ++RefCount; }
    144   void dropRef(AliasSetTracker &AST) {
    145     assert(RefCount >= 1 && "Invalid reference count detected!");
    146     if (--RefCount == 0)
    147       removeFromTracker(AST);
    148   }
    149 
    150   Instruction *getUnknownInst(unsigned i) const {
    151     assert(i < UnknownInsts.size());
    152     return UnknownInsts[i];
    153   }
    154 
    155 public:
    156   /// Accessors...
    157   bool isRef() const { return AccessTy & Refs; }
    158   bool isMod() const { return AccessTy & Mods; }
    159   bool isMustAlias() const { return AliasTy == MustAlias; }
    160   bool isMayAlias()  const { return AliasTy == MayAlias; }
    161 
    162   // isVolatile - Return true if this alias set contains volatile loads or
    163   // stores.
    164   bool isVolatile() const { return Volatile; }
    165 
    166   /// isForwardingAliasSet - Return true if this alias set should be ignored as
    167   /// part of the AliasSetTracker object.
    168   bool isForwardingAliasSet() const { return Forward; }
    169 
    170   /// mergeSetIn - Merge the specified alias set into this alias set...
    171   ///
    172   void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
    173 
    174   // Alias Set iteration - Allow access to all of the pointer which are part of
    175   // this alias set...
    176   class iterator;
    177   iterator begin() const { return iterator(PtrList); }
    178   iterator end()   const { return iterator(); }
    179   bool empty() const { return PtrList == 0; }
    180 
    181   void print(raw_ostream &OS) const;
    182   void dump() const;
    183 
    184   /// Define an iterator for alias sets... this is just a forward iterator.
    185   class iterator : public std::iterator<std::forward_iterator_tag,
    186                                         PointerRec, ptrdiff_t> {
    187     PointerRec *CurNode;
    188   public:
    189     explicit iterator(PointerRec *CN = 0) : CurNode(CN) {}
    190 
    191     bool operator==(const iterator& x) const {
    192       return CurNode == x.CurNode;
    193     }
    194     bool operator!=(const iterator& x) const { return !operator==(x); }
    195 
    196     const iterator &operator=(const iterator &I) {
    197       CurNode = I.CurNode;
    198       return *this;
    199     }
    200 
    201     value_type &operator*() const {
    202       assert(CurNode && "Dereferencing AliasSet.end()!");
    203       return *CurNode;
    204     }
    205     value_type *operator->() const { return &operator*(); }
    206 
    207     Value *getPointer() const { return CurNode->getValue(); }
    208     uint64_t getSize() const { return CurNode->getSize(); }
    209     const MDNode *getTBAAInfo() const { return CurNode->getTBAAInfo(); }
    210 
    211     iterator& operator++() {                // Preincrement
    212       assert(CurNode && "Advancing past AliasSet.end()!");
    213       CurNode = CurNode->getNext();
    214       return *this;
    215     }
    216     iterator operator++(int) { // Postincrement
    217       iterator tmp = *this; ++*this; return tmp;
    218     }
    219   };
    220 
    221 private:
    222   // Can only be created by AliasSetTracker. Also, ilist creates one
    223   // to serve as a sentinel.
    224   friend struct ilist_sentinel_traits<AliasSet>;
    225   AliasSet() : PtrList(0), PtrListEnd(&PtrList), Forward(0), RefCount(0),
    226                AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) {
    227   }
    228 
    229   AliasSet(const AliasSet &AS);        // do not implement
    230   void operator=(const AliasSet &AS);  // do not implement
    231 
    232   PointerRec *getSomePointer() const {
    233     return PtrList;
    234   }
    235 
    236   /// getForwardedTarget - Return the real alias set this represents.  If this
    237   /// has been merged with another set and is forwarding, return the ultimate
    238   /// destination set.  This also implements the union-find collapsing as well.
    239   AliasSet *getForwardedTarget(AliasSetTracker &AST) {
    240     if (!Forward) return this;
    241 
    242     AliasSet *Dest = Forward->getForwardedTarget(AST);
    243     if (Dest != Forward) {
    244       Dest->addRef();
    245       Forward->dropRef(AST);
    246       Forward = Dest;
    247     }
    248     return Dest;
    249   }
    250 
    251   void removeFromTracker(AliasSetTracker &AST);
    252 
    253   void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size,
    254                   const MDNode *TBAAInfo,
    255                   bool KnownMustAlias = false);
    256   void addUnknownInst(Instruction *I, AliasAnalysis &AA);
    257   void removeUnknownInst(Instruction *I) {
    258     for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
    259       if (UnknownInsts[i] == I) {
    260         UnknownInsts[i] = UnknownInsts.back();
    261         UnknownInsts.pop_back();
    262         --i; --e;  // Revisit the moved entry.
    263       }
    264   }
    265   void setVolatile() { Volatile = true; }
    266 
    267 public:
    268   /// aliasesPointer - Return true if the specified pointer "may" (or must)
    269   /// alias one of the members in the set.
    270   ///
    271   bool aliasesPointer(const Value *Ptr, uint64_t Size, const MDNode *TBAAInfo,
    272                       AliasAnalysis &AA) const;
    273   bool aliasesUnknownInst(Instruction *Inst, AliasAnalysis &AA) const;
    274 };
    275 
    276 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
    277   AS.print(OS);
    278   return OS;
    279 }
    280 
    281 
    282 class AliasSetTracker {
    283   /// CallbackVH - A CallbackVH to arrange for AliasSetTracker to be
    284   /// notified whenever a Value is deleted.
    285   class ASTCallbackVH : public CallbackVH {
    286     AliasSetTracker *AST;
    287     virtual void deleted();
    288     virtual void allUsesReplacedWith(Value *);
    289   public:
    290     ASTCallbackVH(Value *V, AliasSetTracker *AST = 0);
    291     ASTCallbackVH &operator=(Value *V);
    292   };
    293   /// ASTCallbackVHDenseMapInfo - Traits to tell DenseMap that tell us how to
    294   /// compare and hash the value handle.
    295   struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
    296 
    297   AliasAnalysis &AA;
    298   ilist<AliasSet> AliasSets;
    299 
    300   typedef DenseMap<ASTCallbackVH, AliasSet::PointerRec*,
    301                    ASTCallbackVHDenseMapInfo>
    302     PointerMapType;
    303 
    304   // Map from pointers to their node
    305   PointerMapType PointerMap;
    306 
    307 public:
    308   /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use
    309   /// the specified alias analysis object to disambiguate load and store
    310   /// addresses.
    311   explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
    312   ~AliasSetTracker() { clear(); }
    313 
    314   /// add methods - These methods are used to add different types of
    315   /// instructions to the alias sets.  Adding a new instruction can result in
    316   /// one of three actions happening:
    317   ///
    318   ///   1. If the instruction doesn't alias any other sets, create a new set.
    319   ///   2. If the instruction aliases exactly one set, add it to the set
    320   ///   3. If the instruction aliases multiple sets, merge the sets, and add
    321   ///      the instruction to the result.
    322   ///
    323   /// These methods return true if inserting the instruction resulted in the
    324   /// addition of a new alias set (i.e., the pointer did not alias anything).
    325   ///
    326   bool add(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo); // Add a location
    327   bool add(LoadInst *LI);
    328   bool add(StoreInst *SI);
    329   bool add(VAArgInst *VAAI);
    330   bool add(Instruction *I);       // Dispatch to one of the other add methods...
    331   void add(BasicBlock &BB);       // Add all instructions in basic block
    332   void add(const AliasSetTracker &AST); // Add alias relations from another AST
    333   bool addUnknown(Instruction *I);
    334 
    335   /// remove methods - These methods are used to remove all entries that might
    336   /// be aliased by the specified instruction.  These methods return true if any
    337   /// alias sets were eliminated.
    338   // Remove a location
    339   bool remove(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo);
    340   bool remove(LoadInst *LI);
    341   bool remove(StoreInst *SI);
    342   bool remove(VAArgInst *VAAI);
    343   bool remove(Instruction *I);
    344   void remove(AliasSet &AS);
    345   bool removeUnknown(Instruction *I);
    346 
    347   void clear();
    348 
    349   /// getAliasSets - Return the alias sets that are active.
    350   ///
    351   const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
    352 
    353   /// getAliasSetForPointer - Return the alias set that the specified pointer
    354   /// lives in.  If the New argument is non-null, this method sets the value to
    355   /// true if a new alias set is created to contain the pointer (because the
    356   /// pointer didn't alias anything).
    357   AliasSet &getAliasSetForPointer(Value *P, uint64_t Size,
    358                                   const MDNode *TBAAInfo,
    359                                   bool *New = 0);
    360 
    361   /// getAliasSetForPointerIfExists - Return the alias set containing the
    362   /// location specified if one exists, otherwise return null.
    363   AliasSet *getAliasSetForPointerIfExists(Value *P, uint64_t Size,
    364                                           const MDNode *TBAAInfo) {
    365     return findAliasSetForPointer(P, Size, TBAAInfo);
    366   }
    367 
    368   /// containsPointer - Return true if the specified location is represented by
    369   /// this alias set, false otherwise.  This does not modify the AST object or
    370   /// alias sets.
    371   bool containsPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo) const;
    372 
    373   /// getAliasAnalysis - Return the underlying alias analysis object used by
    374   /// this tracker.
    375   AliasAnalysis &getAliasAnalysis() const { return AA; }
    376 
    377   /// deleteValue method - This method is used to remove a pointer value from
    378   /// the AliasSetTracker entirely.  It should be used when an instruction is
    379   /// deleted from the program to update the AST.  If you don't use this, you
    380   /// would have dangling pointers to deleted instructions.
    381   ///
    382   void deleteValue(Value *PtrVal);
    383 
    384   /// copyValue - This method should be used whenever a preexisting value in the
    385   /// program is copied or cloned, introducing a new value.  Note that it is ok
    386   /// for clients that use this method to introduce the same value multiple
    387   /// times: if the tracker already knows about a value, it will ignore the
    388   /// request.
    389   ///
    390   void copyValue(Value *From, Value *To);
    391 
    392 
    393   typedef ilist<AliasSet>::iterator iterator;
    394   typedef ilist<AliasSet>::const_iterator const_iterator;
    395 
    396   const_iterator begin() const { return AliasSets.begin(); }
    397   const_iterator end()   const { return AliasSets.end(); }
    398 
    399   iterator begin() { return AliasSets.begin(); }
    400   iterator end()   { return AliasSets.end(); }
    401 
    402   void print(raw_ostream &OS) const;
    403   void dump() const;
    404 
    405 private:
    406   friend class AliasSet;
    407   void removeAliasSet(AliasSet *AS);
    408 
    409   // getEntryFor - Just like operator[] on the map, except that it creates an
    410   // entry for the pointer if it doesn't already exist.
    411   AliasSet::PointerRec &getEntryFor(Value *V) {
    412     AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
    413     if (Entry == 0)
    414       Entry = new AliasSet::PointerRec(V);
    415     return *Entry;
    416   }
    417 
    418   AliasSet &addPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo,
    419                        AliasSet::AccessType E,
    420                        bool &NewSet) {
    421     NewSet = false;
    422     AliasSet &AS = getAliasSetForPointer(P, Size, TBAAInfo, &NewSet);
    423     AS.AccessTy |= E;
    424     return AS;
    425   }
    426   AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size,
    427                                    const MDNode *TBAAInfo);
    428 
    429   AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
    430 };
    431 
    432 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
    433   AST.print(OS);
    434   return OS;
    435 }
    436 
    437 } // End llvm namespace
    438 
    439 #endif
    440