1//===-- PPCCTRLoops.cpp - Generate 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 generates machine instructions for the CTR loops related pseudos:
10// 1: MTCTRloop/DecreaseCTRloop
11// 2: MTCTR8loop/DecreaseCTR8loop
12//
13// If a CTR loop can be generated:
14// 1: MTCTRloop/MTCTR8loop will be converted to "mtctr"
15// 2: DecreaseCTRloop/DecreaseCTR8loop will be converted to "bdnz/bdz" and
16// its user branch instruction can be deleted.
17//
18// If a CTR loop can not be generated due to clobber of CTR:
19// 1: MTCTRloop/MTCTR8loop can be deleted.
20// 2: DecreaseCTRloop/DecreaseCTR8loop will be converted to "addi -1" and
21// a "cmplwi/cmpldi".
22//
23// This pass runs just before register allocation, because we don't want
24// register allocator to allocate register for DecreaseCTRloop if a CTR can be
25// generated or if a CTR loop can not be generated, we don't have any condition
26// register for the new added "cmplwi/cmpldi".
27//
28//===----------------------------------------------------------------------===//
29
30#include "PPC.h"
31#include "PPCInstrInfo.h"
32#include "PPCSubtarget.h"
33#include "llvm/ADT/Statistic.h"
34#include "llvm/CodeGen/MachineBasicBlock.h"
35#include "llvm/CodeGen/MachineFunction.h"
36#include "llvm/CodeGen/MachineFunctionPass.h"
37#include "llvm/CodeGen/MachineInstr.h"
38#include "llvm/CodeGen/MachineLoopInfo.h"
39#include "llvm/CodeGen/MachineOperand.h"
40#include "llvm/CodeGen/MachineRegisterInfo.h"
41#include "llvm/CodeGen/Register.h"
42#include "llvm/InitializePasses.h"
43#include "llvm/Pass.h"
44#include "llvm/Support/ErrorHandling.h"
45#include <cassert>
46
47using namespace llvm;
48
49#define DEBUG_TYPE "ppc-ctrloops"
50
51STATISTIC(NumCTRLoops, "Number of CTR loops generated");
52STATISTIC(NumNormalLoops, "Number of normal compare + branch loops generated");
53
54namespace {
55class PPCCTRLoops : public MachineFunctionPass {
56public:
57 static char ID;
58
59 PPCCTRLoops() : MachineFunctionPass(ID) {}
60
61 void getAnalysisUsage(AnalysisUsage &AU) const override {
62 AU.addRequired<MachineLoopInfoWrapperPass>();
63 MachineFunctionPass::getAnalysisUsage(AU);
64 }
65
66 bool runOnMachineFunction(MachineFunction &MF) override;
67
68private:
69 const PPCInstrInfo *TII = nullptr;
70 MachineRegisterInfo *MRI = nullptr;
71
72 bool processLoop(MachineLoop *ML);
73 bool isCTRClobber(MachineInstr *MI, bool CheckReads) const;
74 void expandNormalLoops(MachineLoop *ML, MachineInstr *Start,
75 MachineInstr *Dec);
76 void expandCTRLoops(MachineLoop *ML, MachineInstr *Start, MachineInstr *Dec);
77};
78} // namespace
79
80char PPCCTRLoops::ID = 0;
81
82INITIALIZE_PASS_BEGIN(PPCCTRLoops, DEBUG_TYPE, "PowerPC CTR loops generation",
83 false, false)
84INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
85INITIALIZE_PASS_END(PPCCTRLoops, DEBUG_TYPE, "PowerPC CTR loops generation",
86 false, false)
87
88FunctionPass *llvm::createPPCCTRLoopsPass() { return new PPCCTRLoops(); }
89
90bool PPCCTRLoops::runOnMachineFunction(MachineFunction &MF) {
91 bool Changed = false;
92
93 auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
94 TII = static_cast<const PPCInstrInfo *>(MF.getSubtarget().getInstrInfo());
95 MRI = &MF.getRegInfo();
96
97 for (auto *ML : MLI) {
98 if (ML->isOutermost())
99 Changed |= processLoop(ML);
100 }
101
102#ifndef NDEBUG
103 for (const MachineBasicBlock &BB : MF) {
104 for (const MachineInstr &I : BB)
105 assert((I.getOpcode() != PPC::DecreaseCTRloop &&
106 I.getOpcode() != PPC::DecreaseCTR8loop) &&
107 "CTR loop pseudo is not expanded!");
108 }
109#endif
110
111 return Changed;
112}
113
114bool PPCCTRLoops::isCTRClobber(MachineInstr *MI, bool CheckReads) const {
115 if (!CheckReads) {
116 // If we are only checking for defs, that is we are going to find
117 // definitions before MTCTRloop, for this case:
118 // CTR defination inside the callee of a call instruction will not impact
119 // the defination of MTCTRloop, so we can use definesRegister() for the
120 // check, no need to check the regmask.
121 return MI->definesRegister(Reg: PPC::CTR, /*TRI=*/nullptr) ||
122 MI->definesRegister(Reg: PPC::CTR8, /*TRI=*/nullptr);
123 }
124
125 if (MI->modifiesRegister(Reg: PPC::CTR, /*TRI=*/nullptr) ||
126 MI->modifiesRegister(Reg: PPC::CTR8, /*TRI=*/nullptr))
127 return true;
128
129 if (MI->getDesc().isCall())
130 return true;
131
132 // We define the CTR in the loop preheader, so if there is any CTR reader in
133 // the loop, we also can not use CTR loop form.
134 if (MI->readsRegister(Reg: PPC::CTR, /*TRI=*/nullptr) ||
135 MI->readsRegister(Reg: PPC::CTR8, /*TRI=*/nullptr))
136 return true;
137
138 return false;
139}
140
141bool PPCCTRLoops::processLoop(MachineLoop *ML) {
142 bool Changed = false;
143
144 // Align with HardwareLoop pass, process inner loops first.
145 for (MachineLoop *I : *ML)
146 Changed |= processLoop(ML: I);
147
148 // If any inner loop is changed, outter loop must be without hardware loop
149 // intrinsics.
150 if (Changed)
151 return true;
152
153 auto IsLoopStart = [](MachineInstr &MI) {
154 return MI.getOpcode() == PPC::MTCTRloop ||
155 MI.getOpcode() == PPC::MTCTR8loop;
156 };
157
158 auto SearchForStart =
159 [&IsLoopStart](MachineBasicBlock *MBB) -> MachineInstr * {
160 for (auto &MI : *MBB) {
161 if (IsLoopStart(MI))
162 return &MI;
163 }
164 return nullptr;
165 };
166
167 MachineInstr *Start = nullptr;
168 MachineInstr *Dec = nullptr;
169 bool InvalidCTRLoop = false;
170
171 MachineBasicBlock *Preheader = ML->getLoopPreheader();
172 // If there is no preheader for this loop, there must be no MTCTRloop
173 // either.
174 if (!Preheader)
175 return false;
176
177 Start = SearchForStart(Preheader);
178 // This is not a CTR loop candidate.
179 if (!Start)
180 return false;
181
182 // If CTR is live to the preheader, we can not redefine the CTR register.
183 if (Preheader->isLiveIn(Reg: PPC::CTR) || Preheader->isLiveIn(Reg: PPC::CTR8))
184 InvalidCTRLoop = true;
185
186 // Make sure there is also no CTR clobber in the block preheader between the
187 // begin and MTCTR.
188 for (MachineBasicBlock::reverse_instr_iterator I =
189 std::next(x: Start->getReverseIterator());
190 I != Preheader->instr_rend(); ++I)
191 // Only check the definitions of CTR. If there is non-dead definition for
192 // the CTR, we conservatively don't generate a CTR loop.
193 if (isCTRClobber(MI: &*I, /* CheckReads */ false)) {
194 InvalidCTRLoop = true;
195 break;
196 }
197
198 // Make sure there is also no CTR clobber/user in the block preheader between
199 // MTCTR and the end.
200 for (MachineBasicBlock::instr_iterator I = std::next(x: Start->getIterator());
201 I != Preheader->instr_end(); ++I)
202 if (isCTRClobber(MI: &*I, /* CheckReads */ true)) {
203 InvalidCTRLoop = true;
204 break;
205 }
206
207 // Find the CTR loop components and decide whether or not to fall back to a
208 // normal loop.
209 for (auto *MBB : reverse(C: ML->getBlocks())) {
210 for (auto &MI : *MBB) {
211 if (MI.getOpcode() == PPC::DecreaseCTRloop ||
212 MI.getOpcode() == PPC::DecreaseCTR8loop)
213 Dec = &MI;
214 else if (!InvalidCTRLoop)
215 // If any instruction clobber CTR, then we can not generate a CTR loop.
216 InvalidCTRLoop |= isCTRClobber(MI: &MI, /* CheckReads */ true);
217 }
218 if (Dec && InvalidCTRLoop)
219 break;
220 }
221
222 assert(Dec && "CTR loop is not complete!");
223
224 if (InvalidCTRLoop) {
225 expandNormalLoops(ML, Start, Dec);
226 ++NumNormalLoops;
227 }
228 else {
229 expandCTRLoops(ML, Start, Dec);
230 ++NumCTRLoops;
231 }
232 return true;
233}
234
235void PPCCTRLoops::expandNormalLoops(MachineLoop *ML, MachineInstr *Start,
236 MachineInstr *Dec) {
237 bool Is64Bit =
238 Start->getParent()->getParent()->getSubtarget<PPCSubtarget>().isPPC64();
239
240 MachineBasicBlock *Preheader = Start->getParent();
241 MachineBasicBlock *Exiting = Dec->getParent();
242 assert((Preheader && Exiting) &&
243 "Preheader and exiting should exist for CTR loop!");
244
245 assert(Dec->getOperand(1).getImm() == 1 &&
246 "Loop decrement stride must be 1");
247
248 unsigned ADDIOpcode = Is64Bit ? PPC::ADDI8 : PPC::ADDI;
249 unsigned CMPOpcode = Is64Bit ? PPC::CMPLDI : PPC::CMPLWI;
250
251 Register PHIDef =
252 MRI->createVirtualRegister(RegClass: Is64Bit ? &PPC::G8RC_and_G8RC_NOX0RegClass
253 : &PPC::GPRC_and_GPRC_NOR0RegClass);
254
255 Start->getParent()->getParent()->getProperties().resetNoPHIs();
256
257 // Generate "PHI" in the header block.
258 auto PHIMIB = BuildMI(BB&: *ML->getHeader(), I: ML->getHeader()->getFirstNonPHI(),
259 MIMD: DebugLoc(), MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: PHIDef);
260 PHIMIB.addReg(RegNo: Start->getOperand(i: 0).getReg()).addMBB(MBB: Preheader);
261
262 Register ADDIDef =
263 MRI->createVirtualRegister(RegClass: Is64Bit ? &PPC::G8RC_and_G8RC_NOX0RegClass
264 : &PPC::GPRC_and_GPRC_NOR0RegClass);
265 // Generate "addi -1" in the exiting block.
266 BuildMI(BB&: *Exiting, I: Dec, MIMD: Dec->getDebugLoc(), MCID: TII->get(Opcode: ADDIOpcode), DestReg: ADDIDef)
267 .addReg(RegNo: PHIDef)
268 .addImm(Val: -1);
269
270 // Add other inputs for the PHI node.
271 if (ML->isLoopLatch(BB: Exiting)) {
272 // There must be only two predecessors for the loop header, one is the
273 // Preheader and the other one is loop latch Exiting. In hardware loop
274 // insertion pass, the block containing DecreaseCTRloop must dominate all
275 // loop latches. So there must be only one latch.
276 assert(ML->getHeader()->pred_size() == 2 &&
277 "Loop header predecessor is not right!");
278 PHIMIB.addReg(RegNo: ADDIDef).addMBB(MBB: Exiting);
279 } else {
280 // If the block containing DecreaseCTRloop is not a loop latch, we can use
281 // ADDIDef as the value for all other blocks for the PHI. In hardware loop
282 // insertion pass, the block containing DecreaseCTRloop must dominate all
283 // loop latches.
284 for (MachineBasicBlock *P : ML->getHeader()->predecessors()) {
285 if (ML->contains(BB: P)) {
286 assert(ML->isLoopLatch(P) &&
287 "Loop's header in-loop predecessor is not loop latch!");
288 PHIMIB.addReg(RegNo: ADDIDef).addMBB(MBB: P);
289 } else
290 assert(P == Preheader &&
291 "CTR loop should not be generated for irreducible loop!");
292 }
293 }
294
295 // Generate the compare in the exiting block.
296 Register CMPDef = MRI->createVirtualRegister(RegClass: &PPC::CRRCRegClass);
297 auto CMPMIB =
298 BuildMI(BB&: *Exiting, I: Dec, MIMD: Dec->getDebugLoc(), MCID: TII->get(Opcode: CMPOpcode), DestReg: CMPDef)
299 .addReg(RegNo: ADDIDef)
300 .addImm(Val: 0);
301
302 BuildMI(BB&: *Exiting, I: Dec, MIMD: Dec->getDebugLoc(), MCID: TII->get(Opcode: TargetOpcode::COPY),
303 DestReg: Dec->getOperand(i: 0).getReg())
304 .addReg(RegNo: CMPMIB->getOperand(i: 0).getReg(), Flags: {}, SubReg: PPC::sub_gt);
305
306 // Remove the pseudo instructions.
307 Start->eraseFromParent();
308 Dec->eraseFromParent();
309}
310
311void PPCCTRLoops::expandCTRLoops(MachineLoop *ML, MachineInstr *Start,
312 MachineInstr *Dec) {
313 bool Is64Bit =
314 Start->getParent()->getParent()->getSubtarget<PPCSubtarget>().isPPC64();
315
316 MachineBasicBlock *Preheader = Start->getParent();
317 MachineBasicBlock *Exiting = Dec->getParent();
318
319 (void)Preheader;
320 assert((Preheader && Exiting) &&
321 "Preheader and exiting should exist for CTR loop!");
322
323 assert(Dec->getOperand(1).getImm() == 1 && "Loop decrement must be 1!");
324
325 unsigned BDNZOpcode = Is64Bit ? PPC::BDNZ8 : PPC::BDNZ;
326 unsigned BDZOpcode = Is64Bit ? PPC::BDZ8 : PPC::BDZ;
327 auto BrInstr = MRI->use_instr_begin(RegNo: Dec->getOperand(i: 0).getReg());
328 assert(MRI->hasOneUse(Dec->getOperand(0).getReg()) &&
329 "There should be only one user for loop decrement pseudo!");
330
331 unsigned Opcode = 0;
332 switch (BrInstr->getOpcode()) {
333 case PPC::BC:
334 Opcode = BDNZOpcode;
335 (void) ML;
336 assert(ML->contains(BrInstr->getOperand(1).getMBB()) &&
337 "Invalid ctr loop!");
338 break;
339 case PPC::BCn:
340 Opcode = BDZOpcode;
341 assert(!ML->contains(BrInstr->getOperand(1).getMBB()) &&
342 "Invalid ctr loop!");
343 break;
344 default:
345 llvm_unreachable("Unhandled branch user for DecreaseCTRloop.");
346 }
347
348 // Generate "bdnz/bdz" in the exiting block just before the terminator.
349 BuildMI(BB&: *Exiting, I: &*BrInstr, MIMD: BrInstr->getDebugLoc(), MCID: TII->get(Opcode))
350 .addMBB(MBB: BrInstr->getOperand(i: 1).getMBB());
351
352 // Remove the pseudo instructions.
353 BrInstr->eraseFromParent();
354 Dec->eraseFromParent();
355}
356