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/TargetLibraryInfo.h" 37 #include "llvm/Analysis/TargetTransformInfo.h" 38 #include "llvm/CodeGen/TargetPassConfig.h" 39 #include "llvm/CodeGen/TargetSchedule.h" 40 #include "llvm/IR/Constants.h" 41 #include "llvm/IR/DerivedTypes.h" 42 #include "llvm/IR/Dominators.h" 43 #include "llvm/IR/InlineAsm.h" 44 #include "llvm/IR/Instructions.h" 45 #include "llvm/IR/IntrinsicInst.h" 46 #include "llvm/IR/Module.h" 47 #include "llvm/IR/ValueHandle.h" 48 #include "llvm/InitializePasses.h" 49 #include "llvm/PassSupport.h" 50 #include "llvm/Support/CommandLine.h" 51 #include "llvm/Support/Debug.h" 52 #include "llvm/Support/raw_ostream.h" 53 #include "llvm/Transforms/Scalar.h" 54 #include "llvm/Transforms/Utils.h" 55 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 56 #include "llvm/Transforms/Utils/Local.h" 57 #include "llvm/Transforms/Utils/LoopUtils.h" 58 59 #ifndef NDEBUG 60 #include "llvm/CodeGen/MachineDominators.h" 61 #include "llvm/CodeGen/MachineFunction.h" 62 #include "llvm/CodeGen/MachineFunctionPass.h" 63 #include "llvm/CodeGen/MachineRegisterInfo.h" 64 #endif 65 66 using namespace llvm; 67 68 #define DEBUG_TYPE "ctrloops" 69 70 #ifndef NDEBUG 71 static cl::opt<int> CTRLoopLimit("ppc-max-ctrloop", cl::Hidden, cl::init(-1)); 72 #endif 73 74 namespace { 75 76 #ifndef NDEBUG 77 struct PPCCTRLoopsVerify : public MachineFunctionPass { 78 public: 79 static char ID; 80 81 PPCCTRLoopsVerify() : MachineFunctionPass(ID) { 82 initializePPCCTRLoopsVerifyPass(*PassRegistry::getPassRegistry()); 83 } 84 85 void getAnalysisUsage(AnalysisUsage &AU) const override { 86 AU.addRequired<MachineDominatorTree>(); 87 MachineFunctionPass::getAnalysisUsage(AU); 88 } 89 90 bool runOnMachineFunction(MachineFunction &MF) override; 91 92 private: 93 MachineDominatorTree *MDT; 94 }; 95 96 char PPCCTRLoopsVerify::ID = 0; 97 #endif // NDEBUG 98 } // end anonymous namespace 99 100 #ifndef NDEBUG 101 INITIALIZE_PASS_BEGIN(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", 102 "PowerPC CTR Loops Verify", false, false) 103 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 104 INITIALIZE_PASS_END(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", 105 "PowerPC CTR Loops Verify", false, false) 106 107 FunctionPass *llvm::createPPCCTRLoopsVerify() { 108 return new PPCCTRLoopsVerify(); 109 } 110 #endif // NDEBUG 111 112 #ifndef NDEBUG 113 static bool clobbersCTR(const MachineInstr &MI) { 114 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 115 const MachineOperand &MO = MI.getOperand(i); 116 if (MO.isReg()) { 117 if (MO.isDef() && (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8)) 118 return true; 119 } else if (MO.isRegMask()) { 120 if (MO.clobbersPhysReg(PPC::CTR) || MO.clobbersPhysReg(PPC::CTR8)) 121 return true; 122 } 123 } 124 125 return false; 126 } 127 128 static bool verifyCTRBranch(MachineBasicBlock *MBB, 129 MachineBasicBlock::iterator I) { 130 MachineBasicBlock::iterator BI = I; 131 SmallSet<MachineBasicBlock *, 16> Visited; 132 SmallVector<MachineBasicBlock *, 8> Preds; 133 bool CheckPreds; 134 135 if (I == MBB->begin()) { 136 Visited.insert(MBB); 137 goto queue_preds; 138 } else 139 --I; 140 141 check_block: 142 Visited.insert(MBB); 143 if (I == MBB->end()) 144 goto queue_preds; 145 146 CheckPreds = true; 147 for (MachineBasicBlock::iterator IE = MBB->begin();; --I) { 148 unsigned Opc = I->getOpcode(); 149 if (Opc == PPC::MTCTRloop || Opc == PPC::MTCTR8loop) { 150 CheckPreds = false; 151 break; 152 } 153 154 if (I != BI && clobbersCTR(*I)) { 155 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " (" << MBB->getFullName() 156 << ") instruction " << *I 157 << " clobbers CTR, invalidating " 158 << printMBBReference(*BI->getParent()) << " (" 159 << BI->getParent()->getFullName() << ") instruction " 160 << *BI << "\n"); 161 return false; 162 } 163 164 if (I == IE) 165 break; 166 } 167 168 if (!CheckPreds && Preds.empty()) 169 return true; 170 171 if (CheckPreds) { 172 queue_preds: 173 if (MachineFunction::iterator(MBB) == MBB->getParent()->begin()) { 174 LLVM_DEBUG(dbgs() << "Unable to find a MTCTR instruction for " 175 << printMBBReference(*BI->getParent()) << " (" 176 << BI->getParent()->getFullName() << ") instruction " 177 << *BI << "\n"); 178 return false; 179 } 180 181 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 182 PIE = MBB->pred_end(); PI != PIE; ++PI) 183 Preds.push_back(*PI); 184 } 185 186 do { 187 MBB = Preds.pop_back_val(); 188 if (!Visited.count(MBB)) { 189 I = MBB->getLastNonDebugInstr(); 190 goto check_block; 191 } 192 } while (!Preds.empty()); 193 194 return true; 195 } 196 197 bool PPCCTRLoopsVerify::runOnMachineFunction(MachineFunction &MF) { 198 MDT = &getAnalysis<MachineDominatorTree>(); 199 200 // Verify that all bdnz/bdz instructions are dominated by a loop mtctr before 201 // any other instructions that might clobber the ctr register. 202 for (MachineFunction::iterator I = MF.begin(), IE = MF.end(); 203 I != IE; ++I) { 204 MachineBasicBlock *MBB = &*I; 205 if (!MDT->isReachableFromEntry(MBB)) 206 continue; 207 208 for (MachineBasicBlock::iterator MII = MBB->getFirstTerminator(), 209 MIIE = MBB->end(); MII != MIIE; ++MII) { 210 unsigned Opc = MII->getOpcode(); 211 if (Opc == PPC::BDNZ8 || Opc == PPC::BDNZ || 212 Opc == PPC::BDZ8 || Opc == PPC::BDZ) 213 if (!verifyCTRBranch(MBB, MII)) 214 llvm_unreachable("Invalid PPC CTR loop!"); 215 } 216 } 217 218 return false; 219 } 220 #endif // NDEBUG 221