1 //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation -------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements an analysis that determines, for a given memory
10 // operation, what preceding memory operations it depends on. It builds on
11 // alias analysis information, and tries to provide a lazy, caching interface to
12 // a common kind of alias information query.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.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/MemoryLocation.h"
26 #include "llvm/Analysis/OrderedBasicBlock.h"
27 #include "llvm/Analysis/PHITransAddr.h"
28 #include "llvm/Analysis/PhiValues.h"
29 #include "llvm/Analysis/TargetLibraryInfo.h"
30 #include "llvm/Analysis/ValueTracking.h"
31 #include "llvm/IR/Attributes.h"
32 #include "llvm/IR/BasicBlock.h"
33 #include "llvm/IR/Constants.h"
34 #include "llvm/IR/DataLayout.h"
35 #include "llvm/IR/DerivedTypes.h"
36 #include "llvm/IR/Dominators.h"
37 #include "llvm/IR/Function.h"
38 #include "llvm/IR/InstrTypes.h"
39 #include "llvm/IR/Instruction.h"
40 #include "llvm/IR/Instructions.h"
41 #include "llvm/IR/IntrinsicInst.h"
42 #include "llvm/IR/LLVMContext.h"
43 #include "llvm/IR/Metadata.h"
44 #include "llvm/IR/Module.h"
45 #include "llvm/IR/PredIteratorCache.h"
46 #include "llvm/IR/Type.h"
47 #include "llvm/IR/Use.h"
48 #include "llvm/IR/User.h"
49 #include "llvm/IR/Value.h"
50 #include "llvm/InitializePasses.h"
51 #include "llvm/Pass.h"
52 #include "llvm/Support/AtomicOrdering.h"
53 #include "llvm/Support/Casting.h"
54 #include "llvm/Support/CommandLine.h"
55 #include "llvm/Support/Compiler.h"
56 #include "llvm/Support/Debug.h"
57 #include "llvm/Support/MathExtras.h"
66 #define DEBUG_TYPE "memdep"
68 STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");
69 STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");
70 STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");
72 STATISTIC(NumCacheNonLocalPtr,
73 "Number of fully cached non-local ptr responses");
74 STATISTIC(NumCacheDirtyNonLocalPtr,
75 "Number of cached, but dirty, non-local ptr responses");
76 STATISTIC(NumUncacheNonLocalPtr, "Number of uncached non-local ptr responses");
77 STATISTIC(NumCacheCompleteNonLocalPtr,
78 "Number of block queries that were completely cached");
80 // Limit for the number of instructions to scan in a block.
82 static cl::opt<unsigned> BlockScanLimit(
83 "memdep-block-scan-limit", cl::Hidden, cl::init(100),
84 cl::desc("The number of instructions to scan in a block in memory "
85 "dependency analysis (default = 100)"));
87 static cl::opt<unsigned>
88 BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(1000),
89 cl::desc("The number of blocks to scan during memory "
90 "dependency analysis (default = 1000)"));
92 // Limit on the number of memdep results to process.
93 static const unsigned int NumResultsLimit = 100;
95 /// This is a helper function that removes Val from 'Inst's set in ReverseMap.
97 /// If the set becomes empty, remove Inst's entry.
98 template <typename KeyTy>
100 RemoveFromReverseMap(DenseMap<Instruction *, SmallPtrSet<KeyTy, 4>> &ReverseMap,
101 Instruction *Inst, KeyTy Val) {
102 typename DenseMap<Instruction *, SmallPtrSet<KeyTy, 4>>::iterator InstIt =
103 ReverseMap.find(Inst);
104 assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
105 bool Found = InstIt->second.erase(Val);
106 assert(Found && "Invalid reverse map!");
108 if (InstIt->second.empty())
109 ReverseMap.erase(InstIt);
112 /// If the given instruction references a specific memory location, fill in Loc
113 /// with the details, otherwise set Loc.Ptr to null.
115 /// Returns a ModRefInfo value describing the general behavior of the
117 static ModRefInfo GetLocation(const Instruction *Inst, MemoryLocation &Loc,
118 const TargetLibraryInfo &TLI) {
119 if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
120 if (LI->isUnordered()) {
121 Loc = MemoryLocation::get(LI);
122 return ModRefInfo::Ref;
124 if (LI->getOrdering() == AtomicOrdering::Monotonic) {
125 Loc = MemoryLocation::get(LI);
126 return ModRefInfo::ModRef;
128 Loc = MemoryLocation();
129 return ModRefInfo::ModRef;
132 if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
133 if (SI->isUnordered()) {
134 Loc = MemoryLocation::get(SI);
135 return ModRefInfo::Mod;
137 if (SI->getOrdering() == AtomicOrdering::Monotonic) {
138 Loc = MemoryLocation::get(SI);
139 return ModRefInfo::ModRef;
141 Loc = MemoryLocation();
142 return ModRefInfo::ModRef;
145 if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
146 Loc = MemoryLocation::get(V);
147 return ModRefInfo::ModRef;
150 if (const CallInst *CI = isFreeCall(Inst, &TLI)) {
151 // calls to free() deallocate the entire structure
152 Loc = MemoryLocation(CI->getArgOperand(0));
153 return ModRefInfo::Mod;
156 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
157 switch (II->getIntrinsicID()) {
158 case Intrinsic::lifetime_start:
159 case Intrinsic::lifetime_end:
160 case Intrinsic::invariant_start:
161 Loc = MemoryLocation::getForArgument(II, 1, TLI);
162 // These intrinsics don't really modify the memory, but returning Mod
163 // will allow them to be handled conservatively.
164 return ModRefInfo::Mod;
165 case Intrinsic::invariant_end:
166 Loc = MemoryLocation::getForArgument(II, 2, TLI);
167 // These intrinsics don't really modify the memory, but returning Mod
168 // will allow them to be handled conservatively.
169 return ModRefInfo::Mod;
175 // Otherwise, just do the coarse-grained thing that always works.
176 if (Inst->mayWriteToMemory())
177 return ModRefInfo::ModRef;
178 if (Inst->mayReadFromMemory())
179 return ModRefInfo::Ref;
180 return ModRefInfo::NoModRef;
183 /// Private helper for finding the local dependencies of a call site.
184 MemDepResult MemoryDependenceResults::getCallDependencyFrom(
185 CallBase *Call, bool isReadOnlyCall, BasicBlock::iterator ScanIt,
187 unsigned Limit = getDefaultBlockScanLimit();
189 // Walk backwards through the block, looking for dependencies.
190 while (ScanIt != BB->begin()) {
191 Instruction *Inst = &*--ScanIt;
192 // Debug intrinsics don't cause dependences and should not affect Limit
193 if (isa<DbgInfoIntrinsic>(Inst))
196 // Limit the amount of scanning we do so we don't end up with quadratic
197 // running time on extreme testcases.
200 return MemDepResult::getUnknown();
202 // If this inst is a memory op, get the pointer it accessed
204 ModRefInfo MR = GetLocation(Inst, Loc, TLI);
206 // A simple instruction.
207 if (isModOrRefSet(AA.getModRefInfo(Call, Loc)))
208 return MemDepResult::getClobber(Inst);
212 if (auto *CallB = dyn_cast<CallBase>(Inst)) {
213 // If these two calls do not interfere, look past it.
214 if (isNoModRef(AA.getModRefInfo(Call, CallB))) {
215 // If the two calls are the same, return Inst as a Def, so that
216 // Call can be found redundant and eliminated.
217 if (isReadOnlyCall && !isModSet(MR) &&
218 Call->isIdenticalToWhenDefined(CallB))
219 return MemDepResult::getDef(Inst);
221 // Otherwise if the two calls don't interact (e.g. CallB is readnone)
225 return MemDepResult::getClobber(Inst);
228 // If we could not obtain a pointer for the instruction and the instruction
229 // touches memory then assume that this is a dependency.
230 if (isModOrRefSet(MR))
231 return MemDepResult::getClobber(Inst);
234 // No dependence found. If this is the entry block of the function, it is
235 // unknown, otherwise it is non-local.
236 if (BB != &BB->getParent()->getEntryBlock())
237 return MemDepResult::getNonLocal();
238 return MemDepResult::getNonFuncLocal();
241 unsigned MemoryDependenceResults::getLoadLoadClobberFullWidthSize(
242 const Value *MemLocBase, int64_t MemLocOffs, unsigned MemLocSize,
243 const LoadInst *LI) {
244 // We can only extend simple integer loads.
245 if (!isa<IntegerType>(LI->getType()) || !LI->isSimple())
248 // Load widening is hostile to ThreadSanitizer: it may cause false positives
249 // or make the reports more cryptic (access sizes are wrong).
250 if (LI->getParent()->getParent()->hasFnAttribute(Attribute::SanitizeThread))
253 const DataLayout &DL = LI->getModule()->getDataLayout();
255 // Get the base of this load.
257 const Value *LIBase =
258 GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, DL);
260 // If the two pointers are not based on the same pointer, we can't tell that
262 if (LIBase != MemLocBase)
265 // Okay, the two values are based on the same pointer, but returned as
266 // no-alias. This happens when we have things like two byte loads at "P+1"
267 // and "P+3". Check to see if increasing the size of the "LI" load up to its
268 // alignment (or the largest native integer type) will allow us to load all
269 // the bits required by MemLoc.
271 // If MemLoc is before LI, then no widening of LI will help us out.
272 if (MemLocOffs < LIOffs)
275 // Get the alignment of the load in bytes. We assume that it is safe to load
276 // any legal integer up to this size without a problem. For example, if we're
277 // looking at an i8 load on x86-32 that is known 1024 byte aligned, we can
278 // widen it up to an i32 load. If it is known 2-byte aligned, we can widen it
280 unsigned LoadAlign = LI->getAlignment();
282 int64_t MemLocEnd = MemLocOffs + MemLocSize;
284 // If no amount of rounding up will let MemLoc fit into LI, then bail out.
285 if (LIOffs + LoadAlign < MemLocEnd)
288 // This is the size of the load to try. Start with the next larger power of
290 unsigned NewLoadByteSize = LI->getType()->getPrimitiveSizeInBits() / 8U;
291 NewLoadByteSize = NextPowerOf2(NewLoadByteSize);
294 // If this load size is bigger than our known alignment or would not fit
295 // into a native integer register, then we fail.
296 if (NewLoadByteSize > LoadAlign ||
297 !DL.fitsInLegalInteger(NewLoadByteSize * 8))
300 if (LIOffs + NewLoadByteSize > MemLocEnd &&
301 (LI->getParent()->getParent()->hasFnAttribute(
302 Attribute::SanitizeAddress) ||
303 LI->getParent()->getParent()->hasFnAttribute(
304 Attribute::SanitizeHWAddress)))
305 // We will be reading past the location accessed by the original program.
306 // While this is safe in a regular build, Address Safety analysis tools
307 // may start reporting false warnings. So, don't do widening.
310 // If a load of this width would include all of MemLoc, then we succeed.
311 if (LIOffs + NewLoadByteSize >= MemLocEnd)
312 return NewLoadByteSize;
314 NewLoadByteSize <<= 1;
318 static bool isVolatile(Instruction *Inst) {
319 if (auto *LI = dyn_cast<LoadInst>(Inst))
320 return LI->isVolatile();
321 if (auto *SI = dyn_cast<StoreInst>(Inst))
322 return SI->isVolatile();
323 if (auto *AI = dyn_cast<AtomicCmpXchgInst>(Inst))
324 return AI->isVolatile();
328 MemDepResult MemoryDependenceResults::getPointerDependencyFrom(
329 const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
330 BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
331 OrderedBasicBlock *OBB) {
332 MemDepResult InvariantGroupDependency = MemDepResult::getUnknown();
333 if (QueryInst != nullptr) {
334 if (auto *LI = dyn_cast<LoadInst>(QueryInst)) {
335 InvariantGroupDependency = getInvariantGroupPointerDependency(LI, BB);
337 if (InvariantGroupDependency.isDef())
338 return InvariantGroupDependency;
341 MemDepResult SimpleDep = getSimplePointerDependencyFrom(
342 MemLoc, isLoad, ScanIt, BB, QueryInst, Limit, OBB);
343 if (SimpleDep.isDef())
345 // Non-local invariant group dependency indicates there is non local Def
346 // (it only returns nonLocal if it finds nonLocal def), which is better than
347 // local clobber and everything else.
348 if (InvariantGroupDependency.isNonLocal())
349 return InvariantGroupDependency;
351 assert(InvariantGroupDependency.isUnknown() &&
352 "InvariantGroupDependency should be only unknown at this point");
357 MemoryDependenceResults::getInvariantGroupPointerDependency(LoadInst *LI,
360 if (!LI->hasMetadata(LLVMContext::MD_invariant_group))
361 return MemDepResult::getUnknown();
363 // Take the ptr operand after all casts and geps 0. This way we can search
364 // cast graph down only.
365 Value *LoadOperand = LI->getPointerOperand()->stripPointerCasts();
367 // It's is not safe to walk the use list of global value, because function
368 // passes aren't allowed to look outside their functions.
369 // FIXME: this could be fixed by filtering instructions from outside
370 // of current function.
371 if (isa<GlobalValue>(LoadOperand))
372 return MemDepResult::getUnknown();
374 // Queue to process all pointers that are equivalent to load operand.
375 SmallVector<const Value *, 8> LoadOperandsQueue;
376 LoadOperandsQueue.push_back(LoadOperand);
378 Instruction *ClosestDependency = nullptr;
379 // Order of instructions in uses list is unpredictible. In order to always
380 // get the same result, we will look for the closest dominance.
381 auto GetClosestDependency = [this](Instruction *Best, Instruction *Other) {
382 assert(Other && "Must call it with not null instruction");
383 if (Best == nullptr || DT.dominates(Best, Other))
388 // FIXME: This loop is O(N^2) because dominates can be O(n) and in worst case
389 // we will see all the instructions. This should be fixed in MSSA.
390 while (!LoadOperandsQueue.empty()) {
391 const Value *Ptr = LoadOperandsQueue.pop_back_val();
392 assert(Ptr && !isa<GlobalValue>(Ptr) &&
393 "Null or GlobalValue should not be inserted");
395 for (const Use &Us : Ptr->uses()) {
396 auto *U = dyn_cast<Instruction>(Us.getUser());
397 if (!U || U == LI || !DT.dominates(U, LI))
400 // Bitcast or gep with zeros are using Ptr. Add to queue to check it's
401 // users. U = bitcast Ptr
402 if (isa<BitCastInst>(U)) {
403 LoadOperandsQueue.push_back(U);
406 // Gep with zeros is equivalent to bitcast.
407 // FIXME: we are not sure if some bitcast should be canonicalized to gep 0
408 // or gep 0 to bitcast because of SROA, so there are 2 forms. When
409 // typeless pointers will be ready then both cases will be gone
410 // (and this BFS also won't be needed).
411 if (auto *GEP = dyn_cast<GetElementPtrInst>(U))
412 if (GEP->hasAllZeroIndices()) {
413 LoadOperandsQueue.push_back(U);
417 // If we hit load/store with the same invariant.group metadata (and the
418 // same pointer operand) we can assume that value pointed by pointer
419 // operand didn't change.
420 if ((isa<LoadInst>(U) || isa<StoreInst>(U)) &&
421 U->hasMetadata(LLVMContext::MD_invariant_group))
422 ClosestDependency = GetClosestDependency(ClosestDependency, U);
426 if (!ClosestDependency)
427 return MemDepResult::getUnknown();
428 if (ClosestDependency->getParent() == BB)
429 return MemDepResult::getDef(ClosestDependency);
430 // Def(U) can't be returned here because it is non-local. If local
431 // dependency won't be found then return nonLocal counting that the
432 // user will call getNonLocalPointerDependency, which will return cached
434 NonLocalDefsCache.try_emplace(
435 LI, NonLocalDepResult(ClosestDependency->getParent(),
436 MemDepResult::getDef(ClosestDependency), nullptr));
437 ReverseNonLocalDefsCache[ClosestDependency].insert(LI);
438 return MemDepResult::getNonLocal();
441 MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
442 const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
443 BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
444 OrderedBasicBlock *OBB) {
445 bool isInvariantLoad = false;
447 unsigned DefaultLimit = getDefaultBlockScanLimit();
449 Limit = &DefaultLimit;
451 // We must be careful with atomic accesses, as they may allow another thread
452 // to touch this location, clobbering it. We are conservative: if the
453 // QueryInst is not a simple (non-atomic) memory access, we automatically
454 // return getClobber.
455 // If it is simple, we know based on the results of
456 // "Compiler testing via a theory of sound optimisations in the C11/C++11
457 // memory model" in PLDI 2013, that a non-atomic location can only be
458 // clobbered between a pair of a release and an acquire action, with no
459 // access to the location in between.
460 // Here is an example for giving the general intuition behind this rule.
461 // In the following code:
463 // release action; [1]
464 // acquire action; [4]
466 // It is unsafe to replace %val by 0 because another thread may be running:
467 // acquire action; [2]
469 // release action; [3]
470 // with synchronization from 1 to 2 and from 3 to 4, resulting in %val
471 // being 42. A key property of this program however is that if either
472 // 1 or 4 were missing, there would be a race between the store of 42
473 // either the store of 0 or the load (making the whole program racy).
474 // The paper mentioned above shows that the same property is respected
475 // by every program that can detect any optimization of that kind: either
476 // it is racy (undefined) or there is a release followed by an acquire
477 // between the pair of accesses under consideration.
479 // If the load is invariant, we "know" that it doesn't alias *any* write. We
480 // do want to respect mustalias results since defs are useful for value
481 // forwarding, but any mayalias write can be assumed to be noalias.
482 // Arguably, this logic should be pushed inside AliasAnalysis itself.
483 if (isLoad && QueryInst) {
484 LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
485 if (LI && LI->hasMetadata(LLVMContext::MD_invariant_load))
486 isInvariantLoad = true;
489 const DataLayout &DL = BB->getModule()->getDataLayout();
491 // If the caller did not provide an ordered basic block,
492 // create one to lazily compute and cache instruction
493 // positions inside a BB. This is used to provide fast queries for relative
494 // position between two instructions in a BB and can be used by
495 // AliasAnalysis::callCapturesBefore.
496 OrderedBasicBlock OBBTmp(BB);
500 // Return "true" if and only if the instruction I is either a non-simple
501 // load or a non-simple store.
502 auto isNonSimpleLoadOrStore = [](Instruction *I) -> bool {
503 if (auto *LI = dyn_cast<LoadInst>(I))
504 return !LI->isSimple();
505 if (auto *SI = dyn_cast<StoreInst>(I))
506 return !SI->isSimple();
510 // Return "true" if I is not a load and not a store, but it does access
512 auto isOtherMemAccess = [](Instruction *I) -> bool {
513 return !isa<LoadInst>(I) && !isa<StoreInst>(I) && I->mayReadOrWriteMemory();
516 // Walk backwards through the basic block, looking for dependencies.
517 while (ScanIt != BB->begin()) {
518 Instruction *Inst = &*--ScanIt;
520 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
521 // Debug intrinsics don't (and can't) cause dependencies.
522 if (isa<DbgInfoIntrinsic>(II))
525 // Limit the amount of scanning we do so we don't end up with quadratic
526 // running time on extreme testcases.
529 return MemDepResult::getUnknown();
531 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
532 // If we reach a lifetime begin or end marker, then the query ends here
533 // because the value is undefined.
534 if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
535 // FIXME: This only considers queries directly on the invariant-tagged
536 // pointer, not on query pointers that are indexed off of them. It'd
537 // be nice to handle that at some point (the right approach is to use
538 // GetPointerBaseWithConstantOffset).
539 if (AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), MemLoc))
540 return MemDepResult::getDef(II);
545 // Values depend on loads if the pointers are must aliased. This means
546 // that a load depends on another must aliased load from the same value.
547 // One exception is atomic loads: a value can depend on an atomic load that
548 // it does not alias with when this atomic load indicates that another
549 // thread may be accessing the location.
550 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
551 // While volatile access cannot be eliminated, they do not have to clobber
552 // non-aliasing locations, as normal accesses, for example, can be safely
553 // reordered with volatile accesses.
554 if (LI->isVolatile()) {
556 // Original QueryInst *may* be volatile
557 return MemDepResult::getClobber(LI);
558 if (isVolatile(QueryInst))
559 // Ordering required if QueryInst is itself volatile
560 return MemDepResult::getClobber(LI);
561 // Otherwise, volatile doesn't imply any special ordering
564 // Atomic loads have complications involved.
565 // A Monotonic (or higher) load is OK if the query inst is itself not
567 // FIXME: This is overly conservative.
568 if (LI->isAtomic() && isStrongerThanUnordered(LI->getOrdering())) {
569 if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
570 isOtherMemAccess(QueryInst))
571 return MemDepResult::getClobber(LI);
572 if (LI->getOrdering() != AtomicOrdering::Monotonic)
573 return MemDepResult::getClobber(LI);
576 MemoryLocation LoadLoc = MemoryLocation::get(LI);
578 // If we found a pointer, check if it could be the same as our pointer.
579 AliasResult R = AA.alias(LoadLoc, MemLoc);
585 // Must aliased loads are defs of each other.
587 return MemDepResult::getDef(Inst);
589 #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads
590 // in terms of clobbering loads, but since it does this by looking
591 // at the clobbering load directly, it doesn't know about any
592 // phi translation that may have happened along the way.
594 // If we have a partial alias, then return this as a clobber for the
596 if (R == PartialAlias)
597 return MemDepResult::getClobber(Inst);
600 // Random may-alias loads don't depend on each other without a
605 // Stores don't depend on other no-aliased accesses.
609 // Stores don't alias loads from read-only memory.
610 if (AA.pointsToConstantMemory(LoadLoc))
613 // Stores depend on may/must aliased loads.
614 return MemDepResult::getDef(Inst);
617 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
618 // Atomic stores have complications involved.
619 // A Monotonic store is OK if the query inst is itself not atomic.
620 // FIXME: This is overly conservative.
621 if (!SI->isUnordered() && SI->isAtomic()) {
622 if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
623 isOtherMemAccess(QueryInst))
624 return MemDepResult::getClobber(SI);
625 if (SI->getOrdering() != AtomicOrdering::Monotonic)
626 return MemDepResult::getClobber(SI);
629 // FIXME: this is overly conservative.
630 // While volatile access cannot be eliminated, they do not have to clobber
631 // non-aliasing locations, as normal accesses can for example be reordered
632 // with volatile accesses.
633 if (SI->isVolatile())
634 if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
635 isOtherMemAccess(QueryInst))
636 return MemDepResult::getClobber(SI);
638 // If alias analysis can tell that this store is guaranteed to not modify
639 // the query pointer, ignore it. Use getModRefInfo to handle cases where
640 // the query pointer points to constant memory etc.
641 if (!isModOrRefSet(AA.getModRefInfo(SI, MemLoc)))
644 // Ok, this store might clobber the query pointer. Check to see if it is
645 // a must alias: in this case, we want to return this as a def.
646 // FIXME: Use ModRefInfo::Must bit from getModRefInfo call above.
647 MemoryLocation StoreLoc = MemoryLocation::get(SI);
649 // If we found a pointer, check if it could be the same as our pointer.
650 AliasResult R = AA.alias(StoreLoc, MemLoc);
655 return MemDepResult::getDef(Inst);
658 return MemDepResult::getClobber(Inst);
661 // If this is an allocation, and if we know that the accessed pointer is to
662 // the allocation, return Def. This means that there is no dependence and
663 // the access can be optimized based on that. For example, a load could
664 // turn into undef. Note that we can bypass the allocation itself when
665 // looking for a clobber in many cases; that's an alias property and is
666 // handled by BasicAA.
667 if (isa<AllocaInst>(Inst) || isNoAliasFn(Inst, &TLI)) {
668 const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, DL);
669 if (AccessPtr == Inst || AA.isMustAlias(Inst, AccessPtr))
670 return MemDepResult::getDef(Inst);
676 // A release fence requires that all stores complete before it, but does
677 // not prevent the reordering of following loads or stores 'before' the
678 // fence. As a result, we look past it when finding a dependency for
679 // loads. DSE uses this to find preceding stores to delete and thus we
680 // can't bypass the fence if the query instruction is a store.
681 if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
682 if (isLoad && FI->getOrdering() == AtomicOrdering::Release)
685 // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
686 ModRefInfo MR = AA.getModRefInfo(Inst, MemLoc);
687 // If necessary, perform additional analysis.
688 if (isModAndRefSet(MR))
689 MR = AA.callCapturesBefore(Inst, MemLoc, &DT, OBB);
690 switch (clearMust(MR)) {
691 case ModRefInfo::NoModRef:
692 // If the call has no effect on the queried pointer, just ignore it.
694 case ModRefInfo::Mod:
695 return MemDepResult::getClobber(Inst);
696 case ModRefInfo::Ref:
697 // If the call is known to never store to the pointer, and if this is a
698 // load query, we can safely ignore it (scan past it).
703 // Otherwise, there is a potential dependence. Return a clobber.
704 return MemDepResult::getClobber(Inst);
708 // No dependence found. If this is the entry block of the function, it is
709 // unknown, otherwise it is non-local.
710 if (BB != &BB->getParent()->getEntryBlock())
711 return MemDepResult::getNonLocal();
712 return MemDepResult::getNonFuncLocal();
715 MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst,
716 OrderedBasicBlock *OBB) {
717 Instruction *ScanPos = QueryInst;
719 // Check for a cached result
720 MemDepResult &LocalCache = LocalDeps[QueryInst];
722 // If the cached entry is non-dirty, just return it. Note that this depends
723 // on MemDepResult's default constructing to 'dirty'.
724 if (!LocalCache.isDirty())
727 // Otherwise, if we have a dirty entry, we know we can start the scan at that
728 // instruction, which may save us some work.
729 if (Instruction *Inst = LocalCache.getInst()) {
732 RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
735 BasicBlock *QueryParent = QueryInst->getParent();
738 if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
739 // No dependence found. If this is the entry block of the function, it is
740 // unknown, otherwise it is non-local.
741 if (QueryParent != &QueryParent->getParent()->getEntryBlock())
742 LocalCache = MemDepResult::getNonLocal();
744 LocalCache = MemDepResult::getNonFuncLocal();
746 MemoryLocation MemLoc;
747 ModRefInfo MR = GetLocation(QueryInst, MemLoc, TLI);
749 // If we can do a pointer scan, make it happen.
750 bool isLoad = !isModSet(MR);
751 if (auto *II = dyn_cast<IntrinsicInst>(QueryInst))
752 isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
755 getPointerDependencyFrom(MemLoc, isLoad, ScanPos->getIterator(),
756 QueryParent, QueryInst, nullptr, OBB);
757 } else if (auto *QueryCall = dyn_cast<CallBase>(QueryInst)) {
758 bool isReadOnly = AA.onlyReadsMemory(QueryCall);
759 LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,
760 ScanPos->getIterator(), QueryParent);
762 // Non-memory instruction.
763 LocalCache = MemDepResult::getUnknown();
766 // Remember the result!
767 if (Instruction *I = LocalCache.getInst())
768 ReverseLocalDeps[I].insert(QueryInst);
774 /// This method is used when -debug is specified to verify that cache arrays
775 /// are properly kept sorted.
776 static void AssertSorted(MemoryDependenceResults::NonLocalDepInfo &Cache,
779 Count = Cache.size();
780 assert(std::is_sorted(Cache.begin(), Cache.begin() + Count) &&
781 "Cache isn't sorted!");
785 const MemoryDependenceResults::NonLocalDepInfo &
786 MemoryDependenceResults::getNonLocalCallDependency(CallBase *QueryCall) {
787 assert(getDependency(QueryCall).isNonLocal() &&
788 "getNonLocalCallDependency should only be used on calls with "
790 PerInstNLInfo &CacheP = NonLocalDeps[QueryCall];
791 NonLocalDepInfo &Cache = CacheP.first;
793 // This is the set of blocks that need to be recomputed. In the cached case,
794 // this can happen due to instructions being deleted etc. In the uncached
795 // case, this starts out as the set of predecessors we care about.
796 SmallVector<BasicBlock *, 32> DirtyBlocks;
798 if (!Cache.empty()) {
799 // Okay, we have a cache entry. If we know it is not dirty, just return it
800 // with no computation.
801 if (!CacheP.second) {
806 // If we already have a partially computed set of results, scan them to
807 // determine what is dirty, seeding our initial DirtyBlocks worklist.
808 for (auto &Entry : Cache)
809 if (Entry.getResult().isDirty())
810 DirtyBlocks.push_back(Entry.getBB());
812 // Sort the cache so that we can do fast binary search lookups below.
815 ++NumCacheDirtyNonLocal;
816 // cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
817 // << Cache.size() << " cached: " << *QueryInst;
819 // Seed DirtyBlocks with each of the preds of QueryInst's block.
820 BasicBlock *QueryBB = QueryCall->getParent();
821 for (BasicBlock *Pred : PredCache.get(QueryBB))
822 DirtyBlocks.push_back(Pred);
823 ++NumUncacheNonLocal;
826 // isReadonlyCall - If this is a read-only call, we can be more aggressive.
827 bool isReadonlyCall = AA.onlyReadsMemory(QueryCall);
829 SmallPtrSet<BasicBlock *, 32> Visited;
831 unsigned NumSortedEntries = Cache.size();
832 LLVM_DEBUG(AssertSorted(Cache));
834 // Iterate while we still have blocks to update.
835 while (!DirtyBlocks.empty()) {
836 BasicBlock *DirtyBB = DirtyBlocks.back();
837 DirtyBlocks.pop_back();
839 // Already processed this block?
840 if (!Visited.insert(DirtyBB).second)
843 // Do a binary search to see if we already have an entry for this block in
844 // the cache set. If so, find it.
845 LLVM_DEBUG(AssertSorted(Cache, NumSortedEntries));
846 NonLocalDepInfo::iterator Entry =
847 std::upper_bound(Cache.begin(), Cache.begin() + NumSortedEntries,
848 NonLocalDepEntry(DirtyBB));
849 if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB)
852 NonLocalDepEntry *ExistingResult = nullptr;
853 if (Entry != Cache.begin() + NumSortedEntries &&
854 Entry->getBB() == DirtyBB) {
855 // If we already have an entry, and if it isn't already dirty, the block
857 if (!Entry->getResult().isDirty())
860 // Otherwise, remember this slot so we can update the value.
861 ExistingResult = &*Entry;
864 // If the dirty entry has a pointer, start scanning from it so we don't have
865 // to rescan the entire block.
866 BasicBlock::iterator ScanPos = DirtyBB->end();
867 if (ExistingResult) {
868 if (Instruction *Inst = ExistingResult->getResult().getInst()) {
869 ScanPos = Inst->getIterator();
870 // We're removing QueryInst's use of Inst.
871 RemoveFromReverseMap<Instruction *>(ReverseNonLocalDeps, Inst,
876 // Find out if this block has a local dependency for QueryInst.
879 if (ScanPos != DirtyBB->begin()) {
880 Dep = getCallDependencyFrom(QueryCall, isReadonlyCall, ScanPos, DirtyBB);
881 } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) {
882 // No dependence found. If this is the entry block of the function, it is
883 // a clobber, otherwise it is unknown.
884 Dep = MemDepResult::getNonLocal();
886 Dep = MemDepResult::getNonFuncLocal();
889 // If we had a dirty entry for the block, update it. Otherwise, just add
892 ExistingResult->setResult(Dep);
894 Cache.push_back(NonLocalDepEntry(DirtyBB, Dep));
896 // If the block has a dependency (i.e. it isn't completely transparent to
897 // the value), remember the association!
898 if (!Dep.isNonLocal()) {
899 // Keep the ReverseNonLocalDeps map up to date so we can efficiently
900 // update this when we remove instructions.
901 if (Instruction *Inst = Dep.getInst())
902 ReverseNonLocalDeps[Inst].insert(QueryCall);
905 // If the block *is* completely transparent to the load, we need to check
906 // the predecessors of this block. Add them to our worklist.
907 for (BasicBlock *Pred : PredCache.get(DirtyBB))
908 DirtyBlocks.push_back(Pred);
915 void MemoryDependenceResults::getNonLocalPointerDependency(
916 Instruction *QueryInst, SmallVectorImpl<NonLocalDepResult> &Result) {
917 const MemoryLocation Loc = MemoryLocation::get(QueryInst);
918 bool isLoad = isa<LoadInst>(QueryInst);
919 BasicBlock *FromBB = QueryInst->getParent();
922 assert(Loc.Ptr->getType()->isPointerTy() &&
923 "Can't get pointer deps of a non-pointer!");
926 // Check if there is cached Def with invariant.group.
927 auto NonLocalDefIt = NonLocalDefsCache.find(QueryInst);
928 if (NonLocalDefIt != NonLocalDefsCache.end()) {
929 Result.push_back(NonLocalDefIt->second);
930 ReverseNonLocalDefsCache[NonLocalDefIt->second.getResult().getInst()]
932 NonLocalDefsCache.erase(NonLocalDefIt);
936 // This routine does not expect to deal with volatile instructions.
937 // Doing so would require piping through the QueryInst all the way through.
938 // TODO: volatiles can't be elided, but they can be reordered with other
939 // non-volatile accesses.
941 // We currently give up on any instruction which is ordered, but we do handle
942 // atomic instructions which are unordered.
943 // TODO: Handle ordered instructions
944 auto isOrdered = [](Instruction *Inst) {
945 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
946 return !LI->isUnordered();
947 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
948 return !SI->isUnordered();
952 if (isVolatile(QueryInst) || isOrdered(QueryInst)) {
953 Result.push_back(NonLocalDepResult(FromBB, MemDepResult::getUnknown(),
954 const_cast<Value *>(Loc.Ptr)));
957 const DataLayout &DL = FromBB->getModule()->getDataLayout();
958 PHITransAddr Address(const_cast<Value *>(Loc.Ptr), DL, &AC);
960 // This is the set of blocks we've inspected, and the pointer we consider in
961 // each block. Because of critical edges, we currently bail out if querying
962 // a block with multiple different pointers. This can happen during PHI
964 DenseMap<BasicBlock *, Value *> Visited;
965 if (getNonLocalPointerDepFromBB(QueryInst, Address, Loc, isLoad, FromBB,
966 Result, Visited, true))
969 Result.push_back(NonLocalDepResult(FromBB, MemDepResult::getUnknown(),
970 const_cast<Value *>(Loc.Ptr)));
973 /// Compute the memdep value for BB with Pointer/PointeeSize using either
974 /// cached information in Cache or by doing a lookup (which may use dirty cache
975 /// info if available).
977 /// If we do a lookup, add the result to the cache.
978 MemDepResult MemoryDependenceResults::GetNonLocalInfoForBlock(
979 Instruction *QueryInst, const MemoryLocation &Loc, bool isLoad,
980 BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
982 // Do a binary search to see if we already have an entry for this block in
983 // the cache set. If so, find it.
984 NonLocalDepInfo::iterator Entry = std::upper_bound(
985 Cache->begin(), Cache->begin() + NumSortedEntries, NonLocalDepEntry(BB));
986 if (Entry != Cache->begin() && (Entry - 1)->getBB() == BB)
989 NonLocalDepEntry *ExistingResult = nullptr;
990 if (Entry != Cache->begin() + NumSortedEntries && Entry->getBB() == BB)
991 ExistingResult = &*Entry;
993 // If we have a cached entry, and it is non-dirty, use it as the value for
995 if (ExistingResult && !ExistingResult->getResult().isDirty()) {
996 ++NumCacheNonLocalPtr;
997 return ExistingResult->getResult();
1000 // Otherwise, we have to scan for the value. If we have a dirty cache
1001 // entry, start scanning from its position, otherwise we scan from the end
1003 BasicBlock::iterator ScanPos = BB->end();
1004 if (ExistingResult && ExistingResult->getResult().getInst()) {
1005 assert(ExistingResult->getResult().getInst()->getParent() == BB &&
1006 "Instruction invalidated?");
1007 ++NumCacheDirtyNonLocalPtr;
1008 ScanPos = ExistingResult->getResult().getInst()->getIterator();
1010 // Eliminating the dirty entry from 'Cache', so update the reverse info.
1011 ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
1012 RemoveFromReverseMap(ReverseNonLocalPtrDeps, &*ScanPos, CacheKey);
1014 ++NumUncacheNonLocalPtr;
1017 // Scan the block for the dependency.
1019 getPointerDependencyFrom(Loc, isLoad, ScanPos, BB, QueryInst);
1021 // If we had a dirty entry for the block, update it. Otherwise, just add
1024 ExistingResult->setResult(Dep);
1026 Cache->push_back(NonLocalDepEntry(BB, Dep));
1028 // If the block has a dependency (i.e. it isn't completely transparent to
1029 // the value), remember the reverse association because we just added it
1031 if (!Dep.isDef() && !Dep.isClobber())
1034 // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
1035 // update MemDep when we remove instructions.
1036 Instruction *Inst = Dep.getInst();
1037 assert(Inst && "Didn't depend on anything?");
1038 ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
1039 ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
1043 /// Sort the NonLocalDepInfo cache, given a certain number of elements in the
1044 /// array that are already properly ordered.
1046 /// This is optimized for the case when only a few entries are added.
1048 SortNonLocalDepInfoCache(MemoryDependenceResults::NonLocalDepInfo &Cache,
1049 unsigned NumSortedEntries) {
1050 switch (Cache.size() - NumSortedEntries) {
1052 // done, no new entries.
1055 // Two new entries, insert the last one into place.
1056 NonLocalDepEntry Val = Cache.back();
1058 MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
1059 std::upper_bound(Cache.begin(), Cache.end() - 1, Val);
1060 Cache.insert(Entry, Val);
1064 // One new entry, Just insert the new value at the appropriate position.
1065 if (Cache.size() != 1) {
1066 NonLocalDepEntry Val = Cache.back();
1068 MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
1069 std::upper_bound(Cache.begin(), Cache.end(), Val);
1070 Cache.insert(Entry, Val);
1074 // Added many values, do a full scale sort.
1080 /// Perform a dependency query based on pointer/pointeesize starting at the end
1083 /// Add any clobber/def results to the results vector and keep track of which
1084 /// blocks are visited in 'Visited'.
1086 /// This has special behavior for the first block queries (when SkipFirstBlock
1087 /// is true). In this special case, it ignores the contents of the specified
1088 /// block and starts returning dependence info for its predecessors.
1090 /// This function returns true on success, or false to indicate that it could
1091 /// not compute dependence information for some reason. This should be treated
1092 /// as a clobber dependence on the first instruction in the predecessor block.
1093 bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
1094 Instruction *QueryInst, const PHITransAddr &Pointer,
1095 const MemoryLocation &Loc, bool isLoad, BasicBlock *StartBB,
1096 SmallVectorImpl<NonLocalDepResult> &Result,
1097 DenseMap<BasicBlock *, Value *> &Visited, bool SkipFirstBlock) {
1098 // Look up the cached info for Pointer.
1099 ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
1101 // Set up a temporary NLPI value. If the map doesn't yet have an entry for
1102 // CacheKey, this value will be inserted as the associated value. Otherwise,
1103 // it'll be ignored, and we'll have to check to see if the cached size and
1104 // aa tags are consistent with the current query.
1105 NonLocalPointerInfo InitialNLPI;
1106 InitialNLPI.Size = Loc.Size;
1107 InitialNLPI.AATags = Loc.AATags;
1109 // Get the NLPI for CacheKey, inserting one into the map if it doesn't
1110 // already have one.
1111 std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
1112 NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
1113 NonLocalPointerInfo *CacheInfo = &Pair.first->second;
1115 // If we already have a cache entry for this CacheKey, we may need to do some
1116 // work to reconcile the cache entry and the current query.
1118 if (CacheInfo->Size != Loc.Size) {
1119 bool ThrowOutEverything;
1120 if (CacheInfo->Size.hasValue() && Loc.Size.hasValue()) {
1121 // FIXME: We may be able to do better in the face of results with mixed
1122 // precision. We don't appear to get them in practice, though, so just
1124 ThrowOutEverything =
1125 CacheInfo->Size.isPrecise() != Loc.Size.isPrecise() ||
1126 CacheInfo->Size.getValue() < Loc.Size.getValue();
1128 // For our purposes, unknown size > all others.
1129 ThrowOutEverything = !Loc.Size.hasValue();
1132 if (ThrowOutEverything) {
1133 // The query's Size is greater than the cached one. Throw out the
1134 // cached data and proceed with the query at the greater size.
1135 CacheInfo->Pair = BBSkipFirstBlockPair();
1136 CacheInfo->Size = Loc.Size;
1137 for (auto &Entry : CacheInfo->NonLocalDeps)
1138 if (Instruction *Inst = Entry.getResult().getInst())
1139 RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
1140 CacheInfo->NonLocalDeps.clear();
1142 // This query's Size is less than the cached one. Conservatively restart
1143 // the query using the greater size.
1144 return getNonLocalPointerDepFromBB(
1145 QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad,
1146 StartBB, Result, Visited, SkipFirstBlock);
1150 // If the query's AATags are inconsistent with the cached one,
1151 // conservatively throw out the cached data and restart the query with
1152 // no tag if needed.
1153 if (CacheInfo->AATags != Loc.AATags) {
1154 if (CacheInfo->AATags) {
1155 CacheInfo->Pair = BBSkipFirstBlockPair();
1156 CacheInfo->AATags = AAMDNodes();
1157 for (auto &Entry : CacheInfo->NonLocalDeps)
1158 if (Instruction *Inst = Entry.getResult().getInst())
1159 RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
1160 CacheInfo->NonLocalDeps.clear();
1163 return getNonLocalPointerDepFromBB(
1164 QueryInst, Pointer, Loc.getWithoutAATags(), isLoad, StartBB, Result,
1165 Visited, SkipFirstBlock);
1169 NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps;
1171 // If we have valid cached information for exactly the block we are
1172 // investigating, just return it with no recomputation.
1173 if (CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
1174 // We have a fully cached result for this query then we can just return the
1175 // cached results and populate the visited set. However, we have to verify
1176 // that we don't already have conflicting results for these blocks. Check
1177 // to ensure that if a block in the results set is in the visited set that
1178 // it was for the same pointer query.
1179 if (!Visited.empty()) {
1180 for (auto &Entry : *Cache) {
1181 DenseMap<BasicBlock *, Value *>::iterator VI =
1182 Visited.find(Entry.getBB());
1183 if (VI == Visited.end() || VI->second == Pointer.getAddr())
1186 // We have a pointer mismatch in a block. Just return false, saying
1187 // that something was clobbered in this result. We could also do a
1188 // non-fully cached query, but there is little point in doing this.
1193 Value *Addr = Pointer.getAddr();
1194 for (auto &Entry : *Cache) {
1195 Visited.insert(std::make_pair(Entry.getBB(), Addr));
1196 if (Entry.getResult().isNonLocal()) {
1200 if (DT.isReachableFromEntry(Entry.getBB())) {
1202 NonLocalDepResult(Entry.getBB(), Entry.getResult(), Addr));
1205 ++NumCacheCompleteNonLocalPtr;
1209 // Otherwise, either this is a new block, a block with an invalid cache
1210 // pointer or one that we're about to invalidate by putting more info into it
1211 // than its valid cache info. If empty, the result will be valid cache info,
1212 // otherwise it isn't.
1214 CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
1216 CacheInfo->Pair = BBSkipFirstBlockPair();
1218 SmallVector<BasicBlock *, 32> Worklist;
1219 Worklist.push_back(StartBB);
1221 // PredList used inside loop.
1222 SmallVector<std::pair<BasicBlock *, PHITransAddr>, 16> PredList;
1224 // Keep track of the entries that we know are sorted. Previously cached
1225 // entries will all be sorted. The entries we add we only sort on demand (we
1226 // don't insert every element into its sorted position). We know that we
1227 // won't get any reuse from currently inserted values, because we don't
1228 // revisit blocks after we insert info for them.
1229 unsigned NumSortedEntries = Cache->size();
1230 unsigned WorklistEntries = BlockNumberLimit;
1231 bool GotWorklistLimit = false;
1232 LLVM_DEBUG(AssertSorted(*Cache));
1234 while (!Worklist.empty()) {
1235 BasicBlock *BB = Worklist.pop_back_val();
1237 // If we do process a large number of blocks it becomes very expensive and
1238 // likely it isn't worth worrying about
1239 if (Result.size() > NumResultsLimit) {
1241 // Sort it now (if needed) so that recursive invocations of
1242 // getNonLocalPointerDepFromBB and other routines that could reuse the
1243 // cache value will only see properly sorted cache arrays.
1244 if (Cache && NumSortedEntries != Cache->size()) {
1245 SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1247 // Since we bail out, the "Cache" set won't contain all of the
1248 // results for the query. This is ok (we can still use it to accelerate
1249 // specific block queries) but we can't do the fastpath "return all
1250 // results from the set". Clear out the indicator for this.
1251 CacheInfo->Pair = BBSkipFirstBlockPair();
1255 // Skip the first block if we have it.
1256 if (!SkipFirstBlock) {
1257 // Analyze the dependency of *Pointer in FromBB. See if we already have
1259 assert(Visited.count(BB) && "Should check 'visited' before adding to WL");
1261 // Get the dependency info for Pointer in BB. If we have cached
1262 // information, we will use it, otherwise we compute it.
1263 LLVM_DEBUG(AssertSorted(*Cache, NumSortedEntries));
1264 MemDepResult Dep = GetNonLocalInfoForBlock(QueryInst, Loc, isLoad, BB,
1265 Cache, NumSortedEntries);
1267 // If we got a Def or Clobber, add this to the list of results.
1268 if (!Dep.isNonLocal()) {
1269 if (DT.isReachableFromEntry(BB)) {
1270 Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));
1276 // If 'Pointer' is an instruction defined in this block, then we need to do
1277 // phi translation to change it into a value live in the predecessor block.
1278 // If not, we just add the predecessors to the worklist and scan them with
1279 // the same Pointer.
1280 if (!Pointer.NeedsPHITranslationFromBlock(BB)) {
1281 SkipFirstBlock = false;
1282 SmallVector<BasicBlock *, 16> NewBlocks;
1283 for (BasicBlock *Pred : PredCache.get(BB)) {
1284 // Verify that we haven't looked at this block yet.
1285 std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> InsertRes =
1286 Visited.insert(std::make_pair(Pred, Pointer.getAddr()));
1287 if (InsertRes.second) {
1288 // First time we've looked at *PI.
1289 NewBlocks.push_back(Pred);
1293 // If we have seen this block before, but it was with a different
1294 // pointer then we have a phi translation failure and we have to treat
1295 // this as a clobber.
1296 if (InsertRes.first->second != Pointer.getAddr()) {
1297 // Make sure to clean up the Visited map before continuing on to
1298 // PredTranslationFailure.
1299 for (unsigned i = 0; i < NewBlocks.size(); i++)
1300 Visited.erase(NewBlocks[i]);
1301 goto PredTranslationFailure;
1304 if (NewBlocks.size() > WorklistEntries) {
1305 // Make sure to clean up the Visited map before continuing on to
1306 // PredTranslationFailure.
1307 for (unsigned i = 0; i < NewBlocks.size(); i++)
1308 Visited.erase(NewBlocks[i]);
1309 GotWorklistLimit = true;
1310 goto PredTranslationFailure;
1312 WorklistEntries -= NewBlocks.size();
1313 Worklist.append(NewBlocks.begin(), NewBlocks.end());
1317 // We do need to do phi translation, if we know ahead of time we can't phi
1318 // translate this value, don't even try.
1319 if (!Pointer.IsPotentiallyPHITranslatable())
1320 goto PredTranslationFailure;
1322 // We may have added values to the cache list before this PHI translation.
1323 // If so, we haven't done anything to ensure that the cache remains sorted.
1324 // Sort it now (if needed) so that recursive invocations of
1325 // getNonLocalPointerDepFromBB and other routines that could reuse the cache
1326 // value will only see properly sorted cache arrays.
1327 if (Cache && NumSortedEntries != Cache->size()) {
1328 SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1329 NumSortedEntries = Cache->size();
1334 for (BasicBlock *Pred : PredCache.get(BB)) {
1335 PredList.push_back(std::make_pair(Pred, Pointer));
1337 // Get the PHI translated pointer in this predecessor. This can fail if
1338 // not translatable, in which case the getAddr() returns null.
1339 PHITransAddr &PredPointer = PredList.back().second;
1340 PredPointer.PHITranslateValue(BB, Pred, &DT, /*MustDominate=*/false);
1341 Value *PredPtrVal = PredPointer.getAddr();
1343 // Check to see if we have already visited this pred block with another
1344 // pointer. If so, we can't do this lookup. This failure can occur
1345 // with PHI translation when a critical edge exists and the PHI node in
1346 // the successor translates to a pointer value different than the
1347 // pointer the block was first analyzed with.
1348 std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> InsertRes =
1349 Visited.insert(std::make_pair(Pred, PredPtrVal));
1351 if (!InsertRes.second) {
1352 // We found the pred; take it off the list of preds to visit.
1353 PredList.pop_back();
1355 // If the predecessor was visited with PredPtr, then we already did
1356 // the analysis and can ignore it.
1357 if (InsertRes.first->second == PredPtrVal)
1360 // Otherwise, the block was previously analyzed with a different
1361 // pointer. We can't represent the result of this case, so we just
1362 // treat this as a phi translation failure.
1364 // Make sure to clean up the Visited map before continuing on to
1365 // PredTranslationFailure.
1366 for (unsigned i = 0, n = PredList.size(); i < n; ++i)
1367 Visited.erase(PredList[i].first);
1369 goto PredTranslationFailure;
1373 // Actually process results here; this need to be a separate loop to avoid
1374 // calling getNonLocalPointerDepFromBB for blocks we don't want to return
1375 // any results for. (getNonLocalPointerDepFromBB will modify our
1376 // datastructures in ways the code after the PredTranslationFailure label
1378 for (unsigned i = 0, n = PredList.size(); i < n; ++i) {
1379 BasicBlock *Pred = PredList[i].first;
1380 PHITransAddr &PredPointer = PredList[i].second;
1381 Value *PredPtrVal = PredPointer.getAddr();
1383 bool CanTranslate = true;
1384 // If PHI translation was unable to find an available pointer in this
1385 // predecessor, then we have to assume that the pointer is clobbered in
1386 // that predecessor. We can still do PRE of the load, which would insert
1387 // a computation of the pointer in this predecessor.
1389 CanTranslate = false;
1391 // FIXME: it is entirely possible that PHI translating will end up with
1392 // the same value. Consider PHI translating something like:
1393 // X = phi [x, bb1], [y, bb2]. PHI translating for bb1 doesn't *need*
1394 // to recurse here, pedantically speaking.
1396 // If getNonLocalPointerDepFromBB fails here, that means the cached
1397 // result conflicted with the Visited list; we have to conservatively
1398 // assume it is unknown, but this also does not block PRE of the load.
1399 if (!CanTranslate ||
1400 !getNonLocalPointerDepFromBB(QueryInst, PredPointer,
1401 Loc.getWithNewPtr(PredPtrVal), isLoad,
1402 Pred, Result, Visited)) {
1403 // Add the entry to the Result list.
1404 NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal);
1405 Result.push_back(Entry);
1407 // Since we had a phi translation failure, the cache for CacheKey won't
1408 // include all of the entries that we need to immediately satisfy future
1409 // queries. Mark this in NonLocalPointerDeps by setting the
1410 // BBSkipFirstBlockPair pointer to null. This requires reuse of the
1411 // cached value to do more work but not miss the phi trans failure.
1412 NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
1413 NLPI.Pair = BBSkipFirstBlockPair();
1418 // Refresh the CacheInfo/Cache pointer so that it isn't invalidated.
1419 CacheInfo = &NonLocalPointerDeps[CacheKey];
1420 Cache = &CacheInfo->NonLocalDeps;
1421 NumSortedEntries = Cache->size();
1423 // Since we did phi translation, the "Cache" set won't contain all of the
1424 // results for the query. This is ok (we can still use it to accelerate
1425 // specific block queries) but we can't do the fastpath "return all
1426 // results from the set" Clear out the indicator for this.
1427 CacheInfo->Pair = BBSkipFirstBlockPair();
1428 SkipFirstBlock = false;
1431 PredTranslationFailure:
1432 // The following code is "failure"; we can't produce a sane translation
1433 // for the given block. It assumes that we haven't modified any of
1434 // our datastructures while processing the current block.
1437 // Refresh the CacheInfo/Cache pointer if it got invalidated.
1438 CacheInfo = &NonLocalPointerDeps[CacheKey];
1439 Cache = &CacheInfo->NonLocalDeps;
1440 NumSortedEntries = Cache->size();
1443 // Since we failed phi translation, the "Cache" set won't contain all of the
1444 // results for the query. This is ok (we can still use it to accelerate
1445 // specific block queries) but we can't do the fastpath "return all
1446 // results from the set". Clear out the indicator for this.
1447 CacheInfo->Pair = BBSkipFirstBlockPair();
1449 // If *nothing* works, mark the pointer as unknown.
1451 // If this is the magic first block, return this as a clobber of the whole
1452 // incoming value. Since we can't phi translate to one of the predecessors,
1453 // we have to bail out.
1457 bool foundBlock = false;
1458 for (NonLocalDepEntry &I : llvm::reverse(*Cache)) {
1459 if (I.getBB() != BB)
1462 assert((GotWorklistLimit || I.getResult().isNonLocal() ||
1463 !DT.isReachableFromEntry(BB)) &&
1464 "Should only be here with transparent block");
1466 I.setResult(MemDepResult::getUnknown());
1468 NonLocalDepResult(I.getBB(), I.getResult(), Pointer.getAddr()));
1471 (void)foundBlock; (void)GotWorklistLimit;
1472 assert((foundBlock || GotWorklistLimit) && "Current block not in cache?");
1475 // Okay, we're done now. If we added new values to the cache, re-sort it.
1476 SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1477 LLVM_DEBUG(AssertSorted(*Cache));
1481 /// If P exists in CachedNonLocalPointerInfo or NonLocalDefsCache, remove it.
1482 void MemoryDependenceResults::RemoveCachedNonLocalPointerDependencies(
1483 ValueIsLoadPair P) {
1485 // Most of the time this cache is empty.
1486 if (!NonLocalDefsCache.empty()) {
1487 auto it = NonLocalDefsCache.find(P.getPointer());
1488 if (it != NonLocalDefsCache.end()) {
1489 RemoveFromReverseMap(ReverseNonLocalDefsCache,
1490 it->second.getResult().getInst(), P.getPointer());
1491 NonLocalDefsCache.erase(it);
1494 if (auto *I = dyn_cast<Instruction>(P.getPointer())) {
1495 auto toRemoveIt = ReverseNonLocalDefsCache.find(I);
1496 if (toRemoveIt != ReverseNonLocalDefsCache.end()) {
1497 for (const auto *entry : toRemoveIt->second)
1498 NonLocalDefsCache.erase(entry);
1499 ReverseNonLocalDefsCache.erase(toRemoveIt);
1504 CachedNonLocalPointerInfo::iterator It = NonLocalPointerDeps.find(P);
1505 if (It == NonLocalPointerDeps.end())
1508 // Remove all of the entries in the BB->val map. This involves removing
1509 // instructions from the reverse map.
1510 NonLocalDepInfo &PInfo = It->second.NonLocalDeps;
1512 for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
1513 Instruction *Target = PInfo[i].getResult().getInst();
1515 continue; // Ignore non-local dep results.
1516 assert(Target->getParent() == PInfo[i].getBB());
1518 // Eliminating the dirty entry from 'Cache', so update the reverse info.
1519 RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P);
1522 // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
1523 NonLocalPointerDeps.erase(It);
1526 void MemoryDependenceResults::invalidateCachedPointerInfo(Value *Ptr) {
1527 // If Ptr isn't really a pointer, just ignore it.
1528 if (!Ptr->getType()->isPointerTy())
1530 // Flush store info for the pointer.
1531 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false));
1532 // Flush load info for the pointer.
1533 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
1534 // Invalidate phis that use the pointer.
1535 PV.invalidateValue(Ptr);
1538 void MemoryDependenceResults::invalidateCachedPredecessors() {
1542 void MemoryDependenceResults::removeInstruction(Instruction *RemInst) {
1543 // Walk through the Non-local dependencies, removing this one as the value
1544 // for any cached queries.
1545 NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
1546 if (NLDI != NonLocalDeps.end()) {
1547 NonLocalDepInfo &BlockMap = NLDI->second.first;
1548 for (auto &Entry : BlockMap)
1549 if (Instruction *Inst = Entry.getResult().getInst())
1550 RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
1551 NonLocalDeps.erase(NLDI);
1554 // If we have a cached local dependence query for this instruction, remove it.
1555 LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
1556 if (LocalDepEntry != LocalDeps.end()) {
1557 // Remove us from DepInst's reverse set now that the local dep info is gone.
1558 if (Instruction *Inst = LocalDepEntry->second.getInst())
1559 RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
1561 // Remove this local dependency info.
1562 LocalDeps.erase(LocalDepEntry);
1565 // If we have any cached pointer dependencies on this instruction, remove
1566 // them. If the instruction has non-pointer type, then it can't be a pointer
1569 // Remove it from both the load info and the store info. The instruction
1570 // can't be in either of these maps if it is non-pointer.
1571 if (RemInst->getType()->isPointerTy()) {
1572 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
1573 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
1576 // Loop over all of the things that depend on the instruction we're removing.
1577 SmallVector<std::pair<Instruction *, Instruction *>, 8> ReverseDepsToAdd;
1579 // If we find RemInst as a clobber or Def in any of the maps for other values,
1580 // we need to replace its entry with a dirty version of the instruction after
1581 // it. If RemInst is a terminator, we use a null dirty value.
1583 // Using a dirty version of the instruction after RemInst saves having to scan
1584 // the entire block to get to this point.
1585 MemDepResult NewDirtyVal;
1586 if (!RemInst->isTerminator())
1587 NewDirtyVal = MemDepResult::getDirty(&*++RemInst->getIterator());
1589 ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
1590 if (ReverseDepIt != ReverseLocalDeps.end()) {
1591 // RemInst can't be the terminator if it has local stuff depending on it.
1592 assert(!ReverseDepIt->second.empty() && !RemInst->isTerminator() &&
1593 "Nothing can locally depend on a terminator");
1595 for (Instruction *InstDependingOnRemInst : ReverseDepIt->second) {
1596 assert(InstDependingOnRemInst != RemInst &&
1597 "Already removed our local dep info");
1599 LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
1601 // Make sure to remember that new things depend on NewDepInst.
1602 assert(NewDirtyVal.getInst() &&
1603 "There is no way something else can have "
1604 "a local dep on this if it is a terminator!");
1605 ReverseDepsToAdd.push_back(
1606 std::make_pair(NewDirtyVal.getInst(), InstDependingOnRemInst));
1609 ReverseLocalDeps.erase(ReverseDepIt);
1611 // Add new reverse deps after scanning the set, to avoid invalidating the
1612 // 'ReverseDeps' reference.
1613 while (!ReverseDepsToAdd.empty()) {
1614 ReverseLocalDeps[ReverseDepsToAdd.back().first].insert(
1615 ReverseDepsToAdd.back().second);
1616 ReverseDepsToAdd.pop_back();
1620 ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
1621 if (ReverseDepIt != ReverseNonLocalDeps.end()) {
1622 for (Instruction *I : ReverseDepIt->second) {
1623 assert(I != RemInst && "Already removed NonLocalDep info for RemInst");
1625 PerInstNLInfo &INLD = NonLocalDeps[I];
1626 // The information is now dirty!
1629 for (auto &Entry : INLD.first) {
1630 if (Entry.getResult().getInst() != RemInst)
1633 // Convert to a dirty entry for the subsequent instruction.
1634 Entry.setResult(NewDirtyVal);
1636 if (Instruction *NextI = NewDirtyVal.getInst())
1637 ReverseDepsToAdd.push_back(std::make_pair(NextI, I));
1641 ReverseNonLocalDeps.erase(ReverseDepIt);
1643 // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
1644 while (!ReverseDepsToAdd.empty()) {
1645 ReverseNonLocalDeps[ReverseDepsToAdd.back().first].insert(
1646 ReverseDepsToAdd.back().second);
1647 ReverseDepsToAdd.pop_back();
1651 // If the instruction is in ReverseNonLocalPtrDeps then it appears as a
1652 // value in the NonLocalPointerDeps info.
1653 ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
1654 ReverseNonLocalPtrDeps.find(RemInst);
1655 if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
1656 SmallVector<std::pair<Instruction *, ValueIsLoadPair>, 8>
1657 ReversePtrDepsToAdd;
1659 for (ValueIsLoadPair P : ReversePtrDepIt->second) {
1660 assert(P.getPointer() != RemInst &&
1661 "Already removed NonLocalPointerDeps info for RemInst");
1663 NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].NonLocalDeps;
1665 // The cache is not valid for any specific block anymore.
1666 NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair();
1668 // Update any entries for RemInst to use the instruction after it.
1669 for (auto &Entry : NLPDI) {
1670 if (Entry.getResult().getInst() != RemInst)
1673 // Convert to a dirty entry for the subsequent instruction.
1674 Entry.setResult(NewDirtyVal);
1676 if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
1677 ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
1680 // Re-sort the NonLocalDepInfo. Changing the dirty entry to its
1681 // subsequent value may invalidate the sortedness.
1685 ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
1687 while (!ReversePtrDepsToAdd.empty()) {
1688 ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first].insert(
1689 ReversePtrDepsToAdd.back().second);
1690 ReversePtrDepsToAdd.pop_back();
1694 // Invalidate phis that use the removed instruction.
1695 PV.invalidateValue(RemInst);
1697 assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
1698 LLVM_DEBUG(verifyRemoved(RemInst));
1701 /// Verify that the specified instruction does not occur in our internal data
1704 /// This function verifies by asserting in debug builds.
1705 void MemoryDependenceResults::verifyRemoved(Instruction *D) const {
1707 for (const auto &DepKV : LocalDeps) {
1708 assert(DepKV.first != D && "Inst occurs in data structures");
1709 assert(DepKV.second.getInst() != D && "Inst occurs in data structures");
1712 for (const auto &DepKV : NonLocalPointerDeps) {
1713 assert(DepKV.first.getPointer() != D && "Inst occurs in NLPD map key");
1714 for (const auto &Entry : DepKV.second.NonLocalDeps)
1715 assert(Entry.getResult().getInst() != D && "Inst occurs as NLPD value");
1718 for (const auto &DepKV : NonLocalDeps) {
1719 assert(DepKV.first != D && "Inst occurs in data structures");
1720 const PerInstNLInfo &INLD = DepKV.second;
1721 for (const auto &Entry : INLD.first)
1722 assert(Entry.getResult().getInst() != D &&
1723 "Inst occurs in data structures");
1726 for (const auto &DepKV : ReverseLocalDeps) {
1727 assert(DepKV.first != D && "Inst occurs in data structures");
1728 for (Instruction *Inst : DepKV.second)
1729 assert(Inst != D && "Inst occurs in data structures");
1732 for (const auto &DepKV : ReverseNonLocalDeps) {
1733 assert(DepKV.first != D && "Inst occurs in data structures");
1734 for (Instruction *Inst : DepKV.second)
1735 assert(Inst != D && "Inst occurs in data structures");
1738 for (const auto &DepKV : ReverseNonLocalPtrDeps) {
1739 assert(DepKV.first != D && "Inst occurs in rev NLPD map");
1741 for (ValueIsLoadPair P : DepKV.second)
1742 assert(P != ValueIsLoadPair(D, false) && P != ValueIsLoadPair(D, true) &&
1743 "Inst occurs in ReverseNonLocalPtrDeps map");
1748 AnalysisKey MemoryDependenceAnalysis::Key;
1750 MemoryDependenceAnalysis::MemoryDependenceAnalysis()
1751 : DefaultBlockScanLimit(BlockScanLimit) {}
1753 MemoryDependenceResults
1754 MemoryDependenceAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
1755 auto &AA = AM.getResult<AAManager>(F);
1756 auto &AC = AM.getResult<AssumptionAnalysis>(F);
1757 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1758 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1759 auto &PV = AM.getResult<PhiValuesAnalysis>(F);
1760 return MemoryDependenceResults(AA, AC, TLI, DT, PV, DefaultBlockScanLimit);
1763 char MemoryDependenceWrapperPass::ID = 0;
1765 INITIALIZE_PASS_BEGIN(MemoryDependenceWrapperPass, "memdep",
1766 "Memory Dependence Analysis", false, true)
1767 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1768 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1769 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1770 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1771 INITIALIZE_PASS_DEPENDENCY(PhiValuesWrapperPass)
1772 INITIALIZE_PASS_END(MemoryDependenceWrapperPass, "memdep",
1773 "Memory Dependence Analysis", false, true)
1775 MemoryDependenceWrapperPass::MemoryDependenceWrapperPass() : FunctionPass(ID) {
1776 initializeMemoryDependenceWrapperPassPass(*PassRegistry::getPassRegistry());
1779 MemoryDependenceWrapperPass::~MemoryDependenceWrapperPass() = default;
1781 void MemoryDependenceWrapperPass::releaseMemory() {
1785 void MemoryDependenceWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1786 AU.setPreservesAll();
1787 AU.addRequired<AssumptionCacheTracker>();
1788 AU.addRequired<DominatorTreeWrapperPass>();
1789 AU.addRequired<PhiValuesWrapperPass>();
1790 AU.addRequiredTransitive<AAResultsWrapperPass>();
1791 AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
1794 bool MemoryDependenceResults::invalidate(Function &F, const PreservedAnalyses &PA,
1795 FunctionAnalysisManager::Invalidator &Inv) {
1796 // Check whether our analysis is preserved.
1797 auto PAC = PA.getChecker<MemoryDependenceAnalysis>();
1798 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
1799 // If not, give up now.
1802 // Check whether the analyses we depend on became invalid for any reason.
1803 if (Inv.invalidate<AAManager>(F, PA) ||
1804 Inv.invalidate<AssumptionAnalysis>(F, PA) ||
1805 Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
1806 Inv.invalidate<PhiValuesAnalysis>(F, PA))
1809 // Otherwise this analysis result remains valid.
1813 unsigned MemoryDependenceResults::getDefaultBlockScanLimit() const {
1814 return DefaultBlockScanLimit;
1817 bool MemoryDependenceWrapperPass::runOnFunction(Function &F) {
1818 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1819 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1820 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1821 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1822 auto &PV = getAnalysis<PhiValuesWrapperPass>().getResult();
1823 MemDep.emplace(AA, AC, TLI, DT, PV, BlockScanLimit);