[WinEH] Disallow cyclic unwinds

[JosephTremoulet]

Summary

Funclet-based EH personalities/tables likely can't handle these, and they
can't be generated at source, so make them officially illegal in IR as
well.

[majnemer]

LGTM

[JosephTremoulet]

rebase

docs/ExceptionHandling.rst

 implies that for any given ``catchswitch``, its unwind destination must also
 be the unwind destination of any unwind edge that exits any of its constituent
 ``catchpad``\s.  Because ``catchswitch`` has no ``nounwind`` variant, and
 because IR producers are not *required* to annotate calls which will not
 unwind as ``nounwind``, it is legal to nest a ``call`` or an "``unwind to
 caller``\ " ``catchswitch`` within a funclet pad that has an unwind
 destination other than caller; it is undefined behavior for such a ``call``
 or ``catchswitch`` to unwind.
+
+Finally, the funclet pads' unwind destinations cannot form a cycle.  This
+ensures that EH lowering can construct "try regions" with a tree-like
+structure, which funclet-based personalities may require.

lib/IR/Verifier.cpp

 //  * A landingpad instruction must be the first non-PHI instruction in the
 //    block.
 //  * Landingpad instructions must be in a function with a personality function.
 //  * All other things that are tested by asserts spread about the code...
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/Verifier.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/CallingConv.h"
private:
   }
 
   void Write(const Comdat *C) {
     if (!C)
       return;
     OS << *C;
   }
 
+  template <typename T> void Write(ArrayRef<T> Vs) {
+    for (const T &V : Vs)
+      Write(V);
+  }
+
   template <typename T1, typename... Ts>
   void WriteTs(const T1 &V1, const Ts &... Vs) {
     Write(V1);
     WriteTs(Vs...);
   }
 
   template <typename... Ts> void WriteTs() {}
 
class Verifier : public InstVisitor<Verifier>, VerifierSupport {
   /// \brief Whether we've seen a call to @llvm.localescape in this function
   /// already.
   bool SawFrameEscape;
 
   /// Stores the count of how many objects were passed to llvm.localescape for a
   /// given function and the largest index passed to llvm.localrecover.
   DenseMap<Function *, std::pair<unsigned, unsigned>> FrameEscapeInfo;
 
+  // Maps catchswitches and cleanuppads that unwind to siblings to the
+  // terminators that indicate the unwind, used to detect cycles therein.
+  MapVector<Instruction *, TerminatorInst *> SiblingFuncletInfo;
+
   /// Cache of constants visited in search of ConstantExprs.
   SmallPtrSet<const Constant *, 32> ConstantExprVisited;
 
   void checkAtomicMemAccessSize(const Module *M, Type *Ty,
                                 const Instruction *I);
 public:
   explicit Verifier(raw_ostream &OS)
       : VerifierSupport(OS), Context(nullptr), LandingPadResultTy(nullptr),
bool verify(const Function &F) {
     // out-of-date dominator tree and makes it significantly more complex to
     // run this code outside of a pass manager.
     // FIXME: It's really gross that we have to cast away constness here.
     DT.recalculate(const_cast<Function &>(F));
 
     Broken = false;
     // FIXME: We strip const here because the inst visitor strips const.
     visit(const_cast<Function &>(F));
+    verifySiblingFuncletUnwinds();
     InstsInThisBlock.clear();
     LandingPadResultTy = nullptr;
     SawFrameEscape = false;
+    SiblingFuncletInfo.clear();
 
     return !Broken;
   }
 
   bool verify(const Module &M) {
     this->M = &M;
     Context = &M.getContext();
     Broken = false;
void VerifyFunctionAttrs(FunctionType *FT, AttributeSet Attrs,
                            const Value *V);
   void VerifyFunctionMetadata(
       const SmallVector<std::pair<unsigned, MDNode *>, 4> MDs);
 
   void visitConstantExprsRecursively(const Constant *EntryC);
   void visitConstantExpr(const ConstantExpr *CE);
   void VerifyStatepoint(ImmutableCallSite CS);
   void verifyFrameRecoverIndices();
+  void verifySiblingFuncletUnwinds();
 
   // Module-level debug info verification...
   void verifyTypeRefs();
   template <class MapTy>
   void verifyBitPieceExpression(const DbgInfoIntrinsic &I,
                                 const MapTy &TypeRefs);
   void visitUnresolvedTypeRef(const MDString *S, const MDNode *N);
 };
for (auto &Counts : FrameEscapeInfo) {
     Assert(MaxRecoveredIndex <= EscapedObjectCount,
            "all indices passed to llvm.localrecover must be less than the "
            "number of arguments passed ot llvm.localescape in the parent "
            "function",
            F);
   }
 }
 
+static Instruction *getSuccPad(TerminatorInst *Terminator) {
+  BasicBlock *UnwindDest;
+  if (auto *II = dyn_cast<InvokeInst>(Terminator))
+    UnwindDest = II->getUnwindDest();
+  else if (auto *CSI = dyn_cast<CatchSwitchInst>(Terminator))
+    UnwindDest = CSI->getUnwindDest();
+  else
+    UnwindDest = cast<CleanupReturnInst>(Terminator)->getUnwindDest();
+  return UnwindDest->getFirstNonPHI();
+}
+
+void Verifier::verifySiblingFuncletUnwinds() {
+  SmallPtrSet<Instruction *, 8> Visited;
+  SmallPtrSet<Instruction *, 8> Active;
+  for (const auto &Pair : SiblingFuncletInfo) {
+    Instruction *PredPad = Pair.first;
+    if (Visited.count(PredPad))
+      continue;
+    Active.insert(PredPad);
+    TerminatorInst *Terminator = Pair.second;
+    do {
+      Instruction *SuccPad = getSuccPad(Terminator);
+      if (Active.count(SuccPad)) {
+        // Found a cycle; report error
+        Instruction *CyclePad = SuccPad;
+        SmallVector<Instruction *, 8> CycleNodes;
+        do {
+          CycleNodes.push_back(CyclePad);
+          TerminatorInst *CycleTerminator = SiblingFuncletInfo[CyclePad];
+          if (CycleTerminator != CyclePad)
+            CycleNodes.push_back(CycleTerminator);
+          CyclePad = getSuccPad(CycleTerminator);
+        } while (CyclePad != SuccPad);
+        Assert(false, "EH pads can't handle each other's exceptions",
+               ArrayRef<Instruction *>(CycleNodes));
+      }
+      // Don't re-walk a node we've already checked
+      if (!Visited.insert(SuccPad).second)
+        break;
+      // Walk to this successor if it has a map entry.
+      PredPad = SuccPad;
+      auto TermI = SiblingFuncletInfo.find(PredPad);
+      if (TermI == SiblingFuncletInfo.end())
+        break;
+      Terminator = TermI->second;
+      Active.insert(PredPad);
+    } while (true);
+    // Each node only has one successor, so we've walked all the active
+    // nodes' successors.
+    Active.clear();
+  }
+}
+
 // visitFunction - Verify that a function is ok.
 //
 void Verifier::visitFunction(const Function &F) {
   // Check function arguments.
   FunctionType *FT = F.getFunctionType();
   unsigned NumArgs = F.arg_size();
 
   Assert(Context == &F.getContext(),
for (User *U : CurrentPad->users()) {
         if (FirstUser) {
           Assert(UnwindPad == FirstUnwindPad, "Unwind edges out of a funclet "
                                               "pad must have the same unwind "
                                               "dest",
                  &FPI, U, FirstUser);
         } else {
           FirstUser = U;
           FirstUnwindPad = UnwindPad;
+          // Record cleanup sibling unwinds for verifySiblingFuncletUnwinds
+          if (isa<CleanupPadInst>(&FPI) && !isa<ConstantTokenNone>(UnwindPad) &&
+              getParentPad(UnwindPad) == getParentPad(&FPI))
+            SiblingFuncletInfo[&FPI] = cast<TerminatorInst>(U);
         }
       }
       // Make sure we visit all uses of FPI, but for nested pads stop as
       // soon as we know where they unwind to.
       if (CurrentPad != &FPI)
         break;
     }
     if (UnresolvedAncestorPad) {
Assert(F->hasPersonalityFn(),
          &CatchSwitch);
 
   // The catchswitch instruction must be the first non-PHI instruction in the
   // block.
   Assert(BB->getFirstNonPHI() == &CatchSwitch,
          "CatchSwitchInst not the first non-PHI instruction in the block.",
          &CatchSwitch);
 
+  auto *ParentPad = CatchSwitch.getParentPad();
+  Assert(isa<ConstantTokenNone>(ParentPad) || isa<FuncletPadInst>(ParentPad),
+         "CatchSwitchInst has an invalid parent.", ParentPad);
+
   if (BasicBlock *UnwindDest = CatchSwitch.getUnwindDest()) {
     Instruction *I = UnwindDest->getFirstNonPHI();
     Assert(I->isEHPad() && !isa<LandingPadInst>(I),
            "CatchSwitchInst must unwind to an EH block which is not a "
            "landingpad.",
            &CatchSwitch);
-  }
 
-  auto *ParentPad = CatchSwitch.getParentPad();
-  Assert(isa<ConstantTokenNone>(ParentPad) || isa<FuncletPadInst>(ParentPad),
-         "CatchSwitchInst has an invalid parent.", ParentPad);
+    // Record catchswitch sibling unwinds for verifySiblingFuncletUnwinds
+    if (getParentPad(I) == ParentPad)
+      SiblingFuncletInfo[&CatchSwitch] = &CatchSwitch;
+  }
 
   Assert(CatchSwitch.getNumHandlers() != 0,
          "CatchSwitchInst cannot have empty handler list", &CatchSwitch);
 
   for (BasicBlock *Handler : CatchSwitch.handlers()) {
     Assert(isa<CatchPadInst>(Handler->getFirstNonPHI()),
            "CatchSwitchInst handlers must be catchpads", &CatchSwitch, Handler);
   }

test/CodeGen/WinEH/wineh-cloning.ll

 ; CHECK:      inner:
 ; CHECK-NEXT:   %i = catchpad within %cs []
 ; CHECK-NEXT:   catchret from %i to label %outer.post-inner
 ; CHECK:      outer.post-inner:
 ; CHECK-NEXT:   call void @llvm.foo(i32 %x)
 ; CHECK-NEXT:   br label %outer.ret
 
 
-define void @test9() personality i32 (...)* @__C_specific_handler {
-entry:
-  invoke void @f()
-    to label %invoke.cont unwind label %left
-invoke.cont:
-  invoke void @f()
-    to label %unreachable unwind label %right
-left:
-  %cp.left = cleanuppad within none []
-  call void @llvm.foo(i32 1)
-  invoke void @f() [ "funclet"(token %cp.left) ]
-    to label %unreachable unwind label %right
-right:
-  %cp.right = cleanuppad within none []
-  call void @llvm.foo(i32 2)
-  invoke void @f() [ "funclet"(token %cp.right) ]
-    to label %unreachable unwind label %left
-unreachable:
-  unreachable
-}
-; This is an irreducible loop with two funclets that enter each other.
-; CHECK-LABEL: define void @test9(
-; CHECK:     entry:
-; CHECK:               to label %invoke.cont unwind label %[[LEFT:.+]]
-; CHECK:     invoke.cont:
-; CHECK:               to label %[[UNREACHABLE_ENTRY:.+]] unwind label %[[RIGHT:.+]]
-; CHECK:     [[LEFT]]:
-; CHECK:       call void @llvm.foo(i32 1)
-; CHECK:       invoke void @f()
-; CHECK:               to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[RIGHT]]
-; CHECK:     [[RIGHT]]:
-; CHECK:       call void @llvm.foo(i32 2)
-; CHECK:       invoke void @f()
-; CHECK:               to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[LEFT]]
-; CHECK:     [[UNREACHABLE_RIGHT]]:
-; CHECK:       unreachable
-; CHECK:     [[UNREACHABLE_LEFT]]:
-; CHECK:       unreachable
-; CHECK:     [[UNREACHABLE_ENTRY]]:
-; CHECK:       unreachable
-
-
 define void @test10() personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   invoke void @f()
     to label %unreachable unwind label %inner
 inner:
   %cleanup = cleanuppad within none []
   ; make sure we don't overlook this cleanupret and try to process
   ; successor %outer as a child of inner.

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
 ; RUN: sed -e s/.T13:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK13 %s
 ; RUN: sed -e s/.T14:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK14 %s
 ; RUN: sed -e s/.T15:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK15 %s
 ; RUN: sed -e s/.T16:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK16 %s
+; RUN: sed -e s/.T17:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK17 %s
+; RUN: sed -e s/.T18:// %s | not opt -verify -disable-output 2>&1 | FileCheck --check-prefix=CHECK18 %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:

 ;T16:     unreachable
 ;T16:   target1:
 ;T16:     cleanuppad within none []
 ;T16:     unreachable
 ;T16:   target2:
 ;T16:     cleanuppad within none []
 ;T16:     unreachable
 ;T16: }
+
+;T17: define void @f() personality void ()* @g {
+;T17:   entry:
+;T17:     invoke void @g()
+;T17:       to label %invoke.cont unwind label %left
+;T17:   invoke.cont:
+;T17:     invoke void @g()
+;T17:       to label %unreachable unwind label %right
+;T17:   left:
+;T17:     %cp.left = cleanuppad within none []
+;T17:     invoke void @g() [ "funclet"(token %cp.left) ]
+;T17:       to label %unreachable unwind label %right
+;T17:   right:
+;T17:     %cp.right = cleanuppad within none []
+;T17:     invoke void @g() [ "funclet"(token %cp.right) ]
+;T17:       to label %unreachable unwind label %left
+;T17:     ; CHECK17: EH pads can't handle each other's exceptions
+;T17:     ; CHECK17-NEXT: %cp.left = cleanuppad within none []
+;T17:     ; CHECK17-NEXT:  invoke void @g() [ "funclet"(token %cp.left) ]
+;T17:     ; CHECK17-NEXT:          to label %unreachable unwind label %right
+;T17:     ; CHECK17-NEXT:  %cp.right = cleanuppad within none []
+;T17:     ; CHECK17-NEXT:  invoke void @g() [ "funclet"(token %cp.right) ]
+;T17:     ; CHECK17-NEXT:          to label %unreachable unwind label %left
+;T17:   unreachable:
+;T17:     unreachable
+;T17: }
+
+;T18: define void @f() personality void ()* @g {
+;T18:   entry:
+;T18:     ret void
+;T18:   red:
+;T18:     %redpad = cleanuppad within none []
+;T18:     unreachable
+;T18:   red.inner:
+;T18:     %innerpad = cleanuppad within %redpad []
+;T18:     invoke void @g() [ "funclet"(token %innerpad) ]
+;T18:       to label %unreachable unwind label %green
+;T18:   green:
+;T18:     %greenswitch = catchswitch within none [label %catch] unwind label %blue
+;T18:   catch:
+;T18:     catchpad within %greenswitch [i32 42]
+;T18:     unreachable
+;T18:   blue:
+;T18:     %bluepad = cleanuppad within none []
+;T18:     cleanupret from %bluepad unwind label %red
+;T18:     ; CHECK18: EH pads can't handle each other's exceptions
+;T18:     ; CHECK18-NEXT: %redpad = cleanuppad within none []
+;T18:     ; CHECK18-NEXT: invoke void @g() [ "funclet"(token %innerpad) ]
+;T18:     ; CHECK18-NEXT:         to label %unreachable unwind label %green
+;T18:     ; CHECK18-NEXT: %greenswitch = catchswitch within none [label %catch] unwind label %blue
+;T18:     ; CHECK18-NEXT: %bluepad = cleanuppad within none []
+;T18:     ; CHECK18-NEXT: cleanupret from %bluepad unwind label %red
+;T18:   unreachable:
+;T18:     unreachable
+;T18: }