1//===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps ---*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the MemoryDependenceAnalysis analysis pass. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H 15#define LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H 16 17#include "llvm/ADT/DenseMap.h" 18#include "llvm/ADT/Optional.h" 19#include "llvm/ADT/PointerEmbeddedInt.h" 20#include "llvm/ADT/PointerIntPair.h" 21#include "llvm/ADT/PointerSumType.h" 22#include "llvm/ADT/SmallPtrSet.h" 23#include "llvm/Analysis/AliasAnalysis.h" 24#include "llvm/Analysis/MemoryLocation.h" 25#include "llvm/IR/BasicBlock.h" 26#include "llvm/IR/Metadata.h" 27#include "llvm/IR/PassManager.h" 28#include "llvm/IR/PredIteratorCache.h" 29#include "llvm/Pass.h" 30#include "llvm/Support/ErrorHandling.h" 31#include <cassert> 32#include <cstdint> 33#include <utility> 34#include <vector> 35 36namespace llvm { 37 38class AssumptionCache; 39class CallSite; 40class DominatorTree; 41class Function; 42class Instruction; 43class LoadInst; 44class PHITransAddr; 45class TargetLibraryInfo; 46class Value; 47 48/// A memory dependence query can return one of three different answers. 49class MemDepResult { 50 enum DepType { 51 /// Clients of MemDep never see this. 52 /// 53 /// Entries with this marker occur in a LocalDeps map or NonLocalDeps map 54 /// when the instruction they previously referenced was removed from 55 /// MemDep. In either case, the entry may include an instruction pointer. 56 /// If so, the pointer is an instruction in the block where scanning can 57 /// start from, saving some work. 58 /// 59 /// In a default-constructed MemDepResult object, the type will be Invalid 60 /// and the instruction pointer will be null. 61 Invalid = 0, 62 63 /// This is a dependence on the specified instruction which clobbers the 64 /// desired value. The pointer member of the MemDepResult pair holds the 65 /// instruction that clobbers the memory. For example, this occurs when we 66 /// see a may-aliased store to the memory location we care about. 67 /// 68 /// There are several cases that may be interesting here: 69 /// 1. Loads are clobbered by may-alias stores. 70 /// 2. Loads are considered clobbered by partially-aliased loads. The 71 /// client may choose to analyze deeper into these cases. 72 Clobber, 73 74 /// This is a dependence on the specified instruction which defines or 75 /// produces the desired memory location. The pointer member of the 76 /// MemDepResult pair holds the instruction that defines the memory. 77 /// 78 /// Cases of interest: 79 /// 1. This could be a load or store for dependence queries on 80 /// load/store. The value loaded or stored is the produced value. 81 /// Note that the pointer operand may be different than that of the 82 /// queried pointer due to must aliases and phi translation. Note 83 /// that the def may not be the same type as the query, the pointers 84 /// may just be must aliases. 85 /// 2. For loads and stores, this could be an allocation instruction. In 86 /// this case, the load is loading an undef value or a store is the 87 /// first store to (that part of) the allocation. 88 /// 3. Dependence queries on calls return Def only when they are readonly 89 /// calls or memory use intrinsics with identical callees and no 90 /// intervening clobbers. No validation is done that the operands to 91 /// the calls are the same. 92 Def, 93 94 /// This marker indicates that the query has no known dependency in the 95 /// specified block. 96 /// 97 /// More detailed state info is encoded in the upper part of the pair (i.e. 98 /// the Instruction*) 99 Other 100 }; 101 102 /// If DepType is "Other", the upper part of the sum type is an encoding of 103 /// the following more detailed type information. 104 enum OtherType { 105 /// This marker indicates that the query has no dependency in the specified 106 /// block. 107 /// 108 /// To find out more, the client should query other predecessor blocks. 109 NonLocal = 1, 110 /// This marker indicates that the query has no dependency in the specified 111 /// function. 112 NonFuncLocal, 113 /// This marker indicates that the query dependency is unknown. 114 Unknown 115 }; 116 117 using ValueTy = PointerSumType< 118 DepType, PointerSumTypeMember<Invalid, Instruction *>, 119 PointerSumTypeMember<Clobber, Instruction *>, 120 PointerSumTypeMember<Def, Instruction *>, 121 PointerSumTypeMember<Other, PointerEmbeddedInt<OtherType, 3>>>; 122 ValueTy Value; 123 124 explicit MemDepResult(ValueTy V) : Value(V) {} 125 126public: 127 MemDepResult() = default; 128 129 /// get methods: These are static ctor methods for creating various 130 /// MemDepResult kinds. 131 static MemDepResult getDef(Instruction *Inst) { 132 assert(Inst && "Def requires inst"); 133 return MemDepResult(ValueTy::create<Def>(Inst)); 134 } 135 static MemDepResult getClobber(Instruction *Inst) { 136 assert(Inst && "Clobber requires inst"); 137 return MemDepResult(ValueTy::create<Clobber>(Inst)); 138 } 139 static MemDepResult getNonLocal() { 140 return MemDepResult(ValueTy::create<Other>(NonLocal)); 141 } 142 static MemDepResult getNonFuncLocal() { 143 return MemDepResult(ValueTy::create<Other>(NonFuncLocal)); 144 } 145 static MemDepResult getUnknown() { 146 return MemDepResult(ValueTy::create<Other>(Unknown)); 147 } 148 149 /// Tests if this MemDepResult represents a query that is an instruction 150 /// clobber dependency. 151 bool isClobber() const { return Value.is<Clobber>(); } 152 153 /// Tests if this MemDepResult represents a query that is an instruction 154 /// definition dependency. 155 bool isDef() const { return Value.is<Def>(); } 156 157 /// Tests if this MemDepResult represents a query that is transparent to the 158 /// start of the block, but where a non-local hasn't been done. 159 bool isNonLocal() const { 160 return Value.is<Other>() && Value.cast<Other>() == NonLocal; 161 } 162 163 /// Tests if this MemDepResult represents a query that is transparent to the 164 /// start of the function. 165 bool isNonFuncLocal() const { 166 return Value.is<Other>() && Value.cast<Other>() == NonFuncLocal; 167 } 168 169 /// Tests if this MemDepResult represents a query which cannot and/or will 170 /// not be computed. 171 bool isUnknown() const { 172 return Value.is<Other>() && Value.cast<Other>() == Unknown; 173 } 174 175 /// If this is a normal dependency, returns the instruction that is depended 176 /// on. Otherwise, returns null. 177 Instruction *getInst() const { 178 switch (Value.getTag()) { 179 case Invalid: 180 return Value.cast<Invalid>(); 181 case Clobber: 182 return Value.cast<Clobber>(); 183 case Def: 184 return Value.cast<Def>(); 185 case Other: 186 return nullptr; 187 } 188 llvm_unreachable("Unknown discriminant!"); 189 } 190 191 bool operator==(const MemDepResult &M) const { return Value == M.Value; } 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 196private: 197 friend class MemoryDependenceResults; 198 199 /// Tests if this is a MemDepResult in its dirty/invalid. state. 200 bool isDirty() const { return Value.is<Invalid>(); } 201 202 static MemDepResult getDirty(Instruction *Inst) { 203 return MemDepResult(ValueTy::create<Invalid>(Inst)); 204 } 205}; 206 207/// This is an entry in the NonLocalDepInfo cache. 208/// 209/// For each BasicBlock (the BB entry) it keeps a MemDepResult. 210class NonLocalDepEntry { 211 BasicBlock *BB; 212 MemDepResult Result; 213 214public: 215 NonLocalDepEntry(BasicBlock *bb, MemDepResult result) 216 : BB(bb), Result(result) {} 217 218 // This is used for searches. 219 NonLocalDepEntry(BasicBlock *bb) : BB(bb) {} 220 221 // BB is the sort key, it can't be changed. 222 BasicBlock *getBB() const { return BB; } 223 224 void setResult(const MemDepResult &R) { Result = R; } 225 226 const MemDepResult &getResult() const { return Result; } 227 228 bool operator<(const NonLocalDepEntry &RHS) const { return BB < RHS.BB; } 229}; 230 231/// This is a result from a NonLocal dependence query. 232/// 233/// For each BasicBlock (the BB entry) it keeps a MemDepResult and the 234/// (potentially phi translated) address that was live in the block. 235class NonLocalDepResult { 236 NonLocalDepEntry Entry; 237 Value *Address; 238 239public: 240 NonLocalDepResult(BasicBlock *bb, MemDepResult result, Value *address) 241 : Entry(bb, result), Address(address) {} 242 243 // BB is the sort key, it can't be changed. 244 BasicBlock *getBB() const { return Entry.getBB(); } 245 246 void setResult(const MemDepResult &R, Value *Addr) { 247 Entry.setResult(R); 248 Address = Addr; 249 } 250 251 const MemDepResult &getResult() const { return Entry.getResult(); } 252 253 /// Returns the address of this pointer in this block. 254 /// 255 /// This can be different than the address queried for the non-local result 256 /// because of phi translation. This returns null if the address was not 257 /// available in a block (i.e. because phi translation failed) or if this is 258 /// a cached result and that address was deleted. 259 /// 260 /// The address is always null for a non-local 'call' dependence. 261 Value *getAddress() const { return Address; } 262}; 263 264/// Provides a lazy, caching interface for making common memory aliasing 265/// information queries, backed by LLVM's alias analysis passes. 266/// 267/// The dependency information returned is somewhat unusual, but is pragmatic. 268/// If queried about a store or call that might modify memory, the analysis 269/// will return the instruction[s] that may either load from that memory or 270/// store to it. If queried with a load or call that can never modify memory, 271/// the analysis will return calls and stores that might modify the pointer, 272/// but generally does not return loads unless a) they are volatile, or 273/// b) they load from *must-aliased* pointers. Returning a dependence on 274/// must-alias'd pointers instead of all pointers interacts well with the 275/// internal caching mechanism. 276class MemoryDependenceResults { 277 // A map from instructions to their dependency. 278 using LocalDepMapType = DenseMap<Instruction *, MemDepResult>; 279 LocalDepMapType LocalDeps; 280 281public: 282 using NonLocalDepInfo = std::vector<NonLocalDepEntry>; 283 284private: 285 /// A pair<Value*, bool> where the bool is true if the dependence is a read 286 /// only dependence, false if read/write. 287 using ValueIsLoadPair = PointerIntPair<const Value *, 1, bool>; 288 289 /// This pair is used when caching information for a block. 290 /// 291 /// If the pointer is null, the cache value is not a full query that starts 292 /// at the specified block. If non-null, the bool indicates whether or not 293 /// the contents of the block was skipped. 294 using BBSkipFirstBlockPair = PointerIntPair<BasicBlock *, 1, bool>; 295 296 /// This record is the information kept for each (value, is load) pair. 297 struct NonLocalPointerInfo { 298 /// The pair of the block and the skip-first-block flag. 299 BBSkipFirstBlockPair Pair; 300 /// The results of the query for each relevant block. 301 NonLocalDepInfo NonLocalDeps; 302 /// The maximum size of the dereferences of the pointer. 303 /// 304 /// May be UnknownSize if the sizes are unknown. 305 uint64_t Size = MemoryLocation::UnknownSize; 306 /// The AA tags associated with dereferences of the pointer. 307 /// 308 /// The members may be null if there are no tags or conflicting tags. 309 AAMDNodes AATags; 310 311 NonLocalPointerInfo() = default; 312 }; 313 314 /// Cache storing single nonlocal def for the instruction. 315 /// It is set when nonlocal def would be found in function returning only 316 /// local dependencies. 317 DenseMap<Instruction *, NonLocalDepResult> NonLocalDefsCache; 318 319 /// This map stores the cached results of doing a pointer lookup at the 320 /// bottom of a block. 321 /// 322 /// The key of this map is the pointer+isload bit, the value is a list of 323 /// <bb->result> mappings. 324 using CachedNonLocalPointerInfo = 325 DenseMap<ValueIsLoadPair, NonLocalPointerInfo>; 326 CachedNonLocalPointerInfo NonLocalPointerDeps; 327 328 // A map from instructions to their non-local pointer dependencies. 329 using ReverseNonLocalPtrDepTy = 330 DenseMap<Instruction *, SmallPtrSet<ValueIsLoadPair, 4>>; 331 ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps; 332 333 /// This is the instruction we keep for each cached access that we have for 334 /// an instruction. 335 /// 336 /// The pointer is an owning pointer and the bool indicates whether we have 337 /// any dirty bits in the set. 338 using PerInstNLInfo = std::pair<NonLocalDepInfo, bool>; 339 340 // A map from instructions to their non-local dependencies. 341 using NonLocalDepMapType = DenseMap<Instruction *, PerInstNLInfo>; 342 343 NonLocalDepMapType NonLocalDeps; 344 345 // A reverse mapping from dependencies to the dependees. This is 346 // used when removing instructions to keep the cache coherent. 347 using ReverseDepMapType = 348 DenseMap<Instruction *, SmallPtrSet<Instruction *, 4>>; 349 ReverseDepMapType ReverseLocalDeps; 350 351 // A reverse mapping from dependencies to the non-local dependees. 352 ReverseDepMapType ReverseNonLocalDeps; 353 354 /// Current AA implementation, just a cache. 355 AliasAnalysis &AA; 356 AssumptionCache &AC; 357 const TargetLibraryInfo &TLI; 358 DominatorTree &DT; 359 PredIteratorCache PredCache; 360 361public: 362 MemoryDependenceResults(AliasAnalysis &AA, AssumptionCache &AC, 363 const TargetLibraryInfo &TLI, 364 DominatorTree &DT) 365 : AA(AA), AC(AC), TLI(TLI), DT(DT) {} 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(CallSite QueryCS); 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 getSimplePointerDependencyFrom(const MemoryLocation &MemLoc, 449 bool isLoad, 450 BasicBlock::iterator ScanIt, 451 BasicBlock *BB, 452 Instruction *QueryInst, 453 unsigned *Limit = nullptr); 454 455 /// This analysis looks for other loads and stores with invariant.group 456 /// metadata and the same pointer operand. Returns Unknown if it does not 457 /// find anything, and Def if it can be assumed that 2 instructions load or 458 /// store the same value and NonLocal which indicate that non-local Def was 459 /// found, which can be retrieved by calling getNonLocalPointerDependency 460 /// with the same queried instruction. 461 MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB); 462 463 /// Looks at a memory location for a load (specified by MemLocBase, Offs, and 464 /// Size) and compares it against a load. 465 /// 466 /// If the specified load could be safely widened to a larger integer load 467 /// that is 1) still efficient, 2) safe for the target, and 3) would provide 468 /// the specified memory location value, then this function returns the size 469 /// in bytes of the load width to use. If not, this returns zero. 470 static unsigned getLoadLoadClobberFullWidthSize(const Value *MemLocBase, 471 int64_t MemLocOffs, 472 unsigned MemLocSize, 473 const LoadInst *LI); 474 475 /// Release memory in caches. 476 void releaseMemory(); 477 478private: 479 MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall, 480 BasicBlock::iterator ScanIt, 481 BasicBlock *BB); 482 bool getNonLocalPointerDepFromBB(Instruction *QueryInst, 483 const PHITransAddr &Pointer, 484 const MemoryLocation &Loc, bool isLoad, 485 BasicBlock *BB, 486 SmallVectorImpl<NonLocalDepResult> &Result, 487 DenseMap<BasicBlock *, Value *> &Visited, 488 bool SkipFirstBlock = false); 489 MemDepResult GetNonLocalInfoForBlock(Instruction *QueryInst, 490 const MemoryLocation &Loc, bool isLoad, 491 BasicBlock *BB, NonLocalDepInfo *Cache, 492 unsigned NumSortedEntries); 493 494 void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P); 495 496 void verifyRemoved(Instruction *Inst) const; 497}; 498 499/// An analysis that produces \c MemoryDependenceResults for a function. 500/// 501/// This is essentially a no-op because the results are computed entirely 502/// lazily. 503class MemoryDependenceAnalysis 504 : public AnalysisInfoMixin<MemoryDependenceAnalysis> { 505 friend AnalysisInfoMixin<MemoryDependenceAnalysis>; 506 507 static AnalysisKey Key; 508 509public: 510 using Result = MemoryDependenceResults; 511 512 MemoryDependenceResults run(Function &F, FunctionAnalysisManager &AM); 513}; 514 515/// A wrapper analysis pass for the legacy pass manager that exposes a \c 516/// MemoryDepnedenceResults instance. 517class MemoryDependenceWrapperPass : public FunctionPass { 518 Optional<MemoryDependenceResults> MemDep; 519 520public: 521 static char ID; 522 523 MemoryDependenceWrapperPass(); 524 ~MemoryDependenceWrapperPass() override; 525 526 /// Pass Implementation stuff. This doesn't do any analysis eagerly. 527 bool runOnFunction(Function &) override; 528 529 /// Clean up memory in between runs 530 void releaseMemory() override; 531 532 /// Does not modify anything. It uses Value Numbering and Alias Analysis. 533 void getAnalysisUsage(AnalysisUsage &AU) const override; 534 535 MemoryDependenceResults &getMemDep() { return *MemDep; } 536}; 537 538} // end namespace llvm 539 540#endif // LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H 541