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

1 files changed, 281 insertions, 0 deletions

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()));
+}