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 } 393