Index: lib/Target/Mips/CMakeLists.txt =================================================================== --- lib/Target/Mips/CMakeLists.txt +++ lib/Target/Mips/CMakeLists.txt @@ -48,6 +48,7 @@ MipsSubtarget.cpp MipsTargetMachine.cpp MipsTargetObjectFile.cpp + MicroMipsSizeReduction.cpp ) add_subdirectory(InstPrinter) Index: lib/Target/Mips/MicroMipsSizeReduction.cpp =================================================================== --- /dev/null +++ lib/Target/Mips/MicroMipsSizeReduction.cpp @@ -0,0 +1,336 @@ +//=== MicroMipsSizeReduction.cpp - MicroMips size reduction pass --------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +///\file +/// 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" +#include "MipsSubtarget.h" + +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/Support/Debug.h" + +using namespace llvm; + +#define DEBUG_TYPE "micromips-reduce-size" + +STATISTIC(NumReduced, "Number of 32-bit instructions reduced to 16-bit ones"); + +namespace { + +/// Order of operands to transfer +// TODO: Will be extended when additional optimizations are added +enum OperandTransfer { + OT_NA, ///< Not applicable + OT_OperandsAll, ///< Transfer all operands +}; + +/// Reduction type +// TODO: Will be extended when additional optimizations are added +enum ReduceType { + RT_OneInstr ///< Reduce one instruction into a smaller instruction +}; + +// Information about immediate field restrictions +struct ImmField { + ImmField() : ImmFieldOperand(-1), Shift(0), LBound(0), HBound(0) {} + ImmField(uint8_t Shift, int16_t LBound, int16_t HBound, + int8_t ImmFieldOperand) + : ImmFieldOperand(ImmFieldOperand), Shift(Shift), LBound(LBound), + HBound(HBound) {} + int8_t ImmFieldOperand; // Immediate operand, -1 if it does not exist + uint8_t Shift; // Shift value + int16_t LBound; // Low bound of the immediate operand + int16_t HBound; // High bound of the immediate operand +}; + +/// Information about operands +// TODO: Will be extended when additional optimizations are added +struct OpInfo { + OpInfo(enum OperandTransfer TransferOperands) + : TransferOperands(TransferOperands) {} + OpInfo() : TransferOperands(OT_NA) {} + + enum OperandTransfer + TransferOperands; ///< Operands to transfer to the new instruction +}; + +// Information about opcodes +struct OpCodes { + OpCodes(unsigned WideOpc, unsigned NarrowOpc) + : WideOpc(WideOpc), NarrowOpc(NarrowOpc) {} + + unsigned WideOpc; ///< Wide opcode + unsigned NarrowOpc; ///< Narrow opcode +}; + +/// 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 + + ReduceEntry(enum ReduceType RType, struct OpCodes Op, + bool (*F)(MachineInstr *MI, const ReduceEntry &Entry), + struct OpInfo OpInf, struct ImmField Imm) + : eRType(RType), ReduceFunction(F), Ops(Op), OpInf(OpInf), Imm(Imm) {} + + unsigned NarrowOpc() const { return Ops.NarrowOpc; } + unsigned WideOpc() const { return Ops.WideOpc; } + int16_t LBound() const { return Imm.LBound; } + int16_t HBound() const { return Imm.HBound; } + uint8_t Shift() const { return Imm.Shift; } + int8_t ImmField() const { return Imm.ImmFieldOperand; } + enum OperandTransfer TransferOperands() const { + return OpInf.TransferOperands; + } + enum ReduceType RType() const { return eRType; } + + // operator used by std::equal_range + bool operator<(const unsigned int r) const { return (WideOpc() < r); } + + // operator used by std::equal_range + friend bool operator<(const unsigned int r, const struct ReduceEntry &re) { + return (r < re.WideOpc()); + } +}; + +class MicroMipsSizeReduce : public MachineFunctionPass { +public: + static char ID; + MicroMipsSizeReduce(); + + static const MipsInstrInfo *MipsII; + const MipsSubtarget *Subtarget; + + bool runOnMachineFunction(MachineFunction &MF) override; + + llvm::StringRef getPassName() const override { + return "microMIPS instruction size reduction pass"; + } + +private: + /// Reduces width of instructions in the specified basic block. + bool ReduceMBB(MachineBasicBlock &MBB); + + /// Attempts to reduce MI, returns true on success. + bool ReduceMI(const MachineBasicBlock::instr_iterator &MII); + + // Attempts to reduce LW/SW instruction into LWSP/SWSP, + // returns true on success. + static bool ReduceXWtoXWSP(MachineInstr *MI, const ReduceEntry &Entry); + + // Attempts to reduce arithmetic instructions, returns true on success + static bool ReduceArithmeticInstructions(MachineInstr *MI, + const ReduceEntry &Entry); + + // Changes opcode of an instruction + static bool ReplaceInstruction(MachineInstr *MI, const ReduceEntry &Entry); + + // Table with transformation rules for each instruction + static llvm::SmallVector ReduceTable; +}; + +char MicroMipsSizeReduce::ID = 0; +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 MicroMipsSizeReduce::ReduceTable = { + + // ReduceType, OpCodes, ReduceFunction, + // OpInfo(TransferOperands), + // ImmField(Shift, LBound, HBound, ImmFieldPosition) + {RT_OneInstr, OpCodes(Mips::ADDu, Mips::ADDU16_MM), + ReduceArithmeticInstructions, OpInfo(OT_OperandsAll), + ImmField(0, 0, 0, -1)}, + {RT_OneInstr, OpCodes(Mips::ADDu_MM, Mips::ADDU16_MM), + ReduceArithmeticInstructions, OpInfo(OT_OperandsAll), + ImmField(0, 0, 0, -1)}, + {RT_OneInstr, OpCodes(Mips::LW, Mips::LWSP_MM), ReduceXWtoXWSP, + OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)}, + {RT_OneInstr, OpCodes(Mips::LW_MM, Mips::LWSP_MM), ReduceXWtoXWSP, + OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)}, + {RT_OneInstr, OpCodes(Mips::SUBu, Mips::SUBU16_MM), + ReduceArithmeticInstructions, OpInfo(OT_OperandsAll), + ImmField(0, 0, 0, -1)}, + {RT_OneInstr, OpCodes(Mips::SUBu_MM, Mips::SUBU16_MM), + ReduceArithmeticInstructions, OpInfo(OT_OperandsAll), + ImmField(0, 0, 0, -1)}, + {RT_OneInstr, OpCodes(Mips::SW, Mips::SWSP_MM), ReduceXWtoXWSP, + OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)}, + {RT_OneInstr, OpCodes(Mips::SW_MM, Mips::SWSP_MM), ReduceXWtoXWSP, + OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)}, +}; +} + +// Returns true if the machine operand MO is register SP +static bool IsSP(const MachineOperand &MO) { + if (MO.isReg() && ((MO.getReg() == Mips::SP) || (MO.getReg() == Mips::SP_64))) + return true; + return false; +} + +// Returns true if the machine operand MO is register $16, $17, or $2-$7. +static bool isMMThreeBitGPRegister(const MachineOperand &MO) { + if (MO.isReg() && Mips::GPRMM16RegClass.contains(MO.getReg())) + return true; + return false; +} + +// Returns true if the operand Op is an immediate value +// and writes the immediate value into variable Imm +static bool GetImm(MachineInstr *MI, unsigned Op, int64_t &Imm) { + + if (!MI->getOperand(Op).isImm()) + return false; + Imm = MI->getOperand(Op).getImm(); + return true; +} + +// Returns true if the variable Value has the number of least-significant zero +// bits equal to Shift and if the shifted value is between the bounds +static bool InRange(int64_t Value, unsigned short Shift, int LBound, + int HBound) { + int64_t Value2 = Value >> Shift; + if ((Value2 << Shift) == Value && (Value2 >= LBound) && (Value2 < HBound)) + return true; + return false; +} + +// Returns true if immediate operand is in range +static bool ImmInRange(MachineInstr *MI, const ReduceEntry &Entry) { + + int64_t offset; + + if (!GetImm(MI, Entry.ImmField(), offset)) + return false; + + if (!InRange(offset, Entry.Shift(), Entry.LBound(), Entry.HBound())) + return false; + + return true; +} + +MicroMipsSizeReduce::MicroMipsSizeReduce() : MachineFunctionPass(ID) {} + +bool MicroMipsSizeReduce::ReduceMI( + const MachineBasicBlock::instr_iterator &MII) { + + MachineInstr *MI = &*MII; + unsigned Opcode = MI->getOpcode(); + + // Search the table. + llvm::SmallVector::const_iterator Start = + std::begin(ReduceTable); + llvm::SmallVector::const_iterator End = + std::end(ReduceTable); + + std::pair::const_iterator, + llvm::SmallVector::const_iterator> + Range = std::equal_range(Start, End, Opcode); + + if (Range.first == Range.second) + return false; + + for (llvm::SmallVector::const_iterator Entry = Range.first; + Entry != Range.second; ++Entry) + if (((*Entry).ReduceFunction)(&(*MII), *Entry)) + return true; + + return false; +} + +bool MicroMipsSizeReduce::ReduceXWtoXWSP(MachineInstr *MI, + const ReduceEntry &Entry) { + + if (!ImmInRange(MI, Entry)) + return false; + + if (!IsSP(MI->getOperand(1))) + return false; + + return ReplaceInstruction(MI, Entry); +} + +bool MicroMipsSizeReduce::ReduceArithmeticInstructions( + MachineInstr *MI, const ReduceEntry &Entry) { + + if (!isMMThreeBitGPRegister(MI->getOperand(0)) || + !isMMThreeBitGPRegister(MI->getOperand(1)) || + !isMMThreeBitGPRegister(MI->getOperand(2))) + return false; + + return ReplaceInstruction(MI, Entry); +} + +bool MicroMipsSizeReduce::ReduceMBB(MachineBasicBlock &MBB) { + bool Modified = false; + MachineBasicBlock::instr_iterator MII = MBB.instr_begin(), + E = MBB.instr_end(); + MachineBasicBlock::instr_iterator NextMII; + + // Iterate through the instructions in the basic block + for (; MII != E; MII = NextMII) { + NextMII = std::next(MII); + MachineInstr *MI = &*MII; + + // Don't reduce bundled instructions or pseudo operations + if (MI->isBundle() || MI->isTransient()) + continue; + + // Try to reduce 32-bit instruction into 16-bit instruction + Modified |= ReduceMI(MII); + } + + return Modified; +} + +bool MicroMipsSizeReduce::ReplaceInstruction(MachineInstr *MI, + const ReduceEntry &Entry) { + + MI->setDesc(MipsII->get(Entry.NarrowOpc())); + DEBUG(dbgs() << "Converted into 16-bit: " << *MI); + ++NumReduced; + return true; +} + +bool MicroMipsSizeReduce::runOnMachineFunction(MachineFunction &MF) { + + Subtarget = &static_cast(MF.getSubtarget()); + + // TODO: Add support for other subtargets: + // microMIPS32r6 and microMIPS64r6 + if (!Subtarget->inMicroMipsMode() || !Subtarget->hasMips32r2()) + return false; + + MipsII = static_cast(Subtarget->getInstrInfo()); + + bool Modified = false; + MachineFunction::iterator I = MF.begin(), E = MF.end(); + + for (; I != E; ++I) + Modified |= ReduceMBB(*I); + return Modified; +} + +/// Returns an instance of the MicroMips size reduction pass. +FunctionPass *llvm::createMicroMipsSizeReductionPass() { + return new MicroMipsSizeReduce(); +} Index: lib/Target/Mips/Mips.h =================================================================== --- lib/Target/Mips/Mips.h +++ lib/Target/Mips/Mips.h @@ -33,6 +33,7 @@ FunctionPass *createMipsLongBranchPass(MipsTargetMachine &TM); FunctionPass *createMipsConstantIslandPass(); FunctionPass *createMipsExpandPseudoPass(); + FunctionPass *createMicroMipsSizeReductionPass(); } // end namespace llvm; #endif Index: lib/Target/Mips/MipsTargetMachine.cpp =================================================================== --- lib/Target/Mips/MipsTargetMachine.cpp +++ lib/Target/Mips/MipsTargetMachine.cpp @@ -261,6 +261,7 @@ // print out the code after the passes. void MipsPassConfig::addPreEmitPass() { MipsTargetMachine &TM = getMipsTargetMachine(); + addPass(createMicroMipsSizeReductionPass()); // The delay slot filler pass can potientially create forbidden slot (FS) // hazards for MIPSR6 which the hazard schedule pass (HSP) will fix. Any Index: test/CodeGen/Mips/llvm-ir/add.ll =================================================================== --- test/CodeGen/Mips/llvm-ir/add.ll +++ test/CodeGen/Mips/llvm-ir/add.ll @@ -117,7 +117,7 @@ ; GP64: daddu $2, $4, $5 - ; MM32: addu $3, $5, $7 + ; MM32: addu16 $3, $5, $7 ; MM32: sltu $[[T0:[0-9]+]], $3, $7 ; MM32: addu $[[T1:[0-9]+]], $[[T0]], $6 ; MM32: addu $2, $4, $[[T1]] @@ -158,16 +158,16 @@ ; MM32: addu $[[T1:[0-9]+]], $7, $[[T0]] ; MM32: sltu $[[T2:[0-9]+]], $[[T1]], $[[T0]] ; MM32: lw $[[T3:[0-9]+]], 24($sp) - ; MM32: addu $[[T4:[0-9]+]], $[[T2]], $[[T3]] - ; MM32: addu $[[T5:[0-9]+]], $6, $[[T4]] + ; MM32: addu16 $[[T4:[0-9]+]], $[[T2]], $[[T3]] + ; MM32: addu16 $[[T5:[0-9]+]], $6, $[[T4]] ; MM32: sltu $[[T6:[0-9]+]], $[[T5]], $[[T3]] ; MM32: lw $[[T7:[0-9]+]], 20($sp) - ; MM32: addu $[[T8:[0-9]+]], $[[T6]], $[[T7]] + ; MM32: addu16 $[[T8:[0-9]+]], $[[T6]], $[[T7]] ; MM32: lw $[[T9:[0-9]+]], 16($sp) - ; MM32: addu $[[T10:[0-9]+]], $5, $[[T8]] + ; MM32: addu16 $[[T10:[0-9]+]], $5, $[[T8]] ; MM32: sltu $[[T11:[0-9]+]], $[[T10]], $[[T7]] ; MM32: addu $[[T12:[0-9]+]], $[[T11]], $[[T9]] - ; MM32: addu $[[T13:[0-9]+]], $4, $[[T12]] + ; MM32: addu16 $[[T13:[0-9]+]], $4, $[[T12]] ; MM32: move $4, $[[T5]] ; MM32: move $5, $[[T1]] @@ -289,12 +289,12 @@ ; MM32: addiu $[[T0:[0-9]+]], $7, 4 ; MM32: li16 $[[T1:[0-9]+]], 4 ; MM32: sltu $[[T1]], $[[T0]], $[[T1]] - ; MM32: addu $[[T2:[0-9]+]], $6, $[[T1]] + ; MM32: addu16 $[[T2:[0-9]+]], $6, $[[T1]] ; MM32: li16 $[[T1]], 0 ; MM32: sltu $[[T3:[0-9]+]], $[[T2]], $[[T1]] - ; MM32: addu $[[T3]], $5, $[[T3]] + ; MM32: addu16 $[[T3]], $5, $[[T3]] ; MM32: sltu $[[T1]], $[[T3]], $[[T1]] - ; MM32: addu $[[T1]], $4, $[[T1]] + ; MM32: addu16 $[[T1]], $4, $[[T1]] ; MM32: move $4, $[[T2]] ; MM32: move $5, $[[T0]] @@ -419,12 +419,12 @@ ; MM32: addiu $[[T0:[0-9]+]], $7, 3 ; MM32: li16 $[[T1:[0-9]+]], 3 ; MM32: sltu $[[T1]], $[[T0]], $[[T1]] - ; MM32: addu $[[T2:[0-9]+]], $6, $[[T1]] + ; MM32: addu16 $[[T2:[0-9]+]], $6, $[[T1]] ; MM32: li16 $[[T3:[0-9]+]], 0 ; MM32: sltu $[[T4:[0-9]+]], $[[T2]], $[[T3]] - ; MM32: addu $[[T4]], $5, $[[T4]] + ; MM32: addu16 $[[T4]], $5, $[[T4]] ; MM32: sltu $[[T5:[0-9]+]], $[[T4]], $[[T3]] - ; MM32: addu $[[T5]], $4, $[[T5]] + ; MM32: addu16 $[[T5]], $4, $[[T5]] ; MM32: move $4, $[[T2]] ; MM32: move $5, $[[T0]] Index: test/CodeGen/Mips/llvm-ir/sub.ll =================================================================== --- test/CodeGen/Mips/llvm-ir/sub.ll +++ test/CodeGen/Mips/llvm-ir/sub.ll @@ -100,7 +100,7 @@ entry: ; ALL-LABEL: sub_i64: - ; GP32: subu $3, $5, $7 + ; GP32-NOT-MM subu $3, $5, $7 ; GP32: sltu $[[T0:[0-9]+]], $5, $7 ; GP32: addu $[[T1:[0-9]+]], $[[T0]], $6 ; GP32: subu $2, $4, $[[T1]] @@ -138,13 +138,13 @@ ; GP32-MM: lw $[[T4:[0-9]+]], 24($sp) ; GP32-MM: lw $[[T5:[0-9]+]], 28($sp) ; GP32-MM: subu $[[T1]], $7, $[[T5]] - ; GP32-MM: subu $[[T3]], $[[T6:[0-9]+]], $[[T3]] + ; GP32-MM: subu16 $[[T3]], $[[T6:[0-9]+]], $[[T3]] ; GP32-MM: sltu $[[T6]], $6, $[[T4]] - ; GP32-MM: addu $[[T0]], $[[T6]], $[[T0]] - ; GP32-MM: subu $[[T0]], $5, $[[T0]] + ; GP32-MM: addu16 $[[T0]], $[[T6]], $[[T0]] + ; GP32-MM: subu16 $[[T0]], $5, $[[T0]] ; GP32-MM: sltu $[[T6]], $7, $[[T5]] ; GP32-MM: addu $[[T6]], $[[T6]], $[[T4]] - ; GP32-MM: subu $[[T6]], $6, $[[T6]] + ; GP32-MM: subu16 $[[T6]], $6, $[[T6]] ; GP32-MM: move $[[T2]], $[[T1]] ; GP64: dsubu $3, $5, $7 Index: test/CodeGen/Mips/micromips-sizereduction/micromips-lwsp-swsp.ll =================================================================== --- /dev/null +++ test/CodeGen/Mips/micromips-sizereduction/micromips-lwsp-swsp.ll @@ -0,0 +1,11 @@ +; RUN: llc -march=mipsel -mcpu=mips32r2 -mattr=+micromips -asm-show-inst < %s | FileCheck %s + +; Function Attrs: nounwind +define i32 @function1(i32 (i32)* %f) { +entry: +; CHECK-LABEL: function1: +; CHECK: SWSP_MM +; CHECK: LWSP_MM + %call = call i32 %f(i32 0) + ret i32 0 +}