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

source code of llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp