diff options
Diffstat (limited to 'backend/unittests/CodeGen')
| -rw-r--r-- | backend/unittests/CodeGen/CMakeLists.txt | 85 | ||||
| -rw-r--r-- | backend/unittests/CodeGen/LiveRegMatrixTest.cpp | 92 | ||||
| -rw-r--r-- | backend/unittests/CodeGen/MachineIRBuilderTest.cpp | 3 | ||||
| -rw-r--r-- | backend/unittests/CodeGen/PBQPTest.cpp | 177 | ||||
| -rw-r--r-- | backend/unittests/CodeGen/RegAllocBasicTest.cpp | 108 | ||||
| -rw-r--r-- | backend/unittests/CodeGen/RegAllocFastTest.cpp | 83 | ||||
| -rw-r--r-- | backend/unittests/CodeGen/RegAllocPBQPTest.cpp | 117 | ||||
| -rw-r--r-- | backend/unittests/CodeGen/RegisterAllocationTest.cpp | 1043 | ||||
| -rw-r--r-- | backend/unittests/CodeGen/RegisterAllocationTestSupport.h | 473 | ||||
| -rw-r--r-- | backend/unittests/CodeGen/SpillerTest.cpp | 94 | ||||
| -rw-r--r-- | backend/unittests/CodeGen/VirtRegMapTest.cpp | 91 |
11 files changed, 2364 insertions, 2 deletions
diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt index b3f071b..65d9168 100644 --- a/backend/unittests/CodeGen/CMakeLists.txt +++ b/backend/unittests/CodeGen/CMakeLists.txt @@ -22,6 +22,8 @@ set( MachineOperandTest.cpp MachinePassTest.cpp MachinePipelinePassesTest.cpp + PBQPTest.cpp + RegisterAllocationTest.cpp MachineSSAExitTest.cpp MachineVerifierTest.cpp MachineVerifierTargetTest.cpp @@ -48,6 +50,72 @@ target_link_libraries(RCCBackendCodeGenCoreTypesTests PRIVATE RCCBackend::CodeGe add_test(NAME RCCBackend.CodeGen.CoreTypes COMMAND RCCBackendCodeGenCoreTypesTests) +add_executable(RCCBackendCodeGenPBQPTests PBQPTest.cpp) +rcc_backend_configure_target(RCCBackendCodeGenPBQPTests) +target_link_libraries(RCCBackendCodeGenPBQPTests PRIVATE RCCBackend::CodeGen) + +add_test(NAME RCCBackend.CodeGen.PBQP COMMAND RCCBackendCodeGenPBQPTests) + +add_executable(RCCBackendCodeGenRegisterAllocationTests RegisterAllocationTest.cpp) +rcc_backend_configure_target(RCCBackendCodeGenRegisterAllocationTests) +target_link_libraries( + RCCBackendCodeGenRegisterAllocationTests + PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget +) + +add_test( + NAME RCCBackend.CodeGen.RegisterAllocation + COMMAND RCCBackendCodeGenRegisterAllocationTests +) + +add_executable(RCCBackendCodeGenLiveRegMatrixTests LiveRegMatrixTest.cpp) +rcc_backend_configure_target(RCCBackendCodeGenLiveRegMatrixTests) +target_link_libraries( + RCCBackendCodeGenLiveRegMatrixTests + PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget +) +add_test(NAME RCCBackend.CodeGen.LiveRegMatrix COMMAND RCCBackendCodeGenLiveRegMatrixTests) + +add_executable(RCCBackendCodeGenVirtRegMapTests VirtRegMapTest.cpp) +rcc_backend_configure_target(RCCBackendCodeGenVirtRegMapTests) +target_link_libraries( + RCCBackendCodeGenVirtRegMapTests + PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget +) +add_test(NAME RCCBackend.CodeGen.VirtRegMap COMMAND RCCBackendCodeGenVirtRegMapTests) + +add_executable(RCCBackendCodeGenSpillerTests SpillerTest.cpp) +rcc_backend_configure_target(RCCBackendCodeGenSpillerTests) +target_link_libraries( + RCCBackendCodeGenSpillerTests + PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget +) +add_test(NAME RCCBackend.CodeGen.Spiller COMMAND RCCBackendCodeGenSpillerTests) + +add_executable(RCCBackendCodeGenBasicAllocatorTests RegAllocBasicTest.cpp) +rcc_backend_configure_target(RCCBackendCodeGenBasicAllocatorTests) +target_link_libraries( + RCCBackendCodeGenBasicAllocatorTests + PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget +) +add_test(NAME RCCBackend.CodeGen.BasicAllocator COMMAND RCCBackendCodeGenBasicAllocatorTests) + +add_executable(RCCBackendCodeGenFastAllocatorTests RegAllocFastTest.cpp) +rcc_backend_configure_target(RCCBackendCodeGenFastAllocatorTests) +target_link_libraries( + RCCBackendCodeGenFastAllocatorTests + PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget +) +add_test(NAME RCCBackend.CodeGen.FastAllocator COMMAND RCCBackendCodeGenFastAllocatorTests) + +add_executable(RCCBackendCodeGenPBQPAllocatorTests RegAllocPBQPTest.cpp) +rcc_backend_configure_target(RCCBackendCodeGenPBQPAllocatorTests) +target_link_libraries( + RCCBackendCodeGenPBQPAllocatorTests + PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget +) +add_test(NAME RCCBackend.CodeGen.PBQPAllocator COMMAND RCCBackendCodeGenPBQPAllocatorTests) + add_executable(RCCBackendCodeGenGenericOpcodesTests GenericOpcodesTest.cpp) rcc_backend_configure_target(RCCBackendCodeGenGenericOpcodesTests) target_link_libraries(RCCBackendCodeGenGenericOpcodesTests PRIVATE RCCBackend::CodeGen) @@ -373,6 +441,8 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachinePassTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePassesTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/PBQPTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegisterAllocationTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExitTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTargetTest.cpp" @@ -382,6 +452,13 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/TargetFunctionStateTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetMIRTextInfoTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetRegisterInfoTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegisterAllocationTestSupport.h" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveRegMatrixTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/VirtRegMapTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/SpillerTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBasicTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocFastTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocPBQPTest.cpp" ) rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/CompilationUnitTest.cpp" @@ -404,6 +481,8 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachinePassTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePassesTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/PBQPTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegisterAllocationTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExitTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTargetTest.cpp" @@ -413,4 +492,10 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/TargetFunctionStateTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetMIRTextInfoTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetRegisterInfoTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveRegMatrixTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/VirtRegMapTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/SpillerTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBasicTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocFastTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocPBQPTest.cpp" ) diff --git a/backend/unittests/CodeGen/LiveRegMatrixTest.cpp b/backend/unittests/CodeGen/LiveRegMatrixTest.cpp new file mode 100644 index 0000000..21c0778 --- /dev/null +++ b/backend/unittests/CodeGen/LiveRegMatrixTest.cpp @@ -0,0 +1,92 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveRegMatrix.h" + +#include "CodeGen/RegisterAllocationTestSupport.h" + +#include <algorithm> +#include <iostream> + +namespace { + +using namespace rcc; +using namespace rcc::test; +using namespace rcc::test::ra; + +void testLaneAndAssignment(TestContext &Context, const TargetDescription &Target) { + auto Fixture = createFunction("matrix-lanes", 1); + if (!Fixture) + return; + auto Low = createVReg(*Fixture->Function); + auto High = createVReg(*Fixture->Function); + if (!Low || !High || + !buildDef(*Fixture->Function, Target, *Fixture->Block, *Low, 1, TestSubReg::Low32) || + !buildDef(*Fixture->Function, Target, *Fixture->Block, *High, 2, TestSubReg::High32) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *High, TestSubReg::High32) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Low, TestSubReg::Low32)) + return; + + MachineAnalysisManager Analyses; + if (!registerStage11MachineAnalyses(Analyses)) + return; + auto Intervals = Analyses.getResult<LiveIntervalsAnalysis>(*Fixture->Function, Target); + if (!Intervals) + return; + const PhysicalRegister G0 = physical(TestRegister::G0); + LiveRegMatrix Matrix(*Fixture->Function, Target, **Intervals); + Context.expect(Matrix.assign(*Low, G0).has_value() && + Matrix.checkInterference(*High, G0).Kind == RegisterInterferenceKind::Free && + Matrix.assign(*High, G0).has_value() && Matrix.assignment(*Low) == G0, + "LiveRegMatrix must allow disjoint lanes and publish assignments"); + Context.expect(Matrix.unassign(*Low).has_value() && !Matrix.assignment(*Low), + "LiveRegMatrix must remove an assignment without affecting other lanes"); +} + +void testFixedAndMaskInterference(TestContext &Context, const TargetDescription &Target) { + auto Fixture = createFunction("matrix-fixed", 2); + if (!Fixture) + return; + auto Value = createVReg(*Fixture->Function); + const PhysicalRegister G0 = physical(TestRegister::G0); + const PhysicalRegister G1 = physical(TestRegister::G1); + if (!Value || !buildDef(*Fixture->Function, Target, *Fixture->Block, *Value, 7) || + !buildMask(*Fixture->Function, Target, *Fixture->Block, createTestCallPreservedMask()) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, Register::fromPhysical(G0)) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Value)) + return; + + MachineAnalysisManager Analyses; + if (!registerStage11MachineAnalyses(Analyses)) + return; + auto Intervals = Analyses.getResult<LiveIntervalsAnalysis>(*Fixture->Function, Target); + if (!Intervals) + return; + LiveRegMatrix Matrix(*Fixture->Function, Target, **Intervals); + const auto G0Interferences = Matrix.collectInterferences(*Value, G0); + const auto G1Interferences = Matrix.collectInterferences(*Value, G1); + const auto HasKind = [](std::span<const RegisterInterference> Values, + RegisterInterferenceKind Kind) { + return std::ranges::any_of( + Values, [Kind](const RegisterInterference &Value) { return Value.Kind == Kind; }); + }; + Context.expect(HasKind(G0Interferences, RegisterInterferenceKind::FixedRegister) && + HasKind(G0Interferences, RegisterInterferenceKind::RegisterMask) && + !HasKind(G1Interferences, RegisterInterferenceKind::FixedRegister) && + Matrix.assign(*Value, G1).has_value(), + "LiveRegMatrix must distinguish fixed-register and RegMask interference"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "LiveRegMatrix test target must be constructible"); + if (!Target) { + std::cerr << Target.error().message() << '\n'; + return Context.result(); + } + testLaneAndAssignment(Context, *Target); + testFixedAndMaskInterference(Context, *Target); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/MachineIRBuilderTest.cpp b/backend/unittests/CodeGen/MachineIRBuilderTest.cpp index 00ffffc..c4d5767 100644 --- a/backend/unittests/CodeGen/MachineIRBuilderTest.cpp +++ b/backend/unittests/CodeGen/MachineIRBuilderTest.cpp @@ -427,8 +427,7 @@ void testImplicitAndMemoryValidation(TestContext &Context) { rcc::MachineConstantPoolEntryDesc ConstantDescription; auto Integer = rcc::IntegerImmediate::fromUnsigned(64, 0x2a2a2a2a2a2a2a2aULL); - ConstantDescription.Value = - std::move(*rcc::GenericConstantData::integer(std::move(*Integer))); + ConstantDescription.Value = std::move(*rcc::GenericConstantData::integer(std::move(*Integer))); ConstantDescription.Size = 8; ConstantDescription.Align = *rcc::Alignment::create(8); auto ConstantIndex = Function->constantPool().addEntry(std::move(ConstantDescription)); diff --git a/backend/unittests/CodeGen/PBQPTest.cpp b/backend/unittests/CodeGen/PBQPTest.cpp new file mode 100644 index 0000000..073de16 --- /dev/null +++ b/backend/unittests/CodeGen/PBQPTest.cpp @@ -0,0 +1,177 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/PBQP/Graph.h" +#include "rcc/CodeGen/PBQP/Math.h" +#include "rcc/CodeGen/PBQP/Solver.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <iostream> +#include <string_view> +#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; +}; + +void testMath(TestContext &Context) { + using namespace rcc::pbqp; + Context.expect( + addCosts(InfiniteCost, -4) == InfiniteCost && addCosts(InfiniteCost - 1, 2) == InfiniteCost && + addCosts(NegativeInfiniteCost + 1, -2) == NegativeInfiniteCost && addCosts(7, -3) == 4, + "PBQP cost arithmetic must saturate deterministically"); + + CostVector Vector(std::vector<Cost>{8, -2, 4}); + Context.expect(Vector.minimumIndex() == 1, + "PBQP cost vectors must choose the first stable minimum"); + CostMatrix Matrix(2, 3); + Matrix.at(0, 0) = 1; + Matrix.at(0, 1) = 2; + Matrix.at(0, 2) = 3; + Matrix.at(1, 0) = 4; + Matrix.at(1, 1) = 5; + Matrix.at(1, 2) = 6; + const CostMatrix Transposed = Matrix.transpose(); + Context.expect(Transposed.rows() == 3 && Transposed.columns() == 2 && Transposed.at(2, 1) == 6 && + Transposed.at(1, 0) == 2, + "PBQP matrix transposition must preserve orientation"); +} + +void testGraphValidation(TestContext &Context) { + using namespace rcc::pbqp; + Graph Problem; + auto Empty = Problem.addNode(CostVector(0)); + auto First = Problem.addNode(CostVector(std::vector<Cost>{0, 1}), 20); + auto Second = Problem.addNode(CostVector(std::vector<Cost>{2, 0, 3}), 10); + Context.expect(!Empty && First && Second, + "PBQP graphs must reject empty nodes and accept stable nonempty nodes"); + if (!First || !Second) + return; + auto Self = Problem.addEdge(*First, *First, CostMatrix(2, 2)); + auto WrongShape = Problem.addEdge(*First, *Second, CostMatrix(2, 2)); + CostMatrix EdgeCosts(2, 3); + EdgeCosts.at(1, 2) = 7; + auto Edge = Problem.addEdge(*Second, *First, EdgeCosts.transpose(), 99); + auto Duplicate = Problem.addEdge(*First, *Second, CostMatrix(2, 3)); + Context.expect(!Self && !WrongShape && Edge && !Duplicate && Problem.verify().has_value(), + "PBQP graph edges must enforce identity, dimensions, orientation, and uniqueness"); + if (!Edge) + return; + const rcc::pbqp::Edge *Stored = Problem.edge(*Edge); + Context.expect(Stored != nullptr && Stored->First == *First && Stored->Second == *Second && + Stored->Costs.rows() == 2 && Stored->Costs.columns() == 3 && + Stored->Costs.at(1, 2) == 7, + "PBQP graph insertion must normalize reversed edge orientation"); +} + +void testReductions(TestContext &Context) { + using namespace rcc::pbqp; + DeterministicSolver Solver; + + Graph DegreeZero; + auto Only = DegreeZero.addNode(CostVector(std::vector<Cost>{4, 1, 1}), 3); + auto ZeroSolution = Solver.solve(DegreeZero); + Context.expect(Only && ZeroSolution && ZeroSolution->selection(*Only) == 1 && + ZeroSolution->totalCost() == 1, + "PBQP R0 reduction must select the first minimum-cost option"); + + Graph DegreeOne; + auto Left = DegreeOne.addNode(CostVector(std::vector<Cost>{3, 0}), 1); + auto Right = DegreeOne.addNode(CostVector(std::vector<Cost>{0, 2}), 2); + CostMatrix Pair(2, 2); + Pair.at(1, 0) = InfiniteCost; + auto PairEdge = DegreeOne.addEdge(*Left, *Right, std::move(Pair)); + auto OneSolution = Solver.solve(DegreeOne); + Context.expect(Left && Right && PairEdge && OneSolution && OneSolution->selection(*Left) == 1 && + OneSolution->selection(*Right) == 1 && OneSolution->totalCost() == 2, + "PBQP R1 reduction must propagate unary costs to its neighbor"); + + Graph DegreeTwo; + auto A = DegreeTwo.addNode(CostVector(std::vector<Cost>{0, 2}), 1); + auto B = DegreeTwo.addNode(CostVector(std::vector<Cost>{0, 0}), 2); + auto C = DegreeTwo.addNode(CostVector(std::vector<Cost>{2, 0}), 3); + CostMatrix AB(2, 2); + CostMatrix BC(2, 2); + AB.at(0, 1) = 5; + AB.at(1, 0) = 5; + BC.at(0, 1) = 5; + BC.at(1, 0) = 5; + auto ABEdge = DegreeTwo.addEdge(*A, *B, std::move(AB)); + auto BCEdge = DegreeTwo.addEdge(*B, *C, std::move(BC)); + auto TwoSolution = Solver.solve(DegreeTwo); + Context.expect(A && B && C && ABEdge && BCEdge && TwoSolution && + TwoSolution->selection(*A) == 0 && TwoSolution->selection(*B) == 0 && + TwoSolution->selection(*C) == 0 && TwoSolution->totalCost() == 2, + "PBQP R2 reduction must add the induced neighbor edge cost"); +} + +[[nodiscard]] rcc::Expected<rcc::pbqp::Solution> solveClique() { + using namespace rcc::pbqp; + Graph Problem; + std::vector<NodeID> Nodes; + for (std::uint64_t Index = 0; Index < 4; ++Index) { + auto Node = Problem.addNode(CostVector(std::vector<Cost>{9, 0, 0}), 100 - Index); + if (!Node) + return std::unexpected(Node.error()); + Nodes.push_back(*Node); + } + for (std::size_t Left = 0; Left < Nodes.size(); ++Left) { + for (std::size_t Right = Left + 1; Right < Nodes.size(); ++Right) { + CostMatrix Costs(3, 3); + Costs.at(1, 1) = InfiniteCost; + Costs.at(2, 2) = InfiniteCost; + auto Edge = Problem.addEdge(Nodes[Left], Nodes[Right], std::move(Costs), + static_cast<std::uint64_t>(Left * Nodes.size() + Right)); + if (!Edge) + return std::unexpected(Edge.error()); + } + } + return DeterministicSolver{}.solve(Problem); +} + +void testHeuristicAndDeterminism(TestContext &Context) { + auto First = solveClique(); + auto Second = solveClique(); + Context.expect(First && Second && std::ranges::equal(First->selections(), Second->selections()) && + First->totalCost() == Second->totalCost(), + "PBQP higher-degree reduction must be deterministic"); + if (First) { + Context.expect(First->totalCost() == 18, + "a four-node two-register clique must spill exactly two nodes"); + } + + rcc::pbqp::Graph Impossible; + auto Node = Impossible.addNode( + rcc::pbqp::CostVector(std::vector<rcc::pbqp::Cost>{rcc::pbqp::InfiniteCost})); + auto Failure = rcc::pbqp::DeterministicSolver{}.solve(Impossible); + Context.expect(Node && !Failure && + Failure.error().code() == rcc::ErrorCode::RegisterAllocationFailed, + "PBQP solver must diagnose a problem with no finite assignment"); +} + +} // namespace + +int main() { + TestContext Context; + testMath(Context); + testGraphValidation(Context); + testReductions(Context); + testHeuristicAndDeterminism(Context); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/RegAllocBasicTest.cpp b/backend/unittests/CodeGen/RegAllocBasicTest.cpp new file mode 100644 index 0000000..015fe37 --- /dev/null +++ b/backend/unittests/CodeGen/RegAllocBasicTest.cpp @@ -0,0 +1,108 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "CodeGen/RegisterAllocationTestSupport.h" + +#include <iostream> + +namespace { + +using namespace rcc; +using namespace rcc::test; +using namespace rcc::test::ra; + +[[nodiscard]] Expected<MachineInstr *> buildEarly(MachineFunction &Function, + const TargetDescription &Target, + MachineBasicBlock &Block, Register Destination, + Register Source) { + MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(testOpcode(EarlyOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + RegisterOperandFlags Flags; + Flags.set(RegisterOperandFlag::EarlyClobber); + if (auto Result = Pending->addDef(Destination, Flags); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addUse(Source); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +void testHintsAndPressure(TestContext &Context, const TargetDescription &Target) { + auto HintFixture = createFunction("basic-hint", 30); + if (!HintFixture) + return; + auto HintValue = createVReg(*HintFixture->Function); + if (!HintValue || !buildDef(*HintFixture->Function, Target, *HintFixture->Block, *HintValue, 1) || + !buildUse(*HintFixture->Function, Target, *HintFixture->Block, *HintValue) || + !HintFixture->Function->registerInfo().addAllocationHint(*HintValue, + physical(TestRegister::G1)) || + !prepareForAllocation(*HintFixture->Function, Target)) + return; + TestRegisterAllocationInfo Info; + auto Allocated = runAllocator(*HintFixture->Function, Target, Info, AllocatorKind::Basic); + const MachineInstr *Use = HintFixture->Block->lastInstruction(); + Context.expect(Allocated && Use != nullptr && + Use->operandAt(0)->registerValue() == + Register::fromPhysical(physical(TestRegister::G1)), + "BasicAllocator must honor the first allocation hint"); + + auto Pressure = createFunction("basic-pressure", 31); + if (!Pressure) + return; + std::vector<Register> Values; + for (std::int64_t Value = 0; Value < 3; ++Value) { + auto Reg = createVReg(*Pressure->Function); + if (!Reg || !buildDef(*Pressure->Function, Target, *Pressure->Block, *Reg, Value)) + return; + Values.push_back(*Reg); + } + for (const Register Reg : Values) + if (!buildUse(*Pressure->Function, Target, *Pressure->Block, Reg)) + return; + if (!prepareForAllocation(*Pressure->Function, Target)) + return; + Allocated = runAllocator(*Pressure->Function, Target, Info, AllocatorKind::Basic, + {.EnableRematerialization = false}); + Context.expect(Allocated && + Pressure->Function->properties().has(MachineFunctionProperty::NoVRegs) && + Pressure->Function->frameInfo().liveObjectCount() != 0, + "BasicAllocator must close spill/reload pressure"); +} + +void testEarlyClobberAndRewrite(TestContext &Context, const TargetDescription &Target) { + auto Fixture = createFunction("basic-constraints", 32); + if (!Fixture) + return; + auto Source = createVReg(*Fixture->Function); + auto Destination = createVReg(*Fixture->Function); + if (!Source || !Destination || + !buildDef(*Fixture->Function, Target, *Fixture->Block, *Source, 1) || + !buildEarly(*Fixture->Function, Target, *Fixture->Block, *Destination, *Source) || + !buildTied(*Fixture->Function, Target, *Fixture->Block, *Destination) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Destination) || + !prepareForAllocation(*Fixture->Function, Target)) + return; + TestRegisterAllocationInfo Info; + auto Allocated = runAllocator(*Fixture->Function, Target, Info, AllocatorKind::Basic); + const MachineInstr *Early = Fixture->Block->firstInstruction()->next(); + const MachineInstr *Tied = Early == nullptr ? nullptr : Early->next(); + Context.expect(Allocated && Early != nullptr && Tied != nullptr && + Early->operandAt(0)->registerValue() != Early->operandAt(1)->registerValue() && + Tied->operandAt(0)->registerValue() == Tied->operandAt(1)->registerValue(), + "BasicAllocator must preserve early-clobber and tied constraints"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "BasicAllocator test target must be constructible"); + if (!Target) + return Context.result(); + testHintsAndPressure(Context, *Target); + testEarlyClobberAndRewrite(Context, *Target); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/RegAllocFastTest.cpp b/backend/unittests/CodeGen/RegAllocFastTest.cpp new file mode 100644 index 0000000..cf5498f --- /dev/null +++ b/backend/unittests/CodeGen/RegAllocFastTest.cpp @@ -0,0 +1,83 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "CodeGen/RegisterAllocationTestSupport.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" + +#include <iostream> + +namespace { + +using namespace rcc; +using namespace rcc::test; +using namespace rcc::test::ra; + +void testBlockBoundary(TestContext &Context, const TargetDescription &Target) { + auto Fixture = createFunction("fast-boundary", 40); + if (!Fixture) + return; + auto Exit = Fixture->Function->createBasicBlock(); + if (!Exit || !Fixture->Function->appendBlock(**Exit) || + !Fixture->Function->cfgUpdater().addSuccessor(*Fixture->Block, **Exit, + BranchProbability::one())) + return; + auto Value = createVReg(*Fixture->Function); + if (!Value || !buildDef(*Fixture->Function, Target, *Fixture->Block, *Value, 9) || + !buildUse(*Fixture->Function, Target, **Exit, *Value) || + !buildUse(*Fixture->Function, Target, **Exit, + Register::fromPhysical(physical(TestRegister::G0))) || + !prepareForAllocation(*Fixture->Function, Target)) + return; + TestRegisterAllocationInfo Info; + auto Allocated = runAllocator(*Fixture->Function, Target, Info, AllocatorKind::Fast); + Context.expect(Allocated && countOpcode(*Fixture->Function, testOpcode(SpillStoreOpcode)) == 1 && + countOpcode(*Fixture->Function, testOpcode(SpillLoadOpcode)) == 1 && + Fixture->Function->properties().has(MachineFunctionProperty::NoVRegs), + "FastAllocator must preserve values across a block boundary"); +} + +void testFunctionLiveInAndDebug(TestContext &Context, const TargetDescription &Target) { + auto Fixture = createFunction("fast-live-in", 41); + if (!Fixture) + return; + auto Value = createVReg(*Fixture->Function); + const PhysicalRegister G0 = physical(TestRegister::G0); + if (!Value || !Fixture->Function->registerInfo().addLiveIn(G0, *Value) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Value, {}, true) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Value) || + !prepareForAllocation(*Fixture->Function, Target)) + return; + TestRegisterAllocationInfo Info; + auto Allocated = runAllocator(*Fixture->Function, Target, Info, AllocatorKind::Fast); + const MachineOperand *DebugOperand = nullptr; + for (const MachineInstr *Instruction = Fixture->Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + for (const MachineOperand &Operand : Instruction->operands()) { + if (Operand.isDebugUse()) { + DebugOperand = &Operand; + break; + } + } + if (DebugOperand != nullptr) + break; + } + Context.expect( + Allocated && DebugOperand != nullptr && DebugOperand->registerValue() && + (DebugOperand->registerValue()->isNoRegister() || + DebugOperand->registerValue() == Register::fromPhysical(G0)) && + std::ranges::none_of(Fixture->Function->registerInfo().virtualRegisters(), + [](const VirtualRegisterInfo &Info) { return !Info.IsTombstone; }), + "FastAllocator must preserve function live-ins and debug locations"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "FastAllocator test target must be constructible"); + if (!Target) + return Context.result(); + testBlockBoundary(Context, *Target); + testFunctionLiveInAndDebug(Context, *Target); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/RegAllocPBQPTest.cpp b/backend/unittests/CodeGen/RegAllocPBQPTest.cpp new file mode 100644 index 0000000..9b70a9b --- /dev/null +++ b/backend/unittests/CodeGen/RegAllocPBQPTest.cpp @@ -0,0 +1,117 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "CodeGen/RegisterAllocationTestSupport.h" + +#include <iostream> + +namespace { + +using namespace rcc; +using namespace rcc::test; +using namespace rcc::test::ra; + +[[nodiscard]] Expected<FunctionFixture> createPressureFunction(const TargetDescription &Target, + std::uint64_t ID, bool WithCopy) { + auto Fixture = createFunction("pbqp-pressure", ID); + if (!Fixture) + return std::unexpected(Fixture.error()); + std::vector<Register> Values; + for (std::int64_t Value = 0; Value < 3; ++Value) { + auto Reg = createVReg(*Fixture->Function); + if (!Reg || !buildDef(*Fixture->Function, Target, *Fixture->Block, *Reg, Value)) + return makeUnexpected(ErrorCode::InternalError, "failed to construct PBQP pressure value"); + Values.push_back(*Reg); + } + if (WithCopy && !buildCopy(*Fixture->Function, Target, *Fixture->Block, Values[1], Values[0])) + return makeUnexpected(ErrorCode::InternalError, "failed to construct PBQP copy"); + for (const Register Reg : Values) + if (!buildUse(*Fixture->Function, Target, *Fixture->Block, Reg)) + return makeUnexpected(ErrorCode::InternalError, "failed to construct PBQP use"); + auto Prepared = prepareForAllocation(*Fixture->Function, Target); + if (!Prepared) + return std::unexpected(Prepared.error()); + return Fixture; +} + +[[nodiscard]] std::vector<std::uint64_t> signature(const MachineFunction &Function) { + std::vector<std::uint64_t> Result; + Result.push_back(Function.frameInfo().liveObjectCount()); + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + Result.push_back(Instruction->opcode().value()); + for (const MachineOperand &Operand : Instruction->operands()) { + Result.push_back(static_cast<std::uint64_t>(Operand.kind())); + if (const Register *Reg = Operand.getIf<Register>()) + Result.push_back(Reg->opaqueValue()); + } + } + } + return Result; +} + +void testHintsAndDeterminism(TestContext &Context, const TargetDescription &Target) { + auto HintFixture = createFunction("pbqp-hint", 50); + if (!HintFixture) + return; + auto Value = createVReg(*HintFixture->Function); + if (!Value || !buildDef(*HintFixture->Function, Target, *HintFixture->Block, *Value, 1) || + !buildUse(*HintFixture->Function, Target, *HintFixture->Block, *Value) || + !HintFixture->Function->registerInfo().addAllocationHint(*Value, + physical(TestRegister::G1)) || + !HintFixture->Function->registerInfo().addAllocationHint(*Value, + physical(TestRegister::G0)) || + !prepareForAllocation(*HintFixture->Function, Target)) + return; + TestRegisterAllocationInfo Info; + auto Allocated = runAllocator(*HintFixture->Function, Target, Info, AllocatorKind::PBQP); + const MachineInstr *Use = HintFixture->Block->lastInstruction(); + Context.expect(Allocated && Use != nullptr && + Use->operandAt(0)->registerValue() == + Register::fromPhysical(physical(TestRegister::G1)), + "PBQP must preserve allocation-hint preference order"); + + auto First = createPressureFunction(Target, 51, false); + auto Second = createPressureFunction(Target, 52, false); + if (!First || !Second) + return; + auto FirstResult = runAllocator(*First->Function, Target, Info, AllocatorKind::PBQP, + {.EnableRematerialization = false}); + auto SecondResult = runAllocator(*Second->Function, Target, Info, AllocatorKind::PBQP, + {.EnableRematerialization = false}); + Context.expect(FirstResult && SecondResult && + signature(*First->Function) == signature(*Second->Function), + "PBQP allocation and spill/rebuild order must be deterministic"); +} + +void testCopyCoalescingSwitch(TestContext &Context, const TargetDescription &Target) { + TestRegisterAllocationInfo Info; + auto Coalesced = createPressureFunction(Target, 53, true); + auto Uncoalesced = createPressureFunction(Target, 54, true); + if (!Coalesced || !Uncoalesced) + return; + auto WithCoalescing = + runAllocator(*Coalesced->Function, Target, Info, AllocatorKind::PBQP, + {.EnableRematerialization = false, .EnableCopyCoalescing = true}); + auto WithoutCoalescing = + runAllocator(*Uncoalesced->Function, Target, Info, AllocatorKind::PBQP, + {.EnableRematerialization = false, .EnableCopyCoalescing = false}); + Context.expect(WithCoalescing && WithoutCoalescing && + Coalesced->Function->properties().has(MachineFunctionProperty::NoVRegs) && + Uncoalesced->Function->properties().has(MachineFunctionProperty::NoVRegs), + "PBQP copy-coalescing modes must both produce valid physical mappings"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "PBQP allocator test target must be constructible"); + if (!Target) + return Context.result(); + testHintsAndDeterminism(Context, *Target); + testCopyCoalescingSwitch(Context, *Target); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/RegisterAllocationTest.cpp b/backend/unittests/CodeGen/RegisterAllocationTest.cpp new file mode 100644 index 0000000..a44cd2e --- /dev/null +++ b/backend/unittests/CodeGen/RegisterAllocationTest.cpp @@ -0,0 +1,1043 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "Target/TestTarget.h" +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveRangeEdit.h" +#include "rcc/CodeGen/LiveRegMatrix.h" +#include "rcc/CodeGen/LowLevelType.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/RegAllocCommon.h" +#include "rcc/CodeGen/RegAllocFast.h" +#include "rcc/CodeGen/RegAllocPBQP.h" +#include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/Spiller.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetRegisterAllocationInfo.h" +#include "rcc/CodeGen/VirtRegMap.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <iostream> +#include <memory> +#include <optional> +#include <ranges> +#include <span> +#include <string> +#include <string_view> +#include <utility> +#include <vector> + +namespace { + +constexpr std::uint32_t DefOpcode = 3000; +constexpr std::uint32_t RematerializableDefOpcode = 3001; +constexpr std::uint32_t UseOpcode = 3002; +constexpr std::uint32_t BinaryOpcode = 3003; +constexpr std::uint32_t SpillLoadOpcode = 3004; +constexpr std::uint32_t SpillStoreOpcode = 3005; +constexpr std::uint32_t MaskOpcode = 3006; +constexpr std::uint32_t EarlyOpcode = 3007; +constexpr std::uint32_t TiedOpcode = 3008; +constexpr std::uint32_t CallDefOpcode = 3009; + +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; +}; + +[[nodiscard]] constexpr rcc::Opcode testOpcode(std::uint32_t Value) noexcept { + return rcc::Opcode::fromValue(Value); +} + +[[nodiscard]] rcc::PhysicalRegister physical(std::uint32_t Number) { + return *rcc::PhysicalRegister::create(Number); +} + +[[nodiscard]] rcc::OperandDescriptor registerOperand(rcc::RegisterOperandRole Role, + bool EarlyClobber = false) { + rcc::OperandDescriptor Result; + Result.Kinds = {rcc::MachineOperand::Kind::Register}; + Result.RegisterRole = Role; + Result.AllowSubReg = true; + Result.EarlyClobber = EarlyClobber; + return Result; +} + +[[nodiscard]] rcc::OperandDescriptor plainOperand(rcc::MachineOperand::Kind Kind) { + rcc::OperandDescriptor Result; + Result.Kinds = {Kind}; + return Result; +} + +[[nodiscard]] rcc::InstructionDescriptor descriptor(std::uint32_t Value, std::string Name) { + rcc::InstructionDescriptor Result; + Result.InstructionOpcode = testOpcode(Value); + Result.Name = std::move(Name); + Result.Flags = {rcc::InstructionFlag::ProducesCode}; + return Result; +} + +[[nodiscard]] rcc::Expected<rcc::TargetDescription> +createTarget(bool AddSharedMultiLaneUnit = false) { + std::vector<rcc::InstructionDescriptor> Descriptors; + + auto Def = descriptor(DefOpcode, "RA_DEF"); + Def.Operands = {registerOperand(rcc::RegisterOperandRole::Def), + plainOperand(rcc::MachineOperand::Kind::Immediate)}; + Def.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Def)); + + auto Remat = descriptor(RematerializableDefOpcode, "RA_REMAT_DEF"); + Remat.Operands = {registerOperand(rcc::RegisterOperandRole::Def), + plainOperand(rcc::MachineOperand::Kind::Immediate)}; + Remat.NumExplicitDefs = 1; + Remat.Flags.set(rcc::InstructionFlag::Rematerializable); + Descriptors.push_back(std::move(Remat)); + + auto Use = descriptor(UseOpcode, "RA_USE"); + Use.Operands = {registerOperand(rcc::RegisterOperandRole::Use)}; + Use.Flags.set(rcc::InstructionFlag::HasSideEffects); + Descriptors.push_back(std::move(Use)); + + auto Binary = descriptor(BinaryOpcode, "RA_BINARY"); + Binary.Operands = {registerOperand(rcc::RegisterOperandRole::Def), + registerOperand(rcc::RegisterOperandRole::Use), + registerOperand(rcc::RegisterOperandRole::Use)}; + Binary.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Binary)); + + auto Reload = descriptor(SpillLoadOpcode, "RA_RELOAD"); + Reload.Operands = {registerOperand(rcc::RegisterOperandRole::Def), + plainOperand(rcc::MachineOperand::Kind::FrameIndex)}; + Reload.NumExplicitDefs = 1; + Reload.Flags.set(rcc::InstructionFlag::MayLoad); + Reload.RequiresMemoryOperands = true; + Descriptors.push_back(std::move(Reload)); + + auto Spill = descriptor(SpillStoreOpcode, "RA_SPILL"); + Spill.Operands = {registerOperand(rcc::RegisterOperandRole::Use), + plainOperand(rcc::MachineOperand::Kind::FrameIndex)}; + Spill.Flags.set(rcc::InstructionFlag::MayStore); + Spill.RequiresMemoryOperands = true; + Descriptors.push_back(std::move(Spill)); + + auto Mask = descriptor(MaskOpcode, "RA_MASK"); + Mask.Operands = {plainOperand(rcc::MachineOperand::Kind::RegisterMask)}; + Mask.Flags.set(rcc::InstructionFlag::Call); + Mask.Flags.set(rcc::InstructionFlag::HasSideEffects); + Descriptors.push_back(std::move(Mask)); + + auto Early = descriptor(EarlyOpcode, "RA_EARLY"); + Early.Operands = {registerOperand(rcc::RegisterOperandRole::Def, true), + registerOperand(rcc::RegisterOperandRole::Use)}; + Early.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Early)); + + auto Tied = descriptor(TiedOpcode, "RA_TIED"); + auto TiedDef = registerOperand(rcc::RegisterOperandRole::Def); + auto TiedUse = registerOperand(rcc::RegisterOperandRole::Use); + TiedDef.DefaultTiedOperand = 1; + TiedUse.DefaultTiedOperand = 0; + Tied.Operands = {TiedDef, TiedUse}; + Tied.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Tied)); + + auto CallDef = descriptor(CallDefOpcode, "RA_CALL_DEF"); + CallDef.Operands = {registerOperand(rcc::RegisterOperandRole::Def), + plainOperand(rcc::MachineOperand::Kind::RegisterMask)}; + CallDef.NumExplicitDefs = 1; + CallDef.Flags.set(rcc::InstructionFlag::Call); + CallDef.Flags.set(rcc::InstructionFlag::HasSideEffects); + Descriptors.push_back(std::move(CallDef)); + + auto Instructions = rcc::InstructionSet::create(std::move(Descriptors), {}); + if (!Instructions) + return std::unexpected(Instructions.error()); + if (AddSharedMultiLaneUnit) { + auto Description = rcc::test::createTestTargetRegisterInfoDescription(); + const rcc::RegisterUnitID SharedUnit = rcc::RegisterUnitID::fromValue(12); + Description.RegisterUnits.push_back({SharedUnit, "shared.multi-lane"}); + for (rcc::PhysicalRegisterDesc &Register : Description.PhysicalRegisters) { + if (Register.Reg == physical(rcc::test::TestRegister::G0) || + Register.Reg == physical(rcc::test::TestRegister::G1)) { + Register.Units.push_back({SharedUnit, rcc::LaneMask::fromRaw(0xF)}); + } + } + auto Registers = rcc::TargetRegisterInfo::create(std::move(Description)); + if (!Registers) + return std::unexpected(Registers.error()); + return rcc::TargetDescription::create(std::move(*Instructions), std::move(*Registers), + rcc::test::createTestTargetMIRTextInfoDescription()); + } + return rcc::test::createTestTargetDescription(std::move(*Instructions)); +} + +[[nodiscard]] rcc::Expected<const rcc::MachineMemOperand *> +createStackMemory(rcc::MachineIRBuilder &Builder, rcc::FrameIndex StackSlot, + rcc::MemoryAccessFlag Access) { + auto Size = rcc::MemorySize::fixed(8); + auto Align = rcc::Alignment::create(8); + if (!Size) + return std::unexpected(Size.error()); + if (!Align) + return std::unexpected(Align.error()); + rcc::MachineMemOperandDesc Description; + Description.Accesses = {Access}; + Description.Size = *Size; + Description.Align = *Align; + Description.Base = rcc::MemoryBase::frameIndex(StackSlot); + return Builder.function().createMemOperand(std::move(Description)); +} + +class TestRegisterAllocationInfo final : public rcc::TargetRegisterAllocationInfo { +public: + [[nodiscard]] rcc::Expected<void> + validateSpillReload(rcc::RegisterClassID Class, + const rcc::TargetDescription &Target) const override { + const rcc::RegisterClassDesc *Description = Target.registers().registerClass(Class); + if (Description == nullptr || !Description->Allocatable || Description->SpillSizeInBits != 64 || + Description->SpillAlignmentInBits != 64) { + return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, + "test target register class is not spillable"); + } + return {}; + } + + [[nodiscard]] rcc::Expected<rcc::MachineInstr *> + emitReload(rcc::MachineIRBuilder &Builder, rcc::Register Destination, rcc::RegisterClassID Class, + rcc::FrameIndex StackSlot, rcc::LaneMask Lanes) const override { + auto Validated = validateSpillReload(Class, Builder.target()); + if (!Validated) + return std::unexpected(Validated.error()); + if (Lanes.empty()) + return rcc::makeUnexpected(rcc::ErrorCode::InvalidArgument, "test reload requires lanes"); + auto Memory = createStackMemory(Builder, StackSlot, rcc::MemoryAccessFlag::Load); + if (!Memory) + return std::unexpected(Memory.error()); + auto Pending = Builder.buildInstr(testOpcode(SpillLoadOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Destination); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addFrameIndex(StackSlot); !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 *> + emitSpill(rcc::MachineIRBuilder &Builder, rcc::Register Source, rcc::RegisterClassID Class, + rcc::FrameIndex StackSlot, rcc::LaneMask Lanes) const override { + auto Validated = validateSpillReload(Class, Builder.target()); + if (!Validated) + return std::unexpected(Validated.error()); + if (Lanes.empty()) + return rcc::makeUnexpected(rcc::ErrorCode::InvalidArgument, "test spill requires lanes"); + auto Memory = createStackMemory(Builder, StackSlot, rcc::MemoryAccessFlag::Store); + if (!Memory) + return std::unexpected(Memory.error()); + auto Pending = Builder.buildInstr(testOpcode(SpillStoreOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addUse(Source); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addFrameIndex(StackSlot); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addMemOperand(**Memory); !Result) + return std::unexpected(Result.error()); + return Pending->build(); + } + + [[nodiscard]] rcc::Expected<bool> + isRematerializable(const rcc::MachineInstr &Instruction, rcc::Register VirtualReg, + const rcc::MachineFunction &, const rcc::TargetDescription &) const override { + const rcc::MachineOperand *Operand = Instruction.operandAt(0); + const rcc::Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<rcc::Register>(); + return Instruction.opcode() == testOpcode(RematerializableDefOpcode) && Reg != nullptr && + *Reg == VirtualReg; + } + + [[nodiscard]] rcc::Expected<rcc::MachineInstr *> + rematerialize(rcc::MachineIRBuilder &Builder, const rcc::MachineInstr &Original, + rcc::Register Destination, rcc::Register OriginalRegister, + const rcc::TargetDescription &Target) const override { + auto Accepted = isRematerializable(Original, OriginalRegister, Builder.function(), Target); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return rcc::makeUnexpected(rcc::ErrorCode::InvalidArgument, + "test instruction is not rematerializable"); + auto Pending = Builder.buildInstr(testOpcode(RematerializableDefOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Destination); !Result) + return std::unexpected(Result.error()); + const rcc::MachineOperand *Immediate = Original.operandAt(1); + if (Immediate == nullptr) + return rcc::makeUnexpected(rcc::ErrorCode::InternalError, + "test rematerialization lost its immediate"); + if (auto Result = Pending->addOperand(Immediate->cloneDetached()); !Result) + return std::unexpected(Result.error()); + return Pending->build(); + } +}; + +class RejectingRegisterAllocationInfo final : public rcc::TargetRegisterAllocationInfo { +public: + [[nodiscard]] rcc::Expected<void> + validateSpillReload(rcc::RegisterClassID, const rcc::TargetDescription &) const override { + return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, + "test target intentionally rejects spills"); + } + + [[nodiscard]] rcc::Expected<rcc::MachineInstr *> emitReload(rcc::MachineIRBuilder &, + rcc::Register, rcc::RegisterClassID, + rcc::FrameIndex, + rcc::LaneMask) const override { + return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, + "test target intentionally rejects reloads"); + } + + [[nodiscard]] rcc::Expected<rcc::MachineInstr *> emitSpill(rcc::MachineIRBuilder &, rcc::Register, + rcc::RegisterClassID, rcc::FrameIndex, + rcc::LaneMask) const override { + return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, + "test target intentionally rejects spills"); + } +}; + +struct FunctionFixture final { + std::unique_ptr<rcc::MachineFunction> Function; + rcc::MachineBasicBlock *Block = nullptr; +}; + +[[nodiscard]] rcc::Expected<FunctionFixture> createFunction(std::string Name, std::uint64_t ID) { + auto Function = + rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID)); + if (!Function) + return std::unexpected(Function.error()); + auto Block = (*Function)->createBasicBlock(); + if (!Block) + return std::unexpected(Block.error()); + auto Appended = (*Function)->appendBlock(**Block); + if (!Appended) + return std::unexpected(Appended.error()); + return FunctionFixture{std::move(*Function), *Block}; +} + +[[nodiscard]] rcc::Expected<rcc::Register> +createVReg(rcc::MachineFunction &Function, + rcc::RegisterClassID Class = rcc::test::TestRegisterClass::GPR64) { + auto Type = rcc::LLT::makeInteger(64); + if (!Type) + return std::unexpected(Type.error()); + auto Reg = Function.registerInfo().createVirtualRegister(*Type); + if (!Reg) + return std::unexpected(Reg.error()); + if (auto Result = Function.registerInfo().setRegisterBank(*Reg, rcc::test::TestRegisterBank::GPR); + !Result) { + return std::unexpected(Result.error()); + } + if (auto Result = Function.registerInfo().setRegisterClass(*Reg, Class); !Result) + return std::unexpected(Result.error()); + return *Reg; +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildDef(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Reg, std::int64_t Value, + rcc::SubRegIndex SubReg = {}, bool Rematerializable = false) { + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = + Builder.buildInstr(testOpcode(Rematerializable ? RematerializableDefOpcode : DefOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Reg, {}, SubReg); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addImmediate(Value); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildUse(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Reg, rcc::SubRegIndex SubReg = {}) { + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(testOpcode(UseOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addUse(Reg, {}, SubReg); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildMask(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, std::shared_ptr<const rcc::RegisterMask> Mask) { + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(testOpcode(MaskOpcode)); + 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 *> +buildCallDef(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Destination, + std::shared_ptr<const rcc::RegisterMask> Mask) { + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(testOpcode(CallDefOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Destination); !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 *> +buildEarly(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(testOpcode(EarlyOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + rcc::RegisterOperandFlags Flags; + Flags.set(rcc::RegisterOperandFlag::EarlyClobber); + if (auto Result = Pending->addDef(Destination, Flags); !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 *> buildTied(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, + rcc::Register Reg) { + rcc::MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(testOpcode(TiedOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Reg); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addUse(Reg); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->tieOperands(0, 1); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<void> prepareForAllocation(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target) { + auto Rebuilt = rcc::rebuildMachineLiveness(Function, Target); + if (!Rebuilt) + return std::unexpected(Rebuilt.error()); + for (const rcc::MachineFunctionProperty Property : { + rcc::MachineFunctionProperty::TracksLiveness, + rcc::MachineFunctionProperty::Legalized, + rcc::MachineFunctionProperty::RegBankSelected, + rcc::MachineFunctionProperty::Selected, + rcc::MachineFunctionProperty::NoPHIs, + rcc::MachineFunctionProperty::TiedOpsRewritten, + }) { + Function.properties().set(Property); + } + return {}; +} + +enum class AllocatorKind : std::uint8_t { + Basic, + Fast, + PBQP, +}; + +[[nodiscard]] rcc::Expected<void> runAllocator(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target, + const rcc::TargetRegisterAllocationInfo &Info, + AllocatorKind Kind, + rcc::RegisterAllocationOptions Options = {}) { + rcc::MachineAnalysisManager Analyses; + auto Registered = rcc::registerStage11MachineAnalyses(Analyses); + if (!Registered) + return std::unexpected(Registered.error()); + std::unique_ptr<rcc::MachineFunctionPass> Pass; + switch (Kind) { + case AllocatorKind::Basic: + Pass = rcc::createBasicAllocatorPass(Info, Options); + break; + case AllocatorKind::Fast: + Pass = std::make_unique<rcc::FastAllocatorPass>(Info); + break; + case AllocatorKind::PBQP: + Pass = std::make_unique<rcc::PBQPAllocatorPass>(Info, Options); + break; + } + rcc::MachinePassManager Pipeline; + auto Added = Pipeline.addPass(std::move(Pass)); + if (!Added) + return std::unexpected(Added.error()); + return Pipeline.run(Function, Target, Analyses); +} + +[[nodiscard]] std::size_t countOpcode(const rcc::MachineFunction &Function, std::uint32_t Value) { + std::size_t Count = 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()) { + Count += Instruction->opcode() == testOpcode(Value) ? 1U : 0U; + } + } + return Count; +} + +[[nodiscard]] bool hasInterference(std::span<const rcc::RegisterInterference> Values, + rcc::RegisterInterferenceKind Kind) { + return std::ranges::any_of( + Values, [Kind](const rcc::RegisterInterference &Value) { return Value.Kind == Kind; }); +} + +[[nodiscard]] std::vector<std::uint64_t> functionSignature(const rcc::MachineFunction &Function) { + std::vector<std::uint64_t> Result; + Result.push_back(Function.frameInfo().liveObjectCount()); + for (const rcc::MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + Result.push_back(Block->stableID().value()); + for (const rcc::MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + Result.push_back(Instruction->opcode().value()); + Result.push_back(Instruction->operandCount()); + for (const rcc::MachineOperand &Operand : Instruction->operands()) { + Result.push_back(static_cast<std::uint64_t>(Operand.kind())); + const rcc::Register *Reg = Operand.getIf<rcc::Register>(); + Result.push_back(Reg == nullptr ? 0 : Reg->opaqueValue()); + } + } + } + return Result; +} + +void testVirtRegMapAndEdit(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("virtreg-map", 1); + if (!Fixture) + return; + auto Parent = createVReg(*Fixture->Function); + if (!Parent) + return; + rcc::VirtRegMap Mapping(*Fixture->Function); + Context.expect(Mapping.add(*Parent).has_value(), + "VirtRegMap must accept a known virtual register"); + rcc::LiveRangeEdit Edit(*Fixture->Function, Target, Mapping); + auto Child = Edit.createFrom(*Parent, false); + auto Slot = Edit.getOrCreateSpillSlot(*Parent); + Context.expect(Child && Slot && Mapping.stackSlot(*Parent) == Slot && + Mapping.entry(*Child) != nullptr && + Mapping.entry(*Child)->SplitParent == *Parent && + Mapping.entry(*Child)->Origin == *Parent && Mapping.verify().has_value(), + "LiveRangeEdit must preserve class, origin, split, and spill-slot state"); + if (!Child) + return; + const auto G0 = physical(rcc::test::TestRegister::G0); + Context.expect(Mapping.assign(*Child, G0).has_value() && Mapping.physicalRegister(*Child) == G0 && + !Mapping.isSpillable(*Child), + "VirtRegMap must publish deterministic child assignments"); +} + +void testLiveRegMatrix(TestContext &Context, const rcc::TargetDescription &Target) { + auto LaneFixture = createFunction("lane-matrix", 2); + if (!LaneFixture) + return; + auto Low = createVReg(*LaneFixture->Function); + auto High = createVReg(*LaneFixture->Function); + if (!Low || !High) + return; + if (!buildDef(*LaneFixture->Function, Target, *LaneFixture->Block, *Low, 1, + rcc::test::TestSubReg::Low32) || + !buildDef(*LaneFixture->Function, Target, *LaneFixture->Block, *High, 2, + rcc::test::TestSubReg::High32) || + !buildUse(*LaneFixture->Function, Target, *LaneFixture->Block, *High, + rcc::test::TestSubReg::High32) || + !buildUse(*LaneFixture->Function, Target, *LaneFixture->Block, *Low, + rcc::test::TestSubReg::Low32)) { + return; + } + if (!rcc::rebuildMachineLiveness(*LaneFixture->Function, Target)) + return; + rcc::MachineAnalysisManager LaneAnalyses; + if (!rcc::registerStage11MachineAnalyses(LaneAnalyses)) + return; + auto LaneIntervals = + LaneAnalyses.getResult<rcc::LiveIntervalsAnalysis>(*LaneFixture->Function, Target); + if (!LaneIntervals) + return; + const auto G0 = physical(rcc::test::TestRegister::G0); + rcc::LiveRegMatrix LaneMatrix(*LaneFixture->Function, Target, **LaneIntervals); + Context.expect(LaneMatrix.assign(*Low, G0).has_value() && + LaneMatrix.checkInterference(*High, G0).Kind == + rcc::RegisterInterferenceKind::Free && + LaneMatrix.assign(*High, G0).has_value(), + "LiveRegMatrix must permit overlapping intervals on disjoint subregister lanes"); + + auto FixedFixture = createFunction("fixed-matrix", 3); + if (!FixedFixture) + return; + auto Value = createVReg(*FixedFixture->Function); + if (!Value || !buildDef(*FixedFixture->Function, Target, *FixedFixture->Block, *Value, 7) || + !buildMask(*FixedFixture->Function, Target, *FixedFixture->Block, + rcc::test::createTestCallPreservedMask()) || + !buildUse(*FixedFixture->Function, Target, *FixedFixture->Block, + rcc::Register::fromPhysical(G0)) || + !buildUse(*FixedFixture->Function, Target, *FixedFixture->Block, *Value)) { + return; + } + if (!rcc::rebuildMachineLiveness(*FixedFixture->Function, Target)) + return; + rcc::MachineAnalysisManager FixedAnalyses; + if (!rcc::registerStage11MachineAnalyses(FixedAnalyses)) + return; + auto FixedIntervals = + FixedAnalyses.getResult<rcc::LiveIntervalsAnalysis>(*FixedFixture->Function, Target); + if (!FixedIntervals) + return; + rcc::LiveRegMatrix FixedMatrix(*FixedFixture->Function, Target, **FixedIntervals); + const auto G0Interferences = FixedMatrix.collectInterferences(*Value, G0); + const auto G1 = physical(rcc::test::TestRegister::G1); + Context.expect( + hasInterference(G0Interferences, rcc::RegisterInterferenceKind::RegisterMask) && + (hasInterference(G0Interferences, rcc::RegisterInterferenceKind::FixedRegister) || + hasInterference(G0Interferences, rcc::RegisterInterferenceKind::RegisterUnit)) && + FixedMatrix.checkInterference(*Value, G1).Kind == rcc::RegisterInterferenceKind::Free, + "LiveRegMatrix must classify fixed, unit, and RegMask interference separately"); + + auto FixedLaneFixture = createFunction("fixed-lane-matrix", 4); + if (!FixedLaneFixture) + return; + auto HighValue = createVReg(*FixedLaneFixture->Function); + const auto G0Low32 = physical(rcc::test::TestRegister::G0Low32); + if (!HighValue || + !buildDef(*FixedLaneFixture->Function, Target, *FixedLaneFixture->Block, *HighValue, 9, + rcc::test::TestSubReg::High32) || + !buildUse(*FixedLaneFixture->Function, Target, *FixedLaneFixture->Block, + rcc::Register::fromPhysical(G0Low32)) || + !buildUse(*FixedLaneFixture->Function, Target, *FixedLaneFixture->Block, *HighValue, + rcc::test::TestSubReg::High32) || + !rcc::rebuildMachineLiveness(*FixedLaneFixture->Function, Target)) { + return; + } + rcc::MachineAnalysisManager FixedLaneAnalyses; + if (!rcc::registerStage11MachineAnalyses(FixedLaneAnalyses)) + return; + auto FixedLaneIntervals = + FixedLaneAnalyses.getResult<rcc::LiveIntervalsAnalysis>(*FixedLaneFixture->Function, Target); + if (!FixedLaneIntervals) + return; + rcc::LiveRegMatrix FixedLaneMatrix(*FixedLaneFixture->Function, Target, **FixedLaneIntervals); + Context.expect(FixedLaneMatrix.checkInterference(*HighValue, G0).Kind == + rcc::RegisterInterferenceKind::Free, + "a fixed subregister must not interfere with a disjoint virtual lane"); +} + +void testSharedUnitLaneMatrix(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("shared-unit-lane-matrix", 5); + if (!Fixture) + return; + auto Low = createVReg(*Fixture->Function); + auto High = createVReg(*Fixture->Function); + if (!Low || !High || + !buildDef(*Fixture->Function, Target, *Fixture->Block, *Low, 1, + rcc::test::TestSubReg::Low32) || + !buildDef(*Fixture->Function, Target, *Fixture->Block, *High, 2, + rcc::test::TestSubReg::High32) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *High, + rcc::test::TestSubReg::High32) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Low, rcc::test::TestSubReg::Low32) || + !rcc::rebuildMachineLiveness(*Fixture->Function, Target)) { + return; + } + rcc::MachineAnalysisManager Analyses; + if (!rcc::registerStage11MachineAnalyses(Analyses)) + return; + auto Intervals = Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, Target); + if (!Intervals) + return; + const auto G0 = physical(rcc::test::TestRegister::G0); + const auto G1 = physical(rcc::test::TestRegister::G1); + rcc::LiveRegMatrix Matrix(*Fixture->Function, Target, **Intervals); + Context.expect(Target.registers().regsOverlap(G0, G1) && Matrix.assign(*Low, G0).has_value() && + Matrix.checkInterference(*High, G1).Kind == + rcc::RegisterInterferenceKind::Free && + Matrix.assign(*High, G1).has_value(), + "disjoint lanes must coexist on a shared multi-lane RegisterUnit"); +} + +[[nodiscard]] rcc::Expected<FunctionFixture> +createPressureFunction(const rcc::TargetDescription &Target, std::uint64_t ID) { + auto Fixture = createFunction("pressure-" + std::to_string(ID), ID); + if (!Fixture) + return std::unexpected(Fixture.error()); + std::vector<rcc::Register> Values; + for (std::int64_t Index = 0; Index < 3; ++Index) { + auto Reg = createVReg(*Fixture->Function); + if (!Reg) + return std::unexpected(Reg.error()); + if (auto Built = buildDef(*Fixture->Function, Target, *Fixture->Block, *Reg, Index); !Built) + return std::unexpected(Built.error()); + Values.push_back(*Reg); + } + for (const rcc::Register Reg : Values) { + if (auto Built = buildUse(*Fixture->Function, Target, *Fixture->Block, Reg); !Built) + return std::unexpected(Built.error()); + } + auto Prepared = prepareForAllocation(*Fixture->Function, Target); + if (!Prepared) + return std::unexpected(Prepared.error()); + return Fixture; +} + +void testAllocatorsUnderPressure(TestContext &Context, const rcc::TargetDescription &Target, + const TestRegisterAllocationInfo &Info) { + for (const auto [Kind, ID, Name] : { + std::tuple{AllocatorKind::Basic, std::uint64_t{10}, std::string_view{"Basic"}}, + std::tuple{AllocatorKind::Fast, std::uint64_t{11}, std::string_view{"Fast"}}, + std::tuple{AllocatorKind::PBQP, std::uint64_t{12}, std::string_view{"PBQP"}}, + }) { + auto Fixture = createPressureFunction(Target, ID); + if (!Fixture) + continue; + auto Allocated = + runAllocator(*Fixture->Function, Target, Info, Kind, {.EnableRematerialization = false}); + if (!Allocated) + std::cerr << Name << " allocation error: " << Allocated.error().message() << '\n'; + Context.expect(Allocated.has_value() && + Fixture->Function->properties().has(rcc::MachineFunctionProperty::NoVRegs) && + Fixture->Function->frameInfo().liveObjectCount() != 0 && + countOpcode(*Fixture->Function, SpillLoadOpcode) != 0 && + countOpcode(*Fixture->Function, SpillStoreOpcode) != 0, + "all allocators must close a deterministic spill/reload cycle under pressure"); + } +} + +void testFailureAtomicity(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createPressureFunction(Target, 13); + if (!Fixture) + return; + const std::vector<std::uint64_t> Before = functionSignature(*Fixture->Function); + const std::size_t KnownBefore = static_cast<std::size_t>(std::ranges::count_if( + Fixture->Function->registerInfo().virtualRegisters(), + [](const rcc::VirtualRegisterInfo &Info) { return !Info.IsTombstone; })); + RejectingRegisterAllocationInfo Rejecting; + auto Failed = runAllocator(*Fixture->Function, Target, Rejecting, AllocatorKind::Basic, + {.EnableRematerialization = false}); + const std::size_t KnownAfter = static_cast<std::size_t>(std::ranges::count_if( + Fixture->Function->registerInfo().virtualRegisters(), + [](const rcc::VirtualRegisterInfo &Info) { return !Info.IsTombstone; })); + Context.expect(!Failed && Failed.error().code() == rcc::ErrorCode::InternalError && + functionSignature(*Fixture->Function) == Before && KnownAfter == KnownBefore && + !Fixture->Function->properties().has(rcc::MachineFunctionProperty::NoVRegs), + "failed register allocation must leave the original MachineFunction unchanged"); +} + +void testFastBlockBoundary(TestContext &Context, const rcc::TargetDescription &Target, + const TestRegisterAllocationInfo &Info) { + auto Fixture = createFunction("fast-block-boundary", 14); + if (!Fixture) + return; + auto Exit = Fixture->Function->createBasicBlock(); + if (!Exit || !Fixture->Function->appendBlock(**Exit) || + !Fixture->Function->cfgUpdater().addSuccessor(*Fixture->Block, **Exit, + rcc::BranchProbability::one())) { + return; + } + auto Value = createVReg(*Fixture->Function); + const rcc::Register G0 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0)); + if (!Value || !buildDef(*Fixture->Function, Target, *Fixture->Block, *Value, 9) || + !buildUse(*Fixture->Function, Target, **Exit, *Value) || + !buildUse(*Fixture->Function, Target, **Exit, G0) || + !prepareForAllocation(*Fixture->Function, Target)) { + return; + } + auto Allocated = runAllocator(*Fixture->Function, Target, Info, AllocatorKind::Fast); + Context.expect( + Allocated && countOpcode(*Fixture->Function, SpillStoreOpcode) == 1 && + countOpcode(*Fixture->Function, SpillLoadOpcode) == 1 && + (*Exit)->firstInstruction()->next() != nullptr && + (*Exit)->firstInstruction()->next()->operandAt(0)->registerValue() != G0, + "FastAllocator must preserve block live-ins and virtual values across a CFG boundary"); +} + +void testFastRegMaskCalls(TestContext &Context, const rcc::TargetDescription &Target, + const TestRegisterAllocationInfo &Info) { + auto LiveThrough = createFunction("fast-regmask-live-through", 16); + if (!LiveThrough) + return; + auto Value = createVReg(*LiveThrough->Function); + if (!Value || !buildDef(*LiveThrough->Function, Target, *LiveThrough->Block, *Value, 11) || + !buildMask(*LiveThrough->Function, Target, *LiveThrough->Block, + rcc::test::createTestCallPreservedMask()) || + !buildUse(*LiveThrough->Function, Target, *LiveThrough->Block, *Value) || + !prepareForAllocation(*LiveThrough->Function, Target)) { + return; + } + auto LiveThroughAllocated = + runAllocator(*LiveThrough->Function, Target, Info, AllocatorKind::Fast); + Context.expect(LiveThroughAllocated && + countOpcode(*LiveThrough->Function, SpillStoreOpcode) == 1 && + countOpcode(*LiveThrough->Function, SpillLoadOpcode) == 1, + "FastAllocator must spill and reload a value live through a clobbering RegMask"); + + auto CallResult = createFunction("fast-regmask-call-result", 17); + if (!CallResult) + return; + auto Result = createVReg(*CallResult->Function); + if (!Result || + !buildCallDef(*CallResult->Function, Target, *CallResult->Block, *Result, + rcc::test::createTestCallPreservedMask()) || + !buildUse(*CallResult->Function, Target, *CallResult->Block, *Result) || + !prepareForAllocation(*CallResult->Function, Target)) { + return; + } + auto ResultAllocated = runAllocator(*CallResult->Function, Target, Info, AllocatorKind::Fast); + Context.expect(ResultAllocated && countOpcode(*CallResult->Function, SpillStoreOpcode) == 0 && + countOpcode(*CallResult->Function, SpillLoadOpcode) == 0, + "FastAllocator must retain a call-defined result without reloading an " + "uninitialized spill slot"); +} + +void testTiedAndEarlyClobber(TestContext &Context, const rcc::TargetDescription &Target, + const TestRegisterAllocationInfo &Info) { + auto Fixture = createFunction("tied-early", 15); + if (!Fixture) + return; + auto Source = createVReg(*Fixture->Function); + auto Destination = createVReg(*Fixture->Function); + if (!Source || !Destination || + !buildDef(*Fixture->Function, Target, *Fixture->Block, *Source, 1)) { + return; + } + auto Early = buildEarly(*Fixture->Function, Target, *Fixture->Block, *Destination, *Source); + auto Tied = buildTied(*Fixture->Function, Target, *Fixture->Block, *Destination); + if (!Early || !Tied || !buildUse(*Fixture->Function, Target, *Fixture->Block, *Destination) || + !prepareForAllocation(*Fixture->Function, Target)) { + return; + } + auto Allocated = runAllocator(*Fixture->Function, Target, Info, AllocatorKind::Basic); + const std::optional<rcc::Register> EarlyDef = (*Early)->operandAt(0)->registerValue(); + const std::optional<rcc::Register> EarlyUse = (*Early)->operandAt(1)->registerValue(); + const std::optional<rcc::Register> TiedDef = (*Tied)->operandAt(0)->registerValue(); + const std::optional<rcc::Register> TiedUse = (*Tied)->operandAt(1)->registerValue(); + Context.expect(Allocated && EarlyDef && EarlyUse && *EarlyDef != *EarlyUse && TiedDef && + TiedUse && *TiedDef == *TiedUse, + "allocation must separate early-clobber operands and preserve rewritten ties"); +} + +void testRematerialization(TestContext &Context, const rcc::TargetDescription &Target, + const TestRegisterAllocationInfo &Info) { + auto Fixture = createFunction("rematerialization", 20); + if (!Fixture) + return; + auto Value = createVReg(*Fixture->Function); + if (!Value || !buildDef(*Fixture->Function, Target, *Fixture->Block, *Value, 42, {}, true) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Value) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Value)) { + return; + } + rcc::VirtRegMap Mapping(*Fixture->Function); + if (!Mapping.add(*Value)) + return; + rcc::Spiller Spiller(*Fixture->Function, Target, Info, Mapping, true); + auto Children = Spiller.spill(*Value); + Context.expect(Children && Children->size() == 2 && + Fixture->Function->frameInfo().liveObjectCount() == 0 && + countOpcode(*Fixture->Function, RematerializableDefOpcode) == 2 && + countOpcode(*Fixture->Function, SpillLoadOpcode) == 0 && + countOpcode(*Fixture->Function, SpillStoreOpcode) == 0, + "Spiller must rematerialize each use without creating a stack object"); + + auto Unspillable = createVReg(*Fixture->Function); + if (!Unspillable || !Mapping.add(*Unspillable, false)) + return; + auto Rejected = Spiller.spill(*Unspillable); + Context.expect(!Rejected && Rejected.error().code() == rcc::ErrorCode::RegisterAllocationFailed, + "Spiller must reject pressure on a non-spillable virtual register"); +} + +void testRewriteAndConstraints(TestContext &Context, const rcc::TargetDescription &Target, + const TestRegisterAllocationInfo &Info) { + auto RewriteFixture = createFunction("subregister-rewrite", 30); + if (!RewriteFixture) + return; + auto Value = createVReg(*RewriteFixture->Function); + if (!Value || + !buildDef(*RewriteFixture->Function, Target, *RewriteFixture->Block, *Value, 1, + rcc::test::TestSubReg::Low32) || + !buildUse(*RewriteFixture->Function, Target, *RewriteFixture->Block, *Value, + rcc::test::TestSubReg::Low32)) { + return; + } + rcc::VirtRegMap Mapping(*RewriteFixture->Function); + const auto G0 = physical(rcc::test::TestRegister::G0); + if (!Mapping.add(*Value) || !Mapping.assign(*Value, G0)) + return; + auto Rewritten = rcc::rewriteVirtualRegisters(*RewriteFixture->Function, Target, Mapping); + const auto G0Low32 = physical(rcc::test::TestRegister::G0Low32); + Context.expect(Rewritten && *Rewritten && + RewriteFixture->Block->firstInstruction()->operandAt(0)->registerValue() == + rcc::Register::fromPhysical(G0Low32) && + RewriteFixture->Block->firstInstruction()->operandAt(0)->subReg().value() == 0, + "physical rewrite must project and clear virtual subregister operands"); + + auto MaskFixture = createFunction("mask-allocation", 31); + if (!MaskFixture) + return; + auto AcrossCall = createVReg(*MaskFixture->Function); + if (!AcrossCall || + !buildDef(*MaskFixture->Function, Target, *MaskFixture->Block, *AcrossCall, 5) || + !buildMask(*MaskFixture->Function, Target, *MaskFixture->Block, + rcc::test::createTestCallPreservedMask()) || + !buildUse(*MaskFixture->Function, Target, *MaskFixture->Block, *AcrossCall) || + !prepareForAllocation(*MaskFixture->Function, Target)) { + return; + } + auto Allocated = runAllocator(*MaskFixture->Function, Target, Info, AllocatorKind::Basic); + const rcc::MachineInstr *FinalUse = MaskFixture->Block->lastInstruction(); + const auto G1 = physical(rcc::test::TestRegister::G1); + Context.expect(Allocated && FinalUse != nullptr && + FinalUse->operandAt(0)->registerValue() == rcc::Register::fromPhysical(G1), + "global allocation must keep call-crossing values in a preserved register"); +} + +void testInvalidRewriteMappings(TestContext &Context, const rcc::TargetDescription &Target) { + auto ExpectAtomicFailure = [&](FunctionFixture &Fixture, const rcc::VirtRegMap &Mapping, + std::string_view Message) { + const std::vector<std::uint64_t> Before = functionSignature(*Fixture.Function); + auto Rewritten = rcc::rewriteVirtualRegisters(*Fixture.Function, Target, Mapping); + Context.expect(!Rewritten && + Rewritten.error().code() == rcc::ErrorCode::RegisterAllocationFailed && + functionSignature(*Fixture.Function) == Before, + Message); + }; + + auto ClassFixture = createFunction("invalid-class-mapping", 40); + if (!ClassFixture) + return; + auto ClassValue = createVReg(*ClassFixture->Function); + if (!ClassValue || + !buildDef(*ClassFixture->Function, Target, *ClassFixture->Block, *ClassValue, 1) || + !buildUse(*ClassFixture->Function, Target, *ClassFixture->Block, *ClassValue) || + !prepareForAllocation(*ClassFixture->Function, Target)) { + return; + } + rcc::VirtRegMap ClassMapping(*ClassFixture->Function); + const auto F0 = physical(rcc::test::TestRegister::F0); + if (!ClassMapping.add(*ClassValue) || !ClassMapping.assign(*ClassValue, F0)) + return; + ExpectAtomicFailure(*ClassFixture, ClassMapping, + "class-incompatible rewrite mappings must fail atomically"); + + auto ReservedFixture = createFunction("reserved-register-mapping", 41); + if (!ReservedFixture) + return; + auto ReservedValue = createVReg(*ReservedFixture->Function); + const auto G0 = physical(rcc::test::TestRegister::G0); + if (!ReservedValue || + !buildDef(*ReservedFixture->Function, Target, *ReservedFixture->Block, *ReservedValue, 2) || + !buildUse(*ReservedFixture->Function, Target, *ReservedFixture->Block, *ReservedValue) || + !ReservedFixture->Function->registerInfo().reservePhysicalRegister(G0) || + !prepareForAllocation(*ReservedFixture->Function, Target)) { + return; + } + rcc::VirtRegMap ReservedMapping(*ReservedFixture->Function); + if (!ReservedMapping.add(*ReservedValue) || !ReservedMapping.assign(*ReservedValue, G0)) + return; + ExpectAtomicFailure(*ReservedFixture, ReservedMapping, + "reserved-register rewrite mappings must fail atomically"); + + auto OverlapFixture = createFunction("overlapping-register-mapping", 42); + if (!OverlapFixture) + return; + auto Left = createVReg(*OverlapFixture->Function); + auto Right = createVReg(*OverlapFixture->Function); + if (!Left || !Right || + !buildDef(*OverlapFixture->Function, Target, *OverlapFixture->Block, *Left, 3) || + !buildDef(*OverlapFixture->Function, Target, *OverlapFixture->Block, *Right, 4) || + !buildUse(*OverlapFixture->Function, Target, *OverlapFixture->Block, *Left) || + !buildUse(*OverlapFixture->Function, Target, *OverlapFixture->Block, *Right) || + !prepareForAllocation(*OverlapFixture->Function, Target)) { + return; + } + rcc::VirtRegMap OverlapMapping(*OverlapFixture->Function); + if (!OverlapMapping.add(*Left) || !OverlapMapping.add(*Right) || + !OverlapMapping.assign(*Left, G0) || !OverlapMapping.assign(*Right, G0)) { + return; + } + ExpectAtomicFailure(*OverlapFixture, OverlapMapping, + "interfering rewrite mappings must fail atomically"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + auto SharedUnitTarget = createTarget(true); + Context.expect(Target.has_value(), "register-allocation TestTarget must be constructible"); + Context.expect(SharedUnitTarget.has_value(), + "shared-unit register-allocation TestTarget must be constructible"); + if (!Target) { + std::cerr << "target construction error: " << Target.error().message() << '\n'; + return Context.result(); + } + TestRegisterAllocationInfo Info; + testVirtRegMapAndEdit(Context, *Target); + testLiveRegMatrix(Context, *Target); + if (SharedUnitTarget) + testSharedUnitLaneMatrix(Context, *SharedUnitTarget); + testAllocatorsUnderPressure(Context, *Target, Info); + testFailureAtomicity(Context, *Target); + testFastBlockBoundary(Context, *Target, Info); + testFastRegMaskCalls(Context, *Target, Info); + testTiedAndEarlyClobber(Context, *Target, Info); + testRematerialization(Context, *Target, Info); + testRewriteAndConstraints(Context, *Target, Info); + testInvalidRewriteMappings(Context, *Target); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/RegisterAllocationTestSupport.h b/backend/unittests/CodeGen/RegisterAllocationTestSupport.h new file mode 100644 index 0000000..5a3bae2 --- /dev/null +++ b/backend/unittests/CodeGen/RegisterAllocationTestSupport.h @@ -0,0 +1,473 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +// The private test header has no stable include-root-relative guard name. +// NOLINTNEXTLINE(llvm-header-guard) +#ifndef RCC_BACKEND_REGISTER_ALLOCATION_TEST_SUPPORT_H +#define RCC_BACKEND_REGISTER_ALLOCATION_TEST_SUPPORT_H + +#include "Target/TestTarget.h" +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveRangeEdit.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/RegAllocFast.h" +#include "rcc/CodeGen/RegAllocPBQP.h" +#include "rcc/CodeGen/Spiller.h" +#include "rcc/CodeGen/TargetRegisterAllocationInfo.h" +#include "rcc/CodeGen/VirtRegMap.h" + +#include <algorithm> +#include <cstdint> +#include <iostream> +#include <memory> +#include <optional> +#include <ranges> +#include <span> +#include <string> +#include <string_view> +#include <tuple> +#include <utility> +#include <vector> + +namespace rcc::test::ra { + +enum class AllocatorKind : std::uint8_t { Basic, Fast, PBQP }; + +inline constexpr std::uint32_t DefOpcode = 3000; +inline constexpr std::uint32_t RematerializableDefOpcode = 3001; +inline constexpr std::uint32_t UseOpcode = 3002; +inline constexpr std::uint32_t BinaryOpcode = 3003; +inline constexpr std::uint32_t SpillLoadOpcode = 3004; +inline constexpr std::uint32_t SpillStoreOpcode = 3005; +inline constexpr std::uint32_t MaskOpcode = 3006; +inline constexpr std::uint32_t EarlyOpcode = 3007; +inline constexpr std::uint32_t TiedOpcode = 3008; +inline constexpr std::uint32_t CallDefOpcode = 3009; + +[[nodiscard]] constexpr Opcode testOpcode(std::uint32_t Value) noexcept { + return Opcode::fromValue(Value); +} + +[[nodiscard]] inline PhysicalRegister physical(std::uint32_t Number) { + return *PhysicalRegister::create(Number); +} + +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; +}; + +[[nodiscard]] inline OperandDescriptor registerOperand(RegisterOperandRole Role, + bool EarlyClobber = false) { + OperandDescriptor Result; + Result.Kinds = {MachineOperand::Kind::Register}; + Result.RegisterRole = Role; + Result.AllowSubReg = true; + Result.EarlyClobber = EarlyClobber; + return Result; +} + +[[nodiscard]] inline OperandDescriptor plainOperand(MachineOperand::Kind Kind) { + OperandDescriptor Result; + Result.Kinds = {Kind}; + return Result; +} + +[[nodiscard]] inline InstructionDescriptor descriptor(std::uint32_t Value, std::string Name) { + InstructionDescriptor Result; + Result.InstructionOpcode = testOpcode(Value); + Result.Name = std::move(Name); + Result.Flags = {InstructionFlag::ProducesCode}; + return Result; +} + +[[nodiscard]] inline Expected<TargetDescription> createTarget() { + std::vector<InstructionDescriptor> Descriptors; + + auto Def = descriptor(DefOpcode, "RA_DEF"); + Def.Operands = {registerOperand(RegisterOperandRole::Def), + plainOperand(MachineOperand::Kind::Immediate)}; + Def.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Def)); + + auto Remat = descriptor(RematerializableDefOpcode, "RA_REMAT_DEF"); + Remat.Operands = {registerOperand(RegisterOperandRole::Def), + plainOperand(MachineOperand::Kind::Immediate)}; + Remat.NumExplicitDefs = 1; + Remat.Flags.set(InstructionFlag::Rematerializable); + Descriptors.push_back(std::move(Remat)); + + auto Use = descriptor(UseOpcode, "RA_USE"); + Use.Operands = {registerOperand(RegisterOperandRole::Use)}; + Use.Flags.set(InstructionFlag::HasSideEffects); + Descriptors.push_back(std::move(Use)); + + auto Binary = descriptor(BinaryOpcode, "RA_BINARY"); + Binary.Operands = {registerOperand(RegisterOperandRole::Def), + registerOperand(RegisterOperandRole::Use), + registerOperand(RegisterOperandRole::Use)}; + Binary.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Binary)); + + auto Reload = descriptor(SpillLoadOpcode, "RA_RELOAD"); + Reload.Operands = {registerOperand(RegisterOperandRole::Def), + plainOperand(MachineOperand::Kind::FrameIndex)}; + Reload.NumExplicitDefs = 1; + Reload.Flags.set(InstructionFlag::MayLoad); + Reload.RequiresMemoryOperands = true; + Descriptors.push_back(std::move(Reload)); + + auto Spill = descriptor(SpillStoreOpcode, "RA_SPILL"); + Spill.Operands = {registerOperand(RegisterOperandRole::Use), + plainOperand(MachineOperand::Kind::FrameIndex)}; + Spill.Flags.set(InstructionFlag::MayStore); + Spill.RequiresMemoryOperands = true; + Descriptors.push_back(std::move(Spill)); + + auto Mask = descriptor(MaskOpcode, "RA_MASK"); + Mask.Operands = {plainOperand(MachineOperand::Kind::RegisterMask)}; + Mask.Flags.set(InstructionFlag::Call); + Mask.Flags.set(InstructionFlag::HasSideEffects); + Descriptors.push_back(std::move(Mask)); + + auto Early = descriptor(EarlyOpcode, "RA_EARLY"); + Early.Operands = {registerOperand(RegisterOperandRole::Def, true), + registerOperand(RegisterOperandRole::Use)}; + Early.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Early)); + + auto Tied = descriptor(TiedOpcode, "RA_TIED"); + auto TiedDef = registerOperand(RegisterOperandRole::Def); + auto TiedUse = registerOperand(RegisterOperandRole::Use); + TiedDef.DefaultTiedOperand = 1; + TiedUse.DefaultTiedOperand = 0; + Tied.Operands = {TiedDef, TiedUse}; + Tied.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Tied)); + + auto CallDef = descriptor(CallDefOpcode, "RA_CALL_DEF"); + CallDef.Operands = {registerOperand(RegisterOperandRole::Def), + plainOperand(MachineOperand::Kind::RegisterMask)}; + CallDef.NumExplicitDefs = 1; + CallDef.Flags.set(InstructionFlag::Call); + CallDef.Flags.set(InstructionFlag::HasSideEffects); + Descriptors.push_back(std::move(CallDef)); + + auto Copy = descriptor(static_cast<std::uint32_t>(GenericOpcode::COPY), "COPY"); + Copy.Operands = {registerOperand(RegisterOperandRole::Def), + registerOperand(RegisterOperandRole::Use)}; + Copy.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Copy)); + + auto Instructions = InstructionSet::create(std::move(Descriptors), {}); + if (!Instructions) + return std::unexpected(Instructions.error()); + return test::createTestTargetDescription(std::move(*Instructions)); +} + +struct FunctionFixture final { + std::unique_ptr<MachineFunction> Function; + MachineBasicBlock *Block = nullptr; +}; + +[[nodiscard]] inline Expected<FunctionFixture> createFunction(std::string Name, std::uint64_t ID) { + auto Function = MachineFunction::create(std::move(Name), MachineFunctionStableID::fromValue(ID)); + if (!Function) + return std::unexpected(Function.error()); + auto Block = (*Function)->createBasicBlock(); + if (!Block) + return std::unexpected(Block.error()); + auto Appended = (*Function)->appendBlock(**Block); + if (!Appended) + return std::unexpected(Appended.error()); + return FunctionFixture{std::move(*Function), *Block}; +} + +[[nodiscard]] inline Expected<Register> +createVReg(MachineFunction &Function, RegisterClassID Class = TestRegisterClass::GPR64) { + auto Type = LLT::makeInteger(64); + if (!Type) + return std::unexpected(Type.error()); + auto Reg = Function.registerInfo().createVirtualRegister(*Type); + if (!Reg) + return std::unexpected(Reg.error()); + if (auto Result = Function.registerInfo().setRegisterBank(*Reg, TestRegisterBank::GPR); !Result) + return std::unexpected(Result.error()); + if (auto Result = Function.registerInfo().setRegisterClass(*Reg, Class); !Result) + return std::unexpected(Result.error()); + return *Reg; +} + +[[nodiscard]] inline Expected<MachineInstr *> +buildDef(MachineFunction &Function, const TargetDescription &Target, MachineBasicBlock &Block, + Register Reg, std::int64_t Value, SubRegIndex SubReg = {}, bool Rematerializable = false) { + MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = + Builder.buildInstr(testOpcode(Rematerializable ? RematerializableDefOpcode : DefOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Reg, {}, SubReg); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addImmediate(Value); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] inline Expected<MachineInstr *> +buildUse(MachineFunction &Function, const TargetDescription &Target, MachineBasicBlock &Block, + Register Reg, SubRegIndex SubReg = {}, bool Debug = false) { + MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(testOpcode(UseOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + RegisterOperandFlags Flags; + if (Debug) + Flags.set(RegisterOperandFlag::Debug); + if (auto Result = Pending->addUse(Reg, Flags, SubReg); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] inline Expected<MachineInstr *> buildCopy(MachineFunction &Function, + const TargetDescription &Target, + MachineBasicBlock &Block, + Register Destination, Register Source) { + MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(opcode(GenericOpcode::COPY)); + 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]] inline Expected<MachineInstr *> buildMask(MachineFunction &Function, + const TargetDescription &Target, + MachineBasicBlock &Block, + std::shared_ptr<const RegisterMask> Mask) { + MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(testOpcode(MaskOpcode)); + 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]] inline Expected<MachineInstr *> buildTied(MachineFunction &Function, + const TargetDescription &Target, + MachineBasicBlock &Block, Register Reg) { + MachineIRBuilder Builder(Function, Target); + if (auto Result = Builder.setInsertPoint(Block); !Result) + return std::unexpected(Result.error()); + auto Pending = Builder.buildInstr(testOpcode(TiedOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Reg); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addUse(Reg); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->tieOperands(0, 1); !Result) + return std::unexpected(Result.error()); + return Pending->build(); +} + +[[nodiscard]] inline Expected<void> prepareForAllocation(MachineFunction &Function, + const TargetDescription &Target) { + auto Rebuilt = rebuildMachineLiveness(Function, Target); + if (!Rebuilt) + return std::unexpected(Rebuilt.error()); + for (const MachineFunctionProperty Property : { + MachineFunctionProperty::TracksLiveness, + MachineFunctionProperty::Legalized, + MachineFunctionProperty::RegBankSelected, + MachineFunctionProperty::Selected, + MachineFunctionProperty::NoPHIs, + MachineFunctionProperty::TiedOpsRewritten, + }) + Function.properties().set(Property); + return {}; +} + +class TestRegisterAllocationInfo : public TargetRegisterAllocationInfo { +public: + std::uint64_t RegisterCost = 0; + std::uint64_t SpillCost = 1; + + [[nodiscard]] Expected<void> validateSpillReload(RegisterClassID Class, + const TargetDescription &Target) const override { + const RegisterClassDesc *Description = Target.registers().registerClass(Class); + if (Description == nullptr || !Description->Allocatable || Description->SpillSizeInBits == 0 || + Description->SpillAlignmentInBits == 0) + return makeUnexpected(ErrorCode::Unsupported, "test register class is not spillable"); + return {}; + } + + [[nodiscard]] Expected<MachineInstr *> emitReload(MachineIRBuilder &Builder, Register Destination, + RegisterClassID Class, FrameIndex StackSlot, + LaneMask Lanes) const override { + auto Validated = validateSpillReload(Class, Builder.target()); + if (!Validated) + return std::unexpected(Validated.error()); + if (Lanes.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "test reload requires lanes"); + auto Size = MemorySize::fixed(8); + auto Align = Alignment::create(8); + if (!Size || !Align) + return makeUnexpected(ErrorCode::InternalError, "test memory shape is invalid"); + MachineMemOperandDesc Memory; + Memory.Accesses = {MemoryAccessFlag::Load}; + Memory.Size = *Size; + Memory.Align = *Align; + Memory.Base = MemoryBase::frameIndex(StackSlot); + auto MMO = Builder.function().createMemOperand(std::move(Memory)); + if (!MMO) + return std::unexpected(MMO.error()); + auto Pending = Builder.buildInstr(testOpcode(SpillLoadOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Destination); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addFrameIndex(StackSlot); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addMemOperand(**MMO); !Result) + return std::unexpected(Result.error()); + return Pending->build(); + } + + [[nodiscard]] Expected<MachineInstr *> emitSpill(MachineIRBuilder &Builder, Register Source, + RegisterClassID Class, FrameIndex StackSlot, + LaneMask Lanes) const override { + auto Validated = validateSpillReload(Class, Builder.target()); + if (!Validated) + return std::unexpected(Validated.error()); + if (Lanes.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "test spill requires lanes"); + auto Size = MemorySize::fixed(8); + auto Align = Alignment::create(8); + if (!Size || !Align) + return makeUnexpected(ErrorCode::InternalError, "test memory shape is invalid"); + MachineMemOperandDesc Memory; + Memory.Accesses = {MemoryAccessFlag::Store}; + Memory.Size = *Size; + Memory.Align = *Align; + Memory.Base = MemoryBase::frameIndex(StackSlot); + auto MMO = Builder.function().createMemOperand(std::move(Memory)); + if (!MMO) + return std::unexpected(MMO.error()); + auto Pending = Builder.buildInstr(testOpcode(SpillStoreOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addUse(Source); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addFrameIndex(StackSlot); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addMemOperand(**MMO); !Result) + return std::unexpected(Result.error()); + return Pending->build(); + } + + [[nodiscard]] Expected<bool> isRematerializable(const MachineInstr &Instruction, + Register VirtualReg, const MachineFunction &, + const TargetDescription &) const override { + const Register *Defined = Instruction.operandAt(0)->getIf<Register>(); + return Instruction.opcode() == testOpcode(RematerializableDefOpcode) && Defined != nullptr && + *Defined == VirtualReg; + } + + [[nodiscard]] Expected<MachineInstr *> + rematerialize(MachineIRBuilder &Builder, const MachineInstr &Original, Register Destination, + Register OriginalRegister, const TargetDescription &Target) const override { + auto Accepted = isRematerializable(Original, OriginalRegister, Builder.function(), Target); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return makeUnexpected(ErrorCode::InvalidArgument, "test instruction is not rematerializable"); + auto Pending = Builder.buildInstr(testOpcode(RematerializableDefOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Destination); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addOperand(Original.operandAt(1)->cloneDetached()); !Result) + return std::unexpected(Result.error()); + return Pending->build(); + } + + [[nodiscard]] std::uint64_t physicalRegisterCost(const MachineFunction &, Register, + PhysicalRegister, RegisterClassID, + bool) const noexcept override { + return RegisterCost; + } + + [[nodiscard]] std::uint64_t spillCost(const MachineFunction &, const LiveInterval &, + RegisterClassID) const noexcept override { + return SpillCost; + } +}; + +[[nodiscard]] inline Expected<void> runAllocator(MachineFunction &Function, + const TargetDescription &Target, + const TargetRegisterAllocationInfo &Info, + AllocatorKind Kind, + RegisterAllocationOptions Options = {}) { + MachineAnalysisManager Analyses; + auto Registered = registerStage11MachineAnalyses(Analyses); + if (!Registered) + return std::unexpected(Registered.error()); + std::unique_ptr<MachineFunctionPass> Pass; + switch (Kind) { + case AllocatorKind::Basic: + Pass = createBasicAllocatorPass(Info, Options); + break; + case AllocatorKind::Fast: + Pass = std::make_unique<FastAllocatorPass>(Info); + break; + case AllocatorKind::PBQP: + Pass = std::make_unique<PBQPAllocatorPass>(Info, Options); + break; + } + MachinePassManager Pipeline; + auto Added = Pipeline.addPass(std::move(Pass)); + if (!Added) + return std::unexpected(Added.error()); + return Pipeline.run(Function, Target, Analyses); +} + +[[nodiscard]] inline std::size_t countOpcode(const MachineFunction &Function, Opcode OpcodeValue) { + std::size_t Count = 0; + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) + Count += Instruction->opcode() == OpcodeValue ? 1U : 0U; + return Count; +} + +} // namespace rcc::test::ra + +#endif // RCC_BACKEND_REGISTER_ALLOCATION_TEST_SUPPORT_H diff --git a/backend/unittests/CodeGen/SpillerTest.cpp b/backend/unittests/CodeGen/SpillerTest.cpp new file mode 100644 index 0000000..1f22d8f --- /dev/null +++ b/backend/unittests/CodeGen/SpillerTest.cpp @@ -0,0 +1,94 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/Spiller.h" + +#include "CodeGen/RegisterAllocationTestSupport.h" + +#include <iostream> +#include <optional> + +namespace { + +using namespace rcc; +using namespace rcc::test; +using namespace rcc::test::ra; + +void testRematerialization(TestContext &Context, const TargetDescription &Target) { + auto Fixture = createFunction("spiller-remat", 20); + if (!Fixture) + return; + auto Value = createVReg(*Fixture->Function); + if (!Value || !buildDef(*Fixture->Function, Target, *Fixture->Block, *Value, 42, {}, true) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Value) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Value)) + return; + VirtRegMap Mapping(*Fixture->Function); + TestRegisterAllocationInfo Info; + if (!Mapping.add(*Value)) + return; + Spiller ValueSpiller(*Fixture->Function, Target, Info, Mapping, true); + auto Children = ValueSpiller.spill(*Value); + Context.expect(Children && Children->size() == 2 && + Fixture->Function->frameInfo().liveObjectCount() == 0 && + countOpcode(*Fixture->Function, testOpcode(RematerializableDefOpcode)) == 2 && + countOpcode(*Fixture->Function, testOpcode(SpillLoadOpcode)) == 0, + "Spiller must rematerialize each use without allocating a stack slot"); +} + +void testDirectSpillAndDebugUse(TestContext &Context, const TargetDescription &Target) { + auto Fixture = createFunction("spiller-debug", 21); + if (!Fixture) + return; + auto Value = createVReg(*Fixture->Function); + if (!Value || !buildDef(*Fixture->Function, Target, *Fixture->Block, *Value, 7) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Value, {}, true) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Value)) + return; + VirtRegMap Mapping(*Fixture->Function); + TestRegisterAllocationInfo Info; + if (!Mapping.add(*Value)) + return; + Spiller ValueSpiller(*Fixture->Function, Target, Info, Mapping, false); + auto Children = ValueSpiller.spill(*Value); + const MachineOperand *DebugOperand = nullptr; + for (const MachineInstr *Instruction = Fixture->Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + for (const MachineOperand &Operand : Instruction->operands()) { + if (Operand.isDebugUse()) { + DebugOperand = &Operand; + break; + } + } + if (DebugOperand != nullptr) + break; + } + const std::optional<Register> DebugRegister = + DebugOperand == nullptr ? std::nullopt : DebugOperand->registerValue(); + const bool DebugRegisterCleared = DebugRegister && DebugRegister.value().isNoRegister(); + Context.expect(Children && !Children->empty() && + countOpcode(*Fixture->Function, testOpcode(SpillLoadOpcode)) != 0 && + countOpcode(*Fixture->Function, testOpcode(SpillStoreOpcode)) != 0 && + DebugOperand != nullptr && DebugRegisterCleared && + DebugOperand->registerFlags().has(RegisterOperandFlag::Undef), + "Spiller must preserve direct spill code and clear debug-only uses"); + + auto Unspillable = createVReg(*Fixture->Function); + if (!Unspillable || !Mapping.add(*Unspillable, false)) + return; + auto Rejected = ValueSpiller.spill(*Unspillable); + Context.expect(!Rejected && Rejected.error().code() == ErrorCode::RegisterAllocationFailed, + "Spiller must reject an explicitly non-spillable value"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "Spiller test target must be constructible"); + if (!Target) + return Context.result(); + testRematerialization(Context, *Target); + testDirectSpillAndDebugUse(Context, *Target); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/VirtRegMapTest.cpp b/backend/unittests/CodeGen/VirtRegMapTest.cpp new file mode 100644 index 0000000..a3bdfc1 --- /dev/null +++ b/backend/unittests/CodeGen/VirtRegMapTest.cpp @@ -0,0 +1,91 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "CodeGen/RegisterAllocationTestSupport.h" +#include "rcc/CodeGen/LiveRangeEdit.h" + +#include <iostream> + +namespace { + +using namespace rcc; +using namespace rcc::test; +using namespace rcc::test::ra; + +void testSplitMetadata(TestContext &Context, const TargetDescription &Target) { + auto Fixture = createFunction("virt-map", 10); + if (!Fixture) + return; + auto Parent = createVReg(*Fixture->Function); + if (!Parent) + return; + VirtRegMap Mapping(*Fixture->Function); + LiveRangeEdit Edit(*Fixture->Function, Target, Mapping); + Context.expect(Mapping.add(*Parent).has_value(), "VirtRegMap must accept a known vreg"); + auto Slot = Edit.getOrCreateSpillSlot(*Parent); + auto Child = Edit.createFrom(*Parent, false); + Context.expect( + Slot && Child && Mapping.verify().has_value() && Mapping.stackSlot(*Child) == Slot && + Mapping.entry(*Child)->SplitParent == *Parent && Mapping.entry(*Child)->Origin == *Parent, + "LiveRangeEdit must preserve split origin and spill metadata"); + if (!Child) + return; + const PhysicalRegister G0 = physical(TestRegister::G0); + Context.expect(Mapping.assign(*Child, G0).has_value() && Mapping.physicalRegister(*Child) == G0 && + Mapping.entry(*Child)->State == VirtRegAllocationState::Assigned, + "VirtRegMap must transition a split child to an assigned state"); +} + +void testRewriteAndAtomicValidation(TestContext &Context, const TargetDescription &Target) { + auto Fixture = createFunction("virt-rewrite", 11); + if (!Fixture) + return; + auto Value = createVReg(*Fixture->Function); + if (!Value || + !buildDef(*Fixture->Function, Target, *Fixture->Block, *Value, 1, TestSubReg::Low32) || + !buildUse(*Fixture->Function, Target, *Fixture->Block, *Value, TestSubReg::Low32) || + !prepareForAllocation(*Fixture->Function, Target)) + return; + VirtRegMap Mapping(*Fixture->Function); + const PhysicalRegister G0 = physical(TestRegister::G0); + Context.expect(Mapping.add(*Value).has_value() && Mapping.assign(*Value, G0).has_value(), + "VirtRegMap must accept a physical assignment before rewrite"); + auto Rewritten = rewriteVirtualRegisters(*Fixture->Function, Target, Mapping); + const MachineOperand *Def = Fixture->Block->firstInstruction()->operandAt(0); + Context.expect( + Rewritten && *Rewritten && Def != nullptr && Def->registerValue() && + Def->registerValue() == Register::fromPhysical(physical(TestRegister::G0Low32)) && + Def->subReg().value() == 0 && + std::ranges::none_of(Fixture->Function->registerInfo().virtualRegisters(), + [](const VirtualRegisterInfo &Info) { return !Info.IsTombstone; }), + "VirtualRegisterRewrite must project and clear subregister operands"); + + auto InvalidFixture = createFunction("virt-rewrite-invalid", 12); + if (!InvalidFixture) + return; + auto Invalid = createVReg(*InvalidFixture->Function); + if (!Invalid || + !buildDef(*InvalidFixture->Function, Target, *InvalidFixture->Block, *Invalid, 2) || + !buildUse(*InvalidFixture->Function, Target, *InvalidFixture->Block, *Invalid) || + !prepareForAllocation(*InvalidFixture->Function, Target)) + return; + VirtRegMap InvalidMapping(*InvalidFixture->Function); + const PhysicalRegister F0 = physical(TestRegister::F0); + if (!InvalidMapping.add(*Invalid) || !InvalidMapping.assign(*Invalid, F0)) + return; + auto Failed = rewriteVirtualRegisters(*InvalidFixture->Function, Target, InvalidMapping); + Context.expect(!Failed && Failed.error().code() == ErrorCode::RegisterAllocationFailed, + "VirtualRegisterRewrite must reject class-incompatible mappings atomically"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "VirtRegMap test target must be constructible"); + if (!Target) + return Context.result(); + testSplitMetadata(Context, *Target); + testRewriteAndAtomicValidation(Context, *Target); + return Context.result(); +} |