1//===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation -------------===//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//===----------------------------------------------------------------------===//
9// This file implements an analysis that determines, for a given memory
10// operation, what preceding memory operations it depends on. It builds on
11// alias analysis information, and tries to provide a lazy, caching interface to
12// a common kind of alias information query.
14//===----------------------------------------------------------------------===//
57 #define DEBUG_TYPE "memdep"
59 STATISTIC(NumCacheNonLocal,
"Number of fully cached non-local responses");
60 STATISTIC(NumCacheDirtyNonLocal,
"Number of dirty cached non-local responses");
61 STATISTIC(NumUncacheNonLocal,
"Number of uncached non-local responses");
64 "Number of fully cached non-local ptr responses");
66 "Number of cached, but dirty, non-local ptr responses");
67 STATISTIC(NumUncacheNonLocalPtr,
"Number of uncached non-local ptr responses");
69 "Number of block queries that were completely cached");
71// Limit for the number of instructions to scan in a block.
75 cl::desc(
"The number of instructions to scan in a block in memory "
76 "dependency analysis (default = 100)"));
80 cl::desc(
"The number of blocks to scan during memory "
81 "dependency analysis (default = 200)"));
85 cl::desc(
"The max number of entries allowed in a cache (default = 10000)"));
87// Limit on the number of memdep results to process.
90/// This is a helper function that removes Val from 'Inst's set in ReverseMap.
92/// If the set becomes empty, remove Inst's entry.
93template <
typename KeyTy>
98 ReverseMap.find(Inst);
99 assert(InstIt != ReverseMap.
end() &&
"Reverse map out of sync?");
100 bool Found = InstIt->second.
erase(Val);
101 assert(Found &&
"Invalid reverse map!");
103 if (InstIt->second.
empty())
104 ReverseMap.erase(InstIt);
107/// If the given instruction references a specific memory location, fill in Loc
108/// with the details, otherwise set Loc.Ptr to null.
110/// Returns a ModRefInfo value describing the general behavior of the
115 if (LI->isUnordered()) {
128 if (
SI->isUnordered()) {
147 // calls to free() deallocate the entire structure
154 switch (
II->getIntrinsicID()) {
155 case Intrinsic::lifetime_start:
156 case Intrinsic::lifetime_end:
158 // These intrinsics don't really modify the memory, but returning Mod
159 // will allow them to be handled conservatively.
161 case Intrinsic::invariant_start:
163 // These intrinsics don't really modify the memory, but returning Mod
164 // will allow them to be handled conservatively.
166 case Intrinsic::invariant_end:
168 // These intrinsics don't really modify the memory, but returning Mod
169 // will allow them to be handled conservatively.
171 case Intrinsic::masked_load:
174 case Intrinsic::masked_store:
182 // Otherwise, just do the coarse-grained thing that always works.
190/// Private helper for finding the local dependencies of a call site.
191MemDepResult MemoryDependenceResults::getCallDependencyFrom(
196 // Walk backwards through the block, looking for dependencies.
197 while (ScanIt != BB->
begin()) {
200 // Limit the amount of scanning we do so we don't end up with quadratic
201 // running time on extreme testcases.
206 // If this inst is a memory op, get the pointer it accessed
210 // A simple instruction.
217 // If these two calls do not interfere, look past it.
219 // If the two calls are the same, return Inst as a Def, so that
220 // Call can be found redundant and eliminated.
221 if (isReadOnlyCall && !
isModSet(MR) &&
225 // Otherwise if the two calls don't interact (e.g. CallB is readnone)
232 // If we could not obtain a pointer for the instruction and the instruction
233 // touches memory then assume that this is a dependency.
238 // No dependence found. If this is the entry block of the function, it is
239 // unknown, otherwise it is non-local.
250 if (QueryInst !=
nullptr) {
254 if (InvariantGroupDependency.
isDef())
255 return InvariantGroupDependency;
259 MemLoc,
isLoad, ScanIt, BB, QueryInst, Limit, BatchAA);
260 if (SimpleDep.
isDef())
262 // Non-local invariant group dependency indicates there is non local Def
263 // (it only returns nonLocal if it finds nonLocal def), which is better than
264 // local clobber and everything else.
266 return InvariantGroupDependency;
269 "InvariantGroupDependency should be only unknown at this point");
285 if (!LI->
hasMetadata(LLVMContext::MD_invariant_group))
288 // Take the ptr operand after all casts and geps 0. This way we can search
289 // cast graph down only.
292 // It's is not safe to walk the use list of global value, because function
293 // passes aren't allowed to look outside their functions.
294 // FIXME: this could be fixed by filtering instructions from outside
295 // of current function.
300 // Order of instructions in uses list is unpredictible. In order to always
301 // get the same result, we will look for the closest dominance.
303 assert(
Other &&
"Must call it with not null instruction");
304 if (Best ==
nullptr || DT.dominates(Best,
Other))
309 for (
const Use &Us : LoadOperand->
uses()) {
311 if (!U || U == LI || !DT.dominates(U, LI))
314 // If we hit load/store with the same invariant.group metadata (and the
315 // same pointer operand) we can assume that value pointed by pointer
316 // operand didn't change.
320 U->hasMetadata(LLVMContext::MD_invariant_group))
321 ClosestDependency = GetClosestDependency(ClosestDependency, U);
324 if (!ClosestDependency)
326 if (ClosestDependency->
getParent() == BB)
328 // Def(U) can't be returned here because it is non-local. If local
329 // dependency won't be found then return nonLocal counting that the
330 // user will call getNonLocalPointerDependency, which will return cached
332 NonLocalDefsCache.try_emplace(
335 ReverseNonLocalDefsCache[ClosestDependency].insert(LI);
339// Check if SI that may alias with MemLoc can be safely skipped. This is
340// possible in case if SI can only must alias or no alias with MemLoc (no
341// partial overlapping possible) and it writes the same value that MemLoc
342// contains now (it was loaded before this store and was not modified in
347 unsigned ScanLimit) {
354 if (std::min(MemLocAlign,
SI->getAlign()).value() <
359 if (!LI || LI->getParent() !=
SI->getParent())
363 unsigned NumVisitedInsts = 0;
365 if (++NumVisitedInsts > ScanLimit ||
382 Limit = &DefaultLimit;
384 // We must be careful with atomic accesses, as they may allow another thread
385 // to touch this location, clobbering it. We are conservative: if the
386 // QueryInst is not a simple (non-atomic) memory access, we automatically
387 // return getClobber.
388 // If it is simple, we know based on the results of
389 // "Compiler testing via a theory of sound optimisations in the C11/C++11
390 // memory model" in PLDI 2013, that a non-atomic location can only be
391 // clobbered between a pair of a release and an acquire action, with no
392 // access to the location in between.
393 // Here is an example for giving the general intuition behind this rule.
394 // In the following code:
396 // release action; [1]
397 // acquire action; [4]
399 // It is unsafe to replace %val by 0 because another thread may be running:
400 // acquire action; [2]
402 // release action; [3]
403 // with synchronization from 1 to 2 and from 3 to 4, resulting in %val
404 // being 42. A key property of this program however is that if either
405 // 1 or 4 were missing, there would be a race between the store of 42
406 // either the store of 0 or the load (making the whole program racy).
407 // The paper mentioned above shows that the same property is respected
408 // by every program that can detect any optimization of that kind: either
409 // it is racy (undefined) or there is a release followed by an acquire
410 // between the pair of accesses under consideration.
412 // If the load is invariant, we "know" that it doesn't alias *any* write. We
413 // do want to respect mustalias results since defs are useful for value
414 // forwarding, but any mayalias write can be assumed to be noalias.
415 // Arguably, this logic should be pushed inside AliasAnalysis itself.
418 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
420 MemLocAlign = LI->getAlign();
423 // True for volatile instruction.
424 // For Load/Store return true if atomic ordering is stronger than AO,
425 // for other instruction just true if it can read or write to memory.
433 return I->mayReadOrWriteMemory();
436 // Walk backwards through the basic block, looking for dependencies.
437 while (ScanIt != BB->
begin()) {
440 // Limit the amount of scanning we do so we don't end up with quadratic
441 // running time on extreme testcases.
447 // If we reach a lifetime begin or end marker, then the query ends here
448 // because the value is undefined.
451 case Intrinsic::lifetime_start: {
457 case Intrinsic::masked_load:
458 case Intrinsic::masked_store: {
466 if (
ID == Intrinsic::masked_load)
473 // Values depend on loads if the pointers are must aliased. This means
474 // that a load depends on another must aliased load from the same value.
475 // One exception is atomic loads: a value can depend on an atomic load that
476 // it does not alias with when this atomic load indicates that another
477 // thread may be accessing the location.
479 // While volatile access cannot be eliminated, they do not have to clobber
480 // non-aliasing locations, as normal accesses, for example, can be safely
481 // reordered with volatile accesses.
482 if (LI->isVolatile()) {
484 // Original QueryInst *may* be volatile
487 // Ordering required if QueryInst is itself volatile
489 // Otherwise, volatile doesn't imply any special ordering
492 // Atomic loads have complications involved.
493 // A Monotonic (or higher) load is OK if the query inst is itself not
495 // FIXME: This is overly conservative.
506 // If we found a pointer, check if it could be the same as our pointer.
513 // Must aliased loads are defs of each other.
517 // If we have a partial alias, then return this as a clobber for the
520 ClobberOffsets[LI] = R.getOffset();
524 // Random may-alias loads don't depend on each other without a
529 // Stores don't alias loads from read-only memory.
533 // Stores depend on may/must aliased loads.
538 // Atomic stores have complications involved.
539 // A Monotonic store is OK if the query inst is itself not atomic.
540 // FIXME: This is overly conservative.
541 if (!
SI->isUnordered() &&
SI->isAtomic()) {
545 // Ok, if we are here the guard above guarantee us that
546 // QueryInst is a non-atomic or unordered load/store.
547 // SI is atomic with monotonic or release semantic (seq_cst for store
548 // is actually a release semantic plus total order over other seq_cst
549 // instructions, as soon as QueryInst is not seq_cst we can consider it
550 // as simple release semantic).
551 // Monotonic and Release semantic allows re-ordering before store
552 // so we are safe to go further and check the aliasing. It will prohibit
553 // re-ordering in case locations are may or must alias.
556 // While volatile access cannot be eliminated, they do not have to clobber
557 // non-aliasing locations, as normal accesses can for example be reordered
558 // with volatile accesses.
559 if (
SI->isVolatile())
563 // If alias analysis can tell that this store is guaranteed to not modify
564 // the query pointer, ignore it. Use getModRefInfo to handle cases where
565 // the query pointer points to constant memory etc.
569 // Ok, this store might clobber the query pointer. Check to see if it is
570 // a must alias: in this case, we want to return this as a def.
571 // FIXME: Use ModRefInfo::Must bit from getModRefInfo call above.
574 // If we found a pointer, check if it could be the same as our pointer.
588 // If this is an allocation, and if we know that the accessed pointer is to
589 // the allocation, return Def. This means that there is no dependence and
590 // the access can be optimized based on that. For example, a load could
591 // turn into undef. Note that we can bypass the allocation itself when
592 // looking for a clobber in many cases; that's an alias property and is
593 // handled by BasicAA.
596 if (AccessPtr == Inst || BatchAA.
isMustAlias(Inst, AccessPtr))
600 // If we found a select instruction for MemLoc pointer, return it as Def
608 // A release fence requires that all stores complete before it, but does
609 // not prevent the reordering of following loads or stores 'before' the
610 // fence. As a result, we look past it when finding a dependency for
611 // loads. DSE uses this to find preceding stores to delete and thus we
612 // can't bypass the fence if the query instruction is a store.
617 // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
620 // If the call has no effect on the queried pointer, just ignore it.
625 // If the call is known to never store to the pointer, and if this is a
626 // load query, we can safely ignore it (scan past it).
631 // Otherwise, there is a potential dependence. Return a clobber.
636 // No dependence found. If this is the entry block of the function, it is
637 // unknown, otherwise it is non-local.
644 ClobberOffsets.clear();
647 // Check for a cached result
650 // If the cached entry is non-dirty, just return it. Note that this depends
651 // on MemDepResult's default constructing to 'dirty'.
652 if (!LocalCache.isDirty())
655 // Otherwise, if we have a dirty entry, we know we can start the scan at that
656 // instruction, which may save us some work.
667 // No dependence found. If this is the entry block of the function, it is
668 // unknown, otherwise it is non-local.
677 // If we can do a pointer scan, make it happen.
680 isLoad |=
II->getIntrinsicID() == Intrinsic::lifetime_start;
684 QueryParent, QueryInst,
nullptr);
686 bool isReadOnly = AA.onlyReadsMemory(QueryCall);
687 LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,
690 // Non-memory instruction.
694 // Remember the result!
696 ReverseLocalDeps[
I].insert(QueryInst);
702/// This method is used when -debug is specified to verify that cache arrays
703/// are properly kept sorted.
707 Count = Cache.size();
708 assert(std::is_sorted(Cache.begin(), Cache.begin() +
Count) &&
709 "Cache isn't sorted!");
716 "getNonLocalCallDependency should only be used on calls with "
718 PerInstNLInfo &CacheP = NonLocalDepsMap[QueryCall];
721 // This is the set of blocks that need to be recomputed. In the cached case,
722 // this can happen due to instructions being deleted etc. In the uncached
723 // case, this starts out as the set of predecessors we care about.
726 if (!Cache.empty()) {
727 // Okay, we have a cache entry. If we know it is not dirty, just return it
728 // with no computation.
729 if (!CacheP.second) {
734 // If we already have a partially computed set of results, scan them to
735 // determine what is dirty, seeding our initial DirtyBlocks worklist.
736 for (
auto &Entry : Cache)
737 if (Entry.getResult().isDirty())
740 // Sort the cache so that we can do fast binary search lookups below.
743 ++NumCacheDirtyNonLocal;
745 // Seed DirtyBlocks with each of the preds of QueryInst's block.
748 ++NumUncacheNonLocal;
751 // isReadonlyCall - If this is a read-only call, we can be more aggressive.
752 bool isReadonlyCall = AA.onlyReadsMemory(QueryCall);
756 unsigned NumSortedEntries = Cache.
size();
759 // Iterate while we still have blocks to update.
760 while (!DirtyBlocks.
empty()) {
763 // Already processed this block?
764 if (!Visited.
insert(DirtyBB).second)
767 // Do a binary search to see if we already have an entry for this block in
768 // the cache set. If so, find it.
770 NonLocalDepInfo::iterator Entry =
771 std::upper_bound(Cache.begin(), Cache.begin() + NumSortedEntries,
773 if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB)
777 if (Entry != Cache.begin() + NumSortedEntries &&
778 Entry->getBB() == DirtyBB) {
779 // If we already have an entry, and if it isn't already dirty, the block
781 if (!Entry->getResult().isDirty())
784 // Otherwise, remember this slot so we can update the value.
785 ExistingResult = &*Entry;
788 // If the dirty entry has a pointer, start scanning from it so we don't have
789 // to rescan the entire block.
791 if (ExistingResult) {
794 // We're removing QueryInst's use of Inst.
800 // Find out if this block has a local dependency for QueryInst.
803 if (ScanPos != DirtyBB->
begin()) {
804 Dep = getCallDependencyFrom(QueryCall, isReadonlyCall, ScanPos, DirtyBB);
806 // No dependence found. If this is the entry block of the function, it is
807 // a clobber, otherwise it is unknown.
813 // If we had a dirty entry for the block, update it. Otherwise, just add
820 // If the block has a dependency (i.e. it isn't completely transparent to
821 // the value), remember the association!
823 // Keep the ReverseNonLocalDeps map up to date so we can efficiently
824 // update this when we remove instructions.
826 ReverseNonLocalDeps[Inst].insert(QueryCall);
829 // If the block *is* completely transparent to the load, we need to check
830 // the predecessors of this block. Add them to our worklist.
845 assert(
Loc.Ptr->getType()->isPointerTy() &&
846 "Can't get pointer deps of a non-pointer!");
849 // Check if there is cached Def with invariant.group.
850 auto NonLocalDefIt = NonLocalDefsCache.find(QueryInst);
851 if (NonLocalDefIt != NonLocalDefsCache.end()) {
852 Result.push_back(NonLocalDefIt->second);
853 ReverseNonLocalDefsCache[NonLocalDefIt->second.getResult().getInst()]
855 NonLocalDefsCache.erase(NonLocalDefIt);
859 // This routine does not expect to deal with volatile instructions.
860 // Doing so would require piping through the QueryInst all the way through.
861 // TODO: volatiles can't be elided, but they can be reordered with other
862 // non-volatile accesses.
864 // We currently give up on any instruction which is ordered, but we do handle
865 // atomic instructions which are unordered.
866 // TODO: Handle ordered instructions
869 return !LI->isUnordered();
871 return !
SI->isUnordered();
883 // This is the set of blocks we've inspected, and the pointer we consider in
884 // each block. Because of critical edges, we currently bail out if querying
885 // a block with multiple different pointers. This can happen during PHI
889 Result, Visited,
true))
896/// Compute the memdep value for BB with Pointer/PointeeSize using either
897/// cached information in Cache or by doing a lookup (which may use dirty cache
898/// info if available).
900/// If we do a lookup, add the result to the cache.
901MemDepResult MemoryDependenceResults::getNonLocalInfoForBlock(
903 BasicBlock *BB, NonLocalDepInfo *Cache,
unsigned NumSortedEntries,
911 // Do a binary search to see if we already have an entry for this block in
912 // the cache set. If so, find it.
913 NonLocalDepInfo::iterator Entry = std::upper_bound(
915 if (Entry != Cache->begin() && (Entry - 1)->getBB() == BB)
919 if (Entry != Cache->begin() + NumSortedEntries && Entry->getBB() == BB)
920 ExistingResult = &*Entry;
922 // Use cached result for invariant load only if there is no dependency for non
923 // invariant load. In this case invariant load can not have any dependency as
927 ExistingResult =
nullptr;
929 // If we have a cached entry, and it is non-dirty, use it as the value for
931 if (ExistingResult && !ExistingResult->
getResult().isDirty()) {
932 ++NumCacheNonLocalPtr;
936 // Otherwise, we have to scan for the value. If we have a dirty cache
937 // entry, start scanning from its position, otherwise we scan from the end
942 "Instruction invalidated?");
943 ++NumCacheDirtyNonLocalPtr;
946 // Eliminating the dirty entry from 'Cache', so update the reverse info.
947 ValueIsLoadPair CacheKey(
Loc.Ptr,
isLoad);
950 ++NumUncacheNonLocalPtr;
953 // Scan the block for the dependency.
955 QueryInst,
nullptr, BatchAA);
957 // Don't cache results for invariant load.
961 // If we had a dirty entry for the block, update it. Otherwise, just add
966 Cache->push_back(NonLocalDepEntry(BB, Dep));
968 // If the block has a dependency (i.e. it isn't completely transparent to
969 // the value), remember the reverse association because we just added it
974 // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
975 // update MemDep when we remove instructions.
977 assert(Inst &&
"Didn't depend on anything?");
978 ValueIsLoadPair CacheKey(Loc.
Ptr,
isLoad);
979 ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
983/// Sort the NonLocalDepInfo cache, given a certain number of elements in the
984/// array that are already properly ordered.
986/// This is optimized for the case when only a few entries are added.
989 unsigned NumSortedEntries) {
991 // If only one entry, don't sort.
992 if (Cache.size() < 2)
995 unsigned s = Cache.size() - NumSortedEntries;
997 // If the cache is already sorted, don't sort it again.
1001 // If no entry is sorted, sort the whole cache.
1002 if (NumSortedEntries == 0) {
1007 // If the number of unsorted entires is small and the cache size is big, using
1008 // insertion sort is faster. Here use Log2_32 to quickly choose the sort
1010 if (s <
Log2_32(Cache.size())) {
1014 MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
1015 std::upper_bound(Cache.begin(), Cache.end() - s + 1, Val);
1016 Cache.insert(Entry, Val);
1024/// Perform a dependency query based on pointer/pointeesize starting at the end
1027/// Add any clobber/def results to the results vector and keep track of which
1028/// blocks are visited in 'Visited'.
1030/// This has special behavior for the first block queries (when SkipFirstBlock
1031/// is true). In this special case, it ignores the contents of the specified
1032/// block and starts returning dependence info for its predecessors.
1034/// This function returns true on success, or false to indicate that it could
1035/// not compute dependence information for some reason. This should be treated
1036/// as a clobber dependence on the first instruction in the predecessor block.
1037bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
1042 bool IsIncomplete) {
1043 // Look up the cached info for Pointer.
1046 // Set up a temporary NLPI value. If the map doesn't yet have an entry for
1047 // CacheKey, this value will be inserted as the associated value. Otherwise,
1048 // it'll be ignored, and we'll have to check to see if the cached size and
1049 // aa tags are consistent with the current query.
1050 NonLocalPointerInfo InitialNLPI;
1051 InitialNLPI.Size = Loc.
Size;
1052 InitialNLPI.AATags = Loc.
AATags;
1058 // Get the NLPI for CacheKey, inserting one into the map if it doesn't
1059 // already have one.
1060 std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
1061 NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
1062 NonLocalPointerInfo *CacheInfo = &Pair.first->second;
1064 // If we already have a cache entry for this CacheKey, we may need to do some
1065 // work to reconcile the cache entry and the current query.
1066 // Invariant loads don't participate in caching. Thus no need to reconcile.
1068 if (CacheInfo->Size != Loc.
Size) {
1069 // The query's Size is not equal to the cached one. Throw out the cached
1070 // data and proceed with the query with the new size.
1071 CacheInfo->Pair = BBSkipFirstBlockPair();
1072 CacheInfo->Size = Loc.
Size;
1073 for (
auto &Entry : CacheInfo->NonLocalDeps)
1074 if (Instruction *Inst =
Entry.getResult().getInst())
1076 CacheInfo->NonLocalDeps.clear();
1077 // The cache is cleared (in the above line) so we will have lost
1078 // information about blocks we have already visited. We therefore must
1079 // assume that the cache information is incomplete.
1080 IsIncomplete =
true;
1083 // If the query's AATags are inconsistent with the cached one,
1084 // conservatively throw out the cached data and restart the query with
1085 // no tag if needed.
1086 if (CacheInfo->AATags != Loc.
AATags) {
1087 if (CacheInfo->AATags) {
1088 CacheInfo->Pair = BBSkipFirstBlockPair();
1089 CacheInfo->AATags = AAMDNodes();
1090 for (
auto &Entry : CacheInfo->NonLocalDeps)
1091 if (Instruction *Inst =
Entry.getResult().getInst())
1093 CacheInfo->NonLocalDeps.clear();
1094 // The cache is cleared (in the above line) so we will have lost
1095 // information about blocks we have already visited. We therefore must
1096 // assume that the cache information is incomplete.
1097 IsIncomplete =
true;
1100 return getNonLocalPointerDepFromBB(
1102 Visited, SkipFirstBlock, IsIncomplete);
1108 // If we have valid cached information for exactly the block we are
1109 // investigating, just return it with no recomputation.
1110 // Don't use cached information for invariant loads since it is valid for
1111 // non-invariant loads only.
1113 CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
1114 // We have a fully cached result for this query then we can just return the
1115 // cached results and populate the visited set. However, we have to verify
1116 // that we don't already have conflicting results for these blocks. Check
1117 // to ensure that if a block in the results set is in the visited set that
1118 // it was for the same pointer query.
1119 if (!Visited.
empty()) {
1120 for (
auto &Entry : *Cache) {
1123 if (VI == Visited.
end() ||
VI->second ==
Pointer.getAddr())
1126 // We have a pointer mismatch in a block. Just return false, saying
1127 // that something was clobbered in this result. We could also do a
1128 // non-fully cached query, but there is little point in doing this.
1134 for (
auto &Entry : *Cache) {
1135 Visited.
insert(std::make_pair(
Entry.getBB(), Addr));
1136 if (
Entry.getResult().isNonLocal()) {
1140 if (DT.isReachableFromEntry(
Entry.getBB())) {
1142 NonLocalDepResult(
Entry.getBB(),
Entry.getResult(), Addr));
1145 ++NumCacheCompleteNonLocalPtr;
1149 // If the size of this cache has surpassed the global limit, stop here.
1153 // Otherwise, either this is a new block, a block with an invalid cache
1154 // pointer or one that we're about to invalidate by putting more info into
1155 // it than its valid cache info. If empty and not explicitly indicated as
1156 // incomplete, the result will be valid cache info, otherwise it isn't.
1158 // Invariant loads don't affect cache in any way thus no need to update
1159 // CacheInfo as well.
1161 if (!IsIncomplete && Cache->empty())
1162 CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
1164 CacheInfo->Pair = BBSkipFirstBlockPair();
1170 // PredList used inside loop.
1173 // Keep track of the entries that we know are sorted. Previously cached
1174 // entries will all be sorted. The entries we add we only sort on demand (we
1175 // don't insert every element into its sorted position). We know that we
1176 // won't get any reuse from currently inserted values, because we don't
1177 // revisit blocks after we insert info for them.
1178 unsigned NumSortedEntries = Cache->size();
1180 bool GotWorklistLimit =
false;
1183 BatchAAResults BatchAA(AA, &EEA);
1184 while (!Worklist.
empty()) {
1187 // If we do process a large number of blocks it becomes very expensive and
1188 // likely it isn't worth worrying about
1190 // Sort it now (if needed) so that recursive invocations of
1191 // getNonLocalPointerDepFromBB and other routines that could reuse the
1192 // cache value will only see properly sorted cache arrays.
1193 if (Cache && NumSortedEntries != Cache->size()) {
1196 // Since we bail out, the "Cache" set won't contain all of the
1197 // results for the query. This is ok (we can still use it to accelerate
1198 // specific block queries) but we can't do the fastpath "return all
1199 // results from the set". Clear out the indicator for this.
1200 CacheInfo->Pair = BBSkipFirstBlockPair();
1204 // Skip the first block if we have it.
1205 if (!SkipFirstBlock) {
1206 // Analyze the dependency of *Pointer in FromBB. See if we already have
1208 assert(Visited.
count(BB) &&
"Should check 'visited' before adding to WL");
1210 // Get the dependency info for Pointer in BB. If we have cached
1211 // information, we will use it, otherwise we compute it.
1213 MemDepResult Dep = getNonLocalInfoForBlock(
1214 QueryInst, Loc,
isLoad, BB, Cache, NumSortedEntries, BatchAA);
1216 // If we got a Def or Clobber, add this to the list of results.
1218 if (DT.isReachableFromEntry(BB)) {
1219 Result.push_back(NonLocalDepResult(BB, Dep,
Pointer.getAddr()));
1225 // If 'Pointer' is an instruction defined in this block, then we need to do
1226 // phi translation to change it into a value live in the predecessor block.
1227 // If not, we just add the predecessors to the worklist and scan them with
1228 // the same Pointer.
1229 if (!
Pointer.needsPHITranslationFromBlock(BB)) {
1230 SkipFirstBlock =
false;
1231 SmallVector<BasicBlock *, 16> NewBlocks;
1232 for (BasicBlock *Pred : PredCache.get(BB)) {
1233 // Verify that we haven't looked at this block yet.
1234 std::pair<DenseMap<BasicBlock *, Value *>::iterator,
bool> InsertRes =
1236 if (InsertRes.second) {
1237 // First time we've looked at *PI.
1242 // If we have seen this block before, but it was with a different
1243 // pointer then we have a phi translation failure and we have to treat
1244 // this as a clobber.
1245 if (InsertRes.first->second !=
Pointer.getAddr()) {
1246 // Make sure to clean up the Visited map before continuing on to
1247 // PredTranslationFailure.
1248 for (
auto *NewBlock : NewBlocks)
1249 Visited.
erase(NewBlock);
1250 goto PredTranslationFailure;
1253 if (NewBlocks.
size() > WorklistEntries) {
1254 // Make sure to clean up the Visited map before continuing on to
1255 // PredTranslationFailure.
1256 for (
auto *NewBlock : NewBlocks)
1257 Visited.
erase(NewBlock);
1258 GotWorklistLimit =
true;
1259 goto PredTranslationFailure;
1261 WorklistEntries -= NewBlocks.size();
1262 Worklist.
append(NewBlocks.begin(), NewBlocks.end());
1266 // We do need to do phi translation, if we know ahead of time we can't phi
1267 // translate this value, don't even try.
1268 if (!
Pointer.isPotentiallyPHITranslatable())
1269 goto PredTranslationFailure;
1271 // We may have added values to the cache list before this PHI translation.
1272 // If so, we haven't done anything to ensure that the cache remains sorted.
1273 // Sort it now (if needed) so that recursive invocations of
1274 // getNonLocalPointerDepFromBB and other routines that could reuse the cache
1275 // value will only see properly sorted cache arrays.
1276 if (Cache && NumSortedEntries != Cache->size()) {
1278 NumSortedEntries = Cache->size();
1283 for (BasicBlock *Pred : PredCache.get(BB)) {
1284 PredList.
push_back(std::make_pair(Pred, Pointer));
1286 // Get the PHI translated pointer in this predecessor. This can fail if
1287 // not translatable, in which case the getAddr() returns null.
1288 PHITransAddr &PredPointer = PredList.
back().second;
1290 PredPointer.
translateValue(BB, Pred, &DT,
/*MustDominate=*/false);
1292 // Check to see if we have already visited this pred block with another
1293 // pointer. If so, we can't do this lookup. This failure can occur
1294 // with PHI translation when a critical edge exists and the PHI node in
1295 // the successor translates to a pointer value different than the
1296 // pointer the block was first analyzed with.
1297 std::pair<DenseMap<BasicBlock *, Value *>::iterator,
bool> InsertRes =
1298 Visited.
insert(std::make_pair(Pred, PredPtrVal));
1300 if (!InsertRes.second) {
1301 // We found the pred; take it off the list of preds to visit.
1304 // If the predecessor was visited with PredPtr, then we already did
1305 // the analysis and can ignore it.
1306 if (InsertRes.first->second == PredPtrVal)
1309 // Otherwise, the block was previously analyzed with a different
1310 // pointer. We can't represent the result of this case, so we just
1311 // treat this as a phi translation failure.
1313 // Make sure to clean up the Visited map before continuing on to
1314 // PredTranslationFailure.
1315 for (
const auto &Pred : PredList)
1316 Visited.
erase(Pred.first);
1318 goto PredTranslationFailure;
1322 // Actually process results here; this need to be a separate loop to avoid
1323 // calling getNonLocalPointerDepFromBB for blocks we don't want to return
1324 // any results for. (getNonLocalPointerDepFromBB will modify our
1325 // datastructures in ways the code after the PredTranslationFailure label
1327 for (
auto &
I : PredList) {
1329 PHITransAddr &PredPointer =
I.second;
1332 bool CanTranslate =
true;
1333 // If PHI translation was unable to find an available pointer in this
1334 // predecessor, then we have to assume that the pointer is clobbered in
1335 // that predecessor. We can still do PRE of the load, which would insert
1336 // a computation of the pointer in this predecessor.
1338 CanTranslate =
false;
1340 // FIXME: it is entirely possible that PHI translating will end up with
1341 // the same value. Consider PHI translating something like:
1342 // X = phi [x, bb1], [y, bb2]. PHI translating for bb1 doesn't *need*
1343 // to recurse here, pedantically speaking.
1345 // If getNonLocalPointerDepFromBB fails here, that means the cached
1346 // result conflicted with the Visited list; we have to conservatively
1347 // assume it is unknown, but this also does not block PRE of the load.
1348 if (!CanTranslate ||
1349 !getNonLocalPointerDepFromBB(QueryInst, PredPointer,
1351 Pred, Result, Visited)) {
1352 // Add the entry to the Result list.
1356 // Since we had a phi translation failure, the cache for CacheKey won't
1357 // include all of the entries that we need to immediately satisfy future
1358 // queries. Mark this in NonLocalPointerDeps by setting the
1359 // BBSkipFirstBlockPair pointer to null. This requires reuse of the
1360 // cached value to do more work but not miss the phi trans failure.
1361 NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
1362 NLPI.Pair = BBSkipFirstBlockPair();
1367 // Refresh the CacheInfo/Cache pointer so that it isn't invalidated.
1368 CacheInfo = &NonLocalPointerDeps[CacheKey];
1369 Cache = &CacheInfo->NonLocalDeps;
1370 NumSortedEntries = Cache->size();
1372 // Since we did phi translation, the "Cache" set won't contain all of the
1373 // results for the query. This is ok (we can still use it to accelerate
1374 // specific block queries) but we can't do the fastpath "return all
1375 // results from the set" Clear out the indicator for this.
1376 CacheInfo->Pair = BBSkipFirstBlockPair();
1377 SkipFirstBlock =
false;
1380 PredTranslationFailure:
1381 // The following code is "failure"; we can't produce a sane translation
1382 // for the given block. It assumes that we haven't modified any of
1383 // our datastructures while processing the current block.
1386 // Refresh the CacheInfo/Cache pointer if it got invalidated.
1387 CacheInfo = &NonLocalPointerDeps[CacheKey];
1388 Cache = &CacheInfo->NonLocalDeps;
1389 NumSortedEntries = Cache->size();
1392 // Since we failed phi translation, the "Cache" set won't contain all of the
1393 // results for the query. This is ok (we can still use it to accelerate
1394 // specific block queries) but we can't do the fastpath "return all
1395 // results from the set". Clear out the indicator for this.
1396 CacheInfo->Pair = BBSkipFirstBlockPair();
1398 // If *nothing* works, mark the pointer as unknown.
1400 // If this is the magic first block, return this as a clobber of the whole
1401 // incoming value. Since we can't phi translate to one of the predecessors,
1402 // we have to bail out.
1406 // Results of invariant loads are not cached thus no need to update cached
1410 if (
I.getBB() != BB)
1413 assert((GotWorklistLimit ||
I.getResult().isNonLocal() ||
1414 !DT.isReachableFromEntry(BB)) &&
1415 "Should only be here with transparent block");
1423 (void)GotWorklistLimit;
1424 // Go ahead and report unknown dependence.
1429 // Okay, we're done now. If we added new values to the cache, re-sort it.
1435/// If P exists in CachedNonLocalPointerInfo or NonLocalDefsCache, remove it.
1436void MemoryDependenceResults::removeCachedNonLocalPointerDependencies(
1437 ValueIsLoadPair
P) {
1439 // Most of the time this cache is empty.
1440 if (!NonLocalDefsCache.empty()) {
1441 auto it = NonLocalDefsCache.find(
P.getPointer());
1442 if (it != NonLocalDefsCache.end()) {
1444 it->second.getResult().getInst(),
P.getPointer());
1445 NonLocalDefsCache.erase(it);
1449 auto toRemoveIt = ReverseNonLocalDefsCache.find(
I);
1450 if (toRemoveIt != ReverseNonLocalDefsCache.end()) {
1451 for (
const auto *entry : toRemoveIt->second)
1452 NonLocalDefsCache.erase(entry);
1453 ReverseNonLocalDefsCache.erase(toRemoveIt);
1459 if (It == NonLocalPointerDeps.end())
1462 // Remove all of the entries in the BB->val map. This involves removing
1463 // instructions from the reverse map.
1466 for (
const NonLocalDepEntry &DE : PInfo) {
1469 continue;
// Ignore non-local dep results.
1472 // Eliminating the dirty entry from 'Cache', so update the reverse info.
1476 // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
1477 NonLocalPointerDeps.erase(It);
1481 // If Ptr isn't really a pointer, just ignore it.
1482 if (!
Ptr->getType()->isPointerTy())
1484 // Flush store info for the pointer.
1485 removeCachedNonLocalPointerDependencies(ValueIsLoadPair(
Ptr,
false));
1486 // Flush load info for the pointer.
1487 removeCachedNonLocalPointerDependencies(ValueIsLoadPair(
Ptr,
true));
1495 EEA.removeInstruction(RemInst);
1497 // Walk through the Non-local dependencies, removing this one as the value
1498 // for any cached queries.
1500 if (NLDI != NonLocalDepsMap.end()) {
1502 for (
auto &Entry : BlockMap)
1503 if (
Instruction *Inst = Entry.getResult().getInst())
1505 NonLocalDepsMap.erase(NLDI);
1508 // If we have a cached local dependence query for this instruction, remove it.
1510 if (LocalDepEntry != LocalDeps.end()) {
1511 // Remove us from DepInst's reverse set now that the local dep info is gone.
1512 if (
Instruction *Inst = LocalDepEntry->second.getInst())
1515 // Remove this local dependency info.
1516 LocalDeps.erase(LocalDepEntry);
1519 // If we have any cached dependencies on this instruction, remove
1522 // If the instruction is a pointer, remove it from both the load info and the
1525 removeCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst,
false));
1526 removeCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst,
true));
1528 // Otherwise, if the instructions is in the map directly, it must be a load.
1530 auto toRemoveIt = NonLocalDefsCache.find(RemInst);
1531 if (toRemoveIt != NonLocalDefsCache.end()) {
1533 "only load instructions should be added directly");
1534 const Instruction *DepV = toRemoveIt->second.getResult().getInst();
1535 ReverseNonLocalDefsCache.find(DepV)->second.erase(RemInst);
1536 NonLocalDefsCache.erase(toRemoveIt);
1540 // Loop over all of the things that depend on the instruction we're removing.
1543 // If we find RemInst as a clobber or Def in any of the maps for other values,
1544 // we need to replace its entry with a dirty version of the instruction after
1545 // it. If RemInst is a terminator, we use a null dirty value.
1547 // Using a dirty version of the instruction after RemInst saves having to scan
1548 // the entire block to get to this point.
1551 NewDirtyVal = MemDepResult::getDirty(&*++RemInst->
getIterator());
1553 ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
1554 if (ReverseDepIt != ReverseLocalDeps.end()) {
1555 // RemInst can't be the terminator if it has local stuff depending on it.
1557 "Nothing can locally depend on a terminator");
1559 for (
Instruction *InstDependingOnRemInst : ReverseDepIt->second) {
1560 assert(InstDependingOnRemInst != RemInst &&
1561 "Already removed our local dep info");
1563 LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
1565 // Make sure to remember that new things depend on NewDepInst.
1567 "There is no way something else can have "
1568 "a local dep on this if it is a terminator!");
1570 std::make_pair(NewDirtyVal.
getInst(), InstDependingOnRemInst));
1573 ReverseLocalDeps.erase(ReverseDepIt);
1575 // Add new reverse deps after scanning the set, to avoid invalidating the
1576 // 'ReverseDeps' reference.
1577 while (!ReverseDepsToAdd.
empty()) {
1578 ReverseLocalDeps[ReverseDepsToAdd.
back().first].insert(
1579 ReverseDepsToAdd.
back().second);
1584 ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
1585 if (ReverseDepIt != ReverseNonLocalDeps.end()) {
1587 assert(
I != RemInst &&
"Already removed NonLocalDep info for RemInst");
1589 PerInstNLInfo &INLD = NonLocalDepsMap[
I];
1590 // The information is now dirty!
1593 for (
auto &Entry : INLD.first) {
1594 if (Entry.getResult().getInst() != RemInst)
1597 // Convert to a dirty entry for the subsequent instruction.
1598 Entry.setResult(NewDirtyVal);
1601 ReverseDepsToAdd.
push_back(std::make_pair(NextI,
I));
1605 ReverseNonLocalDeps.erase(ReverseDepIt);
1607 // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
1608 while (!ReverseDepsToAdd.
empty()) {
1609 ReverseNonLocalDeps[ReverseDepsToAdd.
back().first].insert(
1610 ReverseDepsToAdd.
back().second);
1615 // If the instruction is in ReverseNonLocalPtrDeps then it appears as a
1616 // value in the NonLocalPointerDeps info.
1617 ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
1618 ReverseNonLocalPtrDeps.find(RemInst);
1619 if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
1621 ReversePtrDepsToAdd;
1623 for (ValueIsLoadPair
P : ReversePtrDepIt->second) {
1624 assert(
P.getPointer() != RemInst &&
1625 "Already removed NonLocalPointerDeps info for RemInst");
1627 auto &NLPD = NonLocalPointerDeps[
P];
1631 // The cache is not valid for any specific block anymore.
1632 NLPD.Pair = BBSkipFirstBlockPair();
1634 // Update any entries for RemInst to use the instruction after it.
1635 for (
auto &Entry : NLPDI) {
1636 if (Entry.getResult().getInst() != RemInst)
1639 // Convert to a dirty entry for the subsequent instruction.
1640 Entry.setResult(NewDirtyVal);
1643 ReversePtrDepsToAdd.
push_back(std::make_pair(NewDirtyInst,
P));
1646 // Re-sort the NonLocalDepInfo. Changing the dirty entry to its
1647 // subsequent value may invalidate the sortedness.
1651 ReverseNonLocalPtrDeps.
erase(ReversePtrDepIt);
1653 while (!ReversePtrDepsToAdd.
empty()) {
1654 ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.
back().first].insert(
1655 ReversePtrDepsToAdd.
back().second);
1660 assert(!NonLocalDepsMap.count(RemInst) &&
"RemInst got reinserted?");
1664/// Verify that the specified instruction does not occur in our internal data
1667/// This function verifies by asserting in debug builds.
1668void MemoryDependenceResults::verifyRemoved(
Instruction *
D)
const {
1670 for (
const auto &DepKV : LocalDeps) {
1671 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1672 assert(DepKV.second.getInst() !=
D &&
"Inst occurs in data structures");
1675 for (
const auto &DepKV : NonLocalPointerDeps) {
1676 assert(DepKV.first.getPointer() !=
D &&
"Inst occurs in NLPD map key");
1677 for (
const auto &Entry : DepKV.second.NonLocalDeps)
1678 assert(Entry.getResult().getInst() !=
D &&
"Inst occurs as NLPD value");
1681 for (
const auto &DepKV : NonLocalDepsMap) {
1682 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1683 const PerInstNLInfo &INLD = DepKV.second;
1684 for (
const auto &Entry : INLD.first)
1686 "Inst occurs in data structures");
1689 for (
const auto &DepKV : ReverseLocalDeps) {
1690 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1691 for (Instruction *Inst : DepKV.second)
1692 assert(Inst !=
D &&
"Inst occurs in data structures");
1695 for (
const auto &DepKV : ReverseNonLocalDeps) {
1696 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1697 for (Instruction *Inst : DepKV.second)
1698 assert(Inst !=
D &&
"Inst occurs in data structures");
1701 for (
const auto &DepKV : ReverseNonLocalPtrDeps) {
1702 assert(DepKV.first !=
D &&
"Inst occurs in rev NLPD map");
1704 for (ValueIsLoadPair
P : DepKV.second)
1705 assert(
P != ValueIsLoadPair(
D,
false) &&
P != ValueIsLoadPair(
D,
true) &&
1706 "Inst occurs in ReverseNonLocalPtrDeps map");
1728 "Memory Dependence Analysis",
false,
true)
1753 FunctionAnalysisManager::Invalidator &Inv) {
1754 // Check whether our analysis is preserved.
1757 // If not, give up now.
1760 // Check whether the analyses we depend on became invalid for any reason.
1766 // Otherwise this analysis result remains valid.
1771 return DefaultBlockScanLimit;
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static bool isLoad(int Opcode)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Atomic ordering constants.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This file defines the DenseMap class.
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static const unsigned int NumResultsLimit
static cl::opt< unsigned > CacheGlobalLimit("memdep-cache-global-limit", cl::Hidden, cl::init(10000), cl::desc("The max number of entries allowed in a cache (default = 10000)"))
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 cl::opt< unsigned > BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(200), cl::desc("The number of blocks to scan during memory " "dependency analysis (default = 200)"))
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.
static bool canSkipClobberingStore(const StoreInst *SI, const MemoryLocation &MemLoc, Align MemLocAlign, BatchAAResults &BatchAA, unsigned ScanLimit)
static cl::opt< unsigned > BlockScanLimit("memdep-block-scan-limit", cl::Hidden, cl::init(100), cl::desc("The number of instructions to scan in a block in memory " "dependency analysis (default = 100)"))
This file provides utility analysis objects describing memory locations.
static bool isOrdered(const Instruction *I)
static bool isInvariantLoad(const LoadInst *LI, const bool IsKernelFn)
uint64_t IntrinsicInst * II
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
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)
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....
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.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
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.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
An instruction for ordering other memory operations.
const BasicBlock & getEntryBlock() const
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()
TypeSize getValue() const
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 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.
MemoryDependenceResults run(Function &F, FunctionAnalysisManager &AM)
MemoryDependenceAnalysis()
Provides a lazy, caching interface for making common memory aliasing information queries,...
MemDepResult getSimplePointerDependencyFrom(const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst, unsigned *Limit, BatchAAResults &BatchAA)
std::vector< NonLocalDepEntry > NonLocalDepInfo
void invalidateCachedPredecessors()
Clears the PredIteratorCache info.
void invalidateCachedPointerInfo(Value *Ptr)
Invalidates cached information about the specified pointer, because it may be too conservative in mem...
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.
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB)
This analysis looks for other loads and stores with invariant.group metadata and the same pointer ope...
unsigned getDefaultBlockScanLimit() const
Some methods limit the number of instructions they will examine.
MemDepResult getDependency(Instruction *QueryInst)
Returns the instruction on which a memory operation depends.
const NonLocalDepInfo & getNonLocalCallDependency(CallBase *QueryCall)
Perform a full dependency query for the specified call, returning the set of blocks that the value is...
void getNonLocalPointerDependency(Instruction *QueryInst, SmallVectorImpl< NonLocalDepResult > &Result)
Perform a full dependency query for an access to the QueryInst's specified memory location,...
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.
~MemoryDependenceWrapperPass() override
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.
MemoryDependenceWrapperPass()
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 ...
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.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
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.
A Use represents the edge between a Value definition and its users.
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI Align getPointerAlignment(const DataLayout &DL) const
Returns an alignment of the pointer value.
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
iterator_range< use_iterator > uses()
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
const ParentTy * getParent() const
self_iterator getIterator()
Abstract Attribute helper functions.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ BasicBlock
Various leaf nodes.
initializer< Ty > init(const Ty &Val)
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
FunctionAddr VTableAddr Value
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
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.
auto dyn_cast_or_null(const Y &Val)
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
auto reverse(ContainerTy &&C)
bool isModSet(const ModRefInfo MRI)
void sort(IteratorTy Start, IteratorTy End)
FunctionAddr VTableAddr Count
bool isModOrRefSet(const ModRefInfo MRI)
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
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...
AtomicOrdering
Atomic ordering for LLVM's memory model.
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
@ Ref
The access may reference the value stored in memory.
@ ModRef
The access may reference and may modify the value stored in memory.
@ Mod
The access may modify the value stored in memory.
@ NoModRef
The access neither references nor modifies the value stored in memory.
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.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isNoModRef(const ModRefInfo MRI)
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.
A special type used by analysis passes to provide an address that identifies that particular analysis...