aboutsummaryrefslogtreecommitdiff
path: root/backend/lib
diff options
context:
space:
mode:
Diffstat (limited to 'backend/lib')
-rw-r--r--backend/lib/CodeGen/CMakeLists.txt24
-rw-r--r--backend/lib/CodeGen/MachineBasicBlock.cpp157
-rw-r--r--backend/lib/CodeGen/MachineCFGUpdater.cpp181
-rw-r--r--backend/lib/CodeGen/MachineFunction.cpp205
-rw-r--r--backend/lib/CodeGen/MachineInstr.cpp199
-rw-r--r--backend/lib/CodeGen/MachineOperand.cpp326
-rw-r--r--backend/lib/CodeGen/MachineRegisterInfo.cpp362
7 files changed, 1454 insertions, 0 deletions
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 <algorithm>
+#include <cstddef>
+
+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<void> 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<void> 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<void> 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<void> 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<void> 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<void> 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 <algorithm>
+#include <cstddef>
+#include <optional>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] std::optional<std::size_t> 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<void> MachineCFGUpdater::verifyOwnership(const MachineBasicBlock &Block) const {
+ if (&Block.function() != Function) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "CFG block belongs to another machine function");
+ }
+ return {};
+}
+
+Expected<void> 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<void> 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<std::ptrdiff_t>(*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<void> 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<void> 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<void> 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<MachineSuccessor> 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<void> MachineCFGUpdater::disconnectBlock(MachineBasicBlock &Block) {
+ auto Ownership = verifyOwnership(Block);
+ if (!Ownership)
+ return std::unexpected(Ownership.error());
+
+ const std::vector<MachineSuccessor> Successors = Block.Successors;
+ for (const MachineSuccessor &Successor : Successors) {
+ auto Result = removeSuccessor(Block, *Successor.Block);
+ if (!Result)
+ return std::unexpected(Result.error());
+ }
+
+ const std::vector<MachineBasicBlock *> 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 <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+#include <memory_resource>
+#include <new>
+#include <utility>
+#include <vector>
+
+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 <typename ObjectT, typename... ArgumentTs>
+ [[nodiscard]] ObjectT *create(ArgumentTs &&...Arguments) {
+ void *Storage = Resource.allocate(sizeof(ObjectT), alignof(ObjectT));
+ ObjectT *Object = ::new (Storage) ObjectT(std::forward<ArgumentTs>(Arguments)...);
+ try {
+ Destructors.push_back(DestructorRecord{
+ Object,
+ [](void *RawObject) noexcept { std::destroy_at(static_cast<ObjectT *>(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<DestructorRecord> Destructors;
+};
+
+Expected<std::unique_ptr<MachineFunction>>
+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<MachineFunction>(new MachineFunction(std::move(Name), StableID));
+}
+
+MachineFunction::MachineFunction(std::string Name, MachineFunctionStableID StableID)
+ : Name(std::move(Name)), StableID(StableID), Arena(std::make_unique<MachineArena>()) {}
+
+MachineFunction::~MachineFunction() {
+ for (MachineBasicBlock *Block = FirstBlock; Block != nullptr; Block = Block->NextBlock) {
+ Block->clearInstructions();
+ Block->Predecessors.clear();
+ Block->Successors.clear();
+ }
+}
+
+Expected<MachineBasicBlock *> MachineFunction::createBasicBlock() {
+ auto ID = BlockIDGenerator.allocate();
+ if (!ID)
+ return std::unexpected(ID.error());
+ MachineBasicBlock *Block = Arena->create<MachineBasicBlock>(*this, *ID);
+ AllBlocks.push_back(Block);
+ return Block;
+}
+
+Expected<MachineInstr *> 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<MachineInstr>(*this, InstructionOpcode, *ID);
+ AllInstructions.push_back(Instruction);
+ return Instruction;
+}
+
+Expected<const MachineMemOperand *>
+MachineFunction::createMemOperand(MachineMemOperandDesc Description) {
+ auto MemOperand = MachineMemOperand::create(std::move(Description));
+ if (!MemOperand)
+ return std::unexpected(MemOperand.error());
+
+ const MachineMemOperand *Stored = Arena->create<MachineMemOperand>(std::move(*MemOperand));
+ AllMemOperands.push_back(Stored);
+ return Stored;
+}
+
+Expected<void> 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<void> 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<void> 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 <cstddef>
+#include <functional>
+#include <optional>
+#include <utility>
+
+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<void> 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<void> MachineInstr::addOperand(MachineOperand Operand) {
+ return insertOperand(Operands.size(), std::move(Operand));
+}
+
+Expected<void> 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<BasicBlockOperand>();
+ BlockOperand != nullptr && &BlockOperand->Block->function() != OwnerFunction) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "basic block operand belongs to another machine function");
+ }
+ if (const Register *Reg = Operand.getIf<Register>();
+ 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<std::ptrdiff_t>(Index), std::move(Operand));
+ adjustTiesForInsertion(Index);
+ Operands[Index].attachTo(*this, linkedRegisterInfo());
+ return {};
+}
+
+Expected<void> 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<std::ptrdiff_t>(Index));
+ return {};
+}
+
+Expected<void> 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<void> 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<void> 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<void> 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<std::ptrdiff_t>(Index));
+ return {};
+}
+
+MachineRegisterInfo *MachineInstr::linkedRegisterInfo() noexcept {
+ if (!isLinked())
+ return nullptr;
+ return &OwnerFunction->registerInfo();
+}
+
+Expected<void> 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<Register>();
+ 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<Register>();
+ 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 <algorithm>
+#include <array>
+#include <cstdint>
+#include <memory>
+#include <span>
+#include <utility>
+
+namespace rcc {
+
+Expected<FloatingPointBits> FloatingPointBits::create(FloatSemantics Semantics,
+ std::span<const std::uint64_t> 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<std::uint64_t, 2> StoredWords{};
+ std::ranges::copy(Words, StoredWords.begin());
+ return FloatingPointBits(Semantics, StoredWords, static_cast<std::uint8_t>(RequiredWords));
+}
+
+RegisterOperandFlags::RegisterOperandFlags(
+ std::initializer_list<RegisterOperandFlag> Flags) noexcept {
+ for (const RegisterOperandFlag Flag : Flags)
+ set(Flag);
+}
+
+Expected<void> 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> 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> 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> 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> 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> MachineOperand::registerMask(std::shared_ptr<const RegisterMask> 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> 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> 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<Register> MachineOperand::registerValue() const noexcept {
+ if (!isRegister())
+ return std::nullopt;
+ return std::get<Register>(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<void> 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<void> 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<void> 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<Register>(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 <algorithm>
+#include <functional>
+#include <memory>
+#include <optional>
+#include <unordered_set>
+
+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<Register> MachineRegisterInfo::createVirtualRegister() {
+ auto Reg = Register::makeVirtual(VirtualRegisters.size());
+ if (!Reg)
+ return std::unexpected(Reg.error());
+ VirtualRegisters.emplace_back();
+ return *Reg;
+}
+
+Expected<Register> 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<void> 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<std::reference_wrapper<VirtualRegisterInfo>>
+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<std::reference_wrapper<const VirtualRegisterInfo>>
+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<void> 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<void> MachineRegisterInfo::clearType(Register Reg) {
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ Info->get().Type.reset();
+ return {};
+}
+
+Expected<void> MachineRegisterInfo::setRegisterBank(Register Reg, RegisterBankID Bank) {
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ Info->get().Bank = Bank;
+ return {};
+}
+
+Expected<void> MachineRegisterInfo::clearRegisterBank(Register Reg) {
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ Info->get().Bank.reset();
+ return {};
+}
+
+Expected<void> MachineRegisterInfo::setRegisterClass(Register Reg, RegisterClassID RegClass) {
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ Info->get().RegClass = RegClass;
+ return {};
+}
+
+Expected<void> MachineRegisterInfo::clearRegisterClass(Register Reg) {
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ Info->get().RegClass.reset();
+ return {};
+}
+
+Expected<void> 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<void> MachineRegisterInfo::addLiveIn(PhysicalRegister PhysReg,
+ std::optional<Register> 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<void> 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<std::size_t> 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<void> MachineRegisterInfo::verifyDefUseChains() const {
+ std::unordered_set<const MachineOperand *> 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<RegOperandListHead>();
+
+ 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
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 19:27:59 +0000