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 (const MachineOperand &MO : MI.operands()) { 85 if (MO.isReg()) { 86 if (MO.isDef() && (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8)) 87 return true; 88 } else if (MO.isRegMask()) { 89 if (MO.clobbersPhysReg(PPC::CTR) || MO.clobbersPhysReg(PPC::CTR8)) 90 return true; 91 } 92 } 93 94 return false; 95 } 96 97 static bool verifyCTRBranch(MachineBasicBlock *MBB, 98 MachineBasicBlock::iterator I) { 99 MachineBasicBlock::iterator BI = I; 100 SmallSet<MachineBasicBlock *, 16> Visited; 101 SmallVector<MachineBasicBlock *, 8> Preds; 102 bool CheckPreds; 103 104 if (I == MBB->begin()) { 105 Visited.insert(MBB); 106 goto queue_preds; 107 } else 108 --I; 109 110 check_block: 111 Visited.insert(MBB); 112 if (I == MBB->end()) 113 goto queue_preds; 114 115 CheckPreds = true; 116 for (MachineBasicBlock::iterator IE = MBB->begin();; --I) { 117 unsigned Opc = I->getOpcode(); 118 if (Opc == PPC::MTCTRloop || Opc == PPC::MTCTR8loop) { 119 CheckPreds = false; 120 break; 121 } 122 123 if (I != BI && clobbersCTR(*I)) { 124 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " (" << MBB->getFullName() 125 << ") instruction " << *I 126 << " clobbers CTR, invalidating " 127 << printMBBReference(*BI->getParent()) << " (" 128 << BI->getParent()->getFullName() << ") instruction " 129 << *BI << "\n"); 130 return false; 131 } 132 133 if (I == IE) 134 break; 135 } 136 137 if (!CheckPreds && Preds.empty()) 138 return true; 139 140 if (CheckPreds) { 141 queue_preds: 142 if (MachineFunction::iterator(MBB) == MBB->getParent()->begin()) { 143 LLVM_DEBUG(dbgs() << "Unable to find a MTCTR instruction for " 144 << printMBBReference(*BI->getParent()) << " (" 145 << BI->getParent()->getFullName() << ") instruction " 146 << *BI << "\n"); 147 return false; 148 } 149 150 append_range(Preds, MBB->predecessors()); 151 } 152 153 do { 154 MBB = Preds.pop_back_val(); 155 if (!Visited.count(MBB)) { 156 I = MBB->getLastNonDebugInstr(); 157 goto check_block; 158 } 159 } while (!Preds.empty()); 160 161 return true; 162 } 163 164 bool PPCCTRLoopsVerify::runOnMachineFunction(MachineFunction &MF) { 165 MDT = &getAnalysis<MachineDominatorTree>(); 166 167 // Verify that all bdnz/bdz instructions are dominated by a loop mtctr before 168 // any other instructions that might clobber the ctr register. 169 for (MachineBasicBlock &MBB : MF) { 170 if (!MDT->isReachableFromEntry(&MBB)) 171 continue; 172 173 for (MachineBasicBlock::iterator MII = MBB.getFirstTerminator(), 174 MIIE = MBB.end(); MII != MIIE; ++MII) { 175 unsigned Opc = MII->getOpcode(); 176 if (Opc == PPC::BDNZ8 || Opc == PPC::BDNZ || 177 Opc == PPC::BDZ8 || Opc == PPC::BDZ) 178 if (!verifyCTRBranch(&MBB, MII)) 179 llvm_unreachable("Invalid PPC CTR loop!"); 180 } 181 } 182 183 return false; 184 } 185 #endif // NDEBUG 186