From 495c675771f43cfa12ab7a426a538be72fec1805 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sun, 9 Aug 2026 17:03:19 +0800 Subject: [CodeGen] Implement machine optimization and scheduling --- backend/lib/CodeGen/MachineFinalization.cpp | 217 ++++++++++++++++++++++++++++ 1 file changed, 217 insertions(+) create mode 100644 backend/lib/CodeGen/MachineFinalization.cpp (limited to 'backend/lib/CodeGen/MachineFinalization.cpp') diff --git a/backend/lib/CodeGen/MachineFinalization.cpp b/backend/lib/CodeGen/MachineFinalization.cpp new file mode 100644 index 0000000..8523bb8 --- /dev/null +++ b/backend/lib/CodeGen/MachineFinalization.cpp @@ -0,0 +1,217 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineFinalization.h" + +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/TargetBranchInfo.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include +#include +#include +#include + +namespace rcc { +namespace { + +[[nodiscard]] const MachinePassContract &finalizePseudosContract() { + static const MachinePassContract Contract = [] { + MachinePassContract Value{ + .Name = "finalize-emission-pseudos", + .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs, + MachineFunctionProperty::NoVRegs, MachineFunctionProperty::FrameFinalized, + MachineFunctionProperty::NoFrameIndices}, + .Sets = {MachineFunctionProperty::NoExecutablePseudos}, + .Clears = {}, + .RequiredAnalyses = {}, + .VerificationStage = PipelineStage::Emission, + }; + Value.ThreadSafety = PassThreadSafety::ThreadSafe; + Value.DeclaredChanges = {}; + return Value; + }(); + return Contract; +} + +[[nodiscard]] const MachinePassContract &encodabilityContract() { + static const MachinePassContract Contract = [] { + MachinePassContract Value{ + .Name = "final-encodability-verifier", + .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs, + MachineFunctionProperty::NoVRegs, MachineFunctionProperty::FrameFinalized, + MachineFunctionProperty::NoFrameIndices, + MachineFunctionProperty::NoExecutablePseudos}, + .Sets = {}, + .Clears = {}, + .RequiredAnalyses = {}, + .VerificationStage = PipelineStage::Emission, + }; + Value.ThreadSafety = PassThreadSafety::ThreadSafe; + Value.DeclaredChanges = {}; + return Value; + }(); + return Contract; +} + +[[nodiscard]] Expected alignTo(std::uint64_t Value, std::uint64_t Alignment) { + if (Alignment == 0 || (Alignment & (Alignment - 1U)) != 0) + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final block alignment is not a power of two"); + const std::uint64_t Mask = Alignment - 1U; + if (Value > std::numeric_limits::max() - Mask) + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final machine layout offset overflowed"); + return (Value + Mask) & ~Mask; +} + +[[nodiscard]] Expected displacement(std::uint64_t Source, std::uint64_t Target) { + if (Target >= Source) { + const std::uint64_t Difference = Target - Source; + if (Difference > static_cast(std::numeric_limits::max())) + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final branch displacement overflowed"); + return static_cast(Difference); + } + const std::uint64_t Difference = Source - Target; + if (Difference > static_cast(std::numeric_limits::max())) + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final branch displacement overflowed"); + return -static_cast(Difference); +} + +} // namespace + +const MachinePassContract &FinalizeEmissionPseudosPass::contract() const noexcept { + return finalizePseudosContract(); +} + +Expected FinalizeEmissionPseudosPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &) { + if (!Function.properties().containsAll(contract().Requires)) + return makeUnexpected(ErrorCode::VerificationError, + "emission-pseudo finalization requires finalized allocated MIR"); + for (MachineInstr *Instruction : Function.allInstructions()) { + if (Instruction == nullptr || Instruction->parent() == nullptr) + continue; + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "emission-pseudo finalization encountered an unknown opcode"); + if (!Descriptor->Flags.has(InstructionFlag::Pseudo)) + continue; + const bool NonEmitting = Descriptor->Flags.has(InstructionFlag::Meta) && + !Descriptor->Flags.has(InstructionFlag::ProducesCode); + const bool Terminal = Descriptor->Flags.has(InstructionFlag::TerminalEmission) && + Descriptor->Owner == PseudoOwner::AsmPrinter; + if (!NonEmitting && !Terminal) { + return makeUnexpected(ErrorCode::PseudoExpansionFailed, + "non-terminal executable pseudo survived all expansion owners"); + } + } + MachinePassResult Result; + Result.Preserved = PreservedAnalyses::all(); + return Result; +} + +const MachinePassContract &FinalEncodabilityVerifierPass::contract() const noexcept { + return encodabilityContract(); +} + +Expected FinalEncodabilityVerifierPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &) { + if (!Function.properties().containsAll(contract().Requires)) + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final encodability requires NoExecutablePseudos and finalized MIR"); + + std::unordered_map BlockOffsets; + std::unordered_map InstructionOffsets; + std::uint64_t Offset = 0; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + auto Aligned = alignTo(Offset, Block->attributes().alignment().bytes()); + if (!Aligned) + return std::unexpected(Aligned.error()); + Offset = *Aligned; + BlockOffsets.emplace(Block, Offset); + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final instruction uses an unknown opcode"); + auto InstructionValidation = + Target.validateInstruction(*Instruction, Function.registerInfo()); + if (!InstructionValidation) { + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final instruction is not encodable: " + + std::string(InstructionValidation.error().message())); + } + const bool BundledWithPred = Instruction->flags().has(MachineInstrFlag::BundledWithPred); + const bool BundledWithSucc = Instruction->flags().has(MachineInstrFlag::BundledWithSucc); + if ((BundledWithPred && + (Instruction->previous() == nullptr || + !Instruction->previous()->flags().has(MachineInstrFlag::BundledWithSucc))) || + (BundledWithSucc && + (Instruction->next() == nullptr || + !Instruction->next()->flags().has(MachineInstrFlag::BundledWithPred)))) { + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final instruction has an inconsistent bundle boundary"); + } + for (const MachineOperand &Operand : Instruction->operands()) { + const Register *Reg = Operand.getIf(); + if (Reg != nullptr && !Reg->isNoRegister() && !Reg->isPhysical()) + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final instruction retains a virtual register"); + if (Operand.kind() == MachineOperand::Kind::FrameIndex) + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final instruction retains a frame index"); + } + auto Size = BranchInfo->instructionSize(*Instruction, Function, Target); + if (!Size) + return std::unexpected(Size.error()); + const bool ProducesCode = Descriptor->Flags.has(InstructionFlag::ProducesCode); + if ((ProducesCode && *Size == 0) || + (Descriptor->Flags.has(InstructionFlag::Meta) && *Size != 0)) { + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final instruction violates its exact size contract"); + } + InstructionOffsets.emplace(Instruction, Offset); + if (Offset > std::numeric_limits::max() - *Size) + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final machine function size overflowed"); + Offset += *Size; + } + } + + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + auto TargetBlock = BranchInfo->branchTarget(*Instruction, Function, Target); + if (!TargetBlock) + return std::unexpected(TargetBlock.error()); + if (*TargetBlock == nullptr) + continue; + const auto Source = InstructionOffsets.find(Instruction); + const auto Destination = BlockOffsets.find(*TargetBlock); + if (Source == InstructionOffsets.end() || Destination == BlockOffsets.end()) + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final branch target has no layout offset"); + auto Distance = displacement(Source->second, Destination->second); + if (!Distance) + return std::unexpected(Distance.error()); + if (!BranchInfo->isBranchOffsetInRange(*Instruction, *Distance)) + return makeUnexpected(ErrorCode::FinalEncodabilityFailed, + "final instruction contains an out-of-range branch"); + } + } + MachinePassResult Result; + Result.Preserved = PreservedAnalyses::all(); + return Result; +} + +} // namespace rcc -- cgit v1.2.3