diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
--- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
@@ -2948,9 +2948,21 @@
 
   SmallVector<MachineBasicBlock *, 8> DuplicatedPreds;
   bool IsSimple = TailDup.isSimpleBB(BB);
+  BlockChain &BBChain = *BlockToChain[BB];
   TailDup.tailDuplicateAndUpdate(IsSimple, BB, LPred,
                                  &DuplicatedPreds, &RemovalCallbackRef);
 
+  // Decrease UnscheduledPredecessors previously set for BBChain, if BB is
+  // deleted during tail duplication.
+  if (Removed)
+    for (MachineBasicBlock *Pred : DuplicatedPreds) {
+      if (BlockFilter && !BlockFilter->count(Pred))
+        continue;
+      if (&BBChain != BlockToChain[Pred] &&
+          BBChain.UnscheduledPredecessors != 0)
+        --BBChain.UnscheduledPredecessors;
+    }
+
   // Update UnscheduledPredecessors to reflect tail-duplication.
   DuplicatedToLPred = false;
   for (MachineBasicBlock *Pred : DuplicatedPreds) {