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 "compiler/optimizer/optimizations/regalloc/split_resolver.h"
18 #include "compiler/optimizer/optimizations/regalloc/spill_fills_resolver.h"
19 #include "compiler/optimizer/optimizations/regalloc/reg_alloc_linear_scan.h"
20 #include "compiler/optimizer/analysis/liveness_analyzer.h"
21
22 #define INITIALIZE_GRAPHS(G_BEFORE, G_AFTER) \
23 for (auto __after_resolve : {true, false}) \
24 if (auto ___g = (__after_resolve ? G_AFTER : G_BEFORE)) \
25 GRAPH(___g)
26
27 #define AFTER_SPLIT_RESOLUTION(OP) \
28 if (__after_resolve) \
29 OP
30
31 namespace panda::compiler {
32 class SplitResolverTest : public GraphTest {
33 public:
RunLivenessAnalysis(Graph * graph)34 LivenessAnalyzer *RunLivenessAnalysis(Graph *graph)
35 {
36 graph->RunPass<LivenessAnalyzer>();
37 return &graph->GetAnalysis<LivenessAnalyzer>();
38 }
39
SplitAssignReg(LifeIntervals * source,LifeNumber position,Register reg)40 LifeIntervals *SplitAssignReg(LifeIntervals *source, LifeNumber position, Register reg)
41 {
42 auto split = source->SplitAt(position - 1, GetAllocator());
43 split->SetReg(reg);
44 return split;
45 }
46
SplitAssignSlot(LifeIntervals * source,LifeNumber position,StackSlot slot)47 LifeIntervals *SplitAssignSlot(LifeIntervals *source, LifeNumber position, StackSlot slot)
48 {
49 auto split = source->SplitAt(position - 1, GetAllocator());
50 split->SetLocation(Location::MakeStackSlot(slot));
51 return split;
52 }
53
SplitAssignImmSlot(LifeIntervals * source,LifeNumber position,ImmTableSlot slot)54 LifeIntervals *SplitAssignImmSlot(LifeIntervals *source, LifeNumber position, ImmTableSlot slot)
55 {
56 ASSERT(source->GetInst()->IsConst());
57 auto split = source->SplitAt(position - 1, GetAllocator());
58 split->SetLocation(Location::MakeConstant(slot));
59 return split;
60 }
61
CheckSpillFills(Inst * inst,std::initializer_list<std::tuple<LocationType,LocationType,Register,Register>> data)62 void CheckSpillFills(Inst *inst,
63 std::initializer_list<std::tuple<LocationType, LocationType, Register, Register>> data)
64 {
65 ASSERT_EQ(inst->GetOpcode(), Opcode::SpillFill);
66 auto sf = inst->CastToSpillFill();
67
68 for (auto &[src_loc, dst_loc, src, dst] : data) {
69 bool found = false;
70 for (auto &sf_data : sf->GetSpillFills()) {
71 found |= sf_data.SrcType() == src_loc && sf_data.DstType() == dst_loc && sf_data.SrcValue() == src &&
72 sf_data.DstValue() == dst;
73 }
74 EXPECT_TRUE(found) << "SpillFillData {move, src=" << static_cast<int>(src)
75 << ", dest=" << static_cast<int>(dst) << "} was not found in inst " << inst->GetId();
76 }
77 }
78
InitUsedRegs(Graph * graph)79 Graph *InitUsedRegs(Graph *graph)
80 {
81 ArenaVector<bool> regs =
82 ArenaVector<bool>(std::max(MAX_NUM_REGS, MAX_NUM_VREGS), false, GetAllocator()->Adapter());
83 graph->InitUsedRegs<DataType::INT64>(®s);
84 graph->InitUsedRegs<DataType::FLOAT64>(®s);
85 return graph;
86 }
87 };
88
TEST_F(SplitResolverTest,ProcessIntervalsWithoutSplit)89 TEST_F(SplitResolverTest, ProcessIntervalsWithoutSplit)
90 {
91 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
92 auto expected_graph = CreateEmptyGraph();
93 INITIALIZE_GRAPHS(initial_graph, expected_graph)
94 {
95 PARAMETER(0, 0).u64();
96
97 BASIC_BLOCK(2, -1)
98 {
99 INST(1, Opcode::Add).u64().Inputs(0, 0);
100 INST(2, Opcode::Return).u64().Inputs(1);
101 }
102 }
103
104 SplitResolver resolver(initial_graph, RunLivenessAnalysis(initial_graph));
105 resolver.Run();
106
107 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
108 }
109
TEST_F(SplitResolverTest,ConnectSiblingsWithSameBlock)110 TEST_F(SplitResolverTest, ConnectSiblingsWithSameBlock)
111 {
112 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
113 auto expected_graph = CreateEmptyGraph();
114 INITIALIZE_GRAPHS(initial_graph, expected_graph)
115 {
116 PARAMETER(0, 0).u64();
117
118 BASIC_BLOCK(2, -1)
119 {
120 AFTER_SPLIT_RESOLUTION(INST(4, Opcode::SpillFill));
121 INST(1, Opcode::Add).u64().Inputs(0, 0);
122 AFTER_SPLIT_RESOLUTION(INST(5, Opcode::SpillFill));
123 INST(2, Opcode::Add).u64().Inputs(0, 1);
124 INST(3, Opcode::Return).u64().Inputs(2);
125 }
126 }
127
128 auto la = RunLivenessAnalysis(initial_graph);
129
130 auto param = la->GetInstLifeIntervals(&INS(0));
131 auto add = la->GetInstLifeIntervals(&INS(1));
132 param->SetReg(0);
133
134 SplitAssignReg(SplitAssignSlot(param, add->GetBegin(), 0), add->GetEnd(), 1);
135
136 SplitResolver resolver(initial_graph, la);
137 resolver.Run();
138
139 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
140 CheckSpillFills(INS(1).GetPrev(), {{LocationType::REGISTER, LocationType::STACK, 0, 0}});
141 CheckSpillFills(INS(1).GetNext(), {{LocationType::STACK, LocationType::REGISTER, 0, 1}});
142 }
143
TEST_F(SplitResolverTest,ConnectSiblingsInDifferentBlocks)144 TEST_F(SplitResolverTest, ConnectSiblingsInDifferentBlocks)
145 {
146 auto expected_graph = CreateEmptyGraph();
147 GRAPH(expected_graph)
148 {
149 PARAMETER(0, 0).u64();
150
151 BASIC_BLOCK(2, 3, 6)
152 {
153 INST(1, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 0);
154 INST(2, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(1);
155 }
156
157 BASIC_BLOCK(3, 5)
158 {
159 INST(3, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
160 INST(8, Opcode::SpillFill);
161 INST(4, Opcode::CallStatic).v0id().InputsAutoType(3);
162 }
163
164 BASIC_BLOCK(6, 4)
165 {
166 INST(9, Opcode::SpillFill);
167 }
168
169 BASIC_BLOCK(4, 5)
170 {
171 INST(5, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
172 INST(6, Opcode::CallStatic).v0id().InputsAutoType(5);
173 }
174
175 BASIC_BLOCK(5, -1)
176 {
177 INST(7, Opcode::Return).u64().Inputs(0);
178 }
179 }
180
181 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
182 GRAPH(initial_graph)
183 {
184 PARAMETER(0, 0).u64();
185
186 BASIC_BLOCK(2, 3, 4)
187 {
188 INST(1, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 0);
189 INST(2, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(1);
190 }
191
192 BASIC_BLOCK(3, 5)
193 {
194 INST(3, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
195 INST(4, Opcode::CallStatic).v0id().InputsAutoType(3);
196 }
197
198 BASIC_BLOCK(4, 5)
199 {
200 INST(5, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
201 INST(6, Opcode::CallStatic).v0id().InputsAutoType(5);
202 }
203
204 BASIC_BLOCK(5, -1)
205 {
206 INST(7, Opcode::Return).u64().Inputs(0);
207 }
208 }
209
210 auto la = RunLivenessAnalysis(initial_graph);
211
212 auto param = la->GetInstLifeIntervals(&INS(0));
213 auto call = la->GetInstLifeIntervals(&INS(4));
214 param->SetReg(0);
215
216 SplitAssignSlot(param, call->GetBegin(), 0);
217
218 SplitResolver resolver(initial_graph, la);
219 resolver.Run();
220
221 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
222 CheckSpillFills(INS(4).GetPrev(), {{LocationType::REGISTER, LocationType::STACK, 0, 0}});
223 CheckSpillFills(BB(4).GetPredsBlocks()[0]->GetLastInst(), {{LocationType::REGISTER, LocationType::STACK, 0, 0}});
224 }
225
TEST_F(SplitResolverTest,ConnectSiblingsHavingCriticalEdgeBetweenBlocks)226 TEST_F(SplitResolverTest, ConnectSiblingsHavingCriticalEdgeBetweenBlocks)
227 {
228 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
229 auto expected_graph = CreateEmptyGraph();
230 GRAPH(initial_graph)
231 {
232 PARAMETER(0, 0).u64();
233
234 BASIC_BLOCK(2, 3, 4)
235 {
236 INST(1, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 0);
237 INST(2, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(1);
238 }
239
240 BASIC_BLOCK(3, 4)
241 {
242 INST(3, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
243 INST(4, Opcode::CallStatic).v0id().InputsAutoType(3);
244 }
245
246 BASIC_BLOCK(4, -1)
247 {
248 INST(5, Opcode::Return).u64().Inputs(0);
249 }
250 }
251
252 auto la = RunLivenessAnalysis(initial_graph);
253
254 auto param = la->GetInstLifeIntervals(&INS(0));
255 auto call = la->GetInstLifeIntervals(&INS(4));
256 param->SetReg(0);
257
258 SplitAssignSlot(param, call->GetBegin(), 0);
259
260 SplitResolver resolver(initial_graph, la);
261 resolver.Run();
262
263 GRAPH(expected_graph)
264 {
265 PARAMETER(0, 0).u64();
266
267 BASIC_BLOCK(2, 3, 5)
268 {
269 INST(1, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 0);
270 INST(2, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(1);
271 }
272
273 BASIC_BLOCK(3, 4)
274 {
275 INST(3, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
276 INST(6, Opcode::SpillFill);
277 INST(4, Opcode::CallStatic).v0id().InputsAutoType(3);
278 }
279
280 BASIC_BLOCK(5, 4)
281 {
282 INST(7, Opcode::SpillFill);
283 }
284
285 BASIC_BLOCK(4, -1)
286 {
287 INST(5, Opcode::Return).u64().Inputs(0);
288 }
289 }
290
291 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
292 size_t spill_fills = 0;
293 for (auto block : initial_graph->GetVectorBlocks()) {
294 if (block == nullptr) {
295 continue;
296 }
297 for (auto inst : block->AllInsts()) {
298 if (inst->GetOpcode() == Opcode::SpillFill) {
299 CheckSpillFills(inst, {{LocationType::REGISTER, LocationType::STACK, 0, 0}});
300 spill_fills++;
301 }
302 }
303 }
304 EXPECT_EQ(spill_fills, 2);
305 }
306
TEST_F(SplitResolverTest,SplitAtTheEndOfBlock)307 TEST_F(SplitResolverTest, SplitAtTheEndOfBlock)
308 {
309 auto expected_graph = CreateEmptyGraph();
310 GRAPH(expected_graph)
311 {
312 PARAMETER(0, 0).u64();
313
314 BASIC_BLOCK(2, 3, 7)
315 {
316 INST(1, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 0);
317 INST(2, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(1);
318 }
319
320 BASIC_BLOCK(3, 5)
321 {
322 INST(3, Opcode::Add).u64().Inputs(0, 0);
323 INST(8, Opcode::SpillFill);
324 }
325
326 BASIC_BLOCK(7, 4)
327 {
328 INST(9, Opcode::SpillFill);
329 }
330
331 BASIC_BLOCK(4, 6)
332 {
333 INST(4, Opcode::Mul).u64().Inputs(0, 0);
334 }
335
336 BASIC_BLOCK(5, 6)
337 {
338 INST(7, Opcode::Add).u64().Inputs(3, 0);
339 }
340
341 BASIC_BLOCK(6, -1)
342 {
343 INST(5, Opcode::Phi).u64().Inputs(4, 7);
344 INST(6, Opcode::Return).u64().Inputs(5);
345 }
346 }
347
348 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
349 GRAPH(initial_graph)
350 {
351 PARAMETER(0, 0).u64();
352
353 BASIC_BLOCK(2, 3, 4)
354 {
355 INST(1, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 0);
356 INST(2, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(1);
357 }
358
359 BASIC_BLOCK(3, 5)
360 {
361 INST(3, Opcode::Add).u64().Inputs(0, 0);
362 }
363
364 BASIC_BLOCK(4, 6)
365 {
366 INST(4, Opcode::Mul).u64().Inputs(0, 0);
367 }
368
369 BASIC_BLOCK(5, 6)
370 {
371 INST(7, Opcode::Add).u64().Inputs(3, 0);
372 }
373
374 BASIC_BLOCK(6, -1)
375 {
376 INST(5, Opcode::Phi).u64().Inputs(4, 7);
377 INST(6, Opcode::Return).u64().Inputs(5);
378 }
379 }
380
381 auto la = RunLivenessAnalysis(initial_graph);
382 auto param = la->GetInstLifeIntervals(&INS(0));
383 auto bb3 = la->GetBlockLiveRange(&BB(3));
384 param->SetReg(0);
385 SplitAssignSlot(param, bb3.GetEnd(), 0);
386 // Assign reg to the phi and its inputs
387 la->GetInstLifeIntervals(&INS(4))->SetReg(1);
388 la->GetInstLifeIntervals(&INS(5))->SetReg(1);
389 la->GetInstLifeIntervals(&INS(7))->SetReg(1);
390
391 SplitResolver resolver(initial_graph, la);
392 resolver.Run();
393 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
394 CheckSpillFills(INS(3).GetNext(), {{LocationType::REGISTER, LocationType::STACK, 0, 0}});
395 CheckSpillFills(BB(4).GetPredsBlocks()[0]->GetLastInst(), {{LocationType::REGISTER, LocationType::STACK, 0, 0}});
396 }
397
398 // If we already inserted spill fill instruction for some spill
399 // the we can reuse it for another one.
TEST_F(SplitResolverTest,ReuseExistingSpillFillWithinBlock)400 TEST_F(SplitResolverTest, ReuseExistingSpillFillWithinBlock)
401 {
402 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
403 auto expected_graph = CreateEmptyGraph();
404
405 INITIALIZE_GRAPHS(initial_graph, expected_graph)
406 {
407 PARAMETER(0, 0).u64();
408 PARAMETER(1, 1).u64();
409
410 BASIC_BLOCK(2, -1)
411 {
412 INST(2, Opcode::SaveState).Inputs(0).SrcVregs({0});
413 AFTER_SPLIT_RESOLUTION(INST(6, Opcode::SpillFill));
414 INST(3, Opcode::CallStatic).v0id().InputsAutoType(2);
415 AFTER_SPLIT_RESOLUTION(INST(7, Opcode::SpillFill));
416 INST(4, Opcode::Add).u64().Inputs(0, 1);
417 INST(5, Opcode::Return).u64().Inputs(4);
418 }
419 }
420
421 auto la = RunLivenessAnalysis(initial_graph);
422
423 auto param0 = la->GetInstLifeIntervals(&INS(0));
424 auto param1 = la->GetInstLifeIntervals(&INS(1));
425 auto call = la->GetInstLifeIntervals(&INS(3));
426 param0->SetReg(0);
427 param1->SetReg(1);
428
429 SplitAssignReg(SplitAssignSlot(param0, call->GetBegin(), 0), call->GetEnd(), 0);
430 SplitAssignReg(SplitAssignSlot(param1, call->GetBegin(), 1), call->GetEnd(), 1);
431
432 SplitResolver resolver(initial_graph, la);
433 resolver.Run();
434
435 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
436 CheckSpillFills(INS(3).GetPrev(), {{LocationType::REGISTER, LocationType::STACK, 0, 0},
437 {LocationType::REGISTER, LocationType::STACK, 1, 1}});
438 CheckSpillFills(INS(3).GetNext(), {{LocationType::STACK, LocationType::REGISTER, 0, 0},
439 {LocationType::STACK, LocationType::REGISTER, 1, 1}});
440 }
441
442 // If there are spill fills inserted to load instn's operand or spill instn's result
443 // then we can't reuse these spill fills to connect splits.
TEST_F(SplitResolverTest,DontReuseInstructionSpillFills)444 TEST_F(SplitResolverTest, DontReuseInstructionSpillFills)
445 {
446 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
447 auto expected_graph = CreateEmptyGraph();
448
449 INITIALIZE_GRAPHS(initial_graph, expected_graph)
450 {
451 PARAMETER(0, 0).u64();
452 PARAMETER(1, 1).u64();
453 PARAMETER(2, 2).u64();
454
455 BASIC_BLOCK(2, -1)
456 {
457 AFTER_SPLIT_RESOLUTION(INST(11, Opcode::SpillFill));
458 INST(4, Opcode::SpillFill); // spill fill loading
459 INST(5, Opcode::AddI).u64().Imm(42).Inputs(2);
460 AFTER_SPLIT_RESOLUTION(INST(12, Opcode::SpillFill));
461 INST(7, Opcode::SpillFill); // spill fill loading
462 INST(8, Opcode::Add).u64().Inputs(0, 5);
463 INST(9, Opcode::Add).u64().Inputs(8, 1);
464 INST(10, Opcode::Return).u64().Inputs(9);
465 }
466 }
467
468 auto la = RunLivenessAnalysis(initial_graph);
469
470 auto param0 = la->GetInstLifeIntervals(&INS(0));
471 auto param1 = la->GetInstLifeIntervals(&INS(1));
472 auto param2 = la->GetInstLifeIntervals(&INS(2));
473 auto addi = la->GetInstLifeIntervals(&INS(5));
474 auto add = la->GetInstLifeIntervals(&INS(8));
475 param0->SetReg(0);
476 param1->SetReg(1);
477 param2->SetLocation(Location::MakeStackSlot(4));
478 addi->SetLocation(Location::MakeStackSlot(3));
479
480 INS(4).CastToSpillFill()->SetSpillFillType(SpillFillType::INPUT_FILL);
481 INS(7).CastToSpillFill()->SetSpillFillType(SpillFillType::INPUT_FILL);
482
483 SplitAssignReg(SplitAssignSlot(param0, addi->GetBegin(), 0), add->GetBegin(), 0);
484 SplitAssignReg(SplitAssignSlot(param1, addi->GetBegin(), 1), add->GetBegin(), 1);
485
486 INS(4).CastToSpillFill()->AddFill(param2->GetLocation().GetValue(), 11, DataType::Type::INT64);
487 INS(7).CastToSpillFill()->AddFill(addi->GetLocation().GetValue(), 11, DataType::Type::INT64);
488 INS(5).SetSrcReg(0, 11);
489 INS(5).SetDstReg(11);
490 INS(8).SetSrcReg(0, 0);
491 INS(8).SetSrcReg(1, 11);
492
493 SplitResolver resolver(initial_graph, la);
494 resolver.Run();
495
496 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
497 CheckSpillFills(INS(4).GetPrev(), {{LocationType::REGISTER, LocationType::STACK, 0, 0},
498 {LocationType::REGISTER, LocationType::STACK, 1, 1}});
499 CheckSpillFills(INS(7).GetPrev(), {{LocationType::STACK, LocationType::REGISTER, 0, 0},
500 {LocationType::STACK, LocationType::REGISTER, 1, 1}});
501 }
502
TEST_F(SplitResolverTest,DoNotReuseExistingSpillFillBeforeInstruction)503 TEST_F(SplitResolverTest, DoNotReuseExistingSpillFillBeforeInstruction)
504 {
505 auto initial_graph = CreateEmptyGraph();
506 auto expected_graph = CreateEmptyGraph();
507 INITIALIZE_GRAPHS(initial_graph, expected_graph)
508 {
509 PARAMETER(0, 0).u64();
510 PARAMETER(1, 1).u64();
511
512 BASIC_BLOCK(2, -1)
513 {
514 INST(2, Opcode::Add).u64().Inputs(0, 1);
515 AFTER_SPLIT_RESOLUTION(INST(6, Opcode::SpillFill));
516 INST(5, Opcode::SpillFill);
517 INST(3, Opcode::Mul).u64().Inputs(0, 2);
518 INST(4, Opcode::Return).u64().Inputs(3);
519 }
520 }
521
522 auto la = RunLivenessAnalysis(initial_graph);
523
524 auto param0 = la->GetInstLifeIntervals(&INS(0));
525 auto mul = la->GetInstLifeIntervals(&INS(3));
526 param0->SetReg(0);
527 SplitAssignSlot(param0, mul->GetBegin(), 0);
528
529 auto mul_sf = INS(5).CastToSpillFill();
530 mul_sf->AddFill(0, 1, DataType::Type::UINT64);
531 mul_sf->SetSpillFillType(SpillFillType::INPUT_FILL);
532
533 SplitResolver resolver(initial_graph, la);
534 resolver.Run();
535
536 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
537 CheckSpillFills(INS(2).GetNext(), {{LocationType::REGISTER, LocationType::STACK, 0, 0}});
538 CheckSpillFills(&INS(5), {{LocationType::STACK, LocationType::REGISTER, 0, 1}});
539 }
540
TEST_F(SplitResolverTest,ReuseExistingSpillFillAtTheEndOfBlock)541 TEST_F(SplitResolverTest, ReuseExistingSpillFillAtTheEndOfBlock)
542 {
543 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
544 auto expected_graph = CreateEmptyGraph();
545 INITIALIZE_GRAPHS(initial_graph, expected_graph)
546 {
547 PARAMETER(0, 0).u64();
548 PARAMETER(1, 1).u64();
549
550 BASIC_BLOCK(2, 3, 4)
551 {
552 INST(2, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 1);
553 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
554 }
555
556 BASIC_BLOCK(3, 5)
557 {
558 INST(4, Opcode::Add).u64().Inputs(0, 1);
559 INST(9, Opcode::SpillFill); // SF generated for PHI
560 }
561
562 BASIC_BLOCK(4, 5)
563 {
564 AFTER_SPLIT_RESOLUTION(INST(11, Opcode::SpillFill));
565 INST(5, Opcode::Mul).u64().Inputs(1, 1);
566 }
567
568 BASIC_BLOCK(5, -1)
569 {
570 INST(6, Opcode::Phi).u64().Inputs(4, 5);
571 INST(7, Opcode::Add).u64().Inputs(6, 0);
572 INST(8, Opcode::Return).u64().Inputs(7);
573 }
574 }
575
576 auto la = RunLivenessAnalysis(initial_graph);
577
578 auto phi = la->GetInstLifeIntervals(&INS(6));
579 phi->SetReg(3);
580 auto mul = la->GetInstLifeIntervals(&INS(5));
581 mul->SetReg(3);
582 auto add = la->GetInstLifeIntervals(&INS(4));
583 add->SetReg(2);
584
585 auto param0 = la->GetInstLifeIntervals(&INS(0));
586 param0->SetReg(1);
587
588 SplitAssignSlot(param0, mul->GetBegin(), 0);
589
590 auto phi_sf = INS(9).CastToSpillFill();
591 // param0 still has r1 assigned at the end of BB3, so PHI's SF will move it from r1 to r3 assigned to PHI
592 phi_sf->AddMove(1, 3, DataType::Type::UINT64);
593 phi_sf->SetSpillFillType(SpillFillType::SPLIT_MOVE);
594
595 SplitResolver resolver(initial_graph, la);
596 resolver.Run();
597
598 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
599 CheckSpillFills(&INS(9), {{LocationType::REGISTER, LocationType::STACK, 1, 0}});
600 CheckSpillFills(INS(5).GetPrev(), {{LocationType::REGISTER, LocationType::STACK, 1, 0}});
601 }
602
TEST_F(SplitResolverTest,ConnectSplitAtTheEndOfBlock)603 TEST_F(SplitResolverTest, ConnectSplitAtTheEndOfBlock)
604 {
605 auto expected_graph = CreateEmptyGraph();
606 GRAPH(expected_graph)
607 {
608 PARAMETER(0, 0).u64();
609 PARAMETER(1, 1).u64();
610
611 BASIC_BLOCK(2, 3, 6)
612 {
613 INST(2, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 1);
614 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
615 }
616
617 BASIC_BLOCK(3, 5)
618 {
619 INST(4, Opcode::Add).u64().Inputs(0, 1);
620 // Insert copy instruction before φ-move, because
621 // inst 4 should be already copied at the end of block (where φ inserts move).
622 INST(10, Opcode::SpillFill);
623 INST(9, Opcode::SpillFill); // SF generated for PHI
624 }
625
626 BASIC_BLOCK(6, 4)
627 {
628 INST(11, Opcode::SpillFill);
629 }
630
631 BASIC_BLOCK(4, 5)
632 {
633 INST(5, Opcode::Mul).u64().Inputs(1, 1);
634 }
635
636 BASIC_BLOCK(5, -1)
637 {
638 INST(6, Opcode::Phi).u64().Inputs(4, 5);
639 INST(7, Opcode::Add).u64().Inputs(6, 0);
640 INST(8, Opcode::Return).u64().Inputs(7);
641 }
642 }
643
644 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
645 GRAPH(initial_graph)
646 {
647 PARAMETER(0, 0).u64();
648 PARAMETER(1, 1).u64();
649
650 BASIC_BLOCK(2, 3, 4)
651 {
652 INST(2, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 1);
653 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
654 }
655
656 BASIC_BLOCK(3, 5)
657 {
658 INST(4, Opcode::Add).u64().Inputs(0, 1);
659 INST(9, Opcode::SpillFill); // SF generated for PHI
660 }
661
662 BASIC_BLOCK(4, 5)
663 {
664 INST(5, Opcode::Mul).u64().Inputs(1, 1);
665 }
666
667 BASIC_BLOCK(5, -1)
668 {
669 INST(6, Opcode::Phi).u64().Inputs(4, 5);
670 INST(7, Opcode::Add).u64().Inputs(6, 0);
671 INST(8, Opcode::Return).u64().Inputs(7);
672 }
673 }
674
675 auto la = RunLivenessAnalysis(initial_graph);
676
677 auto phi = la->GetInstLifeIntervals(&INS(6));
678 phi->SetReg(3);
679 auto add = la->GetInstLifeIntervals(&INS(4));
680 add->SetReg(1);
681 auto mul = la->GetInstLifeIntervals(&INS(5));
682 mul->SetReg(3);
683
684 auto param0 = la->GetInstLifeIntervals(&INS(0));
685 param0->SetReg(1);
686
687 SplitAssignSlot(param0, add->GetBegin() + 2, 0);
688
689 auto phi_sf = INS(9).CastToSpillFill();
690 // param0 still has r1 assigned at the end of BB3, so PHI's SF will move it from r1 to r3 assigned to PHI
691 phi_sf->AddMove(1, 3, DataType::Type::UINT64);
692 phi_sf->SetSpillFillType(SpillFillType::SPLIT_MOVE);
693
694 SplitResolver resolver(initial_graph, la);
695 resolver.Run();
696
697 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
698 CheckSpillFills(INS(4).GetNext(), {{LocationType::REGISTER, LocationType::STACK, 1, 0}});
699 }
700
TEST_F(SplitResolverTest,GracefullyHandlePhiResolverBlocks)701 TEST_F(SplitResolverTest, GracefullyHandlePhiResolverBlocks)
702 {
703 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
704 GRAPH(initial_graph)
705 {
706 PARAMETER(0, 0).u64();
707 PARAMETER(1, 1).u64();
708
709 BASIC_BLOCK(2, 5, 3)
710 {
711 INST(2, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 1);
712 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
713 }
714
715 BASIC_BLOCK(3, 5, 4)
716 {
717 INST(4, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 1);
718 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_LE).Imm(0).Inputs(4);
719 }
720
721 BASIC_BLOCK(5, 6)
722 {
723 INST(6, Opcode::Add).u64().Inputs(0, 1);
724 }
725
726 BASIC_BLOCK(4, 6)
727 {
728 INST(7, Opcode::Sub).u64().Inputs(0, 1);
729 }
730
731 BASIC_BLOCK(6, -1)
732 {
733 INST(8, Opcode::Phi).u64().Inputs(6, 7);
734 INST(9, Opcode::Add).u64().Inputs(0, 8);
735 INST(10, Opcode::Return).u64().Inputs(9);
736 }
737 }
738
739 auto la = RunLivenessAnalysis(initial_graph);
740 auto pred = &BB(5);
741 auto succ = &BB(6);
742 auto phi_resolver = pred->InsertNewBlockToSuccEdge(succ);
743 auto sf0 = initial_graph->CreateInstSpillFill();
744 sf0->SetSpillFillType(SpillFillType::SPLIT_MOVE);
745 phi_resolver->PrependInst(sf0);
746
747 auto param0 = la->GetInstLifeIntervals(&INS(0));
748 param0->SetReg(0);
749 auto sub = la->GetInstLifeIntervals(&INS(7));
750 SplitAssignReg(param0, sub->GetBegin(), 4);
751
752 // Assign reg to the phi and its inputs
753 la->GetInstLifeIntervals(&INS(6))->SetReg(1);
754 la->GetInstLifeIntervals(&INS(7))->SetReg(1);
755 la->GetInstLifeIntervals(&INS(8))->SetReg(1);
756
757 SplitResolver resolver(initial_graph, la);
758 resolver.Run();
759
760 auto expected_graph = CreateEmptyGraph();
761 GRAPH(expected_graph)
762 {
763 PARAMETER(0, 0).u64();
764 PARAMETER(1, 1).u64();
765
766 BASIC_BLOCK(2, 5, 3)
767 {
768 INST(2, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 1);
769 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
770 }
771
772 BASIC_BLOCK(3, 5, 4)
773 {
774 INST(4, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 1);
775 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_LE).Imm(0).Inputs(4);
776 }
777
778 BASIC_BLOCK(5, 7)
779 {
780 INST(6, Opcode::Add).u64().Inputs(0, 1);
781 }
782
783 BASIC_BLOCK(7, 6)
784 {
785 // Single spill fill handling both split connection and φ-move
786 INST(12, Opcode::SpillFill);
787 }
788
789 BASIC_BLOCK(4, 6)
790 {
791 INST(11, Opcode::SpillFill); // resolve split
792 INST(7, Opcode::Sub).u64().Inputs(0, 1);
793 }
794
795 BASIC_BLOCK(6, -1)
796 {
797 INST(8, Opcode::Phi).u64().Inputs(6, 7);
798 INST(9, Opcode::Add).u64().Inputs(0, 8);
799 INST(10, Opcode::Return).u64().Inputs(9);
800 }
801 }
802
803 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
804 CheckSpillFills(sf0, {{LocationType::REGISTER, LocationType::REGISTER, 0, 4}});
805 CheckSpillFills(sub->GetInst()->GetPrev(), {{LocationType::REGISTER, LocationType::REGISTER, 0, 4}});
806 }
807
TEST_F(SplitResolverTest,ResolveSplitWithinLoop)808 TEST_F(SplitResolverTest, ResolveSplitWithinLoop)
809 {
810 auto expected_graph = CreateEmptyGraph();
811 GRAPH(expected_graph)
812 {
813 PARAMETER(0, 0).u64();
814 PARAMETER(1, 1).u64();
815
816 BASIC_BLOCK(2, 3)
817 {
818 INST(4, Opcode::Add).u64().Inputs(0, 1);
819 INST(5, Opcode::Add).u64().Inputs(1, 4);
820 INST(12, Opcode::SpillFill);
821 INST(6, Opcode::Add).u64().Inputs(4, 5);
822 }
823
824 BASIC_BLOCK(3, 6, 5)
825 {
826 INST(7, Opcode::Mul).u64().Inputs(4, 5);
827 INST(13, Opcode::SpillFill);
828 INST(8, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(6, 7);
829 INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
830 }
831
832 BASIC_BLOCK(5, -1)
833 {
834 INST(11, Opcode::Return).u64().Inputs(7);
835 }
836
837 BASIC_BLOCK(6, 3)
838 {
839 INST(14, Opcode::SpillFill);
840 }
841 }
842
843 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
844 GRAPH(initial_graph)
845 {
846 PARAMETER(0, 0).u64();
847 PARAMETER(1, 1).u64();
848
849 BASIC_BLOCK(2, 3)
850 {
851 INST(4, Opcode::Add).u64().Inputs(0, 1);
852 INST(5, Opcode::Add).u64().Inputs(1, 4);
853 INST(6, Opcode::Add).u64().Inputs(4, 5);
854 }
855
856 BASIC_BLOCK(3, 3, 5)
857 {
858 INST(7, Opcode::Mul).u64().Inputs(4, 5);
859 INST(8, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(6, 7);
860 INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
861 }
862
863 BASIC_BLOCK(5, -1)
864 {
865 INST(11, Opcode::Return).u64().Inputs(7);
866 }
867 }
868
869 auto la = RunLivenessAnalysis(initial_graph);
870 auto var0 = la->GetInstLifeIntervals(&INS(4));
871 var0->SetLocation(Location::MakeStackSlot(0));
872 SplitAssignSlot(SplitAssignReg(var0, la->GetInstLifeIntervals(&INS(6))->GetBegin(), 4),
873 la->GetInstLifeIntervals(&INS(8))->GetBegin(), 0);
874 auto var1 = la->GetInstLifeIntervals(&INS(5));
875 var1->SetLocation(Location::MakeStackSlot(1));
876 SplitAssignSlot(SplitAssignReg(var1, la->GetInstLifeIntervals(&INS(6))->GetBegin(), 5),
877 la->GetInstLifeIntervals(&INS(8))->GetBegin(), 1);
878
879 SplitResolver resolver(initial_graph, la);
880 resolver.Run();
881
882 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
883 CheckSpillFills(INS(6).GetPrev(), {{LocationType::STACK, LocationType::REGISTER, 0, 4},
884 {LocationType::STACK, LocationType::REGISTER, 1, 5}});
885 CheckSpillFills(INS(8).GetPrev(), {{LocationType::REGISTER, LocationType::STACK, 4, 0},
886 {LocationType::REGISTER, LocationType::STACK, 5, 1}});
887 auto resolver_block = initial_graph->GetVectorBlocks().back();
888 CheckSpillFills(resolver_block->GetLastInst(), {{LocationType::STACK, LocationType::REGISTER, 0, 4},
889 {LocationType::STACK, LocationType::REGISTER, 1, 5}});
890 }
891
TEST_F(SplitResolverTest,SkipIntervalsCoveringOnlyBlockStart)892 TEST_F(SplitResolverTest, SkipIntervalsCoveringOnlyBlockStart)
893 {
894 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
895 auto expected_graph = CreateEmptyGraph();
896 INITIALIZE_GRAPHS(initial_graph, expected_graph)
897 {
898 PARAMETER(0, 0).u64();
899 PARAMETER(1, 1).u64();
900 CONSTANT(2, 2);
901
902 BASIC_BLOCK(2, 3, 4)
903 {
904 INST(3, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 0);
905 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
906 }
907
908 BASIC_BLOCK(3, 5, 4)
909 {
910 INST(5, Opcode::Phi).u64().Inputs(1, 8);
911 INST(6, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(5, 5);
912 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
913 }
914
915 BASIC_BLOCK(5, 3)
916 {
917 // split (r1)
918 AFTER_SPLIT_RESOLUTION(INST(11, Opcode::SpillFill));
919 INST(8, Opcode::Sub).u64().Inputs(5, 0);
920 // copy to location @ begging BB 3 (r0)
921 AFTER_SPLIT_RESOLUTION(INST(12, Opcode::SpillFill));
922 }
923
924 // Interval for parameter 0 is live in loop's header (BB 3), so its live range
925 // will be prolonged until the end of loop (i.e. until the end of BB 5). As a result
926 // parameter 0 will be covering start of the BB 4 and the location of its life interval
927 // at the beginning of BB 4 will differ from location at the end of BB 2 (reg1 vs reg0).
928 // However, we should not insert spill fill in this case.
929 // param0 is not actually alive at BB 4 and the same register may be assigned to a phi (inst 9),
930 // so the move will corrupt Phi's value. If param0 is the Phi's input then it'll be copied
931 // by the phi-move inserted during Phi resolution and the spill-fill connecting sibling intervals
932 // is not required too.
933 BASIC_BLOCK(4, -1)
934 {
935 INST(9, Opcode::Phi).u64().Inputs(2, 5);
936 INST(10, Opcode::Return).u64().Inputs(9);
937 }
938 }
939
940 auto la = RunLivenessAnalysis(initial_graph);
941
942 auto param0 = la->GetInstLifeIntervals(&INS(0));
943 param0->SetReg(0);
944 SplitAssignReg(param0, la->GetInstLifeIntervals(&INS(8))->GetBegin(), 1);
945
946 // Assign reg to the phi and its inputs
947 la->GetInstLifeIntervals(&INS(1))->SetReg(1);
948 la->GetInstLifeIntervals(&INS(2))->SetReg(1);
949 la->GetInstLifeIntervals(&INS(5))->SetReg(1);
950 la->GetInstLifeIntervals(&INS(8))->SetReg(1);
951 la->GetInstLifeIntervals(&INS(9))->SetReg(1);
952
953 SplitResolver resolver(initial_graph, la);
954 resolver.Run();
955
956 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
957 }
958
TEST_F(SplitResolverTest,ConnectIntervalsForConstantWithinBlock)959 TEST_F(SplitResolverTest, ConnectIntervalsForConstantWithinBlock)
960 {
961 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
962 auto expected_graph = CreateEmptyGraph();
963
964 INITIALIZE_GRAPHS(initial_graph, expected_graph)
965 {
966 CONSTANT(0, 42);
967
968 BASIC_BLOCK(2, -1)
969 {
970 INST(1, Opcode::AddI).u64().Imm(1).Inputs(0);
971 INST(2, Opcode::Add).u64().Inputs(0, 1);
972 AFTER_SPLIT_RESOLUTION(INST(6, Opcode::SpillFill));
973 INST(3, Opcode::Add).u64().Inputs(0, 2);
974 INST(4, Opcode::Add).u64().Inputs(0, 3);
975 INST(5, Opcode::Return).u64().Inputs(4);
976 }
977 }
978
979 auto la = RunLivenessAnalysis(initial_graph);
980 auto con = la->GetInstLifeIntervals(&INS(0));
981 con->SetReg(0);
982 SplitAssignReg(SplitAssignImmSlot(SplitAssignImmSlot(con, la->GetInstLifeIntervals(&INS(1))->GetBegin(), 0),
983 la->GetInstLifeIntervals(&INS(2))->GetBegin(), 0),
984 la->GetInstLifeIntervals(&INS(3))->GetBegin(), 0);
985
986 SplitResolver resolver(initial_graph, la);
987 resolver.Run();
988
989 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
990 CheckSpillFills(INS(3).GetPrev(), {{LocationType::IMMEDIATE, LocationType::REGISTER, 0, 0}});
991 }
992
TEST_F(SplitResolverTest,ConnectIntervalsForConstantBetweenBlock)993 TEST_F(SplitResolverTest, ConnectIntervalsForConstantBetweenBlock)
994 {
995 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
996 auto expected_graph = CreateEmptyGraph();
997
998 INITIALIZE_GRAPHS(initial_graph, expected_graph)
999 {
1000 CONSTANT(0, 42);
1001 CONSTANT(1, 64);
1002 PARAMETER(2, 0).u64();
1003
1004 BASIC_BLOCK(2, 3, 4)
1005 {
1006 INST(3, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(2, 2);
1007 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
1008 }
1009
1010 BASIC_BLOCK(3, 5)
1011 {
1012 INST(5, Opcode::Add).u64().Inputs(2, 2);
1013 AFTER_SPLIT_RESOLUTION(INST(11, Opcode::SpillFill));
1014 }
1015
1016 BASIC_BLOCK(4, 5)
1017 {
1018 INST(6, Opcode::Mul).u64().Inputs(2, 2);
1019 AFTER_SPLIT_RESOLUTION(INST(12, Opcode::SpillFill));
1020 }
1021
1022 BASIC_BLOCK(5, -1)
1023 {
1024 INST(7, Opcode::Phi).u64().Inputs(5, 6);
1025 INST(8, Opcode::Add).u64().Inputs(0, 7);
1026 INST(9, Opcode::Add).u64().Inputs(1, 8);
1027 INST(10, Opcode::Return).u64().Inputs(9);
1028 }
1029 }
1030
1031 auto la = RunLivenessAnalysis(initial_graph);
1032 auto con0 = la->GetInstLifeIntervals(&INS(0));
1033 auto con1 = la->GetInstLifeIntervals(&INS(1));
1034 con0->SetReg(0);
1035 con1->SetReg(1);
1036 SplitAssignImmSlot(con0, la->GetInstLifeIntervals(&INS(7))->GetBegin(), 0);
1037 SplitAssignReg(SplitAssignImmSlot(con1, la->GetInstLifeIntervals(&INS(3))->GetBegin(), 0),
1038 la->GetInstLifeIntervals(&INS(7))->GetBegin(), 2);
1039 // Assign reg to the phi and its inputs
1040 la->GetInstLifeIntervals(&INS(5))->SetReg(2);
1041 la->GetInstLifeIntervals(&INS(6))->SetReg(2);
1042 la->GetInstLifeIntervals(&INS(7))->SetReg(2);
1043
1044 SplitResolver resolver(initial_graph, la);
1045 resolver.Run();
1046 CheckSpillFills(INS(5).GetNext(), {{LocationType::IMMEDIATE, LocationType::REGISTER, 0, 2}});
1047 CheckSpillFills(INS(6).GetNext(), {{LocationType::IMMEDIATE, LocationType::REGISTER, 0, 2}});
1048 }
1049
TEST_F(SplitResolverTest,DontReuseSpillFillForConstant)1050 TEST_F(SplitResolverTest, DontReuseSpillFillForConstant)
1051 {
1052 auto initial_graph = InitUsedRegs(CreateEmptyGraph());
1053 auto expected_graph = CreateEmptyGraph();
1054
1055 INITIALIZE_GRAPHS(initial_graph, expected_graph)
1056 {
1057 CONSTANT(0, 42);
1058
1059 BASIC_BLOCK(2, -1)
1060 {
1061 INST(1, Opcode::AddI).u64().Imm(1).Inputs(0);
1062 INST(2, Opcode::Add).u64().Inputs(0, 1);
1063 AFTER_SPLIT_RESOLUTION(INST(3, Opcode::SpillFill));
1064 INST(4, Opcode::SpillFill);
1065 INST(5, Opcode::Add).u64().Inputs(0, 2);
1066 INST(6, Opcode::Return).u64().Inputs(5);
1067 }
1068 }
1069
1070 auto la = RunLivenessAnalysis(initial_graph);
1071 la->GetInstLifeIntervals(&INS(0))->SetLocation(Location::MakeConstant(0));
1072 la->GetInstLifeIntervals(&INS(2))->SetReg(1);
1073 SplitAssignSlot(la->GetInstLifeIntervals(&INS(2)), la->GetInstLifeIntervals(&INS(5))->GetBegin(), 0);
1074 INS(4).CastToSpillFill()->AddSpillFill(Location::MakeConstant(0), Location::MakeRegister(1), DataType::Type::INT64);
1075 INS(4).CastToSpillFill()->SetSpillFillType(SpillFillType::INPUT_FILL);
1076
1077 SplitResolver resolver(initial_graph, la);
1078 resolver.Run();
1079
1080 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
1081 CheckSpillFills(INS(2).GetNext(), {{LocationType::REGISTER, LocationType::STACK, 1, 0}});
1082 }
1083
TEST_F(SplitResolverTest,AppendSpillFIllBeforeLoadArrayPairI)1084 TEST_F(SplitResolverTest, AppendSpillFIllBeforeLoadArrayPairI)
1085 {
1086 auto initial_graph = CreateEmptyGraph();
1087 auto expected_graph = CreateEmptyGraph();
1088
1089 INITIALIZE_GRAPHS(initial_graph, expected_graph)
1090 {
1091 PARAMETER(0, 0).ref();
1092 CONSTANT(1, 42);
1093 CONSTANT(2, 24);
1094
1095 BASIC_BLOCK(2, -1)
1096 {
1097 AFTER_SPLIT_RESOLUTION(INST(13, Opcode::SpillFill));
1098 INST(6, Opcode::LoadArrayPairI).u64().Inputs(0).Imm(0x0);
1099 INST(7, Opcode::LoadPairPart).u64().Inputs(6).Imm(0x0);
1100 INST(8, Opcode::LoadPairPart).u64().Inputs(6).Imm(0x1);
1101 INST(9, Opcode::Add).u64().Inputs(7, 8);
1102 INST(10, Opcode::Add).u64().Inputs(1, 2);
1103 INST(11, Opcode::Add).u64().Inputs(9, 10);
1104 INST(12, Opcode::Return).u64().Inputs(11);
1105 }
1106 }
1107
1108 auto la = RunLivenessAnalysis(initial_graph);
1109 la->GetInstLifeIntervals(&INS(1))->SetReg(1);
1110 la->GetInstLifeIntervals(&INS(2))->SetReg(2);
1111 // Split constants before LoadPairParts
1112 SplitAssignSlot(la->GetInstLifeIntervals(&INS(1)), la->GetInstLifeIntervals(&INS(7))->GetBegin(), 0);
1113 SplitAssignSlot(la->GetInstLifeIntervals(&INS(2)), la->GetInstLifeIntervals(&INS(8))->GetBegin(), 0);
1114 la->GetInstLifeIntervals(&INS(7))->SetReg(1);
1115 la->GetInstLifeIntervals(&INS(8))->SetReg(1);
1116 SplitResolver resolver(initial_graph, la);
1117 resolver.Run();
1118 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
1119 }
1120
TEST_F(SplitResolverTest,SplitAfterLastInstruction)1121 TEST_F(SplitResolverTest, SplitAfterLastInstruction)
1122 {
1123 auto initial_graph = CreateEmptyGraph();
1124 auto expected_graph = CreateEmptyGraph();
1125
1126 INITIALIZE_GRAPHS(initial_graph, expected_graph)
1127 {
1128 PARAMETER(0, 0).u64();
1129 CONSTANT(1, 0);
1130
1131 BASIC_BLOCK(2, 3, 4)
1132 {
1133 INST(2, Opcode::Phi).u64().Inputs(1, 6);
1134 INST(3, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(2, 0);
1135 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_EQ).Imm(0).Inputs(3);
1136 }
1137
1138 BASIC_BLOCK(3, -1)
1139 {
1140 INST(5, Opcode::Return).u64().Inputs(2);
1141 }
1142
1143 BASIC_BLOCK(4, 2)
1144 {
1145 INST(6, Opcode::AddI).u64().Imm(1).Inputs(2);
1146 }
1147 }
1148
1149 auto la = RunLivenessAnalysis(initial_graph);
1150 la->GetInstLifeIntervals(&INS(0))->SetReg(0);
1151 la->GetInstLifeIntervals(&INS(1))->SetReg(2);
1152 la->GetInstLifeIntervals(&INS(2))->SetReg(2);
1153 la->GetInstLifeIntervals(&INS(3))->SetReg(3);
1154 la->GetInstLifeIntervals(&INS(6))->SetReg(2);
1155 SplitAssignSlot(la->GetInstLifeIntervals(&INS(0)), la->GetInstLifeIntervals(&INS(6))->GetEnd(), 0);
1156
1157 InitUsedRegs(initial_graph);
1158 SplitResolver resolver(initial_graph, la);
1159 resolver.Run();
1160 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
1161 }
1162
1163 // TODO (a.popov) Merge equal spill-fills
TEST_F(SplitResolverTest,MultipleEndBlockMoves)1164 TEST_F(SplitResolverTest, MultipleEndBlockMoves)
1165 {
1166 auto initial_graph = CreateEmptyGraph();
1167 auto expected_graph = CreateEmptyGraph();
1168
1169 INITIALIZE_GRAPHS(initial_graph, expected_graph)
1170 {
1171 PARAMETER(0, 0).u64();
1172 PARAMETER(1, 1).u64();
1173 PARAMETER(2, 2).u64();
1174 PARAMETER(3, 3).u64();
1175
1176 BASIC_BLOCK(2, 3, 4)
1177 {
1178 INST(4, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 1);
1179 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_EQ).Imm(0).Inputs(4);
1180 }
1181
1182 BASIC_BLOCK(3, 5)
1183 {
1184 AFTER_SPLIT_RESOLUTION(INST(12, Opcode::SpillFill));
1185 INST(6, Opcode::Add).u64().Inputs(2, 3);
1186 AFTER_SPLIT_RESOLUTION(INST(13, Opcode::SpillFill));
1187 }
1188
1189 BASIC_BLOCK(4, 5)
1190 {
1191 AFTER_SPLIT_RESOLUTION(INST(15, Opcode::SpillFill));
1192 INST(7, Opcode::Mul).u64().Inputs(2, 3);
1193 AFTER_SPLIT_RESOLUTION(INST(14, Opcode::SpillFill));
1194 }
1195
1196 BASIC_BLOCK(5, -1)
1197 {
1198 INST(8, Opcode::Phi).u64().Inputs(6, 7);
1199 INST(9, Opcode::Add).u64().Inputs(0, 1);
1200 INST(10, Opcode::Add).u64().Inputs(8, 9);
1201 INST(11, Opcode::Return).u64().Inputs(10);
1202 }
1203 }
1204
1205 auto la = RunLivenessAnalysis(initial_graph);
1206 auto p0 = la->GetInstLifeIntervals(&INS(0));
1207 auto p1 = la->GetInstLifeIntervals(&INS(1));
1208 p0->SetReg(0);
1209 p1->SetReg(1);
1210 SplitAssignReg(SplitAssignSlot(p0, la->GetInstLifeIntervals(&INS(5))->GetEnd(), 0),
1211 la->GetInstLifeIntervals(&INS(8))->GetBegin(), 0);
1212 SplitAssignReg(SplitAssignSlot(p1, la->GetInstLifeIntervals(&INS(5))->GetEnd(), 1),
1213 la->GetInstLifeIntervals(&INS(8))->GetBegin(), 1);
1214 // Assign reg to the phi and its inputs
1215 la->GetInstLifeIntervals(&INS(6))->SetReg(2);
1216 la->GetInstLifeIntervals(&INS(7))->SetReg(2);
1217 la->GetInstLifeIntervals(&INS(8))->SetReg(2);
1218
1219 InitUsedRegs(initial_graph);
1220 SplitResolver resolver(initial_graph, la);
1221 resolver.Run();
1222 initial_graph->RunPass<Cleanup>();
1223 ASSERT_TRUE(GraphComparator().Compare(initial_graph, expected_graph));
1224 CheckSpillFills(INS(6).GetPrev(), {{LocationType::REGISTER, LocationType::STACK, 0, 0},
1225 {LocationType::REGISTER, LocationType::STACK, 1, 1}});
1226 CheckSpillFills(INS(6).GetNext(), {{LocationType::STACK, LocationType::REGISTER, 0, 0},
1227 {LocationType::STACK, LocationType::REGISTER, 1, 1}});
1228 CheckSpillFills(INS(7).GetPrev(), {{LocationType::REGISTER, LocationType::STACK, 0, 0},
1229 {LocationType::REGISTER, LocationType::STACK, 1, 1}});
1230 CheckSpillFills(INS(7).GetNext(), {{LocationType::STACK, LocationType::REGISTER, 0, 0},
1231 {LocationType::STACK, LocationType::REGISTER, 1, 1}});
1232 }
1233 } // namespace panda::compiler
1234