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();
786 if (RC == &WebAssembly::I32RegClass)
787 return WebAssembly::COPY_I32;
788 if (RC == &WebAssembly::I64RegClass)
789 return WebAssembly::COPY_I64;
790 if (RC == &WebAssembly::F32RegClass)
791 return WebAssembly::COPY_F32;
792 if (RC == &WebAssembly::F64RegClass)
793 return WebAssembly::COPY_F64;
794 if (RC == &WebAssembly::V128RegClass)
795 return WebAssembly::COPY_V128;
796 if (RC == &WebAssembly::FUNCREFRegClass)
797 return WebAssembly::COPY_FUNCREF;
798 if (RC == &WebAssembly::EXTERNREFRegClass)
799 return WebAssembly::COPY_EXTERNREF;
812 for (
auto &
MI : Split) {
813 for (
auto &MO :
MI.explicit_uses()) {
817 if (
Def->getParent() == &
MBB)
818 MFI.unstackifyVReg(MO.getReg());
851 if (!MFI.isVRegStackified(TeeReg)) {
853 MFI.unstackifyVReg(DefReg);
858 MI.eraseFromParent();
865 void WebAssemblyCFGStackify::addTryDelegate(
MachineInstr *RangeBegin,
877 AfterSet.
insert(RangeBegin);
880 if (std::prev(
I)->isDebugInstr() || std::prev(
I)->isPosition())
883 AfterSet.
insert(&*std::prev(
I));
892 TII.get(WebAssembly::TRY))
899 if (DelegateDest != FakeCallerBB)
902 auto SplitPos = std::next(RangeEnd->
getIterator());
903 if (SplitPos == EndBB->end()) {
906 MF.
insert(std::next(EndBB->getIterator()), DelegateBB);
907 EndBB->addSuccessor(DelegateBB);
916 bool PostSplit =
true;
917 if (EndBB->isEHPad()) {
947 PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->
end());
948 PostBB->transferSuccessors(PreBB);
967 MF.
insert(PostBB->getIterator(), PreBB);
968 MF.
insert(PostBB->getIterator(), DelegateBB);
969 PreBB->
splice(PreBB->
end(), PostBB, PostBB->begin(), SplitPos);
983 registerTryScope(Try, Delegate,
nullptr);
986 bool WebAssemblyCFGStackify::fixCallUnwindMismatches(
MachineFunction &MF) {
1109 using TryRange = std::pair<MachineInstr *, MachineInstr *>;
1117 bool SeenThrowableInstInBB =
false;
1119 if (
MI.getOpcode() == WebAssembly::TRY)
1120 EHPadStack.pop_back();
1122 EHPadStack.push_back(
MI.getParent());
1131 SeenThrowableInstInBB =
true;
1142 if (Succ->isEHPad()) {
1147 if (EHPadStack.back() == UnwindDest)
1153 std::prev(RangeBegin->
getIterator())->isEHLabel())
1154 RangeBegin = &*std::prev(RangeBegin->
getIterator());
1155 if (std::next(RangeEnd->getIterator()) !=
MBB.
end() &&
1156 std::next(RangeEnd->getIterator())->isEHLabel())
1157 RangeEnd = &*std::next(RangeEnd->getIterator());
1160 UnwindDestToTryRanges[UnwindDest].push_back(
1161 TryRange(RangeBegin, RangeEnd));
1163 <<
"\nCall = " <<
MI
1164 <<
"\nOriginal dest = " << UnwindDest->
getName()
1165 <<
" Current dest = " << EHPadStack.back()->getName()
1170 assert(EHPadStack.empty());
1177 MachineInstr *RangeBegin =
nullptr, *RangeEnd =
nullptr;
1181 UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back(
1182 TryRange(RangeBegin, RangeEnd));
1185 <<
"\nRange begin = " << *RangeBegin
1186 <<
"Range end = " << *RangeEnd
1187 <<
"\nOriginal dest = caller Current dest = "
1188 << CurrentDest->getName() <<
"\n\n");
1189 RangeBegin = RangeEnd =
nullptr;
1193 bool SeenThrowableInstInBB =
false;
1201 SeenThrowableInstInBB =
true;
1206 RecordCallerMismatchRange(EHPadStack.back());
1210 else if (EHPadStack.empty() || !MayThrow) {
1218 RangeBegin = RangeEnd = &
MI;
1224 if (
MI.getOpcode() == WebAssembly::TRY)
1225 EHPadStack.pop_back();
1227 EHPadStack.push_back(
MI.getParent());
1231 RecordCallerMismatchRange(EHPadStack.back());
1234 assert(EHPadStack.empty());
1237 if (UnwindDestToTryRanges.
empty())
1241 for (
auto &
P : UnwindDestToTryRanges) {
1242 NumCallUnwindMismatches +=
P.second.size();
1244 auto &TryRanges =
P.second;
1246 for (
auto Range : TryRanges) {
1247 MachineInstr *RangeBegin =
nullptr, *RangeEnd =
nullptr;
1248 std::tie(RangeBegin, RangeEnd) = Range;
1258 if (Succ->isEHPad()) {
1266 addTryDelegate(RangeBegin, RangeEnd, UnwindDest);
1273 bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(
MachineFunction &MF) {
1319 if (
MI.getOpcode() == WebAssembly::TRY)
1320 EHPadStack.pop_back();
1322 EHPadStack.push_back(&
MBB);
1328 if (
MI.getOpcode() == WebAssembly::CATCH_ALL) {
1333 else if (EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
1335 <<
"'s unwind destination does not exist anymore"
1341 else if (!EHPadStack.empty() && !EHInfo->hasUnwindDest(EHPad)) {
1342 EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF);
1344 <<
"- Catch unwind mismatch:\nEHPad = " << EHPad->
getName()
1345 <<
" Original dest = caller Current dest = "
1346 << EHPadStack.back()->getName() <<
"\n\n");
1351 else if (!EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
1352 auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
1353 if (EHPadStack.back() != UnwindDest) {
1354 EHPadToUnwindDest[EHPad] = UnwindDest;
1356 << EHPad->
getName() <<
" Original dest = "
1357 << UnwindDest->
getName() <<
" Current dest = "
1358 << EHPadStack.back()->getName() <<
"\n\n");
1362 EHPadStack.push_back(EHPad);
1367 assert(EHPadStack.empty());
1368 if (EHPadToUnwindDest.
empty())
1370 NumCatchUnwindMismatches += EHPadToUnwindDest.
size();
1373 for (
auto &
P : EHPadToUnwindDest) {
1378 addTryDelegate(Try, EndTry, UnwindDest);
1426 for (
auto &
MBB : MF) {
1427 for (
auto &
MI :
MBB) {
1428 if (
MI.isTerminator()) {
1429 for (
auto &MO :
MI.operands()) {
1430 if (MO.isMBB() && NewEndTryBBs.
count(MO.getMBB())) {
1431 auto *BrDest = MO.getMBB();
1432 bool FoundEndBlock =
false;
1433 for (; std::next(BrDest->getIterator()) != MF.end();
1434 BrDest = BrDest->getNextNode()) {
1435 for (
const auto &
MI : *BrDest) {
1437 FoundEndBlock =
true;
1455 void WebAssemblyCFGStackify::recalculateScopeTops(
MachineFunction &MF) {
1465 switch (
MI.getOpcode()) {
1467 case WebAssembly::END_LOOP:
1468 case WebAssembly::END_TRY:
1472 case WebAssembly::CATCH:
1473 case WebAssembly::CATCH_ALL:
1488 void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(
MachineFunction &MF) {
1491 if (MFI.getResults().empty())
1503 Worklist.push_back(MF.
rbegin()->rbegin());
1509 if (
MI.isPosition() ||
MI.isDebugInstr())
1511 switch (
MI.getOpcode()) {
1512 case WebAssembly::END_TRY: {
1516 auto *EHPad = TryToEHPad.
lookup(EndToBegin[&
MI]);
1520 if (NextIt != EHPad->
rend())
1521 Worklist.push_back(NextIt);
1525 case WebAssembly::END_LOOP:
1527 EndToBegin[&
MI]->getOperand(0).setImm(int32_t(RetType));
1539 while (!Worklist.empty())
1549 TII.get(WebAssembly::END_FUNCTION));
1558 for (
auto &
MBB : MF)
1559 placeLoopMarker(
MBB);
1561 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1562 for (
auto &
MBB : MF) {
1566 MF.getFunction().hasPersonalityFn())
1567 placeTryMarker(
MBB);
1570 placeBlockMarker(
MBB);
1575 MF.getFunction().hasPersonalityFn()) {
1576 bool Changed = fixCallUnwindMismatches(MF);
1577 Changed |= fixCatchUnwindMismatches(MF);
1579 recalculateScopeTops(MF);
1583 unsigned WebAssemblyCFGStackify::getBranchDepth(
1595 unsigned WebAssemblyCFGStackify::getDelegateDepth(
1597 if (
MBB == FakeCallerBB)
1598 return Stack.size();
1604 return getBranchDepth(Stack,
MBB);
1622 if (
X.first == EndTry->
getParent() &&
X.second == EndTry)
1630 unsigned WebAssemblyCFGStackify::getRethrowDepth(
1657 if (End->getOpcode() == WebAssembly::END_TRY) {
1658 auto *EHPad = TryToEHPad[EndToBegin[End]];
1659 if (EHPadStack.back() == EHPad)
1668 void WebAssemblyCFGStackify::rewriteDepthImmediates(
MachineFunction &MF) {
1674 switch (
MI.getOpcode()) {
1675 case WebAssembly::BLOCK:
1676 case WebAssembly::TRY:
1677 assert(ScopeTops[
Stack.back().first->getNumber()]->getNumber() <=
1679 "Block/try marker should be balanced");
1684 assert(
Stack.back().first == &
MBB &&
"Loop top should be balanced");
1692 case WebAssembly::END_TRY: {
1696 auto *EHPad = TryToEHPad[EndToBegin[&
MI]];
1697 EHPadStack.push_back(EHPad);
1701 case WebAssembly::END_LOOP:
1705 case WebAssembly::CATCH:
1706 case WebAssembly::CATCH_ALL:
1707 EHPadStack.pop_back();
1710 case WebAssembly::RETHROW:
1711 MI.getOperand(0).setImm(getRethrowDepth(Stack, EHPadStack));
1715 if (
MI.isTerminator()) {
1718 while (
MI.getNumOperands() > 0)
1719 MI.removeOperand(
MI.getNumOperands() - 1);
1720 for (
auto MO : Ops) {
1724 getDelegateDepth(Stack, MO.getMBB()));
1727 getBranchDepth(Stack, MO.getMBB()));
1729 MI.addOperand(MF, MO);
1739 assert(
Stack.empty() &&
"Control flow should be balanced");
1742 void WebAssemblyCFGStackify::cleanupFunctionData(
MachineFunction &MF) {
1745 AppendixBB = FakeCallerBB =
nullptr;
1748 void WebAssemblyCFGStackify::releaseMemory() {
1756 bool WebAssemblyCFGStackify::runOnMachineFunction(
MachineFunction &MF) {
1758 "********** Function: "
1773 removeUnnecessaryInstrs(MF);
1776 rewriteDepthImmediates(MF);
1780 fixEndsAtEndOfFunction(MF);
1789 cleanupFunctionData(MF);