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