xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/WasmEHPrepare.cpp (revision 7877fdebeeb35fad1cbbafce22598b1bdf97c786)
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.extract.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 *ExtractExnF = nullptr;  // wasm.extract.exception() 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   void prepareTerminateCleanupPad(BasicBlock *BB);
128 
129 public:
130   static char ID; // Pass identification, replacement for typeid
131 
132   WasmEHPrepare() : FunctionPass(ID) {}
133   void getAnalysisUsage(AnalysisUsage &AU) const override;
134   bool doInitialization(Module &M) override;
135   bool runOnFunction(Function &F) override;
136 
137   StringRef getPassName() const override {
138     return "WebAssembly Exception handling preparation";
139   }
140 };
141 } // end anonymous namespace
142 
143 char WasmEHPrepare::ID = 0;
144 INITIALIZE_PASS_BEGIN(WasmEHPrepare, DEBUG_TYPE,
145                       "Prepare WebAssembly exceptions", false, false)
146 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
147 INITIALIZE_PASS_END(WasmEHPrepare, DEBUG_TYPE, "Prepare WebAssembly exceptions",
148                     false, false)
149 
150 FunctionPass *llvm::createWasmEHPass() { return new WasmEHPrepare(); }
151 
152 void WasmEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {
153   AU.addRequired<DominatorTreeWrapperPass>();
154 }
155 
156 bool WasmEHPrepare::doInitialization(Module &M) {
157   IRBuilder<> IRB(M.getContext());
158   LPadContextTy = StructType::get(IRB.getInt32Ty(),   // lpad_index
159                                   IRB.getInt8PtrTy(), // lsda
160                                   IRB.getInt32Ty()    // selector
161   );
162   return false;
163 }
164 
165 // Erase the specified BBs if the BB does not have any remaining predecessors,
166 // and also all its dead children.
167 template <typename Container>
168 static void eraseDeadBBsAndChildren(const Container &BBs, DomTreeUpdater *DTU) {
169   SmallVector<BasicBlock *, 8> WL(BBs.begin(), BBs.end());
170   while (!WL.empty()) {
171     auto *BB = WL.pop_back_val();
172     if (pred_begin(BB) != pred_end(BB))
173       continue;
174     WL.append(succ_begin(BB), succ_end(BB));
175     DeleteDeadBlock(BB, DTU);
176   }
177 }
178 
179 bool WasmEHPrepare::runOnFunction(Function &F) {
180   IsEHPadFunctionsSetUp = false;
181   bool Changed = false;
182   Changed |= prepareThrows(F);
183   Changed |= prepareEHPads(F);
184   return Changed;
185 }
186 
187 bool WasmEHPrepare::prepareThrows(Function &F) {
188   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
189   DomTreeUpdater DTU(&DT, /*PostDominatorTree*/ nullptr,
190                      DomTreeUpdater::UpdateStrategy::Eager);
191   Module &M = *F.getParent();
192   IRBuilder<> IRB(F.getContext());
193   bool Changed = false;
194 
195   // wasm.throw() intinsic, which will be lowered to wasm 'throw' instruction.
196   ThrowF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_throw);
197   // Insert an unreachable instruction after a call to @llvm.wasm.throw and
198   // delete all following instructions within the BB, and delete all the dead
199   // children of the BB as well.
200   for (User *U : ThrowF->users()) {
201     // A call to @llvm.wasm.throw() is only generated from __cxa_throw()
202     // builtin call within libcxxabi, and cannot be an InvokeInst.
203     auto *ThrowI = cast<CallInst>(U);
204     if (ThrowI->getFunction() != &F)
205       continue;
206     Changed = true;
207     auto *BB = ThrowI->getParent();
208     SmallVector<BasicBlock *, 4> Succs(succ_begin(BB), succ_end(BB));
209     auto &InstList = BB->getInstList();
210     InstList.erase(std::next(BasicBlock::iterator(ThrowI)), InstList.end());
211     IRB.SetInsertPoint(BB);
212     IRB.CreateUnreachable();
213     eraseDeadBBsAndChildren(Succs, &DTU);
214   }
215 
216   return Changed;
217 }
218 
219 bool WasmEHPrepare::prepareEHPads(Function &F) {
220   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
221   bool Changed = false;
222 
223   // There are two things to decide: whether we need a personality function call
224   // and whether we need a `wasm.lsda()` call and its store.
225   //
226   // For the personality function call, catchpads with `catch (...)` and
227   // cleanuppads don't need it, because exceptions are always caught. Others all
228   // need it.
229   //
230   // For `wasm.lsda()` and its store, in order to minimize the number of them,
231   // we need a way to figure out whether we have encountered `wasm.lsda()` call
232   // in any of EH pads that dominates the current EH pad. To figure that out, we
233   // now visit EH pads in BFS order in the dominator tree so that we visit
234   // parent BBs first before visiting its child BBs in the domtree.
235   //
236   // We keep a set named `ExecutedLSDA`, which basically means "Do we have
237   // `wasm.lsda() either in the current EH pad or any of its parent EH pads in
238   // the dominator tree?". This is to prevent scanning the domtree up to the
239   // root every time we examine an EH pad, in the worst case: each EH pad only
240   // needs to check its immediate parent EH pad.
241   //
242   // - If any of its parent EH pads in the domtree has `wasm.lsda`, this means
243   //   we don't need `wasm.lsda()` in the current EH pad. We also insert the
244   //   current EH pad in `ExecutedLSDA` set.
245   // - If none of its parent EH pad has `wasm.lsda()`,
246   //   - If the current EH pad is a `catch (...)` or a cleanuppad, done.
247   //   - If the current EH pad is neither a `catch (...)` nor a cleanuppad,
248   //     add `wasm.lsda()` and the store in the current EH pad, and add the
249   //     current EH pad to `ExecutedLSDA` set.
250   //
251   // TODO Can we not store LSDA address in user function but make libcxxabi
252   // compute it?
253   DenseSet<Value *> ExecutedLSDA;
254   unsigned Index = 0;
255   for (auto DomNode : breadth_first(&DT)) {
256     auto *BB = DomNode->getBlock();
257     auto *Pad = BB->getFirstNonPHI();
258     if (!Pad || (!isa<CatchPadInst>(Pad) && !isa<CleanupPadInst>(Pad)))
259       continue;
260     Changed = true;
261 
262     Value *ParentPad = nullptr;
263     if (CatchPadInst *CPI = dyn_cast<CatchPadInst>(Pad)) {
264       ParentPad = CPI->getCatchSwitch()->getParentPad();
265       if (ExecutedLSDA.count(ParentPad)) {
266         ExecutedLSDA.insert(CPI);
267         // We insert its associated catchswitch too, because
268         // FuncletPadInst::getParentPad() returns a CatchSwitchInst if the child
269         // FuncletPadInst is a CleanupPadInst.
270         ExecutedLSDA.insert(CPI->getCatchSwitch());
271       }
272     } else { // CleanupPadInst
273       ParentPad = cast<CleanupPadInst>(Pad)->getParentPad();
274       if (ExecutedLSDA.count(ParentPad))
275         ExecutedLSDA.insert(Pad);
276     }
277 
278     if (CatchPadInst *CPI = dyn_cast<CatchPadInst>(Pad)) {
279       if (CPI->getNumArgOperands() == 1 &&
280           cast<Constant>(CPI->getArgOperand(0))->isNullValue())
281         // In case of a single catch (...), we need neither personality call nor
282         // wasm.lsda() call
283         prepareEHPad(BB, false);
284       else {
285         if (ExecutedLSDA.count(CPI))
286           // catch (type), but one of parents already has wasm.lsda() call
287           prepareEHPad(BB, true, false, Index++);
288         else {
289           // catch (type), and none of parents has wasm.lsda() call. We have to
290           // add the call in this EH pad, and record this EH pad in
291           // ExecutedLSDA.
292           ExecutedLSDA.insert(CPI);
293           ExecutedLSDA.insert(CPI->getCatchSwitch());
294           prepareEHPad(BB, true, true, Index++);
295         }
296       }
297     } else if (isa<CleanupPadInst>(Pad)) {
298       // Cleanup pads need neither personality call nor wasm.lsda() call
299       prepareEHPad(BB, false);
300     }
301   }
302 
303   return Changed;
304 }
305 
306 void WasmEHPrepare::setupEHPadFunctions(Function &F) {
307   Module &M = *F.getParent();
308   IRBuilder<> IRB(F.getContext());
309   assert(F.hasPersonalityFn() && "Personality function not found");
310 
311   // __wasm_lpad_context global variable
312   LPadContextGV = cast<GlobalVariable>(
313       M.getOrInsertGlobal("__wasm_lpad_context", LPadContextTy));
314   LPadIndexField = IRB.CreateConstGEP2_32(LPadContextTy, LPadContextGV, 0, 0,
315                                           "lpad_index_gep");
316   LSDAField =
317       IRB.CreateConstGEP2_32(LPadContextTy, LPadContextGV, 0, 1, "lsda_gep");
318   SelectorField = IRB.CreateConstGEP2_32(LPadContextTy, LPadContextGV, 0, 2,
319                                          "selector_gep");
320 
321   // wasm.landingpad.index() intrinsic, which is to specify landingpad index
322   LPadIndexF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_landingpad_index);
323   // wasm.lsda() intrinsic. Returns the address of LSDA table for the current
324   // function.
325   LSDAF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_lsda);
326   // wasm.get.exception() and wasm.get.ehselector() intrinsics. Calls to these
327   // are generated in clang.
328   GetExnF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_get_exception);
329   GetSelectorF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_get_ehselector);
330 
331   // wasm.extract.exception() is the same as wasm.get.exception() but it does
332   // not take a token argument. This will be lowered down to EXTRACT_EXCEPTION
333   // pseudo instruction in instruction selection, which will be expanded using
334   // 'br_on_exn' instruction later.
335   ExtractExnF =
336       Intrinsic::getDeclaration(&M, Intrinsic::wasm_extract_exception);
337 
338   // _Unwind_CallPersonality() wrapper function, which calls the personality
339   CallPersonalityF = M.getOrInsertFunction(
340       "_Unwind_CallPersonality", IRB.getInt32Ty(), IRB.getInt8PtrTy());
341   if (Function *F = dyn_cast<Function>(CallPersonalityF.getCallee()))
342     F->setDoesNotThrow();
343 }
344 
345 // Prepare an EH pad for Wasm EH handling. If NeedPersonality is false, Index is
346 // ignored.
347 void WasmEHPrepare::prepareEHPad(BasicBlock *BB, bool NeedPersonality,
348                                  bool NeedLSDA, unsigned Index) {
349   if (!IsEHPadFunctionsSetUp) {
350     IsEHPadFunctionsSetUp = true;
351     setupEHPadFunctions(*BB->getParent());
352   }
353   assert(BB->isEHPad() && "BB is not an EHPad!");
354   IRBuilder<> IRB(BB->getContext());
355   IRB.SetInsertPoint(&*BB->getFirstInsertionPt());
356 
357   auto *FPI = cast<FuncletPadInst>(BB->getFirstNonPHI());
358   Instruction *GetExnCI = nullptr, *GetSelectorCI = nullptr;
359   for (auto &U : FPI->uses()) {
360     if (auto *CI = dyn_cast<CallInst>(U.getUser())) {
361       if (CI->getCalledOperand() == GetExnF)
362         GetExnCI = CI;
363       if (CI->getCalledOperand() == GetSelectorF)
364         GetSelectorCI = CI;
365     }
366   }
367 
368   // Cleanup pads w/o __clang_call_terminate call do not have any of
369   // wasm.get.exception() or wasm.get.ehselector() calls. We need to do nothing.
370   if (!GetExnCI) {
371     assert(!GetSelectorCI &&
372            "wasm.get.ehselector() cannot exist w/o wasm.get.exception()");
373     return;
374   }
375 
376   Instruction *ExtractExnCI = IRB.CreateCall(ExtractExnF, {}, "exn");
377   GetExnCI->replaceAllUsesWith(ExtractExnCI);
378   GetExnCI->eraseFromParent();
379 
380   // In case it is a catchpad with single catch (...) or a cleanuppad, we don't
381   // need to call personality function because we don't need a selector.
382   if (!NeedPersonality) {
383     if (GetSelectorCI) {
384       assert(GetSelectorCI->use_empty() &&
385              "wasm.get.ehselector() still has uses!");
386       GetSelectorCI->eraseFromParent();
387     }
388     return;
389   }
390   IRB.SetInsertPoint(ExtractExnCI->getNextNode());
391 
392   // This is to create a map of <landingpad EH label, landingpad index> in
393   // SelectionDAGISel, which is to be used in EHStreamer to emit LSDA tables.
394   // Pseudocode: wasm.landingpad.index(Index);
395   IRB.CreateCall(LPadIndexF, {FPI, IRB.getInt32(Index)});
396 
397   // Pseudocode: __wasm_lpad_context.lpad_index = index;
398   IRB.CreateStore(IRB.getInt32(Index), LPadIndexField);
399 
400   auto *CPI = cast<CatchPadInst>(FPI);
401   if (NeedLSDA)
402     // Pseudocode: __wasm_lpad_context.lsda = wasm.lsda();
403     IRB.CreateStore(IRB.CreateCall(LSDAF), LSDAField);
404 
405   // Pseudocode: _Unwind_CallPersonality(exn);
406   CallInst *PersCI = IRB.CreateCall(CallPersonalityF, ExtractExnCI,
407                                     OperandBundleDef("funclet", CPI));
408   PersCI->setDoesNotThrow();
409 
410   // Pseudocode: int selector = __wasm.landingpad_context.selector;
411   Instruction *Selector =
412       IRB.CreateLoad(IRB.getInt32Ty(), SelectorField, "selector");
413 
414   // Replace the return value from wasm.get.ehselector() with the selector value
415   // loaded from __wasm_lpad_context.selector.
416   assert(GetSelectorCI && "wasm.get.ehselector() call does not exist");
417   GetSelectorCI->replaceAllUsesWith(Selector);
418   GetSelectorCI->eraseFromParent();
419 }
420 
421 void llvm::calculateWasmEHInfo(const Function *F, WasmEHFuncInfo &EHInfo) {
422   // If an exception is not caught by a catchpad (i.e., it is a foreign
423   // exception), it will unwind to its parent catchswitch's unwind destination.
424   // We don't record an unwind destination for cleanuppads because every
425   // exception should be caught by it.
426   for (const auto &BB : *F) {
427     if (!BB.isEHPad())
428       continue;
429     const Instruction *Pad = BB.getFirstNonPHI();
430 
431     if (const auto *CatchPad = dyn_cast<CatchPadInst>(Pad)) {
432       const auto *UnwindBB = CatchPad->getCatchSwitch()->getUnwindDest();
433       if (!UnwindBB)
434         continue;
435       const Instruction *UnwindPad = UnwindBB->getFirstNonPHI();
436       if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(UnwindPad))
437         // Currently there should be only one handler per a catchswitch.
438         EHInfo.setEHPadUnwindDest(&BB, *CatchSwitch->handlers().begin());
439       else // cleanuppad
440         EHInfo.setEHPadUnwindDest(&BB, UnwindBB);
441     }
442   }
443 }
444