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

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