[WinEH] Update coloring to handle nested cases cleanly

[JosephTremoulet]

Summary

Change the coloring algorithm in WinEHPrepare to visit a funclet's exits
in its parents' contexts and so properly classify the continuations of
nested funclets.

Also change the placement of cloned blocks to be deterministic and to
maintain the relative order of each funclet's blocks.

Add a lit test showing various patterns that require cloning, the last
several of which don't have CHECKs yet because they require cloning
entire funclets which is NYI.

[majnemer]

test/CodeGen/WinEH/wineh-cloning.ll

269–270

When you say each funclet needs to have a single parent, do you mean that it must have a single non-invoke predecessor? It will be quite common for a set of invokes in a try-block to have the same unwind destination.

[JosephTremoulet]

test/CodeGen/WinEH/wineh-cloning.ll

269–270

I mean that all of its invoke predecessors, after cloning, must be in the same funclet.

[JosephTremoulet]

test/CodeGen/WinEH/wineh-cloning.ll

269–270

This might be a more illustrative example:

define void @foo() personality etc {
entry:
  invoke void @f()
    to label %exit unwind label %funcletA
funcletA:
  %A = catchpad []
         to label %bodyA unwind label %endpad
bodyA:
  invoke void @g()
    to label %invoke.cont unwind label %endpad
invoke.cont:
  invoke void @h()
    to label %retA unwind label %funcletB
retA:
  catchret %A to label %exit
funcletB:
  %B = cleanuppad []
  call void @i()
  cleanupret %B unwind to caller
exit:
  ret void
}

Say we enter @foo() and generate a stack frame for it, then the call to @f() raises an exception that is handled by funcletA, so the runtime calls funcletA (and we generate a stack frame for it). Now there are two invokes in funcletA, both of which are handled by funcletB, but if the call to @g() faults the endpad indicates that the runtime needs to unwind out of funcletA before calling funcletB, whereas if the call to @h() faults then the runtime is supposed to invoke funcletB while funcletA's frame is still on the stack. I don't think we can expect WinEH targets to support encoding and executing that arrangement without making two copies of funcletB.
(in the case where the call to @h() faults, the cleanupret that unwinds to caller instead of unwinding to %retA is UB, so we'd want to replace it with unreachable in that copy of funcletB, but I think we still want a copy just in case @h() does not return dynamically and so the program never executes UB; similarly, if the input already had unreachable there instead of a cleanupret, we wouldn't know statically which reporting is correct for funcletB and so I'd think would want two copies of it)

[JosephTremoulet]

test/CodeGen/WinEH/wineh-cloning.ll

269–270

sigh... insert

endpad:
  catchendpad unwind label %funcletB

somewhere in @foo in the previous example.

[majnemer]

test/CodeGen/WinEH/wineh-cloning.ll

269–270

Our langref describes catchendpad using the following language:

The unwind target of invokes between a catchpad and a corresponding catchret must be its catchendpad or an inner EH pad.

It was my understanding that all invokes in a catchpad funclet must transitively unwind to the catchendpad.

Your example would violate this because the catchret in funcletB uses unwinds to caller.

[JosephTremoulet]

test/CodeGen/WinEH/wineh-cloning.ll

269–270

The unwind target of invokes between a catchpad and a corresponding catchret must be its catchendpad or an inner EH pad.

I think that "inner" in that sentence is ill-defined. I also think this would be a difficult invariant for transformations to determine whether they're violating it or not. I think the parts of the langref that describe UB for executing a mismatched ret/catchret/cleanupret/catchendpad get at the same issue and are better defined (or will be once we have cleanupendpad; currently they refer to an ill-defined notion of "unwinding out of a cleanuppad") and more manageable for transformations.

So, for example, I don't know how a (hypothetical) transformation like tail-merge (extended to treat unreachable like some sort of wildcard join with any program point) is supposed to know that it is illegal to transform this:

define void @foo() personality etc {
entry:
  invoke void @f()
    to label %exit unwind label %funcletA
funcletA:
  %A = catchpad []
         to label %bodyA unwind label %endpad
bodyA:
  invoke void @g()
    to label %invoke.cont unwind label %endpad
invoke.cont:
  invoke void @h()
    to label %retA unwind label %funcletB1
retA:
  catchret %A to label %exit
endpad:
  catchendpad unwind label %funcletB2
funcletB1:
  %B1 = cleanuppad []
  call void @i()
  unreachable
funcletB2:
  %B2 = cleanuppad []
  call void @i()
  cleanupret %B2 unwind to caller
exit:
  ret void
}

into the previous example.

Or if that's too far-fetched, what do you think of this example:

define void @foo() personality etc {
entry:
  invoke void @f()
    to label %exit unwind label %funcletA
funcletA:
  %A = catchpad []
         to label %bodyA unwind label %endpad
bodyA:
  invoke void @g()
    to label %invoke.cont unwind label %endpad
invoke.cont:
  invoke void @h()
    to label %retA unwind label %funcletB
retA:
  catchret %A to label %exit
endpad:
  catchendpad unwind label %funcletB
funcletB:
  %B = cleanuppad []
  call void @i()
  unreachable
exit:
  ret void
}

?

[majnemer]

LGTM with nits.

lib/CodeGen/WinEHPrepare.cpp

3101–3103

I think we usually have braces if an inner block uses them.

test/CodeGen/WinEH/wineh-cloning.ll

269–270

I agree that in the face of unreachable, things get problematic for the preparation machinery.

Do you think it would be heroic for WinEHPrepare to eventually handle this?

[JosephTremoulet]

lib/CodeGen/WinEHPrepare.cpp

3101–3103

Ah, good to know. Will fix, thanks.

test/CodeGen/WinEH/wineh-cloning.ll

269–270

Do you think it would be heroic for WinEHPrepare to eventually handle this?

No, I don't think it'll be too bad. One by-product of the coloring algorithm is a directed graph with one node per funclet (plus a root representing the main function), with an edge X -> Y wherever an invoke/catchendpad/cleanupret in X has an unwind edge to the start of Y (i.e. where you'd expect Y to be a an inner funclet nested in X). I think a straightforward walk could construct a tree by "exploding out" joins and exploring all acyclic paths from the root, resulting in a tree where each node has the color of some funclet. Then any funclet whose color appears more than once in the tree could be duplicated, and any affected unwind/catchret edges could be fixed up, so that after cloning we have one funclet for every node in the tree and they could nest like you'd want because it's a tree. I've been debating whether it makes more sense to do exactly that as another pass after the current cloning (which has the appeal that you could skip it in the ~100% of the cases where the original graph is a tree), or whether it would be natural to fold all of the cloning into the graph walk.

lib/CodeGen/WinEHPrepare.cpp

private:
   void
   insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
                  SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);
   AllocaInst *insertPHILoads(PHINode *PN, Function &F);
   void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
                           DenseMap<BasicBlock *, Value *> &Loads, Function &F);
   void demoteNonlocalUses(Value *V, std::set<BasicBlock *> &ColorsForBB,
                           Function &F);
-  bool prepareExplicitEH(Function &F);
-  void numberFunclet(BasicBlock *InitialBB, BasicBlock *FuncletBB);
+  bool prepareExplicitEH(Function &F,
+                         SmallVectorImpl<BasicBlock *> &EntryBlocks);
+  void colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks);
 
   Triple TheTriple;
 
   // All fields are reset by runOnFunction.
   DominatorTree *DT = nullptr;
   const TargetLibraryInfo *LibInfo = nullptr;
   EHPersonality Personality = EHPersonality::Unknown;
   CatchHandlerMapTy CatchHandlerMap;
private:
   // Map from outlined handler to call to parent local address. Only used for
   // 32-bit EH.
   DenseMap<Function *, Value *> HandlerToParentFP;
 
   AllocaInst *SEHExceptionCodeSlot = nullptr;
 
   std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
+  std::map<BasicBlock *, std::set<BasicBlock *>> FuncletChildren;
 };
 
 class WinEHFrameVariableMaterializer : public ValueMaterializer {
 public:
   WinEHFrameVariableMaterializer(Function *OutlinedFn, Value *ParentFP,
                                  FrameVarInfoMap &FrameVarInfo);
   ~WinEHFrameVariableMaterializer() override {}
 
bool WinEHPrepare::runOnFunction(Function &Fn) {
   Personality = classifyEHPersonality(Fn.getPersonalityFn());
 
   // Do nothing if this is not an MSVC personality.
   if (!isMSVCEHPersonality(Personality))
     return false;
 
   SmallVector<LandingPadInst *, 4> LPads;
   SmallVector<ResumeInst *, 4> Resumes;
+  SmallVector<BasicBlock *, 4> EntryBlocks;
   bool ForExplicitEH = false;
   for (BasicBlock &BB : Fn) {
-    if (auto *LP = BB.getLandingPadInst()) {
+    Instruction *First = BB.getFirstNonPHI();
+    if (auto *LP = dyn_cast<LandingPadInst>(First)) {
       LPads.push_back(LP);
-    } else if (BB.getFirstNonPHI()->isEHPad()) {
+    } else if (First->isEHPad()) {
+      if (!ForExplicitEH)
+        EntryBlocks.push_back(&Fn.getEntryBlock());
+      if (!isa<CatchEndPadInst>(First))
+        EntryBlocks.push_back(&BB);
       ForExplicitEH = true;
-      break;
     }
     if (auto *Resume = dyn_cast<ResumeInst>(BB.getTerminator()))
       Resumes.push_back(Resume);
   }
 
   if (ForExplicitEH)
-    return prepareExplicitEH(Fn);
+    return prepareExplicitEH(Fn, EntryBlocks);
 
   // No need to prepare functions that lack landing pads.
   if (LPads.empty())
     return false;
 
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
void llvm::calculateWinCXXEHStateNumbers(const Function *ParentFn,
   Num.calculateStateNumbers(*ParentFn);
   // Pop everything on the handler stack.
   // It may be necessary to call this more than once because a handler can
   // be pushed on the stack as a result of clearing the stack.
   while (!Num.HandlerStack.empty())
     Num.processCallSite(None, ImmutableCallSite());
 }
 
-void WinEHPrepare::numberFunclet(BasicBlock *InitialBB, BasicBlock *FuncletBB) {
-  Instruction *FirstNonPHI = FuncletBB->getFirstNonPHI();
-  bool IsCatch = isa<CatchPadInst>(FirstNonPHI);
-  bool IsCleanup = isa<CleanupPadInst>(FirstNonPHI);
-
-  // Initialize the worklist with the funclet's entry point.
-  std::vector<BasicBlock *> Worklist;
-  Worklist.push_back(InitialBB);
-
-  while (!Worklist.empty()) {
-    BasicBlock *BB = Worklist.back();
-    Worklist.pop_back();
-
-    // There can be only one "pad" basic block in the funclet: the initial one.
-    if (BB != FuncletBB && BB->isEHPad())
-      continue;
-
-    // Add 'FuncletBB' as a possible color for 'BB'.
-    if (BlockColors[BB].insert(FuncletBB).second == false) {
-      // Skip basic blocks which we have already visited.
-      continue;
-    }
+void WinEHPrepare::colorFunclets(Function &F,
+                                 SmallVectorImpl<BasicBlock *> &EntryBlocks) {
+  SmallVector<std::pair<BasicBlock *, BasicBlock *>, 16> Worklist;
+  BasicBlock *EntryBlock = &F.getEntryBlock();
 
-    FuncletBlocks[FuncletBB].insert(BB);
+  // Build up the color map, which maps each block to its set of 'colors'.
+  // For any block B, the "colors" of B are the set of funclets F (possibly
+  // including a root "funclet" representing the main function), such that
+  // F will need to directly contain B or a copy of B (where the term "directly
+  // contain" is used to distinguish from being "transitively contained" in
+  // a nested funclet).
+  // Use a CFG walk driven by a worklist of (block, color) pairs.  The "color"
+  // sets attached during this processing to a block which is the entry of some
+  // funclet F is actually the set of F's parents -- i.e. the union of colors
+  // of all predecessors of F's entry.  For all other blocks, the color sets
+  // are as defined above.  A post-pass fixes up the block color map to reflect
+  // the same sense of "color" for funclet entries as for other blocks.
 
-    Instruction *Terminator = BB->getTerminator();
-    // The catchret's successors cannot be part of the funclet.
-    if (IsCatch && isa<CatchReturnInst>(Terminator))
-      continue;
-    // The cleanupret's successors cannot be part of the funclet.
-    if (IsCleanup && isa<CleanupReturnInst>(Terminator))
-      continue;
+  Worklist.push_back({EntryBlock, EntryBlock});
 
-    Worklist.insert(Worklist.end(), succ_begin(BB), succ_end(BB));
+  while (!Worklist.empty()) {
+    BasicBlock *Visiting;
+    BasicBlock *Color;
+    std::tie(Visiting, Color) = Worklist.pop_back_val();
+    Instruction *VisitingHead = Visiting->getFirstNonPHI();
+    if (VisitingHead->isEHPad() && !isa<CatchEndPadInst>(VisitingHead)) {
+      // Mark this as a funclet head as a member of itself.
+      FuncletBlocks[Visiting].insert(Visiting);
+      // Queue exits with the parent color.
+      for (User *Exit : VisitingHead->users())
+        for (BasicBlock *Succ :
+             successors(cast<Instruction>(Exit)->getParent()))
+          if (BlockColors[Succ].insert(Color).second) {
+            Worklist.push_back({Succ, Color});
+          }
+      // Handle CatchPad specially since its successors need different colors.
+      if (CatchPadInst *CatchPad = dyn_cast<CatchPadInst>(VisitingHead)) {
+        // Visit the normal successor with the color of the new EH pad, and
+        // visit the unwind successor with the color of the parent.
+        BasicBlock *NormalSucc = CatchPad->getNormalDest();
+        if (BlockColors[NormalSucc].insert(Visiting).second) {
+          Worklist.push_back({NormalSucc, Visiting});
+        }
+        BasicBlock *UnwindSucc = CatchPad->getUnwindDest();
+        if (BlockColors[UnwindSucc].insert(Color).second) {
+          Worklist.push_back({UnwindSucc, Color});
+        }
+        continue;
+      }
+      // Switch color to the current node, except for terminate pads which
+      // have no bodies and only unwind successors and so need their successors
+      // visited with the color of the parent.
+      if (!isa<TerminatePadInst>(VisitingHead))
+        Color = Visiting;
+    } else {
+      // Note that this is a member of the given color.
+      FuncletBlocks[Color].insert(Visiting);
+      TerminatorInst *Terminator = Visiting->getTerminator();
+      if (isa<CleanupReturnInst>(Terminator) ||
+          isa<CatchReturnInst>(Terminator)) {
+        // These block's successors have already been queued with the parent
+        // color.
+        continue;
+      }
+    }
+    for (BasicBlock *Succ : successors(Visiting)) {
+      if (isa<CatchEndPadInst>(Succ->getFirstNonPHI())) {
+        // The catchendpad needs to be visited with the parent's color, not
+        // the current color.  This will happen in the code above that visits
+        // any catchpad unwind successor with the parent color, so we can
+        // safely skip this successor here.
+        continue;
+      }
+      if (BlockColors[Succ].insert(Color).second) {
+        Worklist.push_back({Succ, Color});
+      }
+    }
+  }
+
+  // The processing above actually accumulated the parent set for this
+  // funclet into the color set for its entry; use the parent set to
+  // populate the children map, and reset the color set to include just
+  // the funclet itself (no instruction can target a funclet entry except on
+  // that transitions to the child funclet).
+  for (BasicBlock *FuncletEntry : EntryBlocks) {
+    std::set<BasicBlock *> &ColorMapItem = BlockColors[FuncletEntry];
+    for (BasicBlock *Parent : ColorMapItem)
+      FuncletChildren[Parent].insert(FuncletEntry);
+    ColorMapItem.clear();
+    ColorMapItem.insert(FuncletEntry);
   }
 }
 
-bool WinEHPrepare::prepareExplicitEH(Function &F) {
+bool WinEHPrepare::prepareExplicitEH(
+    Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
   // Remove unreachable blocks.  It is not valuable to assign them a color and
   // their existence can trick us into thinking values are alive when they are
   // not.
   removeUnreachableBlocks(F);
 
-  BasicBlock *EntryBlock = &F.getEntryBlock();
-
-  // Number everything starting from the entry block.
-  numberFunclet(EntryBlock, EntryBlock);
-
-  for (BasicBlock &BB : F) {
-    // Remove single entry PHIs to simplify preparation.
-    if (auto *PN = dyn_cast<PHINode>(BB.begin()))
-      if (PN->getNumIncomingValues() == 1)
-        FoldSingleEntryPHINodes(&BB);
-
-    // EH pad instructions are always the first non-PHI nodes in a block if they
-    // are at all present.
-    Instruction *I = BB.getFirstNonPHI();
-    if (I->isEHPad())
-      numberFunclet(&BB, &BB);
-
-    // It is possible for a normal basic block to only be reachable via an
-    // exceptional basic block.  The successor of a catchret is the only case
-    // where this is possible.
-    if (auto *CRI = dyn_cast<CatchReturnInst>(BB.getTerminator()))
-      numberFunclet(CRI->getSuccessor(), EntryBlock);
-  }
+  // Determine which blocks are reachable from which funclet entries.
+  colorFunclets(F, EntryBlocks);
 
   // Strip PHI nodes off of EH pads.
   SmallVector<PHINode *, 16> PHINodes;
   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
     BasicBlock *BB = FI++;
     if (!BB->isEHPad())
       continue;
     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
bool WinEHPrepare::prepareExplicitEH(
   // Also demote function parameters used in funclets.
   std::set<BasicBlock *> &ColorsForEntry = BlockColors[&F.getEntryBlock()];
   for (Argument &Arg : F.args())
     demoteNonlocalUses(&Arg, ColorsForEntry, F);
 
   // We need to clone all blocks which belong to multiple funclets.  Values are
   // remapped throughout the funclet to propogate both the new instructions
   // *and* the new basic blocks themselves.
-  for (auto &Funclet : FuncletBlocks) {
-    BasicBlock *FuncletPadBB = Funclet.first;
-    std::set<BasicBlock *> &BlocksInFunclet = Funclet.second;
+  for (BasicBlock *FuncletPadBB : EntryBlocks) {
+    std::set<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletPadBB];
 
     std::map<BasicBlock *, BasicBlock *> Orig2Clone;
     ValueToValueMapTy VMap;
     for (BasicBlock *BB : BlocksInFunclet) {
       std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
       // We don't need to do anything if the block is monochromatic.
       size_t NumColorsForBB = ColorsForBB.size();
       if (NumColorsForBB == 1)
         continue;
 
-      assert(!isa<PHINode>(BB->front()) &&
-             "Polychromatic PHI nodes should have been demoted!");
-
       // Create a new basic block and copy instructions into it!
-      BasicBlock *CBB = CloneBasicBlock(
-          BB, VMap, Twine(".for.", FuncletPadBB->getName()), &F);
+      BasicBlock *CBB =
+          CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
+      // Insert the clone immediately after the original to ensure determinism
+      // and to keep the same relative ordering of any funclet's blocks.
+      CBB->insertInto(&F, BB->getNextNode());
 
       // Add basic block mapping.
       VMap[BB] = CBB;
 
       // Record delta operations that we need to perform to our color mappings.
       Orig2Clone[BB] = CBB;
     }
 
for (BasicBlock &BB : F) {
     bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(BB.begin());
     assert(!EHPadHasPHI && "EH Pad still has a PHI!");
     if (EHPadHasPHI)
       report_fatal_error("EH Pad still has a PHI!");
   }
 
   BlockColors.clear();
   FuncletBlocks.clear();
+  FuncletChildren.clear();
 
   return true;
 }
 
 // TODO: Share loads when one use dominates another, or when a catchpad exit
 // dominates uses (needs dominators).
 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
   BasicBlock *PHIBlock = PN->getParent();
void WinEHPrepare::demoteNonlocalUses(Value *V,
 
   DenseMap<BasicBlock *, Value *> Loads;
   AllocaInst *SpillSlot = nullptr;
   for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE;) {
     Use &U = *UI++;
     auto *UsingInst = cast<Instruction>(U.getUser());
     BasicBlock *UsingBB = UsingInst->getParent();
 
-    // Is the Use inside a block which is colored with a subset of the Def?
+    // Is the Use inside a block which is colored the same as the Def?
     // If so, we don't need to escape the Def because we will clone
     // ourselves our own private copy.
     std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[UsingBB];
-    if (std::includes(ColorsForBB.begin(), ColorsForBB.end(),
-                      ColorsForUsingBB.begin(), ColorsForUsingBB.end()))
+    if (ColorsForUsingBB == ColorsForBB)
       continue;
 
     replaceUseWithLoad(V, U, SpillSlot, Loads, F);
   }
   if (SpillSlot) {
     // Insert stores of the computed value into the stack slot.
     // We have to be careful if I is an invoke instruction,
     // because we can't insert the store AFTER the terminator instruction.

test/CodeGen/WinEH/wineh-cloning.ll

+; RUN: opt -mtriple=x86_x64-pc-windows-msvc -S -winehprepare  < %s | FileCheck %s
+
+declare i32 @__CxxFrameHandler3(...)
+
+declare void @f()
+declare i32 @g()
+declare void @h(i32)
+declare i1 @b()
+
+
+define void @test1() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  ; %x def colors: {entry} subset of use colors; must spill
+  %x = call i32 @g()
+  invoke void @f()
+    to label %noreturn unwind label %catch
+catch:
+  catchpad []
+    to label %noreturn unwind label %endcatch
+noreturn:
+  ; %x use colors: {entry, cleanup}
+  call void @h(i32 %x)
+  unreachable
+endcatch:
+  catchendpad unwind to caller
+}
+; Need two copies of the call to @h, one under entry and one under catch.
+; Currently we generate a load for each, though we shouldn't need one
+; for the use in entry's copy.
+; CHECK-LABEL: @test1(
+; CHECK: entry:
+; CHECK:   store i32 %x, i32* [[Slot:%[^ ]+]]
+; CHECK:   invoke void @f()
+; CHECK:     to label %[[EntryCopy:[^ ]+]] unwind label %catch
+; CHECK: catch:
+; CHECK:   catchpad [] to label %[[CatchCopy:[^ ]+]] unwind
+; CHECK: [[CatchCopy]]:
+; CHECK:   [[LoadX2:%[^ ]+]] = load i32, i32* [[Slot]]
+; CHECK:   call void @h(i32 [[LoadX2]]
+; CHECK: [[EntryCopy]]:
+; CHECK:   [[LoadX1:%[^ ]+]] = load i32, i32* [[Slot]]
+; CHECK:   call void @h(i32 [[LoadX1]]
+
+
+define void @test2() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %cleanup
+cleanup:
+  cleanuppad []
+  br label %exit
+exit:
+  call void @f()
+  ret void
+}
+; Need two copies of %exit's call to @f -- the subsequent ret is only
+; valid when coming from %entry, but on the path from %cleanup, this
+; might be a valid call to @f which might dynamically not return.
+; CHECK-LABEL: @test2(
+; CHECK: entry:
+; CHECK:   invoke void @f()
+; CHECK:     to label %[[exit:[^ ]+]] unwind label %cleanup
+; CHECK: cleanup:
+; CHECK:   cleanuppad []
+; CHECK:   call void @f()
+; CHECK-NEXT: unreachable
+; CHECK: [[exit]]:
+; CHECK:   call void @f()
+; CHECK-NEXT: ret void
+
+
+define void @test3() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %catch
+invoke.cont:
+  invoke void @f()
+    to label %exit unwind label %cleanup
+catch:
+  catchpad [] to label %shared unwind label %endcatch
+endcatch:
+  catchendpad unwind to caller
+cleanup:
+  cleanuppad []
+  br label %shared
+shared:
+  call void @f()
+  br label %exit
+exit:
+  ret void
+}
+; Need two copies of %shared's call to @f (similar to @test2 but
+; the two regions here are siblings, not parent-child).
+; CHECK-LABEL: @test3(
+; CHECK:   invoke void @f()
+; CHECK:   invoke void @f()
+; CHECK:     to label %[[exit:[^ ]+]] unwind
+; CHECK: catch:
+; CHECK:   catchpad [] to label %[[shared:[^ ]+]] unwind
+; CHECK: cleanup:
+; CHECK:   cleanuppad []
+; CHECK:   call void @f()
+; CHECK-NEXT: unreachable
+; CHECK: [[shared]]:
+; CHECK:   call void @f()
+; CHECK-NEXT: unreachable
+; CHECK: [[exit]]:
+; CHECK:   ret void
+
+
+define void @test4() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %shared unwind label %catch
+catch:
+  catchpad []
+    to label %shared unwind label %endcatch
+endcatch:
+  catchendpad unwind to caller
+shared:
+  %x = call i32 @g()
+  %i = call i32 @g()
+  %zero.trip = icmp eq i32 %i, 0
+  br i1 %zero.trip, label %exit, label %loop
+loop:
+  %i.loop = phi i32 [ %i, %shared ], [ %i.dec, %loop.tail ]
+  %b = call i1 @b()
+  br i1 %b, label %left, label %right
+left:
+  %y = call i32 @g()
+  br label %loop.tail
+right:
+  call void @h(i32 %x)
+  br label %loop.tail
+loop.tail:
+  %i.dec = sub i32 %i.loop, 1
+  %done = icmp eq i32 %i.dec, 0
+  br i1 %done, label %exit, label %loop
+exit:
+  call void @h(i32 %x)
+  unreachable
+}
+; Make sure we can clone regions that have internal control
+; flow and SSA values.  Here we need two copies of everything
+; from %shared to %exit.
+; CHECK-LABEL: @test4(
+; CHECK:  entry:
+; CHECK:    to label %[[shared_E:[^ ]+]] unwind label %catch
+; CHECK:  catch:
+; CHECK:    to label %[[shared_C:[^ ]+]] unwind label %endcatch
+; CHECK:  [[shared_C]]:
+; CHECK:    [[x_C:%[^ ]+]] = call i32 @g()
+; CHECK:    [[i_C:%[^ ]+]] = call i32 @g()
+; CHECK:    [[zt_C:%[^ ]+]] = icmp eq i32 [[i_C]], 0
+; CHECK:    br i1 [[zt_C]], label %[[exit_C:[^ ]+]], label %[[loop_C:[^ ]+]]
+; CHECK:  [[shared_E]]:
+; CHECK:    [[x_E:%[^ ]+]] = call i32 @g()
+; CHECK:    [[i_E:%[^ ]+]] = call i32 @g()
+; CHECK:    [[zt_E:%[^ ]+]] = icmp eq i32 [[i_E]], 0
+; CHECK:    br i1 [[zt_E]], label %[[exit_E:[^ ]+]], label %[[loop_E:[^ ]+]]
+; CHECK:  [[loop_C]]:
+; CHECK:    [[iloop_C:%[^ ]+]] = phi i32 [ [[i_C]], %[[shared_C]] ], [ [[idec_C:%[^ ]+]], %[[looptail_C:[^ ]+]] ]
+; CHECK:    [[b_C:%[^ ]+]] = call i1 @b()
+; CHECK:    br i1 [[b_C]], label %[[left_C:[^ ]+]], label %[[right_C:[^ ]+]]
+; CHECK:  [[loop_E]]:
+; CHECK:    [[iloop_E:%[^ ]+]] = phi i32 [ [[i_E]], %[[shared_E]] ], [ [[idec_E:%[^ ]+]], %[[looptail_E:[^ ]+]] ]
+; CHECK:    [[b_E:%[^ ]+]] = call i1 @b()
+; CHECK:    br i1 [[b_E]], label %[[left_E:[^ ]+]], label %[[right_E:[^ ]+]]
+; CHECK:  [[left_C]]:
+; CHECK:    [[y_C:%[^ ]+]] = call i32 @g()
+; CHECK     br label %[[looptail_C]]
+; CHECK:  [[left_E]]:
+; CHECK:    [[y_E:%[^ ]+]] = call i32 @g()
+; CHECK     br label %[[looptail_E]]
+; CHECK:  [[right_C]]:
+; CHECK:    call void @h(i32 [[x_C]])
+; CHECK:    br label %[[looptail_C]]
+; CHECK:  [[right_E]]:
+; CHECK:    call void @h(i32 [[x_E]])
+; CHECK:    br label %[[looptail_E]]
+; CHECK:  [[looptail_C]]:
+; CHECK:    [[idec_C]] = sub i32 [[iloop_C]], 1
+; CHECK:    [[done_C:%[^ ]+]] = icmp eq i32 [[idec_C]], 0
+; CHECK:    br i1 [[done_C]], label %[[exit_C]], label %[[loop_C]]
+; CHECK:  [[looptail_E]]:
+; CHECK:    [[idec_E]] = sub i32 [[iloop_E]], 1
+; CHECK:    [[done_E:%[^ ]+]] = icmp eq i32 [[idec_E]], 0
+; CHECK:    br i1 [[done_E]], label %[[exit_E]], label %[[loop_E]]
+; CHECK:  [[exit_C]]:
+; CHECK:    call void @h(i32 [[x_C]])
+; CHECK:    unreachable
+; CHECK:  [[exit_E]]:
+; CHECK:    call void @h(i32 [[x_E]])
+; CHECK:    unreachable
+
+
+define void @test5() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %outer
+outer:
+  %o = cleanuppad []
+  %x = call i32 @g()
+  invoke void @f()
+    to label %outer.ret unwind label %inner
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.endcatch
+inner.catch:
+  catchret %i to label %outer.post-inner
+inner.endcatch:
+  catchendpad unwind to caller
+outer.post-inner:
+  call void @h(i32 %x)
+  br label %outer.ret
+outer.ret:
+  cleanupret %o unwind to caller
+exit:
+  ret void
+}
+; Simple nested case (catch-inside-cleanup).  Nothing needs
+; to be cloned.  The def and use of %x are both in %outer
+; and so don't need to be spilled.
+; CHECK-LABEL: @test5(
+; CHECK:      outer:
+; CHECK:        %x = call i32 @g()
+; CHECK-NEXT:   invoke void @f()
+; CHECK-NEXT:     to label %outer.ret unwind label %inner
+; CHECK:      inner:
+; CHECK:          to label %inner.catch unwind label %inner.endcatch
+; CHECK:      inner.catch:
+; CHECK-NEXT:   catchret %i to label %outer.post-inner
+; CHECK:      outer.post-inner:
+; CHECK-NEXT:   call void @h(i32 %x)
+; CHECK-NEXT:   br label %outer.ret
+
+
+define void @test6() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %exit unwind label %right
+left:
+  cleanuppad []
+  br label %shared
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  %i = cleanuppad []
+  call void @h(i32 %x)
+  cleanupret %i unwind label %right.end
+exit:
+  ret void
+}
+; %inner is a cleanup which appears both as a child of
+; %left and as a child of %right.  Since statically we
+; need each funclet to have a single parent, we need to
+; clone the entire %inner funclet so we can have one
+; copy under each parent.  The cleanupret in %inner
+; unwinds to the catchendpad for %right, so the copy
+; of %inner under %right should include it; the copy
+; of %inner under %left should instead have an
+; `unreachable` inserted there, but the copy under
+; %left still needs to be created because it's possible
+; the dynamic path enters %left, then enters %inner,
+; then calls @h, and that the call to @h doesn't return.
+; CHECK-LABEL: @test6(
+; TODO: CHECKs
+
+
+define void @test7() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %unreachable unwind label %right
+left:
+  cleanuppad []
+  invoke void @f() to label %unreachable unwind label %inner
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  invoke void @f() to label %unreachable unwind label %inner
+right.end:
+  catchendpad unwind to caller
+inner:
+  %i = cleanuppad []
+  %x = call i32 @g()
+  call void @h(i32 %x)
+  cleanupret %i unwind label %right.end
+unreachable:
+  unreachable
+}
+; Another case of a two-parent child (like @test6), this time
+; with the join at the entry itself instead of following a
+; non-pad join.
+; CHECK-LABEL: @test7(
+; TODO: CHECKs
+
+
+define void @test8() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %unreachable unwind label %right
+left:
+  cleanuppad []
+  br label %shared
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  invoke void @f()
+    to label %unreachable unwind label %inner
+inner:
+  cleanuppad []
+  invoke void @f()
+    to label %unreachable unwind label %inner.child
+inner.child:
+  cleanuppad []
+  %x = call i32 @g()
+  call void @h(i32 %x)
+  unreachable
+unreachable:
+  unreachable
+}
+; %inner is a two-parent child which itself has a child; need
+; to make two copies of both the %inner and %inner.child.
+; CHECK-LABEL: @test8(
+; TODO: CHECKs
+
+
+define void @test9() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %unreachable unwind label %right
+left:
+  cleanuppad []
+  call void @h(i32 1)
+  invoke void @f()
+    to label %unreachable unwind label %right
+right:
+  cleanuppad []
+  call void @h(i32 2)
+  invoke void @f()
+    to label %unreachable unwind label %left
+unreachable:
+  unreachable
+}
+; This is an irreducible loop with two funclets that enter each other;
+; need to make two copies of each funclet (one a child of root, the
+; other a child of the opposite funclet), but also make sure not to
+; clone self-descendants (if we tried to do that we'd need to make an
+; infinite number of them).  Presumably if optimizations ever generated
+; such a thing it would mean that one of the two cleanups was originally
+; the parent of the other, but that we'd somehow lost track in the CFG
+; of which was which along the way; generating each possibility lets
+; whichever case was correct execute correctly.
+; CHECK-LABEL: @test9(
+; TODO: CHECKs