LLVM  13.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"
30 
31 #define DEBUG_TYPE "gi-combiner"
32 
33 using namespace llvm;
34 using namespace MIPatternMatch;
35 
36 // Option to allow testing of the combiner while no targets know about indexed
37 // addressing.
38 static cl::opt<bool>
39  ForceLegalIndexing("force-legal-indexing", cl::Hidden, cl::init(false),
40  cl::desc("Force all indexed operations to be "
41  "legal for the GlobalISel combiner"));
42 
46  const LegalizerInfo *LI)
47  : Builder(B), MRI(Builder.getMF().getRegInfo()), Observer(Observer),
48  KB(KB), MDT(MDT), LI(LI) {
49  (void)this->KB;
50 }
51 
54 }
55 
56 /// \returns The little endian in-memory byte position of byte \p I in a
57 /// \p ByteWidth bytes wide type.
58 ///
59 /// E.g. Given a 4-byte type x, x[0] -> byte 0
60 static unsigned littleEndianByteAt(const unsigned ByteWidth, const unsigned I) {
61  assert(I < ByteWidth && "I must be in [0, ByteWidth)");
62  return I;
63 }
64 
65 /// \returns The big endian in-memory byte position of byte \p I in a
66 /// \p ByteWidth bytes wide type.
67 ///
68 /// E.g. Given a 4-byte type x, x[0] -> byte 3
69 static unsigned bigEndianByteAt(const unsigned ByteWidth, const unsigned I) {
70  assert(I < ByteWidth && "I must be in [0, ByteWidth)");
71  return ByteWidth - I - 1;
72 }
73 
74 /// Given a map from byte offsets in memory to indices in a load/store,
75 /// determine if that map corresponds to a little or big endian byte pattern.
76 ///
77 /// \param MemOffset2Idx maps memory offsets to address offsets.
78 /// \param LowestIdx is the lowest index in \p MemOffset2Idx.
79 ///
80 /// \returns true if the map corresponds to a big endian byte pattern, false
81 /// if it corresponds to a little endian byte pattern, and None otherwise.
82 ///
83 /// E.g. given a 32-bit type x, and x[AddrOffset], the in-memory byte patterns
84 /// are as follows:
85 ///
86 /// AddrOffset Little endian Big endian
87 /// 0 0 3
88 /// 1 1 2
89 /// 2 2 1
90 /// 3 3 0
91 static Optional<bool>
93  int64_t LowestIdx) {
94  // Need at least two byte positions to decide on endianness.
95  unsigned Width = MemOffset2Idx.size();
96  if (Width < 2)
97  return None;
98  bool BigEndian = true, LittleEndian = true;
99  for (unsigned MemOffset = 0; MemOffset < Width; ++ MemOffset) {
100  auto MemOffsetAndIdx = MemOffset2Idx.find(MemOffset);
101  if (MemOffsetAndIdx == MemOffset2Idx.end())
102  return None;
103  const int64_t Idx = MemOffsetAndIdx->second - LowestIdx;
104  assert(Idx >= 0 && "Expected non-negative byte offset?");
105  LittleEndian &= Idx == littleEndianByteAt(Width, MemOffset);
106  BigEndian &= Idx == bigEndianByteAt(Width, MemOffset);
107  if (!BigEndian && !LittleEndian)
108  return None;
109  }
110 
111  assert((BigEndian != LittleEndian) &&
112  "Pattern cannot be both big and little endian!");
113  return BigEndian;
114 }
115 
117  const LegalityQuery &Query) const {
118  return !LI || LI->getAction(Query).Action == LegalizeActions::Legal;
119 }
120 
122  Register ToReg) const {
124 
125  if (MRI.constrainRegAttrs(ToReg, FromReg))
126  MRI.replaceRegWith(FromReg, ToReg);
127  else
128  Builder.buildCopy(ToReg, FromReg);
129 
131 }
132 
134  MachineOperand &FromRegOp,
135  Register ToReg) const {
136  assert(FromRegOp.getParent() && "Expected an operand in an MI");
137  Observer.changingInstr(*FromRegOp.getParent());
138 
139  FromRegOp.setReg(ToReg);
140 
141  Observer.changedInstr(*FromRegOp.getParent());
142 }
143 
145  if (matchCombineCopy(MI)) {
147  return true;
148  }
149  return false;
150 }
152  if (MI.getOpcode() != TargetOpcode::COPY)
153  return false;
154  Register DstReg = MI.getOperand(0).getReg();
155  Register SrcReg = MI.getOperand(1).getReg();
156  return canReplaceReg(DstReg, SrcReg, MRI);
157 }
159  Register DstReg = MI.getOperand(0).getReg();
160  Register SrcReg = MI.getOperand(1).getReg();
161  MI.eraseFromParent();
162  replaceRegWith(MRI, DstReg, SrcReg);
163 }
164 
166  bool IsUndef = false;
168  if (matchCombineConcatVectors(MI, IsUndef, Ops)) {
169  applyCombineConcatVectors(MI, IsUndef, Ops);
170  return true;
171  }
172  return false;
173 }
174 
177  assert(MI.getOpcode() == TargetOpcode::G_CONCAT_VECTORS &&
178  "Invalid instruction");
179  IsUndef = true;
180  MachineInstr *Undef = nullptr;
181 
182  // Walk over all the operands of concat vectors and check if they are
183  // build_vector themselves or undef.
184  // Then collect their operands in Ops.
185  for (const MachineOperand &MO : MI.uses()) {
186  Register Reg = MO.getReg();
188  assert(Def && "Operand not defined");
189  switch (Def->getOpcode()) {
190  case TargetOpcode::G_BUILD_VECTOR:
191  IsUndef = false;
192  // Remember the operands of the build_vector to fold
193  // them into the yet-to-build flattened concat vectors.
194  for (const MachineOperand &BuildVecMO : Def->uses())
195  Ops.push_back(BuildVecMO.getReg());
196  break;
197  case TargetOpcode::G_IMPLICIT_DEF: {
198  LLT OpType = MRI.getType(Reg);
199  // Keep one undef value for all the undef operands.
200  if (!Undef) {
201  Builder.setInsertPt(*MI.getParent(), MI);
203  }
204  assert(MRI.getType(Undef->getOperand(0).getReg()) ==
205  OpType.getScalarType() &&
206  "All undefs should have the same type");
207  // Break the undef vector in as many scalar elements as needed
208  // for the flattening.
209  for (unsigned EltIdx = 0, EltEnd = OpType.getNumElements();
210  EltIdx != EltEnd; ++EltIdx)
211  Ops.push_back(Undef->getOperand(0).getReg());
212  break;
213  }
214  default:
215  return false;
216  }
217  }
218  return true;
219 }
221  MachineInstr &MI, bool IsUndef, const ArrayRef<Register> Ops) {
222  // We determined that the concat_vectors can be flatten.
223  // Generate the flattened build_vector.
224  Register DstReg = MI.getOperand(0).getReg();
225  Builder.setInsertPt(*MI.getParent(), MI);
226  Register NewDstReg = MRI.cloneVirtualRegister(DstReg);
227 
228  // Note: IsUndef is sort of redundant. We could have determine it by
229  // checking that at all Ops are undef. Alternatively, we could have
230  // generate a build_vector of undefs and rely on another combine to
231  // clean that up. For now, given we already gather this information
232  // in tryCombineConcatVectors, just save compile time and issue the
233  // right thing.
234  if (IsUndef)
235  Builder.buildUndef(NewDstReg);
236  else
237  Builder.buildBuildVector(NewDstReg, Ops);
238  MI.eraseFromParent();
239  replaceRegWith(MRI, DstReg, NewDstReg);
240 }
241 
244  if (matchCombineShuffleVector(MI, Ops)) {
246  return true;
247  }
248  return false;
249 }
250 
253  assert(MI.getOpcode() == TargetOpcode::G_SHUFFLE_VECTOR &&
254  "Invalid instruction kind");
255  LLT DstType = MRI.getType(MI.getOperand(0).getReg());
256  Register Src1 = MI.getOperand(1).getReg();
257  LLT SrcType = MRI.getType(Src1);
258  // As bizarre as it may look, shuffle vector can actually produce
259  // scalar! This is because at the IR level a <1 x ty> shuffle
260  // vector is perfectly valid.
261  unsigned DstNumElts = DstType.isVector() ? DstType.getNumElements() : 1;
262  unsigned SrcNumElts = SrcType.isVector() ? SrcType.getNumElements() : 1;
263 
264  // If the resulting vector is smaller than the size of the source
265  // vectors being concatenated, we won't be able to replace the
266  // shuffle vector into a concat_vectors.
267  //
268  // Note: We may still be able to produce a concat_vectors fed by
269  // extract_vector_elt and so on. It is less clear that would
270  // be better though, so don't bother for now.
271  //
272  // If the destination is a scalar, the size of the sources doesn't
273  // matter. we will lower the shuffle to a plain copy. This will
274  // work only if the source and destination have the same size. But
275  // that's covered by the next condition.
276  //
277  // TODO: If the size between the source and destination don't match
278  // we could still emit an extract vector element in that case.
279  if (DstNumElts < 2 * SrcNumElts && DstNumElts != 1)
280  return false;
281 
282  // Check that the shuffle mask can be broken evenly between the
283  // different sources.
284  if (DstNumElts % SrcNumElts != 0)
285  return false;
286 
287  // Mask length is a multiple of the source vector length.
288  // Check if the shuffle is some kind of concatenation of the input
289  // vectors.
290  unsigned NumConcat = DstNumElts / SrcNumElts;
291  SmallVector<int, 8> ConcatSrcs(NumConcat, -1);
292  ArrayRef<int> Mask = MI.getOperand(3).getShuffleMask();
293  for (unsigned i = 0; i != DstNumElts; ++i) {
294  int Idx = Mask[i];
295  // Undef value.
296  if (Idx < 0)
297  continue;
298  // Ensure the indices in each SrcType sized piece are sequential and that
299  // the same source is used for the whole piece.
300  if ((Idx % SrcNumElts != (i % SrcNumElts)) ||
301  (ConcatSrcs[i / SrcNumElts] >= 0 &&
302  ConcatSrcs[i / SrcNumElts] != (int)(Idx / SrcNumElts)))
303  return false;
304  // Remember which source this index came from.
305  ConcatSrcs[i / SrcNumElts] = Idx / SrcNumElts;
306  }
307 
308  // The shuffle is concatenating multiple vectors together.
309  // Collect the different operands for that.
310  Register UndefReg;
311  Register Src2 = MI.getOperand(2).getReg();
312  for (auto Src : ConcatSrcs) {
313  if (Src < 0) {
314  if (!UndefReg) {
315  Builder.setInsertPt(*MI.getParent(), MI);
316  UndefReg = Builder.buildUndef(SrcType).getReg(0);
317  }
318  Ops.push_back(UndefReg);
319  } else if (Src == 0)
320  Ops.push_back(Src1);
321  else
322  Ops.push_back(Src2);
323  }
324  return true;
325 }
326 
328  const ArrayRef<Register> Ops) {
329  Register DstReg = MI.getOperand(0).getReg();
330  Builder.setInsertPt(*MI.getParent(), MI);
331  Register NewDstReg = MRI.cloneVirtualRegister(DstReg);
332 
333  if (Ops.size() == 1)
334  Builder.buildCopy(NewDstReg, Ops[0]);
335  else
336  Builder.buildMerge(NewDstReg, Ops);
337 
338  MI.eraseFromParent();
339  replaceRegWith(MRI, DstReg, NewDstReg);
340 }
341 
342 namespace {
343 
344 /// Select a preference between two uses. CurrentUse is the current preference
345 /// while *ForCandidate is attributes of the candidate under consideration.
346 PreferredTuple ChoosePreferredUse(PreferredTuple &CurrentUse,
347  const LLT TyForCandidate,
348  unsigned OpcodeForCandidate,
349  MachineInstr *MIForCandidate) {
350  if (!CurrentUse.Ty.isValid()) {
351  if (CurrentUse.ExtendOpcode == OpcodeForCandidate ||
352  CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT)
353  return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
354  return CurrentUse;
355  }
356 
357  // We permit the extend to hoist through basic blocks but this is only
358  // sensible if the target has extending loads. If you end up lowering back
359  // into a load and extend during the legalizer then the end result is
360  // hoisting the extend up to the load.
361 
362  // Prefer defined extensions to undefined extensions as these are more
363  // likely to reduce the number of instructions.
364  if (OpcodeForCandidate == TargetOpcode::G_ANYEXT &&
365  CurrentUse.ExtendOpcode != TargetOpcode::G_ANYEXT)
366  return CurrentUse;
367  else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT &&
368  OpcodeForCandidate != TargetOpcode::G_ANYEXT)
369  return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
370 
371  // Prefer sign extensions to zero extensions as sign-extensions tend to be
372  // more expensive.
373  if (CurrentUse.Ty == TyForCandidate) {
374  if (CurrentUse.ExtendOpcode == TargetOpcode::G_SEXT &&
375  OpcodeForCandidate == TargetOpcode::G_ZEXT)
376  return CurrentUse;
377  else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ZEXT &&
378  OpcodeForCandidate == TargetOpcode::G_SEXT)
379  return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
380  }
381 
382  // This is potentially target specific. We've chosen the largest type
383  // because G_TRUNC is usually free. One potential catch with this is that
384  // some targets have a reduced number of larger registers than smaller
385  // registers and this choice potentially increases the live-range for the
386  // larger value.
387  if (TyForCandidate.getSizeInBits() > CurrentUse.Ty.getSizeInBits()) {
388  return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
389  }
390  return CurrentUse;
391 }
392 
393 /// Find a suitable place to insert some instructions and insert them. This
394 /// function accounts for special cases like inserting before a PHI node.
395 /// The current strategy for inserting before PHI's is to duplicate the
396 /// instructions for each predecessor. However, while that's ok for G_TRUNC
397 /// on most targets since it generally requires no code, other targets/cases may
398 /// want to try harder to find a dominating block.
399 static void InsertInsnsWithoutSideEffectsBeforeUse(
402  MachineOperand &UseMO)>
403  Inserter) {
404  MachineInstr &UseMI = *UseMO.getParent();
405 
406  MachineBasicBlock *InsertBB = UseMI.getParent();
407 
408  // If the use is a PHI then we want the predecessor block instead.
409  if (UseMI.isPHI()) {
410  MachineOperand *PredBB = std::next(&UseMO);
411  InsertBB = PredBB->getMBB();
412  }
413 
414  // If the block is the same block as the def then we want to insert just after
415  // the def instead of at the start of the block.
416  if (InsertBB == DefMI.getParent()) {
418  Inserter(InsertBB, std::next(InsertPt), UseMO);
419  return;
420  }
421 
422  // Otherwise we want the start of the BB
423  Inserter(InsertBB, InsertBB->getFirstNonPHI(), UseMO);
424 }
425 } // end anonymous namespace
426 
428  PreferredTuple Preferred;
429  if (matchCombineExtendingLoads(MI, Preferred)) {
430  applyCombineExtendingLoads(MI, Preferred);
431  return true;
432  }
433  return false;
434 }
435 
437  PreferredTuple &Preferred) {
438  // We match the loads and follow the uses to the extend instead of matching
439  // the extends and following the def to the load. This is because the load
440  // must remain in the same position for correctness (unless we also add code
441  // to find a safe place to sink it) whereas the extend is freely movable.
442  // It also prevents us from duplicating the load for the volatile case or just
443  // for performance.
444 
445  if (MI.getOpcode() != TargetOpcode::G_LOAD &&
446  MI.getOpcode() != TargetOpcode::G_SEXTLOAD &&
447  MI.getOpcode() != TargetOpcode::G_ZEXTLOAD)
448  return false;
449 
450  auto &LoadValue = MI.getOperand(0);
451  assert(LoadValue.isReg() && "Result wasn't a register?");
452 
453  LLT LoadValueTy = MRI.getType(LoadValue.getReg());
454  if (!LoadValueTy.isScalar())
455  return false;
456 
457  // Most architectures are going to legalize <s8 loads into at least a 1 byte
458  // load, and the MMOs can only describe memory accesses in multiples of bytes.
459  // If we try to perform extload combining on those, we can end up with
460  // %a(s8) = extload %ptr (load 1 byte from %ptr)
461  // ... which is an illegal extload instruction.
462  if (LoadValueTy.getSizeInBits() < 8)
463  return false;
464 
465  // For non power-of-2 types, they will very likely be legalized into multiple
466  // loads. Don't bother trying to match them into extending loads.
467  if (!isPowerOf2_32(LoadValueTy.getSizeInBits()))
468  return false;
469 
470  // Find the preferred type aside from the any-extends (unless it's the only
471  // one) and non-extending ops. We'll emit an extending load to that type and
472  // and emit a variant of (extend (trunc X)) for the others according to the
473  // relative type sizes. At the same time, pick an extend to use based on the
474  // extend involved in the chosen type.
475  unsigned PreferredOpcode = MI.getOpcode() == TargetOpcode::G_LOAD
476  ? TargetOpcode::G_ANYEXT
477  : MI.getOpcode() == TargetOpcode::G_SEXTLOAD
478  ? TargetOpcode::G_SEXT
479  : TargetOpcode::G_ZEXT;
480  Preferred = {LLT(), PreferredOpcode, nullptr};
481  for (auto &UseMI : MRI.use_nodbg_instructions(LoadValue.getReg())) {
482  if (UseMI.getOpcode() == TargetOpcode::G_SEXT ||
483  UseMI.getOpcode() == TargetOpcode::G_ZEXT ||
484  (UseMI.getOpcode() == TargetOpcode::G_ANYEXT)) {
485  // Check for legality.
486  if (LI) {
487  LegalityQuery::MemDesc MMDesc;
488  const auto &MMO = **MI.memoperands_begin();
489  MMDesc.SizeInBits = MMO.getSizeInBits();
490  MMDesc.AlignInBits = MMO.getAlign().value() * 8;
491  MMDesc.Ordering = MMO.getOrdering();
492  LLT UseTy = MRI.getType(UseMI.getOperand(0).getReg());
493  LLT SrcTy = MRI.getType(MI.getOperand(1).getReg());
494  if (LI->getAction({MI.getOpcode(), {UseTy, SrcTy}, {MMDesc}}).Action !=
496  continue;
497  }
498  Preferred = ChoosePreferredUse(Preferred,
499  MRI.getType(UseMI.getOperand(0).getReg()),
500  UseMI.getOpcode(), &UseMI);
501  }
502  }
503 
504  // There were no extends
505  if (!Preferred.MI)
506  return false;
507  // It should be impossible to chose an extend without selecting a different
508  // type since by definition the result of an extend is larger.
509  assert(Preferred.Ty != LoadValueTy && "Extending to same type?");
510 
511  LLVM_DEBUG(dbgs() << "Preferred use is: " << *Preferred.MI);
512  return true;
513 }
514 
515 void CombinerHelper::applyCombineExtendingLoads(MachineInstr &MI,
516  PreferredTuple &Preferred) {
517  // Rewrite the load to the chosen extending load.
518  Register ChosenDstReg = Preferred.MI->getOperand(0).getReg();
519 
520  // Inserter to insert a truncate back to the original type at a given point
521  // with some basic CSE to limit truncate duplication to one per BB.
523  auto InsertTruncAt = [&](MachineBasicBlock *InsertIntoBB,
524  MachineBasicBlock::iterator InsertBefore,
525  MachineOperand &UseMO) {
526  MachineInstr *PreviouslyEmitted = EmittedInsns.lookup(InsertIntoBB);
527  if (PreviouslyEmitted) {
528  Observer.changingInstr(*UseMO.getParent());
529  UseMO.setReg(PreviouslyEmitted->getOperand(0).getReg());
530  Observer.changedInstr(*UseMO.getParent());
531  return;
532  }
533 
534  Builder.setInsertPt(*InsertIntoBB, InsertBefore);
535  Register NewDstReg = MRI.cloneVirtualRegister(MI.getOperand(0).getReg());
536  MachineInstr *NewMI = Builder.buildTrunc(NewDstReg, ChosenDstReg);
537  EmittedInsns[InsertIntoBB] = NewMI;
538  replaceRegOpWith(MRI, UseMO, NewDstReg);
539  };
540 
542  MI.setDesc(
543  Builder.getTII().get(Preferred.ExtendOpcode == TargetOpcode::G_SEXT
544  ? TargetOpcode::G_SEXTLOAD
545  : Preferred.ExtendOpcode == TargetOpcode::G_ZEXT
546  ? TargetOpcode::G_ZEXTLOAD
547  : TargetOpcode::G_LOAD));
548 
549  // Rewrite all the uses to fix up the types.
550  auto &LoadValue = MI.getOperand(0);
552  for (auto &UseMO : MRI.use_operands(LoadValue.getReg()))
553  Uses.push_back(&UseMO);
554 
555  for (auto *UseMO : Uses) {
556  MachineInstr *UseMI = UseMO->getParent();
557 
558  // If the extend is compatible with the preferred extend then we should fix
559  // up the type and extend so that it uses the preferred use.
560  if (UseMI->getOpcode() == Preferred.ExtendOpcode ||
561  UseMI->getOpcode() == TargetOpcode::G_ANYEXT) {
562  Register UseDstReg = UseMI->getOperand(0).getReg();
563  MachineOperand &UseSrcMO = UseMI->getOperand(1);
564  const LLT UseDstTy = MRI.getType(UseDstReg);
565  if (UseDstReg != ChosenDstReg) {
566  if (Preferred.Ty == UseDstTy) {
567  // If the use has the same type as the preferred use, then merge
568  // the vregs and erase the extend. For example:
569  // %1:_(s8) = G_LOAD ...
570  // %2:_(s32) = G_SEXT %1(s8)
571  // %3:_(s32) = G_ANYEXT %1(s8)
572  // ... = ... %3(s32)
573  // rewrites to:
574  // %2:_(s32) = G_SEXTLOAD ...
575  // ... = ... %2(s32)
576  replaceRegWith(MRI, UseDstReg, ChosenDstReg);
577  Observer.erasingInstr(*UseMO->getParent());
578  UseMO->getParent()->eraseFromParent();
579  } else if (Preferred.Ty.getSizeInBits() < UseDstTy.getSizeInBits()) {
580  // If the preferred size is smaller, then keep the extend but extend
581  // from the result of the extending load. For example:
582  // %1:_(s8) = G_LOAD ...
583  // %2:_(s32) = G_SEXT %1(s8)
584  // %3:_(s64) = G_ANYEXT %1(s8)
585  // ... = ... %3(s64)
586  /// rewrites to:
587  // %2:_(s32) = G_SEXTLOAD ...
588  // %3:_(s64) = G_ANYEXT %2:_(s32)
589  // ... = ... %3(s64)
590  replaceRegOpWith(MRI, UseSrcMO, ChosenDstReg);
591  } else {
592  // If the preferred size is large, then insert a truncate. For
593  // example:
594  // %1:_(s8) = G_LOAD ...
595  // %2:_(s64) = G_SEXT %1(s8)
596  // %3:_(s32) = G_ZEXT %1(s8)
597  // ... = ... %3(s32)
598  /// rewrites to:
599  // %2:_(s64) = G_SEXTLOAD ...
600  // %4:_(s8) = G_TRUNC %2:_(s32)
601  // %3:_(s64) = G_ZEXT %2:_(s8)
602  // ... = ... %3(s64)
603  InsertInsnsWithoutSideEffectsBeforeUse(Builder, MI, *UseMO,
604  InsertTruncAt);
605  }
606  continue;
607  }
608  // The use is (one of) the uses of the preferred use we chose earlier.
609  // We're going to update the load to def this value later so just erase
610  // the old extend.
611  Observer.erasingInstr(*UseMO->getParent());
612  UseMO->getParent()->eraseFromParent();
613  continue;
614  }
615 
616  // The use isn't an extend. Truncate back to the type we originally loaded.
617  // This is free on many targets.
618  InsertInsnsWithoutSideEffectsBeforeUse(Builder, MI, *UseMO, InsertTruncAt);
619  }
620 
621  MI.getOperand(0).setReg(ChosenDstReg);
623 }
624 
626  const MachineInstr &UseMI) {
627  assert(!DefMI.isDebugInstr() && !UseMI.isDebugInstr() &&
628  "shouldn't consider debug uses");
629  assert(DefMI.getParent() == UseMI.getParent());
630  if (&DefMI == &UseMI)
631  return false;
632  const MachineBasicBlock &MBB = *DefMI.getParent();
633  auto DefOrUse = find_if(MBB, [&DefMI, &UseMI](const MachineInstr &MI) {
634  return &MI == &DefMI || &MI == &UseMI;
635  });
636  if (DefOrUse == MBB.end())
637  llvm_unreachable("Block must contain both DefMI and UseMI!");
638  return &*DefOrUse == &DefMI;
639 }
640 
642  const MachineInstr &UseMI) {
643  assert(!DefMI.isDebugInstr() && !UseMI.isDebugInstr() &&
644  "shouldn't consider debug uses");
645  if (MDT)
646  return MDT->dominates(&DefMI, &UseMI);
647  else if (DefMI.getParent() != UseMI.getParent())
648  return false;
649 
650  return isPredecessor(DefMI, UseMI);
651 }
652 
654  assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG);
655  Register SrcReg = MI.getOperand(1).getReg();
656  Register LoadUser = SrcReg;
657 
658  if (MRI.getType(SrcReg).isVector())
659  return false;
660 
661  Register TruncSrc;
662  if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc))))
663  LoadUser = TruncSrc;
664 
665  uint64_t SizeInBits = MI.getOperand(2).getImm();
666  // If the source is a G_SEXTLOAD from the same bit width, then we don't
667  // need any extend at all, just a truncate.
668  if (auto *LoadMI = getOpcodeDef(TargetOpcode::G_SEXTLOAD, LoadUser, MRI)) {
669  const auto &MMO = **LoadMI->memoperands_begin();
670  // If truncating more than the original extended value, abort.
671  if (TruncSrc && MRI.getType(TruncSrc).getSizeInBits() < MMO.getSizeInBits())
672  return false;
673  if (MMO.getSizeInBits() == SizeInBits)
674  return true;
675  }
676  return false;
677 }
678 
680  assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG);
682  Builder.buildCopy(MI.getOperand(0).getReg(), MI.getOperand(1).getReg());
683  MI.eraseFromParent();
684  return true;
685 }
686 
688  MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) {
689  assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG);
690 
691  // Only supports scalars for now.
692  if (MRI.getType(MI.getOperand(0).getReg()).isVector())
693  return false;
694 
695  Register SrcReg = MI.getOperand(1).getReg();
696  MachineInstr *LoadDef = getOpcodeDef(TargetOpcode::G_LOAD, SrcReg, MRI);
697  if (!LoadDef || !MRI.hasOneNonDBGUse(LoadDef->getOperand(0).getReg()))
698  return false;
699 
700  // If the sign extend extends from a narrower width than the load's width,
701  // then we can narrow the load width when we combine to a G_SEXTLOAD.
702  auto &MMO = **LoadDef->memoperands_begin();
703  // Don't do this for non-simple loads.
704  if (MMO.isAtomic() || MMO.isVolatile())
705  return false;
706 
707  // Avoid widening the load at all.
708  unsigned NewSizeBits =
709  std::min((uint64_t)MI.getOperand(2).getImm(), MMO.getSizeInBits());
710 
711  // Don't generate G_SEXTLOADs with a < 1 byte width.
712  if (NewSizeBits < 8)
713  return false;
714  // Don't bother creating a non-power-2 sextload, it will likely be broken up
715  // anyway for most targets.
716  if (!isPowerOf2_32(NewSizeBits))
717  return false;
718  MatchInfo = std::make_tuple(LoadDef->getOperand(0).getReg(), NewSizeBits);
719  return true;
720 }
721 
723  MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) {
724  assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG);
725  Register LoadReg;
726  unsigned ScalarSizeBits;
727  std::tie(LoadReg, ScalarSizeBits) = MatchInfo;
728  auto *LoadDef = MRI.getVRegDef(LoadReg);
729  assert(LoadDef && "Expected a load reg");
730 
731  // If we have the following:
732  // %ld = G_LOAD %ptr, (load 2)
733  // %ext = G_SEXT_INREG %ld, 8
734  // ==>
735  // %ld = G_SEXTLOAD %ptr (load 1)
736 
737  auto &MMO = **LoadDef->memoperands_begin();
738  Builder.setInstrAndDebugLoc(*LoadDef);
739  auto &MF = Builder.getMF();
740  auto PtrInfo = MMO.getPointerInfo();
741  auto *NewMMO = MF.getMachineMemOperand(&MMO, PtrInfo, ScalarSizeBits / 8);
742  Builder.buildLoadInstr(TargetOpcode::G_SEXTLOAD, MI.getOperand(0).getReg(),
743  LoadDef->getOperand(1).getReg(), *NewMMO);
744  MI.eraseFromParent();
745  return true;
746 }
747 
748 bool CombinerHelper::findPostIndexCandidate(MachineInstr &MI, Register &Addr,
749  Register &Base, Register &Offset) {
750  auto &MF = *MI.getParent()->getParent();
751  const auto &TLI = *MF.getSubtarget().getTargetLowering();
752 
753 #ifndef NDEBUG
754  unsigned Opcode = MI.getOpcode();
755  assert(Opcode == TargetOpcode::G_LOAD || Opcode == TargetOpcode::G_SEXTLOAD ||
756  Opcode == TargetOpcode::G_ZEXTLOAD || Opcode == TargetOpcode::G_STORE);
757 #endif
758 
759  Base = MI.getOperand(1).getReg();
760  MachineInstr *BaseDef = MRI.getUniqueVRegDef(Base);
761  if (BaseDef && BaseDef->getOpcode() == TargetOpcode::G_FRAME_INDEX)
762  return false;
763 
764  LLVM_DEBUG(dbgs() << "Searching for post-indexing opportunity for: " << MI);
765  // FIXME: The following use traversal needs a bail out for patholigical cases.
766  for (auto &Use : MRI.use_nodbg_instructions(Base)) {
767  if (Use.getOpcode() != TargetOpcode::G_PTR_ADD)
768  continue;
769 
770  Offset = Use.getOperand(2).getReg();
771  if (!ForceLegalIndexing &&
772  !TLI.isIndexingLegal(MI, Base, Offset, /*IsPre*/ false, MRI)) {
773  LLVM_DEBUG(dbgs() << " Ignoring candidate with illegal addrmode: "
774  << Use);
775  continue;
776  }
777 
778  // Make sure the offset calculation is before the potentially indexed op.
779  // FIXME: we really care about dependency here. The offset calculation might
780  // be movable.
781  MachineInstr *OffsetDef = MRI.getUniqueVRegDef(Offset);
782  if (!OffsetDef || !dominates(*OffsetDef, MI)) {
783  LLVM_DEBUG(dbgs() << " Ignoring candidate with offset after mem-op: "
784  << Use);
785  continue;
786  }
787 
788  // FIXME: check whether all uses of Base are load/store with foldable
789  // addressing modes. If so, using the normal addr-modes is better than
790  // forming an indexed one.
791 
792  bool MemOpDominatesAddrUses = true;
793  for (auto &PtrAddUse :
794  MRI.use_nodbg_instructions(Use.getOperand(0).getReg())) {
795  if (!dominates(MI, PtrAddUse)) {
796  MemOpDominatesAddrUses = false;
797  break;
798  }
799  }
800 
801  if (!MemOpDominatesAddrUses) {
802  LLVM_DEBUG(
803  dbgs() << " Ignoring candidate as memop does not dominate uses: "
804  << Use);
805  continue;
806  }
807 
808  LLVM_DEBUG(dbgs() << " Found match: " << Use);
809  Addr = Use.getOperand(0).getReg();
810  return true;
811  }
812 
813  return false;
814 }
815 
816 bool CombinerHelper::findPreIndexCandidate(MachineInstr &MI, Register &Addr,
817  Register &Base, Register &Offset) {
818  auto &MF = *MI.getParent()->getParent();
819  const auto &TLI = *MF.getSubtarget().getTargetLowering();
820 
821 #ifndef NDEBUG
822  unsigned Opcode = MI.getOpcode();
823  assert(Opcode == TargetOpcode::G_LOAD || Opcode == TargetOpcode::G_SEXTLOAD ||
824  Opcode == TargetOpcode::G_ZEXTLOAD || Opcode == TargetOpcode::G_STORE);
825 #endif
826 
827  Addr = MI.getOperand(1).getReg();
828  MachineInstr *AddrDef = getOpcodeDef(TargetOpcode::G_PTR_ADD, Addr, MRI);
829  if (!AddrDef || MRI.hasOneNonDBGUse(Addr))
830  return false;
831 
832  Base = AddrDef->getOperand(1).getReg();
833  Offset = AddrDef->getOperand(2).getReg();
834 
835  LLVM_DEBUG(dbgs() << "Found potential pre-indexed load_store: " << MI);
836 
837  if (!ForceLegalIndexing &&
838  !TLI.isIndexingLegal(MI, Base, Offset, /*IsPre*/ true, MRI)) {
839  LLVM_DEBUG(dbgs() << " Skipping, not legal for target");
840  return false;
841  }
842 
843  MachineInstr *BaseDef = getDefIgnoringCopies(Base, MRI);
844  if (BaseDef->getOpcode() == TargetOpcode::G_FRAME_INDEX) {
845  LLVM_DEBUG(dbgs() << " Skipping, frame index would need copy anyway.");
846  return false;
847  }
848 
849  if (MI.getOpcode() == TargetOpcode::G_STORE) {
850  // Would require a copy.
851  if (Base == MI.getOperand(0).getReg()) {
852  LLVM_DEBUG(dbgs() << " Skipping, storing base so need copy anyway.");
853  return false;
854  }
855 
856  // We're expecting one use of Addr in MI, but it could also be the
857  // value stored, which isn't actually dominated by the instruction.
858  if (MI.getOperand(0).getReg() == Addr) {
859  LLVM_DEBUG(dbgs() << " Skipping, does not dominate all addr uses");
860  return false;
861  }
862  }
863 
864  // FIXME: check whether all uses of the base pointer are constant PtrAdds.
865  // That might allow us to end base's liveness here by adjusting the constant.
866 
867  for (auto &UseMI : MRI.use_nodbg_instructions(Addr)) {
868  if (!dominates(MI, UseMI)) {
869  LLVM_DEBUG(dbgs() << " Skipping, does not dominate all addr uses.");
870  return false;
871  }
872  }
873 
874  return true;
875 }
876 
878  IndexedLoadStoreMatchInfo MatchInfo;
879  if (matchCombineIndexedLoadStore(MI, MatchInfo)) {
880  applyCombineIndexedLoadStore(MI, MatchInfo);
881  return true;
882  }
883  return false;
884 }
885 
887  unsigned Opcode = MI.getOpcode();
888  if (Opcode != TargetOpcode::G_LOAD && Opcode != TargetOpcode::G_SEXTLOAD &&
889  Opcode != TargetOpcode::G_ZEXTLOAD && Opcode != TargetOpcode::G_STORE)
890  return false;
891 
892  // For now, no targets actually support these opcodes so don't waste time
893  // running these unless we're forced to for testing.
894  if (!ForceLegalIndexing)
895  return false;
896 
897  MatchInfo.IsPre = findPreIndexCandidate(MI, MatchInfo.Addr, MatchInfo.Base,
898  MatchInfo.Offset);
899  if (!MatchInfo.IsPre &&
900  !findPostIndexCandidate(MI, MatchInfo.Addr, MatchInfo.Base,
901  MatchInfo.Offset))
902  return false;
903 
904  return true;
905 }
906 
909  MachineInstr &AddrDef = *MRI.getUniqueVRegDef(MatchInfo.Addr);
910  MachineIRBuilder MIRBuilder(MI);
911  unsigned Opcode = MI.getOpcode();
912  bool IsStore = Opcode == TargetOpcode::G_STORE;
913  unsigned NewOpcode;
914  switch (Opcode) {
915  case TargetOpcode::G_LOAD:
916  NewOpcode = TargetOpcode::G_INDEXED_LOAD;
917  break;
918  case TargetOpcode::G_SEXTLOAD:
919  NewOpcode = TargetOpcode::G_INDEXED_SEXTLOAD;
920  break;
921  case TargetOpcode::G_ZEXTLOAD:
922  NewOpcode = TargetOpcode::G_INDEXED_ZEXTLOAD;
923  break;
924  case TargetOpcode::G_STORE:
925  NewOpcode = TargetOpcode::G_INDEXED_STORE;
926  break;
927  default:
928  llvm_unreachable("Unknown load/store opcode");
929  }
930 
931  auto MIB = MIRBuilder.buildInstr(NewOpcode);
932  if (IsStore) {
933  MIB.addDef(MatchInfo.Addr);
934  MIB.addUse(MI.getOperand(0).getReg());
935  } else {
936  MIB.addDef(MI.getOperand(0).getReg());
937  MIB.addDef(MatchInfo.Addr);
938  }
939 
940  MIB.addUse(MatchInfo.Base);
941  MIB.addUse(MatchInfo.Offset);
942  MIB.addImm(MatchInfo.IsPre);
943  MI.eraseFromParent();
944  AddrDef.eraseFromParent();
945 
946  LLVM_DEBUG(dbgs() << " Combinined to indexed operation");
947 }
948 
950  MachineInstr *&OtherMI) {
951  unsigned Opcode = MI.getOpcode();
952  bool IsDiv, IsSigned;
953 
954  switch (Opcode) {
955  default:
956  llvm_unreachable("Unexpected opcode!");
957  case TargetOpcode::G_SDIV:
958  case TargetOpcode::G_UDIV: {
959  IsDiv = true;
960  IsSigned = Opcode == TargetOpcode::G_SDIV;
961  break;
962  }
963  case TargetOpcode::G_SREM:
964  case TargetOpcode::G_UREM: {
965  IsDiv = false;
966  IsSigned = Opcode == TargetOpcode::G_SREM;
967  break;
968  }
969  }
970 
971  Register Src1 = MI.getOperand(1).getReg();
972  unsigned DivOpcode, RemOpcode, DivremOpcode;
973  if (IsSigned) {
974  DivOpcode = TargetOpcode::G_SDIV;
975  RemOpcode = TargetOpcode::G_SREM;
976  DivremOpcode = TargetOpcode::G_SDIVREM;
977  } else {
978  DivOpcode = TargetOpcode::G_UDIV;
979  RemOpcode = TargetOpcode::G_UREM;
980  DivremOpcode = TargetOpcode::G_UDIVREM;
981  }
982 
983  if (!isLegalOrBeforeLegalizer({DivremOpcode, {MRI.getType(Src1)}}))
984  return false;
985 
986  // Combine:
987  // %div:_ = G_[SU]DIV %src1:_, %src2:_
988  // %rem:_ = G_[SU]REM %src1:_, %src2:_
989  // into:
990  // %div:_, %rem:_ = G_[SU]DIVREM %src1:_, %src2:_
991 
992  // Combine:
993  // %rem:_ = G_[SU]REM %src1:_, %src2:_
994  // %div:_ = G_[SU]DIV %src1:_, %src2:_
995  // into:
996  // %div:_, %rem:_ = G_[SU]DIVREM %src1:_, %src2:_
997 
998  for (auto &UseMI : MRI.use_nodbg_instructions(Src1)) {
999  if (MI.getParent() == UseMI.getParent() &&
1000  ((IsDiv && UseMI.getOpcode() == RemOpcode) ||
1001  (!IsDiv && UseMI.getOpcode() == DivOpcode)) &&
1002  matchEqualDefs(MI.getOperand(2), UseMI.getOperand(2))) {
1003  OtherMI = &UseMI;
1004  return true;
1005  }
1006  }
1007 
1008  return false;
1009 }
1010 
1012  MachineInstr *&OtherMI) {
1013  unsigned Opcode = MI.getOpcode();
1014  assert(OtherMI && "OtherMI shouldn't be empty.");
1015 
1016  Register DestDivReg, DestRemReg;
1017  if (Opcode == TargetOpcode::G_SDIV || Opcode == TargetOpcode::G_UDIV) {
1018  DestDivReg = MI.getOperand(0).getReg();
1019  DestRemReg = OtherMI->getOperand(0).getReg();
1020  } else {
1021  DestDivReg = OtherMI->getOperand(0).getReg();
1022  DestRemReg = MI.getOperand(0).getReg();
1023  }
1024 
1025  bool IsSigned =
1026  Opcode == TargetOpcode::G_SDIV || Opcode == TargetOpcode::G_SREM;
1028  Builder.buildInstr(IsSigned ? TargetOpcode::G_SDIVREM
1029  : TargetOpcode::G_UDIVREM,
1030  {DestDivReg, DestRemReg},
1031  {MI.getOperand(1).getReg(), MI.getOperand(2).getReg()});
1032  MI.eraseFromParent();
1033  OtherMI->eraseFromParent();
1034 }
1035 
1037  if (MI.getOpcode() != TargetOpcode::G_BR)
1038  return false;
1039 
1040  // Try to match the following:
1041  // bb1:
1042  // G_BRCOND %c1, %bb2
1043  // G_BR %bb3
1044  // bb2:
1045  // ...
1046  // bb3:
1047 
1048  // The above pattern does not have a fall through to the successor bb2, always
1049  // resulting in a branch no matter which path is taken. Here we try to find
1050  // and replace that pattern with conditional branch to bb3 and otherwise
1051  // fallthrough to bb2. This is generally better for branch predictors.
1052 
1053  MachineBasicBlock *MBB = MI.getParent();
1055  if (BrIt == MBB->begin())
1056  return false;
1057  assert(std::next(BrIt) == MBB->end() && "expected G_BR to be a terminator");
1058 
1059  MachineInstr *BrCond = &*std::prev(BrIt);
1060  if (BrCond->getOpcode() != TargetOpcode::G_BRCOND)
1061  return false;
1062 
1063  // Check that the next block is the conditional branch target. Also make sure
1064  // that it isn't the same as the G_BR's target (otherwise, this will loop.)
1065  MachineBasicBlock *BrCondTarget = BrCond->getOperand(1).getMBB();
1066  return BrCondTarget != MI.getOperand(0).getMBB() &&
1067  MBB->isLayoutSuccessor(BrCondTarget);
1068 }
1069 
1071  MachineBasicBlock *BrTarget = MI.getOperand(0).getMBB();
1073  MachineInstr *BrCond = &*std::prev(BrIt);
1074 
1075  Builder.setInstrAndDebugLoc(*BrCond);
1076  LLT Ty = MRI.getType(BrCond->getOperand(0).getReg());
1077  // FIXME: Does int/fp matter for this? If so, we might need to restrict
1078  // this to i1 only since we might not know for sure what kind of
1079  // compare generated the condition value.
1080  auto True = Builder.buildConstant(
1081  Ty, getICmpTrueVal(getTargetLowering(), false, false));
1082  auto Xor = Builder.buildXor(Ty, BrCond->getOperand(0), True);
1083 
1084  auto *FallthroughBB = BrCond->getOperand(1).getMBB();
1086  MI.getOperand(0).setMBB(FallthroughBB);
1088 
1089  // Change the conditional branch to use the inverted condition and
1090  // new target block.
1091  Observer.changingInstr(*BrCond);
1092  BrCond->getOperand(0).setReg(Xor.getReg(0));
1093  BrCond->getOperand(1).setMBB(BrTarget);
1094  Observer.changedInstr(*BrCond);
1095 }
1096 
1098  // On Darwin, -Os means optimize for size without hurting performance, so
1099  // only really optimize for size when -Oz (MinSize) is used.
1100  if (MF.getTarget().getTargetTriple().isOSDarwin())
1101  return MF.getFunction().hasMinSize();
1102  return MF.getFunction().hasOptSize();
1103 }
1104 
1105 // Returns a list of types to use for memory op lowering in MemOps. A partial
1106 // port of findOptimalMemOpLowering in TargetLowering.
1107 static bool findGISelOptimalMemOpLowering(std::vector<LLT> &MemOps,
1108  unsigned Limit, const MemOp &Op,
1109  unsigned DstAS, unsigned SrcAS,
1110  const AttributeList &FuncAttributes,
1111  const TargetLowering &TLI) {
1112  if (Op.isMemcpyWithFixedDstAlign() && Op.getSrcAlign() < Op.getDstAlign())
1113  return false;
1114 
1115  LLT Ty = TLI.getOptimalMemOpLLT(Op, FuncAttributes);
1116 
1117  if (Ty == LLT()) {
1118  // Use the largest scalar type whose alignment constraints are satisfied.
1119  // We only need to check DstAlign here as SrcAlign is always greater or
1120  // equal to DstAlign (or zero).
1121  Ty = LLT::scalar(64);
1122  if (Op.isFixedDstAlign())
1123  while (Op.getDstAlign() < Ty.getSizeInBytes() &&
1124  !TLI.allowsMisalignedMemoryAccesses(Ty, DstAS, Op.getDstAlign()))
1125  Ty = LLT::scalar(Ty.getSizeInBytes());
1126  assert(Ty.getSizeInBits() > 0 && "Could not find valid type");
1127  // FIXME: check for the largest legal type we can load/store to.
1128  }
1129 
1130  unsigned NumMemOps = 0;
1131  uint64_t Size = Op.size();
1132  while (Size) {
1133  unsigned TySize = Ty.getSizeInBytes();
1134  while (TySize > Size) {
1135  // For now, only use non-vector load / store's for the left-over pieces.
1136  LLT NewTy = Ty;
1137  // FIXME: check for mem op safety and legality of the types. Not all of
1138  // SDAGisms map cleanly to GISel concepts.
1139  if (NewTy.isVector())
1140  NewTy = NewTy.getSizeInBits() > 64 ? LLT::scalar(64) : LLT::scalar(32);
1141  NewTy = LLT::scalar(PowerOf2Floor(NewTy.getSizeInBits() - 1));
1142  unsigned NewTySize = NewTy.getSizeInBytes();
1143  assert(NewTySize > 0 && "Could not find appropriate type");
1144 
1145  // If the new LLT cannot cover all of the remaining bits, then consider
1146  // issuing a (or a pair of) unaligned and overlapping load / store.
1147  bool Fast;
1148  // Need to get a VT equivalent for allowMisalignedMemoryAccesses().
1149  MVT VT = getMVTForLLT(Ty);
1150  if (NumMemOps && Op.allowOverlap() && NewTySize < Size &&
1152  VT, DstAS, Op.isFixedDstAlign() ? Op.getDstAlign() : Align(1),
1153  MachineMemOperand::MONone, &Fast) &&
1154  Fast)
1155  TySize = Size;
1156  else {
1157  Ty = NewTy;
1158  TySize = NewTySize;
1159  }
1160  }
1161 
1162  if (++NumMemOps > Limit)
1163  return false;
1164 
1165  MemOps.push_back(Ty);
1166  Size -= TySize;
1167  }
1168 
1169  return true;
1170 }
1171 
1173  if (Ty.isVector())
1175  Ty.getNumElements());
1176  return IntegerType::get(C, Ty.getSizeInBits());
1177 }
1178 
1179 // Get a vectorized representation of the memset value operand, GISel edition.
1181  MachineRegisterInfo &MRI = *MIB.getMRI();
1182  unsigned NumBits = Ty.getScalarSizeInBits();
1183  auto ValVRegAndVal = getConstantVRegValWithLookThrough(Val, MRI);
1184  if (!Ty.isVector() && ValVRegAndVal) {
1185  APInt Scalar = ValVRegAndVal->Value.truncOrSelf(8);
1186  APInt SplatVal = APInt::getSplat(NumBits, Scalar);
1187  return MIB.buildConstant(Ty, SplatVal).getReg(0);
1188  }
1189 
1190  // Extend the byte value to the larger type, and then multiply by a magic
1191  // value 0x010101... in order to replicate it across every byte.
1192  // Unless it's zero, in which case just emit a larger G_CONSTANT 0.
1193  if (ValVRegAndVal && ValVRegAndVal->Value == 0) {
1194  return MIB.buildConstant(Ty, 0).getReg(0);
1195  }
1196 
1197  LLT ExtType = Ty.getScalarType();
1198  auto ZExt = MIB.buildZExtOrTrunc(ExtType, Val);
1199  if (NumBits > 8) {
1200  APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
1201  auto MagicMI = MIB.buildConstant(ExtType, Magic);
1202  Val = MIB.buildMul(ExtType, ZExt, MagicMI).getReg(0);
1203  }
1204 
1205  // For vector types create a G_BUILD_VECTOR.
1206  if (Ty.isVector())
1207  Val = MIB.buildSplatVector(Ty, Val).getReg(0);
1208 
1209  return Val;
1210 }
1211 
1212 bool CombinerHelper::optimizeMemset(MachineInstr &MI, Register Dst,
1213  Register Val, unsigned KnownLen,
1214  Align Alignment, bool IsVolatile) {
1215  auto &MF = *MI.getParent()->getParent();
1216  const auto &TLI = *MF.getSubtarget().getTargetLowering();
1217  auto &DL = MF.getDataLayout();
1218  LLVMContext &C = MF.getFunction().getContext();
1219 
1220  assert(KnownLen != 0 && "Have a zero length memset length!");
1221 
1222  bool DstAlignCanChange = false;
1223  MachineFrameInfo &MFI = MF.getFrameInfo();
1224  bool OptSize = shouldLowerMemFuncForSize(MF);
1225 
1226  MachineInstr *FIDef = getOpcodeDef(TargetOpcode::G_FRAME_INDEX, Dst, MRI);
1227  if (FIDef && !MFI.isFixedObjectIndex(FIDef->getOperand(1).getIndex()))
1228  DstAlignCanChange = true;
1229 
1230  unsigned Limit = TLI.getMaxStoresPerMemset(OptSize);
1231  std::vector<LLT> MemOps;
1232 
1233  const auto &DstMMO = **MI.memoperands_begin();
1234  MachinePointerInfo DstPtrInfo = DstMMO.getPointerInfo();
1235 
1236  auto ValVRegAndVal = getConstantVRegValWithLookThrough(Val, MRI);
1237  bool IsZeroVal = ValVRegAndVal && ValVRegAndVal->Value == 0;
1238 
1239  if (!findGISelOptimalMemOpLowering(MemOps, Limit,
1240  MemOp::Set(KnownLen, DstAlignCanChange,
1241  Alignment,
1242  /*IsZeroMemset=*/IsZeroVal,
1243  /*IsVolatile=*/IsVolatile),
1244  DstPtrInfo.getAddrSpace(), ~0u,
1245  MF.getFunction().getAttributes(), TLI))
1246  return false;
1247 
1248  if (DstAlignCanChange) {
1249  // Get an estimate of the type from the LLT.
1250  Type *IRTy = getTypeForLLT(MemOps[0], C);
1251  Align NewAlign = DL.getABITypeAlign(IRTy);
1252  if (NewAlign > Alignment) {
1253  Alignment = NewAlign;
1254  unsigned FI = FIDef->getOperand(1).getIndex();
1255  // Give the stack frame object a larger alignment if needed.
1256  if (MFI.getObjectAlign(FI) < Alignment)
1257  MFI.setObjectAlignment(FI, Alignment);
1258  }
1259  }
1260 
1261  MachineIRBuilder MIB(MI);
1262  // Find the largest store and generate the bit pattern for it.
1263  LLT LargestTy = MemOps[0];
1264  for (unsigned i = 1; i < MemOps.size(); i++)
1265  if (MemOps[i].getSizeInBits() > LargestTy.getSizeInBits())
1266  LargestTy = MemOps[i];
1267 
1268  // The memset stored value is always defined as an s8, so in order to make it
1269  // work with larger store types we need to repeat the bit pattern across the
1270  // wider type.
1271  Register MemSetValue = getMemsetValue(Val, LargestTy, MIB);
1272 
1273  if (!MemSetValue)
1274  return false;
1275 
1276  // Generate the stores. For each store type in the list, we generate the
1277  // matching store of that type to the destination address.
1278  LLT PtrTy = MRI.getType(Dst);
1279  unsigned DstOff = 0;
1280  unsigned Size = KnownLen;
1281  for (unsigned I = 0; I < MemOps.size(); I++) {
1282  LLT Ty = MemOps[I];
1283  unsigned TySize = Ty.getSizeInBytes();
1284  if (TySize > Size) {
1285  // Issuing an unaligned load / store pair that overlaps with the previous
1286  // pair. Adjust the offset accordingly.
1287  assert(I == MemOps.size() - 1 && I != 0);
1288  DstOff -= TySize - Size;
1289  }
1290 
1291  // If this store is smaller than the largest store see whether we can get
1292  // the smaller value for free with a truncate.
1293  Register Value = MemSetValue;
1294  if (Ty.getSizeInBits() < LargestTy.getSizeInBits()) {
1295  MVT VT = getMVTForLLT(Ty);
1296  MVT LargestVT = getMVTForLLT(LargestTy);
1297  if (!LargestTy.isVector() && !Ty.isVector() &&
1298  TLI.isTruncateFree(LargestVT, VT))
1299  Value = MIB.buildTrunc(Ty, MemSetValue).getReg(0);
1300  else
1301  Value = getMemsetValue(Val, Ty, MIB);
1302  if (!Value)
1303  return false;
1304  }
1305 
1306  auto *StoreMMO =
1307  MF.getMachineMemOperand(&DstMMO, DstOff, Ty.getSizeInBytes());
1308 
1309  Register Ptr = Dst;
1310  if (DstOff != 0) {
1311  auto Offset =
1312  MIB.buildConstant(LLT::scalar(PtrTy.getSizeInBits()), DstOff);
1313  Ptr = MIB.buildPtrAdd(PtrTy, Dst, Offset).getReg(0);
1314  }
1315 
1316  MIB.buildStore(Value, Ptr, *StoreMMO);
1317  DstOff += Ty.getSizeInBytes();
1318  Size -= TySize;
1319  }
1320 
1321  MI.eraseFromParent();
1322  return true;
1323 }
1324 
1325 bool CombinerHelper::optimizeMemcpy(MachineInstr &MI, Register Dst,
1326  Register Src, unsigned KnownLen,
1327  Align DstAlign, Align SrcAlign,
1328  bool IsVolatile) {
1329  auto &MF = *MI.getParent()->getParent();
1330  const auto &TLI = *MF.getSubtarget().getTargetLowering();
1331  auto &DL = MF.getDataLayout();
1332  LLVMContext &C = MF.getFunction().getContext();
1333 
1334  assert(KnownLen != 0 && "Have a zero length memcpy length!");
1335 
1336  bool DstAlignCanChange = false;
1337  MachineFrameInfo &MFI = MF.getFrameInfo();
1338  bool OptSize = shouldLowerMemFuncForSize(MF);
1339  Align Alignment = commonAlignment(DstAlign, SrcAlign);
1340 
1341  MachineInstr *FIDef = getOpcodeDef(TargetOpcode::G_FRAME_INDEX, Dst, MRI);
1342  if (FIDef && !MFI.isFixedObjectIndex(FIDef->getOperand(1).getIndex()))
1343  DstAlignCanChange = true;
1344 
1345  // FIXME: infer better src pointer alignment like SelectionDAG does here.
1346  // FIXME: also use the equivalent of isMemSrcFromConstant and alwaysinlining
1347  // if the memcpy is in a tail call position.
1348 
1349  unsigned Limit = TLI.getMaxStoresPerMemcpy(OptSize);
1350  std::vector<LLT> MemOps;
1351 
1352  const auto &DstMMO = **MI.memoperands_begin();
1353  const auto &SrcMMO = **std::next(MI.memoperands_begin());
1354  MachinePointerInfo DstPtrInfo = DstMMO.getPointerInfo();
1355  MachinePointerInfo SrcPtrInfo = SrcMMO.getPointerInfo();
1356 
1358  MemOps, Limit,
1359  MemOp::Copy(KnownLen, DstAlignCanChange, Alignment, SrcAlign,
1360  IsVolatile),
1361  DstPtrInfo.getAddrSpace(), SrcPtrInfo.getAddrSpace(),
1362  MF.getFunction().getAttributes(), TLI))
1363  return false;
1364 
1365  if (DstAlignCanChange) {
1366  // Get an estimate of the type from the LLT.
1367  Type *IRTy = getTypeForLLT(MemOps[0], C);
1368  Align NewAlign = DL.getABITypeAlign(IRTy);
1369 
1370  // Don't promote to an alignment that would require dynamic stack
1371  // realignment.
1372  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1373  if (!TRI->hasStackRealignment(MF))
1374  while (NewAlign > Alignment && DL.exceedsNaturalStackAlignment(NewAlign))
1375  NewAlign = NewAlign / 2;
1376 
1377  if (NewAlign > Alignment) {
1378  Alignment = NewAlign;
1379  unsigned FI = FIDef->getOperand(1).getIndex();
1380  // Give the stack frame object a larger alignment if needed.
1381  if (MFI.getObjectAlign(FI) < Alignment)
1382  MFI.setObjectAlignment(FI, Alignment);
1383  }
1384  }
1385 
1386  LLVM_DEBUG(dbgs() << "Inlining memcpy: " << MI << " into loads & stores\n");
1387 
1388  MachineIRBuilder MIB(MI);
1389  // Now we need to emit a pair of load and stores for each of the types we've
1390  // collected. I.e. for each type, generate a load from the source pointer of
1391  // that type width, and then generate a corresponding store to the dest buffer
1392  // of that value loaded. This can result in a sequence of loads and stores
1393  // mixed types, depending on what the target specifies as good types to use.
1394  unsigned CurrOffset = 0;
1395  LLT PtrTy = MRI.getType(Src);
1396  unsigned Size = KnownLen;
1397  for (auto CopyTy : MemOps) {
1398  // Issuing an unaligned load / store pair that overlaps with the previous
1399  // pair. Adjust the offset accordingly.
1400  if (CopyTy.getSizeInBytes() > Size)
1401  CurrOffset -= CopyTy.getSizeInBytes() - Size;
1402 
1403  // Construct MMOs for the accesses.
1404  auto *LoadMMO =
1405  MF.getMachineMemOperand(&SrcMMO, CurrOffset, CopyTy.getSizeInBytes());
1406  auto *StoreMMO =
1407  MF.getMachineMemOperand(&DstMMO, CurrOffset, CopyTy.getSizeInBytes());
1408 
1409  // Create the load.
1410  Register LoadPtr = Src;
1411  Register Offset;
1412  if (CurrOffset != 0) {
1413  Offset = MIB.buildConstant(LLT::scalar(PtrTy.getSizeInBits()), CurrOffset)
1414  .getReg(0);
1415  LoadPtr = MIB.buildPtrAdd(PtrTy, Src, Offset).getReg(0);
1416  }
1417  auto LdVal = MIB.buildLoad(CopyTy, LoadPtr, *LoadMMO);
1418 
1419  // Create the store.
1420  Register StorePtr =
1421  CurrOffset == 0 ? Dst : MIB.buildPtrAdd(PtrTy, Dst, Offset).getReg(0);
1422  MIB.buildStore(LdVal, StorePtr, *StoreMMO);
1423  CurrOffset += CopyTy.getSizeInBytes();
1424  Size -= CopyTy.getSizeInBytes();
1425  }
1426 
1427  MI.eraseFromParent();
1428  return true;
1429 }
1430 
1431 bool CombinerHelper::optimizeMemmove(MachineInstr &MI, Register Dst,
1432  Register Src, unsigned KnownLen,
1433  Align DstAlign, Align SrcAlign,
1434  bool IsVolatile) {
1435  auto &MF = *MI.getParent()->getParent();
1436  const auto &TLI = *MF.getSubtarget().getTargetLowering();
1437  auto &DL = MF.getDataLayout();
1438  LLVMContext &C = MF.getFunction().getContext();
1439 
1440  assert(KnownLen != 0 && "Have a zero length memmove length!");
1441 
1442  bool DstAlignCanChange = false;
1443  MachineFrameInfo &MFI = MF.getFrameInfo();
1444  bool OptSize = shouldLowerMemFuncForSize(MF);
1445  Align Alignment = commonAlignment(DstAlign, SrcAlign);
1446 
1447  MachineInstr *FIDef = getOpcodeDef(TargetOpcode::G_FRAME_INDEX, Dst, MRI);
1448  if (FIDef && !MFI.isFixedObjectIndex(FIDef->getOperand(1).getIndex()))
1449  DstAlignCanChange = true;
1450 
1451  unsigned Limit = TLI.getMaxStoresPerMemmove(OptSize);
1452  std::vector<LLT> MemOps;
1453 
1454  const auto &DstMMO = **MI.memoperands_begin();
1455  const auto &SrcMMO = **std::next(MI.memoperands_begin());
1456  MachinePointerInfo DstPtrInfo = DstMMO.getPointerInfo();
1457  MachinePointerInfo SrcPtrInfo = SrcMMO.getPointerInfo();
1458 
1459  // FIXME: SelectionDAG always passes false for 'AllowOverlap', apparently due
1460  // to a bug in it's findOptimalMemOpLowering implementation. For now do the
1461  // same thing here.
1463  MemOps, Limit,
1464  MemOp::Copy(KnownLen, DstAlignCanChange, Alignment, SrcAlign,
1465  /*IsVolatile*/ true),
1466  DstPtrInfo.getAddrSpace(), SrcPtrInfo.getAddrSpace(),
1467  MF.getFunction().getAttributes(), TLI))
1468  return false;
1469 
1470  if (DstAlignCanChange) {
1471  // Get an estimate of the type from the LLT.
1472  Type *IRTy = getTypeForLLT(MemOps[0], C);
1473  Align NewAlign = DL.getABITypeAlign(IRTy);
1474 
1475  // Don't promote to an alignment that would require dynamic stack
1476  // realignment.
1477  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1478  if (!TRI->hasStackRealignment(MF))
1479  while (NewAlign > Alignment && DL.exceedsNaturalStackAlignment(NewAlign))
1480  NewAlign = NewAlign / 2;
1481 
1482  if (NewAlign > Alignment) {
1483  Alignment = NewAlign;
1484  unsigned FI = FIDef->getOperand(1).getIndex();
1485  // Give the stack frame object a larger alignment if needed.
1486  if (MFI.getObjectAlign(FI) < Alignment)
1487  MFI.setObjectAlignment(FI, Alignment);
1488  }
1489  }
1490 
1491  LLVM_DEBUG(dbgs() << "Inlining memmove: " << MI << " into loads & stores\n");
1492 
1493  MachineIRBuilder MIB(MI);
1494  // Memmove requires that we perform the loads first before issuing the stores.
1495  // Apart from that, this loop is pretty much doing the same thing as the
1496  // memcpy codegen function.
1497  unsigned CurrOffset = 0;
1498  LLT PtrTy = MRI.getType(Src);
1499  SmallVector<Register, 16> LoadVals;
1500  for (auto CopyTy : MemOps) {
1501  // Construct MMO for the load.
1502  auto *LoadMMO =
1503  MF.getMachineMemOperand(&SrcMMO, CurrOffset, CopyTy.getSizeInBytes());
1504 
1505  // Create the load.
1506  Register LoadPtr = Src;
1507  if (CurrOffset != 0) {
1508  auto Offset =
1509  MIB.buildConstant(LLT::scalar(PtrTy.getSizeInBits()), CurrOffset);
1510  LoadPtr = MIB.buildPtrAdd(PtrTy, Src, Offset).getReg(0);
1511  }
1512  LoadVals.push_back(MIB.buildLoad(CopyTy, LoadPtr, *LoadMMO).getReg(0));
1513  CurrOffset += CopyTy.getSizeInBytes();
1514  }
1515 
1516  CurrOffset = 0;
1517  for (unsigned I = 0; I < MemOps.size(); ++I) {
1518  LLT CopyTy = MemOps[I];
1519  // Now store the values loaded.
1520  auto *StoreMMO =
1521  MF.getMachineMemOperand(&DstMMO, CurrOffset, CopyTy.getSizeInBytes());
1522 
1523  Register StorePtr = Dst;
1524  if (CurrOffset != 0) {
1525  auto Offset =
1526  MIB.buildConstant(LLT::scalar(PtrTy.getSizeInBits()), CurrOffset);
1527  StorePtr = MIB.buildPtrAdd(PtrTy, Dst, Offset).getReg(0);
1528  }
1529  MIB.buildStore(LoadVals[I], StorePtr, *StoreMMO);
1530  CurrOffset += CopyTy.getSizeInBytes();
1531  }
1532  MI.eraseFromParent();
1533  return true;
1534 }
1535 
1537  const unsigned Opc = MI.getOpcode();
1538  // This combine is fairly complex so it's not written with a separate
1539  // matcher function.
1540  assert((Opc == TargetOpcode::G_MEMCPY || Opc == TargetOpcode::G_MEMMOVE ||
1541  Opc == TargetOpcode::G_MEMSET) && "Expected memcpy like instruction");
1542 
1543  auto MMOIt = MI.memoperands_begin();
1544  const MachineMemOperand *MemOp = *MMOIt;
1545  bool IsVolatile = MemOp->isVolatile();
1546  // Don't try to optimize volatile.
1547  if (IsVolatile)
1548  return false;
1549 
1550  Align DstAlign = MemOp->getBaseAlign();
1551  Align SrcAlign;
1552  Register Dst = MI.getOperand(0).getReg();
1553  Register Src = MI.getOperand(1).getReg();
1554  Register Len = MI.getOperand(2).getReg();
1555 
1556  if (Opc != TargetOpcode::G_MEMSET) {
1557  assert(MMOIt != MI.memoperands_end() && "Expected a second MMO on MI");
1558  MemOp = *(++MMOIt);
1559  SrcAlign = MemOp->getBaseAlign();
1560  }
1561 
1562  // See if this is a constant length copy
1563  auto LenVRegAndVal = getConstantVRegValWithLookThrough(Len, MRI);
1564  if (!LenVRegAndVal)
1565  return false; // Leave it to the legalizer to lower it to a libcall.
1566  unsigned KnownLen = LenVRegAndVal->Value.getZExtValue();
1567 
1568  if (KnownLen == 0) {
1569  MI.eraseFromParent();
1570  return true;
1571  }
1572 
1573  if (MaxLen && KnownLen > MaxLen)
1574  return false;
1575 
1576  if (Opc == TargetOpcode::G_MEMCPY)
1577  return optimizeMemcpy(MI, Dst, Src, KnownLen, DstAlign, SrcAlign, IsVolatile);
1578  if (Opc == TargetOpcode::G_MEMMOVE)
1579  return optimizeMemmove(MI, Dst, Src, KnownLen, DstAlign, SrcAlign, IsVolatile);
1580  if (Opc == TargetOpcode::G_MEMSET)
1581  return optimizeMemset(MI, Dst, Src, KnownLen, DstAlign, IsVolatile);
1582  return false;
1583 }
1584 
1585 static Optional<APFloat> constantFoldFpUnary(unsigned Opcode, LLT DstTy,
1586  const Register Op,
1587  const MachineRegisterInfo &MRI) {
1588  const ConstantFP *MaybeCst = getConstantFPVRegVal(Op, MRI);
1589  if (!MaybeCst)
1590  return None;
1591 
1592  APFloat V = MaybeCst->getValueAPF();
1593  switch (Opcode) {
1594  default:
1595  llvm_unreachable("Unexpected opcode!");
1596  case TargetOpcode::G_FNEG: {
1597  V.changeSign();
1598  return V;
1599  }
1600  case TargetOpcode::G_FABS: {
1601  V.clearSign();
1602  return V;
1603  }
1604  case TargetOpcode::G_FPTRUNC:
1605  break;
1606  case TargetOpcode::G_FSQRT: {
1607  bool Unused;
1609  V = APFloat(sqrt(V.convertToDouble()));
1610  break;
1611  }
1612  case TargetOpcode::G_FLOG2: {
1613  bool Unused;
1615  V = APFloat(log2(V.convertToDouble()));
1616  break;
1617  }
1618  }
1619  // Convert `APFloat` to appropriate IEEE type depending on `DstTy`. Otherwise,
1620  // `buildFConstant` will assert on size mismatch. Only `G_FPTRUNC`, `G_FSQRT`,
1621  // and `G_FLOG2` reach here.
1622  bool Unused;
1624  return V;
1625 }
1626 
1628  Optional<APFloat> &Cst) {
1629  Register DstReg = MI.getOperand(0).getReg();
1630  Register SrcReg = MI.getOperand(1).getReg();
1631  LLT DstTy = MRI.getType(DstReg);
1632  Cst = constantFoldFpUnary(MI.getOpcode(), DstTy, SrcReg, MRI);
1633  return Cst.hasValue();
1634 }
1635 
1637  Optional<APFloat> &Cst) {
1638  assert(Cst.hasValue() && "Optional is unexpectedly empty!");
1640  MachineFunction &MF = Builder.getMF();
1641  auto *FPVal = ConstantFP::get(MF.getFunction().getContext(), *Cst);
1642  Register DstReg = MI.getOperand(0).getReg();
1643  Builder.buildFConstant(DstReg, *FPVal);
1644  MI.eraseFromParent();
1645  return true;
1646 }
1647 
1649  PtrAddChain &MatchInfo) {
1650  // We're trying to match the following pattern:
1651  // %t1 = G_PTR_ADD %base, G_CONSTANT imm1
1652  // %root = G_PTR_ADD %t1, G_CONSTANT imm2
1653  // -->
1654  // %root = G_PTR_ADD %base, G_CONSTANT (imm1 + imm2)
1655 
1656  if (MI.getOpcode() != TargetOpcode::G_PTR_ADD)
1657  return false;
1658 
1659  Register Add2 = MI.getOperand(1).getReg();
1660  Register Imm1 = MI.getOperand(2).getReg();
1661  auto MaybeImmVal = getConstantVRegValWithLookThrough(Imm1, MRI);
1662  if (!MaybeImmVal)
1663  return false;
1664 
1665  MachineInstr *Add2Def = MRI.getUniqueVRegDef(Add2);
1666  if (!Add2Def || Add2Def->getOpcode() != TargetOpcode::G_PTR_ADD)
1667  return false;
1668 
1669  Register Base = Add2Def->getOperand(1).getReg();
1670  Register Imm2 = Add2Def->getOperand(2).getReg();
1671  auto MaybeImm2Val = getConstantVRegValWithLookThrough(Imm2, MRI);
1672  if (!MaybeImm2Val)
1673  return false;
1674 
1675  // Pass the combined immediate to the apply function.
1676  MatchInfo.Imm = (MaybeImmVal->Value + MaybeImm2Val->Value).getSExtValue();
1677  MatchInfo.Base = Base;
1678  return true;
1679 }
1680 
1682  PtrAddChain &MatchInfo) {
1683  assert(MI.getOpcode() == TargetOpcode::G_PTR_ADD && "Expected G_PTR_ADD");
1684  MachineIRBuilder MIB(MI);
1685  LLT OffsetTy = MRI.getType(MI.getOperand(2).getReg());
1686  auto NewOffset = MIB.buildConstant(OffsetTy, MatchInfo.Imm);
1688  MI.getOperand(1).setReg(MatchInfo.Base);
1689  MI.getOperand(2).setReg(NewOffset.getReg(0));
1691  return true;
1692 }
1693 
1695  RegisterImmPair &MatchInfo) {
1696  // We're trying to match the following pattern with any of
1697  // G_SHL/G_ASHR/G_LSHR/G_SSHLSAT/G_USHLSAT shift instructions:
1698  // %t1 = SHIFT %base, G_CONSTANT imm1
1699  // %root = SHIFT %t1, G_CONSTANT imm2
1700  // -->
1701  // %root = SHIFT %base, G_CONSTANT (imm1 + imm2)
1702 
1703  unsigned Opcode = MI.getOpcode();
1704  assert((Opcode == TargetOpcode::G_SHL || Opcode == TargetOpcode::G_ASHR ||
1705  Opcode == TargetOpcode::G_LSHR || Opcode == TargetOpcode::G_SSHLSAT ||
1706  Opcode == TargetOpcode::G_USHLSAT) &&
1707  "Expected G_SHL, G_ASHR, G_LSHR, G_SSHLSAT or G_USHLSAT");
1708 
1709  Register Shl2 = MI.getOperand(1).getReg();
1710  Register Imm1 = MI.getOperand(2).getReg();
1711  auto MaybeImmVal = getConstantVRegValWithLookThrough(Imm1, MRI);
1712  if (!MaybeImmVal)
1713  return false;
1714 
1715  MachineInstr *Shl2Def = MRI.getUniqueVRegDef(Shl2);
1716  if (Shl2Def->getOpcode() != Opcode)
1717  return false;
1718 
1719  Register Base = Shl2Def->getOperand(1).getReg();
1720  Register Imm2 = Shl2Def->getOperand(2).getReg();
1721  auto MaybeImm2Val = getConstantVRegValWithLookThrough(Imm2, MRI);
1722  if (!MaybeImm2Val)
1723  return false;
1724 
1725  // Pass the combined immediate to the apply function.
1726  MatchInfo.Imm =
1727  (MaybeImmVal->Value.getSExtValue() + MaybeImm2Val->Value).getSExtValue();
1728  MatchInfo.Reg = Base;
1729 
1730  // There is no simple replacement for a saturating unsigned left shift that
1731  // exceeds the scalar size.
1732  if (Opcode == TargetOpcode::G_USHLSAT &&
1733  MatchInfo.Imm >= MRI.getType(Shl2).getScalarSizeInBits())
1734  return false;
1735 
1736  return true;
1737 }
1738 
1740  RegisterImmPair &MatchInfo) {
1741  unsigned Opcode = MI.getOpcode();
1742  assert((Opcode == TargetOpcode::G_SHL || Opcode == TargetOpcode::G_ASHR ||
1743  Opcode == TargetOpcode::G_LSHR || Opcode == TargetOpcode::G_SSHLSAT ||
1744  Opcode == TargetOpcode::G_USHLSAT) &&
1745  "Expected G_SHL, G_ASHR, G_LSHR, G_SSHLSAT or G_USHLSAT");
1746 
1748  LLT Ty = MRI.getType(MI.getOperand(1).getReg());
1749  unsigned const ScalarSizeInBits = Ty.getScalarSizeInBits();
1750  auto Imm = MatchInfo.Imm;
1751 
1752  if (Imm >= ScalarSizeInBits) {
1753  // Any logical shift that exceeds scalar size will produce zero.
1754  if (Opcode == TargetOpcode::G_SHL || Opcode == TargetOpcode::G_LSHR) {
1755  Builder.buildConstant(MI.getOperand(0), 0);
1756  MI.eraseFromParent();
1757  return true;
1758  }
1759  // Arithmetic shift and saturating signed left shift have no effect beyond
1760  // scalar size.
1761  Imm = ScalarSizeInBits - 1;
1762  }
1763 
1764  LLT ImmTy = MRI.getType(MI.getOperand(2).getReg());
1765  Register NewImm = Builder.buildConstant(ImmTy, Imm).getReg(0);
1767  MI.getOperand(1).setReg(MatchInfo.Reg);
1768  MI.getOperand(2).setReg(NewImm);
1770  return true;
1771 }
1772 
1774  ShiftOfShiftedLogic &MatchInfo) {
1775  // We're trying to match the following pattern with any of
1776  // G_SHL/G_ASHR/G_LSHR/G_USHLSAT/G_SSHLSAT shift instructions in combination
1777  // with any of G_AND/G_OR/G_XOR logic instructions.
1778  // %t1 = SHIFT %X, G_CONSTANT C0
1779  // %t2 = LOGIC %t1, %Y
1780  // %root = SHIFT %t2, G_CONSTANT C1
1781  // -->
1782  // %t3 = SHIFT %X, G_CONSTANT (C0+C1)
1783  // %t4 = SHIFT %Y, G_CONSTANT C1
1784  // %root = LOGIC %t3, %t4
1785  unsigned ShiftOpcode = MI.getOpcode();
1786  assert((ShiftOpcode == TargetOpcode::G_SHL ||
1787  ShiftOpcode == TargetOpcode::G_ASHR ||
1788  ShiftOpcode == TargetOpcode::G_LSHR ||
1789  ShiftOpcode == TargetOpcode::G_USHLSAT ||
1790  ShiftOpcode == TargetOpcode::G_SSHLSAT) &&
1791  "Expected G_SHL, G_ASHR, G_LSHR, G_USHLSAT and G_SSHLSAT");
1792 
1793  // Match a one-use bitwise logic op.
1794  Register LogicDest = MI.getOperand(1).getReg();
1795  if (!MRI.hasOneNonDBGUse(LogicDest))
1796  return false;
1797 
1798  MachineInstr *LogicMI = MRI.getUniqueVRegDef(LogicDest);
1799  unsigned LogicOpcode = LogicMI->getOpcode();
1800  if (LogicOpcode != TargetOpcode::G_AND && LogicOpcode != TargetOpcode::G_OR &&
1801  LogicOpcode != TargetOpcode::G_XOR)
1802  return false;
1803 
1804  // Find a matching one-use shift by constant.
1805  const Register C1 = MI.getOperand(2).getReg();
1806  auto MaybeImmVal = getConstantVRegValWithLookThrough(C1, MRI);
1807  if (!MaybeImmVal)
1808  return false;
1809 
1810  const uint64_t C1Val = MaybeImmVal->Value.getZExtValue();
1811 
1812  auto matchFirstShift = [&](const MachineInstr *MI, uint64_t &ShiftVal) {
1813  // Shift should match previous one and should be a one-use.
1814  if (MI->getOpcode() != ShiftOpcode ||
1815  !MRI.hasOneNonDBGUse(MI->getOperand(0).getReg()))
1816  return false;
1817 
1818  // Must be a constant.
1819  auto MaybeImmVal =
1820  getConstantVRegValWithLookThrough(MI->getOperand(2).getReg(), MRI);
1821  if (!MaybeImmVal)
1822  return false;
1823 
1824  ShiftVal = MaybeImmVal->Value.getSExtValue();
1825  return true;
1826  };
1827 
1828  // Logic ops are commutative, so check each operand for a match.
1829  Register LogicMIReg1 = LogicMI->getOperand(1).getReg();
1830  MachineInstr *LogicMIOp1 = MRI.getUniqueVRegDef(LogicMIReg1);
1831  Register LogicMIReg2 = LogicMI->getOperand(2).getReg();
1832  MachineInstr *LogicMIOp2 = MRI.getUniqueVRegDef(LogicMIReg2);
1833  uint64_t C0Val;
1834 
1835  if (matchFirstShift(LogicMIOp1, C0Val)) {
1836  MatchInfo.LogicNonShiftReg = LogicMIReg2;
1837  MatchInfo.Shift2 = LogicMIOp1;
1838  } else if (matchFirstShift(LogicMIOp2, C0Val)) {
1839  MatchInfo.LogicNonShiftReg = LogicMIReg1;
1840  MatchInfo.Shift2 = LogicMIOp2;
1841  } else
1842  return false;
1843 
1844  MatchInfo.ValSum = C0Val + C1Val;
1845 
1846  // The fold is not valid if the sum of the shift values exceeds bitwidth.
1847  if (MatchInfo.ValSum >= MRI.getType(LogicDest).getScalarSizeInBits())
1848  return false;
1849 
1850  MatchInfo.Logic = LogicMI;
1851  return true;
1852 }
1853 
1855  ShiftOfShiftedLogic &MatchInfo) {
1856  unsigned Opcode = MI.getOpcode();
1857  assert((Opcode == TargetOpcode::G_SHL || Opcode == TargetOpcode::G_ASHR ||
1858  Opcode == TargetOpcode::G_LSHR || Opcode == TargetOpcode::G_USHLSAT ||
1859  Opcode == TargetOpcode::G_SSHLSAT) &&
1860  "Expected G_SHL, G_ASHR, G_LSHR, G_USHLSAT and G_SSHLSAT");
1861 
1862  LLT ShlType = MRI.getType(MI.getOperand(2).getReg());
1863  LLT DestType = MRI.getType(MI.getOperand(0).getReg());
1865 
1866  Register Const = Builder.buildConstant(ShlType, MatchInfo.ValSum).getReg(0);
1867 
1868  Register Shift1Base = MatchInfo.Shift2->getOperand(1).getReg();
1869  Register Shift1 =
1870  Builder.buildInstr(Opcode, {DestType}, {Shift1Base, Const}).getReg(0);
1871 
1872  Register Shift2Const = MI.getOperand(2).getReg();
1873  Register Shift2 = Builder
1874  .buildInstr(Opcode, {DestType},
1875  {MatchInfo.LogicNonShiftReg, Shift2Const})
1876  .getReg(0);
1877 
1878  Register Dest = MI.getOperand(0).getReg();
1879  Builder.buildInstr(MatchInfo.Logic->getOpcode(), {Dest}, {Shift1, Shift2});
1880 
1881  // These were one use so it's safe to remove them.
1882  MatchInfo.Shift2->eraseFromParent();
1883  MatchInfo.Logic->eraseFromParent();
1884 
1885  MI.eraseFromParent();
1886  return true;
1887 }
1888 
1890  unsigned &ShiftVal) {
1891  assert(MI.getOpcode() == TargetOpcode::G_MUL && "Expected a G_MUL");
1892  auto MaybeImmVal =
1893  getConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI);
1894  if (!MaybeImmVal)
1895  return false;
1896 
1897  ShiftVal = MaybeImmVal->Value.exactLogBase2();
1898  return (static_cast<int32_t>(ShiftVal) != -1);
1899 }
1900 
1902  unsigned &ShiftVal) {
1903  assert(MI.getOpcode() == TargetOpcode::G_MUL && "Expected a G_MUL");
1904  MachineIRBuilder MIB(MI);
1905  LLT ShiftTy = MRI.getType(MI.getOperand(0).getReg());
1906  auto ShiftCst = MIB.buildConstant(ShiftTy, ShiftVal);
1908  MI.setDesc(MIB.getTII().get(TargetOpcode::G_SHL));
1909  MI.getOperand(2).setReg(ShiftCst.getReg(0));
1911  return true;
1912 }
1913 
1914 // shl ([sza]ext x), y => zext (shl x, y), if shift does not overflow source
1916  RegisterImmPair &MatchData) {
1917  assert(MI.getOpcode() == TargetOpcode::G_SHL && KB);
1918 
1919  Register LHS = MI.getOperand(1).getReg();
1920 
1921  Register ExtSrc;
1922  if (!mi_match(LHS, MRI, m_GAnyExt(m_Reg(ExtSrc))) &&
1923  !mi_match(LHS, MRI, m_GZExt(m_Reg(ExtSrc))) &&
1924  !mi_match(LHS, MRI, m_GSExt(m_Reg(ExtSrc))))
1925  return false;
1926 
1927  // TODO: Should handle vector splat.
1928  Register RHS = MI.getOperand(2).getReg();
1929  auto MaybeShiftAmtVal = getConstantVRegValWithLookThrough(RHS, MRI);
1930  if (!MaybeShiftAmtVal)
1931  return false;
1932 
1933  if (LI) {
1934  LLT SrcTy = MRI.getType(ExtSrc);
1935 
1936  // We only really care about the legality with the shifted value. We can
1937  // pick any type the constant shift amount, so ask the target what to
1938  // use. Otherwise we would have to guess and hope it is reported as legal.
1939  LLT ShiftAmtTy = getTargetLowering().getPreferredShiftAmountTy(SrcTy);
1940  if (!isLegalOrBeforeLegalizer({TargetOpcode::G_SHL, {SrcTy, ShiftAmtTy}}))
1941  return false;
1942  }
1943 
1944  int64_t ShiftAmt = MaybeShiftAmtVal->Value.getSExtValue();
1945  MatchData.Reg = ExtSrc;
1946  MatchData.Imm = ShiftAmt;
1947 
1948  unsigned MinLeadingZeros = KB->getKnownZeroes(ExtSrc).countLeadingOnes();
1949  return MinLeadingZeros >= ShiftAmt;
1950 }
1951 
1953  const RegisterImmPair &MatchData) {
1954  Register ExtSrcReg = MatchData.Reg;
1955  int64_t ShiftAmtVal = MatchData.Imm;
1956 
1957  LLT ExtSrcTy = MRI.getType(ExtSrcReg);
1959  auto ShiftAmt = Builder.buildConstant(ExtSrcTy, ShiftAmtVal);
1960  auto NarrowShift =
1961  Builder.buildShl(ExtSrcTy, ExtSrcReg, ShiftAmt, MI.getFlags());
1962  Builder.buildZExt(MI.getOperand(0), NarrowShift);
1963  MI.eraseFromParent();
1964  return true;
1965 }
1966 
1968  const MachineRegisterInfo &MRI) {
1969  while (mi_match(Reg, MRI, m_GBitcast(m_Reg(Reg))))
1970  ;
1971 
1972  return Reg;
1973 }
1974 
1977  assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES &&
1978  "Expected an unmerge");
1979  Register SrcReg =
1980  peekThroughBitcast(MI.getOperand(MI.getNumOperands() - 1).getReg(), MRI);
1981 
1982  MachineInstr *SrcInstr = MRI.getVRegDef(SrcReg);
1983  if (SrcInstr->getOpcode() != TargetOpcode::G_MERGE_VALUES &&
1984  SrcInstr->getOpcode() != TargetOpcode::G_BUILD_VECTOR &&
1985  SrcInstr->getOpcode() != TargetOpcode::G_CONCAT_VECTORS)
1986  return false;
1987 
1988  // Check the source type of the merge.
1989  LLT SrcMergeTy = MRI.getType(SrcInstr->getOperand(1).getReg());
1990  LLT Dst0Ty = MRI.getType(MI.getOperand(0).getReg());
1991  bool SameSize = Dst0Ty.getSizeInBits() == SrcMergeTy.getSizeInBits();
1992  if (SrcMergeTy != Dst0Ty && !SameSize)
1993  return false;
1994  // They are the same now (modulo a bitcast).
1995  // We can collect all the src registers.
1996  for (unsigned Idx = 1, EndIdx = SrcInstr->getNumOperands(); Idx != EndIdx;
1997  ++Idx)
1998  Operands.push_back(SrcInstr->getOperand(Idx).getReg());
1999  return true;
2000 }
2001 
2004  assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES &&
2005  "Expected an unmerge");
2006  assert((MI.getNumOperands() - 1 == Operands.size()) &&
2007  "Not enough operands to replace all defs");
2008  unsigned NumElems = MI.getNumOperands() - 1;
2009 
2010  LLT SrcTy = MRI.getType(Operands[0]);
2011  LLT DstTy = MRI.getType(MI.getOperand(0).getReg());
2012  bool CanReuseInputDirectly = DstTy == SrcTy;
2014  for (unsigned Idx = 0; Idx < NumElems; ++Idx) {
2015  Register DstReg = MI.getOperand(Idx).getReg();
2016  Register SrcReg = Operands[Idx];
2017  if (CanReuseInputDirectly)
2018  replaceRegWith(MRI, DstReg, SrcReg);
2019  else
2020  Builder.buildCast(DstReg, SrcReg);
2021  }
2022  MI.eraseFromParent();
2023  return true;
2024 }
2025 
2027  SmallVectorImpl<APInt> &Csts) {
2028  unsigned SrcIdx = MI.getNumOperands() - 1;
2029  Register SrcReg = MI.getOperand(SrcIdx).getReg();
2030  MachineInstr *SrcInstr = MRI.getVRegDef(SrcReg);
2031  if (SrcInstr->getOpcode() != TargetOpcode::G_CONSTANT &&
2032  SrcInstr->getOpcode() != TargetOpcode::G_FCONSTANT)
2033  return false;
2034  // Break down the big constant in smaller ones.
2035  const MachineOperand &CstVal = SrcInstr->getOperand(1);
2036  APInt Val = SrcInstr->getOpcode() == TargetOpcode::G_CONSTANT
2037  ? CstVal.getCImm()->getValue()
2038  : CstVal.getFPImm()->getValueAPF().bitcastToAPInt();
2039 
2040  LLT Dst0Ty = MRI.getType(MI.getOperand(0).getReg());
2041  unsigned ShiftAmt = Dst0Ty.getSizeInBits();
2042  // Unmerge a constant.
2043  for (unsigned Idx = 0; Idx != SrcIdx; ++Idx) {
2044  Csts.emplace_back(Val.trunc(ShiftAmt));
2045  Val = Val.lshr(ShiftAmt);
2046  }
2047 
2048  return true;
2049 }
2050 
2052  SmallVectorImpl<APInt> &Csts) {
2053  assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES &&
2054  "Expected an unmerge");
2055  assert((MI.getNumOperands() - 1 == Csts.size()) &&
2056  "Not enough operands to replace all defs");
2057  unsigned NumElems = MI.getNumOperands() - 1;
2059  for (unsigned Idx = 0; Idx < NumElems; ++Idx) {
2060  Register DstReg = MI.getOperand(Idx).getReg();
2061  Builder.buildConstant(DstReg, Csts[Idx]);
2062  }
2063 
2064  MI.eraseFromParent();
2065  return true;
2066 }
2067 
2069  assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES &&
2070  "Expected an unmerge");
2071  // Check that all the lanes are dead except the first one.
2072  for (unsigned Idx = 1, EndIdx = MI.getNumDefs(); Idx != EndIdx; ++Idx) {
2073  if (!MRI.use_nodbg_empty(MI.getOperand(Idx).getReg()))
2074  return false;
2075  }
2076  return true;
2077 }
2078 
2081  Register SrcReg = MI.getOperand(MI.getNumDefs()).getReg();
2082  // Truncating a vector is going to truncate every single lane,
2083  // whereas we want the full lowbits.
2084  // Do the operation on a scalar instead.
2085  LLT SrcTy = MRI.getType(SrcReg);
2086  if (SrcTy.isVector())
2087  SrcReg =
2088  Builder.buildCast(LLT::scalar(SrcTy.getSizeInBits()), SrcReg).getReg(0);
2089 
2090  Register Dst0Reg = MI.getOperand(0).getReg();
2091  LLT Dst0Ty = MRI.getType(Dst0Reg);
2092  if (Dst0Ty.isVector()) {
2093  auto MIB = Builder.buildTrunc(LLT::scalar(Dst0Ty.getSizeInBits()), SrcReg);
2094  Builder.buildCast(Dst0Reg, MIB);
2095  } else
2096  Builder.buildTrunc(Dst0Reg, SrcReg);
2097  MI.eraseFromParent();
2098  return true;
2099 }
2100 
2102  assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES &&
2103  "Expected an unmerge");
2104  Register Dst0Reg = MI.getOperand(0).getReg();
2105  LLT Dst0Ty = MRI.getType(Dst0Reg);
2106  // G_ZEXT on vector applies to each lane, so it will
2107  // affect all destinations. Therefore we won't be able
2108  // to simplify the unmerge to just the first definition.
2109  if (Dst0Ty.isVector())
2110  return false;
2111  Register SrcReg = MI.getOperand(MI.getNumDefs()).getReg();
2112  LLT SrcTy = MRI.getType(SrcReg);
2113  if (SrcTy.isVector())
2114  return false;
2115 
2116  Register ZExtSrcReg;
2117  if (!mi_match(SrcReg, MRI, m_GZExt(m_Reg(ZExtSrcReg))))
2118  return false;
2119 
2120  // Finally we can replace the first definition with
2121  // a zext of the source if the definition is big enough to hold
2122  // all of ZExtSrc bits.
2123  LLT ZExtSrcTy = MRI.getType(ZExtSrcReg);
2124  return ZExtSrcTy.getSizeInBits() <= Dst0Ty.getSizeInBits();
2125 }
2126 
2128  assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES &&
2129  "Expected an unmerge");
2130 
2131  Register Dst0Reg = MI.getOperand(0).getReg();
2132 
2133  MachineInstr *ZExtInstr =
2134  MRI.getVRegDef(MI.getOperand(MI.getNumDefs()).getReg());
2135  assert(ZExtInstr && ZExtInstr->getOpcode() == TargetOpcode::G_ZEXT &&
2136  "Expecting a G_ZEXT");
2137 
2138  Register ZExtSrcReg = ZExtInstr->getOperand(1).getReg();
2139  LLT Dst0Ty = MRI.getType(Dst0Reg);
2140  LLT ZExtSrcTy = MRI.getType(ZExtSrcReg);
2141 
2143 
2144  if (Dst0Ty.getSizeInBits() > ZExtSrcTy.getSizeInBits()) {
2145  Builder.buildZExt(Dst0Reg, ZExtSrcReg);
2146  } else {
2147  assert(Dst0Ty.getSizeInBits() == ZExtSrcTy.getSizeInBits() &&
2148  "ZExt src doesn't fit in destination");
2149  replaceRegWith(MRI, Dst0Reg, ZExtSrcReg);
2150  }
2151 
2152  Register ZeroReg;
2153  for (unsigned Idx = 1, EndIdx = MI.getNumDefs(); Idx != EndIdx; ++Idx) {
2154  if (!ZeroReg)
2155  ZeroReg = Builder.buildConstant(Dst0Ty, 0).getReg(0);
2156  replaceRegWith(MRI, MI.getOperand(Idx).getReg(), ZeroReg);
2157  }
2158  MI.eraseFromParent();
2159  return true;
2160 }
2161 
2163  unsigned TargetShiftSize,
2164  unsigned &ShiftVal) {
2165  assert((MI.getOpcode() == TargetOpcode::G_SHL ||
2166  MI.getOpcode() == TargetOpcode::G_LSHR ||
2167  MI.getOpcode() == TargetOpcode::G_ASHR) && "Expected a shift");
2168 
2169  LLT Ty = MRI.getType(MI.getOperand(0).getReg());
2170  if (Ty.isVector()) // TODO:
2171  return false;
2172 
2173  // Don't narrow further than the requested size.
2174  unsigned Size = Ty.getSizeInBits();
2175  if (Size <= TargetShiftSize)
2176  return false;
2177 
2178  auto MaybeImmVal =
2179  getConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI);
2180  if (!MaybeImmVal)
2181  return false;
2182 
2183  ShiftVal = MaybeImmVal->Value.getSExtValue();
2184  return ShiftVal >= Size / 2 && ShiftVal < Size;
2185 }
2186 
2188  const unsigned &ShiftVal) {
2189  Register DstReg = MI.getOperand(0).getReg();
2190  Register SrcReg = MI.getOperand(1).getReg();
2191  LLT Ty = MRI.getType(SrcReg);
2192  unsigned Size = Ty.getSizeInBits();
2193  unsigned HalfSize = Size / 2;
2194  assert(ShiftVal >= HalfSize);
2195 
2196  LLT HalfTy = LLT::scalar(HalfSize);
2197 
2198  Builder.setInstr(MI);
2199  auto Unmerge = Builder.buildUnmerge(HalfTy, SrcReg);
2200  unsigned NarrowShiftAmt = ShiftVal - HalfSize;
2201 
2202  if (MI.getOpcode() == TargetOpcode::G_LSHR) {
2203  Register Narrowed = Unmerge.getReg(1);
2204 
2205  // dst = G_LSHR s64:x, C for C >= 32
2206  // =>
2207  // lo, hi = G_UNMERGE_VALUES x
2208  // dst = G_MERGE_VALUES (G_LSHR hi, C - 32), 0
2209 
2210  if (NarrowShiftAmt != 0) {
2211  Narrowed = Builder.buildLShr(HalfTy, Narrowed,
2212  Builder.buildConstant(HalfTy, NarrowShiftAmt)).getReg(0);
2213  }
2214 
2215  auto Zero = Builder.buildConstant(HalfTy, 0);
2216  Builder.buildMerge(DstReg, { Narrowed, Zero });
2217  } else if (MI.getOpcode() == TargetOpcode::G_SHL) {
2218  Register Narrowed = Unmerge.getReg(0);
2219  // dst = G_SHL s64:x, C for C >= 32
2220  // =>
2221  // lo, hi = G_UNMERGE_VALUES x
2222  // dst = G_MERGE_VALUES 0, (G_SHL hi, C - 32)
2223  if (NarrowShiftAmt != 0) {
2224  Narrowed = Builder.buildShl(HalfTy, Narrowed,
2225  Builder.buildConstant(HalfTy, NarrowShiftAmt)).getReg(0);
2226  }
2227 
2228  auto Zero = Builder.buildConstant(HalfTy, 0);
2229  Builder.buildMerge(DstReg, { Zero, Narrowed });
2230  } else {
2231  assert(MI.getOpcode() == TargetOpcode::G_ASHR);
2232  auto Hi = Builder.buildAShr(
2233  HalfTy, Unmerge.getReg(1),
2234  Builder.buildConstant(HalfTy, HalfSize - 1));
2235 
2236  if (ShiftVal == HalfSize) {
2237  // (G_ASHR i64:x, 32) ->
2238  // G_MERGE_VALUES hi_32(x), (G_ASHR hi_32(x), 31)
2239  Builder.buildMerge(DstReg, { Unmerge.getReg(1), Hi });
2240  } else if (ShiftVal == Size - 1) {
2241  // Don't need a second shift.
2242  // (G_ASHR i64:x, 63) ->
2243  // %narrowed = (G_ASHR hi_32(x), 31)
2244  // G_MERGE_VALUES %narrowed, %narrowed
2245  Builder.buildMerge(DstReg, { Hi, Hi });
2246  } else {
2247  auto Lo = Builder.buildAShr(
2248  HalfTy, Unmerge.getReg(1),
2249  Builder.buildConstant(HalfTy, ShiftVal - HalfSize));
2250 
2251  // (G_ASHR i64:x, C) ->, for C >= 32
2252  // G_MERGE_VALUES (G_ASHR hi_32(x), C - 32), (G_ASHR hi_32(x), 31)
2253  Builder.buildMerge(DstReg, { Lo, Hi });
2254  }
2255  }
2256 
2257  MI.eraseFromParent();
2258  return true;
2259 }
2260 
2262  unsigned TargetShiftAmount) {
2263  unsigned ShiftAmt;
2264  if (matchCombineShiftToUnmerge(MI, TargetShiftAmount, ShiftAmt)) {
2265  applyCombineShiftToUnmerge(MI, ShiftAmt);
2266  return true;
2267  }
2268 
2269  return false;
2270 }
2271 
2273  assert(MI.getOpcode() == TargetOpcode::G_INTTOPTR && "Expected a G_INTTOPTR");
2274  Register DstReg = MI.getOperand(0).getReg();
2275  LLT DstTy = MRI.getType(DstReg);
2276  Register SrcReg = MI.getOperand(1).getReg();
2277  return mi_match(SrcReg, MRI,
2279 }
2280 
2282  assert(MI.getOpcode() == TargetOpcode::G_INTTOPTR && "Expected a G_INTTOPTR");
2283  Register DstReg = MI.getOperand(0).getReg();
2284  Builder.setInstr(MI);
2285  Builder.buildCopy(DstReg, Reg);
2286  MI.eraseFromParent();
2287  return true;
2288 }
2289 
2291  assert(MI.getOpcode() == TargetOpcode::G_PTRTOINT && "Expected a G_PTRTOINT");
2292  Register SrcReg = MI.getOperand(1).getReg();
2293  return mi_match(SrcReg, MRI, m_GIntToPtr(m_Reg(Reg)));
2294 }
2295 
2297  assert(MI.getOpcode() == TargetOpcode::G_PTRTOINT && "Expected a G_PTRTOINT");
2298  Register DstReg = MI.getOperand(0).getReg();
2299  Builder.setInstr(MI);
2300  Builder.buildZExtOrTrunc(DstReg, Reg);
2301  MI.eraseFromParent();
2302  return true;
2303 }
2304 
2306  MachineInstr &MI, std::pair<Register, bool> &PtrReg) {
2307  assert(MI.getOpcode() == TargetOpcode::G_ADD);
2308  Register LHS = MI.getOperand(1).getReg();
2309  Register RHS = MI.getOperand(2).getReg();
2310  LLT IntTy = MRI.getType(LHS);
2311 
2312  // G_PTR_ADD always has the pointer in the LHS, so we may need to commute the
2313  // instruction.
2314  PtrReg.second = false;
2315  for (Register SrcReg : {LHS, RHS}) {
2316  if (mi_match(SrcReg, MRI, m_GPtrToInt(m_Reg(PtrReg.first)))) {
2317  // Don't handle cases where the integer is implicitly converted to the
2318  // pointer width.
2319  LLT PtrTy = MRI.getType(PtrReg.first);
2320  if (PtrTy.getScalarSizeInBits() == IntTy.getScalarSizeInBits())
2321  return true;
2322  }
2323 
2324  PtrReg.second = true;
2325  }
2326 
2327  return false;
2328 }
2329 
2331  MachineInstr &MI, std::pair<Register, bool> &PtrReg) {
2332  Register Dst = MI.getOperand(0).getReg();
2333  Register LHS = MI.getOperand(1).getReg();
2334  Register RHS = MI.getOperand(2).getReg();
2335 
2336  const bool DoCommute = PtrReg.second;
2337  if (DoCommute)
2338  std::swap(LHS, RHS);
2339  LHS = PtrReg.first;
2340 
2341  LLT PtrTy = MRI.getType(LHS);
2342 
2344  auto PtrAdd = Builder.buildPtrAdd(PtrTy, LHS, RHS);
2345  Builder.buildPtrToInt(Dst, PtrAdd);
2346  MI.eraseFromParent();
2347  return true;
2348 }
2349 
2351  int64_t &NewCst) {
2352  assert(MI.getOpcode() == TargetOpcode::G_PTR_ADD && "Expected a G_PTR_ADD");
2353  Register LHS = MI.getOperand(1).getReg();
2354  Register RHS = MI.getOperand(2).getReg();
2356 
2357  if (auto RHSCst = getConstantVRegSExtVal(RHS, MRI)) {
2358  int64_t Cst;
2359  if (mi_match(LHS, MRI, m_GIntToPtr(m_ICst(Cst)))) {
2360  NewCst = Cst + *RHSCst;
2361  return true;
2362  }
2363  }
2364 
2365  return false;
2366 }
2367 
2369  int64_t &NewCst) {
2370  assert(MI.getOpcode() == TargetOpcode::G_PTR_ADD && "Expected a G_PTR_ADD");
2371  Register Dst = MI.getOperand(0).getReg();
2372 
2374  Builder.buildConstant(Dst, NewCst);
2375  MI.eraseFromParent();
2376  return true;
2377 }
2378 
2380  assert(MI.getOpcode() == TargetOpcode::G_ANYEXT && "Expected a G_ANYEXT");
2381  Register DstReg = MI.getOperand(0).getReg();
2382  Register SrcReg = MI.getOperand(1).getReg();
2383  LLT DstTy = MRI.getType(DstReg);
2384  return mi_match(SrcReg, MRI,
2386 }
2387 
2389  assert(MI.getOpcode() == TargetOpcode::G_ZEXT && "Expected a G_ZEXT");
2390  Register DstReg = MI.getOperand(0).getReg();
2391  Register SrcReg = MI.getOperand(1).getReg();
2392  LLT DstTy = MRI.getType(DstReg);
2393  if (mi_match(SrcReg, MRI,
2394  m_GTrunc(m_all_of(m_Reg(Reg), m_SpecificType(DstTy))))) {
2395  unsigned DstSize = DstTy.getScalarSizeInBits();
2396  unsigned SrcSize = MRI.getType(SrcReg).getScalarSizeInBits();
2397  return KB->getKnownBits(Reg).countMinLeadingZeros() >= DstSize - SrcSize;
2398  }
2399  return false;
2400 }
2401 
2403  MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) {
2404  assert((MI.getOpcode() == TargetOpcode::G_ANYEXT ||
2405  MI.getOpcode() == TargetOpcode::G_SEXT ||
2406  MI.getOpcode() == TargetOpcode::G_ZEXT) &&
2407  "Expected a G_[ASZ]EXT");
2408  Register SrcReg = MI.getOperand(1).getReg();
2409  MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
2410  // Match exts with the same opcode, anyext([sz]ext) and sext(zext).
2411  unsigned Opc = MI.getOpcode();
2412  unsigned SrcOpc = SrcMI->getOpcode();
2413  if (Opc == SrcOpc ||
2414  (Opc == TargetOpcode::G_ANYEXT &&
2415  (SrcOpc == TargetOpcode::G_SEXT || SrcOpc == TargetOpcode::G_ZEXT)) ||
2416  (Opc == TargetOpcode::G_SEXT && SrcOpc == TargetOpcode::G_ZEXT)) {
2417  MatchInfo = std::make_tuple(SrcMI->getOperand(1).getReg(), SrcOpc);
2418  return true;
2419  }
2420  return false;
2421 }
2422 
2424  MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) {
2425  assert((MI.getOpcode() == TargetOpcode::G_ANYEXT ||
2426  MI.getOpcode() == TargetOpcode::G_SEXT ||
2427  MI.getOpcode() == TargetOpcode::G_ZEXT) &&
2428  "Expected a G_[ASZ]EXT");
2429 
2430  Register Reg = std::get<0>(MatchInfo);
2431  unsigned SrcExtOp = std::get<1>(MatchInfo);
2432 
2433  // Combine exts with the same opcode.
2434  if (MI.getOpcode() == SrcExtOp) {
2436  MI.getOperand(1).setReg(Reg);
2438  return true;
2439  }
2440 
2441  // Combine:
2442  // - anyext([sz]ext x) to [sz]ext x
2443  // - sext(zext x) to zext x
2444  if (MI.getOpcode() == TargetOpcode::G_ANYEXT ||
2445  (MI.getOpcode() == TargetOpcode::G_SEXT &&
2446  SrcExtOp == TargetOpcode::G_ZEXT)) {
2447  Register DstReg = MI.getOperand(0).getReg();
2449  Builder.buildInstr(SrcExtOp, {DstReg}, {Reg});
2450  MI.eraseFromParent();
2451  return true;
2452  }
2453 
2454  return false;
2455 }
2456 
2458  assert(MI.getOpcode() == TargetOpcode::G_MUL && "Expected a G_MUL");
2459  Register DstReg = MI.getOperand(0).getReg();
2460  Register SrcReg = MI.getOperand(1).getReg();
2461  LLT DstTy = MRI.getType(DstReg);
2462 
2464  Builder.buildSub(DstReg, Builder.buildConstant(DstTy, 0), SrcReg,
2465  MI.getFlags());
2466  MI.eraseFromParent();
2467  return true;
2468 }
2469 
2471  assert(MI.getOpcode() == TargetOpcode::G_FNEG && "Expected a G_FNEG");
2472  Register SrcReg = MI.getOperand(1).getReg();
2473  return mi_match(SrcReg, MRI, m_GFNeg(m_Reg(Reg)));
2474 }
2475 
2477  assert(MI.getOpcode() == TargetOpcode::G_FABS && "Expected a G_FABS");
2478  Src = MI.getOperand(1).getReg();
2479  Register AbsSrc;
2480  return mi_match(Src, MRI, m_GFabs(m_Reg(AbsSrc)));
2481 }
2482 
2484  MachineInstr &MI, std::pair<Register, unsigned> &MatchInfo) {
2485  assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC");
2486  Register SrcReg = MI.getOperand(1).getReg();
2487  MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
2488  unsigned SrcOpc = SrcMI->getOpcode();
2489  if (SrcOpc == TargetOpcode::G_ANYEXT || SrcOpc == TargetOpcode::G_SEXT ||
2490  SrcOpc == TargetOpcode::G_ZEXT) {
2491  MatchInfo = std::make_pair(SrcMI->getOperand(1).getReg(), SrcOpc);
2492  return true;
2493  }
2494  return false;
2495 }
2496 
2498  MachineInstr &MI, std::pair<Register, unsigned> &MatchInfo) {
2499  assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC");
2500  Register SrcReg = MatchInfo.first;
2501  unsigned SrcExtOp = MatchInfo.second;
2502  Register DstReg = MI.getOperand(0).getReg();
2503  LLT SrcTy = MRI.getType(SrcReg);
2504  LLT DstTy = MRI.getType(DstReg);
2505  if (SrcTy == DstTy) {
2506  MI.eraseFromParent();
2507  replaceRegWith(MRI, DstReg, SrcReg);
2508  return true;
2509  }
2511  if (SrcTy.getSizeInBits() < DstTy.getSizeInBits())
2512  Builder.buildInstr(SrcExtOp, {DstReg}, {SrcReg});
2513  else
2514  Builder.buildTrunc(DstReg, SrcReg);
2515  MI.eraseFromParent();
2516  return true;
2517 }
2518 
2520  MachineInstr &MI, std::pair<Register, Register> &MatchInfo) {
2521  assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC");
2522  Register DstReg = MI.getOperand(0).getReg();
2523  Register SrcReg = MI.getOperand(1).getReg();
2524  LLT DstTy = MRI.getType(DstReg);
2525  Register ShiftSrc;
2526  Register ShiftAmt;
2527 
2528  if (MRI.hasOneNonDBGUse(SrcReg) &&
2529  mi_match(SrcReg, MRI, m_GShl(m_Reg(ShiftSrc), m_Reg(ShiftAmt))) &&
2531  {TargetOpcode::G_SHL,
2532  {DstTy, getTargetLowering().getPreferredShiftAmountTy(DstTy)}})) {
2533  KnownBits Known = KB->getKnownBits(ShiftAmt);
2534  unsigned Size = DstTy.getSizeInBits();
2535  if (Known.getBitWidth() - Known.countMinLeadingZeros() <= Log2_32(Size)) {
2536  MatchInfo = std::make_pair(ShiftSrc, ShiftAmt);
2537  return true;
2538  }
2539  }
2540  return false;
2541 }
2542 
2544  MachineInstr &MI, std::pair<Register, Register> &MatchInfo) {
2545  assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC");
2546  Register DstReg = MI.getOperand(0).getReg();
2547  Register SrcReg = MI.getOperand(1).getReg();
2548  LLT DstTy = MRI.getType(DstReg);
2549  MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
2550 
2551  Register ShiftSrc = MatchInfo.first;
2552  Register ShiftAmt = MatchInfo.second;
2554  auto TruncShiftSrc = Builder.buildTrunc(DstTy, ShiftSrc);
2555  Builder.buildShl(DstReg, TruncShiftSrc, ShiftAmt, SrcMI->getFlags());
2556  MI.eraseFromParent();
2557  return true;
2558 }
2559 
2561  return any_of(MI.explicit_uses(), [this](const MachineOperand &MO) {
2562  return MO.isReg() &&
2563  getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MO.getReg(), MRI);
2564  });
2565 }
2566 
2568  return all_of(MI.explicit_uses(), [this](const MachineOperand &MO) {
2569  return !MO.isReg() ||
2570  getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MO.getReg(), MRI);
2571  });
2572 }
2573 
2575  assert(MI.getOpcode() == TargetOpcode::G_SHUFFLE_VECTOR);
2576  ArrayRef<int> Mask = MI.getOperand(3).getShuffleMask();
2577  return all_of(Mask, [](int Elt) { return Elt < 0; });
2578 }
2579 
2581  assert(MI.getOpcode() == TargetOpcode::G_STORE);
2582  return getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MI.getOperand(0).getReg(),
2583  MRI);
2584 }
2585 
2587  assert(MI.getOpcode() == TargetOpcode::G_SELECT);
2588  return getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MI.getOperand(1).getReg(),
2589  MRI);
2590 }
2591 
2593  assert(MI.getOpcode() == TargetOpcode::G_SELECT);
2594  if (auto MaybeCstCmp =
2595  getConstantVRegValWithLookThrough(MI.getOperand(1).getReg(), MRI)) {
2596  OpIdx = MaybeCstCmp->Value.isNullValue() ? 3 : 2;
2597  return true;
2598  }
2599  return false;
2600 }
2601 
2603  MI.eraseFromParent();
2604  return true;
2605 }
2606 
2608  const MachineOperand &MOP2) {
2609  if (!MOP1.isReg() || !MOP2.isReg())
2610  return false;
2612  if (!I1)
2613  return false;
2615  if (!I2)
2616  return false;
2617 
2618  // Handle a case like this:
2619  //
2620  // %0:_(s64), %1:_(s64) = G_UNMERGE_VALUES %2:_(<2 x s64>)
2621  //
2622  // Even though %0 and %1 are produced by the same instruction they are not
2623  // the same values.
2624  if (I1 == I2)
2625  return MOP1.getReg() == MOP2.getReg();
2626 
2627  // If we have an instruction which loads or stores, we can't guarantee that
2628  // it is identical.
2629  //
2630  // For example, we may have
2631  //
2632  // %x1 = G_LOAD %addr (load N from @somewhere)
2633  // ...
2634  // call @foo
2635  // ...
2636  // %x2 = G_LOAD %addr (load N from @somewhere)
2637  // ...
2638  // %or = G_OR %x1, %x2
2639  //
2640  // It's possible that @foo will modify whatever lives at the address we're
2641  // loading from. To be safe, let's just assume that all loads and stores
2642  // are different (unless we have something which is guaranteed to not
2643  // change.)
2644  if (I1->mayLoadOrStore() && !I1->isDereferenceableInvariantLoad(nullptr))
2645  return false;
2646 
2647  // Check for physical registers on the instructions first to avoid cases
2648  // like this:
2649  //
2650  // %a = COPY $physreg
2651  // ...
2652  // SOMETHING implicit-def $physreg
2653  // ...
2654  // %b = COPY $physreg
2655  //
2656  // These copies are not equivalent.
2657  if (any_of(I1->uses(), [](const MachineOperand &MO) {
2658  return MO.isReg() && MO.getReg().isPhysical();
2659  })) {
2660  // Check if we have a case like this:
2661  //
2662  // %a = COPY $physreg
2663  // %b = COPY %a
2664  //
2665  // In this case, I1 and I2 will both be equal to %a = COPY $physreg.
2666  // From that, we know that they must have the same value, since they must
2667  // have come from the same COPY.
2668  return I1->isIdenticalTo(*I2);
2669  }
2670 
2671  // We don't have any physical registers, so we don't necessarily need the
2672  // same vreg defs.
2673  //
2674  // On the off-chance that there's some target instruction feeding into the
2675  // instruction, let's use produceSameValue instead of isIdenticalTo.
2676  return Builder.getTII().produceSameValue(*I1, *I2, &MRI);
2677 }
2678 
2680  if (!MOP.isReg())
2681  return false;
2682  // MIPatternMatch doesn't let us look through G_ZEXT etc.
2683  auto ValAndVReg = getConstantVRegValWithLookThrough(MOP.getReg(), MRI);
2684  return ValAndVReg && ValAndVReg->Value == C;
2685 }
2686 
2688  unsigned OpIdx) {
2689  assert(MI.getNumExplicitDefs() == 1 && "Expected one explicit def?");
2690  Register OldReg = MI.getOperand(0).getReg();
2691  Register Replacement = MI.getOperand(OpIdx).getReg();
2692  assert(canReplaceReg(OldReg, Replacement, MRI) && "Cannot replace register?");
2693  MI.eraseFromParent();
2694  replaceRegWith(MRI, OldReg, Replacement);
2695  return true;
2696 }
2697 
2699  Register Replacement) {
2700  assert(MI.getNumExplicitDefs() == 1 && "Expected one explicit def?");
2701  Register OldReg = MI.getOperand(0).getReg();
2702  assert(canReplaceReg(OldReg, Replacement, MRI) && "Cannot replace register?");
2703  MI.eraseFromParent();
2704  replaceRegWith(MRI, OldReg, Replacement);
2705  return true;
2706 }
2707 
2709  assert(MI.getOpcode() == TargetOpcode::G_SELECT);
2710  // Match (cond ? x : x)
2711  return matchEqualDefs(MI.getOperand(2), MI.getOperand(3)) &&
2712  canReplaceReg(MI.getOperand(0).getReg(), MI.getOperand(2).getReg(),
2713  MRI);
2714 }
2715 
2717  return matchEqualDefs(MI.getOperand(1), MI.getOperand(2)) &&
2718  canReplaceReg(MI.getOperand(0).getReg(), MI.getOperand(1).getReg(),
2719  MRI);
2720 }
2721 
2723  return matchConstantOp(MI.getOperand(OpIdx), 0) &&
2724  canReplaceReg(MI.getOperand(0).getReg(), MI.getOperand(OpIdx).getReg(),
2725  MRI);
2726 }
2727 
2729  MachineOperand &MO = MI.getOperand(OpIdx);
2730  return MO.isReg() &&
2731  getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MO.getReg(), MRI);
2732 }
2733 
2735  unsigned OpIdx) {
2736  MachineOperand &MO = MI.getOperand(OpIdx);
2737  return isKnownToBeAPowerOfTwo(MO.getReg(), MRI, KB);
2738 }
2739 
2741  assert(MI.getNumDefs() == 1 && "Expected only one def?");
2742  Builder.setInstr(MI);
2743  Builder.buildFConstant(MI.getOperand(0), C);
2744  MI.eraseFromParent();
2745  return true;
2746 }
2747 
2749  assert(MI.getNumDefs() == 1 && "Expected only one def?");
2750  Builder.setInstr(MI);
2751  Builder.buildConstant(MI.getOperand(0), C);
2752  MI.eraseFromParent();
2753  return true;
2754 }
2755 
2757  assert(MI.getNumDefs() == 1 && "Expected only one def?");
2758  Builder.setInstr(MI);
2759  Builder.buildUndef(MI.getOperand(0));
2760  MI.eraseFromParent();
2761  return true;
2762 }
2763 
2765  MachineInstr &MI, std::tuple<Register, Register> &MatchInfo) {
2766  Register LHS = MI.getOperand(1).getReg();
2767  Register RHS = MI.getOperand(2).getReg();
2768  Register &NewLHS = std::get<0>(MatchInfo);
2769  Register &NewRHS = std::get<1>(MatchInfo);
2770 
2771  // Helper lambda to check for opportunities for
2772  // ((0-A) + B) -> B - A
2773  // (A + (0-B)) -> A - B
2774  auto CheckFold = [&](Register &MaybeSub, Register &MaybeNewLHS) {
2775  if (!mi_match(MaybeSub, MRI, m_Neg(m_Reg(NewRHS))))
2776  return false;
2777  NewLHS = MaybeNewLHS;
2778  return true;
2779  };
2780 
2781  return CheckFold(LHS, RHS) || CheckFold(RHS, LHS);
2782 }
2783 
2785  MachineInstr &MI, SmallVectorImpl<Register> &MatchInfo) {
2786  assert(MI.getOpcode() == TargetOpcode::G_INSERT_VECTOR_ELT &&
2787  "Invalid opcode");
2788  Register DstReg = MI.getOperand(0).getReg();
2789  LLT DstTy = MRI.getType(DstReg);
2790  assert(DstTy.isVector() && "Invalid G_INSERT_VECTOR_ELT?");
2791  unsigned NumElts = DstTy.getNumElements();
2792  // If this MI is part of a sequence of insert_vec_elts, then
2793  // don't do the combine in the middle of the sequence.
2794  if (MRI.hasOneUse(DstReg) && MRI.use_instr_begin(DstReg)->getOpcode() ==
2795  TargetOpcode::G_INSERT_VECTOR_ELT)
2796  return false;
2797  MachineInstr *CurrInst = &MI;
2798  MachineInstr *TmpInst;
2799  int64_t IntImm;
2800  Register TmpReg;
2801  MatchInfo.resize(NumElts);
2802  while (mi_match(
2803  CurrInst->getOperand(0).getReg(), MRI,
2804  m_GInsertVecElt(m_MInstr(TmpInst), m_Reg(TmpReg), m_ICst(IntImm)))) {
2805  if (IntImm >= NumElts)
2806  return false;
2807  if (!MatchInfo[IntImm])
2808  MatchInfo[IntImm] = TmpReg;
2809  CurrInst = TmpInst;
2810  }
2811  // Variable index.
2812  if (CurrInst->getOpcode() == TargetOpcode::G_INSERT_VECTOR_ELT)
2813  return false;
2814  if (TmpInst->getOpcode() == TargetOpcode::G_BUILD_VECTOR) {
2815  for (unsigned I = 1; I < TmpInst->getNumOperands(); ++I) {
2816  if (!MatchInfo[I - 1].isValid())
2817  MatchInfo[I - 1] = TmpInst->getOperand(I).getReg();
2818  }
2819  return true;
2820  }
2821  // If we didn't end in a G_IMPLICIT_DEF, bail out.
2822  return TmpInst->getOpcode() == TargetOpcode::G_IMPLICIT_DEF;
2823 }
2824 
2826  MachineInstr &MI, SmallVectorImpl<Register> &MatchInfo) {
2827  Builder.setInstr(MI);
2828  Register UndefReg;
2829  auto GetUndef = [&]() {
2830  if (UndefReg)
2831  return UndefReg;
2832  LLT DstTy = MRI.getType(MI.getOperand(0).getReg());
2833  UndefReg = Builder.buildUndef(DstTy.getScalarType()).getReg(0);
2834  return UndefReg;
2835  };
2836  for (unsigned I = 0; I < MatchInfo.size(); ++I) {
2837  if (!MatchInfo[I])
2838  MatchInfo[I] = GetUndef();
2839  }
2840  Builder.buildBuildVector(MI.getOperand(0).getReg(), MatchInfo);
2841  MI.eraseFromParent();
2842  return true;
2843 }
2844 
2846  MachineInstr &MI, std::tuple<Register, Register> &MatchInfo) {
2847  Builder.setInstr(MI);
2848  Register SubLHS, SubRHS;
2849  std::tie(SubLHS, SubRHS) = MatchInfo;
2850  Builder.buildSub(MI.getOperand(0).getReg(), SubLHS, SubRHS);
2851  MI.eraseFromParent();
2852  return true;
2853 }
2854 
2856  MachineInstr &MI, InstructionStepsMatchInfo &MatchInfo) {
2857  // Matches: logic (hand x, ...), (hand y, ...) -> hand (logic x, y), ...
2858  //
2859  // Creates the new hand + logic instruction (but does not insert them.)
2860  //
2861  // On success, MatchInfo is populated with the new instructions. These are
2862  // inserted in applyHoistLogicOpWithSameOpcodeHands.
2863  unsigned LogicOpcode = MI.getOpcode();
2864  assert(LogicOpcode == TargetOpcode::G_AND ||
2865  LogicOpcode == TargetOpcode::G_OR ||
2866  LogicOpcode == TargetOpcode::G_XOR);
2867  MachineIRBuilder MIB(MI);
2868  Register Dst = MI.getOperand(0).getReg();
2869  Register LHSReg = MI.getOperand(1).getReg();
2870  Register RHSReg = MI.getOperand(2).getReg();
2871 
2872  // Don't recompute anything.
2873  if (!MRI.hasOneNonDBGUse(LHSReg) || !MRI.hasOneNonDBGUse(RHSReg))
2874  return false;
2875 
2876  // Make sure we have (hand x, ...), (hand y, ...)
2877  MachineInstr *LeftHandInst = getDefIgnoringCopies(LHSReg, MRI);
2878  MachineInstr *RightHandInst = getDefIgnoringCopies(RHSReg, MRI);
2879  if (!LeftHandInst || !RightHandInst)
2880  return false;
2881  unsigned HandOpcode = LeftHandInst->getOpcode();
2882  if (HandOpcode != RightHandInst->getOpcode())
2883  return false;
2884  if (!LeftHandInst->getOperand(1).isReg() ||
2885  !RightHandInst->getOperand(1).isReg())
2886  return false;
2887 
2888  // Make sure the types match up, and if we're doing this post-legalization,
2889  // we end up with legal types.
2890  Register X = LeftHandInst->getOperand(1).getReg();
2891  Register Y = RightHandInst->getOperand(1).getReg();
2892  LLT XTy = MRI.getType(X);
2893  LLT YTy = MRI.getType(Y);
2894  if (XTy != YTy)
2895  return false;
2896  if (!isLegalOrBeforeLegalizer({LogicOpcode, {XTy, YTy}}))
2897  return false;
2898 
2899  // Optional extra source register.
2900  Register ExtraHandOpSrcReg;
2901  switch (HandOpcode) {
2902  default:
2903  return false;
2904  case TargetOpcode::G_ANYEXT:
2905  case TargetOpcode::G_SEXT:
2906  case TargetOpcode::G_ZEXT: {
2907  // Match: logic (ext X), (ext Y) --> ext (logic X, Y)
2908  break;
2909  }
2910  case TargetOpcode::G_AND:
2911  case TargetOpcode::G_ASHR:
2912  case TargetOpcode::G_LSHR:
2913  case TargetOpcode::G_SHL: {
2914  // Match: logic (binop x, z), (binop y, z) -> binop (logic x, y), z
2915  MachineOperand &ZOp = LeftHandInst->getOperand(2);
2916  if (!matchEqualDefs(ZOp, RightHandInst->getOperand(2)))
2917  return false;
2918  ExtraHandOpSrcReg = ZOp.getReg();
2919  break;
2920  }
2921  }
2922 
2923  // Record the steps to build the new instructions.
2924  //
2925  // Steps to build (logic x, y)
2926  auto NewLogicDst = MRI.createGenericVirtualRegister(XTy);
2927  OperandBuildSteps LogicBuildSteps = {
2928  [=](MachineInstrBuilder &MIB) { MIB.addDef(NewLogicDst); },
2929  [=](MachineInstrBuilder &MIB) { MIB.addReg(X); },
2930  [=](MachineInstrBuilder &MIB) { MIB.addReg(Y); }};
2931  InstructionBuildSteps LogicSteps(LogicOpcode, LogicBuildSteps);
2932 
2933  // Steps to build hand (logic x, y), ...z
2934  OperandBuildSteps HandBuildSteps = {
2935  [=](MachineInstrBuilder &MIB) { MIB.addDef(Dst); },
2936  [=](MachineInstrBuilder &MIB) { MIB.addReg(NewLogicDst); }};
2937  if (ExtraHandOpSrcReg.isValid())
2938  HandBuildSteps.push_back(
2939  [=](MachineInstrBuilder &MIB) { MIB.addReg(ExtraHandOpSrcReg); });
2940  InstructionBuildSteps HandSteps(HandOpcode, HandBuildSteps);
2941 
2942  MatchInfo = InstructionStepsMatchInfo({LogicSteps, HandSteps});
2943  return true;
2944 }
2945 
2947  MachineInstr &MI, InstructionStepsMatchInfo &MatchInfo) {
2948  assert(MatchInfo.InstrsToBuild.size() &&
2949  "Expected at least one instr to build?");
2950  Builder.setInstr(MI);
2951  for (auto &InstrToBuild : MatchInfo.InstrsToBuild) {
2952  assert(InstrToBuild.Opcode && "Expected a valid opcode?");
2953  assert(InstrToBuild.OperandFns.size() && "Expected at least one operand?");
2954  MachineInstrBuilder Instr = Builder.buildInstr(InstrToBuild.Opcode);
2955  for (auto &OperandFn : InstrToBuild.OperandFns)
2956  OperandFn(Instr);
2957  }
2958  MI.eraseFromParent();
2959  return true;
2960 }
2961 
2963  MachineInstr &MI, std::tuple<Register, int64_t> &MatchInfo) {
2964  assert(MI.getOpcode() == TargetOpcode::G_ASHR);
2965  int64_t ShlCst, AshrCst;
2966  Register Src;
2967  // FIXME: detect splat constant vectors.
2968  if (!mi_match(MI.getOperand(0).getReg(), MRI,
2969  m_GAShr(m_GShl(m_Reg(Src), m_ICst(ShlCst)), m_ICst(AshrCst))))
2970  return false;
2971  if (ShlCst != AshrCst)
2972  return false;
2974  {TargetOpcode::G_SEXT_INREG, {MRI.getType(Src)}}))
2975  return false;
2976  MatchInfo = std::make_tuple(Src, ShlCst);
2977  return true;
2978 }
2980  MachineInstr &MI, std::tuple<Register, int64_t> &MatchInfo) {
2981  assert(MI.getOpcode() == TargetOpcode::G_ASHR);
2982  Register Src;
2983  int64_t ShiftAmt;
2984  std::tie(Src, ShiftAmt) = MatchInfo;
2985  unsigned Size = MRI.getType(Src).getScalarSizeInBits();
2987  Builder.buildSExtInReg(MI.getOperand(0).getReg(), Src, Size - ShiftAmt);
2988  MI.eraseFromParent();
2989  return true;
2990 }
2991 
2993  Register &Replacement) {
2994  // Given
2995  //
2996  // %y:_(sN) = G_SOMETHING
2997  // %x:_(sN) = G_SOMETHING
2998  // %res:_(sN) = G_AND %x, %y
2999  //
3000  // Eliminate the G_AND when it is known that x & y == x or x & y == y.
3001  //
3002  // Patterns like this can appear as a result of legalization. E.g.
3003  //
3004  // %cmp:_(s32) = G_ICMP intpred(pred), %x(s32), %y
3005  // %one:_(s32) = G_CONSTANT i32 1
3006  // %and:_(s32) = G_AND %cmp, %one
3007  //
3008  // In this case, G_ICMP only produces a single bit, so x & 1 == x.
3009  assert(MI.getOpcode() == TargetOpcode::G_AND);
3010  if (!KB)
3011  return false;
3012 
3013  Register AndDst = MI.getOperand(0).getReg();
3014  LLT DstTy = MRI.getType(AndDst);
3015 
3016  // FIXME: This should be removed once GISelKnownBits supports vectors.
3017  if (DstTy.isVector())
3018  return false;
3019 
3020  Register LHS = MI.getOperand(1).getReg();
3021  Register RHS = MI.getOperand(2).getReg();
3022  KnownBits LHSBits = KB->getKnownBits(LHS);
3023  KnownBits RHSBits = KB->getKnownBits(RHS);
3024 
3025  // Check that x & Mask == x.
3026  // x & 1 == x, always
3027  // x & 0 == x, only if x is also 0
3028  // Meaning Mask has no effect if every bit is either one in Mask or zero in x.
3029  //
3030  // Check if we can replace AndDst with the LHS of the G_AND
3031  if (canReplaceReg(AndDst, LHS, MRI) &&
3032  (LHSBits.Zero | RHSBits.One).isAllOnesValue()) {
3033  Replacement = LHS;
3034  return true;
3035  }
3036 
3037  // Check if we can replace AndDst with the RHS of the G_AND
3038  if (canReplaceReg(AndDst, RHS, MRI) &&
3039  (LHSBits.One | RHSBits.Zero).isAllOnesValue()) {
3040  Replacement = RHS;
3041  return true;
3042  }
3043 
3044  return false;
3045 }
3046 
3048  // Given
3049  //
3050  // %y:_(sN) = G_SOMETHING
3051  // %x:_(sN) = G_SOMETHING
3052  // %res:_(sN) = G_OR %x, %y
3053  //
3054  // Eliminate the G_OR when it is known that x | y == x or x | y == y.
3055  assert(MI.getOpcode() == TargetOpcode::G_OR);
3056  if (!KB)
3057  return false;
3058 
3059  Register OrDst = MI.getOperand(0).getReg();
3060  LLT DstTy = MRI.getType(OrDst);
3061 
3062  // FIXME: This should be removed once GISelKnownBits supports vectors.
3063  if (DstTy.isVector())
3064  return false;
3065 
3066  Register LHS = MI.getOperand(1).getReg();
3067  Register RHS = MI.getOperand(2).getReg();
3068  KnownBits LHSBits = KB->getKnownBits(LHS);
3069  KnownBits RHSBits = KB->getKnownBits(RHS);
3070 
3071  // Check that x | Mask == x.
3072  // x | 0 == x, always
3073  // x | 1 == x, only if x is also 1
3074  // Meaning Mask has no effect if every bit is either zero in Mask or one in x.
3075  //
3076  // Check if we can replace OrDst with the LHS of the G_OR
3077  if (canReplaceReg(OrDst, LHS, MRI) &&
3078  (LHSBits.One | RHSBits.Zero).isAllOnesValue()) {
3079  Replacement = LHS;
3080  return true;
3081  }
3082 
3083  // Check if we can replace OrDst with the RHS of the G_OR
3084  if (canReplaceReg(OrDst, RHS, MRI) &&
3085  (LHSBits.Zero | RHSBits.One).isAllOnesValue()) {
3086  Replacement = RHS;
3087  return true;
3088  }
3089 
3090  return false;
3091 }
3092 
3094  // If the input is already sign extended, just drop the extension.
3095  Register Src = MI.getOperand(1).getReg();
3096  unsigned ExtBits = MI.getOperand(2).getImm();
3097  unsigned TypeSize = MRI.getType(Src).getScalarSizeInBits();
3098  return KB->computeNumSignBits(Src) >= (TypeSize - ExtBits + 1);
3099 }
3100 
3101 static bool isConstValidTrue(const TargetLowering &TLI, unsigned ScalarSizeBits,
3102  int64_t Cst, bool IsVector, bool IsFP) {
3103  // For i1, Cst will always be -1 regardless of boolean contents.
3104  return (ScalarSizeBits == 1 && Cst == -1) ||
3105  isConstTrueVal(TLI, Cst, IsVector, IsFP);
3106 }
3107 
3109  SmallVectorImpl<Register> &RegsToNegate) {
3110  assert(MI.getOpcode() == TargetOpcode::G_XOR);
3111  LLT Ty = MRI.getType(MI.getOperand(0).getReg());
3112  const auto &TLI = *Builder.getMF().getSubtarget().getTargetLowering();
3113  Register XorSrc;
3114  Register CstReg;
3115  // We match xor(src, true) here.
3116  if (!mi_match(MI.getOperand(0).getReg(), MRI,
3117  m_GXor(m_Reg(XorSrc), m_Reg(CstReg))))
3118  return false;
3119 
3120  if (!MRI.hasOneNonDBGUse(XorSrc))
3121  return false;
3122 
3123  // Check that XorSrc is the root of a tree of comparisons combined with ANDs
3124  // and ORs. The suffix of RegsToNegate starting from index I is used a work
3125  // list of tree nodes to visit.
3126  RegsToNegate.push_back(XorSrc);
3127  // Remember whether the comparisons are all integer or all floating point.
3128  bool IsInt = false;
3129  bool IsFP = false;
3130  for (unsigned I = 0; I < RegsToNegate.size(); ++I) {
3131  Register Reg = RegsToNegate[I];
3132  if (!MRI.hasOneNonDBGUse(Reg))
3133  return false;
3135  switch (Def->getOpcode()) {
3136  default:
3137  // Don't match if the tree contains anything other than ANDs, ORs and
3138  // comparisons.
3139  return false;
3140  case TargetOpcode::G_ICMP:
3141  if (IsFP)
3142  return false;
3143  IsInt = true;
3144  // When we apply the combine we will invert the predicate.
3145  break;
3146  case TargetOpcode::G_FCMP:
3147  if (IsInt)
3148  return false;
3149  IsFP = true;
3150  // When we apply the combine we will invert the predicate.
3151  break;
3152  case TargetOpcode::G_AND:
3153  case TargetOpcode::G_OR:
3154  // Implement De Morgan's laws:
3155  // ~(x & y) -> ~x | ~y
3156  // ~(x | y) -> ~x & ~y
3157  // When we apply the combine we will change the opcode and recursively
3158  // negate the operands.
3159  RegsToNegate.push_back(Def->getOperand(1).getReg());
3160  RegsToNegate.push_back(Def->getOperand(2).getReg());
3161  break;
3162  }
3163  }
3164 
3165  // Now we know whether the comparisons are integer or floating point, check
3166  // the constant in the xor.
3167  int64_t Cst;
3168  if (Ty.isVector()) {
3169  MachineInstr *CstDef = MRI.getVRegDef(CstReg);
3170  auto MaybeCst = getBuildVectorConstantSplat(*CstDef, MRI);
3171  if (!MaybeCst)
3172  return false;
3173  if (!isConstValidTrue(TLI, Ty.getScalarSizeInBits(), *MaybeCst, true, IsFP))
3174  return false;
3175  } else {
3176  if (!mi_match(CstReg, MRI, m_ICst(Cst)))
3177  return false;
3178  if (!isConstValidTrue(TLI, Ty.getSizeInBits(), Cst, false, IsFP))
3179  return false;
3180  }
3181 
3182  return true;
3183 }
3184 
3186  SmallVectorImpl<Register> &RegsToNegate) {
3187  for (Register Reg : RegsToNegate) {
3190  // For each comparison, invert the opcode. For each AND and OR, change the
3191  // opcode.
3192  switch (Def->getOpcode()) {
3193  default:
3194  llvm_unreachable("Unexpected opcode");
3195  case TargetOpcode::G_ICMP:
3196  case TargetOpcode::G_FCMP: {
3197  MachineOperand &PredOp = Def->getOperand(1);
3199  (CmpInst::Predicate)PredOp.getPredicate());
3200  PredOp.setPredicate(NewP);
3201  break;
3202  }
3203  case TargetOpcode::G_AND:
3204  Def->setDesc(Builder.getTII().get(TargetOpcode::G_OR));
3205  break;
3206  case TargetOpcode::G_OR:
3207  Def->setDesc(Builder.getTII().get(TargetOpcode::G_AND));
3208  break;
3209  }
3211  }
3212 
3213  replaceRegWith(MRI, MI.getOperand(0).getReg(), MI.getOperand(1).getReg());
3214  MI.eraseFromParent();
3215  return true;
3216 }
3217 
3219  MachineInstr &MI, std::pair<Register, Register> &MatchInfo) {
3220  // Match (xor (and x, y), y) (or any of its commuted cases)
3221  assert(MI.getOpcode() == TargetOpcode::G_XOR);
3222  Register &X = MatchInfo.first;
3223  Register &Y = MatchInfo.second;
3224  Register AndReg = MI.getOperand(1).getReg();
3225  Register SharedReg = MI.getOperand(2).getReg();
3226 
3227  // Find a G_AND on either side of the G_XOR.
3228  // Look for one of
3229  //
3230  // (xor (and x, y), SharedReg)
3231  // (xor SharedReg, (and x, y))
3232  if (!mi_match(AndReg, MRI, m_GAnd(m_Reg(X), m_Reg(Y)))) {
3233  std::swap(AndReg, SharedReg);
3234  if (!mi_match(AndReg, MRI, m_GAnd(m_Reg(X), m_Reg(Y))))
3235  return false;
3236  }
3237 
3238  // Only do this if we'll eliminate the G_AND.
3239  if (!MRI.hasOneNonDBGUse(AndReg))
3240  return false;
3241 
3242  // We can combine if SharedReg is the same as either the LHS or RHS of the
3243  // G_AND.
3244  if (Y != SharedReg)
3245  std::swap(X, Y);
3246  return Y == SharedReg;
3247 }
3248 
3250  MachineInstr &MI, std::pair<Register, Register> &MatchInfo) {
3251  // Fold (xor (and x, y), y) -> (and (not x), y)
3253  Register X, Y;
3254  std::tie(X, Y) = MatchInfo;
3255  auto Not = Builder.buildNot(MRI.getType(X), X);
3257  MI.setDesc(Builder.getTII().get(TargetOpcode::G_AND));
3258  MI.getOperand(1).setReg(Not->getOperand(0).getReg());
3259  MI.getOperand(2).setReg(Y);
3261  return true;
3262 }
3263 
3265  Register DstReg = MI.getOperand(0).getReg();
3266  LLT Ty = MRI.getType(DstReg);
3267  const DataLayout &DL = Builder.getMF().getDataLayout();
3268 
3269  if (DL.isNonIntegralAddressSpace(Ty.getScalarType().getAddressSpace()))
3270  return false;
3271 
3272  if (Ty.isPointer()) {
3273  auto ConstVal = getConstantVRegVal(MI.getOperand(1).getReg(), MRI);
3274  return ConstVal && *ConstVal == 0;
3275  }
3276 
3277  assert(Ty.isVector() && "Expecting a vector type");
3278  const MachineInstr *VecMI = MRI.getVRegDef(MI.getOperand(1).getReg());
3279  return isBuildVectorAllZeros(*VecMI, MRI);
3280 }
3281 
3283  assert(MI.getOpcode() == TargetOpcode::G_PTR_ADD);
3285  Builder.buildIntToPtr(MI.getOperand(0), MI.getOperand(2));
3286  MI.eraseFromParent();
3287  return true;
3288 }
3289 
3290 /// The second source operand is known to be a power of 2.
3292  Register DstReg = MI.getOperand(0).getReg();
3293  Register Src0 = MI.getOperand(1).getReg();
3294  Register Pow2Src1 = MI.getOperand(2).getReg();
3295  LLT Ty = MRI.getType(DstReg);
3297 
3298  // Fold (urem x, pow2) -> (and x, pow2-1)
3299  auto NegOne = Builder.buildConstant(Ty, -1);
3300  auto Add = Builder.buildAdd(Ty, Pow2Src1, NegOne);
3301  Builder.buildAnd(DstReg, Src0, Add);
3302  MI.eraseFromParent();
3303  return true;
3304 }
3305 
3307 CombinerHelper::findCandidatesForLoadOrCombine(const MachineInstr *Root) const {
3308  assert(Root->getOpcode() == TargetOpcode::G_OR && "Expected G_OR only!");
3309  // We want to detect if Root is part of a tree which represents a bunch
3310  // of loads being merged into a larger load. We'll try to recognize patterns
3311  // like, for example:
3312  //
3313  // Reg Reg
3314  // \ /
3315  // OR_1 Reg
3316  // \ /
3317  // OR_2
3318  // \ Reg
3319  // .. /
3320  // Root
3321  //
3322  // Reg Reg Reg Reg
3323  // \ / \ /
3324  // OR_1 OR_2
3325  // \ /
3326  // \ /
3327  // ...
3328  // Root
3329  //
3330  // Each "Reg" may have been produced by a load + some arithmetic. This
3331  // function will save each of them.
3332  SmallVector<Register, 8> RegsToVisit;
3334 
3335  // In the "worst" case, we're dealing with a load for each byte. So, there
3336  // are at most #bytes - 1 ORs.
3337  const unsigned MaxIter =
3338  MRI.getType(Root->getOperand(0).getReg()).getSizeInBytes() - 1;
3339  for (unsigned Iter = 0; Iter < MaxIter; ++Iter) {
3340  if (Ors.empty())
3341  break;
3342  const MachineInstr *Curr = Ors.pop_back_val();
3343  Register OrLHS = Curr->getOperand(1).getReg();
3344  Register OrRHS = Curr->getOperand(2).getReg();
3345 
3346  // In the combine, we want to elimate the entire tree.
3347  if (!MRI.hasOneNonDBGUse(OrLHS) || !MRI.hasOneNonDBGUse(OrRHS))
3348  return None;
3349 
3350  // If it's a G_OR, save it and continue to walk. If it's not, then it's
3351  // something that may be a load + arithmetic.
3352  if (const MachineInstr *Or = getOpcodeDef(TargetOpcode::G_OR, OrLHS, MRI))
3353  Ors.push_back(Or);
3354  else
3355  RegsToVisit.push_back(OrLHS);
3356  if (const MachineInstr *Or = getOpcodeDef(TargetOpcode::G_OR, OrRHS, MRI))
3357  Ors.push_back(Or);
3358  else
3359  RegsToVisit.push_back(OrRHS);
3360  }
3361 
3362  // We're going to try and merge each register into a wider power-of-2 type,
3363  // so we ought to have an even number of registers.
3364  if (RegsToVisit.empty() || RegsToVisit.size() % 2 != 0)
3365  return None;
3366  return RegsToVisit;
3367 }
3368 
3369 /// Helper function for findLoadOffsetsForLoadOrCombine.
3370 ///
3371 /// Check if \p Reg is the result of loading a \p MemSizeInBits wide value,
3372 /// and then moving that value into a specific byte offset.
3373 ///
3374 /// e.g. x[i] << 24
3375 ///
3376 /// \returns The load instruction and the byte offset it is moved into.
3378 matchLoadAndBytePosition(Register Reg, unsigned MemSizeInBits,
3379  const MachineRegisterInfo &MRI) {
3381  "Expected Reg to only have one non-debug use?");
3382  Register MaybeLoad;
3383  int64_t Shift;
3384  if (!mi_match(Reg, MRI,
3385  m_OneNonDBGUse(m_GShl(m_Reg(MaybeLoad), m_ICst(Shift))))) {
3386  Shift = 0;
3387  MaybeLoad = Reg;
3388  }
3389 
3390  if (Shift % MemSizeInBits != 0)
3391  return None;
3392 
3393  // TODO: Handle other types of loads.
3394  auto *Load = getOpcodeDef(TargetOpcode::G_ZEXTLOAD, MaybeLoad, MRI);
3395  if (!Load)
3396  return None;
3397 
3398  const auto &MMO = **Load->memoperands_begin();
3399  if (!MMO.isUnordered() || MMO.getSizeInBits() != MemSizeInBits)
3400  return None;
3401 
3402  return std::make_pair(Load, Shift / MemSizeInBits);
3403 }
3404 
3406 CombinerHelper::findLoadOffsetsForLoadOrCombine(
3407  SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx,
3408  const SmallVector<Register, 8> &RegsToVisit, const unsigned MemSizeInBits) {
3409 
3410  // Each load found for the pattern. There should be one for each RegsToVisit.
3412 
3413  // The lowest index used in any load. (The lowest "i" for each x[i].)
3414  int64_t LowestIdx = INT64_MAX;
3415 
3416  // The load which uses the lowest index.
3417  MachineInstr *LowestIdxLoad = nullptr;
3418 
3419  // Keeps track of the load indices we see. We shouldn't see any indices twice.
3420  SmallSet<int64_t, 8> SeenIdx;
3421 
3422  // Ensure each load is in the same MBB.
3423  // TODO: Support multiple MachineBasicBlocks.
3424  MachineBasicBlock *MBB = nullptr;
3425  const MachineMemOperand *MMO = nullptr;
3426 
3427  // Earliest instruction-order load in the pattern.
3428  MachineInstr *EarliestLoad = nullptr;
3429 
3430  // Latest instruction-order load in the pattern.
3431  MachineInstr *LatestLoad = nullptr;
3432 
3433  // Base pointer which every load should share.
3434  Register BasePtr;
3435 
3436  // We want to find a load for each register. Each load should have some
3437  // appropriate bit twiddling arithmetic. During this loop, we will also keep
3438  // track of the load which uses the lowest index. Later, we will check if we
3439  // can use its pointer in the final, combined load.
3440  for (auto Reg : RegsToVisit) {
3441  // Find the load, and find the position that it will end up in (e.g. a
3442  // shifted) value.
3443  auto LoadAndPos = matchLoadAndBytePosition(Reg, MemSizeInBits, MRI);
3444  if (!LoadAndPos)
3445  return None;
3446  MachineInstr *Load;
3447  int64_t DstPos;
3448  std::tie(Load, DstPos) = *LoadAndPos;
3449 
3450  // TODO: Handle multiple MachineBasicBlocks. Currently not handled because
3451  // it is difficult to check for stores/calls/etc between loads.
3452  MachineBasicBlock *LoadMBB = Load->getParent();
3453  if (!MBB)
3454  MBB = LoadMBB;
3455  if (LoadMBB != MBB)
3456  return None;
3457 
3458  // Make sure that the MachineMemOperands of every seen load are compatible.
3459  const MachineMemOperand *LoadMMO = *Load->memoperands_begin();
3460  if (!MMO)
3461  MMO = LoadMMO;
3462  if (MMO->getAddrSpace() != LoadMMO->getAddrSpace())
3463  return None;
3464 
3465  // Find out what the base pointer and index for the load is.
3466  Register LoadPtr;
3467  int64_t Idx;
3468  if (!mi_match(Load->getOperand(1).getReg(), MRI,
3469  m_GPtrAdd(m_Reg(LoadPtr), m_ICst(Idx)))) {
3470  LoadPtr = Load->getOperand(1).getReg();
3471  Idx = 0;
3472  }
3473 
3474  // Don't combine things like a[i], a[i] -> a bigger load.
3475  if (!SeenIdx.insert(Idx).second)
3476  return None;
3477 
3478  // Every load must share the same base pointer; don't combine things like:
3479  //
3480  // a[i], b[i + 1] -> a bigger load.
3481  if (!BasePtr.isValid())
3482  BasePtr = LoadPtr;
3483  if (BasePtr != LoadPtr)
3484  return None;
3485 
3486  if (Idx < LowestIdx) {
3487  LowestIdx = Idx;
3488  LowestIdxLoad = Load;
3489  }
3490 
3491  // Keep track of the byte offset that this load ends up at. If we have seen
3492  // the byte offset, then stop here. We do not want to combine:
3493  //
3494  // a[i] << 16, a[i + k] << 16 -> a bigger load.
3495  if (!MemOffset2Idx.try_emplace(DstPos, Idx).second)
3496  return None;
3497  Loads.insert(Load);
3498 
3499  // Keep track of the position of the earliest/latest loads in the pattern.
3500  // We will check that there are no load fold barriers between them later
3501  // on.
3502  //
3503  // FIXME: Is there a better way to check for load fold barriers?
3504  if (!EarliestLoad || dominates(*Load, *EarliestLoad))
3505  EarliestLoad = Load;
3506  if (!LatestLoad || dominates(*LatestLoad, *Load))
3507  LatestLoad = Load;
3508  }
3509 
3510  // We found a load for each register. Let's check if each load satisfies the
3511  // pattern.
3512  assert(Loads.size() == RegsToVisit.size() &&
3513  "Expected to find a load for each register?");
3514  assert(EarliestLoad != LatestLoad && EarliestLoad &&
3515  LatestLoad && "Expected at least two loads?");
3516 
3517  // Check if there are any stores, calls, etc. between any of the loads. If
3518  // there are, then we can't safely perform the combine.
3519  //
3520  // MaxIter is chosen based off the (worst case) number of iterations it
3521  // typically takes to succeed in the LLVM test suite plus some padding.
3522  //
3523  // FIXME: Is there a better way to check for load fold barriers?
3524  const unsigned MaxIter = 20;
3525  unsigned Iter = 0;
3526  for (const auto &MI : instructionsWithoutDebug(EarliestLoad->getIterator(),
3527  LatestLoad->getIterator())) {
3528  if (Loads.count(&MI))
3529  continue;
3530  if (MI.isLoadFoldBarrier())
3531  return None;
3532  if (Iter++ == MaxIter)
3533  return None;
3534  }
3535 
3536  return std::make_pair(LowestIdxLoad, LowestIdx);
3537 }
3538 
3540  MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
3541  assert(MI.getOpcode() == TargetOpcode::G_OR);
3542  MachineFunction &MF = *MI.getMF();
3543  // Assuming a little-endian target, transform:
3544  // s8 *a = ...
3545  // s32 val = a[0] | (a[1] << 8) | (a[2] << 16) | (a[3] << 24)
3546  // =>
3547  // s32 val = *((i32)a)
3548  //
3549  // s8 *a = ...
3550  // s32 val = (a[0] << 24) | (a[1] << 16) | (a[2] << 8) | a[3]
3551  // =>
3552  // s32 val = BSWAP(*((s32)a))
3553  Register Dst = MI.getOperand(0).getReg();
3554  LLT Ty = MRI.getType(Dst);
3555  if (Ty.isVector())
3556  return false;
3557 
3558  // We need to combine at least two loads into this type. Since the smallest
3559  // possible load is into a byte, we need at least a 16-bit wide type.
3560  const unsigned WideMemSizeInBits = Ty.getSizeInBits();
3561  if (WideMemSizeInBits < 16 || WideMemSizeInBits % 8 != 0)
3562  return false;
3563 
3564  // Match a collection of non-OR instructions in the pattern.
3565  auto RegsToVisit = findCandidatesForLoadOrCombine(&MI);
3566  if (!RegsToVisit)
3567  return false;
3568 
3569  // We have a collection of non-OR instructions. Figure out how wide each of
3570  // the small loads should be based off of the number of potential loads we
3571  // found.
3572  const unsigned NarrowMemSizeInBits = WideMemSizeInBits / RegsToVisit->size();
3573  if (NarrowMemSizeInBits % 8 != 0)
3574  return false;
3575 
3576  // Check if each register feeding into each OR is a load from the same
3577  // base pointer + some arithmetic.
3578  //
3579  // e.g. a[0], a[1] << 8, a[2] << 16, etc.
3580  //
3581  // Also verify that each of these ends up putting a[i] into the same memory
3582  // offset as a load into a wide type would.
3583  SmallDenseMap<int64_t, int64_t, 8> MemOffset2Idx;
3584  MachineInstr *LowestIdxLoad;
3585  int64_t LowestIdx;
3586  auto MaybeLoadInfo = findLoadOffsetsForLoadOrCombine(
3587  MemOffset2Idx, *RegsToVisit, NarrowMemSizeInBits);
3588  if (!MaybeLoadInfo)
3589  return false;
3590  std::tie(LowestIdxLoad, LowestIdx) = *MaybeLoadInfo;
3591 
3592  // We have a bunch of loads being OR'd together. Using the addresses + offsets
3593  // we found before, check if this corresponds to a big or little endian byte
3594  // pattern. If it does, then we can represent it using a load + possibly a
3595  // BSWAP.
3596  bool IsBigEndianTarget = MF.getDataLayout().isBigEndian();
3597  Optional<bool> IsBigEndian = isBigEndian(MemOffset2Idx, LowestIdx);
3598  if (!IsBigEndian.hasValue())
3599  return false;
3600  bool NeedsBSwap = IsBigEndianTarget != *IsBigEndian;
3601  if (NeedsBSwap && !isLegalOrBeforeLegalizer({TargetOpcode::G_BSWAP, {Ty}}))
3602  return false;
3603 
3604  // Make sure that the load from the lowest index produces offset 0 in the
3605  // final value.
3606  //
3607  // This ensures that we won't combine something like this:
3608  //
3609  // load x[i] -> byte 2
3610  // load x[i+1] -> byte 0 ---> wide_load x[i]
3611  // load x[i+2] -> byte 1
3612  const unsigned NumLoadsInTy = WideMemSizeInBits / NarrowMemSizeInBits;
3613  const unsigned ZeroByteOffset =
3614  *IsBigEndian
3615  ? bigEndianByteAt(NumLoadsInTy, 0)
3616  : littleEndianByteAt(NumLoadsInTy, 0);
3617  auto ZeroOffsetIdx = MemOffset2Idx.find(ZeroByteOffset);
3618  if (ZeroOffsetIdx == MemOffset2Idx.end() ||
3619  ZeroOffsetIdx->second != LowestIdx)
3620  return false;
3621 
3622  // We wil reuse the pointer from the load which ends up at byte offset 0. It
3623  // may not use index 0.
3624  Register Ptr = LowestIdxLoad->getOperand(1).getReg();
3625  const MachineMemOperand &MMO = **LowestIdxLoad->memoperands_begin();
3626  LegalityQuery::MemDesc MMDesc;
3627  MMDesc.SizeInBits = WideMemSizeInBits;
3628  MMDesc.AlignInBits = MMO.getAlign().value() * 8;
3629  MMDesc.Ordering = MMO.getOrdering();
3631  {TargetOpcode::G_LOAD, {Ty, MRI.getType(Ptr)}, {MMDesc}}))
3632  return false;
3633  auto PtrInfo = MMO.getPointerInfo();
3634  auto *NewMMO = MF.getMachineMemOperand(&MMO, PtrInfo, WideMemSizeInBits / 8);
3635 
3636  // Load must be allowed and fast on the target.
3637  LLVMContext &C = MF.getFunction().getContext();
3638  auto &DL = MF.getDataLayout();
3639  bool Fast = false;
3640  if (!getTargetLowering().allowsMemoryAccess(C, DL, Ty, *NewMMO, &Fast) ||
3641  !Fast)
3642  return false;
3643 
3644  MatchInfo = [=](MachineIRBuilder &MIB) {
3645  Register LoadDst = NeedsBSwap ? MRI.cloneVirtualRegister(Dst) : Dst;
3646  MIB.buildLoad(LoadDst, Ptr, *NewMMO);
3647  if (NeedsBSwap)
3648  MIB.buildBSwap(Dst, LoadDst);
3649  };
3650  return true;
3651 }
3652 
3654  MachineInstr *&ExtMI) {
3655  assert(MI.getOpcode() == TargetOpcode::G_PHI);
3656 
3657  Register DstReg = MI.getOperand(0).getReg();
3658 
3659  // TODO: Extending a vector may be expensive, don't do this until heuristics
3660  // are better.
3661  if (MRI.getType(DstReg).isVector())
3662  return false;
3663 
3664  // Try to match a phi, whose only use is an extend.
3665  if (!MRI.hasOneNonDBGUse(DstReg))
3666  return false;
3667  ExtMI = &*MRI.use_instr_nodbg_begin(DstReg);
3668  switch (ExtMI->getOpcode()) {
3669  case TargetOpcode::G_ANYEXT:
3670  return true; // G_ANYEXT is usually free.
3671  case TargetOpcode::G_ZEXT:
3672  case TargetOpcode::G_SEXT:
3673  break;
3674  default:
3675  return false;
3676  }
3677 
3678  // If the target is likely to fold this extend away, don't propagate.
3679  if (Builder.getTII().isExtendLikelyToBeFolded(*ExtMI, MRI))
3680  return false;
3681 
3682  // We don't want to propagate the extends unless there's a good chance that
3683  // they'll be optimized in some way.
3684  // Collect the unique incoming values.
3686  for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
3687  auto *DefMI = getDefIgnoringCopies(MI.getOperand(Idx).getReg(), MRI);
3688  switch (DefMI->getOpcode()) {
3689  case TargetOpcode::G_LOAD:
3690  case TargetOpcode::G_TRUNC:
3691  case TargetOpcode::G_SEXT:
3692  case TargetOpcode::G_ZEXT:
3693  case TargetOpcode::G_ANYEXT:
3694  case TargetOpcode::G_CONSTANT:
3695  InSrcs.insert(getDefIgnoringCopies(MI.getOperand(Idx).getReg(), MRI));
3696  // Don't try to propagate if there are too many places to create new
3697  // extends, chances are it'll increase code size.
3698  if (InSrcs.size() > 2)
3699  return false;
3700  break;
3701  default:
3702  return false;
3703  }
3704  }
3705  return true;
3706 }
3707 
3709  MachineInstr *&ExtMI) {
3710  assert(MI.getOpcode() == TargetOpcode::G_PHI);
3711  Register DstReg = ExtMI->getOperand(0).getReg();
3712  LLT ExtTy = MRI.getType(DstReg);
3713 
3714  // Propagate the extension into the block of each incoming reg's block.
3715  // Use a SetVector here because PHIs can have duplicate edges, and we want
3716  // deterministic iteration order.
3719  for (unsigned SrcIdx = 1; SrcIdx < MI.getNumOperands(); SrcIdx += 2) {
3720  auto *SrcMI = MRI.getVRegDef(MI.getOperand(SrcIdx).getReg());
3721  if (!SrcMIs.insert(SrcMI))
3722  continue;
3723 
3724  // Build an extend after each src inst.
3725  auto *MBB = SrcMI->getParent();
3726  MachineBasicBlock::iterator InsertPt = ++SrcMI->getIterator();
3727  if (InsertPt != MBB->end() && InsertPt->isPHI())
3728  InsertPt = MBB->getFirstNonPHI();
3729 
3730  Builder.setInsertPt(*SrcMI->getParent(), InsertPt);
3731  Builder.setDebugLoc(MI.getDebugLoc());
3732  auto NewExt = Builder.buildExtOrTrunc(ExtMI->getOpcode(), ExtTy,
3733  SrcMI->getOperand(0).getReg());
3734  OldToNewSrcMap[SrcMI] = NewExt;
3735  }
3736 
3737  // Create a new phi with the extended inputs.
3739  auto NewPhi = Builder.buildInstrNoInsert(TargetOpcode::G_PHI);
3740  NewPhi.addDef(DstReg);
3741  for (unsigned SrcIdx = 1; SrcIdx < MI.getNumOperands(); ++SrcIdx) {
3742  auto &MO = MI.getOperand(SrcIdx);
3743  if (!MO.isReg()) {
3744  NewPhi.addMBB(MO.getMBB());
3745  continue;
3746  }
3747  auto *NewSrc = OldToNewSrcMap[MRI.getVRegDef(MO.getReg())];
3748  NewPhi.addUse(NewSrc->getOperand(0).getReg());
3749  }
3750  Builder.insertInstr(NewPhi);
3751  ExtMI->eraseFromParent();
3752  return true;
3753 }
3754 
3756  Register &Reg) {
3757  assert(MI.getOpcode() == TargetOpcode::G_EXTRACT_VECTOR_ELT);
3758  // If we have a constant index, look for a G_BUILD_VECTOR source
3759  // and find the source register that the index maps to.
3760  Register SrcVec = MI.getOperand(1).getReg();
3761  LLT SrcTy = MRI.getType(SrcVec);
3763  {TargetOpcode::G_BUILD_VECTOR, {SrcTy, SrcTy.getElementType()}}))
3764  return false;
3765 
3766  auto Cst = getConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI);
3767  if (!Cst || Cst->Value.getZExtValue() >= SrcTy.getNumElements())
3768  return false;
3769 
3770  unsigned VecIdx = Cst->Value.getZExtValue();
3771  MachineInstr *BuildVecMI =
3772  getOpcodeDef(TargetOpcode::G_BUILD_VECTOR, SrcVec, MRI);
3773  if (!BuildVecMI) {
3774  BuildVecMI = getOpcodeDef(TargetOpcode::G_BUILD_VECTOR_TRUNC, SrcVec, MRI);
3775  if (!BuildVecMI)
3776  return false;
3777  LLT ScalarTy = MRI.getType(BuildVecMI->getOperand(1).getReg());
3779  {TargetOpcode::G_BUILD_VECTOR_TRUNC, {SrcTy, ScalarTy}}))
3780  return false;
3781  }
3782 
3783  EVT Ty(getMVTForLLT(SrcTy));
3784  if (!MRI.hasOneNonDBGUse(SrcVec) &&
3785  !getTargetLowering().aggressivelyPreferBuildVectorSources(Ty))
3786  return false;
3787 
3788  Reg = BuildVecMI->getOperand(VecIdx + 1).getReg();
3789  return true;
3790 }
3791 
3793  Register &Reg) {
3794  // Check the type of the register, since it may have come from a
3795  // G_BUILD_VECTOR_TRUNC.
3796  LLT ScalarTy = MRI.getType(Reg);
3797  Register DstReg = MI.getOperand(0).getReg();
3798  LLT DstTy = MRI.getType(DstReg);
3799 
3801  if (ScalarTy != DstTy) {
3802  assert(ScalarTy.getSizeInBits() > DstTy.getSizeInBits());
3803  Builder.buildTrunc(DstReg, Reg);
3804  MI.eraseFromParent();
3805  return;
3806  }
3808 }
3809 
3811  MachineInstr &MI,
3812  SmallVectorImpl<std::pair<Register, MachineInstr *>> &SrcDstPairs) {
3813  assert(MI.getOpcode() == TargetOpcode::G_BUILD_VECTOR);
3814  // This combine tries to find build_vector's which have every source element
3815  // extracted using G_EXTRACT_VECTOR_ELT. This can happen when transforms like
3816  // the masked load scalarization is run late in the pipeline. There's already
3817  // a combine for a similar pattern starting from the extract, but that
3818  // doesn't attempt to do it if there are multiple uses of the build_vector,
3819  // which in this case is true. Starting the combine from the build_vector
3820  // feels more natural than trying to find sibling nodes of extracts.
3821  // E.g.
3822  // %vec(<4 x s32>) = G_BUILD_VECTOR %s1(s32), %s2, %s3, %s4
3823  // %ext1 = G_EXTRACT_VECTOR_ELT %vec, 0
3824  // %ext2 = G_EXTRACT_VECTOR_ELT %vec, 1
3825  // %ext3 = G_EXTRACT_VECTOR_ELT %vec, 2
3826  // %ext4 = G_EXTRACT_VECTOR_ELT %vec, 3
3827  // ==>
3828  // replace ext{1,2,3,4} with %s{1,2,3,4}
3829 
3830  Register DstReg = MI.getOperand(0).getReg();
3831  LLT DstTy = MRI.getType(DstReg);
3832  unsigned NumElts = DstTy.getNumElements();
3833 
3834  SmallBitVector ExtractedElts(NumElts);
3835  for (auto &II : make_range(MRI.use_instr_nodbg_begin(DstReg),
3836  MRI.use_instr_nodbg_end())) {
3837  if (II.getOpcode() != TargetOpcode::G_EXTRACT_VECTOR_ELT)
3838  return false;
3839  auto Cst = getConstantVRegVal(II.getOperand(2).getReg(), MRI);
3840  if (!Cst)
3841  return false;
3842  unsigned Idx = Cst.getValue().getZExtValue();
3843  if (Idx >= NumElts)
3844  return false; // Out of range.
3845  ExtractedElts.set(Idx);
3846  SrcDstPairs.emplace_back(
3847  std::make_pair(MI.getOperand(Idx + 1).getReg(), &II));
3848  }
3849  // Match if every element was extracted.
3850  return ExtractedElts.all();
3851 }
3852 
3854  MachineInstr &MI,
3855  SmallVectorImpl<std::pair<Register, MachineInstr *>> &SrcDstPairs) {
3856  assert(MI.getOpcode() == TargetOpcode::G_BUILD_VECTOR);
3857  for (auto &Pair : SrcDstPairs) {
3858  auto *ExtMI = Pair.second;
3859  replaceRegWith(MRI, ExtMI->getOperand(0).getReg(), Pair.first);
3860  ExtMI->eraseFromParent();
3861  }
3862  MI.eraseFromParent();
3863 }
3864 
3866  MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
3868  MatchInfo(Builder);
3869  MI.eraseFromParent();
3870  return true;
3871 }
3872 
3873 /// Match an FSHL or FSHR that can be combined to a ROTR or ROTL rotate.
3875  unsigned Opc = MI.getOpcode();
3876  assert(Opc == TargetOpcode::G_FSHL || Opc == TargetOpcode::G_FSHR);
3877  Register X = MI.getOperand(1).getReg();
3878  Register Y = MI.getOperand(2).getReg();
3879  if (X != Y)
3880  return false;
3881  unsigned RotateOpc =
3882  Opc == TargetOpcode::G_FSHL ? TargetOpcode::G_ROTL : TargetOpcode::G_ROTR;
3883  return isLegalOrBeforeLegalizer({RotateOpc, {MRI.getType(X), MRI.getType(Y)}});
3884 }
3885 
3887  unsigned Opc = MI.getOpcode();
3888  assert(Opc == TargetOpcode::G_FSHL || Opc == TargetOpcode::G_FSHR);
3889  bool IsFSHL = Opc == TargetOpcode::G_FSHL;
3891  MI.setDesc(Builder.getTII().get(IsFSHL ? TargetOpcode::G_ROTL
3892  : TargetOpcode::G_ROTR));
3893  MI.RemoveOperand(2);
3895 }
3896 
3898  if (tryCombineCopy(MI))
3899  return true;
3901  return true;
3903  return true;
3904  return false;
3905 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::CombinerHelper::matchCombineConstPtrAddToI2P
bool matchCombineConstPtrAddToI2P(MachineInstr &MI, int64_t &NewCst)
Definition: CombinerHelper.cpp:2350
i
i
Definition: README.txt:29
MIPatternMatch.h
llvm::CombinerHelper::matchCombineUnmergeWithDeadLanesToTrunc
bool matchCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI)
Transform X, Y<dead> = G_UNMERGE Z -> X = G_TRUNC Z.
Definition: CombinerHelper.cpp:2068
llvm::lltok::APFloat
@ APFloat
Definition: LLToken.h:487
llvm::IndexedLoadStoreMatchInfo::Addr
Register Addr
Definition: CombinerHelper.h:47
llvm::GISelChangeObserver::erasingInstr
virtual void erasingInstr(MachineInstr &MI)=0
An instruction is about to be erased.
llvm::SmallBitVector::set
SmallBitVector & set()
Definition: SmallBitVector.h:363
llvm::CombinerHelper::applyAshShlToSextInreg
bool applyAshShlToSextInreg(MachineInstr &MI, std::tuple< Register, int64_t > &MatchInfo)
Definition: CombinerHelper.cpp:2979
LowLevelType.h
llvm::MachineInstr::uses
iterator_range< mop_iterator > uses()
Returns a range that includes all operands that are register uses.
Definition: MachineInstr.h:655
llvm::getDefIgnoringCopies
MachineInstr * getDefIgnoringCopies(Register Reg, const MachineRegisterInfo &MRI)
Find the def instruction for Reg, folding away any trivial copies.
Definition: Utils.cpp:396
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
MachineInstr.h
MathExtras.h
llvm::MachineInstrBuilder::addImm
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
Definition: MachineInstrBuilder.h:132
llvm
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::CombinerHelper::applyExtractVecEltBuildVec
void applyExtractVecEltBuildVec(MachineInstr &MI, Register &Reg)
Definition: CombinerHelper.cpp:3792
llvm::RegisterImmPair
Definition: CombinerHelper.h:58
llvm::MachineRegisterInfo::use_instr_nodbg_end
static use_instr_nodbg_iterator use_instr_nodbg_end()
Definition: MachineRegisterInfo.h:538
llvm::MachineRegisterInfo::constrainRegAttrs
bool constrainRegAttrs(Register Reg, Register ConstrainingReg, unsigned MinNumRegs=0)
Constrain the register class or the register bank of the virtual register Reg (and low-level type) to...
Definition: MachineRegisterInfo.cpp:92
llvm::MachineIRBuilder::setDebugLoc
void setDebugLoc(const DebugLoc &DL)
Set the debug location to DL for all the next build instructions.
Definition: MachineIRBuilder.h:363
llvm::MachineIRBuilder::buildIntToPtr
MachineInstrBuilder buildIntToPtr(const DstOp &Dst, const SrcOp &Src)
Build and insert a G_INTTOPTR instruction.
Definition: MachineIRBuilder.h:636
UseMI
MachineInstrBuilder & UseMI
Definition: AArch64ExpandPseudoInsts.cpp:100
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::CombinerHelper::applyCombineI2PToP2I
bool applyCombineI2PToP2I(MachineInstr &MI, Register &Reg)
Definition: CombinerHelper.cpp:2281
llvm::LLT::getScalarSizeInBits
unsigned getScalarSizeInBits() const
Definition: LowLevelTypeImpl.h:163
llvm::CombinerHelper::matchCombineUnmergeConstant
bool matchCombineUnmergeConstant(MachineInstr &MI, SmallVectorImpl< APInt > &Csts)
Transform G_UNMERGE Constant -> Constant1, Constant2, ...
Definition: CombinerHelper.cpp:2026
llvm::CombinerHelper::MRI
MachineRegisterInfo & MRI
Definition: CombinerHelper.h:92
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
llvm::CombinerHelper::matchHoistLogicOpWithSameOpcodeHands
bool matchHoistLogicOpWithSameOpcodeHands(MachineInstr &MI, InstructionStepsMatchInfo &MatchInfo)
Match (logic_op (op x...), (op y...)) -> (op (logic_op x, y))
Definition: CombinerHelper.cpp:2855
llvm::MachineIRBuilder::buildAShr
MachineInstrBuilder buildAShr(const DstOp &Dst, const SrcOp &Src0, const SrcOp &Src1, Optional< unsigned > Flags=None)
Definition: MachineIRBuilder.h:1496
llvm::MachineMemOperand::getAlign
Align getAlign() const
Return the minimum known alignment in bytes of the actual memory reference.
Definition: MachineOperand.cpp:1069
llvm::MIPatternMatch::m_GFNeg
UnaryOp_match< SrcTy, TargetOpcode::G_FNEG > m_GFNeg(const SrcTy &Src)
Definition: MIPatternMatch.h:395
llvm::MIPatternMatch::m_Reg
operand_type_match m_Reg()
Definition: MIPatternMatch.h:106
llvm::MIPatternMatch::m_GAnd
BinaryOp_match< LHS, RHS, TargetOpcode::G_AND, true > m_GAnd(const LHS &L, const RHS &R)
Definition: MIPatternMatch.h:276
llvm::GISelKnownBits
Definition: GISelKnownBits.h:29
llvm::MIPatternMatch::m_GShl
BinaryOp_match< LHS, RHS, TargetOpcode::G_SHL, false > m_GShl(const LHS &L, const RHS &R)
Definition: MIPatternMatch.h:294
llvm::CombinerHelper::applySimplifyURemByPow2
bool applySimplifyURemByPow2(MachineInstr &MI)
Combine G_UREM x, (known power of 2) to an add and bitmasking.
Definition: CombinerHelper.cpp:3291
llvm::ShiftOfShiftedLogic::Shift2
MachineInstr * Shift2
Definition: CombinerHelper.h:65
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::MachineInstr::mayLoadOrStore
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
Definition: MachineInstr.h:1017
llvm::LegalizeActionStep::Action
LegalizeAction Action
The action to take or the final answer.
Definition: LegalizerInfo.h:152
llvm::CombinerHelper::eraseInst
bool eraseInst(MachineInstr &MI)
Erase MI.
Definition: CombinerHelper.cpp:2602
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:197
llvm::MachineInstr::memoperands_begin
mmo_iterator memoperands_begin() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:697
llvm::CombinerHelper::applyCombineMulByNegativeOne
bool applyCombineMulByNegativeOne(MachineInstr &MI)
Transform G_MUL(x, -1) to G_SUB(0, x)
Definition: CombinerHelper.cpp:2457
llvm::IndexedLoadStoreMatchInfo::Base
Register Base
Definition: CombinerHelper.h:48
llvm::getOpcodeDef
MachineInstr * getOpcodeDef(unsigned Opcode, Register Reg, const MachineRegisterInfo &MRI)
See if Reg is defined by an single def instruction that is Opcode.
Definition: Utils.cpp:410
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::KnownBits::Zero
APInt Zero
Definition: KnownBits.h:24
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
constantFoldFpUnary
static Optional< APFloat > constantFoldFpUnary(unsigned Opcode, LLT DstTy, const Register Op, const MachineRegisterInfo &MRI)
Definition: CombinerHelper.cpp:1585
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:131
llvm::MachineIRBuilder::buildSplatVector
MachineInstrBuilder buildSplatVector(const DstOp &Res, const SrcOp &Src)
Build and insert Res = G_BUILD_VECTOR with Src replicated to fill the number of elements.
Definition: MachineIRBuilder.cpp:643
llvm::CombinerHelper::matchCombineP2IToI2P
bool matchCombineP2IToI2P(MachineInstr &MI, Register &Reg)
Transform PtrToInt(IntToPtr(x)) to x.
Definition: CombinerHelper.cpp:2290
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::CombinerHelper::getTargetLowering
const TargetLowering & getTargetLowering() const
Definition: CombinerHelper.cpp:52
llvm::MachineIRBuilder::getMRI
MachineRegisterInfo * getMRI()
Getter for MRI.
Definition: MachineIRBuilder.h:288
llvm::CombinerHelper::applyCombineExtOfExt
bool applyCombineExtOfExt(MachineInstr &MI, std::tuple< Register, unsigned > &MatchInfo)
Definition: CombinerHelper.cpp:2423
llvm::MachineFunction::getMachineMemOperand
MachineMemOperand * getMachineMemOperand(MachinePointerInfo PtrInfo, MachineMemOperand::Flags f, uint64_t s, Align base_alignment, const AAMDNodes &AAInfo=AAMDNodes(), const MDNode *Ranges=nullptr, SyncScope::ID SSID=SyncScope::System, AtomicOrdering Ordering=AtomicOrdering::NotAtomic, AtomicOrdering FailureOrdering=AtomicOrdering::NotAtomic)
getMachineMemOperand - Allocate a new MachineMemOperand.
Definition: MachineFunction.cpp:430
llvm::GISelChangeObserver::finishedChangingAllUsesOfReg
void finishedChangingAllUsesOfReg()
All instructions reported as changing by changingAllUsesOfReg() have finished being changed.
Definition: GISelChangeObserver.cpp:26
llvm::CombinerHelper::tryCombineMemCpyFamily
bool tryCombineMemCpyFamily(MachineInstr &MI, unsigned MaxLen=0)
Optimize memcpy intrinsics et al, e.g.
Definition: CombinerHelper.cpp:1536
peekThroughBitcast
static Register peekThroughBitcast(Register Reg, const MachineRegisterInfo &MRI)
Definition: CombinerHelper.cpp:1967
llvm::MIPatternMatch::m_OneNonDBGUse
OneNonDBGUse_match< SubPat > m_OneNonDBGUse(const SubPat &SP)
Definition: MIPatternMatch.h:53
llvm::CombinerHelper::dominates
bool dominates(const MachineInstr &DefMI, const MachineInstr &UseMI)
Returns true if DefMI dominates UseMI.
Definition: CombinerHelper.cpp:641
llvm::MipsISD::Lo
@ Lo
Definition: MipsISelLowering.h:79
GISelKnownBits.h
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::CombinerHelper::applyCombineAddP2IToPtrAdd
bool applyCombineAddP2IToPtrAdd(MachineInstr &MI, std::pair< Register, bool > &PtrRegAndCommute)
Definition: CombinerHelper.cpp:2330
llvm::MachineRegisterInfo::getUniqueVRegDef
MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
Definition: MachineRegisterInfo.cpp:411
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:823
llvm::CombinerHelper::applyCombineUnmergeWithDeadLanesToTrunc
bool applyCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI)
Definition: CombinerHelper.cpp:2079
llvm::CombinerHelper::matchConstantSelectCmp
bool matchConstantSelectCmp(MachineInstr &MI, unsigned &OpIdx)
Return true if a G_SELECT instruction MI has a constant comparison.
Definition: CombinerHelper.cpp:2592
llvm::MachineIRBuilder::buildZExtOrTrunc
MachineInstrBuilder buildZExtOrTrunc(const DstOp &Res, const SrcOp &Op)
Build and insert Res = G_ZEXT Op, Res = G_TRUNC Op, or Res = COPY Op depending on the differing sizes...
Definition: MachineIRBuilder.cpp:479
llvm::CombinerHelper::applyCombineTruncOfExt
bool applyCombineTruncOfExt(MachineInstr &MI, std::pair< Register, unsigned > &MatchInfo)
Definition: CombinerHelper.cpp:2497
llvm::CombinerHelper::applyFunnelShiftToRotate
void applyFunnelShiftToRotate(MachineInstr &MI)
Definition: CombinerHelper.cpp:3886
llvm::MachineRegisterInfo::use_instr_nodbg_begin
use_instr_nodbg_iterator use_instr_nodbg_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:535
MachineBasicBlock.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::MIPatternMatch::m_GTrunc
UnaryOp_match< SrcTy, TargetOpcode::G_TRUNC > m_GTrunc(const SrcTy &Src)
Definition: MIPatternMatch.h:361
llvm::MemOp
Definition: TargetLowering.h:108
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:543
llvm::CombinerHelper::tryCombineShuffleVector
bool tryCombineShuffleVector(MachineInstr &MI)
Try to combine G_SHUFFLE_VECTOR into G_CONCAT_VECTORS.
Definition: CombinerHelper.cpp:242
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:231
llvm::LLT::getScalarType
LLT getScalarType() const
Definition: LowLevelTypeImpl.h:121
llvm::Function::getContext
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:316
findGISelOptimalMemOpLowering
static bool findGISelOptimalMemOpLowering(std::vector< LLT > &MemOps, unsigned Limit, const MemOp &Op, unsigned DstAS, unsigned SrcAS, const AttributeList &FuncAttributes, const TargetLowering &TLI)
Definition: CombinerHelper.cpp:1107
llvm::CombinerHelper::matchCombineDivRem
bool matchCombineDivRem(MachineInstr &MI, MachineInstr *&OtherMI)
Try to combine G_[SU]DIV and G_[SU]REM into a single G_[SU]DIVREM when their source operands are iden...
Definition: CombinerHelper.cpp:949
Shift
bool Shift
Definition: README.txt:468
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
llvm::CombinerHelper::tryCombineIndexedLoadStore
bool tryCombineIndexedLoadStore(MachineInstr &MI)
Combine MI into a pre-indexed or post-indexed load/store operation if legal and the surrounding code ...
Definition: CombinerHelper.cpp:877
llvm::LegalityQuery::MemDesc
Definition: LegalizerInfo.h:128
llvm::AttributeList
Definition: Attributes.h:385
TargetInstrInfo.h
llvm::MachineMemOperand
A description of a memory reference used in the backend.
Definition: MachineMemOperand.h:127
llvm::MachineRegisterInfo::use_operands
iterator_range< use_iterator > use_operands(Register Reg) const
Definition: MachineRegisterInfo.h:469
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
llvm::InstructionStepsMatchInfo
Definition: CombinerHelper.h:80
isBigEndian
static Optional< bool > isBigEndian(const SmallDenseMap< int64_t, int64_t, 8 > &MemOffset2Idx, int64_t LowestIdx)
Given a map from byte offsets in memory to indices in a load/store, determine if that map corresponds...
Definition: CombinerHelper.cpp:92
llvm::ConstantFP::getValueAPF
const APFloat & getValueAPF() const
Definition: Constants.h:295
llvm::LLT::isValid
bool isValid() const
Definition: LowLevelTypeImpl.h:90
llvm::MachineOperand::setPredicate
void setPredicate(unsigned Predicate)
Definition: MachineOperand.h:705
llvm::Optional< bool >
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::CombinerHelper::tryCombineShiftToUnmerge
bool tryCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftAmount)
Definition: CombinerHelper.cpp:2261
llvm::MachineIRBuilder::buildBuildVector
MachineInstrBuilder buildBuildVector(const DstOp &Res, ArrayRef< Register > Ops)
Build and insert Res = G_BUILD_VECTOR Op0, ...
Definition: MachineIRBuilder.cpp:634
llvm::CombinerHelper::matchSextTruncSextLoad
bool matchSextTruncSextLoad(MachineInstr &MI)
Definition: CombinerHelper.cpp:653
llvm::MachineIRBuilder::buildInstrNoInsert
MachineInstrBuilder buildInstrNoInsert(unsigned Opcode)
Build but don't insert <empty> = Opcode <empty>.
Definition: MachineIRBuilder.cpp:40
llvm::MachineIRBuilder::setInstr
void setInstr(MachineInstr &MI)
Set the insertion point to before MI.
Definition: MachineIRBuilder.h:341
MachineIRBuilder.h
llvm::MachineDominatorTree::dominates
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:109
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::APInt::lshr
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:987
llvm::MachineIRBuilder::buildExtOrTrunc
MachineInstrBuilder buildExtOrTrunc(unsigned ExtOpc, const DstOp &Res, const SrcOp &Op)
Build and insert Res = ExtOpc, Res = G_TRUNC Op, or Res = COPY Op depending on the differing sizes of...
Definition: MachineIRBuilder.cpp:450
llvm::isPowerOf2_32
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:491
llvm::CombinerHelper::matchPtrAddZero
bool matchPtrAddZero(MachineInstr &MI)
}
Definition: CombinerHelper.cpp:3264
llvm::CombinerHelper::tryCombineExtendingLoads
bool tryCombineExtendingLoads(MachineInstr &MI)
If MI is extend that consumes the result of a load, try to combine it.
Definition: CombinerHelper.cpp:427
llvm::MachineIRBuilder::buildXor
MachineInstrBuilder buildXor(const DstOp &Dst, const SrcOp &Src0, const SrcOp &Src1)
Build and insert Res = G_XOR Op0, Op1.
Definition: MachineIRBuilder.h:1535
llvm::PtrAddChain::Imm
int64_t Imm
Definition: CombinerHelper.h:54
llvm::CombinerHelper::matchPtrAddImmedChain
bool matchPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo)
Definition: CombinerHelper.cpp:1648
llvm::CombinerHelper::matchNotCmp
bool matchNotCmp(MachineInstr &MI, SmallVectorImpl< Register > &RegsToNegate)
Combine inverting a result of a compare into the opposite cond code.
Definition: CombinerHelper.cpp:3108
LegalizerInfo.h
llvm::BitmaskEnumDetail::Mask
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
llvm::CombinerHelper::matchCombineCopy
bool matchCombineCopy(MachineInstr &MI)
Definition: CombinerHelper.cpp:151
llvm::MachineFrameInfo::setObjectAlignment
void setObjectAlignment(int ObjectIdx, Align Alignment)
setObjectAlignment - Change the alignment of the specified stack object.
Definition: MachineFrameInfo.h:478
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
llvm::CombinerHelper::matchCombineAddP2IToPtrAdd
bool matchCombineAddP2IToPtrAdd(MachineInstr &MI, std::pair< Register, bool > &PtrRegAndCommute)
Transform G_ADD (G_PTRTOINT x), y -> G_PTRTOINT (G_PTR_ADD x, y) Transform G_ADD y,...
Definition: CombinerHelper.cpp:2305
llvm::MachineIRBuilder::buildConstant
virtual MachineInstrBuilder buildConstant(const DstOp &Res, const ConstantInt &Val)
Build and insert Res = G_CONSTANT Val.
Definition: MachineIRBuilder.cpp:255
llvm::MIPatternMatch::m_GPtrToInt
UnaryOp_match< SrcTy, TargetOpcode::G_PTRTOINT > m_GPtrToInt(const SrcTy &Src)
Definition: MIPatternMatch.h:373
llvm::getICmpTrueVal
int64_t getICmpTrueVal(const TargetLowering &TLI, bool IsVector, bool IsFP)
Returns an integer representing true, as defined by the TargetBooleanContents.
Definition: Utils.cpp:974
llvm::MIPatternMatch::m_GFabs
UnaryOp_match< SrcTy, TargetOpcode::G_FABS > m_GFabs(const SrcTy &Src)
Definition: MIPatternMatch.h:390
llvm::PtrAddChain
Definition: CombinerHelper.h:53
MachineRegisterInfo.h
llvm::CombinerHelper::applyCombineUnmergeMergeToPlainValues
bool applyCombineUnmergeMergeToPlainValues(MachineInstr &MI, SmallVectorImpl< Register > &Operands)
Definition: CombinerHelper.cpp:2002
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:583
llvm::CombinerHelper::matchAshrShlToSextInreg
bool matchAshrShlToSextInreg(MachineInstr &MI, std::tuple< Register, int64_t > &MatchInfo)
Match ashr (shl x, C), C -> sext_inreg (C)
Definition: CombinerHelper.cpp:2962
isConstValidTrue
static bool isConstValidTrue(const TargetLowering &TLI, unsigned ScalarSizeBits, int64_t Cst, bool IsVector, bool IsFP)
Definition: CombinerHelper.cpp:3101
llvm::MipsISD::Hi
@ Hi
Definition: MipsISelLowering.h:75
llvm::getFltSemanticForLLT
const llvm::fltSemantics & getFltSemanticForLLT(LLT Ty)
Get the appropriate floating point arithmetic semantic based on the bit size of the given scalar LLT.
Definition: LowLevelType.cpp:63
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:286
llvm::InstructionBuildSteps
Definition: CombinerHelper.h:72
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::PtrAddChain::Base
Register Base
Definition: CombinerHelper.h:55
llvm::SmallBitVector
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
Definition: SmallBitVector.h:34
llvm::CombinerHelper::applyNotCmp
bool applyNotCmp(MachineInstr &MI, SmallVectorImpl< Register > &RegsToNegate)
Definition: CombinerHelper.cpp:3185
llvm::MachineInstr::getFlags
uint16_t getFlags() const
Return the MI flags bitvector.
Definition: MachineInstr.h:325
llvm::MachineMemOperand::getPointerInfo
const MachinePointerInfo & getPointerInfo() const
Definition: MachineMemOperand.h:191
llvm::CombinerHelper::applyBuildFn
bool applyBuildFn(MachineInstr &MI, std::function< void(MachineIRBuilder &)> &MatchInfo)
Use a function which takes in a MachineIRBuilder to perform a combine.
Definition: CombinerHelper.cpp:3865
llvm::MIPatternMatch::m_GSExt
UnaryOp_match< SrcTy, TargetOpcode::G_SEXT > m_GSExt(const SrcTy &Src)
Definition: MIPatternMatch.h:346
llvm::MachineInstrBuilder::addDef
const MachineInstrBuilder & addDef(Register RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register definition operand.
Definition: MachineInstrBuilder.h:117
llvm::RegisterImmPair::Imm
int64_t Imm
Definition: CombinerHelper.h:60
TargetLowering.h
llvm::CombinerHelper::matchLoadOrCombine
bool matchLoadOrCombine(MachineInstr &MI, std::function< void(MachineIRBuilder &)> &MatchInfo)
Match expression trees of the form.
Definition: CombinerHelper.cpp:3539
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1505
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:565
llvm::CombinerHelper::applyCombineShiftToUnmerge
bool applyCombineShiftToUnmerge(MachineInstr &MI, const unsigned &ShiftVal)
Definition: CombinerHelper.cpp:2187
llvm::MachineIRBuilder::buildUnmerge
MachineInstrBuilder buildUnmerge(ArrayRef< LLT > Res, const SrcOp &Op)
Build and insert Res0, ...
Definition: MachineIRBuilder.cpp:605
TargetMachine.h
llvm::MachineIRBuilder::buildZExt
MachineInstrBuilder buildZExt(const DstOp &Res, const SrcOp &Op)
Build and insert Res = G_ZEXT Op.
Definition: MachineIRBuilder.cpp:426
llvm::GISelKnownBits::getKnownBits
KnownBits getKnownBits(Register R)
Definition: GISelKnownBits.cpp:56
llvm::MIPatternMatch::m_GZExt
UnaryOp_match< SrcTy, TargetOpcode::G_ZEXT > m_GZExt(const SrcTy &Src)
Definition: MIPatternMatch.h:351
llvm::CombinerHelper::MDT
MachineDominatorTree * MDT
Definition: CombinerHelper.h:95
llvm::PowerOf2Floor
uint64_t PowerOf2Floor(uint64_t A)
Returns the power of two which is less than or equal to the given value.
Definition: MathExtras.h:695
llvm::CombinerHelper::matchCombineConcatVectors
bool matchCombineConcatVectors(MachineInstr &MI, bool &IsUndef, SmallVectorImpl< Register > &Ops)
Check if the G_CONCAT_VECTORS MI is undef or if it can be flattened into a build_vector.
Definition: CombinerHelper.cpp:175
llvm::TargetLoweringBase::getOptimalMemOpLLT
virtual LLT getOptimalMemOpLLT(const MemOp &Op, const AttributeList &) const
LLT returning variant.
Definition: TargetLowering.h:1678
llvm::CombinerHelper::matchRedundantSExtInReg
bool matchRedundantSExtInReg(MachineInstr &MI)
Definition: CombinerHelper.cpp:3093
llvm::MachineIRBuilder::buildShl
MachineInstrBuilder buildShl(const DstOp &Dst, const SrcOp &Src0, const SrcOp &Src1, Optional< unsigned > Flags=None)
Definition: MachineIRBuilder.h:1484
llvm::CombinerHelper::matchCombineZextTrunc
bool matchCombineZextTrunc(MachineInstr &MI, Register &Reg)
Transform zext(trunc(x)) to x.
Definition: CombinerHelper.cpp:2388
llvm::ShiftOfShiftedLogic
Definition: CombinerHelper.h:63
llvm::MachineMemOperand::getAddrSpace
unsigned getAddrSpace() const
Definition: MachineMemOperand.h:218
llvm::Triple::isOSDarwin
bool isOSDarwin() const
isOSDarwin - Is this a "Darwin" OS (macOS, iOS, tvOS or watchOS).
Definition: Triple.h:484
llvm::MIPatternMatch::m_GPtrAdd
BinaryOp_match< LHS, RHS, TargetOpcode::G_PTR_ADD, true > m_GPtrAdd(const LHS &L, const RHS &R)
Definition: MIPatternMatch.h:240
llvm::LLT::getSizeInBits
unsigned getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
Definition: LowLevelTypeImpl.h:109
llvm::EVT
Extended Value Type.
Definition: ValueTypes.h:35
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:488
llvm::LegalityQuery::MemDesc::AlignInBits
uint64_t AlignInBits
Definition: LegalizerInfo.h:130
llvm::MachineIRBuilder::buildPtrToInt
MachineInstrBuilder buildPtrToInt(const DstOp &Dst, const SrcOp &Src)
Build and insert a G_PTRTOINT instruction.
Definition: MachineIRBuilder.h:631
llvm::TargetLowering
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Definition: TargetLowering.h:3141
llvm::KnownBits::One
APInt One
Definition: KnownBits.h:25
llvm::GISelChangeObserver::changingAllUsesOfReg
void changingAllUsesOfReg(const MachineRegisterInfo &MRI, Register Reg)
All the instructions using the given register are being changed.
Definition: GISelChangeObserver.cpp:18
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::LLT::getSizeInBytes
unsigned getSizeInBytes() const
Returns the total size of the type in bytes, i.e.
Definition: LowLevelTypeImpl.h:117
Utils.h
TargetOpcodes.h
llvm::MIPatternMatch::m_GIntToPtr
UnaryOp_match< SrcTy, TargetOpcode::G_INTTOPTR > m_GIntToPtr(const SrcTy &Src)
Definition: MIPatternMatch.h:379
llvm::CombinerHelper::matchAnyExplicitUseIsUndef
bool matchAnyExplicitUseIsUndef(MachineInstr &MI)
Return true if any explicit use operand on MI is defined by a G_IMPLICIT_DEF.
Definition: CombinerHelper.cpp:2560
llvm::Log2_32
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:596
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::SmallBitVector::all
bool all() const
Returns true if all bits are set.
Definition: SmallBitVector.h:213
llvm::APFloat::convertToDouble
double convertToDouble() const
Definition: APFloat.h:1135
getMemsetValue
static Register getMemsetValue(Register Val, LLT Ty, MachineIRBuilder &MIB)
Definition: CombinerHelper.cpp:1180
llvm::PreferredTuple::Ty
LLT Ty
Definition: CombinerHelper.h:41
llvm::CombinerHelper::matchCombineI2PToP2I
bool matchCombineI2PToP2I(MachineInstr &MI, Register &Reg)
Transform IntToPtr(PtrToInt(x)) to x if cast is in the same address space.
Definition: CombinerHelper.cpp:2272
llvm::MachineIRBuilder::getMF
MachineFunction & getMF()
Getter for the function we currently build.
Definition: MachineIRBuilder.h:270
llvm::ConstantFP
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:255
llvm::CombinerHelper::applyCombineShlOfExtend
bool applyCombineShlOfExtend(MachineInstr &MI, const RegisterImmPair &MatchData)
Definition: CombinerHelper.cpp:1952
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
llvm::codeview::EncodedFramePtrReg::BasePtr
@ BasePtr
llvm::CombinerHelper::matchCombineFNegOfFNeg
bool matchCombineFNegOfFNeg(MachineInstr &MI, Register &Reg)
Transform fneg(fneg(x)) to x.
Definition: CombinerHelper.cpp:2470
llvm::CombinerHelper::applyExtendThroughPhis
bool applyExtendThroughPhis(MachineInstr &MI, MachineInstr *&ExtMI)
Definition: CombinerHelper.cpp:3708
INT64_MAX
#define INT64_MAX
Definition: DataTypes.h:71
llvm::MachineIRBuilder::buildAnd
MachineInstrBuilder buildAnd(const DstOp &Dst, const SrcOp &Src0, const SrcOp &Src1)
Build and insert Res = G_AND Op0, Op1.
Definition: MachineIRBuilder.h:1513
llvm::GISelChangeObserver::changingInstr
virtual void changingInstr(MachineInstr &MI)=0
This instruction is about to be mutated in some way.
llvm::MachineInstr::isIdenticalTo
bool isIdenticalTo(const MachineInstr &Other, MICheckType Check=CheckDefs) const
Return true if this instruction is identical to Other.
Definition: MachineInstr.cpp:592
llvm::CombinerHelper::applyCombineConcatVectors
void applyCombineConcatVectors(MachineInstr &MI, bool IsUndef, const ArrayRef< Register > Ops)
Replace MI with a flattened build_vector with Ops or an implicit_def if IsUndef is true.
Definition: CombinerHelper.cpp:220
llvm::CombinerHelper::applyCombineMulToShl
bool applyCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal)
Definition: CombinerHelper.cpp:1901
llvm::CombinerHelper::matchCombineShuffleVector
bool matchCombineShuffleVector(MachineInstr &MI, SmallVectorImpl< Register > &Ops)
Check if the G_SHUFFLE_VECTOR MI can be replaced by a concat_vectors.
Definition: CombinerHelper.cpp:251
llvm::APFloat::bitcastToAPInt
APInt bitcastToAPInt() const
Definition: APFloat.h:1132
llvm::MachineFrameInfo::isFixedObjectIndex
bool isFixedObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a fixed stack object.
Definition: MachineFrameInfo.h:677
llvm::MIPatternMatch::m_MInstr
bind_ty< MachineInstr * > m_MInstr(MachineInstr *&MI)
Definition: MIPatternMatch.h:201
llvm::FixedVectorType::get
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
Definition: Type.cpp:644
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::MachineIRBuilder::buildLoadInstr
MachineInstrBuilder buildLoadInstr(unsigned Opcode, const DstOp &Res, const SrcOp &Addr, MachineMemOperand &MMO)
Build and insert Res = <opcode> Addr, MMO.
Definition: MachineIRBuilder.cpp:357
llvm::MachineRegisterInfo::getVRegDef
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Definition: MachineRegisterInfo.cpp:400
llvm::TargetLoweringBase::getPreferredShiftAmountTy
virtual LLVM_READONLY LLT getPreferredShiftAmountTy(LLT ShiftValueTy) const
Return the preferred type to use for a shift opcode, given the shifted amount type is ShiftValueTy.
Definition: TargetLowering.h:381
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:235
llvm::CombinerHelper::tryCombineCopy
bool tryCombineCopy(MachineInstr &MI)
If MI is COPY, try to combine it.
Definition: CombinerHelper.cpp:144
llvm::LegalizeActions::Legal
@ Legal
The operation is expected to be selectable directly by the target, and no transformation is necessary...
Definition: LegalizerInfo.h:48
llvm::MIPatternMatch::m_SpecificType
CheckType m_SpecificType(LLT Ty)
Definition: MIPatternMatch.h:453
llvm::CombinerHelper::Observer
GISelChangeObserver & Observer
Definition: CombinerHelper.h:93
llvm::None
const NoneType None
Definition: None.h:23
llvm::MachineInstrBuilder::getReg
Register getReg(unsigned Idx) const
Get the register for the operand index.
Definition: MachineInstrBuilder.h:95
llvm::CombinerHelper::matchCombineUnmergeZExtToZExt
bool matchCombineUnmergeZExtToZExt(MachineInstr &MI)
Transform X, Y = G_UNMERGE(G_ZEXT(Z)) -> X = G_ZEXT(Z); Y = G_CONSTANT 0.
Definition: CombinerHelper.cpp:2101
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::CombinerHelper::matchUndefShuffleVectorMask
bool matchUndefShuffleVectorMask(MachineInstr &MI)
Return true if a G_SHUFFLE_VECTOR instruction MI has an undef mask.
Definition: CombinerHelper.cpp:2574
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::TargetInstrInfo::isExtendLikelyToBeFolded
virtual bool isExtendLikelyToBeFolded(MachineInstr &ExtMI, MachineRegisterInfo &MRI) const
Given the generic extension instruction ExtMI, returns true if this extension is a likely candidate f...
Definition: TargetInstrInfo.h:1958
llvm::LegalityQuery::MemDesc::SizeInBits
uint64_t SizeInBits
Definition: LegalizerInfo.h:129
llvm::CombinerHelper::applyXorOfAndWithSameReg
bool applyXorOfAndWithSameReg(MachineInstr &MI, std::pair< Register, Register > &MatchInfo)
Definition: CombinerHelper.cpp:3249
llvm::CombinerHelper::KB
GISelKnownBits * KB
Definition: CombinerHelper.h:94
llvm::MIPatternMatch::m_GAnyExt
UnaryOp_match< SrcTy, TargetOpcode::G_ANYEXT > m_GAnyExt(const SrcTy &Src)
Definition: MIPatternMatch.h:341
matchLoadAndBytePosition
static Optional< std::pair< MachineInstr *, int64_t > > matchLoadAndBytePosition(Register Reg, unsigned MemSizeInBits, const MachineRegisterInfo &MRI)
Helper function for findLoadOffsetsForLoadOrCombine.
Definition: CombinerHelper.cpp:3378
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:78
llvm::IndexedLoadStoreMatchInfo::Offset
Register Offset
Definition: CombinerHelper.h:49
llvm::CombinerHelper::applyCombineConstPtrAddToI2P
bool applyCombineConstPtrAddToI2P(MachineInstr &MI, int64_t &NewCst)
Definition: CombinerHelper.cpp:2368
llvm::CombinerHelper::applySextTruncSextLoad
bool applySextTruncSextLoad(MachineInstr &MI)
Definition: CombinerHelper.cpp:679
llvm::LLT::getAddressSpace
unsigned getAddressSpace() const
Definition: LowLevelTypeImpl.h:178
llvm::GISelChangeObserver::changedInstr
virtual void changedInstr(MachineInstr &MI)=0
This instruction was mutated in some way.
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:555
llvm::DataLayout::isBigEndian
bool isBigEndian() const
Definition: DataLayout.h:242
llvm::CombinerHelper::matchRedundantAnd
bool matchRedundantAnd(MachineInstr &MI, Register &Replacement)
Definition: CombinerHelper.cpp:2992
llvm::cl::opt< bool >
llvm::APFloat
Definition: APFloat.h:701
llvm::CombinerHelper::tryCombineConcatVectors
bool tryCombineConcatVectors(MachineInstr &MI)
If MI is G_CONCAT_VECTORS, try to combine it.
Definition: CombinerHelper.cpp:165
llvm::APFloat::changeSign
void changeSign()
Definition: APFloat.h:1088
llvm::GISelKnownBits::computeNumSignBits
unsigned computeNumSignBits(Register R, const APInt &DemandedElts, unsigned Depth=0)
Definition: GISelKnownBits.cpp:518
llvm::MachineIRBuilder::buildFConstant
virtual MachineInstrBuilder buildFConstant(const DstOp &Res, const ConstantFP &Val)
Build and insert Res = G_FCONSTANT Val.
Definition: MachineIRBuilder.cpp:284
llvm::LegalityQuery::MemDesc::Ordering
AtomicOrdering Ordering
Definition: LegalizerInfo.h:131
llvm::CombinerHelper::matchUndefStore
bool matchUndefStore(MachineInstr &MI)
Return true if a G_STORE instruction MI is storing an undef value.
Definition: CombinerHelper.cpp:2580
llvm::MachineIRBuilder::setInsertPt
void setInsertPt(MachineBasicBlock &MBB, MachineBasicBlock::iterator II)
Set the insertion point before the specified position.
Definition: MachineIRBuilder.h:314
llvm::MachineIRBuilder
Helper class to build MachineInstr.
Definition: MachineIRBuilder.h:220
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:318
llvm::MachineOperand::getCImm
const ConstantInt * getCImm() const
Definition: MachineOperand.h:539
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::MachineInstrBuilder
Definition: MachineInstrBuilder.h:70
llvm::CombinerHelper::matchUndefSelectCmp
bool matchUndefSelectCmp(MachineInstr &MI)
Return true if a G_SELECT instruction MI has an undef comparison.
Definition: CombinerHelper.cpp:2586
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:80
llvm::MachineRegisterInfo::use_instr_begin
use_instr_iterator use_instr_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:477
llvm::MachineIRBuilder::buildMul
MachineInstrBuilder buildMul(const DstOp &Dst, const SrcOp &Src0, const SrcOp &Src1, Optional< unsigned > Flags=None)
Build and insert Res = G_MUL Op0, Op1.
Definition: MachineIRBuilder.h:1429
llvm::isConstTrueVal
bool isConstTrueVal(const TargetLowering &TLI, int64_t Val, bool IsVector, bool IsFP)
Returns true if given the TargetLowering's boolean contents information, the value Val contains a tru...
Definition: Utils.cpp:961
llvm::MachinePointerInfo
This class contains a discriminated union of information about pointers in memory operands,...
Definition: MachineMemOperand.h:37
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::CombinerHelper::applyShiftImmedChain
bool applyShiftImmedChain(MachineInstr &MI, RegisterImmPair &MatchInfo)
Definition: CombinerHelper.cpp:1739
llvm::MachineIRBuilder::setInstrAndDebugLoc
void setInstrAndDebugLoc(MachineInstr &MI)
Set the insertion point to before MI, and set the debug loc to MI's loc.
Definition: MachineIRBuilder.h:350
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MachineIRBuilder::buildPtrAdd
MachineInstrBuilder buildPtrAdd(const DstOp &Res, const SrcOp &Op0, const SrcOp &Op1)
Build and insert Res = G_PTR_ADD Op0, Op1.
Definition: MachineIRBuilder.cpp:182
llvm::MIPatternMatch::Or
Definition: MIPatternMatch.h:128
llvm::isBuildVectorAllZeros
bool isBuildVectorAllZeros(const MachineInstr &MI, const MachineRegisterInfo &MRI)
Return true if the specified instruction is a G_BUILD_VECTOR or G_BUILD_VECTOR_TRUNC where all of the...
Definition: Utils.cpp:905
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::GISelKnownBits::getKnownZeroes
APInt getKnownZeroes(Register R)
Definition: GISelKnownBits.cpp:80
llvm::ShiftOfShiftedLogic::LogicNonShiftReg
Register LogicNonShiftReg
Definition: CombinerHelper.h:66
llvm::MachineFrameInfo::getObjectAlign
Align getObjectAlign(int ObjectIdx) const
Return the alignment of the specified stack object.
Definition: MachineFrameInfo.h:471
llvm::CombinerHelper::Builder
MachineIRBuilder & Builder
Definition: CombinerHelper.h:91
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:440
llvm::MachineBasicBlock::getFirstNonPHI
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: MachineBasicBlock.cpp:199
Magic
const char Magic[]
Definition: Archive.cpp:41
llvm::LLT::isVector
bool isVector() const
Definition: LowLevelTypeImpl.h:96
llvm::LLT::getNumElements
uint16_t getNumElements() const
Returns the number of elements in a vector LLT.
Definition: LowLevelTypeImpl.h:100
llvm::CombinerHelper::matchCombineIndexedLoadStore
bool matchCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo)
Definition: CombinerHelper.cpp:886
llvm::CombinerHelper::matchCombineConstantFoldFpUnary
bool matchCombineConstantFoldFpUnary(MachineInstr &MI, Optional< APFloat > &Cst)
Transform fp_instr(cst) to constant result of the fp operation.
Definition: CombinerHelper.cpp:1627
llvm::MachineOperand::getFPImm
const ConstantFP * getFPImm() const
Definition: MachineOperand.h:544
llvm::MachineOperand::getPredicate
unsigned getPredicate() const
Definition: MachineOperand.h:585
llvm::CombinerHelper::matchCombineShlOfExtend
bool matchCombineShlOfExtend(MachineInstr &MI, RegisterImmPair &MatchData)
Definition: CombinerHelper.cpp:1915
llvm::CombinerHelper::matchConstantOp
bool matchConstantOp(const MachineOperand &MOP, int64_t C)
Return true if MOP is defined by a G_CONSTANT with a value equal to C.
Definition: CombinerHelper.cpp:2679
llvm::CombinerHelper::matchEqualDefs
bool matchEqualDefs(const MachineOperand &MOP1, const MachineOperand &MOP2)
Return true if MOP1 and MOP2 are register operands are defined by equivalent instructions.
Definition: CombinerHelper.cpp:2607
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::getConstantVRegSExtVal
Optional< int64_t > getConstantVRegSExtVal(Register VReg, const MachineRegisterInfo &MRI)
If VReg is defined by a G_CONSTANT fits in int64_t returns it.
Definition: Utils.cpp:281
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CombinerHelper::replaceSingleDefInstWithOperand
bool replaceSingleDefInstWithOperand(MachineInstr &MI, unsigned OpIdx)
Delete MI and replace all of its uses with its OpIdx-th operand.
Definition: CombinerHelper.cpp:2687
llvm::TargetLoweringBase::allowsMisalignedMemoryAccesses
virtual bool allowsMisalignedMemoryAccesses(EVT, unsigned AddrSpace=0, Align Alignment=Align(1), MachineMemOperand::Flags Flags=MachineMemOperand::MONone, bool *=nullptr) const
Determine if the target supports unaligned memory accesses.
Definition: TargetLowering.h:1609
llvm::LLT::isPointer
bool isPointer() const
Definition: LowLevelTypeImpl.h:94
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::LegalizerInfo::getAction
LegalizeActionStep getAction(const LegalityQuery &Query) const
Determine what action should be taken to legalize the described instruction.
Definition: LegalizerInfo.cpp:466
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:225
llvm::CombinerHelper::matchCombineTruncOfExt
bool matchCombineTruncOfExt(MachineInstr &MI, std::pair< Register, unsigned > &MatchInfo)
Transform trunc ([asz]ext x) to x or ([asz]ext x) or (trunc x).
Definition: CombinerHelper.cpp:2483
llvm::CombinerHelper::matchCombineMulToShl
bool matchCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal)
Transform a multiply by a power-of-2 value to a left shift.
Definition: CombinerHelper.cpp:1889
llvm::KnownBits::countMinLeadingZeros
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition: KnownBits.h:229
llvm::PreferredTuple::ExtendOpcode
unsigned ExtendOpcode
Definition: CombinerHelper.h:42
llvm::CombinerHelper::applyShiftOfShiftedLogic
bool applyShiftOfShiftedLogic(MachineInstr &MI, ShiftOfShiftedLogic &MatchInfo)
Definition: CombinerHelper.cpp:1854
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::CombinerHelper::isLegalOrBeforeLegalizer
bool isLegalOrBeforeLegalizer(const LegalityQuery &Query) const
Definition: CombinerHelper.cpp:116
llvm::TargetInstrInfo::produceSameValue
virtual bool produceSameValue(const MachineInstr &MI0, const MachineInstr &MI1, const MachineRegisterInfo *MRI=nullptr) const
Return true if two machine instructions would produce identical values.
Definition: TargetInstrInfo.cpp:429
llvm::MachineRegisterInfo::createGenericVirtualRegister
Register createGenericVirtualRegister(LLT Ty, StringRef Name="")
Create and return a new generic virtual register with low-level type Ty.
Definition: MachineRegisterInfo.cpp:188
llvm::MVT
Machine Value Type.
Definition: MachineValueType.h:30
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:98
llvm::MachineInstr::isDereferenceableInvariantLoad
bool isDereferenceableInvariantLoad(AAResults *AA) const
Return true if this load instruction never traps and points to a memory location whose value doesn't ...
Definition: MachineInstr.cpp:1398
llvm::CombinerHelper::replaceInstWithUndef
bool replaceInstWithUndef(MachineInstr &MI)
Replace an instruction with a G_IMPLICIT_DEF.
Definition: CombinerHelper.cpp:2756
llvm::MachineInstrBuilder::addUse
const MachineInstrBuilder & addUse(Register RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register use operand.
Definition: MachineInstrBuilder.h:124
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:357
llvm::CombinerHelper::matchCombineInsertVecElts
bool matchCombineInsertVecElts(MachineInstr &MI, SmallVectorImpl< Register > &MatchInfo)
Definition: CombinerHelper.cpp:2784
llvm::LLT::isScalar
bool isScalar() const
Definition: LowLevelTypeImpl.h:92
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:649
littleEndianByteAt
static unsigned littleEndianByteAt(const unsigned ByteWidth, const unsigned I)
Definition: CombinerHelper.cpp:60
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::MachineFunction
Definition: MachineFunction.h:227
llvm::getConstantVRegVal
Optional< APInt > getConstantVRegVal(Register VReg, const MachineRegisterInfo &MRI)
If VReg is defined by a G_CONSTANT, return the corresponding value.
Definition: Utils.cpp:270
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::CombinerHelper::applyCombineUnmergeConstant
bool applyCombineUnmergeConstant(MachineInstr &MI, SmallVectorImpl< APInt > &Csts)
Definition: CombinerHelper.cpp:2051
llvm::MachineRegisterInfo::use_nodbg_empty
bool use_nodbg_empty(Register RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register.
Definition: MachineRegisterInfo.h:566
llvm::MachineIRBuilder::buildInstr
MachineInstrBuilder buildInstr(unsigned Opcode)
Build and insert <empty> = Opcode <empty>.
Definition: MachineIRBuilder.h:375
llvm::IndexedLoadStoreMatchInfo::IsPre
bool IsPre
Definition: CombinerHelper.h:50
CombinerHelper.h
llvm::LegalityQuery
The LegalityQuery object bundles together all the information that's needed to decide whether a given...
Definition: LegalizerInfo.h:124
llvm::CombinerHelper::isPredecessor
bool isPredecessor(const MachineInstr &DefMI, const MachineInstr &UseMI)
Returns true if DefMI precedes UseMI or they are the same instruction.
Definition: CombinerHelper.cpp:625
llvm::CombinerHelper::matchXorOfAndWithSameReg
bool matchXorOfAndWithSameReg(MachineInstr &MI, std::pair< Register, Register > &MatchInfo)
Fold (xor (and x, y), y) -> (and (not x), y) {.
Definition: CombinerHelper.cpp:3218
llvm::InstructionStepsMatchInfo::InstrsToBuild
SmallVector< InstructionBuildSteps, 2 > InstrsToBuild
Describes instructions to be built during a combine.
Definition: CombinerHelper.h:82
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::CombinerHelper::applyBuildInstructionSteps
bool applyBuildInstructionSteps(MachineInstr &MI, InstructionStepsMatchInfo &MatchInfo)
Replace MI with a series of instructions described in MatchInfo.
Definition: CombinerHelper.cpp:2946
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:549
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1512
llvm::APFloatBase::IEEEdouble
static const fltSemantics & IEEEdouble() LLVM_READNONE
Definition: APFloat.cpp:166
llvm::CombinerHelper::applySextInRegOfLoad
bool applySextInRegOfLoad(MachineInstr &MI, std::tuple< Register, unsigned > &MatchInfo)
Definition: CombinerHelper.cpp:722
llvm::MachineIRBuilder::insertInstr
MachineInstrBuilder insertInstr(MachineInstrBuilder MIB)
Insert an existing instruction at the insertion point.
Definition: MachineIRBuilder.cpp:45
llvm::MachineInstr::getOpcode
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:478
llvm::MachineRegisterInfo::hasOneNonDBGUse
bool hasOneNonDBGUse(Register RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register.
Definition: MachineRegisterInfo.cpp:419
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::CombinerHelper::matchCombineExtOfExt
bool matchCombineExtOfExt(MachineInstr &MI, std::tuple< Register, unsigned > &MatchInfo)
Transform [asz]ext([asz]ext(x)) to [asz]ext x.
Definition: CombinerHelper.cpp:2402
llvm::MachineIRBuilder::buildCopy
MachineInstrBuilder buildCopy(const DstOp &Res, const SrcOp &Op)
Build and insert Res = COPY Op.
Definition: MachineIRBuilder.cpp:238
llvm::CombinerHelper::replaceRegOpWith
void replaceRegOpWith(MachineRegisterInfo &MRI, MachineOperand &FromRegOp, Register ToReg) const
Replace a single register operand with a new register and inform the observer of the changes.
Definition: CombinerHelper.cpp:133
Combiner.h
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
bigEndianByteAt
static unsigned bigEndianByteAt(const unsigned ByteWidth, const unsigned I)
Definition: CombinerHelper.cpp:69
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::CombinerHelper::matchBinOpSameVal
bool matchBinOpSameVal(MachineInstr &MI)
Optimize (x op x) -> x.
Definition: CombinerHelper.cpp:2716
llvm::MIPatternMatch::m_GXor
BinaryOp_match< LHS, RHS, TargetOpcode::G_XOR, true > m_GXor(const LHS &L, const RHS &R)
Definition: MIPatternMatch.h:282
llvm::CombinerHelper::applyCombineP2IToI2P
bool applyCombineP2IToI2P(MachineInstr &MI, Register &Reg)
Definition: CombinerHelper.cpp:2296
llvm::AMDGPU::HSAMD::Kernel::Arg::Key::IsVolatile
constexpr char IsVolatile[]
Key for Kernel::Arg::Metadata::mIsVolatile.
Definition: AMDGPUMetadata.h:194
llvm::CombinerHelper::applyCombineExtendingLoads
void applyCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo)
Definition: CombinerHelper.cpp:515
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:180
llvm::GISelChangeObserver
Abstract class that contains various methods for clients to notify about changes.
Definition: GISelChangeObserver.h:29
llvm::MachineIRBuilder::buildSExtInReg
MachineInstrBuilder buildSExtInReg(const DstOp &Res, const SrcOp &Op, int64_t ImmOp)
Build and insert Res = G_SEXT_INREG Op, ImmOp.
Definition: MachineIRBuilder.h:619
llvm::MachineIRBuilder::buildNot
MachineInstrBuilder buildNot(const DstOp &Dst, const SrcOp &Src0)
Build and insert a bitwise not, NegOne = G_CONSTANT -1 Res = G_OR Op0, NegOne.
Definition: MachineIRBuilder.h:1543
llvm::CombinerHelper::matchSelectSameVal
bool matchSelectSameVal(MachineInstr &MI)
Optimize (cond ? x : x) -> x.
Definition: CombinerHelper.cpp:2708
llvm::CombinerHelper::matchOperandIsUndef
bool matchOperandIsUndef(MachineInstr &MI, unsigned OpIdx)
Check if operand OpIdx is undef.
Definition: CombinerHelper.cpp:2728
llvm::CombinerHelper::applyPtrAddZero
bool applyPtrAddZero(MachineInstr &MI)
Definition: CombinerHelper.cpp:3282
llvm::MachinePointerInfo::getAddrSpace
unsigned getAddrSpace() const
Return the LLVM IR address space number that this pointer points into.
Definition: MachineOperand.cpp:970
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
llvm::Function::hasOptSize
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:706
llvm::CombinerHelper::applySimplifyAddToSub
bool applySimplifyAddToSub(MachineInstr &MI, std::tuple< Register, Register > &MatchInfo)
Definition: CombinerHelper.cpp:2845
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1532
llvm::MemOp::Set
static MemOp Set(uint64_t Size, bool DstAlignCanChange, Align DstAlign, bool IsZeroMemset, bool IsVolatile)
Definition: TargetLowering.h:141
llvm::MachineRegisterInfo::replaceRegWith
void replaceRegWith(Register FromReg, Register ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
Definition: MachineRegisterInfo.cpp:380
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::CombinerHelper::matchShiftOfShiftedLogic
bool matchShiftOfShiftedLogic(MachineInstr &MI, ShiftOfShiftedLogic &MatchInfo)
If we have a shift-by-constant of a bitwise logic op that itself has a shift-by-constant operand with...
Definition: CombinerHelper.cpp:1773
llvm::CombinerHelper::matchCombineFAbsOfFAbs
bool matchCombineFAbsOfFAbs(MachineInstr &MI, Register &Src)
Match fabs(fabs(x)) to fabs(x).
Definition: CombinerHelper.cpp:2476
llvm::CombinerHelper::matchCombineAnyExtTrunc
bool matchCombineAnyExtTrunc(MachineInstr &MI, Register &Reg)
Transform anyext(trunc(x)) to x.
Definition: CombinerHelper.cpp:2379
llvm::CombinerHelper::applyPtrAddImmedChain
bool applyPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo)
Definition: CombinerHelper.cpp:1681
llvm::commonAlignment
Align commonAlignment(Align A, Align B)
Returns the alignment that satisfies both alignments.
Definition: Alignment.h:221
llvm::CombinerHelper::CombinerHelper
CombinerHelper(GISelChangeObserver &Observer, MachineIRBuilder &B, GISelKnownBits *KB=nullptr, MachineDominatorTree *MDT=nullptr, const LegalizerInfo *LI=nullptr)
Definition: CombinerHelper.cpp:43
llvm::CombinerHelper::applyCombineUnmergeZExtToZExt
bool applyCombineUnmergeZExtToZExt(MachineInstr &MI)
Definition: CombinerHelper.cpp:2127
llvm::MIPatternMatch::m_GAShr
BinaryOp_match< LHS, RHS, TargetOpcode::G_ASHR, false > m_GAShr(const LHS &L, const RHS &R)
Definition: MIPatternMatch.h:306
llvm::MachineIRBuilder::buildTrunc
MachineInstrBuilder buildTrunc(const DstOp &Res, const SrcOp &Op)
Build and insert Res = G_TRUNC Op.
Definition: MachineIRBuilder.cpp:737
llvm::MemOp::Copy
static MemOp Copy(uint64_t Size, bool DstAlignCanChange, Align DstAlign, Align SrcAlign, bool IsVolatile, bool MemcpyStrSrc=false)
Definition: TargetLowering.h:126
llvm::CombinerHelper::matchOperandIsKnownToBeAPowerOfTwo
bool matchOperandIsKnownToBeAPowerOfTwo(MachineInstr &MI, unsigned OpIdx)
Check if operand OpIdx is known to be a power of 2.
Definition: CombinerHelper.cpp:2734
llvm::APInt::trunc
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:858
llvm::KnownBits
Definition: KnownBits.h:23
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:521
llvm::APFloat::clearSign
void clearSign()
Definition: APFloat.h:1089
llvm::MachineFunction::getTarget
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
Definition: MachineFunction.h:551
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::getBuildVectorConstantSplat
Optional< int64_t > getBuildVectorConstantSplat(const MachineInstr &MI, const MachineRegisterInfo &MRI)
Returns a scalar constant of a G_BUILD_VECTOR splat if it exists.
Definition: Utils.cpp:884
llvm::CombinerHelper::matchSextInRegOfLoad
bool matchSextInRegOfLoad(MachineInstr &MI, std::tuple< Register, unsigned > &MatchInfo)
Match sext_inreg(load p), imm -> sextload p.
Definition: CombinerHelper.cpp:687
MachineFrameInfo.h
llvm::Align::value
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
llvm::MachineIRBuilder::buildUndef
MachineInstrBuilder buildUndef(const DstOp &Res)
Build and insert Res = IMPLICIT_DEF.
Definition: MachineIRBuilder.cpp:584
llvm::canReplaceReg
bool canReplaceReg(Register DstReg, Register SrcReg, MachineRegisterInfo &MRI)
Check if DstReg can be replaced with SrcReg depending on the register constraints.
Definition: Utils.cpp:180
llvm::RegState::Undef
@ Undef
Value of the register doesn't matter.
Definition: MachineInstrBuilder.h:53
llvm::CombinerHelper::matchFunnelShiftToRotate
bool matchFunnelShiftToRotate(MachineInstr &MI)
Match an FSHL or FSHR that can be combined to a ROTR or ROTL rotate.
Definition: CombinerHelper.cpp:3874
llvm::MachineOperand::getIndex
int getIndex() const
Definition: MachineOperand.h:554
llvm::ConstantFP::get
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:932
llvm::TypeSize
Definition: TypeSize.h:417
llvm::CombinerHelper::matchSimplifyAddToSub
bool matchSimplifyAddToSub(MachineInstr &MI, std::tuple< Register, Register > &MatchInfo)
Return true if MI is a G_ADD which can be simplified to a G_SUB.
Definition: CombinerHelper.cpp:2764
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::size
unsigned size() const
Definition: DenseMap.h:100
llvm::CombinerHelper::applyCombineTruncOfShl
bool applyCombineTruncOfShl(MachineInstr &MI, std::pair< Register, Register > &MatchInfo)
Definition: CombinerHelper.cpp:2543
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::CombinerHelper::LI
const LegalizerInfo * LI
Definition: CombinerHelper.h:96
llvm::log2
static double log2(double V)
Definition: AMDGPULibCalls.cpp:841
llvm::CombinerHelper::applyOptBrCondByInvertingCond
void applyOptBrCondByInvertingCond(MachineInstr &MI)
Definition: CombinerHelper.cpp:1070
llvm::APInt::getSplat
static APInt getSplat(unsigned NewLen, const APInt &V)
Return a value containing V broadcasted over NewLen bits.
Definition: APInt.cpp:574
llvm::MachineBasicBlock::isLayoutSuccessor
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
Definition: MachineBasicBlock.cpp:937
llvm::MachineIRBuilder::getTII
const TargetInstrInfo & getTII()
Definition: MachineIRBuilder.h:264
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:403
llvm::MIPatternMatch::m_ICst
ConstantMatch m_ICst(int64_t &Cst)
Definition: MIPatternMatch.h:69
llvm::TargetRegisterInfo::hasStackRealignment
bool hasStackRealignment(const MachineFunction &MF) const
True if stack realignment is required and still possible.
Definition: TargetRegisterInfo.h:920
llvm::CombinerHelper::matchShiftImmedChain
bool matchShiftImmedChain(MachineInstr &MI, RegisterImmPair &MatchInfo)
Fold (shift (shift base, x), y) -> (shift base (x+y))
Definition: CombinerHelper.cpp:1694
llvm::PreferredTuple::MI
MachineInstr * MI
Definition: CombinerHelper.h:43
llvm::MachineFrameInfo
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
Definition: MachineFrameInfo.h:107
llvm::APFloatBase::rmNearestTiesToEven
static constexpr roundingMode rmNearestTiesToEven
Definition: APFloat.h:190
llvm::APFloat::convert
opStatus convert(const fltSemantics &ToSemantics, roundingMode RM, bool *losesInfo)
Definition: APFloat.cpp:4818
llvm::TargetSubtargetInfo::getTargetLowering
virtual const TargetLowering * getTargetLowering() const
Definition: TargetSubtargetInfo.h:96
llvm::RegisterImmPair::Reg
Register Reg
Definition: CombinerHelper.h:59
llvm::MachineRegisterInfo::hasOneUse
bool hasOneUse(Register RegNo) const
hasOneUse - Return true if there is exactly one instructio