LLVM  9.0.0svn
PPCReduceCRLogicals.cpp
Go to the documentation of this file.
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"
26 #include "llvm/Config/llvm-config.h"
27 #include "llvm/Support/Debug.h"
28 
29 using namespace llvm;
30 
31 #define DEBUG_TYPE "ppc-reduce-cr-ops"
32 
33 STATISTIC(NumContainedSingleUseBinOps,
34  "Number of single-use binary CR logical ops contained in a block");
35 STATISTIC(NumToSplitBlocks,
36  "Number of binary CR logical ops that can be used to split blocks");
37 STATISTIC(TotalCRLogicals, "Number of CR logical ops.");
38 STATISTIC(TotalNullaryCRLogicals,
39  "Number of nullary CR logical ops (CRSET/CRUNSET).");
40 STATISTIC(TotalUnaryCRLogicals, "Number of unary CR logical ops.");
41 STATISTIC(TotalBinaryCRLogicals, "Number of CR logical ops.");
42 STATISTIC(NumBlocksSplitOnBinaryCROp,
43  "Number of blocks split on CR binary logical ops.");
44 STATISTIC(NumNotSplitIdenticalOperands,
45  "Number of blocks not split due to operands being identical.");
46 STATISTIC(NumNotSplitChainCopies,
47  "Number of blocks not split due to operands being chained copies.");
48 STATISTIC(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.
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 - 1).isReg()) {
67  MachineInstr *DefMI = MRI->getVRegDef(MI.getOperand(i - 1).getReg());
68  if (DefMI->getParent() == NewMBB ||
69  !OrigMBB->isSuccessor(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.
85  MachineBasicBlock *OrigMBB,
86  MachineBasicBlock *NewMBB,
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(MI.getOperand(i - 1).getReg()).addMBB(NewMBB);
100  break;
101  }
102  }
103  }
104 }
105 
117  if (!OrigBranch || !SplitBefore || !SplitCond)
118  return false;
119  MachineBasicBlock *MBB = OrigBranch->getParent();
120  if (SplitBefore->getParent() != MBB || SplitCond->getParent() != MBB)
121  return false;
122  if (MIToDelete && MIToDelete->getParent() != MBB)
123  return false;
124  if (NewCond && NewCond->getParent() != MBB)
125  return false;
126  return true;
127  }
128 };
129 
130 /// Splits a MachineBasicBlock to branch before \p SplitBefore. The original
131 /// branch is \p OrigBranch. The target of the new branch can either be the same
132 /// as the target of the original branch or the fallthrough successor of the
133 /// original block as determined by \p BranchToFallThrough. The branch
134 /// conditions will be inverted according to \p InvertNewBranch and
135 /// \p InvertOrigBranch. If an instruction that previously fed the branch is to
136 /// be deleted, it is provided in \p MIToDelete and \p NewCond will be used as
137 /// the branch condition. The branch probabilities will be set if the
138 /// MachineBranchProbabilityInfo isn't null.
139 static bool splitMBB(BlockSplitInfo &BSI) {
140  assert(BSI.allInstrsInSameMBB() &&
141  "All instructions must be in the same block.");
142 
143  MachineBasicBlock *ThisMBB = BSI.OrigBranch->getParent();
144  MachineFunction *MF = ThisMBB->getParent();
146  assert(MRI->isSSA() && "Can only do this while the function is in SSA form.");
147  if (ThisMBB->succ_size() != 2) {
148  LLVM_DEBUG(
149  dbgs() << "Don't know how to handle blocks that don't have exactly"
150  << " two successors.\n");
151  return false;
152  }
153 
154  const PPCInstrInfo *TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo();
155  unsigned OrigBROpcode = BSI.OrigBranch->getOpcode();
156  unsigned InvertedOpcode =
157  OrigBROpcode == PPC::BC
158  ? PPC::BCn
159  : OrigBROpcode == PPC::BCn
160  ? PPC::BC
161  : OrigBROpcode == PPC::BCLR ? PPC::BCLRn : PPC::BCLR;
162  unsigned NewBROpcode = BSI.InvertNewBranch ? InvertedOpcode : OrigBROpcode;
163  MachineBasicBlock *OrigTarget = BSI.OrigBranch->getOperand(1).getMBB();
164  MachineBasicBlock *OrigFallThrough = OrigTarget == *ThisMBB->succ_begin()
165  ? *ThisMBB->succ_rbegin()
166  : *ThisMBB->succ_begin();
167  MachineBasicBlock *NewBRTarget =
168  BSI.BranchToFallThrough ? OrigFallThrough : OrigTarget;
169 
170  // It's impossible to know the precise branch probability after the split.
171  // But it still needs to be reasonable, the whole probability to original
172  // targets should not be changed.
173  // After split NewBRTarget will get two incoming edges. Assume P0 is the
174  // original branch probability to NewBRTarget, P1 and P2 are new branch
175  // probabilies to NewBRTarget after split. If the two edge frequencies are
176  // same, then
177  // F * P1 = F * P0 / 2 ==> P1 = P0 / 2
178  // F * (1 - P1) * P2 = F * P1 ==> P2 = P1 / (1 - P1)
179  BranchProbability ProbToNewTarget, ProbFallThrough; // Prob for new Br.
180  BranchProbability ProbOrigTarget, ProbOrigFallThrough; // Prob for orig Br.
181  ProbToNewTarget = ProbFallThrough = BranchProbability::getUnknown();
182  ProbOrigTarget = ProbOrigFallThrough = BranchProbability::getUnknown();
183  if (BSI.MBPI) {
184  if (BSI.BranchToFallThrough) {
185  ProbToNewTarget = BSI.MBPI->getEdgeProbability(ThisMBB, OrigFallThrough) / 2;
186  ProbFallThrough = ProbToNewTarget.getCompl();
187  ProbOrigFallThrough = ProbToNewTarget / ProbToNewTarget.getCompl();
188  ProbOrigTarget = ProbOrigFallThrough.getCompl();
189  } else {
190  ProbToNewTarget = BSI.MBPI->getEdgeProbability(ThisMBB, OrigTarget) / 2;
191  ProbFallThrough = ProbToNewTarget.getCompl();
192  ProbOrigTarget = ProbToNewTarget / ProbToNewTarget.getCompl();
193  ProbOrigFallThrough = ProbOrigTarget.getCompl();
194  }
195  }
196 
197  // Create a new basic block.
198  MachineBasicBlock::iterator InsertPoint = BSI.SplitBefore;
199  const BasicBlock *LLVM_BB = ThisMBB->getBasicBlock();
200  MachineFunction::iterator It = ThisMBB->getIterator();
201  MachineBasicBlock *NewMBB = MF->CreateMachineBasicBlock(LLVM_BB);
202  MF->insert(++It, NewMBB);
203 
204  // Move everything after SplitBefore into the new block.
205  NewMBB->splice(NewMBB->end(), ThisMBB, InsertPoint, ThisMBB->end());
206  NewMBB->transferSuccessors(ThisMBB);
207  if (!ProbOrigTarget.isUnknown()) {
208  auto MBBI = std::find(NewMBB->succ_begin(), NewMBB->succ_end(), OrigTarget);
209  NewMBB->setSuccProbability(MBBI, ProbOrigTarget);
210  MBBI = std::find(NewMBB->succ_begin(), NewMBB->succ_end(), OrigFallThrough);
211  NewMBB->setSuccProbability(MBBI, ProbOrigFallThrough);
212  }
213 
214  // Add the two successors to ThisMBB.
215  ThisMBB->addSuccessor(NewBRTarget, ProbToNewTarget);
216  ThisMBB->addSuccessor(NewMBB, ProbFallThrough);
217 
218  // Add the branches to ThisMBB.
219  BuildMI(*ThisMBB, ThisMBB->end(), BSI.SplitBefore->getDebugLoc(),
220  TII->get(NewBROpcode))
221  .addReg(BSI.SplitCond->getOperand(0).getReg())
222  .addMBB(NewBRTarget);
223  BuildMI(*ThisMBB, ThisMBB->end(), BSI.SplitBefore->getDebugLoc(),
224  TII->get(PPC::B))
225  .addMBB(NewMBB);
226  if (BSI.MIToDelete)
228 
229  // Change the condition on the original branch and invert it if requested.
230  auto FirstTerminator = NewMBB->getFirstTerminator();
231  if (BSI.NewCond) {
232  assert(FirstTerminator->getOperand(0).isReg() &&
233  "Can't update condition of unconditional branch.");
234  FirstTerminator->getOperand(0).setReg(BSI.NewCond->getOperand(0).getReg());
235  }
236  if (BSI.InvertOrigBranch)
237  FirstTerminator->setDesc(TII->get(InvertedOpcode));
238 
239  // If any of the PHIs in the successors of NewMBB reference values that
240  // now come from NewMBB, they need to be updated.
241  for (auto *Succ : NewMBB->successors()) {
242  updatePHIs(Succ, ThisMBB, NewMBB, MRI);
243  }
244  addIncomingValuesToPHIs(NewBRTarget, ThisMBB, NewMBB, MRI);
245 
246  LLVM_DEBUG(dbgs() << "After splitting, ThisMBB:\n"; ThisMBB->dump());
247  LLVM_DEBUG(dbgs() << "NewMBB:\n"; NewMBB->dump());
248  LLVM_DEBUG(dbgs() << "New branch-to block:\n"; NewBRTarget->dump());
249  return true;
250 }
251 
252 static bool isBinary(MachineInstr &MI) {
253  return MI.getNumOperands() == 3;
254 }
255 
256 static bool isNullary(MachineInstr &MI) {
257  return MI.getNumOperands() == 1;
258 }
259 
260 /// Given a CR logical operation \p CROp, branch opcode \p BROp as well as
261 /// a flag to indicate if the first operand of \p CROp is used as the
262 /// SplitBefore operand, determines whether either of the branches are to be
263 /// inverted as well as whether the new target should be the original
264 /// fall-through block.
265 static void
266 computeBranchTargetAndInversion(unsigned CROp, unsigned BROp, bool UsingDef1,
267  bool &InvertNewBranch, bool &InvertOrigBranch,
268  bool &TargetIsFallThrough) {
269  // The conditions under which each of the output operands should be [un]set
270  // can certainly be written much more concisely with just 3 if statements or
271  // ternary expressions. However, this provides a much clearer overview to the
272  // reader as to what is set for each <CROp, BROp, OpUsed> combination.
273  if (BROp == PPC::BC || BROp == PPC::BCLR) {
274  // Regular branches.
275  switch (CROp) {
276  default:
277  llvm_unreachable("Don't know how to handle this CR logical.");
278  case PPC::CROR:
279  InvertNewBranch = false;
280  InvertOrigBranch = false;
281  TargetIsFallThrough = false;
282  return;
283  case PPC::CRAND:
284  InvertNewBranch = true;
285  InvertOrigBranch = false;
286  TargetIsFallThrough = true;
287  return;
288  case PPC::CRNAND:
289  InvertNewBranch = true;
290  InvertOrigBranch = true;
291  TargetIsFallThrough = false;
292  return;
293  case PPC::CRNOR:
294  InvertNewBranch = false;
295  InvertOrigBranch = true;
296  TargetIsFallThrough = true;
297  return;
298  case PPC::CRORC:
299  InvertNewBranch = UsingDef1;
300  InvertOrigBranch = !UsingDef1;
301  TargetIsFallThrough = false;
302  return;
303  case PPC::CRANDC:
304  InvertNewBranch = !UsingDef1;
305  InvertOrigBranch = !UsingDef1;
306  TargetIsFallThrough = true;
307  return;
308  }
309  } else if (BROp == PPC::BCn || BROp == PPC::BCLRn) {
310  // Negated branches.
311  switch (CROp) {
312  default:
313  llvm_unreachable("Don't know how to handle this CR logical.");
314  case PPC::CROR:
315  InvertNewBranch = true;
316  InvertOrigBranch = false;
317  TargetIsFallThrough = true;
318  return;
319  case PPC::CRAND:
320  InvertNewBranch = false;
321  InvertOrigBranch = false;
322  TargetIsFallThrough = false;
323  return;
324  case PPC::CRNAND:
325  InvertNewBranch = false;
326  InvertOrigBranch = true;
327  TargetIsFallThrough = true;
328  return;
329  case PPC::CRNOR:
330  InvertNewBranch = true;
331  InvertOrigBranch = true;
332  TargetIsFallThrough = false;
333  return;
334  case PPC::CRORC:
335  InvertNewBranch = !UsingDef1;
336  InvertOrigBranch = !UsingDef1;
337  TargetIsFallThrough = true;
338  return;
339  case PPC::CRANDC:
340  InvertNewBranch = UsingDef1;
341  InvertOrigBranch = !UsingDef1;
342  TargetIsFallThrough = false;
343  return;
344  }
345  } else
346  llvm_unreachable("Don't know how to handle this branch.");
347 }
348 
349 namespace {
350 
351 class PPCReduceCRLogicals : public MachineFunctionPass {
352 
353 public:
354  static char ID;
355  struct CRLogicalOpInfo {
356  MachineInstr *MI;
357  // FIXME: If chains of copies are to be handled, this should be a vector.
358  std::pair<MachineInstr*, MachineInstr*> CopyDefs;
359  std::pair<MachineInstr*, MachineInstr*> TrueDefs;
360  unsigned IsBinary : 1;
361  unsigned IsNullary : 1;
362  unsigned ContainedInBlock : 1;
363  unsigned FeedsISEL : 1;
364  unsigned FeedsBR : 1;
365  unsigned FeedsLogical : 1;
366  unsigned SingleUse : 1;
367  unsigned DefsSingleUse : 1;
368  unsigned SubregDef1;
369  unsigned SubregDef2;
370  CRLogicalOpInfo() : MI(nullptr), IsBinary(0), IsNullary(0),
371  ContainedInBlock(0), FeedsISEL(0), FeedsBR(0),
372  FeedsLogical(0), SingleUse(0), DefsSingleUse(1),
373  SubregDef1(0), SubregDef2(0) { }
374  void dump();
375  };
376 
377 private:
378  const PPCInstrInfo *TII;
379  MachineFunction *MF;
381  const MachineBranchProbabilityInfo *MBPI;
382 
383  // A vector to contain all the CR logical operations
384  std::vector<CRLogicalOpInfo> AllCRLogicalOps;
385  void initialize(MachineFunction &MFParm);
386  void collectCRLogicals();
387  bool handleCROp(CRLogicalOpInfo &CRI);
388  bool splitBlockOnBinaryCROp(CRLogicalOpInfo &CRI);
389  static bool isCRLogical(MachineInstr &MI) {
390  unsigned Opc = MI.getOpcode();
391  return Opc == PPC::CRAND || Opc == PPC::CRNAND || Opc == PPC::CROR ||
392  Opc == PPC::CRXOR || Opc == PPC::CRNOR || Opc == PPC::CREQV ||
393  Opc == PPC::CRANDC || Opc == PPC::CRORC || Opc == PPC::CRSET ||
394  Opc == PPC::CRUNSET || Opc == PPC::CR6SET || Opc == PPC::CR6UNSET;
395  }
396  bool simplifyCode() {
397  bool Changed = false;
398  // Not using a range-based for loop here as the vector may grow while being
399  // operated on.
400  for (unsigned i = 0; i < AllCRLogicalOps.size(); i++)
401  Changed |= handleCROp(AllCRLogicalOps[i]);
402  return Changed;
403  }
404 
405 public:
406  PPCReduceCRLogicals() : MachineFunctionPass(ID) {
408  }
409 
410  MachineInstr *lookThroughCRCopy(unsigned Reg, unsigned &Subreg,
411  MachineInstr *&CpDef);
412  bool runOnMachineFunction(MachineFunction &MF) override {
413  if (skipFunction(MF.getFunction()))
414  return false;
415 
416  // If the subtarget doesn't use CR bits, there's nothing to do.
417  const PPCSubtarget &STI = MF.getSubtarget<PPCSubtarget>();
418  if (!STI.useCRBits())
419  return false;
420 
421  initialize(MF);
422  collectCRLogicals();
423  return simplifyCode();
424  }
425  CRLogicalOpInfo createCRLogicalOpInfo(MachineInstr &MI);
426  void getAnalysisUsage(AnalysisUsage &AU) const override {
430  }
431 };
432 
433 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
435  dbgs() << "CRLogicalOpMI: ";
436  MI->dump();
437  dbgs() << "IsBinary: " << IsBinary << ", FeedsISEL: " << FeedsISEL;
438  dbgs() << ", FeedsBR: " << FeedsBR << ", FeedsLogical: ";
439  dbgs() << FeedsLogical << ", SingleUse: " << SingleUse;
440  dbgs() << ", DefsSingleUse: " << DefsSingleUse;
441  dbgs() << ", SubregDef1: " << SubregDef1 << ", SubregDef2: ";
442  dbgs() << SubregDef2 << ", ContainedInBlock: " << ContainedInBlock;
443  if (!IsNullary) {
444  dbgs() << "\nDefs:\n";
445  TrueDefs.first->dump();
446  }
447  if (IsBinary)
448  TrueDefs.second->dump();
449  dbgs() << "\n";
450  if (CopyDefs.first) {
451  dbgs() << "CopyDef1: ";
452  CopyDefs.first->dump();
453  }
454  if (CopyDefs.second) {
455  dbgs() << "CopyDef2: ";
456  CopyDefs.second->dump();
457  }
458 }
459 #endif
460 
461 PPCReduceCRLogicals::CRLogicalOpInfo
462 PPCReduceCRLogicals::createCRLogicalOpInfo(MachineInstr &MIParam) {
463  CRLogicalOpInfo Ret;
464  Ret.MI = &MIParam;
465  // Get the defs
466  if (isNullary(MIParam)) {
467  Ret.IsNullary = 1;
468  Ret.TrueDefs = std::make_pair(nullptr, nullptr);
469  Ret.CopyDefs = std::make_pair(nullptr, nullptr);
470  } else {
471  MachineInstr *Def1 = lookThroughCRCopy(MIParam.getOperand(1).getReg(),
472  Ret.SubregDef1, Ret.CopyDefs.first);
473  Ret.DefsSingleUse &=
474  MRI->hasOneNonDBGUse(Def1->getOperand(0).getReg());
475  Ret.DefsSingleUse &=
476  MRI->hasOneNonDBGUse(Ret.CopyDefs.first->getOperand(0).getReg());
477  assert(Def1 && "Must be able to find a definition of operand 1.");
478  if (isBinary(MIParam)) {
479  Ret.IsBinary = 1;
480  MachineInstr *Def2 = lookThroughCRCopy(MIParam.getOperand(2).getReg(),
481  Ret.SubregDef2,
482  Ret.CopyDefs.second);
483  Ret.DefsSingleUse &=
484  MRI->hasOneNonDBGUse(Def2->getOperand(0).getReg());
485  Ret.DefsSingleUse &=
486  MRI->hasOneNonDBGUse(Ret.CopyDefs.second->getOperand(0).getReg());
487  assert(Def2 && "Must be able to find a definition of operand 2.");
488  Ret.TrueDefs = std::make_pair(Def1, Def2);
489  } else {
490  Ret.TrueDefs = std::make_pair(Def1, nullptr);
491  Ret.CopyDefs.second = nullptr;
492  }
493  }
494 
495  Ret.ContainedInBlock = 1;
496  // Get the uses
497  for (MachineInstr &UseMI :
498  MRI->use_nodbg_instructions(MIParam.getOperand(0).getReg())) {
499  unsigned Opc = UseMI.getOpcode();
500  if (Opc == PPC::ISEL || Opc == PPC::ISEL8)
501  Ret.FeedsISEL = 1;
502  if (Opc == PPC::BC || Opc == PPC::BCn || Opc == PPC::BCLR ||
503  Opc == PPC::BCLRn)
504  Ret.FeedsBR = 1;
505  Ret.FeedsLogical = isCRLogical(UseMI);
506  if (UseMI.getParent() != MIParam.getParent())
507  Ret.ContainedInBlock = 0;
508  }
509  Ret.SingleUse = MRI->hasOneNonDBGUse(MIParam.getOperand(0).getReg()) ? 1 : 0;
510 
511  // We now know whether all the uses of the CR logical are in the same block.
512  if (!Ret.IsNullary) {
513  Ret.ContainedInBlock &=
514  (MIParam.getParent() == Ret.TrueDefs.first->getParent());
515  if (Ret.IsBinary)
516  Ret.ContainedInBlock &=
517  (MIParam.getParent() == Ret.TrueDefs.second->getParent());
518  }
519  LLVM_DEBUG(Ret.dump());
520  if (Ret.IsBinary && Ret.ContainedInBlock && Ret.SingleUse) {
521  NumContainedSingleUseBinOps++;
522  if (Ret.FeedsBR && Ret.DefsSingleUse)
523  NumToSplitBlocks++;
524  }
525  return Ret;
526 }
527 
528 /// Looks through a COPY instruction to the actual definition of the CR-bit
529 /// register and returns the instruction that defines it.
530 /// FIXME: This currently handles what is by-far the most common case:
531 /// an instruction that defines a CR field followed by a single copy of a bit
532 /// from that field into a virtual register. If chains of copies need to be
533 /// handled, this should have a loop until a non-copy instruction is found.
534 MachineInstr *PPCReduceCRLogicals::lookThroughCRCopy(unsigned Reg,
535  unsigned &Subreg,
536  MachineInstr *&CpDef) {
537  Subreg = -1;
539  return nullptr;
540  MachineInstr *Copy = MRI->getVRegDef(Reg);
541  CpDef = Copy;
542  if (!Copy->isCopy())
543  return Copy;
544  unsigned CopySrc = Copy->getOperand(1).getReg();
545  Subreg = Copy->getOperand(1).getSubReg();
547  const TargetRegisterInfo *TRI = &TII->getRegisterInfo();
548  // Set the Subreg
549  if (CopySrc == PPC::CR0EQ || CopySrc == PPC::CR6EQ)
550  Subreg = PPC::sub_eq;
551  if (CopySrc == PPC::CR0LT || CopySrc == PPC::CR6LT)
552  Subreg = PPC::sub_lt;
553  if (CopySrc == PPC::CR0GT || CopySrc == PPC::CR6GT)
554  Subreg = PPC::sub_gt;
555  if (CopySrc == PPC::CR0UN || CopySrc == PPC::CR6UN)
556  Subreg = PPC::sub_un;
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(CopySrc, TRI))
561  return &*Me;
562  return nullptr;
563  }
564  return MRI->getVRegDef(CopySrc);
565 }
566 
568  MF = &MFParam;
569  MRI = &MF->getRegInfo();
570  TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo();
571  MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
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.
581 bool PPCReduceCRLogicals::handleCROp(CRLogicalOpInfo &CRI) {
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  if (CRI.IsBinary && CRI.ContainedInBlock && CRI.SingleUse && CRI.FeedsBR &&
586  CRI.DefsSingleUse) {
587  Changed = splitBlockOnBinaryCROp(CRI);
588  if (Changed)
589  NumBlocksSplitOnBinaryCROp++;
590  }
591  return Changed;
592 }
593 
594 /// Splits a block that contains a CR-logical operation that feeds a branch
595 /// and whose operands are produced within the block.
596 /// Example:
597 /// %vr5<def> = CMPDI %vr2, 0; CRRC:%vr5 G8RC:%vr2
598 /// %vr6<def> = COPY %vr5:sub_eq; CRBITRC:%vr6 CRRC:%vr5
599 /// %vr7<def> = CMPDI %vr3, 0; CRRC:%vr7 G8RC:%vr3
600 /// %vr8<def> = COPY %vr7:sub_eq; CRBITRC:%vr8 CRRC:%vr7
601 /// %vr9<def> = CROR %vr6<kill>, %vr8<kill>; CRBITRC:%vr9,%vr6,%vr8
602 /// BC %vr9<kill>, <BB#2>; CRBITRC:%vr9
603 /// Becomes:
604 /// %vr5<def> = CMPDI %vr2, 0; CRRC:%vr5 G8RC:%vr2
605 /// %vr6<def> = COPY %vr5:sub_eq; CRBITRC:%vr6 CRRC:%vr5
606 /// BC %vr6<kill>, <BB#2>; CRBITRC:%vr6
607 ///
608 /// %vr7<def> = CMPDI %vr3, 0; CRRC:%vr7 G8RC:%vr3
609 /// %vr8<def> = COPY %vr7:sub_eq; CRBITRC:%vr8 CRRC:%vr7
610 /// BC %vr9<kill>, <BB#2>; CRBITRC:%vr9
611 bool PPCReduceCRLogicals::splitBlockOnBinaryCROp(CRLogicalOpInfo &CRI) {
612  if (CRI.CopyDefs.first == CRI.CopyDefs.second) {
613  LLVM_DEBUG(dbgs() << "Unable to split as the two operands are the same\n");
614  NumNotSplitIdenticalOperands++;
615  return false;
616  }
617  if (CRI.TrueDefs.first->isCopy() || CRI.TrueDefs.second->isCopy() ||
618  CRI.TrueDefs.first->isPHI() || CRI.TrueDefs.second->isPHI()) {
619  LLVM_DEBUG(
620  dbgs() << "Unable to split because one of the operands is a PHI or "
621  "chain of copies.\n");
622  NumNotSplitChainCopies++;
623  return false;
624  }
625  // Note: keep in sync with computeBranchTargetAndInversion().
626  if (CRI.MI->getOpcode() != PPC::CROR &&
627  CRI.MI->getOpcode() != PPC::CRAND &&
628  CRI.MI->getOpcode() != PPC::CRNOR &&
629  CRI.MI->getOpcode() != PPC::CRNAND &&
630  CRI.MI->getOpcode() != PPC::CRORC &&
631  CRI.MI->getOpcode() != PPC::CRANDC) {
632  LLVM_DEBUG(dbgs() << "Unable to split blocks on this opcode.\n");
633  NumNotSplitWrongOpcode++;
634  return false;
635  }
636  LLVM_DEBUG(dbgs() << "Splitting the following CR op:\n"; CRI.dump());
637  MachineBasicBlock::iterator Def1It = CRI.TrueDefs.first;
638  MachineBasicBlock::iterator Def2It = CRI.TrueDefs.second;
639 
640  bool UsingDef1 = false;
641  MachineInstr *SplitBefore = &*Def2It;
642  for (auto E = CRI.MI->getParent()->end(); Def2It != E; ++Def2It) {
643  if (Def1It == Def2It) { // Def2 comes before Def1.
644  SplitBefore = &*Def1It;
645  UsingDef1 = true;
646  break;
647  }
648  }
649 
650  LLVM_DEBUG(dbgs() << "We will split the following block:\n";);
651  LLVM_DEBUG(CRI.MI->getParent()->dump());
652  LLVM_DEBUG(dbgs() << "Before instruction:\n"; SplitBefore->dump());
653 
654  // Get the branch instruction.
656  MRI->use_nodbg_begin(CRI.MI->getOperand(0).getReg())->getParent();
657 
658  // We want the new block to have no code in it other than the definition
659  // of the input to the CR logical and the CR logical itself. So we move
660  // those to the bottom of the block (just before the branch). Then we
661  // will split before the CR logical.
662  MachineBasicBlock *MBB = SplitBefore->getParent();
663  auto FirstTerminator = MBB->getFirstTerminator();
664  MachineBasicBlock::iterator FirstInstrToMove =
665  UsingDef1 ? CRI.TrueDefs.first : CRI.TrueDefs.second;
666  MachineBasicBlock::iterator SecondInstrToMove =
667  UsingDef1 ? CRI.CopyDefs.first : CRI.CopyDefs.second;
668 
669  // The instructions that need to be moved are not guaranteed to be
670  // contiguous. Move them individually.
671  // FIXME: If one of the operands is a chain of (single use) copies, they
672  // can all be moved and we can still split.
673  MBB->splice(FirstTerminator, MBB, FirstInstrToMove);
674  if (FirstInstrToMove != SecondInstrToMove)
675  MBB->splice(FirstTerminator, MBB, SecondInstrToMove);
676  MBB->splice(FirstTerminator, MBB, CRI.MI);
677 
678  unsigned Opc = CRI.MI->getOpcode();
679  bool InvertOrigBranch, InvertNewBranch, TargetIsFallThrough;
680  computeBranchTargetAndInversion(Opc, Branch->getOpcode(), UsingDef1,
681  InvertNewBranch, InvertOrigBranch,
682  TargetIsFallThrough);
683  MachineInstr *SplitCond =
684  UsingDef1 ? CRI.CopyDefs.second : CRI.CopyDefs.first;
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 { Branch, SplitBefore, SplitCond, InvertNewBranch,
691  InvertOrigBranch, TargetIsFallThrough, MBPI, CRI.MI,
692  UsingDef1 ? CRI.CopyDefs.first : CRI.CopyDefs.second };
693  bool Changed = splitMBB(BSI);
694  // If we've split on a CR logical that is fed by a CR logical,
695  // recompute the source CR logical as it may be usable for splitting.
696  if (Changed) {
697  bool Input1CRlogical =
698  CRI.TrueDefs.first && isCRLogical(*CRI.TrueDefs.first);
699  bool Input2CRlogical =
700  CRI.TrueDefs.second && isCRLogical(*CRI.TrueDefs.second);
701  if (Input1CRlogical)
702  AllCRLogicalOps.push_back(createCRLogicalOpInfo(*CRI.TrueDefs.first));
703  if (Input2CRlogical)
704  AllCRLogicalOps.push_back(createCRLogicalOpInfo(*CRI.TrueDefs.second));
705  }
706  return Changed;
707 }
708 
709 void PPCReduceCRLogicals::collectCRLogicals() {
710  for (MachineBasicBlock &MBB : *MF) {
711  for (MachineInstr &MI : MBB) {
712  if (isCRLogical(MI)) {
713  AllCRLogicalOps.push_back(createCRLogicalOpInfo(MI));
714  TotalCRLogicals++;
715  if (AllCRLogicalOps.back().IsNullary)
716  TotalNullaryCRLogicals++;
717  else if (AllCRLogicalOps.back().IsBinary)
718  TotalBinaryCRLogicals++;
719  else
720  TotalUnaryCRLogicals++;
721  }
722  }
723  }
724 }
725 
726 } // end anonymous namespace
727 
728 INITIALIZE_PASS_BEGIN(PPCReduceCRLogicals, DEBUG_TYPE,
729  "PowerPC Reduce CR logical Operation", false, false)
731 INITIALIZE_PASS_END(PPCReduceCRLogicals, DEBUG_TYPE,
732  "PowerPC Reduce CR logical Operation", false, false)
733 
734 char PPCReduceCRLogicals::ID = 0;
736 llvm::createPPCReduceCRLogicalsPass() { return new PPCReduceCRLogicals(); }
INITIALIZE_PASS_BEGIN(PPCReduceCRLogicals, DEBUG_TYPE, "PowerPC Reduce CR logical Operation", false, false) INITIALIZE_PASS_END(PPCReduceCRLogicals
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
BranchProbability getCompl() const
MachineBasicBlock * getMBB() const
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:384
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned Reg
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
unsigned getSubReg() const
MachineInstr * SplitCond
MachineInstr * OrigBranch
static void dump(StringRef Title, SpillInfo const &Spills)
Definition: CoroFrame.cpp:298
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
iterator_range< succ_iterator > successors()
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:413
static bool isNullary(MachineInstr &MI)
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
void initializePPCReduceCRLogicalsPass(PassRegistry &)
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:410
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
static void updatePHIs(MachineBasicBlock *Successor, MachineBasicBlock *OrigMBB, MachineBasicBlock *NewMBB, MachineRegisterInfo *MRI)
Given a basic block Successor that potentially contains PHIs, this function will look for any incomin...
FunctionPass * createPPCReduceCRLogicalsPass()
MachineInstr * SplitBefore
void dump() const
Definition: Pass.cpp:134
void setSuccProbability(succ_iterator I, BranchProbability Prob)
Set successor probability of a given iterator.
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
unsigned const MachineRegisterInfo * MRI
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
PowerPC Reduce CR logical Operation
ch, gl = CR6[UN]SET ch, inglue - Toggle CR bit 6 for SVR4 vararg calls
MachineInstrBuilder & UseMI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
MachineInstr * NewCond
void setMBB(MachineBasicBlock *MBB)
Represent the analysis usage information of a pass.
static void computeBranchTargetAndInversion(unsigned CROp, unsigned BROp, bool UsingDef1, bool &InvertNewBranch, bool &InvertOrigBranch, bool &TargetIsFallThrough)
Given a CR logical operation CROp, branch opcode BROp as well as a flag to indicate if the first oper...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
bool isCopy() const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1213
static bool isBinary(MachineInstr &MI)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static BranchProbability getUnknown()
Iterator for intrusive lists based on ilist_node.
MachineOperand class - Representation of each machine instruction operand.
MachineInstr * MIToDelete
MachineInstrBuilder MachineInstrBuilder & DefMI
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringRef > StandardNames)
Initialize the set of available library functions based on the specified target triple.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
#define DEBUG_TYPE
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Representation of each machine instruction.
Definition: MachineInstr.h:63
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool useCRBits() const
useCRBits - Return true if we should store and manipulate i1 values in the individual condition regis...
Definition: PPCSubtarget.h:223
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void insert(iterator MBBI, MachineBasicBlock *MBB)
static void addIncomingValuesToPHIs(MachineBasicBlock *Successor, MachineBasicBlock *OrigMBB, MachineBasicBlock *NewMBB, MachineRegisterInfo *MRI)
Given a basic block Successor that potentially contains PHIs, this function will look for PHIs that h...
static const Function * getParent(const Value *V)
IRTranslator LLVM IR MI
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
const MachineBranchProbabilityInfo * MBPI
static bool splitMBB(BlockSplitInfo &BSI)
Splits a MachineBasicBlock to branch before SplitBefore.