Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===-- llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h -----*- C++ -*-//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

// This file contains some helper functions which try to cleanup artifacts

// such as G_TRUNCs/G_[ZSA]EXTENDS that were created during legalization to make

// the types match. This file also contains some combines of merges that happens

// at the end of the legalization.

//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H

#define LLVM_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H

#include "llvm/ADT/SmallBitVector.h"

#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"

#include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"

#include "llvm/CodeGen/GlobalISel/Legalizer.h"

#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"

#include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"

#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"

#include "llvm/CodeGen/GlobalISel/Utils.h"

#include "llvm/CodeGen/MachineRegisterInfo.h"

#include "llvm/CodeGen/Register.h"

#include "llvm/IR/Constants.h"

#include "llvm/Support/Debug.h"

#define DEBUG_TYPE "legalizer"

namespace llvm {

class LegalizationArtifactCombiner {

  MachineIRBuilder &Builder;

  MachineRegisterInfo &MRI;

  const LegalizerInfo &LI;

  static bool isArtifactCast(unsigned Opc) {

    switch (Opc) {

    case TargetOpcode::G_TRUNC:

    case TargetOpcode::G_SEXT:

    case TargetOpcode::G_ZEXT:

    case TargetOpcode::G_ANYEXT:

      return true;

    default:

      return false;

    }

  }

public:

  LegalizationArtifactCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI,

                    const LegalizerInfo &LI)

      : Builder(B), MRI(MRI), LI(LI) {}

  bool tryCombineAnyExt(MachineInstr &MI,

                        SmallVectorImpl<MachineInstr *> &DeadInsts,

                        SmallVectorImpl<Register> &UpdatedDefs,

                        GISelObserverWrapper &Observer) {

    using namespace llvm::MIPatternMatch;

    assert(MI.getOpcode() == TargetOpcode::G_ANYEXT);

    Builder.setInstrAndDebugLoc(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;);

      if (MRI.getType(DstReg) == MRI.getType(TruncSrc))

        replaceRegOrBuildCopy(DstReg, TruncSrc, MRI, Builder, UpdatedDefs,

                              Observer);

      else

        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.

    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, UpdatedDefs);

  }

  bool tryCombineZExt(MachineInstr &MI,

                      SmallVectorImpl<MachineInstr *> &DeadInsts,

                      SmallVectorImpl<Register> &UpdatedDefs,

                      GISelObserverWrapper &Observer) {

    using namespace llvm::MIPatternMatch;

    assert(MI.getOpcode() == TargetOpcode::G_ZEXT);

    Builder.setInstrAndDebugLoc(MI);

    Register DstReg = MI.getOperand(0).getReg();

    Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());

    // zext(trunc x) - > and (aext/copy/trunc x), mask

    // zext(sext x) -> and (sext x), mask

    Register TruncSrc;

    Register SextSrc;

    if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc))) ||

        mi_match(SrcReg, MRI, m_GSExt(m_Reg(SextSrc)))) {

      LLT DstTy = MRI.getType(DstReg);

      if (isInstUnsupported({TargetOpcode::G_AND, {DstTy}}) ||

          isConstantUnsupported(DstTy))

        return false;

      LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);

      LLT SrcTy = MRI.getType(SrcReg);

      APInt MaskVal = APInt::getAllOnes(SrcTy.getScalarSizeInBits());

      auto Mask = Builder.buildConstant(

        DstTy, MaskVal.zext(DstTy.getScalarSizeInBits()));

      if (SextSrc && (DstTy != MRI.getType(SextSrc)))

        SextSrc = Builder.buildSExtOrTrunc(DstTy, SextSrc).getReg(0);

      if (TruncSrc && (DstTy != MRI.getType(TruncSrc)))

        TruncSrc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrc).getReg(0);

      Builder.buildAnd(DstReg, SextSrc ? SextSrc : TruncSrc, Mask);

      markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);

      return true;

    }

    // zext(zext x) -> (zext x)

    Register ZextSrc;

    if (mi_match(SrcReg, MRI, m_GZExt(m_Reg(ZextSrc)))) {

      LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI);

      Observer.changingInstr(MI);

      MI.getOperand(1).setReg(ZextSrc);

      Observer.changedInstr(MI);

      UpdatedDefs.push_back(DstReg);

      markDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);

      return true;

    }

    // Try to fold zext(g_constant) when the larger constant type is legal.

    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, UpdatedDefs);

  }

  bool tryCombineSExt(MachineInstr &MI,

                      SmallVectorImpl<MachineInstr *> &DeadInsts,

                      SmallVectorImpl<Register> &UpdatedDefs) {

    using namespace llvm::MIPatternMatch;

    assert(MI.getOpcode() == TargetOpcode::G_SEXT);

    Builder.setInstrAndDebugLoc(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();

      if (DstTy != MRI.getType(TruncSrc))

        TruncSrc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrc).getReg(0);

      Builder.buildSExtInReg(DstReg, TruncSrc, SizeInBits);

      markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);

      return true;

    }

    // sext(zext x) -> (zext x)

    // sext(sext x) -> (sext x)

    Register ExtSrc;

    MachineInstr *ExtMI;

    if (mi_match(SrcReg, MRI,

                 m_all_of(m_MInstr(ExtMI), m_any_of(m_GZExt(m_Reg(ExtSrc)),

                                                    m_GSExt(m_Reg(ExtSrc)))))) {

      LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI);

      Builder.buildInstr(ExtMI->getOpcode(), {DstReg}, {ExtSrc});

      UpdatedDefs.push_back(DstReg);

      markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);

      return true;

    }

    // Try to fold sext(g_constant) when the larger constant type is legal.

    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, UpdatedDefs);

  }

  bool tryCombineTrunc(MachineInstr &MI,

                       SmallVectorImpl<MachineInstr *> &DeadInsts,

                       SmallVectorImpl<Register> &UpdatedDefs,

                       GISelObserverWrapper &Observer) {

    using namespace llvm::MIPatternMatch;

    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.

    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;

      }

    }

    // Try to fold trunc(merge) to directly use the source of the merge.

    // This gets rid of large, difficult to legalize, merges

    if (auto *SrcMerge = dyn_cast<GMerge>(SrcMI)) {

      const Register MergeSrcReg = SrcMerge->getSourceReg(0);

      const LLT MergeSrcTy = MRI.getType(MergeSrcReg);

      const LLT DstTy = MRI.getType(DstReg);

      // We can only fold if the types are scalar

      const unsigned DstSize = DstTy.getSizeInBits();

      const unsigned MergeSrcSize = MergeSrcTy.getSizeInBits();

      if (!DstTy.isScalar() || !MergeSrcTy.isScalar())

        return false;

      if (DstSize < MergeSrcSize) {

        // When the merge source is larger than the destination, we can just

        // truncate the merge source directly

        if (isInstUnsupported({TargetOpcode::G_TRUNC, {DstTy, MergeSrcTy}}))

          return false;

        LLVM_DEBUG(dbgs() << "Combining G_TRUNC(G_MERGE_VALUES) to G_TRUNC: "

                          << MI);

        Builder.buildTrunc(DstReg, MergeSrcReg);

        UpdatedDefs.push_back(DstReg);

      } else if (DstSize == MergeSrcSize) {

        // If the sizes match we can simply try to replace the register

        LLVM_DEBUG(

            dbgs() << "Replacing G_TRUNC(G_MERGE_VALUES) with merge input: "

                   << MI);

        replaceRegOrBuildCopy(DstReg, MergeSrcReg, MRI, Builder, UpdatedDefs,

                              Observer);

      } else if (DstSize % MergeSrcSize == 0) {

        // If the trunc size is a multiple of the merge source size we can use

        // a smaller merge instead

        if (isInstUnsupported(

                {TargetOpcode::G_MERGE_VALUES, {DstTy, MergeSrcTy}}))

          return false;

        LLVM_DEBUG(

            dbgs() << "Combining G_TRUNC(G_MERGE_VALUES) to G_MERGE_VALUES: "

                   << MI);

        const unsigned NumSrcs = DstSize / MergeSrcSize;

        assert(NumSrcs < SrcMI->getNumOperands() - 1 &&

               "trunc(merge) should require less inputs than merge");

        SmallVector<Register, 8> SrcRegs(NumSrcs);

        for (unsigned i = 0; i < NumSrcs; ++i)

          SrcRegs[i] = SrcMerge->getSourceReg(i);

        Builder.buildMergeValues(DstReg, SrcRegs);

        UpdatedDefs.push_back(DstReg);

      } else {

        // Unable to combine

        return false;

      }

      markInstAndDefDead(MI, *SrcMerge, DeadInsts);

      return true;

    }

    // trunc(trunc) -> trunc

    Register TruncSrc;

    if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {

      // Always combine trunc(trunc) since the eventual resulting trunc must be

      // legal anyway as it must be legal for all outputs of the consumer type

      // set.

      LLVM_DEBUG(dbgs() << ".. Combine G_TRUNC(G_TRUNC): " << MI);

      Builder.buildTrunc(DstReg, TruncSrc);

      UpdatedDefs.push_back(DstReg);

      markInstAndDefDead(MI, *MRI.getVRegDef(TruncSrc), DeadInsts);

      return true;

    }

    return false;

  }

  /// Try to fold G_[ASZ]EXT (G_IMPLICIT_DEF).

  bool tryFoldImplicitDef(MachineInstr &MI,

                          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 (!isInstLegal({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;

  }

  bool tryFoldUnmergeCast(MachineInstr &MI, MachineInstr &CastMI,

                          SmallVectorImpl<MachineInstr *> &DeadInsts,

                          SmallVectorImpl<Register> &UpdatedDefs) {

    assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES);

    const unsigned CastOpc = CastMI.getOpcode();

    if (!isArtifactCast(CastOpc))

      return false;

    const unsigned NumDefs = MI.getNumOperands() - 1;

    const Register CastSrcReg = CastMI.getOperand(1).getReg();

    const LLT CastSrcTy = MRI.getType(CastSrcReg);

    const LLT DestTy = MRI.getType(MI.getOperand(0).getReg());

    const LLT SrcTy = MRI.getType(MI.getOperand(NumDefs).getReg());

    const unsigned CastSrcSize = CastSrcTy.getSizeInBits();

    const unsigned DestSize = DestTy.getSizeInBits();

    if (CastOpc == TargetOpcode::G_TRUNC) {

      if (SrcTy.isVector() && SrcTy.getScalarType() == DestTy.getScalarType()) {

        //  %1:_(<4 x s8>) = G_TRUNC %0(<4 x s32>)

        //  %2:_(s8), %3:_(s8), %4:_(s8), %5:_(s8) = G_UNMERGE_VALUES %1

        // =>

        //  %6:_(s32), %7:_(s32), %8:_(s32), %9:_(s32) = G_UNMERGE_VALUES %0

        //  %2:_(s8) = G_TRUNC %6

        //  %3:_(s8) = G_TRUNC %7

        //  %4:_(s8) = G_TRUNC %8

        //  %5:_(s8) = G_TRUNC %9

        unsigned UnmergeNumElts =

            DestTy.isVector() ? CastSrcTy.getNumElements() / NumDefs : 1;

        LLT UnmergeTy = CastSrcTy.changeElementCount(

            ElementCount::getFixed(UnmergeNumElts));

        if (isInstUnsupported(

                {TargetOpcode::G_UNMERGE_VALUES, {UnmergeTy, CastSrcTy}}))

          return false;

        Builder.setInstr(MI);

        auto NewUnmerge = Builder.buildUnmerge(UnmergeTy, CastSrcReg);

        for (unsigned I = 0; I != NumDefs; ++I) {

          Register DefReg = MI.getOperand(I).getReg();

          UpdatedDefs.push_back(DefReg);

          Builder.buildTrunc(DefReg, NewUnmerge.getReg(I));

        }

        markInstAndDefDead(MI, CastMI, DeadInsts);

        return true;

      }

      if (CastSrcTy.isScalar() && SrcTy.isScalar() && !DestTy.isVector()) {

        //  %1:_(s16) = G_TRUNC %0(s32)

        //  %2:_(s8), %3:_(s8) = G_UNMERGE_VALUES %1

        // =>

        //  %2:_(s8), %3:_(s8), %4:_(s8), %5:_(s8) = G_UNMERGE_VALUES %0

        // Unmerge(trunc) can be combined if the trunc source size is a multiple

        // of the unmerge destination size

        if (CastSrcSize % DestSize != 0)

          return false;

        // Check if the new unmerge is supported

        if (isInstUnsupported(

                {TargetOpcode::G_UNMERGE_VALUES, {DestTy, CastSrcTy}}))

          return false;

        // Gather the original destination registers and create new ones for the

        // unused bits

        const unsigned NewNumDefs = CastSrcSize / DestSize;

        SmallVector<Register, 8> DstRegs(NewNumDefs);

        for (unsigned Idx = 0; Idx < NewNumDefs; ++Idx) {

          if (Idx < NumDefs)

            DstRegs[Idx] = MI.getOperand(Idx).getReg();

          else

            DstRegs[Idx] = MRI.createGenericVirtualRegister(DestTy);

        }

        // Build new unmerge

        Builder.setInstr(MI);

        Builder.buildUnmerge(DstRegs, CastSrcReg);

        UpdatedDefs.append(DstRegs.begin(), DstRegs.begin() + NewNumDefs);

        markInstAndDefDead(MI, CastMI, DeadInsts);

        return true;

      }

    }

    // TODO: support combines with other casts as well

    return false;

  }

  static bool canFoldMergeOpcode(unsigned MergeOp, unsigned ConvertOp,

                                 LLT OpTy, LLT DestTy) {

    // Check if we found a definition that is like G_MERGE_VALUES.

    switch (MergeOp) {

    default:

      return false;

    case TargetOpcode::G_BUILD_VECTOR:

    case TargetOpcode::G_MERGE_VALUES:

      // The convert operation that we will need to insert is

      // going to convert the input of that type of instruction (scalar)

      // to the destination type (DestTy).

      // The conversion needs to stay in the same domain (scalar to scalar

      // and vector to vector), so if we were to allow to fold the merge

      // we would need to insert some bitcasts.

      // E.g.,

      // <2 x s16> = build_vector s16, s16

      // <2 x s32> = zext <2 x s16>

      // <2 x s16>, <2 x s16> = unmerge <2 x s32>

      //

      // As is the folding would produce:

      // <2 x s16> = zext s16  <-- scalar to vector

      // <2 x s16> = zext s16  <-- scalar to vector

      // Which is invalid.

      // Instead we would want to generate:

      // s32 = zext s16

      // <2 x s16> = bitcast s32

      // s32 = zext s16

      // <2 x s16> = bitcast s32

      //

      // That is not done yet.

      if (ConvertOp == 0)

        return true;

      return !DestTy.isVector() && OpTy.isVector() &&

             DestTy == OpTy.getElementType();

    case TargetOpcode::G_CONCAT_VECTORS: {

      if (ConvertOp == 0)

        return true;

      if (!DestTy.isVector())

        return false;

      const unsigned OpEltSize = OpTy.getElementType().getSizeInBits();

      // Don't handle scalarization with a cast that isn't in the same

      // direction as the vector cast. This could be handled, but it would

      // require more intermediate unmerges.

      if (ConvertOp == TargetOpcode::G_TRUNC)

        return DestTy.getSizeInBits() <= OpEltSize;

      return DestTy.getSizeInBits() >= OpEltSize;

    }

    }

  }

  /// Try to replace DstReg with SrcReg or build a COPY instruction

  /// depending on the register constraints.

  static void replaceRegOrBuildCopy(Register DstReg, Register SrcReg,

                                    MachineRegisterInfo &MRI,

                                    MachineIRBuilder &Builder,

                                    SmallVectorImpl<Register> &UpdatedDefs,

                                    GISelChangeObserver &Observer) {

    if (!llvm::canReplaceReg(DstReg, SrcReg, MRI)) {

      Builder.buildCopy(DstReg, SrcReg);

      UpdatedDefs.push_back(DstReg);

      return;

    }

    SmallVector<MachineInstr *, 4> UseMIs;

    // Get the users and notify the observer before replacing.

    for (auto &UseMI : MRI.use_instructions(DstReg)) {

      UseMIs.push_back(&UseMI);

      Observer.changingInstr(UseMI);

    }

    // Replace the registers.

    MRI.replaceRegWith(DstReg, SrcReg);

    UpdatedDefs.push_back(SrcReg);

    // Notify the observer that we changed the instructions.

    for (auto *UseMI : UseMIs)

      Observer.changedInstr(*UseMI);

  }

  /// Return the operand index in \p MI that defines \p Def

  static unsigned getDefIndex(const MachineInstr &MI, Register SearchDef) {

    unsigned DefIdx = 0;

    for (const MachineOperand &Def : MI.defs()) {

      if (Def.getReg() == SearchDef)

        break;

      ++DefIdx;

    }

    return DefIdx;

  }

  /// This class provides utilities for finding source registers of specific

  /// bit ranges in an artifact. The routines can look through the source

  /// registers if they're other artifacts to try to find a non-artifact source

  /// of a value.

  class ArtifactValueFinder {

    MachineRegisterInfo &MRI;

    MachineIRBuilder &MIB;

    const LegalizerInfo &LI;

    // Stores the best register found in the current query so far.

    Register CurrentBest = Register();

    /// Given an concat_vector op \p Concat and a start bit and size, try to

    /// find the origin of the value defined by that start position and size.

    ///

    /// \returns a register with the requested size, or the current best

    /// register found during the current query.

    Register findValueFromConcat(GConcatVectors &Concat, unsigned StartBit,

                                 unsigned Size) {

      assert(Size > 0);

      // Find the source operand that provides the bits requested.

      Register Src1Reg = Concat.getSourceReg(0);

      unsigned SrcSize = MRI.getType(Src1Reg).getSizeInBits();

      // Operand index of the source that provides the start of the bit range.

      unsigned StartSrcIdx = (StartBit / SrcSize) + 1;

      // Offset into the source at which the bit range starts.

      unsigned InRegOffset = StartBit % SrcSize;

      // Check that the bits don't span multiple sources.

      // FIXME: we might be able return multiple sources? Or create an

      // appropriate concat to make it fit.

      if (InRegOffset + Size > SrcSize)

        return CurrentBest;

      Register SrcReg = Concat.getReg(StartSrcIdx);

      if (InRegOffset == 0 && Size == SrcSize) {

        CurrentBest = SrcReg;

        return findValueFromDefImpl(SrcReg, 0, Size);

      }

      return findValueFromDefImpl(SrcReg, InRegOffset, Size);

    }

    /// Given an build_vector op \p BV and a start bit and size, try to find

    /// the origin of the value defined by that start position and size.

    ///

    /// \returns a register with the requested size, or the current best

    /// register found during the current query.

    Register findValueFromBuildVector(GBuildVector &BV, unsigned StartBit,

                                      unsigned Size) {

      assert(Size > 0);

      // Find the source operand that provides the bits requested.

      Register Src1Reg = BV.getSourceReg(0);

      unsigned SrcSize = MRI.getType(Src1Reg).getSizeInBits();

      // Operand index of the source that provides the start of the bit range.

      unsigned StartSrcIdx = (StartBit / SrcSize) + 1;

      // Offset into the source at which the bit range starts.

      unsigned InRegOffset = StartBit % SrcSize;

      if (InRegOffset != 0)

        return CurrentBest; // Give up, bits don't start at a scalar source.

      if (Size < SrcSize)

        return CurrentBest; // Scalar source is too large for requested bits.

      // If the bits cover multiple sources evenly, then create a new

      // build_vector to synthesize the required size, if that's been requested.

      if (Size > SrcSize) {

        if (Size % SrcSize > 0)

          return CurrentBest; // Isn't covered exactly by sources.

        unsigned NumSrcsUsed = Size / SrcSize;

        // If we're requesting all of the sources, just return this def.

        if (NumSrcsUsed == BV.getNumSources())

          return BV.getReg(0);

        LLT SrcTy = MRI.getType(Src1Reg);

        LLT NewBVTy = LLT::fixed_vector(NumSrcsUsed, SrcTy);

        // Check if the resulting build vector would be legal.

        LegalizeActionStep ActionStep =

            LI.getAction({TargetOpcode::G_BUILD_VECTOR, {NewBVTy, SrcTy}});

        if (ActionStep.Action != LegalizeActions::Legal)

          return CurrentBest;

        SmallVector<Register> NewSrcs;

        for (unsigned SrcIdx = StartSrcIdx; SrcIdx < StartSrcIdx + NumSrcsUsed;

             ++SrcIdx)

          NewSrcs.push_back(BV.getReg(SrcIdx));

        MIB.setInstrAndDebugLoc(BV);

        return MIB.buildBuildVector(NewBVTy, NewSrcs).getReg(0);

      }

      // A single source is requested, just return it.

      return BV.getReg(StartSrcIdx);

    }

    /// Given an G_INSERT op \p MI and a start bit and size, try to find

    /// the origin of the value defined by that start position and size.

    ///

    /// \returns a register with the requested size, or the current best

    /// register found during the current query.

    Register findValueFromInsert(MachineInstr &MI, unsigned StartBit,

                                 unsigned Size) {

      assert(MI.getOpcode() == TargetOpcode::G_INSERT);

      assert(Size > 0);

      Register ContainerSrcReg = MI.getOperand(1).getReg();

      Register InsertedReg = MI.getOperand(2).getReg();

      LLT InsertedRegTy = MRI.getType(InsertedReg);

      unsigned InsertOffset = MI.getOperand(3).getImm();

      // There are 4 possible container/insertreg + requested bit-range layouts

      // that the instruction and query could be representing.

      // For: %_ = G_INSERT %CONTAINER, %INS, InsOff (abbrev. to 'IO')

      // and a start bit 'SB', with size S, giving an end bit 'EB', we could

      // have...

      // Scenario A:

      //   --------------------------

      //  |  INS    |  CONTAINER     |

      //   --------------------------

      //       |   |

      //       SB  EB

      //

      // Scenario B:

      //   --------------------------

      //  |  INS    |  CONTAINER     |

      //   --------------------------

      //                |    |

      //                SB   EB

      //

      // Scenario C:

      //   --------------------------

      //  |  CONTAINER    |  INS     |

      //   --------------------------

      //       |    |

      //       SB   EB

      //

      // Scenario D:

      //   --------------------------

      //  |  CONTAINER    |  INS     |

      //   --------------------------

      //                     |   |

      //                     SB  EB

      //

      // So therefore, A and D are requesting data from the INS operand, while

      // B and C are requesting from the container operand.

      unsigned InsertedEndBit = InsertOffset + InsertedRegTy.getSizeInBits();

      unsigned EndBit = StartBit + Size;

      unsigned NewStartBit;

      Register SrcRegToUse;

      if (EndBit <= InsertOffset || InsertedEndBit <= StartBit) {

        SrcRegToUse = ContainerSrcReg;

        NewStartBit = StartBit;

        return findValueFromDefImpl(SrcRegToUse, NewStartBit, Size);

      }

      if (InsertOffset <= StartBit && EndBit <= InsertedEndBit) {

        SrcRegToUse = InsertedReg;

        NewStartBit = StartBit - InsertOffset;

        if (NewStartBit == 0 &&

            Size == MRI.getType(SrcRegToUse).getSizeInBits())

          CurrentBest = SrcRegToUse;

        return findValueFromDefImpl(SrcRegToUse, NewStartBit, Size);

      }

      // The bit range spans both the inserted and container regions.

      return Register();

    }

    /// Internal implementation for findValueFromDef(). findValueFromDef()

    /// initializes some data like the CurrentBest register, which this method

    /// and its callees rely upon.

    Register findValueFromDefImpl(Register DefReg, unsigned StartBit,

                                  unsigned Size) {

      std::optional<DefinitionAndSourceRegister> DefSrcReg =

          getDefSrcRegIgnoringCopies(DefReg, MRI);

      MachineInstr *Def = DefSrcReg->MI;

      DefReg = DefSrcReg->Reg;

      // If the instruction has a single def, then simply delegate the search.

      // For unmerge however with multiple defs, we need to compute the offset

      // into the source of the unmerge.

      switch (Def->getOpcode()) {

      case TargetOpcode::G_CONCAT_VECTORS:

        return findValueFromConcat(cast<GConcatVectors>(*Def), StartBit, Size);

      case TargetOpcode::G_UNMERGE_VALUES: {

        unsigned DefStartBit = 0;

        unsigned DefSize = MRI.getType(DefReg).getSizeInBits();

        for (const auto &MO : Def->defs()) {

          if (MO.getReg() == DefReg)

            break;

          DefStartBit += DefSize;

        }

        Register SrcReg = Def->getOperand(Def->getNumOperands() - 1).getReg();

        Register SrcOriginReg =

            findValueFromDefImpl(SrcReg, StartBit + DefStartBit, Size);

        if (SrcOriginReg)

          return SrcOriginReg;

        // Failed to find a further value. If the StartBit and Size perfectly

        // covered the requested DefReg, return that since it's better than

        // nothing.

        if (StartBit == 0 && Size == DefSize)

          return DefReg;