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