LLVM 17.0.0git
WebAssemblyExceptionInfo.cpp
Go to the documentation of this file.
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
23#include "llvm/MC/MCAsmInfo.h"
25
26using namespace llvm;
27
28#define DEBUG_TYPE "wasm-exception-info"
29
31
33 "WebAssembly Exception Information", true, true)
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);
52 return false;
53}
54
55// Check if Dst is reachable from Src using BFS. Search only within BBs
56// dominated by Header.
58 const MachineBasicBlock *Dst,
59 const MachineBasicBlock *Header,
60 const MachineDominatorTree &MDT) {
61 assert(MDT.dominates(Header, Dst));
64 WL.push_back(Src);
65
66 while (!WL.empty()) {
67 const auto *MBB = WL.pop_back_val();
68 if (MBB == Dst)
69 return true;
70 Visited.insert(MBB);
71 for (auto *Succ : MBB->successors())
72 if (!Visited.count(Succ) && MDT.dominates(Header, Succ))
73 WL.push_back(Succ);
74 }
75 return false;
76}
77
80 const MachineDominanceFrontier &MDF) {
81 // Postorder traversal of the dominator tree.
83 for (auto *DomNode : post_order(&MDT)) {
84 MachineBasicBlock *EHPad = DomNode->getBlock();
85 if (!EHPad->isEHPad())
86 continue;
87 auto WE = std::make_unique<WebAssemblyException>(EHPad);
88 discoverAndMapException(WE.get(), MDT, MDF);
89 Exceptions.push_back(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();
125 UnwindWEVec;
126 for (auto *DomNode : depth_first(&MDT)) {
127 MachineBasicBlock *EHPad = DomNode->getBlock();
128 if (!EHPad->isEHPad())
129 continue;
130 if (!EHInfo->hasUnwindDest(EHPad))
131 continue;
132 auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
133 auto *SrcWE = getExceptionFor(EHPad);
134 auto *DstWE = getExceptionFor(UnwindDest);
135 if (SrcWE->contains(DstWE)) {
136 UnwindWEVec.push_back(std::make_pair(SrcWE, DstWE));
137 LLVM_DEBUG(dbgs() << "Unwind destination ExceptionInfo fix:\n "
138 << DstWE->getEHPad()->getNumber() << "."
139 << DstWE->getEHPad()->getName()
140 << "'s exception is taken out of "
141 << SrcWE->getEHPad()->getNumber() << "."
142 << SrcWE->getEHPad()->getName() << "'s exception\n");
143 DstWE->setParentException(SrcWE->getParentException());
144 }
145 }
146
147 // After fixing subexception relationship between unwind destinations above,
148 // there can still be remaining discrepancies.
149 //
150 // For example, suppose Exception A is dominated by EHPad A and Exception B is
151 // dominated by EHPad B. EHPad A's unwind destination is EHPad B, but because
152 // EHPad B is dominated by EHPad A, the initial grouping makes Exception B a
153 // subexception of Exception A, and we fix it by taking Exception B out of
154 // Exception A above. But there can still be remaining BBs within Exception A
155 // that are reachable from Exception B. These BBs semantically don't belong
156 // to Exception A and were not a part of this 'catch' clause or cleanup code
157 // in the original code, but they just happened to be grouped within Exception
158 // A because they were dominated by EHPad A. We fix this case by taking those
159 // BBs out of the incorrect exception and all its subexceptions that it
160 // belongs to.
161 //
162 // 1. First, we take out remaining incorrect subexceptions. This part is
163 // easier, because we haven't added BBs to exceptions yet, we only need to
164 // change parent exception pointer.
165 for (auto *DomNode : depth_first(&MDT)) {
166 MachineBasicBlock *EHPad = DomNode->getBlock();
167 if (!EHPad->isEHPad())
168 continue;
169 auto *WE = getExceptionFor(EHPad);
170
171 // For each source EHPad -> unwind destination EHPad
172 for (auto &P : UnwindWEVec) {
173 auto *SrcWE = P.first;
174 auto *DstWE = P.second;
175 // If WE (the current EH pad's exception) is still contained in SrcWE but
176 // reachable from DstWE that was taken out of SrcWE above, we have to take
177 // out WE out of SrcWE too.
178 if (WE != SrcWE && SrcWE->contains(WE) && !DstWE->contains(WE) &&
179 isReachableAmongDominated(DstWE->getEHPad(), EHPad, SrcWE->getEHPad(),
180 MDT)) {
181 LLVM_DEBUG(dbgs() << "Remaining reachable ExceptionInfo fix:\n "
182 << WE->getEHPad()->getNumber() << "."
183 << WE->getEHPad()->getName()
184 << "'s exception is taken out of "
185 << SrcWE->getEHPad()->getNumber() << "."
186 << SrcWE->getEHPad()->getName() << "'s exception\n");
187 WE->setParentException(SrcWE->getParentException());
188 }
189 }
190 }
191
192 // Add BBs to exceptions' block set. This is a preparation to take out
193 // remaining incorect BBs from exceptions, because we need to iterate over BBs
194 // for each exception.
195 for (auto *DomNode : post_order(&MDT)) {
196 MachineBasicBlock *MBB = DomNode->getBlock();
198 for (; WE; WE = WE->getParentException())
199 WE->addToBlocksSet(MBB);
200 }
201
202 // 2. We take out remaining individual BBs out. Now we have added BBs to each
203 // exceptions' BlockSet, when we take a BB out of an exception, we need to fix
204 // those sets too.
205 for (auto &P : UnwindWEVec) {
206 auto *SrcWE = P.first;
207 auto *DstWE = P.second;
208
209 for (auto *MBB : SrcWE->getBlocksSet()) {
210 if (MBB->isEHPad()) {
211 assert(!isReachableAmongDominated(DstWE->getEHPad(), MBB,
212 SrcWE->getEHPad(), MDT) &&
213 "We already handled EH pads above");
214 continue;
215 }
216 if (isReachableAmongDominated(DstWE->getEHPad(), MBB, SrcWE->getEHPad(),
217 MDT)) {
218 LLVM_DEBUG(dbgs() << "Remainder BB: " << MBB->getNumber() << "."
219 << MBB->getName() << " is\n");
221 while (InnerWE != SrcWE) {
223 << " removed from " << InnerWE->getEHPad()->getNumber()
224 << "." << InnerWE->getEHPad()->getName()
225 << "'s exception\n");
226 InnerWE->removeFromBlocksSet(MBB);
227 InnerWE = InnerWE->getParentException();
228 }
229 SrcWE->removeFromBlocksSet(MBB);
230 LLVM_DEBUG(dbgs() << " removed from " << SrcWE->getEHPad()->getNumber()
231 << "." << SrcWE->getEHPad()->getName()
232 << "'s exception\n");
233 changeExceptionFor(MBB, SrcWE->getParentException());
234 if (SrcWE->getParentException())
235 SrcWE->getParentException()->addToBlocksSet(MBB);
236 }
237 }
238 }
239
240 // Add BBs to exceptions' block vector
241 for (auto *DomNode : post_order(&MDT)) {
242 MachineBasicBlock *MBB = DomNode->getBlock();
244 for (; WE; WE = WE->getParentException())
246 }
247
249 ExceptionPointers.reserve(Exceptions.size());
250
251 // Add subexceptions to exceptions
252 for (auto &WE : Exceptions) {
253 ExceptionPointers.push_back(WE.get());
254 if (WE->getParentException())
255 WE->getParentException()->getSubExceptions().push_back(std::move(WE));
256 else
257 addTopLevelException(std::move(WE));
258 }
259
260 // For convenience, Blocks and SubExceptions are inserted in postorder.
261 // Reverse the lists.
262 for (auto *WE : ExceptionPointers) {
263 WE->reverseBlock();
264 std::reverse(WE->getSubExceptions().begin(), WE->getSubExceptions().end());
265 }
266}
267
269 BBMap.clear();
270 TopLevelExceptions.clear();
271}
272
274 AU.setPreservesAll();
278}
279
280void WebAssemblyExceptionInfo::discoverAndMapException(
282 const MachineDominanceFrontier &MDF) {
283 unsigned NumBlocks = 0;
284 unsigned NumSubExceptions = 0;
285
286 // Map blocks that belong to a catchpad / cleanuppad
287 MachineBasicBlock *EHPad = WE->getEHPad();
289 WL.push_back(EHPad);
290 while (!WL.empty()) {
292
293 // Find its outermost discovered exception. If this is a discovered block,
294 // check if it is already discovered to be a subexception of this exception.
295 WebAssemblyException *SubE = getOutermostException(MBB);
296 if (SubE) {
297 if (SubE != WE) {
298 // Discover a subexception of this exception.
299 SubE->setParentException(WE);
300 ++NumSubExceptions;
301 NumBlocks += SubE->getBlocksVector().capacity();
302 // All blocks that belong to this subexception have been already
303 // discovered. Skip all of them. Add the subexception's landing pad's
304 // dominance frontier to the worklist.
305 for (auto &Frontier : MDF.find(SubE->getEHPad())->second)
306 if (MDT.dominates(EHPad, Frontier))
307 WL.push_back(Frontier);
308 }
309 continue;
310 }
311
312 // This is an undiscovered block. Map it to the current exception.
314 ++NumBlocks;
315
316 // Add successors dominated by the current BB to the worklist.
317 for (auto *Succ : MBB->successors())
318 if (MDT.dominates(EHPad, Succ))
319 WL.push_back(Succ);
320 }
321
322 WE->getSubExceptions().reserve(NumSubExceptions);
323 WE->reserveBlocks(NumBlocks);
324}
325
327WebAssemblyExceptionInfo::getOutermostException(MachineBasicBlock *MBB) const {
329 if (WE) {
330 while (WebAssemblyException *Parent = WE->getParentException())
331 WE = Parent;
332 }
333 return WE;
334}
335
337 OS.indent(Depth * 2) << "Exception at depth " << getExceptionDepth()
338 << " containing: ";
339
340 for (unsigned I = 0; I < getBlocks().size(); ++I) {
342 if (I)
343 OS << ", ";
344 OS << "%bb." << MBB->getNumber();
345 if (const auto *BB = MBB->getBasicBlock())
346 if (BB->hasName())
347 OS << "." << BB->getName();
348
349 if (getEHPad() == MBB)
350 OS << " (landing-pad)";
351 }
352 OS << "\n";
353
354 for (auto &SubE : SubExceptions)
355 SubE->print(OS, Depth + 2);
356}
357
358#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
360#endif
361
363 WE.print(OS);
364 return OS;
365}
366
368 for (auto &WE : TopLevelExceptions)
369 WE->print(OS);
370}
MachineBasicBlock & MBB
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
WebAssembly Exception Information
static bool isReachableAmongDominated(const MachineBasicBlock *Src, const MachineBasicBlock *Dst, const MachineBasicBlock *Header, const MachineDominatorTree &MDT)
#define DEBUG_TYPE
WebAssembly Exception true
This file implements WebAssemblyException information analysis.
This file provides WebAssembly-specific target descriptions.
This file contains the declaration of the WebAssembly-specific utility functions.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
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...
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
iterator_range< succ_iterator > successors()
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
iterator find(MachineBasicBlock *B)
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const WasmEHFuncInfo * getWasmEHFuncInfo() const
getWasmEHFuncInfo - Return information about how the current function uses Wasm exception handling.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void reserve(size_type N)
Definition: SmallVector.h:667
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
void changeExceptionFor(const MachineBasicBlock *MBB, WebAssemblyException *WE)
void addTopLevelException(std::unique_ptr< WebAssemblyException > WE)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
void recalculate(MachineFunction &MF, MachineDominatorTree &MDT, const MachineDominanceFrontier &MDF)
WebAssemblyException * getExceptionFor(const MachineBasicBlock *MBB) const
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void print(raw_ostream &OS, unsigned Depth=0) const
MachineBasicBlock * getEHPad() const
void addToBlocksSet(MachineBasicBlock *MBB)
const std::vector< std::unique_ptr< WebAssemblyException > > & getSubExceptions() const
ArrayRef< MachineBasicBlock * > getBlocks() const
std::vector< MachineBasicBlock * > & getBlocksVector()
WebAssemblyException * getParentException() const
void removeFromBlocksSet(MachineBasicBlock *MBB)
void setParentException(WebAssemblyException *WE)
void addToBlocksVector(MachineBasicBlock *MBB)
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
iterator_range< po_iterator< T > > post_order(const T &G)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
iterator_range< df_iterator< T > > depth_first(const T &G)