1 //===-- PPCCTRLoops.cpp - Verify 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 verifies that all bdnz/bdz instructions are dominated by a loop 10 // mtctr before any other instructions that might clobber the ctr register. 11 // 12 //===----------------------------------------------------------------------===// 13 14 // CTR loops are produced by the HardwareLoops pass and this pass is simply a 15 // verification that no invalid CTR loops are produced. As such, it isn't 16 // something that needs to be run (or even defined) for Release builds so the 17 // entire file is guarded by NDEBUG. 18 #ifndef NDEBUG 19 #include "MCTargetDesc/PPCMCTargetDesc.h" 20 #include "PPC.h" 21 #include "llvm/ADT/SmallSet.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/ADT/StringRef.h" 24 #include "llvm/ADT/ilist_iterator.h" 25 #include "llvm/CodeGen/MachineBasicBlock.h" 26 #include "llvm/CodeGen/MachineDominators.h" 27 #include "llvm/CodeGen/MachineFunction.h" 28 #include "llvm/CodeGen/MachineFunctionPass.h" 29 #include "llvm/CodeGen/MachineInstr.h" 30 #include "llvm/CodeGen/MachineInstrBundleIterator.h" 31 #include "llvm/CodeGen/MachineOperand.h" 32 #include "llvm/CodeGen/Register.h" 33 #include "llvm/InitializePasses.h" 34 #include "llvm/Pass.h" 35 #include "llvm/PassRegistry.h" 36 #include "llvm/Support/CodeGen.h" 37 #include "llvm/Support/Debug.h" 38 #include "llvm/Support/ErrorHandling.h" 39 #include "llvm/Support/GenericDomTreeConstruction.h" 40 #include "llvm/Support/Printable.h" 41 #include "llvm/Support/raw_ostream.h" 42 43 using namespace llvm; 44 45 #define DEBUG_TYPE "ppc-ctrloops-verify" 46 47 namespace { 48 49 struct PPCCTRLoopsVerify : public MachineFunctionPass { 50 public: 51 static char ID; 52 53 PPCCTRLoopsVerify() : MachineFunctionPass(ID) { 54 initializePPCCTRLoopsVerifyPass(*PassRegistry::getPassRegistry()); 55 } 56 57 void getAnalysisUsage(AnalysisUsage &AU) const override { 58 AU.addRequired<MachineDominatorTree>(); 59 MachineFunctionPass::getAnalysisUsage(AU); 60 } 61 62 bool runOnMachineFunction(MachineFunction &MF) override; 63 64 private: 65 MachineDominatorTree *MDT; 66 }; 67 68 char PPCCTRLoopsVerify::ID = 0; 69 } // end anonymous namespace 70 71 INITIALIZE_PASS_BEGIN(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", 72 "PowerPC CTR Loops Verify", false, false) 73 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 74 INITIALIZE_PASS_END(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", 75 "PowerPC CTR Loops Verify", false, false) 76 77 FunctionPass *llvm::createPPCCTRLoopsVerify() { 78 return new PPCCTRLoopsVerify(); 79 } 80 81 static bool clobbersCTR(const MachineInstr &MI) { 82 for (const MachineOperand &MO : MI.operands()) { 83 if (MO.isReg()) { 84 if (MO.isDef() && (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8)) 85 return true; 86 } else if (MO.isRegMask()) { 87 if (MO.clobbersPhysReg(PPC::CTR) || MO.clobbersPhysReg(PPC::CTR8)) 88 return true; 89 } 90 } 91 92 return false; 93 } 94 95 static bool verifyCTRBranch(MachineBasicBlock *MBB, 96 MachineBasicBlock::iterator I) { 97 MachineBasicBlock::iterator BI = I; 98 SmallSet<MachineBasicBlock *, 16> Visited; 99 SmallVector<MachineBasicBlock *, 8> Preds; 100 bool CheckPreds; 101 102 if (I == MBB->begin()) { 103 Visited.insert(MBB); 104 goto queue_preds; 105 } else 106 --I; 107 108 check_block: 109 Visited.insert(MBB); 110 if (I == MBB->end()) 111 goto queue_preds; 112 113 CheckPreds = true; 114 for (MachineBasicBlock::iterator IE = MBB->begin();; --I) { 115 unsigned Opc = I->getOpcode(); 116 if (Opc == PPC::MTCTRloop || Opc == PPC::MTCTR8loop) { 117 CheckPreds = false; 118 break; 119 } 120 121 if (I != BI && clobbersCTR(*I)) { 122 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " (" << MBB->getFullName() 123 << ") instruction " << *I 124 << " clobbers CTR, invalidating " 125 << printMBBReference(*BI->getParent()) << " (" 126 << BI->getParent()->getFullName() << ") instruction " 127 << *BI << "\n"); 128 return false; 129 } 130 131 if (I == IE) 132 break; 133 } 134 135 if (!CheckPreds && Preds.empty()) 136 return true; 137 138 if (CheckPreds) { 139 queue_preds: 140 if (MachineFunction::iterator(MBB) == MBB->getParent()->begin()) { 141 LLVM_DEBUG(dbgs() << "Unable to find a MTCTR instruction for " 142 << printMBBReference(*BI->getParent()) << " (" 143 << BI->getParent()->getFullName() << ") instruction " 144 << *BI << "\n"); 145 return false; 146 } 147 148 append_range(Preds, MBB->predecessors()); 149 } 150 151 do { 152 MBB = Preds.pop_back_val(); 153 if (!Visited.count(MBB)) { 154 I = MBB->getLastNonDebugInstr(); 155 goto check_block; 156 } 157 } while (!Preds.empty()); 158 159 return true; 160 } 161 162 bool PPCCTRLoopsVerify::runOnMachineFunction(MachineFunction &MF) { 163 MDT = &getAnalysis<MachineDominatorTree>(); 164 165 // Verify that all bdnz/bdz instructions are dominated by a loop mtctr before 166 // any other instructions that might clobber the ctr register. 167 for (MachineBasicBlock &MBB : MF) { 168 if (!MDT->isReachableFromEntry(&MBB)) 169 continue; 170 171 for (MachineBasicBlock::iterator MII = MBB.getFirstTerminator(), 172 MIIE = MBB.end(); MII != MIIE; ++MII) { 173 unsigned Opc = MII->getOpcode(); 174 if (Opc == PPC::BDNZ8 || Opc == PPC::BDNZ || 175 Opc == PPC::BDZ8 || Opc == PPC::BDZ) 176 if (!verifyCTRBranch(&MBB, MII)) 177 llvm_unreachable("Invalid PPC CTR loop!"); 178 } 179 } 180 181 return false; 182 } 183 #endif // NDEBUG 184