[mips[microMIPS]] Adding code size reduction pass for MicroMIPS

[milena.vujosevic.janicic]

Summary

The code implements size reduction pass for MicroMIPS.

Load and store instructions are examined and transformed, if possible.
lw32 instruction is transformed into 16-bit instruction lwsp
sw32 instruction is transformed into 16-bit instruction swsp

Arithmetic instrcutions are examined and transformed, if possible.
addu32 instruction is transformed into 16-bit instruction addu16
subu32 instruction is transformed into 16-bit instruction subu16

[milena.vujosevic.janicic]

New patch version rebased to revision 259635.
Any comments to this work?

[milena.vujosevic.janicic]

New patch version rebased to revision 264141.
Any comments?

[dsanders]

Sorry, I was part way through writing them a few weeks ago but was distracted by other things.

There appears to be two optimizations in this pass with very different requirements at the moment. The first optimization is a simple substitution of an MI for an equivalent MI with a smaller encoding. This part is generally heading in the right direction. The second is a peephole optimization that reduces two or more MI's into a single MI and this is where most of my concerns are. I don't believe it's checking enough to be able to prove that this reduction is safe. For example, ReduceMIToLwpSwp checks for interfering register uses but fails to check for interfering register defs (including implicit defs and sub/super-registers), memory reads/writes (including aliases), volatile accesses, side effects, etc. I think we should remove this portion for now and proceed with the simple size reductions to begin with.

For the testing in general: We ought to make use of the MIR (http://llvm.org/docs/MIRLangRef.html) so that we're only testing this pass. However, I'm not going to make that a requirement for this patch because I haven't used it myself yet.

I haven't looked too closely at the test cases yet but they will need to check the operands since this is a key part of whether your optimization is working as intended. I'd also like the tests to be more focused than they currently are. They look like they were generated from C examples and as such have a lot of unnecessary noise.

The rest of the comments below are things I noted while reading the patch. I've included them because I've already written them but some will most likely be made moot by the above changes. If the line numbers seem odd it's because they were written for the previous diff.

lib/Target/Mips/MicroMips32SizeReduction.cpp

24 ↗

(On Diff #51393)

Do we really need std::vector or can we use one of the alternatives from http://llvm.org/docs/ProgrammersManual.html#sequential-containers-std-vector-std-list-etc?

For example, I see there's a std::vector<MachineOperand> below. This would probably be better as a SmallVector<MachineOperand, 4> or similar.

37 ↗

(On Diff #51393)

What do these enumerators mean?

Naming nit: Types and enumerators should begin with a capital. They should also have a prefix such as 'ON_'. More information can be found at http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

601 ↗

(On Diff #51393)

Is the double-N meaninful?

604 ↗

(On Diff #51393)

Please delete the commented out code.

[dsanders]

lib/Target/Mips/MicroMips32SizeReduction.cpp

40–43 ↗

(On Diff #46911)

We can make this explanation appear in the doxygen documentation by writing this with '/' and '/<' comments like so:

/// Reduction type:
enum ReduceType {
  SeveralInstr, ///< Several instructions into lwm/swm.
  TwoInstr, ///< Two instructions into one.
  OneInstr ///< 32-bit instruction into 16-bit instruction.
};

Similarly for the other description comments below.

I notice that our doxygen config currently has 'EXTRACT_ANON_NSPACES=NO' but I'm going to propose that we change that.

47 ↗

(On Diff #46911)

Opperand -> Operand. This typo appears in a few other places too

48 ↗

(On Diff #46911)

Variables should begin with a capital and should be descriptive. With this style of constructor it's not ambiguous to use the same name for both the argument and the member (e.g. 'Shift(Shift)').

Similarly for the other constructors below.

59 ↗

(On Diff #46911)

The snr argument is never used.

64 ↗

(On Diff #46911)

I think I know what you're trying to say but the comment isn't very clear. I think you're referring to the way LWM16 only allows a subset of the registers that LVM32 allows.

Can we describe this in terms of register classes?

73–75 ↗

(On Diff #46911)

We normally use 'unsigned' for opcodes.

Also, what's the purpose of the second instruction? It's not clear from the comment

83 ↗

(On Diff #46911)

Why 'void *'? It seems we always pass in a 'struct ReduceEntryFA *'. We also de-reference it and take a copy immediately without nullptr checks so a reference would be better to avoid the copy and explicitly say it can't be nullptr at the same time.

124–125 ↗

(On Diff #46911)

Formatting.

143 ↗

(On Diff #46911)

Naming nit: We should probably drop the '32' so that we can re-use it for microMIPS64 in the future.

158 ↗

(On Diff #46911)

New code shouldn't repeat the function name in the comments.

207–208 ↗

(On Diff #46911)

Given that this is a static table, we should define the table as a normal array and use ArrayRef in this class

212 ↗

(On Diff #46911)

Is this redundant?

214–269 ↗

(On Diff #46911)

This table should probably be tablegen-erated but we can leave that for now and address it in later patches.

272–288 ↗

(On Diff #46911)

This is equivalent to GPRMM16RegClass.contains(Reg)

290–306 ↗

(On Diff #46911)

Similarly, this is equivalent to GPRMM16ZeroRegClass.contains(Reg)

307–312 ↗

(On Diff #46911)

This is only correct for the o32 and n32 ABIs. If you check for Mips::SP64 as well then it will cover the n64 ABI too.

343–344 ↗

(On Diff #46911)

I'd expect this to be indicative of a bug somewhere else. Should it be an assertion?

353 ↗

(On Diff #46911)

Operand indices are 'unsigned' rather than uint8_t

354–361 ↗

(On Diff #46911)

Am I right in thinking this is to check the pointer registers of each instruction are the same? If so, this should be ok but the function name should indicate that it's only suitable for pointers.

If integers are a possibility then we will also need to handle the fact that V0 != V0_64 despite being the same register.

366–381 ↗

(On Diff #46911)

I haven't tested this but something like:

const auto &End = GPR32RegClass.end();
const auto &I = std::find(GPR32RegClass.begin(), End, Reg1);
if (I == End || *I != Reg1)
  return false;
I++;
if (*I == Reg2)
  return true;
return false;

should be the equivalent without duplicating our register classes.

We ought to account for the '*_64' versions of these registers too which can be handled using GPR64RegClass.

385–386 ↗

(On Diff #46911)

Line wrapping

387–393 ↗

(On Diff #46911)

MathExtras.h has isShiftedInt() and isShiftedUInt() templates that are equivalent to this function

474–485 ↗

(On Diff #46911)

This is equivalent to this function:

MI->readsRegister(reg1) || MI->readsRegister(reg2)

If you pass the TRI argument then it will check for reads that occur because of super-register reads too. I don't think it can check for reads caused by sub-register reads though.

492 ↗

(On Diff #46911)

We should use C++11's range based for loop

for (const auto &I : MI->operands())

507–508 ↗

(On Diff #46911)

According to the tablegen definition, it's not guaranteed to be operand 2 when variable_ops for the Lwm/Swm is non-empty. It will be operand NumOps-1

516–517 ↗

(On Diff #46911)

Similarly, it's not guaranteed to be operand 1 when variable_ops for the Lwm/Swm is non-empty. It will be operand NumOps-2

532–533 ↗

(On Diff #46911)

Likewise

539 ↗

(On Diff #46911)

At minimum we have two sources/results ($16 and $31) along with a base address and offset so shouldn't the lower bound be 3.

Similarly: At most, we have five sources/results ($16-$19, and $31) along with the base address and offset so shouldn't the upper bound be 7?

551–560 ↗

(On Diff #46911)

std::find using GPR16MMRegClass and std::distance should be equivalent to this.

564 ↗

(On Diff #46911)

Rather than sort at startup, can we just keep the table sorted and assert std::is_sorted()? If we do want to std::sort() then the best place to put it would be in tablegen when we start tablegen-erating the array.

760 ↗

(On Diff #46911)

Use range-based for loop

940–941 ↗

(On Diff #51393)

Could you add a comment explaining why instrs[9] is special? What does '9' correspond to?

1003–1052 ↗

(On Diff #51393)

I think this is just mutating one MachineInst into another similar one. Do we really need to build a new instruction and transfer everything or can we just call MI->setDesc()?

lib/Target/Mips/MicroMipsInstrInfo.td

529–555 ↗

(On Diff #51393)

If we have explicit operands for the variable-length portion, do we still want the reglist16 operands? I believe the variable length portion covers the same operands as the reglist16's.

test/CodeGen/Mips/micromips-lwm-swm-lwp-swp-sw16.ll

1 ↗

(On Diff #46911)

(filename) Could you move this into a subdirectory for testing this pass? I'm thinking that the number of tests is going to grow over time and we ought to make it easy to tell which tests cover this pass.

test/CodeGen/Mips/micromips-lwsp-swsp.ll

1 ↗

(On Diff #46911)

(filename) Could you move this into a subdirectory for testing this pass?

[sdardis]

I believe this work should be implemented in a similar manner to ARM's codesize reduction passes, Thumb2SizeReduction.cpp and ARMLoadStoreOptimizer.cpp.

Their load store optimizer should be modifiable to work for microMIPS. Reusing their logic should avoid the tricky issue of moving loads and stores past other instructions. I'd suggest dropping all the load/store bundling from this patch and focus on the replacing a instruction with a smaller form.

Some of my comments may overlap with Daniel's as we've both looked this but I've tried to delete any ones that overlapped.

lib/Target/Mips/MicroMips32SizeReduction.cpp

1 ↗

(On Diff #46911)

This file should be called MicroMipsSizeReduction.cpp. This patch is for microMIPS32 but should be sufficiently general that it can be trivially extended to microMIPS64. microMIPS64 support should be a separate patch.

8 ↗

(On Diff #46911)

Please include a description of this pass, any relevant deficiencies and restrictions. Such as the fact is does not supprt microMIPS64. That comment should be at the bottom of the description as a TODO:.
It should look like:

<Usual LLVM boiler plate.>
//===----------------------------------------------------------------------===//
/// \file
/// This pass is used to reduce the size of instructions where applicable ...
/// ....
/// TODO: implement microMIPS64 support.
//===----------------------------------------------------------------------===//

28 ↗

(On Diff #46911)

"MicroMips-reduce-size" should be "micromips-reduce-size".

30 ↗

(On Diff #46911)

'instrs' should be 'instructions', no need to abbreviate it.

32 ↗

(On Diff #46911)

Here too.

595 ↗

(On Diff #46911)

Don't use void * and casts. Instead take a pointer/reference to the relevant type.

946 ↗

(On Diff #46911)

This can be reduced to a unsigned Opcode = <nested ternary operator>; <newline>MIB = BuildMI(...MipsII->get(Opcode));

958 ↗

(On Diff #46911)

Rather than packing the operands into a vector before picking the opcode, pick the opcode then iterate over instrs structure and add the operands from that directly.

971 ↗

(On Diff #46911)

Rename flag to something like 'CopyOperandsForward'.

991 ↗

(On Diff #46911)

Check for illegal cases first before building an instruction.

154 ↗

(On Diff #51393)

microMIPS is the preferred spelling.

399 ↗

(On Diff #51393)

This predicate is too lax. It has to check at least the same candidates as Filler:terminateSearch in MipsDelaySlotFiller.cpp, and also has to check it is not crossing control flow instructions such as wait, pause and branches or instructions such as sync which act as ordering barriers.

667–680 ↗

(On Diff #51393)

All this post loop code should be integrated into the loop body. Rather than 'break'ing out of the loop, in case when you've identified a candidate instruction, I believe you should check the rest of your conditions and if you cannot continue, and immediately return false. If the instruction was an invalid candidate but you can continue the search, update the use set and continue, otherwise you can return ReplaceInstruction(...). Outside the loop body, you should have 'return false'.

test/CodeGen/Mips/micromips-lwm-swm-lwp-swp-sw16.ll

3 ↗

(On Diff #46911)

Can you add CHECK-LABEL: <function name> here to match the function and in all the others?

[milena.vujosevic.janicic]

The code is simplified: everything about transforming several instructions into one instruction is removed (i.e. lwm/swm and lwp/swp). Therefore, most of the comments are not applicable for this code, but will be taken into account later. Test-cases are also simplified.

[milena.vujosevic.janicic]

lib/Target/Mips/MicroMips32SizeReduction.cpp

388–394 ↗

(On Diff #51393)

These functions are similar but are not equivalent and cannot be used in this case. isShiftedInt is a template which should be instantiated with a constant shift value, while here the value of shift is a parameter to the function. Also, in this case, low bound and high bound does not necessary correspond to bit width.

[milena.vujosevic.janicic]

Any comments?

[sdardis]

Comments inlined. Most of them are small issues, and an omission from the reduction table for LW16, which I think should go into this patch.

There is a second short form load instruction, lwgp. That should be done as a separate patch rather than including in this revision. It will be a small patch anyway.

Thanks.

lib/Target/Mips/MicroMipsSizeReduction.cpp

13 ↗

(On Diff #52209)

Doesn't this patch do this? :)

14 ↗

(On Diff #52209)

I think we should borrow ARM's load store optimise pass rather than implementing it here.

26–27 ↗

(On Diff #52209)

Please avoid unnecessary includes.

30 ↗

(On Diff #52209)

Unnecessary include.

41 ↗

(On Diff #52209)

By convention, there should be a colon after 'TODO'. Also, spelling of extended.

151–153 ↗

(On Diff #52209)

I'm not seeing this function used anywhere. Since there are predicates for stack relative accesses and short form memory accesses, is it required?

172–183 ↗

(On Diff #52209)

LW16 is missing from this table.

212–213 ↗

(On Diff #52209)

This should be an assert as calling this function with an out of range Op is an error.

MI->getOperand(Op)

in

if (!MI->getOperand(Op).isImm())

will assert that Op < MI->getNumOperands() anyway. Returning false covers a potential bug.

220–221 ↗

(On Diff #52209)

Capitalise Value and Shift as they refer to arguments of this function.

330–334 ↗

(On Diff #52209)

These two cases can be joined together for clarity.

The second case should use isTransient(). This catches cases where MI is a debug value and other pseudo operations like EHLABEL which do not correspond to physical instruction(s).

Put a comment this check saying something like 'Don't reduce bundled instructions or pseudo operations.' so the intention is obvious.

[milena.vujosevic.janicic]

All the comments from the previous revision are taken into account.
lw16/sw16 support was excluded because it is not necessary in this moment.

The code implements size reduction pass for MicroMIPS.
Load and store instructions are examined and transformed, if possible.

lw32 instruction is transformed into 16-bit instruction lwsp
sw32 instruction is transformed into 16-bit instruction swsp

Arithmetic instrcutions are examined and transformed, if possible.

addu32 instruction is transformed into 16-bit instruction addu16
subu32 instruction is transformed into 16-bit instruction subu16

[milena.vujosevic.janicic]

Any comments?

[sdardis]

lib/Target/Mips/MicroMipsSizeReduction.cpp

158 ↗

(On Diff #79229)

Can this be reduced in size to 16 or 8 entries?

263–285 ↗

(On Diff #79229)

These two functions can be folded together as ReduceXWtoXWSP with a comment stating it covers lwsp, swsp.

310–312 ↗

(On Diff #79229)

Style: drop the '{' '} when it is a single line.

315–317 ↗

(On Diff #79229)

Modifed |= Reduced(MI); is clearer.

327 ↗

(On Diff #79229)

This should be dbgs() << ...

test/CodeGen/Mips/micromips-sizereduction/micromips-lwsp-swsp.ll

6 ↗

(On Diff #79229)

Colon after the function name so that it matches properly.

[milena.vujosevic.janicic]

All the comments from the previous revision are taken into account.

[milena.vujosevic.janicic]

Any comments?

[sdardis]

LGTM. Some small nits inlined.

lib/Target/Mips/MicroMipsSizeReduction.cpp

18 ↗

(On Diff #90327)

Spurious empty line.

185 ↗

(On Diff #90327)

This shouldn't have SP_64 in the conditional as this pass doesn't support microMIPS in 64 bit mode yet..

test/CodeGen/Mips/llvm-ir/add.ll

27 ↗

(On Diff #90327)

Add -verify-machineinstrs to the parameters here. We want to know early if the generated machine code is malformed.

test/CodeGen/Mips/llvm-ir/sub.ll

13 ↗

(On Diff #90327)

Add -verify-machineinstrs to the parameters here. We want to know early if the generated machine code is malformed.

test/CodeGen/Mips/micromips-sizereduction/micromips-lwsp-swsp.ll

1 ↗

(On Diff #90327)

Add -verify-machineinstrs to the parameters here. We want to know early if the generated machine code is malformed.

llvm/trunk/lib/Target/Mips/CMakeLists.txt

add_llvm_target(MipsCodeGen
   MipsSEFrameLowering.cpp
   MipsSEInstrInfo.cpp
   MipsSEISelDAGToDAG.cpp
   MipsSEISelLowering.cpp
   MipsSERegisterInfo.cpp
   MipsSubtarget.cpp
   MipsTargetMachine.cpp
   MipsTargetObjectFile.cpp
+  MicroMipsSizeReduction.cpp
   )
 
 add_subdirectory(InstPrinter)
 add_subdirectory(Disassembler)
 add_subdirectory(TargetInfo)
 add_subdirectory(MCTargetDesc)
 add_subdirectory(AsmParser)
 

llvm/trunk/lib/Target/Mips/MicroMipsSizeReduction.cpp

+//=== 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<ReduceEntry, 16> 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<ReduceEntry, 16> 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<ReduceEntry, 16>::const_iterator Start =
+      std::begin(ReduceTable);
+  llvm::SmallVector<ReduceEntry, 16>::const_iterator End =
+      std::end(ReduceTable);
+
+  std::pair<llvm::SmallVector<ReduceEntry, 16>::const_iterator,
+            llvm::SmallVector<ReduceEntry, 16>::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))
+      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<const MipsSubtarget &>(MF.getSubtarget());
+
+  // TODO: Add support for other subtargets:
+  // microMIPS32r6 and microMIPS64r6
+  if (!Subtarget->inMicroMipsMode() || !Subtarget->hasMips32r2())
+    return false;
+
+  MipsII = static_cast<const MipsInstrInfo *>(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();
+}

llvm/trunk/lib/Target/Mips/Mips.h

namespace llvm {
   ModulePass *createMips16HardFloatPass(MipsTargetMachine &TM);
 
   FunctionPass *createMipsModuleISelDagPass(MipsTargetMachine &TM);
   FunctionPass *createMipsOptimizePICCallPass(MipsTargetMachine &TM);
   FunctionPass *createMipsDelaySlotFillerPass(MipsTargetMachine &TM);
   FunctionPass *createMipsHazardSchedule();
   FunctionPass *createMipsLongBranchPass(MipsTargetMachine &TM);
   FunctionPass *createMipsConstantIslandPass();
+  FunctionPass *createMicroMipsSizeReductionPass();
 } // end namespace llvm;
 
 #endif

llvm/trunk/lib/Target/Mips/MipsTargetMachine.cpp

TargetIRAnalysis MipsTargetMachine::getTargetIRAnalysis() {
   });
 }
 
 // Implemented by targets that want to run passes immediately before
 // machine code is emitted. return true if -print-machineinstrs should
 // 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
   // (new) pass that creates compact branches after the HSP must handle FS
   // hazards itself or be pipelined before the HSP.
   addPass(createMipsDelaySlotFillerPass(TM));
   addPass(createMipsHazardSchedule());
   addPass(createMipsLongBranchPass(TM));
   addPass(createMipsConstantIslandPass());
 }

llvm/trunk/test/CodeGen/Mips/llvm-ir/add.ll

 ; RUN: llc < %s -march=mips64 -mcpu=mips64r2 | FileCheck %s \
 ; RUN:    -check-prefixes=ALL,R2-R6,GP64
 ; RUN: llc < %s -march=mips64 -mcpu=mips64r3 | FileCheck %s \
 ; RUN:    -check-prefixes=ALL,R2-R6,GP64
 ; RUN: llc < %s -march=mips64 -mcpu=mips64r5 | FileCheck %s \
 ; 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
 ; RUN: llc < %s -march=mips -mcpu=mips64r6 -target-abi n64 -mattr=+micromips -O2 | FileCheck %s \
 ; RUN:    -check-prefixes=ALL,MMR6,MM64
 
 
 ; FIXME: This code sequence is inefficient as it should be 'subu $[[T0]], $zero, $[[T0]'. 
; ALL-LABEL: add_i64:
 
   ; GP32:       addu    $3, $5, $7
   ; GP32:       sltu    $[[T0:[0-9]+]], $3, $7
   ; GP32:       addu    $[[T1:[0-9]+]], $[[T0]], $6
   ; GP32:       addu    $2, $4, $[[T1]]
 
   ; 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]]
 
   ; MM64:       daddu   $2, $4, $5
 
   %r = add i64 %a, %b
   ret i64 %r
; ALL-LABEL: add_i128:
   ; GP64:       sltu      $[[T0:[0-9]+]], $3, $7
   ; GP64:       daddu     $[[T1:[0-9]+]], $[[T0]], $6
   ; GP64:       daddu     $2, $4, $[[T1]]
 
   ; MM32:       lw        $[[T0:[0-9]+]], 28($sp)
   ; 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]]
 
   ; MM64:       daddu     $3, $5, $7
   ; MM64:       sltu      $[[T0:[0-9]+]], $3, $7
   ; MM64:       daddu     $[[T1:[0-9]+]], $[[T0]], $6
   ; MM64:       daddu     $2, $4, $[[T1]]
 
; ALL-LABEL: add_i128_4:
   ; GP64:       daddiu  $[[T0:[0-9]+]], $5, 4
   ; GP64:       daddiu  $[[T1:[0-9]+]], $zero, 4
   ; GP64:       sltu    $[[T1]], $[[T0]], $[[T1]]
   ; GP64:       daddu   $2, $4, $[[T1]]
 
   ; 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]]
 
   ; MM64:       daddiu  $[[T0:[0-9]+]], $5, 4
   ; MM64:       daddiu  $[[T1:[0-9]+]], $zero, 4
   ; MM64:       sltu    $[[T1]], $[[T0]], $[[T1]]
   ; MM64:       daddu   $2, $4, $[[T1]]
 
; ALL-LABEL: add_i128_3:
   ; GP64:       daddiu  $[[T0:[0-9]+]], $5, 3
   ; GP64:       daddiu  $[[T1:[0-9]+]], $zero, 3
   ; GP64:       sltu    $[[T1]], $[[T0]], $[[T1]]
   ; GP64:       daddu   $2, $4, $[[T1]]
 
   ; 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]]
 
   ; MM64:       daddiu  $[[T0:[0-9]+]], $5, 3
   ; MM64:       daddiu  $[[T1:[0-9]+]], $zero, 3
   ; MM64:       sltu    $[[T1]], $[[T0]], $[[T1]]
   ; MM64:       daddu   $2, $4, $[[T1]]
 
   %r = add i128 3, %a
   ret i128 %r
 }

llvm/trunk/test/CodeGen/Mips/llvm-ir/sub.ll

 ; RUN: llc < %s -march=mips -mcpu=mips2 | FileCheck %s \
 ; RUN:    -check-prefixes=NOT-R2-R6,GP32,GP32-NOT-MM,NOT-MM
 ; RUN: llc < %s -march=mips -mcpu=mips32 | FileCheck %s \
 ; RUN:    -check-prefixes=NOT-R2-R6,GP32,GP32-NOT-MM,NOT-MM
 ; RUN: llc < %s -march=mips -mcpu=mips32r2 | FileCheck %s \
 ; RUN:    -check-prefixes=R2-R6,GP32,GP32-NOT-MM,NOT-MM
 ; RUN: llc < %s -march=mips -mcpu=mips32r3 | FileCheck %s \
 ; RUN:    -check-prefixes=R2-R6,GP32,GP32-NOT-MM,NOT-MM
 ; RUN: llc < %s -march=mips -mcpu=mips32r5 | FileCheck %s \
 ; 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
 ; RUN: llc < %s -march=mips64 -mcpu=mips3 | FileCheck %s \
 ; RUN:    -check-prefixes=NOT-R2-R6,GP64,NOT-MM
 ; RUN: llc < %s -march=mips64 -mcpu=mips4 | FileCheck %s \
 ; RUN:    -check-prefixes=NOT-R2-R6,GP64,NOT-MM
 ; RUN: llc < %s -march=mips64 -mcpu=mips64 | FileCheck %s \
; ALL-LABEL: sub_i32:
   %r = sub i32 %a, %b
   ret i32 %r
 }
 
 define signext i64 @sub_i64(i64 signext %a, i64 signext %b) {
 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]]
 
   ; GP64:           dsubu   $2, $4, $5
 
   %r = sub i64 %a, %b
   ret i64 %r
; ALL-LABEL: sub_i128:
 
   ; GP32-MM:        lw        $[[T0:[0-9]+]], 20($sp)
   ; GP32-MM:        sltu      $[[T1:[0-9]+]], $[[T2:[0-9]+]], $[[T0]]
   ; GP32-MM:        lw        $[[T3:[0-9]+]], 16($sp)
   ; GP32-MM:        addu      $[[T3]], $[[T1]], $[[T3]]
   ; 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
   ; GP64:           sltu      $[[T0:[0-9]+]], $5, $7
   ; GP64:           daddu     $[[T1:[0-9]+]], $[[T0]], $6
   ; GP64:           dsubu     $2, $4, $[[T1]]
 
   %r = sub i128 %a, %b
   ret i128 %r
 }

llvm/trunk/test/CodeGen/Mips/micromips-sizereduction/micromips-lwsp-swsp.ll

+; 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
+}