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