1 //===-- llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h -----*- C++ -*-//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 // This file contains some helper functions which try to cleanup artifacts
9 // such as G_TRUNCs/G_[ZSA]EXTENDS that were created during legalization to make
10 // the types match. This file also contains some combines of merges that happens
11 // at the end of the legalization.
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
15 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
16 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
17 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
18 #include "llvm/CodeGen/GlobalISel/Utils.h"
19 #include "llvm/CodeGen/MachineRegisterInfo.h"
20 #include "llvm/Support/Debug.h"
21 
22 #define DEBUG_TYPE "legalizer"
23 using namespace llvm::MIPatternMatch;
24 
25 namespace llvm {
26 class LegalizationArtifactCombiner {
27   MachineIRBuilder &Builder;
28   MachineRegisterInfo &MRI;
29   const LegalizerInfo &LI;
30 
31   static bool isArtifactCast(unsigned Opc) {
32     switch (Opc) {
33     case TargetOpcode::G_TRUNC:
34     case TargetOpcode::G_SEXT:
35     case TargetOpcode::G_ZEXT:
36     case TargetOpcode::G_ANYEXT:
37       return true;
38     default:
39       return false;
40     }
41   }
42 
43 public:
44   LegalizationArtifactCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI,
45                     const LegalizerInfo &LI)
46       : Builder(B), MRI(MRI), LI(LI) {}
47 
48   bool tryCombineAnyExt(MachineInstr &MI,
49                         SmallVectorImpl<MachineInstr *> &DeadInsts,
50                         SmallVectorImpl<Register> &UpdatedDefs) {
51     assert(MI.getOpcode() == TargetOpcode::G_ANYEXT);
52 
53     Builder.setInstr(MI);
54     Register DstReg = MI.getOperand(0).getReg();
55     Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
56 
57     // aext(trunc x) - > aext/copy/trunc x
58     Register TruncSrc;
59     if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
60       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
61       Builder.buildAnyExtOrTrunc(DstReg, TruncSrc);
62       UpdatedDefs.push_back(DstReg);
63       markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
64       return true;
65     }
66 
67     // aext([asz]ext x) -> [asz]ext x
68     Register ExtSrc;
69     MachineInstr *ExtMI;
70     if (mi_match(SrcReg, MRI,
71                  m_all_of(m_MInstr(ExtMI), m_any_of(m_GAnyExt(m_Reg(ExtSrc)),
72                                                     m_GSExt(m_Reg(ExtSrc)),
73                                                     m_GZExt(m_Reg(ExtSrc)))))) {
74       Builder.buildInstr(ExtMI->getOpcode(), {DstReg}, {ExtSrc});
75       UpdatedDefs.push_back(DstReg);
76       markInstAndDefDead(MI, *ExtMI, DeadInsts);
77       return true;
78     }
79 
80     // Try to fold aext(g_constant) when the larger constant type is legal.
81     // Can't use MIPattern because we don't have a specific constant in mind.
82     auto *SrcMI = MRI.getVRegDef(SrcReg);
83     if (SrcMI->getOpcode() == TargetOpcode::G_CONSTANT) {
84       const LLT &DstTy = MRI.getType(DstReg);
85       if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
86         auto &CstVal = SrcMI->getOperand(1);
87         Builder.buildConstant(
88             DstReg, CstVal.getCImm()->getValue().sext(DstTy.getSizeInBits()));
89         UpdatedDefs.push_back(DstReg);
90         markInstAndDefDead(MI, *SrcMI, DeadInsts);
91         return true;
92       }
93     }
94     return tryFoldImplicitDef(MI, DeadInsts, UpdatedDefs);
95   }
96 
97   bool tryCombineZExt(MachineInstr &MI,
98                       SmallVectorImpl<MachineInstr *> &DeadInsts,
99                       SmallVectorImpl<Register> &UpdatedDefs) {
100     assert(MI.getOpcode() == TargetOpcode::G_ZEXT);
101 
102     Builder.setInstr(MI);
103     Register DstReg = MI.getOperand(0).getReg();
104     Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
105 
106     // zext(trunc x) - > and (aext/copy/trunc x), mask
107     Register TruncSrc;
108     if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
109       LLT DstTy = MRI.getType(DstReg);
110       if (isInstUnsupported({TargetOpcode::G_AND, {DstTy}}) ||
111           isConstantUnsupported(DstTy))
112         return false;
113       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
114       LLT SrcTy = MRI.getType(SrcReg);
115       APInt Mask = APInt::getAllOnesValue(SrcTy.getScalarSizeInBits());
116       auto MIBMask = Builder.buildConstant(
117         DstTy, Mask.zext(DstTy.getScalarSizeInBits()));
118       Builder.buildAnd(DstReg, Builder.buildAnyExtOrTrunc(DstTy, TruncSrc),
119                        MIBMask);
120       markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
121       return true;
122     }
123 
124     // Try to fold zext(g_constant) when the larger constant type is legal.
125     // Can't use MIPattern because we don't have a specific constant in mind.
126     auto *SrcMI = MRI.getVRegDef(SrcReg);
127     if (SrcMI->getOpcode() == TargetOpcode::G_CONSTANT) {
128       const LLT &DstTy = MRI.getType(DstReg);
129       if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
130         auto &CstVal = SrcMI->getOperand(1);
131         Builder.buildConstant(
132             DstReg, CstVal.getCImm()->getValue().zext(DstTy.getSizeInBits()));
133         UpdatedDefs.push_back(DstReg);
134         markInstAndDefDead(MI, *SrcMI, DeadInsts);
135         return true;
136       }
137     }
138     return tryFoldImplicitDef(MI, DeadInsts, UpdatedDefs);
139   }
140 
141   bool tryCombineSExt(MachineInstr &MI,
142                       SmallVectorImpl<MachineInstr *> &DeadInsts,
143                       SmallVectorImpl<Register> &UpdatedDefs) {
144     assert(MI.getOpcode() == TargetOpcode::G_SEXT);
145 
146     Builder.setInstr(MI);
147     Register DstReg = MI.getOperand(0).getReg();
148     Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
149 
150     // sext(trunc x) - > (sext_inreg (aext/copy/trunc x), c)
151     Register TruncSrc;
152     if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
153       LLT DstTy = MRI.getType(DstReg);
154       if (isInstUnsupported({TargetOpcode::G_SEXT_INREG, {DstTy}}))
155         return false;
156       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
157       LLT SrcTy = MRI.getType(SrcReg);
158       uint64_t SizeInBits = SrcTy.getScalarSizeInBits();
159       Builder.buildInstr(
160           TargetOpcode::G_SEXT_INREG, {DstReg},
161           {Builder.buildAnyExtOrTrunc(DstTy, TruncSrc), SizeInBits});
162       markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
163       return true;
164     }
165     return tryFoldImplicitDef(MI, DeadInsts, UpdatedDefs);
166   }
167 
168   bool tryCombineTrunc(MachineInstr &MI,
169                        SmallVectorImpl<MachineInstr *> &DeadInsts,
170                        SmallVectorImpl<Register> &UpdatedDefs) {
171     assert(MI.getOpcode() == TargetOpcode::G_TRUNC);
172 
173     Builder.setInstr(MI);
174     Register DstReg = MI.getOperand(0).getReg();
175     Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
176 
177     // Try to fold trunc(g_constant) when the smaller constant type is legal.
178     // Can't use MIPattern because we don't have a specific constant in mind.
179     auto *SrcMI = MRI.getVRegDef(SrcReg);
180     if (SrcMI->getOpcode() == TargetOpcode::G_CONSTANT) {
181       const LLT &DstTy = MRI.getType(DstReg);
182       if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
183         auto &CstVal = SrcMI->getOperand(1);
184         Builder.buildConstant(
185             DstReg, CstVal.getCImm()->getValue().trunc(DstTy.getSizeInBits()));
186         UpdatedDefs.push_back(DstReg);
187         markInstAndDefDead(MI, *SrcMI, DeadInsts);
188         return true;
189       }
190     }
191 
192     return false;
193   }
194 
195   /// Try to fold G_[ASZ]EXT (G_IMPLICIT_DEF).
196   bool tryFoldImplicitDef(MachineInstr &MI,
197                           SmallVectorImpl<MachineInstr *> &DeadInsts,
198                           SmallVectorImpl<Register> &UpdatedDefs) {
199     unsigned Opcode = MI.getOpcode();
200     assert(Opcode == TargetOpcode::G_ANYEXT || Opcode == TargetOpcode::G_ZEXT ||
201            Opcode == TargetOpcode::G_SEXT);
202 
203     if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
204                                            MI.getOperand(1).getReg(), MRI)) {
205       Builder.setInstr(MI);
206       Register DstReg = MI.getOperand(0).getReg();
207       LLT DstTy = MRI.getType(DstReg);
208 
209       if (Opcode == TargetOpcode::G_ANYEXT) {
210         // G_ANYEXT (G_IMPLICIT_DEF) -> G_IMPLICIT_DEF
211         if (isInstUnsupported({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
212           return false;
213         LLVM_DEBUG(dbgs() << ".. Combine G_ANYEXT(G_IMPLICIT_DEF): " << MI;);
214         Builder.buildInstr(TargetOpcode::G_IMPLICIT_DEF, {DstReg}, {});
215         UpdatedDefs.push_back(DstReg);
216       } else {
217         // G_[SZ]EXT (G_IMPLICIT_DEF) -> G_CONSTANT 0 because the top
218         // bits will be 0 for G_ZEXT and 0/1 for the G_SEXT.
219         if (isConstantUnsupported(DstTy))
220           return false;
221         LLVM_DEBUG(dbgs() << ".. Combine G_[SZ]EXT(G_IMPLICIT_DEF): " << MI;);
222         Builder.buildConstant(DstReg, 0);
223         UpdatedDefs.push_back(DstReg);
224       }
225 
226       markInstAndDefDead(MI, *DefMI, DeadInsts);
227       return true;
228     }
229     return false;
230   }
231 
232   static bool canFoldMergeOpcode(unsigned MergeOp, unsigned ConvertOp,
233                                  LLT OpTy, LLT DestTy) {
234     // Check if we found a definition that is like G_MERGE_VALUES.
235     switch (MergeOp) {
236     default:
237       return false;
238     case TargetOpcode::G_BUILD_VECTOR:
239     case TargetOpcode::G_MERGE_VALUES:
240       // The convert operation that we will need to insert is
241       // going to convert the input of that type of instruction (scalar)
242       // to the destination type (DestTy).
243       // The conversion needs to stay in the same domain (scalar to scalar
244       // and vector to vector), so if we were to allow to fold the merge
245       // we would need to insert some bitcasts.
246       // E.g.,
247       // <2 x s16> = build_vector s16, s16
248       // <2 x s32> = zext <2 x s16>
249       // <2 x s16>, <2 x s16> = unmerge <2 x s32>
250       //
251       // As is the folding would produce:
252       // <2 x s16> = zext s16  <-- scalar to vector
253       // <2 x s16> = zext s16  <-- scalar to vector
254       // Which is invalid.
255       // Instead we would want to generate:
256       // s32 = zext s16
257       // <2 x s16> = bitcast s32
258       // s32 = zext s16
259       // <2 x s16> = bitcast s32
260       //
261       // That is not done yet.
262       if (ConvertOp == 0)
263         return true;
264       return !DestTy.isVector();
265     case TargetOpcode::G_CONCAT_VECTORS: {
266       if (ConvertOp == 0)
267         return true;
268       if (!DestTy.isVector())
269         return false;
270 
271       const unsigned OpEltSize = OpTy.getElementType().getSizeInBits();
272 
273       // Don't handle scalarization with a cast that isn't in the same
274       // direction as the vector cast. This could be handled, but it would
275       // require more intermediate unmerges.
276       if (ConvertOp == TargetOpcode::G_TRUNC)
277         return DestTy.getSizeInBits() <= OpEltSize;
278       return DestTy.getSizeInBits() >= OpEltSize;
279     }
280     }
281   }
282 
283   bool tryCombineMerges(MachineInstr &MI,
284                         SmallVectorImpl<MachineInstr *> &DeadInsts,
285                         SmallVectorImpl<Register> &UpdatedDefs) {
286     assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES);
287 
288     unsigned NumDefs = MI.getNumOperands() - 1;
289     MachineInstr *SrcDef =
290         getDefIgnoringCopies(MI.getOperand(NumDefs).getReg(), MRI);
291     if (!SrcDef)
292       return false;
293 
294     LLT OpTy = MRI.getType(MI.getOperand(NumDefs).getReg());
295     LLT DestTy = MRI.getType(MI.getOperand(0).getReg());
296     MachineInstr *MergeI = SrcDef;
297     unsigned ConvertOp = 0;
298 
299     // Handle intermediate conversions
300     unsigned SrcOp = SrcDef->getOpcode();
301     if (isArtifactCast(SrcOp)) {
302       ConvertOp = SrcOp;
303       MergeI = getDefIgnoringCopies(SrcDef->getOperand(1).getReg(), MRI);
304     }
305 
306     if (!MergeI || !canFoldMergeOpcode(MergeI->getOpcode(),
307                                        ConvertOp, OpTy, DestTy))
308       return false;
309 
310     const unsigned NumMergeRegs = MergeI->getNumOperands() - 1;
311 
312     if (NumMergeRegs < NumDefs) {
313       if (NumDefs % NumMergeRegs != 0)
314         return false;
315 
316       Builder.setInstr(MI);
317       // Transform to UNMERGEs, for example
318       //   %1 = G_MERGE_VALUES %4, %5
319       //   %9, %10, %11, %12 = G_UNMERGE_VALUES %1
320       // to
321       //   %9, %10 = G_UNMERGE_VALUES %4
322       //   %11, %12 = G_UNMERGE_VALUES %5
323 
324       const unsigned NewNumDefs = NumDefs / NumMergeRegs;
325       for (unsigned Idx = 0; Idx < NumMergeRegs; ++Idx) {
326         SmallVector<Register, 2> DstRegs;
327         for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
328              ++j, ++DefIdx)
329           DstRegs.push_back(MI.getOperand(DefIdx).getReg());
330 
331         if (ConvertOp) {
332           SmallVector<Register, 2> TmpRegs;
333           // This is a vector that is being scalarized and casted. Extract to
334           // the element type, and do the conversion on the scalars.
335           LLT MergeEltTy =
336               MRI.getType(MergeI->getOperand(0).getReg()).getElementType();
337           for (unsigned j = 0; j < NumMergeRegs; ++j)
338             TmpRegs.push_back(MRI.createGenericVirtualRegister(MergeEltTy));
339 
340           Builder.buildUnmerge(TmpRegs, MergeI->getOperand(Idx + 1).getReg());
341 
342           for (unsigned j = 0; j < NumMergeRegs; ++j)
343             Builder.buildInstr(ConvertOp, {DstRegs[j]}, {TmpRegs[j]});
344         } else {
345           Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
346         }
347         UpdatedDefs.append(DstRegs.begin(), DstRegs.end());
348       }
349 
350     } else if (NumMergeRegs > NumDefs) {
351       if (ConvertOp != 0 || NumMergeRegs % NumDefs != 0)
352         return false;
353 
354       Builder.setInstr(MI);
355       // Transform to MERGEs
356       //   %6 = G_MERGE_VALUES %17, %18, %19, %20
357       //   %7, %8 = G_UNMERGE_VALUES %6
358       // to
359       //   %7 = G_MERGE_VALUES %17, %18
360       //   %8 = G_MERGE_VALUES %19, %20
361 
362       const unsigned NumRegs = NumMergeRegs / NumDefs;
363       for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
364         SmallVector<Register, 2> Regs;
365         for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs;
366              ++j, ++Idx)
367           Regs.push_back(MergeI->getOperand(Idx).getReg());
368 
369         Register DefReg = MI.getOperand(DefIdx).getReg();
370         Builder.buildMerge(DefReg, Regs);
371         UpdatedDefs.push_back(DefReg);
372       }
373 
374     } else {
375       LLT MergeSrcTy = MRI.getType(MergeI->getOperand(1).getReg());
376 
377       if (!ConvertOp && DestTy != MergeSrcTy)
378         ConvertOp = TargetOpcode::G_BITCAST;
379 
380       if (ConvertOp) {
381         Builder.setInstr(MI);
382 
383         for (unsigned Idx = 0; Idx < NumDefs; ++Idx) {
384           Register MergeSrc = MergeI->getOperand(Idx + 1).getReg();
385           Register DefReg = MI.getOperand(Idx).getReg();
386           Builder.buildInstr(ConvertOp, {DefReg}, {MergeSrc});
387           UpdatedDefs.push_back(DefReg);
388         }
389 
390         markInstAndDefDead(MI, *MergeI, DeadInsts);
391         return true;
392       }
393 
394       assert(DestTy == MergeSrcTy &&
395              "Bitcast and the other kinds of conversions should "
396              "have happened earlier");
397 
398       for (unsigned Idx = 0; Idx < NumDefs; ++Idx) {
399         Register NewDef = MergeI->getOperand(Idx + 1).getReg();
400         MRI.replaceRegWith(MI.getOperand(Idx).getReg(), NewDef);
401         UpdatedDefs.push_back(NewDef);
402       }
403     }
404 
405     markInstAndDefDead(MI, *MergeI, DeadInsts);
406     return true;
407   }
408 
409   static bool isMergeLikeOpcode(unsigned Opc) {
410     switch (Opc) {
411     case TargetOpcode::G_MERGE_VALUES:
412     case TargetOpcode::G_BUILD_VECTOR:
413     case TargetOpcode::G_CONCAT_VECTORS:
414       return true;
415     default:
416       return false;
417     }
418   }
419 
420   bool tryCombineExtract(MachineInstr &MI,
421                          SmallVectorImpl<MachineInstr *> &DeadInsts,
422                          SmallVectorImpl<Register> &UpdatedDefs) {
423     assert(MI.getOpcode() == TargetOpcode::G_EXTRACT);
424 
425     // Try to use the source registers from a G_MERGE_VALUES
426     //
427     // %2 = G_MERGE_VALUES %0, %1
428     // %3 = G_EXTRACT %2, N
429     // =>
430     //
431     // for N < %2.getSizeInBits() / 2
432     //     %3 = G_EXTRACT %0, N
433     //
434     // for N >= %2.getSizeInBits() / 2
435     //    %3 = G_EXTRACT %1, (N - %0.getSizeInBits()
436 
437     Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
438     MachineInstr *MergeI = MRI.getVRegDef(SrcReg);
439     if (!MergeI || !isMergeLikeOpcode(MergeI->getOpcode()))
440       return false;
441 
442     Register DstReg = MI.getOperand(0).getReg();
443     LLT DstTy = MRI.getType(DstReg);
444     LLT SrcTy = MRI.getType(SrcReg);
445 
446     // TODO: Do we need to check if the resulting extract is supported?
447     unsigned ExtractDstSize = DstTy.getSizeInBits();
448     unsigned Offset = MI.getOperand(2).getImm();
449     unsigned NumMergeSrcs = MergeI->getNumOperands() - 1;
450     unsigned MergeSrcSize = SrcTy.getSizeInBits() / NumMergeSrcs;
451     unsigned MergeSrcIdx = Offset / MergeSrcSize;
452 
453     // Compute the offset of the last bit the extract needs.
454     unsigned EndMergeSrcIdx = (Offset + ExtractDstSize - 1) / MergeSrcSize;
455 
456     // Can't handle the case where the extract spans multiple inputs.
457     if (MergeSrcIdx != EndMergeSrcIdx)
458       return false;
459 
460     // TODO: We could modify MI in place in most cases.
461     Builder.setInstr(MI);
462     Builder.buildExtract(DstReg, MergeI->getOperand(MergeSrcIdx + 1).getReg(),
463                          Offset - MergeSrcIdx * MergeSrcSize);
464     UpdatedDefs.push_back(DstReg);
465     markInstAndDefDead(MI, *MergeI, DeadInsts);
466     return true;
467   }
468 
469   /// Try to combine away MI.
470   /// Returns true if it combined away the MI.
471   /// Adds instructions that are dead as a result of the combine
472   /// into DeadInsts, which can include MI.
473   bool tryCombineInstruction(MachineInstr &MI,
474                              SmallVectorImpl<MachineInstr *> &DeadInsts,
475                              GISelObserverWrapper &WrapperObserver) {
476     // This might be a recursive call, and we might have DeadInsts already
477     // populated. To avoid bad things happening later with multiple vreg defs
478     // etc, process the dead instructions now if any.
479     if (!DeadInsts.empty())
480       deleteMarkedDeadInsts(DeadInsts, WrapperObserver);
481 
482     // Put here every vreg that was redefined in such a way that it's at least
483     // possible that one (or more) of its users (immediate or COPY-separated)
484     // could become artifact combinable with the new definition (or the
485     // instruction reachable from it through a chain of copies if any).
486     SmallVector<Register, 4> UpdatedDefs;
487     bool Changed = false;
488     switch (MI.getOpcode()) {
489     default:
490       return false;
491     case TargetOpcode::G_ANYEXT:
492       Changed = tryCombineAnyExt(MI, DeadInsts, UpdatedDefs);
493       break;
494     case TargetOpcode::G_ZEXT:
495       Changed = tryCombineZExt(MI, DeadInsts, UpdatedDefs);
496       break;
497     case TargetOpcode::G_SEXT:
498       Changed = tryCombineSExt(MI, DeadInsts, UpdatedDefs);
499       break;
500     case TargetOpcode::G_UNMERGE_VALUES:
501       Changed = tryCombineMerges(MI, DeadInsts, UpdatedDefs);
502       break;
503     case TargetOpcode::G_EXTRACT:
504       Changed = tryCombineExtract(MI, DeadInsts, UpdatedDefs);
505       break;
506     case TargetOpcode::G_TRUNC:
507       Changed = tryCombineTrunc(MI, DeadInsts, UpdatedDefs);
508       if (!Changed) {
509         // Try to combine truncates away even if they are legal. As all artifact
510         // combines at the moment look only "up" the def-use chains, we achieve
511         // that by throwing truncates' users (with look through copies) into the
512         // ArtifactList again.
513         UpdatedDefs.push_back(MI.getOperand(0).getReg());
514       }
515       break;
516     }
517     // If the main loop through the ArtifactList found at least one combinable
518     // pair of artifacts, not only combine it away (as done above), but also
519     // follow the def-use chain from there to combine everything that can be
520     // combined within this def-use chain of artifacts.
521     while (!UpdatedDefs.empty()) {
522       Register NewDef = UpdatedDefs.pop_back_val();
523       assert(NewDef.isVirtual() && "Unexpected redefinition of a physreg");
524       for (MachineInstr &Use : MRI.use_instructions(NewDef)) {
525         switch (Use.getOpcode()) {
526         // Keep this list in sync with the list of all artifact combines.
527         case TargetOpcode::G_ANYEXT:
528         case TargetOpcode::G_ZEXT:
529         case TargetOpcode::G_SEXT:
530         case TargetOpcode::G_UNMERGE_VALUES:
531         case TargetOpcode::G_EXTRACT:
532         case TargetOpcode::G_TRUNC:
533           // Adding Use to ArtifactList.
534           WrapperObserver.changedInstr(Use);
535           break;
536         case TargetOpcode::COPY: {
537           Register Copy = Use.getOperand(0).getReg();
538           if (Copy.isVirtual())
539             UpdatedDefs.push_back(Copy);
540           break;
541         }
542         default:
543           // If we do not have an artifact combine for the opcode, there is no
544           // point in adding it to the ArtifactList as nothing interesting will
545           // be done to it anyway.
546           break;
547         }
548       }
549     }
550     return Changed;
551   }
552 
553 private:
554   static unsigned getArtifactSrcReg(const MachineInstr &MI) {
555     switch (MI.getOpcode()) {
556     case TargetOpcode::COPY:
557     case TargetOpcode::G_TRUNC:
558     case TargetOpcode::G_ZEXT:
559     case TargetOpcode::G_ANYEXT:
560     case TargetOpcode::G_SEXT:
561     case TargetOpcode::G_UNMERGE_VALUES:
562       return MI.getOperand(MI.getNumOperands() - 1).getReg();
563     case TargetOpcode::G_EXTRACT:
564       return MI.getOperand(1).getReg();
565     default:
566       llvm_unreachable("Not a legalization artifact happen");
567     }
568   }
569 
570   /// Mark MI as dead. If a def of one of MI's operands, DefMI, would also be
571   /// dead due to MI being killed, then mark DefMI as dead too.
572   /// Some of the combines (extends(trunc)), try to walk through redundant
573   /// copies in between the extends and the truncs, and this attempts to collect
574   /// the in between copies if they're dead.
575   void markInstAndDefDead(MachineInstr &MI, MachineInstr &DefMI,
576                           SmallVectorImpl<MachineInstr *> &DeadInsts) {
577     DeadInsts.push_back(&MI);
578 
579     // Collect all the copy instructions that are made dead, due to deleting
580     // this instruction. Collect all of them until the Trunc(DefMI).
581     // Eg,
582     // %1(s1) = G_TRUNC %0(s32)
583     // %2(s1) = COPY %1(s1)
584     // %3(s1) = COPY %2(s1)
585     // %4(s32) = G_ANYEXT %3(s1)
586     // In this case, we would have replaced %4 with a copy of %0,
587     // and as a result, %3, %2, %1 are dead.
588     MachineInstr *PrevMI = &MI;
589     while (PrevMI != &DefMI) {
590       unsigned PrevRegSrc = getArtifactSrcReg(*PrevMI);
591 
592       MachineInstr *TmpDef = MRI.getVRegDef(PrevRegSrc);
593       if (MRI.hasOneUse(PrevRegSrc)) {
594         if (TmpDef != &DefMI) {
595           assert((TmpDef->getOpcode() == TargetOpcode::COPY ||
596                   isArtifactCast(TmpDef->getOpcode())) &&
597                  "Expecting copy or artifact cast here");
598 
599           DeadInsts.push_back(TmpDef);
600         }
601       } else
602         break;
603       PrevMI = TmpDef;
604     }
605     if (PrevMI == &DefMI && MRI.hasOneUse(DefMI.getOperand(0).getReg()))
606       DeadInsts.push_back(&DefMI);
607   }
608 
609   /// Erase the dead instructions in the list and call the observer hooks.
610   /// Normally the Legalizer will deal with erasing instructions that have been
611   /// marked dead. However, for the trunc(ext(x)) cases we can end up trying to
612   /// process instructions which have been marked dead, but otherwise break the
613   /// MIR by introducing multiple vreg defs. For those cases, allow the combines
614   /// to explicitly delete the instructions before we run into trouble.
615   void deleteMarkedDeadInsts(SmallVectorImpl<MachineInstr *> &DeadInsts,
616                              GISelObserverWrapper &WrapperObserver) {
617     for (auto *DeadMI : DeadInsts) {
618       LLVM_DEBUG(dbgs() << *DeadMI << "Is dead, eagerly deleting\n");
619       WrapperObserver.erasingInstr(*DeadMI);
620       DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
621     }
622     DeadInsts.clear();
623   }
624 
625   /// Checks if the target legalizer info has specified anything about the
626   /// instruction, or if unsupported.
627   bool isInstUnsupported(const LegalityQuery &Query) const {
628     using namespace LegalizeActions;
629     auto Step = LI.getAction(Query);
630     return Step.Action == Unsupported || Step.Action == NotFound;
631   }
632 
633   bool isInstLegal(const LegalityQuery &Query) const {
634     return LI.getAction(Query).Action == LegalizeActions::Legal;
635   }
636 
637   bool isConstantUnsupported(LLT Ty) const {
638     if (!Ty.isVector())
639       return isInstUnsupported({TargetOpcode::G_CONSTANT, {Ty}});
640 
641     LLT EltTy = Ty.getElementType();
642     return isInstUnsupported({TargetOpcode::G_CONSTANT, {EltTy}}) ||
643            isInstUnsupported({TargetOpcode::G_BUILD_VECTOR, {Ty, EltTy}});
644   }
645 
646   /// Looks through copy instructions and returns the actual
647   /// source register.
648   unsigned lookThroughCopyInstrs(Register Reg) {
649     Register TmpReg;
650     while (mi_match(Reg, MRI, m_Copy(m_Reg(TmpReg)))) {
651       if (MRI.getType(TmpReg).isValid())
652         Reg = TmpReg;
653       else
654         break;
655     }
656     return Reg;
657   }
658 };
659 
660 } // namespace llvm
661