[PowerPC] move ctrloop pass before tail duplication

[shchenz]

Summary

Tail duplication may modify the loop to a "non-canonical" form that CTR Loop pass can not
recognize. We fixed one issue in D135846. And we found in some other case, the loop is
changed to irreducible form. It is hard to fix this case in CTR loop pass, instead we reorder the
CTR loop pass before tail duplication pass and just after finalize-isel pass to avoid any unexpected
change to the loop form.

This patch:
1: reverted the change in d135846
2: move the ctrloop pass before tail duplication

[lkail]

llvm/lib/Target/PowerPC/PPCTargetMachine.cpp

505

IIUC, PPCCTRLoops should be enabled iff HardwareLoops is enabled. We'd better put the switch-on logic into separate function, and query this function when adding PPCCTRLoops and HardwareLoopsPass(and maybe PPCCTRLoopsVerify together) to the pipeline.

[shchenz]

llvm/lib/Target/PowerPC/PPCTargetMachine.cpp

505

yes, you are right. Hardware Loops pass is needed for other two backend CTR loop passes. Currently they are all controlled by DisableCTRLoops flag which is defined in PPCTargetMachine.cpp. If we want to add the getOptLevel() as another guard that can be shared, we have to define a function in class PPCPassConfig. But I feel it is not making sense to do so as PPCPassConfig currently should only care about some "big" functionality, not a single pass...

To me, for all these three passes, querying the common DisableCTRLoops flag is enough. What do you think?

[lkail]

llvm/lib/Target/PowerPC/PPCTargetMachine.cpp

505

My thought is based on maintenance in the future. Another approach might be adding a O0-pipeline.ll test case to ensure consistency, i.e., HardwareLoop and PPCCTRLoop appear in O3-pipeline.ll simultaneously and none of them appear in O0-pipeline.

[shchenz]

llvm/lib/Target/PowerPC/PPCTargetMachine.cpp

505

https://reviews.llvm.org/D138973 is created, so any pass that is wrongly added to O0-pipeline should be detected by O0 pipeline test now.

[lkail]

LGTM. Though there might be some pseudo instruction expansion changed the CFG, they are not breaking assumptions PPCCTRLoop made.

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)) {
-    // 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
+    // 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.
-    // 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(llvm::is_contained(ML->getHeader()->predecessors(), Exiting) &&
-           "Loop latch is not loop header predecessor!");
-    assert(llvm::is_contained(ML->getHeader()->predecessors(), Preheader) &&
-           "Loop preheader is not loop header predecessor!");
-
+    assert(ML->getHeader()->pred_size() == 2 &&
+           "Loop header predecessor is not right!");
     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/lib/Target/PowerPC/PPCTargetMachine.cpp

if (!DisableCTRLoops && getOptLevel() != CodeGenOpt::None)
     addPass(createPPCCTRLoopsVerify());
 #endif
 
   addPass(createPPCVSXCopyPass());
   return false;
 }
 
 void PPCPassConfig::addMachineSSAOptimization() {
+  // Run CTR loops pass before any cfg modification pass to prevent the
+  // canonical form of hardware loop from being destroied.
+  if (!DisableCTRLoops && getOptLevel() != CodeGenOpt::None)
+    addPass(createPPCCTRLoopsPass());
+
   // PPCBranchCoalescingPass need to be done before machine sinking
   // since it merges empty blocks.
   if (EnableBranchCoalescing && getOptLevel() != CodeGenOpt::None)
     addPass(createPPCBranchCoalescingPass());
   TargetPassConfig::addMachineSSAOptimization();
   // For little endian, remove where possible the vector swap instructions
   // introduced at code generation to normalize vector element order.
   if (TM->getTargetTriple().getArch() == Triple::ppc64le &&
if (getPPCTargetMachine().isPositionIndependent()) {
     // LiveVariables. This (unnecessary) dependency has been removed now,
     // however a stage-2 clang build fails without LiveVariables computed here.
     addPass(&LiveVariablesID);
     addPass(createPPCTLSDynamicCallPass());
   }
   if (EnableExtraTOCRegDeps)
     addPass(createPPCTOCRegDepsPass());
 
-  // Run CTR loops pass before MachinePipeliner pass.
-  // MachinePipeliner will pipeline all instructions before the terminator, but
-  // we don't want DecreaseCTRPseudo to be pipelined.
-  // Note we may lose some MachinePipeliner opportunities if we run CTR loops
-  // generation pass before MachinePipeliner and the loop is converted back to
-  // a normal loop. We can revisit this later for running PPCCTRLoops after
-  // MachinePipeliner and handling DecreaseCTRPseudo in MachinePipeliner pass.
-  if (getOptLevel() != CodeGenOpt::None)
-    addPass(createPPCCTRLoopsPass());
-
   if (getOptLevel() != CodeGenOpt::None)
     addPass(&MachinePipelinerID);
 }
 
 void PPCPassConfig::addPreSched2() {
   if (getOptLevel() != CodeGenOpt::None)
     addPass(&IfConverterID);
 }

llvm/test/CodeGen/PowerPC/O3-pipeline.ll

 ; CHECK-NEXT:       Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       PowerPC DAG->DAG Pattern Instruction Selection
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       PowerPC CTR Loops Verify
 ; CHECK-NEXT:       PowerPC VSX Copy Legalization
 ; CHECK-NEXT:       Finalize ISel and expand pseudo-instructions
+; CHECK-NEXT:       MachineDominator Tree Construction
+; CHECK-NEXT:       Machine Natural Loop Construction
+; CHECK-NEXT:       PowerPC CTR loops generation
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Early Tail Duplication
 ; CHECK-NEXT:       Optimize machine instruction PHIs
 ; CHECK-NEXT:       Slot index numbering
 ; CHECK-NEXT:       Merge disjoint stack slots
 ; CHECK-NEXT:       Local Stack Slot Allocation
 ; CHECK-NEXT:       Remove dead machine instructions
 ; CHECK-NEXT:       MachineDominator Tree Construction

 ; CHECK-NEXT:       Remove unreachable machine basic blocks
 ; CHECK-NEXT:       Live Variable Analysis
 ; CHECK-NEXT:       Slot index numbering
 ; CHECK-NEXT:       Live Interval Analysis
 ; CHECK-NEXT:       PowerPC TLS Dynamic Call Fixup
 ; CHECK-NEXT:       PowerPC TOC Register Dependencies
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Natural Loop Construction
-; CHECK-NEXT:       PowerPC CTR loops generation
-; CHECK-NEXT:       MachineDominator Tree Construction
-; CHECK-NEXT:       Machine Natural Loop Construction
 ; CHECK-NEXT:       Slot index numbering
 ; CHECK-NEXT:       Live Interval Analysis
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Modulo Software Pipelining
 ; CHECK-NEXT:       Detect Dead Lanes
 ; CHECK-NEXT:       Process Implicit Definitions
 ; CHECK-NEXT:       Remove unreachable machine basic blocks

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
-...