• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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>(&regs);
84         graph->InitUsedRegs<DataType::FLOAT64>(&regs);
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