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 66using namespace llvm; 67 68#define DEBUG_TYPE "ctrloops" 69 70#ifndef NDEBUG 71static cl::opt<int> CTRLoopLimit("ppc-max-ctrloop", cl::Hidden, cl::init(-1)); 72#endif 73 74namespace { 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 101INITIALIZE_PASS_BEGIN(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", 102 "PowerPC CTR Loops Verify", false, false) 103INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 104INITIALIZE_PASS_END(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", 105 "PowerPC CTR Loops Verify", false, false) 106 107FunctionPass *llvm::createPPCCTRLoopsVerify() { 108 return new PPCCTRLoopsVerify(); 109} 110#endif // NDEBUG 111 112#ifndef NDEBUG 113static 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 128static 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 141check_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) { 172queue_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 197bool 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