1 //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements an analysis that determines, for a given memory
11 // operation, what preceding memory operations it depends on. It builds on
12 // alias analysis information, and tries to provide a lazy, caching interface to
13 // a common kind of alias information query.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/Analysis/AssumptionCache.h"
24 #include "llvm/Analysis/MemoryBuiltins.h"
25 #include "llvm/Analysis/PHITransAddr.h"
26 #include "llvm/Analysis/OrderedBasicBlock.h"
27 #include "llvm/Analysis/ValueTracking.h"
28 #include "llvm/Analysis/TargetLibraryInfo.h"
29 #include "llvm/IR/CallSite.h"
30 #include "llvm/IR/Constants.h"
31 #include "llvm/IR/DataLayout.h"
32 #include "llvm/IR/DerivedTypes.h"
33 #include "llvm/IR/Dominators.h"
34 #include "llvm/IR/Function.h"
35 #include "llvm/IR/Instruction.h"
36 #include "llvm/IR/Instructions.h"
37 #include "llvm/IR/IntrinsicInst.h"
38 #include "llvm/IR/LLVMContext.h"
39 #include "llvm/IR/PredIteratorCache.h"
40 #include "llvm/Support/AtomicOrdering.h"
41 #include "llvm/Support/Casting.h"
42 #include "llvm/Support/CommandLine.h"
43 #include "llvm/Support/Compiler.h"
44 #include "llvm/Support/Debug.h"
45 #include "llvm/Support/MathExtras.h"
52 #define DEBUG_TYPE "memdep"
54 STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");
55 STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");
56 STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");
58 STATISTIC(NumCacheNonLocalPtr,
59 "Number of fully cached non-local ptr responses");
60 STATISTIC(NumCacheDirtyNonLocalPtr,
61 "Number of cached, but dirty, non-local ptr responses");
62 STATISTIC(NumUncacheNonLocalPtr, "Number of uncached non-local ptr responses");
63 STATISTIC(NumCacheCompleteNonLocalPtr,
64 "Number of block queries that were completely cached");
66 // Limit for the number of instructions to scan in a block.
68 static cl::opt<unsigned> BlockScanLimit(
69 "memdep-block-scan-limit", cl::Hidden, cl::init(100),
70 cl::desc("The number of instructions to scan in a block in memory "
71 "dependency analysis (default = 100)"));
73 static cl::opt<unsigned>
74 BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(1000),
75 cl::desc("The number of blocks to scan during memory "
76 "dependency analysis (default = 1000)"));
78 // Limit on the number of memdep results to process.
79 static const unsigned int NumResultsLimit = 100;
81 /// This is a helper function that removes Val from 'Inst's set in ReverseMap.
83 /// If the set becomes empty, remove Inst's entry.
84 template <typename KeyTy>
86 RemoveFromReverseMap(DenseMap<Instruction *, SmallPtrSet<KeyTy, 4>> &ReverseMap,
87 Instruction *Inst, KeyTy Val) {
88 typename DenseMap<Instruction *, SmallPtrSet<KeyTy, 4>>::iterator InstIt =
89 ReverseMap.find(Inst);
90 assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
91 bool Found = InstIt->second.erase(Val);
92 assert(Found && "Invalid reverse map!");
94 if (InstIt->second.empty())
95 ReverseMap.erase(InstIt);
98 /// If the given instruction references a specific memory location, fill in Loc
99 /// with the details, otherwise set Loc.Ptr to null.
101 /// Returns a ModRefInfo value describing the general behavior of the
103 static ModRefInfo GetLocation(const Instruction *Inst, MemoryLocation &Loc,
104 const TargetLibraryInfo &TLI) {
105 if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
106 if (LI->isUnordered()) {
107 Loc = MemoryLocation::get(LI);
110 if (LI->getOrdering() == AtomicOrdering::Monotonic) {
111 Loc = MemoryLocation::get(LI);
114 Loc = MemoryLocation();
118 if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
119 if (SI->isUnordered()) {
120 Loc = MemoryLocation::get(SI);
123 if (SI->getOrdering() == AtomicOrdering::Monotonic) {
124 Loc = MemoryLocation::get(SI);
127 Loc = MemoryLocation();
131 if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
132 Loc = MemoryLocation::get(V);
136 if (const CallInst *CI = isFreeCall(Inst, &TLI)) {
137 // calls to free() deallocate the entire structure
138 Loc = MemoryLocation(CI->getArgOperand(0));
142 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
145 switch (II->getIntrinsicID()) {
146 case Intrinsic::lifetime_start:
147 case Intrinsic::lifetime_end:
148 case Intrinsic::invariant_start:
149 II->getAAMetadata(AAInfo);
150 Loc = MemoryLocation(
151 II->getArgOperand(1),
152 cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(), AAInfo);
153 // These intrinsics don't really modify the memory, but returning Mod
154 // will allow them to be handled conservatively.
156 case Intrinsic::invariant_end:
157 II->getAAMetadata(AAInfo);
158 Loc = MemoryLocation(
159 II->getArgOperand(2),
160 cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(), AAInfo);
161 // These intrinsics don't really modify the memory, but returning Mod
162 // will allow them to be handled conservatively.
169 // Otherwise, just do the coarse-grained thing that always works.
170 if (Inst->mayWriteToMemory())
172 if (Inst->mayReadFromMemory())
177 /// Private helper for finding the local dependencies of a call site.
178 MemDepResult MemoryDependenceResults::getCallSiteDependencyFrom(
179 CallSite CS, bool isReadOnlyCall, BasicBlock::iterator ScanIt,
181 unsigned Limit = BlockScanLimit;
183 // Walk backwards through the block, looking for dependencies.
184 while (ScanIt != BB->begin()) {
185 // Limit the amount of scanning we do so we don't end up with quadratic
186 // running time on extreme testcases.
189 return MemDepResult::getUnknown();
191 Instruction *Inst = &*--ScanIt;
193 // If this inst is a memory op, get the pointer it accessed
195 ModRefInfo MR = GetLocation(Inst, Loc, TLI);
197 // A simple instruction.
198 if (AA.getModRefInfo(CS, Loc) != MRI_NoModRef)
199 return MemDepResult::getClobber(Inst);
203 if (auto InstCS = CallSite(Inst)) {
204 // Debug intrinsics don't cause dependences.
205 if (isa<DbgInfoIntrinsic>(Inst))
207 // If these two calls do not interfere, look past it.
208 switch (AA.getModRefInfo(CS, InstCS)) {
210 // If the two calls are the same, return InstCS as a Def, so that
211 // CS can be found redundant and eliminated.
212 if (isReadOnlyCall && !(MR & MRI_Mod) &&
213 CS.getInstruction()->isIdenticalToWhenDefined(Inst))
214 return MemDepResult::getDef(Inst);
216 // Otherwise if the two calls don't interact (e.g. InstCS is readnone)
220 return MemDepResult::getClobber(Inst);
224 // If we could not obtain a pointer for the instruction and the instruction
225 // touches memory then assume that this is a dependency.
226 if (MR != MRI_NoModRef)
227 return MemDepResult::getClobber(Inst);
230 // No dependence found. If this is the entry block of the function, it is
231 // unknown, otherwise it is non-local.
232 if (BB != &BB->getParent()->getEntryBlock())
233 return MemDepResult::getNonLocal();
234 return MemDepResult::getNonFuncLocal();
237 unsigned MemoryDependenceResults::getLoadLoadClobberFullWidthSize(
238 const Value *MemLocBase, int64_t MemLocOffs, unsigned MemLocSize,
239 const LoadInst *LI) {
240 // We can only extend simple integer loads.
241 if (!isa<IntegerType>(LI->getType()) || !LI->isSimple())
244 // Load widening is hostile to ThreadSanitizer: it may cause false positives
245 // or make the reports more cryptic (access sizes are wrong).
246 if (LI->getParent()->getParent()->hasFnAttribute(Attribute::SanitizeThread))
249 const DataLayout &DL = LI->getModule()->getDataLayout();
251 // Get the base of this load.
253 const Value *LIBase =
254 GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, DL);
256 // If the two pointers are not based on the same pointer, we can't tell that
258 if (LIBase != MemLocBase)
261 // Okay, the two values are based on the same pointer, but returned as
262 // no-alias. This happens when we have things like two byte loads at "P+1"
263 // and "P+3". Check to see if increasing the size of the "LI" load up to its
264 // alignment (or the largest native integer type) will allow us to load all
265 // the bits required by MemLoc.
267 // If MemLoc is before LI, then no widening of LI will help us out.
268 if (MemLocOffs < LIOffs)
271 // Get the alignment of the load in bytes. We assume that it is safe to load
272 // any legal integer up to this size without a problem. For example, if we're
273 // looking at an i8 load on x86-32 that is known 1024 byte aligned, we can
274 // widen it up to an i32 load. If it is known 2-byte aligned, we can widen it
276 unsigned LoadAlign = LI->getAlignment();
278 int64_t MemLocEnd = MemLocOffs + MemLocSize;
280 // If no amount of rounding up will let MemLoc fit into LI, then bail out.
281 if (LIOffs + LoadAlign < MemLocEnd)
284 // This is the size of the load to try. Start with the next larger power of
286 unsigned NewLoadByteSize = LI->getType()->getPrimitiveSizeInBits() / 8U;
287 NewLoadByteSize = NextPowerOf2(NewLoadByteSize);
290 // If this load size is bigger than our known alignment or would not fit
291 // into a native integer register, then we fail.
292 if (NewLoadByteSize > LoadAlign ||
293 !DL.fitsInLegalInteger(NewLoadByteSize * 8))
296 if (LIOffs + NewLoadByteSize > MemLocEnd &&
297 LI->getParent()->getParent()->hasFnAttribute(
298 Attribute::SanitizeAddress))
299 // We will be reading past the location accessed by the original program.
300 // While this is safe in a regular build, Address Safety analysis tools
301 // may start reporting false warnings. So, don't do widening.
304 // If a load of this width would include all of MemLoc, then we succeed.
305 if (LIOffs + NewLoadByteSize >= MemLocEnd)
306 return NewLoadByteSize;
308 NewLoadByteSize <<= 1;
312 static bool isVolatile(Instruction *Inst) {
313 if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
314 return LI->isVolatile();
315 else if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
316 return SI->isVolatile();
317 else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst))
318 return AI->isVolatile();
322 MemDepResult MemoryDependenceResults::getPointerDependencyFrom(
323 const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
324 BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
326 if (QueryInst != nullptr) {
327 if (auto *LI = dyn_cast<LoadInst>(QueryInst)) {
328 MemDepResult invariantGroupDependency =
329 getInvariantGroupPointerDependency(LI, BB);
331 if (invariantGroupDependency.isDef())
332 return invariantGroupDependency;
335 return getSimplePointerDependencyFrom(MemLoc, isLoad, ScanIt, BB, QueryInst,
340 MemoryDependenceResults::getInvariantGroupPointerDependency(LoadInst *LI,
343 auto *InvariantGroupMD = LI->getMetadata(LLVMContext::MD_invariant_group);
344 if (!InvariantGroupMD)
345 return MemDepResult::getUnknown();
347 Value *LoadOperand = LI->getPointerOperand();
348 // It's is not safe to walk the use list of global value, because function
349 // passes aren't allowed to look outside their functions.
350 if (isa<GlobalValue>(LoadOperand))
351 return MemDepResult::getUnknown();
353 // Queue to process all pointers that are equivalent to load operand.
354 SmallVector<const Value *, 8> LoadOperandsQueue;
355 SmallSet<const Value *, 14> SeenValues;
356 auto TryInsertToQueue = [&](Value *V) {
357 if (SeenValues.insert(V).second)
358 LoadOperandsQueue.push_back(V);
361 TryInsertToQueue(LoadOperand);
362 while (!LoadOperandsQueue.empty()) {
363 const Value *Ptr = LoadOperandsQueue.pop_back_val();
365 if (isa<GlobalValue>(Ptr))
368 // Value comes from bitcast: Ptr = bitcast x. Insert x.
369 if (auto *BCI = dyn_cast<BitCastInst>(Ptr))
370 TryInsertToQueue(BCI->getOperand(0));
371 // Gep with zeros is equivalent to bitcast.
372 // FIXME: we are not sure if some bitcast should be canonicalized to gep 0
373 // or gep 0 to bitcast because of SROA, so there are 2 forms. When typeless
374 // pointers will be upstream then both cases will be gone (and this BFS
375 // also won't be needed).
376 if (auto *GEP = dyn_cast<GetElementPtrInst>(Ptr))
377 if (GEP->hasAllZeroIndices())
378 TryInsertToQueue(GEP->getOperand(0));
380 for (const Use &Us : Ptr->uses()) {
381 auto *U = dyn_cast<Instruction>(Us.getUser());
382 if (!U || U == LI || !DT.dominates(U, LI))
385 // Bitcast or gep with zeros are using Ptr. Add to queue to check it's
386 // users. U = bitcast Ptr
387 if (isa<BitCastInst>(U)) {
391 // U = getelementptr Ptr, 0, 0...
392 if (auto *GEP = dyn_cast<GetElementPtrInst>(U))
393 if (GEP->hasAllZeroIndices()) {
398 // If we hit load/store with the same invariant.group metadata (and the
399 // same pointer operand) we can assume that value pointed by pointer
400 // operand didn't change.
401 if ((isa<LoadInst>(U) || isa<StoreInst>(U)) && U->getParent() == BB &&
402 U->getMetadata(LLVMContext::MD_invariant_group) == InvariantGroupMD)
403 return MemDepResult::getDef(U);
406 return MemDepResult::getUnknown();
409 MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
410 const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
411 BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
412 bool isInvariantLoad = false;
415 unsigned DefaultLimit = BlockScanLimit;
416 return getSimplePointerDependencyFrom(MemLoc, isLoad, ScanIt, BB, QueryInst,
420 // We must be careful with atomic accesses, as they may allow another thread
421 // to touch this location, clobbering it. We are conservative: if the
422 // QueryInst is not a simple (non-atomic) memory access, we automatically
423 // return getClobber.
424 // If it is simple, we know based on the results of
425 // "Compiler testing via a theory of sound optimisations in the C11/C++11
426 // memory model" in PLDI 2013, that a non-atomic location can only be
427 // clobbered between a pair of a release and an acquire action, with no
428 // access to the location in between.
429 // Here is an example for giving the general intuition behind this rule.
430 // In the following code:
432 // release action; [1]
433 // acquire action; [4]
435 // It is unsafe to replace %val by 0 because another thread may be running:
436 // acquire action; [2]
438 // release action; [3]
439 // with synchronization from 1 to 2 and from 3 to 4, resulting in %val
440 // being 42. A key property of this program however is that if either
441 // 1 or 4 were missing, there would be a race between the store of 42
442 // either the store of 0 or the load (making the whole program racy).
443 // The paper mentioned above shows that the same property is respected
444 // by every program that can detect any optimization of that kind: either
445 // it is racy (undefined) or there is a release followed by an acquire
446 // between the pair of accesses under consideration.
448 // If the load is invariant, we "know" that it doesn't alias *any* write. We
449 // do want to respect mustalias results since defs are useful for value
450 // forwarding, but any mayalias write can be assumed to be noalias.
451 // Arguably, this logic should be pushed inside AliasAnalysis itself.
452 if (isLoad && QueryInst) {
453 LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
454 if (LI && LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr)
455 isInvariantLoad = true;
458 const DataLayout &DL = BB->getModule()->getDataLayout();
460 // Create a numbered basic block to lazily compute and cache instruction
461 // positions inside a BB. This is used to provide fast queries for relative
462 // position between two instructions in a BB and can be used by
463 // AliasAnalysis::callCapturesBefore.
464 OrderedBasicBlock OBB(BB);
466 // Return "true" if and only if the instruction I is either a non-simple
467 // load or a non-simple store.
468 auto isNonSimpleLoadOrStore = [](Instruction *I) -> bool {
469 if (auto *LI = dyn_cast<LoadInst>(I))
470 return !LI->isSimple();
471 if (auto *SI = dyn_cast<StoreInst>(I))
472 return !SI->isSimple();
476 // Return "true" if I is not a load and not a store, but it does access
478 auto isOtherMemAccess = [](Instruction *I) -> bool {
479 return !isa<LoadInst>(I) && !isa<StoreInst>(I) && I->mayReadOrWriteMemory();
482 // Walk backwards through the basic block, looking for dependencies.
483 while (ScanIt != BB->begin()) {
484 Instruction *Inst = &*--ScanIt;
486 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
487 // Debug intrinsics don't (and can't) cause dependencies.
488 if (isa<DbgInfoIntrinsic>(II))
491 // Limit the amount of scanning we do so we don't end up with quadratic
492 // running time on extreme testcases.
495 return MemDepResult::getUnknown();
497 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
498 // If we reach a lifetime begin or end marker, then the query ends here
499 // because the value is undefined.
500 if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
501 // FIXME: This only considers queries directly on the invariant-tagged
502 // pointer, not on query pointers that are indexed off of them. It'd
503 // be nice to handle that at some point (the right approach is to use
504 // GetPointerBaseWithConstantOffset).
505 if (AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), MemLoc))
506 return MemDepResult::getDef(II);
511 // Values depend on loads if the pointers are must aliased. This means
512 // that a load depends on another must aliased load from the same value.
513 // One exception is atomic loads: a value can depend on an atomic load that
514 // it does not alias with when this atomic load indicates that another
515 // thread may be accessing the location.
516 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
518 // While volatile access cannot be eliminated, they do not have to clobber
519 // non-aliasing locations, as normal accesses, for example, can be safely
520 // reordered with volatile accesses.
521 if (LI->isVolatile()) {
523 // Original QueryInst *may* be volatile
524 return MemDepResult::getClobber(LI);
525 if (isVolatile(QueryInst))
526 // Ordering required if QueryInst is itself volatile
527 return MemDepResult::getClobber(LI);
528 // Otherwise, volatile doesn't imply any special ordering
531 // Atomic loads have complications involved.
532 // A Monotonic (or higher) load is OK if the query inst is itself not
534 // FIXME: This is overly conservative.
535 if (LI->isAtomic() && isStrongerThanUnordered(LI->getOrdering())) {
536 if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
537 isOtherMemAccess(QueryInst))
538 return MemDepResult::getClobber(LI);
539 if (LI->getOrdering() != AtomicOrdering::Monotonic)
540 return MemDepResult::getClobber(LI);
543 MemoryLocation LoadLoc = MemoryLocation::get(LI);
545 // If we found a pointer, check if it could be the same as our pointer.
546 AliasResult R = AA.alias(LoadLoc, MemLoc);
552 // Must aliased loads are defs of each other.
554 return MemDepResult::getDef(Inst);
556 #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads
557 // in terms of clobbering loads, but since it does this by looking
558 // at the clobbering load directly, it doesn't know about any
559 // phi translation that may have happened along the way.
561 // If we have a partial alias, then return this as a clobber for the
563 if (R == PartialAlias)
564 return MemDepResult::getClobber(Inst);
567 // Random may-alias loads don't depend on each other without a
572 // Stores don't depend on other no-aliased accesses.
576 // Stores don't alias loads from read-only memory.
577 if (AA.pointsToConstantMemory(LoadLoc))
580 // Stores depend on may/must aliased loads.
581 return MemDepResult::getDef(Inst);
584 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
585 // Atomic stores have complications involved.
586 // A Monotonic store is OK if the query inst is itself not atomic.
587 // FIXME: This is overly conservative.
588 if (!SI->isUnordered() && SI->isAtomic()) {
589 if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
590 isOtherMemAccess(QueryInst))
591 return MemDepResult::getClobber(SI);
592 if (SI->getOrdering() != AtomicOrdering::Monotonic)
593 return MemDepResult::getClobber(SI);
596 // FIXME: this is overly conservative.
597 // While volatile access cannot be eliminated, they do not have to clobber
598 // non-aliasing locations, as normal accesses can for example be reordered
599 // with volatile accesses.
600 if (SI->isVolatile())
601 if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
602 isOtherMemAccess(QueryInst))
603 return MemDepResult::getClobber(SI);
605 // If alias analysis can tell that this store is guaranteed to not modify
606 // the query pointer, ignore it. Use getModRefInfo to handle cases where
607 // the query pointer points to constant memory etc.
608 if (AA.getModRefInfo(SI, MemLoc) == MRI_NoModRef)
611 // Ok, this store might clobber the query pointer. Check to see if it is
612 // a must alias: in this case, we want to return this as a def.
613 MemoryLocation StoreLoc = MemoryLocation::get(SI);
615 // If we found a pointer, check if it could be the same as our pointer.
616 AliasResult R = AA.alias(StoreLoc, MemLoc);
621 return MemDepResult::getDef(Inst);
624 return MemDepResult::getClobber(Inst);
627 // If this is an allocation, and if we know that the accessed pointer is to
628 // the allocation, return Def. This means that there is no dependence and
629 // the access can be optimized based on that. For example, a load could
630 // turn into undef. Note that we can bypass the allocation itself when
631 // looking for a clobber in many cases; that's an alias property and is
632 // handled by BasicAA.
633 if (isa<AllocaInst>(Inst) || isNoAliasFn(Inst, &TLI)) {
634 const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, DL);
635 if (AccessPtr == Inst || AA.isMustAlias(Inst, AccessPtr))
636 return MemDepResult::getDef(Inst);
642 // A release fence requires that all stores complete before it, but does
643 // not prevent the reordering of following loads or stores 'before' the
644 // fence. As a result, we look past it when finding a dependency for
645 // loads. DSE uses this to find preceeding stores to delete and thus we
646 // can't bypass the fence if the query instruction is a store.
647 if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
648 if (isLoad && FI->getOrdering() == AtomicOrdering::Release)
651 // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
652 ModRefInfo MR = AA.getModRefInfo(Inst, MemLoc);
653 // If necessary, perform additional analysis.
654 if (MR == MRI_ModRef)
655 MR = AA.callCapturesBefore(Inst, MemLoc, &DT, &OBB);
658 // If the call has no effect on the queried pointer, just ignore it.
661 return MemDepResult::getClobber(Inst);
663 // If the call is known to never store to the pointer, and if this is a
664 // load query, we can safely ignore it (scan past it).
668 // Otherwise, there is a potential dependence. Return a clobber.
669 return MemDepResult::getClobber(Inst);
673 // No dependence found. If this is the entry block of the function, it is
674 // unknown, otherwise it is non-local.
675 if (BB != &BB->getParent()->getEntryBlock())
676 return MemDepResult::getNonLocal();
677 return MemDepResult::getNonFuncLocal();
680 MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst) {
681 Instruction *ScanPos = QueryInst;
683 // Check for a cached result
684 MemDepResult &LocalCache = LocalDeps[QueryInst];
686 // If the cached entry is non-dirty, just return it. Note that this depends
687 // on MemDepResult's default constructing to 'dirty'.
688 if (!LocalCache.isDirty())
691 // Otherwise, if we have a dirty entry, we know we can start the scan at that
692 // instruction, which may save us some work.
693 if (Instruction *Inst = LocalCache.getInst()) {
696 RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
699 BasicBlock *QueryParent = QueryInst->getParent();
702 if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
703 // No dependence found. If this is the entry block of the function, it is
704 // unknown, otherwise it is non-local.
705 if (QueryParent != &QueryParent->getParent()->getEntryBlock())
706 LocalCache = MemDepResult::getNonLocal();
708 LocalCache = MemDepResult::getNonFuncLocal();
710 MemoryLocation MemLoc;
711 ModRefInfo MR = GetLocation(QueryInst, MemLoc, TLI);
713 // If we can do a pointer scan, make it happen.
714 bool isLoad = !(MR & MRI_Mod);
715 if (auto *II = dyn_cast<IntrinsicInst>(QueryInst))
716 isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
718 LocalCache = getPointerDependencyFrom(
719 MemLoc, isLoad, ScanPos->getIterator(), QueryParent, QueryInst);
720 } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
721 CallSite QueryCS(QueryInst);
722 bool isReadOnly = AA.onlyReadsMemory(QueryCS);
723 LocalCache = getCallSiteDependencyFrom(
724 QueryCS, isReadOnly, ScanPos->getIterator(), QueryParent);
726 // Non-memory instruction.
727 LocalCache = MemDepResult::getUnknown();
730 // Remember the result!
731 if (Instruction *I = LocalCache.getInst())
732 ReverseLocalDeps[I].insert(QueryInst);
738 /// This method is used when -debug is specified to verify that cache arrays
739 /// are properly kept sorted.
740 static void AssertSorted(MemoryDependenceResults::NonLocalDepInfo &Cache,
743 Count = Cache.size();
744 assert(std::is_sorted(Cache.begin(), Cache.begin() + Count) &&
745 "Cache isn't sorted!");
749 const MemoryDependenceResults::NonLocalDepInfo &
750 MemoryDependenceResults::getNonLocalCallDependency(CallSite QueryCS) {
751 assert(getDependency(QueryCS.getInstruction()).isNonLocal() &&
752 "getNonLocalCallDependency should only be used on calls with "
754 PerInstNLInfo &CacheP = NonLocalDeps[QueryCS.getInstruction()];
755 NonLocalDepInfo &Cache = CacheP.first;
757 // This is the set of blocks that need to be recomputed. In the cached case,
758 // this can happen due to instructions being deleted etc. In the uncached
759 // case, this starts out as the set of predecessors we care about.
760 SmallVector<BasicBlock *, 32> DirtyBlocks;
762 if (!Cache.empty()) {
763 // Okay, we have a cache entry. If we know it is not dirty, just return it
764 // with no computation.
765 if (!CacheP.second) {
770 // If we already have a partially computed set of results, scan them to
771 // determine what is dirty, seeding our initial DirtyBlocks worklist.
772 for (auto &Entry : Cache)
773 if (Entry.getResult().isDirty())
774 DirtyBlocks.push_back(Entry.getBB());
776 // Sort the cache so that we can do fast binary search lookups below.
777 std::sort(Cache.begin(), Cache.end());
779 ++NumCacheDirtyNonLocal;
780 // cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
781 // << Cache.size() << " cached: " << *QueryInst;
783 // Seed DirtyBlocks with each of the preds of QueryInst's block.
784 BasicBlock *QueryBB = QueryCS.getInstruction()->getParent();
785 for (BasicBlock *Pred : PredCache.get(QueryBB))
786 DirtyBlocks.push_back(Pred);
787 ++NumUncacheNonLocal;
790 // isReadonlyCall - If this is a read-only call, we can be more aggressive.
791 bool isReadonlyCall = AA.onlyReadsMemory(QueryCS);
793 SmallPtrSet<BasicBlock *, 32> Visited;
795 unsigned NumSortedEntries = Cache.size();
796 DEBUG(AssertSorted(Cache));
798 // Iterate while we still have blocks to update.
799 while (!DirtyBlocks.empty()) {
800 BasicBlock *DirtyBB = DirtyBlocks.back();
801 DirtyBlocks.pop_back();
803 // Already processed this block?
804 if (!Visited.insert(DirtyBB).second)
807 // Do a binary search to see if we already have an entry for this block in
808 // the cache set. If so, find it.
809 DEBUG(AssertSorted(Cache, NumSortedEntries));
810 NonLocalDepInfo::iterator Entry =
811 std::upper_bound(Cache.begin(), Cache.begin() + NumSortedEntries,
812 NonLocalDepEntry(DirtyBB));
813 if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB)
816 NonLocalDepEntry *ExistingResult = nullptr;
817 if (Entry != Cache.begin() + NumSortedEntries &&
818 Entry->getBB() == DirtyBB) {
819 // If we already have an entry, and if it isn't already dirty, the block
821 if (!Entry->getResult().isDirty())
824 // Otherwise, remember this slot so we can update the value.
825 ExistingResult = &*Entry;
828 // If the dirty entry has a pointer, start scanning from it so we don't have
829 // to rescan the entire block.
830 BasicBlock::iterator ScanPos = DirtyBB->end();
831 if (ExistingResult) {
832 if (Instruction *Inst = ExistingResult->getResult().getInst()) {
833 ScanPos = Inst->getIterator();
834 // We're removing QueryInst's use of Inst.
835 RemoveFromReverseMap(ReverseNonLocalDeps, Inst,
836 QueryCS.getInstruction());
840 // Find out if this block has a local dependency for QueryInst.
843 if (ScanPos != DirtyBB->begin()) {
845 getCallSiteDependencyFrom(QueryCS, isReadonlyCall, ScanPos, DirtyBB);
846 } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) {
847 // No dependence found. If this is the entry block of the function, it is
848 // a clobber, otherwise it is unknown.
849 Dep = MemDepResult::getNonLocal();
851 Dep = MemDepResult::getNonFuncLocal();
854 // If we had a dirty entry for the block, update it. Otherwise, just add
857 ExistingResult->setResult(Dep);
859 Cache.push_back(NonLocalDepEntry(DirtyBB, Dep));
861 // If the block has a dependency (i.e. it isn't completely transparent to
862 // the value), remember the association!
863 if (!Dep.isNonLocal()) {
864 // Keep the ReverseNonLocalDeps map up to date so we can efficiently
865 // update this when we remove instructions.
866 if (Instruction *Inst = Dep.getInst())
867 ReverseNonLocalDeps[Inst].insert(QueryCS.getInstruction());
870 // If the block *is* completely transparent to the load, we need to check
871 // the predecessors of this block. Add them to our worklist.
872 for (BasicBlock *Pred : PredCache.get(DirtyBB))
873 DirtyBlocks.push_back(Pred);
880 void MemoryDependenceResults::getNonLocalPointerDependency(
881 Instruction *QueryInst, SmallVectorImpl<NonLocalDepResult> &Result) {
882 const MemoryLocation Loc = MemoryLocation::get(QueryInst);
883 bool isLoad = isa<LoadInst>(QueryInst);
884 BasicBlock *FromBB = QueryInst->getParent();
887 assert(Loc.Ptr->getType()->isPointerTy() &&
888 "Can't get pointer deps of a non-pointer!");
891 // This routine does not expect to deal with volatile instructions.
892 // Doing so would require piping through the QueryInst all the way through.
893 // TODO: volatiles can't be elided, but they can be reordered with other
894 // non-volatile accesses.
896 // We currently give up on any instruction which is ordered, but we do handle
897 // atomic instructions which are unordered.
898 // TODO: Handle ordered instructions
899 auto isOrdered = [](Instruction *Inst) {
900 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
901 return !LI->isUnordered();
902 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
903 return !SI->isUnordered();
907 if (isVolatile(QueryInst) || isOrdered(QueryInst)) {
908 Result.push_back(NonLocalDepResult(FromBB, MemDepResult::getUnknown(),
909 const_cast<Value *>(Loc.Ptr)));
912 const DataLayout &DL = FromBB->getModule()->getDataLayout();
913 PHITransAddr Address(const_cast<Value *>(Loc.Ptr), DL, &AC);
915 // This is the set of blocks we've inspected, and the pointer we consider in
916 // each block. Because of critical edges, we currently bail out if querying
917 // a block with multiple different pointers. This can happen during PHI
919 DenseMap<BasicBlock *, Value *> Visited;
920 if (getNonLocalPointerDepFromBB(QueryInst, Address, Loc, isLoad, FromBB,
921 Result, Visited, true))
924 Result.push_back(NonLocalDepResult(FromBB, MemDepResult::getUnknown(),
925 const_cast<Value *>(Loc.Ptr)));
928 /// Compute the memdep value for BB with Pointer/PointeeSize using either
929 /// cached information in Cache or by doing a lookup (which may use dirty cache
930 /// info if available).
932 /// If we do a lookup, add the result to the cache.
933 MemDepResult MemoryDependenceResults::GetNonLocalInfoForBlock(
934 Instruction *QueryInst, const MemoryLocation &Loc, bool isLoad,
935 BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
937 // Do a binary search to see if we already have an entry for this block in
938 // the cache set. If so, find it.
939 NonLocalDepInfo::iterator Entry = std::upper_bound(
940 Cache->begin(), Cache->begin() + NumSortedEntries, NonLocalDepEntry(BB));
941 if (Entry != Cache->begin() && (Entry - 1)->getBB() == BB)
944 NonLocalDepEntry *ExistingResult = nullptr;
945 if (Entry != Cache->begin() + NumSortedEntries && Entry->getBB() == BB)
946 ExistingResult = &*Entry;
948 // If we have a cached entry, and it is non-dirty, use it as the value for
950 if (ExistingResult && !ExistingResult->getResult().isDirty()) {
951 ++NumCacheNonLocalPtr;
952 return ExistingResult->getResult();
955 // Otherwise, we have to scan for the value. If we have a dirty cache
956 // entry, start scanning from its position, otherwise we scan from the end
958 BasicBlock::iterator ScanPos = BB->end();
959 if (ExistingResult && ExistingResult->getResult().getInst()) {
960 assert(ExistingResult->getResult().getInst()->getParent() == BB &&
961 "Instruction invalidated?");
962 ++NumCacheDirtyNonLocalPtr;
963 ScanPos = ExistingResult->getResult().getInst()->getIterator();
965 // Eliminating the dirty entry from 'Cache', so update the reverse info.
966 ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
967 RemoveFromReverseMap(ReverseNonLocalPtrDeps, &*ScanPos, CacheKey);
969 ++NumUncacheNonLocalPtr;
972 // Scan the block for the dependency.
974 getPointerDependencyFrom(Loc, isLoad, ScanPos, BB, QueryInst);
976 // If we had a dirty entry for the block, update it. Otherwise, just add
979 ExistingResult->setResult(Dep);
981 Cache->push_back(NonLocalDepEntry(BB, Dep));
983 // If the block has a dependency (i.e. it isn't completely transparent to
984 // the value), remember the reverse association because we just added it
986 if (!Dep.isDef() && !Dep.isClobber())
989 // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
990 // update MemDep when we remove instructions.
991 Instruction *Inst = Dep.getInst();
992 assert(Inst && "Didn't depend on anything?");
993 ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
994 ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
998 /// Sort the NonLocalDepInfo cache, given a certain number of elements in the
999 /// array that are already properly ordered.
1001 /// This is optimized for the case when only a few entries are added.
1003 SortNonLocalDepInfoCache(MemoryDependenceResults::NonLocalDepInfo &Cache,
1004 unsigned NumSortedEntries) {
1005 switch (Cache.size() - NumSortedEntries) {
1007 // done, no new entries.
1010 // Two new entries, insert the last one into place.
1011 NonLocalDepEntry Val = Cache.back();
1013 MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
1014 std::upper_bound(Cache.begin(), Cache.end() - 1, Val);
1015 Cache.insert(Entry, Val);
1019 // One new entry, Just insert the new value at the appropriate position.
1020 if (Cache.size() != 1) {
1021 NonLocalDepEntry Val = Cache.back();
1023 MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
1024 std::upper_bound(Cache.begin(), Cache.end(), Val);
1025 Cache.insert(Entry, Val);
1029 // Added many values, do a full scale sort.
1030 std::sort(Cache.begin(), Cache.end());
1035 /// Perform a dependency query based on pointer/pointeesize starting at the end
1038 /// Add any clobber/def results to the results vector and keep track of which
1039 /// blocks are visited in 'Visited'.
1041 /// This has special behavior for the first block queries (when SkipFirstBlock
1042 /// is true). In this special case, it ignores the contents of the specified
1043 /// block and starts returning dependence info for its predecessors.
1045 /// This function returns true on success, or false to indicate that it could
1046 /// not compute dependence information for some reason. This should be treated
1047 /// as a clobber dependence on the first instruction in the predecessor block.
1048 bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
1049 Instruction *QueryInst, const PHITransAddr &Pointer,
1050 const MemoryLocation &Loc, bool isLoad, BasicBlock *StartBB,
1051 SmallVectorImpl<NonLocalDepResult> &Result,
1052 DenseMap<BasicBlock *, Value *> &Visited, bool SkipFirstBlock) {
1053 // Look up the cached info for Pointer.
1054 ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
1056 // Set up a temporary NLPI value. If the map doesn't yet have an entry for
1057 // CacheKey, this value will be inserted as the associated value. Otherwise,
1058 // it'll be ignored, and we'll have to check to see if the cached size and
1059 // aa tags are consistent with the current query.
1060 NonLocalPointerInfo InitialNLPI;
1061 InitialNLPI.Size = Loc.Size;
1062 InitialNLPI.AATags = Loc.AATags;
1064 // Get the NLPI for CacheKey, inserting one into the map if it doesn't
1065 // already have one.
1066 std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
1067 NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
1068 NonLocalPointerInfo *CacheInfo = &Pair.first->second;
1070 // If we already have a cache entry for this CacheKey, we may need to do some
1071 // work to reconcile the cache entry and the current query.
1073 if (CacheInfo->Size < Loc.Size) {
1074 // The query's Size is greater than the cached one. Throw out the
1075 // cached data and proceed with the query at the greater size.
1076 CacheInfo->Pair = BBSkipFirstBlockPair();
1077 CacheInfo->Size = Loc.Size;
1078 for (auto &Entry : CacheInfo->NonLocalDeps)
1079 if (Instruction *Inst = Entry.getResult().getInst())
1080 RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
1081 CacheInfo->NonLocalDeps.clear();
1082 } else if (CacheInfo->Size > Loc.Size) {
1083 // This query's Size is less than the cached one. Conservatively restart
1084 // the query using the greater size.
1085 return getNonLocalPointerDepFromBB(
1086 QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad,
1087 StartBB, Result, Visited, SkipFirstBlock);
1090 // If the query's AATags are inconsistent with the cached one,
1091 // conservatively throw out the cached data and restart the query with
1092 // no tag if needed.
1093 if (CacheInfo->AATags != Loc.AATags) {
1094 if (CacheInfo->AATags) {
1095 CacheInfo->Pair = BBSkipFirstBlockPair();
1096 CacheInfo->AATags = AAMDNodes();
1097 for (auto &Entry : CacheInfo->NonLocalDeps)
1098 if (Instruction *Inst = Entry.getResult().getInst())
1099 RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
1100 CacheInfo->NonLocalDeps.clear();
1103 return getNonLocalPointerDepFromBB(
1104 QueryInst, Pointer, Loc.getWithoutAATags(), isLoad, StartBB, Result,
1105 Visited, SkipFirstBlock);
1109 NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps;
1111 // If we have valid cached information for exactly the block we are
1112 // investigating, just return it with no recomputation.
1113 if (CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
1114 // We have a fully cached result for this query then we can just return the
1115 // cached results and populate the visited set. However, we have to verify
1116 // that we don't already have conflicting results for these blocks. Check
1117 // to ensure that if a block in the results set is in the visited set that
1118 // it was for the same pointer query.
1119 if (!Visited.empty()) {
1120 for (auto &Entry : *Cache) {
1121 DenseMap<BasicBlock *, Value *>::iterator VI =
1122 Visited.find(Entry.getBB());
1123 if (VI == Visited.end() || VI->second == Pointer.getAddr())
1126 // We have a pointer mismatch in a block. Just return false, saying
1127 // that something was clobbered in this result. We could also do a
1128 // non-fully cached query, but there is little point in doing this.
1133 Value *Addr = Pointer.getAddr();
1134 for (auto &Entry : *Cache) {
1135 Visited.insert(std::make_pair(Entry.getBB(), Addr));
1136 if (Entry.getResult().isNonLocal()) {
1140 if (DT.isReachableFromEntry(Entry.getBB())) {
1142 NonLocalDepResult(Entry.getBB(), Entry.getResult(), Addr));
1145 ++NumCacheCompleteNonLocalPtr;
1149 // Otherwise, either this is a new block, a block with an invalid cache
1150 // pointer or one that we're about to invalidate by putting more info into it
1151 // than its valid cache info. If empty, the result will be valid cache info,
1152 // otherwise it isn't.
1154 CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
1156 CacheInfo->Pair = BBSkipFirstBlockPair();
1158 SmallVector<BasicBlock *, 32> Worklist;
1159 Worklist.push_back(StartBB);
1161 // PredList used inside loop.
1162 SmallVector<std::pair<BasicBlock *, PHITransAddr>, 16> PredList;
1164 // Keep track of the entries that we know are sorted. Previously cached
1165 // entries will all be sorted. The entries we add we only sort on demand (we
1166 // don't insert every element into its sorted position). We know that we
1167 // won't get any reuse from currently inserted values, because we don't
1168 // revisit blocks after we insert info for them.
1169 unsigned NumSortedEntries = Cache->size();
1170 unsigned WorklistEntries = BlockNumberLimit;
1171 bool GotWorklistLimit = false;
1172 DEBUG(AssertSorted(*Cache));
1174 while (!Worklist.empty()) {
1175 BasicBlock *BB = Worklist.pop_back_val();
1177 // If we do process a large number of blocks it becomes very expensive and
1178 // likely it isn't worth worrying about
1179 if (Result.size() > NumResultsLimit) {
1181 // Sort it now (if needed) so that recursive invocations of
1182 // getNonLocalPointerDepFromBB and other routines that could reuse the
1183 // cache value will only see properly sorted cache arrays.
1184 if (Cache && NumSortedEntries != Cache->size()) {
1185 SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1187 // Since we bail out, the "Cache" set won't contain all of the
1188 // results for the query. This is ok (we can still use it to accelerate
1189 // specific block queries) but we can't do the fastpath "return all
1190 // results from the set". Clear out the indicator for this.
1191 CacheInfo->Pair = BBSkipFirstBlockPair();
1195 // Skip the first block if we have it.
1196 if (!SkipFirstBlock) {
1197 // Analyze the dependency of *Pointer in FromBB. See if we already have
1199 assert(Visited.count(BB) && "Should check 'visited' before adding to WL");
1201 // Get the dependency info for Pointer in BB. If we have cached
1202 // information, we will use it, otherwise we compute it.
1203 DEBUG(AssertSorted(*Cache, NumSortedEntries));
1204 MemDepResult Dep = GetNonLocalInfoForBlock(QueryInst, Loc, isLoad, BB,
1205 Cache, NumSortedEntries);
1207 // If we got a Def or Clobber, add this to the list of results.
1208 if (!Dep.isNonLocal()) {
1209 if (DT.isReachableFromEntry(BB)) {
1210 Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));
1216 // If 'Pointer' is an instruction defined in this block, then we need to do
1217 // phi translation to change it into a value live in the predecessor block.
1218 // If not, we just add the predecessors to the worklist and scan them with
1219 // the same Pointer.
1220 if (!Pointer.NeedsPHITranslationFromBlock(BB)) {
1221 SkipFirstBlock = false;
1222 SmallVector<BasicBlock *, 16> NewBlocks;
1223 for (BasicBlock *Pred : PredCache.get(BB)) {
1224 // Verify that we haven't looked at this block yet.
1225 std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> InsertRes =
1226 Visited.insert(std::make_pair(Pred, Pointer.getAddr()));
1227 if (InsertRes.second) {
1228 // First time we've looked at *PI.
1229 NewBlocks.push_back(Pred);
1233 // If we have seen this block before, but it was with a different
1234 // pointer then we have a phi translation failure and we have to treat
1235 // this as a clobber.
1236 if (InsertRes.first->second != Pointer.getAddr()) {
1237 // Make sure to clean up the Visited map before continuing on to
1238 // PredTranslationFailure.
1239 for (unsigned i = 0; i < NewBlocks.size(); i++)
1240 Visited.erase(NewBlocks[i]);
1241 goto PredTranslationFailure;
1244 if (NewBlocks.size() > WorklistEntries) {
1245 // Make sure to clean up the Visited map before continuing on to
1246 // PredTranslationFailure.
1247 for (unsigned i = 0; i < NewBlocks.size(); i++)
1248 Visited.erase(NewBlocks[i]);
1249 GotWorklistLimit = true;
1250 goto PredTranslationFailure;
1252 WorklistEntries -= NewBlocks.size();
1253 Worklist.append(NewBlocks.begin(), NewBlocks.end());
1257 // We do need to do phi translation, if we know ahead of time we can't phi
1258 // translate this value, don't even try.
1259 if (!Pointer.IsPotentiallyPHITranslatable())
1260 goto PredTranslationFailure;
1262 // We may have added values to the cache list before this PHI translation.
1263 // If so, we haven't done anything to ensure that the cache remains sorted.
1264 // Sort it now (if needed) so that recursive invocations of
1265 // getNonLocalPointerDepFromBB and other routines that could reuse the cache
1266 // value will only see properly sorted cache arrays.
1267 if (Cache && NumSortedEntries != Cache->size()) {
1268 SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1269 NumSortedEntries = Cache->size();
1274 for (BasicBlock *Pred : PredCache.get(BB)) {
1275 PredList.push_back(std::make_pair(Pred, Pointer));
1277 // Get the PHI translated pointer in this predecessor. This can fail if
1278 // not translatable, in which case the getAddr() returns null.
1279 PHITransAddr &PredPointer = PredList.back().second;
1280 PredPointer.PHITranslateValue(BB, Pred, &DT, /*MustDominate=*/false);
1281 Value *PredPtrVal = PredPointer.getAddr();
1283 // Check to see if we have already visited this pred block with another
1284 // pointer. If so, we can't do this lookup. This failure can occur
1285 // with PHI translation when a critical edge exists and the PHI node in
1286 // the successor translates to a pointer value different than the
1287 // pointer the block was first analyzed with.
1288 std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> InsertRes =
1289 Visited.insert(std::make_pair(Pred, PredPtrVal));
1291 if (!InsertRes.second) {
1292 // We found the pred; take it off the list of preds to visit.
1293 PredList.pop_back();
1295 // If the predecessor was visited with PredPtr, then we already did
1296 // the analysis and can ignore it.
1297 if (InsertRes.first->second == PredPtrVal)
1300 // Otherwise, the block was previously analyzed with a different
1301 // pointer. We can't represent the result of this case, so we just
1302 // treat this as a phi translation failure.
1304 // Make sure to clean up the Visited map before continuing on to
1305 // PredTranslationFailure.
1306 for (unsigned i = 0, n = PredList.size(); i < n; ++i)
1307 Visited.erase(PredList[i].first);
1309 goto PredTranslationFailure;
1313 // Actually process results here; this need to be a separate loop to avoid
1314 // calling getNonLocalPointerDepFromBB for blocks we don't want to return
1315 // any results for. (getNonLocalPointerDepFromBB will modify our
1316 // datastructures in ways the code after the PredTranslationFailure label
1318 for (unsigned i = 0, n = PredList.size(); i < n; ++i) {
1319 BasicBlock *Pred = PredList[i].first;
1320 PHITransAddr &PredPointer = PredList[i].second;
1321 Value *PredPtrVal = PredPointer.getAddr();
1323 bool CanTranslate = true;
1324 // If PHI translation was unable to find an available pointer in this
1325 // predecessor, then we have to assume that the pointer is clobbered in
1326 // that predecessor. We can still do PRE of the load, which would insert
1327 // a computation of the pointer in this predecessor.
1329 CanTranslate = false;
1331 // FIXME: it is entirely possible that PHI translating will end up with
1332 // the same value. Consider PHI translating something like:
1333 // X = phi [x, bb1], [y, bb2]. PHI translating for bb1 doesn't *need*
1334 // to recurse here, pedantically speaking.
1336 // If getNonLocalPointerDepFromBB fails here, that means the cached
1337 // result conflicted with the Visited list; we have to conservatively
1338 // assume it is unknown, but this also does not block PRE of the load.
1339 if (!CanTranslate ||
1340 !getNonLocalPointerDepFromBB(QueryInst, PredPointer,
1341 Loc.getWithNewPtr(PredPtrVal), isLoad,
1342 Pred, Result, Visited)) {
1343 // Add the entry to the Result list.
1344 NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal);
1345 Result.push_back(Entry);
1347 // Since we had a phi translation failure, the cache for CacheKey won't
1348 // include all of the entries that we need to immediately satisfy future
1349 // queries. Mark this in NonLocalPointerDeps by setting the
1350 // BBSkipFirstBlockPair pointer to null. This requires reuse of the
1351 // cached value to do more work but not miss the phi trans failure.
1352 NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
1353 NLPI.Pair = BBSkipFirstBlockPair();
1358 // Refresh the CacheInfo/Cache pointer so that it isn't invalidated.
1359 CacheInfo = &NonLocalPointerDeps[CacheKey];
1360 Cache = &CacheInfo->NonLocalDeps;
1361 NumSortedEntries = Cache->size();
1363 // Since we did phi translation, the "Cache" set won't contain all of the
1364 // results for the query. This is ok (we can still use it to accelerate
1365 // specific block queries) but we can't do the fastpath "return all
1366 // results from the set" Clear out the indicator for this.
1367 CacheInfo->Pair = BBSkipFirstBlockPair();
1368 SkipFirstBlock = false;
1371 PredTranslationFailure:
1372 // The following code is "failure"; we can't produce a sane translation
1373 // for the given block. It assumes that we haven't modified any of
1374 // our datastructures while processing the current block.
1377 // Refresh the CacheInfo/Cache pointer if it got invalidated.
1378 CacheInfo = &NonLocalPointerDeps[CacheKey];
1379 Cache = &CacheInfo->NonLocalDeps;
1380 NumSortedEntries = Cache->size();
1383 // Since we failed phi translation, the "Cache" set won't contain all of the
1384 // results for the query. This is ok (we can still use it to accelerate
1385 // specific block queries) but we can't do the fastpath "return all
1386 // results from the set". Clear out the indicator for this.
1387 CacheInfo->Pair = BBSkipFirstBlockPair();
1389 // If *nothing* works, mark the pointer as unknown.
1391 // If this is the magic first block, return this as a clobber of the whole
1392 // incoming value. Since we can't phi translate to one of the predecessors,
1393 // we have to bail out.
1397 bool foundBlock = false;
1398 for (NonLocalDepEntry &I : llvm::reverse(*Cache)) {
1399 if (I.getBB() != BB)
1402 assert((GotWorklistLimit || I.getResult().isNonLocal() ||
1403 !DT.isReachableFromEntry(BB)) &&
1404 "Should only be here with transparent block");
1406 I.setResult(MemDepResult::getUnknown());
1408 NonLocalDepResult(I.getBB(), I.getResult(), Pointer.getAddr()));
1411 (void)foundBlock; (void)GotWorklistLimit;
1412 assert((foundBlock || GotWorklistLimit) && "Current block not in cache?");
1415 // Okay, we're done now. If we added new values to the cache, re-sort it.
1416 SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1417 DEBUG(AssertSorted(*Cache));
1421 /// If P exists in CachedNonLocalPointerInfo, remove it.
1422 void MemoryDependenceResults::RemoveCachedNonLocalPointerDependencies(
1423 ValueIsLoadPair P) {
1424 CachedNonLocalPointerInfo::iterator It = NonLocalPointerDeps.find(P);
1425 if (It == NonLocalPointerDeps.end())
1428 // Remove all of the entries in the BB->val map. This involves removing
1429 // instructions from the reverse map.
1430 NonLocalDepInfo &PInfo = It->second.NonLocalDeps;
1432 for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
1433 Instruction *Target = PInfo[i].getResult().getInst();
1435 continue; // Ignore non-local dep results.
1436 assert(Target->getParent() == PInfo[i].getBB());
1438 // Eliminating the dirty entry from 'Cache', so update the reverse info.
1439 RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P);
1442 // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
1443 NonLocalPointerDeps.erase(It);
1446 void MemoryDependenceResults::invalidateCachedPointerInfo(Value *Ptr) {
1447 // If Ptr isn't really a pointer, just ignore it.
1448 if (!Ptr->getType()->isPointerTy())
1450 // Flush store info for the pointer.
1451 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false));
1452 // Flush load info for the pointer.
1453 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
1456 void MemoryDependenceResults::invalidateCachedPredecessors() {
1460 void MemoryDependenceResults::removeInstruction(Instruction *RemInst) {
1461 // Walk through the Non-local dependencies, removing this one as the value
1462 // for any cached queries.
1463 NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
1464 if (NLDI != NonLocalDeps.end()) {
1465 NonLocalDepInfo &BlockMap = NLDI->second.first;
1466 for (auto &Entry : BlockMap)
1467 if (Instruction *Inst = Entry.getResult().getInst())
1468 RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
1469 NonLocalDeps.erase(NLDI);
1472 // If we have a cached local dependence query for this instruction, remove it.
1474 LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
1475 if (LocalDepEntry != LocalDeps.end()) {
1476 // Remove us from DepInst's reverse set now that the local dep info is gone.
1477 if (Instruction *Inst = LocalDepEntry->second.getInst())
1478 RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
1480 // Remove this local dependency info.
1481 LocalDeps.erase(LocalDepEntry);
1484 // If we have any cached pointer dependencies on this instruction, remove
1485 // them. If the instruction has non-pointer type, then it can't be a pointer
1488 // Remove it from both the load info and the store info. The instruction
1489 // can't be in either of these maps if it is non-pointer.
1490 if (RemInst->getType()->isPointerTy()) {
1491 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
1492 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
1495 // Loop over all of the things that depend on the instruction we're removing.
1497 SmallVector<std::pair<Instruction *, Instruction *>, 8> ReverseDepsToAdd;
1499 // If we find RemInst as a clobber or Def in any of the maps for other values,
1500 // we need to replace its entry with a dirty version of the instruction after
1501 // it. If RemInst is a terminator, we use a null dirty value.
1503 // Using a dirty version of the instruction after RemInst saves having to scan
1504 // the entire block to get to this point.
1505 MemDepResult NewDirtyVal;
1506 if (!RemInst->isTerminator())
1507 NewDirtyVal = MemDepResult::getDirty(&*++RemInst->getIterator());
1509 ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
1510 if (ReverseDepIt != ReverseLocalDeps.end()) {
1511 // RemInst can't be the terminator if it has local stuff depending on it.
1512 assert(!ReverseDepIt->second.empty() && !isa<TerminatorInst>(RemInst) &&
1513 "Nothing can locally depend on a terminator");
1515 for (Instruction *InstDependingOnRemInst : ReverseDepIt->second) {
1516 assert(InstDependingOnRemInst != RemInst &&
1517 "Already removed our local dep info");
1519 LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
1521 // Make sure to remember that new things depend on NewDepInst.
1522 assert(NewDirtyVal.getInst() &&
1523 "There is no way something else can have "
1524 "a local dep on this if it is a terminator!");
1525 ReverseDepsToAdd.push_back(
1526 std::make_pair(NewDirtyVal.getInst(), InstDependingOnRemInst));
1529 ReverseLocalDeps.erase(ReverseDepIt);
1531 // Add new reverse deps after scanning the set, to avoid invalidating the
1532 // 'ReverseDeps' reference.
1533 while (!ReverseDepsToAdd.empty()) {
1534 ReverseLocalDeps[ReverseDepsToAdd.back().first].insert(
1535 ReverseDepsToAdd.back().second);
1536 ReverseDepsToAdd.pop_back();
1540 ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
1541 if (ReverseDepIt != ReverseNonLocalDeps.end()) {
1542 for (Instruction *I : ReverseDepIt->second) {
1543 assert(I != RemInst && "Already removed NonLocalDep info for RemInst");
1545 PerInstNLInfo &INLD = NonLocalDeps[I];
1546 // The information is now dirty!
1549 for (auto &Entry : INLD.first) {
1550 if (Entry.getResult().getInst() != RemInst)
1553 // Convert to a dirty entry for the subsequent instruction.
1554 Entry.setResult(NewDirtyVal);
1556 if (Instruction *NextI = NewDirtyVal.getInst())
1557 ReverseDepsToAdd.push_back(std::make_pair(NextI, I));
1561 ReverseNonLocalDeps.erase(ReverseDepIt);
1563 // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
1564 while (!ReverseDepsToAdd.empty()) {
1565 ReverseNonLocalDeps[ReverseDepsToAdd.back().first].insert(
1566 ReverseDepsToAdd.back().second);
1567 ReverseDepsToAdd.pop_back();
1571 // If the instruction is in ReverseNonLocalPtrDeps then it appears as a
1572 // value in the NonLocalPointerDeps info.
1573 ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
1574 ReverseNonLocalPtrDeps.find(RemInst);
1575 if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
1576 SmallVector<std::pair<Instruction *, ValueIsLoadPair>, 8>
1577 ReversePtrDepsToAdd;
1579 for (ValueIsLoadPair P : ReversePtrDepIt->second) {
1580 assert(P.getPointer() != RemInst &&
1581 "Already removed NonLocalPointerDeps info for RemInst");
1583 NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].NonLocalDeps;
1585 // The cache is not valid for any specific block anymore.
1586 NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair();
1588 // Update any entries for RemInst to use the instruction after it.
1589 for (auto &Entry : NLPDI) {
1590 if (Entry.getResult().getInst() != RemInst)
1593 // Convert to a dirty entry for the subsequent instruction.
1594 Entry.setResult(NewDirtyVal);
1596 if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
1597 ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
1600 // Re-sort the NonLocalDepInfo. Changing the dirty entry to its
1601 // subsequent value may invalidate the sortedness.
1602 std::sort(NLPDI.begin(), NLPDI.end());
1605 ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
1607 while (!ReversePtrDepsToAdd.empty()) {
1608 ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first].insert(
1609 ReversePtrDepsToAdd.back().second);
1610 ReversePtrDepsToAdd.pop_back();
1614 assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
1615 DEBUG(verifyRemoved(RemInst));
1618 /// Verify that the specified instruction does not occur in our internal data
1621 /// This function verifies by asserting in debug builds.
1622 void MemoryDependenceResults::verifyRemoved(Instruction *D) const {
1624 for (const auto &DepKV : LocalDeps) {
1625 assert(DepKV.first != D && "Inst occurs in data structures");
1626 assert(DepKV.second.getInst() != D && "Inst occurs in data structures");
1629 for (const auto &DepKV : NonLocalPointerDeps) {
1630 assert(DepKV.first.getPointer() != D && "Inst occurs in NLPD map key");
1631 for (const auto &Entry : DepKV.second.NonLocalDeps)
1632 assert(Entry.getResult().getInst() != D && "Inst occurs as NLPD value");
1635 for (const auto &DepKV : NonLocalDeps) {
1636 assert(DepKV.first != D && "Inst occurs in data structures");
1637 const PerInstNLInfo &INLD = DepKV.second;
1638 for (const auto &Entry : INLD.first)
1639 assert(Entry.getResult().getInst() != D &&
1640 "Inst occurs in data structures");
1643 for (const auto &DepKV : ReverseLocalDeps) {
1644 assert(DepKV.first != D && "Inst occurs in data structures");
1645 for (Instruction *Inst : DepKV.second)
1646 assert(Inst != D && "Inst occurs in data structures");
1649 for (const auto &DepKV : ReverseNonLocalDeps) {
1650 assert(DepKV.first != D && "Inst occurs in data structures");
1651 for (Instruction *Inst : DepKV.second)
1652 assert(Inst != D && "Inst occurs in data structures");
1655 for (const auto &DepKV : ReverseNonLocalPtrDeps) {
1656 assert(DepKV.first != D && "Inst occurs in rev NLPD map");
1658 for (ValueIsLoadPair P : DepKV.second)
1659 assert(P != ValueIsLoadPair(D, false) && P != ValueIsLoadPair(D, true) &&
1660 "Inst occurs in ReverseNonLocalPtrDeps map");
1665 AnalysisKey MemoryDependenceAnalysis::Key;
1667 MemoryDependenceResults
1668 MemoryDependenceAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
1669 auto &AA = AM.getResult<AAManager>(F);
1670 auto &AC = AM.getResult<AssumptionAnalysis>(F);
1671 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1672 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1673 return MemoryDependenceResults(AA, AC, TLI, DT);
1676 char MemoryDependenceWrapperPass::ID = 0;
1678 INITIALIZE_PASS_BEGIN(MemoryDependenceWrapperPass, "memdep",
1679 "Memory Dependence Analysis", false, true)
1680 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1681 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1682 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1683 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1684 INITIALIZE_PASS_END(MemoryDependenceWrapperPass, "memdep",
1685 "Memory Dependence Analysis", false, true)
1687 MemoryDependenceWrapperPass::MemoryDependenceWrapperPass() : FunctionPass(ID) {
1688 initializeMemoryDependenceWrapperPassPass(*PassRegistry::getPassRegistry());
1691 MemoryDependenceWrapperPass::~MemoryDependenceWrapperPass() {}
1693 void MemoryDependenceWrapperPass::releaseMemory() {
1697 void MemoryDependenceWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1698 AU.setPreservesAll();
1699 AU.addRequired<AssumptionCacheTracker>();
1700 AU.addRequired<DominatorTreeWrapperPass>();
1701 AU.addRequiredTransitive<AAResultsWrapperPass>();
1702 AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
1705 bool MemoryDependenceResults::invalidate(Function &F, const PreservedAnalyses &PA,
1706 FunctionAnalysisManager::Invalidator &Inv) {
1707 // Check whether our analysis is preserved.
1708 auto PAC = PA.getChecker<MemoryDependenceAnalysis>();
1709 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
1710 // If not, give up now.
1713 // Check whether the analyses we depend on became invalid for any reason.
1714 if (Inv.invalidate<AAManager>(F, PA) ||
1715 Inv.invalidate<AssumptionAnalysis>(F, PA) ||
1716 Inv.invalidate<DominatorTreeAnalysis>(F, PA))
1719 // Otherwise this analysis result remains valid.
1723 unsigned MemoryDependenceResults::getDefaultBlockScanLimit() const {
1724 return BlockScanLimit;
1727 bool MemoryDependenceWrapperPass::runOnFunction(Function &F) {
1728 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1729 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1730 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1731 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1732 MemDep.emplace(AA, AC, TLI, DT);