1 //===-- llvm/CodeGen/GlobalISel/LegalizerHelper.cpp -----------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \file This file implements the LegalizerHelper class to legalize
11 /// individual instructions and the LegalizeMachineIR wrapper pass for the
12 /// primary legalization.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
17 #include "llvm/CodeGen/GlobalISel/CallLowering.h"
18 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
19 #include "llvm/CodeGen/MachineRegisterInfo.h"
20 #include "llvm/CodeGen/TargetLowering.h"
21 #include "llvm/CodeGen/TargetSubtargetInfo.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
24 
25 
26 #define DEBUG_TYPE "legalizer"
27 
28 using namespace llvm;
29 
30 LegalizerHelper::LegalizerHelper(MachineFunction &MF)
31     : MRI(MF.getRegInfo()), LI(*MF.getSubtarget().getLegalizerInfo()) {
32   MIRBuilder.setMF(MF);
33 }
34 
35 LegalizerHelper::LegalizeResult
36 LegalizerHelper::legalizeInstrStep(MachineInstr &MI) {
37   DEBUG(dbgs() << "Legalizing: "; MI.print(dbgs()));
38 
39   auto Action = LI.getAction(MI, MRI);
40   switch (std::get<0>(Action)) {
41   case LegalizerInfo::Legal:
42     DEBUG(dbgs() << ".. Already legal\n");
43     return AlreadyLegal;
44   case LegalizerInfo::Libcall:
45     DEBUG(dbgs() << ".. Convert to libcall\n");
46     return libcall(MI);
47   case LegalizerInfo::NarrowScalar:
48     DEBUG(dbgs() << ".. Narrow scalar\n");
49     return narrowScalar(MI, std::get<1>(Action), std::get<2>(Action));
50   case LegalizerInfo::WidenScalar:
51     DEBUG(dbgs() << ".. Widen scalar\n");
52     return widenScalar(MI, std::get<1>(Action), std::get<2>(Action));
53   case LegalizerInfo::Lower:
54     DEBUG(dbgs() << ".. Lower\n");
55     return lower(MI, std::get<1>(Action), std::get<2>(Action));
56   case LegalizerInfo::FewerElements:
57     DEBUG(dbgs() << ".. Reduce number of elements\n");
58     return fewerElementsVector(MI, std::get<1>(Action), std::get<2>(Action));
59   case LegalizerInfo::Custom:
60     DEBUG(dbgs() << ".. Custom legalization\n");
61     return LI.legalizeCustom(MI, MRI, MIRBuilder) ? Legalized
62                                                   : UnableToLegalize;
63   default:
64     DEBUG(dbgs() << ".. Unable to legalize\n");
65     return UnableToLegalize;
66   }
67 }
68 
69 void LegalizerHelper::extractParts(unsigned Reg, LLT Ty, int NumParts,
70                                    SmallVectorImpl<unsigned> &VRegs) {
71   for (int i = 0; i < NumParts; ++i)
72     VRegs.push_back(MRI.createGenericVirtualRegister(Ty));
73   MIRBuilder.buildUnmerge(VRegs, Reg);
74 }
75 
76 static RTLIB::Libcall getRTLibDesc(unsigned Opcode, unsigned Size) {
77   switch (Opcode) {
78   case TargetOpcode::G_SDIV:
79     assert(Size == 32 && "Unsupported size");
80     return RTLIB::SDIV_I32;
81   case TargetOpcode::G_UDIV:
82     assert(Size == 32 && "Unsupported size");
83     return RTLIB::UDIV_I32;
84   case TargetOpcode::G_SREM:
85     assert(Size == 32 && "Unsupported size");
86     return RTLIB::SREM_I32;
87   case TargetOpcode::G_UREM:
88     assert(Size == 32 && "Unsupported size");
89     return RTLIB::UREM_I32;
90   case TargetOpcode::G_FADD:
91     assert((Size == 32 || Size == 64) && "Unsupported size");
92     return Size == 64 ? RTLIB::ADD_F64 : RTLIB::ADD_F32;
93   case TargetOpcode::G_FSUB:
94     assert((Size == 32 || Size == 64) && "Unsupported size");
95     return Size == 64 ? RTLIB::SUB_F64 : RTLIB::SUB_F32;
96   case TargetOpcode::G_FMUL:
97     assert((Size == 32 || Size == 64) && "Unsupported size");
98     return Size == 64 ? RTLIB::MUL_F64 : RTLIB::MUL_F32;
99   case TargetOpcode::G_FDIV:
100     assert((Size == 32 || Size == 64) && "Unsupported size");
101     return Size == 64 ? RTLIB::DIV_F64 : RTLIB::DIV_F32;
102   case TargetOpcode::G_FREM:
103     return Size == 64 ? RTLIB::REM_F64 : RTLIB::REM_F32;
104   case TargetOpcode::G_FPOW:
105     return Size == 64 ? RTLIB::POW_F64 : RTLIB::POW_F32;
106   case TargetOpcode::G_FMA:
107     assert((Size == 32 || Size == 64) && "Unsupported size");
108     return Size == 64 ? RTLIB::FMA_F64 : RTLIB::FMA_F32;
109   }
110   llvm_unreachable("Unknown libcall function");
111 }
112 
113 LegalizerHelper::LegalizeResult
114 llvm::createLibcall(MachineIRBuilder &MIRBuilder, RTLIB::Libcall Libcall,
115                     const CallLowering::ArgInfo &Result,
116                     ArrayRef<CallLowering::ArgInfo> Args) {
117   auto &CLI = *MIRBuilder.getMF().getSubtarget().getCallLowering();
118   auto &TLI = *MIRBuilder.getMF().getSubtarget().getTargetLowering();
119   const char *Name = TLI.getLibcallName(Libcall);
120 
121   MIRBuilder.getMF().getFrameInfo().setHasCalls(true);
122   if (!CLI.lowerCall(MIRBuilder, TLI.getLibcallCallingConv(Libcall),
123                      MachineOperand::CreateES(Name), Result, Args))
124     return LegalizerHelper::UnableToLegalize;
125 
126   return LegalizerHelper::Legalized;
127 }
128 
129 static LegalizerHelper::LegalizeResult
130 simpleLibcall(MachineInstr &MI, MachineIRBuilder &MIRBuilder, unsigned Size,
131               Type *OpType) {
132   auto Libcall = getRTLibDesc(MI.getOpcode(), Size);
133 
134   SmallVector<CallLowering::ArgInfo, 3> Args;
135   for (unsigned i = 1; i < MI.getNumOperands(); i++)
136     Args.push_back({MI.getOperand(i).getReg(), OpType});
137   return createLibcall(MIRBuilder, Libcall, {MI.getOperand(0).getReg(), OpType},
138                        Args);
139 }
140 
141 LegalizerHelper::LegalizeResult
142 LegalizerHelper::libcall(MachineInstr &MI) {
143   LLT LLTy = MRI.getType(MI.getOperand(0).getReg());
144   unsigned Size = LLTy.getSizeInBits();
145   auto &Ctx = MIRBuilder.getMF().getFunction().getContext();
146 
147   MIRBuilder.setInstr(MI);
148 
149   switch (MI.getOpcode()) {
150   default:
151     return UnableToLegalize;
152   case TargetOpcode::G_SDIV:
153   case TargetOpcode::G_UDIV:
154   case TargetOpcode::G_SREM:
155   case TargetOpcode::G_UREM: {
156     Type *HLTy = Type::getInt32Ty(Ctx);
157     auto Status = simpleLibcall(MI, MIRBuilder, Size, HLTy);
158     if (Status != Legalized)
159       return Status;
160     break;
161   }
162   case TargetOpcode::G_FADD:
163   case TargetOpcode::G_FSUB:
164   case TargetOpcode::G_FMUL:
165   case TargetOpcode::G_FDIV:
166   case TargetOpcode::G_FMA:
167   case TargetOpcode::G_FPOW:
168   case TargetOpcode::G_FREM: {
169     Type *HLTy = Size == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx);
170     auto Status = simpleLibcall(MI, MIRBuilder, Size, HLTy);
171     if (Status != Legalized)
172       return Status;
173     break;
174   }
175   }
176 
177   MI.eraseFromParent();
178   return Legalized;
179 }
180 
181 LegalizerHelper::LegalizeResult LegalizerHelper::narrowScalar(MachineInstr &MI,
182                                                               unsigned TypeIdx,
183                                                               LLT NarrowTy) {
184   // FIXME: Don't know how to handle secondary types yet.
185   if (TypeIdx != 0 && MI.getOpcode() != TargetOpcode::G_EXTRACT)
186     return UnableToLegalize;
187 
188   MIRBuilder.setInstr(MI);
189 
190   int64_t SizeOp0 = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
191   int64_t NarrowSize = NarrowTy.getSizeInBits();
192 
193   switch (MI.getOpcode()) {
194   default:
195     return UnableToLegalize;
196   case TargetOpcode::G_IMPLICIT_DEF: {
197     // FIXME: add support for when SizeOp0 isn't an exact multiple of
198     // NarrowSize.
199     if (SizeOp0 % NarrowSize != 0)
200       return UnableToLegalize;
201     int NumParts = SizeOp0 / NarrowSize;
202 
203     SmallVector<unsigned, 2> DstRegs;
204     for (int i = 0; i < NumParts; ++i) {
205       unsigned Dst = MRI.createGenericVirtualRegister(NarrowTy);
206       MIRBuilder.buildUndef(Dst);
207       DstRegs.push_back(Dst);
208     }
209     MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs);
210     MI.eraseFromParent();
211     return Legalized;
212   }
213   case TargetOpcode::G_ADD: {
214     // FIXME: add support for when SizeOp0 isn't an exact multiple of
215     // NarrowSize.
216     if (SizeOp0 % NarrowSize != 0)
217       return UnableToLegalize;
218     // Expand in terms of carry-setting/consuming G_ADDE instructions.
219     int NumParts = SizeOp0 / NarrowTy.getSizeInBits();
220 
221     SmallVector<unsigned, 2> Src1Regs, Src2Regs, DstRegs;
222     extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs);
223     extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs);
224 
225     unsigned CarryIn = MRI.createGenericVirtualRegister(LLT::scalar(1));
226     MIRBuilder.buildConstant(CarryIn, 0);
227 
228     for (int i = 0; i < NumParts; ++i) {
229       unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
230       unsigned CarryOut = MRI.createGenericVirtualRegister(LLT::scalar(1));
231 
232       MIRBuilder.buildUAdde(DstReg, CarryOut, Src1Regs[i],
233                             Src2Regs[i], CarryIn);
234 
235       DstRegs.push_back(DstReg);
236       CarryIn = CarryOut;
237     }
238     unsigned DstReg = MI.getOperand(0).getReg();
239     MIRBuilder.buildMerge(DstReg, DstRegs);
240     MI.eraseFromParent();
241     return Legalized;
242   }
243   case TargetOpcode::G_EXTRACT: {
244     if (TypeIdx != 1)
245       return UnableToLegalize;
246 
247     int64_t SizeOp1 = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
248     // FIXME: add support for when SizeOp1 isn't an exact multiple of
249     // NarrowSize.
250     if (SizeOp1 % NarrowSize != 0)
251       return UnableToLegalize;
252     int NumParts = SizeOp1 / NarrowSize;
253 
254     SmallVector<unsigned, 2> SrcRegs, DstRegs;
255     SmallVector<uint64_t, 2> Indexes;
256     extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs);
257 
258     unsigned OpReg = MI.getOperand(0).getReg();
259     int64_t OpStart = MI.getOperand(2).getImm();
260     int64_t OpSize = MRI.getType(OpReg).getSizeInBits();
261     for (int i = 0; i < NumParts; ++i) {
262       unsigned SrcStart = i * NarrowSize;
263 
264       if (SrcStart + NarrowSize <= OpStart || SrcStart >= OpStart + OpSize) {
265         // No part of the extract uses this subregister, ignore it.
266         continue;
267       } else if (SrcStart == OpStart && NarrowTy == MRI.getType(OpReg)) {
268         // The entire subregister is extracted, forward the value.
269         DstRegs.push_back(SrcRegs[i]);
270         continue;
271       }
272 
273       // OpSegStart is where this destination segment would start in OpReg if it
274       // extended infinitely in both directions.
275       int64_t ExtractOffset, SegSize;
276       if (OpStart < SrcStart) {
277         ExtractOffset = 0;
278         SegSize = std::min(NarrowSize, OpStart + OpSize - SrcStart);
279       } else {
280         ExtractOffset = OpStart - SrcStart;
281         SegSize = std::min(SrcStart + NarrowSize - OpStart, OpSize);
282       }
283 
284       unsigned SegReg = SrcRegs[i];
285       if (ExtractOffset != 0 || SegSize != NarrowSize) {
286         // A genuine extract is needed.
287         SegReg = MRI.createGenericVirtualRegister(LLT::scalar(SegSize));
288         MIRBuilder.buildExtract(SegReg, SrcRegs[i], ExtractOffset);
289       }
290 
291       DstRegs.push_back(SegReg);
292     }
293 
294     MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs);
295     MI.eraseFromParent();
296     return Legalized;
297   }
298   case TargetOpcode::G_INSERT: {
299     // FIXME: add support for when SizeOp0 isn't an exact multiple of
300     // NarrowSize.
301     if (SizeOp0 % NarrowSize != 0)
302       return UnableToLegalize;
303 
304     int NumParts = SizeOp0 / NarrowSize;
305 
306     SmallVector<unsigned, 2> SrcRegs, DstRegs;
307     SmallVector<uint64_t, 2> Indexes;
308     extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs);
309 
310     unsigned OpReg = MI.getOperand(2).getReg();
311     int64_t OpStart = MI.getOperand(3).getImm();
312     int64_t OpSize = MRI.getType(OpReg).getSizeInBits();
313     for (int i = 0; i < NumParts; ++i) {
314       unsigned DstStart = i * NarrowSize;
315 
316       if (DstStart + NarrowSize <= OpStart || DstStart >= OpStart + OpSize) {
317         // No part of the insert affects this subregister, forward the original.
318         DstRegs.push_back(SrcRegs[i]);
319         continue;
320       } else if (DstStart == OpStart && NarrowTy == MRI.getType(OpReg)) {
321         // The entire subregister is defined by this insert, forward the new
322         // value.
323         DstRegs.push_back(OpReg);
324         continue;
325       }
326 
327       // OpSegStart is where this destination segment would start in OpReg if it
328       // extended infinitely in both directions.
329       int64_t ExtractOffset, InsertOffset, SegSize;
330       if (OpStart < DstStart) {
331         InsertOffset = 0;
332         ExtractOffset = DstStart - OpStart;
333         SegSize = std::min(NarrowSize, OpStart + OpSize - DstStart);
334       } else {
335         InsertOffset = OpStart - DstStart;
336         ExtractOffset = 0;
337         SegSize =
338             std::min(NarrowSize - InsertOffset, OpStart + OpSize - DstStart);
339       }
340 
341       unsigned SegReg = OpReg;
342       if (ExtractOffset != 0 || SegSize != OpSize) {
343         // A genuine extract is needed.
344         SegReg = MRI.createGenericVirtualRegister(LLT::scalar(SegSize));
345         MIRBuilder.buildExtract(SegReg, OpReg, ExtractOffset);
346       }
347 
348       unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
349       MIRBuilder.buildInsert(DstReg, SrcRegs[i], SegReg, InsertOffset);
350       DstRegs.push_back(DstReg);
351     }
352 
353     assert(DstRegs.size() == (unsigned)NumParts && "not all parts covered");
354     MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs);
355     MI.eraseFromParent();
356     return Legalized;
357   }
358   case TargetOpcode::G_LOAD: {
359     // FIXME: add support for when SizeOp0 isn't an exact multiple of
360     // NarrowSize.
361     if (SizeOp0 % NarrowSize != 0)
362       return UnableToLegalize;
363     int NumParts = SizeOp0 / NarrowSize;
364     LLT OffsetTy = LLT::scalar(
365         MRI.getType(MI.getOperand(1).getReg()).getScalarSizeInBits());
366 
367     SmallVector<unsigned, 2> DstRegs;
368     for (int i = 0; i < NumParts; ++i) {
369       unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
370       unsigned SrcReg = 0;
371       unsigned Adjustment = i * NarrowSize / 8;
372 
373       MIRBuilder.materializeGEP(SrcReg, MI.getOperand(1).getReg(), OffsetTy,
374                                 Adjustment);
375 
376       // TODO: This is conservatively correct, but we probably want to split the
377       // memory operands in the future.
378       MIRBuilder.buildLoad(DstReg, SrcReg, **MI.memoperands_begin());
379 
380       DstRegs.push_back(DstReg);
381     }
382     unsigned DstReg = MI.getOperand(0).getReg();
383     MIRBuilder.buildMerge(DstReg, DstRegs);
384     MI.eraseFromParent();
385     return Legalized;
386   }
387   case TargetOpcode::G_STORE: {
388     // FIXME: add support for when SizeOp0 isn't an exact multiple of
389     // NarrowSize.
390     if (SizeOp0 % NarrowSize != 0)
391       return UnableToLegalize;
392     int NumParts = SizeOp0 / NarrowSize;
393     LLT OffsetTy = LLT::scalar(
394         MRI.getType(MI.getOperand(1).getReg()).getScalarSizeInBits());
395 
396     SmallVector<unsigned, 2> SrcRegs;
397     extractParts(MI.getOperand(0).getReg(), NarrowTy, NumParts, SrcRegs);
398 
399     for (int i = 0; i < NumParts; ++i) {
400       unsigned DstReg = 0;
401       unsigned Adjustment = i * NarrowSize / 8;
402 
403       MIRBuilder.materializeGEP(DstReg, MI.getOperand(1).getReg(), OffsetTy,
404                                 Adjustment);
405 
406       // TODO: This is conservatively correct, but we probably want to split the
407       // memory operands in the future.
408       MIRBuilder.buildStore(SrcRegs[i], DstReg, **MI.memoperands_begin());
409     }
410     MI.eraseFromParent();
411     return Legalized;
412   }
413   case TargetOpcode::G_CONSTANT: {
414     // FIXME: add support for when SizeOp0 isn't an exact multiple of
415     // NarrowSize.
416     if (SizeOp0 % NarrowSize != 0)
417       return UnableToLegalize;
418     int NumParts = SizeOp0 / NarrowSize;
419     const APInt &Cst = MI.getOperand(1).getCImm()->getValue();
420     LLVMContext &Ctx = MIRBuilder.getMF().getFunction().getContext();
421 
422     SmallVector<unsigned, 2> DstRegs;
423     for (int i = 0; i < NumParts; ++i) {
424       unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
425       ConstantInt *CI =
426           ConstantInt::get(Ctx, Cst.lshr(NarrowSize * i).trunc(NarrowSize));
427       MIRBuilder.buildConstant(DstReg, *CI);
428       DstRegs.push_back(DstReg);
429     }
430     unsigned DstReg = MI.getOperand(0).getReg();
431     MIRBuilder.buildMerge(DstReg, DstRegs);
432     MI.eraseFromParent();
433     return Legalized;
434   }
435   case TargetOpcode::G_OR: {
436     // Legalize bitwise operation:
437     // A = BinOp<Ty> B, C
438     // into:
439     // B1, ..., BN = G_UNMERGE_VALUES B
440     // C1, ..., CN = G_UNMERGE_VALUES C
441     // A1 = BinOp<Ty/N> B1, C2
442     // ...
443     // AN = BinOp<Ty/N> BN, CN
444     // A = G_MERGE_VALUES A1, ..., AN
445 
446     // FIXME: add support for when SizeOp0 isn't an exact multiple of
447     // NarrowSize.
448     if (SizeOp0 % NarrowSize != 0)
449       return UnableToLegalize;
450     int NumParts = SizeOp0 / NarrowSize;
451 
452     // List the registers where the destination will be scattered.
453     SmallVector<unsigned, 2> DstRegs;
454     // List the registers where the first argument will be split.
455     SmallVector<unsigned, 2> SrcsReg1;
456     // List the registers where the second argument will be split.
457     SmallVector<unsigned, 2> SrcsReg2;
458     // Create all the temporary registers.
459     for (int i = 0; i < NumParts; ++i) {
460       unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
461       unsigned SrcReg1 = MRI.createGenericVirtualRegister(NarrowTy);
462       unsigned SrcReg2 = MRI.createGenericVirtualRegister(NarrowTy);
463 
464       DstRegs.push_back(DstReg);
465       SrcsReg1.push_back(SrcReg1);
466       SrcsReg2.push_back(SrcReg2);
467     }
468     // Explode the big arguments into smaller chunks.
469     MIRBuilder.buildUnmerge(SrcsReg1, MI.getOperand(1).getReg());
470     MIRBuilder.buildUnmerge(SrcsReg2, MI.getOperand(2).getReg());
471 
472     // Do the operation on each small part.
473     for (int i = 0; i < NumParts; ++i)
474       MIRBuilder.buildOr(DstRegs[i], SrcsReg1[i], SrcsReg2[i]);
475 
476     // Gather the destination registers into the final destination.
477     unsigned DstReg = MI.getOperand(0).getReg();
478     MIRBuilder.buildMerge(DstReg, DstRegs);
479     MI.eraseFromParent();
480     return Legalized;
481   }
482   }
483 }
484 
485 LegalizerHelper::LegalizeResult
486 LegalizerHelper::widenScalar(MachineInstr &MI, unsigned TypeIdx, LLT WideTy) {
487   MIRBuilder.setInstr(MI);
488 
489   switch (MI.getOpcode()) {
490   default:
491     return UnableToLegalize;
492   case TargetOpcode::G_ADD:
493   case TargetOpcode::G_AND:
494   case TargetOpcode::G_MUL:
495   case TargetOpcode::G_OR:
496   case TargetOpcode::G_XOR:
497   case TargetOpcode::G_SUB:
498   case TargetOpcode::G_SHL: {
499     // Perform operation at larger width (any extension is fine here, high bits
500     // don't affect the result) and then truncate the result back to the
501     // original type.
502     unsigned Src1Ext = MRI.createGenericVirtualRegister(WideTy);
503     unsigned Src2Ext = MRI.createGenericVirtualRegister(WideTy);
504     MIRBuilder.buildAnyExt(Src1Ext, MI.getOperand(1).getReg());
505     MIRBuilder.buildAnyExt(Src2Ext, MI.getOperand(2).getReg());
506 
507     unsigned DstExt = MRI.createGenericVirtualRegister(WideTy);
508     MIRBuilder.buildInstr(MI.getOpcode())
509         .addDef(DstExt)
510         .addUse(Src1Ext)
511         .addUse(Src2Ext);
512 
513     MIRBuilder.buildTrunc(MI.getOperand(0).getReg(), DstExt);
514     MI.eraseFromParent();
515     return Legalized;
516   }
517   case TargetOpcode::G_SDIV:
518   case TargetOpcode::G_UDIV:
519   case TargetOpcode::G_SREM:
520   case TargetOpcode::G_UREM:
521   case TargetOpcode::G_ASHR:
522   case TargetOpcode::G_LSHR: {
523     unsigned ExtOp = MI.getOpcode() == TargetOpcode::G_SDIV ||
524                              MI.getOpcode() == TargetOpcode::G_SREM ||
525                              MI.getOpcode() == TargetOpcode::G_ASHR
526                          ? TargetOpcode::G_SEXT
527                          : TargetOpcode::G_ZEXT;
528 
529     unsigned LHSExt = MRI.createGenericVirtualRegister(WideTy);
530     MIRBuilder.buildInstr(ExtOp).addDef(LHSExt).addUse(
531         MI.getOperand(1).getReg());
532 
533     unsigned RHSExt = MRI.createGenericVirtualRegister(WideTy);
534     MIRBuilder.buildInstr(ExtOp).addDef(RHSExt).addUse(
535         MI.getOperand(2).getReg());
536 
537     unsigned ResExt = MRI.createGenericVirtualRegister(WideTy);
538     MIRBuilder.buildInstr(MI.getOpcode())
539         .addDef(ResExt)
540         .addUse(LHSExt)
541         .addUse(RHSExt);
542 
543     MIRBuilder.buildTrunc(MI.getOperand(0).getReg(), ResExt);
544     MI.eraseFromParent();
545     return Legalized;
546   }
547   case TargetOpcode::G_SELECT: {
548     if (TypeIdx != 0)
549       return UnableToLegalize;
550 
551     // Perform operation at larger width (any extension is fine here, high bits
552     // don't affect the result) and then truncate the result back to the
553     // original type.
554     unsigned Src1Ext = MRI.createGenericVirtualRegister(WideTy);
555     unsigned Src2Ext = MRI.createGenericVirtualRegister(WideTy);
556     MIRBuilder.buildAnyExt(Src1Ext, MI.getOperand(2).getReg());
557     MIRBuilder.buildAnyExt(Src2Ext, MI.getOperand(3).getReg());
558 
559     unsigned DstExt = MRI.createGenericVirtualRegister(WideTy);
560     MIRBuilder.buildInstr(TargetOpcode::G_SELECT)
561         .addDef(DstExt)
562         .addReg(MI.getOperand(1).getReg())
563         .addUse(Src1Ext)
564         .addUse(Src2Ext);
565 
566     MIRBuilder.buildTrunc(MI.getOperand(0).getReg(), DstExt);
567     MI.eraseFromParent();
568     return Legalized;
569   }
570   case TargetOpcode::G_FPTOSI:
571   case TargetOpcode::G_FPTOUI: {
572     if (TypeIdx != 0)
573       return UnableToLegalize;
574 
575     unsigned DstExt = MRI.createGenericVirtualRegister(WideTy);
576     MIRBuilder.buildInstr(MI.getOpcode())
577         .addDef(DstExt)
578         .addUse(MI.getOperand(1).getReg());
579 
580     MIRBuilder.buildTrunc(MI.getOperand(0).getReg(), DstExt);
581     MI.eraseFromParent();
582     return Legalized;
583   }
584   case TargetOpcode::G_SITOFP:
585   case TargetOpcode::G_UITOFP: {
586     if (TypeIdx != 1)
587       return UnableToLegalize;
588 
589     unsigned Src = MI.getOperand(1).getReg();
590     unsigned SrcExt = MRI.createGenericVirtualRegister(WideTy);
591 
592     if (MI.getOpcode() == TargetOpcode::G_SITOFP) {
593       MIRBuilder.buildSExt(SrcExt, Src);
594     } else {
595       assert(MI.getOpcode() == TargetOpcode::G_UITOFP && "Unexpected conv op");
596       MIRBuilder.buildZExt(SrcExt, Src);
597     }
598 
599     MIRBuilder.buildInstr(MI.getOpcode())
600         .addDef(MI.getOperand(0).getReg())
601         .addUse(SrcExt);
602 
603     MI.eraseFromParent();
604     return Legalized;
605   }
606   case TargetOpcode::G_INSERT: {
607     if (TypeIdx != 0)
608       return UnableToLegalize;
609 
610     unsigned Src = MI.getOperand(1).getReg();
611     unsigned SrcExt = MRI.createGenericVirtualRegister(WideTy);
612     MIRBuilder.buildAnyExt(SrcExt, Src);
613 
614     unsigned DstExt = MRI.createGenericVirtualRegister(WideTy);
615     auto MIB = MIRBuilder.buildInsert(DstExt, SrcExt, MI.getOperand(2).getReg(),
616                                       MI.getOperand(3).getImm());
617     for (unsigned OpNum = 4; OpNum < MI.getNumOperands(); OpNum += 2) {
618       MIB.addReg(MI.getOperand(OpNum).getReg());
619       MIB.addImm(MI.getOperand(OpNum + 1).getImm());
620     }
621 
622     MIRBuilder.buildTrunc(MI.getOperand(0).getReg(), DstExt);
623     MI.eraseFromParent();
624     return Legalized;
625   }
626   case TargetOpcode::G_LOAD: {
627     assert(alignTo(MRI.getType(MI.getOperand(0).getReg()).getSizeInBits(), 8) ==
628                WideTy.getSizeInBits() &&
629            "illegal to increase number of bytes loaded");
630 
631     unsigned DstExt = MRI.createGenericVirtualRegister(WideTy);
632     MIRBuilder.buildLoad(DstExt, MI.getOperand(1).getReg(),
633                          **MI.memoperands_begin());
634     MIRBuilder.buildTrunc(MI.getOperand(0).getReg(), DstExt);
635     MI.eraseFromParent();
636     return Legalized;
637   }
638   case TargetOpcode::G_STORE: {
639     if (MRI.getType(MI.getOperand(0).getReg()) != LLT::scalar(1) ||
640         WideTy != LLT::scalar(8))
641       return UnableToLegalize;
642 
643     auto &TLI = *MIRBuilder.getMF().getSubtarget().getTargetLowering();
644     auto Content = TLI.getBooleanContents(false, false);
645 
646     unsigned ExtOp = TargetOpcode::G_ANYEXT;
647     if (Content == TargetLoweringBase::ZeroOrOneBooleanContent)
648       ExtOp = TargetOpcode::G_ZEXT;
649     else if (Content == TargetLoweringBase::ZeroOrNegativeOneBooleanContent)
650       ExtOp = TargetOpcode::G_SEXT;
651     else
652       ExtOp = TargetOpcode::G_ANYEXT;
653 
654     unsigned SrcExt = MRI.createGenericVirtualRegister(WideTy);
655     MIRBuilder.buildInstr(ExtOp).addDef(SrcExt).addUse(
656         MI.getOperand(0).getReg());
657     MIRBuilder.buildStore(SrcExt, MI.getOperand(1).getReg(),
658                           **MI.memoperands_begin());
659     MI.eraseFromParent();
660     return Legalized;
661   }
662   case TargetOpcode::G_CONSTANT: {
663     unsigned DstExt = MRI.createGenericVirtualRegister(WideTy);
664     MIRBuilder.buildConstant(DstExt, *MI.getOperand(1).getCImm());
665     MIRBuilder.buildTrunc(MI.getOperand(0).getReg(), DstExt);
666     MI.eraseFromParent();
667     return Legalized;
668   }
669   case TargetOpcode::G_FCONSTANT: {
670     unsigned DstExt = MRI.createGenericVirtualRegister(WideTy);
671     MIRBuilder.buildFConstant(DstExt, *MI.getOperand(1).getFPImm());
672     MIRBuilder.buildFPTrunc(MI.getOperand(0).getReg(), DstExt);
673     MI.eraseFromParent();
674     return Legalized;
675   }
676   case TargetOpcode::G_BRCOND: {
677     unsigned TstExt = MRI.createGenericVirtualRegister(WideTy);
678     MIRBuilder.buildAnyExt(TstExt, MI.getOperand(0).getReg());
679     MIRBuilder.buildBrCond(TstExt, *MI.getOperand(1).getMBB());
680     MI.eraseFromParent();
681     return Legalized;
682   }
683   case TargetOpcode::G_FCMP: {
684     unsigned Op0Ext, Op1Ext, DstReg;
685     unsigned Cmp1 = MI.getOperand(2).getReg();
686     unsigned Cmp2 = MI.getOperand(3).getReg();
687     if (TypeIdx == 0) {
688       Op0Ext = Cmp1;
689       Op1Ext = Cmp2;
690       DstReg = MRI.createGenericVirtualRegister(WideTy);
691     } else {
692       Op0Ext = MRI.createGenericVirtualRegister(WideTy);
693       Op1Ext = MRI.createGenericVirtualRegister(WideTy);
694       DstReg = MI.getOperand(0).getReg();
695       MIRBuilder.buildInstr(TargetOpcode::G_FPEXT, Op0Ext, Cmp1);
696       MIRBuilder.buildInstr(TargetOpcode::G_FPEXT, Op1Ext, Cmp2);
697     }
698     MIRBuilder.buildFCmp(
699         static_cast<CmpInst::Predicate>(MI.getOperand(1).getPredicate()),
700         DstReg, Op0Ext, Op1Ext);
701     if (TypeIdx == 0)
702       MIRBuilder.buildInstr(TargetOpcode::G_TRUNC, MI.getOperand(0).getReg(),
703                             DstReg);
704     MI.eraseFromParent();
705     return Legalized;
706   }
707   case TargetOpcode::G_ICMP: {
708     bool IsSigned = CmpInst::isSigned(
709         static_cast<CmpInst::Predicate>(MI.getOperand(1).getPredicate()));
710     unsigned Cmp1 = MI.getOperand(2).getReg();
711     unsigned Cmp2 = MI.getOperand(3).getReg();
712     unsigned Op0Ext, Op1Ext, DstReg;
713     if (TypeIdx == 0) {
714       Op0Ext = Cmp1;
715       Op1Ext = Cmp2;
716       DstReg = MRI.createGenericVirtualRegister(WideTy);
717     } else {
718       Op0Ext = MRI.createGenericVirtualRegister(WideTy);
719       Op1Ext = MRI.createGenericVirtualRegister(WideTy);
720       DstReg = MI.getOperand(0).getReg();
721       if (IsSigned) {
722         MIRBuilder.buildSExt(Op0Ext, Cmp1);
723         MIRBuilder.buildSExt(Op1Ext, Cmp2);
724       } else {
725         MIRBuilder.buildZExt(Op0Ext, Cmp1);
726         MIRBuilder.buildZExt(Op1Ext, Cmp2);
727       }
728     }
729     MIRBuilder.buildICmp(
730         static_cast<CmpInst::Predicate>(MI.getOperand(1).getPredicate()),
731         DstReg, Op0Ext, Op1Ext);
732     if (TypeIdx == 0)
733       MIRBuilder.buildInstr(TargetOpcode::G_TRUNC, MI.getOperand(0).getReg(),
734                             DstReg);
735     MI.eraseFromParent();
736     return Legalized;
737   }
738   case TargetOpcode::G_GEP: {
739     assert(TypeIdx == 1 && "unable to legalize pointer of GEP");
740     unsigned OffsetExt = MRI.createGenericVirtualRegister(WideTy);
741     MIRBuilder.buildSExt(OffsetExt, MI.getOperand(2).getReg());
742     MI.getOperand(2).setReg(OffsetExt);
743     return Legalized;
744   }
745   case TargetOpcode::G_PHI: {
746     assert(TypeIdx == 0 && "Expecting only Idx 0");
747     auto getExtendedReg = [&](unsigned Reg, MachineBasicBlock &MBB) {
748       auto FirstTermIt = MBB.getFirstTerminator();
749       MIRBuilder.setInsertPt(MBB, FirstTermIt);
750       MachineInstr *DefMI = MRI.getVRegDef(Reg);
751       MachineInstrBuilder MIB;
752       if (DefMI->getOpcode() == TargetOpcode::G_TRUNC)
753         MIB = MIRBuilder.buildAnyExtOrTrunc(WideTy,
754                                             DefMI->getOperand(1).getReg());
755       else
756         MIB = MIRBuilder.buildAnyExt(WideTy, Reg);
757       return MIB->getOperand(0).getReg();
758     };
759     auto MIB = MIRBuilder.buildInstr(TargetOpcode::G_PHI, WideTy);
760     for (auto OpIt = MI.operands_begin() + 1, OpE = MI.operands_end();
761          OpIt != OpE;) {
762       unsigned Reg = OpIt++->getReg();
763       MachineBasicBlock *OpMBB = OpIt++->getMBB();
764       MIB.addReg(getExtendedReg(Reg, *OpMBB));
765       MIB.addMBB(OpMBB);
766     }
767     auto *MBB = MI.getParent();
768     MIRBuilder.setInsertPt(*MBB, MBB->getFirstNonPHI());
769     MIRBuilder.buildTrunc(MI.getOperand(0).getReg(),
770                           MIB->getOperand(0).getReg());
771     MI.eraseFromParent();
772     return Legalized;
773   }
774   }
775 }
776 
777 LegalizerHelper::LegalizeResult
778 LegalizerHelper::lower(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
779   using namespace TargetOpcode;
780   MIRBuilder.setInstr(MI);
781 
782   switch(MI.getOpcode()) {
783   default:
784     return UnableToLegalize;
785   case TargetOpcode::G_SREM:
786   case TargetOpcode::G_UREM: {
787     unsigned QuotReg = MRI.createGenericVirtualRegister(Ty);
788     MIRBuilder.buildInstr(MI.getOpcode() == G_SREM ? G_SDIV : G_UDIV)
789         .addDef(QuotReg)
790         .addUse(MI.getOperand(1).getReg())
791         .addUse(MI.getOperand(2).getReg());
792 
793     unsigned ProdReg = MRI.createGenericVirtualRegister(Ty);
794     MIRBuilder.buildMul(ProdReg, QuotReg, MI.getOperand(2).getReg());
795     MIRBuilder.buildSub(MI.getOperand(0).getReg(), MI.getOperand(1).getReg(),
796                         ProdReg);
797     MI.eraseFromParent();
798     return Legalized;
799   }
800   case TargetOpcode::G_SMULO:
801   case TargetOpcode::G_UMULO: {
802     // Generate G_UMULH/G_SMULH to check for overflow and a normal G_MUL for the
803     // result.
804     unsigned Res = MI.getOperand(0).getReg();
805     unsigned Overflow = MI.getOperand(1).getReg();
806     unsigned LHS = MI.getOperand(2).getReg();
807     unsigned RHS = MI.getOperand(3).getReg();
808 
809     MIRBuilder.buildMul(Res, LHS, RHS);
810 
811     unsigned Opcode = MI.getOpcode() == TargetOpcode::G_SMULO
812                           ? TargetOpcode::G_SMULH
813                           : TargetOpcode::G_UMULH;
814 
815     unsigned HiPart = MRI.createGenericVirtualRegister(Ty);
816     MIRBuilder.buildInstr(Opcode)
817       .addDef(HiPart)
818       .addUse(LHS)
819       .addUse(RHS);
820 
821     unsigned Zero = MRI.createGenericVirtualRegister(Ty);
822     MIRBuilder.buildConstant(Zero, 0);
823 
824     // For *signed* multiply, overflow is detected by checking:
825     // (hi != (lo >> bitwidth-1))
826     if (Opcode == TargetOpcode::G_SMULH) {
827       unsigned Shifted = MRI.createGenericVirtualRegister(Ty);
828       unsigned ShiftAmt = MRI.createGenericVirtualRegister(Ty);
829       MIRBuilder.buildConstant(ShiftAmt, Ty.getSizeInBits() - 1);
830       MIRBuilder.buildInstr(TargetOpcode::G_ASHR)
831         .addDef(Shifted)
832         .addUse(Res)
833         .addUse(ShiftAmt);
834       MIRBuilder.buildICmp(CmpInst::ICMP_NE, Overflow, HiPart, Shifted);
835     } else {
836       MIRBuilder.buildICmp(CmpInst::ICMP_NE, Overflow, HiPart, Zero);
837     }
838     MI.eraseFromParent();
839     return Legalized;
840   }
841   case TargetOpcode::G_FNEG: {
842     // TODO: Handle vector types once we are able to
843     // represent them.
844     if (Ty.isVector())
845       return UnableToLegalize;
846     unsigned Res = MI.getOperand(0).getReg();
847     Type *ZeroTy;
848     LLVMContext &Ctx = MIRBuilder.getMF().getFunction().getContext();
849     switch (Ty.getSizeInBits()) {
850     case 16:
851       ZeroTy = Type::getHalfTy(Ctx);
852       break;
853     case 32:
854       ZeroTy = Type::getFloatTy(Ctx);
855       break;
856     case 64:
857       ZeroTy = Type::getDoubleTy(Ctx);
858       break;
859     case 128:
860       ZeroTy = Type::getFP128Ty(Ctx);
861       break;
862     default:
863       llvm_unreachable("unexpected floating-point type");
864     }
865     ConstantFP &ZeroForNegation =
866         *cast<ConstantFP>(ConstantFP::getZeroValueForNegation(ZeroTy));
867     unsigned Zero = MRI.createGenericVirtualRegister(Ty);
868     MIRBuilder.buildFConstant(Zero, ZeroForNegation);
869     MIRBuilder.buildInstr(TargetOpcode::G_FSUB)
870         .addDef(Res)
871         .addUse(Zero)
872         .addUse(MI.getOperand(1).getReg());
873     MI.eraseFromParent();
874     return Legalized;
875   }
876   case TargetOpcode::G_FSUB: {
877     // Lower (G_FSUB LHS, RHS) to (G_FADD LHS, (G_FNEG RHS)).
878     // First, check if G_FNEG is marked as Lower. If so, we may
879     // end up with an infinite loop as G_FSUB is used to legalize G_FNEG.
880     if (LI.getAction({G_FNEG, Ty}).first == LegalizerInfo::Lower)
881       return UnableToLegalize;
882     unsigned Res = MI.getOperand(0).getReg();
883     unsigned LHS = MI.getOperand(1).getReg();
884     unsigned RHS = MI.getOperand(2).getReg();
885     unsigned Neg = MRI.createGenericVirtualRegister(Ty);
886     MIRBuilder.buildInstr(TargetOpcode::G_FNEG).addDef(Neg).addUse(RHS);
887     MIRBuilder.buildInstr(TargetOpcode::G_FADD)
888         .addDef(Res)
889         .addUse(LHS)
890         .addUse(Neg);
891     MI.eraseFromParent();
892     return Legalized;
893   }
894   case TargetOpcode::G_ATOMIC_CMPXCHG_WITH_SUCCESS: {
895     unsigned OldValRes = MI.getOperand(0).getReg();
896     unsigned SuccessRes = MI.getOperand(1).getReg();
897     unsigned Addr = MI.getOperand(2).getReg();
898     unsigned CmpVal = MI.getOperand(3).getReg();
899     unsigned NewVal = MI.getOperand(4).getReg();
900     MIRBuilder.buildAtomicCmpXchg(OldValRes, Addr, CmpVal, NewVal,
901                                   **MI.memoperands_begin());
902     MIRBuilder.buildICmp(CmpInst::ICMP_EQ, SuccessRes, OldValRes, CmpVal);
903     MI.eraseFromParent();
904     return Legalized;
905   }
906   }
907 }
908 
909 LegalizerHelper::LegalizeResult
910 LegalizerHelper::fewerElementsVector(MachineInstr &MI, unsigned TypeIdx,
911                                      LLT NarrowTy) {
912   // FIXME: Don't know how to handle secondary types yet.
913   if (TypeIdx != 0)
914     return UnableToLegalize;
915   switch (MI.getOpcode()) {
916   default:
917     return UnableToLegalize;
918   case TargetOpcode::G_ADD: {
919     unsigned NarrowSize = NarrowTy.getSizeInBits();
920     unsigned DstReg = MI.getOperand(0).getReg();
921     unsigned Size = MRI.getType(DstReg).getSizeInBits();
922     int NumParts = Size / NarrowSize;
923     // FIXME: Don't know how to handle the situation where the small vectors
924     // aren't all the same size yet.
925     if (Size % NarrowSize != 0)
926       return UnableToLegalize;
927 
928     MIRBuilder.setInstr(MI);
929 
930     SmallVector<unsigned, 2> Src1Regs, Src2Regs, DstRegs;
931     extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs);
932     extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs);
933 
934     for (int i = 0; i < NumParts; ++i) {
935       unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
936       MIRBuilder.buildAdd(DstReg, Src1Regs[i], Src2Regs[i]);
937       DstRegs.push_back(DstReg);
938     }
939 
940     MIRBuilder.buildMerge(DstReg, DstRegs);
941     MI.eraseFromParent();
942     return Legalized;
943   }
944   }
945 }
946