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);
367 bool isInvariantLoad =
false;
371 Limit = &DefaultLimit;
405 if (
isLoad && QueryInst) {
406 LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
407 if (LI && LI->
hasMetadata(LLVMContext::MD_invariant_load))
408 isInvariantLoad =
true;
417 if (
auto *LI = dyn_cast<LoadInst>(
I))
419 if (
auto *SI = dyn_cast<StoreInst>(
I))
421 return I->mayReadOrWriteMemory();
425 while (ScanIt != BB->
begin()) {
430 if (isa<DbgInfoIntrinsic>(II))
444 case Intrinsic::lifetime_start: {
454 case Intrinsic::masked_load:
455 case Intrinsic::masked_store: {
463 if (
ID == Intrinsic::masked_load)
475 if (
LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
479 if (LI->isVolatile()) {
517 ClobberOffsets[LI] = R.getOffset();
534 if (
StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
538 if (!SI->isUnordered() && SI->isAtomic()) {
556 if (SI->isVolatile())
591 if (AccessPtr == Inst || BatchAA.
isMustAlias(Inst, AccessPtr))
597 if (isa<SelectInst>(Inst) && MemLoc.
Ptr == Inst)
608 if (
FenceInst *FI = dyn_cast<FenceInst>(Inst))
643 ClobberOffsets.
clear();
651 if (!LocalCache.isDirty())
678 if (
auto *II = dyn_cast<IntrinsicInst>(QueryInst))
679 isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
683 QueryParent, QueryInst,
nullptr);
684 }
else if (
auto *QueryCall = dyn_cast<CallBase>(QueryInst)) {
686 LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,
695 ReverseLocalDeps[
I].
insert(QueryInst);
706 Count = Cache.size();
707 assert(std::is_sorted(Cache.begin(), Cache.begin() + Count) &&
708 "Cache isn't sorted!");
715 "getNonLocalCallDependency should only be used on calls with "
717 PerInstNLInfo &CacheP = NonLocalDepsMap[QueryCall];
725 if (!Cache.empty()) {
728 if (!CacheP.second) {
735 for (
auto &Entry : Cache)
736 if (Entry.getResult().isDirty())
742 ++NumCacheDirtyNonLocal;
747 ++NumUncacheNonLocal;
755 unsigned NumSortedEntries = Cache.
size();
759 while (!DirtyBlocks.
empty()) {
763 if (!Visited.
insert(DirtyBB).second)
769 NonLocalDepInfo::iterator Entry =
770 std::upper_bound(Cache.begin(), Cache.begin() + NumSortedEntries,
772 if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB)
776 if (Entry != Cache.begin() + NumSortedEntries &&
777 Entry->getBB() == DirtyBB) {
780 if (!Entry->getResult().isDirty())
784 ExistingResult = &*Entry;
790 if (ExistingResult) {
794 RemoveFromReverseMap<Instruction *>(ReverseNonLocalDeps, Inst,
802 if (ScanPos != DirtyBB->
begin()) {
803 Dep = getCallDependencyFrom(QueryCall, isReadonlyCall, ScanPos, DirtyBB);
825 ReverseNonLocalDeps[Inst].
insert(QueryCall);
840 bool isLoad = isa<LoadInst>(QueryInst);
845 "Can't get pointer deps of a non-pointer!");
849 auto NonLocalDefIt = NonLocalDefsCache.find(QueryInst);
850 if (NonLocalDefIt != NonLocalDefsCache.end()) {
851 Result.push_back(NonLocalDefIt->second);
852 ReverseNonLocalDefsCache[NonLocalDefIt->second.getResult().getInst()]
854 NonLocalDefsCache.erase(NonLocalDefIt);
867 if (
LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
868 return !LI->isUnordered();
869 }
else if (
StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
870 return !SI->isUnordered();
887 if (getNonLocalPointerDepFromBB(QueryInst,
Address, Loc,
isLoad, FromBB,
888 Result, Visited,
true))
900MemDepResult MemoryDependenceResults::getNonLocalInfoForBlock(
902 BasicBlock *BB, NonLocalDepInfo *Cache,
unsigned NumSortedEntries,
905 bool isInvariantLoad =
false;
907 if (
LoadInst *LI = dyn_cast_or_null<LoadInst>(QueryInst))
908 isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);
912 NonLocalDepInfo::iterator Entry = std::upper_bound(
914 if (Entry != Cache->begin() && (Entry - 1)->getBB() == BB)
918 if (Entry != Cache->begin() + NumSortedEntries && Entry->getBB() == BB)
919 ExistingResult = &*Entry;
924 if (ExistingResult && isInvariantLoad &&
926 ExistingResult =
nullptr;
930 if (ExistingResult && !ExistingResult->
getResult().isDirty()) {
931 ++NumCacheNonLocalPtr;
941 "Instruction invalidated?");
942 ++NumCacheDirtyNonLocalPtr;
946 ValueIsLoadPair CacheKey(Loc.
Ptr,
isLoad);
949 ++NumUncacheNonLocalPtr;
954 QueryInst,
nullptr, BatchAA);
976 assert(Inst &&
"Didn't depend on anything?");
977 ValueIsLoadPair CacheKey(Loc.
Ptr,
isLoad);
978 ReverseNonLocalPtrDeps[Inst].
insert(CacheKey);
988 unsigned NumSortedEntries) {
989 switch (Cache.size() - NumSortedEntries) {
997 MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
998 std::upper_bound(Cache.begin(), Cache.end() - 1, Val);
999 Cache.insert(Entry, Val);
1004 if (Cache.size() != 1) {
1007 MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
1009 Cache.insert(Entry, Val);
1032bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
1037 bool IsIncomplete) {
1045 NonLocalPointerInfo InitialNLPI;
1046 InitialNLPI.Size = Loc.
Size;
1047 InitialNLPI.AATags = Loc.
AATags;
1049 bool isInvariantLoad =
false;
1050 if (
LoadInst *LI = dyn_cast_or_null<LoadInst>(QueryInst))
1051 isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);
1055 std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
1056 NonLocalPointerDeps.
insert(std::make_pair(CacheKey, InitialNLPI));
1057 NonLocalPointerInfo *CacheInfo = &Pair.first->second;
1062 if (!isInvariantLoad && !Pair.second) {
1063 if (CacheInfo->Size != Loc.
Size) {
1064 bool ThrowOutEverything;
1065 if (CacheInfo->Size.hasValue() && Loc.
Size.
hasValue()) {
1069 ThrowOutEverything =
1077 if (ThrowOutEverything) {
1080 CacheInfo->Pair = BBSkipFirstBlockPair();
1081 CacheInfo->Size = Loc.
Size;
1082 for (
auto &Entry : CacheInfo->NonLocalDeps)
1083 if (
Instruction *Inst = Entry.getResult().getInst())
1085 CacheInfo->NonLocalDeps.clear();
1089 IsIncomplete =
true;
1093 return getNonLocalPointerDepFromBB(
1095 StartBB, Result, Visited, SkipFirstBlock, IsIncomplete);
1102 if (CacheInfo->AATags != Loc.
AATags) {
1103 if (CacheInfo->AATags) {
1104 CacheInfo->Pair = BBSkipFirstBlockPair();
1106 for (
auto &Entry : CacheInfo->NonLocalDeps)
1107 if (
Instruction *Inst = Entry.getResult().getInst())
1109 CacheInfo->NonLocalDeps.clear();
1113 IsIncomplete =
true;
1116 return getNonLocalPointerDepFromBB(
1118 Visited, SkipFirstBlock, IsIncomplete);
1128 if (!IsIncomplete && !isInvariantLoad &&
1129 CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
1135 if (!Visited.
empty()) {
1136 for (
auto &Entry : *Cache) {
1138 Visited.
find(Entry.getBB());
1139 if (VI == Visited.
end() ||
VI->second ==
Pointer.getAddr())
1150 for (
auto &Entry : *Cache) {
1151 Visited.
insert(std::make_pair(Entry.getBB(),
Addr));
1152 if (Entry.getResult().isNonLocal()) {
1161 ++NumCacheCompleteNonLocalPtr;
1172 if (!isInvariantLoad) {
1173 if (!IsIncomplete && Cache->empty())
1174 CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
1176 CacheInfo->Pair = BBSkipFirstBlockPair();
1190 unsigned NumSortedEntries = Cache->size();
1192 bool GotWorklistLimit =
false;
1196 while (!Worklist.
empty()) {
1205 if (Cache && NumSortedEntries != Cache->size()) {
1212 CacheInfo->Pair = BBSkipFirstBlockPair();
1217 if (!SkipFirstBlock) {
1220 assert(Visited.
count(BB) &&
"Should check 'visited' before adding to WL");
1226 QueryInst, Loc,
isLoad, BB, Cache, NumSortedEntries, BatchAA);
1241 if (!
Pointer.needsPHITranslationFromBlock(BB)) {
1242 SkipFirstBlock =
false;
1246 std::pair<DenseMap<BasicBlock *, Value *>::iterator,
bool> InsertRes =
1248 if (InsertRes.second) {
1257 if (InsertRes.first->second !=
Pointer.getAddr()) {
1260 for (
unsigned i = 0; i < NewBlocks.
size(); i++)
1261 Visited.
erase(NewBlocks[i]);
1262 goto PredTranslationFailure;
1265 if (NewBlocks.
size() > WorklistEntries) {
1268 for (
unsigned i = 0; i < NewBlocks.
size(); i++)
1269 Visited.
erase(NewBlocks[i]);
1270 GotWorklistLimit =
true;
1271 goto PredTranslationFailure;
1273 WorklistEntries -= NewBlocks.
size();
1280 if (!
Pointer.isPotentiallyPHITranslatable())
1281 goto PredTranslationFailure;
1288 if (Cache && NumSortedEntries != Cache->size()) {
1290 NumSortedEntries = Cache->size();
1296 PredList.
push_back(std::make_pair(Pred, Pointer));
1309 std::pair<DenseMap<BasicBlock *, Value *>::iterator,
bool> InsertRes =
1310 Visited.
insert(std::make_pair(Pred, PredPtrVal));
1312 if (!InsertRes.second) {
1318 if (InsertRes.first->second == PredPtrVal)
1327 for (
unsigned i = 0, n = PredList.
size(); i < n; ++i)
1328 Visited.
erase(PredList[i].first);
1330 goto PredTranslationFailure;
1339 for (
unsigned i = 0, n = PredList.
size(); i < n; ++i) {
1344 bool CanTranslate =
true;
1350 CanTranslate =
false;
1360 if (!CanTranslate ||
1361 !getNonLocalPointerDepFromBB(QueryInst, PredPointer,
1363 Pred, Result, Visited)) {
1373 NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
1374 NLPI.Pair = BBSkipFirstBlockPair();
1380 CacheInfo = &NonLocalPointerDeps[CacheKey];
1381 Cache = &CacheInfo->NonLocalDeps;
1382 NumSortedEntries = Cache->size();
1388 CacheInfo->Pair = BBSkipFirstBlockPair();
1389 SkipFirstBlock =
false;
1392 PredTranslationFailure:
1399 CacheInfo = &NonLocalPointerDeps[CacheKey];
1400 Cache = &CacheInfo->NonLocalDeps;
1401 NumSortedEntries = Cache->size();
1408 CacheInfo->Pair = BBSkipFirstBlockPair();
1420 if (!isInvariantLoad) {
1422 if (
I.getBB() != BB)
1425 assert((GotWorklistLimit ||
I.getResult().isNonLocal() ||
1427 "Should only be here with transparent block");
1435 (void)GotWorklistLimit;
1448void MemoryDependenceResults::removeCachedNonLocalPointerDependencies(
1449 ValueIsLoadPair
P) {
1452 if (!NonLocalDefsCache.empty()) {
1453 auto it = NonLocalDefsCache.find(
P.getPointer());
1454 if (it != NonLocalDefsCache.end()) {
1456 it->second.getResult().getInst(),
P.getPointer());
1457 NonLocalDefsCache.erase(it);
1460 if (
auto *
I = dyn_cast<Instruction>(
P.getPointer())) {
1461 auto toRemoveIt = ReverseNonLocalDefsCache.
find(
I);
1462 if (toRemoveIt != ReverseNonLocalDefsCache.
end()) {
1463 for (
const auto *entry : toRemoveIt->second)
1464 NonLocalDefsCache.erase(entry);
1465 ReverseNonLocalDefsCache.
erase(toRemoveIt);
1471 if (It == NonLocalPointerDeps.
end())
1489 NonLocalPointerDeps.
erase(It);
1494 if (!
Ptr->getType()->isPointerTy())
1510 if (NLDI != NonLocalDepsMap.
end()) {
1512 for (
auto &Entry : BlockMap)
1513 if (
Instruction *Inst = Entry.getResult().getInst())
1515 NonLocalDepsMap.
erase(NLDI);
1520 if (LocalDepEntry != LocalDeps.
end()) {
1522 if (
Instruction *Inst = LocalDepEntry->second.getInst())
1526 LocalDeps.
erase(LocalDepEntry);
1535 removeCachedNonLocalPointerDependencies(
ValueIsLoadPair(RemInst,
false));
1536 removeCachedNonLocalPointerDependencies(
ValueIsLoadPair(RemInst,
true));
1540 auto toRemoveIt = NonLocalDefsCache.find(RemInst);
1541 if (toRemoveIt != NonLocalDefsCache.end()) {
1542 assert(isa<LoadInst>(RemInst) &&
1543 "only load instructions should be added directly");
1544 const Instruction *DepV = toRemoveIt->second.getResult().getInst();
1545 ReverseNonLocalDefsCache.
find(DepV)->second.erase(RemInst);
1546 NonLocalDefsCache.erase(toRemoveIt);
1561 NewDirtyVal = MemDepResult::getDirty(&*++RemInst->
getIterator());
1564 if (ReverseDepIt != ReverseLocalDeps.
end()) {
1567 "Nothing can locally depend on a terminator");
1569 for (
Instruction *InstDependingOnRemInst : ReverseDepIt->second) {
1570 assert(InstDependingOnRemInst != RemInst &&
1571 "Already removed our local dep info");
1573 LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
1577 "There is no way something else can have "
1578 "a local dep on this if it is a terminator!");
1580 std::make_pair(NewDirtyVal.
getInst(), InstDependingOnRemInst));
1583 ReverseLocalDeps.
erase(ReverseDepIt);
1587 while (!ReverseDepsToAdd.
empty()) {
1588 ReverseLocalDeps[ReverseDepsToAdd.
back().first].
insert(
1589 ReverseDepsToAdd.
back().second);
1594 ReverseDepIt = ReverseNonLocalDeps.
find(RemInst);
1595 if (ReverseDepIt != ReverseNonLocalDeps.
end()) {
1597 assert(
I != RemInst &&
"Already removed NonLocalDep info for RemInst");
1599 PerInstNLInfo &INLD = NonLocalDepsMap[
I];
1603 for (
auto &Entry : INLD.first) {
1604 if (Entry.getResult().getInst() != RemInst)
1608 Entry.setResult(NewDirtyVal);
1611 ReverseDepsToAdd.
push_back(std::make_pair(NextI,
I));
1615 ReverseNonLocalDeps.
erase(ReverseDepIt);
1618 while (!ReverseDepsToAdd.
empty()) {
1619 ReverseNonLocalDeps[ReverseDepsToAdd.
back().first].
insert(
1620 ReverseDepsToAdd.
back().second);
1628 ReverseNonLocalPtrDeps.
find(RemInst);
1629 if (ReversePtrDepIt != ReverseNonLocalPtrDeps.
end()) {
1631 ReversePtrDepsToAdd;
1634 assert(
P.getPointer() != RemInst &&
1635 "Already removed NonLocalPointerDeps info for RemInst");
1643 for (
auto &Entry : NLPDI) {
1644 if (Entry.getResult().getInst() != RemInst)
1648 Entry.setResult(NewDirtyVal);
1651 ReversePtrDepsToAdd.
push_back(std::make_pair(NewDirtyInst,
P));
1659 ReverseNonLocalPtrDeps.
erase(ReversePtrDepIt);
1661 while (!ReversePtrDepsToAdd.
empty()) {
1662 ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.
back().first].
insert(
1663 ReversePtrDepsToAdd.
back().second);
1668 assert(!NonLocalDepsMap.
count(RemInst) &&
"RemInst got reinserted?");
1676void MemoryDependenceResults::verifyRemoved(
Instruction *
D)
const {
1678 for (
const auto &DepKV : LocalDeps) {
1679 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1680 assert(DepKV.second.getInst() !=
D &&
"Inst occurs in data structures");
1683 for (
const auto &DepKV : NonLocalPointerDeps) {
1684 assert(DepKV.first.getPointer() !=
D &&
"Inst occurs in NLPD map key");
1685 for (
const auto &Entry : DepKV.second.NonLocalDeps)
1686 assert(Entry.getResult().getInst() !=
D &&
"Inst occurs as NLPD value");
1689 for (
const auto &DepKV : NonLocalDepsMap) {
1690 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1691 const PerInstNLInfo &INLD = DepKV.second;
1692 for (
const auto &Entry : INLD.first)
1693 assert(Entry.getResult().getInst() !=
D &&
1694 "Inst occurs in data structures");
1697 for (
const auto &DepKV : ReverseLocalDeps) {
1698 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1700 assert(Inst !=
D &&
"Inst occurs in data structures");
1703 for (
const auto &DepKV : ReverseNonLocalDeps) {
1704 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1706 assert(Inst !=
D &&
"Inst occurs in data structures");
1709 for (
const auto &DepKV : ReverseNonLocalPtrDeps) {
1710 assert(DepKV.first !=
D &&
"Inst occurs in rev NLPD map");
1712 for (ValueIsLoadPair
P : DepKV.second)
1713 assert(
P != ValueIsLoadPair(
D,
false) &&
P != ValueIsLoadPair(
D,
true) &&
1714 "Inst occurs in ReverseNonLocalPtrDeps map");
1736 "Memory Dependence Analysis",
false,
true)
1781 return DefaultBlockScanLimit;
1785 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1786 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1787 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1788 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 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)
ModRefInfo callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT)
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.
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()
uint64_t 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.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
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 a range to a container.
bool isStrongerThanUnordered(AtomicOrdering AO)
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
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 isModAndRefSet(const ModRefInfo MRI)
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...
A special type used by analysis passes to provide an address that identifies that particular analysis...