LLVM: lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
40using namespace llvm;
42
43#define DEBUG_TYPE "wasm-cfg-stackify"
44
45STATISTIC(NumCallUnwindMismatches, "Number of call unwind mismatches found");
46STATISTIC(NumCatchUnwindMismatches, "Number of catch unwind mismatches found");
47
48namespace {
51
52 StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
53
54 void getAnalysisUsage(AnalysisUsage &AU) const override {
55 AU.addRequired();
56 AU.addRequired();
57 AU.addRequired();
59 }
60
61 bool runOnMachineFunction(MachineFunction &MF) override;
62
63
64
65
66 SmallVector<MachineBasicBlock *, 8> ScopeTops;
67 void updateScopeTops(MachineBasicBlock *Begin, MachineBasicBlock *End) {
70 if (!ScopeTops[EndNo] || ScopeTops[EndNo]->getNumber() > BeginNo)
71 ScopeTops[EndNo] = Begin;
72 }
73
74
75 void placeMarkers(MachineFunction &MF);
76 void placeBlockMarker(MachineBasicBlock &MBB);
77 void placeLoopMarker(MachineBasicBlock &MBB);
78 void placeTryMarker(MachineBasicBlock &MBB);
79 void placeTryTableMarker(MachineBasicBlock &MBB);
80
81
82
83 bool fixCallUnwindMismatches(MachineFunction &MF);
84 bool fixCatchUnwindMismatches(MachineFunction &MF);
85 void recalculateScopeTops(MachineFunction &MF);
86
87 void addNestedTryDelegate(MachineInstr *RangeBegin, MachineInstr *RangeEnd,
88 MachineBasicBlock *UnwindDest);
89 void removeUnnecessaryInstrs(MachineFunction &MF);
90
91 void addNestedTryTable(MachineInstr *RangeBegin, MachineInstr *RangeEnd,
92 MachineBasicBlock *UnwindDest);
93 MachineBasicBlock *getTrampolineBlock(MachineBasicBlock *UnwindDest);
94
95
96 using EndMarkerInfo =
97 std::pair<const MachineBasicBlock *, const MachineInstr *>;
98 unsigned getBranchDepth(const SmallVectorImpl &Stack,
99 const MachineBasicBlock *MBB);
100 unsigned getDelegateDepth(const SmallVectorImpl &Stack,
101 const MachineBasicBlock *MBB);
102 unsigned getRethrowDepth(const SmallVectorImpl &Stack,
103 const MachineBasicBlock *EHPadToRethrow);
104 void rewriteDepthImmediates(MachineFunction &MF);
105 void fixEndsAtEndOfFunction(MachineFunction &MF);
106 void cleanupFunctionData(MachineFunction &MF);
107
108
109
110 DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd;
111
112
113 DenseMap<const MachineInstr *, MachineInstr *> EndToBegin;
114
115 DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad;
116
117 DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry;
118
119 DenseMap<const MachineBasicBlock *, MachineBasicBlock *>
120 UnwindDestToTrampoline;
121
122
123
124 MachineBasicBlock *AppendixBB = nullptr;
125 MachineBasicBlock *getAppendixBlock(MachineFunction &MF) {
126 if (!AppendixBB) {
128
130
131
132 if (CallerTrampolineBB)
133 MF.insert(CallerTrampolineBB->getIterator(), AppendixBB);
134 else
136 }
137 return AppendixBB;
138 }
139
140
141
142 MachineBasicBlock *CallerTrampolineBB = nullptr;
143 MachineBasicBlock *getCallerTrampolineBlock(MachineFunction &MF) {
144 if (!CallerTrampolineBB) {
146 MF.push_back(CallerTrampolineBB);
147 }
148 return CallerTrampolineBB;
149 }
150
151
152
153
154
155
156
157 MachineBasicBlock *FakeCallerBB = nullptr;
158 MachineBasicBlock *getFakeCallerBlock(MachineFunction &MF) {
159 if (!FakeCallerBB)
161 return FakeCallerBB;
162 }
163
164
165
166 void registerScope(MachineInstr *Begin, MachineInstr *End);
167 void registerTryScope(MachineInstr *Begin, MachineInstr *End,
168 MachineBasicBlock *EHPad);
169 void unregisterScope(MachineInstr *Begin);
170
171public:
172 static char ID;
173 WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
174 ~WebAssemblyCFGStackify() override { releaseMemory(); }
175 void releaseMemory() override;
176};
177}
178
179char WebAssemblyCFGStackify::ID = 0;
182 "Insert BLOCK/LOOP/TRY/TRY_TABLE markers for WebAssembly scopes", false,
183 false)
184
186 return new WebAssemblyCFGStackify();
187}
188
189
190
191
192
193
198 if (MO.isMBB() && MO.getMBB() == MBB)
199 return true;
200 return false;
201}
202
203
204
205
206
207
208template
211 const Container &AfterSet) {
212 auto InsertPos = MBB->end();
213 while (InsertPos != MBB->begin()) {
214 if (BeforeSet.count(&*std::prev(InsertPos))) {
215#ifndef NDEBUG
216
217 for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos)
218 assert(!AfterSet.count(&*std::prev(Pos)));
219#endif
220 break;
221 }
222 --InsertPos;
223 }
224 return InsertPos;
225}
226
227
228
229
230
231
232template
235 const Container &AfterSet) {
236 auto InsertPos = MBB->begin();
237 while (InsertPos != MBB->end()) {
238 if (AfterSet.count(&*InsertPos)) {
239#ifndef NDEBUG
240
241 for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos)
242 assert(!BeforeSet.count(&*Pos));
243#endif
244 break;
245 }
246 ++InsertPos;
247 }
248 return InsertPos;
249}
250
251void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin,
253 BeginToEnd[Begin] = End;
254 EndToBegin[End] = Begin;
255}
256
257
258void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin,
259 MachineInstr *End,
260 MachineBasicBlock *EHPad) {
261 registerScope(Begin, End);
262 TryToEHPad[Begin] = EHPad;
263 EHPadToTry[EHPad] = Begin;
264}
265
266void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) {
268 MachineInstr *End = BeginToEnd[Begin];
270 BeginToEnd.erase(Begin);
271 EndToBegin.erase(End);
272 MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin);
273 if (EHPad) {
275 TryToEHPad.erase(Begin);
276 EHPadToTry.erase(EHPad);
277 }
278}
279
280
281
282
283void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) {
286 const auto &TII = *MF.getSubtarget().getInstrInfo();
287 const auto &MFI = *MF.getInfo();
288
289
290
291
292 MachineBasicBlock *Header = nullptr;
293 bool IsBranchedTo = false;
296 if (Pred->getNumber() < MBBNumber) {
297 Header = Header ? MDT->findNearestCommonDominator(Header, Pred) : Pred;
299 IsBranchedTo = true;
300 }
301 }
302 if (!Header)
303 return;
304 if (!IsBranchedTo)
305 return;
306
307 assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
309
310
311
313 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
314 if (ScopeTop->getNumber() > Header->getNumber()) {
315
316 I = std::next(ScopeTop->getIterator());
317 } else {
318
319 Header = ScopeTop;
320 break;
321 }
322 }
323 }
324
325
326
327
328 SmallPtrSet<const MachineInstr *, 4> BeforeSet;
329
330 SmallPtrSet<const MachineInstr *, 4> AfterSet;
331 for (const auto &MI : *Header) {
332
333
334
335 if (MI.getOpcode() == WebAssembly::LOOP) {
336 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
337 if (MBB.getNumber() > LoopBottom->getNumber())
339#ifndef NDEBUG
340 else
342#endif
343 }
344
345
346
347
348
349 if (MI.getOpcode() == WebAssembly::BLOCK ||
350 MI.getOpcode() == WebAssembly::TRY ||
351 MI.getOpcode() == WebAssembly::TRY_TABLE) {
354#ifndef NDEBUG
355 else
357#endif
358 }
359
360#ifndef NDEBUG
361
362 if (MI.getOpcode() == WebAssembly::END_BLOCK ||
363 MI.getOpcode() == WebAssembly::END_LOOP ||
364 MI.getOpcode() == WebAssembly::END_TRY ||
365 MI.getOpcode() == WebAssembly::END_TRY_TABLE)
367#endif
368
369
370 if (MI.isTerminator())
372 }
373
374
375 for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
376 --I) {
377 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
378 continue;
380 AfterSet.insert(&*std::prev(I));
381 else
382 break;
383 }
384
385
388 MachineInstr *Begin =
389 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
390 TII.get(WebAssembly::BLOCK))
391 .addImm(int64_t(ReturnType));
392
393
394 BeforeSet.clear();
395 AfterSet.clear();
397#ifndef NDEBUG
398
399 if (MI.getOpcode() == WebAssembly::LOOP)
401#endif
402
403
404
405
406
407
408
409
410
411
412 if (MI.getOpcode() == WebAssembly::END_LOOP ||
413 MI.getOpcode() == WebAssembly::END_TRY) {
414 if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
416#ifndef NDEBUG
417 else
419#endif
420 }
421 }
422
423
426 TII.get(WebAssembly::END_BLOCK));
427 registerScope(Begin, End);
428
429
430 updateScopeTops(Header, &MBB);
431}
432
433
434void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) {
436 const auto &MLI = getAnalysis().getLI();
437 const auto &WEI = getAnalysis();
438 SortRegionInfo SRI(MLI, WEI);
439 const auto &TII = *MF.getSubtarget().getInstrInfo();
440
441 MachineLoop *Loop = MLI.getLoopFor(&MBB);
443 return;
444
445
446
447 MachineBasicBlock *Bottom = SRI.getBottom(Loop);
448 auto Iter = std::next(Bottom->getIterator());
449 if (Iter == MF.end()) {
450 getAppendixBlock(MF);
452 }
453 MachineBasicBlock *AfterLoop = &*Iter;
454
455
456 SmallPtrSet<const MachineInstr *, 4> BeforeSet;
457 SmallPtrSet<const MachineInstr *, 4> AfterSet;
458 for (const auto &MI : MBB) {
459
460
461 if (MI.getOpcode() == WebAssembly::END_LOOP)
463#ifndef NDEBUG
464 else
466#endif
467 }
468
469
472 TII.get(WebAssembly::LOOP))
473 .addImm(int64_t(WebAssembly::BlockType::Void));
474
475
476 BeforeSet.clear();
477 AfterSet.clear();
478#ifndef NDEBUG
479 for (const auto &MI : MBB)
480
481 if (MI.getOpcode() == WebAssembly::END_LOOP)
483#endif
484
485
486
490 : (*AfterLoop->pred_rbegin())->findBranchDebugLoc();
491 MachineInstr *End =
492 BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP));
493 registerScope(Begin, End);
494
497 "With block sorting the outermost loop for a block should be first.");
498 updateScopeTops(&MBB, AfterLoop);
499}
500
501void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) {
504 auto &MDT = getAnalysis().getDomTree();
505 const auto &TII = *MF.getSubtarget().getInstrInfo();
506 const auto &MLI = getAnalysis().getLI();
507 const auto &WEI = getAnalysis();
508 SortRegionInfo SRI(MLI, WEI);
509 const auto &MFI = *MF.getInfo();
510
511
512 MachineBasicBlock *Header = nullptr;
515 if (Pred->getNumber() < MBBNumber) {
516 Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
518 "Explicit branch to an EH pad!");
519 }
520 }
521 if (!Header)
522 return;
523
524
525
526 WebAssemblyException *WE = WEI.getExceptionFor(&MBB);
528 MachineBasicBlock *Bottom = SRI.getBottom(WE);
529 auto Iter = std::next(Bottom->getIterator());
530 if (Iter == MF.end()) {
531 getAppendixBlock(MF);
533 }
534 MachineBasicBlock *Cont = &*Iter;
535
536
537
539 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
540 if (ScopeTop->getNumber() > Header->getNumber()) {
541
542 I = std::next(ScopeTop->getIterator());
543 } else {
544
545 Header = ScopeTop;
546 break;
547 }
548 }
549 }
550
551
552
553
554 SmallPtrSet<const MachineInstr *, 4> BeforeSet;
555
556 SmallPtrSet<const MachineInstr *, 4> AfterSet;
557 for (const auto &MI : *Header) {
558
559
560
561 if (MI.getOpcode() == WebAssembly::LOOP) {
562 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
563 if (MBB.getNumber() > LoopBottom->getNumber())
565#ifndef NDEBUG
566 else
568#endif
569 }
570
571
572
573 if (MI.getOpcode() == WebAssembly::BLOCK ||
574 MI.getOpcode() == WebAssembly::TRY)
576
577#ifndef NDEBUG
578
579 if (MI.getOpcode() == WebAssembly::END_BLOCK ||
580 MI.getOpcode() == WebAssembly::END_LOOP ||
581 MI.getOpcode() == WebAssembly::END_TRY)
583#endif
584
585
586 if (MI.isTerminator())
588 }
589
590
591
592
593
594
595 MachineInstr *ThrowingCall = nullptr;
597 auto TermPos = Header->getFirstTerminator();
598 if (TermPos == Header->end() ||
599 TermPos->getOpcode() != WebAssembly::RETHROW) {
600 for (auto &MI : reverse(*Header)) {
601 if (MI.isCall()) {
603 ThrowingCall = &MI;
604
605
606 if (MI.getIterator() != Header->begin() &&
607 std::prev(MI.getIterator())->isEHLabel()) {
608 AfterSet.insert(&*std::prev(MI.getIterator()));
609 ThrowingCall = &*std::prev(MI.getIterator());
610 }
611 break;
612 }
613 }
614 }
615 }
616
617
618
619
620
621
622
624 : Header->getFirstTerminator();
625 for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) {
626 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
627 continue;
628 if (WebAssembly::isChild(*std::prev(I), MFI))
629 AfterSet.insert(&*std::prev(I));
630 else
631 break;
632 }
633
634
636 MachineInstr *Begin =
637 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
638 TII.get(WebAssembly::TRY))
639 .addImm(int64_t(WebAssembly::BlockType::Void));
640
641
642 BeforeSet.clear();
643 AfterSet.clear();
644 for (const auto &MI : *Cont) {
645#ifndef NDEBUG
646
647 if (MI.getOpcode() == WebAssembly::LOOP)
649
650
651
652 if (MI.getOpcode() == WebAssembly::END_TRY)
654#endif
655
656
657
658
659
660 if (MI.getOpcode() == WebAssembly::END_LOOP) {
661
662
663 if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber())
665#ifndef NDEBUG
666 else
668#endif
669 }
670
671
672 }
673
674
677 TII.get(WebAssembly::END_TRY));
678 registerTryScope(Begin, End, &MBB);
679
680
681
682
683
684
685
686
687
688
689
690
691 for (auto *End : {&MBB, Cont})
692 updateScopeTops(Header, End);
693}
694
695void WebAssemblyCFGStackify::placeTryTableMarker(MachineBasicBlock &MBB) {
698 auto &MDT = getAnalysis().getDomTree();
699 const auto &TII = *MF.getSubtarget().getInstrInfo();
700 const auto &MLI = getAnalysis().getLI();
701 const auto &WEI = getAnalysis();
702 SortRegionInfo SRI(MLI, WEI);
703 const auto &MFI = *MF.getInfo();
704
705
706 MachineBasicBlock *Header = nullptr;
709 if (Pred->getNumber() < MBBNumber) {
710 Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
712 "Explicit branch to an EH pad!");
713 }
714 }
715 if (!Header)
716 return;
717
718
719
720
721 WebAssemblyException *WE = WEI.getExceptionFor(&MBB);
723 MachineBasicBlock *Bottom = SRI.getBottom(WE);
724 auto Iter = std::next(Bottom->getIterator());
725 if (Iter == MF.end())
726 Iter--;
727 MachineBasicBlock *Cont = &*Iter;
728
729
730
732 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
733 if (ScopeTop->getNumber() > Header->getNumber()) {
734
735 I = std::next(ScopeTop->getIterator());
736 } else {
737
738 Header = ScopeTop;
739 break;
740 }
741 }
742 }
743
744
745
746
747 SmallPtrSet<const MachineInstr *, 4> BeforeSet;
748
749 SmallPtrSet<const MachineInstr *, 4> AfterSet;
750 for (const auto &MI : *Header) {
751
752
753
754 if (MI.getOpcode() == WebAssembly::LOOP) {
755 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
756 if (MBB.getNumber() > LoopBottom->getNumber())
758#ifndef NDEBUG
759 else
761#endif
762 }
763
764
765
766 if (MI.getOpcode() == WebAssembly::BLOCK ||
767 MI.getOpcode() == WebAssembly::TRY_TABLE)
769
770#ifndef NDEBUG
771
772 if (MI.getOpcode() == WebAssembly::END_BLOCK ||
773 MI.getOpcode() == WebAssembly::END_LOOP ||
774 MI.getOpcode() == WebAssembly::END_TRY_TABLE)
776#endif
777
778
779 if (MI.isTerminator())
781 }
782
783
784
785
786
787
788 MachineInstr *ThrowingCall = nullptr;
790 auto TermPos = Header->getFirstTerminator();
791 if (TermPos == Header->end() ||
792 TermPos->getOpcode() != WebAssembly::RETHROW) {
793 for (auto &MI : reverse(*Header)) {
794 if (MI.isCall()) {
796 ThrowingCall = &MI;
797
798
799 if (MI.getIterator() != Header->begin() &&
800 std::prev(MI.getIterator())->isEHLabel()) {
801 AfterSet.insert(&*std::prev(MI.getIterator()));
802 ThrowingCall = &*std::prev(MI.getIterator());
803 }
804 break;
805 }
806 }
807 }
808 }
809
810
811
812
813
814
815
817 : Header->getFirstTerminator();
818 for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) {
819 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
820 continue;
821 if (WebAssembly::isChild(*std::prev(I), MFI))
822 AfterSet.insert(&*std::prev(I));
823 else
824 break;
825 }
826
827
828
829
830
831
832
833
834
835
836
837
838
839
841 MachineInstrBuilder BlockMIB =
842 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
843 TII.get(WebAssembly::BLOCK));
845 MachineInstrBuilder TryTableMIB =
846 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
847 TII.get(WebAssembly::TRY_TABLE))
848 .addImm(int64_t(WebAssembly::BlockType::Void))
849 .addImm(1);
850 auto *TryTable = TryTableMIB.getInstr();
851
852
853
854
855 const auto &TLI =
856 *MF.getSubtarget().getTargetLowering();
859 ? WebAssembly::BlockType::I32
860 : WebAssembly::BlockType::I64;
862 switch (Catch->getOpcode()) {
863 case WebAssembly::CATCH:
864
865
866
867 BlockMIB.addImm(int64_t(PtrTy));
869 for (const auto &Use : Catch->uses()) {
870
872 break;
873 }
875 break;
876 case WebAssembly::CATCH_REF:
877
878
879
880
881 BlockMIB.addImm(int64_t(WebAssembly::BlockType::Multivalue));
884 for (const auto &Use : Catch->uses()) {
886 break;
887 }
889 break;
890 case WebAssembly::CATCH_ALL:
891
892 BlockMIB.addImm(int64_t(WebAssembly::BlockType::Void));
895 break;
896 case WebAssembly::CATCH_ALL_REF:
897
898 BlockMIB.addImm(int64_t(WebAssembly::BlockType::Exnref));
901 break;
902 }
903
904
905
906 BeforeSet.clear();
907 AfterSet.clear();
908 for (const auto &MI : MBB) {
909#ifndef NDEBUG
910
911 if (MI.getOpcode() == WebAssembly::LOOP)
913#endif
914
915
916
917
918
919 if (MI.getOpcode() == WebAssembly::END_LOOP) {
920 if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
922#ifndef NDEBUG
923 else
925#endif
926 }
927
928#ifndef NDEBUG
929
930
931
934#endif
935 }
936
937
939 MachineInstr *EndTryTable =
941 TII.get(WebAssembly::END_TRY_TABLE));
942 registerTryScope(TryTable, EndTryTable, &MBB);
943 MachineInstr *EndBlock =
945 TII.get(WebAssembly::END_BLOCK));
946 registerScope(Block, EndBlock);
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988 for (auto *End : {&MBB, Cont})
989 updateScopeTops(Header, End);
990}
991
992void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) {
993 const auto &TII = *MF.getSubtarget().getInstrInfo();
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028 for (auto &MBB : MF) {
1030 continue;
1031
1032 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1034 MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode();
1035
1036 MachineBasicBlock *Cont = &MBB;
1037 while (Cont->isEHPad()) {
1038 MachineInstr *Try = EHPadToTry[Cont];
1039 MachineInstr *EndTry = BeginToEnd[Try];
1040
1043 }
1044
1046
1047
1048
1049
1050
1051
1052 if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) ||
1053 (.empty() && FBB && FBB == Cont))) {
1054 bool ErasedUncondBr = false;
1055 (void)ErasedUncondBr;
1056 for (auto I = EHPadLayoutPred->end(), E = EHPadLayoutPred->begin();
1058 auto PrevI = std::prev(I);
1059 if (PrevI->isTerminator()) {
1060 assert(PrevI->getOpcode() == WebAssembly::BR);
1061 PrevI->eraseFromParent();
1062 ErasedUncondBr = true;
1063 break;
1064 }
1065 }
1066 assert(ErasedUncondBr && "Unconditional branch not erased!");
1067 }
1068 }
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1082 for (auto &MBB : MF) {
1084 if (MI.getOpcode() != WebAssembly::TRY)
1085 continue;
1086 MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try];
1087 if (EndTry->getOpcode() == WebAssembly::DELEGATE)
1088 continue;
1089
1090 MachineBasicBlock *TryBB = Try->getParent();
1091 MachineBasicBlock *Cont = EndTry->getParent();
1093 for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator());
1094 B != TryBB->begin() && E != Cont->end() &&
1095 std::prev(B)->getOpcode() == WebAssembly::BLOCK &&
1096 E->getOpcode() == WebAssembly::END_BLOCK &&
1097 std::prev(B)->getOperand(0).getImm() == RetType;
1101 }
1102 }
1103 }
1104 for (auto *MI : ToDelete) {
1105 if (MI->getOpcode() == WebAssembly::BLOCK)
1106 unregisterScope(MI);
1107 MI->eraseFromParent();
1108 }
1109}
1110
1111
1112
1119
1120 for (auto &MI : Split) {
1121 for (auto &MO : MI.explicit_uses()) {
1122 if (!MO.isReg() || MO.getReg().isPhysical())
1123 continue;
1124 if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg()))
1125 if (Def->getParent() == &MBB)
1126 MFI.unstackifyVReg(MO.getReg());
1127 }
1128 }
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1155 continue;
1156 Register TeeReg = MI.getOperand(0).getReg();
1158 Register DefReg = MI.getOperand(2).getReg();
1159 if (!MFI.isVRegStackified(TeeReg)) {
1160
1161 MFI.unstackifyVReg(DefReg);
1162 unsigned CopyOpc =
1167 MI.eraseFromParent();
1168 }
1169 }
1170}
1171
1172
1173
1174void WebAssemblyCFGStackify::addNestedTryDelegate(
1175 MachineInstr *RangeBegin, MachineInstr *RangeEnd,
1176 MachineBasicBlock *UnwindDest) {
1177 auto *BeginBB = RangeBegin->getParent();
1178 auto *EndBB = RangeEnd->getParent();
1179 MachineFunction &MF = *BeginBB->getParent();
1180 const auto &MFI = *MF.getInfo();
1181 const auto &TII = *MF.getSubtarget().getInstrInfo();
1182
1183
1184
1185 SmallPtrSet<const MachineInstr *, 4> AfterSet;
1186 AfterSet.insert(RangeBegin);
1189 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
1190 continue;
1192 AfterSet.insert(&*std::prev(I));
1193 else
1194 break;
1195 }
1196
1197
1199 BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet);
1200 MachineInstr *Try = BuildMI(*BeginBB, TryPos, RangeBegin->getDebugLoc(),
1201 TII.get(WebAssembly::TRY))
1202 .addImm(int64_t(WebAssembly::BlockType::Void));
1203
1204
1206
1207
1208 if (UnwindDest != FakeCallerBB)
1210
1211 auto SplitPos = std::next(RangeEnd->getIterator());
1212 if (SplitPos == EndBB->end()) {
1213
1214
1215 MF.insert(std::next(EndBB->getIterator()), DelegateBB);
1216 EndBB->addSuccessor(DelegateBB);
1217
1218 } else {
1219
1220
1221
1222
1223
1224
1225
1226 bool CatchAfterSplit = false;
1227 if (EndBB->isEHPad()) {
1231 CatchAfterSplit = true;
1232 break;
1233 }
1234 }
1235 }
1236
1237 MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;
1238 if (!CatchAfterSplit) {
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253 PreBB = EndBB;
1257 PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end());
1258 PostBB->transferSuccessors(PreBB);
1259 } else {
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274 assert(EndBB->isEHPad());
1276 PostBB = EndBB;
1277 MF.insert(PostBB->getIterator(), PreBB);
1278 MF.insert(PostBB->getIterator(), DelegateBB);
1279 PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos);
1280
1281
1282
1283 }
1287 }
1288
1289
1290 MachineInstr *Delegate = BuildMI(DelegateBB, RangeEnd->getDebugLoc(),
1291 TII.get(WebAssembly::DELEGATE))
1292 .addMBB(UnwindDest);
1293 registerTryScope(Try, Delegate, nullptr);
1294}
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311MachineBasicBlock *
1312WebAssemblyCFGStackify::getTrampolineBlock(MachineBasicBlock *UnwindDest) {
1313
1314
1315
1316 auto It = UnwindDestToTrampoline.find(UnwindDest);
1317 if (It != UnwindDestToTrampoline.end())
1318 return It->second;
1319
1320 auto &MF = *UnwindDest->getParent();
1322 const auto &TII = *MF.getSubtarget().getInstrInfo();
1323
1324 MachineInstr *Block = nullptr;
1325 MachineBasicBlock *TrampolineBB = nullptr;
1327
1328 if (UnwindDest == getFakeCallerBlock(MF)) {
1329
1330
1331
1332 auto BeginPos = MF.begin()->begin();
1334 BeginPos++;
1336 TII.get(WebAssembly::BLOCK))
1337 .addImm(int64_t(WebAssembly::BlockType::Exnref));
1338 TrampolineBB = getCallerTrampolineBlock(MF);
1339 MachineBasicBlock *PrevBB = &*std::prev(CallerTrampolineBB->getIterator());
1341 } else {
1342
1343
1344
1345 auto *TargetBeginTry = EHPadToTry[UnwindDest];
1346 auto *TargetEndTry = BeginToEnd[TargetBeginTry];
1347 auto *TargetBeginBB = TargetBeginTry->getParent();
1348 auto *TargetEndBB = TargetEndTry->getParent();
1349
1350 Block = BuildMI(*TargetBeginBB, std::next(TargetBeginTry->getIterator()),
1351 TargetBeginTry->getDebugLoc(), TII.get(WebAssembly::BLOCK))
1352 .addImm(int64_t(WebAssembly::BlockType::Exnref));
1354 EndDebugLoc = TargetEndTry->getDebugLoc();
1355 MF.insert(TargetEndBB->getIterator(), TrampolineBB);
1357 }
1358
1359
1360
1361 MachineInstr *EndBlock =
1362 BuildMI(TrampolineBB, EndDebugLoc, TII.get(WebAssembly::END_BLOCK));
1363 auto ExnReg = MRI.createVirtualRegister(&WebAssembly::EXNREFRegClass);
1364 BuildMI(TrampolineBB, EndDebugLoc, TII.get(WebAssembly::CATCH_ALL_REF))
1366 BuildMI(TrampolineBB, EndDebugLoc, TII.get(WebAssembly::THROW_REF))
1368
1369
1370
1371
1372 MachineBasicBlock *TrampolineLayoutPred = TrampolineBB->getPrevNode();
1374 TII.get(WebAssembly::UNREACHABLE));
1375
1376 registerScope(Block, EndBlock);
1377 UnwindDestToTrampoline[UnwindDest] = TrampolineBB;
1378 return TrampolineBB;
1379}
1380
1381
1382
1383void WebAssemblyCFGStackify::addNestedTryTable(MachineInstr *RangeBegin,
1384 MachineInstr *RangeEnd,
1385 MachineBasicBlock *UnwindDest) {
1386 auto *BeginBB = RangeBegin->getParent();
1387 auto *EndBB = RangeEnd->getParent();
1388
1389 MachineFunction &MF = *BeginBB->getParent();
1390 const auto &MFI = *MF.getInfo();
1391 const auto &TII = *MF.getSubtarget().getInstrInfo();
1392
1393
1394 auto *TrampolineBB = getTrampolineBlock(UnwindDest);
1395
1396
1397
1398 SmallPtrSet<const MachineInstr *, 4> AfterSet;
1399 AfterSet.insert(RangeBegin);
1402 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
1403 continue;
1405 AfterSet.insert(&*std::prev(I));
1406 else
1407 break;
1408 }
1409
1410
1412 BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet);
1413 MachineInstr *TryTable =
1415 TII.get(WebAssembly::TRY_TABLE))
1416 .addImm(int64_t(WebAssembly::BlockType::Void))
1417 .addImm(1)
1419 .addMBB(TrampolineBB);
1420
1421
1424
1425 auto SplitPos = std::next(RangeEnd->getIterator());
1426 if (SplitPos == EndBB->end()) {
1427
1428
1429 MF.insert(std::next(EndBB->getIterator()), EndTryTableBB);
1430 EndBB->addSuccessor(EndTryTableBB);
1431
1432 } else {
1433
1434
1435
1436
1437
1438
1439
1440 bool CatchAfterSplit = false;
1441 if (EndBB->isEHPad()) {
1445 CatchAfterSplit = true;
1446 break;
1447 }
1448 }
1449 }
1450
1451 MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;
1452 if (!CatchAfterSplit) {
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467 PreBB = EndBB;
1471 PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end());
1472 PostBB->transferSuccessors(PreBB);
1473 } else {
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488 assert(EndBB->isEHPad());
1490 PostBB = EndBB;
1491 MF.insert(PostBB->getIterator(), PreBB);
1492 MF.insert(PostBB->getIterator(), EndTryTableBB);
1493 PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos);
1494
1495
1496
1497 }
1501 }
1502
1503
1504 MachineInstr *EndTryTable = BuildMI(EndTryTableBB, RangeEnd->getDebugLoc(),
1505 TII.get(WebAssembly::END_TRY_TABLE));
1506 registerTryScope(TryTable, EndTryTable, nullptr);
1507}
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1557 auto &MF = *EndTryTableBB->getParent();
1558 MachineInstr *EndTryTable = nullptr, *EndLoop = nullptr;
1559 for (auto &MI : reverse(*EndTryTableBB)) {
1560 if (MI.getOpcode() == WebAssembly::END_TRY_TABLE) {
1561 EndTryTable = &MI;
1562 continue;
1563 }
1564 if (EndTryTable && MI.getOpcode() == WebAssembly::END_LOOP) {
1565 EndLoop = &MI;
1566 break;
1567 }
1568 }
1569 if (!EndLoop)
1570 return;
1571
1574 auto SplitPos = std::next(EndLoop->getIterator());
1575 EndLoopBB->splice(EndLoopBB->end(), EndTryTableBB, EndTryTableBB->begin(),
1576 SplitPos);
1577 EndLoopBB->addSuccessor(EndTryTableBB);
1578}
1579
1580bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) {
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1824
1825
1826
1827 using TryRange = std::pair<MachineInstr *, MachineInstr *>;
1828
1829 DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> UnwindDestToTryRanges;
1830
1831
1832
1833
1835 bool SeenThrowableInstInBB = false;
1841
1842
1843
1844
1845
1848 continue;
1849 SeenThrowableInstInBB = true;
1850
1851
1852
1853 MachineBasicBlock *UnwindDest = nullptr;
1855
1856
1857
1858
1859 if (Succ->isEHPad()) {
1860 UnwindDest = Succ;
1861 break;
1862 }
1863 }
1864 if (EHPadStack.back() == UnwindDest)
1865 continue;
1866
1867
1868 MachineInstr *RangeBegin = &MI, *RangeEnd = &MI;
1870 std::prev(RangeBegin->getIterator())->isEHLabel())
1871 RangeBegin = &*std::prev(RangeBegin->getIterator());
1872 if (std::next(RangeEnd->getIterator()) != MBB.end() &&
1873 std::next(RangeEnd->getIterator())->isEHLabel())
1874 RangeEnd = &*std::next(RangeEnd->getIterator());
1875
1876
1877 UnwindDestToTryRanges[UnwindDest].push_back(
1878 TryRange(RangeBegin, RangeEnd));
1880 << "\nCall = " << MI
1881 << "\nOriginal dest = " << UnwindDest->getName()
1882 << " Current dest = " << EHPadStack.back()->getName()
1883 << "\n\n");
1884 }
1885 }
1886
1888
1889
1890
1891
1892
1893
1894 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
1895
1896
1897 auto RecordCallerMismatchRange = [&](const MachineBasicBlock *CurrentDest) {
1898 UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back(
1899 TryRange(RangeBegin, RangeEnd));
1900 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = "
1902 << "\nRange begin = " << *RangeBegin
1903 << "Range end = " << *RangeEnd
1904 << "\nOriginal dest = caller Current dest = "
1905 << CurrentDest->getName() << "\n\n");
1906 RangeBegin = RangeEnd = nullptr;
1907 };
1908
1910 bool SeenThrowableInstInBB = false;
1913
1914
1915
1916
1918 SeenThrowableInstInBB = true;
1919
1920
1921
1923 RecordCallerMismatchRange(EHPadStack.back());
1924
1925
1926
1927 else if (EHPadStack.empty() || !MayThrow) {
1928 }
1929
1930
1931
1932
1933 else {
1934 if (!RangeEnd)
1935 RangeBegin = RangeEnd = &MI;
1936 else
1937 RangeBegin = &MI;
1938 }
1939
1940
1945 }
1946
1947 if (RangeEnd)
1948 RecordCallerMismatchRange(EHPadStack.back());
1949 }
1950
1952
1953
1954 if (UnwindDestToTryRanges.empty())
1955 return false;
1956
1957
1958
1960 for (auto &[UnwindDest, _] : UnwindDestToTryRanges) {
1961 auto It = EHPadToTry.find(UnwindDest);
1962
1963
1964 if (It != EHPadToTry.end()) {
1965 auto *TryTable = It->second;
1966 auto *EndTryTable = BeginToEnd[TryTable];
1968 }
1969 }
1970
1971
1972 for (auto &P : UnwindDestToTryRanges) {
1973 NumCallUnwindMismatches += P.second.size();
1974 MachineBasicBlock *UnwindDest = P.first;
1975 auto &TryRanges = P.second;
1976
1977 for (auto Range : TryRanges) {
1978 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
1979 std::tie(RangeBegin, RangeEnd) = Range;
1981
1982
1983
1984
1985
1986
1987
1988 if (UnwindDest != getFakeCallerBlock(MF)) {
1989 MachineBasicBlock *EHPad = nullptr;
1991 if (Succ->isEHPad()) {
1992 EHPad = Succ;
1993 break;
1994 }
1995 }
1996 if (EHPad)
1998 }
1999
2001 addNestedTryDelegate(RangeBegin, RangeEnd, UnwindDest);
2002 else
2003 addNestedTryTable(RangeBegin, RangeEnd, UnwindDest);
2004 }
2005 }
2006
2007 return true;
2008}
2009
2010
2011
2012
2015 return nullptr;
2023 default:
2025 }
2026}
2027
2028bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) {
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2132
2133
2134 DenseMap<MachineBasicBlock *, MachineBasicBlock *> EHPadToUnwindDest;
2135
2138 if (MI.getOpcode() == WebAssembly::TRY)
2140 else if (MI.getOpcode() == WebAssembly::TRY_TABLE) {
2141
2142
2143
2146 } else if (MI.getOpcode() == WebAssembly::DELEGATE)
2149 auto *EHPad = &MBB;
2150
2151
2152
2153
2155 continue;
2156
2157
2158
2160 }
2161
2162
2163
2164 else if (EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
2166 << "'s unwind destination does not exist anymore"
2167 << "\n\n");
2168 }
2169
2170
2171
2172 else if (!EHPadStack.empty() && !EHInfo->hasUnwindDest(EHPad)) {
2173 EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF);
2175 << "- Catch unwind mismatch:\nEHPad = " << EHPad->getName()
2176 << " Original dest = caller Current dest = "
2177 << EHPadStack.back()->getName() << "\n\n");
2178 }
2179
2180
2181
2182 else if (!EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
2183 auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
2184 if (EHPadStack.back() != UnwindDest) {
2185 EHPadToUnwindDest[EHPad] = UnwindDest;
2186 LLVM_DEBUG(dbgs() << "- Catch unwind mismatch:\nEHPad = "
2187 << EHPad->getName() << " Original dest = "
2188 << UnwindDest->getName() << " Current dest = "
2189 << EHPadStack.back()->getName() << "\n\n");
2190 }
2191 }
2192
2194 }
2195 }
2196 }
2197
2199 if (EHPadToUnwindDest.empty())
2200 return false;
2201
2202
2203
2204 for (auto &[_, UnwindDest] : EHPadToUnwindDest) {
2205 auto It = EHPadToTry.find(UnwindDest);
2206
2207 if (It != EHPadToTry.end()) {
2208 auto *TryTable = It->second;
2209 auto *EndTryTable = BeginToEnd[TryTable];
2211 }
2212 }
2213
2214 NumCatchUnwindMismatches += EHPadToUnwindDest.size();
2215 SmallPtrSet<MachineBasicBlock *, 4> NewEndTryBBs;
2216
2217 for (auto &[EHPad, UnwindDest] : EHPadToUnwindDest) {
2218 MachineInstr *Try = EHPadToTry[EHPad];
2219 MachineInstr *EndTry = BeginToEnd[Try];
2221 addNestedTryDelegate(Try, EndTry, UnwindDest);
2223 } else {
2224 addNestedTryTable(Try, EndTry, UnwindDest);
2225 }
2226 }
2227
2229 return true;
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275 for (auto &MBB : MF) {
2277 if (MI.isTerminator()) {
2278 for (auto &MO : MI.operands()) {
2279 if (MO.isMBB() && NewEndTryBBs.count(MO.getMBB())) {
2280 auto *BrDest = MO.getMBB();
2281 bool FoundEndBlock = false;
2282 for (; std::next(BrDest->getIterator()) != MF.end();
2283 BrDest = BrDest->getNextNode()) {
2284 for (const auto &MI : *BrDest) {
2285 if (MI.getOpcode() == WebAssembly::END_BLOCK) {
2286 FoundEndBlock = true;
2287 break;
2288 }
2289 }
2290 if (FoundEndBlock)
2291 break;
2292 }
2293 assert(FoundEndBlock);
2294 MO.setMBB(BrDest);
2295 }
2296 }
2297 }
2298 }
2299 }
2300
2301 return true;
2302}
2303
2304void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) {
2305
2306
2308 MDT->updateBlockNumbers();
2309 ScopeTops.clear();
2314 break;
2315 switch (MI.getOpcode()) {
2316 case WebAssembly::END_BLOCK:
2317 case WebAssembly::END_LOOP:
2318 case WebAssembly::END_TRY:
2319 case WebAssembly::END_TRY_TABLE:
2320 case WebAssembly::DELEGATE:
2321 updateScopeTops(EndToBegin[&MI]->getParent(), &MBB);
2322 break;
2323 case WebAssembly::CATCH_LEGACY:
2324 case WebAssembly::CATCH_ALL_LEGACY:
2326 break;
2327 }
2328 }
2329 }
2330}
2331
2332
2333
2334
2335
2336
2337
2338
2339void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
2340 const auto &MFI = *MF.getInfo();
2341
2342 if (MFI.getResults().empty())
2343 return;
2344
2345
2346
2348 MFI.getResults().size() > 1
2349 ? WebAssembly::BlockType::Multivalue
2352
2355
2358 while (It != MBB->rend()) {
2359 MachineInstr &MI = *It++;
2360 if (MI.isPosition() || MI.isDebugInstr())
2361 continue;
2362 switch (MI.getOpcode()) {
2363 case WebAssembly::END_TRY: {
2364
2365
2366
2367 auto *EHPad = TryToEHPad.lookup(EndToBegin[&MI]);
2369 auto NextIt =
2371 if (NextIt != EHPad->rend())
2373 [[fallthrough]];
2374 }
2375 case WebAssembly::END_BLOCK:
2376 case WebAssembly::END_LOOP:
2377 case WebAssembly::END_TRY_TABLE:
2378 case WebAssembly::DELEGATE:
2379 EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
2380 continue;
2381 default:
2382
2383 return;
2384 }
2385 }
2386
2387
2389 };
2390
2391 while (!Worklist.empty())
2393}
2394
2395
2396
2401 TII.get(WebAssembly::END_FUNCTION));
2402}
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2427 std::vector<MachineInstr *> EndTryTables;
2428 for (auto &MBB : MF)
2430 if (MI.getOpcode() == WebAssembly::END_TRY_TABLE)
2431 EndTryTables.push_back(&MI);
2432
2433 for (auto *EndTryTable : EndTryTables) {
2436 MF.insert(MBB->getIterator(), NewEndTryTableBB);
2437 auto SplitPos = std::next(EndTryTable->getIterator());
2438 NewEndTryTableBB->splice(NewEndTryTableBB->end(), MBB, MBB->begin(),
2439 SplitPos);
2440 NewEndTryTableBB->addSuccessor(MBB);
2442 TII.get(WebAssembly::UNREACHABLE));
2443 }
2444}
2445
2446
2447void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
2448
2449
2451
2452 for (auto &MBB : MF)
2453 placeLoopMarker(MBB);
2454
2455 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
2456 for (auto &MBB : MF) {
2458
2460 MF.getFunction().hasPersonalityFn()) {
2462 placeTryMarker(MBB);
2463 else
2464 placeTryTableMarker(MBB);
2465 }
2466 } else {
2467
2468 placeBlockMarker(MBB);
2469 }
2470 }
2471
2473 MF.getFunction().hasPersonalityFn()) {
2474 const auto &TII = *MF.getSubtarget().getInstrInfo();
2475
2477
2478 fixCallUnwindMismatches(MF);
2479 fixCatchUnwindMismatches(MF);
2480
2481
2482 recalculateScopeTops(MF);
2483 }
2484}
2485
2486unsigned WebAssemblyCFGStackify::getBranchDepth(
2487 const SmallVectorImpl &Stack, const MachineBasicBlock *MBB) {
2488 unsigned Depth = 0;
2489 for (auto X : reverse(Stack)) {
2491 break;
2493 }
2494 assert(Depth < Stack.size() && "Branch destination should be in scope");
2496}
2497
2498unsigned WebAssemblyCFGStackify::getDelegateDepth(
2499 const SmallVectorImpl &Stack, const MachineBasicBlock *MBB) {
2500 if (MBB == FakeCallerBB)
2501 return Stack.size();
2502
2503
2504
2505
2506 if (->isEHPad())
2507 return getBranchDepth(Stack, MBB);
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522 unsigned Depth = 0;
2523 const MachineInstr *EndTry = BeginToEnd[EHPadToTry[MBB]];
2524 for (auto X : reverse(Stack)) {
2525 if (X.first == EndTry->getParent() && X.second == EndTry)
2526 break;
2528 }
2529 assert(Depth < Stack.size() && "Delegate destination should be in scope");
2531}
2532
2533unsigned WebAssemblyCFGStackify::getRethrowDepth(
2534 const SmallVectorImpl &Stack,
2535 const MachineBasicBlock *EHPadToRethrow) {
2536 unsigned Depth = 0;
2537 for (auto X : reverse(Stack)) {
2538 const MachineInstr *End = X.second;
2539 if (End->getOpcode() == WebAssembly::END_TRY) {
2540 auto *EHPad = TryToEHPad[EndToBegin[End]];
2541 if (EHPadToRethrow == EHPad)
2542 break;
2543 }
2545 }
2546 assert(Depth < Stack.size() && "Rethrow destination should be in scope");
2548}
2549
2550void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
2551
2553
2554 auto RewriteOperands = [&](MachineInstr &MI) {
2555
2557 while (MI.getNumOperands() > 0)
2558 MI.removeOperand(MI.getNumOperands() - 1);
2559 for (auto MO : Ops) {
2560 if (MO.isMBB()) {
2561 if (MI.getOpcode() == WebAssembly::DELEGATE)
2563 else if (MI.getOpcode() == WebAssembly::RETHROW)
2565 else
2567 }
2568 MI.addOperand(MF, MO);
2569 }
2570 };
2571
2574 switch (MI.getOpcode()) {
2575 case WebAssembly::BLOCK:
2576 case WebAssembly::TRY:
2577 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=
2579 "Block/try/try_table marker should be balanced");
2580 Stack.pop_back();
2581 break;
2582
2583 case WebAssembly::TRY_TABLE:
2584 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=
2586 "Block/try/try_table marker should be balanced");
2587 Stack.pop_back();
2588 RewriteOperands(MI);
2589 break;
2590
2591 case WebAssembly::LOOP:
2592 assert(Stack.back().first == &MBB && "Loop top should be balanced");
2593 Stack.pop_back();
2594 break;
2595
2596 case WebAssembly::END_BLOCK:
2597 case WebAssembly::END_TRY:
2598 case WebAssembly::END_TRY_TABLE:
2599 Stack.push_back(std::make_pair(&MBB, &MI));
2600 break;
2601
2602 case WebAssembly::END_LOOP:
2604 break;
2605
2606 case WebAssembly::DELEGATE:
2607 RewriteOperands(MI);
2608 Stack.push_back(std::make_pair(&MBB, &MI));
2609 break;
2610
2611 default:
2612 if (MI.isTerminator())
2613 RewriteOperands(MI);
2614 break;
2615 }
2616 }
2617 }
2618 assert(Stack.empty() && "Control flow should be balanced");
2619}
2620
2621void WebAssemblyCFGStackify::cleanupFunctionData(MachineFunction &MF) {
2622 if (FakeCallerBB)
2624 AppendixBB = FakeCallerBB = CallerTrampolineBB = nullptr;
2625}
2626
2627void WebAssemblyCFGStackify::releaseMemory() {
2628 ScopeTops.clear();
2629 BeginToEnd.clear();
2630 EndToBegin.clear();
2631 TryToEHPad.clear();
2632 EHPadToTry.clear();
2633 UnwindDestToTrampoline.clear();
2634}
2635
2636bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
2637 LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
2638 "********** Function: "
2639 << MF.getName() << '\n');
2641 MDT = &getAnalysis().getDomTree();
2642
2643 releaseMemory();
2644
2645
2647
2648
2649
2650 placeMarkers(MF);
2651
2652
2655 removeUnnecessaryInstrs(MF);
2656
2657
2658 rewriteDepthImmediates(MF);
2659
2660
2661
2662 fixEndsAtEndOfFunction(MF);
2663
2664
2665 const auto &TII = *MF.getSubtarget().getInstrInfo();
2667
2668 cleanupFunctionData(MF);
2669
2670 MF.getInfo()->setCFGStackified();
2671 return true;
2672}
unsigned const MachineRegisterInfo * MRI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
const TargetInstrInfo & TII
static const Function * getParent(const Value *V)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static bool explicitlyBranchesTo(MachineBasicBlock *Pred, MachineBasicBlock *MBB)
Test whether Pred has any terminators explicitly branching to MBB, as opposed to falling through.
Definition WebAssemblyCFGStackify.cpp:194
static void addUnreachableAfterTryTables(MachineFunction &MF, const WebAssemblyInstrInfo &TII)
Definition WebAssemblyCFGStackify.cpp:2425
static MachineBasicBlock::iterator getLatestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, const Container &AfterSet)
Definition WebAssemblyCFGStackify.cpp:234
static void splitEndLoopBB(MachineBasicBlock *EndTryTableBB)
Definition WebAssemblyCFGStackify.cpp:1556
static void appendEndToFunction(MachineFunction &MF, const WebAssemblyInstrInfo &TII)
Definition WebAssemblyCFGStackify.cpp:2397
static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB, MachineBasicBlock &Split)
Definition WebAssemblyCFGStackify.cpp:1113
static MachineBasicBlock * getSingleUnwindDest(const MachineInstr *TryTable)
Definition WebAssemblyCFGStackify.cpp:2013
static MachineBasicBlock::iterator getEarliestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, const Container &AfterSet)
Definition WebAssemblyCFGStackify.cpp:210
This file implements WebAssemblyException information analysis.
This file declares WebAssembly-specific per-machine-function information.
This file implements regions used in CFGSort and CFGStackify.
This file declares the WebAssembly-specific subclass of TargetSubtarget.
This file declares the WebAssembly-specific subclass of TargetMachine.
This file contains the declaration of the WebAssembly-specific type parsing utility functions.
This file contains the declaration of the WebAssembly-specific utility functions.
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end.
AnalysisUsage & addRequired()
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
FunctionPass class - This class is used to implement most global optimizations.
bool hasPersonalityFn() const
Check whether this function has a personality function.
BlockT * getHeader() const
ExceptionHandling getExceptionHandlingType() const
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
LLVM_ABI bool hasEHPadSuccessor() const
bool isEHPad() const
Returns true if the block is a landing pad.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
LLVM_ABI void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
LLVM_ABI void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
LLVM_ABI bool isPredecessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a predecessor of this block.
LLVM_ABI DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any debug instructions.
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
LLVM_ABI DebugLoc findPrevDebugLoc(instr_iterator MBBI)
Find the previous valid DebugLoc preceding MBBI, skipping any debug instructions.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
LLVM_ABI DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
iterator_range< succ_iterator > successors()
reverse_iterator rbegin()
iterator_range< pred_iterator > predecessors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
MachineInstrBundleIterator< MachineInstr > iterator
LLVM_ABI StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
void push_back(MachineBasicBlock *MBB)
reverse_iterator rbegin()
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
const DataLayout & getDataLayout() const
Return the DataLayout attached to the Module associated to this MF.
void deleteMachineBasicBlock(MachineBasicBlock *MBB)
DeleteMachineBasicBlock - Delete the given MachineBasicBlock.
Function & getFunction()
Return the LLVM function that this machine code represents.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
const MachineBasicBlock & back() const
BasicBlockListType::iterator iterator
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
const WasmEHFuncInfo * getWasmEHFuncInfo() const
getWasmEHFuncInfo - Return information about how the current function uses Wasm exception handling.
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
const MachineBasicBlock & front() const
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)
CreateMachineInstr - Allocate a new MachineInstr.
void insert(iterator MBBI, MachineBasicBlock *MBB)
const TargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
const MachineInstrBuilder & addExternalSymbol(const char *FnName, unsigned TargetFlags=0) const
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
MachineInstr * getInstr() const
If conversion operators fail, use this method to get the MachineInstr explicitly.
const MachineInstrBuilder & addDef(Register RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register definition operand.
Representation of each machine instruction.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
const MachineBasicBlock * getParent() const
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
const MachineOperand & getOperand(unsigned i) const
MachineOperand class - Representation of each machine instruction operand.
MachineBasicBlock * getMBB() const
static MachineOperand CreateImm(int64_t Val)
void setTargetFlags(unsigned F)
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
Wrapper class representing virtual and physical registers.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
void push_back(const T &Elt)
StringRef - Represent a constant reference to a string, i.e.
virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
const MCAsmInfo * getMCAsmInfo() const
Return target specific asm information.
This class is derived from MachineFunctionInfo and contains private WebAssembly-specific information ...
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool isChild(const MachineInstr &MI, const WebAssemblyFunctionInfo &MFI)
Test whether MI is a child of some other node in an expression tree.
bool isArgument(unsigned Opc)
bool isCatchAll(unsigned Opc)
bool isMarker(unsigned Opc)
unsigned getCopyOpcodeForRegClass(const TargetRegisterClass *RC)
Returns the appropriate copy opcode for the given register class.
wasm::ValType toValType(MVT Type)
cl::opt< bool > WasmUseLegacyEH
MachineInstr * findCatch(MachineBasicBlock *EHPad)
Find a catch instruction from an EH pad.
bool isCatch(unsigned Opc)
BlockType
Used as immediate MachineOperands for block signatures.
bool mayThrow(const MachineInstr &MI)
NodeAddr< UseNode * > Use
@ WASM_OPCODE_CATCH_ALL_REF
This is an optimization pass for GlobalISel generic memory operations.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
auto reverse(ContainerTy &&C)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
FunctionPass * createWebAssemblyCFGStackify()
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...