Add eh.begincatch and eh.endcatch intrinsics

[andrew.w.kaylor]

Summary

This patch adds two new intrinsics, llvm.eh.begincatch and llvm.eh.endcatch, that will be used in the native Windows C++ exception handling implementation and begins the documentation for native Windows exception handling.

These intrinsics are not intended to be generated by any component until the back end code to remove them during the WinEHPrepare pass is complete. In the meantime, I am implementing only lint verification. These intrinsics are not intended to make it through to code generation.

[rnk]

This change is 50% docs and 50% verifier. I'm happy with the docs, but it's not clear to me that we can really have these verifier checks.

docs/ExceptionHandling.rst

328 ↗

(On Diff #19297)

"multi"

Would you say this is a two-phase approach? That's how I've always thought of it.

331 ↗

(On Diff #19297)

I don't think "unwind handler" is a term used elsewhere in this document. "cleanup" would be consistent with the rest. Can you define the term if you want to use it in this section?

334–335 ↗

(On Diff #19297)

maybe "it is necessary to outline these handlers from their original context before code generation"?

338 ↗

(On Diff #19297)

I guess the stack pointer is really whatever pointer is established by the Win64 unwind opcodes. If the unwind codes end in .setframe, it's that register plus the specified offset, and otherwise it's the stack pointer. I'm not sure if it's worth writing this down here.

355 ↗

(On Diff #19297)

Maybe "... scope, while the runtime" or "and the runtime"? I don't think the second part of the sentence opposes the first.

369–372 ↗

(On Diff #19297)

I don't think it's quite clear what's going to be left in the landingpad afterwards. Maybe:

During the WinEHPrepare pass, landingpad code is outlined into handler functions. Only stub landingpad basic blocks are left in the IR. Each landingpad contains a landingpad instruction, a call to @llvm.eh.actions, and an indirectbr to indicate possible catch handler destinations.

Then the bit about what eh.actions holds.

lib/IR/Verifier.cpp

1052–1053 ↗

(On Diff #19297)

At a high level, I'm not sure we should be verifying these things. I always try to keep in mind a transform that tries to merge similar basic blocks, like this:

void f() {
  if (b) {
    try {
    } catch (int) {
      g(); g(); g();
    }
  } else {
    g(); g(); g();
  }
}

If we deduplicated the calls to g(), we would end up with a CFG where the begincatch doesn't dominate the endcatch:

g_bb:
  %dst = phi i1 [0, %else], [1, %catch]
  call void @g()
  call void @g()
  call void @g()
  br i1 %dst, label %catch.cont, label %else.cont

Note that the outliner has to leave this bb behind in the parent function, and it will also have to leave behind a call to endcatch which is statically reachable from the entry block. We know after preparation, however, that endcatch is dynamically unreachable, so we could transform it to unreachable and run SimplifyCFG to clean it up.

I agree this is a good check to run on frontend generated, IR, though. Maybe we should move this to the Lint pass? Maybe clang should run the lint pass in asserts mode?

1061 ↗

(On Diff #19297)

First, I think it would be clearer to simply hoist this into a static local function. The only state you need is VisitedBlocks.

Second, std::function is more expensive than using auto. std::function will make an unnecessary opaque wrapper class for the lambda, which we don't need.

1068 ↗

(On Diff #19297)

I added a predecessors() range-based-for adapter for this.

1071 ↗

(On Diff #19297)

You should use a BB worklist. This causes O(n) recursion in the depth of the CFG, which could be large.

[andrew.w.kaylor]

I'm happy to move the verification to the lint pass. Its main usefulness is definitely for verifying the output from the front end.

docs/ExceptionHandling.rst

328 ↗

(On Diff #19297)

It's certainly reasonable to think of it that way, but the runtime is doing enough behind the curtain that I decided to use this as a sort of hand-waving term. There are essentially two phases that are visible for our purposes, and maybe that's reason enough to describe it that way. I was just thinking of the other things that are going on inside the runtime.

331 ↗

(On Diff #19297)

I was thinking that the Microsoft documentation for exception handling (which I should probably link to somewhere) called it an unwind handler, but I just looked and even though the flag is UNW_FLAG_UHANDLER they seem to call it a termination handler. I'll give some thought to how I can best reconcile these things for clarity.

334–335 ↗

(On Diff #19297)

OK

338 ↗

(On Diff #19297)

I'll take a look and make sure I end up with accurate wording.

355 ↗

(On Diff #19297)

This is probably a good reason not to use the term "unwind handler" because it seemed to me like people would be likely to expect the unwind handler to do some unwinding.

369–372 ↗

(On Diff #19297)

An example would probably make it clear.

lib/IR/Verifier.cpp

1052–1053 ↗

(On Diff #19297)

I see. With a bit of effort I could figure out that the branch was using the phi and make the check work, but I suppose trying to generalize that would take way more code than I can justify for this.

1061 ↗

(On Diff #19297)

OK. It seemed like conceptually this was a good place for a lambda, then I had to look up the syntax for making recursion work. I guess I let it get away from me a bit.

1068 ↗

(On Diff #19297)

Nice. I'll look that up.

1071 ↗

(On Diff #19297)

My thinking was that if the IR is correct we'll find the landing pad within a few blocks and if not then compilation is going to fail anyway, so I just wanted to keep this simple.

[andrew.w.kaylor]

Updated documentation based on review comments
Moved verification code from Verifier to Lint and revised it based on review comments
Rebased

[rnk]

lgtm

Thanks, sorry I got distracted working on http://reviews.llvm.org/D7520

llvm/trunk/docs/ExceptionHandling.rst

 
 In contrast to DWARF exception handling, which encodes exception regions and
 frame information in out-of-line tables, SJLJ exception handling builds and
 removes the unwind frame context at runtime. This results in faster exception
 handling at the expense of slower execution when no exceptions are thrown. As
 exceptions are, by their nature, intended for uncommon code paths, DWARF
 exception handling is generally preferred to SJLJ.
 
+Windows Runtime Exception Handling
+-----------------------------------
+
+Windows runtime based exception handling uses the same basic IR structure as
+Itanium ABI based exception handling, but it relies on the personality
+functions provided by the native Windows runtime library, ``__CxxFrameHandler3``
+for C++ exceptions: ``__C_specific_handler`` for 64-bit SEH or 
+``_frame_handler3/4`` for 32-bit SEH.  This results in a very different
+execution model and requires some minor modifications to the initial IR
+representation and a significant restructuring just before code generation.
+
+General information about the Windows x64 exception handling mechanism can be
+found at `MSDN Exception Handling (x64)
+<https://msdn.microsoft.com/en-us/library/1eyas8tf(v=vs.80).aspx>_`.
+
 Overview
 --------
 
 When an exception is thrown in LLVM code, the runtime does its best to find a
 handler suited to processing the circumstance.
 
 The runtime first attempts to find an *exception frame* corresponding to the
 function where the exception was thrown.  If the programming language supports

 catches exceptions of type ``B``. The inliner will update the ``landingpad``
 instruction for the inlined landing pad to include the fact that ``B`` is also
 caught. If that landing pad assumes that it will only be entered to catch an
 ``A``, it's in for a rude awakening.  Consequently, landing pads must test for
 the selector results they understand and then resume exception propagation with
 the `resume instruction <LangRef.html#i_resume>`_ if none of the conditions
 match.
 
+C++ Exception Handling using the Windows Runtime
+=================================================
+
+(Note: Windows C++ exception handling support is a work in progress and is
+ not yet fully implemented.  The text below describes how it will work
+ when completed.)
+
+The Windows runtime function for C++ exception handling uses a mutli-phase
+approach.  When an exception occurs it searches the current callstack for a
+frame that has a handler for the exception.  If a handler is found, it then
+calls the cleanup handler for each frame above the handler which has a
+cleanup handler before calling the catch handler.  These calls are all made
+from a stack context different from the original frame in which the handler
+is defined.  Therefore, it is necessary to outline these handlers from their
+original context before code generation.
+
+Catch handlers are called with a pointer to the handler itself as the first
+argument and a pointer to the parent function's stack frame as the second
+argument.  The catch handler uses the `llvm.recoverframe
+<LangRef.html#llvm-frameallocate-and-llvm-framerecover-intrinsics>`_ to get a
+pointer to a frame allocation block that is created in the parent frame using
+the `llvm.allocateframe 
+<LangRef.html#llvm-frameallocate-and-llvm-framerecover-intrinsics>`_ intrinsic.
+The ``WinEHPrepare`` pass will have created a structure definition for the
+contents of this block.  The first two members of the structure will always be
+(1) a 32-bit integer that the runtime uses to track the exception state of the
+parent frame for the purposes of handling chained exceptions and (2) a pointer
+to the object associated with the exception (roughly, the parameter of the
+catch clause). These two members will be followed by any frame variables from
+the parent function which must be accessed in any of the functions unwind or
+catch handlers.  The catch handler returns the address at which execution
+should continue.
+
+Cleanup handlers perform any cleanup necessary as the frame goes out of scope,
+such as calling object destructors.  The runtime handles the actual unwinding
+of the stack.  If an exception occurs in a cleanup handler the runtime manages
+termination of the process. Cleanup handlers are called with the same arguments
+as catch handlers (a pointer to the handler and a pointer to the parent stack
+frame) and use the same mechanism described above to access frame variables
+in the parent function.  Cleanup handlers do not return a value.
+
+The IR generated for Windows runtime based C++ exception handling is initially
+very similar to the ``landingpad`` mechanism described above.  Calls to
+libc++abi functions (such as ``__cxa_begin_catch``/``__cxa_end_catch`` and
+``__cxa_throw_exception`` are replaced with calls to intrinsics or Windows
+runtime functions (such as ``llvm.eh.begincatch``/``llvm.eh.endcatch`` and
+``__CxxThrowException``).
+
+During the WinEHPrepare pass, the handler functions are outlined into handler
+functions and the original landing pad code is replaced with a call to the
+``llvm.eh.actions`` intrinsic that describes the order in which handlers will
+be processed from the logical location of the landing pad and an indirect
+branch to the return value of the ``llvm.eh.actions`` intrinsic. The
+``llvm.eh.actions`` intrinsic is defined as returning the address at which
+execution will continue.  This is a temporary construct which will be removed
+before code generation, but it allows for the accurate tracking of control
+flow until then.
+
+A typical landing pad will look like this after outlining:
+
+.. code-block:: llvm
+
+    lpad:
+      %vals = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
+        cleanup
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+          catch i8* bitcast (i8** @_ZTIf to i8*)
+      %recover = call i8* (...)* @llvm.eh.actions(
+          i32 3, i8* bitcast (i8** @_ZTIi to i8*), i8* (i8*, i8*)* @_Z4testb.catch.1)
+          i32 2, i8* null, void (i8*, i8*)* @_Z4testb.cleanup.1)
+          i32 1, i8* bitcast (i8** @_ZTIf to i8*), i8* (i8*, i8*)* @_Z4testb.catch.0)
+          i32 0, i8* null, void (i8*, i8*)* @_Z4testb.cleanup.0)
+      indirectbr i8* %recover, [label %try.cont1, label %try.cont2]
+
+In this example, the landing pad represents an exception handling context with
+two catch handlers and a cleanup handler that have been outlined.  If an
+exception is thrown with a type that matches ``_ZTIi``, the ``_Z4testb.catch.1``
+handler will be called an no clean-up is needed.  If an exception is thrown
+with a type that matches ``_ZTIf``, first the ``_Z4testb.cleanup.1`` handler
+will be called to perform unwind-related cleanup, then the ``_Z4testb.catch.1``
+handler will be called.  If an exception is throw which does not match either
+of these types and the exception is handled by another frame further up the
+call stack, first the ``_Z4testb.cleanup.1`` handler will be called, then the
+``_Z4testb.cleanup.0`` handler (which corresponds to a different scope) will be
+called, and exception handling will continue at the next frame in the call
+stack will be called.  One of the catch handlers will return the address of
+``%try.cont1`` in the parent function and the other will return the address of
+``%try.cont2``, meaning that execution continues at one of those blocks after
+an exception is caught.
+
+
 Exception Handling Intrinsics
 =============================
 
 In addition to the ``landingpad`` and ``resume`` instructions, LLVM uses several
 intrinsic functions (name prefixed with ``llvm.eh``) to provide exception
 handling information at various points in generated code.
 
 .. _llvm.eh.typeid.for:
 
 ``llvm.eh.typeid.for``
 ----------------------
 
 .. code-block:: llvm
 
   i32 @llvm.eh.typeid.for(i8* %type_info)
 
 
 This intrinsic returns the type info index in the exception table of the current
 function.  This value can be used to compare against the result of
 ``landingpad`` instruction.  The single argument is a reference to a type info.
 
 Uses of this intrinsic are generated by the C++ front-end.
 
+.. _llvm.eh.begincatch:
+
+``llvm.eh.begincatch``
+----------------------
+
+.. code-block:: llvm
+
+  i8* @llvm.eh.begincatch(i8* %exn)
+
+
+This intrinsic marks the beginning of catch handling code within the blocks
+following a ``landingpad`` instruction.  The exact behavior of this function
+depends on the compilation target and the personality function associated
+with the ``landingpad`` instruction.
+
+The argument to this intrinsic is a pointer that was previously extracted from
+the aggregate return value of the ``landingpad`` instruction.  The return
+value of the intrinsic is a pointer to the exception object to be used by the
+catch code.  This pointer is returned as an ``i8*`` value, but the actual type
+of the object will depend on the exception that was thrown.
+
+Uses of this intrinsic are generated by the C++ front-end.  Many targets will
+use implementation-specific functions (such as ``__cxa_begin_catch``) instead
+of this intrinsic.  The intrinsic is provided for targets that require a more
+abstract interface.
+
+When used in the native Windows C++ exception handling implementation, this
+intrinsic serves as a placeholder to delimit code before a catch handler is
+outlined.  When the handler is is outlined, this intrinsic will be replaced
+by instructions that retrieve the exception object pointer from the frame
+allocation block.
+
+
+.. _llvm.eh.endcatch:
+
+``llvm.eh.endcatch``
+----------------------
+
+.. code-block:: llvm
+
+  void @llvm.eh.endcatch()
+
+
+This intrinsic marks the end of catch handling code within the current block,
+which will be a successor of a block which called ``llvm.eh.begincatch''.
+The exact behavior of this function depends on the compilation target and the
+personality function associated with the corresponding ``landingpad``
+instruction.
+
+There may be more than one call to ``llvm.eh.endcatch`` for any given call to
+``llvm.eh.begincatch`` with each ``llvm.eh.endcatch`` call corresponding to the
+end of a different control path.  All control paths following a call to
+``llvm.eh.begincatch`` must reach a call to ``llvm.eh.endcatch``.
+
+Uses of this intrinsic are generated by the C++ front-end.  Many targets will
+use implementation-specific functions (such as ``__cxa_begin_catch``) instead
+of this intrinsic.  The intrinsic is provided for targets that require a more
+abstract interface.
+
+When used in the native Windows C++ exception handling implementation, this
+intrinsic serves as a placeholder to delimit code before a catch handler is
+outlined.  After the handler is outlined, this intrinsic is simply removed.
+
+
 SJLJ Intrinsics
 ---------------
 
 The ``llvm.eh.sjlj`` intrinsics are used internally within LLVM's
 backend.  Uses of them are generated by the backend's
 ``SjLjEHPrepare`` pass.
 
 .. _llvm.eh.sjlj.setjmp:

llvm/trunk/include/llvm/IR/Intrinsics.td

 
 // The result of eh.typeid.for depends on the enclosing function, but inside a
 // given function it is 'const' and may be CSE'd etc.
 def int_eh_typeid_for : Intrinsic<[llvm_i32_ty], [llvm_ptr_ty], [IntrNoMem]>;
 
 def int_eh_return_i32 : Intrinsic<[], [llvm_i32_ty, llvm_ptr_ty]>;
 def int_eh_return_i64 : Intrinsic<[], [llvm_i64_ty, llvm_ptr_ty]>;
 
+// eh.begincatch takes a pointer returned by a landingpad instruction and
+// returns the exception object pointer for the exception to be handled.
+def int_eh_begincatch : Intrinsic<[llvm_ptr_ty], [llvm_ptr_ty]>;
+def int_eh_endcatch : Intrinsic<[], []>;
+
 // __builtin_unwind_init is an undocumented GCC intrinsic that causes all
 // callee-saved registers to be saved and restored (regardless of whether they
 // are used) in the calling function. It is used by libgcc_eh.
 def int_eh_unwind_init: Intrinsic<[]>,
                         GCCBuiltin<"__builtin_unwind_init">;
 
 def int_eh_dwarf_cfa  : Intrinsic<[llvm_ptr_ty], [llvm_i32_ty]>;
 

llvm/trunk/lib/Analysis/Lint.cpp

 // This code may be run before instcombine. In many cases, instcombine checks
 // for the same kinds of things and turns instructions with undefined behavior
 // into unreachable (or equivalent). Because of this, this pass makes some
 // effort to look through bitcasts and so on.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/Lint.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
class Lint : public FunctionPass, public InstVisitor<Lint> {
     friend class InstVisitor<Lint>;
 
     void visitFunction(Function &F);
 
     void visitCallSite(CallSite CS);
     void visitMemoryReference(Instruction &I, Value *Ptr,
                               uint64_t Size, unsigned Align,
                               Type *Ty, unsigned Flags);
+    void visitEHBeginCatch(IntrinsicInst *II);
+    void visitEHEndCatch(IntrinsicInst *II);
 
     void visitCallInst(CallInst &I);
     void visitInvokeInst(InvokeInst &I);
     void visitReturnInst(ReturnInst &I);
     void visitLoadInst(LoadInst &I);
     void visitStoreInst(StoreInst &I);
     void visitXor(BinaryOperator &I);
     void visitSub(BinaryOperator &I);
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I))
 
     case Intrinsic::stackrestore:
       // Stackrestore doesn't read or write memory, but it sets the
       // stack pointer, which the compiler may read from or write to
       // at any time, so check it for both readability and writeability.
       visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize,
                            0, nullptr, MemRef::Read | MemRef::Write);
       break;
+
+    case Intrinsic::eh_begincatch:
+      visitEHBeginCatch(II);
+      break;
+    case Intrinsic::eh_endcatch:
+      visitEHEndCatch(II);
+      break;
     }
 }
 
 void Lint::visitCallInst(CallInst &I) {
   return visitCallSite(&I);
 }
 
 void Lint::visitInvokeInst(InvokeInst &I) {

 
 void Lint::visitShl(BinaryOperator &I) {
   if (ConstantInt *CI =
         dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false)))
     Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()),
             "Undefined result: Shift count out of range", &I);
 }
 
+static bool
+allPredsCameFromLandingPad(BasicBlock *BB,
+                           SmallSet<BasicBlock *, 4> &VisitedBlocks) {
+  VisitedBlocks.insert(BB);
+  if (BB->isLandingPad())
+    return true;
+  // If we find a block with no predecessors, the search failed.
+  if (pred_empty(BB))
+    return false;
+  for (BasicBlock *Pred : predecessors(BB)) {
+    if (VisitedBlocks.count(Pred))
+      continue;
+    if (!allPredsCameFromLandingPad(Pred, VisitedBlocks))
+      return false;
+  }
+  return true;
+}
+
+static bool
+allSuccessorsReachEndCatch(BasicBlock *BB, BasicBlock::iterator InstBegin,
+                           IntrinsicInst **SecondBeginCatch,
+                           SmallSet<BasicBlock *, 4> &VisitedBlocks) {
+  VisitedBlocks.insert(BB);
+  for (BasicBlock::iterator I = InstBegin, E = BB->end(); I != E; ++I) {
+    IntrinsicInst *IC = dyn_cast<IntrinsicInst>(I);
+    if (IC && IC->getIntrinsicID() == Intrinsic::eh_endcatch)
+      return true;
+    // If we find another begincatch while looking for an endcatch,
+    // that's also an error.
+    if (IC && IC->getIntrinsicID() == Intrinsic::eh_begincatch) {
+      *SecondBeginCatch = IC;
+      return false;
+    }
+  }
+
+  // If we reach a block with no successors while searching, the
+  // search has failed.
+  if (succ_empty(BB))
+    return false;
+  // Otherwise, search all of the successors.
+  for (BasicBlock *Succ : successors(BB)) {
+    if (VisitedBlocks.count(Succ))
+      continue;
+    if (!allSuccessorsReachEndCatch(Succ, Succ->begin(), SecondBeginCatch,
+                                    VisitedBlocks))
+      return false;
+  }
+  return true;
+}
+
+void Lint::visitEHBeginCatch(IntrinsicInst *II) {
+  // The checks in this function make a potentially dubious assumption about
+  // the CFG, namely that any block involved in a catch is only used for the
+  // catch.  This will very likely be true of IR generated by a front end,
+  // but it may cease to be true, for example, if the IR is run through a
+  // pass which combines similar blocks.
+  //
+  // In general, if we encounter a block the isn't dominated by the catch
+  // block while we are searching the catch block's successors for a call
+  // to end catch intrinsic, then it is possible that it will be legal for
+  // a path through this block to never reach a call to llvm.eh.endcatch.
+  // An analogous statement could be made about our search for a landing
+  // pad among the catch block's predecessors.
+  //
+  // What is actually required is that no path is possible at runtime that
+  // reaches a call to llvm.eh.begincatch without having previously visited
+  // a landingpad instruction and that no path is possible at runtime that
+  // calls llvm.eh.begincatch and does not subsequently call llvm.eh.endcatch
+  // (mentally adjusting for the fact that in reality these calls will be
+  // removed before code generation).
+  //
+  // Because this is a lint check, we take a pessimistic approach and warn if
+  // the control flow is potentially incorrect.
+
+  SmallSet<BasicBlock *, 4> VisitedBlocks;
+  BasicBlock *CatchBB = II->getParent();
+
+  // The begin catch must occur in a landing pad block or all paths
+  // to it must have come from a landing pad.
+  Assert1(allPredsCameFromLandingPad(CatchBB, VisitedBlocks),
+          "llvm.eh.begincatch may be reachable without passing a landingpad", 
+          II);
+
+  // Reset the visited block list.
+  VisitedBlocks.clear();
+
+  IntrinsicInst *SecondBeginCatch = nullptr;
+
+  // This has to be called before it is asserted.  Otherwise, the first assert
+  // below can never be hit.
+  bool EndCatchFound = allSuccessorsReachEndCatch(
+      CatchBB, std::next(static_cast<BasicBlock::iterator>(II)),
+      &SecondBeginCatch, VisitedBlocks);
+  Assert2(
+      SecondBeginCatch == nullptr,
+      "llvm.eh.begincatch may be called a second time before llvm.eh.endcatch",
+      II, SecondBeginCatch);
+  Assert1(EndCatchFound,
+          "Some paths from llvm.eh.begincatch may not reach llvm.eh.endcatch",
+          II);
+}
+
+static bool allPredCameFromBeginCatch(
+    BasicBlock *BB, BasicBlock::reverse_iterator InstRbegin,
+    IntrinsicInst **SecondEndCatch, SmallSet<BasicBlock *, 4> &VisitedBlocks) {
+  VisitedBlocks.insert(BB);
+  // Look for a begincatch in this block.
+  for (BasicBlock::reverse_iterator RI = InstRbegin, RE = BB->rend(); RI != RE;
+       ++RI) {
+    IntrinsicInst *IC = dyn_cast<IntrinsicInst>(&*RI);
+    if (IC && IC->getIntrinsicID() == Intrinsic::eh_begincatch)
+      return true;
+    // If we find another end catch before we find a begin catch, that's
+    // an error.
+    if (IC && IC->getIntrinsicID() == Intrinsic::eh_endcatch) {
+      *SecondEndCatch = IC;
+      return false;
+    }
+    // If we encounter a landingpad instruction, the search failed.
+    if (isa<LandingPadInst>(*RI))
+      return false;
+  }
+  // If while searching we find a block with no predeccesors,
+  // the search failed.
+  if (pred_empty(BB))
+    return false;
+  // Search any predecessors we haven't seen before.
+  for (BasicBlock *Pred : predecessors(BB)) {
+    if (VisitedBlocks.count(Pred))
+      continue;
+    if (!allPredCameFromBeginCatch(Pred, Pred->rbegin(), SecondEndCatch,
+                                   VisitedBlocks))
+      return false;
+  }
+  return true;
+}
+
+void Lint::visitEHEndCatch(IntrinsicInst *II) {
+  // The check in this function makes a potentially dubious assumption about
+  // the CFG, namely that any block involved in a catch is only used for the
+  // catch.  This will very likely be true of IR generated by a front end,
+  // but it may cease to be true, for example, if the IR is run through a
+  // pass which combines similar blocks.
+  //
+  // In general, if we encounter a block the isn't post-dominated by the
+  // end catch block while we are searching the end catch block's predecessors
+  // for a call to the begin catch intrinsic, then it is possible that it will
+  // be legal for a path to reach the end catch block without ever having
+  // called llvm.eh.begincatch.
+  //
+  // What is actually required is that no path is possible at runtime that
+  // reaches a call to llvm.eh.endcatch without having previously visited
+  // a call to llvm.eh.begincatch (mentally adjusting for the fact that in
+  // reality these calls will be removed before code generation).
+  //
+  // Because this is a lint check, we take a pessimistic approach and warn if
+  // the control flow is potentially incorrect.
+
+  BasicBlock *EndCatchBB = II->getParent();
+
+  // Alls paths to the end catch call must pass through a begin catch call.
+
+  // If llvm.eh.begincatch wasn't called in the current block, we'll use this
+  // lambda to recursively look for it in predecessors.
+  SmallSet<BasicBlock *, 4> VisitedBlocks;
+  IntrinsicInst *SecondEndCatch = nullptr;
+
+  // This has to be called before it is asserted.  Otherwise, the first assert
+  // below can never be hit.
+  bool BeginCatchFound =
+      allPredCameFromBeginCatch(EndCatchBB, BasicBlock::reverse_iterator(II),
+                                &SecondEndCatch, VisitedBlocks);
+  Assert2(
+      SecondEndCatch == nullptr,
+      "llvm.eh.endcatch may be called a second time after llvm.eh.begincatch",
+      II, SecondEndCatch);
+  Assert1(
+      BeginCatchFound,
+      "llvm.eh.endcatch may be reachable without passing llvm.eh.begincatch",
+      II);
+}
+
 static bool isZero(Value *V, const DataLayout *DL, DominatorTree *DT,
                    AssumptionCache *AC) {
   // Assume undef could be zero.
   if (isa<UndefValue>(V))
     return true;
 
   VectorType *VecTy = dyn_cast<VectorType>(V->getType());
   if (!VecTy) {

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

case Intrinsic::framerecover: {
     // Add the offset to the FP.
     Value *FP = I.getArgOperand(1);
     SDValue FPVal = getValue(FP);
     SDValue Add = DAG.getNode(ISD::ADD, sdl, PtrVT, FPVal, OffsetVal);
     setValue(&I, Add);
 
     return nullptr;
   }
+  case Intrinsic::eh_begincatch:
+  case Intrinsic::eh_endcatch:
+    llvm_unreachable("begin/end catch intrinsics not lowered in codegen");
   }
 }
 
 std::pair<SDValue, SDValue>
 SelectionDAGBuilder::lowerInvokable(TargetLowering::CallLoweringInfo &CLI,
                                     MachineBasicBlock *LandingPad) {
   MachineModuleInfo &MMI = DAG.getMachineFunction().getMMI();
   MCSymbol *BeginLabel = nullptr;

llvm/trunk/test/Analysis/Lint/cppeh-catch-intrinsics-clean.ll

+; RUN: opt -lint -disable-output < %s
+
+; This test is meant to prove that the verifier does not report errors for correct
+; use of the llvm.eh.begincatch and llvm.eh.endcatch intrinsics.
+
+target triple = "x86_64-pc-windows-msvc"
+
+declare i8* @llvm.eh.begincatch(i8*)
+
+declare void @llvm.eh.endcatch()
+
+@_ZTIi = external constant i8*
+
+; Function Attrs: uwtable
+define void @test_ref_clean() {
+entry:
+  invoke void @_Z9may_throwv()
+          to label %try.cont unwind label %lpad
+
+lpad:                                             ; preds = %entry
+  %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %exn = extractvalue { i8*, i32 } %0, 0
+  %sel = extractvalue { i8*, i32 } %0, 1
+  %1 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %sel, %1
+  br i1 %matches, label %catch, label %eh.resume
+
+catch:                                            ; preds = %lpad
+  %2 = call i8* @llvm.eh.begincatch(i8* %exn)
+  call void @_Z10handle_intv()
+  br label %invoke.cont2
+
+invoke.cont2:                                     ; preds = %catch
+  call void @llvm.eh.endcatch()
+  br label %try.cont
+
+try.cont:                                         ; preds = %invoke.cont2, %entry
+  ret void
+
+eh.resume:                                        ; preds = %catch.dispatch
+  resume { i8*, i32 } %0
+}
+
+; Function Attrs: uwtable
+define void @test_ref_clean_multibranch() {
+entry:
+  invoke void @_Z9may_throwv()
+          to label %invoke.cont unwind label %lpad
+
+invoke.cont:
+  invoke void @_Z9may_throwv()
+          to label %invoke.cont unwind label %lpad1
+
+lpad:                                             ; preds = %entry
+  %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %exn = extractvalue { i8*, i32 } %0, 0
+  %sel = extractvalue { i8*, i32 } %0, 1
+  %1 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %sel, %1
+  br i1 %matches, label %catch, label %eh.resume
+
+  invoke void @_Z9may_throwv()
+          to label %try.cont unwind label %lpad
+
+lpad1:                                            ; preds = %entry
+  %l1.0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
+      cleanup
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %exn1 = extractvalue { i8*, i32 } %l1.0, 0
+  %sel1 = extractvalue { i8*, i32 } %l1.0, 1
+  %l1.1 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matchesl1 = icmp eq i32 %sel1, %l1.1
+  br i1 %matchesl1, label %catch, label %eh.resume
+
+catch:                                            ; preds = %lpad, %lpad1
+  %exn2 = phi i8* [%exn, %lpad], [%exn1, %lpad1]
+  %sel2 = phi i32 [%sel, %lpad], [%sel1, %lpad1]
+  %3 = call i8* @llvm.eh.begincatch(i8* %exn2)
+  call void @_Z10handle_intv()
+  %matches1 = icmp eq i32 %sel2, 0
+  br i1 %matches1, label %invoke.cont2, label %invoke.cont3
+
+invoke.cont2:                                     ; preds = %catch
+  call void @llvm.eh.endcatch()
+  br label %try.cont
+
+invoke.cont3:                                     ; preds = %catch
+  call void @llvm.eh.endcatch()
+  br label %eh.resume
+
+try.cont:                                         ; preds = %invoke.cont2, %entry
+  ret void
+
+eh.resume:                                        ; preds = %catch.dispatch
+  %lpad.val = insertvalue { i8*, i32 } undef, i32 0, 1
+  resume { i8*, i32 } %lpad.val
+}
+
+declare void @_Z9may_throwv()
+
+declare i32 @__CxxFrameHandler3(...)
+
+; Function Attrs: nounwind readnone
+declare i32 @llvm.eh.typeid.for(i8*)
+
+declare void @_Z10handle_intv()
+

llvm/trunk/test/Analysis/Lint/cppeh-catch-intrinsics.ll

+; RUN: opt -lint -disable-output < %s 2>&1 | FileCheck %s
+
+; This test is meant to prove that the Verifier is able to identify a variety
+; of errors with the llvm.eh.begincatch and llvm.eh.endcatch intrinsics.
+; See cppeh-catch-intrinsics-clean for correct uses.
+
+target triple = "x86_64-pc-windows-msvc"
+
+declare i8* @llvm.eh.begincatch(i8*)
+
+declare void @llvm.eh.endcatch()
+
+@_ZTIi = external constant i8*
+
+; Function Attrs: uwtable
+define void @test_missing_endcatch() {
+; CHECK: Some paths from llvm.eh.begincatch may not reach llvm.eh.endcatch
+; CHECK-NEXT: %2 = call i8* @llvm.eh.begincatch(i8* %exn)
+entry:
+  invoke void @_Z9may_throwv()
+          to label %try.cont unwind label %lpad
+
+lpad:                                             ; preds = %entry
+  %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %exn = extractvalue { i8*, i32 } %0, 0
+  %sel = extractvalue { i8*, i32 } %0, 1
+  %1 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %sel, %1
+  br i1 %matches, label %catch, label %eh.resume
+
+catch:                                            ; preds = %lpad
+  %2 = call i8* @llvm.eh.begincatch(i8* %exn)
+  call void @_Z10handle_intv()
+  br label %invoke.cont2
+
+invoke.cont2:                                     ; preds = %catch
+  br label %try.cont
+
+try.cont:                                         ; preds = %invoke.cont2, %entry
+  ret void
+
+eh.resume:                                        ; preds = %catch.dispatch
+  resume { i8*, i32 } %0
+}
+
+; Function Attrs: uwtable
+define void @test_missing_begincatch() {
+; CHECK: llvm.eh.endcatch may be reachable without passing llvm.eh.begincatch
+; CHECK-NEXT:  call void @llvm.eh.endcatch()
+entry:
+  invoke void @_Z9may_throwv()
+          to label %try.cont unwind label %lpad
+
+lpad:                                             ; preds = %entry
+  %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %exn = extractvalue { i8*, i32 } %0, 0
+  %sel = extractvalue { i8*, i32 } %0, 1
+  %1 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %sel, %1
+  br i1 %matches, label %catch, label %eh.resume
+
+catch:                                            ; preds = %lpad
+  call void @_Z10handle_intv()
+  br label %invoke.cont2
+
+invoke.cont2:                                     ; preds = %catch
+  call void @llvm.eh.endcatch()
+  br label %try.cont
+
+try.cont:                                         ; preds = %invoke.cont2, %entry
+  ret void
+
+eh.resume:                                        ; preds = %catch.dispatch
+  resume { i8*, i32 } %0
+}
+
+; Function Attrs: uwtable
+define void @test_multiple_begin() {
+; CHECK: llvm.eh.begincatch may be called a second time before llvm.eh.endcatch
+; CHECK-NEXT:  %2 = call i8* @llvm.eh.begincatch(i8* %exn)
+; CHECK-NEXT:  %3 = call i8* @llvm.eh.begincatch(i8* %exn)
+entry:
+  invoke void @_Z9may_throwv()
+          to label %try.cont unwind label %lpad
+
+lpad:                                             ; preds = %entry
+  %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %exn = extractvalue { i8*, i32 } %0, 0
+  %sel = extractvalue { i8*, i32 } %0, 1
+  %1 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %sel, %1
+  br i1 %matches, label %catch, label %eh.resume
+
+catch:                                            ; preds = %lpad
+  %2 = call i8* @llvm.eh.begincatch(i8* %exn)
+  call void @_Z10handle_intv()
+  br label %invoke.cont2
+
+invoke.cont2:                                     ; preds = %catch
+  %3 = call i8* @llvm.eh.begincatch(i8* %exn)
+  call void @llvm.eh.endcatch()
+  br label %try.cont
+
+try.cont:                                         ; preds = %invoke.cont2, %entry
+  ret void
+
+eh.resume:                                        ; preds = %catch.dispatch
+  resume { i8*, i32 } %0
+}
+
+; Function Attrs: uwtable
+define void @test_multiple_end() {
+; CHECK: llvm.eh.endcatch may be called a second time after llvm.eh.begincatch
+; CHECK-NEXT:  call void @llvm.eh.endcatch()
+; CHECK-NEXT:  call void @llvm.eh.endcatch()
+entry:
+  invoke void @_Z9may_throwv()
+          to label %try.cont unwind label %lpad
+
+lpad:                                             ; preds = %entry
+  %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %exn = extractvalue { i8*, i32 } %0, 0
+  %sel = extractvalue { i8*, i32 } %0, 1
+  %1 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %sel, %1
+  br i1 %matches, label %catch, label %eh.resume
+
+catch:                                            ; preds = %lpad
+  %2 = call i8* @llvm.eh.begincatch(i8* %exn)
+  call void @_Z10handle_intv()
+  call void @llvm.eh.endcatch()
+  br label %invoke.cont2
+
+invoke.cont2:                                     ; preds = %catch
+  call void @llvm.eh.endcatch()
+  br label %try.cont
+
+try.cont:                                         ; preds = %invoke.cont2, %entry
+  ret void
+
+eh.resume:                                        ; preds = %catch.dispatch
+  resume { i8*, i32 } %0
+}
+
+
+; Function Attrs: uwtable
+define void @test_begincatch_without_lpad() {
+; CHECK: llvm.eh.begincatch may be reachable without passing a landingpad
+; CHECK-NEXT:  %0 = call i8* @llvm.eh.begincatch(i8* %exn)
+entry:
+  %exn = alloca i8
+  %0 = call i8* @llvm.eh.begincatch(i8* %exn)
+  call void @_Z10handle_intv()
+  br label %invoke.cont2
+
+invoke.cont2:                                     ; preds = %catch
+  call void @llvm.eh.endcatch()
+  br label %try.cont
+
+try.cont:                                         ; preds = %invoke.cont2, %entry
+  ret void
+}
+
+; Function Attrs: uwtable
+define void @test_branch_to_begincatch_with_no_lpad(i32 %fake.sel) {
+; CHECK: llvm.eh.begincatch may be reachable without passing a landingpad
+; CHECK-NEXT:  %3 = call i8* @llvm.eh.begincatch(i8* %exn2)
+entry:
+  %fake.exn = alloca i8
+  invoke void @_Z9may_throwv()
+          to label %catch unwind label %lpad
+
+lpad:                                             ; preds = %entry
+  %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %exn = extractvalue { i8*, i32 } %0, 0
+  %sel = extractvalue { i8*, i32 } %0, 1
+  %1 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %sel, %1
+  br i1 %matches, label %catch, label %eh.resume
+
+  invoke void @_Z9may_throwv()
+          to label %try.cont unwind label %lpad
+
+catch:                                            ; preds = %lpad, %entry
+  %exn2 = phi i8* [%exn, %lpad], [%fake.exn, %entry]
+  %sel2 = phi i32 [%sel, %lpad], [%fake.sel, %entry]
+  %3 = call i8* @llvm.eh.begincatch(i8* %exn2)
+  call void @_Z10handle_intv()
+  %matches1 = icmp eq i32 %sel2, 0
+  br i1 %matches1, label %invoke.cont2, label %invoke.cont3
+
+invoke.cont2:                                     ; preds = %catch
+  call void @llvm.eh.endcatch()
+  br label %try.cont
+
+invoke.cont3:                                     ; preds = %catch
+  call void @llvm.eh.endcatch()
+  br label %eh.resume
+
+try.cont:                                         ; preds = %invoke.cont2
+  ret void
+
+eh.resume:                                        ; preds = %catch.dispatch
+  %lpad.val = insertvalue { i8*, i32 } undef, i32 0, 1
+  resume { i8*, i32 } %lpad.val
+}
+
+; Function Attrs: uwtable
+define void @test_branch_missing_endcatch() {
+; CHECK: Some paths from llvm.eh.begincatch may not reach llvm.eh.endcatch
+; CHECK-NEXT:  %3 = call i8* @llvm.eh.begincatch(i8* %exn2)
+entry:
+  invoke void @_Z9may_throwv()
+          to label %invoke.cont unwind label %lpad
+
+invoke.cont:
+  invoke void @_Z9may_throwv()
+          to label %invoke.cont unwind label %lpad1
+
+lpad:                                             ; preds = %entry
+  %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %exn = extractvalue { i8*, i32 } %0, 0
+  %sel = extractvalue { i8*, i32 } %0, 1
+  %1 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %sel, %1
+  br i1 %matches, label %catch, label %eh.resume
+
+  invoke void @_Z9may_throwv()
+          to label %try.cont unwind label %lpad
+
+lpad1:                                            ; preds = %entry
+  %l1.0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
+      cleanup
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %exn1 = extractvalue { i8*, i32 } %l1.0, 0
+  %sel1 = extractvalue { i8*, i32 } %l1.0, 1
+  %l1.1 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matchesl1 = icmp eq i32 %sel1, %l1.1
+  br i1 %matchesl1, label %catch, label %eh.resume
+
+catch:                                            ; preds = %lpad, %lpad1
+  %exn2 = phi i8* [%exn, %lpad], [%exn1, %lpad1]
+  %sel2 = phi i32 [%sel, %lpad], [%sel1, %lpad1]
+  %3 = call i8* @llvm.eh.begincatch(i8* %exn2)
+  call void @_Z10handle_intv()
+  %matches1 = icmp eq i32 %sel2, 0
+  br i1 %matches1, label %invoke.cont2, label %invoke.cont3
+
+invoke.cont2:                                     ; preds = %catch
+  call void @llvm.eh.endcatch()
+  br label %try.cont
+
+invoke.cont3:                                     ; preds = %catch
+  br label %eh.resume
+
+try.cont:                                         ; preds = %invoke.cont2, %entry
+  ret void
+
+eh.resume:                                        ; preds = %catch.dispatch
+  %lpad.val = insertvalue { i8*, i32 } undef, i32 0, 1
+  resume { i8*, i32 } %lpad.val
+}
+
+declare void @_Z9may_throwv()
+
+declare i32 @__CxxFrameHandler3(...)
+
+; Function Attrs: nounwind readnone
+declare i32 @llvm.eh.typeid.for(i8*)
+
+declare void @_Z10handle_intv()
+