58#define DEBUG_TYPE "memdep"
60STATISTIC(NumCacheNonLocal,
"Number of fully cached non-local responses");
61STATISTIC(NumCacheDirtyNonLocal,
"Number of dirty cached non-local responses");
62STATISTIC(NumUncacheNonLocal,
"Number of uncached non-local responses");
65 "Number of fully cached non-local ptr responses");
67 "Number of cached, but dirty, non-local ptr responses");
68STATISTIC(NumUncacheNonLocalPtr,
"Number of uncached non-local ptr responses");
70 "Number of block queries that were completely cached");
78template <
typename KeyTy>
83 ReverseMap.find(Inst);
84 assert(InstIt != ReverseMap.
end() &&
"Reverse map out of sync?");
85 bool Found = InstIt->second.
erase(Val);
86 assert(Found &&
"Invalid reverse map!");
88 if (InstIt->second.
empty())
89 ReverseMap.erase(InstIt);
100 if (LI->isUnordered()) {
113 if (
SI->isUnordered()) {
139 switch (
II->getIntrinsicID()) {
140 case Intrinsic::lifetime_start:
141 case Intrinsic::lifetime_end:
146 case Intrinsic::invariant_start:
151 case Intrinsic::invariant_end:
156 case Intrinsic::masked_load:
159 case Intrinsic::masked_store:
176MemDepResult MemoryDependenceResults::getCallDependencyFrom(
180 bool IsInvariantLoad =
Call->
hasMetadata(LLVMContext::MD_invariant_load);
183 while (ScanIt != BB->
begin()) {
206 bool IsIdenticalReadOnlyCall = isReadOnlyCall && !
isModSet(MR) &&
211 if (IsInvariantLoad && IsIdenticalReadOnlyCall)
218 if (IsIdenticalReadOnlyCall)
224 }
else if (IsInvariantLoad) {
249 if (QueryInst !=
nullptr) {
253 if (InvariantGroupDependency.
isDef())
254 return InvariantGroupDependency;
258 MemLoc,
isLoad, ScanIt, BB, QueryInst, Limit, BatchAA);
259 if (SimpleDep.
isDef())
265 return InvariantGroupDependency;
268 "InvariantGroupDependency should be only unknown at this point");
284 if (!LI->
hasMetadata(LLVMContext::MD_invariant_group))
302 assert(
Other &&
"Must call it with not null instruction");
303 if (Best ==
nullptr || DT.dominates(Best,
Other))
308 for (
const Use &Us : LoadOperand->
uses()) {
310 if (!U || U == LI || !DT.dominates(U, LI))
319 U->hasMetadata(LLVMContext::MD_invariant_group))
320 ClosestDependency = GetClosestDependency(ClosestDependency, U);
323 if (!ClosestDependency)
325 if (ClosestDependency->
getParent() == BB)
331 NonLocalDefsCache.try_emplace(
334 ReverseNonLocalDefsCache[ClosestDependency].insert(LI);
348 Limit = &DefaultLimit;
382 if (
isLoad && QueryInst) {
385 MemLocAlign = LI->getAlign();
396 return I->mayReadOrWriteMemory();
400 while (ScanIt != BB->
begin()) {
414 case Intrinsic::lifetime_start: {
424 case Intrinsic::masked_load:
425 case Intrinsic::masked_store: {
433 if (ID == Intrinsic::masked_load)
449 if (LI->isVolatile()) {
487 ClobberOffsets[LI] = R.getOffset();
508 if (!
SI->isUnordered() &&
SI->isAtomic()) {
526 if (
SI->isVolatile())
564 if (AccessPtr == Inst || BatchAA.
isMustAlias(Inst, AccessPtr))
612 ClobberOffsets.clear();
620 if (!LocalCache.isDirty())
648 isLoad |=
II->getIntrinsicID() == Intrinsic::lifetime_start;
652 QueryParent, QueryInst,
nullptr);
654 bool isReadOnly = AA.onlyReadsMemory(QueryCall);
655 LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,
664 ReverseLocalDeps[
I].insert(QueryInst);
675 Count = Cache.size();
676 assert(std::is_sorted(Cache.begin(), Cache.begin() +
Count) &&
677 "Cache isn't sorted!");
684 "getNonLocalCallDependency should only be used on calls with "
686 PerInstNLInfo &CacheP = NonLocalDepsMap[QueryCall];
694 if (!Cache.empty()) {
697 if (!CacheP.second) {
704 for (
auto &Entry : Cache)
705 if (Entry.getResult().isDirty())
711 ++NumCacheDirtyNonLocal;
716 ++NumUncacheNonLocal;
720 bool isReadonlyCall = AA.onlyReadsMemory(QueryCall);
724 unsigned NumSortedEntries = Cache.
size();
728 while (!DirtyBlocks.
empty()) {
732 if (!Visited.
insert(DirtyBB).second)
738 NonLocalDepInfo::iterator Entry =
739 std::upper_bound(Cache.begin(), Cache.begin() + NumSortedEntries,
741 if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB)
745 if (Entry != Cache.begin() + NumSortedEntries &&
746 Entry->getBB() == DirtyBB) {
749 if (!Entry->getResult().isDirty())
753 ExistingResult = &*Entry;
759 if (ExistingResult) {
771 if (ScanPos != DirtyBB->
begin()) {
772 Dep = getCallDependencyFrom(QueryCall, isReadonlyCall, ScanPos, DirtyBB);
794 ReverseNonLocalDeps[Inst].insert(QueryCall);
813 assert(
Loc.Ptr->getType()->isPointerTy() &&
814 "Can't get pointer deps of a non-pointer!");
818 auto NonLocalDefIt = NonLocalDefsCache.find(QueryInst);
819 if (NonLocalDefIt != NonLocalDefsCache.end()) {
820 Result.push_back(NonLocalDefIt->second);
822 ReverseNonLocalDefsCache, NonLocalDefIt->second.getResult().getInst(),
824 NonLocalDefsCache.erase(NonLocalDefIt);
838 return !LI->isUnordered();
840 return !
SI->isUnordered();
856 ++NonLocalPointerDepEpoch;
857 assert(NonLocalPointerDepEpoch > 0 &&
858 "NonLocalPointerDepVisitedEpoch overflow");
873MemDepResult MemoryDependenceResults::getNonLocalInfoForBlock(
875 BasicBlock *BB, NonLocalDepInfo *Cache,
unsigned NumSortedEntries,
885 NonLocalDepInfo::iterator Entry = std::upper_bound(
887 if (Entry != Cache->begin() && (Entry - 1)->getBB() == BB)
891 if (Entry != Cache->begin() + NumSortedEntries && Entry->getBB() == BB)
892 ExistingResult = &*Entry;
899 ExistingResult =
nullptr;
903 if (ExistingResult && !ExistingResult->
getResult().isDirty()) {
904 ++NumCacheNonLocalPtr;
914 "Instruction invalidated?");
915 ++NumCacheDirtyNonLocalPtr;
919 ValueIsLoadPair CacheKey(
Loc.Ptr,
isLoad);
922 ++NumUncacheNonLocalPtr;
927 QueryInst,
nullptr, BatchAA);
938 Cache->push_back(NonLocalDepEntry(BB, Dep));
949 assert(Inst &&
"Didn't depend on anything?");
950 ValueIsLoadPair CacheKey(Loc.
Ptr,
isLoad);
951 ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
961 unsigned NumSortedEntries) {
964 if (Cache.size() < 2)
967 unsigned s = Cache.size() - NumSortedEntries;
974 if (NumSortedEntries == 0) {
982 if (s <
Log2_32(Cache.size())) {
986 MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
987 std::upper_bound(Cache.begin(), Cache.end() - s + 1, Val);
988 Cache.insert(Entry, Val);
996void MemoryDependenceResults::setNonLocalPointerDepVisited(
BasicBlock *BB,
998 NonLocalPointerDepVisited[BB->
getNumber()] = {
V, NonLocalPointerDepEpoch};
1001bool MemoryDependenceResults::isNonLocalPointerDepVisited(
1003 return NonLocalPointerDepVisited[BB->
getNumber()].second ==
1004 NonLocalPointerDepEpoch;
1008MemoryDependenceResults::lookupNonLocalPointerDepVisited(
BasicBlock *BB)
const {
1009 assert(isNonLocalPointerDepVisited(BB) &&
1010 "Visited value requested for unseen block");
1011 return NonLocalPointerDepVisited[BB->
getNumber()].first;
1027bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
1031 bool IsIncomplete) {
1039 NonLocalPointerInfo InitialNLPI;
1040 InitialNLPI.Size = Loc.
Size;
1041 InitialNLPI.AATags = Loc.
AATags;
1049 std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
1050 NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
1051 NonLocalPointerInfo *CacheInfo = &Pair.first->second;
1057 if (CacheInfo->Size != Loc.
Size) {
1060 CacheInfo->Pair = BBSkipFirstBlockPair();
1061 CacheInfo->Size = Loc.
Size;
1062 for (
auto &Entry : CacheInfo->NonLocalDeps)
1063 if (Instruction *Inst =
Entry.getResult().getInst())
1065 CacheInfo->NonLocalDeps.clear();
1069 IsIncomplete =
true;
1075 if (CacheInfo->AATags != Loc.
AATags) {
1076 if (CacheInfo->AATags) {
1077 CacheInfo->Pair = BBSkipFirstBlockPair();
1078 CacheInfo->AATags = AAMDNodes();
1079 for (
auto &Entry : CacheInfo->NonLocalDeps)
1080 if (Instruction *Inst =
Entry.getResult().getInst())
1082 CacheInfo->NonLocalDeps.clear();
1086 IsIncomplete =
true;
1089 return getNonLocalPointerDepFromBB(
1091 SkipFirstBlock, IsIncomplete);
1102 CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
1108 for (
auto &Entry : *Cache) {
1109 if (!isNonLocalPointerDepVisited(
Entry.getBB()))
1111 Value *Prev = lookupNonLocalPointerDepVisited(
Entry.getBB());
1112 if (Prev ==
Pointer.getAddr())
1122 for (
auto &Entry : *Cache) {
1123 setNonLocalPointerDepVisited(
Entry.getBB(), Addr);
1124 if (
Entry.getResult().isNonLocal()) {
1128 if (DT.isReachableFromEntry(
Entry.getBB())) {
1130 NonLocalDepResult(
Entry.getBB(),
Entry.getResult(), Addr));
1133 ++NumCacheCompleteNonLocalPtr;
1138 if (Cache->size() > Opts.memdep_cache_global_limit)
1149 if (!IsIncomplete && Cache->empty())
1150 CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
1152 CacheInfo->Pair = BBSkipFirstBlockPair();
1166 unsigned NumSortedEntries = Cache->size();
1167 unsigned WorklistEntries = Opts.memdep_block_number_limit;
1168 bool GotWorklistLimit =
false;
1171 BatchAAResults BatchAA(AA, &EEA);
1172 while (!Worklist.
empty()) {
1181 if (Cache && NumSortedEntries != Cache->size()) {
1188 CacheInfo->Pair = BBSkipFirstBlockPair();
1193 if (!SkipFirstBlock) {
1196 assert(isNonLocalPointerDepVisited(BB) &&
1197 "Should check 'visited' before adding to WL");
1202 MemDepResult Dep = getNonLocalInfoForBlock(
1203 QueryInst, Loc,
isLoad, BB, Cache, NumSortedEntries, BatchAA);
1207 if (DT.isReachableFromEntry(BB)) {
1208 Result.push_back(NonLocalDepResult(BB, Dep,
Pointer.getAddr()));
1218 if (!
Pointer.needsPHITranslationFromBlock(BB)) {
1219 SkipFirstBlock =
false;
1220 SmallVector<BasicBlock *, 16> NewBlocks;
1221 for (BasicBlock *
Pred : PredCache.get(BB)) {
1223 if (!isNonLocalPointerDepVisited(
Pred)) {
1224 setNonLocalPointerDepVisited(
Pred,
Pointer.getAddr());
1229 Value *Prev = lookupNonLocalPointerDepVisited(
Pred);
1233 if (Prev !=
Pointer.getAddr()) {
1236 for (
auto *NewBlock : NewBlocks)
1237 setNonLocalPointerDepVisited(NewBlock,
nullptr);
1238 goto PredTranslationFailure;
1241 if (NewBlocks.
size() > WorklistEntries) {
1244 for (
auto *NewBlock : NewBlocks)
1245 setNonLocalPointerDepVisited(NewBlock,
nullptr);
1246 GotWorklistLimit =
true;
1247 goto PredTranslationFailure;
1249 WorklistEntries -= NewBlocks.
size();
1256 if (!
Pointer.isPotentiallyPHITranslatable())
1257 goto PredTranslationFailure;
1264 if (Cache && NumSortedEntries != Cache->size()) {
1266 NumSortedEntries = Cache->size();
1271 for (BasicBlock *
Pred : PredCache.get(BB)) {
1276 PHITransAddr &PredPointer = PredList.
back().second;
1285 if (!isNonLocalPointerDepVisited(
Pred)) {
1286 setNonLocalPointerDepVisited(
Pred, PredPtrVal);
1289 Value *PrevVal = lookupNonLocalPointerDepVisited(
Pred);
1296 if (PrevVal == PredPtrVal)
1305 for (
const auto &
Pred : PredList)
1306 setNonLocalPointerDepVisited(
Pred.first,
nullptr);
1308 goto PredTranslationFailure;
1316 for (
auto &
I : PredList) {
1318 PHITransAddr &PredPointer =
I.second;
1321 bool CanTranslate =
true;
1333 if (SelectInst *Sel = PredPointer.
getSelect()) {
1335 PHITransAddr(Pointer).translateValue(BB,
Pred, &DT,
1336 Sel->getCondition());
1337 if (SelAddrs.first && SelAddrs.second) {
1339 SelectAddr(Sel, SelAddrs)));
1340 NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
1341 NLPI.Pair = BBSkipFirstBlockPair();
1345 CanTranslate =
false;
1356 if (!CanTranslate ||
1357 !getNonLocalPointerDepFromBB(QueryInst, PredPointer,
1369 NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
1370 NLPI.Pair = BBSkipFirstBlockPair();
1376 CacheInfo = &NonLocalPointerDeps[CacheKey];
1377 Cache = &CacheInfo->NonLocalDeps;
1378 NumSortedEntries = Cache->size();
1384 CacheInfo->Pair = BBSkipFirstBlockPair();
1385 SkipFirstBlock =
false;
1388 PredTranslationFailure:
1395 CacheInfo = &NonLocalPointerDeps[CacheKey];
1396 Cache = &CacheInfo->NonLocalDeps;
1397 NumSortedEntries = Cache->size();
1404 CacheInfo->Pair = BBSkipFirstBlockPair();
1418 if (
I.getBB() != BB)
1421 assert((GotWorklistLimit ||
I.getResult().isNonLocal() ||
1422 !DT.isReachableFromEntry(BB)) &&
1423 "Should only be here with transparent block");
1431 (void)GotWorklistLimit;
1444void MemoryDependenceResults::removeCachedNonLocalPointerDependencies(
1445 ValueIsLoadPair
P) {
1448 if (!NonLocalDefsCache.empty()) {
1449 auto it = NonLocalDefsCache.find(
P.getPointer());
1450 if (it != NonLocalDefsCache.end()) {
1452 it->second.getResult().getInst(),
P.getPointer());
1453 NonLocalDefsCache.erase(it);
1457 auto toRemoveIt = ReverseNonLocalDefsCache.find(
I);
1458 if (toRemoveIt != ReverseNonLocalDefsCache.end()) {
1459 for (
const auto *Entry : toRemoveIt->second) {
1460 [[maybe_unused]]
bool Removed = NonLocalDefsCache.erase(Entry);
1461 assert(Removed &&
"Reverse non-local def map out of sync?");
1463 ReverseNonLocalDefsCache.erase(toRemoveIt);
1469 if (It == NonLocalPointerDeps.end())
1476 for (
const NonLocalDepEntry &DE : PInfo) {
1487 NonLocalPointerDeps.erase(It);
1495 removeCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr,
false));
1497 removeCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr,
true));
1505 EEA.removeInstruction(RemInst);
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()) {
1543 "only load instructions should be added directly");
1544 Instruction *DepV = toRemoveIt->second.getResult().getInst();
1547 NonLocalDefsCache.erase(toRemoveIt);
1551 auto ReverseNonLocalDefIt = ReverseNonLocalDefsCache.find(RemInst);
1552 if (ReverseNonLocalDefIt != ReverseNonLocalDefsCache.end()) {
1553 for (
const Value *QueryInst : ReverseNonLocalDefIt->second) {
1554 [[maybe_unused]]
bool Removed = NonLocalDefsCache.erase(QueryInst);
1555 assert(Removed &&
"Reverse non-local def map out of sync?");
1557 ReverseNonLocalDefsCache.erase(ReverseNonLocalDefIt);
1571 NewDirtyVal = MemDepResult::getDirty(&*++RemInst->
getIterator());
1573 ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
1574 if (ReverseDepIt != ReverseLocalDeps.end()) {
1577 "Nothing can locally depend on a terminator");
1579 for (
Instruction *InstDependingOnRemInst : ReverseDepIt->second) {
1580 assert(InstDependingOnRemInst != RemInst &&
1581 "Already removed our local dep info");
1583 LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
1587 "There is no way something else can have "
1588 "a local dep on this if it is a terminator!");
1590 std::make_pair(NewDirtyVal.
getInst(), InstDependingOnRemInst));
1593 ReverseLocalDeps.erase(ReverseDepIt);
1597 while (!ReverseDepsToAdd.
empty()) {
1598 ReverseLocalDeps[ReverseDepsToAdd.
back().first].insert(
1599 ReverseDepsToAdd.
back().second);
1604 ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
1605 if (ReverseDepIt != ReverseNonLocalDeps.end()) {
1607 assert(
I != RemInst &&
"Already removed NonLocalDep info for RemInst");
1609 PerInstNLInfo &INLD = NonLocalDepsMap[
I];
1613 for (
auto &Entry : INLD.first) {
1614 if (Entry.getResult().getInst() != RemInst)
1618 Entry.setResult(NewDirtyVal);
1621 ReverseDepsToAdd.
push_back(std::make_pair(NextI,
I));
1625 ReverseNonLocalDeps.erase(ReverseDepIt);
1628 while (!ReverseDepsToAdd.
empty()) {
1629 ReverseNonLocalDeps[ReverseDepsToAdd.
back().first].insert(
1630 ReverseDepsToAdd.
back().second);
1637 ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
1638 ReverseNonLocalPtrDeps.find(RemInst);
1639 if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
1641 ReversePtrDepsToAdd;
1643 for (ValueIsLoadPair
P : ReversePtrDepIt->second) {
1644 assert(
P.getPointer() != RemInst &&
1645 "Already removed NonLocalPointerDeps info for RemInst");
1647 auto &NLPD = NonLocalPointerDeps[
P];
1652 NLPD.Pair = BBSkipFirstBlockPair();
1655 for (
auto &Entry : NLPDI) {
1656 if (Entry.getResult().getInst() != RemInst)
1660 Entry.setResult(NewDirtyVal);
1663 ReversePtrDepsToAdd.
push_back(std::make_pair(NewDirtyInst,
P));
1671 ReverseNonLocalPtrDeps.
erase(ReversePtrDepIt);
1673 while (!ReversePtrDepsToAdd.
empty()) {
1674 ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.
back().first].insert(
1675 ReversePtrDepsToAdd.
back().second);
1680 assert(!NonLocalDepsMap.count(RemInst) &&
"RemInst got reinserted?");
1688void MemoryDependenceResults::verifyRemoved(
Instruction *
D)
const {
1690 for (
const auto &DepKV : LocalDeps) {
1691 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1692 assert(DepKV.second.getInst() !=
D &&
"Inst occurs in data structures");
1695 for (
const auto &DepKV : NonLocalPointerDeps) {
1696 assert(DepKV.first.getPointer() !=
D &&
"Inst occurs in NLPD map key");
1697 for (
const auto &Entry : DepKV.second.NonLocalDeps)
1698 assert(Entry.getResult().getInst() !=
D &&
"Inst occurs as NLPD value");
1701 for (
const auto &DepKV : NonLocalDepsMap) {
1702 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1703 const PerInstNLInfo &INLD = DepKV.second;
1704 for (
const auto &Entry : INLD.first)
1706 "Inst occurs in data structures");
1709 for (
const auto &DepKV : ReverseLocalDeps) {
1710 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1711 for (Instruction *Inst : DepKV.second)
1712 assert(Inst !=
D &&
"Inst occurs in data structures");
1715 for (
const auto &DepKV : ReverseNonLocalDeps) {
1716 assert(DepKV.first !=
D &&
"Inst occurs in data structures");
1717 for (Instruction *Inst : DepKV.second)
1718 assert(Inst !=
D &&
"Inst occurs in data structures");
1721 for (
const auto &DepKV : ReverseNonLocalPtrDeps) {
1722 assert(DepKV.first !=
D &&
"Inst occurs in rev NLPD map");
1724 for (ValueIsLoadPair
P : DepKV.second)
1725 assert(
P != ValueIsLoadPair(
D,
false) &&
P != ValueIsLoadPair(
D,
true) &&
1726 "Inst occurs in ReverseNonLocalPtrDeps map");
1743 DefaultBlockScanLimit.value_or(
1750 "Memory Dependence Analysis",
false,
true)
1778 unsigned DefaultBlockScanLimit)
1780 TLI(TLI), DT(DT), EEA(DT), DefaultBlockScanLimit(DefaultBlockScanLimit) {}
1783 FunctionAnalysisManager::Invalidator &Inv) {
1801 return DefaultBlockScanLimit;
1809 MemDep.emplace(
AA, AC,
TLI, DT,
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static bool isLoad(int Opcode)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Atomic ordering constants.
static const Function * getParent(const Value *V)
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static DeltaTreeNode * getRoot(void *Root)
This file defines the DenseMap class.
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static const unsigned int NumResultsLimit
static ModRefInfo GetLocation(const Instruction *Inst, MemoryLocation &Loc, const TargetLibraryInfo &TLI)
If the given instruction references a specific memory location, fill in Loc with the details,...
static void RemoveFromReverseMap(DenseMap< Instruction *, SmallPtrSet< KeyTy, 4 > > &ReverseMap, Instruction *Inst, KeyTy Val)
This is a helper function that removes Val from 'Inst's set in ReverseMap.
static void SortNonLocalDepInfoCache(MemoryDependenceResults::NonLocalDepInfo &Cache, unsigned NumSortedEntries)
Sort the NonLocalDepInfo cache, given a certain number of elements in the array that are already prop...
static void AssertSorted(MemoryDependenceResults::NonLocalDepInfo &Cache, int Count=-1)
This method is used when -debug is specified to verify that cache arrays are properly kept sorted.
This file provides utility analysis objects describing memory locations.
static bool isOrdered(const Instruction *I)
static bool isInvariantLoad(const Instruction *I, const Value *Ptr, 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.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
unsigned getNumber() const
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.
bool erase(const KeyT &Val)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
An instruction for ordering other memory operations.
const BasicBlock & getEntryBlock() const
unsigned getMaxBlockNumber() const
Return a value larger than the largest block number.
LLVM_ABI bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
bool isTerminator() const
LLVM_ABI bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
LLVM_ABI bool isVolatile() const LLVM_READONLY
Return true if this instruction has a volatile memory access.
A wrapper class for inspecting calls to intrinsic functions.
An instruction for reading from memory.
Value * getPointerOperand()
A memory dependence query can return one of three different answers.
bool isNonLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the block,...
static MemDepResult getNonLocal()
bool isNonFuncLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the function.
static MemDepResult getSelect()
static MemDepResult getClobber(Instruction *Inst)
bool isDef() const
Tests if this MemDepResult represents a query that is an instruction definition dependency.
static MemDepResult getUnknown()
bool isLocal() const
Tests if this MemDepResult represents a valid local query (Clobber/Def).
bool isUnknown() const
Tests if this MemDepResult represents a query which cannot and/or will not be computed.
static MemDepResult getNonFuncLocal()
static MemDepResult getDef(Instruction *Inst)
get methods: These are static ctor methods for creating various MemDepResult kinds.
Instruction * getInst() const
If this is a normal dependency, returns the instruction that is depended on.
An analysis that produces MemoryDependenceResults for a function.
LLVM_ABI MemoryDependenceResults run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI MemoryDependenceAnalysis()
Provides a lazy, caching interface for making common memory aliasing information queries,...
LLVM_ABI MemDepResult getSimplePointerDependencyFrom(const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst, unsigned *Limit, BatchAAResults &BatchAA)
std::vector< NonLocalDepEntry > NonLocalDepInfo
LLVM_ABI void invalidateCachedPredecessors()
Clears the PredIteratorCache info.
LLVM_ABI void invalidateCachedPointerInfo(Value *Ptr)
Invalidates cached information about the specified pointer, because it may be too conservative in mem...
LLVM_ABI MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst=nullptr, unsigned *Limit=nullptr)
Returns the instruction on which a memory location depends.
LLVM_ABI void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
LLVM_ABI MemoryDependenceResults(AAResults &AA, AssumptionCache &AC, const TargetLibraryInfo &TLI, DominatorTree &DT, unsigned DefaultBlockScanLimit)
LLVM_ABI MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB)
This analysis looks for other loads and stores with invariant.group metadata and the same pointer ope...
LLVM_ABI unsigned getDefaultBlockScanLimit() const
Some methods limit the number of instructions they will examine.
LLVM_ABI MemDepResult getDependency(Instruction *QueryInst)
Returns the instruction on which a memory operation depends.
LLVM_ABI const NonLocalDepInfo & getNonLocalCallDependency(CallBase *QueryCall)
Perform a full dependency query for the specified call, returning the set of blocks that the value is...
LLVM_ABI void getNonLocalPointerDependency(Instruction *QueryInst, SmallVectorImpl< NonLocalDepResult > &Result)
Perform a full dependency query for an access to the QueryInst's specified memory location,...
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation in the new PM.
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance.
bool runOnFunction(Function &) override
Pass Implementation stuff. This doesn't do any analysis eagerly.
~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 ...
LLVM_ABI SelectInst * getSelect() const
If the address expression depends on a select instruction (possibly through casts or GEPs),...
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< Value *, Value * > SelectAddrs
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()
const ParentTy * getParent() const
self_iterator getIterator()
Abstract Attribute helper functions.
@ BasicBlock
Various leaf nodes.
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool isStorePreservingMemoryLocation(const StoreInst *SI, const MemoryLocation &MemLoc, Align MemLocAlign, BatchAAResults &AA, unsigned ScanLimit)
Check whether SI, which may alias MemLoc, can be safely skipped.
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.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
const AnalysisOptions & getAnalysisOptions(const LLVMContext &C)
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
auto reverse(ContainerTy &&C)
bool isModSet(const ModRefInfo MRI)
void sort(IteratorTy Start, IteratorTy End)
bool isModOrRefSet(const ModRefInfo MRI)
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
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.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
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.
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...