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