stop llvm-reduce's ReduceBasicBlocks delta pass from creating invalid IR

[regehr]

Summary

When the basic block delta pass removes the first basic block in a function, that function becomes illegal if the second block has extra predecessors. The function below is an example of one that triggers this issue. While we could think of various clever ways to fix this issue, the patch here simply makes the entry block ineligible for removal.

define void @aeDeleteEventLoop(ptr %0) {

%2 = alloca ptr, i32 0, align 8
%3 = alloca ptr, i32 0, align 8
call void @zfree()
br label %4

4: ; preds = %6, %1

%5 = icmp ne ptr %0, null
br i1 %5, label %6, label %7

6: ; preds = %4

store ptr null, ptr null, align 8
br label %4

7: ; preds = %4

ret void

}

[aeubanks]

could you add a test case that uses -abort-on-invalid-reduction?

[regehr]

thanks Arthur-- I've added this test and also refined the safety check in the pass to be less conservative

[arsenm]

LGTM. I do think something is off about how the pass currently tries to auto-fold unconditional branches to successors. I was thinking there should be a separate control flow simplification to clean those up

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

105

Capitalize a

[regehr]

In D131026#3695477, @arsenm wrote:

LGTM. I do think something is off about how the pass currently tries to auto-fold unconditional branches to successors. I was thinking there should be a separate control flow simplification to clean those up

hey I have written this and am just testing and cleaning it up!! hope to submit the patch for review soonish, I will tag you in it :)

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);
+}
+
 /// 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;
 
   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);
         // Remove out-of-chunk BB from successor phi nodes
         for (auto *Succ : successors(&BB))
           Succ->removePredecessor(&BB);
       }
     }