lib/Target/PowerPC/PPCCTRLoops.cpp

   1 //===-- PPCCTRLoops.cpp - Identify and generate CTR loops -----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass identifies loops where we can generate the PPC branch instructions
  11 // that decrement and test the count register (CTR) (bdnz and friends).
  12 // This pass is based on the HexagonHardwareLoops pass.
  13 //
  14 // The pattern that defines the induction variable can changed depending on
  15 // prior optimizations.  For example, the IndVarSimplify phase run by 'opt'
  16 // normalizes induction variables, and the Loop Strength Reduction pass
  17 // run by 'llc' may also make changes to the induction variable.
  18 // The pattern detected by this phase is due to running Strength Reduction.
  19 //
  20 // Criteria for CTR loops:
  21 //  - Countable loops (w/ ind. var for a trip count)
  22 //  - Assumes loops are normalized by IndVarSimplify
  23 //  - Try inner-most loops first
  24 //  - No nested CTR loops.
  25 //  - No function calls in loops.
  26 //
  27 //  Note: As with unconverted loops, PPCBranchSelector must be run after this
  28 //  pass in order to convert long-displacement jumps into jump pairs.
  29 //
  30 //===----------------------------------------------------------------------===//
  31
  32 #define DEBUG_TYPE "ctrloops"
  33 #include "PPC.h"
  34 #include "PPCTargetMachine.h"
  35 #include "llvm/Constants.h"
  36 #include "llvm/PassSupport.h"
  37 #include "llvm/ADT/DenseMap.h"
  38 #include "llvm/ADT/Statistic.h"
  39 #include "llvm/CodeGen/Passes.h"
  40 #include "llvm/CodeGen/MachineDominators.h"
  41 #include "llvm/CodeGen/MachineFunction.h"
  42 #include "llvm/CodeGen/MachineFunctionPass.h"
  43 #include "llvm/CodeGen/MachineInstrBuilder.h"
  44 #include "llvm/CodeGen/MachineLoopInfo.h"
  45 #include "llvm/CodeGen/MachineRegisterInfo.h"
  46 #include "llvm/CodeGen/RegisterScavenging.h"
  47 #include "llvm/Support/Debug.h"
  48 #include "llvm/Support/raw_ostream.h"
  49 #include "llvm/Target/TargetInstrInfo.h"
  50 #include <algorithm>
  51
  52 using namespace llvm;
  53
  54 STATISTIC(NumCTRLoops, "Number of loops converted to CTR loops");
  55
  56 namespace {
  57   class CountValue;
  58   struct PPCCTRLoops : public MachineFunctionPass {
  59     MachineLoopInfo       *MLI;
  60     MachineRegisterInfo   *MRI;
  61     const TargetInstrInfo *TII;
  62
  63   public:
  64     static char ID;   // Pass identification, replacement for typeid
  65
  66     PPCCTRLoops() : MachineFunctionPass(ID) {}
  67
  68     virtual bool runOnMachineFunction(MachineFunction &MF);
  69
  70     const char *getPassName() const { return "PPC CTR Loops"; }
  71
  72     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  73       AU.setPreservesCFG();
  74       AU.addRequired<MachineDominatorTree>();
  75       AU.addPreserved<MachineDominatorTree>();
  76       AU.addRequired<MachineLoopInfo>();
  77       AU.addPreserved<MachineLoopInfo>();
  78       MachineFunctionPass::getAnalysisUsage(AU);
  79     }
  80
  81   private:
  82     /// getCanonicalInductionVariable - Check to see if the loop has a canonical
  83     /// induction variable.
  84     /// Should be defined in MachineLoop. Based upon version in class Loop.
  85     MachineInstr *getCanonicalInductionVariable(MachineLoop *L,
  86                                                 MachineInstr *&IOp) const;
  87
  88     /// getTripCount - Return a loop-invariant LLVM register indicating the
  89     /// number of times the loop will be executed.  If the trip-count cannot
  90     /// be determined, this return null.
  91     CountValue *getTripCount(MachineLoop *L, bool &WordCmp,
  92                              SmallVector<MachineInstr *, 2> &OldInsts) const;
  93
  94     /// isInductionOperation - Return true if the instruction matches the
  95     /// pattern for an opertion that defines an induction variable.
  96     bool isInductionOperation(const MachineInstr *MI, unsigned IVReg) const;
  97
  98     /// isInvalidOperation - Return true if the instruction is not valid within
  99     /// a CTR loop.
 100     bool isInvalidLoopOperation(const MachineInstr *MI) const;
 101
 102     /// containsInavlidInstruction - Return true if the loop contains an
 103     /// instruction that inhibits using the CTR loop.
 104     bool containsInvalidInstruction(MachineLoop *L) const;
 105
 106     /// converToCTRLoop - Given a loop, check if we can convert it to a
 107     /// CTR loop.  If so, then perform the conversion and return true.
 108     bool convertToCTRLoop(MachineLoop *L);
 109
 110     /// isDead - Return true if the instruction is now dead.
 111     bool isDead(const MachineInstr *MI,
 112                 SmallVector<MachineInstr *, 1> &DeadPhis) const;
 113
 114     /// removeIfDead - Remove the instruction if it is now dead.
 115     void removeIfDead(MachineInstr *MI);
 116   };
 117
 118   char PPCCTRLoops::ID = 0;
 119
 120
 121   // CountValue class - Abstraction for a trip count of a loop. A
 122   // smaller vesrsion of the MachineOperand class without the concerns
 123   // of changing the operand representation.
 124   class CountValue {
 125   public:
 126     enum CountValueType {
 127       CV_Register,
 128       CV_Immediate
 129     };
 130   private:
 131     CountValueType Kind;
 132     union Values {
 133       unsigned RegNum;
 134       int64_t ImmVal;
 135       Values(unsigned r) : RegNum(r) {}
 136       Values(int64_t i) : ImmVal(i) {}
 137     } Contents;
 138     bool isNegative;
 139
 140   public:
 141     CountValue(unsigned r, bool neg) : Kind(CV_Register), Contents(r),
 142                                        isNegative(neg) {}
 143     explicit CountValue(int64_t i) : Kind(CV_Immediate), Contents(i),
 144                                      isNegative(i < 0) {}
 145     CountValueType getType() const { return Kind; }
 146     bool isReg() const { return Kind == CV_Register; }
 147     bool isImm() const { return Kind == CV_Immediate; }
 148     bool isNeg() const { return isNegative; }
 149
 150     unsigned getReg() const {
 151       assert(isReg() && "Wrong CountValue accessor");
 152       return Contents.RegNum;
 153     }
 154     void setReg(unsigned Val) {
 155       Contents.RegNum = Val;
 156     }
 157     int64_t getImm() const {
 158       assert(isImm() && "Wrong CountValue accessor");
 159       if (isNegative) {
 160         return -Contents.ImmVal;
 161       }
 162       return Contents.ImmVal;
 163     }
 164     void setImm(int64_t Val) {
 165       Contents.ImmVal = Val;
 166     }
 167
 168     void print(raw_ostream &OS, const TargetMachine *TM = 0) const {
 169       if (isReg()) { OS << PrintReg(getReg()); }
 170       if (isImm()) { OS << getImm(); }
 171     }
 172   };
 173 } // end anonymous namespace
 174
 175
 176 /// isCompareEquals - Returns true if the instruction is a compare equals
 177 /// instruction with an immediate operand.
 178 static bool isCompareEqualsImm(const MachineInstr *MI, bool &WordCmp) {
 179   if (MI->getOpcode() == PPC::CMPWI || MI->getOpcode() == PPC::CMPLWI) {
 180     WordCmp = true;
 181     return true;
 182   } else if (MI->getOpcode() == PPC::CMPDI || MI->getOpcode() == PPC::CMPLDI) {
 183     WordCmp = false;
 184     return true;
 185   }
 186
 187   return false;
 188 }
 189
 190
 191 /// createPPCCTRLoops - Factory for creating
 192 /// the CTR loop phase.
 193 FunctionPass *llvm::createPPCCTRLoops() {
 194   return new PPCCTRLoops();
 195 }
 196
 197
 198 bool PPCCTRLoops::runOnMachineFunction(MachineFunction &MF) {
 199   DEBUG(dbgs() << "********* PPC CTR Loops *********\n");
 200
 201   bool Changed = false;
 202
 203   // get the loop information
 204   MLI = &getAnalysis<MachineLoopInfo>();
 205   // get the register information
 206   MRI = &MF.getRegInfo();
 207   // the target specific instructio info.
 208   TII = MF.getTarget().getInstrInfo();
 209
 210   for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
 211        I != E; ++I) {
 212     MachineLoop *L = *I;
 213     if (!L->getParentLoop()) {
 214       Changed |= convertToCTRLoop(L);
 215     }
 216   }
 217
 218   return Changed;
 219 }
 220
 221 /// getCanonicalInductionVariable - Check to see if the loop has a canonical
 222 /// induction variable. We check for a simple recurrence pattern - an
 223 /// integer recurrence that decrements by one each time through the loop and
 224 /// ends at zero.  If so, return the phi node that corresponds to it.
 225 ///
 226 /// Based upon the similar code in LoopInfo except this code is specific to
 227 /// the machine.
 228 /// This method assumes that the IndVarSimplify pass has been run by 'opt'.
 229 ///
 230 MachineInstr
 231 *PPCCTRLoops::getCanonicalInductionVariable(MachineLoop *L,
 232                                             MachineInstr *&IOp) const {
 233   MachineBasicBlock *TopMBB = L->getTopBlock();
 234   MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
 235   assert(PI != TopMBB->pred_end() &&
 236          "Loop must have more than one incoming edge!");
 237   MachineBasicBlock *Backedge = *PI++;
 238   if (PI == TopMBB->pred_end()) return 0;  // dead loop
 239   MachineBasicBlock *Incoming = *PI++;
 240   if (PI != TopMBB->pred_end()) return 0;  // multiple backedges?
 241
 242   // make sure there is one incoming and one backedge and determine which
 243   // is which.
 244   if (L->contains(Incoming)) {
 245     if (L->contains(Backedge))
 246       return 0;
 247     std::swap(Incoming, Backedge);
 248   } else if (!L->contains(Backedge))
 249     return 0;
 250
 251   // Loop over all of the PHI nodes, looking for a canonical induction variable:
 252   //   - The PHI node is "reg1 = PHI reg2, BB1, reg3, BB2".
 253   //   - The recurrence comes from the backedge.
 254   //   - the definition is an induction operatio.n
 255   for (MachineBasicBlock::iterator I = TopMBB->begin(), E = TopMBB->end();
 256        I != E && I->isPHI(); ++I) {
 257     MachineInstr *MPhi = &*I;
 258     unsigned DefReg = MPhi->getOperand(0).getReg();
 259     for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
 260       // Check each operand for the value from the backedge.
 261       MachineBasicBlock *MBB = MPhi->getOperand(i+1).getMBB();
 262       if (L->contains(MBB)) { // operands comes from the backedge
 263         // Check if the definition is an induction operation.
 264         MachineInstr *DI = MRI->getVRegDef(MPhi->getOperand(i).getReg());
 265         if (isInductionOperation(DI, DefReg)) {
 266           IOp = DI;
 267           return MPhi;
 268         }
 269       }
 270     }
 271   }
 272   return 0;
 273 }
 274
 275 /// getTripCount - Return a loop-invariant LLVM value indicating the
 276 /// number of times the loop will be executed.  The trip count can
 277 /// be either a register or a constant value.  If the trip-count
 278 /// cannot be determined, this returns null.
 279 ///
 280 /// We find the trip count from the phi instruction that defines the
 281 /// induction variable.  We follow the links to the CMP instruction
 282 /// to get the trip count.
 283 ///
 284 /// Based upon getTripCount in LoopInfo.
 285 ///
 286 CountValue *PPCCTRLoops::getTripCount(MachineLoop *L, bool &WordCmp,
 287                            SmallVector<MachineInstr *, 2> &OldInsts) const {
 288   // Check that the loop has a induction variable.
 289   MachineInstr *IOp;
 290   MachineInstr *IV_Inst = getCanonicalInductionVariable(L, IOp);
 291   if (IV_Inst == 0) return 0;
 292
 293   // Canonical loops will end with a 'cmpwi/cmpdi cr, IV, Imm',
 294   //  if Imm is 0, get the count from the PHI opnd
 295   //  if Imm is -M, than M is the count
 296   //  Otherwise, Imm is the count
 297   MachineOperand *IV_Opnd;
 298   const MachineOperand *InitialValue;
 299   if (!L->contains(IV_Inst->getOperand(2).getMBB())) {
 300     InitialValue = &IV_Inst->getOperand(1);
 301     IV_Opnd = &IV_Inst->getOperand(3);
 302   } else {
 303     InitialValue = &IV_Inst->getOperand(3);
 304     IV_Opnd = &IV_Inst->getOperand(1);
 305   }
 306
 307   // Look for the cmp instruction to determine if we
 308   // can get a useful trip count.  The trip count can
 309   // be either a register or an immediate.  The location
 310   // of the value depends upon the type (reg or imm).
 311   while ((IV_Opnd = IV_Opnd->getNextOperandForReg())) {
 312     MachineInstr *MI = IV_Opnd->getParent();
 313     if (L->contains(MI) && isCompareEqualsImm(MI, WordCmp)) {
 314       OldInsts.push_back(MI);
 315       OldInsts.push_back(IOp);
 316
 317       const MachineOperand &MO = MI->getOperand(2);
 318       assert(MO.isImm() && "IV Cmp Operand should be an immediate");
 319       int64_t ImmVal = MO.getImm();
 320
 321       const MachineInstr *IV_DefInstr = MRI->getVRegDef(IV_Opnd->getReg());
 322       assert(L->contains(IV_DefInstr->getParent()) &&
 323              "IV definition should occurs in loop");
 324       int64_t iv_value = IV_DefInstr->getOperand(2).getImm();
 325
 326       if (ImmVal == 0) {
 327         // Make sure the induction variable changes by one on each iteration.
 328         if (iv_value != 1 && iv_value != -1) {
 329           return 0;
 330         }
 331         return new CountValue(InitialValue->getReg(), iv_value > 0);
 332       } else {
 333         assert(InitialValue->isReg() && "Expecting register for init value");
 334         const MachineInstr *DefInstr = MRI->getVRegDef(InitialValue->getReg());
 335
 336         // Here we need to look for an immediate load (an li or lis/ori pair).
 337         if (DefInstr && (DefInstr->getOpcode() == PPC::ORI8 ||
 338                          DefInstr->getOpcode() == PPC::ORI)) {
 339           int64_t start = DefInstr->getOperand(2).getImm();
 340           const MachineInstr *DefInstr2 =
 341             MRI->getVRegDef(DefInstr->getOperand(0).getReg());
 342           if (DefInstr2 && (DefInstr2->getOpcode() == PPC::LIS8 ||
 343                             DefInstr2->getOpcode() == PPC::LIS)) {
 344             start |= DefInstr2->getOperand(1).getImm() << 16;
 345
 346             int64_t count = ImmVal - start;
 347             if ((count % iv_value) != 0) {
 348               return 0;
 349             }
 350             return new CountValue(count/iv_value);
 351           }
 352         } else if (DefInstr && (DefInstr->getOpcode() == PPC::LI8 ||
 353                                 DefInstr->getOpcode() == PPC::LI)) {
 354           int64_t count = ImmVal - DefInstr->getOperand(1).getImm();
 355           if ((count % iv_value) != 0) {
 356             return 0;
 357           }
 358           return new CountValue(count/iv_value);
 359         }
 360       }
 361     }
 362   }
 363   return 0;
 364 }
 365
 366 /// isInductionOperation - return true if the operation is matches the
 367 /// pattern that defines an induction variable:
 368 ///    addi iv, c
 369 ///
 370 bool
 371 PPCCTRLoops::isInductionOperation(const MachineInstr *MI,
 372                                            unsigned IVReg) const {
 373   return ((MI->getOpcode() == PPC::ADDI || MI->getOpcode() == PPC::ADDI8) &&
 374           MI->getOperand(1).isReg() && // could be a frame index instead
 375           MI->getOperand(1).getReg() == IVReg);
 376 }
 377
 378 /// isInvalidOperation - Return true if the operation is invalid within
 379 /// CTR loop.
 380 bool
 381 PPCCTRLoops::isInvalidLoopOperation(const MachineInstr *MI) const {
 382
 383   // call is not allowed because the callee may use a CTR loop
 384   if (MI->getDesc().isCall()) {
 385     return true;
 386   }
 387   // check if the instruction defines a CTR loop register
 388   // (this will also catch nested CTR loops)
 389   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 390     const MachineOperand &MO = MI->getOperand(i);
 391     if (MO.isReg() && MO.isDef() &&
 392         (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8)) {
 393       return true;
 394     }
 395   }
 396   return false;
 397 }
 398
 399 /// containsInvalidInstruction - Return true if the loop contains
 400 /// an instruction that inhibits the use of the CTR loop function.
 401 ///
 402 bool PPCCTRLoops::containsInvalidInstruction(MachineLoop *L) const {
 403   const std::vector<MachineBasicBlock*> Blocks = L->getBlocks();
 404   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
 405     MachineBasicBlock *MBB = Blocks[i];
 406     for (MachineBasicBlock::iterator
 407            MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
 408       const MachineInstr *MI = &*MII;
 409       if (isInvalidLoopOperation(MI)) {
 410         return true;
 411       }
 412     }
 413   }
 414   return false;
 415 }
 416
 417 /// isDead returns true if the instruction is dead
 418 /// (this was essentially copied from DeadMachineInstructionElim::isDead, but
 419 /// with special cases for inline asm, physical registers and instructions with
 420 /// side effects removed)
 421 bool PPCCTRLoops::isDead(const MachineInstr *MI,
 422                          SmallVector<MachineInstr *, 1> &DeadPhis) const {
 423   // Examine each operand.
 424   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 425     const MachineOperand &MO = MI->getOperand(i);
 426     if (MO.isReg() && MO.isDef()) {
 427       unsigned Reg = MO.getReg();
 428       if (!MRI->use_nodbg_empty(Reg)) {
 429         // This instruction has users, but if the only user is the phi node for the
 430         // parent block, and the only use of that phi node is this instruction, then
 431         // this instruction is dead: both it (and the phi node) can be removed.
 432         MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg);
 433         if (llvm::next(I) == MRI->use_end() &&
 434             I.getOperand().getParent()->isPHI()) {
 435           MachineInstr *OnePhi = I.getOperand().getParent();
 436
 437           for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
 438             const MachineOperand &OPO = OnePhi->getOperand(j);
 439             if (OPO.isReg() && OPO.isDef()) {
 440               unsigned OPReg = OPO.getReg();
 441
 442               MachineRegisterInfo::use_iterator nextJ;
 443               for (MachineRegisterInfo::use_iterator J = MRI->use_begin(OPReg),
 444                    E = MRI->use_end(); J!=E; J=nextJ) {
 445                 nextJ = llvm::next(J);
 446                 MachineOperand& Use = J.getOperand();
 447                 MachineInstr *UseMI = Use.getParent();
 448
 449                 if (MI != UseMI) {
 450                   // The phi node has a user that is not MI, bail...
 451                   return false;
 452                 }
 453               }
 454             }
 455           }
 456
 457           DeadPhis.push_back(OnePhi);
 458         } else {
 459           // This def has a non-debug use. Don't delete the instruction!
 460           return false;
 461         }
 462       }
 463     }
 464   }
 465
 466   // If there are no defs with uses, the instruction is dead.
 467   return true;
 468 }
 469
 470 void PPCCTRLoops::removeIfDead(MachineInstr *MI) {
 471   // This procedure was essentially copied from DeadMachineInstructionElim
 472
 473   SmallVector<MachineInstr *, 1> DeadPhis;
 474   if (isDead(MI, DeadPhis)) {
 475     DEBUG(dbgs() << "CTR looping will remove: " << *MI);
 476
 477     // It is possible that some DBG_VALUE instructions refer to this
 478     // instruction.  Examine each def operand for such references;
 479     // if found, mark the DBG_VALUE as undef (but don't delete it).
 480     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 481       const MachineOperand &MO = MI->getOperand(i);
 482       if (!MO.isReg() || !MO.isDef())
 483         continue;
 484       unsigned Reg = MO.getReg();
 485       MachineRegisterInfo::use_iterator nextI;
 486       for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
 487            E = MRI->use_end(); I!=E; I=nextI) {
 488         nextI = llvm::next(I);  // I is invalidated by the setReg
 489         MachineOperand& Use = I.getOperand();
 490         MachineInstr *UseMI = Use.getParent();
 491         if (UseMI==MI)
 492           continue;
 493         if (Use.isDebug()) // this might also be a instr -> phi -> instr case
 494                            // which can also be removed.
 495           UseMI->getOperand(0).setReg(0U);
 496       }
 497     }
 498
 499     MI->eraseFromParent();
 500     for (unsigned i = 0; i < DeadPhis.size(); ++i) {
 501       DeadPhis[i]->eraseFromParent();
 502     }
 503   }
 504 }
 505
 506 /// converToCTRLoop - check if the loop is a candidate for
 507 /// converting to a CTR loop.  If so, then perform the
 508 /// transformation.
 509 ///
 510 /// This function works on innermost loops first.  A loop can
 511 /// be converted if it is a counting loop; either a register
 512 /// value or an immediate.
 513 ///
 514 /// The code makes several assumptions about the representation
 515 /// of the loop in llvm.
 516 bool PPCCTRLoops::convertToCTRLoop(MachineLoop *L) {
 517   bool Changed = false;
 518   // Process nested loops first.
 519   for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
 520     Changed |= convertToCTRLoop(*I);
 521   }
 522   // If a nested loop has been converted, then we can't convert this loop.
 523   if (Changed) {
 524     return Changed;
 525   }
 526
 527   bool WordCmp;
 528   SmallVector<MachineInstr *, 2> OldInsts;
 529   // Are we able to determine the trip count for the loop?
 530   CountValue *TripCount = getTripCount(L, WordCmp, OldInsts);
 531   if (TripCount == 0) {
 532     DEBUG(dbgs() << "failed to get trip count!\n");
 533     return false;
 534   }
 535   // Does the loop contain any invalid instructions?
 536   if (containsInvalidInstruction(L)) {
 537     return false;
 538   }
 539   MachineBasicBlock *Preheader = L->getLoopPreheader();
 540   // No preheader means there's not place for the loop instr.
 541   if (Preheader == 0) {
 542     return false;
 543   }
 544   MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
 545
 546   DebugLoc dl;
 547   if (InsertPos != Preheader->end())
 548     dl = InsertPos->getDebugLoc();
 549
 550   MachineBasicBlock *LastMBB = L->getExitingBlock();
 551   // Don't generate CTR loop if the loop has more than one exit.
 552   if (LastMBB == 0) {
 553     return false;
 554   }
 555   MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
 556
 557   // Determine the loop start.
 558   MachineBasicBlock *LoopStart = L->getTopBlock();
 559   if (L->getLoopLatch() != LastMBB) {
 560     // When the exit and latch are not the same, use the latch block as the
 561     // start.
 562     // The loop start address is used only after the 1st iteration, and the loop
 563     // latch may contains instrs. that need to be executed after the 1st iter.
 564     LoopStart = L->getLoopLatch();
 565     // Make sure the latch is a successor of the exit, otherwise it won't work.
 566     if (!LastMBB->isSuccessor(LoopStart)) {
 567       return false;
 568     }
 569   }
 570
 571   // Convert the loop to a CTR loop
 572   DEBUG(dbgs() << "Change to CTR loop at "; L->dump());
 573
 574   MachineFunction *MF = LastMBB->getParent();
 575   const PPCSubtarget &Subtarget = MF->getTarget().getSubtarget<PPCSubtarget>();
 576   bool isPPC64 = Subtarget.isPPC64();
 577
 578   unsigned CountReg;
 579   if (TripCount->isReg()) {
 580     // Create a copy of the loop count register.
 581     const TargetRegisterClass *RC =
 582       MF->getRegInfo().getRegClass(TripCount->getReg());
 583     CountReg = MF->getRegInfo().createVirtualRegister(RC);
 584     BuildMI(*Preheader, InsertPos, dl,
 585             TII->get(TargetOpcode::COPY), CountReg).addReg(TripCount->getReg());
 586     if (TripCount->isNeg()) {
 587       unsigned CountReg1 = CountReg;
 588       CountReg = MF->getRegInfo().createVirtualRegister(RC);
 589       BuildMI(*Preheader, InsertPos, dl,
 590               TII->get(isPPC64 ? PPC::NEG8 : PPC::NEG),
 591                        CountReg).addReg(CountReg1);
 592     }
 593
 594     // On a 64-bit system, if the original comparison was only 32-bit, then
 595     // mask out the higher-order part of the count.
 596     if (isPPC64 && WordCmp) {
 597        unsigned CountReg1 = CountReg;
 598        CountReg = MF->getRegInfo().createVirtualRegister(RC);
 599        BuildMI(*Preheader, InsertPos, dl,
 600                TII->get(PPC::RLDICL), CountReg).addReg(CountReg1
 601               ).addImm(0).addImm(32);
 602     }
 603   } else {
 604     assert(TripCount->isImm() && "Expecting immedate vaule for trip count");
 605     // Put the trip count in a register for transfer into the count register.
 606     const TargetRegisterClass *GPRC = &PPC::GPRCRegClass;
 607     const TargetRegisterClass *G8RC = &PPC::G8RCRegClass;
 608     const TargetRegisterClass *RC = isPPC64 ? G8RC : GPRC;
 609
 610     int64_t CountImm = TripCount->getImm();
 611     if (TripCount->isNeg())
 612       CountImm = -CountImm;
 613
 614     CountReg = MF->getRegInfo().createVirtualRegister(RC);
 615     if (CountImm > 0xFFFF) {
 616       BuildMI(*Preheader, InsertPos, dl,
 617               TII->get(isPPC64 ? PPC::LIS8 : PPC::LIS),
 618               CountReg).addImm(CountImm >> 16);
 619       unsigned CountReg1 = CountReg;
 620       CountReg = MF->getRegInfo().createVirtualRegister(RC);
 621       BuildMI(*Preheader, InsertPos, dl,
 622               TII->get(isPPC64 ? PPC::ORI8 : PPC::ORI),
 623               CountReg).addReg(CountReg1).addImm(CountImm & 0xFFFF);
 624     } else {
 625       BuildMI(*Preheader, InsertPos, dl,
 626               TII->get(isPPC64 ? PPC::LI8 : PPC::LI),
 627               CountReg).addImm(CountImm);
 628     }
 629   }
 630
 631   // Add the mtctr instruction to the beginning of the loop.
 632   BuildMI(*Preheader, InsertPos, dl,
 633           TII->get(isPPC64 ? PPC::MTCTR8 : PPC::MTCTR)).addReg(CountReg,
 634             TripCount->isImm() ? RegState::Kill : 0);
 635
 636   // Make sure the loop start always has a reference in the CFG.  We need to
 637   // create a BlockAddress operand to get this mechanism to work both the
 638   // MachineBasicBlock and BasicBlock objects need the flag set.
 639   LoopStart->setHasAddressTaken();
 640   // This line is needed to set the hasAddressTaken flag on the BasicBlock
 641   // object
 642   BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
 643
 644   // Replace the loop branch with a bdnz instruction.
 645   dl = LastI->getDebugLoc();
 646   const std::vector<MachineBasicBlock*> Blocks = L->getBlocks();
 647   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
 648     MachineBasicBlock *MBB = Blocks[i];
 649     if (MBB != Preheader)
 650       MBB->addLiveIn(isPPC64 ? PPC::CTR8 : PPC::CTR);
 651   }
 652
 653   // The loop ends with either:
 654   //  - a conditional branch followed by an unconditional branch, or
 655   //  - a conditional branch to the loop start.
 656   assert(LastI->getOpcode() == PPC::BCC &&
 657          "loop end must start with a BCC instruction");
 658   // Either the BCC branches to the beginning of the loop, or it
 659   // branches out of the loop and there is an unconditional branch
 660   // to the start of the loop.
 661   MachineBasicBlock *BranchTarget = LastI->getOperand(2).getMBB();
 662   BuildMI(*LastMBB, LastI, dl,
 663         TII->get((BranchTarget == LoopStart) ?
 664                  (isPPC64 ? PPC::BDNZ8 : PPC::BDNZ) :
 665                  (isPPC64 ? PPC::BDZ8 : PPC::BDZ))).addMBB(BranchTarget);
 666
 667   // Conditional branch; just delete it.
 668   LastMBB->erase(LastI);
 669
 670   delete TripCount;
 671
 672   // The induction operation (add) and the comparison (cmpwi) may now be
 673   // unneeded. If these are unneeded, then remove them.
 674   for (unsigned i = 0; i < OldInsts.size(); ++i)
 675     removeIfDead(OldInsts[i]);
 676
 677   ++NumCTRLoops;
 678   return true;
 679 }
 680