From c759cebef15bdac2ef160065efd116fe6ed540a7 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sat, 1 Aug 2026 05:27:13 +0800 Subject: [CodeGen] Build the core MachineIR object model Add arena-owned, address-stable MachineFunction, MachineBasicBlock, and MachineInstr nodes with intrusive layout and instruction lists. Model every required MachineOperand category, reciprocal ties, source state, and immutable per-instruction memory references. Implement physical and virtual register def-use chains whose back-links survive operand vector moves, plus vreg properties, tombstones, live-ins, reserved registers, and atomic CFG updates. Exercise ownership, reallocation, unlink/relink, cross-function rejection, and sanitizer paths. --- backend/lib/CodeGen/CMakeLists.txt | 24 ++ backend/lib/CodeGen/MachineBasicBlock.cpp | 157 ++++++++++++ backend/lib/CodeGen/MachineCFGUpdater.cpp | 181 ++++++++++++++ backend/lib/CodeGen/MachineFunction.cpp | 205 ++++++++++++++++ backend/lib/CodeGen/MachineInstr.cpp | 199 +++++++++++++++ backend/lib/CodeGen/MachineOperand.cpp | 326 +++++++++++++++++++++++++ backend/lib/CodeGen/MachineRegisterInfo.cpp | 362 ++++++++++++++++++++++++++++ 7 files changed, 1454 insertions(+) create mode 100644 backend/lib/CodeGen/MachineBasicBlock.cpp create mode 100644 backend/lib/CodeGen/MachineCFGUpdater.cpp create mode 100644 backend/lib/CodeGen/MachineFunction.cpp create mode 100644 backend/lib/CodeGen/MachineInstr.cpp create mode 100644 backend/lib/CodeGen/MachineOperand.cpp create mode 100644 backend/lib/CodeGen/MachineRegisterInfo.cpp (limited to 'backend/lib/CodeGen') diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index 8a45878..ffa5e82 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -3,8 +3,14 @@ set( RCCBackendCodeGenSources LowLevelType.cpp + MachineBasicBlock.cpp + MachineCFGUpdater.cpp + MachineFunction.cpp MachineIRTypes.cpp + MachineInstr.cpp MachineMemOperand.cpp + MachineOperand.cpp + MachineRegisterInfo.cpp MachineFunctionProperties.cpp Register.cpp RegisterMask.cpp @@ -12,8 +18,14 @@ set( set( RCCBackendCodeGenHeaders "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineBasicBlock.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineCFGUpdater.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunction.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineIRTypes.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineInstr.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMemOperand.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineOperand.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionProperties.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/Register.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterMask.h" @@ -50,8 +62,14 @@ install( rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineBasicBlock.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineCFGUpdater.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunction.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp" @@ -59,8 +77,14 @@ rcc_backend_register_format_files( ) rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineBasicBlock.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineCFGUpdater.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunction.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp" diff --git a/backend/lib/CodeGen/MachineBasicBlock.cpp b/backend/lib/CodeGen/MachineBasicBlock.cpp new file mode 100644 index 0000000..a8d69f6 --- /dev/null +++ b/backend/lib/CodeGen/MachineBasicBlock.cpp @@ -0,0 +1,157 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineBasicBlock.h" + +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" + +#include +#include + +namespace rcc { + +std::size_t MachineBasicBlock::instructionCount() const noexcept { + std::size_t Count = 0; + for (const MachineInstr *Instruction = FirstInstruction; Instruction != nullptr; + Instruction = Instruction->next()) { + ++Count; + } + return Count; +} + +Expected MachineBasicBlock::appendInstruction(MachineInstr &Instruction) { + if (&Instruction.function() != OwnerFunction) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction belongs to another machine function"); + } + if (Instruction.isLinked()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction is already linked to a basic block"); + } + + auto AttachResult = Instruction.attachToBlock(*this); + if (!AttachResult) + return std::unexpected(AttachResult.error()); + + Instruction.PreviousInstruction = LastInstruction; + Instruction.NextInstruction = nullptr; + if (LastInstruction != nullptr) + LastInstruction->NextInstruction = &Instruction; + else + FirstInstruction = &Instruction; + LastInstruction = &Instruction; + return {}; +} + +Expected MachineBasicBlock::insertInstructionBefore(MachineInstr &Position, + MachineInstr &Instruction) { + if (Position.parent() != this) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction insertion position is not in this block"); + } + if (&Instruction.function() != OwnerFunction || Instruction.isLinked()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "inserted instruction is linked or belongs to another function"); + } + + auto AttachResult = Instruction.attachToBlock(*this); + if (!AttachResult) + return std::unexpected(AttachResult.error()); + + Instruction.PreviousInstruction = Position.PreviousInstruction; + Instruction.NextInstruction = &Position; + if (Position.PreviousInstruction != nullptr) + Position.PreviousInstruction->NextInstruction = &Instruction; + else + FirstInstruction = &Instruction; + Position.PreviousInstruction = &Instruction; + return {}; +} + +Expected MachineBasicBlock::insertInstructionAfter(MachineInstr &Position, + MachineInstr &Instruction) { + if (Position.parent() != this) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction insertion position is not in this block"); + } + if (&Instruction.function() != OwnerFunction || Instruction.isLinked()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "inserted instruction is linked or belongs to another function"); + } + + auto AttachResult = Instruction.attachToBlock(*this); + if (!AttachResult) + return std::unexpected(AttachResult.error()); + + Instruction.PreviousInstruction = &Position; + Instruction.NextInstruction = Position.NextInstruction; + if (Position.NextInstruction != nullptr) + Position.NextInstruction->PreviousInstruction = &Instruction; + else + LastInstruction = &Instruction; + Position.NextInstruction = &Instruction; + return {}; +} + +Expected MachineBasicBlock::removeInstruction(MachineInstr &Instruction) { + if (Instruction.parent() != this) { + return makeUnexpected(ErrorCode::InvalidArgument, "instruction does not belong to this block"); + } + + if (Instruction.PreviousInstruction != nullptr) + Instruction.PreviousInstruction->NextInstruction = Instruction.NextInstruction; + else + FirstInstruction = Instruction.NextInstruction; + + if (Instruction.NextInstruction != nullptr) + Instruction.NextInstruction->PreviousInstruction = Instruction.PreviousInstruction; + else + LastInstruction = Instruction.PreviousInstruction; + + Instruction.detachFromBlock(); + return {}; +} + +void MachineBasicBlock::clearInstructions() noexcept { + MachineInstr *Instruction = FirstInstruction; + while (Instruction != nullptr) { + MachineInstr *NextInstruction = Instruction->NextInstruction; + Instruction->detachFromBlock(); + Instruction = NextInstruction; + } + FirstInstruction = nullptr; + LastInstruction = nullptr; +} + +Expected MachineBasicBlock::addLiveIn(PhysicalRegister PhysReg, LaneMask Lanes) { + if (!PhysReg.isValid() || Lanes.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "block live-in requires a physical register and nonempty lanes"); + } + + const auto Position = + std::ranges::find_if(LiveIns, [PhysReg](const MachineBasicBlockLiveIn &LiveIn) { + return LiveIn.PhysReg == PhysReg; + }); + if (Position != LiveIns.end()) { + Position->Lanes = Position->Lanes | Lanes; + return {}; + } + + LiveIns.push_back(MachineBasicBlockLiveIn{PhysReg, Lanes}); + return {}; +} + +Expected MachineBasicBlock::removeLiveIn(PhysicalRegister PhysReg) { + const auto Position = + std::ranges::find_if(LiveIns, [PhysReg](const MachineBasicBlockLiveIn &LiveIn) { + return LiveIn.PhysReg == PhysReg; + }); + if (Position == LiveIns.end()) { + return makeUnexpected(ErrorCode::InvalidArgument, "block physical live-in is not present"); + } + LiveIns.erase(Position); + return {}; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineCFGUpdater.cpp b/backend/lib/CodeGen/MachineCFGUpdater.cpp new file mode 100644 index 0000000..c78e318 --- /dev/null +++ b/backend/lib/CodeGen/MachineCFGUpdater.cpp @@ -0,0 +1,181 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineCFGUpdater.h" + +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" + +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +[[nodiscard]] std::optional findSuccessorIndex(const MachineBasicBlock &From, + const MachineBasicBlock &To) { + const auto Successors = From.successors(); + for (std::size_t Index = 0; Index < Successors.size(); ++Index) { + if (Successors[Index].Block == &To) + return Index; + } + return std::nullopt; +} + +} // namespace + +Expected MachineCFGUpdater::verifyOwnership(const MachineBasicBlock &Block) const { + if (&Block.function() != Function) { + return makeUnexpected(ErrorCode::InvalidArgument, + "CFG block belongs to another machine function"); + } + return {}; +} + +Expected MachineCFGUpdater::addSuccessor(MachineBasicBlock &From, MachineBasicBlock &To, + BranchProbability Probability) { + auto FromOwnership = verifyOwnership(From); + if (!FromOwnership) + return std::unexpected(FromOwnership.error()); + auto ToOwnership = verifyOwnership(To); + if (!ToOwnership) + return std::unexpected(ToOwnership.error()); + + const auto Existing = findSuccessorIndex(From, To); + if (Existing) { + From.Successors[*Existing].Probability = + From.Successors[*Existing].Probability.saturatingAdd(Probability); + return {}; + } + + From.Successors.push_back(MachineSuccessor{&To, Probability}); + if (std::ranges::find(To.Predecessors, &From) == To.Predecessors.end()) + To.Predecessors.push_back(&From); + return {}; +} + +Expected MachineCFGUpdater::removeSuccessor(MachineBasicBlock &From, MachineBasicBlock &To) { + auto FromOwnership = verifyOwnership(From); + if (!FromOwnership) + return std::unexpected(FromOwnership.error()); + auto ToOwnership = verifyOwnership(To); + if (!ToOwnership) + return std::unexpected(ToOwnership.error()); + + const auto Successor = findSuccessorIndex(From, To); + if (!Successor) { + return makeUnexpected(ErrorCode::InvalidArgument, "CFG successor edge is not present"); + } + From.Successors.erase(From.Successors.begin() + static_cast(*Successor)); + + const auto Predecessor = std::ranges::find(To.Predecessors, &From); + if (Predecessor == To.Predecessors.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "CFG successor has no reciprocal predecessor"); + } + To.Predecessors.erase(Predecessor); + return {}; +} + +Expected MachineCFGUpdater::replaceSuccessor(MachineBasicBlock &From, + MachineBasicBlock &OldTarget, + MachineBasicBlock &NewTarget) { + auto FromOwnership = verifyOwnership(From); + if (!FromOwnership) + return std::unexpected(FromOwnership.error()); + auto OldOwnership = verifyOwnership(OldTarget); + if (!OldOwnership) + return std::unexpected(OldOwnership.error()); + auto NewOwnership = verifyOwnership(NewTarget); + if (!NewOwnership) + return std::unexpected(NewOwnership.error()); + + if (&OldTarget == &NewTarget) + return {}; + + const auto Existing = findSuccessorIndex(From, OldTarget); + if (!Existing) { + return makeUnexpected(ErrorCode::InvalidArgument, "replaced CFG successor edge is not present"); + } + const BranchProbability Probability = From.Successors[*Existing].Probability; + + auto RemoveResult = removeSuccessor(From, OldTarget); + if (!RemoveResult) + return std::unexpected(RemoveResult.error()); + auto AddResult = addSuccessor(From, NewTarget, Probability); + if (!AddResult) { + auto RestoreResult = addSuccessor(From, OldTarget, Probability); + if (!RestoreResult) { + return makeUnexpected(ErrorCode::InternalError, + "failed to restore CFG edge after replacement failure"); + } + return std::unexpected(AddResult.error()); + } + return {}; +} + +Expected MachineCFGUpdater::updateBranchProbability(MachineBasicBlock &From, + MachineBasicBlock &To, + BranchProbability Probability) { + auto FromOwnership = verifyOwnership(From); + if (!FromOwnership) + return std::unexpected(FromOwnership.error()); + auto ToOwnership = verifyOwnership(To); + if (!ToOwnership) + return std::unexpected(ToOwnership.error()); + + const auto Successor = findSuccessorIndex(From, To); + if (!Successor) { + return makeUnexpected(ErrorCode::InvalidArgument, "updated CFG successor edge is not present"); + } + From.Successors[*Successor].Probability = Probability; + return {}; +} + +Expected MachineCFGUpdater::transferSuccessors(MachineBasicBlock &From, + MachineBasicBlock &To) { + auto FromOwnership = verifyOwnership(From); + if (!FromOwnership) + return std::unexpected(FromOwnership.error()); + auto ToOwnership = verifyOwnership(To); + if (!ToOwnership) + return std::unexpected(ToOwnership.error()); + if (&From == &To) + return {}; + + const std::vector Successors = From.Successors; + for (const MachineSuccessor &Successor : Successors) { + auto RemoveResult = removeSuccessor(From, *Successor.Block); + if (!RemoveResult) + return std::unexpected(RemoveResult.error()); + auto AddResult = addSuccessor(To, *Successor.Block, Successor.Probability); + if (!AddResult) + return std::unexpected(AddResult.error()); + } + return {}; +} + +Expected MachineCFGUpdater::disconnectBlock(MachineBasicBlock &Block) { + auto Ownership = verifyOwnership(Block); + if (!Ownership) + return std::unexpected(Ownership.error()); + + const std::vector Successors = Block.Successors; + for (const MachineSuccessor &Successor : Successors) { + auto Result = removeSuccessor(Block, *Successor.Block); + if (!Result) + return std::unexpected(Result.error()); + } + + const std::vector Predecessors = Block.Predecessors; + for (MachineBasicBlock *Predecessor : Predecessors) { + auto Result = removeSuccessor(*Predecessor, Block); + if (!Result) + return std::unexpected(Result.error()); + } + return {}; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineFunction.cpp b/backend/lib/CodeGen/MachineFunction.cpp new file mode 100644 index 0000000..e19c115 --- /dev/null +++ b/backend/lib/CodeGen/MachineFunction.cpp @@ -0,0 +1,205 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineFunction.h" + +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { + +class MachineArena final { +public: + MachineArena() = default; + MachineArena(const MachineArena &) = delete; + MachineArena &operator=(const MachineArena &) = delete; + MachineArena(MachineArena &&) = delete; + MachineArena &operator=(MachineArena &&) = delete; + + ~MachineArena() { + for (auto Position = Destructors.rbegin(); Position != Destructors.rend(); ++Position) + Position->Destroy(Position->Object); + } + + template + [[nodiscard]] ObjectT *create(ArgumentTs &&...Arguments) { + void *Storage = Resource.allocate(sizeof(ObjectT), alignof(ObjectT)); + ObjectT *Object = ::new (Storage) ObjectT(std::forward(Arguments)...); + try { + Destructors.push_back(DestructorRecord{ + Object, + [](void *RawObject) noexcept { std::destroy_at(static_cast(RawObject)); }, + }); + } catch (...) { + std::destroy_at(Object); + throw; + } + return Object; + } + +private: + struct DestructorRecord final { + void *Object; + void (*Destroy)(void *) noexcept; + }; + + std::pmr::monotonic_buffer_resource Resource; + std::vector Destructors; +}; + +Expected> +MachineFunction::create(std::string Name, MachineFunctionStableID StableID) { + if (Name.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "machine function name cannot be empty"); + if (!StableID.isValid()) + return makeUnexpected(ErrorCode::InvalidArgument, "machine function StableID must be valid"); + return std::unique_ptr(new MachineFunction(std::move(Name), StableID)); +} + +MachineFunction::MachineFunction(std::string Name, MachineFunctionStableID StableID) + : Name(std::move(Name)), StableID(StableID), Arena(std::make_unique()) {} + +MachineFunction::~MachineFunction() { + for (MachineBasicBlock *Block = FirstBlock; Block != nullptr; Block = Block->NextBlock) { + Block->clearInstructions(); + Block->Predecessors.clear(); + Block->Successors.clear(); + } +} + +Expected MachineFunction::createBasicBlock() { + auto ID = BlockIDGenerator.allocate(); + if (!ID) + return std::unexpected(ID.error()); + MachineBasicBlock *Block = Arena->create(*this, *ID); + AllBlocks.push_back(Block); + return Block; +} + +Expected MachineFunction::createInstruction(Opcode InstructionOpcode) { + if (!InstructionOpcode.isValid()) + return makeUnexpected(ErrorCode::InvalidArgument, "machine opcode must be nonzero"); + + auto ID = InstrIDGenerator.allocate(); + if (!ID) + return std::unexpected(ID.error()); + MachineInstr *Instruction = Arena->create(*this, InstructionOpcode, *ID); + AllInstructions.push_back(Instruction); + return Instruction; +} + +Expected +MachineFunction::createMemOperand(MachineMemOperandDesc Description) { + auto MemOperand = MachineMemOperand::create(std::move(Description)); + if (!MemOperand) + return std::unexpected(MemOperand.error()); + + const MachineMemOperand *Stored = Arena->create(std::move(*MemOperand)); + AllMemOperands.push_back(Stored); + return Stored; +} + +Expected MachineFunction::appendBlock(MachineBasicBlock &Block) { + if (Block.OwnerFunction != this) + return makeUnexpected(ErrorCode::InvalidArgument, + "basic block belongs to another machine function"); + if (Block.IsLinked) + return makeUnexpected(ErrorCode::InvalidArgument, "basic block is already linked"); + + Block.PreviousBlock = LastBlock; + Block.NextBlock = nullptr; + if (LastBlock != nullptr) + LastBlock->NextBlock = &Block; + else + FirstBlock = &Block; + LastBlock = &Block; + Block.IsLinked = true; + renumberBlocks(); + return {}; +} + +Expected MachineFunction::insertBlockBefore(MachineBasicBlock &Position, + MachineBasicBlock &Block) { + if (Position.OwnerFunction != this || !Position.IsLinked) + return makeUnexpected(ErrorCode::InvalidArgument, + "block insertion position is not linked to this function"); + if (Block.OwnerFunction != this || Block.IsLinked) + return makeUnexpected(ErrorCode::InvalidArgument, + "inserted block is linked or belongs to another function"); + + Block.PreviousBlock = Position.PreviousBlock; + Block.NextBlock = &Position; + if (Position.PreviousBlock != nullptr) + Position.PreviousBlock->NextBlock = &Block; + else + FirstBlock = &Block; + Position.PreviousBlock = &Block; + Block.IsLinked = true; + renumberBlocks(); + return {}; +} + +Expected MachineFunction::removeBlock(MachineBasicBlock &Block) { + if (Block.OwnerFunction != this || !Block.IsLinked) + return makeUnexpected(ErrorCode::InvalidArgument, + "removed block is not linked to this function"); + if (!Block.Predecessors.empty() || !Block.Successors.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "disconnect CFG edges before removing a basic block"); + } + + Block.clearInstructions(); + if (Block.PreviousBlock != nullptr) + Block.PreviousBlock->NextBlock = Block.NextBlock; + else + FirstBlock = Block.NextBlock; + if (Block.NextBlock != nullptr) + Block.NextBlock->PreviousBlock = Block.PreviousBlock; + else + LastBlock = Block.PreviousBlock; + + Block.IsLinked = false; + Block.PreviousBlock = nullptr; + Block.NextBlock = nullptr; + Block.DenseNumber.reset(); + Block.LayoutIndex.reset(); + renumberBlocks(); + return {}; +} + +std::size_t MachineFunction::blockCount() const noexcept { + std::size_t Count = 0; + for (const MachineBasicBlock *Block = FirstBlock; Block != nullptr; Block = Block->next()) { + ++Count; + } + return Count; +} + +bool MachineFunction::ownsMemOperand(const MachineMemOperand &MemOperand) const noexcept { + return std::ranges::find(AllMemOperands, &MemOperand) != AllMemOperands.end(); +} + +MachineCFGUpdater MachineFunction::cfgUpdater() noexcept { + return MachineCFGUpdater(*this); +} + +void MachineFunction::renumberBlocks() noexcept { + std::uint32_t Number = 0; + for (MachineBasicBlock *Block = FirstBlock; Block != nullptr; Block = Block->NextBlock) { + Block->DenseNumber = Number; + Block->LayoutIndex = Number; + ++Number; + } +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineInstr.cpp b/backend/lib/CodeGen/MachineInstr.cpp new file mode 100644 index 0000000..3692258 --- /dev/null +++ b/backend/lib/CodeGen/MachineInstr.cpp @@ -0,0 +1,199 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineInstr.h" + +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" + +#include +#include +#include +#include + +namespace rcc { + +MachineInstr::MachineInstr(MachineFunction &OwnerFunction, Opcode InstructionOpcode, + MachineInstrStableID StableID) + : OwnerFunction(&OwnerFunction), InstructionOpcode(InstructionOpcode), StableID(StableID) {} + +MachineInstr::~MachineInstr() { + for (MachineOperand &Operand : Operands) + Operand.detachFromInstruction(); +} + +Expected MachineInstr::setOpcode(Opcode NewOpcode) { + if (!NewOpcode.isValid()) + return makeUnexpected(ErrorCode::InvalidArgument, "machine opcode must be nonzero"); + InstructionOpcode = NewOpcode; + return {}; +} + +MachineOperand *MachineInstr::operandAt(std::size_t Index) noexcept { + if (Index >= Operands.size()) + return nullptr; + return &Operands[Index]; +} + +const MachineOperand *MachineInstr::operandAt(std::size_t Index) const noexcept { + if (Index >= Operands.size()) + return nullptr; + return &Operands[Index]; +} + +void MachineInstr::reserveOperands(std::size_t Capacity) { + Operands.reserve(Capacity); +} + +Expected MachineInstr::addOperand(MachineOperand Operand) { + return insertOperand(Operands.size(), std::move(Operand)); +} + +Expected MachineInstr::insertOperand(std::size_t Index, MachineOperand Operand) { + if (Index > Operands.size()) + return makeUnexpected(ErrorCode::InvalidArgument, "operand insertion index is out of range"); + if (Operand.Parent != nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "operand already belongs to an instruction"); + if (Operand.TiedOperandIndex) + return makeUnexpected(ErrorCode::InvalidArgument, + "detached operand cannot carry a tied operand index"); + if (const auto *BlockOperand = Operand.getIf(); + BlockOperand != nullptr && &BlockOperand->Block->function() != OwnerFunction) { + return makeUnexpected(ErrorCode::InvalidArgument, + "basic block operand belongs to another machine function"); + } + if (const Register *Reg = Operand.getIf(); + Reg != nullptr && Reg->isVirtual() && + !OwnerFunction->registerInfo().isKnownVirtualRegister(*Reg)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "register operand references an unknown virtual register"); + } + + Operands.insert(Operands.begin() + static_cast(Index), std::move(Operand)); + adjustTiesForInsertion(Index); + Operands[Index].attachTo(*this, linkedRegisterInfo()); + return {}; +} + +Expected MachineInstr::eraseOperand(std::size_t Index) { + if (Index >= Operands.size()) + return makeUnexpected(ErrorCode::InvalidArgument, "operand erase index is out of range"); + + adjustTiesForErasure(Index); + Operands.erase(Operands.begin() + static_cast(Index)); + return {}; +} + +Expected MachineInstr::tieOperands(std::size_t DefIndex, std::size_t UseIndex) { + if (DefIndex >= Operands.size() || UseIndex >= Operands.size() || DefIndex == UseIndex) { + return makeUnexpected(ErrorCode::InvalidArgument, "tied operand indices are invalid"); + } + + MachineOperand &DefOperand = Operands[DefIndex]; + MachineOperand &UseOperand = Operands[UseIndex]; + if (!DefOperand.isRegister() || !UseOperand.isRegister() || !DefOperand.isDef() || + !UseOperand.isUse()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "tie must connect a register definition and use"); + } + if (DefOperand.TiedOperandIndex || UseOperand.TiedOperandIndex) { + return makeUnexpected(ErrorCode::InvalidArgument, + "an operand cannot participate in more than one tie"); + } + + DefOperand.setTiedOperandIndex(UseIndex); + UseOperand.setTiedOperandIndex(DefIndex); + return {}; +} + +Expected MachineInstr::untieOperand(std::size_t Index) { + if (Index >= Operands.size()) + return makeUnexpected(ErrorCode::InvalidArgument, "operand tie index is out of range"); + const auto OtherIndex = Operands[Index].TiedOperandIndex; + if (!OtherIndex) + return makeUnexpected(ErrorCode::InvalidArgument, "operand is not tied"); + if (*OtherIndex >= Operands.size() || Operands[*OtherIndex].TiedOperandIndex != Index) { + return makeUnexpected(ErrorCode::VerificationError, "operand tie relation is not reciprocal"); + } + + Operands[*OtherIndex].setTiedOperandIndex(std::nullopt); + Operands[Index].setTiedOperandIndex(std::nullopt); + return {}; +} + +Expected MachineInstr::addMemOperand(const MachineMemOperand &MemOperand) { + if (!OwnerFunction->ownsMemOperand(MemOperand)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine memory operand belongs to another function"); + } + MemOperands.push_back(&MemOperand); + return {}; +} + +Expected MachineInstr::eraseMemOperand(std::size_t Index) { + if (Index >= MemOperands.size()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine memory operand index is out of range"); + } + MemOperands.erase(MemOperands.begin() + static_cast(Index)); + return {}; +} + +MachineRegisterInfo *MachineInstr::linkedRegisterInfo() noexcept { + if (!isLinked()) + return nullptr; + return &OwnerFunction->registerInfo(); +} + +Expected MachineInstr::attachToBlock(MachineBasicBlock &Block) { + if (ParentBlock != nullptr) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction is already linked to a basic block"); + } + + MachineRegisterInfo &RegInfo = OwnerFunction->registerInfo(); + for (const MachineOperand &Operand : Operands) { + const Register *Reg = Operand.getIf(); + if (Reg != nullptr && Reg->isVirtual() && !RegInfo.isKnownVirtualRegister(*Reg)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction references an unknown virtual register"); + } + } + + ParentBlock = &Block; + for (MachineOperand &Operand : Operands) { + const Register *Reg = Operand.getIf(); + if (Reg != nullptr && !Reg->isNoRegister()) + Operand.linkToRegInfo(RegInfo); + } + return {}; +} + +void MachineInstr::detachFromBlock() noexcept { + for (MachineOperand &Operand : Operands) + Operand.unlinkFromRegInfo(); + ParentBlock = nullptr; + PreviousInstruction = nullptr; + NextInstruction = nullptr; +} + +void MachineInstr::adjustTiesForInsertion(std::size_t Index) noexcept { + for (MachineOperand &Operand : Operands) { + if (Operand.TiedOperandIndex && *Operand.TiedOperandIndex >= Index) + ++*Operand.TiedOperandIndex; + } +} + +void MachineInstr::adjustTiesForErasure(std::size_t Index) noexcept { + for (MachineOperand &Operand : Operands) { + if (!Operand.TiedOperandIndex) + continue; + if (*Operand.TiedOperandIndex == Index) + Operand.TiedOperandIndex.reset(); + else if (*Operand.TiedOperandIndex > Index) + --*Operand.TiedOperandIndex; + } +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineOperand.cpp b/backend/lib/CodeGen/MachineOperand.cpp new file mode 100644 index 0000000..0e5febd --- /dev/null +++ b/backend/lib/CodeGen/MachineOperand.cpp @@ -0,0 +1,326 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineOperand.h" + +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" + +#include +#include +#include +#include +#include +#include + +namespace rcc { + +Expected FloatingPointBits::create(FloatSemantics Semantics, + std::span Words) { + const auto BitWidth = getFloatSemanticsBitWidth(Semantics); + if (!BitWidth) { + return makeUnexpected(ErrorCode::InvalidArgument, "floating immediate has unknown semantics"); + } + + const std::size_t RequiredWords = (*BitWidth + 63U) / 64U; + if (RequiredWords > 2 || Words.size() != RequiredWords) { + return makeUnexpected(ErrorCode::InvalidArgument, + "floating immediate bit pattern has the wrong word count"); + } + + const std::uint32_t UsedBitsInLastWord = *BitWidth % 64U; + if (UsedBitsInLastWord != 0 && (Words.back() >> UsedBitsInLastWord) != 0) { + return makeUnexpected(ErrorCode::InvalidArgument, + "floating immediate has nonzero bits above its semantics width"); + } + + std::array StoredWords{}; + std::ranges::copy(Words, StoredWords.begin()); + return FloatingPointBits(Semantics, StoredWords, static_cast(RequiredWords)); +} + +RegisterOperandFlags::RegisterOperandFlags( + std::initializer_list Flags) noexcept { + for (const RegisterOperandFlag Flag : Flags) + set(Flag); +} + +Expected MachineOperand::verifyRegisterFlags(RegisterOperandFlags Flags) { + const bool IsDef = Flags.has(RegisterOperandFlag::Define); + const bool IsUse = Flags.has(RegisterOperandFlag::Use); + if (!IsDef && !IsUse) { + return makeUnexpected(ErrorCode::InvalidArgument, + "register operand must be a definition or use"); + } + if (Flags.has(RegisterOperandFlag::Kill) && !IsUse) { + return makeUnexpected(ErrorCode::InvalidArgument, "kill flag requires a register use"); + } + if (Flags.has(RegisterOperandFlag::Dead) && !IsDef) { + return makeUnexpected(ErrorCode::InvalidArgument, "dead flag requires a register definition"); + } + if (Flags.has(RegisterOperandFlag::Undef) && !IsUse) { + return makeUnexpected(ErrorCode::InvalidArgument, "undef flag requires a register use"); + } + if (Flags.has(RegisterOperandFlag::EarlyClobber) && !IsDef) { + return makeUnexpected(ErrorCode::InvalidArgument, + "early-clobber flag requires a register definition"); + } + if (Flags.has(RegisterOperandFlag::InternalRead) && (!IsDef || !IsUse)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "internal-read flag requires a register def-use operand"); + } + if (IsDef && IsUse && !Flags.has(RegisterOperandFlag::InternalRead)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "register def-use operand requires internal-read"); + } + if (Flags.has(RegisterOperandFlag::Debug) && (!IsUse || IsDef)) { + return makeUnexpected(ErrorCode::InvalidArgument, "debug register operand must be a use"); + } + return {}; +} + +Expected MachineOperand::registerOperand(Register Reg, RegisterOperandFlags Flags, + SubRegIndex SubReg, + std::uint32_t TargetFlags) { + const auto Validation = verifyRegisterFlags(Flags); + if (!Validation) + return std::unexpected(Validation.error()); + + MachineOperand Operand(Kind::Register, Reg, TargetFlags); + Operand.RegFlags = Flags; + Operand.RegSubReg = SubReg; + return Operand; +} + +MachineOperand MachineOperand::immediate(std::int64_t Value, std::uint32_t TargetFlags) { + return MachineOperand(Kind::Immediate, Value, TargetFlags); +} + +MachineOperand MachineOperand::floatingImmediate(FloatingPointBits Bits, + std::uint32_t TargetFlags) { + return MachineOperand(Kind::FloatingImmediate, FloatingImmediateOperand{Bits}, TargetFlags); +} + +MachineOperand MachineOperand::basicBlock(MachineBasicBlock &Block, std::uint32_t TargetFlags) { + return MachineOperand(Kind::BasicBlock, BasicBlockOperand{&Block}, TargetFlags); +} + +MachineOperand MachineOperand::frameIndex(FrameIndex Index, std::int64_t Offset, + std::uint32_t TargetFlags) { + return MachineOperand(Kind::FrameIndex, FrameIndexOperand{Index, Offset}, TargetFlags); +} + +MachineOperand MachineOperand::constantPool(ConstantPoolIndex Index, std::int64_t Offset, + std::uint32_t TargetFlags) { + return MachineOperand(Kind::ConstantPoolIndex, ConstantPoolOperand{Index, Offset}, TargetFlags); +} + +MachineOperand MachineOperand::jumpTable(JumpTableIndex Index, std::uint32_t TargetFlags) { + return MachineOperand(Kind::JumpTableIndex, JumpTableOperand{Index}, TargetFlags); +} + +Expected MachineOperand::globalSymbol(std::string Name, std::int64_t Offset, + std::uint32_t TargetFlags) { + if (Name.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, "global symbol operand name cannot be empty"); + } + return MachineOperand(Kind::GlobalSymbol, GlobalSymbolOperand{std::move(Name), Offset}, + TargetFlags); +} + +Expected MachineOperand::externalSymbol(std::string Name, std::int64_t Offset, + std::uint32_t TargetFlags) { + if (Name.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "external symbol operand name cannot be empty"); + } + return MachineOperand(Kind::ExternalSymbol, ExternalSymbolOperand{std::move(Name), Offset}, + TargetFlags); +} + +Expected MachineOperand::blockAddress(std::string FunctionName, + std::string BlockName, std::int64_t Offset, + std::uint32_t TargetFlags) { + if (FunctionName.empty() || BlockName.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "block address operand requires function and block names"); + } + return MachineOperand(Kind::BlockAddress, + BlockAddressOperand{std::move(FunctionName), std::move(BlockName), Offset}, + TargetFlags); +} + +Expected MachineOperand::registerMask(std::shared_ptr Mask, + std::uint32_t TargetFlags) { + if (!Mask) { + return makeUnexpected(ErrorCode::InvalidArgument, "register mask operand cannot be null"); + } + return MachineOperand(Kind::RegisterMask, RegisterMaskOperand{std::move(Mask)}, TargetFlags); +} + +Expected MachineOperand::metadata(std::string Marker, std::uint32_t TargetFlags) { + if (Marker.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, "metadata operand marker cannot be empty"); + } + return MachineOperand(Kind::Metadata, MetadataOperand{std::move(Marker)}, TargetFlags); +} + +MachineOperand MachineOperand::targetIndex(TargetIndex Index, std::int64_t Offset, + std::uint32_t TargetFlags) { + return MachineOperand(Kind::TargetIndex, TargetIndexOperand{Index, Offset}, TargetFlags); +} + +Expected MachineOperand::mcSymbol(std::string Name, std::int64_t Offset, + std::uint32_t TargetFlags) { + if (Name.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, "MC symbol operand name cannot be empty"); + } + return MachineOperand(Kind::MCSymbol, MCSymbolOperand{std::move(Name), Offset}, TargetFlags); +} + +MachineOperand::MachineOperand(MachineOperand &&Other) noexcept + : OperandKind(Other.OperandKind), Storage(std::move(Other.Storage)), RegFlags(Other.RegFlags), + RegSubReg(Other.RegSubReg), TiedOperandIndex(Other.TiedOperandIndex), + TargetFlags(Other.TargetFlags), Parent(Other.Parent) { + takeRegLinkFrom(Other); + Other.Parent = nullptr; + Other.TiedOperandIndex.reset(); +} + +MachineOperand &MachineOperand::operator=(MachineOperand &&Other) noexcept { + if (this == &Other) + return *this; + + unlinkFromRegInfo(); + OperandKind = Other.OperandKind; + Storage = std::move(Other.Storage); + RegFlags = Other.RegFlags; + RegSubReg = Other.RegSubReg; + TiedOperandIndex = Other.TiedOperandIndex; + TargetFlags = Other.TargetFlags; + Parent = Other.Parent; + takeRegLinkFrom(Other); + Other.Parent = nullptr; + Other.TiedOperandIndex.reset(); + return *this; +} + +MachineOperand::~MachineOperand() { + unlinkFromRegInfo(); +} + +std::optional MachineOperand::registerValue() const noexcept { + if (!isRegister()) + return std::nullopt; + return std::get(Storage); +} + +bool MachineOperand::isDef() const noexcept { + return isRegister() && RegFlags.has(RegisterOperandFlag::Define); +} + +bool MachineOperand::isUse() const noexcept { + return isRegister() && RegFlags.has(RegisterOperandFlag::Use); +} + +bool MachineOperand::isDebugUse() const noexcept { + return isUse() && RegFlags.has(RegisterOperandFlag::Debug); +} + +bool MachineOperand::isImplicit() const noexcept { + return isRegister() && RegFlags.has(RegisterOperandFlag::Implicit); +} + +Expected MachineOperand::setRegister(Register Reg) { + if (!isRegister()) { + return makeUnexpected(ErrorCode::InvalidArgument, "setRegister requires a register operand"); + } + + MachineRegisterInfo *RegInfo = LinkedRegInfo; + if (RegInfo == nullptr && Parent != nullptr) + RegInfo = &Parent->function().registerInfo(); + if (RegInfo != nullptr && Reg.isVirtual() && !RegInfo->isKnownVirtualRegister(Reg)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "register operand references an unknown virtual register"); + } + + const bool WasLinked = LinkedRegInfo != nullptr; + unlinkFromRegInfo(); + Storage = Reg; + if (WasLinked && !Reg.isNoRegister()) + linkToRegInfo(*RegInfo); + return {}; +} + +Expected MachineOperand::setRegisterFlags(RegisterOperandFlags Flags) { + if (!isRegister()) { + return makeUnexpected(ErrorCode::InvalidArgument, "register flags require a register operand"); + } + const auto Validation = verifyRegisterFlags(Flags); + if (!Validation) + return std::unexpected(Validation.error()); + RegFlags = Flags; + return {}; +} + +Expected MachineOperand::setSubReg(SubRegIndex SubReg) { + if (!isRegister()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "subregister index requires a register operand"); + } + RegSubReg = SubReg; + return {}; +} + +MachineOperand MachineOperand::cloneDetached() const { + MachineOperand Result(OperandKind, Storage, TargetFlags); + Result.RegFlags = RegFlags; + Result.RegSubReg = RegSubReg; + return Result; +} + +void MachineOperand::attachTo(MachineInstr &Instruction, MachineRegisterInfo *RegInfo) { + Parent = &Instruction; + if (RegInfo != nullptr && isRegister() && !std::get(Storage).isNoRegister()) { + linkToRegInfo(*RegInfo); + } +} + +void MachineOperand::detachFromInstruction() noexcept { + unlinkFromRegInfo(); + Parent = nullptr; +} + +void MachineOperand::linkToRegInfo(MachineRegisterInfo &RegInfo) { + RegInfo.linkOperand(*this); +} + +void MachineOperand::unlinkFromRegInfo() noexcept { + if (PreviousRegLink == nullptr) + return; + + *PreviousRegLink = NextRegOperand; + if (NextRegOperand != nullptr) + NextRegOperand->PreviousRegLink = PreviousRegLink; + + PreviousRegLink = nullptr; + NextRegOperand = nullptr; + LinkedRegInfo = nullptr; +} + +void MachineOperand::takeRegLinkFrom(MachineOperand &Other) noexcept { + LinkedRegInfo = Other.LinkedRegInfo; + PreviousRegLink = Other.PreviousRegLink; + NextRegOperand = Other.NextRegOperand; + + if (PreviousRegLink != nullptr) + *PreviousRegLink = this; + if (NextRegOperand != nullptr) + NextRegOperand->PreviousRegLink = &NextRegOperand; + + Other.LinkedRegInfo = nullptr; + Other.PreviousRegLink = nullptr; + Other.NextRegOperand = nullptr; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineRegisterInfo.cpp b/backend/lib/CodeGen/MachineRegisterInfo.cpp new file mode 100644 index 0000000..cc0955e --- /dev/null +++ b/backend/lib/CodeGen/MachineRegisterInfo.cpp @@ -0,0 +1,362 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineRegisterInfo.h" + +#include "rcc/CodeGen/MachineOperand.h" + +#include +#include +#include +#include +#include + +namespace rcc { + +RegOperandIterator::RegOperandIterator(MachineOperand *Current, bool RequireUse, bool RequireDef, + bool SkipDebug) noexcept + : Current(Current), RequireUse(RequireUse), RequireDef(RequireDef), SkipDebug(SkipDebug) { + skipFiltered(); +} + +RegOperandIterator::reference RegOperandIterator::operator*() const noexcept { + return *Current; +} + +RegOperandIterator::pointer RegOperandIterator::operator->() const noexcept { + return Current; +} + +RegOperandIterator &RegOperandIterator::operator++() noexcept { + Current = Current->NextRegOperand; + skipFiltered(); + return *this; +} + +RegOperandIterator RegOperandIterator::operator++(int) noexcept { + RegOperandIterator Previous = *this; + ++*this; + return Previous; +} + +void RegOperandIterator::skipFiltered() noexcept { + while (Current != nullptr) { + if (RequireUse && !Current->isUse()) { + Current = Current->NextRegOperand; + continue; + } + if (RequireDef && !Current->isDef()) { + Current = Current->NextRegOperand; + continue; + } + if (SkipDebug && Current->isDebugUse()) { + Current = Current->NextRegOperand; + continue; + } + break; + } +} + +MachineRegisterInfo::~MachineRegisterInfo() = default; + +Expected MachineRegisterInfo::createVirtualRegister() { + auto Reg = Register::makeVirtual(VirtualRegisters.size()); + if (!Reg) + return std::unexpected(Reg.error()); + VirtualRegisters.emplace_back(); + return *Reg; +} + +Expected MachineRegisterInfo::createVirtualRegister(LLT Type) { + if (!Type.isValid()) { + return makeUnexpected(ErrorCode::InvalidArgument, "virtual register type must be a valid LLT"); + } + + auto Reg = createVirtualRegister(); + if (!Reg) + return std::unexpected(Reg.error()); + VirtualRegisters.back().Type = Type; + return *Reg; +} + +Expected MachineRegisterInfo::eraseVirtualRegister(Register Reg) { + auto Info = virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + if (headFor(Reg) != nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "cannot erase a virtual register with operands"); + } + + Info->get().IsTombstone = true; + Info->get().Type.reset(); + Info->get().Bank.reset(); + Info->get().RegClass.reset(); + Info->get().AllocationHints.clear(); + return {}; +} + +bool MachineRegisterInfo::isKnownVirtualRegister(Register Reg) const noexcept { + const auto Index = Reg.virtualIndex(); + if (!Index || *Index >= VirtualRegisters.size()) + return false; + return !VirtualRegisters[*Index].IsTombstone; +} + +Expected> +MachineRegisterInfo::virtualRegisterInfo(Register Reg) { + const auto Index = Reg.virtualIndex(); + if (!Index || *Index >= VirtualRegisters.size() || VirtualRegisters[*Index].IsTombstone) { + return makeUnexpected(ErrorCode::InvalidArgument, "register is not a live virtual register"); + } + return std::ref(VirtualRegisters[*Index]); +} + +Expected> +MachineRegisterInfo::virtualRegisterInfo(Register Reg) const { + const auto Index = Reg.virtualIndex(); + if (!Index || *Index >= VirtualRegisters.size() || VirtualRegisters[*Index].IsTombstone) { + return makeUnexpected(ErrorCode::InvalidArgument, "register is not a live virtual register"); + } + return std::cref(VirtualRegisters[*Index]); +} + +Expected MachineRegisterInfo::setType(Register Reg, LLT Type) { + if (!Type.isValid()) { + return makeUnexpected(ErrorCode::InvalidArgument, "virtual register type must be a valid LLT"); + } + auto Info = virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + Info->get().Type = Type; + return {}; +} + +Expected MachineRegisterInfo::clearType(Register Reg) { + auto Info = virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + Info->get().Type.reset(); + return {}; +} + +Expected MachineRegisterInfo::setRegisterBank(Register Reg, RegisterBankID Bank) { + auto Info = virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + Info->get().Bank = Bank; + return {}; +} + +Expected MachineRegisterInfo::clearRegisterBank(Register Reg) { + auto Info = virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + Info->get().Bank.reset(); + return {}; +} + +Expected MachineRegisterInfo::setRegisterClass(Register Reg, RegisterClassID RegClass) { + auto Info = virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + Info->get().RegClass = RegClass; + return {}; +} + +Expected MachineRegisterInfo::clearRegisterClass(Register Reg) { + auto Info = virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + Info->get().RegClass.reset(); + return {}; +} + +Expected MachineRegisterInfo::addAllocationHint(Register Reg, PhysicalRegister Hint) { + if (!Hint.isValid()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "allocation hint must name a physical register"); + } + auto Info = virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + + auto &Hints = Info->get().AllocationHints; + if (std::ranges::find(Hints, Hint) == Hints.end()) + Hints.push_back(Hint); + return {}; +} + +void MachineRegisterInfo::clearAllVirtualRegisterTypes() noexcept { + for (VirtualRegisterInfo &Info : VirtualRegisters) { + if (!Info.IsTombstone) + Info.Type.reset(); + } +} + +Expected MachineRegisterInfo::addLiveIn(PhysicalRegister PhysReg, + std::optional InitialVirtualRegister) { + if (!PhysReg.isValid()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "function live-in must name a physical register"); + } + if (InitialVirtualRegister && !isKnownVirtualRegister(*InitialVirtualRegister)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "function live-in initial value must be a live virtual register"); + } + if (std::ranges::any_of(LiveIns, [PhysReg](const PhysicalRegisterLiveIn &LiveIn) { + return LiveIn.PhysReg == PhysReg; + })) { + return makeUnexpected(ErrorCode::InvalidArgument, + "function physical live-in is already present"); + } + + LiveIns.push_back(PhysicalRegisterLiveIn{PhysReg, InitialVirtualRegister}); + return {}; +} + +Expected MachineRegisterInfo::reservePhysicalRegister(PhysicalRegister PhysReg) { + if (!PhysReg.isValid()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "reserved register must name a physical register"); + } + if (isReserved(PhysReg)) { + return makeUnexpected(ErrorCode::InvalidArgument, "physical register is already reserved"); + } + ReservedRegisters.push_back(PhysReg); + return {}; +} + +bool MachineRegisterInfo::isReserved(PhysicalRegister PhysReg) const noexcept { + return std::ranges::find(ReservedRegisters, PhysReg) != ReservedRegisters.end(); +} + +RegOperandRange MachineRegisterInfo::regOperands(Register Reg) noexcept { + return RegOperandRange(headFor(Reg), false, false, false); +} + +RegOperandRange MachineRegisterInfo::regNoDebugOperands(Register Reg) noexcept { + return RegOperandRange(headFor(Reg), false, false, true); +} + +RegOperandRange MachineRegisterInfo::useOperands(Register Reg, bool IncludeDebug) noexcept { + return RegOperandRange(headFor(Reg), true, false, !IncludeDebug); +} + +RegOperandRange MachineRegisterInfo::defOperands(Register Reg) noexcept { + return RegOperandRange(headFor(Reg), false, true, false); +} + +bool MachineRegisterInfo::useEmpty(Register Reg, bool IncludeDebug) const noexcept { + for (MachineOperand *Operand = headFor(Reg); Operand != nullptr; + Operand = Operand->NextRegOperand) { + if (Operand->isUse() && (IncludeDebug || !Operand->isDebugUse())) + return false; + } + return true; +} + +bool MachineRegisterInfo::hasOneUse(Register Reg, bool IncludeDebug) const noexcept { + bool FoundUse = false; + for (MachineOperand *Operand = headFor(Reg); Operand != nullptr; + Operand = Operand->NextRegOperand) { + if (!Operand->isUse() || (!IncludeDebug && Operand->isDebugUse())) + continue; + if (FoundUse) + return false; + FoundUse = true; + } + return FoundUse; +} + +const MachineOperand *MachineRegisterInfo::getUniqueVRegDef(Register Reg) const noexcept { + if (!isKnownVirtualRegister(Reg)) + return nullptr; + + const MachineOperand *UniqueDef = nullptr; + for (MachineOperand *Operand = headFor(Reg); Operand != nullptr; + Operand = Operand->NextRegOperand) { + if (!Operand->isDef()) + continue; + if (UniqueDef != nullptr) + return nullptr; + UniqueDef = Operand; + } + return UniqueDef; +} + +Expected MachineRegisterInfo::replaceRegWith(Register OldReg, Register NewReg) { + if (OldReg.isNoRegister() || NewReg.isNoRegister()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "register replacement requires two nonzero registers"); + } + if ((OldReg.isVirtual() && !isKnownVirtualRegister(OldReg)) || + (NewReg.isVirtual() && !isKnownVirtualRegister(NewReg))) { + return makeUnexpected(ErrorCode::InvalidArgument, + "register replacement references an unknown virtual register"); + } + + std::size_t ReplacementCount = 0; + MachineOperand *Operand = headFor(OldReg); + while (Operand != nullptr) { + MachineOperand *Next = Operand->NextRegOperand; + const auto Result = Operand->setRegister(NewReg); + if (!Result) + return std::unexpected(Result.error()); + ++ReplacementCount; + Operand = Next; + } + return ReplacementCount; +} + +Expected MachineRegisterInfo::verifyDefUseChains() const { + std::unordered_set SeenOperands; + + for (const auto &[Reg, HeadStorage] : DefUseHeads) { + MachineOperand *const *ExpectedPreviousLink = &HeadStorage->Head; + for (MachineOperand *Operand = HeadStorage->Head; Operand != nullptr; + Operand = Operand->NextRegOperand) { + if (!SeenOperands.insert(Operand).second) { + return makeUnexpected(ErrorCode::VerificationError, + "register def-use chains contain a cycle or duplicate operand"); + } + if (!Operand->isRegister() || Operand->registerValue() != Reg) { + return makeUnexpected(ErrorCode::VerificationError, + "register def-use chain contains an operand for another register"); + } + if (Operand->LinkedRegInfo != this || Operand->PreviousRegLink != ExpectedPreviousLink) { + return makeUnexpected(ErrorCode::VerificationError, + "register def-use chain back-link is corrupt"); + } + ExpectedPreviousLink = &Operand->NextRegOperand; + } + } + + return {}; +} + +MachineOperand *MachineRegisterInfo::headFor(Register Reg) const noexcept { + const auto Position = DefUseHeads.find(Reg); + if (Position == DefUseHeads.end()) + return nullptr; + return Position->second->Head; +} + +void MachineRegisterInfo::linkOperand(MachineOperand &Operand) { + const auto Reg = Operand.registerValue(); + if (!Reg || Reg->isNoRegister()) + return; + + auto &HeadStorage = DefUseHeads[*Reg]; + if (!HeadStorage) + HeadStorage = std::make_unique(); + + Operand.unlinkFromRegInfo(); + Operand.LinkedRegInfo = this; + Operand.PreviousRegLink = &HeadStorage->Head; + Operand.NextRegOperand = HeadStorage->Head; + if (HeadStorage->Head != nullptr) + HeadStorage->Head->PreviousRegLink = &Operand.NextRegOperand; + HeadStorage->Head = &Operand; +} + +} // namespace rcc -- cgit v1.2.3