llvm/lib/Target/PowerPC/PPCReduceCRLogicals.cpp

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