Add PNaClSjLjEH pass to implement C++ exception handling using setjmp()+longjmp()

There are two parts to this:

 * PNaClSjLjEH.cpp expands out the "invoke", "landingpad" and "resume"
   instructions, modifying the control flow to use setjmp().

 * ExceptionInfoWriter.cpp lowers landingpads' clause lists to data
   that PNaCl's C++ runtime library will interpret.  This part will be
   reused when we drop the SjLj part and create a stable ABI for
   zero-cost EH.

This pass isn't enabled in PNaClABISimplify yet: I'll do that in a
separate change.

BUG=https://code.google.com/p/nativeclient/issues/detail?id=3696
TEST=*.ll tests (also tested end-to-end: plumbing for this will follow later)

Review URL: https://codereview.chromium.org/24777002

9 files changed, 958 insertions, 0 deletions

diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h
index fd59d14b54..f471c55cd9 100644
--- a/include/llvm/InitializePasses.h
+++ b/include/llvm/InitializePasses.h
@@ -293,6 +293,7 @@ void initializeInsertDivideCheckPass(PassRegistry&);
 void initializeNaClCcRewritePass(PassRegistry&);
 void initializePNaClABIVerifyFunctionsPass(PassRegistry&);
 void initializePNaClABIVerifyModulePass(PassRegistry&);
+void initializePNaClSjLjEHPass(PassRegistry&);
 void initializePromoteI1OpsPass(PassRegistry&);
 void initializePromoteIntegersPass(PassRegistry&);
 void initializeRemoveAsmMemoryPass(PassRegistry&);
diff --git a/include/llvm/Transforms/NaCl.h b/include/llvm/Transforms/NaCl.h
index e1be3cf85b..ba85c592f5 100644
--- a/include/llvm/Transforms/NaCl.h
+++ b/include/llvm/Transforms/NaCl.h
@@ -41,6 +41,7 @@ ModulePass *createExpandTlsPass();
 ModulePass *createExpandVarArgsPass();
 ModulePass *createFlattenGlobalsPass();
 ModulePass *createGlobalCleanupPass();
+ModulePass *createPNaClSjLjEHPass();
 ModulePass *createReplacePtrsWithIntsPass();
 ModulePass *createResolveAliasesPass();
 ModulePass *createRewriteAtomicsPass();
diff --git a/lib/Transforms/NaCl/CMakeLists.txt b/lib/Transforms/NaCl/CMakeLists.txt
index 014d322d55..f57558a1e7 100644
--- a/lib/Transforms/NaCl/CMakeLists.txt
+++ b/lib/Transforms/NaCl/CMakeLists.txt
@@ -1,6 +1,7 @@
 add_llvm_library(LLVMNaClTransforms
   AddPNaClExternalDecls.cpp
   CanonicalizeMemIntrinsics.cpp
+  ExceptionInfoWriter.cpp
   ExpandArithWithOverflow.cpp
   ExpandByVal.cpp
   ExpandConstantExpr.cpp
@@ -16,6 +17,7 @@ add_llvm_library(LLVMNaClTransforms
   GlobalCleanup.cpp
   InsertDivideCheck.cpp
   PNaClABISimplify.cpp
+  PNaClSjLjEH.cpp
   PromoteI1Ops.cpp
   PromoteIntegers.cpp
   RemoveAsmMemory.cpp
diff --git a/lib/Transforms/NaCl/ExceptionInfoWriter.cpp b/lib/Transforms/NaCl/ExceptionInfoWriter.cpp
new file mode 100644
index 0000000000..7fbf5245c4
--- /dev/null
+++ b/lib/Transforms/NaCl/ExceptionInfoWriter.cpp
@@ -0,0 +1,281 @@
+//===- ExceptionInfoWriter.cpp - Generate C++ exception info for PNaCl-----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The ExceptionInfoWriter class converts the clauses of a
+// "landingpad" instruction into data tables stored in global
+// variables.  These tables are interpreted by PNaCl's C++ runtime
+// library (either libsupc++ or libcxxabi), which is linked into a
+// pexe.
+//
+// This is similar to the lowering that the LLVM backend does to
+// convert landingpad clauses into ".gcc_except_table" sections.  The
+// difference is that ExceptionInfoWriter is an IR-to-IR
+// transformation that runs on the PNaCl user toolchain side.  The
+// format it produces is not part of PNaCl's stable ABI; the PNaCl
+// translator and LLVM backend do not know about this format.
+//
+// Encoding:
+//
+// A landingpad instruction contains a list of clauses.
+// ExceptionInfoWriter encodes each clause as a 32-bit "clause ID".  A
+// clause is one of the following forms:
+//
+//  1) "catch i8* @ExcType"
+//     * This clause means that the landingpad should be entered if
+//       the C++ exception being thrown has type @ExcType (or a
+//       subtype of @ExcType).  @ExcType is a pointer to the
+//       std::type_info object (an RTTI object) for the C++ exception
+//       type.
+//     * Clang generates this for a "catch" block in the C++ source.
+//     * @ExcType is NULL for "catch (...)" (catch-all) blocks.
+//     * This is encoded as the integer "type ID" @ExcType, X,
+//       such that: __pnacl_eh_type_table[X] == @ExcType, and X >= 0.
+//
+//  2) "filter [i8* @ExcType1, ..., i8* @ExcTypeN]"
+//     * This clause means that the landingpad should be entered if
+//       the C++ exception being thrown *doesn't* match any of the
+//       types in the list (which are again specified as
+//       std::type_info pointers).
+//     * Clang uses this to implement C++ exception specifications, e.g.
+//          void foo() throw(ExcType1, ..., ExcTypeN) { ... }
+//     * This is encoded as the filter ID, X, where X < 0, and
+//       &__pnacl_eh_filter_table[-X-1] points to a -1-terminated
+//       array of integer "type IDs".
+//
+//  3) "cleanup"
+//     * This means that the landingpad should always be entered.
+//     * Clang uses this for calling objects' destructors.
+//     * ExceptionInfoWriter encodes this the same as "catch i8* null"
+//       (which is a catch-all).
+//
+// ExceptionInfoWriter generates the following data structures:
+//
+//   struct action_table_entry {
+//     int32_t clause_id;
+//     uint32_t next_clause_list_id;
+//   };
+//
+//   // Represents singly linked lists of clauses.
+//   extern const struct action_table_entry __pnacl_eh_action_table[];
+//
+//   // Allows std::type_infos to be represented using small integer IDs.
+//   extern std::type_info *const __pnacl_eh_type_table[];
+//
+//   // Used to represent type arrays for "filter" clauses.
+//   extern const int32_t __pnacl_eh_filter_table[];
+//
+// A "clause list ID" is either:
+//  * 0, representing the empty list; or
+//  * an index into __pnacl_eh_action_table[] with 1 added, which
+//    specifies a node in the clause list.
+//
+// Example:
+//
+//   std::type_info *const __pnacl_eh_type_table[] = {
+//     // defines type ID 0 == ExcA and clause ID 0 == "catch ExcA"
+//     &typeinfo(ExcA),
+//     // defines type ID 1 == ExcB and clause ID 1 == "catch ExcB"
+//     &typeinfo(ExcB),
+//     // defines type ID 2 == ExcC and clause ID 2 == "catch ExcC"
+//     &typeinfo(ExcC),
+//   };
+//
+//   const int32_t __pnacl_eh_filter_table[] = {
+//     0,   // refers to ExcA;  defines clause ID -1 as "filter [ExcA, ExcB]"
+//     1,   // refers to ExcB;  defines clause ID -2 as "filter [ExcB]"
+//     -1,  // list terminator; defines clause ID -3 as "filter []"
+//     2,   // refers to ExcC;  defines clause ID -4 as "filter [ExcC]"
+//     -1,  // list terminator; defines clause ID -5 as "filter []"
+//   };
+//
+//   const struct action_table_entry __pnacl_eh_action_table[] = {
+//     // defines clause list ID 1:
+//     {
+//       -4,  // "filter [ExcC]"
+//       0,  // end of list (no more actions)
+//     },
+//     // defines clause list ID 2:
+//     {
+//       -1,  // "filter [ExcA, ExcB]"
+//       1,  // else go to clause list ID 1
+//     },
+//     // defines clause list ID 3:
+//     {
+//       1,  // "catch ExcB"
+//       2,  // else go to clause list ID 2
+//     },
+//     // defines clause list ID 4:
+//     {
+//       0,  // "catch ExcA"
+//       3,  // else go to clause list ID 3
+//     },
+//   };
+//
+// So if a landingpad contains the clause list:
+//   [catch ExcA,
+//    catch ExcB,
+//    filter [ExcA, ExcB],
+//    filter [ExcC]]
+// then this can be represented as clause list ID 4 using the tables above.
+//
+// The C++ runtime library checks the clauses in order to decide
+// whether to enter the landingpad.  If a clause matches, the
+// landingpad BasicBlock is passed the clause ID.  The landingpad code
+// can use the clause ID to decide which C++ catch() block (if any) to
+// execute.
+//
+// The purpose of these exception tables is to keep code sizes
+// relatively small.  The landingpad code only needs to check a small
+// integer clause ID, rather than having to call a function to check
+// whether the C++ exception matches a type.
+//
+// ExceptionInfoWriter's encoding corresponds loosely to the format of
+// GCC's .gcc_except_table sections.  One difference is that
+// ExceptionInfoWriter writes fixed-width 32-bit integers, whereas
+// .gcc_except_table uses variable-length LEB128 encodings.  We could
+// switch to LEB128 to save space in the future.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ExceptionInfoWriter.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+ExceptionInfoWriter::ExceptionInfoWriter(LLVMContext *Context):
+    Context(Context) {
+  Type *I32 = Type::getInt32Ty(*Context);
+  Type *Fields[] = { I32, I32 };
+  ActionTableEntryTy = StructType::create(Fields, "action_table_entry");
+}
+
+unsigned ExceptionInfoWriter::getIDForExceptionType(Value *ExcTy) {
+  Constant *ExcTyConst = dyn_cast<Constant>(ExcTy);
+  if (!ExcTyConst)
+    report_fatal_error("Exception type not a constant");
+
+  // Reuse existing ID if one has already been assigned.
+  TypeTableIDMapType::iterator Iter = TypeTableIDMap.find(ExcTyConst);
+  if (Iter != TypeTableIDMap.end())
+    return Iter->second;
+
+  unsigned Index = TypeTableData.size();
+  TypeTableIDMap[ExcTyConst] = Index;
+  TypeTableData.push_back(ExcTyConst);
+  return Index;
+}
+
+unsigned ExceptionInfoWriter::getIDForClauseListNode(
+    unsigned ClauseID, unsigned NextClauseListID) {
+  // Reuse existing ID if one has already been assigned.
+  ActionTableEntry Key(ClauseID, NextClauseListID);
+  ActionTableIDMapType::iterator Iter = ActionTableIDMap.find(Key);
+  if (Iter != ActionTableIDMap.end())
+    return Iter->second;
+
+  Type *I32 = Type::getInt32Ty(*Context);
+  Constant *Fields[] = { ConstantInt::get(I32, ClauseID),
+                         ConstantInt::get(I32, NextClauseListID) };
+  Constant *Entry = ConstantStruct::get(ActionTableEntryTy, Fields);
+
+  // Add 1 so that the empty list can be represented as 0.
+  unsigned ClauseListID = ActionTableData.size() + 1;
+  ActionTableIDMap[Key] = ClauseListID;
+  ActionTableData.push_back(Entry);
+  return ClauseListID;
+}
+
+unsigned ExceptionInfoWriter::getIDForFilterClause(Value *Filter) {
+  unsigned FilterClauseID = -(FilterTableData.size() + 1);
+  Type *I32 = Type::getInt32Ty(*Context);
+  ArrayType *ArrayTy = dyn_cast<ArrayType>(Filter->getType());
+  if (!ArrayTy)
+    report_fatal_error("Landingpad filter clause is not of array type");
+  unsigned FilterLength = ArrayTy->getNumElements();
+  // Don't try the dyn_cast if the FilterLength is zero, because Array
+  // could be a zeroinitializer.
+  if (FilterLength > 0) {
+    ConstantArray *Array = dyn_cast<ConstantArray>(Filter);
+    if (!Array)
+      report_fatal_error("Landingpad filter clause is not a ConstantArray");
+    for (unsigned I = 0; I < FilterLength; ++I) {
+      unsigned TypeID = getIDForExceptionType(Array->getOperand(I));
+      FilterTableData.push_back(ConstantInt::get(I32, TypeID));
+    }
+  }
+  // Add array terminator.
+  FilterTableData.push_back(ConstantInt::get(I32, -1));
+  return FilterClauseID;
+}
+
+unsigned ExceptionInfoWriter::getIDForLandingPadClauseList(LandingPadInst *LP) {
+  unsigned NextClauseListID = 0;  // ID for empty list.
+
+  if (LP->isCleanup()) {
+    // Add catch-all entry.  There doesn't appear to be any need to
+    // treat "cleanup" differently from a catch-all.
+    unsigned TypeID = getIDForExceptionType(
+        ConstantPointerNull::get(Type::getInt8PtrTy(*Context)));
+    NextClauseListID = getIDForClauseListNode(TypeID, NextClauseListID);
+  }
+
+  for (int I = (int) LP->getNumClauses() - 1; I >= 0; --I) {
+    unsigned ClauseID;
+    if (LP->isCatch(I)) {
+      ClauseID = getIDForExceptionType(LP->getClause(I));
+    } else if (LP->isFilter(I)) {
+      ClauseID = getIDForFilterClause(LP->getClause(I));
+    } else {
+      report_fatal_error("Unknown kind of landingpad clause");
+    }
+    NextClauseListID = getIDForClauseListNode(ClauseID, NextClauseListID);
+  }
+
+  return NextClauseListID;
+}
+
+static void defineArray(Module *M, const char *Name,
+                        const SmallVectorImpl<Constant *> &Elements,
+                        Type *ElementType) {
+  ArrayType *ArrayTy = ArrayType::get(ElementType, Elements.size());
+  Constant *ArrayData = ConstantArray::get(ArrayTy, Elements);
+  GlobalVariable *OldGlobal = M->getGlobalVariable(Name);
+  if (OldGlobal) {
+    if (OldGlobal->hasInitializer()) {
+      report_fatal_error(std::string("Variable ") + Name +
+                         " already has an initializer");
+    }
+    Constant *NewGlobal = new GlobalVariable(
+        *M, ArrayTy, /* isConstant= */ true,
+        GlobalValue::InternalLinkage, ArrayData);
+    NewGlobal->takeName(OldGlobal);
+    OldGlobal->replaceAllUsesWith(ConstantExpr::getBitCast(
+                                      NewGlobal, OldGlobal->getType()));
+    OldGlobal->eraseFromParent();
+  } else {
+    if (Elements.size() > 0) {
+      // This warning could happen for a program that does not link
+      // against the C++ runtime libraries.  Such a program might
+      // contain "invoke" instructions but never throw any C++
+      // exceptions.
+      errs() << "Warning: Variable " << Name << " not referenced\n";
+    }
+  }
+}
+
+void ExceptionInfoWriter::defineGlobalVariables(Module *M) {
+  defineArray(M, "__pnacl_eh_type_table", TypeTableData,
+              Type::getInt8PtrTy(M->getContext()));
+
+  defineArray(M, "__pnacl_eh_action_table", ActionTableData,
+              ActionTableEntryTy);
+
+  defineArray(M, "__pnacl_eh_filter_table", FilterTableData,
+              Type::getInt32Ty(M->getContext()));
+}
diff --git a/lib/Transforms/NaCl/ExceptionInfoWriter.h b/lib/Transforms/NaCl/ExceptionInfoWriter.h
new file mode 100644
index 0000000000..dadaaf7615
--- /dev/null
+++ b/lib/Transforms/NaCl/ExceptionInfoWriter.h
@@ -0,0 +1,71 @@
+//===-- ExceptionInfoWriter.h - Generate C++ exception info------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef TRANSFORMS_NACL_EXCEPTIONINFOWRITER_H
+#define TRANSFORMS_NACL_EXCEPTIONINFOWRITER_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+
+namespace llvm {
+
+// The ExceptionInfoWriter class converts the clauses of a
+// "landingpad" instruction into data tables stored in global
+// variables, which are interpreted by PNaCl's C++ runtime library.
+// See ExceptionInfoWriter.cpp for a full description.
+class ExceptionInfoWriter {
+  LLVMContext *Context;
+  StructType *ActionTableEntryTy;
+
+  // Data for populating __pnacl_eh_type_table[], which is an array of
+  // std::type_info* pointers.  Each of these pointers represents a
+  // C++ exception type.
+  SmallVector<Constant *, 10> TypeTableData;
+  // Mapping from std::type_info* pointer to type ID (index in
+  // TypeTableData).
+  typedef DenseMap<Constant *, unsigned> TypeTableIDMapType;
+  TypeTableIDMapType TypeTableIDMap;
+
+  // Data for populating __pnacl_eh_action_table[], which is an array
+  // of pairs.
+  SmallVector<Constant *, 10> ActionTableData;
+  // Pair of (clause_id, clause_list_id).
+  typedef std::pair<unsigned, unsigned> ActionTableEntry;
+  // Mapping from (clause_id, clause_list_id) to clause_id (index in
+  // ActionTableData).
+  typedef DenseMap<ActionTableEntry, unsigned> ActionTableIDMapType;
+  ActionTableIDMapType ActionTableIDMap;
+
+  // Data for populating __pnacl_eh_filter_table[], which is an array
+  // of integers.
+  SmallVector<Constant *, 10> FilterTableData;
+
+  // Get the interned ID for an action.
+  unsigned getIDForClauseListNode(unsigned ClauseID, unsigned NextClauseListID);
+
+  // Get the clause ID for a "filter" clause.
+  unsigned getIDForFilterClause(Value *Filter);
+
+public:
+  explicit ExceptionInfoWriter(LLVMContext *Context);
+
+  // Get the interned type ID (a small integer) for a C++ exception type.
+  unsigned getIDForExceptionType(Value *Ty);
+
+  // Get the clause list ID for a landingpad's clause list.
+  unsigned getIDForLandingPadClauseList(LandingPadInst *LP);
+
+  // Add the exception info tables to the module.
+  void defineGlobalVariables(Module *M);
+};
+
+}
+
+#endif
diff --git a/lib/Transforms/NaCl/PNaClSjLjEH.cpp b/lib/Transforms/NaCl/PNaClSjLjEH.cpp
new file mode 100644
index 0000000000..d3da681a81
--- /dev/null
+++ b/lib/Transforms/NaCl/PNaClSjLjEH.cpp
@@ -0,0 +1,346 @@
+//===- PNaClSjLjEH.cpp - Lower C++ exception handling to use setjmp()------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The PNaClSjLjEH pass is part of an implementation of C++ exception
+// handling for PNaCl that uses setjmp() and longjmp() to handle C++
+// exceptions.  The pass lowers LLVM "invoke" instructions to use
+// setjmp().
+//
+// For example, consider the following C++ code fragment:
+//
+//   int catcher_func() {
+//     try {
+//       int result = external_func();
+//       return result + 100;
+//     } catch (MyException &exc) {
+//       return exc.value + 200;
+//     }
+//   }
+//
+// PNaClSjLjEH converts the IR for that function to the following
+// pseudo-code:
+//
+//   struct LandingPadResult {
+//     void *exception_obj;  // For passing to __cxa_begin_catch()
+//     int matched_clause_id;  // See ExceptionInfoWriter.cpp
+//   };
+//
+//   struct ExceptionFrame {
+//     union {
+//       jmp_buf jmpbuf;  // Context for jumping to landingpad block
+//       struct LandingPadResult result;  // Data returned to landingpad block
+//     };
+//     struct ExceptionFrame *next;  // Next frame in linked list
+//     int clause_list_id;  // Reference to landingpad's exception info
+//   };
+//
+//   // Thread-local exception state
+//   __thread struct ExceptionFrame *__pnacl_eh_stack;
+//
+//   int catcher_func() {
+//     struct ExceptionFrame frame;
+//     int result;
+//     if (!setjmp(&frame.jmpbuf)) {  // Save context
+//       frame.next = __pnacl_eh_stack;
+//       frame.clause_list_id = 123;
+//       __pnacl_eh_stack = &frame;  // Add frame to stack
+//       result = external_func();
+//       __pnacl_eh_stack = frame.next;  // Remove frame from stack
+//     } else {
+//       // Handle exception.  This is a simplification.  Real code would
+//       // call __cxa_begin_catch() to extract the thrown object.
+//       MyException &exc = *(MyException *) frame.result.exception_obj;
+//       return exc.value + 200;
+//     }
+//     return result + 100;
+//   }
+//
+// The pass makes the following changes to IR:
+//
+//  * Convert "invoke" and "landingpad" instructions.
+//  * Convert "resume" instructions into __pnacl_eh_resume() calls.
+//  * Replace each call to llvm.eh.typeid.for() with an integer
+//    constant representing the exception type.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/NaCl.h"
+#include "ExceptionInfoWriter.h"
+
+using namespace llvm;
+
+namespace {
+  // This is a ModulePass so that it can introduce new global variables.
+  class PNaClSjLjEH : public ModulePass {
+  public:
+    static char ID; // Pass identification, replacement for typeid
+    PNaClSjLjEH() : ModulePass(ID) {
+      initializePNaClSjLjEHPass(*PassRegistry::getPassRegistry());
+    }
+
+    virtual bool runOnModule(Module &M);
+  };
+
+  class FuncRewriter {
+    Type *ExceptionFrameTy;
+    ExceptionInfoWriter *ExcInfoWriter;
+    Function *Func;
+
+    // FrameInitialized indicates whether the following variables have
+    // been initialized.
+    bool FrameInitialized;
+    Function *SetjmpIntrinsic;  // setjmp() intrinsic function
+    Instruction *EHStackTlsVar;  // Bitcast of thread-local __pnacl_eh_stack var
+    Instruction *Frame;  // Frame allocated for this function
+    Instruction *FrameJmpBuf;  // Frame's jmp_buf field
+    Instruction *FrameNextPtr;  // Frame's next field
+    Instruction *FrameExcInfo;  // Frame's clause_list_id field
+
+    Function *EHResumeFunc;  // __pnacl_eh_resume() function
+
+    // Initialize values that are shared across all "invoke"
+    // instructions within the function.
+    void initializeFrame();
+
+  public:
+    FuncRewriter(Type *ExceptionFrameTy, ExceptionInfoWriter *ExcInfoWriter,
+                 Function *Func):
+        ExceptionFrameTy(ExceptionFrameTy),
+        ExcInfoWriter(ExcInfoWriter),
+        Func(Func),
+        FrameInitialized(false),
+        SetjmpIntrinsic(NULL), EHStackTlsVar(NULL),
+        Frame(NULL), FrameJmpBuf(NULL), FrameNextPtr(NULL), FrameExcInfo(NULL),
+        EHResumeFunc(NULL) {}
+
+    void expandInvokeInst(InvokeInst *Invoke);
+    void expandResumeInst(ResumeInst *Resume);
+    void expandFunc();
+  };
+}
+
+char PNaClSjLjEH::ID = 0;
+INITIALIZE_PASS(PNaClSjLjEH, "pnacl-sjlj-eh",
+                "Lower C++ exception handling to use setjmp()",
+                false, false)
+
+static const int kPNaClJmpBufSize = 1024;
+static const int kPNaClJmpBufAlign = 8;
+
+void FuncRewriter::initializeFrame() {
+  if (FrameInitialized)
+    return;
+  FrameInitialized = true;
+  Module *M = Func->getParent();
+
+  SetjmpIntrinsic = Intrinsic::getDeclaration(M, Intrinsic::nacl_setjmp);
+
+  Value *EHStackTlsVarUncast = M->getGlobalVariable("__pnacl_eh_stack");
+  if (!EHStackTlsVarUncast)
+    report_fatal_error("__pnacl_eh_stack not defined");
+  EHStackTlsVar = new BitCastInst(
+      EHStackTlsVarUncast, ExceptionFrameTy->getPointerTo()->getPointerTo(),
+      "pnacl_eh_stack");
+  Func->getEntryBlock().getInstList().push_front(EHStackTlsVar);
+
+  // Allocate the new exception frame.  This is reused across all
+  // invoke instructions in the function.
+  Type *I32 = Type::getInt32Ty(M->getContext());
+  Frame = new AllocaInst(ExceptionFrameTy, ConstantInt::get(I32, 1),
+                         kPNaClJmpBufAlign, "invoke_frame");
+  Func->getEntryBlock().getInstList().push_front(Frame);
+
+  // Calculate addresses of fields in the exception frame.
+  Value *JmpBufIndexes[] = { ConstantInt::get(I32, 0),
+                             ConstantInt::get(I32, 0),
+                             ConstantInt::get(I32, 0) };
+  FrameJmpBuf = GetElementPtrInst::Create(Frame, JmpBufIndexes,
+                                          "invoke_jmp_buf");
+  FrameJmpBuf->insertAfter(Frame);
+
+  Value *NextPtrIndexes[] = { ConstantInt::get(I32, 0),
+                              ConstantInt::get(I32, 1) };
+  FrameNextPtr = GetElementPtrInst::Create(Frame, NextPtrIndexes,
+                                           "invoke_next");
+  FrameNextPtr->insertAfter(Frame);
+
+  Value *ExcInfoIndexes[] = { ConstantInt::get(I32, 0),
+                              ConstantInt::get(I32, 2) };
+  FrameExcInfo = GetElementPtrInst::Create(Frame, ExcInfoIndexes,
+                                           "exc_info_ptr");
+  FrameExcInfo->insertAfter(Frame);
+}
+
+static void updateEdge(BasicBlock *Dest,
+                       BasicBlock *OldIncoming,
+                       BasicBlock *NewIncoming) {
+  for (BasicBlock::iterator Inst = Dest->begin(); Inst != Dest->end(); ++Inst) {
+    PHINode *Phi = dyn_cast<PHINode>(Inst);
+    if (!Phi)
+      break;
+    for (unsigned I = 0, E = Phi->getNumIncomingValues(); I < E; ++I) {
+      if (Phi->getIncomingBlock(I) == OldIncoming)
+        Phi->setIncomingBlock(I, NewIncoming);
+    }
+  }
+}
+
+void FuncRewriter::expandInvokeInst(InvokeInst *Invoke) {
+  initializeFrame();
+
+  LandingPadInst *LP = Invoke->getLandingPadInst();
+  Type *I32 = Type::getInt32Ty(Func->getContext());
+  Value *ExcInfo = ConstantInt::get(
+      I32, ExcInfoWriter->getIDForLandingPadClauseList(LP));
+
+  // Create setjmp() call.
+  Value *SetjmpArgs[] = { FrameJmpBuf };
+  Value *SetjmpCall = CopyDebug(CallInst::Create(SetjmpIntrinsic, SetjmpArgs,
+                                                 "invoke_sj", Invoke), Invoke);
+  // Check setjmp()'s result.
+  Value *IsZero = CopyDebug(new ICmpInst(Invoke, CmpInst::ICMP_EQ, SetjmpCall,
+                                         ConstantInt::get(I32, 0),
+                                         "invoke_sj_is_zero"), Invoke);
+
+  BasicBlock *CallBB = BasicBlock::Create(Func->getContext(), "invoke_do_call",
+                                          Func);
+  CallBB->moveAfter(Invoke->getParent());
+
+  // Append the new frame to the list.
+  Value *OldList = CopyDebug(
+      new LoadInst(EHStackTlsVar, "old_eh_stack", CallBB), Invoke);
+  CopyDebug(new StoreInst(OldList, FrameNextPtr, CallBB), Invoke);
+  CopyDebug(new StoreInst(ExcInfo, FrameExcInfo, CallBB), Invoke);
+  CopyDebug(new StoreInst(Frame, EHStackTlsVar, CallBB), Invoke);
+
+  SmallVector<Value *, 10> CallArgs;
+  for (unsigned I = 0, E = Invoke->getNumArgOperands(); I < E; ++I)
+    CallArgs.push_back(Invoke->getArgOperand(I));
+  CallInst *NewCall = CallInst::Create(Invoke->getCalledValue(), CallArgs, "",
+                                       CallBB);
+  CopyDebug(NewCall, Invoke);
+  NewCall->takeName(Invoke);
+  NewCall->setAttributes(Invoke->getAttributes());
+  NewCall->setCallingConv(Invoke->getCallingConv());
+  // Restore the old frame list.  We only need to do this on the
+  // non-exception code path.  If an exception is raised, the frame
+  // list state will be restored for us.
+  CopyDebug(new StoreInst(OldList, EHStackTlsVar, CallBB), Invoke);
+
+  CopyDebug(BranchInst::Create(CallBB, Invoke->getUnwindDest(), IsZero, Invoke),
+            Invoke);
+  CopyDebug(BranchInst::Create(Invoke->getNormalDest(), CallBB), Invoke);
+
+  updateEdge(Invoke->getNormalDest(), Invoke->getParent(), CallBB);
+
+  Invoke->replaceAllUsesWith(NewCall);
+  Invoke->eraseFromParent();
+}
+
+void FuncRewriter::expandResumeInst(ResumeInst *Resume) {
+  if (!EHResumeFunc) {
+    EHResumeFunc = Func->getParent()->getFunction("__pnacl_eh_resume");
+    if (!EHResumeFunc)
+      report_fatal_error("__pnacl_eh_resume() not defined");
+  }
+
+  // The "resume" instruction gets passed the landingpad's full result
+  // (struct LandingPadResult above).  Extract the exception_obj field
+  // to pass to __pnacl_eh_resume(), which doesn't need the
+  // matched_clause_id field.
+  unsigned Indexes[] = { 0 };
+  Value *ExceptionPtr =
+      CopyDebug(ExtractValueInst::Create(Resume->getValue(), Indexes,
+                                         "resume_exc", Resume), Resume);
+
+  // Cast to the pointer type that __pnacl_eh_resume() expects.
+  if (EHResumeFunc->getFunctionType()->getFunctionNumParams() != 1)
+    report_fatal_error("Bad type for __pnacl_eh_resume()");
+  Type *ArgType = EHResumeFunc->getFunctionType()->getFunctionParamType(0);
+  ExceptionPtr = new BitCastInst(ExceptionPtr, ArgType, "resume_cast", Resume);
+
+  Value *Args[] = { ExceptionPtr };
+  CopyDebug(CallInst::Create(EHResumeFunc, Args, "", Resume), Resume);
+  new UnreachableInst(Func->getContext(), Resume);
+  Resume->eraseFromParent();
+}
+
+void FuncRewriter::expandFunc() {
+  Type *I32 = Type::getInt32Ty(Func->getContext());
+
+  // We need to do two passes: When we process an invoke we need to
+  // look at its landingpad, so we can't remove the landingpads until
+  // all the invokes have been processed.
+  for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB) {
+    for (BasicBlock::iterator Iter = BB->begin(), E = BB->end(); Iter != E; ) {
+      Instruction *Inst = Iter++;
+      if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Inst)) {
+        expandInvokeInst(Invoke);
+      } else if (ResumeInst *Resume = dyn_cast<ResumeInst>(Inst)) {
+        expandResumeInst(Resume);
+      } else if (IntrinsicInst *Intrinsic = dyn_cast<IntrinsicInst>(Inst)) {
+        if (Intrinsic->getIntrinsicID() == Intrinsic::eh_typeid_for) {
+          Value *ExcType = Intrinsic->getArgOperand(0);
+          Value *Val = ConstantInt::get(
+              I32, ExcInfoWriter->getIDForExceptionType(ExcType));
+          Intrinsic->replaceAllUsesWith(Val);
+          Intrinsic->eraseFromParent();
+        }
+      }
+    }
+  }
+  for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB) {
+    for (BasicBlock::iterator Iter = BB->begin(), E = BB->end(); Iter != E; ) {
+      Instruction *Inst = Iter++;
+      if (LandingPadInst *LP = dyn_cast<LandingPadInst>(Inst)) {
+        initializeFrame();
+        Value *LPPtr = new BitCastInst(
+            FrameJmpBuf, LP->getType()->getPointerTo(), "landingpad_ptr", LP);
+        Value *LPVal = CopyDebug(new LoadInst(LPPtr, "", LP), LP);
+        LPVal->takeName(LP);
+        LP->replaceAllUsesWith(LPVal);
+        LP->eraseFromParent();
+      }
+    }
+  }
+}
+
+bool PNaClSjLjEH::runOnModule(Module &M) {
+  Type *JmpBufTy = ArrayType::get(Type::getInt8Ty(M.getContext()),
+                                  kPNaClJmpBufSize);
+
+  // Define "struct ExceptionFrame".
+  StructType *ExceptionFrameTy = StructType::create(M.getContext(),
+                                                    "ExceptionFrame");
+  Type *ExceptionFrameFields[] = {
+    JmpBufTy,  // jmp_buf
+    ExceptionFrameTy->getPointerTo(),  // struct ExceptionFrame *next
+    Type::getInt32Ty(M.getContext())  // Exception info (clause list ID)
+  };
+  ExceptionFrameTy->setBody(ExceptionFrameFields);
+
+  ExceptionInfoWriter ExcInfoWriter(&M.getContext());
+  for (Module::iterator Func = M.begin(), E = M.end(); Func != E; ++Func) {
+    FuncRewriter Rewriter(ExceptionFrameTy, &ExcInfoWriter, Func);
+    Rewriter.expandFunc();
+  }
+  ExcInfoWriter.defineGlobalVariables(&M);
+  return true;
+}
+
+ModulePass *llvm::createPNaClSjLjEHPass() {
+  return new PNaClSjLjEH();
+}
diff --git a/test/Transforms/NaCl/pnacl-eh-exception-info.ll b/test/Transforms/NaCl/pnacl-eh-exception-info.ll
new file mode 100644
index 0000000000..a330f6f5ac
--- /dev/null
+++ b/test/Transforms/NaCl/pnacl-eh-exception-info.ll
@@ -0,0 +1,128 @@
+; RUN: opt %s -pnacl-sjlj-eh -S | FileCheck %s
+
+; Example std::type_info objects.
+@exc_typeid1 = external global i8
+@exc_typeid2 = external global i8
+@exc_typeid3 = external global i8
+
+; This must be declared for "-pnacl-sjlj-eh" to work.
+@__pnacl_eh_stack = external thread_local global i8*
+
+declare i32 @llvm.eh.typeid.for(i8*)
+
+declare void @external_func()
+
+
+@__pnacl_eh_type_table = external global i8*
+@__pnacl_eh_action_table = external global i8*
+@__pnacl_eh_filter_table = external global i8*
+
+; CHECK: %action_table_entry = type { i32, i32 }
+
+; CHECK: @__pnacl_eh_type_table = internal constant [4 x i8*] [i8* @exc_typeid1, i8* @exc_typeid2, i8* @exc_typeid3, i8* null]
+
+; CHECK: @__pnacl_eh_action_table = internal constant [6 x %action_table_entry] [%action_table_entry { i32 2, i32 0 }, %action_table_entry { i32 1, i32 1 }, %action_table_entry { i32 0, i32 2 }, %action_table_entry { i32 -1, i32 0 }, %action_table_entry { i32 -2, i32 0 }, %action_table_entry { i32 3, i32 0 }]
+
+; CHECK: @__pnacl_eh_filter_table = internal constant [5 x i32] [i32 -1, i32 1, i32 2, i32 0, i32 -1]
+
+
+; Exception type pointers are allocated IDs which specify the index
+; into __pnacl_eh_type_table where the type may be found.
+define void @test_eh_typeid(i32 %arg) {
+  %id1 = call i32 @llvm.eh.typeid.for(i8* @exc_typeid1)
+  %id2 = call i32 @llvm.eh.typeid.for(i8* @exc_typeid2)
+  %id3 = call i32 @llvm.eh.typeid.for(i8* @exc_typeid3)
+  %cmp1 = icmp eq i32 %arg, %id1
+  %cmp2 = icmp eq i32 %arg, %id2
+  %cmp3 = icmp eq i32 %arg, %id3
+  ret void
+}
+; CHECK: define void @test_eh_typeid
+; CHECK-NEXT: %cmp1 = icmp eq i32 %arg, 0
+; CHECK-NEXT: %cmp2 = icmp eq i32 %arg, 1
+; CHECK-NEXT: %cmp3 = icmp eq i32 %arg, 2
+; CHECK-NEXT: ret void
+
+
+define void @test_single_catch_clause() {
+  invoke void @external_func() to label %cont unwind label %lpad
+cont:
+  ret void
+lpad:
+  landingpad i32 personality i8* null
+      catch i8* @exc_typeid3
+  ret void
+}
+; CHECK: define void @test_single_catch_clause
+; CHECK: store i32 1, i32* %exc_info_ptr
+
+
+define void @test_multiple_catch_clauses() {
+  invoke void @external_func() to label %cont unwind label %lpad
+cont:
+  ret void
+lpad:
+  landingpad i32 personality i8* null
+      catch i8* @exc_typeid1
+      catch i8* @exc_typeid2
+      catch i8* @exc_typeid3
+  ret void
+}
+; CHECK: define void @test_multiple_catch_clauses
+; CHECK: store i32 3, i32* %exc_info_ptr
+
+
+define void @test_empty_filter_clause() {
+  invoke void @external_func() to label %cont unwind label %lpad
+cont:
+  ret void
+lpad:
+  landingpad i32 personality i8* null
+      filter [0 x i8*] []
+  ret void
+}
+; CHECK: define void @test_empty_filter_clause
+; CHECK: store i32 4, i32* %exc_info_ptr
+
+
+define void @test_filter_clause() {
+  invoke void @external_func() to label %cont unwind label %lpad
+cont:
+  ret void
+lpad:
+  landingpad i32 personality i8* null
+      filter [3 x i8*] [i8* @exc_typeid2,
+                        i8* @exc_typeid3,
+                        i8* @exc_typeid1]
+  ret void
+}
+; CHECK: define void @test_filter_clause
+; CHECK: store i32 5, i32* %exc_info_ptr
+
+
+; "catch i8* null" means that any C++ exception matches.
+define void @test_catch_all_clause() {
+  invoke void @external_func() to label %cont unwind label %lpad
+cont:
+  ret void
+lpad:
+  landingpad i32 personality i8* null
+      catch i8* null
+  ret void
+}
+; CHECK: define void @test_catch_all_clause
+; CHECK: store i32 6, i32* %exc_info_ptr
+
+
+; "cleanup" is treated the same as "catch i8* null".
+define void @test_cleanup_clause() {
+  invoke void @external_func() to label %cont unwind label %lpad
+cont:
+  ret void
+lpad:
+  landingpad i32 personality i8* null
+      cleanup
+  ret void
+}
+; CHECK: define void @test_cleanup_clause
+; CHECK: store i32 6, i32* %exc_info_ptr
diff --git a/test/Transforms/NaCl/pnacl-sjlj-eh.ll b/test/Transforms/NaCl/pnacl-sjlj-eh.ll
new file mode 100644
index 0000000000..3783b08a5e
--- /dev/null
+++ b/test/Transforms/NaCl/pnacl-sjlj-eh.ll
@@ -0,0 +1,127 @@
+; RUN: opt %s -pnacl-sjlj-eh -S | FileCheck %s
+
+; This must be declared for expanding "invoke" and "landingpad" in