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