[PowerPC] generate CTR loops instructions after ISEL

[shchenz]

Summary

This was first raised in https://reviews.llvm.org/D81353#2078725.

We solved many bugs related to PowerPC generating CTR Loops too early and after ISEL we found there is CTR clobber in the CTR loop. So we have to exclude the CTR clobber instructions in hardware loop insertion pass one by one.

This patch implements a new way to generate the CTR loops. Now the intrinsics inserted in hardware loop pass will be mapped to pseudo instructions and these pseudo instructions will be expanded to CTR loop or normal compare+branch loop based on the result of a new added post-isel pass PPCCTRLoop.

This is the first part, including:
1: pseudo instructions for the CTR loops.
2: a new pass to expand the pseudo instructions.

One or more follow up patches will map the hardware loop intrinsics to the new added pseudo instructions and delete the CTR clobber check in hardware loop insertion pass.

[qiucf]

llvm/lib/Target/PowerPC/PPCCTRLoops.cpp

193

Nit: \n is not needed in assert message.

[shchenz]

update after verifying together with functionality patch D123366

[shchenz]

llvm/lib/Target/PowerPC/PPCCTRLoops.cpp

193

thanks!

[shchenz]

gentle ping

[shchenz]

gentle ping

[shchenz]

gentle ping

[lkail]

llvm/lib/Target/PowerPC/PPCCTRLoops.cpp

108

Can we use modifiesRegsiter here to further check RegMask clobbering?

115

Why would a Call read CTR register?

154

Can we rename Revert to something like InvalidCTRLoop? Revert sounds like we have performed part of transformation, then rollback.

158

Typo: either

llvm/test/CodeGen/PowerPC/ctrloops64.mir

240

Please add test whose loop has calls into other functions.

[lkail]

llvm/lib/Target/PowerPC/PPCCTRLoops.cpp

53

Do we have to add stats to count how many loops transformed?

178

nit: isCTRClobber(&*I, /* CheckReads */ false)

185

nit: isCTRClobber(&*I, /* CheckReads */ true)

197

nit: isCTRClobber(&MI, /* CheckReads */ true)

214

It's interesting you define Is32Bit. Most PowerPC code tend to define IsPPC64 something like that.

[shchenz]

address @lkail comments

[shchenz]

Thanks for review @lkail , updated accordingly.

llvm/lib/Target/PowerPC/PPCCTRLoops.cpp

115

CTR is a volatile register, this is not for the Call itself, it is also for the callee function. Inside the callee, we may read the CTR with mfctr or other similar instructions.

But Call may also clobber the CTR, we should check isCall before !CheckReads

154

Sure, good idea.

[lkail]

llvm/lib/Target/PowerPC/PPCCTRLoops.cpp

100

nit: Check isOutermost.

115

Normal call should be covered by checking regmask. Another thing I'm concerned about is indirect branch by bctr. We should add test to ensure bailing out if indirect branch is involved.

[shchenz]

add a new case for indirect call.

[shchenz]

Thanks for review @lkail updated.

[shchenz]

gentle ping

[shchenz]

Hi @lkail , could you please help to have another look? Thanks.

[lkail]

LGTM.

llvm/lib/Target/PowerPC/CMakeLists.txt

 add_llvm_target(PowerPCCodeGen
   GISel/PPCInstructionSelector.cpp
   PPCBoolRetToInt.cpp
   PPCAsmPrinter.cpp
   PPCBranchSelector.cpp
   PPCBranchCoalescing.cpp
   PPCCallingConv.cpp
   PPCCCState.cpp
+  PPCCTRLoops.cpp
   PPCCTRLoopsVerify.cpp
   PPCExpandAtomicPseudoInsts.cpp
   PPCHazardRecognizers.cpp
   PPCInstrInfo.cpp
   PPCISelDAGToDAG.cpp
   PPCISelLowering.cpp
   PPCEarlyReturn.cpp
   PPCFastISel.cpp

llvm/lib/Target/PowerPC/PPC.h

#endif
   FunctionPass *createPPCBranchSelectionPass();
   FunctionPass *createPPCBranchCoalescingPass();
   FunctionPass *createPPCISelDag(PPCTargetMachine &TM, CodeGenOpt::Level OL);
   FunctionPass *createPPCTLSDynamicCallPass();
   FunctionPass *createPPCBoolRetToIntPass();
   FunctionPass *createPPCExpandISELPass();
   FunctionPass *createPPCPreEmitPeepholePass();
   FunctionPass *createPPCExpandAtomicPseudoPass();
+  FunctionPass *createPPCCTRLoopsPass();
   void LowerPPCMachineInstrToMCInst(const MachineInstr *MI, MCInst &OutMI,
                                     AsmPrinter &AP);
   bool LowerPPCMachineOperandToMCOperand(const MachineOperand &MO,
                                          MCOperand &OutMO, AsmPrinter &AP);
 
 #ifndef NDEBUG
   void initializePPCCTRLoopsVerifyPass(PassRegistry&);
 #endif
   void initializePPCLoopInstrFormPrepPass(PassRegistry&);
   void initializePPCTOCRegDepsPass(PassRegistry&);
   void initializePPCEarlyReturnPass(PassRegistry&);
   void initializePPCVSXCopyPass(PassRegistry&);
   void initializePPCVSXFMAMutatePass(PassRegistry&);
   void initializePPCVSXSwapRemovalPass(PassRegistry&);
   void initializePPCReduceCRLogicalsPass(PassRegistry&);
   void initializePPCBSelPass(PassRegistry&);
   void initializePPCBranchCoalescingPass(PassRegistry&);
   void initializePPCBoolRetToIntPass(PassRegistry&);
   void initializePPCExpandISELPass(PassRegistry &);
   void initializePPCPreEmitPeepholePass(PassRegistry &);
   void initializePPCTLSDynamicCallPass(PassRegistry &);
   void initializePPCMIPeepholePass(PassRegistry&);
   void initializePPCExpandAtomicPseudoPass(PassRegistry &);
+  void initializePPCCTRLoopsPass(PassRegistry &);
 
   extern char &PPCVSXFMAMutateID;
 
   ModulePass *createPPCLowerMASSVEntriesPass();
   void initializePPCLowerMASSVEntriesPass(PassRegistry &);
   extern char &PPCLowerMASSVEntriesID;
 
   ModulePass *createPPCGenScalarMASSEntriesPass();

llvm/lib/Target/PowerPC/PPCCTRLoops.cpp

+//===-- PPCCTRLoops.cpp - Generate CTR loops ------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass generates machine instructions for the CTR loops related pseudos:
+// 1: MTCTRPseudo/DecreaseCTRPseudo
+// 2: MTCTR8Pseudo/DecreaseCTR8Pseudo
+//
+// If a CTR loop can be generated:
+// 1: MTCTRPseudo/MTCTR8Pseudo will be converted to "mtctr"
+// 2: DecreaseCTRPseudo/DecreaseCTR8Pseudo will be converted to "bdnz/bdz" and
+//    its user branch instruction can be deleted.
+//
+// If a CTR loop can not be generated due to clobber of CTR:
+// 1: MTCTRPseudo/MTCTR8Pseudo can be deleted.
+// 2: DecreaseCTRPseudo/DecreaseCTR8Pseudo will be converted to "addi -1" and
+//    a "cmplwi/cmpldi".
+//
+// This pass runs just before register allocation, because we don't want
+// register allocator to allocate register for DecreaseCTRPseudo if a CTR can be
+// generated or if a CTR loop can not be generated, we don't have any condition
+// register for the new added "cmplwi/cmpldi".
+//
+//===----------------------------------------------------------------------===//
+
+#include "PPC.h"
+#include "PPCInstrInfo.h"
+#include "PPCSubtarget.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineOperand.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Register.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/PassRegistry.h"
+#include "llvm/Support/CodeGen.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <cassert>
+
+using namespace llvm;
+
+#define DEBUG_TYPE "ppc-ctrloops"
+
+STATISTIC(NumCTRLoops, "Number of CTR loops generated");
+STATISTIC(NumNormalLoops, "Number of normal compare + branch loops generated");
+
+namespace {
+class PPCCTRLoops : public MachineFunctionPass {
+public:
+  static char ID;
+
+  PPCCTRLoops() : MachineFunctionPass(ID) {
+    initializePPCCTRLoopsPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<MachineLoopInfo>();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+private:
+  const PPCInstrInfo *TII = nullptr;
+  MachineRegisterInfo *MRI = nullptr;
+
+  bool processLoop(MachineLoop *ML);
+  bool isCTRClobber(MachineInstr *MI, bool CheckReads) const;
+  void expandNormalLoops(MachineLoop *ML, MachineInstr *Start,
+                         MachineInstr *Dec);
+  void expandCTRLoops(MachineLoop *ML, MachineInstr *Start, MachineInstr *Dec);
+};
+} // namespace
+
+char PPCCTRLoops::ID = 0;
+
+INITIALIZE_PASS_BEGIN(PPCCTRLoops, DEBUG_TYPE, "PowerPC CTR loops generation",
+                      false, false)
+INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_END(PPCCTRLoops, DEBUG_TYPE, "PowerPC CTR loops generation",
+                    false, false)
+
+FunctionPass *llvm::createPPCCTRLoopsPass() { return new PPCCTRLoops(); }
+
+bool PPCCTRLoops::runOnMachineFunction(MachineFunction &MF) {
+  bool Changed = false;
+
+  auto &MLI = getAnalysis<MachineLoopInfo>();
+  TII = static_cast<const PPCInstrInfo *>(MF.getSubtarget().getInstrInfo());
+  MRI = &MF.getRegInfo();
+
+  for (auto ML : MLI) {
+    if (ML->isOutermost())
+      Changed |= processLoop(ML);
+  }
+
+  return Changed;
+}
+
+bool PPCCTRLoops::isCTRClobber(MachineInstr *MI, bool CheckReads) const {
+  if ((MI->modifiesRegister(PPC::CTR) && !MI->registerDefIsDead(PPC::CTR)) ||
+      (MI->modifiesRegister(PPC::CTR8) && !MI->registerDefIsDead(PPC::CTR8)))
+    return true;
+
+  if (MI->getDesc().isCall())
+    return true;
+
+  if (!CheckReads)
+    return false;
+
+  // We define the CTR in the loop preheader, so if there is any CTR reader in
+  // the loop, we also can not use CTR loop form.
+  if (MI->readsRegister(PPC::CTR) || MI->readsRegister(PPC::CTR8))
+    return true;
+
+  return false;
+}
+
+bool PPCCTRLoops::processLoop(MachineLoop *ML) {
+  bool Changed = false;
+
+  // Align with HardwareLoop pass, process inner loops first.
+  for (auto I = ML->begin(), E = ML->end(); I != E; ++I)
+    Changed |= processLoop(*I);
+
+  // If any inner loop is changed, outter loop must be without hardware loop
+  // intrinsics.
+  if (Changed)
+    return true;
+
+  auto IsLoopStart = [](MachineInstr &MI) {
+    return MI.getOpcode() == PPC::MTCTRPseudo ||
+           MI.getOpcode() == PPC::MTCTR8Pseudo;
+  };
+
+  auto SearchForStart =
+      [&IsLoopStart](MachineBasicBlock *MBB) -> MachineInstr * {
+    for (auto &MI : *MBB) {
+      if (IsLoopStart(MI))
+        return &MI;
+    }
+    return nullptr;
+  };
+
+  MachineInstr *Start = nullptr;
+  MachineInstr *Dec = nullptr;
+  bool InvalidCTRLoop = false;
+
+  MachineBasicBlock *Preheader = ML->getLoopPreheader();
+  // If there is no preheader for this loop, there must be no MTCTRPseudo
+  // either.
+  if (!Preheader)
+    return false;
+
+  Start = SearchForStart(Preheader);
+  // This is not a CTR loop candidate.
+  if (!Start)
+    return false;
+
+  // If CTR is live to the preheader, we can not redefine the CTR register.
+  if (Preheader->isLiveIn(PPC::CTR) || Preheader->isLiveIn(PPC::CTR8))
+    InvalidCTRLoop = true;
+
+  // Make sure there is also no CTR clobber in the block preheader between the
+  // begin and MTCTR.
+  for (MachineBasicBlock::reverse_instr_iterator I =
+           std::next(Start->getReverseIterator());
+       I != Preheader->instr_rend(); ++I)
+    // Only check the definitions of CTR. If there is non-dead definition for
+    // the CTR, we conservatively don't generate a CTR loop.
+    if (isCTRClobber(&*I, /* CheckReads */ false)) {
+      InvalidCTRLoop = true;
+      break;
+    }
+
+  // Make sure there is also no CTR clobber/user in the block preheader between
+  // MTCTR and the end.
+  for (MachineBasicBlock::instr_iterator I = std::next(Start->getIterator());
+       I != Preheader->instr_end(); ++I)
+    if (isCTRClobber(&*I, /* CheckReads */ true)) {
+      InvalidCTRLoop = true;
+      break;
+    }
+
+  // Find the CTR loop components and decide whether or not to fall back to a
+  // normal loop.
+  for (auto *MBB : reverse(ML->getBlocks())) {
+    for (auto &MI : *MBB) {
+      if (MI.getOpcode() == PPC::DecreaseCTRPseudo ||
+          MI.getOpcode() == PPC::DecreaseCTR8Pseudo)
+        Dec = &MI;
+      else if (!InvalidCTRLoop)
+        // If any instruction clobber CTR, then we can not generate a CTR loop.
+        InvalidCTRLoop |= isCTRClobber(&MI, /* CheckReads */ true);
+    }
+    if (Dec && InvalidCTRLoop)
+      break;
+  }
+
+  assert(Dec && "CTR loop is not complete!");
+
+  if (InvalidCTRLoop) {
+    expandNormalLoops(ML, Start, Dec);
+    ++NumNormalLoops;
+  }
+  else {
+    expandCTRLoops(ML, Start, Dec);
+    ++NumCTRLoops;
+  }
+  return true;
+}
+
+void PPCCTRLoops::expandNormalLoops(MachineLoop *ML, MachineInstr *Start,
+                                    MachineInstr *Dec) {
+  bool Is64Bit =
+      Start->getParent()->getParent()->getSubtarget<PPCSubtarget>().isPPC64();
+
+  MachineBasicBlock *Preheader = Start->getParent();
+  MachineBasicBlock *Exiting = Dec->getParent();
+  assert((Preheader && Exiting) &&
+         "Preheader and exiting should exist for CTR loop!");
+
+  assert(Dec->getOperand(1).getImm() == 1 &&
+         "Loop decrement stride must be 1");
+
+  unsigned ADDIOpcode = Is64Bit ? PPC::ADDI8 : PPC::ADDI;
+  unsigned CMPOpcode = Is64Bit ? PPC::CMPLDI : PPC::CMPLWI;
+
+  Register PHIDef =
+      MRI->createVirtualRegister(Is64Bit ? &PPC::G8RC_and_G8RC_NOX0RegClass
+                                         : &PPC::GPRC_and_GPRC_NOR0RegClass);
+
+  Start->getParent()->getParent()->getProperties().reset(
+      MachineFunctionProperties::Property::NoPHIs);
+
+  // Generate "PHI" in the header block.
+  auto PHIMIB = BuildMI(*ML->getHeader(), ML->getHeader()->getFirstNonPHI(),
+                        DebugLoc(), TII->get(TargetOpcode::PHI), PHIDef);
+  PHIMIB.addReg(Start->getOperand(0).getReg()).addMBB(Preheader);
+
+  Register ADDIDef =
+      MRI->createVirtualRegister(Is64Bit ? &PPC::G8RC_and_G8RC_NOX0RegClass
+                                         : &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
+    // 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!");
+    PHIMIB.addReg(ADDIDef).addMBB(Exiting);
+  } 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) &&
+               "Loop's header in-loop predecessor is not loop latch!");
+        PHIMIB.addReg(ADDIDef).addMBB(P);
+      } else
+        assert(P == Preheader &&
+               "CTR loop should not be generated for irreducible loop!");
+    }
+  }
+
+  // Generate the compare in the exiting block.
+  Register CMPDef = MRI->createVirtualRegister(&PPC::CRRCRegClass);
+  auto CMPMIB =
+      BuildMI(*Exiting, Dec, Dec->getDebugLoc(), TII->get(CMPOpcode), CMPDef)
+          .addReg(ADDIDef)
+          .addImm(0);
+
+  BuildMI(*Exiting, Dec, Dec->getDebugLoc(), TII->get(TargetOpcode::COPY),
+          Dec->getOperand(0).getReg())
+      .addReg(CMPMIB->getOperand(0).getReg(), 0, PPC::sub_gt);
+
+  // Remove the pseudo instructions.
+  Start->eraseFromParent();
+  Dec->eraseFromParent();
+}
+
+void PPCCTRLoops::expandCTRLoops(MachineLoop *ML, MachineInstr *Start,
+                                 MachineInstr *Dec) {
+  bool Is64Bit =
+      Start->getParent()->getParent()->getSubtarget<PPCSubtarget>().isPPC64();
+
+  MachineBasicBlock *Preheader = Start->getParent();
+  MachineBasicBlock *Exiting = Dec->getParent();
+  assert((Preheader && Exiting) &&
+         "Preheader and exiting should exist for CTR loop!");
+
+  assert(Dec->getOperand(1).getImm() == 1 && "Loop decrement must be 1!");
+
+  unsigned BDNZOpcode = Is64Bit ? PPC::BDNZ8 : PPC::BDNZ;
+  unsigned BDZOpcode = Is64Bit ? PPC::BDZ8 : PPC::BDZ;
+  auto BrInstr = MRI->use_instr_begin(Dec->getOperand(0).getReg());
+  assert(MRI->hasOneUse(Dec->getOperand(0).getReg()) &&
+         "There should be only one user for loop decrement pseudo!");
+
+  unsigned Opcode = 0;
+  switch (BrInstr->getOpcode()) {
+  case PPC::BC:
+    Opcode = BDNZOpcode;
+    (void) ML;
+    assert(ML->contains(BrInstr->getOperand(1).getMBB()) &&
+           "Invalid ctr loop!");
+    break;
+  case PPC::BCn:
+    Opcode = BDZOpcode;
+    assert(!ML->contains(BrInstr->getOperand(1).getMBB()) &&
+           "Invalid ctr loop!");
+    break;
+  default:
+    llvm_unreachable("Unhandled branch user for DecreaseCTRloop.");
+  }
+
+  unsigned MTCTROpcode = Is64Bit ? PPC::MTCTR8 : PPC::MTCTR;
+
+  // Generate "mtctr" in the loop preheader.
+  BuildMI(*Preheader, Start, Start->getDebugLoc(), TII->get(MTCTROpcode))
+      .addReg(Start->getOperand(0).getReg());
+
+  // Generate "bdnz/bdz" in the exiting block just before the terminator.
+  BuildMI(*Exiting, &*BrInstr, BrInstr->getDebugLoc(), TII->get(Opcode))
+      .addMBB(BrInstr->getOperand(1).getMBB());
+
+  // Remove the pseudo instructions.
+  Start->eraseFromParent();
+  BrInstr->eraseFromParent();
+  Dec->eraseFromParent();
+}

llvm/lib/Target/PowerPC/PPCInstr64Bit.td

 }
 let hasSideEffects = 1, Defs = [CTR8] in {
 let Pattern = [(int_set_loop_iterations i64:$rS)] in
 def MTCTR8loop : XFXForm_7_ext<31, 467, 9, (outs), (ins g8rc:$rS),
                                "mtctr $rS", IIC_SprMTSPR>,
                  PPC970_DGroup_First, PPC970_Unit_FXU;
 }
 
+
+let hasSideEffects = 1, Defs = [CTR8] in
+def MTCTR8Pseudo : PPCEmitTimePseudo<(outs), (ins g8rc:$rS), "#MTCTR8Pseudo", []>;
+
+let hasSideEffects = 1, Uses = [CTR8], Defs = [CTR8] in
+def DecreaseCTR8Pseudo : PPCEmitTimePseudo<(outs crbitrc:$rT), (ins i64imm:$stride),
+                                          "#DecreaseCTR8Pseudo", []>;
+
 let Pattern = [(set i64:$rT, readcyclecounter)] in
 def MFTB8 : XFXForm_1_ext<31, 339, 268, (outs g8rc:$rT), (ins),
                           "mfspr $rT, 268", IIC_SprMFTB>,
             PPC970_DGroup_First, PPC970_Unit_FXU;
 // Note that encoding mftb using mfspr is now the preferred form,
 // and has been since at least ISA v2.03. The mftb instruction has
 // now been phased out. Using mfspr, however, is known not to work on
 // the POWER3.

llvm/lib/Target/PowerPC/PPCInstrInfo.td

 }
 let hasSideEffects = 1, isCodeGenOnly = 1, Defs = [CTR] in {
 let Pattern = [(int_set_loop_iterations i32:$rS)] in
 def MTCTRloop : XFXForm_7_ext<31, 467, 9, (outs), (ins gprc:$rS),
                               "mtctr $rS", IIC_SprMTSPR>,
                 PPC970_DGroup_First, PPC970_Unit_FXU;
 }
 
+let hasSideEffects = 1, Defs = [CTR] in
+def MTCTRPseudo : PPCEmitTimePseudo<(outs), (ins gprc:$rS), "#MTCTRPseudo", []>;
+
+let hasSideEffects = 1, Uses = [CTR], Defs = [CTR] in
+def DecreaseCTRPseudo : PPCEmitTimePseudo<(outs crbitrc:$rT), (ins i32imm:$stride),
+                                          "#DecreaseCTRPseudo", []>;
+
 let hasSideEffects = 0 in {
 let Defs = [LR] in {
 def MTLR  : XFXForm_7_ext<31, 467, 8, (outs), (ins gprc:$rS),
                           "mtlr $rS", IIC_SprMTSPR>,
             PPC970_DGroup_First, PPC970_Unit_FXU;
 }
 let Uses = [LR] in {
 def MFLR  : XFXForm_1_ext<31, 339, 8, (outs gprc:$rT), (ins),

llvm/lib/Target/PowerPC/PPCTargetMachine.cpp

#endif
   initializePPCExpandISELPass(PR);
   initializePPCPreEmitPeepholePass(PR);
   initializePPCTLSDynamicCallPass(PR);
   initializePPCMIPeepholePass(PR);
   initializePPCLowerMASSVEntriesPass(PR);
   initializePPCGenScalarMASSEntriesPass(PR);
   initializePPCExpandAtomicPseudoPass(PR);
   initializeGlobalISel(PR);
+  initializePPCCTRLoopsPass(PR);
 }
 
 static bool isLittleEndianTriple(const Triple &T) {
   return T.getArch() == Triple::ppc64le || T.getArch() == Triple::ppcle;
 }
 
 /// Return the datalayout string of a subtarget.
 static std::string getDataLayoutString(const Triple &T) {
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:       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/ctrloops32.mir

+# RUN: llc -ppc-asm-full-reg-names -mtriple=powerpc-ibm-aix-xcoff \
+# RUN:   -run-pass=ppc-ctrloops %s -o - -verify-machineinstrs | FileCheck %s 
+
+---
+name:            test_success1
+# CHECK: test_success1
+
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:gprc = LI 2048
+    ; CHECK: MTCTR
+    ; CHECK: BDNZ
+    ; CHECK-NOT: ADDI
+    ; CHECK-NOT: CMPLWI
+    ; CHECK-NOT: BC
+    MTCTRPseudo killed %0:gprc, implicit-def dead $ctr
+
+  bb.1:
+
+    %1:crbitrc = DecreaseCTRPseudo 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %1:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR implicit $lr, implicit $rm
+...
+---
+name:            test_fail_clobber
+# CHECK: test_fail_clobber
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:gprc = LI 2048
+    ; CHECK-NOT: MTCTR
+    ; CHECK-NOT: BDNZ
+    ; CHECK: ADDI
+    ; CHECK: CMPLWI
+    ; CHECK: BC
+    MTCTRPseudo killed %0:gprc, implicit-def dead $ctr
+
+  bb.1:
+
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+    %1:crbitrc = DecreaseCTRPseudo 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %1:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR implicit $lr, implicit $rm
+...
+---
+name:            test_fail_use_in_loop
+# CHECK: test_fail_use_in_loop
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:gprc = LI 2048
+    ; CHECK-NOT: MTCTR
+    ; CHECK-NOT: BDNZ
+    ; CHECK: ADDI
+    ; CHECK: CMPLWI
+    ; CHECK: BC
+    MTCTRPseudo killed %0:gprc, implicit-def dead $ctr
+
+  bb.1:
+
+    %1:gprc = MFCTR implicit $ctr
+    %2:crbitrc = DecreaseCTRPseudo 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %2:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR implicit $lr, implicit $rm
+...
+---
+name:            test_fail_call_in_loop
+# CHECK: test_fail_call_in_loop
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:gprc = LI 2048
+    ; CHECK-NOT: MTCTR
+    ; CHECK-NOT: BDNZ
+    ; CHECK: ADDI
+    ; CHECK: CMPLWI
+    ; CHECK: BC
+    MTCTRPseudo killed %0:gprc, implicit-def dead $ctr
+
+  bb.1:
+
+    BL @test_fail_use_in_loop, csr_aix32, implicit-def dead $lr, implicit $rm
+    %1:crbitrc = DecreaseCTRPseudo 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %1:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR implicit $lr, implicit $rm
+...
+---
+name:            test_fail_indirect_call_in_loop
+# CHECK: test_fail_indirect_call_in_loop
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+   liveins: $r3, $r4
+
+    %0:gprc = LI 2048
+    ; CHECK-NOT: MTCTR
+    ; CHECK-NOT: BDNZ
+    ; CHECK: ADDI
+    ; CHECK: CMPLWI
+    ; CHECK: BC
+    renamable %1:crrc = CMPLW killed renamable $r3, killed renamable $r4
+    renamable %2:crbitrc = COPY %1.sub_gt
+    MTLR %0:gprc, implicit-def $lr
+    MTCTRPseudo %0:gprc, implicit-def dead $ctr
+
+  bb.1:
+
+    BCLRL renamable %2, implicit $lr, implicit $rm
+    %3:crbitrc = DecreaseCTRPseudo 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %3:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR implicit $lr, implicit $rm
+...
+---
+name:            test_fail_livein_preheader
+# CHECK: test_fail_livein_preheader
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    liveins: $ctr
+
+    %0:gprc = LI 2048
+    ; CHECK-NOT: MTCTR
+    ; CHECK-NOT: BDNZ
+    ; CHECK: ADDI
+    ; CHECK: CMPLWI
+    ; CHECK: BC
+    MTCTRPseudo killed %0:gprc, implicit-def dead $ctr
+
+  bb.1:
+
+    %1:crbitrc = DecreaseCTRPseudo 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %1:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR implicit $lr, implicit $rm
+...
+---
+name:            test_fail_def_preheader
+# CHECK: test_fail_def_preheader
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+    %0:gprc = LI 2048
+    ; CHECK2-NOT: MTCTR
+    ; CHECK-NOT: BDNZ
+    ; CHECK: ADDI
+    ; CHECK: CMPLWI
+    ; CHECK: BC
+    MTCTRPseudo killed %0:gprc, implicit-def dead $ctr
+
+  bb.1:
+
+    %1:crbitrc = DecreaseCTRPseudo 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %1:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR implicit $lr, implicit $rm
+...
+---
+name:            test_success_only_use_preheader
+# CHECK: test_success_only_use_preheader
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:gprc = MFCTR implicit $ctr
+    %1:gprc = LI 2048
+    ; CHECK: MTCTR
+    ; CHECK: BDNZ
+    ; CHECK-NOT: ADDI
+    ; CHECK-NOT: CMPLWI
+    ; CHECK-NOT: BC
+    MTCTRPseudo killed %1:gprc, implicit-def dead $ctr
+
+  bb.1:
+
+    %2:crbitrc = DecreaseCTRPseudo 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %2:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR implicit $lr, implicit $rm
+...
+---
+name:            test_fail_use_after_mtctr
+# CHECK: test_fail_use_after_mtctr
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:gprc = LI 2048
+    ; CHECK-NOT: MTCTR
+    ; CHECK-NOT: BDNZ
+    ; CHECK: ADDI
+    ; CHECK: CMPLWI
+    ; CHECK: BC
+    MTCTRPseudo killed %0:gprc, implicit-def dead $ctr
+    %1:gprc = MFCTR implicit $ctr
+
+  bb.1:
+
+    %2:crbitrc = DecreaseCTRPseudo 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %2:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR implicit $lr, implicit $rm
+...
+---
+name:            test_fail_def_after_mtctr
+# CHECK: test_fail_def_after_mtctr
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:gprc = LI 2048
+    ; CHECK-NOT: MTCTR
+    ; CHECK-NOT: BDNZ
+    ; CHECK: ADDI
+    ; CHECK: CMPLWI
+    ; CHECK: BC
+    MTCTRPseudo killed %0:gprc, implicit-def dead $ctr
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+
+  bb.1:
+
+    %2:crbitrc = DecreaseCTRPseudo 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %2:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR implicit $lr, implicit $rm
+...
+---
+name:            test_success_def_after_loop
+# CHECK: test_success_def_after_loop
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:gprc = LI 2048
+    ; CHECK: MTCTR
+    ; CHECK: BDNZ
+    ; CHECK-NOT: ADDI
+    ; CHECK-NOT: CMPLWI
+    ; CHECK-NOT: BC
+    MTCTRPseudo killed %0:gprc, implicit-def dead $ctr
+
+  bb.1:
+
+    %2:crbitrc = DecreaseCTRPseudo 1, implicit-def dead $ctr, implicit $ctr
+    BC killed %2:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr
+
+    BLR implicit $lr, implicit $rm
+...

llvm/test/CodeGen/PowerPC/ctrloops64.mir

+# RUN: llc -ppc-asm-full-reg-names -mtriple=powerpc64le-unknown-linux-gnu \
+# RUN:   -run-pass=ppc-ctrloops %s -o - -verify-machineinstrs | FileCheck %s
+# RUN: llc -ppc-asm-full-reg-names -mtriple=powerpc64-ibm-aix-xcoff \
+# RUN:   -run-pass=ppc-ctrloops %s -o - -verify-machineinstrs | FileCheck %s
+
+---
+name:            test_success1
+# CHECK: test_success1
+
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:g8rc = LI8 2048
+    ; CHECK: MTCTR8
+    ; CHECK: BDNZ8
+    ; CHECK-NOT: ADDI8
+    ; CHECK-NOT: CMPLDI
+    ; CHECK-NOT: BC
+    MTCTR8Pseudo killed %0:g8rc, implicit-def dead $ctr8
+
+  bb.1:
+
+    %1:crbitrc = DecreaseCTR8Pseudo 1, implicit-def dead $ctr8, implicit $ctr8
+    BC killed %1:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name:            test_fail_clobber
+# CHECK: test_fail_clobber
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:g8rc = LI8 2048
+    ; CHECK-NOT: MTCTR8
+    ; CHECK-NOT: BDNZ8
+    ; CHECK: ADDI8
+    ; CHECK: CMPLDI
+    ; CHECK: BC
+    MTCTR8Pseudo killed %0:g8rc, implicit-def dead $ctr8
+
+  bb.1:
+
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr8
+    %1:crbitrc = DecreaseCTR8Pseudo 1, implicit-def dead $ctr8, implicit $ctr8
+    BC killed %1:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name:            test_fail_use_in_loop
+# CHECK: test_fail_use_in_loop
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:g8rc = LI8 2048
+    ; CHECK-NOT: MTCTR8
+    ; CHECK-NOT: BDNZ8
+    ; CHECK: ADDI8
+    ; CHECK: CMPLDI
+    ; CHECK: BC
+    MTCTR8Pseudo killed %0:g8rc, implicit-def dead $ctr8
+
+  bb.1:
+
+    %1:g8rc = MFCTR8 implicit $ctr8
+    %2:crbitrc = DecreaseCTR8Pseudo 1, implicit-def dead $ctr8, implicit $ctr8
+    BC killed %2:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name:            test_fail_call_in_loop
+# CHECK: test_fail_call_in_loop
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:g8rc = LI8 2048
+    ; CHECK-NOT: MTCTR8
+    ; CHECK-NOT: BDNZ8
+    ; CHECK: ADDI8
+    ; CHECK: CMPLDI
+    ; CHECK: BC
+    MTCTR8Pseudo killed %0:g8rc, implicit-def dead $ctr8
+
+  bb.1:
+
+    BL8 @test_fail_use_in_loop, csr_ppc64, implicit-def dead $lr8, implicit $rm
+    %1:crbitrc = DecreaseCTR8Pseudo 1, implicit-def dead $ctr8, implicit $ctr8
+    BC killed %1:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name:            test_fail_indirect_call_in_loop
+# CHECK: test_fail_indirect_call_in_loop
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    liveins: $x3, $x4
+
+    %0:g8rc = LI8 2048
+    ; CHECK-NOT: MTCTR8
+    ; CHECK-NOT: BDNZ8
+    ; CHECK: ADDI8
+    ; CHECK: CMPLDI
+    ; CHECK: BC
+    renamable %1:crrc = CMPLD killed renamable $x3, killed renamable $x4
+    renamable %2:crbitrc = COPY %1.sub_gt
+    MTLR8 %0:g8rc, implicit-def $lr8
+    MTCTR8Pseudo killed %0:g8rc, implicit-def dead $ctr8
+
+  bb.1:
+
+    BCLRL renamable %2, implicit $lr, implicit $rm
+    %3:crbitrc = DecreaseCTR8Pseudo 1, implicit-def dead $ctr8, implicit $ctr8
+    BC killed %3:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name:            test_fail_livein_preheader
+# CHECK: test_fail_livein_preheader
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    liveins: $ctr8
+
+    %0:g8rc = LI8 2048
+    ; CHECK-NOT: MTCTR8
+    ; CHECK-NOT: BDNZ8
+    ; CHECK: ADDI8
+    ; CHECK: CMPLDI
+    ; CHECK: BC
+    MTCTR8Pseudo killed %0:g8rc, implicit-def dead $ctr8
+
+  bb.1:
+
+    %1:crbitrc = DecreaseCTR8Pseudo 1, implicit-def dead $ctr8, implicit $ctr8
+    BC killed %1:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name:            test_fail_def_preheader
+# CHECK: test_fail_def_preheader
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr8
+    %0:g8rc = LI8 2048
+    ; CHECK-NOT: MTCTR8
+    ; CHECK-NOT: BDNZ8
+    ; CHECK: ADDI8
+    ; CHECK: CMPLDI
+    ; CHECK: BC
+    MTCTR8Pseudo killed %0:g8rc, implicit-def dead $ctr8
+
+  bb.1:
+
+    %1:crbitrc = DecreaseCTR8Pseudo 1, implicit-def dead $ctr8, implicit $ctr8
+    BC killed %1:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name:            test_success_only_use_preheader
+# CHECK: test_success_only_use_preheader
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:g8rc = MFCTR8 implicit $ctr8
+    %1:g8rc = LI8 2048
+    ; CHECK: MTCTR8
+    ; CHECK: BDNZ8
+    ; CHECK-NOT: ADDI8
+    ; CHECK-NOT: CMPLDI
+    ; CHECK-NOT: BC
+    MTCTR8Pseudo killed %1:g8rc, implicit-def dead $ctr8
+
+  bb.1:
+
+    %2:crbitrc = DecreaseCTR8Pseudo 1, implicit-def dead $ctr8, implicit $ctr8
+    BC killed %2:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name:            test_fail_use_after_mtctr
+# CHECK: test_fail_use_after_mtctr
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:g8rc = LI8 2048
+    ; CHECK-NOT: MTCTR8
+    ; CHECK-NOT: BDNZ8
+    ; CHECK: ADDI8
+    ; CHECK: CMPLDI
+    ; CHECK: BC
+    MTCTR8Pseudo killed %0:g8rc, implicit-def dead $ctr8
+    %1:g8rc = MFCTR8 implicit $ctr8
+
+  bb.1:
+
+    %2:crbitrc = DecreaseCTR8Pseudo 1, implicit-def dead $ctr8, implicit $ctr8
+    BC killed %2:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name:            test_fail_def_after_mtctr
+# CHECK: test_fail_def_after_mtctr
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:g8rc = LI8 2048
+    ; CHECK-NOT: MTCTR8
+    ; CHECK-NOT: BDNZ8
+    ; CHECK: ADDI8
+    ; CHECK: CMPLDI
+    ; CHECK: BC
+    MTCTR8Pseudo killed %0:g8rc, implicit-def dead $ctr8
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr8
+
+  bb.1:
+
+    %2:crbitrc = DecreaseCTR8Pseudo 1, implicit-def dead $ctr8, implicit $ctr8
+    BC killed %2:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name:            test_success_def_after_loop
+# CHECK: test_success_def_after_loop
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+
+    %0:g8rc = LI8 2048
+    ; CHECK: MTCTR8
+    ; CHECK: BDNZ8
+    ; CHECK-NOT: ADDI8
+    ; CHECK-NOT: CMPLDI
+    ; CHECK-NOT: BC
+    MTCTR8Pseudo killed %0:g8rc, implicit-def dead $ctr8
+
+  bb.1:
+
+    %2:crbitrc = DecreaseCTR8Pseudo 1, implicit-def dead $ctr8, implicit $ctr8
+    BC killed %2:crbitrc, %bb.1
+    B %bb.2
+
+  bb.2:
+    INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def early-clobber $ctr8
+
+    BLR8 implicit $lr8, implicit $rm
+...