From a2f8d7c5e22b510965327383410bd576f7cf28e7 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Thu, 13 Aug 2026 04:17:52 +0800 Subject: [CodeGen] Split machine liveness components --- backend/lib/CodeGen/SlotIndexes.cpp | 159 ++++++++++++++++++++++++++++++++++++ 1 file changed, 159 insertions(+) create mode 100644 backend/lib/CodeGen/SlotIndexes.cpp (limited to 'backend/lib/CodeGen/SlotIndexes.cpp') diff --git a/backend/lib/CodeGen/SlotIndexes.cpp b/backend/lib/CodeGen/SlotIndexes.cpp new file mode 100644 index 0000000..57e35b5 --- /dev/null +++ b/backend/lib/CodeGen/SlotIndexes.cpp @@ -0,0 +1,159 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/SlotIndexes.h" + +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" + +#include +#include + +namespace rcc { + +namespace { +constexpr std::uint64_t SlotSpacing = 16; +constexpr std::uint64_t SlotAlignmentMask = 3; +} // namespace + +SlotIndex +SlotIndexesAnalysis::Result::instructionIndex(const MachineInstr &Instruction) const noexcept { + const auto Position = InstructionSlots.find(Instruction.stableID()); + return Position == InstructionSlots.end() ? SlotIndex{} : Position->second; +} + +SlotIndex SlotIndexesAnalysis::Result::blockStart(const MachineBasicBlock &Block) const noexcept { + const auto Position = BlockStarts.find(&Block); + return Position == BlockStarts.end() ? SlotIndex{} : Position->second; +} + +SlotIndex SlotIndexesAnalysis::Result::blockEnd(const MachineBasicBlock &Block) const noexcept { + const auto Position = BlockEnds.find(&Block); + return Position == BlockEnds.end() ? SlotIndex{} : Position->second; +} + +const MachineInstr * +SlotIndexesAnalysis::Result::instructionFromIndex(SlotIndex Index) const noexcept { + if (!Index.isValid()) + return nullptr; + const auto Position = SlotToInstruction.find(Index.baseIndex().value()); + return Position == SlotToInstruction.end() ? nullptr : Position->second; +} + +const MachineBasicBlock * +SlotIndexesAnalysis::Result::blockFromIndex(SlotIndex Index) const noexcept { + if (!Index.isValid()) + return nullptr; + for (const MachineBasicBlock *Block : BlocksByStart) { + const SlotIndex Start = blockStart(*Block); + const SlotIndex End = blockEnd(*Block); + if (!(Index < Start) && Index < End) + return Block; + } + return nullptr; +} + +Expected SlotIndexesAnalysis::Result::insertInstruction(const MachineInstr &Instruction) { + const MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr || !BlockStarts.contains(Block) || !BlockEnds.contains(Block)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "SlotIndex insertion requires a linked indexed instruction"); + } + if (InstructionSlots.contains(Instruction.stableID())) { + return makeUnexpected(ErrorCode::InvalidArgument, "instruction already has a SlotIndex"); + } + + const MachineInstr *Previous = Instruction.previous(); + const MachineInstr *Next = Instruction.next(); + const SlotIndex LowerIndex = + Previous == nullptr ? blockStart(*Block) : instructionIndex(*Previous); + const SlotIndex UpperIndex = Next == nullptr ? blockEnd(*Block) : instructionIndex(*Next); + if (!LowerIndex.isValid() || !UpperIndex.isValid()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "adjacent instructions are missing SlotIndexes"); + } + const std::uint64_t Lower = LowerIndex.baseIndex().value(); + const std::uint64_t Upper = UpperIndex.baseIndex().value(); + if (Upper <= Lower || Upper - Lower <= SlotAlignmentMask + 1U) { + return makeUnexpected(ErrorCode::Unsupported, + "local SlotIndex space is exhausted; renumbering is required"); + } + std::uint64_t Candidate = ((Lower + Upper) / 2U) & ~SlotAlignmentMask; + if (Candidate <= Lower) + Candidate = Lower + SlotAlignmentMask + 1U; + if (Candidate >= Upper) { + return makeUnexpected(ErrorCode::Unsupported, + "local SlotIndex space is exhausted; renumbering is required"); + } + const SlotIndex Index = SlotIndex::fromValue(Candidate).registerSlot(); + InstructionSlots.emplace(Instruction.stableID(), Index); + SlotToInstruction.emplace(Index.baseIndex().value(), &Instruction); + return {}; +} + +Expected SlotIndexesAnalysis::Result::eraseInstruction(const MachineInstr &Instruction) { + const auto Position = InstructionSlots.find(Instruction.stableID()); + if (Position == InstructionSlots.end()) + return makeUnexpected(ErrorCode::InvalidArgument, "instruction has no SlotIndex"); + SlotToInstruction.erase(Position->second.baseIndex().value()); + InstructionSlots.erase(Position); + return {}; +} + +Expected SlotIndexesAnalysis::Result::renumber(MachineFunction &Function) { + Result NewResult; + std::uint64_t Position = SlotSpacing; + auto Advance = [&Position]() -> Expected { + if (Position > std::numeric_limits::max() - SlotSpacing) { + return makeUnexpected(ErrorCode::Unsupported, "machine SlotIndex space is exhausted"); + } + Position += SlotSpacing; + return {}; + }; + + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + const SlotIndex Start = SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block); + NewResult.BlockStarts.emplace(Block, Start); + NewResult.BlocksByStart.push_back(Block); + auto Advanced = Advance(); + if (!Advanced) + return std::unexpected(Advanced.error()); + + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const SlotIndex Index = SlotIndex::fromValue(Position).registerSlot(); + if (!NewResult.InstructionSlots.emplace(Instruction->stableID(), Index).second || + !NewResult.SlotToInstruction.emplace(Index.baseIndex().value(), Instruction).second) { + return makeUnexpected(ErrorCode::VerificationError, + "duplicate instruction identity during SlotIndex construction"); + } + Advanced = Advance(); + if (!Advanced) + return std::unexpected(Advanced.error()); + } + NewResult.BlockEnds.emplace(Block, + SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block)); + Advanced = Advance(); + if (!Advanced) + return std::unexpected(Advanced.error()); + } + *this = std::move(NewResult); + return {}; +} + +bool SlotIndexesAnalysis::Result::invalidate(const MachineFunction &, + const PreservedAnalyses &Preserved) const noexcept { + return !Preserved.preserves(MachineAnalysisManager::id()); +} + +Expected SlotIndexesAnalysis::run(MachineFunction &Function, + const TargetDescription &, + MachineAnalysisManager &) { + Result ResultValue; + auto Numbered = ResultValue.renumber(Function); + if (!Numbered) + return std::unexpected(Numbered.error()); + return ResultValue; +} + +} // namespace rcc -- cgit v1.2.3