[WinEH] Verify unwind edges against EH pad tree

[JosephTremoulet]

Summary

Funclet EH personalities require a tree-like nesting among funclets
(enforced by the ParentPad linkage in the IR), and also require that
unwind edges conform to certain rules with respect to the tree:

• An unwind edge may exit 0 or more ancestor pads
• An unwind edge must enter exactly one EH pad, which must be distinct from any exited pads
• A cleanupret's edge must exit its cleanuppad

Describe these rules in the LangRef, and enforce them in the verifier.

[majnemer]

LGTM

lib/IR/Verifier.cpp

2953

Would this be the same as FromPad = CSI; ? I'm not advocating one form over the other, just curious for my own edification. If I understand correctly, it would also imply that a catchswitch cannot unwind to itself.

[andrew.w.kaylor]

docs/ExceptionHandling.rst

801

I found this line confusing. The cleanupret and catchswitch parts of the parenthetical clause seem to be redundant, having already been covered by previous statements, so it took me a bit to figure out how they related here to the call statement. I also think it would be better to leave the explicit verbiage explaining that a call may unwind to the parent function -- "implicitly via a call (which unwinds all the way to the current function's caller)".

docs/LangRef.rst

5597

This would read better as "beginning with either a cleanuppad or catchswitch instruction".

5598

Should "must have..." here be "must be..."?

lib/IR/Verifier.cpp

2937

Won't this be the same as the 'I' argument?

[JosephTremoulet]

address review feedback

[JosephTremoulet]

Feedback addressed.

docs/ExceptionHandling.rst

801

Updated

docs/LangRef.rst

5597

Updated (here and catchswitch)

5598

Changed from "unwind edge must have a legal target" to "unwind destination must be a legal target" (here and catchswitch)

lib/IR/Verifier.cpp

2937

Yep, thanks; kept the ToPad name to help readability below, but assigned from &I and rewrote appearances of &I to ToPad below.

2962

Sounds like you're understanding correctly. I thought about it, and think it's preferable to use CSI and catch the self-switch case here, so I've updated to do so and included a test. Also realized looking at this that we're allowing catchswitches to target their child catchpads, so added a check for that in D16011.

[andrew.w.kaylor]

Looks good.

docs/ExceptionHandling.rst

try.cont6:                                        ; preds = %try.cont
     ret void
 
   unreachable:                                      ; preds = %catch, %entry
     unreachable
   }
 
 The "inner" ``catchswitch`` consumes ``%1`` which is produced by the outer
 catchswitch.
+
+.. _wineh-constraints:
+
+Funclet transitions
+-----------------------
+
+The EH tables for personalities that use funclets make implicit use of the
+funclet nesting relationship to encode unwind destinations, and so are
+constrained in the set of funclet transitions they can represent.  The related
+LLVM IR instructions accordingly have constraints that ensure encodability of
+the EH edges in the flow graph.
+
+A ``catchswitch``, ``catchpad``, or ``cleanuppad`` is said to be "entered"
+when it executes.  It may subsequently be "exited" by any of the following
+means:
+
+* A ``catchswitch`` is immediately exited when none of its constituent
+  ``catchpad``\ s are appropriate for the in-flight exception and it unwinds
+  to its unwind destination or the caller.
+* A ``catchpad`` and its parent ``catchswitch`` are both exited when a
+  ``catchret`` from the ``catchpad`` is executed.
+* A ``cleanuppad`` is exited when a ``cleanupret`` from it is executed.
+* Any of these pads is exited when control unwinds to the function's caller
+  (by a ``call``, ``cleanupret``, or ``catchswitch``).
+* Any of these pads is exited when an unwind edge (from an ``invoke``,
+  ``cleanupret``, or ``catchswitch``) unwinds to a destination pad that is not
+  a descendant of the given pad.
+
+Note that the ``ret`` instruction is *not* a valid way to exit a funclet pad;
+it is undefined behavior to execute a ``ret`` when a pad has been entered but
+not exited.
+
+A single unwind edge may exit any number of pads (with the restrictions that
+the edge from a ``catchswitch`` must exit at least itself, and the edge from
+a ``cleanupret`` must exit at least its ``cleanuppad``), and then must enter
+exactly one pad, which must be distinct from all the exited pads.  The parent
+of the pad that an unwind edge enters must be the most-recently-entered
+not-yet-exited pad (after exiting from any pads that the unwind edge exits),
+or "none" if there is no such pad.  This ensures that the stack of executing
+funclets at run-time always corresponds to some path in the funclet pad tree
+that the parent tokens encode.

docs/LangRef.rst

.. code-block:: llvm
     }
 
 It is the frontend's responsibility to structure or encode the
 deoptimization state in a way that syntactically prepending the
 caller's deoptimization state to the callee's deoptimization state is
 semantically equivalent to composing the caller's deoptimization
 continuation after the callee's deoptimization continuation.
 
+.. _ob_funclet:
+
 Funclet Operand Bundles
 ^^^^^^^^^^^^^^^^^^^^^^^
 
 Funclet operand bundles are characterized by the ``"funclet"``
 operand bundle tag.  These operand bundles indicate that a call site
 is within a particular funclet.  There can be at most one
 ``"funclet"`` operand bundle attached to a call site and it must have
 exactly one bundle operand.
 
+If any funclet EH pads have been "entered" but not "exited" (per the
+`description in the EH doc\ <ExceptionHandling.html#wineh-constraints>`_),
+it is undefined behavior to execute a ``call`` or ``invoke`` which:
+
+* does not have a ``"funclet"`` bundle and is not a ``call`` to a nounwind
+  intrinsic, or
+* has a ``"funclet"`` bundle whose operand is not the most-recently-entered
+  not-yet-exited funclet EH pad.
+
+Similarly, if no funclet EH pads have been entered-but-not-yet-exited,
+executing a ``call`` or ``invoke`` with a ``"funclet"`` bundle is undefined behavior.
+
 .. _moduleasm:
 
 Module-Level Inline Assembly
 ----------------------------
 
 Modules may contain "module-level inline asm" blocks, which corresponds
 to the GCC "file scope inline asm" blocks. These blocks are internally
 concatenated by LLVM and treated as a single unit, but may be separated

 Arguments:
 """"""""""
 
 The ``parent`` argument is the token of the funclet that contains the
 ``catchswitch`` instruction. If the ``catchswitch`` is not inside a funclet,
 this operand may be the token ``none``.
 
 The ``default`` argument is the label of another basic block beginning with a
-"pad" instruction, one of ``cleanuppad`` or ``catchswitch``.
+"pad" instruction, one of ``cleanuppad`` or ``catchswitch``.  This unwind edge
+must have a legal target with respect to the ``parent`` links, as described in
+the `exception handling documentation\ <ExceptionHandling.html#wineh-constraints>`_.
 
-The ``handlers`` are a list of successor blocks that each begin with a
+The ``handlers`` are a nonempty list of successor blocks that each begin with a
 :ref:`catchpad <i_catchpad>` instruction.
 
 Semantics:
 """"""""""
 
 Executing this instruction transfers control to one of the successors in
 ``handlers``, if appropriate, or continues to unwind via the unwind label if
 present.

 not reach the ``catchpad`` instruction.  The representation of ``args`` is
 entirely target and personality function-specific.
 
 Like the :ref:`landingpad <i_landingpad>` instruction, the ``catchpad``
 instruction must be the first non-phi of its parent basic block.
 
 The meaning of the tokens produced and consumed by ``catchpad`` and other "pad"
 instructions is described in the
-`Windows exception handling documentation <ExceptionHandling.html#wineh>`.
+`Windows exception handling documentation\ <ExceptionHandling.html#wineh>`_.
 
-Executing a ``catchpad`` instruction constitutes "entering" that pad.
-The pad may then be "exited" in one of three ways:
-
-1)  explicitly via a ``catchret`` that consumes it.  Executing such a ``catchret``
-    is undefined behavior if any descendant pads have been entered but not yet
-    exited.
-2)  implicitly via a call (which unwinds all the way to the current function's caller),
-    or via a ``catchswitch`` or a ``cleanupret`` that unwinds to caller.
-3)  implicitly via an unwind edge whose destination EH pad isn't a descendant of
-    the ``catchpad``.  When the ``catchpad`` is exited in this manner, it is
-    undefined behavior if the destination EH pad has a parent which is not an
-    ancestor of the ``catchpad`` being exited.
+When a ``catchpad`` has been "entered" but not yet "exited" (as
+described in the `EH documentation\ <ExceptionHandling.html#wineh-constraints>`_),
+it is undefined behavior to execute a :ref:`call <i_call>` or :ref:`invoke <i_invoke>`
+that does not carry an appropriate :ref:`"funclet" bundle <ob_funclet>`.
 
 Example:
 """"""""
 
 .. code-block:: llvm
 
     dispatch:
       %cs = catchswitch within none [label %handler0] unwind to caller

 """"""""""
 
 The '``catchret``' instruction ends an existing (in-flight) exception whose
 unwinding was interrupted with a :ref:`catchpad <i_catchpad>` instruction.  The
 :ref:`personality function <personalityfn>` gets a chance to execute arbitrary
 code to, for example, destroy the active exception.  Control then transfers to
 ``normal``.
 
-The ``token`` argument must be a token produced by a dominating ``catchpad``
-instruction. The ``catchret`` destroys the physical frame established by
-``catchpad``, so executing multiple returns on the same token without
-re-executing the ``catchpad`` will result in undefined behavior.
-See :ref:`catchpad <i_catchpad>` for more details.
+The ``token`` argument must be a token produced by a ``catchpad`` instruction.
+If the specified ``catchpad`` is not the most-recently-entered not-yet-exited
+funclet pad (as described in the `EH documentation\ <ExceptionHandling.html#wineh-constraints>`_),
+the ``catchret``'s behavior is undefined.
 
 Example:
 """"""""
 
 .. code-block:: llvm
 
       catchret from %catch label %continue
 

 an optional successor.
 
 
 Arguments:
 """"""""""
 
 The '``cleanupret``' instruction requires one argument, which indicates
 which ``cleanuppad`` it exits, and must be a :ref:`cleanuppad <i_cleanuppad>`.
-It also has an optional successor, ``continue``.
+If the specified ``cleanuppad`` is not the most-recently-entered not-yet-exited
+funclet pad (as described in the `EH documentation\ <ExceptionHandling.html#wineh-constraints>`_),
+the ``cleanupret``'s behavior is undefined.
+
+The '``cleanupret``' instruction also has an optional successor, ``continue``,
+which must be the label of another basic block beginning with a
+"pad" instruction, one of ``cleanuppad`` or ``catchswitch``.  This unwind edge
+must have a legal target with respect to the ``parent`` links, as described in
+the `exception handling documentation\ <ExceptionHandling.html#wineh-constraints>`_.
 
 Semantics:
 """"""""""
 
 The '``cleanupret``' instruction indicates to the
 :ref:`personality function <personalityfn>` that one
 :ref:`cleanuppad <i_cleanuppad>` it transferred control to has ended.
 It transfers control to ``continue`` or unwinds out of the function.
 
-The unwind destination ``continue``, if present, must be an EH pad
-whose parent is either ``none`` or an ancestor of the ``cleanuppad``
-being returned from.  This constitutes an exceptional exit from all
-ancestors of the completed ``cleanuppad``, up to but not including
-the parent of ``continue``.
-See :ref:`cleanuppad <i_cleanuppad>` for more details.
-
 Example:
 """"""""
 
 .. code-block:: llvm
 
       cleanupret from %cleanup unwind to caller
       cleanupret from %cleanup unwind label %continue
 
-  A cleanup block is a basic block which is the unwind destination of
    an exceptional instruction.
 -  A cleanup block must have a '``cleanuppad``' instruction as its
    first non-PHI instruction.
 -  There can be only one '``cleanuppad``' instruction within the
    cleanup block.
 -  A basic block that is not a cleanup block may not include a
    '``cleanuppad``' instruction.
 
-Executing a ``cleanuppad`` instruction constitutes "entering" that pad.
-The pad may then be "exited" in one of three ways:
-
-1)  explicitly via a ``cleanupret`` that consumes it.  Executing such a ``cleanupret``
-    is undefined behavior if any descendant pads have been entered but not yet
-    exited.
-2)  implicitly via a call (which unwinds all the way to the current function's caller),
-    or via a ``catchswitch`` or a ``cleanupret`` that unwinds to caller.
-3)  implicitly via an unwind edge whose destination EH pad isn't a descendant of
-    the ``cleanuppad``.  When the ``cleanuppad`` is exited in this manner, it is
-    undefined behavior if the destination EH pad has a parent which is not an
-    ancestor of the ``cleanuppad`` being exited.
+When a ``cleanuppad`` has been "entered" but not yet "exited" (as
+described in the `EH documentation\ <ExceptionHandling.html#wineh-constraints>`_),
+it is undefined behavior to execute a :ref:`call <i_call>` or :ref:`invoke <i_invoke>`
+that does not carry an appropriate :ref:`"funclet" bundle <ob_funclet>`.
 
 It is undefined behavior for the ``cleanuppad`` to exit via an unwind edge which
 does not transitively unwind to the same destination as a constituent
 ``cleanupret``.
 
 Example:
 """"""""
 

lib/IR/Verifier.cpp

void Verifier::visitInsertValueInst(InsertValueInst &IVI) {
   Assert(ExtractValueInst::getIndexedType(IVI.getAggregateOperand()->getType(),
                                           IVI.getIndices()) ==
              IVI.getOperand(1)->getType(),
          "Invalid InsertValueInst operands!", &IVI);
 
   visitInstruction(IVI);
 }
 
+static Value *getParentPad(Value *EHPad) {
+  if (auto *FPI = dyn_cast<FuncletPadInst>(EHPad))
+    return FPI->getParentPad();
+
+  return cast<CatchSwitchInst>(EHPad)->getParentPad();
+}
+
 void Verifier::visitEHPadPredecessors(Instruction &I) {
   assert(I.isEHPad());
 
   BasicBlock *BB = I.getParent();
   Function *F = BB->getParent();
 
   Assert(BB != &F->getEntryBlock(), "EH pad cannot be in entry block.", &I);
 
if (auto *CPI = dyn_cast<CatchPadInst>(&I)) {
     if (!pred_empty(BB))
       Assert(BB->getUniquePredecessor() == CPI->getCatchSwitch()->getParent(),
              "Block containg CatchPadInst must be jumped to "
              "only by its catchswitch.",
              CPI);
     return;
   }
 
+  // Verify that each pred has a legal terminator with a legal to/from EH
+  // pad relationship.
+  Instruction *ToPad = BB->getFirstNonPHI();
+  Value *ToPadParent = getParentPad(ToPad);
   for (BasicBlock *PredBB : predecessors(BB)) {
     TerminatorInst *TI = PredBB->getTerminator();
+    Value *FromPad;
     if (auto *II = dyn_cast<InvokeInst>(TI)) {
       Assert(II->getUnwindDest() == BB && II->getNormalDest() != BB,
              "EH pad must be jumped to via an unwind edge", &I, II);
-    } else if (!isa<CleanupReturnInst>(TI) && !isa<CatchSwitchInst>(TI)) {
+      if (auto Bundle = II->getOperandBundle(LLVMContext::OB_funclet))
+        FromPad = Bundle->Inputs[0];
+      else
+        FromPad = ConstantTokenNone::get(II->getContext());
+    } else if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
+      FromPad = CRI->getCleanupPad();
+      Assert(FromPad != ToPadParent, "A cleanupret must exit its cleanup", CRI);
+    } else if (auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
+      FromPad = CSI->getParentPad();
+    } else {
       Assert(false, "EH pad must be jumped to via an unwind edge", &I, TI);
     }
+
+    // The edge may exit from zero or more nested pads.
+    for (;; FromPad = getParentPad(FromPad)) {
+      Assert(FromPad != ToPad,
+             "EH pad cannot handle exceptions raised within it", FromPad, TI);
+      if (FromPad == ToPadParent) {
+        // This is a legal unwind edge.
+        break;
+      }
+      Assert(!isa<ConstantTokenNone>(FromPad),
+             "A single unwind edge may only enter one EH pad", TI);
+    }
   }
 }
 
 void Verifier::visitLandingPadInst(LandingPadInst &LPI) {
   // The landingpad instruction is ill-formed if it doesn't have any clauses and
   // isn't a cleanup.
   Assert(LPI.getNumClauses() > 0 || LPI.isCleanup(),
          "LandingPadInst needs at least one clause or to be a cleanup.", &LPI);

test/Bitcode/compatibility.ll

 
 catchpad:
   %catch = catchpad within %cs []
   br label %body
   ; CHECK: %catch = catchpad within %cs []
   ; CHECK-NEXT: br label %body
 
 body:
-  invoke void @f.ccc() to label %continue unwind label %terminate.inner
+  invoke void @f.ccc() [ "funclet"(token %catch) ]
+    to label %continue unwind label %terminate.inner
   catchret from %catch to label %return
   ; CHECK: catchret from %catch to label %return
 
 return:
   ret i32 0
 
 terminate.inner:
   cleanuppad within %catch []

test/Feature/exception.ll

 }
 
 ; forward ref by name
 define void @cleanupret1() personality i32 (...)* @__gxx_personality_v0 {
 entry:
   invoke void @_Z3quxv() optsize
           to label %exit unwind label %pad
 cleanup:
-  cleanupret from %cp unwind label %pad
+  cleanupret from %cp unwind to caller
 pad:
   %cp = cleanuppad within none []
   br label %cleanup
 exit:
   ret void
 }
 
 ; forward ref by ID
 define void @cleanupret2() personality i32 (...)* @__gxx_personality_v0 {
 entry:
   invoke void @_Z3quxv() optsize
           to label %exit unwind label %pad
 cleanup:
-  cleanupret from %0 unwind label %pad
+  cleanupret from %0 unwind to caller
 pad:
   %0 = cleanuppad within none []
   br label %cleanup
 exit:
   ret void
 }
 
 define void @catchret0() personality i32 (...)* @__gxx_personality_v0 {

test/Verifier/invalid-eh.ll

 ; RUN: sed -e s/.T1:// %s | not llvm-as -disable-output 2>&1 | FileCheck --check-prefix=CHECK1 %s
 ; RUN: sed -e s/.T2:// %s | not llvm-as -disable-output 2>&1 | FileCheck --check-prefix=CHECK2 %s
 ; RUN: sed -e s/.T3:// %s | not llvm-as -disable-output 2>&1 | FileCheck --check-prefix=CHECK3 %s
 ; RUN: sed -e s/.T4:// %s | not llvm-as -disable-output 2>&1 | FileCheck --check-prefix=CHECK4 %s
 ; RUN: sed -e s/.T5:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK5 %s
 ; RUN: sed -e s/.T6:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK6 %s
 ; RUN: sed -e s/.T7:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK7 %s
 ; RUN: sed -e s/.T8:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK8 %s
+; RUN: sed -e s/.T9:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK9 %s
+; RUN: sed -e s/.T10:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK10 %s
+; RUN: sed -e s/.T11:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK11 %s
+; RUN: sed -e s/.T12:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK12 %s
 
 declare void @g()
 
 ;T1: define void @f() {
 ;T1:   entry:
 ;T1:     catchret from undef to label %next
 ;T1:     ; CHECK1: CatchReturnInst needs to be provided a CatchPad
 ;T1:   next:

 
 ;T8: define void @f() personality void ()* @g {
 ;T8:   entry:
 ;T8:     ret void
 ;T8:   switch1:
 ;T8:     %cs1 = catchswitch within none [ label %switch1 ] unwind to caller
 ;T8:     ; CHECK8: CatchSwitchInst handlers must be catchpads
 ;T8: }
+
+;T9: define void @f() personality void ()* @g {
+;T9:   entry:
+;T9:     ret void
+;T9:   cleanup:
+;T9:     %cp = cleanuppad within none []
+;T9:     invoke void @g() [ "funclet"(token %cp) ]
+;T9:       to label %exit unwind label %cleanup
+;T9:       ; CHECK9: EH pad cannot handle exceptions raised within it
+;T9:       ; CHECK9-NEXT: %cp = cleanuppad within none []
+;T9:       ; CHECK9-NEXT: invoke void @g() [ "funclet"(token %cp) ]
+;T9:   exit:
+;T9:     ret void
+;T9: }
+
+;T10: define void @f() personality void ()* @g {
+;T10:   entry:
+;T10:     ret void
+;T10:   cleanup1:
+;T10:     %cp1 = cleanuppad within none []
+;T10:     unreachable
+;T10:   switch:
+;T10:     %cs = catchswitch within %cp1 [label %catch] unwind to caller
+;T10:   catch:
+;T10:     %catchp1 = catchpad within %cs [i32 1]
+;T10:     unreachable
+;T10:   cleanup2:
+;T10:     %cp2 = cleanuppad within %catchp1 []
+;T10:     unreachable
+;T10:   cleanup3:
+;T10:     %cp3 = cleanuppad within %cp2 []
+;T10:     cleanupret from %cp3 unwind label %switch
+;T10:       ; CHECK10: EH pad cannot handle exceptions raised within it
+;T10:       ; CHECK10-NEXT: %cs = catchswitch within %cp1 [label %catch] unwind to caller
+;T10:       ; CHECK10-NEXT: cleanupret from %cp3 unwind label %switch
+;T10: }
+
+;T11: define void @f() personality void ()* @g {
+;T11:   entry:
+;T11:     ret void
+;T11:   cleanup1:
+;T11:     %cp1 = cleanuppad within none []
+;T11:     unreachable
+;T11:   cleanup2:
+;T11:     %cp2 = cleanuppad within %cp1 []
+;T11:     unreachable
+;T11:   switch:
+;T11:     %cs = catchswitch within none [label %catch] unwind label %cleanup2
+;T11:     ; CHECK11: A single unwind edge may only enter one EH pad
+;T11:     ; CHECK11-NEXT: %cs = catchswitch within none [label %catch] unwind label %cleanup2
+;T11:   catch:
+;T11:     catchpad within %cs [i32 1]
+;T11:     unreachable
+;T11: }
+
+;T12: define void @f() personality void ()* @g {
+;T12:   entry:
+;T12:     ret void
+;T12:   cleanup:
+;T12:     %cp = cleanuppad within none []
+;T12:     cleanupret from %cp unwind label %switch
+;T12:     ; CHECK12: A cleanupret must exit its cleanup
+;T12:     ; CHECK12-NEXT: cleanupret from %cp unwind label %switch
+;T12:   switch:
+;T12:     %cs = catchswitch within %cp [label %catch] unwind to caller
+;T12:   catch:
+;T12:     catchpad within %cs [i32 1]
+;T12:     unreachable
+;T12: }