If conversion update

[kparzysz]

Summary

This is an update to D45218, I couldn't update the patch directly in that review.

[vchuravy]

From my side this looks good and it fixes my more complicated test-case in Julia as well.

[kparzysz]

Committed in https://reviews.llvm.org/rL330345.

lib/CodeGen/IfConversion.cpp

bool IfConverter::IfConvertDiamondCommon(
   //   after tracking the BB1 instructions.
   Redefs.init(*TRI);
   if (MRI->tracksLiveness()) {
     Redefs.addLiveIns(MBB1);
     Redefs.addLiveIns(MBB2);
   }
 
   // Remove the duplicated instructions at the beginnings of both paths.
-  // Skip dbg_value instructions
+  // Skip dbg_value instructions.
   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.
+  // differing dbg_value entries. NumDups1 can include a "return"
+  // instruction, if it's not marked as "branch".
   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);
     }
   }
+
   BBI.BB->splice(BBI.BB->end(), &MBB1, MBB1.begin(), DI1);
   MBB2.erase(MBB2.begin(), DI2);
 
-  // The branches have been checked to match, so it is safe to remove the branch
-  // in BB1 and rely on the copy in BB2
+  // The branches have been checked to match, so it is safe to remove the
+  // branch in BB1 and rely on the copy in BB2. The complication is that
+  // the blocks may end with a return instruction, which may or may not
+  // be marked as "branch". If it's not, then it could be included in
+  // "dups1", leaving the blocks potentially empty after moving the common
+  // duplicates.
 #ifndef NDEBUG
   // Unanalyzable branches must match exactly. Check that now.
   if (!BBI1->IsBrAnalyzable)
     verifySameBranchInstructions(&MBB1, &MBB2);
 #endif
   BBI1->NonPredSize -= TII->removeBranch(*BBI1->BB);
   // Remove duplicated instructions.
   DI1 = MBB1.end();
#endif
   MBB1.erase(DI1, MBB1.end());
 
   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());
-      DI2--;
-    } while (DI2->isBranch() || DI2->isDebugValue());
-    DI2++;
+    // Make DI2 point to the end of the range where the common "tail"
+    // instructions could be found.
+    while (DI2 != MBB2.begin()) {
+      MachineBasicBlock::iterator Prev = std::prev(DI2);
+      if (!Prev->isBranch() && !Prev->isDebugValue())
+        break;
+      DI2 = Prev;
+    }
   }
   while (NumDups2 != 0) {
     // NumDups2 only counted non-dbg_value instructions, so this won't
     // run off the head of the list.
     assert(DI2 != MBB2.begin());
     --DI2;
     // skip dbg_value instructions
     if (!DI2->isDebugValue())
#endif
 
   // Predicate the 'true' block.
   PredicateBlock(*BBI1, MBB1.end(), *Cond1, &RedefsByFalse);
 
   // After predicating BBI1, if there is a predicated terminator in BBI1 and
   // a non-predicated in BBI2, then we don't want to predicate the one from
   // BBI2. The reason is that if we merged these blocks, we would end up with
   // two predicated terminators in the same block.
+  // Also, if the branches in MBB1 and MBB2 were non-analyzable, then don't
+  // predicate them either. They were checked to be identical, and so the
+  // same branch would happen regardless of which path was taken.
   if (!MBB2.empty() && (DI2 == MBB2.end())) {
     MachineBasicBlock::iterator BBI1T = MBB1.getFirstTerminator();
     MachineBasicBlock::iterator BBI2T = MBB2.getFirstTerminator();
-    if (BBI1T != MBB1.end() && TII->isPredicated(*BBI1T) &&
-        BBI2T != MBB2.end() && !TII->isPredicated(*BBI2T))
+    bool BB1Predicated = BBI1T != MBB1.end() && TII->isPredicated(*BBI1T);
+    bool BB2NonPredicated = BBI2T != MBB2.end() && !TII->isPredicated(*BBI2T);
+    if (BB2NonPredicated && (BB1Predicated || !BBI2->IsBrAnalyzable))
       --DI2;
   }
 
   // Predicate the 'false' block.
   PredicateBlock(*BBI2, DI2, *Cond2);
 
   // Merge the true block into the entry of the diamond.
   MergeBlocks(BBI, *BBI1, MergeAddEdges);

test/CodeGen/Hexagon/ifcvt-diamond-ret.mir

+# RUN: llc -march=hexagon -run-pass if-converter %s -o - | FileCheck %s
+
+# Make sure this gets if-converted and it doesn't crash.
+# CHECK-LABEL: bb.0
+# CHECK: PS_jmpret $r31
+# CHECK-NOT: bb.{{[1-9]+}}:
+
+---
+name: fred
+tracksRegLiveness: true
+body: |
+  bb.0:
+    successors: %bb.1, %bb.2
+    liveins: $r0
+    renamable $p0 = C2_cmpeqi killed renamable $r0, 0
+    J2_jumpf killed renamable $p0, %bb.2, implicit-def dead $pc
+
+  bb.1:
+    S4_storeiri_io undef renamable $r0, 0, 32768 :: (store 4 into `i32* undef`)
+    PS_jmpret $r31, implicit-def dead $pc
+
+  bb.2:
+    S4_storeiri_io undef renamable $r0, 0, 32768 :: (store 4 into `i32* undef`)
+    PS_jmpret $r31, implicit-def dead $pc
+...

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
+