1 //===- X86InstructionSelector.cpp -----------------------------------------===//
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
11 /// X86.
12 /// \todo This should be generated by TableGen.
13 //===----------------------------------------------------------------------===//
14 
15 #include "MCTargetDesc/X86BaseInfo.h"
16 #include "X86InstrBuilder.h"
17 #include "X86InstrInfo.h"
18 #include "X86RegisterBankInfo.h"
19 #include "X86RegisterInfo.h"
20 #include "X86Subtarget.h"
21 #include "X86TargetMachine.h"
22 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
23 #include "llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h"
24 #include "llvm/CodeGen/GlobalISel/RegisterBank.h"
25 #include "llvm/CodeGen/GlobalISel/Utils.h"
26 #include "llvm/CodeGen/MachineBasicBlock.h"
27 #include "llvm/CodeGen/MachineConstantPool.h"
28 #include "llvm/CodeGen/MachineFunction.h"
29 #include "llvm/CodeGen/MachineInstr.h"
30 #include "llvm/CodeGen/MachineInstrBuilder.h"
31 #include "llvm/CodeGen/MachineMemOperand.h"
32 #include "llvm/CodeGen/MachineOperand.h"
33 #include "llvm/CodeGen/MachineRegisterInfo.h"
34 #include "llvm/CodeGen/TargetOpcodes.h"
35 #include "llvm/CodeGen/TargetRegisterInfo.h"
36 #include "llvm/IR/DataLayout.h"
37 #include "llvm/IR/InstrTypes.h"
38 #include "llvm/Support/AtomicOrdering.h"
39 #include "llvm/Support/CodeGen.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/ErrorHandling.h"
42 #include "llvm/Support/LowLevelTypeImpl.h"
43 #include "llvm/Support/MathExtras.h"
44 #include "llvm/Support/raw_ostream.h"
45 #include <cassert>
46 #include <cstdint>
47 #include <tuple>
48 
49 #define DEBUG_TYPE "X86-isel"
50 
51 using namespace llvm;
52 
53 namespace {
54 
55 #define GET_GLOBALISEL_PREDICATE_BITSET
56 #include "X86GenGlobalISel.inc"
57 #undef GET_GLOBALISEL_PREDICATE_BITSET
58 
59 class X86InstructionSelector : public InstructionSelector {
60 public:
61   X86InstructionSelector(const X86TargetMachine &TM, const X86Subtarget &STI,
62                          const X86RegisterBankInfo &RBI);
63 
64   bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const override;
65   static const char *getName() { return DEBUG_TYPE; }
66 
67 private:
68   /// tblgen-erated 'select' implementation, used as the initial selector for
69   /// the patterns that don't require complex C++.
70   bool selectImpl(MachineInstr &I, CodeGenCoverage &CoverageInfo) const;
71 
72   // TODO: remove after supported by Tablegen-erated instruction selection.
73   unsigned getLoadStoreOp(const LLT &Ty, const RegisterBank &RB, unsigned Opc,
74                           uint64_t Alignment) const;
75 
76   bool selectLoadStoreOp(MachineInstr &I, MachineRegisterInfo &MRI,
77                          MachineFunction &MF) const;
78   bool selectFrameIndexOrGep(MachineInstr &I, MachineRegisterInfo &MRI,
79                              MachineFunction &MF) const;
80   bool selectGlobalValue(MachineInstr &I, MachineRegisterInfo &MRI,
81                          MachineFunction &MF) const;
82   bool selectConstant(MachineInstr &I, MachineRegisterInfo &MRI,
83                       MachineFunction &MF) const;
84   bool selectTruncOrPtrToInt(MachineInstr &I, MachineRegisterInfo &MRI,
85                              MachineFunction &MF) const;
86   bool selectZext(MachineInstr &I, MachineRegisterInfo &MRI,
87                   MachineFunction &MF) const;
88   bool selectAnyext(MachineInstr &I, MachineRegisterInfo &MRI,
89                     MachineFunction &MF) const;
90   bool selectCmp(MachineInstr &I, MachineRegisterInfo &MRI,
91                  MachineFunction &MF) const;
92   bool selectFCmp(MachineInstr &I, MachineRegisterInfo &MRI,
93                   MachineFunction &MF) const;
94   bool selectUadde(MachineInstr &I, MachineRegisterInfo &MRI,
95                    MachineFunction &MF) const;
96   bool selectCopy(MachineInstr &I, MachineRegisterInfo &MRI) const;
97   bool selectUnmergeValues(MachineInstr &I, MachineRegisterInfo &MRI,
98                            MachineFunction &MF,
99                            CodeGenCoverage &CoverageInfo) const;
100   bool selectMergeValues(MachineInstr &I, MachineRegisterInfo &MRI,
101                          MachineFunction &MF,
102                          CodeGenCoverage &CoverageInfo) const;
103   bool selectInsert(MachineInstr &I, MachineRegisterInfo &MRI,
104                     MachineFunction &MF) const;
105   bool selectExtract(MachineInstr &I, MachineRegisterInfo &MRI,
106                      MachineFunction &MF) const;
107   bool selectCondBranch(MachineInstr &I, MachineRegisterInfo &MRI,
108                         MachineFunction &MF) const;
109   bool selectTurnIntoCOPY(MachineInstr &I, MachineRegisterInfo &MRI,
110                           const unsigned DstReg,
111                           const TargetRegisterClass *DstRC,
112                           const unsigned SrcReg,
113                           const TargetRegisterClass *SrcRC) const;
114   bool materializeFP(MachineInstr &I, MachineRegisterInfo &MRI,
115                      MachineFunction &MF) const;
116   bool selectImplicitDefOrPHI(MachineInstr &I, MachineRegisterInfo &MRI) const;
117   bool selectShift(MachineInstr &I, MachineRegisterInfo &MRI,
118                    MachineFunction &MF) const;
119   bool selectDivRem(MachineInstr &I, MachineRegisterInfo &MRI,
120                     MachineFunction &MF) const;
121   bool selectIntrinsicWSideEffects(MachineInstr &I, MachineRegisterInfo &MRI,
122                                    MachineFunction &MF) const;
123 
124   // emit insert subreg instruction and insert it before MachineInstr &I
125   bool emitInsertSubreg(unsigned DstReg, unsigned SrcReg, MachineInstr &I,
126                         MachineRegisterInfo &MRI, MachineFunction &MF) const;
127   // emit extract subreg instruction and insert it before MachineInstr &I
128   bool emitExtractSubreg(unsigned DstReg, unsigned SrcReg, MachineInstr &I,
129                          MachineRegisterInfo &MRI, MachineFunction &MF) const;
130 
131   const TargetRegisterClass *getRegClass(LLT Ty, const RegisterBank &RB) const;
132   const TargetRegisterClass *getRegClass(LLT Ty, unsigned Reg,
133                                          MachineRegisterInfo &MRI) const;
134 
135   const X86TargetMachine &TM;
136   const X86Subtarget &STI;
137   const X86InstrInfo &TII;
138   const X86RegisterInfo &TRI;
139   const X86RegisterBankInfo &RBI;
140 
141 #define GET_GLOBALISEL_PREDICATES_DECL
142 #include "X86GenGlobalISel.inc"
143 #undef GET_GLOBALISEL_PREDICATES_DECL
144 
145 #define GET_GLOBALISEL_TEMPORARIES_DECL
146 #include "X86GenGlobalISel.inc"
147 #undef GET_GLOBALISEL_TEMPORARIES_DECL
148 };
149 
150 } // end anonymous namespace
151 
152 #define GET_GLOBALISEL_IMPL
153 #include "X86GenGlobalISel.inc"
154 #undef GET_GLOBALISEL_IMPL
155 
156 X86InstructionSelector::X86InstructionSelector(const X86TargetMachine &TM,
157                                                const X86Subtarget &STI,
158                                                const X86RegisterBankInfo &RBI)
159     : InstructionSelector(), TM(TM), STI(STI), TII(*STI.getInstrInfo()),
160       TRI(*STI.getRegisterInfo()), RBI(RBI),
161 #define GET_GLOBALISEL_PREDICATES_INIT
162 #include "X86GenGlobalISel.inc"
163 #undef GET_GLOBALISEL_PREDICATES_INIT
164 #define GET_GLOBALISEL_TEMPORARIES_INIT
165 #include "X86GenGlobalISel.inc"
166 #undef GET_GLOBALISEL_TEMPORARIES_INIT
167 {
168 }
169 
170 // FIXME: This should be target-independent, inferred from the types declared
171 // for each class in the bank.
172 const TargetRegisterClass *
173 X86InstructionSelector::getRegClass(LLT Ty, const RegisterBank &RB) const {
174   if (RB.getID() == X86::GPRRegBankID) {
175     if (Ty.getSizeInBits() <= 8)
176       return &X86::GR8RegClass;
177     if (Ty.getSizeInBits() == 16)
178       return &X86::GR16RegClass;
179     if (Ty.getSizeInBits() == 32)
180       return &X86::GR32RegClass;
181     if (Ty.getSizeInBits() == 64)
182       return &X86::GR64RegClass;
183   }
184   if (RB.getID() == X86::VECRRegBankID) {
185     if (Ty.getSizeInBits() == 32)
186       return STI.hasAVX512() ? &X86::FR32XRegClass : &X86::FR32RegClass;
187     if (Ty.getSizeInBits() == 64)
188       return STI.hasAVX512() ? &X86::FR64XRegClass : &X86::FR64RegClass;
189     if (Ty.getSizeInBits() == 128)
190       return STI.hasAVX512() ? &X86::VR128XRegClass : &X86::VR128RegClass;
191     if (Ty.getSizeInBits() == 256)
192       return STI.hasAVX512() ? &X86::VR256XRegClass : &X86::VR256RegClass;
193     if (Ty.getSizeInBits() == 512)
194       return &X86::VR512RegClass;
195   }
196 
197   llvm_unreachable("Unknown RegBank!");
198 }
199 
200 const TargetRegisterClass *
201 X86InstructionSelector::getRegClass(LLT Ty, unsigned Reg,
202                                     MachineRegisterInfo &MRI) const {
203   const RegisterBank &RegBank = *RBI.getRegBank(Reg, MRI, TRI);
204   return getRegClass(Ty, RegBank);
205 }
206 
207 static unsigned getSubRegIndex(const TargetRegisterClass *RC) {
208   unsigned SubIdx = X86::NoSubRegister;
209   if (RC == &X86::GR32RegClass) {
210     SubIdx = X86::sub_32bit;
211   } else if (RC == &X86::GR16RegClass) {
212     SubIdx = X86::sub_16bit;
213   } else if (RC == &X86::GR8RegClass) {
214     SubIdx = X86::sub_8bit;
215   }
216 
217   return SubIdx;
218 }
219 
220 static const TargetRegisterClass *getRegClassFromGRPhysReg(unsigned Reg) {
221   assert(TargetRegisterInfo::isPhysicalRegister(Reg));
222   if (X86::GR64RegClass.contains(Reg))
223     return &X86::GR64RegClass;
224   if (X86::GR32RegClass.contains(Reg))
225     return &X86::GR32RegClass;
226   if (X86::GR16RegClass.contains(Reg))
227     return &X86::GR16RegClass;
228   if (X86::GR8RegClass.contains(Reg))
229     return &X86::GR8RegClass;
230 
231   llvm_unreachable("Unknown RegClass for PhysReg!");
232 }
233 
234 // Set X86 Opcode and constrain DestReg.
235 bool X86InstructionSelector::selectCopy(MachineInstr &I,
236                                         MachineRegisterInfo &MRI) const {
237   unsigned DstReg = I.getOperand(0).getReg();
238   const unsigned DstSize = RBI.getSizeInBits(DstReg, MRI, TRI);
239   const RegisterBank &DstRegBank = *RBI.getRegBank(DstReg, MRI, TRI);
240 
241   unsigned SrcReg = I.getOperand(1).getReg();
242   const unsigned SrcSize = RBI.getSizeInBits(SrcReg, MRI, TRI);
243   const RegisterBank &SrcRegBank = *RBI.getRegBank(SrcReg, MRI, TRI);
244 
245   if (TargetRegisterInfo::isPhysicalRegister(DstReg)) {
246     assert(I.isCopy() && "Generic operators do not allow physical registers");
247 
248     if (DstSize > SrcSize && SrcRegBank.getID() == X86::GPRRegBankID &&
249         DstRegBank.getID() == X86::GPRRegBankID) {
250 
251       const TargetRegisterClass *SrcRC =
252           getRegClass(MRI.getType(SrcReg), SrcRegBank);
253       const TargetRegisterClass *DstRC = getRegClassFromGRPhysReg(DstReg);
254 
255       if (SrcRC != DstRC) {
256         // This case can be generated by ABI lowering, performe anyext
257         unsigned ExtSrc = MRI.createVirtualRegister(DstRC);
258         BuildMI(*I.getParent(), I, I.getDebugLoc(),
259                 TII.get(TargetOpcode::SUBREG_TO_REG))
260             .addDef(ExtSrc)
261             .addImm(0)
262             .addReg(SrcReg)
263             .addImm(getSubRegIndex(SrcRC));
264 
265         I.getOperand(1).setReg(ExtSrc);
266       }
267     }
268 
269     return true;
270   }
271 
272   assert((!TargetRegisterInfo::isPhysicalRegister(SrcReg) || I.isCopy()) &&
273          "No phys reg on generic operators");
274   assert((DstSize == SrcSize ||
275           // Copies are a mean to setup initial types, the number of
276           // bits may not exactly match.
277           (TargetRegisterInfo::isPhysicalRegister(SrcReg) &&
278            DstSize <= RBI.getSizeInBits(SrcReg, MRI, TRI))) &&
279          "Copy with different width?!");
280 
281   const TargetRegisterClass *DstRC =
282       getRegClass(MRI.getType(DstReg), DstRegBank);
283 
284   if (SrcRegBank.getID() == X86::GPRRegBankID &&
285       DstRegBank.getID() == X86::GPRRegBankID && SrcSize > DstSize &&
286       TargetRegisterInfo::isPhysicalRegister(SrcReg)) {
287     // Change the physical register to performe truncate.
288 
289     const TargetRegisterClass *SrcRC = getRegClassFromGRPhysReg(SrcReg);
290 
291     if (DstRC != SrcRC) {
292       I.getOperand(1).setSubReg(getSubRegIndex(DstRC));
293       I.getOperand(1).substPhysReg(SrcReg, TRI);
294     }
295   }
296 
297   // No need to constrain SrcReg. It will get constrained when
298   // we hit another of its use or its defs.
299   // Copies do not have constraints.
300   const TargetRegisterClass *OldRC = MRI.getRegClassOrNull(DstReg);
301   if (!OldRC || !DstRC->hasSubClassEq(OldRC)) {
302     if (!RBI.constrainGenericRegister(DstReg, *DstRC, MRI)) {
303       LLVM_DEBUG(dbgs() << "Failed to constrain " << TII.getName(I.getOpcode())
304                         << " operand\n");
305       return false;
306     }
307   }
308   I.setDesc(TII.get(X86::COPY));
309   return true;
310 }
311 
312 bool X86InstructionSelector::select(MachineInstr &I,
313                                     CodeGenCoverage &CoverageInfo) const {
314   assert(I.getParent() && "Instruction should be in a basic block!");
315   assert(I.getParent()->getParent() && "Instruction should be in a function!");
316 
317   MachineBasicBlock &MBB = *I.getParent();
318   MachineFunction &MF = *MBB.getParent();
319   MachineRegisterInfo &MRI = MF.getRegInfo();
320 
321   unsigned Opcode = I.getOpcode();
322   if (!isPreISelGenericOpcode(Opcode)) {
323     // Certain non-generic instructions also need some special handling.
324 
325     if (Opcode == TargetOpcode::LOAD_STACK_GUARD)
326       return false;
327 
328     if (I.isCopy())
329       return selectCopy(I, MRI);
330 
331     return true;
332   }
333 
334   assert(I.getNumOperands() == I.getNumExplicitOperands() &&
335          "Generic instruction has unexpected implicit operands\n");
336 
337   if (selectImpl(I, CoverageInfo))
338     return true;
339 
340   LLVM_DEBUG(dbgs() << " C++ instruction selection: "; I.print(dbgs()));
341 
342   // TODO: This should be implemented by tblgen.
343   switch (I.getOpcode()) {
344   default:
345     return false;
346   case TargetOpcode::G_STORE:
347   case TargetOpcode::G_LOAD:
348     return selectLoadStoreOp(I, MRI, MF);
349   case TargetOpcode::G_GEP:
350   case TargetOpcode::G_FRAME_INDEX:
351     return selectFrameIndexOrGep(I, MRI, MF);
352   case TargetOpcode::G_GLOBAL_VALUE:
353     return selectGlobalValue(I, MRI, MF);
354   case TargetOpcode::G_CONSTANT:
355     return selectConstant(I, MRI, MF);
356   case TargetOpcode::G_FCONSTANT:
357     return materializeFP(I, MRI, MF);
358   case TargetOpcode::G_PTRTOINT:
359   case TargetOpcode::G_TRUNC:
360     return selectTruncOrPtrToInt(I, MRI, MF);
361   case TargetOpcode::G_INTTOPTR:
362     return selectCopy(I, MRI);
363   case TargetOpcode::G_ZEXT:
364     return selectZext(I, MRI, MF);
365   case TargetOpcode::G_ANYEXT:
366     return selectAnyext(I, MRI, MF);
367   case TargetOpcode::G_ICMP:
368     return selectCmp(I, MRI, MF);
369   case TargetOpcode::G_FCMP:
370     return selectFCmp(I, MRI, MF);
371   case TargetOpcode::G_UADDE:
372     return selectUadde(I, MRI, MF);
373   case TargetOpcode::G_UNMERGE_VALUES:
374     return selectUnmergeValues(I, MRI, MF, CoverageInfo);
375   case TargetOpcode::G_MERGE_VALUES:
376     return selectMergeValues(I, MRI, MF, CoverageInfo);
377   case TargetOpcode::G_EXTRACT:
378     return selectExtract(I, MRI, MF);
379   case TargetOpcode::G_INSERT:
380     return selectInsert(I, MRI, MF);
381   case TargetOpcode::G_BRCOND:
382     return selectCondBranch(I, MRI, MF);
383   case TargetOpcode::G_IMPLICIT_DEF:
384   case TargetOpcode::G_PHI:
385     return selectImplicitDefOrPHI(I, MRI);
386   case TargetOpcode::G_SHL:
387   case TargetOpcode::G_ASHR:
388   case TargetOpcode::G_LSHR:
389     return selectShift(I, MRI, MF);
390   case TargetOpcode::G_SDIV:
391   case TargetOpcode::G_UDIV:
392   case TargetOpcode::G_SREM:
393   case TargetOpcode::G_UREM:
394     return selectDivRem(I, MRI, MF);
395   case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
396     return selectIntrinsicWSideEffects(I, MRI, MF);
397   }
398 
399   return false;
400 }
401 
402 unsigned X86InstructionSelector::getLoadStoreOp(const LLT &Ty,
403                                                 const RegisterBank &RB,
404                                                 unsigned Opc,
405                                                 uint64_t Alignment) const {
406   bool Isload = (Opc == TargetOpcode::G_LOAD);
407   bool HasAVX = STI.hasAVX();
408   bool HasAVX512 = STI.hasAVX512();
409   bool HasVLX = STI.hasVLX();
410 
411   if (Ty == LLT::scalar(8)) {
412     if (X86::GPRRegBankID == RB.getID())
413       return Isload ? X86::MOV8rm : X86::MOV8mr;
414   } else if (Ty == LLT::scalar(16)) {
415     if (X86::GPRRegBankID == RB.getID())
416       return Isload ? X86::MOV16rm : X86::MOV16mr;
417   } else if (Ty == LLT::scalar(32) || Ty == LLT::pointer(0, 32)) {
418     if (X86::GPRRegBankID == RB.getID())
419       return Isload ? X86::MOV32rm : X86::MOV32mr;
420     if (X86::VECRRegBankID == RB.getID())
421       return Isload ? (HasAVX512 ? X86::VMOVSSZrm
422                                  : HasAVX ? X86::VMOVSSrm : X86::MOVSSrm)
423                     : (HasAVX512 ? X86::VMOVSSZmr
424                                  : HasAVX ? X86::VMOVSSmr : X86::MOVSSmr);
425   } else if (Ty == LLT::scalar(64) || Ty == LLT::pointer(0, 64)) {
426     if (X86::GPRRegBankID == RB.getID())
427       return Isload ? X86::MOV64rm : X86::MOV64mr;
428     if (X86::VECRRegBankID == RB.getID())
429       return Isload ? (HasAVX512 ? X86::VMOVSDZrm
430                                  : HasAVX ? X86::VMOVSDrm : X86::MOVSDrm)
431                     : (HasAVX512 ? X86::VMOVSDZmr
432                                  : HasAVX ? X86::VMOVSDmr : X86::MOVSDmr);
433   } else if (Ty.isVector() && Ty.getSizeInBits() == 128) {
434     if (Alignment >= 16)
435       return Isload ? (HasVLX ? X86::VMOVAPSZ128rm
436                               : HasAVX512
437                                     ? X86::VMOVAPSZ128rm_NOVLX
438                                     : HasAVX ? X86::VMOVAPSrm : X86::MOVAPSrm)
439                     : (HasVLX ? X86::VMOVAPSZ128mr
440                               : HasAVX512
441                                     ? X86::VMOVAPSZ128mr_NOVLX
442                                     : HasAVX ? X86::VMOVAPSmr : X86::MOVAPSmr);
443     else
444       return Isload ? (HasVLX ? X86::VMOVUPSZ128rm
445                               : HasAVX512
446                                     ? X86::VMOVUPSZ128rm_NOVLX
447                                     : HasAVX ? X86::VMOVUPSrm : X86::MOVUPSrm)
448                     : (HasVLX ? X86::VMOVUPSZ128mr
449                               : HasAVX512
450                                     ? X86::VMOVUPSZ128mr_NOVLX
451                                     : HasAVX ? X86::VMOVUPSmr : X86::MOVUPSmr);
452   } else if (Ty.isVector() && Ty.getSizeInBits() == 256) {
453     if (Alignment >= 32)
454       return Isload ? (HasVLX ? X86::VMOVAPSZ256rm
455                               : HasAVX512 ? X86::VMOVAPSZ256rm_NOVLX
456                                           : X86::VMOVAPSYrm)
457                     : (HasVLX ? X86::VMOVAPSZ256mr
458                               : HasAVX512 ? X86::VMOVAPSZ256mr_NOVLX
459                                           : X86::VMOVAPSYmr);
460     else
461       return Isload ? (HasVLX ? X86::VMOVUPSZ256rm
462                               : HasAVX512 ? X86::VMOVUPSZ256rm_NOVLX
463                                           : X86::VMOVUPSYrm)
464                     : (HasVLX ? X86::VMOVUPSZ256mr
465                               : HasAVX512 ? X86::VMOVUPSZ256mr_NOVLX
466                                           : X86::VMOVUPSYmr);
467   } else if (Ty.isVector() && Ty.getSizeInBits() == 512) {
468     if (Alignment >= 64)
469       return Isload ? X86::VMOVAPSZrm : X86::VMOVAPSZmr;
470     else
471       return Isload ? X86::VMOVUPSZrm : X86::VMOVUPSZmr;
472   }
473   return Opc;
474 }
475 
476 // Fill in an address from the given instruction.
477 static void X86SelectAddress(const MachineInstr &I,
478                              const MachineRegisterInfo &MRI,
479                              X86AddressMode &AM) {
480   assert(I.getOperand(0).isReg() && "unsupported opperand.");
481   assert(MRI.getType(I.getOperand(0).getReg()).isPointer() &&
482          "unsupported type.");
483 
484   if (I.getOpcode() == TargetOpcode::G_GEP) {
485     if (auto COff = getConstantVRegVal(I.getOperand(2).getReg(), MRI)) {
486       int64_t Imm = *COff;
487       if (isInt<32>(Imm)) { // Check for displacement overflow.
488         AM.Disp = static_cast<int32_t>(Imm);
489         AM.Base.Reg = I.getOperand(1).getReg();
490         return;
491       }
492     }
493   } else if (I.getOpcode() == TargetOpcode::G_FRAME_INDEX) {
494     AM.Base.FrameIndex = I.getOperand(1).getIndex();
495     AM.BaseType = X86AddressMode::FrameIndexBase;
496     return;
497   }
498 
499   // Default behavior.
500   AM.Base.Reg = I.getOperand(0).getReg();
501 }
502 
503 bool X86InstructionSelector::selectLoadStoreOp(MachineInstr &I,
504                                                MachineRegisterInfo &MRI,
505                                                MachineFunction &MF) const {
506   unsigned Opc = I.getOpcode();
507 
508   assert((Opc == TargetOpcode::G_STORE || Opc == TargetOpcode::G_LOAD) &&
509          "unexpected instruction");
510 
511   const unsigned DefReg = I.getOperand(0).getReg();
512   LLT Ty = MRI.getType(DefReg);
513   const RegisterBank &RB = *RBI.getRegBank(DefReg, MRI, TRI);
514 
515   auto &MemOp = **I.memoperands_begin();
516   if (MemOp.getOrdering() != AtomicOrdering::NotAtomic) {
517     LLVM_DEBUG(dbgs() << "Atomic load/store not supported yet\n");
518     return false;
519   }
520 
521   unsigned NewOpc = getLoadStoreOp(Ty, RB, Opc, MemOp.getAlignment());
522   if (NewOpc == Opc)
523     return false;
524 
525   X86AddressMode AM;
526   X86SelectAddress(*MRI.getVRegDef(I.getOperand(1).getReg()), MRI, AM);
527 
528   I.setDesc(TII.get(NewOpc));
529   MachineInstrBuilder MIB(MF, I);
530   if (Opc == TargetOpcode::G_LOAD) {
531     I.RemoveOperand(1);
532     addFullAddress(MIB, AM);
533   } else {
534     // G_STORE (VAL, Addr), X86Store instruction (Addr, VAL)
535     I.RemoveOperand(1);
536     I.RemoveOperand(0);
537     addFullAddress(MIB, AM).addUse(DefReg);
538   }
539   return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
540 }
541 
542 static unsigned getLeaOP(LLT Ty, const X86Subtarget &STI) {
543   if (Ty == LLT::pointer(0, 64))
544     return X86::LEA64r;
545   else if (Ty == LLT::pointer(0, 32))
546     return STI.isTarget64BitILP32() ? X86::LEA64_32r : X86::LEA32r;
547   else
548     llvm_unreachable("Can't get LEA opcode. Unsupported type.");
549 }
550 
551 bool X86InstructionSelector::selectFrameIndexOrGep(MachineInstr &I,
552                                                    MachineRegisterInfo &MRI,
553                                                    MachineFunction &MF) const {
554   unsigned Opc = I.getOpcode();
555 
556   assert((Opc == TargetOpcode::G_FRAME_INDEX || Opc == TargetOpcode::G_GEP) &&
557          "unexpected instruction");
558 
559   const unsigned DefReg = I.getOperand(0).getReg();
560   LLT Ty = MRI.getType(DefReg);
561 
562   // Use LEA to calculate frame index and GEP
563   unsigned NewOpc = getLeaOP(Ty, STI);
564   I.setDesc(TII.get(NewOpc));
565   MachineInstrBuilder MIB(MF, I);
566 
567   if (Opc == TargetOpcode::G_FRAME_INDEX) {
568     addOffset(MIB, 0);
569   } else {
570     MachineOperand &InxOp = I.getOperand(2);
571     I.addOperand(InxOp);        // set IndexReg
572     InxOp.ChangeToImmediate(1); // set Scale
573     MIB.addImm(0).addReg(0);
574   }
575 
576   return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
577 }
578 
579 bool X86InstructionSelector::selectGlobalValue(MachineInstr &I,
580                                                MachineRegisterInfo &MRI,
581                                                MachineFunction &MF) const {
582   assert((I.getOpcode() == TargetOpcode::G_GLOBAL_VALUE) &&
583          "unexpected instruction");
584 
585   auto GV = I.getOperand(1).getGlobal();
586   if (GV->isThreadLocal()) {
587     return false; // TODO: we don't support TLS yet.
588   }
589 
590   // Can't handle alternate code models yet.
591   if (TM.getCodeModel() != CodeModel::Small)
592     return false;
593 
594   X86AddressMode AM;
595   AM.GV = GV;
596   AM.GVOpFlags = STI.classifyGlobalReference(GV);
597 
598   // TODO: The ABI requires an extra load. not supported yet.
599   if (isGlobalStubReference(AM.GVOpFlags))
600     return false;
601 
602   // TODO: This reference is relative to the pic base. not supported yet.
603   if (isGlobalRelativeToPICBase(AM.GVOpFlags))
604     return false;
605 
606   if (STI.isPICStyleRIPRel()) {
607     // Use rip-relative addressing.
608     assert(AM.Base.Reg == 0 && AM.IndexReg == 0);
609     AM.Base.Reg = X86::RIP;
610   }
611 
612   const unsigned DefReg = I.getOperand(0).getReg();
613   LLT Ty = MRI.getType(DefReg);
614   unsigned NewOpc = getLeaOP(Ty, STI);
615 
616   I.setDesc(TII.get(NewOpc));
617   MachineInstrBuilder MIB(MF, I);
618 
619   I.RemoveOperand(1);
620   addFullAddress(MIB, AM);
621 
622   return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
623 }
624 
625 bool X86InstructionSelector::selectConstant(MachineInstr &I,
626                                             MachineRegisterInfo &MRI,
627                                             MachineFunction &MF) const {
628   assert((I.getOpcode() == TargetOpcode::G_CONSTANT) &&
629          "unexpected instruction");
630 
631   const unsigned DefReg = I.getOperand(0).getReg();
632   LLT Ty = MRI.getType(DefReg);
633 
634   if (RBI.getRegBank(DefReg, MRI, TRI)->getID() != X86::GPRRegBankID)
635     return false;
636 
637   uint64_t Val = 0;
638   if (I.getOperand(1).isCImm()) {
639     Val = I.getOperand(1).getCImm()->getZExtValue();
640     I.getOperand(1).ChangeToImmediate(Val);
641   } else if (I.getOperand(1).isImm()) {
642     Val = I.getOperand(1).getImm();
643   } else
644     llvm_unreachable("Unsupported operand type.");
645 
646   unsigned NewOpc;
647   switch (Ty.getSizeInBits()) {
648   case 8:
649     NewOpc = X86::MOV8ri;
650     break;
651   case 16:
652     NewOpc = X86::MOV16ri;
653     break;
654   case 32:
655     NewOpc = X86::MOV32ri;
656     break;
657   case 64:
658     // TODO: in case isUInt<32>(Val), X86::MOV32ri can be used
659     if (isInt<32>(Val))
660       NewOpc = X86::MOV64ri32;
661     else
662       NewOpc = X86::MOV64ri;
663     break;
664   default:
665     llvm_unreachable("Can't select G_CONSTANT, unsupported type.");
666   }
667 
668   I.setDesc(TII.get(NewOpc));
669   return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
670 }
671 
672 // Helper function for selectTruncOrPtrToInt and selectAnyext.
673 // Returns true if DstRC lives on a floating register class and
674 // SrcRC lives on a 128-bit vector class.
675 static bool canTurnIntoCOPY(const TargetRegisterClass *DstRC,
676                             const TargetRegisterClass *SrcRC) {
677   return (DstRC == &X86::FR32RegClass || DstRC == &X86::FR32XRegClass ||
678           DstRC == &X86::FR64RegClass || DstRC == &X86::FR64XRegClass) &&
679          (SrcRC == &X86::VR128RegClass || SrcRC == &X86::VR128XRegClass);
680 }
681 
682 bool X86InstructionSelector::selectTurnIntoCOPY(
683     MachineInstr &I, MachineRegisterInfo &MRI, const unsigned DstReg,
684     const TargetRegisterClass *DstRC, const unsigned SrcReg,
685     const TargetRegisterClass *SrcRC) const {
686 
687   if (!RBI.constrainGenericRegister(SrcReg, *SrcRC, MRI) ||
688       !RBI.constrainGenericRegister(DstReg, *DstRC, MRI)) {
689     LLVM_DEBUG(dbgs() << "Failed to constrain " << TII.getName(I.getOpcode())
690                       << " operand\n");
691     return false;
692   }
693   I.setDesc(TII.get(X86::COPY));
694   return true;
695 }
696 
697 bool X86InstructionSelector::selectTruncOrPtrToInt(MachineInstr &I,
698                                                    MachineRegisterInfo &MRI,
699                                                    MachineFunction &MF) const {
700   assert((I.getOpcode() == TargetOpcode::G_TRUNC ||
701           I.getOpcode() == TargetOpcode::G_PTRTOINT) &&
702          "unexpected instruction");
703 
704   const unsigned DstReg = I.getOperand(0).getReg();
705   const unsigned SrcReg = I.getOperand(1).getReg();
706 
707   const LLT DstTy = MRI.getType(DstReg);
708   const LLT SrcTy = MRI.getType(SrcReg);
709 
710   const RegisterBank &DstRB = *RBI.getRegBank(DstReg, MRI, TRI);
711   const RegisterBank &SrcRB = *RBI.getRegBank(SrcReg, MRI, TRI);
712 
713   if (DstRB.getID() != SrcRB.getID()) {
714     LLVM_DEBUG(dbgs() << TII.getName(I.getOpcode())
715                       << " input/output on different banks\n");
716     return false;
717   }
718 
719   const TargetRegisterClass *DstRC = getRegClass(DstTy, DstRB);
720   const TargetRegisterClass *SrcRC = getRegClass(SrcTy, SrcRB);
721 
722   if (!DstRC || !SrcRC)
723     return false;
724 
725   // If that's truncation of the value that lives on the vector class and goes
726   // into the floating class, just replace it with copy, as we are able to
727   // select it as a regular move.
728   if (canTurnIntoCOPY(DstRC, SrcRC))
729     return selectTurnIntoCOPY(I, MRI, DstReg, DstRC, SrcReg, SrcRC);
730 
731   if (DstRB.getID() != X86::GPRRegBankID)
732     return false;
733 
734   unsigned SubIdx;
735   if (DstRC == SrcRC) {
736     // Nothing to be done
737     SubIdx = X86::NoSubRegister;
738   } else if (DstRC == &X86::GR32RegClass) {
739     SubIdx = X86::sub_32bit;
740   } else if (DstRC == &X86::GR16RegClass) {
741     SubIdx = X86::sub_16bit;
742   } else if (DstRC == &X86::GR8RegClass) {
743     SubIdx = X86::sub_8bit;
744   } else {
745     return false;
746   }
747 
748   SrcRC = TRI.getSubClassWithSubReg(SrcRC, SubIdx);
749 
750   if (!RBI.constrainGenericRegister(SrcReg, *SrcRC, MRI) ||
751       !RBI.constrainGenericRegister(DstReg, *DstRC, MRI)) {
752     LLVM_DEBUG(dbgs() << "Failed to constrain " << TII.getName(I.getOpcode())
753                       << "\n");
754     return false;
755   }
756 
757   I.getOperand(1).setSubReg(SubIdx);
758 
759   I.setDesc(TII.get(X86::COPY));
760   return true;
761 }
762 
763 bool X86InstructionSelector::selectZext(MachineInstr &I,
764                                         MachineRegisterInfo &MRI,
765                                         MachineFunction &MF) const {
766   assert((I.getOpcode() == TargetOpcode::G_ZEXT) && "unexpected instruction");
767 
768   const unsigned DstReg = I.getOperand(0).getReg();
769   const unsigned SrcReg = I.getOperand(1).getReg();
770 
771   const LLT DstTy = MRI.getType(DstReg);
772   const LLT SrcTy = MRI.getType(SrcReg);
773 
774   assert(!(SrcTy == LLT::scalar(8) && DstTy == LLT::scalar(32)) &&
775          "8=>32 Zext is handled by tablegen");
776   assert(!(SrcTy == LLT::scalar(16) && DstTy == LLT::scalar(32)) &&
777          "16=>32 Zext is handled by tablegen");
778 
779   const static struct ZextEntry {
780     LLT SrcTy;
781     LLT DstTy;
782     unsigned MovOp;
783     bool NeedSubregToReg;
784   } OpTable[] = {
785       {LLT::scalar(8), LLT::scalar(16), X86::MOVZX16rr8, false},  // i8  => i16
786       {LLT::scalar(8), LLT::scalar(64), X86::MOVZX32rr8, true},   // i8  => i64
787       {LLT::scalar(16), LLT::scalar(64), X86::MOVZX32rr16, true}, // i16 => i64
788       {LLT::scalar(32), LLT::scalar(64), 0, true}                 // i32 => i64
789   };
790 
791   auto ZextEntryIt =
792       std::find_if(std::begin(OpTable), std::end(OpTable),
793                    [SrcTy, DstTy](const ZextEntry &El) {
794                      return El.DstTy == DstTy && El.SrcTy == SrcTy;
795                    });
796 
797   // Here we try to select Zext into a MOVZ and/or SUBREG_TO_REG instruction.
798   if (ZextEntryIt != std::end(OpTable)) {
799     const RegisterBank &DstRB = *RBI.getRegBank(DstReg, MRI, TRI);
800     const RegisterBank &SrcRB = *RBI.getRegBank(SrcReg, MRI, TRI);
801     const TargetRegisterClass *DstRC = getRegClass(DstTy, DstRB);
802     const TargetRegisterClass *SrcRC = getRegClass(SrcTy, SrcRB);
803 
804     if (!RBI.constrainGenericRegister(SrcReg, *SrcRC, MRI) ||
805         !RBI.constrainGenericRegister(DstReg, *DstRC, MRI)) {
806       LLVM_DEBUG(dbgs() << "Failed to constrain " << TII.getName(I.getOpcode())
807                         << " operand\n");
808       return false;
809     }
810 
811     unsigned TransitRegTo = DstReg;
812     unsigned TransitRegFrom = SrcReg;
813     if (ZextEntryIt->MovOp) {
814       // If we select Zext into MOVZ + SUBREG_TO_REG, we need to have
815       // a transit register in between: create it here.
816       if (ZextEntryIt->NeedSubregToReg) {
817         TransitRegFrom = MRI.createVirtualRegister(
818             getRegClass(LLT::scalar(32), DstReg, MRI));
819         TransitRegTo = TransitRegFrom;
820       }
821 
822       BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(ZextEntryIt->MovOp))
823           .addDef(TransitRegTo)
824           .addReg(SrcReg);
825     }
826     if (ZextEntryIt->NeedSubregToReg) {
827       BuildMI(*I.getParent(), I, I.getDebugLoc(),
828               TII.get(TargetOpcode::SUBREG_TO_REG))
829           .addDef(DstReg)
830           .addImm(0)
831           .addReg(TransitRegFrom)
832           .addImm(X86::sub_32bit);
833     }
834     I.eraseFromParent();
835     return true;
836   }
837 
838   if (SrcTy != LLT::scalar(1))
839     return false;
840 
841   unsigned AndOpc;
842   if (DstTy == LLT::scalar(8))
843     AndOpc = X86::AND8ri;
844   else if (DstTy == LLT::scalar(16))
845     AndOpc = X86::AND16ri8;
846   else if (DstTy == LLT::scalar(32))
847     AndOpc = X86::AND32ri8;
848   else if (DstTy == LLT::scalar(64))
849     AndOpc = X86::AND64ri8;
850   else
851     return false;
852 
853   unsigned DefReg = SrcReg;
854   if (DstTy != LLT::scalar(8)) {
855     DefReg = MRI.createVirtualRegister(getRegClass(DstTy, DstReg, MRI));
856     BuildMI(*I.getParent(), I, I.getDebugLoc(),
857             TII.get(TargetOpcode::SUBREG_TO_REG), DefReg)
858         .addImm(0)
859         .addReg(SrcReg)
860         .addImm(X86::sub_8bit);
861   }
862 
863   MachineInstr &AndInst =
864       *BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(AndOpc), DstReg)
865            .addReg(DefReg)
866            .addImm(1);
867 
868   constrainSelectedInstRegOperands(AndInst, TII, TRI, RBI);
869 
870   I.eraseFromParent();
871   return true;
872 }
873 
874 bool X86InstructionSelector::selectAnyext(MachineInstr &I,
875                                           MachineRegisterInfo &MRI,
876                                           MachineFunction &MF) const {
877   assert((I.getOpcode() == TargetOpcode::G_ANYEXT) && "unexpected instruction");
878 
879   const unsigned DstReg = I.getOperand(0).getReg();
880   const unsigned SrcReg = I.getOperand(1).getReg();
881 
882   const LLT DstTy = MRI.getType(DstReg);
883   const LLT SrcTy = MRI.getType(SrcReg);
884 
885   const RegisterBank &DstRB = *RBI.getRegBank(DstReg, MRI, TRI);
886   const RegisterBank &SrcRB = *RBI.getRegBank(SrcReg, MRI, TRI);
887 
888   assert(DstRB.getID() == SrcRB.getID() &&
889          "G_ANYEXT input/output on different banks\n");
890 
891   assert(DstTy.getSizeInBits() > SrcTy.getSizeInBits() &&
892          "G_ANYEXT incorrect operand size");
893 
894   const TargetRegisterClass *DstRC = getRegClass(DstTy, DstRB);
895   const TargetRegisterClass *SrcRC = getRegClass(SrcTy, SrcRB);
896 
897   // If that's ANY_EXT of the value that lives on the floating class and goes
898   // into the vector class, just replace it with copy, as we are able to select
899   // it as a regular move.
900   if (canTurnIntoCOPY(SrcRC, DstRC))
901     return selectTurnIntoCOPY(I, MRI, SrcReg, SrcRC, DstReg, DstRC);
902 
903   if (DstRB.getID() != X86::GPRRegBankID)
904     return false;
905 
906   if (!RBI.constrainGenericRegister(SrcReg, *SrcRC, MRI) ||
907       !RBI.constrainGenericRegister(DstReg, *DstRC, MRI)) {
908     LLVM_DEBUG(dbgs() << "Failed to constrain " << TII.getName(I.getOpcode())
909                       << " operand\n");
910     return false;
911   }
912 
913   if (SrcRC == DstRC) {
914     I.setDesc(TII.get(X86::COPY));
915     return true;
916   }
917 
918   BuildMI(*I.getParent(), I, I.getDebugLoc(),
919           TII.get(TargetOpcode::SUBREG_TO_REG))
920       .addDef(DstReg)
921       .addImm(0)
922       .addReg(SrcReg)
923       .addImm(getSubRegIndex(SrcRC));
924 
925   I.eraseFromParent();
926   return true;
927 }
928 
929 bool X86InstructionSelector::selectCmp(MachineInstr &I,
930                                        MachineRegisterInfo &MRI,
931                                        MachineFunction &MF) const {
932   assert((I.getOpcode() == TargetOpcode::G_ICMP) && "unexpected instruction");
933 
934   X86::CondCode CC;
935   bool SwapArgs;
936   std::tie(CC, SwapArgs) = X86::getX86ConditionCode(
937       (CmpInst::Predicate)I.getOperand(1).getPredicate());
938   unsigned OpSet = X86::getSETFromCond(CC);
939 
940   unsigned LHS = I.getOperand(2).getReg();
941   unsigned RHS = I.getOperand(3).getReg();
942 
943   if (SwapArgs)
944     std::swap(LHS, RHS);
945 
946   unsigned OpCmp;
947   LLT Ty = MRI.getType(LHS);
948 
949   switch (Ty.getSizeInBits()) {
950   default:
951     return false;
952   case 8:
953     OpCmp = X86::CMP8rr;
954     break;
955   case 16:
956     OpCmp = X86::CMP16rr;
957     break;
958   case 32:
959     OpCmp = X86::CMP32rr;
960     break;
961   case 64:
962     OpCmp = X86::CMP64rr;
963     break;
964   }
965 
966   MachineInstr &CmpInst =
967       *BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(OpCmp))
968            .addReg(LHS)
969            .addReg(RHS);
970 
971   MachineInstr &SetInst = *BuildMI(*I.getParent(), I, I.getDebugLoc(),
972                                    TII.get(OpSet), I.getOperand(0).getReg());
973 
974   constrainSelectedInstRegOperands(CmpInst, TII, TRI, RBI);
975   constrainSelectedInstRegOperands(SetInst, TII, TRI, RBI);
976 
977   I.eraseFromParent();
978   return true;
979 }
980 
981 bool X86InstructionSelector::selectFCmp(MachineInstr &I,
982                                         MachineRegisterInfo &MRI,
983                                         MachineFunction &MF) const {
984   assert((I.getOpcode() == TargetOpcode::G_FCMP) && "unexpected instruction");
985 
986   unsigned LhsReg = I.getOperand(2).getReg();
987   unsigned RhsReg = I.getOperand(3).getReg();
988   CmpInst::Predicate Predicate =
989       (CmpInst::Predicate)I.getOperand(1).getPredicate();
990 
991   // FCMP_OEQ and FCMP_UNE cannot be checked with a single instruction.
992   static const uint16_t SETFOpcTable[2][3] = {
993       {X86::SETEr, X86::SETNPr, X86::AND8rr},
994       {X86::SETNEr, X86::SETPr, X86::OR8rr}};
995   const uint16_t *SETFOpc = nullptr;
996   switch (Predicate) {
997   default:
998     break;
999   case CmpInst::FCMP_OEQ:
1000     SETFOpc = &SETFOpcTable[0][0];
1001     break;
1002   case CmpInst::FCMP_UNE:
1003     SETFOpc = &SETFOpcTable[1][0];
1004     break;
1005   }
1006 
1007   // Compute the opcode for the CMP instruction.
1008   unsigned OpCmp;
1009   LLT Ty = MRI.getType(LhsReg);
1010   switch (Ty.getSizeInBits()) {
1011   default:
1012     return false;
1013   case 32:
1014     OpCmp = X86::UCOMISSrr;
1015     break;
1016   case 64:
1017     OpCmp = X86::UCOMISDrr;
1018     break;
1019   }
1020 
1021   unsigned ResultReg = I.getOperand(0).getReg();
1022   RBI.constrainGenericRegister(
1023       ResultReg,
1024       *getRegClass(LLT::scalar(8), *RBI.getRegBank(ResultReg, MRI, TRI)), MRI);
1025   if (SETFOpc) {
1026     MachineInstr &CmpInst =
1027         *BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(OpCmp))
1028              .addReg(LhsReg)
1029              .addReg(RhsReg);
1030 
1031     unsigned FlagReg1 = MRI.createVirtualRegister(&X86::GR8RegClass);
1032     unsigned FlagReg2 = MRI.createVirtualRegister(&X86::GR8RegClass);
1033     MachineInstr &Set1 = *BuildMI(*I.getParent(), I, I.getDebugLoc(),
1034                                   TII.get(SETFOpc[0]), FlagReg1);
1035     MachineInstr &Set2 = *BuildMI(*I.getParent(), I, I.getDebugLoc(),
1036                                   TII.get(SETFOpc[1]), FlagReg2);
1037     MachineInstr &Set3 = *BuildMI(*I.getParent(), I, I.getDebugLoc(),
1038                                   TII.get(SETFOpc[2]), ResultReg)
1039                               .addReg(FlagReg1)
1040                               .addReg(FlagReg2);
1041     constrainSelectedInstRegOperands(CmpInst, TII, TRI, RBI);
1042     constrainSelectedInstRegOperands(Set1, TII, TRI, RBI);
1043     constrainSelectedInstRegOperands(Set2, TII, TRI, RBI);
1044     constrainSelectedInstRegOperands(Set3, TII, TRI, RBI);
1045 
1046     I.eraseFromParent();
1047     return true;
1048   }
1049 
1050   X86::CondCode CC;
1051   bool SwapArgs;
1052   std::tie(CC, SwapArgs) = X86::getX86ConditionCode(Predicate);
1053   assert(CC <= X86::LAST_VALID_COND && "Unexpected condition code.");
1054   unsigned Opc = X86::getSETFromCond(CC);
1055 
1056   if (SwapArgs)
1057     std::swap(LhsReg, RhsReg);
1058 
1059   // Emit a compare of LHS/RHS.
1060   MachineInstr &CmpInst =
1061       *BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(OpCmp))
1062            .addReg(LhsReg)
1063            .addReg(RhsReg);
1064 
1065   MachineInstr &Set =
1066       *BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(Opc), ResultReg);
1067   constrainSelectedInstRegOperands(CmpInst, TII, TRI, RBI);
1068   constrainSelectedInstRegOperands(Set, TII, TRI, RBI);
1069   I.eraseFromParent();
1070   return true;
1071 }
1072 
1073 bool X86InstructionSelector::selectUadde(MachineInstr &I,
1074                                          MachineRegisterInfo &MRI,
1075                                          MachineFunction &MF) const {
1076   assert((I.getOpcode() == TargetOpcode::G_UADDE) && "unexpected instruction");
1077 
1078   const unsigned DstReg = I.getOperand(0).getReg();
1079   const unsigned CarryOutReg = I.getOperand(1).getReg();
1080   const unsigned Op0Reg = I.getOperand(2).getReg();
1081   const unsigned Op1Reg = I.getOperand(3).getReg();
1082   unsigned CarryInReg = I.getOperand(4).getReg();
1083 
1084   const LLT DstTy = MRI.getType(DstReg);
1085 
1086   if (DstTy != LLT::scalar(32))
1087     return false;
1088 
1089   // find CarryIn def instruction.
1090   MachineInstr *Def = MRI.getVRegDef(CarryInReg);
1091   while (Def->getOpcode() == TargetOpcode::G_TRUNC) {
1092     CarryInReg = Def->getOperand(1).getReg();
1093     Def = MRI.getVRegDef(CarryInReg);
1094   }
1095 
1096   unsigned Opcode;
1097   if (Def->getOpcode() == TargetOpcode::G_UADDE) {
1098     // carry set by prev ADD.
1099 
1100     BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(X86::COPY), X86::EFLAGS)
1101         .addReg(CarryInReg);
1102 
1103     if (!RBI.constrainGenericRegister(CarryInReg, X86::GR32RegClass, MRI))
1104       return false;
1105 
1106     Opcode = X86::ADC32rr;
1107   } else if (auto val = getConstantVRegVal(CarryInReg, MRI)) {
1108     // carry is constant, support only 0.
1109     if (*val != 0)
1110       return false;
1111 
1112     Opcode = X86::ADD32rr;
1113   } else
1114     return false;
1115 
1116   MachineInstr &AddInst =
1117       *BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(Opcode), DstReg)
1118            .addReg(Op0Reg)
1119            .addReg(Op1Reg);
1120 
1121   BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(X86::COPY), CarryOutReg)
1122       .addReg(X86::EFLAGS);
1123 
1124   if (!constrainSelectedInstRegOperands(AddInst, TII, TRI, RBI) ||
1125       !RBI.constrainGenericRegister(CarryOutReg, X86::GR32RegClass, MRI))
1126     return false;
1127 
1128   I.eraseFromParent();
1129   return true;
1130 }
1131 
1132 bool X86InstructionSelector::selectExtract(MachineInstr &I,
1133                                            MachineRegisterInfo &MRI,
1134                                            MachineFunction &MF) const {
1135   assert((I.getOpcode() == TargetOpcode::G_EXTRACT) &&
1136          "unexpected instruction");
1137 
1138   const unsigned DstReg = I.getOperand(0).getReg();
1139   const unsigned SrcReg = I.getOperand(1).getReg();
1140   int64_t Index = I.getOperand(2).getImm();
1141 
1142   const LLT DstTy = MRI.getType(DstReg);
1143   const LLT SrcTy = MRI.getType(SrcReg);
1144 
1145   // Meanwile handle vector type only.
1146   if (!DstTy.isVector())
1147     return false;
1148 
1149   if (Index % DstTy.getSizeInBits() != 0)
1150     return false; // Not extract subvector.
1151 
1152   if (Index == 0) {
1153     // Replace by extract subreg copy.
1154     if (!emitExtractSubreg(DstReg, SrcReg, I, MRI, MF))
1155       return false;
1156 
1157     I.eraseFromParent();
1158     return true;
1159   }
1160 
1161   bool HasAVX = STI.hasAVX();
1162   bool HasAVX512 = STI.hasAVX512();
1163   bool HasVLX = STI.hasVLX();
1164 
1165   if (SrcTy.getSizeInBits() == 256 && DstTy.getSizeInBits() == 128) {
1166     if (HasVLX)
1167       I.setDesc(TII.get(X86::VEXTRACTF32x4Z256rr));
1168     else if (HasAVX)
1169       I.setDesc(TII.get(X86::VEXTRACTF128rr));
1170     else
1171       return false;
1172   } else if (SrcTy.getSizeInBits() == 512 && HasAVX512) {
1173     if (DstTy.getSizeInBits() == 128)
1174       I.setDesc(TII.get(X86::VEXTRACTF32x4Zrr));
1175     else if (DstTy.getSizeInBits() == 256)
1176       I.setDesc(TII.get(X86::VEXTRACTF64x4Zrr));
1177     else
1178       return false;
1179   } else
1180     return false;
1181 
1182   // Convert to X86 VEXTRACT immediate.
1183   Index = Index / DstTy.getSizeInBits();
1184   I.getOperand(2).setImm(Index);
1185 
1186   return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
1187 }
1188 
1189 bool X86InstructionSelector::emitExtractSubreg(unsigned DstReg, unsigned SrcReg,
1190                                                MachineInstr &I,
1191                                                MachineRegisterInfo &MRI,
1192                                                MachineFunction &MF) const {
1193   const LLT DstTy = MRI.getType(DstReg);
1194   const LLT SrcTy = MRI.getType(SrcReg);
1195   unsigned SubIdx = X86::NoSubRegister;
1196 
1197   if (!DstTy.isVector() || !SrcTy.isVector())
1198     return false;
1199 
1200   assert(SrcTy.getSizeInBits() > DstTy.getSizeInBits() &&
1201          "Incorrect Src/Dst register size");
1202 
1203   if (DstTy.getSizeInBits() == 128)
1204     SubIdx = X86::sub_xmm;
1205   else if (DstTy.getSizeInBits() == 256)
1206     SubIdx = X86::sub_ymm;
1207   else
1208     return false;
1209 
1210   const TargetRegisterClass *DstRC = getRegClass(DstTy, DstReg, MRI);
1211   const TargetRegisterClass *SrcRC = getRegClass(SrcTy, SrcReg, MRI);
1212 
1213   SrcRC = TRI.getSubClassWithSubReg(SrcRC, SubIdx);
1214 
1215   if (!RBI.constrainGenericRegister(SrcReg, *SrcRC, MRI) ||
1216       !RBI.constrainGenericRegister(DstReg, *DstRC, MRI)) {
1217     LLVM_DEBUG(dbgs() << "Failed to constrain G_TRUNC\n");
1218     return false;
1219   }
1220 
1221   BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(X86::COPY), DstReg)
1222       .addReg(SrcReg, 0, SubIdx);
1223 
1224   return true;
1225 }
1226 
1227 bool X86InstructionSelector::emitInsertSubreg(unsigned DstReg, unsigned SrcReg,
1228                                               MachineInstr &I,
1229                                               MachineRegisterInfo &MRI,
1230                                               MachineFunction &MF) const {
1231   const LLT DstTy = MRI.getType(DstReg);
1232   const LLT SrcTy = MRI.getType(SrcReg);
1233   unsigned SubIdx = X86::NoSubRegister;
1234 
1235   // TODO: support scalar types
1236   if (!DstTy.isVector() || !SrcTy.isVector())
1237     return false;
1238 
1239   assert(SrcTy.getSizeInBits() < DstTy.getSizeInBits() &&
1240          "Incorrect Src/Dst register size");
1241 
1242   if (SrcTy.getSizeInBits() == 128)
1243     SubIdx = X86::sub_xmm;
1244   else if (SrcTy.getSizeInBits() == 256)
1245     SubIdx = X86::sub_ymm;
1246   else
1247     return false;
1248 
1249   const TargetRegisterClass *SrcRC = getRegClass(SrcTy, SrcReg, MRI);
1250   const TargetRegisterClass *DstRC = getRegClass(DstTy, DstReg, MRI);
1251 
1252   if (!RBI.constrainGenericRegister(SrcReg, *SrcRC, MRI) ||
1253       !RBI.constrainGenericRegister(DstReg, *DstRC, MRI)) {
1254     LLVM_DEBUG(dbgs() << "Failed to constrain INSERT_SUBREG\n");
1255     return false;
1256   }
1257 
1258   BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(X86::COPY))
1259       .addReg(DstReg, RegState::DefineNoRead, SubIdx)
1260       .addReg(SrcReg);
1261 
1262   return true;
1263 }
1264 
1265 bool X86InstructionSelector::selectInsert(MachineInstr &I,
1266                                           MachineRegisterInfo &MRI,
1267                                           MachineFunction &MF) const {
1268   assert((I.getOpcode() == TargetOpcode::G_INSERT) && "unexpected instruction");
1269 
1270   const unsigned DstReg = I.getOperand(0).getReg();
1271   const unsigned SrcReg = I.getOperand(1).getReg();
1272   const unsigned InsertReg = I.getOperand(2).getReg();
1273   int64_t Index = I.getOperand(3).getImm();
1274 
1275   const LLT DstTy = MRI.getType(DstReg);
1276   const LLT InsertRegTy = MRI.getType(InsertReg);
1277 
1278   // Meanwile handle vector type only.
1279   if (!DstTy.isVector())
1280     return false;
1281 
1282   if (Index % InsertRegTy.getSizeInBits() != 0)
1283     return false; // Not insert subvector.
1284 
1285   if (Index == 0 && MRI.getVRegDef(SrcReg)->isImplicitDef()) {
1286     // Replace by subreg copy.
1287     if (!emitInsertSubreg(DstReg, InsertReg, I, MRI, MF))
1288       return false;
1289 
1290     I.eraseFromParent();
1291     return true;
1292   }
1293 
1294   bool HasAVX = STI.hasAVX();
1295   bool HasAVX512 = STI.hasAVX512();
1296   bool HasVLX = STI.hasVLX();
1297 
1298   if (DstTy.getSizeInBits() == 256 && InsertRegTy.getSizeInBits() == 128) {
1299     if (HasVLX)
1300       I.setDesc(TII.get(X86::VINSERTF32x4Z256rr));
1301     else if (HasAVX)
1302       I.setDesc(TII.get(X86::VINSERTF128rr));
1303     else
1304       return false;
1305   } else if (DstTy.getSizeInBits() == 512 && HasAVX512) {
1306     if (InsertRegTy.getSizeInBits() == 128)
1307       I.setDesc(TII.get(X86::VINSERTF32x4Zrr));
1308     else if (InsertRegTy.getSizeInBits() == 256)
1309       I.setDesc(TII.get(X86::VINSERTF64x4Zrr));
1310     else
1311       return false;
1312   } else
1313     return false;
1314 
1315   // Convert to X86 VINSERT immediate.
1316   Index = Index / InsertRegTy.getSizeInBits();
1317 
1318   I.getOperand(3).setImm(Index);
1319 
1320   return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
1321 }
1322 
1323 bool X86InstructionSelector::selectUnmergeValues(
1324     MachineInstr &I, MachineRegisterInfo &MRI, MachineFunction &MF,
1325     CodeGenCoverage &CoverageInfo) const {
1326   assert((I.getOpcode() == TargetOpcode::G_UNMERGE_VALUES) &&
1327          "unexpected instruction");
1328 
1329   // Split to extracts.
1330   unsigned NumDefs = I.getNumOperands() - 1;
1331   unsigned SrcReg = I.getOperand(NumDefs).getReg();
1332   unsigned DefSize = MRI.getType(I.getOperand(0).getReg()).getSizeInBits();
1333 
1334   for (unsigned Idx = 0; Idx < NumDefs; ++Idx) {
1335     MachineInstr &ExtrInst =
1336         *BuildMI(*I.getParent(), I, I.getDebugLoc(),
1337                  TII.get(TargetOpcode::G_EXTRACT), I.getOperand(Idx).getReg())
1338              .addReg(SrcReg)
1339              .addImm(Idx * DefSize);
1340 
1341     if (!select(ExtrInst, CoverageInfo))
1342       return false;
1343   }
1344 
1345   I.eraseFromParent();
1346   return true;
1347 }
1348 
1349 bool X86InstructionSelector::selectMergeValues(
1350     MachineInstr &I, MachineRegisterInfo &MRI, MachineFunction &MF,
1351     CodeGenCoverage &CoverageInfo) const {
1352   assert((I.getOpcode() == TargetOpcode::G_MERGE_VALUES) &&
1353          "unexpected instruction");
1354 
1355   // Split to inserts.
1356   unsigned DstReg = I.getOperand(0).getReg();
1357   unsigned SrcReg0 = I.getOperand(1).getReg();
1358 
1359   const LLT DstTy = MRI.getType(DstReg);
1360   const LLT SrcTy = MRI.getType(SrcReg0);
1361   unsigned SrcSize = SrcTy.getSizeInBits();
1362 
1363   const RegisterBank &RegBank = *RBI.getRegBank(DstReg, MRI, TRI);
1364 
1365   // For the first src use insertSubReg.
1366   unsigned DefReg = MRI.createGenericVirtualRegister(DstTy);
1367   MRI.setRegBank(DefReg, RegBank);
1368   if (!emitInsertSubreg(DefReg, I.getOperand(1).getReg(), I, MRI, MF))
1369     return false;
1370 
1371   for (unsigned Idx = 2; Idx < I.getNumOperands(); ++Idx) {
1372     unsigned Tmp = MRI.createGenericVirtualRegister(DstTy);
1373     MRI.setRegBank(Tmp, RegBank);
1374 
1375     MachineInstr &InsertInst = *BuildMI(*I.getParent(), I, I.getDebugLoc(),
1376                                         TII.get(TargetOpcode::G_INSERT), Tmp)
1377                                     .addReg(DefReg)
1378                                     .addReg(I.getOperand(Idx).getReg())
1379                                     .addImm((Idx - 1) * SrcSize);
1380 
1381     DefReg = Tmp;
1382 
1383     if (!select(InsertInst, CoverageInfo))
1384       return false;
1385   }
1386 
1387   MachineInstr &CopyInst = *BuildMI(*I.getParent(), I, I.getDebugLoc(),
1388                                     TII.get(TargetOpcode::COPY), DstReg)
1389                                 .addReg(DefReg);
1390 
1391   if (!select(CopyInst, CoverageInfo))
1392     return false;
1393 
1394   I.eraseFromParent();
1395   return true;
1396 }
1397 
1398 bool X86InstructionSelector::selectCondBranch(MachineInstr &I,
1399                                               MachineRegisterInfo &MRI,
1400                                               MachineFunction &MF) const {
1401   assert((I.getOpcode() == TargetOpcode::G_BRCOND) && "unexpected instruction");
1402 
1403   const unsigned CondReg = I.getOperand(0).getReg();
1404   MachineBasicBlock *DestMBB = I.getOperand(1).getMBB();
1405 
1406   MachineInstr &TestInst =
1407       *BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(X86::TEST8ri))
1408            .addReg(CondReg)
1409            .addImm(1);
1410   BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(X86::JNE_1))
1411       .addMBB(DestMBB);
1412 
1413   constrainSelectedInstRegOperands(TestInst, TII, TRI, RBI);
1414 
1415   I.eraseFromParent();
1416   return true;
1417 }
1418 
1419 bool X86InstructionSelector::materializeFP(MachineInstr &I,
1420                                            MachineRegisterInfo &MRI,
1421                                            MachineFunction &MF) const {
1422   assert((I.getOpcode() == TargetOpcode::G_FCONSTANT) &&
1423          "unexpected instruction");
1424 
1425   // Can't handle alternate code models yet.
1426   CodeModel::Model CM = TM.getCodeModel();
1427   if (CM != CodeModel::Small && CM != CodeModel::Large)
1428     return false;
1429 
1430   const unsigned DstReg = I.getOperand(0).getReg();
1431   const LLT DstTy = MRI.getType(DstReg);
1432   const RegisterBank &RegBank = *RBI.getRegBank(DstReg, MRI, TRI);
1433   unsigned Align = DstTy.getSizeInBits();
1434   const DebugLoc &DbgLoc = I.getDebugLoc();
1435 
1436   unsigned Opc = getLoadStoreOp(DstTy, RegBank, TargetOpcode::G_LOAD, Align);
1437 
1438   // Create the load from the constant pool.
1439   const ConstantFP *CFP = I.getOperand(1).getFPImm();
1440   unsigned CPI = MF.getConstantPool()->getConstantPoolIndex(CFP, Align);
1441   MachineInstr *LoadInst = nullptr;
1442   unsigned char OpFlag = STI.classifyLocalReference(nullptr);
1443 
1444   if (CM == CodeModel::Large && STI.is64Bit()) {
1445     // Under X86-64 non-small code model, GV (and friends) are 64-bits, so
1446     // they cannot be folded into immediate fields.
1447 
1448     unsigned AddrReg = MRI.createVirtualRegister(&X86::GR64RegClass);
1449     BuildMI(*I.getParent(), I, DbgLoc, TII.get(X86::MOV64ri), AddrReg)
1450         .addConstantPoolIndex(CPI, 0, OpFlag);
1451 
1452     MachineMemOperand *MMO = MF.getMachineMemOperand(
1453         MachinePointerInfo::getConstantPool(MF), MachineMemOperand::MOLoad,
1454         MF.getDataLayout().getPointerSize(), Align);
1455 
1456     LoadInst =
1457         addDirectMem(BuildMI(*I.getParent(), I, DbgLoc, TII.get(Opc), DstReg),
1458                      AddrReg)
1459             .addMemOperand(MMO);
1460 
1461   } else if (CM == CodeModel::Small || !STI.is64Bit()) {
1462     // Handle the case when globals fit in our immediate field.
1463     // This is true for X86-32 always and X86-64 when in -mcmodel=small mode.
1464 
1465     // x86-32 PIC requires a PIC base register for constant pools.
1466     unsigned PICBase = 0;
1467     if (OpFlag == X86II::MO_PIC_BASE_OFFSET || OpFlag == X86II::MO_GOTOFF) {
1468       // PICBase can be allocated by TII.getGlobalBaseReg(&MF).
1469       // In DAGISEL the code that initialize it generated by the CGBR pass.
1470       return false; // TODO support the mode.
1471     } else if (STI.is64Bit() && TM.getCodeModel() == CodeModel::Small)
1472       PICBase = X86::RIP;
1473 
1474     LoadInst = addConstantPoolReference(
1475         BuildMI(*I.getParent(), I, DbgLoc, TII.get(Opc), DstReg), CPI, PICBase,
1476         OpFlag);
1477   } else
1478     return false;
1479 
1480   constrainSelectedInstRegOperands(*LoadInst, TII, TRI, RBI);
1481   I.eraseFromParent();
1482   return true;
1483 }
1484 
1485 bool X86InstructionSelector::selectImplicitDefOrPHI(
1486     MachineInstr &I, MachineRegisterInfo &MRI) const {
1487   assert((I.getOpcode() == TargetOpcode::G_IMPLICIT_DEF ||
1488           I.getOpcode() == TargetOpcode::G_PHI) &&
1489          "unexpected instruction");
1490 
1491   unsigned DstReg = I.getOperand(0).getReg();
1492 
1493   if (!MRI.getRegClassOrNull(DstReg)) {
1494     const LLT DstTy = MRI.getType(DstReg);
1495     const TargetRegisterClass *RC = getRegClass(DstTy, DstReg, MRI);
1496 
1497     if (!RBI.constrainGenericRegister(DstReg, *RC, MRI)) {
1498       LLVM_DEBUG(dbgs() << "Failed to constrain " << TII.getName(I.getOpcode())
1499                         << " operand\n");
1500       return false;
1501     }
1502   }
1503 
1504   if (I.getOpcode() == TargetOpcode::G_IMPLICIT_DEF)
1505     I.setDesc(TII.get(X86::IMPLICIT_DEF));
1506   else
1507     I.setDesc(TII.get(X86::PHI));
1508 
1509   return true;
1510 }
1511 
1512 // Currently GlobalIsel TableGen generates patterns for shift imm and shift 1,
1513 // but with shiftCount i8. In G_LSHR/G_ASHR/G_SHL like LLVM-IR both arguments
1514 // has the same type, so for now only shift i8 can use auto generated
1515 // TableGen patterns.
1516 bool X86InstructionSelector::selectShift(MachineInstr &I,
1517                                          MachineRegisterInfo &MRI,
1518                                          MachineFunction &MF) const {
1519 
1520   assert((I.getOpcode() == TargetOpcode::G_SHL ||
1521           I.getOpcode() == TargetOpcode::G_ASHR ||
1522           I.getOpcode() == TargetOpcode::G_LSHR) &&
1523          "unexpected instruction");
1524 
1525   unsigned DstReg = I.getOperand(0).getReg();
1526   const LLT DstTy = MRI.getType(DstReg);
1527   const RegisterBank &DstRB = *RBI.getRegBank(DstReg, MRI, TRI);
1528 
1529   const static struct ShiftEntry {
1530     unsigned SizeInBits;
1531     unsigned CReg;
1532     unsigned OpLSHR;
1533     unsigned OpASHR;
1534     unsigned OpSHL;
1535   } OpTable[] = {
1536       {8, X86::CL, X86::SHR8rCL, X86::SAR8rCL, X86::SHL8rCL},      // i8
1537       {16, X86::CX, X86::SHR16rCL, X86::SAR16rCL, X86::SHL16rCL},  // i16
1538       {32, X86::ECX, X86::SHR32rCL, X86::SAR32rCL, X86::SHL32rCL}, // i32
1539       {64, X86::RCX, X86::SHR64rCL, X86::SAR64rCL, X86::SHL64rCL}  // i64
1540   };
1541 
1542   if (DstRB.getID() != X86::GPRRegBankID)
1543     return false;
1544 
1545   auto ShiftEntryIt = std::find_if(
1546       std::begin(OpTable), std::end(OpTable), [DstTy](const ShiftEntry &El) {
1547         return El.SizeInBits == DstTy.getSizeInBits();
1548       });
1549   if (ShiftEntryIt == std::end(OpTable))
1550     return false;
1551 
1552   unsigned CReg = ShiftEntryIt->CReg;
1553   unsigned Opcode = 0;
1554   switch (I.getOpcode()) {
1555   case TargetOpcode::G_SHL:
1556     Opcode = ShiftEntryIt->OpSHL;
1557     break;
1558   case TargetOpcode::G_ASHR:
1559     Opcode = ShiftEntryIt->OpASHR;
1560     break;
1561   case TargetOpcode::G_LSHR:
1562     Opcode = ShiftEntryIt->OpLSHR;
1563     break;
1564   default:
1565     return false;
1566   }
1567 
1568   unsigned Op0Reg = I.getOperand(1).getReg();
1569   unsigned Op1Reg = I.getOperand(2).getReg();
1570 
1571   BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(TargetOpcode::COPY),
1572           ShiftEntryIt->CReg)
1573       .addReg(Op1Reg);
1574 
1575   // The shift instruction uses X86::CL. If we defined a super-register
1576   // of X86::CL, emit a subreg KILL to precisely describe what we're doing here.
1577   if (CReg != X86::CL)
1578     BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(TargetOpcode::KILL),
1579             X86::CL)
1580         .addReg(CReg, RegState::Kill);
1581 
1582   MachineInstr &ShiftInst =
1583       *BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(Opcode), DstReg)
1584            .addReg(Op0Reg);
1585 
1586   constrainSelectedInstRegOperands(ShiftInst, TII, TRI, RBI);
1587   I.eraseFromParent();
1588   return true;
1589 }
1590 
1591 bool X86InstructionSelector::selectDivRem(MachineInstr &I,
1592                                           MachineRegisterInfo &MRI,
1593                                           MachineFunction &MF) const {
1594   // The implementation of this function is taken from X86FastISel.
1595   assert((I.getOpcode() == TargetOpcode::G_SDIV ||
1596           I.getOpcode() == TargetOpcode::G_SREM ||
1597           I.getOpcode() == TargetOpcode::G_UDIV ||
1598           I.getOpcode() == TargetOpcode::G_UREM) &&
1599          "unexpected instruction");
1600 
1601   const unsigned DstReg = I.getOperand(0).getReg();
1602   const unsigned Op1Reg = I.getOperand(1).getReg();
1603   const unsigned Op2Reg = I.getOperand(2).getReg();
1604 
1605   const LLT RegTy = MRI.getType(DstReg);
1606   assert(RegTy == MRI.getType(Op1Reg) && RegTy == MRI.getType(Op2Reg) &&
1607          "Arguments and return value types must match");
1608 
1609   const RegisterBank &RegRB = *RBI.getRegBank(DstReg, MRI, TRI);
1610   if (RegRB.getID() != X86::GPRRegBankID)
1611     return false;
1612 
1613   const static unsigned NumTypes = 4; // i8, i16, i32, i64
1614   const static unsigned NumOps = 4;   // SDiv, SRem, UDiv, URem
1615   const static bool S = true;         // IsSigned
1616   const static bool U = false;        // !IsSigned
1617   const static unsigned Copy = TargetOpcode::COPY;
1618   // For the X86 IDIV instruction, in most cases the dividend
1619   // (numerator) must be in a specific register pair highreg:lowreg,
1620   // producing the quotient in lowreg and the remainder in highreg.
1621   // For most data types, to set up the instruction, the dividend is
1622   // copied into lowreg, and lowreg is sign-extended into highreg.  The
1623   // exception is i8, where the dividend is defined as a single register rather
1624   // than a register pair, and we therefore directly sign-extend the dividend
1625   // into lowreg, instead of copying, and ignore the highreg.
1626   const static struct DivRemEntry {
1627     // The following portion depends only on the data type.
1628     unsigned SizeInBits;
1629     unsigned LowInReg;  // low part of the register pair
1630     unsigned HighInReg; // high part of the register pair
1631     // The following portion depends on both the data type and the operation.
1632     struct DivRemResult {
1633       unsigned OpDivRem;        // The specific DIV/IDIV opcode to use.
1634       unsigned OpSignExtend;    // Opcode for sign-extending lowreg into
1635                                 // highreg, or copying a zero into highreg.
1636       unsigned OpCopy;          // Opcode for copying dividend into lowreg, or
1637                                 // zero/sign-extending into lowreg for i8.
1638       unsigned DivRemResultReg; // Register containing the desired result.
1639       bool IsOpSigned;          // Whether to use signed or unsigned form.
1640     } ResultTable[NumOps];
1641   } OpTable[NumTypes] = {
1642       {8,
1643        X86::AX,
1644        0,
1645        {
1646            {X86::IDIV8r, 0, X86::MOVSX16rr8, X86::AL, S}, // SDiv
1647            {X86::IDIV8r, 0, X86::MOVSX16rr8, X86::AH, S}, // SRem
1648            {X86::DIV8r, 0, X86::MOVZX16rr8, X86::AL, U},  // UDiv
1649            {X86::DIV8r, 0, X86::MOVZX16rr8, X86::AH, U},  // URem
1650        }},                                                // i8
1651       {16,
1652        X86::AX,
1653        X86::DX,
1654        {
1655            {X86::IDIV16r, X86::CWD, Copy, X86::AX, S},    // SDiv
1656            {X86::IDIV16r, X86::CWD, Copy, X86::DX, S},    // SRem
1657            {X86::DIV16r, X86::MOV32r0, Copy, X86::AX, U}, // UDiv
1658            {X86::DIV16r, X86::MOV32r0, Copy, X86::DX, U}, // URem
1659        }},                                                // i16
1660       {32,
1661        X86::EAX,
1662        X86::EDX,
1663        {
1664            {X86::IDIV32r, X86::CDQ, Copy, X86::EAX, S},    // SDiv
1665            {X86::IDIV32r, X86::CDQ, Copy, X86::EDX, S},    // SRem
1666            {X86::DIV32r, X86::MOV32r0, Copy, X86::EAX, U}, // UDiv
1667            {X86::DIV32r, X86::MOV32r0, Copy, X86::EDX, U}, // URem
1668        }},                                                 // i32
1669       {64,
1670        X86::RAX,
1671        X86::RDX,
1672        {
1673            {X86::IDIV64r, X86::CQO, Copy, X86::RAX, S},    // SDiv
1674            {X86::IDIV64r, X86::CQO, Copy, X86::RDX, S},    // SRem
1675            {X86::DIV64r, X86::MOV32r0, Copy, X86::RAX, U}, // UDiv
1676            {X86::DIV64r, X86::MOV32r0, Copy, X86::RDX, U}, // URem
1677        }},                                                 // i64
1678   };
1679 
1680   auto OpEntryIt = std::find_if(std::begin(OpTable), std::end(OpTable),
1681                                 [RegTy](const DivRemEntry &El) {
1682                                   return El.SizeInBits == RegTy.getSizeInBits();
1683                                 });
1684   if (OpEntryIt == std::end(OpTable))
1685     return false;
1686 
1687   unsigned OpIndex;
1688   switch (I.getOpcode()) {
1689   default:
1690     llvm_unreachable("Unexpected div/rem opcode");
1691   case TargetOpcode::G_SDIV:
1692     OpIndex = 0;
1693     break;
1694   case TargetOpcode::G_SREM:
1695     OpIndex = 1;
1696     break;
1697   case TargetOpcode::G_UDIV:
1698     OpIndex = 2;
1699     break;
1700   case TargetOpcode::G_UREM:
1701     OpIndex = 3;
1702     break;
1703   }
1704 
1705   const DivRemEntry &TypeEntry = *OpEntryIt;
1706   const DivRemEntry::DivRemResult &OpEntry = TypeEntry.ResultTable[OpIndex];
1707 
1708   const TargetRegisterClass *RegRC = getRegClass(RegTy, RegRB);
1709   if (!RBI.constrainGenericRegister(Op1Reg, *RegRC, MRI) ||
1710       !RBI.constrainGenericRegister(Op2Reg, *RegRC, MRI) ||
1711       !RBI.constrainGenericRegister(DstReg, *RegRC, MRI)) {
1712     LLVM_DEBUG(dbgs() << "Failed to constrain " << TII.getName(I.getOpcode())
1713                       << " operand\n");
1714     return false;
1715   }
1716 
1717   // Move op1 into low-order input register.
1718   BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(OpEntry.OpCopy),
1719           TypeEntry.LowInReg)
1720       .addReg(Op1Reg);
1721   // Zero-extend or sign-extend into high-order input register.
1722   if (OpEntry.OpSignExtend) {
1723     if (OpEntry.IsOpSigned)
1724       BuildMI(*I.getParent(), I, I.getDebugLoc(),
1725               TII.get(OpEntry.OpSignExtend));
1726     else {
1727       unsigned Zero32 = MRI.createVirtualRegister(&X86::GR32RegClass);
1728       BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(X86::MOV32r0),
1729               Zero32);
1730 
1731       // Copy the zero into the appropriate sub/super/identical physical
1732       // register. Unfortunately the operations needed are not uniform enough
1733       // to fit neatly into the table above.
1734       if (RegTy.getSizeInBits() == 16) {
1735         BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(Copy),
1736                 TypeEntry.HighInReg)
1737             .addReg(Zero32, 0, X86::sub_16bit);
1738       } else if (RegTy.getSizeInBits() == 32) {
1739         BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(Copy),
1740                 TypeEntry.HighInReg)
1741             .addReg(Zero32);
1742       } else if (RegTy.getSizeInBits() == 64) {
1743         BuildMI(*I.getParent(), I, I.getDebugLoc(),
1744                 TII.get(TargetOpcode::SUBREG_TO_REG), TypeEntry.HighInReg)
1745             .addImm(0)
1746             .addReg(Zero32)
1747             .addImm(X86::sub_32bit);
1748       }
1749     }
1750   }
1751   // Generate the DIV/IDIV instruction.
1752   BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(OpEntry.OpDivRem))
1753       .addReg(Op2Reg);
1754   // For i8 remainder, we can't reference ah directly, as we'll end
1755   // up with bogus copies like %r9b = COPY %ah. Reference ax
1756   // instead to prevent ah references in a rex instruction.
1757   //
1758   // The current assumption of the fast register allocator is that isel
1759   // won't generate explicit references to the GR8_NOREX registers. If
1760   // the allocator and/or the backend get enhanced to be more robust in
1761   // that regard, this can be, and should be, removed.
1762   if ((I.getOpcode() == Instruction::SRem ||
1763        I.getOpcode() == Instruction::URem) &&
1764       OpEntry.DivRemResultReg == X86::AH && STI.is64Bit()) {
1765     unsigned SourceSuperReg = MRI.createVirtualRegister(&X86::GR16RegClass);
1766     unsigned ResultSuperReg = MRI.createVirtualRegister(&X86::GR16RegClass);
1767     BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(Copy), SourceSuperReg)
1768         .addReg(X86::AX);
1769 
1770     // Shift AX right by 8 bits instead of using AH.
1771     BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(X86::SHR16ri),
1772             ResultSuperReg)
1773         .addReg(SourceSuperReg)
1774         .addImm(8);
1775 
1776     // Now reference the 8-bit subreg of the result.
1777     BuildMI(*I.getParent(), I, I.getDebugLoc(),
1778             TII.get(TargetOpcode::SUBREG_TO_REG))
1779         .addDef(DstReg)
1780         .addImm(0)
1781         .addReg(ResultSuperReg)
1782         .addImm(X86::sub_8bit);
1783   } else {
1784     BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(TargetOpcode::COPY),
1785             DstReg)
1786         .addReg(OpEntry.DivRemResultReg);
1787   }
1788   I.eraseFromParent();
1789   return true;
1790 }
1791 
1792 bool X86InstructionSelector::selectIntrinsicWSideEffects(
1793     MachineInstr &I, MachineRegisterInfo &MRI, MachineFunction &MF) const {
1794 
1795   assert(I.getOpcode() == TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS &&
1796          "unexpected instruction");
1797 
1798   if (I.getOperand(0).getIntrinsicID() != Intrinsic::trap)
1799     return false;
1800 
1801   BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(X86::TRAP));
1802 
1803   I.eraseFromParent();
1804   return true;
1805 }
1806 
1807 InstructionSelector *
1808 llvm::createX86InstructionSelector(const X86TargetMachine &TM,
1809                                    X86Subtarget &Subtarget,
1810                                    X86RegisterBankInfo &RBI) {
1811   return new X86InstructionSelector(TM, Subtarget, RBI);
1812 }
1813