a better fix for llvm-reduce's basicblock pass

[regehr]

Summary

the fix I submitted yesterday fixed all cases I had seen but missed other cases, that are now fixed by this patch. I'm fairly sure this is now solid.

[regehr]

this is the first version of llvm-reduce I've seen that makes it all the way through my benchmark suite in --abort-on-invalid-reduction mode!

[arsenm]

llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp

112

This is just continue

124–125

; after :

138

When doing the MIR version I found it was easier to only track the deletion set. Does this really need a set for both?

[regehr]

llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp

112

yeah I was going for consistency with the goto in the following code (which isn't just continue) but can do continue if you think that's cleaner

124–125

the semicolon is required. if this is all too ugly I can use a boolean flag instead of the gotos. I wrote them both and thought this way is a bit cleaner but happy to do the other thing

138

well, the existing code uses both, and I'm trying to be minimally invasive. if we want to refactor to get rid of one of them, I think we should do it as a separate patchset

[arsenm]

llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp

113

BBSToDelete.count?

[regehr]

updated patch with code suggested by matt, thanks, this is much better

[arsenm]

LGTM

[regehr]

better now

[regehr]

ok hopefully final version, sorry, getting started slowly this morning

llvm/test/tools/llvm-reduce/remove-bbs-illegal2.ll

+; RUN: llvm-reduce --delta-passes=basic-blocks --test %python --test-arg %p/Inputs/remove-bbs.py -abort-on-invalid-reduction %s -o %t
+
+declare void @0()
+
+define internal void @1(ptr %x0, i1 %x1) {
+interesting0:
+  %x3 = alloca i32, align 4
+  store ptr null, ptr %x0, align 8
+  br label %interesting1
+
+interesting1:                                                ; preds = %x2
+  call void @0()
+  br label %x2
+
+x2:
+  br i1 %x1, label %interesting3, label %interesting4
+
+interesting3:
+  call void @0()
+  br label %x2
+
+interesting4:
+  br label %x5
+
+x5:
+  store i32 0, ptr %x3, align 4
+  ret void
+}

llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp

for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
       if (!BBsToKeep.count(Case->getCaseSuccessor())) {
         SwInst.removeCase(Case);
         --I;
         --E;
       }
     }
 }
 
-/// 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);
+/// It's OK to add a block to the set of removed blocks if the first
+/// basic block in the function that survives all of the deletions is
+/// a legal entry block
+static bool okToRemove(BasicBlock &Candidate, Function &F,
+                       const DenseSet<BasicBlock *> &BBsToDelete) {
+  for (auto &B : F) {
+    if (&B == &Candidate)
+      continue;
+    if (BBsToDelete.count(&B))
+      continue;
+    /// Ok we've found the first block that's not going to be deleted,
+    /// it will be the new entry block -- that's only legal if this
+    /// block has no predecessors among blocks that survive the
+    /// deletions
+    for (BasicBlock *Pred : predecessors(&B)) {
+      if (!BBsToDelete.contains(Pred))
+        return false;
+    }
+    return true;
+  }
 }
 
 /// 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) {
-  DenseSet<BasicBlock *> BBsToKeep;
+  DenseSet<BasicBlock *> BBsToKeep, BBsToDelete;
 
-  SmallVector<BasicBlock *> BBsToDelete;
   for (auto &F : Program) {
     for (auto &BB : F) {
-      if (!okToRemove(BB) || O.shouldKeep())
+      if (!okToRemove(BB, F, BBsToDelete) || O.shouldKeep())
         BBsToKeep.insert(&BB);
-      else {
-        BBsToDelete.push_back(&BB);
-        // Remove out-of-chunk BB from successor phi nodes
-        for (auto *Succ : successors(&BB))
-          Succ->removePredecessor(&BB);
-      }
-    }
-  }
+      else
+        BBsToDelete.insert(&BB);
+    }
+  }
+
+  for (auto &F : Program) {
+    for (auto &BB : F) {
 
   // Replace terminators that reference out-of-chunk BBs
   for (auto &F : Program)
     for (auto &BB : F) {
       if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
         removeUninterestingBBsFromSwitch(*SwInst, BBsToKeep);
       else
         replaceBranchTerminator(BB, BBsToKeep);