10b57cec5SDimitry Andric //===---- PPCReduceCRLogicals.cpp - Reduce CR Bit Logical operations ------===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===---------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This pass aims to reduce the number of logical operations on bits in the CR 100b57cec5SDimitry Andric // register. These instructions have a fairly high latency and only a single 110b57cec5SDimitry Andric // pipeline at their disposal in modern PPC cores. Furthermore, they have a 120b57cec5SDimitry Andric // tendency to occur in fairly small blocks where there's little opportunity 130b57cec5SDimitry Andric // to hide the latency between the CR logical operation and its user. 140b57cec5SDimitry Andric // 150b57cec5SDimitry Andric //===---------------------------------------------------------------------===// 160b57cec5SDimitry Andric 170b57cec5SDimitry Andric #include "PPC.h" 180b57cec5SDimitry Andric #include "PPCInstrInfo.h" 190b57cec5SDimitry Andric #include "PPCTargetMachine.h" 200b57cec5SDimitry Andric #include "llvm/ADT/Statistic.h" 210b57cec5SDimitry Andric #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 220b57cec5SDimitry Andric #include "llvm/CodeGen/MachineDominators.h" 230b57cec5SDimitry Andric #include "llvm/CodeGen/MachineFunctionPass.h" 240b57cec5SDimitry Andric #include "llvm/CodeGen/MachineInstrBuilder.h" 250b57cec5SDimitry Andric #include "llvm/CodeGen/MachineRegisterInfo.h" 260b57cec5SDimitry Andric #include "llvm/Config/llvm-config.h" 27480093f4SDimitry Andric #include "llvm/InitializePasses.h" 280b57cec5SDimitry Andric #include "llvm/Support/Debug.h" 290b57cec5SDimitry Andric 300b57cec5SDimitry Andric using namespace llvm; 310b57cec5SDimitry Andric 320b57cec5SDimitry Andric #define DEBUG_TYPE "ppc-reduce-cr-ops" 330b57cec5SDimitry Andric 340b57cec5SDimitry Andric STATISTIC(NumContainedSingleUseBinOps, 350b57cec5SDimitry Andric "Number of single-use binary CR logical ops contained in a block"); 360b57cec5SDimitry Andric STATISTIC(NumToSplitBlocks, 370b57cec5SDimitry Andric "Number of binary CR logical ops that can be used to split blocks"); 380b57cec5SDimitry Andric STATISTIC(TotalCRLogicals, "Number of CR logical ops."); 390b57cec5SDimitry Andric STATISTIC(TotalNullaryCRLogicals, 400b57cec5SDimitry Andric "Number of nullary CR logical ops (CRSET/CRUNSET)."); 410b57cec5SDimitry Andric STATISTIC(TotalUnaryCRLogicals, "Number of unary CR logical ops."); 420b57cec5SDimitry Andric STATISTIC(TotalBinaryCRLogicals, "Number of CR logical ops."); 430b57cec5SDimitry Andric STATISTIC(NumBlocksSplitOnBinaryCROp, 440b57cec5SDimitry Andric "Number of blocks split on CR binary logical ops."); 450b57cec5SDimitry Andric STATISTIC(NumNotSplitIdenticalOperands, 460b57cec5SDimitry Andric "Number of blocks not split due to operands being identical."); 470b57cec5SDimitry Andric STATISTIC(NumNotSplitChainCopies, 480b57cec5SDimitry Andric "Number of blocks not split due to operands being chained copies."); 490b57cec5SDimitry Andric STATISTIC(NumNotSplitWrongOpcode, 500b57cec5SDimitry Andric "Number of blocks not split due to the wrong opcode."); 510b57cec5SDimitry Andric 520b57cec5SDimitry Andric /// Given a basic block \p Successor that potentially contains PHIs, this 530b57cec5SDimitry Andric /// function will look for any incoming values in the PHIs that are supposed to 540b57cec5SDimitry Andric /// be coming from \p OrigMBB but whose definition is actually in \p NewMBB. 550b57cec5SDimitry Andric /// Any such PHIs will be updated to reflect reality. 560b57cec5SDimitry Andric static void updatePHIs(MachineBasicBlock *Successor, MachineBasicBlock *OrigMBB, 570b57cec5SDimitry Andric MachineBasicBlock *NewMBB, MachineRegisterInfo *MRI) { 580b57cec5SDimitry Andric for (auto &MI : Successor->instrs()) { 590b57cec5SDimitry Andric if (!MI.isPHI()) 600b57cec5SDimitry Andric continue; 610b57cec5SDimitry Andric // This is a really ugly-looking loop, but it was pillaged directly from 620b57cec5SDimitry Andric // MachineBasicBlock::transferSuccessorsAndUpdatePHIs(). 630b57cec5SDimitry Andric for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) { 640b57cec5SDimitry Andric MachineOperand &MO = MI.getOperand(i); 650b57cec5SDimitry Andric if (MO.getMBB() == OrigMBB) { 660b57cec5SDimitry Andric // Check if the instruction is actually defined in NewMBB. 670b57cec5SDimitry Andric if (MI.getOperand(i - 1).isReg()) { 680b57cec5SDimitry Andric MachineInstr *DefMI = MRI->getVRegDef(MI.getOperand(i - 1).getReg()); 690b57cec5SDimitry Andric if (DefMI->getParent() == NewMBB || 700b57cec5SDimitry Andric !OrigMBB->isSuccessor(Successor)) { 710b57cec5SDimitry Andric MO.setMBB(NewMBB); 720b57cec5SDimitry Andric break; 730b57cec5SDimitry Andric } 740b57cec5SDimitry Andric } 750b57cec5SDimitry Andric } 760b57cec5SDimitry Andric } 770b57cec5SDimitry Andric } 780b57cec5SDimitry Andric } 790b57cec5SDimitry Andric 800b57cec5SDimitry Andric /// Given a basic block \p Successor that potentially contains PHIs, this 810b57cec5SDimitry Andric /// function will look for PHIs that have an incoming value from \p OrigMBB 820b57cec5SDimitry Andric /// and will add the same incoming value from \p NewMBB. 830b57cec5SDimitry Andric /// NOTE: This should only be used if \p NewMBB is an immediate dominator of 840b57cec5SDimitry Andric /// \p OrigMBB. 850b57cec5SDimitry Andric static void addIncomingValuesToPHIs(MachineBasicBlock *Successor, 860b57cec5SDimitry Andric MachineBasicBlock *OrigMBB, 870b57cec5SDimitry Andric MachineBasicBlock *NewMBB, 880b57cec5SDimitry Andric MachineRegisterInfo *MRI) { 890b57cec5SDimitry Andric assert(OrigMBB->isSuccessor(NewMBB) && 900b57cec5SDimitry Andric "NewMBB must be a successor of OrigMBB"); 910b57cec5SDimitry Andric for (auto &MI : Successor->instrs()) { 920b57cec5SDimitry Andric if (!MI.isPHI()) 930b57cec5SDimitry Andric continue; 940b57cec5SDimitry Andric // This is a really ugly-looking loop, but it was pillaged directly from 950b57cec5SDimitry Andric // MachineBasicBlock::transferSuccessorsAndUpdatePHIs(). 960b57cec5SDimitry Andric for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) { 970b57cec5SDimitry Andric MachineOperand &MO = MI.getOperand(i); 980b57cec5SDimitry Andric if (MO.getMBB() == OrigMBB) { 990b57cec5SDimitry Andric MachineInstrBuilder MIB(*MI.getParent()->getParent(), &MI); 1000b57cec5SDimitry Andric MIB.addReg(MI.getOperand(i - 1).getReg()).addMBB(NewMBB); 1010b57cec5SDimitry Andric break; 1020b57cec5SDimitry Andric } 1030b57cec5SDimitry Andric } 1040b57cec5SDimitry Andric } 1050b57cec5SDimitry Andric } 1060b57cec5SDimitry Andric 1070b57cec5SDimitry Andric struct BlockSplitInfo { 1080b57cec5SDimitry Andric MachineInstr *OrigBranch; 1090b57cec5SDimitry Andric MachineInstr *SplitBefore; 1100b57cec5SDimitry Andric MachineInstr *SplitCond; 1110b57cec5SDimitry Andric bool InvertNewBranch; 1120b57cec5SDimitry Andric bool InvertOrigBranch; 1130b57cec5SDimitry Andric bool BranchToFallThrough; 1140b57cec5SDimitry Andric const MachineBranchProbabilityInfo *MBPI; 1150b57cec5SDimitry Andric MachineInstr *MIToDelete; 1160b57cec5SDimitry Andric MachineInstr *NewCond; 1170b57cec5SDimitry Andric bool allInstrsInSameMBB() { 1180b57cec5SDimitry Andric if (!OrigBranch || !SplitBefore || !SplitCond) 1190b57cec5SDimitry Andric return false; 1200b57cec5SDimitry Andric MachineBasicBlock *MBB = OrigBranch->getParent(); 1210b57cec5SDimitry Andric if (SplitBefore->getParent() != MBB || SplitCond->getParent() != MBB) 1220b57cec5SDimitry Andric return false; 1230b57cec5SDimitry Andric if (MIToDelete && MIToDelete->getParent() != MBB) 1240b57cec5SDimitry Andric return false; 1250b57cec5SDimitry Andric if (NewCond && NewCond->getParent() != MBB) 1260b57cec5SDimitry Andric return false; 1270b57cec5SDimitry Andric return true; 1280b57cec5SDimitry Andric } 1290b57cec5SDimitry Andric }; 1300b57cec5SDimitry Andric 1310b57cec5SDimitry Andric /// Splits a MachineBasicBlock to branch before \p SplitBefore. The original 1320b57cec5SDimitry Andric /// branch is \p OrigBranch. The target of the new branch can either be the same 1330b57cec5SDimitry Andric /// as the target of the original branch or the fallthrough successor of the 1340b57cec5SDimitry Andric /// original block as determined by \p BranchToFallThrough. The branch 1350b57cec5SDimitry Andric /// conditions will be inverted according to \p InvertNewBranch and 1360b57cec5SDimitry Andric /// \p InvertOrigBranch. If an instruction that previously fed the branch is to 1370b57cec5SDimitry Andric /// be deleted, it is provided in \p MIToDelete and \p NewCond will be used as 1380b57cec5SDimitry Andric /// the branch condition. The branch probabilities will be set if the 1390b57cec5SDimitry Andric /// MachineBranchProbabilityInfo isn't null. 1400b57cec5SDimitry Andric static bool splitMBB(BlockSplitInfo &BSI) { 1410b57cec5SDimitry Andric assert(BSI.allInstrsInSameMBB() && 1420b57cec5SDimitry Andric "All instructions must be in the same block."); 1430b57cec5SDimitry Andric 1440b57cec5SDimitry Andric MachineBasicBlock *ThisMBB = BSI.OrigBranch->getParent(); 1450b57cec5SDimitry Andric MachineFunction *MF = ThisMBB->getParent(); 1460b57cec5SDimitry Andric MachineRegisterInfo *MRI = &MF->getRegInfo(); 1470b57cec5SDimitry Andric assert(MRI->isSSA() && "Can only do this while the function is in SSA form."); 1480b57cec5SDimitry Andric if (ThisMBB->succ_size() != 2) { 1490b57cec5SDimitry Andric LLVM_DEBUG( 1500b57cec5SDimitry Andric dbgs() << "Don't know how to handle blocks that don't have exactly" 1510b57cec5SDimitry Andric << " two successors.\n"); 1520b57cec5SDimitry Andric return false; 1530b57cec5SDimitry Andric } 1540b57cec5SDimitry Andric 1550b57cec5SDimitry Andric const PPCInstrInfo *TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo(); 1560b57cec5SDimitry Andric unsigned OrigBROpcode = BSI.OrigBranch->getOpcode(); 1570b57cec5SDimitry Andric unsigned InvertedOpcode = 1580b57cec5SDimitry Andric OrigBROpcode == PPC::BC 1590b57cec5SDimitry Andric ? PPC::BCn 1600b57cec5SDimitry Andric : OrigBROpcode == PPC::BCn 1610b57cec5SDimitry Andric ? PPC::BC 1620b57cec5SDimitry Andric : OrigBROpcode == PPC::BCLR ? PPC::BCLRn : PPC::BCLR; 1630b57cec5SDimitry Andric unsigned NewBROpcode = BSI.InvertNewBranch ? InvertedOpcode : OrigBROpcode; 1640b57cec5SDimitry Andric MachineBasicBlock *OrigTarget = BSI.OrigBranch->getOperand(1).getMBB(); 1650b57cec5SDimitry Andric MachineBasicBlock *OrigFallThrough = OrigTarget == *ThisMBB->succ_begin() 1660b57cec5SDimitry Andric ? *ThisMBB->succ_rbegin() 1670b57cec5SDimitry Andric : *ThisMBB->succ_begin(); 1680b57cec5SDimitry Andric MachineBasicBlock *NewBRTarget = 1690b57cec5SDimitry Andric BSI.BranchToFallThrough ? OrigFallThrough : OrigTarget; 1700b57cec5SDimitry Andric 1710b57cec5SDimitry Andric // It's impossible to know the precise branch probability after the split. 1720b57cec5SDimitry Andric // But it still needs to be reasonable, the whole probability to original 1730b57cec5SDimitry Andric // targets should not be changed. 1740b57cec5SDimitry Andric // After split NewBRTarget will get two incoming edges. Assume P0 is the 1750b57cec5SDimitry Andric // original branch probability to NewBRTarget, P1 and P2 are new branch 1760b57cec5SDimitry Andric // probabilies to NewBRTarget after split. If the two edge frequencies are 1770b57cec5SDimitry Andric // same, then 1780b57cec5SDimitry Andric // F * P1 = F * P0 / 2 ==> P1 = P0 / 2 1790b57cec5SDimitry Andric // F * (1 - P1) * P2 = F * P1 ==> P2 = P1 / (1 - P1) 1800b57cec5SDimitry Andric BranchProbability ProbToNewTarget, ProbFallThrough; // Prob for new Br. 1810b57cec5SDimitry Andric BranchProbability ProbOrigTarget, ProbOrigFallThrough; // Prob for orig Br. 1820b57cec5SDimitry Andric ProbToNewTarget = ProbFallThrough = BranchProbability::getUnknown(); 1830b57cec5SDimitry Andric ProbOrigTarget = ProbOrigFallThrough = BranchProbability::getUnknown(); 1840b57cec5SDimitry Andric if (BSI.MBPI) { 1850b57cec5SDimitry Andric if (BSI.BranchToFallThrough) { 1860b57cec5SDimitry Andric ProbToNewTarget = BSI.MBPI->getEdgeProbability(ThisMBB, OrigFallThrough) / 2; 1870b57cec5SDimitry Andric ProbFallThrough = ProbToNewTarget.getCompl(); 1880b57cec5SDimitry Andric ProbOrigFallThrough = ProbToNewTarget / ProbToNewTarget.getCompl(); 1890b57cec5SDimitry Andric ProbOrigTarget = ProbOrigFallThrough.getCompl(); 1900b57cec5SDimitry Andric } else { 1910b57cec5SDimitry Andric ProbToNewTarget = BSI.MBPI->getEdgeProbability(ThisMBB, OrigTarget) / 2; 1920b57cec5SDimitry Andric ProbFallThrough = ProbToNewTarget.getCompl(); 1930b57cec5SDimitry Andric ProbOrigTarget = ProbToNewTarget / ProbToNewTarget.getCompl(); 1940b57cec5SDimitry Andric ProbOrigFallThrough = ProbOrigTarget.getCompl(); 1950b57cec5SDimitry Andric } 1960b57cec5SDimitry Andric } 1970b57cec5SDimitry Andric 1980b57cec5SDimitry Andric // Create a new basic block. 1990b57cec5SDimitry Andric MachineBasicBlock::iterator InsertPoint = BSI.SplitBefore; 2000b57cec5SDimitry Andric const BasicBlock *LLVM_BB = ThisMBB->getBasicBlock(); 2010b57cec5SDimitry Andric MachineFunction::iterator It = ThisMBB->getIterator(); 2020b57cec5SDimitry Andric MachineBasicBlock *NewMBB = MF->CreateMachineBasicBlock(LLVM_BB); 2030b57cec5SDimitry Andric MF->insert(++It, NewMBB); 2040b57cec5SDimitry Andric 2050b57cec5SDimitry Andric // Move everything after SplitBefore into the new block. 2060b57cec5SDimitry Andric NewMBB->splice(NewMBB->end(), ThisMBB, InsertPoint, ThisMBB->end()); 2070b57cec5SDimitry Andric NewMBB->transferSuccessors(ThisMBB); 2080b57cec5SDimitry Andric if (!ProbOrigTarget.isUnknown()) { 209e8d8bef9SDimitry Andric auto MBBI = find(NewMBB->successors(), OrigTarget); 2100b57cec5SDimitry Andric NewMBB->setSuccProbability(MBBI, ProbOrigTarget); 211e8d8bef9SDimitry Andric MBBI = find(NewMBB->successors(), OrigFallThrough); 2120b57cec5SDimitry Andric NewMBB->setSuccProbability(MBBI, ProbOrigFallThrough); 2130b57cec5SDimitry Andric } 2140b57cec5SDimitry Andric 2150b57cec5SDimitry Andric // Add the two successors to ThisMBB. 2160b57cec5SDimitry Andric ThisMBB->addSuccessor(NewBRTarget, ProbToNewTarget); 2170b57cec5SDimitry Andric ThisMBB->addSuccessor(NewMBB, ProbFallThrough); 2180b57cec5SDimitry Andric 2190b57cec5SDimitry Andric // Add the branches to ThisMBB. 2200b57cec5SDimitry Andric BuildMI(*ThisMBB, ThisMBB->end(), BSI.SplitBefore->getDebugLoc(), 2210b57cec5SDimitry Andric TII->get(NewBROpcode)) 2220b57cec5SDimitry Andric .addReg(BSI.SplitCond->getOperand(0).getReg()) 2230b57cec5SDimitry Andric .addMBB(NewBRTarget); 2240b57cec5SDimitry Andric BuildMI(*ThisMBB, ThisMBB->end(), BSI.SplitBefore->getDebugLoc(), 2250b57cec5SDimitry Andric TII->get(PPC::B)) 2260b57cec5SDimitry Andric .addMBB(NewMBB); 2270b57cec5SDimitry Andric if (BSI.MIToDelete) 2280b57cec5SDimitry Andric BSI.MIToDelete->eraseFromParent(); 2290b57cec5SDimitry Andric 2300b57cec5SDimitry Andric // Change the condition on the original branch and invert it if requested. 2310b57cec5SDimitry Andric auto FirstTerminator = NewMBB->getFirstTerminator(); 2320b57cec5SDimitry Andric if (BSI.NewCond) { 2330b57cec5SDimitry Andric assert(FirstTerminator->getOperand(0).isReg() && 2340b57cec5SDimitry Andric "Can't update condition of unconditional branch."); 2350b57cec5SDimitry Andric FirstTerminator->getOperand(0).setReg(BSI.NewCond->getOperand(0).getReg()); 2360b57cec5SDimitry Andric } 2370b57cec5SDimitry Andric if (BSI.InvertOrigBranch) 2380b57cec5SDimitry Andric FirstTerminator->setDesc(TII->get(InvertedOpcode)); 2390b57cec5SDimitry Andric 2400b57cec5SDimitry Andric // If any of the PHIs in the successors of NewMBB reference values that 2410b57cec5SDimitry Andric // now come from NewMBB, they need to be updated. 2420b57cec5SDimitry Andric for (auto *Succ : NewMBB->successors()) { 2430b57cec5SDimitry Andric updatePHIs(Succ, ThisMBB, NewMBB, MRI); 2440b57cec5SDimitry Andric } 2450b57cec5SDimitry Andric addIncomingValuesToPHIs(NewBRTarget, ThisMBB, NewMBB, MRI); 2460b57cec5SDimitry Andric 2470b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "After splitting, ThisMBB:\n"; ThisMBB->dump()); 2480b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "NewMBB:\n"; NewMBB->dump()); 2490b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "New branch-to block:\n"; NewBRTarget->dump()); 2500b57cec5SDimitry Andric return true; 2510b57cec5SDimitry Andric } 2520b57cec5SDimitry Andric 2530b57cec5SDimitry Andric static bool isBinary(MachineInstr &MI) { 2540b57cec5SDimitry Andric return MI.getNumOperands() == 3; 2550b57cec5SDimitry Andric } 2560b57cec5SDimitry Andric 2570b57cec5SDimitry Andric static bool isNullary(MachineInstr &MI) { 2580b57cec5SDimitry Andric return MI.getNumOperands() == 1; 2590b57cec5SDimitry Andric } 2600b57cec5SDimitry Andric 2610b57cec5SDimitry Andric /// Given a CR logical operation \p CROp, branch opcode \p BROp as well as 2620b57cec5SDimitry Andric /// a flag to indicate if the first operand of \p CROp is used as the 2630b57cec5SDimitry Andric /// SplitBefore operand, determines whether either of the branches are to be 2640b57cec5SDimitry Andric /// inverted as well as whether the new target should be the original 2650b57cec5SDimitry Andric /// fall-through block. 2660b57cec5SDimitry Andric static void 2670b57cec5SDimitry Andric computeBranchTargetAndInversion(unsigned CROp, unsigned BROp, bool UsingDef1, 2680b57cec5SDimitry Andric bool &InvertNewBranch, bool &InvertOrigBranch, 2690b57cec5SDimitry Andric bool &TargetIsFallThrough) { 2700b57cec5SDimitry Andric // The conditions under which each of the output operands should be [un]set 2710b57cec5SDimitry Andric // can certainly be written much more concisely with just 3 if statements or 2720b57cec5SDimitry Andric // ternary expressions. However, this provides a much clearer overview to the 2730b57cec5SDimitry Andric // reader as to what is set for each <CROp, BROp, OpUsed> combination. 2740b57cec5SDimitry Andric if (BROp == PPC::BC || BROp == PPC::BCLR) { 2750b57cec5SDimitry Andric // Regular branches. 2760b57cec5SDimitry Andric switch (CROp) { 2770b57cec5SDimitry Andric default: 2780b57cec5SDimitry Andric llvm_unreachable("Don't know how to handle this CR logical."); 2790b57cec5SDimitry Andric case PPC::CROR: 2800b57cec5SDimitry Andric InvertNewBranch = false; 2810b57cec5SDimitry Andric InvertOrigBranch = false; 2820b57cec5SDimitry Andric TargetIsFallThrough = false; 2830b57cec5SDimitry Andric return; 2840b57cec5SDimitry Andric case PPC::CRAND: 2850b57cec5SDimitry Andric InvertNewBranch = true; 2860b57cec5SDimitry Andric InvertOrigBranch = false; 2870b57cec5SDimitry Andric TargetIsFallThrough = true; 2880b57cec5SDimitry Andric return; 2890b57cec5SDimitry Andric case PPC::CRNAND: 2900b57cec5SDimitry Andric InvertNewBranch = true; 2910b57cec5SDimitry Andric InvertOrigBranch = true; 2920b57cec5SDimitry Andric TargetIsFallThrough = false; 2930b57cec5SDimitry Andric return; 2940b57cec5SDimitry Andric case PPC::CRNOR: 2950b57cec5SDimitry Andric InvertNewBranch = false; 2960b57cec5SDimitry Andric InvertOrigBranch = true; 2970b57cec5SDimitry Andric TargetIsFallThrough = true; 2980b57cec5SDimitry Andric return; 2990b57cec5SDimitry Andric case PPC::CRORC: 3000b57cec5SDimitry Andric InvertNewBranch = UsingDef1; 3010b57cec5SDimitry Andric InvertOrigBranch = !UsingDef1; 3020b57cec5SDimitry Andric TargetIsFallThrough = false; 3030b57cec5SDimitry Andric return; 3040b57cec5SDimitry Andric case PPC::CRANDC: 3050b57cec5SDimitry Andric InvertNewBranch = !UsingDef1; 3060b57cec5SDimitry Andric InvertOrigBranch = !UsingDef1; 3070b57cec5SDimitry Andric TargetIsFallThrough = true; 3080b57cec5SDimitry Andric return; 3090b57cec5SDimitry Andric } 3100b57cec5SDimitry Andric } else if (BROp == PPC::BCn || BROp == PPC::BCLRn) { 3110b57cec5SDimitry Andric // Negated branches. 3120b57cec5SDimitry Andric switch (CROp) { 3130b57cec5SDimitry Andric default: 3140b57cec5SDimitry Andric llvm_unreachable("Don't know how to handle this CR logical."); 3150b57cec5SDimitry Andric case PPC::CROR: 3160b57cec5SDimitry Andric InvertNewBranch = true; 3170b57cec5SDimitry Andric InvertOrigBranch = false; 3180b57cec5SDimitry Andric TargetIsFallThrough = true; 3190b57cec5SDimitry Andric return; 3200b57cec5SDimitry Andric case PPC::CRAND: 3210b57cec5SDimitry Andric InvertNewBranch = false; 3220b57cec5SDimitry Andric InvertOrigBranch = false; 3230b57cec5SDimitry Andric TargetIsFallThrough = false; 3240b57cec5SDimitry Andric return; 3250b57cec5SDimitry Andric case PPC::CRNAND: 3260b57cec5SDimitry Andric InvertNewBranch = false; 3270b57cec5SDimitry Andric InvertOrigBranch = true; 3280b57cec5SDimitry Andric TargetIsFallThrough = true; 3290b57cec5SDimitry Andric return; 3300b57cec5SDimitry Andric case PPC::CRNOR: 3310b57cec5SDimitry Andric InvertNewBranch = true; 3320b57cec5SDimitry Andric InvertOrigBranch = true; 3330b57cec5SDimitry Andric TargetIsFallThrough = false; 3340b57cec5SDimitry Andric return; 3350b57cec5SDimitry Andric case PPC::CRORC: 3360b57cec5SDimitry Andric InvertNewBranch = !UsingDef1; 3370b57cec5SDimitry Andric InvertOrigBranch = !UsingDef1; 3380b57cec5SDimitry Andric TargetIsFallThrough = true; 3390b57cec5SDimitry Andric return; 3400b57cec5SDimitry Andric case PPC::CRANDC: 3410b57cec5SDimitry Andric InvertNewBranch = UsingDef1; 3420b57cec5SDimitry Andric InvertOrigBranch = !UsingDef1; 3430b57cec5SDimitry Andric TargetIsFallThrough = false; 3440b57cec5SDimitry Andric return; 3450b57cec5SDimitry Andric } 3460b57cec5SDimitry Andric } else 3470b57cec5SDimitry Andric llvm_unreachable("Don't know how to handle this branch."); 3480b57cec5SDimitry Andric } 3490b57cec5SDimitry Andric 3500b57cec5SDimitry Andric namespace { 3510b57cec5SDimitry Andric 3520b57cec5SDimitry Andric class PPCReduceCRLogicals : public MachineFunctionPass { 3530b57cec5SDimitry Andric 3540b57cec5SDimitry Andric public: 3550b57cec5SDimitry Andric static char ID; 3560b57cec5SDimitry Andric struct CRLogicalOpInfo { 3570b57cec5SDimitry Andric MachineInstr *MI; 3580b57cec5SDimitry Andric // FIXME: If chains of copies are to be handled, this should be a vector. 3590b57cec5SDimitry Andric std::pair<MachineInstr*, MachineInstr*> CopyDefs; 3600b57cec5SDimitry Andric std::pair<MachineInstr*, MachineInstr*> TrueDefs; 3610b57cec5SDimitry Andric unsigned IsBinary : 1; 3620b57cec5SDimitry Andric unsigned IsNullary : 1; 3630b57cec5SDimitry Andric unsigned ContainedInBlock : 1; 3640b57cec5SDimitry Andric unsigned FeedsISEL : 1; 3650b57cec5SDimitry Andric unsigned FeedsBR : 1; 3660b57cec5SDimitry Andric unsigned FeedsLogical : 1; 3670b57cec5SDimitry Andric unsigned SingleUse : 1; 3680b57cec5SDimitry Andric unsigned DefsSingleUse : 1; 3690b57cec5SDimitry Andric unsigned SubregDef1; 3700b57cec5SDimitry Andric unsigned SubregDef2; 3710b57cec5SDimitry Andric CRLogicalOpInfo() : MI(nullptr), IsBinary(0), IsNullary(0), 3720b57cec5SDimitry Andric ContainedInBlock(0), FeedsISEL(0), FeedsBR(0), 3730b57cec5SDimitry Andric FeedsLogical(0), SingleUse(0), DefsSingleUse(1), 3740b57cec5SDimitry Andric SubregDef1(0), SubregDef2(0) { } 3750b57cec5SDimitry Andric void dump(); 3760b57cec5SDimitry Andric }; 3770b57cec5SDimitry Andric 3780b57cec5SDimitry Andric private: 379480093f4SDimitry Andric const PPCInstrInfo *TII = nullptr; 380480093f4SDimitry Andric MachineFunction *MF = nullptr; 381480093f4SDimitry Andric MachineRegisterInfo *MRI = nullptr; 382480093f4SDimitry Andric const MachineBranchProbabilityInfo *MBPI = nullptr; 3830b57cec5SDimitry Andric 3840b57cec5SDimitry Andric // A vector to contain all the CR logical operations 3858bcb0991SDimitry Andric SmallVector<CRLogicalOpInfo, 16> AllCRLogicalOps; 3860b57cec5SDimitry Andric void initialize(MachineFunction &MFParm); 3870b57cec5SDimitry Andric void collectCRLogicals(); 3888bcb0991SDimitry Andric bool handleCROp(unsigned Idx); 3890b57cec5SDimitry Andric bool splitBlockOnBinaryCROp(CRLogicalOpInfo &CRI); 3900b57cec5SDimitry Andric static bool isCRLogical(MachineInstr &MI) { 3910b57cec5SDimitry Andric unsigned Opc = MI.getOpcode(); 3920b57cec5SDimitry Andric return Opc == PPC::CRAND || Opc == PPC::CRNAND || Opc == PPC::CROR || 393bdd1243dSDimitry Andric Opc == PPC::CRXOR || Opc == PPC::CRNOR || Opc == PPC::CRNOT || 394bdd1243dSDimitry Andric Opc == PPC::CREQV || Opc == PPC::CRANDC || Opc == PPC::CRORC || 395bdd1243dSDimitry Andric Opc == PPC::CRSET || Opc == PPC::CRUNSET || Opc == PPC::CR6SET || 396bdd1243dSDimitry Andric Opc == PPC::CR6UNSET; 3970b57cec5SDimitry Andric } 3980b57cec5SDimitry Andric bool simplifyCode() { 3990b57cec5SDimitry Andric bool Changed = false; 4000b57cec5SDimitry Andric // Not using a range-based for loop here as the vector may grow while being 4010b57cec5SDimitry Andric // operated on. 4020b57cec5SDimitry Andric for (unsigned i = 0; i < AllCRLogicalOps.size(); i++) 4038bcb0991SDimitry Andric Changed |= handleCROp(i); 4040b57cec5SDimitry Andric return Changed; 4050b57cec5SDimitry Andric } 4060b57cec5SDimitry Andric 4070b57cec5SDimitry Andric public: 4080b57cec5SDimitry Andric PPCReduceCRLogicals() : MachineFunctionPass(ID) { 4090b57cec5SDimitry Andric initializePPCReduceCRLogicalsPass(*PassRegistry::getPassRegistry()); 4100b57cec5SDimitry Andric } 4110b57cec5SDimitry Andric 4120b57cec5SDimitry Andric MachineInstr *lookThroughCRCopy(unsigned Reg, unsigned &Subreg, 4130b57cec5SDimitry Andric MachineInstr *&CpDef); 4140b57cec5SDimitry Andric bool runOnMachineFunction(MachineFunction &MF) override { 4150b57cec5SDimitry Andric if (skipFunction(MF.getFunction())) 4160b57cec5SDimitry Andric return false; 4170b57cec5SDimitry Andric 4180b57cec5SDimitry Andric // If the subtarget doesn't use CR bits, there's nothing to do. 4190b57cec5SDimitry Andric const PPCSubtarget &STI = MF.getSubtarget<PPCSubtarget>(); 4200b57cec5SDimitry Andric if (!STI.useCRBits()) 4210b57cec5SDimitry Andric return false; 4220b57cec5SDimitry Andric 4230b57cec5SDimitry Andric initialize(MF); 4240b57cec5SDimitry Andric collectCRLogicals(); 4250b57cec5SDimitry Andric return simplifyCode(); 4260b57cec5SDimitry Andric } 4270b57cec5SDimitry Andric CRLogicalOpInfo createCRLogicalOpInfo(MachineInstr &MI); 4280b57cec5SDimitry Andric void getAnalysisUsage(AnalysisUsage &AU) const override { 429*0fca6ea1SDimitry Andric AU.addRequired<MachineBranchProbabilityInfoWrapperPass>(); 430*0fca6ea1SDimitry Andric AU.addRequired<MachineDominatorTreeWrapperPass>(); 4310b57cec5SDimitry Andric MachineFunctionPass::getAnalysisUsage(AU); 4320b57cec5SDimitry Andric } 4330b57cec5SDimitry Andric }; 4340b57cec5SDimitry Andric 4350b57cec5SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 4360b57cec5SDimitry Andric LLVM_DUMP_METHOD void PPCReduceCRLogicals::CRLogicalOpInfo::dump() { 4370b57cec5SDimitry Andric dbgs() << "CRLogicalOpMI: "; 4380b57cec5SDimitry Andric MI->dump(); 4390b57cec5SDimitry Andric dbgs() << "IsBinary: " << IsBinary << ", FeedsISEL: " << FeedsISEL; 4400b57cec5SDimitry Andric dbgs() << ", FeedsBR: " << FeedsBR << ", FeedsLogical: "; 4410b57cec5SDimitry Andric dbgs() << FeedsLogical << ", SingleUse: " << SingleUse; 4420b57cec5SDimitry Andric dbgs() << ", DefsSingleUse: " << DefsSingleUse; 4430b57cec5SDimitry Andric dbgs() << ", SubregDef1: " << SubregDef1 << ", SubregDef2: "; 4440b57cec5SDimitry Andric dbgs() << SubregDef2 << ", ContainedInBlock: " << ContainedInBlock; 4450b57cec5SDimitry Andric if (!IsNullary) { 4460b57cec5SDimitry Andric dbgs() << "\nDefs:\n"; 4470b57cec5SDimitry Andric TrueDefs.first->dump(); 4480b57cec5SDimitry Andric } 4490b57cec5SDimitry Andric if (IsBinary) 4500b57cec5SDimitry Andric TrueDefs.second->dump(); 4510b57cec5SDimitry Andric dbgs() << "\n"; 4520b57cec5SDimitry Andric if (CopyDefs.first) { 4530b57cec5SDimitry Andric dbgs() << "CopyDef1: "; 4540b57cec5SDimitry Andric CopyDefs.first->dump(); 4550b57cec5SDimitry Andric } 4560b57cec5SDimitry Andric if (CopyDefs.second) { 4570b57cec5SDimitry Andric dbgs() << "CopyDef2: "; 4580b57cec5SDimitry Andric CopyDefs.second->dump(); 4590b57cec5SDimitry Andric } 4600b57cec5SDimitry Andric } 4610b57cec5SDimitry Andric #endif 4620b57cec5SDimitry Andric 4630b57cec5SDimitry Andric PPCReduceCRLogicals::CRLogicalOpInfo 4640b57cec5SDimitry Andric PPCReduceCRLogicals::createCRLogicalOpInfo(MachineInstr &MIParam) { 4650b57cec5SDimitry Andric CRLogicalOpInfo Ret; 4660b57cec5SDimitry Andric Ret.MI = &MIParam; 4670b57cec5SDimitry Andric // Get the defs 4680b57cec5SDimitry Andric if (isNullary(MIParam)) { 4690b57cec5SDimitry Andric Ret.IsNullary = 1; 4700b57cec5SDimitry Andric Ret.TrueDefs = std::make_pair(nullptr, nullptr); 4710b57cec5SDimitry Andric Ret.CopyDefs = std::make_pair(nullptr, nullptr); 4720b57cec5SDimitry Andric } else { 4730b57cec5SDimitry Andric MachineInstr *Def1 = lookThroughCRCopy(MIParam.getOperand(1).getReg(), 4740b57cec5SDimitry Andric Ret.SubregDef1, Ret.CopyDefs.first); 475480093f4SDimitry Andric assert(Def1 && "Must be able to find a definition of operand 1."); 4760b57cec5SDimitry Andric Ret.DefsSingleUse &= 4770b57cec5SDimitry Andric MRI->hasOneNonDBGUse(Def1->getOperand(0).getReg()); 4780b57cec5SDimitry Andric Ret.DefsSingleUse &= 4790b57cec5SDimitry Andric MRI->hasOneNonDBGUse(Ret.CopyDefs.first->getOperand(0).getReg()); 4800b57cec5SDimitry Andric if (isBinary(MIParam)) { 4810b57cec5SDimitry Andric Ret.IsBinary = 1; 4820b57cec5SDimitry Andric MachineInstr *Def2 = lookThroughCRCopy(MIParam.getOperand(2).getReg(), 4830b57cec5SDimitry Andric Ret.SubregDef2, 4840b57cec5SDimitry Andric Ret.CopyDefs.second); 485480093f4SDimitry Andric assert(Def2 && "Must be able to find a definition of operand 2."); 4860b57cec5SDimitry Andric Ret.DefsSingleUse &= 4870b57cec5SDimitry Andric MRI->hasOneNonDBGUse(Def2->getOperand(0).getReg()); 4880b57cec5SDimitry Andric Ret.DefsSingleUse &= 4890b57cec5SDimitry Andric MRI->hasOneNonDBGUse(Ret.CopyDefs.second->getOperand(0).getReg()); 4900b57cec5SDimitry Andric Ret.TrueDefs = std::make_pair(Def1, Def2); 4910b57cec5SDimitry Andric } else { 4920b57cec5SDimitry Andric Ret.TrueDefs = std::make_pair(Def1, nullptr); 4930b57cec5SDimitry Andric Ret.CopyDefs.second = nullptr; 4940b57cec5SDimitry Andric } 4950b57cec5SDimitry Andric } 4960b57cec5SDimitry Andric 4970b57cec5SDimitry Andric Ret.ContainedInBlock = 1; 4980b57cec5SDimitry Andric // Get the uses 4990b57cec5SDimitry Andric for (MachineInstr &UseMI : 5000b57cec5SDimitry Andric MRI->use_nodbg_instructions(MIParam.getOperand(0).getReg())) { 5010b57cec5SDimitry Andric unsigned Opc = UseMI.getOpcode(); 5020b57cec5SDimitry Andric if (Opc == PPC::ISEL || Opc == PPC::ISEL8) 5030b57cec5SDimitry Andric Ret.FeedsISEL = 1; 5040b57cec5SDimitry Andric if (Opc == PPC::BC || Opc == PPC::BCn || Opc == PPC::BCLR || 5050b57cec5SDimitry Andric Opc == PPC::BCLRn) 5060b57cec5SDimitry Andric Ret.FeedsBR = 1; 5070b57cec5SDimitry Andric Ret.FeedsLogical = isCRLogical(UseMI); 5080b57cec5SDimitry Andric if (UseMI.getParent() != MIParam.getParent()) 5090b57cec5SDimitry Andric Ret.ContainedInBlock = 0; 5100b57cec5SDimitry Andric } 5110b57cec5SDimitry Andric Ret.SingleUse = MRI->hasOneNonDBGUse(MIParam.getOperand(0).getReg()) ? 1 : 0; 5120b57cec5SDimitry Andric 5130b57cec5SDimitry Andric // We now know whether all the uses of the CR logical are in the same block. 5140b57cec5SDimitry Andric if (!Ret.IsNullary) { 5150b57cec5SDimitry Andric Ret.ContainedInBlock &= 5160b57cec5SDimitry Andric (MIParam.getParent() == Ret.TrueDefs.first->getParent()); 5170b57cec5SDimitry Andric if (Ret.IsBinary) 5180b57cec5SDimitry Andric Ret.ContainedInBlock &= 5190b57cec5SDimitry Andric (MIParam.getParent() == Ret.TrueDefs.second->getParent()); 5200b57cec5SDimitry Andric } 5210b57cec5SDimitry Andric LLVM_DEBUG(Ret.dump()); 5220b57cec5SDimitry Andric if (Ret.IsBinary && Ret.ContainedInBlock && Ret.SingleUse) { 5230b57cec5SDimitry Andric NumContainedSingleUseBinOps++; 5240b57cec5SDimitry Andric if (Ret.FeedsBR && Ret.DefsSingleUse) 5250b57cec5SDimitry Andric NumToSplitBlocks++; 5260b57cec5SDimitry Andric } 5270b57cec5SDimitry Andric return Ret; 5280b57cec5SDimitry Andric } 5290b57cec5SDimitry Andric 5300b57cec5SDimitry Andric /// Looks through a COPY instruction to the actual definition of the CR-bit 5310b57cec5SDimitry Andric /// register and returns the instruction that defines it. 5320b57cec5SDimitry Andric /// FIXME: This currently handles what is by-far the most common case: 5330b57cec5SDimitry Andric /// an instruction that defines a CR field followed by a single copy of a bit 5340b57cec5SDimitry Andric /// from that field into a virtual register. If chains of copies need to be 5350b57cec5SDimitry Andric /// handled, this should have a loop until a non-copy instruction is found. 5360b57cec5SDimitry Andric MachineInstr *PPCReduceCRLogicals::lookThroughCRCopy(unsigned Reg, 5370b57cec5SDimitry Andric unsigned &Subreg, 5380b57cec5SDimitry Andric MachineInstr *&CpDef) { 5390b57cec5SDimitry Andric Subreg = -1; 5408bcb0991SDimitry Andric if (!Register::isVirtualRegister(Reg)) 5410b57cec5SDimitry Andric return nullptr; 5420b57cec5SDimitry Andric MachineInstr *Copy = MRI->getVRegDef(Reg); 5430b57cec5SDimitry Andric CpDef = Copy; 5440b57cec5SDimitry Andric if (!Copy->isCopy()) 5450b57cec5SDimitry Andric return Copy; 5468bcb0991SDimitry Andric Register CopySrc = Copy->getOperand(1).getReg(); 5470b57cec5SDimitry Andric Subreg = Copy->getOperand(1).getSubReg(); 548bdd1243dSDimitry Andric if (!CopySrc.isVirtual()) { 5490b57cec5SDimitry Andric const TargetRegisterInfo *TRI = &TII->getRegisterInfo(); 5500b57cec5SDimitry Andric // Set the Subreg 5510b57cec5SDimitry Andric if (CopySrc == PPC::CR0EQ || CopySrc == PPC::CR6EQ) 5520b57cec5SDimitry Andric Subreg = PPC::sub_eq; 5530b57cec5SDimitry Andric if (CopySrc == PPC::CR0LT || CopySrc == PPC::CR6LT) 5540b57cec5SDimitry Andric Subreg = PPC::sub_lt; 5550b57cec5SDimitry Andric if (CopySrc == PPC::CR0GT || CopySrc == PPC::CR6GT) 5560b57cec5SDimitry Andric Subreg = PPC::sub_gt; 5570b57cec5SDimitry Andric if (CopySrc == PPC::CR0UN || CopySrc == PPC::CR6UN) 5580b57cec5SDimitry Andric Subreg = PPC::sub_un; 5590b57cec5SDimitry Andric // Loop backwards and return the first MI that modifies the physical CR Reg. 5600b57cec5SDimitry Andric MachineBasicBlock::iterator Me = Copy, B = Copy->getParent()->begin(); 5610b57cec5SDimitry Andric while (Me != B) 5620b57cec5SDimitry Andric if ((--Me)->modifiesRegister(CopySrc, TRI)) 5630b57cec5SDimitry Andric return &*Me; 5640b57cec5SDimitry Andric return nullptr; 5650b57cec5SDimitry Andric } 5660b57cec5SDimitry Andric return MRI->getVRegDef(CopySrc); 5670b57cec5SDimitry Andric } 5680b57cec5SDimitry Andric 5690b57cec5SDimitry Andric void PPCReduceCRLogicals::initialize(MachineFunction &MFParam) { 5700b57cec5SDimitry Andric MF = &MFParam; 5710b57cec5SDimitry Andric MRI = &MF->getRegInfo(); 5720b57cec5SDimitry Andric TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo(); 573*0fca6ea1SDimitry Andric MBPI = &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI(); 5740b57cec5SDimitry Andric 5750b57cec5SDimitry Andric AllCRLogicalOps.clear(); 5760b57cec5SDimitry Andric } 5770b57cec5SDimitry Andric 5780b57cec5SDimitry Andric /// Contains all the implemented transformations on CR logical operations. 5790b57cec5SDimitry Andric /// For example, a binary CR logical can be used to split a block on its inputs, 5800b57cec5SDimitry Andric /// a unary CR logical might be used to change the condition code on a 5810b57cec5SDimitry Andric /// comparison feeding it. A nullary CR logical might simply be removable 5820b57cec5SDimitry Andric /// if the user of the bit it [un]sets can be transformed. 5838bcb0991SDimitry Andric bool PPCReduceCRLogicals::handleCROp(unsigned Idx) { 5840b57cec5SDimitry Andric // We can definitely split a block on the inputs to a binary CR operation 5850b57cec5SDimitry Andric // whose defs and (single) use are within the same block. 5860b57cec5SDimitry Andric bool Changed = false; 5878bcb0991SDimitry Andric CRLogicalOpInfo CRI = AllCRLogicalOps[Idx]; 5880b57cec5SDimitry Andric if (CRI.IsBinary && CRI.ContainedInBlock && CRI.SingleUse && CRI.FeedsBR && 5890b57cec5SDimitry Andric CRI.DefsSingleUse) { 5900b57cec5SDimitry Andric Changed = splitBlockOnBinaryCROp(CRI); 5910b57cec5SDimitry Andric if (Changed) 5920b57cec5SDimitry Andric NumBlocksSplitOnBinaryCROp++; 5930b57cec5SDimitry Andric } 5940b57cec5SDimitry Andric return Changed; 5950b57cec5SDimitry Andric } 5960b57cec5SDimitry Andric 5970b57cec5SDimitry Andric /// Splits a block that contains a CR-logical operation that feeds a branch 5980b57cec5SDimitry Andric /// and whose operands are produced within the block. 5990b57cec5SDimitry Andric /// Example: 6000b57cec5SDimitry Andric /// %vr5<def> = CMPDI %vr2, 0; CRRC:%vr5 G8RC:%vr2 6010b57cec5SDimitry Andric /// %vr6<def> = COPY %vr5:sub_eq; CRBITRC:%vr6 CRRC:%vr5 6020b57cec5SDimitry Andric /// %vr7<def> = CMPDI %vr3, 0; CRRC:%vr7 G8RC:%vr3 6030b57cec5SDimitry Andric /// %vr8<def> = COPY %vr7:sub_eq; CRBITRC:%vr8 CRRC:%vr7 6040b57cec5SDimitry Andric /// %vr9<def> = CROR %vr6<kill>, %vr8<kill>; CRBITRC:%vr9,%vr6,%vr8 6050b57cec5SDimitry Andric /// BC %vr9<kill>, <BB#2>; CRBITRC:%vr9 6060b57cec5SDimitry Andric /// Becomes: 6070b57cec5SDimitry Andric /// %vr5<def> = CMPDI %vr2, 0; CRRC:%vr5 G8RC:%vr2 6080b57cec5SDimitry Andric /// %vr6<def> = COPY %vr5:sub_eq; CRBITRC:%vr6 CRRC:%vr5 6090b57cec5SDimitry Andric /// BC %vr6<kill>, <BB#2>; CRBITRC:%vr6 6100b57cec5SDimitry Andric /// 6110b57cec5SDimitry Andric /// %vr7<def> = CMPDI %vr3, 0; CRRC:%vr7 G8RC:%vr3 6120b57cec5SDimitry Andric /// %vr8<def> = COPY %vr7:sub_eq; CRBITRC:%vr8 CRRC:%vr7 6130b57cec5SDimitry Andric /// BC %vr9<kill>, <BB#2>; CRBITRC:%vr9 6140b57cec5SDimitry Andric bool PPCReduceCRLogicals::splitBlockOnBinaryCROp(CRLogicalOpInfo &CRI) { 6150b57cec5SDimitry Andric if (CRI.CopyDefs.first == CRI.CopyDefs.second) { 6160b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Unable to split as the two operands are the same\n"); 6170b57cec5SDimitry Andric NumNotSplitIdenticalOperands++; 6180b57cec5SDimitry Andric return false; 6190b57cec5SDimitry Andric } 6200b57cec5SDimitry Andric if (CRI.TrueDefs.first->isCopy() || CRI.TrueDefs.second->isCopy() || 6210b57cec5SDimitry Andric CRI.TrueDefs.first->isPHI() || CRI.TrueDefs.second->isPHI()) { 6220b57cec5SDimitry Andric LLVM_DEBUG( 6230b57cec5SDimitry Andric dbgs() << "Unable to split because one of the operands is a PHI or " 6240b57cec5SDimitry Andric "chain of copies.\n"); 6250b57cec5SDimitry Andric NumNotSplitChainCopies++; 6260b57cec5SDimitry Andric return false; 6270b57cec5SDimitry Andric } 6280b57cec5SDimitry Andric // Note: keep in sync with computeBranchTargetAndInversion(). 6290b57cec5SDimitry Andric if (CRI.MI->getOpcode() != PPC::CROR && 6300b57cec5SDimitry Andric CRI.MI->getOpcode() != PPC::CRAND && 6310b57cec5SDimitry Andric CRI.MI->getOpcode() != PPC::CRNOR && 6320b57cec5SDimitry Andric CRI.MI->getOpcode() != PPC::CRNAND && 6330b57cec5SDimitry Andric CRI.MI->getOpcode() != PPC::CRORC && 6340b57cec5SDimitry Andric CRI.MI->getOpcode() != PPC::CRANDC) { 6350b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Unable to split blocks on this opcode.\n"); 6360b57cec5SDimitry Andric NumNotSplitWrongOpcode++; 6370b57cec5SDimitry Andric return false; 6380b57cec5SDimitry Andric } 6390b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Splitting the following CR op:\n"; CRI.dump()); 6400b57cec5SDimitry Andric MachineBasicBlock::iterator Def1It = CRI.TrueDefs.first; 6410b57cec5SDimitry Andric MachineBasicBlock::iterator Def2It = CRI.TrueDefs.second; 6420b57cec5SDimitry Andric 6430b57cec5SDimitry Andric bool UsingDef1 = false; 6440b57cec5SDimitry Andric MachineInstr *SplitBefore = &*Def2It; 6450b57cec5SDimitry Andric for (auto E = CRI.MI->getParent()->end(); Def2It != E; ++Def2It) { 6460b57cec5SDimitry Andric if (Def1It == Def2It) { // Def2 comes before Def1. 6470b57cec5SDimitry Andric SplitBefore = &*Def1It; 6480b57cec5SDimitry Andric UsingDef1 = true; 6490b57cec5SDimitry Andric break; 6500b57cec5SDimitry Andric } 6510b57cec5SDimitry Andric } 6520b57cec5SDimitry Andric 6530b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "We will split the following block:\n";); 6540b57cec5SDimitry Andric LLVM_DEBUG(CRI.MI->getParent()->dump()); 6550b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Before instruction:\n"; SplitBefore->dump()); 6560b57cec5SDimitry Andric 6570b57cec5SDimitry Andric // Get the branch instruction. 6580b57cec5SDimitry Andric MachineInstr *Branch = 6590b57cec5SDimitry Andric MRI->use_nodbg_begin(CRI.MI->getOperand(0).getReg())->getParent(); 6600b57cec5SDimitry Andric 6610b57cec5SDimitry Andric // We want the new block to have no code in it other than the definition 6620b57cec5SDimitry Andric // of the input to the CR logical and the CR logical itself. So we move 6630b57cec5SDimitry Andric // those to the bottom of the block (just before the branch). Then we 6640b57cec5SDimitry Andric // will split before the CR logical. 6650b57cec5SDimitry Andric MachineBasicBlock *MBB = SplitBefore->getParent(); 6660b57cec5SDimitry Andric auto FirstTerminator = MBB->getFirstTerminator(); 6670b57cec5SDimitry Andric MachineBasicBlock::iterator FirstInstrToMove = 6680b57cec5SDimitry Andric UsingDef1 ? CRI.TrueDefs.first : CRI.TrueDefs.second; 6690b57cec5SDimitry Andric MachineBasicBlock::iterator SecondInstrToMove = 6700b57cec5SDimitry Andric UsingDef1 ? CRI.CopyDefs.first : CRI.CopyDefs.second; 6710b57cec5SDimitry Andric 6720b57cec5SDimitry Andric // The instructions that need to be moved are not guaranteed to be 6730b57cec5SDimitry Andric // contiguous. Move them individually. 6740b57cec5SDimitry Andric // FIXME: If one of the operands is a chain of (single use) copies, they 6750b57cec5SDimitry Andric // can all be moved and we can still split. 6760b57cec5SDimitry Andric MBB->splice(FirstTerminator, MBB, FirstInstrToMove); 6770b57cec5SDimitry Andric if (FirstInstrToMove != SecondInstrToMove) 6780b57cec5SDimitry Andric MBB->splice(FirstTerminator, MBB, SecondInstrToMove); 6790b57cec5SDimitry Andric MBB->splice(FirstTerminator, MBB, CRI.MI); 6800b57cec5SDimitry Andric 6810b57cec5SDimitry Andric unsigned Opc = CRI.MI->getOpcode(); 6820b57cec5SDimitry Andric bool InvertOrigBranch, InvertNewBranch, TargetIsFallThrough; 6830b57cec5SDimitry Andric computeBranchTargetAndInversion(Opc, Branch->getOpcode(), UsingDef1, 6840b57cec5SDimitry Andric InvertNewBranch, InvertOrigBranch, 6850b57cec5SDimitry Andric TargetIsFallThrough); 6860b57cec5SDimitry Andric MachineInstr *SplitCond = 6870b57cec5SDimitry Andric UsingDef1 ? CRI.CopyDefs.second : CRI.CopyDefs.first; 6880b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "We will " << (InvertNewBranch ? "invert" : "copy")); 6890b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << " the original branch and the target is the " 6900b57cec5SDimitry Andric << (TargetIsFallThrough ? "fallthrough block\n" 6910b57cec5SDimitry Andric : "orig. target block\n")); 6920b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Original branch instruction: "; Branch->dump()); 6930b57cec5SDimitry Andric BlockSplitInfo BSI { Branch, SplitBefore, SplitCond, InvertNewBranch, 6940b57cec5SDimitry Andric InvertOrigBranch, TargetIsFallThrough, MBPI, CRI.MI, 6950b57cec5SDimitry Andric UsingDef1 ? CRI.CopyDefs.first : CRI.CopyDefs.second }; 6960b57cec5SDimitry Andric bool Changed = splitMBB(BSI); 6970b57cec5SDimitry Andric // If we've split on a CR logical that is fed by a CR logical, 6980b57cec5SDimitry Andric // recompute the source CR logical as it may be usable for splitting. 6990b57cec5SDimitry Andric if (Changed) { 7000b57cec5SDimitry Andric bool Input1CRlogical = 7010b57cec5SDimitry Andric CRI.TrueDefs.first && isCRLogical(*CRI.TrueDefs.first); 7020b57cec5SDimitry Andric bool Input2CRlogical = 7030b57cec5SDimitry Andric CRI.TrueDefs.second && isCRLogical(*CRI.TrueDefs.second); 7040b57cec5SDimitry Andric if (Input1CRlogical) 7050b57cec5SDimitry Andric AllCRLogicalOps.push_back(createCRLogicalOpInfo(*CRI.TrueDefs.first)); 7060b57cec5SDimitry Andric if (Input2CRlogical) 7070b57cec5SDimitry Andric AllCRLogicalOps.push_back(createCRLogicalOpInfo(*CRI.TrueDefs.second)); 7080b57cec5SDimitry Andric } 7090b57cec5SDimitry Andric return Changed; 7100b57cec5SDimitry Andric } 7110b57cec5SDimitry Andric 7120b57cec5SDimitry Andric void PPCReduceCRLogicals::collectCRLogicals() { 7130b57cec5SDimitry Andric for (MachineBasicBlock &MBB : *MF) { 7140b57cec5SDimitry Andric for (MachineInstr &MI : MBB) { 7150b57cec5SDimitry Andric if (isCRLogical(MI)) { 7160b57cec5SDimitry Andric AllCRLogicalOps.push_back(createCRLogicalOpInfo(MI)); 7170b57cec5SDimitry Andric TotalCRLogicals++; 7180b57cec5SDimitry Andric if (AllCRLogicalOps.back().IsNullary) 7190b57cec5SDimitry Andric TotalNullaryCRLogicals++; 7200b57cec5SDimitry Andric else if (AllCRLogicalOps.back().IsBinary) 7210b57cec5SDimitry Andric TotalBinaryCRLogicals++; 7220b57cec5SDimitry Andric else 7230b57cec5SDimitry Andric TotalUnaryCRLogicals++; 7240b57cec5SDimitry Andric } 7250b57cec5SDimitry Andric } 7260b57cec5SDimitry Andric } 7270b57cec5SDimitry Andric } 7280b57cec5SDimitry Andric 7290b57cec5SDimitry Andric } // end anonymous namespace 7300b57cec5SDimitry Andric 7310b57cec5SDimitry Andric INITIALIZE_PASS_BEGIN(PPCReduceCRLogicals, DEBUG_TYPE, 7320b57cec5SDimitry Andric "PowerPC Reduce CR logical Operation", false, false) 733*0fca6ea1SDimitry Andric INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass) 7340b57cec5SDimitry Andric INITIALIZE_PASS_END(PPCReduceCRLogicals, DEBUG_TYPE, 7350b57cec5SDimitry Andric "PowerPC Reduce CR logical Operation", false, false) 7360b57cec5SDimitry Andric 7370b57cec5SDimitry Andric char PPCReduceCRLogicals::ID = 0; 7380b57cec5SDimitry Andric FunctionPass* 7390b57cec5SDimitry Andric llvm::createPPCReduceCRLogicalsPass() { return new PPCReduceCRLogicals(); } 740