Fix SEH state numbering algorithm to handle cleanupendpads
[oota-llvm.git] / lib / CodeGen / WinEHPrepare.cpp
index 68384f08b7c43991b2bc3e13093fe633376a9c1d..bbf61a14bf19b6a6304285d9bc2108ecb3d9f1fa 100644 (file)
@@ -130,8 +130,9 @@ private:
                           DenseMap<BasicBlock *, Value *> &Loads, Function &F);
   void demoteNonlocalUses(Value *V, std::set<BasicBlock *> &ColorsForBB,
                           Function &F);
-  bool prepareExplicitEH(Function &F);
-  void numberFunclet(BasicBlock *InitialBB, BasicBlock *FuncletBB);
+  bool prepareExplicitEH(Function &F,
+                         SmallVectorImpl<BasicBlock *> &EntryBlocks);
+  void colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks);
 
   Triple TheTriple;
 
@@ -175,6 +176,7 @@ private:
 
   std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
+  std::map<BasicBlock *, std::set<BasicBlock *>> FuncletChildren;
 };
 
 class WinEHFrameVariableMaterializer : public ValueMaterializer {
@@ -392,20 +394,25 @@ bool WinEHPrepare::runOnFunction(Function &Fn) {
 
   SmallVector<LandingPadInst *, 4> LPads;
   SmallVector<ResumeInst *, 4> Resumes;
+  SmallVector<BasicBlock *, 4> EntryBlocks;
   bool ForExplicitEH = false;
   for (BasicBlock &BB : Fn) {
-    if (auto *LP = BB.getLandingPadInst()) {
+    Instruction *First = BB.getFirstNonPHI();
+    if (auto *LP = dyn_cast<LandingPadInst>(First)) {
       LPads.push_back(LP);
-    } else if (BB.getFirstNonPHI()->isEHPad()) {
+    } else if (First->isEHPad()) {
+      if (!ForExplicitEH)
+        EntryBlocks.push_back(&Fn.getEntryBlock());
+      if (!isa<CatchEndPadInst>(First) && !isa<CleanupEndPadInst>(First))
+        EntryBlocks.push_back(&BB);
       ForExplicitEH = true;
-      break;
     }
     if (auto *Resume = dyn_cast<ResumeInst>(BB.getTerminator()))
       Resumes.push_back(Resume);
   }
 
   if (ForExplicitEH)
-    return prepareExplicitEH(Fn);
+    return prepareExplicitEH(Fn, EntryBlocks);
 
   // No need to prepare functions that lack landing pads.
   if (LPads.empty())
@@ -2608,7 +2615,7 @@ static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
       HT.TypeDescriptor =
           cast<GlobalVariable>(CS->getAggregateElement(1)->stripPointerCasts());
     }
-    HT.Handler = CPI->getParent();
+    HT.Handler = CPI->getNormalDest();
     // FIXME: Pass CPI->getArgOperand(1).
     HT.CatchObjRecoverIdx = -1;
     TBME.HandlerArray.push_back(HT);
@@ -2637,7 +2644,8 @@ void WinEHNumbering::createTryBlockMapEntry(int TryLow, int TryHigh,
       continue;
     int N;
     for (N = 0; N < NumHandlers; ++N) {
-      if (Entry.HandlerArray[N].Handler != Handlers[N]->getHandlerBlockOrFunc())
+      if (Entry.HandlerArray[N].Handler.get<const Value *>() !=
+          Handlers[N]->getHandlerBlockOrFunc())
         break; // breaks out of inner loop
     }
     // If all the handlers match, this is what we were looking for.
@@ -2940,29 +2948,59 @@ void WinEHNumbering::findActionRootLPads(const Function &F) {
   }
 }
 
-static const BasicBlock *getSingleCatchPadPredecessor(const BasicBlock &BB) {
-  for (const BasicBlock *PredBlock : predecessors(&BB))
-    if (isa<CatchPadInst>(PredBlock->getFirstNonPHI()))
-      return PredBlock;
+static const CatchPadInst *getSingleCatchPadPredecessor(const BasicBlock *BB) {
+  for (const BasicBlock *PredBlock : predecessors(BB))
+    if (auto *CPI = dyn_cast<CatchPadInst>(PredBlock->getFirstNonPHI()))
+      return CPI;
   return nullptr;
 }
 
+/// Find all the catchpads that feed directly into the catchendpad. Frontends
+/// using this personality should ensure that each catchendpad and catchpad has
+/// one or zero catchpad predecessors.
+///
+/// The following C++ generates the IR after it:
+///   try {
+///   } catch (A) {
+///   } catch (B) {
+///   }
+///
+/// IR:
+///   %catchpad.A
+///     catchpad [i8* A typeinfo]
+///         to label %catch.A unwind label %catchpad.B
+///   %catchpad.B
+///     catchpad [i8* B typeinfo]
+///         to label %catch.B unwind label %endcatches
+///   %endcatches
+///     catchendblock unwind to caller
+void findCatchPadsForCatchEndPad(
+    const BasicBlock *CatchEndBB,
+    SmallVectorImpl<const CatchPadInst *> &Handlers) {
+  const CatchPadInst *CPI = getSingleCatchPadPredecessor(CatchEndBB);
+  while (CPI) {
+    Handlers.push_back(CPI);
+    CPI = getSingleCatchPadPredecessor(CPI->getParent());
+  }
+  // We've pushed these back into reverse source order.  Reverse them to get
+  // the list back into source order.
+  std::reverse(Handlers.begin(), Handlers.end());
+}
+
 // Given BB which ends in an unwind edge, return the EHPad that this BB belongs
 // to. If the unwind edge came from an invoke, return null.
 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB) {
   const TerminatorInst *TI = BB->getTerminator();
   if (isa<InvokeInst>(TI))
     return nullptr;
-  if (isa<CatchPadInst>(TI) || isa<CatchEndPadInst>(TI) ||
-      isa<TerminatePadInst>(TI))
+  if (TI->isEHPad())
     return BB;
-  return cast<CleanupPadInst>(cast<CleanupReturnInst>(TI)->getReturnValue())
-      ->getParent();
+  return cast<CleanupReturnInst>(TI)->getCleanupPad()->getParent();
 }
 
-static void calculateExplicitStateNumbers(WinEHFuncInfo &FuncInfo,
-                                          const BasicBlock &BB,
-                                          int ParentState) {
+static void calculateExplicitCXXStateNumbers(WinEHFuncInfo &FuncInfo,
+                                             const BasicBlock &BB,
+                                             int ParentState) {
   assert(BB.isEHPad());
   const Instruction *FirstNonPHI = BB.getFirstNonPHI();
   // All catchpad instructions will be handled when we process their
@@ -2971,36 +3009,30 @@ static void calculateExplicitStateNumbers(WinEHFuncInfo &FuncInfo,
     return;
 
   if (isa<CatchEndPadInst>(FirstNonPHI)) {
-    const BasicBlock *TryPad = &BB;
-    const BasicBlock *LastTryPad = nullptr;
     SmallVector<const CatchPadInst *, 2> Handlers;
-    do {
-      LastTryPad = TryPad;
-      TryPad = getSingleCatchPadPredecessor(*TryPad);
-      if (TryPad)
-        Handlers.push_back(cast<CatchPadInst>(TryPad->getFirstNonPHI()));
-    } while (TryPad);
-    // We've pushed these back into reverse source order.  Reverse them to get
-    // the list back into source order.
-    std::reverse(Handlers.begin(), Handlers.end());
+    findCatchPadsForCatchEndPad(&BB, Handlers);
+    const BasicBlock *FirstTryPad = Handlers.front()->getParent();
     int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
     FuncInfo.EHPadStateMap[Handlers.front()] = TryLow;
-    for (const BasicBlock *PredBlock : predecessors(LastTryPad))
+    for (const BasicBlock *PredBlock : predecessors(FirstTryPad))
       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
-        calculateExplicitStateNumbers(FuncInfo, *PredBlock, TryLow);
+        calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, TryLow);
     int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
+
+    // catchpads are separate funclets in C++ EH due to the way rethrow works.
+    // In SEH, they aren't, so no invokes will unwind to the catchendpad.
     FuncInfo.EHPadStateMap[FirstNonPHI] = CatchLow;
     int TryHigh = CatchLow - 1;
     for (const BasicBlock *PredBlock : predecessors(&BB))
       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
-        calculateExplicitStateNumbers(FuncInfo, *PredBlock, CatchLow);
+        calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, CatchLow);
     int CatchHigh = FuncInfo.getLastStateNumber();
     addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
-    DEBUG(dbgs() << "TryLow[" << LastTryPad->getName() << "]: " << TryLow
+    DEBUG(dbgs() << "TryLow[" << FirstTryPad->getName() << "]: " << TryLow
                  << '\n');
-    DEBUG(dbgs() << "TryHigh[" << LastTryPad->getName() << "]: " << TryHigh
+    DEBUG(dbgs() << "TryHigh[" << FirstTryPad->getName() << "]: " << TryHigh
                  << '\n');
-    DEBUG(dbgs() << "CatchHigh[" << LastTryPad->getName() << "]: " << CatchHigh
+    DEBUG(dbgs() << "CatchHigh[" << FirstTryPad->getName() << "]: " << CatchHigh
                  << '\n');
   } else if (isa<CleanupPadInst>(FirstNonPHI)) {
     int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, &BB);
@@ -3009,7 +3041,7 @@ static void calculateExplicitStateNumbers(WinEHFuncInfo &FuncInfo,
                  << BB.getName() << '\n');
     for (const BasicBlock *PredBlock : predecessors(&BB))
       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
-        calculateExplicitStateNumbers(FuncInfo, *PredBlock, CleanupState);
+        calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, CleanupState);
   } else if (isa<TerminatePadInst>(FirstNonPHI)) {
     report_fatal_error("Not yet implemented!");
   } else {
@@ -3017,6 +3049,111 @@ static void calculateExplicitStateNumbers(WinEHFuncInfo &FuncInfo,
   }
 }
 
+static int addSEHHandler(WinEHFuncInfo &FuncInfo, int ParentState,
+                         const Function *Filter, const BasicBlock *Handler) {
+  SEHUnwindMapEntry Entry;
+  Entry.ToState = ParentState;
+  Entry.Filter = Filter;
+  Entry.Handler = Handler;
+  FuncInfo.SEHUnwindMap.push_back(Entry);
+  return FuncInfo.SEHUnwindMap.size() - 1;
+}
+
+static void calculateExplicitSEHStateNumbers(WinEHFuncInfo &FuncInfo,
+                                             const BasicBlock &BB,
+                                             int ParentState) {
+  assert(BB.isEHPad());
+  const Instruction *FirstNonPHI = BB.getFirstNonPHI();
+  // All catchpad instructions will be handled when we process their
+  // respective catchendpad instruction.
+  if (isa<CatchPadInst>(FirstNonPHI))
+    return;
+
+  if (isa<CatchEndPadInst>(FirstNonPHI)) {
+    // Extract the filter function and the __except basic block and create a
+    // state for them.
+    SmallVector<const CatchPadInst *, 1> Handlers;
+    findCatchPadsForCatchEndPad(&BB, Handlers);
+    assert(Handlers.size() == 1 &&
+           "SEH doesn't have multiple handlers per __try");
+    const CatchPadInst *CPI = Handlers.front();
+    const BasicBlock *CatchPadBB = CPI->getParent();
+    const Function *Filter =
+        cast<Function>(CPI->getArgOperand(0)->stripPointerCasts());
+    int TryState =
+        addSEHHandler(FuncInfo, ParentState, Filter, CPI->getNormalDest());
+
+    // Everything in the __try block uses TryState as its parent state.
+    FuncInfo.EHPadStateMap[CPI] = TryState;
+    DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
+                 << CatchPadBB->getName() << '\n');
+    for (const BasicBlock *PredBlock : predecessors(CatchPadBB))
+      if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
+        calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, TryState);
+
+    // Everything in the __except block unwinds to ParentState, just like code
+    // outside the __try.
+    FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
+    DEBUG(dbgs() << "Assigning state #" << ParentState << " to BB "
+                 << BB.getName() << '\n');
+    for (const BasicBlock *PredBlock : predecessors(&BB))
+      if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
+        calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, ParentState);
+  } else if (isa<CleanupPadInst>(FirstNonPHI)) {
+    int CleanupState =
+        addSEHHandler(FuncInfo, ParentState, /*Filter=*/nullptr, &BB);
+    FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState;
+    DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
+                 << BB.getName() << '\n');
+    for (const BasicBlock *PredBlock : predecessors(&BB))
+      if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
+        calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, CleanupState);
+  } else if (isa<CleanupEndPadInst>(FirstNonPHI)) {
+    // Anything unwinding through CleanupEndPadInst is in ParentState.
+    FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
+    DEBUG(dbgs() << "Assigning state #" << ParentState << " to BB "
+                 << BB.getName() << '\n');
+    for (const BasicBlock *PredBlock : predecessors(&BB))
+      if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
+        calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, ParentState);
+  } else if (isa<TerminatePadInst>(FirstNonPHI)) {
+    report_fatal_error("Not yet implemented!");
+  } else {
+    llvm_unreachable("unexpected EH Pad!");
+  }
+}
+
+/// Check if the EH Pad unwinds to caller.  Cleanups are a little bit of a
+/// special case because we have to look at the cleanupret instruction that uses
+/// the cleanuppad.
+static bool doesEHPadUnwindToCaller(const Instruction *EHPad) {
+  auto *CPI = dyn_cast<CleanupPadInst>(EHPad);
+  if (!CPI)
+    return EHPad->mayThrow();
+
+  // This cleanup does not return or unwind, so we say it unwinds to caller.
+  if (CPI->use_empty())
+    return true;
+
+  const Instruction *User = CPI->user_back();
+  if (auto *CRI = dyn_cast<CleanupReturnInst>(User))
+    return CRI->unwindsToCaller();
+  return cast<CleanupEndPadInst>(User)->unwindsToCaller();
+}
+
+void llvm::calculateSEHStateNumbers(const Function *ParentFn,
+                                    WinEHFuncInfo &FuncInfo) {
+  // Don't compute state numbers twice.
+  if (!FuncInfo.SEHUnwindMap.empty())
+    return;
+
+  for (const BasicBlock &BB : *ParentFn) {
+    if (!BB.isEHPad() || !doesEHPadUnwindToCaller(BB.getFirstNonPHI()))
+      continue;
+    calculateExplicitSEHStateNumbers(FuncInfo, BB, -1);
+  }
+}
+
 void llvm::calculateWinCXXEHStateNumbers(const Function *ParentFn,
                                          WinEHFuncInfo &FuncInfo) {
   // Return if it's already been done.
@@ -3027,23 +3164,13 @@ void llvm::calculateWinCXXEHStateNumbers(const Function *ParentFn,
   for (const BasicBlock &BB : *ParentFn) {
     if (!BB.isEHPad())
       continue;
-    // Check if the EH Pad has no exceptional successors (i.e. it unwinds to
-    // caller).  Cleanups are a little bit of a special case because their
-    // control flow cannot be determined by looking at the pad but instead by
-    // the pad's users.
-    bool HasNoSuccessors = false;
     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
-    if (FirstNonPHI->mayThrow()) {
-      HasNoSuccessors = true;
-    } else if (auto *CPI = dyn_cast<CleanupPadInst>(FirstNonPHI)) {
-      HasNoSuccessors =
-          CPI->use_empty() ||
-          cast<CleanupReturnInst>(CPI->user_back())->unwindsToCaller();
-    }
-
-    if (!HasNoSuccessors)
+    // Skip cleanupendpads; they are exits, not entries.
+    if (isa<CleanupEndPadInst>(FirstNonPHI))
+      continue;
+    if (!doesEHPadUnwindToCaller(FirstNonPHI))
       continue;
-    calculateExplicitStateNumbers(FuncInfo, BB, -1);
+    calculateExplicitCXXStateNumbers(FuncInfo, BB, -1);
     IsExplicit = true;
   }
 
@@ -3063,72 +3190,113 @@ void llvm::calculateWinCXXEHStateNumbers(const Function *ParentFn,
     Num.processCallSite(None, ImmutableCallSite());
 }
 
-void WinEHPrepare::numberFunclet(BasicBlock *InitialBB, BasicBlock *FuncletBB) {
-  Instruction *FirstNonPHI = FuncletBB->getFirstNonPHI();
-  bool IsCatch = isa<CatchPadInst>(FirstNonPHI);
-  bool IsCleanup = isa<CleanupPadInst>(FirstNonPHI);
+void WinEHPrepare::colorFunclets(Function &F,
+                                 SmallVectorImpl<BasicBlock *> &EntryBlocks) {
+  SmallVector<std::pair<BasicBlock *, BasicBlock *>, 16> Worklist;
+  BasicBlock *EntryBlock = &F.getEntryBlock();
 
-  // Initialize the worklist with the funclet's entry point.
-  std::vector<BasicBlock *> Worklist;
-  Worklist.push_back(InitialBB);
+  // 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.
+
+  Worklist.push_back({EntryBlock, EntryBlock});
 
   while (!Worklist.empty()) {
-    BasicBlock *BB = Worklist.back();
-    Worklist.pop_back();
-
-    // There can be only one "pad" basic block in the funclet: the initial one.
-    if (BB != FuncletBB && BB->isEHPad())
-      continue;
-
-    // Add 'FuncletBB' as a possible color for 'BB'.
-    if (BlockColors[BB].insert(FuncletBB).second == false) {
-      // Skip basic blocks which we have already visited.
-      continue;
+    BasicBlock *Visiting;
+    BasicBlock *Color;
+    std::tie(Visiting, Color) = Worklist.pop_back_val();
+    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 with the parent color.
+      for (User *Exit : VisitingHead->users()) {
+        for (BasicBlock *Succ :
+             successors(cast<Instruction>(Exit)->getParent())) {
+          if (BlockColors[Succ].insert(Color).second) {
+            Worklist.push_back({Succ, Color});
+          }
+        }
+      }
+      // Handle CatchPad specially since its successors need different colors.
+      if (CatchPadInst *CatchPad = dyn_cast<CatchPadInst>(VisitingHead)) {
+        // Visit the normal successor with the color of the new EH pad, and
+        // visit the unwind successor with the color of the parent.
+        BasicBlock *NormalSucc = CatchPad->getNormalDest();
+        if (BlockColors[NormalSucc].insert(Visiting).second) {
+          Worklist.push_back({NormalSucc, Visiting});
+        }
+        BasicBlock *UnwindSucc = CatchPad->getUnwindDest();
+        if (BlockColors[UnwindSucc].insert(Color).second) {
+          Worklist.push_back({UnwindSucc, Color});
+        }
+        continue;
+      }
+      // Switch color to the current node, except for terminate pads which
+      // have no bodies and only unwind successors and so need their successors
+      // visited with the color of the parent.
+      if (!isa<TerminatePadInst>(VisitingHead))
+        Color = Visiting;
+    } else {
+      // Note that this is a member of the given color.
+      FuncletBlocks[Color].insert(Visiting);
     }
 
-    FuncletBlocks[FuncletBB].insert(BB);
-
-    Instruction *Terminator = BB->getTerminator();
-    // The catchret's successors cannot be part of the funclet.
-    if (IsCatch && isa<CatchReturnInst>(Terminator))
-      continue;
-    // The cleanupret's successors cannot be part of the funclet.
-    if (IsCleanup && isa<CleanupReturnInst>(Terminator))
+    TerminatorInst *Terminator = Visiting->getTerminator();
+    if (isa<CleanupReturnInst>(Terminator) ||
+        isa<CatchReturnInst>(Terminator) ||
+        isa<CleanupEndPadInst>(Terminator)) {
+      // These blocks' successors have already been queued with the parent
+      // color.
       continue;
+    }
+    for (BasicBlock *Succ : successors(Visiting)) {
+      if (isa<CatchEndPadInst>(Succ->getFirstNonPHI())) {
+        // The catchendpad needs to be visited with the parent's color, not
+        // the current color.  This will happen in the code above that visits
+        // any catchpad unwind successor with the parent color, so we can
+        // safely skip this successor here.
+        continue;
+      }
+      if (BlockColors[Succ].insert(Color).second) {
+        Worklist.push_back({Succ, Color});
+      }
+    }
+  }
 
-    Worklist.insert(Worklist.end(), succ_begin(BB), succ_end(BB));
+  // The processing above actually accumulated the parent set for this
+  // funclet into the color set for its entry; use the parent set to
+  // populate the children map, and reset the color set to include just
+  // the funclet itself (no instruction can target a funclet entry except on
+  // that transitions to the child funclet).
+  for (BasicBlock *FuncletEntry : EntryBlocks) {
+    std::set<BasicBlock *> &ColorMapItem = BlockColors[FuncletEntry];
+    for (BasicBlock *Parent : ColorMapItem)
+      FuncletChildren[Parent].insert(FuncletEntry);
+    ColorMapItem.clear();
+    ColorMapItem.insert(FuncletEntry);
   }
 }
 
-bool WinEHPrepare::prepareExplicitEH(Function &F) {
+bool WinEHPrepare::prepareExplicitEH(
+    Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
   // Remove unreachable blocks.  It is not valuable to assign them a color and
   // their existence can trick us into thinking values are alive when they are
   // not.
   removeUnreachableBlocks(F);
 
-  BasicBlock *EntryBlock = &F.getEntryBlock();
-
-  // Number everything starting from the entry block.
-  numberFunclet(EntryBlock, EntryBlock);
-
-  for (BasicBlock &BB : F) {
-    // Remove single entry PHIs to simplify preparation.
-    if (auto *PN = dyn_cast<PHINode>(BB.begin()))
-      if (PN->getNumIncomingValues() == 1)
-        FoldSingleEntryPHINodes(&BB);
-
-    // EH pad instructions are always the first non-PHI nodes in a block if they
-    // are at all present.
-    Instruction *I = BB.getFirstNonPHI();
-    if (I->isEHPad())
-      numberFunclet(&BB, &BB);
-
-    // It is possible for a normal basic block to only be reachable via an
-    // exceptional basic block.  The successor of a catchret is the only case
-    // where this is possible.
-    if (auto *CRI = dyn_cast<CatchReturnInst>(BB.getTerminator()))
-      numberFunclet(CRI->getSuccessor(), EntryBlock);
-  }
+  // Determine which blocks are reachable from which funclet entries.
+  colorFunclets(F, EntryBlocks);
 
   // Strip PHI nodes off of EH pads.
   SmallVector<PHINode *, 16> PHINodes;
@@ -3179,9 +3347,8 @@ bool WinEHPrepare::prepareExplicitEH(Function &F) {
   // We need to clone all blocks which belong to multiple funclets.  Values are
   // remapped throughout the funclet to propogate both the new instructions
   // *and* the new basic blocks themselves.
-  for (auto &Funclet : FuncletBlocks) {
-    BasicBlock *FuncletPadBB = Funclet.first;
-    std::set<BasicBlock *> &BlocksInFunclet = Funclet.second;
+  for (BasicBlock *FuncletPadBB : EntryBlocks) {
+    std::set<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletPadBB];
 
     std::map<BasicBlock *, BasicBlock *> Orig2Clone;
     ValueToValueMapTy VMap;
@@ -3192,12 +3359,12 @@ bool WinEHPrepare::prepareExplicitEH(Function &F) {
       if (NumColorsForBB == 1)
         continue;
 
-      assert(!isa<PHINode>(BB->front()) &&
-             "Polychromatic PHI nodes should have been demoted!");
-
       // Create a new basic block and copy instructions into it!
-      BasicBlock *CBB = CloneBasicBlock(
-          BB, VMap, Twine(".for.", FuncletPadBB->getName()), &F);
+      BasicBlock *CBB =
+          CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
+      // Insert the clone immediately after the original to ensure determinism
+      // and to keep the same relative ordering of any funclet's blocks.
+      CBB->insertInto(&F, BB->getNextNode());
 
       // Add basic block mapping.
       VMap[BB] = CBB;
@@ -3242,12 +3409,17 @@ bool WinEHPrepare::prepareExplicitEH(Function &F) {
       // The token consumed by a CatchReturnInst must match the funclet token.
       bool IsUnreachableCatchret = false;
       if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
-        IsUnreachableCatchret = CRI->getReturnValue() != CatchPad;
-      // The token consumed by a CleanupPadInst must match the funclet token.
+        IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
+      // The token consumed by a CleanupReturnInst must match the funclet token.
       bool IsUnreachableCleanupret = false;
       if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
-        IsUnreachableCleanupret = CRI->getReturnValue() != CleanupPad;
-      if (IsUnreachableRet || IsUnreachableCatchret || IsUnreachableCleanupret) {
+        IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
+      // The token consumed by a CleanupEndPadInst must match the funclet token.
+      bool IsUnreachableCleanupendpad = false;
+      if (auto *CEPI = dyn_cast<CleanupEndPadInst>(TI))
+        IsUnreachableCleanupendpad = CEPI->getCleanupPad() != CleanupPad;
+      if (IsUnreachableRet || IsUnreachableCatchret ||
+          IsUnreachableCleanupret || IsUnreachableCleanupendpad) {
         new UnreachableInst(BB->getContext(), TI);
         TI->eraseFromParent();
       }
@@ -3283,6 +3455,7 @@ bool WinEHPrepare::prepareExplicitEH(Function &F) {
 
   BlockColors.clear();
   FuncletBlocks.clear();
+  FuncletChildren.clear();
 
   return true;
 }
@@ -3395,12 +3568,11 @@ void WinEHPrepare::demoteNonlocalUses(Value *V,
     auto *UsingInst = cast<Instruction>(U.getUser());
     BasicBlock *UsingBB = UsingInst->getParent();
 
-    // Is the Use inside a block which is colored with a subset of the Def?
+    // Is the Use inside a block which is colored the same as the Def?
     // If so, we don't need to escape the Def because we will clone
     // ourselves our own private copy.
     std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[UsingBB];
-    if (std::includes(ColorsForBB.begin(), ColorsForBB.end(),
-                      ColorsForUsingBB.begin(), ColorsForUsingBB.end()))
+    if (ColorsForUsingBB == ColorsForBB)
       continue;
 
     replaceUseWithLoad(V, U, SpillSlot, Loads, F);