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
PPCCTRLoopsVerify__anone4ab36030111::PPCCTRLoopsVerify51 PPCCTRLoopsVerify() : MachineFunctionPass(ID) {
52 initializePPCCTRLoopsVerifyPass(*PassRegistry::getPassRegistry());
53 }
54
getAnalysisUsage__anone4ab36030111::PPCCTRLoopsVerify55 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)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)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
clobbersCTR(const MachineInstr & MI)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
verifyCTRBranch(MachineBasicBlock * MBB,MachineBasicBlock::iterator I)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
runOnMachineFunction(MachineFunction & MF)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