1 /*
2 * Copyright (c) 2021-2024 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 "libpandabase/utils/utils.h"
18 #include "optimizer/analysis/dominators_tree.h"
19 #include "optimizer/analysis/live_registers.h"
20 #include "optimizer/code_generator/codegen.h"
21 #include "optimizer/code_generator/registers_description.h"
22 #include "optimizer/optimizations/regalloc/reg_alloc_linear_scan.h"
23 #include "optimizer/optimizations/regalloc/reg_alloc_resolver.h"
24 #include "optimizer/optimizations/regalloc/spill_fills_resolver.h"
25 #include "optimizer/optimizations/cleanup.h"
26 #include "optimizer/ir/graph_cloner.h"
27
28 namespace ark::compiler {
operator ==(const SpillFillData & lhs,const SpillFillData & rhs)29 static bool operator==(const SpillFillData &lhs, const SpillFillData &rhs)
30 {
31 return std::forward_as_tuple(lhs.SrcType(), lhs.DstType(), lhs.GetType(), lhs.SrcValue(), lhs.DstValue()) ==
32 std::forward_as_tuple(rhs.SrcType(), rhs.DstType(), rhs.GetType(), rhs.SrcValue(), rhs.DstValue());
33 }
34
35 class RegAllocLinearScanTest : public GraphTest {
36 public:
CheckInstRegNotEqualOthersInstRegs(int checkId,std::vector<int> && instIds)37 void CheckInstRegNotEqualOthersInstRegs(int checkId, std::vector<int> &&instIds)
38 {
39 for (auto id : instIds) {
40 ASSERT_NE(INS(checkId).GetDstReg(), INS(id).GetDstReg());
41 }
42 }
43
CompareSpillFillInsts(SpillFillInst * lhs,SpillFillInst * rhs)44 void CompareSpillFillInsts(SpillFillInst *lhs, SpillFillInst *rhs)
45 {
46 const auto &lhsSfs = lhs->GetSpillFills();
47 const auto &rhsSfs = rhs->GetSpillFills();
48 ASSERT_EQ(lhsSfs.size(), rhsSfs.size());
49
50 for (size_t i = 0; i < lhsSfs.size(); i++) {
51 auto res = lhsSfs[i] == rhsSfs[i];
52 ASSERT_TRUE(res);
53 }
54 }
55
CheckImmediateSpillFill(Inst * inst,size_t inputNum)56 bool CheckImmediateSpillFill(Inst *inst, size_t inputNum)
57 {
58 auto sfInst = inst->GetPrev();
59 auto constInput = inst->GetInput(inputNum).GetInst();
60 if (sfInst->GetOpcode() != Opcode::SpillFill || !constInput->IsConst()) {
61 return false;
62 }
63 auto graph = inst->GetBasicBlock()->GetGraph();
64 auto srcReg = inst->GetSrcReg(inputNum);
65 for (auto sf : sfInst->CastToSpillFill()->GetSpillFills()) {
66 if (sf.SrcType() == LocationType::IMMEDIATE && (graph->GetSpilledConstant(sf.SrcValue()) == constInput) &&
67 sf.DstValue() == srcReg) {
68 return true;
69 }
70 }
71 return false;
72 }
73
74 template <DataType::Type REG_TYPE>
75 void TestPhiMovesOverwriting(Graph *graph, SpillFillInst *sf, SpillFillInst *expectedSf);
76 template <DataType::Type REG_TYPE>
77 void TestPhiMovesOverwritingCyclic(Graph *graph, SpillFillsResolver &resolver, SpillFillInst *sf,
78 SpillFillInst *expectedSf);
79 template <DataType::Type REG_TYPE>
80 void TestPhiMovesOverwritingNotApplied(SpillFillsResolver &resolver, SpillFillInst *sf, SpillFillInst *expectedSf);
81 template <DataType::Type REG_TYPE>
82 void TestPhiMovesOverwritingComplex(SpillFillsResolver &resolver, SpillFillInst *sf, SpillFillInst *expectedSf);
83 void PhiMovesOverwritingMixed(SpillFillsResolver &resolver, SpillFillInst *sf, SpillFillInst *expectedSf);
84 void PhiMovesOverwriting2(SpillFillsResolver &resolver, SpillFillInst *sf, SpillFillInst *expectedSf);
85 template <unsigned int CONSTANTS_NUM>
86 bool FillGraphWithConstants(Graph *graph);
87
88 protected:
InitUsedRegs(Graph * graph)89 void InitUsedRegs(Graph *graph)
90 {
91 ArenaVector<bool> regs =
92 ArenaVector<bool>(std::max(MAX_NUM_REGS, MAX_NUM_VREGS), false, GetAllocator()->Adapter());
93 graph->InitUsedRegs<DataType::INT64>(®s);
94 graph->InitUsedRegs<DataType::FLOAT64>(®s);
95 graph->SetStackSlotsCount(MAX_NUM_STACK_SLOTS);
96 }
97 };
98
99 // NOLINTBEGIN(readability-magic-numbers)
100 /*
101 * Test Graph:
102 * [0]
103 * |
104 * v
105 * /-----[2]<----\
106 * | | |
107 * | v |
108 * | [3]-----/
109 * |
110 * \---->[4]
111 * |
112 * v
113 * [exit]
114 *
115 * Insts linear order:
116 * ID INST(INPUTS) LIFE NUMBER LIFE INTERVALS ARM64 REGS
117 * ------------------------------------------
118 * 0. Constant 2 [2-22] R4
119 * 1. Constant 4 [4-8] R5
120 * 2. Constant 6 [6-24] R6
121 *
122 * 3. Phi (0,7) 8 [8-16][22-24] R7
123 * 4. Phi (1,8) 8 [8-18] R8
124 * 5. Cmp (4,0) 10 [10-12] R9
125 * 6. If (5) 12 -
126 *
127 * 7. Mul (3,4) 16 [16-22] R5
128 * 8. Sub (4,0) 18 [18-22] R9
129 *
130 * 9. Add (2,3) 24 [24-26] R4
131 */
TEST_F(RegAllocLinearScanTest,ARM64Regs)132 TEST_F(RegAllocLinearScanTest, ARM64Regs)
133 {
134 if (GetGraph()->GetArch() != Arch::AARCH64) {
135 return;
136 }
137 GRAPH(GetGraph())
138 {
139 CONSTANT(0U, 1U);
140 CONSTANT(1U, 10U);
141 CONSTANT(2U, 20U);
142
143 BASIC_BLOCK(2U, 3U, 4U)
144 {
145 INST(3U, Opcode::Phi).u64().Inputs({{0U, 0U}, {3U, 7U}});
146 INST(4U, Opcode::Phi).u64().Inputs({{0U, 1U}, {3U, 8U}});
147 INST(5U, Opcode::Compare).b().Inputs(4U, 0U);
148 INST(6U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(5U);
149 }
150
151 BASIC_BLOCK(3U, 2U)
152 {
153 INST(7U, Opcode::Mul).u64().Inputs(3U, 4U);
154 INST(8U, Opcode::Sub).u64().Inputs(4U, 0U);
155 }
156
157 BASIC_BLOCK(4U, -1L)
158 {
159 INST(10U, Opcode::Add).u64().Inputs(2U, 3U);
160 INST(11U, Opcode::Return).u64().Inputs(10U);
161 }
162 }
163 auto result = GetGraph()->RunPass<RegAllocLinearScan>();
164 if (GetGraph()->GetCallingConvention() == nullptr) {
165 ASSERT_FALSE(result);
166 return;
167 }
168 ASSERT_TRUE(result);
169 GraphChecker(GetGraph()).Check();
170 CheckInstRegNotEqualOthersInstRegs(0U, {1U, 2U, 5U, 7U, 8U});
171 CheckInstRegNotEqualOthersInstRegs(1U, {2U});
172 CheckInstRegNotEqualOthersInstRegs(2U, {5U, 7U, 8U});
173 CheckInstRegNotEqualOthersInstRegs(3U, {5U});
174 CheckInstRegNotEqualOthersInstRegs(4U, {5U, 7U});
175 CheckInstRegNotEqualOthersInstRegs(7U, {8U});
176 }
177
178 /**
179 * NOTE(a.popov) Support test-case
180 *
181 * The way to allocate registers in this test is to spill onе of the source registers on the stack:
182 * A -> r1
183 * B -> r2
184 * spill r1 -> STACK
185 * ADD(A, B) -> r1
186 *
187 * Currently, sources on the stack are supported for calls only
188 */
TEST_F(RegAllocLinearScanTest,DISABLED_TwoFreeRegs)189 TEST_F(RegAllocLinearScanTest, DISABLED_TwoFreeRegs)
190 {
191 GRAPH(GetGraph())
192 {
193 CONSTANT(0U, 1U);
194 CONSTANT(1U, 10U);
195 CONSTANT(2U, 20U);
196
197 BASIC_BLOCK(2U, 3U, 4U)
198 {
199 INST(3U, Opcode::Phi).u64().Inputs({{0U, 0U}, {3U, 7U}});
200 INST(4U, Opcode::Phi).u64().Inputs({{0U, 1U}, {3U, 8U}});
201 INST(5U, Opcode::Compare).b().Inputs(4U, 0U);
202 INST(6U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(5U);
203 }
204
205 BASIC_BLOCK(3U, 2U)
206 {
207 INST(7U, Opcode::Mul).u64().Inputs(3U, 4U);
208 INST(8U, Opcode::Sub).u64().Inputs(4U, 0U);
209 }
210
211 BASIC_BLOCK(4U, -1L)
212 {
213 INST(10U, Opcode::Add).u64().Inputs(2U, 3U);
214 INST(11U, Opcode::ReturnVoid);
215 }
216 }
217 // Create reg_mask with 2 available general registers
218 RegAllocLinearScan ra(GetGraph());
219 uint32_t regMask = GetGraph()->GetArch() != Arch::AARCH32 ? 0xF3FFFFFFU : 0xFABFFFFFU;
220 ra.SetRegMask(RegMask {regMask});
221 ra.SetVRegMask(VRegMask {0U});
222 auto result = ra.Run();
223 if (GetGraph()->GetCallingConvention() == nullptr) {
224 EXPECT_FALSE(result);
225 return;
226 }
227 EXPECT_TRUE(result);
228 GraphChecker(GetGraph()).Check();
229 }
230
231 /*
232 * [start]
233 * |
234 * v
235 * [2]
236 * / \
237 * v v
238 * [3] [4]---\
239 * / \ |
240 * v v |
241 * [5]<--[6]<-----/
242 * |
243 * v
244 * [exit]
245 *
246 * SpillFill instructions will be inserted between BB3 and BB5, then between BB3 and BB6
247 * Check if these instructions are unique
248 *
249 */
TEST_F(RegAllocLinearScanTest,InsertSpillFillsAfterSameBlock)250 TEST_F(RegAllocLinearScanTest, InsertSpillFillsAfterSameBlock)
251 {
252 GRAPH(GetGraph())
253 {
254 PARAMETER(0U, 1U).u64();
255 PARAMETER(1U, 10U).u64();
256 PARAMETER(2U, 20U).u64();
257
258 BASIC_BLOCK(2U, 3U, 4U)
259 {
260 INST(3U, Opcode::Compare).b().CC(CC_EQ).Inputs(0U, 1U);
261 INST(4U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(3U);
262 }
263
264 BASIC_BLOCK(3U, 5U, 6U)
265 {
266 INST(5U, Opcode::Mul).u64().Inputs(0U, 1U);
267 INST(6U, Opcode::Compare).b().CC(CC_EQ).Inputs(1U, 2U);
268 INST(7U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(6U);
269 }
270
271 BASIC_BLOCK(4U, 6U)
272 {
273 INST(8U, Opcode::Mul).u64().Inputs(0U, 2U);
274 }
275
276 BASIC_BLOCK(5U, -1L)
277 {
278 INST(10U, Opcode::Phi).u64().Inputs({{3U, 5U}, {6U, 12U}});
279 INST(11U, Opcode::Return).u64().Inputs(10U);
280 }
281
282 BASIC_BLOCK(6U, 5U)
283 {
284 INST(12U, Opcode::Phi).u64().Inputs({{3U, 5U}, {4U, 8U}});
285 INST(13U, Opcode::Mul).u64().Inputs(12U, 2U);
286 }
287 }
288 auto result = GetGraph()->RunPass<RegAllocLinearScan>();
289 if (GetGraph()->GetCallingConvention() == nullptr) {
290 ASSERT_FALSE(result);
291 return;
292 }
293 ASSERT_TRUE(result);
294
295 for (auto block : GetGraph()->GetBlocksRPO()) {
296 for (auto inst : block->AllInsts()) {
297 ASSERT_EQ(inst->GetBasicBlock(), block);
298 }
299 }
300 }
301
TEST_F(RegAllocLinearScanTest,RzeroAssigment)302 TEST_F(RegAllocLinearScanTest, RzeroAssigment)
303 {
304 GRAPH(GetGraph())
305 {
306 CONSTANT(0U, 0U);
307 CONSTANT(1U, 10U);
308 CONSTANT(2U, 20U);
309
310 BASIC_BLOCK(2U, 3U, 4U)
311 {
312 INST(3U, Opcode::Phi).u64().Inputs(0U, 7U);
313 INST(4U, Opcode::Phi).u64().Inputs(1U, 8U);
314 INST(5U, Opcode::Compare).b().Inputs(4U, 0U);
315 INST(6U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(5U);
316 }
317
318 BASIC_BLOCK(3U, 2U)
319 {
320 INST(7U, Opcode::Mul).u64().Inputs(3U, 4U);
321 INST(8U, Opcode::Sub).u64().Inputs(4U, 0U);
322 }
323
324 BASIC_BLOCK(4U, -1L)
325 {
326 INST(10U, Opcode::Add).u64().Inputs(2U, 3U);
327 INST(13U, Opcode::SaveState).Inputs(10U).SrcVregs({0U});
328 INST(11U, Opcode::CallStatic).u64().InputsAutoType(0U, 13U);
329 INST(12U, Opcode::Return).u64().Inputs(11U);
330 }
331 }
332 auto result = GetGraph()->RunPass<RegAllocLinearScan>();
333 if (GetGraph()->GetCallingConvention() == nullptr) {
334 ASSERT_FALSE(result);
335 return;
336 }
337 ASSERT_TRUE(result);
338 auto zeroReg = GetGraph()->GetZeroReg();
339 // check for target arch, which has a zero register
340 if (zeroReg != INVALID_REG) {
341 ASSERT_EQ(INS(0U).GetDstReg(), zeroReg);
342 ASSERT_EQ(INS(5U).GetSrcReg(1U), zeroReg);
343 ASSERT_EQ(INS(8U).GetSrcReg(1U), zeroReg);
344
345 // Find spill-fill with moving zero constant -> phi destination register
346 auto phiResolver = BB(2U).GetPredBlockByIndex(0U);
347 auto spillFillInst = phiResolver->GetLastInst()->IsControlFlow() ? phiResolver->GetLastInst()->GetPrev()
348 : phiResolver->GetLastInst();
349 ASSERT_TRUE(spillFillInst->GetOpcode() == Opcode::SpillFill);
350 auto spillFills = spillFillInst->CastToSpillFill()->GetSpillFills();
351 auto phiReg = INS(3U).GetDstReg();
352 ASSERT_TRUE(phiReg != INVALID_REG);
353 auto iter = std::find_if(spillFills.begin(), spillFills.end(), [zeroReg, phiReg](const SpillFillData &sf) {
354 return (sf.SrcValue() == zeroReg && sf.DstValue() == phiReg);
355 });
356 ASSERT_NE(iter, spillFills.end());
357 }
358 }
359
360 template <DataType::Type REG_TYPE>
TestPhiMovesOverwriting(Graph * graph,SpillFillInst * sf,SpillFillInst * expectedSf)361 void RegAllocLinearScanTest::TestPhiMovesOverwriting(Graph *graph, SpillFillInst *sf, SpillFillInst *expectedSf)
362 {
363 auto resolver = SpillFillsResolver(graph);
364
365 // simple cyclical sf
366 sf->ClearSpillFills();
367 sf->AddMove(4U, 5U, REG_TYPE);
368 sf->AddMove(5U, 4U, REG_TYPE);
369 expectedSf->ClearSpillFills();
370 if (graph->GetArch() != Arch::AARCH32) { // temp is register
371 Register tempReg = DataType::IsFloatType(REG_TYPE) ? graph->GetArchTempVReg() : graph->GetArchTempReg();
372 expectedSf->AddMove(4U, tempReg, REG_TYPE);
373 expectedSf->AddMove(5U, 4U, REG_TYPE);
374 expectedSf->AddMove(tempReg, 5U, REG_TYPE);
375 } else { // temp is stack slot
376 auto tempSlot = StackSlot(0U);
377 expectedSf->AddSpill(4U, tempSlot, REG_TYPE);
378 expectedSf->AddMove(5U, 4U, REG_TYPE);
379 expectedSf->AddFill(tempSlot, 5U, REG_TYPE);
380 }
381 resolver.Resolve(sf);
382 CompareSpillFillInsts(sf, expectedSf);
383
384 TestPhiMovesOverwritingCyclic<REG_TYPE>(graph, resolver, sf, expectedSf);
385 TestPhiMovesOverwritingNotApplied<REG_TYPE>(resolver, sf, expectedSf);
386 TestPhiMovesOverwritingComplex<REG_TYPE>(resolver, sf, expectedSf);
387 }
388
389 template <DataType::Type REG_TYPE>
TestPhiMovesOverwritingCyclic(Graph * graph,SpillFillsResolver & resolver,SpillFillInst * sf,SpillFillInst * expectedSf)390 void RegAllocLinearScanTest::TestPhiMovesOverwritingCyclic(Graph *graph, SpillFillsResolver &resolver,
391 SpillFillInst *sf, SpillFillInst *expectedSf)
392 {
393 // cyclical sf with memcopy
394 sf->ClearSpillFills();
395 sf->AddMemCopy(4U, 5U, REG_TYPE);
396 sf->AddMemCopy(5U, 4U, REG_TYPE);
397 expectedSf->ClearSpillFills();
398 if (graph->GetArch() != Arch::AARCH32) { // temp is register
399 Register tempReg = DataType::IsFloatType(REG_TYPE) ? graph->GetArchTempVReg() : graph->GetArchTempReg();
400 expectedSf->AddFill(4U, tempReg, REG_TYPE);
401 expectedSf->AddMemCopy(5U, 4U, REG_TYPE);
402 expectedSf->AddSpill(tempReg, 5U, REG_TYPE);
403 } else { // temp is stack slot
404 auto tempSlot = StackSlot(0U);
405 expectedSf->AddMemCopy(4U, tempSlot, REG_TYPE);
406 expectedSf->AddMemCopy(5U, 4U, REG_TYPE);
407 expectedSf->AddMemCopy(tempSlot, 5U, REG_TYPE);
408 }
409 resolver.Resolve(sf);
410 CompareSpillFillInsts(sf, expectedSf);
411
412 // cyclic sf with all move-types
413 sf->ClearSpillFills();
414 sf->AddMove(4U, 5U, REG_TYPE);
415 sf->AddSpill(5U, 10U, REG_TYPE);
416 sf->AddMemCopy(10U, 11U, REG_TYPE);
417 sf->AddFill(11U, 4U, REG_TYPE);
418 expectedSf->ClearSpillFills();
419 expectedSf->ClearSpillFills();
420 if (graph->GetArch() != Arch::AARCH32) { // temp is register
421 Register tempReg = DataType::IsFloatType(REG_TYPE) ? graph->GetArchTempVReg() : graph->GetArchTempReg();
422 expectedSf->AddMove(4U, tempReg, REG_TYPE);
423 expectedSf->AddFill(11U, 4U, REG_TYPE);
424 expectedSf->AddMemCopy(10U, 11U, REG_TYPE);
425 expectedSf->AddSpill(5U, 10U, REG_TYPE);
426 expectedSf->AddMove(tempReg, 5U, REG_TYPE);
427 } else { // temp is stack slot
428 auto tempSlot = StackSlot(0U);
429 expectedSf->AddSpill(4U, tempSlot, REG_TYPE);
430 expectedSf->AddFill(11U, 4U, REG_TYPE);
431 expectedSf->AddMemCopy(10U, 11U, REG_TYPE);
432 expectedSf->AddSpill(5U, 10U, REG_TYPE);
433 expectedSf->AddFill(tempSlot, 5U, REG_TYPE);
434 }
435 resolver.Resolve(sf);
436 CompareSpillFillInsts(sf, expectedSf);
437 }
438
439 template <DataType::Type REG_TYPE>
TestPhiMovesOverwritingNotApplied(SpillFillsResolver & resolver,SpillFillInst * sf,SpillFillInst * expectedSf)440 void RegAllocLinearScanTest::TestPhiMovesOverwritingNotApplied(SpillFillsResolver &resolver, SpillFillInst *sf,
441 SpillFillInst *expectedSf)
442 {
443 // not applied
444 sf->ClearSpillFills();
445 sf->AddMove(4U, 5U, REG_TYPE);
446 sf->AddMove(6U, 7U, REG_TYPE);
447 expectedSf->ClearSpillFills();
448 expectedSf->AddMove(4U, 5U, REG_TYPE);
449 expectedSf->AddMove(6U, 7U, REG_TYPE);
450 resolver.Resolve(sf);
451 CompareSpillFillInsts(sf, expectedSf);
452 }
453
454 template <DataType::Type REG_TYPE>
TestPhiMovesOverwritingComplex(SpillFillsResolver & resolver,SpillFillInst * sf,SpillFillInst * expectedSf)455 void RegAllocLinearScanTest::TestPhiMovesOverwritingComplex(SpillFillsResolver &resolver, SpillFillInst *sf,
456 SpillFillInst *expectedSf)
457 {
458 // comlex sf
459 sf->ClearSpillFills();
460 sf->AddFill(1U, 15U, REG_TYPE);
461 sf->AddMove(4U, 5U, REG_TYPE);
462 sf->AddFill(2U, 16U, REG_TYPE);
463 sf->AddMove(5U, 6U, REG_TYPE);
464 sf->AddMove(6U, 7U, REG_TYPE);
465 sf->AddMove(7U, 9U, REG_TYPE);
466 sf->AddMove(6U, 4U, REG_TYPE);
467 sf->AddMove(11U, 12U, REG_TYPE);
468 sf->AddMove(20U, 19U, REG_TYPE);
469 sf->AddMove(21U, 20U, REG_TYPE);
470 sf->AddSpill(15U, 3U, REG_TYPE);
471 sf->AddMove(10U, 11U, REG_TYPE);
472 expectedSf->ClearSpillFills();
473 expectedSf->AddMove(7U, 9U, REG_TYPE);
474 expectedSf->AddMove(6U, 7U, REG_TYPE);
475 expectedSf->AddMove(5U, 6U, REG_TYPE);
476 expectedSf->AddMove(4U, 5U, REG_TYPE);
477 expectedSf->AddMove(7U, 4U, REG_TYPE);
478
479 expectedSf->AddMove(11U, 12U, REG_TYPE);
480 expectedSf->AddMove(10U, 11U, REG_TYPE);
481
482 expectedSf->AddFill(2U, 16U, REG_TYPE);
483
484 expectedSf->AddMove(20U, 19U, REG_TYPE);
485 expectedSf->AddMove(21U, 20U, REG_TYPE);
486
487 expectedSf->AddSpill(15U, 3U, REG_TYPE);
488 expectedSf->AddFill(1U, 15U, REG_TYPE);
489 resolver.Resolve(sf);
490 CompareSpillFillInsts(sf, expectedSf);
491 }
492
PhiMovesOverwritingMixed(SpillFillsResolver & resolver,SpillFillInst * sf,SpillFillInst * expectedSf)493 void RegAllocLinearScanTest::PhiMovesOverwritingMixed(SpillFillsResolver &resolver, SpillFillInst *sf,
494 SpillFillInst *expectedSf)
495 {
496 // mixed reg-types sf
497 sf->ClearSpillFills();
498 sf->AddFill(1U, 5U, DataType::FLOAT64);
499 sf->AddFill(2U, 7U, DataType::UINT32);
500 sf->AddMove(4U, 5U, DataType::UINT64);
501 sf->AddMove(5U, 6U, DataType::UINT64);
502 sf->AddSpill(2U, 3U, DataType::UINT64);
503 sf->AddSpill(7U, 4U, DataType::UINT64);
504 sf->AddMove(6U, 4U, DataType::UINT64);
505 sf->AddMove(6U, 7U, DataType::FLOAT64);
506 sf->AddMove(7U, 9U, DataType::FLOAT64);
507 sf->AddMove(10U, 11U, DataType::UINT64);
508 sf->AddMove(11U, 12U, DataType::FLOAT64);
509 sf->AddMove(21U, 20U, DataType::UINT64);
510 sf->AddMove(22U, 21U, DataType::FLOAT64);
511 sf->AddSpill(15U, 5U, DataType::FLOAT64);
512 expectedSf->ClearSpillFills();
513 expectedSf->AddMove(10U, 11U, DataType::UINT64);
514 expectedSf->AddMove(21U, 20U, DataType::UINT64);
515 expectedSf->AddFill(1U, 5U, DataType::FLOAT64);
516
517 expectedSf->AddMove(7U, 9U, DataType::FLOAT64);
518 expectedSf->AddMove(6U, 7U, DataType::FLOAT64);
519
520 expectedSf->AddMove(11U, 12U, DataType::FLOAT64);
521 expectedSf->AddMove(22U, 21U, DataType::FLOAT64);
522 expectedSf->AddSpill(2U, 3U, DataType::UINT64);
523
524 expectedSf->AddSpill(7U, 4U, DataType::UINT64);
525 expectedSf->AddFill(2U, 7U, DataType::UINT32);
526
527 expectedSf->AddSpill(15U, 5U, DataType::FLOAT64);
528
529 if (GetGraph()->GetArch() != Arch::AARCH32) { // temp is register
530 Register tempReg = GetGraph()->GetArchTempReg();
531 expectedSf->AddMove(4U, tempReg, DataType::UINT64);
532 expectedSf->AddMove(6U, 4U, DataType::UINT64);
533 expectedSf->AddMove(5U, 6U, DataType::UINT64);
534 expectedSf->AddMove(tempReg, 5U, DataType::UINT64);
535 } else { // temp is stack slot
536 auto tempSlot = StackSlot(0U);
537 expectedSf->AddSpill(4U, tempSlot, DataType::UINT64);
538 expectedSf->AddMove(6U, 4U, DataType::UINT64);
539 expectedSf->AddMove(5U, 6U, DataType::UINT64);
540 expectedSf->AddFill(tempSlot, 5U, DataType::UINT64);
541 }
542
543 resolver.Resolve(sf);
544 CompareSpillFillInsts(sf, expectedSf);
545 }
546
PhiMovesOverwriting2(SpillFillsResolver & resolver,SpillFillInst * sf,SpillFillInst * expectedSf)547 void RegAllocLinearScanTest::PhiMovesOverwriting2(SpillFillsResolver &resolver, SpillFillInst *sf,
548 SpillFillInst *expectedSf)
549 {
550 // zero-reg reordering
551 sf->ClearSpillFills();
552 sf->AddMove(31U, 5U, DataType::UINT64);
553 sf->AddMove(5U, 6U, DataType::UINT64);
554 expectedSf->ClearSpillFills();
555 expectedSf->AddMove(5U, 6U, DataType::UINT64);
556 expectedSf->AddMove(31U, 5U, DataType::UINT64);
557 resolver.Resolve(sf);
558 CompareSpillFillInsts(sf, expectedSf);
559
560 // find and resolve cycle in moves sequence starts with not-cycle move
561 sf->ClearSpillFills();
562 sf->AddMove(18U, 7U, DataType::UINT64);
563 sf->AddMove(10U, 18U, DataType::UINT64);
564 sf->AddMove(18U, 10U, DataType::UINT64);
565 sf->AddSpill(7U, 32U, DataType::UINT64);
566 expectedSf->ClearSpillFills();
567 expectedSf->AddSpill(7U, 32U, DataType::UINT64);
568 expectedSf->AddMove(18U, 7U, DataType::UINT64);
569 expectedSf->AddMove(10U, 18U, DataType::UINT64);
570 expectedSf->AddMove(7U, 10U, DataType::UINT64);
571 resolver.Resolve(sf);
572 CompareSpillFillInsts(sf, expectedSf);
573
574 // fix `moves_table_[dst].src != first_src'
575 sf->ClearSpillFills();
576 sf->AddMove(8U, 6U, DataType::UINT64);
577 sf->AddMove(7U, 8U, DataType::UINT64);
578 sf->AddMove(8U, 7U, DataType::UINT64);
579 expectedSf->ClearSpillFills();
580 expectedSf->AddMove(8U, 6U, DataType::UINT64);
581 expectedSf->AddMove(7U, 8U, DataType::UINT64);
582 expectedSf->AddMove(6U, 7U, DataType::UINT64);
583 resolver.Resolve(sf);
584 CompareSpillFillInsts(sf, expectedSf);
585
586 // find and resolve cycle in moves sequence starts with not-cycle move
587 sf->ClearSpillFills();
588 sf->AddMove(18U, 7U, DataType::UINT64);
589 sf->AddMove(10U, 18U, DataType::UINT64);
590 sf->AddMove(18U, 10U, DataType::UINT64);
591 sf->AddMove(7U, 6U, DataType::UINT64);
592 expectedSf->ClearSpillFills();
593 expectedSf->AddMove(7U, 6U, DataType::UINT64);
594 expectedSf->AddMove(18U, 7U, DataType::UINT64);
595 expectedSf->AddMove(10U, 18U, DataType::UINT64);
596 expectedSf->AddMove(7U, 10U, DataType::UINT64);
597 resolver.Resolve(sf);
598 CompareSpillFillInsts(sf, expectedSf);
599 }
600
TEST_F(RegAllocLinearScanTest,PhiMovesOverwriting)601 TEST_F(RegAllocLinearScanTest, PhiMovesOverwriting)
602 {
603 GRAPH(GetGraph())
604 {
605 CONSTANT(0U, 0U);
606 BASIC_BLOCK(2U, -1L)
607 {
608 INST(1U, Opcode::Return).u64().Inputs(0U);
609 }
610 }
611
612 InitUsedRegs(GetGraph());
613 auto resolver = SpillFillsResolver(GetGraph());
614 // Use the last available register as a temp
615 auto sf = GetGraph()->CreateInstSpillFill();
616 auto expectedSf = GetGraph()->CreateInstSpillFill();
617 TestPhiMovesOverwriting<DataType::UINT32>(GetGraph(), sf, expectedSf);
618 TestPhiMovesOverwriting<DataType::UINT64>(GetGraph(), sf, expectedSf);
619 TestPhiMovesOverwriting<DataType::FLOAT64>(GetGraph(), sf, expectedSf);
620
621 // not applied
622 sf->ClearSpillFills();
623 sf->AddMove(4U, 5U, DataType::UINT64);
624 sf->AddMove(5U, 4U, DataType::FLOAT64);
625 expectedSf->ClearSpillFills();
626 expectedSf->AddMove(4U, 5U, DataType::UINT64);
627 expectedSf->AddMove(5U, 4U, DataType::FLOAT64);
628 resolver.Resolve(sf);
629 CompareSpillFillInsts(sf, expectedSf);
630
631 // not applied
632 sf->ClearSpillFills();
633 sf->AddMemCopy(0U, 1U, DataType::UINT64);
634 expectedSf->ClearSpillFills();
635 expectedSf->AddMemCopy(0U, 1U, DataType::UINT64);
636 resolver.Resolve(sf);
637 CompareSpillFillInsts(sf, expectedSf);
638
639 PhiMovesOverwritingMixed(resolver, sf, expectedSf);
640 PhiMovesOverwriting2(resolver, sf, expectedSf);
641 }
642
TEST_F(RegAllocLinearScanTest,DynPhiMovesOverwriting)643 TEST_F(RegAllocLinearScanTest, DynPhiMovesOverwriting)
644 {
645 Graph *graph = CreateDynEmptyGraph();
646 if (graph->GetArch() != Arch::AARCH64) {
647 return;
648 }
649
650 GRAPH(graph)
651 {
652 CONSTANT(0U, 0xffff000000000000U).any();
653
654 BASIC_BLOCK(2U, -1L)
655 {
656 INST(1U, Opcode::Return).any().Inputs(0U);
657 }
658 }
659 InitUsedRegs(graph);
660 auto resolver = SpillFillsResolver(graph);
661 // Use the last available register as a temp
662 auto sf = graph->CreateInstSpillFill();
663 auto expectedSf = graph->CreateInstSpillFill();
664 TestPhiMovesOverwriting<DataType::ANY>(graph, sf, expectedSf);
665 }
666
TEST_F(RegAllocLinearScanTest,BrokenTriangleWithEmptyBlock)667 TEST_F(RegAllocLinearScanTest, BrokenTriangleWithEmptyBlock)
668 {
669 GRAPH(GetGraph())
670 {
671 PARAMETER(0U, 0U).s64().DstReg(0U);
672 PARAMETER(1U, 1U).s64().DstReg(2U);
673 BASIC_BLOCK(2U, 3U, 4U)
674 {
675 INST(2U, Opcode::Compare).b().CC(CC_LT).SrcType(DataType::Type::INT64).Inputs(1U, 0U);
676 INST(3U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(2U);
677 }
678 BASIC_BLOCK(3U, 4U) {}
679 BASIC_BLOCK(4U, -1L)
680 {
681 INST(4U, Opcode::Phi).s64().Inputs({{2U, 1U}, {3U, 0U}}).DstReg(0U);
682 INST(5U, Opcode::Return).s64().Inputs(4U);
683 }
684 }
685 ASSERT_FALSE(GetGraph()->RunPass<Cleanup>());
686
687 // Create reg_mask with small amount available general registers to force spill-fills
688 auto regalloc = RegAllocLinearScan(GetGraph());
689 auto result = regalloc.Run();
690 if (GetGraph()->GetCallingConvention() == nullptr) {
691 ASSERT_FALSE(result);
692 return;
693 }
694 ASSERT_TRUE(result);
695 ASSERT_TRUE(GetGraph()->RunPass<Cleanup>());
696
697 auto graph = CreateEmptyGraph();
698 GRAPH(graph)
699 {
700 PARAMETER(0U, 0U).s64();
701 PARAMETER(1U, 1U).s64();
702 BASIC_BLOCK(2U, 4U, 5U)
703 {
704 INST(2U, Opcode::Compare).b().CC(CC_LT).SrcType(DataType::Type::INT64).Inputs(1U, 0U);
705 INST(3U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(2U);
706 }
707 BASIC_BLOCK(5U, 4U)
708 {
709 INST(6U, Opcode::SpillFill);
710 }
711 BASIC_BLOCK(4U, -1L)
712 {
713 INST(4U, Opcode::Phi).s64().Inputs({{2U, 0U}, {5U, 1U}});
714 INST(5U, Opcode::Return).s64().Inputs(4U);
715 }
716 }
717 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
718 }
719
TEST_F(RegAllocLinearScanTest,LoadArrayPair)720 TEST_F(RegAllocLinearScanTest, LoadArrayPair)
721 {
722 auto graph = CreateEmptyGraph();
723 GRAPH(graph)
724 {
725 CONSTANT(0U, 0x2aU).s64();
726 BASIC_BLOCK(2U, -1L)
727 {
728 INST(44U, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68U);
729 INST(3U, Opcode::NewArray).ref().Inputs(44U, 0U).TypeId(77U);
730 INST(4U, Opcode::SaveState).Inputs(3U).SrcVregs({0U});
731 INST(5U, Opcode::NullCheck).ref().Inputs(3U, 4U);
732 INST(6U, Opcode::LoadArrayPairI).s64().Inputs(5U).Imm(0x0U);
733 INST(7U, Opcode::LoadPairPart).s64().Inputs(6U).Imm(0x0U);
734 INST(8U, Opcode::LoadPairPart).s64().Inputs(6U).Imm(0x1U);
735
736 INST(9U, Opcode::SaveState).Inputs(3U).SrcVregs({0U});
737 INST(10U, Opcode::ZeroCheck).s64().Inputs(7U, 9U);
738 INST(11U, Opcode::Div).s64().Inputs(10U, 8U);
739 INST(12U, Opcode::Return).s64().Inputs(11U);
740 }
741 }
742 auto result = graph->RunPass<RegAllocLinearScan>();
743 if (graph->GetCallingConvention() == nullptr) {
744 ASSERT_FALSE(result);
745 return;
746 }
747 ASSERT_TRUE(result);
748
749 auto &div = INS(11U);
750 auto &loadPair = INS(6U);
751 for (size_t i = 0; i < div.GetInputsCount(); ++i) {
752 if (div.GetSrcReg(0U) != loadPair.GetDstReg(0U)) {
753 auto prev = div.GetPrev();
754 ASSERT_EQ(prev->GetOpcode(), Opcode::SpillFill);
755 ASSERT_EQ(prev->CastToSpillFill()->GetSpillFill(0U).DstValue(), div.GetSrcReg(0U));
756 }
757 }
758 }
759
TEST_F(RegAllocLinearScanTest,CheckInputTypeInStore)760 TEST_F(RegAllocLinearScanTest, CheckInputTypeInStore)
761 {
762 auto graph = CreateEmptyGraph();
763 if (graph->GetArch() != Arch::AARCH64) {
764 return;
765 }
766 GRAPH(graph)
767 {
768 CONSTANT(0U, nullptr).ref();
769 CONSTANT(1U, 0x2aU).s64();
770 CONSTANT(2U, 1.1_D).f64();
771 BASIC_BLOCK(2U, -1L)
772 {
773 INST(3U, Opcode::SaveState).Inputs(0U, 2U).SrcVregs({0U, 1U});
774 INST(4U, Opcode::NullCheck).ref().Inputs(0U, 3U);
775 INST(5U, Opcode::StoreObject).f64().Inputs(4U, 2U);
776 INST(6U, Opcode::Return).s64().Inputs(1U);
777 }
778 }
779 auto result = graph->RunPass<RegAllocLinearScan>();
780 if (graph->GetCallingConvention() == nullptr) {
781 ASSERT_FALSE(result);
782 return;
783 }
784 ASSERT_TRUE(result);
785
786 auto &store = INS(5U);
787 // check zero reg
788 ASSERT_EQ(store.GetSrcReg(0U), 31U);
789 }
790
TEST_F(RegAllocLinearScanTest,NullCheckAsPhiInput)791 TEST_F(RegAllocLinearScanTest, NullCheckAsPhiInput)
792 {
793 auto graph = CreateEmptyGraph();
794 GRAPH(graph)
795 {
796 PARAMETER(0U, 0U).ref();
797 PARAMETER(1U, 1U).s64();
798 PARAMETER(2U, 2U).s64();
799 PARAMETER(3U, 3U).ref();
800 BASIC_BLOCK(2U, 3U, 4U)
801 {
802 INST(4U, Opcode::If).SrcType(DataType::INT64).CC(CC_EQ).Inputs(1U, 2U);
803 }
804 BASIC_BLOCK(3U, 5U)
805 {
806 INST(6U, Opcode::SaveState).Inputs(1U, 2U).SrcVregs({0U, 1U});
807 INST(7U, Opcode::NullCheck).ref().Inputs(0U, 6U);
808 }
809 BASIC_BLOCK(4U, 5U) {}
810 BASIC_BLOCK(5U, -1L)
811 {
812 INST(11U, Opcode::Phi).ref().Inputs(7U, 3U);
813 INST(12U, Opcode::Return).ref().Inputs(11U);
814 }
815 }
816
817 EXPECT_TRUE(graph->RunPass<RegAllocLinearScan>());
818 auto phiLocation = Location::MakeRegister(INS(11U).GetDstReg());
819 auto paramLocation = INS(0U).CastToParameter()->GetLocationData().GetDst();
820 if (phiLocation != paramLocation) {
821 auto sfInst = BB(3U).GetLastInst();
822 ASSERT_TRUE(sfInst->IsSpillFill());
823 auto spillFill = sfInst->CastToSpillFill()->GetSpillFill(0U);
824 EXPECT_EQ(spillFill.GetSrc(), paramLocation);
825 EXPECT_EQ(spillFill.GetDst(), phiLocation);
826 }
827 }
828
TEST_F(RegAllocLinearScanTest,MultiDestInstruction)829 TEST_F(RegAllocLinearScanTest, MultiDestInstruction)
830 {
831 auto graph = CreateEmptyGraph();
832 GRAPH(graph)
833 {
834 CONSTANT(0U, 1000U);
835 CONSTANT(1U, 1U);
836 BASIC_BLOCK(2U, -1L)
837 {
838 INST(44U, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68U);
839 INST(2U, Opcode::NewArray).ref().Inputs(44U, 0U).TypeId(1U);
840 INST(3U, Opcode::LoadArrayPairI).s32().Inputs(2U).Imm(0x0U);
841 INST(4U, Opcode::LoadPairPart).s32().Inputs(3U).Imm(0x0U);
842 INST(5U, Opcode::LoadPairPart).s32().Inputs(3U).Imm(0x1U);
843 INST(6U, Opcode::Add).s32().Inputs(1U, 4U);
844 INST(7U, Opcode::Add).s32().Inputs(6U, 5U);
845 INST(8U, Opcode::Return).s32().Inputs(7U);
846 }
847 }
848 // Run regalloc without free regs to push all dst on the stack
849 auto regalloc = RegAllocLinearScan(graph);
850 RegAllocResolver(graph).ResolveCatchPhis();
851 uint32_t regMask = GetGraph()->GetArch() != Arch::AARCH32 ? 0x000FFFFFU : 0xAAAAAAFFU;
852 regalloc.SetRegMask(RegMask {regMask});
853 regalloc.SetVRegMask(VRegMask {});
854 regalloc.Run();
855
856 auto loadPair = &INS(3U);
857 ASSERT_NE(loadPair->GetDstReg(0U), loadPair->GetDstReg(1U));
858 ASSERT_EQ(INS(6U).GetSrcReg(1U), loadPair->GetDstReg(0U));
859 ASSERT_EQ(INS(7U).GetSrcReg(1U), loadPair->GetDstReg(1U));
860 }
861
862 /// Create COUNT constants and assign COUNT registers for them
TEST_F(RegAllocLinearScanTest,DynamicRegsMask)863 TEST_F(RegAllocLinearScanTest, DynamicRegsMask)
864 {
865 auto graph = CreateEmptyBytecodeGraph();
866 graph->CreateStartBlock();
867 graph->CreateEndBlock();
868
869 const size_t count = 100;
870 auto savePoint = graph->CreateInstSafePoint();
871 auto block = CreateEmptyBlock(graph);
872 block->AppendInst(savePoint);
873 block->AppendInst(graph->CreateInstReturnVoid());
874 graph->GetStartBlock()->AddSucc(block);
875 block->AddSucc(graph->GetEndBlock());
876
877 for (size_t i = 0; i < count; i++) {
878 savePoint->AppendInput(graph->FindOrCreateConstant(i));
879 savePoint->SetVirtualRegister(i, VirtualRegister(i, VRegInfo::VRegType::VREG));
880 }
881 auto result = graph->RunPass<RegAllocLinearScan>(EmptyRegMask());
882 ASSERT_TRUE(result);
883 for (size_t i = 1; i < count; i++) {
884 ASSERT_EQ(graph->FindOrCreateConstant(i)->GetDstReg(), i);
885 }
886 }
887
TEST_F(RegAllocLinearScanTest,MultiDestAsCallInput)888 TEST_F(RegAllocLinearScanTest, MultiDestAsCallInput)
889 {
890 auto graph = CreateEmptyGraph();
891 GRAPH(graph)
892 {
893 CONSTANT(0U, 1000U);
894 CONSTANT(1U, 1U);
895 BASIC_BLOCK(2U, -1L)
896 {
897 INST(44U, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68U);
898 INST(2U, Opcode::NewArray).ref().Inputs(44U, 0U).TypeId(1U);
899 INST(3U, Opcode::LoadArrayPairI).s32().Inputs(2U).Imm(0x0U);
900 INST(4U, Opcode::LoadPairPart).s32().Inputs(3U).Imm(0x0U);
901 INST(5U, Opcode::LoadPairPart).s32().Inputs(3U).Imm(0x1U);
902 INST(6U, Opcode::SaveState).Inputs().SrcVregs({});
903 INST(7U, Opcode::CallStatic).s32().InputsAutoType(4U, 5U, 6U);
904 INST(8U, Opcode::ZeroCheck).s32().Inputs(5U, 6U);
905 INST(9U, Opcode::Div).s32().Inputs(4U, 8U);
906 INST(10U, Opcode::Return).s32().Inputs(9U);
907 }
908 }
909 auto regalloc = RegAllocLinearScan(graph);
910 uint32_t regMask = GetGraph()->GetArch() != Arch::AARCH32 ? 0x000FFFFFU : 0xAAAAAAAFU;
911 regalloc.SetRegMask(RegMask {regMask});
912 regalloc.SetVRegMask(VRegMask {});
913 auto result = regalloc.Run();
914 if (graph->GetCallingConvention() == nullptr) {
915 ASSERT_FALSE(result);
916 return;
917 }
918 ASSERT_TRUE(result);
919
920 auto loadArr = &INS(3U);
921 auto div = &INS(9U);
922 auto callInst = INS(7U).CastToCallStatic();
923 auto spillFill = callInst->GetPrev()->CastToSpillFill();
924 // Check split before call
925 for (auto i = 0U; i < 2U; i++) {
926 ASSERT_EQ(spillFill->GetSpillFill(i).SrcValue(), loadArr->GetDstReg(i));
927 if (loadArr->GetDstReg(i) == callInst->GetSrcReg(i)) {
928 // LoadArrayPairI -> R1, R2 (caller-saved assigned)
929 // R1 -> Rx, R2 -> Ry
930 // call(R1, R2)
931 ASSERT_EQ(div->GetSrcReg(i), spillFill->GetSpillFill(i).DstValue());
932 } else {
933 // LoadArrayPairI -> RX, RY (callee-saved assigned)
934 // RX -> R1, RY -> R2
935 // call(R1, R2)
936 ASSERT_EQ(div->GetSrcReg(i), spillFill->GetSpillFill(i).SrcValue());
937 }
938 }
939 }
940
TEST_F(RegAllocLinearScanTest,MultiDestInLoop)941 TEST_F(RegAllocLinearScanTest, MultiDestInLoop)
942 {
943 auto graph = CreateEmptyGraph();
944 GRAPH(graph)
945 {
946 CONSTANT(0U, 0U);
947 CONSTANT(1U, 1U);
948 CONSTANT(2U, 1000U);
949
950 BASIC_BLOCK(2U, 3U)
951 {
952 INST(44U, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68U);
953 INST(5U, Opcode::NewArray).ref().Inputs(44U, 2U).TypeId(1U);
954 }
955 BASIC_BLOCK(3U, 5U, 4U)
956 {
957 INST(6U, Opcode::Phi).s32().Inputs(0U, 12U); // pair part
958 INST(7U, Opcode::Phi).s32().Inputs(1U, 13U); // pair part
959 INST(8U, Opcode::Phi).s32().Inputs(0U, 10U); // add
960 INST(9U, Opcode::Phi).s32().Inputs(0U, 15U); // add
961 INST(16U, Opcode::SafePoint).Inputs(5U, 6U, 7U).SrcVregs({0U, 1U, 2U});
962 INST(10U, Opcode::AddI).s32().Inputs(8U).Imm(1U);
963 INST(11U, Opcode::LoadArrayPair).s32().Inputs(5U, 10U);
964 INST(12U, Opcode::LoadPairPart).s32().Inputs(11U).Imm(0U);
965 INST(13U, Opcode::LoadPairPart).s32().Inputs(11U).Imm(1U);
966 INST(14U, Opcode::If).SrcType(DataType::INT32).CC(CC_EQ).Inputs(12U, 13U);
967 }
968 BASIC_BLOCK(4U, 3U)
969 {
970 INST(15U, Opcode::SubI).s32().Inputs(9U).Imm(2U);
971 }
972 BASIC_BLOCK(5U, -1L)
973 {
974 INST(20U, Opcode::Return).s32().Inputs(9U);
975 }
976 }
977 auto regalloc = RegAllocLinearScan(graph);
978 regalloc.SetRegMask(RegMask {0xFFFFAAAAU});
979 ASSERT_TRUE(regalloc.Run());
980
981 auto loadPair = &INS(11U);
982 EXPECT_NE(loadPair->GetDstReg(0U), INVALID_REG);
983 EXPECT_NE(loadPair->GetDstReg(1U), INVALID_REG);
984 // LoadArrayPair, SubI and AddI should use unique registers
985 std::set<Register> regs;
986 regs.insert(INS(10U).GetDstReg());
987 regs.insert(INS(15U).GetDstReg());
988 regs.insert(loadPair->GetDstReg(0U));
989 regs.insert(loadPair->GetDstReg(1U));
990 EXPECT_EQ(regs.size(), 4U);
991 }
992
SRC_GRAPH(ResolveSegmentedCallInputs,Graph * graph)993 SRC_GRAPH(ResolveSegmentedCallInputs, Graph *graph)
994 {
995 GRAPH(graph)
996 {
997 PARAMETER(0U, 0U).u64();
998
999 BASIC_BLOCK(2U, -1L)
1000 {
1001 INST(2U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1002 INST(3U, Opcode::CallStatic).u64().Inputs({{DataType::UINT64, 0U}, {DataType::NO_TYPE, 2U}});
1003 INST(4U, Opcode::SaveState).Inputs(0U, 3U).SrcVregs({0U, 3U});
1004 INST(5U, Opcode::CallStatic)
1005 .u64()
1006 .Inputs({{DataType::UINT64, 0U}, {DataType::UINT64, 3U}, {DataType::NO_TYPE, 4U}});
1007 INST(6U, Opcode::Return).u64().Inputs(5U);
1008 }
1009 }
1010 }
1011
TEST_F(RegAllocLinearScanTest,ResolveSegmentedCallInputs)1012 TEST_F(RegAllocLinearScanTest, ResolveSegmentedCallInputs)
1013 {
1014 auto graph = CreateEmptyGraph();
1015 src_graph::ResolveSegmentedCallInputs::CREATE(graph);
1016
1017 graph->RunPass<LivenessAnalyzer>();
1018 auto &la = graph->GetAnalysis<LivenessAnalyzer>();
1019 auto param0 = la.GetInstLifeIntervals(&INS(0U));
1020 auto call0 = (&INS(3U))->CastToCallStatic();
1021 auto call1 = (&INS(5U))->CastToCallStatic();
1022 // split at save state to force usage of stack location as call's input
1023 auto paramSplit0 = param0->SplitAt(la.GetInstLifeIntervals(&INS(2U))->GetBegin() - 1U, GetAllocator());
1024 paramSplit0->SetLocation(Location::MakeStackSlot(42U));
1025 paramSplit0->SetType(DataType::UINT64);
1026
1027 auto paramSplit1 = paramSplit0->SplitAt(la.GetInstLifeIntervals(call1)->GetBegin() - 1U, GetAllocator());
1028 paramSplit1->SetReg(6U);
1029 paramSplit1->SetType(DataType::UINT64);
1030
1031 graph->SetStackSlotsCount(MAX_NUM_STACK_SLOTS);
1032 auto regalloc = RegAllocLinearScan(graph);
1033 regalloc.SetRegMask(RegMask {0x000FFFFFU});
1034 regalloc.SetVRegMask(VRegMask {});
1035 auto result = regalloc.Run();
1036 if (graph->GetCallingConvention() == nullptr) {
1037 ASSERT_FALSE(result);
1038 return;
1039 }
1040 ASSERT_TRUE(result);
1041 auto call0Sf = call0->GetPrev()->CastToSpillFill()->GetSpillFill(0U);
1042 EXPECT_EQ(call0Sf.SrcType(), LocationType::STACK);
1043 EXPECT_EQ(call0Sf.SrcValue(), 42U);
1044
1045 const auto &call1Sfs = call1->GetPrev()->CastToSpillFill()->GetSpillFills();
1046 auto it = std::find_if(call1Sfs.begin(), call1Sfs.end(),
1047 [](auto sf) { return sf.SrcType() == LocationType::REGISTER && sf.SrcValue() == 6; });
1048 EXPECT_NE(it, call1Sfs.end());
1049 }
1050
TEST_F(RegAllocLinearScanTest,ResolveSegmentedSaveStateInputs)1051 TEST_F(RegAllocLinearScanTest, ResolveSegmentedSaveStateInputs)
1052 {
1053 auto graph = CreateEmptyGraph();
1054 GRAPH(graph)
1055 {
1056 PARAMETER(0U, 0U).u64();
1057 PARAMETER(1U, 1U).ref();
1058
1059 BASIC_BLOCK(2U, -1L)
1060 {
1061 INST(2U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 1U});
1062 INST(3U, Opcode::NullCheck).ref().Inputs(1U, 2U);
1063 INST(4U, Opcode::CallVirtual).u64().Inputs({{DataType::REFERENCE, 3U}, {DataType::NO_TYPE, 2U}});
1064 INST(5U, Opcode::Add).u64().Inputs(0U, 4U);
1065 INST(6U, Opcode::Return).u64().Inputs(5U);
1066 }
1067 }
1068
1069 graph->RunPass<LivenessAnalyzer>();
1070 auto &la = graph->GetAnalysis<LivenessAnalyzer>();
1071 auto param0 = la.GetInstLifeIntervals(&INS(0U));
1072 auto call = &INS(4U);
1073 auto paramSplit = param0->SplitAt(la.GetInstLifeIntervals(call)->GetBegin() - 1U, GetAllocator());
1074 static constexpr auto REG_FOR_SPLIT = Register(20U);
1075 paramSplit->SetReg(REG_FOR_SPLIT);
1076 paramSplit->SetType(DataType::UINT64);
1077
1078 auto regalloc = RegAllocLinearScan(graph);
1079 // on AARCH32 use only caller-saved register pairs
1080 uint32_t regMask = GetGraph()->GetArch() != Arch::AARCH32 ? 0xFFFFFFF0U : 0xFFFFFFFAU;
1081 regalloc.SetRegMask(RegMask {regMask});
1082 regalloc.SetVRegMask(VRegMask {});
1083 auto result = regalloc.Run();
1084 if (graph->GetCallingConvention() == nullptr) {
1085 ASSERT_FALSE(result);
1086 return;
1087 }
1088 ASSERT_TRUE(result);
1089
1090 auto nullCheck = &INS(3U);
1091 auto callSaveState = call->GetInput(call->GetInputsCount() - 1L).GetInst()->CastToSaveState();
1092 auto nullCheckSaveState = nullCheck->GetInput(nullCheck->GetInputsCount() - 1L).GetInst()->CastToSaveState();
1093
1094 ASSERT_NE(callSaveState, nullCheckSaveState);
1095 }
1096
TEST_F(RegAllocLinearScanTest,ResolveSegmentedInstInputs)1097 TEST_F(RegAllocLinearScanTest, ResolveSegmentedInstInputs)
1098 {
1099 auto graph = CreateEmptyGraph();
1100 GRAPH(graph)
1101 {
1102 PARAMETER(0U, 0U).u64();
1103
1104 BASIC_BLOCK(2U, -1L)
1105 {
1106 INST(2U, Opcode::Add).u64().Inputs(0U, 0U);
1107 INST(3U, Opcode::Add).u64().Inputs(0U, 2U);
1108 INST(4U, Opcode::Return).u64().Inputs(3U);
1109 }
1110 }
1111
1112 graph->RunPass<LivenessAnalyzer>();
1113 auto &la = graph->GetAnalysis<LivenessAnalyzer>();
1114 auto param0 = la.GetInstLifeIntervals(&INS(0U));
1115 auto paramSplit0 = param0->SplitAt(la.GetInstLifeIntervals(&INS(3U))->GetBegin() - 1U, GetAllocator());
1116 static constexpr auto REG_FOR_SPLIT = Register(20U);
1117 paramSplit0->SetReg(REG_FOR_SPLIT);
1118 paramSplit0->SetType(DataType::UINT64);
1119
1120 auto regalloc = RegAllocLinearScan(graph);
1121 uint32_t regMask = GetGraph()->GetArch() != Arch::AARCH32 ? 0xFFFFFFF0U : 0xFFFFFFAAU;
1122 regalloc.SetRegMask(RegMask {regMask});
1123 regalloc.SetVRegMask(VRegMask {});
1124 auto result = regalloc.Run();
1125 if (graph->GetCallingConvention() == nullptr) {
1126 ASSERT_FALSE(result);
1127 return;
1128 }
1129 ASSERT_TRUE(result);
1130 auto addSf = INS(3U).GetPrev();
1131 ASSERT_TRUE(addSf->IsSpillFill());
1132
1133 EXPECT_EQ(INS(3U).GetSrcReg(0U), REG_FOR_SPLIT);
1134 SpillFillData expectedSf {LocationType::REGISTER, LocationType::REGISTER, param0->GetReg(), REG_FOR_SPLIT,
1135 DataType::UINT64};
1136 EXPECT_EQ(addSf->CastToSpillFill()->GetSpillFill(0U), expectedSf);
1137 }
1138
TEST_F(RegAllocLinearScanTest,ResolveSegmentedSafePointInput)1139 TEST_F(RegAllocLinearScanTest, ResolveSegmentedSafePointInput)
1140 {
1141 auto graph = CreateEmptyGraph();
1142 GRAPH(graph)
1143 {
1144 PARAMETER(0U, 0U).u64();
1145
1146 BASIC_BLOCK(2U, -1L)
1147 {
1148 INST(2U, Opcode::SafePoint).Inputs(0U).SrcVregs({0U});
1149 INST(3U, Opcode::Return).u64().Inputs(0U);
1150 }
1151 }
1152
1153 graph->RunPass<LivenessAnalyzer>();
1154 auto &la = graph->GetAnalysis<LivenessAnalyzer>();
1155 auto param0 = la.GetInstLifeIntervals(&INS(0U));
1156 auto sp = &INS(2U);
1157 auto paramSplit = param0->SplitAt(la.GetInstLifeIntervals(sp)->GetBegin() - 1U, GetAllocator());
1158 static constexpr auto STACK_SLOT = StackSlot(1U);
1159 paramSplit->SetLocation(Location::MakeStackSlot(STACK_SLOT));
1160 paramSplit->SetType(DataType::UINT64);
1161 auto retSplit = paramSplit->SplitAt(la.GetInstLifeIntervals(&INS(3U))->GetBegin() - 1U, GetAllocator());
1162 retSplit->SetReg(0U);
1163 retSplit->SetType(DataType::UINT64);
1164
1165 graph->SetStackSlotsCount(MAX_NUM_STACK_SLOTS);
1166 auto regalloc = RegAllocLinearScan(graph);
1167 uint32_t regMask = GetGraph()->GetArch() != Arch::AARCH32 ? 0xFFFFFFF0U : 0xFFFFFFAAU;
1168 regalloc.SetRegMask(RegMask {regMask});
1169 regalloc.SetVRegMask(VRegMask {});
1170 regalloc.SetSlotsCount(MAX_NUM_STACK_SLOTS);
1171 auto result = regalloc.Run();
1172 if (graph->GetCallingConvention() == nullptr) {
1173 ASSERT_FALSE(result);
1174 return;
1175 }
1176 ASSERT_TRUE(result);
1177 }
1178
SRC_GRAPH(ResolveSegmentedPhiInput,Graph * graph)1179 SRC_GRAPH(ResolveSegmentedPhiInput, Graph *graph)
1180 {
1181 GRAPH(graph)
1182 {
1183 PARAMETER(0U, 0U).u64();
1184 PARAMETER(1U, 1U).u64();
1185
1186 BASIC_BLOCK(2U, 3U, 4U)
1187 {
1188 INST(2U, Opcode::Compare).b().Inputs(0U, 1U);
1189 INST(3U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(2U);
1190 }
1191
1192 BASIC_BLOCK(3U, 5U)
1193 {
1194 INST(4U, Opcode::Add).u64().Inputs(0U, 1U);
1195 }
1196
1197 BASIC_BLOCK(4U, 5U)
1198 {
1199 INST(5U, Opcode::Sub).u64().Inputs(0U, 1U);
1200 }
1201
1202 BASIC_BLOCK(5U, -1L)
1203 {
1204 INST(6U, Opcode::Phi).u64().Inputs(0U, 5U);
1205 INST(7U, Opcode::Phi).u64().Inputs(4U, 1U);
1206 INST(8U, Opcode::Mul).u64().Inputs(6U, 7U);
1207 INST(9U, Opcode::Return).u64().Inputs(8U);
1208 }
1209 }
1210 }
1211
TEST_F(RegAllocLinearScanTest,ResolveSegmentedPhiInput)1212 TEST_F(RegAllocLinearScanTest, ResolveSegmentedPhiInput)
1213 {
1214 auto graph = CreateEmptyGraph();
1215 src_graph::ResolveSegmentedPhiInput::CREATE(graph);
1216
1217 graph->RunPass<LivenessAnalyzer>();
1218 auto &la = graph->GetAnalysis<LivenessAnalyzer>();
1219 auto param0 = la.GetInstLifeIntervals(&INS(0U));
1220 auto paramSplit0 = param0->SplitAt(la.GetInstLifeIntervals(&INS(4U))->GetBegin() - 1U, GetAllocator());
1221 static constexpr auto REG_FOR_SPLIT = Register(20U);
1222 paramSplit0->SetReg(REG_FOR_SPLIT);
1223 paramSplit0->SetType(DataType::UINT64);
1224
1225 auto regalloc = RegAllocLinearScan(graph);
1226 uint32_t regMask = GetGraph()->GetArch() != Arch::AARCH32 ? 0xFFFFFFF0U : 0xFFFFFFAAU;
1227 regalloc.SetRegMask(RegMask {regMask});
1228 regalloc.SetVRegMask(VRegMask {});
1229 auto result = regalloc.Run();
1230 if (graph->GetCallingConvention() == nullptr) {
1231 ASSERT_FALSE(result);
1232 return;
1233 }
1234 ASSERT_TRUE(result);
1235
1236 auto lastInst = INS(4U).GetBasicBlock()->GetLastInst();
1237 ASSERT_TRUE(lastInst->IsSpillFill());
1238 bool spillFillFound = false;
1239 SpillFillData expectedSf {LocationType::REGISTER, LocationType::REGISTER, REG_FOR_SPLIT, INS(6U).GetDstReg(),
1240 DataType::UINT64};
1241
1242 for (auto &sf : lastInst->CastToSpillFill()->GetSpillFills()) {
1243 spillFillFound |= expectedSf == sf;
1244 }
1245 ASSERT_TRUE(spillFillFound);
1246 }
1247
SRC_GRAPH(DISABLED_ResolveSegmentedCatchPhiInputs,Graph * graph)1248 SRC_GRAPH(DISABLED_ResolveSegmentedCatchPhiInputs, Graph *graph)
1249 {
1250 GRAPH(graph)
1251 {
1252 PARAMETER(0U, 0U).ref();
1253 PARAMETER(1U, 1U).ref();
1254 PARAMETER(2U, 2U).b();
1255
1256 BASIC_BLOCK(2U, 3U, 5U)
1257 {
1258 INST(3U, Opcode::Try).CatchTypeIds({0U});
1259 }
1260
1261 BASIC_BLOCK(3U, 4U)
1262 {
1263 INST(10U, Opcode::SaveState).Inputs(0U, 1U, 2U).SrcVregs({0U, 1U, 2U});
1264 INST(4U, Opcode::CallStatic).b().InputsAutoType(0U, 1U, 2U, 10U);
1265 INST(11U, Opcode::SaveState).Inputs(0U, 1U, 2U, 4U).SrcVregs({0U, 1U, 2U, 3U});
1266 INST(9U, Opcode::CallStatic).b().InputsAutoType(0U, 1U, 2U, 11U);
1267 INST(5U, Opcode::And).b().Inputs(4U, 9U);
1268 }
1269
1270 BASIC_BLOCK(4U, 6U, 5U) {} // Try-end
1271
1272 BASIC_BLOCK(5U, -1L)
1273 {
1274 INST(7U, Opcode::CatchPhi).b().Inputs(2U, 4U);
1275 INST(8U, Opcode::Return).b().Inputs(7U);
1276 }
1277
1278 BASIC_BLOCK(6U, -1L)
1279 {
1280 INST(6U, Opcode::Return).b().Inputs(5U);
1281 }
1282 }
1283 }
1284
1285 /**
1286 * Currently `CatchPhi` can be visited by `LinearScan` in the `BytecodeOptimizer` mode only, where splits are not
1287 * posible, so that there is assertion in the `LinearScan` that interval in not splitted, which breaks this tests
1288 */
TEST_F(RegAllocLinearScanTest,DISABLED_ResolveSegmentedCatchPhiInputs)1289 TEST_F(RegAllocLinearScanTest, DISABLED_ResolveSegmentedCatchPhiInputs)
1290 {
1291 auto graph = CreateEmptyBytecodeGraph();
1292 src_graph::DISABLED_ResolveSegmentedCatchPhiInputs::CREATE(graph);
1293
1294 BB(2U).SetTryId(0U);
1295 BB(3U).SetTryId(0U);
1296 BB(4U).SetTryId(0U);
1297
1298 auto catchPhi = (&INS(7U))->CastToCatchPhi();
1299 catchPhi->AppendThrowableInst(&INS(4U));
1300 catchPhi->AppendThrowableInst(&INS(9U));
1301
1302 graph->AppendThrowableInst(&INS(4U), &BB(5U));
1303 graph->AppendThrowableInst(&INS(9U), &BB(5U));
1304 INS(3U).CastToTry()->SetTryEndBlock(&BB(4U));
1305
1306 graph->RunPass<LivenessAnalyzer>();
1307 auto &la = graph->GetAnalysis<LivenessAnalyzer>();
1308
1309 auto con = la.GetInstLifeIntervals(&INS(2U));
1310 auto streq = &INS(4U);
1311 auto conSplit = con->SplitAt(la.GetInstLifeIntervals(streq)->GetBegin() - 1L, GetAllocator());
1312
1313 auto constexpr SPLIT_REG = 10;
1314 conSplit->SetReg(SPLIT_REG);
1315 conSplit->SetType(DataType::UINT32);
1316
1317 auto regalloc = RegAllocLinearScan(graph, EmptyRegMask());
1318 auto result = regalloc.Run();
1319 ASSERT_TRUE(result);
1320
1321 auto catchPhiReg = la.GetInstLifeIntervals(&INS(7U))->GetReg();
1322 auto sfBeforeIns4 = (&INS(4U))->GetPrev()->CastToSpillFill();
1323 EXPECT_EQ(std::count(sfBeforeIns4->GetSpillFills().begin(), sfBeforeIns4->GetSpillFills().end(),
1324 SpillFillData {LocationType::REGISTER, LocationType::REGISTER, SPLIT_REG, catchPhiReg,
1325 DataType::UINT32}),
1326 1U);
1327
1328 auto ins4Reg = la.GetInstLifeIntervals(&INS(4U))->GetReg();
1329 auto sfBeforeIns9 = (&INS(9U))->GetPrev()->CastToSpillFill();
1330 EXPECT_EQ(std::count(sfBeforeIns9->GetSpillFills().begin(), sfBeforeIns9->GetSpillFills().end(),
1331 SpillFillData {LocationType::REGISTER, LocationType::REGISTER, ins4Reg, catchPhiReg,
1332 DataType::UINT32}),
1333 1U);
1334 }
1335
SRC_GRAPH(RematConstants,Graph * graph)1336 SRC_GRAPH(RematConstants, Graph *graph)
1337 {
1338 GRAPH(graph)
1339 {
1340 CONSTANT(0U, 0U).s32();
1341 CONSTANT(1U, 1U).s32();
1342 CONSTANT(2U, 2U).s32();
1343 CONSTANT(13U, 1000U).s32();
1344 CONSTANT(3U, 0.5_D).f64();
1345 CONSTANT(4U, 10.0_D).f64();
1346 CONSTANT(5U, 26.66_D).f64();
1347 CONSTANT(14U, 2.0_D).f64();
1348
1349 BASIC_BLOCK(2U, -1L)
1350 {
1351 INST(6U, Opcode::Add).s32().Inputs(0U, 1U);
1352 INST(7U, Opcode::Add).s32().Inputs(6U, 2U);
1353 INST(15U, Opcode::Add).s32().Inputs(7U, 13U);
1354 INST(20U, Opcode::SaveState).NoVregs();
1355 INST(8U, Opcode::CallStatic).f64().InputsAutoType(15U, 3U, 4U, 20U);
1356 INST(9U, Opcode::Add).f64().Inputs(4U, 5U);
1357 INST(10U, Opcode::Add).f64().Inputs(8U, 3U);
1358 INST(16U, Opcode::Add).f64().Inputs(10U, 14U);
1359 INST(21U, Opcode::SaveState).NoVregs();
1360 INST(11U, Opcode::CallStatic).f64().InputsAutoType(0U, 1U, 2U, 3U, 4U, 5U, 13U, 14U, 16U, 21U);
1361 INST(12U, Opcode::Return).f64().Inputs(11U);
1362 }
1363 }
1364 }
1365
TEST_F(RegAllocLinearScanTest,RematConstants)1366 TEST_F(RegAllocLinearScanTest, RematConstants)
1367 {
1368 auto graph = CreateEmptyGraph();
1369 src_graph::RematConstants::CREATE(graph);
1370
1371 auto regalloc = RegAllocLinearScan(graph);
1372 uint32_t regMask = GetGraph()->GetArch() != Arch::AARCH32 ? 0xFFFFFFE1U : 0xFABFFFFFU;
1373 regalloc.SetRegMask(RegMask {regMask});
1374 regalloc.SetVRegMask(VRegMask {regMask});
1375 auto result = regalloc.Run();
1376 if (graph->GetCallingConvention() == nullptr) {
1377 ASSERT_FALSE(result);
1378 return;
1379 }
1380 ASSERT_TRUE(result);
1381
1382 // Check inserted to the graph spill-fills
1383 EXPECT_TRUE(CheckImmediateSpillFill(&INS(15U), 1U));
1384 EXPECT_TRUE(CheckImmediateSpillFill(&INS(10U), 1U));
1385 EXPECT_TRUE(CheckImmediateSpillFill(&INS(16U), 1U));
1386
1387 // Check call instruction's spill-fills
1388 auto callInst = INS(11U).CastToCallStatic();
1389 auto spillFill = callInst->GetPrev()->CastToSpillFill();
1390 for (auto sf : spillFill->GetSpillFills()) {
1391 if (sf.SrcType() == LocationType::IMMEDIATE) {
1392 auto inputConst = graph->GetSpilledConstant(sf.SrcValue());
1393 auto it = std::find_if(callInst->GetInputs().begin(), callInst->GetInputs().end(),
1394 [inputConst](Input input) { return input.GetInst() == inputConst; });
1395 EXPECT_NE(it, callInst->GetInputs().end());
1396 } else {
1397 EXPECT_TRUE(sf.GetSrc().IsAnyRegister());
1398 }
1399 }
1400 }
1401
TEST_F(RegAllocLinearScanTest,LoadPairPartDiffRegisters)1402 TEST_F(RegAllocLinearScanTest, LoadPairPartDiffRegisters)
1403 {
1404 GRAPH(GetGraph())
1405 {
1406 PARAMETER(0U, 0U).ref();
1407 PARAMETER(11U, 1U).s64();
1408
1409 BASIC_BLOCK(2U, -1L)
1410 {
1411 INST(1U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1412 INST(2U, Opcode::NullCheck).ref().Inputs(0U, 1U);
1413 INST(3U, Opcode::LoadArrayPairI).s64().Inputs(2U).Imm(0x0U);
1414 INST(4U, Opcode::LoadPairPart).s64().Inputs(3U).Imm(0x0U);
1415 INST(5U, Opcode::LoadPairPart).s64().Inputs(3U).Imm(0x1U);
1416 INST(10U, Opcode::Add).s64().Inputs(5U, 11U);
1417 INST(6U, Opcode::SaveState).Inputs().SrcVregs({});
1418 INST(7U, Opcode::CallStatic).s64().InputsAutoType(4U, 5U, 10U, 6U);
1419 INST(8U, Opcode::Return).s64().Inputs(7U);
1420 }
1421 }
1422 auto regalloc = RegAllocLinearScan(GetGraph());
1423 uint32_t regMask = GetGraph()->GetArch() != Arch::AARCH32 ? 0xF3FFFFFFU : 0xFAFFFFFFU;
1424 regalloc.SetRegMask(RegMask {regMask});
1425 auto result = regalloc.Run();
1426 if (GetGraph()->GetCallingConvention() == nullptr) {
1427 ASSERT_FALSE(result);
1428 return;
1429 }
1430 ASSERT_TRUE(result);
1431 auto loadPairI = &INS(3U);
1432 EXPECT_NE(loadPairI->GetDstReg(0U), loadPairI->GetDstReg(1U));
1433 }
1434
TEST_F(RegAllocLinearScanTest,SpillRegistersAroundCall)1435 TEST_F(RegAllocLinearScanTest, SpillRegistersAroundCall)
1436 {
1437 GRAPH(GetGraph())
1438 {
1439 PARAMETER(0U, 0U).u32();
1440 PARAMETER(1U, 1U).f32();
1441
1442 BASIC_BLOCK(2U, -1L)
1443 {
1444 INST(2U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 1U});
1445 INST(3U, Opcode::CallStatic).u32().InputsAutoType(0U, 1U, 2U);
1446 INST(4U, Opcode::Add).u32().Inputs(0U, 3U);
1447 INST(5U, Opcode::Return).u32().Inputs(4U);
1448 }
1449 }
1450 auto regalloc = RegAllocLinearScan(GetGraph());
1451 ASSERT_TRUE(regalloc.Run());
1452
1453 // parameter 0 should be splitted before call and split should be used by add
1454 auto spillFill = (&INS(3U))->GetPrev();
1455 EXPECT_TRUE(spillFill->IsSpillFill());
1456 auto sf = spillFill->CastToSpillFill()->GetSpillFill(0U);
1457 auto paramDst = (&INS(0U))->GetDstReg();
1458 auto callSrc = (&INS(3U))->GetSrcReg(0U);
1459 auto addSrc = (&INS(4U))->GetSrcReg(0U);
1460 ASSERT_EQ(sf.SrcValue(), paramDst);
1461 if (callSrc == paramDst) {
1462 // param -> R1 (caller-saved assigned)
1463 // R1 -> Rx
1464 // call(R1, ..)
1465 ASSERT_EQ(addSrc, sf.DstValue());
1466 } else {
1467 // param -> Rx (callee-saved assigned)
1468 // Rx -> R1
1469 // call(R1, ..)
1470 ASSERT_EQ(addSrc, sf.SrcValue());
1471 }
1472 // all caller-saved regs should be spilled at call
1473 auto &lr = GetGraph()->GetAnalysis<LiveRegisters>();
1474 auto graph = GetGraph();
1475 lr.VisitIntervalsWithLiveRegisters(&INS(3), [graph](const auto &li) {
1476 auto rd = graph->GetRegisters();
1477 auto callerMask =
1478 DataType::IsFloatType(li->GetType()) ? rd->GetCallerSavedVRegMask() : rd->GetCallerSavedRegMask();
1479 ASSERT_FALSE(callerMask.Test(li->GetReg()));
1480 });
1481 }
1482
TEST_F(RegAllocLinearScanTest,SplitCallIntervalAroundNextCall)1483 TEST_F(RegAllocLinearScanTest, SplitCallIntervalAroundNextCall)
1484 {
1485 GRAPH(GetGraph())
1486 {
1487 PARAMETER(0U, 0U).u32();
1488 PARAMETER(1U, 1U).u32();
1489
1490 BASIC_BLOCK(2U, -1L)
1491 {
1492 INST(2U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 1U});
1493 INST(3U, Opcode::CallStatic).InputsAutoType(0U, 1U, 2U).f64();
1494 INST(4U, Opcode::Add).Inputs(3U, 3U).f64();
1495 INST(5U, Opcode::SaveState).Inputs(3U, 4U).SrcVregs({3U, 4U});
1496 INST(6U, Opcode::CallStatic).InputsAutoType(5U).u64();
1497 INST(7U, Opcode::Return).Inputs(3U).f64();
1498 }
1499 }
1500
1501 auto regalloc = RegAllocLinearScan(GetGraph());
1502 uint32_t regMask = GetGraph()->GetArch() != Arch::AARCH32 ? 0xFFFFFFF0U : 0xFFFFFFAAU;
1503 regalloc.SetRegMask(RegMask {regMask});
1504 regalloc.SetVRegMask(RegMask {regMask});
1505 ASSERT_TRUE(regalloc.Run());
1506
1507 // Spill after last use before next call
1508 auto spill = INS(4U).GetNext()->CastToSpillFill()->GetSpillFill(0U);
1509 // Fill before firt use after call
1510 auto fill = INS(7U).GetPrev()->CastToSpillFill()->GetSpillFill(0U);
1511 auto callReg = Location::MakeFpRegister(INS(3U).GetDstReg());
1512
1513 EXPECT_EQ(spill.GetSrc(), callReg);
1514 EXPECT_EQ(spill.GetDst(), fill.GetSrc());
1515 EXPECT_EQ(callReg, fill.GetDst());
1516 }
1517
CheckInstsDstRegs(Inst * inst0,const Inst * inst1,Register reg)1518 static bool CheckInstsDstRegs(Inst *inst0, const Inst *inst1, Register reg)
1519 {
1520 EXPECT_EQ(inst0->GetDstReg(), reg);
1521 EXPECT_EQ(inst1->GetDstReg(), reg);
1522
1523 // Should be spill-fill before second instruction to spill the first one;
1524 for (auto inst : InstIter(*inst0->GetBasicBlock(), inst0)) {
1525 if (inst == inst1) {
1526 break;
1527 }
1528 if (inst->IsSpillFill()) {
1529 auto sfs = inst->CastToSpillFill()->GetSpillFills();
1530 auto it = std::find_if(sfs.cbegin(), sfs.cend(), [reg](auto sf) {
1531 return sf.SrcValue() == reg && sf.SrcType() == LocationType::REGISTER;
1532 });
1533 if (it != sfs.cend()) {
1534 return true;
1535 }
1536 }
1537 }
1538 return false;
1539 }
1540
TEST_F(RegAllocLinearScanTest,PreassignedRegisters)1541 TEST_F(RegAllocLinearScanTest, PreassignedRegisters)
1542 {
1543 // Check with different masks:
1544 RegMask fullMask {0x0U}; // All registers are available for RA
1545 RegMask shortMask {0xFFFFFFAAU}; // only {R0, R2, R4, R6} are available for RA
1546 RegMask shortMaskInvert {0x55U}; // {R0, R2, R4, R6} are NOT available for RA
1547
1548 for (auto &mask : {fullMask, shortMask, shortMaskInvert}) {
1549 auto graph = CreateEmptyGraph();
1550 GRAPH(graph)
1551 {
1552 BASIC_BLOCK(2U, -1L)
1553 {
1554 INST(10U, Opcode::SaveState).Inputs().SrcVregs({});
1555 INST(0U, Opcode::CallStatic).InputsAutoType(10U).u32().DstReg(0U);
1556 INST(1U, Opcode::CallStatic).InputsAutoType(10U).u32().DstReg(1U);
1557 INST(2U, Opcode::CallStatic).InputsAutoType(10U).u32().DstReg(2U);
1558 INST(3U, Opcode::Add).Inputs(0U, 1U).u32().DstReg(0U);
1559 INST(4U, Opcode::Add).Inputs(1U, 2U).u32().DstReg(1U);
1560 INST(5U, Opcode::Add).Inputs(0U, 2U).u32().DstReg(2U);
1561 INST(6U, Opcode::Add).Inputs(4U, 5U).u32();
1562 INST(7U, Opcode::SaveState).Inputs().SrcVregs({});
1563 INST(8U, Opcode::CallStatic).InputsAutoType(0U, 1U, 2U, 3U, 4U, 5U, 6U, 7U).u32();
1564 INST(9U, Opcode::Return).Inputs(8U).u32();
1565 }
1566 }
1567 auto regalloc = RegAllocLinearScan(graph);
1568 regalloc.SetRegMask(mask);
1569 ASSERT_TRUE(regalloc.Run());
1570 ASSERT_TRUE(CheckInstsDstRegs(&INS(0U), &INS(3U), Register(0U)));
1571 ASSERT_TRUE(CheckInstsDstRegs(&INS(1U), &INS(4U), Register(1U)));
1572 ASSERT_TRUE(CheckInstsDstRegs(&INS(2U), &INS(5U), Register(2U)));
1573 }
1574 }
1575
TEST_F(RegAllocLinearScanTest,Select3Regs)1576 TEST_F(RegAllocLinearScanTest, Select3Regs)
1577 {
1578 GRAPH(GetGraph())
1579 {
1580 PARAMETER(0U, 0U).s64();
1581 PARAMETER(1U, 1U).s64();
1582 PARAMETER(2U, 2U).s64();
1583
1584 BASIC_BLOCK(2U, -1L)
1585 {
1586 INST(3U, Opcode::Add).s64().Inputs(0U, 1U);
1587 INST(4U, Opcode::Select).s64().SrcType(DataType::Type::INT64).CC(CC_LT).Inputs(0U, 1U, 2U, 3U);
1588 INST(5U, Opcode::Return).s64().Inputs(4U);
1589 }
1590 }
1591
1592 auto regalloc = RegAllocLinearScan(GetGraph());
1593 auto regMask = GetGraph()->GetArch() == Arch::AARCH32 ? 0xFFFFFFABU : 0xFFFFFFF1U;
1594 regalloc.SetRegMask(RegMask {regMask});
1595 auto result = regalloc.Run();
1596 ASSERT_FALSE(result);
1597 }
1598
TEST_F(RegAllocLinearScanTest,TwoInstsWithZeroReg)1599 TEST_F(RegAllocLinearScanTest, TwoInstsWithZeroReg)
1600 {
1601 auto zeroReg = GetGraph()->GetZeroReg();
1602 if (zeroReg == INVALID_REG) {
1603 return;
1604 }
1605
1606 GRAPH(GetGraph())
1607 {
1608 CONSTANT(0U, 0U).s64();
1609 CONSTANT(1U, nullptr).ref();
1610
1611 BASIC_BLOCK(2U, -1L)
1612 {
1613 INST(2U, Opcode::SaveState).Inputs().SrcVregs({});
1614 INST(3U, Opcode::CallStatic).InputsAutoType(1U, 2U).s64();
1615 INST(4U, Opcode::Add).s64().Inputs(0U, 3U);
1616 INST(5U, Opcode::Return).ref().Inputs(1U);
1617 }
1618 }
1619
1620 auto regalloc = RegAllocLinearScan(GetGraph());
1621 regalloc.Run();
1622 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
1623 auto const0 = la.GetInstLifeIntervals(&INS(0U));
1624 auto nullptrInst = la.GetInstLifeIntervals(&INS(1U));
1625 // Constant and Nullptr should not be split
1626 EXPECT_EQ(const0->GetSibling(), nullptr);
1627 EXPECT_EQ(nullptrInst->GetSibling(), nullptr);
1628 // Intervals' regs and dst's regs should be 'zero_reg'
1629 EXPECT_EQ(const0->GetReg(), zeroReg);
1630 EXPECT_EQ(nullptrInst->GetReg(), zeroReg);
1631 EXPECT_EQ(INS(0U).GetDstReg(), zeroReg);
1632 EXPECT_EQ(INS(1U).GetDstReg(), zeroReg);
1633 // Src's reg should be 'zero_reg'
1634 EXPECT_EQ(INS(4U).GetSrcReg(0U), zeroReg);
1635 if (INS(5U).GetPrev()->IsSpillFill()) {
1636 auto sf = INS(5U).GetPrev()->CastToSpillFill();
1637 EXPECT_EQ(sf->GetSpillFill(0U).SrcValue(), zeroReg);
1638 EXPECT_EQ(sf->GetSpillFill(0U).DstValue(), INS(5U).GetSrcReg(0U));
1639 } else {
1640 EXPECT_EQ(INS(5U).GetSrcReg(0U), zeroReg);
1641 }
1642 }
1643
1644 template <unsigned int CONSTANTS_NUM>
FillGraphWithConstants(Graph * graph)1645 bool RegAllocLinearScanTest::FillGraphWithConstants(Graph *graph)
1646 {
1647 GRAPH(graph)
1648 {
1649 for (size_t i = 0; i < CONSTANTS_NUM; ++i) {
1650 CONSTANT(i, i);
1651 }
1652
1653 BASIC_BLOCK(2U, -1L)
1654 {
1655 INST(CONSTANTS_NUM, Opcode::Add).s64().Inputs(CONSTANTS_NUM - 1L, CONSTANTS_NUM - 2L);
1656 for (int i = CONSTANTS_NUM - 3L, j = 1; i >= 0; --i, ++j) {
1657 INST(CONSTANTS_NUM + j, Opcode::Add).s64().Inputs(i, j - 1L);
1658 }
1659 INST(2U * CONSTANTS_NUM + 2U, Opcode::Return).s64().Inputs(2U * CONSTANTS_NUM - 2L);
1660 }
1661 }
1662
1663 auto regalloc = RegAllocLinearScan(graph);
1664 return regalloc.Run();
1665 }
1666
1667 // Ensure that we can spill at least 255 constants to graph only:
TEST_F(RegAllocLinearScanTest,SpillConstantsGraph)1668 TEST_F(RegAllocLinearScanTest, SpillConstantsGraph)
1669 {
1670 ASSERT_TRUE(compiler::g_options.IsCompilerRematConst());
1671 ASSERT_TRUE(FillGraphWithConstants<255U>(GetGraph()));
1672
1673 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
1674 for (auto interval : la.GetLifeIntervals()) {
1675 auto sibling = interval;
1676 while (sibling != nullptr) {
1677 if (!sibling->IsPhysical() && sibling->GetInst()->IsConst()) {
1678 auto loc = sibling->GetLocation();
1679 EXPECT_TRUE(loc.IsConstant() || loc.IsRegister()) << *sibling->GetInst();
1680 }
1681 sibling = sibling->GetSibling();
1682 }
1683 }
1684 }
1685
1686 // Ensure that we can spill at least 2*255 constants to stack/graph:
TEST_F(RegAllocLinearScanTest,SpillConstantsGraphStack)1687 TEST_F(RegAllocLinearScanTest, SpillConstantsGraphStack)
1688 {
1689 ASSERT_TRUE(compiler::g_options.IsCompilerRematConst());
1690 ASSERT_TRUE(FillGraphWithConstants<510U>(GetGraph()));
1691
1692 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
1693 for (auto interval : la.GetLifeIntervals()) {
1694 auto sibling = interval;
1695 while (sibling != nullptr) {
1696 if (!sibling->IsPhysical() && sibling->GetInst()->IsConst()) {
1697 auto loc = sibling->GetLocation();
1698 EXPECT_TRUE(loc.IsConstant() || loc.IsRegister() || loc.IsStack()) << *sibling->GetInst();
1699 }
1700 sibling = sibling->GetSibling();
1701 }
1702 }
1703 }
1704
1705 // There are no available imm slots nor stack slots:
TEST_F(RegAllocLinearScanTest,SpillConstantsLimit)1706 TEST_F(RegAllocLinearScanTest, SpillConstantsLimit)
1707 {
1708 ASSERT_TRUE(compiler::g_options.IsCompilerRematConst());
1709 ASSERT_FALSE(FillGraphWithConstants<513U>(GetGraph()));
1710 }
1711
TEST_F(RegAllocLinearScanTest,ParameterWithUnavailableRegister)1712 TEST_F(RegAllocLinearScanTest, ParameterWithUnavailableRegister)
1713 {
1714 if (GetGraph()->GetArch() != Arch::AARCH32) {
1715 GTEST_SKIP() << "Unsupported target architecture";
1716 }
1717 GRAPH(GetGraph())
1718 {
1719 PARAMETER(0U, 0U).u32();
1720 PARAMETER(1U, 1U).u32();
1721 PARAMETER(2U, 2U).u32();
1722
1723 BASIC_BLOCK(2U, -1L)
1724 {
1725 INST(3U, Opcode::Add).u32().Inputs(0U, 1U);
1726 INST(4U, Opcode::Add).u32().Inputs(3U, 2U);
1727 INST(5U, Opcode::Return).u32().Inputs(4U);
1728 }
1729 }
1730
1731 RegAllocLinearScan ra(GetGraph());
1732 // r1 is blocked (but param 0 resides there)
1733 uint32_t regMask = 0xFFFFFFF3U;
1734 ra.SetRegMask(RegMask {regMask});
1735 ra.SetVRegMask(VRegMask {0U});
1736 // we can't assign a register to first parameter, so allocation will fail
1737 ASSERT_FALSE(ra.Run());
1738 }
1739 // NOLINTEND(readability-magic-numbers)
1740
1741 } // namespace ark::compiler
1742