xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp (revision ae7e8a02e6e93455e026036132c4d053b2c12ad9)
1 //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation -------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file 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.
13 //
14 //===----------------------------------------------------------------------===//
15 
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/PHITransAddr.h"
27 #include "llvm/Analysis/PhiValues.h"
28 #include "llvm/Analysis/TargetLibraryInfo.h"
29 #include "llvm/Analysis/ValueTracking.h"
30 #include "llvm/IR/Attributes.h"
31 #include "llvm/IR/BasicBlock.h"
32 #include "llvm/IR/Constants.h"
33 #include "llvm/IR/DataLayout.h"
34 #include "llvm/IR/DerivedTypes.h"
35 #include "llvm/IR/Dominators.h"
36 #include "llvm/IR/Function.h"
37 #include "llvm/IR/InstrTypes.h"
38 #include "llvm/IR/Instruction.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/IntrinsicInst.h"
41 #include "llvm/IR/LLVMContext.h"
42 #include "llvm/IR/Metadata.h"
43 #include "llvm/IR/Module.h"
44 #include "llvm/IR/PredIteratorCache.h"
45 #include "llvm/IR/Type.h"
46 #include "llvm/IR/Use.h"
47 #include "llvm/IR/User.h"
48 #include "llvm/IR/Value.h"
49 #include "llvm/InitializePasses.h"
50 #include "llvm/Pass.h"
51 #include "llvm/Support/AtomicOrdering.h"
52 #include "llvm/Support/Casting.h"
53 #include "llvm/Support/CommandLine.h"
54 #include "llvm/Support/Compiler.h"
55 #include "llvm/Support/Debug.h"
56 #include "llvm/Support/MathExtras.h"
57 #include <algorithm>
58 #include <cassert>
59 #include <cstdint>
60 #include <iterator>
61 #include <utility>
62 
63 using namespace llvm;
64 
65 #define DEBUG_TYPE "memdep"
66 
67 STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");
68 STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");
69 STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");
70 
71 STATISTIC(NumCacheNonLocalPtr,
72           "Number of fully cached non-local ptr responses");
73 STATISTIC(NumCacheDirtyNonLocalPtr,
74           "Number of cached, but dirty, non-local ptr responses");
75 STATISTIC(NumUncacheNonLocalPtr, "Number of uncached non-local ptr responses");
76 STATISTIC(NumCacheCompleteNonLocalPtr,
77           "Number of block queries that were completely cached");
78 
79 // Limit for the number of instructions to scan in a block.
80 
81 static cl::opt<unsigned> BlockScanLimit(
82     "memdep-block-scan-limit", cl::Hidden, cl::init(100),
83     cl::desc("The number of instructions to scan in a block in memory "
84              "dependency analysis (default = 100)"));
85 
86 static cl::opt<unsigned>
87     BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(1000),
88                      cl::desc("The number of blocks to scan during memory "
89                               "dependency analysis (default = 1000)"));
90 
91 // Limit on the number of memdep results to process.
92 static const unsigned int NumResultsLimit = 100;
93 
94 /// This is a helper function that removes Val from 'Inst's set in ReverseMap.
95 ///
96 /// If the set becomes empty, remove Inst's entry.
97 template <typename KeyTy>
98 static void
99 RemoveFromReverseMap(DenseMap<Instruction *, SmallPtrSet<KeyTy, 4>> &ReverseMap,
100                      Instruction *Inst, KeyTy Val) {
101   typename DenseMap<Instruction *, SmallPtrSet<KeyTy, 4>>::iterator InstIt =
102       ReverseMap.find(Inst);
103   assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
104   bool Found = InstIt->second.erase(Val);
105   assert(Found && "Invalid reverse map!");
106   (void)Found;
107   if (InstIt->second.empty())
108     ReverseMap.erase(InstIt);
109 }
110 
111 /// If the given instruction references a specific memory location, fill in Loc
112 /// with the details, otherwise set Loc.Ptr to null.
113 ///
114 /// Returns a ModRefInfo value describing the general behavior of the
115 /// instruction.
116 static ModRefInfo GetLocation(const Instruction *Inst, MemoryLocation &Loc,
117                               const TargetLibraryInfo &TLI) {
118   if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
119     if (LI->isUnordered()) {
120       Loc = MemoryLocation::get(LI);
121       return ModRefInfo::Ref;
122     }
123     if (LI->getOrdering() == AtomicOrdering::Monotonic) {
124       Loc = MemoryLocation::get(LI);
125       return ModRefInfo::ModRef;
126     }
127     Loc = MemoryLocation();
128     return ModRefInfo::ModRef;
129   }
130 
131   if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
132     if (SI->isUnordered()) {
133       Loc = MemoryLocation::get(SI);
134       return ModRefInfo::Mod;
135     }
136     if (SI->getOrdering() == AtomicOrdering::Monotonic) {
137       Loc = MemoryLocation::get(SI);
138       return ModRefInfo::ModRef;
139     }
140     Loc = MemoryLocation();
141     return ModRefInfo::ModRef;
142   }
143 
144   if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
145     Loc = MemoryLocation::get(V);
146     return ModRefInfo::ModRef;
147   }
148 
149   if (const CallInst *CI = isFreeCall(Inst, &TLI)) {
150     // calls to free() deallocate the entire structure
151     Loc = MemoryLocation::getAfter(CI->getArgOperand(0));
152     return ModRefInfo::Mod;
153   }
154 
155   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
156     switch (II->getIntrinsicID()) {
157     case Intrinsic::lifetime_start:
158     case Intrinsic::lifetime_end:
159     case Intrinsic::invariant_start:
160       Loc = MemoryLocation::getForArgument(II, 1, TLI);
161       // These intrinsics don't really modify the memory, but returning Mod
162       // will allow them to be handled conservatively.
163       return ModRefInfo::Mod;
164     case Intrinsic::invariant_end:
165       Loc = MemoryLocation::getForArgument(II, 2, TLI);
166       // These intrinsics don't really modify the memory, but returning Mod
167       // will allow them to be handled conservatively.
168       return ModRefInfo::Mod;
169     case Intrinsic::masked_load:
170       Loc = MemoryLocation::getForArgument(II, 0, TLI);
171       return ModRefInfo::Ref;
172     case Intrinsic::masked_store:
173       Loc = MemoryLocation::getForArgument(II, 1, TLI);
174       return ModRefInfo::Mod;
175     default:
176       break;
177     }
178   }
179 
180   // Otherwise, just do the coarse-grained thing that always works.
181   if (Inst->mayWriteToMemory())
182     return ModRefInfo::ModRef;
183   if (Inst->mayReadFromMemory())
184     return ModRefInfo::Ref;
185   return ModRefInfo::NoModRef;
186 }
187 
188 /// Private helper for finding the local dependencies of a call site.
189 MemDepResult MemoryDependenceResults::getCallDependencyFrom(
190     CallBase *Call, bool isReadOnlyCall, BasicBlock::iterator ScanIt,
191     BasicBlock *BB) {
192   unsigned Limit = getDefaultBlockScanLimit();
193 
194   // Walk backwards through the block, looking for dependencies.
195   while (ScanIt != BB->begin()) {
196     Instruction *Inst = &*--ScanIt;
197     // Debug intrinsics don't cause dependences and should not affect Limit
198     if (isa<DbgInfoIntrinsic>(Inst))
199       continue;
200 
201     // Limit the amount of scanning we do so we don't end up with quadratic
202     // running time on extreme testcases.
203     --Limit;
204     if (!Limit)
205       return MemDepResult::getUnknown();
206 
207     // If this inst is a memory op, get the pointer it accessed
208     MemoryLocation Loc;
209     ModRefInfo MR = GetLocation(Inst, Loc, TLI);
210     if (Loc.Ptr) {
211       // A simple instruction.
212       if (isModOrRefSet(AA.getModRefInfo(Call, Loc)))
213         return MemDepResult::getClobber(Inst);
214       continue;
215     }
216 
217     if (auto *CallB = dyn_cast<CallBase>(Inst)) {
218       // If these two calls do not interfere, look past it.
219       if (isNoModRef(AA.getModRefInfo(Call, CallB))) {
220         // If the two calls are the same, return Inst as a Def, so that
221         // Call can be found redundant and eliminated.
222         if (isReadOnlyCall && !isModSet(MR) &&
223             Call->isIdenticalToWhenDefined(CallB))
224           return MemDepResult::getDef(Inst);
225 
226         // Otherwise if the two calls don't interact (e.g. CallB is readnone)
227         // keep scanning.
228         continue;
229       } else
230         return MemDepResult::getClobber(Inst);
231     }
232 
233     // If we could not obtain a pointer for the instruction and the instruction
234     // touches memory then assume that this is a dependency.
235     if (isModOrRefSet(MR))
236       return MemDepResult::getClobber(Inst);
237   }
238 
239   // No dependence found.  If this is the entry block of the function, it is
240   // unknown, otherwise it is non-local.
241   if (BB != &BB->getParent()->getEntryBlock())
242     return MemDepResult::getNonLocal();
243   return MemDepResult::getNonFuncLocal();
244 }
245 
246 static bool isVolatile(Instruction *Inst) {
247   if (auto *LI = dyn_cast<LoadInst>(Inst))
248     return LI->isVolatile();
249   if (auto *SI = dyn_cast<StoreInst>(Inst))
250     return SI->isVolatile();
251   if (auto *AI = dyn_cast<AtomicCmpXchgInst>(Inst))
252     return AI->isVolatile();
253   return false;
254 }
255 
256 MemDepResult MemoryDependenceResults::getPointerDependencyFrom(
257     const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
258     BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
259   MemDepResult InvariantGroupDependency = MemDepResult::getUnknown();
260   if (QueryInst != nullptr) {
261     if (auto *LI = dyn_cast<LoadInst>(QueryInst)) {
262       InvariantGroupDependency = getInvariantGroupPointerDependency(LI, BB);
263 
264       if (InvariantGroupDependency.isDef())
265         return InvariantGroupDependency;
266     }
267   }
268   MemDepResult SimpleDep = getSimplePointerDependencyFrom(
269       MemLoc, isLoad, ScanIt, BB, QueryInst, Limit);
270   if (SimpleDep.isDef())
271     return SimpleDep;
272   // Non-local invariant group dependency indicates there is non local Def
273   // (it only returns nonLocal if it finds nonLocal def), which is better than
274   // local clobber and everything else.
275   if (InvariantGroupDependency.isNonLocal())
276     return InvariantGroupDependency;
277 
278   assert(InvariantGroupDependency.isUnknown() &&
279          "InvariantGroupDependency should be only unknown at this point");
280   return SimpleDep;
281 }
282 
283 MemDepResult
284 MemoryDependenceResults::getInvariantGroupPointerDependency(LoadInst *LI,
285                                                             BasicBlock *BB) {
286 
287   if (!LI->hasMetadata(LLVMContext::MD_invariant_group))
288     return MemDepResult::getUnknown();
289 
290   // Take the ptr operand after all casts and geps 0. This way we can search
291   // cast graph down only.
292   Value *LoadOperand = LI->getPointerOperand()->stripPointerCasts();
293 
294   // It's is not safe to walk the use list of global value, because function
295   // passes aren't allowed to look outside their functions.
296   // FIXME: this could be fixed by filtering instructions from outside
297   // of current function.
298   if (isa<GlobalValue>(LoadOperand))
299     return MemDepResult::getUnknown();
300 
301   // Queue to process all pointers that are equivalent to load operand.
302   SmallVector<const Value *, 8> LoadOperandsQueue;
303   LoadOperandsQueue.push_back(LoadOperand);
304 
305   Instruction *ClosestDependency = nullptr;
306   // Order of instructions in uses list is unpredictible. In order to always
307   // get the same result, we will look for the closest dominance.
308   auto GetClosestDependency = [this](Instruction *Best, Instruction *Other) {
309     assert(Other && "Must call it with not null instruction");
310     if (Best == nullptr || DT.dominates(Best, Other))
311       return Other;
312     return Best;
313   };
314 
315   // FIXME: This loop is O(N^2) because dominates can be O(n) and in worst case
316   // we will see all the instructions. This should be fixed in MSSA.
317   while (!LoadOperandsQueue.empty()) {
318     const Value *Ptr = LoadOperandsQueue.pop_back_val();
319     assert(Ptr && !isa<GlobalValue>(Ptr) &&
320            "Null or GlobalValue should not be inserted");
321 
322     for (const Use &Us : Ptr->uses()) {
323       auto *U = dyn_cast<Instruction>(Us.getUser());
324       if (!U || U == LI || !DT.dominates(U, LI))
325         continue;
326 
327       // Bitcast or gep with zeros are using Ptr. Add to queue to check it's
328       // users.      U = bitcast Ptr
329       if (isa<BitCastInst>(U)) {
330         LoadOperandsQueue.push_back(U);
331         continue;
332       }
333       // Gep with zeros is equivalent to bitcast.
334       // FIXME: we are not sure if some bitcast should be canonicalized to gep 0
335       // or gep 0 to bitcast because of SROA, so there are 2 forms. When
336       // typeless pointers will be ready then both cases will be gone
337       // (and this BFS also won't be needed).
338       if (auto *GEP = dyn_cast<GetElementPtrInst>(U))
339         if (GEP->hasAllZeroIndices()) {
340           LoadOperandsQueue.push_back(U);
341           continue;
342         }
343 
344       // If we hit load/store with the same invariant.group metadata (and the
345       // same pointer operand) we can assume that value pointed by pointer
346       // operand didn't change.
347       if ((isa<LoadInst>(U) ||
348            (isa<StoreInst>(U) &&
349             cast<StoreInst>(U)->getPointerOperand() == Ptr)) &&
350           U->hasMetadata(LLVMContext::MD_invariant_group))
351         ClosestDependency = GetClosestDependency(ClosestDependency, U);
352     }
353   }
354 
355   if (!ClosestDependency)
356     return MemDepResult::getUnknown();
357   if (ClosestDependency->getParent() == BB)
358     return MemDepResult::getDef(ClosestDependency);
359   // Def(U) can't be returned here because it is non-local. If local
360   // dependency won't be found then return nonLocal counting that the
361   // user will call getNonLocalPointerDependency, which will return cached
362   // result.
363   NonLocalDefsCache.try_emplace(
364       LI, NonLocalDepResult(ClosestDependency->getParent(),
365                             MemDepResult::getDef(ClosestDependency), nullptr));
366   ReverseNonLocalDefsCache[ClosestDependency].insert(LI);
367   return MemDepResult::getNonLocal();
368 }
369 
370 MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
371     const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
372     BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
373   // We can batch AA queries, because IR does not change during a MemDep query.
374   BatchAAResults BatchAA(AA);
375   bool isInvariantLoad = false;
376 
377   unsigned DefaultLimit = getDefaultBlockScanLimit();
378   if (!Limit)
379     Limit = &DefaultLimit;
380 
381   // We must be careful with atomic accesses, as they may allow another thread
382   //   to touch this location, clobbering it. We are conservative: if the
383   //   QueryInst is not a simple (non-atomic) memory access, we automatically
384   //   return getClobber.
385   // If it is simple, we know based on the results of
386   // "Compiler testing via a theory of sound optimisations in the C11/C++11
387   //   memory model" in PLDI 2013, that a non-atomic location can only be
388   //   clobbered between a pair of a release and an acquire action, with no
389   //   access to the location in between.
390   // Here is an example for giving the general intuition behind this rule.
391   // In the following code:
392   //   store x 0;
393   //   release action; [1]
394   //   acquire action; [4]
395   //   %val = load x;
396   // It is unsafe to replace %val by 0 because another thread may be running:
397   //   acquire action; [2]
398   //   store x 42;
399   //   release action; [3]
400   // with synchronization from 1 to 2 and from 3 to 4, resulting in %val
401   // being 42. A key property of this program however is that if either
402   // 1 or 4 were missing, there would be a race between the store of 42
403   // either the store of 0 or the load (making the whole program racy).
404   // The paper mentioned above shows that the same property is respected
405   // by every program that can detect any optimization of that kind: either
406   // it is racy (undefined) or there is a release followed by an acquire
407   // between the pair of accesses under consideration.
408 
409   // If the load is invariant, we "know" that it doesn't alias *any* write. We
410   // do want to respect mustalias results since defs are useful for value
411   // forwarding, but any mayalias write can be assumed to be noalias.
412   // Arguably, this logic should be pushed inside AliasAnalysis itself.
413   if (isLoad && QueryInst) {
414     LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
415     if (LI && LI->hasMetadata(LLVMContext::MD_invariant_load))
416       isInvariantLoad = true;
417   }
418 
419   // Return "true" if and only if the instruction I is either a non-simple
420   // load or a non-simple store.
421   auto isNonSimpleLoadOrStore = [](Instruction *I) -> bool {
422     if (auto *LI = dyn_cast<LoadInst>(I))
423       return !LI->isSimple();
424     if (auto *SI = dyn_cast<StoreInst>(I))
425       return !SI->isSimple();
426     return false;
427   };
428 
429   // Return "true" if I is not a load and not a store, but it does access
430   // memory.
431   auto isOtherMemAccess = [](Instruction *I) -> bool {
432     return !isa<LoadInst>(I) && !isa<StoreInst>(I) && I->mayReadOrWriteMemory();
433   };
434 
435   // Walk backwards through the basic block, looking for dependencies.
436   while (ScanIt != BB->begin()) {
437     Instruction *Inst = &*--ScanIt;
438 
439     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
440       // Debug intrinsics don't (and can't) cause dependencies.
441       if (isa<DbgInfoIntrinsic>(II))
442         continue;
443 
444     // Limit the amount of scanning we do so we don't end up with quadratic
445     // running time on extreme testcases.
446     --*Limit;
447     if (!*Limit)
448       return MemDepResult::getUnknown();
449 
450     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
451       // If we reach a lifetime begin or end marker, then the query ends here
452       // because the value is undefined.
453       Intrinsic::ID ID = II->getIntrinsicID();
454       switch (ID) {
455       case Intrinsic::lifetime_start: {
456         // FIXME: This only considers queries directly on the invariant-tagged
457         // pointer, not on query pointers that are indexed off of them.  It'd
458         // be nice to handle that at some point (the right approach is to use
459         // GetPointerBaseWithConstantOffset).
460         MemoryLocation ArgLoc = MemoryLocation::getAfter(II->getArgOperand(1));
461         if (BatchAA.isMustAlias(ArgLoc, MemLoc))
462           return MemDepResult::getDef(II);
463         continue;
464       }
465       case Intrinsic::masked_load:
466       case Intrinsic::masked_store: {
467         MemoryLocation Loc;
468         /*ModRefInfo MR =*/ GetLocation(II, Loc, TLI);
469         AliasResult R = BatchAA.alias(Loc, MemLoc);
470         if (R == NoAlias)
471           continue;
472         if (R == MustAlias)
473           return MemDepResult::getDef(II);
474         if (ID == Intrinsic::masked_load)
475           continue;
476         return MemDepResult::getClobber(II);
477       }
478       }
479     }
480 
481     // Values depend on loads if the pointers are must aliased.  This means
482     // that a load depends on another must aliased load from the same value.
483     // One exception is atomic loads: a value can depend on an atomic load that
484     // it does not alias with when this atomic load indicates that another
485     // thread may be accessing the location.
486     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
487       // While volatile access cannot be eliminated, they do not have to clobber
488       // non-aliasing locations, as normal accesses, for example, can be safely
489       // reordered with volatile accesses.
490       if (LI->isVolatile()) {
491         if (!QueryInst)
492           // Original QueryInst *may* be volatile
493           return MemDepResult::getClobber(LI);
494         if (isVolatile(QueryInst))
495           // Ordering required if QueryInst is itself volatile
496           return MemDepResult::getClobber(LI);
497         // Otherwise, volatile doesn't imply any special ordering
498       }
499 
500       // Atomic loads have complications involved.
501       // A Monotonic (or higher) load is OK if the query inst is itself not
502       // atomic.
503       // FIXME: This is overly conservative.
504       if (LI->isAtomic() && isStrongerThanUnordered(LI->getOrdering())) {
505         if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
506             isOtherMemAccess(QueryInst))
507           return MemDepResult::getClobber(LI);
508         if (LI->getOrdering() != AtomicOrdering::Monotonic)
509           return MemDepResult::getClobber(LI);
510       }
511 
512       MemoryLocation LoadLoc = MemoryLocation::get(LI);
513 
514       // If we found a pointer, check if it could be the same as our pointer.
515       AliasResult R = BatchAA.alias(LoadLoc, MemLoc);
516 
517       if (isLoad) {
518         if (R == NoAlias)
519           continue;
520 
521         // Must aliased loads are defs of each other.
522         if (R == MustAlias)
523           return MemDepResult::getDef(Inst);
524 
525 #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads
526       // in terms of clobbering loads, but since it does this by looking
527       // at the clobbering load directly, it doesn't know about any
528       // phi translation that may have happened along the way.
529 
530         // If we have a partial alias, then return this as a clobber for the
531         // client to handle.
532         if (R == PartialAlias)
533           return MemDepResult::getClobber(Inst);
534 #endif
535 
536         // Random may-alias loads don't depend on each other without a
537         // dependence.
538         continue;
539       }
540 
541       // Stores don't depend on other no-aliased accesses.
542       if (R == NoAlias)
543         continue;
544 
545       // Stores don't alias loads from read-only memory.
546       if (BatchAA.pointsToConstantMemory(LoadLoc))
547         continue;
548 
549       // Stores depend on may/must aliased loads.
550       return MemDepResult::getDef(Inst);
551     }
552 
553     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
554       // Atomic stores have complications involved.
555       // A Monotonic store is OK if the query inst is itself not atomic.
556       // FIXME: This is overly conservative.
557       if (!SI->isUnordered() && SI->isAtomic()) {
558         if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
559             isOtherMemAccess(QueryInst))
560           return MemDepResult::getClobber(SI);
561         if (SI->getOrdering() != AtomicOrdering::Monotonic)
562           return MemDepResult::getClobber(SI);
563       }
564 
565       // FIXME: this is overly conservative.
566       // While volatile access cannot be eliminated, they do not have to clobber
567       // non-aliasing locations, as normal accesses can for example be reordered
568       // with volatile accesses.
569       if (SI->isVolatile())
570         if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
571             isOtherMemAccess(QueryInst))
572           return MemDepResult::getClobber(SI);
573 
574       // If alias analysis can tell that this store is guaranteed to not modify
575       // the query pointer, ignore it.  Use getModRefInfo to handle cases where
576       // the query pointer points to constant memory etc.
577       if (!isModOrRefSet(BatchAA.getModRefInfo(SI, MemLoc)))
578         continue;
579 
580       // Ok, this store might clobber the query pointer.  Check to see if it is
581       // a must alias: in this case, we want to return this as a def.
582       // FIXME: Use ModRefInfo::Must bit from getModRefInfo call above.
583       MemoryLocation StoreLoc = MemoryLocation::get(SI);
584 
585       // If we found a pointer, check if it could be the same as our pointer.
586       AliasResult R = BatchAA.alias(StoreLoc, MemLoc);
587 
588       if (R == NoAlias)
589         continue;
590       if (R == MustAlias)
591         return MemDepResult::getDef(Inst);
592       if (isInvariantLoad)
593         continue;
594       return MemDepResult::getClobber(Inst);
595     }
596 
597     // If this is an allocation, and if we know that the accessed pointer is to
598     // the allocation, return Def.  This means that there is no dependence and
599     // the access can be optimized based on that.  For example, a load could
600     // turn into undef.  Note that we can bypass the allocation itself when
601     // looking for a clobber in many cases; that's an alias property and is
602     // handled by BasicAA.
603     if (isa<AllocaInst>(Inst) || isNoAliasFn(Inst, &TLI)) {
604       const Value *AccessPtr = getUnderlyingObject(MemLoc.Ptr);
605       if (AccessPtr == Inst || BatchAA.isMustAlias(Inst, AccessPtr))
606         return MemDepResult::getDef(Inst);
607     }
608 
609     if (isInvariantLoad)
610       continue;
611 
612     // A release fence requires that all stores complete before it, but does
613     // not prevent the reordering of following loads or stores 'before' the
614     // fence.  As a result, we look past it when finding a dependency for
615     // loads.  DSE uses this to find preceding stores to delete and thus we
616     // can't bypass the fence if the query instruction is a store.
617     if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
618       if (isLoad && FI->getOrdering() == AtomicOrdering::Release)
619         continue;
620 
621     // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
622     ModRefInfo MR = BatchAA.getModRefInfo(Inst, MemLoc);
623     // If necessary, perform additional analysis.
624     if (isModAndRefSet(MR))
625       // TODO: Support callCapturesBefore() on BatchAAResults.
626       MR = AA.callCapturesBefore(Inst, MemLoc, &DT);
627     switch (clearMust(MR)) {
628     case ModRefInfo::NoModRef:
629       // If the call has no effect on the queried pointer, just ignore it.
630       continue;
631     case ModRefInfo::Mod:
632       return MemDepResult::getClobber(Inst);
633     case ModRefInfo::Ref:
634       // If the call is known to never store to the pointer, and if this is a
635       // load query, we can safely ignore it (scan past it).
636       if (isLoad)
637         continue;
638       LLVM_FALLTHROUGH;
639     default:
640       // Otherwise, there is a potential dependence.  Return a clobber.
641       return MemDepResult::getClobber(Inst);
642     }
643   }
644 
645   // No dependence found.  If this is the entry block of the function, it is
646   // unknown, otherwise it is non-local.
647   if (BB != &BB->getParent()->getEntryBlock())
648     return MemDepResult::getNonLocal();
649   return MemDepResult::getNonFuncLocal();
650 }
651 
652 MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst) {
653   Instruction *ScanPos = QueryInst;
654 
655   // Check for a cached result
656   MemDepResult &LocalCache = LocalDeps[QueryInst];
657 
658   // If the cached entry is non-dirty, just return it.  Note that this depends
659   // on MemDepResult's default constructing to 'dirty'.
660   if (!LocalCache.isDirty())
661     return LocalCache;
662 
663   // Otherwise, if we have a dirty entry, we know we can start the scan at that
664   // instruction, which may save us some work.
665   if (Instruction *Inst = LocalCache.getInst()) {
666     ScanPos = Inst;
667 
668     RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
669   }
670 
671   BasicBlock *QueryParent = QueryInst->getParent();
672 
673   // Do the scan.
674   if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
675     // No dependence found. If this is the entry block of the function, it is
676     // unknown, otherwise it is non-local.
677     if (QueryParent != &QueryParent->getParent()->getEntryBlock())
678       LocalCache = MemDepResult::getNonLocal();
679     else
680       LocalCache = MemDepResult::getNonFuncLocal();
681   } else {
682     MemoryLocation MemLoc;
683     ModRefInfo MR = GetLocation(QueryInst, MemLoc, TLI);
684     if (MemLoc.Ptr) {
685       // If we can do a pointer scan, make it happen.
686       bool isLoad = !isModSet(MR);
687       if (auto *II = dyn_cast<IntrinsicInst>(QueryInst))
688         isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
689 
690       LocalCache =
691           getPointerDependencyFrom(MemLoc, isLoad, ScanPos->getIterator(),
692                                    QueryParent, QueryInst, nullptr);
693     } else if (auto *QueryCall = dyn_cast<CallBase>(QueryInst)) {
694       bool isReadOnly = AA.onlyReadsMemory(QueryCall);
695       LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,
696                                          ScanPos->getIterator(), QueryParent);
697     } else
698       // Non-memory instruction.
699       LocalCache = MemDepResult::getUnknown();
700   }
701 
702   // Remember the result!
703   if (Instruction *I = LocalCache.getInst())
704     ReverseLocalDeps[I].insert(QueryInst);
705 
706   return LocalCache;
707 }
708 
709 #ifndef NDEBUG
710 /// This method is used when -debug is specified to verify that cache arrays
711 /// are properly kept sorted.
712 static void AssertSorted(MemoryDependenceResults::NonLocalDepInfo &Cache,
713                          int Count = -1) {
714   if (Count == -1)
715     Count = Cache.size();
716   assert(std::is_sorted(Cache.begin(), Cache.begin() + Count) &&
717          "Cache isn't sorted!");
718 }
719 #endif
720 
721 const MemoryDependenceResults::NonLocalDepInfo &
722 MemoryDependenceResults::getNonLocalCallDependency(CallBase *QueryCall) {
723   assert(getDependency(QueryCall).isNonLocal() &&
724          "getNonLocalCallDependency should only be used on calls with "
725          "non-local deps!");
726   PerInstNLInfo &CacheP = NonLocalDeps[QueryCall];
727   NonLocalDepInfo &Cache = CacheP.first;
728 
729   // This is the set of blocks that need to be recomputed.  In the cached case,
730   // this can happen due to instructions being deleted etc. In the uncached
731   // case, this starts out as the set of predecessors we care about.
732   SmallVector<BasicBlock *, 32> DirtyBlocks;
733 
734   if (!Cache.empty()) {
735     // Okay, we have a cache entry.  If we know it is not dirty, just return it
736     // with no computation.
737     if (!CacheP.second) {
738       ++NumCacheNonLocal;
739       return Cache;
740     }
741 
742     // If we already have a partially computed set of results, scan them to
743     // determine what is dirty, seeding our initial DirtyBlocks worklist.
744     for (auto &Entry : Cache)
745       if (Entry.getResult().isDirty())
746         DirtyBlocks.push_back(Entry.getBB());
747 
748     // Sort the cache so that we can do fast binary search lookups below.
749     llvm::sort(Cache);
750 
751     ++NumCacheDirtyNonLocal;
752     // cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
753     //     << Cache.size() << " cached: " << *QueryInst;
754   } else {
755     // Seed DirtyBlocks with each of the preds of QueryInst's block.
756     BasicBlock *QueryBB = QueryCall->getParent();
757     append_range(DirtyBlocks, PredCache.get(QueryBB));
758     ++NumUncacheNonLocal;
759   }
760 
761   // isReadonlyCall - If this is a read-only call, we can be more aggressive.
762   bool isReadonlyCall = AA.onlyReadsMemory(QueryCall);
763 
764   SmallPtrSet<BasicBlock *, 32> Visited;
765 
766   unsigned NumSortedEntries = Cache.size();
767   LLVM_DEBUG(AssertSorted(Cache));
768 
769   // Iterate while we still have blocks to update.
770   while (!DirtyBlocks.empty()) {
771     BasicBlock *DirtyBB = DirtyBlocks.pop_back_val();
772 
773     // Already processed this block?
774     if (!Visited.insert(DirtyBB).second)
775       continue;
776 
777     // Do a binary search to see if we already have an entry for this block in
778     // the cache set.  If so, find it.
779     LLVM_DEBUG(AssertSorted(Cache, NumSortedEntries));
780     NonLocalDepInfo::iterator Entry =
781         std::upper_bound(Cache.begin(), Cache.begin() + NumSortedEntries,
782                          NonLocalDepEntry(DirtyBB));
783     if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB)
784       --Entry;
785 
786     NonLocalDepEntry *ExistingResult = nullptr;
787     if (Entry != Cache.begin() + NumSortedEntries &&
788         Entry->getBB() == DirtyBB) {
789       // If we already have an entry, and if it isn't already dirty, the block
790       // is done.
791       if (!Entry->getResult().isDirty())
792         continue;
793 
794       // Otherwise, remember this slot so we can update the value.
795       ExistingResult = &*Entry;
796     }
797 
798     // If the dirty entry has a pointer, start scanning from it so we don't have
799     // to rescan the entire block.
800     BasicBlock::iterator ScanPos = DirtyBB->end();
801     if (ExistingResult) {
802       if (Instruction *Inst = ExistingResult->getResult().getInst()) {
803         ScanPos = Inst->getIterator();
804         // We're removing QueryInst's use of Inst.
805         RemoveFromReverseMap<Instruction *>(ReverseNonLocalDeps, Inst,
806                                             QueryCall);
807       }
808     }
809 
810     // Find out if this block has a local dependency for QueryInst.
811     MemDepResult Dep;
812 
813     if (ScanPos != DirtyBB->begin()) {
814       Dep = getCallDependencyFrom(QueryCall, isReadonlyCall, ScanPos, DirtyBB);
815     } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) {
816       // No dependence found.  If this is the entry block of the function, it is
817       // a clobber, otherwise it is unknown.
818       Dep = MemDepResult::getNonLocal();
819     } else {
820       Dep = MemDepResult::getNonFuncLocal();
821     }
822 
823     // If we had a dirty entry for the block, update it.  Otherwise, just add
824     // a new entry.
825     if (ExistingResult)
826       ExistingResult->setResult(Dep);
827     else
828       Cache.push_back(NonLocalDepEntry(DirtyBB, Dep));
829 
830     // If the block has a dependency (i.e. it isn't completely transparent to
831     // the value), remember the association!
832     if (!Dep.isNonLocal()) {
833       // Keep the ReverseNonLocalDeps map up to date so we can efficiently
834       // update this when we remove instructions.
835       if (Instruction *Inst = Dep.getInst())
836         ReverseNonLocalDeps[Inst].insert(QueryCall);
837     } else {
838 
839       // If the block *is* completely transparent to the load, we need to check
840       // the predecessors of this block.  Add them to our worklist.
841       append_range(DirtyBlocks, PredCache.get(DirtyBB));
842     }
843   }
844 
845   return Cache;
846 }
847 
848 void MemoryDependenceResults::getNonLocalPointerDependency(
849     Instruction *QueryInst, SmallVectorImpl<NonLocalDepResult> &Result) {
850   const MemoryLocation Loc = MemoryLocation::get(QueryInst);
851   bool isLoad = isa<LoadInst>(QueryInst);
852   BasicBlock *FromBB = QueryInst->getParent();
853   assert(FromBB);
854 
855   assert(Loc.Ptr->getType()->isPointerTy() &&
856          "Can't get pointer deps of a non-pointer!");
857   Result.clear();
858   {
859     // Check if there is cached Def with invariant.group.
860     auto NonLocalDefIt = NonLocalDefsCache.find(QueryInst);
861     if (NonLocalDefIt != NonLocalDefsCache.end()) {
862       Result.push_back(NonLocalDefIt->second);
863       ReverseNonLocalDefsCache[NonLocalDefIt->second.getResult().getInst()]
864           .erase(QueryInst);
865       NonLocalDefsCache.erase(NonLocalDefIt);
866       return;
867     }
868   }
869   // This routine does not expect to deal with volatile instructions.
870   // Doing so would require piping through the QueryInst all the way through.
871   // TODO: volatiles can't be elided, but they can be reordered with other
872   // non-volatile accesses.
873 
874   // We currently give up on any instruction which is ordered, but we do handle
875   // atomic instructions which are unordered.
876   // TODO: Handle ordered instructions
877   auto isOrdered = [](Instruction *Inst) {
878     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
879       return !LI->isUnordered();
880     } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
881       return !SI->isUnordered();
882     }
883     return false;
884   };
885   if (isVolatile(QueryInst) || isOrdered(QueryInst)) {
886     Result.push_back(NonLocalDepResult(FromBB, MemDepResult::getUnknown(),
887                                        const_cast<Value *>(Loc.Ptr)));
888     return;
889   }
890   const DataLayout &DL = FromBB->getModule()->getDataLayout();
891   PHITransAddr Address(const_cast<Value *>(Loc.Ptr), DL, &AC);
892 
893   // This is the set of blocks we've inspected, and the pointer we consider in
894   // each block.  Because of critical edges, we currently bail out if querying
895   // a block with multiple different pointers.  This can happen during PHI
896   // translation.
897   DenseMap<BasicBlock *, Value *> Visited;
898   if (getNonLocalPointerDepFromBB(QueryInst, Address, Loc, isLoad, FromBB,
899                                    Result, Visited, true))
900     return;
901   Result.clear();
902   Result.push_back(NonLocalDepResult(FromBB, MemDepResult::getUnknown(),
903                                      const_cast<Value *>(Loc.Ptr)));
904 }
905 
906 /// Compute the memdep value for BB with Pointer/PointeeSize using either
907 /// cached information in Cache or by doing a lookup (which may use dirty cache
908 /// info if available).
909 ///
910 /// If we do a lookup, add the result to the cache.
911 MemDepResult MemoryDependenceResults::GetNonLocalInfoForBlock(
912     Instruction *QueryInst, const MemoryLocation &Loc, bool isLoad,
913     BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
914 
915   bool isInvariantLoad = false;
916 
917   if (LoadInst *LI = dyn_cast_or_null<LoadInst>(QueryInst))
918     isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);
919 
920   // Do a binary search to see if we already have an entry for this block in
921   // the cache set.  If so, find it.
922   NonLocalDepInfo::iterator Entry = std::upper_bound(
923       Cache->begin(), Cache->begin() + NumSortedEntries, NonLocalDepEntry(BB));
924   if (Entry != Cache->begin() && (Entry - 1)->getBB() == BB)
925     --Entry;
926 
927   NonLocalDepEntry *ExistingResult = nullptr;
928   if (Entry != Cache->begin() + NumSortedEntries && Entry->getBB() == BB)
929     ExistingResult = &*Entry;
930 
931   // Use cached result for invariant load only if there is no dependency for non
932   // invariant load. In this case invariant load can not have any dependency as
933   // well.
934   if (ExistingResult && isInvariantLoad &&
935       !ExistingResult->getResult().isNonFuncLocal())
936     ExistingResult = nullptr;
937 
938   // If we have a cached entry, and it is non-dirty, use it as the value for
939   // this dependency.
940   if (ExistingResult && !ExistingResult->getResult().isDirty()) {
941     ++NumCacheNonLocalPtr;
942     return ExistingResult->getResult();
943   }
944 
945   // Otherwise, we have to scan for the value.  If we have a dirty cache
946   // entry, start scanning from its position, otherwise we scan from the end
947   // of the block.
948   BasicBlock::iterator ScanPos = BB->end();
949   if (ExistingResult && ExistingResult->getResult().getInst()) {
950     assert(ExistingResult->getResult().getInst()->getParent() == BB &&
951            "Instruction invalidated?");
952     ++NumCacheDirtyNonLocalPtr;
953     ScanPos = ExistingResult->getResult().getInst()->getIterator();
954 
955     // Eliminating the dirty entry from 'Cache', so update the reverse info.
956     ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
957     RemoveFromReverseMap(ReverseNonLocalPtrDeps, &*ScanPos, CacheKey);
958   } else {
959     ++NumUncacheNonLocalPtr;
960   }
961 
962   // Scan the block for the dependency.
963   MemDepResult Dep =
964       getPointerDependencyFrom(Loc, isLoad, ScanPos, BB, QueryInst);
965 
966   // Don't cache results for invariant load.
967   if (isInvariantLoad)
968     return Dep;
969 
970   // If we had a dirty entry for the block, update it.  Otherwise, just add
971   // a new entry.
972   if (ExistingResult)
973     ExistingResult->setResult(Dep);
974   else
975     Cache->push_back(NonLocalDepEntry(BB, Dep));
976 
977   // If the block has a dependency (i.e. it isn't completely transparent to
978   // the value), remember the reverse association because we just added it
979   // to Cache!
980   if (!Dep.isDef() && !Dep.isClobber())
981     return Dep;
982 
983   // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
984   // update MemDep when we remove instructions.
985   Instruction *Inst = Dep.getInst();
986   assert(Inst && "Didn't depend on anything?");
987   ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
988   ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
989   return Dep;
990 }
991 
992 /// Sort the NonLocalDepInfo cache, given a certain number of elements in the
993 /// array that are already properly ordered.
994 ///
995 /// This is optimized for the case when only a few entries are added.
996 static void
997 SortNonLocalDepInfoCache(MemoryDependenceResults::NonLocalDepInfo &Cache,
998                          unsigned NumSortedEntries) {
999   switch (Cache.size() - NumSortedEntries) {
1000   case 0:
1001     // done, no new entries.
1002     break;
1003   case 2: {
1004     // Two new entries, insert the last one into place.
1005     NonLocalDepEntry Val = Cache.back();
1006     Cache.pop_back();
1007     MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
1008         std::upper_bound(Cache.begin(), Cache.end() - 1, Val);
1009     Cache.insert(Entry, Val);
1010     LLVM_FALLTHROUGH;
1011   }
1012   case 1:
1013     // One new entry, Just insert the new value at the appropriate position.
1014     if (Cache.size() != 1) {
1015       NonLocalDepEntry Val = Cache.back();
1016       Cache.pop_back();
1017       MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
1018           llvm::upper_bound(Cache, Val);
1019       Cache.insert(Entry, Val);
1020     }
1021     break;
1022   default:
1023     // Added many values, do a full scale sort.
1024     llvm::sort(Cache);
1025     break;
1026   }
1027 }
1028 
1029 /// Perform a dependency query based on pointer/pointeesize starting at the end
1030 /// of StartBB.
1031 ///
1032 /// Add any clobber/def results to the results vector and keep track of which
1033 /// blocks are visited in 'Visited'.
1034 ///
1035 /// This has special behavior for the first block queries (when SkipFirstBlock
1036 /// is true).  In this special case, it ignores the contents of the specified
1037 /// block and starts returning dependence info for its predecessors.
1038 ///
1039 /// This function returns true on success, or false to indicate that it could
1040 /// not compute dependence information for some reason.  This should be treated
1041 /// as a clobber dependence on the first instruction in the predecessor block.
1042 bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
1043     Instruction *QueryInst, const PHITransAddr &Pointer,
1044     const MemoryLocation &Loc, bool isLoad, BasicBlock *StartBB,
1045     SmallVectorImpl<NonLocalDepResult> &Result,
1046     DenseMap<BasicBlock *, Value *> &Visited, bool SkipFirstBlock,
1047     bool IsIncomplete) {
1048   // Look up the cached info for Pointer.
1049   ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
1050 
1051   // Set up a temporary NLPI value. If the map doesn't yet have an entry for
1052   // CacheKey, this value will be inserted as the associated value. Otherwise,
1053   // it'll be ignored, and we'll have to check to see if the cached size and
1054   // aa tags are consistent with the current query.
1055   NonLocalPointerInfo InitialNLPI;
1056   InitialNLPI.Size = Loc.Size;
1057   InitialNLPI.AATags = Loc.AATags;
1058 
1059   bool isInvariantLoad = false;
1060   if (LoadInst *LI = dyn_cast_or_null<LoadInst>(QueryInst))
1061     isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);
1062 
1063   // Get the NLPI for CacheKey, inserting one into the map if it doesn't
1064   // already have one.
1065   std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
1066       NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
1067   NonLocalPointerInfo *CacheInfo = &Pair.first->second;
1068 
1069   // If we already have a cache entry for this CacheKey, we may need to do some
1070   // work to reconcile the cache entry and the current query.
1071   // Invariant loads don't participate in caching. Thus no need to reconcile.
1072   if (!isInvariantLoad && !Pair.second) {
1073     if (CacheInfo->Size != Loc.Size) {
1074       bool ThrowOutEverything;
1075       if (CacheInfo->Size.hasValue() && Loc.Size.hasValue()) {
1076         // FIXME: We may be able to do better in the face of results with mixed
1077         // precision. We don't appear to get them in practice, though, so just
1078         // be conservative.
1079         ThrowOutEverything =
1080             CacheInfo->Size.isPrecise() != Loc.Size.isPrecise() ||
1081             CacheInfo->Size.getValue() < Loc.Size.getValue();
1082       } else {
1083         // For our purposes, unknown size > all others.
1084         ThrowOutEverything = !Loc.Size.hasValue();
1085       }
1086 
1087       if (ThrowOutEverything) {
1088         // The query's Size is greater than the cached one. Throw out the
1089         // cached data and proceed with the query at the greater size.
1090         CacheInfo->Pair = BBSkipFirstBlockPair();
1091         CacheInfo->Size = Loc.Size;
1092         for (auto &Entry : CacheInfo->NonLocalDeps)
1093           if (Instruction *Inst = Entry.getResult().getInst())
1094             RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
1095         CacheInfo->NonLocalDeps.clear();
1096         // The cache is cleared (in the above line) so we will have lost
1097         // information about blocks we have already visited. We therefore must
1098         // assume that the cache information is incomplete.
1099         IsIncomplete = true;
1100       } else {
1101         // This query's Size is less than the cached one. Conservatively restart
1102         // the query using the greater size.
1103         return getNonLocalPointerDepFromBB(
1104             QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad,
1105             StartBB, Result, Visited, SkipFirstBlock, IsIncomplete);
1106       }
1107     }
1108 
1109     // If the query's AATags are inconsistent with the cached one,
1110     // conservatively throw out the cached data and restart the query with
1111     // no tag if needed.
1112     if (CacheInfo->AATags != Loc.AATags) {
1113       if (CacheInfo->AATags) {
1114         CacheInfo->Pair = BBSkipFirstBlockPair();
1115         CacheInfo->AATags = AAMDNodes();
1116         for (auto &Entry : CacheInfo->NonLocalDeps)
1117           if (Instruction *Inst = Entry.getResult().getInst())
1118             RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
1119         CacheInfo->NonLocalDeps.clear();
1120         // The cache is cleared (in the above line) so we will have lost
1121         // information about blocks we have already visited. We therefore must
1122         // assume that the cache information is incomplete.
1123         IsIncomplete = true;
1124       }
1125       if (Loc.AATags)
1126         return getNonLocalPointerDepFromBB(
1127             QueryInst, Pointer, Loc.getWithoutAATags(), isLoad, StartBB, Result,
1128             Visited, SkipFirstBlock, IsIncomplete);
1129     }
1130   }
1131 
1132   NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps;
1133 
1134   // If we have valid cached information for exactly the block we are
1135   // investigating, just return it with no recomputation.
1136   // Don't use cached information for invariant loads since it is valid for
1137   // non-invariant loads only.
1138   //
1139   // Don't use cached information for invariant loads since it is valid for
1140   // non-invariant loads only.
1141   if (!IsIncomplete && !isInvariantLoad &&
1142       CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
1143     // We have a fully cached result for this query then we can just return the
1144     // cached results and populate the visited set.  However, we have to verify
1145     // that we don't already have conflicting results for these blocks.  Check
1146     // to ensure that if a block in the results set is in the visited set that
1147     // it was for the same pointer query.
1148     if (!Visited.empty()) {
1149       for (auto &Entry : *Cache) {
1150         DenseMap<BasicBlock *, Value *>::iterator VI =
1151             Visited.find(Entry.getBB());
1152         if (VI == Visited.end() || VI->second == Pointer.getAddr())
1153           continue;
1154 
1155         // We have a pointer mismatch in a block.  Just return false, saying
1156         // that something was clobbered in this result.  We could also do a
1157         // non-fully cached query, but there is little point in doing this.
1158         return false;
1159       }
1160     }
1161 
1162     Value *Addr = Pointer.getAddr();
1163     for (auto &Entry : *Cache) {
1164       Visited.insert(std::make_pair(Entry.getBB(), Addr));
1165       if (Entry.getResult().isNonLocal()) {
1166         continue;
1167       }
1168 
1169       if (DT.isReachableFromEntry(Entry.getBB())) {
1170         Result.push_back(
1171             NonLocalDepResult(Entry.getBB(), Entry.getResult(), Addr));
1172       }
1173     }
1174     ++NumCacheCompleteNonLocalPtr;
1175     return true;
1176   }
1177 
1178   // Otherwise, either this is a new block, a block with an invalid cache
1179   // pointer or one that we're about to invalidate by putting more info into
1180   // it than its valid cache info.  If empty and not explicitly indicated as
1181   // incomplete, the result will be valid cache info, otherwise it isn't.
1182   //
1183   // Invariant loads don't affect cache in any way thus no need to update
1184   // CacheInfo as well.
1185   if (!isInvariantLoad) {
1186     if (!IsIncomplete && Cache->empty())
1187       CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
1188     else
1189       CacheInfo->Pair = BBSkipFirstBlockPair();
1190   }
1191 
1192   SmallVector<BasicBlock *, 32> Worklist;
1193   Worklist.push_back(StartBB);
1194 
1195   // PredList used inside loop.
1196   SmallVector<std::pair<BasicBlock *, PHITransAddr>, 16> PredList;
1197 
1198   // Keep track of the entries that we know are sorted.  Previously cached
1199   // entries will all be sorted.  The entries we add we only sort on demand (we
1200   // don't insert every element into its sorted position).  We know that we
1201   // won't get any reuse from currently inserted values, because we don't
1202   // revisit blocks after we insert info for them.
1203   unsigned NumSortedEntries = Cache->size();
1204   unsigned WorklistEntries = BlockNumberLimit;
1205   bool GotWorklistLimit = false;
1206   LLVM_DEBUG(AssertSorted(*Cache));
1207 
1208   while (!Worklist.empty()) {
1209     BasicBlock *BB = Worklist.pop_back_val();
1210 
1211     // If we do process a large number of blocks it becomes very expensive and
1212     // likely it isn't worth worrying about
1213     if (Result.size() > NumResultsLimit) {
1214       Worklist.clear();
1215       // Sort it now (if needed) so that recursive invocations of
1216       // getNonLocalPointerDepFromBB and other routines that could reuse the
1217       // cache value will only see properly sorted cache arrays.
1218       if (Cache && NumSortedEntries != Cache->size()) {
1219         SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1220       }
1221       // Since we bail out, the "Cache" set won't contain all of the
1222       // results for the query.  This is ok (we can still use it to accelerate
1223       // specific block queries) but we can't do the fastpath "return all
1224       // results from the set".  Clear out the indicator for this.
1225       CacheInfo->Pair = BBSkipFirstBlockPair();
1226       return false;
1227     }
1228 
1229     // Skip the first block if we have it.
1230     if (!SkipFirstBlock) {
1231       // Analyze the dependency of *Pointer in FromBB.  See if we already have
1232       // been here.
1233       assert(Visited.count(BB) && "Should check 'visited' before adding to WL");
1234 
1235       // Get the dependency info for Pointer in BB.  If we have cached
1236       // information, we will use it, otherwise we compute it.
1237       LLVM_DEBUG(AssertSorted(*Cache, NumSortedEntries));
1238       MemDepResult Dep = GetNonLocalInfoForBlock(QueryInst, Loc, isLoad, BB,
1239                                                  Cache, NumSortedEntries);
1240 
1241       // If we got a Def or Clobber, add this to the list of results.
1242       if (!Dep.isNonLocal()) {
1243         if (DT.isReachableFromEntry(BB)) {
1244           Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));
1245           continue;
1246         }
1247       }
1248     }
1249 
1250     // If 'Pointer' is an instruction defined in this block, then we need to do
1251     // phi translation to change it into a value live in the predecessor block.
1252     // If not, we just add the predecessors to the worklist and scan them with
1253     // the same Pointer.
1254     if (!Pointer.NeedsPHITranslationFromBlock(BB)) {
1255       SkipFirstBlock = false;
1256       SmallVector<BasicBlock *, 16> NewBlocks;
1257       for (BasicBlock *Pred : PredCache.get(BB)) {
1258         // Verify that we haven't looked at this block yet.
1259         std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> InsertRes =
1260             Visited.insert(std::make_pair(Pred, Pointer.getAddr()));
1261         if (InsertRes.second) {
1262           // First time we've looked at *PI.
1263           NewBlocks.push_back(Pred);
1264           continue;
1265         }
1266 
1267         // If we have seen this block before, but it was with a different
1268         // pointer then we have a phi translation failure and we have to treat
1269         // this as a clobber.
1270         if (InsertRes.first->second != Pointer.getAddr()) {
1271           // Make sure to clean up the Visited map before continuing on to
1272           // PredTranslationFailure.
1273           for (unsigned i = 0; i < NewBlocks.size(); i++)
1274             Visited.erase(NewBlocks[i]);
1275           goto PredTranslationFailure;
1276         }
1277       }
1278       if (NewBlocks.size() > WorklistEntries) {
1279         // Make sure to clean up the Visited map before continuing on to
1280         // PredTranslationFailure.
1281         for (unsigned i = 0; i < NewBlocks.size(); i++)
1282           Visited.erase(NewBlocks[i]);
1283         GotWorklistLimit = true;
1284         goto PredTranslationFailure;
1285       }
1286       WorklistEntries -= NewBlocks.size();
1287       Worklist.append(NewBlocks.begin(), NewBlocks.end());
1288       continue;
1289     }
1290 
1291     // We do need to do phi translation, if we know ahead of time we can't phi
1292     // translate this value, don't even try.
1293     if (!Pointer.IsPotentiallyPHITranslatable())
1294       goto PredTranslationFailure;
1295 
1296     // We may have added values to the cache list before this PHI translation.
1297     // If so, we haven't done anything to ensure that the cache remains sorted.
1298     // Sort it now (if needed) so that recursive invocations of
1299     // getNonLocalPointerDepFromBB and other routines that could reuse the cache
1300     // value will only see properly sorted cache arrays.
1301     if (Cache && NumSortedEntries != Cache->size()) {
1302       SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1303       NumSortedEntries = Cache->size();
1304     }
1305     Cache = nullptr;
1306 
1307     PredList.clear();
1308     for (BasicBlock *Pred : PredCache.get(BB)) {
1309       PredList.push_back(std::make_pair(Pred, Pointer));
1310 
1311       // Get the PHI translated pointer in this predecessor.  This can fail if
1312       // not translatable, in which case the getAddr() returns null.
1313       PHITransAddr &PredPointer = PredList.back().second;
1314       PredPointer.PHITranslateValue(BB, Pred, &DT, /*MustDominate=*/false);
1315       Value *PredPtrVal = PredPointer.getAddr();
1316 
1317       // Check to see if we have already visited this pred block with another
1318       // pointer.  If so, we can't do this lookup.  This failure can occur
1319       // with PHI translation when a critical edge exists and the PHI node in
1320       // the successor translates to a pointer value different than the
1321       // pointer the block was first analyzed with.
1322       std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> InsertRes =
1323           Visited.insert(std::make_pair(Pred, PredPtrVal));
1324 
1325       if (!InsertRes.second) {
1326         // We found the pred; take it off the list of preds to visit.
1327         PredList.pop_back();
1328 
1329         // If the predecessor was visited with PredPtr, then we already did
1330         // the analysis and can ignore it.
1331         if (InsertRes.first->second == PredPtrVal)
1332           continue;
1333 
1334         // Otherwise, the block was previously analyzed with a different
1335         // pointer.  We can't represent the result of this case, so we just
1336         // treat this as a phi translation failure.
1337 
1338         // Make sure to clean up the Visited map before continuing on to
1339         // PredTranslationFailure.
1340         for (unsigned i = 0, n = PredList.size(); i < n; ++i)
1341           Visited.erase(PredList[i].first);
1342 
1343         goto PredTranslationFailure;
1344       }
1345     }
1346 
1347     // Actually process results here; this need to be a separate loop to avoid
1348     // calling getNonLocalPointerDepFromBB for blocks we don't want to return
1349     // any results for.  (getNonLocalPointerDepFromBB will modify our
1350     // datastructures in ways the code after the PredTranslationFailure label
1351     // doesn't expect.)
1352     for (unsigned i = 0, n = PredList.size(); i < n; ++i) {
1353       BasicBlock *Pred = PredList[i].first;
1354       PHITransAddr &PredPointer = PredList[i].second;
1355       Value *PredPtrVal = PredPointer.getAddr();
1356 
1357       bool CanTranslate = true;
1358       // If PHI translation was unable to find an available pointer in this
1359       // predecessor, then we have to assume that the pointer is clobbered in
1360       // that predecessor.  We can still do PRE of the load, which would insert
1361       // a computation of the pointer in this predecessor.
1362       if (!PredPtrVal)
1363         CanTranslate = false;
1364 
1365       // FIXME: it is entirely possible that PHI translating will end up with
1366       // the same value.  Consider PHI translating something like:
1367       // X = phi [x, bb1], [y, bb2].  PHI translating for bb1 doesn't *need*
1368       // to recurse here, pedantically speaking.
1369 
1370       // If getNonLocalPointerDepFromBB fails here, that means the cached
1371       // result conflicted with the Visited list; we have to conservatively
1372       // assume it is unknown, but this also does not block PRE of the load.
1373       if (!CanTranslate ||
1374           !getNonLocalPointerDepFromBB(QueryInst, PredPointer,
1375                                       Loc.getWithNewPtr(PredPtrVal), isLoad,
1376                                       Pred, Result, Visited)) {
1377         // Add the entry to the Result list.
1378         NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal);
1379         Result.push_back(Entry);
1380 
1381         // Since we had a phi translation failure, the cache for CacheKey won't
1382         // include all of the entries that we need to immediately satisfy future
1383         // queries.  Mark this in NonLocalPointerDeps by setting the
1384         // BBSkipFirstBlockPair pointer to null.  This requires reuse of the
1385         // cached value to do more work but not miss the phi trans failure.
1386         NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
1387         NLPI.Pair = BBSkipFirstBlockPair();
1388         continue;
1389       }
1390     }
1391 
1392     // Refresh the CacheInfo/Cache pointer so that it isn't invalidated.
1393     CacheInfo = &NonLocalPointerDeps[CacheKey];
1394     Cache = &CacheInfo->NonLocalDeps;
1395     NumSortedEntries = Cache->size();
1396 
1397     // Since we did phi translation, the "Cache" set won't contain all of the
1398     // results for the query.  This is ok (we can still use it to accelerate
1399     // specific block queries) but we can't do the fastpath "return all
1400     // results from the set"  Clear out the indicator for this.
1401     CacheInfo->Pair = BBSkipFirstBlockPair();
1402     SkipFirstBlock = false;
1403     continue;
1404 
1405   PredTranslationFailure:
1406     // The following code is "failure"; we can't produce a sane translation
1407     // for the given block.  It assumes that we haven't modified any of
1408     // our datastructures while processing the current block.
1409 
1410     if (!Cache) {
1411       // Refresh the CacheInfo/Cache pointer if it got invalidated.
1412       CacheInfo = &NonLocalPointerDeps[CacheKey];
1413       Cache = &CacheInfo->NonLocalDeps;
1414       NumSortedEntries = Cache->size();
1415     }
1416 
1417     // Since we failed phi translation, the "Cache" set won't contain all of the
1418     // results for the query.  This is ok (we can still use it to accelerate
1419     // specific block queries) but we can't do the fastpath "return all
1420     // results from the set".  Clear out the indicator for this.
1421     CacheInfo->Pair = BBSkipFirstBlockPair();
1422 
1423     // If *nothing* works, mark the pointer as unknown.
1424     //
1425     // If this is the magic first block, return this as a clobber of the whole
1426     // incoming value.  Since we can't phi translate to one of the predecessors,
1427     // we have to bail out.
1428     if (SkipFirstBlock)
1429       return false;
1430 
1431     // Results of invariant loads are not cached thus no need to update cached
1432     // information.
1433     if (!isInvariantLoad) {
1434       for (NonLocalDepEntry &I : llvm::reverse(*Cache)) {
1435         if (I.getBB() != BB)
1436           continue;
1437 
1438         assert((GotWorklistLimit || I.getResult().isNonLocal() ||
1439                 !DT.isReachableFromEntry(BB)) &&
1440                "Should only be here with transparent block");
1441 
1442         I.setResult(MemDepResult::getUnknown());
1443 
1444 
1445         break;
1446       }
1447     }
1448     (void)GotWorklistLimit;
1449     // Go ahead and report unknown dependence.
1450     Result.push_back(
1451         NonLocalDepResult(BB, MemDepResult::getUnknown(), Pointer.getAddr()));
1452   }
1453 
1454   // Okay, we're done now.  If we added new values to the cache, re-sort it.
1455   SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1456   LLVM_DEBUG(AssertSorted(*Cache));
1457   return true;
1458 }
1459 
1460 /// If P exists in CachedNonLocalPointerInfo or NonLocalDefsCache, remove it.
1461 void MemoryDependenceResults::RemoveCachedNonLocalPointerDependencies(
1462     ValueIsLoadPair P) {
1463 
1464   // Most of the time this cache is empty.
1465   if (!NonLocalDefsCache.empty()) {
1466     auto it = NonLocalDefsCache.find(P.getPointer());
1467     if (it != NonLocalDefsCache.end()) {
1468       RemoveFromReverseMap(ReverseNonLocalDefsCache,
1469                            it->second.getResult().getInst(), P.getPointer());
1470       NonLocalDefsCache.erase(it);
1471     }
1472 
1473     if (auto *I = dyn_cast<Instruction>(P.getPointer())) {
1474       auto toRemoveIt = ReverseNonLocalDefsCache.find(I);
1475       if (toRemoveIt != ReverseNonLocalDefsCache.end()) {
1476         for (const auto *entry : toRemoveIt->second)
1477           NonLocalDefsCache.erase(entry);
1478         ReverseNonLocalDefsCache.erase(toRemoveIt);
1479       }
1480     }
1481   }
1482 
1483   CachedNonLocalPointerInfo::iterator It = NonLocalPointerDeps.find(P);
1484   if (It == NonLocalPointerDeps.end())
1485     return;
1486 
1487   // Remove all of the entries in the BB->val map.  This involves removing
1488   // instructions from the reverse map.
1489   NonLocalDepInfo &PInfo = It->second.NonLocalDeps;
1490 
1491   for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
1492     Instruction *Target = PInfo[i].getResult().getInst();
1493     if (!Target)
1494       continue; // Ignore non-local dep results.
1495     assert(Target->getParent() == PInfo[i].getBB());
1496 
1497     // Eliminating the dirty entry from 'Cache', so update the reverse info.
1498     RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P);
1499   }
1500 
1501   // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
1502   NonLocalPointerDeps.erase(It);
1503 }
1504 
1505 void MemoryDependenceResults::invalidateCachedPointerInfo(Value *Ptr) {
1506   // If Ptr isn't really a pointer, just ignore it.
1507   if (!Ptr->getType()->isPointerTy())
1508     return;
1509   // Flush store info for the pointer.
1510   RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false));
1511   // Flush load info for the pointer.
1512   RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
1513   // Invalidate phis that use the pointer.
1514   PV.invalidateValue(Ptr);
1515 }
1516 
1517 void MemoryDependenceResults::invalidateCachedPredecessors() {
1518   PredCache.clear();
1519 }
1520 
1521 void MemoryDependenceResults::removeInstruction(Instruction *RemInst) {
1522   // Walk through the Non-local dependencies, removing this one as the value
1523   // for any cached queries.
1524   NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
1525   if (NLDI != NonLocalDeps.end()) {
1526     NonLocalDepInfo &BlockMap = NLDI->second.first;
1527     for (auto &Entry : BlockMap)
1528       if (Instruction *Inst = Entry.getResult().getInst())
1529         RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
1530     NonLocalDeps.erase(NLDI);
1531   }
1532 
1533   // If we have a cached local dependence query for this instruction, remove it.
1534   LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
1535   if (LocalDepEntry != LocalDeps.end()) {
1536     // Remove us from DepInst's reverse set now that the local dep info is gone.
1537     if (Instruction *Inst = LocalDepEntry->second.getInst())
1538       RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
1539 
1540     // Remove this local dependency info.
1541     LocalDeps.erase(LocalDepEntry);
1542   }
1543 
1544   // If we have any cached dependencies on this instruction, remove
1545   // them.
1546 
1547   // If the instruction is a pointer, remove it from both the load info and the
1548   // store info.
1549   if (RemInst->getType()->isPointerTy()) {
1550     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
1551     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
1552   } else {
1553     // Otherwise, if the instructions is in the map directly, it must be a load.
1554     // Remove it.
1555     auto toRemoveIt = NonLocalDefsCache.find(RemInst);
1556     if (toRemoveIt != NonLocalDefsCache.end()) {
1557       assert(isa<LoadInst>(RemInst) &&
1558              "only load instructions should be added directly");
1559       const Instruction *DepV = toRemoveIt->second.getResult().getInst();
1560       ReverseNonLocalDefsCache.find(DepV)->second.erase(RemInst);
1561       NonLocalDefsCache.erase(toRemoveIt);
1562     }
1563   }
1564 
1565   // Loop over all of the things that depend on the instruction we're removing.
1566   SmallVector<std::pair<Instruction *, Instruction *>, 8> ReverseDepsToAdd;
1567 
1568   // If we find RemInst as a clobber or Def in any of the maps for other values,
1569   // we need to replace its entry with a dirty version of the instruction after
1570   // it.  If RemInst is a terminator, we use a null dirty value.
1571   //
1572   // Using a dirty version of the instruction after RemInst saves having to scan
1573   // the entire block to get to this point.
1574   MemDepResult NewDirtyVal;
1575   if (!RemInst->isTerminator())
1576     NewDirtyVal = MemDepResult::getDirty(&*++RemInst->getIterator());
1577 
1578   ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
1579   if (ReverseDepIt != ReverseLocalDeps.end()) {
1580     // RemInst can't be the terminator if it has local stuff depending on it.
1581     assert(!ReverseDepIt->second.empty() && !RemInst->isTerminator() &&
1582            "Nothing can locally depend on a terminator");
1583 
1584     for (Instruction *InstDependingOnRemInst : ReverseDepIt->second) {
1585       assert(InstDependingOnRemInst != RemInst &&
1586              "Already removed our local dep info");
1587 
1588       LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
1589 
1590       // Make sure to remember that new things depend on NewDepInst.
1591       assert(NewDirtyVal.getInst() &&
1592              "There is no way something else can have "
1593              "a local dep on this if it is a terminator!");
1594       ReverseDepsToAdd.push_back(
1595           std::make_pair(NewDirtyVal.getInst(), InstDependingOnRemInst));
1596     }
1597 
1598     ReverseLocalDeps.erase(ReverseDepIt);
1599 
1600     // Add new reverse deps after scanning the set, to avoid invalidating the
1601     // 'ReverseDeps' reference.
1602     while (!ReverseDepsToAdd.empty()) {
1603       ReverseLocalDeps[ReverseDepsToAdd.back().first].insert(
1604           ReverseDepsToAdd.back().second);
1605       ReverseDepsToAdd.pop_back();
1606     }
1607   }
1608 
1609   ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
1610   if (ReverseDepIt != ReverseNonLocalDeps.end()) {
1611     for (Instruction *I : ReverseDepIt->second) {
1612       assert(I != RemInst && "Already removed NonLocalDep info for RemInst");
1613 
1614       PerInstNLInfo &INLD = NonLocalDeps[I];
1615       // The information is now dirty!
1616       INLD.second = true;
1617 
1618       for (auto &Entry : INLD.first) {
1619         if (Entry.getResult().getInst() != RemInst)
1620           continue;
1621 
1622         // Convert to a dirty entry for the subsequent instruction.
1623         Entry.setResult(NewDirtyVal);
1624 
1625         if (Instruction *NextI = NewDirtyVal.getInst())
1626           ReverseDepsToAdd.push_back(std::make_pair(NextI, I));
1627       }
1628     }
1629 
1630     ReverseNonLocalDeps.erase(ReverseDepIt);
1631 
1632     // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
1633     while (!ReverseDepsToAdd.empty()) {
1634       ReverseNonLocalDeps[ReverseDepsToAdd.back().first].insert(
1635           ReverseDepsToAdd.back().second);
1636       ReverseDepsToAdd.pop_back();
1637     }
1638   }
1639 
1640   // If the instruction is in ReverseNonLocalPtrDeps then it appears as a
1641   // value in the NonLocalPointerDeps info.
1642   ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
1643       ReverseNonLocalPtrDeps.find(RemInst);
1644   if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
1645     SmallVector<std::pair<Instruction *, ValueIsLoadPair>, 8>
1646         ReversePtrDepsToAdd;
1647 
1648     for (ValueIsLoadPair P : ReversePtrDepIt->second) {
1649       assert(P.getPointer() != RemInst &&
1650              "Already removed NonLocalPointerDeps info for RemInst");
1651 
1652       NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].NonLocalDeps;
1653 
1654       // The cache is not valid for any specific block anymore.
1655       NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair();
1656 
1657       // Update any entries for RemInst to use the instruction after it.
1658       for (auto &Entry : NLPDI) {
1659         if (Entry.getResult().getInst() != RemInst)
1660           continue;
1661 
1662         // Convert to a dirty entry for the subsequent instruction.
1663         Entry.setResult(NewDirtyVal);
1664 
1665         if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
1666           ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
1667       }
1668 
1669       // Re-sort the NonLocalDepInfo.  Changing the dirty entry to its
1670       // subsequent value may invalidate the sortedness.
1671       llvm::sort(NLPDI);
1672     }
1673 
1674     ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
1675 
1676     while (!ReversePtrDepsToAdd.empty()) {
1677       ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first].insert(
1678           ReversePtrDepsToAdd.back().second);
1679       ReversePtrDepsToAdd.pop_back();
1680     }
1681   }
1682 
1683   // Invalidate phis that use the removed instruction.
1684   PV.invalidateValue(RemInst);
1685 
1686   assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
1687   LLVM_DEBUG(verifyRemoved(RemInst));
1688 }
1689 
1690 /// Verify that the specified instruction does not occur in our internal data
1691 /// structures.
1692 ///
1693 /// This function verifies by asserting in debug builds.
1694 void MemoryDependenceResults::verifyRemoved(Instruction *D) const {
1695 #ifndef NDEBUG
1696   for (const auto &DepKV : LocalDeps) {
1697     assert(DepKV.first != D && "Inst occurs in data structures");
1698     assert(DepKV.second.getInst() != D && "Inst occurs in data structures");
1699   }
1700 
1701   for (const auto &DepKV : NonLocalPointerDeps) {
1702     assert(DepKV.first.getPointer() != D && "Inst occurs in NLPD map key");
1703     for (const auto &Entry : DepKV.second.NonLocalDeps)
1704       assert(Entry.getResult().getInst() != D && "Inst occurs as NLPD value");
1705   }
1706 
1707   for (const auto &DepKV : NonLocalDeps) {
1708     assert(DepKV.first != D && "Inst occurs in data structures");
1709     const PerInstNLInfo &INLD = DepKV.second;
1710     for (const auto &Entry : INLD.first)
1711       assert(Entry.getResult().getInst() != D &&
1712              "Inst occurs in data structures");
1713   }
1714 
1715   for (const auto &DepKV : ReverseLocalDeps) {
1716     assert(DepKV.first != D && "Inst occurs in data structures");
1717     for (Instruction *Inst : DepKV.second)
1718       assert(Inst != D && "Inst occurs in data structures");
1719   }
1720 
1721   for (const auto &DepKV : ReverseNonLocalDeps) {
1722     assert(DepKV.first != D && "Inst occurs in data structures");
1723     for (Instruction *Inst : DepKV.second)
1724       assert(Inst != D && "Inst occurs in data structures");
1725   }
1726 
1727   for (const auto &DepKV : ReverseNonLocalPtrDeps) {
1728     assert(DepKV.first != D && "Inst occurs in rev NLPD map");
1729 
1730     for (ValueIsLoadPair P : DepKV.second)
1731       assert(P != ValueIsLoadPair(D, false) && P != ValueIsLoadPair(D, true) &&
1732              "Inst occurs in ReverseNonLocalPtrDeps map");
1733   }
1734 #endif
1735 }
1736 
1737 AnalysisKey MemoryDependenceAnalysis::Key;
1738 
1739 MemoryDependenceAnalysis::MemoryDependenceAnalysis()
1740     : DefaultBlockScanLimit(BlockScanLimit) {}
1741 
1742 MemoryDependenceResults
1743 MemoryDependenceAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
1744   auto &AA = AM.getResult<AAManager>(F);
1745   auto &AC = AM.getResult<AssumptionAnalysis>(F);
1746   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1747   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1748   auto &PV = AM.getResult<PhiValuesAnalysis>(F);
1749   return MemoryDependenceResults(AA, AC, TLI, DT, PV, DefaultBlockScanLimit);
1750 }
1751 
1752 char MemoryDependenceWrapperPass::ID = 0;
1753 
1754 INITIALIZE_PASS_BEGIN(MemoryDependenceWrapperPass, "memdep",
1755                       "Memory Dependence Analysis", false, true)
1756 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1757 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1758 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1759 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1760 INITIALIZE_PASS_DEPENDENCY(PhiValuesWrapperPass)
1761 INITIALIZE_PASS_END(MemoryDependenceWrapperPass, "memdep",
1762                     "Memory Dependence Analysis", false, true)
1763 
1764 MemoryDependenceWrapperPass::MemoryDependenceWrapperPass() : FunctionPass(ID) {
1765   initializeMemoryDependenceWrapperPassPass(*PassRegistry::getPassRegistry());
1766 }
1767 
1768 MemoryDependenceWrapperPass::~MemoryDependenceWrapperPass() = default;
1769 
1770 void MemoryDependenceWrapperPass::releaseMemory() {
1771   MemDep.reset();
1772 }
1773 
1774 void MemoryDependenceWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1775   AU.setPreservesAll();
1776   AU.addRequired<AssumptionCacheTracker>();
1777   AU.addRequired<DominatorTreeWrapperPass>();
1778   AU.addRequired<PhiValuesWrapperPass>();
1779   AU.addRequiredTransitive<AAResultsWrapperPass>();
1780   AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
1781 }
1782 
1783 bool MemoryDependenceResults::invalidate(Function &F, const PreservedAnalyses &PA,
1784                                FunctionAnalysisManager::Invalidator &Inv) {
1785   // Check whether our analysis is preserved.
1786   auto PAC = PA.getChecker<MemoryDependenceAnalysis>();
1787   if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
1788     // If not, give up now.
1789     return true;
1790 
1791   // Check whether the analyses we depend on became invalid for any reason.
1792   if (Inv.invalidate<AAManager>(F, PA) ||
1793       Inv.invalidate<AssumptionAnalysis>(F, PA) ||
1794       Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
1795       Inv.invalidate<PhiValuesAnalysis>(F, PA))
1796     return true;
1797 
1798   // Otherwise this analysis result remains valid.
1799   return false;
1800 }
1801 
1802 unsigned MemoryDependenceResults::getDefaultBlockScanLimit() const {
1803   return DefaultBlockScanLimit;
1804 }
1805 
1806 bool MemoryDependenceWrapperPass::runOnFunction(Function &F) {
1807   auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1808   auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1809   auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1810   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1811   auto &PV = getAnalysis<PhiValuesWrapperPass>().getResult();
1812   MemDep.emplace(AA, AC, TLI, DT, PV, BlockScanLimit);
1813   return false;
1814 }
1815