1 //===-- WasmEHPrepare - Prepare excepton handling for WebAssembly --------===//
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 // This transformation is designed for use by code generators which use
10 // WebAssembly exception handling scheme. This currently supports C++
11 // exceptions.
12 //
13 // WebAssembly exception handling uses Windows exception IR for the middle level
14 // representation. This pass does the following transformation for every
15 // catchpad block:
16 // (In C-style pseudocode)
17 //
18 // - Before:
19 // catchpad ...
20 // exn = wasm.get.exception();
21 // selector = wasm.get.selector();
22 // ...
23 //
24 // - After:
25 // catchpad ...
26 // exn = wasm.catch(WebAssembly::CPP_EXCEPTION);
27 // // Only add below in case it's not a single catch (...)
28 // wasm.landingpad.index(index);
29 // __wasm_lpad_context.lpad_index = index;
30 // __wasm_lpad_context.lsda = wasm.lsda();
31 // _Unwind_CallPersonality(exn);
32 // selector = __wasm.landingpad_context.selector;
33 // ...
34 //
35 //
36 // * Background: Direct personality function call
37 // In WebAssembly EH, the VM is responsible for unwinding the stack once an
38 // exception is thrown. After the stack is unwound, the control flow is
39 // transfered to WebAssembly 'catch' instruction.
40 //
41 // Unwinding the stack is not done by libunwind but the VM, so the personality
42 // function in libcxxabi cannot be called from libunwind during the unwinding
43 // process. So after a catch instruction, we insert a call to a wrapper function
44 // in libunwind that in turn calls the real personality function.
45 //
46 // In Itanium EH, if the personality function decides there is no matching catch
47 // clause in a call frame and no cleanup action to perform, the unwinder doesn't
48 // stop there and continues unwinding. But in Wasm EH, the unwinder stops at
49 // every call frame with a catch intruction, after which the personality
50 // function is called from the compiler-generated user code here.
51 //
52 // In libunwind, we have this struct that serves as a communincation channel
53 // between the compiler-generated user code and the personality function in
54 // libcxxabi.
55 //
56 // struct _Unwind_LandingPadContext {
57 // uintptr_t lpad_index;
58 // uintptr_t lsda;
59 // uintptr_t selector;
60 // };
61 // struct _Unwind_LandingPadContext __wasm_lpad_context = ...;
62 //
63 // And this wrapper in libunwind calls the personality function.
64 //
65 // _Unwind_Reason_Code _Unwind_CallPersonality(void *exception_ptr) {
66 // struct _Unwind_Exception *exception_obj =
67 // (struct _Unwind_Exception *)exception_ptr;
68 // _Unwind_Reason_Code ret = __gxx_personality_v0(
69 // 1, _UA_CLEANUP_PHASE, exception_obj->exception_class, exception_obj,
70 // (struct _Unwind_Context *)__wasm_lpad_context);
71 // return ret;
72 // }
73 //
74 // We pass a landing pad index, and the address of LSDA for the current function
75 // to the wrapper function _Unwind_CallPersonality in libunwind, and we retrieve
76 // the selector after it returns.
77 //
78 //===----------------------------------------------------------------------===//
79
80 #include "llvm/ADT/BreadthFirstIterator.h"
81 #include "llvm/ADT/SetVector.h"
82 #include "llvm/ADT/Statistic.h"
83 #include "llvm/ADT/Triple.h"
84 #include "llvm/Analysis/DomTreeUpdater.h"
85 #include "llvm/CodeGen/Passes.h"
86 #include "llvm/CodeGen/TargetLowering.h"
87 #include "llvm/CodeGen/TargetSubtargetInfo.h"
88 #include "llvm/CodeGen/WasmEHFuncInfo.h"
89 #include "llvm/IR/Dominators.h"
90 #include "llvm/IR/IRBuilder.h"
91 #include "llvm/IR/Intrinsics.h"
92 #include "llvm/IR/IntrinsicsWebAssembly.h"
93 #include "llvm/InitializePasses.h"
94 #include "llvm/Pass.h"
95 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
96
97 using namespace llvm;
98
99 #define DEBUG_TYPE "wasmehprepare"
100
101 namespace {
102 class WasmEHPrepare : public FunctionPass {
103 Type *LPadContextTy = nullptr; // type of 'struct _Unwind_LandingPadContext'
104 GlobalVariable *LPadContextGV = nullptr; // __wasm_lpad_context
105
106 // Field addresses of struct _Unwind_LandingPadContext
107 Value *LPadIndexField = nullptr; // lpad_index field
108 Value *LSDAField = nullptr; // lsda field
109 Value *SelectorField = nullptr; // selector
110
111 Function *ThrowF = nullptr; // wasm.throw() intrinsic
112 Function *LPadIndexF = nullptr; // wasm.landingpad.index() intrinsic
113 Function *LSDAF = nullptr; // wasm.lsda() intrinsic
114 Function *GetExnF = nullptr; // wasm.get.exception() intrinsic
115 Function *CatchF = nullptr; // wasm.catch() intrinsic
116 Function *GetSelectorF = nullptr; // wasm.get.ehselector() intrinsic
117 FunctionCallee CallPersonalityF =
118 nullptr; // _Unwind_CallPersonality() wrapper
119
120 bool prepareEHPads(Function &F);
121 bool prepareThrows(Function &F);
122
123 bool IsEHPadFunctionsSetUp = false;
124 void setupEHPadFunctions(Function &F);
125 void prepareEHPad(BasicBlock *BB, bool NeedPersonality, bool NeedLSDA = false,
126 unsigned Index = 0);
127
128 public:
129 static char ID; // Pass identification, replacement for typeid
130
WasmEHPrepare()131 WasmEHPrepare() : FunctionPass(ID) {}
132 void getAnalysisUsage(AnalysisUsage &AU) const override;
133 bool doInitialization(Module &M) override;
134 bool runOnFunction(Function &F) override;
135
getPassName() const136 StringRef getPassName() const override {
137 return "WebAssembly Exception handling preparation";
138 }
139 };
140 } // end anonymous namespace
141
142 char WasmEHPrepare::ID = 0;
143 INITIALIZE_PASS_BEGIN(WasmEHPrepare, DEBUG_TYPE,
144 "Prepare WebAssembly exceptions", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)145 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
146 INITIALIZE_PASS_END(WasmEHPrepare, DEBUG_TYPE, "Prepare WebAssembly exceptions",
147 false, false)
148
149 FunctionPass *llvm::createWasmEHPass() { return new WasmEHPrepare(); }
150
getAnalysisUsage(AnalysisUsage & AU) const151 void WasmEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {
152 AU.addRequired<DominatorTreeWrapperPass>();
153 }
154
doInitialization(Module & M)155 bool WasmEHPrepare::doInitialization(Module &M) {
156 IRBuilder<> IRB(M.getContext());
157 LPadContextTy = StructType::get(IRB.getInt32Ty(), // lpad_index
158 IRB.getInt8PtrTy(), // lsda
159 IRB.getInt32Ty() // selector
160 );
161 return false;
162 }
163
164 // Erase the specified BBs if the BB does not have any remaining predecessors,
165 // and also all its dead children.
166 template <typename Container>
eraseDeadBBsAndChildren(const Container & BBs,DomTreeUpdater * DTU)167 static void eraseDeadBBsAndChildren(const Container &BBs, DomTreeUpdater *DTU) {
168 SmallVector<BasicBlock *, 8> WL(BBs.begin(), BBs.end());
169 while (!WL.empty()) {
170 auto *BB = WL.pop_back_val();
171 if (!pred_empty(BB))
172 continue;
173 WL.append(succ_begin(BB), succ_end(BB));
174 DeleteDeadBlock(BB, DTU);
175 }
176 }
177
runOnFunction(Function & F)178 bool WasmEHPrepare::runOnFunction(Function &F) {
179 IsEHPadFunctionsSetUp = false;
180 bool Changed = false;
181 Changed |= prepareThrows(F);
182 Changed |= prepareEHPads(F);
183 return Changed;
184 }
185
prepareThrows(Function & F)186 bool WasmEHPrepare::prepareThrows(Function &F) {
187 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
188 DomTreeUpdater DTU(&DT, /*PostDominatorTree*/ nullptr,
189 DomTreeUpdater::UpdateStrategy::Eager);
190 Module &M = *F.getParent();
191 IRBuilder<> IRB(F.getContext());
192 bool Changed = false;
193
194 // wasm.throw() intinsic, which will be lowered to wasm 'throw' instruction.
195 ThrowF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_throw);
196 // Insert an unreachable instruction after a call to @llvm.wasm.throw and
197 // delete all following instructions within the BB, and delete all the dead
198 // children of the BB as well.
199 for (User *U : ThrowF->users()) {
200 // A call to @llvm.wasm.throw() is only generated from __cxa_throw()
201 // builtin call within libcxxabi, and cannot be an InvokeInst.
202 auto *ThrowI = cast<CallInst>(U);
203 if (ThrowI->getFunction() != &F)
204 continue;
205 Changed = true;
206 auto *BB = ThrowI->getParent();
207 SmallVector<BasicBlock *, 4> Succs(successors(BB));
208 auto &InstList = BB->getInstList();
209 InstList.erase(std::next(BasicBlock::iterator(ThrowI)), InstList.end());
210 IRB.SetInsertPoint(BB);
211 IRB.CreateUnreachable();
212 eraseDeadBBsAndChildren(Succs, &DTU);
213 }
214
215 return Changed;
216 }
217
prepareEHPads(Function & F)218 bool WasmEHPrepare::prepareEHPads(Function &F) {
219 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
220 bool Changed = false;
221
222 // There are two things to decide: whether we need a personality function call
223 // and whether we need a `wasm.lsda()` call and its store.
224 //
225 // For the personality function call, catchpads with `catch (...)` and
226 // cleanuppads don't need it, because exceptions are always caught. Others all
227 // need it.
228 //
229 // For `wasm.lsda()` and its store, in order to minimize the number of them,
230 // we need a way to figure out whether we have encountered `wasm.lsda()` call
231 // in any of EH pads that dominates the current EH pad. To figure that out, we
232 // now visit EH pads in BFS order in the dominator tree so that we visit
233 // parent BBs first before visiting its child BBs in the domtree.
234 //
235 // We keep a set named `ExecutedLSDA`, which basically means "Do we have
236 // `wasm.lsda() either in the current EH pad or any of its parent EH pads in
237 // the dominator tree?". This is to prevent scanning the domtree up to the
238 // root every time we examine an EH pad, in the worst case: each EH pad only
239 // needs to check its immediate parent EH pad.
240 //
241 // - If any of its parent EH pads in the domtree has `wasm.lsda`, this means
242 // we don't need `wasm.lsda()` in the current EH pad. We also insert the
243 // current EH pad in `ExecutedLSDA` set.
244 // - If none of its parent EH pad has `wasm.lsda()`,
245 // - If the current EH pad is a `catch (...)` or a cleanuppad, done.
246 // - If the current EH pad is neither a `catch (...)` nor a cleanuppad,
247 // add `wasm.lsda()` and the store in the current EH pad, and add the
248 // current EH pad to `ExecutedLSDA` set.
249 //
250 // TODO Can we not store LSDA address in user function but make libcxxabi
251 // compute it?
252 DenseSet<Value *> ExecutedLSDA;
253 unsigned Index = 0;
254 for (auto DomNode : breadth_first(&DT)) {
255 auto *BB = DomNode->getBlock();
256 auto *Pad = BB->getFirstNonPHI();
257 if (!Pad || (!isa<CatchPadInst>(Pad) && !isa<CleanupPadInst>(Pad)))
258 continue;
259 Changed = true;
260
261 Value *ParentPad = nullptr;
262 if (CatchPadInst *CPI = dyn_cast<CatchPadInst>(Pad)) {
263 ParentPad = CPI->getCatchSwitch()->getParentPad();
264 if (ExecutedLSDA.count(ParentPad)) {
265 ExecutedLSDA.insert(CPI);
266 // We insert its associated catchswitch too, because
267 // FuncletPadInst::getParentPad() returns a CatchSwitchInst if the child
268 // FuncletPadInst is a CleanupPadInst.
269 ExecutedLSDA.insert(CPI->getCatchSwitch());
270 }
271 } else { // CleanupPadInst
272 ParentPad = cast<CleanupPadInst>(Pad)->getParentPad();
273 if (ExecutedLSDA.count(ParentPad))
274 ExecutedLSDA.insert(Pad);
275 }
276
277 if (CatchPadInst *CPI = dyn_cast<CatchPadInst>(Pad)) {
278 if (CPI->getNumArgOperands() == 1 &&
279 cast<Constant>(CPI->getArgOperand(0))->isNullValue())
280 // In case of a single catch (...), we need neither personality call nor
281 // wasm.lsda() call
282 prepareEHPad(BB, false);
283 else {
284 if (ExecutedLSDA.count(CPI))
285 // catch (type), but one of parents already has wasm.lsda() call
286 prepareEHPad(BB, true, false, Index++);
287 else {
288 // catch (type), and none of parents has wasm.lsda() call. We have to
289 // add the call in this EH pad, and record this EH pad in
290 // ExecutedLSDA.
291 ExecutedLSDA.insert(CPI);
292 ExecutedLSDA.insert(CPI->getCatchSwitch());
293 prepareEHPad(BB, true, true, Index++);
294 }
295 }
296 } else if (isa<CleanupPadInst>(Pad)) {
297 // Cleanup pads need neither personality call nor wasm.lsda() call
298 prepareEHPad(BB, false);
299 }
300 }
301
302 return Changed;
303 }
304
setupEHPadFunctions(Function & F)305 void WasmEHPrepare::setupEHPadFunctions(Function &F) {
306 Module &M = *F.getParent();
307 IRBuilder<> IRB(F.getContext());
308 assert(F.hasPersonalityFn() && "Personality function not found");
309
310 // __wasm_lpad_context global variable
311 LPadContextGV = cast<GlobalVariable>(
312 M.getOrInsertGlobal("__wasm_lpad_context", LPadContextTy));
313 LPadIndexField = IRB.CreateConstGEP2_32(LPadContextTy, LPadContextGV, 0, 0,
314 "lpad_index_gep");
315 LSDAField =
316 IRB.CreateConstGEP2_32(LPadContextTy, LPadContextGV, 0, 1, "lsda_gep");
317 SelectorField = IRB.CreateConstGEP2_32(LPadContextTy, LPadContextGV, 0, 2,
318 "selector_gep");
319
320 // wasm.landingpad.index() intrinsic, which is to specify landingpad index
321 LPadIndexF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_landingpad_index);
322 // wasm.lsda() intrinsic. Returns the address of LSDA table for the current
323 // function.
324 LSDAF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_lsda);
325 // wasm.get.exception() and wasm.get.ehselector() intrinsics. Calls to these
326 // are generated in clang.
327 GetExnF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_get_exception);
328 GetSelectorF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_get_ehselector);
329
330 // wasm.catch() will be lowered down to wasm 'catch' instruction in
331 // instruction selection.
332 CatchF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_catch);
333
334 // _Unwind_CallPersonality() wrapper function, which calls the personality
335 CallPersonalityF = M.getOrInsertFunction(
336 "_Unwind_CallPersonality", IRB.getInt32Ty(), IRB.getInt8PtrTy());
337 if (Function *F = dyn_cast<Function>(CallPersonalityF.getCallee()))
338 F->setDoesNotThrow();
339 }
340
341 // Prepare an EH pad for Wasm EH handling. If NeedPersonality is false, Index is
342 // ignored.
prepareEHPad(BasicBlock * BB,bool NeedPersonality,bool NeedLSDA,unsigned Index)343 void WasmEHPrepare::prepareEHPad(BasicBlock *BB, bool NeedPersonality,
344 bool NeedLSDA, unsigned Index) {
345 if (!IsEHPadFunctionsSetUp) {
346 IsEHPadFunctionsSetUp = true;
347 setupEHPadFunctions(*BB->getParent());
348 }
349 assert(BB->isEHPad() && "BB is not an EHPad!");
350 IRBuilder<> IRB(BB->getContext());
351 IRB.SetInsertPoint(&*BB->getFirstInsertionPt());
352
353 auto *FPI = cast<FuncletPadInst>(BB->getFirstNonPHI());
354 Instruction *GetExnCI = nullptr, *GetSelectorCI = nullptr;
355 for (auto &U : FPI->uses()) {
356 if (auto *CI = dyn_cast<CallInst>(U.getUser())) {
357 if (CI->getCalledOperand() == GetExnF)
358 GetExnCI = CI;
359 if (CI->getCalledOperand() == GetSelectorF)
360 GetSelectorCI = CI;
361 }
362 }
363
364 // Cleanup pads w/o __clang_call_terminate call do not have any of
365 // wasm.get.exception() or wasm.get.ehselector() calls. We need to do nothing.
366 if (!GetExnCI) {
367 assert(!GetSelectorCI &&
368 "wasm.get.ehselector() cannot exist w/o wasm.get.exception()");
369 return;
370 }
371
372 // Replace wasm.get.exception intrinsic with wasm.catch intrinsic, which will
373 // be lowered to wasm 'catch' instruction. We do this mainly because
374 // instruction selection cannot handle wasm.get.exception intrinsic's token
375 // argument.
376 Instruction *CatchCI =
377 IRB.CreateCall(CatchF, {IRB.getInt32(WebAssembly::CPP_EXCEPTION)}, "exn");
378 GetExnCI->replaceAllUsesWith(CatchCI);
379 GetExnCI->eraseFromParent();
380
381 // In case it is a catchpad with single catch (...) or a cleanuppad, we don't
382 // need to call personality function because we don't need a selector.
383 if (!NeedPersonality) {
384 if (GetSelectorCI) {
385 assert(GetSelectorCI->use_empty() &&
386 "wasm.get.ehselector() still has uses!");
387 GetSelectorCI->eraseFromParent();
388 }
389 return;
390 }
391 IRB.SetInsertPoint(CatchCI->getNextNode());
392
393 // This is to create a map of <landingpad EH label, landingpad index> in
394 // SelectionDAGISel, which is to be used in EHStreamer to emit LSDA tables.
395 // Pseudocode: wasm.landingpad.index(Index);
396 IRB.CreateCall(LPadIndexF, {FPI, IRB.getInt32(Index)});
397
398 // Pseudocode: __wasm_lpad_context.lpad_index = index;
399 IRB.CreateStore(IRB.getInt32(Index), LPadIndexField);
400
401 auto *CPI = cast<CatchPadInst>(FPI);
402 if (NeedLSDA)
403 // Pseudocode: __wasm_lpad_context.lsda = wasm.lsda();
404 IRB.CreateStore(IRB.CreateCall(LSDAF), LSDAField);
405
406 // Pseudocode: _Unwind_CallPersonality(exn);
407 CallInst *PersCI = IRB.CreateCall(CallPersonalityF, CatchCI,
408 OperandBundleDef("funclet", CPI));
409 PersCI->setDoesNotThrow();
410
411 // Pseudocode: int selector = __wasm.landingpad_context.selector;
412 Instruction *Selector =
413 IRB.CreateLoad(IRB.getInt32Ty(), SelectorField, "selector");
414
415 // Replace the return value from wasm.get.ehselector() with the selector value
416 // loaded from __wasm_lpad_context.selector.
417 assert(GetSelectorCI && "wasm.get.ehselector() call does not exist");
418 GetSelectorCI->replaceAllUsesWith(Selector);
419 GetSelectorCI->eraseFromParent();
420 }
421
calculateWasmEHInfo(const Function * F,WasmEHFuncInfo & EHInfo)422 void llvm::calculateWasmEHInfo(const Function *F, WasmEHFuncInfo &EHInfo) {
423 // If an exception is not caught by a catchpad (i.e., it is a foreign
424 // exception), it will unwind to its parent catchswitch's unwind destination.
425 // We don't record an unwind destination for cleanuppads because every
426 // exception should be caught by it.
427 for (const auto &BB : *F) {
428 if (!BB.isEHPad())
429 continue;
430 const Instruction *Pad = BB.getFirstNonPHI();
431
432 if (const auto *CatchPad = dyn_cast<CatchPadInst>(Pad)) {
433 const auto *UnwindBB = CatchPad->getCatchSwitch()->getUnwindDest();
434 if (!UnwindBB)
435 continue;
436 const Instruction *UnwindPad = UnwindBB->getFirstNonPHI();
437 if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(UnwindPad))
438 // Currently there should be only one handler per a catchswitch.
439 EHInfo.setEHPadUnwindDest(&BB, *CatchSwitch->handlers().begin());
440 else // cleanuppad
441 EHInfo.setEHPadUnwindDest(&BB, UnwindBB);
442 }
443 }
444 }
445