[llvm-reduce] improve bb removal

[markus]

Summary

Currently the llvm-reduce basic-blocks pass has the habit of replacing branches with ret instructions if the sole branch target of a block has been removed. Replacing a br with a ret results in a radically different CFG that might very well fail to reproduce what we are currently trying to reduce, especially if it is loop dependent. As a result going down these paths is seldom fruitful and we are left with block sequences like the following in the final reduction

cont5830:                                         ; preds = %for.body5828
  br label %for.cond5831

for.cond5831:                                     ; preds = %cont5830
  br label %cont5833

cont5833:                                         ; preds = %for.cond5831
  br label %for.end6075

for.end6075:                                      ; preds = %cont5833
  br label %cont6078

cont6078:                                         ; preds = %for.end6075
  br label %cont6080

cont6080:                                         ; preds = %cont6078
  br label %for.cond5821

This patch instead tries to update the branch to target the next block in sequence that is not to be removed thus increasing the likelihood of still maintaining a loop (while getting rid of some useless sequential flow). Probably we should go further than this and use loop analysis to make sure not to break loop structures but until then this small change seems like a step in the right direction.

[aeubanks]

seems reasonable

[arsenm]

If you blindly scan forward, you're going to run into blocks that have phis that are now missing an input for the new predecessor

[markus]

In D125766#3522764, @arsenm wrote:

If you blindly scan forward, you're going to run into blocks that have phis that are now missing an input for the new predecessor

Yes, absolutely. Since IR verification happens afterwards the reduction is still going to be rejected but of course if we take more care then we can find a reduction that has less risk of failing verification and might lead us down a fruitful path.
So in a way I would consider this an improvement over the current behavior anyway but while we are at it can certainly be improved a bit further. Will address that.

[markus]

Do not branch to blocks with existing phi-node.

[markus]

@arsenm, is this what you had in mind wrt phi-nodes or were you requesting some more elaborate change?

[arsenm]

This isn’t the change I expected but should work for now. I’m working on the machine equivalent of this reduction now and may make additional changes here

[markus]

In D125766#3531269, @arsenm wrote:

I’m working on the machine equivalent of this reduction now and may make additional changes here

Sounds good. There might even be opportunity for some common code (or at least strategy) between IR and MIR here.

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

+; RUN: llvm-reduce --delta-passes=basic-blocks --test %python --test-arg %p/remove-bbs-sequence.py %s -o %t
+; RUN: cat %t | FileCheck %s
+
+; 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:}

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

+import subprocess
+import sys
+
+opt = subprocess.run( [ 'opt', '-passes=print<loops>','-disable-output', sys.argv[1]], stdout=subprocess.PIPE, stderr=subprocess.PIPE )
+
+stdout = opt.stdout.decode()
+
+pattern = 'Loop at depth 1 containing'
+
+if (pattern in opt.stderr.decode()):
+  print('This is interesting!')
+  sys.exit(0)
+else:
+  print('This is NOT interesting!')
+  sys.exit(1)

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

static void replaceBranchTerminator(BasicBlock &BB,
   Value *Address = nullptr;
   if (auto *IndBI = dyn_cast<IndirectBrInst>(Term))
     Address = IndBI->getAddress();
 
   Term->replaceAllUsesWith(UndefValue::get(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 (BBsToKeep.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 : UndefValue::get(FnRetTy),
                        &BB);
     return;
   }
 
   if (IsBranch)