1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "unit_test.h"
17 #include "optimizer/analysis/live_registers.h"
18 #include "optimizer/optimizations/regalloc/reg_alloc_linear_scan.h"
19
20 namespace panda::compiler {
21
22 class LiveRegistersTest : public GraphTest {
23 };
24
TEST_F(LiveRegistersTest,EmptyIntervals)25 TEST_F(LiveRegistersTest, EmptyIntervals)
26 {
27 auto intervals = ArenaVector<LifeIntervals *>(GetGraph()->GetAllocator()->Adapter());
28 ASSERT_EQ(LifeIntervalsTree::BuildIntervalsTree(intervals, GetGraph()), nullptr);
29 }
30
TEST_F(LiveRegistersTest,IntervalsWithoutRegisters)31 TEST_F(LiveRegistersTest, IntervalsWithoutRegisters)
32 {
33 auto alloc = GetGraph()->GetAllocator();
34 auto intervals = ArenaVector<LifeIntervals *>(alloc->Adapter());
35 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(0, 42)));
36 ASSERT_EQ(LifeIntervalsTree::BuildIntervalsTree(intervals, GetGraph()), nullptr);
37 }
38
TEST_F(LiveRegistersTest,IntervalsWithRegisters)39 TEST_F(LiveRegistersTest, IntervalsWithRegisters)
40 {
41 auto alloc = GetGraph()->GetAllocator();
42 auto intervals = ArenaVector<LifeIntervals *>(alloc->Adapter());
43 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(0, 10)));
44 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(0, 2)));
45 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(2, 3)));
46 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(5, 6)));
47 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(6, 8)));
48 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(8, 10)));
49
50 Register reg {0};
51 for (auto &li : intervals) {
52 li->SetType(DataType::UINT64);
53 li->SetReg(reg++);
54 }
55 auto tree = LifeIntervalsTree::BuildIntervalsTree(intervals, GetGraph());
56 ASSERT_NE(tree, nullptr);
57
58 RegMask mask {};
59 tree->VisitIntervals(5, [&mask]([[maybe_unused]] const auto &li) {
60 ASSERT_EQ(mask.test(li->GetReg()), false);
61 mask.set(li->GetReg());
62 });
63 ASSERT_EQ(RegMask {0b1001}, mask);
64
65 mask.reset();
66 tree->VisitIntervals(11, [&mask]([[maybe_unused]] const auto &li) {
67 ASSERT_EQ(mask.test(li->GetReg()), false);
68 mask.set(li->GetReg());
69 });
70 ASSERT_EQ(RegMask {}, mask);
71
72 mask.reset();
73 tree->VisitIntervals(8, [&mask]([[maybe_unused]] const auto &li) {
74 ASSERT_EQ(mask.test(li->GetReg()), false);
75 mask.set(li->GetReg());
76 });
77 ASSERT_EQ(RegMask {0b110001}, mask);
78
79 mask.reset();
80 tree->VisitIntervals(4, [&mask]([[maybe_unused]] const auto &li) {
81 ASSERT_EQ(mask.test(li->GetReg()), false);
82 mask.set(li->GetReg());
83 });
84 ASSERT_EQ(RegMask {0b1}, mask);
85
86 // Not-live splits at target life-position
87 mask.reset();
88 tree->VisitIntervals<false>(8, [&mask]([[maybe_unused]] const auto &li) {
89 ASSERT_EQ(mask.test(li->GetReg()), false);
90 mask.set(li->GetReg());
91 });
92 ASSERT_EQ(RegMask {0b100001}, mask);
93 }
94
TEST_F(LiveRegistersTest,IntervalsWithHole)95 TEST_F(LiveRegistersTest, IntervalsWithHole)
96 {
97 auto alloc = GetGraph()->GetAllocator();
98 auto intervals = ArenaVector<LifeIntervals *>(alloc->Adapter());
99 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(0, 2)));
100 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(8, 10)));
101
102 Register reg {0};
103 for (auto &li : intervals) {
104 li->SetType(DataType::UINT64);
105 li->SetReg(reg++);
106 }
107 auto tree = LifeIntervalsTree::BuildIntervalsTree(intervals, GetGraph());
108 ASSERT_NE(tree, nullptr);
109
110 RegMask mask {};
111 tree->VisitIntervals(5, [&mask]([[maybe_unused]] const auto &li) {
112 ASSERT_EQ(mask.test(li->GetReg()), false);
113 mask.set(li->GetReg());
114 });
115 ASSERT_EQ(RegMask {}, mask);
116
117 mask.reset();
118 tree->VisitIntervals(0, [&mask]([[maybe_unused]] const auto &li) {
119 ASSERT_EQ(mask.test(li->GetReg()), false);
120 mask.set(li->GetReg());
121 });
122 ASSERT_EQ(RegMask {0b1}, mask);
123
124 mask.reset();
125 tree->VisitIntervals(9, [&mask]([[maybe_unused]] const auto &li) {
126 ASSERT_EQ(mask.test(li->GetReg()), false);
127 mask.set(li->GetReg());
128 });
129 ASSERT_EQ(RegMask {0b10}, mask);
130 }
131
TEST_F(LiveRegistersTest,IntervalsOutOfRange)132 TEST_F(LiveRegistersTest, IntervalsOutOfRange)
133 {
134 auto alloc = GetGraph()->GetAllocator();
135 auto intervals = ArenaVector<LifeIntervals *>(alloc->Adapter());
136 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(4, 6)));
137
138 Register reg {0};
139 for (auto &li : intervals) {
140 li->SetType(DataType::UINT64);
141 li->SetReg(reg++);
142 }
143 auto tree = LifeIntervalsTree::BuildIntervalsTree(intervals, GetGraph());
144 ASSERT_NE(tree, nullptr);
145
146 size_t count = 0;
147 tree->VisitIntervals(1, [&count]([[maybe_unused]] const auto &li) { count++; });
148 ASSERT_EQ(count, 0);
149
150 count = 0;
151 tree->VisitIntervals(42, [&count]([[maybe_unused]] const auto &li) { count++; });
152 ASSERT_EQ(count, 0);
153 }
154
TEST_F(LiveRegistersTest,MultipleBranches)155 TEST_F(LiveRegistersTest, MultipleBranches)
156 {
157 auto alloc = GetGraph()->GetAllocator();
158 auto intervals = ArenaVector<LifeIntervals *>(alloc->Adapter());
159 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(0, 80)));
160 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(0, 39)));
161 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(21, 39)));
162 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(21, 29)));
163 intervals.push_back(alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(26, 29)));
164
165 Register reg {0};
166 for (auto &li : intervals) {
167 li->SetType(DataType::UINT64);
168 li->SetReg(reg++);
169 }
170 auto tree = LifeIntervalsTree::BuildIntervalsTree(intervals, GetGraph());
171 ASSERT_NE(tree, nullptr);
172
173 RegMask mask {};
174 tree->VisitIntervals(27, [&mask]([[maybe_unused]] const auto &li) {
175 ASSERT_EQ(mask.test(li->GetReg()), false);
176 mask.set(li->GetReg());
177 });
178 ASSERT_EQ(RegMask {0b11111}, mask);
179 }
180
TEST_F(LiveRegistersTest,LiveRegisterForGraph)181 TEST_F(LiveRegistersTest, LiveRegisterForGraph)
182 {
183 GRAPH(GetGraph())
184 {
185 CONSTANT(0, 42);
186
187 BASIC_BLOCK(2, -1)
188 {
189 INST(1, Opcode::Return).u64().Inputs(0);
190 }
191 }
192
193 auto result = GetGraph()->RunPass<RegAllocLinearScan>();
194 ASSERT_TRUE(result);
195 ASSERT_TRUE(GetGraph()->RunPass<LiveRegisters>());
196
197 auto con = &INS(0);
198
199 auto &lr = GetGraph()->GetAnalysis<LiveRegisters>();
200 lr.VisitIntervalsWithLiveRegisters(con, []([[maybe_unused]] const auto &li) { UNREACHABLE(); });
201
202 size_t count = 0;
203 lr.VisitIntervalsWithLiveRegisters(&INS(1), [&con, &count]([[maybe_unused]] const auto &li) {
204 ASSERT_EQ(li->GetInst(), con);
205 count++;
206 });
207 ASSERT_EQ(count, 1);
208 }
209
TEST_F(LiveRegistersTest,LiveSplits)210 TEST_F(LiveRegistersTest, LiveSplits)
211 {
212 auto alloc = GetGraph()->GetAllocator();
213 auto intervals = ArenaVector<LifeIntervals *>(alloc->Adapter());
214 auto interval = alloc->New<LifeIntervals>(alloc, GetGraph()->CreateInstAdd(), LiveRange(0, 30));
215 intervals.push_back(interval);
216
217 interval->SetType(DataType::Type::UINT64);
218 interval->SetReg(0);
219
220 auto split0 = interval->SplitAt(9, alloc);
221 split0->SetLocation(Location::MakeStackSlot(0));
222 auto split1 = split0->SplitAt(19, alloc);
223 split1->SetReg(1);
224
225 auto tree = LifeIntervalsTree::BuildIntervalsTree(intervals, GetGraph());
226 ASSERT_NE(tree, nullptr);
227
228 std::vector<std::pair<LifeNumber, RegMask::ValueType>> ln2mask = {
229 {7, 0b1}, {9, 0b1}, {11, 0b0}, {19, 0b10}, {30, 0b10}};
230
231 for (auto [ln, expected_mask] : ln2mask) {
232 RegMask mask {};
233 tree->VisitIntervals(ln, [&mask]([[maybe_unused]] const auto &li) {
234 ASSERT_EQ(mask.test(li->GetReg()), false);
235 mask.set(li->GetReg());
236 });
237 EXPECT_EQ(RegMask {expected_mask}, mask) << "Wrong mask @ life number " << ln;
238 }
239 }
240
TEST_F(LiveRegistersTest,IntervalWithLifetimeHole)241 TEST_F(LiveRegistersTest, IntervalWithLifetimeHole)
242 {
243 auto graph = GetGraph();
244 if (graph->GetCallingConvention() == nullptr) {
245 GTEST_SKIP();
246 }
247
248 GRAPH(graph)
249 {
250 PARAMETER(0, 0).u64();
251 PARAMETER(1, 1).u64();
252 CONSTANT(2, 0);
253
254 BASIC_BLOCK(2, 3, 4)
255 {
256 INST(3, Opcode::Mul).Inputs(0, 1).u64();
257 INST(4, Opcode::Compare).b().Inputs(3, 2);
258 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_EQ).Inputs(4).Imm(0);
259 }
260
261 BASIC_BLOCK(3, 5)
262 {
263 INST(6, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({0, 1, 2});
264 // interval for inst 3 will have a lifetime hole at this call
265 INST(7, Opcode::CallStatic).InputsAutoType(6).v0id();
266 }
267
268 BASIC_BLOCK(4, 5)
269 {
270 INST(8, Opcode::Mul).Inputs(3, 3).u64();
271 INST(9, Opcode::SaveState).Inputs(0, 1, 2, 8).SrcVregs({0, 1, 2, 8});
272 INST(10, Opcode::CallStatic).InputsAutoType(9).v0id();
273 }
274
275 BASIC_BLOCK(5, -1)
276 {
277 INST(11, Opcode::Return).Inputs(0).u64();
278 }
279 }
280
281 auto result = graph->RunPass<RegAllocLinearScan>();
282 ASSERT_TRUE(result);
283 ASSERT_TRUE(graph->RunPass<LiveRegisters>());
284
285 auto &lr = graph->GetAnalysis<LiveRegisters>();
286 lr.VisitIntervalsWithLiveRegisters<false>(&INS(7), [graph](const auto &li) {
287 auto rd = graph->GetRegisters();
288 auto caller_mask =
289 DataType::IsFloatType(li->GetType()) ? rd->GetCallerSavedVRegMask() : rd->GetCallerSavedRegMask();
290 ASSERT_FALSE(caller_mask.Test(li->GetReg())) << "There should be no live caller-saved registers at call, but "
291 "a register for following instruction is alive: "
292 << *(li->GetInst());
293 });
294 }
295 } // namespace panda::compiler
296