1 files changed, 392 insertions, 0 deletions
diff --git a/contrib/llvm/lib/Target/Mips/MicroMipsSizeReduction.cpp b/contrib/llvm/lib/Target/Mips/MicroMipsSizeReduction.cpp
new file mode 100644
index 0000000..35948e3
--- /dev/null
+++ b/contrib/llvm/lib/Target/Mips/MicroMipsSizeReduction.cpp
@@ -0,0 +1,392 @@
+//=== 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 LBU/LHU instruction into LBU16/LHU16,
+  // returns true on success.
+  static bool ReduceLXUtoLXU16(MachineInstr *MI, const ReduceEntry &Entry);
+
+  // Attempts to reduce SB/SH instruction into SB16/SH16,
+  // returns true on success.
+  static bool ReduceSXtoSX16(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::LBu, Mips::LBU16_MM), ReduceLXUtoLXU16,
+     OpInfo(OT_OperandsAll), ImmField(0, -1, 15, 2)},
+    {RT_OneInstr, OpCodes(Mips::LBu_MM, Mips::LBU16_MM), ReduceLXUtoLXU16,
+     OpInfo(OT_OperandsAll), ImmField(0, -1, 15, 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_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::SB, Mips::SB16_MM), ReduceSXtoSX16,
+     OpInfo(OT_OperandsAll), ImmField(0, 0, 16, 2)},
+    {RT_OneInstr, OpCodes(Mips::SB_MM, Mips::SB16_MM), ReduceSXtoSX16,
+     OpInfo(OT_OperandsAll), ImmField(0, 0, 16, 2)},
+    {RT_OneInstr, OpCodes(Mips::SH, Mips::SH16_MM), ReduceSXtoSX16,
+     OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)},
+    {RT_OneInstr, OpCodes(Mips::SH_MM, Mips::SH16_MM), ReduceSXtoSX16,
+     OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 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 machine operand MO is register $0, $17, or $2-$7.
+static bool isMMSourceRegister(const MachineOperand &MO) {
+  if (MO.isReg() && Mips::GPRMM16ZeroRegClass.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::ReduceLXUtoLXU16(MachineInstr *MI,
+                                           const ReduceEntry &Entry) {
+
+  if (!ImmInRange(MI, Entry))
+    return false;
+
+  if (!isMMThreeBitGPRegister(MI->getOperand(0)) ||
+      !isMMThreeBitGPRegister(MI->getOperand(1)))
+    return false;
+
+  return ReplaceInstruction(MI, Entry);
+}
+
+bool MicroMipsSizeReduce::ReduceSXtoSX16(MachineInstr *MI,
+                                         const ReduceEntry &Entry) {
+
+  if (!ImmInRange(MI, Entry))
+    return false;
+
+  if (!isMMSourceRegister(MI->getOperand(0)) ||
+      !isMMThreeBitGPRegister(MI->getOperand(1)))
+    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();
+}