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