Lines Matching +full:de +full:- +full:asserting
1 //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation -------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
14 //===----------------------------------------------------------------------===//
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");
74 "memdep-block-scan-limit", cl::Hidden, cl::init(100),
79 BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(200),
96 bool Found = InstIt->second.erase(Val); in RemoveFromReverseMap()
99 if (InstIt->second.empty()) in RemoveFromReverseMap()
111 if (LI->isUnordered()) { in GetLocation()
115 if (LI->getOrdering() == AtomicOrdering::Monotonic) { in GetLocation()
124 if (SI->isUnordered()) { in GetLocation()
128 if (SI->getOrdering() == AtomicOrdering::Monotonic) { in GetLocation()
150 switch (II->getIntrinsicID()) { in GetLocation()
174 // Otherwise, just do the coarse-grained thing that always works. in GetLocation()
175 if (Inst->mayWriteToMemory()) in GetLocation()
177 if (Inst->mayReadFromMemory()) in GetLocation()
189 while (ScanIt != BB->begin()) { in getCallDependencyFrom()
190 Instruction *Inst = &*--ScanIt; in getCallDependencyFrom()
197 --Limit; in getCallDependencyFrom()
217 Call->isIdenticalToWhenDefined(CallB)) in getCallDependencyFrom()
234 // unknown, otherwise it is non-local. in getCallDependencyFrom()
235 if (BB != &BB->getParent()->getEntryBlock()) in getCallDependencyFrom()
257 // Non-local invariant group dependency indicates there is non local Def in getPointerDependencyFrom()
280 if (!LI->hasMetadata(LLVMContext::MD_invariant_group)) in getInvariantGroupPointerDependency()
285 Value *LoadOperand = LI->getPointerOperand()->stripPointerCasts(); in getInvariantGroupPointerDependency()
315 for (const Use &Us : Ptr->uses()) { in getInvariantGroupPointerDependency()
332 if (GEP->hasAllZeroIndices()) { in getInvariantGroupPointerDependency()
342 cast<StoreInst>(U)->getPointerOperand() == Ptr)) && in getInvariantGroupPointerDependency()
343 U->hasMetadata(LLVMContext::MD_invariant_group)) in getInvariantGroupPointerDependency()
350 if (ClosestDependency->getParent() == BB) in getInvariantGroupPointerDependency()
352 // Def(U) can't be returned here because it is non-local. If local in getInvariantGroupPointerDependency()
357 LI, NonLocalDepResult(ClosestDependency->getParent(), in getInvariantGroupPointerDependency()
378 if (std::min(MemLocAlign, SI->getAlign()).value() < in canSkipClobberingStore()
382 auto *LI = dyn_cast<LoadInst>(SI->getValueOperand()); in canSkipClobberingStore()
383 if (!LI || LI->getParent() != SI->getParent()) in canSkipClobberingStore()
388 for (const Instruction *I = LI; I != SI; I = I->getNextNonDebugInstruction()) in canSkipClobberingStore()
402 MemLoc.Ptr->getPointerAlignment(BB->getDataLayout()); in getSimplePointerDependencyFrom()
410 // QueryInst is not a simple (non-atomic) memory access, we automatically in getSimplePointerDependencyFrom()
414 // memory model" in PLDI 2013, that a non-atomic location can only be in getSimplePointerDependencyFrom()
442 if (LI->hasMetadata(LLVMContext::MD_invariant_load)) in getSimplePointerDependencyFrom()
444 MemLocAlign = LI->getAlign(); in getSimplePointerDependencyFrom()
450 auto isComplexForReordering = [](Instruction * I, AtomicOrdering AO)->bool { in getSimplePointerDependencyFrom()
451 if (I->isVolatile()) in getSimplePointerDependencyFrom()
454 return isStrongerThan(LI->getOrdering(), AO); in getSimplePointerDependencyFrom()
456 return isStrongerThan(SI->getOrdering(), AO); in getSimplePointerDependencyFrom()
457 return I->mayReadOrWriteMemory(); in getSimplePointerDependencyFrom()
461 while (ScanIt != BB->begin()) { in getSimplePointerDependencyFrom()
462 Instruction *Inst = &*--ScanIt; in getSimplePointerDependencyFrom()
471 --*Limit; in getSimplePointerDependencyFrom()
478 Intrinsic::ID ID = II->getIntrinsicID(); in getSimplePointerDependencyFrom()
481 // FIXME: This only considers queries directly on the invariant-tagged in getSimplePointerDependencyFrom()
485 MemoryLocation ArgLoc = MemoryLocation::getAfter(II->getArgOperand(1)); in getSimplePointerDependencyFrom()
513 // non-aliasing locations, as normal accesses, for example, can be safely in getSimplePointerDependencyFrom()
515 if (LI->isVolatile()) { in getSimplePointerDependencyFrom()
519 if (QueryInst->isVolatile()) in getSimplePointerDependencyFrom()
529 if (LI->isAtomic() && isStrongerThanUnordered(LI->getOrdering())) { in getSimplePointerDependencyFrom()
533 if (LI->getOrdering() != AtomicOrdering::Monotonic) in getSimplePointerDependencyFrom()
557 // Random may-alias loads don't depend on each other without a in getSimplePointerDependencyFrom()
562 // Stores don't alias loads from read-only memory. in getSimplePointerDependencyFrom()
574 if (!SI->isUnordered() && SI->isAtomic()) { in getSimplePointerDependencyFrom()
579 // QueryInst is a non-atomic or unordered load/store. in getSimplePointerDependencyFrom()
584 // Monotonic and Release semantic allows re-ordering before store in getSimplePointerDependencyFrom()
586 // re-ordering in case locations are may or must alias. in getSimplePointerDependencyFrom()
590 // non-aliasing locations, as normal accesses can for example be reordered in getSimplePointerDependencyFrom()
592 if (SI->isVolatile()) in getSimplePointerDependencyFrom()
593 if (!QueryInst || QueryInst->isVolatile()) in getSimplePointerDependencyFrom()
647 if (isLoad && FI->getOrdering() == AtomicOrdering::Release) in getSimplePointerDependencyFrom()
670 // unknown, otherwise it is non-local. in getSimplePointerDependencyFrom()
671 if (BB != &BB->getParent()->getEntryBlock()) in getSimplePointerDependencyFrom()
683 // If the cached entry is non-dirty, just return it. Note that this depends in getDependency()
696 BasicBlock *QueryParent = QueryInst->getParent(); in getDependency()
699 if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) { in getDependency()
701 // unknown, otherwise it is non-local. in getDependency()
702 if (QueryParent != &QueryParent->getParent()->getEntryBlock()) in getDependency()
713 isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start; in getDependency()
716 getPointerDependencyFrom(MemLoc, isLoad, ScanPos->getIterator(), in getDependency()
721 ScanPos->getIterator(), QueryParent); in getDependency()
723 // Non-memory instruction. in getDependency()
735 /// This method is used when -debug is specified to verify that cache arrays
738 int Count = -1) { in AssertSorted()
739 if (Count == -1) in AssertSorted()
750 "non-local deps!"); in getNonLocalCallDependency()
779 BasicBlock *QueryBB = QueryCall->getParent(); in getNonLocalCallDependency()
784 // isReadonlyCall - If this is a read-only call, we can be more aggressive. in getNonLocalCallDependency()
806 if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB) in getNonLocalCallDependency()
807 --Entry; in getNonLocalCallDependency()
811 Entry->getBB() == DirtyBB) { in getNonLocalCallDependency()
814 if (!Entry->getResult().isDirty()) in getNonLocalCallDependency()
823 BasicBlock::iterator ScanPos = DirtyBB->end(); in getNonLocalCallDependency()
825 if (Instruction *Inst = ExistingResult->getResult().getInst()) { in getNonLocalCallDependency()
826 ScanPos = Inst->getIterator(); in getNonLocalCallDependency()
836 if (ScanPos != DirtyBB->begin()) { in getNonLocalCallDependency()
838 } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) { in getNonLocalCallDependency()
849 ExistingResult->setResult(Dep); in getNonLocalCallDependency()
875 BasicBlock *FromBB = QueryInst->getParent(); in getNonLocalPointerDependency()
878 assert(Loc.Ptr->getType()->isPointerTy() && in getNonLocalPointerDependency()
879 "Can't get pointer deps of a non-pointer!"); in getNonLocalPointerDependency()
885 Result.push_back(NonLocalDefIt->second); in getNonLocalPointerDependency()
886 ReverseNonLocalDefsCache[NonLocalDefIt->second.getResult().getInst()] in getNonLocalPointerDependency()
895 // non-volatile accesses. in getNonLocalPointerDependency()
902 return !LI->isUnordered(); in getNonLocalPointerDependency()
904 return !SI->isUnordered(); in getNonLocalPointerDependency()
908 if (QueryInst->isVolatile() || isOrdered(QueryInst)) { in getNonLocalPointerDependency()
913 const DataLayout &DL = FromBB->getDataLayout(); in getNonLocalPointerDependency()
942 isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load); in getNonLocalInfoForBlock()
947 Cache->begin(), Cache->begin() + NumSortedEntries, NonLocalDepEntry(BB)); in getNonLocalInfoForBlock()
948 if (Entry != Cache->begin() && (Entry - 1)->getBB() == BB) in getNonLocalInfoForBlock()
949 --Entry; in getNonLocalInfoForBlock()
952 if (Entry != Cache->begin() + NumSortedEntries && Entry->getBB() == BB) in getNonLocalInfoForBlock()
959 !ExistingResult->getResult().isNonFuncLocal()) in getNonLocalInfoForBlock()
962 // If we have a cached entry, and it is non-dirty, use it as the value for in getNonLocalInfoForBlock()
964 if (ExistingResult && !ExistingResult->getResult().isDirty()) { in getNonLocalInfoForBlock()
966 return ExistingResult->getResult(); in getNonLocalInfoForBlock()
972 BasicBlock::iterator ScanPos = BB->end(); in getNonLocalInfoForBlock()
973 if (ExistingResult && ExistingResult->getResult().getInst()) { in getNonLocalInfoForBlock()
974 assert(ExistingResult->getResult().getInst()->getParent() == BB && in getNonLocalInfoForBlock()
977 ScanPos = ExistingResult->getResult().getInst()->getIterator(); in getNonLocalInfoForBlock()
997 ExistingResult->setResult(Dep); in getNonLocalInfoForBlock()
999 Cache->push_back(NonLocalDepEntry(BB, Dep)); in getNonLocalInfoForBlock()
1023 switch (Cache.size() - NumSortedEntries) { in SortNonLocalDepInfoCache()
1032 std::upper_bound(Cache.begin(), Cache.end() - 1, Val); in SortNonLocalDepInfoCache()
1085 isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load); in getNonLocalPointerDepFromBB()
1091 NonLocalPointerInfo *CacheInfo = &Pair.first->second; in getNonLocalPointerDepFromBB()
1097 if (CacheInfo->Size != Loc.Size) { in getNonLocalPointerDepFromBB()
1099 if (CacheInfo->Size.hasValue() && Loc.Size.hasValue()) { in getNonLocalPointerDepFromBB()
1104 CacheInfo->Size.isPrecise() != Loc.Size.isPrecise() || in getNonLocalPointerDepFromBB()
1105 !TypeSize::isKnownGE(CacheInfo->Size.getValue(), in getNonLocalPointerDepFromBB()
1115 CacheInfo->Pair = BBSkipFirstBlockPair(); in getNonLocalPointerDepFromBB()
1116 CacheInfo->Size = Loc.Size; in getNonLocalPointerDepFromBB()
1117 for (auto &Entry : CacheInfo->NonLocalDeps) in getNonLocalPointerDepFromBB()
1120 CacheInfo->NonLocalDeps.clear(); in getNonLocalPointerDepFromBB()
1129 QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad, in getNonLocalPointerDepFromBB()
1137 if (CacheInfo->AATags != Loc.AATags) { in getNonLocalPointerDepFromBB()
1138 if (CacheInfo->AATags) { in getNonLocalPointerDepFromBB()
1139 CacheInfo->Pair = BBSkipFirstBlockPair(); in getNonLocalPointerDepFromBB()
1140 CacheInfo->AATags = AAMDNodes(); in getNonLocalPointerDepFromBB()
1141 for (auto &Entry : CacheInfo->NonLocalDeps) in getNonLocalPointerDepFromBB()
1144 CacheInfo->NonLocalDeps.clear(); in getNonLocalPointerDepFromBB()
1157 NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps; in getNonLocalPointerDepFromBB()
1162 // non-invariant loads only. in getNonLocalPointerDepFromBB()
1164 CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) { in getNonLocalPointerDepFromBB()
1174 if (VI == Visited.end() || VI->second == Pointer.getAddr()) in getNonLocalPointerDepFromBB()
1179 // non-fully cached query, but there is little point in doing this. in getNonLocalPointerDepFromBB()
1208 if (!IsIncomplete && Cache->empty()) in getNonLocalPointerDepFromBB()
1209 CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock); in getNonLocalPointerDepFromBB()
1211 CacheInfo->Pair = BBSkipFirstBlockPair(); in getNonLocalPointerDepFromBB()
1225 unsigned NumSortedEntries = Cache->size(); in getNonLocalPointerDepFromBB()
1240 if (Cache && NumSortedEntries != Cache->size()) { in getNonLocalPointerDepFromBB()
1247 CacheInfo->Pair = BBSkipFirstBlockPair(); in getNonLocalPointerDepFromBB()
1292 if (InsertRes.first->second != Pointer.getAddr()) { in getNonLocalPointerDepFromBB()
1308 WorklistEntries -= NewBlocks.size(); in getNonLocalPointerDepFromBB()
1323 if (Cache && NumSortedEntries != Cache->size()) { in getNonLocalPointerDepFromBB()
1325 NumSortedEntries = Cache->size(); in getNonLocalPointerDepFromBB()
1353 if (InsertRes.first->second == PredPtrVal) in getNonLocalPointerDepFromBB()
1416 Cache = &CacheInfo->NonLocalDeps; in getNonLocalPointerDepFromBB()
1417 NumSortedEntries = Cache->size(); in getNonLocalPointerDepFromBB()
1423 CacheInfo->Pair = BBSkipFirstBlockPair(); in getNonLocalPointerDepFromBB()
1435 Cache = &CacheInfo->NonLocalDeps; in getNonLocalPointerDepFromBB()
1436 NumSortedEntries = Cache->size(); in getNonLocalPointerDepFromBB()
1443 CacheInfo->Pair = BBSkipFirstBlockPair(); in getNonLocalPointerDepFromBB()
1476 // Okay, we're done now. If we added new values to the cache, re-sort it. in getNonLocalPointerDepFromBB()
1491 it->second.getResult().getInst(), P.getPointer()); in removeCachedNonLocalPointerDependencies()
1498 for (const auto *entry : toRemoveIt->second) in removeCachedNonLocalPointerDependencies()
1509 // Remove all of the entries in the BB->val map. This involves removing in removeCachedNonLocalPointerDependencies()
1511 NonLocalDepInfo &PInfo = It->second.NonLocalDeps; in removeCachedNonLocalPointerDependencies()
1513 for (const NonLocalDepEntry &DE : PInfo) { in removeCachedNonLocalPointerDependencies() local
1514 Instruction *Target = DE.getResult().getInst(); in removeCachedNonLocalPointerDependencies()
1516 continue; // Ignore non-local dep results. in removeCachedNonLocalPointerDependencies()
1517 assert(Target->getParent() == DE.getBB()); in removeCachedNonLocalPointerDependencies()
1529 if (!Ptr->getType()->isPointerTy()) in invalidateCachedPointerInfo()
1544 // Walk through the Non-local dependencies, removing this one as the value in removeInstruction()
1548 NonLocalDepInfo &BlockMap = NLDI->second.first; in removeInstruction()
1559 if (Instruction *Inst = LocalDepEntry->second.getInst()) in removeInstruction()
1571 if (RemInst->getType()->isPointerTy()) { in removeInstruction()
1581 const Instruction *DepV = toRemoveIt->second.getResult().getInst(); in removeInstruction()
1582 ReverseNonLocalDefsCache.find(DepV)->second.erase(RemInst); in removeInstruction()
1597 if (!RemInst->isTerminator()) in removeInstruction()
1598 NewDirtyVal = MemDepResult::getDirty(&*++RemInst->getIterator()); in removeInstruction()
1603 assert(!ReverseDepIt->second.empty() && !RemInst->isTerminator() && in removeInstruction()
1606 for (Instruction *InstDependingOnRemInst : ReverseDepIt->second) { in removeInstruction()
1633 for (Instruction *I : ReverseDepIt->second) { in removeInstruction()
1670 for (ValueIsLoadPair P : ReversePtrDepIt->second) { in removeInstruction()
1691 // Re-sort the NonLocalDepInfo. Changing the dirty entry to its in removeInstruction()
1712 /// This function verifies by asserting in debug builds.