29 #include "llvm/Config/llvm-config.h"
60 #define DEBUG_TYPE "memoryssa"
86 #ifdef EXPENSIVE_CHECKS
106 MemorySSAAnnotatedWriter(
const MemorySSA *
M) : MSSA(
M) {}
111 OS <<
"; " << *MA <<
"\n";
117 OS <<
"; " << *MA <<
"\n";
130 : MSSA(
M), Walker(
M->getWalker()), BAA(
M->getAA()) {}
135 OS <<
"; " << *MA <<
"\n";
144 OS <<
" - clobbered by ";
164 class MemoryLocOrCall {
169 : MemoryLocOrCall(MUD->getMemoryInst()) {}
171 : MemoryLocOrCall(MUD->getMemoryInst()) {}
174 if (
auto *
C = dyn_cast<CallBase>(Inst)) {
181 if (!isa<FenceInst>(Inst))
198 bool operator==(
const MemoryLocOrCall &Other)
const {
199 if (IsCall !=
Other.IsCall)
203 return Loc ==
Other.Loc;
205 if (
Call->getCalledOperand() !=
Other.Call->getCalledOperand())
208 return Call->arg_size() ==
Other.Call->arg_size() &&
210 Other.Call->arg_begin());
241 MLOC.getCall()->getCalledOperand()));
243 for (
const Value *
Arg : MLOC.getCall()->args())
248 static bool isEqual(
const MemoryLocOrCall &
LHS,
const MemoryLocOrCall &
RHS) {
263 bool VolatileUse =
Use->isVolatile();
264 bool VolatileClobber = MayClobber->
isVolatile();
266 if (VolatileUse && VolatileClobber)
282 return !(SeqCstUse || MayClobberIsAcquire);
285 template <
typename AliasAnalysisType>
288 const Instruction *UseInst, AliasAnalysisType &AA) {
290 assert(DefInst &&
"Defining instruction not actually an instruction");
292 if (
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
300 switch (II->getIntrinsicID()) {
301 case Intrinsic::invariant_start:
302 case Intrinsic::invariant_end:
303 case Intrinsic::assume:
304 case Intrinsic::experimental_noalias_scope_decl:
305 case Intrinsic::pseudoprobe:
307 case Intrinsic::dbg_addr:
308 case Intrinsic::dbg_declare:
309 case Intrinsic::dbg_label:
310 case Intrinsic::dbg_value:
317 if (
auto *CB = dyn_cast_or_null<CallBase>(UseInst)) {
322 if (
auto *DefLoad = dyn_cast<LoadInst>(DefInst))
323 if (
auto *UseLoad = dyn_cast_or_null<LoadInst>(UseInst))
330 template <
typename AliasAnalysisType>
332 const MemoryLocOrCall &UseMLOC,
333 AliasAnalysisType &AA) {
351 struct UpwardsMemoryQuery {
361 bool SkipSelfAccess =
false;
363 UpwardsMemoryQuery() =
default;
366 : IsCall(
isa<
CallBase>(Inst)), Inst(Inst), OriginalAccess(Access) {
378 if (
auto *LI = dyn_cast<LoadInst>(
I)) {
379 return I->hasMetadata(LLVMContext::MD_invariant_load) ||
403 bool AllowImpreciseClobber =
false) {
404 assert(MSSA.
dominates(ClobberAt, Start) &&
"Clobber doesn't dominate start?");
408 "liveOnEntry must clobber itself");
412 bool FoundClobber =
false;
418 while (!Worklist.empty()) {
426 if (MA == ClobberAt) {
427 if (
const auto *MD = dyn_cast<MemoryDef>(MA)) {
445 if (
const auto *MD = dyn_cast<MemoryDef>(MA)) {
451 "Found clobber before reaching ClobberAt!");
455 if (
const auto *MU = dyn_cast<MemoryUse>(MA)) {
458 "Can only find use in def chain if Start is a use");
462 assert(isa<MemoryPhi>(MA));
480 if (AllowImpreciseClobber)
485 assert((isa<MemoryPhi>(ClobberAt) || FoundClobber) &&
486 "ClobberAt never acted as a clobber");
493 class ClobberWalker {
495 using ListIndex = unsigned;
505 std::optional<ListIndex> Previous;
508 std::optional<ListIndex> Previous)
512 std::optional<ListIndex> Previous)
513 : DefPath(Loc,
Init,
Init, Previous) {}
519 UpwardsMemoryQuery *Query;
520 unsigned *UpwardWalkLimit;
531 assert(
From->getNumOperands() &&
"Phi with no operands?");
536 while ((Node = Node->getIDom())) {
545 struct UpwardsWalkResult {
558 walkToPhiOrClobber(DefPath &Desc,
const MemoryAccess *StopAt =
nullptr,
560 assert(!isa<MemoryUse>(Desc.Last) &&
"Uses don't exist in my world");
561 assert(UpwardWalkLimit &&
"Need a valid walk limit");
562 bool LimitAlreadyReached =
false;
567 if (!*UpwardWalkLimit) {
568 *UpwardWalkLimit = 1;
569 LimitAlreadyReached =
true;
574 if (Current == StopAt || Current == SkipStopAt)
575 return {Current,
false};
577 if (
auto *MD = dyn_cast<MemoryDef>(Current)) {
581 if (!--*UpwardWalkLimit)
582 return {Current,
true};
589 if (LimitAlreadyReached)
590 *UpwardWalkLimit = 0;
592 assert(isa<MemoryPhi>(Desc.Last) &&
593 "Ended at a non-clobber that's not a phi?");
594 return {Desc.Last,
false};
598 ListIndex PriorNode) {
602 PausedSearches.push_back(Paths.size());
610 struct TerminatedPath {
624 std::optional<TerminatedPath>
629 assert(!PausedSearches.empty() &&
"No searches to continue?");
633 while (!PausedSearches.empty()) {
635 DefPath &Node = Paths[PathIndex];
655 if (!VisitedPhis.
insert({Node.Last, Node.Loc}).second)
659 if (Query->SkipSelfAccess && Node.Loc == Query->StartingLoc) {
660 assert(isa<MemoryDef>(Query->OriginalAccess));
661 SkipStopWhere = Query->OriginalAccess;
664 UpwardsWalkResult Res = walkToPhiOrClobber(Node,
667 if (Res.IsKnownClobber) {
668 assert(Res.Result != StopWhere && Res.Result != SkipStopWhere);
672 TerminatedPath
Term{Res.Result, PathIndex};
673 if (!MSSA.
dominates(Res.Result, StopWhere))
677 Terminated.push_back(
Term);
681 if (Res.Result == StopWhere || Res.Result == SkipStopWhere) {
686 if (Res.Result != SkipStopWhere)
687 NewPaused.push_back(PathIndex);
692 addSearches(cast<MemoryPhi>(Res.Result), PausedSearches, PathIndex);
698 template <
typename T,
typename Walker>
699 struct generic_def_path_iterator
701 std::forward_iterator_tag, T *> {
702 generic_def_path_iterator() =
default;
703 generic_def_path_iterator(Walker *
W, ListIndex
N) :
W(
W),
N(
N) {}
707 generic_def_path_iterator &operator++() {
708 N = curNode().Previous;
712 bool operator==(
const generic_def_path_iterator &
O)
const {
713 if (
N.has_value() !=
O.N.has_value())
715 return !
N || *
N == *
O.N;
719 T &curNode()
const {
return W->Paths[*
N]; }
722 std::optional<ListIndex>
N;
725 using def_path_iterator = generic_def_path_iterator<DefPath, ClobberWalker>;
726 using const_def_path_iterator =
727 generic_def_path_iterator<const DefPath, const ClobberWalker>;
730 return make_range(def_path_iterator(
this,
From), def_path_iterator());
735 const_def_path_iterator());
740 TerminatedPath PrimaryClobber;
746 ListIndex defPathIndex(
const DefPath &
N)
const {
748 const DefPath *NP = &
N;
749 assert(!Paths.empty() && NP >= &Paths.front() && NP <= &Paths.back() &&
750 "Out of bounds DefPath!");
751 return NP - &Paths.front();
770 "Reset the optimization state.");
775 auto PriorPathsSize = Paths.size();
781 addSearches(Phi, PausedSearches, 0);
786 assert(!Paths.empty() &&
"Need a path to move");
787 auto Dom = Paths.begin();
788 for (
auto I = std::next(Dom),
E = Paths.end();
I !=
E; ++
I)
789 if (!MSSA.
dominates(
I->Clobber, Dom->Clobber))
791 auto Last = Paths.end() - 1;
793 std::iter_swap(Last, Dom);
799 "liveOnEntry wasn't treated as a clobber?");
801 const auto *
Target = getWalkTarget(Current);
804 assert(
all_of(TerminatedPaths, [&](
const TerminatedPath &
P) {
811 if (std::optional<TerminatedPath> Blocker = getBlockingAccess(
812 Target, PausedSearches, NewPaused, TerminatedPaths)) {
816 auto Iter =
find_if(def_path(Blocker->LastNode), [&](
const DefPath &
N) {
817 return defPathIndex(N) < PriorPathsSize;
819 assert(Iter != def_path_iterator());
821 DefPath &CurNode = *Iter;
822 assert(CurNode.Last == Current);
849 TerminatedPath
Result{CurNode.Last, defPathIndex(CurNode)};
856 if (NewPaused.empty()) {
857 MoveDominatedPathToEnd(TerminatedPaths);
864 for (ListIndex Paused : NewPaused) {
865 UpwardsWalkResult WR = walkToPhiOrClobber(Paths[Paused]);
866 if (WR.IsKnownClobber)
867 Clobbers.push_back({WR.Result, Paused});
870 DefChainEnd = WR.Result;
873 if (!TerminatedPaths.empty()) {
879 assert(DefChainEnd &&
"Failed to find dominating phi/liveOnEntry");
884 for (
const TerminatedPath &TP : TerminatedPaths) {
887 if (DT.
dominates(ChainBB, TP.Clobber->getBlock()))
888 Clobbers.push_back(TP);
894 if (!Clobbers.empty()) {
895 MoveDominatedPathToEnd(Clobbers);
901 [&](ListIndex
I) {
return Paths[
I].Last == DefChainEnd; }));
904 auto *DefChainPhi = cast<MemoryPhi>(DefChainEnd);
906 PriorPathsSize = Paths.size();
907 PausedSearches.
clear();
908 for (ListIndex
I : NewPaused)
909 addSearches(DefChainPhi, PausedSearches,
I);
912 Current = DefChainPhi;
916 void verifyOptResult(
const OptznResult &R)
const {
918 return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber);
922 void resetPhiOptznState() {
929 : MSSA(MSSA), DT(DT) {}
934 UpwardsMemoryQuery &Q,
unsigned &UpWalkLimit) {
937 UpwardWalkLimit = &UpWalkLimit;
945 if (
auto *MU = dyn_cast<MemoryUse>(Start))
946 Current = MU->getDefiningAccess();
948 DefPath FirstDesc(Q.StartingLoc, Current, Current, std::nullopt);
951 UpwardsWalkResult WalkResult = walkToPhiOrClobber(FirstDesc);
953 if (WalkResult.IsKnownClobber) {
954 Result = WalkResult.Result;
956 OptznResult OptRes = tryOptimizePhi(cast<MemoryPhi>(FirstDesc.Last),
957 Current, Q.StartingLoc);
958 verifyOptResult(OptRes);
959 resetPhiOptznState();
960 Result = OptRes.PrimaryClobber.Clobber;
963 #ifdef EXPENSIVE_CHECKS
964 if (!Q.SkipSelfAccess && *UpwardWalkLimit > 0)
971 struct RenamePassData {
978 : DTN(
D), ChildIt(It), IncomingVal(
M) {}
980 void swap(RenamePassData &
RHS) {
992 ClobberWalker Walker;
1009 bool UseInvariantGroup =
true);
1027 return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL,
false);
1032 return Walker->getClobberingMemoryAccessBase(MA, Loc, BAA, UWL);
1037 return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL,
false,
false);
1053 if (
auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1054 MUD->resetOptimized();
1070 return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL,
true);
1075 return Walker->getClobberingMemoryAccessBase(MA, Loc, BAA, UWL);
1091 if (
auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1092 MUD->resetOptimized();
1099 bool RenameAllUses) {
1102 auto It = PerBlockAccesses.
find(
S);
1104 if (It == PerBlockAccesses.
end() || !isa<MemoryPhi>(It->second->front()))
1107 auto *Phi = cast<MemoryPhi>(&Accesses->front());
1108 if (RenameAllUses) {
1109 bool ReplacementDone =
false;
1113 ReplacementDone =
true;
1115 (void) ReplacementDone;
1116 assert(ReplacementDone &&
"Incomplete phi during partial rename");
1126 bool RenameAllUses) {
1127 auto It = PerBlockAccesses.
find(
BB);
1129 if (It != PerBlockAccesses.
end()) {
1133 if (MUD->getDefiningAccess() ==
nullptr || RenameAllUses)
1134 MUD->setDefiningAccess(IncomingVal);
1135 if (isa<MemoryDef>(&L))
1151 bool SkipVisited,
bool RenameAllUses) {
1152 assert(Root &&
"Trying to rename accesses in an unreachable block");
1159 if (SkipVisited && AlreadyVisited)
1162 IncomingVal = renameBlock(Root->
getBlock(), IncomingVal, RenameAllUses);
1163 renameSuccessorPhis(Root->
getBlock(), IncomingVal, RenameAllUses);
1164 WorkStack.push_back({Root, Root->
begin(), IncomingVal});
1166 while (!WorkStack.empty()) {
1169 IncomingVal = WorkStack.back().IncomingVal;
1171 if (ChildIt == Node->end()) {
1172 WorkStack.pop_back();
1175 ++WorkStack.back().ChildIt;
1179 AlreadyVisited = !Visited.
insert(
BB).second;
1180 if (SkipVisited && AlreadyVisited) {
1187 IncomingVal = &*BlockDefs->rbegin();
1189 IncomingVal = renameBlock(
BB, IncomingVal, RenameAllUses);
1190 renameSuccessorPhis(
BB, IncomingVal, RenameAllUses);
1191 WorkStack.push_back({Child, Child->
begin(), IncomingVal});
1199 void MemorySSA::markUnreachableAsLiveOnEntry(
BasicBlock *
BB) {
1201 "Reachable block found while handling unreachable blocks");
1210 auto It = PerBlockAccesses.
find(
S);
1212 if (It == PerBlockAccesses.
end() || !isa<MemoryPhi>(It->second->front()))
1215 auto *Phi = cast<MemoryPhi>(&Accesses->front());
1219 auto It = PerBlockAccesses.
find(
BB);
1220 if (It == PerBlockAccesses.
end())
1223 auto &Accesses = It->second;
1224 for (
auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) {
1225 auto Next = std::next(AI);
1228 if (
auto *UseOrDef = dyn_cast<MemoryUseOrDef>(AI))
1229 UseOrDef->setDefiningAccess(LiveOnEntryDef.get());
1231 Accesses->erase(AI);
1237 : DT(DT),
F(Func), LiveOnEntryDef(nullptr), Walker(nullptr),
1238 SkipWalker(nullptr) {
1244 assert(AA &&
"No alias analysis?");
1246 buildMemorySSA(BatchAA);
1256 for (
const auto &Pair : PerBlockAccesses)
1262 auto Res = PerBlockAccesses.
insert(std::make_pair(
BB,
nullptr));
1265 Res.first->second = std::make_unique<AccessList>();
1266 return Res.first->second.get();
1270 auto Res = PerBlockDefs.
insert(std::make_pair(
BB,
nullptr));
1273 Res.first->second = std::make_unique<DefsList>();
1274 return Res.first->second.get();
1290 : MSSA(MSSA), Walker(Walker), AA(BAA), DT(DT) {}
1296 struct MemlocStackInfo {
1299 unsigned long StackEpoch;
1300 unsigned long PopEpoch;
1305 unsigned long LowerBound;
1308 unsigned long LastKill;
1312 void optimizeUsesInBlock(
const BasicBlock *,
unsigned long &,
unsigned long &,
1317 CachingWalker *Walker;
1336 void MemorySSA::OptimizeUses::optimizeUsesInBlock(
1337 const BasicBlock *
BB,
unsigned long &StackEpoch,
unsigned long &PopEpoch,
1343 if (Accesses ==
nullptr)
1350 !VersionStack.empty() &&
1351 "Version stack should have liveOnEntry sentinel dominating everything");
1352 BasicBlock *BackBlock = VersionStack.back()->getBlock();
1355 while (VersionStack.back()->getBlock() == BackBlock)
1356 VersionStack.pop_back();
1361 auto *MU = dyn_cast<MemoryUse>(&MA);
1363 VersionStack.push_back(&MA);
1368 if (MU->isOptimized())
1376 MemoryLocOrCall UseMLOC(MU);
1377 auto &LocInfo = LocStackInfo[UseMLOC];
1381 if (LocInfo.PopEpoch != PopEpoch) {
1382 LocInfo.PopEpoch = PopEpoch;
1383 LocInfo.StackEpoch = StackEpoch;
1395 if (LocInfo.LowerBoundBlock && LocInfo.LowerBoundBlock !=
BB &&
1400 LocInfo.LowerBound = 0;
1401 LocInfo.LowerBoundBlock = VersionStack[0]->getBlock();
1402 LocInfo.LastKillValid =
false;
1404 }
else if (LocInfo.StackEpoch != StackEpoch) {
1408 LocInfo.PopEpoch = PopEpoch;
1409 LocInfo.StackEpoch = StackEpoch;
1411 if (!LocInfo.LastKillValid) {
1412 LocInfo.LastKill = VersionStack.size() - 1;
1413 LocInfo.LastKillValid =
true;
1418 assert(LocInfo.LowerBound < VersionStack.size() &&
1419 "Lower bound out of range");
1420 assert(LocInfo.LastKill < VersionStack.size() &&
1421 "Last kill info out of range");
1423 unsigned long UpperBound = VersionStack.size() - 1;
1426 LLVM_DEBUG(
dbgs() <<
"MemorySSA skipping optimization of " << *MU <<
" ("
1427 << *(MU->getMemoryInst()) <<
")"
1428 <<
" because there are "
1429 << UpperBound - LocInfo.LowerBound
1430 <<
" stores to disambiguate\n");
1433 LocInfo.LastKillValid =
false;
1436 bool FoundClobberResult =
false;
1438 while (UpperBound > LocInfo.LowerBound) {
1439 if (isa<MemoryPhi>(VersionStack[UpperBound])) {
1445 MU, *AA, UpwardWalkLimit);
1447 while (VersionStack[UpperBound] != Result) {
1451 FoundClobberResult =
true;
1455 MemoryDef *MD = cast<MemoryDef>(VersionStack[UpperBound]);
1457 FoundClobberResult =
true;
1465 if (FoundClobberResult || UpperBound < LocInfo.LastKill) {
1466 MU->setDefiningAccess(VersionStack[UpperBound],
true);
1467 LocInfo.LastKill = UpperBound;
1471 MU->setDefiningAccess(VersionStack[LocInfo.LastKill],
true);
1473 LocInfo.LowerBound = VersionStack.size() - 1;
1474 LocInfo.LowerBoundBlock =
BB;
1484 unsigned long StackEpoch = 1;
1485 unsigned long PopEpoch = 1;
1488 optimizeUsesInBlock(DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack,
1492 void MemorySSA::placePHINodes(
1496 IDFs.setDefiningBlocks(DefiningBlocks);
1498 IDFs.calculate(IDFBlocks);
1501 for (
auto &
BB : IDFBlocks)
1502 createMemoryPhi(
BB);
1514 &StartingPoint, NextID++));
1523 bool InsertIntoDef =
false;
1532 Accesses = getOrCreateAccessList(&
B);
1533 Accesses->push_back(MUD);
1534 if (isa<MemoryDef>(MUD)) {
1535 InsertIntoDef =
true;
1537 Defs = getOrCreateDefsList(&
B);
1538 Defs->push_back(*MUD);
1544 placePHINodes(DefiningBlocks);
1555 markUnreachableAsLiveOnEntry(&
BB);
1562 return Walker.get();
1565 WalkerBase = std::make_unique<ClobberWalkerBase>(
this, DT);
1567 Walker = std::make_unique<CachingWalker>(
this, WalkerBase.get());
1568 return Walker.get();
1573 return SkipWalker.get();
1576 WalkerBase = std::make_unique<ClobberWalkerBase>(
this, DT);
1578 SkipWalker = std::make_unique<SkipSelfWalker>(
this, WalkerBase.get());
1579 return SkipWalker.get();
1589 auto *Accesses = getOrCreateAccessList(
BB);
1593 if (isa<MemoryPhi>(NewAccess)) {
1594 Accesses->push_front(NewAccess);
1595 auto *Defs = getOrCreateDefsList(
BB);
1596 Defs->push_front(*NewAccess);
1599 *Accesses, [](
const MemoryAccess &MA) {
return isa<MemoryPhi>(MA); });
1600 Accesses->insert(AI, NewAccess);
1601 if (!isa<MemoryUse>(NewAccess)) {
1602 auto *Defs = getOrCreateDefsList(
BB);
1604 *Defs, [](
const MemoryAccess &MA) {
return isa<MemoryPhi>(MA); });
1605 Defs->insert(DI, *NewAccess);
1609 Accesses->push_back(NewAccess);
1610 if (!isa<MemoryUse>(NewAccess)) {
1611 auto *Defs = getOrCreateDefsList(
BB);
1612 Defs->push_back(*NewAccess);
1615 BlockNumberingValid.erase(
BB);
1621 bool WasEnd = InsertPt == Accesses->end();
1623 if (!isa<MemoryUse>(What)) {
1624 auto *Defs = getOrCreateDefsList(
BB);
1630 Defs->push_back(*What);
1631 }
else if (isa<MemoryDef>(InsertPt)) {
1632 Defs->insert(InsertPt->getDefsIterator(), *What);
1634 while (InsertPt != Accesses->end() && !isa<MemoryDef>(InsertPt))
1637 if (InsertPt == Accesses->end())
1638 Defs->push_back(*What);
1640 Defs->insert(InsertPt->getDefsIterator(), *What);
1643 BlockNumberingValid.erase(
BB);
1653 if (
auto *MD = dyn_cast<MemoryDef>(What))
1664 prepareForMoveTo(What,
BB);
1670 if (isa<MemoryPhi>(What)) {
1672 "Can only move a Phi at the beginning of the block");
1674 ValueToMemoryAccess.erase(What->
getBlock());
1675 bool Inserted = ValueToMemoryAccess.insert({
BB, What}).second;
1677 assert(Inserted &&
"Cannot move a Phi to a block that already has one");
1680 prepareForMoveTo(What,
BB);
1689 ValueToMemoryAccess[
BB] = Phi;
1696 bool CreationMustSucceed) {
1697 assert(!isa<PHINode>(
I) &&
"Cannot create a defined access for a PHI");
1699 if (CreationMustSucceed)
1700 assert(NewAccess !=
nullptr &&
"Tried to create a memory access for a "
1701 "non-memory touching instruction");
1703 assert((!Definition || !isa<MemoryUse>(Definition)) &&
1704 "A use cannot be a defining access");
1714 if (
auto *
SI = dyn_cast<StoreInst>(
I)) {
1715 if (!
SI->isUnordered())
1717 }
else if (
auto *LI = dyn_cast<LoadInst>(
I)) {
1718 if (!LI->isUnordered())
1725 template <
typename AliasAnalysisType>
1727 AliasAnalysisType *AAP,
1736 switch (II->getIntrinsicID()) {
1739 case Intrinsic::assume:
1740 case Intrinsic::experimental_noalias_scope_decl:
1741 case Intrinsic::pseudoprobe:
1749 if (!
I->mayReadFromMemory() && !
I->mayWriteToMemory())
1754 Def = isa<MemoryDef>(Template);
1755 Use = isa<MemoryUse>(Template);
1756 #if !defined(NDEBUG)
1758 bool DefCheck, UseCheck;
1763 assert((
Def == DefCheck || !DefCheck) &&
1764 "Memory accesses should only be reduced");
1765 if (!
Def &&
Use != UseCheck) {
1767 assert(!UseCheck &&
"Invalid template");
1792 MUD =
new MemoryDef(
I->getContext(),
nullptr,
I,
I->getParent(), NextID++);
1794 MUD =
new MemoryUse(
I->getContext(),
nullptr,
I,
I->getParent());
1795 ValueToMemoryAccess[
I] = MUD;
1802 "Trying to remove memory access that still has uses");
1803 BlockNumbering.erase(MA);
1804 if (
auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1807 if (!isa<MemoryUse>(MA))
1811 if (
const auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1816 auto VMA = ValueToMemoryAccess.find(MemoryInst);
1817 if (VMA->second == MA)
1818 ValueToMemoryAccess.erase(VMA);
1831 if (!isa<MemoryUse>(MA)) {
1832 auto DefsIt = PerBlockDefs.
find(
BB);
1833 std::unique_ptr<DefsList> &Defs = DefsIt->second;
1836 PerBlockDefs.
erase(DefsIt);
1841 auto AccessIt = PerBlockAccesses.
find(
BB);
1842 std::unique_ptr<AccessList> &Accesses = AccessIt->second;
1844 Accesses->erase(MA);
1846 Accesses->remove(MA);
1848 if (Accesses->empty()) {
1849 PerBlockAccesses.
erase(AccessIt);
1850 BlockNumberingValid.erase(
BB);
1855 MemorySSAAnnotatedWriter Writer(
this);
1856 F.print(OS, &Writer);
1859 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1864 #if !defined(NDEBUG) && defined(EXPENSIVE_CHECKS)
1895 if (
auto *DTNode = DT->
getNode(Pred)) {
1897 if (
auto *DefList =
getBlockDefs(DTNode->getBlock())) {
1898 auto *LastAcc = &*(--DefList->end());
1899 assert(LastAcc == IncAcc &&
1900 "Incorrect incoming access into phi.");
1905 DTNode = DTNode->getIDom();
1923 if (BlockNumberingValid.empty())
1939 unsigned long LastNumber = 0;
1941 auto ThisNumberIter = BlockNumbering.find(&MA);
1942 assert(ThisNumberIter != BlockNumbering.end() &&
1943 "MemoryAccess has no domination number in a valid block!");
1945 unsigned long ThisNumber = ThisNumberIter->second;
1946 assert(ThisNumber > LastNumber &&
1947 "Domination numbers should be strictly increasing!");
1949 LastNumber = ThisNumber;
1954 "All valid BasicBlocks should exist in F -- dangling pointers?");
1976 ActualAccesses.push_back(Phi);
1977 ActualDefs.push_back(Phi);
1979 for (
const Use &U : Phi->
uses()) {
1980 assert(
dominates(Phi, U) &&
"Memory PHI does not dominate it's uses");
1987 "Incomplete MemoryPhi Node");
1991 "Incoming phi block not a block predecessor");
1998 assert((!MA || (
AL && (isa<MemoryUse>(MA) ||
DL))) &&
1999 "We have memory affecting instructions "
2000 "in this block but they are not in the "
2001 "access list or defs list");
2004 ActualAccesses.push_back(MA);
2007 ActualDefs.push_back(MA);
2009 for (
const Use &U : MD->
uses()) {
2011 "Memory Def does not dominate it's uses");
2025 assert(
AL->size() == ActualAccesses.size() &&
2026 "We don't have the same number of accesses in the block as on the "
2028 assert((
DL || ActualDefs.size() == 0) &&
2029 "Either we should have a defs list, or we should have no defs");
2031 "We don't have the same number of defs in the block as on the "
2033 auto ALI =
AL->begin();
2034 auto AAI = ActualAccesses.begin();
2035 while (ALI !=
AL->end() && AAI != ActualAccesses.end()) {
2036 assert(&*ALI == *AAI &&
"Not the same accesses in the same order");
2040 ActualAccesses.
clear();
2043 auto ADI = ActualDefs.begin();
2044 while (DLI !=
DL->
end() && ADI != ActualDefs.end()) {
2045 assert(&*DLI == *ADI &&
"Not the same defs in the same order");
2060 "Null def but use not point to live on entry def");
2063 "Did not find use in def's use list");
2072 void MemorySSA::renumberBlock(
const BasicBlock *
B)
const {
2074 unsigned long CurrentNumber = 0;
2076 assert(
AL !=
nullptr &&
"Asking to renumber an empty block");
2077 for (
const auto &
I : *
AL)
2078 BlockNumbering[&
I] = ++CurrentNumber;
2079 BlockNumberingValid.insert(
B);
2090 "Asking for local domination when accesses are in different blocks!");
2092 if (Dominatee == Dominator)
2105 if (!BlockNumberingValid.count(DominatorBlock))
2106 renumberBlock(DominatorBlock);
2108 unsigned long DominatorNum = BlockNumbering.lookup(Dominator);
2110 assert(DominatorNum != 0 &&
"Block was not numbered properly");
2111 unsigned long DominateeNum = BlockNumbering.lookup(Dominatee);
2112 assert(DominateeNum != 0 &&
"Block was not numbered properly");
2113 return DominatorNum < DominateeNum;
2118 if (Dominator == Dominatee)
2130 const Use &Dominatee)
const {
2132 BasicBlock *UseBB = MP->getIncomingBlock(Dominatee);
2134 if (UseBB != Dominator->
getBlock())
2155 switch (getValueID()) {
2156 case MemoryPhiVal:
return static_cast<const MemoryPhi *
>(
this)->
print(OS);
2157 case MemoryDefVal:
return static_cast<const MemoryDef *
>(
this)->
print(OS);
2158 case MemoryUseVal:
return static_cast<const MemoryUse *
>(
this)->
print(OS);
2167 if (A && A->getID())
2173 OS << getID() <<
" = MemoryDef(";
2177 if (isOptimized()) {
2179 printID(getOptimized());
2184 ListSeparator
LS(
",");
2185 OS << getID() <<
" = MemoryPhi(";
2186 for (
const auto &
Op : operands()) {
2192 OS <<
BB->getName();
2194 BB->printAsOperand(OS,
false);
2196 if (
unsigned ID = MA->
getID())
2208 if (UO && UO->
getID())
2217 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2237 MemorySSAAnnotatedWriter MSSAWriter;
2241 :
F(
F), MSSAWriter(&MSSA) {}
2244 MemorySSAAnnotatedWriter &
getWriter() {
return MSSAWriter; }
2287 [](std::string &
S,
unsigned &
I,
unsigned Idx) ->
void {
2288 std::string Str =
S.substr(
I, Idx -
I);
2290 if (SR.
count(
" = MemoryDef(") || SR.
count(
" = MemoryPhi(") ||
2291 SR.
count(
"MemoryUse("))
2310 return getNodeLabel(Node, CFGInfo).find(
';') != std::string::npos
2311 ?
"style=filled, fillcolor=lightpink"
2319 auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
2358 OS <<
"MemorySSA for function: " <<
F.getName() <<
"\n";
2368 OS <<
"MemorySSA (walker) for function: " <<
F.getName() <<
"\n";
2369 MemorySSAWalkerAnnotatedWriter Writer(&MSSA);
2370 F.print(OS, &Writer);
2397 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2398 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2421 assert(!isa<MemoryUse>(StartingAccess) &&
"Use cannot be defining access");
2424 if (
auto *StartingUseOrDef = dyn_cast<MemoryUseOrDef>(StartingAccess)) {
2426 return StartingUseOrDef;
2428 I = StartingUseOrDef->getMemoryInst();
2432 if (!isa<CallBase>(
I) &&
I->isFenceLike())
2433 return StartingUseOrDef;
2436 UpwardsMemoryQuery Q;
2437 Q.OriginalAccess = StartingAccess;
2438 Q.StartingLoc = Loc;
2446 Walker.findClobber(BAA, StartingAccess, Q, UpwardWalkLimit);
2448 dbgs() <<
"Clobber starting at access " << *StartingAccess <<
"\n";
2450 dbgs() <<
" for instruction " << *
I <<
"\n";
2451 dbgs() <<
" is " << *Clobber <<
"\n";
2458 if (!
I.hasMetadata(LLVMContext::MD_invariant_group) ||
I.isVolatile())
2470 if (isa<Constant>(PointerOperand))
2475 PointerUsesQueue.push_back(PointerOperand);
2482 while (!PointerUsesQueue.empty()) {
2485 "Null or GlobalValue should not be inserted");
2487 for (
const User *Us :
Ptr->users()) {
2488 auto *U = dyn_cast<Instruction>(Us);
2489 if (!U || U == &
I || !DT.
dominates(U, MostDominatingInstruction))
2493 if (isa<BitCastInst>(U)) {
2494 PointerUsesQueue.push_back(U);
2497 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(U)) {
2498 if (
GEP->hasAllZeroIndices())
2499 PointerUsesQueue.push_back(U);
2506 if (U->hasMetadata(LLVMContext::MD_invariant_group) &&
2508 MostDominatingInstruction = U;
2512 return MostDominatingInstruction == &
I ? nullptr : MostDominatingInstruction;
2517 bool SkipSelf,
bool UseInvariantGroup) {
2518 auto *StartingAccess = dyn_cast<MemoryUseOrDef>(MA);
2520 if (!StartingAccess)
2523 if (UseInvariantGroup) {
2525 *StartingAccess->getMemoryInst(), MSSA->
getDomTree())) {
2526 assert(isa<LoadInst>(
I) || isa<StoreInst>(
I));
2530 if (isa<MemoryUse>(ClobberMA))
2531 return ClobberMA->getDefiningAccess();
2536 bool IsOptimized =
false;
2541 if (StartingAccess->isOptimized()) {
2542 if (!SkipSelf || !isa<MemoryDef>(StartingAccess))
2543 return StartingAccess->getOptimized();
2547 const Instruction *
I = StartingAccess->getMemoryInst();
2551 if (!isa<CallBase>(
I) &&
I->isFenceLike())
2552 return StartingAccess;
2554 UpwardsMemoryQuery Q(
I, StartingAccess);
2558 StartingAccess->setOptimized(LiveOnEntry);
2565 MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
2570 StartingAccess->setOptimized(DefiningAccess);
2571 return DefiningAccess;
2575 Walker.findClobber(BAA, DefiningAccess, Q, UpwardWalkLimit);
2576 StartingAccess->setOptimized(OptimizedAccess);
2578 OptimizedAccess = StartingAccess->getOptimized();
2580 LLVM_DEBUG(
dbgs() <<
"Starting Memory SSA clobber for " << *
I <<
" is ");
2582 LLVM_DEBUG(
dbgs() <<
"Optimized Memory SSA clobber for " << *
I <<
" is ");
2586 if (SkipSelf && isa<MemoryPhi>(OptimizedAccess) &&
2587 isa<MemoryDef>(StartingAccess) && UpwardWalkLimit) {
2588 assert(isa<MemoryDef>(Q.OriginalAccess));
2589 Q.SkipSelfAccess =
true;
2590 Result = Walker.findClobber(BAA, OptimizedAccess, Q, UpwardWalkLimit);
2592 Result = OptimizedAccess;
2594 LLVM_DEBUG(
dbgs() <<
"Result Memory SSA clobber [SkipSelf = " << SkipSelf);
2603 if (
auto *
Use = dyn_cast<MemoryUseOrDef>(MA))
2604 return Use->getDefiningAccess();
2610 if (
auto *
Use = dyn_cast<MemoryUseOrDef>(StartingAccess))
2611 return Use->getDefiningAccess();
2612 return StartingAccess;
2627 bool upward_defs_iterator::IsGuaranteedLoopInvariant(
const Value *
Ptr)
const {
2628 auto IsGuaranteedLoopInvariantBase = [](
const Value *
Ptr) {
2629 Ptr =
Ptr->stripPointerCasts();
2630 if (!isa<Instruction>(
Ptr))
2632 return isa<AllocaInst>(
Ptr);
2635 Ptr =
Ptr->stripPointerCasts();
2636 if (
auto *
I = dyn_cast<Instruction>(
Ptr)) {
2637 if (
I->getParent()->isEntryBlock())
2640 if (
auto *
GEP = dyn_cast<GEPOperator>(
Ptr)) {
2641 return IsGuaranteedLoopInvariantBase(
GEP->getPointerOperand()) &&
2642 GEP->hasAllConstantIndices();
2644 return IsGuaranteedLoopInvariantBase(
Ptr);