[CodeGen] Implement machine SSA exit

8 files changed, 1597 insertions, 49 deletions

diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index f2c81f2..5cff572 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -29,6 +29,7 @@ set(
   MachinePass.cpp
   MachinePipelinePasses.cpp
   MachineRegisterInfo.cpp
+  MachineSSAExit.cpp
   MachineVerifier.cpp
   MachineFunctionProperties.cpp
   MachineFunctionRecords.cpp
@@ -71,6 +72,7 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePipelinePasses.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetCodeGen.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineSSAExit.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineVerifier.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionProperties.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionRecords.h"
@@ -141,6 +143,7 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePasses.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecords.cpp"
@@ -182,6 +185,7 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePasses.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecords.cpp"
diff --git a/backend/lib/CodeGen/GenericOpcodes.cpp b/backend/lib/CodeGen/GenericOpcodes.cpp
index 0b0e0fe..1394507 100644
--- a/backend/lib/CodeGen/GenericOpcodes.cpp
+++ b/backend/lib/CodeGen/GenericOpcodes.cpp
@@ -102,7 +102,7 @@ using GO = GenericOpcode;
   OperandDescriptor Result;
   Result.Kinds = {MachineOperand::Kind::Register};
   Result.RegisterRole = Role;
-  Result.TypeConstraint = OperandTypeConstraint{std::move(Kinds), Group};
+  Result.TypeConstraint = OperandTypeConstraint{Kinds, Group};
   return Result;
 }
 
@@ -146,6 +146,11 @@ using GO = GenericOpcode;
   return Descriptor;
 }
 
+[[nodiscard]] OperandDescriptor registeredTargetFlags(OperandDescriptor Descriptor) {
+  Descriptor.AllowAnyTargetFlags = true;
+  return Descriptor;
+}
+
 class DescriptorRegistry final {
 public:
   DescriptorRegistry() {
@@ -158,7 +163,7 @@ public:
 #undef RCC_CORE_OPCODE
   }
 
-  void configure(std::initializer_list<GO> Opcodes, std::vector<OperandDescriptor> Operands,
+  void configure(std::initializer_list<GO> Opcodes, const std::vector<OperandDescriptor> &Operands,
                  std::size_t NumDefs, std::initializer_list<InstructionFlag> Flags = {},
                  bool Variadic = false, std::size_t MinimumRepetitions = 0,
                  bool RequiresMemoryOperands = false, PseudoOwner Owner = PseudoOwner::None,
@@ -322,9 +327,10 @@ private:
     auto Info = RegInfo.virtualRegisterInfo(*Reg);
     if (!Info)
       return std::unexpected(Info.error());
-    if (!Info->get().Type)
+    const std::optional<LLT> &Type = Info->get().Type;
+    if (!Type)
       return semanticError("generic virtual register is missing its LLT");
-    Types[Index] = *Info->get().Type;
+    Types[Index] = Type.value();
   }
 
   const auto TypeAt = [&Types](std::size_t Index) -> LLT { return *Types[Index]; };
@@ -773,7 +779,7 @@ private:
   }
   case GO::G_INTRINSIC_FPTRUNC_ROUND: {
     const auto Rounding = plainImmediate(Operands[2]);
-    if (!Rounding || !((*Rounding >= 0 && *Rounding <= 4) || *Rounding == 7))
+    if (!Rounding || *Rounding < 0 || (*Rounding > 4 && *Rounding != 7))
       return semanticError("floating truncation rounding mode is invalid");
     return VerifyWidthChange(false);
   }
@@ -980,14 +986,17 @@ private:
 void configureCoreOpcodes(DescriptorRegistry &Registry) {
   const auto RegDef = untypedRegister(RegisterOperandRole::Def);
   const auto RegUse = untypedRegister(RegisterOperandRole::Use);
+  const auto TransferDef = registeredTargetFlags(RegDef);
+  const auto TransferUse = registeredTargetFlags(RegUse);
   const auto Any = anyOperand();
   const auto VariadicAny = repeated(Any);
   const auto VariadicUse = repeated(RegUse);
 
-  Registry.configure({GO::PHI},
-                     {RegDef, VariadicUse, repeated(kind(MachineOperand::Kind::BasicBlock))}, 1,
-                     {InstructionFlag::Phi}, true, 1, false, PseudoOwner::PhiElimination,
-                     PipelineStage::SSAEliminated);
+  Registry.configure(
+      {GO::PHI},
+      {TransferDef, repeated(TransferUse), repeated(kind(MachineOperand::Kind::BasicBlock))}, 1,
+      {InstructionFlag::Phi}, true, 1, false, PseudoOwner::PhiElimination,
+      PipelineStage::SSAEliminated);
   Registry.configure({GO::INLINEASM}, {VariadicAny}, 0,
                      {InstructionFlag::ProducesCode, InstructionFlag::TerminalEmission,
                       InstructionFlag::UnmodeledSideEffects},
@@ -1004,10 +1013,11 @@ void configureCoreOpcodes(DescriptorRegistry &Registry) {
   Registry.configure({GO::KILL}, {VariadicUse}, 0, {InstructionFlag::Meta}, true);
   Registry.configure({GO::EXTRACT_SUBREG}, {RegDef, RegUse, immediate()}, 1, {}, false, 0, false,
                      PseudoOwner::PostRAExpansion, PipelineStage::PostRAFinalized);
-  Registry.configure({GO::INSERT_SUBREG}, {RegDef, RegUse, RegUse, immediate()}, 1, {}, false, 0,
-                     false, PseudoOwner::TwoAddressRewrite, PipelineStage::TiedOpsRewritten);
+  Registry.configure({GO::INSERT_SUBREG}, {TransferDef, TransferUse, TransferUse, immediate()}, 1,
+                     {}, false, 0, false, PseudoOwner::TwoAddressRewrite,
+                     PipelineStage::TiedOpsRewritten);
   Registry.tie(GO::INSERT_SUBREG, 0, 1);
-  Registry.configure({GO::IMPLICIT_DEF}, {RegDef}, 1,
+  Registry.configure({GO::IMPLICIT_DEF}, {TransferDef}, 1,
                      {InstructionFlag::Meta, InstructionFlag::Rematerializable});
   Registry.configure({GO::INIT_UNDEF}, {RegDef}, 1, {}, false, 0, false,
                      PseudoOwner::RegisterAllocator, PipelineStage::RegisterAllocated);
@@ -1019,10 +1029,10 @@ void configureCoreOpcodes(DescriptorRegistry &Registry) {
                      {VariadicAny}, 0, {InstructionFlag::Meta}, true);
   Registry.configure({GO::DBG_LABEL}, {kind(MachineOperand::Kind::Metadata)}, 0,
                      {InstructionFlag::Meta});
-  Registry.configure({GO::REG_SEQUENCE}, {RegDef, repeated(RegUse), repeated(immediate())}, 1, {},
-                     true, 1, false, PseudoOwner::TwoAddressRewrite,
-                     PipelineStage::TiedOpsRewritten);
-  Registry.configure({GO::COPY}, {RegDef, RegUse}, 1, {}, false, 0, false,
+  Registry.configure({GO::REG_SEQUENCE},
+                     {TransferDef, repeated(TransferUse), repeated(immediate())}, 1, {}, true, 1,
+                     false, PseudoOwner::TwoAddressRewrite, PipelineStage::TiedOpsRewritten);
+  Registry.configure({GO::COPY}, {TransferDef, TransferUse}, 1, {}, false, 0, false,
                      PseudoOwner::PostRAExpansion, PipelineStage::PostRAFinalized);
   Registry.configure({GO::COPY_LANEMASK}, {RegDef, RegUse, kind(MachineOperand::Kind::LaneMask)}, 1,
                      {}, false, 0, false, PseudoOwner::PostRAExpansion,
@@ -1170,10 +1180,13 @@ void configureGenericOpcodes(DescriptorRegistry &Registry) {
                    InstructionFlag::Commutable);
 
   Registry.configure({GO::G_SDIVREM, GO::G_UDIVREM}, {IntDef0, IntDef0, IntUse0, IntUse0}, 2);
-  Registry.configure({GO::G_IMPLICIT_DEF}, {AnyDef0}, 1);
-  Registry.configure({GO::G_PHI},
-                     {AnyDef0, repeated(AnyUse0), repeated(kind(MachineOperand::Kind::BasicBlock))},
-                     1, {InstructionFlag::Phi}, true, 1);
+  const auto TransferDef0 = registeredTargetFlags(AnyDef0);
+  const auto TransferUse0 = registeredTargetFlags(AnyUse0);
+  Registry.configure({GO::G_IMPLICIT_DEF}, {TransferDef0}, 1);
+  Registry.configure(
+      {GO::G_PHI},
+      {TransferDef0, repeated(TransferUse0), repeated(kind(MachineOperand::Kind::BasicBlock))}, 1,
+      {InstructionFlag::Phi}, true, 1);
   Registry.configure({GO::G_FRAME_INDEX},
                      {ScalarPointerDef0, kind(MachineOperand::Kind::FrameIndex)}, 1);
   Registry.configure({GO::G_GLOBAL_VALUE},
diff --git a/backend/lib/CodeGen/InstructionDescriptor.cpp b/backend/lib/CodeGen/InstructionDescriptor.cpp
index 57400d6..5aec744 100644
--- a/backend/lib/CodeGen/InstructionDescriptor.cpp
+++ b/backend/lib/CodeGen/InstructionDescriptor.cpp
@@ -420,11 +420,12 @@ Expected<void> InstructionSet::validateExplicitOperands(const InstructionDescrip
     auto Info = RegInfo.virtualRegisterInfo(*Reg);
     if (!Info)
       return std::unexpected(Info.error());
-    if (!Info->get().Type) {
+    const std::optional<LLT> &RegisterType = Info->get().Type;
+    if (!RegisterType) {
       return makeUnexpected(ErrorCode::VerificationError,
                             "typed instruction operand virtual register has no LLT");
     }
-    const LLT Type = *Info->get().Type;
+    const LLT Type = RegisterType.value();
     if (!OperandDesc.TypeConstraint->Kinds.contains(Type.kind())) {
       return makeUnexpected(ErrorCode::VerificationError,
                             "instruction operand LLT kind is not permitted by its descriptor");
@@ -587,7 +588,8 @@ Expected<void> InstructionSet::validateOperand(const OperandDescriptor &Descript
     return makeUnexpected(ErrorCode::VerificationError,
                           "instruction operand kind does not match its descriptor");
   }
-  if ((Operand.targetFlags() & ~Descriptor.AllowedTargetFlags) != 0) {
+  if (!Descriptor.AllowAnyTargetFlags &&
+      (Operand.targetFlags() & ~Descriptor.AllowedTargetFlags) != 0) {
     return makeUnexpected(ErrorCode::VerificationError,
                           "instruction operand uses unregistered target flags");
   }
diff --git a/backend/lib/CodeGen/MachineCFGUpdater.cpp b/backend/lib/CodeGen/MachineCFGUpdater.cpp
index c78e318..4aacdf5 100644
--- a/backend/lib/CodeGen/MachineCFGUpdater.cpp
+++ b/backend/lib/CodeGen/MachineCFGUpdater.cpp
@@ -2,18 +2,108 @@
 
 #include "rcc/CodeGen/MachineCFGUpdater.h"
 
+#include "rcc/CodeGen/GenericOpcodes.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
 #include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
 
 #include <algorithm>
 #include <cstddef>
 #include <optional>
+#include <span>
 #include <utility>
 #include <vector>
 
 namespace rcc {
 namespace {
 
+struct PhiIncomingEdit final {
+  MachineInstr *Phi = nullptr;
+  std::size_t ValueIndex = 0;
+};
+
+[[nodiscard]] bool isKnownPhi(const MachineInstr &Instruction) noexcept {
+  return Instruction.opcode() == opcode(GenericOpcode::PHI) ||
+         Instruction.opcode() == opcode(GenericOpcode::G_PHI);
+}
+
+[[nodiscard]] bool containsKnownPhi(const MachineBasicBlock &Block) noexcept {
+  for (const MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    if (isKnownPhi(*Instruction))
+      return true;
+  }
+  return false;
+}
+
+[[nodiscard]] Expected<std::vector<PhiIncomingEdit>>
+collectPhiIncomingEdits(MachineBasicBlock &Block, const MachineBasicBlock &Predecessor) {
+  std::vector<PhiIncomingEdit> Result;
+  for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    if (!isKnownPhi(*Instruction))
+      continue;
+    if (Instruction->operandCount() < 3 || (Instruction->operandCount() - 1U) % 2U != 0) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "CFG update encountered a malformed PHI instruction");
+    }
+
+    std::optional<std::size_t> Match;
+    for (std::size_t Index = 1; Index < Instruction->operandCount(); Index += 2U) {
+      const MachineOperand *Value = Instruction->operandAt(Index);
+      const MachineOperand *BlockOperand = Instruction->operandAt(Index + 1U);
+      const Register *Reg = Value == nullptr ? nullptr : Value->getIf<Register>();
+      const BasicBlockOperand *Incoming =
+          BlockOperand == nullptr ? nullptr : BlockOperand->getIf<BasicBlockOperand>();
+      if (Reg == nullptr || Incoming == nullptr || Incoming->Block == nullptr) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "CFG update encountered malformed PHI incoming operands");
+      }
+      if (Incoming->Block != &Predecessor)
+        continue;
+      if (Match) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "CFG update encountered duplicate PHI incoming blocks");
+      }
+      Match = Index;
+    }
+    if (!Match) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "CFG edge has no corresponding PHI incoming value");
+    }
+    Result.push_back(PhiIncomingEdit{Instruction, *Match});
+  }
+  return Result;
+}
+
+[[nodiscard]] Expected<void> erasePhiIncoming(std::span<const PhiIncomingEdit> Edits) {
+  for (const PhiIncomingEdit &Edit : Edits) {
+    auto BlockErased = Edit.Phi->eraseOperand(Edit.ValueIndex + 1U);
+    if (!BlockErased)
+      return std::unexpected(BlockErased.error());
+    auto ValueErased = Edit.Phi->eraseOperand(Edit.ValueIndex);
+    if (!ValueErased)
+      return std::unexpected(ValueErased.error());
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<void> rewritePhiIncoming(std::span<const PhiIncomingEdit> Edits,
+                                                MachineBasicBlock &NewPredecessor) {
+  for (const PhiIncomingEdit &Edit : Edits) {
+    MachineOperand *BlockOperand = Edit.Phi->operandAt(Edit.ValueIndex + 1U);
+    if (BlockOperand == nullptr) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "PHI incoming operand disappeared during CFG update");
+    }
+    auto Rewritten = BlockOperand->setBasicBlock(NewPredecessor);
+    if (!Rewritten)
+      return std::unexpected(Rewritten.error());
+  }
+  return {};
+}
+
 [[nodiscard]] std::optional<std::size_t> findSuccessorIndex(const MachineBasicBlock &From,
                                                             const MachineBasicBlock &To) {
   const auto Successors = From.successors();
@@ -24,6 +114,39 @@ namespace {
   return std::nullopt;
 }
 
+[[nodiscard]] Expected<void> validateOutgoingEdges(MachineBasicBlock &From) {
+  for (const MachineSuccessor &Successor : From.successors()) {
+    if (Successor.Block == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError, "CFG successor is null");
+    }
+    if (std::ranges::find(Successor.Block->predecessors(), &From) ==
+        Successor.Block->predecessors().end()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "CFG successor has no reciprocal predecessor");
+    }
+    auto PhiEdits = collectPhiIncomingEdits(*Successor.Block, From);
+    if (!PhiEdits)
+      return std::unexpected(PhiEdits.error());
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<void> validateIncomingEdges(MachineBasicBlock &To) {
+  for (MachineBasicBlock *Predecessor : To.predecessors()) {
+    if (Predecessor == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError, "CFG predecessor is null");
+    }
+    if (!findSuccessorIndex(*Predecessor, To)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "CFG predecessor has no reciprocal successor");
+    }
+    auto PhiEdits = collectPhiIncomingEdits(To, *Predecessor);
+    if (!PhiEdits)
+      return std::unexpected(PhiEdits.error());
+  }
+  return {};
+}
+
 } // namespace
 
 Expected<void> MachineCFGUpdater::verifyOwnership(const MachineBasicBlock &Block) const {
@@ -50,6 +173,15 @@ Expected<void> MachineCFGUpdater::addSuccessor(MachineBasicBlock &From, MachineB
     return {};
   }
 
+  if (containsKnownPhi(To)) {
+    auto PhiEdits = collectPhiIncomingEdits(To, From);
+    if (!PhiEdits) {
+      return makeUnexpected(
+          ErrorCode::InvalidArgument,
+          "adding a predecessor to a PHI block requires explicit incoming values");
+    }
+  }
+
   From.Successors.push_back(MachineSuccessor{&To, Probability});
   if (std::ranges::find(To.Predecessors, &From) == To.Predecessors.end())
     To.Predecessors.push_back(&From);
@@ -68,13 +200,20 @@ Expected<void> MachineCFGUpdater::removeSuccessor(MachineBasicBlock &From, Machi
   if (!Successor) {
     return makeUnexpected(ErrorCode::InvalidArgument, "CFG successor edge is not present");
   }
-  From.Successors.erase(From.Successors.begin() + static_cast<std::ptrdiff_t>(*Successor));
-
   const auto Predecessor = std::ranges::find(To.Predecessors, &From);
   if (Predecessor == To.Predecessors.end()) {
     return makeUnexpected(ErrorCode::VerificationError,
                           "CFG successor has no reciprocal predecessor");
   }
+
+  auto PhiEdits = collectPhiIncomingEdits(To, From);
+  if (!PhiEdits)
+    return std::unexpected(PhiEdits.error());
+  auto PhiResult = erasePhiIncoming(*PhiEdits);
+  if (!PhiResult)
+    return std::unexpected(PhiResult.error());
+
+  From.Successors.erase(From.Successors.begin() + static_cast<std::ptrdiff_t>(*Successor));
   To.Predecessors.erase(Predecessor);
   return {};
 }
@@ -101,18 +240,95 @@ Expected<void> MachineCFGUpdater::replaceSuccessor(MachineBasicBlock &From,
   }
   const BranchProbability Probability = From.Successors[*Existing].Probability;
 
-  auto RemoveResult = removeSuccessor(From, OldTarget);
-  if (!RemoveResult)
-    return std::unexpected(RemoveResult.error());
-  auto AddResult = addSuccessor(From, NewTarget, Probability);
-  if (!AddResult) {
-    auto RestoreResult = addSuccessor(From, OldTarget, Probability);
-    if (!RestoreResult) {
-      return makeUnexpected(ErrorCode::InternalError,
-                            "failed to restore CFG edge after replacement failure");
+  const auto OldPredecessor = std::ranges::find(OldTarget.Predecessors, &From);
+  if (OldPredecessor == OldTarget.Predecessors.end()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "replaced CFG successor has no reciprocal predecessor");
+  }
+  auto OldPhiEdits = collectPhiIncomingEdits(OldTarget, From);
+  if (!OldPhiEdits)
+    return std::unexpected(OldPhiEdits.error());
+
+  const auto NewEdge = findSuccessorIndex(From, NewTarget);
+  const auto NewPredecessor = std::ranges::find(NewTarget.Predecessors, &From);
+  if (NewEdge) {
+    if (NewPredecessor == NewTarget.Predecessors.end()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "replacement target has no reciprocal predecessor");
+    }
+    auto NewPhiEdits = collectPhiIncomingEdits(NewTarget, From);
+    if (!NewPhiEdits)
+      return std::unexpected(NewPhiEdits.error());
+  } else {
+    if (NewPredecessor != NewTarget.Predecessors.end()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "replacement target has a predecessor without a reciprocal edge");
+    }
+    if (containsKnownPhi(NewTarget)) {
+      auto NewPhiEdits = collectPhiIncomingEdits(NewTarget, From);
+      if (!NewPhiEdits) {
+        return makeUnexpected(
+            ErrorCode::InvalidArgument,
+            "redirecting an edge to a PHI block requires explicit incoming values");
+      }
     }
-    return std::unexpected(AddResult.error());
   }
+  auto PhiResult = erasePhiIncoming(*OldPhiEdits);
+  if (!PhiResult)
+    return std::unexpected(PhiResult.error());
+  OldTarget.Predecessors.erase(OldPredecessor);
+  if (NewEdge) {
+    From.Successors[*NewEdge].Probability =
+        From.Successors[*NewEdge].Probability.saturatingAdd(Probability);
+    From.Successors.erase(From.Successors.begin() + static_cast<std::ptrdiff_t>(*Existing));
+  } else {
+    From.Successors[*Existing].Block = &NewTarget;
+    if (std::ranges::find(NewTarget.Predecessors, &From) == NewTarget.Predecessors.end())
+      NewTarget.Predecessors.push_back(&From);
+  }
+  return {};
+}
+
+Expected<void> MachineCFGUpdater::splitEdge(MachineBasicBlock &From, MachineBasicBlock &To,
+                                            MachineBasicBlock &EdgeBlock) {
+  auto FromOwnership = verifyOwnership(From);
+  if (!FromOwnership)
+    return std::unexpected(FromOwnership.error());
+  auto ToOwnership = verifyOwnership(To);
+  if (!ToOwnership)
+    return std::unexpected(ToOwnership.error());
+  auto EdgeOwnership = verifyOwnership(EdgeBlock);
+  if (!EdgeOwnership)
+    return std::unexpected(EdgeOwnership.error());
+  if (&From == &To || &From == &EdgeBlock || &To == &EdgeBlock) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "edge split requires three distinct basic blocks");
+  }
+  if (!EdgeBlock.isLinked() || EdgeBlock.firstInstruction() != nullptr ||
+      !EdgeBlock.predecessors().empty() || !EdgeBlock.successors().empty()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "edge split block must be linked, empty, and disconnected");
+  }
+
+  const auto Successor = findSuccessorIndex(From, To);
+  if (!Successor)
+    return makeUnexpected(ErrorCode::InvalidArgument, "split CFG edge is not present");
+  auto Predecessor = std::ranges::find(To.Predecessors, &From);
+  if (Predecessor == To.Predecessors.end()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "split CFG edge has no reciprocal predecessor");
+  }
+  auto PhiEdits = collectPhiIncomingEdits(To, From);
+  if (!PhiEdits)
+    return std::unexpected(PhiEdits.error());
+
+  auto PhiResult = rewritePhiIncoming(*PhiEdits, EdgeBlock);
+  if (!PhiResult)
+    return std::unexpected(PhiResult.error());
+  From.Successors[*Successor].Block = &EdgeBlock;
+  *Predecessor = &EdgeBlock;
+  EdgeBlock.Predecessors.push_back(&From);
+  EdgeBlock.Successors.push_back(MachineSuccessor{&To, BranchProbability::one()});
   return {};
 }
 
@@ -145,15 +361,67 @@ Expected<void> MachineCFGUpdater::transferSuccessors(MachineBasicBlock &From,
   if (&From == &To)
     return {};
 
-  const std::vector<MachineSuccessor> Successors = From.Successors;
-  for (const MachineSuccessor &Successor : Successors) {
-    auto RemoveResult = removeSuccessor(From, *Successor.Block);
-    if (!RemoveResult)
-      return std::unexpected(RemoveResult.error());
-    auto AddResult = addSuccessor(To, *Successor.Block, Successor.Probability);
-    if (!AddResult)
-      return std::unexpected(AddResult.error());
+  struct Transfer final {
+    MachineSuccessor Successor;
+    std::vector<PhiIncomingEdit> PhiEdits;
+    bool MergeExisting = false;
+  };
+  std::vector<Transfer> Transfers;
+  Transfers.reserve(From.Successors.size());
+  for (const MachineSuccessor &Successor : From.Successors) {
+    if (Successor.Block == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError, "transferred CFG successor is null");
+    }
+    if (std::ranges::find(Successor.Block->Predecessors, &From) ==
+        Successor.Block->Predecessors.end()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "transferred CFG successor has no reciprocal predecessor");
+    }
+    auto PhiEdits = collectPhiIncomingEdits(*Successor.Block, From);
+    if (!PhiEdits)
+      return std::unexpected(PhiEdits.error());
+    const bool MergeExisting = findSuccessorIndex(To, *Successor.Block).has_value();
+    const auto ToPredecessor = std::ranges::find(Successor.Block->Predecessors, &To);
+    if (MergeExisting) {
+      if (ToPredecessor == Successor.Block->Predecessors.end()) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "transfer target edge has no reciprocal predecessor");
+      }
+      auto ExistingPhiEdits = collectPhiIncomingEdits(*Successor.Block, To);
+      if (!ExistingPhiEdits)
+        return std::unexpected(ExistingPhiEdits.error());
+    } else if (ToPredecessor != Successor.Block->Predecessors.end()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "transfer target is a predecessor without a reciprocal edge");
+    }
+    Transfers.push_back(Transfer{Successor, std::move(*PhiEdits), MergeExisting});
   }
+
+  for (Transfer &TransferValue : Transfers) {
+    MachineBasicBlock &Successor = *TransferValue.Successor.Block;
+    auto OldPredecessor = std::ranges::find(Successor.Predecessors, &From);
+    if (TransferValue.MergeExisting) {
+      auto PhiResult = erasePhiIncoming(TransferValue.PhiEdits);
+      if (!PhiResult)
+        return std::unexpected(PhiResult.error());
+      Successor.Predecessors.erase(OldPredecessor);
+      const std::optional<std::size_t> Existing = findSuccessorIndex(To, Successor);
+      if (!Existing) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "preflighted transfer target edge disappeared");
+      }
+      To.Successors[Existing.value()].Probability =
+          To.Successors[Existing.value()].Probability.saturatingAdd(
+              TransferValue.Successor.Probability);
+    } else {
+      auto PhiResult = rewritePhiIncoming(TransferValue.PhiEdits, To);
+      if (!PhiResult)
+        return std::unexpected(PhiResult.error());
+      *OldPredecessor = &To;
+      To.Successors.push_back(TransferValue.Successor);
+    }
+  }
+  From.Successors.clear();
   return {};
 }
 
@@ -162,6 +430,13 @@ Expected<void> MachineCFGUpdater::disconnectBlock(MachineBasicBlock &Block) {
   if (!Ownership)
     return std::unexpected(Ownership.error());
 
+  auto Outgoing = validateOutgoingEdges(Block);
+  if (!Outgoing)
+    return std::unexpected(Outgoing.error());
+  auto Incoming = validateIncomingEdges(Block);
+  if (!Incoming)
+    return std::unexpected(Incoming.error());
+
   const std::vector<MachineSuccessor> Successors = Block.Successors;
   for (const MachineSuccessor &Successor : Successors) {
     auto Result = removeSuccessor(Block, *Successor.Block);
@@ -178,4 +453,70 @@ Expected<void> MachineCFGUpdater::disconnectBlock(MachineBasicBlock &Block) {
   return {};
 }
 
+Expected<MachineBasicBlock *> MachineCFGUpdater::splitBlock(MachineBasicBlock &Block,
+                                                            MachineInstr &SplitBefore) {
+  auto Ownership = verifyOwnership(Block);
+  if (!Ownership)
+    return std::unexpected(Ownership.error());
+  if (!Block.isLinked() || SplitBefore.parent() != &Block) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "split point is not linked to the requested basic block");
+  }
+  bool MovesPhi = false;
+  for (const MachineInstr *Instruction = &SplitBefore; Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    MovesPhi |= isKnownPhi(*Instruction);
+  }
+  if (MovesPhi) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "a basic block cannot be split inside its PHI region");
+  }
+
+  auto Outgoing = validateOutgoingEdges(Block);
+  if (!Outgoing)
+    return std::unexpected(Outgoing.error());
+
+  auto NewBlockResult = Function->createBasicBlock();
+  if (!NewBlockResult)
+    return std::unexpected(NewBlockResult.error());
+  MachineBasicBlock *NewBlock = *NewBlockResult;
+  Expected<void> Inserted = Block.next() == nullptr
+                                ? Function->appendBlock(*NewBlock)
+                                : Function->insertBlockBefore(*Block.next(), *NewBlock);
+  if (!Inserted)
+    return std::unexpected(Inserted.error());
+
+  MachineInstr *Instruction = &SplitBefore;
+  while (Instruction != nullptr) {
+    MachineInstr *Next = Instruction->next();
+    auto Removed = Block.removeInstruction(*Instruction);
+    if (!Removed)
+      return std::unexpected(Removed.error());
+    auto Appended = NewBlock->appendInstruction(*Instruction);
+    if (!Appended)
+      return std::unexpected(Appended.error());
+    Instruction = Next;
+  }
+
+  auto Transferred = transferSuccessors(Block, *NewBlock);
+  if (!Transferred)
+    return std::unexpected(Transferred.error());
+  auto Connected = addSuccessor(Block, *NewBlock, BranchProbability::one());
+  if (!Connected)
+    return std::unexpected(Connected.error());
+  return NewBlock;
+}
+
+Expected<void> MachineCFGUpdater::deleteBlock(MachineBasicBlock &Block) {
+  auto Ownership = verifyOwnership(Block);
+  if (!Ownership)
+    return std::unexpected(Ownership.error());
+  if (!Block.isLinked())
+    return makeUnexpected(ErrorCode::InvalidArgument, "deleted CFG block is not linked");
+  auto Disconnected = disconnectBlock(Block);
+  if (!Disconnected)
+    return std::unexpected(Disconnected.error());
+  return Function->removeBlock(Block);
+}
+
 } // namespace rcc
diff --git a/backend/lib/CodeGen/MachineOperand.cpp b/backend/lib/CodeGen/MachineOperand.cpp
index ae46505..43a4f91 100644
--- a/backend/lib/CodeGen/MachineOperand.cpp
+++ b/backend/lib/CodeGen/MachineOperand.cpp
@@ -2,6 +2,7 @@
 
 #include "rcc/CodeGen/MachineOperand.h"
 
+#include "rcc/CodeGen/MachineBasicBlock.h"
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineInstr.h"
 #include "rcc/CodeGen/MachineRegisterInfo.h"
@@ -172,8 +173,7 @@ std::string IntegerImmediate::toUnsignedDecimal() const {
     return "0";
   std::vector<std::uint64_t> Remaining = Words;
   std::string Digits;
-  while (!std::ranges::all_of(Remaining,
-                              [](std::uint64_t Word) { return Word == 0; })) {
+  while (!std::ranges::all_of(Remaining, [](std::uint64_t Word) { return Word == 0; })) {
     unsigned __int128 Remainder = 0;
     for (auto Iterator = Remaining.rbegin(); Iterator != Remaining.rend(); ++Iterator) {
       const unsigned __int128 Dividend = (Remainder << 64U) | *Iterator;
@@ -537,6 +537,17 @@ Expected<void> MachineOperand::setSubReg(SubRegIndex SubReg) {
   return {};
 }
 
+Expected<void> MachineOperand::setBasicBlock(MachineBasicBlock &Block) {
+  if (OperandKind != Kind::BasicBlock)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "setBasicBlock requires a basic-block operand");
+  if (Parent != nullptr && &Block.function() != &Parent->function())
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "basic-block operand references another machine function");
+  std::get<BasicBlockOperand>(Storage).Block = &Block;
+  return {};
+}
+
 MachineOperand MachineOperand::cloneDetached() const {
   MachineOperand Result(OperandKind, Storage, TargetFlags);
   Result.RegFlags = RegFlags;
diff --git a/backend/lib/CodeGen/MachineSSAExit.cpp b/backend/lib/CodeGen/MachineSSAExit.cpp
new file mode 100644
index 0000000..e77bb2a
--- /dev/null
+++ b/backend/lib/CodeGen/MachineSSAExit.cpp
@@ -0,0 +1,1090 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineSSAExit.h"
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineFunctionCloner.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <ranges>
+#include <string>
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+struct EdgeKey final {
+  const MachineBasicBlock *From = nullptr;
+  const MachineBasicBlock *To = nullptr;
+
+  friend bool operator==(const EdgeKey &, const EdgeKey &) noexcept = default;
+};
+
+struct EdgeKeyHash final {
+  [[nodiscard]] std::size_t operator()(const EdgeKey &Key) const noexcept {
+    const std::size_t FromHash = std::hash<const MachineBasicBlock *>{}(Key.From);
+    const std::size_t ToHash = std::hash<const MachineBasicBlock *>{}(Key.To);
+    return FromHash ^ (ToHash << 1U);
+  }
+};
+
+struct RegisterValue final {
+  Register Reg;
+  SubRegIndex SubReg;
+  RegisterOperandFlags Flags;
+  std::uint32_t TargetFlags = 0;
+};
+
+struct PhiIncoming final {
+  RegisterValue Value;
+  MachineBasicBlock *Predecessor = nullptr;
+  bool IsUndef = false;
+};
+
+struct PhiPlan final {
+  MachineInstr *Instruction = nullptr;
+  RegisterValue Destination;
+  Register FreshIncoming;
+  std::vector<PhiIncoming> IncomingValues;
+};
+
+[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) {
+  Prefix.append(Source.message());
+  return Error(Source.code(), std::move(Prefix));
+}
+
+[[nodiscard]] Expected<void> requireProperties(const MachineFunction &Function,
+                                               const MachinePassContract &Contract) {
+  const MachineFunctionProperties Missing = Contract.Requires.missingFrom(Function.properties());
+  if (Missing.empty())
+    return {};
+  return makeUnexpected(ErrorCode::VerificationError,
+                        Contract.Name + " requires properties: " + Missing.toString());
+}
+
+[[nodiscard]] bool isPhi(const MachineInstr &Instruction, const TargetDescription &Target) {
+  const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
+  return Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Phi);
+}
+
+[[nodiscard]] bool isMeta(const MachineInstr &Instruction, const TargetDescription &Target) {
+  const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
+  return Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Meta);
+}
+
+[[nodiscard]] MachineInstr *firstTerminator(MachineBasicBlock &Block,
+                                            const TargetDescription &Target) {
+  for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+    if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Terminator))
+      return Instruction;
+  }
+  return nullptr;
+}
+
+[[nodiscard]] MachineInstr *firstCodeAfterPhiRegion(MachineBasicBlock &Block,
+                                                    const TargetDescription &Target) {
+  for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    if (!isPhi(*Instruction, Target) && !isMeta(*Instruction, Target))
+      return Instruction;
+  }
+  return nullptr;
+}
+
+[[nodiscard]] RegisterOperandFlags generatedDefFlags(RegisterOperandFlags Original) noexcept {
+  RegisterOperandFlags Result;
+  if (Original.has(RegisterOperandFlag::Undef))
+    Result.set(RegisterOperandFlag::Undef);
+  return Result;
+}
+
+[[nodiscard]] Expected<void> copyDebugLocation(MachineInstrBuilder &Builder,
+                                               const MachineInstr *Source) {
+  if (Source == nullptr || !Source->debugLocation())
+    return {};
+  return Builder.setDebugLocation(*Source->debugLocation());
+}
+
+[[nodiscard]] Expected<Register> cloneRegisterConstraints(MachineFunction &Function,
+                                                          Register Source) {
+  if (!Source.isVirtual()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "SSA deconstruction requires a virtual PHI destination");
+  }
+  auto SourceInfo = Function.registerInfo().virtualRegisterInfo(Source);
+  if (!SourceInfo)
+    return std::unexpected(SourceInfo.error());
+  const VirtualRegisterInfo Info = SourceInfo->get();
+
+  auto Fresh = Function.registerInfo().createVirtualRegister();
+  if (!Fresh)
+    return std::unexpected(Fresh.error());
+  if (Info.Type) {
+    auto SetType = Function.registerInfo().setType(*Fresh, *Info.Type);
+    if (!SetType)
+      return std::unexpected(SetType.error());
+  }
+  if (Info.Bank) {
+    auto SetBank = Function.registerInfo().setRegisterBank(*Fresh, *Info.Bank);
+    if (!SetBank)
+      return std::unexpected(SetBank.error());
+  }
+  if (Info.RegClass) {
+    auto SetClass = Function.registerInfo().setRegisterClass(*Fresh, *Info.RegClass);
+    if (!SetClass)
+      return std::unexpected(SetClass.error());
+  }
+  for (const PhysicalRegister Hint : Info.AllocationHints) {
+    auto AddedHint = Function.registerInfo().addAllocationHint(*Fresh, Hint);
+    if (!AddedHint)
+      return std::unexpected(AddedHint.error());
+  }
+  if (Info.TargetFlags != 0) {
+    auto SetFlags = Function.registerInfo().setTargetRegisterFlags(*Fresh, Info.TargetFlags);
+    if (!SetFlags)
+      return std::unexpected(SetFlags.error());
+  }
+  return *Fresh;
+}
+
+[[nodiscard]] Expected<MachineInstr *>
+buildCopy(MachineFunction &Function, const TargetDescription &Target,
+          const TargetSSAInfo &TargetInfo, MachineBasicBlock &Block, MachineInstr *Before,
+          RegisterValue Destination, RegisterValue Source, const MachineInstr *DebugSource) {
+  auto Legality = TargetInfo.validateCopy(Destination.Reg, Destination.SubReg, Source.Reg,
+                                          Source.SubReg, Function, Target);
+  if (!Legality)
+    return std::unexpected(prefixedError(Legality.error(), "illegal COPY: "));
+
+  MachineIRBuilder Builder(Function, Target);
+  auto Point =
+      Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(opcode(GenericOpcode::COPY));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  auto Def = Pending->addDef(Destination.Reg, generatedDefFlags(Destination.Flags),
+                             Destination.SubReg, Destination.TargetFlags);
+  if (!Def)
+    return std::unexpected(Def.error());
+  auto Use = Pending->addUse(Source.Reg, {}, Source.SubReg, Source.TargetFlags);
+  if (!Use)
+    return std::unexpected(Use.error());
+  auto Debug = copyDebugLocation(*Pending, DebugSource);
+  if (!Debug)
+    return std::unexpected(Debug.error());
+  return Pending->build();
+}
+
+[[nodiscard]] Expected<MachineInstr *>
+buildImplicitDef(MachineFunction &Function, const TargetDescription &Target,
+                 MachineBasicBlock &Block, MachineInstr *Before, RegisterValue Destination,
+                 const MachineInstr *DebugSource) {
+  MachineIRBuilder Builder(Function, Target);
+  auto Point =
+      Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(opcode(GenericOpcode::IMPLICIT_DEF));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  auto Def = Pending->addDef(Destination.Reg, generatedDefFlags(Destination.Flags),
+                             Destination.SubReg, Destination.TargetFlags);
+  if (!Def)
+    return std::unexpected(Def.error());
+  auto Debug = copyDebugLocation(*Pending, DebugSource);
+  if (!Debug)
+    return std::unexpected(Debug.error());
+  return Pending->build();
+}
+
+[[nodiscard]] bool isImplicitlyUndef(const MachineFunction &Function,
+                                     const MachineOperand &Operand) {
+  if (Operand.registerFlags().has(RegisterOperandFlag::Undef))
+    return true;
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr || Reg->isNoRegister())
+    return true;
+  if (!Reg->isVirtual())
+    return false;
+  const MachineOperand *Definition = Function.registerInfo().getUniqueVRegDef(*Reg);
+  if (Definition == nullptr || Definition->parent() == nullptr)
+    return false;
+  if (Definition->subReg().value() != 0 && Definition->subReg() != Operand.subReg())
+    return false;
+  const Opcode DefinitionOpcode = Definition->parent()->opcode();
+  return DefinitionOpcode == opcode(GenericOpcode::IMPLICIT_DEF) ||
+         DefinitionOpcode == opcode(GenericOpcode::G_IMPLICIT_DEF) ||
+         Definition->registerFlags().has(RegisterOperandFlag::Undef);
+}
+
+[[nodiscard]] Expected<void> validatePhiValue(const MachineFunction &Function,
+                                              const TargetDescription &Target,
+                                              const MachineOperand &Destination,
+                                              const MachineOperand &Source) {
+  const Register *DestinationReg = Destination.getIf<Register>();
+  const Register *SourceReg = Source.getIf<Register>();
+  if (DestinationReg == nullptr || SourceReg == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError, "PHI operands must name registers");
+  if (SourceReg->isNoRegister())
+    return {};
+
+  if (DestinationReg->isVirtual() && SourceReg->isVirtual()) {
+    auto DestinationInfo = Function.registerInfo().virtualRegisterInfo(*DestinationReg);
+    if (!DestinationInfo)
+      return std::unexpected(DestinationInfo.error());
+    auto SourceInfo = Function.registerInfo().virtualRegisterInfo(*SourceReg);
+    if (!SourceInfo)
+      return std::unexpected(SourceInfo.error());
+    if (DestinationInfo->get().Type && SourceInfo->get().Type &&
+        DestinationInfo->get().Type != SourceInfo->get().Type) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "PHI destination and incoming value types do not match");
+    }
+  }
+  return Target.validateTieCompatibility(Destination, Source, Function.registerInfo());
+}
+
+[[nodiscard]] Expected<std::vector<PhiPlan>> collectPhiPlans(MachineBasicBlock &Block,
+                                                             MachineFunction &Function,
+                                                             const TargetDescription &Target) {
+  std::vector<PhiPlan> Plans;
+  bool SawCode = false;
+  for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+    if (Descriptor == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "PHI elimination encountered an unknown opcode");
+    }
+    if (Instruction->opcode() == opcode(GenericOpcode::G_PHI)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "PHI elimination requires G_PHI to be selected to PHI");
+    }
+    if (!Descriptor->Flags.has(InstructionFlag::Phi)) {
+      SawCode |= !Descriptor->Flags.has(InstructionFlag::Meta);
+      continue;
+    }
+    if (SawCode) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "PHI instruction appears after the leading PHI/meta region");
+    }
+    if (Instruction->operandCount() < 3 || (Instruction->operandCount() - 1U) % 2U != 0) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "PHI must contain a destination and incoming value/block pairs");
+    }
+
+    MachineOperand *DestinationOperand = Instruction->operandAt(0);
+    const Register *Destination =
+        DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+    if (Destination == nullptr || !Destination->isVirtual() || !DestinationOperand->isDef() ||
+        DestinationOperand->isUse() || DestinationOperand->isImplicit()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "PHI destination must be an explicit virtual-register definition");
+    }
+
+    PhiPlan Plan;
+    Plan.Instruction = Instruction;
+    Plan.Destination =
+        RegisterValue{*Destination, DestinationOperand->subReg(),
+                      DestinationOperand->registerFlags(), DestinationOperand->targetFlags()};
+    std::unordered_set<MachineBasicBlock *> SeenPredecessors;
+    for (std::size_t Index = 1; Index < Instruction->operandCount(); Index += 2U) {
+      MachineOperand *SourceOperand = Instruction->operandAt(Index);
+      MachineOperand *BlockOperand = Instruction->operandAt(Index + 1U);
+      const Register *Source =
+          SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>();
+      const BasicBlockOperand *IncomingBlock =
+          BlockOperand == nullptr ? nullptr : BlockOperand->getIf<BasicBlockOperand>();
+      if (Source == nullptr || SourceOperand == nullptr || !SourceOperand->isUse() ||
+          SourceOperand->isDef() || SourceOperand->isImplicit() || IncomingBlock == nullptr ||
+          IncomingBlock->Block == nullptr || BlockOperand->isImplicit()) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "PHI incoming operands must be explicit register/block pairs");
+      }
+      if (std::ranges::find(Block.predecessors(), IncomingBlock->Block) ==
+          Block.predecessors().end()) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "PHI incoming block is not a CFG predecessor");
+      }
+      if (!SeenPredecessors.insert(IncomingBlock->Block).second) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "PHI contains duplicate incoming predecessors");
+      }
+      auto Compatibility = validatePhiValue(Function, Target, *DestinationOperand, *SourceOperand);
+      if (!Compatibility)
+        return std::unexpected(Compatibility.error());
+      Plan.IncomingValues.push_back(
+          PhiIncoming{RegisterValue{*Source, SourceOperand->subReg(),
+                                    SourceOperand->registerFlags(), SourceOperand->targetFlags()},
+                      IncomingBlock->Block, isImplicitlyUndef(Function, *SourceOperand)});
+    }
+    if (SeenPredecessors.size() != Block.predecessors().size()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "PHI incoming blocks do not exactly cover CFG predecessors");
+    }
+    Plans.push_back(std::move(Plan));
+  }
+  return Plans;
+}
+
+[[nodiscard]] Expected<void> copyLiveIns(const MachineBasicBlock &Source,
+                                         MachineBasicBlock &Destination) {
+  for (const MachineBasicBlockLiveIn &LiveIn : Source.liveIns()) {
+    auto Added = Destination.addLiveIn(LiveIn.PhysReg, LiveIn.Lanes);
+    if (!Added)
+      return std::unexpected(Added.error());
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<void> ensurePhysicalLiveIn(MachineBasicBlock &Block, PhysicalRegister Reg,
+                                                  const TargetDescription &Target) {
+  const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Reg);
+  if (Description == nullptr) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "PHI incoming value references an unknown physical register");
+  }
+  LaneMask Required;
+  for (const RegisterUnitLane &Unit : Description->Units)
+    Required = Required | Unit.Lanes;
+  if (Required.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "PHI incoming physical register has no addressable lanes");
+  }
+
+  for (const MachineBasicBlockLiveIn &LiveIn : Block.liveIns()) {
+    if (LiveIn.PhysReg != Reg)
+      continue;
+    if (LiveIn.Lanes.contains(Required))
+      return {};
+    const LaneMask Combined = LiveIn.Lanes | Required;
+    auto Removed = Block.removeLiveIn(Reg);
+    if (!Removed)
+      return std::unexpected(Removed.error());
+    return Block.addLiveIn(Reg, Combined);
+  }
+  return Block.addLiveIn(Reg, Required);
+}
+
+[[nodiscard]] Expected<MachineBasicBlock *>
+placePhiCopiesOnEdge(MachineFunction &Function, const TargetDescription &Target,
+                     const TargetSSAInfo &TargetInfo, MachineBasicBlock &From,
+                     MachineBasicBlock &To,
+                     std::unordered_map<EdgeKey, MachineBasicBlock *, EdgeKeyHash> &Cache,
+                     MachinePassResult &PassResult) {
+  if (From.successors().size() <= 1)
+    return &From;
+
+  const EdgeKey Key{&From, &To};
+  if (const auto Existing = Cache.find(Key); Existing != Cache.end())
+    return Existing->second;
+  if (std::ranges::none_of(From.successors(), [&To](const MachineSuccessor &Successor) {
+        return Successor.Block == &To;
+      })) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "PHI incoming predecessor has no edge to its successor");
+  }
+
+  auto SourceFallthrough = TargetInfo.isFallthroughEdge(From, To, Function, Target);
+  if (!SourceFallthrough)
+    return std::unexpected(SourceFallthrough.error());
+
+  MachineBasicBlock *LayoutPredecessor = To.previous();
+  if (LayoutPredecessor != nullptr && LayoutPredecessor != &From) {
+    auto OtherFallthrough = TargetInfo.isFallthroughEdge(*LayoutPredecessor, To, Function, Target);
+    if (!OtherFallthrough)
+      return std::unexpected(OtherFallthrough.error());
+    if (*OtherFallthrough) {
+      auto Branch = TargetInfo.insertUnconditionalBranch(*LayoutPredecessor, To, Function, Target);
+      if (!Branch)
+        return std::unexpected(Branch.error());
+      PassResult.Changed = true;
+      PassResult.Changes.add(MachinePassChange::Instructions);
+    }
+  }
+
+  auto EdgeBlockResult = Function.createBasicBlock();
+  if (!EdgeBlockResult)
+    return std::unexpected(EdgeBlockResult.error());
+  MachineBasicBlock *EdgeBlock = *EdgeBlockResult;
+  auto Inserted = Function.insertBlockBefore(To, *EdgeBlock);
+  if (!Inserted)
+    return std::unexpected(Inserted.error());
+
+  auto Rewritten = TargetInfo.rewriteBranchTarget(From, To, *EdgeBlock, Function, Target);
+  if (!Rewritten)
+    return std::unexpected(Rewritten.error());
+  if (!*Rewritten && !*SourceFallthrough) {
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "PHI elimination cannot split an indirect or unmodeled CFG edge");
+  }
+
+  auto Split = Function.cfgUpdater().splitEdge(From, To, *EdgeBlock);
+  if (!Split)
+    return std::unexpected(Split.error());
+  auto LiveIns = copyLiveIns(To, *EdgeBlock);
+  if (!LiveIns)
+    return std::unexpected(LiveIns.error());
+  auto Branch = TargetInfo.insertUnconditionalBranch(*EdgeBlock, To, Function, Target);
+  if (!Branch)
+    return std::unexpected(Branch.error());
+
+  Cache.emplace(Key, EdgeBlock);
+  PassResult.Changed = true;
+  PassResult.Changes.add(MachinePassChange::CFG);
+  PassResult.Changes.add(MachinePassChange::BlockLayout);
+  PassResult.Changes.add(MachinePassChange::Instructions);
+  if (*Rewritten)
+    PassResult.Changes.add(MachinePassChange::Operands);
+  return EdgeBlock;
+}
+
+[[nodiscard]] Expected<bool> clearStaleLivenessFlags(MachineFunction &Function) {
+  bool Changed = false;
+  for (MachineInstr *Instruction : Function.allInstructions()) {
+    if (Instruction->parent() == nullptr)
+      continue;
+    for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+      MachineOperand *Operand = Instruction->operandAt(Index);
+      if (Operand == nullptr || !Operand->isRegister())
+        continue;
+      RegisterOperandFlags Flags = Operand->registerFlags();
+      const bool HadStaleFlag =
+          Flags.has(RegisterOperandFlag::Kill) || Flags.has(RegisterOperandFlag::Dead);
+      if (!HadStaleFlag)
+        continue;
+      Flags.clear(RegisterOperandFlag::Kill);
+      Flags.clear(RegisterOperandFlag::Dead);
+      auto Updated = Operand->setRegisterFlags(Flags);
+      if (!Updated)
+        return std::unexpected(Updated.error());
+      Changed = true;
+    }
+  }
+  return Changed;
+}
+
+[[nodiscard]] Expected<SubRegIndex> subRegIndex(const MachineOperand &Operand,
+                                                const TargetDescription &Target) {
+  std::uint64_t Value = 0;
+  if (const auto *Immediate = Operand.getIf<std::int64_t>(); Immediate != nullptr) {
+    if (*Immediate <= 0)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "subregister pseudo requires a positive subregister index");
+    Value = static_cast<std::uint64_t>(*Immediate);
+  } else if (const auto *WideImmediate = Operand.getIf<IntegerImmediateOperand>();
+             WideImmediate != nullptr) {
+    if (WideImmediate->Value.isNegative() || WideImmediate->Value.bitWidth() > 64)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "subregister pseudo index does not fit an unsigned integer");
+    Value = WideImmediate->Value.words().front();
+  } else {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "subregister pseudo is missing its immediate index");
+  }
+  if (Value == 0 || Value > std::numeric_limits<std::uint32_t>::max()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "subregister pseudo index is outside the supported range");
+  }
+  const SubRegIndex Result = SubRegIndex::fromValue(static_cast<std::uint32_t>(Value));
+  if (Target.registers().subRegIndex(Result) == nullptr) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "subregister pseudo references an unknown target index");
+  }
+  return Result;
+}
+
+[[nodiscard]] Expected<SubRegIndex> composeSubReg(SubRegIndex Outer, SubRegIndex Inner,
+                                                  const TargetDescription &Target) {
+  if (Outer.value() == 0)
+    return Inner;
+  if (Inner.value() == 0)
+    return Outer;
+  const auto Composed = Target.registers().composeSubRegIndices(Outer, Inner);
+  if (!Composed) {
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "target cannot compose the requested subregister indices");
+  }
+  return *Composed;
+}
+
+[[nodiscard]] Expected<void> removeInstruction(MachineInstr &Instruction) {
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError, "rewritten instruction is not linked");
+  return Block->removeInstruction(Instruction);
+}
+
+[[nodiscard]] Expected<void> expandRegSequence(MachineInstr &Instruction, MachineFunction &Function,
+                                               const TargetDescription &Target,
+                                               const TargetSSAInfo &TargetInfo) {
+  if (Instruction.operandCount() < 3 || (Instruction.operandCount() - 1U) % 2U != 0) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "REG_SEQUENCE requires a destination and source/subregister pairs");
+  }
+  MachineOperand *DestinationOperand = Instruction.operandAt(0);
+  const Register *Destination =
+      DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+  if (Destination == nullptr || Destination->isNoRegister() || !DestinationOperand->isDef()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "REG_SEQUENCE requires a register destination definition");
+  }
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError, "REG_SEQUENCE is not linked to a block");
+
+  RegisterValue DestinationValue{*Destination, DestinationOperand->subReg(),
+                                 DestinationOperand->registerFlags(),
+                                 DestinationOperand->targetFlags()};
+  auto Initial =
+      buildImplicitDef(Function, Target, *Block, &Instruction, DestinationValue, &Instruction);
+  if (!Initial)
+    return std::unexpected(Initial.error());
+
+  for (std::size_t Index = 1; Index < Instruction.operandCount(); Index += 2U) {
+    MachineOperand *SourceOperand = Instruction.operandAt(Index);
+    MachineOperand *IndexOperand = Instruction.operandAt(Index + 1U);
+    const Register *Source = SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>();
+    if (Source == nullptr || SourceOperand == nullptr || !SourceOperand->isUse() ||
+        IndexOperand == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "REG_SEQUENCE contains a malformed source/subregister pair");
+    }
+    auto InnerSubReg = subRegIndex(*IndexOperand, Target);
+    if (!InnerSubReg)
+      return std::unexpected(InnerSubReg.error());
+    auto DestinationSubReg = composeSubReg(DestinationOperand->subReg(), *InnerSubReg, Target);
+    if (!DestinationSubReg)
+      return std::unexpected(DestinationSubReg.error());
+
+    RegisterValue LaneDestination{
+        *Destination, *DestinationSubReg, {}, DestinationOperand->targetFlags()};
+    if (isImplicitlyUndef(Function, *SourceOperand)) {
+      auto Undef =
+          buildImplicitDef(Function, Target, *Block, &Instruction, LaneDestination, &Instruction);
+      if (!Undef)
+        return std::unexpected(Undef.error());
+      continue;
+    }
+    RegisterValue SourceValue{*Source, SourceOperand->subReg(), SourceOperand->registerFlags(),
+                              SourceOperand->targetFlags()};
+    auto Copy = buildCopy(Function, Target, TargetInfo, *Block, &Instruction, LaneDestination,
+                          SourceValue, &Instruction);
+    if (!Copy)
+      return std::unexpected(Copy.error());
+  }
+  return removeInstruction(Instruction);
+}
+
+[[nodiscard]] Expected<void> expandInsertSubreg(MachineInstr &Instruction,
+                                                MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                const TargetSSAInfo &TargetInfo) {
+  if (Instruction.operandCount() != 4) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "INSERT_SUBREG requires destination, base, inserted value, and index");
+  }
+  MachineOperand *DestinationOperand = Instruction.operandAt(0);
+  MachineOperand *BaseOperand = Instruction.operandAt(1);
+  MachineOperand *InsertedOperand = Instruction.operandAt(2);
+  MachineOperand *IndexOperand = Instruction.operandAt(3);
+  const Register *Destination =
+      DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+  const Register *Base = BaseOperand == nullptr ? nullptr : BaseOperand->getIf<Register>();
+  const Register *Inserted =
+      InsertedOperand == nullptr ? nullptr : InsertedOperand->getIf<Register>();
+  if (Destination == nullptr || Base == nullptr || Inserted == nullptr ||
+      Destination->isNoRegister() || DestinationOperand == nullptr ||
+      !DestinationOperand->isDef() || BaseOperand == nullptr || !BaseOperand->isUse() ||
+      InsertedOperand == nullptr || !InsertedOperand->isUse() || IndexOperand == nullptr) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "INSERT_SUBREG contains malformed register operands");
+  }
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError, "INSERT_SUBREG is not linked to a block");
+
+  RegisterValue DestinationValue{*Destination, DestinationOperand->subReg(),
+                                 DestinationOperand->registerFlags(),
+                                 DestinationOperand->targetFlags()};
+  if (isImplicitlyUndef(Function, *BaseOperand)) {
+    auto Undef =
+        buildImplicitDef(Function, Target, *Block, &Instruction, DestinationValue, &Instruction);
+    if (!Undef)
+      return std::unexpected(Undef.error());
+  } else if (*Destination != *Base || DestinationOperand->subReg() != BaseOperand->subReg()) {
+    RegisterValue BaseValue{*Base, BaseOperand->subReg(), BaseOperand->registerFlags(),
+                            BaseOperand->targetFlags()};
+    auto Copy = buildCopy(Function, Target, TargetInfo, *Block, &Instruction, DestinationValue,
+                          BaseValue, &Instruction);
+    if (!Copy)
+      return std::unexpected(Copy.error());
+  }
+
+  auto InnerSubReg = subRegIndex(*IndexOperand, Target);
+  if (!InnerSubReg)
+    return std::unexpected(InnerSubReg.error());
+  auto DestinationSubReg = composeSubReg(DestinationOperand->subReg(), *InnerSubReg, Target);
+  if (!DestinationSubReg)
+    return std::unexpected(DestinationSubReg.error());
+  RegisterValue LaneDestination{
+      *Destination, *DestinationSubReg, {}, DestinationOperand->targetFlags()};
+  if (isImplicitlyUndef(Function, *InsertedOperand)) {
+    auto Undef =
+        buildImplicitDef(Function, Target, *Block, &Instruction, LaneDestination, &Instruction);
+    if (!Undef)
+      return std::unexpected(Undef.error());
+  } else {
+    RegisterValue InsertedValue{*Inserted, InsertedOperand->subReg(),
+                                InsertedOperand->registerFlags(), InsertedOperand->targetFlags()};
+    auto Copy = buildCopy(Function, Target, TargetInfo, *Block, &Instruction, LaneDestination,
+                          InsertedValue, &Instruction);
+    if (!Copy)
+      return std::unexpected(Copy.error());
+  }
+  return removeInstruction(Instruction);
+}
+
+[[nodiscard]] Expected<void> swapRegisterUses(MachineOperand &Left, MachineOperand &Right) {
+  const std::optional<Register> LeftReg = Left.registerValue();
+  const std::optional<Register> RightReg = Right.registerValue();
+  if (!LeftReg || !RightReg || !Left.isUse() || Left.isDef() || !Right.isUse() || Right.isDef()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "commutation requires two pure register uses");
+  }
+  const SubRegIndex LeftSubReg = Left.subReg();
+  const SubRegIndex RightSubReg = Right.subReg();
+  const RegisterOperandFlags LeftFlags = Left.registerFlags();
+  const RegisterOperandFlags RightFlags = Right.registerFlags();
+  const std::uint32_t LeftTargetFlags = Left.targetFlags();
+  const std::uint32_t RightTargetFlags = Right.targetFlags();
+
+  auto SetLeftReg = Left.setRegister(*RightReg);
+  if (!SetLeftReg)
+    return std::unexpected(SetLeftReg.error());
+  auto SetRightReg = Right.setRegister(*LeftReg);
+  if (!SetRightReg)
+    return std::unexpected(SetRightReg.error());
+  auto SetLeftSubReg = Left.setSubReg(RightSubReg);
+  if (!SetLeftSubReg)
+    return std::unexpected(SetLeftSubReg.error());
+  auto SetRightSubReg = Right.setSubReg(LeftSubReg);
+  if (!SetRightSubReg)
+    return std::unexpected(SetRightSubReg.error());
+  auto SetLeftFlags = Left.setRegisterFlags(RightFlags);
+  if (!SetLeftFlags)
+    return std::unexpected(SetLeftFlags.error());
+  auto SetRightFlags = Right.setRegisterFlags(LeftFlags);
+  if (!SetRightFlags)
+    return std::unexpected(SetRightFlags.error());
+  Left.setTargetFlags(RightTargetFlags);
+  Right.setTargetFlags(LeftTargetFlags);
+  return {};
+}
+
+[[nodiscard]] Expected<bool> tryCommute(MachineInstr &Instruction, std::size_t TiedUseIndex,
+                                        Register Destination, const TargetDescription &Target,
+                                        MachineFunction &Function) {
+  const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
+  if (Descriptor == nullptr || !Descriptor->Flags.has(InstructionFlag::Commutable))
+    return false;
+  MachineOperand *TiedUse = Instruction.operandAt(TiedUseIndex);
+  if (TiedUse == nullptr)
+    return makeUnexpected(ErrorCode::InternalError, "tied use disappeared during commutation");
+
+  for (std::size_t Index = 0; Index < Instruction.operandCount(); ++Index) {
+    if (Index == TiedUseIndex)
+      continue;
+    MachineOperand *Candidate = Instruction.operandAt(Index);
+    if (Candidate == nullptr || Candidate->isImplicit() || !Candidate->isUse() ||
+        Candidate->isDef() || Candidate->tiedOperandIndex() ||
+        Candidate->registerValue() != Destination || isImplicitlyUndef(Function, *Candidate)) {
+      continue;
+    }
+    auto Swapped = swapRegisterUses(*TiedUse, *Candidate);
+    if (!Swapped)
+      return std::unexpected(Swapped.error());
+    auto Validation = Target.validateInstruction(Instruction, Function.registerInfo());
+    if (Validation)
+      return true;
+    auto Restored = swapRegisterUses(*TiedUse, *Candidate);
+    if (!Restored)
+      return std::unexpected(Restored.error());
+  }
+  return false;
+}
+
+[[nodiscard]] Expected<void> rewriteUndefTie(MachineOperand &Use, const MachineOperand &Def) {
+  const std::optional<Register> Destination = Def.registerValue();
+  if (!Destination)
+    return makeUnexpected(ErrorCode::VerificationError, "tied definition is not a register");
+  auto SetRegister = Use.setRegister(*Destination);
+  if (!SetRegister)
+    return std::unexpected(SetRegister.error());
+  auto SetSubReg = Use.setSubReg(Def.subReg());
+  if (!SetSubReg)
+    return std::unexpected(SetSubReg.error());
+  RegisterOperandFlags Flags = Use.registerFlags();
+  Flags.set(RegisterOperandFlag::Undef);
+  Flags.clear(RegisterOperandFlag::Kill);
+  return Use.setRegisterFlags(Flags);
+}
+
+[[nodiscard]] Expected<void> verifyNoStageTenPseudos(const MachineFunction &Function,
+                                                     const TargetDescription &Target) {
+  for (const MachineInstr *Instruction : Function.allInstructions()) {
+    if (Instruction->parent() == nullptr)
+      continue;
+    if (Instruction->opcode() == opcode(GenericOpcode::G_PHI) ||
+        Instruction->opcode() == opcode(GenericOpcode::PHI) ||
+        Instruction->opcode() == opcode(GenericOpcode::REG_SEQUENCE) ||
+        Instruction->opcode() == opcode(GenericOpcode::INSERT_SUBREG)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "SSA exit left a Stage 10 pseudo instruction in MachineIR");
+    }
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+    if (Descriptor == nullptr)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "SSA exit produced an instruction with no descriptor");
+    for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+      const MachineOperand *Operand = Instruction->operandAt(Index);
+      if (Operand == nullptr || !Operand->isUse())
+        continue;
+      const std::optional<std::size_t> Tie = Operand->tiedOperandIndex();
+      if (!Tie)
+        continue;
+      const MachineOperand *Def = Instruction->operandAt(Tie.value());
+      if (Def == nullptr || Def->registerValue() != Operand->registerValue()) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "two-address rewrite left an unequal tied register");
+      }
+    }
+  }
+  return {};
+}
+
+} // namespace
+
+const MachinePassContract &PHIEliminationPass::contract() const noexcept {
+  static const MachinePassContract Contract{
+      .Name = "PHIElimination",
+      .Requires = {MachineFunctionProperty::IsSSA, MachineFunctionProperty::Selected,
+                   MachineFunctionProperty::RegBankSelected},
+      .Sets = {MachineFunctionProperty::NoPHIs},
+      .Clears = {MachineFunctionProperty::IsSSA},
+      .RequiredAnalyses = {},
+      .VerificationStage = PipelineStage::SSAEliminated,
+  };
+  return Contract;
+}
+
+Expected<MachinePassResult> PHIEliminationPass::run(MachineFunction &Function,
+                                                    const TargetDescription &Target,
+                                                    MachineAnalysisManager &Analyses) {
+  if (Info == nullptr) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "PHI elimination has no target SSA behavior interface");
+  }
+  auto Required = requireProperties(Function, contract());
+  if (!Required)
+    return std::unexpected(Required.error());
+
+  auto Trial = cloneMachineFunction(
+      Function, Target,
+      MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
+  if (!Trial) {
+    return std::unexpected(
+        prefixedError(Trial.error(), "PHI-elimination transaction setup failed: "));
+  }
+  MachineAnalysisManager TrialAnalyses;
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses);
+  if (!TrialResult)
+    return std::unexpected(TrialResult.error());
+
+  auto Result = runImplementation(Function, Target, Analyses);
+  if (!Result) {
+    return std::unexpected(prefixedError(
+        Result.error(), "PHI elimination diverged after a successful transaction preflight: "));
+  }
+  return Result;
+}
+
+Expected<MachinePassResult> PHIEliminationPass::runImplementation(MachineFunction &Function,
+                                                                  const TargetDescription &Target,
+                                                                  MachineAnalysisManager &) {
+  MachinePassResult Result;
+  std::unordered_map<EdgeKey, MachineBasicBlock *, EdgeKeyHash> SplitEdges;
+  const std::vector<MachineBasicBlock *> Blocks(Function.allBlocks().begin(),
+                                                Function.allBlocks().end());
+
+  for (MachineBasicBlock *Block : Blocks) {
+    auto Plans = collectPhiPlans(*Block, Function, Target);
+    if (!Plans)
+      return std::unexpected(Plans.error());
+    if (Plans->empty())
+      continue;
+
+    for (PhiPlan &Plan : *Plans) {
+      auto Fresh = cloneRegisterConstraints(Function, Plan.Destination.Reg);
+      if (!Fresh)
+        return std::unexpected(Fresh.error());
+      Plan.FreshIncoming = *Fresh;
+    }
+
+    for (PhiPlan &Plan : *Plans) {
+      for (const PhiIncoming &Incoming : Plan.IncomingValues) {
+        auto EdgeBlock = placePhiCopiesOnEdge(Function, Target, *Info, *Incoming.Predecessor,
+                                              *Block, SplitEdges, Result);
+        if (!EdgeBlock)
+          return std::unexpected(EdgeBlock.error());
+        if (*EdgeBlock != Incoming.Predecessor) {
+          const std::optional<PhysicalRegister> Physical = Incoming.Value.Reg.physicalRegister();
+          if (Physical) {
+            auto LiveIn = ensurePhysicalLiveIn(**EdgeBlock, *Physical, Target);
+            if (!LiveIn)
+              return std::unexpected(LiveIn.error());
+          }
+        }
+        MachineInstr *Terminator = firstTerminator(**EdgeBlock, Target);
+        RegisterValue Fresh{Plan.FreshIncoming, Plan.Destination.SubReg, Plan.Destination.Flags,
+                            Plan.Destination.TargetFlags};
+        Expected<MachineInstr *> Transfer =
+            Incoming.IsUndef ? buildImplicitDef(Function, Target, **EdgeBlock, Terminator, Fresh,
+                                                Plan.Instruction)
+                             : buildCopy(Function, Target, *Info, **EdgeBlock, Terminator, Fresh,
+                                         Incoming.Value, Plan.Instruction);
+        if (!Transfer)
+          return std::unexpected(Transfer.error());
+        Result.Changed = true;
+        Result.Changes.add(MachinePassChange::Instructions);
+      }
+    }
+
+    MachineInstr *InsertionPoint = firstCodeAfterPhiRegion(*Block, Target);
+    for (PhiPlan &Plan : *Plans) {
+      RegisterValue Fresh{
+          Plan.FreshIncoming, Plan.Destination.SubReg, {}, Plan.Destination.TargetFlags};
+      auto Copy = buildCopy(Function, Target, *Info, *Block, InsertionPoint, Plan.Destination,
+                            Fresh, Plan.Instruction);
+      if (!Copy)
+        return std::unexpected(Copy.error());
+      Result.Changed = true;
+      Result.Changes.add(MachinePassChange::Instructions);
+    }
+
+    for (PhiPlan &Plan : *Plans) {
+      auto Removed = Block->removeInstruction(*Plan.Instruction);
+      if (!Removed)
+        return std::unexpected(Removed.error());
+    }
+    Result.Changes.add(MachinePassChange::Registers);
+  }
+
+  if (Result.Changed && Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
+    auto Cleared = clearStaleLivenessFlags(Function);
+    if (!Cleared)
+      return std::unexpected(Cleared.error());
+    if (*Cleared)
+      Result.Changes.add(MachinePassChange::Operands);
+  }
+  Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
+  return Result;
+}
+
+const MachinePassContract &TwoAddressRewritePass::contract() const noexcept {
+  static const MachinePassContract Contract{
+      .Name = "TwoAddressRewrite",
+      .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs},
+      .Sets = {MachineFunctionProperty::TiedOpsRewritten},
+      .Clears = {MachineFunctionProperty::IsSSA},
+      .RequiredAnalyses = {},
+      .VerificationStage = PipelineStage::TiedOpsRewritten,
+  };
+  return Contract;
+}
+
+Expected<MachinePassResult> TwoAddressRewritePass::run(MachineFunction &Function,
+                                                       const TargetDescription &Target,
+                                                       MachineAnalysisManager &Analyses) {
+  if (Info == nullptr) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "two-address rewrite has no target SSA behavior interface");
+  }
+  auto Required = requireProperties(Function, contract());
+  if (!Required)
+    return std::unexpected(Required.error());
+
+  auto Trial = cloneMachineFunction(
+      Function, Target,
+      MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
+  if (!Trial) {
+    return std::unexpected(prefixedError(Trial.error(), "two-address transaction setup failed: "));
+  }
+  MachineAnalysisManager TrialAnalyses;
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses);
+  if (!TrialResult)
+    return std::unexpected(TrialResult.error());
+
+  auto Result = runImplementation(Function, Target, Analyses);
+  if (!Result) {
+    return std::unexpected(prefixedError(
+        Result.error(), "two-address rewrite diverged after a successful transaction preflight: "));
+  }
+  return Result;
+}
+
+Expected<MachinePassResult>
+TwoAddressRewritePass::runImplementation(MachineFunction &Function, const TargetDescription &Target,
+                                         MachineAnalysisManager &) {
+  MachinePassResult Result;
+  const std::vector<MachineInstr *> Instructions(Function.allInstructions().begin(),
+                                                 Function.allInstructions().end());
+  for (MachineInstr *Instruction : Instructions) {
+    if (Instruction->parent() == nullptr)
+      continue;
+    if (Instruction->opcode() == opcode(GenericOpcode::REG_SEQUENCE)) {
+      auto Expanded = expandRegSequence(*Instruction, Function, Target, *Info);
+      if (!Expanded)
+        return std::unexpected(Expanded.error());
+      Result.Changed = true;
+      Result.Changes.add(MachinePassChange::Instructions);
+      continue;
+    }
+    if (Instruction->opcode() == opcode(GenericOpcode::INSERT_SUBREG)) {
+      auto Expanded = expandInsertSubreg(*Instruction, Function, Target, *Info);
+      if (!Expanded)
+        return std::unexpected(Expanded.error());
+      Result.Changed = true;
+      Result.Changes.add(MachinePassChange::Instructions);
+      continue;
+    }
+
+    std::size_t RewriteAttempts = 0;
+    bool Restart = true;
+    while (Restart && Instruction->parent() != nullptr) {
+      Restart = false;
+      if (++RewriteAttempts > Instruction->operandCount() * 2U + 8U) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "two-address target conversion did not make progress");
+      }
+      const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+      if (Descriptor == nullptr) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "two-address rewrite encountered an unknown opcode");
+      }
+
+      for (std::size_t UseIndex = 0; UseIndex < Instruction->operandCount(); ++UseIndex) {
+        MachineOperand *Use = Instruction->operandAt(UseIndex);
+        if (Use == nullptr || !Use->isUse())
+          continue;
+        const std::optional<std::size_t> TiedDefIndex = Use->tiedOperandIndex();
+        if (!TiedDefIndex)
+          continue;
+        const std::size_t DefIndex = TiedDefIndex.value();
+        MachineOperand *Def = Instruction->operandAt(DefIndex);
+        if (Def == nullptr || !Def->isDef()) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "tied use does not reference a definition");
+        }
+        const std::optional<Register> DefReg = Def->registerValue();
+        const std::optional<Register> UseReg = Use->registerValue();
+        if (!DefReg || !UseReg || DefReg->isNoRegister()) {
+          return makeUnexpected(ErrorCode::Unsupported,
+                                "two-address rewrite requires register ties");
+        }
+        if (*DefReg == *UseReg)
+          continue;
+
+        if (isImplicitlyUndef(Function, *Use)) {
+          auto Rewritten = rewriteUndefTie(*Use, *Def);
+          if (!Rewritten)
+            return std::unexpected(Rewritten.error());
+          Result.Changed = true;
+          Result.Changes.add(MachinePassChange::Operands);
+          continue;
+        }
+
+        auto Commuted = tryCommute(*Instruction, UseIndex, *DefReg, Target, Function);
+        if (!Commuted)
+          return std::unexpected(Commuted.error());
+        if (*Commuted) {
+          Result.Changed = true;
+          Result.Changes.add(MachinePassChange::Operands);
+          continue;
+        }
+
+        auto Converted =
+            Info->tryConvertToThreeAddress(*Instruction, DefIndex, UseIndex, Function, Target);
+        if (!Converted)
+          return std::unexpected(Converted.error());
+        if (*Converted) {
+          Result.Changed = true;
+          Result.Changes.add(MachinePassChange::Instructions);
+          Result.Changes.add(MachinePassChange::Operands);
+          Result.Changes.add(MachinePassChange::Registers);
+          Restart = true;
+          break;
+        }
+
+        MachineBasicBlock *Block = Instruction->parent();
+        if (Block == nullptr)
+          return makeUnexpected(ErrorCode::InternalError,
+                                "two-address instruction disappeared before COPY insertion");
+        RegisterValue Destination{*DefReg, Def->subReg(), Def->registerFlags(), Def->targetFlags()};
+        RegisterValue Source{*UseReg, Use->subReg(), Use->registerFlags(), Use->targetFlags()};
+        auto Copy = buildCopy(Function, Target, *Info, *Block, Instruction, Destination, Source,
+                              Instruction);
+        if (!Copy)
+          return std::unexpected(Copy.error());
+        auto SetRegister = Use->setRegister(*DefReg);
+        if (!SetRegister)
+          return std::unexpected(SetRegister.error());
+        auto SetSubReg = Use->setSubReg(Def->subReg());
+        if (!SetSubReg)
+          return std::unexpected(SetSubReg.error());
+        RegisterOperandFlags Flags = Use->registerFlags();
+        Flags.clear(RegisterOperandFlag::Kill);
+        auto SetFlags = Use->setRegisterFlags(Flags);
+        if (!SetFlags)
+          return std::unexpected(SetFlags.error());
+        Result.Changed = true;
+        Result.Changes.add(MachinePassChange::Instructions);
+        Result.Changes.add(MachinePassChange::Operands);
+      }
+    }
+  }
+
+  auto FinalState = verifyNoStageTenPseudos(Function, Target);
+  if (!FinalState)
+    return std::unexpected(FinalState.error());
+  if (Result.Changed && Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
+    auto Cleared = clearStaleLivenessFlags(Function);
+    if (!Cleared)
+      return std::unexpected(Cleared.error());
+    if (*Cleared)
+      Result.Changes.add(MachinePassChange::Operands);
+  }
+  Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
+  return Result;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp
index f6f5640..8f4809a 100644
--- a/backend/lib/CodeGen/MachineVerifier.cpp
+++ b/backend/lib/CodeGen/MachineVerifier.cpp
@@ -2,6 +2,7 @@
 
 #include "rcc/CodeGen/MachineVerifier.h"
 
+#include "rcc/CodeGen/GenericOpcodes.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
 #include "rcc/CodeGen/MachineFrameInfo.h"
 #include "rcc/CodeGen/MachineFunction.h"
@@ -87,6 +88,9 @@ public:
     auto CFGResult = verifyCFG();
     if (!CFGResult)
       return CFGResult;
+    auto PHIResult = verifyPHIs();
+    if (!PHIResult)
+      return PHIResult;
     auto RegisterResult = verifyRegisterInfo();
     if (!RegisterResult)
       return RegisterResult;
@@ -428,9 +432,8 @@ private:
   }
 
   [[nodiscard]] Expected<void> verifyFrameLifetimes() const {
-    auto VerifyPoints =
-        [this](std::span<const MachineFrameSaveRestorePoint> Points,
-               std::string_view Kind) -> Expected<void> {
+    auto VerifyPoints = [this](std::span<const MachineFrameSaveRestorePoint> Points,
+                               std::string_view Kind) -> Expected<void> {
       for (const MachineFrameSaveRestorePoint &Point : Points) {
         if (!LinkedBlockIDs.contains(Point.Block)) {
           return fail(std::string("frame ") + std::string(Kind) +
@@ -591,6 +594,8 @@ private:
     }
 
     HasPhi |= Descriptor->Flags.has(InstructionFlag::Phi);
+    HasStageTenPseudo |= Instruction.opcode() == opcode(GenericOpcode::REG_SEQUENCE) ||
+                         Instruction.opcode() == opcode(GenericOpcode::INSERT_SUBREG);
     HasGenericInstruction |= Descriptor->Flags.has(InstructionFlag::Generic);
     HasExecutablePseudo |= Descriptor->Flags.has(InstructionFlag::Pseudo) &&
                            !Descriptor->Flags.has(InstructionFlag::Meta) &&
@@ -708,6 +713,75 @@ private:
     return {};
   }
 
+  [[nodiscard]] Expected<void> verifyPHIs() {
+    for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+         Block = Block->next()) {
+      bool SawNonMetaInstruction = false;
+      for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+           Instruction = Instruction->next()) {
+        const InstructionDescriptor *Descriptor =
+            Target.instructionDescriptor(Instruction->opcode());
+        if (Descriptor == nullptr)
+          return fail("PHI verification encountered an unregistered instruction");
+
+        if (!Descriptor->Flags.has(InstructionFlag::Phi)) {
+          SawNonMetaInstruction |= !Descriptor->Flags.has(InstructionFlag::Meta);
+          continue;
+        }
+        if (SawNonMetaInstruction)
+          return fail("PHI instruction appears after a non-meta instruction");
+
+        const std::span<const MachineOperand> Operands = Instruction->operands();
+        if (Operands.size() < 3 || (Operands.size() - 1U) % 2U != 0) {
+          return fail("PHI must contain a destination and at least one incoming pair");
+        }
+        const Register *Destination = Operands.front().getIf<Register>();
+        if (Destination == nullptr || !Destination->isVirtual() || !Operands.front().isDef() ||
+            Operands.front().isUse() || Operands.front().isImplicit()) {
+          return fail("PHI destination must be an explicit virtual-register definition");
+        }
+
+        std::unordered_set<const MachineBasicBlock *> IncomingBlocks;
+        for (std::size_t Index = 1; Index < Operands.size(); Index += 2U) {
+          const MachineOperand &ValueOperand = Operands[Index];
+          const MachineOperand &BlockOperand = Operands[Index + 1U];
+          const Register *Value = ValueOperand.getIf<Register>();
+          const BasicBlockOperand *Incoming = BlockOperand.getIf<BasicBlockOperand>();
+          if (Value == nullptr || !ValueOperand.isUse() || ValueOperand.isDef() ||
+              ValueOperand.isImplicit() || Incoming == nullptr || Incoming->Block == nullptr ||
+              BlockOperand.isImplicit()) {
+            return fail("PHI incoming operands must be explicit register/block pairs");
+          }
+          if (std::ranges::find(Block->predecessors(), Incoming->Block) ==
+              Block->predecessors().end()) {
+            return fail("PHI incoming block is not a CFG predecessor");
+          }
+          if (!IncomingBlocks.insert(Incoming->Block).second)
+            return fail("PHI contains duplicate incoming blocks");
+
+          if (!Value->isNoRegister() && Destination->isVirtual() && Value->isVirtual() &&
+              Operands.front().subReg().value() == 0 && ValueOperand.subReg().value() == 0) {
+            auto DestinationInfo = Function.registerInfo().virtualRegisterInfo(*Destination);
+            auto ValueInfo = Function.registerInfo().virtualRegisterInfo(*Value);
+            if (!DestinationInfo || !ValueInfo)
+              return fail("PHI references an unknown virtual register");
+            if (DestinationInfo->get().Type && ValueInfo->get().Type &&
+                DestinationInfo->get().Type != ValueInfo->get().Type) {
+              return fail("PHI destination and incoming value types do not match");
+            }
+          }
+          auto Compatibility = Target.validateTieCompatibility(Operands.front(), ValueOperand,
+                                                               Function.registerInfo());
+          if (!Compatibility)
+            return failWith("PHI register compatibility", Compatibility.error());
+        }
+        if (IncomingBlocks.size() != Block->predecessors().size())
+          return fail("PHI incoming blocks do not exactly cover CFG predecessors");
+      }
+    }
+    return {};
+  }
+
   [[nodiscard]] Expected<void> verifyRegisterInfo() {
     const MachineRegisterInfo &RegInfo = Function.registerInfo();
     std::unordered_set<PhysicalRegister> FunctionLiveIns;
@@ -767,6 +841,9 @@ private:
     if (Has(MachineFunctionProperty::TiedOpsRewritten) && !Has(MachineFunctionProperty::Selected)) {
       return fail("TiedOpsRewritten requires Selected");
     }
+    if (Has(MachineFunctionProperty::TiedOpsRewritten) && !Has(MachineFunctionProperty::NoPHIs)) {
+      return fail("TiedOpsRewritten requires NoPHIs");
+    }
     if (Has(MachineFunctionProperty::FrameFinalized) &&
         (!Has(MachineFunctionProperty::NoVRegs) || !Has(MachineFunctionProperty::NoFrameIndices))) {
       return fail("FrameFinalized requires NoVRegs and NoFrameIndices");
@@ -797,6 +874,9 @@ private:
     if (Has(MachineFunctionProperty::TiedOpsRewritten) && HasUnrewrittenTie) {
       return fail("TiedOpsRewritten function has unequal tied registers");
     }
+    if (Has(MachineFunctionProperty::TiedOpsRewritten) && HasStageTenPseudo) {
+      return fail("TiedOpsRewritten function contains a Stage 10 pseudo");
+    }
 
     const bool NeedsTypes = Options.Mode == MachineVerifierMode::PreLegalizer ||
                             Has(MachineFunctionProperty::Legalized) ||
@@ -837,6 +917,7 @@ private:
   bool HasExecutablePseudo = false;
   bool HasFrameIndex = false;
   bool HasUnrewrittenTie = false;
+  bool HasStageTenPseudo = false;
   bool HasLiveVirtualRegister = false;
   bool MissingVirtualType = false;
   bool MissingVirtualBank = false;
diff --git a/backend/lib/CodeGen/TargetDescription.cpp b/backend/lib/CodeGen/TargetDescription.cpp
index e2bbe8a..e8c7d79 100644
--- a/backend/lib/CodeGen/TargetDescription.cpp
+++ b/backend/lib/CodeGen/TargetDescription.cpp
@@ -58,7 +58,13 @@ Expected<TargetDescription> TargetDescription::create(InstructionSet Instruction
 
   for (const InstructionDescriptor &Instruction : Instructions.descriptors()) {
     for (const OperandDescriptor &Operand : Instruction.Operands) {
-      if ((Operand.AllowedTargetFlags & ~MIRText->serializableOperandFlagMask()) != 0) {
+      if (Operand.AllowAnyTargetFlags && Operand.AllowedTargetFlags != 0) {
+        return makeUnexpected(
+            ErrorCode::InvalidArgument,
+            "instruction operand cannot combine unrestricted and explicit target flags");
+      }
+      if (!Operand.AllowAnyTargetFlags &&
+          (Operand.AllowedTargetFlags & ~MIRText->serializableOperandFlagMask()) != 0) {
         return makeUnexpected(
             ErrorCode::InvalidArgument,
             "instruction operand allows a target flag outside the MIR text schema");