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