[CodeGen] Split PHI elimination and two-address rewriting

4 files changed, 634 insertions, 487 deletions

diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index 996f771..22bf032 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -66,7 +66,7 @@ set(
   RegAllocFast.cpp
   RegAllocPBQP.cpp
   VirtRegMap.cpp
-  MachineSSAExit.cpp
+  PHIElimination.cpp
   MachineVerifier.cpp
   MachineFunctionProperties.cpp
   MachineFunctionRecords.cpp
@@ -80,6 +80,7 @@ set(
   TargetMIRTextInfo.cpp
   TargetRegisterInfo.cpp
   TargetSchedulingModel.cpp
+  TwoAddressInstructionPass.cpp
 )
 set(
   RCCBackendCodeGenHeaders
@@ -155,7 +156,7 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/Spiller.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetRegisterAllocationInfo.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/VirtRegMap.h"
-  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineSSAExit.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PHIElimination.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"
@@ -172,6 +173,7 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetMemoryFolding.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetRegisterInfo.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetSchedulingModel.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TwoAddressInstructionPass.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetPseudoExpansion.h"
 )
 
@@ -271,7 +273,7 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBase.h"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBasic.h"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocInternal.h"
-  "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/PHIElimination.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecords.cpp"
@@ -285,6 +287,7 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/TargetMIRTextInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TargetRegisterInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TargetSchedulingModel.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/TwoAddressInstructionPass.cpp"
   ${RCCBackendCodeGenHeaders}
 )
 rcc_backend_register_tidy_files(
@@ -349,7 +352,7 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocFast.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocPBQP.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/VirtRegMap.cpp"
-  "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/PHIElimination.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecords.cpp"
@@ -363,4 +366,5 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/TargetMIRTextInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TargetRegisterInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TargetSchedulingModel.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/TwoAddressInstructionPass.cpp"
 )
diff --git a/backend/lib/CodeGen/PHIElimination.cpp b/backend/lib/CodeGen/PHIElimination.cpp
new file mode 100644
index 0000000..5539708
--- /dev/null
+++ b/backend/lib/CodeGen/PHIElimination.cpp
@@ -0,0 +1,610 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/PHIElimination.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/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 <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 TargetInstrInfo &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 TargetInstrInfo &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.insertBranch(*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.insertBranch(*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<void> repairTrackedLiveness(MachineFunction &Function,
+                                                   const TargetDescription &Target,
+                                                   MachinePassResult &Result) {
+  if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
+    return {};
+  }
+  auto Rebuilt = rebuildMachineLiveness(Function, Target);
+  if (!Rebuilt)
+    return std::unexpected(Rebuilt.error());
+  if (*Rebuilt)
+    Result.Changes.add(MachinePassChange::Operands);
+  return {};
+}
+
+} // namespace
+
+const MachinePassContract &PHIEliminationPass::contract() const noexcept {
+  static const MachinePassContract Contract{
+      .Name = "phi-node-elimination",
+      .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) {
+  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: "));
+  }
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
+  if (!TrialResult)
+    return std::unexpected(TrialResult.error());
+
+  Actions.beginReplay();
+  auto Result = runImplementation(Function, Target, Actions);
+  if (!Result) {
+    return std::unexpected(prefixedError(
+        Result.error(), "PHI elimination diverged after a successful transaction preflight: "));
+  }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
+  return Result;
+}
+
+Expected<MachinePassResult> PHIEliminationPass::runImplementation(MachineFunction &Function,
+                                                                  const TargetDescription &Target,
+                                                                  MachineActionReplay &Actions) {
+  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 Accepted = Actions.request("eliminate-phi", Function, Plan.Instruction->stableID());
+      if (!Accepted)
+        return std::unexpected(Accepted.error());
+      if (!*Accepted) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "required PHI elimination action was rejected");
+      }
+      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 Repaired = repairTrackedLiveness(Function, Target, Result);
+    if (!Repaired)
+      return std::unexpected(
+          prefixedError(Repaired.error(), "PHI-elimination liveness repair failed: "));
+  }
+  Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
+  return Result;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineSSAExit.cpp b/backend/lib/CodeGen/TwoAddressInstructionPass.cpp
index ec10b3b..1959b90 100644
--- a/backend/lib/CodeGen/MachineSSAExit.cpp
+++ b/backend/lib/CodeGen/TwoAddressInstructionPass.cpp
@@ -1,10 +1,9 @@
 // SPDX-License-Identifier: GPL-3.0-or-later
 
-#include "rcc/CodeGen/MachineSSAExit.h"
+#include "rcc/CodeGen/TwoAddressInstructionPass.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"
@@ -13,37 +12,19 @@
 #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 <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;
@@ -51,19 +32,6 @@ struct RegisterValue final {
   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));
@@ -78,37 +46,6 @@ struct PhiPlan final {
                         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))
@@ -123,48 +60,6 @@ struct PhiPlan final {
   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 TargetInstrInfo &TargetInfo, MachineBasicBlock &Block, MachineInstr *Before,
@@ -237,228 +132,6 @@ buildImplicitDef(MachineFunction &Function, const TargetDescription &Target,
          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 TargetInstrInfo &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.insertBranch(*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.insertBranch(*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<void> repairTrackedLiveness(MachineFunction &Function,
                                                    const TargetDescription &Target,
                                                    MachinePassResult &Result) {
@@ -774,143 +447,7 @@ placePhiCopiesOnEdge(MachineFunction &Function, const TargetDescription &Target,
 
 } // namespace
 
-const MachinePassContract &PHIEliminationPass::contract() const noexcept {
-  static const MachinePassContract Contract{
-      .Name = "phi-node-elimination",
-      .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 instruction information");
-  }
-  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: "));
-  }
-  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
-  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
-  if (!TrialResult)
-    return std::unexpected(TrialResult.error());
-
-  Actions.beginReplay();
-  auto Result = runImplementation(Function, Target, Actions);
-  if (!Result) {
-    return std::unexpected(prefixedError(
-        Result.error(), "PHI elimination diverged after a successful transaction preflight: "));
-  }
-  auto Replayed = Actions.finishReplay();
-  if (!Replayed)
-    return std::unexpected(Replayed.error());
-  return Result;
-}
-
-Expected<MachinePassResult> PHIEliminationPass::runImplementation(MachineFunction &Function,
-                                                                  const TargetDescription &Target,
-                                                                  MachineActionReplay &Actions) {
-  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 Accepted = Actions.request("eliminate-phi", Function, Plan.Instruction->stableID());
-      if (!Accepted)
-        return std::unexpected(Accepted.error());
-      if (!*Accepted) {
-        return makeUnexpected(ErrorCode::VerificationError,
-                              "required PHI elimination action was rejected");
-      }
-      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 Repaired = repairTrackedLiveness(Function, Target, Result);
-    if (!Repaired)
-      return std::unexpected(
-          prefixedError(Repaired.error(), "PHI-elimination liveness repair failed: "));
-  }
-  Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
-  return Result;
-}
-
-const MachinePassContract &TwoAddressRewritePass::contract() const noexcept {
+const MachinePassContract &TwoAddressInstructionPass::contract() const noexcept {
   static const MachinePassContract Contract{
       .Name = "twoaddressinstruction",
       .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs},
@@ -922,13 +459,9 @@ const MachinePassContract &TwoAddressRewritePass::contract() const noexcept {
   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 instruction information");
-  }
+Expected<MachinePassResult> TwoAddressInstructionPass::run(MachineFunction &Function,
+                                                           const TargetDescription &Target,
+                                                           MachineAnalysisManager &Analyses) {
   auto Required = requireProperties(Function, contract());
   if (!Required)
     return std::unexpected(Required.error());
@@ -956,9 +489,8 @@ Expected<MachinePassResult> TwoAddressRewritePass::run(MachineFunction &Function
   return Result;
 }
 
-Expected<MachinePassResult>
-TwoAddressRewritePass::runImplementation(MachineFunction &Function, const TargetDescription &Target,
-                                         MachineActionReplay &Actions) {
+Expected<MachinePassResult> TwoAddressInstructionPass::runImplementation(
+    MachineFunction &Function, const TargetDescription &Target, MachineActionReplay &Actions) {
   MachinePassResult Result;
   const std::vector<MachineInstr *> Instructions(Function.allInstructions().begin(),
                                                  Function.allInstructions().end());
@@ -972,7 +504,7 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target
       if (!*Accepted)
         return makeUnexpected(ErrorCode::VerificationError,
                               "required REG_SEQUENCE expansion action was rejected");
-      auto Expanded = expandRegSequence(*Instruction, Function, Target, *Info);
+      auto Expanded = expandRegSequence(*Instruction, Function, Target, Info);
       if (!Expanded)
         return std::unexpected(Expanded.error());
       Result.Changed = true;
@@ -986,7 +518,7 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target
       if (!*Accepted)
         return makeUnexpected(ErrorCode::VerificationError,
                               "required INSERT_SUBREG expansion action was rejected");
-      auto Expanded = expandInsertSubreg(*Instruction, Function, Target, *Info);
+      auto Expanded = expandInsertSubreg(*Instruction, Function, Target, Info);
       if (!Expanded)
         return std::unexpected(Expanded.error());
       Result.Changed = true;
@@ -1066,7 +598,7 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target
           return std::unexpected(AllowConversion.error());
         if (*AllowConversion) {
           auto Converted =
-              Info->tryConvertToThreeAddress(*Instruction, DefIndex, UseIndex, Function, Target);
+              Info.tryConvertToThreeAddress(*Instruction, DefIndex, UseIndex, Function, Target);
           if (!Converted)
             return std::unexpected(Converted.error());
           if (*Converted) {
@@ -1091,7 +623,7 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target
                                 "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,
+        auto Copy = buildCopy(Function, Target, Info, *Block, Instruction, Destination, Source,
                               Instruction);
         if (!Copy)
           return std::unexpected(Copy.error());
diff --git a/backend/lib/Target/RISCV/RISCVPipeline.cpp b/backend/lib/Target/RISCV/RISCVPipeline.cpp
index 5212838..c5601ef 100644
--- a/backend/lib/Target/RISCV/RISCVPipeline.cpp
+++ b/backend/lib/Target/RISCV/RISCVPipeline.cpp
@@ -11,9 +11,10 @@
 #include "rcc/CodeGen/MachineCombiner.h"
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineOptimizationPipeline.h"
-#include "rcc/CodeGen/MachineSSAExit.h"
+#include "rcc/CodeGen/PHIElimination.h"
 #include "rcc/CodeGen/RegAllocPBQP.h"
 #include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/CodeGen/TwoAddressInstructionPass.h"
 
 #include <memory>
 #include <ranges>
@@ -52,7 +53,7 @@ template <typename PassT, typename... ArgumentT>
   Added = addPass<PHIEliminationPass>(Pipeline, instrInfo());
   if (!Added)
     return std::unexpected(Added.error());
-  return addPass<TwoAddressRewritePass>(Pipeline, instrInfo());
+  return addPass<TwoAddressInstructionPass>(Pipeline, instrInfo());
 }
 
 [[nodiscard]] Expected<void> addRegisterAllocationPipeline(MachinePassManager &Pipeline) {
@@ -110,7 +111,7 @@ Expected<void> addCanonicalPipeline(MachinePassManager &Pipeline, const MachineF
     }
   }
   if (!Function.properties().has(MachineFunctionProperty::TiedOpsRewritten)) {
-    auto Added = addPass<TwoAddressRewritePass>(Pipeline, instrInfo());
+    auto Added = addPass<TwoAddressInstructionPass>(Pipeline, instrInfo());
     if (!Added)
       return std::unexpected(Added.error());
   }