1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
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::MachineFunctionAnalysisManager 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::MachineFunctionAnalysisManager 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::MachineFunctionAnalysisManager 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::MachineFunctionAnalysisManager 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();
}
|
