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