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 #include "optimizer/optimizations/code_sink.h"
19
20 namespace panda::compiler {
21 class CodeSinkTest : public GraphTest {
22 };
23
TEST_F(CodeSinkTest,OperationPropagation)24 TEST_F(CodeSinkTest, OperationPropagation)
25 {
26 GRAPH(GetGraph())
27 {
28 PARAMETER(0, 0).s64();
29 PARAMETER(1, 1).s64();
30 PARAMETER(2, 2).s64();
31 CONSTANT(3, 0x0).s64();
32 BASIC_BLOCK(2, 3, 4)
33 {
34 INST(5, Opcode::Add).s64().Inputs(1, 2);
35 INST(6, Opcode::Compare).b().CC(CC_NE).Inputs(0, 3);
36 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
37 }
38 BASIC_BLOCK(4, -1)
39 {
40 INST(9, Opcode::Return).s64().Inputs(5);
41 }
42 BASIC_BLOCK(3, -1)
43 {
44 INST(11, Opcode::Return).s64().Inputs(3);
45 }
46 }
47 Graph *sunk_graph = CreateEmptyGraph();
48 GRAPH(sunk_graph)
49 {
50 PARAMETER(0, 0).s64();
51 PARAMETER(1, 1).s64();
52 PARAMETER(2, 2).s64();
53 CONSTANT(3, 0x0).s64();
54 BASIC_BLOCK(2, 3, 4)
55 {
56 INST(6, Opcode::Compare).b().CC(CC_NE).Inputs(0, 3);
57 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
58 }
59 BASIC_BLOCK(4, -1)
60 {
61 INST(5, Opcode::Add).s64().Inputs(1, 2);
62 INST(9, Opcode::Return).s64().Inputs(5);
63 }
64 BASIC_BLOCK(3, -1)
65 {
66 INST(11, Opcode::Return).s64().Inputs(3);
67 }
68 }
69
70 ASSERT_TRUE(GetGraph()->RunPass<CodeSink>());
71 GraphChecker(GetGraph()).Check();
72 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), sunk_graph));
73 }
74
75 /**
76 * Move load but the NullCheck is still on its place:
77 * exception should be thrown where it was initially.
78 */
79 // TODO(Kudriashov Evgenii) enable the test after fixing CodeSink
TEST_F(CodeSinkTest,DISABLED_LoadWithOperationPropagation)80 TEST_F(CodeSinkTest, DISABLED_LoadWithOperationPropagation)
81 {
82 GRAPH(GetGraph())
83 {
84 PARAMETER(0, 0).s64();
85 PARAMETER(1, 1).s64();
86 PARAMETER(2, 2).ref();
87 CONSTANT(3, 0x0).s64();
88 BASIC_BLOCK(2, 3, 4)
89 {
90 INST(4, Opcode::SaveState).Inputs(3, 2).SrcVregs({0, 4});
91 INST(5, Opcode::NullCheck).ref().Inputs(2, 4);
92 INST(6, Opcode::LoadObject).s64().Inputs(5).TypeId(176);
93 INST(7, Opcode::Add).s64().Inputs(6, 1);
94 INST(8, Opcode::Compare).b().CC(CC_NE).Inputs(0, 3);
95 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
96 }
97 BASIC_BLOCK(4, -1)
98 {
99 INST(11, Opcode::Return).s64().Inputs(7);
100 }
101 BASIC_BLOCK(3, -1)
102 {
103 INST(13, Opcode::Return).s64().Inputs(3);
104 }
105 }
106 Graph *sunk_graph = CreateEmptyGraph();
107 GRAPH(sunk_graph)
108 {
109 PARAMETER(0, 0).s64();
110 PARAMETER(1, 1).s64();
111 PARAMETER(2, 2).ref();
112 CONSTANT(3, 0x0).s64();
113 BASIC_BLOCK(2, 3, 4)
114 {
115 INST(4, Opcode::SaveState).Inputs(3, 2).SrcVregs({0, 4});
116 INST(5, Opcode::NullCheck).ref().Inputs(2, 4);
117 INST(8, Opcode::Compare).b().CC(CC_NE).Inputs(0, 3);
118 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
119 }
120 BASIC_BLOCK(4, -1)
121 {
122 INST(6, Opcode::LoadObject).s64().Inputs(5).TypeId(176);
123 INST(7, Opcode::Add).s64().Inputs(6, 1);
124 INST(11, Opcode::Return).s64().Inputs(7);
125 }
126 BASIC_BLOCK(3, -1)
127 {
128 INST(13, Opcode::Return).s64().Inputs(3);
129 }
130 }
131
132 ASSERT_TRUE(GetGraph()->RunPass<CodeSink>());
133 GraphChecker(GetGraph()).Check();
134 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), sunk_graph));
135 }
136
137 /**
138 * Do not move anything
139 */
TEST_F(CodeSinkTest,NoDomination)140 TEST_F(CodeSinkTest, NoDomination)
141 {
142 std::vector<Graph *> equal_graphs = {GetGraph(), CreateEmptyGraph()};
143 for (auto graph : equal_graphs) {
144 GRAPH(graph)
145 {
146 PARAMETER(0, 0).s64();
147 PARAMETER(1, 1).s64();
148 PARAMETER(2, 2).s64();
149 CONSTANT(3, 0x0).s64();
150 BASIC_BLOCK(2, 3, 4)
151 {
152 INST(5, Opcode::Add).s64().Inputs(1, 2);
153 INST(6, Opcode::Compare).b().CC(CC_NE).Inputs(0, 3);
154 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
155 }
156 BASIC_BLOCK(4, -1)
157 {
158 INST(9, Opcode::Return).s64().Inputs(5);
159 }
160 BASIC_BLOCK(3, -1)
161 {
162 INST(11, Opcode::Return).s64().Inputs(5);
163 }
164 }
165 }
166 equal_graphs[0]->RunPass<CodeSink>();
167 GraphChecker(equal_graphs[0]).Check();
168 ASSERT_TRUE(GraphComparator().Compare(equal_graphs[0], equal_graphs[1]));
169 }
170
171 /**
172 * Do not sink loads that may alias further stores in the block
173 */
TEST_F(CodeSinkTest,LoadStoreAliasing)174 TEST_F(CodeSinkTest, LoadStoreAliasing)
175 {
176 std::vector<Graph *> equal_graphs = {GetGraph(), CreateEmptyGraph()};
177 for (auto graph : equal_graphs) {
178 GRAPH(graph)
179 {
180 PARAMETER(0, 0).ref();
181 PARAMETER(1, 1).ref();
182 PARAMETER(2, 2).s64();
183 CONSTANT(3, 0x0).s64();
184 BASIC_BLOCK(2, 3, 4)
185 {
186 INST(6, Opcode::LoadObject).s64().Inputs(0).TypeId(243);
187 INST(9, Opcode::StoreObject).s64().Inputs(1, 2).TypeId(243);
188 INST(10, Opcode::Compare).b().CC(CC_NE).Inputs(2, 3);
189 INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
190 }
191 BASIC_BLOCK(4, -1)
192 {
193 INST(13, Opcode::Return).s64().Inputs(6);
194 }
195 BASIC_BLOCK(3, -1)
196 {
197 INST(15, Opcode::Return).s64().Inputs(3);
198 }
199 }
200 }
201 equal_graphs[0]->RunPass<CodeSink>();
202 GraphChecker(equal_graphs[0]).Check();
203 ASSERT_TRUE(GraphComparator().Compare(equal_graphs[0], equal_graphs[1]));
204 }
205
TEST_F(CodeSinkTest,LoopSinking)206 TEST_F(CodeSinkTest, LoopSinking)
207 {
208 GRAPH(GetGraph())
209 {
210 PARAMETER(0, 0).s32();
211 PARAMETER(1, 1).s64();
212 PARAMETER(2, 2).ref();
213 CONSTANT(3, 0x1).s64();
214 CONSTANT(4, 0x0).s64();
215 CONSTANT(5, 0x42).s64();
216 BASIC_BLOCK(2, 3)
217 {
218 // Do not sink into loop
219 INST(6, Opcode::Add).s64().Inputs(1, 5);
220 }
221 BASIC_BLOCK(3, 3, 4)
222 {
223 INST(10, Opcode::Phi).s64().Inputs({{2, 4}, {3, 22}});
224 INST(20, Opcode::LoadArray).s64().Inputs(2, 10);
225 INST(21, Opcode::Add).s64().Inputs(20, 6);
226 INST(22, Opcode::Add).s64().Inputs(21, 10);
227 INST(23, Opcode::Add).s32().Inputs(10, 3);
228 // Sink out of loop
229 INST(26, Opcode::Add).s64().Inputs(21, 22);
230 INST(24, Opcode::Compare).b().CC(CC_LT).Inputs(23, 0);
231 INST(25, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(24);
232 }
233 BASIC_BLOCK(4, -1)
234 {
235 INST(27, Opcode::Return).s64().Inputs(26);
236 }
237 }
238 Graph *sunk_graph = CreateEmptyGraph();
239 GRAPH(sunk_graph)
240 {
241 PARAMETER(0, 0).s32();
242 PARAMETER(1, 1).s64();
243 PARAMETER(2, 2).ref();
244 CONSTANT(3, 0x1).s64();
245 CONSTANT(4, 0x0).s64();
246 CONSTANT(5, 0x42).s64();
247 BASIC_BLOCK(2, 3)
248 {
249 INST(6, Opcode::Add).s64().Inputs(1, 5);
250 }
251 BASIC_BLOCK(3, 3, 4)
252 {
253 INST(10, Opcode::Phi).s64().Inputs({{2, 4}, {3, 22}});
254 INST(20, Opcode::LoadArray).s64().Inputs(2, 10);
255 INST(21, Opcode::Add).s64().Inputs(20, 6);
256 INST(22, Opcode::Add).s64().Inputs(21, 10);
257 INST(23, Opcode::Add).s32().Inputs(10, 3);
258 INST(24, Opcode::Compare).b().CC(CC_LT).Inputs(23, 0);
259 INST(25, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(24);
260 }
261 BASIC_BLOCK(4, -1)
262 {
263 INST(26, Opcode::Add).s64().Inputs(21, 22);
264 INST(27, Opcode::Return).s64().Inputs(26);
265 }
266 }
267
268 ASSERT_TRUE(GetGraph()->RunPass<CodeSink>());
269 GraphChecker(GetGraph()).Check();
270 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), sunk_graph));
271 }
272
273 /**
274 * Sink instruction over critical edge
275 */
TEST_F(CodeSinkTest,CriticalEdgeSinking)276 TEST_F(CodeSinkTest, CriticalEdgeSinking)
277 {
278 GRAPH(GetGraph())
279 {
280 PARAMETER(0, 0).ref();
281 PARAMETER(1, 1).ref();
282 PARAMETER(2, 2).s64();
283 PARAMETER(3, 3).s64();
284 CONSTANT(4, 0x0).s64();
285 BASIC_BLOCK(2, 3, 4)
286 {
287 INST(5, Opcode::Add).s32().Inputs(3, 2);
288 INST(8, Opcode::LoadObject).s64().Inputs(0).TypeId(243);
289 INST(9, Opcode::Compare).b().CC(CC_NE).Inputs(8, 4);
290 INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(9);
291 }
292 BASIC_BLOCK(4, 3)
293 {
294 INST(13, Opcode::StoreObject).s64().Inputs(1, 8).TypeId(243);
295 }
296 BASIC_BLOCK(3, -1)
297 {
298 INST(15, Opcode::Return).s32().Inputs(5);
299 }
300 }
301 Graph *sunk_graph = CreateEmptyGraph();
302 GRAPH(sunk_graph)
303 {
304 PARAMETER(0, 0).ref();
305 PARAMETER(1, 1).ref();
306 PARAMETER(2, 2).s64();
307 PARAMETER(3, 3).s64();
308 CONSTANT(4, 0x0).s64();
309 BASIC_BLOCK(2, 3, 4)
310 {
311 INST(8, Opcode::LoadObject).s64().Inputs(0).TypeId(243);
312 INST(9, Opcode::Compare).b().CC(CC_NE).Inputs(8, 4);
313 INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(9);
314 }
315 BASIC_BLOCK(4, 3)
316 {
317 INST(13, Opcode::StoreObject).s64().Inputs(1, 8).TypeId(243);
318 }
319 BASIC_BLOCK(3, -1)
320 {
321 INST(5, Opcode::Add).s32().Inputs(3, 2);
322 INST(15, Opcode::Return).s32().Inputs(5);
323 }
324 }
325
326 ASSERT_TRUE(GetGraph()->RunPass<CodeSink>());
327 GraphChecker(GetGraph()).Check();
328 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), sunk_graph));
329 }
330
331 /**
332 * Do not sink loads over monitor
333 */
TEST_F(CodeSinkTest,LoadOverMonitor)334 TEST_F(CodeSinkTest, LoadOverMonitor)
335 {
336 GRAPH(GetGraph())
337 {
338 PARAMETER(0, 0).ref();
339 PARAMETER(1, 1).s64();
340 PARAMETER(2, 2).ref();
341 CONSTANT(3, 0x0).s64();
342 BASIC_BLOCK(2, 3, 4)
343 {
344 INST(4, Opcode::SaveState).Inputs(2, 1, 0, 3).SrcVregs({4, 3, 2, 0});
345 INST(5, Opcode::NullCheck).ref().Inputs(2, 4);
346 // Do not move load
347 INST(6, Opcode::LoadObject).s64().Inputs(5).TypeId(243);
348 // Safely move arithmetic operations
349 INST(7, Opcode::Add).s64().Inputs(6, 1);
350 INST(15, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({0, 1, 2});
351 INST(8, Opcode::Monitor).v0id().Entry().Inputs(0, 15);
352 INST(9, Opcode::Compare).b().CC(CC_NE).Inputs(1, 3);
353 INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(9);
354 }
355 BASIC_BLOCK(4, -1)
356 {
357 INST(16, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({0, 1, 2});
358 INST(11, Opcode::Monitor).v0id().Exit().Inputs(0, 16);
359 INST(12, Opcode::Return).s64().Inputs(7);
360 }
361 BASIC_BLOCK(3, -1)
362 {
363 INST(17, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({0, 1, 2});
364 INST(13, Opcode::Monitor).v0id().Exit().Inputs(0, 17);
365 INST(14, Opcode::Return).s64().Inputs(3);
366 }
367 }
368 Graph *sunk_graph = CreateEmptyGraph();
369 GRAPH(sunk_graph)
370 {
371 PARAMETER(0, 0).ref();
372 PARAMETER(1, 1).s64();
373 PARAMETER(2, 2).ref();
374 CONSTANT(3, 0x0).s64();
375 BASIC_BLOCK(2, 3, 4)
376 {
377 INST(4, Opcode::SaveState).Inputs(2, 1, 0, 3).SrcVregs({4, 3, 2, 0});
378 INST(5, Opcode::NullCheck).ref().Inputs(2, 4);
379 INST(6, Opcode::LoadObject).s64().Inputs(5).TypeId(243);
380 INST(15, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({0, 1, 2});
381 INST(8, Opcode::Monitor).v0id().Entry().Inputs(0, 15);
382 INST(9, Opcode::Compare).b().CC(CC_NE).Inputs(1, 3);
383 INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(9);
384 }
385 BASIC_BLOCK(4, -1)
386 {
387 INST(7, Opcode::Add).s64().Inputs(6, 1);
388 INST(16, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({0, 1, 2});
389 INST(11, Opcode::Monitor).v0id().Exit().Inputs(0, 16);
390 INST(12, Opcode::Return).s64().Inputs(7);
391 }
392 BASIC_BLOCK(3, -1)
393 {
394 INST(17, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({0, 1, 2});
395 INST(13, Opcode::Monitor).v0id().Exit().Inputs(0, 17);
396 INST(14, Opcode::Return).s64().Inputs(3);
397 }
398 }
399
400 ASSERT_TRUE(GetGraph()->RunPass<CodeSink>());
401 GraphChecker(GetGraph()).Check();
402 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), sunk_graph));
403 }
404
405 /**
406 * Reordering of Normal Load and subsequent Volatile Load is allowed
407 */
408 // TODO(Kudriashov Evgenii) enable the test after fixing CodeSink
TEST_F(CodeSinkTest,DISABLED_LoadOverVolatileLoad)409 TEST_F(CodeSinkTest, DISABLED_LoadOverVolatileLoad)
410 {
411 GRAPH(GetGraph())
412 {
413 PARAMETER(0, 0).s64();
414 PARAMETER(2, 2).ref();
415 CONSTANT(3, 0x0).s64();
416 BASIC_BLOCK(2, 3, 4)
417 {
418 INST(4, Opcode::SaveState).Inputs(2).SrcVregs({0});
419 INST(5, Opcode::LoadAndInitClass).ref().Inputs(4).TypeId(0);
420 INST(6, Opcode::LoadObject).s64().Inputs(2).TypeId(176);
421 INST(7, Opcode::LoadStatic).s64().Inputs(5).Volatile().TypeId(103);
422 INST(8, Opcode::Compare).b().CC(CC_NE).Inputs(0, 7);
423 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
424 }
425 BASIC_BLOCK(4, -1)
426 {
427 INST(11, Opcode::Return).s64().Inputs(6);
428 }
429 BASIC_BLOCK(3, -1)
430 {
431 INST(13, Opcode::Return).s64().Inputs(3);
432 }
433 }
434 Graph *opt_graph = CreateEmptyGraph();
435 GRAPH(opt_graph)
436 {
437 PARAMETER(0, 0).s64();
438 PARAMETER(2, 2).ref();
439 CONSTANT(3, 0x0).s64();
440 BASIC_BLOCK(2, 3, 4)
441 {
442 INST(4, Opcode::SaveState).Inputs(2).SrcVregs({0});
443 INST(5, Opcode::LoadAndInitClass).ref().Inputs(4).TypeId(0);
444 INST(7, Opcode::LoadStatic).s64().Inputs(5).Volatile().TypeId(103);
445 INST(8, Opcode::Compare).b().CC(CC_NE).Inputs(0, 7);
446 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
447 }
448 BASIC_BLOCK(4, -1)
449 {
450 INST(6, Opcode::LoadObject).s64().Inputs(2).TypeId(176);
451 INST(11, Opcode::Return).s64().Inputs(6);
452 }
453 BASIC_BLOCK(3, -1)
454 {
455 INST(13, Opcode::Return).s64().Inputs(3);
456 }
457 }
458
459 ASSERT_TRUE(GetGraph()->RunPass<CodeSink>());
460 GraphChecker(GetGraph()).Check();
461 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), opt_graph));
462 }
463
464 /**
465 * /---[2]---\
466 * | |
467 * [3]<------[4]
468 * | |
469 * | [5]
470 * | |
471 * \---[6]---/
472 *
473 * Sink from BB 4 to BB 5
474 */
TEST_F(CodeSinkTest,IntermediateSinking)475 TEST_F(CodeSinkTest, IntermediateSinking)
476 {
477 GRAPH(GetGraph())
478 {
479 PARAMETER(0, 0).ref();
480 PARAMETER(1, 1).s64();
481 PARAMETER(2, 2).s64();
482 CONSTANT(4, 0x0).s64();
483 BASIC_BLOCK(2, 3, 4)
484 {
485 INST(3, Opcode::Compare).b().CC(CC_EQ).Inputs(1, 4);
486 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
487 }
488 BASIC_BLOCK(4, 5, 3)
489 {
490 INST(6, Opcode::Add).s32().Inputs(1, 2);
491 INST(7, Opcode::Compare).b().CC(CC_EQ).Inputs(2, 4);
492 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
493 }
494 BASIC_BLOCK(5, 6)
495 {
496 INST(10, Opcode::SaveState).Inputs(6, 2, 1, 0, 6).SrcVregs({5, 4, 3, 2, 1});
497 INST(11, Opcode::NullCheck).ref().Inputs(0, 10);
498 INST(12, Opcode::StoreObject).s32().Inputs(11, 6).TypeId(271);
499 }
500 BASIC_BLOCK(3, 6) {}
501 BASIC_BLOCK(6, -1)
502 {
503 INST(18, Opcode::Return).s32().Inputs(2);
504 }
505 }
506 Graph *sunk_graph = CreateEmptyGraph();
507 GRAPH(sunk_graph)
508 {
509 PARAMETER(0, 0).ref();
510 PARAMETER(1, 1).s64();
511 PARAMETER(2, 2).s64();
512 CONSTANT(4, 0x0).s64();
513 BASIC_BLOCK(2, 6, 4)
514 {
515 INST(3, Opcode::Compare).b().CC(CC_EQ).Inputs(1, 4);
516 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
517 }
518 BASIC_BLOCK(4, 5, 6)
519 {
520 INST(7, Opcode::Compare).b().CC(CC_EQ).Inputs(2, 4);
521 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
522 }
523 BASIC_BLOCK(5, 6)
524 {
525 INST(6, Opcode::Add).s32().Inputs(1, 2);
526 INST(10, Opcode::SaveState).Inputs(6, 2, 1, 0, 6).SrcVregs({5, 4, 3, 2, 1});
527 INST(11, Opcode::NullCheck).ref().Inputs(0, 10);
528 INST(12, Opcode::StoreObject).s32().Inputs(11, 6).TypeId(271);
529 }
530 BASIC_BLOCK(6, -1)
531 {
532 INST(18, Opcode::Return).s32().Inputs(2);
533 }
534 }
535
536 ASSERT_TRUE(GetGraph()->RunPass<CodeSink>());
537 ASSERT_TRUE(GetGraph()->RunPass<Cleanup>());
538
539 GraphChecker(GetGraph()).Check();
540 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), sunk_graph));
541 }
542
543 /**
544 * Do not sink object allocations
545 */
TEST_F(CodeSinkTest,Allocations)546 TEST_F(CodeSinkTest, Allocations)
547 {
548 std::vector<Graph *> equal_graphs = {GetGraph(), CreateEmptyGraph()};
549 for (auto graph : equal_graphs) {
550 GRAPH(graph)
551 {
552 PARAMETER(1, 1).s64();
553 CONSTANT(4, 0x0).s64();
554 BASIC_BLOCK(2, 3, 4)
555 {
556 INST(18, Opcode::SaveState).Inputs(1).SrcVregs({3});
557 INST(19, Opcode::LoadAndInitClass).TypeId(231).ref().Inputs(18);
558 INST(2, Opcode::NewObject).ref().TypeId(231).Inputs(19, 18);
559 INST(3, Opcode::Compare).b().CC(CC_GT).Inputs(1, 4);
560 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
561 }
562 BASIC_BLOCK(4, 5)
563 {
564 INST(8, Opcode::LoadObject).s64().Inputs(2).TypeId(243);
565 INST(11, Opcode::LoadObject).s64().Inputs(2).TypeId(257);
566 INST(12, Opcode::Add).s64().Inputs(11, 8);
567 }
568 BASIC_BLOCK(3, 5)
569 {
570 INST(14, Opcode::Neg).s64().Inputs(1);
571 }
572 BASIC_BLOCK(5, -1)
573 {
574 INST(16, Opcode::Phi).s64().Inputs({{4, 12}, {3, 14}});
575 INST(17, Opcode::Return).s64().Inputs(16);
576 }
577 }
578 }
579 equal_graphs[0]->RunPass<CodeSink>();
580 GraphChecker(equal_graphs[0]).Check();
581 ASSERT_TRUE(GraphComparator().Compare(equal_graphs[0], equal_graphs[1]));
582 }
583
584 /**
585 * Do not sink over PHI statement
586 */
TEST_F(CodeSinkTest,PhiUsers)587 TEST_F(CodeSinkTest, PhiUsers)
588 {
589 std::vector<Graph *> equal_graphs = {GetGraph(), CreateEmptyGraph()};
590 for (auto graph : equal_graphs) {
591 GRAPH(graph)
592 {
593 PARAMETER(0, 0).s64();
594 CONSTANT(5, 0x0).s64();
595 BASIC_BLOCK(2, 3, 4)
596 {
597 INST(12, Opcode::AddI).s64().Inputs(0).Imm(0x3);
598 INST(4, Opcode::Compare).b().CC(CC_GT).Inputs(0, 5);
599 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
600 }
601 BASIC_BLOCK(4, 3)
602 {
603 INST(8, Opcode::Neg).s64().Inputs(0);
604 }
605 BASIC_BLOCK(3, -1)
606 {
607 INST(9, Opcode::Phi).s64().Inputs({{2, 12}, {4, 8}});
608 INST(11, Opcode::Return).s64().Inputs(9);
609 }
610 }
611 }
612 equal_graphs[0]->RunPass<CodeSink>();
613 GraphChecker(equal_graphs[0]).Check();
614 ASSERT_TRUE(GraphComparator().Compare(equal_graphs[0], equal_graphs[1]));
615 }
616
617 /**
618 * Do not sink volatile loads because other paths might be broken because of it
619 */
TEST_F(CodeSinkTest,SinkableVolatileLoad)620 TEST_F(CodeSinkTest, SinkableVolatileLoad)
621 {
622 GRAPH(GetGraph())
623 {
624 PARAMETER(0, 0).s64();
625 PARAMETER(2, 2).ref();
626 CONSTANT(3, 0x0).s64();
627 BASIC_BLOCK(2, 3, 4)
628 {
629 INST(6, Opcode::LoadObject).s64().Volatile().Inputs(2).TypeId(176);
630 INST(8, Opcode::Compare).b().CC(CC_NE).Inputs(0, 3);
631 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
632 }
633 BASIC_BLOCK(4, -1)
634 {
635 INST(11, Opcode::Return).s64().Inputs(6);
636 }
637 BASIC_BLOCK(3, -1)
638 {
639 INST(13, Opcode::Return).s64().Inputs(3);
640 }
641 }
642 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
643 ASSERT_FALSE(GetGraph()->RunPass<CodeSink>());
644 GraphChecker(GetGraph()).Check();
645 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
646 }
647
648 /**
649 * Do not sink loads over volatile store
650 */
TEST_F(CodeSinkTest,LoadOverVolatileStore)651 TEST_F(CodeSinkTest, LoadOverVolatileStore)
652 {
653 GRAPH(GetGraph())
654 {
655 PARAMETER(0, 0).s64();
656 PARAMETER(1, 1).ref();
657 PARAMETER(2, 2).ref();
658 CONSTANT(3, 0x0).s64();
659 BASIC_BLOCK(2, 3, 4)
660 {
661 INST(4, Opcode::SaveState).Inputs(1, 2).SrcVregs({0, 1});
662 INST(5, Opcode::LoadAndInitClass).ref().Inputs(4).TypeId(0);
663 INST(6, Opcode::LoadObject).s64().Inputs(2).TypeId(176);
664 INST(7, Opcode::StoreStatic).ref().Volatile().Inputs(5, 1).TypeId(103);
665 INST(8, Opcode::Compare).b().CC(CC_NE).Inputs(0, 3);
666 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
667 }
668 BASIC_BLOCK(4, -1)
669 {
670 INST(11, Opcode::Return).s64().Inputs(6);
671 }
672 BASIC_BLOCK(3, -1)
673 {
674 INST(13, Opcode::Return).s64().Inputs(3);
675 }
676 }
677 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
678 ASSERT_FALSE(GetGraph()->RunPass<CodeSink>());
679 GraphChecker(GetGraph()).Check();
680 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
681 }
682
683 /**
684 * Do not sink loads over GC barriered store.
685 */
TEST_F(CodeSinkTest,LoadOverRefStore)686 TEST_F(CodeSinkTest, LoadOverRefStore)
687 {
688 GRAPH(GetGraph())
689 {
690 PARAMETER(0, 0).s64();
691 PARAMETER(1, 1).ref();
692 PARAMETER(2, 2).ref();
693 CONSTANT(3, 0x0).s64();
694 BASIC_BLOCK(2, 3, 4)
695 {
696 INST(6, Opcode::LoadArray).ref().Inputs(1, 0);
697 INST(7, Opcode::StoreArray).ref().Inputs(1, 0, 2);
698 INST(8, Opcode::Compare).b().CC(CC_NE).Inputs(0, 3);
699 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
700 }
701 BASIC_BLOCK(4, -1)
702 {
703 INST(11, Opcode::Return).ref().Inputs(6);
704 }
705 BASIC_BLOCK(3, -1)
706 {
707 INST(13, Opcode::Return).ref().Inputs(2);
708 }
709 }
710 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
711 ASSERT_FALSE(GetGraph()->RunPass<CodeSink>());
712 GraphChecker(GetGraph()).Check();
713 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
714 }
715
716 /**
717 * Do not sink into irreducible loops.
718 */
TEST_F(CodeSinkTest,SinkIntoIrreducible)719 TEST_F(CodeSinkTest, SinkIntoIrreducible)
720 {
721 GRAPH(GetGraph())
722 {
723 PARAMETER(0, 0).s32();
724 PARAMETER(1, 1).s32();
725 PARAMETER(2, 2).s32();
726 PARAMETER(3, 3).s32();
727 CONSTANT(5, 0x2a).s64();
728 BASIC_BLOCK(2, 3, 6)
729 {
730 INST(8, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_EQ).Imm(0).Inputs(0);
731 }
732 BASIC_BLOCK(3, 7, 9)
733 {
734 INST(10, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_EQ).Imm(0).Inputs(1);
735 }
736 BASIC_BLOCK(6, 10, 9)
737 {
738 INST(20, Opcode::Phi).s32().Inputs({{2, 5}, {7, 11}});
739 INST(26, Opcode::Mul).s32().Inputs(20, 5);
740 INST(28, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_EQ).Imm(0).Inputs(2);
741 }
742 // BB 10 and BB 7 represent an irreducible loop. Do not sink v26 into it.
743 BASIC_BLOCK(10, 7)
744 {
745 INST(30, Opcode::SaveState).NoVregs();
746 INST(36, Opcode::CallStatic).s64().InputsAutoType(26, 30);
747 }
748 BASIC_BLOCK(7, 6, 9)
749 {
750 INST(11, Opcode::Phi).s32().Inputs({{3, 5}, {10, 26}});
751 INST(19, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_EQ).Imm(0).Inputs(3);
752 }
753 BASIC_BLOCK(9, -1)
754 {
755 INST(34, Opcode::Phi).s32().Inputs({{3, 1}, {6, 2}, {7, 3}});
756 INST(35, Opcode::Return).s32().Inputs(34);
757 }
758 }
759 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
760 ASSERT_FALSE(GetGraph()->RunPass<CodeSink>());
761 GraphChecker(GetGraph()).Check();
762 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
763 }
764
765 /**
766 * Do not try to sink if an instruction has no uses. It's a waste of time.
767 */
TEST_F(CodeSinkTest,UselessSinking)768 TEST_F(CodeSinkTest, UselessSinking)
769 {
770 GRAPH(GetGraph())
771 {
772 PARAMETER(0, 0).s64();
773 PARAMETER(1, 1).s64();
774 PARAMETER(2, 2).s64();
775 CONSTANT(3, 0x0).s64();
776 BASIC_BLOCK(2, 3, 4)
777 {
778 // v5 is not used anywhere
779 INST(5, Opcode::Add).s64().Inputs(1, 2);
780 INST(6, Opcode::Compare).b().CC(CC_NE).Inputs(0, 3);
781 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
782 }
783 BASIC_BLOCK(4, -1)
784 {
785 INST(9, Opcode::Return).s64().Inputs(0);
786 }
787 BASIC_BLOCK(3, -1)
788 {
789 INST(11, Opcode::Return).s64().Inputs(3);
790 }
791 }
792
793 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
794 ASSERT_FALSE(GetGraph()->RunPass<CodeSink>());
795 GraphChecker(GetGraph()).Check();
796 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
797 }
798 } // namespace panda::compiler
799