| //===-- PPCCTRLoops.cpp - Identify and generate CTR loops -----------------===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This pass identifies loops where we can generate the PPC branch instructions |
| // that decrement and test the count register (CTR) (bdnz and friends). |
| // This pass is based on the HexagonHardwareLoops pass. |
| // |
| // The pattern that defines the induction variable can changed depending on |
| // prior optimizations. For example, the IndVarSimplify phase run by 'opt' |
| // normalizes induction variables, and the Loop Strength Reduction pass |
| // run by 'llc' may also make changes to the induction variable. |
| // The pattern detected by this phase is due to running Strength Reduction. |
| // |
| // Criteria for CTR loops: |
| // - Countable loops (w/ ind. var for a trip count) |
| // - Assumes loops are normalized by IndVarSimplify |
| // - Try inner-most loops first |
| // - No nested CTR loops. |
| // - No function calls in loops. |
| // |
| // Note: As with unconverted loops, PPCBranchSelector must be run after this |
| // pass in order to convert long-displacement jumps into jump pairs. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #define DEBUG_TYPE "ctrloops" |
| #include "PPC.h" |
| #include "MCTargetDesc/PPCPredicates.h" |
| #include "PPCTargetMachine.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/CodeGen/MachineDominators.h" |
| #include "llvm/CodeGen/MachineFunction.h" |
| #include "llvm/CodeGen/MachineFunctionPass.h" |
| #include "llvm/CodeGen/MachineInstrBuilder.h" |
| #include "llvm/CodeGen/MachineLoopInfo.h" |
| #include "llvm/CodeGen/MachineRegisterInfo.h" |
| #include "llvm/CodeGen/Passes.h" |
| #include "llvm/CodeGen/RegisterScavenging.h" |
| #include "llvm/IR/Constants.h" |
| #include "llvm/PassSupport.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include "llvm/Target/TargetInstrInfo.h" |
| #include <algorithm> |
| |
| using namespace llvm; |
| |
| STATISTIC(NumCTRLoops, "Number of loops converted to CTR loops"); |
| |
| namespace llvm { |
| void initializePPCCTRLoopsPass(PassRegistry&); |
| } |
| |
| namespace { |
| class CountValue; |
| struct PPCCTRLoops : public MachineFunctionPass { |
| MachineLoopInfo *MLI; |
| MachineRegisterInfo *MRI; |
| const TargetInstrInfo *TII; |
| |
| public: |
| static char ID; // Pass identification, replacement for typeid |
| |
| PPCCTRLoops() : MachineFunctionPass(ID) { |
| initializePPCCTRLoopsPass(*PassRegistry::getPassRegistry()); |
| } |
| |
| virtual bool runOnMachineFunction(MachineFunction &MF); |
| |
| const char *getPassName() const { return "PPC CTR Loops"; } |
| |
| virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| AU.setPreservesCFG(); |
| AU.addRequired<MachineDominatorTree>(); |
| AU.addPreserved<MachineDominatorTree>(); |
| AU.addRequired<MachineLoopInfo>(); |
| AU.addPreserved<MachineLoopInfo>(); |
| MachineFunctionPass::getAnalysisUsage(AU); |
| } |
| |
| private: |
| /// getCanonicalInductionVariable - Check to see if the loop has a canonical |
| /// induction variable. |
| /// Should be defined in MachineLoop. Based upon version in class Loop. |
| void getCanonicalInductionVariable(MachineLoop *L, |
| SmallVector<MachineInstr *, 4> &IVars, |
| SmallVector<MachineInstr *, 4> &IOps) const; |
| |
| /// getTripCount - Return a loop-invariant LLVM register indicating the |
| /// number of times the loop will be executed. If the trip-count cannot |
| /// be determined, this return null. |
| CountValue *getTripCount(MachineLoop *L, |
| SmallVector<MachineInstr *, 2> &OldInsts) const; |
| |
| /// isInductionOperation - Return true if the instruction matches the |
| /// pattern for an opertion that defines an induction variable. |
| bool isInductionOperation(const MachineInstr *MI, unsigned IVReg) const; |
| |
| /// isInvalidOperation - Return true if the instruction is not valid within |
| /// a CTR loop. |
| bool isInvalidLoopOperation(const MachineInstr *MI) const; |
| |
| /// containsInavlidInstruction - Return true if the loop contains an |
| /// instruction that inhibits using the CTR loop. |
| bool containsInvalidInstruction(MachineLoop *L) const; |
| |
| /// converToCTRLoop - Given a loop, check if we can convert it to a |
| /// CTR loop. If so, then perform the conversion and return true. |
| bool convertToCTRLoop(MachineLoop *L); |
| |
| /// isDead - Return true if the instruction is now dead. |
| bool isDead(const MachineInstr *MI, |
| SmallVector<MachineInstr *, 1> &DeadPhis) const; |
| |
| /// removeIfDead - Remove the instruction if it is now dead. |
| void removeIfDead(MachineInstr *MI); |
| }; |
| |
| char PPCCTRLoops::ID = 0; |
| |
| |
| // CountValue class - Abstraction for a trip count of a loop. A |
| // smaller vesrsion of the MachineOperand class without the concerns |
| // of changing the operand representation. |
| class CountValue { |
| public: |
| enum CountValueType { |
| CV_Register, |
| CV_Immediate |
| }; |
| private: |
| CountValueType Kind; |
| union Values { |
| unsigned RegNum; |
| int64_t ImmVal; |
| Values(unsigned r) : RegNum(r) {} |
| Values(int64_t i) : ImmVal(i) {} |
| } Contents; |
| bool isNegative; |
| |
| public: |
| CountValue(unsigned r, bool neg) : Kind(CV_Register), Contents(r), |
| isNegative(neg) {} |
| explicit CountValue(int64_t i) : Kind(CV_Immediate), Contents(i), |
| isNegative(i < 0) {} |
| CountValueType getType() const { return Kind; } |
| bool isReg() const { return Kind == CV_Register; } |
| bool isImm() const { return Kind == CV_Immediate; } |
| bool isNeg() const { return isNegative; } |
| |
| unsigned getReg() const { |
| assert(isReg() && "Wrong CountValue accessor"); |
| return Contents.RegNum; |
| } |
| void setReg(unsigned Val) { |
| Contents.RegNum = Val; |
| } |
| int64_t getImm() const { |
| assert(isImm() && "Wrong CountValue accessor"); |
| if (isNegative) { |
| return -Contents.ImmVal; |
| } |
| return Contents.ImmVal; |
| } |
| void setImm(int64_t Val) { |
| Contents.ImmVal = Val; |
| } |
| |
| void print(raw_ostream &OS, const TargetMachine *TM = 0) const { |
| if (isReg()) { OS << PrintReg(getReg()); } |
| if (isImm()) { OS << getImm(); } |
| } |
| }; |
| } // end anonymous namespace |
| |
| INITIALIZE_PASS_BEGIN(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops", |
| false, false) |
| INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
| INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) |
| INITIALIZE_PASS_END(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops", |
| false, false) |
| |
| /// isCompareEquals - Returns true if the instruction is a compare equals |
| /// instruction with an immediate operand. |
| static bool isCompareEqualsImm(const MachineInstr *MI, bool &SignedCmp, |
| bool &Int64Cmp) { |
| if (MI->getOpcode() == PPC::CMPWI) { |
| SignedCmp = true; |
| Int64Cmp = false; |
| return true; |
| } else if (MI->getOpcode() == PPC::CMPDI) { |
| SignedCmp = true; |
| Int64Cmp = true; |
| return true; |
| } else if (MI->getOpcode() == PPC::CMPLWI) { |
| SignedCmp = false; |
| Int64Cmp = false; |
| return true; |
| } else if (MI->getOpcode() == PPC::CMPLDI) { |
| SignedCmp = false; |
| Int64Cmp = true; |
| return true; |
| } |
| |
| return false; |
| } |
| |
| |
| /// createPPCCTRLoops - Factory for creating |
| /// the CTR loop phase. |
| FunctionPass *llvm::createPPCCTRLoops() { |
| return new PPCCTRLoops(); |
| } |
| |
| |
| bool PPCCTRLoops::runOnMachineFunction(MachineFunction &MF) { |
| DEBUG(dbgs() << "********* PPC CTR Loops *********\n"); |
| |
| bool Changed = false; |
| |
| // get the loop information |
| MLI = &getAnalysis<MachineLoopInfo>(); |
| // get the register information |
| MRI = &MF.getRegInfo(); |
| // the target specific instructio info. |
| TII = MF.getTarget().getInstrInfo(); |
| |
| for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); |
| I != E; ++I) { |
| MachineLoop *L = *I; |
| if (!L->getParentLoop()) { |
| Changed |= convertToCTRLoop(L); |
| } |
| } |
| |
| return Changed; |
| } |
| |
| /// getCanonicalInductionVariable - Check to see if the loop has a canonical |
| /// induction variable. We check for a simple recurrence pattern - an |
| /// integer recurrence that decrements by one each time through the loop and |
| /// ends at zero. If so, return the phi node that corresponds to it. |
| /// |
| /// Based upon the similar code in LoopInfo except this code is specific to |
| /// the machine. |
| /// This method assumes that the IndVarSimplify pass has been run by 'opt'. |
| /// |
| void |
| PPCCTRLoops::getCanonicalInductionVariable(MachineLoop *L, |
| SmallVector<MachineInstr *, 4> &IVars, |
| SmallVector<MachineInstr *, 4> &IOps) const { |
| MachineBasicBlock *TopMBB = L->getTopBlock(); |
| MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(); |
| assert(PI != TopMBB->pred_end() && |
| "Loop must have more than one incoming edge!"); |
| MachineBasicBlock *Backedge = *PI++; |
| if (PI == TopMBB->pred_end()) return; // dead loop |
| MachineBasicBlock *Incoming = *PI++; |
| if (PI != TopMBB->pred_end()) return; // multiple backedges? |
| |
| // make sure there is one incoming and one backedge and determine which |
| // is which. |
| if (L->contains(Incoming)) { |
| if (L->contains(Backedge)) |
| return; |
| std::swap(Incoming, Backedge); |
| } else if (!L->contains(Backedge)) |
| return; |
| |
| // Loop over all of the PHI nodes, looking for a canonical induction variable: |
| // - The PHI node is "reg1 = PHI reg2, BB1, reg3, BB2". |
| // - The recurrence comes from the backedge. |
| // - the definition is an induction operatio.n |
| for (MachineBasicBlock::iterator I = TopMBB->begin(), E = TopMBB->end(); |
| I != E && I->isPHI(); ++I) { |
| MachineInstr *MPhi = &*I; |
| unsigned DefReg = MPhi->getOperand(0).getReg(); |
| for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) { |
| // Check each operand for the value from the backedge. |
| MachineBasicBlock *MBB = MPhi->getOperand(i+1).getMBB(); |
| if (L->contains(MBB)) { // operands comes from the backedge |
| // Check if the definition is an induction operation. |
| MachineInstr *DI = MRI->getVRegDef(MPhi->getOperand(i).getReg()); |
| if (isInductionOperation(DI, DefReg)) { |
| IOps.push_back(DI); |
| IVars.push_back(MPhi); |
| } |
| } |
| } |
| } |
| return; |
| } |
| |
| /// getTripCount - Return a loop-invariant LLVM value indicating the |
| /// number of times the loop will be executed. The trip count can |
| /// be either a register or a constant value. If the trip-count |
| /// cannot be determined, this returns null. |
| /// |
| /// We find the trip count from the phi instruction that defines the |
| /// induction variable. We follow the links to the CMP instruction |
| /// to get the trip count. |
| /// |
| /// Based upon getTripCount in LoopInfo. |
| /// |
| CountValue *PPCCTRLoops::getTripCount(MachineLoop *L, |
| SmallVector<MachineInstr *, 2> &OldInsts) const { |
| MachineBasicBlock *LastMBB = L->getExitingBlock(); |
| // Don't generate a CTR loop if the loop has more than one exit. |
| if (LastMBB == 0) |
| return 0; |
| |
| MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator(); |
| if (LastI->getOpcode() != PPC::BCC) |
| return 0; |
| |
| // We need to make sure that this compare is defining the condition |
| // register actually used by the terminating branch. |
| |
| unsigned PredReg = LastI->getOperand(1).getReg(); |
| DEBUG(dbgs() << "Examining loop with first terminator: " << *LastI); |
| |
| unsigned PredCond = LastI->getOperand(0).getImm(); |
| if (PredCond != PPC::PRED_EQ && PredCond != PPC::PRED_NE) |
| return 0; |
| |
| // Check that the loop has a induction variable. |
| SmallVector<MachineInstr *, 4> IVars, IOps; |
| getCanonicalInductionVariable(L, IVars, IOps); |
| for (unsigned i = 0; i < IVars.size(); ++i) { |
| MachineInstr *IOp = IOps[i]; |
| MachineInstr *IV_Inst = IVars[i]; |
| |
| // Canonical loops will end with a 'cmpwi/cmpdi cr, IV, Imm', |
| // if Imm is 0, get the count from the PHI opnd |
| // if Imm is -M, than M is the count |
| // Otherwise, Imm is the count |
| MachineOperand *IV_Opnd; |
| const MachineOperand *InitialValue; |
| if (!L->contains(IV_Inst->getOperand(2).getMBB())) { |
| InitialValue = &IV_Inst->getOperand(1); |
| IV_Opnd = &IV_Inst->getOperand(3); |
| } else { |
| InitialValue = &IV_Inst->getOperand(3); |
| IV_Opnd = &IV_Inst->getOperand(1); |
| } |
| |
| DEBUG(dbgs() << "Considering:\n"); |
| DEBUG(dbgs() << " induction operation: " << *IOp); |
| DEBUG(dbgs() << " induction variable: " << *IV_Inst); |
| DEBUG(dbgs() << " initial value: " << *InitialValue << "\n"); |
| |
| // Look for the cmp instruction to determine if we |
| // can get a useful trip count. The trip count can |
| // be either a register or an immediate. The location |
| // of the value depends upon the type (reg or imm). |
| for (MachineRegisterInfo::reg_iterator |
| RI = MRI->reg_begin(IV_Opnd->getReg()), RE = MRI->reg_end(); |
| RI != RE; ++RI) { |
| IV_Opnd = &RI.getOperand(); |
| bool SignedCmp, Int64Cmp; |
| MachineInstr *MI = IV_Opnd->getParent(); |
| if (L->contains(MI) && isCompareEqualsImm(MI, SignedCmp, Int64Cmp) && |
| MI->getOperand(0).getReg() == PredReg) { |
| |
| OldInsts.push_back(MI); |
| OldInsts.push_back(IOp); |
| |
| DEBUG(dbgs() << " compare: " << *MI); |
| |
| const MachineOperand &MO = MI->getOperand(2); |
| assert(MO.isImm() && "IV Cmp Operand should be an immediate"); |
| |
| int64_t ImmVal; |
| if (SignedCmp) |
| ImmVal = (short) MO.getImm(); |
| else |
| ImmVal = MO.getImm(); |
| |
| const MachineInstr *IV_DefInstr = MRI->getVRegDef(IV_Opnd->getReg()); |
| assert(L->contains(IV_DefInstr->getParent()) && |
| "IV definition should occurs in loop"); |
| int64_t iv_value = (short) IV_DefInstr->getOperand(2).getImm(); |
| |
| assert(InitialValue->isReg() && "Expecting register for init value"); |
| unsigned InitialValueReg = InitialValue->getReg(); |
| |
| MachineInstr *DefInstr = MRI->getVRegDef(InitialValueReg); |
| |
| // Here we need to look for an immediate load (an li or lis/ori pair). |
| if (DefInstr && (DefInstr->getOpcode() == PPC::ORI8 || |
| DefInstr->getOpcode() == PPC::ORI)) { |
| int64_t start = DefInstr->getOperand(2).getImm(); |
| MachineInstr *DefInstr2 = |
| MRI->getVRegDef(DefInstr->getOperand(1).getReg()); |
| if (DefInstr2 && (DefInstr2->getOpcode() == PPC::LIS8 || |
| DefInstr2->getOpcode() == PPC::LIS)) { |
| DEBUG(dbgs() << " initial constant: " << *DefInstr); |
| DEBUG(dbgs() << " initial constant: " << *DefInstr2); |
| |
| start |= int64_t(short(DefInstr2->getOperand(1).getImm())) << 16; |
| |
| int64_t count = ImmVal - start; |
| if ((count % iv_value) != 0) { |
| return 0; |
| } |
| |
| OldInsts.push_back(DefInstr); |
| OldInsts.push_back(DefInstr2); |
| |
| // count/iv_value, the trip count, should be positive here. If it |
| // is negative, that indicates that the counter will wrap. |
| if (Int64Cmp) |
| return new CountValue(count/iv_value); |
| else |
| return new CountValue(uint32_t(count/iv_value)); |
| } |
| } else if (DefInstr && (DefInstr->getOpcode() == PPC::LI8 || |
| DefInstr->getOpcode() == PPC::LI)) { |
| DEBUG(dbgs() << " initial constant: " << *DefInstr); |
| |
| int64_t count = ImmVal - |
| int64_t(short(DefInstr->getOperand(1).getImm())); |
| if ((count % iv_value) != 0) { |
| return 0; |
| } |
| |
| OldInsts.push_back(DefInstr); |
| |
| if (Int64Cmp) |
| return new CountValue(count/iv_value); |
| else |
| return new CountValue(uint32_t(count/iv_value)); |
| } else if (iv_value == 1 || iv_value == -1) { |
| // We can't determine a constant starting value. |
| if (ImmVal == 0) { |
| return new CountValue(InitialValueReg, iv_value > 0); |
| } |
| // FIXME: handle non-zero end value. |
| } |
| // FIXME: handle non-unit increments (we might not want to introduce |
| // division but we can handle some 2^n cases with shifts). |
| |
| } |
| } |
| } |
| return 0; |
| } |
| |
| /// isInductionOperation - return true if the operation is matches the |
| /// pattern that defines an induction variable: |
| /// addi iv, c |
| /// |
| bool |
| PPCCTRLoops::isInductionOperation(const MachineInstr *MI, |
| unsigned IVReg) const { |
| return ((MI->getOpcode() == PPC::ADDI || MI->getOpcode() == PPC::ADDI8) && |
| MI->getOperand(1).isReg() && // could be a frame index instead |
| MI->getOperand(1).getReg() == IVReg); |
| } |
| |
| /// isInvalidOperation - Return true if the operation is invalid within |
| /// CTR loop. |
| bool |
| PPCCTRLoops::isInvalidLoopOperation(const MachineInstr *MI) const { |
| |
| // call is not allowed because the callee may use a CTR loop |
| if (MI->getDesc().isCall()) { |
| return true; |
| } |
| // check if the instruction defines a CTR loop register |
| // (this will also catch nested CTR loops) |
| for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| const MachineOperand &MO = MI->getOperand(i); |
| if (MO.isReg() && MO.isDef() && |
| (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8)) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /// containsInvalidInstruction - Return true if the loop contains |
| /// an instruction that inhibits the use of the CTR loop function. |
| /// |
| bool PPCCTRLoops::containsInvalidInstruction(MachineLoop *L) const { |
| const std::vector<MachineBasicBlock*> Blocks = L->getBlocks(); |
| for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { |
| MachineBasicBlock *MBB = Blocks[i]; |
| for (MachineBasicBlock::iterator |
| MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) { |
| const MachineInstr *MI = &*MII; |
| if (isInvalidLoopOperation(MI)) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| /// isDead returns true if the instruction is dead |
| /// (this was essentially copied from DeadMachineInstructionElim::isDead, but |
| /// with special cases for inline asm, physical registers and instructions with |
| /// side effects removed) |
| bool PPCCTRLoops::isDead(const MachineInstr *MI, |
| SmallVector<MachineInstr *, 1> &DeadPhis) const { |
| // Examine each operand. |
| for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| const MachineOperand &MO = MI->getOperand(i); |
| if (MO.isReg() && MO.isDef()) { |
| unsigned Reg = MO.getReg(); |
| if (!MRI->use_nodbg_empty(Reg)) { |
| // This instruction has users, but if the only user is the phi node for |
| // the parent block, and the only use of that phi node is this |
| // instruction, then this instruction is dead: both it (and the phi |
| // node) can be removed. |
| MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg); |
| if (llvm::next(I) == MRI->use_end() && |
| I.getOperand().getParent()->isPHI()) { |
| MachineInstr *OnePhi = I.getOperand().getParent(); |
| |
| for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) { |
| const MachineOperand &OPO = OnePhi->getOperand(j); |
| if (OPO.isReg() && OPO.isDef()) { |
| unsigned OPReg = OPO.getReg(); |
| |
| MachineRegisterInfo::use_iterator nextJ; |
| for (MachineRegisterInfo::use_iterator J = MRI->use_begin(OPReg), |
| E = MRI->use_end(); J!=E; J=nextJ) { |
| nextJ = llvm::next(J); |
| MachineOperand& Use = J.getOperand(); |
| MachineInstr *UseMI = Use.getParent(); |
| |
| if (MI != UseMI) { |
| // The phi node has a user that is not MI, bail... |
| return false; |
| } |
| } |
| } |
| } |
| |
| DeadPhis.push_back(OnePhi); |
| } else { |
| // This def has a non-debug use. Don't delete the instruction! |
| return false; |
| } |
| } |
| } |
| } |
| |
| // If there are no defs with uses, the instruction is dead. |
| return true; |
| } |
| |
| void PPCCTRLoops::removeIfDead(MachineInstr *MI) { |
| // This procedure was essentially copied from DeadMachineInstructionElim |
| |
| SmallVector<MachineInstr *, 1> DeadPhis; |
| if (isDead(MI, DeadPhis)) { |
| DEBUG(dbgs() << "CTR looping will remove: " << *MI); |
| |
| // It is possible that some DBG_VALUE instructions refer to this |
| // instruction. Examine each def operand for such references; |
| // if found, mark the DBG_VALUE as undef (but don't delete it). |
| for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| const MachineOperand &MO = MI->getOperand(i); |
| if (!MO.isReg() || !MO.isDef()) |
| continue; |
| unsigned Reg = MO.getReg(); |
| MachineRegisterInfo::use_iterator nextI; |
| for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg), |
| E = MRI->use_end(); I!=E; I=nextI) { |
| nextI = llvm::next(I); // I is invalidated by the setReg |
| MachineOperand& Use = I.getOperand(); |
| MachineInstr *UseMI = Use.getParent(); |
| if (UseMI==MI) |
| continue; |
| if (Use.isDebug()) // this might also be a instr -> phi -> instr case |
| // which can also be removed. |
| UseMI->getOperand(0).setReg(0U); |
| } |
| } |
| |
| MI->eraseFromParent(); |
| for (unsigned i = 0; i < DeadPhis.size(); ++i) { |
| DeadPhis[i]->eraseFromParent(); |
| } |
| } |
| } |
| |
| /// converToCTRLoop - check if the loop is a candidate for |
| /// converting to a CTR loop. If so, then perform the |
| /// transformation. |
| /// |
| /// This function works on innermost loops first. A loop can |
| /// be converted if it is a counting loop; either a register |
| /// value or an immediate. |
| /// |
| /// The code makes several assumptions about the representation |
| /// of the loop in llvm. |
| bool PPCCTRLoops::convertToCTRLoop(MachineLoop *L) { |
| bool Changed = false; |
| // Process nested loops first. |
| for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) { |
| Changed |= convertToCTRLoop(*I); |
| } |
| // If a nested loop has been converted, then we can't convert this loop. |
| if (Changed) { |
| return Changed; |
| } |
| |
| SmallVector<MachineInstr *, 2> OldInsts; |
| // Are we able to determine the trip count for the loop? |
| CountValue *TripCount = getTripCount(L, OldInsts); |
| if (TripCount == 0) { |
| DEBUG(dbgs() << "failed to get trip count!\n"); |
| return false; |
| } |
| |
| if (TripCount->isImm()) { |
| DEBUG(dbgs() << "constant trip count: " << TripCount->getImm() << "\n"); |
| |
| // FIXME: We currently can't form 64-bit constants |
| // (including 32-bit unsigned constants) |
| if (!isInt<32>(TripCount->getImm())) |
| return false; |
| } |
| |
| // Does the loop contain any invalid instructions? |
| if (containsInvalidInstruction(L)) { |
| return false; |
| } |
| MachineBasicBlock *Preheader = L->getLoopPreheader(); |
| // No preheader means there's not place for the loop instr. |
| if (Preheader == 0) { |
| return false; |
| } |
| MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator(); |
| |
| DebugLoc dl; |
| if (InsertPos != Preheader->end()) |
| dl = InsertPos->getDebugLoc(); |
| |
| MachineBasicBlock *LastMBB = L->getExitingBlock(); |
| // Don't generate CTR loop if the loop has more than one exit. |
| if (LastMBB == 0) { |
| return false; |
| } |
| MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator(); |
| |
| // Determine the loop start. |
| MachineBasicBlock *LoopStart = L->getTopBlock(); |
| if (L->getLoopLatch() != LastMBB) { |
| // When the exit and latch are not the same, use the latch block as the |
| // start. |
| // The loop start address is used only after the 1st iteration, and the loop |
| // latch may contains instrs. that need to be executed after the 1st iter. |
| LoopStart = L->getLoopLatch(); |
| // Make sure the latch is a successor of the exit, otherwise it won't work. |
| if (!LastMBB->isSuccessor(LoopStart)) { |
| return false; |
| } |
| } |
| |
| // Convert the loop to a CTR loop |
| DEBUG(dbgs() << "Change to CTR loop at "; L->dump()); |
| |
| MachineFunction *MF = LastMBB->getParent(); |
| const PPCSubtarget &Subtarget = MF->getTarget().getSubtarget<PPCSubtarget>(); |
| bool isPPC64 = Subtarget.isPPC64(); |
| |
| const TargetRegisterClass *GPRC = &PPC::GPRCRegClass; |
| const TargetRegisterClass *G8RC = &PPC::G8RCRegClass; |
| const TargetRegisterClass *RC = isPPC64 ? G8RC : GPRC; |
| |
| unsigned CountReg; |
| if (TripCount->isReg()) { |
| // Create a copy of the loop count register. |
| const TargetRegisterClass *SrcRC = |
| MF->getRegInfo().getRegClass(TripCount->getReg()); |
| CountReg = MF->getRegInfo().createVirtualRegister(RC); |
| unsigned CopyOp = (isPPC64 && GPRC->hasSubClassEq(SrcRC)) ? |
| (unsigned) PPC::EXTSW_32_64 : |
| (unsigned) TargetOpcode::COPY; |
| BuildMI(*Preheader, InsertPos, dl, |
| TII->get(CopyOp), CountReg).addReg(TripCount->getReg()); |
| if (TripCount->isNeg()) { |
| unsigned CountReg1 = CountReg; |
| CountReg = MF->getRegInfo().createVirtualRegister(RC); |
| BuildMI(*Preheader, InsertPos, dl, |
| TII->get(isPPC64 ? PPC::NEG8 : PPC::NEG), |
| CountReg).addReg(CountReg1); |
| } |
| } else { |
| assert(TripCount->isImm() && "Expecting immedate vaule for trip count"); |
| // Put the trip count in a register for transfer into the count register. |
| |
| int64_t CountImm = TripCount->getImm(); |
| if (TripCount->isNeg()) |
| CountImm = -CountImm; |
| |
| CountReg = MF->getRegInfo().createVirtualRegister(RC); |
| if (abs64(CountImm) > 0x7FFF) { |
| BuildMI(*Preheader, InsertPos, dl, |
| TII->get(isPPC64 ? PPC::LIS8 : PPC::LIS), |
| CountReg).addImm((CountImm >> 16) & 0xFFFF); |
| unsigned CountReg1 = CountReg; |
| CountReg = MF->getRegInfo().createVirtualRegister(RC); |
| BuildMI(*Preheader, InsertPos, dl, |
| TII->get(isPPC64 ? PPC::ORI8 : PPC::ORI), |
| CountReg).addReg(CountReg1).addImm(CountImm & 0xFFFF); |
| } else { |
| BuildMI(*Preheader, InsertPos, dl, |
| TII->get(isPPC64 ? PPC::LI8 : PPC::LI), |
| CountReg).addImm(CountImm); |
| } |
| } |
| |
| // Add the mtctr instruction to the beginning of the loop. |
| BuildMI(*Preheader, InsertPos, dl, |
| TII->get(isPPC64 ? PPC::MTCTR8 : PPC::MTCTR)).addReg(CountReg, |
| TripCount->isImm() ? RegState::Kill : 0); |
| |
| // Make sure the loop start always has a reference in the CFG. We need to |
| // create a BlockAddress operand to get this mechanism to work both the |
| // MachineBasicBlock and BasicBlock objects need the flag set. |
| LoopStart->setHasAddressTaken(); |
| // This line is needed to set the hasAddressTaken flag on the BasicBlock |
| // object |
| BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock())); |
| |
| // Replace the loop branch with a bdnz instruction. |
| dl = LastI->getDebugLoc(); |
| const std::vector<MachineBasicBlock*> Blocks = L->getBlocks(); |
| for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { |
| MachineBasicBlock *MBB = Blocks[i]; |
| if (MBB != Preheader) |
| MBB->addLiveIn(isPPC64 ? PPC::CTR8 : PPC::CTR); |
| } |
| |
| // The loop ends with either: |
| // - a conditional branch followed by an unconditional branch, or |
| // - a conditional branch to the loop start. |
| assert(LastI->getOpcode() == PPC::BCC && |
| "loop end must start with a BCC instruction"); |
| // Either the BCC branches to the beginning of the loop, or it |
| // branches out of the loop and there is an unconditional branch |
| // to the start of the loop. |
| MachineBasicBlock *BranchTarget = LastI->getOperand(2).getMBB(); |
| BuildMI(*LastMBB, LastI, dl, |
| TII->get((BranchTarget == LoopStart) ? |
| (isPPC64 ? PPC::BDNZ8 : PPC::BDNZ) : |
| (isPPC64 ? PPC::BDZ8 : PPC::BDZ))).addMBB(BranchTarget); |
| |
| // Conditional branch; just delete it. |
| DEBUG(dbgs() << "Removing old branch: " << *LastI); |
| LastMBB->erase(LastI); |
| |
| delete TripCount; |
| |
| // The induction operation (add) and the comparison (cmpwi) may now be |
| // unneeded. If these are unneeded, then remove them. |
| for (unsigned i = 0; i < OldInsts.size(); ++i) |
| removeIfDead(OldInsts[i]); |
| |
| ++NumCTRLoops; |
| return true; |
| } |
| |
