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 /// TODO: Implement support for reducing into lwp/swp instruction.
  14 //===----------------------------------------------------------------------===//
  15 #include "Mips.h"
  16 #include "MipsInstrInfo.h"
  17 #include "MipsSubtarget.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/CodeGen/MachineFunctionPass.h"
  20 #include "llvm/Support/Debug.h"
  21
  22 using namespace llvm;
  23
  24 #define DEBUG_TYPE "micromips-reduce-size"
  25
  26 STATISTIC(NumReduced, "Number of 32-bit instructions reduced to 16-bit ones");
  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 };
  36
  37 /// Reduction type
  38 // TODO: Will be extended when additional optimizations are added
  39 enum ReduceType {
  40   RT_OneInstr ///< Reduce one instruction into a smaller instruction
  41 };
  42
  43 // Information about immediate field restrictions
  44 struct ImmField {
  45   ImmField() : ImmFieldOperand(-1), Shift(0), LBound(0), HBound(0) {}
  46   ImmField(uint8_t Shift, int16_t LBound, int16_t HBound,
  47            int8_t ImmFieldOperand)
  48       : ImmFieldOperand(ImmFieldOperand), Shift(Shift), LBound(LBound),
  49         HBound(HBound) {}
  50   int8_t ImmFieldOperand; // Immediate operand, -1 if it does not exist
  51   uint8_t Shift;          // Shift value
  52   int16_t LBound;         // Low bound of the immediate operand
  53   int16_t HBound;         // High bound of the immediate operand
  54 };
  55
  56 /// Information about operands
  57 // TODO: Will be extended when additional optimizations are added
  58 struct OpInfo {
  59   OpInfo(enum OperandTransfer TransferOperands)
  60       : TransferOperands(TransferOperands) {}
  61   OpInfo() : TransferOperands(OT_NA) {}
  62
  63   enum OperandTransfer
  64       TransferOperands; ///< Operands to transfer to the new instruction
  65 };
  66
  67 // Information about opcodes
  68 struct OpCodes {
  69   OpCodes(unsigned WideOpc, unsigned NarrowOpc)
  70       : WideOpc(WideOpc), NarrowOpc(NarrowOpc) {}
  71
  72   unsigned WideOpc;   ///< Wide opcode
  73   unsigned NarrowOpc; ///< Narrow opcode
  74 };
  75
  76 /// ReduceTable - A static table with information on mapping from wide
  77 /// opcodes to narrow
  78 struct ReduceEntry {
  79
  80   enum ReduceType eRType; ///< Reduction type
  81   bool (*ReduceFunction)(
  82       MachineInstr *MI,
  83       const ReduceEntry &Entry); ///< Pointer to reduce function
  84   struct OpCodes Ops;            ///< All relevant OpCodes
  85   struct OpInfo OpInf;           ///< Characteristics of operands
  86   struct ImmField Imm;           ///< Characteristics of immediate field
  87
  88   ReduceEntry(enum ReduceType RType, struct OpCodes Op,
  89               bool (*F)(MachineInstr *MI, const ReduceEntry &Entry),
  90               struct OpInfo OpInf, struct ImmField Imm)
  91       : eRType(RType), ReduceFunction(F), Ops(Op), OpInf(OpInf), Imm(Imm) {}
  92
  93   unsigned NarrowOpc() const { return Ops.NarrowOpc; }
  94   unsigned WideOpc() const { return Ops.WideOpc; }
  95   int16_t LBound() const { return Imm.LBound; }
  96   int16_t HBound() const { return Imm.HBound; }
  97   uint8_t Shift() const { return Imm.Shift; }
  98   int8_t ImmField() const { return Imm.ImmFieldOperand; }
  99   enum OperandTransfer TransferOperands() const {
 100     return OpInf.TransferOperands;
 101   }
 102   enum ReduceType RType() const { return eRType; }
 103
 104   // operator used by std::equal_range
 105   bool operator<(const unsigned int r) const { return (WideOpc() < r); }
 106
 107   // operator used by std::equal_range
 108   friend bool operator<(const unsigned int r, const struct ReduceEntry &re) {
 109     return (r < re.WideOpc());
 110   }
 111 };
 112
 113 class MicroMipsSizeReduce : public MachineFunctionPass {
 114 public:
 115   static char ID;
 116   MicroMipsSizeReduce();
 117
 118   static const MipsInstrInfo *MipsII;
 119   const MipsSubtarget *Subtarget;
 120
 121   bool runOnMachineFunction(MachineFunction &MF) override;
 122
 123   llvm::StringRef getPassName() const override {
 124     return "microMIPS instruction size reduction pass";
 125   }
 126
 127 private:
 128   /// Reduces width of instructions in the specified basic block.
 129   bool ReduceMBB(MachineBasicBlock &MBB);
 130
 131   /// Attempts to reduce MI, returns true on success.
 132   bool ReduceMI(const MachineBasicBlock::instr_iterator &MII);
 133
 134   // Attempts to reduce LW/SW instruction into LWSP/SWSP,
 135   // returns true on success.
 136   static bool ReduceXWtoXWSP(MachineInstr *MI, const ReduceEntry &Entry);
 137
 138   // Attempts to reduce LBU/LHU instruction into LBU16/LHU16,
 139   // returns true on success.
 140   static bool ReduceLXUtoLXU16(MachineInstr *MI, const ReduceEntry &Entry);
 141
 142   // Attempts to reduce SB/SH instruction into SB16/SH16,
 143   // returns true on success.
 144   static bool ReduceSXtoSX16(MachineInstr *MI, const ReduceEntry &Entry);
 145
 146   // Attempts to reduce arithmetic instructions, returns true on success
 147   static bool ReduceArithmeticInstructions(MachineInstr *MI,
 148                                            const ReduceEntry &Entry);
 149
 150   // Changes opcode of an instruction
 151   static bool ReplaceInstruction(MachineInstr *MI, const ReduceEntry &Entry);
 152
 153   // Table with transformation rules for each instruction
 154   static llvm::SmallVector<ReduceEntry, 16> ReduceTable;
 155 };
 156
 157 char MicroMipsSizeReduce::ID = 0;
 158 const MipsInstrInfo *MicroMipsSizeReduce::MipsII;
 159
 160 // This table must be sorted by WideOpc as a main criterion and
 161 // ReduceType as a sub-criterion (when wide opcodes are the same)
 162 llvm::SmallVector<ReduceEntry, 16> MicroMipsSizeReduce::ReduceTable = {
 163
 164     // ReduceType, OpCodes, ReduceFunction,
 165     // OpInfo(TransferOperands),
 166     // ImmField(Shift, LBound, HBound, ImmFieldPosition)
 167     {RT_OneInstr, OpCodes(Mips::ADDu, Mips::ADDU16_MM),
 168      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
 169      ImmField(0, 0, 0, -1)},
 170     {RT_OneInstr, OpCodes(Mips::ADDu_MM, Mips::ADDU16_MM),
 171      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
 172      ImmField(0, 0, 0, -1)},
 173     {RT_OneInstr, OpCodes(Mips::LBu, Mips::LBU16_MM), ReduceLXUtoLXU16,
 174      OpInfo(OT_OperandsAll), ImmField(0, -1, 15, 2)},
 175     {RT_OneInstr, OpCodes(Mips::LBu_MM, Mips::LBU16_MM), ReduceLXUtoLXU16,
 176      OpInfo(OT_OperandsAll), ImmField(0, -1, 15, 2)},
 177     {RT_OneInstr, OpCodes(Mips::LHu, Mips::LHU16_MM), ReduceLXUtoLXU16,
 178      OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)},
 179     {RT_OneInstr, OpCodes(Mips::LHu_MM, Mips::LHU16_MM), ReduceLXUtoLXU16,
 180      OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)},
 181     {RT_OneInstr, OpCodes(Mips::LW, Mips::LWSP_MM), ReduceXWtoXWSP,
 182      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
 183     {RT_OneInstr, OpCodes(Mips::LW_MM, Mips::LWSP_MM), ReduceXWtoXWSP,
 184      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
 185     {RT_OneInstr, OpCodes(Mips::SB, Mips::SB16_MM), ReduceSXtoSX16,
 186      OpInfo(OT_OperandsAll), ImmField(0, 0, 16, 2)},
 187     {RT_OneInstr, OpCodes(Mips::SB_MM, Mips::SB16_MM), ReduceSXtoSX16,
 188      OpInfo(OT_OperandsAll), ImmField(0, 0, 16, 2)},
 189     {RT_OneInstr, OpCodes(Mips::SH, Mips::SH16_MM), ReduceSXtoSX16,
 190      OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)},
 191     {RT_OneInstr, OpCodes(Mips::SH_MM, Mips::SH16_MM), ReduceSXtoSX16,
 192      OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)},
 193     {RT_OneInstr, OpCodes(Mips::SUBu, Mips::SUBU16_MM),
 194      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
 195      ImmField(0, 0, 0, -1)},
 196     {RT_OneInstr, OpCodes(Mips::SUBu_MM, Mips::SUBU16_MM),
 197      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
 198      ImmField(0, 0, 0, -1)},
 199     {RT_OneInstr, OpCodes(Mips::SW, Mips::SWSP_MM), ReduceXWtoXWSP,
 200      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
 201     {RT_OneInstr, OpCodes(Mips::SW_MM, Mips::SWSP_MM), ReduceXWtoXWSP,
 202      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
 203 };
 204 }
 205
 206 // Returns true if the machine operand MO is register SP
 207 static bool IsSP(const MachineOperand &MO) {
 208   if (MO.isReg() && ((MO.getReg() == Mips::SP)))
 209     return true;
 210   return false;
 211 }
 212
 213 // Returns true if the machine operand MO is register $16, $17, or $2-$7.
 214 static bool isMMThreeBitGPRegister(const MachineOperand &MO) {
 215   if (MO.isReg() && Mips::GPRMM16RegClass.contains(MO.getReg()))
 216     return true;
 217   return false;
 218 }
 219
 220 // Returns true if the machine operand MO is register $0, $17, or $2-$7.
 221 static bool isMMSourceRegister(const MachineOperand &MO) {
 222   if (MO.isReg() && Mips::GPRMM16ZeroRegClass.contains(MO.getReg()))
 223     return true;
 224   return false;
 225 }
 226
 227 // Returns true if the operand Op is an immediate value
 228 // and writes the immediate value into variable Imm
 229 static bool GetImm(MachineInstr *MI, unsigned Op, int64_t &Imm) {
 230
 231   if (!MI->getOperand(Op).isImm())
 232     return false;
 233   Imm = MI->getOperand(Op).getImm();
 234   return true;
 235 }
 236
 237 // Returns true if the variable Value has the number of least-significant zero
 238 // bits equal to Shift and if the shifted value is between the bounds
 239 static bool InRange(int64_t Value, unsigned short Shift, int LBound,
 240                     int HBound) {
 241   int64_t Value2 = Value >> Shift;
 242   if ((Value2 << Shift) == Value && (Value2 >= LBound) && (Value2 < HBound))
 243     return true;
 244   return false;
 245 }
 246
 247 // Returns true if immediate operand is in range
 248 static bool ImmInRange(MachineInstr *MI, const ReduceEntry &Entry) {
 249
 250   int64_t offset;
 251
 252   if (!GetImm(MI, Entry.ImmField(), offset))
 253     return false;
 254
 255   if (!InRange(offset, Entry.Shift(), Entry.LBound(), Entry.HBound()))
 256     return false;
 257
 258   return true;
 259 }
 260
 261 MicroMipsSizeReduce::MicroMipsSizeReduce() : MachineFunctionPass(ID) {}
 262
 263 bool MicroMipsSizeReduce::ReduceMI(
 264     const MachineBasicBlock::instr_iterator &MII) {
 265
 266   MachineInstr *MI = &*MII;
 267   unsigned Opcode = MI->getOpcode();
 268
 269   // Search the table.
 270   llvm::SmallVector<ReduceEntry, 16>::const_iterator Start =
 271       std::begin(ReduceTable);
 272   llvm::SmallVector<ReduceEntry, 16>::const_iterator End =
 273       std::end(ReduceTable);
 274
 275   std::pair<llvm::SmallVector<ReduceEntry, 16>::const_iterator,
 276             llvm::SmallVector<ReduceEntry, 16>::const_iterator>
 277       Range = std::equal_range(Start, End, Opcode);
 278
 279   if (Range.first == Range.second)
 280     return false;
 281
 282   for (llvm::SmallVector<ReduceEntry, 16>::const_iterator Entry = Range.first;
 283        Entry != Range.second; ++Entry)
 284     if (((*Entry).ReduceFunction)(&(*MII), *Entry))
 285       return true;
 286
 287   return false;
 288 }
 289
 290 bool MicroMipsSizeReduce::ReduceXWtoXWSP(MachineInstr *MI,
 291                                          const ReduceEntry &Entry) {
 292
 293   if (!ImmInRange(MI, Entry))
 294     return false;
 295
 296   if (!IsSP(MI->getOperand(1)))
 297     return false;
 298
 299   return ReplaceInstruction(MI, Entry);
 300 }
 301
 302 bool MicroMipsSizeReduce::ReduceArithmeticInstructions(
 303     MachineInstr *MI, const ReduceEntry &Entry) {
 304
 305   if (!isMMThreeBitGPRegister(MI->getOperand(0)) ||
 306       !isMMThreeBitGPRegister(MI->getOperand(1)) ||
 307       !isMMThreeBitGPRegister(MI->getOperand(2)))
 308     return false;
 309
 310   return ReplaceInstruction(MI, Entry);
 311 }
 312
 313 bool MicroMipsSizeReduce::ReduceLXUtoLXU16(MachineInstr *MI,
 314                                            const ReduceEntry &Entry) {
 315
 316   if (!ImmInRange(MI, Entry))
 317     return false;
 318
 319   if (!isMMThreeBitGPRegister(MI->getOperand(0)) ||
 320       !isMMThreeBitGPRegister(MI->getOperand(1)))
 321     return false;
 322
 323   return ReplaceInstruction(MI, Entry);
 324 }
 325
 326 bool MicroMipsSizeReduce::ReduceSXtoSX16(MachineInstr *MI,
 327                                          const ReduceEntry &Entry) {
 328
 329   if (!ImmInRange(MI, Entry))
 330     return false;
 331
 332   if (!isMMSourceRegister(MI->getOperand(0)) ||
 333       !isMMThreeBitGPRegister(MI->getOperand(1)))
 334     return false;
 335
 336   return ReplaceInstruction(MI, Entry);
 337 }
 338
 339 bool MicroMipsSizeReduce::ReduceMBB(MachineBasicBlock &MBB) {
 340   bool Modified = false;
 341   MachineBasicBlock::instr_iterator MII = MBB.instr_begin(),
 342                                     E = MBB.instr_end();
 343   MachineBasicBlock::instr_iterator NextMII;
 344
 345   // Iterate through the instructions in the basic block
 346   for (; MII != E; MII = NextMII) {
 347     NextMII = std::next(MII);
 348     MachineInstr *MI = &*MII;
 349
 350     // Don't reduce bundled instructions or pseudo operations
 351     if (MI->isBundle() || MI->isTransient())
 352       continue;
 353
 354     // Try to reduce 32-bit instruction into 16-bit instruction
 355     Modified |= ReduceMI(MII);
 356   }
 357
 358   return Modified;
 359 }
 360
 361 bool MicroMipsSizeReduce::ReplaceInstruction(MachineInstr *MI,
 362                                              const ReduceEntry &Entry) {
 363
 364   MI->setDesc(MipsII->get(Entry.NarrowOpc()));
 365   DEBUG(dbgs() << "Converted into 16-bit: " << *MI);
 366   ++NumReduced;
 367   return true;
 368 }
 369
 370 bool MicroMipsSizeReduce::runOnMachineFunction(MachineFunction &MF) {
 371
 372   Subtarget = &static_cast<const MipsSubtarget &>(MF.getSubtarget());
 373
 374   // TODO: Add support for other subtargets:
 375   // microMIPS32r6 and microMIPS64r6
 376   if (!Subtarget->inMicroMipsMode() || !Subtarget->hasMips32r2())
 377     return false;
 378
 379   MipsII = static_cast<const MipsInstrInfo *>(Subtarget->getInstrInfo());
 380
 381   bool Modified = false;
 382   MachineFunction::iterator I = MF.begin(), E = MF.end();
 383
 384   for (; I != E; ++I)
 385     Modified |= ReduceMBB(*I);
 386   return Modified;
 387 }
 388
 389 /// Returns an instance of the MicroMips size reduction pass.
 390 FunctionPass *llvm::createMicroMipsSizeReductionPass() {
 391   return new MicroMipsSizeReduce();
 392 }