Index: llvm/trunk/lib/Target/Mips/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Target/Mips/CMakeLists.txt +++ llvm/trunk/lib/Target/Mips/CMakeLists.txt @@ -47,6 +47,7 @@ MipsSubtarget.cpp MipsTargetMachine.cpp MipsTargetObjectFile.cpp + MicroMipsSizeReduction.cpp ) add_subdirectory(InstPrinter) Index: llvm/trunk/lib/Target/Mips/MicroMipsSizeReduction.cpp =================================================================== --- llvm/trunk/lib/Target/Mips/MicroMipsSizeReduction.cpp +++ llvm/trunk/lib/Target/Mips/MicroMipsSizeReduction.cpp @@ -0,0 +1,335 @@ +//=== 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))) + 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: llvm/trunk/lib/Target/Mips/Mips.h =================================================================== --- llvm/trunk/lib/Target/Mips/Mips.h +++ llvm/trunk/lib/Target/Mips/Mips.h @@ -32,6 +32,7 @@ FunctionPass *createMipsHazardSchedule(); FunctionPass *createMipsLongBranchPass(MipsTargetMachine &TM); FunctionPass *createMipsConstantIslandPass(); + FunctionPass *createMicroMipsSizeReductionPass(); } // end namespace llvm; #endif Index: llvm/trunk/lib/Target/Mips/MipsTargetMachine.cpp =================================================================== --- llvm/trunk/lib/Target/Mips/MipsTargetMachine.cpp +++ llvm/trunk/lib/Target/Mips/MipsTargetMachine.cpp @@ -260,6 +260,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: llvm/trunk/test/CodeGen/Mips/llvm-ir/add.ll =================================================================== --- llvm/trunk/test/CodeGen/Mips/llvm-ir/add.ll +++ llvm/trunk/test/CodeGen/Mips/llvm-ir/add.ll @@ -24,7 +24,7 @@ ; RUN: -check-prefixes=ALL,R2-R6,GP64 ; RUN: llc < %s -march=mips64 -mcpu=mips64r6 | FileCheck %s \ ; RUN: -check-prefixes=ALL,R2-R6,GP64 -; RUN: llc < %s -march=mips -mcpu=mips32r3 -mattr=+micromips -O2 | FileCheck %s \ +; RUN: llc < %s -march=mips -mcpu=mips32r3 -mattr=+micromips -O2 -verify-machineinstrs | FileCheck %s \ ; RUN: -check-prefixes=ALL,MMR6,MM32 ; RUN: llc < %s -march=mips -mcpu=mips32r6 -mattr=+micromips -O2 | FileCheck %s \ ; RUN: -check-prefixes=ALL,MMR6,MM32 @@ -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: llvm/trunk/test/CodeGen/Mips/llvm-ir/sub.ll =================================================================== --- llvm/trunk/test/CodeGen/Mips/llvm-ir/sub.ll +++ llvm/trunk/test/CodeGen/Mips/llvm-ir/sub.ll @@ -10,7 +10,7 @@ ; RUN: -check-prefixes=R2-R6,GP32,GP32-NOT-MM,NOT-MM ; RUN: llc < %s -march=mips -mcpu=mips32r6 | FileCheck %s \ ; RUN: -check-prefixes=R2-R6,GP32,GP32-NOT-MM,NOT-MM -; RUN: llc < %s -march=mips -mcpu=mips32r3 -mattr=+micromips | FileCheck %s \ +; RUN: llc < %s -march=mips -mcpu=mips32r3 -mattr=+micromips -verify-machineinstrs | FileCheck %s \ ; RUN: -check-prefixes=GP32-MM,GP32,MM ; RUN: llc < %s -march=mips -mcpu=mips32r6 -mattr=+micromips | FileCheck %s \ ; RUN: -check-prefixes=GP32-MM,GP32,MM @@ -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: llvm/trunk/test/CodeGen/Mips/micromips-sizereduction/micromips-lwsp-swsp.ll =================================================================== --- llvm/trunk/test/CodeGen/Mips/micromips-sizereduction/micromips-lwsp-swsp.ll +++ llvm/trunk/test/CodeGen/Mips/micromips-sizereduction/micromips-lwsp-swsp.ll @@ -0,0 +1,11 @@ +; RUN: llc -march=mipsel -mcpu=mips32r2 -mattr=+micromips -asm-show-inst -verify-machineinstrs < %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 +}