MemoryDependenceAnalysis.h revision 360784
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/AliasAnalysis.h" 23#include "llvm/Analysis/MemoryLocation.h" 24#include "llvm/IR/BasicBlock.h" 25#include "llvm/IR/Metadata.h" 26#include "llvm/IR/PassManager.h" 27#include "llvm/IR/PredIteratorCache.h" 28#include "llvm/IR/ValueHandle.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 DominatorTree; 40class Function; 41class Instruction; 42class LoadInst; 43class PHITransAddr; 44class TargetLibraryInfo; 45class PhiValues; 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 LocationSize Size = LocationSize::unknown(); 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<AssertingVH<const Value>, NonLocalDepResult> NonLocalDefsCache; 318 using ReverseNonLocalDefsCacheTy = 319 DenseMap<Instruction *, SmallPtrSet<const Value*, 4>>; 320 ReverseNonLocalDefsCacheTy ReverseNonLocalDefsCache; 321 322 /// This map stores the cached results of doing a pointer lookup at the 323 /// bottom of a block. 324 /// 325 /// The key of this map is the pointer+isload bit, the value is a list of 326 /// <bb->result> mappings. 327 using CachedNonLocalPointerInfo = 328 DenseMap<ValueIsLoadPair, NonLocalPointerInfo>; 329 CachedNonLocalPointerInfo NonLocalPointerDeps; 330 331 // A map from instructions to their non-local pointer dependencies. 332 using ReverseNonLocalPtrDepTy = 333 DenseMap<Instruction *, SmallPtrSet<ValueIsLoadPair, 4>>; 334 ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps; 335 336 /// This is the instruction we keep for each cached access that we have for 337 /// an instruction. 338 /// 339 /// The pointer is an owning pointer and the bool indicates whether we have 340 /// any dirty bits in the set. 341 using PerInstNLInfo = std::pair<NonLocalDepInfo, bool>; 342 343 // A map from instructions to their non-local dependencies. 344 using NonLocalDepMapType = DenseMap<Instruction *, PerInstNLInfo>; 345 346 NonLocalDepMapType NonLocalDeps; 347 348 // A reverse mapping from dependencies to the dependees. This is 349 // used when removing instructions to keep the cache coherent. 350 using ReverseDepMapType = 351 DenseMap<Instruction *, SmallPtrSet<Instruction *, 4>>; 352 ReverseDepMapType ReverseLocalDeps; 353 354 // A reverse mapping from dependencies to the non-local dependees. 355 ReverseDepMapType ReverseNonLocalDeps; 356 357 /// Current AA implementation, just a cache. 358 AliasAnalysis &AA; 359 AssumptionCache &AC; 360 const TargetLibraryInfo &TLI; 361 DominatorTree &DT; 362 PhiValues &PV; 363 PredIteratorCache PredCache; 364 365 unsigned DefaultBlockScanLimit; 366 367public: 368 MemoryDependenceResults(AliasAnalysis &AA, AssumptionCache &AC, 369 const TargetLibraryInfo &TLI, DominatorTree &DT, 370 PhiValues &PV, unsigned DefaultBlockScanLimit) 371 : AA(AA), AC(AC), TLI(TLI), DT(DT), PV(PV), 372 DefaultBlockScanLimit(DefaultBlockScanLimit) {} 373 374 /// Handle invalidation in the new PM. 375 bool invalidate(Function &F, const PreservedAnalyses &PA, 376 FunctionAnalysisManager::Invalidator &Inv); 377 378 /// Some methods limit the number of instructions they will examine. 379 /// The return value of this method is the default limit that will be 380 /// used if no limit is explicitly passed in. 381 unsigned getDefaultBlockScanLimit() const; 382 383 /// Returns the instruction on which a memory operation depends. 384 /// 385 /// See the class comment for more details. It is illegal to call this on 386 /// non-memory instructions. 387 MemDepResult getDependency(Instruction *QueryInst, 388 OrderedBasicBlock *OBB = nullptr); 389 390 /// Perform a full dependency query for the specified call, returning the set 391 /// of blocks that the value is potentially live across. 392 /// 393 /// The returned set of results will include a "NonLocal" result for all 394 /// blocks where the value is live across. 395 /// 396 /// This method assumes the instruction returns a "NonLocal" dependency 397 /// within its own block. 398 /// 399 /// This returns a reference to an internal data structure that may be 400 /// invalidated on the next non-local query or when an instruction is 401 /// removed. Clients must copy this data if they want it around longer than 402 /// that. 403 const NonLocalDepInfo &getNonLocalCallDependency(CallBase *QueryCall); 404 405 /// Perform a full dependency query for an access to the QueryInst's 406 /// specified memory location, returning the set of instructions that either 407 /// define or clobber the value. 408 /// 409 /// Warning: For a volatile query instruction, the dependencies will be 410 /// accurate, and thus usable for reordering, but it is never legal to 411 /// remove the query instruction. 412 /// 413 /// This method assumes the pointer has a "NonLocal" dependency within 414 /// QueryInst's parent basic block. 415 void getNonLocalPointerDependency(Instruction *QueryInst, 416 SmallVectorImpl<NonLocalDepResult> &Result); 417 418 /// Removes an instruction from the dependence analysis, updating the 419 /// dependence of instructions that previously depended on it. 420 void removeInstruction(Instruction *InstToRemove); 421 422 /// Invalidates cached information about the specified pointer, because it 423 /// may be too conservative in memdep. 424 /// 425 /// This is an optional call that can be used when the client detects an 426 /// equivalence between the pointer and some other value and replaces the 427 /// other value with ptr. This can make Ptr available in more places that 428 /// cached info does not necessarily keep. 429 void invalidateCachedPointerInfo(Value *Ptr); 430 431 /// Clears the PredIteratorCache info. 432 /// 433 /// This needs to be done when the CFG changes, e.g., due to splitting 434 /// critical edges. 435 void invalidateCachedPredecessors(); 436 437 /// Returns the instruction on which a memory location depends. 438 /// 439 /// If isLoad is true, this routine ignores may-aliases with read-only 440 /// operations. If isLoad is false, this routine ignores may-aliases 441 /// with reads from read-only locations. If possible, pass the query 442 /// instruction as well; this function may take advantage of the metadata 443 /// annotated to the query instruction to refine the result. \p Limit 444 /// can be used to set the maximum number of instructions that will be 445 /// examined to find the pointer dependency. On return, it will be set to 446 /// the number of instructions left to examine. If a null pointer is passed 447 /// in, the limit will default to the value of -memdep-block-scan-limit. 448 /// 449 /// Note that this is an uncached query, and thus may be inefficient. 450 MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad, 451 BasicBlock::iterator ScanIt, 452 BasicBlock *BB, 453 Instruction *QueryInst = nullptr, 454 unsigned *Limit = nullptr, 455 OrderedBasicBlock *OBB = nullptr); 456 457 MemDepResult 458 getSimplePointerDependencyFrom(const MemoryLocation &MemLoc, bool isLoad, 459 BasicBlock::iterator ScanIt, BasicBlock *BB, 460 Instruction *QueryInst, unsigned *Limit, 461 OrderedBasicBlock *OBB); 462 463 /// This analysis looks for other loads and stores with invariant.group 464 /// metadata and the same pointer operand. Returns Unknown if it does not 465 /// find anything, and Def if it can be assumed that 2 instructions load or 466 /// store the same value and NonLocal which indicate that non-local Def was 467 /// found, which can be retrieved by calling getNonLocalPointerDependency 468 /// with the same queried instruction. 469 MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB); 470 471 /// Looks at a memory location for a load (specified by MemLocBase, Offs, and 472 /// Size) and compares it against a load. 473 /// 474 /// If the specified load could be safely widened to a larger integer load 475 /// that is 1) still efficient, 2) safe for the target, and 3) would provide 476 /// the specified memory location value, then this function returns the size 477 /// in bytes of the load width to use. If not, this returns zero. 478 static unsigned getLoadLoadClobberFullWidthSize(const Value *MemLocBase, 479 int64_t MemLocOffs, 480 unsigned MemLocSize, 481 const LoadInst *LI); 482 483 /// Release memory in caches. 484 void releaseMemory(); 485 486private: 487 MemDepResult getCallDependencyFrom(CallBase *Call, bool isReadOnlyCall, 488 BasicBlock::iterator ScanIt, 489 BasicBlock *BB); 490 bool getNonLocalPointerDepFromBB(Instruction *QueryInst, 491 const PHITransAddr &Pointer, 492 const MemoryLocation &Loc, bool isLoad, 493 BasicBlock *BB, 494 SmallVectorImpl<NonLocalDepResult> &Result, 495 DenseMap<BasicBlock *, Value *> &Visited, 496 bool SkipFirstBlock = false); 497 MemDepResult GetNonLocalInfoForBlock(Instruction *QueryInst, 498 const MemoryLocation &Loc, bool isLoad, 499 BasicBlock *BB, NonLocalDepInfo *Cache, 500 unsigned NumSortedEntries); 501 502 void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P); 503 504 void verifyRemoved(Instruction *Inst) const; 505}; 506 507/// An analysis that produces \c MemoryDependenceResults for a function. 508/// 509/// This is essentially a no-op because the results are computed entirely 510/// lazily. 511class MemoryDependenceAnalysis 512 : public AnalysisInfoMixin<MemoryDependenceAnalysis> { 513 friend AnalysisInfoMixin<MemoryDependenceAnalysis>; 514 515 static AnalysisKey Key; 516 517 unsigned DefaultBlockScanLimit; 518 519public: 520 using Result = MemoryDependenceResults; 521 522 MemoryDependenceAnalysis(); 523 MemoryDependenceAnalysis(unsigned DefaultBlockScanLimit) : DefaultBlockScanLimit(DefaultBlockScanLimit) { } 524 525 MemoryDependenceResults run(Function &F, FunctionAnalysisManager &AM); 526}; 527 528/// A wrapper analysis pass for the legacy pass manager that exposes a \c 529/// MemoryDepnedenceResults instance. 530class MemoryDependenceWrapperPass : public FunctionPass { 531 Optional<MemoryDependenceResults> MemDep; 532 533public: 534 static char ID; 535 536 MemoryDependenceWrapperPass(); 537 ~MemoryDependenceWrapperPass() override; 538 539 /// Pass Implementation stuff. This doesn't do any analysis eagerly. 540 bool runOnFunction(Function &) override; 541 542 /// Clean up memory in between runs 543 void releaseMemory() override; 544 545 /// Does not modify anything. It uses Value Numbering and Alias Analysis. 546 void getAnalysisUsage(AnalysisUsage &AU) const override; 547 548 MemoryDependenceResults &getMemDep() { return *MemDep; } 549}; 550 551} // end namespace llvm 552 553#endif // LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H 554