1 //===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps ---*- 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 the MemoryDependenceAnalysis analysis pass. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H 14 #define LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H 15 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/PointerEmbeddedInt.h" 18 #include "llvm/ADT/PointerIntPair.h" 19 #include "llvm/ADT/PointerSumType.h" 20 #include "llvm/ADT/SmallPtrSet.h" 21 #include "llvm/Analysis/AliasAnalysis.h" 22 #include "llvm/Analysis/MemoryLocation.h" 23 #include "llvm/IR/PassManager.h" 24 #include "llvm/IR/PredIteratorCache.h" 25 #include "llvm/IR/ValueHandle.h" 26 #include "llvm/Pass.h" 27 #include <optional> 28 29 namespace llvm { 30 31 class AssumptionCache; 32 class DominatorTree; 33 class PHITransAddr; 34 35 /// A memory dependence query can return one of three different answers. 36 class MemDepResult { 37 enum DepType { 38 /// Clients of MemDep never see this. 39 /// 40 /// Entries with this marker occur in a LocalDeps map or NonLocalDeps map 41 /// when the instruction they previously referenced was removed from 42 /// MemDep. In either case, the entry may include an instruction pointer. 43 /// If so, the pointer is an instruction in the block where scanning can 44 /// start from, saving some work. 45 /// 46 /// In a default-constructed MemDepResult object, the type will be Invalid 47 /// and the instruction pointer will be null. 48 Invalid = 0, 49 50 /// This is a dependence on the specified instruction which clobbers the 51 /// desired value. The pointer member of the MemDepResult pair holds the 52 /// instruction that clobbers the memory. For example, this occurs when we 53 /// see a may-aliased store to the memory location we care about. 54 /// 55 /// There are several cases that may be interesting here: 56 /// 1. Loads are clobbered by may-alias stores. 57 /// 2. Loads are considered clobbered by partially-aliased loads. The 58 /// client may choose to analyze deeper into these cases. 59 Clobber, 60 61 /// This is a dependence on the specified instruction which defines or 62 /// produces the desired memory location. The pointer member of the 63 /// MemDepResult pair holds the instruction that defines the memory. 64 /// 65 /// Cases of interest: 66 /// 1. This could be a load or store for dependence queries on 67 /// load/store. The value loaded or stored is the produced value. 68 /// Note that the pointer operand may be different than that of the 69 /// queried pointer due to must aliases and phi translation. Note 70 /// that the def may not be the same type as the query, the pointers 71 /// may just be must aliases. 72 /// 2. For loads and stores, this could be an allocation instruction. In 73 /// this case, the load is loading an undef value or a store is the 74 /// first store to (that part of) the allocation. 75 /// 3. Dependence queries on calls return Def only when they are readonly 76 /// calls or memory use intrinsics with identical callees and no 77 /// intervening clobbers. No validation is done that the operands to 78 /// the calls are the same. 79 /// 4. For loads and stores, this could be a select instruction that 80 /// defines pointer to this memory location. In this case, users can 81 /// find non-clobbered Defs for both select values that are reaching 82 // the desired memory location (there is still a guarantee that there 83 // are no clobbers between analyzed memory location and select). 84 Def, 85 86 /// This marker indicates that the query has no known dependency in the 87 /// specified block. 88 /// 89 /// More detailed state info is encoded in the upper part of the pair (i.e. 90 /// the Instruction*) 91 Other 92 }; 93 94 /// If DepType is "Other", the upper part of the sum type is an encoding of 95 /// the following more detailed type information. 96 enum OtherType { 97 /// This marker indicates that the query has no dependency in the specified 98 /// block. 99 /// 100 /// To find out more, the client should query other predecessor blocks. 101 NonLocal = 1, 102 /// This marker indicates that the query has no dependency in the specified 103 /// function. 104 NonFuncLocal, 105 /// This marker indicates that the query dependency is unknown. 106 Unknown 107 }; 108 109 using ValueTy = PointerSumType< 110 DepType, PointerSumTypeMember<Invalid, Instruction *>, 111 PointerSumTypeMember<Clobber, Instruction *>, 112 PointerSumTypeMember<Def, Instruction *>, 113 PointerSumTypeMember<Other, PointerEmbeddedInt<OtherType, 3>>>; 114 ValueTy Value; 115 116 explicit MemDepResult(ValueTy V) : Value(V) {} 117 118 public: 119 MemDepResult() = default; 120 121 /// get methods: These are static ctor methods for creating various 122 /// MemDepResult kinds. 123 static MemDepResult getDef(Instruction *Inst) { 124 assert(Inst && "Def requires inst"); 125 return MemDepResult(ValueTy::create<Def>(Inst)); 126 } 127 static MemDepResult getClobber(Instruction *Inst) { 128 assert(Inst && "Clobber requires inst"); 129 return MemDepResult(ValueTy::create<Clobber>(Inst)); 130 } 131 static MemDepResult getNonLocal() { 132 return MemDepResult(ValueTy::create<Other>(NonLocal)); 133 } 134 static MemDepResult getNonFuncLocal() { 135 return MemDepResult(ValueTy::create<Other>(NonFuncLocal)); 136 } 137 static MemDepResult getUnknown() { 138 return MemDepResult(ValueTy::create<Other>(Unknown)); 139 } 140 141 /// Tests if this MemDepResult represents a query that is an instruction 142 /// clobber dependency. 143 bool isClobber() const { return Value.is<Clobber>(); } 144 145 /// Tests if this MemDepResult represents a query that is an instruction 146 /// definition dependency. 147 bool isDef() const { return Value.is<Def>(); } 148 149 /// Tests if this MemDepResult represents a valid local query (Clobber/Def). 150 bool isLocal() const { return isClobber() || isDef(); } 151 152 /// Tests if this MemDepResult represents a query that is transparent to the 153 /// start of the block, but where a non-local hasn't been done. 154 bool isNonLocal() const { 155 return Value.is<Other>() && Value.cast<Other>() == NonLocal; 156 } 157 158 /// Tests if this MemDepResult represents a query that is transparent to the 159 /// start of the function. 160 bool isNonFuncLocal() const { 161 return Value.is<Other>() && Value.cast<Other>() == NonFuncLocal; 162 } 163 164 /// Tests if this MemDepResult represents a query which cannot and/or will 165 /// not be computed. 166 bool isUnknown() const { 167 return Value.is<Other>() && Value.cast<Other>() == Unknown; 168 } 169 170 /// If this is a normal dependency, returns the instruction that is depended 171 /// on. Otherwise, returns null. 172 Instruction *getInst() const { 173 switch (Value.getTag()) { 174 case Invalid: 175 return Value.cast<Invalid>(); 176 case Clobber: 177 return Value.cast<Clobber>(); 178 case Def: 179 return Value.cast<Def>(); 180 case Other: 181 return nullptr; 182 } 183 llvm_unreachable("Unknown discriminant!"); 184 } 185 186 bool operator==(const MemDepResult &M) const { return Value == M.Value; } 187 bool operator!=(const MemDepResult &M) const { return Value != M.Value; } 188 bool operator<(const MemDepResult &M) const { return Value < M.Value; } 189 bool operator>(const MemDepResult &M) const { return Value > M.Value; } 190 191 private: 192 friend class MemoryDependenceResults; 193 194 /// Tests if this is a MemDepResult in its dirty/invalid. state. 195 bool isDirty() const { return Value.is<Invalid>(); } 196 197 static MemDepResult getDirty(Instruction *Inst) { 198 return MemDepResult(ValueTy::create<Invalid>(Inst)); 199 } 200 }; 201 202 /// This is an entry in the NonLocalDepInfo cache. 203 /// 204 /// For each BasicBlock (the BB entry) it keeps a MemDepResult. 205 class NonLocalDepEntry { 206 BasicBlock *BB; 207 MemDepResult Result; 208 209 public: 210 NonLocalDepEntry(BasicBlock *BB, MemDepResult Result) 211 : BB(BB), Result(Result) {} 212 213 // This is used for searches. 214 NonLocalDepEntry(BasicBlock *BB) : BB(BB) {} 215 216 // BB is the sort key, it can't be changed. 217 BasicBlock *getBB() const { return BB; } 218 219 void setResult(const MemDepResult &R) { Result = R; } 220 221 const MemDepResult &getResult() const { return Result; } 222 223 bool operator<(const NonLocalDepEntry &RHS) const { return BB < RHS.BB; } 224 }; 225 226 /// This is a result from a NonLocal dependence query. 227 /// 228 /// For each BasicBlock (the BB entry) it keeps a MemDepResult and the 229 /// (potentially phi translated) address that was live in the block. 230 class NonLocalDepResult { 231 NonLocalDepEntry Entry; 232 Value *Address; 233 234 public: 235 NonLocalDepResult(BasicBlock *BB, MemDepResult Result, Value *Address) 236 : Entry(BB, Result), Address(Address) {} 237 238 // BB is the sort key, it can't be changed. 239 BasicBlock *getBB() const { return Entry.getBB(); } 240 241 void setResult(const MemDepResult &R, Value *Addr) { 242 Entry.setResult(R); 243 Address = Addr; 244 } 245 246 const MemDepResult &getResult() const { return Entry.getResult(); } 247 248 /// Returns the address of this pointer in this block. 249 /// 250 /// This can be different than the address queried for the non-local result 251 /// because of phi translation. This returns null if the address was not 252 /// available in a block (i.e. because phi translation failed) or if this is 253 /// a cached result and that address was deleted. 254 /// 255 /// The address is always null for a non-local 'call' dependence. 256 Value *getAddress() const { return Address; } 257 }; 258 259 /// Provides a lazy, caching interface for making common memory aliasing 260 /// information queries, backed by LLVM's alias analysis passes. 261 /// 262 /// The dependency information returned is somewhat unusual, but is pragmatic. 263 /// If queried about a store or call that might modify memory, the analysis 264 /// will return the instruction[s] that may either load from that memory or 265 /// store to it. If queried with a load or call that can never modify memory, 266 /// the analysis will return calls and stores that might modify the pointer, 267 /// but generally does not return loads unless a) they are volatile, or 268 /// b) they load from *must-aliased* pointers. Returning a dependence on 269 /// must-alias'd pointers instead of all pointers interacts well with the 270 /// internal caching mechanism. 271 class MemoryDependenceResults { 272 // A map from instructions to their dependency. 273 using LocalDepMapType = DenseMap<Instruction *, MemDepResult>; 274 LocalDepMapType LocalDeps; 275 276 public: 277 using NonLocalDepInfo = std::vector<NonLocalDepEntry>; 278 279 private: 280 /// A pair<Value*, bool> where the bool is true if the dependence is a read 281 /// only dependence, false if read/write. 282 using ValueIsLoadPair = PointerIntPair<const Value *, 1, bool>; 283 284 /// This pair is used when caching information for a block. 285 /// 286 /// If the pointer is null, the cache value is not a full query that starts 287 /// at the specified block. If non-null, the bool indicates whether or not 288 /// the contents of the block was skipped. 289 using BBSkipFirstBlockPair = PointerIntPair<BasicBlock *, 1, bool>; 290 291 /// This record is the information kept for each (value, is load) pair. 292 struct NonLocalPointerInfo { 293 /// The pair of the block and the skip-first-block flag. 294 BBSkipFirstBlockPair Pair; 295 /// The results of the query for each relevant block. 296 NonLocalDepInfo NonLocalDeps; 297 /// The maximum size of the dereferences of the pointer. 298 /// 299 /// May be UnknownSize if the sizes are unknown. 300 LocationSize Size = LocationSize::afterPointer(); 301 /// The AA tags associated with dereferences of the pointer. 302 /// 303 /// The members may be null if there are no tags or conflicting tags. 304 AAMDNodes AATags; 305 306 NonLocalPointerInfo() = default; 307 }; 308 309 /// Cache storing single nonlocal def for the instruction. 310 /// It is set when nonlocal def would be found in function returning only 311 /// local dependencies. 312 DenseMap<AssertingVH<const Value>, NonLocalDepResult> NonLocalDefsCache; 313 using ReverseNonLocalDefsCacheTy = 314 DenseMap<Instruction *, SmallPtrSet<const Value*, 4>>; 315 ReverseNonLocalDefsCacheTy ReverseNonLocalDefsCache; 316 317 /// This map stores the cached results of doing a pointer lookup at the 318 /// bottom of a block. 319 /// 320 /// The key of this map is the pointer+isload bit, the value is a list of 321 /// <bb->result> mappings. 322 using CachedNonLocalPointerInfo = 323 DenseMap<ValueIsLoadPair, NonLocalPointerInfo>; 324 CachedNonLocalPointerInfo NonLocalPointerDeps; 325 326 // A map from instructions to their non-local pointer dependencies. 327 using ReverseNonLocalPtrDepTy = 328 DenseMap<Instruction *, SmallPtrSet<ValueIsLoadPair, 4>>; 329 ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps; 330 331 /// This is the instruction we keep for each cached access that we have for 332 /// an instruction. 333 /// 334 /// The pointer is an owning pointer and the bool indicates whether we have 335 /// any dirty bits in the set. 336 using PerInstNLInfo = std::pair<NonLocalDepInfo, bool>; 337 338 // A map from instructions to their non-local dependencies. 339 using NonLocalDepMapType = DenseMap<Instruction *, PerInstNLInfo>; 340 341 NonLocalDepMapType NonLocalDepsMap; 342 343 // A reverse mapping from dependencies to the dependees. This is 344 // used when removing instructions to keep the cache coherent. 345 using ReverseDepMapType = 346 DenseMap<Instruction *, SmallPtrSet<Instruction *, 4>>; 347 ReverseDepMapType ReverseLocalDeps; 348 349 // A reverse mapping from dependencies to the non-local dependees. 350 ReverseDepMapType ReverseNonLocalDeps; 351 352 /// Current AA implementation, just a cache. 353 AAResults &AA; 354 AssumptionCache &AC; 355 const TargetLibraryInfo &TLI; 356 DominatorTree &DT; 357 PredIteratorCache PredCache; 358 EarliestEscapeAnalysis EEA; 359 360 unsigned DefaultBlockScanLimit; 361 362 /// Offsets to dependant clobber loads. 363 using ClobberOffsetsMapType = DenseMap<LoadInst *, int32_t>; 364 ClobberOffsetsMapType ClobberOffsets; 365 366 public: 367 MemoryDependenceResults(AAResults &AA, AssumptionCache &AC, 368 const TargetLibraryInfo &TLI, DominatorTree &DT, 369 unsigned DefaultBlockScanLimit) 370 : AA(AA), AC(AC), TLI(TLI), DT(DT), EEA(DT), 371 DefaultBlockScanLimit(DefaultBlockScanLimit) {} 372 373 /// Handle invalidation in the new PM. 374 bool invalidate(Function &F, const PreservedAnalyses &PA, 375 FunctionAnalysisManager::Invalidator &Inv); 376 377 /// Some methods limit the number of instructions they will examine. 378 /// The return value of this method is the default limit that will be 379 /// used if no limit is explicitly passed in. 380 unsigned getDefaultBlockScanLimit() const; 381 382 /// Returns the instruction on which a memory operation depends. 383 /// 384 /// See the class comment for more details. It is illegal to call this on 385 /// non-memory instructions. 386 MemDepResult getDependency(Instruction *QueryInst); 387 388 /// Perform a full dependency query for the specified call, returning the set 389 /// of blocks that the value is potentially live across. 390 /// 391 /// The returned set of results will include a "NonLocal" result for all 392 /// blocks where the value is live across. 393 /// 394 /// This method assumes the instruction returns a "NonLocal" dependency 395 /// within its own block. 396 /// 397 /// This returns a reference to an internal data structure that may be 398 /// invalidated on the next non-local query or when an instruction is 399 /// removed. Clients must copy this data if they want it around longer than 400 /// that. 401 const NonLocalDepInfo &getNonLocalCallDependency(CallBase *QueryCall); 402 403 /// Perform a full dependency query for an access to the QueryInst's 404 /// specified memory location, returning the set of instructions that either 405 /// define or clobber the value. 406 /// 407 /// Warning: For a volatile query instruction, the dependencies will be 408 /// accurate, and thus usable for reordering, but it is never legal to 409 /// remove the query instruction. 410 /// 411 /// This method assumes the pointer has a "NonLocal" dependency within 412 /// QueryInst's parent basic block. 413 void getNonLocalPointerDependency(Instruction *QueryInst, 414 SmallVectorImpl<NonLocalDepResult> &Result); 415 416 /// Removes an instruction from the dependence analysis, updating the 417 /// dependence of instructions that previously depended on it. 418 void removeInstruction(Instruction *InstToRemove); 419 420 /// Invalidates cached information about the specified pointer, because it 421 /// may be too conservative in memdep. 422 /// 423 /// This is an optional call that can be used when the client detects an 424 /// equivalence between the pointer and some other value and replaces the 425 /// other value with ptr. This can make Ptr available in more places that 426 /// cached info does not necessarily keep. 427 void invalidateCachedPointerInfo(Value *Ptr); 428 429 /// Clears the PredIteratorCache info. 430 /// 431 /// This needs to be done when the CFG changes, e.g., due to splitting 432 /// critical edges. 433 void invalidateCachedPredecessors(); 434 435 /// Returns the instruction on which a memory location depends. 436 /// 437 /// If isLoad is true, this routine ignores may-aliases with read-only 438 /// operations. If isLoad is false, this routine ignores may-aliases 439 /// with reads from read-only locations. If possible, pass the query 440 /// instruction as well; this function may take advantage of the metadata 441 /// annotated to the query instruction to refine the result. \p Limit 442 /// can be used to set the maximum number of instructions that will be 443 /// examined to find the pointer dependency. On return, it will be set to 444 /// the number of instructions left to examine. If a null pointer is passed 445 /// in, the limit will default to the value of -memdep-block-scan-limit. 446 /// 447 /// Note that this is an uncached query, and thus may be inefficient. 448 MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad, 449 BasicBlock::iterator ScanIt, 450 BasicBlock *BB, 451 Instruction *QueryInst = nullptr, 452 unsigned *Limit = nullptr); 453 454 MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad, 455 BasicBlock::iterator ScanIt, 456 BasicBlock *BB, 457 Instruction *QueryInst, 458 unsigned *Limit, 459 BatchAAResults &BatchAA); 460 461 MemDepResult 462 getSimplePointerDependencyFrom(const MemoryLocation &MemLoc, bool isLoad, 463 BasicBlock::iterator ScanIt, BasicBlock *BB, 464 Instruction *QueryInst, unsigned *Limit, 465 BatchAAResults &BatchAA); 466 467 /// This analysis looks for other loads and stores with invariant.group 468 /// metadata and the same pointer operand. Returns Unknown if it does not 469 /// find anything, and Def if it can be assumed that 2 instructions load or 470 /// store the same value and NonLocal which indicate that non-local Def was 471 /// found, which can be retrieved by calling getNonLocalPointerDependency 472 /// with the same queried instruction. 473 MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB); 474 475 /// Release memory in caches. 476 void releaseMemory(); 477 478 /// Return the clobber offset to dependent instruction. 479 std::optional<int32_t> getClobberOffset(LoadInst *DepInst) const { 480 const auto Off = ClobberOffsets.find(DepInst); 481 if (Off != ClobberOffsets.end()) 482 return Off->getSecond(); 483 return std::nullopt; 484 } 485 486 private: 487 MemDepResult getCallDependencyFrom(CallBase *Call, bool isReadOnlyCall, 488 BasicBlock::iterator ScanIt, 489 BasicBlock *BB); 490 bool getNonLocalPointerDepFromBB(Instruction *QueryInst, 491 const PHITransAddr &Pointer, 492 const MemoryLocation &Loc, bool isLoad, 493 BasicBlock *BB, 494 SmallVectorImpl<NonLocalDepResult> &Result, 495 SmallDenseMap<BasicBlock *, Value *, 16> &Visited, 496 bool SkipFirstBlock = false, 497 bool IsIncomplete = false); 498 MemDepResult getNonLocalInfoForBlock(Instruction *QueryInst, 499 const MemoryLocation &Loc, bool isLoad, 500 BasicBlock *BB, NonLocalDepInfo *Cache, 501 unsigned NumSortedEntries, 502 BatchAAResults &BatchAA); 503 504 void removeCachedNonLocalPointerDependencies(ValueIsLoadPair P); 505 506 void verifyRemoved(Instruction *Inst) const; 507 }; 508 509 /// An analysis that produces \c MemoryDependenceResults for a function. 510 /// 511 /// This is essentially a no-op because the results are computed entirely 512 /// lazily. 513 class MemoryDependenceAnalysis 514 : public AnalysisInfoMixin<MemoryDependenceAnalysis> { 515 friend AnalysisInfoMixin<MemoryDependenceAnalysis>; 516 517 static AnalysisKey Key; 518 519 unsigned DefaultBlockScanLimit; 520 521 public: 522 using Result = MemoryDependenceResults; 523 524 MemoryDependenceAnalysis(); 525 MemoryDependenceAnalysis(unsigned DefaultBlockScanLimit) : DefaultBlockScanLimit(DefaultBlockScanLimit) { } 526 527 MemoryDependenceResults run(Function &F, FunctionAnalysisManager &AM); 528 }; 529 530 /// A wrapper analysis pass for the legacy pass manager that exposes a \c 531 /// MemoryDepnedenceResults instance. 532 class MemoryDependenceWrapperPass : public FunctionPass { 533 std::optional<MemoryDependenceResults> MemDep; 534 535 public: 536 static char ID; 537 538 MemoryDependenceWrapperPass(); 539 ~MemoryDependenceWrapperPass() override; 540 541 /// Pass Implementation stuff. This doesn't do any analysis eagerly. 542 bool runOnFunction(Function &) override; 543 544 /// Clean up memory in between runs 545 void releaseMemory() override; 546 547 /// Does not modify anything. It uses Value Numbering and Alias Analysis. 548 void getAnalysisUsage(AnalysisUsage &AU) const override; 549 550 MemoryDependenceResults &getMemDep() { return *MemDep; } 551 }; 552 553 } // end namespace llvm 554 555 #endif // LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H 556