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