diff --git a/llvm/lib/CodeGen/MachineLoopUtils.cpp b/llvm/lib/CodeGen/MachineLoopUtils.cpp
--- a/llvm/lib/CodeGen/MachineLoopUtils.cpp
+++ b/llvm/lib/CodeGen/MachineLoopUtils.cpp
@@ -103,10 +103,14 @@
 
   DebugLoc DL;
   if (Direction == LPD_Front) {
-    Preheader->replaceSuccessor(Loop, NewBB);
+    Preheader->ReplaceUsesOfBlockWith(Loop, NewBB);
     NewBB->addSuccessor(Loop);
     Loop->replacePhiUsesWith(Preheader, NewBB);
-    if (TII->removeBranch(*Preheader) > 0)
+    Preheader->updateTerminator(Loop);
+    if (Preheader->getFallThrough() == NewBB)
+      // Technically we don't need this, but some code downstream, specifically
+      // the peeling modulo expander is always expecting a terminator in the
+      // prologs.
       TII->insertBranch(*Preheader, NewBB, nullptr, {}, DL);
     TII->removeBranch(*NewBB);
     TII->insertBranch(*NewBB, Loop, nullptr, {}, DL);