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