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/DepthFirstIterator.h"
18#include "llvm/ADT/PostOrderIterator.h"
19#include "llvm/CodeGen/MachineDominanceFrontier.h"
20#include "llvm/CodeGen/MachineDominators.h"
21#include "llvm/CodeGen/WasmEHFuncInfo.h"
22#include "llvm/InitializePasses.h"
23#include "llvm/IR/Function.h"
24#include "llvm/MC/MCAsmInfo.h"
25#include "llvm/Target/TargetMachine.h"
26
27using namespace llvm;
28
29#define DEBUG_TYPE "wasm-exception-info"
30
31char WebAssemblyExceptionInfo::ID = 0;
32
33INITIALIZE_PASS_BEGIN(WebAssemblyExceptionInfo, DEBUG_TYPE,
34 "WebAssembly Exception Information", true, true)
35INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
36INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
37INITIALIZE_PASS_END(WebAssemblyExceptionInfo, DEBUG_TYPE,
38 "WebAssembly Exception Information", true, true)
39
40bool WebAssemblyExceptionInfo::runOnMachineFunction(MachineFunction &MF) {
41 LLVM_DEBUG(dbgs() << "********** Exception Info Calculation **********\n"
42 "********** Function: "
43 << MF.getName() << '\n');
44 releaseMemory();
45 if (MF.getTarget().getMCAsmInfo()->getExceptionHandlingType() !=
46 ExceptionHandling::Wasm ||
47 !MF.getFunction().hasPersonalityFn())
48 return false;
49 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
50 auto &MDF = getAnalysis<MachineDominanceFrontier>();
51 recalculate(MF, MDT, MDF);
52 LLVM_DEBUG(dump());
53 return false;
54}
55
56// Check if Dst is reachable from Src using BFS. Search only within BBs
57// dominated by Header.
58static bool isReachableAmongDominated(const MachineBasicBlock *Src,
59 const MachineBasicBlock *Dst,
60 const MachineBasicBlock *Header,
61 const MachineDominatorTree &MDT) {
62 assert(MDT.dominates(Header, Dst));
63 SmallVector<const MachineBasicBlock *, 8> WL;
64 SmallPtrSet<const MachineBasicBlock *, 8> Visited;
65 WL.push_back(Elt: Src);
66
67 while (!WL.empty()) {
68 const auto *MBB = WL.pop_back_val();
69 if (MBB == Dst)
70 return true;
71 Visited.insert(Ptr: MBB);
72 for (auto *Succ : MBB->successors())
73 if (!Visited.count(Ptr: Succ) && MDT.dominates(A: Header, B: Succ))
74 WL.push_back(Elt: Succ);
75 }
76 return false;
77}
78
79void WebAssemblyExceptionInfo::recalculate(
80 MachineFunction &MF, MachineDominatorTree &MDT,
81 const MachineDominanceFrontier &MDF) {
82 // Postorder traversal of the dominator tree.
83 SmallVector<std::unique_ptr<WebAssemblyException>, 8> Exceptions;
84 for (auto *DomNode : post_order(G: &MDT)) {
85 MachineBasicBlock *EHPad = DomNode->getBlock();
86 if (!EHPad->isEHPad())
87 continue;
88 auto WE = std::make_unique<WebAssemblyException>(args&: EHPad);
89 discoverAndMapException(WE: WE.get(), MDT, MDF);
90 Exceptions.push_back(Elt: std::move(WE));
91 }
92
93 // WasmEHFuncInfo contains a map of <catchpad, its next unwind destination>,
94 // which means, if an exception is not caught by the catchpad, it should end
95 // up in the next unwind destination stored in this data structure. (It is
96 // written as catchswitch's 'unwind' destination in ll files.) The below is an
97 // intuitive example of their relationship in C++ code:
98 // try {
99 // try {
100 // } catch (int) { // catchpad
101 // ... // this catch (int) { ... } is grouped as an exception
102 // }
103 // } catch (...) { // next unwind destination
104 // }
105 // (The example is try-catches for illustration purpose, but the unwind
106 // destination can be also a cleanuppad generated by destructor calls.) So the
107 // unwind destination is in the outside of the catchpad's exception.
108 //
109 // We group exceptions in this analysis simply by including all BBs dominated
110 // by an EH pad. But in case the EH pad's unwind destination does not have any
111 // children outside of the exception, that unwind destination ends up also
112 // being dominated by the EH pad and included in the exception, which is not
113 // semantically correct, because it unwinds/rethrows into an inner scope.
114 //
115 // Here we extract those unwind destinations from their (incorrect) parent
116 // exception. Note that the unwind destinations may not be an immediate
117 // children of the parent exception, so we have to traverse the parent chain.
118 //
119 // We should traverse BBs in the preorder of the dominator tree, because
120 // otherwise the result can be incorrect. For example, when there are three
121 // exceptions A, B, and C and A > B > C (> is subexception relationship here),
122 // and A's unwind destination is B and B's is C. When we visit B before A, we
123 // end up extracting C only out of B but not out of A.
124 const auto *EHInfo = MF.getWasmEHFuncInfo();
125 assert(EHInfo);
126 SmallVector<std::pair<WebAssemblyException *, WebAssemblyException *>>
127 UnwindWEVec;
128 for (auto *DomNode : depth_first(G: &MDT)) {
129 MachineBasicBlock *EHPad = DomNode->getBlock();
130 if (!EHPad->isEHPad())
131 continue;
132 if (!EHInfo->hasUnwindDest(MBB: EHPad))
133 continue;
134 auto *UnwindDest = EHInfo->getUnwindDest(MBB: EHPad);
135 auto *SrcWE = getExceptionFor(MBB: EHPad);
136 auto *DstWE = getExceptionFor(MBB: UnwindDest);
137 if (SrcWE->contains(WE: DstWE)) {
138 UnwindWEVec.push_back(Elt: std::make_pair(x&: SrcWE, y&: DstWE));
139 LLVM_DEBUG(dbgs() << "Unwind destination ExceptionInfo fix:\n "
140 << DstWE->getEHPad()->getNumber() << "."
141 << DstWE->getEHPad()->getName()
142 << "'s exception is taken out of "
143 << SrcWE->getEHPad()->getNumber() << "."
144 << SrcWE->getEHPad()->getName() << "'s exception\n");
145 DstWE->setParentException(SrcWE->getParentException());
146 }
147 }
148
149 // After fixing subexception relationship between unwind destinations above,
150 // there can still be remaining discrepancies.
151 //
152 // For example, suppose Exception A is dominated by EHPad A and Exception B is
153 // dominated by EHPad B. EHPad A's unwind destination is EHPad B, but because
154 // EHPad B is dominated by EHPad A, the initial grouping makes Exception B a
155 // subexception of Exception A, and we fix it by taking Exception B out of
156 // Exception A above. But there can still be remaining BBs within Exception A
157 // that are reachable from Exception B. These BBs semantically don't belong
158 // to Exception A and were not a part of this 'catch' clause or cleanup code
159 // in the original code, but they just happened to be grouped within Exception
160 // A because they were dominated by EHPad A. We fix this case by taking those
161 // BBs out of the incorrect exception and all its subexceptions that it
162 // belongs to.
163 //
164 // 1. First, we take out remaining incorrect subexceptions. This part is
165 // easier, because we haven't added BBs to exceptions yet, we only need to
166 // change parent exception pointer.
167 for (auto *DomNode : depth_first(G: &MDT)) {
168 MachineBasicBlock *EHPad = DomNode->getBlock();
169 if (!EHPad->isEHPad())
170 continue;
171 auto *WE = getExceptionFor(MBB: EHPad);
172
173 // For each source EHPad -> unwind destination EHPad
174 for (auto &P : UnwindWEVec) {
175 auto *SrcWE = P.first;
176 auto *DstWE = P.second;
177 // If WE (the current EH pad's exception) is still contained in SrcWE but
178 // reachable from DstWE that was taken out of SrcWE above, we have to take
179 // out WE out of SrcWE too.
180 if (WE != SrcWE && SrcWE->contains(WE) && !DstWE->contains(WE) &&
181 isReachableAmongDominated(Src: DstWE->getEHPad(), Dst: EHPad, Header: SrcWE->getEHPad(),
182 MDT)) {
183 LLVM_DEBUG(dbgs() << "Remaining reachable ExceptionInfo fix:\n "
184 << WE->getEHPad()->getNumber() << "."
185 << WE->getEHPad()->getName()
186 << "'s exception is taken out of "
187 << SrcWE->getEHPad()->getNumber() << "."
188 << SrcWE->getEHPad()->getName() << "'s exception\n");
189 WE->setParentException(SrcWE->getParentException());
190 }
191 }
192 }
193
194 // Add BBs to exceptions' block set. This is a preparation to take out
195 // remaining incorect BBs from exceptions, because we need to iterate over BBs
196 // for each exception.
197 for (auto *DomNode : post_order(G: &MDT)) {
198 MachineBasicBlock *MBB = DomNode->getBlock();
199 WebAssemblyException *WE = getExceptionFor(MBB);
200 for (; WE; WE = WE->getParentException())
201 WE->addToBlocksSet(MBB);
202 }
203
204 // 2. We take out remaining individual BBs out. Now we have added BBs to each
205 // exceptions' BlockSet, when we take a BB out of an exception, we need to fix
206 // those sets too.
207 for (auto &P : UnwindWEVec) {
208 auto *SrcWE = P.first;
209 auto *DstWE = P.second;
210
211 SrcWE->getBlocksSet().remove_if(P: [&](MachineBasicBlock *MBB){
212 if (MBB->isEHPad()) {
213 assert(!isReachableAmongDominated(DstWE->getEHPad(), MBB,
214 SrcWE->getEHPad(), MDT) &&
215 "We already handled EH pads above");
216 return false;
217 }
218 if (isReachableAmongDominated(Src: DstWE->getEHPad(), Dst: MBB, Header: SrcWE->getEHPad(),
219 MDT)) {
220 LLVM_DEBUG(dbgs() << "Remainder BB: " << MBB->getNumber() << "."
221 << MBB->getName() << " is\n");
222 WebAssemblyException *InnerWE = getExceptionFor(MBB);
223 while (InnerWE != SrcWE) {
224 LLVM_DEBUG(dbgs()
225 << " removed from " << InnerWE->getEHPad()->getNumber()
226 << "." << InnerWE->getEHPad()->getName()
227 << "'s exception\n");
228 InnerWE->removeFromBlocksSet(MBB);
229 InnerWE = InnerWE->getParentException();
230 }
231 LLVM_DEBUG(dbgs() << " removed from " << SrcWE->getEHPad()->getNumber()
232 << "." << SrcWE->getEHPad()->getName()
233 << "'s exception\n");
234 changeExceptionFor(MBB, WE: SrcWE->getParentException());
235 if (SrcWE->getParentException())
236 SrcWE->getParentException()->addToBlocksSet(MBB);
237 return true;
238 }
239 return false;
240 });
241 }
242
243 // Add BBs to exceptions' block vector
244 for (auto *DomNode : post_order(G: &MDT)) {
245 MachineBasicBlock *MBB = DomNode->getBlock();
246 WebAssemblyException *WE = getExceptionFor(MBB);
247 for (; WE; WE = WE->getParentException())
248 WE->addToBlocksVector(MBB);
249 }
250
251 SmallVector<WebAssemblyException*, 8> ExceptionPointers;
252 ExceptionPointers.reserve(N: Exceptions.size());
253
254 // Add subexceptions to exceptions
255 for (auto &WE : Exceptions) {
256 ExceptionPointers.push_back(Elt: WE.get());
257 if (WE->getParentException())
258 WE->getParentException()->getSubExceptions().push_back(x: std::move(WE));
259 else
260 addTopLevelException(WE: std::move(WE));
261 }
262
263 // For convenience, Blocks and SubExceptions are inserted in postorder.
264 // Reverse the lists.
265 for (auto *WE : ExceptionPointers) {
266 WE->reverseBlock();
267 std::reverse(first: WE->getSubExceptions().begin(), last: WE->getSubExceptions().end());
268 }
269}
270
271void WebAssemblyExceptionInfo::releaseMemory() {
272 BBMap.clear();
273 TopLevelExceptions.clear();
274}
275
276void WebAssemblyExceptionInfo::getAnalysisUsage(AnalysisUsage &AU) const {
277 AU.setPreservesAll();
278 AU.addRequired<MachineDominatorTreeWrapperPass>();
279 AU.addRequired<MachineDominanceFrontier>();
280 MachineFunctionPass::getAnalysisUsage(AU);
281}
282
283void WebAssemblyExceptionInfo::discoverAndMapException(
284 WebAssemblyException *WE, const MachineDominatorTree &MDT,
285 const MachineDominanceFrontier &MDF) {
286 unsigned NumBlocks = 0;
287 unsigned NumSubExceptions = 0;
288
289 // Map blocks that belong to a catchpad / cleanuppad
290 MachineBasicBlock *EHPad = WE->getEHPad();
291 SmallVector<MachineBasicBlock *, 8> WL;
292 WL.push_back(Elt: EHPad);
293 while (!WL.empty()) {
294 MachineBasicBlock *MBB = WL.pop_back_val();
295
296 // Find its outermost discovered exception. If this is a discovered block,
297 // check if it is already discovered to be a subexception of this exception.
298 WebAssemblyException *SubE = getOutermostException(MBB);
299 if (SubE) {
300 if (SubE != WE) {
301 // Discover a subexception of this exception.
302 SubE->setParentException(WE);
303 ++NumSubExceptions;
304 NumBlocks += SubE->getBlocksVector().capacity();
305 // All blocks that belong to this subexception have been already
306 // discovered. Skip all of them. Add the subexception's landing pad's
307 // dominance frontier to the worklist.
308 for (auto &Frontier : MDF.find(B: SubE->getEHPad())->second)
309 if (MDT.dominates(A: EHPad, B: Frontier))
310 WL.push_back(Elt: Frontier);
311 }
312 continue;
313 }
314
315 // This is an undiscovered block. Map it to the current exception.
316 changeExceptionFor(MBB, WE);
317 ++NumBlocks;
318
319 // Add successors dominated by the current BB to the worklist.
320 for (auto *Succ : MBB->successors())
321 if (MDT.dominates(A: EHPad, B: Succ))
322 WL.push_back(Elt: Succ);
323 }
324
325 WE->getSubExceptions().reserve(n: NumSubExceptions);
326 WE->reserveBlocks(Size: NumBlocks);
327}
328
329WebAssemblyException *
330WebAssemblyExceptionInfo::getOutermostException(MachineBasicBlock *MBB) const {
331 WebAssemblyException *WE = getExceptionFor(MBB);
332 if (WE) {
333 while (WebAssemblyException *Parent = WE->getParentException())
334 WE = Parent;
335 }
336 return WE;
337}
338
339void WebAssemblyException::print(raw_ostream &OS, unsigned Depth) const {
340 OS.indent(NumSpaces: Depth * 2) << "Exception at depth " << getExceptionDepth()
341 << " containing: ";
342
343 for (unsigned I = 0; I < getBlocks().size(); ++I) {
344 MachineBasicBlock *MBB = getBlocks()[I];
345 if (I)
346 OS << ", ";
347 OS << "%bb." << MBB->getNumber();
348 if (const auto *BB = MBB->getBasicBlock())
349 if (BB->hasName())
350 OS << "." << BB->getName();
351
352 if (getEHPad() == MBB)
353 OS << " (landing-pad)";
354 }
355 OS << "\n";
356
357 for (auto &SubE : SubExceptions)
358 SubE->print(OS, Depth: Depth + 2);
359}
360
361#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
362LLVM_DUMP_METHOD void WebAssemblyException::dump() const { print(dbgs()); }
363#endif
364
365raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE) {
366 WE.print(OS);
367 return OS;
368}
369
370void WebAssemblyExceptionInfo::print(raw_ostream &OS, const Module *) const {
371 for (auto &WE : TopLevelExceptions)
372 WE->print(OS);
373}
374