diff options
Diffstat (limited to 'backend/unittests/CodeGen/LiveIntervalsTest.cpp')
| -rw-r--r-- | backend/unittests/CodeGen/LiveIntervalsTest.cpp | 265 |
1 files changed, 265 insertions, 0 deletions
diff --git a/backend/unittests/CodeGen/LiveIntervalsTest.cpp b/backend/unittests/CodeGen/LiveIntervalsTest.cpp new file mode 100644 index 0000000..5c127a2 --- /dev/null +++ b/backend/unittests/CodeGen/LiveIntervalsTest.cpp @@ -0,0 +1,265 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveIntervals.h" + +#include "LiveTestSupport.h" +#include "rcc/CodeGen/LiveRegUnits.h" +#include "rcc/CodeGen/LiveVariables.h" +#include "rcc/Target/RISCV/RISCVInstructions.h" +#include "rcc/Target/RISCV/RISCVRegisters.h" +#include "rcc/Target/RISCV/RISCVTarget.h" + +namespace { + +using namespace rcc::test::liveness; + +void testCFGAndValueNumbers(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("cfg-liveness", 2, 8); + if (!Fixture) { + Context.expect(false, "CFG liveness fixture creation must succeed"); + return; + } + auto &Function = *Fixture->Function; + auto &Entry = *Fixture->Blocks[0]; + auto &Left = *Fixture->Blocks[1]; + auto &Right = *Fixture->Blocks[2]; + auto &Join = *Fixture->Blocks[3]; + auto &Header = *Fixture->Blocks[4]; + auto &Body = *Fixture->Blocks[5]; + auto &Exit = *Fixture->Blocks[6]; + auto &Dead = *Fixture->Blocks[7]; + auto Half = rcc::BranchProbability::fromFraction(1, 2); + auto Updater = Function.cfgUpdater(); + const bool CFGValid = Half && Updater.addSuccessor(Entry, Left, *Half) && + Updater.addSuccessor(Entry, Right, *Half) && + Updater.addSuccessor(Left, Join, rcc::BranchProbability::one()) && + Updater.addSuccessor(Right, Join, rcc::BranchProbability::one()) && + Updater.addSuccessor(Join, Header, rcc::BranchProbability::one()) && + Updater.addSuccessor(Header, Body, *Half) && + Updater.addSuccessor(Header, Exit, *Half) && + Updater.addSuccessor(Body, Header, rcc::BranchProbability::one()); + Context.expect(CFGValid, "diamond and loop CFG construction must succeed"); + if (!CFGValid) + return; + + auto Across = createVReg(Function); + auto Merged = createVReg(Function); + auto Unreachable = createVReg(Function); + auto Redefined = createVReg(Function); + if (!Across || !Merged || !Unreachable || !Redefined) { + Context.expect(false, "CFG liveness virtual registers must be created"); + return; + } + auto AcrossDef = buildDef(Function, Target, Entry, *Across); + auto LeftDef = buildDef(Function, Target, Left, *Merged); + auto RightDef = buildDef(Function, Target, Right, *Merged); + auto MergedUse = buildUse(Function, Target, Join, *Merged); + auto LoopUse = buildUse(Function, Target, Body, *Across); + auto DeadUse = buildUse(Function, Target, Dead, *Unreachable); + auto FirstRedef = buildDef(Function, Target, Exit, *Redefined); + auto SecondRedef = buildDef(Function, Target, Exit, *Redefined); + if (!AcrossDef || !LeftDef || !RightDef || !MergedUse || !LoopUse || !DeadUse || !FirstRedef || + !SecondRedef) { + Context.expect(false, "CFG liveness instructions must be built"); + return; + } + + rcc::MachineAnalysisManager Analyses; + auto Registered = rcc::registerStage11MachineAnalyses(Analyses); + auto Variables = Registered ? Analyses.getResult<rcc::LiveVariablesAnalysis>(Function, Target) + : rcc::Expected<rcc::LiveVariablesAnalysis::Result *>{ + std::unexpected(Registered.error())}; + auto Intervals = Registered ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(Function, Target) + : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ + std::unexpected(Registered.error())}; + if (!Variables || !Intervals) { + Context.expect(false, "CFG liveness analyses must materialize"); + return; + } + Context.expect((*Variables)->isLiveOut(Entry, *Across) && (*Variables)->isLiveIn(Left, *Across) && + (*Variables)->isLiveIn(Right, *Across) && + (*Variables)->isLiveIn(Header, *Across) && + (*Variables)->isLiveOut(Body, *Across), + "CFG fixed point must propagate a value through a diamond and loop backedge"); + Context.expect( + (*Variables)->isLiveOut(Left, *Merged) && (*Variables)->isLiveOut(Right, *Merged) && + (*Variables)->isLiveIn(Join, *Merged) && (*Variables)->isLiveIn(Dead, *Unreachable), + "liveness must merge predecessor definitions and retain unreachable uses"); + + const rcc::LiveInterval *MergedInterval = (*Intervals)->interval(*Merged); + const rcc::LiveInterval *AcrossInterval = (*Intervals)->interval(*Across); + const rcc::LiveInterval *RedefinedInterval = (*Intervals)->interval(*Redefined); + const bool HasPhi = MergedInterval != nullptr && + std::ranges::any_of(MergedInterval->MainRange.values(), + [](const rcc::LiveValueNumber &Value) { + return Value.State == rcc::LiveValueState::Phi; + }); + const bool HasRedefined = + RedefinedInterval != nullptr && + std::ranges::any_of(RedefinedInterval->MainRange.values(), + [](const rcc::LiveValueNumber &Value) { + return Value.State == rcc::LiveValueState::Redefined; + }); + Context.expect(MergedInterval != nullptr && MergedInterval->MainRange.values().size() >= 3 && + HasPhi && HasRedefined, + "non-SSA intervals must retain multiple definitions, PHI, and redefined values"); + Context.expect(AcrossInterval != nullptr && (*Intervals)->interferes(*Across, *Merged), + "live intervals must expose CFG-derived interference"); +} + +void testPhysicalUnitsAndRegMasks(TestContext &Context, const rcc::TargetDescription &Target) { + const rcc::RegisterUnitID MultiLaneUnit = rcc::RegisterUnitID::fromValue(9); + rcc::LiveRegUnits PartialLanes; + PartialLanes.add(MultiLaneUnit, rcc::LaneMask::fromRaw(0x3)); + rcc::LiveRegUnits RemovedLanes; + RemovedLanes.add(MultiLaneUnit, rcc::LaneMask::fromRaw(0x2)); + PartialLanes.subtract(RemovedLanes); + Context.expect(PartialLanes.lanes(MultiLaneUnit) == rcc::LaneMask::fromRaw(0x1) && + PartialLanes.contains(MultiLaneUnit, rcc::LaneMask::fromRaw(0x1)) && + !PartialLanes.intersects(MultiLaneUnit, rcc::LaneMask::fromRaw(0x2)), + "RegisterUnit lane sets must preserve partial union and subtraction"); + + auto AliasFixture = createFunction("physical-alias", 4, 1); + if (!AliasFixture) { + Context.expect(false, "physical-alias fixture creation must succeed"); + return; + } + const rcc::Register G0 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0)); + const rcc::Register G0High = + rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0High32)); + auto G0Def = buildDef(*AliasFixture->Function, Target, *AliasFixture->Blocks[0], G0); + auto G0HighUse = buildUse(*AliasFixture->Function, Target, *AliasFixture->Blocks[0], G0High); + if (!G0Def || !G0HighUse) { + Context.expect(false, "physical-alias instructions must be built"); + return; + } + rcc::MachineAnalysisManager AliasAnalyses; + auto AliasRegistered = rcc::registerStage11MachineAnalyses(AliasAnalyses); + auto AliasIntervals = + AliasRegistered + ? AliasAnalyses.getResult<rcc::LiveIntervalsAnalysis>(*AliasFixture->Function, Target) + : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ + std::unexpected(AliasRegistered.error())}; + const rcc::RegisterUnitID HighUnit = rcc::RegisterUnitID::fromValue(3); + Context.expect(AliasIntervals && (*AliasIntervals)->regUnitRange(HighUnit) != nullptr && + (*AliasIntervals)->regUnitRange(HighUnit)->segments().size() == 1, + "shared RegisterUnits must connect super-register defs to subregister uses"); + + auto MaskFixture = createFunction("regmask", 5, 1); + if (!MaskFixture) { + Context.expect(false, "RegMask fixture creation must succeed"); + return; + } + auto Across = createVReg(*MaskFixture->Function); + auto Output = createVReg(*MaskFixture->Function); + if (!Across || !Output) { + Context.expect(false, "RegMask virtual registers must be created"); + return; + } + const auto Mask = rcc::test::createTestCallPreservedMask(); + auto AcrossDef = buildDef(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Across); + auto FirstMask = buildMask(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], Mask); + auto AcrossUse = buildUse(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Across); + auto OutputDef = + buildMaskedDef(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Output, Mask); + auto OutputUse = buildUse(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Output); + if (!AcrossDef || !FirstMask || !AcrossUse || !OutputDef || !OutputUse) { + Context.expect(false, "RegMask instructions must be built"); + return; + } + rcc::MachineAnalysisManager MaskAnalyses; + auto MaskRegistered = rcc::registerStage11MachineAnalyses(MaskAnalyses); + auto MaskIntervals = + MaskRegistered + ? MaskAnalyses.getResult<rcc::LiveIntervalsAnalysis>(*MaskFixture->Function, Target) + : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ + std::unexpected(MaskRegistered.error())}; + if (!MaskIntervals) { + Context.expect(false, "RegMask intervals must materialize"); + return; + } + const rcc::PhysicalRegister Candidate = physical(rcc::test::TestRegister::G0); + const rcc::LiveInterval *AcrossInterval = (*MaskIntervals)->interval(*Across); + const rcc::LiveInterval *OutputInterval = (*MaskIntervals)->interval(*Output); + Context.expect((*MaskIntervals)->regMaskPositions().size() == 2 && + std::ranges::all_of((*MaskIntervals)->regMaskPositions(), + [](const rcc::RegMaskPosition &Position) { + return Position.Position.kind() == + rcc::SlotIndexKind::EarlyClobber; + }), + "RegMask interference positions must use early-clobber slots"); + Context.expect(AcrossInterval != nullptr && OutputInterval != nullptr && + (*MaskIntervals)->regMaskClobbers(*AcrossInterval, Candidate) && + !(*MaskIntervals)->regMaskClobbers(*OutputInterval, Candidate), + "RegMask queries must reject live-through values but accept same-call outputs"); + Context.expect((*MaskIntervals)->regUnitRange(rcc::RegisterUnitID::fromValue(1)) == nullptr, + "unused RegMask clobbers must not expand into physical live ranges"); +} + +void testRISCVLiveness(TestContext &Context) { + auto Target = rcc::riscv::createTargetDescription(); + auto Fixture = createFunction("riscv-liveness", 8, 1); + if (!Target || !Fixture) { + Context.expect(false, "RV64GC liveness fixture creation must succeed"); + return; + } + auto X5 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X5); + auto X6 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X6); + auto X7 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X7); + if (!X5 || !X6 || !X7) { + Context.expect(false, "RV64GC physical registers must resolve"); + return; + } + auto BuildADDI = [&](rcc::PhysicalRegister Destination, rcc::PhysicalRegister Source, + std::int64_t Immediate) -> rcc::Expected<rcc::MachineInstr *> { + rcc::MachineIRBuilder Builder(*Fixture->Function, *Target); + auto Point = Builder.setInsertPoint(*Fixture->Blocks[0]); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr( + rcc::Opcode::fromValue(static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADDI))); + if (!Pending) + return std::unexpected(Pending.error()); + auto Def = Pending->addDef(rcc::Register::fromPhysical(Destination)); + if (!Def) + return std::unexpected(Def.error()); + auto Use = Pending->addUse(rcc::Register::fromPhysical(Source)); + if (!Use) + return std::unexpected(Use.error()); + auto Imm = Pending->addImmediate(Immediate); + if (!Imm) + return std::unexpected(Imm.error()); + return Pending->build(); + }; + auto First = BuildADDI(*X6, *X5, 1); + auto Second = BuildADDI(*X7, *X6, 2); + if (!First || !Second) { + Context.expect(false, "RV64GC ADDI instructions must be built"); + return; + } + rcc::MachineAnalysisManager Analyses; + auto Registered = rcc::registerStage11MachineAnalyses(Analyses); + auto Intervals = Registered + ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, *Target) + : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ + std::unexpected(Registered.error())}; + const auto Unit = + rcc::RegisterUnitID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterUnit::U_X6)); + Context.expect(Intervals && (*Intervals)->regUnitRange(Unit) != nullptr && + (*Intervals)->regUnitRange(Unit)->segments().size() == 1, + "production RV64GC register units must participate in LiveIntervals"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "liveness TestTarget must be created"); + if (!Target) + return Context.result(); + testCFGAndValueNumbers(Context, *Target); + testPhysicalUnitsAndRegMasks(Context, *Target); + testRISCVLiveness(Context); + return Context.result(); +} |