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