diff options
Diffstat (limited to 'lib/Target/Mips/MicroMipsSizeReduction.cpp')
| -rw-r--r-- | lib/Target/Mips/MicroMipsSizeReduction.cpp | 297 |
1 files changed, 241 insertions, 56 deletions
diff --git a/lib/Target/Mips/MicroMipsSizeReduction.cpp b/lib/Target/Mips/MicroMipsSizeReduction.cpp index f2e014084e46..568cdfb5b110 100644 --- a/lib/Target/Mips/MicroMipsSizeReduction.cpp +++ b/lib/Target/Mips/MicroMipsSizeReduction.cpp @@ -10,7 +10,6 @@ /// This pass is used to reduce the size of instructions where applicable. /// /// TODO: Implement microMIPS64 support. -/// TODO: Implement support for reducing into lwp/swp instruction. //===----------------------------------------------------------------------===// #include "Mips.h" #include "MipsInstrInfo.h" @@ -22,8 +21,10 @@ using namespace llvm; #define DEBUG_TYPE "micromips-reduce-size" +#define MICROMIPS_SIZE_REDUCE_NAME "MicroMips instruction size reduce pass" -STATISTIC(NumReduced, "Number of 32-bit instructions reduced to 16-bit ones"); +STATISTIC(NumReduced, "Number of instructions reduced (32-bit to 16-bit ones, " + "or two instructions into one"); namespace { @@ -35,12 +36,15 @@ enum OperandTransfer { OT_Operands02, ///< Transfer operands 0 and 2 OT_Operand2, ///< Transfer just operand 2 OT_OperandsXOR, ///< Transfer operands for XOR16 + OT_OperandsLwp, ///< Transfer operands for LWP + OT_OperandsSwp, ///< Transfer operands for SWP }; /// Reduction type // TODO: Will be extended when additional optimizations are added enum ReduceType { - RT_OneInstr ///< Reduce one instruction into a smaller instruction + RT_TwoInstr, ///< Reduce two instructions into one instruction + RT_OneInstr ///< Reduce one instruction into a smaller instruction }; // Information about immediate field restrictions @@ -76,21 +80,22 @@ struct OpCodes { unsigned NarrowOpc; ///< Narrow opcode }; +typedef struct ReduceEntryFunArgs ReduceEntryFunArgs; + /// ReduceTable - A static table with information on mapping from wide /// opcodes to narrow struct ReduceEntry { enum ReduceType eRType; ///< Reduction type bool (*ReduceFunction)( - MachineInstr *MI, - const ReduceEntry &Entry); ///< Pointer to reduce function - struct OpCodes Ops; ///< All relevant OpCodes - struct OpInfo OpInf; ///< Characteristics of operands - struct ImmField Imm; ///< Characteristics of immediate field + ReduceEntryFunArgs *Arguments); ///< Pointer to reduce function + struct OpCodes Ops; ///< All relevant OpCodes + struct OpInfo OpInf; ///< Characteristics of operands + struct ImmField Imm; ///< Characteristics of immediate field ReduceEntry(enum ReduceType RType, struct OpCodes Op, - bool (*F)(MachineInstr *MI, const ReduceEntry &Entry), - struct OpInfo OpInf, struct ImmField Imm) + bool (*F)(ReduceEntryFunArgs *Arguments), struct OpInfo OpInf, + struct ImmField Imm) : eRType(RType), ReduceFunction(F), Ops(Op), OpInf(OpInf), Imm(Imm) {} unsigned NarrowOpc() const { return Ops.NarrowOpc; } @@ -113,6 +118,20 @@ struct ReduceEntry { } }; +// Function arguments for ReduceFunction +struct ReduceEntryFunArgs { + MachineInstr *MI; // Instruction + const ReduceEntry &Entry; // Entry field + MachineBasicBlock::instr_iterator + &NextMII; // Iterator to next instruction in block + + ReduceEntryFunArgs(MachineInstr *argMI, const ReduceEntry &argEntry, + MachineBasicBlock::instr_iterator &argNextMII) + : MI(argMI), Entry(argEntry), NextMII(argNextMII) {} +}; + +typedef llvm::SmallVector<ReduceEntry, 32> ReduceEntryVector; + class MicroMipsSizeReduce : public MachineFunctionPass { public: static char ID; @@ -132,42 +151,50 @@ private: bool ReduceMBB(MachineBasicBlock &MBB); /// Attempts to reduce MI, returns true on success. - bool ReduceMI(const MachineBasicBlock::instr_iterator &MII); + bool ReduceMI(const MachineBasicBlock::instr_iterator &MII, + MachineBasicBlock::instr_iterator &NextMII); // Attempts to reduce LW/SW instruction into LWSP/SWSP, // returns true on success. - static bool ReduceXWtoXWSP(MachineInstr *MI, const ReduceEntry &Entry); + static bool ReduceXWtoXWSP(ReduceEntryFunArgs *Arguments); + + // Attempts to reduce two LW/SW instructions into LWP/SWP instruction, + // returns true on success. + static bool ReduceXWtoXWP(ReduceEntryFunArgs *Arguments); // Attempts to reduce LBU/LHU instruction into LBU16/LHU16, // returns true on success. - static bool ReduceLXUtoLXU16(MachineInstr *MI, const ReduceEntry &Entry); + static bool ReduceLXUtoLXU16(ReduceEntryFunArgs *Arguments); // Attempts to reduce SB/SH instruction into SB16/SH16, // returns true on success. - static bool ReduceSXtoSX16(MachineInstr *MI, const ReduceEntry &Entry); + static bool ReduceSXtoSX16(ReduceEntryFunArgs *Arguments); // Attempts to reduce arithmetic instructions, returns true on success. - static bool ReduceArithmeticInstructions(MachineInstr *MI, - const ReduceEntry &Entry); + static bool ReduceArithmeticInstructions(ReduceEntryFunArgs *Arguments); // Attempts to reduce ADDIU into ADDIUSP instruction, // returns true on success. - static bool ReduceADDIUToADDIUSP(MachineInstr *MI, const ReduceEntry &Entry); + static bool ReduceADDIUToADDIUSP(ReduceEntryFunArgs *Arguments); // Attempts to reduce ADDIU into ADDIUR1SP instruction, // returns true on success. - static bool ReduceADDIUToADDIUR1SP(MachineInstr *MI, - const ReduceEntry &Entry); + static bool ReduceADDIUToADDIUR1SP(ReduceEntryFunArgs *Arguments); // Attempts to reduce XOR into XOR16 instruction, // returns true on success. - static bool ReduceXORtoXOR16(MachineInstr *MI, const ReduceEntry &Entry); + static bool ReduceXORtoXOR16(ReduceEntryFunArgs *Arguments); - // Changes opcode of an instruction. - static bool ReplaceInstruction(MachineInstr *MI, const ReduceEntry &Entry); + // Changes opcode of an instruction, replaces an instruction with a + // new one, or replaces two instructions with a new instruction + // depending on their order i.e. if these are consecutive forward + // or consecutive backward + static bool ReplaceInstruction(MachineInstr *MI, const ReduceEntry &Entry, + MachineInstr *MI2 = nullptr, + bool ConsecutiveForward = true); // Table with transformation rules for each instruction. - static llvm::SmallVector<ReduceEntry, 16> ReduceTable; + static ReduceEntryVector ReduceTable; }; char MicroMipsSizeReduce::ID = 0; @@ -175,7 +202,7 @@ const MipsInstrInfo *MicroMipsSizeReduce::MipsII; // This table must be sorted by WideOpc as a main criterion and // ReduceType as a sub-criterion (when wide opcodes are the same). -llvm::SmallVector<ReduceEntry, 16> MicroMipsSizeReduce::ReduceTable = { +ReduceEntryVector MicroMipsSizeReduce::ReduceTable = { // ReduceType, OpCodes, ReduceFunction, // OpInfo(TransferOperands), @@ -200,12 +227,20 @@ llvm::SmallVector<ReduceEntry, 16> MicroMipsSizeReduce::ReduceTable = { OpInfo(OT_OperandsAll), ImmField(0, -1, 15, 2)}, {RT_OneInstr, OpCodes(Mips::LEA_ADDiu, Mips::ADDIUR1SP_MM), ReduceADDIUToADDIUR1SP, OpInfo(OT_Operands02), ImmField(2, 0, 64, 2)}, + {RT_OneInstr, OpCodes(Mips::LEA_ADDiu_MM, Mips::ADDIUR1SP_MM), + ReduceADDIUToADDIUR1SP, OpInfo(OT_Operands02), ImmField(2, 0, 64, 2)}, {RT_OneInstr, OpCodes(Mips::LHu, Mips::LHU16_MM), ReduceLXUtoLXU16, OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)}, {RT_OneInstr, OpCodes(Mips::LHu_MM, Mips::LHU16_MM), ReduceLXUtoLXU16, OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)}, + {RT_TwoInstr, OpCodes(Mips::LW, Mips::LWP_MM), ReduceXWtoXWP, + OpInfo(OT_OperandsLwp), ImmField(0, -2048, 2048, 2)}, {RT_OneInstr, OpCodes(Mips::LW, Mips::LWSP_MM), ReduceXWtoXWSP, OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)}, + {RT_TwoInstr, OpCodes(Mips::LW16_MM, Mips::LWP_MM), ReduceXWtoXWP, + OpInfo(OT_OperandsLwp), ImmField(0, -2048, 2048, 2)}, + {RT_TwoInstr, OpCodes(Mips::LW_MM, Mips::LWP_MM), ReduceXWtoXWP, + OpInfo(OT_OperandsLwp), ImmField(0, -2048, 2048, 2)}, {RT_OneInstr, OpCodes(Mips::LW_MM, Mips::LWSP_MM), ReduceXWtoXWSP, OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)}, {RT_OneInstr, OpCodes(Mips::SB, Mips::SB16_MM), ReduceSXtoSX16, @@ -222,15 +257,24 @@ llvm::SmallVector<ReduceEntry, 16> MicroMipsSizeReduce::ReduceTable = { {RT_OneInstr, OpCodes(Mips::SUBu_MM, Mips::SUBU16_MM), ReduceArithmeticInstructions, OpInfo(OT_OperandsAll), ImmField(0, 0, 0, -1)}, + {RT_TwoInstr, OpCodes(Mips::SW, Mips::SWP_MM), ReduceXWtoXWP, + OpInfo(OT_OperandsSwp), ImmField(0, -2048, 2048, 2)}, {RT_OneInstr, OpCodes(Mips::SW, Mips::SWSP_MM), ReduceXWtoXWSP, OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)}, + {RT_TwoInstr, OpCodes(Mips::SW16_MM, Mips::SWP_MM), ReduceXWtoXWP, + OpInfo(OT_OperandsSwp), ImmField(0, -2048, 2048, 2)}, + {RT_TwoInstr, OpCodes(Mips::SW_MM, Mips::SWP_MM), ReduceXWtoXWP, + OpInfo(OT_OperandsSwp), ImmField(0, -2048, 2048, 2)}, {RT_OneInstr, OpCodes(Mips::SW_MM, Mips::SWSP_MM), ReduceXWtoXWSP, OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)}, {RT_OneInstr, OpCodes(Mips::XOR, Mips::XOR16_MM), ReduceXORtoXOR16, OpInfo(OT_OperandsXOR), ImmField(0, 0, 0, -1)}, {RT_OneInstr, OpCodes(Mips::XOR_MM, Mips::XOR16_MM), ReduceXORtoXOR16, OpInfo(OT_OperandsXOR), ImmField(0, 0, 0, -1)}}; -} // namespace +} // end anonymous namespace + +INITIALIZE_PASS(MicroMipsSizeReduce, DEBUG_TYPE, MICROMIPS_SIZE_REDUCE_NAME, + false, false) // Returns true if the machine operand MO is register SP. static bool IsSP(const MachineOperand &MO) { @@ -297,37 +341,100 @@ static bool ImmInRange(MachineInstr *MI, const ReduceEntry &Entry) { return true; } +// Returns true if MI can be reduced to lwp/swp instruction +static bool CheckXWPInstr(MachineInstr *MI, bool ReduceToLwp, + const ReduceEntry &Entry) { + + if (ReduceToLwp && + !(MI->getOpcode() == Mips::LW || MI->getOpcode() == Mips::LW_MM || + MI->getOpcode() == Mips::LW16_MM)) + return false; + + if (!ReduceToLwp && + !(MI->getOpcode() == Mips::SW || MI->getOpcode() == Mips::SW_MM || + MI->getOpcode() == Mips::SW16_MM)) + return false; + + unsigned reg = MI->getOperand(0).getReg(); + if (reg == Mips::RA) + return false; + + if (!ImmInRange(MI, Entry)) + return false; + + if (ReduceToLwp && (MI->getOperand(0).getReg() == MI->getOperand(1).getReg())) + return false; + + return true; +} + +// Returns true if the registers Reg1 and Reg2 are consecutive +static bool ConsecutiveRegisters(unsigned Reg1, unsigned Reg2) { + static SmallVector<unsigned, 31> Registers = { + Mips::AT, Mips::V0, Mips::V1, Mips::A0, Mips::A1, Mips::A2, Mips::A3, + Mips::T0, Mips::T1, Mips::T2, Mips::T3, Mips::T4, Mips::T5, Mips::T6, + Mips::T7, Mips::S0, Mips::S1, Mips::S2, Mips::S3, Mips::S4, Mips::S5, + Mips::S6, Mips::S7, Mips::T8, Mips::T9, Mips::K0, Mips::K1, Mips::GP, + Mips::SP, Mips::FP, Mips::RA}; + + for (uint8_t i = 0; i < Registers.size() - 1; i++) { + if (Registers[i] == Reg1) { + if (Registers[i + 1] == Reg2) + return true; + else + return false; + } + } + return false; +} + +// Returns true if registers and offsets are consecutive +static bool ConsecutiveInstr(MachineInstr *MI1, MachineInstr *MI2) { + + int64_t Offset1, Offset2; + if (!GetImm(MI1, 2, Offset1)) + return false; + if (!GetImm(MI2, 2, Offset2)) + return false; + + unsigned Reg1 = MI1->getOperand(0).getReg(); + unsigned Reg2 = MI2->getOperand(0).getReg(); + + return ((Offset1 == (Offset2 - 4)) && (ConsecutiveRegisters(Reg1, Reg2))); +} + MicroMipsSizeReduce::MicroMipsSizeReduce() : MachineFunctionPass(ID) {} -bool MicroMipsSizeReduce::ReduceMI( - const MachineBasicBlock::instr_iterator &MII) { +bool MicroMipsSizeReduce::ReduceMI(const MachineBasicBlock::instr_iterator &MII, + MachineBasicBlock::instr_iterator &NextMII) { MachineInstr *MI = &*MII; unsigned Opcode = MI->getOpcode(); // Search the table. - llvm::SmallVector<ReduceEntry, 16>::const_iterator Start = - std::begin(ReduceTable); - llvm::SmallVector<ReduceEntry, 16>::const_iterator End = - std::end(ReduceTable); + ReduceEntryVector::const_iterator Start = std::begin(ReduceTable); + ReduceEntryVector::const_iterator End = std::end(ReduceTable); - std::pair<llvm::SmallVector<ReduceEntry, 16>::const_iterator, - llvm::SmallVector<ReduceEntry, 16>::const_iterator> + std::pair<ReduceEntryVector::const_iterator, + ReduceEntryVector::const_iterator> Range = std::equal_range(Start, End, Opcode); if (Range.first == Range.second) return false; - for (llvm::SmallVector<ReduceEntry, 16>::const_iterator Entry = Range.first; - Entry != Range.second; ++Entry) - if (((*Entry).ReduceFunction)(&(*MII), *Entry)) + for (ReduceEntryVector::const_iterator Entry = Range.first; + Entry != Range.second; ++Entry) { + ReduceEntryFunArgs Arguments(&(*MII), *Entry, NextMII); + if (((*Entry).ReduceFunction)(&Arguments)) return true; - + } return false; } -bool MicroMipsSizeReduce::ReduceXWtoXWSP(MachineInstr *MI, - const ReduceEntry &Entry) { +bool MicroMipsSizeReduce::ReduceXWtoXWSP(ReduceEntryFunArgs *Arguments) { + + MachineInstr *MI = Arguments->MI; + const ReduceEntry &Entry = Arguments->Entry; if (!ImmInRange(MI, Entry)) return false; @@ -338,8 +445,51 @@ bool MicroMipsSizeReduce::ReduceXWtoXWSP(MachineInstr *MI, return ReplaceInstruction(MI, Entry); } +bool MicroMipsSizeReduce::ReduceXWtoXWP(ReduceEntryFunArgs *Arguments) { + + const ReduceEntry &Entry = Arguments->Entry; + MachineBasicBlock::instr_iterator &NextMII = Arguments->NextMII; + const MachineBasicBlock::instr_iterator &E = + Arguments->MI->getParent()->instr_end(); + + if (NextMII == E) + return false; + + MachineInstr *MI1 = Arguments->MI; + MachineInstr *MI2 = &*NextMII; + + // ReduceToLwp = true/false - reduce to LWP/SWP instruction + bool ReduceToLwp = (MI1->getOpcode() == Mips::LW) || + (MI1->getOpcode() == Mips::LW_MM) || + (MI1->getOpcode() == Mips::LW16_MM); + + if (!CheckXWPInstr(MI1, ReduceToLwp, Entry)) + return false; + + if (!CheckXWPInstr(MI2, ReduceToLwp, Entry)) + return false; + + unsigned Reg1 = MI1->getOperand(1).getReg(); + unsigned Reg2 = MI2->getOperand(1).getReg(); + + if (Reg1 != Reg2) + return false; + + bool ConsecutiveForward = ConsecutiveInstr(MI1, MI2); + bool ConsecutiveBackward = ConsecutiveInstr(MI2, MI1); + + if (!(ConsecutiveForward || ConsecutiveBackward)) + return false; + + NextMII = std::next(NextMII); + return ReplaceInstruction(MI1, Entry, MI2, ConsecutiveForward); +} + bool MicroMipsSizeReduce::ReduceArithmeticInstructions( - MachineInstr *MI, const ReduceEntry &Entry) { + ReduceEntryFunArgs *Arguments) { + + MachineInstr *MI = Arguments->MI; + const ReduceEntry &Entry = Arguments->Entry; if (!isMMThreeBitGPRegister(MI->getOperand(0)) || !isMMThreeBitGPRegister(MI->getOperand(1)) || @@ -349,8 +499,11 @@ bool MicroMipsSizeReduce::ReduceArithmeticInstructions( return ReplaceInstruction(MI, Entry); } -bool MicroMipsSizeReduce::ReduceADDIUToADDIUR1SP(MachineInstr *MI, - const ReduceEntry &Entry) { +bool MicroMipsSizeReduce::ReduceADDIUToADDIUR1SP( + ReduceEntryFunArgs *Arguments) { + + MachineInstr *MI = Arguments->MI; + const ReduceEntry &Entry = Arguments->Entry; if (!ImmInRange(MI, Entry)) return false; @@ -361,8 +514,10 @@ bool MicroMipsSizeReduce::ReduceADDIUToADDIUR1SP(MachineInstr *MI, return ReplaceInstruction(MI, Entry); } -bool MicroMipsSizeReduce::ReduceADDIUToADDIUSP(MachineInstr *MI, - const ReduceEntry &Entry) { +bool MicroMipsSizeReduce::ReduceADDIUToADDIUSP(ReduceEntryFunArgs *Arguments) { + + MachineInstr *MI = Arguments->MI; + const ReduceEntry &Entry = Arguments->Entry; int64_t ImmValue; if (!GetImm(MI, Entry.ImmField(), ImmValue)) @@ -377,8 +532,10 @@ bool MicroMipsSizeReduce::ReduceADDIUToADDIUSP(MachineInstr *MI, return ReplaceInstruction(MI, Entry); } -bool MicroMipsSizeReduce::ReduceLXUtoLXU16(MachineInstr *MI, - const ReduceEntry &Entry) { +bool MicroMipsSizeReduce::ReduceLXUtoLXU16(ReduceEntryFunArgs *Arguments) { + + MachineInstr *MI = Arguments->MI; + const ReduceEntry &Entry = Arguments->Entry; if (!ImmInRange(MI, Entry)) return false; @@ -390,8 +547,10 @@ bool MicroMipsSizeReduce::ReduceLXUtoLXU16(MachineInstr *MI, return ReplaceInstruction(MI, Entry); } -bool MicroMipsSizeReduce::ReduceSXtoSX16(MachineInstr *MI, - const ReduceEntry &Entry) { +bool MicroMipsSizeReduce::ReduceSXtoSX16(ReduceEntryFunArgs *Arguments) { + + MachineInstr *MI = Arguments->MI; + const ReduceEntry &Entry = Arguments->Entry; if (!ImmInRange(MI, Entry)) return false; @@ -403,8 +562,11 @@ bool MicroMipsSizeReduce::ReduceSXtoSX16(MachineInstr *MI, return ReplaceInstruction(MI, Entry); } -bool MicroMipsSizeReduce::ReduceXORtoXOR16(MachineInstr *MI, - const ReduceEntry &Entry) { +bool MicroMipsSizeReduce::ReduceXORtoXOR16(ReduceEntryFunArgs *Arguments) { + + MachineInstr *MI = Arguments->MI; + const ReduceEntry &Entry = Arguments->Entry; + if (!isMMThreeBitGPRegister(MI->getOperand(0)) || !isMMThreeBitGPRegister(MI->getOperand(1)) || !isMMThreeBitGPRegister(MI->getOperand(2))) @@ -433,23 +595,25 @@ bool MicroMipsSizeReduce::ReduceMBB(MachineBasicBlock &MBB) { continue; // Try to reduce 32-bit instruction into 16-bit instruction - Modified |= ReduceMI(MII); + Modified |= ReduceMI(MII, NextMII); } return Modified; } bool MicroMipsSizeReduce::ReplaceInstruction(MachineInstr *MI, - const ReduceEntry &Entry) { + const ReduceEntry &Entry, + MachineInstr *MI2, + bool ConsecutiveForward) { enum OperandTransfer OpTransfer = Entry.TransferOperands(); - DEBUG(dbgs() << "Converting 32-bit: " << *MI); + LLVM_DEBUG(dbgs() << "Converting 32-bit: " << *MI); ++NumReduced; if (OpTransfer == OT_OperandsAll) { MI->setDesc(MipsII->get(Entry.NarrowOpc())); - DEBUG(dbgs() << " to 16-bit: " << *MI); + LLVM_DEBUG(dbgs() << " to 16-bit: " << *MI); return true; } else { MachineBasicBlock &MBB = *MI->getParent(); @@ -477,6 +641,27 @@ bool MicroMipsSizeReduce::ReplaceInstruction(MachineInstr *MI, } break; } + case OT_OperandsLwp: + case OT_OperandsSwp: { + if (ConsecutiveForward) { + MIB.add(MI->getOperand(0)); + MIB.add(MI2->getOperand(0)); + MIB.add(MI->getOperand(1)); + MIB.add(MI->getOperand(2)); + } else { // consecutive backward + MIB.add(MI2->getOperand(0)); + MIB.add(MI->getOperand(0)); + MIB.add(MI2->getOperand(1)); + MIB.add(MI2->getOperand(2)); + } + + LLVM_DEBUG(dbgs() << "and converting 32-bit: " << *MI2 + << " to: " << *MIB); + + MBB.erase_instr(MI); + MBB.erase_instr(MI2); + return true; + } default: llvm_unreachable("Unknown operand transfer!"); } @@ -484,7 +669,7 @@ bool MicroMipsSizeReduce::ReplaceInstruction(MachineInstr *MI, // Transfer MI flags. MIB.setMIFlags(MI->getFlags()); - DEBUG(dbgs() << " to 16-bit: " << *MIB); + LLVM_DEBUG(dbgs() << " to 16-bit: " << *MIB); MBB.erase_instr(MI); return true; } @@ -511,6 +696,6 @@ bool MicroMipsSizeReduce::runOnMachineFunction(MachineFunction &MF) { } /// Returns an instance of the MicroMips size reduction pass. -FunctionPass *llvm::createMicroMipsSizeReductionPass() { +FunctionPass *llvm::createMicroMipsSizeReducePass() { return new MicroMipsSizeReduce(); } |