llvm/lib/Target/Mips/MicroMipsSizeReduction.cpp

   1 //=== MicroMipsSizeReduction.cpp - MicroMips size reduction pass --------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///\file
   9 /// This pass is used to reduce the size of instructions where applicable.
  10 ///
  11 /// TODO: Implement microMIPS64 support.
  12 //===----------------------------------------------------------------------===//
  13 #include "Mips.h"
  14 #include "MipsInstrInfo.h"
  15 #include "MipsSubtarget.h"
  16 #include "llvm/ADT/Statistic.h"
  17 #include "llvm/CodeGen/MachineFunctionPass.h"
  18 #include "llvm/Support/Debug.h"
  19
  20 using namespace llvm;
  21
  22 #define DEBUG_TYPE "micromips-reduce-size"
  23 #define MICROMIPS_SIZE_REDUCE_NAME "MicroMips instruction size reduce pass"
  24
  25 STATISTIC(NumReduced, "Number of instructions reduced (32-bit to 16-bit ones, "
  26                       "or two instructions into one");
  27
  28 namespace {
  29
  30 /// Order of operands to transfer
  31 // TODO: Will be extended when additional optimizations are added
  32 enum OperandTransfer {
  33   OT_NA,            ///< Not applicable
  34   OT_OperandsAll,   ///< Transfer all operands
  35   OT_Operands02,    ///< Transfer operands 0 and 2
  36   OT_Operand2,      ///< Transfer just operand 2
  37   OT_OperandsXOR,   ///< Transfer operands for XOR16
  38   OT_OperandsLwp,   ///< Transfer operands for LWP
  39   OT_OperandsSwp,   ///< Transfer operands for SWP
  40   OT_OperandsMovep, ///< Transfer operands for MOVEP
  41 };
  42
  43 /// Reduction type
  44 // TODO: Will be extended when additional optimizations are added
  45 enum ReduceType {
  46   RT_TwoInstr, ///< Reduce two instructions into one instruction
  47   RT_OneInstr  ///< Reduce one instruction into a smaller instruction
  48 };
  49
  50 // Information about immediate field restrictions
  51 struct ImmField {
  52   ImmField() : ImmFieldOperand(-1), Shift(0), LBound(0), HBound(0) {}
  53   ImmField(uint8_t Shift, int16_t LBound, int16_t HBound,
  54            int8_t ImmFieldOperand)
  55       : ImmFieldOperand(ImmFieldOperand), Shift(Shift), LBound(LBound),
  56         HBound(HBound) {}
  57   int8_t ImmFieldOperand; // Immediate operand, -1 if it does not exist
  58   uint8_t Shift;          // Shift value
  59   int16_t LBound;         // Low bound of the immediate operand
  60   int16_t HBound;         // High bound of the immediate operand
  61 };
  62
  63 /// Information about operands
  64 // TODO: Will be extended when additional optimizations are added
  65 struct OpInfo {
  66   OpInfo(enum OperandTransfer TransferOperands)
  67       : TransferOperands(TransferOperands) {}
  68   OpInfo() : TransferOperands(OT_NA) {}
  69
  70   enum OperandTransfer
  71       TransferOperands; ///< Operands to transfer to the new instruction
  72 };
  73
  74 // Information about opcodes
  75 struct OpCodes {
  76   OpCodes(unsigned WideOpc, unsigned NarrowOpc)
  77       : WideOpc(WideOpc), NarrowOpc(NarrowOpc) {}
  78
  79   unsigned WideOpc;   ///< Wide opcode
  80   unsigned NarrowOpc; ///< Narrow opcode
  81 };
  82
  83 typedef struct ReduceEntryFunArgs ReduceEntryFunArgs;
  84
  85 /// ReduceTable - A static table with information on mapping from wide
  86 /// opcodes to narrow
  87 struct ReduceEntry {
  88
  89   enum ReduceType eRType; ///< Reduction type
  90   bool (*ReduceFunction)(
  91       ReduceEntryFunArgs *Arguments); ///< Pointer to reduce function
  92   struct OpCodes Ops;                 ///< All relevant OpCodes
  93   struct OpInfo OpInf;                ///< Characteristics of operands
  94   struct ImmField Imm;                ///< Characteristics of immediate field
  95
  96   ReduceEntry(enum ReduceType RType, struct OpCodes Op,
  97               bool (*F)(ReduceEntryFunArgs *Arguments), struct OpInfo OpInf,
  98               struct ImmField Imm)
  99       : eRType(RType), ReduceFunction(F), Ops(Op), OpInf(OpInf), Imm(Imm) {}
 100
 101   unsigned NarrowOpc() const { return Ops.NarrowOpc; }
 102   unsigned WideOpc() const { return Ops.WideOpc; }
 103   int16_t LBound() const { return Imm.LBound; }
 104   int16_t HBound() const { return Imm.HBound; }
 105   uint8_t Shift() const { return Imm.Shift; }
 106   int8_t ImmField() const { return Imm.ImmFieldOperand; }
 107   enum OperandTransfer TransferOperands() const {
 108     return OpInf.TransferOperands;
 109   }
 110   enum ReduceType RType() const { return eRType; }
 111
 112   // operator used by std::equal_range
 113   bool operator<(const unsigned int r) const { return (WideOpc() < r); }
 114
 115   // operator used by std::equal_range
 116   friend bool operator<(const unsigned int r, const struct ReduceEntry &re) {
 117     return (r < re.WideOpc());
 118   }
 119 };
 120
 121 // Function arguments for ReduceFunction
 122 struct ReduceEntryFunArgs {
 123   MachineInstr *MI;         // Instruction
 124   const ReduceEntry &Entry; // Entry field
 125   MachineBasicBlock::instr_iterator
 126       &NextMII; // Iterator to next instruction in block
 127
 128   ReduceEntryFunArgs(MachineInstr *argMI, const ReduceEntry &argEntry,
 129                      MachineBasicBlock::instr_iterator &argNextMII)
 130       : MI(argMI), Entry(argEntry), NextMII(argNextMII) {}
 131 };
 132
 133 typedef llvm::SmallVector<ReduceEntry, 32> ReduceEntryVector;
 134
 135 class MicroMipsSizeReduce : public MachineFunctionPass {
 136 public:
 137   static char ID;
 138   MicroMipsSizeReduce();
 139
 140   static const MipsInstrInfo *MipsII;
 141   const MipsSubtarget *Subtarget;
 142
 143   bool runOnMachineFunction(MachineFunction &MF) override;
 144
 145   llvm::StringRef getPassName() const override {
 146     return "microMIPS instruction size reduction pass";
 147   }
 148
 149 private:
 150   /// Reduces width of instructions in the specified basic block.
 151   bool ReduceMBB(MachineBasicBlock &MBB);
 152
 153   /// Attempts to reduce MI, returns true on success.
 154   bool ReduceMI(const MachineBasicBlock::instr_iterator &MII,
 155                 MachineBasicBlock::instr_iterator &NextMII);
 156
 157   // Attempts to reduce LW/SW instruction into LWSP/SWSP,
 158   // returns true on success.
 159   static bool ReduceXWtoXWSP(ReduceEntryFunArgs *Arguments);
 160
 161   // Attempts to reduce two LW/SW instructions into LWP/SWP instruction,
 162   // returns true on success.
 163   static bool ReduceXWtoXWP(ReduceEntryFunArgs *Arguments);
 164
 165   // Attempts to reduce LBU/LHU instruction into LBU16/LHU16,
 166   // returns true on success.
 167   static bool ReduceLXUtoLXU16(ReduceEntryFunArgs *Arguments);
 168
 169   // Attempts to reduce SB/SH instruction into SB16/SH16,
 170   // returns true on success.
 171   static bool ReduceSXtoSX16(ReduceEntryFunArgs *Arguments);
 172
 173   // Attempts to reduce two MOVE instructions into MOVEP instruction,
 174   // returns true on success.
 175   static bool ReduceMoveToMovep(ReduceEntryFunArgs *Arguments);
 176
 177   // Attempts to reduce arithmetic instructions, returns true on success.
 178   static bool ReduceArithmeticInstructions(ReduceEntryFunArgs *Arguments);
 179
 180   // Attempts to reduce ADDIU into ADDIUSP instruction,
 181   // returns true on success.
 182   static bool ReduceADDIUToADDIUSP(ReduceEntryFunArgs *Arguments);
 183
 184   // Attempts to reduce ADDIU into ADDIUR1SP instruction,
 185   // returns true on success.
 186   static bool ReduceADDIUToADDIUR1SP(ReduceEntryFunArgs *Arguments);
 187
 188   // Attempts to reduce XOR into XOR16 instruction,
 189   // returns true on success.
 190   static bool ReduceXORtoXOR16(ReduceEntryFunArgs *Arguments);
 191
 192   // Changes opcode of an instruction, replaces an instruction with a
 193   // new one, or replaces two instructions with a new instruction
 194   // depending on their order i.e. if these are consecutive forward
 195   // or consecutive backward
 196   static bool ReplaceInstruction(MachineInstr *MI, const ReduceEntry &Entry,
 197                                  MachineInstr *MI2 = nullptr,
 198                                  bool ConsecutiveForward = true);
 199
 200   // Table with transformation rules for each instruction.
 201   static ReduceEntryVector ReduceTable;
 202 };
 203
 204 char MicroMipsSizeReduce::ID = 0;
 205 const MipsInstrInfo *MicroMipsSizeReduce::MipsII;
 206
 207 // This table must be sorted by WideOpc as a main criterion and
 208 // ReduceType as a sub-criterion (when wide opcodes are the same).
 209 ReduceEntryVector MicroMipsSizeReduce::ReduceTable = {
 210
 211     // ReduceType, OpCodes, ReduceFunction,
 212     // OpInfo(TransferOperands),
 213     // ImmField(Shift, LBound, HBound, ImmFieldPosition)
 214     {RT_OneInstr, OpCodes(Mips::ADDiu, Mips::ADDIUR1SP_MM),
 215      ReduceADDIUToADDIUR1SP, OpInfo(OT_Operands02), ImmField(2, 0, 64, 2)},
 216     {RT_OneInstr, OpCodes(Mips::ADDiu, Mips::ADDIUSP_MM), ReduceADDIUToADDIUSP,
 217      OpInfo(OT_Operand2), ImmField(0, 0, 0, 2)},
 218     {RT_OneInstr, OpCodes(Mips::ADDiu_MM, Mips::ADDIUR1SP_MM),
 219      ReduceADDIUToADDIUR1SP, OpInfo(OT_Operands02), ImmField(2, 0, 64, 2)},
 220     {RT_OneInstr, OpCodes(Mips::ADDiu_MM, Mips::ADDIUSP_MM),
 221      ReduceADDIUToADDIUSP, OpInfo(OT_Operand2), ImmField(0, 0, 0, 2)},
 222     {RT_OneInstr, OpCodes(Mips::ADDu, Mips::ADDU16_MM),
 223      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
 224      ImmField(0, 0, 0, -1)},
 225     {RT_OneInstr, OpCodes(Mips::ADDu_MM, Mips::ADDU16_MM),
 226      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
 227      ImmField(0, 0, 0, -1)},
 228     {RT_OneInstr, OpCodes(Mips::LBu, Mips::LBU16_MM), ReduceLXUtoLXU16,
 229      OpInfo(OT_OperandsAll), ImmField(0, -1, 15, 2)},
 230     {RT_OneInstr, OpCodes(Mips::LBu_MM, Mips::LBU16_MM), ReduceLXUtoLXU16,
 231      OpInfo(OT_OperandsAll), ImmField(0, -1, 15, 2)},
 232     {RT_OneInstr, OpCodes(Mips::LEA_ADDiu, Mips::ADDIUR1SP_MM),
 233      ReduceADDIUToADDIUR1SP, OpInfo(OT_Operands02), ImmField(2, 0, 64, 2)},
 234     {RT_OneInstr, OpCodes(Mips::LEA_ADDiu_MM, Mips::ADDIUR1SP_MM),
 235      ReduceADDIUToADDIUR1SP, OpInfo(OT_Operands02), ImmField(2, 0, 64, 2)},
 236     {RT_OneInstr, OpCodes(Mips::LHu, Mips::LHU16_MM), ReduceLXUtoLXU16,
 237      OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)},
 238     {RT_OneInstr, OpCodes(Mips::LHu_MM, Mips::LHU16_MM), ReduceLXUtoLXU16,
 239      OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)},
 240     {RT_TwoInstr, OpCodes(Mips::LW, Mips::LWP_MM), ReduceXWtoXWP,
 241      OpInfo(OT_OperandsLwp), ImmField(0, -2048, 2048, 2)},
 242     {RT_OneInstr, OpCodes(Mips::LW, Mips::LWSP_MM), ReduceXWtoXWSP,
 243      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
 244     {RT_TwoInstr, OpCodes(Mips::LW16_MM, Mips::LWP_MM), ReduceXWtoXWP,
 245      OpInfo(OT_OperandsLwp), ImmField(0, -2048, 2048, 2)},
 246     {RT_TwoInstr, OpCodes(Mips::LW_MM, Mips::LWP_MM), ReduceXWtoXWP,
 247      OpInfo(OT_OperandsLwp), ImmField(0, -2048, 2048, 2)},
 248     {RT_OneInstr, OpCodes(Mips::LW_MM, Mips::LWSP_MM), ReduceXWtoXWSP,
 249      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
 250     {RT_TwoInstr, OpCodes(Mips::MOVE16_MM, Mips::MOVEP_MM), ReduceMoveToMovep,
 251      OpInfo(OT_OperandsMovep), ImmField(0, 0, 0, -1)},
 252     {RT_OneInstr, OpCodes(Mips::SB, Mips::SB16_MM), ReduceSXtoSX16,
 253      OpInfo(OT_OperandsAll), ImmField(0, 0, 16, 2)},
 254     {RT_OneInstr, OpCodes(Mips::SB_MM, Mips::SB16_MM), ReduceSXtoSX16,
 255      OpInfo(OT_OperandsAll), ImmField(0, 0, 16, 2)},
 256     {RT_OneInstr, OpCodes(Mips::SH, Mips::SH16_MM), ReduceSXtoSX16,
 257      OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)},
 258     {RT_OneInstr, OpCodes(Mips::SH_MM, Mips::SH16_MM), ReduceSXtoSX16,
 259      OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)},
 260     {RT_OneInstr, OpCodes(Mips::SUBu, Mips::SUBU16_MM),
 261      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
 262      ImmField(0, 0, 0, -1)},
 263     {RT_OneInstr, OpCodes(Mips::SUBu_MM, Mips::SUBU16_MM),
 264      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
 265      ImmField(0, 0, 0, -1)},
 266     {RT_TwoInstr, OpCodes(Mips::SW, Mips::SWP_MM), ReduceXWtoXWP,
 267      OpInfo(OT_OperandsSwp), ImmField(0, -2048, 2048, 2)},
 268     {RT_OneInstr, OpCodes(Mips::SW, Mips::SWSP_MM), ReduceXWtoXWSP,
 269      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
 270     {RT_TwoInstr, OpCodes(Mips::SW16_MM, Mips::SWP_MM), ReduceXWtoXWP,
 271      OpInfo(OT_OperandsSwp), ImmField(0, -2048, 2048, 2)},
 272     {RT_TwoInstr, OpCodes(Mips::SW_MM, Mips::SWP_MM), ReduceXWtoXWP,
 273      OpInfo(OT_OperandsSwp), ImmField(0, -2048, 2048, 2)},
 274     {RT_OneInstr, OpCodes(Mips::SW_MM, Mips::SWSP_MM), ReduceXWtoXWSP,
 275      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
 276     {RT_OneInstr, OpCodes(Mips::XOR, Mips::XOR16_MM), ReduceXORtoXOR16,
 277      OpInfo(OT_OperandsXOR), ImmField(0, 0, 0, -1)},
 278     {RT_OneInstr, OpCodes(Mips::XOR_MM, Mips::XOR16_MM), ReduceXORtoXOR16,
 279      OpInfo(OT_OperandsXOR), ImmField(0, 0, 0, -1)}};
 280 } // end anonymous namespace
 281
 282 INITIALIZE_PASS(MicroMipsSizeReduce, DEBUG_TYPE, MICROMIPS_SIZE_REDUCE_NAME,
 283                 false, false)
 284
 285 // Returns true if the machine operand MO is register SP.
 286 static bool IsSP(const MachineOperand &MO) {
 287   if (MO.isReg() && ((MO.getReg() == Mips::SP)))
 288     return true;
 289   return false;
 290 }
 291
 292 // Returns true if the machine operand MO is register $16, $17, or $2-$7.
 293 static bool isMMThreeBitGPRegister(const MachineOperand &MO) {
 294   if (MO.isReg() && Mips::GPRMM16RegClass.contains(MO.getReg()))
 295     return true;
 296   return false;
 297 }
 298
 299 // Returns true if the machine operand MO is register $0, $17, or $2-$7.
 300 static bool isMMSourceRegister(const MachineOperand &MO) {
 301   if (MO.isReg() && Mips::GPRMM16ZeroRegClass.contains(MO.getReg()))
 302     return true;
 303   return false;
 304 }
 305
 306 // Returns true if the operand Op is an immediate value
 307 // and writes the immediate value into variable Imm.
 308 static bool GetImm(MachineInstr *MI, unsigned Op, int64_t &Imm) {
 309
 310   if (!MI->getOperand(Op).isImm())
 311     return false;
 312   Imm = MI->getOperand(Op).getImm();
 313   return true;
 314 }
 315
 316 // Returns true if the value is a valid immediate for ADDIUSP.
 317 static bool AddiuspImmValue(int64_t Value) {
 318   int64_t Value2 = Value >> 2;
 319   if (((Value & (int64_t)maskTrailingZeros<uint64_t>(2)) == Value) &&
 320       ((Value2 >= 2 && Value2 <= 257) || (Value2 >= -258 && Value2 <= -3)))
 321     return true;
 322   return false;
 323 }
 324
 325 // Returns true if the variable Value has the number of least-significant zero
 326 // bits equal to Shift and if the shifted value is between the bounds.
 327 static bool InRange(int64_t Value, unsigned short Shift, int LBound,
 328                     int HBound) {
 329   int64_t Value2 = Value >> Shift;
 330   if (((Value & (int64_t)maskTrailingZeros<uint64_t>(Shift)) == Value) &&
 331       (Value2 >= LBound) && (Value2 < HBound))
 332     return true;
 333   return false;
 334 }
 335
 336 // Returns true if immediate operand is in range.
 337 static bool ImmInRange(MachineInstr *MI, const ReduceEntry &Entry) {
 338
 339   int64_t offset;
 340
 341   if (!GetImm(MI, Entry.ImmField(), offset))
 342     return false;
 343
 344   if (!InRange(offset, Entry.Shift(), Entry.LBound(), Entry.HBound()))
 345     return false;
 346
 347   return true;
 348 }
 349
 350 // Returns true if MI can be reduced to lwp/swp instruction
 351 static bool CheckXWPInstr(MachineInstr *MI, bool ReduceToLwp,
 352                           const ReduceEntry &Entry) {
 353
 354   if (ReduceToLwp &&
 355       !(MI->getOpcode() == Mips::LW || MI->getOpcode() == Mips::LW_MM ||
 356         MI->getOpcode() == Mips::LW16_MM))
 357     return false;
 358
 359   if (!ReduceToLwp &&
 360       !(MI->getOpcode() == Mips::SW || MI->getOpcode() == Mips::SW_MM ||
 361         MI->getOpcode() == Mips::SW16_MM))
 362     return false;
 363
 364   Register reg = MI->getOperand(0).getReg();
 365   if (reg == Mips::RA)
 366     return false;
 367
 368   if (!ImmInRange(MI, Entry))
 369     return false;
 370
 371   if (ReduceToLwp && (MI->getOperand(0).getReg() == MI->getOperand(1).getReg()))
 372     return false;
 373
 374   return true;
 375 }
 376
 377 // Returns true if the registers Reg1 and Reg2 are consecutive
 378 static bool ConsecutiveRegisters(unsigned Reg1, unsigned Reg2) {
 379   constexpr std::array<unsigned, 31> Registers = {
 380       {Mips::AT, Mips::V0, Mips::V1, Mips::A0, Mips::A1, Mips::A2, Mips::A3,
 381        Mips::T0, Mips::T1, Mips::T2, Mips::T3, Mips::T4, Mips::T5, Mips::T6,
 382        Mips::T7, Mips::S0, Mips::S1, Mips::S2, Mips::S3, Mips::S4, Mips::S5,
 383        Mips::S6, Mips::S7, Mips::T8, Mips::T9, Mips::K0, Mips::K1, Mips::GP,
 384        Mips::SP, Mips::FP, Mips::RA}};
 385
 386   for (uint8_t i = 0; i < Registers.size() - 1; i++) {
 387     if (Registers[i] == Reg1) {
 388       if (Registers[i + 1] == Reg2)
 389         return true;
 390       else
 391         return false;
 392     }
 393   }
 394   return false;
 395 }
 396
 397 // Returns true if registers and offsets are consecutive
 398 static bool ConsecutiveInstr(MachineInstr *MI1, MachineInstr *MI2) {
 399
 400   int64_t Offset1, Offset2;
 401   if (!GetImm(MI1, 2, Offset1))
 402     return false;
 403   if (!GetImm(MI2, 2, Offset2))
 404     return false;
 405
 406   Register Reg1 = MI1->getOperand(0).getReg();
 407   Register Reg2 = MI2->getOperand(0).getReg();
 408
 409   return ((Offset1 == (Offset2 - 4)) && (ConsecutiveRegisters(Reg1, Reg2)));
 410 }
 411
 412 MicroMipsSizeReduce::MicroMipsSizeReduce() : MachineFunctionPass(ID) {}
 413
 414 bool MicroMipsSizeReduce::ReduceMI(const MachineBasicBlock::instr_iterator &MII,
 415                                    MachineBasicBlock::instr_iterator &NextMII) {
 416
 417   MachineInstr *MI = &*MII;
 418   unsigned Opcode = MI->getOpcode();
 419
 420   // Search the table.
 421   ReduceEntryVector::const_iterator Start = std::begin(ReduceTable);
 422   ReduceEntryVector::const_iterator End = std::end(ReduceTable);
 423
 424   std::pair<ReduceEntryVector::const_iterator,
 425             ReduceEntryVector::const_iterator>
 426       Range = std::equal_range(Start, End, Opcode);
 427
 428   if (Range.first == Range.second)
 429     return false;
 430
 431   for (ReduceEntryVector::const_iterator Entry = Range.first;
 432        Entry != Range.second; ++Entry) {
 433     ReduceEntryFunArgs Arguments(&(*MII), *Entry, NextMII);
 434     if (((*Entry).ReduceFunction)(&Arguments))
 435       return true;
 436   }
 437   return false;
 438 }
 439
 440 bool MicroMipsSizeReduce::ReduceXWtoXWSP(ReduceEntryFunArgs *Arguments) {
 441
 442   MachineInstr *MI = Arguments->MI;
 443   const ReduceEntry &Entry = Arguments->Entry;
 444
 445   if (!ImmInRange(MI, Entry))
 446     return false;
 447
 448   if (!IsSP(MI->getOperand(1)))
 449     return false;
 450
 451   return ReplaceInstruction(MI, Entry);
 452 }
 453
 454 bool MicroMipsSizeReduce::ReduceXWtoXWP(ReduceEntryFunArgs *Arguments) {
 455
 456   const ReduceEntry &Entry = Arguments->Entry;
 457   MachineBasicBlock::instr_iterator &NextMII = Arguments->NextMII;
 458   const MachineBasicBlock::instr_iterator &E =
 459       Arguments->MI->getParent()->instr_end();
 460
 461   if (NextMII == E)
 462     return false;
 463
 464   MachineInstr *MI1 = Arguments->MI;
 465   MachineInstr *MI2 = &*NextMII;
 466
 467   // ReduceToLwp = true/false - reduce to LWP/SWP instruction
 468   bool ReduceToLwp = (MI1->getOpcode() == Mips::LW) ||
 469                      (MI1->getOpcode() == Mips::LW_MM) ||
 470                      (MI1->getOpcode() == Mips::LW16_MM);
 471
 472   if (!CheckXWPInstr(MI1, ReduceToLwp, Entry))
 473     return false;
 474
 475   if (!CheckXWPInstr(MI2, ReduceToLwp, Entry))
 476     return false;
 477
 478   Register Reg1 = MI1->getOperand(1).getReg();
 479   Register Reg2 = MI2->getOperand(1).getReg();
 480
 481   if (Reg1 != Reg2)
 482     return false;
 483
 484   bool ConsecutiveForward = ConsecutiveInstr(MI1, MI2);
 485   bool ConsecutiveBackward = ConsecutiveInstr(MI2, MI1);
 486
 487   if (!(ConsecutiveForward || ConsecutiveBackward))
 488     return false;
 489
 490   NextMII = std::next(NextMII);
 491   return ReplaceInstruction(MI1, Entry, MI2, ConsecutiveForward);
 492 }
 493
 494 bool MicroMipsSizeReduce::ReduceArithmeticInstructions(
 495     ReduceEntryFunArgs *Arguments) {
 496
 497   MachineInstr *MI = Arguments->MI;
 498   const ReduceEntry &Entry = Arguments->Entry;
 499
 500   if (!isMMThreeBitGPRegister(MI->getOperand(0)) ||
 501       !isMMThreeBitGPRegister(MI->getOperand(1)) ||
 502       !isMMThreeBitGPRegister(MI->getOperand(2)))
 503     return false;
 504
 505   return ReplaceInstruction(MI, Entry);
 506 }
 507
 508 bool MicroMipsSizeReduce::ReduceADDIUToADDIUR1SP(
 509     ReduceEntryFunArgs *Arguments) {
 510
 511   MachineInstr *MI = Arguments->MI;
 512   const ReduceEntry &Entry = Arguments->Entry;
 513
 514   if (!ImmInRange(MI, Entry))
 515     return false;
 516
 517   if (!isMMThreeBitGPRegister(MI->getOperand(0)) || !IsSP(MI->getOperand(1)))
 518     return false;
 519
 520   return ReplaceInstruction(MI, Entry);
 521 }
 522
 523 bool MicroMipsSizeReduce::ReduceADDIUToADDIUSP(ReduceEntryFunArgs *Arguments) {
 524
 525   MachineInstr *MI = Arguments->MI;
 526   const ReduceEntry &Entry = Arguments->Entry;
 527
 528   int64_t ImmValue;
 529   if (!GetImm(MI, Entry.ImmField(), ImmValue))
 530     return false;
 531
 532   if (!AddiuspImmValue(ImmValue))
 533     return false;
 534
 535   if (!IsSP(MI->getOperand(0)) || !IsSP(MI->getOperand(1)))
 536     return false;
 537
 538   return ReplaceInstruction(MI, Entry);
 539 }
 540
 541 bool MicroMipsSizeReduce::ReduceLXUtoLXU16(ReduceEntryFunArgs *Arguments) {
 542
 543   MachineInstr *MI = Arguments->MI;
 544   const ReduceEntry &Entry = Arguments->Entry;
 545
 546   if (!ImmInRange(MI, Entry))
 547     return false;
 548
 549   if (!isMMThreeBitGPRegister(MI->getOperand(0)) ||
 550       !isMMThreeBitGPRegister(MI->getOperand(1)))
 551     return false;
 552
 553   return ReplaceInstruction(MI, Entry);
 554 }
 555
 556 bool MicroMipsSizeReduce::ReduceSXtoSX16(ReduceEntryFunArgs *Arguments) {
 557
 558   MachineInstr *MI = Arguments->MI;
 559   const ReduceEntry &Entry = Arguments->Entry;
 560
 561   if (!ImmInRange(MI, Entry))
 562     return false;
 563
 564   if (!isMMSourceRegister(MI->getOperand(0)) ||
 565       !isMMThreeBitGPRegister(MI->getOperand(1)))
 566     return false;
 567
 568   return ReplaceInstruction(MI, Entry);
 569 }
 570
 571 // Returns true if Reg can be a source register
 572 // of MOVEP instruction
 573 static bool IsMovepSrcRegister(unsigned Reg) {
 574
 575   if (Reg == Mips::ZERO || Reg == Mips::V0 || Reg == Mips::V1 ||
 576       Reg == Mips::S0 || Reg == Mips::S1 || Reg == Mips::S2 ||
 577       Reg == Mips::S3 || Reg == Mips::S4)
 578     return true;
 579
 580   return false;
 581 }
 582
 583 // Returns true if Reg can be a destination register
 584 // of MOVEP instruction
 585 static bool IsMovepDestinationReg(unsigned Reg) {
 586
 587   if (Reg == Mips::A0 || Reg == Mips::A1 || Reg == Mips::A2 ||
 588       Reg == Mips::A3 || Reg == Mips::S5 || Reg == Mips::S6)
 589     return true;
 590
 591   return false;
 592 }
 593
 594 // Returns true if the registers can be a pair of destination
 595 // registers in MOVEP instruction
 596 static bool IsMovepDestinationRegPair(unsigned R0, unsigned R1) {
 597
 598   if ((R0 == Mips::A0 && R1 == Mips::S5) ||
 599       (R0 == Mips::A0 && R1 == Mips::S6) ||
 600       (R0 == Mips::A0 && R1 == Mips::A1) ||
 601       (R0 == Mips::A0 && R1 == Mips::A2) ||
 602       (R0 == Mips::A0 && R1 == Mips::A3) ||
 603       (R0 == Mips::A1 && R1 == Mips::A2) ||
 604       (R0 == Mips::A1 && R1 == Mips::A3) ||
 605       (R0 == Mips::A2 && R1 == Mips::A3))
 606     return true;
 607
 608   return false;
 609 }
 610
 611 bool MicroMipsSizeReduce::ReduceMoveToMovep(ReduceEntryFunArgs *Arguments) {
 612
 613   const ReduceEntry &Entry = Arguments->Entry;
 614   MachineBasicBlock::instr_iterator &NextMII = Arguments->NextMII;
 615   const MachineBasicBlock::instr_iterator &E =
 616       Arguments->MI->getParent()->instr_end();
 617
 618   if (NextMII == E)
 619     return false;
 620
 621   MachineInstr *MI1 = Arguments->MI;
 622   MachineInstr *MI2 = &*NextMII;
 623
 624   Register RegDstMI1 = MI1->getOperand(0).getReg();
 625   Register RegSrcMI1 = MI1->getOperand(1).getReg();
 626
 627   if (!IsMovepSrcRegister(RegSrcMI1))
 628     return false;
 629
 630   if (!IsMovepDestinationReg(RegDstMI1))
 631     return false;
 632
 633   if (MI2->getOpcode() != Entry.WideOpc())
 634     return false;
 635
 636   Register RegDstMI2 = MI2->getOperand(0).getReg();
 637   Register RegSrcMI2 = MI2->getOperand(1).getReg();
 638
 639   if (!IsMovepSrcRegister(RegSrcMI2))
 640     return false;
 641
 642   bool ConsecutiveForward;
 643   if (IsMovepDestinationRegPair(RegDstMI1, RegDstMI2)) {
 644     ConsecutiveForward = true;
 645   } else if (IsMovepDestinationRegPair(RegDstMI2, RegDstMI1)) {
 646     ConsecutiveForward = false;
 647   } else
 648     return false;
 649
 650   NextMII = std::next(NextMII);
 651   return ReplaceInstruction(MI1, Entry, MI2, ConsecutiveForward);
 652 }
 653
 654 bool MicroMipsSizeReduce::ReduceXORtoXOR16(ReduceEntryFunArgs *Arguments) {
 655
 656   MachineInstr *MI = Arguments->MI;
 657   const ReduceEntry &Entry = Arguments->Entry;
 658
 659   if (!isMMThreeBitGPRegister(MI->getOperand(0)) ||
 660       !isMMThreeBitGPRegister(MI->getOperand(1)) ||
 661       !isMMThreeBitGPRegister(MI->getOperand(2)))
 662     return false;
 663
 664   if (!(MI->getOperand(0).getReg() == MI->getOperand(2).getReg()) &&
 665       !(MI->getOperand(0).getReg() == MI->getOperand(1).getReg()))
 666     return false;
 667
 668   return ReplaceInstruction(MI, Entry);
 669 }
 670
 671 bool MicroMipsSizeReduce::ReduceMBB(MachineBasicBlock &MBB) {
 672   bool Modified = false;
 673   MachineBasicBlock::instr_iterator MII = MBB.instr_begin(),
 674                                     E = MBB.instr_end();
 675   MachineBasicBlock::instr_iterator NextMII;
 676
 677   // Iterate through the instructions in the basic block
 678   for (; MII != E; MII = NextMII) {
 679     NextMII = std::next(MII);
 680     MachineInstr *MI = &*MII;
 681
 682     // Don't reduce bundled instructions or pseudo operations
 683     if (MI->isBundle() || MI->isTransient())
 684       continue;
 685
 686     // Try to reduce 32-bit instruction into 16-bit instruction
 687     Modified |= ReduceMI(MII, NextMII);
 688   }
 689
 690   return Modified;
 691 }
 692
 693 bool MicroMipsSizeReduce::ReplaceInstruction(MachineInstr *MI,
 694                                              const ReduceEntry &Entry,
 695                                              MachineInstr *MI2,
 696                                              bool ConsecutiveForward) {
 697
 698   enum OperandTransfer OpTransfer = Entry.TransferOperands();
 699
 700   LLVM_DEBUG(dbgs() << "Converting 32-bit: " << *MI);
 701   ++NumReduced;
 702
 703   if (OpTransfer == OT_OperandsAll) {
 704     MI->setDesc(MipsII->get(Entry.NarrowOpc()));
 705     LLVM_DEBUG(dbgs() << "       to 16-bit: " << *MI);
 706     return true;
 707   } else {
 708     MachineBasicBlock &MBB = *MI->getParent();
 709     const MCInstrDesc &NewMCID = MipsII->get(Entry.NarrowOpc());
 710     DebugLoc dl = MI->getDebugLoc();
 711     MachineInstrBuilder MIB = BuildMI(MBB, MI, dl, NewMCID);
 712     switch (OpTransfer) {
 713     case OT_Operand2:
 714       MIB.add(MI->getOperand(2));
 715       break;
 716     case OT_Operands02: {
 717       MIB.add(MI->getOperand(0));
 718       MIB.add(MI->getOperand(2));
 719       break;
 720     }
 721     case OT_OperandsXOR: {
 722       if (MI->getOperand(0).getReg() == MI->getOperand(2).getReg()) {
 723         MIB.add(MI->getOperand(0));
 724         MIB.add(MI->getOperand(1));
 725         MIB.add(MI->getOperand(2));
 726       } else {
 727         MIB.add(MI->getOperand(0));
 728         MIB.add(MI->getOperand(2));
 729         MIB.add(MI->getOperand(1));
 730       }
 731       break;
 732     }
 733     case OT_OperandsMovep:
 734     case OT_OperandsLwp:
 735     case OT_OperandsSwp: {
 736       if (ConsecutiveForward) {
 737         MIB.add(MI->getOperand(0));
 738         MIB.add(MI2->getOperand(0));
 739         MIB.add(MI->getOperand(1));
 740         if (OpTransfer == OT_OperandsMovep)
 741           MIB.add(MI2->getOperand(1));
 742         else
 743           MIB.add(MI->getOperand(2));
 744       } else { // consecutive backward
 745         MIB.add(MI2->getOperand(0));
 746         MIB.add(MI->getOperand(0));
 747         MIB.add(MI2->getOperand(1));
 748         if (OpTransfer == OT_OperandsMovep)
 749           MIB.add(MI->getOperand(1));
 750         else
 751           MIB.add(MI2->getOperand(2));
 752       }
 753
 754       LLVM_DEBUG(dbgs() << "and converting 32-bit: " << *MI2
 755                         << "       to: " << *MIB);
 756
 757       MBB.erase_instr(MI);
 758       MBB.erase_instr(MI2);
 759       return true;
 760     }
 761     default:
 762       llvm_unreachable("Unknown operand transfer!");
 763     }
 764
 765     // Transfer MI flags.
 766     MIB.setMIFlags(MI->getFlags());
 767
 768     LLVM_DEBUG(dbgs() << "       to 16-bit: " << *MIB);
 769     MBB.erase_instr(MI);
 770     return true;
 771   }
 772   return false;
 773 }
 774
 775 bool MicroMipsSizeReduce::runOnMachineFunction(MachineFunction &MF) {
 776
 777   Subtarget = &MF.getSubtarget<MipsSubtarget>();
 778
 779   // TODO: Add support for the subtarget microMIPS32R6.
 780   if (!Subtarget->inMicroMipsMode() || !Subtarget->hasMips32r2() ||
 781       Subtarget->hasMips32r6())
 782     return false;
 783
 784   MipsII = static_cast<const MipsInstrInfo *>(Subtarget->getInstrInfo());
 785
 786   bool Modified = false;
 787   MachineFunction::iterator I = MF.begin(), E = MF.end();
 788
 789   for (; I != E; ++I)
 790     Modified |= ReduceMBB(*I);
 791   return Modified;
 792 }
 793
 794 /// Returns an instance of the MicroMips size reduction pass.
 795 FunctionPass *llvm::createMicroMipsSizeReducePass() {
 796   return new MicroMipsSizeReduce();
 797 }