PPCCTRLoops.cpp revision 3ea1b064a0b9c3d161b0f77a9e957970f98907ab
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 53using namespace llvm; 54 55STATISTIC(NumCTRLoops, "Number of loops converted to CTR loops"); 56 57namespace llvm { 58 void initializePPCCTRLoopsPass(PassRegistry&); 59} 60 61namespace { 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 183INITIALIZE_PASS_BEGIN(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops", 184 false, false) 185INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 186INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 187INITIALIZE_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. 192static 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. 218FunctionPass *llvm::createPPCCTRLoops() { 219 return new PPCCTRLoops(); 220} 221 222 223bool 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/// 255void 256PPCCTRLoops::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/// 312CountValue *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/// 460bool 461PPCCTRLoops::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. 470bool 471PPCCTRLoops::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/// 492bool 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) 511bool 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 561void 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. 607bool 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 776