1 //===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines two classes: AliasSetTracker and AliasSet. These interfaces 11 // are used to classify a collection of pointer references into a maximal number 12 // of disjoint sets. Each AliasSet object constructed by the AliasSetTracker 13 // object refers to memory disjoint from the other sets. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H 18 #define LLVM_ANALYSIS_ALIASSETTRACKER_H 19 20 #include "llvm/ADT/DenseMap.h" 21 #include "llvm/ADT/DenseMapInfo.h" 22 #include "llvm/ADT/ilist.h" 23 #include "llvm/ADT/ilist_node.h" 24 #include "llvm/Analysis/AliasAnalysis.h" 25 #include "llvm/IR/Instruction.h" 26 #include "llvm/IR/Metadata.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 MemSetInst; 41 class MemTransferInst; 42 class raw_ostream; 43 class StoreInst; 44 class VAArgInst; 45 class Value; 46 47 class AliasSet : public ilist_node<AliasSet> { 48 friend class AliasSetTracker; 49 50 class PointerRec { 51 Value *Val; // The pointer this record corresponds to. 52 PointerRec **PrevInList = nullptr; 53 PointerRec *NextInList = nullptr; 54 AliasSet *AS = nullptr; 55 uint64_t Size = 0; 56 AAMDNodes AAInfo; 57 58 public: 59 PointerRec(Value *V) 60 : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {} 61 62 Value *getValue() const { return Val; } 63 64 PointerRec *getNext() const { return NextInList; } 65 bool hasAliasSet() const { return AS != nullptr; } 66 67 PointerRec** setPrevInList(PointerRec **PIL) { 68 PrevInList = PIL; 69 return &NextInList; 70 } 71 72 bool updateSizeAndAAInfo(uint64_t NewSize, const AAMDNodes &NewAAInfo) { 73 bool SizeChanged = false; 74 if (NewSize > Size) { 75 Size = NewSize; 76 SizeChanged = true; 77 } 78 79 if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey()) 80 // We don't have a AAInfo yet. Set it to NewAAInfo. 81 AAInfo = NewAAInfo; 82 else { 83 AAMDNodes Intersection(AAInfo.intersect(NewAAInfo)); 84 if (!Intersection) { 85 // NewAAInfo conflicts with AAInfo. 86 AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey(); 87 return SizeChanged; 88 } 89 AAInfo = Intersection; 90 } 91 return SizeChanged; 92 } 93 94 uint64_t getSize() const { return Size; } 95 96 /// Return the AAInfo, or null if there is no information or conflicting 97 /// information. 98 AAMDNodes getAAInfo() const { 99 // If we have missing or conflicting AAInfo, return null. 100 if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() || 101 AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey()) 102 return AAMDNodes(); 103 return AAInfo; 104 } 105 106 AliasSet *getAliasSet(AliasSetTracker &AST) { 107 assert(AS && "No AliasSet yet!"); 108 if (AS->Forward) { 109 AliasSet *OldAS = AS; 110 AS = OldAS->getForwardedTarget(AST); 111 AS->addRef(); 112 OldAS->dropRef(AST); 113 } 114 return AS; 115 } 116 117 void setAliasSet(AliasSet *as) { 118 assert(!AS && "Already have an alias set!"); 119 AS = as; 120 } 121 122 void eraseFromList() { 123 if (NextInList) NextInList->PrevInList = PrevInList; 124 *PrevInList = NextInList; 125 if (AS->PtrListEnd == &NextInList) { 126 AS->PtrListEnd = PrevInList; 127 assert(*AS->PtrListEnd == nullptr && "List not terminated right!"); 128 } 129 delete this; 130 } 131 }; 132 133 // Doubly linked list of nodes. 134 PointerRec *PtrList = nullptr; 135 PointerRec **PtrListEnd; 136 // Forwarding pointer. 137 AliasSet *Forward = nullptr; 138 139 /// All instructions without a specific address in this alias set. 140 /// In rare cases this vector can have a null'ed out WeakVH 141 /// instances (can happen if some other loop pass deletes an 142 /// instruction in this list). 143 std::vector<WeakVH> UnknownInsts; 144 145 /// Number of nodes pointing to this AliasSet plus the number of AliasSets 146 /// forwarding to it. 147 unsigned RefCount : 27; 148 149 // Signifies that this set should be considered to alias any pointer. 150 // Use when the tracker holding this set is saturated. 151 unsigned AliasAny : 1; 152 153 /// The kinds of access this alias set models. 154 /// 155 /// We keep track of whether this alias set merely refers to the locations of 156 /// memory (and not any particular access), whether it modifies or references 157 /// the memory, or whether it does both. The lattice goes from "NoAccess" to 158 /// either RefAccess or ModAccess, then to ModRefAccess as necessary. 159 enum AccessLattice { 160 NoAccess = 0, 161 RefAccess = 1, 162 ModAccess = 2, 163 ModRefAccess = RefAccess | ModAccess 164 }; 165 unsigned Access : 2; 166 167 /// The kind of alias relationship between pointers of the set. 168 /// 169 /// These represent conservatively correct alias results between any members 170 /// of the set. We represent these independently of the values of alias 171 /// results in order to pack it into a single bit. Lattice goes from 172 /// MustAlias to MayAlias. 173 enum AliasLattice { 174 SetMustAlias = 0, SetMayAlias = 1 175 }; 176 unsigned Alias : 1; 177 178 /// True if this alias set contains volatile loads or stores. 179 unsigned Volatile : 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 contains volatile loads or stores. 207 bool isVolatile() const { return Volatile; } 208 209 /// Return true if this alias set should be ignored as part of the 210 /// AliasSetTracker object. 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; 219 iterator begin() const { return iterator(PtrList); } 220 iterator end() const { return iterator(); } 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. 225 unsigned size() { return SetSize; } 226 227 void print(raw_ostream &OS) const; 228 void dump() const; 229 230 /// Define an iterator for alias sets... this is just a forward iterator. 231 class iterator : public std::iterator<std::forward_iterator_tag, 232 PointerRec, ptrdiff_t> { 233 PointerRec *CurNode; 234 235 public: 236 explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {} 237 238 bool operator==(const iterator& x) const { 239 return CurNode == x.CurNode; 240 } 241 bool operator!=(const iterator& x) const { return !operator==(x); } 242 243 value_type &operator*() const { 244 assert(CurNode && "Dereferencing AliasSet.end()!"); 245 return *CurNode; 246 } 247 value_type *operator->() const { return &operator*(); } 248 249 Value *getPointer() const { return CurNode->getValue(); } 250 uint64_t getSize() const { return CurNode->getSize(); } 251 AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); } 252 253 iterator& operator++() { // Preincrement 254 assert(CurNode && "Advancing past AliasSet.end()!"); 255 CurNode = CurNode->getNext(); 256 return *this; 257 } 258 iterator operator++(int) { // Postincrement 259 iterator tmp = *this; ++*this; return tmp; 260 } 261 }; 262 263 private: 264 // Can only be created by AliasSetTracker. 265 AliasSet() 266 : PtrListEnd(&PtrList), RefCount(0), AliasAny(false), Access(NoAccess), 267 Alias(SetMustAlias), Volatile(false) {} 268 269 PointerRec *getSomePointer() const { 270 return PtrList; 271 } 272 273 /// Return the real alias set this represents. If this has been merged with 274 /// another set and is forwarding, return the ultimate destination set. This 275 /// also implements the union-find collapsing as well. 276 AliasSet *getForwardedTarget(AliasSetTracker &AST) { 277 if (!Forward) return this; 278 279 AliasSet *Dest = Forward->getForwardedTarget(AST); 280 if (Dest != Forward) { 281 Dest->addRef(); 282 Forward->dropRef(AST); 283 Forward = Dest; 284 } 285 return Dest; 286 } 287 288 void removeFromTracker(AliasSetTracker &AST); 289 290 void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size, 291 const AAMDNodes &AAInfo, 292 bool KnownMustAlias = false); 293 void addUnknownInst(Instruction *I, AliasAnalysis &AA); 294 295 void removeUnknownInst(AliasSetTracker &AST, Instruction *I) { 296 bool WasEmpty = UnknownInsts.empty(); 297 for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i) 298 if (UnknownInsts[i] == I) { 299 UnknownInsts[i] = UnknownInsts.back(); 300 UnknownInsts.pop_back(); 301 --i; --e; // Revisit the moved entry. 302 } 303 if (!WasEmpty && UnknownInsts.empty()) 304 dropRef(AST); 305 } 306 307 void setVolatile() { Volatile = true; } 308 309 public: 310 /// Return true if the specified pointer "may" (or must) alias one of the 311 /// members in the set. 312 bool aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo, 313 AliasAnalysis &AA) const; 314 bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &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 AliasAnalysis &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(AliasAnalysis &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, uint64_t 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(MemSetInst *MSI); 372 void add(MemTransferInst *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 that the specified pointer lives in. If the New 384 /// argument is non-null, this method sets the value to true if a new alias 385 /// set is created to contain the pointer (because the pointer didn't alias 386 /// anything). 387 AliasSet &getAliasSetForPointer(Value *P, uint64_t Size, 388 const AAMDNodes &AAInfo); 389 390 /// Return the alias set containing the location specified if one exists, 391 /// otherwise return null. 392 AliasSet *getAliasSetForPointerIfExists(const Value *P, uint64_t Size, 393 const AAMDNodes &AAInfo) { 394 return mergeAliasSetsForPointer(P, Size, AAInfo); 395 } 396 397 /// Return true if the specified instruction "may" (or must) alias one of the 398 /// members in any of the sets. 399 bool containsUnknown(const Instruction *I) const; 400 401 /// Return the underlying alias analysis object used by this tracker. 402 AliasAnalysis &getAliasAnalysis() const { return AA; } 403 404 /// This method is used to remove a pointer value from the AliasSetTracker 405 /// entirely. It should be used when an instruction is deleted from the 406 /// program to update the AST. If you don't use this, you would have dangling 407 /// pointers to deleted instructions. 408 void deleteValue(Value *PtrVal); 409 410 /// This method should be used whenever a preexisting value in the program is 411 /// copied or cloned, introducing a new value. Note that it is ok for clients 412 /// that use this method to introduce the same value multiple times: if the 413 /// tracker already knows about a value, it will ignore the request. 414 void copyValue(Value *From, Value *To); 415 416 using iterator = ilist<AliasSet>::iterator; 417 using const_iterator = ilist<AliasSet>::const_iterator; 418 419 const_iterator begin() const { return AliasSets.begin(); } 420 const_iterator end() const { return AliasSets.end(); } 421 422 iterator begin() { return AliasSets.begin(); } 423 iterator end() { return AliasSets.end(); } 424 425 void print(raw_ostream &OS) const; 426 void dump() const; 427 428 private: 429 friend class AliasSet; 430 431 // The total number of pointers contained in all "may" alias sets. 432 unsigned TotalMayAliasSetSize = 0; 433 434 // A non-null value signifies this AST is saturated. A saturated AST lumps 435 // all pointers into a single "May" set. 436 AliasSet *AliasAnyAS = nullptr; 437 438 void removeAliasSet(AliasSet *AS); 439 440 /// Just like operator[] on the map, except that it creates an entry for the 441 /// pointer if it doesn't already exist. 442 AliasSet::PointerRec &getEntryFor(Value *V) { 443 AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)]; 444 if (!Entry) 445 Entry = new AliasSet::PointerRec(V); 446 return *Entry; 447 } 448 449 AliasSet &addPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo, 450 AliasSet::AccessLattice E); 451 AliasSet *mergeAliasSetsForPointer(const Value *Ptr, uint64_t Size, 452 const AAMDNodes &AAInfo); 453 454 /// Merge all alias sets into a single set that is considered to alias any 455 /// pointer. 456 AliasSet &mergeAllAliasSets(); 457 458 AliasSet *findAliasSetForUnknownInst(Instruction *Inst); 459 }; 460 461 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) { 462 AST.print(OS); 463 return OS; 464 } 465 466 } // end namespace llvm 467 468 #endif // LLVM_ANALYSIS_ALIASSETTRACKER_H 469