| //===------------- PPCExpandISEL.cpp - Expand ISEL instruction ------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // A pass that expands the ISEL instruction into an if-then-else sequence. |
| // This pass must be run post-RA since all operands must be physical registers. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "PPC.h" |
| #include "PPCInstrInfo.h" |
| #include "PPCSubtarget.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/CodeGen/LivePhysRegs.h" |
| #include "llvm/CodeGen/MachineFunctionPass.h" |
| #include "llvm/CodeGen/MachineInstrBuilder.h" |
| #include "llvm/CodeGen/MachineRegisterInfo.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/raw_ostream.h" |
| |
| using namespace llvm; |
| |
| #define DEBUG_TYPE "ppc-expand-isel" |
| |
| STATISTIC(NumExpanded, "Number of ISEL instructions expanded"); |
| STATISTIC(NumRemoved, "Number of ISEL instructions removed"); |
| STATISTIC(NumFolded, "Number of ISEL instructions folded"); |
| |
| // If -ppc-gen-isel=false is set, we will disable generating the ISEL |
| // instruction on all PPC targets. Otherwise, if the user set option |
| // -misel or the platform supports ISEL by default, still generate the |
| // ISEL instruction, else expand it. |
| static cl::opt<bool> |
| GenerateISEL("ppc-gen-isel", |
| cl::desc("Enable generating the ISEL instruction."), |
| cl::init(true), cl::Hidden); |
| |
| namespace { |
| class PPCExpandISEL : public MachineFunctionPass { |
| DebugLoc dl; |
| MachineFunction *MF; |
| const TargetInstrInfo *TII; |
| bool IsTrueBlockRequired; |
| bool IsFalseBlockRequired; |
| MachineBasicBlock *TrueBlock; |
| MachineBasicBlock *FalseBlock; |
| MachineBasicBlock *NewSuccessor; |
| MachineBasicBlock::iterator TrueBlockI; |
| MachineBasicBlock::iterator FalseBlockI; |
| |
| typedef SmallVector<MachineInstr *, 4> BlockISELList; |
| typedef SmallDenseMap<int, BlockISELList> ISELInstructionList; |
| |
| // A map of MBB numbers to their lists of contained ISEL instructions. |
| // Please note when we traverse this list and expand ISEL, we only remove |
| // the ISEL from the MBB not from this list. |
| ISELInstructionList ISELInstructions; |
| |
| /// Initialize the object. |
| void initialize(MachineFunction &MFParam); |
| |
| void handleSpecialCases(BlockISELList &BIL, MachineBasicBlock *MBB); |
| void reorganizeBlockLayout(BlockISELList &BIL, MachineBasicBlock *MBB); |
| void populateBlocks(BlockISELList &BIL); |
| void expandMergeableISELs(BlockISELList &BIL); |
| void expandAndMergeISELs(); |
| |
| bool canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI); |
| |
| /// Is this instruction an ISEL or ISEL8? |
| static bool isISEL(const MachineInstr &MI) { |
| return (MI.getOpcode() == PPC::ISEL || MI.getOpcode() == PPC::ISEL8); |
| } |
| |
| /// Is this instruction an ISEL8? |
| static bool isISEL8(const MachineInstr &MI) { |
| return (MI.getOpcode() == PPC::ISEL8); |
| } |
| |
| /// Are the two operands using the same register? |
| bool useSameRegister(const MachineOperand &Op1, const MachineOperand &Op2) { |
| return (Op1.getReg() == Op2.getReg()); |
| } |
| |
| /// |
| /// Collect all ISEL instructions from the current function. |
| /// |
| /// Walk the current function and collect all the ISEL instructions that are |
| /// found. The instructions are placed in the ISELInstructions vector. |
| /// |
| /// \return true if any ISEL instructions were found, false otherwise |
| /// |
| bool collectISELInstructions(); |
| |
| public: |
| static char ID; |
| PPCExpandISEL() : MachineFunctionPass(ID) { |
| initializePPCExpandISELPass(*PassRegistry::getPassRegistry()); |
| } |
| |
| /// |
| /// Determine whether to generate the ISEL instruction or expand it. |
| /// |
| /// Expand ISEL instruction into if-then-else sequence when one of |
| /// the following two conditions hold: |
| /// (1) -ppc-gen-isel=false |
| /// (2) hasISEL() return false |
| /// Otherwise, still generate ISEL instruction. |
| /// The -ppc-gen-isel option is set to true by default. Which means the ISEL |
| /// instruction is still generated by default on targets that support them. |
| /// |
| /// \return true if ISEL should be expanded into if-then-else code sequence; |
| /// false if ISEL instruction should be generated, i.e. not expanded. |
| /// |
| static bool isExpandISELEnabled(const MachineFunction &MF); |
| |
| #ifndef NDEBUG |
| void DumpISELInstructions() const; |
| #endif |
| |
| bool runOnMachineFunction(MachineFunction &MF) override { |
| LLVM_DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n"); |
| initialize(MF); |
| |
| if (!collectISELInstructions()) { |
| LLVM_DEBUG(dbgs() << "No ISEL instructions in this function\n"); |
| return false; |
| } |
| |
| #ifndef NDEBUG |
| DumpISELInstructions(); |
| #endif |
| |
| expandAndMergeISELs(); |
| |
| return true; |
| } |
| }; |
| } // end anonymous namespace |
| |
| void PPCExpandISEL::initialize(MachineFunction &MFParam) { |
| MF = &MFParam; |
| TII = MF->getSubtarget().getInstrInfo(); |
| ISELInstructions.clear(); |
| } |
| |
| bool PPCExpandISEL::isExpandISELEnabled(const MachineFunction &MF) { |
| return !GenerateISEL || !MF.getSubtarget<PPCSubtarget>().hasISEL(); |
| } |
| |
| bool PPCExpandISEL::collectISELInstructions() { |
| for (MachineBasicBlock &MBB : *MF) { |
| BlockISELList thisBlockISELs; |
| for (MachineInstr &MI : MBB) |
| if (isISEL(MI)) |
| thisBlockISELs.push_back(&MI); |
| if (!thisBlockISELs.empty()) |
| ISELInstructions.insert(std::make_pair(MBB.getNumber(), thisBlockISELs)); |
| } |
| return !ISELInstructions.empty(); |
| } |
| |
| #ifndef NDEBUG |
| void PPCExpandISEL::DumpISELInstructions() const { |
| for (const auto &I : ISELInstructions) { |
| LLVM_DEBUG(dbgs() << printMBBReference(*MF->getBlockNumbered(I.first)) |
| << ":\n"); |
| for (const auto &VI : I.second) |
| LLVM_DEBUG(dbgs() << " "; VI->print(dbgs())); |
| } |
| } |
| #endif |
| |
| /// Contiguous ISELs that have the same condition can be merged. |
| bool PPCExpandISEL::canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI) { |
| // Same Condition Register? |
| if (!useSameRegister(PrevPushedMI->getOperand(3), MI->getOperand(3))) |
| return false; |
| |
| MachineBasicBlock::iterator PrevPushedMBBI = *PrevPushedMI; |
| MachineBasicBlock::iterator MBBI = *MI; |
| return (std::prev(MBBI) == PrevPushedMBBI); // Contiguous ISELs? |
| } |
| |
| void PPCExpandISEL::expandAndMergeISELs() { |
| bool ExpandISELEnabled = isExpandISELEnabled(*MF); |
| |
| for (auto &BlockList : ISELInstructions) { |
| LLVM_DEBUG( |
| dbgs() << "Expanding ISEL instructions in " |
| << printMBBReference(*MF->getBlockNumbered(BlockList.first)) |
| << "\n"); |
| BlockISELList &CurrentISELList = BlockList.second; |
| auto I = CurrentISELList.begin(); |
| auto E = CurrentISELList.end(); |
| |
| while (I != E) { |
| assert(isISEL(**I) && "Expecting an ISEL instruction"); |
| MachineOperand &Dest = (*I)->getOperand(0); |
| MachineOperand &TrueValue = (*I)->getOperand(1); |
| MachineOperand &FalseValue = (*I)->getOperand(2); |
| |
| // Special case 1, all registers used by ISEL are the same one. |
| // The non-redundant isel 0, 0, 0, N would not satisfy these conditions |
| // as it would be ISEL %R0, %ZERO, %R0, %CRN. |
| if (useSameRegister(Dest, TrueValue) && |
| useSameRegister(Dest, FalseValue)) { |
| LLVM_DEBUG(dbgs() << "Remove redundant ISEL instruction: " << **I |
| << "\n"); |
| // FIXME: if the CR field used has no other uses, we could eliminate the |
| // instruction that defines it. This would have to be done manually |
| // since this pass runs too late to run DCE after it. |
| NumRemoved++; |
| (*I)->eraseFromParent(); |
| I++; |
| } else if (useSameRegister(TrueValue, FalseValue)) { |
| // Special case 2, the two input registers used by ISEL are the same. |
| // Note: the non-foldable isel RX, 0, 0, N would not satisfy this |
| // condition as it would be ISEL %RX, %ZERO, %R0, %CRN, which makes it |
| // safe to fold ISEL to MR(OR) instead of ADDI. |
| MachineBasicBlock *MBB = (*I)->getParent(); |
| LLVM_DEBUG( |
| dbgs() << "Fold the ISEL instruction to an unconditional copy:\n"); |
| LLVM_DEBUG(dbgs() << "ISEL: " << **I << "\n"); |
| NumFolded++; |
| // Note: we're using both the TrueValue and FalseValue operands so as |
| // not to lose the kill flag if it is set on either of them. |
| BuildMI(*MBB, (*I), dl, TII->get(isISEL8(**I) ? PPC::OR8 : PPC::OR)) |
| .add(Dest) |
| .add(TrueValue) |
| .add(FalseValue); |
| (*I)->eraseFromParent(); |
| I++; |
| } else if (ExpandISELEnabled) { // Normal cases expansion enabled |
| LLVM_DEBUG(dbgs() << "Expand ISEL instructions:\n"); |
| LLVM_DEBUG(dbgs() << "ISEL: " << **I << "\n"); |
| BlockISELList SubISELList; |
| SubISELList.push_back(*I++); |
| // Collect the ISELs that can be merged together. |
| // This will eat up ISEL instructions without considering whether they |
| // may be redundant or foldable to a register copy. So we still keep |
| // the handleSpecialCases() downstream to handle them. |
| while (I != E && canMerge(SubISELList.back(), *I)) { |
| LLVM_DEBUG(dbgs() << "ISEL: " << **I << "\n"); |
| SubISELList.push_back(*I++); |
| } |
| |
| expandMergeableISELs(SubISELList); |
| } else { // Normal cases expansion disabled |
| I++; // leave the ISEL as it is |
| } |
| } // end while |
| } // end for |
| } |
| |
| void PPCExpandISEL::handleSpecialCases(BlockISELList &BIL, |
| MachineBasicBlock *MBB) { |
| IsTrueBlockRequired = false; |
| IsFalseBlockRequired = false; |
| |
| auto MI = BIL.begin(); |
| while (MI != BIL.end()) { |
| assert(isISEL(**MI) && "Expecting an ISEL instruction"); |
| LLVM_DEBUG(dbgs() << "ISEL: " << **MI << "\n"); |
| |
| MachineOperand &Dest = (*MI)->getOperand(0); |
| MachineOperand &TrueValue = (*MI)->getOperand(1); |
| MachineOperand &FalseValue = (*MI)->getOperand(2); |
| |
| // If at least one of the ISEL instructions satisfy the following |
| // condition, we need the True Block: |
| // The Dest Register and True Value Register are not the same |
| // Similarly, if at least one of the ISEL instructions satisfy the |
| // following condition, we need the False Block: |
| // The Dest Register and False Value Register are not the same. |
| bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue); |
| bool IsORIInstRequired = !useSameRegister(Dest, FalseValue); |
| |
| // Special case 1, all registers used by ISEL are the same one. |
| if (!IsADDIInstRequired && !IsORIInstRequired) { |
| LLVM_DEBUG(dbgs() << "Remove redundant ISEL instruction."); |
| // FIXME: if the CR field used has no other uses, we could eliminate the |
| // instruction that defines it. This would have to be done manually |
| // since this pass runs too late to run DCE after it. |
| NumRemoved++; |
| (*MI)->eraseFromParent(); |
| // Setting MI to the erase result keeps the iterator valid and increased. |
| MI = BIL.erase(MI); |
| continue; |
| } |
| |
| // Special case 2, the two input registers used by ISEL are the same. |
| // Note 1: We favor merging ISEL expansions over folding a single one. If |
| // the passed list has multiple merge-able ISEL's, we won't fold any. |
| // Note 2: There is no need to test for PPC::R0/PPC::X0 because PPC::ZERO/ |
| // PPC::ZERO8 will be used for the first operand if the value is meant to |
| // be zero. In this case, the useSameRegister method will return false, |
| // thereby preventing this ISEL from being folded. |
| if (useSameRegister(TrueValue, FalseValue) && (BIL.size() == 1)) { |
| LLVM_DEBUG( |
| dbgs() << "Fold the ISEL instruction to an unconditional copy."); |
| NumFolded++; |
| // Note: we're using both the TrueValue and FalseValue operands so as |
| // not to lose the kill flag if it is set on either of them. |
| BuildMI(*MBB, (*MI), dl, TII->get(isISEL8(**MI) ? PPC::OR8 : PPC::OR)) |
| .add(Dest) |
| .add(TrueValue) |
| .add(FalseValue); |
| (*MI)->eraseFromParent(); |
| // Setting MI to the erase result keeps the iterator valid and increased. |
| MI = BIL.erase(MI); |
| continue; |
| } |
| |
| IsTrueBlockRequired |= IsADDIInstRequired; |
| IsFalseBlockRequired |= IsORIInstRequired; |
| MI++; |
| } |
| } |
| |
| void PPCExpandISEL::reorganizeBlockLayout(BlockISELList &BIL, |
| MachineBasicBlock *MBB) { |
| if (BIL.empty()) |
| return; |
| |
| assert((IsTrueBlockRequired || IsFalseBlockRequired) && |
| "Should have been handled by special cases earlier!"); |
| |
| MachineBasicBlock *Successor = nullptr; |
| const BasicBlock *LLVM_BB = MBB->getBasicBlock(); |
| MachineBasicBlock::iterator MBBI = (*BIL.back()); |
| NewSuccessor = (MBBI != MBB->getLastNonDebugInstr() || !MBB->canFallThrough()) |
| // Another BB is needed to move the instructions that |
| // follow this ISEL. If the ISEL is the last instruction |
| // in a block that can't fall through, we also need a block |
| // to branch to. |
| ? MF->CreateMachineBasicBlock(LLVM_BB) |
| : nullptr; |
| |
| MachineFunction::iterator It = MBB->getIterator(); |
| ++It; // Point to the successor block of MBB. |
| |
| // If NewSuccessor is NULL then the last ISEL in this group is the last |
| // non-debug instruction in this block. Find the fall-through successor |
| // of this block to use when updating the CFG below. |
| if (!NewSuccessor) { |
| for (auto &Succ : MBB->successors()) { |
| if (MBB->isLayoutSuccessor(Succ)) { |
| Successor = Succ; |
| break; |
| } |
| } |
| } else |
| Successor = NewSuccessor; |
| |
| // The FalseBlock and TrueBlock are inserted after the MBB block but before |
| // its successor. |
| // Note this need to be done *after* the above setting the Successor code. |
| if (IsFalseBlockRequired) { |
| FalseBlock = MF->CreateMachineBasicBlock(LLVM_BB); |
| MF->insert(It, FalseBlock); |
| } |
| |
| if (IsTrueBlockRequired) { |
| TrueBlock = MF->CreateMachineBasicBlock(LLVM_BB); |
| MF->insert(It, TrueBlock); |
| } |
| |
| if (NewSuccessor) { |
| MF->insert(It, NewSuccessor); |
| |
| // Transfer the rest of this block into the new successor block. |
| NewSuccessor->splice(NewSuccessor->end(), MBB, |
| std::next(MachineBasicBlock::iterator(BIL.back())), |
| MBB->end()); |
| NewSuccessor->transferSuccessorsAndUpdatePHIs(MBB); |
| |
| // Update the liveins for NewSuccessor. |
| LivePhysRegs LPR; |
| computeAndAddLiveIns(LPR, *NewSuccessor); |
| |
| } else { |
| // Remove successor from MBB. |
| MBB->removeSuccessor(Successor); |
| } |
| |
| // Note that this needs to be done *after* transfering the successors from MBB |
| // to the NewSuccessor block, otherwise these blocks will also be transferred |
| // as successors! |
| MBB->addSuccessor(IsTrueBlockRequired ? TrueBlock : Successor); |
| MBB->addSuccessor(IsFalseBlockRequired ? FalseBlock : Successor); |
| |
| if (IsTrueBlockRequired) { |
| TrueBlockI = TrueBlock->begin(); |
| TrueBlock->addSuccessor(Successor); |
| } |
| |
| if (IsFalseBlockRequired) { |
| FalseBlockI = FalseBlock->begin(); |
| FalseBlock->addSuccessor(Successor); |
| } |
| |
| // Conditional branch to the TrueBlock or Successor |
| BuildMI(*MBB, BIL.back(), dl, TII->get(PPC::BC)) |
| .add(BIL.back()->getOperand(3)) |
| .addMBB(IsTrueBlockRequired ? TrueBlock : Successor); |
| |
| // Jump over the true block to the new successor if the condition is false. |
| BuildMI(*(IsFalseBlockRequired ? FalseBlock : MBB), |
| (IsFalseBlockRequired ? FalseBlockI : BIL.back()), dl, |
| TII->get(PPC::B)) |
| .addMBB(Successor); |
| |
| if (IsFalseBlockRequired) |
| FalseBlockI = FalseBlock->begin(); // get the position of PPC::B |
| } |
| |
| void PPCExpandISEL::populateBlocks(BlockISELList &BIL) { |
| for (auto &MI : BIL) { |
| assert(isISEL(*MI) && "Expecting an ISEL instruction"); |
| |
| MachineOperand &Dest = MI->getOperand(0); // location to store to |
| MachineOperand &TrueValue = MI->getOperand(1); // Value to store if |
| // condition is true |
| MachineOperand &FalseValue = MI->getOperand(2); // Value to store if |
| // condition is false |
| |
| LLVM_DEBUG(dbgs() << "Dest: " << Dest << "\n"); |
| LLVM_DEBUG(dbgs() << "TrueValue: " << TrueValue << "\n"); |
| LLVM_DEBUG(dbgs() << "FalseValue: " << FalseValue << "\n"); |
| LLVM_DEBUG(dbgs() << "ConditionRegister: " << MI->getOperand(3) << "\n"); |
| |
| // If the Dest Register and True Value Register are not the same one, we |
| // need the True Block. |
| bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue); |
| bool IsORIInstRequired = !useSameRegister(Dest, FalseValue); |
| |
| // Copy the result into the destination if the condition is true. |
| if (IsADDIInstRequired) |
| BuildMI(*TrueBlock, TrueBlockI, dl, |
| TII->get(isISEL8(*MI) ? PPC::ADDI8 : PPC::ADDI)) |
| .add(Dest) |
| .add(TrueValue) |
| .add(MachineOperand::CreateImm(0)); |
| |
| // Copy the result into the destination if the condition is false. |
| if (IsORIInstRequired) |
| BuildMI(*FalseBlock, FalseBlockI, dl, |
| TII->get(isISEL8(*MI) ? PPC::ORI8 : PPC::ORI)) |
| .add(Dest) |
| .add(FalseValue) |
| .add(MachineOperand::CreateImm(0)); |
| |
| MI->eraseFromParent(); // Remove the ISEL instruction. |
| |
| NumExpanded++; |
| } |
| |
| if (IsTrueBlockRequired) { |
| // Update the liveins for TrueBlock. |
| LivePhysRegs LPR; |
| computeAndAddLiveIns(LPR, *TrueBlock); |
| } |
| |
| if (IsFalseBlockRequired) { |
| // Update the liveins for FalseBlock. |
| LivePhysRegs LPR; |
| computeAndAddLiveIns(LPR, *FalseBlock); |
| } |
| } |
| |
| void PPCExpandISEL::expandMergeableISELs(BlockISELList &BIL) { |
| // At this stage all the ISELs of BIL are in the same MBB. |
| MachineBasicBlock *MBB = BIL.back()->getParent(); |
| |
| handleSpecialCases(BIL, MBB); |
| reorganizeBlockLayout(BIL, MBB); |
| populateBlocks(BIL); |
| } |
| |
| INITIALIZE_PASS(PPCExpandISEL, DEBUG_TYPE, "PowerPC Expand ISEL Generation", |
| false, false) |
| char PPCExpandISEL::ID = 0; |
| |
| FunctionPass *llvm::createPPCExpandISELPass() { return new PPCExpandISEL(); } |