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