[Legalizer] Making artifact combining order-independent

[rtereshin]

Summary

Legalization algorithm is complicated by two facts:

1. While regular instructions should be possible to legalize in an isolated, per-instruction, context-free manner, legalization artifacts can only be eliminated in pairs, which could be deeply, and ultimately arbitrary nested: { [ () ] }, where which paranthesis kind depicts an artifact kind, like extend, unmerge, etc. Such structure can only be fully eliminated by simple local combines if they are attempted in a particular order (inside out), or alternatively by repeated scans each eliminating only one innermost pair, resulting in O(n^2) complexity.
2. Some artifacts might in fact be regular instructions that could (and sometimes should) be legalized by the target-specific rules. Which means failure to eliminate all artifacts on the first iteration is not a failure, they need to be tried as instructions, which may produce more artifacts, including the ones that are in fact regular instructions, resulting in a non-constant number of iterations required to finish the process.

I trust the recently introduced termination condition (no new artifacts
were created during as-a-regular-instruction-retrial of artifacts not
eliminated on the previous iteration) to be efficient in providing
termination, but only performing the legalization in full if and only if
at each step such chains of artifacts are successfully eliminated in
full as well.

Which is currently not guaranteed, as the artifact combines are applied
only once and in an arbitrary order that has to do with the order of
creation or insertion of artifacts into their worklist, which is a no
particular order.

In this patch I make a small change to the artifact combiner, making it
to re-insert into the worklist immediate (modulo a look-through copies)
artifact users of each vreg that changes its definition due to an
artifact combine.

Here the first scan through the artifacts worklist, while not
being done in any guaranteed order, only needs to find the innermost
pair(s) of artifacts that could be immediately combined out. After that
the process follows def-use chains, making them shorter at each step, thus
combining everything that can be combined in O(n) time.

[aditya_nandakumar]

Looks like a reasonable change to me - LGTM . Maybe wait a couple days for others to give feedback.

[rtereshin]

missed a test case update (arm64-fallback.ll)

[rtereshin]

Adding // Adding Use to ArtifactList. comment in front of WrapperObserver.changedInstr(Use); as requested, NFC.

[paquette]

LGTM aside from some places where a couple comments can be added.

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

481

Can we have a comment explaining what the purpose of UpdatedDefs is?

E.g. "Store the refs that were changed by a combine, so that we can..."

507–508

It's not immediately obvious to me why this is only happening for G_TRUNC. A comment would be helpful here. :)

516

A comment explaining what you're doing here at a high level would be nice too.

[rtereshin]

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

481

Sure! I'll come up with something shortly.

516

Not entirely sure how would I shape it. You mean repeating all the same stuff described in the commit message and the test?

[rtereshin]

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

481

diff --git a/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h b/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
index 3946f2ff0af..58d76fc56ff 100644
--- a/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
+++ b/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
@@ -478,6 +478,10 @@ public:
     if (!DeadInsts.empty())
       deleteMarkedDeadInsts(DeadInsts, WrapperObserver);
 
+    // Put here every vreg that was redefined in such a way that it's at least
+    // possible that one (or more) of its users (immediate or COPY-separated)
+    // could become artifact combinable with the new definition (or the
+    // instruction reachable from it through a chain of copies if any).
     SmallVector<Register, 4> UpdatedDefs;
     bool Changed = false;
     switch (MI.getOpcode()) {

507–508

I believe I'm applying to G_TRUNC here the same change I'm applying to every other opcode. It looks different because the logic the change is applied to is different for G_TRUNC.

That difference seems to stem mostly from 2 prior commits:

1. https://github.com/llvm/llvm-project/commit/e6201c8724dbce94969bc0b7f81e950cdbb6f742 ("[GISel]: Rework legalization algorithm for better elimination of" by @aditya_nandakumar)
2. https://github.com/llvm/llvm-project/commit/a5376f6322132e3b0664de55348f6bbba1fabd00 ("[GlobalISel][AArch64][AMDGPU][X86] Teach LegalizationArtifactCombiner to combine trunc(g_constant)." by @craig.topper)

(1) is of most interest here. It looks like prior to the current patch being reviewed here this behavior (re-visiting the users of G_TRUNC) was needed for the legalization algorithm to work for similar reasons to what I'm driven by here in this patch.

There is also an interesting statement in (1)'s commit message:

Currently, the target needs to say all combinations of extends and truncs are legal

I think with this patch here we finally completely eliminate that requirement, but targets (most notably AMDGPU @arsenm) seem to still have it in their legalization rules, e.g. claiming that a trunc to s8 is legal, while it's actually not. What that leads to is that if I remove this special logic for G_TRUNC, the legalization for AMDGPU produces quite a bit of truncates to s8 and extends from s8 (and s1 even more so), which is technically correct because all of those are declared by the target as legal. Not a single test fails to legalize or select either, so those truncates and extends are either getting combined out after the legalization, or AMDGPU is missing integration tests running the entire GlobalISel, or I'm mistaken and those are in fact actually legal and can be selected, I just don't know. I definitely intend to let the targets to figure out what they want to do with that.

There is also a possibility that some targets try to make GlobalISel work with some of the artifacts (e.g. G_TRUNC to s1) being legal in a context-dependent way, only if they are used only by a specific subset of opcodes. Perhaps in such cases that may force them (or seemingly force them) to call such artifacts legal, but they still need them to be combined away in every case when it's possible, even for correctness. Not sure.

There is also another thing here. There are some instructions which can be both combined out or legalized. Technically, the legalizer's job is to just produce legal code. Practically speaking though, provided such an alternative, it's probably better to combine them out instead, as that tends to improve the quality of the code generated *and* improve compile time both. We probably shouldn't try to do such combines (improving both the codegen and compile time) during legalization on purpose and try too hard to find more of them, but if they come naturally around, like I think in this case with G_TRUNC, I wouldn't try too hard to remove them either.

diff --git a/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h b/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
index 58d76fc56ff..7564736f291 100644
--- a/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
+++ b/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
@@ -504,8 +504,13 @@ public:
       break;
     case TargetOpcode::G_TRUNC:
       Changed = tryCombineTrunc(MI, DeadInsts, UpdatedDefs);
-      if (!Changed)
+      if (!Changed) {
+        // Try to combine truncates away even if they are legal. As all artifact
+        // combines at the moment look only "up" the def-use chains, we achieve
+        // that by throwing truncates' users (with look through copies) into the
+        // ArtifactList again.
         UpdatedDefs.push_back(MI.getOperand(0).getReg());
+      }
       break;
     }
     while (!UpdatedDefs.empty()) {

516

Okay, given the commit message, the tests (especially the unit test and the comment in it), I came up with the following comments here in-code, trying to bring some more information to the table instead of just repeating all the same stuff:

diff --git a/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h b/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
index 7564736f291..4c2ab316930 100644
--- a/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
+++ b/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
@@ -513,11 +513,16 @@ public:
       }
       break;
     }
+    // If the main loop through the ArtifactList found at least one combinable
+    // pair of artifacts, not only combine it away (as done above), but also
+    // follow the def-use chain from there to combine everything that can be
+    // combined within this def-use chain of artifacts.
     while (!UpdatedDefs.empty()) {
       Register NewDef = UpdatedDefs.pop_back_val();
       assert(NewDef.isVirtual() && "Unexpected redefinition of a physreg");
       for (MachineInstr &Use : MRI.use_instructions(NewDef)) {
         switch (Use.getOpcode()) {
+        // Keep this list in sync with the list of all artifact combines.
         case TargetOpcode::G_ANYEXT:
         case TargetOpcode::G_ZEXT:
         case TargetOpcode::G_SEXT:
@@ -533,6 +538,11 @@ public:
             UpdatedDefs.push_back(Copy);
           break;
         }
+        default:
+          // If we do not have an artifact combine for the opcode, there is no
+          // point in adding it to the ArtifactList as nothing interesting will
+          // be done to it anyway.
+          break;
         }
       }
     }

Hope that works.

[rtereshin]

Addressing the feedback, NFC.

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

class LegalizationArtifactCombiner {
   }
 
 public:
   LegalizationArtifactCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI,
                     const LegalizerInfo &LI)
       : Builder(B), MRI(MRI), LI(LI) {}
 
   bool tryCombineAnyExt(MachineInstr &MI,
-                        SmallVectorImpl<MachineInstr *> &DeadInsts) {
+                        SmallVectorImpl<MachineInstr *> &DeadInsts,
+                        SmallVectorImpl<Register> &UpdatedDefs) {
     assert(MI.getOpcode() == TargetOpcode::G_ANYEXT);
 
     Builder.setInstr(MI);
     Register DstReg = MI.getOperand(0).getReg();
     Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
 
     // aext(trunc x) - > aext/copy/trunc x
     Register TruncSrc;
     if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
       Builder.buildAnyExtOrTrunc(DstReg, TruncSrc);
+      UpdatedDefs.push_back(DstReg);
       markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
       return true;
     }
 
     // aext([asz]ext x) -> [asz]ext x
     Register ExtSrc;
     MachineInstr *ExtMI;
     if (mi_match(SrcReg, MRI,
                  m_all_of(m_MInstr(ExtMI), m_any_of(m_GAnyExt(m_Reg(ExtSrc)),
                                                     m_GSExt(m_Reg(ExtSrc)),
                                                     m_GZExt(m_Reg(ExtSrc)))))) {
       Builder.buildInstr(ExtMI->getOpcode(), {DstReg}, {ExtSrc});
+      UpdatedDefs.push_back(DstReg);
       markInstAndDefDead(MI, *ExtMI, DeadInsts);
       return true;
     }
 
     // Try to fold aext(g_constant) when the larger constant type is legal.
     // Can't use MIPattern because we don't have a specific constant in mind.
     auto *SrcMI = MRI.getVRegDef(SrcReg);
     if (SrcMI->getOpcode() == TargetOpcode::G_CONSTANT) {
       const LLT &DstTy = MRI.getType(DstReg);
       if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
         auto &CstVal = SrcMI->getOperand(1);
         Builder.buildConstant(
             DstReg, CstVal.getCImm()->getValue().sext(DstTy.getSizeInBits()));
+        UpdatedDefs.push_back(DstReg);
         markInstAndDefDead(MI, *SrcMI, DeadInsts);
         return true;
       }
     }
-    return tryFoldImplicitDef(MI, DeadInsts);
+    return tryFoldImplicitDef(MI, DeadInsts, UpdatedDefs);
   }
 
   bool tryCombineZExt(MachineInstr &MI,
-                      SmallVectorImpl<MachineInstr *> &DeadInsts) {
+                      SmallVectorImpl<MachineInstr *> &DeadInsts,
+                      SmallVectorImpl<Register> &UpdatedDefs) {
     assert(MI.getOpcode() == TargetOpcode::G_ZEXT);
 
     Builder.setInstr(MI);
     Register DstReg = MI.getOperand(0).getReg();
     Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
 
     // zext(trunc x) - > and (aext/copy/trunc x), mask
     Register TruncSrc;
bool tryCombineZExt(MachineInstr &MI,
     // Can't use MIPattern because we don't have a specific constant in mind.
     auto *SrcMI = MRI.getVRegDef(SrcReg);
     if (SrcMI->getOpcode() == TargetOpcode::G_CONSTANT) {
       const LLT &DstTy = MRI.getType(DstReg);
       if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
         auto &CstVal = SrcMI->getOperand(1);
         Builder.buildConstant(
             DstReg, CstVal.getCImm()->getValue().zext(DstTy.getSizeInBits()));
+        UpdatedDefs.push_back(DstReg);
         markInstAndDefDead(MI, *SrcMI, DeadInsts);
         return true;
       }
     }
-    return tryFoldImplicitDef(MI, DeadInsts);
+    return tryFoldImplicitDef(MI, DeadInsts, UpdatedDefs);
   }
 
   bool tryCombineSExt(MachineInstr &MI,
-                      SmallVectorImpl<MachineInstr *> &DeadInsts) {
+                      SmallVectorImpl<MachineInstr *> &DeadInsts,
+                      SmallVectorImpl<Register> &UpdatedDefs) {
     assert(MI.getOpcode() == TargetOpcode::G_SEXT);
 
     Builder.setInstr(MI);
     Register DstReg = MI.getOperand(0).getReg();
     Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
 
     // sext(trunc x) - > (sext_inreg (aext/copy/trunc x), c)
     Register TruncSrc;
     if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
       LLT DstTy = MRI.getType(DstReg);
       if (isInstUnsupported({TargetOpcode::G_SEXT_INREG, {DstTy}}))
         return false;
       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
       LLT SrcTy = MRI.getType(SrcReg);
       uint64_t SizeInBits = SrcTy.getScalarSizeInBits();
       Builder.buildInstr(
           TargetOpcode::G_SEXT_INREG, {DstReg},
           {Builder.buildAnyExtOrTrunc(DstTy, TruncSrc), SizeInBits});
       markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
       return true;
     }
-    return tryFoldImplicitDef(MI, DeadInsts);
+    return tryFoldImplicitDef(MI, DeadInsts, UpdatedDefs);
   }
 
   bool tryCombineTrunc(MachineInstr &MI,
-                       SmallVectorImpl<MachineInstr *> &DeadInsts) {
+                       SmallVectorImpl<MachineInstr *> &DeadInsts,
+                       SmallVectorImpl<Register> &UpdatedDefs) {
     assert(MI.getOpcode() == TargetOpcode::G_TRUNC);
 
     Builder.setInstr(MI);
     Register DstReg = MI.getOperand(0).getReg();
     Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
 
     // Try to fold trunc(g_constant) when the smaller constant type is legal.
     // Can't use MIPattern because we don't have a specific constant in mind.
     auto *SrcMI = MRI.getVRegDef(SrcReg);
     if (SrcMI->getOpcode() == TargetOpcode::G_CONSTANT) {
       const LLT &DstTy = MRI.getType(DstReg);
       if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
         auto &CstVal = SrcMI->getOperand(1);
         Builder.buildConstant(
             DstReg, CstVal.getCImm()->getValue().trunc(DstTy.getSizeInBits()));
+        UpdatedDefs.push_back(DstReg);
         markInstAndDefDead(MI, *SrcMI, DeadInsts);
         return true;
       }
     }
 
     return false;
   }
 
-
   /// Try to fold G_[ASZ]EXT (G_IMPLICIT_DEF).
   bool tryFoldImplicitDef(MachineInstr &MI,
-                          SmallVectorImpl<MachineInstr *> &DeadInsts) {
+                          SmallVectorImpl<MachineInstr *> &DeadInsts,
+                          SmallVectorImpl<Register> &UpdatedDefs) {
     unsigned Opcode = MI.getOpcode();
     assert(Opcode == TargetOpcode::G_ANYEXT || Opcode == TargetOpcode::G_ZEXT ||
            Opcode == TargetOpcode::G_SEXT);
 
     if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
                                            MI.getOperand(1).getReg(), MRI)) {
       Builder.setInstr(MI);
       Register DstReg = MI.getOperand(0).getReg();
       LLT DstTy = MRI.getType(DstReg);
 
       if (Opcode == TargetOpcode::G_ANYEXT) {
         // G_ANYEXT (G_IMPLICIT_DEF) -> G_IMPLICIT_DEF
         if (isInstUnsupported({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
           return false;
         LLVM_DEBUG(dbgs() << ".. Combine G_ANYEXT(G_IMPLICIT_DEF): " << MI;);
         Builder.buildInstr(TargetOpcode::G_IMPLICIT_DEF, {DstReg}, {});
+        UpdatedDefs.push_back(DstReg);
       } else {
         // G_[SZ]EXT (G_IMPLICIT_DEF) -> G_CONSTANT 0 because the top
         // bits will be 0 for G_ZEXT and 0/1 for the G_SEXT.
         if (isConstantUnsupported(DstTy))
           return false;
         LLVM_DEBUG(dbgs() << ".. Combine G_[SZ]EXT(G_IMPLICIT_DEF): " << MI;);
         Builder.buildConstant(DstReg, 0);
+        UpdatedDefs.push_back(DstReg);
       }
 
       markInstAndDefDead(MI, *DefMI, DeadInsts);
       return true;
     }
     return false;
   }
 
case TargetOpcode::G_CONCAT_VECTORS: {
       if (ConvertOp == TargetOpcode::G_TRUNC)
         return DestTy.getSizeInBits() <= OpEltSize;
       return DestTy.getSizeInBits() >= OpEltSize;
     }
     }
   }
 
   bool tryCombineMerges(MachineInstr &MI,
-                        SmallVectorImpl<MachineInstr *> &DeadInsts) {
+                        SmallVectorImpl<MachineInstr *> &DeadInsts,
+                        SmallVectorImpl<Register> &UpdatedDefs) {
     assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES);
 
     unsigned NumDefs = MI.getNumOperands() - 1;
     MachineInstr *SrcDef =
         getDefIgnoringCopies(MI.getOperand(NumDefs).getReg(), MRI);
     if (!SrcDef)
       return false;
 
if (NumMergeRegs < NumDefs) {
         for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
              ++j, ++DefIdx)
           DstRegs.push_back(MI.getOperand(DefIdx).getReg());
 
         if (ConvertOp) {
           SmallVector<Register, 2> TmpRegs;
           // This is a vector that is being scalarized and casted. Extract to
           // the element type, and do the conversion on the scalars.
-          LLT MergeEltTy
-            = MRI.getType(MergeI->getOperand(0).getReg()).getElementType();
+          LLT MergeEltTy =
+              MRI.getType(MergeI->getOperand(0).getReg()).getElementType();
           for (unsigned j = 0; j < NumMergeRegs; ++j)
             TmpRegs.push_back(MRI.createGenericVirtualRegister(MergeEltTy));
 
           Builder.buildUnmerge(TmpRegs, MergeI->getOperand(Idx + 1).getReg());
 
           for (unsigned j = 0; j < NumMergeRegs; ++j)
             Builder.buildInstr(ConvertOp, {DstRegs[j]}, {TmpRegs[j]});
         } else {
           Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
         }
+        UpdatedDefs.append(DstRegs.begin(), DstRegs.end());
       }
 
     } else if (NumMergeRegs > NumDefs) {
       if (ConvertOp != 0 || NumMergeRegs % NumDefs != 0)
         return false;
 
       Builder.setInstr(MI);
       // Transform to MERGEs
       //   %6 = G_MERGE_VALUES %17, %18, %19, %20
       //   %7, %8 = G_UNMERGE_VALUES %6
       // to
       //   %7 = G_MERGE_VALUES %17, %18
       //   %8 = G_MERGE_VALUES %19, %20
 
       const unsigned NumRegs = NumMergeRegs / NumDefs;
       for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
         SmallVector<Register, 2> Regs;
         for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs;
              ++j, ++Idx)
           Regs.push_back(MergeI->getOperand(Idx).getReg());
 
-        Builder.buildMerge(MI.getOperand(DefIdx).getReg(), Regs);
+        Register DefReg = MI.getOperand(DefIdx).getReg();
+        Builder.buildMerge(DefReg, Regs);
+        UpdatedDefs.push_back(DefReg);
       }
 
     } else {
       LLT MergeSrcTy = MRI.getType(MergeI->getOperand(1).getReg());
 
       if (!ConvertOp && DestTy != MergeSrcTy)
         ConvertOp = TargetOpcode::G_BITCAST;
 
       if (ConvertOp) {
         Builder.setInstr(MI);
 
         for (unsigned Idx = 0; Idx < NumDefs; ++Idx) {
           Register MergeSrc = MergeI->getOperand(Idx + 1).getReg();
-          Builder.buildInstr(ConvertOp, {MI.getOperand(Idx).getReg()},
-                             {MergeSrc});
+          Register DefReg = MI.getOperand(Idx).getReg();
+          Builder.buildInstr(ConvertOp, {DefReg}, {MergeSrc});
+          UpdatedDefs.push_back(DefReg);
         }
 
         markInstAndDefDead(MI, *MergeI, DeadInsts);
         return true;
       }
 
       assert(DestTy == MergeSrcTy &&
              "Bitcast and the other kinds of conversions should "
              "have happened earlier");
 
-      for (unsigned Idx = 0; Idx < NumDefs; ++Idx)
-        MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
-                           MergeI->getOperand(Idx + 1).getReg());
+      for (unsigned Idx = 0; Idx < NumDefs; ++Idx) {
+        Register NewDef = MergeI->getOperand(Idx + 1).getReg();
+        MRI.replaceRegWith(MI.getOperand(Idx).getReg(), NewDef);
+        UpdatedDefs.push_back(NewDef);
+      }
     }
 
     markInstAndDefDead(MI, *MergeI, DeadInsts);
     return true;
   }
 
   static bool isMergeLikeOpcode(unsigned Opc) {
     switch (Opc) {
     case TargetOpcode::G_MERGE_VALUES:
     case TargetOpcode::G_BUILD_VECTOR:
     case TargetOpcode::G_CONCAT_VECTORS:
       return true;
     default:
       return false;
     }
   }
 
   bool tryCombineExtract(MachineInstr &MI,
-                         SmallVectorImpl<MachineInstr *> &DeadInsts) {
+                         SmallVectorImpl<MachineInstr *> &DeadInsts,
+                         SmallVectorImpl<Register> &UpdatedDefs) {
     assert(MI.getOpcode() == TargetOpcode::G_EXTRACT);
 
     // Try to use the source registers from a G_MERGE_VALUES
     //
     // %2 = G_MERGE_VALUES %0, %1
     // %3 = G_EXTRACT %2, N
     // =>
     //
     // for N < %2.getSizeInBits() / 2
     //     %3 = G_EXTRACT %0, N
     //
     // for N >= %2.getSizeInBits() / 2
     //    %3 = G_EXTRACT %1, (N - %0.getSizeInBits()
 
-    unsigned Src = lookThroughCopyInstrs(MI.getOperand(1).getReg());
-    MachineInstr *MergeI = MRI.getVRegDef(Src);
+    Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
+    MachineInstr *MergeI = MRI.getVRegDef(SrcReg);
     if (!MergeI || !isMergeLikeOpcode(MergeI->getOpcode()))
       return false;
 
-    LLT DstTy = MRI.getType(MI.getOperand(0).getReg());
-    LLT SrcTy = MRI.getType(Src);
+    Register DstReg = MI.getOperand(0).getReg();
+    LLT DstTy = MRI.getType(DstReg);
+    LLT SrcTy = MRI.getType(SrcReg);
 
     // TODO: Do we need to check if the resulting extract is supported?
     unsigned ExtractDstSize = DstTy.getSizeInBits();
     unsigned Offset = MI.getOperand(2).getImm();
     unsigned NumMergeSrcs = MergeI->getNumOperands() - 1;
     unsigned MergeSrcSize = SrcTy.getSizeInBits() / NumMergeSrcs;
     unsigned MergeSrcIdx = Offset / MergeSrcSize;
 
     // Compute the offset of the last bit the extract needs.
     unsigned EndMergeSrcIdx = (Offset + ExtractDstSize - 1) / MergeSrcSize;
 
     // Can't handle the case where the extract spans multiple inputs.
     if (MergeSrcIdx != EndMergeSrcIdx)
       return false;
 
     // TODO: We could modify MI in place in most cases.
     Builder.setInstr(MI);
-    Builder.buildExtract(
-      MI.getOperand(0).getReg(),
-      MergeI->getOperand(MergeSrcIdx + 1).getReg(),
+    Builder.buildExtract(DstReg, MergeI->getOperand(MergeSrcIdx + 1).getReg(),
                          Offset - MergeSrcIdx * MergeSrcSize);
+    UpdatedDefs.push_back(DstReg);
     markInstAndDefDead(MI, *MergeI, DeadInsts);
     return true;
   }
 
   /// Try to combine away MI.
   /// Returns true if it combined away the MI.
   /// Adds instructions that are dead as a result of the combine
   /// into DeadInsts, which can include MI.
   bool tryCombineInstruction(MachineInstr &MI,
                              SmallVectorImpl<MachineInstr *> &DeadInsts,
                              GISelObserverWrapper &WrapperObserver) {
     // This might be a recursive call, and we might have DeadInsts already
     // populated. To avoid bad things happening later with multiple vreg defs
     // etc, process the dead instructions now if any.
     if (!DeadInsts.empty())
       deleteMarkedDeadInsts(DeadInsts, WrapperObserver);
+
+    // Put here every vreg that was redefined in such a way that it's at least
+    // possible that one (or more) of its users (immediate or COPY-separated)
+    // could become artifact combinable with the new definition (or the
+    // instruction reachable from it through a chain of copies if any).
+    SmallVector<Register, 4> UpdatedDefs;
+    bool Changed = false;
     switch (MI.getOpcode()) {
     default:
       return false;
     case TargetOpcode::G_ANYEXT:
-      return tryCombineAnyExt(MI, DeadInsts);
+      Changed = tryCombineAnyExt(MI, DeadInsts, UpdatedDefs);
+      break;
+    case TargetOpcode::G_ZEXT:
+      Changed = tryCombineZExt(MI, DeadInsts, UpdatedDefs);
+      break;
+    case TargetOpcode::G_SEXT:
+      Changed = tryCombineSExt(MI, DeadInsts, UpdatedDefs);
+      break;
+    case TargetOpcode::G_UNMERGE_VALUES:
+      Changed = tryCombineMerges(MI, DeadInsts, UpdatedDefs);
+      break;
+    case TargetOpcode::G_EXTRACT:
+      Changed = tryCombineExtract(MI, DeadInsts, UpdatedDefs);
+      break;
+    case TargetOpcode::G_TRUNC:
+      Changed = tryCombineTrunc(MI, DeadInsts, UpdatedDefs);
+      if (!Changed) {
+        // Try to combine truncates away even if they are legal. As all artifact
+        // combines at the moment look only "up" the def-use chains, we achieve
+        // that by throwing truncates' users (with look through copies) into the
+        // ArtifactList again.
+        UpdatedDefs.push_back(MI.getOperand(0).getReg());
+      }
+      break;
+    }
+    // If the main loop through the ArtifactList found at least one combinable
+    // pair of artifacts, not only combine it away (as done above), but also
+    // follow the def-use chain from there to combine everything that can be
+    // combined within this def-use chain of artifacts.
+    while (!UpdatedDefs.empty()) {
+      Register NewDef = UpdatedDefs.pop_back_val();
+      assert(NewDef.isVirtual() && "Unexpected redefinition of a physreg");
+      for (MachineInstr &Use : MRI.use_instructions(NewDef)) {
+        switch (Use.getOpcode()) {
+        // Keep this list in sync with the list of all artifact combines.
+        case TargetOpcode::G_ANYEXT:
         case TargetOpcode::G_ZEXT:
-      return tryCombineZExt(MI, DeadInsts);
         case TargetOpcode::G_SEXT:
-      return tryCombineSExt(MI, DeadInsts);
         case TargetOpcode::G_UNMERGE_VALUES:
-      return tryCombineMerges(MI, DeadInsts);
         case TargetOpcode::G_EXTRACT:
-      return tryCombineExtract(MI, DeadInsts);
-    case TargetOpcode::G_TRUNC: {
-      if (tryCombineTrunc(MI, DeadInsts))
-        return true;
-
-      bool Changed = false;
-      for (auto &Use : MRI.use_instructions(MI.getOperand(0).getReg()))
-        Changed |= tryCombineInstruction(Use, DeadInsts, WrapperObserver);
-      return Changed;
+        case TargetOpcode::G_TRUNC:
+          // Adding Use to ArtifactList.
+          WrapperObserver.changedInstr(Use);
+          break;
+        case TargetOpcode::COPY: {
+          Register Copy = Use.getOperand(0).getReg();
+          if (Copy.isVirtual())
+            UpdatedDefs.push_back(Copy);
+          break;
+        }
+        default:
+          // If we do not have an artifact combine for the opcode, there is no
+          // point in adding it to the ArtifactList as nothing interesting will
+          // be done to it anyway.
+          break;
         }
       }
     }
+    return Changed;
+  }
 
 private:
-
   static unsigned getArtifactSrcReg(const MachineInstr &MI) {
     switch (MI.getOpcode()) {
     case TargetOpcode::COPY:
     case TargetOpcode::G_TRUNC:
     case TargetOpcode::G_ZEXT:
     case TargetOpcode::G_ANYEXT:
     case TargetOpcode::G_SEXT:
     case TargetOpcode::G_UNMERGE_VALUES:

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

while (!InstList.empty()) {
       // Error out if we couldn't legalize this instruction. We may want to
       // fall back to DAG ISel instead in the future.
       if (Res == LegalizerHelper::UnableToLegalize) {
         // Move illegal artifacts to RetryList instead of aborting because
         // legalizing InstList may generate artifacts that allow
         // ArtifactCombiner to combine away them.
         if (isArtifact(MI)) {
           LLVM_DEBUG(dbgs() << ".. Not legalized, moving to artifacts retry\n");
+          assert(NumArtifacts == 0 &&
+                 "Artifacts are only expected in instruction list starting the "
+                 "second iteration, but each iteration starting second must "
+                 "start with an empty artifacts list");
+          (void)NumArtifacts;
           RetryList.push_back(&MI);
           continue;
         }
         Helper.MIRBuilder.stopObservingChanges();
         return {Changed, &MI};
       }
       WorkListObserver.printNewInstrs();
       Changed |= Res == LegalizerHelper::Legalized;
     }
     // Try to combine the instructions in RetryList again if there
     // are new artifacts. If not, stop legalizing.
     if (!RetryList.empty()) {
-      if (ArtifactList.size() > NumArtifacts) {
+      if (!ArtifactList.empty()) {
         while (!RetryList.empty())
           ArtifactList.insert(RetryList.pop_back_val());
       } else {
         LLVM_DEBUG(dbgs() << "No new artifacts created, not retrying!\n");
         Helper.MIRBuilder.stopObservingChanges();
         return {Changed, RetryList.front()};
       }
     }

llvm/lib/Target/Mips/MipsRegisterBankInfo.cpp

void MipsRegisterBankInfo::setRegBank(MachineInstr &MI,
   default:
     llvm_unreachable("Unexpected opcode.");
   }
 }
 
 static void
 combineAwayG_UNMERGE_VALUES(LegalizationArtifactCombiner &ArtCombiner,
                             MachineInstr &MI) {
+  SmallVector<Register, 4> UpdatedDefs;
   SmallVector<MachineInstr *, 2> DeadInstrs;
-  ArtCombiner.tryCombineMerges(MI, DeadInstrs);
+  ArtCombiner.tryCombineMerges(MI, DeadInstrs, UpdatedDefs);
   for (MachineInstr *DeadMI : DeadInstrs)
     DeadMI->eraseFromParent();
 }
 
 void MipsRegisterBankInfo::applyMappingImpl(
     const OperandsMapper &OpdMapper) const {
   MachineInstr &MI = OpdMapper.getMI();
   InstListTy NewInstrs;

llvm/test/CodeGen/AArch64/GlobalISel/arm64-fallback.ll

 ; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for nonpow2_load_narrowing
 ; FALLBACK-WITH-REPORT-OUT-LABEL: nonpow2_load_narrowing:
 define void @nonpow2_load_narrowing() {
   %dummy = load i96, i96* undef
   store i96 %dummy, i96* undef
   ret void
 }
 
-; FALLBACK-WITH-REPORT-ERR: remark: <unknown>:0:0: cannot select: %5:fpr32(s32) = G_EXTRACT %{{[0-9]+}}:fpr(s128), 64 (in function: nonpow2_store_narrowing)
+; FALLBACK-WITH-REPORT-ERR: remark: <unknown>:0:0: cannot select: %14:gpr64(s64), %15:gpr(s1) = G_UADDE %17:gpr, %17:gpr, %13:gpr (in function: nonpow2_store_narrowing)
 ; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for nonpow2_store_narrowing
 ; FALLBACK-WITH-REPORT-OUT-LABEL: nonpow2_store_narrowing:
 define void @nonpow2_store_narrowing(i96* %c) {
   %a = add i128 undef, undef
   %b = trunc i128 %a to i96
   store i96 %b, i96* %c
   ret void
 }

llvm/test/CodeGen/AArch64/GlobalISel/legalize-merge-values.mir

bb.0:
     ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 15
     ; CHECK: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
     ; CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[C2]], [[C1]]
     ; CHECK: [[SHL:%[0-9]+]]:_(s32) = G_SHL [[AND]], [[C]](s32)
     ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY [[C2]](s32)
     ; CHECK: [[AND1:%[0-9]+]]:_(s32) = G_AND [[COPY]], [[C1]]
     ; CHECK: [[COPY1:%[0-9]+]]:_(s32) = COPY [[SHL]](s32)
     ; CHECK: [[OR:%[0-9]+]]:_(s32) = G_OR [[AND1]], [[COPY1]]
-    ; CHECK: [[TRUNC:%[0-9]+]]:_(s8) = G_TRUNC [[OR]](s32)
-    ; CHECK: [[COPY2:%[0-9]+]]:_(s8) = COPY [[TRUNC]](s8)
-    ; CHECK: [[ANYEXT:%[0-9]+]]:_(s64) = G_ANYEXT [[COPY2]](s8)
+    ; CHECK: [[ANYEXT:%[0-9]+]]:_(s64) = G_ANYEXT [[OR]](s32)
     ; CHECK: $x0 = COPY [[ANYEXT]](s64)
     %0:_(s64) = G_CONSTANT i64 0
     %1:_(s4) = G_TRUNC %0
 
     %2:_(s8) = G_MERGE_VALUES %1, %1
     %3:_(s8) = COPY %2
     %4:_(s64) = G_ANYEXT %3
     $x0 = COPY %4
 ...

llvm/test/CodeGen/AArch64/GlobalISel/legalizer-combiner-zext-trunc-crash.mir

body:             |
   ; CHECK:   [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
   ; CHECK:   [[ANYEXT:%[0-9]+]]:_(s32) = G_ANYEXT [[PHI]](s16)
   ; CHECK:   [[AND:%[0-9]+]]:_(s32) = G_AND [[ANYEXT]], [[C]]
   ; CHECK:   [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 46
   ; CHECK:   [[ICMP:%[0-9]+]]:_(s32) = G_ICMP intpred(eq), [[AND]](s32), [[C1]]
   ; CHECK:   [[COPY:%[0-9]+]]:_(s32) = COPY [[ICMP]](s32)
   ; CHECK:   [[DEF1:%[0-9]+]]:_(s32) = G_IMPLICIT_DEF
   ; CHECK:   [[OR:%[0-9]+]]:_(s32) = G_OR [[COPY]], [[DEF1]]
+  ; CHECK:   [[COPY1:%[0-9]+]]:_(s32) = COPY [[ANYEXT]](s32)
   ; CHECK:   [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 -33
-  ; CHECK:   [[AND1:%[0-9]+]]:_(s32) = G_AND [[ANYEXT]], [[C2]]
-  ; CHECK:   [[COPY1:%[0-9]+]]:_(s32) = COPY [[AND1]](s32)
+  ; CHECK:   [[AND1:%[0-9]+]]:_(s32) = G_AND [[COPY1]], [[C2]]
+  ; CHECK:   [[COPY2:%[0-9]+]]:_(s32) = COPY [[AND1]](s32)
   ; CHECK:   [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 -65
-  ; CHECK:   [[ADD:%[0-9]+]]:_(s32) = G_ADD [[COPY1]], [[C3]]
-  ; CHECK:   [[COPY2:%[0-9]+]]:_(s32) = COPY [[ADD]](s32)
-  ; CHECK:   [[AND2:%[0-9]+]]:_(s32) = G_AND [[COPY2]], [[C]]
+  ; CHECK:   [[ADD:%[0-9]+]]:_(s32) = G_ADD [[COPY2]], [[C3]]
+  ; CHECK:   [[COPY3:%[0-9]+]]:_(s32) = COPY [[ADD]](s32)
+  ; CHECK:   [[AND2:%[0-9]+]]:_(s32) = G_AND [[COPY3]], [[C]]
   ; CHECK:   [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 26
   ; CHECK:   [[ICMP1:%[0-9]+]]:_(s32) = G_ICMP intpred(ult), [[AND2]](s32), [[C4]]
-  ; CHECK:   [[COPY3:%[0-9]+]]:_(s32) = COPY [[ICMP1]](s32)
-  ; CHECK:   [[COPY4:%[0-9]+]]:_(s32) = COPY [[OR]](s32)
-  ; CHECK:   [[OR1:%[0-9]+]]:_(s32) = G_OR [[COPY3]], [[COPY4]]
+  ; CHECK:   [[COPY4:%[0-9]+]]:_(s32) = COPY [[ICMP1]](s32)
+  ; CHECK:   [[COPY5:%[0-9]+]]:_(s32) = COPY [[OR]](s32)
+  ; CHECK:   [[OR1:%[0-9]+]]:_(s32) = G_OR [[COPY4]], [[COPY5]]
   ; CHECK:   [[TRUNC:%[0-9]+]]:_(s1) = G_TRUNC [[OR1]](s32)
   ; CHECK:   G_BRCOND [[TRUNC]](s1), %bb.2
   ; CHECK: bb.2:
   ; CHECK:   successors: %bb.1(0x80000000)
   ; CHECK:   [[C5:%[0-9]+]]:_(s16) = G_CONSTANT i16 64
   ; CHECK:   G_BR %bb.1
   bb.1:
     %1:_(s8) = G_CONSTANT i8 46

llvm/test/CodeGen/AArch64/GlobalISel/retry-artifact-combine.mir

 # NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
 # RUN: llc -o - -march=aarch64 -run-pass=legalizer %s | FileCheck %s
 ---
 name:            combine_anyext_s2
 body:             |
   bb.1:
     ; CHECK-LABEL: name: combine_anyext_s2
     ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
     ; CHECK: [[COPY1:%[0-9]+]]:_(s32) = COPY $w1
     ; CHECK: [[FCMP:%[0-9]+]]:_(s32) = G_FCMP floatpred(ogt), [[COPY]](s32), [[COPY1]]
-    ; CHECK: [[COPY2:%[0-9]+]]:_(s32) = COPY [[FCMP]](s32)
     ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 1
-    ; CHECK: [[COPY3:%[0-9]+]]:_(s32) = COPY [[C]](s32)
-    ; CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[COPY2]], [[COPY3]]
-    ; CHECK: [[COPY4:%[0-9]+]]:_(s32) = COPY [[AND]](s32)
-    ; CHECK: [[AND1:%[0-9]+]]:_(s32) = G_AND [[COPY4]], [[C]]
-    ; CHECK: [[COPY5:%[0-9]+]]:_(s32) = COPY [[AND1]](s32)
-    ; CHECK: $w0 = COPY [[COPY5]](s32)
+    ; CHECK: [[COPY2:%[0-9]+]]:_(s32) = COPY [[FCMP]](s32)
+    ; CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[COPY2]], [[C]]
+    ; CHECK: [[AND1:%[0-9]+]]:_(s32) = G_AND [[AND]], [[C]]
+    ; CHECK: [[COPY3:%[0-9]+]]:_(s32) = COPY [[AND1]](s32)
+    ; CHECK: $w0 = COPY [[COPY3]](s32)
     %0:_(s32) = COPY $w0
     %1:_(s32) = COPY $w1
     %2:_(s1) = G_FCMP floatpred(ogt), %0(s32), %1
     %3:_(s2) = G_ZEXT %2(s1)
     %4:_(s2) = G_CONSTANT i2 1
     %5:_(s2) = G_AND %3, %4
     %6:_(s32) = G_ANYEXT %5(s2)
     $w0 = COPY %6(s32)
 ...
 

llvm/test/CodeGen/AMDGPU/GlobalISel/artifact-combiner-sext.mir

body: |
   bb.0:
     liveins: $vgpr0_vgpr1
 
     ; CHECK-LABEL: name: test_sext_trunc_v2s32_to_v2s16_to_v2s64
     ; CHECK: [[COPY:%[0-9]+]]:_(<2 x s32>) = COPY $vgpr0_vgpr1
     ; CHECK: [[UV:%[0-9]+]]:_(s32), [[UV1:%[0-9]+]]:_(s32) = G_UNMERGE_VALUES [[COPY]](<2 x s32>)
     ; CHECK: [[ANYEXT:%[0-9]+]]:_(s64) = G_ANYEXT [[UV]](s32)
     ; CHECK: [[ANYEXT1:%[0-9]+]]:_(s64) = G_ANYEXT [[UV1]](s32)
-    ; CHECK: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 48
-    ; CHECK: [[TRUNC:%[0-9]+]]:_(s32) = G_TRUNC [[C]](s64)
-    ; CHECK: [[SHL:%[0-9]+]]:_(s64) = G_SHL [[ANYEXT]], [[TRUNC]](s32)
-    ; CHECK: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[C]](s64)
-    ; CHECK: [[SHL1:%[0-9]+]]:_(s64) = G_SHL [[ANYEXT1]], [[TRUNC1]](s32)
-    ; CHECK: [[TRUNC2:%[0-9]+]]:_(s32) = G_TRUNC [[C]](s64)
-    ; CHECK: [[ASHR:%[0-9]+]]:_(s64) = G_ASHR [[SHL]], [[TRUNC2]](s32)
-    ; CHECK: [[TRUNC3:%[0-9]+]]:_(s32) = G_TRUNC [[C]](s64)
-    ; CHECK: [[ASHR1:%[0-9]+]]:_(s64) = G_ASHR [[SHL1]], [[TRUNC3]](s32)
+    ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 48
+    ; CHECK: [[COPY1:%[0-9]+]]:_(s32) = COPY [[C]](s32)
+    ; CHECK: [[SHL:%[0-9]+]]:_(s64) = G_SHL [[ANYEXT]], [[COPY1]](s32)
+    ; CHECK: [[SHL1:%[0-9]+]]:_(s64) = G_SHL [[ANYEXT1]], [[C]](s32)
+    ; CHECK: [[COPY2:%[0-9]+]]:_(s32) = COPY [[C]](s32)
+    ; CHECK: [[ASHR:%[0-9]+]]:_(s64) = G_ASHR [[SHL]], [[COPY2]](s32)
+    ; CHECK: [[COPY3:%[0-9]+]]:_(s32) = COPY [[C]](s32)
+    ; CHECK: [[ASHR1:%[0-9]+]]:_(s64) = G_ASHR [[SHL1]], [[COPY3]](s32)
     ; CHECK: [[BUILD_VECTOR:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[ASHR]](s64), [[ASHR1]](s64)
     ; CHECK: $vgpr0_vgpr1_vgpr2_vgpr3 = COPY [[BUILD_VECTOR]](<2 x s64>)
     %0:_(<2 x s32>) = COPY $vgpr0_vgpr1
     %1:_(<2 x s16>) = G_TRUNC %0
     %2:_(<2 x s64>) = G_SEXT %1
     $vgpr0_vgpr1_vgpr2_vgpr3 = COPY %2
 ...
 
 ---
 name: test_sext_trunc_v2s32_to_v2s8_to_v2s16
 body: |
   bb.0:
     liveins: $vgpr0_vgpr1
 
     ; The G_SEXT_INREG doesn't lower here because G_TRUNC is both illegal and
     ; unable to legalize. This prevents further legalization.
     ; CHECK-LABEL: name: test_sext_trunc_v2s32_to_v2s8_to_v2s16
     ; CHECK: [[COPY:%[0-9]+]]:_(<2 x s32>) = COPY $vgpr0_vgpr1
     ; CHECK: [[TRUNC:%[0-9]+]]:_(<2 x s16>) = G_TRUNC [[COPY]](<2 x s32>)
-    ; CHECK: [[C:%[0-9]+]]:_(s16) = G_CONSTANT i16 8
     ; CHECK: [[BITCAST:%[0-9]+]]:_(s32) = G_BITCAST [[TRUNC]](<2 x s16>)
-    ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 16
-    ; CHECK: [[LSHR:%[0-9]+]]:_(s32) = G_LSHR [[BITCAST]], [[C1]](s32)
-    ; CHECK: [[ZEXT:%[0-9]+]]:_(s32) = G_ZEXT [[C]](s16)
-    ; CHECK: [[COPY1:%[0-9]+]]:_(s32) = COPY [[BITCAST]](s32)
-    ; CHECK: [[SHL:%[0-9]+]]:_(s32) = G_SHL [[COPY1]], [[ZEXT]](s32)
-    ; CHECK: [[TRUNC1:%[0-9]+]]:_(s16) = G_TRUNC [[SHL]](s32)
-    ; CHECK: [[ZEXT1:%[0-9]+]]:_(s32) = G_ZEXT [[C]](s16)
-    ; CHECK: [[COPY2:%[0-9]+]]:_(s32) = COPY [[LSHR]](s32)
-    ; CHECK: [[SHL1:%[0-9]+]]:_(s32) = G_SHL [[COPY2]], [[ZEXT1]](s32)
-    ; CHECK: [[TRUNC2:%[0-9]+]]:_(s16) = G_TRUNC [[SHL1]](s32)
-    ; CHECK: [[ZEXT2:%[0-9]+]]:_(s32) = G_ZEXT [[C]](s16)
-    ; CHECK: [[SEXT:%[0-9]+]]:_(s32) = G_SEXT [[TRUNC1]](s16)
-    ; CHECK: [[ASHR:%[0-9]+]]:_(s32) = G_ASHR [[SEXT]], [[ZEXT2]](s32)
-    ; CHECK: [[TRUNC3:%[0-9]+]]:_(s16) = G_TRUNC [[ASHR]](s32)
-    ; CHECK: [[ZEXT3:%[0-9]+]]:_(s32) = G_ZEXT [[C]](s16)
-    ; CHECK: [[SEXT1:%[0-9]+]]:_(s32) = G_SEXT [[TRUNC2]](s16)
-    ; CHECK: [[ASHR1:%[0-9]+]]:_(s32) = G_ASHR [[SEXT1]], [[ZEXT3]](s32)
-    ; CHECK: [[TRUNC4:%[0-9]+]]:_(s16) = G_TRUNC [[ASHR1]](s32)
-    ; CHECK: [[BUILD_VECTOR:%[0-9]+]]:_(<2 x s16>) = G_BUILD_VECTOR [[TRUNC3]](s16), [[TRUNC4]](s16)
+    ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 16
+    ; CHECK: [[LSHR:%[0-9]+]]:_(s32) = G_LSHR [[BITCAST]], [[C]](s32)
+    ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 8
+    ; CHECK: [[COPY1:%[0-9]+]]:_(s32) = COPY [[C1]](s32)
+    ; CHECK: [[COPY2:%[0-9]+]]:_(s32) = COPY [[BITCAST]](s32)
+    ; CHECK: [[SHL:%[0-9]+]]:_(s32) = G_SHL [[COPY2]], [[COPY1]](s32)
+    ; CHECK: [[COPY3:%[0-9]+]]:_(s32) = COPY [[LSHR]](s32)
+    ; CHECK: [[SHL1:%[0-9]+]]:_(s32) = G_SHL [[COPY3]], [[C1]](s32)
+    ; CHECK: [[COPY4:%[0-9]+]]:_(s32) = COPY [[C1]](s32)
+    ; CHECK: [[COPY5:%[0-9]+]]:_(s32) = COPY [[SHL]](s32)
+    ; CHECK: [[SHL2:%[0-9]+]]:_(s32) = G_SHL [[COPY5]], [[C]](s32)
+    ; CHECK: [[ASHR:%[0-9]+]]:_(s32) = G_ASHR [[SHL2]], [[C]](s32)
+    ; CHECK: [[ASHR1:%[0-9]+]]:_(s32) = G_ASHR [[ASHR]], [[COPY4]](s32)
+    ; CHECK: [[TRUNC1:%[0-9]+]]:_(s16) = G_TRUNC [[ASHR1]](s32)
+    ; CHECK: [[COPY6:%[0-9]+]]:_(s32) = COPY [[C1]](s32)
+    ; CHECK: [[COPY7:%[0-9]+]]:_(s32) = COPY [[SHL1]](s32)
+    ; CHECK: [[SHL3:%[0-9]+]]:_(s32) = G_SHL [[COPY7]], [[C]](s32)
+    ; CHECK: [[ASHR2:%[0-9]+]]:_(s32) = G_ASHR [[SHL3]], [[C]](s32)
+    ; CHECK: [[ASHR3:%[0-9]+]]:_(s32) = G_ASHR [[ASHR2]], [[COPY6]](s32)
+    ; CHECK: [[TRUNC2:%[0-9]+]]:_(s16) = G_TRUNC [[ASHR3]](s32)
+    ; CHECK: [[BUILD_VECTOR:%[0-9]+]]:_(<2 x s16>) = G_BUILD_VECTOR [[TRUNC1]](s16), [[TRUNC2]](s16)
     ; CHECK: $vgpr0 = COPY [[BUILD_VECTOR]](<2 x s16>)
     %0:_(<2 x s32>) = COPY $vgpr0_vgpr1
     %1:_(<2 x s8>) = G_TRUNC %0
     %2:_(<2 x s16>) = G_SEXT %1
     $vgpr0 = COPY %2
 ...
 
 ---

llvm/test/CodeGen/AMDGPU/GlobalISel/legalize-fcopysign.mir

bb.0:
     ; SI-LABEL: name: test_copysign_v2s64_v2s32
     ; SI: [[COPY:%[0-9]+]]:_(<2 x s64>) = COPY $vgpr0_vgpr1_vgpr2_vgpr3
     ; SI: [[COPY1:%[0-9]+]]:_(<2 x s32>) = COPY $vgpr4_vgpr5
     ; SI: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 -9223372036854775808
     ; SI: [[C1:%[0-9]+]]:_(s64) = G_CONSTANT i64 9223372036854775807
     ; SI: [[UV:%[0-9]+]]:_(s64), [[UV1:%[0-9]+]]:_(s64) = G_UNMERGE_VALUES [[COPY]](<2 x s64>)
     ; SI: [[AND:%[0-9]+]]:_(s64) = G_AND [[UV]], [[C1]]
     ; SI: [[AND1:%[0-9]+]]:_(s64) = G_AND [[UV1]], [[C1]]
-    ; SI: [[C2:%[0-9]+]]:_(s64) = G_CONSTANT i64 32
     ; SI: [[UV2:%[0-9]+]]:_(s32), [[UV3:%[0-9]+]]:_(s32) = G_UNMERGE_VALUES [[COPY1]](<2 x s32>)
     ; SI: [[ZEXT:%[0-9]+]]:_(s64) = G_ZEXT [[UV2]](s32)
     ; SI: [[ZEXT1:%[0-9]+]]:_(s64) = G_ZEXT [[UV3]](s32)
     ; SI: [[BUILD_VECTOR:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[ZEXT]](s64), [[ZEXT1]](s64)
     ; SI: [[UV4:%[0-9]+]]:_(s64), [[UV5:%[0-9]+]]:_(s64) = G_UNMERGE_VALUES [[BUILD_VECTOR]](<2 x s64>)
-    ; SI: [[TRUNC:%[0-9]+]]:_(s32) = G_TRUNC [[C2]](s64)
-    ; SI: [[SHL:%[0-9]+]]:_(s64) = G_SHL [[UV4]], [[TRUNC]](s32)
-    ; SI: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[C2]](s64)
-    ; SI: [[SHL1:%[0-9]+]]:_(s64) = G_SHL [[UV5]], [[TRUNC1]](s32)
+    ; SI: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 32
+    ; SI: [[COPY2:%[0-9]+]]:_(s32) = COPY [[C2]](s32)
+    ; SI: [[SHL:%[0-9]+]]:_(s64) = G_SHL [[UV4]], [[COPY2]](s32)
+    ; SI: [[SHL1:%[0-9]+]]:_(s64) = G_SHL [[UV5]], [[C2]](s32)
     ; SI: [[AND2:%[0-9]+]]:_(s64) = G_AND [[SHL]], [[C]]
     ; SI: [[AND3:%[0-9]+]]:_(s64) = G_AND [[SHL1]], [[C]]
     ; SI: [[OR:%[0-9]+]]:_(s64) = G_OR [[AND]], [[AND2]]
     ; SI: [[OR1:%[0-9]+]]:_(s64) = G_OR [[AND1]], [[AND3]]
     ; SI: [[BUILD_VECTOR1:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[OR]](s64), [[OR1]](s64)
     ; SI: $vgpr0_vgpr1_vgpr2_vgpr3 = COPY [[BUILD_VECTOR1]](<2 x s64>)
     ; VI-LABEL: name: test_copysign_v2s64_v2s32
     ; VI: [[COPY:%[0-9]+]]:_(<2 x s64>) = COPY $vgpr0_vgpr1_vgpr2_vgpr3
     ; VI: [[COPY1:%[0-9]+]]:_(<2 x s32>) = COPY $vgpr4_vgpr5
     ; VI: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 -9223372036854775808
     ; VI: [[C1:%[0-9]+]]:_(s64) = G_CONSTANT i64 9223372036854775807
     ; VI: [[UV:%[0-9]+]]:_(s64), [[UV1:%[0-9]+]]:_(s64) = G_UNMERGE_VALUES [[COPY]](<2 x s64>)
     ; VI: [[AND:%[0-9]+]]:_(s64) = G_AND [[UV]], [[C1]]
     ; VI: [[AND1:%[0-9]+]]:_(s64) = G_AND [[UV1]], [[C1]]
-    ; VI: [[C2:%[0-9]+]]:_(s64) = G_CONSTANT i64 32
     ; VI: [[UV2:%[0-9]+]]:_(s32), [[UV3:%[0-9]+]]:_(s32) = G_UNMERGE_VALUES [[COPY1]](<2 x s32>)
     ; VI: [[ZEXT:%[0-9]+]]:_(s64) = G_ZEXT [[UV2]](s32)
     ; VI: [[ZEXT1:%[0-9]+]]:_(s64) = G_ZEXT [[UV3]](s32)
     ; VI: [[BUILD_VECTOR:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[ZEXT]](s64), [[ZEXT1]](s64)
     ; VI: [[UV4:%[0-9]+]]:_(s64), [[UV5:%[0-9]+]]:_(s64) = G_UNMERGE_VALUES [[BUILD_VECTOR]](<2 x s64>)
-    ; VI: [[TRUNC:%[0-9]+]]:_(s32) = G_TRUNC [[C2]](s64)
-    ; VI: [[SHL:%[0-9]+]]:_(s64) = G_SHL [[UV4]], [[TRUNC]](s32)
-    ; VI: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[C2]](s64)
-    ; VI: [[SHL1:%[0-9]+]]:_(s64) = G_SHL [[UV5]], [[TRUNC1]](s32)
+    ; VI: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 32
+    ; VI: [[COPY2:%[0-9]+]]:_(s32) = COPY [[C2]](s32)
+    ; VI: [[SHL:%[0-9]+]]:_(s64) = G_SHL [[UV4]], [[COPY2]](s32)
+    ; VI: [[SHL1:%[0-9]+]]:_(s64) = G_SHL [[UV5]], [[C2]](s32)
     ; VI: [[AND2:%[0-9]+]]:_(s64) = G_AND [[SHL]], [[C]]
     ; VI: [[AND3:%[0-9]+]]:_(s64) = G_AND [[SHL1]], [[C]]
     ; VI: [[OR:%[0-9]+]]:_(s64) = G_OR [[AND]], [[AND2]]
     ; VI: [[OR1:%[0-9]+]]:_(s64) = G_OR [[AND1]], [[AND3]]
     ; VI: [[BUILD_VECTOR1:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[OR]](s64), [[OR1]](s64)
     ; VI: $vgpr0_vgpr1_vgpr2_vgpr3 = COPY [[BUILD_VECTOR1]](<2 x s64>)
     ; GFX9-LABEL: name: test_copysign_v2s64_v2s32
     ; GFX9: [[COPY:%[0-9]+]]:_(<2 x s64>) = COPY $vgpr0_vgpr1_vgpr2_vgpr3
     ; GFX9: [[COPY1:%[0-9]+]]:_(<2 x s32>) = COPY $vgpr4_vgpr5
     ; GFX9: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 -9223372036854775808
     ; GFX9: [[C1:%[0-9]+]]:_(s64) = G_CONSTANT i64 9223372036854775807
     ; GFX9: [[UV:%[0-9]+]]:_(s64), [[UV1:%[0-9]+]]:_(s64) = G_UNMERGE_VALUES [[COPY]](<2 x s64>)
     ; GFX9: [[AND:%[0-9]+]]:_(s64) = G_AND [[UV]], [[C1]]
     ; GFX9: [[AND1:%[0-9]+]]:_(s64) = G_AND [[UV1]], [[C1]]
-    ; GFX9: [[C2:%[0-9]+]]:_(s64) = G_CONSTANT i64 32
     ; GFX9: [[UV2:%[0-9]+]]:_(s32), [[UV3:%[0-9]+]]:_(s32) = G_UNMERGE_VALUES [[COPY1]](<2 x s32>)
     ; GFX9: [[ZEXT:%[0-9]+]]:_(s64) = G_ZEXT [[UV2]](s32)
     ; GFX9: [[ZEXT1:%[0-9]+]]:_(s64) = G_ZEXT [[UV3]](s32)
     ; GFX9: [[BUILD_VECTOR:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[ZEXT]](s64), [[ZEXT1]](s64)
     ; GFX9: [[UV4:%[0-9]+]]:_(s64), [[UV5:%[0-9]+]]:_(s64) = G_UNMERGE_VALUES [[BUILD_VECTOR]](<2 x s64>)
-    ; GFX9: [[TRUNC:%[0-9]+]]:_(s32) = G_TRUNC [[C2]](s64)
-    ; GFX9: [[SHL:%[0-9]+]]:_(s64) = G_SHL [[UV4]], [[TRUNC]](s32)
-    ; GFX9: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[C2]](s64)
-    ; GFX9: [[SHL1:%[0-9]+]]:_(s64) = G_SHL [[UV5]], [[TRUNC1]](s32)
+    ; GFX9: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 32
+    ; GFX9: [[COPY2:%[0-9]+]]:_(s32) = COPY [[C2]](s32)
+    ; GFX9: [[SHL:%[0-9]+]]:_(s64) = G_SHL [[UV4]], [[COPY2]](s32)
+    ; GFX9: [[SHL1:%[0-9]+]]:_(s64) = G_SHL [[UV5]], [[C2]](s32)
     ; GFX9: [[AND2:%[0-9]+]]:_(s64) = G_AND [[SHL]], [[C]]
     ; GFX9: [[AND3:%[0-9]+]]:_(s64) = G_AND [[SHL1]], [[C]]
     ; GFX9: [[OR:%[0-9]+]]:_(s64) = G_OR [[AND]], [[AND2]]
     ; GFX9: [[OR1:%[0-9]+]]:_(s64) = G_OR [[AND1]], [[AND3]]
     ; GFX9: [[BUILD_VECTOR1:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[OR]](s64), [[OR1]](s64)
     ; GFX9: $vgpr0_vgpr1_vgpr2_vgpr3 = COPY [[BUILD_VECTOR1]](<2 x s64>)
     %0:_(<2 x s64>) = COPY $vgpr0_vgpr1_vgpr2_vgpr3
     %1:_(<2 x s32>) = COPY $vgpr4_vgpr5
bb.0:
     ; SI-LABEL: name: test_copysign_v2s32_v2s64
     ; SI: [[COPY:%[0-9]+]]:_(<2 x s32>) = COPY $vgpr0_vgpr1
     ; SI: [[COPY1:%[0-9]+]]:_(<2 x s64>) = COPY $vgpr2_vgpr3_vgpr4_vgpr5
     ; SI: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 -2147483648
     ; SI: [[BUILD_VECTOR:%[0-9]+]]:_(<2 x s32>) = G_BUILD_VECTOR [[C]](s32), [[C]](s32)
     ; SI: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 2147483647
     ; SI: [[BUILD_VECTOR1:%[0-9]+]]:_(<2 x s32>) = G_BUILD_VECTOR [[C1]](s32), [[C1]](s32)
     ; SI: [[AND:%[0-9]+]]:_(<2 x s32>) = G_AND [[COPY]], [[BUILD_VECTOR1]]
-    ; SI: [[C2:%[0-9]+]]:_(s64) = G_CONSTANT i64 32
     ; SI: [[UV:%[0-9]+]]:_(s64), [[UV1:%[0-9]+]]:_(s64) = G_UNMERGE_VALUES [[COPY1]](<2 x s64>)
-    ; SI: [[TRUNC:%[0-9]+]]:_(s32) = G_TRUNC [[C2]](s64)
-    ; SI: [[LSHR:%[0-9]+]]:_(s64) = G_LSHR [[UV]], [[TRUNC]](s32)
-    ; SI: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[C2]](s64)
-    ; SI: [[LSHR1:%[0-9]+]]:_(s64) = G_LSHR [[UV1]], [[TRUNC1]](s32)
+    ; SI: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 32
+    ; SI: [[COPY2:%[0-9]+]]:_(s32) = COPY [[C2]](s32)
+    ; SI: [[LSHR:%[0-9]+]]:_(s64) = G_LSHR [[UV]], [[COPY2]](s32)
+    ; SI: [[LSHR1:%[0-9]+]]:_(s64) = G_LSHR [[UV1]], [[C2]](s32)
     ; SI: [[BUILD_VECTOR2:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[LSHR]](s64), [[LSHR1]](s64)
-    ; SI: [[TRUNC2:%[0-9]+]]:_(<2 x s32>) = G_TRUNC [[BUILD_VECTOR2]](<2 x s64>)
-    ; SI: [[AND1:%[0-9]+]]:_(<2 x s32>) = G_AND [[TRUNC2]], [[BUILD_VECTOR]]
+    ; SI: [[TRUNC:%[0-9]+]]:_(<2 x s32>) = G_TRUNC [[BUILD_VECTOR2]](<2 x s64>)
+    ; SI: [[AND1:%[0-9]+]]:_(<2 x s32>) = G_AND [[TRUNC]], [[BUILD_VECTOR]]
     ; SI: [[OR:%[0-9]+]]:_(<2 x s32>) = G_OR [[AND]], [[AND1]]
     ; SI: $vgpr0_vgpr1 = COPY [[OR]](<2 x s32>)
     ; VI-LABEL: name: test_copysign_v2s32_v2s64
     ; VI: [[COPY:%[0-9]+]]:_(<2 x s32>) = COPY $vgpr0_vgpr1
     ; VI: [[COPY1:%[0-9]+]]:_(<2 x s64>) = COPY $vgpr2_vgpr3_vgpr4_vgpr5
     ; VI: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 -2147483648
     ; VI: [[BUILD_VECTOR:%[0-9]+]]:_(<2 x s32>) = G_BUILD_VECTOR [[C]](s32), [[C]](s32)
     ; VI: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 2147483647
     ; VI: [[BUILD_VECTOR1:%[0-9]+]]:_(<2 x s32>) = G_BUILD_VECTOR [[C1]](s32), [[C1]](s32)
     ; VI: [[AND:%[0-9]+]]:_(<2 x s32>) = G_AND [[COPY]], [[BUILD_VECTOR1]]
-    ; VI: [[C2:%[0-9]+]]:_(s64) = G_CONSTANT i64 32
     ; VI: [[UV:%[0-9]+]]:_(s64), [[UV1:%[0-9]+]]:_(s64) = G_UNMERGE_VALUES [[COPY1]](<2 x s64>)
-    ; VI: [[TRUNC:%[0-9]+]]:_(s32) = G_TRUNC [[C2]](s64)
-    ; VI: [[LSHR:%[0-9]+]]:_(s64) = G_LSHR [[UV]], [[TRUNC]](s32)
-    ; VI: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[C2]](s64)
-    ; VI: [[LSHR1:%[0-9]+]]:_(s64) = G_LSHR [[UV1]], [[TRUNC1]](s32)
+    ; VI: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 32
+    ; VI: [[COPY2:%[0-9]+]]:_(s32) = COPY [[C2]](s32)
+    ; VI: [[LSHR:%[0-9]+]]:_(s64) = G_LSHR [[UV]], [[COPY2]](s32)
+    ; VI: [[LSHR1:%[0-9]+]]:_(s64) = G_LSHR [[UV1]], [[C2]](s32)
     ; VI: [[BUILD_VECTOR2:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[LSHR]](s64), [[LSHR1]](s64)
-    ; VI: [[TRUNC2:%[0-9]+]]:_(<2 x s32>) = G_TRUNC [[BUILD_VECTOR2]](<2 x s64>)
-    ; VI: [[AND1:%[0-9]+]]:_(<2 x s32>) = G_AND [[TRUNC2]], [[BUILD_VECTOR]]
+    ; VI: [[TRUNC:%[0-9]+]]:_(<2 x s32>) = G_TRUNC [[BUILD_VECTOR2]](<2 x s64>)
+    ; VI: [[AND1:%[0-9]+]]:_(<2 x s32>) = G_AND [[TRUNC]], [[BUILD_VECTOR]]
     ; VI: [[OR:%[0-9]+]]:_(<2 x s32>) = G_OR [[AND]], [[AND1]]
     ; VI: $vgpr0_vgpr1 = COPY [[OR]](<2 x s32>)
     ; GFX9-LABEL: name: test_copysign_v2s32_v2s64
     ; GFX9: [[COPY:%[0-9]+]]:_(<2 x s32>) = COPY $vgpr0_vgpr1
     ; GFX9: [[COPY1:%[0-9]+]]:_(<2 x s64>) = COPY $vgpr2_vgpr3_vgpr4_vgpr5
     ; GFX9: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 -2147483648
     ; GFX9: [[BUILD_VECTOR:%[0-9]+]]:_(<2 x s32>) = G_BUILD_VECTOR [[C]](s32), [[C]](s32)
     ; GFX9: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 2147483647
     ; GFX9: [[BUILD_VECTOR1:%[0-9]+]]:_(<2 x s32>) = G_BUILD_VECTOR [[C1]](s32), [[C1]](s32)
     ; GFX9: [[AND:%[0-9]+]]:_(<2 x s32>) = G_AND [[COPY]], [[BUILD_VECTOR1]]
-    ; GFX9: [[C2:%[0-9]+]]:_(s64) = G_CONSTANT i64 32
     ; GFX9: [[UV:%[0-9]+]]:_(s64), [[UV1:%[0-9]+]]:_(s64) = G_UNMERGE_VALUES [[COPY1]](<2 x s64>)
-    ; GFX9: [[TRUNC:%[0-9]+]]:_(s32) = G_TRUNC [[C2]](s64)
-    ; GFX9: [[LSHR:%[0-9]+]]:_(s64) = G_LSHR [[UV]], [[TRUNC]](s32)
-    ; GFX9: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[C2]](s64)
-    ; GFX9: [[LSHR1:%[0-9]+]]:_(s64) = G_LSHR [[UV1]], [[TRUNC1]](s32)
+    ; GFX9: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 32
+    ; GFX9: [[COPY2:%[0-9]+]]:_(s32) = COPY [[C2]](s32)
+    ; GFX9: [[LSHR:%[0-9]+]]:_(s64) = G_LSHR [[UV]], [[COPY2]](s32)
+    ; GFX9: [[LSHR1:%[0-9]+]]:_(s64) = G_LSHR [[UV1]], [[C2]](s32)
     ; GFX9: [[BUILD_VECTOR2:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[LSHR]](s64), [[LSHR1]](s64)
-    ; GFX9: [[TRUNC2:%[0-9]+]]:_(<2 x s32>) = G_TRUNC [[BUILD_VECTOR2]](<2 x s64>)
-    ; GFX9: [[AND1:%[0-9]+]]:_(<2 x s32>) = G_AND [[TRUNC2]], [[BUILD_VECTOR]]
+    ; GFX9: [[TRUNC:%[0-9]+]]:_(<2 x s32>) = G_TRUNC [[BUILD_VECTOR2]](<2 x s64>)
+    ; GFX9: [[AND1:%[0-9]+]]:_(<2 x s32>) = G_AND [[TRUNC]], [[BUILD_VECTOR]]
     ; GFX9: [[OR:%[0-9]+]]:_(<2 x s32>) = G_OR [[AND]], [[AND1]]
     ; GFX9: $vgpr0_vgpr1 = COPY [[OR]](<2 x s32>)
     %0:_(<2 x s32>) = COPY $vgpr0_vgpr1
     %1:_(<2 x s64>) = COPY $vgpr2_vgpr3_vgpr4_vgpr5
     %2:_(<2 x s32>) = G_FCOPYSIGN %0, %1
     $vgpr0_vgpr1 = COPY %2
 ...
 

llvm/unittests/CodeGen/GlobalISel/LegalizerTest.cpp

::testing::AssertionResult isNullMIPtr(const MachineInstr *MI) {
   std::string MIBuffer;
   raw_string_ostream MISStream(MIBuffer);
   MI->print(MISStream, /*IsStandalone=*/true, /*SkipOpers=*/false,
             /*SkipDebugLoc=*/false, /*AddNewLine=*/false);
   return ::testing::AssertionFailure()
          << "unable to legalize instruction: " << MISStream.str();
 }
 
-TEST_F(GISelMITest, BasicLegalizerTest) {
-  StringRef MIRString = R"(
-    %vptr:_(p0) = COPY $x4
-    %v:_(<2 x s8>) = G_LOAD %vptr:_(p0) :: (load 2, align 1)
-    $h4 = COPY %v:_(<2 x s8>)
-  )";
-  setUp(MIRString.rtrim(' '));
-  if (!TM)
-    return;
-
-  DefineLegalizerInfo(ALegalizer, {
-    auto p0 = LLT::pointer(0, 64);
-    auto v2s8 = LLT::vector(2, 8);
-    auto v2s16 = LLT::vector(2, 16);
-    getActionDefinitionsBuilder(G_LOAD)
-        .legalForTypesWithMemDesc({{s16, p0, 8, 8}})
-        .scalarize(0)
-        .clampScalar(0, s16, s16);
-    getActionDefinitionsBuilder(G_PTR_ADD).legalFor({{p0, s64}});
-    getActionDefinitionsBuilder(G_CONSTANT).legalFor({s64});
-    getActionDefinitionsBuilder(G_BUILD_VECTOR)
-        .legalFor({{v2s16, s16}})
-        .clampScalar(1, s16, s16);
-    getActionDefinitionsBuilder(G_BUILD_VECTOR_TRUNC).legalFor({{v2s8, s16}});
-    getActionDefinitionsBuilder(G_ANYEXT).legalFor({{s32, s16}});
-  });
+  getActionDefinitionsBuilder(G_CONSTANT).legalFor({s32, s64});
+  getActionDefinitionsBuilder(G_ZEXT).legalFor({{s32, s16}});
+  getActionDefinitionsBuilder(G_SEXT).legalFor({{s32, s16}});
+  getActionDefinitionsBuilder(G_AND).legalFor({s32});
+  getActionDefinitionsBuilder(G_SEXT_INREG).lower();
+  getActionDefinitionsBuilder(G_ASHR).legalFor({{s32, s32}});
+  getActionDefinitionsBuilder(G_SHL).legalFor({{s32, s32}});
 
+TEST_F(GISelMITest, BasicLegalizerTest) {
+  StringRef MIRString = R"(
+    %vptr:_(p0) = COPY $x4
+    %v:_(<2 x s8>) = G_LOAD %vptr:_(p0) :: (load 2, align 1)
+    $h4 = COPY %v:_(<2 x s8>)
+  )";
+  setUp(MIRString.rtrim(' '));
+  if (!TM)
+    return;
+
   ALegalizerInfo LI(MF->getSubtarget());
 
   Legalizer::MFResult Result =
       Legalizer::legalizeMachineFunction(*MF, LI, {}, B);
 
   EXPECT_TRUE(isNullMIPtr(Result.FailedOn));
   EXPECT_TRUE(Result.Changed);
 
   StringRef CheckString = R"(
     CHECK:      %vptr:_(p0) = COPY $x4
     CHECK-NEXT: [[LOAD_0:%[0-9]+]]:_(s16) = G_LOAD %vptr:_(p0) :: (load 1)
     CHECK-NEXT: [[OFFSET_1:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
     CHECK-NEXT: [[VPTR_1:%[0-9]+]]:_(p0) = G_PTR_ADD %vptr:_, [[OFFSET_1]]:_(s64)
     CHECK-NEXT: [[LOAD_1:%[0-9]+]]:_(s16) = G_LOAD [[VPTR_1]]:_(p0) :: (load 1)
     CHECK-NEXT: [[V0:%[0-9]+]]:_(s16) = COPY [[LOAD_0]]:_(s16)
     CHECK-NEXT: [[V1:%[0-9]+]]:_(s16) = COPY [[LOAD_1]]:_(s16)
     CHECK-NEXT: %v:_(<2 x s8>) = G_BUILD_VECTOR_TRUNC [[V0]]:_(s16), [[V1]]:_(s16)
     CHECK-NEXT: $h4 = COPY %v:_(<2 x s8>)
   )";
 
   EXPECT_TRUE(CheckMachineFunction(*MF, CheckString)) << *MF;
 }
 
+// Making sure the legalization finishes successfully w/o failure to combine
+// away all the legalization artifacts regardless of the order of their
+// creation.
+TEST_F(GISelMITest, UnorderedArtifactCombiningTest) {
+  StringRef MIRString = R"(
+    %vptr:_(p0) = COPY $x4
+    %v:_(<2 x s8>) = G_LOAD %vptr:_(p0) :: (load 2, align 1)
+    %v0:_(s8), %v1:_(s8) = G_UNMERGE_VALUES %v:_(<2 x s8>)
+    %v0_ext:_(s16) = G_ANYEXT %v0:_(s8)
+    $h4 = COPY %v0_ext:_(s16)
+  )";
+  setUp(MIRString.rtrim(' '));
+  if (!TM)
+    return;
+
+  ALegalizerInfo LI(MF->getSubtarget());
+
+  // The events here unfold as follows:
+  // 1. First, the function is scanned pre-forming the worklist of artifacts:
+  //
+  //      UNMERGE  (1): pushed into the worklist first, will be processed last.
+  //         |
+  //       ANYEXT  (2)
+  //
+  // 2. Second, the load is scalarized, and then its destination is widened,
+  //    forming the following chain of legalization artifacts:
+  //
+  //        TRUNC  (4): created last, will be processed first.
+  //         |
+  // BUILD_VECTOR  (3)
+  //         |
+  //      UNMERGE  (1): pushed into the worklist first, will be processed last.
+  //         |
+  //       ANYEXT  (2)
+  //
+  // 3. Third, the artifacts are attempted to be combined in pairs, looking
+  //    through the def-use chain from the roots towards the leafs, visiting the
+  //    roots in order they happen to be in the worklist:
+  //      (4) - (trunc):                  can not be combined;
+  //      (3) - (build_vector (trunc)):   can not be combined;
+  //      (2) - (anyext (unmerge)):       can not be combined;
+  //      (1) - (unmerge (build_vector)): combined and eliminated;
+  //
+  //    leaving the function in the following state:
+  //
+  //        TRUNC  (1): moved to non-artifact instructions worklist first.
+  //         |
+  //       ANYEXT  (2): also moved to non-artifact instructions worklist.
+  //
+  //    Every other instruction is successfully legalized in full.
+  //    If combining (unmerge (build_vector)) does not re-insert every artifact
+  //    that had its def-use chain modified (shortened) into the artifact
+  //    worklist (here it's just ANYEXT), the process moves on onto the next
+  //    outer loop iteration of the top-level legalization algorithm here, w/o
+  //    performing all the artifact combines possible. Let's consider this
+  //    scenario first:
+  //  4.A. Neither TRUNC, nor ANYEXT can be legalized in isolation, both of them
+  //       get moved to the retry worklist, but no additional artifacts were
+  //       created in the process, thus algorithm concludes no progress could be
+  //       made, and fails.
+  //  4.B. If, however, combining (unmerge (build_vector)) had re-inserted
+  //       ANYEXT into the worklist (as ANYEXT's source changes, not by value,
+  //       but by implementation), (anyext (trunc)) combine happens next, which
+  //       fully eliminates all the artifacts and legalization succeeds.
+  //
+  //  We're looking into making sure that (4.B) happens here, not (4.A). Note
+  //  that in that case the first scan through the artifacts worklist, while not
+  //  being done in any guaranteed order, only needs to find the innermost
+  //  pair(s) of artifacts that could be immediately combined out. After that
+  //  the process follows def-use chains, making them shorter at each step, thus
+  //  combining everything that can be combined in O(n) time.
+  Legalizer::MFResult Result =
+      Legalizer::legalizeMachineFunction(*MF, LI, {}, B);
+
+  EXPECT_TRUE(isNullMIPtr(Result.FailedOn));
+  EXPECT_TRUE(Result.Changed);
+
+  StringRef CheckString = R"(
+    CHECK:      %vptr:_(p0) = COPY $x4
+    CHECK-NEXT: [[LOAD_0:%[0-9]+]]:_(s16) = G_LOAD %vptr:_(p0) :: (load 1)
+    CHECK:      %v0_ext:_(s16) = COPY [[LOAD_0]]:_(s16)
+    CHECK-NEXT: $h4 = COPY %v0_ext:_(s16)
+  )";
+
+  EXPECT_TRUE(CheckMachineFunction(*MF, CheckString)) << *MF;
+}
+
+TEST_F(GISelMITest, UnorderedArtifactCombiningManyCopiesTest) {
+  StringRef MIRString = R"(
+    %vptr:_(p0) = COPY $x4
+    %v:_(<2 x s8>) = G_LOAD %vptr:_(p0) :: (load 2, align 1)
+    %vc0:_(<2 x s8>) = COPY %v:_(<2 x s8>)
+    %vc1:_(<2 x s8>) = COPY %v:_(<2 x s8>)
+    %vc00:_(s8), %vc01:_(s8) = G_UNMERGE_VALUES %vc0:_(<2 x s8>)
+    %vc10:_(s8), %vc11:_(s8) = G_UNMERGE_VALUES %vc1:_(<2 x s8>)
+    %v0t:_(s8) = COPY %vc00:_(s8)
+    %v0:_(s8) = COPY %v0t:_(s8)
+    %v1t:_(s8) = COPY %vc11:_(s8)
+    %v1:_(s8) = COPY %v1t:_(s8)
+    %v0_zext:_(s32) = G_ZEXT %v0:_(s8)
+    %v1_sext:_(s32) = G_SEXT %v1:_(s8)
+    $w4 = COPY %v0_zext:_(s32)
+    $w5 = COPY %v1_sext:_(s32)
+  )";
+  setUp(MIRString.rtrim(' '));
+  if (!TM)
+    return;
+
+  ALegalizerInfo LI(MF->getSubtarget());
+
+  Legalizer::MFResult Result =
+      Legalizer::legalizeMachineFunction(*MF, LI, {}, B);
+
+  EXPECT_TRUE(isNullMIPtr(Result.FailedOn));
+  EXPECT_TRUE(Result.Changed);
+
+  StringRef CheckString = R"(
+    CHECK:      %vptr:_(p0) = COPY $x4
+    CHECK-NEXT: [[LOAD_0:%[0-9]+]]:_(s16) = G_LOAD %vptr:_(p0) :: (load 1)
+    CHECK-NEXT: [[OFFSET_1:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
+    CHECK-NEXT: [[VPTR_1:%[0-9]+]]:_(p0) = G_PTR_ADD %vptr:_, [[OFFSET_1]]:_(s64)
+    CHECK-NEXT: [[LOAD_1:%[0-9]+]]:_(s16) = G_LOAD [[VPTR_1]]:_(p0) :: (load 1)
+    CHECK-NEXT: [[FF_MASK:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
+    CHECK-NEXT: [[V0_EXT:%[0-9]+]]:_(s32) = G_ANYEXT [[LOAD_0]]:_(s16)
+    CHECK-NEXT: %v0_zext:_(s32) = G_AND [[V0_EXT]]:_, [[FF_MASK]]:_
+    CHECK-NEXT: [[V1_EXT:%[0-9]+]]:_(s32) = G_ANYEXT [[LOAD_1]]:_(s16)
+    CHECK-NEXT: [[SHAMNT:%[0-9]+]]:_(s32) = G_CONSTANT i32 24
+    CHECK-NEXT: [[V1_SHL:%[0-9]+]]:_(s32) = G_SHL [[V1_EXT]]:_, [[SHAMNT]]:_(s32)
+    CHECK-NEXT: %v1_sext:_(s32) = G_ASHR [[V1_SHL]]:_, [[SHAMNT]]:_(s32)
+    CHECK-NEXT: $w4 = COPY %v0_zext:_(s32)
+    CHECK-NEXT: $w5 = COPY %v1_sext:_(s32)
+  )";
+
+  EXPECT_TRUE(CheckMachineFunction(*MF, CheckString)) << *MF;
+}
+
 } // namespace