xref: /freebsd-src/contrib/llvm-project/llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp (revision 5e801ac66d24704442eba426ed13c3effb8a34e7)
1 //===-- lib/CodeGen/GlobalISel/GICombinerHelper.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 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
9 #include "llvm/ADT/SetVector.h"
10 #include "llvm/ADT/SmallBitVector.h"
11 #include "llvm/CodeGen/GlobalISel/Combiner.h"
12 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
13 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
14 #include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
15 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
16 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
17 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
18 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
19 #include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h"
20 #include "llvm/CodeGen/GlobalISel/Utils.h"
21 #include "llvm/CodeGen/LowLevelType.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineDominators.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineInstr.h"
26 #include "llvm/CodeGen/MachineMemOperand.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/CodeGen/TargetInstrInfo.h"
29 #include "llvm/CodeGen/TargetLowering.h"
30 #include "llvm/CodeGen/TargetOpcodes.h"
31 #include "llvm/IR/DataLayout.h"
32 #include "llvm/Support/Casting.h"
33 #include "llvm/Support/DivisionByConstantInfo.h"
34 #include "llvm/Support/MathExtras.h"
35 #include <tuple>
36 
37 #define DEBUG_TYPE "gi-combiner"
38 
39 using namespace llvm;
40 using namespace MIPatternMatch;
41 
42 // Option to allow testing of the combiner while no targets know about indexed
43 // addressing.
44 static cl::opt<bool>
45     ForceLegalIndexing("force-legal-indexing", cl::Hidden, cl::init(false),
46                        cl::desc("Force all indexed operations to be "
47                                 "legal for the GlobalISel combiner"));
48 
49 CombinerHelper::CombinerHelper(GISelChangeObserver &Observer,
50                                MachineIRBuilder &B, GISelKnownBits *KB,
51                                MachineDominatorTree *MDT,
52                                const LegalizerInfo *LI)
53     : Builder(B), MRI(Builder.getMF().getRegInfo()), Observer(Observer), KB(KB),
54       MDT(MDT), LI(LI), RBI(Builder.getMF().getSubtarget().getRegBankInfo()),
55       TRI(Builder.getMF().getSubtarget().getRegisterInfo()) {
56   (void)this->KB;
57 }
58 
59 const TargetLowering &CombinerHelper::getTargetLowering() const {
60   return *Builder.getMF().getSubtarget().getTargetLowering();
61 }
62 
63 /// \returns The little endian in-memory byte position of byte \p I in a
64 /// \p ByteWidth bytes wide type.
65 ///
66 /// E.g. Given a 4-byte type x, x[0] -> byte 0
67 static unsigned littleEndianByteAt(const unsigned ByteWidth, const unsigned I) {
68   assert(I < ByteWidth && "I must be in [0, ByteWidth)");
69   return I;
70 }
71 
72 /// Determines the LogBase2 value for a non-null input value using the
73 /// transform: LogBase2(V) = (EltBits - 1) - ctlz(V).
74 static Register buildLogBase2(Register V, MachineIRBuilder &MIB) {
75   auto &MRI = *MIB.getMRI();
76   LLT Ty = MRI.getType(V);
77   auto Ctlz = MIB.buildCTLZ(Ty, V);
78   auto Base = MIB.buildConstant(Ty, Ty.getScalarSizeInBits() - 1);
79   return MIB.buildSub(Ty, Base, Ctlz).getReg(0);
80 }
81 
82 /// \returns The big endian in-memory byte position of byte \p I in a
83 /// \p ByteWidth bytes wide type.
84 ///
85 /// E.g. Given a 4-byte type x, x[0] -> byte 3
86 static unsigned bigEndianByteAt(const unsigned ByteWidth, const unsigned I) {
87   assert(I < ByteWidth && "I must be in [0, ByteWidth)");
88   return ByteWidth - I - 1;
89 }
90 
91 /// Given a map from byte offsets in memory to indices in a load/store,
92 /// determine if that map corresponds to a little or big endian byte pattern.
93 ///
94 /// \param MemOffset2Idx maps memory offsets to address offsets.
95 /// \param LowestIdx is the lowest index in \p MemOffset2Idx.
96 ///
97 /// \returns true if the map corresponds to a big endian byte pattern, false
98 /// if it corresponds to a little endian byte pattern, and None otherwise.
99 ///
100 /// E.g. given a 32-bit type x, and x[AddrOffset], the in-memory byte patterns
101 /// are as follows:
102 ///
103 /// AddrOffset   Little endian    Big endian
104 /// 0            0                3
105 /// 1            1                2
106 /// 2            2                1
107 /// 3            3                0
108 static Optional<bool>
109 isBigEndian(const SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx,
110             int64_t LowestIdx) {
111   // Need at least two byte positions to decide on endianness.
112   unsigned Width = MemOffset2Idx.size();
113   if (Width < 2)
114     return None;
115   bool BigEndian = true, LittleEndian = true;
116   for (unsigned MemOffset = 0; MemOffset < Width; ++ MemOffset) {
117     auto MemOffsetAndIdx = MemOffset2Idx.find(MemOffset);
118     if (MemOffsetAndIdx == MemOffset2Idx.end())
119       return None;
120     const int64_t Idx = MemOffsetAndIdx->second - LowestIdx;
121     assert(Idx >= 0 && "Expected non-negative byte offset?");
122     LittleEndian &= Idx == littleEndianByteAt(Width, MemOffset);
123     BigEndian &= Idx == bigEndianByteAt(Width, MemOffset);
124     if (!BigEndian && !LittleEndian)
125       return None;
126   }
127 
128   assert((BigEndian != LittleEndian) &&
129          "Pattern cannot be both big and little endian!");
130   return BigEndian;
131 }
132 
133 bool CombinerHelper::isLegalOrBeforeLegalizer(
134     const LegalityQuery &Query) const {
135   return !LI || LI->getAction(Query).Action == LegalizeActions::Legal;
136 }
137 
138 void CombinerHelper::replaceRegWith(MachineRegisterInfo &MRI, Register FromReg,
139                                     Register ToReg) const {
140   Observer.changingAllUsesOfReg(MRI, FromReg);
141 
142   if (MRI.constrainRegAttrs(ToReg, FromReg))
143     MRI.replaceRegWith(FromReg, ToReg);
144   else
145     Builder.buildCopy(ToReg, FromReg);
146 
147   Observer.finishedChangingAllUsesOfReg();
148 }
149 
150 void CombinerHelper::replaceRegOpWith(MachineRegisterInfo &MRI,
151                                       MachineOperand &FromRegOp,
152                                       Register ToReg) const {
153   assert(FromRegOp.getParent() && "Expected an operand in an MI");
154   Observer.changingInstr(*FromRegOp.getParent());
155 
156   FromRegOp.setReg(ToReg);
157 
158   Observer.changedInstr(*FromRegOp.getParent());
159 }
160 
161 void CombinerHelper::replaceOpcodeWith(MachineInstr &FromMI,
162                                        unsigned ToOpcode) const {
163   Observer.changingInstr(FromMI);
164 
165   FromMI.setDesc(Builder.getTII().get(ToOpcode));
166 
167   Observer.changedInstr(FromMI);
168 }
169 
170 const RegisterBank *CombinerHelper::getRegBank(Register Reg) const {
171   return RBI->getRegBank(Reg, MRI, *TRI);
172 }
173 
174 void CombinerHelper::setRegBank(Register Reg, const RegisterBank *RegBank) {
175   if (RegBank)
176     MRI.setRegBank(Reg, *RegBank);
177 }
178 
179 bool CombinerHelper::tryCombineCopy(MachineInstr &MI) {
180   if (matchCombineCopy(MI)) {
181     applyCombineCopy(MI);
182     return true;
183   }
184   return false;
185 }
186 bool CombinerHelper::matchCombineCopy(MachineInstr &MI) {
187   if (MI.getOpcode() != TargetOpcode::COPY)
188     return false;
189   Register DstReg = MI.getOperand(0).getReg();
190   Register SrcReg = MI.getOperand(1).getReg();
191   return canReplaceReg(DstReg, SrcReg, MRI);
192 }
193 void CombinerHelper::applyCombineCopy(MachineInstr &MI) {
194   Register DstReg = MI.getOperand(0).getReg();
195   Register SrcReg = MI.getOperand(1).getReg();
196   MI.eraseFromParent();
197   replaceRegWith(MRI, DstReg, SrcReg);
198 }
199 
200 bool CombinerHelper::tryCombineConcatVectors(MachineInstr &MI) {
201   bool IsUndef = false;
202   SmallVector<Register, 4> Ops;
203   if (matchCombineConcatVectors(MI, IsUndef, Ops)) {
204     applyCombineConcatVectors(MI, IsUndef, Ops);
205     return true;
206   }
207   return false;
208 }
209 
210 bool CombinerHelper::matchCombineConcatVectors(MachineInstr &MI, bool &IsUndef,
211                                                SmallVectorImpl<Register> &Ops) {
212   assert(MI.getOpcode() == TargetOpcode::G_CONCAT_VECTORS &&
213          "Invalid instruction");
214   IsUndef = true;
215   MachineInstr *Undef = nullptr;
216 
217   // Walk over all the operands of concat vectors and check if they are
218   // build_vector themselves or undef.
219   // Then collect their operands in Ops.
220   for (const MachineOperand &MO : MI.uses()) {
221     Register Reg = MO.getReg();
222     MachineInstr *Def = MRI.getVRegDef(Reg);
223     assert(Def && "Operand not defined");
224     switch (Def->getOpcode()) {
225     case TargetOpcode::G_BUILD_VECTOR:
226       IsUndef = false;
227       // Remember the operands of the build_vector to fold
228       // them into the yet-to-build flattened concat vectors.
229       for (const MachineOperand &BuildVecMO : Def->uses())
230         Ops.push_back(BuildVecMO.getReg());
231       break;
232     case TargetOpcode::G_IMPLICIT_DEF: {
233       LLT OpType = MRI.getType(Reg);
234       // Keep one undef value for all the undef operands.
235       if (!Undef) {
236         Builder.setInsertPt(*MI.getParent(), MI);
237         Undef = Builder.buildUndef(OpType.getScalarType());
238       }
239       assert(MRI.getType(Undef->getOperand(0).getReg()) ==
240                  OpType.getScalarType() &&
241              "All undefs should have the same type");
242       // Break the undef vector in as many scalar elements as needed
243       // for the flattening.
244       for (unsigned EltIdx = 0, EltEnd = OpType.getNumElements();
245            EltIdx != EltEnd; ++EltIdx)
246         Ops.push_back(Undef->getOperand(0).getReg());
247       break;
248     }
249     default:
250       return false;
251     }
252   }
253   return true;
254 }
255 void CombinerHelper::applyCombineConcatVectors(
256     MachineInstr &MI, bool IsUndef, const ArrayRef<Register> Ops) {
257   // We determined that the concat_vectors can be flatten.
258   // Generate the flattened build_vector.
259   Register DstReg = MI.getOperand(0).getReg();
260   Builder.setInsertPt(*MI.getParent(), MI);
261   Register NewDstReg = MRI.cloneVirtualRegister(DstReg);
262 
263   // Note: IsUndef is sort of redundant. We could have determine it by
264   // checking that at all Ops are undef.  Alternatively, we could have
265   // generate a build_vector of undefs and rely on another combine to
266   // clean that up.  For now, given we already gather this information
267   // in tryCombineConcatVectors, just save compile time and issue the
268   // right thing.
269   if (IsUndef)
270     Builder.buildUndef(NewDstReg);
271   else
272     Builder.buildBuildVector(NewDstReg, Ops);
273   MI.eraseFromParent();
274   replaceRegWith(MRI, DstReg, NewDstReg);
275 }
276 
277 bool CombinerHelper::tryCombineShuffleVector(MachineInstr &MI) {
278   SmallVector<Register, 4> Ops;
279   if (matchCombineShuffleVector(MI, Ops)) {
280     applyCombineShuffleVector(MI, Ops);
281     return true;
282   }
283   return false;
284 }
285 
286 bool CombinerHelper::matchCombineShuffleVector(MachineInstr &MI,
287                                                SmallVectorImpl<Register> &Ops) {
288   assert(MI.getOpcode() == TargetOpcode::G_SHUFFLE_VECTOR &&
289          "Invalid instruction kind");
290   LLT DstType = MRI.getType(MI.getOperand(0).getReg());
291   Register Src1 = MI.getOperand(1).getReg();
292   LLT SrcType = MRI.getType(Src1);
293   // As bizarre as it may look, shuffle vector can actually produce
294   // scalar! This is because at the IR level a <1 x ty> shuffle
295   // vector is perfectly valid.
296   unsigned DstNumElts = DstType.isVector() ? DstType.getNumElements() : 1;
297   unsigned SrcNumElts = SrcType.isVector() ? SrcType.getNumElements() : 1;
298 
299   // If the resulting vector is smaller than the size of the source
300   // vectors being concatenated, we won't be able to replace the
301   // shuffle vector into a concat_vectors.
302   //
303   // Note: We may still be able to produce a concat_vectors fed by
304   //       extract_vector_elt and so on. It is less clear that would
305   //       be better though, so don't bother for now.
306   //
307   // If the destination is a scalar, the size of the sources doesn't
308   // matter. we will lower the shuffle to a plain copy. This will
309   // work only if the source and destination have the same size. But
310   // that's covered by the next condition.
311   //
312   // TODO: If the size between the source and destination don't match
313   //       we could still emit an extract vector element in that case.
314   if (DstNumElts < 2 * SrcNumElts && DstNumElts != 1)
315     return false;
316 
317   // Check that the shuffle mask can be broken evenly between the
318   // different sources.
319   if (DstNumElts % SrcNumElts != 0)
320     return false;
321 
322   // Mask length is a multiple of the source vector length.
323   // Check if the shuffle is some kind of concatenation of the input
324   // vectors.
325   unsigned NumConcat = DstNumElts / SrcNumElts;
326   SmallVector<int, 8> ConcatSrcs(NumConcat, -1);
327   ArrayRef<int> Mask = MI.getOperand(3).getShuffleMask();
328   for (unsigned i = 0; i != DstNumElts; ++i) {
329     int Idx = Mask[i];
330     // Undef value.
331     if (Idx < 0)
332       continue;
333     // Ensure the indices in each SrcType sized piece are sequential and that
334     // the same source is used for the whole piece.
335     if ((Idx % SrcNumElts != (i % SrcNumElts)) ||
336         (ConcatSrcs[i / SrcNumElts] >= 0 &&
337          ConcatSrcs[i / SrcNumElts] != (int)(Idx / SrcNumElts)))
338       return false;
339     // Remember which source this index came from.
340     ConcatSrcs[i / SrcNumElts] = Idx / SrcNumElts;
341   }
342 
343   // The shuffle is concatenating multiple vectors together.
344   // Collect the different operands for that.
345   Register UndefReg;
346   Register Src2 = MI.getOperand(2).getReg();
347   for (auto Src : ConcatSrcs) {
348     if (Src < 0) {
349       if (!UndefReg) {
350         Builder.setInsertPt(*MI.getParent(), MI);
351         UndefReg = Builder.buildUndef(SrcType).getReg(0);
352       }
353       Ops.push_back(UndefReg);
354     } else if (Src == 0)
355       Ops.push_back(Src1);
356     else
357       Ops.push_back(Src2);
358   }
359   return true;
360 }
361 
362 void CombinerHelper::applyCombineShuffleVector(MachineInstr &MI,
363                                                const ArrayRef<Register> Ops) {
364   Register DstReg = MI.getOperand(0).getReg();
365   Builder.setInsertPt(*MI.getParent(), MI);
366   Register NewDstReg = MRI.cloneVirtualRegister(DstReg);
367 
368   if (Ops.size() == 1)
369     Builder.buildCopy(NewDstReg, Ops[0]);
370   else
371     Builder.buildMerge(NewDstReg, Ops);
372 
373   MI.eraseFromParent();
374   replaceRegWith(MRI, DstReg, NewDstReg);
375 }
376 
377 namespace {
378 
379 /// Select a preference between two uses. CurrentUse is the current preference
380 /// while *ForCandidate is attributes of the candidate under consideration.
381 PreferredTuple ChoosePreferredUse(PreferredTuple &CurrentUse,
382                                   const LLT TyForCandidate,
383                                   unsigned OpcodeForCandidate,
384                                   MachineInstr *MIForCandidate) {
385   if (!CurrentUse.Ty.isValid()) {
386     if (CurrentUse.ExtendOpcode == OpcodeForCandidate ||
387         CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT)
388       return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
389     return CurrentUse;
390   }
391 
392   // We permit the extend to hoist through basic blocks but this is only
393   // sensible if the target has extending loads. If you end up lowering back
394   // into a load and extend during the legalizer then the end result is
395   // hoisting the extend up to the load.
396 
397   // Prefer defined extensions to undefined extensions as these are more
398   // likely to reduce the number of instructions.
399   if (OpcodeForCandidate == TargetOpcode::G_ANYEXT &&
400       CurrentUse.ExtendOpcode != TargetOpcode::G_ANYEXT)
401     return CurrentUse;
402   else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT &&
403            OpcodeForCandidate != TargetOpcode::G_ANYEXT)
404     return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
405 
406   // Prefer sign extensions to zero extensions as sign-extensions tend to be
407   // more expensive.
408   if (CurrentUse.Ty == TyForCandidate) {
409     if (CurrentUse.ExtendOpcode == TargetOpcode::G_SEXT &&
410         OpcodeForCandidate == TargetOpcode::G_ZEXT)
411       return CurrentUse;
412     else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ZEXT &&
413              OpcodeForCandidate == TargetOpcode::G_SEXT)
414       return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
415   }
416 
417   // This is potentially target specific. We've chosen the largest type
418   // because G_TRUNC is usually free. One potential catch with this is that
419   // some targets have a reduced number of larger registers than smaller
420   // registers and this choice potentially increases the live-range for the
421   // larger value.
422   if (TyForCandidate.getSizeInBits() > CurrentUse.Ty.getSizeInBits()) {
423     return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
424   }
425   return CurrentUse;
426 }
427 
428 /// Find a suitable place to insert some instructions and insert them. This
429 /// function accounts for special cases like inserting before a PHI node.
430 /// The current strategy for inserting before PHI's is to duplicate the
431 /// instructions for each predecessor. However, while that's ok for G_TRUNC
432 /// on most targets since it generally requires no code, other targets/cases may
433 /// want to try harder to find a dominating block.
434 static void InsertInsnsWithoutSideEffectsBeforeUse(
435     MachineIRBuilder &Builder, MachineInstr &DefMI, MachineOperand &UseMO,
436     std::function<void(MachineBasicBlock *, MachineBasicBlock::iterator,
437                        MachineOperand &UseMO)>
438         Inserter) {
439   MachineInstr &UseMI = *UseMO.getParent();
440 
441   MachineBasicBlock *InsertBB = UseMI.getParent();
442 
443   // If the use is a PHI then we want the predecessor block instead.
444   if (UseMI.isPHI()) {
445     MachineOperand *PredBB = std::next(&UseMO);
446     InsertBB = PredBB->getMBB();
447   }
448 
449   // If the block is the same block as the def then we want to insert just after
450   // the def instead of at the start of the block.
451   if (InsertBB == DefMI.getParent()) {
452     MachineBasicBlock::iterator InsertPt = &DefMI;
453     Inserter(InsertBB, std::next(InsertPt), UseMO);
454     return;
455   }
456 
457   // Otherwise we want the start of the BB
458   Inserter(InsertBB, InsertBB->getFirstNonPHI(), UseMO);
459 }
460 } // end anonymous namespace
461 
462 bool CombinerHelper::tryCombineExtendingLoads(MachineInstr &MI) {
463   PreferredTuple Preferred;
464   if (matchCombineExtendingLoads(MI, Preferred)) {
465     applyCombineExtendingLoads(MI, Preferred);
466     return true;
467   }
468   return false;
469 }
470 
471 bool CombinerHelper::matchCombineExtendingLoads(MachineInstr &MI,
472                                                 PreferredTuple &Preferred) {
473   // We match the loads and follow the uses to the extend instead of matching
474   // the extends and following the def to the load. This is because the load
475   // must remain in the same position for correctness (unless we also add code
476   // to find a safe place to sink it) whereas the extend is freely movable.
477   // It also prevents us from duplicating the load for the volatile case or just
478   // for performance.
479   GAnyLoad *LoadMI = dyn_cast<GAnyLoad>(&MI);
480   if (!LoadMI)
481     return false;
482 
483   Register LoadReg = LoadMI->getDstReg();
484 
485   LLT LoadValueTy = MRI.getType(LoadReg);
486   if (!LoadValueTy.isScalar())
487     return false;
488 
489   // Most architectures are going to legalize <s8 loads into at least a 1 byte
490   // load, and the MMOs can only describe memory accesses in multiples of bytes.
491   // If we try to perform extload combining on those, we can end up with
492   // %a(s8) = extload %ptr (load 1 byte from %ptr)
493   // ... which is an illegal extload instruction.
494   if (LoadValueTy.getSizeInBits() < 8)
495     return false;
496 
497   // For non power-of-2 types, they will very likely be legalized into multiple
498   // loads. Don't bother trying to match them into extending loads.
499   if (!isPowerOf2_32(LoadValueTy.getSizeInBits()))
500     return false;
501 
502   // Find the preferred type aside from the any-extends (unless it's the only
503   // one) and non-extending ops. We'll emit an extending load to that type and
504   // and emit a variant of (extend (trunc X)) for the others according to the
505   // relative type sizes. At the same time, pick an extend to use based on the
506   // extend involved in the chosen type.
507   unsigned PreferredOpcode =
508       isa<GLoad>(&MI)
509           ? TargetOpcode::G_ANYEXT
510           : isa<GSExtLoad>(&MI) ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT;
511   Preferred = {LLT(), PreferredOpcode, nullptr};
512   for (auto &UseMI : MRI.use_nodbg_instructions(LoadReg)) {
513     if (UseMI.getOpcode() == TargetOpcode::G_SEXT ||
514         UseMI.getOpcode() == TargetOpcode::G_ZEXT ||
515         (UseMI.getOpcode() == TargetOpcode::G_ANYEXT)) {
516       const auto &MMO = LoadMI->getMMO();
517       // For atomics, only form anyextending loads.
518       if (MMO.isAtomic() && UseMI.getOpcode() != TargetOpcode::G_ANYEXT)
519         continue;
520       // Check for legality.
521       if (LI) {
522         LegalityQuery::MemDesc MMDesc(MMO);
523         LLT UseTy = MRI.getType(UseMI.getOperand(0).getReg());
524         LLT SrcTy = MRI.getType(LoadMI->getPointerReg());
525         if (LI->getAction({LoadMI->getOpcode(), {UseTy, SrcTy}, {MMDesc}})
526                 .Action != LegalizeActions::Legal)
527           continue;
528       }
529       Preferred = ChoosePreferredUse(Preferred,
530                                      MRI.getType(UseMI.getOperand(0).getReg()),
531                                      UseMI.getOpcode(), &UseMI);
532     }
533   }
534 
535   // There were no extends
536   if (!Preferred.MI)
537     return false;
538   // It should be impossible to chose an extend without selecting a different
539   // type since by definition the result of an extend is larger.
540   assert(Preferred.Ty != LoadValueTy && "Extending to same type?");
541 
542   LLVM_DEBUG(dbgs() << "Preferred use is: " << *Preferred.MI);
543   return true;
544 }
545 
546 void CombinerHelper::applyCombineExtendingLoads(MachineInstr &MI,
547                                                 PreferredTuple &Preferred) {
548   // Rewrite the load to the chosen extending load.
549   Register ChosenDstReg = Preferred.MI->getOperand(0).getReg();
550 
551   // Inserter to insert a truncate back to the original type at a given point
552   // with some basic CSE to limit truncate duplication to one per BB.
553   DenseMap<MachineBasicBlock *, MachineInstr *> EmittedInsns;
554   auto InsertTruncAt = [&](MachineBasicBlock *InsertIntoBB,
555                            MachineBasicBlock::iterator InsertBefore,
556                            MachineOperand &UseMO) {
557     MachineInstr *PreviouslyEmitted = EmittedInsns.lookup(InsertIntoBB);
558     if (PreviouslyEmitted) {
559       Observer.changingInstr(*UseMO.getParent());
560       UseMO.setReg(PreviouslyEmitted->getOperand(0).getReg());
561       Observer.changedInstr(*UseMO.getParent());
562       return;
563     }
564 
565     Builder.setInsertPt(*InsertIntoBB, InsertBefore);
566     Register NewDstReg = MRI.cloneVirtualRegister(MI.getOperand(0).getReg());
567     MachineInstr *NewMI = Builder.buildTrunc(NewDstReg, ChosenDstReg);
568     EmittedInsns[InsertIntoBB] = NewMI;
569     replaceRegOpWith(MRI, UseMO, NewDstReg);
570   };
571 
572   Observer.changingInstr(MI);
573   MI.setDesc(
574       Builder.getTII().get(Preferred.ExtendOpcode == TargetOpcode::G_SEXT
575                                ? TargetOpcode::G_SEXTLOAD
576                                : Preferred.ExtendOpcode == TargetOpcode::G_ZEXT
577                                      ? TargetOpcode::G_ZEXTLOAD
578                                      : TargetOpcode::G_LOAD));
579 
580   // Rewrite all the uses to fix up the types.
581   auto &LoadValue = MI.getOperand(0);
582   SmallVector<MachineOperand *, 4> Uses;
583   for (auto &UseMO : MRI.use_operands(LoadValue.getReg()))
584     Uses.push_back(&UseMO);
585 
586   for (auto *UseMO : Uses) {
587     MachineInstr *UseMI = UseMO->getParent();
588 
589     // If the extend is compatible with the preferred extend then we should fix
590     // up the type and extend so that it uses the preferred use.
591     if (UseMI->getOpcode() == Preferred.ExtendOpcode ||
592         UseMI->getOpcode() == TargetOpcode::G_ANYEXT) {
593       Register UseDstReg = UseMI->getOperand(0).getReg();
594       MachineOperand &UseSrcMO = UseMI->getOperand(1);
595       const LLT UseDstTy = MRI.getType(UseDstReg);
596       if (UseDstReg != ChosenDstReg) {
597         if (Preferred.Ty == UseDstTy) {
598           // If the use has the same type as the preferred use, then merge
599           // the vregs and erase the extend. For example:
600           //    %1:_(s8) = G_LOAD ...
601           //    %2:_(s32) = G_SEXT %1(s8)
602           //    %3:_(s32) = G_ANYEXT %1(s8)
603           //    ... = ... %3(s32)
604           // rewrites to:
605           //    %2:_(s32) = G_SEXTLOAD ...
606           //    ... = ... %2(s32)
607           replaceRegWith(MRI, UseDstReg, ChosenDstReg);
608           Observer.erasingInstr(*UseMO->getParent());
609           UseMO->getParent()->eraseFromParent();
610         } else if (Preferred.Ty.getSizeInBits() < UseDstTy.getSizeInBits()) {
611           // If the preferred size is smaller, then keep the extend but extend
612           // from the result of the extending load. For example:
613           //    %1:_(s8) = G_LOAD ...
614           //    %2:_(s32) = G_SEXT %1(s8)
615           //    %3:_(s64) = G_ANYEXT %1(s8)
616           //    ... = ... %3(s64)
617           /// rewrites to:
618           //    %2:_(s32) = G_SEXTLOAD ...
619           //    %3:_(s64) = G_ANYEXT %2:_(s32)
620           //    ... = ... %3(s64)
621           replaceRegOpWith(MRI, UseSrcMO, ChosenDstReg);
622         } else {
623           // If the preferred size is large, then insert a truncate. For
624           // example:
625           //    %1:_(s8) = G_LOAD ...
626           //    %2:_(s64) = G_SEXT %1(s8)
627           //    %3:_(s32) = G_ZEXT %1(s8)
628           //    ... = ... %3(s32)
629           /// rewrites to:
630           //    %2:_(s64) = G_SEXTLOAD ...
631           //    %4:_(s8) = G_TRUNC %2:_(s32)
632           //    %3:_(s64) = G_ZEXT %2:_(s8)
633           //    ... = ... %3(s64)
634           InsertInsnsWithoutSideEffectsBeforeUse(Builder, MI, *UseMO,
635                                                  InsertTruncAt);
636         }
637         continue;
638       }
639       // The use is (one of) the uses of the preferred use we chose earlier.
640       // We're going to update the load to def this value later so just erase
641       // the old extend.
642       Observer.erasingInstr(*UseMO->getParent());
643       UseMO->getParent()->eraseFromParent();
644       continue;
645     }
646 
647     // The use isn't an extend. Truncate back to the type we originally loaded.
648     // This is free on many targets.
649     InsertInsnsWithoutSideEffectsBeforeUse(Builder, MI, *UseMO, InsertTruncAt);
650   }
651 
652   MI.getOperand(0).setReg(ChosenDstReg);
653   Observer.changedInstr(MI);
654 }
655 
656 bool CombinerHelper::matchCombineLoadWithAndMask(MachineInstr &MI,
657                                                  BuildFnTy &MatchInfo) {
658   assert(MI.getOpcode() == TargetOpcode::G_AND);
659 
660   // If we have the following code:
661   //  %mask = G_CONSTANT 255
662   //  %ld   = G_LOAD %ptr, (load s16)
663   //  %and  = G_AND %ld, %mask
664   //
665   // Try to fold it into
666   //   %ld = G_ZEXTLOAD %ptr, (load s8)
667 
668   Register Dst = MI.getOperand(0).getReg();
669   if (MRI.getType(Dst).isVector())
670     return false;
671 
672   auto MaybeMask =
673       getIConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI);
674   if (!MaybeMask)
675     return false;
676 
677   APInt MaskVal = MaybeMask->Value;
678 
679   if (!MaskVal.isMask())
680     return false;
681 
682   Register SrcReg = MI.getOperand(1).getReg();
683   GAnyLoad *LoadMI = getOpcodeDef<GAnyLoad>(SrcReg, MRI);
684   if (!LoadMI || !MRI.hasOneNonDBGUse(LoadMI->getDstReg()) ||
685       !LoadMI->isSimple())
686     return false;
687 
688   Register LoadReg = LoadMI->getDstReg();
689   LLT LoadTy = MRI.getType(LoadReg);
690   Register PtrReg = LoadMI->getPointerReg();
691   uint64_t LoadSizeBits = LoadMI->getMemSizeInBits();
692   unsigned MaskSizeBits = MaskVal.countTrailingOnes();
693 
694   // The mask may not be larger than the in-memory type, as it might cover sign
695   // extended bits
696   if (MaskSizeBits > LoadSizeBits)
697     return false;
698 
699   // If the mask covers the whole destination register, there's nothing to
700   // extend
701   if (MaskSizeBits >= LoadTy.getSizeInBits())
702     return false;
703 
704   // Most targets cannot deal with loads of size < 8 and need to re-legalize to
705   // at least byte loads. Avoid creating such loads here
706   if (MaskSizeBits < 8 || !isPowerOf2_32(MaskSizeBits))
707     return false;
708 
709   const MachineMemOperand &MMO = LoadMI->getMMO();
710   LegalityQuery::MemDesc MemDesc(MMO);
711   MemDesc.MemoryTy = LLT::scalar(MaskSizeBits);
712   if (!isLegalOrBeforeLegalizer(
713           {TargetOpcode::G_ZEXTLOAD, {LoadTy, MRI.getType(PtrReg)}, {MemDesc}}))
714     return false;
715 
716   MatchInfo = [=](MachineIRBuilder &B) {
717     B.setInstrAndDebugLoc(*LoadMI);
718     auto &MF = B.getMF();
719     auto PtrInfo = MMO.getPointerInfo();
720     auto *NewMMO = MF.getMachineMemOperand(&MMO, PtrInfo, MaskSizeBits / 8);
721     B.buildLoadInstr(TargetOpcode::G_ZEXTLOAD, Dst, PtrReg, *NewMMO);
722   };
723   return true;
724 }
725 
726 bool CombinerHelper::isPredecessor(const MachineInstr &DefMI,
727                                    const MachineInstr &UseMI) {
728   assert(!DefMI.isDebugInstr() && !UseMI.isDebugInstr() &&
729          "shouldn't consider debug uses");
730   assert(DefMI.getParent() == UseMI.getParent());
731   if (&DefMI == &UseMI)
732     return true;
733   const MachineBasicBlock &MBB = *DefMI.getParent();
734   auto DefOrUse = find_if(MBB, [&DefMI, &UseMI](const MachineInstr &MI) {
735     return &MI == &DefMI || &MI == &UseMI;
736   });
737   if (DefOrUse == MBB.end())
738     llvm_unreachable("Block must contain both DefMI and UseMI!");
739   return &*DefOrUse == &DefMI;
740 }
741 
742 bool CombinerHelper::dominates(const MachineInstr &DefMI,
743                                const MachineInstr &UseMI) {
744   assert(!DefMI.isDebugInstr() && !UseMI.isDebugInstr() &&
745          "shouldn't consider debug uses");
746   if (MDT)
747     return MDT->dominates(&DefMI, &UseMI);
748   else if (DefMI.getParent() != UseMI.getParent())
749     return false;
750 
751   return isPredecessor(DefMI, UseMI);
752 }
753 
754 bool CombinerHelper::matchSextTruncSextLoad(MachineInstr &MI) {
755   assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG);
756   Register SrcReg = MI.getOperand(1).getReg();
757   Register LoadUser = SrcReg;
758 
759   if (MRI.getType(SrcReg).isVector())
760     return false;
761 
762   Register TruncSrc;
763   if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc))))
764     LoadUser = TruncSrc;
765 
766   uint64_t SizeInBits = MI.getOperand(2).getImm();
767   // If the source is a G_SEXTLOAD from the same bit width, then we don't
768   // need any extend at all, just a truncate.
769   if (auto *LoadMI = getOpcodeDef<GSExtLoad>(LoadUser, MRI)) {
770     // If truncating more than the original extended value, abort.
771     auto LoadSizeBits = LoadMI->getMemSizeInBits();
772     if (TruncSrc && MRI.getType(TruncSrc).getSizeInBits() < LoadSizeBits)
773       return false;
774     if (LoadSizeBits == SizeInBits)
775       return true;
776   }
777   return false;
778 }
779 
780 void CombinerHelper::applySextTruncSextLoad(MachineInstr &MI) {
781   assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG);
782   Builder.setInstrAndDebugLoc(MI);
783   Builder.buildCopy(MI.getOperand(0).getReg(), MI.getOperand(1).getReg());
784   MI.eraseFromParent();
785 }
786 
787 bool CombinerHelper::matchSextInRegOfLoad(
788     MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) {
789   assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG);
790 
791   // Only supports scalars for now.
792   if (MRI.getType(MI.getOperand(0).getReg()).isVector())
793     return false;
794 
795   Register SrcReg = MI.getOperand(1).getReg();
796   auto *LoadDef = getOpcodeDef<GLoad>(SrcReg, MRI);
797   if (!LoadDef || !MRI.hasOneNonDBGUse(LoadDef->getOperand(0).getReg()) ||
798       !LoadDef->isSimple())
799     return false;
800 
801   // If the sign extend extends from a narrower width than the load's width,
802   // then we can narrow the load width when we combine to a G_SEXTLOAD.
803   // Avoid widening the load at all.
804   unsigned NewSizeBits = std::min((uint64_t)MI.getOperand(2).getImm(),
805                                   LoadDef->getMemSizeInBits());
806 
807   // Don't generate G_SEXTLOADs with a < 1 byte width.
808   if (NewSizeBits < 8)
809     return false;
810   // Don't bother creating a non-power-2 sextload, it will likely be broken up
811   // anyway for most targets.
812   if (!isPowerOf2_32(NewSizeBits))
813     return false;
814 
815   const MachineMemOperand &MMO = LoadDef->getMMO();
816   LegalityQuery::MemDesc MMDesc(MMO);
817   MMDesc.MemoryTy = LLT::scalar(NewSizeBits);
818   if (!isLegalOrBeforeLegalizer({TargetOpcode::G_SEXTLOAD,
819                                  {MRI.getType(LoadDef->getDstReg()),
820                                   MRI.getType(LoadDef->getPointerReg())},
821                                  {MMDesc}}))
822     return false;
823 
824   MatchInfo = std::make_tuple(LoadDef->getDstReg(), NewSizeBits);
825   return true;
826 }
827 
828 void CombinerHelper::applySextInRegOfLoad(
829     MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) {
830   assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG);
831   Register LoadReg;
832   unsigned ScalarSizeBits;
833   std::tie(LoadReg, ScalarSizeBits) = MatchInfo;
834   GLoad *LoadDef = cast<GLoad>(MRI.getVRegDef(LoadReg));
835 
836   // If we have the following:
837   // %ld = G_LOAD %ptr, (load 2)
838   // %ext = G_SEXT_INREG %ld, 8
839   //    ==>
840   // %ld = G_SEXTLOAD %ptr (load 1)
841 
842   auto &MMO = LoadDef->getMMO();
843   Builder.setInstrAndDebugLoc(*LoadDef);
844   auto &MF = Builder.getMF();
845   auto PtrInfo = MMO.getPointerInfo();
846   auto *NewMMO = MF.getMachineMemOperand(&MMO, PtrInfo, ScalarSizeBits / 8);
847   Builder.buildLoadInstr(TargetOpcode::G_SEXTLOAD, MI.getOperand(0).getReg(),
848                          LoadDef->getPointerReg(), *NewMMO);
849   MI.eraseFromParent();
850 }
851 
852 bool CombinerHelper::findPostIndexCandidate(MachineInstr &MI, Register &Addr,
853                                             Register &Base, Register &Offset) {
854   auto &MF = *MI.getParent()->getParent();
855   const auto &TLI = *MF.getSubtarget().getTargetLowering();
856 
857 #ifndef NDEBUG
858   unsigned Opcode = MI.getOpcode();
859   assert(Opcode == TargetOpcode::G_LOAD || Opcode == TargetOpcode::G_SEXTLOAD ||
860          Opcode == TargetOpcode::G_ZEXTLOAD || Opcode == TargetOpcode::G_STORE);
861 #endif
862 
863   Base = MI.getOperand(1).getReg();
864   MachineInstr *BaseDef = MRI.getUniqueVRegDef(Base);
865   if (BaseDef && BaseDef->getOpcode() == TargetOpcode::G_FRAME_INDEX)
866     return false;
867 
868   LLVM_DEBUG(dbgs() << "Searching for post-indexing opportunity for: " << MI);
869   // FIXME: The following use traversal needs a bail out for patholigical cases.
870   for (auto &Use : MRI.use_nodbg_instructions(Base)) {
871     if (Use.getOpcode() != TargetOpcode::G_PTR_ADD)
872       continue;
873 
874     Offset = Use.getOperand(2).getReg();
875     if (!ForceLegalIndexing &&
876         !TLI.isIndexingLegal(MI, Base, Offset, /*IsPre*/ false, MRI)) {
877       LLVM_DEBUG(dbgs() << "    Ignoring candidate with illegal addrmode: "
878                         << Use);
879       continue;
880     }
881 
882     // Make sure the offset calculation is before the potentially indexed op.
883     // FIXME: we really care about dependency here. The offset calculation might
884     // be movable.
885     MachineInstr *OffsetDef = MRI.getUniqueVRegDef(Offset);
886     if (!OffsetDef || !dominates(*OffsetDef, MI)) {
887       LLVM_DEBUG(dbgs() << "    Ignoring candidate with offset after mem-op: "
888                         << Use);
889       continue;
890     }
891 
892     // FIXME: check whether all uses of Base are load/store with foldable
893     // addressing modes. If so, using the normal addr-modes is better than
894     // forming an indexed one.
895 
896     bool MemOpDominatesAddrUses = true;
897     for (auto &PtrAddUse :
898          MRI.use_nodbg_instructions(Use.getOperand(0).getReg())) {
899       if (!dominates(MI, PtrAddUse)) {
900         MemOpDominatesAddrUses = false;
901         break;
902       }
903     }
904 
905     if (!MemOpDominatesAddrUses) {
906       LLVM_DEBUG(
907           dbgs() << "    Ignoring candidate as memop does not dominate uses: "
908                  << Use);
909       continue;
910     }
911 
912     LLVM_DEBUG(dbgs() << "    Found match: " << Use);
913     Addr = Use.getOperand(0).getReg();
914     return true;
915   }
916 
917   return false;
918 }
919 
920 bool CombinerHelper::findPreIndexCandidate(MachineInstr &MI, Register &Addr,
921                                            Register &Base, Register &Offset) {
922   auto &MF = *MI.getParent()->getParent();
923   const auto &TLI = *MF.getSubtarget().getTargetLowering();
924 
925 #ifndef NDEBUG
926   unsigned Opcode = MI.getOpcode();
927   assert(Opcode == TargetOpcode::G_LOAD || Opcode == TargetOpcode::G_SEXTLOAD ||
928          Opcode == TargetOpcode::G_ZEXTLOAD || Opcode == TargetOpcode::G_STORE);
929 #endif
930 
931   Addr = MI.getOperand(1).getReg();
932   MachineInstr *AddrDef = getOpcodeDef(TargetOpcode::G_PTR_ADD, Addr, MRI);
933   if (!AddrDef || MRI.hasOneNonDBGUse(Addr))
934     return false;
935 
936   Base = AddrDef->getOperand(1).getReg();
937   Offset = AddrDef->getOperand(2).getReg();
938 
939   LLVM_DEBUG(dbgs() << "Found potential pre-indexed load_store: " << MI);
940 
941   if (!ForceLegalIndexing &&
942       !TLI.isIndexingLegal(MI, Base, Offset, /*IsPre*/ true, MRI)) {
943     LLVM_DEBUG(dbgs() << "    Skipping, not legal for target");
944     return false;
945   }
946 
947   MachineInstr *BaseDef = getDefIgnoringCopies(Base, MRI);
948   if (BaseDef->getOpcode() == TargetOpcode::G_FRAME_INDEX) {
949     LLVM_DEBUG(dbgs() << "    Skipping, frame index would need copy anyway.");
950     return false;
951   }
952 
953   if (MI.getOpcode() == TargetOpcode::G_STORE) {
954     // Would require a copy.
955     if (Base == MI.getOperand(0).getReg()) {
956       LLVM_DEBUG(dbgs() << "    Skipping, storing base so need copy anyway.");
957       return false;
958     }
959 
960     // We're expecting one use of Addr in MI, but it could also be the
961     // value stored, which isn't actually dominated by the instruction.
962     if (MI.getOperand(0).getReg() == Addr) {
963       LLVM_DEBUG(dbgs() << "    Skipping, does not dominate all addr uses");
964       return false;
965     }
966   }
967 
968   // FIXME: check whether all uses of the base pointer are constant PtrAdds.
969   // That might allow us to end base's liveness here by adjusting the constant.
970 
971   for (auto &UseMI : MRI.use_nodbg_instructions(Addr)) {
972     if (!dominates(MI, UseMI)) {
973       LLVM_DEBUG(dbgs() << "    Skipping, does not dominate all addr uses.");
974       return false;
975     }
976   }
977 
978   return true;
979 }
980 
981 bool CombinerHelper::tryCombineIndexedLoadStore(MachineInstr &MI) {
982   IndexedLoadStoreMatchInfo MatchInfo;
983   if (matchCombineIndexedLoadStore(MI, MatchInfo)) {
984     applyCombineIndexedLoadStore(MI, MatchInfo);
985     return true;
986   }
987   return false;
988 }
989 
990 bool CombinerHelper::matchCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo) {
991   unsigned Opcode = MI.getOpcode();
992   if (Opcode != TargetOpcode::G_LOAD && Opcode != TargetOpcode::G_SEXTLOAD &&
993       Opcode != TargetOpcode::G_ZEXTLOAD && Opcode != TargetOpcode::G_STORE)
994     return false;
995 
996   // For now, no targets actually support these opcodes so don't waste time
997   // running these unless we're forced to for testing.
998   if (!ForceLegalIndexing)
999     return false;
1000 
1001   MatchInfo.IsPre = findPreIndexCandidate(MI, MatchInfo.Addr, MatchInfo.Base,
1002                                           MatchInfo.Offset);
1003   if (!MatchInfo.IsPre &&
1004       !findPostIndexCandidate(MI, MatchInfo.Addr, MatchInfo.Base,
1005                               MatchInfo.Offset))
1006     return false;
1007 
1008   return true;
1009 }
1010 
1011 void CombinerHelper::applyCombineIndexedLoadStore(
1012     MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo) {
1013   MachineInstr &AddrDef = *MRI.getUniqueVRegDef(MatchInfo.Addr);
1014   MachineIRBuilder MIRBuilder(MI);
1015   unsigned Opcode = MI.getOpcode();
1016   bool IsStore = Opcode == TargetOpcode::G_STORE;
1017   unsigned NewOpcode;
1018   switch (Opcode) {
1019   case TargetOpcode::G_LOAD:
1020     NewOpcode = TargetOpcode::G_INDEXED_LOAD;
1021     break;
1022   case TargetOpcode::G_SEXTLOAD:
1023     NewOpcode = TargetOpcode::G_INDEXED_SEXTLOAD;
1024     break;
1025   case TargetOpcode::G_ZEXTLOAD:
1026     NewOpcode = TargetOpcode::G_INDEXED_ZEXTLOAD;
1027     break;
1028   case TargetOpcode::G_STORE:
1029     NewOpcode = TargetOpcode::G_INDEXED_STORE;
1030     break;
1031   default:
1032     llvm_unreachable("Unknown load/store opcode");
1033   }
1034 
1035   auto MIB = MIRBuilder.buildInstr(NewOpcode);
1036   if (IsStore) {
1037     MIB.addDef(MatchInfo.Addr);
1038     MIB.addUse(MI.getOperand(0).getReg());
1039   } else {
1040     MIB.addDef(MI.getOperand(0).getReg());
1041     MIB.addDef(MatchInfo.Addr);
1042   }
1043 
1044   MIB.addUse(MatchInfo.Base);
1045   MIB.addUse(MatchInfo.Offset);
1046   MIB.addImm(MatchInfo.IsPre);
1047   MI.eraseFromParent();
1048   AddrDef.eraseFromParent();
1049 
1050   LLVM_DEBUG(dbgs() << "    Combinined to indexed operation");
1051 }
1052 
1053 bool CombinerHelper::matchCombineDivRem(MachineInstr &MI,
1054                                         MachineInstr *&OtherMI) {
1055   unsigned Opcode = MI.getOpcode();
1056   bool IsDiv, IsSigned;
1057 
1058   switch (Opcode) {
1059   default:
1060     llvm_unreachable("Unexpected opcode!");
1061   case TargetOpcode::G_SDIV:
1062   case TargetOpcode::G_UDIV: {
1063     IsDiv = true;
1064     IsSigned = Opcode == TargetOpcode::G_SDIV;
1065     break;
1066   }
1067   case TargetOpcode::G_SREM:
1068   case TargetOpcode::G_UREM: {
1069     IsDiv = false;
1070     IsSigned = Opcode == TargetOpcode::G_SREM;
1071     break;
1072   }
1073   }
1074 
1075   Register Src1 = MI.getOperand(1).getReg();
1076   unsigned DivOpcode, RemOpcode, DivremOpcode;
1077   if (IsSigned) {
1078     DivOpcode = TargetOpcode::G_SDIV;
1079     RemOpcode = TargetOpcode::G_SREM;
1080     DivremOpcode = TargetOpcode::G_SDIVREM;
1081   } else {
1082     DivOpcode = TargetOpcode::G_UDIV;
1083     RemOpcode = TargetOpcode::G_UREM;
1084     DivremOpcode = TargetOpcode::G_UDIVREM;
1085   }
1086 
1087   if (!isLegalOrBeforeLegalizer({DivremOpcode, {MRI.getType(Src1)}}))
1088     return false;
1089 
1090   // Combine:
1091   //   %div:_ = G_[SU]DIV %src1:_, %src2:_
1092   //   %rem:_ = G_[SU]REM %src1:_, %src2:_
1093   // into:
1094   //  %div:_, %rem:_ = G_[SU]DIVREM %src1:_, %src2:_
1095 
1096   // Combine:
1097   //   %rem:_ = G_[SU]REM %src1:_, %src2:_
1098   //   %div:_ = G_[SU]DIV %src1:_, %src2:_
1099   // into:
1100   //  %div:_, %rem:_ = G_[SU]DIVREM %src1:_, %src2:_
1101 
1102   for (auto &UseMI : MRI.use_nodbg_instructions(Src1)) {
1103     if (MI.getParent() == UseMI.getParent() &&
1104         ((IsDiv && UseMI.getOpcode() == RemOpcode) ||
1105          (!IsDiv && UseMI.getOpcode() == DivOpcode)) &&
1106         matchEqualDefs(MI.getOperand(2), UseMI.getOperand(2))) {
1107       OtherMI = &UseMI;
1108       return true;
1109     }
1110   }
1111 
1112   return false;
1113 }
1114 
1115 void CombinerHelper::applyCombineDivRem(MachineInstr &MI,
1116                                         MachineInstr *&OtherMI) {
1117   unsigned Opcode = MI.getOpcode();
1118   assert(OtherMI && "OtherMI shouldn't be empty.");
1119 
1120   Register DestDivReg, DestRemReg;
1121   if (Opcode == TargetOpcode::G_SDIV || Opcode == TargetOpcode::G_UDIV) {
1122     DestDivReg = MI.getOperand(0).getReg();
1123     DestRemReg = OtherMI->getOperand(0).getReg();
1124   } else {
1125     DestDivReg = OtherMI->getOperand(0).getReg();
1126     DestRemReg = MI.getOperand(0).getReg();
1127   }
1128 
1129   bool IsSigned =
1130       Opcode == TargetOpcode::G_SDIV || Opcode == TargetOpcode::G_SREM;
1131 
1132   // Check which instruction is first in the block so we don't break def-use
1133   // deps by "moving" the instruction incorrectly.
1134   if (dominates(MI, *OtherMI))
1135     Builder.setInstrAndDebugLoc(MI);
1136   else
1137     Builder.setInstrAndDebugLoc(*OtherMI);
1138 
1139   Builder.buildInstr(IsSigned ? TargetOpcode::G_SDIVREM
1140                               : TargetOpcode::G_UDIVREM,
1141                      {DestDivReg, DestRemReg},
1142                      {MI.getOperand(1).getReg(), MI.getOperand(2).getReg()});
1143   MI.eraseFromParent();
1144   OtherMI->eraseFromParent();
1145 }
1146 
1147 bool CombinerHelper::matchOptBrCondByInvertingCond(MachineInstr &MI,
1148                                                    MachineInstr *&BrCond) {
1149   assert(MI.getOpcode() == TargetOpcode::G_BR);
1150 
1151   // Try to match the following:
1152   // bb1:
1153   //   G_BRCOND %c1, %bb2
1154   //   G_BR %bb3
1155   // bb2:
1156   // ...
1157   // bb3:
1158 
1159   // The above pattern does not have a fall through to the successor bb2, always
1160   // resulting in a branch no matter which path is taken. Here we try to find
1161   // and replace that pattern with conditional branch to bb3 and otherwise
1162   // fallthrough to bb2. This is generally better for branch predictors.
1163 
1164   MachineBasicBlock *MBB = MI.getParent();
1165   MachineBasicBlock::iterator BrIt(MI);
1166   if (BrIt == MBB->begin())
1167     return false;
1168   assert(std::next(BrIt) == MBB->end() && "expected G_BR to be a terminator");
1169 
1170   BrCond = &*std::prev(BrIt);
1171   if (BrCond->getOpcode() != TargetOpcode::G_BRCOND)
1172     return false;
1173 
1174   // Check that the next block is the conditional branch target. Also make sure
1175   // that it isn't the same as the G_BR's target (otherwise, this will loop.)
1176   MachineBasicBlock *BrCondTarget = BrCond->getOperand(1).getMBB();
1177   return BrCondTarget != MI.getOperand(0).getMBB() &&
1178          MBB->isLayoutSuccessor(BrCondTarget);
1179 }
1180 
1181 void CombinerHelper::applyOptBrCondByInvertingCond(MachineInstr &MI,
1182                                                    MachineInstr *&BrCond) {
1183   MachineBasicBlock *BrTarget = MI.getOperand(0).getMBB();
1184   Builder.setInstrAndDebugLoc(*BrCond);
1185   LLT Ty = MRI.getType(BrCond->getOperand(0).getReg());
1186   // FIXME: Does int/fp matter for this? If so, we might need to restrict
1187   // this to i1 only since we might not know for sure what kind of
1188   // compare generated the condition value.
1189   auto True = Builder.buildConstant(
1190       Ty, getICmpTrueVal(getTargetLowering(), false, false));
1191   auto Xor = Builder.buildXor(Ty, BrCond->getOperand(0), True);
1192 
1193   auto *FallthroughBB = BrCond->getOperand(1).getMBB();
1194   Observer.changingInstr(MI);
1195   MI.getOperand(0).setMBB(FallthroughBB);
1196   Observer.changedInstr(MI);
1197 
1198   // Change the conditional branch to use the inverted condition and
1199   // new target block.
1200   Observer.changingInstr(*BrCond);
1201   BrCond->getOperand(0).setReg(Xor.getReg(0));
1202   BrCond->getOperand(1).setMBB(BrTarget);
1203   Observer.changedInstr(*BrCond);
1204 }
1205 
1206 static Type *getTypeForLLT(LLT Ty, LLVMContext &C) {
1207   if (Ty.isVector())
1208     return FixedVectorType::get(IntegerType::get(C, Ty.getScalarSizeInBits()),
1209                                 Ty.getNumElements());
1210   return IntegerType::get(C, Ty.getSizeInBits());
1211 }
1212 
1213 bool CombinerHelper::tryEmitMemcpyInline(MachineInstr &MI) {
1214   MachineIRBuilder HelperBuilder(MI);
1215   GISelObserverWrapper DummyObserver;
1216   LegalizerHelper Helper(HelperBuilder.getMF(), DummyObserver, HelperBuilder);
1217   return Helper.lowerMemcpyInline(MI) ==
1218          LegalizerHelper::LegalizeResult::Legalized;
1219 }
1220 
1221 bool CombinerHelper::tryCombineMemCpyFamily(MachineInstr &MI, unsigned MaxLen) {
1222   MachineIRBuilder HelperBuilder(MI);
1223   GISelObserverWrapper DummyObserver;
1224   LegalizerHelper Helper(HelperBuilder.getMF(), DummyObserver, HelperBuilder);
1225   return Helper.lowerMemCpyFamily(MI, MaxLen) ==
1226          LegalizerHelper::LegalizeResult::Legalized;
1227 }
1228 
1229 static Optional<APFloat> constantFoldFpUnary(unsigned Opcode, LLT DstTy,
1230                                              const Register Op,
1231                                              const MachineRegisterInfo &MRI) {
1232   const ConstantFP *MaybeCst = getConstantFPVRegVal(Op, MRI);
1233   if (!MaybeCst)
1234     return None;
1235 
1236   APFloat V = MaybeCst->getValueAPF();
1237   switch (Opcode) {
1238   default:
1239     llvm_unreachable("Unexpected opcode!");
1240   case TargetOpcode::G_FNEG: {
1241     V.changeSign();
1242     return V;
1243   }
1244   case TargetOpcode::G_FABS: {
1245     V.clearSign();
1246     return V;
1247   }
1248   case TargetOpcode::G_FPTRUNC:
1249     break;
1250   case TargetOpcode::G_FSQRT: {
1251     bool Unused;
1252     V.convert(APFloat::IEEEdouble(), APFloat::rmNearestTiesToEven, &Unused);
1253     V = APFloat(sqrt(V.convertToDouble()));
1254     break;
1255   }
1256   case TargetOpcode::G_FLOG2: {
1257     bool Unused;
1258     V.convert(APFloat::IEEEdouble(), APFloat::rmNearestTiesToEven, &Unused);
1259     V = APFloat(log2(V.convertToDouble()));
1260     break;
1261   }
1262   }
1263   // Convert `APFloat` to appropriate IEEE type depending on `DstTy`. Otherwise,
1264   // `buildFConstant` will assert on size mismatch. Only `G_FPTRUNC`, `G_FSQRT`,
1265   // and `G_FLOG2` reach here.
1266   bool Unused;
1267   V.convert(getFltSemanticForLLT(DstTy), APFloat::rmNearestTiesToEven, &Unused);
1268   return V;
1269 }
1270 
1271 bool CombinerHelper::matchCombineConstantFoldFpUnary(MachineInstr &MI,
1272                                                      Optional<APFloat> &Cst) {
1273   Register DstReg = MI.getOperand(0).getReg();
1274   Register SrcReg = MI.getOperand(1).getReg();
1275   LLT DstTy = MRI.getType(DstReg);
1276   Cst = constantFoldFpUnary(MI.getOpcode(), DstTy, SrcReg, MRI);
1277   return Cst.hasValue();
1278 }
1279 
1280 void CombinerHelper::applyCombineConstantFoldFpUnary(MachineInstr &MI,
1281                                                      Optional<APFloat> &Cst) {
1282   assert(Cst.hasValue() && "Optional is unexpectedly empty!");
1283   Builder.setInstrAndDebugLoc(MI);
1284   MachineFunction &MF = Builder.getMF();
1285   auto *FPVal = ConstantFP::get(MF.getFunction().getContext(), *Cst);
1286   Register DstReg = MI.getOperand(0).getReg();
1287   Builder.buildFConstant(DstReg, *FPVal);
1288   MI.eraseFromParent();
1289 }
1290 
1291 bool CombinerHelper::matchPtrAddImmedChain(MachineInstr &MI,
1292                                            PtrAddChain &MatchInfo) {
1293   // We're trying to match the following pattern:
1294   //   %t1 = G_PTR_ADD %base, G_CONSTANT imm1
1295   //   %root = G_PTR_ADD %t1, G_CONSTANT imm2
1296   // -->
1297   //   %root = G_PTR_ADD %base, G_CONSTANT (imm1 + imm2)
1298 
1299   if (MI.getOpcode() != TargetOpcode::G_PTR_ADD)
1300     return false;
1301 
1302   Register Add2 = MI.getOperand(1).getReg();
1303   Register Imm1 = MI.getOperand(2).getReg();
1304   auto MaybeImmVal = getIConstantVRegValWithLookThrough(Imm1, MRI);
1305   if (!MaybeImmVal)
1306     return false;
1307 
1308   MachineInstr *Add2Def = MRI.getVRegDef(Add2);
1309   if (!Add2Def || Add2Def->getOpcode() != TargetOpcode::G_PTR_ADD)
1310     return false;
1311 
1312   Register Base = Add2Def->getOperand(1).getReg();
1313   Register Imm2 = Add2Def->getOperand(2).getReg();
1314   auto MaybeImm2Val = getIConstantVRegValWithLookThrough(Imm2, MRI);
1315   if (!MaybeImm2Val)
1316     return false;
1317 
1318   // Check if the new combined immediate forms an illegal addressing mode.
1319   // Do not combine if it was legal before but would get illegal.
1320   // To do so, we need to find a load/store user of the pointer to get
1321   // the access type.
1322   Type *AccessTy = nullptr;
1323   auto &MF = *MI.getMF();
1324   for (auto &UseMI : MRI.use_nodbg_instructions(MI.getOperand(0).getReg())) {
1325     if (auto *LdSt = dyn_cast<GLoadStore>(&UseMI)) {
1326       AccessTy = getTypeForLLT(MRI.getType(LdSt->getReg(0)),
1327                                MF.getFunction().getContext());
1328       break;
1329     }
1330   }
1331   TargetLoweringBase::AddrMode AMNew;
1332   APInt CombinedImm = MaybeImmVal->Value + MaybeImm2Val->Value;
1333   AMNew.BaseOffs = CombinedImm.getSExtValue();
1334   if (AccessTy) {
1335     AMNew.HasBaseReg = true;
1336     TargetLoweringBase::AddrMode AMOld;
1337     AMOld.BaseOffs = MaybeImm2Val->Value.getSExtValue();
1338     AMOld.HasBaseReg = true;
1339     unsigned AS = MRI.getType(Add2).getAddressSpace();
1340     const auto &TLI = *MF.getSubtarget().getTargetLowering();
1341     if (TLI.isLegalAddressingMode(MF.getDataLayout(), AMOld, AccessTy, AS) &&
1342         !TLI.isLegalAddressingMode(MF.getDataLayout(), AMNew, AccessTy, AS))
1343       return false;
1344   }
1345 
1346   // Pass the combined immediate to the apply function.
1347   MatchInfo.Imm = AMNew.BaseOffs;
1348   MatchInfo.Base = Base;
1349   MatchInfo.Bank = getRegBank(Imm2);
1350   return true;
1351 }
1352 
1353 void CombinerHelper::applyPtrAddImmedChain(MachineInstr &MI,
1354                                            PtrAddChain &MatchInfo) {
1355   assert(MI.getOpcode() == TargetOpcode::G_PTR_ADD && "Expected G_PTR_ADD");
1356   MachineIRBuilder MIB(MI);
1357   LLT OffsetTy = MRI.getType(MI.getOperand(2).getReg());
1358   auto NewOffset = MIB.buildConstant(OffsetTy, MatchInfo.Imm);
1359   setRegBank(NewOffset.getReg(0), MatchInfo.Bank);
1360   Observer.changingInstr(MI);
1361   MI.getOperand(1).setReg(MatchInfo.Base);
1362   MI.getOperand(2).setReg(NewOffset.getReg(0));
1363   Observer.changedInstr(MI);
1364 }
1365 
1366 bool CombinerHelper::matchShiftImmedChain(MachineInstr &MI,
1367                                           RegisterImmPair &MatchInfo) {
1368   // We're trying to match the following pattern with any of
1369   // G_SHL/G_ASHR/G_LSHR/G_SSHLSAT/G_USHLSAT shift instructions:
1370   //   %t1 = SHIFT %base, G_CONSTANT imm1
1371   //   %root = SHIFT %t1, G_CONSTANT imm2
1372   // -->
1373   //   %root = SHIFT %base, G_CONSTANT (imm1 + imm2)
1374 
1375   unsigned Opcode = MI.getOpcode();
1376   assert((Opcode == TargetOpcode::G_SHL || Opcode == TargetOpcode::G_ASHR ||
1377           Opcode == TargetOpcode::G_LSHR || Opcode == TargetOpcode::G_SSHLSAT ||
1378           Opcode == TargetOpcode::G_USHLSAT) &&
1379          "Expected G_SHL, G_ASHR, G_LSHR, G_SSHLSAT or G_USHLSAT");
1380 
1381   Register Shl2 = MI.getOperand(1).getReg();
1382   Register Imm1 = MI.getOperand(2).getReg();
1383   auto MaybeImmVal = getIConstantVRegValWithLookThrough(Imm1, MRI);
1384   if (!MaybeImmVal)
1385     return false;
1386 
1387   MachineInstr *Shl2Def = MRI.getUniqueVRegDef(Shl2);
1388   if (Shl2Def->getOpcode() != Opcode)
1389     return false;
1390 
1391   Register Base = Shl2Def->getOperand(1).getReg();
1392   Register Imm2 = Shl2Def->getOperand(2).getReg();
1393   auto MaybeImm2Val = getIConstantVRegValWithLookThrough(Imm2, MRI);
1394   if (!MaybeImm2Val)
1395     return false;
1396 
1397   // Pass the combined immediate to the apply function.
1398   MatchInfo.Imm =
1399       (MaybeImmVal->Value.getSExtValue() + MaybeImm2Val->Value).getSExtValue();
1400   MatchInfo.Reg = Base;
1401 
1402   // There is no simple replacement for a saturating unsigned left shift that
1403   // exceeds the scalar size.
1404   if (Opcode == TargetOpcode::G_USHLSAT &&
1405       MatchInfo.Imm >= MRI.getType(Shl2).getScalarSizeInBits())
1406     return false;
1407 
1408   return true;
1409 }
1410 
1411 void CombinerHelper::applyShiftImmedChain(MachineInstr &MI,
1412                                           RegisterImmPair &MatchInfo) {
1413   unsigned Opcode = MI.getOpcode();
1414   assert((Opcode == TargetOpcode::G_SHL || Opcode == TargetOpcode::G_ASHR ||
1415           Opcode == TargetOpcode::G_LSHR || Opcode == TargetOpcode::G_SSHLSAT ||
1416           Opcode == TargetOpcode::G_USHLSAT) &&
1417          "Expected G_SHL, G_ASHR, G_LSHR, G_SSHLSAT or G_USHLSAT");
1418 
1419   Builder.setInstrAndDebugLoc(MI);
1420   LLT Ty = MRI.getType(MI.getOperand(1).getReg());
1421   unsigned const ScalarSizeInBits = Ty.getScalarSizeInBits();
1422   auto Imm = MatchInfo.Imm;
1423 
1424   if (Imm >= ScalarSizeInBits) {
1425     // Any logical shift that exceeds scalar size will produce zero.
1426     if (Opcode == TargetOpcode::G_SHL || Opcode == TargetOpcode::G_LSHR) {
1427       Builder.buildConstant(MI.getOperand(0), 0);
1428       MI.eraseFromParent();
1429       return;
1430     }
1431     // Arithmetic shift and saturating signed left shift have no effect beyond
1432     // scalar size.
1433     Imm = ScalarSizeInBits - 1;
1434   }
1435 
1436   LLT ImmTy = MRI.getType(MI.getOperand(2).getReg());
1437   Register NewImm = Builder.buildConstant(ImmTy, Imm).getReg(0);
1438   Observer.changingInstr(MI);
1439   MI.getOperand(1).setReg(MatchInfo.Reg);
1440   MI.getOperand(2).setReg(NewImm);
1441   Observer.changedInstr(MI);
1442 }
1443 
1444 bool CombinerHelper::matchShiftOfShiftedLogic(MachineInstr &MI,
1445                                               ShiftOfShiftedLogic &MatchInfo) {
1446   // We're trying to match the following pattern with any of
1447   // G_SHL/G_ASHR/G_LSHR/G_USHLSAT/G_SSHLSAT shift instructions in combination
1448   // with any of G_AND/G_OR/G_XOR logic instructions.
1449   //   %t1 = SHIFT %X, G_CONSTANT C0
1450   //   %t2 = LOGIC %t1, %Y
1451   //   %root = SHIFT %t2, G_CONSTANT C1
1452   // -->
1453   //   %t3 = SHIFT %X, G_CONSTANT (C0+C1)
1454   //   %t4 = SHIFT %Y, G_CONSTANT C1
1455   //   %root = LOGIC %t3, %t4
1456   unsigned ShiftOpcode = MI.getOpcode();
1457   assert((ShiftOpcode == TargetOpcode::G_SHL ||
1458           ShiftOpcode == TargetOpcode::G_ASHR ||
1459           ShiftOpcode == TargetOpcode::G_LSHR ||
1460           ShiftOpcode == TargetOpcode::G_USHLSAT ||
1461           ShiftOpcode == TargetOpcode::G_SSHLSAT) &&
1462          "Expected G_SHL, G_ASHR, G_LSHR, G_USHLSAT and G_SSHLSAT");
1463 
1464   // Match a one-use bitwise logic op.
1465   Register LogicDest = MI.getOperand(1).getReg();
1466   if (!MRI.hasOneNonDBGUse(LogicDest))
1467     return false;
1468 
1469   MachineInstr *LogicMI = MRI.getUniqueVRegDef(LogicDest);
1470   unsigned LogicOpcode = LogicMI->getOpcode();
1471   if (LogicOpcode != TargetOpcode::G_AND && LogicOpcode != TargetOpcode::G_OR &&
1472       LogicOpcode != TargetOpcode::G_XOR)
1473     return false;
1474 
1475   // Find a matching one-use shift by constant.
1476   const Register C1 = MI.getOperand(2).getReg();
1477   auto MaybeImmVal = getIConstantVRegValWithLookThrough(C1, MRI);
1478   if (!MaybeImmVal)
1479     return false;
1480 
1481   const uint64_t C1Val = MaybeImmVal->Value.getZExtValue();
1482 
1483   auto matchFirstShift = [&](const MachineInstr *MI, uint64_t &ShiftVal) {
1484     // Shift should match previous one and should be a one-use.
1485     if (MI->getOpcode() != ShiftOpcode ||
1486         !MRI.hasOneNonDBGUse(MI->getOperand(0).getReg()))
1487       return false;
1488 
1489     // Must be a constant.
1490     auto MaybeImmVal =
1491         getIConstantVRegValWithLookThrough(MI->getOperand(2).getReg(), MRI);
1492     if (!MaybeImmVal)
1493       return false;
1494 
1495     ShiftVal = MaybeImmVal->Value.getSExtValue();
1496     return true;
1497   };
1498 
1499   // Logic ops are commutative, so check each operand for a match.
1500   Register LogicMIReg1 = LogicMI->getOperand(1).getReg();
1501   MachineInstr *LogicMIOp1 = MRI.getUniqueVRegDef(LogicMIReg1);
1502   Register LogicMIReg2 = LogicMI->getOperand(2).getReg();
1503   MachineInstr *LogicMIOp2 = MRI.getUniqueVRegDef(LogicMIReg2);
1504   uint64_t C0Val;
1505 
1506   if (matchFirstShift(LogicMIOp1, C0Val)) {
1507     MatchInfo.LogicNonShiftReg = LogicMIReg2;
1508     MatchInfo.Shift2 = LogicMIOp1;
1509   } else if (matchFirstShift(LogicMIOp2, C0Val)) {
1510     MatchInfo.LogicNonShiftReg = LogicMIReg1;
1511     MatchInfo.Shift2 = LogicMIOp2;
1512   } else
1513     return false;
1514 
1515   MatchInfo.ValSum = C0Val + C1Val;
1516 
1517   // The fold is not valid if the sum of the shift values exceeds bitwidth.
1518   if (MatchInfo.ValSum >= MRI.getType(LogicDest).getScalarSizeInBits())
1519     return false;
1520 
1521   MatchInfo.Logic = LogicMI;
1522   return true;
1523 }
1524 
1525 void CombinerHelper::applyShiftOfShiftedLogic(MachineInstr &MI,
1526                                               ShiftOfShiftedLogic &MatchInfo) {
1527   unsigned Opcode = MI.getOpcode();
1528   assert((Opcode == TargetOpcode::G_SHL || Opcode == TargetOpcode::G_ASHR ||
1529           Opcode == TargetOpcode::G_LSHR || Opcode == TargetOpcode::G_USHLSAT ||
1530           Opcode == TargetOpcode::G_SSHLSAT) &&
1531          "Expected G_SHL, G_ASHR, G_LSHR, G_USHLSAT and G_SSHLSAT");
1532 
1533   LLT ShlType = MRI.getType(MI.getOperand(2).getReg());
1534   LLT DestType = MRI.getType(MI.getOperand(0).getReg());
1535   Builder.setInstrAndDebugLoc(MI);
1536 
1537   Register Const = Builder.buildConstant(ShlType, MatchInfo.ValSum).getReg(0);
1538 
1539   Register Shift1Base = MatchInfo.Shift2->getOperand(1).getReg();
1540   Register Shift1 =
1541       Builder.buildInstr(Opcode, {DestType}, {Shift1Base, Const}).getReg(0);
1542 
1543   Register Shift2Const = MI.getOperand(2).getReg();
1544   Register Shift2 = Builder
1545                         .buildInstr(Opcode, {DestType},
1546                                     {MatchInfo.LogicNonShiftReg, Shift2Const})
1547                         .getReg(0);
1548 
1549   Register Dest = MI.getOperand(0).getReg();
1550   Builder.buildInstr(MatchInfo.Logic->getOpcode(), {Dest}, {Shift1, Shift2});
1551 
1552   // These were one use so it's safe to remove them.
1553   MatchInfo.Shift2->eraseFromParentAndMarkDBGValuesForRemoval();
1554   MatchInfo.Logic->eraseFromParentAndMarkDBGValuesForRemoval();
1555 
1556   MI.eraseFromParent();
1557 }
1558 
1559 bool CombinerHelper::matchCombineMulToShl(MachineInstr &MI,
1560                                           unsigned &ShiftVal) {
1561   assert(MI.getOpcode() == TargetOpcode::G_MUL && "Expected a G_MUL");
1562   auto MaybeImmVal =
1563       getIConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI);
1564   if (!MaybeImmVal)
1565     return false;
1566 
1567   ShiftVal = MaybeImmVal->Value.exactLogBase2();
1568   return (static_cast<int32_t>(ShiftVal) != -1);
1569 }
1570 
1571 void CombinerHelper::applyCombineMulToShl(MachineInstr &MI,
1572                                           unsigned &ShiftVal) {
1573   assert(MI.getOpcode() == TargetOpcode::G_MUL && "Expected a G_MUL");
1574   MachineIRBuilder MIB(MI);
1575   LLT ShiftTy = MRI.getType(MI.getOperand(0).getReg());
1576   auto ShiftCst = MIB.buildConstant(ShiftTy, ShiftVal);
1577   Observer.changingInstr(MI);
1578   MI.setDesc(MIB.getTII().get(TargetOpcode::G_SHL));
1579   MI.getOperand(2).setReg(ShiftCst.getReg(0));
1580   Observer.changedInstr(MI);
1581 }
1582 
1583 // shl ([sza]ext x), y => zext (shl x, y), if shift does not overflow source
1584 bool CombinerHelper::matchCombineShlOfExtend(MachineInstr &MI,
1585                                              RegisterImmPair &MatchData) {
1586   assert(MI.getOpcode() == TargetOpcode::G_SHL && KB);
1587 
1588   Register LHS = MI.getOperand(1).getReg();
1589 
1590   Register ExtSrc;
1591   if (!mi_match(LHS, MRI, m_GAnyExt(m_Reg(ExtSrc))) &&
1592       !mi_match(LHS, MRI, m_GZExt(m_Reg(ExtSrc))) &&
1593       !mi_match(LHS, MRI, m_GSExt(m_Reg(ExtSrc))))
1594     return false;
1595 
1596   // TODO: Should handle vector splat.
1597   Register RHS = MI.getOperand(2).getReg();
1598   auto MaybeShiftAmtVal = getIConstantVRegValWithLookThrough(RHS, MRI);
1599   if (!MaybeShiftAmtVal)
1600     return false;
1601 
1602   if (LI) {
1603     LLT SrcTy = MRI.getType(ExtSrc);
1604 
1605     // We only really care about the legality with the shifted value. We can
1606     // pick any type the constant shift amount, so ask the target what to
1607     // use. Otherwise we would have to guess and hope it is reported as legal.
1608     LLT ShiftAmtTy = getTargetLowering().getPreferredShiftAmountTy(SrcTy);
1609     if (!isLegalOrBeforeLegalizer({TargetOpcode::G_SHL, {SrcTy, ShiftAmtTy}}))
1610       return false;
1611   }
1612 
1613   int64_t ShiftAmt = MaybeShiftAmtVal->Value.getSExtValue();
1614   MatchData.Reg = ExtSrc;
1615   MatchData.Imm = ShiftAmt;
1616 
1617   unsigned MinLeadingZeros = KB->getKnownZeroes(ExtSrc).countLeadingOnes();
1618   return MinLeadingZeros >= ShiftAmt;
1619 }
1620 
1621 void CombinerHelper::applyCombineShlOfExtend(MachineInstr &MI,
1622                                              const RegisterImmPair &MatchData) {
1623   Register ExtSrcReg = MatchData.Reg;
1624   int64_t ShiftAmtVal = MatchData.Imm;
1625 
1626   LLT ExtSrcTy = MRI.getType(ExtSrcReg);
1627   Builder.setInstrAndDebugLoc(MI);
1628   auto ShiftAmt = Builder.buildConstant(ExtSrcTy, ShiftAmtVal);
1629   auto NarrowShift =
1630       Builder.buildShl(ExtSrcTy, ExtSrcReg, ShiftAmt, MI.getFlags());
1631   Builder.buildZExt(MI.getOperand(0), NarrowShift);
1632   MI.eraseFromParent();
1633 }
1634 
1635 bool CombinerHelper::matchCombineMergeUnmerge(MachineInstr &MI,
1636                                               Register &MatchInfo) {
1637   GMerge &Merge = cast<GMerge>(MI);
1638   SmallVector<Register, 16> MergedValues;
1639   for (unsigned I = 0; I < Merge.getNumSources(); ++I)
1640     MergedValues.emplace_back(Merge.getSourceReg(I));
1641 
1642   auto *Unmerge = getOpcodeDef<GUnmerge>(MergedValues[0], MRI);
1643   if (!Unmerge || Unmerge->getNumDefs() != Merge.getNumSources())
1644     return false;
1645 
1646   for (unsigned I = 0; I < MergedValues.size(); ++I)
1647     if (MergedValues[I] != Unmerge->getReg(I))
1648       return false;
1649 
1650   MatchInfo = Unmerge->getSourceReg();
1651   return true;
1652 }
1653 
1654 static Register peekThroughBitcast(Register Reg,
1655                                    const MachineRegisterInfo &MRI) {
1656   while (mi_match(Reg, MRI, m_GBitcast(m_Reg(Reg))))
1657     ;
1658 
1659   return Reg;
1660 }
1661 
1662 bool CombinerHelper::matchCombineUnmergeMergeToPlainValues(
1663     MachineInstr &MI, SmallVectorImpl<Register> &Operands) {
1664   assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES &&
1665          "Expected an unmerge");
1666   auto &Unmerge = cast<GUnmerge>(MI);
1667   Register SrcReg = peekThroughBitcast(Unmerge.getSourceReg(), MRI);
1668 
1669   auto *SrcInstr = getOpcodeDef<GMergeLikeOp>(SrcReg, MRI);
1670   if (!SrcInstr)
1671     return false;
1672 
1673   // Check the source type of the merge.
1674   LLT SrcMergeTy = MRI.getType(SrcInstr->getSourceReg(0));
1675   LLT Dst0Ty = MRI.getType(Unmerge.getReg(0));
1676   bool SameSize = Dst0Ty.getSizeInBits() == SrcMergeTy.getSizeInBits();
1677   if (SrcMergeTy != Dst0Ty && !SameSize)
1678     return false;
1679   // They are the same now (modulo a bitcast).
1680   // We can collect all the src registers.
1681   for (unsigned Idx = 0; Idx < SrcInstr->getNumSources(); ++Idx)
1682     Operands.push_back(SrcInstr->getSourceReg(Idx));
1683   return true;
1684 }
1685 
1686 void CombinerHelper::applyCombineUnmergeMergeToPlainValues(
1687     MachineInstr &MI, SmallVectorImpl<Register> &Operands) {
1688   assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES &&
1689          "Expected an unmerge");
1690   assert((MI.getNumOperands() - 1 == Operands.size()) &&
1691          "Not enough operands to replace all defs");
1692   unsigned NumElems = MI.getNumOperands() - 1;
1693 
1694   LLT SrcTy = MRI.getType(Operands[0]);
1695   LLT DstTy = MRI.getType(MI.getOperand(0).getReg());
1696   bool CanReuseInputDirectly = DstTy == SrcTy;
1697   Builder.setInstrAndDebugLoc(MI);
1698   for (unsigned Idx = 0; Idx < NumElems; ++Idx) {
1699     Register DstReg = MI.getOperand(Idx).getReg();
1700     Register SrcReg = Operands[Idx];
1701     if (CanReuseInputDirectly)
1702       replaceRegWith(MRI, DstReg, SrcReg);
1703     else
1704       Builder.buildCast(DstReg, SrcReg);
1705   }
1706   MI.eraseFromParent();
1707 }
1708 
1709 bool CombinerHelper::matchCombineUnmergeConstant(MachineInstr &MI,
1710                                                  SmallVectorImpl<APInt> &Csts) {
1711   unsigned SrcIdx = MI.getNumOperands() - 1;
1712   Register SrcReg = MI.getOperand(SrcIdx).getReg();
1713   MachineInstr *SrcInstr = MRI.getVRegDef(SrcReg);
1714   if (SrcInstr->getOpcode() != TargetOpcode::G_CONSTANT &&
1715       SrcInstr->getOpcode() != TargetOpcode::G_FCONSTANT)
1716     return false;
1717   // Break down the big constant in smaller ones.
1718   const MachineOperand &CstVal = SrcInstr->getOperand(1);
1719   APInt Val = SrcInstr->getOpcode() == TargetOpcode::G_CONSTANT
1720                   ? CstVal.getCImm()->getValue()
1721                   : CstVal.getFPImm()->getValueAPF().bitcastToAPInt();
1722 
1723   LLT Dst0Ty = MRI.getType(MI.getOperand(0).getReg());
1724   unsigned ShiftAmt = Dst0Ty.getSizeInBits();
1725   // Unmerge a constant.
1726   for (unsigned Idx = 0; Idx != SrcIdx; ++Idx) {
1727     Csts.emplace_back(Val.trunc(ShiftAmt));
1728     Val = Val.lshr(ShiftAmt);
1729   }
1730 
1731   return true;
1732 }
1733 
1734 void CombinerHelper::applyCombineUnmergeConstant(MachineInstr &MI,
1735                                                  SmallVectorImpl<APInt> &Csts) {
1736   assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES &&
1737          "Expected an unmerge");
1738   assert((MI.getNumOperands() - 1 == Csts.size()) &&
1739          "Not enough operands to replace all defs");
1740   unsigned NumElems = MI.getNumOperands() - 1;
1741   Builder.setInstrAndDebugLoc(MI);
1742   for (unsigned Idx = 0; Idx < NumElems; ++Idx) {
1743     Register DstReg = MI.getOperand(Idx).getReg();
1744     Builder.buildConstant(DstReg, Csts[Idx]);
1745   }
1746 
1747   MI.eraseFromParent();
1748 }
1749 
1750 bool CombinerHelper::matchCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI) {
1751   assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES &&
1752          "Expected an unmerge");
1753   // Check that all the lanes are dead except the first one.
1754   for (unsigned Idx = 1, EndIdx = MI.getNumDefs(); Idx != EndIdx; ++Idx) {
1755     if (!MRI.use_nodbg_empty(MI.getOperand(Idx).getReg()))
1756       return false;
1757   }
1758   return true;
1759 }
1760 
1761 void CombinerHelper::applyCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI) {
1762   Builder.setInstrAndDebugLoc(MI);
1763   Register SrcReg = MI.getOperand(MI.getNumDefs()).getReg();
1764   // Truncating a vector is going to truncate every single lane,
1765   // whereas we want the full lowbits.
1766   // Do the operation on a scalar instead.
1767   LLT SrcTy = MRI.getType(SrcReg);
1768   if (SrcTy.isVector())
1769     SrcReg =
1770         Builder.buildCast(LLT::scalar(SrcTy.getSizeInBits()), SrcReg).getReg(0);
1771 
1772   Register Dst0Reg = MI.getOperand(0).getReg();
1773   LLT Dst0Ty = MRI.getType(Dst0Reg);
1774   if (Dst0Ty.isVector()) {
1775     auto MIB = Builder.buildTrunc(LLT::scalar(Dst0Ty.getSizeInBits()), SrcReg);
1776     Builder.buildCast(Dst0Reg, MIB);
1777   } else
1778     Builder.buildTrunc(Dst0Reg, SrcReg);
1779   MI.eraseFromParent();
1780 }
1781 
1782 bool CombinerHelper::matchCombineUnmergeZExtToZExt(MachineInstr &MI) {
1783   assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES &&
1784          "Expected an unmerge");
1785   Register Dst0Reg = MI.getOperand(0).getReg();
1786   LLT Dst0Ty = MRI.getType(Dst0Reg);
1787   // G_ZEXT on vector applies to each lane, so it will
1788   // affect all destinations. Therefore we won't be able
1789   // to simplify the unmerge to just the first definition.
1790   if (Dst0Ty.isVector())
1791     return false;
1792   Register SrcReg = MI.getOperand(MI.getNumDefs()).getReg();
1793   LLT SrcTy = MRI.getType(SrcReg);
1794   if (SrcTy.isVector())
1795     return false;
1796 
1797   Register ZExtSrcReg;
1798   if (!mi_match(SrcReg, MRI, m_GZExt(m_Reg(ZExtSrcReg))))
1799     return false;
1800 
1801   // Finally we can replace the first definition with
1802   // a zext of the source if the definition is big enough to hold
1803   // all of ZExtSrc bits.
1804   LLT ZExtSrcTy = MRI.getType(ZExtSrcReg);
1805   return ZExtSrcTy.getSizeInBits() <= Dst0Ty.getSizeInBits();
1806 }
1807 
1808 void CombinerHelper::applyCombineUnmergeZExtToZExt(MachineInstr &MI) {
1809   assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES &&
1810          "Expected an unmerge");
1811 
1812   Register Dst0Reg = MI.getOperand(0).getReg();
1813 
1814   MachineInstr *ZExtInstr =
1815       MRI.getVRegDef(MI.getOperand(MI.getNumDefs()).getReg());
1816   assert(ZExtInstr && ZExtInstr->getOpcode() == TargetOpcode::G_ZEXT &&
1817          "Expecting a G_ZEXT");
1818 
1819   Register ZExtSrcReg = ZExtInstr->getOperand(1).getReg();
1820   LLT Dst0Ty = MRI.getType(Dst0Reg);
1821   LLT ZExtSrcTy = MRI.getType(ZExtSrcReg);
1822 
1823   Builder.setInstrAndDebugLoc(MI);
1824 
1825   if (Dst0Ty.getSizeInBits() > ZExtSrcTy.getSizeInBits()) {
1826     Builder.buildZExt(Dst0Reg, ZExtSrcReg);
1827   } else {
1828     assert(Dst0Ty.getSizeInBits() == ZExtSrcTy.getSizeInBits() &&
1829            "ZExt src doesn't fit in destination");
1830     replaceRegWith(MRI, Dst0Reg, ZExtSrcReg);
1831   }
1832 
1833   Register ZeroReg;
1834   for (unsigned Idx = 1, EndIdx = MI.getNumDefs(); Idx != EndIdx; ++Idx) {
1835     if (!ZeroReg)
1836       ZeroReg = Builder.buildConstant(Dst0Ty, 0).getReg(0);
1837     replaceRegWith(MRI, MI.getOperand(Idx).getReg(), ZeroReg);
1838   }
1839   MI.eraseFromParent();
1840 }
1841 
1842 bool CombinerHelper::matchCombineShiftToUnmerge(MachineInstr &MI,
1843                                                 unsigned TargetShiftSize,
1844                                                 unsigned &ShiftVal) {
1845   assert((MI.getOpcode() == TargetOpcode::G_SHL ||
1846           MI.getOpcode() == TargetOpcode::G_LSHR ||
1847           MI.getOpcode() == TargetOpcode::G_ASHR) && "Expected a shift");
1848 
1849   LLT Ty = MRI.getType(MI.getOperand(0).getReg());
1850   if (Ty.isVector()) // TODO:
1851     return false;
1852 
1853   // Don't narrow further than the requested size.
1854   unsigned Size = Ty.getSizeInBits();
1855   if (Size <= TargetShiftSize)
1856     return false;
1857 
1858   auto MaybeImmVal =
1859       getIConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI);
1860   if (!MaybeImmVal)
1861     return false;
1862 
1863   ShiftVal = MaybeImmVal->Value.getSExtValue();
1864   return ShiftVal >= Size / 2 && ShiftVal < Size;
1865 }
1866 
1867 void CombinerHelper::applyCombineShiftToUnmerge(MachineInstr &MI,
1868                                                 const unsigned &ShiftVal) {
1869   Register DstReg = MI.getOperand(0).getReg();
1870   Register SrcReg = MI.getOperand(1).getReg();
1871   LLT Ty = MRI.getType(SrcReg);
1872   unsigned Size = Ty.getSizeInBits();
1873   unsigned HalfSize = Size / 2;
1874   assert(ShiftVal >= HalfSize);
1875 
1876   LLT HalfTy = LLT::scalar(HalfSize);
1877 
1878   Builder.setInstr(MI);
1879   auto Unmerge = Builder.buildUnmerge(HalfTy, SrcReg);
1880   unsigned NarrowShiftAmt = ShiftVal - HalfSize;
1881 
1882   if (MI.getOpcode() == TargetOpcode::G_LSHR) {
1883     Register Narrowed = Unmerge.getReg(1);
1884 
1885     //  dst = G_LSHR s64:x, C for C >= 32
1886     // =>
1887     //   lo, hi = G_UNMERGE_VALUES x
1888     //   dst = G_MERGE_VALUES (G_LSHR hi, C - 32), 0
1889 
1890     if (NarrowShiftAmt != 0) {
1891       Narrowed = Builder.buildLShr(HalfTy, Narrowed,
1892         Builder.buildConstant(HalfTy, NarrowShiftAmt)).getReg(0);
1893     }
1894 
1895     auto Zero = Builder.buildConstant(HalfTy, 0);
1896     Builder.buildMerge(DstReg, { Narrowed, Zero });
1897   } else if (MI.getOpcode() == TargetOpcode::G_SHL) {
1898     Register Narrowed = Unmerge.getReg(0);
1899     //  dst = G_SHL s64:x, C for C >= 32
1900     // =>
1901     //   lo, hi = G_UNMERGE_VALUES x
1902     //   dst = G_MERGE_VALUES 0, (G_SHL hi, C - 32)
1903     if (NarrowShiftAmt != 0) {
1904       Narrowed = Builder.buildShl(HalfTy, Narrowed,
1905         Builder.buildConstant(HalfTy, NarrowShiftAmt)).getReg(0);
1906     }
1907 
1908     auto Zero = Builder.buildConstant(HalfTy, 0);
1909     Builder.buildMerge(DstReg, { Zero, Narrowed });
1910   } else {
1911     assert(MI.getOpcode() == TargetOpcode::G_ASHR);
1912     auto Hi = Builder.buildAShr(
1913       HalfTy, Unmerge.getReg(1),
1914       Builder.buildConstant(HalfTy, HalfSize - 1));
1915 
1916     if (ShiftVal == HalfSize) {
1917       // (G_ASHR i64:x, 32) ->
1918       //   G_MERGE_VALUES hi_32(x), (G_ASHR hi_32(x), 31)
1919       Builder.buildMerge(DstReg, { Unmerge.getReg(1), Hi });
1920     } else if (ShiftVal == Size - 1) {
1921       // Don't need a second shift.
1922       // (G_ASHR i64:x, 63) ->
1923       //   %narrowed = (G_ASHR hi_32(x), 31)
1924       //   G_MERGE_VALUES %narrowed, %narrowed
1925       Builder.buildMerge(DstReg, { Hi, Hi });
1926     } else {
1927       auto Lo = Builder.buildAShr(
1928         HalfTy, Unmerge.getReg(1),
1929         Builder.buildConstant(HalfTy, ShiftVal - HalfSize));
1930 
1931       // (G_ASHR i64:x, C) ->, for C >= 32
1932       //   G_MERGE_VALUES (G_ASHR hi_32(x), C - 32), (G_ASHR hi_32(x), 31)
1933       Builder.buildMerge(DstReg, { Lo, Hi });
1934     }
1935   }
1936 
1937   MI.eraseFromParent();
1938 }
1939 
1940 bool CombinerHelper::tryCombineShiftToUnmerge(MachineInstr &MI,
1941                                               unsigned TargetShiftAmount) {
1942   unsigned ShiftAmt;
1943   if (matchCombineShiftToUnmerge(MI, TargetShiftAmount, ShiftAmt)) {
1944     applyCombineShiftToUnmerge(MI, ShiftAmt);
1945     return true;
1946   }
1947 
1948   return false;
1949 }
1950 
1951 bool CombinerHelper::matchCombineI2PToP2I(MachineInstr &MI, Register &Reg) {
1952   assert(MI.getOpcode() == TargetOpcode::G_INTTOPTR && "Expected a G_INTTOPTR");
1953   Register DstReg = MI.getOperand(0).getReg();
1954   LLT DstTy = MRI.getType(DstReg);
1955   Register SrcReg = MI.getOperand(1).getReg();
1956   return mi_match(SrcReg, MRI,
1957                   m_GPtrToInt(m_all_of(m_SpecificType(DstTy), m_Reg(Reg))));
1958 }
1959 
1960 void CombinerHelper::applyCombineI2PToP2I(MachineInstr &MI, Register &Reg) {
1961   assert(MI.getOpcode() == TargetOpcode::G_INTTOPTR && "Expected a G_INTTOPTR");
1962   Register DstReg = MI.getOperand(0).getReg();
1963   Builder.setInstr(MI);
1964   Builder.buildCopy(DstReg, Reg);
1965   MI.eraseFromParent();
1966 }
1967 
1968 bool CombinerHelper::matchCombineP2IToI2P(MachineInstr &MI, Register &Reg) {
1969   assert(MI.getOpcode() == TargetOpcode::G_PTRTOINT && "Expected a G_PTRTOINT");
1970   Register SrcReg = MI.getOperand(1).getReg();
1971   return mi_match(SrcReg, MRI, m_GIntToPtr(m_Reg(Reg)));
1972 }
1973 
1974 void CombinerHelper::applyCombineP2IToI2P(MachineInstr &MI, Register &Reg) {
1975   assert(MI.getOpcode() == TargetOpcode::G_PTRTOINT && "Expected a G_PTRTOINT");
1976   Register DstReg = MI.getOperand(0).getReg();
1977   Builder.setInstr(MI);
1978   Builder.buildZExtOrTrunc(DstReg, Reg);
1979   MI.eraseFromParent();
1980 }
1981 
1982 bool CombinerHelper::matchCombineAddP2IToPtrAdd(
1983     MachineInstr &MI, std::pair<Register, bool> &PtrReg) {
1984   assert(MI.getOpcode() == TargetOpcode::G_ADD);
1985   Register LHS = MI.getOperand(1).getReg();
1986   Register RHS = MI.getOperand(2).getReg();
1987   LLT IntTy = MRI.getType(LHS);
1988 
1989   // G_PTR_ADD always has the pointer in the LHS, so we may need to commute the
1990   // instruction.
1991   PtrReg.second = false;
1992   for (Register SrcReg : {LHS, RHS}) {
1993     if (mi_match(SrcReg, MRI, m_GPtrToInt(m_Reg(PtrReg.first)))) {
1994       // Don't handle cases where the integer is implicitly converted to the
1995       // pointer width.
1996       LLT PtrTy = MRI.getType(PtrReg.first);
1997       if (PtrTy.getScalarSizeInBits() == IntTy.getScalarSizeInBits())
1998         return true;
1999     }
2000 
2001     PtrReg.second = true;
2002   }
2003 
2004   return false;
2005 }
2006 
2007 void CombinerHelper::applyCombineAddP2IToPtrAdd(
2008     MachineInstr &MI, std::pair<Register, bool> &PtrReg) {
2009   Register Dst = MI.getOperand(0).getReg();
2010   Register LHS = MI.getOperand(1).getReg();
2011   Register RHS = MI.getOperand(2).getReg();
2012 
2013   const bool DoCommute = PtrReg.second;
2014   if (DoCommute)
2015     std::swap(LHS, RHS);
2016   LHS = PtrReg.first;
2017 
2018   LLT PtrTy = MRI.getType(LHS);
2019 
2020   Builder.setInstrAndDebugLoc(MI);
2021   auto PtrAdd = Builder.buildPtrAdd(PtrTy, LHS, RHS);
2022   Builder.buildPtrToInt(Dst, PtrAdd);
2023   MI.eraseFromParent();
2024 }
2025 
2026 bool CombinerHelper::matchCombineConstPtrAddToI2P(MachineInstr &MI,
2027                                                   int64_t &NewCst) {
2028   auto &PtrAdd = cast<GPtrAdd>(MI);
2029   Register LHS = PtrAdd.getBaseReg();
2030   Register RHS = PtrAdd.getOffsetReg();
2031   MachineRegisterInfo &MRI = Builder.getMF().getRegInfo();
2032 
2033   if (auto RHSCst = getIConstantVRegSExtVal(RHS, MRI)) {
2034     int64_t Cst;
2035     if (mi_match(LHS, MRI, m_GIntToPtr(m_ICst(Cst)))) {
2036       NewCst = Cst + *RHSCst;
2037       return true;
2038     }
2039   }
2040 
2041   return false;
2042 }
2043 
2044 void CombinerHelper::applyCombineConstPtrAddToI2P(MachineInstr &MI,
2045                                                   int64_t &NewCst) {
2046   auto &PtrAdd = cast<GPtrAdd>(MI);
2047   Register Dst = PtrAdd.getReg(0);
2048 
2049   Builder.setInstrAndDebugLoc(MI);
2050   Builder.buildConstant(Dst, NewCst);
2051   PtrAdd.eraseFromParent();
2052 }
2053 
2054 bool CombinerHelper::matchCombineAnyExtTrunc(MachineInstr &MI, Register &Reg) {
2055   assert(MI.getOpcode() == TargetOpcode::G_ANYEXT && "Expected a G_ANYEXT");
2056   Register DstReg = MI.getOperand(0).getReg();
2057   Register SrcReg = MI.getOperand(1).getReg();
2058   LLT DstTy = MRI.getType(DstReg);
2059   return mi_match(SrcReg, MRI,
2060                   m_GTrunc(m_all_of(m_Reg(Reg), m_SpecificType(DstTy))));
2061 }
2062 
2063 bool CombinerHelper::matchCombineZextTrunc(MachineInstr &MI, Register &Reg) {
2064   assert(MI.getOpcode() == TargetOpcode::G_ZEXT && "Expected a G_ZEXT");
2065   Register DstReg = MI.getOperand(0).getReg();
2066   Register SrcReg = MI.getOperand(1).getReg();
2067   LLT DstTy = MRI.getType(DstReg);
2068   if (mi_match(SrcReg, MRI,
2069                m_GTrunc(m_all_of(m_Reg(Reg), m_SpecificType(DstTy))))) {
2070     unsigned DstSize = DstTy.getScalarSizeInBits();
2071     unsigned SrcSize = MRI.getType(SrcReg).getScalarSizeInBits();
2072     return KB->getKnownBits(Reg).countMinLeadingZeros() >= DstSize - SrcSize;
2073   }
2074   return false;
2075 }
2076 
2077 bool CombinerHelper::matchCombineExtOfExt(
2078     MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) {
2079   assert((MI.getOpcode() == TargetOpcode::G_ANYEXT ||
2080           MI.getOpcode() == TargetOpcode::G_SEXT ||
2081           MI.getOpcode() == TargetOpcode::G_ZEXT) &&
2082          "Expected a G_[ASZ]EXT");
2083   Register SrcReg = MI.getOperand(1).getReg();
2084   MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
2085   // Match exts with the same opcode, anyext([sz]ext) and sext(zext).
2086   unsigned Opc = MI.getOpcode();
2087   unsigned SrcOpc = SrcMI->getOpcode();
2088   if (Opc == SrcOpc ||
2089       (Opc == TargetOpcode::G_ANYEXT &&
2090        (SrcOpc == TargetOpcode::G_SEXT || SrcOpc == TargetOpcode::G_ZEXT)) ||
2091       (Opc == TargetOpcode::G_SEXT && SrcOpc == TargetOpcode::G_ZEXT)) {
2092     MatchInfo = std::make_tuple(SrcMI->getOperand(1).getReg(), SrcOpc);
2093     return true;
2094   }
2095   return false;
2096 }
2097 
2098 void CombinerHelper::applyCombineExtOfExt(
2099     MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) {
2100   assert((MI.getOpcode() == TargetOpcode::G_ANYEXT ||
2101           MI.getOpcode() == TargetOpcode::G_SEXT ||
2102           MI.getOpcode() == TargetOpcode::G_ZEXT) &&
2103          "Expected a G_[ASZ]EXT");
2104 
2105   Register Reg = std::get<0>(MatchInfo);
2106   unsigned SrcExtOp = std::get<1>(MatchInfo);
2107 
2108   // Combine exts with the same opcode.
2109   if (MI.getOpcode() == SrcExtOp) {
2110     Observer.changingInstr(MI);
2111     MI.getOperand(1).setReg(Reg);
2112     Observer.changedInstr(MI);
2113     return;
2114   }
2115 
2116   // Combine:
2117   // - anyext([sz]ext x) to [sz]ext x
2118   // - sext(zext x) to zext x
2119   if (MI.getOpcode() == TargetOpcode::G_ANYEXT ||
2120       (MI.getOpcode() == TargetOpcode::G_SEXT &&
2121        SrcExtOp == TargetOpcode::G_ZEXT)) {
2122     Register DstReg = MI.getOperand(0).getReg();
2123     Builder.setInstrAndDebugLoc(MI);
2124     Builder.buildInstr(SrcExtOp, {DstReg}, {Reg});
2125     MI.eraseFromParent();
2126   }
2127 }
2128 
2129 void CombinerHelper::applyCombineMulByNegativeOne(MachineInstr &MI) {
2130   assert(MI.getOpcode() == TargetOpcode::G_MUL && "Expected a G_MUL");
2131   Register DstReg = MI.getOperand(0).getReg();
2132   Register SrcReg = MI.getOperand(1).getReg();
2133   LLT DstTy = MRI.getType(DstReg);
2134 
2135   Builder.setInstrAndDebugLoc(MI);
2136   Builder.buildSub(DstReg, Builder.buildConstant(DstTy, 0), SrcReg,
2137                    MI.getFlags());
2138   MI.eraseFromParent();
2139 }
2140 
2141 bool CombinerHelper::matchCombineFNegOfFNeg(MachineInstr &MI, Register &Reg) {
2142   assert(MI.getOpcode() == TargetOpcode::G_FNEG && "Expected a G_FNEG");
2143   Register SrcReg = MI.getOperand(1).getReg();
2144   return mi_match(SrcReg, MRI, m_GFNeg(m_Reg(Reg)));
2145 }
2146 
2147 bool CombinerHelper::matchCombineFAbsOfFAbs(MachineInstr &MI, Register &Src) {
2148   assert(MI.getOpcode() == TargetOpcode::G_FABS && "Expected a G_FABS");
2149   Src = MI.getOperand(1).getReg();
2150   Register AbsSrc;
2151   return mi_match(Src, MRI, m_GFabs(m_Reg(AbsSrc)));
2152 }
2153 
2154 bool CombinerHelper::matchCombineFAbsOfFNeg(MachineInstr &MI,
2155                                             BuildFnTy &MatchInfo) {
2156   assert(MI.getOpcode() == TargetOpcode::G_FABS && "Expected a G_FABS");
2157   Register Src = MI.getOperand(1).getReg();
2158   Register NegSrc;
2159 
2160   if (!mi_match(Src, MRI, m_GFNeg(m_Reg(NegSrc))))
2161     return false;
2162 
2163   MatchInfo = [=, &MI](MachineIRBuilder &B) {
2164     Observer.changingInstr(MI);
2165     MI.getOperand(1).setReg(NegSrc);
2166     Observer.changedInstr(MI);
2167   };
2168   return true;
2169 }
2170 
2171 bool CombinerHelper::matchCombineTruncOfExt(
2172     MachineInstr &MI, std::pair<Register, unsigned> &MatchInfo) {
2173   assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC");
2174   Register SrcReg = MI.getOperand(1).getReg();
2175   MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
2176   unsigned SrcOpc = SrcMI->getOpcode();
2177   if (SrcOpc == TargetOpcode::G_ANYEXT || SrcOpc == TargetOpcode::G_SEXT ||
2178       SrcOpc == TargetOpcode::G_ZEXT) {
2179     MatchInfo = std::make_pair(SrcMI->getOperand(1).getReg(), SrcOpc);
2180     return true;
2181   }
2182   return false;
2183 }
2184 
2185 void CombinerHelper::applyCombineTruncOfExt(
2186     MachineInstr &MI, std::pair<Register, unsigned> &MatchInfo) {
2187   assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC");
2188   Register SrcReg = MatchInfo.first;
2189   unsigned SrcExtOp = MatchInfo.second;
2190   Register DstReg = MI.getOperand(0).getReg();
2191   LLT SrcTy = MRI.getType(SrcReg);
2192   LLT DstTy = MRI.getType(DstReg);
2193   if (SrcTy == DstTy) {
2194     MI.eraseFromParent();
2195     replaceRegWith(MRI, DstReg, SrcReg);
2196     return;
2197   }
2198   Builder.setInstrAndDebugLoc(MI);
2199   if (SrcTy.getSizeInBits() < DstTy.getSizeInBits())
2200     Builder.buildInstr(SrcExtOp, {DstReg}, {SrcReg});
2201   else
2202     Builder.buildTrunc(DstReg, SrcReg);
2203   MI.eraseFromParent();
2204 }
2205 
2206 bool CombinerHelper::matchCombineTruncOfShl(
2207     MachineInstr &MI, std::pair<Register, Register> &MatchInfo) {
2208   assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC");
2209   Register DstReg = MI.getOperand(0).getReg();
2210   Register SrcReg = MI.getOperand(1).getReg();
2211   LLT DstTy = MRI.getType(DstReg);
2212   Register ShiftSrc;
2213   Register ShiftAmt;
2214 
2215   if (MRI.hasOneNonDBGUse(SrcReg) &&
2216       mi_match(SrcReg, MRI, m_GShl(m_Reg(ShiftSrc), m_Reg(ShiftAmt))) &&
2217       isLegalOrBeforeLegalizer(
2218           {TargetOpcode::G_SHL,
2219            {DstTy, getTargetLowering().getPreferredShiftAmountTy(DstTy)}})) {
2220     KnownBits Known = KB->getKnownBits(ShiftAmt);
2221     unsigned Size = DstTy.getSizeInBits();
2222     if (Known.countMaxActiveBits() <= Log2_32(Size)) {
2223       MatchInfo = std::make_pair(ShiftSrc, ShiftAmt);
2224       return true;
2225     }
2226   }
2227   return false;
2228 }
2229 
2230 void CombinerHelper::applyCombineTruncOfShl(
2231     MachineInstr &MI, std::pair<Register, Register> &MatchInfo) {
2232   assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC");
2233   Register DstReg = MI.getOperand(0).getReg();
2234   Register SrcReg = MI.getOperand(1).getReg();
2235   LLT DstTy = MRI.getType(DstReg);
2236   MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
2237 
2238   Register ShiftSrc = MatchInfo.first;
2239   Register ShiftAmt = MatchInfo.second;
2240   Builder.setInstrAndDebugLoc(MI);
2241   auto TruncShiftSrc = Builder.buildTrunc(DstTy, ShiftSrc);
2242   Builder.buildShl(DstReg, TruncShiftSrc, ShiftAmt, SrcMI->getFlags());
2243   MI.eraseFromParent();
2244 }
2245 
2246 bool CombinerHelper::matchAnyExplicitUseIsUndef(MachineInstr &MI) {
2247   return any_of(MI.explicit_uses(), [this](const MachineOperand &MO) {
2248     return MO.isReg() &&
2249            getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MO.getReg(), MRI);
2250   });
2251 }
2252 
2253 bool CombinerHelper::matchAllExplicitUsesAreUndef(MachineInstr &MI) {
2254   return all_of(MI.explicit_uses(), [this](const MachineOperand &MO) {
2255     return !MO.isReg() ||
2256            getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MO.getReg(), MRI);
2257   });
2258 }
2259 
2260 bool CombinerHelper::matchUndefShuffleVectorMask(MachineInstr &MI) {
2261   assert(MI.getOpcode() == TargetOpcode::G_SHUFFLE_VECTOR);
2262   ArrayRef<int> Mask = MI.getOperand(3).getShuffleMask();
2263   return all_of(Mask, [](int Elt) { return Elt < 0; });
2264 }
2265 
2266 bool CombinerHelper::matchUndefStore(MachineInstr &MI) {
2267   assert(MI.getOpcode() == TargetOpcode::G_STORE);
2268   return getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MI.getOperand(0).getReg(),
2269                       MRI);
2270 }
2271 
2272 bool CombinerHelper::matchUndefSelectCmp(MachineInstr &MI) {
2273   assert(MI.getOpcode() == TargetOpcode::G_SELECT);
2274   return getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MI.getOperand(1).getReg(),
2275                       MRI);
2276 }
2277 
2278 bool CombinerHelper::matchConstantSelectCmp(MachineInstr &MI, unsigned &OpIdx) {
2279   GSelect &SelMI = cast<GSelect>(MI);
2280   auto Cst =
2281       isConstantOrConstantSplatVector(*MRI.getVRegDef(SelMI.getCondReg()), MRI);
2282   if (!Cst)
2283     return false;
2284   OpIdx = Cst->isZero() ? 3 : 2;
2285   return true;
2286 }
2287 
2288 bool CombinerHelper::eraseInst(MachineInstr &MI) {
2289   MI.eraseFromParent();
2290   return true;
2291 }
2292 
2293 bool CombinerHelper::matchEqualDefs(const MachineOperand &MOP1,
2294                                     const MachineOperand &MOP2) {
2295   if (!MOP1.isReg() || !MOP2.isReg())
2296     return false;
2297   auto InstAndDef1 = getDefSrcRegIgnoringCopies(MOP1.getReg(), MRI);
2298   if (!InstAndDef1)
2299     return false;
2300   auto InstAndDef2 = getDefSrcRegIgnoringCopies(MOP2.getReg(), MRI);
2301   if (!InstAndDef2)
2302     return false;
2303   MachineInstr *I1 = InstAndDef1->MI;
2304   MachineInstr *I2 = InstAndDef2->MI;
2305 
2306   // Handle a case like this:
2307   //
2308   // %0:_(s64), %1:_(s64) = G_UNMERGE_VALUES %2:_(<2 x s64>)
2309   //
2310   // Even though %0 and %1 are produced by the same instruction they are not
2311   // the same values.
2312   if (I1 == I2)
2313     return MOP1.getReg() == MOP2.getReg();
2314 
2315   // If we have an instruction which loads or stores, we can't guarantee that
2316   // it is identical.
2317   //
2318   // For example, we may have
2319   //
2320   // %x1 = G_LOAD %addr (load N from @somewhere)
2321   // ...
2322   // call @foo
2323   // ...
2324   // %x2 = G_LOAD %addr (load N from @somewhere)
2325   // ...
2326   // %or = G_OR %x1, %x2
2327   //
2328   // It's possible that @foo will modify whatever lives at the address we're
2329   // loading from. To be safe, let's just assume that all loads and stores
2330   // are different (unless we have something which is guaranteed to not
2331   // change.)
2332   if (I1->mayLoadOrStore() && !I1->isDereferenceableInvariantLoad(nullptr))
2333     return false;
2334 
2335   // Check for physical registers on the instructions first to avoid cases
2336   // like this:
2337   //
2338   // %a = COPY $physreg
2339   // ...
2340   // SOMETHING implicit-def $physreg
2341   // ...
2342   // %b = COPY $physreg
2343   //
2344   // These copies are not equivalent.
2345   if (any_of(I1->uses(), [](const MachineOperand &MO) {
2346         return MO.isReg() && MO.getReg().isPhysical();
2347       })) {
2348     // Check if we have a case like this:
2349     //
2350     // %a = COPY $physreg
2351     // %b = COPY %a
2352     //
2353     // In this case, I1 and I2 will both be equal to %a = COPY $physreg.
2354     // From that, we know that they must have the same value, since they must
2355     // have come from the same COPY.
2356     return I1->isIdenticalTo(*I2);
2357   }
2358 
2359   // We don't have any physical registers, so we don't necessarily need the
2360   // same vreg defs.
2361   //
2362   // On the off-chance that there's some target instruction feeding into the
2363   // instruction, let's use produceSameValue instead of isIdenticalTo.
2364   if (Builder.getTII().produceSameValue(*I1, *I2, &MRI)) {
2365     // Handle instructions with multiple defs that produce same values. Values
2366     // are same for operands with same index.
2367     // %0:_(s8), %1:_(s8), %2:_(s8), %3:_(s8) = G_UNMERGE_VALUES %4:_(<4 x s8>)
2368     // %5:_(s8), %6:_(s8), %7:_(s8), %8:_(s8) = G_UNMERGE_VALUES %4:_(<4 x s8>)
2369     // I1 and I2 are different instructions but produce same values,
2370     // %1 and %6 are same, %1 and %7 are not the same value.
2371     return I1->findRegisterDefOperandIdx(InstAndDef1->Reg) ==
2372            I2->findRegisterDefOperandIdx(InstAndDef2->Reg);
2373   }
2374   return false;
2375 }
2376 
2377 bool CombinerHelper::matchConstantOp(const MachineOperand &MOP, int64_t C) {
2378   if (!MOP.isReg())
2379     return false;
2380   auto *MI = MRI.getVRegDef(MOP.getReg());
2381   auto MaybeCst = isConstantOrConstantSplatVector(*MI, MRI);
2382   return MaybeCst.hasValue() && MaybeCst->getBitWidth() <= 64 &&
2383          MaybeCst->getSExtValue() == C;
2384 }
2385 
2386 bool CombinerHelper::replaceSingleDefInstWithOperand(MachineInstr &MI,
2387                                                      unsigned OpIdx) {
2388   assert(MI.getNumExplicitDefs() == 1 && "Expected one explicit def?");
2389   Register OldReg = MI.getOperand(0).getReg();
2390   Register Replacement = MI.getOperand(OpIdx).getReg();
2391   assert(canReplaceReg(OldReg, Replacement, MRI) && "Cannot replace register?");
2392   MI.eraseFromParent();
2393   replaceRegWith(MRI, OldReg, Replacement);
2394   return true;
2395 }
2396 
2397 bool CombinerHelper::replaceSingleDefInstWithReg(MachineInstr &MI,
2398                                                  Register Replacement) {
2399   assert(MI.getNumExplicitDefs() == 1 && "Expected one explicit def?");
2400   Register OldReg = MI.getOperand(0).getReg();
2401   assert(canReplaceReg(OldReg, Replacement, MRI) && "Cannot replace register?");
2402   MI.eraseFromParent();
2403   replaceRegWith(MRI, OldReg, Replacement);
2404   return true;
2405 }
2406 
2407 bool CombinerHelper::matchSelectSameVal(MachineInstr &MI) {
2408   assert(MI.getOpcode() == TargetOpcode::G_SELECT);
2409   // Match (cond ? x : x)
2410   return matchEqualDefs(MI.getOperand(2), MI.getOperand(3)) &&
2411          canReplaceReg(MI.getOperand(0).getReg(), MI.getOperand(2).getReg(),
2412                        MRI);
2413 }
2414 
2415 bool CombinerHelper::matchBinOpSameVal(MachineInstr &MI) {
2416   return matchEqualDefs(MI.getOperand(1), MI.getOperand(2)) &&
2417          canReplaceReg(MI.getOperand(0).getReg(), MI.getOperand(1).getReg(),
2418                        MRI);
2419 }
2420 
2421 bool CombinerHelper::matchOperandIsZero(MachineInstr &MI, unsigned OpIdx) {
2422   return matchConstantOp(MI.getOperand(OpIdx), 0) &&
2423          canReplaceReg(MI.getOperand(0).getReg(), MI.getOperand(OpIdx).getReg(),
2424                        MRI);
2425 }
2426 
2427 bool CombinerHelper::matchOperandIsUndef(MachineInstr &MI, unsigned OpIdx) {
2428   MachineOperand &MO = MI.getOperand(OpIdx);
2429   return MO.isReg() &&
2430          getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MO.getReg(), MRI);
2431 }
2432 
2433 bool CombinerHelper::matchOperandIsKnownToBeAPowerOfTwo(MachineInstr &MI,
2434                                                         unsigned OpIdx) {
2435   MachineOperand &MO = MI.getOperand(OpIdx);
2436   return isKnownToBeAPowerOfTwo(MO.getReg(), MRI, KB);
2437 }
2438 
2439 bool CombinerHelper::replaceInstWithFConstant(MachineInstr &MI, double C) {
2440   assert(MI.getNumDefs() == 1 && "Expected only one def?");
2441   Builder.setInstr(MI);
2442   Builder.buildFConstant(MI.getOperand(0), C);
2443   MI.eraseFromParent();
2444   return true;
2445 }
2446 
2447 bool CombinerHelper::replaceInstWithConstant(MachineInstr &MI, int64_t C) {
2448   assert(MI.getNumDefs() == 1 && "Expected only one def?");
2449   Builder.setInstr(MI);
2450   Builder.buildConstant(MI.getOperand(0), C);
2451   MI.eraseFromParent();
2452   return true;
2453 }
2454 
2455 bool CombinerHelper::replaceInstWithConstant(MachineInstr &MI, APInt C) {
2456   assert(MI.getNumDefs() == 1 && "Expected only one def?");
2457   Builder.setInstr(MI);
2458   Builder.buildConstant(MI.getOperand(0), C);
2459   MI.eraseFromParent();
2460   return true;
2461 }
2462 
2463 bool CombinerHelper::replaceInstWithUndef(MachineInstr &MI) {
2464   assert(MI.getNumDefs() == 1 && "Expected only one def?");
2465   Builder.setInstr(MI);
2466   Builder.buildUndef(MI.getOperand(0));
2467   MI.eraseFromParent();
2468   return true;
2469 }
2470 
2471 bool CombinerHelper::matchSimplifyAddToSub(
2472     MachineInstr &MI, std::tuple<Register, Register> &MatchInfo) {
2473   Register LHS = MI.getOperand(1).getReg();
2474   Register RHS = MI.getOperand(2).getReg();
2475   Register &NewLHS = std::get<0>(MatchInfo);
2476   Register &NewRHS = std::get<1>(MatchInfo);
2477 
2478   // Helper lambda to check for opportunities for
2479   // ((0-A) + B) -> B - A
2480   // (A + (0-B)) -> A - B
2481   auto CheckFold = [&](Register &MaybeSub, Register &MaybeNewLHS) {
2482     if (!mi_match(MaybeSub, MRI, m_Neg(m_Reg(NewRHS))))
2483       return false;
2484     NewLHS = MaybeNewLHS;
2485     return true;
2486   };
2487 
2488   return CheckFold(LHS, RHS) || CheckFold(RHS, LHS);
2489 }
2490 
2491 bool CombinerHelper::matchCombineInsertVecElts(
2492     MachineInstr &MI, SmallVectorImpl<Register> &MatchInfo) {
2493   assert(MI.getOpcode() == TargetOpcode::G_INSERT_VECTOR_ELT &&
2494          "Invalid opcode");
2495   Register DstReg = MI.getOperand(0).getReg();
2496   LLT DstTy = MRI.getType(DstReg);
2497   assert(DstTy.isVector() && "Invalid G_INSERT_VECTOR_ELT?");
2498   unsigned NumElts = DstTy.getNumElements();
2499   // If this MI is part of a sequence of insert_vec_elts, then
2500   // don't do the combine in the middle of the sequence.
2501   if (MRI.hasOneUse(DstReg) && MRI.use_instr_begin(DstReg)->getOpcode() ==
2502                                    TargetOpcode::G_INSERT_VECTOR_ELT)
2503     return false;
2504   MachineInstr *CurrInst = &MI;
2505   MachineInstr *TmpInst;
2506   int64_t IntImm;
2507   Register TmpReg;
2508   MatchInfo.resize(NumElts);
2509   while (mi_match(
2510       CurrInst->getOperand(0).getReg(), MRI,
2511       m_GInsertVecElt(m_MInstr(TmpInst), m_Reg(TmpReg), m_ICst(IntImm)))) {
2512     if (IntImm >= NumElts)
2513       return false;
2514     if (!MatchInfo[IntImm])
2515       MatchInfo[IntImm] = TmpReg;
2516     CurrInst = TmpInst;
2517   }
2518   // Variable index.
2519   if (CurrInst->getOpcode() == TargetOpcode::G_INSERT_VECTOR_ELT)
2520     return false;
2521   if (TmpInst->getOpcode() == TargetOpcode::G_BUILD_VECTOR) {
2522     for (unsigned I = 1; I < TmpInst->getNumOperands(); ++I) {
2523       if (!MatchInfo[I - 1].isValid())
2524         MatchInfo[I - 1] = TmpInst->getOperand(I).getReg();
2525     }
2526     return true;
2527   }
2528   // If we didn't end in a G_IMPLICIT_DEF, bail out.
2529   return TmpInst->getOpcode() == TargetOpcode::G_IMPLICIT_DEF;
2530 }
2531 
2532 void CombinerHelper::applyCombineInsertVecElts(
2533     MachineInstr &MI, SmallVectorImpl<Register> &MatchInfo) {
2534   Builder.setInstr(MI);
2535   Register UndefReg;
2536   auto GetUndef = [&]() {
2537     if (UndefReg)
2538       return UndefReg;
2539     LLT DstTy = MRI.getType(MI.getOperand(0).getReg());
2540     UndefReg = Builder.buildUndef(DstTy.getScalarType()).getReg(0);
2541     return UndefReg;
2542   };
2543   for (unsigned I = 0; I < MatchInfo.size(); ++I) {
2544     if (!MatchInfo[I])
2545       MatchInfo[I] = GetUndef();
2546   }
2547   Builder.buildBuildVector(MI.getOperand(0).getReg(), MatchInfo);
2548   MI.eraseFromParent();
2549 }
2550 
2551 void CombinerHelper::applySimplifyAddToSub(
2552     MachineInstr &MI, std::tuple<Register, Register> &MatchInfo) {
2553   Builder.setInstr(MI);
2554   Register SubLHS, SubRHS;
2555   std::tie(SubLHS, SubRHS) = MatchInfo;
2556   Builder.buildSub(MI.getOperand(0).getReg(), SubLHS, SubRHS);
2557   MI.eraseFromParent();
2558 }
2559 
2560 bool CombinerHelper::matchHoistLogicOpWithSameOpcodeHands(
2561     MachineInstr &MI, InstructionStepsMatchInfo &MatchInfo) {
2562   // Matches: logic (hand x, ...), (hand y, ...) -> hand (logic x, y), ...
2563   //
2564   // Creates the new hand + logic instruction (but does not insert them.)
2565   //
2566   // On success, MatchInfo is populated with the new instructions. These are
2567   // inserted in applyHoistLogicOpWithSameOpcodeHands.
2568   unsigned LogicOpcode = MI.getOpcode();
2569   assert(LogicOpcode == TargetOpcode::G_AND ||
2570          LogicOpcode == TargetOpcode::G_OR ||
2571          LogicOpcode == TargetOpcode::G_XOR);
2572   MachineIRBuilder MIB(MI);
2573   Register Dst = MI.getOperand(0).getReg();
2574   Register LHSReg = MI.getOperand(1).getReg();
2575   Register RHSReg = MI.getOperand(2).getReg();
2576 
2577   // Don't recompute anything.
2578   if (!MRI.hasOneNonDBGUse(LHSReg) || !MRI.hasOneNonDBGUse(RHSReg))
2579     return false;
2580 
2581   // Make sure we have (hand x, ...), (hand y, ...)
2582   MachineInstr *LeftHandInst = getDefIgnoringCopies(LHSReg, MRI);
2583   MachineInstr *RightHandInst = getDefIgnoringCopies(RHSReg, MRI);
2584   if (!LeftHandInst || !RightHandInst)
2585     return false;
2586   unsigned HandOpcode = LeftHandInst->getOpcode();
2587   if (HandOpcode != RightHandInst->getOpcode())
2588     return false;
2589   if (!LeftHandInst->getOperand(1).isReg() ||
2590       !RightHandInst->getOperand(1).isReg())
2591     return false;
2592 
2593   // Make sure the types match up, and if we're doing this post-legalization,
2594   // we end up with legal types.
2595   Register X = LeftHandInst->getOperand(1).getReg();
2596   Register Y = RightHandInst->getOperand(1).getReg();
2597   LLT XTy = MRI.getType(X);
2598   LLT YTy = MRI.getType(Y);
2599   if (XTy != YTy)
2600     return false;
2601   if (!isLegalOrBeforeLegalizer({LogicOpcode, {XTy, YTy}}))
2602     return false;
2603 
2604   // Optional extra source register.
2605   Register ExtraHandOpSrcReg;
2606   switch (HandOpcode) {
2607   default:
2608     return false;
2609   case TargetOpcode::G_ANYEXT:
2610   case TargetOpcode::G_SEXT:
2611   case TargetOpcode::G_ZEXT: {
2612     // Match: logic (ext X), (ext Y) --> ext (logic X, Y)
2613     break;
2614   }
2615   case TargetOpcode::G_AND:
2616   case TargetOpcode::G_ASHR:
2617   case TargetOpcode::G_LSHR:
2618   case TargetOpcode::G_SHL: {
2619     // Match: logic (binop x, z), (binop y, z) -> binop (logic x, y), z
2620     MachineOperand &ZOp = LeftHandInst->getOperand(2);
2621     if (!matchEqualDefs(ZOp, RightHandInst->getOperand(2)))
2622       return false;
2623     ExtraHandOpSrcReg = ZOp.getReg();
2624     break;
2625   }
2626   }
2627 
2628   // Record the steps to build the new instructions.
2629   //
2630   // Steps to build (logic x, y)
2631   auto NewLogicDst = MRI.createGenericVirtualRegister(XTy);
2632   OperandBuildSteps LogicBuildSteps = {
2633       [=](MachineInstrBuilder &MIB) { MIB.addDef(NewLogicDst); },
2634       [=](MachineInstrBuilder &MIB) { MIB.addReg(X); },
2635       [=](MachineInstrBuilder &MIB) { MIB.addReg(Y); }};
2636   InstructionBuildSteps LogicSteps(LogicOpcode, LogicBuildSteps);
2637 
2638   // Steps to build hand (logic x, y), ...z
2639   OperandBuildSteps HandBuildSteps = {
2640       [=](MachineInstrBuilder &MIB) { MIB.addDef(Dst); },
2641       [=](MachineInstrBuilder &MIB) { MIB.addReg(NewLogicDst); }};
2642   if (ExtraHandOpSrcReg.isValid())
2643     HandBuildSteps.push_back(
2644         [=](MachineInstrBuilder &MIB) { MIB.addReg(ExtraHandOpSrcReg); });
2645   InstructionBuildSteps HandSteps(HandOpcode, HandBuildSteps);
2646 
2647   MatchInfo = InstructionStepsMatchInfo({LogicSteps, HandSteps});
2648   return true;
2649 }
2650 
2651 void CombinerHelper::applyBuildInstructionSteps(
2652     MachineInstr &MI, InstructionStepsMatchInfo &MatchInfo) {
2653   assert(MatchInfo.InstrsToBuild.size() &&
2654          "Expected at least one instr to build?");
2655   Builder.setInstr(MI);
2656   for (auto &InstrToBuild : MatchInfo.InstrsToBuild) {
2657     assert(InstrToBuild.Opcode && "Expected a valid opcode?");
2658     assert(InstrToBuild.OperandFns.size() && "Expected at least one operand?");
2659     MachineInstrBuilder Instr = Builder.buildInstr(InstrToBuild.Opcode);
2660     for (auto &OperandFn : InstrToBuild.OperandFns)
2661       OperandFn(Instr);
2662   }
2663   MI.eraseFromParent();
2664 }
2665 
2666 bool CombinerHelper::matchAshrShlToSextInreg(
2667     MachineInstr &MI, std::tuple<Register, int64_t> &MatchInfo) {
2668   assert(MI.getOpcode() == TargetOpcode::G_ASHR);
2669   int64_t ShlCst, AshrCst;
2670   Register Src;
2671   // FIXME: detect splat constant vectors.
2672   if (!mi_match(MI.getOperand(0).getReg(), MRI,
2673                 m_GAShr(m_GShl(m_Reg(Src), m_ICst(ShlCst)), m_ICst(AshrCst))))
2674     return false;
2675   if (ShlCst != AshrCst)
2676     return false;
2677   if (!isLegalOrBeforeLegalizer(
2678           {TargetOpcode::G_SEXT_INREG, {MRI.getType(Src)}}))
2679     return false;
2680   MatchInfo = std::make_tuple(Src, ShlCst);
2681   return true;
2682 }
2683 
2684 void CombinerHelper::applyAshShlToSextInreg(
2685     MachineInstr &MI, std::tuple<Register, int64_t> &MatchInfo) {
2686   assert(MI.getOpcode() == TargetOpcode::G_ASHR);
2687   Register Src;
2688   int64_t ShiftAmt;
2689   std::tie(Src, ShiftAmt) = MatchInfo;
2690   unsigned Size = MRI.getType(Src).getScalarSizeInBits();
2691   Builder.setInstrAndDebugLoc(MI);
2692   Builder.buildSExtInReg(MI.getOperand(0).getReg(), Src, Size - ShiftAmt);
2693   MI.eraseFromParent();
2694 }
2695 
2696 /// and(and(x, C1), C2) -> C1&C2 ? and(x, C1&C2) : 0
2697 bool CombinerHelper::matchOverlappingAnd(
2698     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
2699   assert(MI.getOpcode() == TargetOpcode::G_AND);
2700 
2701   Register Dst = MI.getOperand(0).getReg();
2702   LLT Ty = MRI.getType(Dst);
2703 
2704   Register R;
2705   int64_t C1;
2706   int64_t C2;
2707   if (!mi_match(
2708           Dst, MRI,
2709           m_GAnd(m_GAnd(m_Reg(R), m_ICst(C1)), m_ICst(C2))))
2710     return false;
2711 
2712   MatchInfo = [=](MachineIRBuilder &B) {
2713     if (C1 & C2) {
2714       B.buildAnd(Dst, R, B.buildConstant(Ty, C1 & C2));
2715       return;
2716     }
2717     auto Zero = B.buildConstant(Ty, 0);
2718     replaceRegWith(MRI, Dst, Zero->getOperand(0).getReg());
2719   };
2720   return true;
2721 }
2722 
2723 bool CombinerHelper::matchRedundantAnd(MachineInstr &MI,
2724                                        Register &Replacement) {
2725   // Given
2726   //
2727   // %y:_(sN) = G_SOMETHING
2728   // %x:_(sN) = G_SOMETHING
2729   // %res:_(sN) = G_AND %x, %y
2730   //
2731   // Eliminate the G_AND when it is known that x & y == x or x & y == y.
2732   //
2733   // Patterns like this can appear as a result of legalization. E.g.
2734   //
2735   // %cmp:_(s32) = G_ICMP intpred(pred), %x(s32), %y
2736   // %one:_(s32) = G_CONSTANT i32 1
2737   // %and:_(s32) = G_AND %cmp, %one
2738   //
2739   // In this case, G_ICMP only produces a single bit, so x & 1 == x.
2740   assert(MI.getOpcode() == TargetOpcode::G_AND);
2741   if (!KB)
2742     return false;
2743 
2744   Register AndDst = MI.getOperand(0).getReg();
2745   LLT DstTy = MRI.getType(AndDst);
2746 
2747   // FIXME: This should be removed once GISelKnownBits supports vectors.
2748   if (DstTy.isVector())
2749     return false;
2750 
2751   Register LHS = MI.getOperand(1).getReg();
2752   Register RHS = MI.getOperand(2).getReg();
2753   KnownBits LHSBits = KB->getKnownBits(LHS);
2754   KnownBits RHSBits = KB->getKnownBits(RHS);
2755 
2756   // Check that x & Mask == x.
2757   // x & 1 == x, always
2758   // x & 0 == x, only if x is also 0
2759   // Meaning Mask has no effect if every bit is either one in Mask or zero in x.
2760   //
2761   // Check if we can replace AndDst with the LHS of the G_AND
2762   if (canReplaceReg(AndDst, LHS, MRI) &&
2763       (LHSBits.Zero | RHSBits.One).isAllOnes()) {
2764     Replacement = LHS;
2765     return true;
2766   }
2767 
2768   // Check if we can replace AndDst with the RHS of the G_AND
2769   if (canReplaceReg(AndDst, RHS, MRI) &&
2770       (LHSBits.One | RHSBits.Zero).isAllOnes()) {
2771     Replacement = RHS;
2772     return true;
2773   }
2774 
2775   return false;
2776 }
2777 
2778 bool CombinerHelper::matchRedundantOr(MachineInstr &MI, Register &Replacement) {
2779   // Given
2780   //
2781   // %y:_(sN) = G_SOMETHING
2782   // %x:_(sN) = G_SOMETHING
2783   // %res:_(sN) = G_OR %x, %y
2784   //
2785   // Eliminate the G_OR when it is known that x | y == x or x | y == y.
2786   assert(MI.getOpcode() == TargetOpcode::G_OR);
2787   if (!KB)
2788     return false;
2789 
2790   Register OrDst = MI.getOperand(0).getReg();
2791   LLT DstTy = MRI.getType(OrDst);
2792 
2793   // FIXME: This should be removed once GISelKnownBits supports vectors.
2794   if (DstTy.isVector())
2795     return false;
2796 
2797   Register LHS = MI.getOperand(1).getReg();
2798   Register RHS = MI.getOperand(2).getReg();
2799   KnownBits LHSBits = KB->getKnownBits(LHS);
2800   KnownBits RHSBits = KB->getKnownBits(RHS);
2801 
2802   // Check that x | Mask == x.
2803   // x | 0 == x, always
2804   // x | 1 == x, only if x is also 1
2805   // Meaning Mask has no effect if every bit is either zero in Mask or one in x.
2806   //
2807   // Check if we can replace OrDst with the LHS of the G_OR
2808   if (canReplaceReg(OrDst, LHS, MRI) &&
2809       (LHSBits.One | RHSBits.Zero).isAllOnes()) {
2810     Replacement = LHS;
2811     return true;
2812   }
2813 
2814   // Check if we can replace OrDst with the RHS of the G_OR
2815   if (canReplaceReg(OrDst, RHS, MRI) &&
2816       (LHSBits.Zero | RHSBits.One).isAllOnes()) {
2817     Replacement = RHS;
2818     return true;
2819   }
2820 
2821   return false;
2822 }
2823 
2824 bool CombinerHelper::matchRedundantSExtInReg(MachineInstr &MI) {
2825   // If the input is already sign extended, just drop the extension.
2826   Register Src = MI.getOperand(1).getReg();
2827   unsigned ExtBits = MI.getOperand(2).getImm();
2828   unsigned TypeSize = MRI.getType(Src).getScalarSizeInBits();
2829   return KB->computeNumSignBits(Src) >= (TypeSize - ExtBits + 1);
2830 }
2831 
2832 static bool isConstValidTrue(const TargetLowering &TLI, unsigned ScalarSizeBits,
2833                              int64_t Cst, bool IsVector, bool IsFP) {
2834   // For i1, Cst will always be -1 regardless of boolean contents.
2835   return (ScalarSizeBits == 1 && Cst == -1) ||
2836          isConstTrueVal(TLI, Cst, IsVector, IsFP);
2837 }
2838 
2839 bool CombinerHelper::matchNotCmp(MachineInstr &MI,
2840                                  SmallVectorImpl<Register> &RegsToNegate) {
2841   assert(MI.getOpcode() == TargetOpcode::G_XOR);
2842   LLT Ty = MRI.getType(MI.getOperand(0).getReg());
2843   const auto &TLI = *Builder.getMF().getSubtarget().getTargetLowering();
2844   Register XorSrc;
2845   Register CstReg;
2846   // We match xor(src, true) here.
2847   if (!mi_match(MI.getOperand(0).getReg(), MRI,
2848                 m_GXor(m_Reg(XorSrc), m_Reg(CstReg))))
2849     return false;
2850 
2851   if (!MRI.hasOneNonDBGUse(XorSrc))
2852     return false;
2853 
2854   // Check that XorSrc is the root of a tree of comparisons combined with ANDs
2855   // and ORs. The suffix of RegsToNegate starting from index I is used a work
2856   // list of tree nodes to visit.
2857   RegsToNegate.push_back(XorSrc);
2858   // Remember whether the comparisons are all integer or all floating point.
2859   bool IsInt = false;
2860   bool IsFP = false;
2861   for (unsigned I = 0; I < RegsToNegate.size(); ++I) {
2862     Register Reg = RegsToNegate[I];
2863     if (!MRI.hasOneNonDBGUse(Reg))
2864       return false;
2865     MachineInstr *Def = MRI.getVRegDef(Reg);
2866     switch (Def->getOpcode()) {
2867     default:
2868       // Don't match if the tree contains anything other than ANDs, ORs and
2869       // comparisons.
2870       return false;
2871     case TargetOpcode::G_ICMP:
2872       if (IsFP)
2873         return false;
2874       IsInt = true;
2875       // When we apply the combine we will invert the predicate.
2876       break;
2877     case TargetOpcode::G_FCMP:
2878       if (IsInt)
2879         return false;
2880       IsFP = true;
2881       // When we apply the combine we will invert the predicate.
2882       break;
2883     case TargetOpcode::G_AND:
2884     case TargetOpcode::G_OR:
2885       // Implement De Morgan's laws:
2886       // ~(x & y) -> ~x | ~y
2887       // ~(x | y) -> ~x & ~y
2888       // When we apply the combine we will change the opcode and recursively
2889       // negate the operands.
2890       RegsToNegate.push_back(Def->getOperand(1).getReg());
2891       RegsToNegate.push_back(Def->getOperand(2).getReg());
2892       break;
2893     }
2894   }
2895 
2896   // Now we know whether the comparisons are integer or floating point, check
2897   // the constant in the xor.
2898   int64_t Cst;
2899   if (Ty.isVector()) {
2900     MachineInstr *CstDef = MRI.getVRegDef(CstReg);
2901     auto MaybeCst = getBuildVectorConstantSplat(*CstDef, MRI);
2902     if (!MaybeCst)
2903       return false;
2904     if (!isConstValidTrue(TLI, Ty.getScalarSizeInBits(), *MaybeCst, true, IsFP))
2905       return false;
2906   } else {
2907     if (!mi_match(CstReg, MRI, m_ICst(Cst)))
2908       return false;
2909     if (!isConstValidTrue(TLI, Ty.getSizeInBits(), Cst, false, IsFP))
2910       return false;
2911   }
2912 
2913   return true;
2914 }
2915 
2916 void CombinerHelper::applyNotCmp(MachineInstr &MI,
2917                                  SmallVectorImpl<Register> &RegsToNegate) {
2918   for (Register Reg : RegsToNegate) {
2919     MachineInstr *Def = MRI.getVRegDef(Reg);
2920     Observer.changingInstr(*Def);
2921     // For each comparison, invert the opcode. For each AND and OR, change the
2922     // opcode.
2923     switch (Def->getOpcode()) {
2924     default:
2925       llvm_unreachable("Unexpected opcode");
2926     case TargetOpcode::G_ICMP:
2927     case TargetOpcode::G_FCMP: {
2928       MachineOperand &PredOp = Def->getOperand(1);
2929       CmpInst::Predicate NewP = CmpInst::getInversePredicate(
2930           (CmpInst::Predicate)PredOp.getPredicate());
2931       PredOp.setPredicate(NewP);
2932       break;
2933     }
2934     case TargetOpcode::G_AND:
2935       Def->setDesc(Builder.getTII().get(TargetOpcode::G_OR));
2936       break;
2937     case TargetOpcode::G_OR:
2938       Def->setDesc(Builder.getTII().get(TargetOpcode::G_AND));
2939       break;
2940     }
2941     Observer.changedInstr(*Def);
2942   }
2943 
2944   replaceRegWith(MRI, MI.getOperand(0).getReg(), MI.getOperand(1).getReg());
2945   MI.eraseFromParent();
2946 }
2947 
2948 bool CombinerHelper::matchXorOfAndWithSameReg(
2949     MachineInstr &MI, std::pair<Register, Register> &MatchInfo) {
2950   // Match (xor (and x, y), y) (or any of its commuted cases)
2951   assert(MI.getOpcode() == TargetOpcode::G_XOR);
2952   Register &X = MatchInfo.first;
2953   Register &Y = MatchInfo.second;
2954   Register AndReg = MI.getOperand(1).getReg();
2955   Register SharedReg = MI.getOperand(2).getReg();
2956 
2957   // Find a G_AND on either side of the G_XOR.
2958   // Look for one of
2959   //
2960   // (xor (and x, y), SharedReg)
2961   // (xor SharedReg, (and x, y))
2962   if (!mi_match(AndReg, MRI, m_GAnd(m_Reg(X), m_Reg(Y)))) {
2963     std::swap(AndReg, SharedReg);
2964     if (!mi_match(AndReg, MRI, m_GAnd(m_Reg(X), m_Reg(Y))))
2965       return false;
2966   }
2967 
2968   // Only do this if we'll eliminate the G_AND.
2969   if (!MRI.hasOneNonDBGUse(AndReg))
2970     return false;
2971 
2972   // We can combine if SharedReg is the same as either the LHS or RHS of the
2973   // G_AND.
2974   if (Y != SharedReg)
2975     std::swap(X, Y);
2976   return Y == SharedReg;
2977 }
2978 
2979 void CombinerHelper::applyXorOfAndWithSameReg(
2980     MachineInstr &MI, std::pair<Register, Register> &MatchInfo) {
2981   // Fold (xor (and x, y), y) -> (and (not x), y)
2982   Builder.setInstrAndDebugLoc(MI);
2983   Register X, Y;
2984   std::tie(X, Y) = MatchInfo;
2985   auto Not = Builder.buildNot(MRI.getType(X), X);
2986   Observer.changingInstr(MI);
2987   MI.setDesc(Builder.getTII().get(TargetOpcode::G_AND));
2988   MI.getOperand(1).setReg(Not->getOperand(0).getReg());
2989   MI.getOperand(2).setReg(Y);
2990   Observer.changedInstr(MI);
2991 }
2992 
2993 bool CombinerHelper::matchPtrAddZero(MachineInstr &MI) {
2994   auto &PtrAdd = cast<GPtrAdd>(MI);
2995   Register DstReg = PtrAdd.getReg(0);
2996   LLT Ty = MRI.getType(DstReg);
2997   const DataLayout &DL = Builder.getMF().getDataLayout();
2998 
2999   if (DL.isNonIntegralAddressSpace(Ty.getScalarType().getAddressSpace()))
3000     return false;
3001 
3002   if (Ty.isPointer()) {
3003     auto ConstVal = getIConstantVRegVal(PtrAdd.getBaseReg(), MRI);
3004     return ConstVal && *ConstVal == 0;
3005   }
3006 
3007   assert(Ty.isVector() && "Expecting a vector type");
3008   const MachineInstr *VecMI = MRI.getVRegDef(PtrAdd.getBaseReg());
3009   return isBuildVectorAllZeros(*VecMI, MRI);
3010 }
3011 
3012 void CombinerHelper::applyPtrAddZero(MachineInstr &MI) {
3013   auto &PtrAdd = cast<GPtrAdd>(MI);
3014   Builder.setInstrAndDebugLoc(PtrAdd);
3015   Builder.buildIntToPtr(PtrAdd.getReg(0), PtrAdd.getOffsetReg());
3016   PtrAdd.eraseFromParent();
3017 }
3018 
3019 /// The second source operand is known to be a power of 2.
3020 void CombinerHelper::applySimplifyURemByPow2(MachineInstr &MI) {
3021   Register DstReg = MI.getOperand(0).getReg();
3022   Register Src0 = MI.getOperand(1).getReg();
3023   Register Pow2Src1 = MI.getOperand(2).getReg();
3024   LLT Ty = MRI.getType(DstReg);
3025   Builder.setInstrAndDebugLoc(MI);
3026 
3027   // Fold (urem x, pow2) -> (and x, pow2-1)
3028   auto NegOne = Builder.buildConstant(Ty, -1);
3029   auto Add = Builder.buildAdd(Ty, Pow2Src1, NegOne);
3030   Builder.buildAnd(DstReg, Src0, Add);
3031   MI.eraseFromParent();
3032 }
3033 
3034 Optional<SmallVector<Register, 8>>
3035 CombinerHelper::findCandidatesForLoadOrCombine(const MachineInstr *Root) const {
3036   assert(Root->getOpcode() == TargetOpcode::G_OR && "Expected G_OR only!");
3037   // We want to detect if Root is part of a tree which represents a bunch
3038   // of loads being merged into a larger load. We'll try to recognize patterns
3039   // like, for example:
3040   //
3041   //  Reg   Reg
3042   //   \    /
3043   //    OR_1   Reg
3044   //     \    /
3045   //      OR_2
3046   //        \     Reg
3047   //         .. /
3048   //        Root
3049   //
3050   //  Reg   Reg   Reg   Reg
3051   //     \ /       \   /
3052   //     OR_1      OR_2
3053   //       \       /
3054   //        \    /
3055   //         ...
3056   //         Root
3057   //
3058   // Each "Reg" may have been produced by a load + some arithmetic. This
3059   // function will save each of them.
3060   SmallVector<Register, 8> RegsToVisit;
3061   SmallVector<const MachineInstr *, 7> Ors = {Root};
3062 
3063   // In the "worst" case, we're dealing with a load for each byte. So, there
3064   // are at most #bytes - 1 ORs.
3065   const unsigned MaxIter =
3066       MRI.getType(Root->getOperand(0).getReg()).getSizeInBytes() - 1;
3067   for (unsigned Iter = 0; Iter < MaxIter; ++Iter) {
3068     if (Ors.empty())
3069       break;
3070     const MachineInstr *Curr = Ors.pop_back_val();
3071     Register OrLHS = Curr->getOperand(1).getReg();
3072     Register OrRHS = Curr->getOperand(2).getReg();
3073 
3074     // In the combine, we want to elimate the entire tree.
3075     if (!MRI.hasOneNonDBGUse(OrLHS) || !MRI.hasOneNonDBGUse(OrRHS))
3076       return None;
3077 
3078     // If it's a G_OR, save it and continue to walk. If it's not, then it's
3079     // something that may be a load + arithmetic.
3080     if (const MachineInstr *Or = getOpcodeDef(TargetOpcode::G_OR, OrLHS, MRI))
3081       Ors.push_back(Or);
3082     else
3083       RegsToVisit.push_back(OrLHS);
3084     if (const MachineInstr *Or = getOpcodeDef(TargetOpcode::G_OR, OrRHS, MRI))
3085       Ors.push_back(Or);
3086     else
3087       RegsToVisit.push_back(OrRHS);
3088   }
3089 
3090   // We're going to try and merge each register into a wider power-of-2 type,
3091   // so we ought to have an even number of registers.
3092   if (RegsToVisit.empty() || RegsToVisit.size() % 2 != 0)
3093     return None;
3094   return RegsToVisit;
3095 }
3096 
3097 /// Helper function for findLoadOffsetsForLoadOrCombine.
3098 ///
3099 /// Check if \p Reg is the result of loading a \p MemSizeInBits wide value,
3100 /// and then moving that value into a specific byte offset.
3101 ///
3102 /// e.g. x[i] << 24
3103 ///
3104 /// \returns The load instruction and the byte offset it is moved into.
3105 static Optional<std::pair<GZExtLoad *, int64_t>>
3106 matchLoadAndBytePosition(Register Reg, unsigned MemSizeInBits,
3107                          const MachineRegisterInfo &MRI) {
3108   assert(MRI.hasOneNonDBGUse(Reg) &&
3109          "Expected Reg to only have one non-debug use?");
3110   Register MaybeLoad;
3111   int64_t Shift;
3112   if (!mi_match(Reg, MRI,
3113                 m_OneNonDBGUse(m_GShl(m_Reg(MaybeLoad), m_ICst(Shift))))) {
3114     Shift = 0;
3115     MaybeLoad = Reg;
3116   }
3117 
3118   if (Shift % MemSizeInBits != 0)
3119     return None;
3120 
3121   // TODO: Handle other types of loads.
3122   auto *Load = getOpcodeDef<GZExtLoad>(MaybeLoad, MRI);
3123   if (!Load)
3124     return None;
3125 
3126   if (!Load->isUnordered() || Load->getMemSizeInBits() != MemSizeInBits)
3127     return None;
3128 
3129   return std::make_pair(Load, Shift / MemSizeInBits);
3130 }
3131 
3132 Optional<std::tuple<GZExtLoad *, int64_t, GZExtLoad *>>
3133 CombinerHelper::findLoadOffsetsForLoadOrCombine(
3134     SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx,
3135     const SmallVector<Register, 8> &RegsToVisit, const unsigned MemSizeInBits) {
3136 
3137   // Each load found for the pattern. There should be one for each RegsToVisit.
3138   SmallSetVector<const MachineInstr *, 8> Loads;
3139 
3140   // The lowest index used in any load. (The lowest "i" for each x[i].)
3141   int64_t LowestIdx = INT64_MAX;
3142 
3143   // The load which uses the lowest index.
3144   GZExtLoad *LowestIdxLoad = nullptr;
3145 
3146   // Keeps track of the load indices we see. We shouldn't see any indices twice.
3147   SmallSet<int64_t, 8> SeenIdx;
3148 
3149   // Ensure each load is in the same MBB.
3150   // TODO: Support multiple MachineBasicBlocks.
3151   MachineBasicBlock *MBB = nullptr;
3152   const MachineMemOperand *MMO = nullptr;
3153 
3154   // Earliest instruction-order load in the pattern.
3155   GZExtLoad *EarliestLoad = nullptr;
3156 
3157   // Latest instruction-order load in the pattern.
3158   GZExtLoad *LatestLoad = nullptr;
3159 
3160   // Base pointer which every load should share.
3161   Register BasePtr;
3162 
3163   // We want to find a load for each register. Each load should have some
3164   // appropriate bit twiddling arithmetic. During this loop, we will also keep
3165   // track of the load which uses the lowest index. Later, we will check if we
3166   // can use its pointer in the final, combined load.
3167   for (auto Reg : RegsToVisit) {
3168     // Find the load, and find the position that it will end up in (e.g. a
3169     // shifted) value.
3170     auto LoadAndPos = matchLoadAndBytePosition(Reg, MemSizeInBits, MRI);
3171     if (!LoadAndPos)
3172       return None;
3173     GZExtLoad *Load;
3174     int64_t DstPos;
3175     std::tie(Load, DstPos) = *LoadAndPos;
3176 
3177     // TODO: Handle multiple MachineBasicBlocks. Currently not handled because
3178     // it is difficult to check for stores/calls/etc between loads.
3179     MachineBasicBlock *LoadMBB = Load->getParent();
3180     if (!MBB)
3181       MBB = LoadMBB;
3182     if (LoadMBB != MBB)
3183       return None;
3184 
3185     // Make sure that the MachineMemOperands of every seen load are compatible.
3186     auto &LoadMMO = Load->getMMO();
3187     if (!MMO)
3188       MMO = &LoadMMO;
3189     if (MMO->getAddrSpace() != LoadMMO.getAddrSpace())
3190       return None;
3191 
3192     // Find out what the base pointer and index for the load is.
3193     Register LoadPtr;
3194     int64_t Idx;
3195     if (!mi_match(Load->getOperand(1).getReg(), MRI,
3196                   m_GPtrAdd(m_Reg(LoadPtr), m_ICst(Idx)))) {
3197       LoadPtr = Load->getOperand(1).getReg();
3198       Idx = 0;
3199     }
3200 
3201     // Don't combine things like a[i], a[i] -> a bigger load.
3202     if (!SeenIdx.insert(Idx).second)
3203       return None;
3204 
3205     // Every load must share the same base pointer; don't combine things like:
3206     //
3207     // a[i], b[i + 1] -> a bigger load.
3208     if (!BasePtr.isValid())
3209       BasePtr = LoadPtr;
3210     if (BasePtr != LoadPtr)
3211       return None;
3212 
3213     if (Idx < LowestIdx) {
3214       LowestIdx = Idx;
3215       LowestIdxLoad = Load;
3216     }
3217 
3218     // Keep track of the byte offset that this load ends up at. If we have seen
3219     // the byte offset, then stop here. We do not want to combine:
3220     //
3221     // a[i] << 16, a[i + k] << 16 -> a bigger load.
3222     if (!MemOffset2Idx.try_emplace(DstPos, Idx).second)
3223       return None;
3224     Loads.insert(Load);
3225 
3226     // Keep track of the position of the earliest/latest loads in the pattern.
3227     // We will check that there are no load fold barriers between them later
3228     // on.
3229     //
3230     // FIXME: Is there a better way to check for load fold barriers?
3231     if (!EarliestLoad || dominates(*Load, *EarliestLoad))
3232       EarliestLoad = Load;
3233     if (!LatestLoad || dominates(*LatestLoad, *Load))
3234       LatestLoad = Load;
3235   }
3236 
3237   // We found a load for each register. Let's check if each load satisfies the
3238   // pattern.
3239   assert(Loads.size() == RegsToVisit.size() &&
3240          "Expected to find a load for each register?");
3241   assert(EarliestLoad != LatestLoad && EarliestLoad &&
3242          LatestLoad && "Expected at least two loads?");
3243 
3244   // Check if there are any stores, calls, etc. between any of the loads. If
3245   // there are, then we can't safely perform the combine.
3246   //
3247   // MaxIter is chosen based off the (worst case) number of iterations it
3248   // typically takes to succeed in the LLVM test suite plus some padding.
3249   //
3250   // FIXME: Is there a better way to check for load fold barriers?
3251   const unsigned MaxIter = 20;
3252   unsigned Iter = 0;
3253   for (const auto &MI : instructionsWithoutDebug(EarliestLoad->getIterator(),
3254                                                  LatestLoad->getIterator())) {
3255     if (Loads.count(&MI))
3256       continue;
3257     if (MI.isLoadFoldBarrier())
3258       return None;
3259     if (Iter++ == MaxIter)
3260       return None;
3261   }
3262 
3263   return std::make_tuple(LowestIdxLoad, LowestIdx, LatestLoad);
3264 }
3265 
3266 bool CombinerHelper::matchLoadOrCombine(
3267     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
3268   assert(MI.getOpcode() == TargetOpcode::G_OR);
3269   MachineFunction &MF = *MI.getMF();
3270   // Assuming a little-endian target, transform:
3271   //  s8 *a = ...
3272   //  s32 val = a[0] | (a[1] << 8) | (a[2] << 16) | (a[3] << 24)
3273   // =>
3274   //  s32 val = *((i32)a)
3275   //
3276   //  s8 *a = ...
3277   //  s32 val = (a[0] << 24) | (a[1] << 16) | (a[2] << 8) | a[3]
3278   // =>
3279   //  s32 val = BSWAP(*((s32)a))
3280   Register Dst = MI.getOperand(0).getReg();
3281   LLT Ty = MRI.getType(Dst);
3282   if (Ty.isVector())
3283     return false;
3284 
3285   // We need to combine at least two loads into this type. Since the smallest
3286   // possible load is into a byte, we need at least a 16-bit wide type.
3287   const unsigned WideMemSizeInBits = Ty.getSizeInBits();
3288   if (WideMemSizeInBits < 16 || WideMemSizeInBits % 8 != 0)
3289     return false;
3290 
3291   // Match a collection of non-OR instructions in the pattern.
3292   auto RegsToVisit = findCandidatesForLoadOrCombine(&MI);
3293   if (!RegsToVisit)
3294     return false;
3295 
3296   // We have a collection of non-OR instructions. Figure out how wide each of
3297   // the small loads should be based off of the number of potential loads we
3298   // found.
3299   const unsigned NarrowMemSizeInBits = WideMemSizeInBits / RegsToVisit->size();
3300   if (NarrowMemSizeInBits % 8 != 0)
3301     return false;
3302 
3303   // Check if each register feeding into each OR is a load from the same
3304   // base pointer + some arithmetic.
3305   //
3306   // e.g. a[0], a[1] << 8, a[2] << 16, etc.
3307   //
3308   // Also verify that each of these ends up putting a[i] into the same memory
3309   // offset as a load into a wide type would.
3310   SmallDenseMap<int64_t, int64_t, 8> MemOffset2Idx;
3311   GZExtLoad *LowestIdxLoad, *LatestLoad;
3312   int64_t LowestIdx;
3313   auto MaybeLoadInfo = findLoadOffsetsForLoadOrCombine(
3314       MemOffset2Idx, *RegsToVisit, NarrowMemSizeInBits);
3315   if (!MaybeLoadInfo)
3316     return false;
3317   std::tie(LowestIdxLoad, LowestIdx, LatestLoad) = *MaybeLoadInfo;
3318 
3319   // We have a bunch of loads being OR'd together. Using the addresses + offsets
3320   // we found before, check if this corresponds to a big or little endian byte
3321   // pattern. If it does, then we can represent it using a load + possibly a
3322   // BSWAP.
3323   bool IsBigEndianTarget = MF.getDataLayout().isBigEndian();
3324   Optional<bool> IsBigEndian = isBigEndian(MemOffset2Idx, LowestIdx);
3325   if (!IsBigEndian.hasValue())
3326     return false;
3327   bool NeedsBSwap = IsBigEndianTarget != *IsBigEndian;
3328   if (NeedsBSwap && !isLegalOrBeforeLegalizer({TargetOpcode::G_BSWAP, {Ty}}))
3329     return false;
3330 
3331   // Make sure that the load from the lowest index produces offset 0 in the
3332   // final value.
3333   //
3334   // This ensures that we won't combine something like this:
3335   //
3336   // load x[i] -> byte 2
3337   // load x[i+1] -> byte 0 ---> wide_load x[i]
3338   // load x[i+2] -> byte 1
3339   const unsigned NumLoadsInTy = WideMemSizeInBits / NarrowMemSizeInBits;
3340   const unsigned ZeroByteOffset =
3341       *IsBigEndian
3342           ? bigEndianByteAt(NumLoadsInTy, 0)
3343           : littleEndianByteAt(NumLoadsInTy, 0);
3344   auto ZeroOffsetIdx = MemOffset2Idx.find(ZeroByteOffset);
3345   if (ZeroOffsetIdx == MemOffset2Idx.end() ||
3346       ZeroOffsetIdx->second != LowestIdx)
3347     return false;
3348 
3349   // We wil reuse the pointer from the load which ends up at byte offset 0. It
3350   // may not use index 0.
3351   Register Ptr = LowestIdxLoad->getPointerReg();
3352   const MachineMemOperand &MMO = LowestIdxLoad->getMMO();
3353   LegalityQuery::MemDesc MMDesc(MMO);
3354   MMDesc.MemoryTy = Ty;
3355   if (!isLegalOrBeforeLegalizer(
3356           {TargetOpcode::G_LOAD, {Ty, MRI.getType(Ptr)}, {MMDesc}}))
3357     return false;
3358   auto PtrInfo = MMO.getPointerInfo();
3359   auto *NewMMO = MF.getMachineMemOperand(&MMO, PtrInfo, WideMemSizeInBits / 8);
3360 
3361   // Load must be allowed and fast on the target.
3362   LLVMContext &C = MF.getFunction().getContext();
3363   auto &DL = MF.getDataLayout();
3364   bool Fast = false;
3365   if (!getTargetLowering().allowsMemoryAccess(C, DL, Ty, *NewMMO, &Fast) ||
3366       !Fast)
3367     return false;
3368 
3369   MatchInfo = [=](MachineIRBuilder &MIB) {
3370     MIB.setInstrAndDebugLoc(*LatestLoad);
3371     Register LoadDst = NeedsBSwap ? MRI.cloneVirtualRegister(Dst) : Dst;
3372     MIB.buildLoad(LoadDst, Ptr, *NewMMO);
3373     if (NeedsBSwap)
3374       MIB.buildBSwap(Dst, LoadDst);
3375   };
3376   return true;
3377 }
3378 
3379 /// Check if the store \p Store is a truncstore that can be merged. That is,
3380 /// it's a store of a shifted value of \p SrcVal. If \p SrcVal is an empty
3381 /// Register then it does not need to match and SrcVal is set to the source
3382 /// value found.
3383 /// On match, returns the start byte offset of the \p SrcVal that is being
3384 /// stored.
3385 static Optional<int64_t> getTruncStoreByteOffset(GStore &Store, Register &SrcVal,
3386                                                  MachineRegisterInfo &MRI) {
3387   Register TruncVal;
3388   if (!mi_match(Store.getValueReg(), MRI, m_GTrunc(m_Reg(TruncVal))))
3389     return None;
3390 
3391   // The shift amount must be a constant multiple of the narrow type.
3392   // It is translated to the offset address in the wide source value "y".
3393   //
3394   // x = G_LSHR y, ShiftAmtC
3395   // s8 z = G_TRUNC x
3396   // store z, ...
3397   Register FoundSrcVal;
3398   int64_t ShiftAmt;
3399   if (!mi_match(TruncVal, MRI,
3400                 m_any_of(m_GLShr(m_Reg(FoundSrcVal), m_ICst(ShiftAmt)),
3401                          m_GAShr(m_Reg(FoundSrcVal), m_ICst(ShiftAmt))))) {
3402     if (!SrcVal.isValid() || TruncVal == SrcVal) {
3403       if (!SrcVal.isValid())
3404         SrcVal = TruncVal;
3405       return 0; // If it's the lowest index store.
3406     }
3407     return None;
3408   }
3409 
3410   unsigned NarrowBits = Store.getMMO().getMemoryType().getScalarSizeInBits();
3411   if (ShiftAmt % NarrowBits!= 0)
3412     return None;
3413   const unsigned Offset = ShiftAmt / NarrowBits;
3414 
3415   if (SrcVal.isValid() && FoundSrcVal != SrcVal)
3416     return None;
3417 
3418   if (!SrcVal.isValid())
3419     SrcVal = FoundSrcVal;
3420   else if (MRI.getType(SrcVal) != MRI.getType(FoundSrcVal))
3421     return None;
3422   return Offset;
3423 }
3424 
3425 /// Match a pattern where a wide type scalar value is stored by several narrow
3426 /// stores. Fold it into a single store or a BSWAP and a store if the targets
3427 /// supports it.
3428 ///
3429 /// Assuming little endian target:
3430 ///  i8 *p = ...
3431 ///  i32 val = ...
3432 ///  p[0] = (val >> 0) & 0xFF;
3433 ///  p[1] = (val >> 8) & 0xFF;
3434 ///  p[2] = (val >> 16) & 0xFF;
3435 ///  p[3] = (val >> 24) & 0xFF;
3436 /// =>
3437 ///  *((i32)p) = val;
3438 ///
3439 ///  i8 *p = ...
3440 ///  i32 val = ...
3441 ///  p[0] = (val >> 24) & 0xFF;
3442 ///  p[1] = (val >> 16) & 0xFF;
3443 ///  p[2] = (val >> 8) & 0xFF;
3444 ///  p[3] = (val >> 0) & 0xFF;
3445 /// =>
3446 ///  *((i32)p) = BSWAP(val);
3447 bool CombinerHelper::matchTruncStoreMerge(MachineInstr &MI,
3448                                           MergeTruncStoresInfo &MatchInfo) {
3449   auto &StoreMI = cast<GStore>(MI);
3450   LLT MemTy = StoreMI.getMMO().getMemoryType();
3451 
3452   // We only handle merging simple stores of 1-4 bytes.
3453   if (!MemTy.isScalar())
3454     return false;
3455   switch (MemTy.getSizeInBits()) {
3456   case 8:
3457   case 16:
3458   case 32:
3459     break;
3460   default:
3461     return false;
3462   }
3463   if (!StoreMI.isSimple())
3464     return false;
3465 
3466   // We do a simple search for mergeable stores prior to this one.
3467   // Any potential alias hazard along the way terminates the search.
3468   SmallVector<GStore *> FoundStores;
3469 
3470   // We're looking for:
3471   // 1) a (store(trunc(...)))
3472   // 2) of an LSHR/ASHR of a single wide value, by the appropriate shift to get
3473   //    the partial value stored.
3474   // 3) where the offsets form either a little or big-endian sequence.
3475 
3476   auto &LastStore = StoreMI;
3477 
3478   // The single base pointer that all stores must use.
3479   Register BaseReg;
3480   int64_t LastOffset;
3481   if (!mi_match(LastStore.getPointerReg(), MRI,
3482                 m_GPtrAdd(m_Reg(BaseReg), m_ICst(LastOffset)))) {
3483     BaseReg = LastStore.getPointerReg();
3484     LastOffset = 0;
3485   }
3486 
3487   GStore *LowestIdxStore = &LastStore;
3488   int64_t LowestIdxOffset = LastOffset;
3489 
3490   Register WideSrcVal;
3491   auto LowestShiftAmt = getTruncStoreByteOffset(LastStore, WideSrcVal, MRI);
3492   if (!LowestShiftAmt)
3493     return false; // Didn't match a trunc.
3494   assert(WideSrcVal.isValid());
3495 
3496   LLT WideStoreTy = MRI.getType(WideSrcVal);
3497   // The wide type might not be a multiple of the memory type, e.g. s48 and s32.
3498   if (WideStoreTy.getSizeInBits() % MemTy.getSizeInBits() != 0)
3499     return false;
3500   const unsigned NumStoresRequired =
3501       WideStoreTy.getSizeInBits() / MemTy.getSizeInBits();
3502 
3503   SmallVector<int64_t, 8> OffsetMap(NumStoresRequired, INT64_MAX);
3504   OffsetMap[*LowestShiftAmt] = LastOffset;
3505   FoundStores.emplace_back(&LastStore);
3506 
3507   // Search the block up for more stores.
3508   // We use a search threshold of 10 instructions here because the combiner
3509   // works top-down within a block, and we don't want to search an unbounded
3510   // number of predecessor instructions trying to find matching stores.
3511   // If we moved this optimization into a separate pass then we could probably
3512   // use a more efficient search without having a hard-coded threshold.
3513   const int MaxInstsToCheck = 10;
3514   int NumInstsChecked = 0;
3515   for (auto II = ++LastStore.getReverseIterator();
3516        II != LastStore.getParent()->rend() && NumInstsChecked < MaxInstsToCheck;
3517        ++II) {
3518     NumInstsChecked++;
3519     GStore *NewStore;
3520     if ((NewStore = dyn_cast<GStore>(&*II))) {
3521       if (NewStore->getMMO().getMemoryType() != MemTy || !NewStore->isSimple())
3522         break;
3523     } else if (II->isLoadFoldBarrier() || II->mayLoad()) {
3524       break;
3525     } else {
3526       continue; // This is a safe instruction we can look past.
3527     }
3528 
3529     Register NewBaseReg;
3530     int64_t MemOffset;
3531     // Check we're storing to the same base + some offset.
3532     if (!mi_match(NewStore->getPointerReg(), MRI,
3533                   m_GPtrAdd(m_Reg(NewBaseReg), m_ICst(MemOffset)))) {
3534       NewBaseReg = NewStore->getPointerReg();
3535       MemOffset = 0;
3536     }
3537     if (BaseReg != NewBaseReg)
3538       break;
3539 
3540     auto ShiftByteOffset = getTruncStoreByteOffset(*NewStore, WideSrcVal, MRI);
3541     if (!ShiftByteOffset)
3542       break;
3543     if (MemOffset < LowestIdxOffset) {
3544       LowestIdxOffset = MemOffset;
3545       LowestIdxStore = NewStore;
3546     }
3547 
3548     // Map the offset in the store and the offset in the combined value, and
3549     // early return if it has been set before.
3550     if (*ShiftByteOffset < 0 || *ShiftByteOffset >= NumStoresRequired ||
3551         OffsetMap[*ShiftByteOffset] != INT64_MAX)
3552       break;
3553     OffsetMap[*ShiftByteOffset] = MemOffset;
3554 
3555     FoundStores.emplace_back(NewStore);
3556     // Reset counter since we've found a matching inst.
3557     NumInstsChecked = 0;
3558     if (FoundStores.size() == NumStoresRequired)
3559       break;
3560   }
3561 
3562   if (FoundStores.size() != NumStoresRequired) {
3563     return false;
3564   }
3565 
3566   const auto &DL = LastStore.getMF()->getDataLayout();
3567   auto &C = LastStore.getMF()->getFunction().getContext();
3568   // Check that a store of the wide type is both allowed and fast on the target
3569   bool Fast = false;
3570   bool Allowed = getTargetLowering().allowsMemoryAccess(
3571       C, DL, WideStoreTy, LowestIdxStore->getMMO(), &Fast);
3572   if (!Allowed || !Fast)
3573     return false;
3574 
3575   // Check if the pieces of the value are going to the expected places in memory
3576   // to merge the stores.
3577   unsigned NarrowBits = MemTy.getScalarSizeInBits();
3578   auto checkOffsets = [&](bool MatchLittleEndian) {
3579     if (MatchLittleEndian) {
3580       for (unsigned i = 0; i != NumStoresRequired; ++i)
3581         if (OffsetMap[i] != i * (NarrowBits / 8) + LowestIdxOffset)
3582           return false;
3583     } else { // MatchBigEndian by reversing loop counter.
3584       for (unsigned i = 0, j = NumStoresRequired - 1; i != NumStoresRequired;
3585            ++i, --j)
3586         if (OffsetMap[j] != i * (NarrowBits / 8) + LowestIdxOffset)
3587           return false;
3588     }
3589     return true;
3590   };
3591 
3592   // Check if the offsets line up for the native data layout of this target.
3593   bool NeedBswap = false;
3594   bool NeedRotate = false;
3595   if (!checkOffsets(DL.isLittleEndian())) {
3596     // Special-case: check if byte offsets line up for the opposite endian.
3597     if (NarrowBits == 8 && checkOffsets(DL.isBigEndian()))
3598       NeedBswap = true;
3599     else if (NumStoresRequired == 2 && checkOffsets(DL.isBigEndian()))
3600       NeedRotate = true;
3601     else
3602       return false;
3603   }
3604 
3605   if (NeedBswap &&
3606       !isLegalOrBeforeLegalizer({TargetOpcode::G_BSWAP, {WideStoreTy}}))
3607     return false;
3608   if (NeedRotate &&
3609       !isLegalOrBeforeLegalizer({TargetOpcode::G_ROTR, {WideStoreTy}}))
3610     return false;
3611 
3612   MatchInfo.NeedBSwap = NeedBswap;
3613   MatchInfo.NeedRotate = NeedRotate;
3614   MatchInfo.LowestIdxStore = LowestIdxStore;
3615   MatchInfo.WideSrcVal = WideSrcVal;
3616   MatchInfo.FoundStores = std::move(FoundStores);
3617   return true;
3618 }
3619 
3620 void CombinerHelper::applyTruncStoreMerge(MachineInstr &MI,
3621                                           MergeTruncStoresInfo &MatchInfo) {
3622 
3623   Builder.setInstrAndDebugLoc(MI);
3624   Register WideSrcVal = MatchInfo.WideSrcVal;
3625   LLT WideStoreTy = MRI.getType(WideSrcVal);
3626 
3627   if (MatchInfo.NeedBSwap) {
3628     WideSrcVal = Builder.buildBSwap(WideStoreTy, WideSrcVal).getReg(0);
3629   } else if (MatchInfo.NeedRotate) {
3630     assert(WideStoreTy.getSizeInBits() % 2 == 0 &&
3631            "Unexpected type for rotate");
3632     auto RotAmt =
3633         Builder.buildConstant(WideStoreTy, WideStoreTy.getSizeInBits() / 2);
3634     WideSrcVal =
3635         Builder.buildRotateRight(WideStoreTy, WideSrcVal, RotAmt).getReg(0);
3636   }
3637 
3638   Builder.buildStore(WideSrcVal, MatchInfo.LowestIdxStore->getPointerReg(),
3639                      MatchInfo.LowestIdxStore->getMMO().getPointerInfo(),
3640                      MatchInfo.LowestIdxStore->getMMO().getAlign());
3641 
3642   // Erase the old stores.
3643   for (auto *ST : MatchInfo.FoundStores)
3644     ST->eraseFromParent();
3645 }
3646 
3647 bool CombinerHelper::matchExtendThroughPhis(MachineInstr &MI,
3648                                             MachineInstr *&ExtMI) {
3649   assert(MI.getOpcode() == TargetOpcode::G_PHI);
3650 
3651   Register DstReg = MI.getOperand(0).getReg();
3652 
3653   // TODO: Extending a vector may be expensive, don't do this until heuristics
3654   // are better.
3655   if (MRI.getType(DstReg).isVector())
3656     return false;
3657 
3658   // Try to match a phi, whose only use is an extend.
3659   if (!MRI.hasOneNonDBGUse(DstReg))
3660     return false;
3661   ExtMI = &*MRI.use_instr_nodbg_begin(DstReg);
3662   switch (ExtMI->getOpcode()) {
3663   case TargetOpcode::G_ANYEXT:
3664     return true; // G_ANYEXT is usually free.
3665   case TargetOpcode::G_ZEXT:
3666   case TargetOpcode::G_SEXT:
3667     break;
3668   default:
3669     return false;
3670   }
3671 
3672   // If the target is likely to fold this extend away, don't propagate.
3673   if (Builder.getTII().isExtendLikelyToBeFolded(*ExtMI, MRI))
3674     return false;
3675 
3676   // We don't want to propagate the extends unless there's a good chance that
3677   // they'll be optimized in some way.
3678   // Collect the unique incoming values.
3679   SmallPtrSet<MachineInstr *, 4> InSrcs;
3680   for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
3681     auto *DefMI = getDefIgnoringCopies(MI.getOperand(Idx).getReg(), MRI);
3682     switch (DefMI->getOpcode()) {
3683     case TargetOpcode::G_LOAD:
3684     case TargetOpcode::G_TRUNC:
3685     case TargetOpcode::G_SEXT:
3686     case TargetOpcode::G_ZEXT:
3687     case TargetOpcode::G_ANYEXT:
3688     case TargetOpcode::G_CONSTANT:
3689       InSrcs.insert(getDefIgnoringCopies(MI.getOperand(Idx).getReg(), MRI));
3690       // Don't try to propagate if there are too many places to create new
3691       // extends, chances are it'll increase code size.
3692       if (InSrcs.size() > 2)
3693         return false;
3694       break;
3695     default:
3696       return false;
3697     }
3698   }
3699   return true;
3700 }
3701 
3702 void CombinerHelper::applyExtendThroughPhis(MachineInstr &MI,
3703                                             MachineInstr *&ExtMI) {
3704   assert(MI.getOpcode() == TargetOpcode::G_PHI);
3705   Register DstReg = ExtMI->getOperand(0).getReg();
3706   LLT ExtTy = MRI.getType(DstReg);
3707 
3708   // Propagate the extension into the block of each incoming reg's block.
3709   // Use a SetVector here because PHIs can have duplicate edges, and we want
3710   // deterministic iteration order.
3711   SmallSetVector<MachineInstr *, 8> SrcMIs;
3712   SmallDenseMap<MachineInstr *, MachineInstr *, 8> OldToNewSrcMap;
3713   for (unsigned SrcIdx = 1; SrcIdx < MI.getNumOperands(); SrcIdx += 2) {
3714     auto *SrcMI = MRI.getVRegDef(MI.getOperand(SrcIdx).getReg());
3715     if (!SrcMIs.insert(SrcMI))
3716       continue;
3717 
3718     // Build an extend after each src inst.
3719     auto *MBB = SrcMI->getParent();
3720     MachineBasicBlock::iterator InsertPt = ++SrcMI->getIterator();
3721     if (InsertPt != MBB->end() && InsertPt->isPHI())
3722       InsertPt = MBB->getFirstNonPHI();
3723 
3724     Builder.setInsertPt(*SrcMI->getParent(), InsertPt);
3725     Builder.setDebugLoc(MI.getDebugLoc());
3726     auto NewExt = Builder.buildExtOrTrunc(ExtMI->getOpcode(), ExtTy,
3727                                           SrcMI->getOperand(0).getReg());
3728     OldToNewSrcMap[SrcMI] = NewExt;
3729   }
3730 
3731   // Create a new phi with the extended inputs.
3732   Builder.setInstrAndDebugLoc(MI);
3733   auto NewPhi = Builder.buildInstrNoInsert(TargetOpcode::G_PHI);
3734   NewPhi.addDef(DstReg);
3735   for (unsigned SrcIdx = 1; SrcIdx < MI.getNumOperands(); ++SrcIdx) {
3736     auto &MO = MI.getOperand(SrcIdx);
3737     if (!MO.isReg()) {
3738       NewPhi.addMBB(MO.getMBB());
3739       continue;
3740     }
3741     auto *NewSrc = OldToNewSrcMap[MRI.getVRegDef(MO.getReg())];
3742     NewPhi.addUse(NewSrc->getOperand(0).getReg());
3743   }
3744   Builder.insertInstr(NewPhi);
3745   ExtMI->eraseFromParent();
3746 }
3747 
3748 bool CombinerHelper::matchExtractVecEltBuildVec(MachineInstr &MI,
3749                                                 Register &Reg) {
3750   assert(MI.getOpcode() == TargetOpcode::G_EXTRACT_VECTOR_ELT);
3751   // If we have a constant index, look for a G_BUILD_VECTOR source
3752   // and find the source register that the index maps to.
3753   Register SrcVec = MI.getOperand(1).getReg();
3754   LLT SrcTy = MRI.getType(SrcVec);
3755   if (!isLegalOrBeforeLegalizer(
3756           {TargetOpcode::G_BUILD_VECTOR, {SrcTy, SrcTy.getElementType()}}))
3757     return false;
3758 
3759   auto Cst = getIConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI);
3760   if (!Cst || Cst->Value.getZExtValue() >= SrcTy.getNumElements())
3761     return false;
3762 
3763   unsigned VecIdx = Cst->Value.getZExtValue();
3764   MachineInstr *BuildVecMI =
3765       getOpcodeDef(TargetOpcode::G_BUILD_VECTOR, SrcVec, MRI);
3766   if (!BuildVecMI) {
3767     BuildVecMI = getOpcodeDef(TargetOpcode::G_BUILD_VECTOR_TRUNC, SrcVec, MRI);
3768     if (!BuildVecMI)
3769       return false;
3770     LLT ScalarTy = MRI.getType(BuildVecMI->getOperand(1).getReg());
3771     if (!isLegalOrBeforeLegalizer(
3772             {TargetOpcode::G_BUILD_VECTOR_TRUNC, {SrcTy, ScalarTy}}))
3773       return false;
3774   }
3775 
3776   EVT Ty(getMVTForLLT(SrcTy));
3777   if (!MRI.hasOneNonDBGUse(SrcVec) &&
3778       !getTargetLowering().aggressivelyPreferBuildVectorSources(Ty))
3779     return false;
3780 
3781   Reg = BuildVecMI->getOperand(VecIdx + 1).getReg();
3782   return true;
3783 }
3784 
3785 void CombinerHelper::applyExtractVecEltBuildVec(MachineInstr &MI,
3786                                                 Register &Reg) {
3787   // Check the type of the register, since it may have come from a
3788   // G_BUILD_VECTOR_TRUNC.
3789   LLT ScalarTy = MRI.getType(Reg);
3790   Register DstReg = MI.getOperand(0).getReg();
3791   LLT DstTy = MRI.getType(DstReg);
3792 
3793   Builder.setInstrAndDebugLoc(MI);
3794   if (ScalarTy != DstTy) {
3795     assert(ScalarTy.getSizeInBits() > DstTy.getSizeInBits());
3796     Builder.buildTrunc(DstReg, Reg);
3797     MI.eraseFromParent();
3798     return;
3799   }
3800   replaceSingleDefInstWithReg(MI, Reg);
3801 }
3802 
3803 bool CombinerHelper::matchExtractAllEltsFromBuildVector(
3804     MachineInstr &MI,
3805     SmallVectorImpl<std::pair<Register, MachineInstr *>> &SrcDstPairs) {
3806   assert(MI.getOpcode() == TargetOpcode::G_BUILD_VECTOR);
3807   // This combine tries to find build_vector's which have every source element
3808   // extracted using G_EXTRACT_VECTOR_ELT. This can happen when transforms like
3809   // the masked load scalarization is run late in the pipeline. There's already
3810   // a combine for a similar pattern starting from the extract, but that
3811   // doesn't attempt to do it if there are multiple uses of the build_vector,
3812   // which in this case is true. Starting the combine from the build_vector
3813   // feels more natural than trying to find sibling nodes of extracts.
3814   // E.g.
3815   //  %vec(<4 x s32>) = G_BUILD_VECTOR %s1(s32), %s2, %s3, %s4
3816   //  %ext1 = G_EXTRACT_VECTOR_ELT %vec, 0
3817   //  %ext2 = G_EXTRACT_VECTOR_ELT %vec, 1
3818   //  %ext3 = G_EXTRACT_VECTOR_ELT %vec, 2
3819   //  %ext4 = G_EXTRACT_VECTOR_ELT %vec, 3
3820   // ==>
3821   // replace ext{1,2,3,4} with %s{1,2,3,4}
3822 
3823   Register DstReg = MI.getOperand(0).getReg();
3824   LLT DstTy = MRI.getType(DstReg);
3825   unsigned NumElts = DstTy.getNumElements();
3826 
3827   SmallBitVector ExtractedElts(NumElts);
3828   for (auto &II : make_range(MRI.use_instr_nodbg_begin(DstReg),
3829                              MRI.use_instr_nodbg_end())) {
3830     if (II.getOpcode() != TargetOpcode::G_EXTRACT_VECTOR_ELT)
3831       return false;
3832     auto Cst = getIConstantVRegVal(II.getOperand(2).getReg(), MRI);
3833     if (!Cst)
3834       return false;
3835     unsigned Idx = Cst.getValue().getZExtValue();
3836     if (Idx >= NumElts)
3837       return false; // Out of range.
3838     ExtractedElts.set(Idx);
3839     SrcDstPairs.emplace_back(
3840         std::make_pair(MI.getOperand(Idx + 1).getReg(), &II));
3841   }
3842   // Match if every element was extracted.
3843   return ExtractedElts.all();
3844 }
3845 
3846 void CombinerHelper::applyExtractAllEltsFromBuildVector(
3847     MachineInstr &MI,
3848     SmallVectorImpl<std::pair<Register, MachineInstr *>> &SrcDstPairs) {
3849   assert(MI.getOpcode() == TargetOpcode::G_BUILD_VECTOR);
3850   for (auto &Pair : SrcDstPairs) {
3851     auto *ExtMI = Pair.second;
3852     replaceRegWith(MRI, ExtMI->getOperand(0).getReg(), Pair.first);
3853     ExtMI->eraseFromParent();
3854   }
3855   MI.eraseFromParent();
3856 }
3857 
3858 void CombinerHelper::applyBuildFn(
3859     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
3860   Builder.setInstrAndDebugLoc(MI);
3861   MatchInfo(Builder);
3862   MI.eraseFromParent();
3863 }
3864 
3865 void CombinerHelper::applyBuildFnNoErase(
3866     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
3867   Builder.setInstrAndDebugLoc(MI);
3868   MatchInfo(Builder);
3869 }
3870 
3871 /// Match an FSHL or FSHR that can be combined to a ROTR or ROTL rotate.
3872 bool CombinerHelper::matchFunnelShiftToRotate(MachineInstr &MI) {
3873   unsigned Opc = MI.getOpcode();
3874   assert(Opc == TargetOpcode::G_FSHL || Opc == TargetOpcode::G_FSHR);
3875   Register X = MI.getOperand(1).getReg();
3876   Register Y = MI.getOperand(2).getReg();
3877   if (X != Y)
3878     return false;
3879   unsigned RotateOpc =
3880       Opc == TargetOpcode::G_FSHL ? TargetOpcode::G_ROTL : TargetOpcode::G_ROTR;
3881   return isLegalOrBeforeLegalizer({RotateOpc, {MRI.getType(X), MRI.getType(Y)}});
3882 }
3883 
3884 void CombinerHelper::applyFunnelShiftToRotate(MachineInstr &MI) {
3885   unsigned Opc = MI.getOpcode();
3886   assert(Opc == TargetOpcode::G_FSHL || Opc == TargetOpcode::G_FSHR);
3887   bool IsFSHL = Opc == TargetOpcode::G_FSHL;
3888   Observer.changingInstr(MI);
3889   MI.setDesc(Builder.getTII().get(IsFSHL ? TargetOpcode::G_ROTL
3890                                          : TargetOpcode::G_ROTR));
3891   MI.RemoveOperand(2);
3892   Observer.changedInstr(MI);
3893 }
3894 
3895 // Fold (rot x, c) -> (rot x, c % BitSize)
3896 bool CombinerHelper::matchRotateOutOfRange(MachineInstr &MI) {
3897   assert(MI.getOpcode() == TargetOpcode::G_ROTL ||
3898          MI.getOpcode() == TargetOpcode::G_ROTR);
3899   unsigned Bitsize =
3900       MRI.getType(MI.getOperand(0).getReg()).getScalarSizeInBits();
3901   Register AmtReg = MI.getOperand(2).getReg();
3902   bool OutOfRange = false;
3903   auto MatchOutOfRange = [Bitsize, &OutOfRange](const Constant *C) {
3904     if (auto *CI = dyn_cast<ConstantInt>(C))
3905       OutOfRange |= CI->getValue().uge(Bitsize);
3906     return true;
3907   };
3908   return matchUnaryPredicate(MRI, AmtReg, MatchOutOfRange) && OutOfRange;
3909 }
3910 
3911 void CombinerHelper::applyRotateOutOfRange(MachineInstr &MI) {
3912   assert(MI.getOpcode() == TargetOpcode::G_ROTL ||
3913          MI.getOpcode() == TargetOpcode::G_ROTR);
3914   unsigned Bitsize =
3915       MRI.getType(MI.getOperand(0).getReg()).getScalarSizeInBits();
3916   Builder.setInstrAndDebugLoc(MI);
3917   Register Amt = MI.getOperand(2).getReg();
3918   LLT AmtTy = MRI.getType(Amt);
3919   auto Bits = Builder.buildConstant(AmtTy, Bitsize);
3920   Amt = Builder.buildURem(AmtTy, MI.getOperand(2).getReg(), Bits).getReg(0);
3921   Observer.changingInstr(MI);
3922   MI.getOperand(2).setReg(Amt);
3923   Observer.changedInstr(MI);
3924 }
3925 
3926 bool CombinerHelper::matchICmpToTrueFalseKnownBits(MachineInstr &MI,
3927                                                    int64_t &MatchInfo) {
3928   assert(MI.getOpcode() == TargetOpcode::G_ICMP);
3929   auto Pred = static_cast<CmpInst::Predicate>(MI.getOperand(1).getPredicate());
3930   auto KnownLHS = KB->getKnownBits(MI.getOperand(2).getReg());
3931   auto KnownRHS = KB->getKnownBits(MI.getOperand(3).getReg());
3932   Optional<bool> KnownVal;
3933   switch (Pred) {
3934   default:
3935     llvm_unreachable("Unexpected G_ICMP predicate?");
3936   case CmpInst::ICMP_EQ:
3937     KnownVal = KnownBits::eq(KnownLHS, KnownRHS);
3938     break;
3939   case CmpInst::ICMP_NE:
3940     KnownVal = KnownBits::ne(KnownLHS, KnownRHS);
3941     break;
3942   case CmpInst::ICMP_SGE:
3943     KnownVal = KnownBits::sge(KnownLHS, KnownRHS);
3944     break;
3945   case CmpInst::ICMP_SGT:
3946     KnownVal = KnownBits::sgt(KnownLHS, KnownRHS);
3947     break;
3948   case CmpInst::ICMP_SLE:
3949     KnownVal = KnownBits::sle(KnownLHS, KnownRHS);
3950     break;
3951   case CmpInst::ICMP_SLT:
3952     KnownVal = KnownBits::slt(KnownLHS, KnownRHS);
3953     break;
3954   case CmpInst::ICMP_UGE:
3955     KnownVal = KnownBits::uge(KnownLHS, KnownRHS);
3956     break;
3957   case CmpInst::ICMP_UGT:
3958     KnownVal = KnownBits::ugt(KnownLHS, KnownRHS);
3959     break;
3960   case CmpInst::ICMP_ULE:
3961     KnownVal = KnownBits::ule(KnownLHS, KnownRHS);
3962     break;
3963   case CmpInst::ICMP_ULT:
3964     KnownVal = KnownBits::ult(KnownLHS, KnownRHS);
3965     break;
3966   }
3967   if (!KnownVal)
3968     return false;
3969   MatchInfo =
3970       *KnownVal
3971           ? getICmpTrueVal(getTargetLowering(),
3972                            /*IsVector = */
3973                            MRI.getType(MI.getOperand(0).getReg()).isVector(),
3974                            /* IsFP = */ false)
3975           : 0;
3976   return true;
3977 }
3978 
3979 bool CombinerHelper::matchICmpToLHSKnownBits(
3980     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
3981   assert(MI.getOpcode() == TargetOpcode::G_ICMP);
3982   // Given:
3983   //
3984   // %x = G_WHATEVER (... x is known to be 0 or 1 ...)
3985   // %cmp = G_ICMP ne %x, 0
3986   //
3987   // Or:
3988   //
3989   // %x = G_WHATEVER (... x is known to be 0 or 1 ...)
3990   // %cmp = G_ICMP eq %x, 1
3991   //
3992   // We can replace %cmp with %x assuming true is 1 on the target.
3993   auto Pred = static_cast<CmpInst::Predicate>(MI.getOperand(1).getPredicate());
3994   if (!CmpInst::isEquality(Pred))
3995     return false;
3996   Register Dst = MI.getOperand(0).getReg();
3997   LLT DstTy = MRI.getType(Dst);
3998   if (getICmpTrueVal(getTargetLowering(), DstTy.isVector(),
3999                      /* IsFP = */ false) != 1)
4000     return false;
4001   int64_t OneOrZero = Pred == CmpInst::ICMP_EQ;
4002   if (!mi_match(MI.getOperand(3).getReg(), MRI, m_SpecificICst(OneOrZero)))
4003     return false;
4004   Register LHS = MI.getOperand(2).getReg();
4005   auto KnownLHS = KB->getKnownBits(LHS);
4006   if (KnownLHS.getMinValue() != 0 || KnownLHS.getMaxValue() != 1)
4007     return false;
4008   // Make sure replacing Dst with the LHS is a legal operation.
4009   LLT LHSTy = MRI.getType(LHS);
4010   unsigned LHSSize = LHSTy.getSizeInBits();
4011   unsigned DstSize = DstTy.getSizeInBits();
4012   unsigned Op = TargetOpcode::COPY;
4013   if (DstSize != LHSSize)
4014     Op = DstSize < LHSSize ? TargetOpcode::G_TRUNC : TargetOpcode::G_ZEXT;
4015   if (!isLegalOrBeforeLegalizer({Op, {DstTy, LHSTy}}))
4016     return false;
4017   MatchInfo = [=](MachineIRBuilder &B) { B.buildInstr(Op, {Dst}, {LHS}); };
4018   return true;
4019 }
4020 
4021 // Replace (and (or x, c1), c2) with (and x, c2) iff c1 & c2 == 0
4022 bool CombinerHelper::matchAndOrDisjointMask(
4023     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
4024   assert(MI.getOpcode() == TargetOpcode::G_AND);
4025 
4026   // Ignore vector types to simplify matching the two constants.
4027   // TODO: do this for vectors and scalars via a demanded bits analysis.
4028   LLT Ty = MRI.getType(MI.getOperand(0).getReg());
4029   if (Ty.isVector())
4030     return false;
4031 
4032   Register Src;
4033   int64_t MaskAnd;
4034   int64_t MaskOr;
4035   if (!mi_match(MI, MRI,
4036                 m_GAnd(m_GOr(m_Reg(Src), m_ICst(MaskOr)), m_ICst(MaskAnd))))
4037     return false;
4038 
4039   // Check if MaskOr could turn on any bits in Src.
4040   if (MaskAnd & MaskOr)
4041     return false;
4042 
4043   MatchInfo = [=, &MI](MachineIRBuilder &B) {
4044     Observer.changingInstr(MI);
4045     MI.getOperand(1).setReg(Src);
4046     Observer.changedInstr(MI);
4047   };
4048   return true;
4049 }
4050 
4051 /// Form a G_SBFX from a G_SEXT_INREG fed by a right shift.
4052 bool CombinerHelper::matchBitfieldExtractFromSExtInReg(
4053     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
4054   assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG);
4055   Register Dst = MI.getOperand(0).getReg();
4056   Register Src = MI.getOperand(1).getReg();
4057   LLT Ty = MRI.getType(Src);
4058   LLT ExtractTy = getTargetLowering().getPreferredShiftAmountTy(Ty);
4059   if (!LI || !LI->isLegalOrCustom({TargetOpcode::G_SBFX, {Ty, ExtractTy}}))
4060     return false;
4061   int64_t Width = MI.getOperand(2).getImm();
4062   Register ShiftSrc;
4063   int64_t ShiftImm;
4064   if (!mi_match(
4065           Src, MRI,
4066           m_OneNonDBGUse(m_any_of(m_GAShr(m_Reg(ShiftSrc), m_ICst(ShiftImm)),
4067                                   m_GLShr(m_Reg(ShiftSrc), m_ICst(ShiftImm))))))
4068     return false;
4069   if (ShiftImm < 0 || ShiftImm + Width > Ty.getScalarSizeInBits())
4070     return false;
4071 
4072   MatchInfo = [=](MachineIRBuilder &B) {
4073     auto Cst1 = B.buildConstant(ExtractTy, ShiftImm);
4074     auto Cst2 = B.buildConstant(ExtractTy, Width);
4075     B.buildSbfx(Dst, ShiftSrc, Cst1, Cst2);
4076   };
4077   return true;
4078 }
4079 
4080 /// Form a G_UBFX from "(a srl b) & mask", where b and mask are constants.
4081 bool CombinerHelper::matchBitfieldExtractFromAnd(
4082     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
4083   assert(MI.getOpcode() == TargetOpcode::G_AND);
4084   Register Dst = MI.getOperand(0).getReg();
4085   LLT Ty = MRI.getType(Dst);
4086   if (!getTargetLowering().isConstantUnsignedBitfieldExtactLegal(
4087           TargetOpcode::G_UBFX, Ty, Ty))
4088     return false;
4089 
4090   int64_t AndImm, LSBImm;
4091   Register ShiftSrc;
4092   const unsigned Size = Ty.getScalarSizeInBits();
4093   if (!mi_match(MI.getOperand(0).getReg(), MRI,
4094                 m_GAnd(m_OneNonDBGUse(m_GLShr(m_Reg(ShiftSrc), m_ICst(LSBImm))),
4095                        m_ICst(AndImm))))
4096     return false;
4097 
4098   // The mask is a mask of the low bits iff imm & (imm+1) == 0.
4099   auto MaybeMask = static_cast<uint64_t>(AndImm);
4100   if (MaybeMask & (MaybeMask + 1))
4101     return false;
4102 
4103   // LSB must fit within the register.
4104   if (static_cast<uint64_t>(LSBImm) >= Size)
4105     return false;
4106 
4107   LLT ExtractTy = getTargetLowering().getPreferredShiftAmountTy(Ty);
4108   uint64_t Width = APInt(Size, AndImm).countTrailingOnes();
4109   MatchInfo = [=](MachineIRBuilder &B) {
4110     auto WidthCst = B.buildConstant(ExtractTy, Width);
4111     auto LSBCst = B.buildConstant(ExtractTy, LSBImm);
4112     B.buildInstr(TargetOpcode::G_UBFX, {Dst}, {ShiftSrc, LSBCst, WidthCst});
4113   };
4114   return true;
4115 }
4116 
4117 bool CombinerHelper::matchBitfieldExtractFromShr(
4118     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
4119   const unsigned Opcode = MI.getOpcode();
4120   assert(Opcode == TargetOpcode::G_ASHR || Opcode == TargetOpcode::G_LSHR);
4121 
4122   const Register Dst = MI.getOperand(0).getReg();
4123 
4124   const unsigned ExtrOpcode = Opcode == TargetOpcode::G_ASHR
4125                                   ? TargetOpcode::G_SBFX
4126                                   : TargetOpcode::G_UBFX;
4127 
4128   // Check if the type we would use for the extract is legal
4129   LLT Ty = MRI.getType(Dst);
4130   LLT ExtractTy = getTargetLowering().getPreferredShiftAmountTy(Ty);
4131   if (!LI || !LI->isLegalOrCustom({ExtrOpcode, {Ty, ExtractTy}}))
4132     return false;
4133 
4134   Register ShlSrc;
4135   int64_t ShrAmt;
4136   int64_t ShlAmt;
4137   const unsigned Size = Ty.getScalarSizeInBits();
4138 
4139   // Try to match shr (shl x, c1), c2
4140   if (!mi_match(Dst, MRI,
4141                 m_BinOp(Opcode,
4142                         m_OneNonDBGUse(m_GShl(m_Reg(ShlSrc), m_ICst(ShlAmt))),
4143                         m_ICst(ShrAmt))))
4144     return false;
4145 
4146   // Make sure that the shift sizes can fit a bitfield extract
4147   if (ShlAmt < 0 || ShlAmt > ShrAmt || ShrAmt >= Size)
4148     return false;
4149 
4150   // Skip this combine if the G_SEXT_INREG combine could handle it
4151   if (Opcode == TargetOpcode::G_ASHR && ShlAmt == ShrAmt)
4152     return false;
4153 
4154   // Calculate start position and width of the extract
4155   const int64_t Pos = ShrAmt - ShlAmt;
4156   const int64_t Width = Size - ShrAmt;
4157 
4158   MatchInfo = [=](MachineIRBuilder &B) {
4159     auto WidthCst = B.buildConstant(ExtractTy, Width);
4160     auto PosCst = B.buildConstant(ExtractTy, Pos);
4161     B.buildInstr(ExtrOpcode, {Dst}, {ShlSrc, PosCst, WidthCst});
4162   };
4163   return true;
4164 }
4165 
4166 bool CombinerHelper::matchBitfieldExtractFromShrAnd(
4167     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
4168   const unsigned Opcode = MI.getOpcode();
4169   assert(Opcode == TargetOpcode::G_LSHR || Opcode == TargetOpcode::G_ASHR);
4170 
4171   const Register Dst = MI.getOperand(0).getReg();
4172   LLT Ty = MRI.getType(Dst);
4173   if (!getTargetLowering().isConstantUnsignedBitfieldExtactLegal(
4174           TargetOpcode::G_UBFX, Ty, Ty))
4175     return false;
4176 
4177   // Try to match shr (and x, c1), c2
4178   Register AndSrc;
4179   int64_t ShrAmt;
4180   int64_t SMask;
4181   if (!mi_match(Dst, MRI,
4182                 m_BinOp(Opcode,
4183                         m_OneNonDBGUse(m_GAnd(m_Reg(AndSrc), m_ICst(SMask))),
4184                         m_ICst(ShrAmt))))
4185     return false;
4186 
4187   const unsigned Size = Ty.getScalarSizeInBits();
4188   if (ShrAmt < 0 || ShrAmt >= Size)
4189     return false;
4190 
4191   // Check that ubfx can do the extraction, with no holes in the mask.
4192   uint64_t UMask = SMask;
4193   UMask |= maskTrailingOnes<uint64_t>(ShrAmt);
4194   UMask &= maskTrailingOnes<uint64_t>(Size);
4195   if (!isMask_64(UMask))
4196     return false;
4197 
4198   // Calculate start position and width of the extract.
4199   const int64_t Pos = ShrAmt;
4200   const int64_t Width = countTrailingOnes(UMask) - ShrAmt;
4201 
4202   // It's preferable to keep the shift, rather than form G_SBFX.
4203   // TODO: remove the G_AND via demanded bits analysis.
4204   if (Opcode == TargetOpcode::G_ASHR && Width + ShrAmt == Size)
4205     return false;
4206 
4207   MatchInfo = [=](MachineIRBuilder &B) {
4208     auto WidthCst = B.buildConstant(Ty, Width);
4209     auto PosCst = B.buildConstant(Ty, Pos);
4210     B.buildInstr(TargetOpcode::G_UBFX, {Dst}, {AndSrc, PosCst, WidthCst});
4211   };
4212   return true;
4213 }
4214 
4215 bool CombinerHelper::reassociationCanBreakAddressingModePattern(
4216     MachineInstr &PtrAdd) {
4217   assert(PtrAdd.getOpcode() == TargetOpcode::G_PTR_ADD);
4218 
4219   Register Src1Reg = PtrAdd.getOperand(1).getReg();
4220   MachineInstr *Src1Def = getOpcodeDef(TargetOpcode::G_PTR_ADD, Src1Reg, MRI);
4221   if (!Src1Def)
4222     return false;
4223 
4224   Register Src2Reg = PtrAdd.getOperand(2).getReg();
4225 
4226   if (MRI.hasOneNonDBGUse(Src1Reg))
4227     return false;
4228 
4229   auto C1 = getIConstantVRegVal(Src1Def->getOperand(2).getReg(), MRI);
4230   if (!C1)
4231     return false;
4232   auto C2 = getIConstantVRegVal(Src2Reg, MRI);
4233   if (!C2)
4234     return false;
4235 
4236   const APInt &C1APIntVal = *C1;
4237   const APInt &C2APIntVal = *C2;
4238   const int64_t CombinedValue = (C1APIntVal + C2APIntVal).getSExtValue();
4239 
4240   for (auto &UseMI : MRI.use_nodbg_instructions(Src1Reg)) {
4241     // This combine may end up running before ptrtoint/inttoptr combines
4242     // manage to eliminate redundant conversions, so try to look through them.
4243     MachineInstr *ConvUseMI = &UseMI;
4244     unsigned ConvUseOpc = ConvUseMI->getOpcode();
4245     while (ConvUseOpc == TargetOpcode::G_INTTOPTR ||
4246            ConvUseOpc == TargetOpcode::G_PTRTOINT) {
4247       Register DefReg = ConvUseMI->getOperand(0).getReg();
4248       if (!MRI.hasOneNonDBGUse(DefReg))
4249         break;
4250       ConvUseMI = &*MRI.use_instr_nodbg_begin(DefReg);
4251       ConvUseOpc = ConvUseMI->getOpcode();
4252     }
4253     auto LoadStore = ConvUseOpc == TargetOpcode::G_LOAD ||
4254                      ConvUseOpc == TargetOpcode::G_STORE;
4255     if (!LoadStore)
4256       continue;
4257     // Is x[offset2] already not a legal addressing mode? If so then
4258     // reassociating the constants breaks nothing (we test offset2 because
4259     // that's the one we hope to fold into the load or store).
4260     TargetLoweringBase::AddrMode AM;
4261     AM.HasBaseReg = true;
4262     AM.BaseOffs = C2APIntVal.getSExtValue();
4263     unsigned AS =
4264         MRI.getType(ConvUseMI->getOperand(1).getReg()).getAddressSpace();
4265     Type *AccessTy =
4266         getTypeForLLT(MRI.getType(ConvUseMI->getOperand(0).getReg()),
4267                       PtrAdd.getMF()->getFunction().getContext());
4268     const auto &TLI = *PtrAdd.getMF()->getSubtarget().getTargetLowering();
4269     if (!TLI.isLegalAddressingMode(PtrAdd.getMF()->getDataLayout(), AM,
4270                                    AccessTy, AS))
4271       continue;
4272 
4273     // Would x[offset1+offset2] still be a legal addressing mode?
4274     AM.BaseOffs = CombinedValue;
4275     if (!TLI.isLegalAddressingMode(PtrAdd.getMF()->getDataLayout(), AM,
4276                                    AccessTy, AS))
4277       return true;
4278   }
4279 
4280   return false;
4281 }
4282 
4283 bool CombinerHelper::matchReassocConstantInnerRHS(GPtrAdd &MI,
4284                                                   MachineInstr *RHS,
4285                                                   BuildFnTy &MatchInfo) {
4286   // G_PTR_ADD(BASE, G_ADD(X, C)) -> G_PTR_ADD(G_PTR_ADD(BASE, X), C)
4287   Register Src1Reg = MI.getOperand(1).getReg();
4288   if (RHS->getOpcode() != TargetOpcode::G_ADD)
4289     return false;
4290   auto C2 = getIConstantVRegVal(RHS->getOperand(2).getReg(), MRI);
4291   if (!C2)
4292     return false;
4293 
4294   MatchInfo = [=, &MI](MachineIRBuilder &B) {
4295     LLT PtrTy = MRI.getType(MI.getOperand(0).getReg());
4296 
4297     auto NewBase =
4298         Builder.buildPtrAdd(PtrTy, Src1Reg, RHS->getOperand(1).getReg());
4299     Observer.changingInstr(MI);
4300     MI.getOperand(1).setReg(NewBase.getReg(0));
4301     MI.getOperand(2).setReg(RHS->getOperand(2).getReg());
4302     Observer.changedInstr(MI);
4303   };
4304   return !reassociationCanBreakAddressingModePattern(MI);
4305 }
4306 
4307 bool CombinerHelper::matchReassocConstantInnerLHS(GPtrAdd &MI,
4308                                                   MachineInstr *LHS,
4309                                                   MachineInstr *RHS,
4310                                                   BuildFnTy &MatchInfo) {
4311   // G_PTR_ADD (G_PTR_ADD X, C), Y) -> (G_PTR_ADD (G_PTR_ADD(X, Y), C)
4312   // if and only if (G_PTR_ADD X, C) has one use.
4313   Register LHSBase;
4314   Optional<ValueAndVReg> LHSCstOff;
4315   if (!mi_match(MI.getBaseReg(), MRI,
4316                 m_OneNonDBGUse(m_GPtrAdd(m_Reg(LHSBase), m_GCst(LHSCstOff)))))
4317     return false;
4318 
4319   auto *LHSPtrAdd = cast<GPtrAdd>(LHS);
4320   MatchInfo = [=, &MI](MachineIRBuilder &B) {
4321     // When we change LHSPtrAdd's offset register we might cause it to use a reg
4322     // before its def. Sink the instruction so the outer PTR_ADD to ensure this
4323     // doesn't happen.
4324     LHSPtrAdd->moveBefore(&MI);
4325     Register RHSReg = MI.getOffsetReg();
4326     Observer.changingInstr(MI);
4327     MI.getOperand(2).setReg(LHSCstOff->VReg);
4328     Observer.changedInstr(MI);
4329     Observer.changingInstr(*LHSPtrAdd);
4330     LHSPtrAdd->getOperand(2).setReg(RHSReg);
4331     Observer.changedInstr(*LHSPtrAdd);
4332   };
4333   return !reassociationCanBreakAddressingModePattern(MI);
4334 }
4335 
4336 bool CombinerHelper::matchReassocFoldConstantsInSubTree(GPtrAdd &MI,
4337                                                         MachineInstr *LHS,
4338                                                         MachineInstr *RHS,
4339                                                         BuildFnTy &MatchInfo) {
4340   // G_PTR_ADD(G_PTR_ADD(BASE, C1), C2) -> G_PTR_ADD(BASE, C1+C2)
4341   auto *LHSPtrAdd = dyn_cast<GPtrAdd>(LHS);
4342   if (!LHSPtrAdd)
4343     return false;
4344 
4345   Register Src2Reg = MI.getOperand(2).getReg();
4346   Register LHSSrc1 = LHSPtrAdd->getBaseReg();
4347   Register LHSSrc2 = LHSPtrAdd->getOffsetReg();
4348   auto C1 = getIConstantVRegVal(LHSSrc2, MRI);
4349   if (!C1)
4350     return false;
4351   auto C2 = getIConstantVRegVal(Src2Reg, MRI);
4352   if (!C2)
4353     return false;
4354 
4355   MatchInfo = [=, &MI](MachineIRBuilder &B) {
4356     auto NewCst = B.buildConstant(MRI.getType(Src2Reg), *C1 + *C2);
4357     Observer.changingInstr(MI);
4358     MI.getOperand(1).setReg(LHSSrc1);
4359     MI.getOperand(2).setReg(NewCst.getReg(0));
4360     Observer.changedInstr(MI);
4361   };
4362   return !reassociationCanBreakAddressingModePattern(MI);
4363 }
4364 
4365 bool CombinerHelper::matchReassocPtrAdd(MachineInstr &MI,
4366                                         BuildFnTy &MatchInfo) {
4367   auto &PtrAdd = cast<GPtrAdd>(MI);
4368   // We're trying to match a few pointer computation patterns here for
4369   // re-association opportunities.
4370   // 1) Isolating a constant operand to be on the RHS, e.g.:
4371   // G_PTR_ADD(BASE, G_ADD(X, C)) -> G_PTR_ADD(G_PTR_ADD(BASE, X), C)
4372   //
4373   // 2) Folding two constants in each sub-tree as long as such folding
4374   // doesn't break a legal addressing mode.
4375   // G_PTR_ADD(G_PTR_ADD(BASE, C1), C2) -> G_PTR_ADD(BASE, C1+C2)
4376   //
4377   // 3) Move a constant from the LHS of an inner op to the RHS of the outer.
4378   // G_PTR_ADD (G_PTR_ADD X, C), Y) -> G_PTR_ADD (G_PTR_ADD(X, Y), C)
4379   // iif (G_PTR_ADD X, C) has one use.
4380   MachineInstr *LHS = MRI.getVRegDef(PtrAdd.getBaseReg());
4381   MachineInstr *RHS = MRI.getVRegDef(PtrAdd.getOffsetReg());
4382 
4383   // Try to match example 2.
4384   if (matchReassocFoldConstantsInSubTree(PtrAdd, LHS, RHS, MatchInfo))
4385     return true;
4386 
4387   // Try to match example 3.
4388   if (matchReassocConstantInnerLHS(PtrAdd, LHS, RHS, MatchInfo))
4389     return true;
4390 
4391   // Try to match example 1.
4392   if (matchReassocConstantInnerRHS(PtrAdd, RHS, MatchInfo))
4393     return true;
4394 
4395   return false;
4396 }
4397 
4398 bool CombinerHelper::matchConstantFold(MachineInstr &MI, APInt &MatchInfo) {
4399   Register Op1 = MI.getOperand(1).getReg();
4400   Register Op2 = MI.getOperand(2).getReg();
4401   auto MaybeCst = ConstantFoldBinOp(MI.getOpcode(), Op1, Op2, MRI);
4402   if (!MaybeCst)
4403     return false;
4404   MatchInfo = *MaybeCst;
4405   return true;
4406 }
4407 
4408 bool CombinerHelper::matchNarrowBinopFeedingAnd(
4409     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
4410   // Look for a binop feeding into an AND with a mask:
4411   //
4412   // %add = G_ADD %lhs, %rhs
4413   // %and = G_AND %add, 000...11111111
4414   //
4415   // Check if it's possible to perform the binop at a narrower width and zext
4416   // back to the original width like so:
4417   //
4418   // %narrow_lhs = G_TRUNC %lhs
4419   // %narrow_rhs = G_TRUNC %rhs
4420   // %narrow_add = G_ADD %narrow_lhs, %narrow_rhs
4421   // %new_add = G_ZEXT %narrow_add
4422   // %and = G_AND %new_add, 000...11111111
4423   //
4424   // This can allow later combines to eliminate the G_AND if it turns out
4425   // that the mask is irrelevant.
4426   assert(MI.getOpcode() == TargetOpcode::G_AND);
4427   Register Dst = MI.getOperand(0).getReg();
4428   Register AndLHS = MI.getOperand(1).getReg();
4429   Register AndRHS = MI.getOperand(2).getReg();
4430   LLT WideTy = MRI.getType(Dst);
4431 
4432   // If the potential binop has more than one use, then it's possible that one
4433   // of those uses will need its full width.
4434   if (!WideTy.isScalar() || !MRI.hasOneNonDBGUse(AndLHS))
4435     return false;
4436 
4437   // Check if the LHS feeding the AND is impacted by the high bits that we're
4438   // masking out.
4439   //
4440   // e.g. for 64-bit x, y:
4441   //
4442   // add_64(x, y) & 65535 == zext(add_16(trunc(x), trunc(y))) & 65535
4443   MachineInstr *LHSInst = getDefIgnoringCopies(AndLHS, MRI);
4444   if (!LHSInst)
4445     return false;
4446   unsigned LHSOpc = LHSInst->getOpcode();
4447   switch (LHSOpc) {
4448   default:
4449     return false;
4450   case TargetOpcode::G_ADD:
4451   case TargetOpcode::G_SUB:
4452   case TargetOpcode::G_MUL:
4453   case TargetOpcode::G_AND:
4454   case TargetOpcode::G_OR:
4455   case TargetOpcode::G_XOR:
4456     break;
4457   }
4458 
4459   // Find the mask on the RHS.
4460   auto Cst = getIConstantVRegValWithLookThrough(AndRHS, MRI);
4461   if (!Cst)
4462     return false;
4463   auto Mask = Cst->Value;
4464   if (!Mask.isMask())
4465     return false;
4466 
4467   // No point in combining if there's nothing to truncate.
4468   unsigned NarrowWidth = Mask.countTrailingOnes();
4469   if (NarrowWidth == WideTy.getSizeInBits())
4470     return false;
4471   LLT NarrowTy = LLT::scalar(NarrowWidth);
4472 
4473   // Check if adding the zext + truncates could be harmful.
4474   auto &MF = *MI.getMF();
4475   const auto &TLI = getTargetLowering();
4476   LLVMContext &Ctx = MF.getFunction().getContext();
4477   auto &DL = MF.getDataLayout();
4478   if (!TLI.isTruncateFree(WideTy, NarrowTy, DL, Ctx) ||
4479       !TLI.isZExtFree(NarrowTy, WideTy, DL, Ctx))
4480     return false;
4481   if (!isLegalOrBeforeLegalizer({TargetOpcode::G_TRUNC, {NarrowTy, WideTy}}) ||
4482       !isLegalOrBeforeLegalizer({TargetOpcode::G_ZEXT, {WideTy, NarrowTy}}))
4483     return false;
4484   Register BinOpLHS = LHSInst->getOperand(1).getReg();
4485   Register BinOpRHS = LHSInst->getOperand(2).getReg();
4486   MatchInfo = [=, &MI](MachineIRBuilder &B) {
4487     auto NarrowLHS = Builder.buildTrunc(NarrowTy, BinOpLHS);
4488     auto NarrowRHS = Builder.buildTrunc(NarrowTy, BinOpRHS);
4489     auto NarrowBinOp =
4490         Builder.buildInstr(LHSOpc, {NarrowTy}, {NarrowLHS, NarrowRHS});
4491     auto Ext = Builder.buildZExt(WideTy, NarrowBinOp);
4492     Observer.changingInstr(MI);
4493     MI.getOperand(1).setReg(Ext.getReg(0));
4494     Observer.changedInstr(MI);
4495   };
4496   return true;
4497 }
4498 
4499 bool CombinerHelper::matchMulOBy2(MachineInstr &MI, BuildFnTy &MatchInfo) {
4500   unsigned Opc = MI.getOpcode();
4501   assert(Opc == TargetOpcode::G_UMULO || Opc == TargetOpcode::G_SMULO);
4502   // Check for a constant 2 or a splat of 2 on the RHS.
4503   auto RHS = MI.getOperand(3).getReg();
4504   bool IsVector = MRI.getType(RHS).isVector();
4505   if (!IsVector && !mi_match(MI.getOperand(3).getReg(), MRI, m_SpecificICst(2)))
4506     return false;
4507   if (IsVector) {
4508     // FIXME: There's no mi_match pattern for this yet.
4509     auto *RHSDef = getDefIgnoringCopies(RHS, MRI);
4510     if (!RHSDef)
4511       return false;
4512     auto Splat = getBuildVectorConstantSplat(*RHSDef, MRI);
4513     if (!Splat || *Splat != 2)
4514       return false;
4515   }
4516 
4517   MatchInfo = [=, &MI](MachineIRBuilder &B) {
4518     Observer.changingInstr(MI);
4519     unsigned NewOpc = Opc == TargetOpcode::G_UMULO ? TargetOpcode::G_UADDO
4520                                                    : TargetOpcode::G_SADDO;
4521     MI.setDesc(Builder.getTII().get(NewOpc));
4522     MI.getOperand(3).setReg(MI.getOperand(2).getReg());
4523     Observer.changedInstr(MI);
4524   };
4525   return true;
4526 }
4527 
4528 MachineInstr *CombinerHelper::buildUDivUsingMul(MachineInstr &MI) {
4529   assert(MI.getOpcode() == TargetOpcode::G_UDIV);
4530   auto &UDiv = cast<GenericMachineInstr>(MI);
4531   Register Dst = UDiv.getReg(0);
4532   Register LHS = UDiv.getReg(1);
4533   Register RHS = UDiv.getReg(2);
4534   LLT Ty = MRI.getType(Dst);
4535   LLT ScalarTy = Ty.getScalarType();
4536   const unsigned EltBits = ScalarTy.getScalarSizeInBits();
4537   LLT ShiftAmtTy = getTargetLowering().getPreferredShiftAmountTy(Ty);
4538   LLT ScalarShiftAmtTy = ShiftAmtTy.getScalarType();
4539   auto &MIB = Builder;
4540   MIB.setInstrAndDebugLoc(MI);
4541 
4542   bool UseNPQ = false;
4543   SmallVector<Register, 16> PreShifts, PostShifts, MagicFactors, NPQFactors;
4544 
4545   auto BuildUDIVPattern = [&](const Constant *C) {
4546     auto *CI = cast<ConstantInt>(C);
4547     const APInt &Divisor = CI->getValue();
4548     UnsignedDivisonByConstantInfo magics =
4549         UnsignedDivisonByConstantInfo::get(Divisor);
4550     unsigned PreShift = 0, PostShift = 0;
4551 
4552     // If the divisor is even, we can avoid using the expensive fixup by
4553     // shifting the divided value upfront.
4554     if (magics.IsAdd != 0 && !Divisor[0]) {
4555       PreShift = Divisor.countTrailingZeros();
4556       // Get magic number for the shifted divisor.
4557       magics =
4558           UnsignedDivisonByConstantInfo::get(Divisor.lshr(PreShift), PreShift);
4559       assert(magics.IsAdd == 0 && "Should use cheap fixup now");
4560     }
4561 
4562     APInt Magic = magics.Magic;
4563 
4564     unsigned SelNPQ;
4565     if (magics.IsAdd == 0 || Divisor.isOneValue()) {
4566       assert(magics.ShiftAmount < Divisor.getBitWidth() &&
4567              "We shouldn't generate an undefined shift!");
4568       PostShift = magics.ShiftAmount;
4569       SelNPQ = false;
4570     } else {
4571       PostShift = magics.ShiftAmount - 1;
4572       SelNPQ = true;
4573     }
4574 
4575     PreShifts.push_back(
4576         MIB.buildConstant(ScalarShiftAmtTy, PreShift).getReg(0));
4577     MagicFactors.push_back(MIB.buildConstant(ScalarTy, Magic).getReg(0));
4578     NPQFactors.push_back(
4579         MIB.buildConstant(ScalarTy,
4580                           SelNPQ ? APInt::getOneBitSet(EltBits, EltBits - 1)
4581                                  : APInt::getZero(EltBits))
4582             .getReg(0));
4583     PostShifts.push_back(
4584         MIB.buildConstant(ScalarShiftAmtTy, PostShift).getReg(0));
4585     UseNPQ |= SelNPQ;
4586     return true;
4587   };
4588 
4589   // Collect the shifts/magic values from each element.
4590   bool Matched = matchUnaryPredicate(MRI, RHS, BuildUDIVPattern);
4591   (void)Matched;
4592   assert(Matched && "Expected unary predicate match to succeed");
4593 
4594   Register PreShift, PostShift, MagicFactor, NPQFactor;
4595   auto *RHSDef = getOpcodeDef<GBuildVector>(RHS, MRI);
4596   if (RHSDef) {
4597     PreShift = MIB.buildBuildVector(ShiftAmtTy, PreShifts).getReg(0);
4598     MagicFactor = MIB.buildBuildVector(Ty, MagicFactors).getReg(0);
4599     NPQFactor = MIB.buildBuildVector(Ty, NPQFactors).getReg(0);
4600     PostShift = MIB.buildBuildVector(ShiftAmtTy, PostShifts).getReg(0);
4601   } else {
4602     assert(MRI.getType(RHS).isScalar() &&
4603            "Non-build_vector operation should have been a scalar");
4604     PreShift = PreShifts[0];
4605     MagicFactor = MagicFactors[0];
4606     PostShift = PostShifts[0];
4607   }
4608 
4609   Register Q = LHS;
4610   Q = MIB.buildLShr(Ty, Q, PreShift).getReg(0);
4611 
4612   // Multiply the numerator (operand 0) by the magic value.
4613   Q = MIB.buildUMulH(Ty, Q, MagicFactor).getReg(0);
4614 
4615   if (UseNPQ) {
4616     Register NPQ = MIB.buildSub(Ty, LHS, Q).getReg(0);
4617 
4618     // For vectors we might have a mix of non-NPQ/NPQ paths, so use
4619     // G_UMULH to act as a SRL-by-1 for NPQ, else multiply by zero.
4620     if (Ty.isVector())
4621       NPQ = MIB.buildUMulH(Ty, NPQ, NPQFactor).getReg(0);
4622     else
4623       NPQ = MIB.buildLShr(Ty, NPQ, MIB.buildConstant(ShiftAmtTy, 1)).getReg(0);
4624 
4625     Q = MIB.buildAdd(Ty, NPQ, Q).getReg(0);
4626   }
4627 
4628   Q = MIB.buildLShr(Ty, Q, PostShift).getReg(0);
4629   auto One = MIB.buildConstant(Ty, 1);
4630   auto IsOne = MIB.buildICmp(
4631       CmpInst::Predicate::ICMP_EQ,
4632       Ty.isScalar() ? LLT::scalar(1) : Ty.changeElementSize(1), RHS, One);
4633   return MIB.buildSelect(Ty, IsOne, LHS, Q);
4634 }
4635 
4636 bool CombinerHelper::matchUDivByConst(MachineInstr &MI) {
4637   assert(MI.getOpcode() == TargetOpcode::G_UDIV);
4638   Register Dst = MI.getOperand(0).getReg();
4639   Register RHS = MI.getOperand(2).getReg();
4640   LLT DstTy = MRI.getType(Dst);
4641   auto *RHSDef = MRI.getVRegDef(RHS);
4642   if (!isConstantOrConstantVector(*RHSDef, MRI))
4643     return false;
4644 
4645   auto &MF = *MI.getMF();
4646   AttributeList Attr = MF.getFunction().getAttributes();
4647   const auto &TLI = getTargetLowering();
4648   LLVMContext &Ctx = MF.getFunction().getContext();
4649   auto &DL = MF.getDataLayout();
4650   if (TLI.isIntDivCheap(getApproximateEVTForLLT(DstTy, DL, Ctx), Attr))
4651     return false;
4652 
4653   // Don't do this for minsize because the instruction sequence is usually
4654   // larger.
4655   if (MF.getFunction().hasMinSize())
4656     return false;
4657 
4658   // Don't do this if the types are not going to be legal.
4659   if (LI) {
4660     if (!isLegalOrBeforeLegalizer({TargetOpcode::G_MUL, {DstTy, DstTy}}))
4661       return false;
4662     if (!isLegalOrBeforeLegalizer({TargetOpcode::G_UMULH, {DstTy}}))
4663       return false;
4664     if (!isLegalOrBeforeLegalizer(
4665             {TargetOpcode::G_ICMP,
4666              {DstTy.isVector() ? DstTy.changeElementSize(1) : LLT::scalar(1),
4667               DstTy}}))
4668       return false;
4669   }
4670 
4671   auto CheckEltValue = [&](const Constant *C) {
4672     if (auto *CI = dyn_cast_or_null<ConstantInt>(C))
4673       return !CI->isZero();
4674     return false;
4675   };
4676   return matchUnaryPredicate(MRI, RHS, CheckEltValue);
4677 }
4678 
4679 void CombinerHelper::applyUDivByConst(MachineInstr &MI) {
4680   auto *NewMI = buildUDivUsingMul(MI);
4681   replaceSingleDefInstWithReg(MI, NewMI->getOperand(0).getReg());
4682 }
4683 
4684 bool CombinerHelper::matchUMulHToLShr(MachineInstr &MI) {
4685   assert(MI.getOpcode() == TargetOpcode::G_UMULH);
4686   Register RHS = MI.getOperand(2).getReg();
4687   Register Dst = MI.getOperand(0).getReg();
4688   LLT Ty = MRI.getType(Dst);
4689   LLT ShiftAmtTy = getTargetLowering().getPreferredShiftAmountTy(Ty);
4690   auto MatchPow2ExceptOne = [&](const Constant *C) {
4691     if (auto *CI = dyn_cast<ConstantInt>(C))
4692       return CI->getValue().isPowerOf2() && !CI->getValue().isOne();
4693     return false;
4694   };
4695   if (!matchUnaryPredicate(MRI, RHS, MatchPow2ExceptOne, false))
4696     return false;
4697   return isLegalOrBeforeLegalizer({TargetOpcode::G_LSHR, {Ty, ShiftAmtTy}});
4698 }
4699 
4700 void CombinerHelper::applyUMulHToLShr(MachineInstr &MI) {
4701   Register LHS = MI.getOperand(1).getReg();
4702   Register RHS = MI.getOperand(2).getReg();
4703   Register Dst = MI.getOperand(0).getReg();
4704   LLT Ty = MRI.getType(Dst);
4705   LLT ShiftAmtTy = getTargetLowering().getPreferredShiftAmountTy(Ty);
4706   unsigned NumEltBits = Ty.getScalarSizeInBits();
4707 
4708   Builder.setInstrAndDebugLoc(MI);
4709   auto LogBase2 = buildLogBase2(RHS, Builder);
4710   auto ShiftAmt =
4711       Builder.buildSub(Ty, Builder.buildConstant(Ty, NumEltBits), LogBase2);
4712   auto Trunc = Builder.buildZExtOrTrunc(ShiftAmtTy, ShiftAmt);
4713   Builder.buildLShr(Dst, LHS, Trunc);
4714   MI.eraseFromParent();
4715 }
4716 
4717 bool CombinerHelper::matchRedundantNegOperands(MachineInstr &MI,
4718                                                BuildFnTy &MatchInfo) {
4719   unsigned Opc = MI.getOpcode();
4720   assert(Opc == TargetOpcode::G_FADD || Opc == TargetOpcode::G_FSUB ||
4721          Opc == TargetOpcode::G_FMUL || Opc == TargetOpcode::G_FDIV ||
4722          Opc == TargetOpcode::G_FMAD || Opc == TargetOpcode::G_FMA);
4723 
4724   Register Dst = MI.getOperand(0).getReg();
4725   Register X = MI.getOperand(1).getReg();
4726   Register Y = MI.getOperand(2).getReg();
4727   LLT Type = MRI.getType(Dst);
4728 
4729   // fold (fadd x, fneg(y)) -> (fsub x, y)
4730   // fold (fadd fneg(y), x) -> (fsub x, y)
4731   // G_ADD is commutative so both cases are checked by m_GFAdd
4732   if (mi_match(Dst, MRI, m_GFAdd(m_Reg(X), m_GFNeg(m_Reg(Y)))) &&
4733       isLegalOrBeforeLegalizer({TargetOpcode::G_FSUB, {Type}})) {
4734     Opc = TargetOpcode::G_FSUB;
4735   }
4736   /// fold (fsub x, fneg(y)) -> (fadd x, y)
4737   else if (mi_match(Dst, MRI, m_GFSub(m_Reg(X), m_GFNeg(m_Reg(Y)))) &&
4738            isLegalOrBeforeLegalizer({TargetOpcode::G_FADD, {Type}})) {
4739     Opc = TargetOpcode::G_FADD;
4740   }
4741   // fold (fmul fneg(x), fneg(y)) -> (fmul x, y)
4742   // fold (fdiv fneg(x), fneg(y)) -> (fdiv x, y)
4743   // fold (fmad fneg(x), fneg(y), z) -> (fmad x, y, z)
4744   // fold (fma fneg(x), fneg(y), z) -> (fma x, y, z)
4745   else if ((Opc == TargetOpcode::G_FMUL || Opc == TargetOpcode::G_FDIV ||
4746             Opc == TargetOpcode::G_FMAD || Opc == TargetOpcode::G_FMA) &&
4747            mi_match(X, MRI, m_GFNeg(m_Reg(X))) &&
4748            mi_match(Y, MRI, m_GFNeg(m_Reg(Y)))) {
4749     // no opcode change
4750   } else
4751     return false;
4752 
4753   MatchInfo = [=, &MI](MachineIRBuilder &B) {
4754     Observer.changingInstr(MI);
4755     MI.setDesc(B.getTII().get(Opc));
4756     MI.getOperand(1).setReg(X);
4757     MI.getOperand(2).setReg(Y);
4758     Observer.changedInstr(MI);
4759   };
4760   return true;
4761 }
4762 
4763 bool CombinerHelper::tryCombine(MachineInstr &MI) {
4764   if (tryCombineCopy(MI))
4765     return true;
4766   if (tryCombineExtendingLoads(MI))
4767     return true;
4768   if (tryCombineIndexedLoadStore(MI))
4769     return true;
4770   return false;
4771 }
4772