57#define DEBUG_TYPE "memdep"
59STATISTIC(NumCacheNonLocal,
"Number of fully cached non-local responses");
60STATISTIC(NumCacheDirtyNonLocal,
"Number of dirty cached non-local responses");
61STATISTIC(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");
67STATISTIC(NumUncacheNonLocalPtr,
"Number of uncached non-local ptr responses");
69 "Number of block queries that were completely cached");
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)"));
89template <
typename KeyTy>
94 ReverseMap.
find(Inst);
95 assert(InstIt != ReverseMap.
end() &&
"Reverse map out of sync?");
96 bool Found = InstIt->second.
erase(Val);
97 assert(Found &&
"Invalid reverse map!");
99 if (InstIt->second.
empty())
100 ReverseMap.erase(InstIt);
110 if (
const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
111 if (LI->isUnordered()) {
113 return ModRefInfo::Ref;
115 if (LI->getOrdering() == AtomicOrdering::Monotonic) {
117 return ModRefInfo::ModRef;
120 return ModRefInfo::ModRef;
123 if (
const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
124 if (SI->isUnordered()) {
126 return ModRefInfo::Mod;
128 if (SI->getOrdering() == AtomicOrdering::Monotonic) {
130 return ModRefInfo::ModRef;
133 return ModRefInfo::ModRef;
136 if (
const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
138 return ModRefInfo::ModRef;
141 if (
const CallBase *CB = dyn_cast<CallBase>(Inst)) {
145 return ModRefInfo::Mod;
149 if (
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
150 switch (II->getIntrinsicID()) {
151 case Intrinsic::lifetime_start:
152 case Intrinsic::lifetime_end:
153 case Intrinsic::invariant_start:
157 return ModRefInfo::Mod;
158 case Intrinsic::invariant_end:
162 return ModRefInfo::Mod;
163 case Intrinsic::masked_load:
165 return ModRefInfo::Ref;
166 case Intrinsic::masked_store:
168 return ModRefInfo::Mod;
176 return ModRefInfo::ModRef;
178 return ModRefInfo::Ref;
179 return ModRefInfo::NoModRef;
183MemDepResult MemoryDependenceResults::getCallDependencyFrom(
189 while (ScanIt != BB->
begin()) {
192 if (isa<DbgInfoIntrinsic>(Inst))
211 if (
auto *CallB = dyn_cast<CallBase>(Inst)) {
216 if (isReadOnlyCall && !
isModSet(MR) &&
217 Call->isIdenticalToWhenDefined(CallB))
245 if (QueryInst !=
nullptr) {
246 if (
auto *LI = dyn_cast<LoadInst>(QueryInst)) {
249 if (InvariantGroupDependency.
isDef())
250 return InvariantGroupDependency;
254 MemLoc,
isLoad, ScanIt, BB, QueryInst, Limit, BatchAA);
255 if (SimpleDep.
isDef())
261 return InvariantGroupDependency;
264 "InvariantGroupDependency should be only unknown at this point");
280 if (!LI->
hasMetadata(LLVMContext::MD_invariant_group))
291 if (isa<GlobalValue>(LoadOperand))
296 LoadOperandsQueue.
push_back(LoadOperand);
302 assert(
Other &&
"Must call it with not null instruction");
310 while (!LoadOperandsQueue.
empty()) {
313 "Null or GlobalValue should not be inserted");
315 for (
const Use &Us :
Ptr->uses()) {
316 auto *U = dyn_cast<Instruction>(Us.getUser());
317 if (!U || U == LI || !DT.
dominates(U, LI))
322 if (isa<BitCastInst>(U)) {
331 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(U))
332 if (
GEP->hasAllZeroIndices()) {
340 if ((isa<LoadInst>(U) ||
341 (isa<StoreInst>(U) &&
343 U->hasMetadata(LLVMContext::MD_invariant_group))
344 ClosestDependency = GetClosestDependency(ClosestDependency, U);
348 if (!ClosestDependency)
350 if (ClosestDependency->
getParent() == BB)
356 NonLocalDefsCache.try_emplace(
359 ReverseNonLocalDefsCache[ClosestDependency].
insert(LI);
371 unsigned ScanLimit) {
378 if (std::min(MemLocAlign, SI->getAlign()).value() <
382 auto *LI = dyn_cast<LoadInst>(SI->getValueOperand());
383 if (!LI || LI->getParent() != SI->getParent())
387 unsigned NumVisitedInsts = 0;
388 for (
const Instruction *
I = LI;
I != SI;
I =
I->getNextNonDebugInstruction())
389 if (++NumVisitedInsts > ScanLimit ||
400 bool isInvariantLoad =
false;
406 Limit = &DefaultLimit;
441 if (
LoadInst *LI = dyn_cast<LoadInst>(QueryInst)) {
442 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
443 isInvariantLoad =
true;
444 MemLocAlign = LI->getAlign();
453 if (
auto *LI = dyn_cast<LoadInst>(
I))
455 if (
auto *SI = dyn_cast<StoreInst>(
I))
457 return I->mayReadOrWriteMemory();
461 while (ScanIt != BB->
begin()) {
466 if (isa<DbgInfoIntrinsic>(II))
480 case Intrinsic::lifetime_start: {
490 case Intrinsic::masked_load:
491 case Intrinsic::masked_store: {
499 if (
ID == Intrinsic::masked_load)
511 if (
LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
515 if (LI->isVolatile()) {
553 ClobberOffsets[LI] = R.getOffset();
570 if (
StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
574 if (!SI->isUnordered() && SI->isAtomic()) {
592 if (SI->isVolatile())
629 if (AccessPtr == Inst || BatchAA.
isMustAlias(Inst, AccessPtr))
635 if (isa<SelectInst>(Inst) && MemLoc.
Ptr == Inst)
646 if (
FenceInst *FI = dyn_cast<FenceInst>(Inst))
677 ClobberOffsets.
clear();
685 if (!LocalCache.isDirty())
712 if (
auto *II = dyn_cast<IntrinsicInst>(QueryInst))
713 isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
717 QueryParent, QueryInst,
nullptr);
718 }
else if (
auto *QueryCall = dyn_cast<CallBase>(QueryInst)) {
720 LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,
729 ReverseLocalDeps[
I].
insert(QueryInst);
740 Count = Cache.size();
741 assert(std::is_sorted(Cache.begin(), Cache.begin() + Count) &&
742 "Cache isn't sorted!");
749 "getNonLocalCallDependency should only be used on calls with "
751 PerInstNLInfo &CacheP = NonLocalDepsMap[QueryCall];
759 if (!Cache.empty()) {
762 if (!CacheP.second) {
769 for (
auto &Entry : Cache)
770 if (Entry.getResult().isDirty())
776 ++NumCacheDirtyNonLocal;
781 ++NumUncacheNonLocal;
789 unsigned NumSortedEntries = Cache.
size();
793 while (!DirtyBlocks.
empty()) {
797 if (!Visited.
insert(DirtyBB).second)
803 NonLocalDepInfo::iterator Entry =
804 std::upper_bound(Cache.begin(), Cache.begin() + NumSortedEntries,
806 if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB)
810 if (Entry != Cache.begin() + NumSortedEntries &&
811 Entry->getBB() == DirtyBB) {
814 if (!Entry->getResult().isDirty())
818 ExistingResult = &*Entry;
824 if (ExistingResult) {
828 RemoveFromReverseMap<Instruction *>(ReverseNonLocalDeps, Inst,
836 if (ScanPos != DirtyBB->
begin()) {
837 Dep = getCallDependencyFrom(QueryCall, isReadonlyCall, ScanPos, DirtyBB);
859 ReverseNonLocalDeps[Inst].
insert(QueryCall);
874 bool isLoad = isa<LoadInst>(QueryInst);
879 "Can't get pointer deps of a non-pointer!");
883 auto NonLocalDefIt = NonLocalDefsCache.find(QueryInst);
884 if (NonLocalDefIt != NonLocalDefsCache.end()) {
885 Result.push_back(NonLocalDefIt->second);
886 ReverseNonLocalDefsCache[NonLocalDefIt->second.getResult().getInst()]
888 NonLocalDefsCache.erase(NonLocalDefIt);
901 if (
LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
902 return !LI->isUnordered();
903 }
else if (
StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
904 return !SI->isUnordered();
921 if (getNonLocalPointerDepFromBB(QueryInst,
Address, Loc,
isLoad, FromBB,
922 Result, Visited,
true))
934MemDepResult MemoryDependenceResults::getNonLocalInfoForBlock(
936 BasicBlock *BB, NonLocalDepInfo *Cache,
unsigned NumSortedEntries,
939 bool isInvariantLoad =
false;
941 if (
LoadInst *LI = dyn_cast_or_null<LoadInst>(QueryInst))
942 isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);
946 NonLocalDepInfo::iterator Entry = std::upper_bound(
948 if (Entry != Cache->begin() && (Entry - 1)->getBB() == BB)
952 if (Entry != Cache->begin() + NumSortedEntries && Entry->getBB() == BB)
953 ExistingResult = &*Entry;
958 if (ExistingResult && isInvariantLoad &&
960 ExistingResult =
nullptr;
964 if (ExistingResult && !ExistingResult->
getResult().isDirty()) {
965 ++NumCacheNonLocalPtr;
975 "Instruction invalidated?");
976 ++NumCacheDirtyNonLocalPtr;
980 ValueIsLoadPair CacheKey(Loc.
Ptr,
isLoad);
983 ++NumUncacheNonLocalPtr;
988 QueryInst,
nullptr, BatchAA);
1010 assert(Inst &&
"Didn't depend on anything?");
1011 ValueIsLoadPair CacheKey(Loc.
Ptr,
isLoad);
1012 ReverseNonLocalPtrDeps[Inst].
insert(CacheKey);
1022 unsigned NumSortedEntries) {
1023 switch (Cache.size() - NumSortedEntries) {
1031 MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
1032 std::upper_bound(Cache.begin(), Cache.end() - 1, Val);
1033 Cache.insert(Entry, Val);
1038 if (Cache.size() != 1) {
1041 MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
1043 Cache.insert(Entry, Val);
1066bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
1071 bool IsIncomplete) {
1079 NonLocalPointerInfo InitialNLPI;
1080 InitialNLPI.Size = Loc.
Size;
1081 InitialNLPI.AATags = Loc.
AATags;
1083 bool isInvariantLoad =
false;
1084 if (
LoadInst *LI = dyn_cast_or_null<LoadInst>(QueryInst))
1085 isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);
1089 std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
1090 NonLocalPointerDeps.
insert(std::make_pair(CacheKey, InitialNLPI));
1091 NonLocalPointerInfo *CacheInfo = &Pair.first->second;
1096 if (!isInvariantLoad && !Pair.second) {
1097 if (CacheInfo->Size != Loc.
Size) {
1098 bool ThrowOutEverything;
1099 if (CacheInfo->Size.hasValue() && Loc.
Size.
hasValue()) {
1103 ThrowOutEverything =
1112 if (ThrowOutEverything) {
1115 CacheInfo->Pair = BBSkipFirstBlockPair();
1116 CacheInfo->Size = Loc.
Size;
1117 for (
auto &Entry : CacheInfo->NonLocalDeps)
1118 if (
Instruction *Inst = Entry.getResult().getInst())
1120 CacheInfo->NonLocalDeps.clear();
1124 IsIncomplete =
true;
1128 return getNonLocalPointerDepFromBB(
1130 StartBB, Result, Visited, SkipFirstBlock, IsIncomplete);
1137 if (CacheInfo->AATags != Loc.
AATags) {
1138 if (CacheInfo->AATags) {
1139 CacheInfo->Pair = BBSkipFirstBlockPair();
1141 for (
auto &Entry : CacheInfo->NonLocalDeps)
1142 if (
Instruction *Inst = Entry.getResult().getInst())
1144 CacheInfo->NonLocalDeps.clear();
1148 IsIncomplete =
true;
1151 return getNonLocalPointerDepFromBB(
1153 Visited, SkipFirstBlock, IsIncomplete);
1163 if (!IsIncomplete && !isInvariantLoad &&
1164 CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
1170 if (!Visited.
empty()) {
1171 for (
auto &Entry : *Cache) {
1173 Visited.
find(Entry.getBB());
1174 if (VI == Visited.
end() ||
VI->second ==
Pointer.getAddr())
1185 for (
auto &Entry : *Cache) {
1186 Visited.
insert(std::make_pair(Entry.getBB(),
Addr));
1187 if (Entry.getResult().isNonLocal()) {
1196 ++NumCacheCompleteNonLocalPtr;
1207 if (!isInvariantLoad) {
1208 if (!IsIncomplete && Cache->empty())
1209 CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
1211 CacheInfo->Pair = BBSkipFirstBlockPair();
1225 unsigned NumSortedEntries = Cache->size();
1227 bool GotWorklistLimit =
false;
1231 while (!Worklist.
empty()) {
1240 if (Cache && NumSortedEntries != Cache->size()) {
1247 CacheInfo->Pair = BBSkipFirstBlockPair();
1252 if (!SkipFirstBlock) {
1255 assert(Visited.
count(BB) &&
"Should check 'visited' before adding to WL");
1261 QueryInst, Loc,
isLoad, BB, Cache, NumSortedEntries, BatchAA);
1276 if (!
Pointer.needsPHITranslationFromBlock(BB)) {
1277 SkipFirstBlock =
false;
1281 std::pair<DenseMap<BasicBlock *, Value *>::iterator,
bool> InsertRes =
1283 if (InsertRes.second) {
1292 if (InsertRes.first->second !=
Pointer.getAddr()) {
1295 for (
auto *NewBlock : NewBlocks)
1296 Visited.
erase(NewBlock);
1297 goto PredTranslationFailure;
1300 if (NewBlocks.
size() > WorklistEntries) {
1303 for (
auto *NewBlock : NewBlocks)
1304 Visited.
erase(NewBlock);
1305 GotWorklistLimit =
true;
1306 goto PredTranslationFailure;
1308 WorklistEntries -= NewBlocks.size();
1309 Worklist.
append(NewBlocks.begin(), NewBlocks.end());
1315 if (!
Pointer.isPotentiallyPHITranslatable())
1316 goto PredTranslationFailure;
1323 if (Cache && NumSortedEntries != Cache->size()) {
1325 NumSortedEntries = Cache->size();
1331 PredList.
push_back(std::make_pair(Pred, Pointer));
1344 std::pair<DenseMap<BasicBlock *, Value *>::iterator,
bool> InsertRes =
1345 Visited.
insert(std::make_pair(Pred, PredPtrVal));
1347 if (!InsertRes.second) {
1353 if (InsertRes.first->second == PredPtrVal)
1362 for (
const auto &Pred : PredList)
1363 Visited.
erase(Pred.first);
1365 goto PredTranslationFailure;
1374 for (
auto &
I : PredList) {
1379 bool CanTranslate =
true;
1385 CanTranslate =
false;
1395 if (!CanTranslate ||
1396 !getNonLocalPointerDepFromBB(QueryInst, PredPointer,
1398 Pred, Result, Visited)) {
1408 NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
1409 NLPI.Pair = BBSkipFirstBlockPair();
1415 CacheInfo = &NonLocalPointerDeps[CacheKey];
1416 Cache = &CacheInfo->NonLocalDeps;
1417 NumSortedEntries = Cache->size();
1423 CacheInfo->Pair = BBSkipFirstBlockPair();
1424 SkipFirstBlock =
false;
1427 PredTranslationFailure:
1434 CacheInfo = &NonLocalPointerDeps[CacheKey];
1435 Cache = &CacheInfo->NonLocalDeps;
1436 NumSortedEntries = Cache->size();
1443 CacheInfo->Pair = BBSkipFirstBlockPair();
1455 if (!isInvariantLoad) {
1457 if (
I.getBB() != BB)
1460 assert((GotWorklistLimit ||
I.getResult().isNonLocal() ||
1462 "Should only be here with transparent block");
1470 (void)GotWorklistLimit;
1483void MemoryDependenceResults::removeCachedNonLocalPointerDependencies(
1484 ValueIsLoadPair
P) {
1487 if (!NonLocalDefsCache.empty()) {
1488 auto it = NonLocalDefsCache.find(
P.getPointer());
1489 if (it != NonLocalDefsCache.end()) {
1491 it->second.getResult().getInst(),
P.getPointer());
1492 NonLocalDefsCache.erase(it);
1495 if (
auto *
I = dyn_cast<Instruction>(
P.getPointer())) {
1496 auto toRemoveIt = ReverseNonLocalDefsCache.
find(
I);
1497 if (toRemoveIt != ReverseNonLocalDefsCache.
end()) {
1498 for (
const auto *entry : toRemoveIt->second)
1499 NonLocalDefsCache.erase(entry);
1500 ReverseNonLocalDefsCache.
erase(toRemoveIt);
1506 if (It == NonLocalPointerDeps.
end())
1524 NonLocalPointerDeps.
erase(It);
1529 if (!
Ptr->getType()->isPointerTy())
1547 if (NLDI != NonLocalDepsMap.
end()) {
1549 for (
auto &Entry : BlockMap)
1550 if (
Instruction *Inst = Entry.getResult().getInst())
1552 NonLocalDepsMap.
erase(NLDI);
1557 if (LocalDepEntry != LocalDeps.
end()) {
1559 if (
Instruction *Inst = LocalDepEntry->second.getInst())
1563 LocalDeps.
erase(LocalDepEntry);
1572 removeCachedNonLocalPointerDependencies(
ValueIsLoadPair(RemInst,
false));
1573 removeCachedNonLocalPointerDependencies(
ValueIsLoadPair(RemInst,
true));
1577 auto toRemoveIt = NonLocalDefsCache.find(RemInst);
1578 if (toRemoveIt != NonLocalDefsCache.end()) {
1579 assert(isa<LoadInst>(RemInst) &&
1580 "only load instructions should be added directly");
1581 const Instruction *DepV = toRemoveIt->second.getResult().getInst();
1582 ReverseNonLocalDefsCache.
find(DepV)->second.erase(RemInst);
1583 NonLocalDefsCache.erase(toRemoveIt);
1598 NewDirtyVal = MemDepResult::getDirty(&*++RemInst->
getIterator());
1601 if (ReverseDepIt != ReverseLocalDeps.
end()) {
1604 "Nothing can locally depend on a terminator");
1606 for (
Instruction *InstDependingOnRemInst : ReverseDepIt->second) {
1607 assert(InstDependingOnRemInst != RemInst &&
1608 "Already removed our local dep info");
1610 LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
1614 "There is no way something else can have "
1615 "a local dep on this if it is a terminator!");
1617 std::make_pair(NewDirtyVal.
getInst(), InstDependingOnRemInst));
1620 ReverseLocalDeps.
erase(ReverseDepIt);
1624 while (!ReverseDepsToAdd.
empty()) {
1625 ReverseLocalDeps[ReverseDepsToAdd.
back().first].
insert(
1626 ReverseDepsToAdd.
back().second);
1631 ReverseDepIt = ReverseNonLocalDeps.
find(RemInst);
1632 if (ReverseDepIt != ReverseNonLocalDeps.
end()) {
1634 assert(
I != RemInst &&
"Already removed NonLocalDep info for RemInst");
1636 PerInstNLInfo &INLD = NonLocalDepsMap[
I];
1640 for (
auto &Entry : INLD.first) {
1641 if (Entry.getResult().getInst() != RemInst)
1645 Entry.setResult(NewDirtyVal);
1648 ReverseDepsToAdd.
push_back(std::make_pair(NextI,
I));
1652 ReverseNonLocalDeps.
erase(ReverseDepIt);
1655 while (!ReverseDepsToAdd.
empty()) {
1656 ReverseNonLocalDeps[ReverseDepsToAdd.
back().first].
insert(
1657 ReverseDepsToAdd.
back().second);
1665 ReverseNonLocalPtrDeps.
find(RemInst);
1666 if (ReversePtrDepIt != ReverseNonLocalPtrDeps.
end()) {
1668 ReversePtrDepsToAdd;
1671 assert(
P.getPointer() != RemInst &&
1672 "Already removed NonLocalPointerDeps info for RemInst");
1680 for (
auto &Entry : NLPDI) {
1681 if (Entry.getResult().getInst() != RemInst)
1685 Entry.setResult(NewDirtyVal);
1688 ReversePtrDepsToAdd.
push_back(std::make_pair(NewDirtyInst,
P));
1696 ReverseNonLocalPtrDeps.
erase(ReversePtrDepIt);
1698 while (!ReversePtrDepsToAdd.
empty()) {
1699 ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.
back().first].
insert(
1700 ReversePtrDepsToAdd.
back().second);
1705 assert(!NonLocalDepsMap.
count(RemInst) &&
"RemInst got reinserted?");
1713void MemoryDependenceResults::verifyRemoved(
Instruction *
D)
const {
1715 for (
const auto &DepKV : LocalDeps) {
1716 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1717 assert(DepKV.second.getInst() !=
D &&
"Inst occurs in data structures");
1720 for (
const auto &DepKV : NonLocalPointerDeps) {
1721 assert(DepKV.first.getPointer() !=
D &&
"Inst occurs in NLPD map key");
1722 for (
const auto &Entry : DepKV.second.NonLocalDeps)
1723 assert(Entry.getResult().getInst() !=
D &&
"Inst occurs as NLPD value");
1726 for (
const auto &DepKV : NonLocalDepsMap) {
1727 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1728 const PerInstNLInfo &INLD = DepKV.second;
1729 for (
const auto &Entry : INLD.first)
1730 assert(Entry.getResult().getInst() !=
D &&
1731 "Inst occurs in data structures");
1734 for (
const auto &DepKV : ReverseLocalDeps) {
1735 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1737 assert(Inst !=
D &&
"Inst occurs in data structures");
1740 for (
const auto &DepKV : ReverseNonLocalDeps) {
1741 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1743 assert(Inst !=
D &&
"Inst occurs in data structures");
1746 for (
const auto &DepKV : ReverseNonLocalPtrDeps) {
1747 assert(DepKV.first !=
D &&
"Inst occurs in rev NLPD map");
1749 for (ValueIsLoadPair
P : DepKV.second)
1750 assert(
P != ValueIsLoadPair(
D,
false) &&
P != ValueIsLoadPair(
D,
true) &&
1751 "Inst occurs in ReverseNonLocalPtrDeps map");
1773 "Memory Dependence Analysis",
false,
true)
1818 return DefaultBlockScanLimit;
1822 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1823 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1824 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1825 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static bool isLoad(int Opcode)
Atomic ordering constants.
block Block Frequency Analysis
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This file defines the DenseMap class.
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 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)
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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)
This defines the Use class.
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
bool onlyReadsMemory(const CallBase *Call)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
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 <a particular IR unit>" (e....
API to communicate dependencies between analyses during invalidation.
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
A container for analyses that lazily runs them and caches their results.
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.
InstListType::iterator iterator
Instruction iterators...
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
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)
Dependence - This class represents a dependence between two memory memory references in a function.
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
void removeInstruction(Instruction *I)
An instruction for ordering other memory operations.
FunctionPass class - This class is used to implement most global optimizations.
const BasicBlock & getEntryBlock() const
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.
const BasicBlock * getParent() const
bool isTerminator() const
bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
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.
Representation for a specific memory location.
MemoryLocation getWithNewSize(LocationSize NewSize) const
MemoryLocation getWithoutAATags() const
static 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 MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
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.
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 ...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void clear()
clear - Remove all information.
ArrayRef< BasicBlock * > get(BasicBlock *BB)
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...
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.
Target - Wrapper for Target specific information.
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.
Align getPointerAlignment(const DataLayout &DL) const
Returns an alignment of the pointer value.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
static constexpr bool isKnownGE(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
self_iterator getIterator()
This class provides various memory handling functions that manipulate MemoryBlock instances.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
void initializeMemoryDependenceWrapperPassPass(PassRegistry &)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
bool isStrongerThanUnordered(AtomicOrdering AO)
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
auto reverse(ContainerTy &&C)
bool isModSet(const ModRefInfo MRI)
void sort(IteratorTy Start, IteratorTy End)
bool isModOrRefSet(const ModRefInfo MRI)
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.
@ Mod
The access may modify the value stored in memory.
@ NoModRef
The access neither references nor modifies the value stored in memory.
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
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,...
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
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...