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