1 //===- MipsInstructionSelector.cpp ------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 /// This file implements the targeting of the InstructionSelector class for
10 /// Mips.
11 /// \todo This should be generated by TableGen.
12 //===----------------------------------------------------------------------===//
13 
14 #include "MipsRegisterBankInfo.h"
15 #include "MipsTargetMachine.h"
16 #include "llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h"
17 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
18 
19 #define DEBUG_TYPE "mips-isel"
20 
21 using namespace llvm;
22 
23 namespace {
24 
25 #define GET_GLOBALISEL_PREDICATE_BITSET
26 #include "MipsGenGlobalISel.inc"
27 #undef GET_GLOBALISEL_PREDICATE_BITSET
28 
29 class MipsInstructionSelector : public InstructionSelector {
30 public:
31   MipsInstructionSelector(const MipsTargetMachine &TM, const MipsSubtarget &STI,
32                           const MipsRegisterBankInfo &RBI);
33 
34   bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const override;
35   static const char *getName() { return DEBUG_TYPE; }
36 
37 private:
38   bool selectImpl(MachineInstr &I, CodeGenCoverage &CoverageInfo) const;
39   bool materialize32BitImm(unsigned DestReg, APInt Imm,
40                            MachineIRBuilder &B) const;
41   bool selectCopy(MachineInstr &I, MachineRegisterInfo &MRI) const;
42 
43   const MipsTargetMachine &TM;
44   const MipsSubtarget &STI;
45   const MipsInstrInfo &TII;
46   const MipsRegisterInfo &TRI;
47   const MipsRegisterBankInfo &RBI;
48 
49 #define GET_GLOBALISEL_PREDICATES_DECL
50 #include "MipsGenGlobalISel.inc"
51 #undef GET_GLOBALISEL_PREDICATES_DECL
52 
53 #define GET_GLOBALISEL_TEMPORARIES_DECL
54 #include "MipsGenGlobalISel.inc"
55 #undef GET_GLOBALISEL_TEMPORARIES_DECL
56 };
57 
58 } // end anonymous namespace
59 
60 #define GET_GLOBALISEL_IMPL
61 #include "MipsGenGlobalISel.inc"
62 #undef GET_GLOBALISEL_IMPL
63 
64 MipsInstructionSelector::MipsInstructionSelector(
65     const MipsTargetMachine &TM, const MipsSubtarget &STI,
66     const MipsRegisterBankInfo &RBI)
67     : InstructionSelector(), TM(TM), STI(STI), TII(*STI.getInstrInfo()),
68       TRI(*STI.getRegisterInfo()), RBI(RBI),
69 
70 #define GET_GLOBALISEL_PREDICATES_INIT
71 #include "MipsGenGlobalISel.inc"
72 #undef GET_GLOBALISEL_PREDICATES_INIT
73 #define GET_GLOBALISEL_TEMPORARIES_INIT
74 #include "MipsGenGlobalISel.inc"
75 #undef GET_GLOBALISEL_TEMPORARIES_INIT
76 {
77 }
78 
79 bool MipsInstructionSelector::selectCopy(MachineInstr &I,
80                                          MachineRegisterInfo &MRI) const {
81   unsigned DstReg = I.getOperand(0).getReg();
82   if (TargetRegisterInfo::isPhysicalRegister(DstReg))
83     return true;
84 
85   const RegisterBank *RegBank = RBI.getRegBank(DstReg, MRI, TRI);
86   const unsigned DstSize = MRI.getType(DstReg).getSizeInBits();
87 
88   const TargetRegisterClass *RC = &Mips::GPR32RegClass;
89   if (RegBank->getID() == Mips::FPRBRegBankID) {
90     if (DstSize == 32)
91       RC = &Mips::FGR32RegClass;
92     else if (DstSize == 64)
93       RC = STI.isFP64bit() ? &Mips::FGR64RegClass : &Mips::AFGR64RegClass;
94     else
95       llvm_unreachable("Unsupported destination size");
96   }
97   if (!RBI.constrainGenericRegister(DstReg, *RC, MRI)) {
98     LLVM_DEBUG(dbgs() << "Failed to constrain " << TII.getName(I.getOpcode())
99                       << " operand\n");
100     return false;
101   }
102   return true;
103 }
104 
105 bool MipsInstructionSelector::materialize32BitImm(unsigned DestReg, APInt Imm,
106                                                   MachineIRBuilder &B) const {
107   assert(Imm.getBitWidth() == 32 && "Unsupported immediate size.");
108   // Ori zero extends immediate. Used for values with zeros in high 16 bits.
109   if (Imm.getHiBits(16).isNullValue()) {
110     MachineInstr *Inst = B.buildInstr(Mips::ORi, {DestReg}, {Mips::ZERO})
111                              .addImm(Imm.getLoBits(16).getLimitedValue());
112     return constrainSelectedInstRegOperands(*Inst, TII, TRI, RBI);
113   }
114   // Lui places immediate in high 16 bits and sets low 16 bits to zero.
115   if (Imm.getLoBits(16).isNullValue()) {
116     MachineInstr *Inst = B.buildInstr(Mips::LUi, {DestReg}, {})
117                              .addImm(Imm.getHiBits(16).getLimitedValue());
118     return constrainSelectedInstRegOperands(*Inst, TII, TRI, RBI);
119   }
120   // ADDiu sign extends immediate. Used for values with 1s in high 17 bits.
121   if (Imm.isSignedIntN(16)) {
122     MachineInstr *Inst = B.buildInstr(Mips::ADDiu, {DestReg}, {Mips::ZERO})
123                              .addImm(Imm.getLoBits(16).getLimitedValue());
124     return constrainSelectedInstRegOperands(*Inst, TII, TRI, RBI);
125   }
126   // Values that cannot be materialized with single immediate instruction.
127   unsigned LUiReg = B.getMRI()->createVirtualRegister(&Mips::GPR32RegClass);
128   MachineInstr *LUi = B.buildInstr(Mips::LUi, {LUiReg}, {})
129                           .addImm(Imm.getHiBits(16).getLimitedValue());
130   MachineInstr *ORi = B.buildInstr(Mips::ORi, {DestReg}, {LUiReg})
131                           .addImm(Imm.getLoBits(16).getLimitedValue());
132   if (!constrainSelectedInstRegOperands(*LUi, TII, TRI, RBI))
133     return false;
134   if (!constrainSelectedInstRegOperands(*ORi, TII, TRI, RBI))
135     return false;
136   return true;
137 }
138 
139 /// Returning Opc indicates that we failed to select MIPS instruction opcode.
140 static unsigned selectLoadStoreOpCode(unsigned Opc, unsigned MemSizeInBytes) {
141   if (Opc == TargetOpcode::G_STORE)
142     switch (MemSizeInBytes) {
143     case 4:
144       return Mips::SW;
145     case 2:
146       return Mips::SH;
147     case 1:
148       return Mips::SB;
149     default:
150       return Opc;
151     }
152   else
153     // Unspecified extending load is selected into zeroExtending load.
154     switch (MemSizeInBytes) {
155     case 4:
156       return Mips::LW;
157     case 2:
158       return Opc == TargetOpcode::G_SEXTLOAD ? Mips::LH : Mips::LHu;
159     case 1:
160       return Opc == TargetOpcode::G_SEXTLOAD ? Mips::LB : Mips::LBu;
161     default:
162       return Opc;
163     }
164 }
165 
166 bool MipsInstructionSelector::select(MachineInstr &I,
167                                      CodeGenCoverage &CoverageInfo) const {
168 
169   MachineBasicBlock &MBB = *I.getParent();
170   MachineFunction &MF = *MBB.getParent();
171   MachineRegisterInfo &MRI = MF.getRegInfo();
172 
173   if (!isPreISelGenericOpcode(I.getOpcode())) {
174     if (I.isCopy())
175       return selectCopy(I, MRI);
176 
177     return true;
178   }
179 
180   if (I.getOpcode() == Mips::G_MUL) {
181     MachineInstr *Mul = BuildMI(MBB, I, I.getDebugLoc(), TII.get(Mips::MUL))
182                             .add(I.getOperand(0))
183                             .add(I.getOperand(1))
184                             .add(I.getOperand(2));
185     if (!constrainSelectedInstRegOperands(*Mul, TII, TRI, RBI))
186       return false;
187     Mul->getOperand(3).setIsDead(true);
188     Mul->getOperand(4).setIsDead(true);
189 
190     I.eraseFromParent();
191     return true;
192   }
193 
194   if (selectImpl(I, CoverageInfo))
195     return true;
196 
197   MachineInstr *MI = nullptr;
198   using namespace TargetOpcode;
199 
200   switch (I.getOpcode()) {
201   case G_UMULH: {
202     unsigned PseudoMULTuReg = MRI.createVirtualRegister(&Mips::ACC64RegClass);
203     MachineInstr *PseudoMULTu, *PseudoMove;
204 
205     PseudoMULTu = BuildMI(MBB, I, I.getDebugLoc(), TII.get(Mips::PseudoMULTu))
206                       .addDef(PseudoMULTuReg)
207                       .add(I.getOperand(1))
208                       .add(I.getOperand(2));
209     if (!constrainSelectedInstRegOperands(*PseudoMULTu, TII, TRI, RBI))
210       return false;
211 
212     PseudoMove = BuildMI(MBB, I, I.getDebugLoc(), TII.get(Mips::PseudoMFHI))
213                      .addDef(I.getOperand(0).getReg())
214                      .addUse(PseudoMULTuReg);
215     if (!constrainSelectedInstRegOperands(*PseudoMove, TII, TRI, RBI))
216       return false;
217 
218     I.eraseFromParent();
219     return true;
220   }
221   case G_GEP: {
222     MI = BuildMI(MBB, I, I.getDebugLoc(), TII.get(Mips::ADDu))
223              .add(I.getOperand(0))
224              .add(I.getOperand(1))
225              .add(I.getOperand(2));
226     break;
227   }
228   case G_FRAME_INDEX: {
229     MI = BuildMI(MBB, I, I.getDebugLoc(), TII.get(Mips::ADDiu))
230              .add(I.getOperand(0))
231              .add(I.getOperand(1))
232              .addImm(0);
233     break;
234   }
235   case G_BRCOND: {
236     MI = BuildMI(MBB, I, I.getDebugLoc(), TII.get(Mips::BNE))
237              .add(I.getOperand(0))
238              .addUse(Mips::ZERO)
239              .add(I.getOperand(1));
240     break;
241   }
242   case G_PHI: {
243     const unsigned DestReg = I.getOperand(0).getReg();
244     const unsigned DestRegBank = RBI.getRegBank(DestReg, MRI, TRI)->getID();
245     const unsigned OpSize = MRI.getType(DestReg).getSizeInBits();
246 
247     if (DestRegBank != Mips::GPRBRegBankID || OpSize != 32)
248       return false;
249 
250     const TargetRegisterClass *DefRC = &Mips::GPR32RegClass;
251     I.setDesc(TII.get(TargetOpcode::PHI));
252     return RBI.constrainGenericRegister(DestReg, *DefRC, MRI);
253   }
254   case G_STORE:
255   case G_LOAD:
256   case G_ZEXTLOAD:
257   case G_SEXTLOAD: {
258     const unsigned DestReg = I.getOperand(0).getReg();
259     const unsigned DestRegBank = RBI.getRegBank(DestReg, MRI, TRI)->getID();
260     const unsigned OpSize = MRI.getType(DestReg).getSizeInBits();
261     const unsigned OpMemSizeInBytes = (*I.memoperands_begin())->getSize();
262 
263     if (DestRegBank != Mips::GPRBRegBankID || OpSize != 32)
264       return false;
265 
266     const unsigned NewOpc =
267         selectLoadStoreOpCode(I.getOpcode(), OpMemSizeInBytes);
268     if (NewOpc == I.getOpcode())
269       return false;
270 
271     MI = BuildMI(MBB, I, I.getDebugLoc(), TII.get(NewOpc))
272              .add(I.getOperand(0))
273              .add(I.getOperand(1))
274              .addImm(0)
275              .addMemOperand(*I.memoperands_begin());
276     break;
277   }
278   case G_UDIV:
279   case G_UREM:
280   case G_SDIV:
281   case G_SREM: {
282     unsigned HILOReg = MRI.createVirtualRegister(&Mips::ACC64RegClass);
283     bool IsSigned = I.getOpcode() == G_SREM || I.getOpcode() == G_SDIV;
284     bool IsDiv = I.getOpcode() == G_UDIV || I.getOpcode() == G_SDIV;
285 
286     MachineInstr *PseudoDIV, *PseudoMove;
287     PseudoDIV = BuildMI(MBB, I, I.getDebugLoc(),
288                         TII.get(IsSigned ? Mips::PseudoSDIV : Mips::PseudoUDIV))
289                     .addDef(HILOReg)
290                     .add(I.getOperand(1))
291                     .add(I.getOperand(2));
292     if (!constrainSelectedInstRegOperands(*PseudoDIV, TII, TRI, RBI))
293       return false;
294 
295     PseudoMove = BuildMI(MBB, I, I.getDebugLoc(),
296                          TII.get(IsDiv ? Mips::PseudoMFLO : Mips::PseudoMFHI))
297                      .addDef(I.getOperand(0).getReg())
298                      .addUse(HILOReg);
299     if (!constrainSelectedInstRegOperands(*PseudoMove, TII, TRI, RBI))
300       return false;
301 
302     I.eraseFromParent();
303     return true;
304   }
305   case G_SELECT: {
306     // Handle operands with pointer type.
307     MI = BuildMI(MBB, I, I.getDebugLoc(), TII.get(Mips::MOVN_I_I))
308              .add(I.getOperand(0))
309              .add(I.getOperand(2))
310              .add(I.getOperand(1))
311              .add(I.getOperand(3));
312     break;
313   }
314   case G_CONSTANT: {
315     MachineIRBuilder B(I);
316     if (!materialize32BitImm(I.getOperand(0).getReg(),
317                              I.getOperand(1).getCImm()->getValue(), B))
318       return false;
319 
320     I.eraseFromParent();
321     return true;
322   }
323   case G_GLOBAL_VALUE: {
324     if (MF.getTarget().isPositionIndependent())
325       return false;
326 
327     const llvm::GlobalValue *GVal = I.getOperand(1).getGlobal();
328     unsigned LUiReg = MRI.createVirtualRegister(&Mips::GPR32RegClass);
329     MachineInstr *LUi, *ADDiu;
330 
331     LUi = BuildMI(MBB, I, I.getDebugLoc(), TII.get(Mips::LUi))
332               .addDef(LUiReg)
333               .addGlobalAddress(GVal);
334     LUi->getOperand(1).setTargetFlags(MipsII::MO_ABS_HI);
335 
336     ADDiu = BuildMI(MBB, I, I.getDebugLoc(), TII.get(Mips::ADDiu))
337                 .addDef(I.getOperand(0).getReg())
338                 .addUse(LUiReg)
339                 .addGlobalAddress(GVal);
340     ADDiu->getOperand(2).setTargetFlags(MipsII::MO_ABS_LO);
341 
342     if (!constrainSelectedInstRegOperands(*LUi, TII, TRI, RBI))
343       return false;
344     if (!constrainSelectedInstRegOperands(*ADDiu, TII, TRI, RBI))
345       return false;
346 
347     I.eraseFromParent();
348     return true;
349   }
350   case G_ICMP: {
351     struct Instr {
352       unsigned Opcode, Def, LHS, RHS;
353       Instr(unsigned Opcode, unsigned Def, unsigned LHS, unsigned RHS)
354           : Opcode(Opcode), Def(Def), LHS(LHS), RHS(RHS){};
355 
356       bool hasImm() const {
357         if (Opcode == Mips::SLTiu || Opcode == Mips::XORi)
358           return true;
359         return false;
360       }
361     };
362 
363     SmallVector<struct Instr, 2> Instructions;
364     unsigned ICMPReg = I.getOperand(0).getReg();
365     unsigned Temp = MRI.createVirtualRegister(&Mips::GPR32RegClass);
366     unsigned LHS = I.getOperand(2).getReg();
367     unsigned RHS = I.getOperand(3).getReg();
368     CmpInst::Predicate Cond =
369         static_cast<CmpInst::Predicate>(I.getOperand(1).getPredicate());
370 
371     switch (Cond) {
372     case CmpInst::ICMP_EQ: // LHS == RHS -> (LHS ^ RHS) < 1
373       Instructions.emplace_back(Mips::XOR, Temp, LHS, RHS);
374       Instructions.emplace_back(Mips::SLTiu, ICMPReg, Temp, 1);
375       break;
376     case CmpInst::ICMP_NE: // LHS != RHS -> 0 < (LHS ^ RHS)
377       Instructions.emplace_back(Mips::XOR, Temp, LHS, RHS);
378       Instructions.emplace_back(Mips::SLTu, ICMPReg, Mips::ZERO, Temp);
379       break;
380     case CmpInst::ICMP_UGT: // LHS >  RHS -> RHS < LHS
381       Instructions.emplace_back(Mips::SLTu, ICMPReg, RHS, LHS);
382       break;
383     case CmpInst::ICMP_UGE: // LHS >= RHS -> !(LHS < RHS)
384       Instructions.emplace_back(Mips::SLTu, Temp, LHS, RHS);
385       Instructions.emplace_back(Mips::XORi, ICMPReg, Temp, 1);
386       break;
387     case CmpInst::ICMP_ULT: // LHS <  RHS -> LHS < RHS
388       Instructions.emplace_back(Mips::SLTu, ICMPReg, LHS, RHS);
389       break;
390     case CmpInst::ICMP_ULE: // LHS <= RHS -> !(RHS < LHS)
391       Instructions.emplace_back(Mips::SLTu, Temp, RHS, LHS);
392       Instructions.emplace_back(Mips::XORi, ICMPReg, Temp, 1);
393       break;
394     case CmpInst::ICMP_SGT: // LHS >  RHS -> RHS < LHS
395       Instructions.emplace_back(Mips::SLT, ICMPReg, RHS, LHS);
396       break;
397     case CmpInst::ICMP_SGE: // LHS >= RHS -> !(LHS < RHS)
398       Instructions.emplace_back(Mips::SLT, Temp, LHS, RHS);
399       Instructions.emplace_back(Mips::XORi, ICMPReg, Temp, 1);
400       break;
401     case CmpInst::ICMP_SLT: // LHS <  RHS -> LHS < RHS
402       Instructions.emplace_back(Mips::SLT, ICMPReg, LHS, RHS);
403       break;
404     case CmpInst::ICMP_SLE: // LHS <= RHS -> !(RHS < LHS)
405       Instructions.emplace_back(Mips::SLT, Temp, RHS, LHS);
406       Instructions.emplace_back(Mips::XORi, ICMPReg, Temp, 1);
407       break;
408     default:
409       return false;
410     }
411 
412     MachineIRBuilder B(I);
413     for (const struct Instr &Instruction : Instructions) {
414       MachineInstrBuilder MIB = B.buildInstr(
415           Instruction.Opcode, {Instruction.Def}, {Instruction.LHS});
416 
417       if (Instruction.hasImm())
418         MIB.addImm(Instruction.RHS);
419       else
420         MIB.addUse(Instruction.RHS);
421 
422       if (!MIB.constrainAllUses(TII, TRI, RBI))
423         return false;
424     }
425 
426     I.eraseFromParent();
427     return true;
428   }
429   default:
430     return false;
431   }
432 
433   I.eraseFromParent();
434   return constrainSelectedInstRegOperands(*MI, TII, TRI, RBI);
435 }
436 
437 namespace llvm {
438 InstructionSelector *createMipsInstructionSelector(const MipsTargetMachine &TM,
439                                                    MipsSubtarget &Subtarget,
440                                                    MipsRegisterBankInfo &RBI) {
441   return new MipsInstructionSelector(TM, Subtarget, RBI);
442 }
443 } // end namespace llvm
444