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