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/ir/graph_cloner.h"
18 namespace panda::compiler {
19 class GraphClonerTest : public CommonTest {
20 public:
GraphClonerTest()21 GraphClonerTest() : graph_(CreateGraphStartEndBlocks()) {}
22
GetGraph()23 Graph *GetGraph()
24 {
25 return graph_;
26 }
27
28 private:
29 Graph *graph_;
30 };
31
TEST_F(GraphClonerTest,LoopCoping_SimpleLoop)32 TEST_F(GraphClonerTest, LoopCoping_SimpleLoop)
33 {
34 GRAPH(GetGraph())
35 {
36 CONSTANT(0, 0); // initial
37 CONSTANT(1, 1); // increment
38 CONSTANT(2, 10); // len_array
39 PARAMETER(13, 0).s32(); // X
40 BASIC_BLOCK(2, 3, 6)
41 {
42 INST(44, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68);
43 INST(3, Opcode::NewArray).ref().Inputs(44, 2);
44 INST(14, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(0, 13); // i < X
45 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
46 }
47 BASIC_BLOCK(3, 3, 6)
48 {
49 INST(4, Opcode::Phi).s32().Inputs(0, 10);
50 INST(7, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
51 INST(8, Opcode::BoundsCheck).s32().Inputs(2, 4, 7);
52 INST(9, Opcode::StoreArray).s32().Inputs(3, 8, 0); // a[i] = 0
53 INST(10, Opcode::Add).s32().Inputs(4, 1); // i++
54 INST(5, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(10, 13); // i < X
55 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
56 }
57 BASIC_BLOCK(6, 1)
58 {
59 INST(16, Opcode::Phi).s32().Inputs(0, 10);
60 INST(12, Opcode::Return).s32().Inputs(16);
61 }
62 }
63
64 GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneLoop(BB(3).GetLoop());
65 auto graph1 = CreateEmptyGraph();
66 GRAPH(graph1)
67 {
68 CONSTANT(0, 0); // initial
69 CONSTANT(1, 1); // increment
70 CONSTANT(2, 10); // len_array
71 PARAMETER(13, 0).s32(); // X
72 BASIC_BLOCK(2, 7)
73 {
74 INST(44, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68);
75 INST(3, Opcode::NewArray).ref().Inputs(44, 2);
76 }
77 BASIC_BLOCK(7, 3, 6)
78 {
79 INST(14, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(0, 13); // i < X
80 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
81 }
82 BASIC_BLOCK(3, 3, 6)
83 {
84 INST(4, Opcode::Phi).s32().Inputs(0, 10);
85 INST(7, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
86 INST(8, Opcode::BoundsCheck).s32().Inputs(2, 4, 7);
87 INST(9, Opcode::StoreArray).s32().Inputs(3, 8, 0); // a[i] = 0
88 INST(10, Opcode::Add).s32().Inputs(4, 1); // i++
89 INST(5, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(10, 13); // i < X
90 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
91 }
92 BASIC_BLOCK(6, 8)
93 {
94 INST(16, Opcode::Phi).s32().Inputs(0, 10);
95 }
96 BASIC_BLOCK(8, 10, 13)
97 {
98 INST(17, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(16, 13); // i < X
99 INST(18, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(17);
100 }
101 BASIC_BLOCK(10, 10, 13)
102 {
103 INST(19, Opcode::Phi).s32().Inputs(16, 25);
104 INST(22, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
105 INST(23, Opcode::BoundsCheck).s32().Inputs(2, 19, 22);
106 INST(24, Opcode::StoreArray).s32().Inputs(3, 23, 0); // a[i] = 0
107 INST(25, Opcode::Add).s32().Inputs(19, 1); // i++
108 INST(20, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(25, 13); // i < X
109 INST(21, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(20);
110 }
111 BASIC_BLOCK(13, 14)
112 {
113 INST(27, Opcode::Phi).s32().Inputs(16, 25);
114 }
115 BASIC_BLOCK(14, 1)
116 {
117 INST(12, Opcode::Return).s32().Inputs(27);
118 }
119 }
120 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph1));
121 }
122
TEST_F(GraphClonerTest,LoopCoping_LoopSum)123 TEST_F(GraphClonerTest, LoopCoping_LoopSum)
124 {
125 GRAPH(GetGraph())
126 {
127 CONSTANT(0, 0); // initial
128 CONSTANT(1, 1); // increment
129 CONSTANT(2, 10); // len_array
130 PARAMETER(13, 0).s32(); // X
131 BASIC_BLOCK(2, 7)
132 {
133 INST(44, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68);
134 INST(3, Opcode::NewArray).ref().Inputs(44, 2);
135 }
136 BASIC_BLOCK(7, 3, 6)
137 {
138 INST(14, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(0, 13); // i < X
139 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
140 }
141 BASIC_BLOCK(3, 3, 6)
142 {
143 INST(4, Opcode::Phi).s32().Inputs(0, 10);
144 INST(20, Opcode::Phi).s32().Inputs(0, 21);
145 INST(7, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
146 INST(8, Opcode::BoundsCheck).s32().Inputs(2, 4, 7);
147 INST(9, Opcode::LoadArray).s32().Inputs(3, 8); // a[i]
148 INST(21, Opcode::Add).s32().Inputs(20, 9);
149 INST(10, Opcode::Add).s32().Inputs(4, 1); // i++
150 INST(5, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(10, 13); // i < X
151 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
152 }
153 BASIC_BLOCK(6, 5)
154 {
155 INST(16, Opcode::Phi).s32().Inputs(0, 10);
156 INST(22, Opcode::Phi).s32().Inputs(0, 21);
157 }
158 BASIC_BLOCK(5, 1)
159 {
160 INST(12, Opcode::Return).s32().Inputs(22);
161 }
162 }
163 GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneLoop(BB(3).GetLoop());
164 auto graph1 = CreateEmptyGraph();
165 GRAPH(graph1)
166 {
167 CONSTANT(0, 0); // initial
168 CONSTANT(1, 1); // increment
169 CONSTANT(2, 10); // len_array
170 PARAMETER(13, 0).s32(); // X
171 BASIC_BLOCK(2, 7)
172 {
173 INST(44, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68);
174 INST(3, Opcode::NewArray).ref().Inputs(44, 2);
175 }
176 BASIC_BLOCK(7, 3, 6)
177 {
178 INST(14, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(0, 13); // i < X
179 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
180 }
181 BASIC_BLOCK(3, 3, 6)
182 {
183 INST(4, Opcode::Phi).s32().Inputs(0, 10);
184 INST(20, Opcode::Phi).s32().Inputs(0, 21);
185 INST(7, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
186 INST(8, Opcode::BoundsCheck).s32().Inputs(2, 4, 7);
187 INST(9, Opcode::LoadArray).s32().Inputs(3, 8); // a[i]
188 INST(21, Opcode::Add).s32().Inputs(20, 9);
189 INST(10, Opcode::Add).s32().Inputs(4, 1); // i++
190 INST(5, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(10, 13); // i < X
191 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
192 }
193 BASIC_BLOCK(6, 8)
194 {
195 INST(16, Opcode::Phi).s32().Inputs(0, 10);
196 INST(22, Opcode::Phi).s32().Inputs(0, 21);
197 }
198 BASIC_BLOCK(8, 10, 13)
199 {
200 INST(23, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(16, 13); // i < X
201 INST(24, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(23);
202 }
203 BASIC_BLOCK(10, 10, 13)
204 {
205 INST(25, Opcode::Phi).s32().Inputs(16, 31);
206 INST(26, Opcode::Phi).s32().Inputs(22, 30);
207 INST(27, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
208 INST(28, Opcode::BoundsCheck).s32().Inputs(2, 25, 27);
209 INST(29, Opcode::LoadArray).s32().Inputs(3, 28); // a[i]
210 INST(30, Opcode::Add).s32().Inputs(26, 29);
211 INST(31, Opcode::Add).s32().Inputs(25, 1); // i++
212 INST(33, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(31, 13); // i < X
213 INST(34, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(33);
214 }
215 BASIC_BLOCK(13, 14)
216 {
217 INST(35, Opcode::Phi).s32().Inputs(16, 31);
218 INST(36, Opcode::Phi).s32().Inputs(22, 30);
219 }
220 BASIC_BLOCK(14, 1)
221 {
222 INST(12, Opcode::Return).s32().Inputs(36);
223 }
224 }
225 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph1));
226 }
227
TEST_F(GraphClonerTest,LoopCoping_DoubleLoop)228 TEST_F(GraphClonerTest, LoopCoping_DoubleLoop)
229 {
230 GRAPH(GetGraph())
231 {
232 CONSTANT(0, 0); // initial
233 CONSTANT(1, 1); // increment
234 CONSTANT(2, 10); // len_array
235 PARAMETER(3, 0).s32(); // X
236 PARAMETER(4, 1).s32(); // Y
237 BASIC_BLOCK(2, 5, 4)
238 {
239 INST(5, Opcode::Phi).s32().Inputs(0, 8);
240 INST(6, Opcode::Compare).b().CC(ConditionCode::CC_LT).Inputs(5, 4);
241 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
242 }
243 BASIC_BLOCK(5, 6, 3)
244 {
245 INST(10, Opcode::Phi).s32().Inputs(0, 13);
246 INST(11, Opcode::Compare).b().CC(ConditionCode::CC_LT).Inputs(10, 3);
247 INST(12, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(11);
248 }
249 BASIC_BLOCK(6, 5)
250 {
251 INST(13, Opcode::Add).s32().Inputs(10, 1);
252 }
253 BASIC_BLOCK(3, 2)
254 {
255 INST(8, Opcode::Add).s32().Inputs(5, 1);
256 }
257 BASIC_BLOCK(4, 1)
258 {
259 INST(9, Opcode::ReturnVoid).s32();
260 }
261 }
262 ASSERT_FALSE(IsLoopSingleBackEdgeExitPoint((BB(2).GetLoop())));
263 ASSERT_FALSE(IsLoopSingleBackEdgeExitPoint((BB(5).GetLoop())));
264 }
265
TEST_F(GraphClonerTest,LoopCoping_TwoBackEdge)266 TEST_F(GraphClonerTest, LoopCoping_TwoBackEdge)
267 {
268 GRAPH(GetGraph())
269 {
270 PARAMETER(0, 0).b();
271 PARAMETER(1, 1).s32();
272 BASIC_BLOCK(2, 3, 4)
273 {
274 INST(2, Opcode::Phi).Inputs(1, 4, 6).s32();
275 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(0);
276 }
277 BASIC_BLOCK(3, 2, 5)
278 {
279 INST(4, Opcode::Add).Inputs(1, 1).s32();
280 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(0);
281 }
282 BASIC_BLOCK(5, 2)
283 {
284 INST(6, Opcode::Add).Inputs(4, 4).s32();
285 }
286 BASIC_BLOCK(4, -1)
287 {
288 INST(7, Opcode::Return).s32().Inputs(2);
289 }
290 }
291 ASSERT_FALSE(IsLoopSingleBackEdgeExitPoint((BB(2).GetLoop())));
292 }
293
TEST_F(GraphClonerTest,LoopCoping_HeadExit)294 TEST_F(GraphClonerTest, LoopCoping_HeadExit)
295 {
296 // not applied
297 GRAPH(GetGraph())
298 {
299 CONSTANT(0, 0);
300 CONSTANT(1, 1);
301 CONSTANT(2, 10);
302 BASIC_BLOCK(2, 3, 4)
303 {
304 INST(4, Opcode::Phi).s32().Inputs(0, 7);
305 INST(5, Opcode::Compare).b().CC(ConditionCode::CC_LT).Inputs(4, 2);
306 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
307 }
308 BASIC_BLOCK(3, 2)
309 {
310 INST(7, Opcode::Add).s32().Inputs(4, 1);
311 }
312 BASIC_BLOCK(4, 1)
313 {
314 INST(8, Opcode::Return).s32().Inputs(4);
315 }
316 }
317 ASSERT_FALSE(IsLoopSingleBackEdgeExitPoint((BB(2).GetLoop())));
318 }
319
TEST_F(GraphClonerTest,LoopCoping_WithoutIndexResolver)320 TEST_F(GraphClonerTest, LoopCoping_WithoutIndexResolver)
321 {
322 GRAPH(GetGraph())
323 {
324 CONSTANT(0, 0); // initial
325 CONSTANT(1, 1); // increment
326 CONSTANT(2, 10); // len_array
327 PARAMETER(13, 0).s32(); // X
328 BASIC_BLOCK(2, 7)
329 {
330 INST(44, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68);
331 INST(3, Opcode::NewArray).ref().Inputs(44, 2);
332 }
333 BASIC_BLOCK(7, 3, 6)
334 {
335 INST(14, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(0, 13); // i < X
336 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
337 }
338 BASIC_BLOCK(3, 3, 6)
339 {
340 INST(4, Opcode::Phi).s32().Inputs(0, 10);
341 INST(7, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
342 INST(8, Opcode::BoundsCheck).s32().Inputs(2, 4, 7);
343 INST(9, Opcode::StoreArray).s32().Inputs(3, 8, 0); // a[i] = 0
344 INST(10, Opcode::Add).s32().Inputs(4, 1); // i++
345 INST(5, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(10, 13); // i < X
346 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
347 }
348 BASIC_BLOCK(6, 1)
349 {
350 INST(12, Opcode::Return).ref().Inputs(3);
351 }
352 }
353 GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneLoop(BB(3).GetLoop());
354 auto graph1 = CreateEmptyGraph();
355 GRAPH(graph1)
356 {
357 CONSTANT(0, 0); // initial
358 CONSTANT(1, 1); // increment
359 CONSTANT(2, 10); // len_array
360 PARAMETER(13, 0).s32(); // X
361 BASIC_BLOCK(2, 7)
362 {
363 INST(44, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68);
364 INST(3, Opcode::NewArray).ref().Inputs(44, 2);
365 }
366 BASIC_BLOCK(7, 3, 6)
367 {
368 INST(14, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(0, 13); // i < X
369 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
370 }
371 BASIC_BLOCK(3, 3, 6)
372 {
373 INST(4, Opcode::Phi).s32().Inputs(0, 10);
374 INST(7, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
375 INST(8, Opcode::BoundsCheck).s32().Inputs(2, 4, 7);
376 INST(9, Opcode::StoreArray).s32().Inputs(3, 8, 0); // a[i] = 0
377 INST(10, Opcode::Add).s32().Inputs(4, 1); // i++
378 INST(5, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(10, 13); // i < X
379 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
380 }
381 BASIC_BLOCK(6, 8)
382 {
383 INST(16, Opcode::Phi).s32().Inputs(0, 10);
384 }
385 BASIC_BLOCK(8, 10, 14)
386 {
387 INST(17, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(16, 13); // i < X
388 INST(18, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(17);
389 }
390 BASIC_BLOCK(10, 10, 14)
391 {
392 INST(19, Opcode::Phi).s32().Inputs(16, 25);
393 INST(22, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
394 INST(23, Opcode::BoundsCheck).s32().Inputs(2, 19, 22);
395 INST(24, Opcode::StoreArray).s32().Inputs(3, 23, 0); // a[i] = 0
396 INST(25, Opcode::Add).s32().Inputs(19, 1); // i++
397 INST(20, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(25, 13); // i < X
398 INST(21, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(20);
399 }
400 BASIC_BLOCK(14, 13) {}
401 BASIC_BLOCK(13, 1)
402 {
403 INST(12, Opcode::Return).ref().Inputs(3);
404 }
405 }
406 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph1));
407 }
408 } // namespace panda::compiler
409