LLVM  8.0.1
WasmEHPrepare.cpp
Go to the documentation of this file.
1 //===-- WasmEHPrepare - Prepare excepton handling for WebAssembly --------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This transformation is designed for use by code generators which use
11 // WebAssembly exception handling scheme.
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(0); // 0 is a tag for C++
27 // wasm.landingpad.index(index);
28 // // Only add below in case it's not a single catch (...)
29 // __wasm_lpad_context.lpad_index = index;
30 // __wasm_lpad_context.lsda = wasm.lsda();
31 // _Unwind_CallPersonality(exn);
32 // int selector = __wasm.landingpad_context.selector;
33 // ...
34 //
35 // Also, does the following for a cleanuppad block with a call to
36 // __clang_call_terminate():
37 // - Before:
38 // cleanuppad ...
39 // exn = wasm.get.exception();
40 // __clang_call_terminate(exn);
41 //
42 // - After:
43 // cleanuppad ...
44 // exn = wasm.catch(0); // 0 is a tag for C++
45 // __clang_call_terminate(exn);
46 //
47 //
48 // * Background: WebAssembly EH instructions
49 // WebAssembly's try and catch instructions are structured as follows:
50 // try
51 // instruction*
52 // catch (C++ tag)
53 // instruction*
54 // ...
55 // catch_all
56 // instruction*
57 // try_end
58 //
59 // A catch instruction in WebAssembly does not correspond to a C++ catch clause.
60 // In WebAssembly, there is a single catch instruction for all C++ exceptions.
61 // There can be more catch instructions for exceptions in other languages, but
62 // they are not generated for now. catch_all catches all exceptions including
63 // foreign exceptions (e.g. JavaScript). We turn catchpads into catch (C++ tag)
64 // and cleanuppads into catch_all, with one exception: cleanuppad with a call to
65 // __clang_call_terminate should be both in catch (C++ tag) and catch_all.
66 //
67 //
68 // * Background: Direct personality function call
69 // In WebAssembly EH, the VM is responsible for unwinding the stack once an
70 // exception is thrown. After the stack is unwound, the control flow is
71 // transfered to WebAssembly 'catch' instruction, which returns a caught
72 // exception object.
73 //
74 // Unwinding the stack is not done by libunwind but the VM, so the personality
75 // function in libcxxabi cannot be called from libunwind during the unwinding
76 // process. So after a catch instruction, we insert a call to a wrapper function
77 // in libunwind that in turn calls the real personality function.
78 //
79 // In Itanium EH, if the personality function decides there is no matching catch
80 // clause in a call frame and no cleanup action to perform, the unwinder doesn't
81 // stop there and continues unwinding. But in Wasm EH, the unwinder stops at
82 // every call frame with a catch intruction, after which the personality
83 // function is called from the compiler-generated user code here.
84 //
85 // In libunwind, we have this struct that serves as a communincation channel
86 // between the compiler-generated user code and the personality function in
87 // libcxxabi.
88 //
89 // struct _Unwind_LandingPadContext {
90 // uintptr_t lpad_index;
91 // uintptr_t lsda;
92 // uintptr_t selector;
93 // };
94 // struct _Unwind_LandingPadContext __wasm_lpad_context = ...;
95 //
96 // And this wrapper in libunwind calls the personality function.
97 //
98 // _Unwind_Reason_Code _Unwind_CallPersonality(void *exception_ptr) {
99 // struct _Unwind_Exception *exception_obj =
100 // (struct _Unwind_Exception *)exception_ptr;
101 // _Unwind_Reason_Code ret = __gxx_personality_v0(
102 // 1, _UA_CLEANUP_PHASE, exception_obj->exception_class, exception_obj,
103 // (struct _Unwind_Context *)__wasm_lpad_context);
104 // return ret;
105 // }
106 //
107 // We pass a landing pad index, and the address of LSDA for the current function
108 // to the wrapper function _Unwind_CallPersonality in libunwind, and we retrieve
109 // the selector after it returns.
110 //
111 //===----------------------------------------------------------------------===//
112 
113 #include "llvm/ADT/SetVector.h"
114 #include "llvm/ADT/Statistic.h"
115 #include "llvm/ADT/Triple.h"
116 #include "llvm/CodeGen/Passes.h"
120 #include "llvm/IR/Dominators.h"
121 #include "llvm/IR/IRBuilder.h"
122 #include "llvm/IR/Intrinsics.h"
123 #include "llvm/Pass.h"
125 
126 using namespace llvm;
127 
128 #define DEBUG_TYPE "wasmehprepare"
129 
130 namespace {
131 class WasmEHPrepare : public FunctionPass {
132  Type *LPadContextTy = nullptr; // type of 'struct _Unwind_LandingPadContext'
133  GlobalVariable *LPadContextGV = nullptr; // __wasm_lpad_context
134 
135  // Field addresses of struct _Unwind_LandingPadContext
136  Value *LPadIndexField = nullptr; // lpad_index field
137  Value *LSDAField = nullptr; // lsda field
138  Value *SelectorField = nullptr; // selector
139 
140  Function *ThrowF = nullptr; // wasm.throw() intrinsic
141  Function *CatchF = nullptr; // wasm.catch.extract() intrinsic
142  Function *LPadIndexF = nullptr; // wasm.landingpad.index() intrinsic
143  Function *LSDAF = nullptr; // wasm.lsda() intrinsic
144  Function *GetExnF = nullptr; // wasm.get.exception() intrinsic
145  Function *GetSelectorF = nullptr; // wasm.get.ehselector() intrinsic
146  Function *CallPersonalityF = nullptr; // _Unwind_CallPersonality() wrapper
147  Function *ClangCallTermF = nullptr; // __clang_call_terminate() function
148 
149  bool prepareEHPads(Function &F);
150  bool prepareThrows(Function &F);
151 
152  void prepareEHPad(BasicBlock *BB, unsigned Index);
153  void prepareTerminateCleanupPad(BasicBlock *BB);
154 
155 public:
156  static char ID; // Pass identification, replacement for typeid
157 
158  WasmEHPrepare() : FunctionPass(ID) {}
159 
160  bool doInitialization(Module &M) override;
161  bool runOnFunction(Function &F) override;
162 
163  StringRef getPassName() const override {
164  return "WebAssembly Exception handling preparation";
165  }
166 };
167 } // end anonymous namespace
168 
169 char WasmEHPrepare::ID = 0;
170 INITIALIZE_PASS(WasmEHPrepare, DEBUG_TYPE, "Prepare WebAssembly exceptions",
171  false, false)
172 
173 FunctionPass *llvm::createWasmEHPass() { return new WasmEHPrepare(); }
174 
175 bool WasmEHPrepare::doInitialization(Module &M) {
176  IRBuilder<> IRB(M.getContext());
177  LPadContextTy = StructType::get(IRB.getInt32Ty(), // lpad_index
178  IRB.getInt8PtrTy(), // lsda
179  IRB.getInt32Ty() // selector
180  );
181  return false;
182 }
183 
184 // Erase the specified BBs if the BB does not have any remaining predecessors,
185 // and also all its dead children.
186 template <typename Container>
187 static void eraseDeadBBsAndChildren(const Container &BBs) {
188  SmallVector<BasicBlock *, 8> WL(BBs.begin(), BBs.end());
189  while (!WL.empty()) {
190  auto *BB = WL.pop_back_val();
191  if (pred_begin(BB) != pred_end(BB))
192  continue;
193  WL.append(succ_begin(BB), succ_end(BB));
194  DeleteDeadBlock(BB);
195  }
196 }
197 
199  bool Changed = false;
200  Changed |= prepareThrows(F);
201  Changed |= prepareEHPads(F);
202  return Changed;
203 }
204 
205 bool WasmEHPrepare::prepareThrows(Function &F) {
206  Module &M = *F.getParent();
207  IRBuilder<> IRB(F.getContext());
208  bool Changed = false;
209 
210  // wasm.throw() intinsic, which will be lowered to wasm 'throw' instruction.
212 
213  // Insert an unreachable instruction after a call to @llvm.wasm.throw and
214  // delete all following instructions within the BB, and delete all the dead
215  // children of the BB as well.
216  for (User *U : ThrowF->users()) {
217  // A call to @llvm.wasm.throw() is only generated from
218  // __builtin_wasm_throw() builtin call within libcxxabi, and cannot be an
219  // InvokeInst.
220  auto *ThrowI = cast<CallInst>(U);
221  if (ThrowI->getFunction() != &F)
222  continue;
223  Changed = true;
224  auto *BB = ThrowI->getParent();
226  auto &InstList = BB->getInstList();
227  InstList.erase(std::next(BasicBlock::iterator(ThrowI)), InstList.end());
228  IRB.SetInsertPoint(BB);
229  IRB.CreateUnreachable();
231  }
232 
233  return Changed;
234 }
235 
236 bool WasmEHPrepare::prepareEHPads(Function &F) {
237  Module &M = *F.getParent();
238  IRBuilder<> IRB(F.getContext());
239 
241  SmallVector<BasicBlock *, 16> CleanupPads;
242  for (BasicBlock &BB : F) {
243  if (!BB.isEHPad())
244  continue;
245  auto *Pad = BB.getFirstNonPHI();
246  if (isa<CatchPadInst>(Pad))
247  CatchPads.push_back(&BB);
248  else if (isa<CleanupPadInst>(Pad))
249  CleanupPads.push_back(&BB);
250  }
251 
252  if (CatchPads.empty() && CleanupPads.empty())
253  return false;
254  assert(F.hasPersonalityFn() && "Personality function not found");
255 
256  // __wasm_lpad_context global variable
257  LPadContextGV = cast<GlobalVariable>(
258  M.getOrInsertGlobal("__wasm_lpad_context", LPadContextTy));
259  LPadIndexField = IRB.CreateConstGEP2_32(LPadContextTy, LPadContextGV, 0, 0,
260  "lpad_index_gep");
261  LSDAField =
262  IRB.CreateConstGEP2_32(LPadContextTy, LPadContextGV, 0, 1, "lsda_gep");
263  SelectorField = IRB.CreateConstGEP2_32(LPadContextTy, LPadContextGV, 0, 2,
264  "selector_gep");
265 
266  // wasm.catch() intinsic, which will be lowered to wasm 'catch' instruction.
268  // wasm.landingpad.index() intrinsic, which is to specify landingpad index
270  // wasm.lsda() intrinsic. Returns the address of LSDA table for the current
271  // function.
273  // wasm.get.exception() and wasm.get.ehselector() intrinsics. Calls to these
274  // are generated in clang.
277 
278  // _Unwind_CallPersonality() wrapper function, which calls the personality
279  CallPersonalityF = cast<Function>(M.getOrInsertFunction(
280  "_Unwind_CallPersonality", IRB.getInt32Ty(), IRB.getInt8PtrTy()));
281  CallPersonalityF->setDoesNotThrow();
282 
283  // __clang_call_terminate() function, which is inserted by clang in case a
284  // cleanup throws
285  ClangCallTermF = M.getFunction("__clang_call_terminate");
286 
287  unsigned Index = 0;
288  for (auto *BB : CatchPads) {
289  auto *CPI = cast<CatchPadInst>(BB->getFirstNonPHI());
290  // In case of a single catch (...), we don't need to emit LSDA
291  if (CPI->getNumArgOperands() == 1 &&
292  cast<Constant>(CPI->getArgOperand(0))->isNullValue())
293  prepareEHPad(BB, -1);
294  else
295  prepareEHPad(BB, Index++);
296  }
297 
298  if (!ClangCallTermF)
299  return !CatchPads.empty();
300 
301  // Cleanuppads will turn into catch_all later, but cleanuppads with a call to
302  // __clang_call_terminate() is a special case. __clang_call_terminate() takes
303  // an exception object, so we have to duplicate call in both 'catch <C++ tag>'
304  // and 'catch_all' clauses. Here we only insert a call to catch; the
305  // duplication will be done later. In catch_all, the exception object will be
306  // set to null.
307  for (auto *BB : CleanupPads)
308  for (auto &I : *BB)
309  if (auto *CI = dyn_cast<CallInst>(&I))
310  if (CI->getCalledValue() == ClangCallTermF)
311  prepareEHPad(BB, -1);
312 
313  return true;
314 }
315 
316 void WasmEHPrepare::prepareEHPad(BasicBlock *BB, unsigned Index) {
317  assert(BB->isEHPad() && "BB is not an EHPad!");
318  IRBuilder<> IRB(BB->getContext());
319 
320  IRB.SetInsertPoint(&*BB->getFirstInsertionPt());
321  // The argument to wasm.catch() is the tag for C++ exceptions, which we set to
322  // 0 for this module.
323  // Pseudocode: void *exn = wasm.catch(0);
324  Instruction *Exn = IRB.CreateCall(CatchF, IRB.getInt32(0), "exn");
325  // Replace the return value of wasm.get.exception() with the return value from
326  // wasm.catch().
327  auto *FPI = cast<FuncletPadInst>(BB->getFirstNonPHI());
328  Instruction *GetExnCI = nullptr, *GetSelectorCI = nullptr;
329  for (auto &U : FPI->uses()) {
330  if (auto *CI = dyn_cast<CallInst>(U.getUser())) {
331  if (CI->getCalledValue() == GetExnF)
332  GetExnCI = CI;
333  else if (CI->getCalledValue() == GetSelectorF)
334  GetSelectorCI = CI;
335  }
336  }
337 
338  assert(GetExnCI && "wasm.get.exception() call does not exist");
339  GetExnCI->replaceAllUsesWith(Exn);
340  GetExnCI->eraseFromParent();
341 
342  // In case it is a catchpad with single catch (...) or a cleanuppad, we don't
343  // need to call personality function because we don't need a selector.
344  if (FPI->getNumArgOperands() == 0 ||
345  (FPI->getNumArgOperands() == 1 &&
346  cast<Constant>(FPI->getArgOperand(0))->isNullValue())) {
347  if (GetSelectorCI) {
348  assert(GetSelectorCI->use_empty() &&
349  "wasm.get.ehselector() still has uses!");
350  GetSelectorCI->eraseFromParent();
351  }
352  return;
353  }
354  IRB.SetInsertPoint(Exn->getNextNode());
355 
356  // This is to create a map of <landingpad EH label, landingpad index> in
357  // SelectionDAGISel, which is to be used in EHStreamer to emit LSDA tables.
358  // Pseudocode: wasm.landingpad.index(Index);
359  IRB.CreateCall(LPadIndexF, {FPI, IRB.getInt32(Index)});
360 
361  // Pseudocode: __wasm_lpad_context.lpad_index = index;
362  IRB.CreateStore(IRB.getInt32(Index), LPadIndexField);
363 
364  // Store LSDA address only if this catchpad belongs to a top-level
365  // catchswitch. If there is another catchpad that dominates this pad, we don't
366  // need to store LSDA address again, because they are the same throughout the
367  // function and have been already stored before.
368  // TODO Can we not store LSDA address in user function but make libcxxabi
369  // compute it?
370  auto *CPI = cast<CatchPadInst>(FPI);
371  if (isa<ConstantTokenNone>(CPI->getCatchSwitch()->getParentPad()))
372  // Pseudocode: __wasm_lpad_context.lsda = wasm.lsda();
373  IRB.CreateStore(IRB.CreateCall(LSDAF), LSDAField);
374 
375  // Pseudocode: _Unwind_CallPersonality(exn);
376  CallInst *PersCI =
377  IRB.CreateCall(CallPersonalityF, Exn, OperandBundleDef("funclet", CPI));
378  PersCI->setDoesNotThrow();
379 
380  // Pseudocode: int selector = __wasm.landingpad_context.selector;
381  Instruction *Selector = IRB.CreateLoad(SelectorField, "selector");
382 
383  // Replace the return value from wasm.get.ehselector() with the selector value
384  // loaded from __wasm_lpad_context.selector.
385  assert(GetSelectorCI && "wasm.get.ehselector() call does not exist");
386  GetSelectorCI->replaceAllUsesWith(Selector);
387  GetSelectorCI->eraseFromParent();
388 }
389 
391  for (const auto &BB : *F) {
392  if (!BB.isEHPad())
393  continue;
394  const Instruction *Pad = BB.getFirstNonPHI();
395 
396  // If an exception is not caught by a catchpad (i.e., it is a foreign
397  // exception), it will unwind to its parent catchswitch's unwind
398  // destination. We don't record an unwind destination for cleanuppads
399  // because every exception should be caught by it.
400  if (const auto *CatchPad = dyn_cast<CatchPadInst>(Pad)) {
401  const auto *UnwindBB = CatchPad->getCatchSwitch()->getUnwindDest();
402  if (!UnwindBB)
403  continue;
404  const Instruction *UnwindPad = UnwindBB->getFirstNonPHI();
405  if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(UnwindPad))
406  // Currently there should be only one handler per a catchswitch.
407  EHInfo.setEHPadUnwindDest(&BB, *CatchSwitch->handlers().begin());
408  else // cleanuppad
409  EHInfo.setEHPadUnwindDest(&BB, UnwindBB);
410  }
411  }
412 
413  // Record the unwind destination for invoke and cleanupret instructions.
414  for (const auto &BB : *F) {
415  const Instruction *TI = BB.getTerminator();
416  BasicBlock *UnwindBB = nullptr;
417  if (const auto *Invoke = dyn_cast<InvokeInst>(TI))
418  UnwindBB = Invoke->getUnwindDest();
419  else if (const auto *CleanupRet = dyn_cast<CleanupReturnInst>(TI))
420  UnwindBB = CleanupRet->getUnwindDest();
421  if (!UnwindBB)
422  continue;
423  const Instruction *UnwindPad = UnwindBB->getFirstNonPHI();
424  if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(UnwindPad))
425  // Currently there should be only one handler per a catchswitch.
426  EHInfo.setThrowUnwindDest(&BB, *CatchSwitch->handlers().begin());
427  else // cleanuppad
428  EHInfo.setThrowUnwindDest(&BB, UnwindBB);
429  }
430 }
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
This class represents lattice values for constants.
Definition: AllocatorList.h:24
Constant * getOrInsertFunction(StringRef Name, FunctionType *T, AttributeList AttributeList)
Look up the specified function in the module symbol table.
Definition: Module.cpp:144
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
This class represents a function call, abstracting a target machine&#39;s calling convention.
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Delete the specified block, which must have no predecessors.
F(f)
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:269
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:244
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:743
static StructType * get(LLVMContext &Context, ArrayRef< Type *> Elements, bool isPacked=false)
This static method is the primary way to create a literal StructType.
Definition: Type.cpp:342
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
static void eraseDeadBBsAndChildren(const Container &BBs)
FunctionPass * createWasmEHPass()
createWasmEHPass - This pass adapts exception handling code to use WebAssembly&#39;s exception handling s...
Function * getDeclaration(Module *M, ID id, ArrayRef< Type *> Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1020
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:127
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
static bool runOnFunction(Function &F, bool PostInlining)
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:190
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:217
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
void setEHPadUnwindDest(const BasicBlock *BB, const BasicBlock *Dest)
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:193
Iterator for intrusive lists based on ilist_node.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
OperandBundleDefT< Value * > OperandBundleDef
Definition: InstrTypes.h:993
INITIALIZE_PASS(WasmEHPrepare, DEBUG_TYPE, "Prepare WebAssembly exceptions", false, false) FunctionPass *llvm
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:176
iterator_range< user_iterator > users()
Definition: Value.h:400
Constant * getOrInsertGlobal(StringRef Name, Type *Ty, function_ref< GlobalVariable *()> CreateGlobalCallback)
Look up the specified global in the module symbol table.
Definition: Module.cpp:206
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
#define I(x, y, z)
Definition: MD5.cpp:58
void calculateWasmEHInfo(const Function *F, WasmEHFuncInfo &EHInfo)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:399
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:566
LLVM Value Representation.
Definition: Value.h:73
void setThrowUnwindDest(const BasicBlock *BB, const BasicBlock *Dest)
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
#define DEBUG_TYPE
void setDoesNotThrow()
Definition: InstrTypes.h:1556
This file describes how to lower LLVM code to machine code.