41 #define DEBUG_TYPE "wasm-cfg-stackify"
43 STATISTIC(NumCallUnwindMismatches,
"Number of call unwind mismatches found");
44 STATISTIC(NumCatchUnwindMismatches,
"Number of catch unwind mismatches found");
48 StringRef getPassName()
const override {
return "WebAssembly CFG Stackify"; }
64 int EndNo = End->getNumber();
65 if (!ScopeTops[EndNo] || ScopeTops[EndNo]->getNumber() > Begin->
getNumber())
66 ScopeTops[EndNo] = Begin;
85 std::pair<const MachineBasicBlock *, const MachineInstr *>;
144 ~WebAssemblyCFGStackify()
override { releaseMemory(); }
145 void releaseMemory()
override;
151 "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes",
false,
155 return new WebAssemblyCFGStackify();
167 if (MO.isMBB() && MO.getMBB() ==
MBB)
177 template <
typename Container>
180 const Container &AfterSet) {
181 auto InsertPos =
MBB->
end();
183 if (BeforeSet.count(&*std::prev(InsertPos))) {
186 for (
auto Pos = InsertPos,
E =
MBB->
begin(); Pos !=
E; --Pos)
187 assert(!AfterSet.count(&*std::prev(Pos)));
201 template <
typename Container>
204 const Container &AfterSet) {
206 while (InsertPos !=
MBB->
end()) {
207 if (AfterSet.count(&*InsertPos)) {
210 for (
auto Pos = InsertPos,
E =
MBB->
end(); Pos !=
E; ++Pos)
211 assert(!BeforeSet.count(&*Pos));
220 void WebAssemblyCFGStackify::registerScope(
MachineInstr *Begin,
222 BeginToEnd[Begin] = End;
223 EndToBegin[End] = Begin;
227 void WebAssemblyCFGStackify::registerTryScope(
MachineInstr *Begin,
230 registerScope(Begin, End);
231 TryToEHPad[Begin] = EHPad;
232 EHPadToTry[EHPad] = Begin;
235 void WebAssemblyCFGStackify::unregisterScope(
MachineInstr *Begin) {
239 BeginToEnd.
erase(Begin);
240 EndToBegin.
erase(End);
244 TryToEHPad.
erase(Begin);
245 EHPadToTry.
erase(EHPad);
255 auto &MDT = getAnalysis<MachineDominatorTree>();
263 bool IsBranchedTo =
false;
266 if (Pred->getNumber() < MBBNumber) {
267 Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
277 assert(&
MBB != &MF.
front() &&
"Header blocks shouldn't have predecessors");
284 if (ScopeTop->getNumber() > Header->getNumber()) {
286 I = std::next(ScopeTop->getIterator());
301 for (
const auto &
MI : *Header) {
306 auto *LoopBottom = BeginToEnd[&
MI]->getParent()->getPrevNode();
319 if (
MI.getOpcode() == WebAssembly::BLOCK ||
320 MI.getOpcode() == WebAssembly::TRY) {
332 MI.getOpcode() == WebAssembly::END_LOOP ||
333 MI.getOpcode() == WebAssembly::END_TRY)
338 if (
MI.isTerminator())
343 for (
auto I = Header->getFirstTerminator(),
E = Header->begin();
I !=
E;
345 if (std::prev(
I)->isDebugInstr() || std::prev(
I)->isPosition())
348 AfterSet.
insert(&*std::prev(
I));
357 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
358 TII.get(WebAssembly::BLOCK))
364 for (
auto &
MI :
MBB) {
368 MI.getOpcode() == WebAssembly::TRY)
376 if (
MI.getOpcode() == WebAssembly::END_LOOP ||
377 MI.getOpcode() == WebAssembly::END_TRY) {
378 if (EndToBegin[&
MI]->
getParent()->getNumber() >= Header->getNumber())
391 registerScope(Begin, End);
394 updateScopeTops(Header, &
MBB);
400 const auto &MLI = getAnalysis<MachineLoopInfo>();
401 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
413 if (Iter == MF.
end()) {
414 getAppendixBlock(MF);
422 for (
const auto &
MI :
MBB) {
425 if (
MI.getOpcode() == WebAssembly::END_LOOP)
443 for (
const auto &
MI :
MBB)
445 if (
MI.getOpcode() == WebAssembly::END_LOOP)
454 : (*AfterLoop->pred_rbegin())->findBranchDebugLoc();
456 BuildMI(*AfterLoop, InsertPos, EndDL,
TII.get(WebAssembly::END_LOOP));
457 registerScope(Begin, End);
461 "With block sorting the outermost loop for a block should be first.");
462 updateScopeTops(&
MBB, AfterLoop);
468 auto &MDT = getAnalysis<MachineDominatorTree>();
470 const auto &MLI = getAnalysis<MachineLoopInfo>();
471 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
479 if (Pred->getNumber() < MBBNumber) {
480 Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
482 "Explicit branch to an EH pad!");
495 if (Iter == MF.
end()) {
496 getAppendixBlock(MF);
508 if (ScopeTop->getNumber() > Header->getNumber()) {
510 I = std::next(ScopeTop->getIterator());
525 for (
const auto &
MI : *Header) {
530 auto *LoopBottom = BeginToEnd[&
MI]->getParent()->getPrevNode();
541 if (
MI.getOpcode() == WebAssembly::BLOCK ||
542 MI.getOpcode() == WebAssembly::TRY)
548 MI.getOpcode() == WebAssembly::END_LOOP ||
549 MI.getOpcode() == WebAssembly::END_TRY)
554 if (
MI.isTerminator())
565 auto TermPos = Header->getFirstTerminator();
566 if (TermPos == Header->end() ||
567 TermPos->getOpcode() != WebAssembly::RETHROW) {
574 if (
MI.getIterator() != Header->begin() &&
575 std::prev(
MI.getIterator())->isEHLabel()) {
576 AfterSet.
insert(&*std::prev(
MI.getIterator()));
577 ThrowingCall = &*std::prev(
MI.getIterator());
592 : Header->getFirstTerminator();
593 for (
auto I = SearchStartPt,
E = Header->begin();
I !=
E; --
I) {
594 if (std::prev(
I)->isDebugInstr() || std::prev(
I)->isPosition())
597 AfterSet.
insert(&*std::prev(
I));
605 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
606 TII.get(WebAssembly::TRY))
612 for (
const auto &
MI : *Cont) {
616 MI.getOpcode() == WebAssembly::BLOCK)
621 if (
MI.getOpcode() == WebAssembly::END_TRY)
629 if (
MI.getOpcode() == WebAssembly::END_LOOP) {
632 if (EndToBegin[&
MI]->
getParent()->getNumber() > Header->getNumber())
647 TII.get(WebAssembly::END_TRY));
648 registerTryScope(Begin, End, &
MBB);
661 for (
auto *End : {&
MBB, Cont})
662 updateScopeTops(Header, End);
665 void WebAssemblyCFGStackify::removeUnnecessaryInstrs(
MachineFunction &MF) {
701 for (
auto &
MBB : MF) {
725 if (Analyzable && ((
Cond.empty() &&
TBB &&
TBB == Cont) ||
726 (!
Cond.empty() && FBB && FBB == Cont))) {
727 bool ErasedUncondBr =
false;
728 (void)ErasedUncondBr;
729 for (
auto I = EHPadLayoutPred->
end(),
E = EHPadLayoutPred->
begin();
731 auto PrevI = std::prev(
I);
732 if (PrevI->isTerminator()) {
734 PrevI->eraseFromParent();
735 ErasedUncondBr =
true;
739 assert(ErasedUncondBr &&
"Unconditional branch not erased!");
755 for (
auto &
MBB : MF) {
756 for (
auto &
MI :
MBB) {
757 if (
MI.getOpcode() != WebAssembly::TRY)
766 for (
auto B = Try->
getIterator(),
E = std::next(EndTry->getIterator());
768 std::prev(
B)->getOpcode() == WebAssembly::BLOCK &&
770 std::prev(
B)->getOperand(0).getImm() == RetType;
772 ToDelete.push_back(&*std::prev(
B));
773 ToDelete.push_back(&*
E);
777 for (
auto *
MI : ToDelete) {
778 if (
MI->getOpcode() == WebAssembly::BLOCK)
780 MI->eraseFromParent();
793 for (
auto &
MI : Split) {
794 for (
auto &MO :
MI.explicit_uses()) {
795 if (!MO.isReg() || MO.getReg().isPhysical())
798 if (
Def->getParent() == &
MBB)
799 MFI.unstackifyVReg(MO.getReg());
832 if (!MFI.isVRegStackified(TeeReg)) {
834 MFI.unstackifyVReg(DefReg);
840 MI.eraseFromParent();
847 void WebAssemblyCFGStackify::addTryDelegate(
MachineInstr *RangeBegin,
859 AfterSet.
insert(RangeBegin);
862 if (std::prev(
I)->isDebugInstr() || std::prev(
I)->isPosition())
865 AfterSet.
insert(&*std::prev(
I));
874 TII.get(WebAssembly::TRY))
881 if (DelegateDest != FakeCallerBB)
884 auto SplitPos = std::next(RangeEnd->
getIterator());
885 if (SplitPos == EndBB->end()) {
888 MF.
insert(std::next(EndBB->getIterator()), DelegateBB);
889 EndBB->addSuccessor(DelegateBB);
898 bool PostSplit =
true;
899 if (EndBB->isEHPad()) {
929 PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->
end());
930 PostBB->transferSuccessors(PreBB);
949 MF.
insert(PostBB->getIterator(), PreBB);
950 MF.
insert(PostBB->getIterator(), DelegateBB);
951 PreBB->
splice(PreBB->
end(), PostBB, PostBB->begin(), SplitPos);
965 registerTryScope(Try, Delegate,
nullptr);
968 bool WebAssemblyCFGStackify::fixCallUnwindMismatches(
MachineFunction &MF) {
1091 using TryRange = std::pair<MachineInstr *, MachineInstr *>;
1099 bool SeenThrowableInstInBB =
false;
1101 if (
MI.getOpcode() == WebAssembly::TRY)
1102 EHPadStack.pop_back();
1104 EHPadStack.push_back(
MI.getParent());
1113 SeenThrowableInstInBB =
true;
1124 if (Succ->isEHPad()) {
1129 if (EHPadStack.back() == UnwindDest)
1135 std::prev(RangeBegin->
getIterator())->isEHLabel())
1136 RangeBegin = &*std::prev(RangeBegin->
getIterator());
1137 if (std::next(RangeEnd->getIterator()) !=
MBB.
end() &&
1138 std::next(RangeEnd->getIterator())->isEHLabel())
1139 RangeEnd = &*std::next(RangeEnd->getIterator());
1142 UnwindDestToTryRanges[UnwindDest].push_back(
1143 TryRange(RangeBegin, RangeEnd));
1145 <<
"\nCall = " <<
MI
1146 <<
"\nOriginal dest = " << UnwindDest->
getName()
1147 <<
" Current dest = " << EHPadStack.back()->getName()
1152 assert(EHPadStack.empty());
1159 MachineInstr *RangeBegin =
nullptr, *RangeEnd =
nullptr;
1163 UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back(
1164 TryRange(RangeBegin, RangeEnd));
1167 <<
"\nRange begin = " << *RangeBegin
1168 <<
"Range end = " << *RangeEnd
1169 <<
"\nOriginal dest = caller Current dest = "
1170 << CurrentDest->getName() <<
"\n\n");
1171 RangeBegin = RangeEnd =
nullptr;
1175 bool SeenThrowableInstInBB =
false;
1183 SeenThrowableInstInBB =
true;
1188 RecordCallerMismatchRange(EHPadStack.back());
1192 else if (EHPadStack.empty() || !MayThrow) {
1200 RangeBegin = RangeEnd = &
MI;
1206 if (
MI.getOpcode() == WebAssembly::TRY)
1207 EHPadStack.pop_back();
1209 EHPadStack.push_back(
MI.getParent());
1213 RecordCallerMismatchRange(EHPadStack.back());
1216 assert(EHPadStack.empty());
1219 if (UnwindDestToTryRanges.
empty())
1223 for (
auto &
P : UnwindDestToTryRanges) {
1224 NumCallUnwindMismatches +=
P.second.size();
1226 auto &TryRanges =
P.second;
1228 for (
auto Range : TryRanges) {
1229 MachineInstr *RangeBegin =
nullptr, *RangeEnd =
nullptr;
1230 std::tie(RangeBegin, RangeEnd) =
Range;
1240 if (Succ->isEHPad()) {
1248 addTryDelegate(RangeBegin, RangeEnd, UnwindDest);
1255 bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(
MachineFunction &MF) {
1301 if (
MI.getOpcode() == WebAssembly::TRY)
1302 EHPadStack.pop_back();
1304 EHPadStack.push_back(&
MBB);
1310 if (
MI.getOpcode() == WebAssembly::CATCH_ALL) {
1315 else if (EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
1317 <<
"'s unwind destination does not exist anymore"
1323 else if (!EHPadStack.empty() && !EHInfo->hasUnwindDest(EHPad)) {
1324 EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF);
1326 <<
"- Catch unwind mismatch:\nEHPad = " << EHPad->
getName()
1327 <<
" Original dest = caller Current dest = "
1328 << EHPadStack.back()->getName() <<
"\n\n");
1333 else if (!EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
1334 auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
1335 if (EHPadStack.back() != UnwindDest) {
1336 EHPadToUnwindDest[EHPad] = UnwindDest;
1338 << EHPad->
getName() <<
" Original dest = "
1339 << UnwindDest->
getName() <<
" Current dest = "
1340 << EHPadStack.back()->getName() <<
"\n\n");
1344 EHPadStack.push_back(EHPad);
1349 assert(EHPadStack.empty());
1350 if (EHPadToUnwindDest.
empty())
1352 NumCatchUnwindMismatches += EHPadToUnwindDest.
size();
1355 for (
auto &
P : EHPadToUnwindDest) {
1360 addTryDelegate(Try, EndTry, UnwindDest);
1408 for (
auto &
MBB : MF) {
1409 for (
auto &
MI :
MBB) {
1410 if (
MI.isTerminator()) {
1411 for (
auto &MO :
MI.operands()) {
1412 if (MO.isMBB() && NewEndTryBBs.
count(MO.getMBB())) {
1413 auto *BrDest = MO.getMBB();
1414 bool FoundEndBlock =
false;
1415 for (; std::next(BrDest->getIterator()) != MF.end();
1416 BrDest = BrDest->getNextNode()) {
1417 for (
const auto &
MI : *BrDest) {
1419 FoundEndBlock =
true;
1437 void WebAssemblyCFGStackify::recalculateScopeTops(
MachineFunction &MF) {
1447 switch (
MI.getOpcode()) {
1449 case WebAssembly::END_LOOP:
1450 case WebAssembly::END_TRY:
1454 case WebAssembly::CATCH:
1455 case WebAssembly::CATCH_ALL:
1470 void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(
MachineFunction &MF) {
1473 if (MFI.getResults().empty())
1485 Worklist.push_back(MF.
rbegin()->rbegin());
1491 if (
MI.isPosition() ||
MI.isDebugInstr())
1493 switch (
MI.getOpcode()) {
1494 case WebAssembly::END_TRY: {
1498 auto *EHPad = TryToEHPad.
lookup(EndToBegin[&
MI]);
1502 if (NextIt != EHPad->
rend())
1503 Worklist.push_back(NextIt);
1507 case WebAssembly::END_LOOP:
1509 EndToBegin[&
MI]->getOperand(0).setImm(int32_t(RetType));
1521 while (!Worklist.empty())
1531 TII.get(WebAssembly::END_FUNCTION));
1540 for (
auto &
MBB : MF)
1541 placeLoopMarker(
MBB);
1543 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1544 for (
auto &
MBB : MF) {
1548 MF.getFunction().hasPersonalityFn())
1549 placeTryMarker(
MBB);
1552 placeBlockMarker(
MBB);
1557 MF.getFunction().hasPersonalityFn()) {
1558 bool Changed = fixCallUnwindMismatches(MF);
1559 Changed |= fixCatchUnwindMismatches(MF);
1561 recalculateScopeTops(MF);
1565 unsigned WebAssemblyCFGStackify::getBranchDepth(
1577 unsigned WebAssemblyCFGStackify::getDelegateDepth(
1579 if (
MBB == FakeCallerBB)
1580 return Stack.size();
1586 return getBranchDepth(Stack,
MBB);
1604 if (
X.first == EndTry->
getParent() &&
X.second == EndTry)
1612 unsigned WebAssemblyCFGStackify::getRethrowDepth(
1639 if (End->getOpcode() == WebAssembly::END_TRY) {
1640 auto *EHPad = TryToEHPad[EndToBegin[End]];
1641 if (EHPadStack.back() == EHPad)
1650 void WebAssemblyCFGStackify::rewriteDepthImmediates(
MachineFunction &MF) {
1656 switch (
MI.getOpcode()) {
1657 case WebAssembly::BLOCK:
1658 case WebAssembly::TRY:
1659 assert(ScopeTops[
Stack.back().first->getNumber()]->getNumber() <=
1661 "Block/try marker should be balanced");
1666 assert(
Stack.back().first == &
MBB &&
"Loop top should be balanced");
1674 case WebAssembly::END_TRY: {
1678 auto *EHPad = TryToEHPad[EndToBegin[&
MI]];
1679 EHPadStack.push_back(EHPad);
1683 case WebAssembly::END_LOOP:
1687 case WebAssembly::CATCH:
1688 case WebAssembly::CATCH_ALL:
1689 EHPadStack.pop_back();
1692 case WebAssembly::RETHROW:
1693 MI.getOperand(0).setImm(getRethrowDepth(Stack, EHPadStack));
1697 if (
MI.isTerminator()) {
1700 while (
MI.getNumOperands() > 0)
1701 MI.removeOperand(
MI.getNumOperands() - 1);
1702 for (
auto MO : Ops) {
1706 getDelegateDepth(Stack, MO.getMBB()));
1709 getBranchDepth(Stack, MO.getMBB()));
1711 MI.addOperand(MF, MO);
1721 assert(
Stack.empty() &&
"Control flow should be balanced");
1724 void WebAssemblyCFGStackify::cleanupFunctionData(
MachineFunction &MF) {
1727 AppendixBB = FakeCallerBB =
nullptr;
1730 void WebAssemblyCFGStackify::releaseMemory() {
1738 bool WebAssemblyCFGStackify::runOnMachineFunction(
MachineFunction &MF) {
1740 "********** Function: "
1755 removeUnnecessaryInstrs(MF);
1758 rewriteDepthImmediates(MF);
1762 fixEndsAtEndOfFunction(MF);
1771 cleanupFunctionData(MF);