contrib/llvm/lib/CodeGen/WasmEHPrepare.cpp

   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"
 117 #include "llvm/CodeGen/TargetLowering.h"
 118 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 119 #include "llvm/CodeGen/WasmEHFuncInfo.h"
 120 #include "llvm/IR/Dominators.h"
 121 #include "llvm/IR/IRBuilder.h"
 122 #include "llvm/IR/Intrinsics.h"
 123 #include "llvm/Pass.h"
 124 #include "llvm/Transforms/Utils/BasicBlockUtils.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
 198 bool WasmEHPrepare::runOnFunction(Function &F) {
 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.
 211   ThrowF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_throw);
 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();
 225     SmallVector<BasicBlock *, 4> Succs(succ_begin(BB), succ_end(BB));
 226     auto &InstList = BB->getInstList();
 227     InstList.erase(std::next(BasicBlock::iterator(ThrowI)), InstList.end());
 228     IRB.SetInsertPoint(BB);
 229     IRB.CreateUnreachable();
 230     eraseDeadBBsAndChildren(Succs);
 231   }
 232
 233   return Changed;
 234 }
 235
 236 bool WasmEHPrepare::prepareEHPads(Function &F) {
 237   Module &M = *F.getParent();
 238   IRBuilder<> IRB(F.getContext());
 239
 240   SmallVector<BasicBlock *, 16> CatchPads;
 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.
 267   CatchF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_catch);
 268   // wasm.landingpad.index() intrinsic, which is to specify landingpad index
 269   LPadIndexF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_landingpad_index);
 270   // wasm.lsda() intrinsic. Returns the address of LSDA table for the current
 271   // function.
 272   LSDAF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_lsda);
 273   // wasm.get.exception() and wasm.get.ehselector() intrinsics. Calls to these
 274   // are generated in clang.
 275   GetExnF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_get_exception);
 276   GetSelectorF = Intrinsic::getDeclaration(&M, Intrinsic::wasm_get_ehselector);
 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
 390 void llvm::calculateWasmEHInfo(const Function *F, WasmEHFuncInfo &EHInfo) {
 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 }