contrib/llvm/lib/Target/PowerPC/PPCReduceCRLogicals.cpp

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