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