llvm-reduce: Handle reducing blocks using G_BR/G_BRCOND

[arsenm]

Summary

Still doesn't handle reducing G_BRJT into G_BRCOND

llvm/test/tools/llvm-reduce/mir/reduce-blocks-g_br.mir

 # REQUIRES: amdgpu-registered-target
 # RUN: llvm-reduce -abort-on-invalid-reduction -simplify-mir --delta-passes=basic-blocks -mtriple=amdgcn-amd-amdhsa --test FileCheck --test-arg --check-prefix=CHECK-INTERESTINGNESS0 --test-arg %s --test-arg --input-file %s -o %t.0 2> %t.0.log
 # RUN: FileCheck --check-prefix=RESULT0 %s < %t.0
 
 
 # CHECK-INTERESTINGNESS0: S_NOP 0
 # CHECK-INTERESTINGNESS0: S_NOP 1
 # CHECK-INTERESTINGNESS0: S_ENDPGM
 
 # RESULT0: bb.0:
 # RESULT0: %0:_(s32) = COPY $vgpr0
 # RESULT0-NEXT: %1:_(s32) = G_CONSTANT i32 0
 # RESULT0-NEXT: %2:_(s32) = G_ICMP intpred(ugt), %0(s32), %1
 # RESULT0-NEXT: S_NOP 0
-# RESULT0-NEXT: G_BRCOND %2(s32), %bb.[[UNDEF_BB:[0-9]+]]
+# RESULT0-NEXT: %3:_(s1) = G_IMPLICIT_DEF
 # RESULT0-NEXT: G_BR %bb.1
 
 # RESULT0: bb.1:
 # RESULT0-NEXT: S_NOP 1
-# RESULT0-NEXT: G_BRCOND %2(s32), %bb.[[UNDEF_BB]]
-# RESULT0-NEXT: G_BR %bb.[[UNDEF_BB]]
+# RESULT0-NEXT: G_BR %bb.[[UNDEF_BB:[0-9]+]]
 
-# RESULT0: bb.4:
+# RESULT0-NOT: bb.
+
+# RESULT0: bb.5:
 # RESULT0-NEXT: S_ENDPGM 0
 
+# RESULT0-NOT: bb.
+
 # RESULT0: bb.[[UNDEF_BB]]:
 
 ---
 name: g_br
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $vgpr0
bb.1:
     G_BR %bb.2
 
   bb.2:
     S_NOP 2
     G_BRCOND %2(s32), %bb.4
     G_BR %bb.3
 
   bb.3:
+    ; Conditional fallthrough
     S_NOP 3
+    %4:_(s1) = G_IMPLICIT_DEF
+    G_BRCOND %4, %bb.5
 
   bb.4:
+    S_NOP 3
+
+  bb.5:
     S_ENDPGM 0
 
 ...

llvm/test/tools/llvm-reduce/mir/reduce-blocks-g_brjt.mir

 # RESULT0-NEXT: %4:_(s32) = G_IMPLICIT_DEF
 # RESULT0-NEXT: %6:_(s32) = G_IMPLICIT_DEF
 # RESULT0-NEXT: %1:_(s32) = G_IMPLICIT_DEF
 # RESULT0-NEXT: %8:_(s64) = G_IMPLICIT_DEF
 # RESULT0-NEXT: %3:_(s32) = G_IMPLICIT_DEF
 # RESULT0-NEXT: %10:_(s1) = G_IMPLICIT_DEF
 # RESULT0-NEXT: %5:_(s32) = G_IMPLICIT_DEF
 # RESULT0-NEXT: %17:_(s32) = G_IMPLICIT_DEF
-# RESULT0-NEXT: G_BRCOND %10(s1), %bb.[[UNDEF_BB:[0-9]+]]
+# RESULT0-NEXT: G_BR %bb.1
 
 # RESULT0: bb.1.entry:
 # RESULT0-NEXT: S_NOP 1
 # RESULT0-NEXT: %11:_(s32) = G_CONSTANT i32 0
 # RESULT0-NEXT: %12:_(p0) = G_JUMP_TABLE %jump-table.0
 # RESULT0-NEXT: %14:_(s32) = G_IMPLICIT_DEF
 # RESULT0-NEXT: %13:_(s32) = G_IMPLICIT_DEF
 # RESULT0-NEXT: %15:_(s32) = G_IMPLICIT_DEF
 # RESULT0-NEXT: G_BRJT %12(p0), %jump-table.0, %7(s64)
 
-# RESULT0: bb.[[UNDEF_BB]]:
+# RESULT0-NOT: bb.
 
 
 # RESULT1: bb.0.entry:
 # RESULT1: G_BRCOND %10(s1), %bb.4
 
 # RESULT1: bb.1.entry:
 # RESULT1: S_NOP 1
 # RESULT1: G_BRJT %12(p0), %jump-table.0, %7(s64)

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

 #include "llvm/CodeGen/TargetInstrInfo.h"
 
 #define DEBUG_TYPE "llvm-reduce"
 
 using namespace llvm;
 
 using BlockSet = DenseSet<MachineBasicBlock *>;
 
+// Analyze the successors for a block using GlobalISel's generic branch
+// instructions, G_BR and G_BRCOND.
+static bool analyzeBranchGeneric(const MachineBasicBlock &MBB,
+                                 MachineBasicBlock *&TrueMBB,
+                                 MachineBasicBlock *&FalseMBB,
+                                 SmallVectorImpl<MachineOperand> &Cond) {
+  MachineBasicBlock::const_iterator I = MBB.getFirstTerminator();
+  if (I == MBB.end())
+    return false;
+
+  if (I->getOpcode() == TargetOpcode::G_BR) {
+    TrueMBB = I->getOperand(0).getMBB();
+    return false;
+  }
+
+  if (I->getOpcode() != TargetOpcode::G_BRCOND)
+    return true;
+
+  Cond.push_back(I->getOperand(0));
+  TrueMBB = I->getOperand(1).getMBB();
+  ++I;
+  if (I == MBB.end())
+    return false;
+
+  if (I->getOpcode() != TargetOpcode::G_BR)
+    return true;
+
+  FalseMBB = I->getOperand(0).getMBB();
+  return false;
+}
+
+static void removeBranchGeneric(MachineBasicBlock &MBB) {
+  for (MachineInstr &MI : make_early_inc_range(MBB.terminators())) {
+    assert(MI.getOpcode() == TargetOpcode::G_BR ||
+           MI.getOpcode() == TargetOpcode::G_BRCOND);
+    if (MI.isBranch())
+      MI.eraseFromParent();
+  }
+}
+
 static bool isPseudoUndefBlock(const MachineBasicBlock &MBB) {
   return MBB.empty() && &MBB == &MBB.getParent()->back() && MBB.succ_empty();
 }
 
 // We can't have a real undef block like in the IR, so treat an empty block at
 // the end of the function as a pseudo undef block.
 static MachineBasicBlock *getPseudoUndefBlock(MachineFunction &MF) {
   if (isPseudoUndefBlock(MF.back())) {
static void updateCFG(const TargetInstrInfo &TII, MachineBasicBlock &MBB,
   if (MBB.succ_size() == Succs.size())
     return;
 
   // No point in updating the terminators if we're just going to delete all the
   // instructions.
   if (&MBB != EntryBB && BBsToDelete.count(&MBB))
     return;
 
+  enum BranchType {
+    UnknownBranching,
+    TargetBranching,
+    GenericBranching
+  } BranchType = UnknownBranching;
+
   MachineBasicBlock *TBB = nullptr;
   MachineBasicBlock *FBB = nullptr;
   SmallVector<MachineOperand, 2> Cond;
+
   if (TII.analyzeBranch(MBB, TBB, FBB, Cond)) {
+    TBB = FBB = nullptr;
+    if (!analyzeBranchGeneric(MBB, TBB, FBB, Cond))
+      BranchType = GenericBranching;
+  } else
+    BranchType = TargetBranching;
+
+  if (BranchType == UnknownBranching) {
     // If we don't understand this branch, replace deleted block references with
     // the dummy undef block.
     bool UsedUndefBlock = false;
 
     for (MachineInstr &Term : MBB.terminators()) {
       for (MachineOperand &MO : Term.operands()) {
         if (MO.isMBB() && BBsToDelete.count(MO.getMBB())) {
           if (!UndefBlock)
             UndefBlock = getPseudoUndefBlock(*MF);
 
           MO.setMBB(UndefBlock);
           UsedUndefBlock = true;
         }
       }
     }
 
     if (UsedUndefBlock && !MBB.isSuccessor(UndefBlock))
       MBB.addSuccessor(UndefBlock);
 
     return;
   }
 
   // If we can analyze this branch, insert simplified terminators.
+  if (BranchType == GenericBranching)
+    removeBranchGeneric(MBB);
+  else
     TII.removeBranch(MBB);
 
   MachineBasicBlock *NewSucc;
   if (MBB.succ_empty()) {
     // We don't have an API to insert a return, so insert a branch to fall off
     // the end of the function.
     if (!UndefBlock)
       UndefBlock = getPseudoUndefBlock(*MBB.getParent());
     MBB.addSuccessor(UndefBlock);
     NewSucc = UndefBlock;
   } else {
     assert(MBB.succ_size() == 1);
     NewSucc = *MBB.succ_begin();
   }
 
+  if (BranchType == GenericBranching) {
+    BuildMI(&MBB, DebugLoc(), TII.get(TargetOpcode::G_BR))
+      .addMBB(NewSucc);
+  } else {
     TII.insertUnconditionalBranch(MBB, NewSucc, DebugLoc());
   }
+}
 
 static unsigned getImpDefOpcode(const MachineRegisterInfo &MRI, Register Reg) {
   return Reg.isVirtual() && MRI.getRegClassOrNull(Reg) == nullptr
              ? TargetOpcode::G_IMPLICIT_DEF
              : TargetOpcode::IMPLICIT_DEF;
 }
 
 static int getBasicBlockIndex(const MachineInstr &Phi,