[WinEH] Fix mutli-parent cloning

[andrew.w.kaylor]

Summary

This fixes the bug in the earlier multi-parent cloning implementation that was leading to non-deterministic (and incorrect) output.

The problem is that while updating sibling-to-sibling unwind edges for cloned funclets, the code to handle invokes was attempting to walk the unwind edges of the cloned funclets. As a result, it was likely to walk the catch-to-catch unwind chain before that chain was properly updated. This change just creates a second loop in updateSiblingToSiblingUnwind() so that the invoke processing happens after all of the other unwind edges are updated.

I've included just the changes since the previously committed revision (as reviewed in D13274), but since that commit has been reverted, I will be committing the previous change set in addition to these modifications when the review is complete.

[JosephTremoulet]

lgtm

[andrew.w.kaylor]

This still doesn't fix everything. There's a problem with the block ordering of cloned catch end pads.

The code that I added to cloneCommonBlocks for catchendpad handling finds the catchpad that unwinds to the catchendpad and assigns the catchendpad the color of that catchpad's first parent. I said in the comment that it didn't matter if the catchpad had multiple parents because we'd clone it later if it did. That's not quite true. When we clone the block later, we use its color to figure out whether to give the new catchend pad to the clone parent or the original funclet's parent. So the color we gave it in cloneCommonBlocks determines which parent funclet gets the clone and that, in turn, determines whether or not the unwind edge is removed as implausible.

For instance, test15 in wineh-multi-parent-cloning.ll has this form (with a bunch of stuff omitted):

define void @test15() personality i32 (...)* @__CxxFrameHandler3 {
left:
left.end:
  catchendpad unwind to caller
right:
right.end:
  catchendpad unwind label %left.end
inner:
  catchpad []
inner.end:
  catchendpad unwind label %left.end
}

Here %left and %right are both parents of %inner. When we see %inner.end in cloneCommonBlocks() we can set its color to either %left or %right. FuncletParents maps to a vector, trying to normalize the order of traversal, but the order is actually based on the order of the BlockColors assigned to %inner by colorFunclets.

So we set the color of %inner.end to either %left or %right. When we do the cloning, if we made it %left, it comes out like this:

inner:
  catchpad []
inner.from.right:
  catchpad []
inner.end:
  catchendpad unwind label %left.end
inner.end.from.right
  catchendpad unwind to caller

but if we made it %right, it comes out like this:

inner:
  catchpad []
inner.from.right:
  catchpad []
inner.end:
  catchendpad unwind to caller
inner.end.from.left
  catchendpad unwind label %left.end

Basically, I think I need to make the BlockColors value type a vector too.

[andrew.w.kaylor]

Rebasing and incorporating the previously reverted changes to establish a better baseline for the next update (which will address another determinism issue).

[andrew.w.kaylor]

This fixes the additional problems with determinism. I had to change the BlockColors value type (container) from a std::set to a SetVector. I don't think that should be a problem given the expected size of the sets involved.

[JosephTremoulet]

Looks good to me.

change the BlockColors value type (container) from a std::set to a SetVector. I don't think that should be a problem given the expected size of the sets involved

I agree. It's maybe too bad we don't have a SmallSetVector that just uses a vector when small like a SmallSet but allows deterministic iteration when large like a SetVector. (not trying to suggest you stop to add such a thing for this lone use case, just thinking "out loud"...)

[yaron.keren]

Hi Andy,

The change from std::set to SetVector gains stable iteration order but
loses stable iterators...
Specifically, it invalidates BlockColors[BB].end() after every remove(), so
it should not be cached in the End variable. Even if we solve this by
testing It != BlockColors[BB].end(), after removing the last item 'It' will
be at the (new after removal) end()+1 and then compared to the (new after
removal) end() which is probably undefined behaviour for an iterator.
Finally, erasing items in a loop in a SetVector is quadratic complexity.

To solve all at once, we could split the loop into two steps:

for (BasicBlock *ContainingFunclet : BlockColors[BB])
  if (ContainingFunclet != CorrectColor)
    FuncletBlocks[ContainingFunclet].erase(BB);
BlockColors[BB].remove_if([&](BasicBlock *ContainingFunclet) {
  return ContainingFunclet != CorrectColor;
});

Please feel free to modify the attached patch and commit,

Yaron

• wineh.diff1 KBDownload

[andrew.w.kaylor]

Thanks, Yaron.

This change looks good to me. I didn’t get to it earlier, and I don’t want to commit it now in case it this late in the day, but I’ll commit this first thing tomorrow.

-Andy

From: Yaron Keren [mailto:[e-mail]]
Sent: Wednesday, November 11, 2015 9:03 AM
To: [e-mail]; Phabricator <[e-mail]>
Cc: Kaylor, Andrew <[e-mail]>; Reid Kleckner <[e-mail]>; David Majnemer <[e-mail]>; [e-mail]; llvm-commits <[e-mail]>
Subject: Re: [PATCH] D14454: [WinEH] Fix mutli-parent cloning

Hi Andy,

The change from std::set to SetVector gains stable iteration order but loses stable iterators...
Specifically, it invalidates BlockColors[BB].end() after every remove(), so it should not be cached in the End variable. Even if we solve this by testing It != BlockColors[BB].end(), after removing the last item 'It' will be at the (new after removal) end()+1 and then compared to the (new after removal) end() which is probably undefined behaviour for an iterator. Finally, erasing items in a loop in a SetVector is quadratic complexity.

To solve all at once, we could split the loop into two steps:

for (BasicBlock *ContainingFunclet : BlockColors[BB])
  if (ContainingFunclet != CorrectColor)
    FuncletBlocks[ContainingFunclet].erase(BB);
BlockColors[BB].remove_if([&](BasicBlock *ContainingFunclet) {
  return ContainingFunclet != CorrectColor;
});

Please feel free to modify the attached patch and commit,

Yaron

llvm/trunk/lib/CodeGen/WinEHPrepare.cpp

 // provided by MSVC. Functions with other personality functions are left alone
 // and may be prepared by other passes. In particular, all supported MSVC
 // personality functions require cleanup code to be outlined, and the C++
 // personality requires catch handler code to be outlined.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/LibCallSemantics.h"
 #include "llvm/CodeGen/WinEHFuncInfo.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
static cl::opt<bool> DisableDemotion(
     cl::init(false));
 
 static cl::opt<bool> DisableCleanups(
     "disable-cleanups", cl::Hidden,
     cl::desc("Do not remove implausible terminators or other similar cleanups"),
     cl::init(false));
 
 namespace {
   
 class WinEHPrepare : public FunctionPass {
 public:
   static char ID; // Pass identification, replacement for typeid.
   WinEHPrepare(const TargetMachine *TM = nullptr) : FunctionPass(ID) {}
 
   bool runOnFunction(Function &Fn) override;
 
   bool doFinalization(Module &M) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   const char *getPassName() const override {
     return "Windows exception handling preparation";
   }
 
 private:
   void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);
   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,
+  void demoteNonlocalUses(Value *V, SetVector<BasicBlock *> &ColorsForBB,
                           Function &F);
   bool prepareExplicitEH(Function &F,
                          SmallVectorImpl<BasicBlock *> &EntryBlocks);
   void replaceTerminatePadWithCleanup(Function &F);
   void colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks);
+  void resolveFuncletAncestry(Function &F,
+                              SmallVectorImpl<BasicBlock *> &EntryBlocks);
+  void resolveFuncletAncestryForPath(
+      Function &F, SmallVectorImpl<BasicBlock *> &FuncletPath,
+      std::map<BasicBlock *, BasicBlock *> &IdentityMap);
+  void makeFuncletEdgeUnreachable(BasicBlock *Parent, BasicBlock *Child);
+  BasicBlock *cloneFuncletForParent(Function &F, BasicBlock *FuncletEntry,
+                                    BasicBlock *Parent);
+  void updateTerminatorsAfterFuncletClone(
+      Function &F, BasicBlock *OrigFunclet, BasicBlock *CloneFunclet,
+      BasicBlock *OrigBlock, BasicBlock *CloneBlock, BasicBlock *CloneParent,
+      ValueToValueMapTy &VMap,
+      std::map<BasicBlock *, BasicBlock *> &Orig2Clone);
+
   void demotePHIsOnFunclets(Function &F);
   void demoteUsesBetweenFunclets(Function &F);
   void demoteArgumentUses(Function &F);
   void cloneCommonBlocks(Function &F,
                          SmallVectorImpl<BasicBlock *> &EntryBlocks);
   void removeImplausibleTerminators(Function &F);
   void cleanupPreparedFunclets(Function &F);
   void verifyPreparedFunclets(Function &F);
 
   // All fields are reset by runOnFunction.
   EHPersonality Personality = EHPersonality::Unknown;
 
-  std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
+  std::map<BasicBlock *, SetVector<BasicBlock *>> BlockColors;
   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
-  std::map<BasicBlock *, std::set<BasicBlock *>> FuncletChildren;
+  std::map<BasicBlock *, std::vector<BasicBlock *>> FuncletChildren;
+  std::map<BasicBlock *, std::vector<BasicBlock *>> FuncletParents;
+
+  // This is a flag that indicates an uncommon situation where we need to
+  // clone funclets has been detected.
+  bool FuncletCloningRequired = false;
+  // When a funclet with multiple parents contains a catchret, the block to
+  // which it returns will be cloned so that there is a copy in each parent
+  // but one of the copies will not be properly linked to the catchret and
+  // in most cases will have no predecessors.  This double map allows us
+  // to find these cloned blocks when we clone the child funclet.
+  std::map<BasicBlock *, std::map<BasicBlock *, BasicBlock*>> EstrangedBlocks;
 };
 
 } // end anonymous namespace
 
 char WinEHPrepare::ID = 0;
 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
                    false, false)
 
for (BasicBlock &BB : F) {
     // Let's remove the terminatepad now that we've inserted the new
     // instructions.
     TPI->eraseFromParent();
   }
 }
 
 static void
 colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks,
-              std::map<BasicBlock *, std::set<BasicBlock *>> &BlockColors,
-              std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks,
-              std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletChildren) {
+              std::map<BasicBlock *, SetVector<BasicBlock *>> &BlockColors,
+              std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks) {
   SmallVector<std::pair<BasicBlock *, BasicBlock *>, 16> Worklist;
   BasicBlock *EntryBlock = &F.getEntryBlock();
 
   // 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.
 
+  DEBUG_WITH_TYPE("winehprepare-coloring", dbgs() << "\nColoring funclets for "
+                                                  << F.getName() << "\n");
+
   Worklist.push_back({EntryBlock, EntryBlock});
 
   while (!Worklist.empty()) {
     BasicBlock *Visiting;
     BasicBlock *Color;
     std::tie(Visiting, Color) = Worklist.pop_back_val();
+    DEBUG_WITH_TYPE("winehprepare-coloring",
+                    dbgs() << "Visiting " << Visiting->getName() << ", "
+                           << Color->getName() << "\n");
     Instruction *VisitingHead = Visiting->getFirstNonPHI();
     if (VisitingHead->isEHPad() && !isa<CatchEndPadInst>(VisitingHead) &&
         !isa<CleanupEndPadInst>(VisitingHead)) {
       // Mark this as a funclet head as a member of itself.
       FuncletBlocks[Visiting].insert(Visiting);
       // Queue exits (i.e. successors of rets/endpads) with the parent color.
       // Skip any exits that are catchendpads, since the parent color must then
       // represent one of the catches chained to that catchendpad, but the
       // catchendpad should get the color of the common parent of all its
       // chained catches (i.e. the grandparent color of the current pad).
       // We don't need to worry abou catchendpads going unvisited, since the
       // catches chained to them must have unwind edges to them by which we will
       // visit them.
       for (User *U : VisitingHead->users()) {
         if (auto *Exit = dyn_cast<TerminatorInst>(U)) {
           for (BasicBlock *Succ : successors(Exit->getParent()))
             if (!isa<CatchEndPadInst>(*Succ->getFirstNonPHI()))
-              if (BlockColors[Succ].insert(Color).second)
+              if (BlockColors[Succ].insert(Color)) {
+                DEBUG_WITH_TYPE("winehprepare-coloring",
+                                dbgs() << "  Assigned color \'"
+                                       << Color->getName() << "\' to block \'"
+                                       << Succ->getName() << "\'.\n");
                 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) {
+        if (BlockColors[NormalSucc].insert(Visiting)) {
+          DEBUG_WITH_TYPE("winehprepare-coloring",
+                          dbgs() << "  Assigned color \'" << Visiting->getName()
+                                 << "\' to block \'" << NormalSucc->getName()
+                                 << "\'.\n");
           Worklist.push_back({NormalSucc, Visiting});
         }
         BasicBlock *UnwindSucc = CatchPad->getUnwindDest();
-        if (BlockColors[UnwindSucc].insert(Color).second) {
+        if (BlockColors[UnwindSucc].insert(Color)) {
+          DEBUG_WITH_TYPE("winehprepare-coloring",
+                          dbgs() << "  Assigned color \'" << Color->getName()
+                                 << "\' to block \'" << UnwindSucc->getName()
+                                 << "\'.\n");
           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))
while (!Worklist.empty()) {
     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) {
+      if (BlockColors[Succ].insert(Color)) {
+        DEBUG_WITH_TYPE("winehprepare-coloring",
+                        dbgs() << "  Assigned color \'" << Color->getName()
+                               << "\' to block \'" << Succ->getName()
+                               << "\'.\n");
         Worklist.push_back({Succ, Color});
       }
     }
   }
+}
+
+static BasicBlock *getEndPadForCatch(CatchPadInst *Catch) {
+  // The catch may have sibling catches.  Follow the unwind chain until we get
+  // to the catchendpad.
+  BasicBlock *NextUnwindDest = Catch->getUnwindDest();
+  auto *UnwindTerminator = NextUnwindDest->getTerminator();
+  while (auto *NextCatch = dyn_cast<CatchPadInst>(UnwindTerminator)) {
+    NextUnwindDest = NextCatch->getUnwindDest();
+    UnwindTerminator = NextUnwindDest->getTerminator();
+  }
+  // The last catch in the chain must unwind to a catchendpad.
+  assert(isa<CatchEndPadInst>(UnwindTerminator));
+  return NextUnwindDest;
+}
+
+static void updateClonedEHPadUnwindToParent(
+    BasicBlock *UnwindDest, BasicBlock *OrigBlock, BasicBlock *CloneBlock,
+    std::vector<BasicBlock *> &OrigParents, BasicBlock *CloneParent) {
+  auto updateUnwindTerminator = [](BasicBlock *BB) {
+    auto *Terminator = BB->getTerminator();
+    if (isa<CatchEndPadInst>(Terminator) ||
+        isa<CleanupEndPadInst>(Terminator)) {
+      removeUnwindEdge(BB);
+    } else {
+      // If the block we're updating has a cleanupendpad or cleanupret
+      // terminator, we just want to replace that terminator with an
+      // unreachable instruction.
+      assert(isa<CleanupEndPadInst>(Terminator) ||
+             isa<CleanupReturnInst>(Terminator));
+      // Loop over all of the successors, removing the block's entry from any
+      // PHI nodes.
+      for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
+        (*SI)->removePredecessor(BB);
+      // Remove the terminator and replace it with an unreachable instruction.
+      BB->getTerminator()->eraseFromParent();
+      new UnreachableInst(BB->getContext(), BB);
+    }
+  };
+
+  assert(UnwindDest->isEHPad());
+  // There are many places to which this EH terminator can unwind and each has
+  // slightly different rules for whether or not it fits with the given
+  // location.
+  auto *EHPadInst = UnwindDest->getFirstNonPHI();
+  if (isa<CatchEndPadInst>(EHPadInst)) {
+    auto *CloneParentCatch =
+        dyn_cast<CatchPadInst>(CloneParent->getFirstNonPHI());
+    if (!CloneParentCatch ||
+        getEndPadForCatch(CloneParentCatch) != UnwindDest) {
+      DEBUG_WITH_TYPE(
+          "winehprepare-coloring",
+          dbgs() << "      removing unwind destination of clone block \'"
+                 << CloneBlock->getName() << "\'.\n");
+      updateUnwindTerminator(CloneBlock);
+    }
+    // It's possible that the catch end pad is a legal match for both the clone
+    // and the original, so they must be checked separately.  If the original
+    // funclet will still have multiple parents after the current clone parent
+    // is removed, we'll leave its unwind terminator until later.
+    assert(OrigParents.size() >= 2);
+    if (OrigParents.size() != 2)
+      return;
+
+    // If the original funclet will have a single parent after the clone parent
+    // is removed, check that parent's unwind destination.
+    assert(OrigParents.front() == CloneParent ||
+           OrigParents.back() == CloneParent);
+    BasicBlock *OrigParent;
+    if (OrigParents.front() == CloneParent)
+      OrigParent = OrigParents.back();
+    else
+      OrigParent = OrigParents.front();
+
+    auto *OrigParentCatch =
+        dyn_cast<CatchPadInst>(OrigParent->getFirstNonPHI());
+    if (!OrigParentCatch || getEndPadForCatch(OrigParentCatch) != UnwindDest) {
+      DEBUG_WITH_TYPE(
+          "winehprepare-coloring",
+          dbgs() << "      removing unwind destination of original block \'"
+                 << OrigBlock << "\'.\n");
+      updateUnwindTerminator(OrigBlock);
+    }
+  } else if (auto *CleanupEnd = dyn_cast<CleanupEndPadInst>(EHPadInst)) {
+    // If the EH terminator unwinds to a cleanupendpad, that cleanupendpad
+    // must be ending a cleanuppad of either our clone parent or one
+    // one of the parents of the original funclet.
+    auto *CloneParentCP =
+        dyn_cast<CleanupPadInst>(CloneParent->getFirstNonPHI());
+    auto *EndedCP = CleanupEnd->getCleanupPad();
+    if (EndedCP == CloneParentCP) {
+      // If it is ending the cleanuppad of our cloned parent, then we
+      // want to remove the unwind destination of the EH terminator that
+      // we associated with the original funclet.
+      assert(isa<CatchEndPadInst>(OrigBlock->getFirstNonPHI()));
+      DEBUG_WITH_TYPE(
+          "winehprepare-coloring",
+          dbgs() << "      removing unwind destination of original block \'"
+                 << OrigBlock->getName() << "\'.\n");
+      updateUnwindTerminator(OrigBlock);
+    } else {
+      // If it isn't ending the cleanuppad of our clone parent, then we
+      // want to remove the unwind destination of the EH terminator that
+      // associated with our cloned funclet.
+      assert(isa<CatchEndPadInst>(CloneBlock->getFirstNonPHI()));
+      DEBUG_WITH_TYPE(
+          "winehprepare-coloring",
+          dbgs() << "      removing unwind destination of clone block \'"
+                 << CloneBlock->getName() << "\'.\n");
+      updateUnwindTerminator(CloneBlock);
+    }
+  } else {
+    // If the EH terminator unwinds to a catchpad, cleanuppad or
+    // terminatepad that EH pad must be a sibling of the funclet we're
+    // cloning.  We'll clone it later and update one of the catchendpad
+    // instrunctions that unwinds to it at that time.
+    assert(isa<CatchPadInst>(EHPadInst) || isa<CleanupPadInst>(EHPadInst) ||
+           isa<TerminatePadInst>(EHPadInst));
+  }
+}
+
+// If the terminator is a catchpad, we must also clone the catchendpad to which
+// it unwinds and add this to the clone parent's block list.  The catchendpad
+// unwinds to either its caller, a sibling EH pad, a cleanup end pad in its
+// parent funclet or a catch end pad in its grandparent funclet (which must be
+// coupled with the parent funclet).  If it has no unwind destination
+// (i.e. unwind to caller), there is nothing to be done. If the unwind
+// destination is a sibling EH pad, we will update the terminators later (in
+// resolveFuncletAncestryForPath).  If it unwinds to a cleanup end pad or a
+// catch end pad and this end pad corresponds to the clone parent, we will
+// remove the unwind destination in the original catchendpad. If it unwinds to
+// a cleanup end pad or a catch end pad that does not correspond to the clone
+// parent, we will remove the unwind destination in the cloned catchendpad.
+static void updateCatchTerminators(
+    Function &F, CatchPadInst *OrigCatch, CatchPadInst *CloneCatch,
+    std::vector<BasicBlock *> &OrigParents, BasicBlock *CloneParent,
+    ValueToValueMapTy &VMap,
+    std::map<BasicBlock *, SetVector<BasicBlock *>> &BlockColors,
+    std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks) {
+  // If we're cloning a catch pad that unwinds to a catchendpad, we also
+  // need to clone the catchendpad.  The coloring algorithm associates
+  // the catchendpad block with the funclet's parent, so we have some work
+  // to do here to figure out whether the original belongs to the clone
+  // parent or one of the original funclets other parents (it might have
+  // more than one at this point).  In either case, we might also need to
+  // remove the unwind edge if the catchendpad doesn't unwind to a block
+  // in the right grandparent funclet.
+  Instruction *I = CloneCatch->getUnwindDest()->getFirstNonPHI();
+  if (auto *CEP = dyn_cast<CatchEndPadInst>(I)) {
+    assert(BlockColors[CEP->getParent()].size() == 1);
+    BasicBlock *CEPFunclet = *(BlockColors[CEP->getParent()].begin());
+    BasicBlock *CEPCloneParent = nullptr;
+    CatchPadInst *PredCatch = nullptr;
+    if (CEPFunclet == CloneParent) {
+      // The catchendpad is in the clone parent, so we need to clone it
+      // and associate the clone with the original funclet's parent.  If
+      // the original funclet had multiple parents, we'll add it to the
+      // first parent that isn't the clone parent.  The logic in
+      // updateClonedEHPadUnwindToParent() will only remove the unwind edge
+      // if there is only one parent other than the clone parent, so we don't
+      // need to verify the ancestry.  The catchendpad will eventually be
+      // cloned into the correct parent and all invalid unwind edges will be
+      // removed.
+      for (auto *Parent : OrigParents) {
+        if (Parent != CloneParent) {
+          CEPCloneParent = Parent;
+          break;
+        }
+      }
+      PredCatch = OrigCatch;
+    } else {
+      CEPCloneParent = CloneParent;
+      PredCatch = CloneCatch;
+    }
+    assert(CEPCloneParent && PredCatch);
+    DEBUG_WITH_TYPE("winehprepare-coloring",
+                    dbgs() << "  Cloning catchendpad \'"
+                           << CEP->getParent()->getName() << "\' for funclet \'"
+                           << CEPCloneParent->getName() << "\'.\n");
+    BasicBlock *ClonedCEP = CloneBasicBlock(
+        CEP->getParent(), VMap, Twine(".from.", CEPCloneParent->getName()));
+    // Insert the clone immediately after the original to ensure determinism
+    // and to keep the same relative ordering of any funclet's blocks.
+    ClonedCEP->insertInto(&F, CEP->getParent()->getNextNode());
+    PredCatch->setUnwindDest(ClonedCEP);
+    FuncletBlocks[CEPCloneParent].insert(ClonedCEP);
+    BlockColors[ClonedCEP].insert(CEPCloneParent);
+    DEBUG_WITH_TYPE("winehprepare-coloring",
+                    dbgs() << "    Assigning color \'"
+                           << CEPCloneParent->getName() << "\' to block \'"
+                           << ClonedCEP->getName() << "\'.\n");
+    auto *ClonedCEPInst = cast<CatchEndPadInst>(ClonedCEP->getTerminator());
+    if (auto *Dest = ClonedCEPInst->getUnwindDest())
+      updateClonedEHPadUnwindToParent(Dest, OrigCatch->getUnwindDest(),
+                                      CloneCatch->getUnwindDest(), OrigParents,
+                                      CloneParent);
+  }
+}
+
+// While we are cloning a funclet because it has multiple parents, we will call
+// this routine to update the terminators for the original and cloned copies
+// of each basic block.  All blocks in the funclet have been clone by this time.
+// OrigBlock and CloneBlock will be identical except for their block label.
+//
+// If the terminator is a catchpad, we must also clone the catchendpad to which
+// it unwinds and in most cases update either the original catchendpad or the
+// clone.  See the updateCatchTerminators() helper routine for details.
+//
+// If the terminator is a catchret its successor is a block in its parent
+// funclet.  If the instruction returns to a block in the parent for which the
+// cloned funclet was created, the terminator in the original block must be
+// replaced by an unreachable instruction.  Otherwise the terminator in the
+// clone block must be replaced by an unreachable instruction.
+//
+// If the terminator is a cleanupret or cleanupendpad it either unwinds to
+// caller or unwinds to a sibling EH pad, a cleanup end pad in its parent
+// funclet or a catch end pad in its grandparent funclet (which must be
+// coupled with the parent funclet).  If it unwinds to caller there is
+// nothing to be done. If the unwind destination is a sibling EH pad, we will
+// update the terminators later (in resolveFuncletAncestryForPath).  If it
+// unwinds to a cleanup end pad or a catch end pad and this end pad corresponds
+// to the clone parent, we will replace the terminator in the original block
+// with an unreachable instruction. If it unwinds to a cleanup end pad or a
+// catch end pad that does not correspond to the clone parent, we will replace
+// the terminator in the clone block with an unreachable instruction.
+//
+// If the terminator is an invoke instruction, we will handle it after all
+// siblings of the current funclet have been cloned.
+void WinEHPrepare::updateTerminatorsAfterFuncletClone(
+    Function &F, BasicBlock *OrigFunclet, BasicBlock *CloneFunclet,
+    BasicBlock *OrigBlock, BasicBlock *CloneBlock, BasicBlock *CloneParent,
+    ValueToValueMapTy &VMap, std::map<BasicBlock *, BasicBlock *> &Orig2Clone) {
+  // If the cloned block doesn't have an exceptional terminator, there is
+  // nothing to be done here.
+  TerminatorInst *CloneTerminator = CloneBlock->getTerminator();
+  if (!CloneTerminator->isExceptional())
+    return;
+
+  if (auto *CloneCatch = dyn_cast<CatchPadInst>(CloneTerminator)) {
+    // A cloned catch pad has a lot of wrinkles, so we'll call a helper function
+    // to update this case.
+    auto *OrigCatch = cast<CatchPadInst>(OrigBlock->getTerminator());
+    updateCatchTerminators(F, OrigCatch, CloneCatch,
+                           FuncletParents[OrigFunclet], CloneParent, VMap,
+                           BlockColors, FuncletBlocks);
+  } else if (auto *CRI = dyn_cast<CatchReturnInst>(CloneTerminator)) {
+    if (FuncletBlocks[CloneParent].count(CRI->getSuccessor())) {
+      BasicBlock *OrigParent;
+      // The original funclet may have more than two parents, but that's OK.
+      // We just need to remap the original catchret to any of the parents.
+      // All of the parents should have an entry in the EstrangedBlocks map
+      // if any of them do.
+      if (FuncletParents[OrigFunclet].front() == CloneParent)
+        OrigParent = FuncletParents[OrigFunclet].back();
+      else
+        OrigParent = FuncletParents[OrigFunclet].front();
+      for (succ_iterator SI = succ_begin(OrigBlock), SE = succ_end(OrigBlock);
+           SI != SE; ++SI)
+        (*SI)->removePredecessor(OrigBlock);
+      BasicBlock *LostBlock = EstrangedBlocks[OrigParent][CRI->getSuccessor()];
+      auto *OrigCatchRet = cast<CatchReturnInst>(OrigBlock->getTerminator());
+      if (LostBlock) {
+        OrigCatchRet->setSuccessor(LostBlock);
+      } else {
+        OrigCatchRet->eraseFromParent();
+        new UnreachableInst(OrigBlock->getContext(), OrigBlock);
+      }
+    } else {
+      for (succ_iterator SI = succ_begin(CloneBlock), SE = succ_end(CloneBlock);
+           SI != SE; ++SI)
+        (*SI)->removePredecessor(CloneBlock);
+      BasicBlock *LostBlock = EstrangedBlocks[CloneParent][CRI->getSuccessor()];
+      if (LostBlock) {
+        CRI->setSuccessor(LostBlock);
+      } else {
+        CRI->eraseFromParent();
+        new UnreachableInst(CloneBlock->getContext(), CloneBlock);
+      }
+    }
+  } else if (isa<CleanupReturnInst>(CloneTerminator) ||
+             isa<CleanupEndPadInst>(CloneTerminator)) {
+    BasicBlock *UnwindDest = nullptr;
+
+    // A cleanup pad can unwind through either a cleanupret or a cleanupendpad
+    // but both are handled the same way.
+    if (auto *CRI = dyn_cast<CleanupReturnInst>(CloneTerminator))
+      UnwindDest = CRI->getUnwindDest();
+    else if (auto *CEI = dyn_cast<CleanupEndPadInst>(CloneTerminator))
+      UnwindDest = CEI->getUnwindDest();
+
+    // If the instruction has no local unwind destination, there is nothing
+    // to be done.
+    if (!UnwindDest)
+      return;
+
+    // The unwind destination may be a sibling EH pad, a catchendpad in
+    // a grandparent funclet (ending a catchpad in the parent) or a cleanup
+    // cleanupendpad in the parent.  Call a helper routine to diagnose this
+    // and remove either the clone or original terminator as needed.
+    updateClonedEHPadUnwindToParent(UnwindDest, OrigBlock, CloneBlock,
+                                    FuncletParents[OrigFunclet], CloneParent);
+  }
+}
+
+// Clones all blocks used by the specified funclet to avoid the funclet having
+// multiple parent funclets.  All terminators in the parent that unwind to the
+// original funclet are remapped to unwind to the clone.  Any terminator in the
+// original funclet which returned to this parent is converted to an unreachable
+// instruction. Likewise, any terminator in the cloned funclet which returns to
+// a parent funclet other than the specified parent is converted to an
+// unreachable instruction.
+BasicBlock *WinEHPrepare::cloneFuncletForParent(Function &F,
+                                                BasicBlock *FuncletEntry,
+                                                BasicBlock *Parent) {
+  std::set<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletEntry];
+
+  DEBUG_WITH_TYPE("winehprepare-coloring",
+                  dbgs() << "Cloning funclet \'" << FuncletEntry->getName()
+                         << "\' for parent \'" << Parent->getName() << "\'.\n");
+
+  std::map<BasicBlock *, BasicBlock *> Orig2Clone;
+  ValueToValueMapTy VMap;
+  for (BasicBlock *BB : BlocksInFunclet) {
+    // Create a new basic block and copy instructions into it.
+    BasicBlock *CBB =
+        CloneBasicBlock(BB, VMap, Twine(".from.", Parent->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;
+  } // end for (BasicBlock *BB : BlocksInFunclet)
+
+  BasicBlock *ClonedFunclet = Orig2Clone[FuncletEntry];
+  assert(ClonedFunclet);
+
+  // Set the coloring for the blocks we just cloned.
+  std::set<BasicBlock *> &ClonedBlocks = FuncletBlocks[ClonedFunclet];
+  for (auto &BBMapping : Orig2Clone) {
+    BasicBlock *NewBlock = BBMapping.second;
+    ClonedBlocks.insert(NewBlock);
+    BlockColors[NewBlock].insert(ClonedFunclet);
+
+    DEBUG_WITH_TYPE("winehprepare-coloring",
+                    dbgs() << "  Assigning color \'" << ClonedFunclet->getName()
+                           << "\' to block \'" << NewBlock->getName()
+                           << "\'.\n");
+
+    // Use the VMap to remap the instructions in this cloned block.
+    for (Instruction &I : *NewBlock)
+      RemapInstruction(&I, VMap, RF_IgnoreMissingEntries);
+  }
+
+  // All the cloned blocks have to be colored in the loop above before we can
+  // update the terminators because doing so can require checking the color of
+  // other blocks in the cloned funclet.
+  for (auto &BBMapping : Orig2Clone) {
+    BasicBlock *OldBlock = BBMapping.first;
+    BasicBlock *NewBlock = BBMapping.second;
+
+    // Update the terminator, if necessary, in both the original block and the
+    // cloned so that the original funclet never returns to a block in the
+    // clone parent and the clone funclet never returns to a block in any other
+    // of the original funclet's parents.
+    updateTerminatorsAfterFuncletClone(F, FuncletEntry, ClonedFunclet, OldBlock,
+                                       NewBlock, Parent, VMap, Orig2Clone);
+
+    // Check to see if the cloned block successor has PHI nodes. If so, we need
+    // to add entries to the PHI nodes for the cloned block now.
+    for (BasicBlock *SuccBB : successors(NewBlock)) {
+      for (Instruction &SuccI : *SuccBB) {
+        auto *SuccPN = dyn_cast<PHINode>(&SuccI);
+        if (!SuccPN)
+          break;
+
+        // Ok, we have a PHI node.  Figure out what the incoming value was for
+        // the OldBlock.
+        int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
+        if (OldBlockIdx == -1)
+          break;
+        Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
+
+        // Remap the value if necessary.
+        if (auto *Inst = dyn_cast<Instruction>(IV)) {
+          ValueToValueMapTy::iterator I = VMap.find(Inst);
+          if (I != VMap.end())
+            IV = I->second;
+        }
+
+        SuccPN->addIncoming(IV, NewBlock);
+      }
+    }
+  }
+
+  // Erase the clone's parent from the original funclet's parent list.
+  std::vector<BasicBlock *> &Parents = FuncletParents[FuncletEntry];
+  Parents.erase(std::remove(Parents.begin(), Parents.end(), Parent),
+                Parents.end());
+
+  // Store the cloned funclet's parent.
+  assert(std::find(FuncletParents[ClonedFunclet].begin(),
+                   FuncletParents[ClonedFunclet].end(),
+                   Parent) == std::end(FuncletParents[ClonedFunclet]));
+  FuncletParents[ClonedFunclet].push_back(Parent);
+
+  // Copy any children of the original funclet to the clone.  We'll either
+  // clone them too or make that path unreachable when we take the next step
+  // in resolveFuncletAncestryForPath().
+  for (auto *Child : FuncletChildren[FuncletEntry]) {
+    assert(std::find(FuncletChildren[ClonedFunclet].begin(),
+                     FuncletChildren[ClonedFunclet].end(),
+                     Child) == std::end(FuncletChildren[ClonedFunclet]));
+    FuncletChildren[ClonedFunclet].push_back(Child);
+    assert(std::find(FuncletParents[Child].begin(), FuncletParents[Child].end(),
+                     ClonedFunclet) == std::end(FuncletParents[Child]));
+    FuncletParents[Child].push_back(ClonedFunclet);
+  }
+
+  // Find any blocks that unwound to the original funclet entry from the
+  // clone parent block and remap them to the clone.
+  for (auto *U : FuncletEntry->users()) {
+    auto *UT = dyn_cast<TerminatorInst>(U);
+    if (!UT)
+      continue;
+    BasicBlock *UBB = UT->getParent();
+    assert(BlockColors[UBB].size() == 1);
+    BasicBlock *UFunclet = *(BlockColors[UBB].begin());
+    // Funclets shouldn't be able to loop back on themselves.
+    assert(UFunclet != FuncletEntry);
+    // If this instruction unwinds to the original funclet from the clone
+    // parent, remap the terminator so that it unwinds to the clone instead.
+    // We will perform a similar transformation for siblings after all
+    // the siblings have been cloned.
+    if (UFunclet == Parent) {
+      // We're about to break the path from this block to the uncloned funclet
+      // entry, so remove it as a predeccessor to clean up the PHIs.
+      FuncletEntry->removePredecessor(UBB);
+      TerminatorInst *Terminator = UBB->getTerminator();
+      RemapInstruction(Terminator, VMap, RF_IgnoreMissingEntries);
+    }
+  }
+
+  // This asserts a condition that is relied upon inside the loop below,
+  // namely that no predecessors of the original funclet entry block
+  // are also predecessors of the cloned funclet entry block.
+  assert(std::all_of(pred_begin(FuncletEntry), pred_end(FuncletEntry),
+                     [&ClonedFunclet](BasicBlock *Pred) {
+                       return std::find(pred_begin(ClonedFunclet),
+                                        pred_end(ClonedFunclet),
+                                        Pred) == pred_end(ClonedFunclet);
+                     }));
+
+  // Remove any invalid PHI node entries in the cloned funclet.cl
+  std::vector<PHINode *> PHIsToErase;
+  for (Instruction &I : *ClonedFunclet) {
+    auto *PN = dyn_cast<PHINode>(&I);
+    if (!PN)
+      break;
+
+    // Predecessors of the original funclet do not reach the cloned funclet,
+    // but the cloning process assumes they will.  Remove them now.
+    for (auto *Pred : predecessors(FuncletEntry))
+      PN->removeIncomingValue(Pred, false);
+  }
+  for (auto *PN : PHIsToErase)
+    PN->eraseFromParent();
+
+  // Replace the original funclet in the parent's children vector with the
+  // cloned funclet.
+  for (auto &It : FuncletChildren[Parent]) {
+    if (It == FuncletEntry) {
+      It = ClonedFunclet;
+      break;
+    }
+  }
+
+  return ClonedFunclet;
+}
+
+// Removes the unwind edge for any exceptional terminators within the specified
+// parent funclet that previously unwound to the specified child funclet.
+void WinEHPrepare::makeFuncletEdgeUnreachable(BasicBlock *Parent,
+                                              BasicBlock *Child) {
+  for (BasicBlock *BB : FuncletBlocks[Parent]) {
+    TerminatorInst *Terminator = BB->getTerminator();
+    if (!Terminator->isExceptional())
+      continue;
+
+    // Look for terninators that unwind to the child funclet.
+    BasicBlock *UnwindDest = nullptr;
+    if (auto *I = dyn_cast<InvokeInst>(Terminator))
+      UnwindDest = I->getUnwindDest();
+    else if (auto *I = dyn_cast<CatchEndPadInst>(Terminator))
+      UnwindDest = I->getUnwindDest();
+    else if (auto *I = dyn_cast<TerminatePadInst>(Terminator))
+      UnwindDest = I->getUnwindDest();
+    // cleanupendpad, catchret and cleanupret don't represent a parent-to-child
+    // funclet transition, so we don't need to consider them here.
+
+    // If the child funclet is the unwind destination, replace the terminator
+    // with an unreachable instruction.
+    if (UnwindDest == Child)
+      removeUnwindEdge(BB);
+  }
+  // The specified parent is no longer a parent of the specified child.
+  std::vector<BasicBlock *> &Children = FuncletChildren[Parent];
+  Children.erase(std::remove(Children.begin(), Children.end(), Child),
+                 Children.end());
+}
+
+// This routine is called after funclets with multiple parents are cloned for
+// a specific parent.  Here we look for children of the specified funclet that
+// unwind to other children of that funclet and update the unwind destinations
+// to ensure that each sibling is connected to the correct clone of the sibling
+// to which it unwinds.
+//
+// If the terminator is an invoke instruction, it unwinds either to a child
+// EH pad, a cleanup end pad in the current funclet, or a catch end pad in a
+// parent funclet (which ends either the current catch pad or a sibling
+// catch pad).  If it unwinds to a child EH pad, the child will have multiple
+// parents after this funclet is cloned and this case will be handled later in
+// the resolveFuncletAncestryForPath processing.  If it unwinds to a
+// cleanup end pad in the current funclet, the instruction remapping during
+// the cloning process should have already mapped the unwind destination to
+// the cloned copy of the cleanup end pad.  If it unwinds to a catch end pad
+// there are two possibilities: either the catch end pad is the unwind
+// destination for the catch pad we are currently cloning or it is the unwind
+// destination for a sibling catch pad.  If it it the unwind destination of the
+// catch pad we are cloning, we need to update the cloned invoke instruction
+// to unwind to the cloned catch end pad.  Otherwise, we will handle this
+// later (in resolveFuncletAncestryForPath).
+static void updateSiblingToSiblingUnwind(
+    BasicBlock *CurFunclet,
+    std::map<BasicBlock *, SetVector<BasicBlock *>> &BlockColors,
+    std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks,
+    std::map<BasicBlock *, std::vector<BasicBlock *>> &FuncletParents,
+    std::map<BasicBlock *, std::vector<BasicBlock *>> &FuncletChildren,
+    std::map<BasicBlock *, BasicBlock *> &Funclet2Orig) {
+  // Remap any bad sibling-to-sibling transitions for funclets that
+  // we just cloned.
+  for (BasicBlock *ChildFunclet : FuncletChildren[CurFunclet]) {
+    for (auto *BB : FuncletBlocks[ChildFunclet]) {
+      TerminatorInst *Terminator = BB->getTerminator();
+      if (!Terminator->isExceptional())
+        continue;
+
+      // See if this terminator has an unwind destination.
+      // Note that catchendpads are handled when the associated catchpad
+      // is cloned.  They don't fit the pattern we're looking for here.
+      BasicBlock *UnwindDest = nullptr;
+      if (auto *I = dyn_cast<CatchPadInst>(Terminator)) {
+        UnwindDest = I->getUnwindDest();
+        // The catchendpad is not a sibling destination.  This case should
+        // have been handled in cloneFuncletForParent().
+        if (isa<CatchEndPadInst>(Terminator)) {
+          assert(BlockColors[UnwindDest].size() == 1 &&
+                 "Cloned catchpad unwinds to an pad with multiple parents.");
+          assert(FuncletParents[UnwindDest].front() == CurFunclet &&
+                 "Cloned catchpad unwinds to the wrong parent.");
+          continue;
+        }
+      } else {
+        if (auto *I = dyn_cast<CleanupReturnInst>(Terminator))
+          UnwindDest = I->getUnwindDest();
+        else if (auto *I = dyn_cast<CleanupEndPadInst>(Terminator))
+          UnwindDest = I->getUnwindDest();
+
+        // If the cleanup unwinds to caller, there is nothing to be done.
+        if (!UnwindDest)
+          continue;
+      }
+
+      // If the destination is not a cleanup pad, catch pad or terminate pad
+      // we don't need to handle it here.
+      Instruction *EHPad = UnwindDest->getFirstNonPHI();
+      if (!isa<CleanupPadInst>(EHPad) && !isa<CatchPadInst>(EHPad) &&
+          !isa<TerminatePadInst>(EHPad))
+        continue;
+
+      // If it is one of these, then it is either a sibling of the current
+      // child funclet or a clone of one of those siblings.
+      // If it is a sibling, no action is needed.
+      if (FuncletParents[UnwindDest].size() == 1 &&
+          FuncletParents[UnwindDest].front() == CurFunclet)
+        continue;
+
+      // If the unwind destination is a clone of a sibling, we need to figure
+      // out which sibling it is a clone of and use that sibling as the
+      // unwind destination.
+      BasicBlock *DestOrig = Funclet2Orig[UnwindDest];
+      BasicBlock *TargetSibling = nullptr;
+      for (auto &Mapping : Funclet2Orig) {
+        if (Mapping.second != DestOrig)
+          continue;
+        BasicBlock *MappedFunclet = Mapping.first;
+        if (FuncletParents[MappedFunclet].size() == 1 &&
+            FuncletParents[MappedFunclet].front() == CurFunclet) {
+          TargetSibling = MappedFunclet;
+        }
+      }
+      // If we didn't find the sibling we were looking for then the
+      // unwind destination is not a clone of one of child's siblings.
+      // That's unexpected.
+      assert(TargetSibling && "Funclet unwinds to unexpected destination.");
+
+      // Update the terminator instruction to unwind to the correct sibling.
+      if (auto *I = dyn_cast<CatchPadInst>(Terminator))
+        I->setUnwindDest(TargetSibling);
+      else if (auto *I = dyn_cast<CleanupReturnInst>(Terminator))
+        I->setUnwindDest(TargetSibling);
+      else if (auto *I = dyn_cast<CleanupEndPadInst>(Terminator))
+        I->setUnwindDest(TargetSibling);
+    }
+  }
+  
+  // Invoke remapping can't be done correctly until after all of their
+  // other sibling-to-sibling unwinds have been remapped.
+  for (BasicBlock *ChildFunclet : FuncletChildren[CurFunclet]) {
+    bool NeedOrigInvokeRemapping = false;
+    for (auto *BB : FuncletBlocks[ChildFunclet]) {
+      TerminatorInst *Terminator = BB->getTerminator();
+      auto *II = dyn_cast<InvokeInst>(Terminator);
+      if (!II)
+        continue;
+
+      BasicBlock *UnwindDest = II->getUnwindDest();
+      assert(UnwindDest && "Invoke unwinds to a null destination.");
+      assert(UnwindDest->isEHPad() && "Invoke does not unwind to an EH pad.");
+      auto *EHPadInst = UnwindDest->getFirstNonPHI();
+      if (isa<CleanupEndPadInst>(EHPadInst)) {
+        // An invoke that unwinds to a cleanup end pad must be in a cleanup pad.
+        assert(isa<CleanupPadInst>(ChildFunclet->getFirstNonPHI()) &&
+               "Unwinding to cleanup end pad from a non cleanup pad funclet.");
+        // The funclet cloning should have remapped the destination to the cloned
+        // cleanup end pad.
+        assert(FuncletBlocks[ChildFunclet].count(UnwindDest) &&
+               "Unwind destination for invoke was not updated during cloning.");
+      } else if (isa<CatchEndPadInst>(EHPadInst)) {
+        // If the invoke unwind destination is the unwind destination for
+        // the current child catch pad funclet, there is nothing to be done.
+        BasicBlock *OrigFunclet = Funclet2Orig[ChildFunclet];
+        auto *CurCatch = cast<CatchPadInst>(ChildFunclet->getFirstNonPHI());
+        auto *OrigCatch = cast<CatchPadInst>(OrigFunclet->getFirstNonPHI());
+        if (OrigCatch->getUnwindDest() == UnwindDest) {
+          // If the invoke unwinds to a catch end pad that is the unwind
+          // destination for the original catch pad, the cloned invoke should
+          // unwind to the cloned catch end pad.
+          II->setUnwindDest(CurCatch->getUnwindDest());
+        } else if (CurCatch->getUnwindDest() == UnwindDest) {
+          // If the invoke unwinds to a catch end pad that is the unwind
+          // destination for the clone catch pad, the original invoke should
+          // unwind to the unwind destination of the original catch pad.
+          // This happens when the catch end pad is matched to the clone
+          // parent when the catchpad instruction is cloned and the original
+          // invoke instruction unwinds to the original catch end pad (which
+          // is now the unwind destination of the cloned catch pad).
+          NeedOrigInvokeRemapping = true;
+        } else {
+          // Otherwise, the invoke unwinds to a catch end pad that is the unwind
+          // destination another catch pad in the unwind chain from either the
+          // current catch pad or one of its clones.  If it is already the
+          // catch end pad at the end unwind chain from the current catch pad,
+          // we'll need to check the invoke instructions in the original funclet
+          // later.  Otherwise, we need to remap this invoke now.
+          assert((getEndPadForCatch(OrigCatch) == UnwindDest ||
+                  getEndPadForCatch(CurCatch) == UnwindDest) &&
+                "Invoke within catch pad unwinds to an invalid catch end pad.");
+          BasicBlock *CurCatchEnd = getEndPadForCatch(CurCatch);
+          if (CurCatchEnd == UnwindDest)
+            NeedOrigInvokeRemapping = true;
+          else
+            II->setUnwindDest(CurCatchEnd);
+        }
+      }
+    }
+    if (NeedOrigInvokeRemapping) {
+      // To properly remap invoke instructions that unwind to catch end pads
+      // that are not the unwind destination of the catch pad funclet in which
+      // the invoke appears, we must also look at the uncloned invoke in the
+      // original funclet.  If we saw an invoke that was already properly
+      // unwinding to a sibling's catch end pad, we need to check the invokes
+      // in the original funclet.
+      BasicBlock *OrigFunclet = Funclet2Orig[ChildFunclet];
+      for (auto *BB : FuncletBlocks[OrigFunclet]) {
+        auto *II = dyn_cast<InvokeInst>(BB->getTerminator());
+        if (!II)
+          continue;
+
+        BasicBlock *UnwindDest = II->getUnwindDest();
+        assert(UnwindDest && "Invoke unwinds to a null destination.");
+        assert(UnwindDest->isEHPad() && "Invoke does not unwind to an EH pad.");
+        auto *CEP = dyn_cast<CatchEndPadInst>(UnwindDest->getFirstNonPHI());
+        if (!CEP)
+          continue;
+
+        // If the invoke unwind destination is the unwind destination for
+        // the original catch pad funclet, there is nothing to be done.
+        auto *OrigCatch = cast<CatchPadInst>(OrigFunclet->getFirstNonPHI());
+
+        // If the invoke unwinds to a catch end pad that is neither the unwind
+        // destination of OrigCatch or the destination another catch pad in the
+        // unwind chain from current catch pad, we need to remap the invoke.
+        BasicBlock *OrigCatchEnd = getEndPadForCatch(OrigCatch);
+        if (OrigCatchEnd != UnwindDest)
+          II->setUnwindDest(OrigCatchEnd);
+      }
+    }
+  }
+}
+
+void WinEHPrepare::resolveFuncletAncestry(
+    Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
+  // Most of the time this will be unnecessary.  If the conditions arise that
+  // require this work, this flag will be set.
+  if (!FuncletCloningRequired)
+    return;
+  
+  // Funclet2Orig is used to map any cloned funclets back to the original
+  // funclet from which they were cloned.  The map is seeded with the
+  // original funclets mapping to themselves.
+  std::map<BasicBlock *, BasicBlock *> Funclet2Orig;
+  for (auto *Funclet : EntryBlocks)
+    Funclet2Orig[Funclet] = Funclet;
+
+  // Start with the entry funclet and walk the funclet parent-child tree.
+  SmallVector<BasicBlock *, 4> FuncletPath;
+  FuncletPath.push_back(&(F.getEntryBlock()));
+  resolveFuncletAncestryForPath(F, FuncletPath, Funclet2Orig);
+}
+
+// Walks the funclet control flow, cloning any funclets that have more than one
+// parent funclet and breaking any cyclic unwind chains so that the path becomes
+// unreachable at the point where a funclet would have unwound to a funclet that
+// was already in the chain.
+void WinEHPrepare::resolveFuncletAncestryForPath(
+    Function &F, SmallVectorImpl<BasicBlock *> &FuncletPath,
+    std::map<BasicBlock *, BasicBlock *> &Funclet2Orig) {
+  bool ClonedAnyChildren = false;
+  BasicBlock *CurFunclet = FuncletPath.back();
+  // Copy the children vector because we might changing it.
+  std::vector<BasicBlock *> Children(FuncletChildren[CurFunclet]);
+  for (BasicBlock *ChildFunclet : Children) {
+    // Don't allow the funclet chain to unwind back on itself.
+    // If this funclet is already in the current funclet chain, make the
+    // path to it through the current funclet unreachable.
+    bool IsCyclic = false;
+    BasicBlock *ChildIdentity = Funclet2Orig[ChildFunclet];
+    for (BasicBlock *Ancestor : FuncletPath) {
+      BasicBlock *AncestorIdentity = Funclet2Orig[Ancestor];
+      if (AncestorIdentity == ChildIdentity) {
+        IsCyclic = true;
+        break;
+      }
+    }
+    // If the unwind chain wraps back on itself, break the chain.
+    if (IsCyclic) {
+      makeFuncletEdgeUnreachable(CurFunclet, ChildFunclet);
+      continue;
+    }
+    // If this child funclet has other parents, clone the entire funclet.
+    if (FuncletParents[ChildFunclet].size() > 1) {
+      ChildFunclet = cloneFuncletForParent(F, ChildFunclet, CurFunclet);
+      Funclet2Orig[ChildFunclet] = ChildIdentity;
+      ClonedAnyChildren = true;
+    }
+    FuncletPath.push_back(ChildFunclet);
+    resolveFuncletAncestryForPath(F, FuncletPath, Funclet2Orig);
+    FuncletPath.pop_back();
+  }
+  // If we didn't clone any children, we can return now.
+  if (!ClonedAnyChildren)
+    return;
+
+  updateSiblingToSiblingUnwind(CurFunclet, BlockColors, FuncletBlocks,
+                               FuncletParents, FuncletChildren, Funclet2Orig);
+}
+
+void WinEHPrepare::colorFunclets(Function &F,
+                                 SmallVectorImpl<BasicBlock *> &EntryBlocks) {
+  ::colorFunclets(F, EntryBlocks, BlockColors, FuncletBlocks);
 
   // 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);
+    SetVector<BasicBlock *> &ColorMapItem = BlockColors[FuncletEntry];
+    // It will be rare for funclets to have multiple parents, but if any
+    // do we need to clone the funclet later to address that.  Here we
+    // set a flag indicating that this case has arisen so that we don't
+    // have to do a lot of checking later to handle the more common case.
+    if (ColorMapItem.size() > 1)
+      FuncletCloningRequired = true;
+    for (BasicBlock *Parent : ColorMapItem) {
+      assert(std::find(FuncletChildren[Parent].begin(),
+                       FuncletChildren[Parent].end(),
+                       FuncletEntry) == std::end(FuncletChildren[Parent]));
+      FuncletChildren[Parent].push_back(FuncletEntry);
+      assert(std::find(FuncletParents[FuncletEntry].begin(),
+                       FuncletParents[FuncletEntry].end(),
+                       Parent) == std::end(FuncletParents[FuncletEntry]));
+      FuncletParents[FuncletEntry].push_back(Parent);
+    }
     ColorMapItem.clear();
     ColorMapItem.insert(FuncletEntry);
   }
 }
 
-void WinEHPrepare::colorFunclets(Function &F,
-                                 SmallVectorImpl<BasicBlock *> &EntryBlocks) {
-  ::colorFunclets(F, EntryBlocks, BlockColors, FuncletBlocks, FuncletChildren);
-}
-
 void llvm::calculateCatchReturnSuccessorColors(const Function *Fn,
                                                WinEHFuncInfo &FuncInfo) {
   SmallVector<BasicBlock *, 4> EntryBlocks;
   // colorFunclets needs the set of EntryBlocks, get them using
   // findFuncletEntryPoints.
   findFuncletEntryPoints(const_cast<Function &>(*Fn), EntryBlocks);
 
-  std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
+  std::map<BasicBlock *, SetVector<BasicBlock *>> BlockColors;
   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
-  std::map<BasicBlock *, std::set<BasicBlock *>> FuncletChildren;
   // Figure out which basic blocks belong to which funclets.
   colorFunclets(const_cast<Function &>(*Fn), EntryBlocks, BlockColors,
-                FuncletBlocks, FuncletChildren);
+                FuncletBlocks);
+
+  // The static colorFunclets routine assigns multiple colors to funclet entries
+  // because that information is needed to calculate funclets' parent-child
+  // relationship, but we don't need those relationship here and ultimately the
+  // entry blocks should have the color of the funclet they begin.
+  for (BasicBlock *FuncletEntry : EntryBlocks) {
+    BlockColors[FuncletEntry].clear();
+    BlockColors[FuncletEntry].insert(FuncletEntry);
+  }
 
   // We need to find the catchret successors.  To do this, we must first find
   // all the catchpad funclets.
   for (auto &Funclet : FuncletBlocks) {
     // Figure out what kind of funclet we are looking at; We only care about
     // catchpads.
     BasicBlock *FuncletPadBB = Funclet.first;
     Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
     auto *CatchPad = dyn_cast<CatchPadInst>(FirstNonPHI);
     if (!CatchPad)
       continue;
 
     // The users of a catchpad are always catchrets.
     for (User *Exit : CatchPad->users()) {
       auto *CatchReturn = dyn_cast<CatchReturnInst>(Exit);
       if (!CatchReturn)
         continue;
       BasicBlock *CatchRetSuccessor = CatchReturn->getSuccessor();
-      std::set<BasicBlock *> &SuccessorColors = BlockColors[CatchRetSuccessor];
+      SetVector<BasicBlock *> &SuccessorColors = BlockColors[CatchRetSuccessor];
       assert(SuccessorColors.size() == 1 && "Expected BB to be monochrome!");
       BasicBlock *Color = *SuccessorColors.begin();
       // Record the catchret successor's funclet membership.
       FuncInfo.CatchRetSuccessorColorMap[CatchReturn] = Color;
     }
   }
 }
 
for (auto *PN : PHINodes) {
     PN->eraseFromParent();
   }
 }
 
 void WinEHPrepare::demoteUsesBetweenFunclets(Function &F) {
   // Turn all inter-funclet uses of a Value into loads and stores.
   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
     BasicBlock *BB = &*FI++;
-    std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
+    SetVector<BasicBlock *> &ColorsForBB = BlockColors[BB];
     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
       Instruction *I = &*BI++;
       // Funclets are permitted to use static allocas.
       if (auto *AI = dyn_cast<AllocaInst>(I))
         if (AI->isStaticAlloca())
           continue;
 
       demoteNonlocalUses(I, ColorsForBB, F);
     }
   }
 }
 
 void WinEHPrepare::demoteArgumentUses(Function &F) {
   // Also demote function parameters used in funclets.
-  std::set<BasicBlock *> &ColorsForEntry = BlockColors[&F.getEntryBlock()];
+  SetVector<BasicBlock *> &ColorsForEntry = BlockColors[&F.getEntryBlock()];
   for (Argument &Arg : F.args())
     demoteNonlocalUses(&Arg, ColorsForEntry, F);
 }
 
 void WinEHPrepare::cloneCommonBlocks(
     Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
   // 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 (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];
+    for (auto BlockIt = BlocksInFunclet.begin(),
+              BlockEnd = BlocksInFunclet.end();
+         BlockIt != BlockEnd;) {
+      // Increment the iterator inside the loop because we might be removing
+      // blocks from the set.
+      BasicBlock *BB = *BlockIt++;
+      SetVector<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;
 
+      // If this block is a catchendpad, it shouldn't be cloned.
+      // We will only see a catchendpad with multiple colors in the case where
+      // some funclet has multiple parents.  In that case, the color will be
+      // resolved during the resolveFuncletAncestry processing.
+      // For now, find the catchpad that unwinds to this block and assign
+      // that catchpad's first parent to be the color for this block.
+      if (isa<CatchEndPadInst>(BB->getFirstNonPHI())) {
+        assert(
+            FuncletCloningRequired &&
+            "Found multi-colored catchendpad with no multi-parent funclets.");
+        BasicBlock *CatchParent = nullptr;
+        // There can only be one catchpad predecessor for a catchendpad.
+        for (BasicBlock *PredBB : predecessors(BB)) {
+          if (isa<CatchPadInst>(PredBB->getTerminator())) {
+            CatchParent = PredBB;
+            break;
+          }
+        }
+        // There must be one catchpad predecessor for a catchendpad.
+        assert(CatchParent && "No catchpad found for catchendpad.");
+
+        // If the catchpad has multiple parents, we'll clone the catchendpad
+        // when we clone the catchpad funclet and insert it into the correct
+        // funclet.  For now, we just select the first parent of the catchpad
+        // and give the catchendpad that color.
+        BasicBlock *CorrectColor = FuncletParents[CatchParent].front();
+        assert(FuncletBlocks[CorrectColor].count(BB));
+        assert(BlockColors[BB].count(CorrectColor));
+
+        // Remove this block from the FuncletBlocks set of any funclet that
+        // isn't the funclet whose color we just selected.
+        for (auto It = BlockColors[BB].begin(), End = BlockColors[BB].end();
+             It != End; ) {
+          // The iterator must be incremented here because we are removing
+          // elements from the set we're walking.
+          auto Temp = It++;
+          BasicBlock *ContainingFunclet = *Temp;
+          if (ContainingFunclet != CorrectColor) {
+            FuncletBlocks[ContainingFunclet].erase(BB);
+            BlockColors[BB].remove(ContainingFunclet);
+          }
+        }
+
+        // This should leave just one color for BB.
+        assert(BlockColors[BB].size() == 1);
+        continue;
+      }
+
+      DEBUG_WITH_TYPE("winehprepare-coloring",
+                      dbgs() << "  Cloning block \'" << BB->getName()
+                              << "\' for funclet \'" << FuncletPadBB->getName()
+                              << "\'.\n");
+
       // Create a new basic block and copy instructions into it!
       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.
for (BasicBlock *FuncletPadBB : EntryBlocks) {
     // another has gained a color.
     for (auto &BBMapping : Orig2Clone) {
       BasicBlock *OldBlock = BBMapping.first;
       BasicBlock *NewBlock = BBMapping.second;
 
       BlocksInFunclet.insert(NewBlock);
       BlockColors[NewBlock].insert(FuncletPadBB);
 
+      DEBUG_WITH_TYPE("winehprepare-coloring",
+                      dbgs() << "  Assigned color \'" << FuncletPadBB->getName()
+                              << "\' to block \'" << NewBlock->getName()
+                              << "\'.\n");
+
       BlocksInFunclet.erase(OldBlock);
-      BlockColors[OldBlock].erase(FuncletPadBB);
+      BlockColors[OldBlock].remove(FuncletPadBB);
+
+      DEBUG_WITH_TYPE("winehprepare-coloring",
+                      dbgs() << "  Removed color \'" << FuncletPadBB->getName()
+                              << "\' from block \'" << OldBlock->getName()
+                              << "\'.\n");
+
+      // If we are cloning a funclet that might share a child funclet with
+      // another funclet, look to see if the cloned block is reached from a
+      // catchret instruction.  If so, save this association so we can retrieve
+      // the possibly orphaned clone when we clone the child funclet.
+      if (FuncletCloningRequired) {
+        for (auto *Pred : predecessors(OldBlock)) {
+          auto *Terminator = Pred->getTerminator();
+          if (!isa<CatchReturnInst>(Terminator))
+            continue;
+          // If this block is reached from a catchret instruction in a funclet
+          // that has multiple parents, it will have a color for each of those
+          // parents.  We just removed the color of one of the parents, but
+          // the cloned block will be unreachable until we clone the child
+          // funclet that contains the catchret instruction.  In that case we
+          // need to create a mapping that will let us find the cloned block
+          // later and associate it with the cloned child funclet.
+          bool BlockWillBeEstranged = false;
+          for (auto *Color : BlockColors[Pred]) {
+            if (FuncletParents[Color].size() > 1) {
+              BlockWillBeEstranged = true;
+              break; // Breaks out of the color loop
+            }
+          }
+          if (BlockWillBeEstranged) {
+            EstrangedBlocks[FuncletPadBB][OldBlock] = NewBlock;
+            DEBUG_WITH_TYPE("winehprepare-coloring",
+                            dbgs() << "  Saved mapping of estranged block \'"
+                                  << NewBlock->getName() << "\' for \'"
+                                  << FuncletPadBB->getName() << "\'.\n");
+            break; // Breaks out of the predecessor loop
+          }
+        }
+      }
     }
 
     // Loop over all of the instructions in this funclet, fixing up operand
     // references as we go.  This uses VMap to do all the hard work.
     for (BasicBlock *BB : BlocksInFunclet)
       // Loop over all instructions, fixing each one as we find it...
       for (Instruction &I : *BB)
         RemapInstruction(&I, VMap,
for (ValueToValueMapTy::value_type VT : VMap) {
       if (!OldI)
         continue;
       auto *NewI = cast<Instruction>(VT.second);
       // Scan all uses of this instruction to see if it is used outside of its
       // funclet, and if so, record them in UsesToRename.
       for (Use &U : OldI->uses()) {
         Instruction *UserI = cast<Instruction>(U.getUser());
         BasicBlock *UserBB = UserI->getParent();
-        std::set<BasicBlock *> &ColorsForUserBB = BlockColors[UserBB];
+        SetVector<BasicBlock *> &ColorsForUserBB = BlockColors[UserBB];
         assert(!ColorsForUserBB.empty());
         if (ColorsForUserBB.size() > 1 ||
             *ColorsForUserBB.begin() != FuncletPadBB)
           UsesToRename.push_back(&U);
       }
 
       // If there are no uses outside the block, we're done with this
       // instruction.
if (!DisableDemotion) {
 
     demoteUsesBetweenFunclets(F);
 
     demoteArgumentUses(F);
   }
 
   cloneCommonBlocks(F, EntryBlocks);
 
+  resolveFuncletAncestry(F, EntryBlocks);
+
   if (!DisableCleanups) {
     removeImplausibleTerminators(F);
 
     cleanupPreparedFunclets(F);
   }
 
   verifyPreparedFunclets(F);
 
   BlockColors.clear();
   FuncletBlocks.clear();
   FuncletChildren.clear();
+  FuncletParents.clear();
+  EstrangedBlocks.clear();
+  FuncletCloningRequired = false;
 
   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();
if (PredBlock->isEHPad() &&
     Worklist.push_back({PredBlock, PredVal});
     return;
   }
 
   // Otherwise, insert the store at the end of the basic block.
   new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
 }
 
+// The SetVector == operator uses the std::vector == operator, so it doesn't
+// actually tell us whether or not the two sets contain the same colors. This
+// function does that.
+// FIXME: Would it be better to add a isSetEquivalent() method to SetVector?
+static bool isBlockColorSetEquivalent(SetVector<BasicBlock *> &SetA,
+                                      SetVector<BasicBlock *> &SetB) {
+  if (SetA.size() != SetB.size())
+    return false;
+  for (auto *Color : SetA)
+    if (!SetB.count(Color))
+      return false;
+  return true;
+}
+
 // TODO: Share loads for same-funclet uses (requires dominators if funclets
 // aren't properly nested).
 void WinEHPrepare::demoteNonlocalUses(Value *V,
-                                      std::set<BasicBlock *> &ColorsForBB,
+                                      SetVector<BasicBlock *> &ColorsForBB,
                                       Function &F) {
   // Tokens can only be used non-locally due to control flow involving
   // unreachable edges.  Don't try to demote the token usage, we'll simply
   // delete the cloned user later.
   if (isa<CatchPadInst>(V) || isa<CleanupPadInst>(V))
     return;
 
   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 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 (ColorsForUsingBB == ColorsForBB)
+    SetVector<BasicBlock *> &ColorsForUsingBB = BlockColors[UsingBB];
+    if (isBlockColorSetEquivalent(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.
     BasicBlock::iterator InsertPt;
     if (isa<Argument>(V)) {
       InsertPt = F.getEntryBlock().getTerminator()->getIterator();
     } else if (isa<TerminatorInst>(V)) {
       auto *II = cast<InvokeInst>(V);
       // We cannot demote invoke instructions to the stack if their normal
       // edge is critical. Therefore, split the critical edge and create a
       // basic block into which the store can be inserted.
       if (!II->getNormalDest()->getSinglePredecessor()) {
         unsigned SuccNum =
             GetSuccessorNumber(II->getParent(), II->getNormalDest());
         assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!");
         BasicBlock *NewBlock = SplitCriticalEdge(II, SuccNum);
         assert(NewBlock && "Unable to split critical edge.");
         // Update the color mapping for the newly split edge.
-        std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[II->getParent()];
+        SetVector<BasicBlock *> &ColorsForUsingBB = BlockColors[II->getParent()];
         BlockColors[NewBlock] = ColorsForUsingBB;
         for (BasicBlock *FuncletPad : ColorsForUsingBB)
           FuncletBlocks[FuncletPad].insert(NewBlock);
       }
       InsertPt = II->getNormalDest()->getFirstInsertionPt();
     } else {
       InsertPt = cast<Instruction>(V)->getIterator();
       ++InsertPt;
if (auto *CatchRet =
       BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
       Goto->removeFromParent();
       CatchRet->removeFromParent();
       IncomingBlock->getInstList().push_back(CatchRet);
       NewBlock->getInstList().push_back(Goto);
       Goto->setSuccessor(0, PHIBlock);
       CatchRet->setSuccessor(NewBlock);
       // Update the color mapping for the newly split edge.
-      std::set<BasicBlock *> &ColorsForPHIBlock = BlockColors[PHIBlock];
+      SetVector<BasicBlock *> &ColorsForPHIBlock = BlockColors[PHIBlock];
       BlockColors[NewBlock] = ColorsForPHIBlock;
       for (BasicBlock *FuncletPad : ColorsForPHIBlock)
         FuncletBlocks[FuncletPad].insert(NewBlock);
       // Treat the new block as incoming for load insertion.
       IncomingBlock = NewBlock;
     }
     Value *&Load = Loads[IncomingBlock];
     // Insert the load into the predecessor block

llvm/trunk/test/CodeGen/WinEH/wineh-cloning.ll

 ; 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: define void @test6(
-; TODO: CHECKs
+; CHECK:     left:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:       %x = call i32 @g()
+; CHECK:       store i32 %x, i32* %x.wineh.spillslot
+; CHECK:           to label %shared.cont unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     shared.cont:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_R:\%.+]] = cleanuppad []
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       cleanupret [[I_R]] unwind label %right.end
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_L:\%.+]] = cleanuppad []
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
 
 
 define void @test7() personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   invoke void @f()
     to label %invoke.cont unwind label %left
 invoke.cont:
   invoke void @f()
inner:
   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: define void @test7(
-; TODO: CHECKs
+; CHECK:     invoke.cont:
+; CHECK:           to label %[[UNREACHABLE_ENTRY:.+]] unwind label %right
+; CHECK:     left:
+; CHECK:           to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:           to label %unreachable unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_R:\%.+]] = cleanuppad []
+; CHECK:       [[X_R:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X_R]])
+; CHECK:       cleanupret [[I_R]] unwind label %right.end
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_L:\%.+]] = cleanuppad []
+; CHECK:       [[X_L:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X_L]])
+; CHECK:       unreachable
+; CHECK:     unreachable:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_ENTRY]]:
+; CHECK:       unreachable
 
 
 define void @test8() personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   invoke void @f()
     to label %invoke.cont unwind label %left
 invoke.cont:
   invoke void @f()
inner.child:
   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: define void @test8(
-; TODO: CHECKs
+; CHECK:     invoke.cont:
+; CHECK:               to label %[[UNREACHABLE_ENTRY:.+]] unwind label %right
+; CHECK:     left:
+; CHECK:               to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:               to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:               to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:               to label %[[UNREACHABLE_INNER_RIGHT:.+]] unwind label %[[INNER_CHILD_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:               to label %[[UNREACHABLE_INNER_LEFT:.+]] unwind label %[[INNER_CHILD_LEFT:.+]]
+; CHECK:     [[INNER_CHILD_RIGHT]]:
+; CHECK:       [[TMP:\%.+]] = cleanuppad []
+; CHECK:       [[X:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CHILD_LEFT]]:
+; CHECK:       [[TMP:\%.+]] = cleanuppad []
+; CHECK:       [[X:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X]])
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_INNER_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_INNER_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_ENTRY]]:
+; CHECK:       unreachable
 
 
 define void @test9() personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   invoke void @f()
     to label %invoke.cont unwind label %left
 invoke.cont:
   invoke void @f()

 ; 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: define void @test9(
-; TODO: CHECKs
+; CHECK:     entry:
+; CHECK:               to label %invoke.cont unwind label %[[LEFT:.+]]
+; CHECK:     invoke.cont:
+; CHECK:               to label %[[UNREACHABLE_ENTRY:.+]] unwind label %[[RIGHT:.+]]
+; CHECK:     [[LEFT_FROM_RIGHT:.+]]:
+; CHECK:       call void @h(i32 1)
+; CHECK:       call void @f()
+; CHECK:       unreachable
+; CHECK:     [[LEFT]]:
+; CHECK:       call void @h(i32 1)
+; CHECK:       invoke void @f()
+; CHECK:               to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[RIGHT_FROM_LEFT:.+]]
+; CHECK:     [[RIGHT]]:
+; CHECK:       call void @h(i32 2)
+; CHECK:       invoke void @f()
+; CHECK:               to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[LEFT_FROM_RIGHT]]
+; CHECK:     [[RIGHT_FROM_LEFT]]:
+; CHECK:       call void @h(i32 2)
+; CHECK:       call void @f()
+; CHECK:       unreachable
+; 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 []
   ; make sure we don't overlook this cleanupret and try to process

llvm/trunk/test/CodeGen/WinEH/wineh-demotion.ll

 
 catch.inner:
   ; Need just one store here because only %y is affected
   ; CHECK: catch.inner:
   %z = call i32 @g()
   ; CHECK:   store i32 %z
   ; CHECK-NEXT: invoke void @f
   invoke void @f()
-          to label %catchret.inner unwind label %merge.outer
+          to label %catchret.inner unwind label %catchend.inner
 
 catchret.inner:
   catchret %cpinner to label %exit
 catchend.inner:
+  ; CHECK-NOT: = phi
+  %y = phi i32 [ %x, %merge.inner ], [ %z, %catch.inner ]
   catchendpad unwind label %merge.outer
 
 merge.outer:
   ; CHECK: merge.outer:
-  ; CHECK-NOT: = phi
   ; CHECK: [[CatchPad:%[^ ]+]] = catchpad []
-  %y = phi i32 [ %x, %catchend.inner ], [ %z, %catch.inner ]
   %cpouter = catchpad [] to label %catch.outer unwind label %catchend.outer
 
 catchend.outer:
   catchendpad unwind to caller
 
 catch.outer:
   ; Need to load x and y from two different slots since they're both live
   ; and can have different values (if we came from catch.inner)

llvm/trunk/test/CodeGen/WinEH/wineh-multi-parent-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:
+  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: define void @test1(
+; CHECK:     left:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:       %x = call i32 @g()
+; CHECK:       store i32 %x, i32* %x.wineh.spillslot
+; CHECK:           to label %shared.cont unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     shared.cont:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_R:\%.+]] = cleanuppad []
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       cleanupret [[I_R]] unwind label %right.end
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_L:\%.+]] = cleanuppad []
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+
+
+define void @test2() 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:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %right.end
+exit:
+  ret void
+}
+; In this case left and right are both parents of inner.  This differs from
+; @test1 in that inner is a catchpad rather than a cleanuppad, which makes
+; inner.end a block that gets cloned so that left and right each contain a
+; copy (catchendpad blocks are considered to be part of the parent funclet
+; of the associated catchpad). The catchendpad in %inner.end unwinds to
+; %right.end (which belongs to the entry funclet).
+; CHECK-LABEL: define void @test2(
+; CHECK:     left:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %[[RIGHT_END:.+]]
+; CHECK:     right.catch:
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind label %[[RIGHT_END]]
+
+define void @test3() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  %l = cleanuppad []
+  br label %shared
+left.end:
+  cleanupendpad %l unwind label %right
+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:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; In this case, %left and %right are siblings with %entry as the parent of both,
+; while %left and %right are both parents of %inner.  The catchendpad in
+; %inner.end unwinds to %left.end.  When %inner is cloned a copy of %inner.end
+; will be made for both %left and %right, but because %left.end is a cleanup pad
+; and %right is a catch pad the unwind edge from the copy of %inner.end for
+; %right must be removed.
+; CHECK-LABEL: define void @test3(
+; CHECK:     left:
+; CHECK:       %l = cleanuppad []
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[LEFT_END:left.end.*]]:
+; CHECK:       cleanupendpad %l unwind label %right
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %[[RIGHT_END:.+]]
+; CHECK:     right.catch:
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+
+define void @test4() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  catchpad []
+    to label %left.catch unwind label %left.end
+left.catch:
+  br label %shared
+left.end:
+  catchendpad unwind label %right
+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:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This is a variation of @test3 in which both %left and %right are catch pads.
+; In this case, %left and %right are siblings with %entry as the parent of both,
+; while %left and %right are both parents of %inner.  The catchendpad in
+; %inner.end unwinds to %left.end.  When %inner is cloned a copy of %inner.end
+; will be made for both %left and %right, but because the catchpad in %right
+; does not unwind to %left.end the unwind edge from the copy of %inner.end for
+; %right must be removed.
+; CHECK-LABEL: define void @test4(
+; CHECK:     left:
+; CHECK:       catchpad []
+; CHECK:           to label %left.catch unwind label %[[LEFT_END:.+]]
+; CHECK:     left.catch:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind label %right
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %[[RIGHT_END:.+]]
+; CHECK:     right.catch:
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+
+
+define void @test5() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  catchpad []
+    to label %left.catch unwind label %left.end
+left.catch:
+  br label %shared
+left.end:
+  catchendpad unwind label %right
+right:
+  %r = cleanuppad []
+  br label %shared
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; Like @test3, %left and %right are siblings with %entry as the parent of both,
+; while %left and %right are both parents of %inner.  This case makes %left a
+; catch and %right a cleanup so that %inner unwinds to %left.end, which is a
+; block in %entry.  The %inner funclet is cloned for %left and %right, but the
+; copy of %inner.end for %right must have its unwind edge removed because the
+; catchendpad at %left.end is not compatible with %right.
+; CHECK-LABEL: define void @test5(
+; CHECK:     left:
+; CHECK:       catchpad []
+; CHECK:           to label %left.catch unwind label %[[LEFT_END:.+]]
+; CHECK:     left.catch:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind label %right
+; CHECK:     right:
+; CHECK:       %r = cleanuppad []
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+
+define void @test6() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  catchpad []
+    to label %left.catch unwind label %left.end
+left.catch:
+  br label %shared
+left.end:
+  catchendpad unwind label %middle
+middle:
+  %m = catchpad []
+    to label %middle.catch unwind label %middle.end
+middle.catch:
+  catchret %m to label %exit
+middle.end:
+  catchendpad unwind label %right
+right:
+  %r = cleanuppad []
+  br label %shared
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This is like @test5 but it inserts another sibling between %left and %right.
+; In this case %left, %middle and %right are all siblings, while %left and
+; %right are both parents of %inner.  This checks the proper handling of the
+; catchendpad in %inner.end (which will be cloned so that %left and %right both
+; have copies) unwinding to a catchendpad that unwinds to a sibling.
+; CHECK-LABEL: define void @test6(
+; CHECK:     left:
+; CHECK:       catchpad []
+; CHECK:           to label %left.catch unwind label %[[LEFT_END:.+]]
+; CHECK:     left.catch:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind label %middle
+; CHECK:     middle:
+; CHECK:       catchpad []
+; CHECK:         to label %middle.catch unwind label %middle.end
+; CHECK:     middle.catch:
+; CHECK:       catchret %m to label %exit
+; CHECK:     middle.end:
+; CHECK:       catchendpad unwind label %right
+; CHECK:     right:
+; CHECK:       %r = cleanuppad []
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+
+
+define void @test7() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  catchpad []
+    to label %left.catch unwind label %left.end
+left.catch:
+  br label %shared
+left.end:
+  catchendpad unwind label %right
+right:
+  %r = cleanuppad []
+  br label %shared
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %inner.sibling
+inner.sibling:
+  %is = cleanuppad []
+  call void @h(i32 0)
+  cleanupret %is unwind label %left.end
+exit:
+  ret void
+}
+; This is like @test5 but instead of unwinding to %left.end, the catchendpad
+; in %inner.end unwinds to a sibling cleanup pad. Both %inner (along with its
+; associated blocks) and %inner.sibling must be cloned for %left and %right.
+; The clones of %inner will be identical, but the copy of %inner.sibling for
+; %right must end with an unreachable instruction, because it cannot unwind to
+; %left.end.
+; CHECK-LABEL: define void @test7(
+; CHECK:     left:
+; CHECK:       catchpad []
+; CHECK:           to label %left.catch unwind label %[[LEFT_END:.+]]
+; CHECK:     left.catch:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind label %[[RIGHT:.+]]
+; CHECK:     [[RIGHT]]:
+; CHECK:       [[R:\%.+]] = cleanuppad []
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind label %[[INNER_SIBLING_RIGHT:.+]]
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[INNER_SIBLING_LEFT:.+]]
+; CHECK:     [[INNER_SIBLING_RIGHT]]
+; CHECK:       [[IS_R:\%.+]] = cleanuppad []
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_SIBLING_LEFT]]
+; CHECK:       [[IS_L:\%.+]] = cleanuppad []
+; CHECK:       call void @h(i32 0)
+; CHECK:       cleanupret [[IS_L]] unwind label %[[LEFT_END]]
+
+
+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 []
+  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 @test1), this time
+; with the join at the entry itself instead of following a
+; non-pad join.
+; CHECK-LABEL: define void @test8(
+; CHECK:     invoke.cont:
+; CHECK:           to label %[[UNREACHABLE_ENTRY:.+]] unwind label %right
+; CHECK:     left:
+; CHECK:           to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:           to label %unreachable unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_R:\%.+]] = cleanuppad []
+; CHECK:       [[X_R:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X_R]])
+; CHECK:       cleanupret [[I_R]] unwind label %right.end
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_L:\%.+]] = cleanuppad []
+; CHECK:       [[X_L:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X_L]])
+; CHECK:       unreachable
+; CHECK:     unreachable:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_ENTRY]]:
+; CHECK:       unreachable
+
+
+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 []
+  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: define void @test9(
+; CHECK:     invoke.cont:
+; CHECK:               to label %[[UNREACHABLE_ENTRY:.+]] unwind label %right
+; CHECK:     left:
+; CHECK:               to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:               to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:               to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:               to label %[[UNREACHABLE_INNER_RIGHT:.+]] unwind label %[[INNER_CHILD_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:               to label %[[UNREACHABLE_INNER_LEFT:.+]] unwind label %[[INNER_CHILD_LEFT:.+]]
+; CHECK:     [[INNER_CHILD_RIGHT]]:
+; CHECK:       [[TMP:\%.+]] = cleanuppad []
+; CHECK:       [[X:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CHILD_LEFT]]:
+; CHECK:       [[TMP:\%.+]] = cleanuppad []
+; CHECK:       [[X:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X]])
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_INNER_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_INNER_LEFT]]:
+; CHECK:       unreachable
+; 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 %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: define void @test10(
+; CHECK:     entry:
+; CHECK:               to label %invoke.cont unwind label %[[LEFT:.+]]
+; CHECK:     invoke.cont:
+; CHECK:               to label %[[UNREACHABLE_ENTRY:.+]] unwind label %[[RIGHT:.+]]
+; CHECK:     [[LEFT_FROM_RIGHT:.+]]:
+; CHECK:       call void @h(i32 1)
+; CHECK:       call void @f()
+; CHECK:       unreachable
+; CHECK:     [[LEFT]]:
+; CHECK:       call void @h(i32 1)
+; CHECK:       invoke void @f()
+; CHECK:               to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[RIGHT_FROM_LEFT:.+]]
+; CHECK:     [[RIGHT]]:
+; CHECK:       call void @h(i32 2)
+; CHECK:       invoke void @f()
+; CHECK:               to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[LEFT_FROM_RIGHT]]
+; CHECK:     [[RIGHT_FROM_LEFT]]:
+; CHECK:       call void @h(i32 2)
+; CHECK:       call void @f()
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_ENTRY]]:
+; CHECK:       unreachable
+
+
+define void @test11() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  catchpad []
+    to label %left.catch unwind label %left.sibling
+left.catch:
+  br label %shared
+left.sibling:
+  %ls = catchpad []
+    to label %left.sibling.catch unwind label %left.end
+left.sibling.catch:
+  catchret %ls to label %exit
+left.end:
+  catchendpad unwind label %right
+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:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This is a variation of @test4 in which the shared child funclet unwinds to a
+; catchend pad that is the unwind destination of %left.sibling rather than %left
+; but is still a valid destination for %inner as reach from %left.
+; When %inner is cloned a copy of %inner.end will be made for both %left and
+; %right, but because the catchpad in %right does not unwind to %left.end the
+; unwind edge from the copy of %inner.end for %right must be removed.
+; CHECK-LABEL: define void @test11(
+; CHECK:     left:
+; CHECK:       catchpad []
+; CHECK:           to label %left.catch unwind label %left.sibling
+; CHECK:     left.catch:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     left.sibling:
+; CHECK:       catchpad []
+; CHECK:           to label %left.sibling.catch unwind label %[[LEFT_END:.+]]
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind label %right
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %[[RIGHT_END:.+]]
+; CHECK:     right.catch:
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+
+
+define void @test12() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  catchpad []
+    to label %left.catch unwind label %right
+left.catch:
+  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:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %right.end
+exit:
+  ret void
+}
+; In this case %left and %right are both parents of %inner, so %inner must be
+; cloned but the catchendpad unwind target in %inner.end is valid for both
+; parents, so the unwind edge should not be removed in either case.
+; CHECK-LABEL: define void @test12(
+; CHECK:     left:
+; CHECK:       catchpad []
+; CHECK:           to label %left.catch unwind label %right
+; CHECK:     left.catch:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %[[RIGHT_END:.+]]
+; CHECK:     right.catch:
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind label %[[RIGHT_END]]
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[RIGHT_END]]
+
+define void @test13() 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:
+  %l = catchpad []
+    to label %left.cont unwind label %left.end
+left.cont:
+  invoke void @f()
+    to label %left.ret unwind label %inner
+left.ret:
+  catchret %l to label %invoke.cont
+left.end:
+  catchendpad unwind to caller
+right:
+  %r = catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  invoke void @f()
+    to label %right.ret unwind label %inner
+right.ret:
+  catchret %r to label %exit
+right.end:
+  catchendpad unwind to caller
+shared:
+  call void @h(i32 0)
+  unreachable
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 1)
+  catchret %i to label %shared
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This case tests the scenario where a funclet with multiple parents uses a
+; catchret to return to a block that may exist in either parent funclets.
+; Both %left and %right are parents of %inner.  During common block cloning
+; a clone of %shared will be made so that both %left and %right have a copy,
+; but the copy of %shared for one of the parent funclets will be unreachable
+; until the %inner funclet is cloned.  When the %inner.catch block is cloned
+; during the %inner funclet cloning, the catchret instruction should be updated
+; so that the catchret in the copy %inner.catch for %left returns to the copy of
+; %shared in %left and the catchret in the copy of %inner.catch for %right
+; returns to the copy of %shared for %right.
+; CHECK-LABEL: define void @test13(
+; CHECK:     left:
+; CHECK:       %l = catchpad []
+; CHECK:           to label %left.cont unwind label %left.end
+; CHECK:     left.cont:
+; CHECK:       invoke void @f()
+; CHECK:           to label %left.ret unwind label %[[INNER_LEFT:.+]]
+; CHECK:     left.ret:
+; CHECK:       catchret %l to label %invoke.cont
+; CHECK:     left.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     right:
+; CHECK:       %r = catchpad []
+; CHECK:           to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:       invoke void @f()
+; CHECK:           to label %right.ret unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.ret:
+; CHECK:       catchret %r to label %exit
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_RIGHT:.+]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[SHARED_LEFT:.+]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       %[[I_RIGHT:.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       %[[I_LEFT:.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       call void @h(i32 1)
+; CHECK:       catchret %[[I_RIGHT]] to label %[[SHARED_RIGHT]]
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       call void @h(i32 1)
+; CHECK:       catchret %[[I_LEFT]] to label %[[SHARED_LEFT]]
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+
+define void @test14() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  %l = catchpad []
+    to label %shared unwind label %left.end
+left.cont:
+  invoke void @f()
+    to label %left.ret unwind label %right
+left.ret: 
+  catchret %l to label %exit
+left.end:
+  catchendpad unwind to caller
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind label %left.end
+shared:
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 0)
+  catchret %i to label %left.cont
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This case tests another scenario where a funclet with multiple parents uses a
+; catchret to return to a block in one of the parent funclets.  Here %right and
+; %left are both parents of %inner and %left is a parent of %right.  The
+; catchret in %inner.catch will cause %left.cont and %left.ret to be cloned for
+; both %left and %right, but the catchret in %left.ret is invalid for %right
+; but the catchret instruction in the copy of %left.ret for %right will be
+; removed as an implausible terminator.
+; CHECK-LABEL: define void @test14(
+; CHECK:     left:
+; CHECK:       %l = catchpad []
+; CHECK:           to label %[[SHARED_LEFT:.+]] unwind label %[[LEFT_END:.+]]
+; CHECK:     [[LEFT_CONT:left.cont.*]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[LEFT_RET:.+]] unwind label %[[RIGHT:.+]]
+; CHECK:     [[LEFT_RET]]:
+; CHECK:       catchret %l to label %exit
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[SHARED_LEFT]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       catchret [[I_LEFT]] to label %[[LEFT_CONT]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+define void @test15() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  %l = catchpad []
+    to label %left.catch unwind label %left.end
+left.catch:
+  invoke void @f()
+    to label %shared unwind label %right
+left.ret:
+  catchret %l to label %exit
+left.end:
+  catchendpad unwind to caller
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind label %left.end
+shared:
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 0)
+  catchret %i to label %left.ret
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This case is a variation of test14 but instead of returning to an invoke the
+; catchret in %inner.catch returns to a catchret instruction.
+; CHECK-LABEL: define void @test15(
+; CHECK:     left:
+; CHECK:       %l = catchpad []
+; CHECK:           to label %left.catch unwind label %[[LEFT_END:.+]]
+; CHECK:     left.catch:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_LEFT:.+]] unwind label %[[RIGHT:.+]]
+; CHECK:     [[LEFT_RET_RIGHT:.+]]:
+; CHECK:       unreachable
+; CHECK:     [[LEFT_RET_LEFT:.+]]:
+; CHECK:       catchret %l to label %exit
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[SHARED_LEFT]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       catchret [[I_LEFT]] to label %[[LEFT_RET_LEFT]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       catchret [[I_RIGHT]] to label %[[LEFT_RET_RIGHT]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+
+
+define void @test16() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  %l = cleanuppad []
+  br label %shared
+left.cont:
+  cleanupret %l unwind label %right
+left.end:
+  cleanupendpad %l unwind label %right
+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 %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 0)
+  catchret %i to label %left.cont
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This case is another variation of test14 but here the catchret in %inner.catch
+; returns to a cleanupret instruction.
+; CHECK-LABEL: define void @test16(
+; CHECK:     left:
+; CHECK:       %l = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[LEFT_CONT_RIGHT:.+]]:
+; CHECK:       unreachable
+; CHECK:     [[LEFT_CONT_LEFT:.+]]:
+; CHECK:       cleanupret %l unwind label %[[RIGHT:.+]]
+; CHECK:     [[LEFT_END_LEFT:.+]]:
+; CHECK:       cleanupendpad %l unwind label %[[RIGHT]]
+; CHECK:     [[RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       catchret [[I_RIGHT]] to label %[[LEFT_CONT_RIGHT]]
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       catchret [[I_LEFT]] to label %[[LEFT_CONT_LEFT]]
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END_LEFT]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+
+define void @test17() 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:
+  %l = 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
+unreachable:
+  unreachable
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.sibling
+inner.catch:
+  call void @h(i32 0)
+  unreachable
+inner.sibling:
+  %is = catchpad []
+    to label %inner.sibling.catch unwind label %inner.end
+inner.sibling.catch:
+  invoke void @f()
+    to label %unreachable unwind label %inner.end
+inner.end:
+  catchendpad unwind label %right.end
+exit:
+  ret void
+}
+; This case tests the scenario where two catchpads with the same catchendpad
+; have multiple parents.  Both %left and %right are parents of %inner and
+; %inner.sibling so both of the inner funclets must be cloned.  Because
+; the catchendpad in %inner.end unwinds to the catchendpad for %right, the
+; unwind edge should be removed for the copy of %inner.end that is reached
+; from %left.  In addition, the %inner.siblin.catch block contains an invoke
+; that unwinds to the shared inner catchendpad.  The unwind destination for
+; this invoke should be updated to unwind to the correct cloned %inner.end
+; for each path to the funclet.
+; CHECK-LABEL: define void @test17(
+; CHECK:     left:
+; CHECK:       %l = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_SIBLING_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_SIBLING_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_SIBLING_RIGHT]]:
+; CHECK:       [[IS_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_SIBLING_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_SIBLING_LEFT]]:
+; CHECK:       [[IS_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_SIBLING_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_SIBLING_CATCH_RIGHT]]:
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[INNER_END_RIGHT]]
+; CHECK:     [[INNER_SIBLING_CATCH_LEFT]]:
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_END_LEFT]]
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind label %[[RIGHT_END]]
+
+
+define void @test18() 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:
+  %l = 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
+unreachable:
+  unreachable
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.sibling
+inner.catch:
+  invoke void @f()
+    to label %unreachable unwind label %inner.end
+inner.sibling:
+  %is = catchpad []
+    to label %inner.sibling.catch unwind label %inner.end
+inner.sibling.catch:
+  call void @h(i32 0)
+  unreachable
+inner.end:
+  catchendpad unwind label %right.end
+exit:
+  ret void
+}
+; This is like test17 except that the inner invoke is moved from the
+; %inner.sibling funclet to %inner so that it is unwinding to a
+; catchendpad block that has not yet been cloned.  The unwind destination
+; of the invoke should still be updated to reach the correct copy of
+; %inner.end for the path by which it is reached.
+; CHECK-LABEL: define void @test18(
+; CHECK:     left:
+; CHECK:       %l = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_SIBLING_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_SIBLING_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_SIBLING_RIGHT]]:
+; CHECK:       [[IS_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_SIBLING_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT]]
+; CHECK:     [[INNER_SIBLING_LEFT]]:
+; CHECK:       [[IS_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_SIBLING_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT]]
+; CHECK:     [[INNER_SIBLING_CATCH_RIGHT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_SIBLING_CATCH_LEFT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind label %[[RIGHT_END]]
+
+
+define void @test19() 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:
+  %l = 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
+unreachable:
+  unreachable
+inner:
+  %i = cleanuppad []
+  invoke void @f()
+    to label %unreachable unwind label %inner.end
+inner.end:
+  cleanupendpad %i unwind label %right.end
+exit:
+  ret void
+}
+; This case tests the scenario where an invoke in a funclet with multiple
+; parents unwinds to a cleanup end pad for the funclet.  The unwind destination
+; for the invoke should map to the correct copy of the cleanup end pad block.
+; CHECK-LABEL: define void @test19(
+; CHECK:     left:
+; CHECK:       %l = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       cleanupendpad [[I_RIGHT]] unwind label %[[RIGHT_END]]
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       cleanupendpad [[I_LEFT]] unwind to caller
+
+define void @test20() 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:
+  %l = 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
+unreachable:
+  unreachable
+inner:
+  %i = cleanuppad []
+  invoke void @f()
+    to label %unreachable unwind label %inner.cleanup
+inner.cleanup:
+  cleanuppad []
+  call void @f()
+  unreachable
+exit:
+  ret void
+}
+; This tests the case where a funclet with multiple parents contains an invoke
+; instruction that unwinds to a child funclet.  Here %left and %right are both
+; parents of %inner.  Initially %inner is the only parent of %inner.cleanup but
+; after %inner is cloned, %inner.cleanup has multiple parents and so it must
+; also be cloned.
+; CHECK-LABEL: define void @test20(
+; CHECK:     left:
+; CHECK:       %l = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[INNER_CLEANUP_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_CLEANUP_LEFT:.+]]
+; CHECK:     [[INNER_CLEANUP_RIGHT]]:
+; CHECK:       cleanuppad []
+; CHECK:       call void @f()
+; CHECK:       unreachable
+; CHECK:     [[INNER_CLEANUP_LEFT]]:
+; CHECK:       cleanuppad []
+; CHECK:       call void @f()
+; CHECK:       unreachable
+
+

llvm/trunk/test/CodeGen/WinEH/wineh-no-demotion.ll

shared:
   %x = call i32 @g()
   invoke void @f()
           to label %shared.cont unwind label %inner
 
 shared.cont:
   unreachable
 
 inner:
-  ; CHECK: %phi = phi i32 [ %x, %right ], [ 0, %invoke.cont2 ], [ %x.for.left, %left ]
   %phi = phi i32 [ %x, %shared ], [ 0, %invoke.cont2 ]
   %i = cleanuppad []
   call void @h(i32 %phi)
   unreachable
 
+; CHECK [[INNER_INVOKE_CONT2:inner.*]]:
+  ; CHECK: call void @h(i32 0)
+
+; CHECK [[INNER_RIGHT:inner.*]]:
+  ; CHECK: call void @h(i32 %x)
+
+; CHECK [[INNER_LEFT:inner.*]]:
+  ; CHECK: call void @h(i32 %x.for.left)
+
 exit:
   unreachable
 }
 
 ; CHECK-LABEL: @test2(
 define void @test2() personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   invoke void @f()
shared:
   %x = call i32 @g()
   invoke void @f()
           to label %shared.cont unwind label %inner
 
 shared.cont:
   unreachable
 
 inner:
-  ; CHECK: %x1 = phi i32 [ %x.for.left, %left ], [ %x, %right ]
-  ; CHECK: call void @h(i32 %x1)
   %i = cleanuppad []
   call void @h(i32 %x)
   unreachable
 
+; CHECK [[INNER_RIGHT:inner.*]]:
+  ; CHECK: call void @h(i32 %x)
+
+; CHECK [[INNER_LEFT:inner.*]]:
+  ; CHECK: call void @h(i32 %x.for.left)
+
 exit:
   unreachable
 }
 
 ; CHECK-LABEL: @test3(
 define void @test3() personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   invoke void @f()