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