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