include/llvm/Analysis/AliasSetTracker.h

   1 //===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines two classes: AliasSetTracker and AliasSet. These interfaces
  10 // are used to classify a collection of pointer references into a maximal number
  11 // of disjoint sets. Each AliasSet object constructed by the AliasSetTracker
  12 // object refers to memory disjoint from the other sets.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H
  17 #define LLVM_ANALYSIS_ALIASSETTRACKER_H
  18
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/DenseMapInfo.h"
  21 #include "llvm/ADT/ilist.h"
  22 #include "llvm/ADT/ilist_node.h"
  23 #include "llvm/Analysis/AliasAnalysis.h"
  24 #include "llvm/IR/Instruction.h"
  25 #include "llvm/IR/Metadata.h"
  26 #include "llvm/IR/ValueHandle.h"
  27 #include "llvm/Support/Casting.h"
  28 #include <cassert>
  29 #include <cstddef>
  30 #include <cstdint>
  31 #include <iterator>
  32 #include <vector>
  33
  34 namespace llvm {
  35
  36 class AliasSetTracker;
  37 class BasicBlock;
  38 class LoadInst;
  39 class Loop;
  40 class MemorySSA;
  41 class AnyMemSetInst;
  42 class AnyMemTransferInst;
  43 class raw_ostream;
  44 class StoreInst;
  45 class VAArgInst;
  46 class Value;
  47
  48 class AliasSet : public ilist_node<AliasSet> {
  49   friend class AliasSetTracker;
  50
  51   class PointerRec {
  52     Value *Val;  // The pointer this record corresponds to.
  53     PointerRec **PrevInList = nullptr;
  54     PointerRec *NextInList = nullptr;
  55     AliasSet *AS = nullptr;
  56     LocationSize Size = LocationSize::mapEmpty();
  57     AAMDNodes AAInfo;
  58
  59     // Whether the size for this record has been set at all. This makes no
  60     // guarantees about the size being known.
  61     bool isSizeSet() const { return Size != LocationSize::mapEmpty(); }
  62
  63   public:
  64     PointerRec(Value *V)
  65       : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}
  66
  67     Value *getValue() const { return Val; }
  68
  69     PointerRec *getNext() const { return NextInList; }
  70     bool hasAliasSet() const { return AS != nullptr; }
  71
  72     PointerRec** setPrevInList(PointerRec **PIL) {
  73       PrevInList = PIL;
  74       return &NextInList;
  75     }
  76
  77     bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
  78       bool SizeChanged = false;
  79       if (NewSize != Size) {
  80         LocationSize OldSize = Size;
  81         Size = isSizeSet() ? Size.unionWith(NewSize) : NewSize;
  82         SizeChanged = OldSize != Size;
  83       }
  84
  85       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
  86         // We don't have a AAInfo yet. Set it to NewAAInfo.
  87         AAInfo = NewAAInfo;
  88       else {
  89         AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
  90         if (!Intersection.TBAA || !Intersection.Scope ||
  91             !Intersection.NoAlias) {
  92           // NewAAInfo conflicts with AAInfo.
  93           AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
  94           SizeChanged = true;
  95         }
  96         AAInfo = Intersection;
  97       }
  98       return SizeChanged;
  99     }
 100
 101     LocationSize getSize() const {
 102       assert(isSizeSet() && "Getting an unset size!");
 103       return Size;
 104     }
 105
 106     /// Return the AAInfo, or null if there is no information or conflicting
 107     /// information.
 108     AAMDNodes getAAInfo() const {
 109       // If we have missing or conflicting AAInfo, return null.
 110       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
 111           AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey())
 112         return AAMDNodes();
 113       return AAInfo;
 114     }
 115
 116     AliasSet *getAliasSet(AliasSetTracker &AST) {
 117       assert(AS && "No AliasSet yet!");
 118       if (AS->Forward) {
 119         AliasSet *OldAS = AS;
 120         AS = OldAS->getForwardedTarget(AST);
 121         AS->addRef();
 122         OldAS->dropRef(AST);
 123       }
 124       return AS;
 125     }
 126
 127     void setAliasSet(AliasSet *as) {
 128       assert(!AS && "Already have an alias set!");
 129       AS = as;
 130     }
 131
 132     void eraseFromList() {
 133       if (NextInList) NextInList->PrevInList = PrevInList;
 134       *PrevInList = NextInList;
 135       if (AS->PtrListEnd == &NextInList) {
 136         AS->PtrListEnd = PrevInList;
 137         assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
 138       }
 139       delete this;
 140     }
 141   };
 142
 143   // Doubly linked list of nodes.
 144   PointerRec *PtrList = nullptr;
 145   PointerRec **PtrListEnd;
 146   // Forwarding pointer.
 147   AliasSet *Forward = nullptr;
 148
 149   /// All instructions without a specific address in this alias set.
 150   /// In rare cases this vector can have a null'ed out WeakVH
 151   /// instances (can happen if some other loop pass deletes an
 152   /// instruction in this list).
 153   std::vector<WeakVH> UnknownInsts;
 154
 155   /// Number of nodes pointing to this AliasSet plus the number of AliasSets
 156   /// forwarding to it.
 157   unsigned RefCount : 27;
 158
 159   // Signifies that this set should be considered to alias any pointer.
 160   // Use when the tracker holding this set is saturated.
 161   unsigned AliasAny : 1;
 162
 163   /// The kinds of access this alias set models.
 164   ///
 165   /// We keep track of whether this alias set merely refers to the locations of
 166   /// memory (and not any particular access), whether it modifies or references
 167   /// the memory, or whether it does both. The lattice goes from "NoAccess" to
 168   /// either RefAccess or ModAccess, then to ModRefAccess as necessary.
 169   enum AccessLattice {
 170     NoAccess = 0,
 171     RefAccess = 1,
 172     ModAccess = 2,
 173     ModRefAccess = RefAccess | ModAccess
 174   };
 175   unsigned Access : 2;
 176
 177   /// The kind of alias relationship between pointers of the set.
 178   ///
 179   /// These represent conservatively correct alias results between any members
 180   /// of the set. We represent these independently of the values of alias
 181   /// results in order to pack it into a single bit. Lattice goes from
 182   /// MustAlias to MayAlias.
 183   enum AliasLattice {
 184     SetMustAlias = 0, SetMayAlias = 1
 185   };
 186   unsigned Alias : 1;
 187
 188   unsigned SetSize = 0;
 189
 190   void addRef() { ++RefCount; }
 191
 192   void dropRef(AliasSetTracker &AST) {
 193     assert(RefCount >= 1 && "Invalid reference count detected!");
 194     if (--RefCount == 0)
 195       removeFromTracker(AST);
 196   }
 197
 198   Instruction *getUnknownInst(unsigned i) const {
 199     assert(i < UnknownInsts.size());
 200     return cast_or_null<Instruction>(UnknownInsts[i]);
 201   }
 202
 203 public:
 204   AliasSet(const AliasSet &) = delete;
 205   AliasSet &operator=(const AliasSet &) = delete;
 206
 207   /// Accessors...
 208   bool isRef() const { return Access & RefAccess; }
 209   bool isMod() const { return Access & ModAccess; }
 210   bool isMustAlias() const { return Alias == SetMustAlias; }
 211   bool isMayAlias()  const { return Alias == SetMayAlias; }
 212
 213   /// Return true if this alias set should be ignored as part of the
 214   /// AliasSetTracker object.
 215   bool isForwardingAliasSet() const { return Forward; }
 216
 217   /// Merge the specified alias set into this alias set.
 218   void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
 219
 220   // Alias Set iteration - Allow access to all of the pointers which are part of
 221   // this alias set.
 222   class iterator;
 223   iterator begin() const { return iterator(PtrList); }
 224   iterator end()   const { return iterator(); }
 225   bool empty() const { return PtrList == nullptr; }
 226
 227   // Unfortunately, ilist::size() is linear, so we have to add code to keep
 228   // track of the list's exact size.
 229   unsigned size() { return SetSize; }
 230
 231   /// If this alias set is known to contain a single instruction and *only* a
 232   /// single unique instruction, return it.  Otherwise, return nullptr.
 233   Instruction* getUniqueInstruction();
 234
 235   void print(raw_ostream &OS) const;
 236   void dump() const;
 237
 238   /// Define an iterator for alias sets... this is just a forward iterator.
 239   class iterator : public std::iterator<std::forward_iterator_tag,
 240                                         PointerRec, ptrdiff_t> {
 241     PointerRec *CurNode;
 242
 243   public:
 244     explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {}
 245
 246     bool operator==(const iterator& x) const {
 247       return CurNode == x.CurNode;
 248     }
 249     bool operator!=(const iterator& x) const { return !operator==(x); }
 250
 251     value_type &operator*() const {
 252       assert(CurNode && "Dereferencing AliasSet.end()!");
 253       return *CurNode;
 254     }
 255     value_type *operator->() const { return &operator*(); }
 256
 257     Value *getPointer() const { return CurNode->getValue(); }
 258     LocationSize getSize() const { return CurNode->getSize(); }
 259     AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
 260
 261     iterator& operator++() {                // Preincrement
 262       assert(CurNode && "Advancing past AliasSet.end()!");
 263       CurNode = CurNode->getNext();
 264       return *this;
 265     }
 266     iterator operator++(int) { // Postincrement
 267       iterator tmp = *this; ++*this; return tmp;
 268     }
 269   };
 270
 271 private:
 272   // Can only be created by AliasSetTracker.
 273   AliasSet()
 274       : PtrListEnd(&PtrList), RefCount(0),  AliasAny(false), Access(NoAccess),
 275         Alias(SetMustAlias) {}
 276
 277   PointerRec *getSomePointer() const {
 278     return PtrList;
 279   }
 280
 281   /// Return the real alias set this represents. If this has been merged with
 282   /// another set and is forwarding, return the ultimate destination set. This
 283   /// also implements the union-find collapsing as well.
 284   AliasSet *getForwardedTarget(AliasSetTracker &AST) {
 285     if (!Forward) return this;
 286
 287     AliasSet *Dest = Forward->getForwardedTarget(AST);
 288     if (Dest != Forward) {
 289       Dest->addRef();
 290       Forward->dropRef(AST);
 291       Forward = Dest;
 292     }
 293     return Dest;
 294   }
 295
 296   void removeFromTracker(AliasSetTracker &AST);
 297
 298   void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size,
 299                   const AAMDNodes &AAInfo, bool KnownMustAlias = false,
 300                   bool SkipSizeUpdate = false);
 301   void addUnknownInst(Instruction *I, AliasAnalysis &AA);
 302
 303   void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
 304     bool WasEmpty = UnknownInsts.empty();
 305     for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
 306       if (UnknownInsts[i] == I) {
 307         UnknownInsts[i] = UnknownInsts.back();
 308         UnknownInsts.pop_back();
 309         --i; --e;  // Revisit the moved entry.
 310       }
 311     if (!WasEmpty && UnknownInsts.empty())
 312       dropRef(AST);
 313   }
 314
 315 public:
 316   /// If the specified pointer "may" (or must) alias one of the members in the
 317   /// set return the appropriate AliasResult. Otherwise return NoAlias.
 318   AliasResult aliasesPointer(const Value *Ptr, LocationSize Size,
 319                              const AAMDNodes &AAInfo, AliasAnalysis &AA) const;
 320   bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
 321 };
 322
 323 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
 324   AS.print(OS);
 325   return OS;
 326 }
 327
 328 class AliasSetTracker {
 329   /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a
 330   /// Value is deleted.
 331   class ASTCallbackVH final : public CallbackVH {
 332     AliasSetTracker *AST;
 333
 334     void deleted() override;
 335     void allUsesReplacedWith(Value *) override;
 336
 337   public:
 338     ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);
 339
 340     ASTCallbackVH &operator=(Value *V);
 341   };
 342   /// Traits to tell DenseMap that tell us how to compare and hash the value
 343   /// handle.
 344   struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
 345
 346   AliasAnalysis &AA;
 347   MemorySSA *MSSA;
 348   Loop *L;
 349   ilist<AliasSet> AliasSets;
 350
 351   using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *,
 352                                   ASTCallbackVHDenseMapInfo>;
 353
 354   // Map from pointers to their node
 355   PointerMapType PointerMap;
 356
 357 public:
 358   /// Create an empty collection of AliasSets, and use the specified alias
 359   /// analysis object to disambiguate load and store addresses.
 360   explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
 361   explicit AliasSetTracker(AliasAnalysis &aa, MemorySSA *mssa, Loop *l)
 362       : AA(aa), MSSA(mssa), L(l) {}
 363   ~AliasSetTracker() { clear(); }
 364
 365   /// These methods are used to add different types of instructions to the alias
 366   /// sets. Adding a new instruction can result in one of three actions
 367   /// happening:
 368   ///
 369   ///   1. If the instruction doesn't alias any other sets, create a new set.
 370   ///   2. If the instruction aliases exactly one set, add it to the set
 371   ///   3. If the instruction aliases multiple sets, merge the sets, and add
 372   ///      the instruction to the result.
 373   ///
 374   /// These methods return true if inserting the instruction resulted in the
 375   /// addition of a new alias set (i.e., the pointer did not alias anything).
 376   ///
 377   void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc
 378   void add(LoadInst *LI);
 379   void add(StoreInst *SI);
 380   void add(VAArgInst *VAAI);
 381   void add(AnyMemSetInst *MSI);
 382   void add(AnyMemTransferInst *MTI);
 383   void add(Instruction *I);       // Dispatch to one of the other add methods...
 384   void add(BasicBlock &BB);       // Add all instructions in basic block
 385   void add(const AliasSetTracker &AST); // Add alias relations from another AST
 386   void addUnknown(Instruction *I);
 387   void addAllInstructionsInLoopUsingMSSA();
 388
 389   void clear();
 390
 391   /// Return the alias sets that are active.
 392   const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
 393
 394   /// Return the alias set which contains the specified memory location.  If
 395   /// the memory location aliases two or more existing alias sets, will have
 396   /// the effect of merging those alias sets before the single resulting alias
 397   /// set is returned.
 398   AliasSet &getAliasSetFor(const MemoryLocation &MemLoc);
 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(MemoryLocation Loc, AliasSet::AccessLattice E);
 449   AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
 450                                      const AAMDNodes &AAInfo,
 451                                      bool &MustAliasAll);
 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