1 //===- ARMInstructionSelector.cpp ----------------------------*- C++ -*-==//
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 file implements the targeting of the InstructionSelector class for ARM.
11 /// \todo This should be generated by TableGen.
12 //===----------------------------------------------------------------------===//
13 
14 #include "ARMRegisterBankInfo.h"
15 #include "ARMSubtarget.h"
16 #include "ARMTargetMachine.h"
17 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
18 #include "llvm/CodeGen/MachineRegisterInfo.h"
19 #include "llvm/Support/Debug.h"
20 
21 #define DEBUG_TYPE "arm-isel"
22 
23 using namespace llvm;
24 
25 #ifndef LLVM_BUILD_GLOBAL_ISEL
26 #error "You shouldn't build this"
27 #endif
28 
29 namespace {
30 
31 #define GET_GLOBALISEL_PREDICATE_BITSET
32 #include "ARMGenGlobalISel.inc"
33 #undef GET_GLOBALISEL_PREDICATE_BITSET
34 
35 class ARMInstructionSelector : public InstructionSelector {
36 public:
37   ARMInstructionSelector(const ARMBaseTargetMachine &TM, const ARMSubtarget &STI,
38                          const ARMRegisterBankInfo &RBI);
39 
40   bool select(MachineInstr &I) const override;
41 
42 private:
43   bool selectImpl(MachineInstr &I) const;
44 
45   bool selectICmp(MachineInstrBuilder &MIB, const ARMBaseInstrInfo &TII,
46                   MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
47                   const RegisterBankInfo &RBI) const;
48 
49   const ARMBaseInstrInfo &TII;
50   const ARMBaseRegisterInfo &TRI;
51   const ARMBaseTargetMachine &TM;
52   const ARMRegisterBankInfo &RBI;
53   const ARMSubtarget &STI;
54 
55 #define GET_GLOBALISEL_PREDICATES_DECL
56 #include "ARMGenGlobalISel.inc"
57 #undef GET_GLOBALISEL_PREDICATES_DECL
58 
59 // We declare the temporaries used by selectImpl() in the class to minimize the
60 // cost of constructing placeholder values.
61 #define GET_GLOBALISEL_TEMPORARIES_DECL
62 #include "ARMGenGlobalISel.inc"
63 #undef GET_GLOBALISEL_TEMPORARIES_DECL
64 };
65 } // end anonymous namespace
66 
67 namespace llvm {
68 InstructionSelector *
69 createARMInstructionSelector(const ARMBaseTargetMachine &TM,
70                              const ARMSubtarget &STI,
71                              const ARMRegisterBankInfo &RBI) {
72   return new ARMInstructionSelector(TM, STI, RBI);
73 }
74 }
75 
76 unsigned zero_reg = 0;
77 
78 #define GET_GLOBALISEL_IMPL
79 #include "ARMGenGlobalISel.inc"
80 #undef GET_GLOBALISEL_IMPL
81 
82 ARMInstructionSelector::ARMInstructionSelector(const ARMBaseTargetMachine &TM,
83                                                const ARMSubtarget &STI,
84                                                const ARMRegisterBankInfo &RBI)
85     : InstructionSelector(), TII(*STI.getInstrInfo()),
86       TRI(*STI.getRegisterInfo()), TM(TM), RBI(RBI), STI(STI),
87 #define GET_GLOBALISEL_PREDICATES_INIT
88 #include "ARMGenGlobalISel.inc"
89 #undef GET_GLOBALISEL_PREDICATES_INIT
90 #define GET_GLOBALISEL_TEMPORARIES_INIT
91 #include "ARMGenGlobalISel.inc"
92 #undef GET_GLOBALISEL_TEMPORARIES_INIT
93 {
94 }
95 
96 static bool selectCopy(MachineInstr &I, const TargetInstrInfo &TII,
97                        MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
98                        const RegisterBankInfo &RBI) {
99   unsigned DstReg = I.getOperand(0).getReg();
100   if (TargetRegisterInfo::isPhysicalRegister(DstReg))
101     return true;
102 
103   const RegisterBank *RegBank = RBI.getRegBank(DstReg, MRI, TRI);
104   (void)RegBank;
105   assert(RegBank && "Can't get reg bank for virtual register");
106 
107   const unsigned DstSize = MRI.getType(DstReg).getSizeInBits();
108   assert((RegBank->getID() == ARM::GPRRegBankID ||
109           RegBank->getID() == ARM::FPRRegBankID) &&
110          "Unsupported reg bank");
111 
112   const TargetRegisterClass *RC = &ARM::GPRRegClass;
113 
114   if (RegBank->getID() == ARM::FPRRegBankID) {
115     if (DstSize == 32)
116       RC = &ARM::SPRRegClass;
117     else if (DstSize == 64)
118       RC = &ARM::DPRRegClass;
119     else
120       llvm_unreachable("Unsupported destination size");
121   }
122 
123   // No need to constrain SrcReg. It will get constrained when
124   // we hit another of its uses or its defs.
125   // Copies do not have constraints.
126   if (!RBI.constrainGenericRegister(DstReg, *RC, MRI)) {
127     DEBUG(dbgs() << "Failed to constrain " << TII.getName(I.getOpcode())
128                  << " operand\n");
129     return false;
130   }
131   return true;
132 }
133 
134 static bool selectMergeValues(MachineInstrBuilder &MIB,
135                               const ARMBaseInstrInfo &TII,
136                               MachineRegisterInfo &MRI,
137                               const TargetRegisterInfo &TRI,
138                               const RegisterBankInfo &RBI) {
139   assert(TII.getSubtarget().hasVFP2() && "Can't select merge without VFP");
140 
141   // We only support G_MERGE_VALUES as a way to stick together two scalar GPRs
142   // into one DPR.
143   unsigned VReg0 = MIB->getOperand(0).getReg();
144   (void)VReg0;
145   assert(MRI.getType(VReg0).getSizeInBits() == 64 &&
146          RBI.getRegBank(VReg0, MRI, TRI)->getID() == ARM::FPRRegBankID &&
147          "Unsupported operand for G_MERGE_VALUES");
148   unsigned VReg1 = MIB->getOperand(1).getReg();
149   (void)VReg1;
150   assert(MRI.getType(VReg1).getSizeInBits() == 32 &&
151          RBI.getRegBank(VReg1, MRI, TRI)->getID() == ARM::GPRRegBankID &&
152          "Unsupported operand for G_MERGE_VALUES");
153   unsigned VReg2 = MIB->getOperand(2).getReg();
154   (void)VReg2;
155   assert(MRI.getType(VReg2).getSizeInBits() == 32 &&
156          RBI.getRegBank(VReg2, MRI, TRI)->getID() == ARM::GPRRegBankID &&
157          "Unsupported operand for G_MERGE_VALUES");
158 
159   MIB->setDesc(TII.get(ARM::VMOVDRR));
160   MIB.add(predOps(ARMCC::AL));
161 
162   return true;
163 }
164 
165 static bool selectUnmergeValues(MachineInstrBuilder &MIB,
166                                 const ARMBaseInstrInfo &TII,
167                                 MachineRegisterInfo &MRI,
168                                 const TargetRegisterInfo &TRI,
169                                 const RegisterBankInfo &RBI) {
170   assert(TII.getSubtarget().hasVFP2() && "Can't select unmerge without VFP");
171 
172   // We only support G_UNMERGE_VALUES as a way to break up one DPR into two
173   // GPRs.
174   unsigned VReg0 = MIB->getOperand(0).getReg();
175   (void)VReg0;
176   assert(MRI.getType(VReg0).getSizeInBits() == 32 &&
177          RBI.getRegBank(VReg0, MRI, TRI)->getID() == ARM::GPRRegBankID &&
178          "Unsupported operand for G_UNMERGE_VALUES");
179   unsigned VReg1 = MIB->getOperand(1).getReg();
180   (void)VReg1;
181   assert(MRI.getType(VReg1).getSizeInBits() == 32 &&
182          RBI.getRegBank(VReg1, MRI, TRI)->getID() == ARM::GPRRegBankID &&
183          "Unsupported operand for G_UNMERGE_VALUES");
184   unsigned VReg2 = MIB->getOperand(2).getReg();
185   (void)VReg2;
186   assert(MRI.getType(VReg2).getSizeInBits() == 64 &&
187          RBI.getRegBank(VReg2, MRI, TRI)->getID() == ARM::FPRRegBankID &&
188          "Unsupported operand for G_UNMERGE_VALUES");
189 
190   MIB->setDesc(TII.get(ARM::VMOVRRD));
191   MIB.add(predOps(ARMCC::AL));
192 
193   return true;
194 }
195 
196 /// Select the opcode for simple extensions (that translate to a single SXT/UXT
197 /// instruction). Extension operations more complicated than that should not
198 /// invoke this. Returns the original opcode if it doesn't know how to select a
199 /// better one.
200 static unsigned selectSimpleExtOpc(unsigned Opc, unsigned Size) {
201   using namespace TargetOpcode;
202 
203   if (Size != 8 && Size != 16)
204     return Opc;
205 
206   if (Opc == G_SEXT)
207     return Size == 8 ? ARM::SXTB : ARM::SXTH;
208 
209   if (Opc == G_ZEXT)
210     return Size == 8 ? ARM::UXTB : ARM::UXTH;
211 
212   return Opc;
213 }
214 
215 /// Select the opcode for simple loads and stores. For types smaller than 32
216 /// bits, the value will be zero extended. Returns the original opcode if it
217 /// doesn't know how to select a better one.
218 static unsigned selectLoadStoreOpCode(unsigned Opc, unsigned RegBank,
219                                       unsigned Size) {
220   bool isStore = Opc == TargetOpcode::G_STORE;
221 
222   if (RegBank == ARM::GPRRegBankID) {
223     switch (Size) {
224     case 1:
225     case 8:
226       return isStore ? ARM::STRBi12 : ARM::LDRBi12;
227     case 16:
228       return isStore ? ARM::STRH : ARM::LDRH;
229     case 32:
230       return isStore ? ARM::STRi12 : ARM::LDRi12;
231     default:
232       return Opc;
233     }
234   }
235 
236   if (RegBank == ARM::FPRRegBankID) {
237     switch (Size) {
238     case 32:
239       return isStore ? ARM::VSTRS : ARM::VLDRS;
240     case 64:
241       return isStore ? ARM::VSTRD : ARM::VLDRD;
242     default:
243       return Opc;
244     }
245   }
246 
247   return Opc;
248 }
249 
250 static ARMCC::CondCodes getComparePred(CmpInst::Predicate Pred) {
251   switch (Pred) {
252   // Needs two compares...
253   case CmpInst::FCMP_ONE:
254   case CmpInst::FCMP_UEQ:
255   default:
256     // AL is our "false" for now. The other two need more compares.
257     return ARMCC::AL;
258   case CmpInst::ICMP_EQ:
259   case CmpInst::FCMP_OEQ:
260     return ARMCC::EQ;
261   case CmpInst::ICMP_SGT:
262   case CmpInst::FCMP_OGT:
263     return ARMCC::GT;
264   case CmpInst::ICMP_SGE:
265   case CmpInst::FCMP_OGE:
266     return ARMCC::GE;
267   case CmpInst::ICMP_UGT:
268   case CmpInst::FCMP_UGT:
269     return ARMCC::HI;
270   case CmpInst::FCMP_OLT:
271     return ARMCC::MI;
272   case CmpInst::ICMP_ULE:
273   case CmpInst::FCMP_OLE:
274     return ARMCC::LS;
275   case CmpInst::FCMP_ORD:
276     return ARMCC::VC;
277   case CmpInst::FCMP_UNO:
278     return ARMCC::VS;
279   case CmpInst::FCMP_UGE:
280     return ARMCC::PL;
281   case CmpInst::ICMP_SLT:
282   case CmpInst::FCMP_ULT:
283     return ARMCC::LT;
284   case CmpInst::ICMP_SLE:
285   case CmpInst::FCMP_ULE:
286     return ARMCC::LE;
287   case CmpInst::FCMP_UNE:
288   case CmpInst::ICMP_NE:
289     return ARMCC::NE;
290   case CmpInst::ICMP_UGE:
291     return ARMCC::HS;
292   case CmpInst::ICMP_ULT:
293     return ARMCC::LO;
294   }
295 }
296 
297 bool ARMInstructionSelector::selectICmp(MachineInstrBuilder &MIB,
298                                         const ARMBaseInstrInfo &TII,
299                                         MachineRegisterInfo &MRI,
300                                         const TargetRegisterInfo &TRI,
301                                         const RegisterBankInfo &RBI) const {
302   auto &MBB = *MIB->getParent();
303   auto InsertBefore = std::next(MIB->getIterator());
304   auto &DebugLoc = MIB->getDebugLoc();
305 
306   // Move 0 into the result register.
307   auto Mov0I = BuildMI(MBB, InsertBefore, DebugLoc, TII.get(ARM::MOVi))
308                    .addDef(MRI.createVirtualRegister(&ARM::GPRRegClass))
309                    .addImm(0)
310                    .add(predOps(ARMCC::AL))
311                    .add(condCodeOp());
312   if (!constrainSelectedInstRegOperands(*Mov0I, TII, TRI, RBI))
313     return false;
314 
315   // Perform the comparison.
316   auto LHSReg = MIB->getOperand(2).getReg();
317   auto RHSReg = MIB->getOperand(3).getReg();
318   assert(MRI.getType(LHSReg) == MRI.getType(RHSReg) &&
319          MRI.getType(LHSReg).getSizeInBits() == 32 &&
320          MRI.getType(RHSReg).getSizeInBits() == 32 &&
321          "Unsupported types for comparison operation");
322   auto CmpI = BuildMI(MBB, InsertBefore, DebugLoc, TII.get(ARM::CMPrr))
323                   .addUse(LHSReg)
324                   .addUse(RHSReg)
325                   .add(predOps(ARMCC::AL));
326   if (!constrainSelectedInstRegOperands(*CmpI, TII, TRI, RBI))
327     return false;
328 
329   // Move 1 into the result register if the flags say so.
330   auto ResReg = MIB->getOperand(0).getReg();
331   auto Cond =
332       static_cast<CmpInst::Predicate>(MIB->getOperand(1).getPredicate());
333   auto ARMCond = getComparePred(Cond);
334   if (ARMCond == ARMCC::AL)
335     return false;
336 
337   auto Mov1I = BuildMI(MBB, InsertBefore, DebugLoc, TII.get(ARM::MOVCCi))
338                    .addDef(ResReg)
339                    .addUse(Mov0I->getOperand(0).getReg())
340                    .addImm(1)
341                    .add(predOps(ARMCond, ARM::CPSR));
342   if (!constrainSelectedInstRegOperands(*Mov1I, TII, TRI, RBI))
343     return false;
344 
345   MIB->eraseFromParent();
346   return true;
347 }
348 
349 bool ARMInstructionSelector::select(MachineInstr &I) const {
350   assert(I.getParent() && "Instruction should be in a basic block!");
351   assert(I.getParent()->getParent() && "Instruction should be in a function!");
352 
353   auto &MBB = *I.getParent();
354   auto &MF = *MBB.getParent();
355   auto &MRI = MF.getRegInfo();
356 
357   if (!isPreISelGenericOpcode(I.getOpcode())) {
358     if (I.isCopy())
359       return selectCopy(I, TII, MRI, TRI, RBI);
360 
361     return true;
362   }
363 
364   if (selectImpl(I))
365     return true;
366 
367   MachineInstrBuilder MIB{MF, I};
368   bool isSExt = false;
369 
370   using namespace TargetOpcode;
371   switch (I.getOpcode()) {
372   case G_SEXT:
373     isSExt = true;
374     LLVM_FALLTHROUGH;
375   case G_ZEXT: {
376     LLT DstTy = MRI.getType(I.getOperand(0).getReg());
377     // FIXME: Smaller destination sizes coming soon!
378     if (DstTy.getSizeInBits() != 32) {
379       DEBUG(dbgs() << "Unsupported destination size for extension");
380       return false;
381     }
382 
383     LLT SrcTy = MRI.getType(I.getOperand(1).getReg());
384     unsigned SrcSize = SrcTy.getSizeInBits();
385     switch (SrcSize) {
386     case 1: {
387       // ZExt boils down to & 0x1; for SExt we also subtract that from 0
388       I.setDesc(TII.get(ARM::ANDri));
389       MIB.addImm(1).add(predOps(ARMCC::AL)).add(condCodeOp());
390 
391       if (isSExt) {
392         unsigned SExtResult = I.getOperand(0).getReg();
393 
394         // Use a new virtual register for the result of the AND
395         unsigned AndResult = MRI.createVirtualRegister(&ARM::GPRRegClass);
396         I.getOperand(0).setReg(AndResult);
397 
398         auto InsertBefore = std::next(I.getIterator());
399         auto SubI =
400             BuildMI(MBB, InsertBefore, I.getDebugLoc(), TII.get(ARM::RSBri))
401                 .addDef(SExtResult)
402                 .addUse(AndResult)
403                 .addImm(0)
404                 .add(predOps(ARMCC::AL))
405                 .add(condCodeOp());
406         if (!constrainSelectedInstRegOperands(*SubI, TII, TRI, RBI))
407           return false;
408       }
409       break;
410     }
411     case 8:
412     case 16: {
413       unsigned NewOpc = selectSimpleExtOpc(I.getOpcode(), SrcSize);
414       if (NewOpc == I.getOpcode())
415         return false;
416       I.setDesc(TII.get(NewOpc));
417       MIB.addImm(0).add(predOps(ARMCC::AL));
418       break;
419     }
420     default:
421       DEBUG(dbgs() << "Unsupported source size for extension");
422       return false;
423     }
424     break;
425   }
426   case G_ANYEXT:
427   case G_TRUNC: {
428     // The high bits are undefined, so there's nothing special to do, just
429     // treat it as a copy.
430     auto SrcReg = I.getOperand(1).getReg();
431     auto DstReg = I.getOperand(0).getReg();
432 
433     const auto &SrcRegBank = *RBI.getRegBank(SrcReg, MRI, TRI);
434     const auto &DstRegBank = *RBI.getRegBank(DstReg, MRI, TRI);
435 
436     if (SrcRegBank.getID() != DstRegBank.getID()) {
437       DEBUG(dbgs() << "G_TRUNC/G_ANYEXT operands on different register banks\n");
438       return false;
439     }
440 
441     if (SrcRegBank.getID() != ARM::GPRRegBankID) {
442       DEBUG(dbgs() << "G_TRUNC/G_ANYEXT on non-GPR not supported yet\n");
443       return false;
444     }
445 
446     I.setDesc(TII.get(COPY));
447     return selectCopy(I, TII, MRI, TRI, RBI);
448   }
449   case G_ICMP:
450     return selectICmp(MIB, TII, MRI, TRI, RBI);
451   case G_GEP:
452     I.setDesc(TII.get(ARM::ADDrr));
453     MIB.add(predOps(ARMCC::AL)).add(condCodeOp());
454     break;
455   case G_FRAME_INDEX:
456     // Add 0 to the given frame index and hope it will eventually be folded into
457     // the user(s).
458     I.setDesc(TII.get(ARM::ADDri));
459     MIB.addImm(0).add(predOps(ARMCC::AL)).add(condCodeOp());
460     break;
461   case G_CONSTANT: {
462     unsigned Reg = I.getOperand(0).getReg();
463     if (MRI.getType(Reg).getSizeInBits() != 32)
464       return false;
465 
466     assert(RBI.getRegBank(Reg, MRI, TRI)->getID() == ARM::GPRRegBankID &&
467            "Expected constant to live in a GPR");
468     I.setDesc(TII.get(ARM::MOVi));
469     MIB.add(predOps(ARMCC::AL)).add(condCodeOp());
470 
471     auto &Val = I.getOperand(1);
472     if (Val.isCImm()) {
473       if (Val.getCImm()->getBitWidth() > 32)
474         return false;
475       Val.ChangeToImmediate(Val.getCImm()->getZExtValue());
476     }
477 
478     if (!Val.isImm()) {
479       return false;
480     }
481 
482     break;
483   }
484   case G_STORE:
485   case G_LOAD: {
486     const auto &MemOp = **I.memoperands_begin();
487     if (MemOp.getOrdering() != AtomicOrdering::NotAtomic) {
488       DEBUG(dbgs() << "Atomic load/store not supported yet\n");
489       return false;
490     }
491 
492     unsigned Reg = I.getOperand(0).getReg();
493     unsigned RegBank = RBI.getRegBank(Reg, MRI, TRI)->getID();
494 
495     LLT ValTy = MRI.getType(Reg);
496     const auto ValSize = ValTy.getSizeInBits();
497 
498     assert((ValSize != 64 || TII.getSubtarget().hasVFP2()) &&
499            "Don't know how to load/store 64-bit value without VFP");
500 
501     const auto NewOpc = selectLoadStoreOpCode(I.getOpcode(), RegBank, ValSize);
502     if (NewOpc == G_LOAD || NewOpc == G_STORE)
503       return false;
504 
505     I.setDesc(TII.get(NewOpc));
506 
507     if (NewOpc == ARM::LDRH || NewOpc == ARM::STRH)
508       // LDRH has a funny addressing mode (there's already a FIXME for it).
509       MIB.addReg(0);
510     MIB.addImm(0).add(predOps(ARMCC::AL));
511     break;
512   }
513   case G_MERGE_VALUES: {
514     if (!selectMergeValues(MIB, TII, MRI, TRI, RBI))
515       return false;
516     break;
517   }
518   case G_UNMERGE_VALUES: {
519     if (!selectUnmergeValues(MIB, TII, MRI, TRI, RBI))
520       return false;
521     break;
522   }
523   default:
524     return false;
525   }
526 
527   return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
528 }
529