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
18 namespace panda::compiler {
19 class LoopAnalyzerTest : public CommonTest {
20 public:
LoopAnalyzerTest()21 LoopAnalyzerTest() : graph_(CreateGraphStartEndBlocks()) {}
22 ~LoopAnalyzerTest() override {}
23
24 template <typename T>
CheckVectorEqualSet(ArenaVector<T *> blocks, std::set<T *> &&excepct)25 void CheckVectorEqualSet(ArenaVector<T *> blocks, std::set<T *> &&excepct)
26 {
27 ASSERT_EQ(blocks.size(), excepct.size());
28
29 std::set<T *> result;
30 for (auto block : blocks) {
31 result.insert(block);
32 }
33 EXPECT_EQ(result, excepct);
34 }
35
CheckVectorEqualBlocksIdSet(ArenaVector<BasicBlock *> blocks, std::vector<int> &&bb_ids)36 void CheckVectorEqualBlocksIdSet(ArenaVector<BasicBlock *> blocks, std::vector<int> &&bb_ids)
37 {
38 std::set<BasicBlock *> bb_set;
39 for (auto id : bb_ids) {
40 bb_set.insert(&BB(id));
41 }
42 CheckVectorEqualSet(blocks, std::move(bb_set));
43 }
44
CheckPhiInputs(BasicBlock *block)45 void CheckPhiInputs(BasicBlock *block)
46 {
47 for (auto phi : block->PhiInsts()) {
48 for (unsigned i = 0; i < phi->GetInputs().size(); i++) {
49 EXPECT_EQ(block->GetPredsBlocks()[i], phi->GetInputs()[i].GetInst()->GetBasicBlock());
50 }
51 }
52 }
53
GetGraph()54 Graph *GetGraph()
55 {
56 return graph_;
57 }
58
59 private:
60 Graph *graph_;
61 };
62
63 /*
64 * Test Graph:
65 * [2]
66 * |
67 * v
68 * /------/------------->[3]<---------------------\
69 * | | | |
70 * | | v |
71 * | | [4]<---------\ |
72 * | | | | |
73 * | | | [6] |
74 * | | | ^ |
75 * | | v | |
76 * [17] [19] [5]----------/ |
77 * | | | |
78 * | | v |
79 * | [18] [7] [14]
80 * | ^ | ^
81 * | | v |
82 * [16] \--------------[8]<-------------\ |
83 * ^ | | |
84 * | v | |
85 * | [9] [11] |
86 * | / \ ^ |
87 * | v v | |
88 * \----------------[15] [10]---------/ |
89 * | |
90 * v |
91 * [12] |
92 * | |
93 * v |
94 * [13]----------------/
95 * |
96 * V
97 * [20]
98 * |
99 * V
100 * [exit]
101 *
102 * Loop1:
103 * header: B4
104 * back_edges: B5
105 * blocks: B4, B5, B6
106 * outer_loop: Loop3
107 * Loop2:
108 * header: B8
109 * back_edges: B11
110 * blocks: B8, B9, B10, B11
111 * outer_loop: Loop3
112 * Loop3:
113 * header: B3
114 * back_edges: B14, B17, B19
115 * blocks: B3, B7, B12, B13, B14, B15, B16, B17, B18, B19
116 * inner_loops: Loop1, Loop2
117 *
118 */
TEST_F(LoopAnalyzerTest, LoopAnalyzer)119 TEST_F(LoopAnalyzerTest, LoopAnalyzer)
120 {
121 GRAPH(GetGraph())
122 {
123 CONSTANT(0, 0);
124 CONSTANT(1, 1);
125 BASIC_BLOCK(2, 3) {}
126 BASIC_BLOCK(3, 4) {}
127 BASIC_BLOCK(4, 5) {}
128 BASIC_BLOCK(5, 6, 7)
129 {
130 INST(5, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
131 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
132 }
133 BASIC_BLOCK(6, 4) {}
134 BASIC_BLOCK(7, 8) {}
135 BASIC_BLOCK(8, 9, 18)
136 {
137 INST(9, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
138 INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(9);
139 }
140 BASIC_BLOCK(9, 10, 15)
141 {
142 INST(11, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
143 INST(12, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(11);
144 }
145 BASIC_BLOCK(10, 11, 12)
146 {
147 INST(13, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
148 INST(14, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(13);
149 }
150 BASIC_BLOCK(11, 8) {}
151 BASIC_BLOCK(12, 13) {}
152 BASIC_BLOCK(13, 14, 20)
153 {
154 INST(17, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
155 INST(18, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(17);
156 }
157 BASIC_BLOCK(14, 3) {}
158 BASIC_BLOCK(15, 16) {}
159 BASIC_BLOCK(16, 17) {}
160 BASIC_BLOCK(17, 3) {}
161 BASIC_BLOCK(18, 19) {}
162 BASIC_BLOCK(19, 3) {}
163 BASIC_BLOCK(20, -1)
164 {
165 INST(25, Opcode::ReturnVoid);
166 }
167 }
168
169 auto loop1 = BB(4).GetLoop();
170 auto loop2 = BB(8).GetLoop();
171 auto loop3 = BB(3).GetLoop();
172 auto root_loop = GetGraph()->GetRootLoop();
173
174 ASSERT_NE(loop1, nullptr);
175 ASSERT_NE(loop2, nullptr);
176 ASSERT_NE(loop3, nullptr);
177
178 ASSERT_EQ(loop1->GetHeader(), &BB(4));
179 ASSERT_EQ(loop1->GetPreHeader(), &BB(3));
180 CheckVectorEqualBlocksIdSet(loop1->GetBackEdges(), {6});
181 CheckVectorEqualBlocksIdSet(loop1->GetBlocks(), {4, 5, 6});
182 CheckVectorEqualSet(loop1->GetInnerLoops(), {});
183 EXPECT_EQ(loop1->GetOuterLoop(), loop3);
184 EXPECT_EQ(loop1->IsIrreducible(), false);
185
186 ASSERT_EQ(loop2->GetHeader(), &BB(8));
187 ASSERT_EQ(loop2->GetPreHeader(), &BB(7));
188 CheckVectorEqualBlocksIdSet(loop2->GetBackEdges(), {11});
189 CheckVectorEqualBlocksIdSet(loop2->GetBlocks(), {8, 9, 10, 11});
190 CheckVectorEqualSet(loop2->GetInnerLoops(), {});
191 EXPECT_EQ(loop2->GetOuterLoop(), loop3);
192 EXPECT_EQ(loop2->IsIrreducible(), false);
193
194 ASSERT_EQ(loop3->GetHeader(), &BB(3));
195 ASSERT_EQ(loop3->GetPreHeader(), &BB(2));
196 CheckVectorEqualBlocksIdSet(loop3->GetBackEdges(), {14, 17, 19});
197 CheckVectorEqualBlocksIdSet(loop3->GetBlocks(), {3, 7, 12, 13, 14, 15, 16, 17, 18, 19});
198 CheckVectorEqualSet(loop3->GetInnerLoops(), {loop1, loop2});
199 EXPECT_EQ(loop3->GetOuterLoop(), root_loop);
200 EXPECT_EQ(loop3->IsIrreducible(), false);
201
202 EXPECT_EQ(BB(2).GetLoop(), root_loop);
203 EXPECT_EQ(BB(20).GetLoop(), root_loop);
204 CheckVectorEqualSet(root_loop->GetInnerLoops(), {loop3});
205 }
206
207 /*
208 * Initial Graph:
209 * [entry]
210 * |
211 * v
212 * /-----[2]-----\
213 * | | |
214 * v v v
215 * [3] [4] [5]
216 * | | |
217 * | v |
218 * \---->[6]<----/<----------\
219 * | PHI(3,4,5,8) |
220 * | PHI(3,4,5,8) |
221 * v |
222 * [7]----->[8]--------/
223 * |
224 * |
225 * v
226 * [exit]
227 *
228 * After loop pre-header insertion:
229 *
230 * [entry]
231 * |
232 * v
233 * /---------[2]----------\
234 * | | |
235 * v v v
236 * [3] [4] [5]
237 * | | |
238 * | v |
239 * \---->[pre-header]<----/
240 * | PHI(3,4,5)
241 * | PHI(3,4,5)
242 * V
243 * [6]<-------------------\
244 * | PHI(8,pre-header) |
245 * | PHI(8,pre-header) |
246 * v |
247 * [7]-------->[8]--------/
248 * |
249 * |
250 * v
251 * [exit]
252 *
253 *
254 */
TEST_F(LoopAnalyzerTest, PreheaderInsert)255 TEST_F(LoopAnalyzerTest, PreheaderInsert)
256 {
257 GRAPH(GetGraph())
258 {
259 PARAMETER(0, 1).u64();
260 PARAMETER(1, 5).u64();
261 PARAMETER(2, 10).u64();
262
263 BASIC_BLOCK(2, 4, 5)
264 {
265 INST(3, Opcode::Not).u64().Inputs(0);
266 INST(19, Opcode::Compare).b().Inputs(0, 1);
267 INST(20, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(19);
268 }
269 BASIC_BLOCK(4, 6)
270 {
271 INST(5, Opcode::Add).u64().Inputs(0, 1);
272 }
273 BASIC_BLOCK(5, 6)
274 {
275 INST(6, Opcode::Add).u64().Inputs(0, 2);
276 }
277 BASIC_BLOCK(6, 7)
278 {
279 INST(7, Opcode::Phi).u64().Inputs({{4, 5}, {5, 6}, {8, 12}});
280 INST(8, Opcode::Phi).u64().Inputs({{4, 5}, {5, 6}, {8, 12}});
281 }
282 BASIC_BLOCK(7, 8, 9)
283 {
284 INST(9, Opcode::Mul).u64().Inputs(7, 8);
285 INST(10, Opcode::Compare).b().Inputs(9, 2);
286 INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
287 }
288 BASIC_BLOCK(8, 6)
289 {
290 INST(12, Opcode::Mul).u64().Inputs(9, 1);
291 }
292 BASIC_BLOCK(9, -1)
293 {
294 INST(18, Opcode::ReturnVoid);
295 }
296 }
297
298 auto loop = BB(6).GetLoop();
299 ASSERT_NE(loop, nullptr);
300 EXPECT_EQ(loop->GetHeader(), &BB(6));
301 CheckVectorEqualBlocksIdSet(loop->GetBackEdges(), {8});
302
303 auto pre_header = loop->GetPreHeader();
304 ASSERT_EQ(pre_header->GetLoop(), loop->GetOuterLoop());
305 CheckVectorEqualBlocksIdSet(pre_header->GetPredsBlocks(), {4, 5});
306 CheckVectorEqualBlocksIdSet(pre_header->GetSuccsBlocks(), {6});
307 EXPECT_EQ(loop->GetHeader()->GetDominator(), pre_header);
308 CheckVectorEqualBlocksIdSet(pre_header->GetDominatedBlocks(), {6});
309
310 CheckPhiInputs(&BB(6));
311 CheckPhiInputs(pre_header);
312 }
313
314 /*
315 * Initial Graph:
316 * [0]
317 * |
318 * v
319 * [2]<------\
320 * | |
321 * v |
322 * [3]-------/
323 * |
324 * v
325 * [4]<------\
326 * | |
327 * v |
328 * [5]-------/
329 * |
330 * V
331 * [6]----->[1]
332 *
333 * After loop pre-headers insertion:
334 *
335 */
TEST_F(LoopAnalyzerTest, PreheaderInsert2)336 TEST_F(LoopAnalyzerTest, PreheaderInsert2)
337 {
338 GRAPH(GetGraph())
339 {
340 CONSTANT(0, 0);
341 CONSTANT(1, 1);
342 BASIC_BLOCK(2, 3) {}
343 BASIC_BLOCK(3, 4, 2)
344 {
345 INST(3, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
346 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
347 }
348 BASIC_BLOCK(4, 5) {}
349 BASIC_BLOCK(5, 6, 4)
350 {
351 INST(6, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
352 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
353 }
354 BASIC_BLOCK(6, -1)
355 {
356 INST(8, Opcode::ReturnVoid);
357 }
358 }
359
360 auto loop1 = BB(2).GetLoop();
361 auto loop2 = BB(4).GetLoop();
362 CheckVectorEqualBlocksIdSet(loop1->GetPreHeader()->GetPredsBlocks(), {0});
363 CheckVectorEqualBlocksIdSet(loop1->GetPreHeader()->GetSuccsBlocks(), {2});
364 CheckVectorEqualBlocksIdSet(loop2->GetPreHeader()->GetPredsBlocks(), {3});
365 CheckVectorEqualBlocksIdSet(loop2->GetPreHeader()->GetSuccsBlocks(), {4});
366 }
367
368 /**
369 * Check infinite loop
370 *
371 * [begin]
372 * |
373 * [2]<------\
374 * / \ |
375 * [4] [3]---/
376 * |
377 * [5]<---\
378 * | |
379 * [6]----/
380 */
TEST_F(LoopAnalyzerTest, InfiniteLoop)381 TEST_F(LoopAnalyzerTest, InfiniteLoop)
382 {
383 GRAPH(GetGraph())
384 {
385 PARAMETER(0, 0).s32();
386 PARAMETER(1, 1).s32();
387 CONSTANT(2, 1);
388
389 BASIC_BLOCK(2, 3, 4)
390 {
391 INST(3, Opcode::Phi).s32().Inputs(0, 6);
392 INST(4, Opcode::Compare).b().CC(CC_NE).Inputs(3, 1);
393 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
394 }
395 BASIC_BLOCK(3, 2)
396 {
397 INST(6, Opcode::Add).s32().Inputs(3, 2);
398 }
399 BASIC_BLOCK(4, 5) {}
400 BASIC_BLOCK(5, 5)
401 {
402 INST(7, Opcode::Phi).s32().Inputs(3, 8);
403 INST(8, Opcode::Add).s32().Inputs(7, 2);
404 }
405 }
406
407 auto loop1 = BB(2).GetLoop();
408 auto loop2 = BB(5).GetLoop();
409 ASSERT_FALSE(loop1->IsInfinite());
410 ASSERT_TRUE(loop2->IsInfinite());
411 }
412
413 /**
414 * Test checks the ASSERTION fail issue fix in a Loop::AppendBlock.
415 *
416 * Original progam:
417 *
418 * .function u1 main(){
419 * ldai 0
420 * jltz loop1
421 * jltz loop2
422 * loop1:
423 * jltz loop1
424 * loop2:
425 * jltz loop1
426 * return
427 * }
428 *
429 * Graph dump:
430 *
431 * BB 5
432 * prop: start
433 * succs: [bb 0]
434 *
435 * BB 0 preds: [bb 5]
436 * succs: [bb 1, bb 2]
437 *
438 * BB 2 preds: [bb 0]
439 * succs: [bb 3, bb 1]
440 *
441 * BB 1 preds: [bb 0, bb 2, bb 1, bb 3]
442 * succs: [bb 1, bb 3]
443 *
444 * BB 3 preds: [bb 2, bb 1]
445 * succs: [bb 1, bb 4]
446 *
447 * BB 4 preds: [bb 3]
448 * succs: [bb 6]
449 *
450 * BB 6 preds: [bb 4]
451 * prop: end
452 *
453 * Test Graph:
454 *
455 * [5-start]
456 * |
457 * [0] --> [2]
458 * \ /
459 * [3] <--> [1] <-- ┐
460 * | | |
461 * [4] └ ---> ┘
462 * |
463 * [6-end]
464 *
465 */
TEST_F(LoopAnalyzerTest, LoopTest1)466 TEST_F(LoopAnalyzerTest, LoopTest1)
467 {
468 GRAPH(GetGraph())
469 {
470 CONSTANT(0, 0);
471 CONSTANT(1, 1);
472
473 BASIC_BLOCK(10, 11, 12)
474 {
475 INST(2, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
476 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
477 }
478 BASIC_BLOCK(12, 13, 11)
479 {
480 INST(4, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
481 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
482 }
483 BASIC_BLOCK(11, 11, 13)
484 {
485 INST(6, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
486 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
487 }
488 BASIC_BLOCK(13, 11, 14)
489 {
490 INST(8, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
491 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
492 }
493 BASIC_BLOCK(14, -1)
494 {
495 INST(10, Opcode::ReturnVoid);
496 }
497 }
498
499 // No asserts, just IrBuilder sanity check
500 }
501 } // namespace panda::compiler
502