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