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
41using namespace llvm;
42
43#define DEBUG_TYPE "ppc-ctrloops-verify"
44
45namespace {
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
69INITIALIZE_PASS_BEGIN(PPCCTRLoopsVerify, "ppc-ctr-loops-verify",
70 "PowerPC CTR Loops Verify", false, false)
71INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
72INITIALIZE_PASS_END(PPCCTRLoopsVerify, "ppc-ctr-loops-verify",
73 "PowerPC CTR Loops Verify", false, false)
74
75FunctionPass *llvm::createPPCCTRLoopsVerify() {
76 return new PPCCTRLoopsVerify();
77}
78
79static 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
93static 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
106check_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) {
137queue_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
160bool 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