LLVM 24.0.0git
MemoryDependenceAnalysis.cpp
Go to the documentation of this file.
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
17#include "AnalysisOptions.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/Statistic.h"
25#include "llvm/Analysis/Loads.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"
38#include "llvm/IR/LLVMContext.h"
39#include "llvm/IR/Metadata.h"
40#include "llvm/IR/Module.h"
42#include "llvm/IR/Type.h"
43#include "llvm/IR/Use.h"
44#include "llvm/IR/Value.h"
46#include "llvm/Pass.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
81 Instruction *Inst, KeyTy Val) {
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.
98 const TargetLibraryInfo &TLI) {
99 if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
100 if (LI->isUnordered()) {
102 return ModRefInfo::Ref;
103 }
104 if (LI->getOrdering() == AtomicOrdering::Monotonic) {
106 return ModRefInfo::ModRef;
107 }
109 return ModRefInfo::ModRef;
110 }
111
112 if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
113 if (SI->isUnordered()) {
115 return ModRefInfo::Mod;
116 }
117 if (SI->getOrdering() == AtomicOrdering::Monotonic) {
119 return ModRefInfo::ModRef;
120 }
122 return ModRefInfo::ModRef;
123 }
124
125 if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
127 return ModRefInfo::ModRef;
128 }
129
130 if (const CallBase *CB = dyn_cast<CallBase>(Inst)) {
131 if (Value *FreedOp = getFreedOperand(CB, &TLI)) {
132 // calls to free() deallocate the entire structure
133 Loc = MemoryLocation::getAfter(FreedOp);
134 return ModRefInfo::Mod;
135 }
136 }
137
138 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
139 switch (II->getIntrinsicID()) {
140 case Intrinsic::lifetime_start:
141 case Intrinsic::lifetime_end:
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:
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:
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:
158 return ModRefInfo::Ref;
159 case Intrinsic::masked_store:
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;
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(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)
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(AA.getModRefInfo(Call, Loc))) {
198 if (IsInvariantLoad)
199 continue;
200 return MemDepResult::getClobber(Inst);
201 }
202 continue;
203 }
204
205 if (auto *CallB = dyn_cast<CallBase>(Inst)) {
206 bool IsIdenticalReadOnlyCall = isReadOnlyCall && !isModSet(MR) &&
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(AA.getModRefInfo(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(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())
242}
243
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>(QueryInst)) {
251 InvariantGroupDependency = getInvariantGroupPointerDependency(LI, BB);
252
253 if (InvariantGroupDependency.isDef())
254 return InvariantGroupDependency;
255 }
256 }
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
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
282 BasicBlock *BB) {
283
284 if (!LI->hasMetadata(LLVMContext::MD_invariant_group))
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>(LoadOperand))
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(Best, Other))
304 return Other;
305 return Best;
306 };
307
308 for (const Use &Us : LoadOperand->uses()) {
309 auto *U = dyn_cast<Instruction>(Us.getUser());
310 if (!U || U == LI || !DT.dominates(U, 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>(U) ||
317 (isa<StoreInst>(U) &&
318 cast<StoreInst>(U)->getPointerOperand() == LoadOperand)) &&
319 U->hasMetadata(LLVMContext::MD_invariant_group))
320 ClosestDependency = GetClosestDependency(ClosestDependency, U);
321 }
322
323 if (!ClosestDependency)
325 if (ClosestDependency->getParent() == BB)
326 return MemDepResult::getDef(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 LI, NonLocalDepResult(ClosestDependency->getParent(),
333 MemDepResult::getDef(ClosestDependency), nullptr));
334 ReverseNonLocalDefsCache[ClosestDependency].insert(LI);
336}
337
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 =
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(LLVMContext::MD_invariant_load);
384 if (LoadInst *LI = dyn_cast<LoadInst>(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>(I))
393 return LI->isVolatile() || isStrongerThan(LI->getOrdering(), AO);
394 if (auto *SI = dyn_cast<StoreInst>(I))
395 return SI->isVolatile() || isStrongerThan(SI->getOrdering(), 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)
408
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(II->getArgOperand(0));
416 AliasResult R = BatchAA.alias(ArgLoc, MemLoc);
417 if (R == AliasResult::MustAlias)
418 return MemDepResult::getDef(II);
419 if (R == AliasResult::NoAlias)
420 continue;
421 // A partial overlap must act as a barrier.
423 }
424 case Intrinsic::masked_load:
425 case Intrinsic::masked_store: {
427 /*ModRefInfo MR =*/ GetLocation(II, Loc, TLI);
428 AliasResult R = BatchAA.alias(Loc, MemLoc);
429 if (R == AliasResult::NoAlias)
430 continue;
431 if (R == AliasResult::MustAlias)
432 return MemDepResult::getDef(II);
433 if (ID == Intrinsic::masked_load)
434 continue;
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>(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(LI);
453 if (QueryInst->isVolatile())
454 // Ordering required if QueryInst is itself volatile
455 return MemDepResult::getClobber(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(LI->getOrdering())) {
464 if (!QueryInst ||
465 isComplexForReordering(QueryInst, AtomicOrdering::NotAtomic))
466 return MemDepResult::getClobber(LI);
467 if (LI->getOrdering() != AtomicOrdering::Monotonic)
468 return MemDepResult::getClobber(LI);
469 }
470
472
473 // If we found a pointer, check if it could be the same as our pointer.
474 AliasResult R = BatchAA.alias(LoadLoc, 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(BatchAA.getModRefInfoMask(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>(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))
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())
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(BatchAA.getModRefInfo(SI, 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.
540
541 // If we found a pointer, check if it could be the same as our pointer.
542 AliasResult R = BatchAA.alias(StoreLoc, 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, BatchAA,
551 *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>(Inst) || isNoAliasCall(Inst)) {
563 const Value *AccessPtr = getUnderlyingObject(MemLoc.Ptr);
564 if (AccessPtr == Inst || BatchAA.isMustAlias(Inst, 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>(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>(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(Inst, MemLoc)) {
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())
609}
610
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(ReverseLocalDeps, Inst, 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(QueryInst, MemLoc, TLI);
644 if (MemLoc.Ptr) {
645 // If we can do a pointer scan, make it happen.
646 bool isLoad = !isModSet(MR);
647 if (auto *II = dyn_cast<IntrinsicInst>(QueryInst))
648 isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
649
650 LocalCache =
651 getPointerDependencyFrom(MemLoc, isLoad, ScanPos->getIterator(),
652 QueryParent, QueryInst, nullptr);
653 } else if (auto *QueryCall = dyn_cast<CallBase>(QueryInst)) {
654 bool isReadOnly = AA.onlyReadsMemory(QueryCall);
655 LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,
656 ScanPos->getIterator(), 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(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.
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
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.
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(Entry.getBB());
707
708 // Sort the cache so that we can do fast binary search lookups below.
709 llvm::sort(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(DirtyBlocks, PredCache.get(QueryBB));
716 ++NumUncacheNonLocal;
717 }
718
719 // isReadonlyCall - If this is a read-only call, we can be more aggressive.
720 bool isReadonlyCall = AA.onlyReadsMemory(QueryCall);
721
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(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(Cache.begin(), Cache.begin() + NumSortedEntries,
740 NonLocalDepEntry(DirtyBB));
741 if (Entry != Cache.begin() && std::prev(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 *>(ReverseNonLocalDeps, Inst,
764 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(QueryCall, isReadonlyCall, ScanPos, 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.
777 } else {
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(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(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(DirtyBlocks, PredCache.get(DirtyBB));
800 }
801 }
802
803 return Cache;
804}
805
808 const MemoryLocation Loc = MemoryLocation::get(QueryInst);
809 bool isLoad = isa<LoadInst>(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(QueryInst);
819 if (NonLocalDefIt != NonLocalDefsCache.end()) {
820 Result.push_back(NonLocalDefIt->second);
822 ReverseNonLocalDefsCache, NonLocalDefIt->second.getResult().getInst(),
823 QueryInst);
824 NonLocalDefsCache.erase(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>(Inst)) {
838 return !LI->isUnordered();
839 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
840 return !SI->isUnordered();
841 }
842 return false;
843 };
844 if (QueryInst->isVolatile() || isOrdered(QueryInst)) {
845 Result.push_back(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(FromBB->getParent()->getMaxBlockNumber());
860 if (getNonLocalPointerDepFromBB(QueryInst, Address, Loc, isLoad, FromBB,
861 Result, true))
862 return;
863 Result.clear();
864 Result.push_back(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(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 Cache->begin(), Cache->begin() + NumSortedEntries, 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(ReverseNonLocalPtrDeps, &*ScanPos, CacheKey);
921 } else {
922 ++NumUncacheNonLocalPtr;
923 }
924
925 // Scan the block for the dependency.
926 MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB,
927 QueryInst, 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(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(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
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(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(Cache.size())) {
983 while (s > 0) {
984 NonLocalDepEntry Val = Cache.back();
985 Cache.pop_back();
986 MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
987 std::upper_bound(Cache.begin(), Cache.end() - s + 1, Val);
988 Cache.insert(Entry, Val);
989 s--;
990 }
991 } else {
992 llvm::sort(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(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(std::make_pair(CacheKey, 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(ReverseNonLocalPtrDeps, Inst, 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(ReverseNonLocalPtrDeps, Inst, 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.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(Entry.getBB()))
1110 continue;
1111 Value *Prev = lookupNonLocalPointerDepVisited(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(Entry.getBB(), Addr);
1124 if (Entry.getResult().isNonLocal()) {
1125 continue;
1126 }
1127
1128 if (DT.isReachableFromEntry(Entry.getBB())) {
1129 Result.push_back(
1130 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
1156 Worklist.push_back(StartBB);
1157
1158 // PredList used inside loop.
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, 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(BB)) {
1208 Result.push_back(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(Pred)) {
1224 setNonLocalPointerDepVisited(Pred, Pointer.getAddr());
1225 // First time we've looked at *PI.
1226 NewBlocks.push_back(Pred);
1227 continue;
1228 }
1229 Value *Prev = lookupNonLocalPointerDepVisited(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(NewBlock, 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(NewBlock, nullptr);
1246 GotWorklistLimit = true;
1247 goto PredTranslationFailure;
1248 }
1249 WorklistEntries -= NewBlocks.size();
1250 Worklist.append(NewBlocks.begin(), 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, NumSortedEntries);
1266 NumSortedEntries = Cache->size();
1267 }
1268 Cache = nullptr;
1269
1270 PredList.clear();
1271 for (BasicBlock *Pred : PredCache.get(BB)) {
1272 PredList.push_back(std::make_pair(Pred, 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(BB, Pred, &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(Pred)) {
1286 setNonLocalPointerDepVisited(Pred, PredPtrVal);
1287 continue;
1288 }
1289 Value *PrevVal = lookupNonLocalPointerDepVisited(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(Pred.first, 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(BB, Pred, &DT,
1336 Sel->getCondition());
1337 if (SelAddrs.first && SelAddrs.second) {
1338 Result.push_back(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, PredPointer,
1358 Loc.getWithNewPtr(PredPtrVal), isLoad,
1359 Pred, Result)) {
1360 // Add the entry to the Result list.
1361 NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal);
1362 Result.push_back(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(*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 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, 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(P.getPointer());
1450 if (it != NonLocalDefsCache.end()) {
1451 RemoveFromReverseMap(ReverseNonLocalDefsCache,
1452 it->second.getResult().getInst(), P.getPointer());
1453 NonLocalDefsCache.erase(it);
1454 }
1455
1456 if (auto *I = dyn_cast<Instruction>(P.getPointer())) {
1457 auto toRemoveIt = ReverseNonLocalDefsCache.find(I);
1458 if (toRemoveIt != ReverseNonLocalDefsCache.end()) {
1459 for (const auto *Entry : toRemoveIt->second) {
1460 [[maybe_unused]] bool Removed = NonLocalDefsCache.erase(Entry);
1461 assert(Removed && "Reverse non-local def map out of sync?");
1462 }
1463 ReverseNonLocalDefsCache.erase(toRemoveIt);
1464 }
1465 }
1466 }
1467
1468 CachedNonLocalPointerInfo::iterator It = NonLocalPointerDeps.find(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(ReverseNonLocalPtrDeps, Target, P);
1484 }
1485
1486 // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
1487 NonLocalPointerDeps.erase(It);
1488}
1489
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(ValueIsLoadPair(Ptr, false));
1496 // Flush load info for the pointer.
1497 removeCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
1498}
1499
1501 PredCache.clear();
1502}
1503
1505 EEA.removeInstruction(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(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(ReverseNonLocalDeps, Inst, RemInst);
1515 NonLocalDepsMap.erase(NLDI);
1516 }
1517
1518 // If we have a cached local dependence query for this instruction, remove it.
1519 LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(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(ReverseLocalDeps, Inst, RemInst);
1524
1525 // Remove this local dependency info.
1526 LocalDeps.erase(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(ValueIsLoadPair(RemInst, false));
1536 removeCachedNonLocalPointerDependencies(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(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 *>(ReverseNonLocalDefsCache, DepV,
1546 RemInst);
1547 NonLocalDefsCache.erase(toRemoveIt);
1548 }
1549 }
1550
1551 auto ReverseNonLocalDefIt = ReverseNonLocalDefsCache.find(RemInst);
1552 if (ReverseNonLocalDefIt != ReverseNonLocalDefsCache.end()) {
1553 for (const Value *QueryInst : ReverseNonLocalDefIt->second) {
1554 [[maybe_unused]] bool Removed = NonLocalDefsCache.erase(QueryInst);
1555 assert(Removed && "Reverse non-local def map out of sync?");
1556 }
1557 ReverseNonLocalDefsCache.erase(ReverseNonLocalDefIt);
1558 }
1559
1560 // Loop over all of the things that depend on the instruction we're removing.
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(&*++RemInst->getIterator());
1572
1573 ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(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 std::make_pair(NewDirtyVal.getInst(), InstDependingOnRemInst));
1591 }
1592
1593 ReverseLocalDeps.erase(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 ReverseDepsToAdd.back().second);
1600 ReverseDepsToAdd.pop_back();
1601 }
1602 }
1603
1604 ReverseDepIt = ReverseNonLocalDeps.find(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(std::make_pair(NextI, I));
1622 }
1623 }
1624
1625 ReverseNonLocalDeps.erase(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 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(RemInst);
1639 if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
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(std::make_pair(NewDirtyInst, P));
1664 }
1665
1666 // Re-sort the NonLocalDepInfo. Changing the dirty entry to its
1667 // subsequent value may invalidate the sortedness.
1668 llvm::sort(NLPDI);
1669 }
1670
1671 ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
1672
1673 while (!ReversePtrDepsToAdd.empty()) {
1674 ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first].insert(
1675 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
1734
1737 auto &AA = AM.getResult<AAManager>(F);
1738 auto &AC = AM.getResult<AssumptionAnalysis>(F);
1739 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1740 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1742 AA, AC, TLI, DT,
1743 DefaultBlockScanLimit.value_or(
1744 getAnalysisOptions(F).memdep_block_scan_limit));
1745}
1746
1748
1750 "Memory Dependence Analysis", false, true)
1756 "Memory Dependence Analysis", false, true)
1757
1759
1761
1763 MemDep.reset();
1764}
1765
1773
1775 AssumptionCache &AC,
1776 const TargetLibraryInfo &TLI,
1777 DominatorTree &DT,
1778 unsigned DefaultBlockScanLimit)
1779 : Opts(getAnalysisOptions(*DT.getRoot()->getParent())), AA(AA), AC(AC),
1780 TLI(TLI), DT(DT), EEA(DT), DefaultBlockScanLimit(DefaultBlockScanLimit) {}
1781
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>(F, PA) ||
1792 Inv.invalidate<AssumptionAnalysis>(F, PA) ||
1793 Inv.invalidate<DominatorTreeAnalysis>(F, PA))
1794 return true;
1795
1796 // Otherwise this analysis result remains valid.
1797 return false;
1798}
1799
1801 return DefaultBlockScanLimit;
1802}
1803
1805 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1806 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1808 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1809 MemDep.emplace(AA, AC, TLI, DT,
1810 getAnalysisOptions(F).memdep_block_scan_limit);
1811 return false;
1812}
const TargetLowering & TLI
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static bool isLoad(int Opcode)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Atomic ordering constants.
static const Function * getParent(const Value *V)
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static DeltaTreeNode * getRoot(void *Root)
This file defines the DenseMap class.
Module.h This file contains the declarations for the Module class.
This defines the Use class.
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
static const unsigned int NumResultsLimit
static ModRefInfo GetLocation(const Instruction *Inst, MemoryLocation &Loc, const TargetLibraryInfo &TLI)
If the given instruction references a specific memory location, fill in Loc with the details,...
static void RemoveFromReverseMap(DenseMap< Instruction *, SmallPtrSet< KeyTy, 4 > > &ReverseMap, Instruction *Inst, KeyTy Val)
This is a helper function that removes Val from 'Inst's set in ReverseMap.
static void SortNonLocalDepInfoCache(MemoryDependenceResults::NonLocalDepInfo &Cache, unsigned NumSortedEntries)
Sort the NonLocalDepInfo cache, given a certain number of elements in the array that are already prop...
static void AssertSorted(MemoryDependenceResults::NonLocalDepInfo &Cache, int Count=-1)
This method is used when -debug is specified to verify that cache arrays are properly kept sorted.
This file provides utility analysis objects describing memory locations.
static bool isOrdered(const Instruction *I)
This file contains the declarations for metadata subclasses.
static bool isInvariantLoad(const Instruction *I, const Value *Ptr, const bool IsKernelFn)
uint64_t IntrinsicInst * II
#define P(N)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
The possible results of an alias query.
@ NoAlias
The two locations do not alias at all.
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
Definition Analysis.h:50
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
iterator end()
Definition BasicBlock.h:453
unsigned getNumber() const
Definition BasicBlock.h:95
iterator begin()
Instruction iterator methods.
Definition BasicBlock.h:440
const Function * getParent() const
Return the enclosing method, or null if none.
Definition BasicBlock.h:213
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
Definition BasicBlock.h:170
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, bool IgnoreLocals=false)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
bool empty() const
Definition DenseMap.h:716
iterator end()
Definition DenseMap.h:686
bool erase(const KeyT &Val)
Definition DenseMap.h:930
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
Definition DenseMap.h:678
Analysis pass which computes a DominatorTree.
Definition Dominators.h:241
Legacy analysis pass which computes a DominatorTree.
Definition Dominators.h:277
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:122
An instruction for ordering other memory operations.
FunctionPass(char &pid)
Definition Pass.h:314
const BasicBlock & getEntryBlock() const
Definition Function.h:803
unsigned getMaxBlockNumber() const
Return a value larger than the largest block number.
Definition Function.h:822
LLVM_ABI bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
bool isTerminator() const
LLVM_ABI bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
LLVM_ABI bool isVolatile() const LLVM_READONLY
Return true if this instruction has a volatile memory access.
A wrapper class for inspecting calls to intrinsic functions.
An instruction for reading from memory.
Value * getPointerOperand()
A memory dependence query can return one of three different answers.
bool isNonLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the block,...
static MemDepResult getNonLocal()
bool isNonFuncLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the function.
static MemDepResult getSelect()
static MemDepResult getClobber(Instruction *Inst)
bool isDef() const
Tests if this MemDepResult represents a query that is an instruction definition dependency.
static MemDepResult getUnknown()
bool isLocal() const
Tests if this MemDepResult represents a valid local query (Clobber/Def).
bool isUnknown() const
Tests if this MemDepResult represents a query which cannot and/or will not be computed.
static MemDepResult getNonFuncLocal()
static MemDepResult getDef(Instruction *Inst)
get methods: These are static ctor methods for creating various MemDepResult kinds.
Instruction * getInst() const
If this is a normal dependency, returns the instruction that is depended on.
An analysis that produces MemoryDependenceResults for a function.
LLVM_ABI MemoryDependenceResults run(Function &F, FunctionAnalysisManager &AM)
Provides a lazy, caching interface for making common memory aliasing information queries,...
LLVM_ABI MemDepResult getSimplePointerDependencyFrom(const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst, unsigned *Limit, BatchAAResults &BatchAA)
std::vector< NonLocalDepEntry > NonLocalDepInfo
LLVM_ABI void invalidateCachedPredecessors()
Clears the PredIteratorCache info.
LLVM_ABI void invalidateCachedPointerInfo(Value *Ptr)
Invalidates cached information about the specified pointer, because it may be too conservative in mem...
LLVM_ABI MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst=nullptr, unsigned *Limit=nullptr)
Returns the instruction on which a memory location depends.
LLVM_ABI void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
LLVM_ABI MemoryDependenceResults(AAResults &AA, AssumptionCache &AC, const TargetLibraryInfo &TLI, DominatorTree &DT, unsigned DefaultBlockScanLimit)
LLVM_ABI MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB)
This analysis looks for other loads and stores with invariant.group metadata and the same pointer ope...
LLVM_ABI unsigned getDefaultBlockScanLimit() const
Some methods limit the number of instructions they will examine.
LLVM_ABI MemDepResult getDependency(Instruction *QueryInst)
Returns the instruction on which a memory operation depends.
LLVM_ABI const NonLocalDepInfo & getNonLocalCallDependency(CallBase *QueryCall)
Perform a full dependency query for the specified call, returning the set of blocks that the value is...
LLVM_ABI void getNonLocalPointerDependency(Instruction *QueryInst, SmallVectorImpl< NonLocalDepResult > &Result)
Perform a full dependency query for an access to the QueryInst's specified memory location,...
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation in the new PM.
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance.
bool runOnFunction(Function &) override
Pass Implementation stuff. This doesn't do any analysis eagerly.
void getAnalysisUsage(AnalysisUsage &AU) const override
Does not modify anything. It uses Value Numbering and Alias Analysis.
void releaseMemory() override
Clean up memory in between runs.
Representation for a specific memory location.
MemoryLocation getWithoutAATags() const
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
static MemoryLocation getAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location after Ptr, while remaining within the underlying objec...
MemoryLocation getWithNewPtr(const Value *NewPtr) const
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
const Value * Ptr
The address of the start of the location.
static LLVM_ABI MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
This is an entry in the NonLocalDepInfo cache.
void setResult(const MemDepResult &R)
const MemDepResult & getResult() const
This is a result from a NonLocal dependence query.
PHITransAddr - An address value which tracks and handles phi translation.
LLVM_ABI Value * translateValue(BasicBlock *CurBB, BasicBlock *PredBB, const DominatorTree *DT, bool MustDominate)
translateValue - PHI translate the current address up the CFG from CurBB to Pred, updating our state ...
LLVM_ABI SelectInst * getSelect() const
If the address expression depends on a select instruction (possibly through casts or GEPs),...
Value * getAddr() const
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition Analysis.h:276
std::pair< Value *, Value * > SelectAddrs
size_type size() const
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool isPointerTy() const
True if this is an instance of PointerType.
Definition Type.h:277
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
LLVM_ABI Align getPointerAlignment(const DataLayout &DL) const
Returns an alignment of the pointer value.
Definition Value.cpp:985
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition Value.cpp:707
iterator_range< use_iterator > uses()
Definition Value.h:382
const ParentTy * getParent() const
Definition ilist_node.h:34
self_iterator getIterator()
Definition ilist_node.h:123
CallInst * Call
Abstract Attribute helper functions.
Definition Attributor.h:166
@ Entry
Definition COFF.h:862
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:83
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
This is an optimization pass for GlobalISel generic memory operations.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
LLVM_ABI bool isStorePreservingMemoryLocation(const StoreInst *SI, const MemoryLocation &MemLoc, Align MemLocAlign, BatchAAResults &AA, unsigned ScanLimit)
Check whether SI, which may alias MemLoc, can be safely skipped.
Definition Loads.cpp:845
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition STLExtras.h:2224
bool isStrongerThanUnordered(AtomicOrdering AO)
LLVM_ABI bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
const AnalysisOptions & getAnalysisOptions(const LLVMContext &C)
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition MathExtras.h:326
auto reverse(ContainerTy &&C)
Definition STLExtras.h:408
bool isModSet(const ModRefInfo MRI)
Definition ModRef.h:49
void sort(IteratorTy Start, IteratorTy End)
Definition STLExtras.h:1652
bool isModOrRefSet(const ModRefInfo MRI)
Definition ModRef.h:43
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
AtomicOrdering
Atomic ordering for LLVM's memory model.
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition ModRef.h:28
@ Ref
The access may reference the value stored in memory.
Definition ModRef.h:32
@ ModRef
The access may reference and may modify the value stored in memory.
Definition ModRef.h:36
@ Mod
The access may modify the value stored in memory.
Definition ModRef.h:34
@ NoModRef
The access neither references nor modifies the value stored in memory.
Definition ModRef.h:30
@ Other
Any other memory.
Definition ModRef.h:68
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
Definition InstrProf.h:145
LLVM_ABI Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
bool isNoModRef(const ModRefInfo MRI)
Definition ModRef.h:40
bool isStrongerThan(AtomicOrdering AO, AtomicOrdering Other)
Returns true if ao is stronger than other as defined by the AtomicOrdering lattice,...
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition Alignment.h:39
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition Analysis.h:29