[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

while (TIB != TIE && FIB != FIE) {
     if (!TIB->isIdenticalTo(*FIB))
       break;
     // A pred-clobbering instruction in the shared portion prevents
     // if-conversion.
     std::vector<MachineOperand> PredDefs;
     if (TII->DefinesPredicate(*TIB, PredDefs))
       return false;
     // If we get all the way to the branch instructions, don't count them.
-    if (!TIB->isBranch())
+    // We treat returns as unconditional branches
+    if (!(TIB->isBranch() || TIB->isReturn()))
       ++Dups1;
     ++TIB;
     ++FIB;
   }
 
   // Check for already containing all of the block.
   if (TIB == TIE || FIB == FIE)
     return true;
while (RTIE != RTIB && RFIE != RFIB) {
     RTIE = skipDebugInstructionsForward(RTIE, RTIB);
     RFIE = skipDebugInstructionsForward(RFIE, RFIB);
     if (RTIE == RTIB || RFIE == RFIB)
       break;
     if (!RTIE->isIdenticalTo(*RFIE))
       break;
     // We have to verify that any branch instructions are the same, and then we
     // don't count them toward the # of duplicate instructions.
-    if (!RTIE->isBranch())
+    if (!(RTIE->isBranch() || RTIE->isReturn()))
       ++Dups2;
     ++RTIE;
     ++RFIE;
   }
   TIE = std::next(RTIE.getReverse());
   FIE = std::next(RFIE.getReverse());
   return true;
 }

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 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:    BCLRn $cr2lt, implicit $lr8, implicit $rm, implicit $x3
+# CHECK:    BCLR $cr2lt, implicit $lr8, implicit $rm, implicit $x3
+
+