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 arithmetic instructions, returns true on success
139   static bool ReduceArithmeticInstructions(MachineInstr *MI,
140                                            const ReduceEntry &Entry);
141 
142   // Changes opcode of an instruction
143   static bool ReplaceInstruction(MachineInstr *MI, const ReduceEntry &Entry);
144 
145   // Table with transformation rules for each instruction
146   static llvm::SmallVector<ReduceEntry, 16> ReduceTable;
147 };
148 
149 char MicroMipsSizeReduce::ID = 0;
150 const MipsInstrInfo *MicroMipsSizeReduce::MipsII;
151 
152 // This table must be sorted by WideOpc as a main criterion and
153 // ReduceType as a sub-criterion (when wide opcodes are the same)
154 llvm::SmallVector<ReduceEntry, 16> MicroMipsSizeReduce::ReduceTable = {
155 
156     // ReduceType, OpCodes, ReduceFunction,
157     // OpInfo(TransferOperands),
158     // ImmField(Shift, LBound, HBound, ImmFieldPosition)
159     {RT_OneInstr, OpCodes(Mips::ADDu, Mips::ADDU16_MM),
160      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
161      ImmField(0, 0, 0, -1)},
162     {RT_OneInstr, OpCodes(Mips::ADDu_MM, Mips::ADDU16_MM),
163      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
164      ImmField(0, 0, 0, -1)},
165     {RT_OneInstr, OpCodes(Mips::LW, Mips::LWSP_MM), ReduceXWtoXWSP,
166      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
167     {RT_OneInstr, OpCodes(Mips::LW_MM, Mips::LWSP_MM), ReduceXWtoXWSP,
168      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
169     {RT_OneInstr, OpCodes(Mips::SUBu, Mips::SUBU16_MM),
170      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
171      ImmField(0, 0, 0, -1)},
172     {RT_OneInstr, OpCodes(Mips::SUBu_MM, Mips::SUBU16_MM),
173      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
174      ImmField(0, 0, 0, -1)},
175     {RT_OneInstr, OpCodes(Mips::SW, Mips::SWSP_MM), ReduceXWtoXWSP,
176      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
177     {RT_OneInstr, OpCodes(Mips::SW_MM, Mips::SWSP_MM), ReduceXWtoXWSP,
178      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
179 };
180 }
181 
182 // Returns true if the machine operand MO is register SP
183 static bool IsSP(const MachineOperand &MO) {
184   if (MO.isReg() && ((MO.getReg() == Mips::SP)))
185     return true;
186   return false;
187 }
188 
189 // Returns true if the machine operand MO is register $16, $17, or $2-$7.
190 static bool isMMThreeBitGPRegister(const MachineOperand &MO) {
191   if (MO.isReg() && Mips::GPRMM16RegClass.contains(MO.getReg()))
192     return true;
193   return false;
194 }
195 
196 // Returns true if the operand Op is an immediate value
197 // and writes the immediate value into variable Imm
198 static bool GetImm(MachineInstr *MI, unsigned Op, int64_t &Imm) {
199 
200   if (!MI->getOperand(Op).isImm())
201     return false;
202   Imm = MI->getOperand(Op).getImm();
203   return true;
204 }
205 
206 // Returns true if the variable Value has the number of least-significant zero
207 // bits equal to Shift and if the shifted value is between the bounds
208 static bool InRange(int64_t Value, unsigned short Shift, int LBound,
209                     int HBound) {
210   int64_t Value2 = Value >> Shift;
211   if ((Value2 << Shift) == Value && (Value2 >= LBound) && (Value2 < HBound))
212     return true;
213   return false;
214 }
215 
216 // Returns true if immediate operand is in range
217 static bool ImmInRange(MachineInstr *MI, const ReduceEntry &Entry) {
218 
219   int64_t offset;
220 
221   if (!GetImm(MI, Entry.ImmField(), offset))
222     return false;
223 
224   if (!InRange(offset, Entry.Shift(), Entry.LBound(), Entry.HBound()))
225     return false;
226 
227   return true;
228 }
229 
230 MicroMipsSizeReduce::MicroMipsSizeReduce() : MachineFunctionPass(ID) {}
231 
232 bool MicroMipsSizeReduce::ReduceMI(
233     const MachineBasicBlock::instr_iterator &MII) {
234 
235   MachineInstr *MI = &*MII;
236   unsigned Opcode = MI->getOpcode();
237 
238   // Search the table.
239   llvm::SmallVector<ReduceEntry, 16>::const_iterator Start =
240       std::begin(ReduceTable);
241   llvm::SmallVector<ReduceEntry, 16>::const_iterator End =
242       std::end(ReduceTable);
243 
244   std::pair<llvm::SmallVector<ReduceEntry, 16>::const_iterator,
245             llvm::SmallVector<ReduceEntry, 16>::const_iterator>
246       Range = std::equal_range(Start, End, Opcode);
247 
248   if (Range.first == Range.second)
249     return false;
250 
251   for (llvm::SmallVector<ReduceEntry, 16>::const_iterator Entry = Range.first;
252        Entry != Range.second; ++Entry)
253     if (((*Entry).ReduceFunction)(&(*MII), *Entry))
254       return true;
255 
256   return false;
257 }
258 
259 bool MicroMipsSizeReduce::ReduceXWtoXWSP(MachineInstr *MI,
260                                          const ReduceEntry &Entry) {
261 
262   if (!ImmInRange(MI, Entry))
263     return false;
264 
265   if (!IsSP(MI->getOperand(1)))
266     return false;
267 
268   return ReplaceInstruction(MI, Entry);
269 }
270 
271 bool MicroMipsSizeReduce::ReduceArithmeticInstructions(
272     MachineInstr *MI, const ReduceEntry &Entry) {
273 
274   if (!isMMThreeBitGPRegister(MI->getOperand(0)) ||
275       !isMMThreeBitGPRegister(MI->getOperand(1)) ||
276       !isMMThreeBitGPRegister(MI->getOperand(2)))
277     return false;
278 
279   return ReplaceInstruction(MI, Entry);
280 }
281 
282 bool MicroMipsSizeReduce::ReduceMBB(MachineBasicBlock &MBB) {
283   bool Modified = false;
284   MachineBasicBlock::instr_iterator MII = MBB.instr_begin(),
285                                     E = MBB.instr_end();
286   MachineBasicBlock::instr_iterator NextMII;
287 
288   // Iterate through the instructions in the basic block
289   for (; MII != E; MII = NextMII) {
290     NextMII = std::next(MII);
291     MachineInstr *MI = &*MII;
292 
293     // Don't reduce bundled instructions or pseudo operations
294     if (MI->isBundle() || MI->isTransient())
295       continue;
296 
297     // Try to reduce 32-bit instruction into 16-bit instruction
298     Modified |= ReduceMI(MII);
299   }
300 
301   return Modified;
302 }
303 
304 bool MicroMipsSizeReduce::ReplaceInstruction(MachineInstr *MI,
305                                              const ReduceEntry &Entry) {
306 
307   MI->setDesc(MipsII->get(Entry.NarrowOpc()));
308   DEBUG(dbgs() << "Converted into 16-bit: " << *MI);
309   ++NumReduced;
310   return true;
311 }
312 
313 bool MicroMipsSizeReduce::runOnMachineFunction(MachineFunction &MF) {
314 
315   Subtarget = &static_cast<const MipsSubtarget &>(MF.getSubtarget());
316 
317   // TODO: Add support for other subtargets:
318   // microMIPS32r6 and microMIPS64r6
319   if (!Subtarget->inMicroMipsMode() || !Subtarget->hasMips32r2())
320     return false;
321 
322   MipsII = static_cast<const MipsInstrInfo *>(Subtarget->getInstrInfo());
323 
324   bool Modified = false;
325   MachineFunction::iterator I = MF.begin(), E = MF.end();
326 
327   for (; I != E; ++I)
328     Modified |= ReduceMBB(*I);
329   return Modified;
330 }
331 
332 /// Returns an instance of the MicroMips size reduction pass.
333 FunctionPass *llvm::createMicroMipsSizeReductionPass() {
334   return new MicroMipsSizeReduce();
335 }
336