1//===---- PPCReduceCRLogicals.cpp - Reduce CR Bit Logical operations ------===//
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 aims to reduce the number of logical operations on bits in the CR
10// register. These instructions have a fairly high latency and only a single
11// pipeline at their disposal in modern PPC cores. Furthermore, they have a
12// tendency to occur in fairly small blocks where there's little opportunity
13// to hide the latency between the CR logical operation and its user.
14//
15//===---------------------------------------------------------------------===//
16
17#include "PPC.h"
18#include "PPCInstrInfo.h"
19#include "PPCTargetMachine.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
22#include "llvm/CodeGen/MachineDominators.h"
23#include "llvm/CodeGen/MachineFunctionPass.h"
24#include "llvm/CodeGen/MachineInstrBuilder.h"
25#include "llvm/CodeGen/MachineRegisterInfo.h"
26#include "llvm/Config/llvm-config.h"
27#include "llvm/InitializePasses.h"
28#include "llvm/Support/Debug.h"
29
30using namespace llvm;
31
32#define DEBUG_TYPE "ppc-reduce-cr-ops"
33
34STATISTIC(NumContainedSingleUseBinOps,
35 "Number of single-use binary CR logical ops contained in a block");
36STATISTIC(NumToSplitBlocks,
37 "Number of binary CR logical ops that can be used to split blocks");
38STATISTIC(TotalCRLogicals, "Number of CR logical ops.");
39STATISTIC(TotalNullaryCRLogicals,
40 "Number of nullary CR logical ops (CRSET/CRUNSET).");
41STATISTIC(TotalUnaryCRLogicals, "Number of unary CR logical ops.");
42STATISTIC(TotalBinaryCRLogicals, "Number of CR logical ops.");
43STATISTIC(NumBlocksSplitOnBinaryCROp,
44 "Number of blocks split on CR binary logical ops.");
45STATISTIC(NumNotSplitIdenticalOperands,
46 "Number of blocks not split due to operands being identical.");
47STATISTIC(NumNotSplitChainCopies,
48 "Number of blocks not split due to operands being chained copies.");
49STATISTIC(NumNotSplitWrongOpcode,
50 "Number of blocks not split due to the wrong opcode.");
51
52/// Given a basic block \p Successor that potentially contains PHIs, this
53/// function will look for any incoming values in the PHIs that are supposed to
54/// be coming from \p OrigMBB but whose definition is actually in \p NewMBB.
55/// Any such PHIs will be updated to reflect reality.
56static void updatePHIs(MachineBasicBlock *Successor, MachineBasicBlock *OrigMBB,
57 MachineBasicBlock *NewMBB, MachineRegisterInfo *MRI) {
58 for (auto &MI : Successor->instrs()) {
59 if (!MI.isPHI())
60 continue;
61 // This is a really ugly-looking loop, but it was pillaged directly from
62 // MachineBasicBlock::transferSuccessorsAndUpdatePHIs().
63 for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) {
64 MachineOperand &MO = MI.getOperand(i);
65 if (MO.getMBB() == OrigMBB) {
66 // Check if the instruction is actually defined in NewMBB.
67 if (MI.getOperand(i: i - 1).isReg()) {
68 MachineInstr *DefMI = MRI->getVRegDef(Reg: MI.getOperand(i: i - 1).getReg());
69 if (DefMI->getParent() == NewMBB ||
70 !OrigMBB->isSuccessor(MBB: Successor)) {
71 MO.setMBB(NewMBB);
72 break;
73 }
74 }
75 }
76 }
77 }
78}
79
80/// Given a basic block \p Successor that potentially contains PHIs, this
81/// function will look for PHIs that have an incoming value from \p OrigMBB
82/// and will add the same incoming value from \p NewMBB.
83/// NOTE: This should only be used if \p NewMBB is an immediate dominator of
84/// \p OrigMBB.
85static void addIncomingValuesToPHIs(MachineBasicBlock *Successor,
86 MachineBasicBlock *OrigMBB,
87 MachineBasicBlock *NewMBB,
88 MachineRegisterInfo *MRI) {
89 assert(OrigMBB->isSuccessor(NewMBB) &&
90 "NewMBB must be a successor of OrigMBB");
91 for (auto &MI : Successor->instrs()) {
92 if (!MI.isPHI())
93 continue;
94 // This is a really ugly-looking loop, but it was pillaged directly from
95 // MachineBasicBlock::transferSuccessorsAndUpdatePHIs().
96 for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) {
97 MachineOperand &MO = MI.getOperand(i);
98 if (MO.getMBB() == OrigMBB) {
99 MachineInstrBuilder MIB(*MI.getParent()->getParent(), &MI);
100 MIB.addReg(RegNo: MI.getOperand(i: i - 1).getReg()).addMBB(MBB: NewMBB);
101 break;
102 }
103 }
104 }
105}
106
107namespace {
108struct BlockSplitInfo {
109 MachineInstr *OrigBranch;
110 MachineInstr *SplitBefore;
111 MachineInstr *SplitCond;
112 unsigned OrigSubreg;
113 unsigned SplitCondSubreg;
114 bool InvertNewBranch;
115 bool InvertOrigBranch;
116 bool BranchToFallThrough;
117 const MachineBranchProbabilityInfo *MBPI;
118 MachineInstr *MIToDelete;
119 MachineInstr *NewCond;
120 bool allInstrsInSameMBB() {
121 if (!OrigBranch || !SplitBefore || !SplitCond)
122 return false;
123 MachineBasicBlock *MBB = OrigBranch->getParent();
124 if (SplitBefore->getParent() != MBB || SplitCond->getParent() != MBB)
125 return false;
126 if (MIToDelete && MIToDelete->getParent() != MBB)
127 return false;
128 if (NewCond && NewCond->getParent() != MBB)
129 return false;
130 return true;
131 }
132};
133} // end anonymous namespace
134
135/// Splits a MachineBasicBlock to branch before \p SplitBefore. The original
136/// branch is \p OrigBranch. The target of the new branch can either be the same
137/// as the target of the original branch or the fallthrough successor of the
138/// original block as determined by \p BranchToFallThrough. The branch
139/// conditions will be inverted according to \p InvertNewBranch and
140/// \p InvertOrigBranch. If an instruction that previously fed the branch is to
141/// be deleted, it is provided in \p MIToDelete and \p NewCond will be used as
142/// the branch condition. The branch probabilities will be set if the
143/// MachineBranchProbabilityInfo isn't null.
144static bool splitMBB(BlockSplitInfo &BSI) {
145 assert(BSI.allInstrsInSameMBB() &&
146 "All instructions must be in the same block.");
147
148 MachineBasicBlock *ThisMBB = BSI.OrigBranch->getParent();
149 MachineFunction *MF = ThisMBB->getParent();
150 MachineRegisterInfo *MRI = &MF->getRegInfo();
151 assert(MRI->isSSA() && "Can only do this while the function is in SSA form.");
152 if (ThisMBB->succ_size() != 2) {
153 LLVM_DEBUG(
154 dbgs() << "Don't know how to handle blocks that don't have exactly"
155 << " two successors.\n");
156 return false;
157 }
158
159 const PPCInstrInfo *TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo();
160 unsigned OrigBROpcode = BSI.OrigBranch->getOpcode();
161 unsigned InvertedOpcode =
162 OrigBROpcode == PPC::BC
163 ? PPC::BCn
164 : OrigBROpcode == PPC::BCn
165 ? PPC::BC
166 : OrigBROpcode == PPC::BCLR ? PPC::BCLRn : PPC::BCLR;
167 unsigned NewBROpcode = BSI.InvertNewBranch ? InvertedOpcode : OrigBROpcode;
168 MachineBasicBlock *OrigTarget = BSI.OrigBranch->getOperand(i: 1).getMBB();
169 MachineBasicBlock *OrigFallThrough = OrigTarget == *ThisMBB->succ_begin()
170 ? *ThisMBB->succ_rbegin()
171 : *ThisMBB->succ_begin();
172 MachineBasicBlock *NewBRTarget =
173 BSI.BranchToFallThrough ? OrigFallThrough : OrigTarget;
174
175 // It's impossible to know the precise branch probability after the split.
176 // But it still needs to be reasonable, the whole probability to original
177 // targets should not be changed.
178 // After split NewBRTarget will get two incoming edges. Assume P0 is the
179 // original branch probability to NewBRTarget, P1 and P2 are new branch
180 // probabilies to NewBRTarget after split. If the two edge frequencies are
181 // same, then
182 // F * P1 = F * P0 / 2 ==> P1 = P0 / 2
183 // F * (1 - P1) * P2 = F * P1 ==> P2 = P1 / (1 - P1)
184 BranchProbability ProbToNewTarget, ProbFallThrough; // Prob for new Br.
185 BranchProbability ProbOrigTarget, ProbOrigFallThrough; // Prob for orig Br.
186 ProbToNewTarget = ProbFallThrough = BranchProbability::getUnknown();
187 ProbOrigTarget = ProbOrigFallThrough = BranchProbability::getUnknown();
188 if (BSI.MBPI) {
189 if (BSI.BranchToFallThrough) {
190 ProbToNewTarget = BSI.MBPI->getEdgeProbability(Src: ThisMBB, Dst: OrigFallThrough) / 2;
191 ProbFallThrough = ProbToNewTarget.getCompl();
192 ProbOrigFallThrough = ProbToNewTarget / ProbToNewTarget.getCompl();
193 ProbOrigTarget = ProbOrigFallThrough.getCompl();
194 } else {
195 ProbToNewTarget = BSI.MBPI->getEdgeProbability(Src: ThisMBB, Dst: OrigTarget) / 2;
196 ProbFallThrough = ProbToNewTarget.getCompl();
197 ProbOrigTarget = ProbToNewTarget / ProbToNewTarget.getCompl();
198 ProbOrigFallThrough = ProbOrigTarget.getCompl();
199 }
200 }
201
202 // Create a new basic block.
203 MachineBasicBlock::iterator InsertPoint = BSI.SplitBefore;
204 const BasicBlock *LLVM_BB = ThisMBB->getBasicBlock();
205 MachineFunction::iterator It = ThisMBB->getIterator();
206 MachineBasicBlock *NewMBB = MF->CreateMachineBasicBlock(BB: LLVM_BB);
207 MF->insert(MBBI: ++It, MBB: NewMBB);
208
209 // Move everything after SplitBefore into the new block.
210 NewMBB->splice(Where: NewMBB->end(), Other: ThisMBB, From: InsertPoint, To: ThisMBB->end());
211 NewMBB->transferSuccessors(FromMBB: ThisMBB);
212 if (!ProbOrigTarget.isUnknown()) {
213 auto MBBI = find(Range: NewMBB->successors(), Val: OrigTarget);
214 NewMBB->setSuccProbability(I: MBBI, Prob: ProbOrigTarget);
215 MBBI = find(Range: NewMBB->successors(), Val: OrigFallThrough);
216 NewMBB->setSuccProbability(I: MBBI, Prob: ProbOrigFallThrough);
217 }
218
219 // Add the two successors to ThisMBB.
220 ThisMBB->addSuccessor(Succ: NewBRTarget, Prob: ProbToNewTarget);
221 ThisMBB->addSuccessor(Succ: NewMBB, Prob: ProbFallThrough);
222
223 // Add the branches to ThisMBB.
224 BuildMI(BB&: *ThisMBB, I: ThisMBB->end(), MIMD: BSI.SplitBefore->getDebugLoc(),
225 MCID: TII->get(Opcode: NewBROpcode))
226 .addReg(RegNo: BSI.SplitCond->getOperand(i: 0).getReg(), Flags: {}, SubReg: BSI.SplitCondSubreg)
227 .addMBB(MBB: NewBRTarget);
228 BuildMI(BB&: *ThisMBB, I: ThisMBB->end(), MIMD: BSI.SplitBefore->getDebugLoc(),
229 MCID: TII->get(Opcode: PPC::B))
230 .addMBB(MBB: NewMBB);
231 if (BSI.MIToDelete)
232 BSI.MIToDelete->eraseFromParent();
233
234 // Change the condition on the original branch and invert it if requested.
235 auto FirstTerminator = NewMBB->getFirstTerminator();
236 if (BSI.NewCond) {
237 assert(FirstTerminator->getOperand(0).isReg() &&
238 "Can't update condition of unconditional branch.");
239 FirstTerminator->getOperand(i: 0).setReg(BSI.NewCond->getOperand(i: 0).getReg());
240 FirstTerminator->getOperand(i: 0).setSubReg(BSI.OrigSubreg);
241 }
242 if (BSI.InvertOrigBranch)
243 FirstTerminator->setDesc(TII->get(Opcode: InvertedOpcode));
244
245 // If any of the PHIs in the successors of NewMBB reference values that
246 // now come from NewMBB, they need to be updated.
247 for (auto *Succ : NewMBB->successors()) {
248 updatePHIs(Successor: Succ, OrigMBB: ThisMBB, NewMBB, MRI);
249 }
250 addIncomingValuesToPHIs(Successor: NewBRTarget, OrigMBB: ThisMBB, NewMBB, MRI);
251
252 // Set the call frame size on ThisMBB to the new basic blocks.
253 // See https://reviews.llvm.org/D156113.
254 NewMBB->setCallFrameSize(TII->getCallFrameSizeAt(MI&: ThisMBB->back()));
255
256 LLVM_DEBUG(dbgs() << "After splitting, ThisMBB:\n"; ThisMBB->dump());
257 LLVM_DEBUG(dbgs() << "NewMBB:\n"; NewMBB->dump());
258 LLVM_DEBUG(dbgs() << "New branch-to block:\n"; NewBRTarget->dump());
259 return true;
260}
261
262static bool isBinary(MachineInstr &MI) {
263 return MI.getNumOperands() == 3;
264}
265
266static bool isNullary(MachineInstr &MI) {
267 return MI.getNumOperands() == 1;
268}
269
270/// Given a CR logical operation \p CROp, branch opcode \p BROp as well as
271/// a flag to indicate if the first operand of \p CROp is used as the
272/// SplitBefore operand, determines whether either of the branches are to be
273/// inverted as well as whether the new target should be the original
274/// fall-through block.
275static void
276computeBranchTargetAndInversion(unsigned CROp, unsigned BROp, bool UsingDef1,
277 bool &InvertNewBranch, bool &InvertOrigBranch,
278 bool &TargetIsFallThrough) {
279 // The conditions under which each of the output operands should be [un]set
280 // can certainly be written much more concisely with just 3 if statements or
281 // ternary expressions. However, this provides a much clearer overview to the
282 // reader as to what is set for each <CROp, BROp, OpUsed> combination.
283 if (BROp == PPC::BC || BROp == PPC::BCLR) {
284 // Regular branches.
285 switch (CROp) {
286 default:
287 llvm_unreachable("Don't know how to handle this CR logical.");
288 case PPC::CROR:
289 InvertNewBranch = false;
290 InvertOrigBranch = false;
291 TargetIsFallThrough = false;
292 return;
293 case PPC::CRAND:
294 InvertNewBranch = true;
295 InvertOrigBranch = false;
296 TargetIsFallThrough = true;
297 return;
298 case PPC::CRNAND:
299 InvertNewBranch = true;
300 InvertOrigBranch = true;
301 TargetIsFallThrough = false;
302 return;
303 case PPC::CRNOR:
304 InvertNewBranch = false;
305 InvertOrigBranch = true;
306 TargetIsFallThrough = true;
307 return;
308 case PPC::CRORC:
309 InvertNewBranch = UsingDef1;
310 InvertOrigBranch = !UsingDef1;
311 TargetIsFallThrough = false;
312 return;
313 case PPC::CRANDC:
314 InvertNewBranch = !UsingDef1;
315 InvertOrigBranch = !UsingDef1;
316 TargetIsFallThrough = true;
317 return;
318 }
319 } else if (BROp == PPC::BCn || BROp == PPC::BCLRn) {
320 // Negated branches.
321 switch (CROp) {
322 default:
323 llvm_unreachable("Don't know how to handle this CR logical.");
324 case PPC::CROR:
325 InvertNewBranch = true;
326 InvertOrigBranch = false;
327 TargetIsFallThrough = true;
328 return;
329 case PPC::CRAND:
330 InvertNewBranch = false;
331 InvertOrigBranch = false;
332 TargetIsFallThrough = false;
333 return;
334 case PPC::CRNAND:
335 InvertNewBranch = false;
336 InvertOrigBranch = true;
337 TargetIsFallThrough = true;
338 return;
339 case PPC::CRNOR:
340 InvertNewBranch = true;
341 InvertOrigBranch = true;
342 TargetIsFallThrough = false;
343 return;
344 case PPC::CRORC:
345 InvertNewBranch = !UsingDef1;
346 InvertOrigBranch = !UsingDef1;
347 TargetIsFallThrough = true;
348 return;
349 case PPC::CRANDC:
350 InvertNewBranch = UsingDef1;
351 InvertOrigBranch = !UsingDef1;
352 TargetIsFallThrough = false;
353 return;
354 }
355 } else
356 llvm_unreachable("Don't know how to handle this branch.");
357}
358
359namespace {
360
361class PPCReduceCRLogicals : public MachineFunctionPass {
362public:
363 static char ID;
364 struct CRLogicalOpInfo {
365 MachineInstr *MI;
366 // FIXME: If chains of copies are to be handled, this should be a vector.
367 std::pair<MachineInstr*, MachineInstr*> CopyDefs;
368 std::pair<MachineInstr*, MachineInstr*> TrueDefs;
369 unsigned IsBinary : 1;
370 unsigned IsNullary : 1;
371 unsigned ContainedInBlock : 1;
372 unsigned FeedsISEL : 1;
373 unsigned FeedsBR : 1;
374 unsigned FeedsLogical : 1;
375 unsigned SingleUse : 1;
376 unsigned DefsSingleUse : 1;
377 unsigned SubregDef1;
378 unsigned SubregDef2;
379 CRLogicalOpInfo() : MI(nullptr), IsBinary(0), IsNullary(0),
380 ContainedInBlock(0), FeedsISEL(0), FeedsBR(0),
381 FeedsLogical(0), SingleUse(0), DefsSingleUse(1),
382 SubregDef1(0), SubregDef2(0) { }
383 void dump();
384 };
385
386private:
387 const PPCInstrInfo *TII = nullptr;
388 MachineFunction *MF = nullptr;
389 MachineRegisterInfo *MRI = nullptr;
390 const MachineBranchProbabilityInfo *MBPI = nullptr;
391
392 // A vector to contain all the CR logical operations
393 SmallVector<CRLogicalOpInfo, 16> AllCRLogicalOps;
394 void initialize(MachineFunction &MFParm);
395 void collectCRLogicals();
396 bool handleCROp(unsigned Idx);
397 bool splitBlockOnBinaryCROp(CRLogicalOpInfo &CRI);
398 static bool isCRLogical(MachineInstr &MI) {
399 unsigned Opc = MI.getOpcode();
400 return Opc == PPC::CRAND || Opc == PPC::CRNAND || Opc == PPC::CROR ||
401 Opc == PPC::CRXOR || Opc == PPC::CRNOR || Opc == PPC::CRNOT ||
402 Opc == PPC::CREQV || Opc == PPC::CRANDC || Opc == PPC::CRORC ||
403 Opc == PPC::CRSET || Opc == PPC::CRUNSET || Opc == PPC::CR6SET ||
404 Opc == PPC::CR6UNSET;
405 }
406 bool simplifyCode() {
407 bool Changed = false;
408 // Not using a range-based for loop here as the vector may grow while being
409 // operated on.
410 for (unsigned i = 0; i < AllCRLogicalOps.size(); i++)
411 Changed |= handleCROp(Idx: i);
412 return Changed;
413 }
414
415public:
416 PPCReduceCRLogicals() : MachineFunctionPass(ID) {}
417
418 MachineInstr *lookThroughCRCopy(unsigned Reg, unsigned &Subreg,
419 MachineInstr *&CpDef);
420 bool runOnMachineFunction(MachineFunction &MF) override {
421 if (skipFunction(F: MF.getFunction()))
422 return false;
423
424 // If the subtarget doesn't use CR bits, there's nothing to do.
425 const PPCSubtarget &STI = MF.getSubtarget<PPCSubtarget>();
426 if (!STI.useCRBits())
427 return false;
428
429 initialize(MFParm&: MF);
430 collectCRLogicals();
431 return simplifyCode();
432 }
433 CRLogicalOpInfo createCRLogicalOpInfo(MachineInstr &MI);
434 void getAnalysisUsage(AnalysisUsage &AU) const override {
435 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();
436 AU.addRequired<MachineDominatorTreeWrapperPass>();
437 MachineFunctionPass::getAnalysisUsage(AU);
438 }
439};
440} // end anonymous namespace
441
442#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
443LLVM_DUMP_METHOD void PPCReduceCRLogicals::CRLogicalOpInfo::dump() {
444 dbgs() << "CRLogicalOpMI: ";
445 MI->dump();
446 dbgs() << "IsBinary: " << IsBinary << ", FeedsISEL: " << FeedsISEL;
447 dbgs() << ", FeedsBR: " << FeedsBR << ", FeedsLogical: ";
448 dbgs() << FeedsLogical << ", SingleUse: " << SingleUse;
449 dbgs() << ", DefsSingleUse: " << DefsSingleUse;
450 dbgs() << ", SubregDef1: " << SubregDef1 << ", SubregDef2: ";
451 dbgs() << SubregDef2 << ", ContainedInBlock: " << ContainedInBlock;
452 if (!IsNullary) {
453 dbgs() << "\nDefs:\n";
454 TrueDefs.first->dump();
455 }
456 if (IsBinary)
457 TrueDefs.second->dump();
458 dbgs() << "\n";
459 if (CopyDefs.first) {
460 dbgs() << "CopyDef1: ";
461 CopyDefs.first->dump();
462 }
463 if (CopyDefs.second) {
464 dbgs() << "CopyDef2: ";
465 CopyDefs.second->dump();
466 }
467}
468#endif
469
470PPCReduceCRLogicals::CRLogicalOpInfo
471PPCReduceCRLogicals::createCRLogicalOpInfo(MachineInstr &MIParam) {
472 CRLogicalOpInfo Ret;
473 Ret.MI = &MIParam;
474 // Get the defs
475 if (isNullary(MI&: MIParam)) {
476 Ret.IsNullary = 1;
477 Ret.TrueDefs = std::make_pair(x: nullptr, y: nullptr);
478 Ret.CopyDefs = std::make_pair(x: nullptr, y: nullptr);
479 } else {
480 MachineInstr *Def1 = lookThroughCRCopy(Reg: MIParam.getOperand(i: 1).getReg(),
481 Subreg&: Ret.SubregDef1, CpDef&: Ret.CopyDefs.first);
482 Ret.SubregDef1 = MIParam.getOperand(i: 1).getSubReg();
483 assert(Def1 && "Must be able to find a definition of operand 1.");
484 Ret.DefsSingleUse &=
485 MRI->hasOneNonDBGUse(RegNo: Def1->getOperand(i: 0).getReg());
486 Ret.DefsSingleUse &=
487 MRI->hasOneNonDBGUse(RegNo: Ret.CopyDefs.first->getOperand(i: 0).getReg());
488 if (isBinary(MI&: MIParam)) {
489 Ret.IsBinary = 1;
490 MachineInstr *Def2 = lookThroughCRCopy(Reg: MIParam.getOperand(i: 2).getReg(),
491 Subreg&: Ret.SubregDef2,
492 CpDef&: Ret.CopyDefs.second);
493 Ret.SubregDef2 = MIParam.getOperand(i: 2).getSubReg();
494 assert(Def2 && "Must be able to find a definition of operand 2.");
495 Ret.DefsSingleUse &=
496 MRI->hasOneNonDBGUse(RegNo: Def2->getOperand(i: 0).getReg());
497 Ret.DefsSingleUse &=
498 MRI->hasOneNonDBGUse(RegNo: Ret.CopyDefs.second->getOperand(i: 0).getReg());
499 Ret.TrueDefs = std::make_pair(x&: Def1, y&: Def2);
500 } else {
501 Ret.TrueDefs = std::make_pair(x&: Def1, y: nullptr);
502 Ret.CopyDefs.second = nullptr;
503 }
504 }
505
506 Ret.ContainedInBlock = 1;
507 // Get the uses
508 for (MachineInstr &UseMI :
509 MRI->use_nodbg_instructions(Reg: MIParam.getOperand(i: 0).getReg())) {
510 unsigned Opc = UseMI.getOpcode();
511 if (Opc == PPC::ISEL || Opc == PPC::ISEL8)
512 Ret.FeedsISEL = 1;
513 if (Opc == PPC::BC || Opc == PPC::BCn || Opc == PPC::BCLR ||
514 Opc == PPC::BCLRn)
515 Ret.FeedsBR = 1;
516 Ret.FeedsLogical = isCRLogical(MI&: UseMI);
517 if (UseMI.getParent() != MIParam.getParent())
518 Ret.ContainedInBlock = 0;
519 }
520 Ret.SingleUse = MRI->hasOneNonDBGUse(RegNo: MIParam.getOperand(i: 0).getReg()) ? 1 : 0;
521
522 // We now know whether all the uses of the CR logical are in the same block.
523 if (!Ret.IsNullary) {
524 Ret.ContainedInBlock &=
525 (MIParam.getParent() == Ret.TrueDefs.first->getParent());
526 if (Ret.IsBinary)
527 Ret.ContainedInBlock &=
528 (MIParam.getParent() == Ret.TrueDefs.second->getParent());
529 }
530 LLVM_DEBUG(Ret.dump());
531 if (Ret.IsBinary && Ret.ContainedInBlock && Ret.SingleUse) {
532 NumContainedSingleUseBinOps++;
533 if (Ret.FeedsBR && Ret.DefsSingleUse)
534 NumToSplitBlocks++;
535 }
536 return Ret;
537}
538
539/// Looks through a COPY instruction to the actual definition of the CR-bit
540/// register and returns the instruction that defines it.
541/// FIXME: This currently handles what is by-far the most common case:
542/// an instruction that defines a CR field followed by a single copy of a bit
543/// from that field into a virtual register. If chains of copies need to be
544/// handled, this should have a loop until a non-copy instruction is found.
545MachineInstr *PPCReduceCRLogicals::lookThroughCRCopy(unsigned Reg,
546 unsigned &Subreg,
547 MachineInstr *&CpDef) {
548 if (!Register::isVirtualRegister(Reg))
549 return nullptr;
550 MachineInstr *Copy = MRI->getVRegDef(Reg);
551 CpDef = Copy;
552 if (!Copy->isCopy())
553 return Copy;
554 Register CopySrc = Copy->getOperand(i: 1).getReg();
555 if (!CopySrc.isVirtual()) {
556 const TargetRegisterInfo *TRI = &TII->getRegisterInfo();
557 // Loop backwards and return the first MI that modifies the physical CR Reg.
558 MachineBasicBlock::iterator Me = Copy, B = Copy->getParent()->begin();
559 while (Me != B)
560 if ((--Me)->modifiesRegister(Reg: CopySrc, TRI))
561 return &*Me;
562 return nullptr;
563 }
564 return MRI->getVRegDef(Reg: CopySrc);
565}
566
567void PPCReduceCRLogicals::initialize(MachineFunction &MFParam) {
568 MF = &MFParam;
569 MRI = &MF->getRegInfo();
570 TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo();
571 MBPI = &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
572
573 AllCRLogicalOps.clear();
574}
575
576/// Contains all the implemented transformations on CR logical operations.
577/// For example, a binary CR logical can be used to split a block on its inputs,
578/// a unary CR logical might be used to change the condition code on a
579/// comparison feeding it. A nullary CR logical might simply be removable
580/// if the user of the bit it [un]sets can be transformed.
581bool PPCReduceCRLogicals::handleCROp(unsigned Idx) {
582 // We can definitely split a block on the inputs to a binary CR operation
583 // whose defs and (single) use are within the same block.
584 bool Changed = false;
585 CRLogicalOpInfo CRI = AllCRLogicalOps[Idx];
586 if (CRI.IsBinary && CRI.ContainedInBlock && CRI.SingleUse && CRI.FeedsBR &&
587 CRI.DefsSingleUse) {
588 Changed = splitBlockOnBinaryCROp(CRI);
589 if (Changed)
590 NumBlocksSplitOnBinaryCROp++;
591 }
592 return Changed;
593}
594
595/// Splits a block that contains a CR-logical operation that feeds a branch
596/// and whose operands are produced within the block.
597/// Example:
598/// %vr5<def> = CMPDI %vr2, 0; CRRC:%vr5 G8RC:%vr2
599/// %vr6<def> = COPY %vr5:sub_eq; CRBITRC:%vr6 CRRC:%vr5
600/// %vr7<def> = CMPDI %vr3, 0; CRRC:%vr7 G8RC:%vr3
601/// %vr8<def> = COPY %vr7:sub_eq; CRBITRC:%vr8 CRRC:%vr7
602/// %vr9<def> = CROR %vr6<kill>, %vr8<kill>; CRBITRC:%vr9,%vr6,%vr8
603/// BC %vr9<kill>, <BB#2>; CRBITRC:%vr9
604/// Becomes:
605/// %vr5<def> = CMPDI %vr2, 0; CRRC:%vr5 G8RC:%vr2
606/// %vr6<def> = COPY %vr5:sub_eq; CRBITRC:%vr6 CRRC:%vr5
607/// BC %vr6<kill>, <BB#2>; CRBITRC:%vr6
608///
609/// %vr7<def> = CMPDI %vr3, 0; CRRC:%vr7 G8RC:%vr3
610/// %vr8<def> = COPY %vr7:sub_eq; CRBITRC:%vr8 CRRC:%vr7
611/// BC %vr9<kill>, <BB#2>; CRBITRC:%vr9
612bool PPCReduceCRLogicals::splitBlockOnBinaryCROp(CRLogicalOpInfo &CRI) {
613 if (CRI.CopyDefs.first == CRI.CopyDefs.second) {
614 LLVM_DEBUG(dbgs() << "Unable to split as the two operands are the same\n");
615 NumNotSplitIdenticalOperands++;
616 return false;
617 }
618 if (CRI.TrueDefs.first->isCopy() || CRI.TrueDefs.second->isCopy() ||
619 CRI.TrueDefs.first->isPHI() || CRI.TrueDefs.second->isPHI()) {
620 LLVM_DEBUG(
621 dbgs() << "Unable to split because one of the operands is a PHI or "
622 "chain of copies.\n");
623 NumNotSplitChainCopies++;
624 return false;
625 }
626 // Note: keep in sync with computeBranchTargetAndInversion().
627 if (CRI.MI->getOpcode() != PPC::CROR &&
628 CRI.MI->getOpcode() != PPC::CRAND &&
629 CRI.MI->getOpcode() != PPC::CRNOR &&
630 CRI.MI->getOpcode() != PPC::CRNAND &&
631 CRI.MI->getOpcode() != PPC::CRORC &&
632 CRI.MI->getOpcode() != PPC::CRANDC) {
633 LLVM_DEBUG(dbgs() << "Unable to split blocks on this opcode.\n");
634 NumNotSplitWrongOpcode++;
635 return false;
636 }
637 LLVM_DEBUG(dbgs() << "Splitting the following CR op:\n"; CRI.dump());
638 MachineBasicBlock::iterator Def1It = CRI.TrueDefs.first;
639 MachineBasicBlock::iterator Def2It = CRI.TrueDefs.second;
640
641 bool UsingDef1 = false;
642 MachineInstr *SplitBefore = &*Def2It;
643 for (auto E = CRI.MI->getParent()->end(); Def2It != E; ++Def2It) {
644 if (Def1It == Def2It) { // Def2 comes before Def1.
645 SplitBefore = &*Def1It;
646 UsingDef1 = true;
647 break;
648 }
649 }
650
651 LLVM_DEBUG(dbgs() << "We will split the following block:\n";);
652 LLVM_DEBUG(CRI.MI->getParent()->dump());
653 LLVM_DEBUG(dbgs() << "Before instruction:\n"; SplitBefore->dump());
654
655 // Get the branch instruction.
656 MachineInstr *Branch =
657 MRI->use_nodbg_begin(RegNo: CRI.MI->getOperand(i: 0).getReg())->getParent();
658
659 // We want the new block to have no code in it other than the definition
660 // of the input to the CR logical and the CR logical itself. So we move
661 // those to the bottom of the block (just before the branch). Then we
662 // will split before the CR logical.
663 MachineBasicBlock *MBB = SplitBefore->getParent();
664 auto FirstTerminator = MBB->getFirstTerminator();
665 MachineBasicBlock::iterator FirstInstrToMove =
666 UsingDef1 ? CRI.TrueDefs.first : CRI.TrueDefs.second;
667 MachineBasicBlock::iterator SecondInstrToMove =
668 UsingDef1 ? CRI.CopyDefs.first : CRI.CopyDefs.second;
669
670 // The instructions that need to be moved are not guaranteed to be
671 // contiguous. Move them individually.
672 // FIXME: If one of the operands is a chain of (single use) copies, they
673 // can all be moved and we can still split.
674 MBB->splice(Where: FirstTerminator, Other: MBB, From: FirstInstrToMove);
675 if (FirstInstrToMove != SecondInstrToMove)
676 MBB->splice(Where: FirstTerminator, Other: MBB, From: SecondInstrToMove);
677 MBB->splice(Where: FirstTerminator, Other: MBB, From: CRI.MI);
678
679 unsigned Opc = CRI.MI->getOpcode();
680 bool InvertOrigBranch, InvertNewBranch, TargetIsFallThrough;
681 computeBranchTargetAndInversion(CROp: Opc, BROp: Branch->getOpcode(), UsingDef1,
682 InvertNewBranch, InvertOrigBranch,
683 TargetIsFallThrough);
684 MachineInstr *NewCond = CRI.CopyDefs.first;
685 MachineInstr *SplitCond = CRI.CopyDefs.second;
686 if (!UsingDef1) {
687 std::swap(a&: NewCond, b&: SplitCond);
688 std::swap(a&: CRI.SubregDef1, b&: CRI.SubregDef2);
689 }
690 LLVM_DEBUG(dbgs() << "We will " << (InvertNewBranch ? "invert" : "copy"));
691 LLVM_DEBUG(dbgs() << " the original branch and the target is the "
692 << (TargetIsFallThrough ? "fallthrough block\n"
693 : "orig. target block\n"));
694 LLVM_DEBUG(dbgs() << "Original branch instruction: "; Branch->dump());
695 BlockSplitInfo BSI{
696 .OrigBranch: Branch, .SplitBefore: SplitBefore, .SplitCond: SplitCond, .OrigSubreg: CRI.SubregDef1,
697 .SplitCondSubreg: CRI.SubregDef2, .InvertNewBranch: InvertNewBranch, .InvertOrigBranch: InvertOrigBranch, .BranchToFallThrough: TargetIsFallThrough,
698 .MBPI: MBPI, .MIToDelete: CRI.MI, .NewCond: NewCond};
699 bool Changed = splitMBB(BSI);
700 // If we've split on a CR logical that is fed by a CR logical,
701 // recompute the source CR logical as it may be usable for splitting.
702 if (Changed) {
703 bool Input1CRlogical =
704 CRI.TrueDefs.first && isCRLogical(MI&: *CRI.TrueDefs.first);
705 bool Input2CRlogical =
706 CRI.TrueDefs.second && isCRLogical(MI&: *CRI.TrueDefs.second);
707 if (Input1CRlogical)
708 AllCRLogicalOps.push_back(Elt: createCRLogicalOpInfo(MIParam&: *CRI.TrueDefs.first));
709 if (Input2CRlogical)
710 AllCRLogicalOps.push_back(Elt: createCRLogicalOpInfo(MIParam&: *CRI.TrueDefs.second));
711 }
712 return Changed;
713}
714
715void PPCReduceCRLogicals::collectCRLogicals() {
716 for (MachineBasicBlock &MBB : *MF) {
717 for (MachineInstr &MI : MBB) {
718 if (isCRLogical(MI)) {
719 AllCRLogicalOps.push_back(Elt: createCRLogicalOpInfo(MIParam&: MI));
720 TotalCRLogicals++;
721 if (AllCRLogicalOps.back().IsNullary)
722 TotalNullaryCRLogicals++;
723 else if (AllCRLogicalOps.back().IsBinary)
724 TotalBinaryCRLogicals++;
725 else
726 TotalUnaryCRLogicals++;
727 }
728 }
729 }
730}
731
732INITIALIZE_PASS_BEGIN(PPCReduceCRLogicals, DEBUG_TYPE,
733 "PowerPC Reduce CR logical Operation", false, false)
734INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
735INITIALIZE_PASS_END(PPCReduceCRLogicals, DEBUG_TYPE,
736 "PowerPC Reduce CR logical Operation", false, false)
737
738char PPCReduceCRLogicals::ID = 0;
739FunctionPass*
740llvm::createPPCReduceCRLogicalsPass() { return new PPCReduceCRLogicals(); }
741