[CodeGen] Split PHI elimination and two-address rewriting

6 files changed, 1221 insertions, 1187 deletions

diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt
index 3ae0f3d..7e79344 100644
--- a/backend/unittests/CodeGen/CMakeLists.txt
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -25,7 +25,8 @@ set(
   MachineSchedulingTest.cpp
   PBQPTest.cpp
   RegisterAllocationTest.cpp
-  MachineSSAExitTest.cpp
+  PHIEliminationTest.cpp
+  TwoAddressInstructionPassTest.cpp
   MachineVerifierTest.cpp
   MachineVerifierTargetTest.cpp
   MachineValueTypesTest.cpp
@@ -371,13 +372,30 @@ target_link_libraries(
 )
 add_test(NAME RCCBackend.CodeGen.MachineScheduling COMMAND RCCBackendCodeGenMachineSchedulingTests)
 
-add_executable(RCCBackendCodeGenMachineSSAExitTests MachineSSAExitTest.cpp)
-rcc_backend_configure_target(RCCBackendCodeGenMachineSSAExitTests)
+add_executable(RCCBackendCodeGenPHIEliminationTests PHIEliminationTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenPHIEliminationTests)
 target_link_libraries(
-  RCCBackendCodeGenMachineSSAExitTests
+  RCCBackendCodeGenPHIEliminationTests
   PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget
 )
-add_test(NAME RCCBackend.CodeGen.MachineSSAExit COMMAND RCCBackendCodeGenMachineSSAExitTests)
+add_test(
+  NAME RCCBackend.CodeGen.PHIElimination
+  COMMAND RCCBackendCodeGenPHIEliminationTests
+)
+
+add_executable(
+  RCCBackendCodeGenTwoAddressInstructionPassTests
+  TwoAddressInstructionPassTest.cpp
+)
+rcc_backend_configure_target(RCCBackendCodeGenTwoAddressInstructionPassTests)
+target_link_libraries(
+  RCCBackendCodeGenTwoAddressInstructionPassTests
+  PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget
+)
+add_test(
+  NAME RCCBackend.CodeGen.TwoAddressInstructionPass
+  COMMAND RCCBackendCodeGenTwoAddressInstructionPassTests
+)
 
 add_executable(RCCBackendCodeGenTargetConstantTests TargetConstantTest.cpp)
 rcc_backend_configure_target(RCCBackendCodeGenTargetConstantTests)
@@ -460,7 +478,9 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineSchedulingTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/PBQPTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegisterAllocationTest.cpp"
-  "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExitTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/PHIEliminationTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/SSAExitTestSupport.h"
+  "${CMAKE_CURRENT_SOURCE_DIR}/TwoAddressInstructionPassTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTargetTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
@@ -501,7 +521,9 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineSchedulingTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/PBQPTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegisterAllocationTest.cpp"
-  "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExitTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/PHIEliminationTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/SSAExitTestSupport.h"
+  "${CMAKE_CURRENT_SOURCE_DIR}/TwoAddressInstructionPassTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTargetTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
diff --git a/backend/unittests/CodeGen/MachineSSAExitTest.cpp b/backend/unittests/CodeGen/MachineSSAExitTest.cpp
deleted file mode 100644
index a5cc1c7..0000000
--- a/backend/unittests/CodeGen/MachineSSAExitTest.cpp
+++ /dev/null
@@ -1,1179 +0,0 @@
-// SPDX-License-Identifier: GPL-3.0-or-later
-
-#include "rcc/CodeGen/MachineSSAExit.h"
-
-#include "Target/TestTarget.h"
-#include "rcc/CodeGen/GenericOpcodes.h"
-#include "rcc/CodeGen/MachineBasicBlock.h"
-#include "rcc/CodeGen/MachineCFGUpdater.h"
-#include "rcc/CodeGen/MachineFunction.h"
-#include "rcc/CodeGen/MachineIRBuilder.h"
-#include "rcc/CodeGen/MachineInstr.h"
-#include "rcc/CodeGen/MachineLiveness.h"
-#include "rcc/CodeGen/MachineOperand.h"
-#include "rcc/CodeGen/MachinePass.h"
-#include "rcc/CodeGen/MachineRegisterInfo.h"
-#include "rcc/CodeGen/MachineVerifier.h"
-#include "rcc/CodeGen/TargetDescription.h"
-#include "rcc/CodeGen/TargetInstrInfo.h"
-
-#include <algorithm>
-#include <array>
-#include <cstddef>
-#include <cstdint>
-#include <iostream>
-#include <memory>
-#include <optional>
-#include <span>
-#include <string>
-#include <string_view>
-#include <utility>
-#include <vector>
-
-namespace {
-
-constexpr std::uint32_t DefOpcode = 1024;
-constexpr std::uint32_t UseOpcode = 1025;
-constexpr std::uint32_t ConditionalBranchOpcode = 1026;
-constexpr std::uint32_t JumpOpcode = 1027;
-constexpr std::uint32_t ReturnOpcode = 1028;
-constexpr std::uint32_t MetaOpcode = 1029;
-constexpr std::uint32_t TiedOpcode = 1030;
-constexpr std::uint32_t CommutableTiedOpcode = 1031;
-constexpr std::uint32_t ConvertibleTiedOpcode = 1032;
-constexpr std::uint32_t ThreeAddressOpcode = 1033;
-
-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;
-};
-
-[[nodiscard]] rcc::Opcode testOpcode(std::uint32_t Value) {
-  return rcc::Opcode::fromValue(Value);
-}
-
-[[nodiscard]] rcc::OperandDescriptor registerOperand(rcc::RegisterOperandRole Role,
-                                                     bool AllowSubReg = true) {
-  rcc::OperandDescriptor Result;
-  Result.Kinds = {rcc::MachineOperand::Kind::Register};
-  Result.RegisterRole = Role;
-  Result.AllowSubReg = AllowSubReg;
-  Result.AllowAnyTargetFlags = true;
-  return Result;
-}
-
-[[nodiscard]] rcc::OperandDescriptor blockOperand() {
-  rcc::OperandDescriptor Result;
-  Result.Kinds = {rcc::MachineOperand::Kind::BasicBlock};
-  return Result;
-}
-
-[[nodiscard]] rcc::InstructionDescriptor instruction(std::uint32_t Value, std::string Name) {
-  rcc::InstructionDescriptor Result;
-  Result.InstructionOpcode = testOpcode(Value);
-  Result.Name = std::move(Name);
-  Result.Flags = {rcc::InstructionFlag::ProducesCode};
-  return Result;
-}
-
-[[nodiscard]] rcc::Expected<rcc::TargetDescription> createTarget() {
-  std::vector<rcc::InstructionDescriptor> Descriptors;
-  std::vector<rcc::ImmediatePredicate> Predicates;
-  auto Generic = rcc::appendGenericInstructionInfo(Descriptors, Predicates);
-  if (!Generic)
-    return std::unexpected(Generic.error());
-
-  auto Def = instruction(DefOpcode, "TEST_DEF");
-  Def.Operands = {registerOperand(rcc::RegisterOperandRole::Def)};
-  Def.NumExplicitDefs = 1;
-  Descriptors.push_back(std::move(Def));
-
-  auto Use = instruction(UseOpcode, "TEST_USE");
-  Use.Operands = {registerOperand(rcc::RegisterOperandRole::Use)};
-  Descriptors.push_back(std::move(Use));
-
-  auto Conditional = instruction(ConditionalBranchOpcode, "TEST_BRCOND");
-  Conditional.Operands = {registerOperand(rcc::RegisterOperandRole::Use, false), blockOperand()};
-  Conditional.Flags.set(rcc::InstructionFlag::Branch);
-  Conditional.Flags.set(rcc::InstructionFlag::Terminator);
-  Descriptors.push_back(std::move(Conditional));
-
-  auto Jump = instruction(JumpOpcode, "TEST_JUMP");
-  Jump.Operands = {blockOperand()};
-  Jump.Flags.set(rcc::InstructionFlag::Branch);
-  Jump.Flags.set(rcc::InstructionFlag::Terminator);
-  Jump.Flags.set(rcc::InstructionFlag::Barrier);
-  Descriptors.push_back(std::move(Jump));
-
-  auto Return = instruction(ReturnOpcode, "TEST_RETURN");
-  Return.Flags.set(rcc::InstructionFlag::Return);
-  Return.Flags.set(rcc::InstructionFlag::Terminator);
-  Return.Flags.set(rcc::InstructionFlag::Barrier);
-  Descriptors.push_back(std::move(Return));
-
-  auto Meta = instruction(MetaOpcode, "TEST_META");
-  Meta.Flags = {rcc::InstructionFlag::Pseudo, rcc::InstructionFlag::Meta};
-  Descriptors.push_back(std::move(Meta));
-
-  auto Tied = instruction(TiedOpcode, "TEST_TIED");
-  auto TiedDef = registerOperand(rcc::RegisterOperandRole::Def);
-  auto TiedUse = registerOperand(rcc::RegisterOperandRole::Use);
-  TiedDef.DefaultTiedOperand = 1;
-  TiedUse.DefaultTiedOperand = 0;
-  Tied.Operands = {TiedDef, TiedUse};
-  Tied.NumExplicitDefs = 1;
-  Descriptors.push_back(std::move(Tied));
-
-  auto Commutable = instruction(CommutableTiedOpcode, "TEST_COMMUTABLE_TIED");
-  Commutable.Operands = {TiedDef, TiedUse, registerOperand(rcc::RegisterOperandRole::Use)};
-  Commutable.NumExplicitDefs = 1;
-  Commutable.Flags.set(rcc::InstructionFlag::Commutable);
-  Descriptors.push_back(std::move(Commutable));
-
-  auto Convertible = instruction(ConvertibleTiedOpcode, "TEST_CONVERTIBLE_TIED");
-  Convertible.Operands = {TiedDef, TiedUse};
-  Convertible.NumExplicitDefs = 1;
-  Descriptors.push_back(std::move(Convertible));
-
-  auto ThreeAddress = instruction(ThreeAddressOpcode, "TEST_THREE_ADDRESS");
-  ThreeAddress.Operands = {registerOperand(rcc::RegisterOperandRole::Def),
-                           registerOperand(rcc::RegisterOperandRole::Use)};
-  ThreeAddress.NumExplicitDefs = 1;
-  Descriptors.push_back(std::move(ThreeAddress));
-
-  auto Instructions = rcc::InstructionSet::create(std::move(Descriptors), std::move(Predicates));
-  if (!Instructions)
-    return std::unexpected(Instructions.error());
-  return rcc::test::createTestTargetDescription(std::move(*Instructions));
-}
-
-class TestInstrInfo final : public rcc::TargetInstrInfo {
-public:
-  explicit TestInstrInfo(bool RejectCopies = false) : RejectCopies(RejectCopies) {}
-
-  [[nodiscard]] rcc::Expected<rcc::MachineBranchAnalysis>
-  analyzeBranch(rcc::MachineBasicBlock &, rcc::MachineFunction &,
-                const rcc::TargetDescription &) const override {
-    return rcc::MachineBranchAnalysis{};
-  }
-
-  [[nodiscard]] rcc::Expected<void>
-  reverseBranchCondition(rcc::MachineInstr &, rcc::MachineBasicBlock &, rcc::MachineFunction &,
-                         const rcc::TargetDescription &) const override {
-    return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, "test target has no branch reversal");
-  }
-
-  [[nodiscard]] rcc::Expected<void> removeBranch(rcc::MachineInstr &, rcc::MachineFunction &,
-                                                 const rcc::TargetDescription &) const override {
-    return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, "test target has no branch removal");
-  }
-
-  [[nodiscard]] rcc::Expected<bool>
-  isFallthroughEdge(const rcc::MachineBasicBlock &From, const rcc::MachineBasicBlock &To,
-                    const rcc::MachineFunction &Function,
-                    const rcc::TargetDescription &Target) const override {
-    if (&From.function() != &Function || &To.function() != &Function) {
-      return rcc::makeUnexpected(rcc::ErrorCode::InvalidArgument,
-                                 "fallthrough query references another function");
-    }
-    if (From.next() != &To ||
-        std::ranges::none_of(From.successors(), [&To](const rcc::MachineSuccessor &Successor) {
-          return Successor.Block == &To;
-        })) {
-      return false;
-    }
-
-    bool CanFallThrough = true;
-    for (const rcc::MachineInstr *Instruction = From.firstInstruction(); Instruction != nullptr;
-         Instruction = Instruction->next()) {
-      const rcc::InstructionDescriptor *Descriptor =
-          Target.instructionDescriptor(Instruction->opcode());
-      if (Descriptor == nullptr) {
-        return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
-                                   "fallthrough query encountered an unknown opcode");
-      }
-      if (Descriptor->Flags.has(rcc::InstructionFlag::Terminator))
-        CanFallThrough = Instruction->opcode() == testOpcode(ConditionalBranchOpcode);
-    }
-    return CanFallThrough;
-  }
-
-  [[nodiscard]] rcc::Expected<bool>
-  rewriteBranchTarget(rcc::MachineBasicBlock &Block, rcc::MachineBasicBlock &OldTarget,
-                      rcc::MachineBasicBlock &NewTarget, rcc::MachineFunction &Function,
-                      const rcc::TargetDescription &Target) const override {
-    if (&Block.function() != &Function || &OldTarget.function() != &Function ||
-        &NewTarget.function() != &Function) {
-      return rcc::makeUnexpected(rcc::ErrorCode::InvalidArgument,
-                                 "branch rewrite references another function");
-    }
-    bool Changed = false;
-    for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
-         Instruction = Instruction->next()) {
-      const rcc::InstructionDescriptor *Descriptor =
-          Target.instructionDescriptor(Instruction->opcode());
-      if (Descriptor == nullptr)
-        return rcc::makeUnexpected(rcc::ErrorCode::VerificationError, "unknown branch opcode");
-      if (!Descriptor->Flags.has(rcc::InstructionFlag::Branch))
-        continue;
-      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
-        rcc::MachineOperand *Operand = Instruction->operandAt(Index);
-        const auto *BlockOperand =
-            Operand == nullptr ? nullptr : Operand->getIf<rcc::BasicBlockOperand>();
-        if (BlockOperand == nullptr || BlockOperand->Block != &OldTarget)
-          continue;
-        auto Rewritten = Operand->setBasicBlock(NewTarget);
-        if (!Rewritten)
-          return std::unexpected(Rewritten.error());
-        Changed = true;
-      }
-    }
-    return Changed;
-  }
-
-  [[nodiscard]] rcc::Expected<rcc::MachineInstr *>
-  insertBranch(rcc::MachineBasicBlock &Block, rcc::MachineBasicBlock &TargetBlock,
-               rcc::MachineFunction &Function,
-               const rcc::TargetDescription &Target) const override {
-    rcc::MachineIRBuilder Builder(Function, Target);
-    auto Point = Builder.setInsertPoint(Block);
-    if (!Point)
-      return std::unexpected(Point.error());
-    auto Pending = Builder.buildInstr(testOpcode(JumpOpcode));
-    if (!Pending)
-      return std::unexpected(Pending.error());
-    auto Destination = Pending->addBasicBlock(TargetBlock);
-    if (!Destination)
-      return std::unexpected(Destination.error());
-    auto Built = Pending->build();
-    if (!Built)
-      return std::unexpected(Built.error());
-    return *Built;
-  }
-
-  [[nodiscard]] rcc::Expected<void>
-  validateCopy(rcc::Register Destination, rcc::SubRegIndex DestinationSubReg, rcc::Register Source,
-               rcc::SubRegIndex SourceSubReg, const rcc::MachineFunction &Function,
-               const rcc::TargetDescription &Target) const override {
-    if (RejectCopies) {
-      return rcc::makeUnexpected(rcc::ErrorCode::Unsupported,
-                                 "test target intentionally rejects COPY");
-    }
-    if (Destination.isNoRegister() || Source.isNoRegister()) {
-      return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
-                                 "COPY requires nonzero registers");
-    }
-    if ((Destination.isPhysical() && DestinationSubReg.value() != 0) ||
-        (Source.isPhysical() && SourceSubReg.value() != 0)) {
-      return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
-                                 "physical COPY operands cannot carry subregisters");
-    }
-    auto Def = rcc::MachineOperand::registerOperand(Destination, {rcc::RegisterOperandFlag::Define},
-                                                    DestinationSubReg);
-    auto Use =
-        rcc::MachineOperand::registerOperand(Source, {rcc::RegisterOperandFlag::Use}, SourceSubReg);
-    if (!Def || !Use)
-      return rcc::makeUnexpected(rcc::ErrorCode::InternalError, "failed to model COPY operands");
-    return Target.validateTieCompatibility(*Def, *Use, Function.registerInfo());
-  }
-
-  [[nodiscard]] rcc::Expected<bool>
-  tryConvertToThreeAddress(rcc::MachineInstr &Instruction, std::size_t DefIndex,
-                           std::size_t UseIndex, rcc::MachineFunction &,
-                           const rcc::TargetDescription &) const override {
-    if (Instruction.opcode() != testOpcode(ConvertibleTiedOpcode))
-      return false;
-    if (DefIndex != 0 || UseIndex != 1)
-      return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
-                                 "unexpected convertible tie indices");
-    auto Untied = Instruction.untieOperand(DefIndex);
-    if (!Untied)
-      return std::unexpected(Untied.error());
-    auto Opcode = Instruction.setOpcode(testOpcode(ThreeAddressOpcode));
-    if (!Opcode)
-      return std::unexpected(Opcode.error());
-    return true;
-  }
-
-  [[nodiscard]] rcc::Expected<std::uint32_t>
-  instructionSize(const rcc::MachineInstr &, const rcc::MachineFunction &,
-                  const rcc::TargetDescription &) const override {
-    return 4;
-  }
-
-  [[nodiscard]] rcc::Expected<rcc::MachineBasicBlock *>
-  branchTarget(rcc::MachineInstr &, rcc::MachineFunction &,
-               const rcc::TargetDescription &) const override {
-    return static_cast<rcc::MachineBasicBlock *>(nullptr);
-  }
-
-  [[nodiscard]] bool isBranchOffsetInRange(const rcc::MachineInstr &,
-                                           std::int64_t) const noexcept override {
-    return true;
-  }
-
-  [[nodiscard]] rcc::Expected<bool> relaxBranch(rcc::MachineInstr &, std::int64_t,
-                                                rcc::MachineFunction &,
-                                                const rcc::TargetDescription &) const override {
-    return false;
-  }
-
-private:
-  bool RejectCopies = false;
-};
-
-struct FunctionFixture final {
-  std::unique_ptr<rcc::MachineFunction> Function;
-  std::vector<rcc::MachineBasicBlock *> Blocks;
-};
-
-[[nodiscard]] FunctionFixture createFunction(TestContext &Context, std::string Name,
-                                             std::uint64_t ID, std::size_t BlockCount) {
-  auto Function =
-      rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID));
-  Context.expect(Function.has_value(), "SSA-exit function creation must succeed");
-  if (!Function)
-    return {};
-
-  FunctionFixture Result{std::move(*Function), {}};
-  for (std::size_t Index = 0; Index < BlockCount; ++Index) {
-    auto Block = Result.Function->createBasicBlock();
-    Context.expect(Block && Result.Function->appendBlock(**Block).has_value(),
-                   "SSA-exit block creation must succeed");
-    if (!Block)
-      return {};
-    Result.Blocks.push_back(*Block);
-  }
-  return Result;
-}
-
-[[nodiscard]] rcc::Expected<rcc::Register>
-createVReg(rcc::MachineFunction &Function, rcc::LLT Type, rcc::RegisterBankID Bank,
-           rcc::RegisterClassID Class, std::uint8_t TargetFlags = 0,
-           std::optional<rcc::PhysicalRegister> Hint = std::nullopt) {
-  auto Reg = Function.registerInfo().createVirtualRegister(Type);
-  if (!Reg)
-    return std::unexpected(Reg.error());
-  auto BankResult = Function.registerInfo().setRegisterBank(*Reg, Bank);
-  if (!BankResult)
-    return std::unexpected(BankResult.error());
-  auto ClassResult = Function.registerInfo().setRegisterClass(*Reg, Class);
-  if (!ClassResult)
-    return std::unexpected(ClassResult.error());
-  if (TargetFlags != 0) {
-    auto FlagsResult = Function.registerInfo().setTargetRegisterFlags(*Reg, TargetFlags);
-    if (!FlagsResult)
-      return std::unexpected(FlagsResult.error());
-  }
-  if (Hint) {
-    auto HintResult = Function.registerInfo().addAllocationHint(*Reg, *Hint);
-    if (!HintResult)
-      return std::unexpected(HintResult.error());
-  }
-  return *Reg;
-}
-
-[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
-buildRegisterInstruction(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
-                         rcc::MachineBasicBlock &Block, rcc::Opcode Opcode,
-                         std::span<const rcc::Register> Defs, std::span<const rcc::Register> Uses,
-                         rcc::RegisterOperandFlags DefFlags = {},
-                         rcc::RegisterOperandFlags UseFlags = {}) {
-  rcc::MachineIRBuilder Builder(Function, Target);
-  auto Point = Builder.setInsertPoint(Block);
-  if (!Point)
-    return std::unexpected(Point.error());
-  auto Pending = Builder.buildInstr(Opcode);
-  if (!Pending)
-    return std::unexpected(Pending.error());
-  for (rcc::Register Reg : Defs) {
-    auto Added = Pending->addDef(Reg, DefFlags);
-    if (!Added)
-      return std::unexpected(Added.error());
-  }
-  for (rcc::Register Reg : Uses) {
-    auto Added = Pending->addUse(Reg, UseFlags);
-    if (!Added)
-      return std::unexpected(Added.error());
-  }
-  return Pending->build();
-}
-
-[[nodiscard]] rcc::Expected<rcc::MachineInstr *> buildJump(rcc::MachineFunction &Function,
-                                                           const rcc::TargetDescription &Target,
-                                                           rcc::MachineBasicBlock &Block,
-                                                           rcc::MachineBasicBlock &Destination) {
-  rcc::MachineIRBuilder Builder(Function, Target);
-  auto Point = Builder.setInsertPoint(Block);
-  if (!Point)
-    return std::unexpected(Point.error());
-  auto Pending = Builder.buildInstr(testOpcode(JumpOpcode));
-  if (!Pending)
-    return std::unexpected(Pending.error());
-  auto TargetOperand = Pending->addBasicBlock(Destination);
-  if (!TargetOperand)
-    return std::unexpected(TargetOperand.error());
-  return Pending->build();
-}
-
-[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
-buildPhi(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
-         rcc::MachineBasicBlock &Block, rcc::Register Destination,
-         std::span<const std::pair<rcc::Register, rcc::MachineBasicBlock *>> Incoming,
-         rcc::RegisterOperandFlags DestinationFlags = {}, std::uint32_t DestinationTargetFlags = 0,
-         rcc::RegisterOperandFlags IncomingFlags = {}, std::uint32_t IncomingTargetFlags = 0) {
-  rcc::MachineIRBuilder Builder(Function, Target);
-  auto Point = Builder.setInsertPoint(Block);
-  if (!Point)
-    return std::unexpected(Point.error());
-  auto Pending = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI));
-  if (!Pending)
-    return std::unexpected(Pending.error());
-  auto Def = Pending->addDef(Destination, DestinationFlags, {}, DestinationTargetFlags);
-  if (!Def)
-    return std::unexpected(Def.error());
-  for (const auto &[Value, Predecessor] : Incoming) {
-    auto Use = Pending->addUse(Value, IncomingFlags, {}, IncomingTargetFlags);
-    if (!Use)
-      return std::unexpected(Use.error());
-    auto IncomingBlock = Pending->addBasicBlock(*Predecessor);
-    if (!IncomingBlock)
-      return std::unexpected(IncomingBlock.error());
-  }
-  return Pending->build();
-}
-
-[[nodiscard]] rcc::Expected<void> setSelectedSSAProperties(rcc::MachineFunction &Function,
-                                                           const rcc::TargetDescription &Target) {
-  auto Rebuilt = rcc::rebuildMachineLiveness(Function, Target);
-  if (!Rebuilt)
-    return std::unexpected(Rebuilt.error());
-  for (rcc::MachineFunctionProperty Property :
-       {rcc::MachineFunctionProperty::IsSSA, rcc::MachineFunctionProperty::TracksLiveness,
-        rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected,
-        rcc::MachineFunctionProperty::Selected}) {
-    Function.properties().set(Property);
-  }
-  return {};
-}
-
-[[nodiscard]] rcc::Expected<void> runPHIElimination(rcc::MachineFunction &Function,
-                                                    const rcc::TargetDescription &Target,
-                                                    const rcc::TargetInstrInfo &Info) {
-  rcc::MachinePassManager Pipeline;
-  auto Added = Pipeline.addPass(std::make_unique<rcc::PHIEliminationPass>(Info));
-  if (!Added)
-    return std::unexpected(Added.error());
-  rcc::MachineAnalysisManager Analyses;
-  return Pipeline.run(Function, Target, Analyses);
-}
-
-[[nodiscard]] std::vector<rcc::MachineInstr *> linkedInstructions(rcc::MachineBasicBlock &Block) {
-  std::vector<rcc::MachineInstr *> Result;
-  for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
-       Instruction = Instruction->next()) {
-    Result.push_back(Instruction);
-  }
-  return Result;
-}
-
-[[nodiscard]] std::vector<rcc::MachineInstr *>
-instructionsWithOpcode(rcc::MachineFunction &Function, rcc::Opcode Opcode) {
-  std::vector<rcc::MachineInstr *> Result;
-  for (rcc::MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
-       Block = Block->next()) {
-    for (rcc::MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
-         Instruction = Instruction->next()) {
-      if (Instruction->opcode() == Opcode)
-        Result.push_back(Instruction);
-    }
-  }
-  return Result;
-}
-
-[[nodiscard]] bool hasLiveIn(const rcc::MachineBasicBlock &Block, rcc::PhysicalRegister Reg) {
-  return std::ranges::any_of(Block.liveIns(), [Reg](const rcc::MachineBasicBlockLiveIn &LiveIn) {
-    return LiveIn.PhysReg == Reg;
-  });
-}
-
-void testParallelPHIsAndPlacement(TestContext &Context, const rcc::TargetDescription &Target,
-                                  const TestInstrInfo &Info) {
-  auto Fixture = createFunction(Context, "parallel_phis", 1, 3);
-  if (!Fixture.Function || Fixture.Blocks.size() != 3)
-    return;
-  auto I64 = rcc::LLT::makeInteger(64);
-  if (!I64)
-    return;
-  auto &Function = *Fixture.Function;
-  rcc::MachineBasicBlock &Preheader = *Fixture.Blocks[0];
-  rcc::MachineBasicBlock &Header = *Fixture.Blocks[1];
-  rcc::MachineBasicBlock &Backedge = *Fixture.Blocks[2];
-  const rcc::PhysicalRegister Hint = *rcc::PhysicalRegister::create(rcc::test::TestRegister::G1);
-
-  auto InitA = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
-                          rcc::test::TestRegisterClass::GPR64);
-  auto InitB = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
-                          rcc::test::TestRegisterClass::GPR64);
-  auto DestinationA = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
-                                 rcc::test::TestRegisterClass::GPR64, 0x1, Hint);
-  auto DestinationB = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
-                                 rcc::test::TestRegisterClass::GPR64);
-  Context.expect(InitA && InitB && DestinationA && DestinationB,
-                 "parallel PHI registers must be created");
-  if (!InitA || !InitB || !DestinationA || !DestinationB)
-    return;
-
-  auto CFG = Function.cfgUpdater();
-  Context.expect(
-      CFG.addSuccessor(Preheader, Header, rcc::BranchProbability::one()).has_value() &&
-          CFG.addSuccessor(Header, Backedge, rcc::BranchProbability::one()).has_value() &&
-          CFG.addSuccessor(Backedge, Header, rcc::BranchProbability::one()).has_value(),
-      "parallel PHI loop CFG must be connected");
-
-  const std::array InitADef{*InitA};
-  const std::array InitBDef{*InitB};
-  Context.expect(buildRegisterInstruction(Function, Target, Preheader, testOpcode(DefOpcode),
-                                          InitADef, {}, {rcc::RegisterOperandFlag::Dead}) &&
-                     buildRegisterInstruction(Function, Target, Preheader, testOpcode(DefOpcode),
-                                              InitBDef, {}) &&
-                     buildJump(Function, Target, Preheader, Header),
-                 "parallel PHI preheader must be populated");
-
-  const std::array IncomingA{
-      std::pair<rcc::Register, rcc::MachineBasicBlock *>{*InitA, &Preheader},
-      std::pair<rcc::Register, rcc::MachineBasicBlock *>{*DestinationB, &Backedge}};
-  const std::array IncomingB{
-      std::pair<rcc::Register, rcc::MachineBasicBlock *>{*InitB, &Preheader},
-      std::pair<rcc::Register, rcc::MachineBasicBlock *>{*DestinationA, &Backedge}};
-  Context.expect(buildPhi(Function, Target, Header, *DestinationA, IncomingA, {}, 0x4, {}, 0x8) &&
-                     buildPhi(Function, Target, Header, *DestinationB, IncomingB),
-                 "parallel PHIs must be built");
-
-  rcc::MachineIRBuilder HeaderBuilder(Function, Target);
-  if (!HeaderBuilder.setInsertPoint(Header))
-    return;
-  auto Meta = HeaderBuilder.buildInstr(testOpcode(MetaOpcode));
-  const std::array HeaderUse{*DestinationA};
-  Context.expect(Meta && Meta->build() &&
-                     buildRegisterInstruction(Function, Target, Header, testOpcode(UseOpcode), {},
-                                              HeaderUse) &&
-                     buildJump(Function, Target, Header, Backedge),
-                 "parallel PHI header must contain meta, code, and terminator instructions");
-
-  const std::array KilledUse{*DestinationA};
-  Context.expect(buildRegisterInstruction(Function, Target, Backedge, testOpcode(UseOpcode), {},
-                                          KilledUse, {}, {rcc::RegisterOperandFlag::Kill}) &&
-                     buildJump(Function, Target, Backedge, Header),
-                 "parallel PHI backedge must be populated");
-  auto InitialLiveness = setSelectedSSAProperties(Function, Target);
-  Context.expect(InitialLiveness.has_value(), "parallel PHI liveness rebuild must succeed");
-  if (!InitialLiveness)
-    return;
-
-  auto Run = runPHIElimination(Function, Target, Info);
-  Context.expect(Run.has_value(), "parallel PHI elimination must succeed");
-  if (!Run)
-    return;
-  Context.expect(!Function.properties().has(rcc::MachineFunctionProperty::IsSSA) &&
-                     Function.properties().has(rcc::MachineFunctionProperty::NoPHIs) &&
-                     Function.properties().has(rcc::MachineFunctionProperty::TracksLiveness),
-                 "PHI elimination must publish its exact property transition");
-  Context.expect(instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::PHI)).empty(),
-                 "PHI elimination must remove every PHI");
-
-  const auto HeaderInstructions = linkedInstructions(Header);
-  Context.expect(HeaderInstructions.size() == 5 &&
-                     HeaderInstructions[0]->opcode() == testOpcode(MetaOpcode) &&
-                     HeaderInstructions[1]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
-                     HeaderInstructions[2]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
-                     HeaderInstructions[3]->opcode() == testOpcode(UseOpcode) &&
-                     HeaderInstructions[4]->opcode() == testOpcode(JumpOpcode),
-                 "destination COPYs must follow the full leading PHI/meta region");
-  if (HeaderInstructions.size() < 3)
-    return;
-
-  const rcc::Register *FreshA = HeaderInstructions[1]->operandAt(1)->getIf<rcc::Register>();
-  const rcc::Register *FreshB = HeaderInstructions[2]->operandAt(1)->getIf<rcc::Register>();
-  Context.expect(FreshA != nullptr && FreshB != nullptr && *FreshA != *FreshB &&
-                     *FreshA != *DestinationA && *FreshB != *DestinationB,
-                 "each PHI must receive an independent fresh incoming vreg");
-  if (FreshA == nullptr || FreshB == nullptr)
-    return;
-
-  const auto BackedgeInstructions = linkedInstructions(Backedge);
-  Context.expect(BackedgeInstructions.size() == 4 &&
-                     BackedgeInstructions[1]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
-                     BackedgeInstructions[2]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
-                     BackedgeInstructions[3]->opcode() == testOpcode(JumpOpcode),
-                 "incoming COPYs must be placed together before the first terminator");
-  if (BackedgeInstructions.size() >= 3) {
-    const auto FirstDef = BackedgeInstructions[1]->operandAt(0)->registerValue();
-    const auto FirstUse = BackedgeInstructions[1]->operandAt(1)->registerValue();
-    const auto SecondDef = BackedgeInstructions[2]->operandAt(0)->registerValue();
-    const auto SecondUse = BackedgeInstructions[2]->operandAt(1)->registerValue();
-    Context.expect(FirstDef == *FreshA && FirstUse == *DestinationB && SecondDef == *FreshB &&
-                       SecondUse == *DestinationA,
-                   "backedge COPYs must read old PHI destinations into distinct temporaries");
-  }
-
-  auto FreshInfo = Function.registerInfo().virtualRegisterInfo(*FreshA);
-  Context.expect(FreshInfo.has_value(), "fresh PHI vreg must remain registered");
-  if (!FreshInfo)
-    return;
-  Context.expect(FreshInfo->get().Type == I64, "fresh PHI vreg must clone its LLT");
-  Context.expect(FreshInfo->get().Bank == rcc::test::TestRegisterBank::GPR,
-                 "fresh PHI vreg must clone its register bank");
-  Context.expect(FreshInfo->get().RegClass == rcc::test::TestRegisterClass::GPR64,
-                 "fresh PHI vreg must clone its register class");
-  Context.expect(FreshInfo->get().TargetFlags == 0x1,
-                 "fresh PHI vreg must clone registered target flags");
-  Context.expect(FreshInfo->get().AllocationHints.size() == 1,
-                 "fresh PHI vreg must clone the allocation-hint count");
-  Context.expect(!FreshInfo->get().AllocationHints.empty() &&
-                     FreshInfo->get().AllocationHints.front() == Hint,
-                 "fresh PHI vreg must clone the allocation-hint register");
-  Context.expect(HeaderInstructions[1]->operandAt(0)->targetFlags() == 0x4 &&
-                     HeaderInstructions[1]->operandAt(1)->targetFlags() == 0x4,
-                 "successor COPY must preserve registered destination target flags");
-
-  const rcc::MachineInstr *InitDefinition = Preheader.firstInstruction();
-  Context.expect(
-      InitDefinition != nullptr &&
-          !InitDefinition->operandAt(0)->registerFlags().has(rcc::RegisterOperandFlag::Dead) &&
-          !BackedgeInstructions[0]->operandAt(0)->registerFlags().has(
-              rcc::RegisterOperandFlag::Kill),
-      "liveness-preserving PHI elimination must conservatively clear kill/dead flags");
-  Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(),
-                 "parallel PHI result must pass MachineVerifier");
-}
-
-void testCriticalEdgeAndPhysicalLiveIn(TestContext &Context, const rcc::TargetDescription &Target,
-                                       const TestInstrInfo &Info) {
-  auto Fixture = createFunction(Context, "critical_edge", 2, 4);
-  if (!Fixture.Function || Fixture.Blocks.size() != 4)
-    return;
-  auto I64 = rcc::LLT::makeInteger(64);
-  if (!I64)
-    return;
-  auto &Function = *Fixture.Function;
-  rcc::MachineBasicBlock &From = *Fixture.Blocks[0];
-  rcc::MachineBasicBlock &Side = *Fixture.Blocks[1];
-  rcc::MachineBasicBlock &Other = *Fixture.Blocks[2];
-  rcc::MachineBasicBlock &Merge = *Fixture.Blocks[3];
-  auto Condition = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
-                              rcc::test::TestRegisterClass::GPR64);
-  auto OtherValue = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
-                               rcc::test::TestRegisterClass::GPR64);
-  auto Destination = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
-                                rcc::test::TestRegisterClass::GPR64);
-  if (!Condition || !OtherValue || !Destination)
-    return;
-
-  auto Half = rcc::BranchProbability::fromFraction(1, 2);
-  auto CFG = Function.cfgUpdater();
-  Context.expect(Half && CFG.addSuccessor(From, Side, *Half) &&
-                     CFG.addSuccessor(From, Merge, *Half) &&
-                     CFG.addSuccessor(Other, Merge, rcc::BranchProbability::one()),
-                 "critical-edge CFG must be connected");
-
-  const std::array ConditionDef{*Condition};
-  Context.expect(
-      buildRegisterInstruction(Function, Target, From, testOpcode(DefOpcode), ConditionDef, {})
-          .has_value(),
-      "critical-edge condition must be defined");
-  rcc::MachineIRBuilder FromBuilder(Function, Target);
-  if (!FromBuilder.setInsertPoint(From))
-    return;
-  auto Branch = FromBuilder.buildInstr(testOpcode(ConditionalBranchOpcode));
-  Context.expect(Branch && Branch->addUse(*Condition) && Branch->addBasicBlock(Merge) &&
-                     Branch->build(),
-                 "critical-edge conditional branch must be built");
-  const std::array OtherDef{*OtherValue};
-  Context.expect(
-      buildRegisterInstruction(Function, Target, Other, testOpcode(DefOpcode), OtherDef, {})
-          .has_value(),
-      "unrelated fallthrough predecessor must define its incoming value");
-
-  const rcc::PhysicalRegister G0 = *rcc::PhysicalRegister::create(rcc::test::TestRegister::G0);
-  const rcc::PhysicalRegister G1 = *rcc::PhysicalRegister::create(rcc::test::TestRegister::G1);
-  Context.expect(Merge.addLiveIn(G1, rcc::LaneMask::fromRaw(0xF)).has_value(),
-                 "merge block live-in setup must succeed");
-  const std::array Incoming{
-      std::pair<rcc::Register, rcc::MachineBasicBlock *>{rcc::Register::fromPhysical(G0), &From},
-      std::pair<rcc::Register, rcc::MachineBasicBlock *>{*OtherValue, &Other}};
-  Context.expect(buildPhi(Function, Target, Merge, *Destination, Incoming).has_value(),
-                 "critical-edge PHI must be built");
-  const std::array G1Use{rcc::Register::fromPhysical(G1)};
-  Context.expect(buildRegisterInstruction(Function, Target, Merge, testOpcode(UseOpcode), {}, G1Use)
-                     .has_value(),
-                 "merge block must consume its inherited physical live-in");
-  auto InitialLiveness = setSelectedSSAProperties(Function, Target);
-  Context.expect(InitialLiveness.has_value(), "critical-edge PHI liveness rebuild must succeed");
-  if (!InitialLiveness)
-    return;
-
-  auto Run = runPHIElimination(Function, Target, Info);
-  Context.expect(Run.has_value(), "critical-edge PHI elimination must succeed");
-  if (!Run)
-    return;
-
-  rcc::MachineBasicBlock *Edge = Merge.previous();
-  Context.expect(
-      Edge != nullptr && Edge != &Other && Edge->previous() == &Other &&
-          From.successors().size() == 2 &&
-          std::ranges::any_of(From.successors(),
-                              [Edge](const rcc::MachineSuccessor &S) { return S.Block == Edge; }) &&
-          Edge->predecessors().size() == 1 && Edge->predecessors()[0] == &From &&
-          Edge->successors().size() == 1 && Edge->successors()[0].Block == &Merge,
-      "critical edge must become a reciprocal From-to-edge-to-Merge CFG path");
-  if (Edge == nullptr || Edge == &Other)
-    return;
-
-  const rcc::MachineOperand *BranchTarget = From.lastInstruction()->operandAt(1);
-  const auto *BranchBlock =
-      BranchTarget == nullptr ? nullptr : BranchTarget->getIf<rcc::BasicBlockOperand>();
-  Context.expect(BranchBlock != nullptr && BranchBlock->Block == Edge,
-                 "explicit critical-edge branch must target the split block");
-  const auto OtherInstructions = linkedInstructions(Other);
-  const auto EdgeInstructions = linkedInstructions(*Edge);
-  Context.expect(OtherInstructions.size() == 3 &&
-                     OtherInstructions.back()->opcode() == testOpcode(JumpOpcode) &&
-                     EdgeInstructions.size() == 2 &&
-                     EdgeInstructions[0]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
-                     EdgeInstructions[1]->opcode() == testOpcode(JumpOpcode),
-                 "edge split must preserve unrelated fallthrough and terminator placement");
-  Context.expect(hasLiveIn(*Edge, G0) && hasLiveIn(*Edge, G1),
-                 "split edge must inherit successor live-ins and its physical PHI source");
-  Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(),
-                 "critical-edge result must pass MachineVerifier");
-}
-
-void testUndefAndFailureAtomicity(TestContext &Context, const rcc::TargetDescription &Target,
-                                  const TestInstrInfo &Info) {
-  auto BuildFixture = [&](std::uint64_t ID) {
-    auto Fixture = createFunction(Context, "undef_phi", ID, 2);
-    if (!Fixture.Function || Fixture.Blocks.size() != 2)
-      return Fixture;
-    auto I64 = rcc::LLT::makeInteger(64);
-    if (!I64)
-      return Fixture;
-    auto Source = createVReg(*Fixture.Function, *I64, rcc::test::TestRegisterBank::GPR,
-                             rcc::test::TestRegisterClass::GPR64);
-    auto Destination = createVReg(*Fixture.Function, *I64, rcc::test::TestRegisterBank::GPR,
-                                  rcc::test::TestRegisterClass::GPR64);
-    if (!Source || !Destination)
-      return Fixture;
-    auto CFG = Fixture.Function->cfgUpdater();
-    if (!CFG.addSuccessor(*Fixture.Blocks[0], *Fixture.Blocks[1], rcc::BranchProbability::one()) ||
-        !buildJump(*Fixture.Function, Target, *Fixture.Blocks[0], *Fixture.Blocks[1])) {
-      return Fixture;
-    }
-    const std::array Incoming{
-        std::pair<rcc::Register, rcc::MachineBasicBlock *>{*Source, Fixture.Blocks[0]}};
-    if (!buildPhi(*Fixture.Function, Target, *Fixture.Blocks[1], *Destination, Incoming, {}, 0,
-                  {rcc::RegisterOperandFlag::Undef})) {
-      return Fixture;
-    }
-    Context.expect(setSelectedSSAProperties(*Fixture.Function, Target).has_value(),
-                   "undef PHI liveness rebuild must succeed");
-    return Fixture;
-  };
-
-  auto Undef = BuildFixture(3);
-  if (!Undef.Function)
-    return;
-  auto Run = runPHIElimination(*Undef.Function, Target, Info);
-  Context.expect(Run.has_value(), "undef PHI elimination must succeed");
-  if (Run) {
-    const auto PredecessorInstructions = linkedInstructions(*Undef.Blocks[0]);
-    Context.expect(PredecessorInstructions.size() == 2 &&
-                       PredecessorInstructions[0]->opcode() ==
-                           rcc::opcode(rcc::GenericOpcode::IMPLICIT_DEF) &&
-                       PredecessorInstructions[1]->opcode() == testOpcode(JumpOpcode),
-                   "undef PHI incoming values must become edge IMPLICIT_DEF instructions");
-  }
-
-  auto Atomic = BuildFixture(4);
-  if (!Atomic.Function)
-    return;
-  const std::size_t BlocksBefore = Atomic.Function->blockCount();
-  const std::size_t InstructionsBefore =
-      instructionsWithOpcode(*Atomic.Function, rcc::opcode(rcc::GenericOpcode::PHI)).size();
-  const std::size_t RegistersBefore = Atomic.Function->registerInfo().virtualRegisters().size();
-  const std::uint64_t PropertiesBefore = Atomic.Function->properties().rawValue();
-  TestInstrInfo RejectingInfo(true);
-  rcc::MachineAnalysisManager Analyses;
-  rcc::PHIEliminationPass FailingPass(RejectingInfo);
-  auto Failed = FailingPass.run(*Atomic.Function, Target, Analyses);
-  Context.expect(!Failed && Failed.error().code() == rcc::ErrorCode::Unsupported,
-                 "COPY rejection must produce a structured PHI-elimination failure");
-  Context.expect(
-      Atomic.Function->blockCount() == BlocksBefore &&
-          instructionsWithOpcode(*Atomic.Function, rcc::opcode(rcc::GenericOpcode::PHI)).size() ==
-              InstructionsBefore &&
-          Atomic.Function->registerInfo().virtualRegisters().size() == RegistersBefore &&
-          Atomic.Function->properties().rawValue() == PropertiesBefore,
-      "failed PHI transaction preflight must leave the original function unchanged");
-
-  rcc::PHIEliminationPass MissingBehavior;
-  auto Missing = MissingBehavior.run(*Atomic.Function, Target, Analyses);
-  Context.expect(!Missing && Missing.error().code() == rcc::ErrorCode::InvalidArgument,
-                 "PHI elimination without target behavior must fail explicitly");
-}
-
-void testTwoAddressAndSubregisterPseudos(TestContext &Context, const rcc::TargetDescription &Target,
-                                         const TestInstrInfo &Info) {
-  auto Fixture = createFunction(Context, "two_address", 5, 1);
-  if (!Fixture.Function || Fixture.Blocks.empty())
-    return;
-  auto I64 = rcc::LLT::makeInteger(64);
-  auto I32 = rcc::LLT::makeInteger(32);
-  if (!I64 || !I32)
-    return;
-  auto &Function = *Fixture.Function;
-  rcc::MachineBasicBlock &Block = *Fixture.Blocks[0];
-  auto GPR64 = [&](std::uint8_t Flags = 0) {
-    return createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
-                      rcc::test::TestRegisterClass::GPR64, Flags);
-  };
-  auto GPR32 = [&]() {
-    return createVReg(Function, *I32, rcc::test::TestRegisterBank::GPR,
-                      rcc::test::TestRegisterClass::GPR32);
-  };
-
-  auto Satisfied = GPR64();
-  auto UndefSource = GPR64();
-  auto UndefDestination = GPR64();
-  auto CommuteSource = GPR64();
-  auto CommuteDestination = GPR64();
-  auto ConvertSource = GPR64();
-  auto ConvertDestination = GPR64();
-  auto FallbackSource = GPR64();
-  auto FallbackDestination = GPR64();
-  auto SequenceDestination = GPR64();
-  auto SequenceLow = GPR32();
-  auto SequenceHigh = GPR32();
-  auto InsertDestination = GPR64();
-  auto InsertBase = GPR64();
-  auto Inserted = GPR32();
-  const bool Complete = Satisfied && UndefSource && UndefDestination && CommuteSource &&
-                        CommuteDestination && ConvertSource && ConvertDestination &&
-                        FallbackSource && FallbackDestination && SequenceDestination &&
-                        SequenceLow && SequenceHigh && InsertDestination && InsertBase && Inserted;
-  Context.expect(Complete, "two-address test registers must be created");
-  if (!Complete)
-    return;
-
-  for (rcc::Register Source : {*CommuteSource, *ConvertSource, *FallbackSource, *SequenceLow,
-                               *SequenceHigh, *InsertBase, *Inserted}) {
-    const std::array Def{Source};
-    Context.expect(buildRegisterInstruction(Function, Target, Block, testOpcode(DefOpcode), Def, {},
-                                            {rcc::RegisterOperandFlag::Dead})
-                       .has_value(),
-                   "two-address source definition must be built");
-  }
-  const std::array UndefDef{*UndefSource};
-  Context.expect(buildRegisterInstruction(Function, Target, Block,
-                                          rcc::opcode(rcc::GenericOpcode::IMPLICIT_DEF), UndefDef,
-                                          {})
-                     .has_value(),
-                 "two-address undef source must be defined by IMPLICIT_DEF");
-
-  auto BuildTied = [&](rcc::Opcode Opcode, rcc::Register Def, rcc::Register Use,
-                       std::optional<rcc::Register> Other = std::nullopt) {
-    rcc::MachineIRBuilder Builder(Function, Target);
-    auto Point = Builder.setInsertPoint(Block);
-    if (!Point)
-      return rcc::Expected<rcc::MachineInstr *>{std::unexpected(Point.error())};
-    auto Pending = Builder.buildInstr(Opcode);
-    if (!Pending)
-      return rcc::Expected<rcc::MachineInstr *>{std::unexpected(Pending.error())};
-    auto AddedDef = Pending->addDef(Def);
-    if (!AddedDef)
-      return rcc::Expected<rcc::MachineInstr *>{std::unexpected(AddedDef.error())};
-    auto AddedUse = Pending->addUse(Use, {rcc::RegisterOperandFlag::Kill});
-    if (!AddedUse)
-      return rcc::Expected<rcc::MachineInstr *>{std::unexpected(AddedUse.error())};
-    if (Other) {
-      auto AddedOther = Pending->addUse(*Other);
-      if (!AddedOther)
-        return rcc::Expected<rcc::MachineInstr *>{std::unexpected(AddedOther.error())};
-    }
-    return Pending->build();
-  };
-
-  auto AlreadyTied = BuildTied(testOpcode(TiedOpcode), *Satisfied, *Satisfied);
-  auto UndefTied = BuildTied(testOpcode(TiedOpcode), *UndefDestination, *UndefSource);
-  auto Commutable = BuildTied(testOpcode(CommutableTiedOpcode), *CommuteDestination, *CommuteSource,
-                              *CommuteDestination);
-  auto Convertible =
-      BuildTied(testOpcode(ConvertibleTiedOpcode), *ConvertDestination, *ConvertSource);
-  auto Fallback = BuildTied(testOpcode(TiedOpcode), *FallbackDestination, *FallbackSource);
-  Context.expect(AlreadyTied && UndefTied && Commutable && Convertible && Fallback,
-                 "two-address instruction fixtures must be built");
-  if (!AlreadyTied || !UndefTied || !Commutable || !Convertible || !Fallback)
-    return;
-
-  rcc::MachineIRBuilder Builder(Function, Target);
-  if (!Builder.setInsertPoint(Block))
-    return;
-  auto Sequence = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::REG_SEQUENCE));
-  Context.expect(
-      Sequence && Sequence->addDef(*SequenceDestination) && Sequence->addUse(*SequenceLow) &&
-          Sequence->addImmediate(rcc::test::TestSubReg::Low32.value()) &&
-          Sequence->addUse(*SequenceHigh) &&
-          Sequence->addImmediate(rcc::test::TestSubReg::High32.value()) && Sequence->build(),
-      "REG_SEQUENCE fixture must be built");
-  auto Insert = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::INSERT_SUBREG));
-  Context.expect(Insert && Insert->addDef(*InsertDestination) && Insert->addUse(*InsertBase) &&
-                     Insert->addUse(*Inserted) &&
-                     Insert->addImmediate(rcc::test::TestSubReg::Low32.value()) && Insert->build(),
-                 "INSERT_SUBREG fixture must be built");
-  auto Return = Builder.buildInstr(testOpcode(ReturnOpcode));
-  Context.expect(Return && Return->build(), "two-address return must be built");
-
-  auto InitialLiveness = setSelectedSSAProperties(Function, Target);
-  Context.expect(InitialLiveness.has_value(), "two-address liveness rebuild must succeed");
-  if (!InitialLiveness)
-    return;
-  Function.properties().set(rcc::MachineFunctionProperty::NoPHIs);
-  rcc::MachinePassManager Pipeline;
-  Context.expect(Pipeline.addPass(std::make_unique<rcc::TwoAddressRewritePass>(Info)).has_value(),
-                 "two-address pass must be registered");
-  rcc::MachineAnalysisManager Analyses;
-  auto Run = Pipeline.run(Function, Target, Analyses);
-  Context.expect(Run.has_value(), "two-address rewrite must succeed");
-  if (!Run)
-    return;
-
-  Context.expect(Function.properties().has(rcc::MachineFunctionProperty::TiedOpsRewritten) &&
-                     !Function.properties().has(rcc::MachineFunctionProperty::IsSSA),
-                 "two-address rewrite must publish TiedOpsRewritten and clear IsSSA");
-  Context.expect(
-      instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::REG_SEQUENCE)).empty() &&
-          instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::INSERT_SUBREG)).empty(),
-      "TwoAddressRewrite must consume all Stage 10 subregister pseudos");
-
-  Context.expect((*AlreadyTied)->operandAt(1)->registerValue() == *Satisfied,
-                 "an already-satisfied tie must remain unchanged");
-  Context.expect(
-      (*UndefTied)->operandAt(1)->registerValue() == *UndefDestination &&
-          (*UndefTied)->operandAt(1)->registerFlags().has(rcc::RegisterOperandFlag::Undef),
-      "undef tied uses must be rewritten without a COPY");
-  Context.expect((*Commutable)->operandAt(1)->registerValue() == *CommuteDestination &&
-                     (*Commutable)->operandAt(2)->registerValue() == *CommuteSource,
-                 "commutation must satisfy a tie before COPY fallback");
-  Context.expect((*Convertible)->opcode() == testOpcode(ThreeAddressOpcode) &&
-                     !(*Convertible)->operandAt(0)->tiedOperandIndex() &&
-                     !(*Convertible)->operandAt(1)->tiedOperandIndex(),
-                 "target three-address conversion must run before COPY fallback");
-  Context.expect((*Fallback)->previous() != nullptr &&
-                     (*Fallback)->previous()->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
-                     (*Fallback)->previous()->operandAt(0)->registerValue() ==
-                         *FallbackDestination &&
-                     (*Fallback)->previous()->operandAt(1)->registerValue() == *FallbackSource &&
-                     (*Fallback)->operandAt(1)->registerValue() == *FallbackDestination,
-                 "unsatisfied ties must receive a COPY immediately before the instruction");
-
-  const auto Copies = instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::COPY));
-  const auto ImplicitDefs =
-      instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::IMPLICIT_DEF));
-  Context.expect(Copies.size() >= 5 && ImplicitDefs.size() >= 2,
-                 "subregister pseudo expansion must materialize base and lane definitions");
-  Context.expect(
-      std::ranges::any_of(Copies,
-                          [InsertDestination](const rcc::MachineInstr *Copy) {
-                            return Copy->operandAt(0)->registerValue() == *InsertDestination &&
-                                   Copy->operandAt(0)->subReg() == rcc::test::TestSubReg::Low32;
-                          }),
-      "INSERT_SUBREG must copy its inserted value into the requested destination lane");
-  const bool HasKill = std::ranges::any_of(Function.allInstructions(), [](const auto *MI) {
-    return MI->parent() != nullptr &&
-           std::ranges::any_of(MI->operands(), [](const rcc::MachineOperand &Operand) {
-             return Operand.registerFlags().has(rcc::RegisterOperandFlag::Kill);
-           });
-  });
-  const bool HasDead = std::ranges::any_of(Function.allInstructions(), [](const auto *MI) {
-    return MI->parent() != nullptr &&
-           std::ranges::any_of(MI->operands(), [](const rcc::MachineOperand &Operand) {
-             return Operand.registerFlags().has(rcc::RegisterOperandFlag::Dead);
-           });
-  });
-  Context.expect(HasKill && HasDead,
-                 "two-address rewrite must rebuild precise kill and dead flags");
-  Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(),
-                 "two-address and subregister expansion result must verify");
-
-  auto AtomicFixture = createFunction(Context, "two_address_atomic", 10, 1);
-  if (!AtomicFixture.Function || AtomicFixture.Blocks.empty())
-    return;
-  auto AtomicSource = createVReg(*AtomicFixture.Function, *I64, rcc::test::TestRegisterBank::GPR,
-                                 rcc::test::TestRegisterClass::GPR64);
-  auto AtomicDestination =
-      createVReg(*AtomicFixture.Function, *I64, rcc::test::TestRegisterBank::GPR,
-                 rcc::test::TestRegisterClass::GPR64);
-  if (!AtomicSource || !AtomicDestination)
-    return;
-  const std::array AtomicSourceDef{*AtomicSource};
-  Context.expect(buildRegisterInstruction(*AtomicFixture.Function, Target, *AtomicFixture.Blocks[0],
-                                          testOpcode(DefOpcode), AtomicSourceDef, {})
-                     .has_value(),
-                 "two-address atomicity source definition must build");
-  rcc::MachineIRBuilder AtomicBuilder(*AtomicFixture.Function, Target);
-  if (!AtomicBuilder.setInsertPoint(*AtomicFixture.Blocks[0]))
-    return;
-  auto AtomicPending = AtomicBuilder.buildInstr(testOpcode(TiedOpcode));
-  auto AtomicInstruction =
-      AtomicPending && AtomicPending->addDef(*AtomicDestination) &&
-              AtomicPending->addUse(*AtomicSource, {rcc::RegisterOperandFlag::Kill})
-          ? AtomicPending->build()
-          : rcc::Expected<rcc::MachineInstr *>{rcc::makeUnexpected(
-                rcc::ErrorCode::InternalError, "failed to build atomicity fixture")};
-  Context.expect(AtomicInstruction.has_value(),
-                 "two-address atomicity tied instruction must build");
-  if (!AtomicInstruction)
-    return;
-  auto AtomicLiveness = setSelectedSSAProperties(*AtomicFixture.Function, Target);
-  Context.expect(AtomicLiveness.has_value(), "two-address atomicity liveness rebuild must succeed");
-  if (!AtomicLiveness)
-    return;
-  AtomicFixture.Function->properties().set(rcc::MachineFunctionProperty::NoPHIs);
-  const std::size_t AtomicInstructionsBefore = AtomicFixture.Function->allInstructions().size();
-  const std::size_t AtomicRegistersBefore =
-      AtomicFixture.Function->registerInfo().virtualRegisters().size();
-  const std::uint64_t AtomicPropertiesBefore = AtomicFixture.Function->properties().rawValue();
-
-  TestInstrInfo RejectingInfo(true);
-  rcc::MachineAnalysisManager AtomicAnalyses;
-  rcc::TwoAddressRewritePass FailingPass(RejectingInfo);
-  auto Failed = FailingPass.run(*AtomicFixture.Function, Target, AtomicAnalyses);
-  Context.expect(!Failed && Failed.error().code() == rcc::ErrorCode::Unsupported,
-                 "COPY rejection must produce a structured two-address failure");
-  Context.expect(
-      AtomicFixture.Function->allInstructions().size() == AtomicInstructionsBefore &&
-          AtomicFixture.Function->registerInfo().virtualRegisters().size() ==
-              AtomicRegistersBefore &&
-          AtomicFixture.Function->properties().rawValue() == AtomicPropertiesBefore &&
-          (*AtomicInstruction)->operandAt(0)->registerValue() == *AtomicDestination &&
-          (*AtomicInstruction)->operandAt(1)->registerValue() == *AtomicSource &&
-          (*AtomicInstruction)->operandAt(1)->registerFlags().has(rcc::RegisterOperandFlag::Kill),
-      "failed two-address transaction preflight must leave the original function unchanged");
-
-  rcc::TwoAddressRewritePass MissingBehavior;
-  auto Missing = MissingBehavior.run(*AtomicFixture.Function, Target, AtomicAnalyses);
-  Context.expect(!Missing && Missing.error().code() == rcc::ErrorCode::InvalidArgument,
-                 "two-address rewrite without target behavior must fail explicitly");
-}
-
-void testVerifierAndPseudoFailures(TestContext &Context, const rcc::TargetDescription &Target) {
-  auto BuildBadPhi = [&](std::uint64_t ID, rcc::LLT DestinationType,
-                         rcc::RegisterBankID DestinationBank, rcc::RegisterClassID DestinationClass,
-                         rcc::LLT SourceType, rcc::RegisterBankID SourceBank,
-                         rcc::RegisterClassID SourceClass, rcc::SubRegIndex SourceSubReg = {}) {
-    auto Fixture = createFunction(Context, "bad_phi", ID, 2);
-    if (!Fixture.Function || Fixture.Blocks.size() != 2)
-      return Fixture;
-    auto Destination =
-        createVReg(*Fixture.Function, DestinationType, DestinationBank, DestinationClass);
-    auto Source = createVReg(*Fixture.Function, SourceType, SourceBank, SourceClass);
-    if (!Destination || !Source)
-      return Fixture;
-    auto CFG = Fixture.Function->cfgUpdater();
-    if (!CFG.addSuccessor(*Fixture.Blocks[0], *Fixture.Blocks[1], rcc::BranchProbability::one())) {
-      return Fixture;
-    }
-    const std::array SourceDef{*Source};
-    if (!buildRegisterInstruction(*Fixture.Function, Target, *Fixture.Blocks[0],
-                                  testOpcode(DefOpcode), SourceDef, {})) {
-      return Fixture;
-    }
-    rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
-    if (!Builder.setInsertPoint(*Fixture.Blocks[1]))
-      return Fixture;
-    auto Phi = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI));
-    if (!Phi || !Phi->addDef(*Destination) || !Phi->addUse(*Source, {}, SourceSubReg) ||
-        !Phi->addBasicBlock(*Fixture.Blocks[0]) || !Phi->build()) {
-      return Fixture;
-    }
-    return Fixture;
-  };
-
-  auto I64 = rcc::LLT::makeInteger(64);
-  auto I32 = rcc::LLT::makeInteger(32);
-  if (!I64 || !I32)
-    return;
-  auto BadType =
-      BuildBadPhi(6, *I64, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR64,
-                  *I32, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR32);
-  Context.expect(BadType.Function && !rcc::MachineVerifier::verify(*BadType.Function, Target),
-                 "MachineVerifier must reject incompatible PHI LLTs");
-
-  auto BadClass =
-      BuildBadPhi(7, *I64, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR64,
-                  *I64, rcc::test::TestRegisterBank::FPR, rcc::test::TestRegisterClass::FPR64);
-  Context.expect(BadClass.Function && !rcc::MachineVerifier::verify(*BadClass.Function, Target),
-                 "MachineVerifier must reject nonoverlapping PHI register classes");
-
-  auto BadSubReg =
-      BuildBadPhi(8, *I32, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR32Low,
-                  *I64, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR64,
-                  rcc::test::TestSubReg::High32);
-  Context.expect(BadSubReg.Function && !rcc::MachineVerifier::verify(*BadSubReg.Function, Target),
-                 "MachineVerifier must reject incompatible PHI subregister projections");
-
-  auto Residual = createFunction(Context, "residual_stage10_pseudo", 9, 1);
-  if (!Residual.Function || Residual.Blocks.empty())
-    return;
-  auto Destination = createVReg(*Residual.Function, *I64, rcc::test::TestRegisterBank::GPR,
-                                rcc::test::TestRegisterClass::GPR64);
-  auto Source = createVReg(*Residual.Function, *I32, rcc::test::TestRegisterBank::GPR,
-                           rcc::test::TestRegisterClass::GPR32);
-  if (!Destination || !Source)
-    return;
-  rcc::MachineIRBuilder Builder(*Residual.Function, Target);
-  if (!Builder.setInsertPoint(*Residual.Blocks[0]))
-    return;
-  auto Sequence = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::REG_SEQUENCE));
-  Context.expect(Sequence && Sequence->addDef(*Destination) && Sequence->addUse(*Source) &&
-                     Sequence->addImmediate(rcc::test::TestSubReg::Low32.value()) &&
-                     Sequence->build(),
-                 "residual Stage 10 pseudo fixture must be built");
-  for (rcc::MachineFunctionProperty Property :
-       {rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected,
-        rcc::MachineFunctionProperty::Selected, rcc::MachineFunctionProperty::NoPHIs,
-        rcc::MachineFunctionProperty::TiedOpsRewritten}) {
-    Residual.Function->properties().set(Property);
-  }
-  Context.expect(!rcc::MachineVerifier::verify(*Residual.Function, Target),
-                 "TiedOpsRewritten must reject residual REG_SEQUENCE/INSERT_SUBREG pseudos");
-}
-
-} // namespace
-
-int main() {
-  TestContext Context;
-  auto Target = createTarget();
-  Context.expect(Target.has_value(), "SSA-exit TestTarget must be created");
-  if (!Target)
-    return Context.result();
-  TestInstrInfo Info;
-  testParallelPHIsAndPlacement(Context, *Target, Info);
-  testCriticalEdgeAndPhysicalLiveIn(Context, *Target, Info);
-  testUndefAndFailureAtomicity(Context, *Target, Info);
-  testTwoAddressAndSubregisterPseudos(Context, *Target, Info);
-  testVerifierAndPseudoFailures(Context, *Target);
-  return Context.result();
-}
diff --git a/backend/unittests/CodeGen/PHIEliminationTest.cpp b/backend/unittests/CodeGen/PHIEliminationTest.cpp
new file mode 100644
index 0000000..00668e4
--- /dev/null
+++ b/backend/unittests/CodeGen/PHIEliminationTest.cpp
@@ -0,0 +1,479 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/PHIElimination.h"
+
+#include "SSAExitTestSupport.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+
+#include <array>
+#include <memory>
+#include <utility>
+
+namespace {
+
+using namespace rcc::test::ssa;
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *> buildJump(rcc::MachineFunction &Function,
+                                                           const rcc::TargetDescription &Target,
+                                                           rcc::MachineBasicBlock &Block,
+                                                           rcc::MachineBasicBlock &Destination) {
+  rcc::MachineIRBuilder Builder(Function, Target);
+  auto Point = Builder.setInsertPoint(Block);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(testOpcode(JumpOpcode));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  auto TargetOperand = Pending->addBasicBlock(Destination);
+  if (!TargetOperand)
+    return std::unexpected(TargetOperand.error());
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildPhi(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+         rcc::MachineBasicBlock &Block, rcc::Register Destination,
+         std::span<const std::pair<rcc::Register, rcc::MachineBasicBlock *>> Incoming,
+         rcc::RegisterOperandFlags DestinationFlags = {}, std::uint32_t DestinationTargetFlags = 0,
+         rcc::RegisterOperandFlags IncomingFlags = {}, std::uint32_t IncomingTargetFlags = 0) {
+  rcc::MachineIRBuilder Builder(Function, Target);
+  auto Point = Builder.setInsertPoint(Block);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  auto Def = Pending->addDef(Destination, DestinationFlags, {}, DestinationTargetFlags);
+  if (!Def)
+    return std::unexpected(Def.error());
+  for (const auto &[Value, Predecessor] : Incoming) {
+    auto Use = Pending->addUse(Value, IncomingFlags, {}, IncomingTargetFlags);
+    if (!Use)
+      return std::unexpected(Use.error());
+    auto IncomingBlock = Pending->addBasicBlock(*Predecessor);
+    if (!IncomingBlock)
+      return std::unexpected(IncomingBlock.error());
+  }
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<void> runPHIElimination(rcc::MachineFunction &Function,
+                                                    const rcc::TargetDescription &Target,
+                                                    const rcc::TargetInstrInfo &Info) {
+  rcc::MachinePassManager Pipeline;
+  auto Added = Pipeline.addPass(std::make_unique<rcc::PHIEliminationPass>(Info));
+  if (!Added)
+    return std::unexpected(Added.error());
+  rcc::MachineAnalysisManager Analyses;
+  return Pipeline.run(Function, Target, Analyses);
+}
+
+[[nodiscard]] std::vector<rcc::MachineInstr *> linkedInstructions(rcc::MachineBasicBlock &Block) {
+  std::vector<rcc::MachineInstr *> Result;
+  for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    Result.push_back(Instruction);
+  }
+  return Result;
+}
+
+[[nodiscard]] bool hasLiveIn(const rcc::MachineBasicBlock &Block, rcc::PhysicalRegister Reg) {
+  return std::ranges::any_of(Block.liveIns(), [Reg](const rcc::MachineBasicBlockLiveIn &LiveIn) {
+    return LiveIn.PhysReg == Reg;
+  });
+}
+
+void testParallelPHIsAndPlacement(TestContext &Context, const rcc::TargetDescription &Target,
+                                  const TestInstrInfo &Info) {
+  auto Fixture = createFunction(Context, "parallel_phis", 1, 3);
+  if (!Fixture.Function || Fixture.Blocks.size() != 3)
+    return;
+  auto I64 = rcc::LLT::makeInteger(64);
+  if (!I64)
+    return;
+  auto &Function = *Fixture.Function;
+  rcc::MachineBasicBlock &Preheader = *Fixture.Blocks[0];
+  rcc::MachineBasicBlock &Header = *Fixture.Blocks[1];
+  rcc::MachineBasicBlock &Backedge = *Fixture.Blocks[2];
+  const rcc::PhysicalRegister Hint = *rcc::PhysicalRegister::create(rcc::test::TestRegister::G1);
+
+  auto InitA = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+                          rcc::test::TestRegisterClass::GPR64);
+  auto InitB = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+                          rcc::test::TestRegisterClass::GPR64);
+  auto DestinationA = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+                                 rcc::test::TestRegisterClass::GPR64, 0x1, Hint);
+  auto DestinationB = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+                                 rcc::test::TestRegisterClass::GPR64);
+  Context.expect(InitA && InitB && DestinationA && DestinationB,
+                 "parallel PHI registers must be created");
+  if (!InitA || !InitB || !DestinationA || !DestinationB)
+    return;
+
+  auto CFG = Function.cfgUpdater();
+  Context.expect(
+      CFG.addSuccessor(Preheader, Header, rcc::BranchProbability::one()).has_value() &&
+          CFG.addSuccessor(Header, Backedge, rcc::BranchProbability::one()).has_value() &&
+          CFG.addSuccessor(Backedge, Header, rcc::BranchProbability::one()).has_value(),
+      "parallel PHI loop CFG must be connected");
+
+  const std::array InitADef{*InitA};
+  const std::array InitBDef{*InitB};
+  Context.expect(buildRegisterInstruction(Function, Target, Preheader, testOpcode(DefOpcode),
+                                          InitADef, {}, {rcc::RegisterOperandFlag::Dead}) &&
+                     buildRegisterInstruction(Function, Target, Preheader, testOpcode(DefOpcode),
+                                              InitBDef, {}) &&
+                     buildJump(Function, Target, Preheader, Header),
+                 "parallel PHI preheader must be populated");
+
+  const std::array IncomingA{
+      std::pair<rcc::Register, rcc::MachineBasicBlock *>{*InitA, &Preheader},
+      std::pair<rcc::Register, rcc::MachineBasicBlock *>{*DestinationB, &Backedge}};
+  const std::array IncomingB{
+      std::pair<rcc::Register, rcc::MachineBasicBlock *>{*InitB, &Preheader},
+      std::pair<rcc::Register, rcc::MachineBasicBlock *>{*DestinationA, &Backedge}};
+  Context.expect(buildPhi(Function, Target, Header, *DestinationA, IncomingA, {}, 0x4, {}, 0x8) &&
+                     buildPhi(Function, Target, Header, *DestinationB, IncomingB),
+                 "parallel PHIs must be built");
+
+  rcc::MachineIRBuilder HeaderBuilder(Function, Target);
+  if (!HeaderBuilder.setInsertPoint(Header))
+    return;
+  auto Meta = HeaderBuilder.buildInstr(testOpcode(MetaOpcode));
+  const std::array HeaderUse{*DestinationA};
+  Context.expect(Meta && Meta->build() &&
+                     buildRegisterInstruction(Function, Target, Header, testOpcode(UseOpcode), {},
+                                              HeaderUse) &&
+                     buildJump(Function, Target, Header, Backedge),
+                 "parallel PHI header must contain meta, code, and terminator instructions");
+
+  const std::array KilledUse{*DestinationA};
+  Context.expect(buildRegisterInstruction(Function, Target, Backedge, testOpcode(UseOpcode), {},
+                                          KilledUse, {}, {rcc::RegisterOperandFlag::Kill}) &&
+                     buildJump(Function, Target, Backedge, Header),
+                 "parallel PHI backedge must be populated");
+  auto InitialLiveness = setSelectedSSAProperties(Function, Target);
+  Context.expect(InitialLiveness.has_value(), "parallel PHI liveness rebuild must succeed");
+  if (!InitialLiveness)
+    return;
+
+  auto Run = runPHIElimination(Function, Target, Info);
+  Context.expect(Run.has_value(), "parallel PHI elimination must succeed");
+  if (!Run)
+    return;
+  Context.expect(!Function.properties().has(rcc::MachineFunctionProperty::IsSSA) &&
+                     Function.properties().has(rcc::MachineFunctionProperty::NoPHIs) &&
+                     Function.properties().has(rcc::MachineFunctionProperty::TracksLiveness),
+                 "PHI elimination must publish its exact property transition");
+  Context.expect(instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::PHI)).empty(),
+                 "PHI elimination must remove every PHI");
+
+  const auto HeaderInstructions = linkedInstructions(Header);
+  Context.expect(HeaderInstructions.size() == 5 &&
+                     HeaderInstructions[0]->opcode() == testOpcode(MetaOpcode) &&
+                     HeaderInstructions[1]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+                     HeaderInstructions[2]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+                     HeaderInstructions[3]->opcode() == testOpcode(UseOpcode) &&
+                     HeaderInstructions[4]->opcode() == testOpcode(JumpOpcode),
+                 "destination COPYs must follow the full leading PHI/meta region");
+  if (HeaderInstructions.size() < 3)
+    return;
+
+  const rcc::Register *FreshA = HeaderInstructions[1]->operandAt(1)->getIf<rcc::Register>();
+  const rcc::Register *FreshB = HeaderInstructions[2]->operandAt(1)->getIf<rcc::Register>();
+  Context.expect(FreshA != nullptr && FreshB != nullptr && *FreshA != *FreshB &&
+                     *FreshA != *DestinationA && *FreshB != *DestinationB,
+                 "each PHI must receive an independent fresh incoming vreg");
+  if (FreshA == nullptr || FreshB == nullptr)
+    return;
+
+  const auto BackedgeInstructions = linkedInstructions(Backedge);
+  Context.expect(BackedgeInstructions.size() == 4 &&
+                     BackedgeInstructions[1]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+                     BackedgeInstructions[2]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+                     BackedgeInstructions[3]->opcode() == testOpcode(JumpOpcode),
+                 "incoming COPYs must be placed together before the first terminator");
+  if (BackedgeInstructions.size() >= 3) {
+    const auto FirstDef = BackedgeInstructions[1]->operandAt(0)->registerValue();
+    const auto FirstUse = BackedgeInstructions[1]->operandAt(1)->registerValue();
+    const auto SecondDef = BackedgeInstructions[2]->operandAt(0)->registerValue();
+    const auto SecondUse = BackedgeInstructions[2]->operandAt(1)->registerValue();
+    Context.expect(FirstDef == *FreshA && FirstUse == *DestinationB && SecondDef == *FreshB &&
+                       SecondUse == *DestinationA,
+                   "backedge COPYs must read old PHI destinations into distinct temporaries");
+  }
+
+  auto FreshInfo = Function.registerInfo().virtualRegisterInfo(*FreshA);
+  Context.expect(FreshInfo.has_value(), "fresh PHI vreg must remain registered");
+  if (!FreshInfo)
+    return;
+  Context.expect(FreshInfo->get().Type == I64, "fresh PHI vreg must clone its LLT");
+  Context.expect(FreshInfo->get().Bank == rcc::test::TestRegisterBank::GPR,
+                 "fresh PHI vreg must clone its register bank");
+  Context.expect(FreshInfo->get().RegClass == rcc::test::TestRegisterClass::GPR64,
+                 "fresh PHI vreg must clone its register class");
+  Context.expect(FreshInfo->get().TargetFlags == 0x1,
+                 "fresh PHI vreg must clone registered target flags");
+  Context.expect(FreshInfo->get().AllocationHints.size() == 1,
+                 "fresh PHI vreg must clone the allocation-hint count");
+  Context.expect(!FreshInfo->get().AllocationHints.empty() &&
+                     FreshInfo->get().AllocationHints.front() == Hint,
+                 "fresh PHI vreg must clone the allocation-hint register");
+  Context.expect(HeaderInstructions[1]->operandAt(0)->targetFlags() == 0x4 &&
+                     HeaderInstructions[1]->operandAt(1)->targetFlags() == 0x4,
+                 "successor COPY must preserve registered destination target flags");
+
+  const rcc::MachineInstr *InitDefinition = Preheader.firstInstruction();
+  Context.expect(
+      InitDefinition != nullptr &&
+          !InitDefinition->operandAt(0)->registerFlags().has(rcc::RegisterOperandFlag::Dead) &&
+          !BackedgeInstructions[0]->operandAt(0)->registerFlags().has(
+              rcc::RegisterOperandFlag::Kill),
+      "liveness-preserving PHI elimination must conservatively clear kill/dead flags");
+  Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(),
+                 "parallel PHI result must pass MachineVerifier");
+}
+
+void testCriticalEdgeAndPhysicalLiveIn(TestContext &Context, const rcc::TargetDescription &Target,
+                                       const TestInstrInfo &Info) {
+  auto Fixture = createFunction(Context, "critical_edge", 2, 4);
+  if (!Fixture.Function || Fixture.Blocks.size() != 4)
+    return;
+  auto I64 = rcc::LLT::makeInteger(64);
+  if (!I64)
+    return;
+  auto &Function = *Fixture.Function;
+  rcc::MachineBasicBlock &From = *Fixture.Blocks[0];
+  rcc::MachineBasicBlock &Side = *Fixture.Blocks[1];
+  rcc::MachineBasicBlock &Other = *Fixture.Blocks[2];
+  rcc::MachineBasicBlock &Merge = *Fixture.Blocks[3];
+  auto Condition = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+                              rcc::test::TestRegisterClass::GPR64);
+  auto OtherValue = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+                               rcc::test::TestRegisterClass::GPR64);
+  auto Destination = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+                                rcc::test::TestRegisterClass::GPR64);
+  if (!Condition || !OtherValue || !Destination)
+    return;
+
+  auto Half = rcc::BranchProbability::fromFraction(1, 2);
+  auto CFG = Function.cfgUpdater();
+  Context.expect(Half && CFG.addSuccessor(From, Side, *Half) &&
+                     CFG.addSuccessor(From, Merge, *Half) &&
+                     CFG.addSuccessor(Other, Merge, rcc::BranchProbability::one()),
+                 "critical-edge CFG must be connected");
+
+  const std::array ConditionDef{*Condition};
+  Context.expect(
+      buildRegisterInstruction(Function, Target, From, testOpcode(DefOpcode), ConditionDef, {})
+          .has_value(),
+      "critical-edge condition must be defined");
+  rcc::MachineIRBuilder FromBuilder(Function, Target);
+  if (!FromBuilder.setInsertPoint(From))
+    return;
+  auto Branch = FromBuilder.buildInstr(testOpcode(ConditionalBranchOpcode));
+  Context.expect(Branch && Branch->addUse(*Condition) && Branch->addBasicBlock(Merge) &&
+                     Branch->build(),
+                 "critical-edge conditional branch must be built");
+  const std::array OtherDef{*OtherValue};
+  Context.expect(
+      buildRegisterInstruction(Function, Target, Other, testOpcode(DefOpcode), OtherDef, {})
+          .has_value(),
+      "unrelated fallthrough predecessor must define its incoming value");
+
+  const rcc::PhysicalRegister G0 = *rcc::PhysicalRegister::create(rcc::test::TestRegister::G0);
+  const rcc::PhysicalRegister G1 = *rcc::PhysicalRegister::create(rcc::test::TestRegister::G1);
+  Context.expect(Merge.addLiveIn(G1, rcc::LaneMask::fromRaw(0xF)).has_value(),
+                 "merge block live-in setup must succeed");
+  const std::array Incoming{
+      std::pair<rcc::Register, rcc::MachineBasicBlock *>{rcc::Register::fromPhysical(G0), &From},
+      std::pair<rcc::Register, rcc::MachineBasicBlock *>{*OtherValue, &Other}};
+  Context.expect(buildPhi(Function, Target, Merge, *Destination, Incoming).has_value(),
+                 "critical-edge PHI must be built");
+  const std::array G1Use{rcc::Register::fromPhysical(G1)};
+  Context.expect(buildRegisterInstruction(Function, Target, Merge, testOpcode(UseOpcode), {}, G1Use)
+                     .has_value(),
+                 "merge block must consume its inherited physical live-in");
+  auto InitialLiveness = setSelectedSSAProperties(Function, Target);
+  Context.expect(InitialLiveness.has_value(), "critical-edge PHI liveness rebuild must succeed");
+  if (!InitialLiveness)
+    return;
+
+  auto Run = runPHIElimination(Function, Target, Info);
+  Context.expect(Run.has_value(), "critical-edge PHI elimination must succeed");
+  if (!Run)
+    return;
+
+  rcc::MachineBasicBlock *Edge = Merge.previous();
+  Context.expect(
+      Edge != nullptr && Edge != &Other && Edge->previous() == &Other &&
+          From.successors().size() == 2 &&
+          std::ranges::any_of(From.successors(),
+                              [Edge](const rcc::MachineSuccessor &S) { return S.Block == Edge; }) &&
+          Edge->predecessors().size() == 1 && Edge->predecessors()[0] == &From &&
+          Edge->successors().size() == 1 && Edge->successors()[0].Block == &Merge,
+      "critical edge must become a reciprocal From-to-edge-to-Merge CFG path");
+  if (Edge == nullptr || Edge == &Other)
+    return;
+
+  const rcc::MachineOperand *BranchTarget = From.lastInstruction()->operandAt(1);
+  const auto *BranchBlock =
+      BranchTarget == nullptr ? nullptr : BranchTarget->getIf<rcc::BasicBlockOperand>();
+  Context.expect(BranchBlock != nullptr && BranchBlock->Block == Edge,
+                 "explicit critical-edge branch must target the split block");
+  const auto OtherInstructions = linkedInstructions(Other);
+  const auto EdgeInstructions = linkedInstructions(*Edge);
+  Context.expect(OtherInstructions.size() == 3 &&
+                     OtherInstructions.back()->opcode() == testOpcode(JumpOpcode) &&
+                     EdgeInstructions.size() == 2 &&
+                     EdgeInstructions[0]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+                     EdgeInstructions[1]->opcode() == testOpcode(JumpOpcode),
+                 "edge split must preserve unrelated fallthrough and terminator placement");
+  Context.expect(hasLiveIn(*Edge, G0) && hasLiveIn(*Edge, G1),
+                 "split edge must inherit successor live-ins and its physical PHI source");
+  Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(),
+                 "critical-edge result must pass MachineVerifier");
+}
+
+void testUndefAndFailureAtomicity(TestContext &Context, const rcc::TargetDescription &Target,
+                                  const TestInstrInfo &Info) {
+  auto BuildFixture = [&](std::uint64_t ID) {
+    auto Fixture = createFunction(Context, "undef_phi", ID, 2);
+    if (!Fixture.Function || Fixture.Blocks.size() != 2)
+      return Fixture;
+    auto I64 = rcc::LLT::makeInteger(64);
+    if (!I64)
+      return Fixture;
+    auto Source = createVReg(*Fixture.Function, *I64, rcc::test::TestRegisterBank::GPR,
+                             rcc::test::TestRegisterClass::GPR64);
+    auto Destination = createVReg(*Fixture.Function, *I64, rcc::test::TestRegisterBank::GPR,
+                                  rcc::test::TestRegisterClass::GPR64);
+    if (!Source || !Destination)
+      return Fixture;
+    auto CFG = Fixture.Function->cfgUpdater();
+    if (!CFG.addSuccessor(*Fixture.Blocks[0], *Fixture.Blocks[1], rcc::BranchProbability::one()) ||
+        !buildJump(*Fixture.Function, Target, *Fixture.Blocks[0], *Fixture.Blocks[1])) {
+      return Fixture;
+    }
+    const std::array Incoming{
+        std::pair<rcc::Register, rcc::MachineBasicBlock *>{*Source, Fixture.Blocks[0]}};
+    if (!buildPhi(*Fixture.Function, Target, *Fixture.Blocks[1], *Destination, Incoming, {}, 0,
+                  {rcc::RegisterOperandFlag::Undef})) {
+      return Fixture;
+    }
+    Context.expect(setSelectedSSAProperties(*Fixture.Function, Target).has_value(),
+                   "undef PHI liveness rebuild must succeed");
+    return Fixture;
+  };
+
+  auto Undef = BuildFixture(3);
+  if (!Undef.Function)
+    return;
+  auto Run = runPHIElimination(*Undef.Function, Target, Info);
+  Context.expect(Run.has_value(), "undef PHI elimination must succeed");
+  if (Run) {
+    const auto PredecessorInstructions = linkedInstructions(*Undef.Blocks[0]);
+    Context.expect(PredecessorInstructions.size() == 2 &&
+                       PredecessorInstructions[0]->opcode() ==
+                           rcc::opcode(rcc::GenericOpcode::IMPLICIT_DEF) &&
+                       PredecessorInstructions[1]->opcode() == testOpcode(JumpOpcode),
+                   "undef PHI incoming values must become edge IMPLICIT_DEF instructions");
+  }
+
+  auto Atomic = BuildFixture(4);
+  if (!Atomic.Function)
+    return;
+  const std::size_t BlocksBefore = Atomic.Function->blockCount();
+  const std::size_t InstructionsBefore =
+      instructionsWithOpcode(*Atomic.Function, rcc::opcode(rcc::GenericOpcode::PHI)).size();
+  const std::size_t RegistersBefore = Atomic.Function->registerInfo().virtualRegisters().size();
+  const std::uint64_t PropertiesBefore = Atomic.Function->properties().rawValue();
+  TestInstrInfo RejectingInfo(true);
+  rcc::MachineAnalysisManager Analyses;
+  rcc::PHIEliminationPass FailingPass(RejectingInfo);
+  auto Failed = FailingPass.run(*Atomic.Function, Target, Analyses);
+  Context.expect(!Failed && Failed.error().code() == rcc::ErrorCode::Unsupported,
+                 "COPY rejection must produce a structured PHI-elimination failure");
+  Context.expect(
+      Atomic.Function->blockCount() == BlocksBefore &&
+          instructionsWithOpcode(*Atomic.Function, rcc::opcode(rcc::GenericOpcode::PHI)).size() ==
+              InstructionsBefore &&
+          Atomic.Function->registerInfo().virtualRegisters().size() == RegistersBefore &&
+          Atomic.Function->properties().rawValue() == PropertiesBefore,
+      "failed PHI transaction preflight must leave the original function unchanged");
+}
+
+void testMalformedPHIs(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto BuildBadPhi = [&](std::uint64_t ID, rcc::LLT DestinationType,
+                         rcc::RegisterBankID DestinationBank, rcc::RegisterClassID DestinationClass,
+                         rcc::LLT SourceType, rcc::RegisterBankID SourceBank,
+                         rcc::RegisterClassID SourceClass, rcc::SubRegIndex SourceSubReg = {}) {
+    auto Fixture = createFunction(Context, "bad_phi", ID, 2);
+    if (!Fixture.Function || Fixture.Blocks.size() != 2)
+      return Fixture;
+    auto Destination =
+        createVReg(*Fixture.Function, DestinationType, DestinationBank, DestinationClass);
+    auto Source = createVReg(*Fixture.Function, SourceType, SourceBank, SourceClass);
+    if (!Destination || !Source)
+      return Fixture;
+    auto CFG = Fixture.Function->cfgUpdater();
+    if (!CFG.addSuccessor(*Fixture.Blocks[0], *Fixture.Blocks[1], rcc::BranchProbability::one())) {
+      return Fixture;
+    }
+    const std::array SourceDef{*Source};
+    if (!buildRegisterInstruction(*Fixture.Function, Target, *Fixture.Blocks[0],
+                                  testOpcode(DefOpcode), SourceDef, {})) {
+      return Fixture;
+    }
+    rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
+    if (!Builder.setInsertPoint(*Fixture.Blocks[1]))
+      return Fixture;
+    auto Phi = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI));
+    if (!Phi || !Phi->addDef(*Destination) || !Phi->addUse(*Source, {}, SourceSubReg) ||
+        !Phi->addBasicBlock(*Fixture.Blocks[0]) || !Phi->build()) {
+      return Fixture;
+    }
+    return Fixture;
+  };
+
+  auto I64 = rcc::LLT::makeInteger(64);
+  auto I32 = rcc::LLT::makeInteger(32);
+  if (!I64 || !I32)
+    return;
+  auto BadType =
+      BuildBadPhi(6, *I64, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR64,
+                  *I32, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR32);
+  Context.expect(BadType.Function && !rcc::MachineVerifier::verify(*BadType.Function, Target),
+                 "MachineVerifier must reject incompatible PHI LLTs");
+
+  auto BadClass =
+      BuildBadPhi(7, *I64, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR64,
+                  *I64, rcc::test::TestRegisterBank::FPR, rcc::test::TestRegisterClass::FPR64);
+  Context.expect(BadClass.Function && !rcc::MachineVerifier::verify(*BadClass.Function, Target),
+                 "MachineVerifier must reject nonoverlapping PHI register classes");
+
+  auto BadSubReg =
+      BuildBadPhi(8, *I32, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR32Low,
+                  *I64, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR64,
+                  rcc::test::TestSubReg::High32);
+  Context.expect(BadSubReg.Function && !rcc::MachineVerifier::verify(*BadSubReg.Function, Target),
+                 "MachineVerifier must reject incompatible PHI subregister projections");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  auto Target = createTarget();
+  Context.expect(Target.has_value(), "PHI-elimination TestTarget must be created");
+  if (!Target)
+    return Context.result();
+  TestInstrInfo Info;
+  testParallelPHIsAndPlacement(Context, *Target, Info);
+  testCriticalEdgeAndPhysicalLiveIn(Context, *Target, Info);
+  testUndefAndFailureAtomicity(Context, *Target, Info);
+  testMalformedPHIs(Context, *Target);
+  return Context.result();
+}
diff --git a/backend/unittests/CodeGen/SSAExitTestSupport.h b/backend/unittests/CodeGen/SSAExitTestSupport.h
new file mode 100644
index 0000000..a5eeff1
--- /dev/null
+++ b/backend/unittests/CodeGen/SSAExitTestSupport.h
@@ -0,0 +1,444 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+// This private test header has no stable include-root-relative guard name.
+// NOLINTNEXTLINE(llvm-header-guard)
+#ifndef RCC_BACKEND_SSA_EXIT_TEST_SUPPORT_H
+#define RCC_BACKEND_SSA_EXIT_TEST_SUPPORT_H
+
+#include "Target/TestTarget.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/MachineLiveness.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/CodeGen/TargetInstrInfo.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#include <optional>
+#include <ranges>
+#include <span>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace rcc::test::ssa {
+
+constexpr std::uint32_t DefOpcode = 1024;
+constexpr std::uint32_t UseOpcode = 1025;
+constexpr std::uint32_t ConditionalBranchOpcode = 1026;
+constexpr std::uint32_t JumpOpcode = 1027;
+constexpr std::uint32_t ReturnOpcode = 1028;
+constexpr std::uint32_t MetaOpcode = 1029;
+constexpr std::uint32_t TiedOpcode = 1030;
+constexpr std::uint32_t CommutableTiedOpcode = 1031;
+constexpr std::uint32_t ConvertibleTiedOpcode = 1032;
+constexpr std::uint32_t ThreeAddressOpcode = 1033;
+
+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;
+};
+
+[[nodiscard]] inline rcc::Opcode testOpcode(std::uint32_t Value) {
+  return rcc::Opcode::fromValue(Value);
+}
+
+[[nodiscard]] inline rcc::OperandDescriptor registerOperand(rcc::RegisterOperandRole Role,
+                                                            bool AllowSubReg = true) {
+  rcc::OperandDescriptor Result;
+  Result.Kinds = {rcc::MachineOperand::Kind::Register};
+  Result.RegisterRole = Role;
+  Result.AllowSubReg = AllowSubReg;
+  Result.AllowAnyTargetFlags = true;
+  return Result;
+}
+
+[[nodiscard]] inline rcc::OperandDescriptor blockOperand() {
+  rcc::OperandDescriptor Result;
+  Result.Kinds = {rcc::MachineOperand::Kind::BasicBlock};
+  return Result;
+}
+
+[[nodiscard]] inline rcc::InstructionDescriptor instruction(std::uint32_t Value, std::string Name) {
+  rcc::InstructionDescriptor Result;
+  Result.InstructionOpcode = testOpcode(Value);
+  Result.Name = std::move(Name);
+  Result.Flags = {rcc::InstructionFlag::ProducesCode};
+  return Result;
+}
+
+[[nodiscard]] inline rcc::Expected<rcc::TargetDescription> createTarget() {
+  std::vector<rcc::InstructionDescriptor> Descriptors;
+  std::vector<rcc::ImmediatePredicate> Predicates;
+  auto Generic = rcc::appendGenericInstructionInfo(Descriptors, Predicates);
+  if (!Generic)
+    return std::unexpected(Generic.error());
+
+  auto Def = instruction(DefOpcode, "TEST_DEF");
+  Def.Operands = {registerOperand(rcc::RegisterOperandRole::Def)};
+  Def.NumExplicitDefs = 1;
+  Descriptors.push_back(std::move(Def));
+
+  auto Use = instruction(UseOpcode, "TEST_USE");
+  Use.Operands = {registerOperand(rcc::RegisterOperandRole::Use)};
+  Descriptors.push_back(std::move(Use));
+
+  auto Conditional = instruction(ConditionalBranchOpcode, "TEST_BRCOND");
+  Conditional.Operands = {registerOperand(rcc::RegisterOperandRole::Use, false), blockOperand()};
+  Conditional.Flags.set(rcc::InstructionFlag::Branch);
+  Conditional.Flags.set(rcc::InstructionFlag::Terminator);
+  Descriptors.push_back(std::move(Conditional));
+
+  auto Jump = instruction(JumpOpcode, "TEST_JUMP");
+  Jump.Operands = {blockOperand()};
+  Jump.Flags.set(rcc::InstructionFlag::Branch);
+  Jump.Flags.set(rcc::InstructionFlag::Terminator);
+  Jump.Flags.set(rcc::InstructionFlag::Barrier);
+  Descriptors.push_back(std::move(Jump));
+
+  auto Return = instruction(ReturnOpcode, "TEST_RETURN");
+  Return.Flags.set(rcc::InstructionFlag::Return);
+  Return.Flags.set(rcc::InstructionFlag::Terminator);
+  Return.Flags.set(rcc::InstructionFlag::Barrier);
+  Descriptors.push_back(std::move(Return));
+
+  auto Meta = instruction(MetaOpcode, "TEST_META");
+  Meta.Flags = {rcc::InstructionFlag::Pseudo, rcc::InstructionFlag::Meta};
+  Descriptors.push_back(std::move(Meta));
+
+  auto Tied = instruction(TiedOpcode, "TEST_TIED");
+  auto TiedDef = registerOperand(rcc::RegisterOperandRole::Def);
+  auto TiedUse = registerOperand(rcc::RegisterOperandRole::Use);
+  TiedDef.DefaultTiedOperand = 1;
+  TiedUse.DefaultTiedOperand = 0;
+  Tied.Operands = {TiedDef, TiedUse};
+  Tied.NumExplicitDefs = 1;
+  Descriptors.push_back(std::move(Tied));
+
+  auto Commutable = instruction(CommutableTiedOpcode, "TEST_COMMUTABLE_TIED");
+  Commutable.Operands = {TiedDef, TiedUse, registerOperand(rcc::RegisterOperandRole::Use)};
+  Commutable.NumExplicitDefs = 1;
+  Commutable.Flags.set(rcc::InstructionFlag::Commutable);
+  Descriptors.push_back(std::move(Commutable));
+
+  auto Convertible = instruction(ConvertibleTiedOpcode, "TEST_CONVERTIBLE_TIED");
+  Convertible.Operands = {TiedDef, TiedUse};
+  Convertible.NumExplicitDefs = 1;
+  Descriptors.push_back(std::move(Convertible));
+
+  auto ThreeAddress = instruction(ThreeAddressOpcode, "TEST_THREE_ADDRESS");
+  ThreeAddress.Operands = {registerOperand(rcc::RegisterOperandRole::Def),
+                           registerOperand(rcc::RegisterOperandRole::Use)};
+  ThreeAddress.NumExplicitDefs = 1;
+  Descriptors.push_back(std::move(ThreeAddress));
+
+  auto Instructions = rcc::InstructionSet::create(std::move(Descriptors), std::move(Predicates));
+  if (!Instructions)
+    return std::unexpected(Instructions.error());
+  return rcc::test::createTestTargetDescription(std::move(*Instructions));
+}
+
+class TestInstrInfo final : public rcc::TargetInstrInfo {
+public:
+  explicit TestInstrInfo(bool RejectCopies = false) : RejectCopies(RejectCopies) {}
+
+  [[nodiscard]] rcc::Expected<rcc::MachineBranchAnalysis>
+  analyzeBranch(rcc::MachineBasicBlock &, rcc::MachineFunction &,
+                const rcc::TargetDescription &) const override {
+    return rcc::MachineBranchAnalysis{};
+  }
+
+  [[nodiscard]] rcc::Expected<void>
+  reverseBranchCondition(rcc::MachineInstr &, rcc::MachineBasicBlock &, rcc::MachineFunction &,
+                         const rcc::TargetDescription &) const override {
+    return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, "test target has no branch reversal");
+  }
+
+  [[nodiscard]] rcc::Expected<void> removeBranch(rcc::MachineInstr &, rcc::MachineFunction &,
+                                                 const rcc::TargetDescription &) const override {
+    return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, "test target has no branch removal");
+  }
+
+  [[nodiscard]] rcc::Expected<bool>
+  isFallthroughEdge(const rcc::MachineBasicBlock &From, const rcc::MachineBasicBlock &To,
+                    const rcc::MachineFunction &Function,
+                    const rcc::TargetDescription &Target) const override {
+    if (&From.function() != &Function || &To.function() != &Function) {
+      return rcc::makeUnexpected(rcc::ErrorCode::InvalidArgument,
+                                 "fallthrough query references another function");
+    }
+    if (From.next() != &To ||
+        std::ranges::none_of(From.successors(), [&To](const rcc::MachineSuccessor &Successor) {
+          return Successor.Block == &To;
+        })) {
+      return false;
+    }
+
+    bool CanFallThrough = true;
+    for (const rcc::MachineInstr *Instruction = From.firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      const rcc::InstructionDescriptor *Descriptor =
+          Target.instructionDescriptor(Instruction->opcode());
+      if (Descriptor == nullptr) {
+        return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
+                                   "fallthrough query encountered an unknown opcode");
+      }
+      if (Descriptor->Flags.has(rcc::InstructionFlag::Terminator))
+        CanFallThrough = Instruction->opcode() == testOpcode(ConditionalBranchOpcode);
+    }
+    return CanFallThrough;
+  }
+
+  [[nodiscard]] rcc::Expected<bool>
+  rewriteBranchTarget(rcc::MachineBasicBlock &Block, rcc::MachineBasicBlock &OldTarget,
+                      rcc::MachineBasicBlock &NewTarget, rcc::MachineFunction &Function,
+                      const rcc::TargetDescription &Target) const override {
+    if (&Block.function() != &Function || &OldTarget.function() != &Function ||
+        &NewTarget.function() != &Function) {
+      return rcc::makeUnexpected(rcc::ErrorCode::InvalidArgument,
+                                 "branch rewrite references another function");
+    }
+    bool Changed = false;
+    for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      const rcc::InstructionDescriptor *Descriptor =
+          Target.instructionDescriptor(Instruction->opcode());
+      if (Descriptor == nullptr)
+        return rcc::makeUnexpected(rcc::ErrorCode::VerificationError, "unknown branch opcode");
+      if (!Descriptor->Flags.has(rcc::InstructionFlag::Branch))
+        continue;
+      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+        rcc::MachineOperand *Operand = Instruction->operandAt(Index);
+        const auto *BlockOperand =
+            Operand == nullptr ? nullptr : Operand->getIf<rcc::BasicBlockOperand>();
+        if (BlockOperand == nullptr || BlockOperand->Block != &OldTarget)
+          continue;
+        auto Rewritten = Operand->setBasicBlock(NewTarget);
+        if (!Rewritten)
+          return std::unexpected(Rewritten.error());
+        Changed = true;
+      }
+    }
+    return Changed;
+  }
+
+  [[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+  insertBranch(rcc::MachineBasicBlock &Block, rcc::MachineBasicBlock &TargetBlock,
+               rcc::MachineFunction &Function,
+               const rcc::TargetDescription &Target) const override {
+    rcc::MachineIRBuilder Builder(Function, Target);
+    auto Point = Builder.setInsertPoint(Block);
+    if (!Point)
+      return std::unexpected(Point.error());
+    auto Pending = Builder.buildInstr(testOpcode(JumpOpcode));
+    if (!Pending)
+      return std::unexpected(Pending.error());
+    auto Destination = Pending->addBasicBlock(TargetBlock);
+    if (!Destination)
+      return std::unexpected(Destination.error());
+    auto Built = Pending->build();
+    if (!Built)
+      return std::unexpected(Built.error());
+    return *Built;
+  }
+
+  [[nodiscard]] rcc::Expected<void>
+  validateCopy(rcc::Register Destination, rcc::SubRegIndex DestinationSubReg, rcc::Register Source,
+               rcc::SubRegIndex SourceSubReg, const rcc::MachineFunction &Function,
+               const rcc::TargetDescription &Target) const override {
+    if (RejectCopies) {
+      return rcc::makeUnexpected(rcc::ErrorCode::Unsupported,
+                                 "test target intentionally rejects COPY");
+    }
+    if (Destination.isNoRegister() || Source.isNoRegister()) {
+      return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
+                                 "COPY requires nonzero registers");
+    }
+    if ((Destination.isPhysical() && DestinationSubReg.value() != 0) ||
+        (Source.isPhysical() && SourceSubReg.value() != 0)) {
+      return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
+                                 "physical COPY operands cannot carry subregisters");
+    }
+    auto Def = rcc::MachineOperand::registerOperand(Destination, {rcc::RegisterOperandFlag::Define},
+                                                    DestinationSubReg);
+    auto Use =
+        rcc::MachineOperand::registerOperand(Source, {rcc::RegisterOperandFlag::Use}, SourceSubReg);
+    if (!Def || !Use)
+      return rcc::makeUnexpected(rcc::ErrorCode::InternalError, "failed to model COPY operands");
+    return Target.validateTieCompatibility(*Def, *Use, Function.registerInfo());
+  }
+
+  [[nodiscard]] rcc::Expected<bool>
+  tryConvertToThreeAddress(rcc::MachineInstr &Instruction, std::size_t DefIndex,
+                           std::size_t UseIndex, rcc::MachineFunction &,
+                           const rcc::TargetDescription &) const override {
+    if (Instruction.opcode() != testOpcode(ConvertibleTiedOpcode))
+      return false;
+    if (DefIndex != 0 || UseIndex != 1)
+      return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
+                                 "unexpected convertible tie indices");
+    auto Untied = Instruction.untieOperand(DefIndex);
+    if (!Untied)
+      return std::unexpected(Untied.error());
+    auto Opcode = Instruction.setOpcode(testOpcode(ThreeAddressOpcode));
+    if (!Opcode)
+      return std::unexpected(Opcode.error());
+    return true;
+  }
+
+  [[nodiscard]] rcc::Expected<std::uint32_t>
+  instructionSize(const rcc::MachineInstr &, const rcc::MachineFunction &,
+                  const rcc::TargetDescription &) const override {
+    return 4;
+  }
+
+  [[nodiscard]] rcc::Expected<rcc::MachineBasicBlock *>
+  branchTarget(rcc::MachineInstr &, rcc::MachineFunction &,
+               const rcc::TargetDescription &) const override {
+    return static_cast<rcc::MachineBasicBlock *>(nullptr);
+  }
+
+  [[nodiscard]] bool isBranchOffsetInRange(const rcc::MachineInstr &,
+                                           std::int64_t) const noexcept override {
+    return true;
+  }
+
+  [[nodiscard]] rcc::Expected<bool> relaxBranch(rcc::MachineInstr &, std::int64_t,
+                                                rcc::MachineFunction &,
+                                                const rcc::TargetDescription &) const override {
+    return false;
+  }
+
+private:
+  bool RejectCopies = false;
+};
+
+struct FunctionFixture final {
+  std::unique_ptr<rcc::MachineFunction> Function;
+  std::vector<rcc::MachineBasicBlock *> Blocks;
+};
+
+[[nodiscard]] inline FunctionFixture createFunction(TestContext &Context, std::string Name,
+                                                    std::uint64_t ID, std::size_t BlockCount) {
+  auto Function =
+      rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID));
+  Context.expect(Function.has_value(), "SSA-exit function creation must succeed");
+  if (!Function)
+    return {};
+
+  FunctionFixture Result{std::move(*Function), {}};
+  for (std::size_t Index = 0; Index < BlockCount; ++Index) {
+    auto Block = Result.Function->createBasicBlock();
+    Context.expect(Block && Result.Function->appendBlock(**Block).has_value(),
+                   "SSA-exit block creation must succeed");
+    if (!Block)
+      return {};
+    Result.Blocks.push_back(*Block);
+  }
+  return Result;
+}
+
+[[nodiscard]] inline rcc::Expected<rcc::Register>
+createVReg(rcc::MachineFunction &Function, rcc::LLT Type, rcc::RegisterBankID Bank,
+           rcc::RegisterClassID Class, std::uint8_t TargetFlags = 0,
+           std::optional<rcc::PhysicalRegister> Hint = std::nullopt) {
+  auto Reg = Function.registerInfo().createVirtualRegister(Type);
+  if (!Reg)
+    return std::unexpected(Reg.error());
+  auto BankResult = Function.registerInfo().setRegisterBank(*Reg, Bank);
+  if (!BankResult)
+    return std::unexpected(BankResult.error());
+  auto ClassResult = Function.registerInfo().setRegisterClass(*Reg, Class);
+  if (!ClassResult)
+    return std::unexpected(ClassResult.error());
+  if (TargetFlags != 0) {
+    auto FlagsResult = Function.registerInfo().setTargetRegisterFlags(*Reg, TargetFlags);
+    if (!FlagsResult)
+      return std::unexpected(FlagsResult.error());
+  }
+  if (Hint) {
+    auto HintResult = Function.registerInfo().addAllocationHint(*Reg, *Hint);
+    if (!HintResult)
+      return std::unexpected(HintResult.error());
+  }
+  return *Reg;
+}
+
+[[nodiscard]] inline rcc::Expected<rcc::MachineInstr *>
+buildRegisterInstruction(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+                         rcc::MachineBasicBlock &Block, rcc::Opcode Opcode,
+                         std::span<const rcc::Register> Defs, std::span<const rcc::Register> Uses,
+                         rcc::RegisterOperandFlags DefFlags = {},
+                         rcc::RegisterOperandFlags UseFlags = {}) {
+  rcc::MachineIRBuilder Builder(Function, Target);
+  auto Point = Builder.setInsertPoint(Block);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(Opcode);
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  for (rcc::Register Reg : Defs) {
+    auto Added = Pending->addDef(Reg, DefFlags);
+    if (!Added)
+      return std::unexpected(Added.error());
+  }
+  for (rcc::Register Reg : Uses) {
+    auto Added = Pending->addUse(Reg, UseFlags);
+    if (!Added)
+      return std::unexpected(Added.error());
+  }
+  return Pending->build();
+}
+
+[[nodiscard]] inline rcc::Expected<void>
+setSelectedSSAProperties(rcc::MachineFunction &Function, const rcc::TargetDescription &Target) {
+  auto Rebuilt = rcc::rebuildMachineLiveness(Function, Target);
+  if (!Rebuilt)
+    return std::unexpected(Rebuilt.error());
+  for (rcc::MachineFunctionProperty Property :
+       {rcc::MachineFunctionProperty::IsSSA, rcc::MachineFunctionProperty::TracksLiveness,
+        rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected,
+        rcc::MachineFunctionProperty::Selected}) {
+    Function.properties().set(Property);
+  }
+  return {};
+}
+
+[[nodiscard]] inline std::vector<rcc::MachineInstr *>
+instructionsWithOpcode(rcc::MachineFunction &Function, rcc::Opcode Opcode) {
+  std::vector<rcc::MachineInstr *> Result;
+  for (rcc::MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    for (rcc::MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      if (Instruction->opcode() == Opcode)
+        Result.push_back(Instruction);
+    }
+  }
+  return Result;
+}
+
+} // namespace rcc::test::ssa
+
+#endif // RCC_BACKEND_SSA_EXIT_TEST_SUPPORT_H
diff --git a/backend/unittests/CodeGen/TwoAddressInstructionPassTest.cpp b/backend/unittests/CodeGen/TwoAddressInstructionPassTest.cpp
new file mode 100644
index 0000000..6853a36
--- /dev/null
+++ b/backend/unittests/CodeGen/TwoAddressInstructionPassTest.cpp
@@ -0,0 +1,268 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/TwoAddressInstructionPass.h"
+
+#include "SSAExitTestSupport.h"
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+
+#include <array>
+#include <memory>
+#include <optional>
+
+namespace {
+
+using namespace rcc::test::ssa;
+
+void testTwoAddressAndSubregisterPseudos(TestContext &Context, const rcc::TargetDescription &Target,
+                                         const TestInstrInfo &Info) {
+  auto Fixture = createFunction(Context, "two_address", 5, 1);
+  if (!Fixture.Function || Fixture.Blocks.empty())
+    return;
+  auto I64 = rcc::LLT::makeInteger(64);
+  auto I32 = rcc::LLT::makeInteger(32);
+  if (!I64 || !I32)
+    return;
+  auto &Function = *Fixture.Function;
+  rcc::MachineBasicBlock &Block = *Fixture.Blocks[0];
+  auto GPR64 = [&](std::uint8_t Flags = 0) {
+    return createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+                      rcc::test::TestRegisterClass::GPR64, Flags);
+  };
+  auto GPR32 = [&]() {
+    return createVReg(Function, *I32, rcc::test::TestRegisterBank::GPR,
+                      rcc::test::TestRegisterClass::GPR32);
+  };
+
+  auto Satisfied = GPR64();
+  auto UndefSource = GPR64();
+  auto UndefDestination = GPR64();
+  auto CommuteSource = GPR64();
+  auto CommuteDestination = GPR64();
+  auto ConvertSource = GPR64();
+  auto ConvertDestination = GPR64();
+  auto FallbackSource = GPR64();
+  auto FallbackDestination = GPR64();
+  auto SequenceDestination = GPR64();
+  auto SequenceLow = GPR32();
+  auto SequenceHigh = GPR32();
+  auto InsertDestination = GPR64();
+  auto InsertBase = GPR64();
+  auto Inserted = GPR32();
+  const bool Complete = Satisfied && UndefSource && UndefDestination && CommuteSource &&
+                        CommuteDestination && ConvertSource && ConvertDestination &&
+                        FallbackSource && FallbackDestination && SequenceDestination &&
+                        SequenceLow && SequenceHigh && InsertDestination && InsertBase && Inserted;
+  Context.expect(Complete, "two-address test registers must be created");
+  if (!Complete)
+    return;
+
+  for (rcc::Register Source : {*CommuteSource, *ConvertSource, *FallbackSource, *SequenceLow,
+                               *SequenceHigh, *InsertBase, *Inserted}) {
+    const std::array Def{Source};
+    Context.expect(buildRegisterInstruction(Function, Target, Block, testOpcode(DefOpcode), Def, {},
+                                            {rcc::RegisterOperandFlag::Dead})
+                       .has_value(),
+                   "two-address source definition must be built");
+  }
+  const std::array UndefDef{*UndefSource};
+  Context.expect(buildRegisterInstruction(Function, Target, Block,
+                                          rcc::opcode(rcc::GenericOpcode::IMPLICIT_DEF), UndefDef,
+                                          {})
+                     .has_value(),
+                 "two-address undef source must be defined by IMPLICIT_DEF");
+
+  auto BuildTied = [&](rcc::Opcode Opcode, rcc::Register Def, rcc::Register Use,
+                       std::optional<rcc::Register> Other = std::nullopt) {
+    rcc::MachineIRBuilder Builder(Function, Target);
+    auto Point = Builder.setInsertPoint(Block);
+    if (!Point)
+      return rcc::Expected<rcc::MachineInstr *>{std::unexpected(Point.error())};
+    auto Pending = Builder.buildInstr(Opcode);
+    if (!Pending)
+      return rcc::Expected<rcc::MachineInstr *>{std::unexpected(Pending.error())};
+    auto AddedDef = Pending->addDef(Def);
+    if (!AddedDef)
+      return rcc::Expected<rcc::MachineInstr *>{std::unexpected(AddedDef.error())};
+    auto AddedUse = Pending->addUse(Use, {rcc::RegisterOperandFlag::Kill});
+    if (!AddedUse)
+      return rcc::Expected<rcc::MachineInstr *>{std::unexpected(AddedUse.error())};
+    if (Other) {
+      auto AddedOther = Pending->addUse(*Other);
+      if (!AddedOther)
+        return rcc::Expected<rcc::MachineInstr *>{std::unexpected(AddedOther.error())};
+    }
+    return Pending->build();
+  };
+
+  auto AlreadyTied = BuildTied(testOpcode(TiedOpcode), *Satisfied, *Satisfied);
+  auto UndefTied = BuildTied(testOpcode(TiedOpcode), *UndefDestination, *UndefSource);
+  auto Commutable = BuildTied(testOpcode(CommutableTiedOpcode), *CommuteDestination, *CommuteSource,
+                              *CommuteDestination);
+  auto Convertible =
+      BuildTied(testOpcode(ConvertibleTiedOpcode), *ConvertDestination, *ConvertSource);
+  auto Fallback = BuildTied(testOpcode(TiedOpcode), *FallbackDestination, *FallbackSource);
+  Context.expect(AlreadyTied && UndefTied && Commutable && Convertible && Fallback,
+                 "two-address instruction fixtures must be built");
+  if (!AlreadyTied || !UndefTied || !Commutable || !Convertible || !Fallback)
+    return;
+
+  rcc::MachineIRBuilder Builder(Function, Target);
+  if (!Builder.setInsertPoint(Block))
+    return;
+  auto Sequence = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::REG_SEQUENCE));
+  Context.expect(
+      Sequence && Sequence->addDef(*SequenceDestination) && Sequence->addUse(*SequenceLow) &&
+          Sequence->addImmediate(rcc::test::TestSubReg::Low32.value()) &&
+          Sequence->addUse(*SequenceHigh) &&
+          Sequence->addImmediate(rcc::test::TestSubReg::High32.value()) && Sequence->build(),
+      "REG_SEQUENCE fixture must be built");
+  auto Insert = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::INSERT_SUBREG));
+  Context.expect(Insert && Insert->addDef(*InsertDestination) && Insert->addUse(*InsertBase) &&
+                     Insert->addUse(*Inserted) &&
+                     Insert->addImmediate(rcc::test::TestSubReg::Low32.value()) && Insert->build(),
+                 "INSERT_SUBREG fixture must be built");
+  auto Return = Builder.buildInstr(testOpcode(ReturnOpcode));
+  Context.expect(Return && Return->build(), "two-address return must be built");
+
+  auto InitialLiveness = setSelectedSSAProperties(Function, Target);
+  Context.expect(InitialLiveness.has_value(), "two-address liveness rebuild must succeed");
+  if (!InitialLiveness)
+    return;
+  Function.properties().set(rcc::MachineFunctionProperty::NoPHIs);
+  rcc::MachinePassManager Pipeline;
+  Context.expect(
+      Pipeline.addPass(std::make_unique<rcc::TwoAddressInstructionPass>(Info)).has_value(),
+      "two-address pass must be registered");
+  rcc::MachineAnalysisManager Analyses;
+  auto Run = Pipeline.run(Function, Target, Analyses);
+  Context.expect(Run.has_value(), "two-address rewrite must succeed");
+  if (!Run)
+    return;
+
+  Context.expect(Function.properties().has(rcc::MachineFunctionProperty::TiedOpsRewritten) &&
+                     !Function.properties().has(rcc::MachineFunctionProperty::IsSSA),
+                 "two-address rewrite must publish TiedOpsRewritten and clear IsSSA");
+  Context.expect(
+      instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::REG_SEQUENCE)).empty() &&
+          instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::INSERT_SUBREG)).empty(),
+      "TwoAddressInstructionPass must consume all Stage 10 subregister pseudos");
+
+  Context.expect((*AlreadyTied)->operandAt(1)->registerValue() == *Satisfied,
+                 "an already-satisfied tie must remain unchanged");
+  Context.expect(
+      (*UndefTied)->operandAt(1)->registerValue() == *UndefDestination &&
+          (*UndefTied)->operandAt(1)->registerFlags().has(rcc::RegisterOperandFlag::Undef),
+      "undef tied uses must be rewritten without a COPY");
+  Context.expect((*Commutable)->operandAt(1)->registerValue() == *CommuteDestination &&
+                     (*Commutable)->operandAt(2)->registerValue() == *CommuteSource,
+                 "commutation must satisfy a tie before COPY fallback");
+  Context.expect((*Convertible)->opcode() == testOpcode(ThreeAddressOpcode) &&
+                     !(*Convertible)->operandAt(0)->tiedOperandIndex() &&
+                     !(*Convertible)->operandAt(1)->tiedOperandIndex(),
+                 "target three-address conversion must run before COPY fallback");
+  Context.expect((*Fallback)->previous() != nullptr &&
+                     (*Fallback)->previous()->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+                     (*Fallback)->previous()->operandAt(0)->registerValue() ==
+                         *FallbackDestination &&
+                     (*Fallback)->previous()->operandAt(1)->registerValue() == *FallbackSource &&
+                     (*Fallback)->operandAt(1)->registerValue() == *FallbackDestination,
+                 "unsatisfied ties must receive a COPY immediately before the instruction");
+
+  const auto Copies = instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::COPY));
+  const auto ImplicitDefs =
+      instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::IMPLICIT_DEF));
+  Context.expect(Copies.size() >= 5 && ImplicitDefs.size() >= 2,
+                 "subregister pseudo expansion must materialize base and lane definitions");
+  Context.expect(
+      std::ranges::any_of(Copies,
+                          [InsertDestination](const rcc::MachineInstr *Copy) {
+                            return Copy->operandAt(0)->registerValue() == *InsertDestination &&
+                                   Copy->operandAt(0)->subReg() == rcc::test::TestSubReg::Low32;
+                          }),
+      "INSERT_SUBREG must copy its inserted value into the requested destination lane");
+  const bool HasKill = std::ranges::any_of(Function.allInstructions(), [](const auto *MI) {
+    return MI->parent() != nullptr &&
+           std::ranges::any_of(MI->operands(), [](const rcc::MachineOperand &Operand) {
+             return Operand.registerFlags().has(rcc::RegisterOperandFlag::Kill);
+           });
+  });
+  const bool HasDead = std::ranges::any_of(Function.allInstructions(), [](const auto *MI) {
+    return MI->parent() != nullptr &&
+           std::ranges::any_of(MI->operands(), [](const rcc::MachineOperand &Operand) {
+             return Operand.registerFlags().has(rcc::RegisterOperandFlag::Dead);
+           });
+  });
+  Context.expect(HasKill && HasDead,
+                 "two-address rewrite must rebuild precise kill and dead flags");
+  Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(),
+                 "two-address and subregister expansion result must verify");
+
+  auto AtomicFixture = createFunction(Context, "two_address_atomic", 10, 1);
+  if (!AtomicFixture.Function || AtomicFixture.Blocks.empty())
+    return;
+  auto AtomicSource = createVReg(*AtomicFixture.Function, *I64, rcc::test::TestRegisterBank::GPR,
+                                 rcc::test::TestRegisterClass::GPR64);
+  auto AtomicDestination =
+      createVReg(*AtomicFixture.Function, *I64, rcc::test::TestRegisterBank::GPR,
+                 rcc::test::TestRegisterClass::GPR64);
+  if (!AtomicSource || !AtomicDestination)
+    return;
+  const std::array AtomicSourceDef{*AtomicSource};
+  Context.expect(buildRegisterInstruction(*AtomicFixture.Function, Target, *AtomicFixture.Blocks[0],
+                                          testOpcode(DefOpcode), AtomicSourceDef, {})
+                     .has_value(),
+                 "two-address atomicity source definition must build");
+  rcc::MachineIRBuilder AtomicBuilder(*AtomicFixture.Function, Target);
+  if (!AtomicBuilder.setInsertPoint(*AtomicFixture.Blocks[0]))
+    return;
+  auto AtomicPending = AtomicBuilder.buildInstr(testOpcode(TiedOpcode));
+  auto AtomicInstruction =
+      AtomicPending && AtomicPending->addDef(*AtomicDestination) &&
+              AtomicPending->addUse(*AtomicSource, {rcc::RegisterOperandFlag::Kill})
+          ? AtomicPending->build()
+          : rcc::Expected<rcc::MachineInstr *>{rcc::makeUnexpected(
+                rcc::ErrorCode::InternalError, "failed to build atomicity fixture")};
+  Context.expect(AtomicInstruction.has_value(),
+                 "two-address atomicity tied instruction must build");
+  if (!AtomicInstruction)
+    return;
+  auto AtomicLiveness = setSelectedSSAProperties(*AtomicFixture.Function, Target);
+  Context.expect(AtomicLiveness.has_value(), "two-address atomicity liveness rebuild must succeed");
+  if (!AtomicLiveness)
+    return;
+  AtomicFixture.Function->properties().set(rcc::MachineFunctionProperty::NoPHIs);
+  const std::size_t AtomicInstructionsBefore = AtomicFixture.Function->allInstructions().size();
+  const std::size_t AtomicRegistersBefore =
+      AtomicFixture.Function->registerInfo().virtualRegisters().size();
+  const std::uint64_t AtomicPropertiesBefore = AtomicFixture.Function->properties().rawValue();
+
+  TestInstrInfo RejectingInfo(true);
+  rcc::MachineAnalysisManager AtomicAnalyses;
+  rcc::TwoAddressInstructionPass FailingPass(RejectingInfo);
+  auto Failed = FailingPass.run(*AtomicFixture.Function, Target, AtomicAnalyses);
+  Context.expect(!Failed && Failed.error().code() == rcc::ErrorCode::Unsupported,
+                 "COPY rejection must produce a structured two-address failure");
+  Context.expect(
+      AtomicFixture.Function->allInstructions().size() == AtomicInstructionsBefore &&
+          AtomicFixture.Function->registerInfo().virtualRegisters().size() ==
+              AtomicRegistersBefore &&
+          AtomicFixture.Function->properties().rawValue() == AtomicPropertiesBefore &&
+          (*AtomicInstruction)->operandAt(0)->registerValue() == *AtomicDestination &&
+          (*AtomicInstruction)->operandAt(1)->registerValue() == *AtomicSource &&
+          (*AtomicInstruction)->operandAt(1)->registerFlags().has(rcc::RegisterOperandFlag::Kill),
+      "failed two-address transaction preflight must leave the original function unchanged");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  auto Target = createTarget();
+  Context.expect(Target.has_value(), "two-address TestTarget must be created");
+  if (!Target)
+    return Context.result();
+  TestInstrInfo Info;
+  testTwoAddressAndSubregisterPseudos(Context, *Target, Info);
+  return Context.result();
+}
diff --git a/backend/unittests/Target/RISCVSSAExitTest.cpp b/backend/unittests/Target/RISCVSSAExitTest.cpp
index eafb5a0..3f81d1d 100644
--- a/backend/unittests/Target/RISCVSSAExitTest.cpp
+++ b/backend/unittests/Target/RISCVSSAExitTest.cpp
@@ -11,8 +11,8 @@
 #include "rcc/CodeGen/MachineLiveness.h"
 #include "rcc/CodeGen/MachineOperand.h"
 #include "rcc/CodeGen/MachinePass.h"
-#include "rcc/CodeGen/MachineSSAExit.h"
 #include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/CodeGen/PHIElimination.h"
 #include "rcc/Target/RISCV/RISCVTarget.h"
 
 #include <algorithm>