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

lib/Transforms/NaCl/ExceptionInfoWriter.cpp

Index: lib/Transforms/NaCl/ExceptionInfoWriter.cpp
diff --git a/lib/Transforms/NaCl/ExceptionInfoWriter.cpp b/lib/Transforms/NaCl/ExceptionInfoWriter.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..77757608dc082e89bf0093f72d1b41ce05921a24
--- /dev/null
+++ b/lib/Transforms/NaCl/ExceptionInfoWriter.cpp
@@ -0,0 +1,228 @@
+//===- 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

[Derek Schuff, 2013/10/15 17:39:26]

I do like the idea of starting with the top-down description. My problem was
that I read the header file first, and got the bottom-up description first
anyway. Maybe we could just put a note at the top of the header pointing to the
general description here.

[Mark Seaborn, 2013/10/15 21:41:18]

Comment added to ExceptionInfoWriter.h.

+// "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

[Derek Schuff, 2013/10/15 17:39:26]

maybe say "represents" instead of "encodes" (the way you do elsewhere below),
since "encodes" seems to imply that you pack all of the relevant information
into the 32-bit identifier.

More generally, it wasn't immediately clear to me that each clause in a
landingpad's list is uniquely identified by the pair of its list id (which is
unique to the landingpad instruction) and its clause id (which is the same as
other clauses which catch or filter the same types). It would almost be clearer
to call "clause ID" a "clause type ID" because it really identifies the *kind*
of clause rather than the clause itself. but of course "type" isn't a great word
to use in that context.

[Mark Seaborn, 2013/10/15 21:41:18]

Hmm, I thought "represent" would carry the same implication that you're
concerned about here. :-)

OK, changed to "represent".
No, none of these IDs are unique to specific instances of landingpad
instructions...

The same IDs can be used across converted landingpads.  Type IDs and clause list
IDs are currently interned (though filter IDs are not).
Not sure I understand what you've understood from this...

How about if I include an example like the following?

std::type_info *const __pnacl_eh_type_table[] = {
  &typeinfo(ExcA),  // defines type ID 0 == ExcA and clause ID 0 == "catch ExcA"
  &typeinfo(ExcB),  // defines type ID 1 == ExcB and clause ID 1 == "catch ExcA"
};

const uint32_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 []"
};

const struct action_table_entry __pnacl_eh_action_table[] = {
  // defines clause list ID 1:
  {
    0,  // "catch ExcA"
    2,  // else go to clause list ID 2
  },
  // defines clause list ID 2:
  {
    1,  // "catch ExcB"
    3,  // else go to clause list ID 3
  },
  // defines clause list ID 3:
  {
    -1,  // "filter [ExcA, ExcB]"
    0,  // end of list (no more actions)
  },
};

So if a landingpad contains the clause list:
  catch ExcA,
  catch ExcB
  filter [ExcA, ExcB]
this will be represented as clause list ID 1.

Maybe I should rename "clause list ID" to "action ID"?

[Derek Schuff, 2013/10/15 22:36:20]

Yeah, after seeing it the other way, it doesn't really seem any better or worse.
Your call.

And yes, the example is helpful.
I'm not sure action ID is any better, since there's not a really good idea of
what an action is. clause list ID at least makes sense in the context of the
landingpad instructions.

[Mark Seaborn, 2013/10/15 23:08:57]

OK, I've changed it back to "encode".
I've added it to the comment in the code.  Please take a look.
OK.

+// 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 uint32_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.
+//
+// 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");

[Derek Schuff, 2013/10/15 17:39:26]

We've been using report_fatal_error for things that depends on user/developer
input or which might be conceivably reported to the user, but all the RFE's in
here are basically violations of invariants in the construction of the
EH-related IR, and would basically imply a broken module. It might make more
sense just to have them as asserts (and if the module verifier doesn't check
them, we can fix that too). That would also allow conversion of a bunch of
dyn_casts to casts.

[Mark Seaborn, 2013/10/15 21:41:18]

Not sure I agree.  It's inelegant for the module verifier to have to check usage
of miscellaneous intrinsics.  I'd hope the module verifier only has to check
core IR features (instructions).  The purpose of having intrinsics is to make IR
extensible without having the extend core code (such as the module verifier).

It also might be slower to have checks in the module verifier than at the point
where intrinsics are used.

The module verifier generally isn't run between passes, so it wouldn't protect
us from bad output by (e.g.) an optimisation pass.

ExpandConstantExpr is an example of a pass that would make this check fail.

+
+  // 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 represent as 0.

[Derek Schuff, 2013/10/15 17:39:26]

represent->represented

[Mark Seaborn, 2013/10/15 21:41:18]

Done.

+  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);
+  GlobalValue *OldGlobal = M->getGlobalVariable(Name);
+  if (OldGlobal) {

[Derek Schuff, 2013/10/15 17:39:26]

If there does not exist a variable by that name already, where is it actually
created?

[Mark Seaborn, 2013/10/15 21:41:18]

This code is expecting an external reference to __pnacl_eh_type_table, etc.  It
resolves the external reference.

I've added a check to give an error if the variable is not an external reference
(if it has an initialiser).

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