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 // 13 // The pattern that defines the induction variable can changed depending on 14 // prior optimizations. For example, the IndVarSimplify phase run by 'opt' 15 // normalizes induction variables, and the Loop Strength Reduction pass 16 // run by 'llc' may also make changes to the induction variable. 17 // 18 // Criteria for CTR loops: 19 // - Countable loops (w/ ind. var for a trip count) 20 // - Try inner-most loops first 21 // - No nested CTR loops. 22 // - No function calls in loops. 23 // 24 //===----------------------------------------------------------------------===// 25 26 #include "llvm/Transforms/Scalar.h" 27 #include "PPC.h" 28 #include "PPCTargetMachine.h" 29 #include "llvm/ADT/STLExtras.h" 30 #include "llvm/ADT/Statistic.h" 31 #include "llvm/Analysis/LoopInfo.h" 32 #include "llvm/Analysis/ScalarEvolutionExpander.h" 33 #include "llvm/Analysis/TargetLibraryInfo.h" 34 #include "llvm/IR/Constants.h" 35 #include "llvm/IR/DerivedTypes.h" 36 #include "llvm/IR/Dominators.h" 37 #include "llvm/IR/InlineAsm.h" 38 #include "llvm/IR/Instructions.h" 39 #include "llvm/IR/IntrinsicInst.h" 40 #include "llvm/IR/Module.h" 41 #include "llvm/IR/ValueHandle.h" 42 #include "llvm/PassSupport.h" 43 #include "llvm/Support/CommandLine.h" 44 #include "llvm/Support/Debug.h" 45 #include "llvm/Support/raw_ostream.h" 46 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 47 #include "llvm/Transforms/Utils/Local.h" 48 #include "llvm/Transforms/Utils/LoopUtils.h" 49 50 #ifndef NDEBUG 51 #include "llvm/CodeGen/MachineDominators.h" 52 #include "llvm/CodeGen/MachineFunction.h" 53 #include "llvm/CodeGen/MachineFunctionPass.h" 54 #include "llvm/CodeGen/MachineRegisterInfo.h" 55 #endif 56 57 using namespace llvm; 58 59 #define DEBUG_TYPE "ctrloops" 60 61 #ifndef NDEBUG 62 static cl::opt<int> CTRLoopLimit("ppc-max-ctrloop", cl::Hidden, cl::init(-1)); 63 #endif 64 65 STATISTIC(NumCTRLoops, "Number of loops converted to CTR loops"); 66 67 namespace llvm { 68 void initializePPCCTRLoopsPass(PassRegistry&); 69 #ifndef NDEBUG 70 void initializePPCCTRLoopsVerifyPass(PassRegistry&); 71 #endif 72 } 73 74 namespace { 75 struct PPCCTRLoops : public FunctionPass { 76 77 #ifndef NDEBUG 78 static int Counter; 79 #endif 80 81 public: 82 static char ID; 83 84 PPCCTRLoops() : FunctionPass(ID), TM(nullptr) { 85 initializePPCCTRLoopsPass(*PassRegistry::getPassRegistry()); 86 } 87 PPCCTRLoops(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) { 88 initializePPCCTRLoopsPass(*PassRegistry::getPassRegistry()); 89 } 90 91 bool runOnFunction(Function &F) override; 92 93 void getAnalysisUsage(AnalysisUsage &AU) const override { 94 AU.addRequired<LoopInfoWrapperPass>(); 95 AU.addPreserved<LoopInfoWrapperPass>(); 96 AU.addRequired<DominatorTreeWrapperPass>(); 97 AU.addPreserved<DominatorTreeWrapperPass>(); 98 AU.addRequired<ScalarEvolutionWrapperPass>(); 99 } 100 101 private: 102 bool mightUseCTR(const Triple &TT, BasicBlock *BB); 103 bool convertToCTRLoop(Loop *L); 104 105 private: 106 PPCTargetMachine *TM; 107 LoopInfo *LI; 108 ScalarEvolution *SE; 109 const DataLayout *DL; 110 DominatorTree *DT; 111 const TargetLibraryInfo *LibInfo; 112 bool PreserveLCSSA; 113 }; 114 115 char PPCCTRLoops::ID = 0; 116 #ifndef NDEBUG 117 int PPCCTRLoops::Counter = 0; 118 #endif 119 120 #ifndef NDEBUG 121 struct PPCCTRLoopsVerify : public MachineFunctionPass { 122 public: 123 static char ID; 124 125 PPCCTRLoopsVerify() : MachineFunctionPass(ID) { 126 initializePPCCTRLoopsVerifyPass(*PassRegistry::getPassRegistry()); 127 } 128 129 void getAnalysisUsage(AnalysisUsage &AU) const override { 130 AU.addRequired<MachineDominatorTree>(); 131 MachineFunctionPass::getAnalysisUsage(AU); 132 } 133 134 bool runOnMachineFunction(MachineFunction &MF) override; 135 136 private: 137 MachineDominatorTree *MDT; 138 }; 139 140 char PPCCTRLoopsVerify::ID = 0; 141 #endif // NDEBUG 142 } // end anonymous namespace 143 144 INITIALIZE_PASS_BEGIN(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops", 145 false, false) 146 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 147 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 148 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 149 INITIALIZE_PASS_END(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops", 150 false, false) 151 152 FunctionPass *llvm::createPPCCTRLoops(PPCTargetMachine &TM) { 153 return new PPCCTRLoops(TM); 154 } 155 156 #ifndef NDEBUG 157 INITIALIZE_PASS_BEGIN(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", 158 "PowerPC CTR Loops Verify", false, false) 159 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 160 INITIALIZE_PASS_END(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", 161 "PowerPC CTR Loops Verify", false, false) 162 163 FunctionPass *llvm::createPPCCTRLoopsVerify() { 164 return new PPCCTRLoopsVerify(); 165 } 166 #endif // NDEBUG 167 168 bool PPCCTRLoops::runOnFunction(Function &F) { 169 if (skipFunction(F)) 170 return false; 171 172 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 173 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 174 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 175 DL = &F.getParent()->getDataLayout(); 176 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>(); 177 LibInfo = TLIP ? &TLIP->getTLI() : nullptr; 178 PreserveLCSSA = mustPreserveAnalysisID(LCSSAID); 179 180 bool MadeChange = false; 181 182 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); 183 I != E; ++I) { 184 Loop *L = *I; 185 if (!L->getParentLoop()) 186 MadeChange |= convertToCTRLoop(L); 187 } 188 189 return MadeChange; 190 } 191 192 static bool isLargeIntegerTy(bool Is32Bit, Type *Ty) { 193 if (IntegerType *ITy = dyn_cast<IntegerType>(Ty)) 194 return ITy->getBitWidth() > (Is32Bit ? 32U : 64U); 195 196 return false; 197 } 198 199 // Determining the address of a TLS variable results in a function call in 200 // certain TLS models. 201 static bool memAddrUsesCTR(const PPCTargetMachine *TM, 202 const Value *MemAddr) { 203 const auto *GV = dyn_cast<GlobalValue>(MemAddr); 204 if (!GV) { 205 // Recurse to check for constants that refer to TLS global variables. 206 if (const auto *CV = dyn_cast<Constant>(MemAddr)) 207 for (const auto &CO : CV->operands()) 208 if (memAddrUsesCTR(TM, CO)) 209 return true; 210 211 return false; 212 } 213 214 if (!GV->isThreadLocal()) 215 return false; 216 if (!TM) 217 return true; 218 TLSModel::Model Model = TM->getTLSModel(GV); 219 return Model == TLSModel::GeneralDynamic || Model == TLSModel::LocalDynamic; 220 } 221 222 bool PPCCTRLoops::mightUseCTR(const Triple &TT, BasicBlock *BB) { 223 for (BasicBlock::iterator J = BB->begin(), JE = BB->end(); 224 J != JE; ++J) { 225 if (CallInst *CI = dyn_cast<CallInst>(J)) { 226 if (InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue())) { 227 // Inline ASM is okay, unless it clobbers the ctr register. 228 InlineAsm::ConstraintInfoVector CIV = IA->ParseConstraints(); 229 for (unsigned i = 0, ie = CIV.size(); i < ie; ++i) { 230 InlineAsm::ConstraintInfo &C = CIV[i]; 231 if (C.Type != InlineAsm::isInput) 232 for (unsigned j = 0, je = C.Codes.size(); j < je; ++j) 233 if (StringRef(C.Codes[j]).equals_lower("{ctr}")) 234 return true; 235 } 236 237 continue; 238 } 239 240 if (!TM) 241 return true; 242 const TargetLowering *TLI = 243 TM->getSubtargetImpl(*BB->getParent())->getTargetLowering(); 244 245 if (Function *F = CI->getCalledFunction()) { 246 // Most intrinsics don't become function calls, but some might. 247 // sin, cos, exp and log are always calls. 248 unsigned Opcode = 0; 249 if (F->getIntrinsicID() != Intrinsic::not_intrinsic) { 250 switch (F->getIntrinsicID()) { 251 default: continue; 252 // If we have a call to ppc_is_decremented_ctr_nonzero, or ppc_mtctr 253 // we're definitely using CTR. 254 case Intrinsic::ppc_is_decremented_ctr_nonzero: 255 case Intrinsic::ppc_mtctr: 256 return true; 257 258 // VisualStudio defines setjmp as _setjmp 259 #if defined(_MSC_VER) && defined(setjmp) && \ 260 !defined(setjmp_undefined_for_msvc) 261 # pragma push_macro("setjmp") 262 # undef setjmp 263 # define setjmp_undefined_for_msvc 264 #endif 265 266 case Intrinsic::setjmp: 267 268 #if defined(_MSC_VER) && defined(setjmp_undefined_for_msvc) 269 // let's return it to _setjmp state 270 # pragma pop_macro("setjmp") 271 # undef setjmp_undefined_for_msvc 272 #endif 273 274 case Intrinsic::longjmp: 275 276 // Exclude eh_sjlj_setjmp; we don't need to exclude eh_sjlj_longjmp 277 // because, although it does clobber the counter register, the 278 // control can't then return to inside the loop unless there is also 279 // an eh_sjlj_setjmp. 280 case Intrinsic::eh_sjlj_setjmp: 281 282 case Intrinsic::memcpy: 283 case Intrinsic::memmove: 284 case Intrinsic::memset: 285 case Intrinsic::powi: 286 case Intrinsic::log: 287 case Intrinsic::log2: 288 case Intrinsic::log10: 289 case Intrinsic::exp: 290 case Intrinsic::exp2: 291 case Intrinsic::pow: 292 case Intrinsic::sin: 293 case Intrinsic::cos: 294 return true; 295 case Intrinsic::copysign: 296 if (CI->getArgOperand(0)->getType()->getScalarType()-> 297 isPPC_FP128Ty()) 298 return true; 299 else 300 continue; // ISD::FCOPYSIGN is never a library call. 301 case Intrinsic::sqrt: Opcode = ISD::FSQRT; break; 302 case Intrinsic::floor: Opcode = ISD::FFLOOR; break; 303 case Intrinsic::ceil: Opcode = ISD::FCEIL; break; 304 case Intrinsic::trunc: Opcode = ISD::FTRUNC; break; 305 case Intrinsic::rint: Opcode = ISD::FRINT; break; 306 case Intrinsic::nearbyint: Opcode = ISD::FNEARBYINT; break; 307 case Intrinsic::round: Opcode = ISD::FROUND; break; 308 case Intrinsic::minnum: Opcode = ISD::FMINNUM; break; 309 case Intrinsic::maxnum: Opcode = ISD::FMAXNUM; break; 310 } 311 } 312 313 // PowerPC does not use [US]DIVREM or other library calls for 314 // operations on regular types which are not otherwise library calls 315 // (i.e. soft float or atomics). If adapting for targets that do, 316 // additional care is required here. 317 318 LibFunc::Func Func; 319 if (!F->hasLocalLinkage() && F->hasName() && LibInfo && 320 LibInfo->getLibFunc(F->getName(), Func) && 321 LibInfo->hasOptimizedCodeGen(Func)) { 322 // Non-read-only functions are never treated as intrinsics. 323 if (!CI->onlyReadsMemory()) 324 return true; 325 326 // Conversion happens only for FP calls. 327 if (!CI->getArgOperand(0)->getType()->isFloatingPointTy()) 328 return true; 329 330 switch (Func) { 331 default: return true; 332 case LibFunc::copysign: 333 case LibFunc::copysignf: 334 continue; // ISD::FCOPYSIGN is never a library call. 335 case LibFunc::copysignl: 336 return true; 337 case LibFunc::fabs: 338 case LibFunc::fabsf: 339 case LibFunc::fabsl: 340 continue; // ISD::FABS is never a library call. 341 case LibFunc::sqrt: 342 case LibFunc::sqrtf: 343 case LibFunc::sqrtl: 344 Opcode = ISD::FSQRT; break; 345 case LibFunc::floor: 346 case LibFunc::floorf: 347 case LibFunc::floorl: 348 Opcode = ISD::FFLOOR; break; 349 case LibFunc::nearbyint: 350 case LibFunc::nearbyintf: 351 case LibFunc::nearbyintl: 352 Opcode = ISD::FNEARBYINT; break; 353 case LibFunc::ceil: 354 case LibFunc::ceilf: 355 case LibFunc::ceill: 356 Opcode = ISD::FCEIL; break; 357 case LibFunc::rint: 358 case LibFunc::rintf: 359 case LibFunc::rintl: 360 Opcode = ISD::FRINT; break; 361 case LibFunc::round: 362 case LibFunc::roundf: 363 case LibFunc::roundl: 364 Opcode = ISD::FROUND; break; 365 case LibFunc::trunc: 366 case LibFunc::truncf: 367 case LibFunc::truncl: 368 Opcode = ISD::FTRUNC; break; 369 case LibFunc::fmin: 370 case LibFunc::fminf: 371 case LibFunc::fminl: 372 Opcode = ISD::FMINNUM; break; 373 case LibFunc::fmax: 374 case LibFunc::fmaxf: 375 case LibFunc::fmaxl: 376 Opcode = ISD::FMAXNUM; break; 377 } 378 } 379 380 if (Opcode) { 381 auto &DL = CI->getModule()->getDataLayout(); 382 MVT VTy = TLI->getSimpleValueType(DL, CI->getArgOperand(0)->getType(), 383 true); 384 if (VTy == MVT::Other) 385 return true; 386 387 if (TLI->isOperationLegalOrCustom(Opcode, VTy)) 388 continue; 389 else if (VTy.isVector() && 390 TLI->isOperationLegalOrCustom(Opcode, VTy.getScalarType())) 391 continue; 392 393 return true; 394 } 395 } 396 397 return true; 398 } else if (isa<BinaryOperator>(J) && 399 J->getType()->getScalarType()->isPPC_FP128Ty()) { 400 // Most operations on ppc_f128 values become calls. 401 return true; 402 } else if (isa<UIToFPInst>(J) || isa<SIToFPInst>(J) || 403 isa<FPToUIInst>(J) || isa<FPToSIInst>(J)) { 404 CastInst *CI = cast<CastInst>(J); 405 if (CI->getSrcTy()->getScalarType()->isPPC_FP128Ty() || 406 CI->getDestTy()->getScalarType()->isPPC_FP128Ty() || 407 isLargeIntegerTy(TT.isArch32Bit(), CI->getSrcTy()->getScalarType()) || 408 isLargeIntegerTy(TT.isArch32Bit(), CI->getDestTy()->getScalarType())) 409 return true; 410 } else if (isLargeIntegerTy(TT.isArch32Bit(), 411 J->getType()->getScalarType()) && 412 (J->getOpcode() == Instruction::UDiv || 413 J->getOpcode() == Instruction::SDiv || 414 J->getOpcode() == Instruction::URem || 415 J->getOpcode() == Instruction::SRem)) { 416 return true; 417 } else if (TT.isArch32Bit() && 418 isLargeIntegerTy(false, J->getType()->getScalarType()) && 419 (J->getOpcode() == Instruction::Shl || 420 J->getOpcode() == Instruction::AShr || 421 J->getOpcode() == Instruction::LShr)) { 422 // Only on PPC32, for 128-bit integers (specifically not 64-bit 423 // integers), these might be runtime calls. 424 return true; 425 } else if (isa<IndirectBrInst>(J) || isa<InvokeInst>(J)) { 426 // On PowerPC, indirect jumps use the counter register. 427 return true; 428 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(J)) { 429 if (!TM) 430 return true; 431 const TargetLowering *TLI = 432 TM->getSubtargetImpl(*BB->getParent())->getTargetLowering(); 433 434 if (SI->getNumCases() + 1 >= (unsigned)TLI->getMinimumJumpTableEntries()) 435 return true; 436 } 437 438 if (TM->getSubtargetImpl(*BB->getParent())->getTargetLowering()->useSoftFloat()) { 439 switch(J->getOpcode()) { 440 case Instruction::FAdd: 441 case Instruction::FSub: 442 case Instruction::FMul: 443 case Instruction::FDiv: 444 case Instruction::FRem: 445 case Instruction::FPTrunc: 446 case Instruction::FPExt: 447 case Instruction::FPToUI: 448 case Instruction::FPToSI: 449 case Instruction::UIToFP: 450 case Instruction::SIToFP: 451 case Instruction::FCmp: 452 return true; 453 } 454 } 455 456 for (Value *Operand : J->operands()) 457 if (memAddrUsesCTR(TM, Operand)) 458 return true; 459 } 460 461 return false; 462 } 463 464 bool PPCCTRLoops::convertToCTRLoop(Loop *L) { 465 bool MadeChange = false; 466 467 const Triple TT = 468 Triple(L->getHeader()->getParent()->getParent()->getTargetTriple()); 469 if (!TT.isArch32Bit() && !TT.isArch64Bit()) 470 return MadeChange; // Unknown arch. type. 471 472 // Process nested loops first. 473 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) { 474 MadeChange |= convertToCTRLoop(*I); 475 DEBUG(dbgs() << "Nested loop converted\n"); 476 } 477 478 // If a nested loop has been converted, then we can't convert this loop. 479 if (MadeChange) 480 return MadeChange; 481 482 #ifndef NDEBUG 483 // Stop trying after reaching the limit (if any). 484 int Limit = CTRLoopLimit; 485 if (Limit >= 0) { 486 if (Counter >= CTRLoopLimit) 487 return false; 488 Counter++; 489 } 490 #endif 491 492 // We don't want to spill/restore the counter register, and so we don't 493 // want to use the counter register if the loop contains calls. 494 for (Loop::block_iterator I = L->block_begin(), IE = L->block_end(); 495 I != IE; ++I) 496 if (mightUseCTR(TT, *I)) 497 return MadeChange; 498 499 SmallVector<BasicBlock*, 4> ExitingBlocks; 500 L->getExitingBlocks(ExitingBlocks); 501 502 BasicBlock *CountedExitBlock = nullptr; 503 const SCEV *ExitCount = nullptr; 504 BranchInst *CountedExitBranch = nullptr; 505 for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(), 506 IE = ExitingBlocks.end(); I != IE; ++I) { 507 const SCEV *EC = SE->getExitCount(L, *I); 508 DEBUG(dbgs() << "Exit Count for " << *L << " from block " << 509 (*I)->getName() << ": " << *EC << "\n"); 510 if (isa<SCEVCouldNotCompute>(EC)) 511 continue; 512 if (const SCEVConstant *ConstEC = dyn_cast<SCEVConstant>(EC)) { 513 if (ConstEC->getValue()->isZero()) 514 continue; 515 } else if (!SE->isLoopInvariant(EC, L)) 516 continue; 517 518 if (SE->getTypeSizeInBits(EC->getType()) > (TT.isArch64Bit() ? 64 : 32)) 519 continue; 520 521 // We now have a loop-invariant count of loop iterations (which is not the 522 // constant zero) for which we know that this loop will not exit via this 523 // exisiting block. 524 525 // We need to make sure that this block will run on every loop iteration. 526 // For this to be true, we must dominate all blocks with backedges. Such 527 // blocks are in-loop predecessors to the header block. 528 bool NotAlways = false; 529 for (pred_iterator PI = pred_begin(L->getHeader()), 530 PIE = pred_end(L->getHeader()); PI != PIE; ++PI) { 531 if (!L->contains(*PI)) 532 continue; 533 534 if (!DT->dominates(*I, *PI)) { 535 NotAlways = true; 536 break; 537 } 538 } 539 540 if (NotAlways) 541 continue; 542 543 // Make sure this blocks ends with a conditional branch. 544 Instruction *TI = (*I)->getTerminator(); 545 if (!TI) 546 continue; 547 548 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 549 if (!BI->isConditional()) 550 continue; 551 552 CountedExitBranch = BI; 553 } else 554 continue; 555 556 // Note that this block may not be the loop latch block, even if the loop 557 // has a latch block. 558 CountedExitBlock = *I; 559 ExitCount = EC; 560 break; 561 } 562 563 if (!CountedExitBlock) 564 return MadeChange; 565 566 BasicBlock *Preheader = L->getLoopPreheader(); 567 568 // If we don't have a preheader, then insert one. If we already have a 569 // preheader, then we can use it (except if the preheader contains a use of 570 // the CTR register because some such uses might be reordered by the 571 // selection DAG after the mtctr instruction). 572 if (!Preheader || mightUseCTR(TT, Preheader)) 573 Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA); 574 if (!Preheader) 575 return MadeChange; 576 577 DEBUG(dbgs() << "Preheader for exit count: " << Preheader->getName() << "\n"); 578 579 // Insert the count into the preheader and replace the condition used by the 580 // selected branch. 581 MadeChange = true; 582 583 SCEVExpander SCEVE(*SE, Preheader->getModule()->getDataLayout(), "loopcnt"); 584 LLVMContext &C = SE->getContext(); 585 Type *CountType = TT.isArch64Bit() ? Type::getInt64Ty(C) : 586 Type::getInt32Ty(C); 587 if (!ExitCount->getType()->isPointerTy() && 588 ExitCount->getType() != CountType) 589 ExitCount = SE->getZeroExtendExpr(ExitCount, CountType); 590 ExitCount = SE->getAddExpr(ExitCount, SE->getOne(CountType)); 591 Value *ECValue = 592 SCEVE.expandCodeFor(ExitCount, CountType, Preheader->getTerminator()); 593 594 IRBuilder<> CountBuilder(Preheader->getTerminator()); 595 Module *M = Preheader->getParent()->getParent(); 596 Value *MTCTRFunc = Intrinsic::getDeclaration(M, Intrinsic::ppc_mtctr, 597 CountType); 598 CountBuilder.CreateCall(MTCTRFunc, ECValue); 599 600 IRBuilder<> CondBuilder(CountedExitBranch); 601 Value *DecFunc = 602 Intrinsic::getDeclaration(M, Intrinsic::ppc_is_decremented_ctr_nonzero); 603 Value *NewCond = CondBuilder.CreateCall(DecFunc, {}); 604 Value *OldCond = CountedExitBranch->getCondition(); 605 CountedExitBranch->setCondition(NewCond); 606 607 // The false branch must exit the loop. 608 if (!L->contains(CountedExitBranch->getSuccessor(0))) 609 CountedExitBranch->swapSuccessors(); 610 611 // The old condition may be dead now, and may have even created a dead PHI 612 // (the original induction variable). 613 RecursivelyDeleteTriviallyDeadInstructions(OldCond); 614 DeleteDeadPHIs(CountedExitBlock); 615 616 ++NumCTRLoops; 617 return MadeChange; 618 } 619 620 #ifndef NDEBUG 621 static bool clobbersCTR(const MachineInstr *MI) { 622 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 623 const MachineOperand &MO = MI->getOperand(i); 624 if (MO.isReg()) { 625 if (MO.isDef() && (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8)) 626 return true; 627 } else if (MO.isRegMask()) { 628 if (MO.clobbersPhysReg(PPC::CTR) || MO.clobbersPhysReg(PPC::CTR8)) 629 return true; 630 } 631 } 632 633 return false; 634 } 635 636 static bool verifyCTRBranch(MachineBasicBlock *MBB, 637 MachineBasicBlock::iterator I) { 638 MachineBasicBlock::iterator BI = I; 639 SmallSet<MachineBasicBlock *, 16> Visited; 640 SmallVector<MachineBasicBlock *, 8> Preds; 641 bool CheckPreds; 642 643 if (I == MBB->begin()) { 644 Visited.insert(MBB); 645 goto queue_preds; 646 } else 647 --I; 648 649 check_block: 650 Visited.insert(MBB); 651 if (I == MBB->end()) 652 goto queue_preds; 653 654 CheckPreds = true; 655 for (MachineBasicBlock::iterator IE = MBB->begin();; --I) { 656 unsigned Opc = I->getOpcode(); 657 if (Opc == PPC::MTCTRloop || Opc == PPC::MTCTR8loop) { 658 CheckPreds = false; 659 break; 660 } 661 662 if (I != BI && clobbersCTR(I)) { 663 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " (" << 664 MBB->getFullName() << ") instruction " << *I << 665 " clobbers CTR, invalidating " << "BB#" << 666 BI->getParent()->getNumber() << " (" << 667 BI->getParent()->getFullName() << ") instruction " << 668 *BI << "\n"); 669 return false; 670 } 671 672 if (I == IE) 673 break; 674 } 675 676 if (!CheckPreds && Preds.empty()) 677 return true; 678 679 if (CheckPreds) { 680 queue_preds: 681 if (MachineFunction::iterator(MBB) == MBB->getParent()->begin()) { 682 DEBUG(dbgs() << "Unable to find a MTCTR instruction for BB#" << 683 BI->getParent()->getNumber() << " (" << 684 BI->getParent()->getFullName() << ") instruction " << 685 *BI << "\n"); 686 return false; 687 } 688 689 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 690 PIE = MBB->pred_end(); PI != PIE; ++PI) 691 Preds.push_back(*PI); 692 } 693 694 do { 695 MBB = Preds.pop_back_val(); 696 if (!Visited.count(MBB)) { 697 I = MBB->getLastNonDebugInstr(); 698 goto check_block; 699 } 700 } while (!Preds.empty()); 701 702 return true; 703 } 704 705 bool PPCCTRLoopsVerify::runOnMachineFunction(MachineFunction &MF) { 706 MDT = &getAnalysis<MachineDominatorTree>(); 707 708 // Verify that all bdnz/bdz instructions are dominated by a loop mtctr before 709 // any other instructions that might clobber the ctr register. 710 for (MachineFunction::iterator I = MF.begin(), IE = MF.end(); 711 I != IE; ++I) { 712 MachineBasicBlock *MBB = &*I; 713 if (!MDT->isReachableFromEntry(MBB)) 714 continue; 715 716 for (MachineBasicBlock::iterator MII = MBB->getFirstTerminator(), 717 MIIE = MBB->end(); MII != MIIE; ++MII) { 718 unsigned Opc = MII->getOpcode(); 719 if (Opc == PPC::BDNZ8 || Opc == PPC::BDNZ || 720 Opc == PPC::BDZ8 || Opc == PPC::BDZ) 721 if (!verifyCTRBranch(MBB, MII)) 722 llvm_unreachable("Invalid PPC CTR loop!"); 723 } 724 } 725 726 return false; 727 } 728 #endif // NDEBUG 729
