PPCCTRLoops.cpp revision 99f823f94374917174f96a7689955b8463db6816
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 52using namespace llvm; 53 54STATISTIC(NumCTRLoops, "Number of loops converted to CTR loops"); 55 56namespace { 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. 178static 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. 193FunctionPass *llvm::createPPCCTRLoops() { 194 return new PPCCTRLoops(); 195} 196 197 198bool 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/// 230MachineInstr 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/// 286CountValue *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/// 370bool 371PPCCTRLoops::isInductionOperation(const MachineInstr *MI, 372 unsigned IVReg) const { 373 return ((MI->getOpcode() == PPC::ADDI || MI->getOpcode() == PPC::ADDI8) && 374 MI->getOperand(1).getReg() == IVReg); 375} 376 377/// isInvalidOperation - Return true if the operation is invalid within 378/// CTR loop. 379bool 380PPCCTRLoops::isInvalidLoopOperation(const MachineInstr *MI) const { 381 382 // call is not allowed because the callee may use a CTR loop 383 if (MI->getDesc().isCall()) { 384 return true; 385 } 386 // check if the instruction defines a CTR loop register 387 // (this will also catch nested CTR loops) 388 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 389 const MachineOperand &MO = MI->getOperand(i); 390 if (MO.isReg() && MO.isDef() && 391 (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8)) { 392 return true; 393 } 394 } 395 return false; 396} 397 398/// containsInvalidInstruction - Return true if the loop contains 399/// an instruction that inhibits the use of the CTR loop function. 400/// 401bool PPCCTRLoops::containsInvalidInstruction(MachineLoop *L) const { 402 const std::vector<MachineBasicBlock*> Blocks = L->getBlocks(); 403 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 404 MachineBasicBlock *MBB = Blocks[i]; 405 for (MachineBasicBlock::iterator 406 MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) { 407 const MachineInstr *MI = &*MII; 408 if (isInvalidLoopOperation(MI)) { 409 return true; 410 } 411 } 412 } 413 return false; 414} 415 416/// isDead returns true if the instruction is dead 417/// (this was essentially copied from DeadMachineInstructionElim::isDead, but 418/// with special cases for inline asm, physical registers and instructions with 419/// side effects removed) 420bool PPCCTRLoops::isDead(const MachineInstr *MI, 421 SmallVector<MachineInstr *, 1> &DeadPhis) const { 422 // Examine each operand. 423 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 424 const MachineOperand &MO = MI->getOperand(i); 425 if (MO.isReg() && MO.isDef()) { 426 unsigned Reg = MO.getReg(); 427 if (!MRI->use_nodbg_empty(Reg)) { 428 // This instruction has users, but if the only user is the phi node for the 429 // parent block, and the only use of that phi node is this instruction, then 430 // this instruction is dead: both it (and the phi node) can be removed. 431 MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg); 432 if (llvm::next(I) == MRI->use_end() && 433 I.getOperand().getParent()->isPHI()) { 434 MachineInstr *OnePhi = I.getOperand().getParent(); 435 436 for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) { 437 const MachineOperand &OPO = OnePhi->getOperand(j); 438 if (OPO.isReg() && OPO.isDef()) { 439 unsigned OPReg = OPO.getReg(); 440 441 MachineRegisterInfo::use_iterator nextJ; 442 for (MachineRegisterInfo::use_iterator J = MRI->use_begin(OPReg), 443 E = MRI->use_end(); J!=E; J=nextJ) { 444 nextJ = llvm::next(J); 445 MachineOperand& Use = J.getOperand(); 446 MachineInstr *UseMI = Use.getParent(); 447 448 if (MI != UseMI) { 449 // The phi node has a user that is not MI, bail... 450 return false; 451 } 452 } 453 } 454 } 455 456 DeadPhis.push_back(OnePhi); 457 } else { 458 // This def has a non-debug use. Don't delete the instruction! 459 return false; 460 } 461 } 462 } 463 } 464 465 // If there are no defs with uses, the instruction is dead. 466 return true; 467} 468 469void PPCCTRLoops::removeIfDead(MachineInstr *MI) { 470 // This procedure was essentially copied from DeadMachineInstructionElim 471 472 SmallVector<MachineInstr *, 1> DeadPhis; 473 if (isDead(MI, DeadPhis)) { 474 DEBUG(dbgs() << "CTR looping will remove: " << *MI); 475 476 // It is possible that some DBG_VALUE instructions refer to this 477 // instruction. Examine each def operand for such references; 478 // if found, mark the DBG_VALUE as undef (but don't delete it). 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 continue; 483 unsigned Reg = MO.getReg(); 484 MachineRegisterInfo::use_iterator nextI; 485 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg), 486 E = MRI->use_end(); I!=E; I=nextI) { 487 nextI = llvm::next(I); // I is invalidated by the setReg 488 MachineOperand& Use = I.getOperand(); 489 MachineInstr *UseMI = Use.getParent(); 490 if (UseMI==MI) 491 continue; 492 if (Use.isDebug()) // this might also be a instr -> phi -> instr case 493 // which can also be removed. 494 UseMI->getOperand(0).setReg(0U); 495 } 496 } 497 498 MI->eraseFromParent(); 499 for (unsigned i = 0; i < DeadPhis.size(); ++i) { 500 DeadPhis[i]->eraseFromParent(); 501 } 502 } 503} 504 505/// converToCTRLoop - check if the loop is a candidate for 506/// converting to a CTR loop. If so, then perform the 507/// transformation. 508/// 509/// This function works on innermost loops first. A loop can 510/// be converted if it is a counting loop; either a register 511/// value or an immediate. 512/// 513/// The code makes several assumptions about the representation 514/// of the loop in llvm. 515bool PPCCTRLoops::convertToCTRLoop(MachineLoop *L) { 516 bool Changed = false; 517 // Process nested loops first. 518 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) { 519 Changed |= convertToCTRLoop(*I); 520 } 521 // If a nested loop has been converted, then we can't convert this loop. 522 if (Changed) { 523 return Changed; 524 } 525 526 bool WordCmp; 527 SmallVector<MachineInstr *, 2> OldInsts; 528 // Are we able to determine the trip count for the loop? 529 CountValue *TripCount = getTripCount(L, WordCmp, OldInsts); 530 if (TripCount == 0) { 531 DEBUG(dbgs() << "failed to get trip count!\n"); 532 return false; 533 } 534 // Does the loop contain any invalid instructions? 535 if (containsInvalidInstruction(L)) { 536 return false; 537 } 538 MachineBasicBlock *Preheader = L->getLoopPreheader(); 539 // No preheader means there's not place for the loop instr. 540 if (Preheader == 0) { 541 return false; 542 } 543 MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator(); 544 545 DebugLoc dl; 546 if (InsertPos != Preheader->end()) 547 dl = InsertPos->getDebugLoc(); 548 549 MachineBasicBlock *LastMBB = L->getExitingBlock(); 550 // Don't generate CTR loop if the loop has more than one exit. 551 if (LastMBB == 0) { 552 return false; 553 } 554 MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator(); 555 556 // Determine the loop start. 557 MachineBasicBlock *LoopStart = L->getTopBlock(); 558 if (L->getLoopLatch() != LastMBB) { 559 // When the exit and latch are not the same, use the latch block as the 560 // start. 561 // The loop start address is used only after the 1st iteration, and the loop 562 // latch may contains instrs. that need to be executed after the 1st iter. 563 LoopStart = L->getLoopLatch(); 564 // Make sure the latch is a successor of the exit, otherwise it won't work. 565 if (!LastMBB->isSuccessor(LoopStart)) { 566 return false; 567 } 568 } 569 570 // Convert the loop to a CTR loop 571 DEBUG(dbgs() << "Change to CTR loop at "; L->dump()); 572 573 MachineFunction *MF = LastMBB->getParent(); 574 const PPCSubtarget &Subtarget = MF->getTarget().getSubtarget<PPCSubtarget>(); 575 bool isPPC64 = Subtarget.isPPC64(); 576 577 unsigned CountReg; 578 if (TripCount->isReg()) { 579 // Create a copy of the loop count register. 580 const TargetRegisterClass *RC = 581 MF->getRegInfo().getRegClass(TripCount->getReg()); 582 CountReg = MF->getRegInfo().createVirtualRegister(RC); 583 BuildMI(*Preheader, InsertPos, dl, 584 TII->get(TargetOpcode::COPY), CountReg).addReg(TripCount->getReg()); 585 if (TripCount->isNeg()) { 586 unsigned CountReg1 = CountReg; 587 CountReg = MF->getRegInfo().createVirtualRegister(RC); 588 BuildMI(*Preheader, InsertPos, dl, 589 TII->get(isPPC64 ? PPC::NEG8 : PPC::NEG), 590 CountReg).addReg(CountReg1); 591 } 592 593 // On a 64-bit system, if the original comparison was only 32-bit, then 594 // mask out the higher-order part of the count. 595 if (isPPC64 && WordCmp) { 596 unsigned CountReg1 = CountReg; 597 CountReg = MF->getRegInfo().createVirtualRegister(RC); 598 BuildMI(*Preheader, InsertPos, dl, 599 TII->get(PPC::RLDICL), CountReg).addReg(CountReg1 600 ).addImm(0).addImm(32); 601 } 602 } else { 603 assert(TripCount->isImm() && "Expecting immedate vaule for trip count"); 604 // Put the trip count in a register for transfer into the count register. 605 const TargetRegisterClass *GPRC = &PPC::GPRCRegClass; 606 const TargetRegisterClass *G8RC = &PPC::G8RCRegClass; 607 const TargetRegisterClass *RC = isPPC64 ? G8RC : GPRC; 608 609 int64_t CountImm = TripCount->getImm(); 610 if (TripCount->isNeg()) 611 CountImm = -CountImm; 612 613 CountReg = MF->getRegInfo().createVirtualRegister(RC); 614 if (CountImm > 0xFFFF) { 615 BuildMI(*Preheader, InsertPos, dl, 616 TII->get(isPPC64 ? PPC::LIS8 : PPC::LIS), 617 CountReg).addImm(CountImm >> 16); 618 unsigned CountReg1 = CountReg; 619 CountReg = MF->getRegInfo().createVirtualRegister(RC); 620 BuildMI(*Preheader, InsertPos, dl, 621 TII->get(isPPC64 ? PPC::ORI8 : PPC::ORI), 622 CountReg).addReg(CountReg1).addImm(CountImm & 0xFFFF); 623 } else { 624 BuildMI(*Preheader, InsertPos, dl, 625 TII->get(isPPC64 ? PPC::LI8 : PPC::LI), 626 CountReg).addImm(CountImm); 627 } 628 } 629 630 // Add the mtctr instruction to the beginning of the loop. 631 BuildMI(*Preheader, InsertPos, dl, 632 TII->get(isPPC64 ? PPC::MTCTR8 : PPC::MTCTR)).addReg(CountReg, 633 TripCount->isImm() ? RegState::Kill : 0); 634 635 // Make sure the loop start always has a reference in the CFG. We need to 636 // create a BlockAddress operand to get this mechanism to work both the 637 // MachineBasicBlock and BasicBlock objects need the flag set. 638 LoopStart->setHasAddressTaken(); 639 // This line is needed to set the hasAddressTaken flag on the BasicBlock 640 // object 641 BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock())); 642 643 // Replace the loop branch with a bdnz instruction. 644 dl = LastI->getDebugLoc(); 645 const std::vector<MachineBasicBlock*> Blocks = L->getBlocks(); 646 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 647 MachineBasicBlock *MBB = Blocks[i]; 648 if (MBB != Preheader) 649 MBB->addLiveIn(isPPC64 ? PPC::CTR8 : PPC::CTR); 650 } 651 652 // The loop ends with either: 653 // - a conditional branch followed by an unconditional branch, or 654 // - a conditional branch to the loop start. 655 assert(LastI->getOpcode() == PPC::BCC && 656 "loop end must start with a BCC instruction"); 657 // Either the BCC branches to the beginning of the loop, or it 658 // branches out of the loop and there is an unconditional branch 659 // to the start of the loop. 660 MachineBasicBlock *BranchTarget = LastI->getOperand(2).getMBB(); 661 BuildMI(*LastMBB, LastI, dl, 662 TII->get((BranchTarget == LoopStart) ? 663 (isPPC64 ? PPC::BDNZ8 : PPC::BDNZ) : 664 (isPPC64 ? PPC::BDZ8 : PPC::BDZ))).addMBB(BranchTarget); 665 666 // Conditional branch; just delete it. 667 LastMBB->erase(LastI); 668 669 delete TripCount; 670 671 // The induction operation (add) and the comparison (cmpwi) may now be 672 // unneeded. If these are unneeded, then remove them. 673 for (unsigned i = 0; i < OldInsts.size(); ++i) 674 removeIfDead(OldInsts[i]); 675 676 ++NumCTRLoops; 677 return true; 678} 679 680