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