[GlobalISel] Match LLVM CSE builder result semantics

8 files changed, 1187 insertions, 244 deletions

diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index ff02a20..862caca 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -90,6 +90,7 @@ set(
   RCCBackendCodeGenHeaders
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/CompilationUnit.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/CommandFlags.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/CSEConfigBase.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalObject.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GenericOpcodes.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/FrameIndexElimination.h"
diff --git a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
index 3b01e9b..8fc50d2 100644
--- a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
+++ b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
@@ -2,6 +2,8 @@
 
 set(
   RCCBackendGlobalISelSources
+  CSEInfo.cpp
+  CSEMIRBuilder.cpp
   GISelChangeObserver.cpp
   GISelValueTracking.cpp
   InstructionSelect.cpp
@@ -14,6 +16,8 @@ set(
 
 set(
   RCCBackendGlobalISelHeaders
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/CSEInfo.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/CSEMIRBuilder.h"
   "${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"
@@ -31,6 +35,8 @@ set(
 target_sources(RCCBackendCodeGen PRIVATE ${RCCBackendGlobalISelSources})
 
 rcc_backend_register_format_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/CSEInfo.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/CSEMIRBuilder.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp"
@@ -43,6 +49,8 @@ rcc_backend_register_format_files(
 )
 
 rcc_backend_register_tidy_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/CSEInfo.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/CSEMIRBuilder.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp"
diff --git a/backend/lib/CodeGen/GlobalISel/CSEInfo.cpp b/backend/lib/CodeGen/GlobalISel/CSEInfo.cpp
new file mode 100644
index 0000000..201dedd
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/CSEInfo.cpp
@@ -0,0 +1,467 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/CSEInfo.h"
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include <bit>
+#include <cstddef>
+#include <cstdint>
+#include <functional>
+#include <memory>
+#include <utility>
+
+namespace rcc {
+namespace {
+
+enum class ProfileTag : std::uint64_t {
+  Definition,
+  Use,
+  RegisterNumber,
+  PhysicalRegister,
+  Type,
+  RegisterBank,
+  NoRegisterBank,
+  RegisterClass,
+  NoRegisterClass,
+  Immediate,
+  IntegerImmediate,
+  FloatingImmediate,
+  IntegerPredicate,
+  FloatingPredicate,
+  Flags,
+};
+
+void appendTypeProfile(std::vector<std::uint64_t> &Profile, LowLevelType Type,
+                       std::optional<RegisterBankID> Bank,
+                       std::optional<RegisterClassID> RegClass) {
+  Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Type));
+  Profile.push_back(Type.rawValue());
+  if (Bank) {
+    Profile.push_back(static_cast<std::uint64_t>(ProfileTag::RegisterBank));
+    Profile.push_back(Bank->value());
+  } else {
+    Profile.push_back(static_cast<std::uint64_t>(ProfileTag::NoRegisterBank));
+  }
+  if (RegClass) {
+    Profile.push_back(static_cast<std::uint64_t>(ProfileTag::RegisterClass));
+    Profile.push_back(RegClass->value());
+  } else {
+    Profile.push_back(static_cast<std::uint64_t>(ProfileTag::NoRegisterClass));
+  }
+}
+
+void appendAPIntProfile(std::vector<std::uint64_t> &Profile, const APInt &Value) {
+  Profile.push_back(static_cast<std::uint64_t>(ProfileTag::IntegerImmediate));
+  Profile.push_back(Value.bitWidth());
+  Profile.push_back(Value.words().size());
+  Profile.insert(Profile.end(), Value.words().begin(), Value.words().end());
+}
+
+void appendAPFloatProfile(std::vector<std::uint64_t> &Profile, const APFloat &Value) {
+  Profile.push_back(static_cast<std::uint64_t>(ProfileTag::FloatingImmediate));
+  Profile.push_back(static_cast<std::uint64_t>(Value.semantics()));
+  Profile.push_back(Value.words().size());
+  Profile.insert(Profile.end(), Value.words().begin(), Value.words().end());
+}
+
+void hashCombine(std::size_t &Seed, std::size_t Value) noexcept {
+  Seed ^= Value + 0x9e3779b97f4a7c15ULL + (Seed << 6U) + (Seed >> 2U);
+}
+
+} // namespace
+
+bool CSEConfigFull::shouldCSEOpcode(Opcode InstructionOpcode) const noexcept {
+  switch (static_cast<GenericOpcode>(InstructionOpcode.value())) {
+  default:
+    return false;
+  case GenericOpcode::G_ADD:
+  case GenericOpcode::G_AND:
+  case GenericOpcode::G_ASHR:
+  case GenericOpcode::G_LSHR:
+  case GenericOpcode::G_MUL:
+  case GenericOpcode::G_OR:
+  case GenericOpcode::G_SHL:
+  case GenericOpcode::G_SUB:
+  case GenericOpcode::G_XOR:
+  case GenericOpcode::G_UDIV:
+  case GenericOpcode::G_SDIV:
+  case GenericOpcode::G_UREM:
+  case GenericOpcode::G_SREM:
+  case GenericOpcode::G_CONSTANT:
+  case GenericOpcode::G_FCONSTANT:
+  case GenericOpcode::G_IMPLICIT_DEF:
+  case GenericOpcode::G_ZEXT:
+  case GenericOpcode::G_SEXT:
+  case GenericOpcode::G_ANYEXT:
+  case GenericOpcode::G_UNMERGE_VALUES:
+  case GenericOpcode::G_TRUNC:
+  case GenericOpcode::G_PTR_ADD:
+  case GenericOpcode::G_EXTRACT:
+  case GenericOpcode::G_SELECT:
+  case GenericOpcode::G_BUILD_VECTOR:
+  case GenericOpcode::G_BUILD_VECTOR_TRUNC:
+  case GenericOpcode::G_SEXT_INREG:
+  case GenericOpcode::G_FADD:
+  case GenericOpcode::G_FSUB:
+  case GenericOpcode::G_FMUL:
+  case GenericOpcode::G_FDIV:
+  case GenericOpcode::G_FABS:
+  case GenericOpcode::G_FMAXNUM:
+  case GenericOpcode::G_FMINNUM:
+  case GenericOpcode::G_FMAXNUM_IEEE:
+  case GenericOpcode::G_FMINNUM_IEEE:
+    return true;
+  }
+}
+
+bool CSEConfigConstantOnly::shouldCSEOpcode(Opcode InstructionOpcode) const noexcept {
+  return InstructionOpcode == opcode(GenericOpcode::G_CONSTANT) ||
+         InstructionOpcode == opcode(GenericOpcode::G_FCONSTANT) ||
+         InstructionOpcode == opcode(GenericOpcode::G_IMPLICIT_DEF);
+}
+
+std::unique_ptr<CSEConfigBase> getStandardCSEConfigForOpt(OptimizationLevel Level) {
+  if (Level == OptimizationLevel::O0)
+    return std::make_unique<CSEConfigConstantOnly>();
+  return std::make_unique<CSEConfigFull>();
+}
+
+std::size_t GISelCSEInfo::CSEKeyHash::operator()(const CSEKey &Key) const noexcept {
+  std::size_t Result = std::hash<const MachineBasicBlock *>{}(Key.Block);
+  hashCombine(Result, std::hash<std::uint32_t>{}(Key.InstructionOpcode.value()));
+  for (std::uint64_t Value : Key.Profile)
+    hashCombine(Result, std::hash<std::uint64_t>{}(Value));
+  return Result;
+}
+
+void GISelCSEInfo::setCSEConfig(std::unique_ptr<CSEConfigBase> NewConfig) noexcept {
+  Config = std::move(NewConfig);
+}
+
+bool GISelCSEInfo::shouldCSE(Opcode InstructionOpcode) const noexcept {
+  return Config != nullptr && isGenericOpcode(InstructionOpcode) &&
+         Config->shouldCSEOpcode(InstructionOpcode);
+}
+
+Expected<void> GISelCSEInfo::appendRegisterProfile(std::vector<std::uint64_t> &Profile,
+                                                   Register Reg, bool IsDefinition) const {
+  Profile.push_back(
+      static_cast<std::uint64_t>(IsDefinition ? ProfileTag::Definition : ProfileTag::Use));
+  if (!IsDefinition) {
+    Profile.push_back(static_cast<std::uint64_t>(ProfileTag::RegisterNumber));
+    Profile.push_back(Reg.opaqueValue());
+  }
+  if (!Reg.isVirtual()) {
+    Profile.push_back(static_cast<std::uint64_t>(ProfileTag::PhysicalRegister));
+    Profile.push_back(Reg.opaqueValue());
+    return {};
+  }
+  if (Function == nullptr)
+    return makeUnexpected(ErrorCode::InternalError, "GlobalISel CSE has no machine function");
+  auto Info = Function->registerInfo().virtualRegisterInfo(Reg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  const std::optional<LowLevelType> &Type = Info->get().Type;
+  if (!Type.has_value()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "GlobalISel CSE requires typed virtual registers");
+  }
+  appendTypeProfile(Profile, Type.value(), Info->get().Bank, Info->get().RegClass);
+  return {};
+}
+
+Expected<void> GISelCSEInfo::appendResultProfile(std::vector<std::uint64_t> &Profile,
+                                                 const MachineIRBuilderResult &Result) const {
+  if (Result.kind() == MachineIRBuilderResult::Kind::Register)
+    return appendRegisterProfile(Profile, Result.reg(), true);
+  Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Definition));
+  appendTypeProfile(Profile, Result.type(), std::nullopt, std::nullopt);
+  return {};
+}
+
+Expected<GISelCSEInfo::CSEKey>
+GISelCSEInfo::profileInstruction(const MachineInstr &Instruction) const {
+  if (Instruction.parent() == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "cannot profile a detached instruction");
+  if (!Instruction.memOperands().empty()) {
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "GlobalISel CSE does not profile memory operands");
+  }
+
+  CSEKey Key{
+      .Block = Instruction.parent(), .InstructionOpcode = Instruction.opcode(), .Profile = {}};
+  for (const MachineOperand &Operand : Instruction.operands()) {
+    switch (Operand.kind()) {
+    case MachineOperand::Kind::Register: {
+      const Register *Reg = Operand.getIf<Register>();
+      if (Reg == nullptr || Operand.isImplicit()) {
+        return makeUnexpected(ErrorCode::Unsupported,
+                              "GlobalISel CSE does not profile implicit register operands");
+      }
+      auto Appended = appendRegisterProfile(Key.Profile, *Reg, Operand.isDef());
+      if (!Appended)
+        return std::unexpected(Appended.error());
+      break;
+    }
+    case MachineOperand::Kind::Immediate: {
+      const std::int64_t *Value = Operand.getIf<std::int64_t>();
+      if (Value == nullptr)
+        return makeUnexpected(ErrorCode::InternalError, "invalid immediate operand storage");
+      Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Immediate));
+      Key.Profile.push_back(std::bit_cast<std::uint64_t>(*Value));
+      break;
+    }
+    case MachineOperand::Kind::IntegerImmediate: {
+      const auto *Value = Operand.getIf<IntegerImmediateOperand>();
+      if (Value == nullptr)
+        return makeUnexpected(ErrorCode::InternalError,
+                              "invalid integer immediate operand storage");
+      appendAPIntProfile(Key.Profile, Value->Value);
+      break;
+    }
+    case MachineOperand::Kind::FloatingImmediate: {
+      const auto *Value = Operand.getIf<FloatingImmediateOperand>();
+      if (Value == nullptr)
+        return makeUnexpected(ErrorCode::InternalError,
+                              "invalid floating immediate operand storage");
+      appendAPFloatProfile(Key.Profile, Value->Bits);
+      break;
+    }
+    case MachineOperand::Kind::Predicate: {
+      const auto *Predicate = Operand.getIf<PredicateOperand>();
+      if (Predicate == nullptr)
+        return makeUnexpected(ErrorCode::InternalError, "invalid predicate operand storage");
+      if (const IntegerPredicate *Integer = Predicate->integerPredicate()) {
+        Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::IntegerPredicate));
+        Key.Profile.push_back(static_cast<std::uint64_t>(*Integer));
+      } else if (const FloatingPredicate *Floating = Predicate->floatingPredicate()) {
+        Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::FloatingPredicate));
+        Key.Profile.push_back(static_cast<std::uint64_t>(*Floating));
+      } else {
+        return makeUnexpected(ErrorCode::InternalError, "empty predicate operand");
+      }
+      break;
+    }
+    default:
+      return makeUnexpected(ErrorCode::Unsupported,
+                            "GlobalISel CSE encountered an unsupported operand kind");
+    }
+  }
+  Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Flags));
+  Key.Profile.push_back(Instruction.flags().rawValue());
+  return Key;
+}
+
+Expected<GISelCSEInfo::CSEKey> GISelCSEInfo::profileBuilderInstruction(
+    Opcode InstructionOpcode, std::span<const MachineIRBuilderResult> Destinations,
+    std::span<const Register> Sources, std::span<const std::int64_t> Immediates,
+    MachineInstrFlags Flags, const MachineBasicBlock &Block) const {
+  CSEKey Key{.Block = &Block, .InstructionOpcode = InstructionOpcode, .Profile = {}};
+  for (const MachineIRBuilderResult &Destination : Destinations) {
+    auto Appended = appendResultProfile(Key.Profile, Destination);
+    if (!Appended)
+      return std::unexpected(Appended.error());
+  }
+  for (Register Source : Sources) {
+    auto Appended = appendRegisterProfile(Key.Profile, Source, false);
+    if (!Appended)
+      return std::unexpected(Appended.error());
+  }
+  for (std::int64_t Immediate : Immediates) {
+    Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Immediate));
+    Key.Profile.push_back(std::bit_cast<std::uint64_t>(Immediate));
+  }
+  Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Flags));
+  Key.Profile.push_back(Flags.rawValue());
+  return Key;
+}
+
+Expected<GISelCSEInfo::CSEKey>
+GISelCSEInfo::profileConstant(const MachineIRBuilderResult &Destination, const APInt &Value,
+                              const MachineBasicBlock &Block) const {
+  CSEKey Key{
+      .Block = &Block, .InstructionOpcode = opcode(GenericOpcode::G_CONSTANT), .Profile = {}};
+  auto Appended = appendResultProfile(Key.Profile, Destination);
+  if (!Appended)
+    return std::unexpected(Appended.error());
+  appendAPIntProfile(Key.Profile, Value);
+  Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Flags));
+  Key.Profile.push_back(0);
+  return Key;
+}
+
+Expected<void> GISelCSEInfo::insertInstruction(MachineInstr &Instruction) {
+  TemporaryInstructions.remove(&Instruction);
+  auto Key = profileInstruction(Instruction);
+  if (!Key)
+    return std::unexpected(Key.error());
+  auto [Position, Inserted] = CSEMap.emplace(*Key, &Instruction);
+  if (Inserted)
+    InstructionMapping.emplace(&Instruction, std::move(*Key));
+  return {};
+}
+
+void GISelCSEInfo::recordNewInstruction(MachineInstr &Instruction) {
+  if (shouldCSE(Instruction.opcode()))
+    TemporaryInstructions.insert(&Instruction);
+}
+
+Expected<void> GISelCSEInfo::handleRecordedInstruction(MachineInstr &Instruction) {
+  TemporaryInstructions.remove(&Instruction);
+  handleRemoveInstruction(Instruction);
+  if (Instruction.parent() == nullptr || !shouldCSE(Instruction.opcode()))
+    return {};
+  return insertInstruction(Instruction);
+}
+
+Expected<void> GISelCSEInfo::handleRecordedInstructions() {
+  if (HandlingRecordedInstructions)
+    return {};
+  HandlingRecordedInstructions = true;
+  while (!TemporaryInstructions.empty()) {
+    MachineInstr *Instruction = TemporaryInstructions.popBack();
+    if (Instruction == nullptr)
+      continue;
+    auto Handled = handleRecordedInstruction(*Instruction);
+    if (!Handled) {
+      HandlingRecordedInstructions = false;
+      return std::unexpected(Handled.error());
+    }
+  }
+  HandlingRecordedInstructions = false;
+  return {};
+}
+
+void GISelCSEInfo::handleRemoveInstruction(MachineInstr &Instruction) noexcept {
+  const auto Mapping = InstructionMapping.find(&Instruction);
+  if (Mapping != InstructionMapping.end()) {
+    const auto Position = CSEMap.find(Mapping->second);
+    if (Position != CSEMap.end() && Position->second == &Instruction)
+      CSEMap.erase(Position);
+    InstructionMapping.erase(Mapping);
+  }
+  TemporaryInstructions.remove(&Instruction);
+}
+
+Expected<MachineInstr *> GISelCSEInfo::getMachineInstrIfExists(
+    Opcode InstructionOpcode, std::span<const MachineIRBuilderResult> Destinations,
+    std::span<const Register> Sources, std::span<const std::int64_t> Immediates,
+    MachineInstrFlags Flags, MachineBasicBlock &Block) {
+  auto Handled = handleRecordedInstructions();
+  if (!Handled)
+    return std::unexpected(Handled.error());
+  auto Key =
+      profileBuilderInstruction(InstructionOpcode, Destinations, Sources, Immediates, Flags, Block);
+  if (!Key)
+    return std::unexpected(Key.error());
+  const auto Position = CSEMap.find(*Key);
+  if (Position == CSEMap.end())
+    return nullptr;
+  countOpcodeHit(InstructionOpcode);
+  return Position->second;
+}
+
+Expected<MachineInstr *>
+GISelCSEInfo::getConstantIfExists(const MachineIRBuilderResult &Destination, const APInt &Value,
+                                  MachineBasicBlock &Block) {
+  auto Handled = handleRecordedInstructions();
+  if (!Handled)
+    return std::unexpected(Handled.error());
+  auto Key = profileConstant(Destination, Value, Block);
+  if (!Key)
+    return std::unexpected(Key.error());
+  const auto Position = CSEMap.find(*Key);
+  if (Position == CSEMap.end())
+    return nullptr;
+  countOpcodeHit(opcode(GenericOpcode::G_CONSTANT));
+  return Position->second;
+}
+
+void GISelCSEInfo::countOpcodeHit(Opcode InstructionOpcode) noexcept {
+  ++OpcodeHitTable[InstructionOpcode.value()];
+}
+
+Expected<void> GISelCSEInfo::analyze(MachineFunction &NewFunction) {
+  if (Config == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "GlobalISel CSE configuration is not set");
+  CSEMap.clear();
+  InstructionMapping.clear();
+  TemporaryInstructions.clear();
+  OpcodeHitTable.clear();
+  HandlingRecordedInstructions = false;
+  Function = &NewFunction;
+  for (MachineBasicBlock *Block = NewFunction.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      if (!shouldCSE(Instruction->opcode()))
+        continue;
+      auto Inserted = insertInstruction(*Instruction);
+      if (!Inserted)
+        return std::unexpected(Inserted.error());
+    }
+  }
+  return {};
+}
+
+Expected<void> GISelCSEInfo::verify() {
+  auto Handled = handleRecordedInstructions();
+  if (!Handled)
+    return std::unexpected(Handled.error());
+  for (const auto &[Instruction, Key] : InstructionMapping) {
+    if (Instruction == nullptr || Instruction->parent() == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "GlobalISel CSE maps a detached instruction");
+    auto CurrentKey = profileInstruction(*Instruction);
+    if (!CurrentKey)
+      return std::unexpected(CurrentKey.error());
+    const auto Position = CSEMap.find(*CurrentKey);
+    if (*CurrentKey != Key || Position == CSEMap.end() || Position->second != Instruction) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "GlobalISel CSE instruction mapping is inconsistent");
+    }
+  }
+  for (const auto &[Key, Instruction] : CSEMap) {
+    const auto Mapping = InstructionMapping.find(Instruction);
+    if (Mapping == InstructionMapping.end() || Mapping->second != Key) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "GlobalISel CSE table has no instruction mapping");
+    }
+  }
+  return {};
+}
+
+void GISelCSEInfo::releaseMemory() noexcept {
+  CSEMap.clear();
+  InstructionMapping.clear();
+  TemporaryInstructions.clear();
+  OpcodeHitTable.clear();
+  Config.reset();
+  Function = nullptr;
+  HandlingRecordedInstructions = false;
+}
+
+void GISelCSEInfo::erasingInstr(MachineInstr &Instruction) {
+  handleRemoveInstruction(Instruction);
+}
+
+void GISelCSEInfo::createdInstr(MachineInstr &Instruction) {
+  recordNewInstruction(Instruction);
+}
+
+void GISelCSEInfo::changingInstr(MachineInstr &Instruction) {
+  erasingInstr(Instruction);
+  createdInstr(Instruction);
+}
+
+void GISelCSEInfo::changedInstr(MachineInstr &Instruction) {
+  changingInstr(Instruction);
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp b/backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp
new file mode 100644
index 0000000..e1fdaa6
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp
@@ -0,0 +1,226 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/CSEMIRBuilder.h"
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/GlobalISel/CSEInfo.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include <algorithm>
+#include <array>
+#include <cstdint>
+#include <limits>
+#include <span>
+#include <utility>
+
+namespace rcc {
+
+bool CSEMIRBuilder::canPerformCSE(Opcode InstructionOpcode) const noexcept {
+  const GISelCSEInfo *Info = getCSEInfo();
+  return Info != nullptr && Info->shouldCSE(InstructionOpcode);
+}
+
+bool CSEMIRBuilder::dominatesInsertionPoint(const MachineInstr &Instruction) const noexcept {
+  const MachineBasicBlock *Block = insertionBlock();
+  const MachineInstr *InsertBefore = insertionInstruction();
+  if (Block == nullptr || Instruction.parent() != Block)
+    return false;
+  if (InsertBefore == nullptr)
+    return true;
+  for (const MachineInstr *Current = Block->firstInstruction(); Current != nullptr;
+       Current = Current->next()) {
+    if (Current == &Instruction)
+      return true;
+    if (Current == InsertBefore)
+      return false;
+  }
+  return false;
+}
+
+Expected<void> CSEMIRBuilder::makeInstructionDominate(MachineInstr &Instruction) const {
+  MachineBasicBlock *Block = insertionBlock();
+  MachineInstr *InsertBefore = insertionInstruction();
+  if (Block == nullptr || Instruction.parent() != Block) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "GlobalISel CSE candidate is not in the insertion block");
+  }
+  if (&Instruction == InsertBefore) {
+    return const_cast<CSEMIRBuilder *>(this)->setInsertPointAfter(Instruction);
+  }
+  if (InsertBefore == nullptr || dominatesInsertionPoint(Instruction))
+    return {};
+  auto Removed = Block->removeInstruction(Instruction);
+  if (!Removed)
+    return std::unexpected(Removed.error());
+  auto Inserted = Block->insertInstructionBefore(*InsertBefore, Instruction);
+  if (!Inserted)
+    return std::unexpected(Inserted.error());
+  return {};
+}
+
+Expected<MachineInstr *>
+CSEMIRBuilder::generateCopyIfRequired(const MachineIRBuilderResult &Destination,
+                                      MachineInstr &Instruction) const {
+  if (Destination.kind() == MachineIRBuilderResult::Kind::Type)
+    return &Instruction;
+  const MachineOperand *Definition = Instruction.operandAt(0);
+  const Register *Source = Definition == nullptr ? nullptr : Definition->getIf<Register>();
+  if (Source == nullptr || !Definition->isDef()) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "GlobalISel CSE candidate has no register definition");
+  }
+  if (Destination.reg() == *Source)
+    return &Instruction;
+  return MachineIRBuilder::buildCopy(Destination, *Source);
+}
+
+Expected<MachineInstr *> CSEMIRBuilder::memoize(MachineInstr &Instruction) const {
+  GISelCSEInfo *Info = getCSEInfo();
+  if (Info == nullptr)
+    return &Instruction;
+  auto Inserted = Info->handleRecordedInstruction(Instruction);
+  if (!Inserted)
+    return std::unexpected(Inserted.error());
+  return &Instruction;
+}
+
+Expected<MachineInstr *>
+CSEMIRBuilder::buildInstr(Opcode InstructionOpcode,
+                          std::span<const MachineIRBuilderResult> Destinations,
+                          std::span<const Register> Sources) const {
+  if (!canPerformCSE(InstructionOpcode))
+    return MachineIRBuilder::buildInstr(InstructionOpcode, Destinations, Sources);
+  MachineBasicBlock *Block = insertionBlock();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point");
+
+  GISelCSEInfo *Info = getCSEInfo();
+  const bool CanGenerateCopies =
+      Destinations.size() == 1 || std::ranges::all_of(Destinations, [](const auto &Destination) {
+        return Destination.kind() == MachineIRBuilderResult::Kind::Type;
+      });
+  if (!CanGenerateCopies) {
+    auto Built = MachineIRBuilder::buildInstr(InstructionOpcode, Destinations, Sources);
+    if (!Built)
+      return std::unexpected(Built.error());
+    Info->handleRemoveInstruction(**Built);
+    return *Built;
+  }
+
+  auto Existing =
+      Info->getMachineInstrIfExists(InstructionOpcode, Destinations, Sources,
+                                    std::span<const std::int64_t>(), MachineInstrFlags(), *Block);
+  if (!Existing)
+    return std::unexpected(Existing.error());
+  if (*Existing != nullptr) {
+    auto Dominating = makeInstructionDominate(**Existing);
+    if (!Dominating)
+      return std::unexpected(Dominating.error());
+    if (Destinations.size() == 1)
+      return generateCopyIfRequired(Destinations.front(), **Existing);
+    return *Existing;
+  }
+
+  auto Built = MachineIRBuilder::buildInstr(InstructionOpcode, Destinations, Sources);
+  if (!Built)
+    return std::unexpected(Built.error());
+  return memoize(**Built);
+}
+
+Expected<MachineInstr *> CSEMIRBuilder::buildConstant(MachineIRBuilderResult Destination,
+                                                      APInt Value) const {
+  const Opcode ConstantOpcode = opcode(GenericOpcode::G_CONSTANT);
+  if (!canPerformCSE(ConstantOpcode))
+    return MachineIRBuilder::buildConstant(Destination, std::move(Value));
+  MachineBasicBlock *Block = insertionBlock();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point");
+
+  GISelCSEInfo *Info = getCSEInfo();
+  auto Existing = Info->getConstantIfExists(Destination, Value, *Block);
+  if (!Existing)
+    return std::unexpected(Existing.error());
+  if (*Existing != nullptr) {
+    auto Dominating = makeInstructionDominate(**Existing);
+    if (!Dominating)
+      return std::unexpected(Dominating.error());
+    return generateCopyIfRequired(Destination, **Existing);
+  }
+
+  auto Built = MachineIRBuilder::buildConstant(Destination, std::move(Value));
+  if (!Built)
+    return std::unexpected(Built.error());
+  return memoize(**Built);
+}
+
+Expected<MachineInstr *> CSEMIRBuilder::buildSExtInReg(MachineIRBuilderResult Destination,
+                                                       Register Source, std::uint32_t Width) const {
+  const Opcode InstructionOpcode = opcode(GenericOpcode::G_SEXT_INREG);
+  if (!canPerformCSE(InstructionOpcode))
+    return MachineIRBuilder::buildSExtInReg(Destination, Source, Width);
+  MachineBasicBlock *Block = insertionBlock();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point");
+
+  GISelCSEInfo *Info = getCSEInfo();
+  const std::array Destinations{Destination};
+  const std::array Sources{Source};
+  const std::array Immediates{static_cast<std::int64_t>(Width)};
+  auto Existing = Info->getMachineInstrIfExists(
+      InstructionOpcode, std::span<const MachineIRBuilderResult>(Destinations),
+      std::span<const Register>(Sources), std::span<const std::int64_t>(Immediates),
+      MachineInstrFlags(), *Block);
+  if (!Existing)
+    return std::unexpected(Existing.error());
+  if (*Existing != nullptr) {
+    auto Dominating = makeInstructionDominate(**Existing);
+    if (!Dominating)
+      return std::unexpected(Dominating.error());
+    return generateCopyIfRequired(Destination, **Existing);
+  }
+
+  auto Built = MachineIRBuilder::buildSExtInReg(Destination, Source, Width);
+  if (!Built)
+    return std::unexpected(Built.error());
+  return memoize(**Built);
+}
+
+Expected<MachineInstr *> CSEMIRBuilder::buildExtract(MachineIRBuilderResult Destination,
+                                                     Register Source, std::uint64_t Offset) const {
+  if (Offset > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()))
+    return MachineIRBuilder::buildExtract(Destination, Source, Offset);
+  const Opcode InstructionOpcode = opcode(GenericOpcode::G_EXTRACT);
+  if (!canPerformCSE(InstructionOpcode))
+    return MachineIRBuilder::buildExtract(Destination, Source, Offset);
+  MachineBasicBlock *Block = insertionBlock();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point");
+
+  GISelCSEInfo *Info = getCSEInfo();
+  const std::array Destinations{Destination};
+  const std::array Sources{Source};
+  const std::array Immediates{static_cast<std::int64_t>(Offset)};
+  auto Existing = Info->getMachineInstrIfExists(
+      InstructionOpcode, std::span<const MachineIRBuilderResult>(Destinations),
+      std::span<const Register>(Sources), std::span<const std::int64_t>(Immediates),
+      MachineInstrFlags(), *Block);
+  if (!Existing)
+    return std::unexpected(Existing.error());
+  if (*Existing != nullptr) {
+    auto Dominating = makeInstructionDominate(**Existing);
+    if (!Dominating)
+      return std::unexpected(Dominating.error());
+    return generateCopyIfRequired(Destination, **Existing);
+  }
+
+  auto Built = MachineIRBuilder::buildExtract(Destination, Source, Offset);
+  if (!Built)
+    return std::unexpected(Built.error());
+  return memoize(**Built);
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
index dfa4523..77c1b0c 100644
--- a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
+++ b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
@@ -3,6 +3,8 @@
 #include "rcc/CodeGen/GlobalISel/Legalizer.h"
 
 #include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/GlobalISel/CSEInfo.h"
+#include "rcc/CodeGen/GlobalISel/CSEMIRBuilder.h"
 #include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
 #include "rcc/CodeGen/GlobalISel/GISelValueTracking.h"
 #include "rcc/CodeGen/GlobalISel/GISelWorkList.h"
@@ -18,7 +20,9 @@
 #include "rcc/CodeGen/TargetDescription.h"
 
 #include <algorithm>
+#include <array>
 #include <cstddef>
+#include <memory>
 #include <optional>
 #include <ranges>
 #include <string>
@@ -126,7 +130,7 @@ private:
     std::size_t NextSuccessor = 0;
   };
 
-  const auto makeFrame = [](MachineBasicBlock &Block) {
+  const auto MakeFrame = [](MachineBasicBlock &Block) {
     TraversalFrame Frame;
     Frame.Block = &Block;
     for (const MachineSuccessor &Successor : Block.successors()) {
@@ -156,13 +160,13 @@ private:
   for (MachineBasicBlock *Root : Roots) {
     if (!Visited.insert(Root).second)
       continue;
-    Stack.push_back(makeFrame(*Root));
+    Stack.push_back(MakeFrame(*Root));
     while (!Stack.empty()) {
       TraversalFrame &Frame = Stack.back();
       if (Frame.NextSuccessor < Frame.Successors.size()) {
         MachineBasicBlock *Successor = Frame.Successors[Frame.NextSuccessor++];
         if (Visited.insert(Successor).second)
-          Stack.push_back(makeFrame(*Successor));
+          Stack.push_back(MakeFrame(*Successor));
         continue;
       }
       PostOrder.push_back(Frame.Block);
@@ -305,9 +309,17 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi
   InstructionWorklist.finalize();
 
   LegalizerWorkListManager WorkListObserver(InstructionWorklist, ArtifactWorklist);
-  GISelObserverWrapper Observer(WorkListObserver);
+  GISelCSEInfo CSEInfo;
+  CSEInfo.setCSEConfig(getStandardCSEConfigForOpt(Optimization));
+  auto CSEAnalysis = CSEInfo.analyze(Function);
+  if (!CSEAnalysis)
+    return std::unexpected(
+        withErrorContext(CSEAnalysis.error(), "GlobalISel CSE analysis failed: "));
+  std::array<GISelChangeObserver *, 2> AuxiliaryObservers{&WorkListObserver, &CSEInfo};
+  GISelObserverWrapper Observer{std::span<GISelChangeObserver *const>(AuxiliaryObservers)};
   MachineFunctionDelegateInstaller ObserverInstaller(Function, Observer);
-  MachineIRBuilder Builder(Function, Target);
+  CSEMIRBuilder Builder(Function, Target);
+  Builder.setCSEInfo(&CSEInfo);
   LegalizerHelper Helper(Function, *Info, Observer, Builder);
   GISelValueTracking ValueTracking(Function, Target);
   LegalizationArtifactCombiner ArtifactCombiner(Builder, Function.registerInfo(), *Info,
@@ -452,6 +464,12 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi
     }
   } while (!InstructionWorklist.empty());
 
+  auto CSEValidation = CSEInfo.verify();
+  if (!CSEValidation) {
+    return std::unexpected(
+        withErrorContext(CSEValidation.error(), "GlobalISel CSE verification failed: "));
+  }
+
   for (MachineInstr *Instruction : layoutInstructions(Function)) {
     const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
     if (Descriptor == nullptr)
diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp
index def363a..a0b0981 100644
--- a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp
+++ b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp
@@ -69,21 +69,41 @@ struct ScalarLayout final {
   return Function.createMemOperand(std::move(Description));
 }
 
+[[nodiscard]] Expected<Register> resultRegister(MachineInstr &Instruction) {
+  const MachineOperand *Definition = Instruction.operandAt(0);
+  const Register *Result = Definition == nullptr ? nullptr : Definition->getIf<Register>();
+  if (Result == nullptr || !Definition->isDef()) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "machine IR builder returned an instruction without a register result");
+  }
+  return *Result;
+}
+
+[[nodiscard]] Expected<Register> buildConstantRegister(MachineIRBuilder &Builder, LowLevelType Type,
+                                                       APInt Value) {
+  auto Built = Builder.buildConstant(Type, std::move(Value));
+  if (!Built)
+    return std::unexpected(Built.error());
+  return resultRegister(**Built);
+}
+
+[[nodiscard]] Expected<Register> buildConstantRegister(MachineIRBuilder &Builder, LowLevelType Type,
+                                                       std::int64_t Value) {
+  auto Immediate = APInt::fromSigned(Type.scalarBitWidth(), Value);
+  if (!Immediate)
+    return std::unexpected(Immediate.error());
+  return buildConstantRegister(Builder, Type, std::move(*Immediate));
+}
+
 [[nodiscard]] Expected<Register> buildConstantBefore(MachineIRBuilder &Builder,
                                                      MachineInstr &Anchor, LowLevelType Type,
                                                      std::uint64_t Value) {
-  auto Result = Builder.function().registerInfo().createVirtualRegister(Type);
-  if (!Result)
-    return std::unexpected(Result.error());
   auto Immediate = APInt::fromUnsigned(Type.scalarBitWidth(), Value);
   if (!Immediate)
     return std::unexpected(Immediate.error());
   if (auto Point = Builder.setInsertPointBefore(Anchor); !Point)
     return std::unexpected(Point.error());
-  auto Built = Builder.buildConstant(*Result, std::move(*Immediate));
-  if (!Built)
-    return std::unexpected(Built.error());
-  return *Result;
+  return buildConstantRegister(Builder, Type, std::move(*Immediate));
 }
 
 [[nodiscard]] Expected<Register> buildBinaryBefore(MachineIRBuilder &Builder, MachineInstr &Anchor,
@@ -152,11 +172,12 @@ Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction
     return std::unexpected(Point.error());
 
   if (WideSize >= DestinationSize) {
-    auto Result = MRI.createVirtualRegister(WideType);
+    auto BuiltResult = MIRBuilder.buildZExt(WideType, *FirstSource);
+    if (!BuiltResult)
+      return std::unexpected(BuiltResult.error());
+    auto Result = resultRegister(**BuiltResult);
     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) {
@@ -171,23 +192,22 @@ Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction
         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);
+      auto BuiltExtendedInput = MIRBuilder.buildZExt(WideType, *Source);
+      if (!BuiltExtendedInput)
+        return std::unexpected(BuiltExtendedInput.error());
+      auto ExtendedInput = resultRegister(**BuiltExtendedInput);
       if (!ExtendedInput)
         return std::unexpected(ExtendedInput.error());
+      auto ShiftAmount = buildConstantRegister(MIRBuilder, WideType,
+                                               static_cast<std::int64_t>((Index - 1U) * PartSize));
       if (!ShiftAmount)
         return std::unexpected(ShiftAmount.error());
+      auto BuiltShiftedInput = MIRBuilder.buildShl(WideType, *ExtendedInput, *ShiftAmount);
+      if (!BuiltShiftedInput)
+        return std::unexpected(BuiltShiftedInput.error());
+      auto ShiftedInput = resultRegister(**BuiltShiftedInput);
       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) {
@@ -240,11 +260,12 @@ Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction
 
   const std::uint64_t RequiredPartCount = MergeCount * WideSize;
   if (UnmergedRegisters.size() != RequiredPartCount) {
-    auto UndefRegister = MRI.createVirtualRegister(*GCDType);
+    auto BuiltUndef = MIRBuilder.buildUndef(*GCDType);
+    if (!BuiltUndef)
+      return std::unexpected(BuiltUndef.error());
+    auto UndefRegister = resultRegister(**BuiltUndef);
     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);
   }
@@ -256,11 +277,12 @@ Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction
     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);
+    auto BuiltMerge = MIRBuilder.buildMergeLikeInstr(WideType, Parts);
+    if (!BuiltMerge)
+      return std::unexpected(BuiltMerge.error());
+    auto MergeRegister = resultRegister(**BuiltMerge);
     if (!MergeRegister)
       return std::unexpected(MergeRegister.error());
-    if (auto Built = MIRBuilder.buildMergeLikeInstr(*MergeRegister, Parts); !Built)
-      return std::unexpected(Built.error());
     NewMergeRegisters.push_back(*MergeRegister);
   }
 
@@ -268,11 +290,12 @@ Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction
     if (auto Built = MIRBuilder.buildMergeLikeInstr(*Destination, NewMergeRegisters); !Built)
       return std::unexpected(Built.error());
   } else {
-    auto FinalMerge = MRI.createVirtualRegister(*WideDestinationType);
+    auto BuiltFinalMerge = MIRBuilder.buildMergeLikeInstr(*WideDestinationType, NewMergeRegisters);
+    if (!BuiltFinalMerge)
+      return std::unexpected(BuiltFinalMerge.error());
+    auto FinalMerge = resultRegister(**BuiltFinalMerge);
     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());
   }
@@ -347,16 +370,13 @@ Expected<void> LegalizerHelper::widenScalarUnmergeValues(MachineInstr &Instructi
       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());
+      auto ShiftAmount = buildConstantRegister(MIRBuilder, *SourceType,
+                                               static_cast<std::int64_t>(DestinationSize * Index));
+      if (!ShiftAmount)
+        return std::unexpected(ShiftAmount.error());
       if (auto Built = MIRBuilder.buildLShr(*ShiftedSource, SourceRegister, *ShiftAmount); !Built)
         return std::unexpected(Built.error());
       if (auto Built = MIRBuilder.buildTrunc(*Destination, *ShiftedSource); !Built)
@@ -553,15 +573,20 @@ Expected<LowLevelType> LegalizerHelper::buildLCMMergePieces(LowLevelType Destina
 
   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());
+    if (PadStrategy == GenericOpcode::G_ZEXT) {
+      auto Pad = buildConstantRegister(MIRBuilder, GCDType, 0);
+      if (!Pad)
+        return std::unexpected(Pad.error());
+      PadRegister = *Pad;
+    } else {
+      auto Built = MIRBuilder.buildUndef(GCDType);
+      if (!Built)
+        return std::unexpected(Built.error());
+      auto Pad = resultRegister(**Built);
+      if (!Pad)
+        return std::unexpected(Pad.error());
+      PadRegister = *Pad;
+    }
   }
 
   std::vector<Register> Remerge(static_cast<std::size_t>(PartCount));
@@ -580,15 +605,20 @@ Expected<LowLevelType> LegalizerHelper::buildLCMMergePieces(LowLevelType Destina
     }
 
     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 (PadStrategy == GenericOpcode::G_ZEXT) {
+        auto Pad = buildConstantRegister(MIRBuilder, NarrowType, 0);
+        if (!Pad)
+          return std::unexpected(Pad.error());
+        AllPadRegister = *Pad;
+      } else {
+        auto Built = MIRBuilder.buildUndef(NarrowType);
+        if (!Built)
+          return std::unexpected(Built.error());
+        auto Pad = resultRegister(**Built);
+        if (!Pad)
+          return std::unexpected(Pad.error());
+        AllPadRegister = *Pad;
+      }
     }
     if (!AllPadRegister.isNoRegister()) {
       Remerge[static_cast<std::size_t>(PartIndex)] = AllPadRegister;
@@ -597,12 +627,12 @@ Expected<LowLevelType> LegalizerHelper::buildLCMMergePieces(LowLevelType Destina
     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);
+      auto Built = MIRBuilder.buildMergeLikeInstr(NarrowType, SubMerge);
       if (!Built)
         return std::unexpected(Built.error());
+      auto RemergeRegister = resultRegister(**Built);
+      if (!RemergeRegister)
+        return std::unexpected(RemergeRegister.error());
       Remerge[static_cast<std::size_t>(PartIndex)] = *RemergeRegister;
     }
     if (AllMergePartsArePadding && AllPadRegister.isNoRegister())
@@ -701,6 +731,95 @@ Expected<void> LegalizerHelper::widenScalarDst(MachineInstr &Instruction, LowLev
   return Operand->setRegister(*WideDestination);
 }
 
+Expected<void> LegalizerHelper::widenScalarAddSubOverflow(MachineInstr &Instruction,
+                                                          std::size_t TypeIndex,
+                                                          LowLevelType WideType) {
+  if (TypeIndex != 0)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "add/sub overflow widening requires type index zero");
+
+  const GenericOpcode Generic = static_cast<GenericOpcode>(Instruction.opcode().value());
+  GenericOpcode ArithmeticOpcode;
+  GenericOpcode ExtensionOpcode;
+  switch (Generic) {
+  case GenericOpcode::G_SADDO:
+    ArithmeticOpcode = GenericOpcode::G_ADD;
+    ExtensionOpcode = GenericOpcode::G_SEXT;
+    break;
+  case GenericOpcode::G_SSUBO:
+    ArithmeticOpcode = GenericOpcode::G_SUB;
+    ExtensionOpcode = GenericOpcode::G_SEXT;
+    break;
+  case GenericOpcode::G_UADDO:
+    ArithmeticOpcode = GenericOpcode::G_ADD;
+    ExtensionOpcode = GenericOpcode::G_ZEXT;
+    break;
+  case GenericOpcode::G_USUBO:
+    ArithmeticOpcode = GenericOpcode::G_SUB;
+    ExtensionOpcode = GenericOpcode::G_ZEXT;
+    break;
+  default:
+    return makeUnexpected(ErrorCode::InternalError,
+                          "unexpected opcode during add/sub overflow widening");
+  }
+
+  const Register Destination = *Instruction.operandAt(0)->getIf<Register>();
+  const Register Overflow = *Instruction.operandAt(1)->getIf<Register>();
+  const Register Left = *Instruction.operandAt(2)->getIf<Register>();
+  const Register Right = *Instruction.operandAt(3)->getIf<Register>();
+  auto OriginalType = MRI.getType(Destination);
+  if (!OriginalType)
+    return std::unexpected(OriginalType.error());
+
+  auto WideLeft = MRI.createVirtualRegister(WideType);
+  auto WideRight = MRI.createVirtualRegister(WideType);
+  auto WideResult = MRI.createVirtualRegister(WideType);
+  auto TruncatedResult = MRI.createVirtualRegister(*OriginalType);
+  auto ExtendedResult = MRI.createVirtualRegister(WideType);
+  if (!WideLeft)
+    return std::unexpected(WideLeft.error());
+  if (!WideRight)
+    return std::unexpected(WideRight.error());
+  if (!WideResult)
+    return std::unexpected(WideResult.error());
+  if (!TruncatedResult)
+    return std::unexpected(TruncatedResult.error());
+  if (!ExtendedResult)
+    return std::unexpected(ExtendedResult.error());
+
+  if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+    return std::unexpected(Point.error());
+  if (auto Built = MIRBuilder.buildInstr(opcode(ExtensionOpcode), {*WideLeft}, {Left}); !Built)
+    return std::unexpected(Built.error());
+  if (auto Built = MIRBuilder.buildInstr(opcode(ExtensionOpcode), {*WideRight}, {Right}); !Built)
+    return std::unexpected(Built.error());
+  if (auto Built =
+          MIRBuilder.buildInstr(opcode(ArithmeticOpcode), {*WideResult}, {*WideLeft, *WideRight});
+      !Built) {
+    return std::unexpected(Built.error());
+  }
+  if (auto Built = MIRBuilder.buildTrunc(*TruncatedResult, *WideResult); !Built)
+    return std::unexpected(Built.error());
+  if (auto Built =
+          MIRBuilder.buildInstr(opcode(ExtensionOpcode), {*ExtendedResult}, {*TruncatedResult});
+      !Built) {
+    return std::unexpected(Built.error());
+  }
+  if (auto Built =
+          MIRBuilder.buildICmp(IntegerPredicate::NotEqual, Overflow, *WideResult, *ExtendedResult);
+      !Built) {
+    return std::unexpected(Built.error());
+  }
+  if (auto Built = MIRBuilder.buildTrunc(Destination, *WideResult); !Built)
+    return std::unexpected(Built.error());
+
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "add/sub overflow instruction became detached during widening");
+  return Block->removeInstruction(Instruction);
+}
+
 Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size_t TypeIndex,
                                             LowLevelType WideType) {
   auto Query = LegalizerInfo::buildQuery(Instruction, Function, MIRBuilder.target());
@@ -713,14 +832,14 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
                           "scalar widening has an invalid type index or target type");
   }
 
-  const auto widenSource = [&](std::size_t OperandIndex, GenericOpcode ExtensionOpcode) {
+  const auto WidenSource = [&](std::size_t OperandIndex, GenericOpcode ExtensionOpcode) {
     return widenScalarSrc(Instruction, WideType, OperandIndex, ExtensionOpcode);
   };
-  const auto widenDestination = [&](std::size_t OperandIndex = 0,
+  const auto WidenDestination = [&](std::size_t OperandIndex = 0,
                                     GenericOpcode TruncOpcode = GenericOpcode::G_TRUNC) {
     return widenScalarDst(Instruction, WideType, OperandIndex, TruncOpcode);
   };
-  const auto apply = [](Expected<void> Result) -> Expected<void> {
+  const auto Apply = [](Expected<void> Result) -> Expected<void> {
     if (!Result)
       return std::unexpected(Result.error());
     return {};
@@ -745,9 +864,9 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
     if (TypeIndex != 0)
       return makeUnexpected(ErrorCode::VerificationError,
                             "atomic RMW value widening has an invalid type index");
-    if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result)
+    if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ANYEXT)); !Result)
       return Result;
-    if (auto Result = apply(widenDestination()); !Result)
+    if (auto Result = Apply(WidenDestination()); !Result)
       return Result;
     break;
 
@@ -755,28 +874,28 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
     if (TypeIndex != 0)
       return makeUnexpected(ErrorCode::VerificationError,
                             "compare-exchange widening has an invalid type index");
-    if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result)
+    if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ANYEXT)); !Result)
       return Result;
-    if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result)
+    if (auto Result = Apply(WidenSource(3, GenericOpcode::G_ANYEXT)); !Result)
       return Result;
-    if (auto Result = apply(widenDestination()); !Result)
+    if (auto Result = Apply(WidenDestination()); !Result)
       return Result;
     break;
 
   case GenericOpcode::G_ATOMIC_CMPXCHG_WITH_SUCCESS:
     if (TypeIndex == 0) {
-      if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result)
+      if (auto Result = Apply(WidenSource(3, GenericOpcode::G_ANYEXT)); !Result)
         return Result;
-      if (auto Result = apply(widenSource(4, GenericOpcode::G_ANYEXT)); !Result)
+      if (auto Result = Apply(WidenSource(4, GenericOpcode::G_ANYEXT)); !Result)
         return Result;
-      if (auto Result = apply(widenDestination()); !Result)
+      if (auto Result = Apply(WidenDestination()); !Result)
         return Result;
       break;
     }
     if (TypeIndex != 1)
       return makeUnexpected(ErrorCode::VerificationError,
                             "compare-exchange success widening has an invalid type index");
-    if (auto Result = apply(widenDestination(1)); !Result)
+    if (auto Result = Apply(WidenDestination(1)); !Result)
       return Result;
     break;
 
@@ -804,11 +923,17 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
       return std::unexpected(Extended.error());
     if (auto Replaced = SourceOperand->setIntegerImmediate(std::move(*Extended)); !Replaced)
       return std::unexpected(Replaced.error());
-    if (auto Result = apply(widenDestination()); !Result)
+    if (auto Result = Apply(WidenDestination()); !Result)
       return Result;
     break;
   }
 
+  case GenericOpcode::G_SADDO:
+  case GenericOpcode::G_SSUBO:
+  case GenericOpcode::G_UADDO:
+  case GenericOpcode::G_USUBO:
+    return widenScalarAddSubOverflow(Instruction, TypeIndex, WideType);
+
   case GenericOpcode::G_ADD:
   case GenericOpcode::G_SUB:
   case GenericOpcode::G_MUL:
@@ -818,11 +943,11 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
     if (TypeIndex != 0)
       return makeUnexpected(ErrorCode::VerificationError,
                             "binary operation widening has an invalid type index");
-    if (auto Result = apply(widenSource(1, GenericOpcode::G_ANYEXT)); !Result)
+    if (auto Result = Apply(WidenSource(1, GenericOpcode::G_ANYEXT)); !Result)
       return Result;
-    if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result)
+    if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ANYEXT)); !Result)
       return Result;
-    if (auto Result = apply(widenDestination()); !Result)
+    if (auto Result = Apply(WidenDestination()); !Result)
       return Result;
     break;
 
@@ -834,11 +959,11 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
     if (TypeIndex != 0)
       return makeUnexpected(ErrorCode::VerificationError,
                             "signed operation widening has an invalid type index");
-    if (auto Result = apply(widenSource(1, GenericOpcode::G_SEXT)); !Result)
+    if (auto Result = Apply(WidenSource(1, GenericOpcode::G_SEXT)); !Result)
       return Result;
-    if (auto Result = apply(widenSource(2, GenericOpcode::G_SEXT)); !Result)
+    if (auto Result = Apply(WidenSource(2, GenericOpcode::G_SEXT)); !Result)
       return Result;
-    if (auto Result = apply(widenDestination()); !Result)
+    if (auto Result = Apply(WidenDestination()); !Result)
       return Result;
     break;
 
@@ -850,11 +975,11 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
     if (TypeIndex != 0)
       return makeUnexpected(ErrorCode::VerificationError,
                             "unsigned operation widening has an invalid type index");
-    if (auto Result = apply(widenSource(1, GenericOpcode::G_ZEXT)); !Result)
+    if (auto Result = Apply(WidenSource(1, GenericOpcode::G_ZEXT)); !Result)
       return Result;
-    if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result)
+    if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ZEXT)); !Result)
       return Result;
-    if (auto Result = apply(widenDestination()); !Result)
+    if (auto Result = Apply(WidenDestination()); !Result)
       return Result;
     break;
 
@@ -867,16 +992,16 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
         ExtensionOpcode = GenericOpcode::G_ZEXT;
       else if (Instruction.opcode() == opcode(GenericOpcode::G_ASHR))
         ExtensionOpcode = GenericOpcode::G_SEXT;
-      if (auto Result = apply(widenSource(1, ExtensionOpcode)); !Result)
+      if (auto Result = Apply(WidenSource(1, ExtensionOpcode)); !Result)
         return Result;
-      if (auto Result = apply(widenDestination()); !Result)
+      if (auto Result = Apply(WidenDestination()); !Result)
         return Result;
       break;
     }
     if (TypeIndex != 1)
       return makeUnexpected(ErrorCode::VerificationError,
                             "shift widening has an invalid type index");
-    if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result)
+    if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ZEXT)); !Result)
       return Result;
     break;
 
@@ -884,7 +1009,7 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
   case GenericOpcode::G_ROTR:
     if (TypeIndex != 1)
       return makeUnexpected(ErrorCode::Unsupported, "rotate value widening is not defined");
-    if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result)
+    if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ZEXT)); !Result)
       return Result;
     break;
 
@@ -893,9 +1018,9 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
     if (TypeIndex != 0)
       return makeUnexpected(ErrorCode::VerificationError,
                             "unary operation widening has an invalid type index");
-    if (auto Result = apply(widenSource(1, GenericOpcode::G_ANYEXT)); !Result)
+    if (auto Result = Apply(WidenSource(1, GenericOpcode::G_ANYEXT)); !Result)
       return Result;
-    if (auto Result = apply(widenDestination()); !Result)
+    if (auto Result = Apply(WidenDestination()); !Result)
       return Result;
     break;
 
@@ -903,15 +1028,15 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
     if (TypeIndex != 0)
       return makeUnexpected(ErrorCode::VerificationError,
                             "absolute-value widening has an invalid type index");
-    if (auto Result = apply(widenSource(1, GenericOpcode::G_SEXT)); !Result)
+    if (auto Result = Apply(WidenSource(1, GenericOpcode::G_SEXT)); !Result)
       return Result;
-    if (auto Result = apply(widenDestination()); !Result)
+    if (auto Result = Apply(WidenDestination()); !Result)
       return Result;
     break;
 
   case GenericOpcode::G_ICMP:
     if (TypeIndex == 0) {
-      if (auto Result = apply(widenDestination()); !Result)
+      if (auto Result = Apply(WidenDestination()); !Result)
         return Result;
       break;
     }
@@ -952,27 +1077,27 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
           IsSigned || Info.isSExtCheaperThanZExt(Query->Types[TypeIndex], WideType)
               ? GenericOpcode::G_SEXT
               : GenericOpcode::G_ZEXT;
-      if (auto Result = apply(widenSource(2, ExtensionOpcode)); !Result)
+      if (auto Result = Apply(WidenSource(2, ExtensionOpcode)); !Result)
         return Result;
-      if (auto Result = apply(widenSource(3, ExtensionOpcode)); !Result)
+      if (auto Result = Apply(WidenSource(3, ExtensionOpcode)); !Result)
         return Result;
     }
     break;
 
   case GenericOpcode::G_SELECT:
     if (TypeIndex == 0) {
-      if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result)
+      if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ANYEXT)); !Result)
         return Result;
-      if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result)
+      if (auto Result = Apply(WidenSource(3, GenericOpcode::G_ANYEXT)); !Result)
         return Result;
-      if (auto Result = apply(widenDestination()); !Result)
+      if (auto Result = Apply(WidenDestination()); !Result)
         return Result;
       break;
     }
     if (TypeIndex != 1)
       return makeUnexpected(ErrorCode::VerificationError,
                             "select widening has an invalid type index");
-    if (auto Result = apply(widenSource(1, GenericOpcode::G_ZEXT)); !Result)
+    if (auto Result = Apply(WidenSource(1, GenericOpcode::G_ZEXT)); !Result)
       return Result;
     break;
 
@@ -980,7 +1105,7 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
     if (TypeIndex != 1)
       return makeUnexpected(ErrorCode::Unsupported,
                             "floating-point extension destination widening is not defined");
-    if (auto Result = apply(widenSource(1, GenericOpcode::G_FPEXT)); !Result)
+    if (auto Result = Apply(WidenSource(1, GenericOpcode::G_FPEXT)); !Result)
       return Result;
     break;
 
@@ -990,28 +1115,28 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
   case GenericOpcode::G_INTRINSIC_LLRINT:
   case GenericOpcode::G_IS_FPCLASS:
     if (TypeIndex == 0) {
-      if (auto Result = apply(widenDestination()); !Result)
+      if (auto Result = Apply(WidenDestination()); !Result)
         return Result;
       break;
     }
     if (TypeIndex != 1)
       return makeUnexpected(ErrorCode::VerificationError,
                             "floating-to-integer widening has an invalid type index");
-    if (auto Result = apply(widenSource(1, GenericOpcode::G_FPEXT)); !Result)
+    if (auto Result = Apply(WidenSource(1, GenericOpcode::G_FPEXT)); !Result)
       return Result;
     break;
 
   case GenericOpcode::G_SITOFP:
   case GenericOpcode::G_UITOFP:
     if (TypeIndex == 0) {
-      if (auto Result = apply(widenDestination(0, GenericOpcode::G_FPTRUNC)); !Result)
+      if (auto Result = Apply(WidenDestination(0, GenericOpcode::G_FPTRUNC)); !Result)
         return Result;
       break;
     }
     if (TypeIndex != 1)
       return makeUnexpected(ErrorCode::VerificationError,
                             "integer-to-floating widening has an invalid type index");
-    if (auto Result = apply(widenSource(1, Instruction.opcode() == opcode(GenericOpcode::G_SITOFP)
+    if (auto Result = Apply(WidenSource(1, Instruction.opcode() == opcode(GenericOpcode::G_SITOFP)
                                                ? GenericOpcode::G_SEXT
                                                : GenericOpcode::G_ZEXT));
         !Result)
@@ -1275,15 +1400,19 @@ Expected<void> LegalizerHelper::lowerVAArg(MachineInstr &Instruction) {
   auto DestinationInfo = MRI.virtualRegisterInfo(*Destination);
   auto PointerInfo = MRI.virtualRegisterInfo(*ListPointer);
   auto RequestedAlignment = signedImmediate(*AlignmentOperand);
-  if (!DestinationInfo || !PointerInfo || !DestinationInfo->get().Type ||
-      !PointerInfo->get().Type || !RequestedAlignment || *RequestedAlignment <= 0 ||
+  if (!DestinationInfo || !PointerInfo)
+    return makeUnexpected(ErrorCode::VerificationError, "G_VAARG has invalid register information");
+  const std::optional<LowLevelType> &DestinationTypeInfo = DestinationInfo->get().Type;
+  const std::optional<LowLevelType> &PointerTypeInfo = PointerInfo->get().Type;
+  if (!DestinationTypeInfo.has_value() || !PointerTypeInfo.has_value() || !RequestedAlignment ||
+      *RequestedAlignment <= 0 ||
       !std::has_single_bit(static_cast<std::uint64_t>(*RequestedAlignment))) {
     return makeUnexpected(ErrorCode::VerificationError,
                           "G_VAARG has invalid type or alignment information");
   }
 
-  const LowLevelType DestinationType = *DestinationInfo->get().Type;
-  const LowLevelType PointerType = *PointerInfo->get().Type;
+  const LowLevelType DestinationType = DestinationTypeInfo.value();
+  const LowLevelType PointerType = PointerTypeInfo.value();
   const auto DestinationLayout = scalarLayout(DestinationType);
   const auto PointerLayout = scalarLayout(PointerType);
   if (!DestinationLayout || !PointerLayout || !PointerType.isPointer()) {
@@ -1415,6 +1544,9 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
       return lowerAbsDiffToMinMax(Instruction);
     return lowerAbsDiffToSelect(Instruction);
   }
+  case GenericOpcode::G_SADDO:
+  case GenericOpcode::G_SSUBO:
+    return lowerSignedAddSubOverflow(Instruction);
   case GenericOpcode::G_SEXT_INREG: {
     const Register Destination = *Instruction.operandAt(0)->getIf<Register>();
     const Register Source = *Instruction.operandAt(1)->getIf<Register>();
@@ -1425,18 +1557,16 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
     if (!Type)
       return std::unexpected(Type.error());
 
-    auto ShiftAmount = MRI.createVirtualRegister(*Type);
     auto Temporary = MRI.createVirtualRegister(*Type);
-    if (!ShiftAmount)
-      return std::unexpected(ShiftAmount.error());
     if (!Temporary)
       return std::unexpected(Temporary.error());
 
     if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
       return std::unexpected(Point.error());
     const std::int64_t Shift = static_cast<std::int64_t>(Type->scalarBitWidth()) - *SizeInBits;
-    if (auto Built = MIRBuilder.buildConstant(*ShiftAmount, Shift); !Built)
-      return std::unexpected(Built.error());
+    auto ShiftAmount = buildConstantRegister(MIRBuilder, *Type, Shift);
+    if (!ShiftAmount)
+      return std::unexpected(ShiftAmount.error());
     if (auto Built = MIRBuilder.buildShl(*Temporary, Source, *ShiftAmount); !Built)
       return std::unexpected(Built.error());
     if (auto Built = MIRBuilder.buildAShr(Destination, *Temporary, *ShiftAmount); !Built)
@@ -1490,7 +1620,6 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
     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)
@@ -1501,8 +1630,6 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
       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)
@@ -1519,8 +1646,9 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
       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());
+    auto Zero = buildConstantRegister(MIRBuilder, *ResultType, 0);
+    if (!Zero)
+      return std::unexpected(Zero.error());
     if (auto Built =
             MIRBuilder.buildICmp(IntegerPredicate::Equal, *ResultIsZero, *NewResult, *Zero);
         !Built)
@@ -1569,7 +1697,6 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
     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)
@@ -1578,8 +1705,6 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
       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)
@@ -1596,8 +1721,9 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
       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());
+    auto Zero = buildConstantRegister(MIRBuilder, *ResultType, 0);
+    if (!Zero)
+      return std::unexpected(Zero.error());
     if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::Equal, *TemporaryResultIsZero,
                                           *TemporaryResult, *Zero);
         !Built)
@@ -1630,11 +1756,8 @@ Expected<void> LegalizerHelper::lowerAbsToAddXor(MachineInstr &Instruction) {
   if (!Type)
     return std::unexpected(Type.error());
 
-  auto ShiftAmount = MRI.createVirtualRegister(*Type);
   auto Shift = MRI.createVirtualRegister(*Type);
   auto Add = MRI.createVirtualRegister(*Type);
-  if (!ShiftAmount)
-    return std::unexpected(ShiftAmount.error());
   if (!Shift)
     return std::unexpected(Shift.error());
   if (!Add)
@@ -1642,8 +1765,10 @@ Expected<void> LegalizerHelper::lowerAbsToAddXor(MachineInstr &Instruction) {
 
   if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
     return std::unexpected(Point.error());
-  if (auto Built = MIRBuilder.buildConstant(*ShiftAmount, Type->scalarBitWidth() - 1U); !Built)
-    return std::unexpected(Built.error());
+  auto ShiftAmount = buildConstantRegister(MIRBuilder, *Type,
+                                           static_cast<std::int64_t>(Type->scalarBitWidth() - 1U));
+  if (!ShiftAmount)
+    return std::unexpected(ShiftAmount.error());
   if (auto Built = MIRBuilder.buildAShr(*Shift, Source, *ShiftAmount); !Built)
     return std::unexpected(Built.error());
   if (auto Built = MIRBuilder.buildAdd(*Add, Source, *Shift); !Built)
@@ -1736,6 +1861,76 @@ Expected<void> LegalizerHelper::lowerAbsDiffToMinMax(MachineInstr &Instruction)
   return Block->removeInstruction(Instruction);
 }
 
+Expected<void> LegalizerHelper::lowerSignedAddSubOverflow(MachineInstr &Instruction) {
+  const bool IsAdd = Instruction.opcode() == opcode(GenericOpcode::G_SADDO);
+  const Register Destination = *Instruction.operandAt(0)->getIf<Register>();
+  const Register Overflow = *Instruction.operandAt(1)->getIf<Register>();
+  const Register Left = *Instruction.operandAt(2)->getIf<Register>();
+  const Register Right = *Instruction.operandAt(3)->getIf<Register>();
+  auto Type = MRI.getType(Destination);
+  auto BooleanType = MRI.getType(Overflow);
+  if (!Type)
+    return std::unexpected(Type.error());
+  if (!BooleanType)
+    return std::unexpected(BooleanType.error());
+
+  auto Result = MRI.cloneVirtualRegister(Destination);
+  auto FirstComparison = MRI.createVirtualRegister(*BooleanType);
+  auto SecondComparison = MRI.createVirtualRegister(*BooleanType);
+  if (!Result)
+    return std::unexpected(Result.error());
+  if (!FirstComparison)
+    return std::unexpected(FirstComparison.error());
+  if (!SecondComparison)
+    return std::unexpected(SecondComparison.error());
+
+  if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+    return std::unexpected(Point.error());
+  if (auto Built = IsAdd ? MIRBuilder.buildAdd(*Result, Left, Right)
+                         : MIRBuilder.buildSub(*Result, Left, Right);
+      !Built) {
+    return std::unexpected(Built.error());
+  }
+  auto Zero = buildConstantRegister(MIRBuilder, *Type, 0);
+  if (!Zero)
+    return std::unexpected(Zero.error());
+  if (IsAdd) {
+    if (auto Built =
+            MIRBuilder.buildICmp(IntegerPredicate::SignedLessThan, *FirstComparison, *Result, Left);
+        !Built) {
+      return std::unexpected(Built.error());
+    }
+    if (auto Built =
+            MIRBuilder.buildICmp(IntegerPredicate::SignedLessThan, *SecondComparison, Right, *Zero);
+        !Built) {
+      return std::unexpected(Built.error());
+    }
+    if (auto Built = MIRBuilder.buildXor(Overflow, *SecondComparison, *FirstComparison); !Built)
+      return std::unexpected(Built.error());
+  } else {
+    if (auto Built =
+            MIRBuilder.buildICmp(IntegerPredicate::SignedLessThan, *FirstComparison, Left, Right);
+        !Built) {
+      return std::unexpected(Built.error());
+    }
+    if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::SignedLessThan, *SecondComparison,
+                                          *Result, *Zero);
+        !Built) {
+      return std::unexpected(Built.error());
+    }
+    if (auto Built = MIRBuilder.buildXor(Overflow, *FirstComparison, *SecondComparison); !Built)
+      return std::unexpected(Built.error());
+  }
+  if (auto Built = MIRBuilder.buildCopy(Destination, *Result); !Built)
+    return std::unexpected(Built.error());
+
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "signed add/sub overflow instruction became detached during lowering");
+  return Block->removeInstruction(Instruction);
+}
+
 Expected<void> LegalizerHelper::legalize(MachineInstr &Instruction,
                                          const LegalizationDecision &Decision) {
   if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp
index c4cf946..ee7f856 100644
--- a/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp
+++ b/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp
@@ -295,7 +295,7 @@ LegalizeRuleSet &LegalizeRuleSet::clampScalar(std::size_t TypeIndex, LowLevelTyp
 
 LegalizeRuleSet &LegalizeRuleSet::scalarSameSizeAs(std::size_t TypeIndex,
                                                    std::size_t ReferenceTypeIndex) {
-  const auto changeToReference = [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) {
+  const auto ChangeToReference = [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) {
     return std::pair{TypeIndex, scalarType(Query.Types[ReferenceTypeIndex].scalarBitWidth())};
   };
   widenScalarIf(
@@ -306,7 +306,7 @@ LegalizeRuleSet &LegalizeRuleSet::scalarSameSizeAs(std::size_t TypeIndex,
                Query.Types[TypeIndex].scalarBitWidth() <
                    Query.Types[ReferenceTypeIndex].scalarBitWidth();
       },
-      changeToReference);
+      ChangeToReference);
   return narrowScalarIf(
       [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) {
         return TypeIndex < Query.Types.size() && ReferenceTypeIndex < Query.Types.size() &&
@@ -315,7 +315,7 @@ LegalizeRuleSet &LegalizeRuleSet::scalarSameSizeAs(std::size_t TypeIndex,
                Query.Types[TypeIndex].scalarBitWidth() >
                    Query.Types[ReferenceTypeIndex].scalarBitWidth();
       },
-      changeToReference);
+      ChangeToReference);
 }
 
 LegalizeRuleSet &LegalizeRuleSet::lowerIfMemSizeNotByteSizePow2(std::size_t MemoryIndex) {
@@ -327,6 +327,10 @@ LegalizeRuleSet &LegalizeRuleSet::lowerIfMemSizeNotByteSizePow2(std::size_t Memo
   });
 }
 
+LegalizeRuleSet &LegalizeRuleSet::custom() {
+  return customIf([](const LegalizationQuery &) { return true; });
+}
+
 LegalizeRuleSet &LegalizeRuleSet::alwaysLegal() {
   return legalIf([](const LegalizationQuery &) { return true; });
 }
@@ -401,13 +405,15 @@ Expected<LegalizationQuery> LegalizerInfo::buildQuery(const MachineInstr &Instru
     auto Info = Function.registerInfo().virtualRegisterInfo(*Reg);
     if (!Info)
       return std::unexpected(Info.error());
-    if (!Info->get().Type)
+    const std::optional<LowLevelType> &RegisterType = Info->get().Type;
+    if (!RegisterType.has_value())
       return makeUnexpected(ErrorCode::VerificationError,
                             "legalization type operand has no LowLevelType");
-    if (OptionalTypes[TypeIndex] && *OptionalTypes[TypeIndex] != *Info->get().Type)
+    std::optional<LowLevelType> &ExistingType = OptionalTypes[TypeIndex];
+    if (ExistingType.has_value() && ExistingType.value() != RegisterType.value())
       return makeUnexpected(ErrorCode::VerificationError,
                             "legalization type operands disagree within one type index");
-    OptionalTypes[TypeIndex] = *Info->get().Type;
+    ExistingType = RegisterType.value();
     TypeOperands[TypeIndex].push_back(Index);
   }
 
diff --git a/backend/lib/CodeGen/MachineIRBuilder.cpp b/backend/lib/CodeGen/MachineIRBuilder.cpp
index e3ac0bf..36f697b 100644
--- a/backend/lib/CodeGen/MachineIRBuilder.cpp
+++ b/backend/lib/CodeGen/MachineIRBuilder.cpp
@@ -11,6 +11,8 @@
 #include "rcc/CodeGen/MachineRegisterInfo.h"
 
 #include <algorithm>
+#include <array>
+#include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <memory>
@@ -21,6 +23,34 @@
 
 namespace rcc {
 
+Register MachineIRBuilderResult::reg() const noexcept {
+  assert(ResultKind == Kind::Register && "machine IR builder result is not a register");
+  return Reg;
+}
+
+LowLevelType MachineIRBuilderResult::type() const noexcept {
+  assert(ResultKind == Kind::Type && "machine IR builder result is not a type");
+  return Type;
+}
+
+Expected<LowLevelType> MachineIRBuilderResult::type(const MachineRegisterInfo &MRI) const {
+  if (ResultKind == Kind::Type)
+    return Type;
+  return MRI.getType(Reg);
+}
+
+Expected<void> MachineIRBuilderResult::addDef(MachineRegisterInfo &MRI,
+                                              MachineInstrBuilder &Builder) const {
+  Register Definition = Reg;
+  if (ResultKind == Kind::Type) {
+    auto Created = MRI.createVirtualRegister(Type);
+    if (!Created)
+      return std::unexpected(Created.error());
+    Definition = *Created;
+  }
+  return Builder.addDef(Definition);
+}
+
 MachineInstrBuilder::MachineInstrBuilder(MachineFunction &Function, const TargetDescription &Target,
                                          const InstructionDescriptor &Descriptor,
                                          MachineBasicBlock &InsertBlock,
@@ -709,13 +739,24 @@ Expected<MachineInstrBuilder> MachineIRBuilder::buildInstr(Opcode InstructionOpc
 }
 
 Expected<MachineInstr *>
-MachineIRBuilder::buildInstr(Opcode InstructionOpcode, std::initializer_list<Register> Destinations,
+MachineIRBuilder::buildInstr(Opcode InstructionOpcode,
+                             std::initializer_list<MachineIRBuilderResult> Destinations,
                              std::initializer_list<Register> Sources) const {
+  return buildInstr(
+      InstructionOpcode,
+      std::span<const MachineIRBuilderResult>(Destinations.begin(), Destinations.size()),
+      std::span<const Register>(Sources.begin(), Sources.size()));
+}
+
+Expected<MachineInstr *>
+MachineIRBuilder::buildInstr(Opcode InstructionOpcode,
+                             std::span<const MachineIRBuilderResult> Destinations,
+                             std::span<const Register> Sources) const {
   auto Pending = buildInstr(InstructionOpcode);
   if (!Pending)
     return std::unexpected(Pending.error());
-  for (Register Destination : Destinations) {
-    if (auto Added = Pending->addDef(Destination); !Added)
+  for (const MachineIRBuilderResult &Destination : Destinations) {
+    if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added)
       return std::unexpected(Added.error());
   }
   for (Register Source : Sources) {
@@ -732,77 +773,72 @@ Expected<LowLevelType> MachineIRBuilder::registerType(Register Reg) const {
   auto Info = Function->registerInfo().virtualRegisterInfo(Reg);
   if (!Info)
     return std::unexpected(Info.error());
-  if (!Info->get().Type)
+  const std::optional<LowLevelType> &Type = Info->get().Type;
+  if (!Type.has_value())
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "generic builder operand has no LowLevelType");
-  return *Info->get().Type;
+  return Type.value();
 }
 
 Expected<MachineInstr *> MachineIRBuilder::buildUnary(Opcode InstructionOpcode,
-                                                      Register Destination, Register Source) const {
-  auto Pending = buildInstr(InstructionOpcode);
-  if (!Pending)
-    return std::unexpected(Pending.error());
-  if (auto Added = Pending->addDef(Destination); !Added)
-    return std::unexpected(Added.error());
-  if (auto Added = Pending->addUse(Source); !Added)
-    return std::unexpected(Added.error());
-  return Pending->build();
+                                                      MachineIRBuilderResult Destination,
+                                                      Register Source) const {
+  const std::array Destinations{Destination};
+  const std::array Sources{Source};
+  return buildInstr(InstructionOpcode, std::span<const MachineIRBuilderResult>(Destinations),
+                    std::span<const Register>(Sources));
 }
 
 Expected<MachineInstr *> MachineIRBuilder::buildBinary(Opcode InstructionOpcode,
-                                                       Register Destination, Register Left,
-                                                       Register Right) const {
-  auto Pending = buildInstr(InstructionOpcode);
-  if (!Pending)
-    return std::unexpected(Pending.error());
-  if (auto Added = Pending->addDef(Destination); !Added)
-    return std::unexpected(Added.error());
-  if (auto Added = Pending->addUse(Left); !Added)
-    return std::unexpected(Added.error());
-  if (auto Added = Pending->addUse(Right); !Added)
-    return std::unexpected(Added.error());
-  return Pending->build();
+                                                       MachineIRBuilderResult Destination,
+                                                       Register Left, Register Right) const {
+  const std::array Destinations{Destination};
+  const std::array Sources{Left, Right};
+  return buildInstr(InstructionOpcode, std::span<const MachineIRBuilderResult>(Destinations),
+                    std::span<const Register>(Sources));
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildTrunc(Register Destination, Register Source) const {
+Expected<MachineInstr *> MachineIRBuilder::buildTrunc(MachineIRBuilderResult Destination,
+                                                      Register Source) const {
   return buildUnary(opcode(GenericOpcode::G_TRUNC), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildCopy(Register Destination, Register Source) const {
+Expected<MachineInstr *> MachineIRBuilder::buildCopy(MachineIRBuilderResult Destination,
+                                                     Register Source) const {
   return buildUnary(opcode(GenericOpcode::COPY), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildImplicitDef(Register Destination) const {
-  auto Pending = buildInstr(opcode(GenericOpcode::G_IMPLICIT_DEF));
-  if (!Pending)
-    return std::unexpected(Pending.error());
-  if (auto Added = Pending->addDef(Destination); !Added)
-    return std::unexpected(Added.error());
-  return Pending->build();
+Expected<MachineInstr *>
+MachineIRBuilder::buildImplicitDef(MachineIRBuilderResult Destination) const {
+  const std::array Destinations{Destination};
+  return buildInstr(opcode(GenericOpcode::G_IMPLICIT_DEF),
+                    std::span<const MachineIRBuilderResult>(Destinations),
+                    std::span<const Register>());
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildAnyExt(Register Destination,
+Expected<MachineInstr *> MachineIRBuilder::buildAnyExt(MachineIRBuilderResult Destination,
                                                        Register Source) const {
   return buildUnary(opcode(GenericOpcode::G_ANYEXT), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildZExt(Register Destination, Register Source) const {
+Expected<MachineInstr *> MachineIRBuilder::buildZExt(MachineIRBuilderResult Destination,
+                                                     Register Source) const {
   return buildUnary(opcode(GenericOpcode::G_ZEXT), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildSExt(Register Destination, Register Source) const {
+Expected<MachineInstr *> MachineIRBuilder::buildSExt(MachineIRBuilderResult Destination,
+                                                     Register Source) const {
   return buildUnary(opcode(GenericOpcode::G_SEXT), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildUndef(Register Destination) const {
+Expected<MachineInstr *> MachineIRBuilder::buildUndef(MachineIRBuilderResult Destination) const {
   return buildImplicitDef(Destination);
 }
 
 Expected<MachineInstr *> MachineIRBuilder::buildExtOrTrunc(Opcode ExtensionOpcode,
-                                                           Register Destination,
+                                                           MachineIRBuilderResult Destination,
                                                            Register Source) const {
-  auto DestinationType = registerType(Destination);
+  auto DestinationType = Destination.type(Function->registerInfo());
   if (!DestinationType)
     return std::unexpected(DestinationType.error());
   auto SourceType = registerType(Source);
@@ -817,30 +853,31 @@ Expected<MachineInstr *> MachineIRBuilder::buildExtOrTrunc(Opcode ExtensionOpcod
   return buildUnary(opcode(GenericOpcode::COPY), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildAnyExtOrTrunc(Register Destination,
+Expected<MachineInstr *> MachineIRBuilder::buildAnyExtOrTrunc(MachineIRBuilderResult Destination,
                                                               Register Source) const {
   return buildExtOrTrunc(opcode(GenericOpcode::G_ANYEXT), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildSExtOrTrunc(Register Destination,
+Expected<MachineInstr *> MachineIRBuilder::buildSExtOrTrunc(MachineIRBuilderResult Destination,
                                                             Register Source) const {
   return buildExtOrTrunc(opcode(GenericOpcode::G_SEXT), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildConstant(Register Destination, APInt Value) const {
+Expected<MachineInstr *> MachineIRBuilder::buildConstant(MachineIRBuilderResult Destination,
+                                                         APInt Value) const {
   auto Pending = buildInstr(opcode(GenericOpcode::G_CONSTANT));
   if (!Pending)
     return std::unexpected(Pending.error());
-  if (auto Added = Pending->addDef(Destination); !Added)
+  if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added)
     return std::unexpected(Added.error());
   if (auto Added = Pending->addIntegerImmediate(std::move(Value)); !Added)
     return std::unexpected(Added.error());
   return Pending->build();
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildConstant(Register Destination,
+Expected<MachineInstr *> MachineIRBuilder::buildConstant(MachineIRBuilderResult Destination,
                                                          std::int64_t Value) const {
-  auto Type = registerType(Destination);
+  auto Type = Destination.type(Function->registerInfo());
   if (!Type)
     return std::unexpected(Type.error());
   auto Immediate = APInt::fromSigned(Type->scalarBitWidth(), Value);
@@ -849,12 +886,13 @@ Expected<MachineInstr *> MachineIRBuilder::buildConstant(Register Destination,
   return buildConstant(Destination, std::move(*Immediate));
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildSExtInReg(Register Destination, Register Source,
+Expected<MachineInstr *> MachineIRBuilder::buildSExtInReg(MachineIRBuilderResult Destination,
+                                                          Register Source,
                                                           std::uint32_t Width) const {
   auto Pending = buildInstr(opcode(GenericOpcode::G_SEXT_INREG));
   if (!Pending)
     return std::unexpected(Pending.error());
-  if (auto Added = Pending->addDef(Destination); !Added)
+  if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added)
     return std::unexpected(Added.error());
   if (auto Added = Pending->addUse(Source); !Added)
     return std::unexpected(Added.error());
@@ -863,63 +901,63 @@ Expected<MachineInstr *> MachineIRBuilder::buildSExtInReg(Register Destination,
   return Pending->build();
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildAnd(Register Destination, Register Left,
-                                                    Register Right) const {
+Expected<MachineInstr *> MachineIRBuilder::buildAnd(MachineIRBuilderResult Destination,
+                                                    Register Left, Register Right) const {
   return buildBinary(opcode(GenericOpcode::G_AND), Destination, Left, Right);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildOr(Register Destination, Register Left,
-                                                   Register Right) const {
+Expected<MachineInstr *> MachineIRBuilder::buildOr(MachineIRBuilderResult Destination,
+                                                   Register Left, Register Right) const {
   return buildBinary(opcode(GenericOpcode::G_OR), Destination, Left, Right);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildXor(Register Destination, Register Left,
-                                                    Register Right) const {
+Expected<MachineInstr *> MachineIRBuilder::buildXor(MachineIRBuilderResult Destination,
+                                                    Register Left, Register Right) const {
   return buildBinary(opcode(GenericOpcode::G_XOR), Destination, Left, Right);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildAdd(Register Destination, Register Left,
-                                                    Register Right) const {
+Expected<MachineInstr *> MachineIRBuilder::buildAdd(MachineIRBuilderResult Destination,
+                                                    Register Left, Register Right) const {
   return buildBinary(opcode(GenericOpcode::G_ADD), Destination, Left, Right);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildSub(Register Destination, Register Left,
-                                                    Register Right) const {
+Expected<MachineInstr *> MachineIRBuilder::buildSub(MachineIRBuilderResult Destination,
+                                                    Register Left, Register Right) const {
   return buildBinary(opcode(GenericOpcode::G_SUB), Destination, Left, Right);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildShl(Register Destination, Register Left,
-                                                    Register Right) const {
+Expected<MachineInstr *> MachineIRBuilder::buildShl(MachineIRBuilderResult Destination,
+                                                    Register Left, Register Right) const {
   return buildBinary(opcode(GenericOpcode::G_SHL), Destination, Left, Right);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildLShr(Register Destination, Register Left,
-                                                     Register Right) const {
+Expected<MachineInstr *> MachineIRBuilder::buildLShr(MachineIRBuilderResult Destination,
+                                                     Register Left, Register Right) const {
   return buildBinary(opcode(GenericOpcode::G_LSHR), Destination, Left, Right);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildAShr(Register Destination, Register Left,
-                                                     Register Right) const {
+Expected<MachineInstr *> MachineIRBuilder::buildAShr(MachineIRBuilderResult Destination,
+                                                     Register Left, Register Right) const {
   return buildBinary(opcode(GenericOpcode::G_ASHR), Destination, Left, Right);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildPtrToInt(Register Destination,
+Expected<MachineInstr *> MachineIRBuilder::buildPtrToInt(MachineIRBuilderResult Destination,
                                                          Register Source) const {
   return buildUnary(opcode(GenericOpcode::G_PTRTOINT), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildIntToPtr(Register Destination,
+Expected<MachineInstr *> MachineIRBuilder::buildIntToPtr(MachineIRBuilderResult Destination,
                                                          Register Source) const {
   return buildUnary(opcode(GenericOpcode::G_INTTOPTR), Destination, Source);
 }
 
 Expected<MachineInstr *> MachineIRBuilder::buildICmp(IntegerPredicate Predicate,
-                                                     Register Destination, Register Left,
-                                                     Register Right) const {
+                                                     MachineIRBuilderResult Destination,
+                                                     Register Left, Register Right) const {
   auto Pending = buildInstr(opcode(GenericOpcode::G_ICMP));
   if (!Pending)
     return std::unexpected(Pending.error());
-  if (auto Added = Pending->addDef(Destination); !Added)
+  if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added)
     return std::unexpected(Added.error());
   if (auto Added = Pending->addIntegerPredicate(Predicate); !Added)
     return std::unexpected(Added.error());
@@ -931,9 +969,9 @@ Expected<MachineInstr *> MachineIRBuilder::buildICmp(IntegerPredicate Predicate,
 }
 
 Expected<MachineInstr *>
-MachineIRBuilder::buildMergeLikeInstr(Register Destination,
+MachineIRBuilder::buildMergeLikeInstr(MachineIRBuilderResult Destination,
                                       const std::vector<Register> &Sources) const {
-  auto DestinationType = registerType(Destination);
+  auto DestinationType = Destination.type(Function->registerInfo());
   if (!DestinationType)
     return std::unexpected(DestinationType.error());
   if (!DestinationType->isVector())
@@ -946,49 +984,33 @@ MachineIRBuilder::buildMergeLikeInstr(Register Destination,
     return std::unexpected(SourceType.error());
   const GenericOpcode MergeOpcode =
       SourceType->isVector() ? GenericOpcode::G_CONCAT_VECTORS : GenericOpcode::G_BUILD_VECTOR;
-  auto Pending = buildInstr(opcode(MergeOpcode));
-  if (!Pending)
-    return std::unexpected(Pending.error());
-  if (auto Added = Pending->addDef(Destination); !Added)
-    return std::unexpected(Added.error());
-  for (Register Source : Sources) {
-    if (auto Added = Pending->addUse(Source); !Added)
-      return std::unexpected(Added.error());
-  }
-  return Pending->build();
+  const std::array Destinations{Destination};
+  return buildInstr(opcode(MergeOpcode), std::span<const MachineIRBuilderResult>(Destinations),
+                    Sources);
 }
 
 Expected<MachineInstr *>
-MachineIRBuilder::buildMergeValues(Register Destination,
+MachineIRBuilder::buildMergeValues(MachineIRBuilderResult Destination,
                                    const std::vector<Register> &Sources) const {
-  auto Pending = buildInstr(opcode(GenericOpcode::G_MERGE_VALUES));
-  if (!Pending)
-    return std::unexpected(Pending.error());
-  if (auto Added = Pending->addDef(Destination); !Added)
-    return std::unexpected(Added.error());
-  for (Register Source : Sources) {
-    if (auto Added = Pending->addUse(Source); !Added)
-      return std::unexpected(Added.error());
-  }
-  return Pending->build();
+  const std::array Destinations{Destination};
+  return buildInstr(opcode(GenericOpcode::G_MERGE_VALUES),
+                    std::span<const MachineIRBuilderResult>(Destinations), Sources);
 }
 
 Expected<MachineInstr *>
 MachineIRBuilder::buildUnmergeValues(const std::vector<Register> &Destinations,
                                      Register Source) const {
-  auto Pending = buildInstr(opcode(GenericOpcode::G_UNMERGE_VALUES));
-  if (!Pending)
-    return std::unexpected(Pending.error());
-  for (Register Destination : Destinations) {
-    if (auto Added = Pending->addDef(Destination); !Added)
-      return std::unexpected(Added.error());
-  }
-  if (auto Added = Pending->addUse(Source); !Added)
-    return std::unexpected(Added.error());
-  return Pending->build();
+  std::vector<MachineIRBuilderResult> Results;
+  Results.reserve(Destinations.size());
+  for (Register Destination : Destinations)
+    Results.emplace_back(Destination);
+  const std::array Sources{Source};
+  return buildInstr(opcode(GenericOpcode::G_UNMERGE_VALUES), Results,
+                    std::span<const Register>(Sources));
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildExtract(Register Destination, Register Source,
+Expected<MachineInstr *> MachineIRBuilder::buildExtract(MachineIRBuilderResult Destination,
+                                                        Register Source,
                                                         std::uint64_t Offset) const {
   if (Offset > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()))
     return makeUnexpected(ErrorCode::InvalidArgument,
@@ -996,7 +1018,7 @@ Expected<MachineInstr *> MachineIRBuilder::buildExtract(Register Destination, Re
   auto Pending = buildInstr(opcode(GenericOpcode::G_EXTRACT));
   if (!Pending)
     return std::unexpected(Pending.error());
-  if (auto Added = Pending->addDef(Destination); !Added)
+  if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added)
     return std::unexpected(Added.error());
   if (auto Added = Pending->addUse(Source); !Added)
     return std::unexpected(Added.error());
@@ -1005,8 +1027,8 @@ Expected<MachineInstr *> MachineIRBuilder::buildExtract(Register Destination, Re
   return Pending->build();
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildInsert(Register Destination, Register Source,
-                                                       Register Inserted,
+Expected<MachineInstr *> MachineIRBuilder::buildInsert(MachineIRBuilderResult Destination,
+                                                       Register Source, Register Inserted,
                                                        std::uint64_t Offset) const {
   if (Offset > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()))
     return makeUnexpected(ErrorCode::InvalidArgument,
@@ -1014,7 +1036,7 @@ Expected<MachineInstr *> MachineIRBuilder::buildInsert(Register Destination, Reg
   auto Pending = buildInstr(opcode(GenericOpcode::G_INSERT));
   if (!Pending)
     return std::unexpected(Pending.error());
-  if (auto Added = Pending->addDef(Destination); !Added)
+  if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added)
     return std::unexpected(Added.error());
   if (auto Added = Pending->addUse(Source); !Added)
     return std::unexpected(Added.error());