Index: llvm/test/tools/llvm-reduce/remove-bbs-illegal.ll
===================================================================
--- /dev/null
+++ llvm/test/tools/llvm-reduce/remove-bbs-illegal.ll
@@ -0,0 +1,25 @@
+; Ensure that llvm-reduce doesn't try to remove the first BB of a
+; function when the second BB has multiple predecessors, since that
+; results in invalid IR. This issue was fixed by:
+; https://reviews.llvm.org/D131026
+
+; RUN: llvm-reduce --delta-passes=basic-blocks --test %python --test-arg %p/Inputs/remove-bbs.py -abort-on-invalid-reduction %s -o %t
+
+define void @f(ptr %x0) {
+uninteresting:
+  %x2 = alloca ptr, i32 0, align 8
+  %x3 = alloca ptr, i32 0, align 8
+  br label %interesting1
+
+; this block has 2 predecessors and can't become the entry block
+interesting1:
+  %x5 = icmp ne ptr %x0, null
+  br i1 %x5, label %interesting2, label %interesting1
+
+interesting2:
+  store ptr null, ptr null, align 8
+  br label %interesting3
+
+interesting3:
+  ret void
+}
Index: llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp
===================================================================
--- llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp
+++ llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp
@@ -102,6 +102,19 @@
     }
 }
 
+/// a BB is ok to remove if it's not the entry block, or else it is
+/// the entry block but the next block in the function has just one
+/// predecessor -- this property is required because that block is
+/// going to become the new entry block
+static bool okToRemove(BasicBlock &BB) {
+  if (!BB.isEntryBlock())
+    return true;
+  auto F = BB.getParent();
+  auto it = F->begin();
+  ++it;
+  return (it == F->end()) || (*it).hasNPredecessors(1);
+}
+
 /// Removes out-of-chunk arguments from functions, and modifies their calls
 /// accordingly. It also removes allocations of out-of-chunk arguments.
 static void extractBasicBlocksFromModule(Oracle &O, Module &Program) {
@@ -110,7 +123,7 @@
   SmallVector<BasicBlock *> BBsToDelete;
   for (auto &F : Program) {
     for (auto &BB : F) {
-      if (O.shouldKeep())
+      if (!okToRemove(BB) || O.shouldKeep())
         BBsToKeep.insert(&BB);
       else {
         BBsToDelete.push_back(&BB);