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 #include "optimizer/optimizations/scheduler.h"
19
20 namespace panda::compiler {
21 class SchedulerTest : public GraphTest {
22 };
23
TEST_F(SchedulerTest,Basic)24 TEST_F(SchedulerTest, Basic)
25 {
26 GRAPH(GetGraph())
27 {
28 CONSTANT(0, 42);
29 CONSTANT(1, 43);
30 CONSTANT(2, 44);
31 CONSTANT(3, 45);
32 CONSTANT(4, 46);
33 CONSTANT(5, 47);
34 CONSTANT(6, 48);
35 CONSTANT(7, 49);
36
37 BASIC_BLOCK(2, -1)
38 {
39 INST(8, Opcode::Add).u64().Inputs(0, 1);
40 INST(9, Opcode::Add).u64().Inputs(2, 3);
41 // should be moved down
42 INST(10, Opcode::Add).u64().Inputs(8, 9);
43
44 INST(11, Opcode::Add).u64().Inputs(4, 5);
45 INST(12, Opcode::Add).u64().Inputs(6, 7);
46 INST(13, Opcode::Add).u64().Inputs(11, 12);
47 // Grand total
48 INST(14, Opcode::Add).u64().Inputs(10, 13);
49 INST(15, Opcode::Return).u64().Inputs(14);
50 }
51 }
52
53 ASSERT_TRUE(GetGraph()->RunPass<Scheduler>());
54
55 ASSERT_EQ(INS(8).GetNext(), &INS(9));
56 ASSERT_NE(INS(9).GetNext(), &INS(10));
57
58 EXPECT_TRUE((INS(11).GetNext() == &INS(10)) || (INS(12).GetNext() == &INS(10)));
59
60 ASSERT_EQ(INS(13).GetNext(), &INS(14));
61 ASSERT_EQ(INS(14).GetNext(), &INS(15));
62 }
63
TEST_F(SchedulerTest,LoadBarrier)64 TEST_F(SchedulerTest, LoadBarrier)
65 {
66 GRAPH(GetGraph())
67 {
68 PARAMETER(0, 0).s32(); // index
69 PARAMETER(1, 1).ref();
70 CONSTANT(2, 42);
71 CONSTANT(3, 43);
72 CONSTANT(4, 44);
73 CONSTANT(5, 45);
74 CONSTANT(6, 46);
75 CONSTANT(7, 47);
76 CONSTANT(8, 48);
77 CONSTANT(9, 5); // len array
78
79 BASIC_BLOCK(2, -1)
80 {
81 INST(10, Opcode::Add).u64().Inputs(2, 3);
82 INST(11, Opcode::Add).u64().Inputs(4, 5);
83 // should be moved down
84 INST(12, Opcode::Add).u64().Inputs(10, 11);
85
86 INST(13, Opcode::Add).u64().Inputs(6, 7);
87
88 INST(21, Opcode::SafePoint).Inputs(0, 1).SrcVregs({0, 1});
89 INST(14, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
90 INST(15, Opcode::BoundsCheck).s32().Inputs(9, 0, 14);
91 // can't move up because of SafePoint
92 INST(16, Opcode::LoadArray).u64().Inputs(1, 15);
93
94 INST(17, Opcode::Add).u64().Inputs(8, 16);
95 INST(18, Opcode::Add).u64().Inputs(13, 17);
96
97 INST(19, Opcode::Add).u64().Inputs(12, 18);
98 INST(20, Opcode::Return).u64().Inputs(19);
99 }
100 }
101
102 ASSERT_TRUE(GetGraph()->RunPass<Scheduler>());
103
104 ASSERT_EQ(INS(11).GetNext(), &INS(13));
105 ASSERT_EQ(INS(13).GetNext(), &INS(12));
106 ASSERT_EQ(INS(12).GetNext(), &INS(21));
107 ASSERT_EQ(INS(21).GetNext(), &INS(14));
108 ASSERT_EQ(INS(15).GetNext(), &INS(16));
109 ASSERT_EQ(INS(16).GetNext(), &INS(17));
110 }
111
TEST_F(SchedulerTest,Load)112 TEST_F(SchedulerTest, Load)
113 {
114 GRAPH(GetGraph())
115 {
116 PARAMETER(0, 0).s32(); // index
117 PARAMETER(1, 1).ref();
118 CONSTANT(2, 42);
119 CONSTANT(3, 43);
120 CONSTANT(4, 44);
121 CONSTANT(5, 45);
122 CONSTANT(6, 46);
123 CONSTANT(7, 47);
124 CONSTANT(8, 48);
125 CONSTANT(9, 5); // len array
126
127 BASIC_BLOCK(2, -1)
128 {
129 INST(10, Opcode::Add).u64().Inputs(2, 3);
130 INST(11, Opcode::Add).u64().Inputs(4, 5);
131 // should be moved down
132 INST(12, Opcode::Add).u64().Inputs(10, 11);
133
134 INST(13, Opcode::Add).u64().Inputs(6, 7);
135
136 // all three should be moved up
137 INST(14, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
138 INST(15, Opcode::BoundsCheck).s32().Inputs(9, 0, 14);
139 INST(16, Opcode::LoadArray).u64().Inputs(1, 15);
140
141 INST(17, Opcode::Add).u64().Inputs(8, 16);
142 INST(18, Opcode::Add).u64().Inputs(13, 17);
143
144 INST(19, Opcode::Add).u64().Inputs(12, 18);
145 INST(20, Opcode::Return).u64().Inputs(19);
146 }
147 }
148
149 ASSERT_TRUE(GetGraph()->RunPass<Scheduler>());
150
151 ASSERT_EQ(INS(14).GetNext(), &INS(10));
152 ASSERT_EQ(INS(10).GetNext(), &INS(15));
153 ASSERT_EQ(INS(15).GetNext(), &INS(11));
154 ASSERT_EQ(INS(11).GetNext(), &INS(16));
155 ASSERT_EQ(INS(16).GetNext(), &INS(13));
156 ASSERT_EQ(INS(13).GetNext(), &INS(12));
157 ASSERT_EQ(INS(12).GetNext(), &INS(17));
158 ASSERT_EQ(INS(17).GetNext(), &INS(18));
159 ASSERT_EQ(INS(18).GetNext(), &INS(19));
160 ASSERT_EQ(INS(19).GetNext(), &INS(20));
161 }
162
TEST_F(SchedulerTest,LoadI)163 TEST_F(SchedulerTest, LoadI)
164 {
165 GRAPH(GetGraph())
166 {
167 PARAMETER(0, 0).u64();
168 PARAMETER(1, 1).ref();
169
170 BASIC_BLOCK(2, -1)
171 {
172 INST(2, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
173 INST(3, Opcode::BoundsCheckI).s32().Inputs(0, 2).Imm(1);
174 INST(4, Opcode::StoreArrayI).u64().Inputs(1, 0).Imm(1);
175 INST(5, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
176 INST(6, Opcode::BoundsCheckI).s32().Inputs(0, 5).Imm(0);
177 INST(7, Opcode::LoadArrayI).u64().Inputs(1).Imm(0);
178 INST(8, Opcode::Return).u64().Inputs(7);
179 }
180 }
181
182 ASSERT_FALSE(GetGraph()->RunPass<Scheduler>());
183 }
184
TEST_F(SchedulerTest,TrickyLoadI)185 TEST_F(SchedulerTest, TrickyLoadI)
186 {
187 GRAPH(GetGraph())
188 {
189 PARAMETER(0, 0).u64();
190 PARAMETER(1, 1).ref();
191 BASIC_BLOCK(2, -1)
192 {
193 INST(5, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
194 INST(6, Opcode::BoundsCheckI).s32().Inputs(0, 5).Imm(0);
195 // Manually moved here
196 INST(2, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
197 INST(3, Opcode::BoundsCheckI).s32().Inputs(0, 2).Imm(1);
198 INST(4, Opcode::StoreArrayI).u64().Inputs(1, 0).Imm(1);
199 // But than all 3 may be moved below the load
200 INST(7, Opcode::LoadArrayI).u64().Inputs(1).Imm(0);
201 INST(8, Opcode::Return).u64().Inputs(7);
202 }
203 }
204
205 ASSERT_TRUE(GetGraph()->RunPass<Scheduler>());
206
207 auto graph = CreateEmptyGraph();
208 GRAPH(graph)
209 {
210 PARAMETER(0, 0).u64();
211 PARAMETER(1, 1).ref();
212 BASIC_BLOCK(2, -1)
213 {
214 INST(5, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
215 INST(6, Opcode::BoundsCheckI).s32().Inputs(0, 5).Imm(0);
216 INST(7, Opcode::LoadArrayI).u64().Inputs(1).Imm(0);
217
218 INST(2, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
219 INST(3, Opcode::BoundsCheckI).s32().Inputs(0, 2).Imm(1);
220 INST(4, Opcode::StoreArrayI).u64().Inputs(1, 0).Imm(1);
221
222 INST(8, Opcode::Return).u64().Inputs(7);
223 }
224 }
225 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
226 }
227
TEST_F(SchedulerTest,MustAliasLoadI)228 TEST_F(SchedulerTest, MustAliasLoadI)
229 {
230 GRAPH(GetGraph())
231 {
232 PARAMETER(0, 0).u64();
233 PARAMETER(1, 1).ref();
234 BASIC_BLOCK(2, -1)
235 {
236 INST(5, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
237 INST(6, Opcode::BoundsCheckI).s32().Inputs(0, 5).Imm(42);
238 // Manually moved here
239 INST(2, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
240 INST(3, Opcode::BoundsCheckI).s32().Inputs(0, 2).Imm(42);
241 INST(4, Opcode::StoreArrayI).u64().Inputs(1, 0).Imm(42);
242 // But than all 3 may be moved below the load
243 INST(7, Opcode::LoadArrayI).u64().Inputs(1).Imm(42);
244 INST(8, Opcode::Return).u64().Inputs(7);
245 }
246 }
247
248 ASSERT_FALSE(GetGraph()->RunPass<Scheduler>());
249 }
250
TEST_F(SchedulerTest,LoadPair)251 TEST_F(SchedulerTest, LoadPair)
252 {
253 GRAPH(GetGraph())
254 {
255 PARAMETER(0, 0).s32(); // index
256 PARAMETER(1, 1).ref();
257 CONSTANT(11, 41);
258 CONSTANT(12, 42);
259 CONSTANT(13, 43);
260 CONSTANT(14, 44);
261 CONSTANT(15, 45);
262 CONSTANT(16, 46);
263 CONSTANT(17, 47);
264 CONSTANT(18, 48);
265 CONSTANT(19, 49);
266 CONSTANT(20, 50);
267 CONSTANT(21, 51);
268 CONSTANT(22, 52);
269 CONSTANT(23, 53);
270 CONSTANT(24, 54);
271
272 BASIC_BLOCK(2, -1)
273 {
274 INST(31, Opcode::Add).u64().Inputs(11, 12);
275 INST(32, Opcode::Add).u64().Inputs(13, 14);
276 INST(41, Opcode::Add).u64().Inputs(31, 32);
277
278 INST(33, Opcode::Add).u64().Inputs(15, 16);
279 INST(34, Opcode::Add).u64().Inputs(17, 18);
280 INST(42, Opcode::Add).u64().Inputs(33, 34);
281
282 INST(35, Opcode::Add).u64().Inputs(19, 20);
283 INST(36, Opcode::Add).u64().Inputs(21, 22);
284 INST(43, Opcode::Add).u64().Inputs(35, 36);
285
286 INST(92, Opcode::LoadArrayPair).u64().Inputs(1, 0);
287 INST(93, Opcode::LoadPairPart).u64().Inputs(92).Imm(0);
288 INST(94, Opcode::LoadPairPart).u64().Inputs(92).Imm(1);
289
290 INST(37, Opcode::Add).u64().Inputs(23, 93);
291 INST(38, Opcode::Add).u64().Inputs(24, 94);
292 INST(44, Opcode::Add).u64().Inputs(37, 38);
293
294 INST(51, Opcode::Add).u64().Inputs(41, 42);
295 INST(52, Opcode::Add).u64().Inputs(43, 44);
296
297 INST(61, Opcode::Add).u64().Inputs(51, 52);
298 INST(62, Opcode::Return).u64().Inputs(61);
299 }
300 }
301
302 ASSERT_TRUE(GetGraph()->RunPass<Scheduler>());
303
304 auto graph = CreateEmptyGraph();
305 GRAPH(graph)
306 {
307 PARAMETER(0, 0).s32(); // index
308 PARAMETER(1, 1).ref();
309 CONSTANT(11, 41);
310 CONSTANT(12, 42);
311 CONSTANT(13, 43);
312 CONSTANT(14, 44);
313 CONSTANT(15, 45);
314 CONSTANT(16, 46);
315 CONSTANT(17, 47);
316 CONSTANT(18, 48);
317 CONSTANT(19, 49);
318 CONSTANT(20, 50);
319 CONSTANT(21, 51);
320 CONSTANT(22, 52);
321 CONSTANT(23, 53);
322 CONSTANT(24, 54);
323
324 BASIC_BLOCK(2, -1)
325 {
326 INST(92, Opcode::LoadArrayPair).u64().Inputs(1, 0);
327 INST(93, Opcode::LoadPairPart).u64().Inputs(92).Imm(0);
328 INST(94, Opcode::LoadPairPart).u64().Inputs(92).Imm(1);
329
330 INST(31, Opcode::Add).u64().Inputs(11, 12);
331 INST(32, Opcode::Add).u64().Inputs(13, 14);
332 INST(33, Opcode::Add).u64().Inputs(15, 16);
333 INST(34, Opcode::Add).u64().Inputs(17, 18);
334 INST(35, Opcode::Add).u64().Inputs(19, 20);
335 INST(36, Opcode::Add).u64().Inputs(21, 22);
336 INST(37, Opcode::Add).u64().Inputs(23, 93);
337 INST(38, Opcode::Add).u64().Inputs(24, 94);
338
339 INST(41, Opcode::Add).u64().Inputs(31, 32);
340 INST(42, Opcode::Add).u64().Inputs(33, 34);
341 INST(43, Opcode::Add).u64().Inputs(35, 36);
342 INST(44, Opcode::Add).u64().Inputs(37, 38);
343
344 INST(51, Opcode::Add).u64().Inputs(41, 42);
345 INST(52, Opcode::Add).u64().Inputs(43, 44);
346
347 INST(61, Opcode::Add).u64().Inputs(51, 52);
348 INST(62, Opcode::Return).u64().Inputs(61);
349 }
350 }
351 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
352 }
353
TEST_F(SchedulerTest,NonVolatileLoadObject)354 TEST_F(SchedulerTest, NonVolatileLoadObject)
355 {
356 GRAPH(GetGraph())
357 {
358 PARAMETER(0, 0).ref();
359 PARAMETER(1, 1).s32();
360 PARAMETER(2, 2).s32();
361 PARAMETER(3, 3).s32();
362 BASIC_BLOCK(2, -1)
363 {
364 INST(4, Opcode::Add).s32().Inputs(1, 2);
365 INST(5, Opcode::Add).s32().Inputs(1, 3);
366 INST(6, Opcode::Add).s32().Inputs(2, 3);
367 INST(7, Opcode::Add).s32().Inputs(4, 5);
368 INST(8, Opcode::Add).s32().Inputs(6, 7);
369 INST(9, Opcode::SaveState).Inputs(0).SrcVregs({0});
370 INST(10, Opcode::NullCheck).ref().Inputs(0, 9);
371 INST(11, Opcode::LoadObject).s32().Inputs(10).TypeId(152);
372 INST(12, Opcode::Add).s32().Inputs(8, 11);
373 INST(13, Opcode::Return).s32().Inputs(12);
374 }
375 }
376 ASSERT_TRUE(GetGraph()->RunPass<Scheduler>());
377
378 auto graph = CreateEmptyGraph();
379 GRAPH(graph)
380 {
381 PARAMETER(0, 0).ref();
382 PARAMETER(1, 1).s32();
383 PARAMETER(2, 2).s32();
384 PARAMETER(3, 3).s32();
385 BASIC_BLOCK(2, -1)
386 {
387 INST(9, Opcode::SaveState).Inputs(0).SrcVregs({0});
388 INST(4, Opcode::Add).s32().Inputs(1, 2);
389 INST(10, Opcode::NullCheck).ref().Inputs(0, 9);
390 INST(5, Opcode::Add).s32().Inputs(1, 3);
391 INST(11, Opcode::LoadObject).s32().Inputs(10).TypeId(152);
392 INST(6, Opcode::Add).s32().Inputs(2, 3);
393 INST(7, Opcode::Add).s32().Inputs(4, 5);
394 INST(8, Opcode::Add).s32().Inputs(6, 7);
395 INST(12, Opcode::Add).s32().Inputs(8, 11);
396 INST(13, Opcode::Return).s32().Inputs(12);
397 }
398 }
399 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
400 }
401
TEST_F(SchedulerTest,VolatileLoadObject)402 TEST_F(SchedulerTest, VolatileLoadObject)
403 {
404 GRAPH(GetGraph())
405 {
406 PARAMETER(0, 0).ref();
407 PARAMETER(1, 1).s32();
408 PARAMETER(2, 2).s32();
409 PARAMETER(3, 3).s32();
410 BASIC_BLOCK(2, -1)
411 {
412 INST(4, Opcode::Add).s32().Inputs(1, 2);
413 INST(5, Opcode::Add).s32().Inputs(1, 3);
414 INST(6, Opcode::Add).s32().Inputs(2, 3);
415 INST(7, Opcode::Add).s32().Inputs(4, 5);
416 INST(8, Opcode::Add).s32().Inputs(6, 7);
417 INST(9, Opcode::SaveState).Inputs(0).SrcVregs({0});
418 INST(10, Opcode::NullCheck).ref().Inputs(0, 9);
419 INST(11, Opcode::LoadObject).s32().Inputs(10).TypeId(152).Volatile();
420 INST(12, Opcode::Add).s32().Inputs(8, 11);
421 INST(13, Opcode::Return).s32().Inputs(12);
422 }
423 }
424 ASSERT_TRUE(GetGraph()->RunPass<Scheduler>());
425
426 auto graph = CreateEmptyGraph();
427 GRAPH(graph)
428 {
429 PARAMETER(0, 0).ref();
430 PARAMETER(1, 1).s32();
431 PARAMETER(2, 2).s32();
432 PARAMETER(3, 3).s32();
433 BASIC_BLOCK(2, -1)
434 {
435 INST(4, Opcode::Add).s32().Inputs(1, 2);
436 INST(5, Opcode::Add).s32().Inputs(1, 3);
437 INST(9, Opcode::SaveState).Inputs(0).SrcVregs({0});
438 INST(6, Opcode::Add).s32().Inputs(2, 3);
439 INST(7, Opcode::Add).s32().Inputs(4, 5);
440 INST(10, Opcode::NullCheck).ref().Inputs(0, 9);
441 INST(8, Opcode::Add).s32().Inputs(6, 7);
442 INST(11, Opcode::LoadObject).s32().Inputs(10).TypeId(152).Volatile();
443 INST(12, Opcode::Add).s32().Inputs(8, 11);
444 INST(13, Opcode::Return).s32().Inputs(12);
445 }
446 }
447 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
448 }
449 } // namespace panda::compiler
450