[PowerPC] handle more than two predecessors loop header in ctrloop pass

[shchenz]

Summary

After ISEL, the "valid" loop header which has two predecessors
(one is preheader and the other one is latch) may be transformed
to have more than two predecessors by some optimizations, like tail
duplicator, if the old header's successor(will be changed to new
header) is a sub loop.

The predecessors of the new loop header are preheader, loop latch
and the loop latch(es) of the sub loop(old header's successor).

Before the patch, ctrloop pass assumes two predecessors for candidate
loop header. This patch fixes this case.

[lkail]

The summary is a bit confusing. Might be phrased to something like
"The header of the outermost loop is also the header of a self-cycle sub loop".

[lkail]

LG.

[shchenz]

This is not a complete solution. I will refine the implementation later.

[shchenz]

Thanks for review and the offline discussion @lkail

llvm/lib/Target/PowerPC/PPCCTRLoops.cpp

Register ADDIDef =
                                          : &PPC::GPRC_and_GPRC_NOR0RegClass);
   // Generate "addi -1" in the exiting block.
   BuildMI(*Exiting, Dec, Dec->getDebugLoc(), TII->get(ADDIOpcode), ADDIDef)
       .addReg(PHIDef)
       .addImm(-1);
 
   // Add other inputs for the PHI node.
   if (ML->isLoopLatch(Exiting)) {
-    // There must be only two predecessors for the loop header, one is the
-    // Preheader and the other one is loop latch Exiting. In hardware loop
+    // Normally there must be only two predecessors for the loop header, one is
+    // the Preheader and the other one is loop latch Exiting. In hardware loop
     // insertion pass, the block containing DecreaseCTRloop must dominate all
     // loop latches. So there must be only one latch.
-    assert(ML->getHeader()->pred_size() == 2 &&
-           "Loop header predecessor is not right!");
+    // But there are some optimizations after ISEL, like tail duplicator, may
+    // merge the two-predecessor loop header with its successor. If the
+    // successor happens to be a header of nest loop, then we will have a header
+    // which has more than 2 predecessors.
+    assert(std::find(ML->getHeader()->predecessors().begin(),
+                     ML->getHeader()->predecessors().end(),
+                     Exiting) != ML->getHeader()->predecessors().end() &&
+           "Loop latch is not loop header predecessor!");
+    assert(std::find(ML->getHeader()->predecessors().begin(),
+                     ML->getHeader()->predecessors().end(),
+                     Preheader) != ML->getHeader()->predecessors().end() &&
+           "Loop preheader is not loop header predecessor!");
+
     PHIMIB.addReg(ADDIDef).addMBB(Exiting);
+
+    if (ML->getHeader()->pred_size() > 2) {
+      Register HeaderIncoming = MRI->createVirtualRegister(
+          Is64Bit ? &PPC::G8RC_and_G8RC_NOX0RegClass
+                  : &PPC::GPRC_and_GPRC_NOR0RegClass);
+      BuildMI(*ML->getHeader(), ML->getHeader()->getFirstNonPHI(), DebugLoc(),
+              TII->get(TargetOpcode::COPY), HeaderIncoming)
+          .addReg(PHIDef);
+
+      for (MachineBasicBlock *P : ML->getHeader()->predecessors()) {
+        if (P != Preheader && P != Exiting)
+          PHIMIB.addReg(HeaderIncoming).addMBB(P);
+      }
+    }
   } else {
     // If the block containing DecreaseCTRloop is not a loop latch, we can use
     // ADDIDef as the value for all other blocks for the PHI. In hardware loop
     // insertion pass, the block containing DecreaseCTRloop must dominate all
     // loop latches.
     for (MachineBasicBlock *P : ML->getHeader()->predecessors()) {
       if (ML->contains(P)) {
         assert(ML->isLoopLatch(P) &&

llvm/test/CodeGen/PowerPC/ctrloop-header-multiple-preds.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -ppc-asm-full-reg-names -mtriple=powerpc-ibm-aix-xcoff \
+# RUN:   -stop-after=ppc-ctrloops %s -o - -verify-machineinstrs | FileCheck %s
+
+---
+name:            three-preds-single-block-loop
+
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: three-preds-single-block-loop
+  ; CHECK: bb.0.entry:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[LI:%[0-9]+]]:gprc = LI 2048
+  ; CHECK-NEXT:   [[LI1:%[0-9]+]]:gprc = LI 9
+  ; CHECK-NEXT:   [[CMPLWI:%[0-9]+]]:crrc = CMPLWI [[LI1]], 0
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:crbitrc = COPY [[CMPLWI]].sub_eq
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[PHI:%[0-9]+]]:gprc_and_gprc_nor0 = PHI [[LI]], %bb.0, %7, %bb.2, %8, %bb.1
+  ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:gprc_and_gprc_nor0 = COPY [[PHI]]
+  ; CHECK-NEXT:   BC [[COPY]], %bb.1
+  ; CHECK-NEXT:   B %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.3(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+  ; CHECK-NEXT:   [[ADDI:%[0-9]+]]:gprc_and_gprc_nor0 = ADDI [[PHI]], -1
+  ; CHECK-NEXT:   [[CMPLWI1:%[0-9]+]]:crrc = CMPLWI [[ADDI]], 0
+  ; CHECK-NEXT:   [[COPY2:%[0-9]+]]:crbitrc = COPY [[CMPLWI1]].sub_gt
+  ; CHECK-NEXT:   BC [[COPY2]], %bb.1
+  ; CHECK-NEXT:   B %bb.3
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   BLR implicit $lr, implicit $rm
+  bb.0.entry:
+
+    %0:gprc = LI 2048
+    %1:gprc_and_gprc_nor0 = LI 10
+    MTCTRloop killed %0:gprc, implicit-def dead $ctr
+
+  bb.1:
+    %2:gprc = ADDI %1:gprc_and_gprc_nor0, -1
+    %3:crrc = CMPLWI %2:gprc, 0
+    %4:crbitrc = COPY %3.sub_eq
+    BC killed %4:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+    %5:crbitrc = DecreaseCTRloop 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %5:crbitrc, %bb.1
+    B %bb.3
+
+  bb.3:
+
+    BLR implicit $lr, implicit $rm
+...
+---
+name:            three-preds-mult-blocks-loop
+
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: three-preds-mult-blocks-loop
+  ; CHECK: bb.0.entry:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[LI:%[0-9]+]]:gprc = LI 2048
+  ; CHECK-NEXT:   [[LI1:%[0-9]+]]:gprc = LI 9
+  ; CHECK-NEXT:   [[CMPLWI:%[0-9]+]]:crrc = CMPLWI [[LI1]], 0
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:crbitrc = COPY [[CMPLWI]].sub_eq
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[PHI:%[0-9]+]]:gprc_and_gprc_nor0 = PHI [[LI]], %bb.0, %7, %bb.3, %8, %bb.2
+  ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:gprc_and_gprc_nor0 = COPY [[PHI]]
+  ; CHECK-NEXT:   INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+  ; CHECK-NEXT:   B %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.3(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   BC [[COPY]], %bb.1
+  ; CHECK-NEXT:   B %bb.3
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.4(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+  ; CHECK-NEXT:   [[ADDI:%[0-9]+]]:gprc_and_gprc_nor0 = ADDI [[PHI]], -1
+  ; CHECK-NEXT:   [[CMPLWI1:%[0-9]+]]:crrc = CMPLWI [[ADDI]], 0
+  ; CHECK-NEXT:   [[COPY2:%[0-9]+]]:crbitrc = COPY [[CMPLWI1]].sub_gt
+  ; CHECK-NEXT:   BC [[COPY2]], %bb.1
+  ; CHECK-NEXT:   B %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4:
+  ; CHECK-NEXT:   BLR implicit $lr, implicit $rm
+  bb.0.entry:
+
+    %0:gprc = LI 2048
+    %1:gprc_and_gprc_nor0 = LI 10
+    MTCTRloop killed %0:gprc, implicit-def dead $ctr
+
+  bb.1:
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+    B %bb.2
+
+  bb.2:
+    %2:gprc = ADDI %1:gprc_and_gprc_nor0, -1
+    %3:crrc = CMPLWI %2:gprc, 0
+    %4:crbitrc = COPY %3.sub_eq
+    BC killed %4:crbitrc, %bb.1
+    B %bb.3
+
+  bb.3:
+
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+    %5:crbitrc = DecreaseCTRloop 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %5:crbitrc, %bb.1
+    B %bb.4
+
+  bb.4:
+
+    BLR implicit $lr, implicit $rm
+...
+---
+name:            more-than-three-preds
+
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: more-than-three-preds
+  ; CHECK: bb.0.entry:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[LI:%[0-9]+]]:gprc = LI 2048
+  ; CHECK-NEXT:   [[LI1:%[0-9]+]]:gprc = LI 9
+  ; CHECK-NEXT:   [[CMPLWI:%[0-9]+]]:crrc = CMPLWI [[LI1]], 0
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:crbitrc = COPY [[CMPLWI]].sub_eq
+  ; CHECK-NEXT:   [[LI2:%[0-9]+]]:gprc = LI 8
+  ; CHECK-NEXT:   [[CMPLWI1:%[0-9]+]]:crrc = CMPLWI [[LI2]], 0
+  ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:crbitrc = COPY [[CMPLWI1]].sub_gt
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[PHI:%[0-9]+]]:gprc_and_gprc_nor0 = PHI [[LI]], %bb.0, %10, %bb.4, %11, %bb.2, %11, %bb.3
+  ; CHECK-NEXT:   [[COPY2:%[0-9]+]]:gprc_and_gprc_nor0 = COPY [[PHI]]
+  ; CHECK-NEXT:   INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+  ; CHECK-NEXT:   B %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.3(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   BC [[COPY]], %bb.1
+  ; CHECK-NEXT:   B %bb.3
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.4(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   BC [[COPY1]], %bb.1
+  ; CHECK-NEXT:   B %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.5(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+  ; CHECK-NEXT:   [[ADDI:%[0-9]+]]:gprc_and_gprc_nor0 = ADDI [[PHI]], -1
+  ; CHECK-NEXT:   [[CMPLWI2:%[0-9]+]]:crrc = CMPLWI [[ADDI]], 0
+  ; CHECK-NEXT:   [[COPY3:%[0-9]+]]:crbitrc = COPY [[CMPLWI2]].sub_gt
+  ; CHECK-NEXT:   BC [[COPY3]], %bb.1
+  ; CHECK-NEXT:   B %bb.5
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.5:
+  ; CHECK-NEXT:   BLR implicit $lr, implicit $rm
+  bb.0.entry:
+
+    %0:gprc = LI 2048
+    %1:gprc_and_gprc_nor0 = LI 10
+    MTCTRloop killed %0:gprc, implicit-def dead $ctr
+
+  bb.1:
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+    B %bb.2
+
+  bb.2:
+    %2:gprc = ADDI %1:gprc_and_gprc_nor0, -1
+    %3:crrc = CMPLWI %2:gprc, 0
+    %4:crbitrc = COPY %3.sub_eq
+    BC killed %4:crbitrc, %bb.1
+    B %bb.3
+
+  bb.3:
+    %5:gprc = ADDI %1:gprc_and_gprc_nor0, -2
+    %6:crrc = CMPLWI %5:gprc, 0
+    %7:crbitrc = COPY %6.sub_gt
+    BC killed %7:crbitrc, %bb.1
+    B %bb.4
+
+  bb.4:
+
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+    %8:crbitrc = DecreaseCTRloop 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %8:crbitrc, %bb.1
+    B %bb.5
+
+  bb.5:
+
+    BLR implicit $lr, implicit $rm
+...