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