[SplitEdge] Update SplitCriticalEdge to return a nullptr only when the edge is not critical

[sidbav]

Summary

The function SplitCriticalEdge (called by SplitEdge) can return a nullptr in cases where the edge is a critical. SplitEdge uses SplitCriticalEdge assuming it can always split all critical edges, which is an incorrect assumption.

The three cases where the function SplitCriticalEdge will return a nullptr is:

1. DestBB is an exception block
2. Options.IgnoreUnreachableDests is set to true and isa(DestBB->getFirstNonPHIOrDbgOrLifetime()) is not equal to a nullptr
3. LoopSimplify form must be preserved (Options.PreserveLoopSimplify is true) and it cannot be maintained for a loop due to indirect branches

For each of these situations they are handled in the following way:

1. Modified the function ehAwareSplitEdge originally from llvm/lib/Transforms/Coroutines/CoroFrame.cpp to handle the cases when the DestBB is an exception block. This function is called directly in SplitEdge. SplitEdge does not call SplitCriticalEdge in this case
2. Options.IgnoreUnreachableDests is set to false by default, so this situation does not apply.
3. Return a nullptr in this situation since the SplitCriticalEdge also returned nullptr. Nothing we can do in this case.

[sidbav]

Ping!

[sidbav]

Ping

[sidbav]

Ping

[sidbav]

ping

[sidbav]

Ping

[asbirlea]

I'd have liked the thoughts of folks familiar with coroutines here, but overall the change looks like an improvement.

[sidbav]

Ping!

[sidbav]

I am going to commit this change since no one else seems to be reviewing it... will welcome any post commit reviews.

[lebedev.ri]

Could use an IR test. Is only CoroFrame.cpp affected?
I'd recommend to split this up into NFC refactoring patch, and the actual functionality change.

[sidbav]

In D94619#2672518, @lebedev.ri wrote:

Could use an IR test. Is only CoroFrame.cpp affected?

Decided to use a unit test for this patch since I modified the functionality of SplitCriticalEdge and SplitEdge, and these functions are tested with unit tests. Used a unit test to be consistent.
CoroFrame.cpp, and BasicBlockUtils and BreakCriticalEdges are modified as well.

[lebedev.ri]

In D94619#2672562, @sidbav wrote:

In D94619#2672518, @lebedev.ri wrote:

Could use an IR test. Is only CoroFrame.cpp affected?

Decided to use a unit test for this patch since I modified the functionality of SplitCriticalEdge and SplitEdge, and these functions are tested with unit tests. Used a unit test to be consistent.
CoroFrame.cpp, and BasicBlockUtils and BreakCriticalEdges are modified as well.

This doesn't really answer my question, sorry.
Which transformation passes benefit from this change?
Can there not be a lit test for that for them?

[sidbav]

In D94619#2673338, @lebedev.ri wrote:

In D94619#2672562, @sidbav wrote:

In D94619#2672518, @lebedev.ri wrote:

Could use an IR test. Is only CoroFrame.cpp affected?

Decided to use a unit test for this patch since I modified the functionality of SplitCriticalEdge and SplitEdge, and these functions are tested with unit tests. Used a unit test to be consistent.
CoroFrame.cpp, and BasicBlockUtils and BreakCriticalEdges are modified as well.

This doesn't really answer my question, sorry.
Which transformation passes benefit from this change?
Can there not be a lit test for that for them?

Oh, I thought you were asking which files were changed!

CoroFrame.cpp is not really affected as this is more of a NFC for CoroFrame.
However, quite a few other transformations that make use of SplitCriticalEdge and/or SplitEdge. I can create a lit test for those transformations.

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

struct CriticalEdgeSplittingOptions {
   }
 
   CriticalEdgeSplittingOptions &unsetPreserveLoopSimplify() {
     PreserveLoopSimplify = false;
     return *this;
   }
 };
 
+/// When a loop exit edge is split, LCSSA form may require new PHIs in the new
+/// exit block. This function inserts the new PHIs, as needed. Preds is a list
+/// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is
+/// the old loop exit, now the successor of SplitBB.
+void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds,
+                                BasicBlock *SplitBB, BasicBlock *DestBB);
+
 /// If this edge is a critical edge, insert a new node to split the critical
 /// edge. This will update the analyses passed in through the option struct.
 /// This returns the new block if the edge was split, null otherwise.
 ///
 /// If MergeIdenticalEdges in the options struct is true (not the default),
 /// *all* edges from TI to the specified successor will be merged into the same
 /// critical edge block. This is most commonly interesting with switch
 /// instructions, which may have many edges to any one destination.  This
 /// ensures that all edges to that dest go to one block instead of each going
 /// to a different block, but isn't the standard definition of a "critical
 /// edge".
 ///
 /// It is invalid to call this function on a critical edge that starts at an
 /// IndirectBrInst.  Splitting these edges will almost always create an invalid
 /// program because the address of the new block won't be the one that is jumped
 /// to.
 BasicBlock *SplitCriticalEdge(Instruction *TI, unsigned SuccNum,
                               const CriticalEdgeSplittingOptions &Options =
                                   CriticalEdgeSplittingOptions(),
                               const Twine &BBName = "");
 
+/// If it is known that an edge is critical, SplitKnownCriticalEdge can be
+/// called directly, rather than calling SplitCriticalEdge first.
+BasicBlock *SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum,
+                                   const CriticalEdgeSplittingOptions &Options =
+                                       CriticalEdgeSplittingOptions(),
+                                   const Twine &BBName = "");
+
 inline BasicBlock *
 SplitCriticalEdge(BasicBlock *BB, succ_iterator SI,
                   const CriticalEdgeSplittingOptions &Options =
                       CriticalEdgeSplittingOptions()) {
   return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(),
                            Options);
 }
 

 
 /// Split the edge connecting the specified blocks, and return the newly created
 /// basic block between \p From and \p To.
 BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To,
                       DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
                       MemorySSAUpdater *MSSAU = nullptr,
                       const Twine &BBName = "");
 
+/// Sets the unwind edge of an instruction to a particular successor.
+void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ);
+
+/// Replaces all uses of OldPred with the NewPred block in all PHINodes in a
+/// block.
+void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred,
+                    BasicBlock *NewPred, PHINode *Until = nullptr);
+
+/// Split the edge connect the specficed blocks in the case that \p Succ is an
+/// Exception Handling Block
+BasicBlock *ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ,
+                             LandingPadInst *OriginalPad = nullptr,
+                             PHINode *LandingPadReplacement = nullptr,
+                             const CriticalEdgeSplittingOptions &Options =
+                                 CriticalEdgeSplittingOptions(),
+                             const Twine &BBName = "");
+
 /// Split the specified block at the specified instruction.
 ///
 /// If \p Before is true, splitBlockBefore handles the block
 /// splitting. Otherwise, execution proceeds as described below.
 ///
 /// Everything before \p SplitPt stays in \p Old and everything starting with \p
 /// SplitPt moves to a new block. The two blocks are joined by an unconditional
 /// branch. The new block with name \p BBName is returned.

llvm/lib/Transforms/Coroutines/CoroFrame.cpp

for (const auto &Alias : A.Aliases) {
           Builder.CreateBitCast(AliasPtr, Alias.first->getType());
       Alias.first->replaceUsesWithIf(
           AliasPtrTyped, [&](Use &U) { return DT.dominates(CB, U); });
     }
   }
   return FramePtr;
 }
 
-// Sets the unwind edge of an instruction to a particular successor.
-static void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ) {
-  if (auto *II = dyn_cast<InvokeInst>(TI))
-    II->setUnwindDest(Succ);
-  else if (auto *CS = dyn_cast<CatchSwitchInst>(TI))
-    CS->setUnwindDest(Succ);
-  else if (auto *CR = dyn_cast<CleanupReturnInst>(TI))
-    CR->setUnwindDest(Succ);
-  else
-    llvm_unreachable("unexpected terminator instruction");
-}
-
-// Replaces all uses of OldPred with the NewPred block in all PHINodes in a
-// block.
-static void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred,
-                           BasicBlock *NewPred, PHINode *Until = nullptr) {
-  unsigned BBIdx = 0;
-  for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
-    PHINode *PN = cast<PHINode>(I);
-
-    // We manually update the LandingPadReplacement PHINode and it is the last
-    // PHI Node. So, if we find it, we are done.
-    if (Until == PN)
-      break;
-
-    // Reuse the previous value of BBIdx if it lines up.  In cases where we
-    // have multiple phi nodes with *lots* of predecessors, this is a speed
-    // win because we don't have to scan the PHI looking for TIBB.  This
-    // happens because the BB list of PHI nodes are usually in the same
-    // order.
-    if (PN->getIncomingBlock(BBIdx) != OldPred)
-      BBIdx = PN->getBasicBlockIndex(OldPred);
-
-    assert(BBIdx != (unsigned)-1 && "Invalid PHI Index!");
-    PN->setIncomingBlock(BBIdx, NewPred);
-  }
-}
-
-// Uses SplitEdge unless the successor block is an EHPad, in which case do EH
-// specific handling.
-static BasicBlock *ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ,
-                                    LandingPadInst *OriginalPad,
-                                    PHINode *LandingPadReplacement) {
-  auto *PadInst = Succ->getFirstNonPHI();
-  if (!LandingPadReplacement && !PadInst->isEHPad())
-    return SplitEdge(BB, Succ);
-
-  auto *NewBB = BasicBlock::Create(BB->getContext(), "", BB->getParent(), Succ);
-  setUnwindEdgeTo(BB->getTerminator(), NewBB);
-  updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement);
-
-  if (LandingPadReplacement) {
-    auto *NewLP = OriginalPad->clone();
-    auto *Terminator = BranchInst::Create(Succ, NewBB);
-    NewLP->insertBefore(Terminator);
-    LandingPadReplacement->addIncoming(NewLP, NewBB);
-    return NewBB;
-  }
-  Value *ParentPad = nullptr;
-  if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
-    ParentPad = FuncletPad->getParentPad();
-  else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
-    ParentPad = CatchSwitch->getParentPad();
-  else
-    llvm_unreachable("handling for other EHPads not implemented yet");
-
-  auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, "", NewBB);
-  CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB);
-  return NewBB;
-}
-
 // Moves the values in the PHIs in SuccBB that correspong to PredBB into a new
 // PHI in InsertedBB.
 static void movePHIValuesToInsertedBlock(BasicBlock *SuccBB,
                                          BasicBlock *InsertedBB,
                                          BasicBlock *PredBB,
                                          PHINode *UntilPHI = nullptr) {
   auto *PN = cast<PHINode>(&SuccBB->front());
   do {

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
   ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
 }
 
 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT,
                             LoopInfo *LI, MemorySSAUpdater *MSSAU,
                             const Twine &BBName) {
   unsigned SuccNum = GetSuccessorNumber(BB, Succ);
 
-  // If this is a critical edge, let SplitCriticalEdge do it.
   Instruction *LatchTerm = BB->getTerminator();
-  if (SplitCriticalEdge(
-          LatchTerm, SuccNum,
-          CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA(),
-          BBName))
-    return LatchTerm->getSuccessor(SuccNum);
+
+  CriticalEdgeSplittingOptions Options =
+      CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA();
+
+  if ((isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges))) {
+    // If it is a critical edge, and the succesor is an exception block, handle
+    // the split edge logic in this specific function
+    if (Succ->isEHPad())
+      return ehAwareSplitEdge(BB, Succ, nullptr, nullptr, Options, BBName);
+
+    // If this is a critical edge, let SplitKnownCriticalEdge do it.
+    return SplitKnownCriticalEdge(LatchTerm, SuccNum, Options, BBName);
+  }
 
   // If the edge isn't critical, then BB has a single successor or Succ has a
   // single pred.  Split the block.
   if (BasicBlock *SP = Succ->getSinglePredecessor()) {
     // If the successor only has a single pred, split the top of the successor
     // block.
     assert(SP == BB && "CFG broken");
     SP = nullptr;
     return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU, BBName,
                       /*Before=*/true);
   }
 
   // Otherwise, if BB has a single successor, split it at the bottom of the
   // block.
   assert(BB->getTerminator()->getNumSuccessors() == 1 &&
          "Should have a single succ!");
   return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU, BBName);
 }
 
+void llvm::setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ) {
+  if (auto *II = dyn_cast<InvokeInst>(TI))
+    II->setUnwindDest(Succ);
+  else if (auto *CS = dyn_cast<CatchSwitchInst>(TI))
+    CS->setUnwindDest(Succ);
+  else if (auto *CR = dyn_cast<CleanupReturnInst>(TI))
+    CR->setUnwindDest(Succ);
+  else
+    llvm_unreachable("unexpected terminator instruction");
+}
+
+void llvm::updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred,
+                          BasicBlock *NewPred, PHINode *Until) {
+  int BBIdx = 0;
+  for (PHINode &PN : DestBB->phis()) {
+    // We manually update the LandingPadReplacement PHINode and it is the last
+    // PHI Node. So, if we find it, we are done.
+    if (Until == &PN)
+      break;
+
+    // Reuse the previous value of BBIdx if it lines up.  In cases where we
+    // have multiple phi nodes with *lots* of predecessors, this is a speed
+    // win because we don't have to scan the PHI looking for TIBB.  This
+    // happens because the BB list of PHI nodes are usually in the same
+    // order.
+    if (PN.getIncomingBlock(BBIdx) != OldPred)
+      BBIdx = PN.getBasicBlockIndex(OldPred);
+
+    assert(BBIdx != -1 && "Invalid PHI Index!");
+    PN.setIncomingBlock(BBIdx, NewPred);
+  }
+}
+
+BasicBlock *llvm::ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ,
+                                   LandingPadInst *OriginalPad,
+                                   PHINode *LandingPadReplacement,
+                                   const CriticalEdgeSplittingOptions &Options,
+                                   const Twine &BBName) {
+
+  auto *PadInst = Succ->getFirstNonPHI();
+  if (!LandingPadReplacement && !PadInst->isEHPad())
+    return SplitEdge(BB, Succ, Options.DT, Options.LI, Options.MSSAU, BBName);
+
+  auto *LI = Options.LI;
+  SmallVector<BasicBlock *, 4> LoopPreds;
+  // Check if extra modifications will be required to preserve loop-simplify
+  // form after splitting. If it would require splitting blocks with IndirectBr
+  // terminators, bail out if preserving loop-simplify form is requested.
+  if (Options.PreserveLoopSimplify && LI) {
+    if (Loop *BBLoop = LI->getLoopFor(BB)) {
+
+      // The only way that we can break LoopSimplify form by splitting a
+      // critical edge is when there exists some edge from BBLoop to Succ *and*
+      // the only edge into Succ from outside of BBLoop is that of NewBB after
+      // the split. If the first isn't true, then LoopSimplify still holds,
+      // NewBB is the new exit block and it has no non-loop predecessors. If the
+      // second isn't true, then Succ was not in LoopSimplify form prior to
+      // the split as it had a non-loop predecessor. In both of these cases,
+      // the predecessor must be directly in BBLoop, not in a subloop, or again
+      // LoopSimplify doesn't hold.
+      for (BasicBlock *P : predecessors(Succ)) {
+        if (P == BB)
+          continue; // The new block is known.
+        if (LI->getLoopFor(P) != BBLoop) {
+          // Loop is not in LoopSimplify form, no need to re simplify after
+          // splitting edge.
+          LoopPreds.clear();
+          break;
+        }
+        LoopPreds.push_back(P);
+      }
+      // Loop-simplify form can be preserved, if we can split all in-loop
+      // predecessors.
+      if (any_of(LoopPreds, [](BasicBlock *Pred) {
+            return isa<IndirectBrInst>(Pred->getTerminator());
+          })) {
+        return nullptr;
+      }
+    }
+  }
+
+  auto *NewBB =
+      BasicBlock::Create(BB->getContext(), BBName, BB->getParent(), Succ);
+  setUnwindEdgeTo(BB->getTerminator(), NewBB);
+  updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement);
+
+  if (LandingPadReplacement) {
+    auto *NewLP = OriginalPad->clone();
+    auto *Terminator = BranchInst::Create(Succ, NewBB);
+    NewLP->insertBefore(Terminator);
+    LandingPadReplacement->addIncoming(NewLP, NewBB);
+  } else {
+    Value *ParentPad = nullptr;
+    if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
+      ParentPad = FuncletPad->getParentPad();
+    else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
+      ParentPad = CatchSwitch->getParentPad();
+    else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst))
+      ParentPad = CleanupPad->getParentPad();
+    else if (auto *LandingPad = dyn_cast<LandingPadInst>(PadInst))
+      ParentPad = LandingPad->getParent();
+    else
+      llvm_unreachable("handling for other EHPads not implemented yet");
+
+    auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, BBName, NewBB);
+    CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB);
+  }
+
+  auto *DT = Options.DT;
+  auto *MSSAU = Options.MSSAU;
+  if (!DT && !LI)
+    return NewBB;
+
+  if (DT) {
+    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+    SmallVector<DominatorTree::UpdateType, 3> Updates;
+
+    Updates.push_back({DominatorTree::Insert, BB, NewBB});
+    Updates.push_back({DominatorTree::Insert, NewBB, Succ});
+    Updates.push_back({DominatorTree::Delete, BB, Succ});
+
+    DTU.applyUpdates(Updates);
+    DTU.flush();
+
+    if (MSSAU) {
+      MSSAU->applyUpdates(Updates, *DT);
+      if (VerifyMemorySSA)
+        MSSAU->getMemorySSA()->verifyMemorySSA();
+    }
+  }
+
+  if (LI) {
+    if (Loop *BBLoop = LI->getLoopFor(BB)) {
+      // If one or the other blocks were not in a loop, the new block is not
+      // either, and thus LI doesn't need to be updated.
+      if (Loop *SuccLoop = LI->getLoopFor(Succ)) {
+        if (BBLoop == SuccLoop) {
+          // Both in the same loop, the NewBB joins loop.
+          SuccLoop->addBasicBlockToLoop(NewBB, *LI);
+        } else if (BBLoop->contains(SuccLoop)) {
+          // Edge from an outer loop to an inner loop.  Add to the outer loop.
+          BBLoop->addBasicBlockToLoop(NewBB, *LI);
+        } else if (SuccLoop->contains(BBLoop)) {
+          // Edge from an inner loop to an outer loop.  Add to the outer loop.
+          SuccLoop->addBasicBlockToLoop(NewBB, *LI);
+        } else {
+          // Edge from two loops with no containment relation.  Because these
+          // are natural loops, we know that the destination block must be the
+          // header of its loop (adding a branch into a loop elsewhere would
+          // create an irreducible loop).
+          assert(SuccLoop->getHeader() == Succ &&
+                 "Should not create irreducible loops!");
+          if (Loop *P = SuccLoop->getParentLoop())
+            P->addBasicBlockToLoop(NewBB, *LI);
+        }
+      }
+
+      // If BB is in a loop and Succ is outside of that loop, we may need to
+      // update LoopSimplify form and LCSSA form.
+      if (!BBLoop->contains(Succ)) {
+        assert(!BBLoop->contains(NewBB) &&
+               "Split point for loop exit is contained in loop!");
+
+        // Update LCSSA form in the newly created exit block.
+        if (Options.PreserveLCSSA) {
+          createPHIsForSplitLoopExit(BB, NewBB, Succ);
+        }
+
+        if (!LoopPreds.empty()) {
+          BasicBlock *NewExitBB = SplitBlockPredecessors(
+              Succ, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
+          if (Options.PreserveLCSSA)
+            createPHIsForSplitLoopExit(LoopPreds, NewExitBB, Succ);
+        }
+      }
+    }
+  }
+
+  return NewBB;
+}
+
+void llvm::createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds,
+                                      BasicBlock *SplitBB, BasicBlock *DestBB) {
+  // SplitBB shouldn't have anything non-trivial in it yet.
+  assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
+          SplitBB->isLandingPad()) &&
+         "SplitBB has non-PHI nodes!");
+
+  // For each PHI in the destination block.
+  for (PHINode &PN : DestBB->phis()) {
+    int Idx = PN.getBasicBlockIndex(SplitBB);
+    assert(Idx >= 0 && "Invalid Block Index");
+    Value *V = PN.getIncomingValue(Idx);
+
+    // If the input is a PHI which already satisfies LCSSA, don't create
+    // a new one.
+    if (const PHINode *VP = dyn_cast<PHINode>(V))
+      if (VP->getParent() == SplitBB)
+        continue;
+
+    // Otherwise a new PHI is needed. Create one and populate it.
+    PHINode *NewPN = PHINode::Create(
+        PN.getType(), Preds.size(), "split",
+        SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator());
+    for (BasicBlock *BB : Preds)
+      NewPN->addIncoming(V, BB);
+
+    // Update the original PHI.
+    PN.setIncomingValue(Idx, NewPN);
+  }
+}
+
 unsigned
 llvm::SplitAllCriticalEdges(Function &F,
                             const CriticalEdgeSplittingOptions &Options) {
   unsigned NumBroken = 0;
   for (BasicBlock &BB : F) {
     Instruction *TI = BB.getTerminator();
     if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI) &&
         !isa<CallBrInst>(TI))

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp

PreservedAnalyses BreakCriticalEdgesPass::run(Function &F,
   PA.preserve<LoopAnalysis>();
   return PA;
 }
 
 //===----------------------------------------------------------------------===//
 //    Implementation of the external critical edge manipulation functions
 //===----------------------------------------------------------------------===//
 
-/// When a loop exit edge is split, LCSSA form may require new PHIs in the new
-/// exit block. This function inserts the new PHIs, as needed. Preds is a list
-/// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is
-/// the old loop exit, now the successor of SplitBB.
-static void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds,
-                                       BasicBlock *SplitBB,
-                                       BasicBlock *DestBB) {
-  // SplitBB shouldn't have anything non-trivial in it yet.
-  assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
-          SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!");
-
-  // For each PHI in the destination block.
-  for (PHINode &PN : DestBB->phis()) {
-    unsigned Idx = PN.getBasicBlockIndex(SplitBB);
-    Value *V = PN.getIncomingValue(Idx);
-
-    // If the input is a PHI which already satisfies LCSSA, don't create
-    // a new one.
-    if (const PHINode *VP = dyn_cast<PHINode>(V))
-      if (VP->getParent() == SplitBB)
-        continue;
-
-    // Otherwise a new PHI is needed. Create one and populate it.
-    PHINode *NewPN = PHINode::Create(
-        PN.getType(), Preds.size(), "split",
-        SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator());
-    for (unsigned i = 0, e = Preds.size(); i != e; ++i)
-      NewPN->addIncoming(V, Preds[i]);
-
-    // Update the original PHI.
-    PN.setIncomingValue(Idx, NewPN);
-  }
-}
-
 BasicBlock *llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum,
                                     const CriticalEdgeSplittingOptions &Options,
                                     const Twine &BBName) {
   if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges))
     return nullptr;
 
+  return SplitKnownCriticalEdge(TI, SuccNum, Options, BBName);
+}
+
+BasicBlock *
+llvm::SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum,
+                             const CriticalEdgeSplittingOptions &Options,
+                             const Twine &BBName) {
   assert(!isa<IndirectBrInst>(TI) &&
          "Cannot split critical edge from IndirectBrInst");
 
   BasicBlock *TIBB = TI->getParent();
   BasicBlock *DestBB = TI->getSuccessor(SuccNum);
 
   // Splitting the critical edge to a pad block is non-trivial. Don't do
   // it in this generic function.

llvm/unittests/Transforms/Utils/BasicBlockUtilsTest.cpp

 //===- BasicBlockUtils.cpp - Unit tests for BasicBlockUtils ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/Support/SourceMgr.h"
+#include "llvm/Transforms/Utils/BreakCriticalEdges.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
   SMDiagnostic Err;
   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
   if (!Mod)
TEST(BasicBlockUtils, SplitEdge_ex3) {
   for (BasicBlock &BB : *F) {
     if (BB.getName() == NewBB->getName()) {
       BBFlag = true;
     }
   }
   EXPECT_TRUE(BBFlag);
 }
 
+TEST(BasicBlockUtils, SplitEdge_ex4) {
+  LLVMContext C;
+  std::unique_ptr<Module> M = parseIR(
+      C, "define void @bar(i32 %cond) personality i8 0 {\n"
+         "entry:\n"
+         "  switch i32 %cond, label %exit [\n"
+         "    i32 -1, label %continue\n"
+         "    i32 0, label %continue\n"
+         "    i32 1, label %continue_alt\n"
+         "    i32 2, label %continue_alt\n"
+         "  ]\n"
+         "exit:\n"
+         "  ret void\n"
+         "continue:\n"
+         "  invoke void @sink() to label %normal unwind label %exception\n"
+         "continue_alt:\n"
+         "  invoke void @sink_alt() to label %normal unwind label %exception\n"
+         "exception:\n"
+         "  %cleanup = landingpad i8 cleanup\n"
+         "  br label %trivial-eh-handler\n"
+         "trivial-eh-handler:\n"
+         "  call void @sideeffect(i32 1)\n"
+         "  br label %normal\n"
+         "normal:\n"
+         "  call void @sideeffect(i32 0)\n"
+         "  ret void\n"
+         "}\n"
+         "\n"
+         "declare void @sideeffect(i32)\n"
+         "declare void @sink() cold\n"
+         "declare void @sink_alt() cold\n");
+
+  Function *F = M->getFunction("bar");
+
+  DominatorTree DT(*F);
+
+  LoopInfo LI(DT);
+
+  TargetLibraryInfoImpl TLII;
+  TargetLibraryInfo TLI(TLII);
+
+  AAResults AA(TLI);
+
+  MemorySSA MSSA(*F, &AA, &DT);
+  MemorySSAUpdater MSSAU(&MSSA);
+
+  BasicBlock *SrcBlock;
+  BasicBlock *DestBlock;
+
+  SrcBlock = getBasicBlockByName(*F, "continue");
+  DestBlock = getBasicBlockByName(*F, "exception");
+
+  unsigned SuccNum = GetSuccessorNumber(SrcBlock, DestBlock);
+  Instruction *LatchTerm = SrcBlock->getTerminator();
+
+  const CriticalEdgeSplittingOptions Options =
+      CriticalEdgeSplittingOptions(&DT, &LI, &MSSAU);
+
+  // Check that the following edge is both critical and the destination block is
+  // an exception block. These must be handled differently by SplitEdge
+  bool CriticalEdge =
+      isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges);
+  EXPECT_TRUE(CriticalEdge);
+
+  bool Ehpad = DestBlock->isEHPad();
+  EXPECT_TRUE(Ehpad);
+
+  BasicBlock *NewBB = SplitEdge(SrcBlock, DestBlock, &DT, &LI, &MSSAU, "");
+
+  MSSA.verifyMemorySSA();
+  EXPECT_TRUE(DT.verify());
+  EXPECT_NE(NewBB, nullptr);
+  EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
+  EXPECT_EQ(NewBB, SrcBlock->getTerminator()->getSuccessor(SuccNum));
+  EXPECT_EQ(NewBB->getParent(), F);
+
+  bool BBFlag = false;
+  for (BasicBlock &BB : *F) {
+    if (BB.getName() == NewBB->getName()) {
+      BBFlag = true;
+      break;
+    }
+  }
+  EXPECT_TRUE(BBFlag);
+}
+
 TEST(BasicBlockUtils, splitBasicBlockBefore_ex1) {
   LLVMContext C;
   std::unique_ptr<Module> M = parseIR(C, "define void @foo() {\n"
                                          "bb0:\n"
                                          " %0 = mul i32 1, 2\n"
                                          "  br label %bb2\n"
                                          "bb1:\n"
                                          "  br label %bb3\n"