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