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