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