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