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