llvm-reduce: Fix producing invalid reductions with landingpads

[arsenm]

Summary

It's not valid to simply branch to a landingpad block, so it
needs to be removed.

Also stop trying to scan forward to find a block that can be merged.
The predecessor merge rules are more complex than this. This also
would need to have considered landingpads. Just do the minimum
to delete the block, and let the simplify-cfg reduction handle
the branch chain cleanups.

[arsenm]

Rebase. Between this and D136461, I'm able to reduce a 56k line testcase without generating invalid reductions

[arsenm]

f02bc70c7d53e5898abddc83f249ef28b8b4b9b6

llvm/test/tools/llvm-reduce/reduce-bb-merge-next-block-invalid-reduction.ll

+; RUN: llvm-reduce --abort-on-invalid-reduction --delta-passes=basic-blocks --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: FileCheck %s < %t
+
+; CHECK-INTERESTINGNESS: store i32 0,
+; CHECK-INTERESTINGNESS: store i32 1,
+
+; CHECK: bb:
+; CHECK-NEXT: br label %bb10
+
+; CHECK: bb10:
+; CHECK-NEXT: br label %bb11
+
+; CHECK: bb11:
+; CHECK-NEXT: br label %bb12
+
+; CHECK: bb12:
+; CHECK-NEXT: switch i32 %arg, label %bb13 [
+; CHECK-NEXT: i32 1, label %bb13
+; CHECK-NEXT: i32 0, label %bb18
+; CHECK-NEXT: ]
+
+; CHECK: bb13:
+; CHECK-NEXT: br label %bb17
+
+; CHECK: bb17:
+; CHECK-NEXT: store i32 0
+; CHECK-NEXT: br label %bb17
+
+; CHECK: bb18:
+; CHECK-NEXT: store i32 1
+; CHECK-NEXT: br label %bb18
+define amdgpu_kernel void @wibble(i32 %arg, i1 %arg1, i1 %arg2) {
+bb:
+  br label %bb10
+
+bb10:                                             ; preds = %bb
+  br label %bb11
+
+bb11:                                             ; preds = %bb10
+  br label %bb12
+
+bb12:                                             ; preds = %bb11
+  switch i32 %arg, label %bb13 [
+    i32 1, label %bb13
+    i32 0, label %bb18
+  ]
+
+bb13:                                             ; preds = %bb12, %bb12
+  br i1 %arg1, label %bb14, label %bb17
+
+bb14:                                             ; preds = %bb15, %bb13
+  %tmp = phi i32 [ 0, %bb15 ], [ 0, %bb13 ]
+  br label %bb15
+
+bb15:                                             ; preds = %bb14
+  %tmp16 = zext i32 %tmp to i64
+  br i1 %arg2, label %bb17, label %bb14
+
+bb17:                                             ; preds = %bb17, %bb15, %bb13
+  store i32 0, ptr addrspace(3) null
+  br label %bb17
+
+bb18:                                             ; preds = %bb18, %bb12
+  store i32 1, ptr addrspace(3) null
+  br label %bb18
+}

llvm/test/tools/llvm-reduce/reduce-bb-unreachable-does-not-dominate-error1.ll

 ; CHECK: bb:
 ; CHECK-NEXT: br i1 %arg1, label %bb3, label %bb7
 
 ; CHECK: bb3: ; preds = %bb
 ; CHECK-NEXT: br i1 %arg2, label %bb4, label %bb7
 
 ; CHECK: bb4: ; preds = %bb3
 ; CHECK-NEXT: store i32 0, ptr addrspace(1) null, align 4
-; CHECK-NEXT: br label %bb10
+; CHECK-NEXT: ret void
 
 ; CHECK: bb7: ; preds = %bb3, %bb
 ; CHECK-NEXT: %i = phi i1 [ false, %bb ], [ true, %bb3 ]
 ; CHECK-NEXT: store i32 1, ptr addrspace(1) null, align 4
 ; CHECK-NEXT: br label %bb10
 
-; CHECK: bb10: ; preds = %bb7, %bb4
+; CHECK: bb10: ; preds = %bb7
 ; CHECK-NEXT: store i32 2, ptr addrspace(1) null, align 4
 ; CHECK-NEXT: unreachable
 define amdgpu_kernel void @func(i1 %arg, i1 %arg1, i1 %arg2) {
 bb:
   br i1 %arg1, label %bb3, label %bb7
 
 bb3:                                              ; preds = %bb
   br i1 %arg2, label %bb4, label %bb7

llvm/test/tools/llvm-reduce/reduce-bb-unreachable-does-not-dominate-error3.ll

 ; RUN: llvm-reduce --abort-on-invalid-reduction --delta-passes=unreachable-basic-blocks,basic-blocks --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
 ; RUN: FileCheck %s < %t
 
 
 ; CHECK-INTERESTINGNESS: store i32 0,
 ; CHECK-INTERESTINGNESS: store i32 1,
 
 
 ; CHECK: bb:
 ; CHECK-NEXT: %tmp = icmp eq i8 0, 0
-; CHECK-NEXT: %tmp12 = load i32, ptr addrspace(4) inttoptr (i64 3016 to ptr addrspace(4)), align 8
-; CHECK-NEXT: %tmp13 = load i32, ptr addrspace(4) null, align 8
-; CHECK-NEXT: br label %bb20
+; CHECK-NEXT: %tmp12 = load i32,
+; CHECK-NEXT: %tmp13 = load i32,
+; CHECK-NEXT: br label %bb14
+
+; CHECK: bb14:
+; CHECK-NEXT: switch i32 %tmp12, label %bb14 [
+; CHECK-NEXT: i32 2, label %bb14
+; CHECK-NEXT: i32 1, label %bb19
+; CHECK-NEXT: ]
+
+; CHECK: bb19:
+; CHECK-NEXT: switch i32 %tmp13, label %bb14 [
+; CHECK-NEXT: i32 2, label %bb21
+; CHECK-NEXT: i32 1, label %bb20
+; CHECK-NEXT: ]
 
 ; CHECK: bb20:
-; CHECK-NEXT: store i32 0, ptr addrspace(3) null, align 4
-; CHECK-NEXT: br label %bb21
+; CHECK-NEXT: store i32 0,
+; CHECK-NEXT: br label %bb14
 
 ; CHECK: bb21:
-; CHECK-NEXT: store i32 1, ptr addrspace(3) null, align 4
-; CHECK-NEXT: ret void
-
+; CHECK-NEXT: store i32 1,
+; CHECK-NEXT: br label %bb14
 define void @snork() {
 bb:
   %tmp = icmp eq i8 0, 0
   %tmp12 = load i32, ptr addrspace(4) inttoptr (i64 3016 to ptr addrspace(4)), align 8
   %tmp13 = load i32, ptr addrspace(4) null, align 8
   br label %bb14
 
 bb14:                                             ; preds = %bb21, %bb20, %bb19, %bb14, %bb

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

-; RUN: llvm-reduce -abort-on-invalid-reduction --delta-passes=basic-blocks --test %python --test-arg %p/remove-bbs-sequence.py %s -o %t
+; RUN: llvm-reduce -abort-on-invalid-reduction --delta-passes=basic-blocks,simplify-cfg --test %python --test-arg %p/remove-bbs-sequence.py %s -o %t
 ; RUN: FileCheck %s < %t
 
 ; The interestingness test is that the CFG contains a loop. Verify that the
 ; unnecessary bb2 and bb3 are removed while still maintaining a loop.
 
 define void @main() {
   bb0:
     br label %bb1
   bb1:
     br label %bb2
   bb2:
     br label %bb3
   bb3:
     %phi = phi i32 [ undef, %bb2 ]
     br label %bb4
   bb4:
     br label %bb1
 }
 
 ; CHECK:define void @main() {
 ; CHECK-NEXT: bb0:
-; CHECK-NEXT:   br label %bb1
-; CHECK-EMPTY:
-; CHECK-NEXT: bb1:
 ; CHECK-NEXT:   br label %bb4
 ; CHECK-EMPTY:
 ; CHECK-NEXT: bb4:
-; CHECK-NEXT:   br label %bb1
+; CHECK-NEXT: %phi = phi i32 [ undef, %bb0 ], [ undef, %bb4 ]
+; CHECK-NEXT: br label %bb4
 ; CHECK-NEXT:}

llvm/test/tools/llvm-reduce/remove-bbs-unwinded-to.ll

-; RUN: llvm-reduce --delta-passes=basic-blocks --test FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
-; RUN: cat %t | FileCheck --check-prefixes=CHECK-ALL,CHECK-FINAL %s
+; RUN: llvm-reduce -abort-on-invalid-reduction --delta-passes=basic-blocks --test FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS0 --test-arg %s --test-arg --input-file %s -o %t.0
+; RUN: FileCheck --check-prefixes=CHECK-ALL,CHECK-FINAL0 %s < %t.0
+
+; RUN: llvm-reduce -abort-on-invalid-reduction --delta-passes=basic-blocks --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS1 --test-arg %s --test-arg --input-file %s -o %t.1
+; RUN: FileCheck --check-prefixes=CHECK-ALL,CHECK-FINAL1 %s < %t.1
 
 declare i32 @maybe_throwing_callee()
 
 ; CHECK-ALL: declare void @did_not_throw(i32)
 declare void @did_not_throw(i32)
 
 declare void @thrown()
 
 ; CHECK-ALL: define void @caller()
 define void @caller() personality ptr @__gxx_personality_v0 {
 ; CHECK-ALL: bb:
+; CHECK-FINAL1-NEXT: br label %bb1
 bb:
-; CHECK-INTERESTINGNESS: label %bb3
-; CHECK-FINAL: br label %bb3
+; CHECK-INTERESTINGNESS0: label %bb3
+; CHECK-FINAL0: br label %bb3
   %i0 = invoke i32 @maybe_throwing_callee()
           to label %bb3 unwind label %bb1
 
 bb1:
   landingpad { ptr, i32 } catch ptr null
+; CHECK-INTERESTINGNESS1: call void @thrown()
+
+; CHECK-FINAL1: bb1:
+; CHECK-FINAL1-NEXT: call void @thrown()
+; CHECK-FINAL1-NEXT: ret void
   call void @thrown()
   br label %bb4
 
-; CHECK-ALL: bb3:
+; CHECK-INTERESTINGNESS0: bb3:
+; CHECK-FINAL0: bb3:
 bb3:
-; CHECK-INTERESTINGNESS: call void @did_not_throw(i32
-; CHECK-FINAL: call void @did_not_throw(i32 0)
-; CHECK-ALL: br label %bb4
+; CHECK-INTERESTINGNESS0: call void @did_not_throw(i32
+; CHECK-INTERESTINGNESS0: br label %bb4
+
+; CHECK-FINAL0: call void @did_not_throw(i32 0)
+; CHECK-FINAL0: br label %bb4
+
   call void @did_not_throw(i32 %i0)
   br label %bb4
 
-; CHECK-ALL: bb4:
-; CHECK-ALL: ret void
+; RESULT0: bb4:
+; RESULT0-NEXT: ret void
+
+; CHECK-INTERESTINGNESS0: bb4:
+; CHECK-INTERESTINGNESS0-NEXT: ret void
 bb4:
   ret void
 }
 
+
 declare i32 @__gxx_personality_v0(...)

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

for (auto *Succ : successors(&BB)) {
     if (!BBsToDelete.count(Succ))
       ChunkSuccessors.push_back(Succ);
   }
 
   // BB only references Chunk BBs
   if (ChunkSuccessors.size() == Term->getNumSuccessors())
     return;
 
-  bool IsBranch = isa<BranchInst>(Term) || isa<InvokeInst>(Term);
+  bool IsBranch = isa<BranchInst>(Term);
+  if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Term)) {
+    LandingPadInst *LP = Invoke->getLandingPadInst();
+    LP->replaceAllUsesWith(getDefaultValue(LP->getType()));
+    LP->eraseFromParent();
+    IsBranch = true;
+  }
+
   Value *Address = nullptr;
   if (auto *IndBI = dyn_cast<IndirectBrInst>(Term))
     Address = IndBI->getAddress();
 
   Term->replaceAllUsesWith(getDefaultValue(Term->getType()));
   Term->eraseFromParent();
 
   if (ChunkSuccessors.empty()) {
-    // Scan forward in BB list to try find a block that is kept.
-    Function &F = *BB.getParent();
-    Function::iterator FI = BB.getIterator();
-    FI++;
-    while (FI != F.end()) {
-      auto &FIB = *FI;
-      if (!BBsToDelete.count(&FIB) && !isa<PHINode>(FIB.begin())) {
-        BranchInst::Create(&FIB, &BB);
-        return;
-      }
-      FI++;
-    }
     // If that fails then resort to replacing with a ret.
     auto *FnRetTy = BB.getParent()->getReturnType();
     ReturnInst::Create(BB.getContext(),
                        FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy),
                        &BB);
     return;
   }