1 //===--- WebAssemblyExceptionInfo.cpp - Exception Infomation --------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// \brief This file implements WebAssemblyException information analysis.
11 ///
12 //===----------------------------------------------------------------------===//
13
14 #include "WebAssemblyExceptionInfo.h"
15 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
16 #include "WebAssemblyUtilities.h"
17 #include "llvm/ADT/PostOrderIterator.h"
18 #include "llvm/CodeGen/MachineDominanceFrontier.h"
19 #include "llvm/CodeGen/MachineDominators.h"
20 #include "llvm/InitializePasses.h"
21
22 using namespace llvm;
23
24 #define DEBUG_TYPE "wasm-exception-info"
25
26 char WebAssemblyExceptionInfo::ID = 0;
27
28 INITIALIZE_PASS_BEGIN(WebAssemblyExceptionInfo, DEBUG_TYPE,
29 "WebAssembly Exception Information", true, true)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)30 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
31 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
32 INITIALIZE_PASS_END(WebAssemblyExceptionInfo, DEBUG_TYPE,
33 "WebAssembly Exception Information", true, true)
34
35 bool WebAssemblyExceptionInfo::runOnMachineFunction(MachineFunction &MF) {
36 LLVM_DEBUG(dbgs() << "********** Exception Info Calculation **********\n"
37 "********** Function: "
38 << MF.getName() << '\n');
39 releaseMemory();
40 auto &MDT = getAnalysis<MachineDominatorTree>();
41 auto &MDF = getAnalysis<MachineDominanceFrontier>();
42 recalculate(MDT, MDF);
43 return false;
44 }
45
recalculate(MachineDominatorTree & MDT,const MachineDominanceFrontier & MDF)46 void WebAssemblyExceptionInfo::recalculate(
47 MachineDominatorTree &MDT, const MachineDominanceFrontier &MDF) {
48 // Postorder traversal of the dominator tree.
49 SmallVector<WebAssemblyException *, 8> Exceptions;
50 for (auto DomNode : post_order(&MDT)) {
51 MachineBasicBlock *EHPad = DomNode->getBlock();
52 if (!EHPad->isEHPad())
53 continue;
54 auto *WE = new WebAssemblyException(EHPad);
55 discoverAndMapException(WE, MDT, MDF);
56 Exceptions.push_back(WE);
57 }
58
59 // Add BBs to exceptions
60 for (auto DomNode : post_order(&MDT)) {
61 MachineBasicBlock *MBB = DomNode->getBlock();
62 WebAssemblyException *WE = getExceptionFor(MBB);
63 for (; WE; WE = WE->getParentException())
64 WE->addBlock(MBB);
65 }
66
67 // Add subexceptions to exceptions
68 for (auto *WE : Exceptions) {
69 if (WE->getParentException())
70 WE->getParentException()->getSubExceptions().push_back(WE);
71 else
72 addTopLevelException(WE);
73 }
74
75 // For convenience, Blocks and SubExceptions are inserted in postorder.
76 // Reverse the lists.
77 for (auto *WE : Exceptions) {
78 WE->reverseBlock();
79 std::reverse(WE->getSubExceptions().begin(), WE->getSubExceptions().end());
80 }
81 }
82
releaseMemory()83 void WebAssemblyExceptionInfo::releaseMemory() {
84 BBMap.clear();
85 DeleteContainerPointers(TopLevelExceptions);
86 TopLevelExceptions.clear();
87 }
88
getAnalysisUsage(AnalysisUsage & AU) const89 void WebAssemblyExceptionInfo::getAnalysisUsage(AnalysisUsage &AU) const {
90 AU.setPreservesAll();
91 AU.addRequired<MachineDominatorTree>();
92 AU.addRequired<MachineDominanceFrontier>();
93 MachineFunctionPass::getAnalysisUsage(AU);
94 }
95
discoverAndMapException(WebAssemblyException * WE,const MachineDominatorTree & MDT,const MachineDominanceFrontier & MDF)96 void WebAssemblyExceptionInfo::discoverAndMapException(
97 WebAssemblyException *WE, const MachineDominatorTree &MDT,
98 const MachineDominanceFrontier &MDF) {
99 unsigned NumBlocks = 0;
100 unsigned NumSubExceptions = 0;
101
102 // Map blocks that belong to a catchpad / cleanuppad
103 MachineBasicBlock *EHPad = WE->getEHPad();
104 SmallVector<MachineBasicBlock *, 8> WL;
105 WL.push_back(EHPad);
106 while (!WL.empty()) {
107 MachineBasicBlock *MBB = WL.pop_back_val();
108
109 // Find its outermost discovered exception. If this is a discovered block,
110 // check if it is already discovered to be a subexception of this exception.
111 WebAssemblyException *SubE = getOutermostException(MBB);
112 if (SubE) {
113 if (SubE != WE) {
114 // Discover a subexception of this exception.
115 SubE->setParentException(WE);
116 ++NumSubExceptions;
117 NumBlocks += SubE->getBlocksVector().capacity();
118 // All blocks that belong to this subexception have been already
119 // discovered. Skip all of them. Add the subexception's landing pad's
120 // dominance frontier to the worklist.
121 for (auto &Frontier : MDF.find(SubE->getEHPad())->second)
122 if (MDT.dominates(EHPad, Frontier))
123 WL.push_back(Frontier);
124 }
125 continue;
126 }
127
128 // This is an undiscovered block. Map it to the current exception.
129 changeExceptionFor(MBB, WE);
130 ++NumBlocks;
131
132 // Add successors dominated by the current BB to the worklist.
133 for (auto *Succ : MBB->successors())
134 if (MDT.dominates(EHPad, Succ))
135 WL.push_back(Succ);
136 }
137
138 WE->getSubExceptions().reserve(NumSubExceptions);
139 WE->reserveBlocks(NumBlocks);
140 }
141
142 WebAssemblyException *
getOutermostException(MachineBasicBlock * MBB) const143 WebAssemblyExceptionInfo::getOutermostException(MachineBasicBlock *MBB) const {
144 WebAssemblyException *WE = getExceptionFor(MBB);
145 if (WE) {
146 while (WebAssemblyException *Parent = WE->getParentException())
147 WE = Parent;
148 }
149 return WE;
150 }
151
print(raw_ostream & OS,unsigned Depth) const152 void WebAssemblyException::print(raw_ostream &OS, unsigned Depth) const {
153 OS.indent(Depth * 2) << "Exception at depth " << getExceptionDepth()
154 << " containing: ";
155
156 for (unsigned I = 0; I < getBlocks().size(); ++I) {
157 MachineBasicBlock *MBB = getBlocks()[I];
158 if (I)
159 OS << ", ";
160 OS << "%bb." << MBB->getNumber();
161 if (const auto *BB = MBB->getBasicBlock())
162 if (BB->hasName())
163 OS << "." << BB->getName();
164
165 if (getEHPad() == MBB)
166 OS << " (landing-pad)";
167 }
168 OS << "\n";
169
170 for (auto &SubE : SubExceptions)
171 SubE->print(OS, Depth + 2);
172 }
173
174 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const175 LLVM_DUMP_METHOD void WebAssemblyException::dump() const { print(dbgs()); }
176 #endif
177
operator <<(raw_ostream & OS,const WebAssemblyException & WE)178 raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE) {
179 WE.print(OS);
180 return OS;
181 }
182
print(raw_ostream & OS,const Module *) const183 void WebAssemblyExceptionInfo::print(raw_ostream &OS, const Module *) const {
184 for (auto *WE : TopLevelExceptions)
185 WE->print(OS);
186 }
187