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

source code of llvm/lib/Target/PowerPC/PPCReduceCRLogicals.cpp