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