// SPDX-License-Identifier: GPL-3.0-or-later

#include "rcc/CodeGen/TwoAddressInstructionPass.h"

#include "rcc/CodeGen/GenericOpcodes.h"
#include "rcc/CodeGen/LiveVariables.h"
#include "rcc/CodeGen/MachineBasicBlock.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 "rcc/CodeGen/TargetInstrInfo.h"

#include <cstddef>
#include <cstdint>
#include <limits>
#include <optional>
#include <string>
#include <utility>
#include <vector>

namespace rcc {
namespace {

struct RegisterValue final {
  Register Reg;
  SubRegIndex SubReg;
  RegisterOperandFlags Flags;
  std::uint32_t TargetFlags = 0;
};

[[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]] 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<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> repairTrackedLiveness(MachineFunction &Function,
                                                   const TargetDescription &Target,
                                                   MachinePassResult &Result) {
  if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
    return {};
  }
  auto Rebuilt = rebuildMachineLiveness(Function, Target);
  if (!Rebuilt)
    return std::unexpected(Rebuilt.error());
  if (*Rebuilt)
    Result.Changes.add(MachinePassChange::Operands);
  return {};
}

[[nodiscard]] Expected<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 TargetInstrInfo &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 TargetInstrInfo &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 &TwoAddressInstructionPass::contract() const noexcept {
  static const MachinePassContract Contract{
      .Name = "twoaddressinstruction",
      .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs},
      .Sets = {MachineFunctionProperty::TiedOpsRewritten},
      .Clears = {MachineFunctionProperty::IsSSA},
      .RequiredAnalyses = {},
      .VerificationStage = PipelineStage::TiedOpsRewritten,
  };
  return Contract;
}

Expected<MachinePassResult>
TwoAddressInstructionPass::run(MachineFunction &Function, const TargetDescription &Target,
                               MachineFunctionAnalysisManager &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(), "two-address 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(), "two-address rewrite diverged after a successful transaction preflight: "));
  }
  auto Replayed = Actions.finishReplay();
  if (!Replayed)
    return std::unexpected(Replayed.error());
  return Result;
}

Expected<MachinePassResult> TwoAddressInstructionPass::runImplementation(
    MachineFunction &Function, const TargetDescription &Target, MachineActionReplay &Actions) {
  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 Accepted = Actions.request("expand-reg-sequence", Function, Instruction->stableID());
      if (!Accepted)
        return std::unexpected(Accepted.error());
      if (!*Accepted)
        return makeUnexpected(ErrorCode::VerificationError,
                              "required REG_SEQUENCE expansion action was rejected");
      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 Accepted = Actions.request("expand-insert-subreg", Function, Instruction->stableID());
      if (!Accepted)
        return std::unexpected(Accepted.error());
      if (!*Accepted)
        return makeUnexpected(ErrorCode::VerificationError,
                              "required INSERT_SUBREG expansion action was rejected");
      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 Accepted = Actions.request("rewrite-undef-tie", Function, Instruction->stableID());
          if (!Accepted)
            return std::unexpected(Accepted.error());
          if (!*Accepted)
            return makeUnexpected(ErrorCode::VerificationError,
                                  "required undef tie rewrite action was rejected");
          auto Rewritten = rewriteUndefTie(*Use, *Def);
          if (!Rewritten)
            return std::unexpected(Rewritten.error());
          Result.Changed = true;
          Result.Changes.add(MachinePassChange::Operands);
          continue;
        }

        auto AllowCommute =
            Actions.request("commute-tied-operands", Function, Instruction->stableID());
        if (!AllowCommute)
          return std::unexpected(AllowCommute.error());
        if (*AllowCommute) {
          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 AllowConversion =
            Actions.request("convert-three-address", Function, Instruction->stableID());
        if (!AllowConversion)
          return std::unexpected(AllowConversion.error());
        if (*AllowConversion) {
          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;
          }
        }

        auto AllowCopy = Actions.request("insert-tied-copy", Function, Instruction->stableID());
        if (!AllowCopy)
          return std::unexpected(AllowCopy.error());
        if (!*AllowCopy)
          return makeUnexpected(ErrorCode::VerificationError,
                                "required tied COPY insertion action was rejected");
        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 Repaired = repairTrackedLiveness(Function, Target, Result);
    if (!Repaired)
      return std::unexpected(
          prefixedError(Repaired.error(), "two-address liveness repair failed: "));
  }
  Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
  return Result;
}

} // namespace rcc