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 | |
26 | using namespace llvm; |
27 | |
28 | #define DEBUG_TYPE "wasm-exception-info" |
29 | |
30 | char WebAssemblyExceptionInfo::ID = 0; |
31 | |
32 | INITIALIZE_PASS_BEGIN(WebAssemblyExceptionInfo, DEBUG_TYPE, |
33 | "WebAssembly Exception Information" , true, true) |
34 | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
35 | INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier) |
36 | INITIALIZE_PASS_END(WebAssemblyExceptionInfo, DEBUG_TYPE, |
37 | "WebAssembly Exception Information" , true, true) |
38 | |
39 | bool 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. |
57 | static bool isReachableAmongDominated(const MachineBasicBlock *Src, |
58 | const MachineBasicBlock *Dst, |
59 | const MachineBasicBlock *, |
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 | |
78 | void 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 | |
269 | void WebAssemblyExceptionInfo::releaseMemory() { |
270 | BBMap.clear(); |
271 | TopLevelExceptions.clear(); |
272 | } |
273 | |
274 | void WebAssemblyExceptionInfo::getAnalysisUsage(AnalysisUsage &AU) const { |
275 | AU.setPreservesAll(); |
276 | AU.addRequired<MachineDominatorTree>(); |
277 | AU.addRequired<MachineDominanceFrontier>(); |
278 | MachineFunctionPass::getAnalysisUsage(AU); |
279 | } |
280 | |
281 | void 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 | |
327 | WebAssemblyException * |
328 | WebAssemblyExceptionInfo::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 | |
337 | void 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) |
360 | LLVM_DUMP_METHOD void WebAssemblyException::dump() const { print(OS&: dbgs()); } |
361 | #endif |
362 | |
363 | raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE) { |
364 | WE.print(OS); |
365 | return OS; |
366 | } |
367 | |
368 | void WebAssemblyExceptionInfo::print(raw_ostream &OS, const Module *) const { |
369 | for (auto &WE : TopLevelExceptions) |
370 | WE->print(OS); |
371 | } |
372 | |