1 //===-- PPCCTRLoops.cpp - Identify and generate CTR loops -----------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This pass identifies loops where we can generate the PPC branch instructions 10 // that decrement and test the count register (CTR) (bdnz and friends). 11 // 12 // The pattern that defines the induction variable can changed depending on 13 // prior optimizations. For example, the IndVarSimplify phase run by 'opt' 14 // normalizes induction variables, and the Loop Strength Reduction pass 15 // run by 'llc' may also make changes to the induction variable. 16 // 17 // Criteria for CTR loops: 18 // - Countable loops (w/ ind. var for a trip count) 19 // - Try inner-most loops first 20 // - No nested CTR loops. 21 // - No function calls in loops. 22 // 23 //===----------------------------------------------------------------------===// 24 25 #include "PPC.h" 26 #include "PPCSubtarget.h" 27 #include "PPCTargetMachine.h" 28 #include "PPCTargetTransformInfo.h" 29 #include "llvm/ADT/STLExtras.h" 30 #include "llvm/ADT/Statistic.h" 31 #include "llvm/Analysis/AssumptionCache.h" 32 #include "llvm/Analysis/CFG.h" 33 #include "llvm/Analysis/CodeMetrics.h" 34 #include "llvm/Analysis/LoopInfo.h" 35 #include "llvm/Analysis/LoopIterator.h" 36 #include "llvm/Analysis/ScalarEvolutionExpander.h" 37 #include "llvm/Analysis/TargetLibraryInfo.h" 38 #include "llvm/Analysis/TargetTransformInfo.h" 39 #include "llvm/CodeGen/TargetPassConfig.h" 40 #include "llvm/CodeGen/TargetSchedule.h" 41 #include "llvm/IR/Constants.h" 42 #include "llvm/IR/DerivedTypes.h" 43 #include "llvm/IR/Dominators.h" 44 #include "llvm/IR/InlineAsm.h" 45 #include "llvm/IR/Instructions.h" 46 #include "llvm/IR/IntrinsicInst.h" 47 #include "llvm/IR/Module.h" 48 #include "llvm/IR/ValueHandle.h" 49 #include "llvm/InitializePasses.h" 50 #include "llvm/PassSupport.h" 51 #include "llvm/Support/CommandLine.h" 52 #include "llvm/Support/Debug.h" 53 #include "llvm/Support/raw_ostream.h" 54 #include "llvm/Transforms/Scalar.h" 55 #include "llvm/Transforms/Utils.h" 56 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 57 #include "llvm/Transforms/Utils/Local.h" 58 #include "llvm/Transforms/Utils/LoopUtils.h" 59 60 #ifndef NDEBUG 61 #include "llvm/CodeGen/MachineDominators.h" 62 #include "llvm/CodeGen/MachineFunction.h" 63 #include "llvm/CodeGen/MachineFunctionPass.h" 64 #include "llvm/CodeGen/MachineRegisterInfo.h" 65 #endif 66 67 using namespace llvm; 68 69 #define DEBUG_TYPE "ctrloops" 70 71 #ifndef NDEBUG 72 static cl::opt<int> CTRLoopLimit("ppc-max-ctrloop", cl::Hidden, cl::init(-1)); 73 #endif 74 75 namespace { 76 77 #ifndef NDEBUG 78 struct PPCCTRLoopsVerify : public MachineFunctionPass { 79 public: 80 static char ID; 81 82 PPCCTRLoopsVerify() : MachineFunctionPass(ID) { 83 initializePPCCTRLoopsVerifyPass(*PassRegistry::getPassRegistry()); 84 } 85 86 void getAnalysisUsage(AnalysisUsage &AU) const override { 87 AU.addRequired<MachineDominatorTree>(); 88 MachineFunctionPass::getAnalysisUsage(AU); 89 } 90 91 bool runOnMachineFunction(MachineFunction &MF) override; 92 93 private: 94 MachineDominatorTree *MDT; 95 }; 96 97 char PPCCTRLoopsVerify::ID = 0; 98 #endif // NDEBUG 99 } // end anonymous namespace 100 101 #ifndef NDEBUG 102 INITIALIZE_PASS_BEGIN(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", 103 "PowerPC CTR Loops Verify", false, false) 104 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 105 INITIALIZE_PASS_END(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", 106 "PowerPC CTR Loops Verify", false, false) 107 108 FunctionPass *llvm::createPPCCTRLoopsVerify() { 109 return new PPCCTRLoopsVerify(); 110 } 111 #endif // NDEBUG 112 113 #ifndef NDEBUG 114 static bool clobbersCTR(const MachineInstr &MI) { 115 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 116 const MachineOperand &MO = MI.getOperand(i); 117 if (MO.isReg()) { 118 if (MO.isDef() && (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8)) 119 return true; 120 } else if (MO.isRegMask()) { 121 if (MO.clobbersPhysReg(PPC::CTR) || MO.clobbersPhysReg(PPC::CTR8)) 122 return true; 123 } 124 } 125 126 return false; 127 } 128 129 static bool verifyCTRBranch(MachineBasicBlock *MBB, 130 MachineBasicBlock::iterator I) { 131 MachineBasicBlock::iterator BI = I; 132 SmallSet<MachineBasicBlock *, 16> Visited; 133 SmallVector<MachineBasicBlock *, 8> Preds; 134 bool CheckPreds; 135 136 if (I == MBB->begin()) { 137 Visited.insert(MBB); 138 goto queue_preds; 139 } else 140 --I; 141 142 check_block: 143 Visited.insert(MBB); 144 if (I == MBB->end()) 145 goto queue_preds; 146 147 CheckPreds = true; 148 for (MachineBasicBlock::iterator IE = MBB->begin();; --I) { 149 unsigned Opc = I->getOpcode(); 150 if (Opc == PPC::MTCTRloop || Opc == PPC::MTCTR8loop) { 151 CheckPreds = false; 152 break; 153 } 154 155 if (I != BI && clobbersCTR(*I)) { 156 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " (" << MBB->getFullName() 157 << ") instruction " << *I 158 << " clobbers CTR, invalidating " 159 << printMBBReference(*BI->getParent()) << " (" 160 << BI->getParent()->getFullName() << ") instruction " 161 << *BI << "\n"); 162 return false; 163 } 164 165 if (I == IE) 166 break; 167 } 168 169 if (!CheckPreds && Preds.empty()) 170 return true; 171 172 if (CheckPreds) { 173 queue_preds: 174 if (MachineFunction::iterator(MBB) == MBB->getParent()->begin()) { 175 LLVM_DEBUG(dbgs() << "Unable to find a MTCTR instruction for " 176 << printMBBReference(*BI->getParent()) << " (" 177 << BI->getParent()->getFullName() << ") instruction " 178 << *BI << "\n"); 179 return false; 180 } 181 182 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 183 PIE = MBB->pred_end(); PI != PIE; ++PI) 184 Preds.push_back(*PI); 185 } 186 187 do { 188 MBB = Preds.pop_back_val(); 189 if (!Visited.count(MBB)) { 190 I = MBB->getLastNonDebugInstr(); 191 goto check_block; 192 } 193 } while (!Preds.empty()); 194 195 return true; 196 } 197 198 bool PPCCTRLoopsVerify::runOnMachineFunction(MachineFunction &MF) { 199 MDT = &getAnalysis<MachineDominatorTree>(); 200 201 // Verify that all bdnz/bdz instructions are dominated by a loop mtctr before 202 // any other instructions that might clobber the ctr register. 203 for (MachineFunction::iterator I = MF.begin(), IE = MF.end(); 204 I != IE; ++I) { 205 MachineBasicBlock *MBB = &*I; 206 if (!MDT->isReachableFromEntry(MBB)) 207 continue; 208 209 for (MachineBasicBlock::iterator MII = MBB->getFirstTerminator(), 210 MIIE = MBB->end(); MII != MIIE; ++MII) { 211 unsigned Opc = MII->getOpcode(); 212 if (Opc == PPC::BDNZ8 || Opc == PPC::BDNZ || 213 Opc == PPC::BDZ8 || Opc == PPC::BDZ) 214 if (!verifyCTRBranch(MBB, MII)) 215 llvm_unreachable("Invalid PPC CTR loop!"); 216 } 217 } 218 219 return false; 220 } 221 #endif // NDEBUG 222