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/optimizations/loop_peeling.h"
18 #include "optimizer/optimizations/cleanup.h"
19 #include "optimizer/ir/graph_cloner.h"
20
21 namespace panda::compiler {
22 class LoopPeelingTest : public GraphTest {
23 protected:
BuildGraphTwoBackEdges(Graph * graph)24 void BuildGraphTwoBackEdges(Graph *graph)
25 {
26 GRAPH(graph)
27 {
28 PARAMETER(0, 0).b();
29 PARAMETER(1, 1).u64();
30 BASIC_BLOCK(2, 3, 4)
31 {
32 INST(2, Opcode::Phi).Inputs(1, 4, 6).u64();
33 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(0);
34 }
35 BASIC_BLOCK(3, 2, 5)
36 {
37 INST(4, Opcode::Add).Inputs(1, 1).u64();
38 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(0);
39 }
40 BASIC_BLOCK(5, 2)
41 {
42 INST(6, Opcode::Add).Inputs(4, 4).u64();
43 }
44 BASIC_BLOCK(4, -1)
45 {
46 INST(7, Opcode::Return).u64().Inputs(2);
47 }
48 }
49 }
50
BuildGraphNotHeaderExit(Graph * graph)51 void BuildGraphNotHeaderExit(Graph *graph)
52 {
53 GRAPH(graph)
54 {
55 PARAMETER(1, 1).u64();
56 BASIC_BLOCK(2, 6, 7)
57 {
58 INST(2, Opcode::Phi).Inputs(1, 6).u64();
59 INST(20, Opcode::SaveState).NoVregs();
60 INST(8, Opcode::CallStatic).v0id().InputsAutoType(20);
61 INST(0, Opcode::IfImm).SrcType(DataType::UINT64).CC(CC_NE).Imm(0).Inputs(1);
62 }
63 BASIC_BLOCK(6, 3)
64 {
65 INST(3, Opcode::Add).Inputs(1, 2).u64();
66 }
67 BASIC_BLOCK(7, 3)
68 {
69 INST(9, Opcode::Add).Inputs(2, 1).u64();
70 }
71 BASIC_BLOCK(3, 4, 5)
72 {
73 INST(10, Opcode::Phi).Inputs(3, 9).u64();
74 INST(4, Opcode::Add).Inputs(1, 10).u64();
75 INST(5, Opcode::IfImm).SrcType(DataType::UINT64).CC(CC_NE).Imm(0).Inputs(2);
76 }
77 BASIC_BLOCK(4, 2)
78 {
79 INST(6, Opcode::Add).Inputs(4, 4).u64();
80 }
81 BASIC_BLOCK(5, -1)
82 {
83 INST(7, Opcode::Return).u64().Inputs(4);
84 }
85 }
86 }
87
BuildGraphHeaderAndBackEdgeExit(Graph * graph)88 void BuildGraphHeaderAndBackEdgeExit(Graph *graph)
89 {
90 GRAPH(graph)
91 {
92 CONSTANT(0, 10);
93 CONSTANT(1, 0);
94 CONSTANT(2, 1);
95 BASIC_BLOCK(2, 3, 4)
96 {
97 INST(3, Opcode::Phi).u64().Inputs(1, 9);
98 INST(4, Opcode::Phi).u64().Inputs(1, 10);
99 INST(6, Opcode::SafePoint).Inputs(0, 3, 4, 4).SrcVregs({0, 1, 2, 3});
100 INST(7, Opcode::Compare).CC(CC_EQ).b().Inputs(4, 0);
101 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
102 }
103 BASIC_BLOCK(3, 2, 4)
104 {
105 INST(9, Opcode::And).u64().Inputs(4, 3);
106 INST(10, Opcode::Add).u64().Inputs(4, 2);
107 INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(1);
108 }
109 BASIC_BLOCK(4, -1)
110 {
111 INST(12, Opcode::Phi).u64().Inputs(4, 10);
112 INST(13, Opcode::Return).u64().Inputs(12);
113 }
114 }
115 }
116
BuildGraphMultiExit(Graph * graph)117 void BuildGraphMultiExit(Graph *graph)
118 {
119 GRAPH(graph)
120 {
121 PARAMETER(0, 0).b();
122 PARAMETER(1, 1).u64();
123 BASIC_BLOCK(2, 3, 5)
124 {
125 INST(2, Opcode::Phi).Inputs(1, 6).u64();
126 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(0);
127 }
128 BASIC_BLOCK(3, 4, 5)
129 {
130 INST(4, Opcode::Add).Inputs(1, 1).u64();
131 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(0);
132 }
133 BASIC_BLOCK(4, 2)
134 {
135 INST(6, Opcode::Add).Inputs(4, 4).u64();
136 }
137 BASIC_BLOCK(5, -1)
138 {
139 INST(7, Opcode::Phi).Inputs(2, 4).u64();
140 INST(8, Opcode::Return).u64().Inputs(7);
141 }
142 }
143 }
144 };
145
146 /*
147 * [0]
148 * |
149 * v
150 * /---->[2]-----\
151 * | | |
152 * | v v
153 * \-----[3] [4]
154 * |
155 * [exit]
156 */
TEST_F(LoopPeelingTest,CloneBlock)157 TEST_F(LoopPeelingTest, CloneBlock)
158 {
159 GRAPH(GetGraph())
160 {
161 PARAMETER(0, 0).u64();
162 PARAMETER(1, 1).u64();
163 PARAMETER(2, 2).u64();
164 BASIC_BLOCK(2, 3, 4)
165 {
166 INST(3, Opcode::Phi).u64().Inputs(1, 9).u64();
167 INST(4, Opcode::Phi).u64().Inputs(2, 10).u64();
168 INST(6, Opcode::SafePoint).Inputs(0, 3, 4).SrcVregs({0, 1, 2});
169 INST(7, Opcode::Compare).CC(CC_EQ).b().Inputs(0, 3);
170 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
171 }
172 BASIC_BLOCK(3, 2)
173 {
174 INST(9, Opcode::And).u64().Inputs(4, 3);
175 INST(10, Opcode::Add).u64().Inputs(4, 2);
176 }
177 BASIC_BLOCK(4, -1)
178 {
179 INST(13, Opcode::Div).Inputs(3, 4).u64();
180 INST(14, Opcode::Return).u64().Inputs(13);
181 }
182 }
183 GetGraph()->RunPass<LoopAnalyzer>();
184 auto graph_cloner = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator());
185 graph_cloner.CloneLoopHeader(&BB(2), &BB(4), BB(2).GetLoop()->GetPreHeader());
186 GetGraph()->RunPass<Cleanup>();
187
188 auto expected_graph = CreateEmptyGraph();
189 GRAPH(expected_graph)
190 {
191 PARAMETER(0, 0).u64();
192 PARAMETER(1, 1).u64();
193 PARAMETER(2, 2).u64();
194 BASIC_BLOCK(8, 2, 4)
195 {
196 INST(15, Opcode::Compare).CC(CC_EQ).b().Inputs(0, 1);
197 INST(16, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(15);
198 }
199 BASIC_BLOCK(2, 3, 4)
200 {
201 INST(3, Opcode::Phi).u64().Inputs({{8, 1}, {3, 9}}).u64();
202 INST(4, Opcode::Phi).u64().Inputs({{8, 2}, {3, 10}}).u64();
203 INST(6, Opcode::SafePoint).Inputs(0, 3, 4).SrcVregs({0, 1, 2});
204 INST(7, Opcode::Compare).CC(CC_EQ).b().Inputs(0, 3);
205 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
206 }
207 BASIC_BLOCK(3, 2)
208 {
209 INST(9, Opcode::And).u64().Inputs(4, 3);
210 INST(10, Opcode::Add).u64().Inputs(4, 2);
211 }
212 BASIC_BLOCK(4, -1)
213 {
214 INST(17, Opcode::Phi).u64().Inputs({{2, 3}, {8, 1}}).u64();
215 INST(18, Opcode::Phi).u64().Inputs({{2, 4}, {8, 2}}).u64();
216 INST(13, Opcode::Div).Inputs(17, 18).u64();
217 INST(14, Opcode::Return).u64().Inputs(13);
218 }
219 }
220 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), expected_graph));
221 }
222
223 /*
224 * [0]
225 * |
226 * v
227 * /---->[2]-----\
228 * | | |
229 * | v v
230 * \-----[3] [4]
231 * |
232 * [exit]
233 *
234 * Transform to:
235 *
236 * [0]
237 * |
238 * v
239 * [pre-loop]---------\
240 * | |
241 * /---->[2] |
242 * | | |
243 * | v |
244 * | [3] |
245 * | | |
246 * | v v
247 * \--[loop-exit]--->[loop-outer]
248 * |
249 * v
250 * [4]
251 * |
252 * v
253 * [exit]
254 */
TEST_F(LoopPeelingTest,SingleLoop)255 TEST_F(LoopPeelingTest, SingleLoop)
256 {
257 GRAPH(GetGraph())
258 {
259 PARAMETER(0, 0).u64();
260 PARAMETER(1, 1).u64();
261 PARAMETER(2, 2).u64();
262 BASIC_BLOCK(2, 3, 4)
263 {
264 INST(3, Opcode::Phi).u64().Inputs(1, 5);
265 INST(4, Opcode::Phi).u64().Inputs(2, 10);
266 INST(5, Opcode::Sub).u64().Inputs(3, 2);
267 INST(6, Opcode::SafePoint).Inputs(0, 3, 4).SrcVregs({0, 1, 2});
268 INST(7, Opcode::Compare).CC(CC_EQ).b().Inputs(5, 0);
269 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
270 }
271 BASIC_BLOCK(3, 2)
272 {
273 INST(9, Opcode::And).u64().Inputs(4, 5);
274 INST(10, Opcode::Add).u64().Inputs(9, 4);
275 }
276 BASIC_BLOCK(4, -1)
277 {
278 INST(11, Opcode::Return).u64().Inputs(4);
279 }
280 }
281
282 auto expected_graph = CreateEmptyGraph();
283 GRAPH(expected_graph)
284 {
285 PARAMETER(0, 0).u64();
286 PARAMETER(1, 1).u64();
287 PARAMETER(2, 2).u64();
288 BASIC_BLOCK(5, 2, 4)
289 {
290 INST(12, Opcode::Sub).u64().Inputs(1, 2);
291 INST(13, Opcode::Compare).CC(CC_EQ).b().Inputs(12, 0);
292 INST(14, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(13);
293 }
294 BASIC_BLOCK(2, 2, 4)
295 {
296 INST(3, Opcode::Phi).u64().Inputs({{5, 12}, {2, 5}});
297 INST(4, Opcode::Phi).u64().Inputs({{5, 2}, {2, 10}});
298 INST(9, Opcode::And).u64().Inputs(4, 3);
299 INST(10, Opcode::Add).u64().Inputs(9, 4);
300 INST(5, Opcode::Sub).u64().Inputs(3, 2);
301 INST(6, Opcode::SafePoint).Inputs(0, 3, 10).SrcVregs({0, 1, 2});
302 INST(7, Opcode::Compare).CC(CC_EQ).b().Inputs(5, 0);
303 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
304 }
305 BASIC_BLOCK(4, -1)
306 {
307 INST(16, Opcode::Phi).u64().Inputs({{5, 2}, {2, 10}});
308 INST(11, Opcode::Return).u64().Inputs(16);
309 }
310 }
311
312 EXPECT_TRUE(GetGraph()->RunPass<LoopPeeling>());
313 // TODO(a.popov): remove these calls, see todo in LoopPeeling pass constructor
314 GetGraph()->RunPass<Cleanup>();
315 EXPECT_TRUE(GraphComparator().Compare(GetGraph(), expected_graph));
316 }
317
318 /*
319 * [0]
320 * |
321 * v
322 * /--------->[2]------------\
323 * | | |
324 * | v |
325 * | /---->[3]-----\ [6]
326 * | | | | |
327 * | | v v |
328 * | \-----[4] [5] [exit]
329 * | |
330 * | |
331 * \------------------/
332 *
333 * Transform to:
334 *
335 * [0]
336 * |
337 * v
338 * /--------->[2]-------------------------\
339 * | | |
340 * | v [6]
341 * | [pre-loop]---------\ |
342 * | | | v
343 * | v | [exit]
344 * | /---->[3] |
345 * | | | |
346 * | | v |
347 * | | [4] |
348 * | | | |
349 * | | v v
350 * | \--[loop-exit]-->[loop-outer]
351 * | |
352 * | v
353 * \-------------------------[5]
354 *
355 */
TEST_F(LoopPeelingTest,InnerLoop)356 TEST_F(LoopPeelingTest, InnerLoop)
357 {
358 GRAPH(GetGraph())
359 {
360 PARAMETER(0, 0).u64(); // count
361 PARAMETER(1, 1).u64(); // i
362 CONSTANT(2, 100);
363 CONSTANT(3, 1);
364 BASIC_BLOCK(2, 3, 6)
365 {
366 INST(4, Opcode::Phi).u64().Inputs(0, 8); // count
367 INST(5, Opcode::Phi).u64().Inputs(1, 14); // i
368 INST(6, Opcode::Compare).CC(CC_LT).b().Inputs(5, 2); // while i < 100
369 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
370 }
371 BASIC_BLOCK(3, 4, 5)
372 {
373 INST(8, Opcode::Phi).u64().Inputs(4, 12); // count
374 INST(9, Opcode::Phi).u64().Inputs(5, 13); // j = i
375 INST(10, Opcode::Compare).CC(CC_LT).b().Inputs(9, 2); // while j < 100
376 INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
377 }
378 BASIC_BLOCK(4, 3)
379 {
380 INST(12, Opcode::Add).u64().Inputs(8, 3); // j++
381 INST(13, Opcode::Add).u64().Inputs(9, 3); // count++
382 }
383 BASIC_BLOCK(5, 2)
384 {
385 INST(14, Opcode::Add).u64().Inputs(5, 3); // i++
386 }
387 BASIC_BLOCK(6, -1)
388 {
389 INST(15, Opcode::Return).u64().Inputs(4); // return count
390 }
391 }
392
393 auto expected_graph = CreateEmptyGraph();
394 GRAPH(expected_graph)
395 {
396 PARAMETER(0, 0).u64();
397 PARAMETER(1, 1).u64();
398 CONSTANT(2, 100);
399 CONSTANT(3, 1);
400 BASIC_BLOCK(2, 7, 6)
401 {
402 INST(4, Opcode::Phi).u64().Inputs(0, 18);
403 INST(5, Opcode::Phi).u64().Inputs(1, 14);
404 INST(6, Opcode::Compare).CC(CC_LT).b().Inputs(5, 2);
405 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
406 }
407 BASIC_BLOCK(7, 3, 5)
408 {
409 INST(16, Opcode::Compare).CC(CC_LT).b().Inputs(5, 2);
410 INST(17, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(16);
411 }
412 BASIC_BLOCK(3, 3, 5)
413 {
414 INST(8, Opcode::Phi).u64().Inputs(4, 12);
415 INST(9, Opcode::Phi).u64().Inputs(5, 13);
416 INST(12, Opcode::Add).u64().Inputs(8, 3);
417 INST(13, Opcode::Add).u64().Inputs(9, 3);
418 INST(10, Opcode::Compare).CC(CC_LT).b().Inputs(13, 2);
419 INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
420 }
421
422 BASIC_BLOCK(5, 2)
423 {
424 INST(18, Opcode::Phi).u64().Inputs({{7, 4}, {3, 12}});
425 INST(14, Opcode::Add).u64().Inputs(5, 3);
426 }
427 BASIC_BLOCK(6, -1)
428 {
429 INST(15, Opcode::Return).u64().Inputs(4);
430 }
431 }
432
433 EXPECT_TRUE(GetGraph()->RunPass<LoopPeeling>());
434 GetGraph()->RunPass<Cleanup>();
435 EXPECT_TRUE(GraphComparator().Compare(GetGraph(), expected_graph));
436 }
437
438 /*
439 * [0]
440 * |
441 * v
442 * /------>[2]------\
443 * | | |
444 * | [3] |
445 * | / \ |
446 * | v v v
447 * | [4] [5] [7]
448 * | \ / |
449 * \-------[6] [exit]
450 *
451 * Transform to:
452 *
453 * [0]
454 * |
455 * v
456 * [pre-loop]---------\
457 * | |
458 * v |
459 * /------>[2] |
460 * | | |
461 * | [3] |
462 * | / \ |
463 * | v v |
464 * | [4] [5] |
465 * | \ / |
466 * | [6] |
467 * | | v
468 * \---[loop-exit]-->[loop-outer]
469 * |
470 * [7]
471 * |
472 * [exit]
473 */
TEST_F(LoopPeelingTest,LoopWithBranch)474 TEST_F(LoopPeelingTest, LoopWithBranch)
475 {
476 GRAPH(GetGraph())
477 {
478 PARAMETER(0, 0).b();
479 PARAMETER(1, 1).u64();
480 CONSTANT(2, 2);
481 BASIC_BLOCK(2, 3, 7)
482 {
483 INST(3, Opcode::Phi).Inputs(1, 8).u64();
484 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(0);
485 }
486 BASIC_BLOCK(3, 4, 5)
487 {
488 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(0);
489 }
490 BASIC_BLOCK(4, 6)
491 {
492 INST(6, Opcode::Add).Inputs(3, 2).u64();
493 }
494 BASIC_BLOCK(5, 6)
495 {
496 INST(7, Opcode::Mul).Inputs(3, 2).u64();
497 }
498 BASIC_BLOCK(6, 2)
499 {
500 INST(8, Opcode::Phi).Inputs(6, 7).u64();
501 INST(11, Opcode::SaveState).NoVregs();
502 INST(9, Opcode::CallStatic).v0id().InputsAutoType(11);
503 }
504 BASIC_BLOCK(7, -1)
505 {
506 INST(10, Opcode::Return).Inputs(3).u64();
507 }
508 }
509
510 auto expected_graph = CreateEmptyGraph();
511 GRAPH(expected_graph)
512 {
513 PARAMETER(0, 0).b();
514 PARAMETER(1, 1).u64();
515 CONSTANT(2, 2);
516 BASIC_BLOCK(8, 3, 7)
517 {
518 INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(0);
519 }
520 BASIC_BLOCK(3, 4, 5)
521 {
522 INST(3, Opcode::Phi).Inputs(1, 8).u64();
523 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(0);
524 }
525 BASIC_BLOCK(4, 6)
526 {
527 INST(6, Opcode::Add).Inputs(3, 2).u64();
528 }
529 BASIC_BLOCK(5, 6)
530 {
531 INST(7, Opcode::Mul).Inputs(3, 2).u64();
532 }
533 BASIC_BLOCK(6, 3, 7)
534 {
535 INST(8, Opcode::Phi).Inputs(6, 7).u64();
536 INST(13, Opcode::SaveState).NoVregs();
537 INST(9, Opcode::CallStatic).v0id().InputsAutoType(13);
538 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(0);
539 }
540 BASIC_BLOCK(7, -1)
541 {
542 INST(12, Opcode::Phi).Inputs({{8, 1}, {6, 8}}).u64();
543 INST(10, Opcode::Return).Inputs(12).u64();
544 }
545 }
546
547 EXPECT_TRUE(GetGraph()->RunPass<LoopPeeling>());
548 GetGraph()->RunPass<Cleanup>();
549 EXPECT_TRUE(GraphComparator().Compare(GetGraph(), expected_graph));
550 }
551
552 /*
553 * [0]
554 * |
555 * v
556 * --/---->[2]-----\
557 * | | | |
558 * | | v v
559 * | \-----[3] [4]
560 * | | |
561 * \-------[5] [exit]
562 *
563 * NotApplied
564 */
TEST_F(LoopPeelingTest,TwoBackEdges)565 TEST_F(LoopPeelingTest, TwoBackEdges)
566 {
567 BuildGraphTwoBackEdges(GetGraph());
568 auto graph = CreateEmptyGraph();
569 BuildGraphTwoBackEdges(graph);
570
571 EXPECT_FALSE(GetGraph()->RunPass<LoopPeeling>());
572 EXPECT_TRUE(GraphComparator().Compare(GetGraph(), graph));
573 }
574
575 /*
576 * [0]
577 * |
578 * v
579 * /------>[2]
580 * | |
581 * | v
582 * | [3]--->[5]
583 * | | |
584 * \-------[4] [exit]
585 *
586 * NotApplied
587 */
TEST_F(LoopPeelingTest,NotHeaderExit)588 TEST_F(LoopPeelingTest, NotHeaderExit)
589 {
590 BuildGraphNotHeaderExit(GetGraph());
591 auto graph = CreateEmptyGraph();
592 BuildGraphNotHeaderExit(graph);
593
594 EXPECT_FALSE(GetGraph()->RunPass<LoopPeeling>());
595 EXPECT_TRUE(GraphComparator().Compare(GetGraph(), graph));
596 }
597
598 /*
599 * [0]
600 * |
601 * v
602 * /---->[2]-----\
603 * | | |
604 * | v v
605 * \-----[3]--->[4]
606 * |
607 * v
608 * [exit]
609 *
610 * NotApplied
611 */
TEST_F(LoopPeelingTest,HeaderAndBackEdgeExit)612 TEST_F(LoopPeelingTest, HeaderAndBackEdgeExit)
613 {
614 BuildGraphHeaderAndBackEdgeExit(GetGraph());
615 auto graph = CreateEmptyGraph();
616 BuildGraphHeaderAndBackEdgeExit(graph);
617
618 EXPECT_FALSE(GetGraph()->RunPass<LoopPeeling>());
619 EXPECT_TRUE(GraphComparator().Compare(GetGraph(), graph));
620 }
621
622 /*
623 * [0]
624 * |
625 * v
626 * /------>[2]----\
627 * | | |
628 * | v v
629 * | [3]--->[5]
630 * | | |
631 * \-------[4] [exit]
632 *
633 * NotApplied
634 */
TEST_F(LoopPeelingTest,MultiExit)635 TEST_F(LoopPeelingTest, MultiExit)
636 {
637 BuildGraphMultiExit(GetGraph());
638 auto graph = CreateEmptyGraph();
639 BuildGraphMultiExit(graph);
640
641 EXPECT_FALSE(GetGraph()->RunPass<LoopPeeling>());
642 EXPECT_TRUE(GraphComparator().Compare(GetGraph(), graph));
643 }
644
TEST_F(LoopPeelingTest,RemoveDeadPhi)645 TEST_F(LoopPeelingTest, RemoveDeadPhi)
646 {
647 GRAPH(GetGraph())
648 {
649 PARAMETER(0, 0).u64();
650 PARAMETER(1, 1).u64();
651 PARAMETER(2, 2).u64();
652 BASIC_BLOCK(2, 3, 4)
653 {
654 INST(3, Opcode::Phi).u64().Inputs(0, 1);
655 INST(4, Opcode::Phi).u64().Inputs(2, 10);
656 INST(6, Opcode::SafePoint).Inputs(3, 4).SrcVregs({0, 1});
657 INST(7, Opcode::Compare).CC(CC_EQ).b().Inputs(4, 0);
658 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
659 }
660 BASIC_BLOCK(3, 2)
661 {
662 INST(10, Opcode::Add).u64().Inputs(4, 2);
663 }
664 BASIC_BLOCK(4, -1)
665 {
666 INST(11, Opcode::Return).u64().Inputs(4);
667 }
668 }
669
670 EXPECT_TRUE(GetGraph()->RunPass<LoopPeeling>());
671 EXPECT_FALSE(INS(3).HasUsers());
672 EXPECT_EQ(INS(3).GetBasicBlock(), nullptr);
673 }
674
TEST_F(LoopPeelingTest,SingleBlockLoop)675 TEST_F(LoopPeelingTest, SingleBlockLoop)
676 {
677 GRAPH(GetGraph())
678 {
679 PARAMETER(0, 0).u64();
680 PARAMETER(1, 1).u64();
681 PARAMETER(2, 2).u64();
682
683 BASIC_BLOCK(2, 2, 3)
684 {
685 INST(3, Opcode::Phi).u64().Inputs(0, 6);
686 INST(4, Opcode::SafePoint).Inputs(3).SrcVregs({0});
687 INST(5, Opcode::Add).u64().Inputs(1, 3);
688 INST(6, Opcode::Add).u64().Inputs(0, 3);
689 INST(7, Opcode::Compare).CC(CC_EQ).b().Inputs(6, 2);
690 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
691 }
692
693 BASIC_BLOCK(3, -1)
694 {
695 INST(9, Opcode::Return).u64().Inputs(5);
696 }
697 }
698
699 auto expected_graph = CreateEmptyGraph();
700 GRAPH(expected_graph)
701 {
702 PARAMETER(0, 0).u64();
703 PARAMETER(1, 1).u64();
704 PARAMETER(2, 2).u64();
705
706 BASIC_BLOCK(6, 2, 7)
707 {
708 INST(12, Opcode::Add).u64().Inputs(1, 0);
709 INST(13, Opcode::Add).u64().Inputs(0, 0);
710 INST(14, Opcode::Compare).CC(CC_EQ).b().Inputs(13, 2);
711 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
712 }
713
714 BASIC_BLOCK(2, 2, 7)
715 {
716 INST(3, Opcode::Phi).u64().Inputs(13, 6);
717 INST(4, Opcode::SafePoint).Inputs(3).SrcVregs({0});
718 INST(5, Opcode::Add).u64().Inputs(1, 3);
719 INST(6, Opcode::Add).u64().Inputs(0, 3);
720 INST(7, Opcode::Compare).CC(CC_EQ).b().Inputs(6, 2);
721 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
722 }
723
724 BASIC_BLOCK(7, -1)
725 {
726 INST(17, Opcode::Phi).u64().Inputs({{2, 5}, {6, 12}});
727 INST(9, Opcode::Return).u64().Inputs(17);
728 }
729 }
730
731 EXPECT_TRUE(GetGraph()->RunPass<LoopPeeling>());
732 GetGraph()->RunPass<Cleanup>();
733 EXPECT_TRUE(GraphComparator().Compare(GetGraph(), expected_graph));
734 }
735
736 // TODO (apopov) Fix GraphComparator and enable test
TEST_F(LoopPeelingTest,DISABLED_RepeatedCloneableInputs)737 TEST_F(LoopPeelingTest, DISABLED_RepeatedCloneableInputs)
738 {
739 GRAPH(GetGraph())
740 {
741 PARAMETER(0, 0).ref();
742 PARAMETER(1, 1).u32();
743 BASIC_BLOCK(2, 3, 4)
744 {
745 INST(2, Opcode::LoadObject).u32().Inputs(0);
746 INST(3, Opcode::Sub).u32().Inputs(2, 1);
747 INST(4, Opcode::Compare).CC(CC_EQ).b().Inputs(3, 1);
748 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
749 }
750 BASIC_BLOCK(3, 2)
751 {
752 INST(6, Opcode::SaveState).Inputs(1, 2, 2, 3).SrcVregs({0, 1, 2, 3});
753 }
754 BASIC_BLOCK(4, -1)
755 {
756 INST(7, Opcode::Return).u32().Inputs(2);
757 }
758 }
759
760 auto expected_graph = CreateEmptyGraph();
761 GRAPH(expected_graph)
762 {
763 PARAMETER(0, 0).ref();
764 PARAMETER(1, 1).u32();
765 BASIC_BLOCK(6, 2, 7)
766 {
767 INST(9, Opcode::LoadObject).u32().Inputs(0);
768 INST(10, Opcode::Sub).u32().Inputs(9, 1);
769 INST(11, Opcode::Compare).CC(CC_EQ).b().Inputs(10, 1);
770 INST(12, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(11);
771 }
772 BASIC_BLOCK(2, 2, 7)
773 {
774 INST(13, Opcode::Phi).u32().Inputs(9, 2);
775 INST(15, Opcode::Phi).u32().Inputs(10, 3);
776 INST(6, Opcode::SaveState).Inputs(1, 13, 13, 15).SrcVregs({0, 1, 2, 3});
777 INST(2, Opcode::LoadObject).u32().Inputs(0);
778 INST(3, Opcode::Sub).u32().Inputs(2, 1);
779 INST(4, Opcode::Compare).CC(CC_EQ).b().Inputs(3, 1);
780 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
781 }
782 BASIC_BLOCK(7, -1)
783 {
784 INST(14, Opcode::Phi).u32().Inputs({{2, 2}, {6, 9}});
785 INST(7, Opcode::Return).u32().Inputs(14);
786 }
787 }
788 EXPECT_TRUE(GetGraph()->RunPass<LoopPeeling>());
789 EXPECT_TRUE(GraphComparator().Compare(GetGraph(), expected_graph));
790 }
791
TEST_F(LoopPeelingTest,InfiniteLoop)792 TEST_F(LoopPeelingTest, InfiniteLoop)
793 {
794 auto graph = CreateEmptyGraph();
795 GRAPH(graph)
796 {
797 PARAMETER(0, 0).s32();
798 CONSTANT(1, 1);
799
800 BASIC_BLOCK(2, 2)
801 {
802 INST(2, Opcode::Phi).s32().Inputs(0, 3);
803 INST(3, Opcode::Add).s32().Inputs(2, 1);
804 }
805 }
806 EXPECT_FALSE(graph->RunPass<LoopPeeling>());
807 }
808
TEST_F(LoopPeelingTest,MultiSafePointsLoop)809 TEST_F(LoopPeelingTest, MultiSafePointsLoop)
810 {
811 GRAPH(GetGraph())
812 {
813 PARAMETER(0, 0).u64();
814 PARAMETER(1, 1).u64();
815 PARAMETER(2, 2).u64();
816 BASIC_BLOCK(2, 3, 4)
817 {
818 INST(3, Opcode::Phi).u64().Inputs(1, 5);
819 INST(4, Opcode::Phi).u64().Inputs(2, 10);
820 INST(5, Opcode::Sub).u64().Inputs(3, 2);
821 INST(6, Opcode::SafePoint).Inputs(0, 5, 4).SrcVregs({0, 1, 2});
822 INST(7, Opcode::Compare).CC(CC_EQ).b().Inputs(5, 0);
823 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
824 }
825 BASIC_BLOCK(3, 2)
826 {
827 INST(9, Opcode::And).u64().Inputs(4, 5);
828 INST(10, Opcode::Add).u64().Inputs(9, 4);
829 INST(12, Opcode::SafePoint).Inputs(0, 5, 10).SrcVregs({0, 1, 2});
830 }
831 BASIC_BLOCK(4, -1)
832 {
833 INST(11, Opcode::Return).u64().Inputs(4);
834 }
835 }
836
837 auto expected_graph = CreateEmptyGraph();
838 GRAPH(expected_graph)
839 {
840 PARAMETER(0, 0).u64();
841 PARAMETER(1, 1).u64();
842 PARAMETER(2, 2).u64();
843 BASIC_BLOCK(5, 2, 4)
844 {
845 INST(13, Opcode::Sub).u64().Inputs(1, 2);
846 INST(14, Opcode::Compare).CC(CC_EQ).b().Inputs(13, 0);
847 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
848 }
849 BASIC_BLOCK(2, 2, 4)
850 {
851 INST(3, Opcode::Phi).u64().Inputs(13, 5);
852 INST(4, Opcode::Phi).u64().Inputs(2, 10);
853 INST(9, Opcode::And).u64().Inputs(4, 3);
854 INST(10, Opcode::Add).u64().Inputs(9, 4);
855 INST(12, Opcode::SafePoint).Inputs(0, 3, 10).SrcVregs({0, 1, 2});
856 INST(5, Opcode::Sub).u64().Inputs(3, 2);
857 INST(6, Opcode::SafePoint).Inputs(0, 5, 10).SrcVregs({0, 1, 2});
858 INST(7, Opcode::Compare).CC(CC_EQ).b().Inputs(5, 0);
859 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
860 }
861 BASIC_BLOCK(4, -1)
862 {
863 INST(16, Opcode::Phi).u64().Inputs({{2, 10}, {5, 2}});
864 INST(11, Opcode::Return).u64().Inputs(16);
865 }
866 }
867 EXPECT_TRUE(GetGraph()->RunPass<LoopPeeling>());
868 GetGraph()->RunPass<Cleanup>();
869 EXPECT_TRUE(GraphComparator().Compare(GetGraph(), expected_graph));
870 }
871
TEST_F(LoopPeelingTest,LoopWithInlinedCall)872 TEST_F(LoopPeelingTest, LoopWithInlinedCall)
873 {
874 GRAPH(GetGraph())
875 {
876 PARAMETER(0, 0).u32();
877 PARAMETER(1, 1).ref();
878
879 BASIC_BLOCK(2, 3, 4)
880 {
881 INST(3, Opcode::SaveState).Inputs().SrcVregs({});
882 INST(4, Opcode::CallStatic).v0id().Inlined().InputsAutoType(3);
883 INST(5, Opcode::IfImm).SrcType(DataType::UINT32).CC(CC_NE).Imm(0).Inputs(0);
884 }
885 BASIC_BLOCK(3, 2)
886 {
887 INST(6, Opcode::ReturnInlined).Inputs(3);
888 }
889 BASIC_BLOCK(4, -1)
890 {
891 INST(7, Opcode::SaveState).Inputs().SrcVregs({});
892 INST(8, Opcode::Throw).Inputs(1, 7);
893 }
894 }
895 INS(7).CastToSaveState()->SetCallerInst(static_cast<CallInst *>(&INS(4)));
896 ASSERT_FALSE(GetGraph()->RunPass<LoopPeeling>());
897 }
898
899 } // namespace panda::compiler
900