contrib/llvm/include/llvm/Analysis/AliasSetTracker.h

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