LLVM  10.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;
538  if (!Register::isVirtualRegister(Reg))
539  return nullptr;
540  MachineInstr *Copy = MRI->getVRegDef(Reg);
541  CpDef = Copy;
542  if (!Copy->isCopy())
543  return Copy;
544  Register CopySrc = Copy->getOperand(1).getReg();
545  Subreg = Copy->getOperand(1).getSubReg();
546  if (!Register::isVirtualRegister(CopySrc)) {
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:476
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:385
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
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:322
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:414
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:411
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
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
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:1186
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
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:256
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:64
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:226
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 bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
static const Function * getParent(const Value *V)
IRTranslator LLVM IR MI
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
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.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19