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