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