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