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

#include "rcc/CodeGen/MachineIRBuilder.h"

#include "rcc/CodeGen/GenericOpcodes.h"
#include "rcc/CodeGen/MachineBasicBlock.h"
#include "rcc/CodeGen/MachineFrameInfo.h"
#include "rcc/CodeGen/MachineFunction.h"
#include "rcc/CodeGen/MachineInstr.h"
#include "rcc/CodeGen/MachineMemOperand.h"
#include "rcc/CodeGen/MachineRegisterInfo.h"

#include <algorithm>
#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <memory>
#include <optional>
#include <string>
#include <utility>
#include <vector>

namespace rcc {

Register MachineIRBuilderResult::reg() const noexcept {
  assert(ResultKind == Kind::Register && "machine IR builder result is not a register");
  return Reg;
}

LowLevelType MachineIRBuilderResult::type() const noexcept {
  assert(ResultKind == Kind::Type && "machine IR builder result is not a type");
  return Type;
}

Expected<LowLevelType> MachineIRBuilderResult::type(const MachineRegisterInfo &MRI) const {
  if (ResultKind == Kind::Type)
    return Type;
  return MRI.getType(Reg);
}

Expected<void> MachineIRBuilderResult::addDef(MachineRegisterInfo &MRI,
                                              MachineInstrBuilder &Builder) const {
  Register Definition = Reg;
  if (ResultKind == Kind::Type) {
    auto Created = MRI.createVirtualRegister(Type);
    if (!Created)
      return std::unexpected(Created.error());
    Definition = *Created;
  }
  return Builder.addDef(Definition);
}

MachineInstrBuilder::MachineInstrBuilder(MachineFunction &Function, const TargetDescription &Target,
                                         const InstructionDescriptor &Descriptor,
                                         MachineBasicBlock &InsertBlock,
                                         MachineInstr *InsertBefore) noexcept
    : Function(&Function), Target(&Target), Descriptor(&Descriptor), InsertBlock(&InsertBlock),
      InsertBefore(InsertBefore) {}

MachineInstrBuilder::MachineInstrBuilder(MachineInstrBuilder &&Other) noexcept
    : Function(Other.Function), Target(Other.Target), Descriptor(Other.Descriptor),
      InsertBlock(Other.InsertBlock), InsertBefore(Other.InsertBefore),
      ExplicitOperands(std::move(Other.ExplicitOperands)),
      ExtraImplicitOperands(std::move(Other.ExtraImplicitOperands)),
      RequestedTies(std::move(Other.RequestedTies)), MemOperands(std::move(Other.MemOperands)),
      Flags(Other.Flags), Location(std::move(Other.Location)),
      DebugLocation(std::move(Other.DebugLocation)), Origin(Other.Origin), IsBuilt(Other.IsBuilt) {
  Other.Function = nullptr;
  Other.Target = nullptr;
  Other.Descriptor = nullptr;
  Other.InsertBlock = nullptr;
  Other.InsertBefore = nullptr;
  Other.IsBuilt = true;
}

MachineInstrBuilder &MachineInstrBuilder::operator=(MachineInstrBuilder &&Other) noexcept {
  if (this == &Other)
    return *this;

  Function = Other.Function;
  Target = Other.Target;
  Descriptor = Other.Descriptor;
  InsertBlock = Other.InsertBlock;
  InsertBefore = Other.InsertBefore;
  ExplicitOperands = std::move(Other.ExplicitOperands);
  ExtraImplicitOperands = std::move(Other.ExtraImplicitOperands);
  RequestedTies = std::move(Other.RequestedTies);
  MemOperands = std::move(Other.MemOperands);
  Flags = Other.Flags;
  Location = std::move(Other.Location);
  DebugLocation = std::move(Other.DebugLocation);
  Origin = Other.Origin;
  IsBuilt = Other.IsBuilt;

  Other.Function = nullptr;
  Other.Target = nullptr;
  Other.Descriptor = nullptr;
  Other.InsertBlock = nullptr;
  Other.InsertBefore = nullptr;
  Other.IsBuilt = true;
  return *this;
}

Expected<void> MachineInstrBuilder::ensurePending() const {
  if (IsBuilt) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "machine instruction builder was already consumed");
  }
  return {};
}

Expected<void> MachineInstrBuilder::addOperand(MachineOperand &&Operand) {
  auto Pending = ensurePending();
  if (!Pending)
    return std::unexpected(Pending.error());
  if (Operand.parent() != nullptr) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder operand already belongs to an instruction");
  }
  if (Operand.isImplicit()) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "implicit register requires addImplicitOperand");
  }
  ExplicitOperands.push_back(std::move(Operand));
  return {};
}

Expected<void> MachineInstrBuilder::addImplicitOperand(MachineOperand &&Operand) {
  auto Pending = ensurePending();
  if (!Pending)
    return std::unexpected(Pending.error());
  if (Operand.parent() != nullptr) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder operand already belongs to an instruction");
  }
  if (!Operand.isRegister() || !Operand.isImplicit()) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "dynamic implicit operand must be an implicit register");
  }
  ExtraImplicitOperands.push_back(std::move(Operand));
  return {};
}

Expected<void> MachineInstrBuilder::appendRegister(Register Reg, RegisterOperandFlags RegisterFlags,
                                                   SubRegIndex SubReg, std::uint32_t TargetFlags,
                                                   bool IsImplicit) {
  auto Operand = MachineOperand::registerOperand(Reg, RegisterFlags, SubReg, TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  if (IsImplicit)
    return addImplicitOperand(std::move(*Operand));
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addDef(Register Reg, RegisterOperandFlags AdditionalFlags,
                                           SubRegIndex SubReg, std::uint32_t TargetFlags) {
  AdditionalFlags.set(RegisterOperandFlag::Define);
  return appendRegister(Reg, AdditionalFlags, SubReg, TargetFlags, false);
}

Expected<void> MachineInstrBuilder::addUse(Register Reg, RegisterOperandFlags AdditionalFlags,
                                           SubRegIndex SubReg, std::uint32_t TargetFlags) {
  AdditionalFlags.set(RegisterOperandFlag::Use);
  return appendRegister(Reg, AdditionalFlags, SubReg, TargetFlags, false);
}

Expected<void> MachineInstrBuilder::addDefUse(Register Reg, RegisterOperandFlags AdditionalFlags,
                                              SubRegIndex SubReg, std::uint32_t TargetFlags) {
  AdditionalFlags.set(RegisterOperandFlag::Define);
  AdditionalFlags.set(RegisterOperandFlag::Use);
  AdditionalFlags.set(RegisterOperandFlag::InternalRead);
  return appendRegister(Reg, AdditionalFlags, SubReg, TargetFlags, false);
}

Expected<void> MachineInstrBuilder::addImplicitDef(Register Reg,
                                                   RegisterOperandFlags AdditionalFlags,
                                                   SubRegIndex SubReg, std::uint32_t TargetFlags) {
  AdditionalFlags.set(RegisterOperandFlag::Define);
  AdditionalFlags.set(RegisterOperandFlag::Implicit);
  return appendRegister(Reg, AdditionalFlags, SubReg, TargetFlags, true);
}

Expected<void> MachineInstrBuilder::addImplicitUse(Register Reg,
                                                   RegisterOperandFlags AdditionalFlags,
                                                   SubRegIndex SubReg, std::uint32_t TargetFlags) {
  AdditionalFlags.set(RegisterOperandFlag::Use);
  AdditionalFlags.set(RegisterOperandFlag::Implicit);
  return appendRegister(Reg, AdditionalFlags, SubReg, TargetFlags, true);
}

Expected<void> MachineInstrBuilder::addImmediate(std::int64_t Value, std::uint32_t TargetFlags) {
  return addOperand(MachineOperand::immediate(Value, TargetFlags));
}

Expected<void> MachineInstrBuilder::addIntegerImmediate(APInt Value, std::uint32_t TargetFlags) {
  return addOperand(MachineOperand::integerImmediate(std::move(Value), TargetFlags));
}

Expected<void> MachineInstrBuilder::addFloatingImmediate(APFloat Bits, std::uint32_t TargetFlags) {
  return addOperand(MachineOperand::floatingImmediate(Bits, TargetFlags));
}

Expected<void> MachineInstrBuilder::addBasicBlock(MachineBasicBlock &Block,
                                                  std::uint32_t TargetFlags) {
  return addOperand(MachineOperand::basicBlock(Block, TargetFlags));
}

Expected<void> MachineInstrBuilder::addFrameIndex(FrameIndex Index, std::int64_t Offset,
                                                  std::uint32_t TargetFlags) {
  return addOperand(MachineOperand::frameIndex(Index, Offset, TargetFlags));
}

Expected<void> MachineInstrBuilder::addConstantPool(ConstantPoolIndex Index, std::int64_t Offset,
                                                    std::uint32_t TargetFlags) {
  return addOperand(MachineOperand::constantPool(Index, Offset, TargetFlags));
}

Expected<void> MachineInstrBuilder::addJumpTable(JumpTableIndex Index, std::uint32_t TargetFlags) {
  return addOperand(MachineOperand::jumpTable(Index, TargetFlags));
}

Expected<void> MachineInstrBuilder::addGlobalSymbol(std::string Name, std::int64_t Offset,
                                                    std::uint32_t TargetFlags) {
  auto Operand = MachineOperand::globalSymbol(std::move(Name), Offset, TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addExternalSymbol(std::string Name, std::int64_t Offset,
                                                      std::uint32_t TargetFlags) {
  auto Operand = MachineOperand::externalSymbol(std::move(Name), Offset, TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addBlockAddress(std::string FunctionName, std::string BlockName,
                                                    std::int64_t Offset,
                                                    std::uint32_t TargetFlags) {
  auto Operand = MachineOperand::blockAddress(std::move(FunctionName), std::move(BlockName), Offset,
                                              TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addRegisterMask(std::shared_ptr<const RegisterMask> Mask,
                                                    std::uint32_t TargetFlags) {
  auto Operand = MachineOperand::registerMask(std::move(Mask), TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addLiveOutRegisterMask(std::shared_ptr<const RegisterMask> Mask,
                                                           std::uint32_t TargetFlags) {
  auto Operand = MachineOperand::liveOutRegisterMask(std::move(Mask), TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addMetadata(MachineMetadataValue Value,
                                                std::uint32_t TargetFlags) {
  auto Operand = MachineOperand::metadata(std::move(Value), TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addTargetIndex(TargetIndex Index, std::int64_t Offset,
                                                   std::uint32_t TargetFlags) {
  return addOperand(MachineOperand::targetIndex(Index, Offset, TargetFlags));
}

Expected<void> MachineInstrBuilder::addMCSymbol(std::string Name, std::int64_t Offset,
                                                std::uint32_t TargetFlags) {
  auto Operand = MachineOperand::mcSymbol(std::move(Name), Offset, TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addCFIInstruction(CFIInstructionIndex Index,
                                                      std::uint32_t TargetFlags) {
  return addOperand(MachineOperand::cfiIndex(Index, TargetFlags));
}

Expected<void> MachineInstrBuilder::addIntrinsic(IntrinsicID ID, std::uint32_t TargetFlags) {
  auto Operand = MachineOperand::intrinsic(ID, TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addIntegerPredicate(IntegerPredicate Predicate,
                                                        std::uint32_t TargetFlags) {
  auto Operand = MachineOperand::integerPredicate(Predicate, TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addFloatingPredicate(FloatingPredicate Predicate,
                                                         std::uint32_t TargetFlags) {
  auto Operand = MachineOperand::floatingPredicate(Predicate, TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addShuffleMask(std::vector<std::int32_t> Elements,
                                                   std::uint32_t TargetFlags) {
  auto Operand = MachineOperand::shuffleMask(std::move(Elements), TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addDebugInstrRef(std::uint64_t InstructionNumber,
                                                     std::uint64_t OperandNumber,
                                                     std::uint32_t TargetFlags) {
  auto Operand = MachineOperand::debugInstrRef(InstructionNumber, OperandNumber, TargetFlags);
  if (!Operand)
    return std::unexpected(Operand.error());
  return addOperand(std::move(*Operand));
}

Expected<void> MachineInstrBuilder::addLaneMask(LaneMask Mask, std::uint32_t TargetFlags) {
  return addOperand(MachineOperand::laneMask(Mask, TargetFlags));
}

Expected<void> MachineInstrBuilder::tieOperands(std::size_t DefOperand, std::size_t UseOperand) {
  auto Pending = ensurePending();
  if (!Pending)
    return std::unexpected(Pending.error());
  if (DefOperand >= ExplicitOperands.size() || UseOperand >= ExplicitOperands.size() ||
      DefOperand == UseOperand) {
    return makeUnexpected(ErrorCode::InvalidArgument, "builder operand tie indices are invalid");
  }

  const MachineOperand &Def = ExplicitOperands[DefOperand];
  const MachineOperand &Use = ExplicitOperands[UseOperand];
  if (!Def.isRegister() || !Use.isRegister() || !Def.isDef() || Def.isUse() || !Use.isUse() ||
      Use.isDef()) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder tie must connect a pure register def and use");
  }

  const MachineOperandTie Tie{DefOperand, UseOperand};
  if (std::ranges::find(RequestedTies, Tie) == RequestedTies.end())
    RequestedTies.push_back(Tie);
  return {};
}

Expected<void> MachineInstrBuilder::addMemOperand(const MachineMemOperand &MemOperand) {
  auto Pending = ensurePending();
  if (!Pending)
    return std::unexpected(Pending.error());
  if (!Function->ownsMemOperand(MemOperand)) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder memory operand belongs to another function");
  }
  MemOperands.push_back(&MemOperand);
  return {};
}

Expected<void> MachineInstrBuilder::setFlags(MachineInstrFlags NewFlags) {
  auto Pending = ensurePending();
  if (!Pending)
    return std::unexpected(Pending.error());
  Flags = NewFlags;
  return {};
}

Expected<void> MachineInstrBuilder::setSourceLocation(SourceLocation NewLocation) {
  auto Pending = ensurePending();
  if (!Pending)
    return std::unexpected(Pending.error());
  if (!NewLocation.isValid()) {
    return makeUnexpected(ErrorCode::InvalidArgument, "builder source location is incomplete");
  }
  Location = std::move(NewLocation);
  return {};
}

Expected<void> MachineInstrBuilder::clearSourceLocation() {
  auto Pending = ensurePending();
  if (!Pending)
    return std::unexpected(Pending.error());
  Location.reset();
  return {};
}

Expected<void> MachineInstrBuilder::setDebugLocation(MachineDebugLocation NewLocation) {
  auto Pending = ensurePending();
  if (!Pending)
    return std::unexpected(Pending.error());
  if (!NewLocation.isValid()) {
    return makeUnexpected(ErrorCode::InvalidArgument, "builder debug location is invalid");
  }
  DebugLocation = std::move(NewLocation);
  return {};
}

Expected<void> MachineInstrBuilder::clearDebugLocation() {
  auto Pending = ensurePending();
  if (!Pending)
    return std::unexpected(Pending.error());
  DebugLocation.reset();
  return {};
}

Expected<void> MachineInstrBuilder::setOrigin(OriginID NewOrigin) {
  auto Pending = ensurePending();
  if (!Pending)
    return std::unexpected(Pending.error());
  if (NewOrigin.value() == 0) {
    return makeUnexpected(ErrorCode::InvalidArgument, "builder origin ID must be nonzero");
  }
  Origin = NewOrigin;
  return {};
}

Expected<void> MachineInstrBuilder::clearOrigin() {
  auto Pending = ensurePending();
  if (!Pending)
    return std::unexpected(Pending.error());
  Origin.reset();
  return {};
}

Expected<void> MachineInstrBuilder::validateInsertionPoint() const {
  if (InsertBlock == nullptr || &InsertBlock->function() != Function || !InsertBlock->isLinked()) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder insertion block is not linked to its function");
  }
  if (InsertBefore != nullptr && InsertBefore->parent() != InsertBlock) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder insertion cursor is no longer in its block");
  }
  return {};
}

Expected<void> MachineInstrBuilder::validateFrameReference(FrameIndex Index) const {
  const StackObject *Object = Function->frameInfo().object(Index);
  if (Object == nullptr || Object->description()->IsDead) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder references an unknown or dead stack object");
  }
  return {};
}

Expected<void> MachineInstrBuilder::validateConstantPoolReference(ConstantPoolIndex Index) const {
  if (Function->constantPool().entry(Index) == nullptr) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder references an unknown constant pool entry");
  }
  return {};
}

Expected<void> MachineInstrBuilder::validateJumpTableReference(JumpTableIndex Index) const {
  if (Function->jumpTableInfo().table(Index) == nullptr) {
    return makeUnexpected(ErrorCode::InvalidArgument, "builder references an unknown jump table");
  }
  return {};
}

Expected<void> MachineInstrBuilder::validateCFIReference(CFIInstructionIndex Index) const {
  if (Function->cfiInfo().instruction(Index) == nullptr) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder references an unknown CFI instruction");
  }
  return {};
}

Expected<void> MachineInstrBuilder::validateOperandOwnership(const MachineOperand &Operand) const {
  if (Operand.parent() != nullptr) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder operand already belongs to an instruction");
  }
  if (const auto *Block = Operand.getIf<BasicBlockOperand>();
      Block != nullptr && (Block->Block == nullptr || &Block->Block->function() != Function ||
                           !Block->Block->isLinked())) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder basic block operand is not linked to its function");
  }
  if (const Register *Reg = Operand.getIf<Register>();
      Reg != nullptr && Reg->isVirtual() &&
      !Function->registerInfo().isKnownVirtualRegister(*Reg)) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder operand references an unknown virtual register");
  }
  if (const auto *Frame = Operand.getIf<FrameIndexOperand>(); Frame != nullptr) {
    auto FrameResult = validateFrameReference(Frame->Index);
    if (!FrameResult)
      return FrameResult;
  }
  if (const auto *Constant = Operand.getIf<ConstantPoolOperand>(); Constant != nullptr) {
    auto ConstantResult = validateConstantPoolReference(Constant->Index);
    if (!ConstantResult)
      return ConstantResult;
  }
  if (const auto *JumpTable = Operand.getIf<JumpTableOperand>(); JumpTable != nullptr) {
    auto JumpTableResult = validateJumpTableReference(JumpTable->Index);
    if (!JumpTableResult)
      return JumpTableResult;
  }
  if (const auto *CFI = Operand.getIf<CFIIndexOperand>(); CFI != nullptr) {
    auto CFIResult = validateCFIReference(CFI->Index);
    if (!CFIResult)
      return CFIResult;
  }
  return {};
}

std::vector<MachineOperandTie> MachineInstrBuilder::collectOperandTies() const {
  std::vector<MachineOperandTie> Result;
  for (std::size_t Index = 0; Index < Descriptor->Operands.size(); ++Index) {
    const OperandDescriptor &Operand = Descriptor->Operands[Index];
    if (!Operand.DefaultTiedOperand || Index > *Operand.DefaultTiedOperand)
      continue;
    const std::size_t Other = *Operand.DefaultTiedOperand;
    const bool IndexIsDef = Operand.RegisterRole == RegisterOperandRole::Def;
    Result.push_back(IndexIsDef ? MachineOperandTie{Index, Other}
                                : MachineOperandTie{Other, Index});
  }
  for (const MachineOperandTie Tie : RequestedTies) {
    if (std::ranges::find(Result, Tie) == Result.end())
      Result.push_back(Tie);
  }
  return Result;
}

Expected<MachineInstr *> MachineInstrBuilder::build() {
  auto Pending = ensurePending();
  if (!Pending)
    return std::unexpected(Pending.error());

  auto InsertionValidation = validateInsertionPoint();
  if (!InsertionValidation)
    return std::unexpected(InsertionValidation.error());

  for (const MachineOperand &Operand : ExplicitOperands) {
    auto Ownership = validateOperandOwnership(Operand);
    if (!Ownership)
      return std::unexpected(Ownership.error());
  }
  for (const MachineOperand &Operand : ExtraImplicitOperands) {
    auto Ownership = validateOperandOwnership(Operand);
    if (!Ownership)
      return std::unexpected(Ownership.error());
  }
  for (const MachineMemOperand *MemOperand : MemOperands) {
    const MemoryBase &Base = MemOperand->description().Base;
    if (const auto Frame = Base.frameIndex()) {
      auto FrameResult = validateFrameReference(*Frame);
      if (!FrameResult)
        return std::unexpected(FrameResult.error());
    }
    if (const auto Constant = Base.constantPoolIndex()) {
      auto ConstantResult = validateConstantPoolReference(*Constant);
      if (!ConstantResult)
        return std::unexpected(ConstantResult.error());
    }
    if (const auto JumpTable = Base.jumpTableIndex()) {
      auto JumpTableResult = validateJumpTableReference(*JumpTable);
      if (!JumpTableResult)
        return std::unexpected(JumpTableResult.error());
    }
  }

  auto ExplicitValidation = Target->validateExplicitOperands(
      Descriptor->InstructionOpcode, ExplicitOperands, Function->registerInfo());
  if (!ExplicitValidation)
    return std::unexpected(ExplicitValidation.error());

  auto DefaultImplicit = Target->createDefaultImplicitOperands(*Descriptor);
  if (!DefaultImplicit)
    return std::unexpected(DefaultImplicit.error());

  std::vector<const MachineOperand *> ImplicitOperands;
  ImplicitOperands.reserve(DefaultImplicit->size() + ExtraImplicitOperands.size());
  for (const MachineOperand &Operand : *DefaultImplicit)
    ImplicitOperands.push_back(&Operand);
  for (const MachineOperand &Operand : ExtraImplicitOperands)
    ImplicitOperands.push_back(&Operand);
  auto ImplicitValidation = Target->validateImplicitOperands(
      Descriptor->InstructionOpcode, ImplicitOperands, Function->registerInfo());
  if (!ImplicitValidation)
    return std::unexpected(ImplicitValidation.error());

  const std::vector<MachineOperandTie> Ties = collectOperandTies();
  auto TieValidation = Target->validateOperandTies(Descriptor->InstructionOpcode, ExplicitOperands,
                                                   Ties, Function->registerInfo());
  if (!TieValidation)
    return std::unexpected(TieValidation.error());

  auto EarlyClobberValidation =
      Target->validateEarlyClobber(ExplicitOperands, ImplicitOperands, Ties);
  if (!EarlyClobberValidation)
    return std::unexpected(EarlyClobberValidation.error());

  auto MemoryValidation = Target->validateMemOperands(Descriptor->InstructionOpcode, MemOperands);
  if (!MemoryValidation)
    return std::unexpected(MemoryValidation.error());

  auto Instruction = Function->createInstruction(Descriptor->InstructionOpcode);
  if (!Instruction)
    return std::unexpected(Instruction.error());
  MachineInstr *Result = *Instruction;
  Result->reserveOperands(ExplicitOperands.size() + DefaultImplicit->size() +
                          ExtraImplicitOperands.size());

  for (MachineOperand &Operand : ExplicitOperands) {
    auto AddResult = Result->addOperand(std::move(Operand));
    if (!AddResult)
      return std::unexpected(AddResult.error());
  }
  for (MachineOperand &Operand : *DefaultImplicit) {
    auto AddResult = Result->addOperand(std::move(Operand));
    if (!AddResult)
      return std::unexpected(AddResult.error());
  }
  for (MachineOperand &Operand : ExtraImplicitOperands) {
    auto AddResult = Result->addOperand(std::move(Operand));
    if (!AddResult)
      return std::unexpected(AddResult.error());
  }
  for (const MachineOperandTie Tie : Ties) {
    auto TieResult = Result->tieOperands(Tie.DefOperand, Tie.UseOperand);
    if (!TieResult)
      return std::unexpected(TieResult.error());
  }
  for (const MachineMemOperand *MemOperand : MemOperands) {
    auto AddResult = Result->addMemOperand(*MemOperand);
    if (!AddResult)
      return std::unexpected(AddResult.error());
  }

  Result->setFlags(Flags);
  if (Location)
    Result->setSourceLocation(std::move(*Location));
  if (DebugLocation) {
    auto DebugLocationResult = Result->setDebugLocation(std::move(*DebugLocation));
    if (!DebugLocationResult)
      return std::unexpected(DebugLocationResult.error());
  }
  if (Origin)
    Result->setOrigin(*Origin);

  Expected<void> InsertResult;
  if (InsertBefore == nullptr)
    InsertResult = InsertBlock->appendInstruction(*Result);
  else
    InsertResult = InsertBlock->insertInstructionBefore(*InsertBefore, *Result);
  if (!InsertResult)
    return std::unexpected(InsertResult.error());

  IsBuilt = true;
  return Result;
}

Expected<void> MachineIRBuilder::validateBlock(const MachineBasicBlock &Block) const {
  if (&Block.function() != Function || !Block.isLinked()) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder insertion block is not linked to its function");
  }
  return {};
}

Expected<void> MachineIRBuilder::validateInstruction(const MachineInstr &Instruction) const {
  if (&Instruction.function() != Function || Instruction.parent() == nullptr) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "builder insertion instruction is not linked to its function");
  }
  return {};
}

Expected<void> MachineIRBuilder::verifyInsertPoint() const {
  if (InsertBlock == nullptr)
    return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point");
  auto BlockValidation = validateBlock(*InsertBlock);
  if (!BlockValidation)
    return std::unexpected(BlockValidation.error());
  if (InsertBefore != nullptr && InsertBefore->parent() != InsertBlock) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "machine IR builder insertion cursor is no longer in its block");
  }
  return {};
}

Expected<void> MachineIRBuilder::setInsertPoint(MachineBasicBlock &Block) {
  auto Validation = validateBlock(Block);
  if (!Validation)
    return std::unexpected(Validation.error());
  InsertBlock = &Block;
  InsertBefore = nullptr;
  return {};
}

Expected<void> MachineIRBuilder::setInsertPointBefore(MachineInstr &Instruction) {
  auto Validation = validateInstruction(Instruction);
  if (!Validation)
    return std::unexpected(Validation.error());
  InsertBlock = Instruction.parent();
  InsertBefore = &Instruction;
  return {};
}

Expected<void> MachineIRBuilder::setInsertPointAfter(MachineInstr &Instruction) {
  auto Validation = validateInstruction(Instruction);
  if (!Validation)
    return std::unexpected(Validation.error());
  InsertBlock = Instruction.parent();
  InsertBefore = Instruction.next();
  return {};
}

Expected<MachineInstrBuilder> MachineIRBuilder::buildInstr(Opcode InstructionOpcode) const {
  if (InsertBlock == nullptr) {
    return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point");
  }
  const InstructionDescriptor *Descriptor = Target->instructionDescriptor(InstructionOpcode);
  if (Descriptor == nullptr) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "machine IR builder opcode is not registered");
  }
  auto BlockValidation = validateBlock(*InsertBlock);
  if (!BlockValidation)
    return std::unexpected(BlockValidation.error());
  if (InsertBefore != nullptr && InsertBefore->parent() != InsertBlock) {
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "machine IR builder insertion cursor is stale");
  }
  return MachineInstrBuilder(*Function, *Target, *Descriptor, *InsertBlock, InsertBefore);
}

Expected<MachineInstr *>
MachineIRBuilder::buildInstr(Opcode InstructionOpcode,
                             std::initializer_list<MachineIRBuilderResult> Destinations,
                             std::initializer_list<Register> Sources) const {
  return buildInstr(
      InstructionOpcode,
      std::span<const MachineIRBuilderResult>(Destinations.begin(), Destinations.size()),
      std::span<const Register>(Sources.begin(), Sources.size()));
}

Expected<MachineInstr *>
MachineIRBuilder::buildInstr(Opcode InstructionOpcode,
                             std::span<const MachineIRBuilderResult> Destinations,
                             std::span<const Register> Sources) const {
  auto Pending = buildInstr(InstructionOpcode);
  if (!Pending)
    return std::unexpected(Pending.error());
  for (const MachineIRBuilderResult &Destination : Destinations) {
    if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added)
      return std::unexpected(Added.error());
  }
  for (Register Source : Sources) {
    if (auto Added = Pending->addUse(Source); !Added)
      return std::unexpected(Added.error());
  }
  return Pending->build();
}

Expected<LowLevelType> MachineIRBuilder::registerType(Register Reg) const {
  if (!Reg.isVirtual())
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "generic builder operand is not a virtual register");
  auto Info = Function->registerInfo().virtualRegisterInfo(Reg);
  if (!Info)
    return std::unexpected(Info.error());
  const std::optional<LowLevelType> &Type = Info->get().Type;
  if (!Type.has_value())
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "generic builder operand has no LowLevelType");
  return Type.value();
}

Expected<MachineInstr *> MachineIRBuilder::buildUnary(Opcode InstructionOpcode,
                                                      MachineIRBuilderResult Destination,
                                                      Register Source) const {
  const std::array Destinations{Destination};
  const std::array Sources{Source};
  return buildInstr(InstructionOpcode, std::span<const MachineIRBuilderResult>(Destinations),
                    std::span<const Register>(Sources));
}

Expected<MachineInstr *> MachineIRBuilder::buildBinary(Opcode InstructionOpcode,
                                                       MachineIRBuilderResult Destination,
                                                       Register Left, Register Right) const {
  const std::array Destinations{Destination};
  const std::array Sources{Left, Right};
  return buildInstr(InstructionOpcode, std::span<const MachineIRBuilderResult>(Destinations),
                    std::span<const Register>(Sources));
}

Expected<MachineInstr *> MachineIRBuilder::buildTrunc(MachineIRBuilderResult Destination,
                                                      Register Source) const {
  return buildUnary(opcode(GenericOpcode::G_TRUNC), Destination, Source);
}

Expected<MachineInstr *> MachineIRBuilder::buildCopy(MachineIRBuilderResult Destination,
                                                     Register Source) const {
  return buildUnary(opcode(GenericOpcode::COPY), Destination, Source);
}

Expected<MachineInstr *>
MachineIRBuilder::buildImplicitDef(MachineIRBuilderResult Destination) const {
  const std::array Destinations{Destination};
  return buildInstr(opcode(GenericOpcode::G_IMPLICIT_DEF),
                    std::span<const MachineIRBuilderResult>(Destinations),
                    std::span<const Register>());
}

Expected<MachineInstr *> MachineIRBuilder::buildAnyExt(MachineIRBuilderResult Destination,
                                                       Register Source) const {
  return buildUnary(opcode(GenericOpcode::G_ANYEXT), Destination, Source);
}

Expected<MachineInstr *> MachineIRBuilder::buildZExt(MachineIRBuilderResult Destination,
                                                     Register Source) const {
  return buildUnary(opcode(GenericOpcode::G_ZEXT), Destination, Source);
}

Expected<MachineInstr *> MachineIRBuilder::buildSExt(MachineIRBuilderResult Destination,
                                                     Register Source) const {
  return buildUnary(opcode(GenericOpcode::G_SEXT), Destination, Source);
}

GenericOpcode MachineIRBuilder::getBoolExtOp(bool IsVector, bool IsFloatingPoint) const noexcept {
  switch (Target->getBooleanContents(IsVector, IsFloatingPoint)) {
  case BooleanContent::ZeroOrNegativeOne:
    return GenericOpcode::G_SEXT;
  case BooleanContent::ZeroOrOne:
    return GenericOpcode::G_ZEXT;
  case BooleanContent::Undefined:
    return GenericOpcode::G_ANYEXT;
  }
  return GenericOpcode::G_ANYEXT;
}

Expected<MachineInstr *> MachineIRBuilder::buildUndef(MachineIRBuilderResult Destination) const {
  return buildImplicitDef(Destination);
}

Expected<MachineInstr *> MachineIRBuilder::buildExtOrTrunc(Opcode ExtensionOpcode,
                                                           MachineIRBuilderResult Destination,
                                                           Register Source) const {
  auto DestinationType = Destination.type(Function->registerInfo());
  if (!DestinationType)
    return std::unexpected(DestinationType.error());
  auto SourceType = registerType(Source);
  if (!SourceType)
    return std::unexpected(SourceType.error());
  const std::uint64_t DestinationWidth = DestinationType->minimumBitWidth();
  const std::uint64_t SourceWidth = SourceType->minimumBitWidth();
  if (DestinationWidth > SourceWidth)
    return buildUnary(ExtensionOpcode, Destination, Source);
  if (DestinationWidth < SourceWidth)
    return buildTrunc(Destination, Source);
  return buildUnary(opcode(GenericOpcode::COPY), Destination, Source);
}

Expected<MachineInstr *> MachineIRBuilder::buildAnyExtOrTrunc(MachineIRBuilderResult Destination,
                                                              Register Source) const {
  return buildExtOrTrunc(opcode(GenericOpcode::G_ANYEXT), Destination, Source);
}

Expected<MachineInstr *> MachineIRBuilder::buildZExtOrTrunc(MachineIRBuilderResult Destination,
                                                            Register Source) const {
  return buildExtOrTrunc(opcode(GenericOpcode::G_ZEXT), Destination, Source);
}

Expected<MachineInstr *> MachineIRBuilder::buildSExtOrTrunc(MachineIRBuilderResult Destination,
                                                            Register Source) const {
  return buildExtOrTrunc(opcode(GenericOpcode::G_SEXT), Destination, Source);
}

Expected<MachineInstr *> MachineIRBuilder::buildConstant(MachineIRBuilderResult Destination,
                                                         APInt Value) const {
  auto Pending = buildInstr(opcode(GenericOpcode::G_CONSTANT));
  if (!Pending)
    return std::unexpected(Pending.error());
  if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added)
    return std::unexpected(Added.error());
  if (auto Added = Pending->addIntegerImmediate(std::move(Value)); !Added)
    return std::unexpected(Added.error());
  return Pending->build();
}

Expected<MachineInstr *> MachineIRBuilder::buildConstant(MachineIRBuilderResult Destination,
                                                         std::int64_t Value) const {
  auto Type = Destination.type(Function->registerInfo());
  if (!Type)
    return std::unexpected(Type.error());
  auto Immediate = APInt::fromSigned(Type->scalarBitWidth(), Value);
  if (!Immediate)
    return std::unexpected(Immediate.error());
  return buildConstant(Destination, std::move(*Immediate));
}

Expected<MachineInstr *> MachineIRBuilder::buildSExtInReg(MachineIRBuilderResult Destination,
                                                          Register Source,
                                                          std::uint32_t Width) const {
  auto Pending = buildInstr(opcode(GenericOpcode::G_SEXT_INREG));
  if (!Pending)
    return std::unexpected(Pending.error());
  if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added)
    return std::unexpected(Added.error());
  if (auto Added = Pending->addUse(Source); !Added)
    return std::unexpected(Added.error());
  if (auto Added = Pending->addImmediate(static_cast<std::int64_t>(Width)); !Added)
    return std::unexpected(Added.error());
  return Pending->build();
}

Expected<MachineInstr *> MachineIRBuilder::buildAnd(MachineIRBuilderResult Destination,
                                                    Register Left, Register Right) const {
  return buildBinary(opcode(GenericOpcode::G_AND), Destination, Left, Right);
}

Expected<MachineInstr *> MachineIRBuilder::buildOr(MachineIRBuilderResult Destination,
                                                   Register Left, Register Right) const {
  return buildBinary(opcode(GenericOpcode::G_OR), Destination, Left, Right);
}

Expected<MachineInstr *> MachineIRBuilder::buildXor(MachineIRBuilderResult Destination,
                                                    Register Left, Register Right) const {
  return buildBinary(opcode(GenericOpcode::G_XOR), Destination, Left, Right);
}

Expected<MachineInstr *> MachineIRBuilder::buildAdd(MachineIRBuilderResult Destination,
                                                    Register Left, Register Right) const {
  return buildBinary(opcode(GenericOpcode::G_ADD), Destination, Left, Right);
}

Expected<MachineInstr *> MachineIRBuilder::buildSub(MachineIRBuilderResult Destination,
                                                    Register Left, Register Right) const {
  return buildBinary(opcode(GenericOpcode::G_SUB), Destination, Left, Right);
}

Expected<MachineInstr *> MachineIRBuilder::buildShl(MachineIRBuilderResult Destination,
                                                    Register Left, Register Right) const {
  return buildBinary(opcode(GenericOpcode::G_SHL), Destination, Left, Right);
}

Expected<MachineInstr *> MachineIRBuilder::buildLShr(MachineIRBuilderResult Destination,
                                                     Register Left, Register Right) const {
  return buildBinary(opcode(GenericOpcode::G_LSHR), Destination, Left, Right);
}

Expected<MachineInstr *> MachineIRBuilder::buildAShr(MachineIRBuilderResult Destination,
                                                     Register Left, Register Right) const {
  return buildBinary(opcode(GenericOpcode::G_ASHR), Destination, Left, Right);
}

Expected<MachineInstr *> MachineIRBuilder::buildPtrToInt(MachineIRBuilderResult Destination,
                                                         Register Source) const {
  return buildUnary(opcode(GenericOpcode::G_PTRTOINT), Destination, Source);
}

Expected<MachineInstr *> MachineIRBuilder::buildIntToPtr(MachineIRBuilderResult Destination,
                                                         Register Source) const {
  return buildUnary(opcode(GenericOpcode::G_INTTOPTR), Destination, Source);
}

Expected<MachineInstr *> MachineIRBuilder::buildICmp(IntegerPredicate Predicate,
                                                     MachineIRBuilderResult Destination,
                                                     Register Left, Register Right) const {
  auto Pending = buildInstr(opcode(GenericOpcode::G_ICMP));
  if (!Pending)
    return std::unexpected(Pending.error());
  if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added)
    return std::unexpected(Added.error());
  if (auto Added = Pending->addIntegerPredicate(Predicate); !Added)
    return std::unexpected(Added.error());
  if (auto Added = Pending->addUse(Left); !Added)
    return std::unexpected(Added.error());
  if (auto Added = Pending->addUse(Right); !Added)
    return std::unexpected(Added.error());
  return Pending->build();
}

Expected<MachineInstr *>
MachineIRBuilder::buildMergeLikeInstr(MachineIRBuilderResult Destination,
                                      const std::vector<Register> &Sources) const {
  auto DestinationType = Destination.type(Function->registerInfo());
  if (!DestinationType)
    return std::unexpected(DestinationType.error());
  if (!DestinationType->isVector())
    return buildMergeValues(Destination, Sources);
  if (Sources.empty())
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "merge-like instruction requires source registers");
  auto SourceType = registerType(Sources.front());
  if (!SourceType)
    return std::unexpected(SourceType.error());
  const GenericOpcode MergeOpcode =
      SourceType->isVector() ? GenericOpcode::G_CONCAT_VECTORS : GenericOpcode::G_BUILD_VECTOR;
  const std::array Destinations{Destination};
  return buildInstr(opcode(MergeOpcode), std::span<const MachineIRBuilderResult>(Destinations),
                    Sources);
}

Expected<MachineInstr *>
MachineIRBuilder::buildMergeValues(MachineIRBuilderResult Destination,
                                   const std::vector<Register> &Sources) const {
  const std::array Destinations{Destination};
  return buildInstr(opcode(GenericOpcode::G_MERGE_VALUES),
                    std::span<const MachineIRBuilderResult>(Destinations), Sources);
}

Expected<MachineInstr *>
MachineIRBuilder::buildUnmergeValues(const std::vector<Register> &Destinations,
                                     Register Source) const {
  std::vector<MachineIRBuilderResult> Results;
  Results.reserve(Destinations.size());
  for (Register Destination : Destinations)
    Results.emplace_back(Destination);
  const std::array Sources{Source};
  return buildInstr(opcode(GenericOpcode::G_UNMERGE_VALUES), Results,
                    std::span<const Register>(Sources));
}

Expected<MachineInstr *> MachineIRBuilder::buildExtract(MachineIRBuilderResult Destination,
                                                        Register Source,
                                                        std::uint64_t Offset) const {
  if (Offset > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()))
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "generic extract offset does not fit a machine immediate");
  auto Pending = buildInstr(opcode(GenericOpcode::G_EXTRACT));
  if (!Pending)
    return std::unexpected(Pending.error());
  if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added)
    return std::unexpected(Added.error());
  if (auto Added = Pending->addUse(Source); !Added)
    return std::unexpected(Added.error());
  if (auto Added = Pending->addImmediate(static_cast<std::int64_t>(Offset)); !Added)
    return std::unexpected(Added.error());
  return Pending->build();
}

Expected<MachineInstr *> MachineIRBuilder::buildInsert(MachineIRBuilderResult Destination,
                                                       Register Source, Register Inserted,
                                                       std::uint64_t Offset) const {
  if (Offset > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()))
    return makeUnexpected(ErrorCode::InvalidArgument,
                          "generic insert offset does not fit a machine immediate");
  auto Pending = buildInstr(opcode(GenericOpcode::G_INSERT));
  if (!Pending)
    return std::unexpected(Pending.error());
  if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added)
    return std::unexpected(Added.error());
  if (auto Added = Pending->addUse(Source); !Added)
    return std::unexpected(Added.error());
  if (auto Added = Pending->addUse(Inserted); !Added)
    return std::unexpected(Added.error());
  if (auto Added = Pending->addImmediate(static_cast<std::int64_t>(Offset)); !Added)
    return std::unexpected(Added.error());
  return Pending->build();
}

} // namespace rcc