diff options
29 files changed, 4264 insertions, 9 deletions
diff --git a/backend/include/rcc/CodeGen/FrameIndexElimination.h b/backend/include/rcc/CodeGen/FrameIndexElimination.h new file mode 100644 index 0000000..df67479 --- /dev/null +++ b/backend/include/rcc/CodeGen/FrameIndexElimination.h @@ -0,0 +1,22 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_FRAMEINDEXELIMINATION_H +#define RCC_CODEGEN_FRAMEINDEXELIMINATION_H + +#include "rcc/Support/Error.h" + +namespace rcc { + +class MachineFunction; +class RegisterScavenger; +class TargetDescription; +class TargetFrameLowering; + +[[nodiscard]] Expected<bool> eliminateFrameIndices(MachineFunction &Function, + const TargetDescription &Target, + const TargetFrameLowering &FrameLowering, + RegisterScavenger &Scavenger); + +} // namespace rcc + +#endif // RCC_CODEGEN_FRAMEINDEXELIMINATION_H diff --git a/backend/include/rcc/CodeGen/MachineInstr.h b/backend/include/rcc/CodeGen/MachineInstr.h index e7294b4..84d2f0e 100644 --- a/backend/include/rcc/CodeGen/MachineInstr.h +++ b/backend/include/rcc/CodeGen/MachineInstr.h @@ -98,6 +98,8 @@ public: [[nodiscard]] Expected<void> untieOperand(std::size_t Index); [[nodiscard]] Expected<void> addMemOperand(const MachineMemOperand &MemOperand); + [[nodiscard]] Expected<void> replaceMemOperand(std::size_t Index, + const MachineMemOperand &MemOperand); [[nodiscard]] Expected<void> eraseMemOperand(std::size_t Index); [[nodiscard]] std::span<const MachineMemOperand *const> memOperands() const noexcept { return MemOperands; diff --git a/backend/include/rcc/CodeGen/PrologueEpilogueInsertion.h b/backend/include/rcc/CodeGen/PrologueEpilogueInsertion.h new file mode 100644 index 0000000..b94715a --- /dev/null +++ b/backend/include/rcc/CodeGen/PrologueEpilogueInsertion.h @@ -0,0 +1,30 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_PROLOGUEEPILOGUEINSERTION_H +#define RCC_CODEGEN_PROLOGUEEPILOGUEINSERTION_H + +#include "rcc/CodeGen/MachinePass.h" + +namespace rcc { + +class TargetFrameLowering; + +class PrologueEpilogueInsertionPass final : public MachineFunctionPass { +public: + explicit PrologueEpilogueInsertionPass(const TargetFrameLowering &Info) noexcept : Info(&Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected<MachinePassResult> + runImplementation(MachineFunction &Function, const TargetDescription &Target) const; + + const TargetFrameLowering *Info; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_PROLOGUEEPILOGUEINSERTION_H diff --git a/backend/include/rcc/CodeGen/RegisterScavenger.h b/backend/include/rcc/CodeGen/RegisterScavenger.h new file mode 100644 index 0000000..6351b98 --- /dev/null +++ b/backend/include/rcc/CodeGen/RegisterScavenger.h @@ -0,0 +1,42 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_REGISTERSCAVENGER_H +#define RCC_CODEGEN_REGISTERSCAVENGER_H + +#include "rcc/CodeGen/Register.h" +#include "rcc/Support/Error.h" + +#include <span> + +namespace rcc { + +class MachineFunction; +class MachineInstr; +class TargetDescription; + +struct ScavengedRegister final { + PhysicalRegister Reg; + bool RequiresSpill = false; +}; + +class RegisterScavenger final { +public: + RegisterScavenger(const MachineFunction &Function, const TargetDescription &Target) noexcept + : Function(&Function), Target(&Target) {} + + [[nodiscard]] Expected<ScavengedRegister> + scavenge(const MachineInstr &Instruction, std::span<const PhysicalRegister> Candidates) const; + +private: + [[nodiscard]] Expected<bool> isLiveBefore(const MachineInstr &Instruction, + PhysicalRegister Reg) const; + [[nodiscard]] bool instructionUses(const MachineInstr &Instruction, + PhysicalRegister Reg) const noexcept; + + const MachineFunction *Function; + const TargetDescription *Target; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_REGISTERSCAVENGER_H diff --git a/backend/include/rcc/CodeGen/TargetFrameLowering.h b/backend/include/rcc/CodeGen/TargetFrameLowering.h new file mode 100644 index 0000000..1712616 --- /dev/null +++ b/backend/include/rcc/CodeGen/TargetFrameLowering.h @@ -0,0 +1,73 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_TARGETFRAMELOWERING_H +#define RCC_CODEGEN_TARGETFRAMELOWERING_H + +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/Register.h" +#include "rcc/Support/Error.h" + +#include <cstddef> +#include <cstdint> + +namespace rcc { + +class MachineBasicBlock; +class MachineFunction; +class MachineInstr; +class RegisterScavenger; +class TargetDescription; + +struct FrameIndexReference final { + PhysicalRegister BaseRegister; + std::int64_t Offset = 0; +}; + +class TargetFrameLowering { +public: + virtual ~TargetFrameLowering() = default; + + [[nodiscard]] virtual Expected<void> prepareFrame(MachineFunction &Function, + const TargetDescription &Target) const = 0; + [[nodiscard]] virtual Expected<void> + insertCalleeSavedSpillsAndRestores(MachineFunction &Function, + const TargetDescription &Target) const = 0; + [[nodiscard]] virtual Expected<void> + processFunctionBeforeFrameFinalized(MachineFunction &, const TargetDescription &) const { + return {}; + } + [[nodiscard]] virtual Expected<void> finalizeFrame(MachineFunction &Function, + const TargetDescription &Target) const = 0; + + [[nodiscard]] virtual bool isCallFramePseudo(const MachineInstr &Instruction) const noexcept = 0; + [[nodiscard]] virtual Expected<void> + eliminateCallFramePseudo(MachineInstr &Instruction, MachineFunction &Function, + const TargetDescription &Target, RegisterScavenger &Scavenger) const = 0; + + [[nodiscard]] virtual Expected<void> emitPrologue(MachineFunction &Function, + const TargetDescription &Target, + RegisterScavenger &Scavenger) const = 0; + [[nodiscard]] virtual bool + isEpilogueTerminator(const MachineInstr &Instruction, + const TargetDescription &Target) const noexcept = 0; + [[nodiscard]] virtual Expected<void> + emitEpilogue(MachineBasicBlock &Block, MachineInstr &Terminator, MachineFunction &Function, + const TargetDescription &Target, RegisterScavenger &Scavenger) const = 0; + [[nodiscard]] virtual Expected<void> + processFunctionBeforeFrameIndexElimination(MachineFunction &, const TargetDescription &) const { + return {}; + } + + [[nodiscard]] virtual Expected<FrameIndexReference> + getFrameIndexReference(const MachineFunction &Function, const MachineInstr &Instruction, + FrameIndex Index, std::int64_t OperandOffset) const = 0; + [[nodiscard]] virtual Expected<void> eliminateFrameIndex(MachineInstr &Instruction, + std::size_t OperandIndex, + MachineFunction &Function, + const TargetDescription &Target, + RegisterScavenger &Scavenger) const = 0; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_TARGETFRAMELOWERING_H diff --git a/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h index 6e25465..4448933 100644 --- a/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h +++ b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h @@ -51,6 +51,11 @@ public: RegisterClassID) const noexcept { return 1; } + + [[nodiscard]] virtual bool isReservedForFunction(const MachineFunction &, PhysicalRegister, + const TargetDescription &) const noexcept { + return false; + } }; } // namespace rcc diff --git a/backend/include/rcc/Support/Error.h b/backend/include/rcc/Support/Error.h index 81568de..44ff967 100644 --- a/backend/include/rcc/Support/Error.h +++ b/backend/include/rcc/Support/Error.h @@ -19,6 +19,7 @@ enum class ErrorCode : std::uint8_t { RegisterAllocationFailed, IoError, InternalError, + FrameLayoutFailed, }; [[nodiscard]] std::string_view getErrorCodeName(ErrorCode Code) noexcept; diff --git a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h index 403bb2d..0cec77d 100644 --- a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h +++ b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h @@ -4,6 +4,7 @@ #define RCC_TARGET_RISCV_RISCVCODEGEN_H #include "rcc/CodeGen/TargetCodeGen.h" +#include "rcc/CodeGen/TargetFrameLowering.h" #include "rcc/CodeGen/TargetRegisterAllocationInfo.h" namespace rcc::riscv { @@ -13,6 +14,7 @@ namespace rcc::riscv { [[nodiscard]] const TargetInstructionSelector &instructionSelector() noexcept; [[nodiscard]] const TargetSSAInfo &ssaInfo() noexcept; [[nodiscard]] const TargetRegisterAllocationInfo ®isterAllocationInfo() noexcept; +[[nodiscard]] const TargetFrameLowering &frameLowering() noexcept; } // namespace rcc::riscv diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index d6233c2..a8cb952 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -5,6 +5,7 @@ set( CompilationUnit.cpp GenericOpcodes.cpp GenericConstant.cpp + FrameIndexElimination.cpp InstructionDescriptor.cpp LowLevelType.cpp MachineBasicBlockAttributes.cpp @@ -30,6 +31,8 @@ set( MachinePass.cpp MachinePipelinePasses.cpp MachineRegisterInfo.cpp + PrologueEpilogueInsertion.cpp + RegisterScavenger.cpp InlineSpiller.cpp LiveRangeEdit.cpp LiveRegMatrix.cpp @@ -56,6 +59,7 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/CompilationUnit.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GenericOpcodes.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GenericConstant.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/FrameIndexElimination.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/InstructionDescriptor.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineBasicBlockAttributes.h" @@ -80,7 +84,10 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineOperand.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePass.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePipelinePasses.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PrologueEpilogueInsertion.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterScavenger.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetCodeGen.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetFrameLowering.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PBQP/Graph.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PBQP/Math.h" diff --git a/backend/lib/CodeGen/FrameIndexElimination.cpp b/backend/lib/CodeGen/FrameIndexElimination.cpp new file mode 100644 index 0000000..53c64e1 --- /dev/null +++ b/backend/lib/CodeGen/FrameIndexElimination.cpp @@ -0,0 +1,61 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/FrameIndexElimination.h" + +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/RegisterScavenger.h" +#include "rcc/CodeGen/TargetFrameLowering.h" + +#include <cstddef> +#include <utility> + +namespace rcc { + +Expected<bool> eliminateFrameIndices(MachineFunction &Function, const TargetDescription &Target, + const TargetFrameLowering &FrameLowering, + RegisterScavenger &Scavenger) { + bool Changed = false; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;) { + MachineInstr *Next = Instruction->next(); + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + if (Instruction->operandAt(Index)->kind() != MachineOperand::Kind::FrameIndex) + continue; + auto Eliminated = + FrameLowering.eliminateFrameIndex(*Instruction, Index, Function, Target, Scavenger); + if (!Eliminated) + return std::unexpected(Eliminated.error()); + Changed = true; + } + + for (std::size_t Index = 0; Index < Instruction->memOperands().size(); ++Index) { + const MachineMemOperand *Memory = Instruction->memOperands()[Index]; + const auto Frame = Memory->description().Base.frameIndex(); + if (!Frame) + continue; + auto Reference = FrameLowering.getFrameIndexReference(Function, *Instruction, *Frame, + Memory->description().Offset); + if (!Reference) + return std::unexpected(Reference.error()); + MachineMemOperandDesc Description = Memory->description(); + Description.Base = MemoryBase::stack(); + Description.Offset = Reference->Offset; + auto Replacement = Function.createMemOperand(std::move(Description)); + if (!Replacement) + return std::unexpected(Replacement.error()); + auto Replaced = Instruction->replaceMemOperand(Index, **Replacement); + if (!Replaced) + return std::unexpected(Replaced.error()); + Changed = true; + } + Instruction = Next; + } + } + return Changed; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineCompilationStatus.cpp b/backend/lib/CodeGen/MachineCompilationStatus.cpp index 1091b52..765e133 100644 --- a/backend/lib/CodeGen/MachineCompilationStatus.cpp +++ b/backend/lib/CodeGen/MachineCompilationStatus.cpp @@ -43,6 +43,7 @@ isKnownDiagnosticSeverity(MachineCompilationDiagnosticSeverity Severity) noexcep case ErrorCode::VerificationError: case ErrorCode::Unsupported: case ErrorCode::RegisterAllocationFailed: + case ErrorCode::FrameLayoutFailed: case ErrorCode::IoError: case ErrorCode::InternalError: return true; diff --git a/backend/lib/CodeGen/MachineFrameInfo.cpp b/backend/lib/CodeGen/MachineFrameInfo.cpp index a6f7a77..8c3e6e5 100644 --- a/backend/lib/CodeGen/MachineFrameInfo.cpp +++ b/backend/lib/CodeGen/MachineFrameInfo.cpp @@ -330,7 +330,7 @@ Expected<void> MachineFrameInfo::freeze(std::uint64_t Size, Alignment Align) { if (Frozen) return makeUnexpected(ErrorCode::InvalidArgument, "frame layout is already frozen"); for (const StackObject &Object : Objects) { - if (Object.isTombstone() || Object.isVariableSized()) + if (Object.isTombstone() || Object.description()->IsDead || Object.isVariableSized()) continue; if (!Object.description()->Offset) { return makeUnexpected(ErrorCode::VerificationError, @@ -364,7 +364,8 @@ Expected<void> MachineFrameInfo::verify() const { auto DescriptionResult = verifyDescription(*Object.description()); if (!DescriptionResult) return std::unexpected(DescriptionResult.error()); - if (Frozen && !Object.isVariableSized() && !Object.description()->Offset) { + if (Frozen && !Object.description()->IsDead && !Object.isVariableSized() && + !Object.description()->Offset) { return makeUnexpected(ErrorCode::VerificationError, "frozen fixed-size stack object has no final offset"); } diff --git a/backend/lib/CodeGen/MachineInstr.cpp b/backend/lib/CodeGen/MachineInstr.cpp index 7597651..f4602e0 100644 --- a/backend/lib/CodeGen/MachineInstr.cpp +++ b/backend/lib/CodeGen/MachineInstr.cpp @@ -235,6 +235,20 @@ Expected<void> MachineInstr::addMemOperand(const MachineMemOperand &MemOperand) return {}; } +Expected<void> MachineInstr::replaceMemOperand(std::size_t Index, + const MachineMemOperand &MemOperand) { + if (Index >= MemOperands.size()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine memory operand index is out of range"); + } + if (!OwnerFunction->ownsMemOperand(MemOperand)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "replacement memory operand belongs to another function"); + } + MemOperands[Index] = &MemOperand; + return {}; +} + Expected<void> MachineInstr::eraseMemOperand(std::size_t Index) { if (Index >= MemOperands.size()) { return makeUnexpected(ErrorCode::InvalidArgument, diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp index 957213b..be7462b 100644 --- a/backend/lib/CodeGen/MachineVerifier.cpp +++ b/backend/lib/CodeGen/MachineVerifier.cpp @@ -657,6 +657,7 @@ private: for (const MachineMemOperand *MemOperand : Instruction.memOperands()) { const MemoryBase &Base = MemOperand->description().Base; if (const auto Frame = Base.frameIndex()) { + HasFrameIndex = true; auto FrameResult = verifyFrameIndex(*Frame); if (!FrameResult) return FrameResult; @@ -849,6 +850,8 @@ private: (!Has(MachineFunctionProperty::NoVRegs) || !Has(MachineFunctionProperty::NoFrameIndices))) { return fail("FrameFinalized requires NoVRegs and NoFrameIndices"); } + if (Has(MachineFunctionProperty::FrameFinalized) && !Function.frameInfo().isFrozen()) + return fail("FrameFinalized requires a frozen frame layout"); if (Has(MachineFunctionProperty::IsSSA)) { for (const auto &[Reg, DefinitionCount] : VirtualDefCounts) { diff --git a/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp b/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp new file mode 100644 index 0000000..acbcbcf --- /dev/null +++ b/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp @@ -0,0 +1,166 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/PrologueEpilogueInsertion.h" + +#include "rcc/CodeGen/FrameIndexElimination.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineFunctionCloner.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineVerifier.h" +#include "rcc/CodeGen/RegisterScavenger.h" +#include "rcc/CodeGen/TargetFrameLowering.h" + +#include <string> +#include <utility> +#include <vector> + +namespace rcc { +namespace { + +[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) { + Prefix.append(Source.message()); + return Error(Source.code(), std::move(Prefix)); +} + +} // namespace + +const MachinePassContract &PrologueEpilogueInsertionPass::contract() const noexcept { + static const MachinePassContract Contract = [] { + MachinePassContract Value{ + .Name = "PrologueEpilogueInsertion", + .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs, + MachineFunctionProperty::TiedOpsRewritten, MachineFunctionProperty::NoVRegs}, + .Sets = {MachineFunctionProperty::FrameFinalized, MachineFunctionProperty::NoFrameIndices}, + .Clears = {}, + .RequiredAnalyses = {}, + .VerificationStage = PipelineStage::FrameFinalized, + }; + Value.ThreadSafety = PassThreadSafety::ThreadSafe; + Value.DeclaredChanges = {MachinePassChange::Instructions, MachinePassChange::Operands, + MachinePassChange::Registers, MachinePassChange::Frame}; + return Value; + }(); + return Contract; +} + +Expected<MachinePassResult> PrologueEpilogueInsertionPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &) { + if (Info == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, + "PrologueEpilogueInsertion requires target frame lowering"); + const MachineFunctionProperties Missing = contract().Requires.missingFrom(Function.properties()); + if (!Missing.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "PrologueEpilogueInsertion requires properties: " + Missing.toString()); + } + + auto Trial = cloneMachineFunction( + Function, Target, + MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); + if (!Trial) + return std::unexpected(prefixedError(Trial.error(), "frame transaction setup failed: ")); + auto TrialRun = runImplementation(*Trial->ClonedFunction, Target); + if (!TrialRun) + return std::unexpected(prefixedError(TrialRun.error(), "frame transaction rejected input: ")); + auto Transition = Trial->ClonedFunction->properties().applyTransition( + contract().Requires, contract().Sets, contract().Clears); + if (!Transition) { + return std::unexpected( + prefixedError(Transition.error(), "frame transaction property update failed: ")); + } + auto Verified = + MachineVerifier::verify(*Trial->ClonedFunction, Target, + MachineVerifierOptions{.Mode = MachineVerifierMode::Generic, + .Stage = contract().VerificationStage, + .VerifyProperties = true}); + if (!Verified) { + return std::unexpected( + prefixedError(Verified.error(), "frame transaction postcondition failed: ")); + } + + auto Result = runImplementation(Function, Target); + if (!Result) { + return std::unexpected(prefixedError( + Result.error(), "frame lowering diverged after successful transaction preflight: ")); + } + return Result; +} + +Expected<MachinePassResult> +PrologueEpilogueInsertionPass::runImplementation(MachineFunction &Function, + const TargetDescription &Target) const { + auto Prepared = Info->prepareFrame(Function, Target); + if (!Prepared) + return std::unexpected(Prepared.error()); + + RegisterScavenger Scavenger(Function, Target); + std::vector<MachineInstr *> CallFramePseudos; + std::vector<std::pair<MachineBasicBlock *, MachineInstr *>> Epilogues; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (Info->isCallFramePseudo(*Instruction)) + CallFramePseudos.push_back(Instruction); + if (Info->isEpilogueTerminator(*Instruction, Target)) + Epilogues.emplace_back(Block, Instruction); + } + } + for (MachineInstr *Pseudo : CallFramePseudos) { + auto Eliminated = Info->eliminateCallFramePseudo(*Pseudo, Function, Target, Scavenger); + if (!Eliminated) + return std::unexpected(Eliminated.error()); + } + + auto CalleeSaved = Info->insertCalleeSavedSpillsAndRestores(Function, Target); + if (!CalleeSaved) + return std::unexpected(CalleeSaved.error()); + + auto PreFinalized = Info->processFunctionBeforeFrameFinalized(Function, Target); + if (!PreFinalized) + return std::unexpected(PreFinalized.error()); + + auto Finalized = Info->finalizeFrame(Function, Target); + if (!Finalized) + return std::unexpected(Finalized.error()); + if (!Function.frameInfo().isFrozen()) { + return makeUnexpected(ErrorCode::InternalError, + "target frame lowering did not freeze the frame layout"); + } + + auto Prologue = Info->emitPrologue(Function, Target, Scavenger); + if (!Prologue) + return std::unexpected(Prologue.error()); + for (const auto &[Block, Terminator] : Epilogues) { + auto Epilogue = Info->emitEpilogue(*Block, *Terminator, Function, Target, Scavenger); + if (!Epilogue) + return std::unexpected(Epilogue.error()); + } + + auto PreFrameIndices = Info->processFunctionBeforeFrameIndexElimination(Function, Target); + if (!PreFrameIndices) + return std::unexpected(PreFrameIndices.error()); + + auto FrameIndices = eliminateFrameIndices(Function, Target, *Info, Scavenger); + if (!FrameIndices) + return std::unexpected(FrameIndices.error()); + + if (Function.properties().has(MachineFunctionProperty::TracksLiveness)) { + auto Rebuilt = rebuildMachineLiveness(Function, Target); + if (!Rebuilt) + return std::unexpected(Rebuilt.error()); + } + + MachinePassResult Result; + Result.Changed = true; + Result.Changes = {MachinePassChange::Instructions, MachinePassChange::Operands, + MachinePassChange::Registers, MachinePassChange::Frame}; + Result.Preserved = PreservedAnalyses::none(); + return Result; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/RegAllocBasic.cpp b/backend/lib/CodeGen/RegAllocBasic.cpp index 4bb7b23..7f88f25 100644 --- a/backend/lib/CodeGen/RegAllocBasic.cpp +++ b/backend/lib/CodeGen/RegAllocBasic.cpp @@ -42,7 +42,7 @@ private: if (!Marked) return std::unexpected(Marked.error()); } - auto Candidates = regalloc_detail::allocationOrder(Function, Target, VirtualReg); + auto Candidates = regalloc_detail::allocationOrder(Function, Target, TargetInfo, VirtualReg); if (!Candidates) return std::unexpected(Candidates.error()); bool Assigned = false; @@ -105,6 +105,12 @@ Expected<MachinePassResult> BasicAllocatorPass::run(MachineFunction &Function, auto Trial = regalloc_detail::cloneForAllocation(Function, Target); if (!Trial) return std::unexpected(Trial.error()); + const std::vector<PhysicalRegister> FunctionReserved = + regalloc_detail::functionReservedRegisters(Function, Target, *Info); + auto TrialReserved = + regalloc_detail::reserveFunctionRegisters(*Trial->ClonedFunction, FunctionReserved); + if (!TrialReserved) + return std::unexpected(TrialReserved.error()); MachineAnalysisManager TrialAnalyses; auto Registered = registerStage11MachineAnalyses(TrialAnalyses); if (!Registered) @@ -124,6 +130,10 @@ Expected<MachinePassResult> BasicAllocatorPass::run(MachineFunction &Function, return std::unexpected(regalloc_detail::withPrefix( Allocated.error(), "BasicAllocator diverged after a successful transaction preflight: ")); } + auto Reserved = regalloc_detail::reserveFunctionRegisters(Function, FunctionReserved); + if (!Reserved) + return std::unexpected(Reserved.error()); + Allocated->Changed |= *Reserved; return regalloc_detail::passResult(*Allocated); } diff --git a/backend/lib/CodeGen/RegAllocFast.cpp b/backend/lib/CodeGen/RegAllocFast.cpp index 9b087cc..897f217 100644 --- a/backend/lib/CodeGen/RegAllocFast.cpp +++ b/backend/lib/CodeGen/RegAllocFast.cpp @@ -266,7 +266,7 @@ private: return std::unexpected(Evicted.error()); } - auto Candidates = regalloc_detail::allocationOrder(Function, Target, Reg); + auto Candidates = regalloc_detail::allocationOrder(Function, Target, TargetInfo, Reg); if (!Candidates) return std::unexpected(Candidates.error()); for (const PhysicalRegister Candidate : *Candidates) { @@ -319,7 +319,7 @@ private: const Register Reg = *LiveIn.InitialVirtualRegister; if (!Function.registerInfo().isKnownVirtualRegister(Reg)) continue; - auto Candidates = regalloc_detail::allocationOrder(Function, Target, Reg); + auto Candidates = regalloc_detail::allocationOrder(Function, Target, TargetInfo, Reg); if (!Candidates) return std::unexpected(Candidates.error()); if (std::ranges::find(*Candidates, LiveIn.PhysReg) == Candidates->end()) { @@ -577,6 +577,12 @@ Expected<MachinePassResult> FastAllocatorPass::run(MachineFunction &Function, auto Trial = regalloc_detail::cloneForAllocation(Function, Target); if (!Trial) return std::unexpected(Trial.error()); + const std::vector<PhysicalRegister> FunctionReserved = + regalloc_detail::functionReservedRegisters(Function, Target, *Info); + auto TrialReserved = + regalloc_detail::reserveFunctionRegisters(*Trial->ClonedFunction, FunctionReserved); + if (!TrialReserved) + return std::unexpected(TrialReserved.error()); MachineAnalysisManager TrialAnalyses; auto Registered = registerStage11MachineAnalyses(TrialAnalyses); if (!Registered) @@ -602,6 +608,10 @@ Expected<MachinePassResult> FastAllocatorPass::run(MachineFunction &Function, return std::unexpected(regalloc_detail::withPrefix( Allocated.error(), "FastAllocator diverged after a successful transaction preflight: ")); } + auto Reserved = regalloc_detail::reserveFunctionRegisters(Function, FunctionReserved); + if (!Reserved) + return std::unexpected(Reserved.error()); + Allocated->Changed |= *Reserved; return regalloc_detail::passResult(*Allocated); } diff --git a/backend/lib/CodeGen/RegAllocInternal.h b/backend/lib/CodeGen/RegAllocInternal.h index 5d0f434..5cd98e8 100644 --- a/backend/lib/CodeGen/RegAllocInternal.h +++ b/backend/lib/CodeGen/RegAllocInternal.h @@ -16,6 +16,7 @@ #include "rcc/CodeGen/MachineVerifier.h" #include "rcc/CodeGen/RegAllocCommon.h" #include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetRegisterAllocationInfo.h" #include "rcc/CodeGen/TargetRegisterInfo.h" #include "rcc/CodeGen/VirtRegMap.h" @@ -87,7 +88,7 @@ struct AllocationRunResult final { [[nodiscard]] inline Expected<std::vector<PhysicalRegister>> allocationOrder(const MachineFunction &Function, const TargetDescription &Target, - Register VirtualReg) { + const TargetRegisterAllocationInfo &TargetInfo, Register VirtualReg) { auto ClassID = registerClassFor(Function, VirtualReg); if (!ClassID) return std::unexpected(ClassID.error()); @@ -113,11 +114,45 @@ allocationOrder(const MachineFunction &Function, const TargetDescription &Target } std::erase_if(Result, [&](PhysicalRegister Candidate) { return isUnavailablePhysicalRegister(Function, Target.registers(), Candidate) || + TargetInfo.isReservedForFunction(Function, Candidate, Target) || !candidateSupportsSubRegisters(Function, Target.registers(), VirtualReg, Candidate); }); return Result; } +[[nodiscard]] inline std::vector<PhysicalRegister> +functionReservedRegisters(const MachineFunction &Function, const TargetDescription &Target, + const TargetRegisterAllocationInfo &TargetInfo) { + std::vector<PhysicalRegister> Roots; + for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { + if (TargetInfo.isReservedForFunction(Function, Description.Reg, Target)) + Roots.push_back(Description.Reg); + } + std::vector<PhysicalRegister> Result; + for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { + if (std::ranges::any_of(Roots, [&](PhysicalRegister Root) { + return Target.registers().regsOverlap(Description.Reg, Root); + })) { + Result.push_back(Description.Reg); + } + } + return Result; +} + +[[nodiscard]] inline Expected<bool> +reserveFunctionRegisters(MachineFunction &Function, std::span<const PhysicalRegister> Registers) { + bool Changed = false; + for (const PhysicalRegister Reg : Registers) { + if (Function.registerInfo().isReserved(Reg)) + continue; + auto Reserved = Function.registerInfo().reservePhysicalRegister(Reg); + if (!Reserved) + return std::unexpected(Reserved.error()); + Changed = true; + } + return Changed; +} + [[nodiscard]] inline MachineInstr *firstTerminator(MachineBasicBlock &Block, const TargetDescription &Target) noexcept { for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; diff --git a/backend/lib/CodeGen/RegAllocPBQP.cpp b/backend/lib/CodeGen/RegAllocPBQP.cpp index 5e56728..a5a12f7 100644 --- a/backend/lib/CodeGen/RegAllocPBQP.cpp +++ b/backend/lib/CodeGen/RegAllocPBQP.cpp @@ -84,7 +84,7 @@ private: auto ClassID = regalloc_detail::registerClassFor(Function, VirtualReg); if (!ClassID) return std::unexpected(ClassID.error()); - auto Candidates = regalloc_detail::allocationOrder(Function, Target, VirtualReg); + auto Candidates = regalloc_detail::allocationOrder(Function, Target, TargetInfo, VirtualReg); if (!Candidates) return std::unexpected(Candidates.error()); std::erase_if(*Candidates, [&](PhysicalRegister Candidate) { @@ -257,6 +257,12 @@ Expected<MachinePassResult> PBQPAllocatorPass::run(MachineFunction &Function, auto Trial = regalloc_detail::cloneForAllocation(Function, Target); if (!Trial) return std::unexpected(Trial.error()); + const std::vector<PhysicalRegister> FunctionReserved = + regalloc_detail::functionReservedRegisters(Function, Target, *Info); + auto TrialReserved = + regalloc_detail::reserveFunctionRegisters(*Trial->ClonedFunction, FunctionReserved); + if (!TrialReserved) + return std::unexpected(TrialReserved.error()); MachineAnalysisManager TrialAnalyses; auto Registered = registerStage11MachineAnalyses(TrialAnalyses); if (!Registered) @@ -275,6 +281,10 @@ Expected<MachinePassResult> PBQPAllocatorPass::run(MachineFunction &Function, return std::unexpected(regalloc_detail::withPrefix( Allocated.error(), "PBQPAllocator diverged after a successful transaction preflight: ")); } + auto Reserved = regalloc_detail::reserveFunctionRegisters(Function, FunctionReserved); + if (!Reserved) + return std::unexpected(Reserved.error()); + Allocated->Changed |= *Reserved; return regalloc_detail::passResult(*Allocated); } diff --git a/backend/lib/CodeGen/RegisterScavenger.cpp b/backend/lib/CodeGen/RegisterScavenger.cpp new file mode 100644 index 0000000..386c327 --- /dev/null +++ b/backend/lib/CodeGen/RegisterScavenger.cpp @@ -0,0 +1,226 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/RegisterScavenger.h" + +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include <algorithm> +#include <optional> +#include <ranges> +#include <unordered_map> +#include <vector> + +namespace rcc { +namespace { + +[[nodiscard]] std::optional<PhysicalRegister> +physicalRegister(const MachineOperand &Operand) noexcept { + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || !Reg->isPhysical()) + return std::nullopt; + return Reg->physicalRegister(); +} + +[[nodiscard]] bool maskClobbersRegisterUnits(const RegisterMask &Mask, PhysicalRegister Reg, + const TargetDescription &Target) noexcept { + return std::ranges::any_of(Target.registers().physicalRegisters(), + [&](const PhysicalRegisterDesc &Description) { + return Target.registers().regsOverlap(Description.Reg, Reg) && + Mask.clobbers(Description.Reg); + }); +} + +[[nodiscard]] bool maskPreservesRegisterUnits(const RegisterMask &Mask, PhysicalRegister Reg, + const TargetDescription &Target) noexcept { + return std::ranges::any_of(Target.registers().physicalRegisters(), + [&](const PhysicalRegisterDesc &Description) { + return Target.registers().regsOverlap(Description.Reg, Reg) && + Mask.preserves(Description.Reg); + }); +} + +[[nodiscard]] bool isUnavailable(const MachineFunction &Function, const TargetDescription &Target, + PhysicalRegister Reg) noexcept { + const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Reg); + if (Description == nullptr || Description->IsConstant || Description->IsArtificial || + Description->IsReserved || Target.registers().isReservedRegister(Reg)) { + return true; + } + return std::ranges::any_of( + Function.registerInfo().reservedRegisters(), + [&](PhysicalRegister Reserved) { return Target.registers().regsOverlap(Reg, Reserved); }); +} + +} // namespace + +bool RegisterScavenger::instructionUses(const MachineInstr &Instruction, + PhysicalRegister Reg) const noexcept { + for (const MachineOperand &Operand : Instruction.operands()) { + const auto Physical = physicalRegister(Operand); + if (Physical && Target->registers().regsOverlap(*Physical, Reg)) + return true; + } + return false; +} + +Expected<bool> RegisterScavenger::isLiveBefore(const MachineInstr &Instruction, + PhysicalRegister Reg) const { + const MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr || &Instruction.function() != Function || &Block->function() != Function) { + return makeUnexpected(ErrorCode::VerificationError, + "register scavenging anchor is detached or belongs to another function"); + } + + std::vector<const MachineBasicBlock *> Blocks; + std::unordered_map<const MachineBasicBlock *, std::size_t> BlockIndices; + for (const MachineBasicBlock *Current = Function->firstBlock(); Current != nullptr; + Current = Current->next()) { + BlockIndices.emplace(Current, Blocks.size()); + Blocks.push_back(Current); + } + + if (!BlockIndices.contains(Block)) { + return makeUnexpected(ErrorCode::VerificationError, + "register scavenging anchor block is not linked in its function"); + } + for (const MachineBasicBlock *Current : Blocks) { + for (const MachineSuccessor &Successor : Current->successors()) { + if (Successor.Block == nullptr || !BlockIndices.contains(Successor.Block)) { + return makeUnexpected(ErrorCode::VerificationError, + "register scavenging CFG has an unknown successor"); + } + } + for (const MachineInstr *CurrentInstruction = Current->firstInstruction(); + CurrentInstruction != nullptr; CurrentInstruction = CurrentInstruction->next()) { + for (const MachineOperand &Operand : CurrentInstruction->operands()) { + if (const auto *Mask = Operand.getIf<RegisterMaskOperand>(); + Mask != nullptr && !Mask->Mask) { + return makeUnexpected(ErrorCode::VerificationError, + "register scavenging found a null register mask"); + } + if (const auto *Mask = Operand.getIf<LiveOutRegisterMaskOperand>(); + Mask != nullptr && !Mask->Mask) { + return makeUnexpected(ErrorCode::VerificationError, + "register scavenging found a null live-out register mask"); + } + } + } + } + + const auto Transfer = [&](const MachineBasicBlock &Current, bool LiveOut) noexcept { + bool Live = LiveOut; + for (const MachineInstr *CurrentInstruction = Current.lastInstruction(); + CurrentInstruction != nullptr; CurrentInstruction = CurrentInstruction->previous()) { + for (const MachineOperand &Operand : CurrentInstruction->operands()) { + if (const auto *Mask = Operand.getIf<RegisterMaskOperand>(); + Mask != nullptr && maskClobbersRegisterUnits(*Mask->Mask, Reg, *Target)) { + Live = false; + } + const auto Physical = physicalRegister(Operand); + if (Physical && Operand.isDef() && Target->registers().regsOverlap(*Physical, Reg)) { + Live = false; + } + } + for (const MachineOperand &Operand : CurrentInstruction->operands()) { + if (const auto *Mask = Operand.getIf<LiveOutRegisterMaskOperand>(); + Mask != nullptr && maskPreservesRegisterUnits(*Mask->Mask, Reg, *Target)) { + Live = true; + } + const auto Physical = physicalRegister(Operand); + if (Physical && Operand.isUse() && !Operand.isDebugUse() && + !Operand.registerFlags().has(RegisterOperandFlag::Undef) && + Target->registers().regsOverlap(*Physical, Reg)) { + Live = true; + } + } + } + return Live; + }; + + std::vector<bool> LiveIns(Blocks.size(), false); + for (std::size_t Index = 0; Index < Blocks.size(); ++Index) { + for (const MachineBasicBlockLiveIn &LiveIn : Blocks[Index]->liveIns()) { + if (Target->registers().regsOverlap(LiveIn.PhysReg, Reg)) + LiveIns[Index] = true; + } + } + bool Changed = true; + while (Changed) { + Changed = false; + for (std::size_t Reverse = Blocks.size(); Reverse != 0; --Reverse) { + const std::size_t Index = Reverse - 1U; + bool LiveOut = false; + for (const MachineSuccessor &Successor : Blocks[Index]->successors()) { + LiveOut |= LiveIns[BlockIndices.at(Successor.Block)]; + } + const bool NewLiveIn = LiveIns[Index] || Transfer(*Blocks[Index], LiveOut); + if (NewLiveIn != LiveIns[Index]) { + LiveIns[Index] = NewLiveIn; + Changed = true; + } + } + } + + bool Live = false; + for (const MachineSuccessor &Successor : Block->successors()) { + Live |= LiveIns[BlockIndices.at(Successor.Block)]; + } + + for (const MachineInstr *Current = Block->lastInstruction(); Current != nullptr; + Current = Current->previous()) { + for (const MachineOperand &Operand : Current->operands()) { + if (const auto *Mask = Operand.getIf<RegisterMaskOperand>(); + Mask != nullptr && maskClobbersRegisterUnits(*Mask->Mask, Reg, *Target)) { + Live = false; + } + const auto Physical = physicalRegister(Operand); + if (Physical && Operand.isDef() && Target->registers().regsOverlap(*Physical, Reg)) + Live = false; + } + for (const MachineOperand &Operand : Current->operands()) { + if (const auto *Mask = Operand.getIf<LiveOutRegisterMaskOperand>(); + Mask != nullptr && maskPreservesRegisterUnits(*Mask->Mask, Reg, *Target)) { + Live = true; + } + const auto Physical = physicalRegister(Operand); + if (Physical && Operand.isUse() && !Operand.isDebugUse() && + !Operand.registerFlags().has(RegisterOperandFlag::Undef) && + Target->registers().regsOverlap(*Physical, Reg)) + Live = true; + } + if (Current == &Instruction) + return Live; + } + return true; +} + +Expected<ScavengedRegister> +RegisterScavenger::scavenge(const MachineInstr &Instruction, + std::span<const PhysicalRegister> Candidates) const { + std::optional<PhysicalRegister> SpillCandidate; + for (const PhysicalRegister Candidate : Candidates) { + if (!Candidate.isValid() || isUnavailable(*Function, *Target, Candidate) || + instructionUses(Instruction, Candidate)) { + continue; + } + if (!SpillCandidate) + SpillCandidate = Candidate; + auto Live = isLiveBefore(Instruction, Candidate); + if (!Live) + return std::unexpected(Live.error()); + if (!*Live) + return ScavengedRegister{Candidate, false}; + } + if (SpillCandidate) + return ScavengedRegister{*SpillCandidate, true}; + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "register scavenging found no usable physical register"); +} + +} // namespace rcc diff --git a/backend/lib/Support/Error.cpp b/backend/lib/Support/Error.cpp index 817a2bb..f18cc45 100644 --- a/backend/lib/Support/Error.cpp +++ b/backend/lib/Support/Error.cpp @@ -16,6 +16,8 @@ std::string_view getErrorCodeName(ErrorCode Code) noexcept { return "unsupported"; case ErrorCode::RegisterAllocationFailed: return "register allocation failed"; + case ErrorCode::FrameLayoutFailed: + return "frame layout failed"; case ErrorCode::IoError: return "I/O error"; case ErrorCode::InternalError: diff --git a/backend/lib/Target/RISCV/CMakeLists.txt b/backend/lib/Target/RISCV/CMakeLists.txt index 1d9a27a..442e75e 100644 --- a/backend/lib/Target/RISCV/CMakeLists.txt +++ b/backend/lib/Target/RISCV/CMakeLists.txt @@ -49,6 +49,7 @@ add_library( RCCBackendRISCV RISCVCodeGen.cpp RISCVCallLowering.cpp + RISCVFrameLowering.cpp RISCVRegisterAllocation.cpp RISCVTarget.cpp "${RCCBackendRISCVGeneratedRegisterHeader}" @@ -94,6 +95,7 @@ install( rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGen.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLowering.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFrameLowering.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVRegisterAllocation.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVTarget.cpp" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Target/RISCV/RISCVCodeGen.h" @@ -103,6 +105,7 @@ rcc_backend_register_format_files( rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGen.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLowering.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFrameLowering.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVRegisterAllocation.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVTarget.cpp" ) diff --git a/backend/lib/Target/RISCV/RISCVFrameLowering.cpp b/backend/lib/Target/RISCV/RISCVFrameLowering.cpp new file mode 100644 index 0000000..0e6fec9 --- /dev/null +++ b/backend/lib/Target/RISCV/RISCVFrameLowering.cpp @@ -0,0 +1,2019 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFIInfo.h" +#include "rcc/CodeGen/MachineFrameInfo.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/RegisterScavenger.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/Target/RISCV/RISCVCallLowering.h" +#include "rcc/Target/RISCV/RISCVCodeGen.h" +#include "rcc/Target/RISCV/RISCVInstructions.h" +#include "rcc/Target/RISCV/RISCVRegisters.h" +#include "rcc/Target/RISCV/RISCVTarget.h" + +#include <algorithm> +#include <array> +#include <bit> +#include <cstddef> +#include <cstdint> +#include <iterator> +#include <limits> +#include <optional> +#include <ranges> +#include <span> +#include <unordered_set> +#include <utility> +#include <vector> + +namespace rcc::riscv { +namespace { + +constexpr std::uint64_t StackAlignmentBytes = 16; +constexpr std::int64_t MinSigned12 = -2048; +constexpr std::int64_t MaxSigned12 = 2047; +constexpr std::uint8_t DwarfCFAExpression = 0x10U; +constexpr std::uint8_t DwarfOpBaseRegister0 = 0x70U; +constexpr std::uint8_t DwarfOpBaseRegisterExtended = 0x92U; + +[[nodiscard]] constexpr Opcode targetOpcode(InstructionOpcode Value) noexcept { + return Opcode::fromValue(static_cast<std::uint32_t>(Value)); +} + +[[nodiscard]] Expected<PhysicalRegister> physical(PhysicalRegisterID ID) { + return physicalRegister(ID); +} + +[[nodiscard]] constexpr bool fitsSigned12(std::int64_t Value) noexcept { + return Value >= MinSigned12 && Value <= MaxSigned12; +} + +[[nodiscard]] constexpr bool hasStackObjectFlag(const StackObjectDesc &Object, + CallStackObjectFlag Flag) noexcept { + return (Object.TargetFlags & static_cast<std::uint64_t>(Flag)) != 0; +} + +[[nodiscard]] constexpr bool isOutgoingCallObject(const StackObjectDesc &Object) noexcept { + return Object.Kind == StackObjectKind::Target && + (hasStackObjectFlag(Object, CallStackObjectFlag::OutgoingArgument) || + hasStackObjectFlag(Object, CallStackObjectFlag::ByValCopy)); +} + +[[nodiscard]] Expected<std::int64_t> checkedAdd(std::int64_t Left, std::int64_t Right) { + std::int64_t Result = 0; + if (__builtin_add_overflow(Left, Right, &Result)) + return makeUnexpected(ErrorCode::FrameLayoutFailed, "RISC-V frame offset overflows int64"); + return Result; +} + +[[nodiscard]] Expected<std::uint64_t> alignTo(std::uint64_t Value, std::uint64_t Align) { + if (Align == 0 || !std::has_single_bit(Align)) + return makeUnexpected(ErrorCode::InvalidArgument, "RISC-V frame alignment is invalid"); + const std::uint64_t Mask = Align - 1U; + if (Value > std::numeric_limits<std::uint64_t>::max() - Mask) + return makeUnexpected(ErrorCode::FrameLayoutFailed, "RISC-V frame size overflows uint64"); + return (Value + Mask) & ~Mask; +} + +[[nodiscard]] Expected<std::int64_t> immediateValue(const MachineOperand &Operand) { + if (const auto *Immediate = Operand.getIf<std::int64_t>()) + return *Immediate; + const auto *Integer = Operand.getIf<IntegerImmediateOperand>(); + if (Integer == nullptr || Integer->Value.bitWidth() == 0) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V frame operand requires an integer immediate"); + } + if (Integer->Value.bitWidth() > 64) { + return makeUnexpected(ErrorCode::Unsupported, "RISC-V frame immediate must fit in 64 bits"); + } + std::uint64_t Raw = Integer->Value.words().empty() ? 0 : Integer->Value.words().front(); + const std::uint32_t Width = Integer->Value.bitWidth(); + if (Width < 64 && (Raw & (std::uint64_t{1} << (Width - 1U))) != 0) + Raw |= ~std::uint64_t{0} << Width; + return std::bit_cast<std::int64_t>(Raw); +} + +struct CallFrameRequirement final { + std::int64_t Amount = 0; + std::int64_t Alignment = 0; + std::int64_t AlignedAmount = 0; +}; + +[[nodiscard]] Expected<CallFrameRequirement> callFrameRequirement(const MachineInstr &Instruction) { + if (Instruction.operandCount() != 2) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V call-frame pseudo requires exactly amount and alignment"); + } + auto Amount = immediateValue(*Instruction.operandAt(0)); + auto RequestedAlignment = immediateValue(*Instruction.operandAt(1)); + if (!Amount || !RequestedAlignment || *Amount < 0 || *RequestedAlignment <= 0 || + !std::has_single_bit(static_cast<std::uint64_t>(*RequestedAlignment))) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V call-frame amount or alignment is invalid"); + } + const std::uint64_t Alignment = + std::max(StackAlignmentBytes, static_cast<std::uint64_t>(*RequestedAlignment)); + auto Aligned = alignTo(static_cast<std::uint64_t>(*Amount), Alignment); + if (!Aligned || *Aligned > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, "RISC-V call-frame amount is too large"); + } + return CallFrameRequirement{*Amount, *RequestedAlignment, static_cast<std::int64_t>(*Aligned)}; +} + +[[nodiscard]] Expected<std::int64_t> callFrameAmount(const MachineInstr &Instruction) { + auto Requirement = callFrameRequirement(Instruction); + if (!Requirement) + return std::unexpected(Requirement.error()); + return Requirement->AlignedAmount; +} + +[[nodiscard]] bool hasVariableObject(const MachineFunction &Function) noexcept { + return std::ranges::any_of(Function.frameInfo().objects(), [](const StackObject &Object) { + return !Object.isTombstone() && !Object.description()->IsDead && Object.isVariableSized(); + }); +} + +[[nodiscard]] std::uint64_t requiredStackAlignment(const MachineFunction &Function) noexcept { + std::uint64_t Result = StackAlignmentBytes; + Result = + std::max(Result, Function.frameInfo().state().MaxAlignment.value_or(Alignment{}).bytes()); + for (const StackObject &Object : Function.frameInfo().objects()) { + if (!Object.isTombstone() && !Object.description()->IsDead) + Result = std::max(Result, Object.description()->Align.bytes()); + } + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (Instruction->opcode() != targetOpcode(InstructionOpcode::ADJCALLSTACKDOWN) && + Instruction->opcode() != targetOpcode(InstructionOpcode::ADJCALLSTACKUP)) { + continue; + } + if (Instruction->operandCount() < 2) + continue; + auto Requested = immediateValue(*Instruction->operandAt(1)); + if (Requested && *Requested > 0 && + std::has_single_bit(static_cast<std::uint64_t>(*Requested))) { + Result = std::max(Result, static_cast<std::uint64_t>(*Requested)); + } + } + } + return Result; +} + +[[nodiscard]] bool requiresStackRealignment(const MachineFunction &Function) noexcept { + return requiredStackAlignment(Function) > StackAlignmentBytes; +} + +[[nodiscard]] bool requiresFramePointer(const MachineFunction &Function) noexcept { + const MachineFrameState &State = Function.frameInfo().state(); + if (State.IsFrameAddressTaken || State.HasOpaqueSPAdjustment || hasVariableObject(Function) || + requiresStackRealignment(Function)) + return true; + switch (State.FramePointerPolicy) { + case MachineFramePointerPolicy::All: + return true; + case MachineFramePointerPolicy::NonLeaf: + case MachineFramePointerPolicy::NonLeafNoReserve: + return State.HasCalls; + case MachineFramePointerPolicy::None: + case MachineFramePointerPolicy::Reserved: + case MachineFramePointerPolicy::Count: + return false; + } + return false; +} + +[[nodiscard]] bool requiresBasePointer(const MachineFunction &Function) noexcept { + return requiresStackRealignment(Function); +} + +[[nodiscard]] Expected<void> validateFrameRegisterUses(const MachineFunction &Function, + const TargetDescription &Target) { + std::vector<PhysicalRegister> FrameRegisters; + if (requiresFramePointer(Function)) { + auto FP = physical(PhysicalRegisterID::X8); + if (!FP) + return std::unexpected(FP.error()); + FrameRegisters.push_back(*FP); + } + if (requiresBasePointer(Function)) { + auto BP = physical(PhysicalRegisterID::X9); + if (!BP) + return std::unexpected(BP.error()); + FrameRegisters.push_back(*BP); + } + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + for (const MachineOperand &Operand : Instruction->operands()) { + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || !Reg->isPhysical()) + continue; + const auto Physical = Reg->physicalRegister(); + if (Physical && std::ranges::any_of(FrameRegisters, [&](PhysicalRegister FrameReg) { + return Target.registers().regsOverlap(*Physical, FrameReg); + })) { + return makeUnexpected( + ErrorCode::VerificationError, + "RISC-V post-allocation code uses a register reserved for frame lowering"); + } + } + } + } + if (!requiresStackRealignment(Function)) + return {}; + auto OldFPScratch = physical(PhysicalRegisterID::X5); + if (!OldFPScratch) + return std::unexpected(OldFPScratch.error()); + const auto OverlapsScratch = [&](PhysicalRegister Reg) { + return Target.registers().regsOverlap(Reg, *OldFPScratch); + }; + if (std::ranges::any_of(Function.registerInfo().liveIns(), [&](const PhysicalRegisterLiveIn &In) { + return OverlapsScratch(In.PhysReg); + })) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V realignment scratch register is a function live-in"); + } + const MachineBasicBlock *Entry = Function.firstBlock(); + if (Entry == nullptr) + return {}; + if (std::ranges::any_of(Entry->liveIns(), [&](const MachineBasicBlockLiveIn &In) { + return OverlapsScratch(In.PhysReg); + })) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V realignment scratch register is an entry live-in"); + } + bool Defined = false; + for (const MachineInstr *Instruction = Entry->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + for (const MachineOperand &Operand : Instruction->operands()) { + const Register *Reg = Operand.getIf<Register>(); + const auto Physical = + Reg != nullptr && Reg->isPhysical() ? Reg->physicalRegister() : std::nullopt; + if (Physical && OverlapsScratch(*Physical) && Operand.isUse() && !Operand.isDebugUse() && + !Operand.registerFlags().has(RegisterOperandFlag::Undef) && !Defined) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V realignment scratch register is used before its first def"); + } + } + for (const MachineOperand &Operand : Instruction->operands()) { + const Register *Reg = Operand.getIf<Register>(); + const auto Physical = + Reg != nullptr && Reg->isPhysical() ? Reg->physicalRegister() : std::nullopt; + Defined |= Physical && OverlapsScratch(*Physical) && Operand.isDef(); + if (const auto *Mask = Operand.getIf<RegisterMaskOperand>(); + Mask != nullptr && Mask->Mask && Mask->Mask->clobbers(*OldFPScratch)) { + Defined = true; + } + } + } + return {}; +} + +[[nodiscard]] bool hasReservedCallFrame(const MachineFunction &Function) noexcept { + const MachineFrameState &State = Function.frameInfo().state(); + return !hasVariableObject(Function) && !State.HasOpaqueSPAdjustment; +} + +[[nodiscard]] Expected<void> computeMaxCallFrameSize(MachineFunction &Function) { + std::uint64_t Maximum = Function.frameInfo().maxCallFrameSize().value_or(0); + bool SawPseudo = false; + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + std::optional<CallFrameRequirement> Active; + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const bool IsDown = + Instruction->opcode() == targetOpcode(InstructionOpcode::ADJCALLSTACKDOWN); + const bool IsUp = Instruction->opcode() == targetOpcode(InstructionOpcode::ADJCALLSTACKUP); + if (!IsDown && !IsUp) + continue; + SawPseudo = true; + auto Requirement = callFrameRequirement(*Instruction); + if (!Requirement) + return std::unexpected(Requirement.error()); + if (IsDown) { + if (Active) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V call-frame sequences must not be nested"); + } + Active = *Requirement; + Maximum = std::max(Maximum, static_cast<std::uint64_t>(Requirement->AlignedAmount)); + continue; + } + if (!Active) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V call-frame destroy has no matching setup"); + } + if (Active->Amount != Requirement->Amount || Active->Alignment != Requirement->Alignment) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V call-frame setup and destroy requirements differ"); + } + Active.reset(); + } + if (Active) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V call-frame setup has no matching destroy"); + } + } + if (!SawPseudo && !Function.frameInfo().maxCallFrameSize()) + return {}; + return Function.frameInfo().setMaxCallFrameSize(Maximum); +} + +[[nodiscard]] std::array<PhysicalRegisterID, 25> saveOrder() noexcept { + return { + PhysicalRegisterID::X1, PhysicalRegisterID::X8, PhysicalRegisterID::X9, + PhysicalRegisterID::X18, PhysicalRegisterID::X19, PhysicalRegisterID::X20, + PhysicalRegisterID::X21, PhysicalRegisterID::X22, PhysicalRegisterID::X23, + PhysicalRegisterID::X24, PhysicalRegisterID::X25, PhysicalRegisterID::X26, + PhysicalRegisterID::X27, PhysicalRegisterID::F8, PhysicalRegisterID::F9, + PhysicalRegisterID::F18, PhysicalRegisterID::F19, PhysicalRegisterID::F20, + PhysicalRegisterID::F21, PhysicalRegisterID::F22, PhysicalRegisterID::F23, + PhysicalRegisterID::F24, PhysicalRegisterID::F25, PhysicalRegisterID::F26, + PhysicalRegisterID::F27, + }; +} + +[[nodiscard]] Expected<std::vector<PhysicalRegister>> +modifiedCalleeSavedRegisters(const MachineFunction &Function, const TargetDescription &Target) { + std::unordered_set<PhysicalRegister> Modified; + for (const StackObject &Object : Function.frameInfo().objects()) { + if (!Object.isTombstone() && !Object.description()->IsDead && + Object.description()->CalleeSavedRegister) { + Modified.insert(*Object.description()->CalleeSavedRegister); + } + } + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + for (const MachineOperand &Operand : Instruction->operands()) { + if (const auto *Mask = Operand.getIf<RegisterMaskOperand>(); Mask != nullptr) { + if (!Mask->Mask) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V callee-save analysis found a null register mask"); + } + for (const PhysicalRegisterID ID : saveOrder()) { + auto Reg = physical(ID); + if (!Reg) + return std::unexpected(Reg.error()); + if (Mask->Mask->clobbers(*Reg)) + Modified.insert(*Reg); + } + } + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || !Reg->isPhysical() || !Operand.isDef()) + continue; + const auto Physical = Reg->physicalRegister(); + if (Physical) + Modified.insert(*Physical); + } + } + } + + std::vector<PhysicalRegister> Result; + for (const PhysicalRegisterID ID : saveOrder()) { + auto Reg = physical(ID); + if (!Reg) + return std::unexpected(Reg.error()); + if (Modified.contains(*Reg)) + Result.push_back(*Reg); + } + if (requiresFramePointer(Function)) { + auto FP = physical(PhysicalRegisterID::X8); + if (!FP) + return std::unexpected(FP.error()); + if (std::ranges::find(Result, *FP) == Result.end()) { + const auto Position = static_cast<std::vector<PhysicalRegister>::difference_type>( + std::min<std::size_t>(1, Result.size())); + Result.insert(Result.begin() + Position, *FP); + } + } + if (requiresBasePointer(Function)) { + auto BP = physical(PhysicalRegisterID::X9); + if (!BP) + return std::unexpected(BP.error()); + if (std::ranges::find(Result, *BP) == Result.end()) { + const auto Position = static_cast<std::vector<PhysicalRegister>::difference_type>( + std::min<std::size_t>(2, Result.size())); + Result.insert(Result.begin() + Position, *BP); + } + } + for (const PhysicalRegister Reg : Result) { + if (Target.registers().physicalRegister(Reg) == nullptr) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V callee-save register is absent from target facts"); + } + } + return Result; +} + +[[nodiscard]] Expected<const MachineMemOperand *> +createStackMemory(MachineFunction &Function, FrameIndex Index, MemoryAccessFlag Access) { + auto Size = MemorySize::fixed(8); + auto Align = Alignment::create(8); + if (!Size || !Align) + return makeUnexpected(ErrorCode::InternalError, "RISC-V spill facts are invalid"); + MachineMemOperandDesc Description; + Description.Accesses = {Access}; + Description.Size = *Size; + Description.Align = *Align; + Description.Base = MemoryBase::frameIndex(Index); + return Function.createMemOperand(std::move(Description)); +} + +[[nodiscard]] Expected<const MachineMemOperand *> +createResolvedStackMemory(MachineFunction &Function, MemoryAccessFlag Access, std::int64_t Offset) { + auto Size = MemorySize::fixed(8); + auto Align = Alignment::create(8); + if (!Size || !Align) + return makeUnexpected(ErrorCode::InternalError, "RISC-V spill facts are invalid"); + MachineMemOperandDesc Description; + Description.Accesses = {Access}; + Description.Size = *Size; + Description.Align = *Align; + Description.Base = MemoryBase::stack(); + Description.Offset = Offset; + return Function.createMemOperand(std::move(Description)); +} + +[[nodiscard]] Expected<void> replaceImmediate(MachineInstr &Instruction, std::size_t Index, + std::int64_t Value) { + const MachineOperand *Old = Instruction.operandAt(Index); + if (Old == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V frame instruction lacks its offset operand"); + const std::uint32_t TargetFlags = Old->targetFlags(); + auto Erased = Instruction.eraseOperand(Index); + if (!Erased) + return std::unexpected(Erased.error()); + return Instruction.insertOperand(Index, MachineOperand::immediate(Value, TargetFlags)); +} + +[[nodiscard]] Expected<void> replaceWithRegister(MachineInstr &Instruction, std::size_t Index, + PhysicalRegister Reg) { + const MachineOperand *Old = Instruction.operandAt(Index); + if (Old == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V frame instruction lacks its frame operand"); + const std::uint32_t TargetFlags = Old->targetFlags(); + auto Replacement = MachineOperand::registerOperand(Register::fromPhysical(Reg), + {RegisterOperandFlag::Use}, {}, TargetFlags); + if (!Replacement) + return std::unexpected(Replacement.error()); + auto Erased = Instruction.eraseOperand(Index); + if (!Erased) + return std::unexpected(Erased.error()); + return Instruction.insertOperand(Index, std::move(*Replacement)); +} + +[[nodiscard]] Expected<void> setFrameFlag(MachineInstrBuilder &Builder, + std::optional<MachineInstrFlag> Flag) { + if (!Flag) + return {}; + return Builder.setFlags({*Flag}); +} + +[[nodiscard]] Expected<DwarfRegisterNumber> dwarfRegister(const TargetDescription &Target, + PhysicalRegister Reg) { + const auto Number = Target.mirText().dwarfRegister(Reg); + if (!Number) { + return makeUnexpected(ErrorCode::InternalError, "RISC-V frame register has no DWARF mapping"); + } + return DwarfRegisterNumber::fromValue(*Number); +} + +[[nodiscard]] Expected<void> emitCFI(MachineIRBuilder &Builder, MachineCFIInstruction Instruction) { + auto Index = Builder.function().cfiInfo().addInstruction(std::move(Instruction)); + if (!Index) + return std::unexpected(Index.error()); + auto Pending = Builder.buildInstr(rcc::opcode(GenericOpcode::CFI_INSTRUCTION)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addCFIInstruction(*Index); !Result) + return std::unexpected(Result.error()); + auto Built = Pending->build(); + if (!Built) + return std::unexpected(Built.error()); + return {}; +} + +void appendULEB128(std::vector<std::uint8_t> &Bytes, std::uint64_t Value) { + do { + std::uint8_t Byte = static_cast<std::uint8_t>(Value & 0x7FU); + Value >>= 7U; + if (Value != 0) + Byte |= 0x80U; + Bytes.push_back(Byte); + } while (Value != 0); +} + +void appendSLEB128(std::vector<std::uint8_t> &Bytes, std::int64_t Value) { + bool More = true; + while (More) { + std::uint8_t Byte = static_cast<std::uint8_t>(Value & 0x7F); + const bool Sign = (Byte & 0x40U) != 0; + Value >>= 7; + More = (Value != 0 || Sign) && (Value != -1 || !Sign); + if (More) + Byte |= 0x80U; + Bytes.push_back(Byte); + } +} + +[[nodiscard]] Expected<void> +emitSavedRegisterCFI(MachineIRBuilder &Builder, const TargetDescription &Target, + PhysicalRegister Reg, std::int64_t Offset, + std::optional<PhysicalRegister> ExpressionBase = std::nullopt) { + auto DwarfReg = dwarfRegister(Target, Reg); + if (!DwarfReg) + return std::unexpected(DwarfReg.error()); + if (!ExpressionBase) + return emitCFI(Builder, MachineCFIInstruction::offset(*DwarfReg, Offset)); + + auto DwarfBase = dwarfRegister(Target, *ExpressionBase); + if (!DwarfBase) + return std::unexpected(DwarfBase.error()); + std::vector<std::uint8_t> Expression; + if (DwarfBase->value() <= 31U) { + Expression.push_back(static_cast<std::uint8_t>(DwarfOpBaseRegister0 + DwarfBase->value())); + } else { + Expression.push_back(DwarfOpBaseRegisterExtended); + appendULEB128(Expression, DwarfBase->value()); + } + appendSLEB128(Expression, Offset); + + std::vector<std::uint8_t> Escape{DwarfCFAExpression}; + appendULEB128(Escape, DwarfReg->value()); + appendULEB128(Escape, Expression.size()); + Escape.insert(Escape.end(), Expression.begin(), Expression.end()); + auto Rule = MachineCFIInstruction::escape(std::move(Escape)); + if (!Rule) + return std::unexpected(Rule.error()); + return emitCFI(Builder, std::move(*Rule)); +} + +[[nodiscard]] Expected<void> emitRestoreRegisterCFI(MachineIRBuilder &Builder, + const TargetDescription &Target, + PhysicalRegister Reg) { + auto DwarfReg = dwarfRegister(Target, Reg); + if (!DwarfReg) + return std::unexpected(DwarfReg.error()); + return emitCFI(Builder, MachineCFIInstruction::restore(*DwarfReg)); +} + +[[nodiscard]] Expected<void> emitDefCFI(MachineIRBuilder &Builder, const TargetDescription &Target, + PhysicalRegister Reg, std::int64_t Offset) { + auto DwarfReg = dwarfRegister(Target, Reg); + if (!DwarfReg) + return std::unexpected(DwarfReg.error()); + return emitCFI(Builder, MachineCFIInstruction::defCFA(*DwarfReg, Offset)); +} + +[[nodiscard]] Expected<void> emitConstant(MachineIRBuilder &Builder, PhysicalRegister Destination, + PhysicalRegister Zero, std::int64_t Value, + std::optional<MachineInstrFlag> Flag) { + std::uint64_t Remaining = static_cast<std::uint64_t>(Value); + std::vector<std::int64_t> Digits; + while (!fitsSigned12(std::bit_cast<std::int64_t>(Remaining))) { + std::int64_t Digit = static_cast<std::int64_t>(Remaining & 0xFFFU); + if (Digit >= 0x800) + Digit -= 0x1000; + Digits.push_back(Digit); + const std::uint64_t Adjusted = Remaining - static_cast<std::uint64_t>(Digit); + Remaining = Adjusted >> 12U; + if ((Adjusted & (std::uint64_t{1} << 63U)) != 0) + Remaining |= ~std::uint64_t{0} << 52U; + } + + auto Base = Builder.buildInstr(targetOpcode(InstructionOpcode::ADDI)); + if (!Base) + return std::unexpected(Base.error()); + if (auto Result = Base->addDef(Register::fromPhysical(Destination)); !Result) + return std::unexpected(Result.error()); + if (auto Result = Base->addUse(Register::fromPhysical(Zero)); !Result) + return std::unexpected(Result.error()); + if (auto Result = Base->addImmediate(std::bit_cast<std::int64_t>(Remaining)); !Result) + return std::unexpected(Result.error()); + if (auto Result = setFrameFlag(*Base, Flag); !Result) + return std::unexpected(Result.error()); + if (auto Result = Base->build(); !Result) + return std::unexpected(Result.error()); + + for (std::size_t Reverse = Digits.size(); Reverse != 0; --Reverse) { + auto Shift = Builder.buildInstr(targetOpcode(InstructionOpcode::SLLI)); + if (!Shift) + return std::unexpected(Shift.error()); + if (auto Result = Shift->addDef(Register::fromPhysical(Destination)); !Result) + return std::unexpected(Result.error()); + if (auto Result = Shift->addUse(Register::fromPhysical(Destination)); !Result) + return std::unexpected(Result.error()); + if (auto Result = Shift->addImmediate(12); !Result) + return std::unexpected(Result.error()); + if (auto Result = setFrameFlag(*Shift, Flag); !Result) + return std::unexpected(Result.error()); + if (auto Result = Shift->build(); !Result) + return std::unexpected(Result.error()); + + auto Add = Builder.buildInstr(targetOpcode(InstructionOpcode::ADDI)); + if (!Add) + return std::unexpected(Add.error()); + if (auto Result = Add->addDef(Register::fromPhysical(Destination)); !Result) + return std::unexpected(Result.error()); + if (auto Result = Add->addUse(Register::fromPhysical(Destination)); !Result) + return std::unexpected(Result.error()); + if (auto Result = Add->addImmediate(Digits[Reverse - 1U]); !Result) + return std::unexpected(Result.error()); + if (auto Result = setFrameFlag(*Add, Flag); !Result) + return std::unexpected(Result.error()); + if (auto Result = Add->build(); !Result) + return std::unexpected(Result.error()); + } + return {}; +} + +[[nodiscard]] Expected<void> emitRegisterAdd(MachineIRBuilder &Builder, + PhysicalRegister Destination, PhysicalRegister Left, + PhysicalRegister Right, + std::optional<MachineInstrFlag> Flag) { + auto Add = Builder.buildInstr(targetOpcode(InstructionOpcode::ADD)); + if (!Add) + return std::unexpected(Add.error()); + if (auto Result = Add->addDef(Register::fromPhysical(Destination)); !Result) + return std::unexpected(Result.error()); + if (auto Result = Add->addUse(Register::fromPhysical(Left)); !Result) + return std::unexpected(Result.error()); + if (auto Result = Add->addUse(Register::fromPhysical(Right)); !Result) + return std::unexpected(Result.error()); + if (auto Result = setFrameFlag(*Add, Flag); !Result) + return std::unexpected(Result.error()); + auto Built = Add->build(); + if (!Built) + return std::unexpected(Built.error()); + return {}; +} + +[[nodiscard]] Expected<void> emitAddImmediate(MachineIRBuilder &Builder, + PhysicalRegister Destination, PhysicalRegister Source, + std::int64_t Amount, + std::optional<MachineInstrFlag> Flag) { + auto Add = Builder.buildInstr(targetOpcode(InstructionOpcode::ADDI)); + if (!Add) + return std::unexpected(Add.error()); + if (auto Result = Add->addDef(Register::fromPhysical(Destination)); !Result) + return std::unexpected(Result.error()); + if (auto Result = Add->addUse(Register::fromPhysical(Source)); !Result) + return std::unexpected(Result.error()); + if (auto Result = Add->addImmediate(Amount); !Result) + return std::unexpected(Result.error()); + if (auto Result = setFrameFlag(*Add, Flag); !Result) + return std::unexpected(Result.error()); + auto Built = Add->build(); + if (!Built) + return std::unexpected(Built.error()); + return {}; +} + +[[nodiscard]] Expected<void> emitAndImmediate(MachineIRBuilder &Builder, + PhysicalRegister Destination, PhysicalRegister Source, + std::int64_t Amount, + std::optional<MachineInstrFlag> Flag) { + auto And = Builder.buildInstr(targetOpcode(InstructionOpcode::ANDI)); + if (!And) + return std::unexpected(And.error()); + if (auto Result = And->addDef(Register::fromPhysical(Destination)); !Result) + return std::unexpected(Result.error()); + if (auto Result = And->addUse(Register::fromPhysical(Source)); !Result) + return std::unexpected(Result.error()); + if (auto Result = And->addImmediate(Amount); !Result) + return std::unexpected(Result.error()); + if (auto Result = setFrameFlag(*And, Flag); !Result) + return std::unexpected(Result.error()); + auto Built = And->build(); + if (!Built) + return std::unexpected(Built.error()); + return {}; +} + +[[nodiscard]] Expected<void> emitRegisterAnd(MachineIRBuilder &Builder, + PhysicalRegister Destination, PhysicalRegister Left, + PhysicalRegister Right, + std::optional<MachineInstrFlag> Flag) { + auto And = Builder.buildInstr(targetOpcode(InstructionOpcode::AND)); + if (!And) + return std::unexpected(And.error()); + if (auto Result = And->addDef(Register::fromPhysical(Destination)); !Result) + return std::unexpected(Result.error()); + if (auto Result = And->addUse(Register::fromPhysical(Left)); !Result) + return std::unexpected(Result.error()); + if (auto Result = And->addUse(Register::fromPhysical(Right)); !Result) + return std::unexpected(Result.error()); + if (auto Result = setFrameFlag(*And, Flag); !Result) + return std::unexpected(Result.error()); + auto Built = And->build(); + if (!Built) + return std::unexpected(Built.error()); + return {}; +} + +[[nodiscard]] std::array<PhysicalRegisterID, 7> scratchOrder() noexcept { + return {PhysicalRegisterID::X5, PhysicalRegisterID::X6, PhysicalRegisterID::X7, + PhysicalRegisterID::X28, PhysicalRegisterID::X29, PhysicalRegisterID::X30, + PhysicalRegisterID::X31}; +} + +[[nodiscard]] Expected<std::vector<PhysicalRegister>> scratchRegisters() { + std::vector<PhysicalRegister> Result; + for (const PhysicalRegisterID ID : scratchOrder()) { + auto Reg = physical(ID); + if (!Reg) + return std::unexpected(Reg.error()); + Result.push_back(*Reg); + } + return Result; +} + +[[nodiscard]] const StackObject *emergencyObject(const MachineFunction &Function) noexcept { + for (const StackObject &Object : Function.frameInfo().objects()) { + if (!Object.isTombstone() && !Object.description()->IsDead && + Object.description()->Kind == StackObjectKind::EmergencySpill) + return &Object; + } + return nullptr; +} + +[[nodiscard]] Expected<FrameIndex> createEmergencyObject(MachineFunction &Function) { + auto Align = Alignment::create(8); + if (!Align) + return std::unexpected(Align.error()); + StackObjectDesc Description; + Description.Kind = StackObjectKind::EmergencySpill; + Description.Size = 8; + Description.Align = *Align; + return Function.frameInfo().createObject(std::move(Description)); +} + +[[nodiscard]] Expected<std::uint64_t> layoutFrame(MachineFunction &Function, bool HasFP, + bool ReserveCallFrame) { + MachineFrameInfo &Frame = Function.frameInfo(); + const std::uint64_t CallFrame = ReserveCallFrame ? Frame.maxCallFrameSize().value_or(0) : 0; + auto Initial = alignTo(CallFrame, StackAlignmentBytes); + if (!Initial) + return std::unexpected(Initial.error()); + std::uint64_t Cursor = *Initial; + + std::vector<const StackObject *> Specials; + std::vector<const StackObject *> Locals; + std::vector<const StackObject *> PreallocatedLocals; + std::uint64_t LocalBlobSize = Frame.state().LocalFrameSize; + std::uint64_t LocalBlobAlignment = 1; + std::uint64_t MaximumAlignment = requiredStackAlignment(Function); + for (const StackObject &Object : Frame.objects()) { + if (Object.isTombstone() || Object.description()->IsDead) + continue; + const StackObjectDesc &Description = *Object.description(); + if (Description.Stack != StackID::defaultStack()) { + return makeUnexpected(ErrorCode::Unsupported, + "RV64GC does not support non-default stack IDs"); + } + MaximumAlignment = std::max(MaximumAlignment, Description.Align.bytes()); + if (Object.isVariableSized()) + continue; + if (Description.LocalOffset) { + if (*Description.LocalOffset < 0 || + static_cast<std::uint64_t>(*Description.LocalOffset) % Description.Align.bytes() != 0) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, + "RISC-V local stack object has an invalid offset"); + } + const std::uint64_t Offset = static_cast<std::uint64_t>(*Description.LocalOffset); + if (Description.Size.value_or(0) > std::numeric_limits<std::uint64_t>::max() - Offset) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, + "RISC-V local stack object range overflows"); + } + const std::uint64_t End = Offset + Description.Size.value_or(0); + if (isOutgoingCallObject(Description)) { + if (!Frame.maxCallFrameSize() || End > *Frame.maxCallFrameSize()) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, + "RISC-V outgoing stack object exceeds the call frame"); + } + } else { + LocalBlobSize = std::max(LocalBlobSize, End); + LocalBlobAlignment = std::max(LocalBlobAlignment, Description.Align.bytes()); + PreallocatedLocals.push_back(&Object); + } + continue; + } + if (Object.isFixed()) + continue; + if (Description.Kind == StackObjectKind::CalleeSaved || + Description.Kind == StackObjectKind::EmergencySpill) { + Specials.push_back(&Object); + } else { + Locals.push_back(&Object); + } + } + const auto Order = [](const StackObject *Left, const StackObject *Right) { + const StackObjectDesc &L = *Left->description(); + const StackObjectDesc &R = *Right->description(); + if (L.Align.bytes() != R.Align.bytes()) + return L.Align.bytes() > R.Align.bytes(); + if (L.Size != R.Size) + return L.Size.value_or(0) > R.Size.value_or(0); + return Left->index().value() < Right->index().value(); + }; + std::ranges::sort(Locals, Order); + std::ranges::sort(Specials, Order); + std::ranges::sort(PreallocatedLocals, [](const StackObject *Left, const StackObject *Right) { + return Left->index().value() < Right->index().value(); + }); + + const auto Place = [&](std::span<const StackObject *const> Objects) -> Expected<void> { + for (const StackObject *Object : Objects) { + const StackObjectDesc &Description = *Object->description(); + auto Aligned = alignTo(Cursor, Description.Align.bytes()); + if (!Aligned) + return std::unexpected(Aligned.error()); + Cursor = *Aligned; + if (Cursor > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, + "RISC-V frame offset exceeds signed 64-bit range"); + } + auto Set = Frame.setObjectOffset(Object->index(), static_cast<std::int64_t>(Cursor)); + if (!Set) + return std::unexpected(Set.error()); + if (Description.Size.value_or(0) > std::numeric_limits<std::uint64_t>::max() - Cursor) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, "RISC-V frame size overflows uint64"); + } + Cursor += Description.Size.value_or(0); + } + return {}; + }; + + const auto PlacePreallocated = [&]() -> Expected<void> { + if (LocalBlobSize == 0) + return {}; + auto Aligned = alignTo(Cursor, LocalBlobAlignment); + if (!Aligned) + return std::unexpected(Aligned.error()); + const std::uint64_t BlobStart = *Aligned; + for (const StackObject *Object : PreallocatedLocals) { + const std::uint64_t LocalOffset = + static_cast<std::uint64_t>(*Object->description()->LocalOffset); + if (BlobStart > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()) || + LocalOffset > + static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()) - BlobStart) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, + "RISC-V local frame offset exceeds int64"); + } + auto Set = Frame.setObjectOffset(Object->index(), + static_cast<std::int64_t>(BlobStart + LocalOffset)); + if (!Set) + return std::unexpected(Set.error()); + } + if (LocalBlobSize > std::numeric_limits<std::uint64_t>::max() - BlobStart) + return makeUnexpected(ErrorCode::FrameLayoutFailed, + "RISC-V local frame size overflows uint64"); + Cursor = BlobStart + LocalBlobSize; + return {}; + }; + + if (!HasFP || requiresStackRealignment(Function)) { + auto Placed = Place(Specials); + if (!Placed) + return std::unexpected(Placed.error()); + } + auto PlacedLocals = Place(Locals); + if (!PlacedLocals) + return std::unexpected(PlacedLocals.error()); + auto PlacedPreallocated = PlacePreallocated(); + if (!PlacedPreallocated) + return std::unexpected(PlacedPreallocated.error()); + if (HasFP && !requiresStackRealignment(Function)) { + auto Placed = Place(Specials); + if (!Placed) + return std::unexpected(Placed.error()); + } + + for (const StackObject &Object : Frame.objects()) { + if (Object.isTombstone() || Object.description()->IsDead || Object.isVariableSized()) + continue; + const StackObjectDesc &Description = *Object.description(); + if (Description.LocalOffset && isOutgoingCallObject(Description)) { + auto Set = Frame.setObjectOffset(Object.index(), *Description.LocalOffset); + if (!Set) + return std::unexpected(Set.error()); + } + } + if (LocalBlobSize > std::numeric_limits<std::uint32_t>::max()) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, + "RISC-V local frame blob exceeds MIR limits"); + } + MachineFrameState State = Frame.state(); + State.LocalFrameSize = static_cast<std::uint32_t>(LocalBlobSize); + auto UpdatedState = Frame.setState(std::move(State)); + if (!UpdatedState) + return std::unexpected(UpdatedState.error()); + auto FinalSize = alignTo(Cursor, MaximumAlignment); + if (!FinalSize) + return std::unexpected(FinalSize.error()); + if (*FinalSize > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, + "RISC-V frame size exceeds signed 64-bit range"); + } + return *FinalSize; +} + +[[nodiscard]] Expected<std::int64_t> objectReferenceOffset(const MachineFunction &Function, + const MachineInstr &Instruction, + const StackObjectDesc &Object, + std::int64_t OperandOffset) { + if (!Object.Offset) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V FrameIndex references an object without a final offset"); + const bool HasFP = requiresFramePointer(Function); + std::int64_t BaseOffset = *Object.Offset; + if (Object.LocalOffset && isOutgoingCallObject(Object)) + BaseOffset = *Object.LocalOffset; + else if (Object.Kind == StackObjectKind::FixedABI || + Object.Kind == StackObjectKind::FixedSpillSlot) { + if (!HasFP) { + if (Function.frameInfo().state().StackSize > + static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, + "RISC-V stack size exceeds signed 64-bit range"); + } + auto Added = + checkedAdd(BaseOffset, static_cast<std::int64_t>(Function.frameInfo().state().StackSize)); + if (!Added) + return std::unexpected(Added.error()); + BaseOffset = *Added; + } + } else if (!requiresStackRealignment(Function) && HasFP && + !Instruction.flags().has(MachineInstrFlag::FrameSetup)) { + if (Function.frameInfo().state().StackSize > + static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, + "RISC-V stack size exceeds signed 64-bit range"); + } + auto Added = + checkedAdd(BaseOffset, -static_cast<std::int64_t>(Function.frameInfo().state().StackSize)); + if (!Added) + return std::unexpected(Added.error()); + BaseOffset = *Added; + } + return checkedAdd(BaseOffset, OperandOffset); +} + +[[nodiscard]] Expected<FrameIndexReference> emergencyFrameReference(const MachineFunction &Function, + const StackObjectDesc &Object) { + if (!Object.Offset) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V emergency spill object has no final offset"); + } + PhysicalRegisterID BaseID = PhysicalRegisterID::X2; + std::int64_t Offset = *Object.Offset; + if (requiresBasePointer(Function)) { + BaseID = PhysicalRegisterID::X9; + } else if (requiresFramePointer(Function)) { + BaseID = PhysicalRegisterID::X8; + if (Function.frameInfo().state().StackSize > + static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, + "RISC-V stack size exceeds signed 64-bit range"); + } + auto Adjusted = + checkedAdd(Offset, -static_cast<std::int64_t>(Function.frameInfo().state().StackSize)); + if (!Adjusted) + return std::unexpected(Adjusted.error()); + Offset = *Adjusted; + } + auto Base = physical(BaseID); + if (!Base) + return std::unexpected(Base.error()); + return FrameIndexReference{*Base, Offset}; +} + +[[nodiscard]] Expected<MachineInstr *> +emitCalleeSave(MachineIRBuilder &Builder, PhysicalRegister Reg, FrameIndex Index, bool Restore) { + const bool IsFPR = Reg.number() >= static_cast<std::uint32_t>(PhysicalRegisterID::F0); + const InstructionOpcode OpcodeValue = + Restore ? (IsFPR ? InstructionOpcode::FLD : InstructionOpcode::LD) + : (IsFPR ? InstructionOpcode::FSD : InstructionOpcode::SD); + auto Memory = createStackMemory(Builder.function(), Index, + Restore ? MemoryAccessFlag::Load : MemoryAccessFlag::Store); + if (!Memory) + return std::unexpected(Memory.error()); + auto Pending = Builder.buildInstr(targetOpcode(OpcodeValue)); + if (!Pending) + return std::unexpected(Pending.error()); + const Register Value = Register::fromPhysical(Reg); + auto RegisterResult = Restore ? Pending->addDef(Value) : Pending->addUse(Value); + if (!RegisterResult) + return std::unexpected(RegisterResult.error()); + if (auto Result = Pending->addFrameIndex(Index); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addImmediate(0); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addMemOperand(**Memory); !Result) + return std::unexpected(Result.error()); + if (auto Result = setFrameFlag(*Pending, Restore ? MachineInstrFlag::FrameDestroy + : MachineInstrFlag::FrameSetup); + !Result) { + return std::unexpected(Result.error()); + } + auto Built = Pending->build(); + if (!Built) + return std::unexpected(Built.error()); + return *Built; +} + +[[nodiscard]] std::optional<FrameIndex> calleeSaveSlot(const MachineFunction &Function, + PhysicalRegister Reg) noexcept { + for (const StackObject &Object : Function.frameInfo().objects()) { + if (Object.isTombstone() || Object.description()->IsDead) + continue; + if (Object.description()->CalleeSavedRegister == Reg) + return Object.index(); + } + return std::nullopt; +} + +[[nodiscard]] bool isABIStackSaveRegister(PhysicalRegister Reg) { + return std::ranges::any_of(saveOrder(), [Reg](PhysicalRegisterID ID) { + auto Candidate = physical(ID); + return Candidate && *Candidate == Reg; + }); +} + +[[nodiscard]] Expected<void> +validateCalleeSaveObjects(const MachineFunction &Function, + std::span<const PhysicalRegister> SavedRegisters) { + std::unordered_set<PhysicalRegister> Slots; + for (const StackObject &Object : Function.frameInfo().objects()) { + if (Object.isTombstone() || Object.description()->IsDead || + !Object.description()->CalleeSavedRegister) { + continue; + } + const StackObjectDesc &Description = *Object.description(); + const PhysicalRegister Reg = *Description.CalleeSavedRegister; + if (!isABIStackSaveRegister(Reg)) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V callee-save object names a caller-saved register"); + } + if (Description.Kind != StackObjectKind::CalleeSaved || + Description.Size != std::optional<std::uint64_t>{8} || Description.Align.bytes() < 8 || + Description.Stack != StackID::defaultStack()) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V callee-save object has an invalid kind, size, or alignment"); + } + if (!Slots.insert(Reg).second) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V callee-save register has duplicate stack objects"); + } + if (std::ranges::find(SavedRegisters, Reg) == SavedRegisters.end()) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V callee-save object was omitted from save analysis"); + } + } + return {}; +} + +[[nodiscard]] bool calleeSaveIsRestored(const MachineFunction &Function, + PhysicalRegister Reg) noexcept { + const auto Slot = calleeSaveSlot(Function, Reg); + const StackObject *Object = Slot ? Function.frameInfo().object(*Slot) : nullptr; + return Object != nullptr && Object->description()->CalleeSavedRestored; +} + +struct CalleeSaveOperation final { + MachineInstr *Instruction = nullptr; + PhysicalRegister Reg; +}; + +[[nodiscard]] std::vector<CalleeSaveOperation> +calleeSaveOperations(MachineBasicBlock &Block, const MachineFunction &Function, bool Restore) { + std::vector<CalleeSaveOperation> Result; + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (!Instruction->flags().has(Restore ? MachineInstrFlag::FrameDestroy + : MachineInstrFlag::FrameSetup)) { + continue; + } + for (const MachineOperand &Operand : Instruction->operands()) { + const auto *Frame = Operand.getIf<FrameIndexOperand>(); + if (Frame == nullptr) + continue; + const StackObject *Object = Function.frameInfo().object(Frame->Index); + if (Object != nullptr && Object->description()->CalleeSavedRegister) { + Result.push_back( + CalleeSaveOperation{Instruction, *Object->description()->CalleeSavedRegister}); + break; + } + } + } + return Result; +} + +class RISCVFrameLowering final : public TargetFrameLowering { +public: + [[nodiscard]] Expected<void> prepareFrame(MachineFunction &Function, + const TargetDescription &Target) const override { + MachineFrameInfo &Frame = Function.frameInfo(); + if (Frame.isFrozen()) + return makeUnexpected(ErrorCode::InvalidArgument, "RISC-V frame layout is already frozen"); + + MachineFrameState State = Frame.state(); + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = + Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Call)) + State.HasCalls = true; + } + } + auto UpdatedState = Frame.setState(State); + if (!UpdatedState) + return std::unexpected(UpdatedState.error()); + + auto CallFrame = computeMaxCallFrameSize(Function); + if (!CallFrame) + return std::unexpected(CallFrame.error()); + auto FrameRegisters = validateFrameRegisterUses(Function, Target); + if (!FrameRegisters) + return std::unexpected(FrameRegisters.error()); + + auto SavedRegisters = modifiedCalleeSavedRegisters(Function, Target); + if (!SavedRegisters) + return std::unexpected(SavedRegisters.error()); + auto ExistingSlots = validateCalleeSaveObjects(Function, *SavedRegisters); + if (!ExistingSlots) + return std::unexpected(ExistingSlots.error()); + auto Align8 = Alignment::create(8); + if (!Align8) + return std::unexpected(Align8.error()); + for (const PhysicalRegister Reg : *SavedRegisters) { + if (calleeSaveSlot(Function, Reg)) + continue; + StackObjectDesc Description; + Description.Kind = StackObjectKind::CalleeSaved; + Description.Size = 8; + Description.Align = *Align8; + Description.CalleeSavedRegister = Reg; + auto Created = Frame.createObject(std::move(Description)); + if (!Created) + return std::unexpected(Created.error()); + } + auto CompleteSlots = validateCalleeSaveObjects(Function, *SavedRegisters); + if (!CompleteSlots) + return std::unexpected(CompleteSlots.error()); + + const bool HasFP = requiresFramePointer(Function); + const bool ReserveCallFrame = hasReservedCallFrame(Function); + auto StackSize = layoutFrame(Function, HasFP, ReserveCallFrame); + if (!StackSize) + return std::unexpected(StackSize.error()); + + State = Frame.state(); + State.StackSize = *StackSize; + auto RequiredAlignment = Alignment::create(requiredStackAlignment(Function)); + if (!RequiredAlignment) + return std::unexpected(RequiredAlignment.error()); + State.MaxAlignment = *RequiredAlignment; + auto StateForReferences = Frame.setState(State); + if (!StateForReferences) + return std::unexpected(StateForReferences.error()); + + bool NeedsEmergency = false; + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (isCallFramePseudo(*Instruction)) { + auto Amount = callFrameAmount(*Instruction); + if (!Amount) + return std::unexpected(Amount.error()); + NeedsEmergency |= !ReserveCallFrame && !fitsSigned12(*Amount); + } + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + const auto *FrameOperand = Instruction->operandAt(Index)->getIf<FrameIndexOperand>(); + if (FrameOperand == nullptr) + continue; + std::int64_t Extra = FrameOperand->Offset; + if (Index + 1U >= Instruction->operandCount()) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V frame operand lacks an adjacent immediate"); + } + auto Immediate = immediateValue(*Instruction->operandAt(Index + 1U)); + if (!Immediate) + return std::unexpected(Immediate.error()); + auto Added = checkedAdd(Extra, *Immediate); + if (!Added) + return std::unexpected(Added.error()); + Extra = *Added; + const StackObject *Object = Frame.object(FrameOperand->Index); + if (Object == nullptr || Object->description()->IsDead) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V frame instruction references an invalid object"); + auto Offset = + objectReferenceOffset(Function, *Instruction, *Object->description(), Extra); + if (!Offset) + return std::unexpected(Offset.error()); + NeedsEmergency |= !fitsSigned12(*Offset); + } + } + } + if (NeedsEmergency && emergencyObject(Function) == nullptr) { + auto Emergency = createEmergencyObject(Function); + if (!Emergency) + return std::unexpected(Emergency.error()); + StackSize = layoutFrame(Function, HasFP, ReserveCallFrame); + if (!StackSize) + return std::unexpected(StackSize.error()); + } + + State = Frame.state(); + State.StackSize = *StackSize; + State.AdjustsStack = State.AdjustsStack || *StackSize != 0; + State.IsCalleeSavedInfoValid = true; + State.SavePoints.clear(); + State.RestorePoints.clear(); + if (!SavedRegisters->empty() && Function.firstBlock() != nullptr) { + State.SavePoints.push_back( + MachineFrameSaveRestorePoint{Function.firstBlock()->stableID(), *SavedRegisters}); + } + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + bool HasEpilogue = false; + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + HasEpilogue |= isEpilogueTerminator(*Instruction, Target); + } + if (HasEpilogue && !SavedRegisters->empty()) { + std::vector<PhysicalRegister> Restored; + std::ranges::copy_if( + *SavedRegisters, std::back_inserter(Restored), + [&Function](PhysicalRegister Reg) { return calleeSaveIsRestored(Function, Reg); }); + if (!Restored.empty()) { + State.RestorePoints.push_back( + MachineFrameSaveRestorePoint{Block->stableID(), std::move(Restored)}); + } + } + } + auto SetState = Frame.setState(std::move(State)); + if (!SetState) + return std::unexpected(SetState.error()); + auto Records = Function.records().setCalleeSavedRegisters(*SavedRegisters); + if (!Records) + return std::unexpected(Records.error()); + return {}; + } + + [[nodiscard]] Expected<void> + insertCalleeSavedSpillsAndRestores(MachineFunction &Function, + const TargetDescription &Target) const override { + if (Function.frameInfo().isFrozen()) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V callee saves must be inserted before frame freeze"); + } + const std::span<const PhysicalRegister> Saved = Function.records().calleeSavedRegisters(); + if (Saved.empty()) + return {}; + MachineBasicBlock *Entry = Function.firstBlock(); + if (Entry == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V callee-save frame has no entry block"); + } + auto FP = physical(PhysicalRegisterID::X8); + auto BP = physical(PhysicalRegisterID::X9); + auto OldFP = physical(PhysicalRegisterID::X5); + if (!FP || !BP || !OldFP) + return makeUnexpected(ErrorCode::InternalError, "RISC-V frame registers are unavailable"); + const bool Realign = requiresStackRealignment(Function); + + MachineIRBuilder SaveBuilder(Function, Target); + auto SavePoint = Entry->firstInstruction() != nullptr + ? SaveBuilder.setInsertPointBefore(*Entry->firstInstruction()) + : SaveBuilder.setInsertPoint(*Entry); + if (!SavePoint) + return std::unexpected(SavePoint.error()); + for (const PhysicalRegister Reg : Saved) { + const auto Slot = calleeSaveSlot(Function, Reg); + if (!Slot) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V callee-save register has no stack slot"); + } + const PhysicalRegister Value = Realign && Reg == *FP ? *OldFP : Reg; + auto Stored = emitCalleeSave(SaveBuilder, Value, *Slot, false); + if (!Stored) + return std::unexpected(Stored.error()); + } + + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + std::vector<MachineInstr *> Terminators; + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (isEpilogueTerminator(*Instruction, Target)) + Terminators.push_back(Instruction); + } + for (MachineInstr *Terminator : Terminators) { + MachineIRBuilder RestoreBuilder(Function, Target); + auto Point = RestoreBuilder.setInsertPointBefore(*Terminator); + if (!Point) + return std::unexpected(Point.error()); + const auto EmitRestore = [&](PhysicalRegister Reg) -> Expected<void> { + if (!calleeSaveIsRestored(Function, Reg)) + return {}; + const auto Slot = calleeSaveSlot(Function, Reg); + if (!Slot) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V callee-save register has no restore slot"); + } + auto Loaded = emitCalleeSave(RestoreBuilder, Reg, *Slot, true); + if (!Loaded) + return std::unexpected(Loaded.error()); + return {}; + }; + for (const PhysicalRegister Reg : Saved) { + if ((requiresFramePointer(Function) && Reg == *FP) || (Realign && Reg == *BP)) + continue; + auto Loaded = EmitRestore(Reg); + if (!Loaded) + return std::unexpected(Loaded.error()); + } + if (requiresFramePointer(Function)) { + auto Loaded = EmitRestore(*FP); + if (!Loaded) + return std::unexpected(Loaded.error()); + } + if (Realign) { + auto Loaded = EmitRestore(*BP); + if (!Loaded) + return std::unexpected(Loaded.error()); + } + } + } + return {}; + } + + [[nodiscard]] Expected<void> finalizeFrame(MachineFunction &Function, + const TargetDescription &) const override { + MachineFrameInfo &Frame = Function.frameInfo(); + if (Frame.isFrozen()) + return makeUnexpected(ErrorCode::InternalError, + "RISC-V frame was frozen before final layout"); + std::vector<std::optional<std::int64_t>> PreliminaryOffsets; + PreliminaryOffsets.reserve(Frame.objects().size()); + for (const StackObject &Object : Frame.objects()) { + PreliminaryOffsets.push_back(Object.isTombstone() ? std::nullopt + : Object.description()->Offset); + } + const std::uint64_t PreliminarySize = Frame.state().StackSize; + auto StackSize = + layoutFrame(Function, requiresFramePointer(Function), hasReservedCallFrame(Function)); + if (!StackSize) + return std::unexpected(StackSize.error()); + if (*StackSize != PreliminarySize || Frame.objects().size() != PreliminaryOffsets.size()) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V frame resources changed after preliminary layout"); + } + for (const StackObject &Object : Frame.objects()) { + if (!Object.isTombstone() && + Object.description()->Offset != PreliminaryOffsets[Object.index().value()]) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V frame offsets changed after callee-save insertion"); + } + } + auto StackAlignment = Alignment::create(requiredStackAlignment(Function)); + if (!StackAlignment) + return std::unexpected(StackAlignment.error()); + return Frame.freeze(*StackSize, *StackAlignment); + } + + [[nodiscard]] bool isCallFramePseudo(const MachineInstr &Instruction) const noexcept override { + return Instruction.opcode() == targetOpcode(InstructionOpcode::ADJCALLSTACKDOWN) || + Instruction.opcode() == targetOpcode(InstructionOpcode::ADJCALLSTACKUP); + } + + [[nodiscard]] Expected<void> + eliminateCallFramePseudo(MachineInstr &Instruction, MachineFunction &Function, + const TargetDescription &Target, + RegisterScavenger &Scavenger) const override { + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::VerificationError, "RISC-V call-frame pseudo is detached"); + if (!hasReservedCallFrame(Function)) { + auto Amount = callFrameAmount(Instruction); + if (!Amount) + return std::unexpected(Amount.error()); + std::int64_t Adjustment = *Amount; + if (Instruction.opcode() == targetOpcode(InstructionOpcode::ADJCALLSTACKDOWN)) + Adjustment = -Adjustment; + auto Adjusted = emitStackAdjustment(Instruction, Function, Target, Scavenger, Adjustment, + Adjustment < 0 ? MachineInstrFlag::FrameSetup + : MachineInstrFlag::FrameDestroy); + if (!Adjusted) + return std::unexpected(Adjusted.error()); + } + return Block->removeInstruction(Instruction); + } + + [[nodiscard]] Expected<void> emitPrologue(MachineFunction &Function, + const TargetDescription &Target, + RegisterScavenger &Scavenger) const override { + MachineBasicBlock *Entry = Function.firstBlock(); + if (Entry == nullptr) + return Function.frameInfo().state().StackSize == 0 + ? Expected<void>{} + : makeUnexpected(ErrorCode::VerificationError, + "RISC-V nonempty frame has no entry block"); + const std::vector<CalleeSaveOperation> Saves = calleeSaveOperations(*Entry, Function, false); + if (Saves.size() != Function.records().calleeSavedRegisters().size()) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V prologue has an incomplete callee-save sequence"); + } + MachineInstr *Anchor = Entry->firstInstruction(); + MachineIRBuilder Builder(Function, Target); + auto Point = + Anchor != nullptr ? Builder.setInsertPointBefore(*Anchor) : Builder.setInsertPoint(*Entry); + if (!Point) + return std::unexpected(Point.error()); + + const std::uint64_t StackSize = Function.frameInfo().state().StackSize; + const std::uint64_t StackAlignment = requiredStackAlignment(Function); + const bool Realign = requiresStackRealignment(Function); + auto SP = physical(PhysicalRegisterID::X2); + auto FP = physical(PhysicalRegisterID::X8); + auto BP = physical(PhysicalRegisterID::X9); + auto Zero = physical(PhysicalRegisterID::X0); + auto OldFP = physical(PhysicalRegisterID::X5); + auto DefaultTemporary = physical(PhysicalRegisterID::X6); + if (!SP || !FP || !BP || !Zero || !OldFP || !DefaultTemporary) { + return makeUnexpected(ErrorCode::InternalError, "RISC-V frame registers are unavailable"); + } + PhysicalRegister Temporary = *DefaultTemporary; + const std::int64_t AlignmentMask = std::bit_cast<std::int64_t>(~(StackAlignment - 1U)); + const bool NeedsTemporary = StackSize > 2048U || + (!Realign && requiresFramePointer(Function) && + StackSize > static_cast<std::uint64_t>(MaxSigned12)) || + (Realign && !fitsSigned12(AlignmentMask)); + if (NeedsTemporary) { + auto Candidates = scratchRegisters(); + if (!Candidates) + return std::unexpected(Candidates.error()); + if (Anchor != nullptr) { + auto Scratch = Scavenger.scavenge(*Anchor, *Candidates); + if (!Scratch) + return std::unexpected(Scratch.error()); + if (Scratch->RequiresSpill) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "RISC-V prologue has no dead scratch register"); + } + Temporary = Scratch->Reg; + } else { + Temporary = Candidates->front(); + } + } + + if (Realign) { + auto PreserveFP = emitAddImmediate(Builder, *OldFP, *FP, 0, MachineInstrFlag::FrameSetup); + if (!PreserveFP) + return std::unexpected(PreserveFP.error()); + auto CaptureIncomingSP = emitAddImmediate(Builder, *FP, *SP, 0, MachineInstrFlag::FrameSetup); + if (!CaptureIncomingSP) + return std::unexpected(CaptureIncomingSP.error()); + auto CFA = emitDefCFI(Builder, Target, *FP, 0); + if (!CFA) + return std::unexpected(CFA.error()); + } + + const std::uint64_t AllocationSize = StackSize; + if (AllocationSize > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) { + return makeUnexpected(ErrorCode::FrameLayoutFailed, "RISC-V stack adjustment exceeds int64"); + } + if (AllocationSize != 0) { + const std::int64_t Amount = -static_cast<std::int64_t>(AllocationSize); + if (fitsSigned12(Amount)) { + auto Adjust = emitAddImmediate(Builder, *SP, *SP, Amount, MachineInstrFlag::FrameSetup); + if (!Adjust) + return std::unexpected(Adjust.error()); + } else { + auto Constant = + emitConstant(Builder, Temporary, *Zero, Amount, MachineInstrFlag::FrameSetup); + if (!Constant) + return std::unexpected(Constant.error()); + auto Adjust = emitRegisterAdd(Builder, *SP, *SP, Temporary, MachineInstrFlag::FrameSetup); + if (!Adjust) + return std::unexpected(Adjust.error()); + } + if (!Realign) { + auto CFA = emitDefCFI(Builder, Target, *SP, static_cast<std::int64_t>(StackSize)); + if (!CFA) + return std::unexpected(CFA.error()); + } + } + if (Realign) { + const std::int64_t Mask = AlignmentMask; + Expected<void> Aligned = + fitsSigned12(Mask) + ? emitAndImmediate(Builder, *SP, *SP, Mask, MachineInstrFlag::FrameSetup) + : emitConstant(Builder, Temporary, *Zero, Mask, MachineInstrFlag::FrameSetup); + if (!Aligned) + return std::unexpected(Aligned.error()); + if (!fitsSigned12(Mask)) { + Aligned = emitRegisterAnd(Builder, *SP, *SP, Temporary, MachineInstrFlag::FrameSetup); + if (!Aligned) + return std::unexpected(Aligned.error()); + } + } + + if (Realign) { + if (Saves.empty()) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V realigned frame has no callee-save sequence"); + } + MachineIRBuilder AfterSaves(Function, Target); + auto PointAfterSaves = AfterSaves.setInsertPointAfter(*Saves.back().Instruction); + if (!PointAfterSaves) + return std::unexpected(PointAfterSaves.error()); + auto Set = emitAddImmediate(AfterSaves, *BP, *SP, 0, MachineInstrFlag::FrameSetup); + if (!Set) + return std::unexpected(Set.error()); + for (const PhysicalRegister Reg : Function.records().calleeSavedRegisters()) { + const auto Slot = calleeSaveSlot(Function, Reg); + const StackObject *Object = Slot ? Function.frameInfo().object(*Slot) : nullptr; + if (Object == nullptr || !Object->description()->Offset) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V realigned CFI slot is incomplete"); + } + auto CFI = + emitSavedRegisterCFI(AfterSaves, Target, Reg, *Object->description()->Offset, *BP); + if (!CFI) + return std::unexpected(CFI.error()); + } + return {}; + } + + for (std::size_t Index = 0; Index < Saves.size(); ++Index) { + const CalleeSaveOperation &Save = Saves[Index]; + const auto Slot = calleeSaveSlot(Function, Save.Reg); + const StackObject *Object = Slot ? Function.frameInfo().object(*Slot) : nullptr; + if (Object == nullptr || !Object->description()->Offset) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V callee-save CFI slot is incomplete"); + } + auto Offset = + checkedAdd(*Object->description()->Offset, -static_cast<std::int64_t>(StackSize)); + if (!Offset) + return std::unexpected(Offset.error()); + MachineIRBuilder AfterSave(Function, Target); + auto PointAfterSave = AfterSave.setInsertPointAfter(*Save.Instruction); + if (!PointAfterSave) + return std::unexpected(PointAfterSave.error()); + auto CFI = emitSavedRegisterCFI(AfterSave, Target, Save.Reg, *Offset); + if (!CFI) + return std::unexpected(CFI.error()); + if (Index + 1U != Saves.size() || !requiresFramePointer(Function)) + continue; + Expected<void> Set = + StackSize <= static_cast<std::uint64_t>(MaxSigned12) + ? emitAddImmediate(AfterSave, *FP, *SP, static_cast<std::int64_t>(StackSize), + MachineInstrFlag::FrameSetup) + : emitConstant(AfterSave, Temporary, *Zero, static_cast<std::int64_t>(StackSize), + MachineInstrFlag::FrameSetup); + if (!Set) + return std::unexpected(Set.error()); + if (StackSize > static_cast<std::uint64_t>(MaxSigned12)) { + Set = emitRegisterAdd(AfterSave, *FP, *SP, Temporary, MachineInstrFlag::FrameSetup); + if (!Set) + return std::unexpected(Set.error()); + } + auto CFA = emitDefCFI(AfterSave, Target, *FP, 0); + if (!CFA) + return std::unexpected(CFA.error()); + } + if (Saves.empty() && requiresFramePointer(Function)) { + Expected<void> Set = + StackSize <= static_cast<std::uint64_t>(MaxSigned12) + ? emitAddImmediate(Builder, *FP, *SP, static_cast<std::int64_t>(StackSize), + MachineInstrFlag::FrameSetup) + : emitConstant(Builder, Temporary, *Zero, static_cast<std::int64_t>(StackSize), + MachineInstrFlag::FrameSetup); + if (!Set) + return std::unexpected(Set.error()); + if (StackSize > static_cast<std::uint64_t>(MaxSigned12)) { + Set = emitRegisterAdd(Builder, *FP, *SP, Temporary, MachineInstrFlag::FrameSetup); + if (!Set) + return std::unexpected(Set.error()); + } + auto CFA = emitDefCFI(Builder, Target, *FP, 0); + if (!CFA) + return std::unexpected(CFA.error()); + } + return {}; + } + + [[nodiscard]] bool isEpilogueTerminator(const MachineInstr &Instruction, + const TargetDescription &Target) const noexcept override { + if (Instruction.opcode() == targetOpcode(InstructionOpcode::PseudoTAIL)) + return true; + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode()); + return Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Return); + } + + [[nodiscard]] Expected<void> emitEpilogue(MachineBasicBlock &Block, MachineInstr &Terminator, + MachineFunction &Function, + const TargetDescription &Target, + RegisterScavenger &Scavenger) const override { + auto FP = physical(PhysicalRegisterID::X8); + auto SP = physical(PhysicalRegisterID::X2); + auto BP = physical(PhysicalRegisterID::X9); + if (!FP || !SP || !BP) { + return makeUnexpected(ErrorCode::InternalError, "RISC-V frame registers are unavailable"); + } + const bool HasFP = requiresFramePointer(Function); + const bool Realign = requiresStackRealignment(Function); + const std::uint64_t StackSize = Function.frameInfo().state().StackSize; + const bool HasFrameCFI = StackSize != 0 || !Function.records().calleeSavedRegisters().empty(); + + const std::vector<CalleeSaveOperation> BlockRestores = + calleeSaveOperations(Block, Function, true); + std::vector<CalleeSaveOperation> Restores; + for (MachineInstr *Cursor = Terminator.previous(); Cursor != nullptr; + Cursor = Cursor->previous()) { + const auto Position = + std::ranges::find(BlockRestores, Cursor, &CalleeSaveOperation::Instruction); + if (Position == BlockRestores.end()) + break; + Restores.push_back(*Position); + } + std::ranges::reverse(Restores); + const std::size_t ExpectedRestores = static_cast<std::size_t>(std::ranges::count_if( + Function.records().calleeSavedRegisters(), + [&Function](PhysicalRegister Reg) { return calleeSaveIsRestored(Function, Reg); })); + if (Restores.size() != ExpectedRestores) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V epilogue has an incomplete callee-restore sequence"); + } + + if (HasFrameCFI) { + MachineIRBuilder RememberBuilder(Function, Target); + auto Point = Restores.empty() + ? RememberBuilder.setInsertPointBefore(Terminator) + : RememberBuilder.setInsertPointBefore(*Restores.front().Instruction); + if (!Point) + return std::unexpected(Point.error()); + auto Remember = emitCFI(RememberBuilder, MachineCFIInstruction::rememberState()); + if (!Remember) + return std::unexpected(Remember.error()); + } + + for (const CalleeSaveOperation &Restore : Restores) { + if ((HasFP && Restore.Reg == *FP) || (Realign && Restore.Reg == *BP)) + continue; + MachineIRBuilder AfterRestore(Function, Target); + auto Point = AfterRestore.setInsertPointAfter(*Restore.Instruction); + if (!Point) + return std::unexpected(Point.error()); + auto CFI = emitRestoreRegisterCFI(AfterRestore, Target, Restore.Reg); + if (!CFI) + return std::unexpected(CFI.error()); + } + + if (Realign) { + const auto FPRestore = std::ranges::find(Restores, *FP, &CalleeSaveOperation::Reg); + const auto BPRestore = std::ranges::find(Restores, *BP, &CalleeSaveOperation::Reg); + MachineIRBuilder Teardown(Function, Target); + MachineInstr *SpecialRestore = + FPRestore != Restores.end() + ? FPRestore->Instruction + : (BPRestore != Restores.end() ? BPRestore->Instruction : &Terminator); + auto Point = Teardown.setInsertPointBefore(*SpecialRestore); + if (!Point) + return std::unexpected(Point.error()); + auto RestoreSP = emitAddImmediate(Teardown, *SP, *FP, 0, MachineInstrFlag::FrameDestroy); + if (!RestoreSP) + return std::unexpected(RestoreSP.error()); + auto CFA = emitDefCFI(Teardown, Target, *SP, 0); + if (!CFA) + return std::unexpected(CFA.error()); + if (FPRestore != Restores.end()) { + MachineIRBuilder AfterFP(Function, Target); + auto After = AfterFP.setInsertPointAfter(*FPRestore->Instruction); + if (!After) + return std::unexpected(After.error()); + auto FPCFI = emitRestoreRegisterCFI(AfterFP, Target, *FP); + if (!FPCFI) + return std::unexpected(FPCFI.error()); + } + if (BPRestore != Restores.end()) { + MachineIRBuilder AfterBP(Function, Target); + auto After = AfterBP.setInsertPointAfter(*BPRestore->Instruction); + if (!After) + return std::unexpected(After.error()); + auto BPCFI = emitRestoreRegisterCFI(AfterBP, Target, *BP); + if (!BPCFI) + return std::unexpected(BPCFI.error()); + } + } else if (HasFP) { + const auto FPRestore = std::ranges::find(Restores, *FP, &CalleeSaveOperation::Reg); + MachineIRBuilder Teardown(Function, Target); + auto Point = FPRestore == Restores.end() + ? Teardown.setInsertPointBefore(Terminator) + : Teardown.setInsertPointBefore(*FPRestore->Instruction); + if (!Point) + return std::unexpected(Point.error()); + auto RestoreSP = emitAddImmediate(Teardown, *SP, *FP, 0, MachineInstrFlag::FrameDestroy); + if (!RestoreSP) + return std::unexpected(RestoreSP.error()); + auto CFA = emitDefCFI(Teardown, Target, *SP, 0); + if (!CFA) + return std::unexpected(CFA.error()); + if (FPRestore != Restores.end()) { + MachineIRBuilder AfterFP(Function, Target); + auto After = AfterFP.setInsertPointAfter(*FPRestore->Instruction); + if (!After) + return std::unexpected(After.error()); + auto FPCFI = emitRestoreRegisterCFI(AfterFP, Target, *FP); + if (!FPCFI) + return std::unexpected(FPCFI.error()); + } + } else if (StackSize != 0) { + if (StackSize > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) + return makeUnexpected(ErrorCode::FrameLayoutFailed, + "RISC-V stack adjustment exceeds int64"); + MachineIRBuilder Teardown(Function, Target); + auto Point = Teardown.setInsertPointBefore(Terminator); + if (!Point) + return std::unexpected(Point.error()); + const std::int64_t Amount = static_cast<std::int64_t>(StackSize); + if (fitsSigned12(Amount)) { + auto Adjust = emitAddImmediate(Teardown, *SP, *SP, Amount, MachineInstrFlag::FrameDestroy); + if (!Adjust) + return std::unexpected(Adjust.error()); + } else { + auto Candidates = scratchRegisters(); + auto Zero = physical(PhysicalRegisterID::X0); + if (!Candidates || !Zero) + return std::unexpected(!Candidates ? Candidates.error() : Zero.error()); + auto Scratch = Scavenger.scavenge(Terminator, *Candidates); + if (!Scratch) + return std::unexpected(Scratch.error()); + if (Scratch->RequiresSpill) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "RISC-V epilogue has no dead scratch register"); + } + auto Constant = + emitConstant(Teardown, Scratch->Reg, *Zero, Amount, MachineInstrFlag::FrameDestroy); + if (!Constant) + return std::unexpected(Constant.error()); + auto Adjust = + emitRegisterAdd(Teardown, *SP, *SP, Scratch->Reg, MachineInstrFlag::FrameDestroy); + if (!Adjust) + return std::unexpected(Adjust.error()); + } + auto CFA = emitDefCFI(Teardown, Target, *SP, 0); + if (!CFA) + return std::unexpected(CFA.error()); + } + if (HasFrameCFI) { + MachineIRBuilder RestoreBuilder(Function, Target); + auto After = RestoreBuilder.setInsertPointAfter(Terminator); + if (!After) + return std::unexpected(After.error()); + auto Restore = emitCFI(RestoreBuilder, MachineCFIInstruction::restoreState()); + if (!Restore) + return std::unexpected(Restore.error()); + } + return {}; + } + + [[nodiscard]] Expected<FrameIndexReference> + getFrameIndexReference(const MachineFunction &Function, const MachineInstr &Instruction, + FrameIndex Index, std::int64_t OperandOffset) const override { + const StackObject *Object = Function.frameInfo().object(Index); + if (Object == nullptr || Object->description()->IsDead) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V FrameIndex references an invalid stack object"); + if (Object->isVariableSized()) + return makeUnexpected(ErrorCode::Unsupported, + "RISC-V variable-sized object cannot be addressed by FrameIndex"); + auto Offset = + objectReferenceOffset(Function, Instruction, *Object->description(), OperandOffset); + if (!Offset) + return std::unexpected(Offset.error()); + const StackObjectDesc &Description = *Object->description(); + PhysicalRegisterID BaseID = PhysicalRegisterID::X2; + if (!isOutgoingCallObject(Description) && + !Instruction.flags().has(MachineInstrFlag::FrameSetup)) { + const bool FixedObject = Description.Kind == StackObjectKind::FixedABI || + Description.Kind == StackObjectKind::FixedSpillSlot; + const bool HasFP = requiresFramePointer(Function); + const bool HasBP = requiresBasePointer(Function); + if (HasFP && (FixedObject || !HasBP)) { + BaseID = PhysicalRegisterID::X8; + } else if (HasBP) { + BaseID = PhysicalRegisterID::X9; + } + } + auto Base = physical(BaseID); + if (!Base) + return std::unexpected(Base.error()); + return FrameIndexReference{*Base, *Offset}; + } + + [[nodiscard]] Expected<void> eliminateFrameIndex(MachineInstr &Instruction, + std::size_t OperandIndex, + MachineFunction &Function, + const TargetDescription &Target, + RegisterScavenger &Scavenger) const override { + const auto *Frame = Instruction.operandAt(OperandIndex)->getIf<FrameIndexOperand>(); + if (Frame == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V frame elimination requires a FrameIndex operand"); + if (OperandIndex + 1U >= Instruction.operandCount()) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V frame operand lacks an adjacent immediate"); + auto Immediate = immediateValue(*Instruction.operandAt(OperandIndex + 1U)); + if (!Immediate) + return std::unexpected(Immediate.error()); + auto Extra = checkedAdd(Frame->Offset, *Immediate); + if (!Extra) + return std::unexpected(Extra.error()); + auto Reference = getFrameIndexReference(Function, Instruction, Frame->Index, *Extra); + if (!Reference) + return std::unexpected(Reference.error()); + if (fitsSigned12(Reference->Offset)) { + auto Base = replaceWithRegister(Instruction, OperandIndex, Reference->BaseRegister); + if (!Base) + return std::unexpected(Base.error()); + return replaceImmediate(Instruction, OperandIndex + 1U, Reference->Offset); + } + + auto Candidates = scratchRegisters(); + if (!Candidates) + return std::unexpected(Candidates.error()); + auto Scratch = Scavenger.scavenge(Instruction, *Candidates); + if (!Scratch) + return std::unexpected(Scratch.error()); + std::optional<FrameIndexReference> Emergency; + if (Scratch->RequiresSpill) { + const StackObject *Object = emergencyObject(Function); + if (Object == nullptr) + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "RISC-V scavenging requires an emergency spill slot"); + auto Ref = emergencyFrameReference(Function, *Object->description()); + if (!Ref) + return std::unexpected(Ref.error()); + if (!fitsSigned12(Ref->Offset)) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "RISC-V emergency spill slot is out of range"); + } + Emergency = *Ref; + auto Saved = + emitResolvedScratchAccess(Instruction, Function, Target, Scratch->Reg, *Emergency, false); + if (!Saved) + return std::unexpected(Saved.error()); + } + + MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPointBefore(Instruction); + if (!Point) + return std::unexpected(Point.error()); + auto Zero = physical(PhysicalRegisterID::X0); + if (!Zero) + return std::unexpected(Zero.error()); + auto Constant = emitConstant(Builder, Scratch->Reg, *Zero, Reference->Offset, std::nullopt); + if (!Constant) + return std::unexpected(Constant.error()); + auto Address = + emitRegisterAdd(Builder, Scratch->Reg, Reference->BaseRegister, Scratch->Reg, std::nullopt); + if (!Address) + return std::unexpected(Address.error()); + auto Base = replaceWithRegister(Instruction, OperandIndex, Scratch->Reg); + if (!Base) + return std::unexpected(Base.error()); + auto Offset = replaceImmediate(Instruction, OperandIndex + 1U, 0); + if (!Offset) + return std::unexpected(Offset.error()); + if (Emergency) { + auto Restored = + emitResolvedScratchAccess(Instruction, Function, Target, Scratch->Reg, *Emergency, true); + if (!Restored) + return std::unexpected(Restored.error()); + } + return {}; + } + +private: + [[nodiscard]] Expected<void> emitStackAdjustment(MachineInstr &Anchor, MachineFunction &Function, + const TargetDescription &Target, + RegisterScavenger &Scavenger, + std::int64_t Amount, + MachineInstrFlag Flag) const { + if (Amount == 0) + return {}; + auto SP = physical(PhysicalRegisterID::X2); + if (!SP) + return std::unexpected(SP.error()); + MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPointBefore(Anchor); + if (!Point) + return std::unexpected(Point.error()); + if (fitsSigned12(Amount)) + return emitAddImmediate(Builder, *SP, *SP, Amount, Flag); + + auto Candidates = scratchRegisters(); + if (!Candidates) + return std::unexpected(Candidates.error()); + auto Scratch = Scavenger.scavenge(Anchor, *Candidates); + if (!Scratch) + return std::unexpected(Scratch.error()); + std::optional<FrameIndexReference> Emergency; + if (Scratch->RequiresSpill) { + const StackObject *Object = emergencyObject(Function); + if (Object == nullptr) + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "RISC-V stack adjustment requires an emergency spill slot"); + auto Ref = emergencyFrameReference(Function, *Object->description()); + if (!Ref || !fitsSigned12(Ref->Offset)) + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "RISC-V emergency spill slot is unavailable"); + Emergency = *Ref; + auto Saved = + emitResolvedScratchAccess(Anchor, Function, Target, Scratch->Reg, *Emergency, false); + if (!Saved) + return std::unexpected(Saved.error()); + } + auto Zero = physical(PhysicalRegisterID::X0); + if (!Zero) + return std::unexpected(Zero.error()); + auto Constant = emitConstant(Builder, Scratch->Reg, *Zero, Amount, Flag); + if (!Constant) + return std::unexpected(Constant.error()); + auto Adjust = emitRegisterAdd(Builder, *SP, *SP, Scratch->Reg, Flag); + if (!Adjust) + return std::unexpected(Adjust.error()); + if (Emergency) { + auto Restored = + emitResolvedScratchAccess(Anchor, Function, Target, Scratch->Reg, *Emergency, true); + if (!Restored) + return std::unexpected(Restored.error()); + } + return {}; + } + + [[nodiscard]] Expected<void> + emitResolvedScratchAccess(MachineInstr &Anchor, MachineFunction &Function, + const TargetDescription &Target, PhysicalRegister Scratch, + FrameIndexReference Reference, bool Restore) const { + MachineIRBuilder Builder(Function, Target); + auto Point = + Restore ? Builder.setInsertPointAfter(Anchor) : Builder.setInsertPointBefore(Anchor); + if (!Point) + return std::unexpected(Point.error()); + auto Memory = createResolvedStackMemory( + Function, Restore ? MemoryAccessFlag::Load : MemoryAccessFlag::Store, Reference.Offset); + if (!Memory) + return std::unexpected(Memory.error()); + auto Pending = + Builder.buildInstr(targetOpcode(Restore ? InstructionOpcode::LD : InstructionOpcode::SD)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Value = Restore ? Pending->addDef(Register::fromPhysical(Scratch)) + : Pending->addUse(Register::fromPhysical(Scratch)); + if (!Value) + return std::unexpected(Value.error()); + if (auto Result = Pending->addUse(Register::fromPhysical(Reference.BaseRegister)); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addImmediate(Reference.Offset); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addMemOperand(**Memory); !Result) + return std::unexpected(Result.error()); + auto Built = Pending->build(); + if (!Built) + return std::unexpected(Built.error()); + return {}; + } +}; + +} // namespace + +const TargetFrameLowering &frameLowering() noexcept { + static const RISCVFrameLowering Info; + return Info; +} + +} // namespace rcc::riscv diff --git a/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp b/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp index e437e18..81fc6dc 100644 --- a/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp +++ b/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp @@ -1,6 +1,7 @@ // SPDX-License-Identifier: GPL-3.0-or-later #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" @@ -13,6 +14,7 @@ #include <algorithm> #include <array> +#include <bit> #include <cstddef> #include <cstdint> #include <optional> @@ -35,6 +37,20 @@ struct SpillForm final { return RegisterClassID::fromValue(static_cast<std::uint32_t>(Value)); } +[[nodiscard]] std::optional<std::int64_t> immediateValue(const MachineOperand &Operand) noexcept { + if (const auto *Immediate = Operand.getIf<std::int64_t>()) + return *Immediate; + const auto *Integer = Operand.getIf<IntegerImmediateOperand>(); + if (Integer == nullptr || Integer->Value.bitWidth() == 0 || Integer->Value.bitWidth() > 64) { + return std::nullopt; + } + std::uint64_t Raw = Integer->Value.words().empty() ? 0 : Integer->Value.words().front(); + const std::uint32_t Width = Integer->Value.bitWidth(); + if (Width < 64 && (Raw & (std::uint64_t{1} << (Width - 1U))) != 0) + Raw |= ~std::uint64_t{0} << Width; + return std::bit_cast<std::int64_t>(Raw); +} + [[nodiscard]] constexpr std::optional<SpillForm> spillForm(RegisterClassID Class) noexcept { if (Class == registerClassID(RegisterClass::GPR) || Class == registerClassID(RegisterClass::GPRC) || @@ -102,6 +118,74 @@ createStackMemoryOperand(MachineIRBuilder &Builder, FrameIndex StackSlot, Memory class RISCVRegisterAllocationInfo final : public TargetRegisterAllocationInfo { public: + [[nodiscard]] bool + isReservedForFunction(const MachineFunction &Function, PhysicalRegister Reg, + const TargetDescription &Target) const noexcept override { + std::uint64_t RequiredAlignment = 16; + RequiredAlignment = std::max( + RequiredAlignment, Function.frameInfo().state().MaxAlignment.value_or(Alignment{}).bytes()); + for (const StackObject &Object : Function.frameInfo().objects()) { + if (!Object.isTombstone() && !Object.description()->IsDead) { + RequiredAlignment = std::max(RequiredAlignment, Object.description()->Align.bytes()); + } + } + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (Instruction->opcode() != targetOpcode(InstructionOpcode::ADJCALLSTACKDOWN) && + Instruction->opcode() != targetOpcode(InstructionOpcode::ADJCALLSTACKUP)) { + continue; + } + if (Instruction->operandCount() < 2) + continue; + const auto Requested = immediateValue(*Instruction->operandAt(1)); + if (Requested && *Requested > 0 && + std::has_single_bit(static_cast<std::uint64_t>(*Requested))) { + RequiredAlignment = std::max(RequiredAlignment, static_cast<std::uint64_t>(*Requested)); + } + } + } + const bool RequiresRealignment = RequiredAlignment > 16; + if (Reg.number() == static_cast<std::uint32_t>(PhysicalRegisterID::X9)) + return RequiresRealignment; + if (Reg.number() != static_cast<std::uint32_t>(PhysicalRegisterID::X8)) + return false; + const MachineFrameState &State = Function.frameInfo().state(); + bool HasCalls = State.HasCalls; + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr && !HasCalls; + Block = Block->next()) { + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = + Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Call)) { + HasCalls = true; + break; + } + } + } + const bool HasVariableObject = + std::ranges::any_of(Function.frameInfo().objects(), [](const StackObject &Object) { + return !Object.isTombstone() && !Object.description()->IsDead && Object.isVariableSized(); + }); + if (State.IsFrameAddressTaken || State.HasOpaqueSPAdjustment || HasVariableObject || + RequiresRealignment) + return true; + switch (State.FramePointerPolicy) { + case MachineFramePointerPolicy::All: + case MachineFramePointerPolicy::Reserved: + return true; + case MachineFramePointerPolicy::NonLeaf: + case MachineFramePointerPolicy::NonLeafNoReserve: + return HasCalls; + case MachineFramePointerPolicy::None: + case MachineFramePointerPolicy::Count: + return false; + } + return false; + } + [[nodiscard]] Expected<void> validateSpillReload(RegisterClassID Class, const TargetDescription &Target) const override { const RegisterClassDesc *Description = Target.registers().registerClass(Class); diff --git a/backend/unittests/CodeGen/MachineIRCoreTest.cpp b/backend/unittests/CodeGen/MachineIRCoreTest.cpp index 028afc5..7982b04 100644 --- a/backend/unittests/CodeGen/MachineIRCoreTest.cpp +++ b/backend/unittests/CodeGen/MachineIRCoreTest.cpp @@ -438,12 +438,20 @@ void testOwnershipCFGAndMemory(TestContext &Context) { "instruction must reject a block operand from another function"); auto MemOperand = Function->createMemOperand(makeLoadDescription()); + auto ReplacementMemOperand = Function->createMemOperand(makeLoadDescription()); auto ForeignMemOperand = OtherFunction->createMemOperand(makeLoadDescription()); - Context.expect(MemOperand && ForeignMemOperand, + Context.expect(MemOperand && ReplacementMemOperand && ForeignMemOperand, "function arena must allocate immutable memory operands"); - if (MemOperand && ForeignMemOperand) { + if (MemOperand && ReplacementMemOperand && ForeignMemOperand) { Context.expect((*Instr)->addMemOperand(**MemOperand).has_value(), "instruction must accept a memory operand owned by its function"); + Context.expect((*Instr)->replaceMemOperand(0, **ReplacementMemOperand).has_value() && + (*Instr)->memOperands().front() == *ReplacementMemOperand, + "instruction must replace an owned memory operand in place"); + Context.expect(!(*Instr)->replaceMemOperand(1, **MemOperand) && + !(*Instr)->replaceMemOperand(0, **ForeignMemOperand) && + (*Instr)->memOperands().front() == *ReplacementMemOperand, + "invalid memory replacement must fail without mutation"); Context.expect(!(*Instr)->addMemOperand(**ForeignMemOperand), "instruction must reject a memory operand from another function"); } diff --git a/backend/unittests/Support/ErrorTest.cpp b/backend/unittests/Support/ErrorTest.cpp index 23140e3..af2ece9 100644 --- a/backend/unittests/Support/ErrorTest.cpp +++ b/backend/unittests/Support/ErrorTest.cpp @@ -28,6 +28,8 @@ int main() { return fail("Error must preserve its message"); if (rcc::getErrorCodeName(Failure.error().code()) != "parse error") return fail("Error code must have a stable name"); + if (rcc::getErrorCodeName(rcc::ErrorCode::FrameLayoutFailed) != "frame layout failed") + return fail("frame-layout errors must have a stable name"); return 0; } diff --git a/backend/unittests/Target/CMakeLists.txt b/backend/unittests/Target/CMakeLists.txt index ca376da..a114c7f 100644 --- a/backend/unittests/Target/CMakeLists.txt +++ b/backend/unittests/Target/CMakeLists.txt @@ -49,6 +49,17 @@ add_test( COMMAND RCCBackendRISCVRegisterAllocationTests ) +add_executable(RCCBackendRISCVFrameLoweringTests RISCVFrameLoweringTest.cpp) +rcc_backend_configure_target(RCCBackendRISCVFrameLoweringTests) +target_link_libraries( + RCCBackendRISCVFrameLoweringTests + PRIVATE RCCBackend::RISCV RCCBackend::CodeGen +) +add_test( + NAME RCCBackendRISCVFrameLoweringTests + COMMAND RCCBackendRISCVFrameLoweringTests +) + rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/DescriptionGeneratorTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLoweringTest.cpp" @@ -56,6 +67,7 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGenTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVSSAExitTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVRegisterAllocationTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFrameLoweringTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TestTarget.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TestTarget.h" ) @@ -66,5 +78,6 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGenTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVSSAExitTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVRegisterAllocationTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFrameLoweringTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TestTarget.cpp" ) diff --git a/backend/unittests/Target/RISCVFrameLoweringTest.cpp b/backend/unittests/Target/RISCVFrameLoweringTest.cpp new file mode 100644 index 0000000..7096840 --- /dev/null +++ b/backend/unittests/Target/RISCVFrameLoweringTest.cpp @@ -0,0 +1,1361 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachineCFIInfo.h" +#include "rcc/CodeGen/MachineFrameInfo.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/PrologueEpilogueInsertion.h" +#include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetFrameLowering.h" +#include "rcc/CodeGen/TargetRegisterAllocationInfo.h" +#include "rcc/Target/RISCV/RISCVCallLowering.h" +#include "rcc/Target/RISCV/RISCVCodeGen.h" +#include "rcc/Target/RISCV/RISCVInstructions.h" +#include "rcc/Target/RISCV/RISCVRegisters.h" +#include "rcc/Target/RISCV/RISCVTarget.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <iostream> +#include <memory> +#include <optional> +#include <string> +#include <string_view> +#include <utility> +#include <vector> + +namespace { + +class TestContext final { +public: + void expect(bool Condition, std::string_view Message) { + if (Condition) + return; + std::cerr << Message << '\n'; + ++Failures; + } + + [[nodiscard]] int result() const noexcept { + return Failures == 0 ? 0 : 1; + } + +private: + int Failures = 0; +}; + +struct FunctionFixture final { + std::unique_ptr<rcc::MachineFunction> Function; + rcc::MachineBasicBlock *Block = nullptr; +}; + +class ObservingFrameLowering final : public rcc::TargetFrameLowering { +public: + explicit ObservingFrameLowering(const rcc::TargetFrameLowering &Delegate, + bool SkipFrameIndexElimination = false) noexcept + : Delegate(&Delegate), SkipFrameIndexElimination(SkipFrameIndexElimination) {} + + [[nodiscard]] rcc::Expected<void> + prepareFrame(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target) const override { + PrepareSawUnfrozen = !Function.frameInfo().isFrozen(); + return Delegate->prepareFrame(Function, Target); + } + + [[nodiscard]] rcc::Expected<void> + insertCalleeSavedSpillsAndRestores(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target) const override { + InsertSawUnfrozen = !Function.frameInfo().isFrozen(); + return Delegate->insertCalleeSavedSpillsAndRestores(Function, Target); + } + + [[nodiscard]] rcc::Expected<void> + processFunctionBeforeFrameFinalized(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target) const override { + return Delegate->processFunctionBeforeFrameFinalized(Function, Target); + } + + [[nodiscard]] rcc::Expected<void> + finalizeFrame(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target) const override { + FinalizeSawUnfrozen = !Function.frameInfo().isFrozen(); + bool HasCalleeSave = false; + for (const rcc::MachineInstr *Instruction : Function.allInstructions()) { + if (Instruction == nullptr || Instruction->parent() == nullptr) + continue; + for (const rcc::MachineOperand &Operand : Instruction->operands()) { + const auto *Frame = Operand.getIf<rcc::FrameIndexOperand>(); + const rcc::StackObject *Object = + Frame == nullptr ? nullptr : Function.frameInfo().object(Frame->Index); + HasCalleeSave |= + Object != nullptr && Object->description()->Kind == rcc::StackObjectKind::CalleeSaved; + } + } + FinalizeSawCalleeSave = HasCalleeSave; + auto Result = Delegate->finalizeFrame(Function, Target); + FinalizeProducedFrozen = Result && Function.frameInfo().isFrozen(); + return Result; + } + + [[nodiscard]] bool + isCallFramePseudo(const rcc::MachineInstr &Instruction) const noexcept override { + return Delegate->isCallFramePseudo(Instruction); + } + + [[nodiscard]] rcc::Expected<void> + eliminateCallFramePseudo(rcc::MachineInstr &Instruction, rcc::MachineFunction &Function, + const rcc::TargetDescription &Target, + rcc::RegisterScavenger &Scavenger) const override { + return Delegate->eliminateCallFramePseudo(Instruction, Function, Target, Scavenger); + } + + [[nodiscard]] rcc::Expected<void> emitPrologue(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target, + rcc::RegisterScavenger &Scavenger) const override { + PrologueSawFrozen = Function.frameInfo().isFrozen(); + return Delegate->emitPrologue(Function, Target, Scavenger); + } + + [[nodiscard]] bool + isEpilogueTerminator(const rcc::MachineInstr &Instruction, + const rcc::TargetDescription &Target) const noexcept override { + return Delegate->isEpilogueTerminator(Instruction, Target); + } + + [[nodiscard]] rcc::Expected<void> emitEpilogue(rcc::MachineBasicBlock &Block, + rcc::MachineInstr &Terminator, + rcc::MachineFunction &Function, + const rcc::TargetDescription &Target, + rcc::RegisterScavenger &Scavenger) const override { + EpilogueSawFrozen = Function.frameInfo().isFrozen(); + return Delegate->emitEpilogue(Block, Terminator, Function, Target, Scavenger); + } + + [[nodiscard]] rcc::Expected<void> + processFunctionBeforeFrameIndexElimination(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target) const override { + return Delegate->processFunctionBeforeFrameIndexElimination(Function, Target); + } + + [[nodiscard]] rcc::Expected<rcc::FrameIndexReference> + getFrameIndexReference(const rcc::MachineFunction &Function, const rcc::MachineInstr &Instruction, + rcc::FrameIndex Index, std::int64_t OperandOffset) const override { + return Delegate->getFrameIndexReference(Function, Instruction, Index, OperandOffset); + } + + [[nodiscard]] rcc::Expected<void> + eliminateFrameIndex(rcc::MachineInstr &Instruction, std::size_t OperandIndex, + rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::RegisterScavenger &Scavenger) const override { + if (SkipFrameIndexElimination) + return {}; + return Delegate->eliminateFrameIndex(Instruction, OperandIndex, Function, Target, Scavenger); + } + + mutable bool PrepareSawUnfrozen = false; + mutable bool InsertSawUnfrozen = false; + mutable bool FinalizeSawUnfrozen = false; + mutable bool FinalizeSawCalleeSave = false; + mutable bool FinalizeProducedFrozen = false; + mutable bool PrologueSawFrozen = false; + mutable bool EpilogueSawFrozen = false; + +private: + const rcc::TargetFrameLowering *Delegate; + bool SkipFrameIndexElimination = false; +}; + +[[nodiscard]] constexpr rcc::Opcode opcode(rcc::riscv::InstructionOpcode Value) noexcept { + return rcc::Opcode::fromValue(static_cast<std::uint32_t>(Value)); +} + +[[nodiscard]] rcc::PhysicalRegister physReg(rcc::riscv::PhysicalRegisterID ID) { + return *rcc::riscv::physicalRegister(ID); +} + +[[nodiscard]] rcc::Register physical(rcc::riscv::PhysicalRegisterID ID) { + return rcc::Register::fromPhysical(physReg(ID)); +} + +[[nodiscard]] rcc::Expected<FunctionFixture> createFunction(std::string Name, + std::uint64_t StableID) { + auto Function = rcc::MachineFunction::create(std::move(Name), + rcc::MachineFunctionStableID::fromValue(StableID)); + if (!Function) + return std::unexpected(Function.error()); + auto Block = (*Function)->createBasicBlock(); + if (!Block) + return std::unexpected(Block.error()); + if (auto Result = (*Function)->appendBlock(**Block); !Result) + return std::unexpected(Result.error()); + return FunctionFixture{std::move(*Function), *Block}; +} + +void setFramePassProperties(rcc::MachineFunction &Function) { + for (const rcc::MachineFunctionProperty Property : { + rcc::MachineFunctionProperty::Legalized, + rcc::MachineFunctionProperty::RegBankSelected, + rcc::MachineFunctionProperty::Selected, + rcc::MachineFunctionProperty::NoPHIs, + rcc::MachineFunctionProperty::TiedOpsRewritten, + rcc::MachineFunctionProperty::NoVRegs, + }) { + Function.properties().set(Property); + } +} + +[[nodiscard]] rcc::Expected<void> +runFrameLoweringWith(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + const rcc::TargetFrameLowering &FrameLowering) { + setFramePassProperties(Function); + rcc::MachinePassManager Pipeline; + auto Added = + Pipeline.addPass(std::make_unique<rcc::PrologueEpilogueInsertionPass>(FrameLowering)); + if (!Added) + return std::unexpected(Added.error()); + rcc::MachineAnalysisManager Analyses; + return Pipeline.run(Function, Target, Analyses); +} + +[[nodiscard]] rcc::Expected<void> runFrameLowering(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target) { + return runFrameLoweringWith(Function, Target, rcc::riscv::frameLowering()); +} + +[[nodiscard]] rcc::Expected<rcc::FrameIndex> +createStackObject(rcc::MachineFunction &Function, rcc::StackObjectKind Kind, + std::optional<std::uint64_t> Size, std::uint64_t Alignment, + std::optional<std::int64_t> Offset = std::nullopt) { + auto Align = rcc::Alignment::create(Alignment); + if (!Align) + return std::unexpected(Align.error()); + rcc::StackObjectDesc Description; + Description.Kind = Kind; + Description.Size = Size; + Description.Align = *Align; + Description.Offset = Offset; + return Function.frameInfo().createObject(std::move(Description)); +} + +[[nodiscard]] rcc::Expected<const rcc::MachineMemOperand *> +createStackMemory(rcc::MachineFunction &Function, rcc::FrameIndex Index, + rcc::MemoryAccessFlag Access, std::int64_t Offset) { + auto Size = rcc::MemorySize::fixed(8); + auto Align = rcc::Alignment::create(8); + if (!Size || !Align) + return rcc::makeUnexpected(rcc::ErrorCode::InternalError, "invalid test memory facts"); + rcc::MachineMemOperandDesc Description; + Description.Accesses = {Access}; + Description.Size = *Size; + Description.Align = *Align; + Description.Base = rcc::MemoryBase::frameIndex(Index); + Description.Offset = Offset; + return Function.createMemOperand(std::move(Description)); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildStackAccess(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::riscv::InstructionOpcode OpcodeValue, + rcc::Register Value, rcc::FrameIndex Index, std::int64_t Offset) { + const bool IsLoad = OpcodeValue == rcc::riscv::InstructionOpcode::LD || + OpcodeValue == rcc::riscv::InstructionOpcode::FLD; + auto Memory = createStackMemory( + Function, Index, IsLoad ? rcc::MemoryAccessFlag::Load : rcc::MemoryAccessFlag::Store, Offset); + if (!Memory) + return std::unexpected(Memory.error()); + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(opcode(OpcodeValue)); + if (!Pending) + return std::unexpected(Pending.error()); + auto RegisterResult = IsLoad ? Pending->addDef(Value) : Pending->addUse(Value); + if (!RegisterResult) + return std::unexpected(RegisterResult.error()); + if (auto Result = Pending->addFrameIndex(Index); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addImmediate(Offset); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addMemOperand(**Memory); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildAddImmediate(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Destination, rcc::Register Source, + std::int64_t Immediate) { + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::ADDI)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Destination); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addUse(Source); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addImmediate(Immediate); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> buildAdd(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, + rcc::Register Destination, + rcc::Register Left, rcc::Register Right) { + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::ADD)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Destination); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addUse(Left); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addUse(Right); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildMoveToDouble(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Destination, rcc::Register Source) { + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::FMV_D_X)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Destination); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addUse(Source); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildCallFramePseudo(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::riscv::InstructionOpcode OpcodeValue, + std::int64_t Amount, std::int64_t Alignment = 16) { + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(opcode(OpcodeValue)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addImmediate(Amount); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addImmediate(Alignment); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildRegisterMaskClobber(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::PhysicalRegister Clobbered) { + std::uint64_t Preserved = ~std::uint64_t{1}; + Preserved &= ~(std::uint64_t{1} << Clobbered.number()); + auto Mask = std::make_shared<const rcc::RegisterMask>(std::vector<std::uint64_t>{Preserved}); + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::INLINEASM)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addRegisterMask(std::move(Mask)); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildIndirectTail(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Callee) { + auto Mask = + std::make_shared<const rcc::RegisterMask>(std::vector<std::uint64_t>{~std::uint64_t{1}}); + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::PseudoTAIL)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addUse(Callee); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addImmediate(1); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addRegisterMask(std::move(Mask)); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> buildReturn(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block) { + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::PseudoRET)); + if (!Pending) + return std::unexpected(Pending.error()); + return Pending->build(); +} + +[[nodiscard]] std::vector<rcc::MachineInstr *> instructions(rcc::MachineBasicBlock &Block) { + std::vector<rcc::MachineInstr *> Result; + for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + Result.push_back(Instruction); + } + return Result; +} + +[[nodiscard]] std::size_t countOpcode(const rcc::MachineFunction &Function, + rcc::Opcode OpcodeValue) { + std::size_t Result = 0; + for (const rcc::MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const rcc::MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + Result += Instruction->opcode() == OpcodeValue ? 1U : 0U; + } + } + return Result; +} + +[[nodiscard]] std::size_t countOpcode(const rcc::MachineFunction &Function, + rcc::riscv::InstructionOpcode OpcodeValue) { + return countOpcode(Function, opcode(OpcodeValue)); +} + +[[nodiscard]] std::optional<rcc::PhysicalRegister> registerAt(const rcc::MachineInstr &Instruction, + std::size_t Index) { + const rcc::MachineOperand *Operand = Instruction.operandAt(Index); + if (Operand == nullptr) + return std::nullopt; + const rcc::Register *Reg = Operand->getIf<rcc::Register>(); + if (Reg == nullptr || !Reg->isPhysical()) + return std::nullopt; + return Reg->physicalRegister(); +} + +[[nodiscard]] std::optional<std::int64_t> immediateAt(const rcc::MachineInstr &Instruction, + std::size_t Index) { + const rcc::MachineOperand *Operand = Instruction.operandAt(Index); + if (Operand == nullptr) + return std::nullopt; + const auto *Immediate = Operand->getIf<std::int64_t>(); + return Immediate == nullptr ? std::nullopt : std::optional<std::int64_t>(*Immediate); +} + +[[nodiscard]] bool hasFrameIndex(const rcc::MachineFunction &Function) { + for (const rcc::MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const rcc::MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + for (const rcc::MachineOperand &Operand : Instruction->operands()) { + if (Operand.kind() == rcc::MachineOperand::Kind::FrameIndex) + return true; + } + for (const rcc::MachineMemOperand *Memory : Instruction->memOperands()) { + if (Memory->description().Base.frameIndex()) + return true; + } + } + } + return false; +} + +[[nodiscard]] const rcc::StackObject *findStackObject(const rcc::MachineFunction &Function, + rcc::StackObjectKind Kind) { + const auto Position = + std::ranges::find_if(Function.frameInfo().objects(), [Kind](const rcc::StackObject &Object) { + return !Object.isTombstone() && !Object.description()->IsDead && + Object.description()->Kind == Kind; + }); + return Position == Function.frameInfo().objects().end() ? nullptr : &*Position; +} + +[[nodiscard]] const rcc::StackObject *findCalleeSave(const rcc::MachineFunction &Function, + rcc::PhysicalRegister Reg) { + const auto Position = + std::ranges::find_if(Function.frameInfo().objects(), [Reg](const rcc::StackObject &Object) { + return !Object.isTombstone() && !Object.description()->IsDead && + Object.description()->CalleeSavedRegister == Reg; + }); + return Position == Function.frameInfo().objects().end() ? nullptr : &*Position; +} + +void testLeafAndSmallFrame(TestContext &Context, const rcc::TargetDescription &Target) { + auto Leaf = createFunction("leaf", 1); + if (!Leaf || !buildReturn(*Leaf->Function, Target, *Leaf->Block)) + return; + auto LoweredLeaf = runFrameLowering(*Leaf->Function, Target); + Context.expect( + LoweredLeaf && Leaf->Function->frameInfo().isFrozen() && + Leaf->Function->frameInfo().state().StackSize == 0 && + instructions(*Leaf->Block).size() == 1 && + Leaf->Function->properties().has(rcc::MachineFunctionProperty::FrameFinalized) && + Leaf->Function->properties().has(rcc::MachineFunctionProperty::NoFrameIndices), + "leaf frame lowering must freeze an empty frame without extra code"); + + auto DeadObject = createFunction("dead-stack-object", 24); + if (!DeadObject) + return; + auto DeadSlot = createStackObject(*DeadObject->Function, rcc::StackObjectKind::Default, 32, 16); + if (!DeadSlot || !DeadObject->Function->frameInfo().markObjectDead(*DeadSlot) || + !buildReturn(*DeadObject->Function, Target, *DeadObject->Block)) { + return; + } + auto DeadResult = runFrameLowering(*DeadObject->Function, Target); + Context.expect(DeadResult && DeadObject->Function->frameInfo().isFrozen() && + DeadObject->Function->frameInfo().state().StackSize == 0, + "dead stack objects must not require layout offsets or stack space"); + + auto Small = createFunction("small-frame", 2); + if (!Small) + return; + auto Slot = createStackObject(*Small->Function, rcc::StackObjectKind::SpillSlot, 8, 8); + if (!Slot) + return; + auto Store = + buildStackAccess(*Small->Function, Target, *Small->Block, rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X10), *Slot, 0); + if (!Store || !buildReturn(*Small->Function, Target, *Small->Block)) + return; + auto Lowered = runFrameLowering(*Small->Function, Target); + Context.expect(Lowered && Small->Function->frameInfo().state().StackSize == 16 && + !hasFrameIndex(*Small->Function) && + countOpcode(*Small->Function, rcc::riscv::InstructionOpcode::ADDI) == 2, + "a small frame must use one aligned allocation and eliminate every FrameIndex"); + const auto SmallCFI = Small->Function->cfiInfo().instructions(); + Context.expect( + Lowered && SmallCFI.size() == 4 && + SmallCFI.front().operation() == rcc::MachineCFIOperation::DefCFA && + SmallCFI.front().getIf<rcc::MachineCFIRegisterOffsetRule>()->Offset == 16 && + SmallCFI[1].operation() == rcc::MachineCFIOperation::RememberState && + SmallCFI[2].operation() == rcc::MachineCFIOperation::DefCFA && + SmallCFI[2].getIf<rcc::MachineCFIRegisterOffsetRule>()->Offset == 0 && + SmallCFI.back().operation() == rcc::MachineCFIOperation::RestoreState && + countOpcode(*Small->Function, rcc::opcode(rcc::GenericOpcode::CFI_INSTRUCTION)) == 4, + "small-frame CFI must track the allocated and restored CFA exactly"); + Context.expect(Lowered && registerAt(**Store, 1) == physReg(rcc::riscv::PhysicalRegisterID::X2) && + immediateAt(**Store, 2) == 0 && (*Store)->memOperands().size() == 1 && + (*Store)->memOperands().front()->description().Base.kind() == + rcc::MemoryBase::Kind::Stack && + (*Store)->memOperands().front()->description().Offset == 0, + "small-frame instruction and MMO addresses must agree after elimination"); + + auto MultiExit = createFunction("multi-exit-frame", 14); + if (!MultiExit) + return; + auto SecondBlock = MultiExit->Function->createBasicBlock(); + if (!SecondBlock || !MultiExit->Function->appendBlock(**SecondBlock)) + return; + auto MultiSlot = createStackObject(*MultiExit->Function, rcc::StackObjectKind::Default, 8, 8); + if (!MultiSlot || + !buildStackAccess(*MultiExit->Function, Target, *MultiExit->Block, + rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X10), *MultiSlot, 0) || + !buildReturn(*MultiExit->Function, Target, *MultiExit->Block) || + !buildReturn(*MultiExit->Function, Target, **SecondBlock)) { + return; + } + auto MultiResult = runFrameLowering(*MultiExit->Function, Target); + const auto MultiCFI = MultiExit->Function->cfiInfo().instructions(); + const auto CountCFIOperation = [MultiCFI](rcc::MachineCFIOperation Operation) { + return std::ranges::count_if(MultiCFI, + [Operation](const rcc::MachineCFIInstruction &Instruction) { + return Instruction.operation() == Operation; + }); + }; + Context.expect(MultiResult && MultiCFI.size() == 7 && + CountCFIOperation(rcc::MachineCFIOperation::RememberState) == 2 && + CountCFIOperation(rcc::MachineCFIOperation::RestoreState) == 2, + "multiple epilogues must isolate their linear CFI state"); +} + +void testCalleeSavedRegisters(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("callee-saves", 3); + if (!Fixture) + return; + const rcc::Register Zero = physical(rcc::riscv::PhysicalRegisterID::X0); + if (!buildAddImmediate(*Fixture->Function, Target, *Fixture->Block, + physical(rcc::riscv::PhysicalRegisterID::X1), Zero, 1) || + !buildAddImmediate(*Fixture->Function, Target, *Fixture->Block, + physical(rcc::riscv::PhysicalRegisterID::X9), Zero, 2) || + !buildMoveToDouble(*Fixture->Function, Target, *Fixture->Block, + physical(rcc::riscv::PhysicalRegisterID::F8), Zero) || + !buildReturn(*Fixture->Function, Target, *Fixture->Block)) { + return; + } + auto Lowered = runFrameLowering(*Fixture->Function, Target); + const auto Saved = Fixture->Function->records().calleeSavedRegisters(); + Context.expect( + Lowered && Saved.size() == 3 && Saved[0] == physReg(rcc::riscv::PhysicalRegisterID::X1) && + Saved[1] == physReg(rcc::riscv::PhysicalRegisterID::X9) && + Saved[2] == physReg(rcc::riscv::PhysicalRegisterID::F8) && + countOpcode(*Fixture->Function, rcc::riscv::InstructionOpcode::SD) == 2 && + countOpcode(*Fixture->Function, rcc::riscv::InstructionOpcode::FSD) == 1 && + countOpcode(*Fixture->Function, rcc::riscv::InstructionOpcode::LD) == 2 && + countOpcode(*Fixture->Function, rcc::riscv::InstructionOpcode::FLD) == 1, + "used GPR, FPR, and return-address callee saves must have symmetric save/restore code"); + Context.expect( + Lowered && Fixture->Function->cfiInfo().instructions().size() == 10 && + countOpcode(*Fixture->Function, rcc::opcode(rcc::GenericOpcode::CFI_INSTRUCTION)) == 10, + "callee-save CFI must describe every save, restore, and CFA transition"); + Context.expect( + findCalleeSave(*Fixture->Function, physReg(rcc::riscv::PhysicalRegisterID::X1)) != nullptr && + findCalleeSave(*Fixture->Function, physReg(rcc::riscv::PhysicalRegisterID::X9)) != + nullptr && + findCalleeSave(*Fixture->Function, physReg(rcc::riscv::PhysicalRegisterID::F8)) != + nullptr && + !hasFrameIndex(*Fixture->Function), + "callee-save records, stack objects, and eliminated operands must remain consistent"); + + auto MaskFixture = createFunction("regmask-callee-save", 15); + const rcc::PhysicalRegister X18 = physReg(rcc::riscv::PhysicalRegisterID::X18); + if (!MaskFixture || + !buildRegisterMaskClobber(*MaskFixture->Function, Target, *MaskFixture->Block, X18) || + !buildReturn(*MaskFixture->Function, Target, *MaskFixture->Block)) { + return; + } + auto MaskLowered = runFrameLowering(*MaskFixture->Function, Target); + Context.expect(MaskLowered && + MaskFixture->Function->records().calleeSavedRegisters().size() == 1 && + MaskFixture->Function->records().calleeSavedRegisters().front() == X18 && + countOpcode(*MaskFixture->Function, rcc::riscv::InstructionOpcode::SD) == 1 && + countOpcode(*MaskFixture->Function, rcc::riscv::InstructionOpcode::LD) == 1, + "RegMask clobbers must participate in callee-save discovery"); + + auto NoRestore = createFunction("callee-save-no-restore", 16); + auto Align8 = rcc::Alignment::create(8); + if (!NoRestore || !Align8) + return; + rcc::StackObjectDesc NoRestoreDescription; + NoRestoreDescription.Kind = rcc::StackObjectKind::CalleeSaved; + NoRestoreDescription.Size = 8; + NoRestoreDescription.Align = *Align8; + NoRestoreDescription.CalleeSavedRegister = X18; + NoRestoreDescription.CalleeSavedRestored = false; + if (!NoRestore->Function->frameInfo().createObject(std::move(NoRestoreDescription)) || + !buildReturn(*NoRestore->Function, Target, *NoRestore->Block)) { + return; + } + auto NoRestoreResult = runFrameLowering(*NoRestore->Function, Target); + Context.expect( + NoRestoreResult && + countOpcode(*NoRestore->Function, rcc::riscv::InstructionOpcode::SD) == 1 && + countOpcode(*NoRestore->Function, rcc::riscv::InstructionOpcode::LD) == 0 && + NoRestore->Function->frameInfo().state().RestorePoints.empty(), + "CalleeSavedRestored=false must suppress the restore without suppressing the save"); +} + +void testFramePointerAndFixedObjects(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("frame-pointer", 4); + if (!Fixture) + return; + rcc::MachineFrameState State = Fixture->Function->frameInfo().state(); + State.FramePointerPolicy = rcc::MachineFramePointerPolicy::All; + if (!Fixture->Function->frameInfo().setState(State)) + return; + auto Local = createStackObject(*Fixture->Function, rcc::StackObjectKind::Default, 8, 8); + auto Fixed = createStackObject(*Fixture->Function, rcc::StackObjectKind::FixedABI, 8, 8, 16); + auto Variable = + createStackObject(*Fixture->Function, rcc::StackObjectKind::VariableSized, std::nullopt, 16); + if (!Local || !Fixed || !Variable) + return; + auto LocalLoad = buildStackAccess(*Fixture->Function, Target, *Fixture->Block, + rcc::riscv::InstructionOpcode::LD, + physical(rcc::riscv::PhysicalRegisterID::X10), *Local, 0); + auto FixedLoad = buildStackAccess(*Fixture->Function, Target, *Fixture->Block, + rcc::riscv::InstructionOpcode::LD, + physical(rcc::riscv::PhysicalRegisterID::X11), *Fixed, 0); + if (!LocalLoad || !FixedLoad || !buildReturn(*Fixture->Function, Target, *Fixture->Block)) { + return; + } + auto Lowered = runFrameLowering(*Fixture->Function, Target); + const rcc::PhysicalRegister FP = physReg(rcc::riscv::PhysicalRegisterID::X8); + Context.expect(Lowered && registerAt(**LocalLoad, 1) == FP && + immediateAt(**LocalLoad, 2) == -16 && registerAt(**FixedLoad, 1) == FP && + immediateAt(**FixedLoad, 2) == 16 && + findCalleeSave(*Fixture->Function, FP) != nullptr, + "FP frames must address locals below and fixed ABI objects above incoming SP"); + + auto Preallocated = createFunction("preallocated-local-frame", 13); + if (!Preallocated) + return; + rcc::MachineFrameState PreallocatedState = Preallocated->Function->frameInfo().state(); + PreallocatedState.LocalFrameSize = 32; + if (!Preallocated->Function->frameInfo().setState(PreallocatedState)) + return; + auto Align8 = rcc::Alignment::create(8); + if (!Align8) + return; + rcc::StackObjectDesc PreallocatedDescription; + PreallocatedDescription.Size = 8; + PreallocatedDescription.Align = *Align8; + PreallocatedDescription.LocalOffset = 16; + auto PreallocatedObject = + Preallocated->Function->frameInfo().createObject(std::move(PreallocatedDescription)); + if (!PreallocatedObject) + return; + auto PreallocatedStore = buildStackAccess( + *Preallocated->Function, Target, *Preallocated->Block, rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X10), *PreallocatedObject, 0); + if (!PreallocatedStore || !buildReturn(*Preallocated->Function, Target, *Preallocated->Block)) { + return; + } + auto PreallocatedResult = runFrameLowering(*Preallocated->Function, Target); + Context.expect( + PreallocatedResult && Preallocated->Function->frameInfo().state().StackSize == 32 && + Preallocated->Function->frameInfo().state().LocalFrameSize == 32 && + registerAt(**PreallocatedStore, 1) == physReg(rcc::riscv::PhysicalRegisterID::X2) && + immediateAt(**PreallocatedStore, 2) == 16, + "preallocated local blobs must preserve localFrameSize and local-offset semantics"); +} + +void testStackRealignment(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("realigned-frame", 5); + if (!Fixture) + return; + auto Local = createStackObject(*Fixture->Function, rcc::StackObjectKind::Default, 32, 32); + if (!Local) + return; + auto Store = buildStackAccess(*Fixture->Function, Target, *Fixture->Block, + rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X10), *Local, 0); + if (!Store || !buildReturn(*Fixture->Function, Target, *Fixture->Block)) + return; + + const auto &RA = rcc::riscv::registerAllocationInfo(); + const rcc::PhysicalRegister FP = physReg(rcc::riscv::PhysicalRegisterID::X8); + const rcc::PhysicalRegister BP = physReg(rcc::riscv::PhysicalRegisterID::X9); + Context.expect(RA.isReservedForFunction(*Fixture->Function, FP, Target) && + RA.isReservedForFunction(*Fixture->Function, BP, Target), + "stack realignment must reserve both FP and BP before allocation"); + + auto Lowered = runFrameLowering(*Fixture->Function, Target); + const bool Valid = Lowered && Fixture->Function->frameInfo().stackAlignment().bytes() == 32 && + Fixture->Function->frameInfo().state().StackSize == 64 && + registerAt(**Store, 1) == BP && immediateAt(**Store, 2) == 32 && + countOpcode(*Fixture->Function, rcc::riscv::InstructionOpcode::ANDI) == 1 && + findCalleeSave(*Fixture->Function, FP) != nullptr && + findCalleeSave(*Fixture->Function, BP) != nullptr; + Context.expect(Valid, + "over-aligned frames must align SP and use a preserved aligned base pointer"); + const auto CFI = Fixture->Function->cfiInfo().instructions(); + const std::size_t Expressions = static_cast<std::size_t>( + std::ranges::count_if(CFI, [](const rcc::MachineCFIInstruction &Instruction) { + const auto *Escape = Instruction.getIf<rcc::MachineCFIEscapeRule>(); + return Escape != nullptr && !Escape->Bytes.empty() && Escape->Bytes.front() == 0x10U; + })); + Context.expect(Lowered && Expressions == 2, + "realigned callee saves must use BP-relative DWARF expressions"); +} + +void testCallFrames(TestContext &Context, const rcc::TargetDescription &Target) { + auto Reserved = createFunction("reserved-call-frame", 6); + if (!Reserved || !Reserved->Function->frameInfo().setMaxCallFrameSize(48)) + return; + auto Align16 = rcc::Alignment::create(16); + if (!Align16) + return; + rcc::StackObjectDesc OutgoingDescription; + OutgoingDescription.Kind = rcc::StackObjectKind::Target; + OutgoingDescription.Size = 8; + OutgoingDescription.Align = *Align16; + OutgoingDescription.LocalOffset = 32; + OutgoingDescription.TargetFlags = + static_cast<std::uint64_t>(rcc::riscv::CallStackObjectFlag::OutgoingArgument); + auto Outgoing = Reserved->Function->frameInfo().createObject(std::move(OutgoingDescription)); + if (!Outgoing) + return; + auto OutgoingStore = buildStackAccess( + *Reserved->Function, Target, *Reserved->Block, rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X10), *Outgoing, 0); + if (!OutgoingStore || + !buildCallFramePseudo(*Reserved->Function, Target, *Reserved->Block, + rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN, 48) || + !buildCallFramePseudo(*Reserved->Function, Target, *Reserved->Block, + rcc::riscv::InstructionOpcode::ADJCALLSTACKUP, 48) || + !buildReturn(*Reserved->Function, Target, *Reserved->Block)) { + return; + } + auto ReservedResult = runFrameLowering(*Reserved->Function, Target); + Context.expect( + ReservedResult && Reserved->Function->frameInfo().state().StackSize == 48 && + countOpcode(*Reserved->Function, rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN) == 0 && + countOpcode(*Reserved->Function, rcc::riscv::InstructionOpcode::ADJCALLSTACKUP) == 0 && + countOpcode(*Reserved->Function, rcc::riscv::InstructionOpcode::ADDI) == 2 && + registerAt(**OutgoingStore, 1) == physReg(rcc::riscv::PhysicalRegisterID::X2) && + immediateAt(**OutgoingStore, 2) == 32, + "reserved call frames must fold call pseudos into the fixed frame"); + + auto Computed = createFunction("computed-call-frame", 17); + if (!Computed) + return; + auto ComputedOutgoingAlign = rcc::Alignment::create(16); + if (!ComputedOutgoingAlign) + return; + rcc::StackObjectDesc ComputedOutgoingDescription; + ComputedOutgoingDescription.Kind = rcc::StackObjectKind::Target; + ComputedOutgoingDescription.Size = 8; + ComputedOutgoingDescription.Align = *ComputedOutgoingAlign; + ComputedOutgoingDescription.LocalOffset = 48; + ComputedOutgoingDescription.TargetFlags = + static_cast<std::uint64_t>(rcc::riscv::CallStackObjectFlag::OutgoingArgument); + auto ComputedOutgoing = + Computed->Function->frameInfo().createObject(std::move(ComputedOutgoingDescription)); + auto ComputedLocal = createStackObject(*Computed->Function, rcc::StackObjectKind::Default, 8, 8); + if (!ComputedOutgoing || !ComputedLocal || + !buildStackAccess(*Computed->Function, Target, *Computed->Block, + rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X10), *ComputedOutgoing, 0) || + !buildStackAccess(*Computed->Function, Target, *Computed->Block, + rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X11), *ComputedLocal, 0) || + !buildCallFramePseudo(*Computed->Function, Target, *Computed->Block, + rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN, 48, 64) || + !buildCallFramePseudo(*Computed->Function, Target, *Computed->Block, + rcc::riscv::InstructionOpcode::ADJCALLSTACKUP, 48, 64) || + !buildReturn(*Computed->Function, Target, *Computed->Block)) { + return; + } + auto ComputedResult = runFrameLowering(*Computed->Function, Target); + const rcc::StackObject *ComputedLocalObject = + Computed->Function->frameInfo().object(*ComputedLocal); + Context.expect(ComputedResult && Computed->Function->frameInfo().maxCallFrameSize() == 64 && + Computed->Function->frameInfo().stackAlignment().bytes() == 64 && + Computed->Function->frameInfo().state().StackSize == 128 && + ComputedLocalObject != nullptr && + ComputedLocalObject->description()->Offset >= 64, + "PEI must compute and align the reserved call frame from call-frame pseudos"); + + auto Mismatched = createFunction("mismatched-call-frame", 18); + if (!Mismatched || + !buildCallFramePseudo(*Mismatched->Function, Target, *Mismatched->Block, + rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN, 48, 16) || + !buildCallFramePseudo(*Mismatched->Function, Target, *Mismatched->Block, + rcc::riscv::InstructionOpcode::ADJCALLSTACKUP, 48, 32) || + !buildReturn(*Mismatched->Function, Target, *Mismatched->Block)) { + return; + } + auto MismatchResult = runFrameLowering(*Mismatched->Function, Target); + Context.expect( + !MismatchResult && MismatchResult.error().code() == rcc::ErrorCode::VerificationError && + !Mismatched->Function->frameInfo().isFrozen() && + countOpcode(*Mismatched->Function, rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN) == + 1 && + countOpcode(*Mismatched->Function, rcc::riscv::InstructionOpcode::ADJCALLSTACKUP) == 1, + "mismatched call-frame pairs must fail transactionally"); + + auto Unmatched = createFunction("unmatched-call-frame", 19); + if (!Unmatched || + !buildCallFramePseudo(*Unmatched->Function, Target, *Unmatched->Block, + rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN, 32) || + !buildReturn(*Unmatched->Function, Target, *Unmatched->Block)) { + return; + } + auto UnmatchedResult = runFrameLowering(*Unmatched->Function, Target); + Context.expect(!UnmatchedResult && + UnmatchedResult.error().code() == rcc::ErrorCode::VerificationError && + !Unmatched->Function->frameInfo().isFrozen(), + "unmatched call-frame setup must fail transactionally"); + + auto Dynamic = createFunction("dynamic-call-frame", 7); + if (!Dynamic) + return; + auto Variable = + createStackObject(*Dynamic->Function, rcc::StackObjectKind::DynamicAlloca, std::nullopt, 16); + if (!Variable || + !buildCallFramePseudo(*Dynamic->Function, Target, *Dynamic->Block, + rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN, 4096, 32) || + !buildCallFramePseudo(*Dynamic->Function, Target, *Dynamic->Block, + rcc::riscv::InstructionOpcode::ADJCALLSTACKUP, 4096, 32) || + !buildReturn(*Dynamic->Function, Target, *Dynamic->Block)) { + return; + } + Context.expect(rcc::riscv::registerAllocationInfo().isReservedForFunction( + *Dynamic->Function, physReg(rcc::riscv::PhysicalRegisterID::X9), Target), + "over-aligned call frames must reserve BP before register allocation"); + auto DynamicResult = runFrameLowering(*Dynamic->Function, Target); + Context.expect( + DynamicResult && + countOpcode(*Dynamic->Function, rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN) == 0 && + countOpcode(*Dynamic->Function, rcc::riscv::InstructionOpcode::ADJCALLSTACKUP) == 0 && + countOpcode(*Dynamic->Function, rcc::riscv::InstructionOpcode::ADD) >= 2 && + countOpcode(*Dynamic->Function, rcc::riscv::InstructionOpcode::ANDI) == 1 && + findStackObject(*Dynamic->Function, rcc::StackObjectKind::EmergencySpill) != nullptr, + "dynamic large call frames must materialize SP adjustments and reserve emergency space"); + + auto DynamicSpill = createFunction("dynamic-call-frame-spill", 25); + if (!DynamicSpill) + return; + auto DynamicVariable = createStackObject(*DynamicSpill->Function, + rcc::StackObjectKind::DynamicAlloca, std::nullopt, 16); + const std::vector<rcc::riscv::PhysicalRegisterID> ScratchIDs = { + rcc::riscv::PhysicalRegisterID::X5, rcc::riscv::PhysicalRegisterID::X6, + rcc::riscv::PhysicalRegisterID::X7, rcc::riscv::PhysicalRegisterID::X28, + rcc::riscv::PhysicalRegisterID::X29, rcc::riscv::PhysicalRegisterID::X30, + rcc::riscv::PhysicalRegisterID::X31, + }; + const rcc::Register Zero = physical(rcc::riscv::PhysicalRegisterID::X0); + if (!DynamicVariable) + return; + for (std::size_t Index = 0; Index < ScratchIDs.size(); ++Index) { + if (!buildAddImmediate(*DynamicSpill->Function, Target, *DynamicSpill->Block, + physical(ScratchIDs[Index]), Zero, + static_cast<std::int64_t>(Index + 1U))) { + return; + } + } + if (!buildCallFramePseudo(*DynamicSpill->Function, Target, *DynamicSpill->Block, + rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN, 4096) || + !buildCallFramePseudo(*DynamicSpill->Function, Target, *DynamicSpill->Block, + rcc::riscv::InstructionOpcode::ADJCALLSTACKUP, 4096)) { + return; + } + for (const rcc::riscv::PhysicalRegisterID ID : ScratchIDs) { + if (!buildAdd(*DynamicSpill->Function, Target, *DynamicSpill->Block, + physical(rcc::riscv::PhysicalRegisterID::X10), physical(ID), Zero)) { + return; + } + } + if (!buildReturn(*DynamicSpill->Function, Target, *DynamicSpill->Block)) + return; + auto DynamicSpillResult = runFrameLowering(*DynamicSpill->Function, Target); + const rcc::PhysicalRegister FP = physReg(rcc::riscv::PhysicalRegisterID::X8); + std::size_t StableEmergencyStores = 0; + std::size_t StableEmergencyLoads = 0; + for (const rcc::MachineInstr *Instruction : DynamicSpill->Function->allInstructions()) { + if (Instruction == nullptr || Instruction->parent() == nullptr || + Instruction->memOperands().empty() || + Instruction->flags().has(rcc::MachineInstrFlag::FrameSetup) || + Instruction->flags().has(rcc::MachineInstrFlag::FrameDestroy)) { + continue; + } + const auto &Memory = Instruction->memOperands().front()->description(); + if (Memory.Base.kind() != rcc::MemoryBase::Kind::Stack || registerAt(*Instruction, 1) != FP) + continue; + StableEmergencyStores += + Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::SD) ? 1U : 0U; + StableEmergencyLoads += + Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::LD) ? 1U : 0U; + } + Context.expect(DynamicSpillResult && StableEmergencyStores == 2 && StableEmergencyLoads == 2, + "dynamic call-frame scavenging must preserve scratch values through stable " + "FP-relative emergency slots"); +} + +void testLargeOffsetAndScavenging(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("large-frame-offset", 8); + if (!Fixture) + return; + auto Local = createStackObject(*Fixture->Function, rcc::StackObjectKind::Default, 8192, 8); + if (!Local) + return; + + const std::vector<rcc::riscv::PhysicalRegisterID> ScratchIDs = { + rcc::riscv::PhysicalRegisterID::X5, rcc::riscv::PhysicalRegisterID::X6, + rcc::riscv::PhysicalRegisterID::X7, rcc::riscv::PhysicalRegisterID::X28, + rcc::riscv::PhysicalRegisterID::X29, rcc::riscv::PhysicalRegisterID::X30, + rcc::riscv::PhysicalRegisterID::X31, + }; + const rcc::Register Zero = physical(rcc::riscv::PhysicalRegisterID::X0); + for (std::size_t Index = 0; Index < ScratchIDs.size(); ++Index) { + if (!buildAddImmediate(*Fixture->Function, Target, *Fixture->Block, physical(ScratchIDs[Index]), + Zero, static_cast<std::int64_t>(Index + 1U))) { + return; + } + } + auto Store = buildStackAccess(*Fixture->Function, Target, *Fixture->Block, + rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X10), *Local, 5000); + if (!Store) + return; + for (const rcc::riscv::PhysicalRegisterID ID : ScratchIDs) { + if (!buildAdd(*Fixture->Function, Target, *Fixture->Block, + physical(rcc::riscv::PhysicalRegisterID::X10), physical(ID), Zero)) { + return; + } + } + if (!buildReturn(*Fixture->Function, Target, *Fixture->Block)) + return; + + auto Lowered = runFrameLowering(*Fixture->Function, Target); + Context.expect(Lowered && + findStackObject(*Fixture->Function, rcc::StackObjectKind::EmergencySpill) != + nullptr && + registerAt(**Store, 1) == physReg(rcc::riscv::PhysicalRegisterID::X5) && + immediateAt(**Store, 2) == 0 && !hasFrameIndex(*Fixture->Function), + "large FrameIndex offsets must use a scavenged physical address register"); + + bool HasUnflaggedEmergencyStore = false; + bool HasUnflaggedEmergencyLoad = false; + for (rcc::MachineInstr *Instruction : instructions(*Fixture->Block)) { + if (Instruction == *Store || Instruction->memOperands().empty()) + continue; + const auto &Memory = Instruction->memOperands().front()->description(); + if (Memory.Base.kind() != rcc::MemoryBase::Kind::Stack || Memory.Offset != 0) + continue; + const bool HasFrameFlag = Instruction->flags().has(rcc::MachineInstrFlag::FrameSetup) || + Instruction->flags().has(rcc::MachineInstrFlag::FrameDestroy); + HasUnflaggedEmergencyStore |= + Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::SD) && !HasFrameFlag; + HasUnflaggedEmergencyLoad |= + Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::LD) && !HasFrameFlag; + } + Context.expect(HasUnflaggedEmergencyStore && HasUnflaggedEmergencyLoad, + "live scratch registers must be preserved without false frame flags"); + + auto Huge = createFunction("huge-rv64-frame", 26); + constexpr std::uint64_t HugeFrameSize = (std::uint64_t{1} << 32U) + 16U; + if (!Huge || + !createStackObject(*Huge->Function, rcc::StackObjectKind::Default, HugeFrameSize, 16) || + !buildReturn(*Huge->Function, Target, *Huge->Block)) { + return; + } + auto HugeResult = runFrameLowering(*Huge->Function, Target); + Context.expect(HugeResult && Huge->Function->frameInfo().state().StackSize == HugeFrameSize && + countOpcode(*Huge->Function, rcc::riscv::InstructionOpcode::ADD) >= 2, + "RV64 frames larger than uint32 must use 64-bit stack adjustments"); + + auto TailScratch = createFunction("large-frame-tail-scratch", 27); + if (!TailScratch || + !createStackObject(*TailScratch->Function, rcc::StackObjectKind::Default, 8192, 16) || + !buildIndirectTail(*TailScratch->Function, Target, *TailScratch->Block, + physical(rcc::riscv::PhysicalRegisterID::X5))) { + return; + } + auto TailResult = runFrameLowering(*TailScratch->Function, Target); + bool FrameCodeClobbersTailCallee = false; + for (const rcc::MachineInstr *Instruction : TailScratch->Function->allInstructions()) { + if (Instruction == nullptr || Instruction->parent() == nullptr || + (!Instruction->flags().has(rcc::MachineInstrFlag::FrameSetup) && + !Instruction->flags().has(rcc::MachineInstrFlag::FrameDestroy))) { + continue; + } + FrameCodeClobbersTailCallee |= + registerAt(*Instruction, 0) == physReg(rcc::riscv::PhysicalRegisterID::X5); + } + Context.expect(TailResult && !FrameCodeClobbersTailCallee, + "large prologue/epilogue adjustments must not clobber a tail-call operand"); +} + +void testCFGScavenging(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("cfg-scavenging", 13); + if (!Fixture) + return; + auto Loop = Fixture->Function->createBasicBlock(); + if (!Loop || !Fixture->Function->appendBlock(**Loop) || + !Fixture->Function->cfgUpdater().addSuccessor(*Fixture->Block, **Loop, + rcc::BranchProbability::one()) || + !Fixture->Function->cfgUpdater().addSuccessor(**Loop, **Loop, + rcc::BranchProbability::one())) { + return; + } + auto Local = createStackObject(*Fixture->Function, rcc::StackObjectKind::Default, 8192, 8); + if (!Local) + return; + + const std::vector<rcc::riscv::PhysicalRegisterID> ScratchIDs = { + rcc::riscv::PhysicalRegisterID::X5, rcc::riscv::PhysicalRegisterID::X6, + rcc::riscv::PhysicalRegisterID::X7, rcc::riscv::PhysicalRegisterID::X28, + rcc::riscv::PhysicalRegisterID::X29, rcc::riscv::PhysicalRegisterID::X30, + rcc::riscv::PhysicalRegisterID::X31, + }; + const rcc::Register Zero = physical(rcc::riscv::PhysicalRegisterID::X0); + for (std::size_t Index = 0; Index < ScratchIDs.size(); ++Index) { + if (!buildAddImmediate(*Fixture->Function, Target, *Fixture->Block, physical(ScratchIDs[Index]), + Zero, static_cast<std::int64_t>(Index + 1U))) { + return; + } + } + auto Store = buildStackAccess(*Fixture->Function, Target, *Fixture->Block, + rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X10), *Local, 5000); + if (!Store) + return; + for (const rcc::riscv::PhysicalRegisterID ID : ScratchIDs) { + if (!buildAdd(*Fixture->Function, Target, **Loop, physical(rcc::riscv::PhysicalRegisterID::X10), + physical(ID), Zero)) { + return; + } + } + if (!buildReturn(*Fixture->Function, Target, **Loop)) + return; + + Context.expect((*Loop)->liveIns().empty(), + "CFG scavenging fixture must not depend on prebuilt live-ins"); + auto Lowered = runFrameLowering(*Fixture->Function, Target); + bool HasEmergencyStore = false; + bool HasEmergencyLoad = false; + for (rcc::MachineInstr *Instruction : instructions(*Fixture->Block)) { + if (Instruction == *Store || Instruction->memOperands().empty()) + continue; + const auto &Memory = Instruction->memOperands().front()->description(); + if (Memory.Base.kind() != rcc::MemoryBase::Kind::Stack || Memory.Offset != 0) { + continue; + } + HasEmergencyStore |= Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::SD); + HasEmergencyLoad |= Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::LD); + } + Context.expect( + Lowered && HasEmergencyStore && HasEmergencyLoad && + registerAt(**Store, 1) == physReg(rcc::riscv::PhysicalRegisterID::X5) && + !hasFrameIndex(*Fixture->Function), + "successor and loop uses must keep scratch registers live across FrameIndex elimination"); +} + +[[nodiscard]] std::vector<std::int64_t> frameSignature(const rcc::MachineFunction &Function) { + std::vector<std::int64_t> Result; + Result.push_back(static_cast<std::int64_t>(Function.frameInfo().state().StackSize)); + Result.push_back(static_cast<std::int64_t>(Function.frameInfo().stackAlignment().bytes())); + for (const rcc::StackObject &Object : Function.frameInfo().objects()) { + if (Object.isTombstone() || Object.description()->IsDead) + continue; + Result.push_back(static_cast<std::int64_t>(Object.description()->Kind)); + Result.push_back(Object.description()->Offset.value_or(-1)); + } + for (const rcc::MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const rcc::MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + Result.push_back(static_cast<std::int64_t>(Instruction->opcode().value())); + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + Result.push_back(immediateAt(*Instruction, Index).value_or(0)); + Result.push_back(registerAt(*Instruction, Index) + .transform([](rcc::PhysicalRegister Reg) { + return static_cast<std::int64_t>(Reg.number()); + }) + .value_or(0)); + } + } + } + return Result; +} + +[[nodiscard]] rcc::Expected<FunctionFixture> +createDeterminismFixture(const rcc::TargetDescription &Target, std::uint64_t StableID) { + auto Fixture = createFunction("deterministic-frame", StableID); + if (!Fixture) + return std::unexpected(Fixture.error()); + auto Small = createStackObject(*Fixture->Function, rcc::StackObjectKind::Default, 8, 8); + auto Large = createStackObject(*Fixture->Function, rcc::StackObjectKind::SpillSlot, 24, 16); + if (!Small || !Large) + return std::unexpected(!Small ? Small.error() : Large.error()); + auto Store = buildStackAccess(*Fixture->Function, Target, *Fixture->Block, + rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X10), *Small, 0); + if (!Store) + return std::unexpected(Store.error()); + auto Return = buildReturn(*Fixture->Function, Target, *Fixture->Block); + if (!Return) + return std::unexpected(Return.error()); + return Fixture; +} + +void testPEIOrderingAndPostconditions(TestContext &Context, const rcc::TargetDescription &Target) { + auto Ordered = createFunction("pei-ordering", 22); + if (!Ordered || + !buildAddImmediate(*Ordered->Function, Target, *Ordered->Block, + physical(rcc::riscv::PhysicalRegisterID::X18), + physical(rcc::riscv::PhysicalRegisterID::X0), 1) || + !buildReturn(*Ordered->Function, Target, *Ordered->Block)) { + return; + } + ObservingFrameLowering Observer(rcc::riscv::frameLowering()); + auto OrderedResult = runFrameLoweringWith(*Ordered->Function, Target, Observer); + Context.expect( + OrderedResult && Observer.PrepareSawUnfrozen && Observer.InsertSawUnfrozen && + Observer.FinalizeSawUnfrozen && Observer.FinalizeSawCalleeSave && + Observer.FinalizeProducedFrozen && Observer.PrologueSawFrozen && + Observer.EpilogueSawFrozen, + "PEI must insert callee saves before freeze and emit prologue/epilogue after freeze"); + + auto InvalidPostcondition = createFunction("pei-invalid-postcondition", 23); + if (!InvalidPostcondition) + return; + auto Slot = + createStackObject(*InvalidPostcondition->Function, rcc::StackObjectKind::Default, 8, 8); + if (!Slot) + return; + auto Store = buildStackAccess(*InvalidPostcondition->Function, Target, + *InvalidPostcondition->Block, rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X10), *Slot, 0); + if (!Store || + !buildReturn(*InvalidPostcondition->Function, Target, *InvalidPostcondition->Block)) { + return; + } + const std::size_t OriginalInstructionCount = InvalidPostcondition->Block->instructionCount(); + ObservingFrameLowering Broken(rcc::riscv::frameLowering(), true); + auto Rejected = runFrameLoweringWith(*InvalidPostcondition->Function, Target, Broken); + Context.expect( + !Rejected && !InvalidPostcondition->Function->frameInfo().isFrozen() && + InvalidPostcondition->Block->instructionCount() == OriginalInstructionCount && + (*Store)->operandAt(1)->kind() == rcc::MachineOperand::Kind::FrameIndex && + InvalidPostcondition->Function->cfiInfo().instructions().empty(), + "PEI transaction preflight must verify final properties before mutating the original"); +} + +void testAtomicityAndDeterminism(TestContext &Context, const rcc::TargetDescription &Target) { + auto Invalid = createFunction("invalid-frame", 9); + if (!Invalid) + return; + auto Slot = createStackObject(*Invalid->Function, rcc::StackObjectKind::Default, 8, 8); + if (!Slot) + return; + auto Store = buildStackAccess(*Invalid->Function, Target, *Invalid->Block, + rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X10), *Slot, 0); + if (!Store || !(*Store)->eraseOperand(2) || + !buildReturn(*Invalid->Function, Target, *Invalid->Block)) { + return; + } + auto Rejected = runFrameLowering(*Invalid->Function, Target); + Context.expect(!Rejected && !Invalid->Function->frameInfo().isFrozen() && + Invalid->Function->frameInfo().liveObjectCount() == 1 && + (*Store)->operandCount() == 2 && + (*Store)->operandAt(1)->kind() == rcc::MachineOperand::Kind::FrameIndex, + "failed frame lowering must leave the original MachineFunction unchanged"); + + auto OverflowingCallFrame = createFunction("overflowing-call-frame", 12); + if (!OverflowingCallFrame || + !OverflowingCallFrame->Function->frameInfo().setMaxCallFrameSize(16)) { + return; + } + auto Align8 = rcc::Alignment::create(8); + if (!Align8) + return; + rcc::StackObjectDesc OutgoingDescription; + OutgoingDescription.Kind = rcc::StackObjectKind::Target; + OutgoingDescription.Size = 8; + OutgoingDescription.Align = *Align8; + OutgoingDescription.LocalOffset = 16; + OutgoingDescription.TargetFlags = + static_cast<std::uint64_t>(rcc::riscv::CallStackObjectFlag::OutgoingArgument); + auto Outgoing = + OverflowingCallFrame->Function->frameInfo().createObject(std::move(OutgoingDescription)); + if (!Outgoing) + return; + auto OutgoingStore = + buildStackAccess(*OverflowingCallFrame->Function, Target, *OverflowingCallFrame->Block, + rcc::riscv::InstructionOpcode::SD, + physical(rcc::riscv::PhysicalRegisterID::X10), *Outgoing, 0); + if (!OutgoingStore || + !buildReturn(*OverflowingCallFrame->Function, Target, *OverflowingCallFrame->Block)) { + return; + } + auto FrameRejected = runFrameLowering(*OverflowingCallFrame->Function, Target); + Context.expect( + !FrameRejected && FrameRejected.error().code() == rcc::ErrorCode::FrameLayoutFailed && + !OverflowingCallFrame->Function->frameInfo().isFrozen() && + OverflowingCallFrame->Function->cfiInfo().instructions().empty() && + (*OutgoingStore)->operandAt(1)->kind() == rcc::MachineOperand::Kind::FrameIndex && + (*OutgoingStore)->memOperands().front()->description().Base.frameIndex() == *Outgoing, + "transaction preflight must reject invalid call-frame layout without mutation"); + + auto MalformedSave = createFunction("malformed-callee-save", 20); + auto Align4 = rcc::Alignment::create(4); + if (!MalformedSave || !Align4) + return; + rcc::StackObjectDesc MalformedDescription; + MalformedDescription.Kind = rcc::StackObjectKind::CalleeSaved; + MalformedDescription.Size = 4; + MalformedDescription.Align = *Align4; + MalformedDescription.CalleeSavedRegister = physReg(rcc::riscv::PhysicalRegisterID::X18); + if (!MalformedSave->Function->frameInfo().createObject(std::move(MalformedDescription)) || + !buildReturn(*MalformedSave->Function, Target, *MalformedSave->Block)) { + return; + } + auto MalformedResult = runFrameLowering(*MalformedSave->Function, Target); + Context.expect( + !MalformedResult && MalformedResult.error().code() == rcc::ErrorCode::VerificationError && + !MalformedSave->Function->frameInfo().isFrozen() && + MalformedSave->Function->frameInfo().liveObjectCount() == 1 && + MalformedSave->Function->cfiInfo().instructions().empty(), + "malformed callee-save slots must be rejected before mutating the original function"); + + auto DuplicateSave = createFunction("duplicate-callee-save", 28); + auto Align8ForDuplicates = rcc::Alignment::create(8); + if (!DuplicateSave || !Align8ForDuplicates) + return; + for (std::size_t Index = 0; Index < 2; ++Index) { + rcc::StackObjectDesc DuplicateDescription; + DuplicateDescription.Kind = rcc::StackObjectKind::CalleeSaved; + DuplicateDescription.Size = 8; + DuplicateDescription.Align = *Align8ForDuplicates; + DuplicateDescription.CalleeSavedRegister = physReg(rcc::riscv::PhysicalRegisterID::X18); + if (!DuplicateSave->Function->frameInfo().createObject(std::move(DuplicateDescription))) { + return; + } + } + if (!buildReturn(*DuplicateSave->Function, Target, *DuplicateSave->Block)) + return; + auto DuplicateResult = runFrameLowering(*DuplicateSave->Function, Target); + Context.expect(!DuplicateResult && + DuplicateResult.error().code() == rcc::ErrorCode::VerificationError && + !DuplicateSave->Function->frameInfo().isFrozen(), + "duplicate callee-save slots must be rejected transactionally"); + + auto ReservedFrameRegister = createFunction("used-reserved-frame-register", 21); + if (!ReservedFrameRegister) + return; + auto OverAligned = + createStackObject(*ReservedFrameRegister->Function, rcc::StackObjectKind::Default, 32, 32); + if (!OverAligned || + !buildAddImmediate(*ReservedFrameRegister->Function, Target, *ReservedFrameRegister->Block, + physical(rcc::riscv::PhysicalRegisterID::X8), + physical(rcc::riscv::PhysicalRegisterID::X0), 1) || + !buildReturn(*ReservedFrameRegister->Function, Target, *ReservedFrameRegister->Block)) { + return; + } + auto ReservedFrameResult = runFrameLowering(*ReservedFrameRegister->Function, Target); + Context.expect( + !ReservedFrameResult && + ReservedFrameResult.error().code() == rcc::ErrorCode::VerificationError && + !ReservedFrameRegister->Function->frameInfo().isFrozen() && + ReservedFrameRegister->Function->frameInfo().liveObjectCount() == 1, + "post-RA uses of required FP/BP registers must fail without partial frame mutation"); + + auto First = createDeterminismFixture(Target, 10); + auto Second = createDeterminismFixture(Target, 11); + if (!First || !Second) + return; + auto FirstResult = runFrameLowering(*First->Function, Target); + auto SecondResult = runFrameLowering(*Second->Function, Target); + Context.expect(FirstResult && SecondResult && + frameSignature(*First->Function) == frameSignature(*Second->Function), + "identical frame inputs must produce deterministic layouts and code"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = rcc::riscv::createTargetDescription(); + Context.expect(Target.has_value(), "RV64GC frame-lowering target must be constructible"); + if (!Target) + return Context.result(); + + testLeafAndSmallFrame(Context, *Target); + testCalleeSavedRegisters(Context, *Target); + testFramePointerAndFixedObjects(Context, *Target); + testStackRealignment(Context, *Target); + testCallFrames(Context, *Target); + testLargeOffsetAndScavenging(Context, *Target); + testCFGScavenging(Context, *Target); + testPEIOrderingAndPostconditions(Context, *Target); + testAtomicityAndDeterminism(Context, *Target); + return Context.result(); +} diff --git a/backend/unittests/Target/RISCVRegisterAllocationTest.cpp b/backend/unittests/Target/RISCVRegisterAllocationTest.cpp index f9031da..72cce51 100644 --- a/backend/unittests/Target/RISCVRegisterAllocationTest.cpp +++ b/backend/unittests/Target/RISCVRegisterAllocationTest.cpp @@ -26,6 +26,7 @@ #include <cstdint> #include <iostream> #include <memory> +#include <optional> #include <string> #include <string_view> #include <utility> @@ -399,6 +400,46 @@ void testRealAllocators(TestContext &Context, const rcc::TargetDescription &Targ } } +void testFunctionReservedRegisters(TestContext &Context, const rcc::TargetDescription &Target) { + for (const auto [Kind, ID, Name] : { + std::tuple{AllocatorKind::Basic, std::uint64_t{13}, std::string_view{"Basic"}}, + std::tuple{AllocatorKind::Fast, std::uint64_t{14}, std::string_view{"Fast"}}, + std::tuple{AllocatorKind::PBQP, std::uint64_t{15}, std::string_view{"PBQP"}}, + }) { + auto Fixture = createSimpleAllocationFunction(Target, ID); + auto Align64 = rcc::Alignment::create(64); + if (!Fixture || !Align64) + continue; + rcc::StackObjectDesc Description; + Description.Size = 8; + Description.Align = *Align64; + if (!Fixture->Function->frameInfo().createObject(std::move(Description))) + continue; + auto Allocated = runAllocator(*Fixture->Function, Target, Kind); + const rcc::PhysicalRegister FP = + *rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X8); + const rcc::PhysicalRegister BP = + *rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X9); + bool AllocatedFrameRegister = false; + for (const rcc::MachineInstr *Instruction : Fixture->Function->allInstructions()) { + if (Instruction == nullptr || Instruction->parent() == nullptr) + continue; + for (const rcc::MachineOperand &Operand : Instruction->operands()) { + const rcc::Register *Reg = Operand.getIf<rcc::Register>(); + const auto Physical = + Reg != nullptr && Reg->isPhysical() ? Reg->physicalRegister() : std::nullopt; + AllocatedFrameRegister |= Physical && (*Physical == FP || *Physical == BP); + } + } + if (!Allocated) + std::cerr << "RV64GC " << Name << " reservation error: " << Allocated.error().message() + << '\n'; + Context.expect(Allocated && Fixture->Function->registerInfo().isReserved(FP) && + Fixture->Function->registerInfo().isReserved(BP) && !AllocatedFrameRegister, + "every allocator must persist and honor function-level FP/BP reservations"); + } +} + [[nodiscard]] rcc::Expected<FunctionFixture> createPressureFunction(const rcc::TargetDescription &Target, std::uint64_t ID) { auto Fixture = createFunction("riscv-pressure-" + std::to_string(ID), ID); @@ -486,6 +527,7 @@ int main() { testTargetHooks(Context, *Target); testRematerialization(Context, *Target); testRealAllocators(Context, *Target); + testFunctionReservedRegisters(Context, *Target); testRealPressureAndDeterminism(Context, *Target); return Context.result(); } |