[GlobalISel] Split the generic pipeline components

24 files changed, 2003 insertions, 1633 deletions

diff --git a/backend/include/rcc/CodeGen/GlobalISel/InstructionSelect.h b/backend/include/rcc/CodeGen/GlobalISel/InstructionSelect.h
new file mode 100644
index 0000000..0c034cd
--- /dev/null
+++ b/backend/include/rcc/CodeGen/GlobalISel/InstructionSelect.h
@@ -0,0 +1,31 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_H
+#define RCC_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_H
+
+#include "rcc/CodeGen/GlobalISel/InstructionSelector.h"
+#include "rcc/CodeGen/MachinePass.h"
+
+namespace rcc {
+
+class InstructionSelect final : public MachineFunctionPass {
+public:
+  explicit InstructionSelect(const InstructionSelector *Info) : Info(Info) {}
+  explicit InstructionSelect(const InstructionSelector &Info) : Info(&Info) {}
+
+  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                MachineAnalysisManager &Analyses) override;
+
+private:
+  [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
+                                                              const TargetDescription &Target,
+                                                              MachineActionReplay &Actions);
+
+  const InstructionSelector *Info;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_H
diff --git a/backend/include/rcc/CodeGen/GlobalISel/InstructionSelector.h b/backend/include/rcc/CodeGen/GlobalISel/InstructionSelector.h
new file mode 100644
index 0000000..4c69606
--- /dev/null
+++ b/backend/include/rcc/CodeGen/GlobalISel/InstructionSelector.h
@@ -0,0 +1,35 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
+#define RCC_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
+
+#include "rcc/Support/Error.h"
+
+namespace rcc {
+
+class MachineFunction;
+class MachineInstr;
+class TargetDescription;
+
+class InstructionSelector {
+public:
+  virtual ~InstructionSelector() = default;
+
+  [[nodiscard]] virtual Expected<void> select(MachineInstr &Instruction, MachineFunction &Function,
+                                              const TargetDescription &Target) const = 0;
+
+  // Selection matching is read-only and completes before select() mutates MachineIR.
+  [[nodiscard]] virtual Expected<void> canSelect(const MachineInstr &, const MachineFunction &,
+                                                 const TargetDescription &) const {
+    return {};
+  }
+
+  [[nodiscard]] virtual Expected<void>
+  constrainSelectedInstruction(MachineInstr &, MachineFunction &, const TargetDescription &) const {
+    return {};
+  }
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
diff --git a/backend/include/rcc/CodeGen/GlobalISel/Legalizer.h b/backend/include/rcc/CodeGen/GlobalISel/Legalizer.h
new file mode 100644
index 0000000..7f86d16
--- /dev/null
+++ b/backend/include/rcc/CodeGen/GlobalISel/Legalizer.h
@@ -0,0 +1,36 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_GLOBALISEL_LEGALIZER_H
+#define RCC_CODEGEN_GLOBALISEL_LEGALIZER_H
+
+#include "rcc/CodeGen/GlobalISel/LegalizerInfo.h"
+#include "rcc/CodeGen/MachinePass.h"
+
+#include <memory>
+
+namespace rcc {
+
+class Legalizer final : public MachineFunctionPass {
+public:
+  explicit Legalizer(const LegalizerInfo *Info) : Info(Info) {}
+  explicit Legalizer(const LegalizerInfo &Info) : Info(&Info) {}
+  explicit Legalizer(std::unique_ptr<LegalizerInfo> Info)
+      : OwnedInfo(std::move(Info)), Info(OwnedInfo.get()) {}
+
+  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                MachineAnalysisManager &Analyses) override;
+
+private:
+  [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
+                                                              const TargetDescription &Target,
+                                                              MachineActionReplay &Actions);
+
+  std::unique_ptr<LegalizerInfo> OwnedInfo;
+  const LegalizerInfo *Info = nullptr;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_GLOBALISEL_LEGALIZER_H
diff --git a/backend/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h b/backend/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h
new file mode 100644
index 0000000..218a4c6
--- /dev/null
+++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h
@@ -0,0 +1,54 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
+#define RCC_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
+
+#include "rcc/Support/Error.h"
+
+#include <cstdint>
+
+namespace rcc {
+
+class MachineFunction;
+class MachineInstr;
+class TargetDescription;
+
+enum class LegalizationAction : std::uint8_t {
+  Legal,
+  Unsupported,
+  Custom,
+  Lower,
+  Libcall,
+  WidenScalar,
+  NarrowScalar,
+  MoreElements,
+  FewerElements,
+  Bitcast,
+  ChangeElementType,
+  ChangeAddressSpace,
+};
+
+class LegalizerInfo {
+public:
+  virtual ~LegalizerInfo() = default;
+
+  [[nodiscard]] virtual Expected<LegalizationAction>
+  classify(const MachineInstr &Instruction, const MachineFunction &Function,
+           const TargetDescription &Target) const = 0;
+
+  [[nodiscard]] virtual Expected<void> lower(MachineInstr &Instruction, MachineFunction &Function,
+                                             const TargetDescription &Target,
+                                             LegalizationAction Action) const = 0;
+
+  // This hook performs read-only target checks before a lowering mutation is committed.
+  [[nodiscard]] virtual Expected<void> validateLowering(const MachineInstr &,
+                                                        const MachineFunction &,
+                                                        const TargetDescription &,
+                                                        LegalizationAction) const {
+    return {};
+  }
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
diff --git a/backend/include/rcc/CodeGen/GlobalISel/RegBankSelect.h b/backend/include/rcc/CodeGen/GlobalISel/RegBankSelect.h
new file mode 100644
index 0000000..256d748
--- /dev/null
+++ b/backend/include/rcc/CodeGen/GlobalISel/RegBankSelect.h
@@ -0,0 +1,27 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_GLOBALISEL_REGBANKSELECT_H
+#define RCC_CODEGEN_GLOBALISEL_REGBANKSELECT_H
+
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/RegisterBankInfo.h"
+
+namespace rcc {
+
+class RegBankSelect final : public MachineFunctionPass {
+public:
+  explicit RegBankSelect(const RegisterBankInfo *Info) : Info(Info) {}
+  explicit RegBankSelect(const RegisterBankInfo &Info) : Info(&Info) {}
+
+  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                MachineAnalysisManager &Analyses) override;
+
+private:
+  const RegisterBankInfo *Info;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_GLOBALISEL_REGBANKSELECT_H
diff --git a/backend/include/rcc/CodeGen/MachinePipelinePasses.h b/backend/include/rcc/CodeGen/MachinePipelinePasses.h
deleted file mode 100644
index 1187e4a..0000000
--- a/backend/include/rcc/CodeGen/MachinePipelinePasses.h
+++ /dev/null
@@ -1,68 +0,0 @@
-// SPDX-License-Identifier: GPL-3.0-or-later
-
-#ifndef RCC_CODEGEN_MACHINEPIPELINEPASSES_H
-#define RCC_CODEGEN_MACHINEPIPELINEPASSES_H
-
-#include "rcc/CodeGen/MachinePass.h"
-#include "rcc/CodeGen/TargetCodeGen.h"
-
-#include <memory>
-
-namespace rcc {
-
-class LegalizerPass final : public MachineFunctionPass {
-public:
-  explicit LegalizerPass(const TargetLegalizerInfo *Info) : Info(Info) {}
-  explicit LegalizerPass(const TargetLegalizerInfo &Info) : Info(&Info) {}
-  explicit LegalizerPass(std::unique_ptr<TargetLegalizerInfo> Info)
-      : OwnedInfo(std::move(Info)), Info(OwnedInfo.get()) {}
-
-  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
-  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
-                                                const TargetDescription &Target,
-                                                MachineAnalysisManager &Analyses) override;
-
-private:
-  [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
-                                                              const TargetDescription &Target,
-                                                              MachineActionReplay &Actions);
-
-  std::unique_ptr<TargetLegalizerInfo> OwnedInfo;
-  const TargetLegalizerInfo *Info = nullptr;
-};
-
-class RegisterBankSelectPass final : public MachineFunctionPass {
-public:
-  explicit RegisterBankSelectPass(const TargetRegisterBankInfo *Info) : Info(Info) {}
-  explicit RegisterBankSelectPass(const TargetRegisterBankInfo &Info) : Info(&Info) {}
-
-  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
-  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
-                                                const TargetDescription &Target,
-                                                MachineAnalysisManager &Analyses) override;
-
-private:
-  const TargetRegisterBankInfo *Info;
-};
-
-class InstructionSelectPass final : public MachineFunctionPass {
-public:
-  explicit InstructionSelectPass(const TargetInstructionSelector *Info) : Info(Info) {}
-  explicit InstructionSelectPass(const TargetInstructionSelector &Info) : Info(&Info) {}
-
-  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
-  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
-                                                const TargetDescription &Target,
-                                                MachineAnalysisManager &Analyses) override;
-
-private:
-  [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
-                                                              const TargetDescription &Target,
-                                                              MachineActionReplay &Actions);
-
-  const TargetInstructionSelector *Info;
-};
-
-} // namespace rcc
-
-#endif // RCC_CODEGEN_MACHINEPIPELINEPASSES_H
diff --git a/backend/include/rcc/CodeGen/RegisterBankInfo.h b/backend/include/rcc/CodeGen/RegisterBankInfo.h
new file mode 100644
index 0000000..70b7340
--- /dev/null
+++ b/backend/include/rcc/CodeGen/RegisterBankInfo.h
@@ -0,0 +1,39 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_REGISTERBANKINFO_H
+#define RCC_CODEGEN_REGISTERBANKINFO_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+namespace rcc {
+
+class MachineFunction;
+class MachineInstr;
+class TargetDescription;
+struct VirtualRegisterInfo;
+
+class RegisterBankInfo {
+public:
+  virtual ~RegisterBankInfo() = default;
+
+  [[nodiscard]] virtual Expected<RegisterBankID>
+  selectBank(const MachineFunction &Function, Register Reg, const VirtualRegisterInfo &Info,
+             const MachineInstr *Context, const TargetDescription &Target) const = 0;
+
+  [[nodiscard]] virtual Expected<void>
+  constrainInstruction(MachineInstr &Instruction, MachineFunction &Function,
+                       const TargetDescription &Target) const = 0;
+
+  // This hook rejects invalid mappings before bank or register-class state is published.
+  [[nodiscard]] virtual Expected<void> validateInstruction(const MachineInstr &,
+                                                           const MachineFunction &,
+                                                           const TargetDescription &) const {
+    return {};
+  }
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_REGISTERBANKINFO_H
diff --git a/backend/include/rcc/CodeGen/TargetCodeGen.h b/backend/include/rcc/CodeGen/TargetCodeGen.h
deleted file mode 100644
index 65f65a4..0000000
--- a/backend/include/rcc/CodeGen/TargetCodeGen.h
+++ /dev/null
@@ -1,95 +0,0 @@
-// SPDX-License-Identifier: GPL-3.0-or-later
-
-#ifndef RCC_CODEGEN_TARGETCODEGEN_H
-#define RCC_CODEGEN_TARGETCODEGEN_H
-
-#include "rcc/Support/Error.h"
-
-#include <cstdint>
-
-namespace rcc {
-
-class MachineFunction;
-class MachineInstr;
-class TargetDescription;
-struct VirtualRegisterInfo;
-
-enum class LegalizationAction : std::uint8_t {
-  Legal,
-  Unsupported,
-  Custom,
-  Lower,
-  Libcall,
-  WidenScalar,
-  NarrowScalar,
-  MoreElements,
-  FewerElements,
-  Bitcast,
-  ChangeElementType,
-  ChangeAddressSpace,
-};
-
-class TargetLegalizerInfo {
-public:
-  virtual ~TargetLegalizerInfo() = default;
-
-  [[nodiscard]] virtual Expected<LegalizationAction>
-  classify(const MachineInstr &Instruction, const MachineFunction &Function,
-           const TargetDescription &Target) const = 0;
-
-  [[nodiscard]] virtual Expected<void> lower(MachineInstr &Instruction, MachineFunction &Function,
-                                             const TargetDescription &Target,
-                                             LegalizationAction Action) const = 0;
-
-  // This hook performs read-only target checks before a lowering mutation is committed.
-  [[nodiscard]] virtual Expected<void> validateLowering(const MachineInstr &,
-                                                        const MachineFunction &,
-                                                        const TargetDescription &,
-                                                        LegalizationAction) const {
-    return {};
-  }
-};
-
-class TargetRegisterBankInfo {
-public:
-  virtual ~TargetRegisterBankInfo() = default;
-
-  [[nodiscard]] virtual Expected<RegisterBankID>
-  selectBank(const MachineFunction &Function, Register Reg, const VirtualRegisterInfo &Info,
-             const MachineInstr *Context, const TargetDescription &Target) const = 0;
-
-  [[nodiscard]] virtual Expected<void>
-  constrainInstruction(MachineInstr &Instruction, MachineFunction &Function,
-                       const TargetDescription &Target) const = 0;
-
-  // This hook must not mutate MachineIR. It allows the pass to reject a bad mapping
-  // before publishing any bank or class assignment.
-  [[nodiscard]] virtual Expected<void> validateInstruction(const MachineInstr &,
-                                                           const MachineFunction &,
-                                                           const TargetDescription &) const {
-    return {};
-  }
-};
-
-class TargetInstructionSelector {
-public:
-  virtual ~TargetInstructionSelector() = default;
-
-  [[nodiscard]] virtual Expected<void> select(MachineInstr &Instruction, MachineFunction &Function,
-                                              const TargetDescription &Target) const = 0;
-
-  // Selection matching is read-only and must complete before select() mutates MachineIR.
-  [[nodiscard]] virtual Expected<void> canSelect(const MachineInstr &, const MachineFunction &,
-                                                 const TargetDescription &) const {
-    return {};
-  }
-
-  [[nodiscard]] virtual Expected<void>
-  constrainSelectedInstruction(MachineInstr &, MachineFunction &, const TargetDescription &) const {
-    return {};
-  }
-};
-
-} // namespace rcc
-
-#endif // RCC_CODEGEN_TARGETCODEGEN_H
diff --git a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
index 6cda815..37f1c97 100644
--- a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
+++ b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
@@ -3,9 +3,11 @@
 #ifndef RCC_TARGET_RISCV_RISCVCODEGEN_H
 #define RCC_TARGET_RISCV_RISCVCODEGEN_H
 
+#include "rcc/CodeGen/GlobalISel/InstructionSelector.h"
+#include "rcc/CodeGen/GlobalISel/LegalizerInfo.h"
 #include "rcc/CodeGen/MachineCombinerPattern.h"
 #include "rcc/CodeGen/MachineOptimizationPipeline.h"
-#include "rcc/CodeGen/TargetCodeGen.h"
+#include "rcc/CodeGen/RegisterBankInfo.h"
 #include "rcc/CodeGen/TargetFrameLowering.h"
 #include "rcc/CodeGen/TargetMemoryFolding.h"
 #include "rcc/CodeGen/TargetPseudoExpansion.h"
@@ -17,11 +19,10 @@
 
 namespace rcc::riscv {
 
-[[nodiscard]] const TargetLegalizerInfo &legalizerInfo() noexcept;
-[[nodiscard]] std::unique_ptr<TargetLegalizerInfo>
-createLegalizerInfo(RISCVSubtargetFeatures Features);
-[[nodiscard]] const TargetRegisterBankInfo &registerBankInfo() noexcept;
-[[nodiscard]] const TargetInstructionSelector &instructionSelector() noexcept;
+[[nodiscard]] const LegalizerInfo &legalizerInfo() noexcept;
+[[nodiscard]] std::unique_ptr<LegalizerInfo> createLegalizerInfo(RISCVSubtargetFeatures Features);
+[[nodiscard]] const RegisterBankInfo &registerBankInfo() noexcept;
+[[nodiscard]] const InstructionSelector &instructionSelector() noexcept;
 [[nodiscard]] const TargetRegisterAllocationInfo &registerAllocationInfo() noexcept;
 [[nodiscard]] const TargetFrameLowering &frameLowering() noexcept;
 [[nodiscard]] const TargetSchedulingModel &schedulingModel() noexcept;
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index 3a1f34c..996f771 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -45,7 +45,6 @@ set(
   MachineOptimizationPipeline.cpp
   MachinePass.cpp
   MachinePseudoExpansion.cpp
-  MachinePipelinePasses.cpp
   MachineRegisterInfo.cpp
   MachineScheduler.cpp
   MachineShrinkWrapping.cpp
@@ -129,13 +128,11 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineOptimizationPipeline.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePass.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePseudoExpansion.h"
-  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePipelinePasses.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PrologueEpilogueInsertion.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterPressure.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterScavenger.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/ScheduleDAG.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/ScheduleHazardRecognizer.h"
-  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetCodeGen.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetFrameLowering.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineScheduler.h"
@@ -163,6 +160,7 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionProperties.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionRecords.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/Register.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterBankInfo.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterMask.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/StableID.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetConstant.h"
@@ -180,6 +178,8 @@ set(
 add_library(RCCBackendCodeGen ${RCCBackendCodeGenSources})
 add_library(RCCBackend::CodeGen ALIAS RCCBackendCodeGen)
 
+add_subdirectory(GlobalISel)
+
 rcc_backend_configure_target(RCCBackendCodeGen)
 
 target_include_directories(
@@ -248,7 +248,6 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOptimizationPipeline.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePseudoExpansion.cpp"
-  "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePasses.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineScheduler.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineSchedulerInternal.h"
@@ -331,7 +330,6 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOptimizationPipeline.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePseudoExpansion.cpp"
-  "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePasses.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineScheduler.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineShrinkWrapping.cpp"
diff --git a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
new file mode 100644
index 0000000..8a37497
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
@@ -0,0 +1,32 @@
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+set(
+  RCCBackendGlobalISelSources
+  InstructionSelect.cpp
+  Legalizer.cpp
+  RegBankSelect.cpp
+)
+
+set(
+  RCCBackendGlobalISelHeaders
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/InstructionSelect.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/InstructionSelector.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/Legalizer.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/RegBankSelect.h"
+)
+
+target_sources(RCCBackendCodeGen PRIVATE ${RCCBackendGlobalISelSources})
+
+rcc_backend_register_format_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/Legalizer.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelect.cpp"
+  ${RCCBackendGlobalISelHeaders}
+)
+
+rcc_backend_register_tidy_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/Legalizer.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelect.cpp"
+)
diff --git a/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp b/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp
new file mode 100644
index 0000000..8937fd8
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp
@@ -0,0 +1,351 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/InstructionSelect.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineFunctionCloner.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <optional>
+#include <string>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] const MachinePassContract &instructionSelectContract() {
+  static const MachinePassContract Contract{
+      .Name = "instruction-select",
+      .Requires = {MachineFunctionProperty::Legalized, MachineFunctionProperty::RegBankSelected},
+      .Sets = {MachineFunctionProperty::Selected},
+      .Clears = {},
+      .RequiredAnalyses = {},
+      .VerificationStage = PipelineStage::Selected,
+  };
+  return Contract;
+}
+
+struct OpcodeState final {
+  MachineInstrStableID Instruction;
+  Opcode OpcodeValue;
+  std::uint64_t OperandFingerprint = 0;
+
+  friend bool operator==(const OpcodeState &Left, const OpcodeState &Right) noexcept = default;
+};
+
+struct OpcodeStateHash final {
+  [[nodiscard]] std::size_t operator()(const OpcodeState &State) const noexcept {
+    return std::hash<std::uint64_t>{}(State.Instruction.value()) ^
+           (std::hash<std::uint32_t>{}(State.OpcodeValue.value()) << 1U) ^
+           (std::hash<std::uint64_t>{}(State.OperandFingerprint) << 2U);
+  }
+};
+
+void combineFingerprint(std::uint64_t &State, std::uint64_t Value) noexcept {
+  State ^= Value + 0x9e3779b97f4a7c15ULL + (State << 6U) + (State >> 2U);
+}
+
+[[nodiscard]] std::uint64_t operandFingerprint(const MachineInstr &Instruction) noexcept {
+  std::uint64_t Result = 0xcbf29ce484222325ULL;
+  combineFingerprint(Result, Instruction.flags().rawValue());
+  combineFingerprint(Result, Instruction.operandCount());
+  for (const MachineOperand &Operand : Instruction.operands()) {
+    combineFingerprint(Result, static_cast<std::uint64_t>(Operand.kind()));
+    combineFingerprint(Result, Operand.targetFlags());
+    combineFingerprint(Result, Operand.registerFlags().rawValue());
+    combineFingerprint(Result, Operand.subReg().value());
+    if (const Register *Reg = Operand.getIf<Register>())
+      combineFingerprint(Result, Reg->opaqueValue());
+    else if (const std::int64_t *Immediate = Operand.getIf<std::int64_t>())
+      combineFingerprint(Result, static_cast<std::uint64_t>(*Immediate));
+    else if (const auto *Integer = Operand.getIf<IntegerImmediateOperand>())
+      combineFingerprint(Result, Integer->Value.bitWidth());
+    else if (const auto *Floating = Operand.getIf<FloatingImmediateOperand>())
+      combineFingerprint(Result, static_cast<std::uint64_t>(Floating->Bits.semantics()));
+    else if (const auto *Block = Operand.getIf<BasicBlockOperand>())
+      combineFingerprint(Result, Block->Block == nullptr ? 0 : Block->Block->stableID().value());
+  }
+  return Result;
+}
+
+[[nodiscard]] OpcodeState stateOf(const MachineInstr &Instruction) noexcept {
+  return {Instruction.stableID(), Instruction.opcode(), operandFingerprint(Instruction)};
+}
+
+[[nodiscard]] std::vector<MachineInstr *> layoutInstructions(MachineFunction &Function) {
+  std::vector<MachineInstr *> Result;
+  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next())
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next())
+      Result.push_back(Instruction);
+  return Result;
+}
+
+[[nodiscard]] std::vector<MachineBasicBlock *> stableCFGPostOrder(MachineFunction &Function) {
+  std::vector<MachineBasicBlock *> Roots;
+  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next())
+    Roots.push_back(Block);
+  std::ranges::sort(Roots, {},
+                    [](const MachineBasicBlock *Block) { return Block->stableID().value(); });
+  if (MachineBasicBlock *Entry = Function.firstBlock(); Entry != nullptr) {
+    const auto Position = std::ranges::find(Roots, Entry);
+    if (Position != Roots.end())
+      std::rotate(Roots.begin(), Position, std::next(Position));
+  }
+
+  struct TraversalFrame final {
+    MachineBasicBlock *Block = nullptr;
+    std::vector<MachineBasicBlock *> Successors;
+    std::size_t NextSuccessor = 0;
+  };
+  const auto MakeFrame = [](MachineBasicBlock &Block) {
+    TraversalFrame Frame;
+    Frame.Block = &Block;
+    for (const MachineSuccessor &Successor : Block.successors()) {
+      if (Successor.Block != nullptr)
+        Frame.Successors.push_back(Successor.Block);
+    }
+    std::ranges::sort(Frame.Successors, {}, [](const MachineBasicBlock *Successor) {
+      return Successor->stableID().value();
+    });
+    return Frame;
+  };
+
+  std::vector<MachineBasicBlock *> Result;
+  std::unordered_set<MachineBasicBlock *> Visited;
+  std::vector<TraversalFrame> Stack;
+  for (MachineBasicBlock *Root : Roots) {
+    if (!Visited.insert(Root).second)
+      continue;
+    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));
+        continue;
+      }
+      Result.push_back(Frame.Block);
+      Stack.pop_back();
+    }
+  }
+  return Result;
+}
+
+[[nodiscard]] std::vector<MachineInstr *> bottomUpInstructions(MachineFunction &Function) {
+  std::vector<MachineInstr *> Result;
+  for (MachineBasicBlock *Block : stableCFGPostOrder(Function)) {
+    for (MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr;
+         Instruction = Instruction->previous())
+      Result.push_back(Instruction);
+  }
+  return Result;
+}
+
+[[nodiscard]] Expected<void> requireProperties(const MachineFunction &Function,
+                                               const MachinePassContract &Contract) {
+  const MachineFunctionProperties Missing = Contract.Requires.missingFrom(Function.properties());
+  if (!Missing.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "pass '" + Contract.Name +
+                              "' requires properties: " + Missing.toString());
+  }
+  return {};
+}
+
+[[nodiscard]] Error passFailure(std::string Message,
+                                ErrorCode Code = ErrorCode::VerificationError) {
+  return Error(Code, std::move(Message));
+}
+
+[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) {
+  Prefix.append(Source.message());
+  return Error(Source.code(), std::move(Prefix));
+}
+
+[[nodiscard]] Expected<void> repairTrackedLiveness(MachineFunction &Function,
+                                                   const TargetDescription &Target,
+                                                   MachinePassResult &Result) {
+  if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
+    return {};
+  }
+  auto Rebuilt = rebuildMachineLiveness(Function, Target);
+  if (!Rebuilt)
+    return std::unexpected(Rebuilt.error());
+  if (*Rebuilt)
+    Result.Changes.add(MachinePassChange::Operands);
+  return {};
+}
+
+} // namespace
+
+const MachinePassContract &InstructionSelect::contract() const noexcept {
+  return instructionSelectContract();
+}
+
+Expected<MachinePassResult> InstructionSelect::run(MachineFunction &Function,
+                                                   const TargetDescription &Target,
+                                                   MachineAnalysisManager &Analyses) {
+  if (Info == nullptr)
+    return std::unexpected(passFailure("instruction select has no target behavior interface",
+                                       ErrorCode::InvalidArgument));
+  auto Required = requireProperties(Function, contract());
+  if (!Required)
+    return std::unexpected(Required.error());
+
+  auto Trial = cloneMachineFunction(
+      Function, Target,
+      MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
+  if (!Trial) {
+    return std::unexpected(
+        prefixedError(Trial.error(), "instruction-selection transaction setup failed: "));
+  }
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
+  if (!TrialResult)
+    return std::unexpected(TrialResult.error());
+  Actions.beginReplay();
+  auto Result = runImplementation(Function, Target, Actions);
+  if (!Result) {
+    return std::unexpected(
+        prefixedError(Result.error(),
+                      "instruction selection diverged after a successful transaction preflight: "));
+  }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
+  return Result;
+}
+
+Expected<MachinePassResult> InstructionSelect::runImplementation(MachineFunction &Function,
+                                                                 const TargetDescription &Target,
+                                                                 MachineActionReplay &Actions) {
+
+  MachinePassResult Result;
+  std::vector<MachineInstr *> Worklist;
+  std::unordered_set<MachineInstrStableID> DiscoveredInstructions;
+  std::unordered_set<OpcodeState, OpcodeStateHash> SeenStates;
+  for (MachineInstr *Instruction : bottomUpInstructions(Function)) {
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+    if (Descriptor == nullptr)
+      return std::unexpected(
+          passFailure("instruction selector encountered an unknown instruction descriptor"));
+    auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo());
+    if (!Validation)
+      return std::unexpected(
+          prefixedError(Validation.error(), "instruction selector input is invalid: "));
+    if (!Descriptor->Flags.has(InstructionFlag::Generic))
+      continue;
+    auto Match = Info->canSelect(*Instruction, Function, Target);
+    if (!Match)
+      return std::unexpected(Match.error());
+    Worklist.push_back(Instruction);
+    DiscoveredInstructions.insert(Instruction->stableID());
+  }
+
+  for (std::size_t Index = 0; Index < Worklist.size(); ++Index) {
+    MachineInstr *Instruction = Worklist[Index];
+    if (Instruction->parent() == nullptr)
+      return std::unexpected(passFailure("instruction selector lost its input instruction"));
+    const InstructionDescriptor *CurrentDescriptor =
+        Target.instructionDescriptor(Instruction->opcode());
+    if (CurrentDescriptor == nullptr)
+      return std::unexpected(
+          passFailure("instruction selector encountered an unknown instruction descriptor"));
+    if (!CurrentDescriptor->Flags.has(InstructionFlag::Generic))
+      continue;
+    const OpcodeState Before = stateOf(*Instruction);
+    if (!SeenStates.insert(Before).second) {
+      return std::unexpected(passFailure("instruction selector entered a repeated state for '" +
+                                             CurrentDescriptor->Name + "'",
+                                         ErrorCode::InternalError));
+    }
+    auto Match = Info->canSelect(*Instruction, Function, Target);
+    if (!Match)
+      return std::unexpected(Match.error());
+    std::string Rule = "select.";
+    Rule.append(CurrentDescriptor->Name);
+    auto Accepted = Actions.request(Rule, Function, Instruction->stableID());
+    if (!Accepted)
+      return std::unexpected(Accepted.error());
+    if (!*Accepted) {
+      return std::unexpected(passFailure("required selection action was rejected for '" +
+                                             CurrentDescriptor->Name + "'",
+                                         ErrorCode::VerificationError));
+    }
+    auto Selection = Info->select(*Instruction, Function, Target);
+    if (!Selection)
+      return std::unexpected(Selection.error());
+    const InstructionDescriptor *Selected = Target.instructionDescriptor(Instruction->opcode());
+    if (Selected == nullptr)
+      return std::unexpected(
+          passFailure("instruction selector produced an unknown instruction descriptor"));
+    auto Constraint = Info->constrainSelectedInstruction(*Instruction, Function, Target);
+    if (!Constraint) {
+      return std::unexpected(prefixedError(
+          Constraint.error(), "instruction selector could not constrain selected registers: "));
+    }
+    auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo());
+    if (!Validation)
+      return std::unexpected(
+          prefixedError(Validation.error(), "instruction selector produced invalid MachineIR: "));
+    const OpcodeState After = stateOf(*Instruction);
+    if (After == Before)
+      return std::unexpected(
+          passFailure("instruction selector reported success without observable progress",
+                      ErrorCode::InternalError));
+    Result.Changed = true;
+    Result.Changes.add(MachinePassChange::Instructions);
+    if (Selected->Flags.has(InstructionFlag::Generic))
+      Worklist.push_back(Instruction);
+    for (MachineInstr *Candidate : bottomUpInstructions(Function)) {
+      const InstructionDescriptor *CandidateDescriptor =
+          Target.instructionDescriptor(Candidate->opcode());
+      if (CandidateDescriptor == nullptr)
+        return std::unexpected(
+            passFailure("instruction selector produced an unknown instruction descriptor"));
+      if (!CandidateDescriptor->Flags.has(InstructionFlag::Generic) ||
+          !DiscoveredInstructions.insert(Candidate->stableID()).second) {
+        continue;
+      }
+      auto CandidateMatch = Info->canSelect(*Candidate, Function, Target);
+      if (!CandidateMatch)
+        return std::unexpected(CandidateMatch.error());
+      Worklist.push_back(Candidate);
+    }
+  }
+  for (MachineInstr *Instruction : layoutInstructions(Function)) {
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+    if (Descriptor == nullptr)
+      return std::unexpected(
+          passFailure("instruction selector produced an unknown instruction descriptor"));
+    auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo());
+    if (!Validation)
+      return std::unexpected(
+          prefixedError(Validation.error(), "instruction selector produced invalid MachineIR: "));
+    if (Descriptor->Flags.has(InstructionFlag::Generic))
+      return std::unexpected(
+          passFailure("instruction selector left a generic opcode in the function"));
+  }
+  auto RegisterValidation = Target.validateRegisterInfo(Function.registerInfo());
+  if (!RegisterValidation)
+    return std::unexpected(prefixedError(RegisterValidation.error(),
+                                         "instruction selection produced invalid registers: "));
+  auto Liveness = repairTrackedLiveness(Function, Target, Result);
+  if (!Liveness) {
+    return std::unexpected(
+        prefixedError(Liveness.error(), "instruction-selection liveness repair failed: "));
+  }
+  Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
+  return Result;
+}
+} // namespace rcc
diff --git a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
new file mode 100644
index 0000000..e61a801
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
@@ -0,0 +1,324 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/Legalizer.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineFunctionCloner.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <cstdint>
+#include <optional>
+#include <string>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] const MachinePassContract &legalizerContract() {
+  static const MachinePassContract Contract{
+      .Name = "legalizer",
+      // LLVM's GlobalISel legalizer operates on SSA form and does not require
+      // the optional register-liveness tracking property.
+      .Requires = {MachineFunctionProperty::IsSSA},
+      .Sets = {MachineFunctionProperty::Legalized},
+      .Clears = {},
+      .RequiredAnalyses = {},
+      .VerificationStage = PipelineStage::Legalized,
+  };
+  return Contract;
+}
+
+struct OpcodeState final {
+  MachineInstrStableID Instruction;
+  Opcode OpcodeValue;
+  std::uint64_t OperandFingerprint = 0;
+
+  friend bool operator==(const OpcodeState &Left, const OpcodeState &Right) noexcept = default;
+};
+
+struct OpcodeStateHash final {
+  [[nodiscard]] std::size_t operator()(const OpcodeState &State) const noexcept {
+    return std::hash<std::uint64_t>{}(State.Instruction.value()) ^
+           (std::hash<std::uint32_t>{}(State.OpcodeValue.value()) << 1U) ^
+           (std::hash<std::uint64_t>{}(State.OperandFingerprint) << 2U);
+  }
+};
+
+void combineFingerprint(std::uint64_t &State, std::uint64_t Value) noexcept {
+  State ^= Value + 0x9e3779b97f4a7c15ULL + (State << 6U) + (State >> 2U);
+}
+
+[[nodiscard]] std::uint64_t operandFingerprint(const MachineInstr &Instruction) noexcept {
+  std::uint64_t Result = 0xcbf29ce484222325ULL;
+  combineFingerprint(Result, Instruction.flags().rawValue());
+  combineFingerprint(Result, Instruction.operandCount());
+  for (const MachineOperand &Operand : Instruction.operands()) {
+    combineFingerprint(Result, static_cast<std::uint64_t>(Operand.kind()));
+    combineFingerprint(Result, Operand.targetFlags());
+    combineFingerprint(Result, Operand.registerFlags().rawValue());
+    combineFingerprint(Result, Operand.subReg().value());
+    if (const Register *Reg = Operand.getIf<Register>())
+      combineFingerprint(Result, Reg->opaqueValue());
+    else if (const std::int64_t *Immediate = Operand.getIf<std::int64_t>())
+      combineFingerprint(Result, static_cast<std::uint64_t>(*Immediate));
+    else if (const auto *Integer = Operand.getIf<IntegerImmediateOperand>())
+      combineFingerprint(Result, Integer->Value.bitWidth());
+    else if (const auto *Floating = Operand.getIf<FloatingImmediateOperand>())
+      combineFingerprint(Result, static_cast<std::uint64_t>(Floating->Bits.semantics()));
+    else if (const auto *Block = Operand.getIf<BasicBlockOperand>())
+      combineFingerprint(Result, Block->Block == nullptr ? 0 : Block->Block->stableID().value());
+  }
+  return Result;
+}
+
+[[nodiscard]] OpcodeState stateOf(const MachineInstr &Instruction) noexcept {
+  return {Instruction.stableID(), Instruction.opcode(), operandFingerprint(Instruction)};
+}
+
+[[nodiscard]] std::vector<MachineInstr *> layoutInstructions(MachineFunction &Function) {
+  std::vector<MachineInstr *> Result;
+  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next())
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next())
+      Result.push_back(Instruction);
+  return Result;
+}
+
+[[nodiscard]] Expected<void> requireProperties(const MachineFunction &Function,
+                                               const MachinePassContract &Contract) {
+  const MachineFunctionProperties Missing = Contract.Requires.missingFrom(Function.properties());
+  if (!Missing.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "pass '" + Contract.Name +
+                              "' requires properties: " + Missing.toString());
+  }
+  return {};
+}
+
+[[nodiscard]] Error passFailure(std::string Message,
+                                ErrorCode Code = ErrorCode::VerificationError) {
+  return Error(Code, std::move(Message));
+}
+
+[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) {
+  Prefix.append(Source.message());
+  return Error(Source.code(), std::move(Prefix));
+}
+
+[[nodiscard]] std::string_view legalizationActionName(LegalizationAction Action) noexcept {
+  switch (Action) {
+  case LegalizationAction::Legal:
+    return "legal";
+  case LegalizationAction::Unsupported:
+    return "unsupported";
+  case LegalizationAction::Custom:
+    return "custom";
+  case LegalizationAction::Lower:
+    return "lower";
+  case LegalizationAction::Libcall:
+    return "libcall";
+  case LegalizationAction::WidenScalar:
+    return "widen-scalar";
+  case LegalizationAction::NarrowScalar:
+    return "narrow-scalar";
+  case LegalizationAction::MoreElements:
+    return "more-elements";
+  case LegalizationAction::FewerElements:
+    return "fewer-elements";
+  case LegalizationAction::Bitcast:
+    return "bitcast";
+  case LegalizationAction::ChangeElementType:
+    return "change-element-type";
+  case LegalizationAction::ChangeAddressSpace:
+    return "change-address-space";
+  }
+  return "unknown";
+}
+
+[[nodiscard]] Expected<void> clearTrackedLivenessFlags(MachineFunction &Function,
+                                                       MachinePassResult &Result) {
+  if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness))
+    return {};
+  bool Changed = false;
+  for (MachineInstr *Instruction : layoutInstructions(Function)) {
+    for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+      MachineOperand &Operand = *Instruction->operandAt(Index);
+      if (!Operand.isRegister())
+        continue;
+      RegisterOperandFlags Flags = Operand.registerFlags();
+      if (!Flags.has(RegisterOperandFlag::Kill) && !Flags.has(RegisterOperandFlag::Dead))
+        continue;
+      Flags.clear(RegisterOperandFlag::Kill);
+      Flags.clear(RegisterOperandFlag::Dead);
+      auto Updated = Operand.setRegisterFlags(Flags);
+      if (!Updated)
+        return std::unexpected(Updated.error());
+      Changed = true;
+    }
+  }
+  if (Changed)
+    Result.Changes.add(MachinePassChange::Operands);
+  return {};
+}
+
+} // namespace
+
+const MachinePassContract &Legalizer::contract() const noexcept {
+  return legalizerContract();
+}
+
+Expected<MachinePassResult> Legalizer::run(MachineFunction &Function,
+                                           const TargetDescription &Target,
+                                           MachineAnalysisManager &Analyses) {
+  if (Info == nullptr)
+    return std::unexpected(
+        passFailure("legalizer has no target behavior interface", ErrorCode::InvalidArgument));
+  auto Required = requireProperties(Function, contract());
+  if (!Required)
+    return std::unexpected(Required.error());
+
+  auto Trial = cloneMachineFunction(
+      Function, Target,
+      MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
+  if (!Trial)
+    return std::unexpected(prefixedError(Trial.error(), "legalizer transaction setup failed: "));
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
+  if (!TrialResult)
+    return std::unexpected(TrialResult.error());
+  Actions.beginReplay();
+  auto Result = runImplementation(Function, Target, Actions);
+  if (!Result) {
+    return std::unexpected(prefixedError(
+        Result.error(), "legalizer diverged after a successful transaction preflight: "));
+  }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
+  return Result;
+}
+
+Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Function,
+                                                         const TargetDescription &Target,
+                                                         MachineActionReplay &Actions) {
+
+  MachinePassResult Result;
+  std::unordered_set<OpcodeState, OpcodeStateHash> SeenStates;
+
+  std::vector<MachineInstr *> Worklist = layoutInstructions(Function);
+  std::unordered_set<MachineInstrStableID> PendingInstructions;
+  for (const MachineInstr *Instruction : Worklist)
+    PendingInstructions.insert(Instruction->stableID());
+  for (std::size_t Index = 0; Index < Worklist.size(); ++Index) {
+    MachineInstr *Instruction = Worklist[Index];
+    if (Instruction != nullptr)
+      PendingInstructions.erase(Instruction->stableID());
+    if (Instruction == nullptr || Instruction->parent() == nullptr)
+      continue;
+
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+    if (Descriptor == nullptr)
+      return std::unexpected(
+          passFailure("legalizer encountered an unknown instruction descriptor"));
+    if (!Descriptor->Flags.has(InstructionFlag::Generic))
+      continue;
+
+    auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo());
+    if (!Validation)
+      return std::unexpected(prefixedError(Validation.error(), "legalizer input is invalid: "));
+
+    auto Action = Info->classify(*Instruction, Function, Target);
+    if (!Action)
+      return std::unexpected(Action.error());
+    if (*Action == LegalizationAction::Legal)
+      continue;
+    if (*Action == LegalizationAction::Unsupported) {
+      return std::unexpected(
+          passFailure("target legalizer rejected generic instruction '" + Descriptor->Name + "'",
+                      ErrorCode::Unsupported));
+    }
+
+    const OpcodeState Before = stateOf(*Instruction);
+    if (!SeenStates.insert(Before).second)
+      return std::unexpected(
+          passFailure("target legalizer entered a repeated state for '" + Descriptor->Name + "'",
+                      ErrorCode::InternalError));
+
+    auto LoweringValidation = Info->validateLowering(*Instruction, Function, Target, *Action);
+    if (!LoweringValidation)
+      return std::unexpected(
+          prefixedError(LoweringValidation.error(), "legalizer lowering precondition failed: "));
+    std::string Rule = "legalize.";
+    Rule.append(legalizationActionName(*Action));
+    Rule.push_back('.');
+    Rule.append(Descriptor->Name);
+    auto Accepted = Actions.request(Rule, Function, Instruction->stableID());
+    if (!Accepted)
+      return std::unexpected(Accepted.error());
+    if (!*Accepted) {
+      return std::unexpected(
+          passFailure("required legalizer action was rejected for '" + Descriptor->Name + "'",
+                      ErrorCode::VerificationError));
+    }
+    auto Lowered = Info->lower(*Instruction, Function, Target, *Action);
+    if (!Lowered)
+      return std::unexpected(Lowered.error());
+    const bool InstructionWasErased = Instruction->parent() == nullptr;
+    if (!InstructionWasErased) {
+      const OpcodeState After = stateOf(*Instruction);
+      if (After == Before)
+        return std::unexpected(passFailure("target legalizer made no observable progress for '" +
+                                               Descriptor->Name + "'",
+                                           ErrorCode::InternalError));
+    }
+    Result.Changed = true;
+    Result.Changes.add(MachinePassChange::Instructions);
+
+    const std::vector<MachineInstr *> Current = layoutInstructions(Function);
+    for (MachineInstr *Candidate : Current) {
+      const InstructionDescriptor *CandidateDescriptor =
+          Target.instructionDescriptor(Candidate->opcode());
+      if (CandidateDescriptor == nullptr)
+        return std::unexpected(passFailure("legalizer produced an unknown instruction descriptor"));
+      if (CandidateDescriptor->Flags.has(InstructionFlag::Generic) &&
+          PendingInstructions.insert(Candidate->stableID()).second) {
+        Worklist.push_back(Candidate);
+      }
+    }
+  }
+
+  for (MachineInstr *Instruction : layoutInstructions(Function)) {
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+    if (Descriptor == nullptr)
+      return std::unexpected(passFailure("legalizer produced an unknown instruction descriptor"));
+    if (!Descriptor->Flags.has(InstructionFlag::Generic))
+      continue;
+    auto Action = Info->classify(*Instruction, Function, Target);
+    if (!Action)
+      return std::unexpected(Action.error());
+    if (*Action != LegalizationAction::Legal)
+      return std::unexpected(
+          passFailure("legalizer reached a fixed point with an illegal generic instruction '" +
+                          Descriptor->Name + "'",
+                      *Action == LegalizationAction::Unsupported ? ErrorCode::Unsupported
+                                                                 : ErrorCode::InternalError));
+    auto FinalValidation = Target.validateInstruction(*Instruction, Function.registerInfo());
+    if (!FinalValidation)
+      return std::unexpected(
+          prefixedError(FinalValidation.error(), "legalizer produced invalid MachineIR: "));
+  }
+  auto Liveness = clearTrackedLivenessFlags(Function, Result);
+  if (!Liveness)
+    return std::unexpected(
+        prefixedError(Liveness.error(), "legalizer liveness-flag invalidation failed: "));
+  Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
+  return Result;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/GlobalISel/RegBankSelect.cpp b/backend/lib/CodeGen/GlobalISel/RegBankSelect.cpp
new file mode 100644
index 0000000..337db80
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/RegBankSelect.cpp
@@ -0,0 +1,238 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/RegBankSelect.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <cstdint>
+#include <optional>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] const MachinePassContract &bankSelectContract() {
+  static const MachinePassContract Contract{
+      .Name = "regbankselect",
+      .Requires = {MachineFunctionProperty::Legalized},
+      .Sets = {MachineFunctionProperty::RegBankSelected},
+      .Clears = {},
+      .RequiredAnalyses = {},
+      .VerificationStage = PipelineStage::RegBankSelected,
+  };
+  return Contract;
+}
+
+void combineFingerprint(std::uint64_t &State, std::uint64_t Value) noexcept {
+  State ^= Value + 0x9e3779b97f4a7c15ULL + (State << 6U) + (State >> 2U);
+}
+
+[[nodiscard]] std::uint64_t
+registerConfigurationFingerprint(const MachineRegisterInfo &RegInfo) noexcept {
+  std::uint64_t Result = 0xcbf29ce484222325ULL;
+  for (const VirtualRegisterInfo &Info : RegInfo.virtualRegisters()) {
+    combineFingerprint(Result, Info.IsTombstone ? 1U : 0U);
+    combineFingerprint(Result, Info.Bank ? Info.Bank->value() : 0U);
+    combineFingerprint(Result, Info.RegClass ? Info.RegClass->value() : 0U);
+  }
+  return Result;
+}
+
+[[nodiscard]] std::vector<MachineInstr *> layoutInstructions(MachineFunction &Function) {
+  std::vector<MachineInstr *> Result;
+  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next())
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next())
+      Result.push_back(Instruction);
+  return Result;
+}
+
+[[nodiscard]] Expected<void> requireProperties(const MachineFunction &Function,
+                                               const MachinePassContract &Contract) {
+  const MachineFunctionProperties Missing = Contract.Requires.missingFrom(Function.properties());
+  if (!Missing.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "pass '" + Contract.Name +
+                              "' requires properties: " + Missing.toString());
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<void> restoreRegisterConfiguration(
+    MachineRegisterInfo &RegInfo,
+    const std::vector<std::pair<Register, std::pair<std::optional<RegisterBankID>,
+                                                    std::optional<RegisterClassID>>>> &Snapshot) {
+  for (const auto &[Reg, Configuration] : Snapshot) {
+    auto ClearBank = RegInfo.clearRegisterBank(Reg);
+    if (!ClearBank)
+      return std::unexpected(ClearBank.error());
+    if (Configuration.first) {
+      auto SetBank = RegInfo.setRegisterBank(Reg, *Configuration.first);
+      if (!SetBank)
+        return std::unexpected(SetBank.error());
+    }
+    auto ClearClass = RegInfo.clearRegisterClass(Reg);
+    if (!ClearClass)
+      return std::unexpected(ClearClass.error());
+    if (Configuration.second) {
+      auto SetClass = RegInfo.setRegisterClass(Reg, *Configuration.second);
+      if (!SetClass)
+        return std::unexpected(SetClass.error());
+    }
+  }
+  return {};
+}
+
+[[nodiscard]] Error passFailure(std::string Message,
+                                ErrorCode Code = ErrorCode::VerificationError) {
+  return Error(Code, std::move(Message));
+}
+
+[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) {
+  Prefix.append(Source.message());
+  return Error(Source.code(), std::move(Prefix));
+}
+
+[[nodiscard]] Expected<void> repairTrackedLiveness(MachineFunction &Function,
+                                                   const TargetDescription &Target,
+                                                   MachinePassResult &Result) {
+  if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
+    return {};
+  }
+  auto Rebuilt = rebuildMachineLiveness(Function, Target);
+  if (!Rebuilt)
+    return std::unexpected(Rebuilt.error());
+  if (*Rebuilt)
+    Result.Changes.add(MachinePassChange::Operands);
+  return {};
+}
+
+} // namespace
+
+const MachinePassContract &RegBankSelect::contract() const noexcept {
+  return bankSelectContract();
+}
+
+Expected<MachinePassResult> RegBankSelect::run(MachineFunction &Function,
+                                               const TargetDescription &Target,
+                                               MachineAnalysisManager &) {
+  if (Info == nullptr)
+    return std::unexpected(passFailure("register-bank select has no target behavior interface",
+                                       ErrorCode::InvalidArgument));
+  auto Required = requireProperties(Function, contract());
+  if (!Required)
+    return std::unexpected(Required.error());
+
+  MachinePassResult Result;
+  MachineRegisterInfo &RegInfo = Function.registerInfo();
+  const std::uint64_t RegisterConfigurationBefore = registerConfigurationFingerprint(RegInfo);
+  using RegisterConfiguration =
+      std::pair<std::optional<RegisterBankID>, std::optional<RegisterClassID>>;
+  std::vector<std::pair<Register, RegisterConfiguration>> Snapshot;
+  std::vector<std::pair<Register, RegisterBankID>> PlannedBanks;
+  for (std::size_t Index = 0; Index < RegInfo.virtualRegisters().size(); ++Index) {
+    auto Reg = Register::makeVirtual(Index);
+    if (!Reg)
+      return std::unexpected(Reg.error());
+    const VirtualRegisterInfo &StoredInfo = RegInfo.virtualRegisters()[Index];
+    if (StoredInfo.IsTombstone)
+      continue;
+    Snapshot.emplace_back(*Reg, RegisterConfiguration{StoredInfo.Bank, StoredInfo.RegClass});
+    auto InfoResult = RegInfo.virtualRegisterInfo(*Reg);
+    if (!InfoResult)
+      return std::unexpected(InfoResult.error());
+    const VirtualRegisterInfo &InfoValue = InfoResult->get();
+    const MachineInstr *Context = nullptr;
+    for (const MachineOperand &Operand : RegInfo.regOperands(*Reg)) {
+      Context = Operand.parent();
+      if (Context != nullptr)
+        break;
+    }
+    auto Bank = Info->selectBank(Function, *Reg, InfoValue, Context, Target);
+    if (!Bank)
+      return std::unexpected(Bank.error());
+    if (Target.registers().registerBank(*Bank) == nullptr)
+      return std::unexpected(passFailure("target register-bank selector returned an unknown bank"));
+    if (InfoValue.Bank && *InfoValue.Bank != *Bank)
+      return std::unexpected(
+          passFailure("target register-bank selector conflicts with an existing bank"));
+    if (InfoValue.RegClass && !Target.registers().bankCoversClass(*Bank, *InfoValue.RegClass))
+      return std::unexpected(
+          passFailure("existing register class is not covered by selected bank"));
+    PlannedBanks.emplace_back(*Reg, *Bank);
+  }
+
+  for (MachineInstr *Instruction : layoutInstructions(Function)) {
+    auto Validation = Info->validateInstruction(*Instruction, Function, Target);
+    if (!Validation)
+      return std::unexpected(
+          prefixedError(Validation.error(), "register-bank mapping precondition failed: "));
+  }
+
+  for (const auto &[Reg, Bank] : PlannedBanks) {
+    const auto InfoResult = RegInfo.virtualRegisterInfo(Reg);
+    if (!InfoResult)
+      return std::unexpected(InfoResult.error());
+    if (!InfoResult->get().Bank) {
+      auto SetBank = RegInfo.setRegisterBank(Reg, Bank);
+      if (!SetBank)
+        return std::unexpected(SetBank.error());
+      Result.Changed = true;
+      Result.Changes.add(MachinePassChange::Registers);
+    }
+  }
+
+  const auto Restore = [&]() -> Expected<void> {
+    return restoreRegisterConfiguration(RegInfo, Snapshot);
+  };
+  for (MachineInstr *Instruction : layoutInstructions(Function)) {
+    auto Constraint = Info->constrainInstruction(*Instruction, Function, Target);
+    if (!Constraint) {
+      auto Restored = Restore();
+      if (!Restored)
+        return std::unexpected(prefixedError(Restored.error(), "register-bank rollback failed: "));
+      return std::unexpected(Constraint.error());
+    }
+    auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo());
+    if (!Validation) {
+      auto Restored = Restore();
+      if (!Restored)
+        return std::unexpected(prefixedError(Restored.error(), "register-bank rollback failed: "));
+      return std::unexpected(prefixedError(Validation.error(),
+                                           "register-bank selection produced invalid MachineIR: "));
+    }
+  }
+  auto RegisterValidation = Target.validateRegisterInfo(RegInfo);
+  if (!RegisterValidation) {
+    auto Restored = Restore();
+    if (!Restored)
+      return std::unexpected(prefixedError(Restored.error(), "register-bank rollback failed: "));
+    return std::unexpected(prefixedError(RegisterValidation.error(),
+                                         "register-bank selection produced invalid registers: "));
+  }
+
+  if (registerConfigurationFingerprint(RegInfo) != RegisterConfigurationBefore) {
+    Result.Changed = true;
+    Result.Changes.add(MachinePassChange::Registers);
+  }
+
+  auto Liveness = repairTrackedLiveness(Function, Target, Result);
+  if (!Liveness) {
+    auto Restored = Restore();
+    if (!Restored)
+      return std::unexpected(prefixedError(Restored.error(), "register-bank rollback failed: "));
+    return std::unexpected(
+        prefixedError(Liveness.error(), "register-bank liveness repair failed: "));
+  }
+  Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
+  return Result;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachinePipelinePasses.cpp b/backend/lib/CodeGen/MachinePipelinePasses.cpp
deleted file mode 100644
index 3dae07e..0000000
--- a/backend/lib/CodeGen/MachinePipelinePasses.cpp
+++ /dev/null
@@ -1,742 +0,0 @@
-// SPDX-License-Identifier: GPL-3.0-or-later
-
-#include "rcc/CodeGen/MachinePipelinePasses.h"
-
-#include "rcc/CodeGen/GenericOpcodes.h"
-#include "rcc/CodeGen/MachineBasicBlock.h"
-#include "rcc/CodeGen/MachineFunction.h"
-#include "rcc/CodeGen/MachineFunctionCloner.h"
-#include "rcc/CodeGen/MachineInstr.h"
-#include "rcc/CodeGen/MachineLiveness.h"
-#include "rcc/CodeGen/MachineRegisterInfo.h"
-#include "rcc/CodeGen/TargetDescription.h"
-
-#include <algorithm>
-#include <cstdint>
-#include <optional>
-#include <string>
-#include <unordered_set>
-#include <utility>
-#include <vector>
-
-namespace rcc {
-namespace {
-
-[[nodiscard]] const MachinePassContract &legalizerContract() {
-  static const MachinePassContract Contract{
-      .Name = "legalizer",
-      // LLVM's GlobalISel legalizer operates on SSA form and does not require
-      // the optional register-liveness tracking property.
-      .Requires = {MachineFunctionProperty::IsSSA},
-      .Sets = {MachineFunctionProperty::Legalized},
-      .Clears = {},
-      .RequiredAnalyses = {},
-      .VerificationStage = PipelineStage::Legalized,
-  };
-  return Contract;
-}
-
-[[nodiscard]] const MachinePassContract &bankSelectContract() {
-  static const MachinePassContract Contract{
-      .Name = "regbankselect",
-      .Requires = {MachineFunctionProperty::Legalized},
-      .Sets = {MachineFunctionProperty::RegBankSelected},
-      .Clears = {},
-      .RequiredAnalyses = {},
-      .VerificationStage = PipelineStage::RegBankSelected,
-  };
-  return Contract;
-}
-
-[[nodiscard]] const MachinePassContract &instructionSelectContract() {
-  static const MachinePassContract Contract{
-      .Name = "instruction-select",
-      .Requires = {MachineFunctionProperty::Legalized, MachineFunctionProperty::RegBankSelected},
-      .Sets = {MachineFunctionProperty::Selected},
-      .Clears = {},
-      .RequiredAnalyses = {},
-      .VerificationStage = PipelineStage::Selected,
-  };
-  return Contract;
-}
-
-struct OpcodeState final {
-  MachineInstrStableID Instruction;
-  Opcode OpcodeValue;
-  std::uint64_t OperandFingerprint = 0;
-
-  friend bool operator==(const OpcodeState &Left, const OpcodeState &Right) noexcept = default;
-};
-
-struct OpcodeStateHash final {
-  [[nodiscard]] std::size_t operator()(const OpcodeState &State) const noexcept {
-    return std::hash<std::uint64_t>{}(State.Instruction.value()) ^
-           (std::hash<std::uint32_t>{}(State.OpcodeValue.value()) << 1U) ^
-           (std::hash<std::uint64_t>{}(State.OperandFingerprint) << 2U);
-  }
-};
-
-void combineFingerprint(std::uint64_t &State, std::uint64_t Value) noexcept {
-  State ^= Value + 0x9e3779b97f4a7c15ULL + (State << 6U) + (State >> 2U);
-}
-
-[[nodiscard]] std::uint64_t
-registerConfigurationFingerprint(const MachineRegisterInfo &RegInfo) noexcept {
-  std::uint64_t Result = 0xcbf29ce484222325ULL;
-  for (const VirtualRegisterInfo &Info : RegInfo.virtualRegisters()) {
-    combineFingerprint(Result, Info.IsTombstone ? 1U : 0U);
-    combineFingerprint(Result, Info.Bank ? Info.Bank->value() : 0U);
-    combineFingerprint(Result, Info.RegClass ? Info.RegClass->value() : 0U);
-  }
-  return Result;
-}
-
-[[nodiscard]] std::uint64_t operandFingerprint(const MachineInstr &Instruction) noexcept {
-  std::uint64_t Result = 0xcbf29ce484222325ULL;
-  combineFingerprint(Result, Instruction.flags().rawValue());
-  combineFingerprint(Result, Instruction.operandCount());
-  for (const MachineOperand &Operand : Instruction.operands()) {
-    combineFingerprint(Result, static_cast<std::uint64_t>(Operand.kind()));
-    combineFingerprint(Result, Operand.targetFlags());
-    combineFingerprint(Result, Operand.registerFlags().rawValue());
-    combineFingerprint(Result, Operand.subReg().value());
-    if (const Register *Reg = Operand.getIf<Register>())
-      combineFingerprint(Result, Reg->opaqueValue());
-    else if (const std::int64_t *Immediate = Operand.getIf<std::int64_t>())
-      combineFingerprint(Result, static_cast<std::uint64_t>(*Immediate));
-    else if (const auto *Integer = Operand.getIf<IntegerImmediateOperand>())
-      combineFingerprint(Result, Integer->Value.bitWidth());
-    else if (const auto *Floating = Operand.getIf<FloatingImmediateOperand>())
-      combineFingerprint(Result, static_cast<std::uint64_t>(Floating->Bits.semantics()));
-    else if (const auto *Block = Operand.getIf<BasicBlockOperand>())
-      combineFingerprint(Result, Block->Block == nullptr ? 0 : Block->Block->stableID().value());
-  }
-  return Result;
-}
-
-[[nodiscard]] OpcodeState stateOf(const MachineInstr &Instruction) noexcept {
-  return {Instruction.stableID(), Instruction.opcode(), operandFingerprint(Instruction)};
-}
-
-[[nodiscard]] std::vector<MachineInstr *> layoutInstructions(MachineFunction &Function) {
-  std::vector<MachineInstr *> Result;
-  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next())
-    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
-         Instruction = Instruction->next())
-      Result.push_back(Instruction);
-  return Result;
-}
-
-[[nodiscard]] std::vector<MachineBasicBlock *> stableCFGPostOrder(MachineFunction &Function) {
-  std::vector<MachineBasicBlock *> Roots;
-  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next())
-    Roots.push_back(Block);
-  std::ranges::sort(Roots, {},
-                    [](const MachineBasicBlock *Block) { return Block->stableID().value(); });
-  if (MachineBasicBlock *Entry = Function.firstBlock(); Entry != nullptr) {
-    const auto Position = std::ranges::find(Roots, Entry);
-    if (Position != Roots.end())
-      std::rotate(Roots.begin(), Position, std::next(Position));
-  }
-
-  struct TraversalFrame final {
-    MachineBasicBlock *Block = nullptr;
-    std::vector<MachineBasicBlock *> Successors;
-    std::size_t NextSuccessor = 0;
-  };
-  const auto MakeFrame = [](MachineBasicBlock &Block) {
-    TraversalFrame Frame;
-    Frame.Block = &Block;
-    for (const MachineSuccessor &Successor : Block.successors()) {
-      if (Successor.Block != nullptr)
-        Frame.Successors.push_back(Successor.Block);
-    }
-    std::ranges::sort(Frame.Successors, {}, [](const MachineBasicBlock *Successor) {
-      return Successor->stableID().value();
-    });
-    return Frame;
-  };
-
-  std::vector<MachineBasicBlock *> Result;
-  std::unordered_set<MachineBasicBlock *> Visited;
-  std::vector<TraversalFrame> Stack;
-  for (MachineBasicBlock *Root : Roots) {
-    if (!Visited.insert(Root).second)
-      continue;
-    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));
-        continue;
-      }
-      Result.push_back(Frame.Block);
-      Stack.pop_back();
-    }
-  }
-  return Result;
-}
-
-[[nodiscard]] std::vector<MachineInstr *> bottomUpInstructions(MachineFunction &Function) {
-  std::vector<MachineInstr *> Result;
-  for (MachineBasicBlock *Block : stableCFGPostOrder(Function)) {
-    for (MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr;
-         Instruction = Instruction->previous())
-      Result.push_back(Instruction);
-  }
-  return Result;
-}
-
-[[nodiscard]] Expected<void> requireProperties(const MachineFunction &Function,
-                                               const MachinePassContract &Contract) {
-  const MachineFunctionProperties Missing = Contract.Requires.missingFrom(Function.properties());
-  if (!Missing.empty()) {
-    return makeUnexpected(ErrorCode::VerificationError,
-                          "pass '" + Contract.Name +
-                              "' requires properties: " + Missing.toString());
-  }
-  return {};
-}
-
-[[nodiscard]] Expected<void> restoreRegisterConfiguration(
-    MachineRegisterInfo &RegInfo,
-    const std::vector<std::pair<Register, std::pair<std::optional<RegisterBankID>,
-                                                    std::optional<RegisterClassID>>>> &Snapshot) {
-  for (const auto &[Reg, Configuration] : Snapshot) {
-    auto ClearBank = RegInfo.clearRegisterBank(Reg);
-    if (!ClearBank)
-      return std::unexpected(ClearBank.error());
-    if (Configuration.first) {
-      auto SetBank = RegInfo.setRegisterBank(Reg, *Configuration.first);
-      if (!SetBank)
-        return std::unexpected(SetBank.error());
-    }
-    auto ClearClass = RegInfo.clearRegisterClass(Reg);
-    if (!ClearClass)
-      return std::unexpected(ClearClass.error());
-    if (Configuration.second) {
-      auto SetClass = RegInfo.setRegisterClass(Reg, *Configuration.second);
-      if (!SetClass)
-        return std::unexpected(SetClass.error());
-    }
-  }
-  return {};
-}
-
-[[nodiscard]] Error passFailure(std::string Message,
-                                ErrorCode Code = ErrorCode::VerificationError) {
-  return Error(Code, std::move(Message));
-}
-
-[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) {
-  Prefix.append(Source.message());
-  return Error(Source.code(), std::move(Prefix));
-}
-
-[[nodiscard]] std::string_view legalizationActionName(LegalizationAction Action) noexcept {
-  switch (Action) {
-  case LegalizationAction::Legal:
-    return "legal";
-  case LegalizationAction::Unsupported:
-    return "unsupported";
-  case LegalizationAction::Custom:
-    return "custom";
-  case LegalizationAction::Lower:
-    return "lower";
-  case LegalizationAction::Libcall:
-    return "libcall";
-  case LegalizationAction::WidenScalar:
-    return "widen-scalar";
-  case LegalizationAction::NarrowScalar:
-    return "narrow-scalar";
-  case LegalizationAction::MoreElements:
-    return "more-elements";
-  case LegalizationAction::FewerElements:
-    return "fewer-elements";
-  case LegalizationAction::Bitcast:
-    return "bitcast";
-  case LegalizationAction::ChangeElementType:
-    return "change-element-type";
-  case LegalizationAction::ChangeAddressSpace:
-    return "change-address-space";
-  }
-  return "unknown";
-}
-
-[[nodiscard]] Expected<void> repairTrackedLiveness(MachineFunction &Function,
-                                                   const TargetDescription &Target,
-                                                   MachinePassResult &Result) {
-  if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
-    return {};
-  }
-  auto Rebuilt = rebuildMachineLiveness(Function, Target);
-  if (!Rebuilt)
-    return std::unexpected(Rebuilt.error());
-  if (*Rebuilt)
-    Result.Changes.add(MachinePassChange::Operands);
-  return {};
-}
-
-[[nodiscard]] Expected<void> clearTrackedLivenessFlags(MachineFunction &Function,
-                                                       MachinePassResult &Result) {
-  if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness))
-    return {};
-  bool Changed = false;
-  for (MachineInstr *Instruction : layoutInstructions(Function)) {
-    for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
-      MachineOperand &Operand = *Instruction->operandAt(Index);
-      if (!Operand.isRegister())
-        continue;
-      RegisterOperandFlags Flags = Operand.registerFlags();
-      if (!Flags.has(RegisterOperandFlag::Kill) && !Flags.has(RegisterOperandFlag::Dead))
-        continue;
-      Flags.clear(RegisterOperandFlag::Kill);
-      Flags.clear(RegisterOperandFlag::Dead);
-      auto Updated = Operand.setRegisterFlags(Flags);
-      if (!Updated)
-        return std::unexpected(Updated.error());
-      Changed = true;
-    }
-  }
-  if (Changed)
-    Result.Changes.add(MachinePassChange::Operands);
-  return {};
-}
-
-} // namespace
-
-const MachinePassContract &LegalizerPass::contract() const noexcept {
-  return legalizerContract();
-}
-
-Expected<MachinePassResult> LegalizerPass::run(MachineFunction &Function,
-                                               const TargetDescription &Target,
-                                               MachineAnalysisManager &Analyses) {
-  if (Info == nullptr)
-    return std::unexpected(
-        passFailure("legalizer has no target behavior interface", ErrorCode::InvalidArgument));
-  auto Required = requireProperties(Function, contract());
-  if (!Required)
-    return std::unexpected(Required.error());
-
-  auto Trial = cloneMachineFunction(
-      Function, Target,
-      MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
-  if (!Trial)
-    return std::unexpected(prefixedError(Trial.error(), "legalizer transaction setup failed: "));
-  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
-  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
-  if (!TrialResult)
-    return std::unexpected(TrialResult.error());
-  Actions.beginReplay();
-  auto Result = runImplementation(Function, Target, Actions);
-  if (!Result) {
-    return std::unexpected(prefixedError(
-        Result.error(), "legalizer diverged after a successful transaction preflight: "));
-  }
-  auto Replayed = Actions.finishReplay();
-  if (!Replayed)
-    return std::unexpected(Replayed.error());
-  return Result;
-}
-
-Expected<MachinePassResult> LegalizerPass::runImplementation(MachineFunction &Function,
-                                                             const TargetDescription &Target,
-                                                             MachineActionReplay &Actions) {
-
-  MachinePassResult Result;
-  std::unordered_set<OpcodeState, OpcodeStateHash> SeenStates;
-
-  std::vector<MachineInstr *> Worklist = layoutInstructions(Function);
-  std::unordered_set<MachineInstrStableID> PendingInstructions;
-  for (const MachineInstr *Instruction : Worklist)
-    PendingInstructions.insert(Instruction->stableID());
-  for (std::size_t Index = 0; Index < Worklist.size(); ++Index) {
-    MachineInstr *Instruction = Worklist[Index];
-    if (Instruction != nullptr)
-      PendingInstructions.erase(Instruction->stableID());
-    if (Instruction == nullptr || Instruction->parent() == nullptr)
-      continue;
-
-    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
-    if (Descriptor == nullptr)
-      return std::unexpected(
-          passFailure("legalizer encountered an unknown instruction descriptor"));
-    if (!Descriptor->Flags.has(InstructionFlag::Generic))
-      continue;
-
-    auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo());
-    if (!Validation)
-      return std::unexpected(prefixedError(Validation.error(), "legalizer input is invalid: "));
-
-    auto Action = Info->classify(*Instruction, Function, Target);
-    if (!Action)
-      return std::unexpected(Action.error());
-    if (*Action == LegalizationAction::Legal)
-      continue;
-    if (*Action == LegalizationAction::Unsupported) {
-      return std::unexpected(
-          passFailure("target legalizer rejected generic instruction '" + Descriptor->Name + "'",
-                      ErrorCode::Unsupported));
-    }
-
-    const OpcodeState Before = stateOf(*Instruction);
-    if (!SeenStates.insert(Before).second)
-      return std::unexpected(
-          passFailure("target legalizer entered a repeated state for '" + Descriptor->Name + "'",
-                      ErrorCode::InternalError));
-
-    auto LoweringValidation = Info->validateLowering(*Instruction, Function, Target, *Action);
-    if (!LoweringValidation)
-      return std::unexpected(
-          prefixedError(LoweringValidation.error(), "legalizer lowering precondition failed: "));
-    std::string Rule = "legalize.";
-    Rule.append(legalizationActionName(*Action));
-    Rule.push_back('.');
-    Rule.append(Descriptor->Name);
-    auto Accepted = Actions.request(Rule, Function, Instruction->stableID());
-    if (!Accepted)
-      return std::unexpected(Accepted.error());
-    if (!*Accepted) {
-      return std::unexpected(
-          passFailure("required legalizer action was rejected for '" + Descriptor->Name + "'",
-                      ErrorCode::VerificationError));
-    }
-    auto Lowered = Info->lower(*Instruction, Function, Target, *Action);
-    if (!Lowered)
-      return std::unexpected(Lowered.error());
-    const bool InstructionWasErased = Instruction->parent() == nullptr;
-    if (!InstructionWasErased) {
-      const OpcodeState After = stateOf(*Instruction);
-      if (After == Before)
-        return std::unexpected(passFailure("target legalizer made no observable progress for '" +
-                                               Descriptor->Name + "'",
-                                           ErrorCode::InternalError));
-    }
-    Result.Changed = true;
-    Result.Changes.add(MachinePassChange::Instructions);
-
-    const std::vector<MachineInstr *> Current = layoutInstructions(Function);
-    for (MachineInstr *Candidate : Current) {
-      const InstructionDescriptor *CandidateDescriptor =
-          Target.instructionDescriptor(Candidate->opcode());
-      if (CandidateDescriptor == nullptr)
-        return std::unexpected(passFailure("legalizer produced an unknown instruction descriptor"));
-      if (CandidateDescriptor->Flags.has(InstructionFlag::Generic) &&
-          PendingInstructions.insert(Candidate->stableID()).second) {
-        Worklist.push_back(Candidate);
-      }
-    }
-  }
-
-  for (MachineInstr *Instruction : layoutInstructions(Function)) {
-    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
-    if (Descriptor == nullptr)
-      return std::unexpected(passFailure("legalizer produced an unknown instruction descriptor"));
-    if (!Descriptor->Flags.has(InstructionFlag::Generic))
-      continue;
-    auto Action = Info->classify(*Instruction, Function, Target);
-    if (!Action)
-      return std::unexpected(Action.error());
-    if (*Action != LegalizationAction::Legal)
-      return std::unexpected(
-          passFailure("legalizer reached a fixed point with an illegal generic instruction '" +
-                          Descriptor->Name + "'",
-                      *Action == LegalizationAction::Unsupported ? ErrorCode::Unsupported
-                                                                 : ErrorCode::InternalError));
-    auto FinalValidation = Target.validateInstruction(*Instruction, Function.registerInfo());
-    if (!FinalValidation)
-      return std::unexpected(
-          prefixedError(FinalValidation.error(), "legalizer produced invalid MachineIR: "));
-  }
-  auto Liveness = clearTrackedLivenessFlags(Function, Result);
-  if (!Liveness)
-    return std::unexpected(
-        prefixedError(Liveness.error(), "legalizer liveness-flag invalidation failed: "));
-  Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
-  return Result;
-}
-
-const MachinePassContract &RegisterBankSelectPass::contract() const noexcept {
-  return bankSelectContract();
-}
-
-Expected<MachinePassResult> RegisterBankSelectPass::run(MachineFunction &Function,
-                                                        const TargetDescription &Target,
-                                                        MachineAnalysisManager &) {
-  if (Info == nullptr)
-    return std::unexpected(passFailure("register-bank select has no target behavior interface",
-                                       ErrorCode::InvalidArgument));
-  auto Required = requireProperties(Function, contract());
-  if (!Required)
-    return std::unexpected(Required.error());
-
-  MachinePassResult Result;
-  MachineRegisterInfo &RegInfo = Function.registerInfo();
-  const std::uint64_t RegisterConfigurationBefore = registerConfigurationFingerprint(RegInfo);
-  using RegisterConfiguration =
-      std::pair<std::optional<RegisterBankID>, std::optional<RegisterClassID>>;
-  std::vector<std::pair<Register, RegisterConfiguration>> Snapshot;
-  std::vector<std::pair<Register, RegisterBankID>> PlannedBanks;
-  for (std::size_t Index = 0; Index < RegInfo.virtualRegisters().size(); ++Index) {
-    auto Reg = Register::makeVirtual(Index);
-    if (!Reg)
-      return std::unexpected(Reg.error());
-    const VirtualRegisterInfo &StoredInfo = RegInfo.virtualRegisters()[Index];
-    if (StoredInfo.IsTombstone)
-      continue;
-    Snapshot.emplace_back(*Reg, RegisterConfiguration{StoredInfo.Bank, StoredInfo.RegClass});
-    auto InfoResult = RegInfo.virtualRegisterInfo(*Reg);
-    if (!InfoResult)
-      return std::unexpected(InfoResult.error());
-    const VirtualRegisterInfo &InfoValue = InfoResult->get();
-    const MachineInstr *Context = nullptr;
-    for (const MachineOperand &Operand : RegInfo.regOperands(*Reg)) {
-      Context = Operand.parent();
-      if (Context != nullptr)
-        break;
-    }
-    auto Bank = Info->selectBank(Function, *Reg, InfoValue, Context, Target);
-    if (!Bank)
-      return std::unexpected(Bank.error());
-    if (Target.registers().registerBank(*Bank) == nullptr)
-      return std::unexpected(passFailure("target register-bank selector returned an unknown bank"));
-    if (InfoValue.Bank && *InfoValue.Bank != *Bank)
-      return std::unexpected(
-          passFailure("target register-bank selector conflicts with an existing bank"));
-    if (InfoValue.RegClass && !Target.registers().bankCoversClass(*Bank, *InfoValue.RegClass))
-      return std::unexpected(
-          passFailure("existing register class is not covered by selected bank"));
-    PlannedBanks.emplace_back(*Reg, *Bank);
-  }
-
-  for (MachineInstr *Instruction : layoutInstructions(Function)) {
-    auto Validation = Info->validateInstruction(*Instruction, Function, Target);
-    if (!Validation)
-      return std::unexpected(
-          prefixedError(Validation.error(), "register-bank mapping precondition failed: "));
-  }
-
-  for (const auto &[Reg, Bank] : PlannedBanks) {
-    const auto InfoResult = RegInfo.virtualRegisterInfo(Reg);
-    if (!InfoResult)
-      return std::unexpected(InfoResult.error());
-    if (!InfoResult->get().Bank) {
-      auto SetBank = RegInfo.setRegisterBank(Reg, Bank);
-      if (!SetBank)
-        return std::unexpected(SetBank.error());
-      Result.Changed = true;
-      Result.Changes.add(MachinePassChange::Registers);
-    }
-  }
-
-  const auto Restore = [&]() -> Expected<void> {
-    return restoreRegisterConfiguration(RegInfo, Snapshot);
-  };
-  for (MachineInstr *Instruction : layoutInstructions(Function)) {
-    auto Constraint = Info->constrainInstruction(*Instruction, Function, Target);
-    if (!Constraint) {
-      auto Restored = Restore();
-      if (!Restored)
-        return std::unexpected(prefixedError(Restored.error(), "register-bank rollback failed: "));
-      return std::unexpected(Constraint.error());
-    }
-    auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo());
-    if (!Validation) {
-      auto Restored = Restore();
-      if (!Restored)
-        return std::unexpected(prefixedError(Restored.error(), "register-bank rollback failed: "));
-      return std::unexpected(prefixedError(Validation.error(),
-                                           "register-bank selection produced invalid MachineIR: "));
-    }
-  }
-  auto RegisterValidation = Target.validateRegisterInfo(RegInfo);
-  if (!RegisterValidation) {
-    auto Restored = Restore();
-    if (!Restored)
-      return std::unexpected(prefixedError(Restored.error(), "register-bank rollback failed: "));
-    return std::unexpected(prefixedError(RegisterValidation.error(),
-                                         "register-bank selection produced invalid registers: "));
-  }
-
-  if (registerConfigurationFingerprint(RegInfo) != RegisterConfigurationBefore) {
-    Result.Changed = true;
-    Result.Changes.add(MachinePassChange::Registers);
-  }
-
-  auto Liveness = repairTrackedLiveness(Function, Target, Result);
-  if (!Liveness) {
-    auto Restored = Restore();
-    if (!Restored)
-      return std::unexpected(prefixedError(Restored.error(), "register-bank rollback failed: "));
-    return std::unexpected(
-        prefixedError(Liveness.error(), "register-bank liveness repair failed: "));
-  }
-  Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
-  return Result;
-}
-
-const MachinePassContract &InstructionSelectPass::contract() const noexcept {
-  return instructionSelectContract();
-}
-
-Expected<MachinePassResult> InstructionSelectPass::run(MachineFunction &Function,
-                                                       const TargetDescription &Target,
-                                                       MachineAnalysisManager &Analyses) {
-  if (Info == nullptr)
-    return std::unexpected(passFailure("instruction select has no target behavior interface",
-                                       ErrorCode::InvalidArgument));
-  auto Required = requireProperties(Function, contract());
-  if (!Required)
-    return std::unexpected(Required.error());
-
-  auto Trial = cloneMachineFunction(
-      Function, Target,
-      MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
-  if (!Trial) {
-    return std::unexpected(
-        prefixedError(Trial.error(), "instruction-selection transaction setup failed: "));
-  }
-  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
-  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
-  if (!TrialResult)
-    return std::unexpected(TrialResult.error());
-  Actions.beginReplay();
-  auto Result = runImplementation(Function, Target, Actions);
-  if (!Result) {
-    return std::unexpected(
-        prefixedError(Result.error(),
-                      "instruction selection diverged after a successful transaction preflight: "));
-  }
-  auto Replayed = Actions.finishReplay();
-  if (!Replayed)
-    return std::unexpected(Replayed.error());
-  return Result;
-}
-
-Expected<MachinePassResult>
-InstructionSelectPass::runImplementation(MachineFunction &Function, const TargetDescription &Target,
-                                         MachineActionReplay &Actions) {
-
-  MachinePassResult Result;
-  std::vector<MachineInstr *> Worklist;
-  std::unordered_set<MachineInstrStableID> DiscoveredInstructions;
-  std::unordered_set<OpcodeState, OpcodeStateHash> SeenStates;
-  for (MachineInstr *Instruction : bottomUpInstructions(Function)) {
-    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
-    if (Descriptor == nullptr)
-      return std::unexpected(
-          passFailure("instruction selector encountered an unknown instruction descriptor"));
-    auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo());
-    if (!Validation)
-      return std::unexpected(
-          prefixedError(Validation.error(), "instruction selector input is invalid: "));
-    if (!Descriptor->Flags.has(InstructionFlag::Generic))
-      continue;
-    auto Match = Info->canSelect(*Instruction, Function, Target);
-    if (!Match)
-      return std::unexpected(Match.error());
-    Worklist.push_back(Instruction);
-    DiscoveredInstructions.insert(Instruction->stableID());
-  }
-
-  for (std::size_t Index = 0; Index < Worklist.size(); ++Index) {
-    MachineInstr *Instruction = Worklist[Index];
-    if (Instruction->parent() == nullptr)
-      return std::unexpected(passFailure("instruction selector lost its input instruction"));
-    const InstructionDescriptor *CurrentDescriptor =
-        Target.instructionDescriptor(Instruction->opcode());
-    if (CurrentDescriptor == nullptr)
-      return std::unexpected(
-          passFailure("instruction selector encountered an unknown instruction descriptor"));
-    if (!CurrentDescriptor->Flags.has(InstructionFlag::Generic))
-      continue;
-    const OpcodeState Before = stateOf(*Instruction);
-    if (!SeenStates.insert(Before).second) {
-      return std::unexpected(passFailure("instruction selector entered a repeated state for '" +
-                                             CurrentDescriptor->Name + "'",
-                                         ErrorCode::InternalError));
-    }
-    auto Match = Info->canSelect(*Instruction, Function, Target);
-    if (!Match)
-      return std::unexpected(Match.error());
-    std::string Rule = "select.";
-    Rule.append(CurrentDescriptor->Name);
-    auto Accepted = Actions.request(Rule, Function, Instruction->stableID());
-    if (!Accepted)
-      return std::unexpected(Accepted.error());
-    if (!*Accepted) {
-      return std::unexpected(passFailure("required selection action was rejected for '" +
-                                             CurrentDescriptor->Name + "'",
-                                         ErrorCode::VerificationError));
-    }
-    auto Selection = Info->select(*Instruction, Function, Target);
-    if (!Selection)
-      return std::unexpected(Selection.error());
-    const InstructionDescriptor *Selected = Target.instructionDescriptor(Instruction->opcode());
-    if (Selected == nullptr)
-      return std::unexpected(
-          passFailure("instruction selector produced an unknown instruction descriptor"));
-    auto Constraint = Info->constrainSelectedInstruction(*Instruction, Function, Target);
-    if (!Constraint) {
-      return std::unexpected(prefixedError(
-          Constraint.error(), "instruction selector could not constrain selected registers: "));
-    }
-    auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo());
-    if (!Validation)
-      return std::unexpected(
-          prefixedError(Validation.error(), "instruction selector produced invalid MachineIR: "));
-    const OpcodeState After = stateOf(*Instruction);
-    if (After == Before)
-      return std::unexpected(
-          passFailure("instruction selector reported success without observable progress",
-                      ErrorCode::InternalError));
-    Result.Changed = true;
-    Result.Changes.add(MachinePassChange::Instructions);
-    if (Selected->Flags.has(InstructionFlag::Generic))
-      Worklist.push_back(Instruction);
-    for (MachineInstr *Candidate : bottomUpInstructions(Function)) {
-      const InstructionDescriptor *CandidateDescriptor =
-          Target.instructionDescriptor(Candidate->opcode());
-      if (CandidateDescriptor == nullptr)
-        return std::unexpected(
-            passFailure("instruction selector produced an unknown instruction descriptor"));
-      if (!CandidateDescriptor->Flags.has(InstructionFlag::Generic) ||
-          !DiscoveredInstructions.insert(Candidate->stableID()).second) {
-        continue;
-      }
-      auto CandidateMatch = Info->canSelect(*Candidate, Function, Target);
-      if (!CandidateMatch)
-        return std::unexpected(CandidateMatch.error());
-      Worklist.push_back(Candidate);
-    }
-  }
-  for (MachineInstr *Instruction : layoutInstructions(Function)) {
-    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
-    if (Descriptor == nullptr)
-      return std::unexpected(
-          passFailure("instruction selector produced an unknown instruction descriptor"));
-    auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo());
-    if (!Validation)
-      return std::unexpected(
-          prefixedError(Validation.error(), "instruction selector produced invalid MachineIR: "));
-    if (Descriptor->Flags.has(InstructionFlag::Generic))
-      return std::unexpected(
-          passFailure("instruction selector left a generic opcode in the function"));
-  }
-  auto RegisterValidation = Target.validateRegisterInfo(Function.registerInfo());
-  if (!RegisterValidation)
-    return std::unexpected(prefixedError(RegisterValidation.error(),
-                                         "instruction selection produced invalid registers: "));
-  auto Liveness = repairTrackedLiveness(Function, Target, Result);
-  if (!Liveness) {
-    return std::unexpected(
-        prefixedError(Liveness.error(), "instruction-selection liveness repair failed: "));
-  }
-  Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
-  return Result;
-}
-
-} // namespace rcc
diff --git a/backend/lib/Target/RISCV/RISCVCodeGen.cpp b/backend/lib/Target/RISCV/RISCVCodeGen.cpp
index 00dba94..b610d81 100644
--- a/backend/lib/Target/RISCV/RISCVCodeGen.cpp
+++ b/backend/lib/Target/RISCV/RISCVCodeGen.cpp
@@ -3250,7 +3250,7 @@ struct VACopyPlan final {
   return eraseInstruction(Instruction);
 }
 
-class RISCVLegalizerInfo final : public TargetLegalizerInfo {
+class RISCVLegalizerInfo final : public LegalizerInfo {
 public:
   explicit RISCVLegalizerInfo(RISCVSubtargetFeatures Features) : Features(Features) {}
 
@@ -3985,7 +3985,7 @@ private:
   RISCVSubtargetFeatures Features;
 };
 
-class RISCVRegisterBankInfo final : public TargetRegisterBankInfo {
+class RISCVRegisterBankInfo final : public RegisterBankInfo {
 public:
   [[nodiscard]] Expected<RegisterBankID> selectBank(const MachineFunction &, Register,
                                                     const VirtualRegisterInfo &Info,
@@ -4049,7 +4049,7 @@ public:
   }
 };
 
-class RISCVInstructionSelector final : public TargetInstructionSelector {
+class RISCVInstructionSelector final : public InstructionSelector {
 public:
   [[nodiscard]] Expected<void>
   constrainSelectedInstruction(MachineInstr &Instruction, MachineFunction &Function,
@@ -6514,21 +6514,21 @@ private:
 
 } // namespace
 
-const TargetLegalizerInfo &legalizerInfo() noexcept {
+const LegalizerInfo &legalizerInfo() noexcept {
   static const RISCVLegalizerInfo Value(RISCVSubtargetFeatures::rv64gc());
   return Value;
 }
 
-std::unique_ptr<TargetLegalizerInfo> createLegalizerInfo(RISCVSubtargetFeatures Features) {
+std::unique_ptr<LegalizerInfo> createLegalizerInfo(RISCVSubtargetFeatures Features) {
   return std::make_unique<RISCVLegalizerInfo>(Features);
 }
 
-const TargetRegisterBankInfo &registerBankInfo() noexcept {
+const RegisterBankInfo &registerBankInfo() noexcept {
   static const RISCVRegisterBankInfo Value;
   return Value;
 }
 
-const TargetInstructionSelector &instructionSelector() noexcept {
+const InstructionSelector &instructionSelector() noexcept {
   static const RISCVInstructionSelector Value;
   return Value;
 }
diff --git a/backend/lib/Target/RISCV/RISCVPipeline.cpp b/backend/lib/Target/RISCV/RISCVPipeline.cpp
index 08a4653..7c778ea 100644
--- a/backend/lib/Target/RISCV/RISCVPipeline.cpp
+++ b/backend/lib/Target/RISCV/RISCVPipeline.cpp
@@ -3,10 +3,12 @@
 #include "rcc/Target/RISCV/RISCVPipeline.h"
 
 #include "RISCVInstrInfo.h"
+#include "rcc/CodeGen/GlobalISel/InstructionSelect.h"
+#include "rcc/CodeGen/GlobalISel/Legalizer.h"
+#include "rcc/CodeGen/GlobalISel/RegBankSelect.h"
 #include "rcc/CodeGen/MachineCombiner.h"
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineOptimizationPipeline.h"
-#include "rcc/CodeGen/MachinePipelinePasses.h"
 #include "rcc/CodeGen/MachineSSAExit.h"
 #include "rcc/CodeGen/RegAllocPBQP.h"
 #include "rcc/CodeGen/TargetDescription.h"
@@ -33,13 +35,13 @@ template <typename PassT, typename... ArgumentT>
                                             MachineCombinerStage::PreLegalizer);
   if (!Added)
     return std::unexpected(Added.error());
-  Added = addPass<LegalizerPass>(Pipeline, createLegalizerInfo(Features));
+  Added = addPass<Legalizer>(Pipeline, createLegalizerInfo(Features));
   if (!Added)
     return std::unexpected(Added.error());
-  Added = addPass<RegisterBankSelectPass>(Pipeline, registerBankInfo());
+  Added = addPass<RegBankSelect>(Pipeline, registerBankInfo());
   if (!Added)
     return std::unexpected(Added.error());
-  return addPass<InstructionSelectPass>(Pipeline, instructionSelector());
+  return addPass<InstructionSelect>(Pipeline, instructionSelector());
 }
 
 [[nodiscard]] Expected<void> addSSAExitPipeline(MachinePassManager &Pipeline) {
@@ -86,17 +88,17 @@ Expected<void> addCanonicalPipeline(MachinePassManager &Pipeline, const MachineF
                                               MachineCombinerStage::PreLegalizer);
     if (!Added)
       return std::unexpected(Added.error());
-    Added = addPass<LegalizerPass>(Pipeline, createLegalizerInfo(Features));
+    Added = addPass<Legalizer>(Pipeline, createLegalizerInfo(Features));
     if (!Added)
       return std::unexpected(Added.error());
   }
   if (!Function.properties().has(MachineFunctionProperty::RegBankSelected)) {
-    auto Added = addPass<RegisterBankSelectPass>(Pipeline, registerBankInfo());
+    auto Added = addPass<RegBankSelect>(Pipeline, registerBankInfo());
     if (!Added)
       return std::unexpected(Added.error());
   }
   if (!Function.properties().has(MachineFunctionProperty::Selected)) {
-    auto Added = addPass<InstructionSelectPass>(Pipeline, instructionSelector());
+    auto Added = addPass<InstructionSelect>(Pipeline, instructionSelector());
     if (!Added)
       return std::unexpected(Added.error());
   }
diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt
index 1b66194..5f73d3b 100644
--- a/backend/unittests/CodeGen/CMakeLists.txt
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -22,7 +22,6 @@ set(
   MachineOperandTest.cpp
   MachineOptimizationTest.cpp
   MachinePassTest.cpp
-  MachinePipelinePassesTest.cpp
   MachineSchedulingTest.cpp
   PBQPTest.cpp
   RegisterAllocationTest.cpp
@@ -337,16 +336,7 @@ target_link_libraries(
 
 add_test(NAME RCCBackend.CodeGen.MachinePass COMMAND RCCBackendCodeGenMachinePassTests)
 
-add_executable(RCCBackendCodeGenMachinePipelinePassesTests MachinePipelinePassesTest.cpp)
-rcc_backend_configure_target(RCCBackendCodeGenMachinePipelinePassesTests)
-target_link_libraries(
-  RCCBackendCodeGenMachinePipelinePassesTests
-  PRIVATE RCCBackend::CodeGen RCCBackend::RISCV RCCBackend::TestTarget
-)
-add_test(
-  NAME RCCBackend.CodeGen.MachinePipelinePasses
-  COMMAND RCCBackendCodeGenMachinePipelinePassesTests
-)
+add_subdirectory(GlobalISel)
 
 add_executable(RCCBackendCodeGenMachineAnalysesTests MachineAnalysesTest.cpp)
 rcc_backend_configure_target(RCCBackendCodeGenMachineAnalysesTests)
@@ -459,7 +449,6 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOptimizationTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePassTest.cpp"
-  "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePassesTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineSchedulingTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/PBQPTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegisterAllocationTest.cpp"
@@ -501,7 +490,6 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOptimizationTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePassTest.cpp"
-  "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePassesTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineSchedulingTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/PBQPTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegisterAllocationTest.cpp"
diff --git a/backend/unittests/CodeGen/GlobalISel/CMakeLists.txt b/backend/unittests/CodeGen/GlobalISel/CMakeLists.txt
new file mode 100644
index 0000000..319e31f
--- /dev/null
+++ b/backend/unittests/CodeGen/GlobalISel/CMakeLists.txt
@@ -0,0 +1,44 @@
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+add_executable(RCCBackendCodeGenLegalizerTests LegalizerTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenLegalizerTests)
+target_link_libraries(
+  RCCBackendCodeGenLegalizerTests
+  PRIVATE RCCBackend::CodeGen RCCBackend::RISCV RCCBackend::TestTarget
+)
+add_test(NAME RCCBackend.CodeGen.GlobalISel.Legalizer COMMAND RCCBackendCodeGenLegalizerTests)
+
+add_executable(RCCBackendCodeGenRegBankSelectTests RegBankSelectTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenRegBankSelectTests)
+target_link_libraries(
+  RCCBackendCodeGenRegBankSelectTests
+  PRIVATE RCCBackend::CodeGen RCCBackend::RISCV RCCBackend::TestTarget
+)
+add_test(
+  NAME RCCBackend.CodeGen.GlobalISel.RegBankSelect
+  COMMAND RCCBackendCodeGenRegBankSelectTests
+)
+
+add_executable(RCCBackendCodeGenInstructionSelectTests InstructionSelectTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenInstructionSelectTests)
+target_link_libraries(
+  RCCBackendCodeGenInstructionSelectTests
+  PRIVATE RCCBackend::CodeGen RCCBackend::RISCV RCCBackend::TestTarget
+)
+add_test(
+  NAME RCCBackend.CodeGen.GlobalISel.InstructionSelect
+  COMMAND RCCBackendCodeGenInstructionSelectTests
+)
+
+rcc_backend_register_format_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/GISelMITest.h"
+  "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelectTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelectTest.cpp"
+)
+
+rcc_backend_register_tidy_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelectTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelectTest.cpp"
+)
diff --git a/backend/unittests/CodeGen/GlobalISel/GISelMITest.h b/backend/unittests/CodeGen/GlobalISel/GISelMITest.h
new file mode 100644
index 0000000..5b16535
--- /dev/null
+++ b/backend/unittests/CodeGen/GlobalISel/GISelMITest.h
@@ -0,0 +1,115 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_UNITTESTS_CODEGEN_GLOBALISEL_GISELMITEST_H
+#define RCC_UNITTESTS_CODEGEN_GLOBALISEL_GISELMITEST_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/MachineRegisterInfo.h"
+#include "rcc/Target/RISCV/RISCVTarget.h"
+
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#include <string>
+#include <string_view>
+#include <utility>
+
+namespace rcc::test {
+
+class TestContext final {
+public:
+  void expect(bool Condition, std::string_view Message) {
+    if (Condition)
+      return;
+    std::cerr << Message << '\n';
+    ++Failures;
+  }
+
+  [[nodiscard]] int result() const noexcept {
+    return Failures == 0 ? 0 : 1;
+  }
+
+private:
+  int Failures = 0;
+};
+
+struct FunctionFixture final {
+  std::unique_ptr<rcc::MachineFunction> Function;
+  rcc::MachineBasicBlock *Entry = nullptr;
+};
+
+[[nodiscard]] inline FunctionFixture createFixture(TestContext &Context, std::string_view Name,
+                                                   std::uint64_t ID) {
+  auto Function =
+      rcc::MachineFunction::create(std::string(Name), rcc::MachineFunctionStableID::fromValue(ID));
+  Context.expect(Function.has_value(), "machine pipeline function creation must succeed");
+  if (!Function)
+    return {};
+  auto Entry = (*Function)->createBasicBlock();
+  Context.expect(Entry.has_value(), "machine pipeline block creation must succeed");
+  if (!Entry || !(*Function)->appendBlock(**Entry))
+    return {};
+  return {std::move(*Function), *Entry};
+}
+
+[[nodiscard]] inline rcc::Register
+createRegister(TestContext &Context, rcc::MachineFunction &Function, std::uint32_t Bits) {
+  auto Type = rcc::LLT::makeInteger(Bits);
+  Context.expect(Type.has_value(), "integer LLT construction must succeed");
+  if (!Type)
+    return {};
+  auto Reg = Function.registerInfo().createVirtualRegister(*Type);
+  Context.expect(Reg.has_value(), "virtual register construction must succeed");
+  return Reg ? *Reg : rcc::Register{};
+}
+
+[[nodiscard]] inline rcc::Register createFloatRegister(TestContext &Context,
+                                                       rcc::MachineFunction &Function) {
+  auto Type = rcc::LLT::makeFloat(rcc::FloatSemantics::IEEEDouble);
+  Context.expect(Type.has_value(), "floating LLT construction must succeed");
+  if (!Type)
+    return {};
+  auto Reg = Function.registerInfo().createVirtualRegister(*Type);
+  Context.expect(Reg.has_value(), "floating virtual register construction must succeed");
+  return Reg ? *Reg : rcc::Register{};
+}
+
+[[nodiscard]] inline bool assignGPR(rcc::MachineFunction &Function, rcc::Register Reg) {
+  const auto Bank =
+      rcc::RegisterBankID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterBank::GPR));
+  const auto RegClass =
+      rcc::RegisterClassID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterClass::GPR));
+  return Function.registerInfo().setRegisterBank(Reg, Bank).has_value() &&
+         Function.registerInfo().setRegisterClass(Reg, RegClass).has_value();
+}
+
+[[nodiscard]] inline bool buildConstant(TestContext &Context, rcc::MachineIRBuilder &Builder,
+                                        rcc::Register Destination, std::int64_t Value) {
+  auto Pending = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_CONSTANT));
+  if (!Pending || !Pending->addDef(Destination) || !Pending->addImmediate(Value) ||
+      !Pending->build()) {
+    Context.expect(false, "generic constant construction must succeed");
+    return false;
+  }
+  return true;
+}
+
+[[nodiscard]] inline bool buildAdd(TestContext &Context, rcc::MachineIRBuilder &Builder,
+                                   rcc::Register Destination, rcc::Register Left,
+                                   rcc::Register Right) {
+  auto Pending = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_ADD));
+  if (!Pending || !Pending->addDef(Destination) || !Pending->addUse(Left) ||
+      !Pending->addUse(Right) || !Pending->build()) {
+    Context.expect(false, "generic add construction must succeed");
+    return false;
+  }
+  return true;
+}
+
+} // namespace rcc::test
+
+#endif // RCC_UNITTESTS_CODEGEN_GLOBALISEL_GISELMITEST_H
diff --git a/backend/unittests/CodeGen/GlobalISel/InstructionSelectTest.cpp b/backend/unittests/CodeGen/GlobalISel/InstructionSelectTest.cpp
new file mode 100644
index 0000000..9e09934
--- /dev/null
+++ b/backend/unittests/CodeGen/GlobalISel/InstructionSelectTest.cpp
@@ -0,0 +1,357 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/InstructionSelect.h"
+
+#include "GISelMITest.h"
+#include "rcc/CodeGen/GlobalISel/Legalizer.h"
+#include "rcc/CodeGen/GlobalISel/RegBankSelect.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/Target/RISCV/RISCVCodeGen.h"
+
+#include <algorithm>
+#include <array>
+#include <cstdint>
+#include <memory>
+#include <ranges>
+#include <vector>
+
+namespace {
+
+using rcc::test::assignGPR;
+using rcc::test::buildAdd;
+using rcc::test::buildConstant;
+using rcc::test::createFixture;
+using rcc::test::createRegister;
+using rcc::test::TestContext;
+
+class MutatingFailingSelector final : public rcc::InstructionSelector {
+public:
+  [[nodiscard]] rcc::Expected<void> canSelect(const rcc::MachineInstr &,
+                                              const rcc::MachineFunction &,
+                                              const rcc::TargetDescription &) const override {
+    return {};
+  }
+
+  [[nodiscard]] rcc::Expected<void> select(rcc::MachineInstr &Instruction, rcc::MachineFunction &,
+                                           const rcc::TargetDescription &) const override {
+    auto Mutation = Instruction.setOpcode(rcc::opcode(rcc::GenericOpcode::G_SUB));
+    if (!Mutation)
+      return std::unexpected(Mutation.error());
+    return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, "test selector rejected its renderer");
+  }
+};
+
+class RecordingSelector final : public rcc::InstructionSelector {
+public:
+  explicit RecordingSelector(const rcc::InstructionSelector &Delegate) : Delegate(&Delegate) {}
+
+  [[nodiscard]] rcc::Expected<void> canSelect(const rcc::MachineInstr &Instruction,
+                                              const rcc::MachineFunction &Function,
+                                              const rcc::TargetDescription &Target) const override {
+    return Delegate->canSelect(Instruction, Function, Target);
+  }
+
+  [[nodiscard]] rcc::Expected<void> select(rcc::MachineInstr &Instruction,
+                                           rcc::MachineFunction &Function,
+                                           const rcc::TargetDescription &Target) const override {
+    SelectedIDs.push_back(Instruction.stableID().value());
+    return Delegate->select(Instruction, Function, Target);
+  }
+
+  [[nodiscard]] const std::vector<std::uint64_t> &selectedIDs() const noexcept {
+    return SelectedIDs;
+  }
+
+private:
+  const rcc::InstructionSelector *Delegate;
+  mutable std::vector<std::uint64_t> SelectedIDs;
+};
+
+class TwoStepSelector final : public rcc::InstructionSelector {
+public:
+  [[nodiscard]] rcc::Expected<void> canSelect(const rcc::MachineInstr &,
+                                              const rcc::MachineFunction &,
+                                              const rcc::TargetDescription &) const override {
+    return {};
+  }
+
+  [[nodiscard]] rcc::Expected<void> select(rcc::MachineInstr &Instruction, rcc::MachineFunction &,
+                                           const rcc::TargetDescription &) const override {
+    ++Selections;
+    if (Instruction.opcode() == rcc::opcode(rcc::GenericOpcode::G_ADD))
+      return Instruction.setOpcode(rcc::opcode(rcc::GenericOpcode::G_SUB));
+    if (Instruction.opcode() == rcc::opcode(rcc::GenericOpcode::G_SUB)) {
+      return Instruction.setOpcode(
+          rcc::Opcode::fromValue(static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADD)));
+    }
+    return rcc::makeUnexpected(rcc::ErrorCode::Unsupported,
+                               "two-step selector received an unexpected opcode");
+  }
+
+  [[nodiscard]] std::size_t selections() const noexcept {
+    return Selections;
+  }
+
+private:
+  mutable std::size_t Selections = 0;
+};
+
+void testPipeline(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  auto Fixture = createFixture(Context, "pipeline_success", 2);
+  Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr,
+                 "pipeline success fixture must be complete");
+  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
+    return;
+
+  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Result = createRegister(Context, *Fixture.Function, 64);
+  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
+  Context.expect(Builder.setInsertPoint(*Fixture.Entry).has_value(),
+                 "pipeline insertion point must be valid");
+  if (Left.isNoRegister() || Right.isNoRegister() || Result.isNoRegister() ||
+      !buildConstant(Context, Builder, Left, 42) || !buildConstant(Context, Builder, Right, 1) ||
+      !buildAdd(Context, Builder, Result, Left, Right))
+    return;
+
+  Fixture.Function->properties() = {rcc::MachineFunctionProperty::IsSSA,
+                                    rcc::MachineFunctionProperty::TracksLiveness};
+  rcc::MachinePassManager Pipeline;
+  Context.expect(
+      Pipeline.addPass(std::make_unique<rcc::Legalizer>(rcc::riscv::legalizerInfo())).has_value(),
+      "legalizer must be accepted by the pass manager");
+  Context.expect(
+      Pipeline.addPass(std::make_unique<rcc::RegBankSelect>(rcc::riscv::registerBankInfo()))
+          .has_value(),
+      "register-bank selector must be accepted by the pass manager");
+  Context.expect(
+      Pipeline.addPass(std::make_unique<rcc::InstructionSelect>(rcc::riscv::instructionSelector()))
+          .has_value(),
+      "instruction selector must be accepted by the pass manager");
+  rcc::MachineAnalysisManager Analyses;
+  auto Run = Pipeline.run(*Fixture.Function, *Target, Analyses);
+  Context.expect(Run.has_value(), "RV64GC generic pipeline must complete");
+  Context.expect(Fixture.Function->properties().has(rcc::MachineFunctionProperty::Selected),
+                 "successful instruction selection must publish Selected");
+  Context.expect(Fixture.Function->firstBlock()->firstInstruction() != nullptr,
+                 "selected instructions must remain attached to their block");
+  for (const rcc::MachineInstr *Instruction : Fixture.Function->allInstructions())
+    Context.expect(!rcc::isGenericOpcode(Instruction->opcode()),
+                   "successful instruction selection must remove generic opcodes");
+}
+
+void testInstructionSelectionTransaction(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  auto Fixture = createFixture(Context, "pipeline_selection_transaction", 8);
+  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Result = createRegister(Context, *Fixture.Function, 64);
+  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
+  if (Left.isNoRegister() || Right.isNoRegister() || Result.isNoRegister() ||
+      !Builder.setInsertPoint(*Fixture.Entry) || !buildAdd(Context, Builder, Result, Left, Right) ||
+      !assignGPR(*Fixture.Function, Left) || !assignGPR(*Fixture.Function, Right) ||
+      !assignGPR(*Fixture.Function, Result)) {
+    return;
+  }
+  rcc::MachineInstr *Original = Fixture.Entry->firstInstruction();
+  if (Original == nullptr)
+    return;
+  const rcc::Opcode OriginalOpcode = Original->opcode();
+  const std::size_t OriginalOperandCount = Original->operandCount();
+  Fixture.Function->properties() = {rcc::MachineFunctionProperty::Legalized,
+                                    rcc::MachineFunctionProperty::RegBankSelected};
+  MutatingFailingSelector Selector;
+  rcc::InstructionSelect Pass(Selector);
+  rcc::MachineAnalysisManager Analyses;
+  auto Run = Pass.run(*Fixture.Function, *Target, Analyses);
+  Context.expect(!Run && Run.error().code() == rcc::ErrorCode::Unsupported,
+                 "a renderer failure must be reported before publication");
+  Context.expect(Original->opcode() == OriginalOpcode &&
+                     Original->operandCount() == OriginalOperandCount &&
+                     Fixture.Entry->instructionCount() == 1,
+                 "a renderer failure must leave the original MachineIR unchanged");
+}
+
+void testInstructionSelectionOrder(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  auto Fixture = createFixture(Context, "pipeline_selection_order", 9);
+  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Result = createRegister(Context, *Fixture.Function, 64);
+  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
+  if (Left.isNoRegister() || Right.isNoRegister() || Result.isNoRegister() ||
+      !Builder.setInsertPoint(*Fixture.Entry) || !buildConstant(Context, Builder, Left, 6) ||
+      !buildConstant(Context, Builder, Right, 7) ||
+      !buildAdd(Context, Builder, Result, Left, Right) || !assignGPR(*Fixture.Function, Left) ||
+      !assignGPR(*Fixture.Function, Right) || !assignGPR(*Fixture.Function, Result)) {
+    return;
+  }
+  std::vector<std::uint64_t> LayoutIDs;
+  for (const rcc::MachineInstr *Instruction = Fixture.Entry->firstInstruction();
+       Instruction != nullptr; Instruction = Instruction->next()) {
+    LayoutIDs.push_back(Instruction->stableID().value());
+  }
+  Fixture.Function->properties() = {rcc::MachineFunctionProperty::Legalized,
+                                    rcc::MachineFunctionProperty::RegBankSelected};
+  RecordingSelector Selector(rcc::riscv::instructionSelector());
+  rcc::InstructionSelect Pass(Selector);
+  rcc::MachineAnalysisManager Analyses;
+  auto Run = Pass.run(*Fixture.Function, *Target, Analyses);
+  Context.expect(Run.has_value(), "recorded instruction selection must complete");
+  std::ranges::reverse(LayoutIDs);
+  std::vector<std::uint64_t> Expected = LayoutIDs;
+  Expected.insert(Expected.end(), LayoutIDs.begin(), LayoutIDs.end());
+  Context.expect(
+      Selector.selectedIDs() == Expected,
+      "instruction selection must use stable block-postorder and reverse instruction order");
+}
+
+void testInstructionSelectionWorklist(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  auto Fixture = createFixture(Context, "pipeline_selection_worklist", 10);
+  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Result = createRegister(Context, *Fixture.Function, 64);
+  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
+  if (Left.isNoRegister() || Right.isNoRegister() || Result.isNoRegister() ||
+      !Builder.setInsertPoint(*Fixture.Entry) || !buildAdd(Context, Builder, Result, Left, Right) ||
+      !assignGPR(*Fixture.Function, Left) || !assignGPR(*Fixture.Function, Right) ||
+      !assignGPR(*Fixture.Function, Result)) {
+    return;
+  }
+  Fixture.Function->properties() = {rcc::MachineFunctionProperty::Legalized,
+                                    rcc::MachineFunctionProperty::RegBankSelected};
+  TwoStepSelector Selector;
+  rcc::InstructionSelect Pass(Selector);
+  rcc::MachineAnalysisManager Analyses;
+  auto Run = Pass.run(*Fixture.Function, *Target, Analyses);
+  Context.expect(Run.has_value(), "a progressing multi-step selection must complete");
+  Context.expect(Selector.selections() == 4,
+                 "transaction preflight and publication must each select both generic states");
+  Context.expect(Fixture.Entry->firstInstruction() != nullptr &&
+                     Fixture.Entry->firstInstruction()->opcode() ==
+                         rcc::Opcode::fromValue(
+                             static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADD)),
+                 "the selection worklist must revisit a progressing generic root");
+}
+
+void testExtendedRV64GCPipeline(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  auto Fixture = createFixture(Context, "pipeline_extended_rv64gc", 7);
+  Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr,
+                 "extended pipeline fixture must be complete");
+  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  auto I1 = rcc::LLT::makeInteger(1);
+  auto I64 = rcc::LLT::makeInteger(64);
+  auto Pointer = rcc::LLT::makePointer(0, 64);
+  if (!I1 || !I64 || !Pointer)
+    return;
+  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Condition =
+      Fixture.Function->registerInfo().createVirtualRegister(*I1).value_or(rcc::Register{});
+  const rcc::Register Selected = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Sum = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Overflow =
+      Fixture.Function->registerInfo().createVirtualRegister(*I1).value_or(rcc::Register{});
+  const rcc::Register Quotient = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Remainder = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Address =
+      Fixture.Function->registerInfo().createVirtualRegister(*Pointer).value_or(rcc::Register{});
+  const rcc::Register AtomicResult = createRegister(Context, *Fixture.Function, 64);
+  const std::array Registers{Left,     Right,    Condition, Selected, Sum,
+                             Overflow, Quotient, Remainder, Address,  AtomicResult};
+  if (std::ranges::any_of(Registers, [](rcc::Register Reg) { return Reg.isNoRegister(); }))
+    return;
+  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
+  if (!Builder.setInsertPoint(*Fixture.Entry) || !buildConstant(Context, Builder, Left, 41) ||
+      !buildConstant(Context, Builder, Right, 7)) {
+    return;
+  }
+  auto Compare = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_ICMP));
+  if (!Compare || !Compare->addDef(Condition) ||
+      !Compare->addIntegerPredicate(rcc::IntegerPredicate::UnsignedGreaterThan) ||
+      !Compare->addUse(Left) || !Compare->addUse(Right) || !Compare->build()) {
+    return;
+  }
+  auto Select = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_SELECT));
+  if (!Select || !Select->addDef(Selected) || !Select->addUse(Condition) || !Select->addUse(Left) ||
+      !Select->addUse(Right) || !Select->build()) {
+    return;
+  }
+  auto AddOverflow = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_UADDO));
+  if (!AddOverflow || !AddOverflow->addDef(Sum) || !AddOverflow->addDef(Overflow) ||
+      !AddOverflow->addUse(Left) || !AddOverflow->addUse(Right) || !AddOverflow->build()) {
+    return;
+  }
+  auto DivRem = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_SDIVREM));
+  if (!DivRem || !DivRem->addDef(Quotient) || !DivRem->addDef(Remainder) || !DivRem->addUse(Left) ||
+      !DivRem->addUse(Right) || !DivRem->build()) {
+    return;
+  }
+  auto AddressDefinition = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_IMPLICIT_DEF));
+  if (!AddressDefinition || !AddressDefinition->addDef(Address) || !AddressDefinition->build())
+    return;
+  auto Size = rcc::MemorySize::fixed(8);
+  auto Align = rcc::Alignment::create(8);
+  if (!Size || !Align)
+    return;
+  rcc::MachineMemOperandDesc Description;
+  Description.Accesses = {rcc::MemoryAccessFlag::Load, rcc::MemoryAccessFlag::Store};
+  Description.AtomicKind = rcc::AtomicOperation::ReadModifyWrite;
+  Description.SuccessOrdering = rcc::AtomicOrdering::SequentiallyConsistent;
+  Description.Size = *Size;
+  Description.Align = *Align;
+  Description.Base = rcc::MemoryBase::stack();
+  auto Memory = Fixture.Function->createMemOperand(std::move(Description));
+  if (!Memory)
+    return;
+  auto Atomic = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_ATOMICRMW_ADD));
+  if (!Atomic || !Atomic->addDef(AtomicResult) || !Atomic->addUse(Address) ||
+      !Atomic->addUse(Selected) || !Atomic->addMemOperand(**Memory) || !Atomic->build()) {
+    return;
+  }
+
+  Fixture.Function->properties() = {rcc::MachineFunctionProperty::IsSSA,
+                                    rcc::MachineFunctionProperty::TracksLiveness};
+  rcc::MachinePassManager Pipeline;
+  if (!Pipeline.addPass(std::make_unique<rcc::Legalizer>(rcc::riscv::legalizerInfo())) ||
+      !Pipeline.addPass(std::make_unique<rcc::RegBankSelect>(rcc::riscv::registerBankInfo())) ||
+      !Pipeline.addPass(
+          std::make_unique<rcc::InstructionSelect>(rcc::riscv::instructionSelector()))) {
+    Context.expect(false, "extended RV64GC pipeline construction must succeed");
+    return;
+  }
+  rcc::MachineAnalysisManager Analyses;
+  auto Run = Pipeline.run(*Fixture.Function, *Target, Analyses);
+  Context.expect(Run.has_value(), "extended RV64GC pipeline must complete");
+  Context.expect(Run && Fixture.Function->properties().has(rcc::MachineFunctionProperty::Selected),
+                 "extended pipeline must publish Selected");
+  for (const rcc::MachineInstr *Instruction : Fixture.Function->allInstructions()) {
+    Context.expect(!rcc::isGenericOpcode(Instruction->opcode()),
+                   "extended pipeline must eliminate every generic opcode");
+    Context.expect(
+        Target->validateInstruction(*Instruction, Fixture.Function->registerInfo()).has_value(),
+        "extended pipeline output must satisfy target descriptors");
+  }
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  testPipeline(Context);
+  testInstructionSelectionTransaction(Context);
+  testInstructionSelectionOrder(Context);
+  testInstructionSelectionWorklist(Context);
+  testExtendedRV64GCPipeline(Context);
+  return Context.result();
+}
diff --git a/backend/unittests/CodeGen/GlobalISel/LegalizerTest.cpp b/backend/unittests/CodeGen/GlobalISel/LegalizerTest.cpp
new file mode 100644
index 0000000..6280182
--- /dev/null
+++ b/backend/unittests/CodeGen/GlobalISel/LegalizerTest.cpp
@@ -0,0 +1,205 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/Legalizer.h"
+
+#include "GISelMITest.h"
+#include "rcc/Target/RISCV/RISCVCodeGen.h"
+
+#include <cstdint>
+#include <memory>
+#include <string>
+
+namespace {
+
+using rcc::test::buildAdd;
+using rcc::test::createFixture;
+using rcc::test::createFloatRegister;
+using rcc::test::createRegister;
+using rcc::test::TestContext;
+
+class TogglingLegalizer final : public rcc::LegalizerInfo {
+public:
+  [[nodiscard]] rcc::Expected<rcc::LegalizationAction>
+  classify(const rcc::MachineInstr &, const rcc::MachineFunction &,
+           const rcc::TargetDescription &) const override {
+    return rcc::LegalizationAction::Lower;
+  }
+
+  [[nodiscard]] rcc::Expected<void> lower(rcc::MachineInstr &Instruction, rcc::MachineFunction &,
+                                          const rcc::TargetDescription &,
+                                          rcc::LegalizationAction) const override {
+    const auto Generic = static_cast<rcc::GenericOpcode>(Instruction.opcode().value());
+    return Instruction.setOpcode(rcc::opcode(Generic == rcc::GenericOpcode::G_ADD
+                                                 ? rcc::GenericOpcode::G_SUB
+                                                 : rcc::GenericOpcode::G_ADD));
+  }
+};
+
+class BackwardInvalidatingLegalizer final : public rcc::LegalizerInfo {
+public:
+  [[nodiscard]] rcc::Expected<rcc::LegalizationAction>
+  classify(const rcc::MachineInstr &Instruction, const rcc::MachineFunction &,
+           const rcc::TargetDescription &) const override {
+    return Instruction.opcode() == rcc::opcode(rcc::GenericOpcode::G_SUB)
+               ? rcc::LegalizationAction::Custom
+               : rcc::LegalizationAction::Legal;
+  }
+
+  [[nodiscard]] rcc::Expected<void> lower(rcc::MachineInstr &Instruction,
+                                          rcc::MachineFunction &Function,
+                                          const rcc::TargetDescription &,
+                                          rcc::LegalizationAction) const override {
+    for (rcc::MachineInstr *Candidate : Function.allInstructions()) {
+      if (Candidate != &Instruction &&
+          Candidate->opcode() == rcc::opcode(rcc::GenericOpcode::G_ADD)) {
+        auto Invalidated = Candidate->setOpcode(rcc::opcode(rcc::GenericOpcode::G_SUB));
+        if (!Invalidated)
+          return std::unexpected(Invalidated.error());
+        break;
+      }
+    }
+    return Instruction.setOpcode(
+        rcc::Opcode::fromValue(static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADD)));
+  }
+};
+
+void testNullAndMissingContracts(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  auto Fixture = createFixture(Context, "pipeline_contracts", 1);
+  Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr,
+                 "pipeline contract fixture must be complete");
+  if (!Target || !Fixture.Function)
+    return;
+
+  rcc::Legalizer NullPass(nullptr);
+  rcc::MachineAnalysisManager Analyses;
+  auto NullResult = NullPass.run(*Fixture.Function, *Target, Analyses);
+  Context.expect(!NullResult && NullResult.error().code() == rcc::ErrorCode::InvalidArgument,
+                 "a null legalizer interface must be rejected");
+  Context.expect(Fixture.Function->properties().empty(),
+                 "a rejected pass must not publish function properties");
+
+  rcc::Legalizer ValidPass(rcc::riscv::legalizerInfo());
+  auto MissingResult = ValidPass.run(*Fixture.Function, *Target, Analyses);
+  Context.expect(!MissingResult &&
+                     MissingResult.error().code() == rcc::ErrorCode::VerificationError,
+                 "a pass with missing prerequisites must be rejected");
+}
+
+void testUnsupportedRollback(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  if (!Target)
+    return;
+  auto Unsupported = createFixture(Context, "pipeline_unsupported", 3);
+  Context.expect(Unsupported.Function != nullptr && Unsupported.Entry != nullptr,
+                 "unsupported pipeline fixture must be complete");
+  if (!Unsupported.Function || Unsupported.Entry == nullptr)
+    return;
+  const rcc::Register UnsupportedReg = createFloatRegister(Context, *Unsupported.Function);
+  const rcc::Register UnsupportedSource = createFloatRegister(Context, *Unsupported.Function);
+  rcc::MachineIRBuilder UnsupportedBuilder(*Unsupported.Function, *Target);
+  Context.expect(UnsupportedBuilder.setInsertPoint(*Unsupported.Entry).has_value(),
+                 "unsupported pipeline insertion point must be valid");
+  if (UnsupportedReg.isNoRegister() || UnsupportedSource.isNoRegister())
+    return;
+  auto Pending = UnsupportedBuilder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_FEXP));
+  Context.expect(Pending.has_value(), "unsupported generic instruction must be constructible");
+  if (!Pending)
+    return;
+  auto Built = Pending->addDef(UnsupportedReg);
+  Context.expect(Built.has_value(), "unsupported generic definition must be accepted");
+  if (!Built)
+    return;
+  Context.expect(Pending->addUse(UnsupportedSource).has_value() && Pending->build().has_value(),
+                 "unsupported floating operation must be constructible");
+  Unsupported.Function->properties() = {rcc::MachineFunctionProperty::IsSSA,
+                                        rcc::MachineFunctionProperty::TracksLiveness};
+  rcc::MachinePassManager OnlyLegalizer;
+  Context.expect(
+      OnlyLegalizer.addPass(std::make_unique<rcc::Legalizer>(rcc::riscv::legalizerInfo()))
+          .has_value(),
+      "standalone legalizer must be accepted");
+  rcc::MachineAnalysisManager UnsupportedAnalyses;
+  auto Failure = OnlyLegalizer.run(*Unsupported.Function, *Target, UnsupportedAnalyses);
+  Context.expect(!Failure && Failure.error().code() == rcc::ErrorCode::Unsupported,
+                 "unsupported generic instructions must produce a target diagnostic");
+  Context.expect(!Failure && Failure.error().message().find("G_FEXP") != std::string::npos,
+                 "unsupported legalization diagnostics must name the rejected opcode");
+  Context.expect(
+      Unsupported.Function->properties().has(rcc::MachineFunctionProperty::IsSSA) &&
+          !Unsupported.Function->properties().has(rcc::MachineFunctionProperty::Legalized),
+      "failed legalizer execution must not publish Legalized");
+}
+
+void testLegalizerCycleDiagnostic(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  auto Fixture = createFixture(Context, "pipeline_legalizer_cycle", 6);
+  Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr,
+                 "legalizer cycle fixture must be complete");
+  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Result = createRegister(Context, *Fixture.Function, 64);
+  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
+  if (Left.isNoRegister() || Right.isNoRegister() || Result.isNoRegister() ||
+      !Builder.setInsertPoint(*Fixture.Entry) || !buildAdd(Context, Builder, Result, Left, Right))
+    return;
+  Fixture.Function->properties() = {rcc::MachineFunctionProperty::IsSSA,
+                                    rcc::MachineFunctionProperty::TracksLiveness};
+  TogglingLegalizer Legalizer;
+  rcc::Legalizer StablePass(Legalizer);
+  rcc::MachineAnalysisManager Analyses;
+  auto ResultRun = StablePass.run(*Fixture.Function, *Target, Analyses);
+  Context.expect(!ResultRun && ResultRun.error().code() == rcc::ErrorCode::InternalError,
+                 "repeated legalization states must report InternalError");
+  Context.expect(Fixture.Entry->firstInstruction() != nullptr &&
+                     Fixture.Entry->firstInstruction()->opcode() ==
+                         rcc::opcode(rcc::GenericOpcode::G_ADD),
+                 "failed legalization preflight must preserve the original instruction");
+  Context.expect(!Fixture.Function->properties().has(rcc::MachineFunctionProperty::Legalized),
+                 "a failed legalization cycle must not publish Legalized");
+}
+
+void testLegalizerRevisitsInvalidatedInstructions(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  auto Fixture = createFixture(Context, "pipeline_legalizer_revisit", 7);
+  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register FirstResult = createRegister(Context, *Fixture.Function, 64);
+  const rcc::Register SecondResult = createRegister(Context, *Fixture.Function, 64);
+  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
+  if (Left.isNoRegister() || Right.isNoRegister() || FirstResult.isNoRegister() ||
+      SecondResult.isNoRegister() || !Builder.setInsertPoint(*Fixture.Entry) ||
+      !buildAdd(Context, Builder, FirstResult, Left, Right) ||
+      !buildAdd(Context, Builder, SecondResult, Left, Right))
+    return;
+  rcc::MachineInstr *First = Fixture.Entry->firstInstruction();
+  rcc::MachineInstr *Second = First == nullptr ? nullptr : First->next();
+  if (Second == nullptr || !Second->setOpcode(rcc::opcode(rcc::GenericOpcode::G_SUB)))
+    return;
+
+  Fixture.Function->properties() = {rcc::MachineFunctionProperty::IsSSA,
+                                    rcc::MachineFunctionProperty::TracksLiveness};
+  BackwardInvalidatingLegalizer Legalizer;
+  rcc::Legalizer Pass(Legalizer);
+  rcc::MachineAnalysisManager Analyses;
+  auto Run = Pass.run(*Fixture.Function, *Target, Analyses);
+  const rcc::Opcode LegalOpcode =
+      rcc::Opcode::fromValue(static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADD));
+  Context.expect(Run && First->opcode() == LegalOpcode && Second->opcode() == LegalOpcode,
+                 "legalizer must revisit an earlier instruction invalidated by a later lowering");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  testNullAndMissingContracts(Context);
+  testUnsupportedRollback(Context);
+  testLegalizerCycleDiagnostic(Context);
+  testLegalizerRevisitsInvalidatedInstructions(Context);
+  return Context.result();
+}
diff --git a/backend/unittests/CodeGen/GlobalISel/RegBankSelectTest.cpp b/backend/unittests/CodeGen/GlobalISel/RegBankSelectTest.cpp
new file mode 100644
index 0000000..3cfa888
--- /dev/null
+++ b/backend/unittests/CodeGen/GlobalISel/RegBankSelectTest.cpp
@@ -0,0 +1,88 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/RegBankSelect.h"
+
+#include "GISelMITest.h"
+#include "rcc/Target/RISCV/RISCVCodeGen.h"
+
+#include <cstdint>
+
+namespace {
+
+using rcc::test::buildConstant;
+using rcc::test::createFixture;
+using rcc::test::createRegister;
+using rcc::test::TestContext;
+
+void testBankConflict(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  auto Fixture = createFixture(Context, "pipeline_bank_conflict", 4);
+  Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr,
+                 "bank conflict fixture must be complete");
+  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  const rcc::Register Value = createRegister(Context, *Fixture.Function, 64);
+  Context.expect(
+      Fixture.Function->registerInfo()
+          .setRegisterBank(Value, rcc::RegisterBankID::fromValue(
+                                      static_cast<std::uint32_t>(rcc::riscv::RegisterBank::FPR)))
+          .has_value(),
+      "conflicting bank assignment must be constructible");
+  Fixture.Function->properties() = {rcc::MachineFunctionProperty::Legalized};
+  rcc::RegBankSelect Pass(rcc::riscv::registerBankInfo());
+  rcc::MachineAnalysisManager Analyses;
+  auto Result = Pass.run(*Fixture.Function, *Target, Analyses);
+  Context.expect(!Result && Result.error().code() == rcc::ErrorCode::VerificationError,
+                 "bank selection must reject a conflicting pre-existing bank");
+  auto Info = Fixture.Function->registerInfo().virtualRegisterInfo(Value);
+  Context.expect(Info && Info->get().Bank, "failed bank selection must preserve a bank assignment");
+  if (!Info || !Info->get().Bank)
+    return;
+  const rcc::RegisterBankID Bank = Info->get().Bank.value_or(rcc::RegisterBankID{});
+  Context.expect(Bank == rcc::RegisterBankID::fromValue(
+                             static_cast<std::uint32_t>(rcc::riscv::RegisterBank::FPR)),
+                 "failed bank selection must preserve the original bank assignment");
+}
+
+void testBankClassOnlyChange(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  auto Fixture = createFixture(Context, "pipeline_bank_class", 5);
+  Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr,
+                 "bank class fixture must be complete");
+  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  const rcc::Register Value = createRegister(Context, *Fixture.Function, 64);
+  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
+  if (Value.isNoRegister() || !Builder.setInsertPoint(*Fixture.Entry) ||
+      !buildConstant(Context, Builder, Value, 7))
+    return;
+  const auto GPR =
+      rcc::RegisterBankID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterBank::GPR));
+  Context.expect(Fixture.Function->registerInfo().setRegisterBank(Value, GPR).has_value(),
+                 "pre-existing GPR bank must be assignable");
+  Fixture.Function->properties() = {rcc::MachineFunctionProperty::Legalized};
+  rcc::RegBankSelect Pass(rcc::riscv::registerBankInfo());
+  rcc::MachineAnalysisManager Analyses;
+  auto Result = Pass.run(*Fixture.Function, *Target, Analyses);
+  Context.expect(Result.has_value() && Result->Changed &&
+                     Result->Changes.has(rcc::MachinePassChange::Registers),
+                 "bank selection must report a class-only register change");
+  auto Info = Fixture.Function->registerInfo().virtualRegisterInfo(Value);
+  Context.expect(Info && Info->get().Bank && Info->get().RegClass,
+                 "bank selection must publish both bank and class");
+  if (!Info || !Info->get().RegClass)
+    return;
+  Context.expect(Info->get().RegClass.value_or(rcc::RegisterClassID{}) ==
+                     rcc::RegisterClassID::fromValue(
+                         static_cast<std::uint32_t>(rcc::riscv::RegisterClass::GPR)),
+                 "i64 GPR bank must select the GPR class");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  testBankConflict(Context);
+  testBankClassOnlyChange(Context);
+  return Context.result();
+}
diff --git a/backend/unittests/CodeGen/MachinePipelinePassesTest.cpp b/backend/unittests/CodeGen/MachinePipelinePassesTest.cpp
deleted file mode 100644
index 78c4cc7..0000000
--- a/backend/unittests/CodeGen/MachinePipelinePassesTest.cpp
+++ /dev/null
@@ -1,690 +0,0 @@
-// SPDX-License-Identifier: GPL-3.0-or-later
-
-#include "rcc/CodeGen/MachinePipelinePasses.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/MachineMemOperand.h"
-#include "rcc/CodeGen/MachineRegisterInfo.h"
-#include "rcc/Target/RISCV/RISCVCodeGen.h"
-#include "rcc/Target/RISCV/RISCVTarget.h"
-
-#include <algorithm>
-#include <array>
-#include <cstdint>
-#include <iostream>
-#include <memory>
-#include <ranges>
-#include <string>
-#include <string_view>
-#include <vector>
-
-namespace {
-
-class TestContext final {
-public:
-  void expect(bool Condition, std::string_view Message) {
-    if (Condition)
-      return;
-    std::cerr << Message << '\n';
-    ++Failures;
-  }
-
-  [[nodiscard]] int result() const noexcept {
-    return Failures == 0 ? 0 : 1;
-  }
-
-private:
-  int Failures = 0;
-};
-
-struct FunctionFixture final {
-  std::unique_ptr<rcc::MachineFunction> Function;
-  rcc::MachineBasicBlock *Entry = nullptr;
-};
-
-class TogglingLegalizer final : public rcc::TargetLegalizerInfo {
-public:
-  [[nodiscard]] rcc::Expected<rcc::LegalizationAction>
-  classify(const rcc::MachineInstr &, const rcc::MachineFunction &,
-           const rcc::TargetDescription &) const override {
-    return rcc::LegalizationAction::Lower;
-  }
-
-  [[nodiscard]] rcc::Expected<void> lower(rcc::MachineInstr &Instruction, rcc::MachineFunction &,
-                                          const rcc::TargetDescription &,
-                                          rcc::LegalizationAction) const override {
-    const auto Generic = static_cast<rcc::GenericOpcode>(Instruction.opcode().value());
-    return Instruction.setOpcode(rcc::opcode(Generic == rcc::GenericOpcode::G_ADD
-                                                 ? rcc::GenericOpcode::G_SUB
-                                                 : rcc::GenericOpcode::G_ADD));
-  }
-};
-
-class BackwardInvalidatingLegalizer final : public rcc::TargetLegalizerInfo {
-public:
-  [[nodiscard]] rcc::Expected<rcc::LegalizationAction>
-  classify(const rcc::MachineInstr &Instruction, const rcc::MachineFunction &,
-           const rcc::TargetDescription &) const override {
-    return Instruction.opcode() == rcc::opcode(rcc::GenericOpcode::G_SUB)
-               ? rcc::LegalizationAction::Custom
-               : rcc::LegalizationAction::Legal;
-  }
-
-  [[nodiscard]] rcc::Expected<void> lower(rcc::MachineInstr &Instruction,
-                                          rcc::MachineFunction &Function,
-                                          const rcc::TargetDescription &,
-                                          rcc::LegalizationAction) const override {
-    for (rcc::MachineInstr *Candidate : Function.allInstructions()) {
-      if (Candidate != &Instruction &&
-          Candidate->opcode() == rcc::opcode(rcc::GenericOpcode::G_ADD)) {
-        auto Invalidated = Candidate->setOpcode(rcc::opcode(rcc::GenericOpcode::G_SUB));
-        if (!Invalidated)
-          return std::unexpected(Invalidated.error());
-        break;
-      }
-    }
-    return Instruction.setOpcode(
-        rcc::Opcode::fromValue(static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADD)));
-  }
-};
-
-class MutatingFailingSelector final : public rcc::TargetInstructionSelector {
-public:
-  [[nodiscard]] rcc::Expected<void> canSelect(const rcc::MachineInstr &,
-                                              const rcc::MachineFunction &,
-                                              const rcc::TargetDescription &) const override {
-    return {};
-  }
-
-  [[nodiscard]] rcc::Expected<void> select(rcc::MachineInstr &Instruction, rcc::MachineFunction &,
-                                           const rcc::TargetDescription &) const override {
-    auto Mutation = Instruction.setOpcode(rcc::opcode(rcc::GenericOpcode::G_SUB));
-    if (!Mutation)
-      return std::unexpected(Mutation.error());
-    return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, "test selector rejected its renderer");
-  }
-};
-
-class RecordingSelector final : public rcc::TargetInstructionSelector {
-public:
-  explicit RecordingSelector(const rcc::TargetInstructionSelector &Delegate)
-      : Delegate(&Delegate) {}
-
-  [[nodiscard]] rcc::Expected<void> canSelect(const rcc::MachineInstr &Instruction,
-                                              const rcc::MachineFunction &Function,
-                                              const rcc::TargetDescription &Target) const override {
-    return Delegate->canSelect(Instruction, Function, Target);
-  }
-
-  [[nodiscard]] rcc::Expected<void> select(rcc::MachineInstr &Instruction,
-                                           rcc::MachineFunction &Function,
-                                           const rcc::TargetDescription &Target) const override {
-    SelectedIDs.push_back(Instruction.stableID().value());
-    return Delegate->select(Instruction, Function, Target);
-  }
-
-  [[nodiscard]] const std::vector<std::uint64_t> &selectedIDs() const noexcept {
-    return SelectedIDs;
-  }
-
-private:
-  const rcc::TargetInstructionSelector *Delegate;
-  mutable std::vector<std::uint64_t> SelectedIDs;
-};
-
-class TwoStepSelector final : public rcc::TargetInstructionSelector {
-public:
-  [[nodiscard]] rcc::Expected<void> canSelect(const rcc::MachineInstr &,
-                                              const rcc::MachineFunction &,
-                                              const rcc::TargetDescription &) const override {
-    return {};
-  }
-
-  [[nodiscard]] rcc::Expected<void> select(rcc::MachineInstr &Instruction, rcc::MachineFunction &,
-                                           const rcc::TargetDescription &) const override {
-    ++Selections;
-    if (Instruction.opcode() == rcc::opcode(rcc::GenericOpcode::G_ADD))
-      return Instruction.setOpcode(rcc::opcode(rcc::GenericOpcode::G_SUB));
-    if (Instruction.opcode() == rcc::opcode(rcc::GenericOpcode::G_SUB)) {
-      return Instruction.setOpcode(
-          rcc::Opcode::fromValue(static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADD)));
-    }
-    return rcc::makeUnexpected(rcc::ErrorCode::Unsupported,
-                               "two-step selector received an unexpected opcode");
-  }
-
-  [[nodiscard]] std::size_t selections() const noexcept {
-    return Selections;
-  }
-
-private:
-  mutable std::size_t Selections = 0;
-};
-
-[[nodiscard]] FunctionFixture createFixture(TestContext &Context, std::string_view Name,
-                                            std::uint64_t ID) {
-  auto Function =
-      rcc::MachineFunction::create(std::string(Name), rcc::MachineFunctionStableID::fromValue(ID));
-  Context.expect(Function.has_value(), "machine pipeline function creation must succeed");
-  if (!Function)
-    return {};
-  auto Entry = (*Function)->createBasicBlock();
-  Context.expect(Entry.has_value(), "machine pipeline block creation must succeed");
-  if (!Entry || !(*Function)->appendBlock(**Entry))
-    return {};
-  return {std::move(*Function), *Entry};
-}
-
-[[nodiscard]] rcc::Register createRegister(TestContext &Context, rcc::MachineFunction &Function,
-                                           std::uint32_t Bits) {
-  auto Type = rcc::LLT::makeInteger(Bits);
-  Context.expect(Type.has_value(), "integer LLT construction must succeed");
-  if (!Type)
-    return {};
-  auto Reg = Function.registerInfo().createVirtualRegister(*Type);
-  Context.expect(Reg.has_value(), "virtual register construction must succeed");
-  return Reg ? *Reg : rcc::Register{};
-}
-
-[[nodiscard]] rcc::Register createFloatRegister(TestContext &Context,
-                                                rcc::MachineFunction &Function) {
-  auto Type = rcc::LLT::makeFloat(rcc::FloatSemantics::IEEEDouble);
-  Context.expect(Type.has_value(), "floating LLT construction must succeed");
-  if (!Type)
-    return {};
-  auto Reg = Function.registerInfo().createVirtualRegister(*Type);
-  Context.expect(Reg.has_value(), "floating virtual register construction must succeed");
-  return Reg ? *Reg : rcc::Register{};
-}
-
-[[nodiscard]] bool assignGPR(rcc::MachineFunction &Function, rcc::Register Reg) {
-  const auto Bank =
-      rcc::RegisterBankID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterBank::GPR));
-  const auto RegClass =
-      rcc::RegisterClassID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterClass::GPR));
-  return Function.registerInfo().setRegisterBank(Reg, Bank).has_value() &&
-         Function.registerInfo().setRegisterClass(Reg, RegClass).has_value();
-}
-
-[[nodiscard]] bool buildConstant(TestContext &Context, rcc::MachineIRBuilder &Builder,
-                                 rcc::Register Destination, std::int64_t Value) {
-  auto Pending = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_CONSTANT));
-  if (!Pending || !Pending->addDef(Destination) || !Pending->addImmediate(Value) ||
-      !Pending->build()) {
-    Context.expect(false, "generic constant construction must succeed");
-    return false;
-  }
-  return true;
-}
-
-[[nodiscard]] bool buildAdd(TestContext &Context, rcc::MachineIRBuilder &Builder,
-                            rcc::Register Destination, rcc::Register Left, rcc::Register Right) {
-  auto Pending = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_ADD));
-  if (!Pending || !Pending->addDef(Destination) || !Pending->addUse(Left) ||
-      !Pending->addUse(Right) || !Pending->build()) {
-    Context.expect(false, "generic add construction must succeed");
-    return false;
-  }
-  return true;
-}
-
-void testNullAndMissingContracts(TestContext &Context) {
-  auto Target = rcc::riscv::createTargetDescription();
-  auto Fixture = createFixture(Context, "pipeline_contracts", 1);
-  Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr,
-                 "pipeline contract fixture must be complete");
-  if (!Target || !Fixture.Function)
-    return;
-
-  rcc::LegalizerPass NullPass(nullptr);
-  rcc::MachineAnalysisManager Analyses;
-  auto NullResult = NullPass.run(*Fixture.Function, *Target, Analyses);
-  Context.expect(!NullResult && NullResult.error().code() == rcc::ErrorCode::InvalidArgument,
-                 "a null legalizer interface must be rejected");
-  Context.expect(Fixture.Function->properties().empty(),
-                 "a rejected pass must not publish function properties");
-
-  rcc::LegalizerPass ValidPass(rcc::riscv::legalizerInfo());
-  auto MissingResult = ValidPass.run(*Fixture.Function, *Target, Analyses);
-  Context.expect(!MissingResult &&
-                     MissingResult.error().code() == rcc::ErrorCode::VerificationError,
-                 "a pass with missing prerequisites must be rejected");
-}
-
-void testPipelineAndUnsupportedRollback(TestContext &Context) {
-  auto Target = rcc::riscv::createTargetDescription();
-  auto Fixture = createFixture(Context, "pipeline_success", 2);
-  Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr,
-                 "pipeline success fixture must be complete");
-  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
-    return;
-
-  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Result = createRegister(Context, *Fixture.Function, 64);
-  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
-  Context.expect(Builder.setInsertPoint(*Fixture.Entry).has_value(),
-                 "pipeline insertion point must be valid");
-  if (Left.isNoRegister() || Right.isNoRegister() || Result.isNoRegister() ||
-      !buildConstant(Context, Builder, Left, 42) || !buildConstant(Context, Builder, Right, 1) ||
-      !buildAdd(Context, Builder, Result, Left, Right))
-    return;
-
-  Fixture.Function->properties() = {rcc::MachineFunctionProperty::IsSSA,
-                                    rcc::MachineFunctionProperty::TracksLiveness};
-  rcc::MachinePassManager Pipeline;
-  Context.expect(Pipeline.addPass(std::make_unique<rcc::LegalizerPass>(rcc::riscv::legalizerInfo()))
-                     .has_value(),
-                 "legalizer must be accepted by the pass manager");
-  Context.expect(
-      Pipeline
-          .addPass(std::make_unique<rcc::RegisterBankSelectPass>(rcc::riscv::registerBankInfo()))
-          .has_value(),
-      "register-bank selector must be accepted by the pass manager");
-  Context.expect(
-      Pipeline
-          .addPass(std::make_unique<rcc::InstructionSelectPass>(rcc::riscv::instructionSelector()))
-          .has_value(),
-      "instruction selector must be accepted by the pass manager");
-  rcc::MachineAnalysisManager Analyses;
-  auto Run = Pipeline.run(*Fixture.Function, *Target, Analyses);
-  Context.expect(Run.has_value(), "RV64GC generic pipeline must complete");
-  Context.expect(Fixture.Function->properties().has(rcc::MachineFunctionProperty::Selected),
-                 "successful instruction selection must publish Selected");
-  Context.expect(Fixture.Function->firstBlock()->firstInstruction() != nullptr,
-                 "selected instructions must remain attached to their block");
-  for (const rcc::MachineInstr *Instruction : Fixture.Function->allInstructions())
-    Context.expect(!rcc::isGenericOpcode(Instruction->opcode()),
-                   "successful instruction selection must remove generic opcodes");
-
-  auto Unsupported = createFixture(Context, "pipeline_unsupported", 3);
-  Context.expect(Unsupported.Function != nullptr && Unsupported.Entry != nullptr,
-                 "unsupported pipeline fixture must be complete");
-  if (!Unsupported.Function || Unsupported.Entry == nullptr)
-    return;
-  const rcc::Register UnsupportedReg = createFloatRegister(Context, *Unsupported.Function);
-  const rcc::Register UnsupportedSource = createFloatRegister(Context, *Unsupported.Function);
-  rcc::MachineIRBuilder UnsupportedBuilder(*Unsupported.Function, *Target);
-  Context.expect(UnsupportedBuilder.setInsertPoint(*Unsupported.Entry).has_value(),
-                 "unsupported pipeline insertion point must be valid");
-  if (UnsupportedReg.isNoRegister() || UnsupportedSource.isNoRegister())
-    return;
-  auto Pending = UnsupportedBuilder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_FEXP));
-  Context.expect(Pending.has_value(), "unsupported generic instruction must be constructible");
-  if (!Pending)
-    return;
-  auto Built = Pending->addDef(UnsupportedReg);
-  Context.expect(Built.has_value(), "unsupported generic definition must be accepted");
-  if (!Built)
-    return;
-  Context.expect(Pending->addUse(UnsupportedSource).has_value() && Pending->build().has_value(),
-                 "unsupported floating operation must be constructible");
-  Unsupported.Function->properties() = {rcc::MachineFunctionProperty::IsSSA,
-                                        rcc::MachineFunctionProperty::TracksLiveness};
-  rcc::MachinePassManager OnlyLegalizer;
-  Context.expect(
-      OnlyLegalizer.addPass(std::make_unique<rcc::LegalizerPass>(rcc::riscv::legalizerInfo()))
-          .has_value(),
-      "standalone legalizer must be accepted");
-  rcc::MachineAnalysisManager UnsupportedAnalyses;
-  auto Failure = OnlyLegalizer.run(*Unsupported.Function, *Target, UnsupportedAnalyses);
-  Context.expect(!Failure && Failure.error().code() == rcc::ErrorCode::Unsupported,
-                 "unsupported generic instructions must produce a target diagnostic");
-  Context.expect(!Failure && Failure.error().message().find("G_FEXP") != std::string::npos,
-                 "unsupported legalization diagnostics must name the rejected opcode");
-  Context.expect(
-      Unsupported.Function->properties().has(rcc::MachineFunctionProperty::IsSSA) &&
-          !Unsupported.Function->properties().has(rcc::MachineFunctionProperty::Legalized),
-      "failed legalizer execution must not publish Legalized");
-}
-
-void testBankConflict(TestContext &Context) {
-  auto Target = rcc::riscv::createTargetDescription();
-  auto Fixture = createFixture(Context, "pipeline_bank_conflict", 4);
-  Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr,
-                 "bank conflict fixture must be complete");
-  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
-    return;
-  const rcc::Register Value = createRegister(Context, *Fixture.Function, 64);
-  Context.expect(
-      Fixture.Function->registerInfo()
-          .setRegisterBank(Value, rcc::RegisterBankID::fromValue(
-                                      static_cast<std::uint32_t>(rcc::riscv::RegisterBank::FPR)))
-          .has_value(),
-      "conflicting bank assignment must be constructible");
-  Fixture.Function->properties() = {rcc::MachineFunctionProperty::Legalized};
-  rcc::RegisterBankSelectPass Pass(rcc::riscv::registerBankInfo());
-  rcc::MachineAnalysisManager Analyses;
-  auto Result = Pass.run(*Fixture.Function, *Target, Analyses);
-  Context.expect(!Result && Result.error().code() == rcc::ErrorCode::VerificationError,
-                 "bank selection must reject a conflicting pre-existing bank");
-  auto Info = Fixture.Function->registerInfo().virtualRegisterInfo(Value);
-  Context.expect(Info && Info->get().Bank, "failed bank selection must preserve a bank assignment");
-  if (!Info || !Info->get().Bank)
-    return;
-  const rcc::RegisterBankID Bank = Info->get().Bank.value_or(rcc::RegisterBankID{});
-  Context.expect(Bank == rcc::RegisterBankID::fromValue(
-                             static_cast<std::uint32_t>(rcc::riscv::RegisterBank::FPR)),
-                 "failed bank selection must preserve the original bank assignment");
-}
-
-void testBankClassOnlyChange(TestContext &Context) {
-  auto Target = rcc::riscv::createTargetDescription();
-  auto Fixture = createFixture(Context, "pipeline_bank_class", 5);
-  Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr,
-                 "bank class fixture must be complete");
-  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
-    return;
-  const rcc::Register Value = createRegister(Context, *Fixture.Function, 64);
-  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
-  if (Value.isNoRegister() || !Builder.setInsertPoint(*Fixture.Entry) ||
-      !buildConstant(Context, Builder, Value, 7))
-    return;
-  const auto GPR =
-      rcc::RegisterBankID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterBank::GPR));
-  Context.expect(Fixture.Function->registerInfo().setRegisterBank(Value, GPR).has_value(),
-                 "pre-existing GPR bank must be assignable");
-  Fixture.Function->properties() = {rcc::MachineFunctionProperty::Legalized};
-  rcc::RegisterBankSelectPass Pass(rcc::riscv::registerBankInfo());
-  rcc::MachineAnalysisManager Analyses;
-  auto Result = Pass.run(*Fixture.Function, *Target, Analyses);
-  Context.expect(Result.has_value() && Result->Changed &&
-                     Result->Changes.has(rcc::MachinePassChange::Registers),
-                 "bank selection must report a class-only register change");
-  auto Info = Fixture.Function->registerInfo().virtualRegisterInfo(Value);
-  Context.expect(Info && Info->get().Bank && Info->get().RegClass,
-                 "bank selection must publish both bank and class");
-  if (!Info || !Info->get().RegClass)
-    return;
-  Context.expect(Info->get().RegClass.value_or(rcc::RegisterClassID{}) ==
-                     rcc::RegisterClassID::fromValue(
-                         static_cast<std::uint32_t>(rcc::riscv::RegisterClass::GPR)),
-                 "i64 GPR bank must select the GPR class");
-}
-
-void testLegalizerCycleDiagnostic(TestContext &Context) {
-  auto Target = rcc::riscv::createTargetDescription();
-  auto Fixture = createFixture(Context, "pipeline_legalizer_cycle", 6);
-  Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr,
-                 "legalizer cycle fixture must be complete");
-  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
-    return;
-  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Result = createRegister(Context, *Fixture.Function, 64);
-  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
-  if (Left.isNoRegister() || Right.isNoRegister() || Result.isNoRegister() ||
-      !Builder.setInsertPoint(*Fixture.Entry) || !buildAdd(Context, Builder, Result, Left, Right))
-    return;
-  Fixture.Function->properties() = {rcc::MachineFunctionProperty::IsSSA,
-                                    rcc::MachineFunctionProperty::TracksLiveness};
-  TogglingLegalizer Legalizer;
-  rcc::LegalizerPass StablePass(Legalizer);
-  rcc::MachineAnalysisManager Analyses;
-  auto ResultRun = StablePass.run(*Fixture.Function, *Target, Analyses);
-  Context.expect(!ResultRun && ResultRun.error().code() == rcc::ErrorCode::InternalError,
-                 "repeated legalization states must report InternalError");
-  Context.expect(Fixture.Entry->firstInstruction() != nullptr &&
-                     Fixture.Entry->firstInstruction()->opcode() ==
-                         rcc::opcode(rcc::GenericOpcode::G_ADD),
-                 "failed legalization preflight must preserve the original instruction");
-  Context.expect(!Fixture.Function->properties().has(rcc::MachineFunctionProperty::Legalized),
-                 "a failed legalization cycle must not publish Legalized");
-}
-
-void testLegalizerRevisitsInvalidatedInstructions(TestContext &Context) {
-  auto Target = rcc::riscv::createTargetDescription();
-  auto Fixture = createFixture(Context, "pipeline_legalizer_revisit", 7);
-  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
-    return;
-  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register FirstResult = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register SecondResult = createRegister(Context, *Fixture.Function, 64);
-  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
-  if (Left.isNoRegister() || Right.isNoRegister() || FirstResult.isNoRegister() ||
-      SecondResult.isNoRegister() || !Builder.setInsertPoint(*Fixture.Entry) ||
-      !buildAdd(Context, Builder, FirstResult, Left, Right) ||
-      !buildAdd(Context, Builder, SecondResult, Left, Right))
-    return;
-  rcc::MachineInstr *First = Fixture.Entry->firstInstruction();
-  rcc::MachineInstr *Second = First == nullptr ? nullptr : First->next();
-  if (Second == nullptr || !Second->setOpcode(rcc::opcode(rcc::GenericOpcode::G_SUB)))
-    return;
-
-  Fixture.Function->properties() = {rcc::MachineFunctionProperty::IsSSA,
-                                    rcc::MachineFunctionProperty::TracksLiveness};
-  BackwardInvalidatingLegalizer Legalizer;
-  rcc::LegalizerPass Pass(Legalizer);
-  rcc::MachineAnalysisManager Analyses;
-  auto Run = Pass.run(*Fixture.Function, *Target, Analyses);
-  const rcc::Opcode LegalOpcode =
-      rcc::Opcode::fromValue(static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADD));
-  Context.expect(Run && First->opcode() == LegalOpcode && Second->opcode() == LegalOpcode,
-                 "legalizer must revisit an earlier instruction invalidated by a later lowering");
-}
-
-void testInstructionSelectionTransaction(TestContext &Context) {
-  auto Target = rcc::riscv::createTargetDescription();
-  auto Fixture = createFixture(Context, "pipeline_selection_transaction", 8);
-  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
-    return;
-  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Result = createRegister(Context, *Fixture.Function, 64);
-  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
-  if (Left.isNoRegister() || Right.isNoRegister() || Result.isNoRegister() ||
-      !Builder.setInsertPoint(*Fixture.Entry) || !buildAdd(Context, Builder, Result, Left, Right) ||
-      !assignGPR(*Fixture.Function, Left) || !assignGPR(*Fixture.Function, Right) ||
-      !assignGPR(*Fixture.Function, Result)) {
-    return;
-  }
-  rcc::MachineInstr *Original = Fixture.Entry->firstInstruction();
-  if (Original == nullptr)
-    return;
-  const rcc::Opcode OriginalOpcode = Original->opcode();
-  const std::size_t OriginalOperandCount = Original->operandCount();
-  Fixture.Function->properties() = {rcc::MachineFunctionProperty::Legalized,
-                                    rcc::MachineFunctionProperty::RegBankSelected};
-  MutatingFailingSelector Selector;
-  rcc::InstructionSelectPass Pass(Selector);
-  rcc::MachineAnalysisManager Analyses;
-  auto Run = Pass.run(*Fixture.Function, *Target, Analyses);
-  Context.expect(!Run && Run.error().code() == rcc::ErrorCode::Unsupported,
-                 "a renderer failure must be reported before publication");
-  Context.expect(Original->opcode() == OriginalOpcode &&
-                     Original->operandCount() == OriginalOperandCount &&
-                     Fixture.Entry->instructionCount() == 1,
-                 "a renderer failure must leave the original MachineIR unchanged");
-}
-
-void testInstructionSelectionOrder(TestContext &Context) {
-  auto Target = rcc::riscv::createTargetDescription();
-  auto Fixture = createFixture(Context, "pipeline_selection_order", 9);
-  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
-    return;
-  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Result = createRegister(Context, *Fixture.Function, 64);
-  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
-  if (Left.isNoRegister() || Right.isNoRegister() || Result.isNoRegister() ||
-      !Builder.setInsertPoint(*Fixture.Entry) || !buildConstant(Context, Builder, Left, 6) ||
-      !buildConstant(Context, Builder, Right, 7) ||
-      !buildAdd(Context, Builder, Result, Left, Right) || !assignGPR(*Fixture.Function, Left) ||
-      !assignGPR(*Fixture.Function, Right) || !assignGPR(*Fixture.Function, Result)) {
-    return;
-  }
-  std::vector<std::uint64_t> LayoutIDs;
-  for (const rcc::MachineInstr *Instruction = Fixture.Entry->firstInstruction();
-       Instruction != nullptr; Instruction = Instruction->next()) {
-    LayoutIDs.push_back(Instruction->stableID().value());
-  }
-  Fixture.Function->properties() = {rcc::MachineFunctionProperty::Legalized,
-                                    rcc::MachineFunctionProperty::RegBankSelected};
-  RecordingSelector Selector(rcc::riscv::instructionSelector());
-  rcc::InstructionSelectPass Pass(Selector);
-  rcc::MachineAnalysisManager Analyses;
-  auto Run = Pass.run(*Fixture.Function, *Target, Analyses);
-  Context.expect(Run.has_value(), "recorded instruction selection must complete");
-  std::ranges::reverse(LayoutIDs);
-  std::vector<std::uint64_t> Expected = LayoutIDs;
-  Expected.insert(Expected.end(), LayoutIDs.begin(), LayoutIDs.end());
-  Context.expect(
-      Selector.selectedIDs() == Expected,
-      "instruction selection must use stable block-postorder and reverse instruction order");
-}
-
-void testInstructionSelectionWorklist(TestContext &Context) {
-  auto Target = rcc::riscv::createTargetDescription();
-  auto Fixture = createFixture(Context, "pipeline_selection_worklist", 10);
-  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
-    return;
-  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Result = createRegister(Context, *Fixture.Function, 64);
-  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
-  if (Left.isNoRegister() || Right.isNoRegister() || Result.isNoRegister() ||
-      !Builder.setInsertPoint(*Fixture.Entry) || !buildAdd(Context, Builder, Result, Left, Right) ||
-      !assignGPR(*Fixture.Function, Left) || !assignGPR(*Fixture.Function, Right) ||
-      !assignGPR(*Fixture.Function, Result)) {
-    return;
-  }
-  Fixture.Function->properties() = {rcc::MachineFunctionProperty::Legalized,
-                                    rcc::MachineFunctionProperty::RegBankSelected};
-  TwoStepSelector Selector;
-  rcc::InstructionSelectPass Pass(Selector);
-  rcc::MachineAnalysisManager Analyses;
-  auto Run = Pass.run(*Fixture.Function, *Target, Analyses);
-  Context.expect(Run.has_value(), "a progressing multi-step selection must complete");
-  Context.expect(Selector.selections() == 4,
-                 "transaction preflight and publication must each select both generic states");
-  Context.expect(Fixture.Entry->firstInstruction() != nullptr &&
-                     Fixture.Entry->firstInstruction()->opcode() ==
-                         rcc::Opcode::fromValue(
-                             static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADD)),
-                 "the selection worklist must revisit a progressing generic root");
-}
-
-void testExtendedRV64GCPipeline(TestContext &Context) {
-  auto Target = rcc::riscv::createTargetDescription();
-  auto Fixture = createFixture(Context, "pipeline_extended_rv64gc", 7);
-  Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr,
-                 "extended pipeline fixture must be complete");
-  if (!Target || !Fixture.Function || Fixture.Entry == nullptr)
-    return;
-  auto I1 = rcc::LLT::makeInteger(1);
-  auto I64 = rcc::LLT::makeInteger(64);
-  auto Pointer = rcc::LLT::makePointer(0, 64);
-  if (!I1 || !I64 || !Pointer)
-    return;
-  const rcc::Register Left = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Right = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Condition =
-      Fixture.Function->registerInfo().createVirtualRegister(*I1).value_or(rcc::Register{});
-  const rcc::Register Selected = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Sum = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Overflow =
-      Fixture.Function->registerInfo().createVirtualRegister(*I1).value_or(rcc::Register{});
-  const rcc::Register Quotient = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Remainder = createRegister(Context, *Fixture.Function, 64);
-  const rcc::Register Address =
-      Fixture.Function->registerInfo().createVirtualRegister(*Pointer).value_or(rcc::Register{});
-  const rcc::Register AtomicResult = createRegister(Context, *Fixture.Function, 64);
-  const std::array Registers{Left,     Right,    Condition, Selected, Sum,
-                             Overflow, Quotient, Remainder, Address,  AtomicResult};
-  if (std::ranges::any_of(Registers, [](rcc::Register Reg) { return Reg.isNoRegister(); }))
-    return;
-  rcc::MachineIRBuilder Builder(*Fixture.Function, *Target);
-  if (!Builder.setInsertPoint(*Fixture.Entry) || !buildConstant(Context, Builder, Left, 41) ||
-      !buildConstant(Context, Builder, Right, 7)) {
-    return;
-  }
-  auto Compare = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_ICMP));
-  if (!Compare || !Compare->addDef(Condition) ||
-      !Compare->addIntegerPredicate(rcc::IntegerPredicate::UnsignedGreaterThan) ||
-      !Compare->addUse(Left) || !Compare->addUse(Right) || !Compare->build()) {
-    return;
-  }
-  auto Select = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_SELECT));
-  if (!Select || !Select->addDef(Selected) || !Select->addUse(Condition) || !Select->addUse(Left) ||
-      !Select->addUse(Right) || !Select->build()) {
-    return;
-  }
-  auto AddOverflow = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_UADDO));
-  if (!AddOverflow || !AddOverflow->addDef(Sum) || !AddOverflow->addDef(Overflow) ||
-      !AddOverflow->addUse(Left) || !AddOverflow->addUse(Right) || !AddOverflow->build()) {
-    return;
-  }
-  auto DivRem = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_SDIVREM));
-  if (!DivRem || !DivRem->addDef(Quotient) || !DivRem->addDef(Remainder) || !DivRem->addUse(Left) ||
-      !DivRem->addUse(Right) || !DivRem->build()) {
-    return;
-  }
-  auto AddressDefinition = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_IMPLICIT_DEF));
-  if (!AddressDefinition || !AddressDefinition->addDef(Address) || !AddressDefinition->build())
-    return;
-  auto Size = rcc::MemorySize::fixed(8);
-  auto Align = rcc::Alignment::create(8);
-  if (!Size || !Align)
-    return;
-  rcc::MachineMemOperandDesc Description;
-  Description.Accesses = {rcc::MemoryAccessFlag::Load, rcc::MemoryAccessFlag::Store};
-  Description.AtomicKind = rcc::AtomicOperation::ReadModifyWrite;
-  Description.SuccessOrdering = rcc::AtomicOrdering::SequentiallyConsistent;
-  Description.Size = *Size;
-  Description.Align = *Align;
-  Description.Base = rcc::MemoryBase::stack();
-  auto Memory = Fixture.Function->createMemOperand(std::move(Description));
-  if (!Memory)
-    return;
-  auto Atomic = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_ATOMICRMW_ADD));
-  if (!Atomic || !Atomic->addDef(AtomicResult) || !Atomic->addUse(Address) ||
-      !Atomic->addUse(Selected) || !Atomic->addMemOperand(**Memory) || !Atomic->build()) {
-    return;
-  }
-
-  Fixture.Function->properties() = {rcc::MachineFunctionProperty::IsSSA,
-                                    rcc::MachineFunctionProperty::TracksLiveness};
-  rcc::MachinePassManager Pipeline;
-  if (!Pipeline.addPass(std::make_unique<rcc::LegalizerPass>(rcc::riscv::legalizerInfo())) ||
-      !Pipeline.addPass(
-          std::make_unique<rcc::RegisterBankSelectPass>(rcc::riscv::registerBankInfo())) ||
-      !Pipeline.addPass(
-          std::make_unique<rcc::InstructionSelectPass>(rcc::riscv::instructionSelector()))) {
-    Context.expect(false, "extended RV64GC pipeline construction must succeed");
-    return;
-  }
-  rcc::MachineAnalysisManager Analyses;
-  auto Run = Pipeline.run(*Fixture.Function, *Target, Analyses);
-  Context.expect(Run.has_value(), "extended RV64GC pipeline must complete");
-  Context.expect(Run && Fixture.Function->properties().has(rcc::MachineFunctionProperty::Selected),
-                 "extended pipeline must publish Selected");
-  for (const rcc::MachineInstr *Instruction : Fixture.Function->allInstructions()) {
-    Context.expect(!rcc::isGenericOpcode(Instruction->opcode()),
-                   "extended pipeline must eliminate every generic opcode");
-    Context.expect(
-        Target->validateInstruction(*Instruction, Fixture.Function->registerInfo()).has_value(),
-        "extended pipeline output must satisfy target descriptors");
-  }
-}
-
-} // namespace
-
-int main() {
-  TestContext Context;
-  testNullAndMissingContracts(Context);
-  testPipelineAndUnsupportedRollback(Context);
-  testBankConflict(Context);
-  testBankClassOnlyChange(Context);
-  testLegalizerCycleDiagnostic(Context);
-  testLegalizerRevisitsInvalidatedInstructions(Context);
-  testInstructionSelectionTransaction(Context);
-  testInstructionSelectionOrder(Context);
-  testInstructionSelectionWorklist(Context);
-  testExtendedRV64GCPipeline(Context);
-  return Context.result();
-}