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