1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "unit_test.h"
17 #include "optimizer/analysis/dominators_tree.h"
18 #include "optimizer/analysis/live_registers.h"
19 #include "optimizer/code_generator/registers_description.h"
20 #include "optimizer/optimizations/regalloc/reg_alloc_graph_coloring.h"
21 #include "optimizer/optimizations/regalloc/spill_fills_resolver.h"
22 #include "optimizer/optimizations/cleanup.h"
23 #include "optimizer/ir/graph_cloner.h"
24
25 namespace panda::compiler {
26 class RegAllocGraphColoringTest : public GraphTest {
27 public:
GetParameterSpillFilll(Inst * param)28 SpillFillData GetParameterSpillFilll(Inst *param)
29 {
30 ASSERT(param->IsParameter());
31 ASSERT(param->GetNext()->IsSpillFill());
32 auto spill_fill = param->GetNext()->CastToSpillFill()->GetSpillFill(0);
33 auto param_liveness = GetGraph()->GetAnalysis<LivenessAnalyzer>().GetInstLifeIntervals(param);
34 EXPECT_EQ(param_liveness->GetReg(), spill_fill.SrcValue());
35 EXPECT_EQ(param_liveness->GetSibling()->GetReg(), spill_fill.DstValue());
36 return spill_fill;
37 }
38 };
39
TEST_F(RegAllocGraphColoringTest,Simple)40 TEST_F(RegAllocGraphColoringTest, Simple)
41 {
42 // Test is for bigger number of registers (spilling is not supported yet)
43 if (GetGraph()->GetArch() == Arch::AARCH32) {
44 return;
45 }
46
47 GRAPH(GetGraph())
48 {
49 PARAMETER(0, 0).u64();
50 CONSTANT(1, 1);
51 CONSTANT(2, 10);
52
53 BASIC_BLOCK(2, 3, 4)
54 {
55 INST(3, Opcode::Compare).b().CC(CC_LT).SrcType(DataType::Type::UINT64).Inputs(2, 0);
56 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
57 }
58
59 BASIC_BLOCK(3, 4)
60 {
61 INST(5, Opcode::Add).u64().Inputs(0, 2);
62 }
63
64 BASIC_BLOCK(4, -1)
65 {
66 INST(6, Opcode::Phi).u64().Inputs(2, 5);
67 INST(7, Opcode::Add).u64().Inputs(6, 1);
68 INST(8, Opcode::Return).u64().Inputs(7);
69 }
70 }
71 auto result = GetGraph()->RunPass<RegAllocGraphColoring>();
72 ASSERT_TRUE(result);
73 GraphChecker(GetGraph()).Check();
74 EXPECT_NE(INS(0).GetDstReg(), INS(6).GetDstReg());
75 EXPECT_NE(INS(0).GetDstReg(), INS(1).GetDstReg());
76 EXPECT_NE(INS(0).GetDstReg(), INS(2).GetDstReg());
77
78 auto arch = GetGraph()->GetArch();
79 size_t first_callee = arch != Arch::NONE ? GetFirstCalleeReg(arch, false) : 0;
80 EXPECT_LT(INS(0).CastToParameter()->GetLocationData().DstValue(), first_callee);
81 EXPECT_LT(INS(1).GetDstReg(), first_callee);
82 EXPECT_LT(INS(2).GetDstReg(), first_callee);
83 EXPECT_LT(INS(5).GetDstReg(), first_callee);
84 EXPECT_LT(INS(6).GetDstReg(), first_callee);
85 EXPECT_LT(INS(7).GetDstReg(), first_callee);
86 }
87
TEST_F(RegAllocGraphColoringTest,AffineComponent)88 TEST_F(RegAllocGraphColoringTest, AffineComponent)
89 {
90 // Test is for bigger number of registers (spilling is not supported yet)
91 if (GetGraph()->GetArch() == Arch::AARCH32) {
92 return;
93 }
94
95 GRAPH(GetGraph())
96 {
97 PARAMETER(0, 0).u64();
98 CONSTANT(1, 1);
99 CONSTANT(2, 10);
100
101 BASIC_BLOCK(2, 3, 4)
102 {
103 INST(3, Opcode::Compare).b().CC(CC_LT).SrcType(DataType::Type::UINT64).Inputs(2, 0);
104 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
105 }
106
107 BASIC_BLOCK(3, 8)
108 {
109 INST(5, Opcode::Add).u64().Inputs(0, 2);
110 }
111
112 BASIC_BLOCK(4, 5, 6)
113 {
114 INST(7, Opcode::Compare).b().CC(CC_LT).SrcType(DataType::Type::UINT64).Inputs(1, 0);
115 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
116 }
117
118 BASIC_BLOCK(5, 7)
119 {
120 CONSTANT(9, 188);
121 }
122
123 BASIC_BLOCK(6, 7)
124 {
125 INST(6, Opcode::Add).u64().Inputs(0, 1);
126 }
127
128 BASIC_BLOCK(7, 8)
129 {
130 INST(10, Opcode::Phi).u64().Inputs(9, 6);
131 }
132
133 BASIC_BLOCK(8, -1)
134 {
135 INST(11, Opcode::Phi).u64().Inputs(5, 10);
136 INST(12, Opcode::Add).u64().Inputs(11, 1);
137 INST(13, Opcode::Add).u64().Inputs(12, 0);
138 INST(14, Opcode::Return).u64().Inputs(13);
139 }
140 }
141 auto result = GetGraph()->RunPass<RegAllocGraphColoring>();
142 ASSERT_TRUE(result);
143 GraphChecker(GetGraph()).Check();
144 EXPECT_EQ(INS(0).GetDstReg(), INS(3).GetSrcReg(1));
145 EXPECT_EQ(INS(0).GetDstReg(), INS(7).GetSrcReg(1));
146
147 // Check affinity group
148 EXPECT_EQ(INS(5).GetDstReg(), INS(6).GetDstReg());
149 EXPECT_EQ(INS(5).GetDstReg(), INS(9).GetDstReg());
150 EXPECT_EQ(INS(5).GetDstReg(), INS(10).GetDstReg());
151 EXPECT_EQ(INS(5).GetDstReg(), INS(11).GetDstReg());
152 }
153
TEST_F(RegAllocGraphColoringTest,SimpleCall)154 TEST_F(RegAllocGraphColoringTest, SimpleCall)
155 {
156 // Test is for bigger number of registers (spilling is not supported yet)
157 if (GetGraph()->GetArch() == Arch::AARCH32 || GetGraph()->GetCallingConvention() == nullptr) {
158 return;
159 }
160
161 GRAPH(GetGraph())
162 {
163 PARAMETER(0, 0).ref();
164 PARAMETER(1, 1).u64();
165 CONSTANT(2, 1);
166 CONSTANT(3, 10);
167
168 BASIC_BLOCK(2, 3, 4)
169 {
170 INST(4, Opcode::Compare).b().CC(CC_LT).SrcType(DataType::Type::UINT64).Inputs(3, 1);
171 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
172 }
173
174 BASIC_BLOCK(3, 4)
175 {
176 INST(6, Opcode::SaveState).Inputs().SrcVregs({});
177 INST(7, Opcode::CallStatic).b().InputsAutoType(0, 1, 2, 6);
178 INST(8, Opcode::Add).u64().Inputs(1, 3);
179 }
180
181 BASIC_BLOCK(4, -1)
182 {
183 INST(9, Opcode::Phi).u64().Inputs(3, 8);
184 INST(10, Opcode::Add).u64().Inputs(9, 1);
185 INST(11, Opcode::Return).u64().Inputs(10);
186 }
187 }
188 auto regalloc = RegAllocGraphColoring(GetGraph());
189 auto arch = GetGraph()->GetArch();
190 size_t first_callee = arch != Arch::NONE ? GetFirstCalleeReg(arch, false) : 0;
191
192 auto result = regalloc.Run();
193 ASSERT_TRUE(result);
194 GraphChecker(GetGraph()).Check();
195
196 auto param1_sf = GetParameterSpillFilll(&INS(1));
197 EXPECT_NE(param1_sf.DstValue(), INS(8).GetDstReg());
198 EXPECT_NE(param1_sf.DstValue(), INS(2).GetDstReg());
199 EXPECT_NE(param1_sf.DstValue(), INS(3).GetDstReg());
200
201 // Check intervals in calle registers and splits
202 EXPECT_LT(INS(0).GetDstReg(), first_callee);
203 EXPECT_GE(param1_sf.DstValue(), first_callee);
204 }
205
206 // Check fallback to Linearscan (spilling is not implemented yet)
TEST_F(RegAllocGraphColoringTest,HighPressure)207 TEST_F(RegAllocGraphColoringTest, HighPressure)
208 {
209 // Test is for bigger number of registers (spilling is not supported yet)
210 if (GetGraph()->GetArch() == Arch::AARCH32 || GetGraph()->GetCallingConvention() == nullptr) {
211 return;
212 }
213
214 GRAPH(GetGraph())
215 {
216 PARAMETER(0, 0).u64();
217 CONSTANT(1, 1);
218 CONSTANT(2, 10);
219 CONSTANT(3, 10);
220 CONSTANT(4, 10);
221 CONSTANT(5, 10);
222 CONSTANT(6, 10);
223
224 BASIC_BLOCK(2, -1)
225 {
226 INST(7, Opcode::Add).u64().Inputs(0, 1);
227 INST(8, Opcode::Add).u64().Inputs(0, 2);
228 INST(9, Opcode::Add).u64().Inputs(0, 3);
229 INST(10, Opcode::Add).u64().Inputs(0, 4);
230 INST(11, Opcode::Add).u64().Inputs(0, 5);
231 INST(12, Opcode::Add).u64().Inputs(0, 6);
232 INST(13, Opcode::Add).u64().Inputs(0, 7);
233 INST(14, Opcode::Add).u64().Inputs(0, 8);
234 INST(15, Opcode::Add).u64().Inputs(8, 7);
235 INST(16, Opcode::Add).u64().Inputs(9, 8);
236
237 INST(17, Opcode::SaveState).Inputs().SrcVregs({});
238 INST(18, Opcode::CallStatic).b().InputsAutoType(0, 1, 2, 17);
239
240 INST(20, Opcode::Add).u64().Inputs(1, 2);
241 INST(21, Opcode::Add).u64().Inputs(3, 4);
242 INST(22, Opcode::Add).u64().Inputs(5, 6);
243 INST(23, Opcode::Add).u64().Inputs(7, 8);
244 INST(24, Opcode::Add).u64().Inputs(9, 10);
245 INST(25, Opcode::Add).u64().Inputs(11, 12);
246 INST(26, Opcode::Add).u64().Inputs(13, 14);
247 INST(27, Opcode::Add).u64().Inputs(15, 16);
248
249 INST(60, Opcode::Return).u64().Inputs(27);
250 }
251 }
252 auto result = GetGraph()->RunPass<RegAllocGraphColoring>();
253 ASSERT_FALSE(result);
254 GraphChecker(GetGraph()).Check();
255
256 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
257 for (const auto *interv : la.GetLifeIntervals()) {
258 EXPECT_EQ(interv->GetSibling(), nullptr);
259 if (!interv->IsPreassigned() && !interv->IsPhysical()) {
260 EXPECT_FALSE(interv->HasReg());
261 }
262 }
263 }
264 } // namespace panda::compiler
265