diff --git a/llvm/tools/llvm-reduce/deltas/ReduceInstructions.cpp b/llvm/tools/llvm-reduce/deltas/ReduceInstructions.cpp
--- a/llvm/tools/llvm-reduce/deltas/ReduceInstructions.cpp
+++ b/llvm/tools/llvm-reduce/deltas/ReduceInstructions.cpp
@@ -24,10 +24,14 @@
   std::set<Instruction *> InstToKeep;
 
   for (auto &F : *Program)
-    for (auto &BB : F)
-      for (auto &Inst : BB)
+    for (auto &BB : F) {
+      // Removing the terminator would make the block invalid. Only iterate over
+      // instructions before the terminator.
+      InstToKeep.insert(BB.getTerminator());
+      for (auto &Inst : make_range(BB.begin(), std::prev(BB.end())))
         if (O.shouldKeep())
           InstToKeep.insert(&Inst);
+    }
 
   std::vector<Instruction *> InstToDelete;
   for (auto &F : *Program)
@@ -49,7 +53,8 @@
   int InstCount = 0;
   for (auto &F : *Program)
     for (auto &BB : F)
-        InstCount += BB.getInstList().size();
+      // Well-formed blocks have terminators, which we cannot remove.
+      InstCount += BB.getInstList().size() - 1;
   outs() << "Number of instructions: " << InstCount << "\n";
 
   return InstCount;