[if-converter] Handle BB that terminate in ret during diamond conversion

[vchuravy]

Summary

While I was updating the Julia frontend for LLVM 6.0.0 I encountered a situation
where we emitted code that triggered the diamond conversion in if-converter while
TrueBB and FalseBB terminated in ret.

      BB
    /    \
TrueBB  FalseBB
  ...     ...
  ret     ret

The if-converter pass decided that this was a valid structure to do a diamond conversion on
and this triggered an assertion later on since if-converter implictly assumed that TrueBB and
FalseBB terminate in a branch or a fall-trough. Since the situation described above is equivalent
to:

      BB
    /    \
TrueBB  FalseBB
  ...     ...
    \     /
       BB
       ret

I think it is reasonable for if-converter to do a diamond conversion on and so this PR adds a bit handling for
return (treating returns as a form of an unconditional branch).

This fixes https://bugs.llvm.org/show_bug.cgi?id=36825

[vchuravy]

@nemanjai correctly noted that the both branches are equal and we can simplify this,
by making sure that we don't fall over the iterator and then removing both BB.

My previous version causes problems for other test cases and this version passes my minimal test
and the case found in the Julia frontend.

[kparzysz]

I encountered a related problem in Hexagon code and I amended the patch to handle that as well. I couldn't upload it to this review, so I created a new one: D45819, but it's really meant to be an extension of this fix.

[vchuravy]

Superseded by https://reviews.llvm.org/D45819

lib/CodeGen/IfConversion.cpp

bool IfConverter::IfConvertDiamondCommon(
   MachineBasicBlock::iterator DI1 = MBB1.getFirstNonDebugInstr();
   MachineBasicBlock::iterator DI2 = MBB2.getFirstNonDebugInstr();
   BBI1->NonPredSize -= NumDups1;
   BBI2->NonPredSize -= NumDups1;
 
   // Skip past the dups on each side separately since there may be
   // differing dbg_value entries.
   for (unsigned i = 0; i < NumDups1; ++DI1) {
+    if (DI1 == MBB1.end())
+      break;
     if (!DI1->isDebugValue())
       ++i;
   }
   while (NumDups1 != 0) {
     ++DI2;
+    if (DI2 == MBB2.end())
+      break;
     if (!DI2->isDebugValue())
       --NumDups1;
   }
 
   if (MRI->tracksLiveness()) {
     for (const MachineInstr &MI : make_range(MBB1.begin(), DI1)) {
       SmallVector<std::pair<unsigned, const MachineOperand*>, 4> Dummy;
       Redefs.stepForward(MI, Dummy);
for (unsigned i = 0; i != NumDups2; ) {
     assert(DI1 != MBB1.begin());
     --DI1;
     // skip dbg_value instructions
     if (!DI1->isDebugValue())
       ++i;
   }
   MBB1.erase(DI1, MBB1.end());
 
+  // Identical blocks, already moved all the instructions up.
+  if (MBB1.empty() && MBB2.empty()) {
+    BBI.BB->removeSuccessor(&MBB1, true);
+    BBI.BB->removeSuccessor(&MBB2, true);
+    return true;
+  }
   DI2 = BBI2->BB->end();
   // The branches have been checked to match. Skip over the branch in the false
   // block so that we don't try to predicate it.
   if (RemoveBranch)
     BBI2->NonPredSize -= TII->removeBranch(*BBI2->BB);
   else {
     do {
       assert(DI2 != MBB2.begin());

test/CodeGen/MIR/PowerPC/ifcvt-diamond-ret.mir

+# RUN: llc -mtriple=powerpc64le-unknown-linux-gnu -run-pass=if-converter %s -o - | FileCheck %s
+---
+name:           foo
+body:           |
+  bb.0:
+  liveins: $x0, $x3
+  successors: %bb.1(0x40000000), %bb.2(0x40000000)
+
+  dead renamable $x3 = ANDIo8 killed renamable $x3, 1, implicit-def dead $cr0, implicit-def $cr0gt
+  $cr2lt = CROR $cr0gt, $cr0gt
+  BCn killed renamable $cr2lt, %bb.2
+  B %bb.1
+
+  bb.1:
+    renamable $x3 = LIS8 4096
+    MTLR8 $x0, implicit-def $lr8
+    BLR8 implicit $lr8, implicit $rm, implicit $x3
+
+  bb.2:
+    renamable $x3 = LIS8 4096
+    MTLR8 $x0, implicit-def $lr8
+    BLR8 implicit $lr8, implicit $rm, implicit $x3
+...
+
+# Diamond testcase with equivalent branches terminating in returns.
+
+# CHECK: body:             |          
+# CHECK:  bb.0:
+# CHECK:    dead renamable $x3 = ANDIo8 killed renamable $x3, 1, implicit-def dead $cr0, implicit-def $cr0gt
+# CHECK:    $cr2lt = CROR $cr0gt, $cr0gt
+# CHECK:    renamable $x3 = LIS8 4096
+# CHECK:    MTLR8 $x0, implicit-def $lr8
+# CHECK:    BLR8 implicit $lr8, implicit $rm, implicit $x3
+