1 //===-- llvm/CodeGen/GlobalISel/LegalizerHelper.cpp -----------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file This file implements the LegalizerHelper class to legalize
10 /// individual instructions and the LegalizeMachineIR wrapper pass for the
11 /// primary legalization.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
16 #include "llvm/CodeGen/GlobalISel/CallLowering.h"
17 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
18 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
19 #include "llvm/CodeGen/MachineRegisterInfo.h"
20 #include "llvm/CodeGen/TargetFrameLowering.h"
21 #include "llvm/CodeGen/TargetInstrInfo.h"
22 #include "llvm/CodeGen/TargetLowering.h"
23 #include "llvm/CodeGen/TargetSubtargetInfo.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/MathExtras.h"
26 #include "llvm/Support/raw_ostream.h"
27 
28 #define DEBUG_TYPE "legalizer"
29 
30 using namespace llvm;
31 using namespace LegalizeActions;
32 
33 /// Try to break down \p OrigTy into \p NarrowTy sized pieces.
34 ///
35 /// Returns the number of \p NarrowTy elements needed to reconstruct \p OrigTy,
36 /// with any leftover piece as type \p LeftoverTy
37 ///
38 /// Returns -1 in the first element of the pair if the breakdown is not
39 /// satisfiable.
40 static std::pair<int, int>
41 getNarrowTypeBreakDown(LLT OrigTy, LLT NarrowTy, LLT &LeftoverTy) {
42   assert(!LeftoverTy.isValid() && "this is an out argument");
43 
44   unsigned Size = OrigTy.getSizeInBits();
45   unsigned NarrowSize = NarrowTy.getSizeInBits();
46   unsigned NumParts = Size / NarrowSize;
47   unsigned LeftoverSize = Size - NumParts * NarrowSize;
48   assert(Size > NarrowSize);
49 
50   if (LeftoverSize == 0)
51     return {NumParts, 0};
52 
53   if (NarrowTy.isVector()) {
54     unsigned EltSize = OrigTy.getScalarSizeInBits();
55     if (LeftoverSize % EltSize != 0)
56       return {-1, -1};
57     LeftoverTy = LLT::scalarOrVector(LeftoverSize / EltSize, EltSize);
58   } else {
59     LeftoverTy = LLT::scalar(LeftoverSize);
60   }
61 
62   int NumLeftover = LeftoverSize / LeftoverTy.getSizeInBits();
63   return std::make_pair(NumParts, NumLeftover);
64 }
65 
66 static LLT getGCDType(LLT OrigTy, LLT TargetTy) {
67   if (OrigTy.isVector() && TargetTy.isVector()) {
68     assert(OrigTy.getElementType() == TargetTy.getElementType());
69     int GCD = greatestCommonDivisor(OrigTy.getNumElements(),
70                                     TargetTy.getNumElements());
71     return LLT::scalarOrVector(GCD, OrigTy.getElementType());
72   }
73 
74   if (OrigTy.isVector() && !TargetTy.isVector()) {
75     assert(OrigTy.getElementType() == TargetTy);
76     return TargetTy;
77   }
78 
79   assert(!OrigTy.isVector() && !TargetTy.isVector() &&
80          "GCD type of vector and scalar not implemented");
81 
82   int GCD = greatestCommonDivisor(OrigTy.getSizeInBits(),
83                                   TargetTy.getSizeInBits());
84   return LLT::scalar(GCD);
85 }
86 
87 static LLT getLCMType(LLT Ty0, LLT Ty1) {
88   if (!Ty0.isVector() && !Ty1.isVector()) {
89     unsigned Mul = Ty0.getSizeInBits() * Ty1.getSizeInBits();
90     int GCDSize = greatestCommonDivisor(Ty0.getSizeInBits(),
91                                         Ty1.getSizeInBits());
92     return LLT::scalar(Mul / GCDSize);
93   }
94 
95   if (Ty0.isVector() && !Ty1.isVector()) {
96     assert(Ty0.getElementType() == Ty1 && "not yet handled");
97     return Ty0;
98   }
99 
100   if (Ty1.isVector() && !Ty0.isVector()) {
101     assert(Ty1.getElementType() == Ty0 && "not yet handled");
102     return Ty1;
103   }
104 
105   if (Ty0.isVector() && Ty1.isVector()) {
106     assert(Ty0.getElementType() == Ty1.getElementType() && "not yet handled");
107 
108     int GCDElts = greatestCommonDivisor(Ty0.getNumElements(),
109                                         Ty1.getNumElements());
110 
111     int Mul = Ty0.getNumElements() * Ty1.getNumElements();
112     return LLT::vector(Mul / GCDElts, Ty0.getElementType());
113   }
114 
115   llvm_unreachable("not yet handled");
116 }
117 
118 static Type *getFloatTypeForLLT(LLVMContext &Ctx, LLT Ty) {
119 
120   if (!Ty.isScalar())
121     return nullptr;
122 
123   switch (Ty.getSizeInBits()) {
124   case 16:
125     return Type::getHalfTy(Ctx);
126   case 32:
127     return Type::getFloatTy(Ctx);
128   case 64:
129     return Type::getDoubleTy(Ctx);
130   case 128:
131     return Type::getFP128Ty(Ctx);
132   default:
133     return nullptr;
134   }
135 }
136 
137 LegalizerHelper::LegalizerHelper(MachineFunction &MF,
138                                  GISelChangeObserver &Observer,
139                                  MachineIRBuilder &Builder)
140     : MIRBuilder(Builder), MRI(MF.getRegInfo()),
141       LI(*MF.getSubtarget().getLegalizerInfo()), Observer(Observer) {
142   MIRBuilder.setMF(MF);
143   MIRBuilder.setChangeObserver(Observer);
144 }
145 
146 LegalizerHelper::LegalizerHelper(MachineFunction &MF, const LegalizerInfo &LI,
147                                  GISelChangeObserver &Observer,
148                                  MachineIRBuilder &B)
149     : MIRBuilder(B), MRI(MF.getRegInfo()), LI(LI), Observer(Observer) {
150   MIRBuilder.setMF(MF);
151   MIRBuilder.setChangeObserver(Observer);
152 }
153 LegalizerHelper::LegalizeResult
154 LegalizerHelper::legalizeInstrStep(MachineInstr &MI) {
155   LLVM_DEBUG(dbgs() << "Legalizing: "; MI.print(dbgs()));
156 
157   if (MI.getOpcode() == TargetOpcode::G_INTRINSIC ||
158       MI.getOpcode() == TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS)
159     return LI.legalizeIntrinsic(MI, MIRBuilder, Observer) ? Legalized
160                                                           : UnableToLegalize;
161   auto Step = LI.getAction(MI, MRI);
162   switch (Step.Action) {
163   case Legal:
164     LLVM_DEBUG(dbgs() << ".. Already legal\n");
165     return AlreadyLegal;
166   case Libcall:
167     LLVM_DEBUG(dbgs() << ".. Convert to libcall\n");
168     return libcall(MI);
169   case NarrowScalar:
170     LLVM_DEBUG(dbgs() << ".. Narrow scalar\n");
171     return narrowScalar(MI, Step.TypeIdx, Step.NewType);
172   case WidenScalar:
173     LLVM_DEBUG(dbgs() << ".. Widen scalar\n");
174     return widenScalar(MI, Step.TypeIdx, Step.NewType);
175   case Lower:
176     LLVM_DEBUG(dbgs() << ".. Lower\n");
177     return lower(MI, Step.TypeIdx, Step.NewType);
178   case FewerElements:
179     LLVM_DEBUG(dbgs() << ".. Reduce number of elements\n");
180     return fewerElementsVector(MI, Step.TypeIdx, Step.NewType);
181   case MoreElements:
182     LLVM_DEBUG(dbgs() << ".. Increase number of elements\n");
183     return moreElementsVector(MI, Step.TypeIdx, Step.NewType);
184   case Custom:
185     LLVM_DEBUG(dbgs() << ".. Custom legalization\n");
186     return LI.legalizeCustom(MI, MRI, MIRBuilder, Observer) ? Legalized
187                                                             : UnableToLegalize;
188   default:
189     LLVM_DEBUG(dbgs() << ".. Unable to legalize\n");
190     return UnableToLegalize;
191   }
192 }
193 
194 void LegalizerHelper::extractParts(Register Reg, LLT Ty, int NumParts,
195                                    SmallVectorImpl<Register> &VRegs) {
196   for (int i = 0; i < NumParts; ++i)
197     VRegs.push_back(MRI.createGenericVirtualRegister(Ty));
198   MIRBuilder.buildUnmerge(VRegs, Reg);
199 }
200 
201 bool LegalizerHelper::extractParts(Register Reg, LLT RegTy,
202                                    LLT MainTy, LLT &LeftoverTy,
203                                    SmallVectorImpl<Register> &VRegs,
204                                    SmallVectorImpl<Register> &LeftoverRegs) {
205   assert(!LeftoverTy.isValid() && "this is an out argument");
206 
207   unsigned RegSize = RegTy.getSizeInBits();
208   unsigned MainSize = MainTy.getSizeInBits();
209   unsigned NumParts = RegSize / MainSize;
210   unsigned LeftoverSize = RegSize - NumParts * MainSize;
211 
212   // Use an unmerge when possible.
213   if (LeftoverSize == 0) {
214     for (unsigned I = 0; I < NumParts; ++I)
215       VRegs.push_back(MRI.createGenericVirtualRegister(MainTy));
216     MIRBuilder.buildUnmerge(VRegs, Reg);
217     return true;
218   }
219 
220   if (MainTy.isVector()) {
221     unsigned EltSize = MainTy.getScalarSizeInBits();
222     if (LeftoverSize % EltSize != 0)
223       return false;
224     LeftoverTy = LLT::scalarOrVector(LeftoverSize / EltSize, EltSize);
225   } else {
226     LeftoverTy = LLT::scalar(LeftoverSize);
227   }
228 
229   // For irregular sizes, extract the individual parts.
230   for (unsigned I = 0; I != NumParts; ++I) {
231     Register NewReg = MRI.createGenericVirtualRegister(MainTy);
232     VRegs.push_back(NewReg);
233     MIRBuilder.buildExtract(NewReg, Reg, MainSize * I);
234   }
235 
236   for (unsigned Offset = MainSize * NumParts; Offset < RegSize;
237        Offset += LeftoverSize) {
238     Register NewReg = MRI.createGenericVirtualRegister(LeftoverTy);
239     LeftoverRegs.push_back(NewReg);
240     MIRBuilder.buildExtract(NewReg, Reg, Offset);
241   }
242 
243   return true;
244 }
245 
246 void LegalizerHelper::insertParts(Register DstReg,
247                                   LLT ResultTy, LLT PartTy,
248                                   ArrayRef<Register> PartRegs,
249                                   LLT LeftoverTy,
250                                   ArrayRef<Register> LeftoverRegs) {
251   if (!LeftoverTy.isValid()) {
252     assert(LeftoverRegs.empty());
253 
254     if (!ResultTy.isVector()) {
255       MIRBuilder.buildMerge(DstReg, PartRegs);
256       return;
257     }
258 
259     if (PartTy.isVector())
260       MIRBuilder.buildConcatVectors(DstReg, PartRegs);
261     else
262       MIRBuilder.buildBuildVector(DstReg, PartRegs);
263     return;
264   }
265 
266   unsigned PartSize = PartTy.getSizeInBits();
267   unsigned LeftoverPartSize = LeftoverTy.getSizeInBits();
268 
269   Register CurResultReg = MRI.createGenericVirtualRegister(ResultTy);
270   MIRBuilder.buildUndef(CurResultReg);
271 
272   unsigned Offset = 0;
273   for (Register PartReg : PartRegs) {
274     Register NewResultReg = MRI.createGenericVirtualRegister(ResultTy);
275     MIRBuilder.buildInsert(NewResultReg, CurResultReg, PartReg, Offset);
276     CurResultReg = NewResultReg;
277     Offset += PartSize;
278   }
279 
280   for (unsigned I = 0, E = LeftoverRegs.size(); I != E; ++I) {
281     // Use the original output register for the final insert to avoid a copy.
282     Register NewResultReg = (I + 1 == E) ?
283       DstReg : MRI.createGenericVirtualRegister(ResultTy);
284 
285     MIRBuilder.buildInsert(NewResultReg, CurResultReg, LeftoverRegs[I], Offset);
286     CurResultReg = NewResultReg;
287     Offset += LeftoverPartSize;
288   }
289 }
290 
291 /// Return the result registers of G_UNMERGE_VALUES \p MI in \p Regs
292 static void getUnmergeResults(SmallVectorImpl<Register> &Regs,
293                               const MachineInstr &MI) {
294   assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES);
295 
296   const int NumResults = MI.getNumOperands() - 1;
297   Regs.resize(NumResults);
298   for (int I = 0; I != NumResults; ++I)
299     Regs[I] = MI.getOperand(I).getReg();
300 }
301 
302 LLT LegalizerHelper::extractGCDType(SmallVectorImpl<Register> &Parts, LLT DstTy,
303                                     LLT NarrowTy, Register SrcReg) {
304   LLT SrcTy = MRI.getType(SrcReg);
305 
306   LLT GCDTy = getGCDType(DstTy, getGCDType(SrcTy, NarrowTy));
307   if (SrcTy == GCDTy) {
308     // If the source already evenly divides the result type, we don't need to do
309     // anything.
310     Parts.push_back(SrcReg);
311   } else {
312     // Need to split into common type sized pieces.
313     auto Unmerge = MIRBuilder.buildUnmerge(GCDTy, SrcReg);
314     getUnmergeResults(Parts, *Unmerge);
315   }
316 
317   return GCDTy;
318 }
319 
320 LLT LegalizerHelper::buildLCMMergePieces(LLT DstTy, LLT NarrowTy, LLT GCDTy,
321                                          SmallVectorImpl<Register> &VRegs,
322                                          unsigned PadStrategy) {
323   LLT LCMTy = getLCMType(DstTy, NarrowTy);
324 
325   int NumParts = LCMTy.getSizeInBits() / NarrowTy.getSizeInBits();
326   int NumSubParts = NarrowTy.getSizeInBits() / GCDTy.getSizeInBits();
327   int NumOrigSrc = VRegs.size();
328 
329   Register PadReg;
330 
331   // Get a value we can use to pad the source value if the sources won't evenly
332   // cover the result type.
333   if (NumOrigSrc < NumParts * NumSubParts) {
334     if (PadStrategy == TargetOpcode::G_ZEXT)
335       PadReg = MIRBuilder.buildConstant(GCDTy, 0).getReg(0);
336     else if (PadStrategy == TargetOpcode::G_ANYEXT)
337       PadReg = MIRBuilder.buildUndef(GCDTy).getReg(0);
338     else {
339       assert(PadStrategy == TargetOpcode::G_SEXT);
340 
341       // Shift the sign bit of the low register through the high register.
342       auto ShiftAmt =
343         MIRBuilder.buildConstant(LLT::scalar(64), GCDTy.getSizeInBits() - 1);
344       PadReg = MIRBuilder.buildAShr(GCDTy, VRegs.back(), ShiftAmt).getReg(0);
345     }
346   }
347 
348   // Registers for the final merge to be produced.
349   SmallVector<Register, 4> Remerge(NumParts);
350 
351   // Registers needed for intermediate merges, which will be merged into a
352   // source for Remerge.
353   SmallVector<Register, 4> SubMerge(NumSubParts);
354 
355   // Once we've fully read off the end of the original source bits, we can reuse
356   // the same high bits for remaining padding elements.
357   Register AllPadReg;
358 
359   // Build merges to the LCM type to cover the original result type.
360   for (int I = 0; I != NumParts; ++I) {
361     bool AllMergePartsArePadding = true;
362 
363     // Build the requested merges to the requested type.
364     for (int J = 0; J != NumSubParts; ++J) {
365       int Idx = I * NumSubParts + J;
366       if (Idx >= NumOrigSrc) {
367         SubMerge[J] = PadReg;
368         continue;
369       }
370 
371       SubMerge[J] = VRegs[Idx];
372 
373       // There are meaningful bits here we can't reuse later.
374       AllMergePartsArePadding = false;
375     }
376 
377     // If we've filled up a complete piece with padding bits, we can directly
378     // emit the natural sized constant if applicable, rather than a merge of
379     // smaller constants.
380     if (AllMergePartsArePadding && !AllPadReg) {
381       if (PadStrategy == TargetOpcode::G_ANYEXT)
382         AllPadReg = MIRBuilder.buildUndef(NarrowTy).getReg(0);
383       else if (PadStrategy == TargetOpcode::G_ZEXT)
384         AllPadReg = MIRBuilder.buildConstant(NarrowTy, 0).getReg(0);
385 
386       // If this is a sign extension, we can't materialize a trivial constant
387       // with the right type and have to produce a merge.
388     }
389 
390     if (AllPadReg) {
391       // Avoid creating additional instructions if we're just adding additional
392       // copies of padding bits.
393       Remerge[I] = AllPadReg;
394       continue;
395     }
396 
397     if (NumSubParts == 1)
398       Remerge[I] = SubMerge[0];
399     else
400       Remerge[I] = MIRBuilder.buildMerge(NarrowTy, SubMerge).getReg(0);
401 
402     // In the sign extend padding case, re-use the first all-signbit merge.
403     if (AllMergePartsArePadding && !AllPadReg)
404       AllPadReg = Remerge[I];
405   }
406 
407   VRegs = std::move(Remerge);
408   return LCMTy;
409 }
410 
411 void LegalizerHelper::buildWidenedRemergeToDst(Register DstReg, LLT LCMTy,
412                                                ArrayRef<Register> RemergeRegs) {
413   LLT DstTy = MRI.getType(DstReg);
414 
415   // Create the merge to the widened source, and extract the relevant bits into
416   // the result.
417 
418   if (DstTy == LCMTy) {
419     MIRBuilder.buildMerge(DstReg, RemergeRegs);
420     return;
421   }
422 
423   auto Remerge = MIRBuilder.buildMerge(LCMTy, RemergeRegs);
424   if (DstTy.isScalar() && LCMTy.isScalar()) {
425     MIRBuilder.buildTrunc(DstReg, Remerge);
426     return;
427   }
428 
429   if (LCMTy.isVector()) {
430     MIRBuilder.buildExtract(DstReg, Remerge, 0);
431     return;
432   }
433 
434   llvm_unreachable("unhandled case");
435 }
436 
437 static RTLIB::Libcall getRTLibDesc(unsigned Opcode, unsigned Size) {
438   switch (Opcode) {
439   case TargetOpcode::G_SDIV:
440     assert((Size == 32 || Size == 64 || Size == 128) && "Unsupported size");
441     switch (Size) {
442     case 32:
443       return RTLIB::SDIV_I32;
444     case 64:
445       return RTLIB::SDIV_I64;
446     case 128:
447       return RTLIB::SDIV_I128;
448     default:
449       llvm_unreachable("unexpected size");
450     }
451   case TargetOpcode::G_UDIV:
452     assert((Size == 32 || Size == 64 || Size == 128) && "Unsupported size");
453     switch (Size) {
454     case 32:
455       return RTLIB::UDIV_I32;
456     case 64:
457       return RTLIB::UDIV_I64;
458     case 128:
459       return RTLIB::UDIV_I128;
460     default:
461       llvm_unreachable("unexpected size");
462     }
463   case TargetOpcode::G_SREM:
464     assert((Size == 32 || Size == 64) && "Unsupported size");
465     return Size == 64 ? RTLIB::SREM_I64 : RTLIB::SREM_I32;
466   case TargetOpcode::G_UREM:
467     assert((Size == 32 || Size == 64) && "Unsupported size");
468     return Size == 64 ? RTLIB::UREM_I64 : RTLIB::UREM_I32;
469   case TargetOpcode::G_CTLZ_ZERO_UNDEF:
470     assert(Size == 32 && "Unsupported size");
471     return RTLIB::CTLZ_I32;
472   case TargetOpcode::G_FADD:
473     assert((Size == 32 || Size == 64) && "Unsupported size");
474     return Size == 64 ? RTLIB::ADD_F64 : RTLIB::ADD_F32;
475   case TargetOpcode::G_FSUB:
476     assert((Size == 32 || Size == 64) && "Unsupported size");
477     return Size == 64 ? RTLIB::SUB_F64 : RTLIB::SUB_F32;
478   case TargetOpcode::G_FMUL:
479     assert((Size == 32 || Size == 64) && "Unsupported size");
480     return Size == 64 ? RTLIB::MUL_F64 : RTLIB::MUL_F32;
481   case TargetOpcode::G_FDIV:
482     assert((Size == 32 || Size == 64) && "Unsupported size");
483     return Size == 64 ? RTLIB::DIV_F64 : RTLIB::DIV_F32;
484   case TargetOpcode::G_FEXP:
485     assert((Size == 32 || Size == 64) && "Unsupported size");
486     return Size == 64 ? RTLIB::EXP_F64 : RTLIB::EXP_F32;
487   case TargetOpcode::G_FEXP2:
488     assert((Size == 32 || Size == 64) && "Unsupported size");
489     return Size == 64 ? RTLIB::EXP2_F64 : RTLIB::EXP2_F32;
490   case TargetOpcode::G_FREM:
491     return Size == 64 ? RTLIB::REM_F64 : RTLIB::REM_F32;
492   case TargetOpcode::G_FPOW:
493     return Size == 64 ? RTLIB::POW_F64 : RTLIB::POW_F32;
494   case TargetOpcode::G_FMA:
495     assert((Size == 32 || Size == 64) && "Unsupported size");
496     return Size == 64 ? RTLIB::FMA_F64 : RTLIB::FMA_F32;
497   case TargetOpcode::G_FSIN:
498     assert((Size == 32 || Size == 64 || Size == 128) && "Unsupported size");
499     return Size == 128 ? RTLIB::SIN_F128
500                        : Size == 64 ? RTLIB::SIN_F64 : RTLIB::SIN_F32;
501   case TargetOpcode::G_FCOS:
502     assert((Size == 32 || Size == 64 || Size == 128) && "Unsupported size");
503     return Size == 128 ? RTLIB::COS_F128
504                        : Size == 64 ? RTLIB::COS_F64 : RTLIB::COS_F32;
505   case TargetOpcode::G_FLOG10:
506     assert((Size == 32 || Size == 64 || Size == 128) && "Unsupported size");
507     return Size == 128 ? RTLIB::LOG10_F128
508                        : Size == 64 ? RTLIB::LOG10_F64 : RTLIB::LOG10_F32;
509   case TargetOpcode::G_FLOG:
510     assert((Size == 32 || Size == 64 || Size == 128) && "Unsupported size");
511     return Size == 128 ? RTLIB::LOG_F128
512                        : Size == 64 ? RTLIB::LOG_F64 : RTLIB::LOG_F32;
513   case TargetOpcode::G_FLOG2:
514     assert((Size == 32 || Size == 64 || Size == 128) && "Unsupported size");
515     return Size == 128 ? RTLIB::LOG2_F128
516                        : Size == 64 ? RTLIB::LOG2_F64 : RTLIB::LOG2_F32;
517   case TargetOpcode::G_FCEIL:
518     assert((Size == 32 || Size == 64) && "Unsupported size");
519     return Size == 64 ? RTLIB::CEIL_F64 : RTLIB::CEIL_F32;
520   case TargetOpcode::G_FFLOOR:
521     assert((Size == 32 || Size == 64) && "Unsupported size");
522     return Size == 64 ? RTLIB::FLOOR_F64 : RTLIB::FLOOR_F32;
523   }
524   llvm_unreachable("Unknown libcall function");
525 }
526 
527 /// True if an instruction is in tail position in its caller. Intended for
528 /// legalizing libcalls as tail calls when possible.
529 static bool isLibCallInTailPosition(MachineInstr &MI) {
530   const Function &F = MI.getParent()->getParent()->getFunction();
531 
532   // Conservatively require the attributes of the call to match those of
533   // the return. Ignore NoAlias and NonNull because they don't affect the
534   // call sequence.
535   AttributeList CallerAttrs = F.getAttributes();
536   if (AttrBuilder(CallerAttrs, AttributeList::ReturnIndex)
537           .removeAttribute(Attribute::NoAlias)
538           .removeAttribute(Attribute::NonNull)
539           .hasAttributes())
540     return false;
541 
542   // It's not safe to eliminate the sign / zero extension of the return value.
543   if (CallerAttrs.hasAttribute(AttributeList::ReturnIndex, Attribute::ZExt) ||
544       CallerAttrs.hasAttribute(AttributeList::ReturnIndex, Attribute::SExt))
545     return false;
546 
547   // Only tail call if the following instruction is a standard return.
548   auto &TII = *MI.getMF()->getSubtarget().getInstrInfo();
549   MachineInstr *Next = MI.getNextNode();
550   if (!Next || TII.isTailCall(*Next) || !Next->isReturn())
551     return false;
552 
553   return true;
554 }
555 
556 LegalizerHelper::LegalizeResult
557 llvm::createLibcall(MachineIRBuilder &MIRBuilder, RTLIB::Libcall Libcall,
558                     const CallLowering::ArgInfo &Result,
559                     ArrayRef<CallLowering::ArgInfo> Args) {
560   auto &CLI = *MIRBuilder.getMF().getSubtarget().getCallLowering();
561   auto &TLI = *MIRBuilder.getMF().getSubtarget().getTargetLowering();
562   const char *Name = TLI.getLibcallName(Libcall);
563 
564   CallLowering::CallLoweringInfo Info;
565   Info.CallConv = TLI.getLibcallCallingConv(Libcall);
566   Info.Callee = MachineOperand::CreateES(Name);
567   Info.OrigRet = Result;
568   std::copy(Args.begin(), Args.end(), std::back_inserter(Info.OrigArgs));
569   if (!CLI.lowerCall(MIRBuilder, Info))
570     return LegalizerHelper::UnableToLegalize;
571 
572   return LegalizerHelper::Legalized;
573 }
574 
575 // Useful for libcalls where all operands have the same type.
576 static LegalizerHelper::LegalizeResult
577 simpleLibcall(MachineInstr &MI, MachineIRBuilder &MIRBuilder, unsigned Size,
578               Type *OpType) {
579   auto Libcall = getRTLibDesc(MI.getOpcode(), Size);
580 
581   SmallVector<CallLowering::ArgInfo, 3> Args;
582   for (unsigned i = 1; i < MI.getNumOperands(); i++)
583     Args.push_back({MI.getOperand(i).getReg(), OpType});
584   return createLibcall(MIRBuilder, Libcall, {MI.getOperand(0).getReg(), OpType},
585                        Args);
586 }
587 
588 LegalizerHelper::LegalizeResult
589 llvm::createMemLibcall(MachineIRBuilder &MIRBuilder, MachineRegisterInfo &MRI,
590                        MachineInstr &MI) {
591   assert(MI.getOpcode() == TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS);
592   auto &Ctx = MIRBuilder.getMF().getFunction().getContext();
593 
594   SmallVector<CallLowering::ArgInfo, 3> Args;
595   // Add all the args, except for the last which is an imm denoting 'tail'.
596   for (unsigned i = 1; i < MI.getNumOperands() - 1; i++) {
597     Register Reg = MI.getOperand(i).getReg();
598 
599     // Need derive an IR type for call lowering.
600     LLT OpLLT = MRI.getType(Reg);
601     Type *OpTy = nullptr;
602     if (OpLLT.isPointer())
603       OpTy = Type::getInt8PtrTy(Ctx, OpLLT.getAddressSpace());
604     else
605       OpTy = IntegerType::get(Ctx, OpLLT.getSizeInBits());
606     Args.push_back({Reg, OpTy});
607   }
608 
609   auto &CLI = *MIRBuilder.getMF().getSubtarget().getCallLowering();
610   auto &TLI = *MIRBuilder.getMF().getSubtarget().getTargetLowering();
611   Intrinsic::ID ID = MI.getOperand(0).getIntrinsicID();
612   RTLIB::Libcall RTLibcall;
613   switch (ID) {
614   case Intrinsic::memcpy:
615     RTLibcall = RTLIB::MEMCPY;
616     break;
617   case Intrinsic::memset:
618     RTLibcall = RTLIB::MEMSET;
619     break;
620   case Intrinsic::memmove:
621     RTLibcall = RTLIB::MEMMOVE;
622     break;
623   default:
624     return LegalizerHelper::UnableToLegalize;
625   }
626   const char *Name = TLI.getLibcallName(RTLibcall);
627 
628   MIRBuilder.setInstr(MI);
629 
630   CallLowering::CallLoweringInfo Info;
631   Info.CallConv = TLI.getLibcallCallingConv(RTLibcall);
632   Info.Callee = MachineOperand::CreateES(Name);
633   Info.OrigRet = CallLowering::ArgInfo({0}, Type::getVoidTy(Ctx));
634   Info.IsTailCall = MI.getOperand(MI.getNumOperands() - 1).getImm() == 1 &&
635                     isLibCallInTailPosition(MI);
636 
637   std::copy(Args.begin(), Args.end(), std::back_inserter(Info.OrigArgs));
638   if (!CLI.lowerCall(MIRBuilder, Info))
639     return LegalizerHelper::UnableToLegalize;
640 
641   if (Info.LoweredTailCall) {
642     assert(Info.IsTailCall && "Lowered tail call when it wasn't a tail call?");
643     // We must have a return following the call to get past
644     // isLibCallInTailPosition.
645     assert(MI.getNextNode() && MI.getNextNode()->isReturn() &&
646            "Expected instr following MI to be a return?");
647 
648     // We lowered a tail call, so the call is now the return from the block.
649     // Delete the old return.
650     MI.getNextNode()->eraseFromParent();
651   }
652 
653   return LegalizerHelper::Legalized;
654 }
655 
656 static RTLIB::Libcall getConvRTLibDesc(unsigned Opcode, Type *ToType,
657                                        Type *FromType) {
658   auto ToMVT = MVT::getVT(ToType);
659   auto FromMVT = MVT::getVT(FromType);
660 
661   switch (Opcode) {
662   case TargetOpcode::G_FPEXT:
663     return RTLIB::getFPEXT(FromMVT, ToMVT);
664   case TargetOpcode::G_FPTRUNC:
665     return RTLIB::getFPROUND(FromMVT, ToMVT);
666   case TargetOpcode::G_FPTOSI:
667     return RTLIB::getFPTOSINT(FromMVT, ToMVT);
668   case TargetOpcode::G_FPTOUI:
669     return RTLIB::getFPTOUINT(FromMVT, ToMVT);
670   case TargetOpcode::G_SITOFP:
671     return RTLIB::getSINTTOFP(FromMVT, ToMVT);
672   case TargetOpcode::G_UITOFP:
673     return RTLIB::getUINTTOFP(FromMVT, ToMVT);
674   }
675   llvm_unreachable("Unsupported libcall function");
676 }
677 
678 static LegalizerHelper::LegalizeResult
679 conversionLibcall(MachineInstr &MI, MachineIRBuilder &MIRBuilder, Type *ToType,
680                   Type *FromType) {
681   RTLIB::Libcall Libcall = getConvRTLibDesc(MI.getOpcode(), ToType, FromType);
682   return createLibcall(MIRBuilder, Libcall, {MI.getOperand(0).getReg(), ToType},
683                        {{MI.getOperand(1).getReg(), FromType}});
684 }
685 
686 LegalizerHelper::LegalizeResult
687 LegalizerHelper::libcall(MachineInstr &MI) {
688   LLT LLTy = MRI.getType(MI.getOperand(0).getReg());
689   unsigned Size = LLTy.getSizeInBits();
690   auto &Ctx = MIRBuilder.getMF().getFunction().getContext();
691 
692   MIRBuilder.setInstr(MI);
693 
694   switch (MI.getOpcode()) {
695   default:
696     return UnableToLegalize;
697   case TargetOpcode::G_SDIV:
698   case TargetOpcode::G_UDIV:
699   case TargetOpcode::G_SREM:
700   case TargetOpcode::G_UREM:
701   case TargetOpcode::G_CTLZ_ZERO_UNDEF: {
702     Type *HLTy = IntegerType::get(Ctx, Size);
703     auto Status = simpleLibcall(MI, MIRBuilder, Size, HLTy);
704     if (Status != Legalized)
705       return Status;
706     break;
707   }
708   case TargetOpcode::G_FADD:
709   case TargetOpcode::G_FSUB:
710   case TargetOpcode::G_FMUL:
711   case TargetOpcode::G_FDIV:
712   case TargetOpcode::G_FMA:
713   case TargetOpcode::G_FPOW:
714   case TargetOpcode::G_FREM:
715   case TargetOpcode::G_FCOS:
716   case TargetOpcode::G_FSIN:
717   case TargetOpcode::G_FLOG10:
718   case TargetOpcode::G_FLOG:
719   case TargetOpcode::G_FLOG2:
720   case TargetOpcode::G_FEXP:
721   case TargetOpcode::G_FEXP2:
722   case TargetOpcode::G_FCEIL:
723   case TargetOpcode::G_FFLOOR: {
724     Type *HLTy = getFloatTypeForLLT(Ctx, LLTy);
725     if (!HLTy || (Size != 32 && Size != 64)) {
726       LLVM_DEBUG(dbgs() << "No libcall available for size " << Size << ".\n");
727       return UnableToLegalize;
728     }
729     auto Status = simpleLibcall(MI, MIRBuilder, Size, HLTy);
730     if (Status != Legalized)
731       return Status;
732     break;
733   }
734   case TargetOpcode::G_FPEXT:
735   case TargetOpcode::G_FPTRUNC: {
736     Type *FromTy = getFloatTypeForLLT(Ctx,  MRI.getType(MI.getOperand(1).getReg()));
737     Type *ToTy = getFloatTypeForLLT(Ctx, MRI.getType(MI.getOperand(0).getReg()));
738     if (!FromTy || !ToTy)
739       return UnableToLegalize;
740     LegalizeResult Status = conversionLibcall(MI, MIRBuilder, ToTy, FromTy );
741     if (Status != Legalized)
742       return Status;
743     break;
744   }
745   case TargetOpcode::G_FPTOSI:
746   case TargetOpcode::G_FPTOUI: {
747     // FIXME: Support other types
748     unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
749     unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
750     if ((ToSize != 32 && ToSize != 64) || (FromSize != 32 && FromSize != 64))
751       return UnableToLegalize;
752     LegalizeResult Status = conversionLibcall(
753         MI, MIRBuilder,
754         ToSize == 32 ? Type::getInt32Ty(Ctx) : Type::getInt64Ty(Ctx),
755         FromSize == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx));
756     if (Status != Legalized)
757       return Status;
758     break;
759   }
760   case TargetOpcode::G_SITOFP:
761   case TargetOpcode::G_UITOFP: {
762     // FIXME: Support other types
763     unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
764     unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
765     if ((FromSize != 32 && FromSize != 64) || (ToSize != 32 && ToSize != 64))
766       return UnableToLegalize;
767     LegalizeResult Status = conversionLibcall(
768         MI, MIRBuilder,
769         ToSize == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx),
770         FromSize == 32 ? Type::getInt32Ty(Ctx) : Type::getInt64Ty(Ctx));
771     if (Status != Legalized)
772       return Status;
773     break;
774   }
775   }
776 
777   MI.eraseFromParent();
778   return Legalized;
779 }
780 
781 LegalizerHelper::LegalizeResult LegalizerHelper::narrowScalar(MachineInstr &MI,
782                                                               unsigned TypeIdx,
783                                                               LLT NarrowTy) {
784   MIRBuilder.setInstr(MI);
785 
786   uint64_t SizeOp0 = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
787   uint64_t NarrowSize = NarrowTy.getSizeInBits();
788 
789   switch (MI.getOpcode()) {
790   default:
791     return UnableToLegalize;
792   case TargetOpcode::G_IMPLICIT_DEF: {
793     // FIXME: add support for when SizeOp0 isn't an exact multiple of
794     // NarrowSize.
795     if (SizeOp0 % NarrowSize != 0)
796       return UnableToLegalize;
797     int NumParts = SizeOp0 / NarrowSize;
798 
799     SmallVector<Register, 2> DstRegs;
800     for (int i = 0; i < NumParts; ++i)
801       DstRegs.push_back(
802           MIRBuilder.buildUndef(NarrowTy).getReg(0));
803 
804     Register DstReg = MI.getOperand(0).getReg();
805     if(MRI.getType(DstReg).isVector())
806       MIRBuilder.buildBuildVector(DstReg, DstRegs);
807     else
808       MIRBuilder.buildMerge(DstReg, DstRegs);
809     MI.eraseFromParent();
810     return Legalized;
811   }
812   case TargetOpcode::G_CONSTANT: {
813     LLT Ty = MRI.getType(MI.getOperand(0).getReg());
814     const APInt &Val = MI.getOperand(1).getCImm()->getValue();
815     unsigned TotalSize = Ty.getSizeInBits();
816     unsigned NarrowSize = NarrowTy.getSizeInBits();
817     int NumParts = TotalSize / NarrowSize;
818 
819     SmallVector<Register, 4> PartRegs;
820     for (int I = 0; I != NumParts; ++I) {
821       unsigned Offset = I * NarrowSize;
822       auto K = MIRBuilder.buildConstant(NarrowTy,
823                                         Val.lshr(Offset).trunc(NarrowSize));
824       PartRegs.push_back(K.getReg(0));
825     }
826 
827     LLT LeftoverTy;
828     unsigned LeftoverBits = TotalSize - NumParts * NarrowSize;
829     SmallVector<Register, 1> LeftoverRegs;
830     if (LeftoverBits != 0) {
831       LeftoverTy = LLT::scalar(LeftoverBits);
832       auto K = MIRBuilder.buildConstant(
833         LeftoverTy,
834         Val.lshr(NumParts * NarrowSize).trunc(LeftoverBits));
835       LeftoverRegs.push_back(K.getReg(0));
836     }
837 
838     insertParts(MI.getOperand(0).getReg(),
839                 Ty, NarrowTy, PartRegs, LeftoverTy, LeftoverRegs);
840 
841     MI.eraseFromParent();
842     return Legalized;
843   }
844   case TargetOpcode::G_SEXT:
845   case TargetOpcode::G_ZEXT:
846   case TargetOpcode::G_ANYEXT:
847     return narrowScalarExt(MI, TypeIdx, NarrowTy);
848   case TargetOpcode::G_TRUNC: {
849     if (TypeIdx != 1)
850       return UnableToLegalize;
851 
852     uint64_t SizeOp1 = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
853     if (NarrowTy.getSizeInBits() * 2 != SizeOp1) {
854       LLVM_DEBUG(dbgs() << "Can't narrow trunc to type " << NarrowTy << "\n");
855       return UnableToLegalize;
856     }
857 
858     auto Unmerge = MIRBuilder.buildUnmerge(NarrowTy, MI.getOperand(1));
859     MIRBuilder.buildCopy(MI.getOperand(0), Unmerge.getReg(0));
860     MI.eraseFromParent();
861     return Legalized;
862   }
863 
864   case TargetOpcode::G_ADD: {
865     // FIXME: add support for when SizeOp0 isn't an exact multiple of
866     // NarrowSize.
867     if (SizeOp0 % NarrowSize != 0)
868       return UnableToLegalize;
869     // Expand in terms of carry-setting/consuming G_ADDE instructions.
870     int NumParts = SizeOp0 / NarrowTy.getSizeInBits();
871 
872     SmallVector<Register, 2> Src1Regs, Src2Regs, DstRegs;
873     extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs);
874     extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs);
875 
876     Register CarryIn;
877     for (int i = 0; i < NumParts; ++i) {
878       Register DstReg = MRI.createGenericVirtualRegister(NarrowTy);
879       Register CarryOut = MRI.createGenericVirtualRegister(LLT::scalar(1));
880 
881       if (i == 0)
882         MIRBuilder.buildUAddo(DstReg, CarryOut, Src1Regs[i], Src2Regs[i]);
883       else {
884         MIRBuilder.buildUAdde(DstReg, CarryOut, Src1Regs[i],
885                               Src2Regs[i], CarryIn);
886       }
887 
888       DstRegs.push_back(DstReg);
889       CarryIn = CarryOut;
890     }
891     Register DstReg = MI.getOperand(0).getReg();
892     if(MRI.getType(DstReg).isVector())
893       MIRBuilder.buildBuildVector(DstReg, DstRegs);
894     else
895       MIRBuilder.buildMerge(DstReg, DstRegs);
896     MI.eraseFromParent();
897     return Legalized;
898   }
899   case TargetOpcode::G_SUB: {
900     // FIXME: add support for when SizeOp0 isn't an exact multiple of
901     // NarrowSize.
902     if (SizeOp0 % NarrowSize != 0)
903       return UnableToLegalize;
904 
905     int NumParts = SizeOp0 / NarrowTy.getSizeInBits();
906 
907     SmallVector<Register, 2> Src1Regs, Src2Regs, DstRegs;
908     extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs);
909     extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs);
910 
911     Register DstReg = MRI.createGenericVirtualRegister(NarrowTy);
912     Register BorrowOut = MRI.createGenericVirtualRegister(LLT::scalar(1));
913     MIRBuilder.buildInstr(TargetOpcode::G_USUBO, {DstReg, BorrowOut},
914                           {Src1Regs[0], Src2Regs[0]});
915     DstRegs.push_back(DstReg);
916     Register BorrowIn = BorrowOut;
917     for (int i = 1; i < NumParts; ++i) {
918       DstReg = MRI.createGenericVirtualRegister(NarrowTy);
919       BorrowOut = MRI.createGenericVirtualRegister(LLT::scalar(1));
920 
921       MIRBuilder.buildInstr(TargetOpcode::G_USUBE, {DstReg, BorrowOut},
922                             {Src1Regs[i], Src2Regs[i], BorrowIn});
923 
924       DstRegs.push_back(DstReg);
925       BorrowIn = BorrowOut;
926     }
927     MIRBuilder.buildMerge(MI.getOperand(0), DstRegs);
928     MI.eraseFromParent();
929     return Legalized;
930   }
931   case TargetOpcode::G_MUL:
932   case TargetOpcode::G_UMULH:
933     return narrowScalarMul(MI, NarrowTy);
934   case TargetOpcode::G_EXTRACT:
935     return narrowScalarExtract(MI, TypeIdx, NarrowTy);
936   case TargetOpcode::G_INSERT:
937     return narrowScalarInsert(MI, TypeIdx, NarrowTy);
938   case TargetOpcode::G_LOAD: {
939     const auto &MMO = **MI.memoperands_begin();
940     Register DstReg = MI.getOperand(0).getReg();
941     LLT DstTy = MRI.getType(DstReg);
942     if (DstTy.isVector())
943       return UnableToLegalize;
944 
945     if (8 * MMO.getSize() != DstTy.getSizeInBits()) {
946       Register TmpReg = MRI.createGenericVirtualRegister(NarrowTy);
947       auto &MMO = **MI.memoperands_begin();
948       MIRBuilder.buildLoad(TmpReg, MI.getOperand(1), MMO);
949       MIRBuilder.buildAnyExt(DstReg, TmpReg);
950       MI.eraseFromParent();
951       return Legalized;
952     }
953 
954     return reduceLoadStoreWidth(MI, TypeIdx, NarrowTy);
955   }
956   case TargetOpcode::G_ZEXTLOAD:
957   case TargetOpcode::G_SEXTLOAD: {
958     bool ZExt = MI.getOpcode() == TargetOpcode::G_ZEXTLOAD;
959     Register DstReg = MI.getOperand(0).getReg();
960     Register PtrReg = MI.getOperand(1).getReg();
961 
962     Register TmpReg = MRI.createGenericVirtualRegister(NarrowTy);
963     auto &MMO = **MI.memoperands_begin();
964     if (MMO.getSizeInBits() == NarrowSize) {
965       MIRBuilder.buildLoad(TmpReg, PtrReg, MMO);
966     } else {
967       MIRBuilder.buildLoadInstr(MI.getOpcode(), TmpReg, PtrReg, MMO);
968     }
969 
970     if (ZExt)
971       MIRBuilder.buildZExt(DstReg, TmpReg);
972     else
973       MIRBuilder.buildSExt(DstReg, TmpReg);
974 
975     MI.eraseFromParent();
976     return Legalized;
977   }
978   case TargetOpcode::G_STORE: {
979     const auto &MMO = **MI.memoperands_begin();
980 
981     Register SrcReg = MI.getOperand(0).getReg();
982     LLT SrcTy = MRI.getType(SrcReg);
983     if (SrcTy.isVector())
984       return UnableToLegalize;
985 
986     int NumParts = SizeOp0 / NarrowSize;
987     unsigned HandledSize = NumParts * NarrowTy.getSizeInBits();
988     unsigned LeftoverBits = SrcTy.getSizeInBits() - HandledSize;
989     if (SrcTy.isVector() && LeftoverBits != 0)
990       return UnableToLegalize;
991 
992     if (8 * MMO.getSize() != SrcTy.getSizeInBits()) {
993       Register TmpReg = MRI.createGenericVirtualRegister(NarrowTy);
994       auto &MMO = **MI.memoperands_begin();
995       MIRBuilder.buildTrunc(TmpReg, SrcReg);
996       MIRBuilder.buildStore(TmpReg, MI.getOperand(1), MMO);
997       MI.eraseFromParent();
998       return Legalized;
999     }
1000 
1001     return reduceLoadStoreWidth(MI, 0, NarrowTy);
1002   }
1003   case TargetOpcode::G_SELECT:
1004     return narrowScalarSelect(MI, TypeIdx, NarrowTy);
1005   case TargetOpcode::G_AND:
1006   case TargetOpcode::G_OR:
1007   case TargetOpcode::G_XOR: {
1008     // Legalize bitwise operation:
1009     // A = BinOp<Ty> B, C
1010     // into:
1011     // B1, ..., BN = G_UNMERGE_VALUES B
1012     // C1, ..., CN = G_UNMERGE_VALUES C
1013     // A1 = BinOp<Ty/N> B1, C2
1014     // ...
1015     // AN = BinOp<Ty/N> BN, CN
1016     // A = G_MERGE_VALUES A1, ..., AN
1017     return narrowScalarBasic(MI, TypeIdx, NarrowTy);
1018   }
1019   case TargetOpcode::G_SHL:
1020   case TargetOpcode::G_LSHR:
1021   case TargetOpcode::G_ASHR:
1022     return narrowScalarShift(MI, TypeIdx, NarrowTy);
1023   case TargetOpcode::G_CTLZ:
1024   case TargetOpcode::G_CTLZ_ZERO_UNDEF:
1025   case TargetOpcode::G_CTTZ:
1026   case TargetOpcode::G_CTTZ_ZERO_UNDEF:
1027   case TargetOpcode::G_CTPOP:
1028     if (TypeIdx == 1)
1029       switch (MI.getOpcode()) {
1030       case TargetOpcode::G_CTLZ:
1031         return narrowScalarCTLZ(MI, TypeIdx, NarrowTy);
1032       case TargetOpcode::G_CTTZ:
1033         return narrowScalarCTTZ(MI, TypeIdx, NarrowTy);
1034       case TargetOpcode::G_CTPOP:
1035         return narrowScalarCTPOP(MI, TypeIdx, NarrowTy);
1036       default:
1037         return UnableToLegalize;
1038       }
1039 
1040     Observer.changingInstr(MI);
1041     narrowScalarDst(MI, NarrowTy, 0, TargetOpcode::G_ZEXT);
1042     Observer.changedInstr(MI);
1043     return Legalized;
1044   case TargetOpcode::G_INTTOPTR:
1045     if (TypeIdx != 1)
1046       return UnableToLegalize;
1047 
1048     Observer.changingInstr(MI);
1049     narrowScalarSrc(MI, NarrowTy, 1);
1050     Observer.changedInstr(MI);
1051     return Legalized;
1052   case TargetOpcode::G_PTRTOINT:
1053     if (TypeIdx != 0)
1054       return UnableToLegalize;
1055 
1056     Observer.changingInstr(MI);
1057     narrowScalarDst(MI, NarrowTy, 0, TargetOpcode::G_ZEXT);
1058     Observer.changedInstr(MI);
1059     return Legalized;
1060   case TargetOpcode::G_PHI: {
1061     unsigned NumParts = SizeOp0 / NarrowSize;
1062     SmallVector<Register, 2> DstRegs(NumParts);
1063     SmallVector<SmallVector<Register, 2>, 2> SrcRegs(MI.getNumOperands() / 2);
1064     Observer.changingInstr(MI);
1065     for (unsigned i = 1; i < MI.getNumOperands(); i += 2) {
1066       MachineBasicBlock &OpMBB = *MI.getOperand(i + 1).getMBB();
1067       MIRBuilder.setInsertPt(OpMBB, OpMBB.getFirstTerminator());
1068       extractParts(MI.getOperand(i).getReg(), NarrowTy, NumParts,
1069                    SrcRegs[i / 2]);
1070     }
1071     MachineBasicBlock &MBB = *MI.getParent();
1072     MIRBuilder.setInsertPt(MBB, MI);
1073     for (unsigned i = 0; i < NumParts; ++i) {
1074       DstRegs[i] = MRI.createGenericVirtualRegister(NarrowTy);
1075       MachineInstrBuilder MIB =
1076           MIRBuilder.buildInstr(TargetOpcode::G_PHI).addDef(DstRegs[i]);
1077       for (unsigned j = 1; j < MI.getNumOperands(); j += 2)
1078         MIB.addUse(SrcRegs[j / 2][i]).add(MI.getOperand(j + 1));
1079     }
1080     MIRBuilder.setInsertPt(MBB, MBB.getFirstNonPHI());
1081     MIRBuilder.buildMerge(MI.getOperand(0), DstRegs);
1082     Observer.changedInstr(MI);
1083     MI.eraseFromParent();
1084     return Legalized;
1085   }
1086   case TargetOpcode::G_EXTRACT_VECTOR_ELT:
1087   case TargetOpcode::G_INSERT_VECTOR_ELT: {
1088     if (TypeIdx != 2)
1089       return UnableToLegalize;
1090 
1091     int OpIdx = MI.getOpcode() == TargetOpcode::G_EXTRACT_VECTOR_ELT ? 2 : 3;
1092     Observer.changingInstr(MI);
1093     narrowScalarSrc(MI, NarrowTy, OpIdx);
1094     Observer.changedInstr(MI);
1095     return Legalized;
1096   }
1097   case TargetOpcode::G_ICMP: {
1098     uint64_t SrcSize = MRI.getType(MI.getOperand(2).getReg()).getSizeInBits();
1099     if (NarrowSize * 2 != SrcSize)
1100       return UnableToLegalize;
1101 
1102     Observer.changingInstr(MI);
1103     Register LHSL = MRI.createGenericVirtualRegister(NarrowTy);
1104     Register LHSH = MRI.createGenericVirtualRegister(NarrowTy);
1105     MIRBuilder.buildUnmerge({LHSL, LHSH}, MI.getOperand(2));
1106 
1107     Register RHSL = MRI.createGenericVirtualRegister(NarrowTy);
1108     Register RHSH = MRI.createGenericVirtualRegister(NarrowTy);
1109     MIRBuilder.buildUnmerge({RHSL, RHSH}, MI.getOperand(3));
1110 
1111     CmpInst::Predicate Pred =
1112         static_cast<CmpInst::Predicate>(MI.getOperand(1).getPredicate());
1113     LLT ResTy = MRI.getType(MI.getOperand(0).getReg());
1114 
1115     if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) {
1116       MachineInstrBuilder XorL = MIRBuilder.buildXor(NarrowTy, LHSL, RHSL);
1117       MachineInstrBuilder XorH = MIRBuilder.buildXor(NarrowTy, LHSH, RHSH);
1118       MachineInstrBuilder Or = MIRBuilder.buildOr(NarrowTy, XorL, XorH);
1119       MachineInstrBuilder Zero = MIRBuilder.buildConstant(NarrowTy, 0);
1120       MIRBuilder.buildICmp(Pred, MI.getOperand(0), Or, Zero);
1121     } else {
1122       MachineInstrBuilder CmpH = MIRBuilder.buildICmp(Pred, ResTy, LHSH, RHSH);
1123       MachineInstrBuilder CmpHEQ =
1124           MIRBuilder.buildICmp(CmpInst::Predicate::ICMP_EQ, ResTy, LHSH, RHSH);
1125       MachineInstrBuilder CmpLU = MIRBuilder.buildICmp(
1126           ICmpInst::getUnsignedPredicate(Pred), ResTy, LHSL, RHSL);
1127       MIRBuilder.buildSelect(MI.getOperand(0), CmpHEQ, CmpLU, CmpH);
1128     }
1129     Observer.changedInstr(MI);
1130     MI.eraseFromParent();
1131     return Legalized;
1132   }
1133   case TargetOpcode::G_SEXT_INREG: {
1134     if (TypeIdx != 0)
1135       return UnableToLegalize;
1136 
1137     int64_t SizeInBits = MI.getOperand(2).getImm();
1138 
1139     // So long as the new type has more bits than the bits we're extending we
1140     // don't need to break it apart.
1141     if (NarrowTy.getScalarSizeInBits() >= SizeInBits) {
1142       Observer.changingInstr(MI);
1143       // We don't lose any non-extension bits by truncating the src and
1144       // sign-extending the dst.
1145       MachineOperand &MO1 = MI.getOperand(1);
1146       auto TruncMIB = MIRBuilder.buildTrunc(NarrowTy, MO1);
1147       MO1.setReg(TruncMIB.getReg(0));
1148 
1149       MachineOperand &MO2 = MI.getOperand(0);
1150       Register DstExt = MRI.createGenericVirtualRegister(NarrowTy);
1151       MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt());
1152       MIRBuilder.buildSExt(MO2, DstExt);
1153       MO2.setReg(DstExt);
1154       Observer.changedInstr(MI);
1155       return Legalized;
1156     }
1157 
1158     // Break it apart. Components below the extension point are unmodified. The
1159     // component containing the extension point becomes a narrower SEXT_INREG.
1160     // Components above it are ashr'd from the component containing the
1161     // extension point.
1162     if (SizeOp0 % NarrowSize != 0)
1163       return UnableToLegalize;
1164     int NumParts = SizeOp0 / NarrowSize;
1165 
1166     // List the registers where the destination will be scattered.
1167     SmallVector<Register, 2> DstRegs;
1168     // List the registers where the source will be split.
1169     SmallVector<Register, 2> SrcRegs;
1170 
1171     // Create all the temporary registers.
1172     for (int i = 0; i < NumParts; ++i) {
1173       Register SrcReg = MRI.createGenericVirtualRegister(NarrowTy);
1174 
1175       SrcRegs.push_back(SrcReg);
1176     }
1177 
1178     // Explode the big arguments into smaller chunks.
1179     MIRBuilder.buildUnmerge(SrcRegs, MI.getOperand(1));
1180 
1181     Register AshrCstReg =
1182         MIRBuilder.buildConstant(NarrowTy, NarrowTy.getScalarSizeInBits() - 1)
1183             .getReg(0);
1184     Register FullExtensionReg = 0;
1185     Register PartialExtensionReg = 0;
1186 
1187     // Do the operation on each small part.
1188     for (int i = 0; i < NumParts; ++i) {
1189       if ((i + 1) * NarrowTy.getScalarSizeInBits() < SizeInBits)
1190         DstRegs.push_back(SrcRegs[i]);
1191       else if (i * NarrowTy.getScalarSizeInBits() > SizeInBits) {
1192         assert(PartialExtensionReg &&
1193                "Expected to visit partial extension before full");
1194         if (FullExtensionReg) {
1195           DstRegs.push_back(FullExtensionReg);
1196           continue;
1197         }
1198         DstRegs.push_back(
1199             MIRBuilder.buildAShr(NarrowTy, PartialExtensionReg, AshrCstReg)
1200                 .getReg(0));
1201         FullExtensionReg = DstRegs.back();
1202       } else {
1203         DstRegs.push_back(
1204             MIRBuilder
1205                 .buildInstr(
1206                     TargetOpcode::G_SEXT_INREG, {NarrowTy},
1207                     {SrcRegs[i], SizeInBits % NarrowTy.getScalarSizeInBits()})
1208                 .getReg(0));
1209         PartialExtensionReg = DstRegs.back();
1210       }
1211     }
1212 
1213     // Gather the destination registers into the final destination.
1214     Register DstReg = MI.getOperand(0).getReg();
1215     MIRBuilder.buildMerge(DstReg, DstRegs);
1216     MI.eraseFromParent();
1217     return Legalized;
1218   }
1219   case TargetOpcode::G_BSWAP:
1220   case TargetOpcode::G_BITREVERSE: {
1221     if (SizeOp0 % NarrowSize != 0)
1222       return UnableToLegalize;
1223 
1224     Observer.changingInstr(MI);
1225     SmallVector<Register, 2> SrcRegs, DstRegs;
1226     unsigned NumParts = SizeOp0 / NarrowSize;
1227     extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs);
1228 
1229     for (unsigned i = 0; i < NumParts; ++i) {
1230       auto DstPart = MIRBuilder.buildInstr(MI.getOpcode(), {NarrowTy},
1231                                            {SrcRegs[NumParts - 1 - i]});
1232       DstRegs.push_back(DstPart.getReg(0));
1233     }
1234 
1235     MIRBuilder.buildMerge(MI.getOperand(0), DstRegs);
1236 
1237     Observer.changedInstr(MI);
1238     MI.eraseFromParent();
1239     return Legalized;
1240   }
1241   }
1242 }
1243 
1244 void LegalizerHelper::widenScalarSrc(MachineInstr &MI, LLT WideTy,
1245                                      unsigned OpIdx, unsigned ExtOpcode) {
1246   MachineOperand &MO = MI.getOperand(OpIdx);
1247   auto ExtB = MIRBuilder.buildInstr(ExtOpcode, {WideTy}, {MO});
1248   MO.setReg(ExtB.getReg(0));
1249 }
1250 
1251 void LegalizerHelper::narrowScalarSrc(MachineInstr &MI, LLT NarrowTy,
1252                                       unsigned OpIdx) {
1253   MachineOperand &MO = MI.getOperand(OpIdx);
1254   auto ExtB = MIRBuilder.buildTrunc(NarrowTy, MO);
1255   MO.setReg(ExtB.getReg(0));
1256 }
1257 
1258 void LegalizerHelper::widenScalarDst(MachineInstr &MI, LLT WideTy,
1259                                      unsigned OpIdx, unsigned TruncOpcode) {
1260   MachineOperand &MO = MI.getOperand(OpIdx);
1261   Register DstExt = MRI.createGenericVirtualRegister(WideTy);
1262   MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt());
1263   MIRBuilder.buildInstr(TruncOpcode, {MO}, {DstExt});
1264   MO.setReg(DstExt);
1265 }
1266 
1267 void LegalizerHelper::narrowScalarDst(MachineInstr &MI, LLT NarrowTy,
1268                                       unsigned OpIdx, unsigned ExtOpcode) {
1269   MachineOperand &MO = MI.getOperand(OpIdx);
1270   Register DstTrunc = MRI.createGenericVirtualRegister(NarrowTy);
1271   MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt());
1272   MIRBuilder.buildInstr(ExtOpcode, {MO}, {DstTrunc});
1273   MO.setReg(DstTrunc);
1274 }
1275 
1276 void LegalizerHelper::moreElementsVectorDst(MachineInstr &MI, LLT WideTy,
1277                                             unsigned OpIdx) {
1278   MachineOperand &MO = MI.getOperand(OpIdx);
1279   Register DstExt = MRI.createGenericVirtualRegister(WideTy);
1280   MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt());
1281   MIRBuilder.buildExtract(MO, DstExt, 0);
1282   MO.setReg(DstExt);
1283 }
1284 
1285 void LegalizerHelper::moreElementsVectorSrc(MachineInstr &MI, LLT MoreTy,
1286                                             unsigned OpIdx) {
1287   MachineOperand &MO = MI.getOperand(OpIdx);
1288 
1289   LLT OldTy = MRI.getType(MO.getReg());
1290   unsigned OldElts = OldTy.getNumElements();
1291   unsigned NewElts = MoreTy.getNumElements();
1292 
1293   unsigned NumParts = NewElts / OldElts;
1294 
1295   // Use concat_vectors if the result is a multiple of the number of elements.
1296   if (NumParts * OldElts == NewElts) {
1297     SmallVector<Register, 8> Parts;
1298     Parts.push_back(MO.getReg());
1299 
1300     Register ImpDef = MIRBuilder.buildUndef(OldTy).getReg(0);
1301     for (unsigned I = 1; I != NumParts; ++I)
1302       Parts.push_back(ImpDef);
1303 
1304     auto Concat = MIRBuilder.buildConcatVectors(MoreTy, Parts);
1305     MO.setReg(Concat.getReg(0));
1306     return;
1307   }
1308 
1309   Register MoreReg = MRI.createGenericVirtualRegister(MoreTy);
1310   Register ImpDef = MIRBuilder.buildUndef(MoreTy).getReg(0);
1311   MIRBuilder.buildInsert(MoreReg, ImpDef, MO.getReg(), 0);
1312   MO.setReg(MoreReg);
1313 }
1314 
1315 LegalizerHelper::LegalizeResult
1316 LegalizerHelper::widenScalarMergeValues(MachineInstr &MI, unsigned TypeIdx,
1317                                         LLT WideTy) {
1318   if (TypeIdx != 1)
1319     return UnableToLegalize;
1320 
1321   Register DstReg = MI.getOperand(0).getReg();
1322   LLT DstTy = MRI.getType(DstReg);
1323   if (DstTy.isVector())
1324     return UnableToLegalize;
1325 
1326   Register Src1 = MI.getOperand(1).getReg();
1327   LLT SrcTy = MRI.getType(Src1);
1328   const int DstSize = DstTy.getSizeInBits();
1329   const int SrcSize = SrcTy.getSizeInBits();
1330   const int WideSize = WideTy.getSizeInBits();
1331   const int NumMerge = (DstSize + WideSize - 1) / WideSize;
1332 
1333   unsigned NumOps = MI.getNumOperands();
1334   unsigned NumSrc = MI.getNumOperands() - 1;
1335   unsigned PartSize = DstTy.getSizeInBits() / NumSrc;
1336 
1337   if (WideSize >= DstSize) {
1338     // Directly pack the bits in the target type.
1339     Register ResultReg = MIRBuilder.buildZExt(WideTy, Src1).getReg(0);
1340 
1341     for (unsigned I = 2; I != NumOps; ++I) {
1342       const unsigned Offset = (I - 1) * PartSize;
1343 
1344       Register SrcReg = MI.getOperand(I).getReg();
1345       assert(MRI.getType(SrcReg) == LLT::scalar(PartSize));
1346 
1347       auto ZextInput = MIRBuilder.buildZExt(WideTy, SrcReg);
1348 
1349       Register NextResult = I + 1 == NumOps && WideTy == DstTy ? DstReg :
1350         MRI.createGenericVirtualRegister(WideTy);
1351 
1352       auto ShiftAmt = MIRBuilder.buildConstant(WideTy, Offset);
1353       auto Shl = MIRBuilder.buildShl(WideTy, ZextInput, ShiftAmt);
1354       MIRBuilder.buildOr(NextResult, ResultReg, Shl);
1355       ResultReg = NextResult;
1356     }
1357 
1358     if (WideSize > DstSize)
1359       MIRBuilder.buildTrunc(DstReg, ResultReg);
1360     else if (DstTy.isPointer())
1361       MIRBuilder.buildIntToPtr(DstReg, ResultReg);
1362 
1363     MI.eraseFromParent();
1364     return Legalized;
1365   }
1366 
1367   // Unmerge the original values to the GCD type, and recombine to the next
1368   // multiple greater than the original type.
1369   //
1370   // %3:_(s12) = G_MERGE_VALUES %0:_(s4), %1:_(s4), %2:_(s4) -> s6
1371   // %4:_(s2), %5:_(s2) = G_UNMERGE_VALUES %0
1372   // %6:_(s2), %7:_(s2) = G_UNMERGE_VALUES %1
1373   // %8:_(s2), %9:_(s2) = G_UNMERGE_VALUES %2
1374   // %10:_(s6) = G_MERGE_VALUES %4, %5, %6
1375   // %11:_(s6) = G_MERGE_VALUES %7, %8, %9
1376   // %12:_(s12) = G_MERGE_VALUES %10, %11
1377   //
1378   // Padding with undef if necessary:
1379   //
1380   // %2:_(s8) = G_MERGE_VALUES %0:_(s4), %1:_(s4) -> s6
1381   // %3:_(s2), %4:_(s2) = G_UNMERGE_VALUES %0
1382   // %5:_(s2), %6:_(s2) = G_UNMERGE_VALUES %1
1383   // %7:_(s2) = G_IMPLICIT_DEF
1384   // %8:_(s6) = G_MERGE_VALUES %3, %4, %5
1385   // %9:_(s6) = G_MERGE_VALUES %6, %7, %7
1386   // %10:_(s12) = G_MERGE_VALUES %8, %9
1387 
1388   const int GCD = greatestCommonDivisor(SrcSize, WideSize);
1389   LLT GCDTy = LLT::scalar(GCD);
1390 
1391   SmallVector<Register, 8> Parts;
1392   SmallVector<Register, 8> NewMergeRegs;
1393   SmallVector<Register, 8> Unmerges;
1394   LLT WideDstTy = LLT::scalar(NumMerge * WideSize);
1395 
1396   // Decompose the original operands if they don't evenly divide.
1397   for (int I = 1, E = MI.getNumOperands(); I != E; ++I) {
1398     Register SrcReg = MI.getOperand(I).getReg();
1399     if (GCD == SrcSize) {
1400       Unmerges.push_back(SrcReg);
1401     } else {
1402       auto Unmerge = MIRBuilder.buildUnmerge(GCDTy, SrcReg);
1403       for (int J = 0, JE = Unmerge->getNumOperands() - 1; J != JE; ++J)
1404         Unmerges.push_back(Unmerge.getReg(J));
1405     }
1406   }
1407 
1408   // Pad with undef to the next size that is a multiple of the requested size.
1409   if (static_cast<int>(Unmerges.size()) != NumMerge * WideSize) {
1410     Register UndefReg = MIRBuilder.buildUndef(GCDTy).getReg(0);
1411     for (int I = Unmerges.size(); I != NumMerge * WideSize; ++I)
1412       Unmerges.push_back(UndefReg);
1413   }
1414 
1415   const int PartsPerGCD = WideSize / GCD;
1416 
1417   // Build merges of each piece.
1418   ArrayRef<Register> Slicer(Unmerges);
1419   for (int I = 0; I != NumMerge; ++I, Slicer = Slicer.drop_front(PartsPerGCD)) {
1420     auto Merge = MIRBuilder.buildMerge(WideTy, Slicer.take_front(PartsPerGCD));
1421     NewMergeRegs.push_back(Merge.getReg(0));
1422   }
1423 
1424   // A truncate may be necessary if the requested type doesn't evenly divide the
1425   // original result type.
1426   if (DstTy.getSizeInBits() == WideDstTy.getSizeInBits()) {
1427     MIRBuilder.buildMerge(DstReg, NewMergeRegs);
1428   } else {
1429     auto FinalMerge = MIRBuilder.buildMerge(WideDstTy, NewMergeRegs);
1430     MIRBuilder.buildTrunc(DstReg, FinalMerge.getReg(0));
1431   }
1432 
1433   MI.eraseFromParent();
1434   return Legalized;
1435 }
1436 
1437 LegalizerHelper::LegalizeResult
1438 LegalizerHelper::widenScalarUnmergeValues(MachineInstr &MI, unsigned TypeIdx,
1439                                           LLT WideTy) {
1440   if (TypeIdx != 0)
1441     return UnableToLegalize;
1442 
1443   int NumDst = MI.getNumOperands() - 1;
1444   Register SrcReg = MI.getOperand(NumDst).getReg();
1445   LLT SrcTy = MRI.getType(SrcReg);
1446   if (SrcTy.isVector())
1447     return UnableToLegalize;
1448 
1449   Register Dst0Reg = MI.getOperand(0).getReg();
1450   LLT DstTy = MRI.getType(Dst0Reg);
1451   if (!DstTy.isScalar())
1452     return UnableToLegalize;
1453 
1454   if (WideTy.getSizeInBits() == SrcTy.getSizeInBits()) {
1455     if (SrcTy.isPointer()) {
1456       const DataLayout &DL = MIRBuilder.getDataLayout();
1457       if (DL.isNonIntegralAddressSpace(SrcTy.getAddressSpace())) {
1458         LLVM_DEBUG(dbgs() << "Not casting non-integral address space integer\n");
1459         return UnableToLegalize;
1460       }
1461 
1462       SrcTy = LLT::scalar(SrcTy.getSizeInBits());
1463       SrcReg = MIRBuilder.buildPtrToInt(SrcTy, SrcReg).getReg(0);
1464     }
1465 
1466     // Theres no unmerge type to target. Directly extract the bits from the
1467     // source type
1468     unsigned DstSize = DstTy.getSizeInBits();
1469 
1470     MIRBuilder.buildTrunc(Dst0Reg, SrcReg);
1471     for (int I = 1; I != NumDst; ++I) {
1472       auto ShiftAmt = MIRBuilder.buildConstant(SrcTy, DstSize * I);
1473       auto Shr = MIRBuilder.buildLShr(SrcTy, SrcReg, ShiftAmt);
1474       MIRBuilder.buildTrunc(MI.getOperand(I), Shr);
1475     }
1476 
1477     MI.eraseFromParent();
1478     return Legalized;
1479   }
1480 
1481   // TODO
1482   if (WideTy.getSizeInBits() > SrcTy.getSizeInBits())
1483     return UnableToLegalize;
1484 
1485   // Extend the source to a wider type.
1486   LLT LCMTy = getLCMType(SrcTy, WideTy);
1487 
1488   Register WideSrc = SrcReg;
1489   if (LCMTy.getSizeInBits() != SrcTy.getSizeInBits()) {
1490     // TODO: If this is an integral address space, cast to integer and anyext.
1491     if (SrcTy.isPointer()) {
1492       LLVM_DEBUG(dbgs() << "Widening pointer source types not implemented\n");
1493       return UnableToLegalize;
1494     }
1495 
1496     WideSrc = MIRBuilder.buildAnyExt(LCMTy, WideSrc).getReg(0);
1497   }
1498 
1499   auto Unmerge = MIRBuilder.buildUnmerge(WideTy, WideSrc);
1500 
1501   // Create a sequence of unmerges to the original results. since we may have
1502   // widened the source, we will need to pad the results with dead defs to cover
1503   // the source register.
1504   // e.g. widen s16 to s32:
1505   // %1:_(s16), %2:_(s16), %3:_(s16) = G_UNMERGE_VALUES %0:_(s48)
1506   //
1507   // =>
1508   //  %4:_(s64) = G_ANYEXT %0:_(s48)
1509   //  %5:_(s32), %6:_(s32) = G_UNMERGE_VALUES %4 ; Requested unmerge
1510   //  %1:_(s16), %2:_(s16) = G_UNMERGE_VALUES %5 ; unpack to original regs
1511   //  %3:_(s16), dead %7 = G_UNMERGE_VALUES %6 ; original reg + extra dead def
1512 
1513   const int NumUnmerge = Unmerge->getNumOperands() - 1;
1514   const int PartsPerUnmerge = WideTy.getSizeInBits() / DstTy.getSizeInBits();
1515 
1516   for (int I = 0; I != NumUnmerge; ++I) {
1517     auto MIB = MIRBuilder.buildInstr(TargetOpcode::G_UNMERGE_VALUES);
1518 
1519     for (int J = 0; J != PartsPerUnmerge; ++J) {
1520       int Idx = I * PartsPerUnmerge + J;
1521       if (Idx < NumDst)
1522         MIB.addDef(MI.getOperand(Idx).getReg());
1523       else {
1524         // Create dead def for excess components.
1525         MIB.addDef(MRI.createGenericVirtualRegister(DstTy));
1526       }
1527     }
1528 
1529     MIB.addUse(Unmerge.getReg(I));
1530   }
1531 
1532   MI.eraseFromParent();
1533   return Legalized;
1534 }
1535 
1536 LegalizerHelper::LegalizeResult
1537 LegalizerHelper::widenScalarExtract(MachineInstr &MI, unsigned TypeIdx,
1538                                     LLT WideTy) {
1539   Register DstReg = MI.getOperand(0).getReg();
1540   Register SrcReg = MI.getOperand(1).getReg();
1541   LLT SrcTy = MRI.getType(SrcReg);
1542 
1543   LLT DstTy = MRI.getType(DstReg);
1544   unsigned Offset = MI.getOperand(2).getImm();
1545 
1546   if (TypeIdx == 0) {
1547     if (SrcTy.isVector() || DstTy.isVector())
1548       return UnableToLegalize;
1549 
1550     SrcOp Src(SrcReg);
1551     if (SrcTy.isPointer()) {
1552       // Extracts from pointers can be handled only if they are really just
1553       // simple integers.
1554       const DataLayout &DL = MIRBuilder.getDataLayout();
1555       if (DL.isNonIntegralAddressSpace(SrcTy.getAddressSpace()))
1556         return UnableToLegalize;
1557 
1558       LLT SrcAsIntTy = LLT::scalar(SrcTy.getSizeInBits());
1559       Src = MIRBuilder.buildPtrToInt(SrcAsIntTy, Src);
1560       SrcTy = SrcAsIntTy;
1561     }
1562 
1563     if (DstTy.isPointer())
1564       return UnableToLegalize;
1565 
1566     if (Offset == 0) {
1567       // Avoid a shift in the degenerate case.
1568       MIRBuilder.buildTrunc(DstReg,
1569                             MIRBuilder.buildAnyExtOrTrunc(WideTy, Src));
1570       MI.eraseFromParent();
1571       return Legalized;
1572     }
1573 
1574     // Do a shift in the source type.
1575     LLT ShiftTy = SrcTy;
1576     if (WideTy.getSizeInBits() > SrcTy.getSizeInBits()) {
1577       Src = MIRBuilder.buildAnyExt(WideTy, Src);
1578       ShiftTy = WideTy;
1579     } else if (WideTy.getSizeInBits() > SrcTy.getSizeInBits())
1580       return UnableToLegalize;
1581 
1582     auto LShr = MIRBuilder.buildLShr(
1583       ShiftTy, Src, MIRBuilder.buildConstant(ShiftTy, Offset));
1584     MIRBuilder.buildTrunc(DstReg, LShr);
1585     MI.eraseFromParent();
1586     return Legalized;
1587   }
1588 
1589   if (SrcTy.isScalar()) {
1590     Observer.changingInstr(MI);
1591     widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
1592     Observer.changedInstr(MI);
1593     return Legalized;
1594   }
1595 
1596   if (!SrcTy.isVector())
1597     return UnableToLegalize;
1598 
1599   if (DstTy != SrcTy.getElementType())
1600     return UnableToLegalize;
1601 
1602   if (Offset % SrcTy.getScalarSizeInBits() != 0)
1603     return UnableToLegalize;
1604 
1605   Observer.changingInstr(MI);
1606   widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
1607 
1608   MI.getOperand(2).setImm((WideTy.getSizeInBits() / SrcTy.getSizeInBits()) *
1609                           Offset);
1610   widenScalarDst(MI, WideTy.getScalarType(), 0);
1611   Observer.changedInstr(MI);
1612   return Legalized;
1613 }
1614 
1615 LegalizerHelper::LegalizeResult
1616 LegalizerHelper::widenScalarInsert(MachineInstr &MI, unsigned TypeIdx,
1617                                    LLT WideTy) {
1618   if (TypeIdx != 0)
1619     return UnableToLegalize;
1620   Observer.changingInstr(MI);
1621   widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
1622   widenScalarDst(MI, WideTy);
1623   Observer.changedInstr(MI);
1624   return Legalized;
1625 }
1626 
1627 LegalizerHelper::LegalizeResult
1628 LegalizerHelper::widenScalar(MachineInstr &MI, unsigned TypeIdx, LLT WideTy) {
1629   MIRBuilder.setInstr(MI);
1630 
1631   switch (MI.getOpcode()) {
1632   default:
1633     return UnableToLegalize;
1634   case TargetOpcode::G_EXTRACT:
1635     return widenScalarExtract(MI, TypeIdx, WideTy);
1636   case TargetOpcode::G_INSERT:
1637     return widenScalarInsert(MI, TypeIdx, WideTy);
1638   case TargetOpcode::G_MERGE_VALUES:
1639     return widenScalarMergeValues(MI, TypeIdx, WideTy);
1640   case TargetOpcode::G_UNMERGE_VALUES:
1641     return widenScalarUnmergeValues(MI, TypeIdx, WideTy);
1642   case TargetOpcode::G_UADDO:
1643   case TargetOpcode::G_USUBO: {
1644     if (TypeIdx == 1)
1645       return UnableToLegalize; // TODO
1646     auto LHSZext = MIRBuilder.buildZExt(WideTy, MI.getOperand(2));
1647     auto RHSZext = MIRBuilder.buildZExt(WideTy, MI.getOperand(3));
1648     unsigned Opcode = MI.getOpcode() == TargetOpcode::G_UADDO
1649                           ? TargetOpcode::G_ADD
1650                           : TargetOpcode::G_SUB;
1651     // Do the arithmetic in the larger type.
1652     auto NewOp = MIRBuilder.buildInstr(Opcode, {WideTy}, {LHSZext, RHSZext});
1653     LLT OrigTy = MRI.getType(MI.getOperand(0).getReg());
1654     APInt Mask =
1655         APInt::getLowBitsSet(WideTy.getSizeInBits(), OrigTy.getSizeInBits());
1656     auto AndOp = MIRBuilder.buildAnd(
1657         WideTy, NewOp, MIRBuilder.buildConstant(WideTy, Mask));
1658     // There is no overflow if the AndOp is the same as NewOp.
1659     MIRBuilder.buildICmp(CmpInst::ICMP_NE, MI.getOperand(1), NewOp, AndOp);
1660     // Now trunc the NewOp to the original result.
1661     MIRBuilder.buildTrunc(MI.getOperand(0), NewOp);
1662     MI.eraseFromParent();
1663     return Legalized;
1664   }
1665   case TargetOpcode::G_CTTZ:
1666   case TargetOpcode::G_CTTZ_ZERO_UNDEF:
1667   case TargetOpcode::G_CTLZ:
1668   case TargetOpcode::G_CTLZ_ZERO_UNDEF:
1669   case TargetOpcode::G_CTPOP: {
1670     if (TypeIdx == 0) {
1671       Observer.changingInstr(MI);
1672       widenScalarDst(MI, WideTy, 0);
1673       Observer.changedInstr(MI);
1674       return Legalized;
1675     }
1676 
1677     Register SrcReg = MI.getOperand(1).getReg();
1678 
1679     // First ZEXT the input.
1680     auto MIBSrc = MIRBuilder.buildZExt(WideTy, SrcReg);
1681     LLT CurTy = MRI.getType(SrcReg);
1682     if (MI.getOpcode() == TargetOpcode::G_CTTZ) {
1683       // The count is the same in the larger type except if the original
1684       // value was zero.  This can be handled by setting the bit just off
1685       // the top of the original type.
1686       auto TopBit =
1687           APInt::getOneBitSet(WideTy.getSizeInBits(), CurTy.getSizeInBits());
1688       MIBSrc = MIRBuilder.buildOr(
1689         WideTy, MIBSrc, MIRBuilder.buildConstant(WideTy, TopBit));
1690     }
1691 
1692     // Perform the operation at the larger size.
1693     auto MIBNewOp = MIRBuilder.buildInstr(MI.getOpcode(), {WideTy}, {MIBSrc});
1694     // This is already the correct result for CTPOP and CTTZs
1695     if (MI.getOpcode() == TargetOpcode::G_CTLZ ||
1696         MI.getOpcode() == TargetOpcode::G_CTLZ_ZERO_UNDEF) {
1697       // The correct result is NewOp - (Difference in widety and current ty).
1698       unsigned SizeDiff = WideTy.getSizeInBits() - CurTy.getSizeInBits();
1699       MIBNewOp = MIRBuilder.buildSub(
1700           WideTy, MIBNewOp, MIRBuilder.buildConstant(WideTy, SizeDiff));
1701     }
1702 
1703     MIRBuilder.buildZExtOrTrunc(MI.getOperand(0), MIBNewOp);
1704     MI.eraseFromParent();
1705     return Legalized;
1706   }
1707   case TargetOpcode::G_BSWAP: {
1708     Observer.changingInstr(MI);
1709     Register DstReg = MI.getOperand(0).getReg();
1710 
1711     Register ShrReg = MRI.createGenericVirtualRegister(WideTy);
1712     Register DstExt = MRI.createGenericVirtualRegister(WideTy);
1713     Register ShiftAmtReg = MRI.createGenericVirtualRegister(WideTy);
1714     widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
1715 
1716     MI.getOperand(0).setReg(DstExt);
1717 
1718     MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt());
1719 
1720     LLT Ty = MRI.getType(DstReg);
1721     unsigned DiffBits = WideTy.getScalarSizeInBits() - Ty.getScalarSizeInBits();
1722     MIRBuilder.buildConstant(ShiftAmtReg, DiffBits);
1723     MIRBuilder.buildLShr(ShrReg, DstExt, ShiftAmtReg);
1724 
1725     MIRBuilder.buildTrunc(DstReg, ShrReg);
1726     Observer.changedInstr(MI);
1727     return Legalized;
1728   }
1729   case TargetOpcode::G_BITREVERSE: {
1730     Observer.changingInstr(MI);
1731 
1732     Register DstReg = MI.getOperand(0).getReg();
1733     LLT Ty = MRI.getType(DstReg);
1734     unsigned DiffBits = WideTy.getScalarSizeInBits() - Ty.getScalarSizeInBits();
1735 
1736     Register DstExt = MRI.createGenericVirtualRegister(WideTy);
1737     widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
1738     MI.getOperand(0).setReg(DstExt);
1739     MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt());
1740 
1741     auto ShiftAmt = MIRBuilder.buildConstant(WideTy, DiffBits);
1742     auto Shift = MIRBuilder.buildLShr(WideTy, DstExt, ShiftAmt);
1743     MIRBuilder.buildTrunc(DstReg, Shift);
1744     Observer.changedInstr(MI);
1745     return Legalized;
1746   }
1747   case TargetOpcode::G_ADD:
1748   case TargetOpcode::G_AND:
1749   case TargetOpcode::G_MUL:
1750   case TargetOpcode::G_OR:
1751   case TargetOpcode::G_XOR:
1752   case TargetOpcode::G_SUB:
1753     // Perform operation at larger width (any extension is fines here, high bits
1754     // don't affect the result) and then truncate the result back to the
1755     // original type.
1756     Observer.changingInstr(MI);
1757     widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
1758     widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ANYEXT);
1759     widenScalarDst(MI, WideTy);
1760     Observer.changedInstr(MI);
1761     return Legalized;
1762 
1763   case TargetOpcode::G_SHL:
1764     Observer.changingInstr(MI);
1765 
1766     if (TypeIdx == 0) {
1767       widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
1768       widenScalarDst(MI, WideTy);
1769     } else {
1770       assert(TypeIdx == 1);
1771       // The "number of bits to shift" operand must preserve its value as an
1772       // unsigned integer:
1773       widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ZEXT);
1774     }
1775 
1776     Observer.changedInstr(MI);
1777     return Legalized;
1778 
1779   case TargetOpcode::G_SDIV:
1780   case TargetOpcode::G_SREM:
1781   case TargetOpcode::G_SMIN:
1782   case TargetOpcode::G_SMAX:
1783     Observer.changingInstr(MI);
1784     widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_SEXT);
1785     widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_SEXT);
1786     widenScalarDst(MI, WideTy);
1787     Observer.changedInstr(MI);
1788     return Legalized;
1789 
1790   case TargetOpcode::G_ASHR:
1791   case TargetOpcode::G_LSHR:
1792     Observer.changingInstr(MI);
1793 
1794     if (TypeIdx == 0) {
1795       unsigned CvtOp = MI.getOpcode() == TargetOpcode::G_ASHR ?
1796         TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT;
1797 
1798       widenScalarSrc(MI, WideTy, 1, CvtOp);
1799       widenScalarDst(MI, WideTy);
1800     } else {
1801       assert(TypeIdx == 1);
1802       // The "number of bits to shift" operand must preserve its value as an
1803       // unsigned integer:
1804       widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ZEXT);
1805     }
1806 
1807     Observer.changedInstr(MI);
1808     return Legalized;
1809   case TargetOpcode::G_UDIV:
1810   case TargetOpcode::G_UREM:
1811   case TargetOpcode::G_UMIN:
1812   case TargetOpcode::G_UMAX:
1813     Observer.changingInstr(MI);
1814     widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ZEXT);
1815     widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ZEXT);
1816     widenScalarDst(MI, WideTy);
1817     Observer.changedInstr(MI);
1818     return Legalized;
1819 
1820   case TargetOpcode::G_SELECT:
1821     Observer.changingInstr(MI);
1822     if (TypeIdx == 0) {
1823       // Perform operation at larger width (any extension is fine here, high
1824       // bits don't affect the result) and then truncate the result back to the
1825       // original type.
1826       widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ANYEXT);
1827       widenScalarSrc(MI, WideTy, 3, TargetOpcode::G_ANYEXT);
1828       widenScalarDst(MI, WideTy);
1829     } else {
1830       bool IsVec = MRI.getType(MI.getOperand(1).getReg()).isVector();
1831       // Explicit extension is required here since high bits affect the result.
1832       widenScalarSrc(MI, WideTy, 1, MIRBuilder.getBoolExtOp(IsVec, false));
1833     }
1834     Observer.changedInstr(MI);
1835     return Legalized;
1836 
1837   case TargetOpcode::G_FPTOSI:
1838   case TargetOpcode::G_FPTOUI:
1839     Observer.changingInstr(MI);
1840 
1841     if (TypeIdx == 0)
1842       widenScalarDst(MI, WideTy);
1843     else
1844       widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_FPEXT);
1845 
1846     Observer.changedInstr(MI);
1847     return Legalized;
1848   case TargetOpcode::G_SITOFP:
1849     if (TypeIdx != 1)
1850       return UnableToLegalize;
1851     Observer.changingInstr(MI);
1852     widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_SEXT);
1853     Observer.changedInstr(MI);
1854     return Legalized;
1855 
1856   case TargetOpcode::G_UITOFP:
1857     if (TypeIdx != 1)
1858       return UnableToLegalize;
1859     Observer.changingInstr(MI);
1860     widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ZEXT);
1861     Observer.changedInstr(MI);
1862     return Legalized;
1863 
1864   case TargetOpcode::G_LOAD:
1865   case TargetOpcode::G_SEXTLOAD:
1866   case TargetOpcode::G_ZEXTLOAD:
1867     Observer.changingInstr(MI);
1868     widenScalarDst(MI, WideTy);
1869     Observer.changedInstr(MI);
1870     return Legalized;
1871 
1872   case TargetOpcode::G_STORE: {
1873     if (TypeIdx != 0)
1874       return UnableToLegalize;
1875 
1876     LLT Ty = MRI.getType(MI.getOperand(0).getReg());
1877     if (!isPowerOf2_32(Ty.getSizeInBits()))
1878       return UnableToLegalize;
1879 
1880     Observer.changingInstr(MI);
1881 
1882     unsigned ExtType = Ty.getScalarSizeInBits() == 1 ?
1883       TargetOpcode::G_ZEXT : TargetOpcode::G_ANYEXT;
1884     widenScalarSrc(MI, WideTy, 0, ExtType);
1885 
1886     Observer.changedInstr(MI);
1887     return Legalized;
1888   }
1889   case TargetOpcode::G_CONSTANT: {
1890     MachineOperand &SrcMO = MI.getOperand(1);
1891     LLVMContext &Ctx = MIRBuilder.getMF().getFunction().getContext();
1892     unsigned ExtOpc = LI.getExtOpcodeForWideningConstant(
1893         MRI.getType(MI.getOperand(0).getReg()));
1894     assert((ExtOpc == TargetOpcode::G_ZEXT || ExtOpc == TargetOpcode::G_SEXT ||
1895             ExtOpc == TargetOpcode::G_ANYEXT) &&
1896            "Illegal Extend");
1897     const APInt &SrcVal = SrcMO.getCImm()->getValue();
1898     const APInt &Val = (ExtOpc == TargetOpcode::G_SEXT)
1899                            ? SrcVal.sext(WideTy.getSizeInBits())
1900                            : SrcVal.zext(WideTy.getSizeInBits());
1901     Observer.changingInstr(MI);
1902     SrcMO.setCImm(ConstantInt::get(Ctx, Val));
1903 
1904     widenScalarDst(MI, WideTy);
1905     Observer.changedInstr(MI);
1906     return Legalized;
1907   }
1908   case TargetOpcode::G_FCONSTANT: {
1909     MachineOperand &SrcMO = MI.getOperand(1);
1910     LLVMContext &Ctx = MIRBuilder.getMF().getFunction().getContext();
1911     APFloat Val = SrcMO.getFPImm()->getValueAPF();
1912     bool LosesInfo;
1913     switch (WideTy.getSizeInBits()) {
1914     case 32:
1915       Val.convert(APFloat::IEEEsingle(), APFloat::rmNearestTiesToEven,
1916                   &LosesInfo);
1917       break;
1918     case 64:
1919       Val.convert(APFloat::IEEEdouble(), APFloat::rmNearestTiesToEven,
1920                   &LosesInfo);
1921       break;
1922     default:
1923       return UnableToLegalize;
1924     }
1925 
1926     assert(!LosesInfo && "extend should always be lossless");
1927 
1928     Observer.changingInstr(MI);
1929     SrcMO.setFPImm(ConstantFP::get(Ctx, Val));
1930 
1931     widenScalarDst(MI, WideTy, 0, TargetOpcode::G_FPTRUNC);
1932     Observer.changedInstr(MI);
1933     return Legalized;
1934   }
1935   case TargetOpcode::G_IMPLICIT_DEF: {
1936     Observer.changingInstr(MI);
1937     widenScalarDst(MI, WideTy);
1938     Observer.changedInstr(MI);
1939     return Legalized;
1940   }
1941   case TargetOpcode::G_BRCOND:
1942     Observer.changingInstr(MI);
1943     widenScalarSrc(MI, WideTy, 0, MIRBuilder.getBoolExtOp(false, false));
1944     Observer.changedInstr(MI);
1945     return Legalized;
1946 
1947   case TargetOpcode::G_FCMP:
1948     Observer.changingInstr(MI);
1949     if (TypeIdx == 0)
1950       widenScalarDst(MI, WideTy);
1951     else {
1952       widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_FPEXT);
1953       widenScalarSrc(MI, WideTy, 3, TargetOpcode::G_FPEXT);
1954     }
1955     Observer.changedInstr(MI);
1956     return Legalized;
1957 
1958   case TargetOpcode::G_ICMP:
1959     Observer.changingInstr(MI);
1960     if (TypeIdx == 0)
1961       widenScalarDst(MI, WideTy);
1962     else {
1963       unsigned ExtOpcode = CmpInst::isSigned(static_cast<CmpInst::Predicate>(
1964                                MI.getOperand(1).getPredicate()))
1965                                ? TargetOpcode::G_SEXT
1966                                : TargetOpcode::G_ZEXT;
1967       widenScalarSrc(MI, WideTy, 2, ExtOpcode);
1968       widenScalarSrc(MI, WideTy, 3, ExtOpcode);
1969     }
1970     Observer.changedInstr(MI);
1971     return Legalized;
1972 
1973   case TargetOpcode::G_PTR_ADD:
1974     assert(TypeIdx == 1 && "unable to legalize pointer of G_PTR_ADD");
1975     Observer.changingInstr(MI);
1976     widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_SEXT);
1977     Observer.changedInstr(MI);
1978     return Legalized;
1979 
1980   case TargetOpcode::G_PHI: {
1981     assert(TypeIdx == 0 && "Expecting only Idx 0");
1982 
1983     Observer.changingInstr(MI);
1984     for (unsigned I = 1; I < MI.getNumOperands(); I += 2) {
1985       MachineBasicBlock &OpMBB = *MI.getOperand(I + 1).getMBB();
1986       MIRBuilder.setInsertPt(OpMBB, OpMBB.getFirstTerminator());
1987       widenScalarSrc(MI, WideTy, I, TargetOpcode::G_ANYEXT);
1988     }
1989 
1990     MachineBasicBlock &MBB = *MI.getParent();
1991     MIRBuilder.setInsertPt(MBB, --MBB.getFirstNonPHI());
1992     widenScalarDst(MI, WideTy);
1993     Observer.changedInstr(MI);
1994     return Legalized;
1995   }
1996   case TargetOpcode::G_EXTRACT_VECTOR_ELT: {
1997     if (TypeIdx == 0) {
1998       Register VecReg = MI.getOperand(1).getReg();
1999       LLT VecTy = MRI.getType(VecReg);
2000       Observer.changingInstr(MI);
2001 
2002       widenScalarSrc(MI, LLT::vector(VecTy.getNumElements(),
2003                                      WideTy.getSizeInBits()),
2004                      1, TargetOpcode::G_SEXT);
2005 
2006       widenScalarDst(MI, WideTy, 0);
2007       Observer.changedInstr(MI);
2008       return Legalized;
2009     }
2010 
2011     if (TypeIdx != 2)
2012       return UnableToLegalize;
2013     Observer.changingInstr(MI);
2014     // TODO: Probably should be zext
2015     widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_SEXT);
2016     Observer.changedInstr(MI);
2017     return Legalized;
2018   }
2019   case TargetOpcode::G_INSERT_VECTOR_ELT: {
2020     if (TypeIdx == 1) {
2021       Observer.changingInstr(MI);
2022 
2023       Register VecReg = MI.getOperand(1).getReg();
2024       LLT VecTy = MRI.getType(VecReg);
2025       LLT WideVecTy = LLT::vector(VecTy.getNumElements(), WideTy);
2026 
2027       widenScalarSrc(MI, WideVecTy, 1, TargetOpcode::G_ANYEXT);
2028       widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ANYEXT);
2029       widenScalarDst(MI, WideVecTy, 0);
2030       Observer.changedInstr(MI);
2031       return Legalized;
2032     }
2033 
2034     if (TypeIdx == 2) {
2035       Observer.changingInstr(MI);
2036       // TODO: Probably should be zext
2037       widenScalarSrc(MI, WideTy, 3, TargetOpcode::G_SEXT);
2038       Observer.changedInstr(MI);
2039     }
2040 
2041     return Legalized;
2042   }
2043   case TargetOpcode::G_FADD:
2044   case TargetOpcode::G_FMUL:
2045   case TargetOpcode::G_FSUB:
2046   case TargetOpcode::G_FMA:
2047   case TargetOpcode::G_FMAD:
2048   case TargetOpcode::G_FNEG:
2049   case TargetOpcode::G_FABS:
2050   case TargetOpcode::G_FCANONICALIZE:
2051   case TargetOpcode::G_FMINNUM:
2052   case TargetOpcode::G_FMAXNUM:
2053   case TargetOpcode::G_FMINNUM_IEEE:
2054   case TargetOpcode::G_FMAXNUM_IEEE:
2055   case TargetOpcode::G_FMINIMUM:
2056   case TargetOpcode::G_FMAXIMUM:
2057   case TargetOpcode::G_FDIV:
2058   case TargetOpcode::G_FREM:
2059   case TargetOpcode::G_FCEIL:
2060   case TargetOpcode::G_FFLOOR:
2061   case TargetOpcode::G_FCOS:
2062   case TargetOpcode::G_FSIN:
2063   case TargetOpcode::G_FLOG10:
2064   case TargetOpcode::G_FLOG:
2065   case TargetOpcode::G_FLOG2:
2066   case TargetOpcode::G_FRINT:
2067   case TargetOpcode::G_FNEARBYINT:
2068   case TargetOpcode::G_FSQRT:
2069   case TargetOpcode::G_FEXP:
2070   case TargetOpcode::G_FEXP2:
2071   case TargetOpcode::G_FPOW:
2072   case TargetOpcode::G_INTRINSIC_TRUNC:
2073   case TargetOpcode::G_INTRINSIC_ROUND:
2074     assert(TypeIdx == 0);
2075     Observer.changingInstr(MI);
2076 
2077     for (unsigned I = 1, E = MI.getNumOperands(); I != E; ++I)
2078       widenScalarSrc(MI, WideTy, I, TargetOpcode::G_FPEXT);
2079 
2080     widenScalarDst(MI, WideTy, 0, TargetOpcode::G_FPTRUNC);
2081     Observer.changedInstr(MI);
2082     return Legalized;
2083   case TargetOpcode::G_INTTOPTR:
2084     if (TypeIdx != 1)
2085       return UnableToLegalize;
2086 
2087     Observer.changingInstr(MI);
2088     widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ZEXT);
2089     Observer.changedInstr(MI);
2090     return Legalized;
2091   case TargetOpcode::G_PTRTOINT:
2092     if (TypeIdx != 0)
2093       return UnableToLegalize;
2094 
2095     Observer.changingInstr(MI);
2096     widenScalarDst(MI, WideTy, 0);
2097     Observer.changedInstr(MI);
2098     return Legalized;
2099   case TargetOpcode::G_BUILD_VECTOR: {
2100     Observer.changingInstr(MI);
2101 
2102     const LLT WideEltTy = TypeIdx == 1 ? WideTy : WideTy.getElementType();
2103     for (int I = 1, E = MI.getNumOperands(); I != E; ++I)
2104       widenScalarSrc(MI, WideEltTy, I, TargetOpcode::G_ANYEXT);
2105 
2106     // Avoid changing the result vector type if the source element type was
2107     // requested.
2108     if (TypeIdx == 1) {
2109       auto &TII = *MI.getMF()->getSubtarget().getInstrInfo();
2110       MI.setDesc(TII.get(TargetOpcode::G_BUILD_VECTOR_TRUNC));
2111     } else {
2112       widenScalarDst(MI, WideTy, 0);
2113     }
2114 
2115     Observer.changedInstr(MI);
2116     return Legalized;
2117   }
2118   case TargetOpcode::G_SEXT_INREG:
2119     if (TypeIdx != 0)
2120       return UnableToLegalize;
2121 
2122     Observer.changingInstr(MI);
2123     widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
2124     widenScalarDst(MI, WideTy, 0, TargetOpcode::G_TRUNC);
2125     Observer.changedInstr(MI);
2126     return Legalized;
2127   }
2128 }
2129 
2130 static void getUnmergePieces(SmallVectorImpl<Register> &Pieces,
2131                              MachineIRBuilder &B, Register Src, LLT Ty) {
2132   auto Unmerge = B.buildUnmerge(Ty, Src);
2133   for (int I = 0, E = Unmerge->getNumOperands() - 1; I != E; ++I)
2134     Pieces.push_back(Unmerge.getReg(I));
2135 }
2136 
2137 LegalizerHelper::LegalizeResult
2138 LegalizerHelper::lowerBitcast(MachineInstr &MI) {
2139   Register Dst = MI.getOperand(0).getReg();
2140   Register Src = MI.getOperand(1).getReg();
2141   LLT DstTy = MRI.getType(Dst);
2142   LLT SrcTy = MRI.getType(Src);
2143 
2144   if (SrcTy.isVector() && !DstTy.isVector()) {
2145     SmallVector<Register, 8> SrcRegs;
2146     getUnmergePieces(SrcRegs, MIRBuilder, Src, SrcTy.getElementType());
2147     MIRBuilder.buildMerge(Dst, SrcRegs);
2148     MI.eraseFromParent();
2149     return Legalized;
2150   }
2151 
2152   if (DstTy.isVector() && !SrcTy.isVector()) {
2153     SmallVector<Register, 8> SrcRegs;
2154     getUnmergePieces(SrcRegs, MIRBuilder, Src, DstTy.getElementType());
2155     MIRBuilder.buildMerge(Dst, SrcRegs);
2156     MI.eraseFromParent();
2157     return Legalized;
2158   }
2159 
2160   return UnableToLegalize;
2161 }
2162 
2163 LegalizerHelper::LegalizeResult
2164 LegalizerHelper::lower(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
2165   using namespace TargetOpcode;
2166   MIRBuilder.setInstr(MI);
2167 
2168   switch(MI.getOpcode()) {
2169   default:
2170     return UnableToLegalize;
2171   case TargetOpcode::G_BITCAST:
2172     return lowerBitcast(MI);
2173   case TargetOpcode::G_SREM:
2174   case TargetOpcode::G_UREM: {
2175     Register QuotReg = MRI.createGenericVirtualRegister(Ty);
2176     MIRBuilder.buildInstr(MI.getOpcode() == G_SREM ? G_SDIV : G_UDIV, {QuotReg},
2177                           {MI.getOperand(1), MI.getOperand(2)});
2178 
2179     Register ProdReg = MRI.createGenericVirtualRegister(Ty);
2180     MIRBuilder.buildMul(ProdReg, QuotReg, MI.getOperand(2));
2181     MIRBuilder.buildSub(MI.getOperand(0), MI.getOperand(1), ProdReg);
2182     MI.eraseFromParent();
2183     return Legalized;
2184   }
2185   case TargetOpcode::G_SADDO:
2186   case TargetOpcode::G_SSUBO:
2187     return lowerSADDO_SSUBO(MI);
2188   case TargetOpcode::G_SMULO:
2189   case TargetOpcode::G_UMULO: {
2190     // Generate G_UMULH/G_SMULH to check for overflow and a normal G_MUL for the
2191     // result.
2192     Register Res = MI.getOperand(0).getReg();
2193     Register Overflow = MI.getOperand(1).getReg();
2194     Register LHS = MI.getOperand(2).getReg();
2195     Register RHS = MI.getOperand(3).getReg();
2196 
2197     unsigned Opcode = MI.getOpcode() == TargetOpcode::G_SMULO
2198                           ? TargetOpcode::G_SMULH
2199                           : TargetOpcode::G_UMULH;
2200 
2201     Observer.changingInstr(MI);
2202     const auto &TII = MIRBuilder.getTII();
2203     MI.setDesc(TII.get(TargetOpcode::G_MUL));
2204     MI.RemoveOperand(1);
2205     Observer.changedInstr(MI);
2206 
2207     MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt());
2208 
2209     auto HiPart = MIRBuilder.buildInstr(Opcode, {Ty}, {LHS, RHS});
2210 
2211     Register Zero = MRI.createGenericVirtualRegister(Ty);
2212     MIRBuilder.buildConstant(Zero, 0);
2213 
2214     // For *signed* multiply, overflow is detected by checking:
2215     // (hi != (lo >> bitwidth-1))
2216     if (Opcode == TargetOpcode::G_SMULH) {
2217       auto ShiftAmt = MIRBuilder.buildConstant(Ty, Ty.getSizeInBits() - 1);
2218       auto Shifted = MIRBuilder.buildAShr(Ty, Res, ShiftAmt);
2219       MIRBuilder.buildICmp(CmpInst::ICMP_NE, Overflow, HiPart, Shifted);
2220     } else {
2221       MIRBuilder.buildICmp(CmpInst::ICMP_NE, Overflow, HiPart, Zero);
2222     }
2223     return Legalized;
2224   }
2225   case TargetOpcode::G_FNEG: {
2226     // TODO: Handle vector types once we are able to
2227     // represent them.
2228     if (Ty.isVector())
2229       return UnableToLegalize;
2230     Register Res = MI.getOperand(0).getReg();
2231     LLVMContext &Ctx = MIRBuilder.getMF().getFunction().getContext();
2232     Type *ZeroTy = getFloatTypeForLLT(Ctx, Ty);
2233     if (!ZeroTy)
2234       return UnableToLegalize;
2235     ConstantFP &ZeroForNegation =
2236         *cast<ConstantFP>(ConstantFP::getZeroValueForNegation(ZeroTy));
2237     auto Zero = MIRBuilder.buildFConstant(Ty, ZeroForNegation);
2238     Register SubByReg = MI.getOperand(1).getReg();
2239     Register ZeroReg = Zero.getReg(0);
2240     MIRBuilder.buildFSub(Res, ZeroReg, SubByReg, MI.getFlags());
2241     MI.eraseFromParent();
2242     return Legalized;
2243   }
2244   case TargetOpcode::G_FSUB: {
2245     // Lower (G_FSUB LHS, RHS) to (G_FADD LHS, (G_FNEG RHS)).
2246     // First, check if G_FNEG is marked as Lower. If so, we may
2247     // end up with an infinite loop as G_FSUB is used to legalize G_FNEG.
2248     if (LI.getAction({G_FNEG, {Ty}}).Action == Lower)
2249       return UnableToLegalize;
2250     Register Res = MI.getOperand(0).getReg();
2251     Register LHS = MI.getOperand(1).getReg();
2252     Register RHS = MI.getOperand(2).getReg();
2253     Register Neg = MRI.createGenericVirtualRegister(Ty);
2254     MIRBuilder.buildFNeg(Neg, RHS);
2255     MIRBuilder.buildFAdd(Res, LHS, Neg, MI.getFlags());
2256     MI.eraseFromParent();
2257     return Legalized;
2258   }
2259   case TargetOpcode::G_FMAD:
2260     return lowerFMad(MI);
2261   case TargetOpcode::G_INTRINSIC_ROUND:
2262     return lowerIntrinsicRound(MI);
2263   case TargetOpcode::G_ATOMIC_CMPXCHG_WITH_SUCCESS: {
2264     Register OldValRes = MI.getOperand(0).getReg();
2265     Register SuccessRes = MI.getOperand(1).getReg();
2266     Register Addr = MI.getOperand(2).getReg();
2267     Register CmpVal = MI.getOperand(3).getReg();
2268     Register NewVal = MI.getOperand(4).getReg();
2269     MIRBuilder.buildAtomicCmpXchg(OldValRes, Addr, CmpVal, NewVal,
2270                                   **MI.memoperands_begin());
2271     MIRBuilder.buildICmp(CmpInst::ICMP_EQ, SuccessRes, OldValRes, CmpVal);
2272     MI.eraseFromParent();
2273     return Legalized;
2274   }
2275   case TargetOpcode::G_LOAD:
2276   case TargetOpcode::G_SEXTLOAD:
2277   case TargetOpcode::G_ZEXTLOAD: {
2278     // Lower to a memory-width G_LOAD and a G_SEXT/G_ZEXT/G_ANYEXT
2279     Register DstReg = MI.getOperand(0).getReg();
2280     Register PtrReg = MI.getOperand(1).getReg();
2281     LLT DstTy = MRI.getType(DstReg);
2282     auto &MMO = **MI.memoperands_begin();
2283 
2284     if (DstTy.getSizeInBits() == MMO.getSizeInBits()) {
2285       if (MI.getOpcode() == TargetOpcode::G_LOAD) {
2286         // This load needs splitting into power of 2 sized loads.
2287         if (DstTy.isVector())
2288           return UnableToLegalize;
2289         if (isPowerOf2_32(DstTy.getSizeInBits()))
2290           return UnableToLegalize; // Don't know what we're being asked to do.
2291 
2292         // Our strategy here is to generate anyextending loads for the smaller
2293         // types up to next power-2 result type, and then combine the two larger
2294         // result values together, before truncating back down to the non-pow-2
2295         // type.
2296         // E.g. v1 = i24 load =>
2297         // v2 = i32 zextload (2 byte)
2298         // v3 = i32 load (1 byte)
2299         // v4 = i32 shl v3, 16
2300         // v5 = i32 or v4, v2
2301         // v1 = i24 trunc v5
2302         // By doing this we generate the correct truncate which should get
2303         // combined away as an artifact with a matching extend.
2304         uint64_t LargeSplitSize = PowerOf2Floor(DstTy.getSizeInBits());
2305         uint64_t SmallSplitSize = DstTy.getSizeInBits() - LargeSplitSize;
2306 
2307         MachineFunction &MF = MIRBuilder.getMF();
2308         MachineMemOperand *LargeMMO =
2309             MF.getMachineMemOperand(&MMO, 0, LargeSplitSize / 8);
2310         MachineMemOperand *SmallMMO = MF.getMachineMemOperand(
2311             &MMO, LargeSplitSize / 8, SmallSplitSize / 8);
2312 
2313         LLT PtrTy = MRI.getType(PtrReg);
2314         unsigned AnyExtSize = NextPowerOf2(DstTy.getSizeInBits());
2315         LLT AnyExtTy = LLT::scalar(AnyExtSize);
2316         Register LargeLdReg = MRI.createGenericVirtualRegister(AnyExtTy);
2317         Register SmallLdReg = MRI.createGenericVirtualRegister(AnyExtTy);
2318         auto LargeLoad = MIRBuilder.buildLoadInstr(
2319             TargetOpcode::G_ZEXTLOAD, LargeLdReg, PtrReg, *LargeMMO);
2320 
2321         auto OffsetCst = MIRBuilder.buildConstant(
2322             LLT::scalar(PtrTy.getSizeInBits()), LargeSplitSize / 8);
2323         Register PtrAddReg = MRI.createGenericVirtualRegister(PtrTy);
2324         auto SmallPtr =
2325             MIRBuilder.buildPtrAdd(PtrAddReg, PtrReg, OffsetCst.getReg(0));
2326         auto SmallLoad = MIRBuilder.buildLoad(SmallLdReg, SmallPtr.getReg(0),
2327                                               *SmallMMO);
2328 
2329         auto ShiftAmt = MIRBuilder.buildConstant(AnyExtTy, LargeSplitSize);
2330         auto Shift = MIRBuilder.buildShl(AnyExtTy, SmallLoad, ShiftAmt);
2331         auto Or = MIRBuilder.buildOr(AnyExtTy, Shift, LargeLoad);
2332         MIRBuilder.buildTrunc(DstReg, {Or.getReg(0)});
2333         MI.eraseFromParent();
2334         return Legalized;
2335       }
2336       MIRBuilder.buildLoad(DstReg, PtrReg, MMO);
2337       MI.eraseFromParent();
2338       return Legalized;
2339     }
2340 
2341     if (DstTy.isScalar()) {
2342       Register TmpReg =
2343           MRI.createGenericVirtualRegister(LLT::scalar(MMO.getSizeInBits()));
2344       MIRBuilder.buildLoad(TmpReg, PtrReg, MMO);
2345       switch (MI.getOpcode()) {
2346       default:
2347         llvm_unreachable("Unexpected opcode");
2348       case TargetOpcode::G_LOAD:
2349         MIRBuilder.buildExtOrTrunc(TargetOpcode::G_ANYEXT, DstReg, TmpReg);
2350         break;
2351       case TargetOpcode::G_SEXTLOAD:
2352         MIRBuilder.buildSExt(DstReg, TmpReg);
2353         break;
2354       case TargetOpcode::G_ZEXTLOAD:
2355         MIRBuilder.buildZExt(DstReg, TmpReg);
2356         break;
2357       }
2358       MI.eraseFromParent();
2359       return Legalized;
2360     }
2361 
2362     return UnableToLegalize;
2363   }
2364   case TargetOpcode::G_STORE: {
2365     // Lower a non-power of 2 store into multiple pow-2 stores.
2366     // E.g. split an i24 store into an i16 store + i8 store.
2367     // We do this by first extending the stored value to the next largest power
2368     // of 2 type, and then using truncating stores to store the components.
2369     // By doing this, likewise with G_LOAD, generate an extend that can be
2370     // artifact-combined away instead of leaving behind extracts.
2371     Register SrcReg = MI.getOperand(0).getReg();
2372     Register PtrReg = MI.getOperand(1).getReg();
2373     LLT SrcTy = MRI.getType(SrcReg);
2374     MachineMemOperand &MMO = **MI.memoperands_begin();
2375     if (SrcTy.getSizeInBits() != MMO.getSizeInBits())
2376       return UnableToLegalize;
2377     if (SrcTy.isVector())
2378       return UnableToLegalize;
2379     if (isPowerOf2_32(SrcTy.getSizeInBits()))
2380       return UnableToLegalize; // Don't know what we're being asked to do.
2381 
2382     // Extend to the next pow-2.
2383     const LLT ExtendTy = LLT::scalar(NextPowerOf2(SrcTy.getSizeInBits()));
2384     auto ExtVal = MIRBuilder.buildAnyExt(ExtendTy, SrcReg);
2385 
2386     // Obtain the smaller value by shifting away the larger value.
2387     uint64_t LargeSplitSize = PowerOf2Floor(SrcTy.getSizeInBits());
2388     uint64_t SmallSplitSize = SrcTy.getSizeInBits() - LargeSplitSize;
2389     auto ShiftAmt = MIRBuilder.buildConstant(ExtendTy, LargeSplitSize);
2390     auto SmallVal = MIRBuilder.buildLShr(ExtendTy, ExtVal, ShiftAmt);
2391 
2392     // Generate the PtrAdd and truncating stores.
2393     LLT PtrTy = MRI.getType(PtrReg);
2394     auto OffsetCst = MIRBuilder.buildConstant(
2395             LLT::scalar(PtrTy.getSizeInBits()), LargeSplitSize / 8);
2396     Register PtrAddReg = MRI.createGenericVirtualRegister(PtrTy);
2397     auto SmallPtr =
2398         MIRBuilder.buildPtrAdd(PtrAddReg, PtrReg, OffsetCst.getReg(0));
2399 
2400     MachineFunction &MF = MIRBuilder.getMF();
2401     MachineMemOperand *LargeMMO =
2402         MF.getMachineMemOperand(&MMO, 0, LargeSplitSize / 8);
2403     MachineMemOperand *SmallMMO =
2404         MF.getMachineMemOperand(&MMO, LargeSplitSize / 8, SmallSplitSize / 8);
2405     MIRBuilder.buildStore(ExtVal.getReg(0), PtrReg, *LargeMMO);
2406     MIRBuilder.buildStore(SmallVal.getReg(0), SmallPtr.getReg(0), *SmallMMO);
2407     MI.eraseFromParent();
2408     return Legalized;
2409   }
2410   case TargetOpcode::G_CTLZ_ZERO_UNDEF:
2411   case TargetOpcode::G_CTTZ_ZERO_UNDEF:
2412   case TargetOpcode::G_CTLZ:
2413   case TargetOpcode::G_CTTZ:
2414   case TargetOpcode::G_CTPOP:
2415     return lowerBitCount(MI, TypeIdx, Ty);
2416   case G_UADDO: {
2417     Register Res = MI.getOperand(0).getReg();
2418     Register CarryOut = MI.getOperand(1).getReg();
2419     Register LHS = MI.getOperand(2).getReg();
2420     Register RHS = MI.getOperand(3).getReg();
2421 
2422     MIRBuilder.buildAdd(Res, LHS, RHS);
2423     MIRBuilder.buildICmp(CmpInst::ICMP_ULT, CarryOut, Res, RHS);
2424 
2425     MI.eraseFromParent();
2426     return Legalized;
2427   }
2428   case G_UADDE: {
2429     Register Res = MI.getOperand(0).getReg();
2430     Register CarryOut = MI.getOperand(1).getReg();
2431     Register LHS = MI.getOperand(2).getReg();
2432     Register RHS = MI.getOperand(3).getReg();
2433     Register CarryIn = MI.getOperand(4).getReg();
2434 
2435     Register TmpRes = MRI.createGenericVirtualRegister(Ty);
2436     Register ZExtCarryIn = MRI.createGenericVirtualRegister(Ty);
2437 
2438     MIRBuilder.buildAdd(TmpRes, LHS, RHS);
2439     MIRBuilder.buildZExt(ZExtCarryIn, CarryIn);
2440     MIRBuilder.buildAdd(Res, TmpRes, ZExtCarryIn);
2441     MIRBuilder.buildICmp(CmpInst::ICMP_ULT, CarryOut, Res, LHS);
2442 
2443     MI.eraseFromParent();
2444     return Legalized;
2445   }
2446   case G_USUBO: {
2447     Register Res = MI.getOperand(0).getReg();
2448     Register BorrowOut = MI.getOperand(1).getReg();
2449     Register LHS = MI.getOperand(2).getReg();
2450     Register RHS = MI.getOperand(3).getReg();
2451 
2452     MIRBuilder.buildSub(Res, LHS, RHS);
2453     MIRBuilder.buildICmp(CmpInst::ICMP_ULT, BorrowOut, LHS, RHS);
2454 
2455     MI.eraseFromParent();
2456     return Legalized;
2457   }
2458   case G_USUBE: {
2459     Register Res = MI.getOperand(0).getReg();
2460     Register BorrowOut = MI.getOperand(1).getReg();
2461     Register LHS = MI.getOperand(2).getReg();
2462     Register RHS = MI.getOperand(3).getReg();
2463     Register BorrowIn = MI.getOperand(4).getReg();
2464 
2465     Register TmpRes = MRI.createGenericVirtualRegister(Ty);
2466     Register ZExtBorrowIn = MRI.createGenericVirtualRegister(Ty);
2467     Register LHS_EQ_RHS = MRI.createGenericVirtualRegister(LLT::scalar(1));
2468     Register LHS_ULT_RHS = MRI.createGenericVirtualRegister(LLT::scalar(1));
2469 
2470     MIRBuilder.buildSub(TmpRes, LHS, RHS);
2471     MIRBuilder.buildZExt(ZExtBorrowIn, BorrowIn);
2472     MIRBuilder.buildSub(Res, TmpRes, ZExtBorrowIn);
2473     MIRBuilder.buildICmp(CmpInst::ICMP_EQ, LHS_EQ_RHS, LHS, RHS);
2474     MIRBuilder.buildICmp(CmpInst::ICMP_ULT, LHS_ULT_RHS, LHS, RHS);
2475     MIRBuilder.buildSelect(BorrowOut, LHS_EQ_RHS, BorrowIn, LHS_ULT_RHS);
2476 
2477     MI.eraseFromParent();
2478     return Legalized;
2479   }
2480   case G_UITOFP:
2481     return lowerUITOFP(MI, TypeIdx, Ty);
2482   case G_SITOFP:
2483     return lowerSITOFP(MI, TypeIdx, Ty);
2484   case G_FPTOUI:
2485     return lowerFPTOUI(MI, TypeIdx, Ty);
2486   case G_FPTOSI:
2487     return lowerFPTOSI(MI);
2488   case G_SMIN:
2489   case G_SMAX:
2490   case G_UMIN:
2491   case G_UMAX:
2492     return lowerMinMax(MI, TypeIdx, Ty);
2493   case G_FCOPYSIGN:
2494     return lowerFCopySign(MI, TypeIdx, Ty);
2495   case G_FMINNUM:
2496   case G_FMAXNUM:
2497     return lowerFMinNumMaxNum(MI);
2498   case G_UNMERGE_VALUES:
2499     return lowerUnmergeValues(MI);
2500   case TargetOpcode::G_SEXT_INREG: {
2501     assert(MI.getOperand(2).isImm() && "Expected immediate");
2502     int64_t SizeInBits = MI.getOperand(2).getImm();
2503 
2504     Register DstReg = MI.getOperand(0).getReg();
2505     Register SrcReg = MI.getOperand(1).getReg();
2506     LLT DstTy = MRI.getType(DstReg);
2507     Register TmpRes = MRI.createGenericVirtualRegister(DstTy);
2508 
2509     auto MIBSz = MIRBuilder.buildConstant(DstTy, DstTy.getScalarSizeInBits() - SizeInBits);
2510     MIRBuilder.buildShl(TmpRes, SrcReg, MIBSz->getOperand(0));
2511     MIRBuilder.buildAShr(DstReg, TmpRes, MIBSz->getOperand(0));
2512     MI.eraseFromParent();
2513     return Legalized;
2514   }
2515   case G_SHUFFLE_VECTOR:
2516     return lowerShuffleVector(MI);
2517   case G_DYN_STACKALLOC:
2518     return lowerDynStackAlloc(MI);
2519   case G_EXTRACT:
2520     return lowerExtract(MI);
2521   case G_INSERT:
2522     return lowerInsert(MI);
2523   case G_BSWAP:
2524     return lowerBswap(MI);
2525   case G_BITREVERSE:
2526     return lowerBitreverse(MI);
2527   case G_READ_REGISTER:
2528   case G_WRITE_REGISTER:
2529     return lowerReadWriteRegister(MI);
2530   }
2531 }
2532 
2533 LegalizerHelper::LegalizeResult LegalizerHelper::fewerElementsVectorImplicitDef(
2534     MachineInstr &MI, unsigned TypeIdx, LLT NarrowTy) {
2535   SmallVector<Register, 2> DstRegs;
2536 
2537   unsigned NarrowSize = NarrowTy.getSizeInBits();
2538   Register DstReg = MI.getOperand(0).getReg();
2539   unsigned Size = MRI.getType(DstReg).getSizeInBits();
2540   int NumParts = Size / NarrowSize;
2541   // FIXME: Don't know how to handle the situation where the small vectors
2542   // aren't all the same size yet.
2543   if (Size % NarrowSize != 0)
2544     return UnableToLegalize;
2545 
2546   for (int i = 0; i < NumParts; ++i) {
2547     Register TmpReg = MRI.createGenericVirtualRegister(NarrowTy);
2548     MIRBuilder.buildUndef(TmpReg);
2549     DstRegs.push_back(TmpReg);
2550   }
2551 
2552   if (NarrowTy.isVector())
2553     MIRBuilder.buildConcatVectors(DstReg, DstRegs);
2554   else
2555     MIRBuilder.buildBuildVector(DstReg, DstRegs);
2556 
2557   MI.eraseFromParent();
2558   return Legalized;
2559 }
2560 
2561 LegalizerHelper::LegalizeResult
2562 LegalizerHelper::fewerElementsVectorBasic(MachineInstr &MI, unsigned TypeIdx,
2563                                           LLT NarrowTy) {
2564   const unsigned Opc = MI.getOpcode();
2565   const unsigned NumOps = MI.getNumOperands() - 1;
2566   const unsigned NarrowSize = NarrowTy.getSizeInBits();
2567   const Register DstReg = MI.getOperand(0).getReg();
2568   const unsigned Flags = MI.getFlags();
2569   const LLT DstTy = MRI.getType(DstReg);
2570   const unsigned Size = DstTy.getSizeInBits();
2571   const int NumParts = Size / NarrowSize;
2572   const LLT EltTy = DstTy.getElementType();
2573   const unsigned EltSize = EltTy.getSizeInBits();
2574   const unsigned BitsForNumParts = NarrowSize * NumParts;
2575 
2576   // Check if we have any leftovers. If we do, then only handle the case where
2577   // the leftover is one element.
2578   if (BitsForNumParts != Size && BitsForNumParts + EltSize != Size)
2579     return UnableToLegalize;
2580 
2581   if (BitsForNumParts != Size) {
2582     Register AccumDstReg = MRI.createGenericVirtualRegister(DstTy);
2583     MIRBuilder.buildUndef(AccumDstReg);
2584 
2585     // Handle the pieces which evenly divide into the requested type with
2586     // extract/op/insert sequence.
2587     for (unsigned Offset = 0; Offset < BitsForNumParts; Offset += NarrowSize) {
2588       SmallVector<SrcOp, 4> SrcOps;
2589       for (unsigned I = 1, E = MI.getNumOperands(); I != E; ++I) {
2590         Register PartOpReg = MRI.createGenericVirtualRegister(NarrowTy);
2591         MIRBuilder.buildExtract(PartOpReg, MI.getOperand(I), Offset);
2592         SrcOps.push_back(PartOpReg);
2593       }
2594 
2595       Register PartDstReg = MRI.createGenericVirtualRegister(NarrowTy);
2596       MIRBuilder.buildInstr(Opc, {PartDstReg}, SrcOps, Flags);
2597 
2598       Register PartInsertReg = MRI.createGenericVirtualRegister(DstTy);
2599       MIRBuilder.buildInsert(PartInsertReg, AccumDstReg, PartDstReg, Offset);
2600       AccumDstReg = PartInsertReg;
2601     }
2602 
2603     // Handle the remaining element sized leftover piece.
2604     SmallVector<SrcOp, 4> SrcOps;
2605     for (unsigned I = 1, E = MI.getNumOperands(); I != E; ++I) {
2606       Register PartOpReg = MRI.createGenericVirtualRegister(EltTy);
2607       MIRBuilder.buildExtract(PartOpReg, MI.getOperand(I), BitsForNumParts);
2608       SrcOps.push_back(PartOpReg);
2609     }
2610 
2611     Register PartDstReg = MRI.createGenericVirtualRegister(EltTy);
2612     MIRBuilder.buildInstr(Opc, {PartDstReg}, SrcOps, Flags);
2613     MIRBuilder.buildInsert(DstReg, AccumDstReg, PartDstReg, BitsForNumParts);
2614     MI.eraseFromParent();
2615 
2616     return Legalized;
2617   }
2618 
2619   SmallVector<Register, 2> DstRegs, Src0Regs, Src1Regs, Src2Regs;
2620 
2621   extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src0Regs);
2622 
2623   if (NumOps >= 2)
2624     extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src1Regs);
2625 
2626   if (NumOps >= 3)
2627     extractParts(MI.getOperand(3).getReg(), NarrowTy, NumParts, Src2Regs);
2628 
2629   for (int i = 0; i < NumParts; ++i) {
2630     Register DstReg = MRI.createGenericVirtualRegister(NarrowTy);
2631 
2632     if (NumOps == 1)
2633       MIRBuilder.buildInstr(Opc, {DstReg}, {Src0Regs[i]}, Flags);
2634     else if (NumOps == 2) {
2635       MIRBuilder.buildInstr(Opc, {DstReg}, {Src0Regs[i], Src1Regs[i]}, Flags);
2636     } else if (NumOps == 3) {
2637       MIRBuilder.buildInstr(Opc, {DstReg},
2638                             {Src0Regs[i], Src1Regs[i], Src2Regs[i]}, Flags);
2639     }
2640 
2641     DstRegs.push_back(DstReg);
2642   }
2643 
2644   if (NarrowTy.isVector())
2645     MIRBuilder.buildConcatVectors(DstReg, DstRegs);
2646   else
2647     MIRBuilder.buildBuildVector(DstReg, DstRegs);
2648 
2649   MI.eraseFromParent();
2650   return Legalized;
2651 }
2652 
2653 // Handle splitting vector operations which need to have the same number of
2654 // elements in each type index, but each type index may have a different element
2655 // type.
2656 //
2657 // e.g.  <4 x s64> = G_SHL <4 x s64>, <4 x s32> ->
2658 //       <2 x s64> = G_SHL <2 x s64>, <2 x s32>
2659 //       <2 x s64> = G_SHL <2 x s64>, <2 x s32>
2660 //
2661 // Also handles some irregular breakdown cases, e.g.
2662 // e.g.  <3 x s64> = G_SHL <3 x s64>, <3 x s32> ->
2663 //       <2 x s64> = G_SHL <2 x s64>, <2 x s32>
2664 //             s64 = G_SHL s64, s32
2665 LegalizerHelper::LegalizeResult
2666 LegalizerHelper::fewerElementsVectorMultiEltType(
2667   MachineInstr &MI, unsigned TypeIdx, LLT NarrowTyArg) {
2668   if (TypeIdx != 0)
2669     return UnableToLegalize;
2670 
2671   const LLT NarrowTy0 = NarrowTyArg;
2672   const unsigned NewNumElts =
2673       NarrowTy0.isVector() ? NarrowTy0.getNumElements() : 1;
2674 
2675   const Register DstReg = MI.getOperand(0).getReg();
2676   LLT DstTy = MRI.getType(DstReg);
2677   LLT LeftoverTy0;
2678 
2679   // All of the operands need to have the same number of elements, so if we can
2680   // determine a type breakdown for the result type, we can for all of the
2681   // source types.
2682   int NumParts = getNarrowTypeBreakDown(DstTy, NarrowTy0, LeftoverTy0).first;
2683   if (NumParts < 0)
2684     return UnableToLegalize;
2685 
2686   SmallVector<MachineInstrBuilder, 4> NewInsts;
2687 
2688   SmallVector<Register, 4> DstRegs, LeftoverDstRegs;
2689   SmallVector<Register, 4> PartRegs, LeftoverRegs;
2690 
2691   for (unsigned I = 1, E = MI.getNumOperands(); I != E; ++I) {
2692     LLT LeftoverTy;
2693     Register SrcReg = MI.getOperand(I).getReg();
2694     LLT SrcTyI = MRI.getType(SrcReg);
2695     LLT NarrowTyI = LLT::scalarOrVector(NewNumElts, SrcTyI.getScalarType());
2696     LLT LeftoverTyI;
2697 
2698     // Split this operand into the requested typed registers, and any leftover
2699     // required to reproduce the original type.
2700     if (!extractParts(SrcReg, SrcTyI, NarrowTyI, LeftoverTyI, PartRegs,
2701                       LeftoverRegs))
2702       return UnableToLegalize;
2703 
2704     if (I == 1) {
2705       // For the first operand, create an instruction for each part and setup
2706       // the result.
2707       for (Register PartReg : PartRegs) {
2708         Register PartDstReg = MRI.createGenericVirtualRegister(NarrowTy0);
2709         NewInsts.push_back(MIRBuilder.buildInstrNoInsert(MI.getOpcode())
2710                                .addDef(PartDstReg)
2711                                .addUse(PartReg));
2712         DstRegs.push_back(PartDstReg);
2713       }
2714 
2715       for (Register LeftoverReg : LeftoverRegs) {
2716         Register PartDstReg = MRI.createGenericVirtualRegister(LeftoverTy0);
2717         NewInsts.push_back(MIRBuilder.buildInstrNoInsert(MI.getOpcode())
2718                                .addDef(PartDstReg)
2719                                .addUse(LeftoverReg));
2720         LeftoverDstRegs.push_back(PartDstReg);
2721       }
2722     } else {
2723       assert(NewInsts.size() == PartRegs.size() + LeftoverRegs.size());
2724 
2725       // Add the newly created operand splits to the existing instructions. The
2726       // odd-sized pieces are ordered after the requested NarrowTyArg sized
2727       // pieces.
2728       unsigned InstCount = 0;
2729       for (unsigned J = 0, JE = PartRegs.size(); J != JE; ++J)
2730         NewInsts[InstCount++].addUse(PartRegs[J]);
2731       for (unsigned J = 0, JE = LeftoverRegs.size(); J != JE; ++J)
2732         NewInsts[InstCount++].addUse(LeftoverRegs[J]);
2733     }
2734 
2735     PartRegs.clear();
2736     LeftoverRegs.clear();
2737   }
2738 
2739   // Insert the newly built operations and rebuild the result register.
2740   for (auto &MIB : NewInsts)
2741     MIRBuilder.insertInstr(MIB);
2742 
2743   insertParts(DstReg, DstTy, NarrowTy0, DstRegs, LeftoverTy0, LeftoverDstRegs);
2744 
2745   MI.eraseFromParent();
2746   return Legalized;
2747 }
2748 
2749 LegalizerHelper::LegalizeResult
2750 LegalizerHelper::fewerElementsVectorCasts(MachineInstr &MI, unsigned TypeIdx,
2751                                           LLT NarrowTy) {
2752   if (TypeIdx != 0)
2753     return UnableToLegalize;
2754 
2755   Register DstReg = MI.getOperand(0).getReg();
2756   Register SrcReg = MI.getOperand(1).getReg();
2757   LLT DstTy = MRI.getType(DstReg);
2758   LLT SrcTy = MRI.getType(SrcReg);
2759 
2760   LLT NarrowTy0 = NarrowTy;
2761   LLT NarrowTy1;
2762   unsigned NumParts;
2763 
2764   if (NarrowTy.isVector()) {
2765     // Uneven breakdown not handled.
2766     NumParts = DstTy.getNumElements() / NarrowTy.getNumElements();
2767     if (NumParts * NarrowTy.getNumElements() != DstTy.getNumElements())
2768       return UnableToLegalize;
2769 
2770     NarrowTy1 = LLT::vector(NumParts, SrcTy.getElementType().getSizeInBits());
2771   } else {
2772     NumParts = DstTy.getNumElements();
2773     NarrowTy1 = SrcTy.getElementType();
2774   }
2775 
2776   SmallVector<Register, 4> SrcRegs, DstRegs;
2777   extractParts(SrcReg, NarrowTy1, NumParts, SrcRegs);
2778 
2779   for (unsigned I = 0; I < NumParts; ++I) {
2780     Register DstReg = MRI.createGenericVirtualRegister(NarrowTy0);
2781     MachineInstr *NewInst =
2782         MIRBuilder.buildInstr(MI.getOpcode(), {DstReg}, {SrcRegs[I]});
2783 
2784     NewInst->setFlags(MI.getFlags());
2785     DstRegs.push_back(DstReg);
2786   }
2787 
2788   if (NarrowTy.isVector())
2789     MIRBuilder.buildConcatVectors(DstReg, DstRegs);
2790   else
2791     MIRBuilder.buildBuildVector(DstReg, DstRegs);
2792 
2793   MI.eraseFromParent();
2794   return Legalized;
2795 }
2796 
2797 LegalizerHelper::LegalizeResult
2798 LegalizerHelper::fewerElementsVectorCmp(MachineInstr &MI, unsigned TypeIdx,
2799                                         LLT NarrowTy) {
2800   Register DstReg = MI.getOperand(0).getReg();
2801   Register Src0Reg = MI.getOperand(2).getReg();
2802   LLT DstTy = MRI.getType(DstReg);
2803   LLT SrcTy = MRI.getType(Src0Reg);
2804 
2805   unsigned NumParts;
2806   LLT NarrowTy0, NarrowTy1;
2807 
2808   if (TypeIdx == 0) {
2809     unsigned NewElts = NarrowTy.isVector() ? NarrowTy.getNumElements() : 1;
2810     unsigned OldElts = DstTy.getNumElements();
2811 
2812     NarrowTy0 = NarrowTy;
2813     NumParts = NarrowTy.isVector() ? (OldElts / NewElts) : DstTy.getNumElements();
2814     NarrowTy1 = NarrowTy.isVector() ?
2815       LLT::vector(NarrowTy.getNumElements(), SrcTy.getScalarSizeInBits()) :
2816       SrcTy.getElementType();
2817 
2818   } else {
2819     unsigned NewElts = NarrowTy.isVector() ? NarrowTy.getNumElements() : 1;
2820     unsigned OldElts = SrcTy.getNumElements();
2821 
2822     NumParts = NarrowTy.isVector() ? (OldElts / NewElts) :
2823       NarrowTy.getNumElements();
2824     NarrowTy0 = LLT::vector(NarrowTy.getNumElements(),
2825                             DstTy.getScalarSizeInBits());
2826     NarrowTy1 = NarrowTy;
2827   }
2828 
2829   // FIXME: Don't know how to handle the situation where the small vectors
2830   // aren't all the same size yet.
2831   if (NarrowTy1.isVector() &&
2832       NarrowTy1.getNumElements() * NumParts != DstTy.getNumElements())
2833     return UnableToLegalize;
2834 
2835   CmpInst::Predicate Pred
2836     = static_cast<CmpInst::Predicate>(MI.getOperand(1).getPredicate());
2837 
2838   SmallVector<Register, 2> Src1Regs, Src2Regs, DstRegs;
2839   extractParts(MI.getOperand(2).getReg(), NarrowTy1, NumParts, Src1Regs);
2840   extractParts(MI.getOperand(3).getReg(), NarrowTy1, NumParts, Src2Regs);
2841 
2842   for (unsigned I = 0; I < NumParts; ++I) {
2843     Register DstReg = MRI.createGenericVirtualRegister(NarrowTy0);
2844     DstRegs.push_back(DstReg);
2845 
2846     if (MI.getOpcode() == TargetOpcode::G_ICMP)
2847       MIRBuilder.buildICmp(Pred, DstReg, Src1Regs[I], Src2Regs[I]);
2848     else {
2849       MachineInstr *NewCmp
2850         = MIRBuilder.buildFCmp(Pred, DstReg, Src1Regs[I], Src2Regs[I]);
2851       NewCmp->setFlags(MI.getFlags());
2852     }
2853   }
2854 
2855   if (NarrowTy1.isVector())
2856     MIRBuilder.buildConcatVectors(DstReg, DstRegs);
2857   else
2858     MIRBuilder.buildBuildVector(DstReg, DstRegs);
2859 
2860   MI.eraseFromParent();
2861   return Legalized;
2862 }
2863 
2864 LegalizerHelper::LegalizeResult
2865 LegalizerHelper::fewerElementsVectorSelect(MachineInstr &MI, unsigned TypeIdx,
2866                                            LLT NarrowTy) {
2867   Register DstReg = MI.getOperand(0).getReg();
2868   Register CondReg = MI.getOperand(1).getReg();
2869 
2870   unsigned NumParts = 0;
2871   LLT NarrowTy0, NarrowTy1;
2872 
2873   LLT DstTy = MRI.getType(DstReg);
2874   LLT CondTy = MRI.getType(CondReg);
2875   unsigned Size = DstTy.getSizeInBits();
2876 
2877   assert(TypeIdx == 0 || CondTy.isVector());
2878 
2879   if (TypeIdx == 0) {
2880     NarrowTy0 = NarrowTy;
2881     NarrowTy1 = CondTy;
2882 
2883     unsigned NarrowSize = NarrowTy0.getSizeInBits();
2884     // FIXME: Don't know how to handle the situation where the small vectors
2885     // aren't all the same size yet.
2886     if (Size % NarrowSize != 0)
2887       return UnableToLegalize;
2888 
2889     NumParts = Size / NarrowSize;
2890 
2891     // Need to break down the condition type
2892     if (CondTy.isVector()) {
2893       if (CondTy.getNumElements() == NumParts)
2894         NarrowTy1 = CondTy.getElementType();
2895       else
2896         NarrowTy1 = LLT::vector(CondTy.getNumElements() / NumParts,
2897                                 CondTy.getScalarSizeInBits());
2898     }
2899   } else {
2900     NumParts = CondTy.getNumElements();
2901     if (NarrowTy.isVector()) {
2902       // TODO: Handle uneven breakdown.
2903       if (NumParts * NarrowTy.getNumElements() != CondTy.getNumElements())
2904         return UnableToLegalize;
2905 
2906       return UnableToLegalize;
2907     } else {
2908       NarrowTy0 = DstTy.getElementType();
2909       NarrowTy1 = NarrowTy;
2910     }
2911   }
2912 
2913   SmallVector<Register, 2> DstRegs, Src0Regs, Src1Regs, Src2Regs;
2914   if (CondTy.isVector())
2915     extractParts(MI.getOperand(1).getReg(), NarrowTy1, NumParts, Src0Regs);
2916 
2917   extractParts(MI.getOperand(2).getReg(), NarrowTy0, NumParts, Src1Regs);
2918   extractParts(MI.getOperand(3).getReg(), NarrowTy0, NumParts, Src2Regs);
2919 
2920   for (unsigned i = 0; i < NumParts; ++i) {
2921     Register DstReg = MRI.createGenericVirtualRegister(NarrowTy0);
2922     MIRBuilder.buildSelect(DstReg, CondTy.isVector() ? Src0Regs[i] : CondReg,
2923                            Src1Regs[i], Src2Regs[i]);
2924     DstRegs.push_back(DstReg);
2925   }
2926 
2927   if (NarrowTy0.isVector())
2928     MIRBuilder.buildConcatVectors(DstReg, DstRegs);
2929   else
2930     MIRBuilder.buildBuildVector(DstReg, DstRegs);
2931 
2932   MI.eraseFromParent();
2933   return Legalized;
2934 }
2935 
2936 LegalizerHelper::LegalizeResult
2937 LegalizerHelper::fewerElementsVectorPhi(MachineInstr &MI, unsigned TypeIdx,
2938                                         LLT NarrowTy) {
2939   const Register DstReg = MI.getOperand(0).getReg();
2940   LLT PhiTy = MRI.getType(DstReg);
2941   LLT LeftoverTy;
2942 
2943   // All of the operands need to have the same number of elements, so if we can
2944   // determine a type breakdown for the result type, we can for all of the
2945   // source types.
2946   int NumParts, NumLeftover;
2947   std::tie(NumParts, NumLeftover)
2948     = getNarrowTypeBreakDown(PhiTy, NarrowTy, LeftoverTy);
2949   if (NumParts < 0)
2950     return UnableToLegalize;
2951 
2952   SmallVector<Register, 4> DstRegs, LeftoverDstRegs;
2953   SmallVector<MachineInstrBuilder, 4> NewInsts;
2954 
2955   const int TotalNumParts = NumParts + NumLeftover;
2956 
2957   // Insert the new phis in the result block first.
2958   for (int I = 0; I != TotalNumParts; ++I) {
2959     LLT Ty = I < NumParts ? NarrowTy : LeftoverTy;
2960     Register PartDstReg = MRI.createGenericVirtualRegister(Ty);
2961     NewInsts.push_back(MIRBuilder.buildInstr(TargetOpcode::G_PHI)
2962                        .addDef(PartDstReg));
2963     if (I < NumParts)
2964       DstRegs.push_back(PartDstReg);
2965     else
2966       LeftoverDstRegs.push_back(PartDstReg);
2967   }
2968 
2969   MachineBasicBlock *MBB = MI.getParent();
2970   MIRBuilder.setInsertPt(*MBB, MBB->getFirstNonPHI());
2971   insertParts(DstReg, PhiTy, NarrowTy, DstRegs, LeftoverTy, LeftoverDstRegs);
2972 
2973   SmallVector<Register, 4> PartRegs, LeftoverRegs;
2974 
2975   // Insert code to extract the incoming values in each predecessor block.
2976   for (unsigned I = 1, E = MI.getNumOperands(); I != E; I += 2) {
2977     PartRegs.clear();
2978     LeftoverRegs.clear();
2979 
2980     Register SrcReg = MI.getOperand(I).getReg();
2981     MachineBasicBlock &OpMBB = *MI.getOperand(I + 1).getMBB();
2982     MIRBuilder.setInsertPt(OpMBB, OpMBB.getFirstTerminator());
2983 
2984     LLT Unused;
2985     if (!extractParts(SrcReg, PhiTy, NarrowTy, Unused, PartRegs,
2986                       LeftoverRegs))
2987       return UnableToLegalize;
2988 
2989     // Add the newly created operand splits to the existing instructions. The
2990     // odd-sized pieces are ordered after the requested NarrowTyArg sized
2991     // pieces.
2992     for (int J = 0; J != TotalNumParts; ++J) {
2993       MachineInstrBuilder MIB = NewInsts[J];
2994       MIB.addUse(J < NumParts ? PartRegs[J] : LeftoverRegs[J - NumParts]);
2995       MIB.addMBB(&OpMBB);
2996     }
2997   }
2998 
2999   MI.eraseFromParent();
3000   return Legalized;
3001 }
3002 
3003 LegalizerHelper::LegalizeResult
3004 LegalizerHelper::fewerElementsVectorUnmergeValues(MachineInstr &MI,
3005                                                   unsigned TypeIdx,
3006                                                   LLT NarrowTy) {
3007   if (TypeIdx != 1)
3008     return UnableToLegalize;
3009 
3010   const int NumDst = MI.getNumOperands() - 1;
3011   const Register SrcReg = MI.getOperand(NumDst).getReg();
3012   LLT SrcTy = MRI.getType(SrcReg);
3013 
3014   LLT DstTy = MRI.getType(MI.getOperand(0).getReg());
3015 
3016   // TODO: Create sequence of extracts.
3017   if (DstTy == NarrowTy)
3018     return UnableToLegalize;
3019 
3020   LLT GCDTy = getGCDType(SrcTy, NarrowTy);
3021   if (DstTy == GCDTy) {
3022     // This would just be a copy of the same unmerge.
3023     // TODO: Create extracts, pad with undef and create intermediate merges.
3024     return UnableToLegalize;
3025   }
3026 
3027   auto Unmerge = MIRBuilder.buildUnmerge(GCDTy, SrcReg);
3028   const int NumUnmerge = Unmerge->getNumOperands() - 1;
3029   const int PartsPerUnmerge = NumDst / NumUnmerge;
3030 
3031   for (int I = 0; I != NumUnmerge; ++I) {
3032     auto MIB = MIRBuilder.buildInstr(TargetOpcode::G_UNMERGE_VALUES);
3033 
3034     for (int J = 0; J != PartsPerUnmerge; ++J)
3035       MIB.addDef(MI.getOperand(I * PartsPerUnmerge + J).getReg());
3036     MIB.addUse(Unmerge.getReg(I));
3037   }
3038 
3039   MI.eraseFromParent();
3040   return Legalized;
3041 }
3042 
3043 LegalizerHelper::LegalizeResult
3044 LegalizerHelper::fewerElementsVectorBuildVector(MachineInstr &MI,
3045                                                 unsigned TypeIdx,
3046                                                 LLT NarrowTy) {
3047   assert(TypeIdx == 0 && "not a vector type index");
3048   Register DstReg = MI.getOperand(0).getReg();
3049   LLT DstTy = MRI.getType(DstReg);
3050   LLT SrcTy = DstTy.getElementType();
3051 
3052   int DstNumElts = DstTy.getNumElements();
3053   int NarrowNumElts = NarrowTy.getNumElements();
3054   int NumConcat = (DstNumElts + NarrowNumElts - 1) / NarrowNumElts;
3055   LLT WidenedDstTy = LLT::vector(NarrowNumElts * NumConcat, SrcTy);
3056 
3057   SmallVector<Register, 8> ConcatOps;
3058   SmallVector<Register, 8> SubBuildVector;
3059 
3060   Register UndefReg;
3061   if (WidenedDstTy != DstTy)
3062     UndefReg = MIRBuilder.buildUndef(SrcTy).getReg(0);
3063 
3064   // Create a G_CONCAT_VECTORS of NarrowTy pieces, padding with undef as
3065   // necessary.
3066   //
3067   // %3:_(<3 x s16>) = G_BUILD_VECTOR %0, %1, %2
3068   //   -> <2 x s16>
3069   //
3070   // %4:_(s16) = G_IMPLICIT_DEF
3071   // %5:_(<2 x s16>) = G_BUILD_VECTOR %0, %1
3072   // %6:_(<2 x s16>) = G_BUILD_VECTOR %2, %4
3073   // %7:_(<4 x s16>) = G_CONCAT_VECTORS %5, %6
3074   // %3:_(<3 x s16>) = G_EXTRACT %7, 0
3075   for (int I = 0; I != NumConcat; ++I) {
3076     for (int J = 0; J != NarrowNumElts; ++J) {
3077       int SrcIdx = NarrowNumElts * I + J;
3078 
3079       if (SrcIdx < DstNumElts) {
3080         Register SrcReg = MI.getOperand(SrcIdx + 1).getReg();
3081         SubBuildVector.push_back(SrcReg);
3082       } else
3083         SubBuildVector.push_back(UndefReg);
3084     }
3085 
3086     auto BuildVec = MIRBuilder.buildBuildVector(NarrowTy, SubBuildVector);
3087     ConcatOps.push_back(BuildVec.getReg(0));
3088     SubBuildVector.clear();
3089   }
3090 
3091   if (DstTy == WidenedDstTy)
3092     MIRBuilder.buildConcatVectors(DstReg, ConcatOps);
3093   else {
3094     auto Concat = MIRBuilder.buildConcatVectors(WidenedDstTy, ConcatOps);
3095     MIRBuilder.buildExtract(DstReg, Concat, 0);
3096   }
3097 
3098   MI.eraseFromParent();
3099   return Legalized;
3100 }
3101 
3102 LegalizerHelper::LegalizeResult
3103 LegalizerHelper::reduceLoadStoreWidth(MachineInstr &MI, unsigned TypeIdx,
3104                                       LLT NarrowTy) {
3105   // FIXME: Don't know how to handle secondary types yet.
3106   if (TypeIdx != 0)
3107     return UnableToLegalize;
3108 
3109   MachineMemOperand *MMO = *MI.memoperands_begin();
3110 
3111   // This implementation doesn't work for atomics. Give up instead of doing
3112   // something invalid.
3113   if (MMO->getOrdering() != AtomicOrdering::NotAtomic ||
3114       MMO->getFailureOrdering() != AtomicOrdering::NotAtomic)
3115     return UnableToLegalize;
3116 
3117   bool IsLoad = MI.getOpcode() == TargetOpcode::G_LOAD;
3118   Register ValReg = MI.getOperand(0).getReg();
3119   Register AddrReg = MI.getOperand(1).getReg();
3120   LLT ValTy = MRI.getType(ValReg);
3121 
3122   int NumParts = -1;
3123   int NumLeftover = -1;
3124   LLT LeftoverTy;
3125   SmallVector<Register, 8> NarrowRegs, NarrowLeftoverRegs;
3126   if (IsLoad) {
3127     std::tie(NumParts, NumLeftover) = getNarrowTypeBreakDown(ValTy, NarrowTy, LeftoverTy);
3128   } else {
3129     if (extractParts(ValReg, ValTy, NarrowTy, LeftoverTy, NarrowRegs,
3130                      NarrowLeftoverRegs)) {
3131       NumParts = NarrowRegs.size();
3132       NumLeftover = NarrowLeftoverRegs.size();
3133     }
3134   }
3135 
3136   if (NumParts == -1)
3137     return UnableToLegalize;
3138 
3139   const LLT OffsetTy = LLT::scalar(MRI.getType(AddrReg).getScalarSizeInBits());
3140 
3141   unsigned TotalSize = ValTy.getSizeInBits();
3142 
3143   // Split the load/store into PartTy sized pieces starting at Offset. If this
3144   // is a load, return the new registers in ValRegs. For a store, each elements
3145   // of ValRegs should be PartTy. Returns the next offset that needs to be
3146   // handled.
3147   auto splitTypePieces = [=](LLT PartTy, SmallVectorImpl<Register> &ValRegs,
3148                              unsigned Offset) -> unsigned {
3149     MachineFunction &MF = MIRBuilder.getMF();
3150     unsigned PartSize = PartTy.getSizeInBits();
3151     for (unsigned Idx = 0, E = NumParts; Idx != E && Offset < TotalSize;
3152          Offset += PartSize, ++Idx) {
3153       unsigned ByteSize = PartSize / 8;
3154       unsigned ByteOffset = Offset / 8;
3155       Register NewAddrReg;
3156 
3157       MIRBuilder.materializePtrAdd(NewAddrReg, AddrReg, OffsetTy, ByteOffset);
3158 
3159       MachineMemOperand *NewMMO =
3160         MF.getMachineMemOperand(MMO, ByteOffset, ByteSize);
3161 
3162       if (IsLoad) {
3163         Register Dst = MRI.createGenericVirtualRegister(PartTy);
3164         ValRegs.push_back(Dst);
3165         MIRBuilder.buildLoad(Dst, NewAddrReg, *NewMMO);
3166       } else {
3167         MIRBuilder.buildStore(ValRegs[Idx], NewAddrReg, *NewMMO);
3168       }
3169     }
3170 
3171     return Offset;
3172   };
3173 
3174   unsigned HandledOffset = splitTypePieces(NarrowTy, NarrowRegs, 0);
3175 
3176   // Handle the rest of the register if this isn't an even type breakdown.
3177   if (LeftoverTy.isValid())
3178     splitTypePieces(LeftoverTy, NarrowLeftoverRegs, HandledOffset);
3179 
3180   if (IsLoad) {
3181     insertParts(ValReg, ValTy, NarrowTy, NarrowRegs,
3182                 LeftoverTy, NarrowLeftoverRegs);
3183   }
3184 
3185   MI.eraseFromParent();
3186   return Legalized;
3187 }
3188 
3189 LegalizerHelper::LegalizeResult
3190 LegalizerHelper::fewerElementsVectorSextInReg(MachineInstr &MI, unsigned TypeIdx,
3191                                               LLT NarrowTy) {
3192   Register DstReg = MI.getOperand(0).getReg();
3193   Register SrcReg = MI.getOperand(1).getReg();
3194   int64_t Imm = MI.getOperand(2).getImm();
3195 
3196   LLT DstTy = MRI.getType(DstReg);
3197 
3198   SmallVector<Register, 8> Parts;
3199   LLT GCDTy = extractGCDType(Parts, DstTy, NarrowTy, SrcReg);
3200   LLT LCMTy = buildLCMMergePieces(DstTy, NarrowTy, GCDTy, Parts);
3201 
3202   for (Register &R : Parts)
3203     R = MIRBuilder.buildSExtInReg(NarrowTy, R, Imm).getReg(0);
3204 
3205   buildWidenedRemergeToDst(DstReg, LCMTy, Parts);
3206 
3207   MI.eraseFromParent();
3208   return Legalized;
3209 }
3210 
3211 LegalizerHelper::LegalizeResult
3212 LegalizerHelper::fewerElementsVector(MachineInstr &MI, unsigned TypeIdx,
3213                                      LLT NarrowTy) {
3214   using namespace TargetOpcode;
3215 
3216   MIRBuilder.setInstr(MI);
3217   switch (MI.getOpcode()) {
3218   case G_IMPLICIT_DEF:
3219     return fewerElementsVectorImplicitDef(MI, TypeIdx, NarrowTy);
3220   case G_AND:
3221   case G_OR:
3222   case G_XOR:
3223   case G_ADD:
3224   case G_SUB:
3225   case G_MUL:
3226   case G_SMULH:
3227   case G_UMULH:
3228   case G_FADD:
3229   case G_FMUL:
3230   case G_FSUB:
3231   case G_FNEG:
3232   case G_FABS:
3233   case G_FCANONICALIZE:
3234   case G_FDIV:
3235   case G_FREM:
3236   case G_FMA:
3237   case G_FMAD:
3238   case G_FPOW:
3239   case G_FEXP:
3240   case G_FEXP2:
3241   case G_FLOG:
3242   case G_FLOG2:
3243   case G_FLOG10:
3244   case G_FNEARBYINT:
3245   case G_FCEIL:
3246   case G_FFLOOR:
3247   case G_FRINT:
3248   case G_INTRINSIC_ROUND:
3249   case G_INTRINSIC_TRUNC:
3250   case G_FCOS:
3251   case G_FSIN:
3252   case G_FSQRT:
3253   case G_BSWAP:
3254   case G_BITREVERSE:
3255   case G_SDIV:
3256   case G_UDIV:
3257   case G_SREM:
3258   case G_UREM:
3259   case G_SMIN:
3260   case G_SMAX:
3261   case G_UMIN:
3262   case G_UMAX:
3263   case G_FMINNUM:
3264   case G_FMAXNUM:
3265   case G_FMINNUM_IEEE:
3266   case G_FMAXNUM_IEEE:
3267   case G_FMINIMUM:
3268   case G_FMAXIMUM:
3269     return fewerElementsVectorBasic(MI, TypeIdx, NarrowTy);
3270   case G_SHL:
3271   case G_LSHR:
3272   case G_ASHR:
3273   case G_CTLZ:
3274   case G_CTLZ_ZERO_UNDEF:
3275   case G_CTTZ:
3276   case G_CTTZ_ZERO_UNDEF:
3277   case G_CTPOP:
3278   case G_FCOPYSIGN:
3279     return fewerElementsVectorMultiEltType(MI, TypeIdx, NarrowTy);
3280   case G_ZEXT:
3281   case G_SEXT:
3282   case G_ANYEXT:
3283   case G_FPEXT:
3284   case G_FPTRUNC:
3285   case G_SITOFP:
3286   case G_UITOFP:
3287   case G_FPTOSI:
3288   case G_FPTOUI:
3289   case G_INTTOPTR:
3290   case G_PTRTOINT:
3291   case G_ADDRSPACE_CAST:
3292     return fewerElementsVectorCasts(MI, TypeIdx, NarrowTy);
3293   case G_ICMP:
3294   case G_FCMP:
3295     return fewerElementsVectorCmp(MI, TypeIdx, NarrowTy);
3296   case G_SELECT:
3297     return fewerElementsVectorSelect(MI, TypeIdx, NarrowTy);
3298   case G_PHI:
3299     return fewerElementsVectorPhi(MI, TypeIdx, NarrowTy);
3300   case G_UNMERGE_VALUES:
3301     return fewerElementsVectorUnmergeValues(MI, TypeIdx, NarrowTy);
3302   case G_BUILD_VECTOR:
3303     return fewerElementsVectorBuildVector(MI, TypeIdx, NarrowTy);
3304   case G_LOAD:
3305   case G_STORE:
3306     return reduceLoadStoreWidth(MI, TypeIdx, NarrowTy);
3307   case G_SEXT_INREG:
3308     return fewerElementsVectorSextInReg(MI, TypeIdx, NarrowTy);
3309   default:
3310     return UnableToLegalize;
3311   }
3312 }
3313 
3314 LegalizerHelper::LegalizeResult
3315 LegalizerHelper::narrowScalarShiftByConstant(MachineInstr &MI, const APInt &Amt,
3316                                              const LLT HalfTy, const LLT AmtTy) {
3317 
3318   Register InL = MRI.createGenericVirtualRegister(HalfTy);
3319   Register InH = MRI.createGenericVirtualRegister(HalfTy);
3320   MIRBuilder.buildUnmerge({InL, InH}, MI.getOperand(1));
3321 
3322   if (Amt.isNullValue()) {
3323     MIRBuilder.buildMerge(MI.getOperand(0), {InL, InH});
3324     MI.eraseFromParent();
3325     return Legalized;
3326   }
3327 
3328   LLT NVT = HalfTy;
3329   unsigned NVTBits = HalfTy.getSizeInBits();
3330   unsigned VTBits = 2 * NVTBits;
3331 
3332   SrcOp Lo(Register(0)), Hi(Register(0));
3333   if (MI.getOpcode() == TargetOpcode::G_SHL) {
3334     if (Amt.ugt(VTBits)) {
3335       Lo = Hi = MIRBuilder.buildConstant(NVT, 0);
3336     } else if (Amt.ugt(NVTBits)) {
3337       Lo = MIRBuilder.buildConstant(NVT, 0);
3338       Hi = MIRBuilder.buildShl(NVT, InL,
3339                                MIRBuilder.buildConstant(AmtTy, Amt - NVTBits));
3340     } else if (Amt == NVTBits) {
3341       Lo = MIRBuilder.buildConstant(NVT, 0);
3342       Hi = InL;
3343     } else {
3344       Lo = MIRBuilder.buildShl(NVT, InL, MIRBuilder.buildConstant(AmtTy, Amt));
3345       auto OrLHS =
3346           MIRBuilder.buildShl(NVT, InH, MIRBuilder.buildConstant(AmtTy, Amt));
3347       auto OrRHS = MIRBuilder.buildLShr(
3348           NVT, InL, MIRBuilder.buildConstant(AmtTy, -Amt + NVTBits));
3349       Hi = MIRBuilder.buildOr(NVT, OrLHS, OrRHS);
3350     }
3351   } else if (MI.getOpcode() == TargetOpcode::G_LSHR) {
3352     if (Amt.ugt(VTBits)) {
3353       Lo = Hi = MIRBuilder.buildConstant(NVT, 0);
3354     } else if (Amt.ugt(NVTBits)) {
3355       Lo = MIRBuilder.buildLShr(NVT, InH,
3356                                 MIRBuilder.buildConstant(AmtTy, Amt - NVTBits));
3357       Hi = MIRBuilder.buildConstant(NVT, 0);
3358     } else if (Amt == NVTBits) {
3359       Lo = InH;
3360       Hi = MIRBuilder.buildConstant(NVT, 0);
3361     } else {
3362       auto ShiftAmtConst = MIRBuilder.buildConstant(AmtTy, Amt);
3363 
3364       auto OrLHS = MIRBuilder.buildLShr(NVT, InL, ShiftAmtConst);
3365       auto OrRHS = MIRBuilder.buildShl(
3366           NVT, InH, MIRBuilder.buildConstant(AmtTy, -Amt + NVTBits));
3367 
3368       Lo = MIRBuilder.buildOr(NVT, OrLHS, OrRHS);
3369       Hi = MIRBuilder.buildLShr(NVT, InH, ShiftAmtConst);
3370     }
3371   } else {
3372     if (Amt.ugt(VTBits)) {
3373       Hi = Lo = MIRBuilder.buildAShr(
3374           NVT, InH, MIRBuilder.buildConstant(AmtTy, NVTBits - 1));
3375     } else if (Amt.ugt(NVTBits)) {
3376       Lo = MIRBuilder.buildAShr(NVT, InH,
3377                                 MIRBuilder.buildConstant(AmtTy, Amt - NVTBits));
3378       Hi = MIRBuilder.buildAShr(NVT, InH,
3379                                 MIRBuilder.buildConstant(AmtTy, NVTBits - 1));
3380     } else if (Amt == NVTBits) {
3381       Lo = InH;
3382       Hi = MIRBuilder.buildAShr(NVT, InH,
3383                                 MIRBuilder.buildConstant(AmtTy, NVTBits - 1));
3384     } else {
3385       auto ShiftAmtConst = MIRBuilder.buildConstant(AmtTy, Amt);
3386 
3387       auto OrLHS = MIRBuilder.buildLShr(NVT, InL, ShiftAmtConst);
3388       auto OrRHS = MIRBuilder.buildShl(
3389           NVT, InH, MIRBuilder.buildConstant(AmtTy, -Amt + NVTBits));
3390 
3391       Lo = MIRBuilder.buildOr(NVT, OrLHS, OrRHS);
3392       Hi = MIRBuilder.buildAShr(NVT, InH, ShiftAmtConst);
3393     }
3394   }
3395 
3396   MIRBuilder.buildMerge(MI.getOperand(0), {Lo, Hi});
3397   MI.eraseFromParent();
3398 
3399   return Legalized;
3400 }
3401 
3402 // TODO: Optimize if constant shift amount.
3403 LegalizerHelper::LegalizeResult
3404 LegalizerHelper::narrowScalarShift(MachineInstr &MI, unsigned TypeIdx,
3405                                    LLT RequestedTy) {
3406   if (TypeIdx == 1) {
3407     Observer.changingInstr(MI);
3408     narrowScalarSrc(MI, RequestedTy, 2);
3409     Observer.changedInstr(MI);
3410     return Legalized;
3411   }
3412 
3413   Register DstReg = MI.getOperand(0).getReg();
3414   LLT DstTy = MRI.getType(DstReg);
3415   if (DstTy.isVector())
3416     return UnableToLegalize;
3417 
3418   Register Amt = MI.getOperand(2).getReg();
3419   LLT ShiftAmtTy = MRI.getType(Amt);
3420   const unsigned DstEltSize = DstTy.getScalarSizeInBits();
3421   if (DstEltSize % 2 != 0)
3422     return UnableToLegalize;
3423 
3424   // Ignore the input type. We can only go to exactly half the size of the
3425   // input. If that isn't small enough, the resulting pieces will be further
3426   // legalized.
3427   const unsigned NewBitSize = DstEltSize / 2;
3428   const LLT HalfTy = LLT::scalar(NewBitSize);
3429   const LLT CondTy = LLT::scalar(1);
3430 
3431   if (const MachineInstr *KShiftAmt =
3432           getOpcodeDef(TargetOpcode::G_CONSTANT, Amt, MRI)) {
3433     return narrowScalarShiftByConstant(
3434         MI, KShiftAmt->getOperand(1).getCImm()->getValue(), HalfTy, ShiftAmtTy);
3435   }
3436 
3437   // TODO: Expand with known bits.
3438 
3439   // Handle the fully general expansion by an unknown amount.
3440   auto NewBits = MIRBuilder.buildConstant(ShiftAmtTy, NewBitSize);
3441 
3442   Register InL = MRI.createGenericVirtualRegister(HalfTy);
3443   Register InH = MRI.createGenericVirtualRegister(HalfTy);
3444   MIRBuilder.buildUnmerge({InL, InH}, MI.getOperand(1));
3445 
3446   auto AmtExcess = MIRBuilder.buildSub(ShiftAmtTy, Amt, NewBits);
3447   auto AmtLack = MIRBuilder.buildSub(ShiftAmtTy, NewBits, Amt);
3448 
3449   auto Zero = MIRBuilder.buildConstant(ShiftAmtTy, 0);
3450   auto IsShort = MIRBuilder.buildICmp(ICmpInst::ICMP_ULT, CondTy, Amt, NewBits);
3451   auto IsZero = MIRBuilder.buildICmp(ICmpInst::ICMP_EQ, CondTy, Amt, Zero);
3452 
3453   Register ResultRegs[2];
3454   switch (MI.getOpcode()) {
3455   case TargetOpcode::G_SHL: {
3456     // Short: ShAmt < NewBitSize
3457     auto LoS = MIRBuilder.buildShl(HalfTy, InL, Amt);
3458 
3459     auto LoOr = MIRBuilder.buildLShr(HalfTy, InL, AmtLack);
3460     auto HiOr = MIRBuilder.buildShl(HalfTy, InH, Amt);
3461     auto HiS = MIRBuilder.buildOr(HalfTy, LoOr, HiOr);
3462 
3463     // Long: ShAmt >= NewBitSize
3464     auto LoL = MIRBuilder.buildConstant(HalfTy, 0);         // Lo part is zero.
3465     auto HiL = MIRBuilder.buildShl(HalfTy, InL, AmtExcess); // Hi from Lo part.
3466 
3467     auto Lo = MIRBuilder.buildSelect(HalfTy, IsShort, LoS, LoL);
3468     auto Hi = MIRBuilder.buildSelect(
3469         HalfTy, IsZero, InH, MIRBuilder.buildSelect(HalfTy, IsShort, HiS, HiL));
3470 
3471     ResultRegs[0] = Lo.getReg(0);
3472     ResultRegs[1] = Hi.getReg(0);
3473     break;
3474   }
3475   case TargetOpcode::G_LSHR:
3476   case TargetOpcode::G_ASHR: {
3477     // Short: ShAmt < NewBitSize
3478     auto HiS = MIRBuilder.buildInstr(MI.getOpcode(), {HalfTy}, {InH, Amt});
3479 
3480     auto LoOr = MIRBuilder.buildLShr(HalfTy, InL, Amt);
3481     auto HiOr = MIRBuilder.buildShl(HalfTy, InH, AmtLack);
3482     auto LoS = MIRBuilder.buildOr(HalfTy, LoOr, HiOr);
3483 
3484     // Long: ShAmt >= NewBitSize
3485     MachineInstrBuilder HiL;
3486     if (MI.getOpcode() == TargetOpcode::G_LSHR) {
3487       HiL = MIRBuilder.buildConstant(HalfTy, 0);            // Hi part is zero.
3488     } else {
3489       auto ShiftAmt = MIRBuilder.buildConstant(ShiftAmtTy, NewBitSize - 1);
3490       HiL = MIRBuilder.buildAShr(HalfTy, InH, ShiftAmt);    // Sign of Hi part.
3491     }
3492     auto LoL = MIRBuilder.buildInstr(MI.getOpcode(), {HalfTy},
3493                                      {InH, AmtExcess});     // Lo from Hi part.
3494 
3495     auto Lo = MIRBuilder.buildSelect(
3496         HalfTy, IsZero, InL, MIRBuilder.buildSelect(HalfTy, IsShort, LoS, LoL));
3497 
3498     auto Hi = MIRBuilder.buildSelect(HalfTy, IsShort, HiS, HiL);
3499 
3500     ResultRegs[0] = Lo.getReg(0);
3501     ResultRegs[1] = Hi.getReg(0);
3502     break;
3503   }
3504   default:
3505     llvm_unreachable("not a shift");
3506   }
3507 
3508   MIRBuilder.buildMerge(DstReg, ResultRegs);
3509   MI.eraseFromParent();
3510   return Legalized;
3511 }
3512 
3513 LegalizerHelper::LegalizeResult
3514 LegalizerHelper::moreElementsVectorPhi(MachineInstr &MI, unsigned TypeIdx,
3515                                        LLT MoreTy) {
3516   assert(TypeIdx == 0 && "Expecting only Idx 0");
3517 
3518   Observer.changingInstr(MI);
3519   for (unsigned I = 1, E = MI.getNumOperands(); I != E; I += 2) {
3520     MachineBasicBlock &OpMBB = *MI.getOperand(I + 1).getMBB();
3521     MIRBuilder.setInsertPt(OpMBB, OpMBB.getFirstTerminator());
3522     moreElementsVectorSrc(MI, MoreTy, I);
3523   }
3524 
3525   MachineBasicBlock &MBB = *MI.getParent();
3526   MIRBuilder.setInsertPt(MBB, --MBB.getFirstNonPHI());
3527   moreElementsVectorDst(MI, MoreTy, 0);
3528   Observer.changedInstr(MI);
3529   return Legalized;
3530 }
3531 
3532 LegalizerHelper::LegalizeResult
3533 LegalizerHelper::moreElementsVector(MachineInstr &MI, unsigned TypeIdx,
3534                                     LLT MoreTy) {
3535   MIRBuilder.setInstr(MI);
3536   unsigned Opc = MI.getOpcode();
3537   switch (Opc) {
3538   case TargetOpcode::G_IMPLICIT_DEF:
3539   case TargetOpcode::G_LOAD: {
3540     if (TypeIdx != 0)
3541       return UnableToLegalize;
3542     Observer.changingInstr(MI);
3543     moreElementsVectorDst(MI, MoreTy, 0);
3544     Observer.changedInstr(MI);
3545     return Legalized;
3546   }
3547   case TargetOpcode::G_STORE:
3548     if (TypeIdx != 0)
3549       return UnableToLegalize;
3550     Observer.changingInstr(MI);
3551     moreElementsVectorSrc(MI, MoreTy, 0);
3552     Observer.changedInstr(MI);
3553     return Legalized;
3554   case TargetOpcode::G_AND:
3555   case TargetOpcode::G_OR:
3556   case TargetOpcode::G_XOR:
3557   case TargetOpcode::G_SMIN:
3558   case TargetOpcode::G_SMAX:
3559   case TargetOpcode::G_UMIN:
3560   case TargetOpcode::G_UMAX:
3561   case TargetOpcode::G_FMINNUM:
3562   case TargetOpcode::G_FMAXNUM:
3563   case TargetOpcode::G_FMINNUM_IEEE:
3564   case TargetOpcode::G_FMAXNUM_IEEE:
3565   case TargetOpcode::G_FMINIMUM:
3566   case TargetOpcode::G_FMAXIMUM: {
3567     Observer.changingInstr(MI);
3568     moreElementsVectorSrc(MI, MoreTy, 1);
3569     moreElementsVectorSrc(MI, MoreTy, 2);
3570     moreElementsVectorDst(MI, MoreTy, 0);
3571     Observer.changedInstr(MI);
3572     return Legalized;
3573   }
3574   case TargetOpcode::G_EXTRACT:
3575     if (TypeIdx != 1)
3576       return UnableToLegalize;
3577     Observer.changingInstr(MI);
3578     moreElementsVectorSrc(MI, MoreTy, 1);
3579     Observer.changedInstr(MI);
3580     return Legalized;
3581   case TargetOpcode::G_INSERT:
3582     if (TypeIdx != 0)
3583       return UnableToLegalize;
3584     Observer.changingInstr(MI);
3585     moreElementsVectorSrc(MI, MoreTy, 1);
3586     moreElementsVectorDst(MI, MoreTy, 0);
3587     Observer.changedInstr(MI);
3588     return Legalized;
3589   case TargetOpcode::G_SELECT:
3590     if (TypeIdx != 0)
3591       return UnableToLegalize;
3592     if (MRI.getType(MI.getOperand(1).getReg()).isVector())
3593       return UnableToLegalize;
3594 
3595     Observer.changingInstr(MI);
3596     moreElementsVectorSrc(MI, MoreTy, 2);
3597     moreElementsVectorSrc(MI, MoreTy, 3);
3598     moreElementsVectorDst(MI, MoreTy, 0);
3599     Observer.changedInstr(MI);
3600     return Legalized;
3601   case TargetOpcode::G_UNMERGE_VALUES: {
3602     if (TypeIdx != 1)
3603       return UnableToLegalize;
3604 
3605     LLT DstTy = MRI.getType(MI.getOperand(0).getReg());
3606     int NumDst = MI.getNumOperands() - 1;
3607     moreElementsVectorSrc(MI, MoreTy, NumDst);
3608 
3609     auto MIB = MIRBuilder.buildInstr(TargetOpcode::G_UNMERGE_VALUES);
3610     for (int I = 0; I != NumDst; ++I)
3611       MIB.addDef(MI.getOperand(I).getReg());
3612 
3613     int NewNumDst = MoreTy.getSizeInBits() / DstTy.getSizeInBits();
3614     for (int I = NumDst; I != NewNumDst; ++I)
3615       MIB.addDef(MRI.createGenericVirtualRegister(DstTy));
3616 
3617     MIB.addUse(MI.getOperand(NumDst).getReg());
3618     MI.eraseFromParent();
3619     return Legalized;
3620   }
3621   case TargetOpcode::G_PHI:
3622     return moreElementsVectorPhi(MI, TypeIdx, MoreTy);
3623   default:
3624     return UnableToLegalize;
3625   }
3626 }
3627 
3628 void LegalizerHelper::multiplyRegisters(SmallVectorImpl<Register> &DstRegs,
3629                                         ArrayRef<Register> Src1Regs,
3630                                         ArrayRef<Register> Src2Regs,
3631                                         LLT NarrowTy) {
3632   MachineIRBuilder &B = MIRBuilder;
3633   unsigned SrcParts = Src1Regs.size();
3634   unsigned DstParts = DstRegs.size();
3635 
3636   unsigned DstIdx = 0; // Low bits of the result.
3637   Register FactorSum =
3638       B.buildMul(NarrowTy, Src1Regs[DstIdx], Src2Regs[DstIdx]).getReg(0);
3639   DstRegs[DstIdx] = FactorSum;
3640 
3641   unsigned CarrySumPrevDstIdx;
3642   SmallVector<Register, 4> Factors;
3643 
3644   for (DstIdx = 1; DstIdx < DstParts; DstIdx++) {
3645     // Collect low parts of muls for DstIdx.
3646     for (unsigned i = DstIdx + 1 < SrcParts ? 0 : DstIdx - SrcParts + 1;
3647          i <= std::min(DstIdx, SrcParts - 1); ++i) {
3648       MachineInstrBuilder Mul =
3649           B.buildMul(NarrowTy, Src1Regs[DstIdx - i], Src2Regs[i]);
3650       Factors.push_back(Mul.getReg(0));
3651     }
3652     // Collect high parts of muls from previous DstIdx.
3653     for (unsigned i = DstIdx < SrcParts ? 0 : DstIdx - SrcParts;
3654          i <= std::min(DstIdx - 1, SrcParts - 1); ++i) {
3655       MachineInstrBuilder Umulh =
3656           B.buildUMulH(NarrowTy, Src1Regs[DstIdx - 1 - i], Src2Regs[i]);
3657       Factors.push_back(Umulh.getReg(0));
3658     }
3659     // Add CarrySum from additions calculated for previous DstIdx.
3660     if (DstIdx != 1) {
3661       Factors.push_back(CarrySumPrevDstIdx);
3662     }
3663 
3664     Register CarrySum;
3665     // Add all factors and accumulate all carries into CarrySum.
3666     if (DstIdx != DstParts - 1) {
3667       MachineInstrBuilder Uaddo =
3668           B.buildUAddo(NarrowTy, LLT::scalar(1), Factors[0], Factors[1]);
3669       FactorSum = Uaddo.getReg(0);
3670       CarrySum = B.buildZExt(NarrowTy, Uaddo.getReg(1)).getReg(0);
3671       for (unsigned i = 2; i < Factors.size(); ++i) {
3672         MachineInstrBuilder Uaddo =
3673             B.buildUAddo(NarrowTy, LLT::scalar(1), FactorSum, Factors[i]);
3674         FactorSum = Uaddo.getReg(0);
3675         MachineInstrBuilder Carry = B.buildZExt(NarrowTy, Uaddo.getReg(1));
3676         CarrySum = B.buildAdd(NarrowTy, CarrySum, Carry).getReg(0);
3677       }
3678     } else {
3679       // Since value for the next index is not calculated, neither is CarrySum.
3680       FactorSum = B.buildAdd(NarrowTy, Factors[0], Factors[1]).getReg(0);
3681       for (unsigned i = 2; i < Factors.size(); ++i)
3682         FactorSum = B.buildAdd(NarrowTy, FactorSum, Factors[i]).getReg(0);
3683     }
3684 
3685     CarrySumPrevDstIdx = CarrySum;
3686     DstRegs[DstIdx] = FactorSum;
3687     Factors.clear();
3688   }
3689 }
3690 
3691 LegalizerHelper::LegalizeResult
3692 LegalizerHelper::narrowScalarMul(MachineInstr &MI, LLT NarrowTy) {
3693   Register DstReg = MI.getOperand(0).getReg();
3694   Register Src1 = MI.getOperand(1).getReg();
3695   Register Src2 = MI.getOperand(2).getReg();
3696 
3697   LLT Ty = MRI.getType(DstReg);
3698   if (Ty.isVector())
3699     return UnableToLegalize;
3700 
3701   unsigned SrcSize = MRI.getType(Src1).getSizeInBits();
3702   unsigned DstSize = Ty.getSizeInBits();
3703   unsigned NarrowSize = NarrowTy.getSizeInBits();
3704   if (DstSize % NarrowSize != 0 || SrcSize % NarrowSize != 0)
3705     return UnableToLegalize;
3706 
3707   unsigned NumDstParts = DstSize / NarrowSize;
3708   unsigned NumSrcParts = SrcSize / NarrowSize;
3709   bool IsMulHigh = MI.getOpcode() == TargetOpcode::G_UMULH;
3710   unsigned DstTmpParts = NumDstParts * (IsMulHigh ? 2 : 1);
3711 
3712   SmallVector<Register, 2> Src1Parts, Src2Parts;
3713   SmallVector<Register, 2> DstTmpRegs(DstTmpParts);
3714   extractParts(Src1, NarrowTy, NumSrcParts, Src1Parts);
3715   extractParts(Src2, NarrowTy, NumSrcParts, Src2Parts);
3716   multiplyRegisters(DstTmpRegs, Src1Parts, Src2Parts, NarrowTy);
3717 
3718   // Take only high half of registers if this is high mul.
3719   ArrayRef<Register> DstRegs(
3720       IsMulHigh ? &DstTmpRegs[DstTmpParts / 2] : &DstTmpRegs[0], NumDstParts);
3721   MIRBuilder.buildMerge(DstReg, DstRegs);
3722   MI.eraseFromParent();
3723   return Legalized;
3724 }
3725 
3726 LegalizerHelper::LegalizeResult
3727 LegalizerHelper::narrowScalarExtract(MachineInstr &MI, unsigned TypeIdx,
3728                                      LLT NarrowTy) {
3729   if (TypeIdx != 1)
3730     return UnableToLegalize;
3731 
3732   uint64_t NarrowSize = NarrowTy.getSizeInBits();
3733 
3734   int64_t SizeOp1 = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
3735   // FIXME: add support for when SizeOp1 isn't an exact multiple of
3736   // NarrowSize.
3737   if (SizeOp1 % NarrowSize != 0)
3738     return UnableToLegalize;
3739   int NumParts = SizeOp1 / NarrowSize;
3740 
3741   SmallVector<Register, 2> SrcRegs, DstRegs;
3742   SmallVector<uint64_t, 2> Indexes;
3743   extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs);
3744 
3745   Register OpReg = MI.getOperand(0).getReg();
3746   uint64_t OpStart = MI.getOperand(2).getImm();
3747   uint64_t OpSize = MRI.getType(OpReg).getSizeInBits();
3748   for (int i = 0; i < NumParts; ++i) {
3749     unsigned SrcStart = i * NarrowSize;
3750 
3751     if (SrcStart + NarrowSize <= OpStart || SrcStart >= OpStart + OpSize) {
3752       // No part of the extract uses this subregister, ignore it.
3753       continue;
3754     } else if (SrcStart == OpStart && NarrowTy == MRI.getType(OpReg)) {
3755       // The entire subregister is extracted, forward the value.
3756       DstRegs.push_back(SrcRegs[i]);
3757       continue;
3758     }
3759 
3760     // OpSegStart is where this destination segment would start in OpReg if it
3761     // extended infinitely in both directions.
3762     int64_t ExtractOffset;
3763     uint64_t SegSize;
3764     if (OpStart < SrcStart) {
3765       ExtractOffset = 0;
3766       SegSize = std::min(NarrowSize, OpStart + OpSize - SrcStart);
3767     } else {
3768       ExtractOffset = OpStart - SrcStart;
3769       SegSize = std::min(SrcStart + NarrowSize - OpStart, OpSize);
3770     }
3771 
3772     Register SegReg = SrcRegs[i];
3773     if (ExtractOffset != 0 || SegSize != NarrowSize) {
3774       // A genuine extract is needed.
3775       SegReg = MRI.createGenericVirtualRegister(LLT::scalar(SegSize));
3776       MIRBuilder.buildExtract(SegReg, SrcRegs[i], ExtractOffset);
3777     }
3778 
3779     DstRegs.push_back(SegReg);
3780   }
3781 
3782   Register DstReg = MI.getOperand(0).getReg();
3783   if(MRI.getType(DstReg).isVector())
3784     MIRBuilder.buildBuildVector(DstReg, DstRegs);
3785   else
3786     MIRBuilder.buildMerge(DstReg, DstRegs);
3787   MI.eraseFromParent();
3788   return Legalized;
3789 }
3790 
3791 LegalizerHelper::LegalizeResult
3792 LegalizerHelper::narrowScalarInsert(MachineInstr &MI, unsigned TypeIdx,
3793                                     LLT NarrowTy) {
3794   // FIXME: Don't know how to handle secondary types yet.
3795   if (TypeIdx != 0)
3796     return UnableToLegalize;
3797 
3798   uint64_t SizeOp0 = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
3799   uint64_t NarrowSize = NarrowTy.getSizeInBits();
3800 
3801   // FIXME: add support for when SizeOp0 isn't an exact multiple of
3802   // NarrowSize.
3803   if (SizeOp0 % NarrowSize != 0)
3804     return UnableToLegalize;
3805 
3806   int NumParts = SizeOp0 / NarrowSize;
3807 
3808   SmallVector<Register, 2> SrcRegs, DstRegs;
3809   SmallVector<uint64_t, 2> Indexes;
3810   extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs);
3811 
3812   Register OpReg = MI.getOperand(2).getReg();
3813   uint64_t OpStart = MI.getOperand(3).getImm();
3814   uint64_t OpSize = MRI.getType(OpReg).getSizeInBits();
3815   for (int i = 0; i < NumParts; ++i) {
3816     unsigned DstStart = i * NarrowSize;
3817 
3818     if (DstStart + NarrowSize <= OpStart || DstStart >= OpStart + OpSize) {
3819       // No part of the insert affects this subregister, forward the original.
3820       DstRegs.push_back(SrcRegs[i]);
3821       continue;
3822     } else if (DstStart == OpStart && NarrowTy == MRI.getType(OpReg)) {
3823       // The entire subregister is defined by this insert, forward the new
3824       // value.
3825       DstRegs.push_back(OpReg);
3826       continue;
3827     }
3828 
3829     // OpSegStart is where this destination segment would start in OpReg if it
3830     // extended infinitely in both directions.
3831     int64_t ExtractOffset, InsertOffset;
3832     uint64_t SegSize;
3833     if (OpStart < DstStart) {
3834       InsertOffset = 0;
3835       ExtractOffset = DstStart - OpStart;
3836       SegSize = std::min(NarrowSize, OpStart + OpSize - DstStart);
3837     } else {
3838       InsertOffset = OpStart - DstStart;
3839       ExtractOffset = 0;
3840       SegSize =
3841         std::min(NarrowSize - InsertOffset, OpStart + OpSize - DstStart);
3842     }
3843 
3844     Register SegReg = OpReg;
3845     if (ExtractOffset != 0 || SegSize != OpSize) {
3846       // A genuine extract is needed.
3847       SegReg = MRI.createGenericVirtualRegister(LLT::scalar(SegSize));
3848       MIRBuilder.buildExtract(SegReg, OpReg, ExtractOffset);
3849     }
3850 
3851     Register DstReg = MRI.createGenericVirtualRegister(NarrowTy);
3852     MIRBuilder.buildInsert(DstReg, SrcRegs[i], SegReg, InsertOffset);
3853     DstRegs.push_back(DstReg);
3854   }
3855 
3856   assert(DstRegs.size() == (unsigned)NumParts && "not all parts covered");
3857   Register DstReg = MI.getOperand(0).getReg();
3858   if(MRI.getType(DstReg).isVector())
3859     MIRBuilder.buildBuildVector(DstReg, DstRegs);
3860   else
3861     MIRBuilder.buildMerge(DstReg, DstRegs);
3862   MI.eraseFromParent();
3863   return Legalized;
3864 }
3865 
3866 LegalizerHelper::LegalizeResult
3867 LegalizerHelper::narrowScalarBasic(MachineInstr &MI, unsigned TypeIdx,
3868                                    LLT NarrowTy) {
3869   Register DstReg = MI.getOperand(0).getReg();
3870   LLT DstTy = MRI.getType(DstReg);
3871 
3872   assert(MI.getNumOperands() == 3 && TypeIdx == 0);
3873 
3874   SmallVector<Register, 4> DstRegs, DstLeftoverRegs;
3875   SmallVector<Register, 4> Src0Regs, Src0LeftoverRegs;
3876   SmallVector<Register, 4> Src1Regs, Src1LeftoverRegs;
3877   LLT LeftoverTy;
3878   if (!extractParts(MI.getOperand(1).getReg(), DstTy, NarrowTy, LeftoverTy,
3879                     Src0Regs, Src0LeftoverRegs))
3880     return UnableToLegalize;
3881 
3882   LLT Unused;
3883   if (!extractParts(MI.getOperand(2).getReg(), DstTy, NarrowTy, Unused,
3884                     Src1Regs, Src1LeftoverRegs))
3885     llvm_unreachable("inconsistent extractParts result");
3886 
3887   for (unsigned I = 0, E = Src1Regs.size(); I != E; ++I) {
3888     auto Inst = MIRBuilder.buildInstr(MI.getOpcode(), {NarrowTy},
3889                                         {Src0Regs[I], Src1Regs[I]});
3890     DstRegs.push_back(Inst.getReg(0));
3891   }
3892 
3893   for (unsigned I = 0, E = Src1LeftoverRegs.size(); I != E; ++I) {
3894     auto Inst = MIRBuilder.buildInstr(
3895       MI.getOpcode(),
3896       {LeftoverTy}, {Src0LeftoverRegs[I], Src1LeftoverRegs[I]});
3897     DstLeftoverRegs.push_back(Inst.getReg(0));
3898   }
3899 
3900   insertParts(DstReg, DstTy, NarrowTy, DstRegs,
3901               LeftoverTy, DstLeftoverRegs);
3902 
3903   MI.eraseFromParent();
3904   return Legalized;
3905 }
3906 
3907 LegalizerHelper::LegalizeResult
3908 LegalizerHelper::narrowScalarExt(MachineInstr &MI, unsigned TypeIdx,
3909                                  LLT NarrowTy) {
3910   if (TypeIdx != 0)
3911     return UnableToLegalize;
3912 
3913   Register DstReg = MI.getOperand(0).getReg();
3914   Register SrcReg = MI.getOperand(1).getReg();
3915 
3916   LLT DstTy = MRI.getType(DstReg);
3917   if (DstTy.isVector())
3918     return UnableToLegalize;
3919 
3920   SmallVector<Register, 8> Parts;
3921   LLT GCDTy = extractGCDType(Parts, DstTy, NarrowTy, SrcReg);
3922   LLT LCMTy = buildLCMMergePieces(DstTy, NarrowTy, GCDTy, Parts, MI.getOpcode());
3923   buildWidenedRemergeToDst(DstReg, LCMTy, Parts);
3924 
3925   MI.eraseFromParent();
3926   return Legalized;
3927 }
3928 
3929 LegalizerHelper::LegalizeResult
3930 LegalizerHelper::narrowScalarSelect(MachineInstr &MI, unsigned TypeIdx,
3931                                     LLT NarrowTy) {
3932   if (TypeIdx != 0)
3933     return UnableToLegalize;
3934 
3935   Register CondReg = MI.getOperand(1).getReg();
3936   LLT CondTy = MRI.getType(CondReg);
3937   if (CondTy.isVector()) // TODO: Handle vselect
3938     return UnableToLegalize;
3939 
3940   Register DstReg = MI.getOperand(0).getReg();
3941   LLT DstTy = MRI.getType(DstReg);
3942 
3943   SmallVector<Register, 4> DstRegs, DstLeftoverRegs;
3944   SmallVector<Register, 4> Src1Regs, Src1LeftoverRegs;
3945   SmallVector<Register, 4> Src2Regs, Src2LeftoverRegs;
3946   LLT LeftoverTy;
3947   if (!extractParts(MI.getOperand(2).getReg(), DstTy, NarrowTy, LeftoverTy,
3948                     Src1Regs, Src1LeftoverRegs))
3949     return UnableToLegalize;
3950 
3951   LLT Unused;
3952   if (!extractParts(MI.getOperand(3).getReg(), DstTy, NarrowTy, Unused,
3953                     Src2Regs, Src2LeftoverRegs))
3954     llvm_unreachable("inconsistent extractParts result");
3955 
3956   for (unsigned I = 0, E = Src1Regs.size(); I != E; ++I) {
3957     auto Select = MIRBuilder.buildSelect(NarrowTy,
3958                                          CondReg, Src1Regs[I], Src2Regs[I]);
3959     DstRegs.push_back(Select.getReg(0));
3960   }
3961 
3962   for (unsigned I = 0, E = Src1LeftoverRegs.size(); I != E; ++I) {
3963     auto Select = MIRBuilder.buildSelect(
3964       LeftoverTy, CondReg, Src1LeftoverRegs[I], Src2LeftoverRegs[I]);
3965     DstLeftoverRegs.push_back(Select.getReg(0));
3966   }
3967 
3968   insertParts(DstReg, DstTy, NarrowTy, DstRegs,
3969               LeftoverTy, DstLeftoverRegs);
3970 
3971   MI.eraseFromParent();
3972   return Legalized;
3973 }
3974 
3975 LegalizerHelper::LegalizeResult
3976 LegalizerHelper::narrowScalarCTLZ(MachineInstr &MI, unsigned TypeIdx,
3977                                   LLT NarrowTy) {
3978   if (TypeIdx != 1)
3979     return UnableToLegalize;
3980 
3981   LLT SrcTy = MRI.getType(MI.getOperand(1).getReg());
3982   unsigned NarrowSize = NarrowTy.getSizeInBits();
3983 
3984   if (SrcTy.isScalar() && SrcTy.getSizeInBits() == 2 * NarrowSize) {
3985     MachineIRBuilder &B = MIRBuilder;
3986     auto UnmergeSrc = B.buildUnmerge(NarrowTy, MI.getOperand(1));
3987     // ctlz(Hi:Lo) -> Hi == 0 ? (NarrowSize + ctlz(Lo)) : ctlz(Hi)
3988     auto C_0 = B.buildConstant(NarrowTy, 0);
3989     auto HiIsZero = B.buildICmp(CmpInst::ICMP_EQ, LLT::scalar(1),
3990                                 UnmergeSrc.getReg(1), C_0);
3991     auto LoCTLZ = B.buildCTLZ(NarrowTy, UnmergeSrc.getReg(0));
3992     auto C_NarrowSize = B.buildConstant(NarrowTy, NarrowSize);
3993     auto HiIsZeroCTLZ = B.buildAdd(NarrowTy, LoCTLZ, C_NarrowSize);
3994     auto HiCTLZ = B.buildCTLZ_ZERO_UNDEF(NarrowTy, UnmergeSrc.getReg(1));
3995     auto LoOut = B.buildSelect(NarrowTy, HiIsZero, HiIsZeroCTLZ, HiCTLZ);
3996 
3997     B.buildMerge(MI.getOperand(0), {LoOut, C_0});
3998 
3999     MI.eraseFromParent();
4000     return Legalized;
4001   }
4002 
4003   return UnableToLegalize;
4004 }
4005 
4006 LegalizerHelper::LegalizeResult
4007 LegalizerHelper::narrowScalarCTTZ(MachineInstr &MI, unsigned TypeIdx,
4008                                   LLT NarrowTy) {
4009   if (TypeIdx != 1)
4010     return UnableToLegalize;
4011 
4012   LLT SrcTy = MRI.getType(MI.getOperand(1).getReg());
4013   unsigned NarrowSize = NarrowTy.getSizeInBits();
4014 
4015   if (SrcTy.isScalar() && SrcTy.getSizeInBits() == 2 * NarrowSize) {
4016     MachineIRBuilder &B = MIRBuilder;
4017     auto UnmergeSrc = B.buildUnmerge(NarrowTy, MI.getOperand(1));
4018     // cttz(Hi:Lo) -> Lo == 0 ? (cttz(Hi) + NarrowSize) : cttz(Lo)
4019     auto C_0 = B.buildConstant(NarrowTy, 0);
4020     auto LoIsZero = B.buildICmp(CmpInst::ICMP_EQ, LLT::scalar(1),
4021                                 UnmergeSrc.getReg(0), C_0);
4022     auto HiCTTZ = B.buildCTTZ(NarrowTy, UnmergeSrc.getReg(1));
4023     auto C_NarrowSize = B.buildConstant(NarrowTy, NarrowSize);
4024     auto LoIsZeroCTTZ = B.buildAdd(NarrowTy, HiCTTZ, C_NarrowSize);
4025     auto LoCTTZ = B.buildCTTZ_ZERO_UNDEF(NarrowTy, UnmergeSrc.getReg(0));
4026     auto LoOut = B.buildSelect(NarrowTy, LoIsZero, LoIsZeroCTTZ, LoCTTZ);
4027 
4028     B.buildMerge(MI.getOperand(0), {LoOut, C_0});
4029 
4030     MI.eraseFromParent();
4031     return Legalized;
4032   }
4033 
4034   return UnableToLegalize;
4035 }
4036 
4037 LegalizerHelper::LegalizeResult
4038 LegalizerHelper::narrowScalarCTPOP(MachineInstr &MI, unsigned TypeIdx,
4039                                    LLT NarrowTy) {
4040   if (TypeIdx != 1)
4041     return UnableToLegalize;
4042 
4043   Register DstReg = MI.getOperand(0).getReg();
4044   LLT DstTy = MRI.getType(DstReg);
4045   LLT SrcTy = MRI.getType(MI.getOperand(1).getReg());
4046   unsigned NarrowSize = NarrowTy.getSizeInBits();
4047 
4048   if (SrcTy.isScalar() && SrcTy.getSizeInBits() == 2 * NarrowSize) {
4049     auto UnmergeSrc = MIRBuilder.buildUnmerge(NarrowTy, MI.getOperand(1));
4050 
4051     auto LoCTPOP = MIRBuilder.buildCTPOP(DstTy, UnmergeSrc.getReg(0));
4052     auto HiCTPOP = MIRBuilder.buildCTPOP(DstTy, UnmergeSrc.getReg(1));
4053     MIRBuilder.buildAdd(DstReg, HiCTPOP, LoCTPOP);
4054 
4055     MI.eraseFromParent();
4056     return Legalized;
4057   }
4058 
4059   return UnableToLegalize;
4060 }
4061 
4062 LegalizerHelper::LegalizeResult
4063 LegalizerHelper::lowerBitCount(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
4064   unsigned Opc = MI.getOpcode();
4065   auto &TII = *MI.getMF()->getSubtarget().getInstrInfo();
4066   auto isSupported = [this](const LegalityQuery &Q) {
4067     auto QAction = LI.getAction(Q).Action;
4068     return QAction == Legal || QAction == Libcall || QAction == Custom;
4069   };
4070   switch (Opc) {
4071   default:
4072     return UnableToLegalize;
4073   case TargetOpcode::G_CTLZ_ZERO_UNDEF: {
4074     // This trivially expands to CTLZ.
4075     Observer.changingInstr(MI);
4076     MI.setDesc(TII.get(TargetOpcode::G_CTLZ));
4077     Observer.changedInstr(MI);
4078     return Legalized;
4079   }
4080   case TargetOpcode::G_CTLZ: {
4081     Register DstReg = MI.getOperand(0).getReg();
4082     Register SrcReg = MI.getOperand(1).getReg();
4083     LLT DstTy = MRI.getType(DstReg);
4084     LLT SrcTy = MRI.getType(SrcReg);
4085     unsigned Len = SrcTy.getSizeInBits();
4086 
4087     if (isSupported({TargetOpcode::G_CTLZ_ZERO_UNDEF, {DstTy, SrcTy}})) {
4088       // If CTLZ_ZERO_UNDEF is supported, emit that and a select for zero.
4089       auto CtlzZU = MIRBuilder.buildCTLZ_ZERO_UNDEF(DstTy, SrcReg);
4090       auto ZeroSrc = MIRBuilder.buildConstant(SrcTy, 0);
4091       auto ICmp = MIRBuilder.buildICmp(
4092           CmpInst::ICMP_EQ, SrcTy.changeElementSize(1), SrcReg, ZeroSrc);
4093       auto LenConst = MIRBuilder.buildConstant(DstTy, Len);
4094       MIRBuilder.buildSelect(DstReg, ICmp, LenConst, CtlzZU);
4095       MI.eraseFromParent();
4096       return Legalized;
4097     }
4098     // for now, we do this:
4099     // NewLen = NextPowerOf2(Len);
4100     // x = x | (x >> 1);
4101     // x = x | (x >> 2);
4102     // ...
4103     // x = x | (x >>16);
4104     // x = x | (x >>32); // for 64-bit input
4105     // Upto NewLen/2
4106     // return Len - popcount(x);
4107     //
4108     // Ref: "Hacker's Delight" by Henry Warren
4109     Register Op = SrcReg;
4110     unsigned NewLen = PowerOf2Ceil(Len);
4111     for (unsigned i = 0; (1U << i) <= (NewLen / 2); ++i) {
4112       auto MIBShiftAmt = MIRBuilder.buildConstant(SrcTy, 1ULL << i);
4113       auto MIBOp = MIRBuilder.buildOr(
4114           SrcTy, Op, MIRBuilder.buildLShr(SrcTy, Op, MIBShiftAmt));
4115       Op = MIBOp.getReg(0);
4116     }
4117     auto MIBPop = MIRBuilder.buildCTPOP(DstTy, Op);
4118     MIRBuilder.buildSub(MI.getOperand(0), MIRBuilder.buildConstant(DstTy, Len),
4119                         MIBPop);
4120     MI.eraseFromParent();
4121     return Legalized;
4122   }
4123   case TargetOpcode::G_CTTZ_ZERO_UNDEF: {
4124     // This trivially expands to CTTZ.
4125     Observer.changingInstr(MI);
4126     MI.setDesc(TII.get(TargetOpcode::G_CTTZ));
4127     Observer.changedInstr(MI);
4128     return Legalized;
4129   }
4130   case TargetOpcode::G_CTTZ: {
4131     Register DstReg = MI.getOperand(0).getReg();
4132     Register SrcReg = MI.getOperand(1).getReg();
4133     LLT DstTy = MRI.getType(DstReg);
4134     LLT SrcTy = MRI.getType(SrcReg);
4135 
4136     unsigned Len = SrcTy.getSizeInBits();
4137     if (isSupported({TargetOpcode::G_CTTZ_ZERO_UNDEF, {DstTy, SrcTy}})) {
4138       // If CTTZ_ZERO_UNDEF is legal or custom, emit that and a select with
4139       // zero.
4140       auto CttzZU = MIRBuilder.buildCTTZ_ZERO_UNDEF(DstTy, SrcReg);
4141       auto Zero = MIRBuilder.buildConstant(SrcTy, 0);
4142       auto ICmp = MIRBuilder.buildICmp(
4143           CmpInst::ICMP_EQ, DstTy.changeElementSize(1), SrcReg, Zero);
4144       auto LenConst = MIRBuilder.buildConstant(DstTy, Len);
4145       MIRBuilder.buildSelect(DstReg, ICmp, LenConst, CttzZU);
4146       MI.eraseFromParent();
4147       return Legalized;
4148     }
4149     // for now, we use: { return popcount(~x & (x - 1)); }
4150     // unless the target has ctlz but not ctpop, in which case we use:
4151     // { return 32 - nlz(~x & (x-1)); }
4152     // Ref: "Hacker's Delight" by Henry Warren
4153     auto MIBCstNeg1 = MIRBuilder.buildConstant(Ty, -1);
4154     auto MIBNot = MIRBuilder.buildXor(Ty, SrcReg, MIBCstNeg1);
4155     auto MIBTmp = MIRBuilder.buildAnd(
4156         Ty, MIBNot, MIRBuilder.buildAdd(Ty, SrcReg, MIBCstNeg1));
4157     if (!isSupported({TargetOpcode::G_CTPOP, {Ty, Ty}}) &&
4158         isSupported({TargetOpcode::G_CTLZ, {Ty, Ty}})) {
4159       auto MIBCstLen = MIRBuilder.buildConstant(Ty, Len);
4160       MIRBuilder.buildSub(MI.getOperand(0), MIBCstLen,
4161                           MIRBuilder.buildCTLZ(Ty, MIBTmp));
4162       MI.eraseFromParent();
4163       return Legalized;
4164     }
4165     MI.setDesc(TII.get(TargetOpcode::G_CTPOP));
4166     MI.getOperand(1).setReg(MIBTmp.getReg(0));
4167     return Legalized;
4168   }
4169   case TargetOpcode::G_CTPOP: {
4170     unsigned Size = Ty.getSizeInBits();
4171     MachineIRBuilder &B = MIRBuilder;
4172 
4173     // Count set bits in blocks of 2 bits. Default approach would be
4174     // B2Count = { val & 0x55555555 } + { (val >> 1) & 0x55555555 }
4175     // We use following formula instead:
4176     // B2Count = val - { (val >> 1) & 0x55555555 }
4177     // since it gives same result in blocks of 2 with one instruction less.
4178     auto C_1 = B.buildConstant(Ty, 1);
4179     auto B2Set1LoTo1Hi = B.buildLShr(Ty, MI.getOperand(1).getReg(), C_1);
4180     APInt B2Mask1HiTo0 = APInt::getSplat(Size, APInt(8, 0x55));
4181     auto C_B2Mask1HiTo0 = B.buildConstant(Ty, B2Mask1HiTo0);
4182     auto B2Count1Hi = B.buildAnd(Ty, B2Set1LoTo1Hi, C_B2Mask1HiTo0);
4183     auto B2Count = B.buildSub(Ty, MI.getOperand(1).getReg(), B2Count1Hi);
4184 
4185     // In order to get count in blocks of 4 add values from adjacent block of 2.
4186     // B4Count = { B2Count & 0x33333333 } + { (B2Count >> 2) & 0x33333333 }
4187     auto C_2 = B.buildConstant(Ty, 2);
4188     auto B4Set2LoTo2Hi = B.buildLShr(Ty, B2Count, C_2);
4189     APInt B4Mask2HiTo0 = APInt::getSplat(Size, APInt(8, 0x33));
4190     auto C_B4Mask2HiTo0 = B.buildConstant(Ty, B4Mask2HiTo0);
4191     auto B4HiB2Count = B.buildAnd(Ty, B4Set2LoTo2Hi, C_B4Mask2HiTo0);
4192     auto B4LoB2Count = B.buildAnd(Ty, B2Count, C_B4Mask2HiTo0);
4193     auto B4Count = B.buildAdd(Ty, B4HiB2Count, B4LoB2Count);
4194 
4195     // For count in blocks of 8 bits we don't have to mask high 4 bits before
4196     // addition since count value sits in range {0,...,8} and 4 bits are enough
4197     // to hold such binary values. After addition high 4 bits still hold count
4198     // of set bits in high 4 bit block, set them to zero and get 8 bit result.
4199     // B8Count = { B4Count + (B4Count >> 4) } & 0x0F0F0F0F
4200     auto C_4 = B.buildConstant(Ty, 4);
4201     auto B8HiB4Count = B.buildLShr(Ty, B4Count, C_4);
4202     auto B8CountDirty4Hi = B.buildAdd(Ty, B8HiB4Count, B4Count);
4203     APInt B8Mask4HiTo0 = APInt::getSplat(Size, APInt(8, 0x0F));
4204     auto C_B8Mask4HiTo0 = B.buildConstant(Ty, B8Mask4HiTo0);
4205     auto B8Count = B.buildAnd(Ty, B8CountDirty4Hi, C_B8Mask4HiTo0);
4206 
4207     assert(Size<=128 && "Scalar size is too large for CTPOP lower algorithm");
4208     // 8 bits can hold CTPOP result of 128 bit int or smaller. Mul with this
4209     // bitmask will set 8 msb in ResTmp to sum of all B8Counts in 8 bit blocks.
4210     auto MulMask = B.buildConstant(Ty, APInt::getSplat(Size, APInt(8, 0x01)));
4211     auto ResTmp = B.buildMul(Ty, B8Count, MulMask);
4212 
4213     // Shift count result from 8 high bits to low bits.
4214     auto C_SizeM8 = B.buildConstant(Ty, Size - 8);
4215     B.buildLShr(MI.getOperand(0).getReg(), ResTmp, C_SizeM8);
4216 
4217     MI.eraseFromParent();
4218     return Legalized;
4219   }
4220   }
4221 }
4222 
4223 // Expand s32 = G_UITOFP s64 using bit operations to an IEEE float
4224 // representation.
4225 LegalizerHelper::LegalizeResult
4226 LegalizerHelper::lowerU64ToF32BitOps(MachineInstr &MI) {
4227   Register Dst = MI.getOperand(0).getReg();
4228   Register Src = MI.getOperand(1).getReg();
4229   const LLT S64 = LLT::scalar(64);
4230   const LLT S32 = LLT::scalar(32);
4231   const LLT S1 = LLT::scalar(1);
4232 
4233   assert(MRI.getType(Src) == S64 && MRI.getType(Dst) == S32);
4234 
4235   // unsigned cul2f(ulong u) {
4236   //   uint lz = clz(u);
4237   //   uint e = (u != 0) ? 127U + 63U - lz : 0;
4238   //   u = (u << lz) & 0x7fffffffffffffffUL;
4239   //   ulong t = u & 0xffffffffffUL;
4240   //   uint v = (e << 23) | (uint)(u >> 40);
4241   //   uint r = t > 0x8000000000UL ? 1U : (t == 0x8000000000UL ? v & 1U : 0U);
4242   //   return as_float(v + r);
4243   // }
4244 
4245   auto Zero32 = MIRBuilder.buildConstant(S32, 0);
4246   auto Zero64 = MIRBuilder.buildConstant(S64, 0);
4247 
4248   auto LZ = MIRBuilder.buildCTLZ_ZERO_UNDEF(S32, Src);
4249 
4250   auto K = MIRBuilder.buildConstant(S32, 127U + 63U);
4251   auto Sub = MIRBuilder.buildSub(S32, K, LZ);
4252 
4253   auto NotZero = MIRBuilder.buildICmp(CmpInst::ICMP_NE, S1, Src, Zero64);
4254   auto E = MIRBuilder.buildSelect(S32, NotZero, Sub, Zero32);
4255 
4256   auto Mask0 = MIRBuilder.buildConstant(S64, (-1ULL) >> 1);
4257   auto ShlLZ = MIRBuilder.buildShl(S64, Src, LZ);
4258 
4259   auto U = MIRBuilder.buildAnd(S64, ShlLZ, Mask0);
4260 
4261   auto Mask1 = MIRBuilder.buildConstant(S64, 0xffffffffffULL);
4262   auto T = MIRBuilder.buildAnd(S64, U, Mask1);
4263 
4264   auto UShl = MIRBuilder.buildLShr(S64, U, MIRBuilder.buildConstant(S64, 40));
4265   auto ShlE = MIRBuilder.buildShl(S32, E, MIRBuilder.buildConstant(S32, 23));
4266   auto V = MIRBuilder.buildOr(S32, ShlE, MIRBuilder.buildTrunc(S32, UShl));
4267 
4268   auto C = MIRBuilder.buildConstant(S64, 0x8000000000ULL);
4269   auto RCmp = MIRBuilder.buildICmp(CmpInst::ICMP_UGT, S1, T, C);
4270   auto TCmp = MIRBuilder.buildICmp(CmpInst::ICMP_EQ, S1, T, C);
4271   auto One = MIRBuilder.buildConstant(S32, 1);
4272 
4273   auto VTrunc1 = MIRBuilder.buildAnd(S32, V, One);
4274   auto Select0 = MIRBuilder.buildSelect(S32, TCmp, VTrunc1, Zero32);
4275   auto R = MIRBuilder.buildSelect(S32, RCmp, One, Select0);
4276   MIRBuilder.buildAdd(Dst, V, R);
4277 
4278   return Legalized;
4279 }
4280 
4281 LegalizerHelper::LegalizeResult
4282 LegalizerHelper::lowerUITOFP(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
4283   Register Dst = MI.getOperand(0).getReg();
4284   Register Src = MI.getOperand(1).getReg();
4285   LLT DstTy = MRI.getType(Dst);
4286   LLT SrcTy = MRI.getType(Src);
4287 
4288   if (SrcTy == LLT::scalar(1)) {
4289     auto True = MIRBuilder.buildFConstant(DstTy, 1.0);
4290     auto False = MIRBuilder.buildFConstant(DstTy, 0.0);
4291     MIRBuilder.buildSelect(Dst, Src, True, False);
4292     MI.eraseFromParent();
4293     return Legalized;
4294   }
4295 
4296   if (SrcTy != LLT::scalar(64))
4297     return UnableToLegalize;
4298 
4299   if (DstTy == LLT::scalar(32)) {
4300     // TODO: SelectionDAG has several alternative expansions to port which may
4301     // be more reasonble depending on the available instructions. If a target
4302     // has sitofp, does not have CTLZ, or can efficiently use f64 as an
4303     // intermediate type, this is probably worse.
4304     return lowerU64ToF32BitOps(MI);
4305   }
4306 
4307   return UnableToLegalize;
4308 }
4309 
4310 LegalizerHelper::LegalizeResult
4311 LegalizerHelper::lowerSITOFP(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
4312   Register Dst = MI.getOperand(0).getReg();
4313   Register Src = MI.getOperand(1).getReg();
4314   LLT DstTy = MRI.getType(Dst);
4315   LLT SrcTy = MRI.getType(Src);
4316 
4317   const LLT S64 = LLT::scalar(64);
4318   const LLT S32 = LLT::scalar(32);
4319   const LLT S1 = LLT::scalar(1);
4320 
4321   if (SrcTy == S1) {
4322     auto True = MIRBuilder.buildFConstant(DstTy, -1.0);
4323     auto False = MIRBuilder.buildFConstant(DstTy, 0.0);
4324     MIRBuilder.buildSelect(Dst, Src, True, False);
4325     MI.eraseFromParent();
4326     return Legalized;
4327   }
4328 
4329   if (SrcTy != S64)
4330     return UnableToLegalize;
4331 
4332   if (DstTy == S32) {
4333     // signed cl2f(long l) {
4334     //   long s = l >> 63;
4335     //   float r = cul2f((l + s) ^ s);
4336     //   return s ? -r : r;
4337     // }
4338     Register L = Src;
4339     auto SignBit = MIRBuilder.buildConstant(S64, 63);
4340     auto S = MIRBuilder.buildAShr(S64, L, SignBit);
4341 
4342     auto LPlusS = MIRBuilder.buildAdd(S64, L, S);
4343     auto Xor = MIRBuilder.buildXor(S64, LPlusS, S);
4344     auto R = MIRBuilder.buildUITOFP(S32, Xor);
4345 
4346     auto RNeg = MIRBuilder.buildFNeg(S32, R);
4347     auto SignNotZero = MIRBuilder.buildICmp(CmpInst::ICMP_NE, S1, S,
4348                                             MIRBuilder.buildConstant(S64, 0));
4349     MIRBuilder.buildSelect(Dst, SignNotZero, RNeg, R);
4350     return Legalized;
4351   }
4352 
4353   return UnableToLegalize;
4354 }
4355 
4356 LegalizerHelper::LegalizeResult
4357 LegalizerHelper::lowerFPTOUI(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
4358   Register Dst = MI.getOperand(0).getReg();
4359   Register Src = MI.getOperand(1).getReg();
4360   LLT DstTy = MRI.getType(Dst);
4361   LLT SrcTy = MRI.getType(Src);
4362   const LLT S64 = LLT::scalar(64);
4363   const LLT S32 = LLT::scalar(32);
4364 
4365   if (SrcTy != S64 && SrcTy != S32)
4366     return UnableToLegalize;
4367   if (DstTy != S32 && DstTy != S64)
4368     return UnableToLegalize;
4369 
4370   // FPTOSI gives same result as FPTOUI for positive signed integers.
4371   // FPTOUI needs to deal with fp values that convert to unsigned integers
4372   // greater or equal to 2^31 for float or 2^63 for double. For brevity 2^Exp.
4373 
4374   APInt TwoPExpInt = APInt::getSignMask(DstTy.getSizeInBits());
4375   APFloat TwoPExpFP(SrcTy.getSizeInBits() == 32 ? APFloat::IEEEsingle()
4376                                                 : APFloat::IEEEdouble(),
4377                     APInt::getNullValue(SrcTy.getSizeInBits()));
4378   TwoPExpFP.convertFromAPInt(TwoPExpInt, false, APFloat::rmNearestTiesToEven);
4379 
4380   MachineInstrBuilder FPTOSI = MIRBuilder.buildFPTOSI(DstTy, Src);
4381 
4382   MachineInstrBuilder Threshold = MIRBuilder.buildFConstant(SrcTy, TwoPExpFP);
4383   // For fp Value greater or equal to Threshold(2^Exp), we use FPTOSI on
4384   // (Value - 2^Exp) and add 2^Exp by setting highest bit in result to 1.
4385   MachineInstrBuilder FSub = MIRBuilder.buildFSub(SrcTy, Src, Threshold);
4386   MachineInstrBuilder ResLowBits = MIRBuilder.buildFPTOSI(DstTy, FSub);
4387   MachineInstrBuilder ResHighBit = MIRBuilder.buildConstant(DstTy, TwoPExpInt);
4388   MachineInstrBuilder Res = MIRBuilder.buildXor(DstTy, ResLowBits, ResHighBit);
4389 
4390   const LLT S1 = LLT::scalar(1);
4391 
4392   MachineInstrBuilder FCMP =
4393       MIRBuilder.buildFCmp(CmpInst::FCMP_ULT, S1, Src, Threshold);
4394   MIRBuilder.buildSelect(Dst, FCMP, FPTOSI, Res);
4395 
4396   MI.eraseFromParent();
4397   return Legalized;
4398 }
4399 
4400 LegalizerHelper::LegalizeResult LegalizerHelper::lowerFPTOSI(MachineInstr &MI) {
4401   Register Dst = MI.getOperand(0).getReg();
4402   Register Src = MI.getOperand(1).getReg();
4403   LLT DstTy = MRI.getType(Dst);
4404   LLT SrcTy = MRI.getType(Src);
4405   const LLT S64 = LLT::scalar(64);
4406   const LLT S32 = LLT::scalar(32);
4407 
4408   // FIXME: Only f32 to i64 conversions are supported.
4409   if (SrcTy.getScalarType() != S32 || DstTy.getScalarType() != S64)
4410     return UnableToLegalize;
4411 
4412   // Expand f32 -> i64 conversion
4413   // This algorithm comes from compiler-rt's implementation of fixsfdi:
4414   // https://github.com/llvm/llvm-project/blob/master/compiler-rt/lib/builtins/fixsfdi.c
4415 
4416   unsigned SrcEltBits = SrcTy.getScalarSizeInBits();
4417 
4418   auto ExponentMask = MIRBuilder.buildConstant(SrcTy, 0x7F800000);
4419   auto ExponentLoBit = MIRBuilder.buildConstant(SrcTy, 23);
4420 
4421   auto AndExpMask = MIRBuilder.buildAnd(SrcTy, Src, ExponentMask);
4422   auto ExponentBits = MIRBuilder.buildLShr(SrcTy, AndExpMask, ExponentLoBit);
4423 
4424   auto SignMask = MIRBuilder.buildConstant(SrcTy,
4425                                            APInt::getSignMask(SrcEltBits));
4426   auto AndSignMask = MIRBuilder.buildAnd(SrcTy, Src, SignMask);
4427   auto SignLowBit = MIRBuilder.buildConstant(SrcTy, SrcEltBits - 1);
4428   auto Sign = MIRBuilder.buildAShr(SrcTy, AndSignMask, SignLowBit);
4429   Sign = MIRBuilder.buildSExt(DstTy, Sign);
4430 
4431   auto MantissaMask = MIRBuilder.buildConstant(SrcTy, 0x007FFFFF);
4432   auto AndMantissaMask = MIRBuilder.buildAnd(SrcTy, Src, MantissaMask);
4433   auto K = MIRBuilder.buildConstant(SrcTy, 0x00800000);
4434 
4435   auto R = MIRBuilder.buildOr(SrcTy, AndMantissaMask, K);
4436   R = MIRBuilder.buildZExt(DstTy, R);
4437 
4438   auto Bias = MIRBuilder.buildConstant(SrcTy, 127);
4439   auto Exponent = MIRBuilder.buildSub(SrcTy, ExponentBits, Bias);
4440   auto SubExponent = MIRBuilder.buildSub(SrcTy, Exponent, ExponentLoBit);
4441   auto ExponentSub = MIRBuilder.buildSub(SrcTy, ExponentLoBit, Exponent);
4442 
4443   auto Shl = MIRBuilder.buildShl(DstTy, R, SubExponent);
4444   auto Srl = MIRBuilder.buildLShr(DstTy, R, ExponentSub);
4445 
4446   const LLT S1 = LLT::scalar(1);
4447   auto CmpGt = MIRBuilder.buildICmp(CmpInst::ICMP_SGT,
4448                                     S1, Exponent, ExponentLoBit);
4449 
4450   R = MIRBuilder.buildSelect(DstTy, CmpGt, Shl, Srl);
4451 
4452   auto XorSign = MIRBuilder.buildXor(DstTy, R, Sign);
4453   auto Ret = MIRBuilder.buildSub(DstTy, XorSign, Sign);
4454 
4455   auto ZeroSrcTy = MIRBuilder.buildConstant(SrcTy, 0);
4456 
4457   auto ExponentLt0 = MIRBuilder.buildICmp(CmpInst::ICMP_SLT,
4458                                           S1, Exponent, ZeroSrcTy);
4459 
4460   auto ZeroDstTy = MIRBuilder.buildConstant(DstTy, 0);
4461   MIRBuilder.buildSelect(Dst, ExponentLt0, ZeroDstTy, Ret);
4462 
4463   MI.eraseFromParent();
4464   return Legalized;
4465 }
4466 
4467 static CmpInst::Predicate minMaxToCompare(unsigned Opc) {
4468   switch (Opc) {
4469   case TargetOpcode::G_SMIN:
4470     return CmpInst::ICMP_SLT;
4471   case TargetOpcode::G_SMAX:
4472     return CmpInst::ICMP_SGT;
4473   case TargetOpcode::G_UMIN:
4474     return CmpInst::ICMP_ULT;
4475   case TargetOpcode::G_UMAX:
4476     return CmpInst::ICMP_UGT;
4477   default:
4478     llvm_unreachable("not in integer min/max");
4479   }
4480 }
4481 
4482 LegalizerHelper::LegalizeResult
4483 LegalizerHelper::lowerMinMax(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
4484   Register Dst = MI.getOperand(0).getReg();
4485   Register Src0 = MI.getOperand(1).getReg();
4486   Register Src1 = MI.getOperand(2).getReg();
4487 
4488   const CmpInst::Predicate Pred = minMaxToCompare(MI.getOpcode());
4489   LLT CmpType = MRI.getType(Dst).changeElementSize(1);
4490 
4491   auto Cmp = MIRBuilder.buildICmp(Pred, CmpType, Src0, Src1);
4492   MIRBuilder.buildSelect(Dst, Cmp, Src0, Src1);
4493 
4494   MI.eraseFromParent();
4495   return Legalized;
4496 }
4497 
4498 LegalizerHelper::LegalizeResult
4499 LegalizerHelper::lowerFCopySign(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
4500   Register Dst = MI.getOperand(0).getReg();
4501   Register Src0 = MI.getOperand(1).getReg();
4502   Register Src1 = MI.getOperand(2).getReg();
4503 
4504   const LLT Src0Ty = MRI.getType(Src0);
4505   const LLT Src1Ty = MRI.getType(Src1);
4506 
4507   const int Src0Size = Src0Ty.getScalarSizeInBits();
4508   const int Src1Size = Src1Ty.getScalarSizeInBits();
4509 
4510   auto SignBitMask = MIRBuilder.buildConstant(
4511     Src0Ty, APInt::getSignMask(Src0Size));
4512 
4513   auto NotSignBitMask = MIRBuilder.buildConstant(
4514     Src0Ty, APInt::getLowBitsSet(Src0Size, Src0Size - 1));
4515 
4516   auto And0 = MIRBuilder.buildAnd(Src0Ty, Src0, NotSignBitMask);
4517   MachineInstr *Or;
4518 
4519   if (Src0Ty == Src1Ty) {
4520     auto And1 = MIRBuilder.buildAnd(Src1Ty, Src0, SignBitMask);
4521     Or = MIRBuilder.buildOr(Dst, And0, And1);
4522   } else if (Src0Size > Src1Size) {
4523     auto ShiftAmt = MIRBuilder.buildConstant(Src0Ty, Src0Size - Src1Size);
4524     auto Zext = MIRBuilder.buildZExt(Src0Ty, Src1);
4525     auto Shift = MIRBuilder.buildShl(Src0Ty, Zext, ShiftAmt);
4526     auto And1 = MIRBuilder.buildAnd(Src0Ty, Shift, SignBitMask);
4527     Or = MIRBuilder.buildOr(Dst, And0, And1);
4528   } else {
4529     auto ShiftAmt = MIRBuilder.buildConstant(Src1Ty, Src1Size - Src0Size);
4530     auto Shift = MIRBuilder.buildLShr(Src1Ty, Src1, ShiftAmt);
4531     auto Trunc = MIRBuilder.buildTrunc(Src0Ty, Shift);
4532     auto And1 = MIRBuilder.buildAnd(Src0Ty, Trunc, SignBitMask);
4533     Or = MIRBuilder.buildOr(Dst, And0, And1);
4534   }
4535 
4536   // Be careful about setting nsz/nnan/ninf on every instruction, since the
4537   // constants are a nan and -0.0, but the final result should preserve
4538   // everything.
4539   if (unsigned Flags = MI.getFlags())
4540     Or->setFlags(Flags);
4541 
4542   MI.eraseFromParent();
4543   return Legalized;
4544 }
4545 
4546 LegalizerHelper::LegalizeResult
4547 LegalizerHelper::lowerFMinNumMaxNum(MachineInstr &MI) {
4548   unsigned NewOp = MI.getOpcode() == TargetOpcode::G_FMINNUM ?
4549     TargetOpcode::G_FMINNUM_IEEE : TargetOpcode::G_FMAXNUM_IEEE;
4550 
4551   Register Dst = MI.getOperand(0).getReg();
4552   Register Src0 = MI.getOperand(1).getReg();
4553   Register Src1 = MI.getOperand(2).getReg();
4554   LLT Ty = MRI.getType(Dst);
4555 
4556   if (!MI.getFlag(MachineInstr::FmNoNans)) {
4557     // Insert canonicalizes if it's possible we need to quiet to get correct
4558     // sNaN behavior.
4559 
4560     // Note this must be done here, and not as an optimization combine in the
4561     // absence of a dedicate quiet-snan instruction as we're using an
4562     // omni-purpose G_FCANONICALIZE.
4563     if (!isKnownNeverSNaN(Src0, MRI))
4564       Src0 = MIRBuilder.buildFCanonicalize(Ty, Src0, MI.getFlags()).getReg(0);
4565 
4566     if (!isKnownNeverSNaN(Src1, MRI))
4567       Src1 = MIRBuilder.buildFCanonicalize(Ty, Src1, MI.getFlags()).getReg(0);
4568   }
4569 
4570   // If there are no nans, it's safe to simply replace this with the non-IEEE
4571   // version.
4572   MIRBuilder.buildInstr(NewOp, {Dst}, {Src0, Src1}, MI.getFlags());
4573   MI.eraseFromParent();
4574   return Legalized;
4575 }
4576 
4577 LegalizerHelper::LegalizeResult LegalizerHelper::lowerFMad(MachineInstr &MI) {
4578   // Expand G_FMAD a, b, c -> G_FADD (G_FMUL a, b), c
4579   Register DstReg = MI.getOperand(0).getReg();
4580   LLT Ty = MRI.getType(DstReg);
4581   unsigned Flags = MI.getFlags();
4582 
4583   auto Mul = MIRBuilder.buildFMul(Ty, MI.getOperand(1), MI.getOperand(2),
4584                                   Flags);
4585   MIRBuilder.buildFAdd(DstReg, Mul, MI.getOperand(3), Flags);
4586   MI.eraseFromParent();
4587   return Legalized;
4588 }
4589 
4590 LegalizerHelper::LegalizeResult
4591 LegalizerHelper::lowerIntrinsicRound(MachineInstr &MI) {
4592   Register DstReg = MI.getOperand(0).getReg();
4593   Register SrcReg = MI.getOperand(1).getReg();
4594   unsigned Flags = MI.getFlags();
4595   LLT Ty = MRI.getType(DstReg);
4596   const LLT CondTy = Ty.changeElementSize(1);
4597 
4598   // result = trunc(src);
4599   // if (src < 0.0 && src != result)
4600   //   result += -1.0.
4601 
4602   auto Zero = MIRBuilder.buildFConstant(Ty, 0.0);
4603   auto Trunc = MIRBuilder.buildIntrinsicTrunc(Ty, SrcReg, Flags);
4604 
4605   auto Lt0 = MIRBuilder.buildFCmp(CmpInst::FCMP_OLT, CondTy,
4606                                   SrcReg, Zero, Flags);
4607   auto NeTrunc = MIRBuilder.buildFCmp(CmpInst::FCMP_ONE, CondTy,
4608                                       SrcReg, Trunc, Flags);
4609   auto And = MIRBuilder.buildAnd(CondTy, Lt0, NeTrunc);
4610   auto AddVal = MIRBuilder.buildSITOFP(Ty, And);
4611 
4612   MIRBuilder.buildFAdd(DstReg, Trunc, AddVal);
4613   MI.eraseFromParent();
4614   return Legalized;
4615 }
4616 
4617 LegalizerHelper::LegalizeResult
4618 LegalizerHelper::lowerUnmergeValues(MachineInstr &MI) {
4619   const unsigned NumDst = MI.getNumOperands() - 1;
4620   const Register SrcReg = MI.getOperand(NumDst).getReg();
4621   LLT SrcTy = MRI.getType(SrcReg);
4622 
4623   Register Dst0Reg = MI.getOperand(0).getReg();
4624   LLT DstTy = MRI.getType(Dst0Reg);
4625 
4626 
4627   // Expand scalarizing unmerge as bitcast to integer and shift.
4628   if (!DstTy.isVector() && SrcTy.isVector() &&
4629       SrcTy.getElementType() == DstTy) {
4630     LLT IntTy = LLT::scalar(SrcTy.getSizeInBits());
4631     Register Cast = MIRBuilder.buildBitcast(IntTy, SrcReg).getReg(0);
4632 
4633     MIRBuilder.buildTrunc(Dst0Reg, Cast);
4634 
4635     const unsigned DstSize = DstTy.getSizeInBits();
4636     unsigned Offset = DstSize;
4637     for (unsigned I = 1; I != NumDst; ++I, Offset += DstSize) {
4638       auto ShiftAmt = MIRBuilder.buildConstant(IntTy, Offset);
4639       auto Shift = MIRBuilder.buildLShr(IntTy, Cast, ShiftAmt);
4640       MIRBuilder.buildTrunc(MI.getOperand(I), Shift);
4641     }
4642 
4643     MI.eraseFromParent();
4644     return Legalized;
4645   }
4646 
4647   return UnableToLegalize;
4648 }
4649 
4650 LegalizerHelper::LegalizeResult
4651 LegalizerHelper::lowerShuffleVector(MachineInstr &MI) {
4652   Register DstReg = MI.getOperand(0).getReg();
4653   Register Src0Reg = MI.getOperand(1).getReg();
4654   Register Src1Reg = MI.getOperand(2).getReg();
4655   LLT Src0Ty = MRI.getType(Src0Reg);
4656   LLT DstTy = MRI.getType(DstReg);
4657   LLT IdxTy = LLT::scalar(32);
4658 
4659   ArrayRef<int> Mask = MI.getOperand(3).getShuffleMask();
4660 
4661   if (DstTy.isScalar()) {
4662     if (Src0Ty.isVector())
4663       return UnableToLegalize;
4664 
4665     // This is just a SELECT.
4666     assert(Mask.size() == 1 && "Expected a single mask element");
4667     Register Val;
4668     if (Mask[0] < 0 || Mask[0] > 1)
4669       Val = MIRBuilder.buildUndef(DstTy).getReg(0);
4670     else
4671       Val = Mask[0] == 0 ? Src0Reg : Src1Reg;
4672     MIRBuilder.buildCopy(DstReg, Val);
4673     MI.eraseFromParent();
4674     return Legalized;
4675   }
4676 
4677   Register Undef;
4678   SmallVector<Register, 32> BuildVec;
4679   LLT EltTy = DstTy.getElementType();
4680 
4681   for (int Idx : Mask) {
4682     if (Idx < 0) {
4683       if (!Undef.isValid())
4684         Undef = MIRBuilder.buildUndef(EltTy).getReg(0);
4685       BuildVec.push_back(Undef);
4686       continue;
4687     }
4688 
4689     if (Src0Ty.isScalar()) {
4690       BuildVec.push_back(Idx == 0 ? Src0Reg : Src1Reg);
4691     } else {
4692       int NumElts = Src0Ty.getNumElements();
4693       Register SrcVec = Idx < NumElts ? Src0Reg : Src1Reg;
4694       int ExtractIdx = Idx < NumElts ? Idx : Idx - NumElts;
4695       auto IdxK = MIRBuilder.buildConstant(IdxTy, ExtractIdx);
4696       auto Extract = MIRBuilder.buildExtractVectorElement(EltTy, SrcVec, IdxK);
4697       BuildVec.push_back(Extract.getReg(0));
4698     }
4699   }
4700 
4701   MIRBuilder.buildBuildVector(DstReg, BuildVec);
4702   MI.eraseFromParent();
4703   return Legalized;
4704 }
4705 
4706 LegalizerHelper::LegalizeResult
4707 LegalizerHelper::lowerDynStackAlloc(MachineInstr &MI) {
4708   Register Dst = MI.getOperand(0).getReg();
4709   Register AllocSize = MI.getOperand(1).getReg();
4710   unsigned Align = MI.getOperand(2).getImm();
4711 
4712   const auto &MF = *MI.getMF();
4713   const auto &TLI = *MF.getSubtarget().getTargetLowering();
4714 
4715   LLT PtrTy = MRI.getType(Dst);
4716   LLT IntPtrTy = LLT::scalar(PtrTy.getSizeInBits());
4717 
4718   Register SPReg = TLI.getStackPointerRegisterToSaveRestore();
4719   auto SPTmp = MIRBuilder.buildCopy(PtrTy, SPReg);
4720   SPTmp = MIRBuilder.buildCast(IntPtrTy, SPTmp);
4721 
4722   // Subtract the final alloc from the SP. We use G_PTRTOINT here so we don't
4723   // have to generate an extra instruction to negate the alloc and then use
4724   // G_PTR_ADD to add the negative offset.
4725   auto Alloc = MIRBuilder.buildSub(IntPtrTy, SPTmp, AllocSize);
4726   if (Align) {
4727     APInt AlignMask(IntPtrTy.getSizeInBits(), Align, true);
4728     AlignMask.negate();
4729     auto AlignCst = MIRBuilder.buildConstant(IntPtrTy, AlignMask);
4730     Alloc = MIRBuilder.buildAnd(IntPtrTy, Alloc, AlignCst);
4731   }
4732 
4733   SPTmp = MIRBuilder.buildCast(PtrTy, Alloc);
4734   MIRBuilder.buildCopy(SPReg, SPTmp);
4735   MIRBuilder.buildCopy(Dst, SPTmp);
4736 
4737   MI.eraseFromParent();
4738   return Legalized;
4739 }
4740 
4741 LegalizerHelper::LegalizeResult
4742 LegalizerHelper::lowerExtract(MachineInstr &MI) {
4743   Register Dst = MI.getOperand(0).getReg();
4744   Register Src = MI.getOperand(1).getReg();
4745   unsigned Offset = MI.getOperand(2).getImm();
4746 
4747   LLT DstTy = MRI.getType(Dst);
4748   LLT SrcTy = MRI.getType(Src);
4749 
4750   if (DstTy.isScalar() &&
4751       (SrcTy.isScalar() ||
4752        (SrcTy.isVector() && DstTy == SrcTy.getElementType()))) {
4753     LLT SrcIntTy = SrcTy;
4754     if (!SrcTy.isScalar()) {
4755       SrcIntTy = LLT::scalar(SrcTy.getSizeInBits());
4756       Src = MIRBuilder.buildBitcast(SrcIntTy, Src).getReg(0);
4757     }
4758 
4759     if (Offset == 0)
4760       MIRBuilder.buildTrunc(Dst, Src);
4761     else {
4762       auto ShiftAmt = MIRBuilder.buildConstant(SrcIntTy, Offset);
4763       auto Shr = MIRBuilder.buildLShr(SrcIntTy, Src, ShiftAmt);
4764       MIRBuilder.buildTrunc(Dst, Shr);
4765     }
4766 
4767     MI.eraseFromParent();
4768     return Legalized;
4769   }
4770 
4771   return UnableToLegalize;
4772 }
4773 
4774 LegalizerHelper::LegalizeResult LegalizerHelper::lowerInsert(MachineInstr &MI) {
4775   Register Dst = MI.getOperand(0).getReg();
4776   Register Src = MI.getOperand(1).getReg();
4777   Register InsertSrc = MI.getOperand(2).getReg();
4778   uint64_t Offset = MI.getOperand(3).getImm();
4779 
4780   LLT DstTy = MRI.getType(Src);
4781   LLT InsertTy = MRI.getType(InsertSrc);
4782 
4783   if (InsertTy.isScalar() &&
4784       (DstTy.isScalar() ||
4785        (DstTy.isVector() && DstTy.getElementType() == InsertTy))) {
4786     LLT IntDstTy = DstTy;
4787     if (!DstTy.isScalar()) {
4788       IntDstTy = LLT::scalar(DstTy.getSizeInBits());
4789       Src = MIRBuilder.buildBitcast(IntDstTy, Src).getReg(0);
4790     }
4791 
4792     Register ExtInsSrc = MIRBuilder.buildZExt(IntDstTy, InsertSrc).getReg(0);
4793     if (Offset != 0) {
4794       auto ShiftAmt = MIRBuilder.buildConstant(IntDstTy, Offset);
4795       ExtInsSrc = MIRBuilder.buildShl(IntDstTy, ExtInsSrc, ShiftAmt).getReg(0);
4796     }
4797 
4798     APInt MaskVal = APInt::getBitsSetWithWrap(DstTy.getSizeInBits(),
4799                                               Offset + InsertTy.getSizeInBits(),
4800                                               Offset);
4801 
4802     auto Mask = MIRBuilder.buildConstant(IntDstTy, MaskVal);
4803     auto MaskedSrc = MIRBuilder.buildAnd(IntDstTy, Src, Mask);
4804     auto Or = MIRBuilder.buildOr(IntDstTy, MaskedSrc, ExtInsSrc);
4805 
4806     MIRBuilder.buildBitcast(Dst, Or);
4807     MI.eraseFromParent();
4808     return Legalized;
4809   }
4810 
4811   return UnableToLegalize;
4812 }
4813 
4814 LegalizerHelper::LegalizeResult
4815 LegalizerHelper::lowerSADDO_SSUBO(MachineInstr &MI) {
4816   Register Dst0 = MI.getOperand(0).getReg();
4817   Register Dst1 = MI.getOperand(1).getReg();
4818   Register LHS = MI.getOperand(2).getReg();
4819   Register RHS = MI.getOperand(3).getReg();
4820   const bool IsAdd = MI.getOpcode() == TargetOpcode::G_SADDO;
4821 
4822   LLT Ty = MRI.getType(Dst0);
4823   LLT BoolTy = MRI.getType(Dst1);
4824 
4825   if (IsAdd)
4826     MIRBuilder.buildAdd(Dst0, LHS, RHS);
4827   else
4828     MIRBuilder.buildSub(Dst0, LHS, RHS);
4829 
4830   // TODO: If SADDSAT/SSUBSAT is legal, compare results to detect overflow.
4831 
4832   auto Zero = MIRBuilder.buildConstant(Ty, 0);
4833 
4834   // For an addition, the result should be less than one of the operands (LHS)
4835   // if and only if the other operand (RHS) is negative, otherwise there will
4836   // be overflow.
4837   // For a subtraction, the result should be less than one of the operands
4838   // (LHS) if and only if the other operand (RHS) is (non-zero) positive,
4839   // otherwise there will be overflow.
4840   auto ResultLowerThanLHS =
4841       MIRBuilder.buildICmp(CmpInst::ICMP_SLT, BoolTy, Dst0, LHS);
4842   auto ConditionRHS = MIRBuilder.buildICmp(
4843       IsAdd ? CmpInst::ICMP_SLT : CmpInst::ICMP_SGT, BoolTy, RHS, Zero);
4844 
4845   MIRBuilder.buildXor(Dst1, ConditionRHS, ResultLowerThanLHS);
4846   MI.eraseFromParent();
4847   return Legalized;
4848 }
4849 
4850 LegalizerHelper::LegalizeResult
4851 LegalizerHelper::lowerBswap(MachineInstr &MI) {
4852   Register Dst = MI.getOperand(0).getReg();
4853   Register Src = MI.getOperand(1).getReg();
4854   const LLT Ty = MRI.getType(Src);
4855   unsigned SizeInBytes = Ty.getSizeInBytes();
4856   unsigned BaseShiftAmt = (SizeInBytes - 1) * 8;
4857 
4858   // Swap most and least significant byte, set remaining bytes in Res to zero.
4859   auto ShiftAmt = MIRBuilder.buildConstant(Ty, BaseShiftAmt);
4860   auto LSByteShiftedLeft = MIRBuilder.buildShl(Ty, Src, ShiftAmt);
4861   auto MSByteShiftedRight = MIRBuilder.buildLShr(Ty, Src, ShiftAmt);
4862   auto Res = MIRBuilder.buildOr(Ty, MSByteShiftedRight, LSByteShiftedLeft);
4863 
4864   // Set i-th high/low byte in Res to i-th low/high byte from Src.
4865   for (unsigned i = 1; i < SizeInBytes / 2; ++i) {
4866     // AND with Mask leaves byte i unchanged and sets remaining bytes to 0.
4867     APInt APMask(SizeInBytes * 8, 0xFF << (i * 8));
4868     auto Mask = MIRBuilder.buildConstant(Ty, APMask);
4869     auto ShiftAmt = MIRBuilder.buildConstant(Ty, BaseShiftAmt - 16 * i);
4870     // Low byte shifted left to place of high byte: (Src & Mask) << ShiftAmt.
4871     auto LoByte = MIRBuilder.buildAnd(Ty, Src, Mask);
4872     auto LoShiftedLeft = MIRBuilder.buildShl(Ty, LoByte, ShiftAmt);
4873     Res = MIRBuilder.buildOr(Ty, Res, LoShiftedLeft);
4874     // High byte shifted right to place of low byte: (Src >> ShiftAmt) & Mask.
4875     auto SrcShiftedRight = MIRBuilder.buildLShr(Ty, Src, ShiftAmt);
4876     auto HiShiftedRight = MIRBuilder.buildAnd(Ty, SrcShiftedRight, Mask);
4877     Res = MIRBuilder.buildOr(Ty, Res, HiShiftedRight);
4878   }
4879   Res.getInstr()->getOperand(0).setReg(Dst);
4880 
4881   MI.eraseFromParent();
4882   return Legalized;
4883 }
4884 
4885 //{ (Src & Mask) >> N } | { (Src << N) & Mask }
4886 static MachineInstrBuilder SwapN(unsigned N, DstOp Dst, MachineIRBuilder &B,
4887                                  MachineInstrBuilder Src, APInt Mask) {
4888   const LLT Ty = Dst.getLLTTy(*B.getMRI());
4889   MachineInstrBuilder C_N = B.buildConstant(Ty, N);
4890   MachineInstrBuilder MaskLoNTo0 = B.buildConstant(Ty, Mask);
4891   auto LHS = B.buildLShr(Ty, B.buildAnd(Ty, Src, MaskLoNTo0), C_N);
4892   auto RHS = B.buildAnd(Ty, B.buildShl(Ty, Src, C_N), MaskLoNTo0);
4893   return B.buildOr(Dst, LHS, RHS);
4894 }
4895 
4896 LegalizerHelper::LegalizeResult
4897 LegalizerHelper::lowerBitreverse(MachineInstr &MI) {
4898   Register Dst = MI.getOperand(0).getReg();
4899   Register Src = MI.getOperand(1).getReg();
4900   const LLT Ty = MRI.getType(Src);
4901   unsigned Size = Ty.getSizeInBits();
4902 
4903   MachineInstrBuilder BSWAP =
4904       MIRBuilder.buildInstr(TargetOpcode::G_BSWAP, {Ty}, {Src});
4905 
4906   // swap high and low 4 bits in 8 bit blocks 7654|3210 -> 3210|7654
4907   //    [(val & 0xF0F0F0F0) >> 4] | [(val & 0x0F0F0F0F) << 4]
4908   // -> [(val & 0xF0F0F0F0) >> 4] | [(val << 4) & 0xF0F0F0F0]
4909   MachineInstrBuilder Swap4 =
4910       SwapN(4, Ty, MIRBuilder, BSWAP, APInt::getSplat(Size, APInt(8, 0xF0)));
4911 
4912   // swap high and low 2 bits in 4 bit blocks 32|10 76|54 -> 10|32 54|76
4913   //    [(val & 0xCCCCCCCC) >> 2] & [(val & 0x33333333) << 2]
4914   // -> [(val & 0xCCCCCCCC) >> 2] & [(val << 2) & 0xCCCCCCCC]
4915   MachineInstrBuilder Swap2 =
4916       SwapN(2, Ty, MIRBuilder, Swap4, APInt::getSplat(Size, APInt(8, 0xCC)));
4917 
4918   // swap high and low 1 bit in 2 bit blocks 1|0 3|2 5|4 7|6 -> 0|1 2|3 4|5 6|7
4919   //    [(val & 0xAAAAAAAA) >> 1] & [(val & 0x55555555) << 1]
4920   // -> [(val & 0xAAAAAAAA) >> 1] & [(val << 1) & 0xAAAAAAAA]
4921   SwapN(1, Dst, MIRBuilder, Swap2, APInt::getSplat(Size, APInt(8, 0xAA)));
4922 
4923   MI.eraseFromParent();
4924   return Legalized;
4925 }
4926 
4927 LegalizerHelper::LegalizeResult
4928 LegalizerHelper::lowerReadWriteRegister(MachineInstr &MI) {
4929   MachineFunction &MF = MIRBuilder.getMF();
4930   const TargetSubtargetInfo &STI = MF.getSubtarget();
4931   const TargetLowering *TLI = STI.getTargetLowering();
4932 
4933   bool IsRead = MI.getOpcode() == TargetOpcode::G_READ_REGISTER;
4934   int NameOpIdx = IsRead ? 1 : 0;
4935   int ValRegIndex = IsRead ? 0 : 1;
4936 
4937   Register ValReg = MI.getOperand(ValRegIndex).getReg();
4938   const LLT Ty = MRI.getType(ValReg);
4939   const MDString *RegStr = cast<MDString>(
4940     cast<MDNode>(MI.getOperand(NameOpIdx).getMetadata())->getOperand(0));
4941 
4942   Register PhysReg = TLI->getRegisterByName(RegStr->getString().data(), Ty, MF);
4943   if (!PhysReg.isValid())
4944     return UnableToLegalize;
4945 
4946   if (IsRead)
4947     MIRBuilder.buildCopy(ValReg, PhysReg);
4948   else
4949     MIRBuilder.buildCopy(PhysReg, ValReg);
4950 
4951   MI.eraseFromParent();
4952   return Legalized;
4953 }
4954