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