[GlobalISel] Match LLVM legalization value tracking

5 files changed, 1884 insertions, 9 deletions

diff --git a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
index b7064e3..3b01e9b 100644
--- a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
+++ b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
@@ -3,16 +3,19 @@
 set(
   RCCBackendGlobalISelSources
   GISelChangeObserver.cpp
+  GISelValueTracking.cpp
   InstructionSelect.cpp
   Legalizer.cpp
   LegalizerHelper.cpp
   LegalizerInfo.cpp
   RegBankSelect.cpp
+  Utils.cpp
 )
 
 set(
   RCCBackendGlobalISelHeaders
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelWorkList.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/InstructionSelect.h"
@@ -22,25 +25,30 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/RegBankSelect.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/Utils.h"
 )
 
 target_sources(RCCBackendCodeGen PRIVATE ${RCCBackendGlobalISelSources})
 
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/Legalizer.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerHelper.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelect.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/Utils.cpp"
   ${RCCBackendGlobalISelHeaders}
 )
 
 rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/Legalizer.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerHelper.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelect.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/Utils.cpp"
 )
diff --git a/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp
new file mode 100644
index 0000000..fe694ab
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp
@@ -0,0 +1,514 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/GISelValueTracking.h"
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] std::optional<Register> registerOperand(const MachineInstr &Instruction,
+                                                      std::size_t Index) noexcept {
+  const MachineOperand *Operand = Instruction.operandAt(Index);
+  return Operand == nullptr ? std::nullopt : Operand->registerValue();
+}
+
+[[nodiscard]] Expected<APInt> zero(std::uint32_t BitWidth) {
+  return APInt::fromUnsigned(BitWidth, 0);
+}
+
+[[nodiscard]] Expected<APInt> resizeMask(const APInt &Value, std::uint32_t BitWidth) {
+  if (Value.bitWidth() == BitWidth)
+    return Value;
+  if (Value.bitWidth() == 0)
+    return zero(BitWidth);
+  if (Value.bitWidth() < BitWidth)
+    return Value.zext(BitWidth);
+  return Value.trunc(BitWidth);
+}
+
+[[nodiscard]] Expected<APInt> highBitsMask(std::uint32_t BitWidth, std::uint32_t LowBitCount) {
+  auto LowBits = APInt::getLowBitsSet(BitWidth, LowBitCount);
+  if (!LowBits)
+    return std::unexpected(LowBits.error());
+  return LowBits->bitwiseNot();
+}
+
+[[nodiscard]] Expected<APInt> mergeMasks(const APInt &Left, const APInt &Right) {
+  return Left.bitwiseOr(Right);
+}
+
+[[nodiscard]] Expected<APInt> intersectMasks(const APInt &Left, const APInt &Right) {
+  return Left.bitwiseAnd(Right);
+}
+
+[[nodiscard]] Expected<APInt> constantAtWidth(const APInt &Value, std::uint32_t BitWidth) {
+  return resizeMask(Value, BitWidth);
+}
+
+[[nodiscard]] std::optional<std::uint32_t>
+constantShiftAmount(Register Reg, const MachineRegisterInfo &MRI, std::uint32_t BitWidth) {
+  const MachineInstr *Definition = MRI.getVRegDef(Reg);
+  if (Definition == nullptr || Definition->opcode() != opcode(GenericOpcode::G_CONSTANT))
+    return std::nullopt;
+  const MachineOperand *ValueOperand = Definition->operandAt(1);
+  const auto *Immediate =
+      ValueOperand == nullptr ? nullptr : ValueOperand->getIf<IntegerImmediateOperand>();
+  if (Immediate == nullptr || Immediate->Value.activeBitWidth() > 32)
+    return std::nullopt;
+  const std::uint64_t Amount = Immediate->Value.word(0);
+  if (Amount >= BitWidth)
+    return std::nullopt;
+  return static_cast<std::uint32_t>(Amount);
+}
+
+[[nodiscard]] Expected<APInt> shiftMaskLeft(const APInt &Value, std::uint32_t Amount) {
+  std::vector<std::uint64_t> Words(Value.words().size(), 0);
+  for (std::uint32_t Bit = 0; Bit + Amount < Value.bitWidth(); ++Bit) {
+    if (Value.testBit(Bit)) {
+      const std::uint32_t DestinationBit = Bit + Amount;
+      Words[DestinationBit / 64U] |= std::uint64_t{1} << (DestinationBit % 64U);
+    }
+  }
+  return APInt::create(Value.bitWidth(), Words);
+}
+
+[[nodiscard]] Expected<APInt> shiftMaskRight(const APInt &Value, std::uint32_t Amount) {
+  std::vector<std::uint64_t> Words(Value.words().size(), 0);
+  for (std::uint32_t Bit = Amount; Bit < Value.bitWidth(); ++Bit) {
+    if (Value.testBit(Bit)) {
+      const std::uint32_t DestinationBit = Bit - Amount;
+      Words[DestinationBit / 64U] |= std::uint64_t{1} << (DestinationBit % 64U);
+    }
+  }
+  return APInt::create(Value.bitWidth(), Words);
+}
+
+[[nodiscard]] std::uint32_t constantNumSignBits(const APInt &Value) noexcept {
+  if (Value.bitWidth() == 0)
+    return 1;
+  if (Value.isNegative())
+    return static_cast<std::uint32_t>(Value.countlOne());
+  auto Inverted = Value.bitwiseNot();
+  return Inverted ? static_cast<std::uint32_t>(Inverted->countlOne()) : 1U;
+}
+
+} // namespace
+
+GISelValueTracking::GISelValueTracking(MachineFunction &Function, const TargetDescription &Target,
+                                       unsigned MaxDepth) noexcept
+    : Function(Function), MRI(Function.registerInfo()), Target(Target), MaxDepth(MaxDepth) {}
+
+Expected<GISelValueTracking::KnownBits>
+GISelValueTracking::makeUnknown(std::uint32_t BitWidth) const {
+  auto Zero = zero(BitWidth);
+  if (!Zero)
+    return std::unexpected(Zero.error());
+  auto One = zero(BitWidth);
+  if (!One)
+    return std::unexpected(One.error());
+  return KnownBits{.Zero = std::move(*Zero), .One = std::move(*One)};
+}
+
+Expected<GISelValueTracking::KnownBits> GISelValueTracking::getKnownBits(Register Reg,
+                                                                         unsigned Depth) const {
+  auto Type = MRI.getType(Reg);
+  if (!Type)
+    return std::unexpected(Type.error());
+  const std::uint32_t BitWidth = Type->scalarBitWidth();
+  auto Unknown = makeUnknown(BitWidth);
+  if (!Unknown)
+    return std::unexpected(Unknown.error());
+  if (Depth >= MaxDepth)
+    return Unknown;
+
+  const MachineInstr *Definition = MRI.getVRegDef(Reg);
+  if (Definition == nullptr)
+    return Unknown;
+
+  const auto Opcode = static_cast<GenericOpcode>(Definition->opcode().value());
+  if (Opcode == GenericOpcode::G_CONSTANT) {
+    const MachineOperand *ValueOperand = Definition->operandAt(1);
+    const auto *Immediate =
+        ValueOperand == nullptr ? nullptr : ValueOperand->getIf<IntegerImmediateOperand>();
+    if (Immediate == nullptr)
+      return Unknown;
+    auto Value = constantAtWidth(Immediate->Value, BitWidth);
+    if (!Value)
+      return std::unexpected(Value.error());
+    auto KnownZero = Value->bitwiseNot();
+    if (!KnownZero)
+      return std::unexpected(KnownZero.error());
+    return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*Value)};
+  }
+
+  if (Opcode == GenericOpcode::COPY) {
+    const auto Source = registerOperand(*Definition, 1);
+    if (!Source || !Source->isVirtual())
+      return Unknown;
+    auto SourceBits = getKnownBits(*Source, Depth);
+    if (!SourceBits)
+      return std::unexpected(SourceBits.error());
+    auto KnownZero = resizeMask(SourceBits->Zero, BitWidth);
+    if (!KnownZero)
+      return std::unexpected(KnownZero.error());
+    auto KnownOne = resizeMask(SourceBits->One, BitWidth);
+    if (!KnownOne)
+      return std::unexpected(KnownOne.error());
+    return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+  }
+
+  if (Opcode == GenericOpcode::G_ICMP || Opcode == GenericOpcode::G_FCMP) {
+    if (!Type->isVector() && BitWidth > 1 &&
+        Target.getBooleanContents(false, Opcode == GenericOpcode::G_FCMP) ==
+            BooleanContent::ZeroOrOne) {
+      auto KnownZero = highBitsMask(BitWidth, 1);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+      Unknown->Zero = std::move(*KnownZero);
+    }
+    return Unknown;
+  }
+
+  switch (Opcode) {
+  case GenericOpcode::G_UADDO:
+  case GenericOpcode::G_UADDE:
+  case GenericOpcode::G_USUBO:
+  case GenericOpcode::G_USUBE:
+  case GenericOpcode::G_SADDO:
+  case GenericOpcode::G_SADDE:
+  case GenericOpcode::G_SSUBO:
+  case GenericOpcode::G_SSUBE:
+  case GenericOpcode::G_UMULO:
+  case GenericOpcode::G_SMULO: {
+    const auto BooleanResult = registerOperand(*Definition, 1);
+    if (BooleanResult && *BooleanResult == Reg && !Type->isVector() && BitWidth > 1 &&
+        Target.getBooleanContents(false, false) == BooleanContent::ZeroOrOne) {
+      auto KnownZero = highBitsMask(BitWidth, 1);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+      Unknown->Zero = std::move(*KnownZero);
+    }
+    return Unknown;
+  }
+  default:
+    break;
+  }
+
+  const auto Source = registerOperand(*Definition, 1);
+  if (!Source)
+    return Unknown;
+
+  if (Opcode == GenericOpcode::G_TRUNC || Opcode == GenericOpcode::G_ANYEXT ||
+      Opcode == GenericOpcode::G_ZEXT || Opcode == GenericOpcode::G_SEXT ||
+      Opcode == GenericOpcode::G_ASSERT_ZEXT || Opcode == GenericOpcode::G_ASSERT_SEXT ||
+      Opcode == GenericOpcode::G_SEXT_INREG) {
+    auto SourceBits = getKnownBits(*Source, Depth + 1U);
+    if (!SourceBits)
+      return std::unexpected(SourceBits.error());
+    auto SourceType = MRI.getType(*Source);
+    if (!SourceType)
+      return std::unexpected(SourceType.error());
+    const std::uint32_t SourceWidth = SourceType->scalarBitWidth();
+    auto KnownZero = resizeMask(SourceBits->Zero, BitWidth);
+    if (!KnownZero)
+      return std::unexpected(KnownZero.error());
+    auto KnownOne = resizeMask(SourceBits->One, BitWidth);
+    if (!KnownOne)
+      return std::unexpected(KnownOne.error());
+
+    if (Opcode == GenericOpcode::G_ZEXT && SourceWidth < BitWidth) {
+      auto HighZero = highBitsMask(BitWidth, SourceWidth);
+      if (!HighZero)
+        return std::unexpected(HighZero.error());
+      KnownZero = mergeMasks(*KnownZero, *HighZero);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+    }
+
+    std::uint32_t ExtendedFrom = SourceWidth;
+    if (Opcode == GenericOpcode::G_ASSERT_ZEXT || Opcode == GenericOpcode::G_ASSERT_SEXT ||
+        Opcode == GenericOpcode::G_SEXT_INREG) {
+      const MachineOperand *WidthOperand = Definition->operandAt(2);
+      const auto *Width = WidthOperand == nullptr ? nullptr : WidthOperand->getIf<std::int64_t>();
+      if (Width == nullptr || *Width <= 0 || static_cast<std::uint64_t>(*Width) > BitWidth)
+        return Unknown;
+      ExtendedFrom = static_cast<std::uint32_t>(*Width);
+    }
+
+    if (Opcode == GenericOpcode::G_ASSERT_ZEXT) {
+      auto HighZero = highBitsMask(BitWidth, ExtendedFrom);
+      if (!HighZero)
+        return std::unexpected(HighZero.error());
+      KnownZero = mergeMasks(*KnownZero, *HighZero);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+    }
+
+    if ((Opcode == GenericOpcode::G_SEXT || Opcode == GenericOpcode::G_ASSERT_SEXT ||
+         Opcode == GenericOpcode::G_SEXT_INREG) &&
+        ExtendedFrom < BitWidth) {
+      auto HighBits = highBitsMask(BitWidth, ExtendedFrom);
+      if (!HighBits)
+        return std::unexpected(HighBits.error());
+      if (KnownZero->testBit(ExtendedFrom - 1U)) {
+        KnownZero = mergeMasks(*KnownZero, *HighBits);
+        if (!KnownZero)
+          return std::unexpected(KnownZero.error());
+      } else if (KnownOne->testBit(ExtendedFrom - 1U)) {
+        KnownOne = mergeMasks(*KnownOne, *HighBits);
+        if (!KnownOne)
+          return std::unexpected(KnownOne.error());
+      }
+    }
+
+    return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+  }
+
+  if (Opcode == GenericOpcode::G_AND || Opcode == GenericOpcode::G_OR ||
+      Opcode == GenericOpcode::G_XOR) {
+    const auto Right = registerOperand(*Definition, 2);
+    if (!Right)
+      return Unknown;
+    auto LeftBits = getKnownBits(*Source, Depth + 1U);
+    if (!LeftBits)
+      return std::unexpected(LeftBits.error());
+    auto RightBits = getKnownBits(*Right, Depth + 1U);
+    if (!RightBits)
+      return std::unexpected(RightBits.error());
+
+    if (Opcode == GenericOpcode::G_AND) {
+      auto KnownZero = mergeMasks(LeftBits->Zero, RightBits->Zero);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+      auto KnownOne = intersectMasks(LeftBits->One, RightBits->One);
+      if (!KnownOne)
+        return std::unexpected(KnownOne.error());
+      return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+    }
+    if (Opcode == GenericOpcode::G_OR) {
+      auto KnownZero = intersectMasks(LeftBits->Zero, RightBits->Zero);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+      auto KnownOne = mergeMasks(LeftBits->One, RightBits->One);
+      if (!KnownOne)
+        return std::unexpected(KnownOne.error());
+      return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+    }
+
+    auto BothZero = intersectMasks(LeftBits->Zero, RightBits->Zero);
+    if (!BothZero)
+      return std::unexpected(BothZero.error());
+    auto BothOne = intersectMasks(LeftBits->One, RightBits->One);
+    if (!BothOne)
+      return std::unexpected(BothOne.error());
+    auto KnownZero = mergeMasks(*BothZero, *BothOne);
+    if (!KnownZero)
+      return std::unexpected(KnownZero.error());
+    auto LeftZeroRightOne = intersectMasks(LeftBits->Zero, RightBits->One);
+    if (!LeftZeroRightOne)
+      return std::unexpected(LeftZeroRightOne.error());
+    auto LeftOneRightZero = intersectMasks(LeftBits->One, RightBits->Zero);
+    if (!LeftOneRightZero)
+      return std::unexpected(LeftOneRightZero.error());
+    auto KnownOne = mergeMasks(*LeftZeroRightOne, *LeftOneRightZero);
+    if (!KnownOne)
+      return std::unexpected(KnownOne.error());
+    return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+  }
+
+  if (Opcode == GenericOpcode::G_SHL || Opcode == GenericOpcode::G_LSHR ||
+      Opcode == GenericOpcode::G_ASHR) {
+    const auto AmountReg = registerOperand(*Definition, 2);
+    if (!AmountReg)
+      return Unknown;
+    const auto Amount = constantShiftAmount(*AmountReg, MRI, BitWidth);
+    if (!Amount)
+      return Unknown;
+    auto SourceBits = getKnownBits(*Source, Depth + 1U);
+    if (!SourceBits)
+      return std::unexpected(SourceBits.error());
+
+    if (Opcode == GenericOpcode::G_SHL) {
+      auto KnownZero = shiftMaskLeft(SourceBits->Zero, *Amount);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+      auto LowZero = APInt::getLowBitsSet(BitWidth, *Amount);
+      if (!LowZero)
+        return std::unexpected(LowZero.error());
+      KnownZero = mergeMasks(*KnownZero, *LowZero);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+      auto KnownOne = shiftMaskLeft(SourceBits->One, *Amount);
+      if (!KnownOne)
+        return std::unexpected(KnownOne.error());
+      return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+    }
+
+    auto KnownZero = shiftMaskRight(SourceBits->Zero, *Amount);
+    if (!KnownZero)
+      return std::unexpected(KnownZero.error());
+    auto KnownOne = shiftMaskRight(SourceBits->One, *Amount);
+    if (!KnownOne)
+      return std::unexpected(KnownOne.error());
+    auto HighBits = highBitsMask(BitWidth, BitWidth - *Amount);
+    if (!HighBits)
+      return std::unexpected(HighBits.error());
+    if (Opcode == GenericOpcode::G_LSHR || SourceBits->Zero.testBit(BitWidth - 1U)) {
+      KnownZero = mergeMasks(*KnownZero, *HighBits);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+    } else if (SourceBits->One.testBit(BitWidth - 1U)) {
+      KnownOne = mergeMasks(*KnownOne, *HighBits);
+      if (!KnownOne)
+        return std::unexpected(KnownOne.error());
+    }
+    return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+  }
+
+  return Unknown;
+}
+
+Expected<APInt> GISelValueTracking::getKnownZeroes(Register Reg) const {
+  auto Known = getKnownBits(Reg);
+  if (!Known)
+    return std::unexpected(Known.error());
+  return std::move(Known->Zero);
+}
+
+Expected<std::uint32_t> GISelValueTracking::computeNumSignBits(Register Reg, unsigned Depth) const {
+  auto Type = MRI.getType(Reg);
+  if (!Type)
+    return std::unexpected(Type.error());
+  const std::uint32_t BitWidth = Type->scalarBitWidth();
+  if (Depth >= MaxDepth)
+    return 1U;
+
+  const MachineInstr *Definition = MRI.getVRegDef(Reg);
+  if (Definition == nullptr)
+    return 1U;
+  const auto Opcode = static_cast<GenericOpcode>(Definition->opcode().value());
+
+  if (Opcode == GenericOpcode::G_CONSTANT) {
+    const MachineOperand *ValueOperand = Definition->operandAt(1);
+    const auto *Immediate =
+        ValueOperand == nullptr ? nullptr : ValueOperand->getIf<IntegerImmediateOperand>();
+    if (Immediate == nullptr)
+      return 1U;
+    auto Value = constantAtWidth(Immediate->Value, BitWidth);
+    if (!Value)
+      return std::unexpected(Value.error());
+    return constantNumSignBits(*Value);
+  }
+
+  const auto Source = registerOperand(*Definition, 1);
+  if (Opcode == GenericOpcode::COPY && Source && Source->isVirtual())
+    return computeNumSignBits(*Source, Depth);
+
+  if (Opcode == GenericOpcode::G_SEXT && Source) {
+    auto SourceType = MRI.getType(*Source);
+    if (!SourceType)
+      return std::unexpected(SourceType.error());
+    auto SourceSignBits = computeNumSignBits(*Source, Depth + 1U);
+    if (!SourceSignBits)
+      return std::unexpected(SourceSignBits.error());
+    return std::min(BitWidth, *SourceSignBits + BitWidth - SourceType->scalarBitWidth());
+  }
+
+  if ((Opcode == GenericOpcode::G_ASSERT_SEXT || Opcode == GenericOpcode::G_SEXT_INREG) && Source) {
+    const MachineOperand *WidthOperand = Definition->operandAt(2);
+    const auto *Width = WidthOperand == nullptr ? nullptr : WidthOperand->getIf<std::int64_t>();
+    if (Width != nullptr && *Width > 0 && static_cast<std::uint64_t>(*Width) <= BitWidth) {
+      auto SourceSignBits = computeNumSignBits(*Source, Depth + 1U);
+      if (!SourceSignBits)
+        return std::unexpected(SourceSignBits.error());
+      return std::max(*SourceSignBits, BitWidth - static_cast<std::uint32_t>(*Width) + 1U);
+    }
+  }
+
+  if ((Opcode == GenericOpcode::G_AND || Opcode == GenericOpcode::G_OR ||
+       Opcode == GenericOpcode::G_XOR) &&
+      Source) {
+    const auto Right = registerOperand(*Definition, 2);
+    if (Right) {
+      auto LeftSignBits = computeNumSignBits(*Source, Depth + 1U);
+      if (!LeftSignBits)
+        return std::unexpected(LeftSignBits.error());
+      if (*LeftSignBits != 1) {
+        auto RightSignBits = computeNumSignBits(*Right, Depth + 1U);
+        if (!RightSignBits)
+          return std::unexpected(RightSignBits.error());
+        if (*RightSignBits != 1)
+          return std::min(*LeftSignBits, *RightSignBits);
+      }
+    }
+  }
+
+  if (Opcode == GenericOpcode::G_TRUNC && Source) {
+    auto SourceType = MRI.getType(*Source);
+    if (!SourceType)
+      return std::unexpected(SourceType.error());
+    const std::uint32_t SourceWidth = SourceType->scalarBitWidth();
+    auto SourceSignBits = computeNumSignBits(*Source, Depth + 1U);
+    if (!SourceSignBits)
+      return std::unexpected(SourceSignBits.error());
+    if (SourceWidth > BitWidth && *SourceSignBits > SourceWidth - BitWidth)
+      return *SourceSignBits - (SourceWidth - BitWidth);
+  }
+
+  if (Opcode == GenericOpcode::G_ICMP || Opcode == GenericOpcode::G_FCMP) {
+    if (BitWidth > 1) {
+      const BooleanContent Contents =
+          Target.getBooleanContents(Type->isVector(), Opcode == GenericOpcode::G_FCMP);
+      if (Contents == BooleanContent::ZeroOrNegativeOne)
+        return BitWidth;
+      if (Contents == BooleanContent::ZeroOrOne)
+        return BitWidth - 1U;
+    }
+  }
+
+  switch (Opcode) {
+  case GenericOpcode::G_UADDO:
+  case GenericOpcode::G_UADDE:
+  case GenericOpcode::G_USUBO:
+  case GenericOpcode::G_USUBE:
+  case GenericOpcode::G_SADDO:
+  case GenericOpcode::G_SADDE:
+  case GenericOpcode::G_SSUBO:
+  case GenericOpcode::G_SSUBE:
+  case GenericOpcode::G_UMULO:
+  case GenericOpcode::G_SMULO: {
+    const auto BooleanResult = registerOperand(*Definition, 1);
+    if (BooleanResult && *BooleanResult == Reg &&
+        Target.getBooleanContents(Type->isVector(), false) == BooleanContent::ZeroOrNegativeOne)
+      return BitWidth;
+    break;
+  }
+  default:
+    break;
+  }
+
+  auto Known = getKnownBits(Reg, Depth);
+  if (!Known)
+    return std::unexpected(Known.error());
+  std::uint32_t KnownSignBits = 1;
+  if (Known->Zero.testBit(BitWidth - 1U))
+    KnownSignBits = static_cast<std::uint32_t>(Known->Zero.countlOne());
+  else if (Known->One.testBit(BitWidth - 1U))
+    KnownSignBits = static_cast<std::uint32_t>(Known->One.countlOne());
+  return std::max(1U, KnownSignBits);
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
index d971b42..c749039 100644
--- a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
+++ b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
@@ -4,9 +4,11 @@
 
 #include "rcc/CodeGen/GenericOpcodes.h"
 #include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
+#include "rcc/CodeGen/GlobalISel/GISelValueTracking.h"
 #include "rcc/CodeGen/GlobalISel/GISelWorkList.h"
 #include "rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
 #include "rcc/CodeGen/GlobalISel/LegalizerHelper.h"
+#include "rcc/CodeGen/GlobalISel/Utils.h"
 #include "rcc/CodeGen/LiveVariables.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
 #include "rcc/CodeGen/MachineFunction.h"
@@ -295,7 +297,9 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi
   MachineFunctionDelegateInstaller ObserverInstaller(Function, Observer);
   MachineIRBuilder Builder(Function, Target);
   LegalizerHelper Helper(Function, *Info, Observer, Builder);
-  LegalizationArtifactCombiner ArtifactCombiner(Builder, Function.registerInfo(), *Info);
+  GISelValueTracking ValueTracking(Function, Target);
+  LegalizationArtifactCombiner ArtifactCombiner(Builder, Function.registerInfo(), *Info,
+                                                &ValueTracking);
 
   do {
     while (!InstructionWorklist.empty()) {
@@ -303,6 +307,15 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi
       if (Instruction == nullptr || Instruction->parent() == nullptr)
         continue;
 
+      if (isTriviallyDead(*Instruction, Function.registerInfo(), Target)) {
+        auto Removed = eraseInstr(*Instruction, Function.registerInfo(), Target);
+        if (!Removed)
+          return std::unexpected(Removed.error());
+        Result.Changed = true;
+        Result.Changes.add(MachinePassChange::Instructions);
+        continue;
+      }
+
       const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
       if (Descriptor == nullptr)
         return std::unexpected(
@@ -381,19 +394,23 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi
       MachineInstr *Instruction = ArtifactWorklist.popBack();
       if (Instruction == nullptr || Instruction->parent() == nullptr)
         continue;
+      if (isTriviallyDead(*Instruction, Function.registerInfo(), Target)) {
+        auto Removed = eraseInstr(*Instruction, Function.registerInfo(), Target);
+        if (!Removed)
+          return std::unexpected(Removed.error());
+        Result.Changed = true;
+        Result.Changes.add(MachinePassChange::Instructions);
+        continue;
+      }
       std::vector<MachineInstr *> DeadInstructions;
       auto Combined =
           ArtifactCombiner.tryCombineInstruction(*Instruction, DeadInstructions, Observer);
       if (!Combined)
         return std::unexpected(Combined.error());
       if (*Combined) {
-        for (MachineInstr *Dead : DeadInstructions) {
-          if (Dead == nullptr || Dead->parent() == nullptr)
-            continue;
-          auto Removed = Dead->parent()->removeInstruction(*Dead);
-          if (!Removed)
-            return std::unexpected(Removed.error());
-        }
+        auto Removed = eraseInstrs(DeadInstructions, Function.registerInfo(), Target);
+        if (!Removed)
+          return std::unexpected(Removed.error());
         Result.Changed = true;
         Result.Changes.add(MachinePassChange::Instructions);
         continue;
diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp
index 1e52214..0ea3783 100644
--- a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp
+++ b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp
@@ -3,6 +3,7 @@
 #include "rcc/CodeGen/GlobalISel/LegalizerHelper.h"
 
 #include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
+#include "rcc/CodeGen/GlobalISel/Utils.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineInstr.h"
@@ -14,7 +15,9 @@
 #include <bit>
 #include <cstddef>
 #include <cstdint>
+#include <numeric>
 #include <optional>
+#include <span>
 #include <utility>
 
 namespace rcc {
@@ -113,6 +116,539 @@ LegalizerHelper::LegalizerHelper(MachineFunction &Function, const LegalizerInfo
     : MIRBuilder(MIRBuilder), Observer(Observer), Function(Function), MRI(Function.registerInfo()),
       Info(Info) {}
 
+Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction,
+                                                       std::size_t TypeIndex,
+                                                       LowLevelType WideType) {
+  if (TypeIndex != 1)
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "G_MERGE_VALUES widening requires type index one");
+  if (Instruction.operandCount() < 3)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "G_MERGE_VALUES requires a destination and sources");
+
+  const Register *Destination = Instruction.operandAt(0)->getIf<Register>();
+  const Register *FirstSource = Instruction.operandAt(1)->getIf<Register>();
+  if (Destination == nullptr || FirstSource == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "G_MERGE_VALUES requires register operands");
+  auto DestinationType = MRI.getType(*Destination);
+  auto SourceType = MRI.getType(*FirstSource);
+  if (!DestinationType)
+    return std::unexpected(DestinationType.error());
+  if (!SourceType)
+    return std::unexpected(SourceType.error());
+  if (DestinationType->isVector())
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "vector G_MERGE_VALUES widening is not supported");
+
+  const std::uint64_t DestinationSize = DestinationType->minimumBitWidth();
+  const std::uint64_t SourceSize = SourceType->minimumBitWidth();
+  const std::uint64_t WideSize = WideType.minimumBitWidth();
+  const std::uint64_t MergeCount = (DestinationSize + WideSize - 1U) / WideSize;
+  const std::size_t SourceCount = Instruction.operandCount() - 1U;
+  const std::uint64_t PartSize = DestinationSize / SourceCount;
+
+  if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+    return std::unexpected(Point.error());
+
+  if (WideSize >= DestinationSize) {
+    auto Result = MRI.createVirtualRegister(WideType);
+    if (!Result)
+      return std::unexpected(Result.error());
+    if (auto Built = MIRBuilder.buildZExt(*Result, *FirstSource); !Built)
+      return std::unexpected(Built.error());
+    Register ResultRegister = *Result;
+
+    for (std::size_t Index = 2; Index != Instruction.operandCount(); ++Index) {
+      const Register *Source = Instruction.operandAt(Index)->getIf<Register>();
+      if (Source == nullptr)
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "G_MERGE_VALUES requires register sources");
+      auto ActualSourceType = MRI.getType(*Source);
+      if (!ActualSourceType)
+        return std::unexpected(ActualSourceType.error());
+      if (*ActualSourceType != *SourceType || ActualSourceType->minimumBitWidth() != PartSize)
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "G_MERGE_VALUES source types are inconsistent");
+
+      auto ExtendedInput = MRI.createVirtualRegister(WideType);
+      auto ShiftAmount = MRI.createVirtualRegister(WideType);
+      auto ShiftedInput = MRI.createVirtualRegister(WideType);
+      if (!ExtendedInput)
+        return std::unexpected(ExtendedInput.error());
+      if (!ShiftAmount)
+        return std::unexpected(ShiftAmount.error());
+      if (!ShiftedInput)
+        return std::unexpected(ShiftedInput.error());
+      if (auto Built = MIRBuilder.buildZExt(*ExtendedInput, *Source); !Built)
+        return std::unexpected(Built.error());
+      if (auto Built = MIRBuilder.buildConstant(*ShiftAmount,
+                                                static_cast<std::int64_t>((Index - 1U) * PartSize));
+          !Built)
+        return std::unexpected(Built.error());
+      if (auto Built = MIRBuilder.buildShl(*ShiftedInput, *ExtendedInput, *ShiftAmount); !Built)
+        return std::unexpected(Built.error());
+
+      Register NextResult = *Destination;
+      if (Index + 1U != Instruction.operandCount() || WideType != *DestinationType) {
+        auto NewResult = MRI.createVirtualRegister(WideType);
+        if (!NewResult)
+          return std::unexpected(NewResult.error());
+        NextResult = *NewResult;
+      }
+      if (auto Built = MIRBuilder.buildOr(NextResult, ResultRegister, *ShiftedInput); !Built)
+        return std::unexpected(Built.error());
+      ResultRegister = NextResult;
+    }
+
+    if (WideSize > DestinationSize) {
+      if (auto Built = MIRBuilder.buildTrunc(*Destination, ResultRegister); !Built)
+        return std::unexpected(Built.error());
+    } else if (DestinationType->isPointer()) {
+      if (auto Built = MIRBuilder.buildIntToPtr(*Destination, ResultRegister); !Built)
+        return std::unexpected(Built.error());
+    }
+
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::InternalError,
+                            "G_MERGE_VALUES became detached during widening");
+    return Block->removeInstruction(Instruction);
+  }
+
+  auto GCDType = LowLevelType::makeCategoryNeutralScalar(std::gcd(SourceSize, WideSize));
+  auto WideDestinationType = LowLevelType::makeCategoryNeutralScalar(MergeCount * WideSize);
+  if (!GCDType)
+    return std::unexpected(GCDType.error());
+  if (!WideDestinationType)
+    return std::unexpected(WideDestinationType.error());
+
+  std::vector<Register> UnmergedRegisters;
+  for (std::size_t Index = 1; Index != Instruction.operandCount(); ++Index) {
+    const Register *Source = Instruction.operandAt(Index)->getIf<Register>();
+    if (Source == nullptr)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "G_MERGE_VALUES requires register sources");
+    if (GCDType->minimumBitWidth() == SourceSize) {
+      UnmergedRegisters.push_back(*Source);
+      continue;
+    }
+    auto Extracted = extractGCDType(UnmergedRegisters, *GCDType, *Source);
+    if (!Extracted)
+      return std::unexpected(Extracted.error());
+  }
+
+  const std::uint64_t RequiredPartCount = MergeCount * WideSize;
+  if (UnmergedRegisters.size() != RequiredPartCount) {
+    auto UndefRegister = MRI.createVirtualRegister(*GCDType);
+    if (!UndefRegister)
+      return std::unexpected(UndefRegister.error());
+    if (auto Built = MIRBuilder.buildUndef(*UndefRegister); !Built)
+      return std::unexpected(Built.error());
+    while (UnmergedRegisters.size() != RequiredPartCount)
+      UnmergedRegisters.push_back(*UndefRegister);
+  }
+
+  const std::size_t PartsPerGCD = static_cast<std::size_t>(WideSize / GCDType->minimumBitWidth());
+  std::vector<Register> NewMergeRegisters;
+  NewMergeRegisters.reserve(static_cast<std::size_t>(MergeCount));
+  for (std::size_t Index = 0; Index != MergeCount; ++Index) {
+    std::vector<Register> Parts(
+        UnmergedRegisters.begin() + static_cast<std::ptrdiff_t>(Index * PartsPerGCD),
+        UnmergedRegisters.begin() + static_cast<std::ptrdiff_t>((Index + 1U) * PartsPerGCD));
+    auto MergeRegister = MRI.createVirtualRegister(WideType);
+    if (!MergeRegister)
+      return std::unexpected(MergeRegister.error());
+    if (auto Built = MIRBuilder.buildMergeLikeInstr(*MergeRegister, Parts); !Built)
+      return std::unexpected(Built.error());
+    NewMergeRegisters.push_back(*MergeRegister);
+  }
+
+  if (DestinationSize == WideDestinationType->minimumBitWidth()) {
+    if (auto Built = MIRBuilder.buildMergeLikeInstr(*Destination, NewMergeRegisters); !Built)
+      return std::unexpected(Built.error());
+  } else {
+    auto FinalMerge = MRI.createVirtualRegister(*WideDestinationType);
+    if (!FinalMerge)
+      return std::unexpected(FinalMerge.error());
+    if (auto Built = MIRBuilder.buildMergeLikeInstr(*FinalMerge, NewMergeRegisters); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildTrunc(*Destination, *FinalMerge); !Built)
+      return std::unexpected(Built.error());
+  }
+
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "G_MERGE_VALUES became detached during widening");
+  return Block->removeInstruction(Instruction);
+}
+
+Expected<void> LegalizerHelper::widenScalarUnmergeValues(MachineInstr &Instruction,
+                                                         std::size_t TypeIndex,
+                                                         LowLevelType WideType) {
+  if (TypeIndex != 0)
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "G_UNMERGE_VALUES widening requires type index zero");
+  if (Instruction.operandCount() < 2)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "G_UNMERGE_VALUES requires destinations and a source");
+
+  const std::size_t DestinationCount = Instruction.operandCount() - 1U;
+  const Register *Source = Instruction.operandAt(DestinationCount)->getIf<Register>();
+  const Register *FirstDestination = Instruction.operandAt(0)->getIf<Register>();
+  if (Source == nullptr || FirstDestination == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "G_UNMERGE_VALUES requires register operands");
+  auto SourceType = MRI.getType(*Source);
+  auto DestinationType = MRI.getType(*FirstDestination);
+  if (!SourceType)
+    return std::unexpected(SourceType.error());
+  if (!DestinationType)
+    return std::unexpected(DestinationType.error());
+  if (SourceType->isVector() || !DestinationType->isCategoryNeutralScalar())
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "G_UNMERGE_VALUES widening requires scalar types");
+
+  if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+    return std::unexpected(Point.error());
+
+  Register SourceRegister = *Source;
+  if (WideType.minimumBitWidth() >= SourceType->minimumBitWidth()) {
+    if (SourceType->isPointer()) {
+      auto IntegerSourceType =
+          LowLevelType::makeCategoryNeutralScalar(SourceType->minimumBitWidth());
+      if (!IntegerSourceType)
+        return std::unexpected(IntegerSourceType.error());
+      auto IntegerSource = MRI.createVirtualRegister(*IntegerSourceType);
+      if (!IntegerSource)
+        return std::unexpected(IntegerSource.error());
+      if (auto Built = MIRBuilder.buildPtrToInt(*IntegerSource, SourceRegister); !Built)
+        return std::unexpected(Built.error());
+      *SourceType = *IntegerSourceType;
+      SourceRegister = *IntegerSource;
+    }
+
+    if (WideType.minimumBitWidth() > SourceType->minimumBitWidth()) {
+      auto WideSource = MRI.createVirtualRegister(WideType);
+      if (!WideSource)
+        return std::unexpected(WideSource.error());
+      if (auto Built = MIRBuilder.buildAnyExt(*WideSource, SourceRegister); !Built)
+        return std::unexpected(Built.error());
+      *SourceType = WideType;
+      SourceRegister = *WideSource;
+    }
+
+    const std::uint64_t DestinationSize = DestinationType->minimumBitWidth();
+    if (auto Built = MIRBuilder.buildTrunc(*FirstDestination, SourceRegister); !Built)
+      return std::unexpected(Built.error());
+    for (std::size_t Index = 1; Index != DestinationCount; ++Index) {
+      const Register *Destination = Instruction.operandAt(Index)->getIf<Register>();
+      if (Destination == nullptr)
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "G_UNMERGE_VALUES requires register destinations");
+      auto ShiftAmount = MRI.createVirtualRegister(*SourceType);
+      auto ShiftedSource = MRI.createVirtualRegister(*SourceType);
+      if (!ShiftAmount)
+        return std::unexpected(ShiftAmount.error());
+      if (!ShiftedSource)
+        return std::unexpected(ShiftedSource.error());
+      if (auto Built = MIRBuilder.buildConstant(*ShiftAmount,
+                                                static_cast<std::int64_t>(DestinationSize * Index));
+          !Built)
+        return std::unexpected(Built.error());
+      if (auto Built = MIRBuilder.buildLShr(*ShiftedSource, SourceRegister, *ShiftAmount); !Built)
+        return std::unexpected(Built.error());
+      if (auto Built = MIRBuilder.buildTrunc(*Destination, *ShiftedSource); !Built)
+        return std::unexpected(Built.error());
+    }
+
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::InternalError,
+                            "G_UNMERGE_VALUES became detached during widening");
+    return Block->removeInstruction(Instruction);
+  }
+
+  auto LCMType = getLCMType(*SourceType, WideType);
+  if (!LCMType)
+    return std::unexpected(LCMType.error());
+  Register WideSource = SourceRegister;
+  if (LCMType->minimumBitWidth() != SourceType->minimumBitWidth()) {
+    if (SourceType->isPointer())
+      return makeUnexpected(ErrorCode::Unsupported,
+                            "widening a pointer G_UNMERGE_VALUES source is not implemented");
+    auto ExtendedSource = MRI.createVirtualRegister(*LCMType);
+    if (!ExtendedSource)
+      return std::unexpected(ExtendedSource.error());
+    if (auto Built = MIRBuilder.buildAnyExt(*ExtendedSource, WideSource); !Built)
+      return std::unexpected(Built.error());
+    WideSource = *ExtendedSource;
+  }
+
+  const std::size_t UnmergeCount =
+      static_cast<std::size_t>(LCMType->minimumBitWidth() / WideType.minimumBitWidth());
+  std::vector<Register> UnmergeRegisters;
+  UnmergeRegisters.reserve(UnmergeCount);
+  for (std::size_t Index = 0; Index != UnmergeCount; ++Index) {
+    auto Part = MRI.createVirtualRegister(WideType);
+    if (!Part)
+      return std::unexpected(Part.error());
+    UnmergeRegisters.push_back(*Part);
+  }
+  if (auto Built = MIRBuilder.buildUnmergeValues(UnmergeRegisters, WideSource); !Built)
+    return std::unexpected(Built.error());
+
+  auto GCDType = getGCDType(WideType, *DestinationType);
+  if (!GCDType)
+    return std::unexpected(GCDType.error());
+  const std::size_t PartsPerRemerge =
+      static_cast<std::size_t>(DestinationType->minimumBitWidth() / GCDType->minimumBitWidth());
+
+  if (PartsPerRemerge == 1) {
+    const std::size_t PartsPerUnmerge =
+        static_cast<std::size_t>(WideType.minimumBitWidth() / DestinationType->minimumBitWidth());
+    for (std::size_t Index = 0; Index != UnmergeRegisters.size(); ++Index) {
+      std::vector<Register> Destinations;
+      Destinations.reserve(PartsPerUnmerge);
+      for (std::size_t PartIndex = 0; PartIndex != PartsPerUnmerge; ++PartIndex) {
+        const std::size_t DestinationIndex = Index * PartsPerUnmerge + PartIndex;
+        if (DestinationIndex < DestinationCount) {
+          const Register *Destination = Instruction.operandAt(DestinationIndex)->getIf<Register>();
+          if (Destination == nullptr)
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "G_UNMERGE_VALUES requires register destinations");
+          Destinations.push_back(*Destination);
+        } else {
+          auto DeadDestination = MRI.createVirtualRegister(*DestinationType);
+          if (!DeadDestination)
+            return std::unexpected(DeadDestination.error());
+          Destinations.push_back(*DeadDestination);
+        }
+      }
+      if (auto Built = MIRBuilder.buildUnmergeValues(Destinations, UnmergeRegisters[Index]); !Built)
+        return std::unexpected(Built.error());
+    }
+  } else {
+    std::vector<Register> Parts;
+    for (Register UnmergeRegister : UnmergeRegisters) {
+      auto Extracted = extractGCDType(Parts, *GCDType, UnmergeRegister);
+      if (!Extracted)
+        return std::unexpected(Extracted.error());
+    }
+    for (std::size_t Index = 0; Index != DestinationCount; ++Index) {
+      const Register *Destination = Instruction.operandAt(Index)->getIf<Register>();
+      if (Destination == nullptr)
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "G_UNMERGE_VALUES requires register destinations");
+      std::vector<Register> RemergeParts(
+          Parts.begin() + static_cast<std::ptrdiff_t>(Index * PartsPerRemerge),
+          Parts.begin() + static_cast<std::ptrdiff_t>((Index + 1U) * PartsPerRemerge));
+      if (auto Built = MIRBuilder.buildMergeLikeInstr(*Destination, RemergeParts); !Built)
+        return std::unexpected(Built.error());
+    }
+  }
+
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "G_UNMERGE_VALUES became detached during widening");
+  return Block->removeInstruction(Instruction);
+}
+
+Expected<void> LegalizerHelper::insertParts(Register Destination, LowLevelType ResultType,
+                                            LowLevelType PartType,
+                                            const std::vector<Register> &PartRegisters,
+                                            LowLevelType LeftoverType,
+                                            const std::vector<Register> &LeftoverRegisters) {
+  if (!LeftoverType.isValid()) {
+    if (!LeftoverRegisters.empty())
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "leftover registers require a leftover type");
+    return MIRBuilder.buildMergeLikeInstr(Destination, PartRegisters).transform([](MachineInstr *) {
+    });
+  }
+
+  if (ResultType.isVector()) {
+    if (LeftoverRegisters.size() != 1)
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "mixed subvector merge requires one leftover register");
+    std::vector<Register> AllRegisters = PartRegisters;
+    AllRegisters.insert(AllRegisters.end(), LeftoverRegisters.begin(), LeftoverRegisters.end());
+    return MIRBuilder.buildMergeLikeInstr(Destination, AllRegisters).transform([](MachineInstr *) {
+    });
+  }
+
+  std::vector<Register> GCDRegisters;
+  auto FirstGCD = getGCDType(ResultType, LeftoverType);
+  if (!FirstGCD)
+    return std::unexpected(FirstGCD.error());
+  auto GCDType = getGCDType(*FirstGCD, PartType);
+  if (!GCDType)
+    return std::unexpected(GCDType.error());
+  for (Register Part : PartRegisters) {
+    auto Extracted = extractGCDType(GCDRegisters, *GCDType, Part);
+    if (!Extracted)
+      return std::unexpected(Extracted.error());
+  }
+  for (Register Part : LeftoverRegisters) {
+    auto Extracted = extractGCDType(GCDRegisters, *GCDType, Part);
+    if (!Extracted)
+      return std::unexpected(Extracted.error());
+  }
+  auto LCMType = buildLCMMergePieces(ResultType, LeftoverType, *GCDType, GCDRegisters);
+  if (!LCMType)
+    return std::unexpected(LCMType.error());
+  return buildWidenedRemergeToDst(Destination, *LCMType, GCDRegisters);
+}
+
+Expected<void> LegalizerHelper::extractGCDType(std::vector<Register> &Parts, LowLevelType GCDType,
+                                               Register Source) {
+  auto SourceType = MRI.getType(Source);
+  if (!SourceType)
+    return std::unexpected(SourceType.error());
+  if (*SourceType == GCDType) {
+    Parts.push_back(Source);
+    return {};
+  }
+  const std::uint64_t SourceSize = SourceType->minimumBitWidth();
+  const std::uint64_t GCDSize = GCDType.minimumBitWidth();
+  if (GCDSize == 0 || SourceSize % GCDSize != 0)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "GCD type does not evenly divide the source type");
+  return extractParts(Source, GCDType, static_cast<int>(SourceSize / GCDSize), Parts, MIRBuilder,
+                      MRI);
+}
+
+Expected<LowLevelType> LegalizerHelper::extractGCDType(std::vector<Register> &Parts,
+                                                       LowLevelType DestinationType,
+                                                       LowLevelType NarrowType, Register Source) {
+  auto SourceType = MRI.getType(Source);
+  if (!SourceType)
+    return std::unexpected(SourceType.error());
+  auto FirstGCD = getGCDType(*SourceType, NarrowType);
+  if (!FirstGCD)
+    return std::unexpected(FirstGCD.error());
+  auto GCDType = getGCDType(*FirstGCD, DestinationType);
+  if (!GCDType)
+    return std::unexpected(GCDType.error());
+  auto Extracted = extractGCDType(Parts, *GCDType, Source);
+  if (!Extracted)
+    return std::unexpected(Extracted.error());
+  return *GCDType;
+}
+
+Expected<LowLevelType> LegalizerHelper::buildLCMMergePieces(LowLevelType DestinationType,
+                                                            LowLevelType NarrowType,
+                                                            LowLevelType GCDType,
+                                                            std::vector<Register> &Registers,
+                                                            GenericOpcode PadStrategy) {
+  auto LCMType = getLCMType(DestinationType, NarrowType);
+  if (!LCMType)
+    return std::unexpected(LCMType.error());
+  const int PartCount = static_cast<int>(LCMType->minimumBitWidth() / NarrowType.minimumBitWidth());
+  const int SubPartCount =
+      static_cast<int>(NarrowType.minimumBitWidth() / GCDType.minimumBitWidth());
+  const int OriginalSourceCount = static_cast<int>(Registers.size());
+
+  Register PadRegister;
+  if (OriginalSourceCount < PartCount * SubPartCount) {
+    auto NewPad = MRI.createVirtualRegister(GCDType);
+    if (!NewPad)
+      return std::unexpected(NewPad.error());
+    PadRegister = *NewPad;
+    Expected<MachineInstr *> Built = PadStrategy == GenericOpcode::G_ZEXT
+                                         ? MIRBuilder.buildConstant(PadRegister, 0)
+                                         : MIRBuilder.buildUndef(PadRegister);
+    if (!Built)
+      return std::unexpected(Built.error());
+  }
+
+  std::vector<Register> Remerge(static_cast<std::size_t>(PartCount));
+  std::vector<Register> SubMerge(static_cast<std::size_t>(SubPartCount));
+  Register AllPadRegister;
+  for (int PartIndex = 0; PartIndex != PartCount; ++PartIndex) {
+    bool AllMergePartsArePadding = true;
+    for (int SubPartIndex = 0; SubPartIndex != SubPartCount; ++SubPartIndex) {
+      const int Index = PartIndex * SubPartCount + SubPartIndex;
+      if (Index >= OriginalSourceCount) {
+        SubMerge[static_cast<std::size_t>(SubPartIndex)] = PadRegister;
+        continue;
+      }
+      SubMerge[static_cast<std::size_t>(SubPartIndex)] = Registers[static_cast<std::size_t>(Index)];
+      AllMergePartsArePadding = false;
+    }
+
+    if (AllMergePartsArePadding && AllPadRegister.isNoRegister()) {
+      auto Pad = MRI.createVirtualRegister(NarrowType);
+      if (!Pad)
+        return std::unexpected(Pad.error());
+      AllPadRegister = *Pad;
+      Expected<MachineInstr *> Built = PadStrategy == GenericOpcode::G_ZEXT
+                                           ? MIRBuilder.buildConstant(AllPadRegister, 0)
+                                           : MIRBuilder.buildUndef(AllPadRegister);
+      if (!Built)
+        return std::unexpected(Built.error());
+    }
+    if (!AllPadRegister.isNoRegister()) {
+      Remerge[static_cast<std::size_t>(PartIndex)] = AllPadRegister;
+      continue;
+    }
+    if (SubPartCount == 1) {
+      Remerge[static_cast<std::size_t>(PartIndex)] = SubMerge.front();
+    } else {
+      auto RemergeRegister = MRI.createVirtualRegister(NarrowType);
+      if (!RemergeRegister)
+        return std::unexpected(RemergeRegister.error());
+      auto Built = MIRBuilder.buildMergeLikeInstr(*RemergeRegister, SubMerge);
+      if (!Built)
+        return std::unexpected(Built.error());
+      Remerge[static_cast<std::size_t>(PartIndex)] = *RemergeRegister;
+    }
+    if (AllMergePartsArePadding && AllPadRegister.isNoRegister())
+      AllPadRegister = Remerge[static_cast<std::size_t>(PartIndex)];
+  }
+  Registers = std::move(Remerge);
+  return *LCMType;
+}
+
+Expected<void>
+LegalizerHelper::buildWidenedRemergeToDst(Register Destination, LowLevelType LCMType,
+                                          const std::vector<Register> &RemergeRegisters) {
+  auto DestinationType = MRI.getType(Destination);
+  if (!DestinationType)
+    return std::unexpected(DestinationType.error());
+  if (*DestinationType == LCMType)
+    return MIRBuilder.buildMergeLikeInstr(Destination, RemergeRegisters)
+        .transform([](MachineInstr *) {});
+
+  auto Remerge = MRI.createVirtualRegister(LCMType);
+  if (!Remerge)
+    return std::unexpected(Remerge.error());
+  auto BuiltMerge = MIRBuilder.buildMergeLikeInstr(*Remerge, RemergeRegisters);
+  if (!BuiltMerge)
+    return std::unexpected(BuiltMerge.error());
+  if (!DestinationType->isVector() && !LCMType.isVector())
+    return MIRBuilder.buildTrunc(Destination, *Remerge).transform([](MachineInstr *) {});
+
+  if (LCMType.isVector()) {
+    const std::size_t DefinitionCount =
+        static_cast<std::size_t>(LCMType.minimumBitWidth() / DestinationType->minimumBitWidth());
+    std::vector<Register> Definitions;
+    Definitions.reserve(DefinitionCount);
+    Definitions.push_back(Destination);
+    for (std::size_t Index = 1; Index != DefinitionCount; ++Index) {
+      auto Definition = MRI.createVirtualRegister(*DestinationType);
+      if (!Definition)
+        return std::unexpected(Definition.error());
+      Definitions.push_back(*Definition);
+    }
+    return MIRBuilder.buildUnmergeValues(Definitions, *Remerge).transform([](MachineInstr *) {});
+  }
+  return makeUnexpected(ErrorCode::Unsupported,
+                        "widened remerge has an unsupported type combination");
+}
+
 Expected<void> LegalizerHelper::widenScalarSrc(MachineInstr &Instruction, LowLevelType WideType,
                                                std::size_t OperandIndex,
                                                GenericOpcode ExtensionOpcode) {
@@ -192,6 +728,10 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
 
   Observer.changingInstr(Instruction);
   switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
+  case GenericOpcode::G_MERGE_VALUES:
+    return widenScalarMergeValues(Instruction, TypeIndex, WideType);
+  case GenericOpcode::G_UNMERGE_VALUES:
+    return widenScalarUnmergeValues(Instruction, TypeIndex, WideType);
   case GenericOpcode::G_ATOMICRMW_XCHG:
   case GenericOpcode::G_ATOMICRMW_ADD:
   case GenericOpcode::G_ATOMICRMW_SUB:
@@ -408,6 +948,232 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
   return {};
 }
 
+Expected<void> LegalizerHelper::narrowScalarAddSub(MachineInstr &Instruction, std::size_t TypeIndex,
+                                                   LowLevelType NarrowType) {
+  if (TypeIndex != 0)
+    return makeUnexpected(ErrorCode::Unsupported, "add/sub narrowing requires type index zero");
+
+  const MachineOperand *DestinationOperand = Instruction.operandAt(0);
+  const Register *Destination =
+      DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+  if (Destination == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "add/sub narrowing requires a register destination");
+  auto DestinationType = MRI.getType(*Destination);
+  if (!DestinationType)
+    return std::unexpected(DestinationType.error());
+  if (DestinationType->isVector())
+    return makeUnexpected(ErrorCode::Unsupported, "vector add/sub narrowing is not implemented");
+  if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+    return std::unexpected(Point.error());
+
+  GenericOpcode FirstOpcode;
+  GenericOpcode MiddleOpcode;
+  GenericOpcode FinalOpcode;
+  switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
+  case GenericOpcode::G_SADDO:
+  case GenericOpcode::G_SADDE:
+  case GenericOpcode::G_UADDO:
+  case GenericOpcode::G_UADDE:
+  case GenericOpcode::G_ADD:
+    FirstOpcode = GenericOpcode::G_UADDO;
+    MiddleOpcode = GenericOpcode::G_UADDE;
+    FinalOpcode = Instruction.opcode() == opcode(GenericOpcode::G_SADDO) ||
+                          Instruction.opcode() == opcode(GenericOpcode::G_SADDE)
+                      ? GenericOpcode::G_SADDE
+                      : GenericOpcode::G_UADDE;
+    break;
+  case GenericOpcode::G_SSUBO:
+  case GenericOpcode::G_SSUBE:
+  case GenericOpcode::G_USUBO:
+  case GenericOpcode::G_USUBE:
+  case GenericOpcode::G_SUB:
+    FirstOpcode = GenericOpcode::G_USUBO;
+    MiddleOpcode = GenericOpcode::G_USUBE;
+    FinalOpcode = Instruction.opcode() == opcode(GenericOpcode::G_SSUBO) ||
+                          Instruction.opcode() == opcode(GenericOpcode::G_SSUBE)
+                      ? GenericOpcode::G_SSUBE
+                      : GenericOpcode::G_USUBE;
+    break;
+  default:
+    return makeUnexpected(ErrorCode::InternalError,
+                          "unexpected add/sub opcode during scalar narrowing");
+  }
+
+  const InstructionDescriptor *Descriptor =
+      MIRBuilder.target().instructionDescriptor(Instruction.opcode());
+  if (Descriptor == nullptr)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "add/sub narrowing has no instruction descriptor");
+  const std::size_t DefinitionCount = Descriptor->NumExplicitDefs;
+  const MachineOperand *FirstSourceOperand = Instruction.operandAt(DefinitionCount);
+  const MachineOperand *SecondSourceOperand = Instruction.operandAt(DefinitionCount + 1);
+  const Register *FirstSource =
+      FirstSourceOperand == nullptr ? nullptr : FirstSourceOperand->getIf<Register>();
+  const Register *SecondSource =
+      SecondSourceOperand == nullptr ? nullptr : SecondSourceOperand->getIf<Register>();
+  if (FirstSource == nullptr || SecondSource == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "add/sub narrowing requires two register sources");
+
+  Register CarryDestination;
+  Register CarryIn;
+  if (DefinitionCount == 2) {
+    const MachineOperand *CarryOperand = Instruction.operandAt(1);
+    const Register *Carry = CarryOperand == nullptr ? nullptr : CarryOperand->getIf<Register>();
+    if (Carry == nullptr)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "add/sub narrowing has an invalid carry destination");
+    CarryDestination = *Carry;
+  }
+  if (Instruction.operandCount() == DefinitionCount + 3) {
+    const MachineOperand *CarryOperand = Instruction.operandAt(DefinitionCount + 2);
+    const Register *Carry = CarryOperand == nullptr ? nullptr : CarryOperand->getIf<Register>();
+    if (Carry == nullptr)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "add/sub narrowing has an invalid carry input");
+    CarryIn = *Carry;
+  }
+
+  LowLevelType LeftoverType;
+  LowLevelType DummyType;
+  std::vector<Register> FirstParts;
+  std::vector<Register> SecondParts;
+  std::vector<Register> FirstLeftovers;
+  std::vector<Register> SecondLeftovers;
+  std::vector<Register> DestinationParts;
+  auto FirstExtracted = extractParts(*FirstSource, *DestinationType, NarrowType, LeftoverType,
+                                     FirstParts, FirstLeftovers, MIRBuilder, MRI);
+  if (!FirstExtracted)
+    return std::unexpected(FirstExtracted.error());
+  auto SecondExtracted = extractParts(*SecondSource, *DestinationType, NarrowType, DummyType,
+                                      SecondParts, SecondLeftovers, MIRBuilder, MRI);
+  if (!SecondExtracted)
+    return std::unexpected(SecondExtracted.error());
+
+  const std::size_t NarrowPartCount = FirstParts.size();
+  FirstParts.insert(FirstParts.end(), FirstLeftovers.begin(), FirstLeftovers.end());
+  SecondParts.insert(SecondParts.end(), SecondLeftovers.begin(), SecondLeftovers.end());
+  if (FirstParts.size() != SecondParts.size())
+    return makeUnexpected(ErrorCode::InternalError,
+                          "add/sub source splits have different part counts");
+  DestinationParts.reserve(FirstParts.size());
+
+  auto BooleanType = LowLevelType::makeCategoryNeutralScalar(1);
+  if (!BooleanType)
+    return std::unexpected(BooleanType.error());
+  for (std::size_t Index = 0; Index != FirstParts.size(); ++Index) {
+    auto PartType = MRI.getType(FirstParts[Index]);
+    if (!PartType)
+      return std::unexpected(PartType.error());
+    auto PartDestination = MRI.createVirtualRegister(*PartType);
+    if (!PartDestination)
+      return std::unexpected(PartDestination.error());
+
+    Register CarryOut;
+    if (Index + 1 == FirstParts.size() && !CarryDestination.isNoRegister()) {
+      CarryOut = CarryDestination;
+    } else {
+      auto NewCarry = MRI.createVirtualRegister(*BooleanType);
+      if (!NewCarry)
+        return std::unexpected(NewCarry.error());
+      CarryOut = *NewCarry;
+    }
+
+    Expected<MachineInstr *> Built;
+    if (CarryIn.isNoRegister()) {
+      Built = MIRBuilder.buildInstr(opcode(FirstOpcode), {*PartDestination, CarryOut},
+                                    {FirstParts[Index], SecondParts[Index]});
+    } else if (Index + 1 == FirstParts.size()) {
+      Built = MIRBuilder.buildInstr(opcode(FinalOpcode), {*PartDestination, CarryOut},
+                                    {FirstParts[Index], SecondParts[Index], CarryIn});
+    } else {
+      Built = MIRBuilder.buildInstr(opcode(MiddleOpcode), {*PartDestination, CarryOut},
+                                    {FirstParts[Index], SecondParts[Index], CarryIn});
+    }
+    if (!Built)
+      return std::unexpected(Built.error());
+    DestinationParts.push_back(*PartDestination);
+    CarryIn = CarryOut;
+  }
+
+  std::vector<Register> MainDestinations(DestinationParts.begin(),
+                                         DestinationParts.begin() +
+                                             static_cast<std::ptrdiff_t>(NarrowPartCount));
+  std::vector<Register> LeftoverDestinations(DestinationParts.begin() +
+                                                 static_cast<std::ptrdiff_t>(NarrowPartCount),
+                                             DestinationParts.end());
+  auto Inserted = insertParts(*Destination, *DestinationType, NarrowType, MainDestinations,
+                              LeftoverType, LeftoverDestinations);
+  if (!Inserted)
+    return std::unexpected(Inserted.error());
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "add/sub instruction became detached during narrowing");
+  return Block->removeInstruction(Instruction);
+}
+
+Expected<void> LegalizerHelper::narrowScalarExt(MachineInstr &Instruction, std::size_t TypeIndex,
+                                                LowLevelType NarrowType) {
+  if (TypeIndex != 0)
+    return makeUnexpected(ErrorCode::Unsupported, "extension narrowing requires type index zero");
+
+  const auto Destination = Instruction.operandAt(0)->registerValue();
+  const auto Source = Instruction.operandAt(1)->registerValue();
+  if (!Destination || !Source)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "extension narrowing requires register operands");
+
+  auto DestinationType = MRI.getType(*Destination);
+  if (!DestinationType)
+    return std::unexpected(DestinationType.error());
+  if (DestinationType->isVector())
+    return makeUnexpected(ErrorCode::Unsupported, "vector extension narrowing is not implemented");
+
+  std::vector<Register> Parts;
+  auto GCDType = extractGCDType(Parts, *DestinationType, NarrowType, *Source);
+  if (!GCDType)
+    return std::unexpected(GCDType.error());
+  auto LCMType = buildLCMMergePieces(*DestinationType, NarrowType, *GCDType, Parts,
+                                     static_cast<GenericOpcode>(Instruction.opcode().value()));
+  if (!LCMType)
+    return std::unexpected(LCMType.error());
+  auto Remerged = buildWidenedRemergeToDst(*Destination, *LCMType, Parts);
+  if (!Remerged)
+    return std::unexpected(Remerged.error());
+
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "extension instruction became detached during narrowing");
+  return Block->removeInstruction(Instruction);
+}
+
+Expected<void> LegalizerHelper::narrowScalar(MachineInstr &Instruction, std::size_t TypeIndex,
+                                             LowLevelType NarrowType) {
+  switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
+  case GenericOpcode::G_ADD:
+  case GenericOpcode::G_SUB:
+  case GenericOpcode::G_SADDO:
+  case GenericOpcode::G_SSUBO:
+  case GenericOpcode::G_SADDE:
+  case GenericOpcode::G_SSUBE:
+  case GenericOpcode::G_UADDO:
+  case GenericOpcode::G_USUBO:
+  case GenericOpcode::G_UADDE:
+  case GenericOpcode::G_USUBE:
+    return narrowScalarAddSub(Instruction, TypeIndex, NarrowType);
+  case GenericOpcode::G_SEXT:
+  case GenericOpcode::G_ZEXT:
+  case GenericOpcode::G_ANYEXT:
+    return narrowScalarExt(Instruction, TypeIndex, NarrowType);
+  default:
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "scalar narrowing is not implemented for this opcode");
+  }
+}
+
 Expected<void> LegalizerHelper::lowerVAArg(MachineInstr &Instruction) {
   if (Instruction.opcode() != opcode(GenericOpcode::G_VAARG) || Instruction.operandCount() != 3 ||
       !Instruction.memOperands().empty()) {
@@ -550,6 +1316,166 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
   switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
   case GenericOpcode::G_VAARG:
     return lowerVAArg(Instruction);
+  case GenericOpcode::G_UADDO: {
+    const Register Result = *Instruction.operandAt(0)->getIf<Register>();
+    const Register CarryOut = *Instruction.operandAt(1)->getIf<Register>();
+    const Register Left = *Instruction.operandAt(2)->getIf<Register>();
+    const Register Right = *Instruction.operandAt(3)->getIf<Register>();
+    auto NewResult = MRI.cloneVirtualRegister(Result);
+    if (!NewResult)
+      return std::unexpected(NewResult.error());
+    if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+      return std::unexpected(Point.error());
+    if (auto Built = MIRBuilder.buildAdd(*NewResult, Left, Right); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built =
+            MIRBuilder.buildICmp(IntegerPredicate::UnsignedLessThan, CarryOut, *NewResult, Right);
+        !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildCopy(Result, *NewResult); !Built)
+      return std::unexpected(Built.error());
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "G_UADDO became detached during lowering");
+    return Block->removeInstruction(Instruction);
+  }
+  case GenericOpcode::G_UADDE: {
+    const Register Result = *Instruction.operandAt(0)->getIf<Register>();
+    const Register CarryOut = *Instruction.operandAt(1)->getIf<Register>();
+    const Register Left = *Instruction.operandAt(2)->getIf<Register>();
+    const Register Right = *Instruction.operandAt(3)->getIf<Register>();
+    const Register CarryIn = *Instruction.operandAt(4)->getIf<Register>();
+    auto ResultType = MRI.getType(Result);
+    auto ConditionType = MRI.getType(CarryOut);
+    if (!ResultType)
+      return std::unexpected(ResultType.error());
+    if (!ConditionType)
+      return std::unexpected(ConditionType.error());
+    auto NewResult = MRI.cloneVirtualRegister(Result);
+    auto TemporaryResult = MRI.createVirtualRegister(*ResultType);
+    auto Carry = MRI.createVirtualRegister(*ConditionType);
+    auto ExtendedCarryIn = MRI.createVirtualRegister(*ResultType);
+    auto Zero = MRI.createVirtualRegister(*ResultType);
+    auto ResultIsZero = MRI.createVirtualRegister(*ConditionType);
+    auto SecondCarry = MRI.createVirtualRegister(*ConditionType);
+    if (!NewResult)
+      return std::unexpected(NewResult.error());
+    if (!TemporaryResult)
+      return std::unexpected(TemporaryResult.error());
+    if (!Carry)
+      return std::unexpected(Carry.error());
+    if (!ExtendedCarryIn)
+      return std::unexpected(ExtendedCarryIn.error());
+    if (!Zero)
+      return std::unexpected(Zero.error());
+    if (!ResultIsZero)
+      return std::unexpected(ResultIsZero.error());
+    if (!SecondCarry)
+      return std::unexpected(SecondCarry.error());
+    if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+      return std::unexpected(Point.error());
+    if (auto Built = MIRBuilder.buildAdd(*TemporaryResult, Left, Right); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::UnsignedLessThan, *Carry,
+                                          *TemporaryResult, Left);
+        !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildZExt(*ExtendedCarryIn, CarryIn); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildAdd(*NewResult, *TemporaryResult, *ExtendedCarryIn); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildConstant(*Zero, 0); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built =
+            MIRBuilder.buildICmp(IntegerPredicate::Equal, *ResultIsZero, *NewResult, *Zero);
+        !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildAnd(*SecondCarry, *ResultIsZero, CarryIn); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildOr(CarryOut, *Carry, *SecondCarry); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildCopy(Result, *NewResult); !Built)
+      return std::unexpected(Built.error());
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "G_UADDE became detached during lowering");
+    return Block->removeInstruction(Instruction);
+  }
+  case GenericOpcode::G_USUBO: {
+    const Register Result = *Instruction.operandAt(0)->getIf<Register>();
+    const Register BorrowOut = *Instruction.operandAt(1)->getIf<Register>();
+    const Register Left = *Instruction.operandAt(2)->getIf<Register>();
+    const Register Right = *Instruction.operandAt(3)->getIf<Register>();
+    if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+      return std::unexpected(Point.error());
+    if (auto Built = MIRBuilder.buildSub(Result, Left, Right); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built =
+            MIRBuilder.buildICmp(IntegerPredicate::UnsignedLessThan, BorrowOut, Left, Right);
+        !Built)
+      return std::unexpected(Built.error());
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "G_USUBO became detached during lowering");
+    return Block->removeInstruction(Instruction);
+  }
+  case GenericOpcode::G_USUBE: {
+    const Register Result = *Instruction.operandAt(0)->getIf<Register>();
+    const Register BorrowOut = *Instruction.operandAt(1)->getIf<Register>();
+    const Register Left = *Instruction.operandAt(2)->getIf<Register>();
+    const Register Right = *Instruction.operandAt(3)->getIf<Register>();
+    const Register BorrowIn = *Instruction.operandAt(4)->getIf<Register>();
+    auto ResultType = MRI.getType(Result);
+    auto ConditionType = MRI.getType(BorrowOut);
+    if (!ResultType)
+      return std::unexpected(ResultType.error());
+    if (!ConditionType)
+      return std::unexpected(ConditionType.error());
+    auto TemporaryResult = MRI.createVirtualRegister(*ResultType);
+    auto Borrow = MRI.createVirtualRegister(*ConditionType);
+    auto ExtendedBorrowIn = MRI.createVirtualRegister(*ResultType);
+    auto Zero = MRI.createVirtualRegister(*ResultType);
+    auto TemporaryResultIsZero = MRI.createVirtualRegister(*ConditionType);
+    auto SecondBorrow = MRI.createVirtualRegister(*ConditionType);
+    if (!TemporaryResult)
+      return std::unexpected(TemporaryResult.error());
+    if (!Borrow)
+      return std::unexpected(Borrow.error());
+    if (!ExtendedBorrowIn)
+      return std::unexpected(ExtendedBorrowIn.error());
+    if (!Zero)
+      return std::unexpected(Zero.error());
+    if (!TemporaryResultIsZero)
+      return std::unexpected(TemporaryResultIsZero.error());
+    if (!SecondBorrow)
+      return std::unexpected(SecondBorrow.error());
+    if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+      return std::unexpected(Point.error());
+    if (auto Built = MIRBuilder.buildSub(*TemporaryResult, Left, Right); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::UnsignedGreaterThan, *Borrow,
+                                          *TemporaryResult, Left);
+        !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildZExt(*ExtendedBorrowIn, BorrowIn); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildSub(Result, *TemporaryResult, *ExtendedBorrowIn); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildConstant(*Zero, 0); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::Equal, *TemporaryResultIsZero,
+                                          *TemporaryResult, *Zero);
+        !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildAnd(*SecondBorrow, *TemporaryResultIsZero, BorrowIn); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildOr(BorrowOut, *Borrow, *SecondBorrow); !Built)
+      return std::unexpected(Built.error());
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "G_USUBE became detached during lowering");
+    return Block->removeInstruction(Instruction);
+  }
   default: {
     const InstructionDescriptor *Descriptor =
         MIRBuilder.target().instructionDescriptor(Instruction.opcode());
@@ -564,9 +1490,14 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
 
 Expected<void> LegalizerHelper::legalize(MachineInstr &Instruction,
                                          const LegalizationDecision &Decision) {
+  if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+    return std::unexpected(Point.error());
+
   switch (Decision.Action) {
   case LegalizationAction::WidenScalar:
     return widenScalar(Instruction, Decision.TypeIndex, Decision.NewType);
+  case LegalizationAction::NarrowScalar:
+    return narrowScalar(Instruction, Decision.TypeIndex, Decision.NewType);
   case LegalizationAction::Custom:
     return Info.legalizeCustom(*this, Instruction, Decision);
   case LegalizationAction::Lower:
@@ -575,7 +1506,6 @@ Expected<void> LegalizerHelper::legalize(MachineInstr &Instruction,
     return {};
   case LegalizationAction::Unsupported:
   case LegalizationAction::Libcall:
-  case LegalizationAction::NarrowScalar:
   case LegalizationAction::MoreElements:
   case LegalizationAction::FewerElements:
   case LegalizationAction::Bitcast:
diff --git a/backend/lib/CodeGen/GlobalISel/Utils.cpp b/backend/lib/CodeGen/GlobalISel/Utils.cpp
new file mode 100644
index 0000000..6640694
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/Utils.cpp
@@ -0,0 +1,406 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/Utils.h"
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <cstdint>
+#include <numeric>
+#include <utility>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] bool hasProtectedAttachment(const MachineInstr &Instruction) noexcept {
+  return Instruction.flags().has(MachineInstrFlag::FrameSetup) ||
+         Instruction.flags().has(MachineInstrFlag::FrameDestroy) ||
+         Instruction.debugInstrNumber() != 0 || Instruction.preInstrSymbol().has_value() ||
+         Instruction.postInstrSymbol().has_value() || Instruction.heapAllocMarker().has_value() ||
+         Instruction.pcSections().has_value() || Instruction.mmra().has_value() ||
+         Instruction.cfiType().has_value() || Instruction.deactivationSymbol().has_value();
+}
+
+[[nodiscard]] bool wouldBeTriviallyDead(const MachineInstr &Instruction,
+                                        const InstructionDescriptor &Descriptor) noexcept {
+  switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
+  case GenericOpcode::LOCAL_ESCAPE:
+  case GenericOpcode::FAKE_USE:
+  case GenericOpcode::LIFETIME_START:
+  case GenericOpcode::LIFETIME_END:
+    return false;
+  default:
+    break;
+  }
+
+  const InstructionFlags Flags = Descriptor.Flags;
+  if (Flags.has(InstructionFlag::Phi))
+    return true;
+  if (Flags.has(InstructionFlag::Terminator) || Flags.has(InstructionFlag::Branch) ||
+      Flags.has(InstructionFlag::Call) || Flags.has(InstructionFlag::Return) ||
+      Flags.has(InstructionFlag::Barrier) || Flags.has(InstructionFlag::MayLoad) ||
+      Flags.has(InstructionFlag::MayStore) || Flags.has(InstructionFlag::HasSideEffects) ||
+      Flags.has(InstructionFlag::UnmodeledSideEffects) ||
+      Flags.has(InstructionFlag::MayRaiseFPException) || hasProtectedAttachment(Instruction))
+    return false;
+  return true;
+}
+
+[[nodiscard]] Expected<void> saveUsesAndErase(MachineInstr &Instruction, MachineRegisterInfo &MRI,
+                                              std::vector<MachineInstr *> &DeadChain) {
+  for (const MachineOperand &Operand : Instruction.operands()) {
+    if (!Operand.isRegister() || !Operand.isUse())
+      continue;
+    const std::optional<Register> Reg = Operand.registerValue();
+    if (!Reg || !Reg->isVirtual())
+      continue;
+    MachineInstr *Definition = MRI.getVRegDef(*Reg);
+    if (Definition != nullptr && Definition != &Instruction)
+      DeadChain.push_back(Definition);
+  }
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return {};
+  return Block->removeInstruction(Instruction);
+}
+
+[[nodiscard]] Expected<LowLevelType> makeVectorType(std::uint64_t ElementCount, bool IsScalable,
+                                                    LowLevelType ElementType) {
+  if (!IsScalable && ElementCount == 1)
+    return ElementType;
+  return IsScalable ? LowLevelType::makeScalableVector(ElementCount, ElementType)
+                    : LowLevelType::makeFixedVector(ElementCount, ElementType);
+}
+
+[[nodiscard]] Expected<void> extractVectorParts(Register Reg, std::size_t ElementCount,
+                                                std::vector<Register> &Parts,
+                                                MachineIRBuilder &MIRBuilder,
+                                                MachineRegisterInfo &MRI) {
+  auto RegisterType = MRI.getType(Reg);
+  if (!RegisterType)
+    return std::unexpected(RegisterType.error());
+  if (!RegisterType->isVector() || RegisterType->isScalableVector() || ElementCount == 0) {
+    return makeUnexpected(
+        ErrorCode::InvalidArgument,
+        "vector part extraction requires a fixed vector and a nonzero element count");
+  }
+
+  const LowLevelType ElementType = *RegisterType->scalarElementType();
+  auto NarrowType = makeVectorType(ElementCount, false, ElementType);
+  if (!NarrowType)
+    return std::unexpected(NarrowType.error());
+  const std::size_t RegisterElementCount = RegisterType->minimumElementCount();
+  const std::size_t LeftoverElementCount = RegisterElementCount % ElementCount;
+  const std::size_t NarrowPartCount = RegisterElementCount / ElementCount;
+
+  if (LeftoverElementCount == 0)
+    return extractParts(Reg, *NarrowType, static_cast<int>(NarrowPartCount), Parts, MIRBuilder,
+                        MRI);
+
+  std::vector<Register> Elements;
+  auto Extracted = extractParts(Reg, ElementType, static_cast<int>(RegisterElementCount), Elements,
+                                MIRBuilder, MRI);
+  if (!Extracted)
+    return std::unexpected(Extracted.error());
+
+  std::size_t Offset = 0;
+  for (std::size_t Index = 0; Index != NarrowPartCount; ++Index, Offset += ElementCount) {
+    std::vector<Register> Piece(Elements.begin() + static_cast<std::ptrdiff_t>(Offset),
+                                Elements.begin() +
+                                    static_cast<std::ptrdiff_t>(Offset + ElementCount));
+    auto Part = MRI.createVirtualRegister(*NarrowType);
+    if (!Part)
+      return std::unexpected(Part.error());
+    auto Built = MIRBuilder.buildMergeLikeInstr(*Part, Piece);
+    if (!Built)
+      return std::unexpected(Built.error());
+    Parts.push_back(*Part);
+  }
+
+  if (LeftoverElementCount == 1) {
+    Parts.push_back(Elements[Offset]);
+    return {};
+  }
+
+  auto LeftoverType = LowLevelType::makeFixedVector(LeftoverElementCount, ElementType);
+  if (!LeftoverType)
+    return std::unexpected(LeftoverType.error());
+  std::vector<Register> LeftoverElements(Elements.begin() + static_cast<std::ptrdiff_t>(Offset),
+                                         Elements.end());
+  auto Leftover = MRI.createVirtualRegister(*LeftoverType);
+  if (!Leftover)
+    return std::unexpected(Leftover.error());
+  auto Built = MIRBuilder.buildMergeLikeInstr(*Leftover, LeftoverElements);
+  if (!Built)
+    return std::unexpected(Built.error());
+  Parts.push_back(*Leftover);
+  return {};
+}
+
+} // namespace
+
+bool isTriviallyDead(const MachineInstr &Instruction, const MachineRegisterInfo &MRI,
+                     const TargetDescription &Target) noexcept {
+  for (const MachineOperand &Operand : Instruction.operands()) {
+    if (!Operand.isRegister() || !Operand.isDef())
+      continue;
+    const std::optional<Register> Reg = Operand.registerValue();
+    if (!Reg || Reg->isPhysical() || !MRI.useEmpty(*Reg, false))
+      return false;
+  }
+
+  const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
+  return Descriptor != nullptr && wouldBeTriviallyDead(Instruction, *Descriptor);
+}
+
+Expected<void> eraseInstrs(std::span<MachineInstr *const> Instructions, MachineRegisterInfo &MRI,
+                           const TargetDescription &Target) {
+  std::vector<MachineInstr *> DeadChain;
+  for (MachineInstr *Instruction : Instructions) {
+    if (Instruction == nullptr || Instruction->parent() == nullptr)
+      continue;
+    auto Removed = saveUsesAndErase(*Instruction, MRI, DeadChain);
+    if (!Removed)
+      return std::unexpected(Removed.error());
+  }
+
+  while (!DeadChain.empty()) {
+    MachineInstr *Instruction = DeadChain.back();
+    DeadChain.pop_back();
+    if (Instruction == nullptr || Instruction->parent() == nullptr ||
+        !isTriviallyDead(*Instruction, MRI, Target))
+      continue;
+    auto Removed = saveUsesAndErase(*Instruction, MRI, DeadChain);
+    if (!Removed)
+      return std::unexpected(Removed.error());
+  }
+  return {};
+}
+
+Expected<void> eraseInstr(MachineInstr &Instruction, MachineRegisterInfo &MRI,
+                          const TargetDescription &Target) {
+  MachineInstr *Instructions[] = {&Instruction};
+  return eraseInstrs(Instructions, MRI, Target);
+}
+
+Expected<void> extractParts(Register Reg, LowLevelType Type, int PartCount,
+                            std::vector<Register> &Parts, MachineIRBuilder &MIRBuilder,
+                            MachineRegisterInfo &MRI) {
+  std::vector<Register> NewParts;
+  if (PartCount < 0)
+    return makeUnexpected(ErrorCode::InvalidArgument, "part count cannot be negative");
+  NewParts.reserve(static_cast<std::size_t>(PartCount));
+  for (int Index = 0; Index != PartCount; ++Index) {
+    auto Part = MRI.createVirtualRegister(Type);
+    if (!Part)
+      return std::unexpected(Part.error());
+    NewParts.push_back(*Part);
+  }
+  auto Built = MIRBuilder.buildUnmergeValues(NewParts, Reg);
+  if (!Built)
+    return std::unexpected(Built.error());
+  Parts.insert(Parts.end(), NewParts.begin(), NewParts.end());
+  return {};
+}
+
+Expected<bool> extractParts(Register Reg, LowLevelType RegisterType, LowLevelType MainType,
+                            LowLevelType &LeftoverType, std::vector<Register> &Parts,
+                            std::vector<Register> &LeftoverParts, MachineIRBuilder &MIRBuilder,
+                            MachineRegisterInfo &MRI) {
+  if (LeftoverType.isValid()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "part extraction leftover type must be an output");
+  }
+
+  const std::uint64_t RegisterSize = RegisterType.minimumBitWidth();
+  const std::uint64_t MainSize = MainType.minimumBitWidth();
+  if (MainSize == 0 || MainSize > RegisterSize) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "part extraction requires a smaller nonzero main type");
+  }
+  const std::size_t PartCount = RegisterSize / MainSize;
+  const std::uint64_t LeftoverSize = RegisterSize - PartCount * MainSize;
+
+  if (LeftoverSize == 0) {
+    auto Extracted =
+        extractParts(Reg, MainType, static_cast<int>(PartCount), Parts, MIRBuilder, MRI);
+    if (!Extracted)
+      return std::unexpected(Extracted.error());
+    return true;
+  }
+
+  if (RegisterType.isVector() && MainType.isVector() && !RegisterType.isScalableVector() &&
+      !MainType.isScalableVector()) {
+    const std::size_t RegisterElementCount = RegisterType.minimumElementCount();
+    const std::size_t MainElementCount = MainType.minimumElementCount();
+    const std::size_t LeftoverElementCount = RegisterElementCount % MainElementCount;
+    if (LeftoverElementCount > 1 && MainElementCount % LeftoverElementCount == 0 &&
+        RegisterElementCount % LeftoverElementCount == 0 &&
+        RegisterType.scalarBitWidth() == MainType.scalarBitWidth()) {
+      auto Candidate =
+          LowLevelType::makeFixedVector(LeftoverElementCount, *RegisterType.scalarElementType());
+      if (!Candidate)
+        return std::unexpected(Candidate.error());
+      LeftoverType = *Candidate;
+
+      std::vector<Register> Unmerged;
+      auto Extracted = extractParts(Reg, LeftoverType,
+                                    static_cast<int>(RegisterElementCount / LeftoverElementCount),
+                                    Unmerged, MIRBuilder, MRI);
+      if (!Extracted)
+        return std::unexpected(Extracted.error());
+
+      const std::size_t LeftoversPerMain = MainElementCount / LeftoverElementCount;
+      const std::size_t LeftoverValueCount =
+          (RegisterElementCount % MainElementCount) / LeftoverElementCount;
+      std::vector<Register> MergeValues;
+      for (std::size_t Index = 0; Index != Unmerged.size() - LeftoverValueCount; ++Index) {
+        MergeValues.push_back(Unmerged[Index]);
+        if (MergeValues.size() != LeftoversPerMain)
+          continue;
+        auto Part = MRI.createVirtualRegister(MainType);
+        if (!Part)
+          return std::unexpected(Part.error());
+        auto Built = MIRBuilder.buildMergeLikeInstr(*Part, MergeValues);
+        if (!Built)
+          return std::unexpected(Built.error());
+        Parts.push_back(*Part);
+        MergeValues.clear();
+      }
+      LeftoverParts.insert(LeftoverParts.end(),
+                           Unmerged.end() - static_cast<std::ptrdiff_t>(LeftoverValueCount),
+                           Unmerged.end());
+      return true;
+    }
+  }
+
+  if (MainType.isVector()) {
+    std::vector<Register> RegisterPieces;
+    auto Extracted =
+        extractVectorParts(Reg, MainType.minimumElementCount(), RegisterPieces, MIRBuilder, MRI);
+    if (!Extracted)
+      return std::unexpected(Extracted.error());
+    Parts.insert(Parts.end(), RegisterPieces.begin(), std::prev(RegisterPieces.end()));
+    LeftoverParts.push_back(RegisterPieces.back());
+    auto Type = MRI.getType(LeftoverParts.front());
+    if (!Type)
+      return std::unexpected(Type.error());
+    LeftoverType = *Type;
+    return true;
+  }
+
+  auto ScalarLeftover = LowLevelType::makeCategoryNeutralScalar(LeftoverSize);
+  if (!ScalarLeftover)
+    return std::unexpected(ScalarLeftover.error());
+  LeftoverType = *ScalarLeftover;
+  for (std::size_t Index = 0; Index != PartCount; ++Index) {
+    auto Part = MRI.createVirtualRegister(MainType);
+    if (!Part)
+      return std::unexpected(Part.error());
+    auto Built = MIRBuilder.buildExtract(*Part, Reg, MainSize * Index);
+    if (!Built)
+      return std::unexpected(Built.error());
+    Parts.push_back(*Part);
+  }
+  for (std::uint64_t Offset = MainSize * PartCount; Offset < RegisterSize; Offset += LeftoverSize) {
+    auto Part = MRI.createVirtualRegister(LeftoverType);
+    if (!Part)
+      return std::unexpected(Part.error());
+    auto Built = MIRBuilder.buildExtract(*Part, Reg, Offset);
+    if (!Built)
+      return std::unexpected(Built.error());
+    LeftoverParts.push_back(*Part);
+  }
+  return true;
+}
+
+Expected<LowLevelType> getLCMType(LowLevelType OriginalType, LowLevelType TargetType) {
+  if (OriginalType.minimumBitWidth() == TargetType.minimumBitWidth())
+    return OriginalType;
+  if ((OriginalType.isScalableVector() && TargetType.isVector() &&
+       !TargetType.isScalableVector()) ||
+      (TargetType.isScalableVector() && OriginalType.isVector() &&
+       !OriginalType.isScalableVector())) {
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "LCM type is undefined between fixed and scalable vectors");
+  }
+
+  if (OriginalType.isVector() && TargetType.isVector()) {
+    const LowLevelType OriginalElement = *OriginalType.scalarElementType();
+    const LowLevelType TargetElement = *TargetType.scalarElementType();
+    if (OriginalElement.minimumBitWidth() == TargetElement.minimumBitWidth()) {
+      const std::uint64_t ElementCount =
+          std::lcm(static_cast<std::uint64_t>(OriginalType.minimumElementCount()),
+                   static_cast<std::uint64_t>(TargetType.minimumElementCount()));
+      return makeVectorType(ElementCount, OriginalType.isScalableVector(), OriginalElement);
+    }
+    const std::uint64_t Width =
+        std::lcm(OriginalType.minimumBitWidth(), TargetType.minimumBitWidth());
+    return makeVectorType(Width / OriginalElement.minimumBitWidth(),
+                          OriginalType.isScalableVector(), OriginalElement);
+  }
+
+  if (OriginalType.isVector() || TargetType.isVector()) {
+    const LowLevelType VectorType = OriginalType.isVector() ? OriginalType : TargetType;
+    const LowLevelType ScalarType = OriginalType.isVector() ? TargetType : OriginalType;
+    const LowLevelType VectorElement = *VectorType.scalarElementType();
+    const LowLevelType OriginalElement =
+        OriginalType.isVector() ? *OriginalType.scalarElementType() : OriginalType;
+    if (VectorElement.minimumBitWidth() == ScalarType.minimumBitWidth())
+      return makeVectorType(VectorType.minimumElementCount(), VectorType.isScalableVector(),
+                            OriginalElement);
+    const std::uint64_t Width =
+        std::lcm(VectorType.minimumBitWidth(), ScalarType.minimumBitWidth());
+    return makeVectorType(Width / OriginalElement.minimumBitWidth(), VectorType.isScalableVector(),
+                          OriginalElement);
+  }
+
+  const std::uint64_t Width =
+      std::lcm(OriginalType.minimumBitWidth(), TargetType.minimumBitWidth());
+  if (Width == OriginalType.minimumBitWidth())
+    return OriginalType;
+  if (Width == TargetType.minimumBitWidth())
+    return TargetType;
+  return LowLevelType::makeCategoryNeutralScalar(Width);
+}
+
+Expected<LowLevelType> getGCDType(LowLevelType OriginalType, LowLevelType TargetType) {
+  if (OriginalType.minimumBitWidth() == TargetType.minimumBitWidth())
+    return OriginalType;
+  if ((OriginalType.isScalableVector() && TargetType.isVector() &&
+       !TargetType.isScalableVector()) ||
+      (TargetType.isScalableVector() && OriginalType.isVector() &&
+       !OriginalType.isScalableVector())) {
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "GCD type is undefined between fixed and scalable vectors");
+  }
+
+  if (OriginalType.isVector() && TargetType.isVector()) {
+    const LowLevelType OriginalElement = *OriginalType.scalarElementType();
+    const std::uint64_t Width =
+        std::gcd(OriginalType.minimumBitWidth(), TargetType.minimumBitWidth());
+    if (Width == OriginalElement.minimumBitWidth())
+      return makeVectorType(1, OriginalType.isScalableVector(), OriginalElement);
+    if (Width < OriginalElement.minimumBitWidth())
+      return LowLevelType::makeCategoryNeutralScalar(Width);
+    return makeVectorType(Width / OriginalElement.minimumBitWidth(),
+                          OriginalType.isScalableVector(), OriginalElement);
+  }
+
+  if (OriginalType.isVector() && OriginalType.scalarBitWidth() == TargetType.minimumBitWidth())
+    return *OriginalType.scalarElementType();
+  if (TargetType.isVector() && TargetType.scalarBitWidth() == OriginalType.minimumBitWidth())
+    return OriginalType;
+
+  const std::uint64_t OriginalScalarWidth = OriginalType.scalarBitWidth();
+  const std::uint64_t TargetScalarWidth = TargetType.scalarBitWidth();
+  return LowLevelType::makeCategoryNeutralScalar(std::gcd(OriginalScalarWidth, TargetScalarWidth));
+}
+
+} // namespace rcc