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