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