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 53using namespace llvm; 54 55STATISTIC(NumCTRLoops, "Number of loops converted to CTR loops"); 56 57namespace { 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. 180static 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. 195FunctionPass *llvm::createPPCCTRLoops() { 196 return new PPCCTRLoops(); 197} 198 199 200bool 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/// 232void 233PPCCTRLoops::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/// 289CountValue *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/// 421bool 422PPCCTRLoops::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. 431bool 432PPCCTRLoops::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/// 453bool 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) 472bool 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 521void 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. 567bool 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 725