contrib/llvm/lib/Target/WebAssembly/WebAssemblyLowerEmscriptenEHSjLj.cpp

   1 //=== WebAssemblyLowerEmscriptenEHSjLj.cpp - Lower exceptions for Emscripten =//
   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 /// \file
  11 /// \brief This file lowers exception-related instructions and setjmp/longjmp
  12 /// function calls in order to use Emscripten's JavaScript try and catch
  13 /// mechanism.
  14 ///
  15 /// To handle exceptions and setjmp/longjmps, this scheme relies on JavaScript's
  16 /// try and catch syntax and relevant exception-related libraries implemented
  17 /// in JavaScript glue code that will be produced by Emscripten. This is similar
  18 /// to the current Emscripten asm.js exception handling in fastcomp. For
  19 /// fastcomp's EH / SjLj scheme, see these files in fastcomp LLVM branch:
  20 /// (Location: https://github.com/kripken/emscripten-fastcomp)
  21 /// lib/Target/JSBackend/NaCl/LowerEmExceptionsPass.cpp
  22 /// lib/Target/JSBackend/NaCl/LowerEmSetjmp.cpp
  23 /// lib/Target/JSBackend/JSBackend.cpp
  24 /// lib/Target/JSBackend/CallHandlers.h
  25 ///
  26 /// * Exception handling
  27 /// This pass lowers invokes and landingpads into library functions in JS glue
  28 /// code. Invokes are lowered into function wrappers called invoke wrappers that
  29 /// exist in JS side, which wraps the original function call with JS try-catch.
  30 /// If an exception occurred, cxa_throw() function in JS side sets some
  31 /// variables (see below) so we can check whether an exception occurred from
  32 /// wasm code and handle it appropriately.
  33 ///
  34 /// * Setjmp-longjmp handling
  35 /// This pass lowers setjmp to a reasonably-performant approach for emscripten.
  36 /// The idea is that each block with a setjmp is broken up into two parts: the
  37 /// part containing setjmp and the part right after the setjmp. The latter part
  38 /// is either reached from the setjmp, or later from a longjmp. To handle the
  39 /// longjmp, all calls that might longjmp are also called using invoke wrappers
  40 /// and thus JS / try-catch. JS longjmp() function also sets some variables so
  41 /// we can check / whether a longjmp occurred from wasm code. Each block with a
  42 /// function call that might longjmp is also split up after the longjmp call.
  43 /// After the longjmp call, we check whether a longjmp occurred, and if it did,
  44 /// which setjmp it corresponds to, and jump to the right post-setjmp block.
  45 /// We assume setjmp-longjmp handling always run after EH handling, which means
  46 /// we don't expect any exception-related instructions when SjLj runs.
  47 /// FIXME Currently this scheme does not support indirect call of setjmp,
  48 /// because of the limitation of the scheme itself. fastcomp does not support it
  49 /// either.
  50 ///
  51 /// In detail, this pass does following things:
  52 ///
  53 /// 1) Create three global variables: __THREW__, __threwValue, and __tempRet0.
  54 ///    __tempRet0 will be set within __cxa_find_matching_catch() function in
  55 ///    JS library, and __THREW__ and __threwValue will be set in invoke wrappers
  56 ///    in JS glue code. For what invoke wrappers are, refer to 3). These
  57 ///    variables are used for both exceptions and setjmp/longjmps.
  58 ///    __THREW__ indicates whether an exception or a longjmp occurred or not. 0
  59 ///    means nothing occurred, 1 means an exception occurred, and other numbers
  60 ///    mean a longjmp occurred. In the case of longjmp, __threwValue variable
  61 ///    indicates the corresponding setjmp buffer the longjmp corresponds to.
  62 ///    In exception handling, __tempRet0 indicates the type of an exception
  63 ///    caught, and in setjmp/longjmp, it means the second argument to longjmp
  64 ///    function.
  65 ///
  66 /// * Exception handling
  67 ///
  68 /// 2) Create setThrew and setTempRet0 functions.
  69 ///    The global variables created in 1) will exist in wasm address space,
  70 ///    but their values should be set in JS code, so we provide these functions
  71 ///    as interfaces to JS glue code. These functions are equivalent to the
  72 ///    following JS functions, which actually exist in asm.js version of JS
  73 ///    library.
  74 ///
  75 ///    function setThrew(threw, value) {
  76 ///      if (__THREW__ == 0) {
  77 ///        __THREW__ = threw;
  78 ///        __threwValue = value;
  79 ///      }
  80 ///    }
  81 ///
  82 ///    function setTempRet0(value) {
  83 ///      __tempRet0 = value;
  84 ///    }
  85 ///
  86 /// 3) Lower
  87 ///      invoke @func(arg1, arg2) to label %invoke.cont unwind label %lpad
  88 ///    into
  89 ///      __THREW__ = 0;
  90 ///      call @__invoke_SIG(func, arg1, arg2)
  91 ///      %__THREW__.val = __THREW__;
  92 ///      __THREW__ = 0;
  93 ///      if (%__THREW__.val == 1)
  94 ///        goto %lpad
  95 ///      else
  96 ///         goto %invoke.cont
  97 ///    SIG is a mangled string generated based on the LLVM IR-level function
  98 ///    signature. After LLVM IR types are lowered to the target wasm types,
  99 ///    the names for these wrappers will change based on wasm types as well,
 100 ///    as in invoke_vi (function takes an int and returns void). The bodies of
 101 ///    these wrappers will be generated in JS glue code, and inside those
 102 ///    wrappers we use JS try-catch to generate actual exception effects. It
 103 ///    also calls the original callee function. An example wrapper in JS code
 104 ///    would look like this:
 105 ///      function invoke_vi(index,a1) {
 106 ///        try {
 107 ///          Module["dynCall_vi"](index,a1); // This calls original callee
 108 ///        } catch(e) {
 109 ///          if (typeof e !== 'number' && e !== 'longjmp') throw e;
 110 ///          asm["setThrew"](1, 0); // setThrew is called here
 111 ///        }
 112 ///      }
 113 ///    If an exception is thrown, __THREW__ will be set to true in a wrapper,
 114 ///    so we can jump to the right BB based on this value.
 115 ///
 116 /// 4) Lower
 117 ///      %val = landingpad catch c1 catch c2 catch c3 ...
 118 ///      ... use %val ...
 119 ///    into
 120 ///      %fmc = call @__cxa_find_matching_catch_N(c1, c2, c3, ...)
 121 ///      %val = {%fmc, __tempRet0}
 122 ///      ... use %val ...
 123 ///    Here N is a number calculated based on the number of clauses.
 124 ///    Global variable __tempRet0 is set within __cxa_find_matching_catch() in
 125 ///    JS glue code.
 126 ///
 127 /// 5) Lower
 128 ///      resume {%a, %b}
 129 ///    into
 130 ///      call @__resumeException(%a)
 131 ///    where __resumeException() is a function in JS glue code.
 132 ///
 133 /// 6) Lower
 134 ///      call @llvm.eh.typeid.for(type) (intrinsic)
 135 ///    into
 136 ///      call @llvm_eh_typeid_for(type)
 137 ///    llvm_eh_typeid_for function will be generated in JS glue code.
 138 ///
 139 /// * Setjmp / Longjmp handling
 140 ///
 141 /// 7) In the function entry that calls setjmp, initialize setjmpTable and
 142 ///    sejmpTableSize as follows:
 143 ///      setjmpTableSize = 4;
 144 ///      setjmpTable = (int *) malloc(40);
 145 ///      setjmpTable[0] = 0;
 146 ///    setjmpTable and setjmpTableSize are used in saveSetjmp() function in JS
 147 ///    code.
 148 ///
 149 /// 8) Lower
 150 ///      setjmp(buf)
 151 ///    into
 152 ///      setjmpTable = saveSetjmp(buf, label, setjmpTable, setjmpTableSize);
 153 ///      setjmpTableSize = __tempRet0;
 154 ///    For each dynamic setjmp call, setjmpTable stores its ID (a number which
 155 ///    is incrementally assigned from 0) and its label (a unique number that
 156 ///    represents each callsite of setjmp). When we need more entries in
 157 ///    setjmpTable, it is reallocated in saveSetjmp() in JS code and it will
 158 ///    return the new table address, and assign the new table size in
 159 ///    __tempRet0. saveSetjmp also stores the setjmp's ID into the buffer buf.
 160 ///    A BB with setjmp is split into two after setjmp call in order to make the
 161 ///    post-setjmp BB the possible destination of longjmp BB.
 162 ///
 163 /// 9) Lower
 164 ///      longjmp(buf, value)
 165 ///    into
 166 ///      emscripten_longjmp_jmpbuf(buf, value)
 167 ///    emscripten_longjmp_jmpbuf will be lowered to emscripten_longjmp later.
 168 ///
 169 /// 10) Lower every call that might longjmp into
 170 ///      __THREW__ = 0;
 171 ///      call @__invoke_SIG(func, arg1, arg2)
 172 ///      %__THREW__.val = __THREW__;
 173 ///      __THREW__ = 0;
 174 ///      if (%__THREW__.val != 0 & __threwValue != 0) {
 175 ///        %label = testSetjmp(mem[%__THREW__.val], setjmpTable,
 176 ///                            setjmpTableSize);
 177 ///        if (%label == 0)
 178 ///          emscripten_longjmp(%__THREW__.val, __threwValue);
 179 ///        __tempRet0 = __threwValue;
 180 ///      } else {
 181 ///        %label = -1;
 182 ///      }
 183 ///      longjmp_result = __tempRet0;
 184 ///      switch label {
 185 ///        label 1: goto post-setjmp BB 1
 186 ///        label 2: goto post-setjmp BB 2
 187 ///        ...
 188 ///        default: goto splitted next BB
 189 ///      }
 190 ///     testSetjmp examines setjmpTable to see if there is a matching setjmp
 191 ///     call. After calling an invoke wrapper, if a longjmp occurred, __THREW__
 192 ///     will be the address of matching jmp_buf buffer and __threwValue be the
 193 ///     second argument to longjmp. mem[__THREW__.val] is a setjmp ID that is
 194 ///     stored in saveSetjmp. testSetjmp returns a setjmp label, a unique ID to
 195 ///     each setjmp callsite. Label 0 means this longjmp buffer does not
 196 ///     correspond to one of the setjmp callsites in this function, so in this
 197 ///     case we just chain the longjmp to the caller. (Here we call
 198 ///     emscripten_longjmp, which is different from emscripten_longjmp_jmpbuf.
 199 ///     emscripten_longjmp_jmpbuf takes jmp_buf as its first argument, while
 200 ///     emscripten_longjmp takes an int. Both of them will eventually be lowered
 201 ///     to emscripten_longjmp in s2wasm, but here we need two signatures - we
 202 ///     can't translate an int value to a jmp_buf.)
 203 ///     Label -1 means no longjmp occurred. Otherwise we jump to the right
 204 ///     post-setjmp BB based on the label.
 205 ///
 206 ///===----------------------------------------------------------------------===//
 207
 208 #include "WebAssembly.h"
 209 #include "llvm/IR/CallSite.h"
 210 #include "llvm/IR/Dominators.h"
 211 #include "llvm/IR/IRBuilder.h"
 212 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 213 #include "llvm/Transforms/Utils/SSAUpdater.h"
 214
 215 using namespace llvm;
 216
 217 #define DEBUG_TYPE "wasm-lower-em-ehsjlj"
 218
 219 static cl::list<std::string>
 220     EHWhitelist("emscripten-cxx-exceptions-whitelist",
 221                 cl::desc("The list of function names in which Emscripten-style "
 222                          "exception handling is enabled (see emscripten "
 223                          "EMSCRIPTEN_CATCHING_WHITELIST options)"),
 224                 cl::CommaSeparated);
 225
 226 namespace {
 227 class WebAssemblyLowerEmscriptenEHSjLj final : public ModulePass {
 228   static const char *ThrewGVName;
 229   static const char *ThrewValueGVName;
 230   static const char *TempRet0GVName;
 231   static const char *ResumeFName;
 232   static const char *EHTypeIDFName;
 233   static const char *SetThrewFName;
 234   static const char *SetTempRet0FName;
 235   static const char *EmLongjmpFName;
 236   static const char *EmLongjmpJmpbufFName;
 237   static const char *SaveSetjmpFName;
 238   static const char *TestSetjmpFName;
 239   static const char *FindMatchingCatchPrefix;
 240   static const char *InvokePrefix;
 241
 242   bool EnableEH;   // Enable exception handling
 243   bool EnableSjLj; // Enable setjmp/longjmp handling
 244
 245   GlobalVariable *ThrewGV;
 246   GlobalVariable *ThrewValueGV;
 247   GlobalVariable *TempRet0GV;
 248   Function *ResumeF;
 249   Function *EHTypeIDF;
 250   Function *EmLongjmpF;
 251   Function *EmLongjmpJmpbufF;
 252   Function *SaveSetjmpF;
 253   Function *TestSetjmpF;
 254
 255   // __cxa_find_matching_catch_N functions.
 256   // Indexed by the number of clauses in an original landingpad instruction.
 257   DenseMap<int, Function *> FindMatchingCatches;
 258   // Map of <function signature string, invoke_ wrappers>
 259   StringMap<Function *> InvokeWrappers;
 260   // Set of whitelisted function names for exception handling
 261   std::set<std::string> EHWhitelistSet;
 262
 263   StringRef getPassName() const override {
 264     return "WebAssembly Lower Emscripten Exceptions";
 265   }
 266
 267   bool runEHOnFunction(Function &F);
 268   bool runSjLjOnFunction(Function &F);
 269   Function *getFindMatchingCatch(Module &M, unsigned NumClauses);
 270
 271   template <typename CallOrInvoke> Value *wrapInvoke(CallOrInvoke *CI);
 272   void wrapTestSetjmp(BasicBlock *BB, Instruction *InsertPt, Value *Threw,
 273                       Value *SetjmpTable, Value *SetjmpTableSize, Value *&Label,
 274                       Value *&LongjmpResult, BasicBlock *&EndBB);
 275   template <typename CallOrInvoke> Function *getInvokeWrapper(CallOrInvoke *CI);
 276
 277   bool areAllExceptionsAllowed() const { return EHWhitelistSet.empty(); }
 278   bool canLongjmp(Module &M, const Value *Callee) const;
 279
 280   void createSetThrewFunction(Module &M);
 281   void createSetTempRet0Function(Module &M);
 282
 283   void rebuildSSA(Function &F);
 284
 285 public:
 286   static char ID;
 287
 288   WebAssemblyLowerEmscriptenEHSjLj(bool EnableEH = true, bool EnableSjLj = true)
 289       : ModulePass(ID), EnableEH(EnableEH), EnableSjLj(EnableSjLj),
 290         ThrewGV(nullptr), ThrewValueGV(nullptr), TempRet0GV(nullptr),
 291         ResumeF(nullptr), EHTypeIDF(nullptr), EmLongjmpF(nullptr),
 292         EmLongjmpJmpbufF(nullptr), SaveSetjmpF(nullptr), TestSetjmpF(nullptr) {
 293     EHWhitelistSet.insert(EHWhitelist.begin(), EHWhitelist.end());
 294   }
 295   bool runOnModule(Module &M) override;
 296
 297   void getAnalysisUsage(AnalysisUsage &AU) const override {
 298     AU.addRequired<DominatorTreeWrapperPass>();
 299   }
 300 };
 301 } // End anonymous namespace
 302
 303 const char *WebAssemblyLowerEmscriptenEHSjLj::ThrewGVName = "__THREW__";
 304 const char *WebAssemblyLowerEmscriptenEHSjLj::ThrewValueGVName = "__threwValue";
 305 const char *WebAssemblyLowerEmscriptenEHSjLj::TempRet0GVName = "__tempRet0";
 306 const char *WebAssemblyLowerEmscriptenEHSjLj::ResumeFName = "__resumeException";
 307 const char *WebAssemblyLowerEmscriptenEHSjLj::EHTypeIDFName =
 308     "llvm_eh_typeid_for";
 309 const char *WebAssemblyLowerEmscriptenEHSjLj::SetThrewFName = "setThrew";
 310 const char *WebAssemblyLowerEmscriptenEHSjLj::SetTempRet0FName = "setTempRet0";
 311 const char *WebAssemblyLowerEmscriptenEHSjLj::EmLongjmpFName =
 312     "emscripten_longjmp";
 313 const char *WebAssemblyLowerEmscriptenEHSjLj::EmLongjmpJmpbufFName =
 314     "emscripten_longjmp_jmpbuf";
 315 const char *WebAssemblyLowerEmscriptenEHSjLj::SaveSetjmpFName = "saveSetjmp";
 316 const char *WebAssemblyLowerEmscriptenEHSjLj::TestSetjmpFName = "testSetjmp";
 317 const char *WebAssemblyLowerEmscriptenEHSjLj::FindMatchingCatchPrefix =
 318     "__cxa_find_matching_catch_";
 319 const char *WebAssemblyLowerEmscriptenEHSjLj::InvokePrefix = "__invoke_";
 320
 321 char WebAssemblyLowerEmscriptenEHSjLj::ID = 0;
 322 INITIALIZE_PASS(WebAssemblyLowerEmscriptenEHSjLj, DEBUG_TYPE,
 323                 "WebAssembly Lower Emscripten Exceptions / Setjmp / Longjmp",
 324                 false, false)
 325
 326 ModulePass *llvm::createWebAssemblyLowerEmscriptenEHSjLj(bool EnableEH,
 327                                                          bool EnableSjLj) {
 328   return new WebAssemblyLowerEmscriptenEHSjLj(EnableEH, EnableSjLj);
 329 }
 330
 331 static bool canThrow(const Value *V) {
 332   if (const auto *F = dyn_cast<const Function>(V)) {
 333     // Intrinsics cannot throw
 334     if (F->isIntrinsic())
 335       return false;
 336     StringRef Name = F->getName();
 337     // leave setjmp and longjmp (mostly) alone, we process them properly later
 338     if (Name == "setjmp" || Name == "longjmp")
 339       return false;
 340     return !F->doesNotThrow();
 341   }
 342   // not a function, so an indirect call - can throw, we can't tell
 343   return true;
 344 }
 345
 346 // Returns an available name for a global value.
 347 // If the proposed name already exists in the module, adds '_' at the end of
 348 // the name until the name is available.
 349 static inline std::string createGlobalValueName(const Module &M,
 350                                                 const std::string &Propose) {
 351   std::string Name = Propose;
 352   while (M.getNamedGlobal(Name))
 353     Name += "_";
 354   return Name;
 355 }
 356
 357 // Simple function name mangler.
 358 // This function simply takes LLVM's string representation of parameter types
 359 // and concatenate them with '_'. There are non-alphanumeric characters but llc
 360 // is ok with it, and we need to postprocess these names after the lowering
 361 // phase anyway.
 362 static std::string getSignature(FunctionType *FTy) {
 363   std::string Sig;
 364   raw_string_ostream OS(Sig);
 365   OS << *FTy->getReturnType();
 366   for (Type *ParamTy : FTy->params())
 367     OS << "_" << *ParamTy;
 368   if (FTy->isVarArg())
 369     OS << "_...";
 370   Sig = OS.str();
 371   Sig.erase(remove_if(Sig, isspace), Sig.end());
 372   // When s2wasm parses .s file, a comma means the end of an argument. So a
 373   // mangled function name can contain any character but a comma.
 374   std::replace(Sig.begin(), Sig.end(), ',', '.');
 375   return Sig;
 376 }
 377
 378 // Returns __cxa_find_matching_catch_N function, where N = NumClauses + 2.
 379 // This is because a landingpad instruction contains two more arguments, a
 380 // personality function and a cleanup bit, and __cxa_find_matching_catch_N
 381 // functions are named after the number of arguments in the original landingpad
 382 // instruction.
 383 Function *
 384 WebAssemblyLowerEmscriptenEHSjLj::getFindMatchingCatch(Module &M,
 385                                                        unsigned NumClauses) {
 386   if (FindMatchingCatches.count(NumClauses))
 387     return FindMatchingCatches[NumClauses];
 388   PointerType *Int8PtrTy = Type::getInt8PtrTy(M.getContext());
 389   SmallVector<Type *, 16> Args(NumClauses, Int8PtrTy);
 390   FunctionType *FTy = FunctionType::get(Int8PtrTy, Args, false);
 391   Function *F =
 392       Function::Create(FTy, GlobalValue::ExternalLinkage,
 393                        FindMatchingCatchPrefix + Twine(NumClauses + 2), &M);
 394   FindMatchingCatches[NumClauses] = F;
 395   return F;
 396 }
 397
 398 // Generate invoke wrapper seqence with preamble and postamble
 399 // Preamble:
 400 // __THREW__ = 0;
 401 // Postamble:
 402 // %__THREW__.val = __THREW__; __THREW__ = 0;
 403 // Returns %__THREW__.val, which indicates whether an exception is thrown (or
 404 // whether longjmp occurred), for future use.
 405 template <typename CallOrInvoke>
 406 Value *WebAssemblyLowerEmscriptenEHSjLj::wrapInvoke(CallOrInvoke *CI) {
 407   LLVMContext &C = CI->getModule()->getContext();
 408
 409   // If we are calling a function that is noreturn, we must remove that
 410   // attribute. The code we insert here does expect it to return, after we
 411   // catch the exception.
 412   if (CI->doesNotReturn()) {
 413     if (auto *F = dyn_cast<Function>(CI->getCalledValue()))
 414       F->removeFnAttr(Attribute::NoReturn);
 415     CI->removeAttribute(AttributeSet::FunctionIndex, Attribute::NoReturn);
 416   }
 417
 418   IRBuilder<> IRB(C);
 419   IRB.SetInsertPoint(CI);
 420
 421   // Pre-invoke
 422   // __THREW__ = 0;
 423   IRB.CreateStore(IRB.getInt32(0), ThrewGV);
 424
 425   // Invoke function wrapper in JavaScript
 426   SmallVector<Value *, 16> Args;
 427   // Put the pointer to the callee as first argument, so it can be called
 428   // within the invoke wrapper later
 429   Args.push_back(CI->getCalledValue());
 430   Args.append(CI->arg_begin(), CI->arg_end());
 431   CallInst *NewCall = IRB.CreateCall(getInvokeWrapper(CI), Args);
 432   NewCall->takeName(CI);
 433   NewCall->setCallingConv(CI->getCallingConv());
 434   NewCall->setDebugLoc(CI->getDebugLoc());
 435
 436   // Because we added the pointer to the callee as first argument, all
 437   // argument attribute indices have to be incremented by one.
 438   SmallVector<AttributeSet, 8> AttributesVec;
 439   const AttributeSet &InvokePAL = CI->getAttributes();
 440   CallSite::arg_iterator AI = CI->arg_begin();
 441   unsigned i = 1; // Argument attribute index starts from 1
 442   for (unsigned e = CI->getNumArgOperands(); i <= e; ++AI, ++i) {
 443     if (InvokePAL.hasAttributes(i)) {
 444       AttrBuilder B(InvokePAL, i);
 445       AttributesVec.push_back(AttributeSet::get(C, i + 1, B));
 446     }
 447   }
 448   // Add any return attributes.
 449   if (InvokePAL.hasAttributes(AttributeSet::ReturnIndex))
 450     AttributesVec.push_back(AttributeSet::get(C, InvokePAL.getRetAttributes()));
 451   // Add any function attributes.
 452   if (InvokePAL.hasAttributes(AttributeSet::FunctionIndex))
 453     AttributesVec.push_back(AttributeSet::get(C, InvokePAL.getFnAttributes()));
 454   // Reconstruct the AttributesList based on the vector we constructed.
 455   AttributeSet NewCallPAL = AttributeSet::get(C, AttributesVec);
 456   NewCall->setAttributes(NewCallPAL);
 457
 458   CI->replaceAllUsesWith(NewCall);
 459
 460   // Post-invoke
 461   // %__THREW__.val = __THREW__; __THREW__ = 0;
 462   Value *Threw = IRB.CreateLoad(ThrewGV, ThrewGV->getName() + ".val");
 463   IRB.CreateStore(IRB.getInt32(0), ThrewGV);
 464   return Threw;
 465 }
 466
 467 // Get matching invoke wrapper based on callee signature
 468 template <typename CallOrInvoke>
 469 Function *WebAssemblyLowerEmscriptenEHSjLj::getInvokeWrapper(CallOrInvoke *CI) {
 470   Module *M = CI->getModule();
 471   SmallVector<Type *, 16> ArgTys;
 472   Value *Callee = CI->getCalledValue();
 473   FunctionType *CalleeFTy;
 474   if (auto *F = dyn_cast<Function>(Callee))
 475     CalleeFTy = F->getFunctionType();
 476   else {
 477     auto *CalleeTy = cast<PointerType>(Callee->getType())->getElementType();
 478     CalleeFTy = dyn_cast<FunctionType>(CalleeTy);
 479   }
 480
 481   std::string Sig = getSignature(CalleeFTy);
 482   if (InvokeWrappers.find(Sig) != InvokeWrappers.end())
 483     return InvokeWrappers[Sig];
 484
 485   // Put the pointer to the callee as first argument
 486   ArgTys.push_back(PointerType::getUnqual(CalleeFTy));
 487   // Add argument types
 488   ArgTys.append(CalleeFTy->param_begin(), CalleeFTy->param_end());
 489
 490   FunctionType *FTy = FunctionType::get(CalleeFTy->getReturnType(), ArgTys,
 491                                         CalleeFTy->isVarArg());
 492   Function *F = Function::Create(FTy, GlobalValue::ExternalLinkage,
 493                                  InvokePrefix + Sig, M);
 494   InvokeWrappers[Sig] = F;
 495   return F;
 496 }
 497
 498 bool WebAssemblyLowerEmscriptenEHSjLj::canLongjmp(Module &M,
 499                                                   const Value *Callee) const {
 500   if (auto *CalleeF = dyn_cast<Function>(Callee))
 501     if (CalleeF->isIntrinsic())
 502       return false;
 503
 504   // The reason we include malloc/free here is to exclude the malloc/free
 505   // calls generated in setjmp prep / cleanup routines.
 506   Function *SetjmpF = M.getFunction("setjmp");
 507   Function *MallocF = M.getFunction("malloc");
 508   Function *FreeF = M.getFunction("free");
 509   if (Callee == SetjmpF || Callee == MallocF || Callee == FreeF)
 510     return false;
 511
 512   // There are functions in JS glue code
 513   if (Callee == ResumeF || Callee == EHTypeIDF || Callee == SaveSetjmpF ||
 514       Callee == TestSetjmpF)
 515     return false;
 516
 517   // __cxa_find_matching_catch_N functions cannot longjmp
 518   if (Callee->getName().startswith(FindMatchingCatchPrefix))
 519     return false;
 520
 521   // Exception-catching related functions
 522   Function *BeginCatchF = M.getFunction("__cxa_begin_catch");
 523   Function *EndCatchF = M.getFunction("__cxa_end_catch");
 524   Function *AllocExceptionF = M.getFunction("__cxa_allocate_exception");
 525   Function *ThrowF = M.getFunction("__cxa_throw");
 526   Function *TerminateF = M.getFunction("__clang_call_terminate");
 527   if (Callee == BeginCatchF || Callee == EndCatchF ||
 528       Callee == AllocExceptionF || Callee == ThrowF || Callee == TerminateF)
 529     return false;
 530
 531   // Otherwise we don't know
 532   return true;
 533 }
 534
 535 // Generate testSetjmp function call seqence with preamble and postamble.
 536 // The code this generates is equivalent to the following JavaScript code:
 537 // if (%__THREW__.val != 0 & threwValue != 0) {
 538 //   %label = _testSetjmp(mem[%__THREW__.val], setjmpTable, setjmpTableSize);
 539 //   if (%label == 0)
 540 //     emscripten_longjmp(%__THREW__.val, threwValue);
 541 //   __tempRet0 = threwValue;
 542 // } else {
 543 //   %label = -1;
 544 // }
 545 // %longjmp_result = __tempRet0;
 546 //
 547 // As output parameters. returns %label, %longjmp_result, and the BB the last
 548 // instruction (%longjmp_result = ...) is in.
 549 void WebAssemblyLowerEmscriptenEHSjLj::wrapTestSetjmp(
 550     BasicBlock *BB, Instruction *InsertPt, Value *Threw, Value *SetjmpTable,
 551     Value *SetjmpTableSize, Value *&Label, Value *&LongjmpResult,
 552     BasicBlock *&EndBB) {
 553   Function *F = BB->getParent();
 554   LLVMContext &C = BB->getModule()->getContext();
 555   IRBuilder<> IRB(C);
 556   IRB.SetInsertPoint(InsertPt);
 557
 558   // if (%__THREW__.val != 0 & threwValue != 0)
 559   IRB.SetInsertPoint(BB);
 560   BasicBlock *ThenBB1 = BasicBlock::Create(C, "if.then1", F);
 561   BasicBlock *ElseBB1 = BasicBlock::Create(C, "if.else1", F);
 562   BasicBlock *EndBB1 = BasicBlock::Create(C, "if.end", F);
 563   Value *ThrewCmp = IRB.CreateICmpNE(Threw, IRB.getInt32(0));
 564   Value *ThrewValue =
 565       IRB.CreateLoad(ThrewValueGV, ThrewValueGV->getName() + ".val");
 566   Value *ThrewValueCmp = IRB.CreateICmpNE(ThrewValue, IRB.getInt32(0));
 567   Value *Cmp1 = IRB.CreateAnd(ThrewCmp, ThrewValueCmp, "cmp1");
 568   IRB.CreateCondBr(Cmp1, ThenBB1, ElseBB1);
 569
 570   // %label = _testSetjmp(mem[%__THREW__.val], _setjmpTable, _setjmpTableSize);
 571   // if (%label == 0)
 572   IRB.SetInsertPoint(ThenBB1);
 573   BasicBlock *ThenBB2 = BasicBlock::Create(C, "if.then2", F);
 574   BasicBlock *EndBB2 = BasicBlock::Create(C, "if.end2", F);
 575   Value *ThrewInt = IRB.CreateIntToPtr(Threw, Type::getInt32PtrTy(C),
 576                                        Threw->getName() + ".i32p");
 577   Value *LoadedThrew =
 578       IRB.CreateLoad(ThrewInt, ThrewInt->getName() + ".loaded");
 579   Value *ThenLabel = IRB.CreateCall(
 580       TestSetjmpF, {LoadedThrew, SetjmpTable, SetjmpTableSize}, "label");
 581   Value *Cmp2 = IRB.CreateICmpEQ(ThenLabel, IRB.getInt32(0));
 582   IRB.CreateCondBr(Cmp2, ThenBB2, EndBB2);
 583
 584   // emscripten_longjmp(%__THREW__.val, threwValue);
 585   IRB.SetInsertPoint(ThenBB2);
 586   IRB.CreateCall(EmLongjmpF, {Threw, ThrewValue});
 587   IRB.CreateUnreachable();
 588
 589   // __tempRet0 = threwValue;
 590   IRB.SetInsertPoint(EndBB2);
 591   IRB.CreateStore(ThrewValue, TempRet0GV);
 592   IRB.CreateBr(EndBB1);
 593
 594   IRB.SetInsertPoint(ElseBB1);
 595   IRB.CreateBr(EndBB1);
 596
 597   // longjmp_result = __tempRet0;
 598   IRB.SetInsertPoint(EndBB1);
 599   PHINode *LabelPHI = IRB.CreatePHI(IRB.getInt32Ty(), 2, "label");
 600   LabelPHI->addIncoming(ThenLabel, EndBB2);
 601
 602   LabelPHI->addIncoming(IRB.getInt32(-1), ElseBB1);
 603
 604   // Output parameter assignment
 605   Label = LabelPHI;
 606   EndBB = EndBB1;
 607   LongjmpResult = IRB.CreateLoad(TempRet0GV, "longjmp_result");
 608 }
 609
 610 // Create setThrew function
 611 // function setThrew(threw, value) {
 612 //   if (__THREW__ == 0) {
 613 //     __THREW__ = threw;
 614 //     __threwValue = value;
 615 //   }
 616 // }
 617 void WebAssemblyLowerEmscriptenEHSjLj::createSetThrewFunction(Module &M) {
 618   LLVMContext &C = M.getContext();
 619   IRBuilder<> IRB(C);
 620
 621   assert(!M.getNamedGlobal(SetThrewFName) && "setThrew already exists");
 622   Type *Params[] = {IRB.getInt32Ty(), IRB.getInt32Ty()};
 623   FunctionType *FTy = FunctionType::get(IRB.getVoidTy(), Params, false);
 624   Function *F =
 625       Function::Create(FTy, GlobalValue::ExternalLinkage, SetThrewFName, &M);
 626   Argument *Arg1 = &*(F->arg_begin());
 627   Argument *Arg2 = &*(++F->arg_begin());
 628   Arg1->setName("threw");
 629   Arg2->setName("value");
 630   BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
 631   BasicBlock *ThenBB = BasicBlock::Create(C, "if.then", F);
 632   BasicBlock *EndBB = BasicBlock::Create(C, "if.end", F);
 633
 634   IRB.SetInsertPoint(EntryBB);
 635   Value *Threw = IRB.CreateLoad(ThrewGV, ThrewGV->getName() + ".val");
 636   Value *Cmp = IRB.CreateICmpEQ(Threw, IRB.getInt32(0), "cmp");
 637   IRB.CreateCondBr(Cmp, ThenBB, EndBB);
 638
 639   IRB.SetInsertPoint(ThenBB);
 640   IRB.CreateStore(Arg1, ThrewGV);
 641   IRB.CreateStore(Arg2, ThrewValueGV);
 642   IRB.CreateBr(EndBB);
 643
 644   IRB.SetInsertPoint(EndBB);
 645   IRB.CreateRetVoid();
 646 }
 647
 648 // Create setTempRet0 function
 649 // function setTempRet0(value) {
 650 //   __tempRet0 = value;
 651 // }
 652 void WebAssemblyLowerEmscriptenEHSjLj::createSetTempRet0Function(Module &M) {
 653   LLVMContext &C = M.getContext();
 654   IRBuilder<> IRB(C);
 655
 656   assert(!M.getNamedGlobal(SetTempRet0FName) && "setTempRet0 already exists");
 657   Type *Params[] = {IRB.getInt32Ty()};
 658   FunctionType *FTy = FunctionType::get(IRB.getVoidTy(), Params, false);
 659   Function *F =
 660       Function::Create(FTy, GlobalValue::ExternalLinkage, SetTempRet0FName, &M);
 661   F->arg_begin()->setName("value");
 662   BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
 663   IRB.SetInsertPoint(EntryBB);
 664   IRB.CreateStore(&*F->arg_begin(), TempRet0GV);
 665   IRB.CreateRetVoid();
 666 }
 667
 668 void WebAssemblyLowerEmscriptenEHSjLj::rebuildSSA(Function &F) {
 669   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
 670   DT.recalculate(F); // CFG has been changed
 671   SSAUpdater SSA;
 672   for (BasicBlock &BB : F) {
 673     for (Instruction &I : BB) {
 674       for (auto UI = I.use_begin(), UE = I.use_end(); UI != UE;) {
 675         Use &U = *UI;
 676         ++UI;
 677         SSA.Initialize(I.getType(), I.getName());
 678         SSA.AddAvailableValue(&BB, &I);
 679         Instruction *User = cast<Instruction>(U.getUser());
 680         if (User->getParent() == &BB)
 681           continue;
 682
 683         if (PHINode *UserPN = dyn_cast<PHINode>(User))
 684           if (UserPN->getIncomingBlock(U) == &BB)
 685             continue;
 686
 687         if (DT.dominates(&I, User))
 688           continue;
 689         SSA.RewriteUseAfterInsertions(U);
 690       }
 691     }
 692   }
 693 }
 694
 695 bool WebAssemblyLowerEmscriptenEHSjLj::runOnModule(Module &M) {
 696   LLVMContext &C = M.getContext();
 697   IRBuilder<> IRB(C);
 698
 699   Function *SetjmpF = M.getFunction("setjmp");
 700   Function *LongjmpF = M.getFunction("longjmp");
 701   bool SetjmpUsed = SetjmpF && !SetjmpF->use_empty();
 702   bool LongjmpUsed = LongjmpF && !LongjmpF->use_empty();
 703   bool DoSjLj = EnableSjLj && (SetjmpUsed || LongjmpUsed);
 704
 705   // Create global variables __THREW__, threwValue, and __tempRet0, which are
 706   // used in common for both exception handling and setjmp/longjmp handling
 707   ThrewGV = new GlobalVariable(M, IRB.getInt32Ty(), false,
 708                                GlobalValue::ExternalLinkage, IRB.getInt32(0),
 709                                createGlobalValueName(M, ThrewGVName));
 710   ThrewValueGV = new GlobalVariable(
 711       M, IRB.getInt32Ty(), false, GlobalValue::ExternalLinkage, IRB.getInt32(0),
 712       createGlobalValueName(M, ThrewValueGVName));
 713   TempRet0GV = new GlobalVariable(M, IRB.getInt32Ty(), false,
 714                                   GlobalValue::ExternalLinkage, IRB.getInt32(0),
 715                                   createGlobalValueName(M, TempRet0GVName));
 716
 717   bool Changed = false;
 718
 719   // Exception handling
 720   if (EnableEH) {
 721     // Register __resumeException function
 722     FunctionType *ResumeFTy =
 723         FunctionType::get(IRB.getVoidTy(), IRB.getInt8PtrTy(), false);
 724     ResumeF = Function::Create(ResumeFTy, GlobalValue::ExternalLinkage,
 725                                ResumeFName, &M);
 726
 727     // Register llvm_eh_typeid_for function
 728     FunctionType *EHTypeIDTy =
 729         FunctionType::get(IRB.getInt32Ty(), IRB.getInt8PtrTy(), false);
 730     EHTypeIDF = Function::Create(EHTypeIDTy, GlobalValue::ExternalLinkage,
 731                                  EHTypeIDFName, &M);
 732
 733     for (Function &F : M) {
 734       if (F.isDeclaration())
 735         continue;
 736       Changed |= runEHOnFunction(F);
 737     }
 738   }
 739
 740   // Setjmp/longjmp handling
 741   if (DoSjLj) {
 742     Changed = true; // We have setjmp or longjmp somewhere
 743
 744     Function *MallocF = M.getFunction("malloc");
 745     Function *FreeF = M.getFunction("free");
 746     if (!MallocF || !FreeF)
 747       report_fatal_error(
 748           "malloc and free must be linked into the module if setjmp is used");
 749
 750     // Register saveSetjmp function
 751     FunctionType *SetjmpFTy = SetjmpF->getFunctionType();
 752     SmallVector<Type *, 4> Params = {SetjmpFTy->getParamType(0),
 753                                      IRB.getInt32Ty(), Type::getInt32PtrTy(C),
 754                                      IRB.getInt32Ty()};
 755     FunctionType *FTy =
 756         FunctionType::get(Type::getInt32PtrTy(C), Params, false);
 757     SaveSetjmpF = Function::Create(FTy, GlobalValue::ExternalLinkage,
 758                                    SaveSetjmpFName, &M);
 759
 760     // Register testSetjmp function
 761     Params = {IRB.getInt32Ty(), Type::getInt32PtrTy(C), IRB.getInt32Ty()};
 762     FTy = FunctionType::get(IRB.getInt32Ty(), Params, false);
 763     TestSetjmpF = Function::Create(FTy, GlobalValue::ExternalLinkage,
 764                                    TestSetjmpFName, &M);
 765
 766     if (LongjmpF) {
 767       // Replace all uses of longjmp with emscripten_longjmp_jmpbuf, which is
 768       // defined in JS code
 769       EmLongjmpJmpbufF = Function::Create(LongjmpF->getFunctionType(),
 770                                           GlobalValue::ExternalLinkage,
 771                                           EmLongjmpJmpbufFName, &M);
 772
 773       LongjmpF->replaceAllUsesWith(EmLongjmpJmpbufF);
 774     }
 775     FTy = FunctionType::get(IRB.getVoidTy(),
 776                             {IRB.getInt32Ty(), IRB.getInt32Ty()}, false);
 777     EmLongjmpF =
 778         Function::Create(FTy, GlobalValue::ExternalLinkage, EmLongjmpFName, &M);
 779
 780     // Only traverse functions that uses setjmp in order not to insert
 781     // unnecessary prep / cleanup code in every function
 782     SmallPtrSet<Function *, 8> SetjmpUsers;
 783     for (User *U : SetjmpF->users()) {
 784       auto *UI = cast<Instruction>(U);
 785       SetjmpUsers.insert(UI->getFunction());
 786     }
 787     for (Function *F : SetjmpUsers)
 788       runSjLjOnFunction(*F);
 789   }
 790
 791   if (!Changed) {
 792     // Delete unused global variables and functions
 793     ThrewGV->eraseFromParent();
 794     ThrewValueGV->eraseFromParent();
 795     TempRet0GV->eraseFromParent();
 796     if (ResumeF)
 797       ResumeF->eraseFromParent();
 798     if (EHTypeIDF)
 799       EHTypeIDF->eraseFromParent();
 800     if (EmLongjmpF)
 801       EmLongjmpF->eraseFromParent();
 802     if (SaveSetjmpF)
 803       SaveSetjmpF->eraseFromParent();
 804     if (TestSetjmpF)
 805       TestSetjmpF->eraseFromParent();
 806     return false;
 807   }
 808
 809   // If we have made any changes while doing exception handling or
 810   // setjmp/longjmp handling, we have to create these functions for JavaScript
 811   // to call.
 812   createSetThrewFunction(M);
 813   createSetTempRet0Function(M);
 814
 815   return true;
 816 }
 817
 818 bool WebAssemblyLowerEmscriptenEHSjLj::runEHOnFunction(Function &F) {
 819   Module &M = *F.getParent();
 820   LLVMContext &C = F.getContext();
 821   IRBuilder<> IRB(C);
 822   bool Changed = false;
 823   SmallVector<Instruction *, 64> ToErase;
 824   SmallPtrSet<LandingPadInst *, 32> LandingPads;
 825   bool AllowExceptions =
 826       areAllExceptionsAllowed() || EHWhitelistSet.count(F.getName());
 827
 828   for (BasicBlock &BB : F) {
 829     auto *II = dyn_cast<InvokeInst>(BB.getTerminator());
 830     if (!II)
 831       continue;
 832     Changed = true;
 833     LandingPads.insert(II->getLandingPadInst());
 834     IRB.SetInsertPoint(II);
 835
 836     bool NeedInvoke = AllowExceptions && canThrow(II->getCalledValue());
 837     if (NeedInvoke) {
 838       // Wrap invoke with invoke wrapper and generate preamble/postamble
 839       Value *Threw = wrapInvoke(II);
 840       ToErase.push_back(II);
 841
 842       // Insert a branch based on __THREW__ variable
 843       Value *Cmp = IRB.CreateICmpEQ(Threw, IRB.getInt32(1), "cmp");
 844       IRB.CreateCondBr(Cmp, II->getUnwindDest(), II->getNormalDest());
 845
 846     } else {
 847       // This can't throw, and we don't need this invoke, just replace it with a
 848       // call+branch
 849       SmallVector<Value *, 16> Args(II->arg_begin(), II->arg_end());
 850       CallInst *NewCall = IRB.CreateCall(II->getCalledValue(), Args);
 851       NewCall->takeName(II);
 852       NewCall->setCallingConv(II->getCallingConv());
 853       NewCall->setDebugLoc(II->getDebugLoc());
 854       NewCall->setAttributes(II->getAttributes());
 855       II->replaceAllUsesWith(NewCall);
 856       ToErase.push_back(II);
 857
 858       IRB.CreateBr(II->getNormalDest());
 859
 860       // Remove any PHI node entries from the exception destination
 861       II->getUnwindDest()->removePredecessor(&BB);
 862     }
 863   }
 864
 865   // Process resume instructions
 866   for (BasicBlock &BB : F) {
 867     // Scan the body of the basic block for resumes
 868     for (Instruction &I : BB) {
 869       auto *RI = dyn_cast<ResumeInst>(&I);
 870       if (!RI)
 871         continue;
 872
 873       // Split the input into legal values
 874       Value *Input = RI->getValue();
 875       IRB.SetInsertPoint(RI);
 876       Value *Low = IRB.CreateExtractValue(Input, 0, "low");
 877       // Create a call to __resumeException function
 878       IRB.CreateCall(ResumeF, {Low});
 879       // Add a terminator to the block
 880       IRB.CreateUnreachable();
 881       ToErase.push_back(RI);
 882     }
 883   }
 884
 885   // Process llvm.eh.typeid.for intrinsics
 886   for (BasicBlock &BB : F) {
 887     for (Instruction &I : BB) {
 888       auto *CI = dyn_cast<CallInst>(&I);
 889       if (!CI)
 890         continue;
 891       const Function *Callee = CI->getCalledFunction();
 892       if (!Callee)
 893         continue;
 894       if (Callee->getIntrinsicID() != Intrinsic::eh_typeid_for)
 895         continue;
 896
 897       IRB.SetInsertPoint(CI);
 898       CallInst *NewCI =
 899           IRB.CreateCall(EHTypeIDF, CI->getArgOperand(0), "typeid");
 900       CI->replaceAllUsesWith(NewCI);
 901       ToErase.push_back(CI);
 902     }
 903   }
 904
 905   // Look for orphan landingpads, can occur in blocks with no predecesors
 906   for (BasicBlock &BB : F) {
 907     Instruction *I = BB.getFirstNonPHI();
 908     if (auto *LPI = dyn_cast<LandingPadInst>(I))
 909       LandingPads.insert(LPI);
 910   }
 911
 912   // Handle all the landingpad for this function together, as multiple invokes
 913   // may share a single lp
 914   for (LandingPadInst *LPI : LandingPads) {
 915     IRB.SetInsertPoint(LPI);
 916     SmallVector<Value *, 16> FMCArgs;
 917     for (unsigned i = 0, e = LPI->getNumClauses(); i < e; ++i) {
 918       Constant *Clause = LPI->getClause(i);
 919       // As a temporary workaround for the lack of aggregate varargs support
 920       // in the interface between JS and wasm, break out filter operands into
 921       // their component elements.
 922       if (LPI->isFilter(i)) {
 923         auto *ATy = cast<ArrayType>(Clause->getType());
 924         for (unsigned j = 0, e = ATy->getNumElements(); j < e; ++j) {
 925           Value *EV = IRB.CreateExtractValue(Clause, makeArrayRef(j), "filter");
 926           FMCArgs.push_back(EV);
 927         }
 928       } else
 929         FMCArgs.push_back(Clause);
 930     }
 931
 932     // Create a call to __cxa_find_matching_catch_N function
 933     Function *FMCF = getFindMatchingCatch(M, FMCArgs.size());
 934     CallInst *FMCI = IRB.CreateCall(FMCF, FMCArgs, "fmc");
 935     Value *Undef = UndefValue::get(LPI->getType());
 936     Value *Pair0 = IRB.CreateInsertValue(Undef, FMCI, 0, "pair0");
 937     Value *TempRet0 =
 938         IRB.CreateLoad(TempRet0GV, TempRet0GV->getName() + ".val");
 939     Value *Pair1 = IRB.CreateInsertValue(Pair0, TempRet0, 1, "pair1");
 940
 941     LPI->replaceAllUsesWith(Pair1);
 942     ToErase.push_back(LPI);
 943   }
 944
 945   // Erase everything we no longer need in this function
 946   for (Instruction *I : ToErase)
 947     I->eraseFromParent();
 948
 949   return Changed;
 950 }
 951
 952 bool WebAssemblyLowerEmscriptenEHSjLj::runSjLjOnFunction(Function &F) {
 953   Module &M = *F.getParent();
 954   LLVMContext &C = F.getContext();
 955   IRBuilder<> IRB(C);
 956   SmallVector<Instruction *, 64> ToErase;
 957   // Vector of %setjmpTable values
 958   std::vector<Instruction *> SetjmpTableInsts;
 959   // Vector of %setjmpTableSize values
 960   std::vector<Instruction *> SetjmpTableSizeInsts;
 961
 962   // Setjmp preparation
 963
 964   // This instruction effectively means %setjmpTableSize = 4.
 965   // We create this as an instruction intentionally, and we don't want to fold
 966   // this instruction to a constant 4, because this value will be used in
 967   // SSAUpdater.AddAvailableValue(...) later.
 968   BasicBlock &EntryBB = F.getEntryBlock();
 969   BinaryOperator *SetjmpTableSize = BinaryOperator::Create(
 970       Instruction::Add, IRB.getInt32(4), IRB.getInt32(0), "setjmpTableSize",
 971       &*EntryBB.getFirstInsertionPt());
 972   // setjmpTable = (int *) malloc(40);
 973   Instruction *SetjmpTable = CallInst::CreateMalloc(
 974       SetjmpTableSize, IRB.getInt32Ty(), IRB.getInt32Ty(), IRB.getInt32(40),
 975       nullptr, nullptr, "setjmpTable");
 976   // setjmpTable[0] = 0;
 977   IRB.SetInsertPoint(SetjmpTableSize);
 978   IRB.CreateStore(IRB.getInt32(0), SetjmpTable);
 979   SetjmpTableInsts.push_back(SetjmpTable);
 980   SetjmpTableSizeInsts.push_back(SetjmpTableSize);
 981
 982   // Setjmp transformation
 983   std::vector<PHINode *> SetjmpRetPHIs;
 984   Function *SetjmpF = M.getFunction("setjmp");
 985   for (User *U : SetjmpF->users()) {
 986     auto *CI = dyn_cast<CallInst>(U);
 987     if (!CI)
 988       report_fatal_error("Does not support indirect calls to setjmp");
 989
 990     BasicBlock *BB = CI->getParent();
 991     if (BB->getParent() != &F) // in other function
 992       continue;
 993
 994     // The tail is everything right after the call, and will be reached once
 995     // when setjmp is called, and later when longjmp returns to the setjmp
 996     BasicBlock *Tail = SplitBlock(BB, CI->getNextNode());
 997     // Add a phi to the tail, which will be the output of setjmp, which
 998     // indicates if this is the first call or a longjmp back. The phi directly
 999     // uses the right value based on where we arrive from
1000     IRB.SetInsertPoint(Tail->getFirstNonPHI());
1001     PHINode *SetjmpRet = IRB.CreatePHI(IRB.getInt32Ty(), 2, "setjmp.ret");
1002
1003     // setjmp initial call returns 0
1004     SetjmpRet->addIncoming(IRB.getInt32(0), BB);
1005     // The proper output is now this, not the setjmp call itself
1006     CI->replaceAllUsesWith(SetjmpRet);
1007     // longjmp returns to the setjmp will add themselves to this phi
1008     SetjmpRetPHIs.push_back(SetjmpRet);
1009
1010     // Fix call target
1011     // Our index in the function is our place in the array + 1 to avoid index
1012     // 0, because index 0 means the longjmp is not ours to handle.
1013     IRB.SetInsertPoint(CI);
1014     Value *Args[] = {CI->getArgOperand(0), IRB.getInt32(SetjmpRetPHIs.size()),
1015                      SetjmpTable, SetjmpTableSize};
1016     Instruction *NewSetjmpTable =
1017         IRB.CreateCall(SaveSetjmpF, Args, "setjmpTable");
1018     Instruction *NewSetjmpTableSize =
1019         IRB.CreateLoad(TempRet0GV, "setjmpTableSize");
1020     SetjmpTableInsts.push_back(NewSetjmpTable);
1021     SetjmpTableSizeInsts.push_back(NewSetjmpTableSize);
1022     ToErase.push_back(CI);
1023   }
1024
1025   // Update each call that can longjmp so it can return to a setjmp where
1026   // relevant.
1027
1028   // Because we are creating new BBs while processing and don't want to make
1029   // all these newly created BBs candidates again for longjmp processing, we
1030   // first make the vector of candidate BBs.
1031   std::vector<BasicBlock *> BBs;
1032   for (BasicBlock &BB : F)
1033     BBs.push_back(&BB);
1034
1035   // BBs.size() will change within the loop, so we query it every time
1036   for (unsigned i = 0; i < BBs.size(); i++) {
1037     BasicBlock *BB = BBs[i];
1038     for (Instruction &I : *BB) {
1039       assert(!isa<InvokeInst>(&I));
1040       auto *CI = dyn_cast<CallInst>(&I);
1041       if (!CI)
1042         continue;
1043
1044       const Value *Callee = CI->getCalledValue();
1045       if (!canLongjmp(M, Callee))
1046         continue;
1047
1048       Value *Threw = nullptr;
1049       BasicBlock *Tail;
1050       if (Callee->getName().startswith(InvokePrefix)) {
1051         // If invoke wrapper has already been generated for this call in
1052         // previous EH phase, search for the load instruction
1053         // %__THREW__.val = __THREW__;
1054         // in postamble after the invoke wrapper call
1055         LoadInst *ThrewLI = nullptr;
1056         StoreInst *ThrewResetSI = nullptr;
1057         for (auto I = std::next(BasicBlock::iterator(CI)), IE = BB->end();
1058              I != IE; ++I) {
1059           if (auto *LI = dyn_cast<LoadInst>(I))
1060             if (auto *GV = dyn_cast<GlobalVariable>(LI->getPointerOperand()))
1061               if (GV == ThrewGV) {
1062                 Threw = ThrewLI = LI;
1063                 break;
1064               }
1065         }
1066         // Search for the store instruction after the load above
1067         // __THREW__ = 0;
1068         for (auto I = std::next(BasicBlock::iterator(ThrewLI)), IE = BB->end();
1069              I != IE; ++I) {
1070           if (auto *SI = dyn_cast<StoreInst>(I))
1071             if (auto *GV = dyn_cast<GlobalVariable>(SI->getPointerOperand()))
1072               if (GV == ThrewGV && SI->getValueOperand() == IRB.getInt32(0)) {
1073                 ThrewResetSI = SI;
1074                 break;
1075               }
1076         }
1077         assert(Threw && ThrewLI && "Cannot find __THREW__ load after invoke");
1078         assert(ThrewResetSI && "Cannot find __THREW__ store after invoke");
1079         Tail = SplitBlock(BB, ThrewResetSI->getNextNode());
1080
1081       } else {
1082         // Wrap call with invoke wrapper and generate preamble/postamble
1083         Threw = wrapInvoke(CI);
1084         ToErase.push_back(CI);
1085         Tail = SplitBlock(BB, CI->getNextNode());
1086       }
1087
1088       // We need to replace the terminator in Tail - SplitBlock makes BB go
1089       // straight to Tail, we need to check if a longjmp occurred, and go to the
1090       // right setjmp-tail if so
1091       ToErase.push_back(BB->getTerminator());
1092
1093       // Generate a function call to testSetjmp function and preamble/postamble
1094       // code to figure out (1) whether longjmp occurred (2) if longjmp
1095       // occurred, which setjmp it corresponds to
1096       Value *Label = nullptr;
1097       Value *LongjmpResult = nullptr;
1098       BasicBlock *EndBB = nullptr;
1099       wrapTestSetjmp(BB, CI, Threw, SetjmpTable, SetjmpTableSize, Label,
1100                      LongjmpResult, EndBB);
1101       assert(Label && LongjmpResult && EndBB);
1102
1103       // Create switch instruction
1104       IRB.SetInsertPoint(EndBB);
1105       SwitchInst *SI = IRB.CreateSwitch(Label, Tail, SetjmpRetPHIs.size());
1106       // -1 means no longjmp happened, continue normally (will hit the default
1107       // switch case). 0 means a longjmp that is not ours to handle, needs a
1108       // rethrow. Otherwise the index is the same as the index in P+1 (to avoid
1109       // 0).
1110       for (unsigned i = 0; i < SetjmpRetPHIs.size(); i++) {
1111         SI->addCase(IRB.getInt32(i + 1), SetjmpRetPHIs[i]->getParent());
1112         SetjmpRetPHIs[i]->addIncoming(LongjmpResult, EndBB);
1113       }
1114
1115       // We are splitting the block here, and must continue to find other calls
1116       // in the block - which is now split. so continue to traverse in the Tail
1117       BBs.push_back(Tail);
1118     }
1119   }
1120
1121   // Erase everything we no longer need in this function
1122   for (Instruction *I : ToErase)
1123     I->eraseFromParent();
1124
1125   // Free setjmpTable buffer before each return instruction
1126   for (BasicBlock &BB : F) {
1127     TerminatorInst *TI = BB.getTerminator();
1128     if (isa<ReturnInst>(TI))
1129       CallInst::CreateFree(SetjmpTable, TI);
1130   }
1131
1132   // Every call to saveSetjmp can change setjmpTable and setjmpTableSize
1133   // (when buffer reallocation occurs)
1134   // entry:
1135   //   setjmpTableSize = 4;
1136   //   setjmpTable = (int *) malloc(40);
1137   //   setjmpTable[0] = 0;
1138   // ...
1139   // somebb:
1140   //   setjmpTable = saveSetjmp(buf, label, setjmpTable, setjmpTableSize);
1141   //   setjmpTableSize = __tempRet0;
1142   // So we need to make sure the SSA for these variables is valid so that every
1143   // saveSetjmp and testSetjmp calls have the correct arguments.
1144   SSAUpdater SetjmpTableSSA;
1145   SSAUpdater SetjmpTableSizeSSA;
1146   SetjmpTableSSA.Initialize(Type::getInt32PtrTy(C), "setjmpTable");
1147   SetjmpTableSizeSSA.Initialize(Type::getInt32Ty(C), "setjmpTableSize");
1148   for (Instruction *I : SetjmpTableInsts)
1149     SetjmpTableSSA.AddAvailableValue(I->getParent(), I);
1150   for (Instruction *I : SetjmpTableSizeInsts)
1151     SetjmpTableSizeSSA.AddAvailableValue(I->getParent(), I);
1152
1153   for (auto UI = SetjmpTable->use_begin(), UE = SetjmpTable->use_end();
1154        UI != UE;) {
1155     // Grab the use before incrementing the iterator.
1156     Use &U = *UI;
1157     // Increment the iterator before removing the use from the list.
1158     ++UI;
1159     if (Instruction *I = dyn_cast<Instruction>(U.getUser()))
1160       if (I->getParent() != &EntryBB)
1161         SetjmpTableSSA.RewriteUse(U);
1162   }
1163   for (auto UI = SetjmpTableSize->use_begin(), UE = SetjmpTableSize->use_end();
1164        UI != UE;) {
1165     Use &U = *UI;
1166     ++UI;
1167     if (Instruction *I = dyn_cast<Instruction>(U.getUser()))
1168       if (I->getParent() != &EntryBB)
1169         SetjmpTableSizeSSA.RewriteUse(U);
1170   }
1171
1172   // Finally, our modifications to the cfg can break dominance of SSA variables.
1173   // For example, in this code,
1174   // if (x()) { .. setjmp() .. }
1175   // if (y()) { .. longjmp() .. }
1176   // We must split the longjmp block, and it can jump into the block splitted
1177   // from setjmp one. But that means that when we split the setjmp block, it's
1178   // first part no longer dominates its second part - there is a theoretically
1179   // possible control flow path where x() is false, then y() is true and we
1180   // reach the second part of the setjmp block, without ever reaching the first
1181   // part. So, we rebuild SSA form here.
1182   rebuildSSA(F);
1183   return true;
1184 }