24 #define DEBUG_TYPE "memoryssa"
41 auto Cached = CachedPreviousDef.find(
BB);
42 if (Cached != CachedPreviousDef.end())
43 return Cached->second;
50 VisitedBlocks.insert(
BB);
52 MemoryAccess *Result = getPreviousDefFromEnd(Pred, CachedPreviousDef);
53 CachedPreviousDef.insert({
BB, Result});
57 if (VisitedBlocks.count(
BB)) {
62 CachedPreviousDef.insert({
BB, Result});
66 if (VisitedBlocks.insert(
BB).second) {
73 bool UniqueIncomingAccess =
true;
77 auto *IncomingAccess = getPreviousDefFromEnd(Pred, CachedPreviousDef);
79 SingleAccess = IncomingAccess;
80 else if (IncomingAccess != SingleAccess)
81 UniqueIncomingAccess =
false;
82 PhiOps.push_back(IncomingAccess);
92 auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
94 if (Result == Phi && UniqueIncomingAccess && SingleAccess) {
101 Result = SingleAccess;
102 }
else if (Result == Phi && !(UniqueIncomingAccess && SingleAccess)) {
104 Phi = MSSA->createMemoryPhi(
BB);
120 InsertedPHIs.push_back(Phi);
126 VisitedBlocks.erase(
BB);
127 CachedPreviousDef.insert({
BB, Result});
138 if (
auto *LocalResult = getPreviousDefInBlock(MA))
141 return getPreviousDefRecursive(MA->
getBlock(), CachedPreviousDef);
153 if (!isa<MemoryUse>(MA)) {
156 if (Iter != Defs->rend())
162 if (!isa<MemoryUse>(U))
163 return cast<MemoryAccess>(&U);
178 CachedPreviousDef.
insert({
BB, &*Defs->rbegin()});
179 return &*Defs->rbegin();
182 return getPreviousDefRecursive(
BB, CachedPreviousDef);
192 if (
MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U))
193 tryRemoveTrivialPhi(UsePhi);
203 assert(Phi &&
"Can only remove concrete Phi.");
205 return tryRemoveTrivialPhi(Phi, OperRange);
207 template <
class RangeType>
211 if (NonOptPhis.count(Phi))
218 if (
Op == Phi ||
Op == Same)
223 Same = cast<MemoryAccess>(&*
Op);
235 return recursePhi(Same);
239 VisitedBlocks.clear();
240 InsertedPHIs.clear();
256 if (!RenameUses && !InsertedPHIs.empty()) {
259 assert((!Defs || (++Defs->begin() == Defs->end())) &&
260 "Block may have only a Phi or no defs");
263 if (RenameUses && InsertedPHIs.size()) {
271 if (
auto *MD = dyn_cast<MemoryDef>(FirstDef))
272 FirstDef = MD->getDefiningAccess();
278 for (
auto &MP : InsertedPHIs)
279 if (
MemoryPhi *Phi = cast_or_null<MemoryPhi>(MP))
290 assert(
i != -1 &&
"Should have found the basic block in the phi");
314 VisitedBlocks.clear();
315 InsertedPHIs.clear();
319 bool DefBeforeSameBlock =
false;
321 !(isa<MemoryPhi>(DefBefore) &&
323 DefBeforeSameBlock =
true;
329 if (DefBeforeSameBlock) {
334 return !isa<MemoryUse>(Usr) && Usr != MD;
348 unsigned NewPhiIndex = InsertedPHIs.size();
349 if (!DefBeforeSameBlock) {
371 for (
const auto &VH : InsertedPHIs)
372 if (
const auto *RealPHI = cast_or_null<MemoryPhi>(VH))
373 DefiningBlocks.
insert(RealPHI->getBlock());
379 for (
auto *BBIDF : IDFBlocks) {
382 MPhi = MSSA->createMemoryPhi(BBIDF);
383 NewInsertedPHIs.push_back(MPhi);
385 ExistingPhis.
insert(MPhi);
393 NonOptPhis.insert(MPhi);
395 for (
auto &MPhi : NewInsertedPHIs) {
396 auto *BBIDF = MPhi->getBlock();
399 MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef), Pred);
405 NewPhiIndex = InsertedPHIs.
size();
406 for (
auto &MPhi : NewInsertedPHIs) {
407 InsertedPHIs.push_back(&*MPhi);
408 FixupList.push_back(&*MPhi);
411 FixupList.push_back(MD);
416 unsigned NewPhiIndexEnd = InsertedPHIs.size();
418 while (!FixupList.empty()) {
419 unsigned StartingPHISize = InsertedPHIs.size();
420 fixupDefs(FixupList);
423 FixupList.
append(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());
427 unsigned NewPhiSize = NewPhiIndexEnd - NewPhiIndex;
429 tryRemoveTrivialPhis(
ArrayRef<WeakVH>(&InsertedPHIs[NewPhiIndex], NewPhiSize));
441 if (
auto *MD = dyn_cast<MemoryDef>(FirstDef))
447 for (
auto &MP : InsertedPHIs) {
448 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);
454 for (
auto &MP : ExistingPhis) {
455 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);
465 for (
auto &Var : Vars) {
466 MemoryAccess *NewDef = dyn_cast_or_null<MemoryAccess>(Var);
474 if (
MemoryPhi *Phi = dyn_cast<MemoryPhi>(NewDef))
475 NonOptPhis.erase(Phi);
478 if (++DefIter != Defs->end()) {
479 cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
490 Worklist.push_back(
S);
493 while (!Worklist.empty()) {
498 auto *FirstDef = &*Defs->
begin();
500 assert(!isa<MemoryPhi>(FirstDef) &&
501 "Should have already handled phi nodes!");
505 "Should have dominated the new access");
510 cast<MemoryDef>(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef));
524 Worklist.push_back(
S);
533 MPhi->unorderedDeleteIncomingBlock(
From);
534 tryRemoveTrivialPhi(MPhi);
550 tryRemoveTrivialPhi(MPhi);
561 MA = cast<MemoryAccess>(
Arg);
571 bool CloneWasSimplified,
574 if (
MemoryDef *DefMUD = dyn_cast<MemoryDef>(InsnDefining)) {
577 assert(DefMUDI &&
"Found MemoryUseOrDef with no Instruction.");
579 cast_or_null<Instruction>(VMap.
lookup(DefMUDI))) {
581 if (!CloneWasSimplified)
582 assert(InsnDefining &&
"Defining instruction cannot be nullptr.");
583 else if (!InsnDefining || isa<MemoryUse>(InsnDefining)) {
585 auto DefIt = DefMUD->getDefsIterator();
590 "Previous def must exist");
592 &*(--DefIt), VMap, MPhiMap, CloneWasSimplified, MSSA);
597 MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);
599 InsnDefining = NewDefPhi;
601 assert(InsnDefining &&
"Defining instruction cannot be nullptr.");
608 bool CloneWasSimplified) {
623 dyn_cast_or_null<Instruction>(VMap.
lookup(
Insn))) {
627 MPhiMap, CloneWasSimplified, MSSA),
628 CloneWasSimplified ?
nullptr : MUD,
629 CloneWasSimplified ?
false :
true);
645 auto *NewMPhi = MSSA->createMemoryPhi(BEBlock);
646 bool HasUniqueIncomingValue =
true;
648 for (
unsigned I = 0,
E = MPhi->getNumIncomingValues();
I !=
E; ++
I) {
651 if (IBB != Preheader) {
652 NewMPhi->addIncoming(
IV, IBB);
653 if (HasUniqueIncomingValue) {
656 else if (UniqueValue !=
IV)
657 HasUniqueIncomingValue =
false;
664 auto *AccFromPreheader = MPhi->getIncomingValueForBlock(Preheader);
665 MPhi->setIncomingValue(0, AccFromPreheader);
666 MPhi->setIncomingBlock(0, Preheader);
667 for (
unsigned I = MPhi->getNumIncomingValues() - 1;
I >= 1; --
I)
668 MPhi->unorderedDeleteIncoming(
I);
669 MPhi->addIncoming(NewMPhi, BEBlock);
673 tryRemoveTrivialPhi(NewMPhi);
679 bool IgnoreIncomingWithNoClones) {
683 assert(Phi && NewPhi &&
"Invalid Phi nodes.");
693 else if (IgnoreIncomingWithNoClones)
700 if (!NewPhiBBPreds.
count(IncBB))
704 if (
MemoryUseOrDef *IncMUD = dyn_cast<MemoryUseOrDef>(IncomingAccess)) {
707 assert(IncI &&
"Found MemoryUseOrDef with no Instruction.");
709 cast_or_null<Instruction>(VMap.
lookup(IncI))) {
712 "MemoryUseOrDef cannot be null, all preds processed.");
715 NewPhi->addIncoming(IncMUD, IncBB);
717 MemoryPhi *IncPhi = cast<MemoryPhi>(IncomingAccess);
719 NewPhi->addIncoming(NewDefPhi, IncBB);
721 NewPhi->addIncoming(IncPhi, IncBB);
725 MPhiMap[Phi] = SingleAccess;
736 "Cloned block should have no accesses");
740 MemoryPhi *NewPhi = MSSA->createMemoryPhi(NewBlock);
741 MPhiMap[MPhi] = NewPhi;
744 cloneUsesAndDefs(
BB, NewBlock, VMap, MPhiMap);
747 for (
auto BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
750 for (
auto BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
753 FixPhiIncomingValues(MPhi, cast<MemoryPhi>(NewPhi));
768 MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(P1);
769 cloneUsesAndDefs(
BB, P1, VM, MPhiMap,
true);
772 template <
typename Iter>
773 void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(
778 for (
auto *Exit : ExitBlocks)
782 Updates.push_back({DT.
Insert, NewExit, ExitSucc});
791 privateUpdateExitBlocksForClonedLoop(ExitBlocks,
std::begin(Arr),
798 auto GetPtr = [&](
const std::unique_ptr<ValueToValueMapTy> &
I) {
801 using MappedIteratorType =
804 auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr);
805 auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr);
806 privateUpdateExitBlocksForClonedLoop(ExitBlocks, MapBegin, MapEnd, DT);
814 for (
auto &Update : Updates) {
815 if (Update.getKind() == DT.
Insert)
816 InsertUpdates.push_back({DT.
Insert, Update.getFrom(), Update.getTo()});
818 DeleteUpdates.push_back({DT.
Delete, Update.getFrom(), Update.getTo()});
819 RevDeleteUpdates.push_back({DT.
Insert, Update.getFrom(), Update.getTo()});
823 if (!DeleteUpdates.empty()) {
824 if (!InsertUpdates.empty()) {
856 for (
auto &Update : DeleteUpdates)
875 return &*(--Defs->
end());
880 for (
auto *Pi : GD->template getChildren</*InverseEdge=*/true>(
BB)) {
895 if (IDom->getBlock() !=
BB) {
896 BB = IDom->getBlock();
902 assert(Count == 1 && Pred &&
"Single predecessor expected.");
915 auto FindNearestCommonDominator =
918 for (
auto *
BB : BBSet)
925 auto GetNoLongerDomBlocks =
928 if (PrevIDom == CurrIDom)
930 BlocksPrevDom.push_back(PrevIDom);
934 if (UpIDom == CurrIDom)
936 BlocksPrevDom.push_back(UpIDom);
961 for (
auto &Edge : Updates) {
963 auto &AddedBlockSet = PredMap[
BB].Added;
964 AddedBlockSet.
insert(Edge.getFrom());
970 for (
auto &BBPredPair : PredMap) {
971 auto *
BB = BBPredPair.first;
972 const auto &AddedBlockSet = BBPredPair.second.Added;
973 auto &PrevBlockSet = BBPredPair.second.Prev;
974 for (
auto *Pi : GD->template getChildren</*InverseEdge=*/true>(
BB)) {
975 if (!AddedBlockSet.count(Pi))
976 PrevBlockSet.insert(Pi);
977 EdgeCountMap[{Pi,
BB}]++;
980 if (PrevBlockSet.empty()) {
984 <<
"Adding a predecessor to a block with no predecessors. "
985 "This must be an edge added to a new, likely cloned, block. "
986 "Its memory accesses must be already correct, assuming completed "
987 "via the updateExitBlocksForClonedLoop API. "
988 "Assert a single such edge is added so no phi addition or "
989 "additional processing is required.\n");
990 assert(AddedBlockSet.size() == 1 &&
991 "Can only handle adding one predecessor to a new block.");
998 for (
auto *
BB : NewBlocks)
1006 for (
auto &Edge : Updates) {
1009 InsertedPhis.push_back(MSSA->createMemoryPhi(
BB));
1013 for (
auto &BBPredPair : PredMap) {
1014 auto *
BB = BBPredPair.first;
1015 const auto &PrevBlockSet = BBPredPair.second.Prev;
1016 const auto &AddedBlockSet = BBPredPair.second.Added;
1017 assert(!PrevBlockSet.empty() &&
1018 "At least one previous predecessor must exist.");
1027 for (
auto *AddedPred : AddedBlockSet) {
1028 auto *DefPn = GetLastDef(AddedPred);
1029 assert(DefPn !=
nullptr &&
"Unable to find last definition.");
1030 LastDefAddedPred[AddedPred] = DefPn;
1037 for (
auto *Pred : AddedBlockSet) {
1038 auto *LastDefForPred = LastDefAddedPred[Pred];
1039 for (
int I = 0,
E = EdgeCountMap[{Pred,
BB}];
I <
E; ++
I)
1045 auto *P1 = *PrevBlockSet.begin();
1050 bool InsertPhi =
false;
1051 for (
auto LastDefPredPair : LastDefAddedPred)
1052 if (DefP1 != LastDefPredPair.second) {
1068 for (
auto *Pred : AddedBlockSet) {
1069 auto *LastDefForPred = LastDefAddedPred[Pred];
1070 for (
int I = 0,
E = EdgeCountMap[{Pred,
BB}];
I <
E; ++
I)
1073 for (
auto *Pred : PrevBlockSet)
1074 for (
int I = 0,
E = EdgeCountMap[{Pred,
BB}];
I <
E; ++
I)
1081 BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);
1082 assert(PrevIDom &&
"Previous IDom should exists");
1084 assert(NewIDom &&
"BB should have a new valid idom");
1086 "New idom should dominate old idom");
1087 GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
1090 tryRemoveTrivialPhis(InsertedPhis);
1094 for (
auto &VH : InsertedPhis)
1095 if (
auto *MPhi = cast_or_null<MemoryPhi>(VH))
1096 BlocksToProcess.push_back(MPhi->getBlock());
1100 if (!BlocksToProcess.empty()) {
1103 BlocksToProcess.end());
1104 IDFs.setDefiningBlocks(DefiningBlocks);
1105 IDFs.calculate(IDFBlocks);
1109 for (
auto *BBIDF : IDFBlocks)
1111 auto *IDFPhi = MSSA->createMemoryPhi(BBIDF);
1112 InsertedPhis.push_back(IDFPhi);
1113 PhisToFill.
insert(IDFPhi);
1116 for (
auto *BBIDF : IDFBlocks) {
1118 assert(IDFPhi &&
"Phi must exist");
1119 if (!PhisToFill.
count(IDFPhi)) {
1122 for (
unsigned I = 0,
E = IDFPhi->getNumIncomingValues();
I <
E; ++
I)
1123 IDFPhi->setIncomingValue(
I, GetLastDef(IDFPhi->getIncomingBlock(
I)));
1125 for (
auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BBIDF))
1126 IDFPhi->addIncoming(GetLastDef(Pi), Pi);
1134 for (
auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {
1136 for (
auto &DefToReplaceUses : *DefsList) {
1137 BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();
1140 if (
MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Usr)) {
1141 BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);
1142 if (!DT.
dominates(DominatingBlock, DominatedBlock))
1143 U.set(GetLastDef(DominatedBlock));
1146 if (!DT.
dominates(DominatingBlock, DominatedBlock)) {
1151 assert(IDom &&
"Block must have a valid IDom.");
1152 U.set(GetLastDef(IDom->getBlock()));
1154 cast<MemoryUseOrDef>(Usr)->resetOptimized();
1161 tryRemoveTrivialPhis(InsertedPhis);
1165 template <
class WhereType>
1169 for (
auto *U : What->
users())
1170 if (
MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
1171 NonOptPhis.insert(PhiUser);
1180 if (
auto *MD = dyn_cast<MemoryDef>(What))
1202 if (Where != MemorySSA::InsertionPlace::BeforeTerminator)
1203 return moveTo(What,
BB, Where);
1208 return moveTo(What,
BB, MemorySSA::InsertionPlace::End);
1219 assert(Start->getParent() == To &&
"Incorrect Start instruction");
1225 auto *MUD = cast<MemoryUseOrDef>(FirstInNew);
1227 auto NextIt = ++MUD->getIterator();
1230 : cast<MemoryUseOrDef>(&*NextIt);
1242 if (Defs && !Defs->
empty())
1243 if (
auto *Phi = dyn_cast<MemoryPhi>(&*Defs->
begin()))
1244 tryRemoveTrivialPhi(Phi);
1251 "To block is expected to be free of MemoryAccesses.");
1252 moveAllAccesses(
From, To, Start);
1255 MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(
From), To);
1261 "From block is expected to have a single predecessor (To).");
1262 moveAllAccesses(
From, To, Start);
1265 MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(
From), To);
1270 bool IdenticalEdgesWereMerged) {
1272 "Access list should be null for a new block.");
1278 "Should have moved all predecessors.");
1281 assert(!Preds.
empty() &&
"Must be moving at least one predecessor to the "
1282 "new immediate predecessor.");
1283 MemoryPhi *NewPhi = MSSA->createMemoryPhi(New);
1287 if (!IdenticalEdgesWereMerged)
1289 "If identical edges were not merged, we cannot have duplicate "
1290 "blocks in the predecessors");
1293 NewPhi->addIncoming(MA, B);
1294 if (!IdenticalEdgesWereMerged)
1301 tryRemoveTrivialPhi(NewPhi);
1307 "Trying to remove the live on entry def");
1311 if (
MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
1319 "We can't delete this memory phi");
1321 NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
1327 if (!isa<MemoryUse>(MA) && !MA->
use_empty()) {
1341 assert(NewDefTarget != MA &&
"Going into an infinite loop");
1344 if (
auto *MUD = dyn_cast<MemoryUseOrDef>(U.
getUser()))
1345 MUD->resetOptimized();
1349 U.
set(NewDefTarget);
1359 if (!PhisToCheck.
empty()) {
1362 PhisToCheck.
clear();
1364 unsigned PhisSize = PhisToOptimize.size();
1365 while (PhisSize-- > 0)
1367 cast_or_null<MemoryPhi>(PhisToOptimize.pop_back_val()))
1368 tryRemoveTrivialPhi(MP);
1377 assert(TI &&
"Basic block expected to have a terminator instruction");
1379 if (!DeadBlocks.count(Succ))
1381 MP->unorderedDeleteIncomingBlock(
BB);
1382 tryRemoveTrivialPhi(MP);
1402 void MemorySSAUpdater::tryRemoveTrivialPhis(
ArrayRef<WeakVH> UpdatedPHIs) {
1403 for (
auto &VH : UpdatedPHIs)
1404 if (
auto *MPhi = cast_or_null<MemoryPhi>(VH))
1405 tryRemoveTrivialPhi(MPhi);
1411 auto BBI =
I->getIterator(), BBE =
BB->end();
1421 MPhi->unorderedDeleteIncomingBlock(
BB);
1422 UpdatedPHIs.push_back(MPhi);
1426 tryRemoveTrivialPhis(UpdatedPHIs);
1440 "New and old access must be in the same block");
1450 "New and old access must be in the same block");