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