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/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 35namespace llvm { 36 37class AAResults; 38class AliasResult; 39class AliasSetTracker; 40class AnyMemSetInst; 41class AnyMemTransferInst; 42class BasicBlock; 43class LoadInst; 44class raw_ostream; 45class StoreInst; 46class VAArgInst; 47class Value; 48 49class 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. 62 bool isSizeSet() const { return Size != LocationSize::mapEmpty(); } 63 64 public: 65 PointerRec(Value *V) 66 : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {} 67 68 Value *getValue() const { return Val; } 69 70 PointerRec *getNext() const { return NextInList; } 71 bool hasAliasSet() const { return AS != nullptr; } 72 73 PointerRec** setPrevInList(PointerRec **PIL) { 74 PrevInList = PIL; 75 return &NextInList; 76 } 77 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 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. 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 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 123 void setAliasSet(AliasSet *as) { 124 assert(!AS && "Already have an alias set!"); 125 AS = as; 126 } 127 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 186 void addRef() { ++RefCount; } 187 188 void dropRef(AliasSetTracker &AST) { 189 assert(RefCount >= 1 && "Invalid reference count detected!"); 190 if (--RefCount == 0) 191 removeFromTracker(AST); 192 } 193 194 Instruction *getUnknownInst(unsigned i) const { 195 assert(i < UnknownInsts.size()); 196 return cast_or_null<Instruction>(UnknownInsts[i]); 197 } 198 199public: 200 AliasSet(const AliasSet &) = delete; 201 AliasSet &operator=(const AliasSet &) = delete; 202 203 /// Accessors... 204 bool isRef() const { return Access & RefAccess; } 205 bool isMod() const { return Access & ModAccess; } 206 bool isMustAlias() const { return Alias == SetMustAlias; } 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. 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 /// 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 { 236 PointerRec *CurNode; 237 238 public: 239 using iterator_category = std::forward_iterator_tag; 240 using value_type = PointerRec; 241 using difference_type = std::ptrdiff_t; 242 using pointer = value_type *; 243 using reference = value_type &; 244 245 explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {} 246 247 bool operator==(const iterator& x) const { 248 return CurNode == x.CurNode; 249 } 250 bool operator!=(const iterator& x) const { return !operator==(x); } 251 252 value_type &operator*() const { 253 assert(CurNode && "Dereferencing AliasSet.end()!"); 254 return *CurNode; 255 } 256 value_type *operator->() const { return &operator*(); } 257 258 Value *getPointer() const { return CurNode->getValue(); } 259 LocationSize getSize() const { return CurNode->getSize(); } 260 AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); } 261 262 iterator& operator++() { // Preincrement 263 assert(CurNode && "Advancing past AliasSet.end()!"); 264 CurNode = CurNode->getNext(); 265 return *this; 266 } 267 iterator operator++(int) { // Postincrement 268 iterator tmp = *this; ++*this; return tmp; 269 } 270 }; 271 272private: 273 // Can only be created by AliasSetTracker. 274 AliasSet() 275 : PtrListEnd(&PtrList), RefCount(0), AliasAny(false), Access(NoAccess), 276 Alias(SetMustAlias) {} 277 278 PointerRec *getSomePointer() const { 279 return PtrList; 280 } 281 282 /// Return the real alias set this represents. If this has been merged with 283 /// another set and is forwarding, return the ultimate destination set. This 284 /// also implements the union-find collapsing as well. 285 AliasSet *getForwardedTarget(AliasSetTracker &AST) { 286 if (!Forward) return this; 287 288 AliasSet *Dest = Forward->getForwardedTarget(AST); 289 if (Dest != Forward) { 290 Dest->addRef(); 291 Forward->dropRef(AST); 292 Forward = Dest; 293 } 294 return Dest; 295 } 296 297 void removeFromTracker(AliasSetTracker &AST); 298 299 void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size, 300 const AAMDNodes &AAInfo, bool KnownMustAlias = false, 301 bool SkipSizeUpdate = false); 302 void addUnknownInst(Instruction *I, AAResults &AA); 303 304 void removeUnknownInst(AliasSetTracker &AST, Instruction *I) { 305 bool WasEmpty = UnknownInsts.empty(); 306 for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i) 307 if (UnknownInsts[i] == I) { 308 UnknownInsts[i] = UnknownInsts.back(); 309 UnknownInsts.pop_back(); 310 --i; --e; // Revisit the moved entry. 311 } 312 if (!WasEmpty && UnknownInsts.empty()) 313 dropRef(AST); 314 } 315 316public: 317 /// If the specified pointer "may" (or must) alias one of the members in the 318 /// set return the appropriate AliasResult. Otherwise return NoAlias. 319 AliasResult aliasesPointer(const Value *Ptr, LocationSize Size, 320 const AAMDNodes &AAInfo, AAResults &AA) const; 321 bool aliasesUnknownInst(const Instruction *Inst, AAResults &AA) const; 322}; 323 324inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) { 325 AS.print(OS); 326 return OS; 327} 328 329class AliasSetTracker { 330 /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a 331 /// Value is deleted. 332 class ASTCallbackVH final : public CallbackVH { 333 AliasSetTracker *AST; 334 335 void deleted() override; 336 void allUsesReplacedWith(Value *) override; 337 338 public: 339 ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr); 340 341 ASTCallbackVH &operator=(Value *V); 342 }; 343 /// Traits to tell DenseMap that tell us how to compare and hash the value 344 /// handle. 345 struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {}; 346 347 AAResults &AA; 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 356public: 357 /// Create an empty collection of AliasSets, and use the specified alias 358 /// analysis object to disambiguate load and store addresses. 359 explicit AliasSetTracker(AAResults &AA) : AA(AA) {} 360 ~AliasSetTracker() { clear(); } 361 362 /// These methods are used to add different types of instructions to the alias 363 /// sets. Adding a new instruction can result in one of three actions 364 /// happening: 365 /// 366 /// 1. If the instruction doesn't alias any other sets, create a new set. 367 /// 2. If the instruction aliases exactly one set, add it to the set 368 /// 3. If the instruction aliases multiple sets, merge the sets, and add 369 /// the instruction to the result. 370 /// 371 /// These methods return true if inserting the instruction resulted in the 372 /// addition of a new alias set (i.e., the pointer did not alias anything). 373 /// 374 void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc 375 void add(LoadInst *LI); 376 void add(StoreInst *SI); 377 void add(VAArgInst *VAAI); 378 void add(AnyMemSetInst *MSI); 379 void add(AnyMemTransferInst *MTI); 380 void add(Instruction *I); // Dispatch to one of the other add methods... 381 void add(BasicBlock &BB); // Add all instructions in basic block 382 void add(const AliasSetTracker &AST); // Add alias relations from another AST 383 void addUnknown(Instruction *I); 384 385 void clear(); 386 387 /// Return the alias sets that are active. 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. 397 AAResults &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 414 const_iterator begin() const { return AliasSets.begin(); } 415 const_iterator end() const { return AliasSets.end(); } 416 417 iterator begin() { return AliasSets.begin(); } 418 iterator end() { return AliasSets.end(); } 419 420 void print(raw_ostream &OS) const; 421 void dump() const; 422 423private: 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. 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 456inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) { 457 AST.print(OS); 458 return OS; 459} 460 461class AliasSetsPrinterPass : public PassInfoMixin<AliasSetsPrinterPass> { 462 raw_ostream &OS; 463 464public: 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