[CodeGen] Implement machine SSA exit

1 files changed, 1090 insertions, 0 deletions

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