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 <gtest/gtest.h>
17 #include <gmock/gmock.h>
18 #include "unit_test.h"
19 #include "optimizer/analysis/dominators_tree.h"
20 #include "optimizer/analysis/liveness_analyzer.h"
21
22 namespace panda::compiler {
23 using LiveRanges = ArenaDeque<LiveRange>;
24
25 #define LIVE_RANGES_DEQUE(...) LiveRanges({__VA_ARGS__}, GetAllocator()->Adapter())
26
27 class LivenessAnalyzerTest : public GraphTest {
28 public:
Check_Subsequence(const ArenaVector<BasicBlock * > & blocks,const ArenaVector<BasicBlock * > && subsequence)29 void Check_Subsequence(const ArenaVector<BasicBlock *> &blocks, const ArenaVector<BasicBlock *> &&subsequence)
30 {
31 auto subseq_iter = subsequence.begin();
32 for (auto block : blocks) {
33 if (block == *subseq_iter) {
34 if (++subseq_iter == subsequence.end()) {
35 break;
36 }
37 }
38 }
39 EXPECT_TRUE(subseq_iter == subsequence.end());
40 }
41 };
42
43 /*
44 * Test Graph:
45 * [0]
46 * |
47 * v
48 * /--[2]--\
49 * / \
50 * / \
51 * v V
52 * /----------->[4]---------->[3]<---------[15]-------\
53 * | | | |
54 * | v V |
55 * [12] [5] [6]<-----------\ |
56 * | | | | |
57 * | v v | |
58 * \------------[11] [7] [10] |
59 * | | ^ |
60 * v v | |
61 * [13] [8]---------->[9] |
62 * | | |
63 * v v |
64 * [1] [14]---------------------/
65 *
66 * Linear order:
67 * [0, 2, 4, 5, 11, 12, 13, 1, 3, 6, 7, 8, 9, 10, 14, 15, 1]
68 */
TEST_F(LivenessAnalyzerTest,LinearizeGraph)69 TEST_F(LivenessAnalyzerTest, LinearizeGraph)
70 {
71 GRAPH(GetGraph())
72 {
73 CONSTANT(0, 0);
74 CONSTANT(1, 1);
75 BASIC_BLOCK(2, 4, 3)
76 {
77 INST(2, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
78 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
79 }
80 BASIC_BLOCK(3, 6) {}
81 BASIC_BLOCK(4, 5, 3)
82 {
83 INST(5, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
84 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
85 }
86 BASIC_BLOCK(5, 11) {}
87 BASIC_BLOCK(6, 7) {}
88 BASIC_BLOCK(7, 8) {}
89 BASIC_BLOCK(8, 14, 9)
90 {
91 INST(10, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
92 INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
93 }
94 BASIC_BLOCK(9, 10) {}
95 BASIC_BLOCK(10, 6) {}
96 BASIC_BLOCK(11, 13, 12)
97 {
98 INST(14, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
99 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
100 }
101 BASIC_BLOCK(12, 4) {}
102 BASIC_BLOCK(13, -1)
103 {
104 INST(17, Opcode::ReturnVoid);
105 }
106 BASIC_BLOCK(14, 15) {}
107 BASIC_BLOCK(15, 3) {}
108 }
109 EXPECT_TRUE(GetGraph()->RunPass<LivenessAnalyzer>());
110
111 const auto &blocks = GetGraph()->GetAnalysis<LivenessAnalyzer>().GetLinearizedBlocks();
112 Check_Subsequence(blocks, GetBlocksById(GetGraph(), {0, 2, 4, 5, 11, 12, 13, 1, 3, 6, 7, 8, 9, 10, 14, 15}));
113 }
114
TEST_F(LivenessAnalyzerTest,LinearizeGraph2)115 TEST_F(LivenessAnalyzerTest, LinearizeGraph2)
116 {
117 GRAPH(GetGraph())
118 {
119 CONSTANT(0, 0);
120 CONSTANT(1, 1);
121
122 BASIC_BLOCK(100, 6) {}
123 BASIC_BLOCK(6, 2, 7)
124 {
125 INST(2, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
126 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
127 }
128
129 BASIC_BLOCK(2, 5) {}
130 BASIC_BLOCK(5, 4, 3)
131 {
132 INST(4, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
133 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
134 }
135
136 BASIC_BLOCK(4, 21) {}
137 BASIC_BLOCK(21, 17, 14)
138 {
139 INST(6, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
140 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
141 }
142
143 BASIC_BLOCK(14, 5) {}
144 BASIC_BLOCK(3, 6) {}
145 BASIC_BLOCK(7, -1)
146 {
147 INST(14, Opcode::ReturnVoid);
148 }
149
150 BASIC_BLOCK(17, 18, 19)
151 {
152 INST(8, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
153 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
154 }
155
156 BASIC_BLOCK(18, 24, 31)
157 {
158 INST(10, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
159 INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
160 }
161
162 BASIC_BLOCK(19, 36, 43)
163 {
164 INST(12, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
165 INST(13, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(12);
166 }
167
168 BASIC_BLOCK(24, 20) {}
169 BASIC_BLOCK(36, 20) {}
170 BASIC_BLOCK(20, 21) {}
171 BASIC_BLOCK(31, -1)
172 {
173 INST(15, Opcode::ReturnVoid);
174 }
175 BASIC_BLOCK(43, -1)
176 {
177 INST(16, Opcode::ReturnVoid);
178 }
179 }
180 EXPECT_TRUE(GetGraph()->RunPass<LivenessAnalyzer>());
181
182 const auto &blocks = GetGraph()->GetAnalysis<LivenessAnalyzer>().GetLinearizedBlocks();
183 Check_Subsequence(blocks,
184 GetBlocksById(GetGraph(), {0, 100, 6, 2, 5, 4, 21, 17, 18, 24, 19, 36, 20, 14, 3, 43, 31, 7, 1}));
185 }
186
187 /*
188 * [0]
189 * |
190 * v
191 * [2]
192 * / \
193 * v v
194 * [3]<----[4]
195 * |
196 * v
197 * [1]
198 */
TEST_F(LivenessAnalyzerTest,LinearizeGraphWithoutLoops)199 TEST_F(LivenessAnalyzerTest, LinearizeGraphWithoutLoops)
200 {
201 GRAPH(GetGraph())
202 {
203 PARAMETER(0, 0).u64();
204 PARAMETER(1, 1).u64();
205
206 BASIC_BLOCK(2, 3, 4)
207 {
208 INST(2, Opcode::Compare).b().Inputs(0, 1);
209 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
210 }
211 BASIC_BLOCK(4, 3) {}
212 BASIC_BLOCK(3, -1)
213 {
214 INST(5, Opcode::ReturnVoid);
215 }
216 }
217
218 EXPECT_TRUE(GetGraph()->RunPass<LivenessAnalyzer>());
219 Check_Subsequence(GetGraph()->GetAnalysis<LivenessAnalyzer>().GetLinearizedBlocks(),
220 GetBlocksById(GetGraph(), {0, 2, 4, 3, 1}));
221
222 BB(2).SwapTrueFalseSuccessors();
223 EXPECT_TRUE(GetGraph()->RunPass<LivenessAnalyzer>());
224 Check_Subsequence(GetGraph()->GetAnalysis<LivenessAnalyzer>().GetLinearizedBlocks(),
225 GetBlocksById(GetGraph(), {0, 2, 4, 3, 1}));
226 }
227
228 /*
229 * Сheck LifeIntervals updating correctness
230 */
TEST_F(LivenessAnalyzerTest,LifeIntervals)231 TEST_F(LivenessAnalyzerTest, LifeIntervals)
232 {
233 LifeIntervals life_inter(GetAllocator());
234 life_inter.AppendRange({90, 100});
235 life_inter.AppendRange({80, 90});
236 life_inter.AppendRange({40, 50});
237 life_inter.AppendRange({35, 40});
238 EXPECT_EQ(life_inter.GetRanges(), LIVE_RANGES_DEQUE({35, 50}, {80, 100}));
239
240 life_inter.AppendRange({20, 34});
241 life_inter.StartFrom(30);
242 EXPECT_EQ(life_inter.GetRanges(), LIVE_RANGES_DEQUE({30, 34}, {35, 50}, {80, 100}));
243
244 life_inter.AppendRange({10, 20});
245 life_inter.AppendGroupRange({10, 25});
246 EXPECT_EQ(life_inter.GetRanges(), LIVE_RANGES_DEQUE({10, 25}, {30, 34}, {35, 50}, {80, 100}));
247
248 life_inter.AppendGroupRange({10, 79});
249 EXPECT_EQ(life_inter.GetRanges(), LIVE_RANGES_DEQUE({10, 79}, {80, 100}));
250
251 life_inter.AppendGroupRange({10, 95});
252 EXPECT_EQ(life_inter.GetRanges(), LIVE_RANGES_DEQUE({10, 100}));
253 }
254
255 /*
256 * Test Graph:
257 * [0]
258 * |
259 * v
260 * /-----[2]<----\
261 * | | |
262 * | v |
263 * | [3]-----/
264 * |
265 * \---->[4]
266 * |
267 * v
268 * [exit]
269 *
270 *
271 * Blocks linear order:
272 * ID LIFE RANGE
273 * ---------------
274 * 0 [0, 8]
275 * 2 [8, 14]
276 * 3 [14, 22]
277 * 4 [22, 26]
278 *
279 *
280 * Insts linear order:
281 * ID INST(INPUTS) LIFE NUMBER LIFE INTERVALS
282 * ------------------------------------------
283 * 0. Constant 2 [2-22]
284 * 1. Constant 4 [4-8]
285 * 2. Constant 6 [6-24]
286 *
287 * 3. Phi (0,7) 8 [8-16][22-24]
288 * 4. Phi (1,8) 8 [8-18]
289 * 5. Cmp (4,0) 10 [10-12]
290 * 6. If (5) 12 -
291 *
292 * 7. Mul (3,4) 16 [16-2?]
293 * 8. Sub (4,0) 18 [18-2?]
294 *
295 * 9. Add (2,3) 2? [2?-2?]
296 */
TEST_F(LivenessAnalyzerTest,InstructionsLifetime)297 TEST_F(LivenessAnalyzerTest, InstructionsLifetime)
298 {
299 GRAPH(GetGraph())
300 {
301 CONSTANT(0, 1);
302 CONSTANT(1, 10);
303 CONSTANT(2, 20);
304
305 BASIC_BLOCK(2, 3, 4)
306 {
307 INST(3, Opcode::Phi).u64().Inputs({{0, 0}, {3, 7}});
308 INST(4, Opcode::Phi).u64().Inputs({{0, 1}, {3, 8}});
309 INST(5, Opcode::Compare).b().Inputs(4, 0);
310 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
311 }
312
313 BASIC_BLOCK(3, 2)
314 {
315 INST(7, Opcode::Mul).u64().Inputs(3, 4);
316 INST(8, Opcode::Sub).u64().Inputs(4, 0);
317 }
318
319 BASIC_BLOCK(4, -1)
320 {
321 INST(9, Opcode::Add).u64().Inputs(2, 3);
322 INST(10, Opcode::ReturnVoid);
323 }
324 }
325 auto liveness_analyzer = &GetGraph()->GetValidAnalysis<LivenessAnalyzer>();
326
327 auto const0 = liveness_analyzer->GetInstLifeIntervals(&INS(0));
328 auto const1 = liveness_analyzer->GetInstLifeIntervals(&INS(1));
329 auto const2 = liveness_analyzer->GetInstLifeIntervals(&INS(2));
330 auto phi0 = liveness_analyzer->GetInstLifeIntervals(&INS(3));
331 auto phi1 = liveness_analyzer->GetInstLifeIntervals(&INS(4));
332 auto cmp = liveness_analyzer->GetInstLifeIntervals(&INS(5));
333 auto mul = liveness_analyzer->GetInstLifeIntervals(&INS(7));
334 auto sub = liveness_analyzer->GetInstLifeIntervals(&INS(8));
335 auto add = liveness_analyzer->GetInstLifeIntervals(&INS(9));
336
337 auto b0_lifetime = liveness_analyzer->GetBlockLiveRange(&BB(0));
338 auto b2_lifetime = liveness_analyzer->GetBlockLiveRange(&BB(2));
339 auto b3_lifetime = liveness_analyzer->GetBlockLiveRange(&BB(3));
340 auto b4_lifetime = liveness_analyzer->GetBlockLiveRange(&BB(4));
341
342 EXPECT_EQ(const0->GetRanges()[0], LiveRange(b0_lifetime.GetBegin() + 2, b3_lifetime.GetEnd()));
343 EXPECT_EQ(const1->GetRanges()[0], LiveRange(b0_lifetime.GetBegin() + 4, phi0->GetRanges()[0].GetBegin()));
344 EXPECT_EQ(const2->GetRanges()[0], LiveRange(b0_lifetime.GetBegin() + 6, add->GetRanges()[0].GetBegin()));
345 EXPECT_EQ(phi0->GetRanges()[0], LiveRange(b2_lifetime.GetBegin(), mul->GetRanges()[0].GetBegin()));
346 EXPECT_EQ(phi0->GetRanges()[1], LiveRange(b4_lifetime.GetBegin(), add->GetRanges()[0].GetBegin()));
347 EXPECT_EQ(phi1->GetRanges()[0], LiveRange(b2_lifetime.GetBegin(), sub->GetRanges()[0].GetBegin()));
348 EXPECT_EQ(cmp->GetRanges()[0], LiveRange(b2_lifetime.GetBegin() + 2, b2_lifetime.GetBegin() + 4));
349 EXPECT_EQ(mul->GetRanges()[0], LiveRange(b3_lifetime.GetBegin() + 2, b3_lifetime.GetEnd()));
350 EXPECT_EQ(sub->GetRanges()[0], LiveRange(b3_lifetime.GetBegin() + 4, b3_lifetime.GetEnd()));
351 EXPECT_EQ(add->GetRanges()[0], LiveRange(b4_lifetime.GetBegin() + 2, b4_lifetime.GetBegin() + 4));
352 }
353
TEST_F(LivenessAnalyzerTest,LoadStoreArrayDataFlow)354 TEST_F(LivenessAnalyzerTest, LoadStoreArrayDataFlow)
355 {
356 GRAPH(GetGraph())
357 {
358 PARAMETER(0, 0).ref(); // array
359 PARAMETER(1, 1).s64(); // index
360 BASIC_BLOCK(2, 3)
361 {
362 INST(2, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
363 INST(3, Opcode::NullCheck).ref().Inputs(0, 2);
364 INST(4, Opcode::LenArray).s32().Inputs(3);
365 INST(5, Opcode::BoundsCheck).s32().Inputs(4, 1, 2);
366 INST(6, Opcode::LoadArray).u64().Inputs(3, 5);
367 INST(7, Opcode::Add).s64().Inputs(6, 6);
368 INST(8, Opcode::StoreArray).u64().Inputs(3, 5, 7);
369 }
370 BASIC_BLOCK(3, -1)
371 {
372 INST(11, Opcode::Return).u64().Inputs(7); // Some return value
373 }
374 }
375
376 auto liveness_analyzer = &GetGraph()->GetAnalysis<LivenessAnalyzer>();
377 liveness_analyzer->Run();
378
379 auto array = liveness_analyzer->GetInstLifeIntervals(&INS(0));
380 auto index = liveness_analyzer->GetInstLifeIntervals(&INS(1));
381 auto null_check = liveness_analyzer->GetInstLifeIntervals(&INS(3));
382 auto len_array = liveness_analyzer->GetInstLifeIntervals(&INS(4));
383 auto bounds_check = liveness_analyzer->GetInstLifeIntervals(&INS(5));
384 auto st_array = liveness_analyzer->GetInstLifeIntervals(&INS(8));
385
386 auto b0_lifetime = liveness_analyzer->GetBlockLiveRange(&BB(0));
387
388 EXPECT_EQ(array->GetRanges()[0], LiveRange(b0_lifetime.GetBegin() + 2, st_array->GetRanges()[0].GetBegin()));
389 EXPECT_EQ(index->GetRanges()[0], LiveRange(b0_lifetime.GetBegin() + 4, st_array->GetRanges()[0].GetBegin()));
390
391 EXPECT_EQ(null_check->GetRanges()[0].GetEnd() - null_check->GetRanges()[0].GetBegin(), 2U);
392 EXPECT_EQ(bounds_check->GetRanges()[0].GetEnd() - bounds_check->GetRanges()[0].GetBegin(), 2U);
393 EXPECT_EQ(len_array->GetRanges()[0].GetEnd() - len_array->GetRanges()[0].GetBegin(), 2U);
394 }
395
TEST_F(LivenessAnalyzerTest,SaveStateInputs)396 TEST_F(LivenessAnalyzerTest, SaveStateInputs)
397 {
398 GRAPH(GetGraph())
399 {
400 PARAMETER(0, 0).ref();
401 PARAMETER(1, 1).u32();
402 PARAMETER(2, 2).u32();
403
404 BASIC_BLOCK(2, -1)
405 {
406 INST(3, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({0, 1, 2});
407 INST(4, Opcode::NullCheck).ref().Inputs(0, 3);
408 INST(5, Opcode::StoreObject).u32().Inputs(4, 1);
409 INST(6, Opcode::ReturnVoid).v0id();
410 }
411 }
412 auto liveness_analyzer = &GetGraph()->GetAnalysis<LivenessAnalyzer>();
413 liveness_analyzer->Run();
414
415 auto par0_lifetime = liveness_analyzer->GetInstLifeIntervals(&INS(0));
416 auto par1_lifetime = liveness_analyzer->GetInstLifeIntervals(&INS(1));
417 auto par2_lifetime = liveness_analyzer->GetInstLifeIntervals(&INS(2));
418 auto null_check_lifetime = liveness_analyzer->GetInstLifeIntervals(&INS(4));
419 EXPECT_TRUE(par0_lifetime->GetEnd() == null_check_lifetime->GetEnd());
420 EXPECT_TRUE(par1_lifetime->GetEnd() == null_check_lifetime->GetEnd());
421 EXPECT_TRUE(par2_lifetime->GetEnd() == null_check_lifetime->GetBegin());
422 }
423
424 /**
425 * [begin]
426 * |
427 * [2]
428 * |
429 * [3]<-------\
430 * / \ |
431 * [end] [4] |
432 * | |
433 * /---->[5]----/
434 * | |
435 * \-----[6]
436 *
437 */
TEST_F(LivenessAnalyzerTest,InnerLoops)438 TEST_F(LivenessAnalyzerTest, InnerLoops)
439 {
440 GRAPH(GetGraph())
441 {
442 PARAMETER(0, 0).u32(); // a
443 PARAMETER(1, 1).u32(); // b
444 PARAMETER(2, 2).u32(); // c
445 CONSTANT(3, 1); // d
446
447 BASIC_BLOCK(2, 3)
448 {
449 INST(5, Opcode::Mul).u32().Inputs(0, 1); // a * b
450 INST(6, Opcode::Add).u32().Inputs(0, 1); // a + b
451 }
452 BASIC_BLOCK(3, 4, 7)
453 {
454 INST(9, Opcode::Phi).u32().Inputs(2, 12);
455 INST(10, Opcode::If).SrcType(DataType::UINT32).CC(CC_LT).Inputs(9, 5); // if c < a * b
456 }
457 BASIC_BLOCK(4, 5)
458 {
459 INST(11, Opcode::Add).u32().Inputs(9, 3); // c++
460 }
461 BASIC_BLOCK(5, 6, 3)
462 {
463 INST(12, Opcode::Phi).u32().Inputs(11, 14);
464 INST(13, Opcode::If).SrcType(DataType::UINT32).CC(CC_LT).Inputs(12, 6); // if c < a + b
465 }
466 BASIC_BLOCK(6, 5)
467 {
468 INST(14, Opcode::Add).u32().Inputs(12, 3); // c++
469 }
470 BASIC_BLOCK(7, -1)
471 {
472 INST(15, Opcode::ReturnVoid);
473 }
474 }
475
476 auto liveness_analyzer = &GetGraph()->GetAnalysis<LivenessAnalyzer>();
477 liveness_analyzer->Run();
478 auto mul = liveness_analyzer->GetInstLifeIntervals(&INS(5));
479 auto add = liveness_analyzer->GetInstLifeIntervals(&INS(6));
480 auto inner_loop_back = liveness_analyzer->GetBlockLiveRange(&BB(6));
481 EXPECT_EQ(mul->GetEnd(), inner_loop_back.GetEnd());
482 EXPECT_EQ(add->GetEnd(), inner_loop_back.GetEnd());
483 }
484
TEST_F(LivenessAnalyzerTest,UpdateExistingRanges)485 TEST_F(LivenessAnalyzerTest, UpdateExistingRanges)
486 {
487 GRAPH(GetGraph())
488 {
489 PARAMETER(0, 0).u32();
490 PARAMETER(1, 1).u32();
491
492 BASIC_BLOCK(2, 4, 3)
493 {
494 INST(2, Opcode::Add).u32().Inputs(0, 1);
495 INST(3, Opcode::Compare).b().Inputs(0, 2);
496 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
497 }
498
499 BASIC_BLOCK(3, -1)
500 {
501 INST(5, Opcode::Cast).u32().SrcType(DataType::BOOL).Inputs(3);
502 INST(6, Opcode::Return).u32().Inputs(5);
503 }
504
505 BASIC_BLOCK(4, -1)
506 {
507 INST(7, Opcode::ReturnI).u32().Imm(1);
508 }
509 }
510
511 auto la = &GetGraph()->GetAnalysis<LivenessAnalyzer>();
512 la->Run();
513
514 auto cmp = la->GetInstLifeIntervals(&INS(3));
515 EXPECT_EQ(cmp->GetRanges().size(), 2);
516
517 auto first_interval = cmp->GetRanges().front();
518 auto add = la->GetInstLifeIntervals(&INS(2));
519 EXPECT_EQ(first_interval.GetBegin(), add->GetEnd());
520 EXPECT_EQ(first_interval.GetEnd(), la->GetBlockLiveRange(&BB(2)).GetEnd());
521
522 auto second_interval = cmp->GetRanges().back();
523 auto cast = la->GetInstLifeIntervals(&INS(5));
524 EXPECT_EQ(second_interval.GetBegin(), la->GetBlockLiveRange(&BB(3)).GetBegin());
525 EXPECT_EQ(second_interval.GetEnd(), cast->GetBegin());
526 }
527
TEST_F(LivenessAnalyzerTest,ReturnInlinedLiveness)528 TEST_F(LivenessAnalyzerTest, ReturnInlinedLiveness)
529 {
530 GRAPH(GetGraph())
531 {
532 PARAMETER(0, 0).s32();
533 PARAMETER(1, 1).s32();
534 PARAMETER(20, 2).s32();
535
536 BASIC_BLOCK(2, -1)
537 {
538 INST(2, Opcode::SaveState).Inputs(20).SrcVregs({0});
539 INST(3, Opcode::CallStatic).v0id().Inlined().InputsAutoType(2);
540 INST(4, Opcode::ReturnInlined).s32().Inputs(2);
541 INST(5, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
542 INST(6, Opcode::CallStatic).v0id().Inlined().InputsAutoType(5);
543 INST(7, Opcode::CallStatic).v0id().Inlined().InputsAutoType(5);
544 INST(8, Opcode::SaveStateDeoptimize).Inputs(6, 7).SrcVregs({0, 1});
545 INST(9, Opcode::ReturnInlined).s32().Inputs(5);
546 INST(10, Opcode::ReturnInlined).s32().Inputs(5);
547 INST(13, Opcode::NOP);
548 INST(14, Opcode::NOP);
549 INST(11, Opcode::Deoptimize).Inputs(8);
550 INST(12, Opcode::ReturnVoid).v0id();
551 }
552 }
553 INS(10).CastToReturnInlined()->SetExtendedLiveness();
554
555 auto la = &GetGraph()->GetAnalysis<LivenessAnalyzer>();
556 la->Run();
557 auto par0_lifetime = la->GetInstLifeIntervals(&INS(0));
558 auto par1_lifetime = la->GetInstLifeIntervals(&INS(1));
559 auto par2_lifetime = la->GetInstLifeIntervals(&INS(20));
560 auto deopt_lifetime = la->GetInstLifeIntervals(&INS(11));
561 // 5.SaveState's inputs' liveness should be propagated up to 11.Deoptimize
562 EXPECT_GE(par0_lifetime->GetEnd(), deopt_lifetime->GetBegin());
563 EXPECT_GE(par1_lifetime->GetEnd(), deopt_lifetime->GetBegin());
564 // 2.SaveState's input's liveness should not be propagated
565 EXPECT_LT(par2_lifetime->GetEnd(), deopt_lifetime->GetBegin());
566 }
567
TEST_F(LivenessAnalyzerTest,LookupInstByLifeNumber)568 TEST_F(LivenessAnalyzerTest, LookupInstByLifeNumber)
569 {
570 GRAPH(GetGraph())
571 {
572 PARAMETER(0, 0).u64();
573 PARAMETER(1, 1).u64();
574
575 BASIC_BLOCK(2, 3, 4)
576 {
577 INST(2, Opcode::Compare).b().SrcType(DataType::Type::UINT64).Inputs(0, 1);
578 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
579 }
580
581 BASIC_BLOCK(3, 5)
582 {
583 INST(4, Opcode::Add).u64().Inputs(0, 1);
584 }
585
586 BASIC_BLOCK(4, 5)
587 {
588 INST(5, Opcode::Sub).u64().Inputs(0, 1);
589 }
590
591 BASIC_BLOCK(5, -1)
592 {
593 INST(6, Opcode::Phi).u64().Inputs(4, 5);
594 INST(7, Opcode::Return).u64().Inputs(6);
595 }
596 }
597
598 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
599 la.Run();
600
601 EXPECT_EQ(la.GetInstByLifeNumber(la.GetInstLifeIntervals(&INS(4))->GetBegin()), &INS(4));
602 EXPECT_EQ(la.GetInstByLifeNumber(la.GetInstLifeIntervals(&INS(4))->GetBegin() + 1), &INS(4));
603 EXPECT_EQ(la.GetInstByLifeNumber(la.GetInstLifeIntervals(&INS(6))->GetBegin()), nullptr);
604 }
605
TEST_F(LivenessAnalyzerTest,PhiDataFlowInput)606 TEST_F(LivenessAnalyzerTest, PhiDataFlowInput)
607 {
608 GRAPH(GetGraph())
609 {
610 CONSTANT(0, nullptr).ref();
611 PARAMETER(1, 0).ref();
612
613 BASIC_BLOCK(2, 3, 4)
614 {
615 INST(5, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
616 INST(6, Opcode::NullCheck).ref().Inputs(1, 5);
617 INST(7, Opcode::LoadObject).s32().Inputs(6);
618 INST(8, Opcode::IfImm).SrcType(compiler::DataType::INT32).CC(compiler::CC_NE).Imm(0).Inputs(7);
619 }
620 BASIC_BLOCK(3, 5) {}
621 BASIC_BLOCK(4, 5) {}
622 BASIC_BLOCK(5, 1)
623 {
624 INST(9, Opcode::Phi).ref().Inputs(0, 6);
625 INST(10, Opcode::Return).ref().Inputs(9);
626 }
627 }
628
629 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
630 la.Run();
631 auto par0_lifetime = la.GetInstLifeIntervals(&INS(1));
632 auto phi_lifetime = la.GetInstLifeIntervals(&INS(9));
633 EXPECT_EQ(par0_lifetime->GetEnd(), phi_lifetime->GetBegin());
634 }
635
636 // TODO (a.popov) Enable
TEST_F(LivenessAnalyzerTest,DISABLED_CatchProcessing)637 TEST_F(LivenessAnalyzerTest, DISABLED_CatchProcessing)
638 {
639 GRAPH(GetGraph())
640 {
641 PARAMETER(0, 0).u64();
642
643 BASIC_BLOCK(2, 3, 4)
644 {
645 INST(1, Opcode::Try).CatchTypeIds({0x0});
646 }
647
648 BASIC_BLOCK(3, 5)
649 {
650 INST(2, Opcode::Mul).u64().Inputs(0, 0);
651 INST(3, Opcode::Mul).u64().Inputs(0, 2);
652 }
653
654 BASIC_BLOCK(5, 6, 4) {} // try-end
655
656 BASIC_BLOCK(4, -1)
657 {
658 INST(5, Opcode::Return).u64().Inputs(2);
659 }
660
661 BASIC_BLOCK(6, -1)
662 {
663 INST(4, Opcode::Return).u64().Inputs(3);
664 }
665 }
666
667 GetGraph()->AppendThrowableInst(&INS(3), &BB(5));
668 INS(1).CastToTry()->SetTryEndBlock(&BB(5));
669
670 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
671 la.Run();
672
673 EXPECT_EQ(la.GetInstByLifeNumber(la.GetInstLifeIntervals(&INS(2))->GetBegin()), &INS(2));
674 EXPECT_EQ(la.GetInstByLifeNumber(la.GetInstLifeIntervals(&INS(3))->GetBegin()), &INS(3));
675 }
676
TEST_F(LivenessAnalyzerTest,FirstIntersection)677 TEST_F(LivenessAnalyzerTest, FirstIntersection)
678 {
679 // li: [10-20] [30-40]
680 // other: [21-25] [45-100]
681 // intersection: INVALID_LIFE_NUMBER
682 LifeIntervals li(GetAllocator());
683 li.AppendRange({30, 40});
684 li.AppendRange({10, 20});
685 LifeIntervals other_li(GetAllocator());
686 other_li.AppendRange({45, 100});
687 other_li.AppendRange({21, 25});
688 EXPECT_EQ(li.GetFirstIntersectionWith(&other_li), INVALID_LIFE_NUMBER);
689
690 // li: [21-25] [30-40]
691 // other: [10-20] [45-100]
692 // intersection: INVALID_LIFE_NUMBER
693 li.Clear();
694 li.AppendRange({30, 40});
695 li.AppendRange({21, 25});
696 other_li.Clear();
697 other_li.AppendRange({45, 100});
698 other_li.AppendRange({10, 20});
699 EXPECT_EQ(li.GetFirstIntersectionWith(&other_li), INVALID_LIFE_NUMBER);
700
701 // li: [10-20] [30-40]
702 // other: [15-25] [35-100]
703 // intersection: INVALID_LIFE_NUMBER
704 li.Clear();
705 li.AppendRange({30, 40});
706 li.AppendRange({10, 20});
707 other_li.Clear();
708 other_li.AppendRange({35, 100});
709 other_li.AppendRange({15, 25});
710 EXPECT_EQ(li.GetFirstIntersectionWith(&other_li), LifeNumber(15));
711
712 // li: [15-25] [35-100]
713 // other: [10-20] [30-40]
714 // intersection: INVALID_LIFE_NUMBER
715 li.Clear();
716 li.AppendRange({35, 100});
717 li.AppendRange({15, 25});
718 other_li.Clear();
719 other_li.AppendRange({30, 40});
720 other_li.AppendRange({10, 20});
721 EXPECT_EQ(li.GetFirstIntersectionWith(&other_li), LifeNumber(15));
722
723 // li: [25-35] [45 - 100]
724 // other: [10-20] [50-60]
725 // intersection: INVALID_LIFE_NUMBER
726 li.Clear();
727 li.AppendRange({45, 100});
728 li.AppendRange({25, 35});
729 other_li.Clear();
730 other_li.AppendRange({50, 60});
731 other_li.AppendRange({10, 20});
732 EXPECT_EQ(li.GetFirstIntersectionWith(&other_li), LifeNumber(50));
733
734 // li: [0-10]
735 // other: [6-12]
736 // seach_from: 8
737 // intersection: 8
738 li.Clear();
739 li.AppendRange({0, 10});
740 other_li.Clear();
741 other_li.AppendRange({6, 12});
742 EXPECT_EQ(li.GetFirstIntersectionWith(&other_li, 8), LifeNumber(8));
743
744 // li: [0-10] [20-30]
745 // other: [0-2] [18-24]
746 // search_from: 2
747 // intersection: 20
748 li.Clear();
749 li.AppendRange({20, 30});
750 li.AppendRange({0, 10});
751 other_li.Clear();
752 other_li.AppendRange({18, 24});
753 other_li.AppendRange({0, 2});
754 EXPECT_EQ(li.GetFirstIntersectionWith(&other_li, 2), LifeNumber(20));
755
756 // li: [10-20]
757 // other: [8-30]
758 // search_from: 18
759 // intersection: 18
760 li.Clear();
761 li.AppendRange({10, 20});
762 other_li.Clear();
763 other_li.AppendRange({8, 30});
764 EXPECT_EQ(li.GetFirstIntersectionWith(&other_li, 18), LifeNumber(18));
765
766 // li: [0-10] [20-22] [24-26]
767 // other: [0-2] [22-24]
768 // search_from: 12
769 // intersection: INVALID_LIFE_NUMBER
770 li.Clear();
771 li.AppendRange({24, 26});
772 li.AppendRange({20, 22});
773 li.AppendRange({0, 10});
774 other_li.Clear();
775 other_li.AppendRange({22, 24});
776 other_li.AppendRange({0, 2});
777 EXPECT_EQ(li.GetFirstIntersectionWith(&other_li, 12), INVALID_LIFE_NUMBER);
778 }
779
TEST_F(LivenessAnalyzerTest,NextUsePositions)780 TEST_F(LivenessAnalyzerTest, NextUsePositions)
781 {
782 LifeIntervals li(GetAllocator());
783 li.AppendRange({0, 100});
784 li.AddUsePosition(20);
785 li.AddUsePosition(50);
786 li.AddUsePosition(75);
787 li.AddUsePosition(100);
788
789 EXPECT_EQ(li.GetNextUsage(0), 20);
790 EXPECT_EQ(li.GetNextUsage(20), 20);
791 EXPECT_EQ(li.GetNextUsage(30), 50);
792 EXPECT_EQ(li.GetNextUsage(50), 50);
793 EXPECT_EQ(li.GetNextUsage(70), 75);
794 EXPECT_EQ(li.GetNextUsage(75), 75);
795 EXPECT_EQ(li.GetNextUsage(90), 100);
796 EXPECT_EQ(li.GetNextUsage(100), 100);
797 EXPECT_EQ(li.GetNextUsage(150), INVALID_LIFE_NUMBER);
798 }
799
TEST_F(LivenessAnalyzerTest,NoUsageUntil)800 TEST_F(LivenessAnalyzerTest, NoUsageUntil)
801 {
802 LifeIntervals li(GetAllocator());
803 li.AppendRange({0, 100});
804 li.AddUsePosition(20);
805 li.AddUsePosition(50);
806 EXPECT_TRUE(li.NoUsageUntil(0));
807 EXPECT_TRUE(li.NoUsageUntil(19));
808 EXPECT_FALSE(li.NoUsageUntil(20));
809 EXPECT_FALSE(li.NoUsageUntil(21));
810 EXPECT_FALSE(li.NoUsageUntil(100));
811 }
812
TEST_F(LivenessAnalyzerTest,SplitUsePositions)813 TEST_F(LivenessAnalyzerTest, SplitUsePositions)
814 {
815 LifeIntervals li(GetAllocator());
816 li.AppendRange({0, 200});
817 li.AddUsePosition(20);
818 li.AddUsePosition(50);
819 li.AddUsePosition(75);
820 li.AddUsePosition(100);
821
822 auto split = li.SplitAt(50, GetAllocator());
823 EXPECT_THAT(li.GetUsePositions(), ::testing::ElementsAre(20));
824 EXPECT_THAT(split->GetUsePositions(), ::testing::ElementsAre(50, 75, 100));
825
826 auto next_spit = split->SplitAt(150, GetAllocator());
827 EXPECT_TRUE(next_spit->GetUsePositions().empty());
828 EXPECT_THAT(split->GetUsePositions(), ::testing::ElementsAre(50, 75, 100));
829 }
830
TEST_F(LivenessAnalyzerTest,PropagateLivenessForImplicitNullCheckSaveStateInputs)831 TEST_F(LivenessAnalyzerTest, PropagateLivenessForImplicitNullCheckSaveStateInputs)
832 {
833 GRAPH(GetGraph())
834 {
835 PARAMETER(0, 0).ref();
836 PARAMETER(1, 1).s32();
837
838 BASIC_BLOCK(2, -1)
839 {
840 INST(2, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
841 INST(3, Opcode::NullCheck).ref().Inputs(0, 2);
842 INST(4, Opcode::AddI).s32().Imm(1U).Inputs(1);
843 INST(5, Opcode::LenArray).s32().Inputs(3);
844 INST(6, Opcode::Add).s32().Inputs(4, 5);
845 INST(7, Opcode::Return).s32().Inputs(6);
846 }
847 }
848 INS(3).CastToNullCheck()->SetImplicit(true);
849
850 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
851 ASSERT_TRUE(la.Run());
852
853 auto param = la.GetInstLifeIntervals(&INS(1));
854 auto len = la.GetInstLifeIntervals(&INS(5));
855 ASSERT_GE(param->GetEnd(), len->GetBegin());
856 }
857
TEST_F(LivenessAnalyzerTest,PropagateLivenessForExplicitNullCheckSaveStateInputs)858 TEST_F(LivenessAnalyzerTest, PropagateLivenessForExplicitNullCheckSaveStateInputs)
859 {
860 GRAPH(GetGraph())
861 {
862 PARAMETER(0, 0).ref();
863 PARAMETER(1, 1).s32();
864
865 BASIC_BLOCK(2, -1)
866 {
867 INST(2, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
868 INST(3, Opcode::NullCheck).ref().Inputs(0, 2);
869 INST(4, Opcode::AddI).s32().Imm(1U).Inputs(1);
870 INST(5, Opcode::LenArray).s32().Inputs(3);
871 INST(6, Opcode::Add).s32().Inputs(4, 5);
872 INST(7, Opcode::Return).s32().Inputs(6);
873 }
874 }
875 INS(3).CastToNullCheck()->SetImplicit(false);
876
877 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
878 ASSERT_TRUE(la.Run());
879
880 auto param = la.GetInstLifeIntervals(&INS(1));
881 auto addi = la.GetInstLifeIntervals(&INS(4));
882 ASSERT_EQ(param->GetEnd(), addi->GetBegin());
883 }
884
TEST_F(LivenessAnalyzerTest,NullCheckWithoutUsers)885 TEST_F(LivenessAnalyzerTest, NullCheckWithoutUsers)
886 {
887 GRAPH(GetGraph())
888 {
889 PARAMETER(0, 0).ref();
890 PARAMETER(1, 1).s32();
891
892 BASIC_BLOCK(2, -1)
893 {
894 INST(20, Opcode::SaveState).NoVregs();
895 INST(2, Opcode::CallStatic).ref().InputsAutoType(0, 20);
896 INST(3, Opcode::SaveState).Inputs(2).SrcVregs({0});
897 INST(4, Opcode::NullCheck).ref().Inputs(2, 3);
898 INST(5, Opcode::Return).s32().Inputs(1);
899 }
900 }
901 BB(2).SetTry(true);
902 INS(4).CastToNullCheck()->SetImplicit(true);
903
904 auto &la = GetGraph()->GetAnalysis<LivenessAnalyzer>();
905 ASSERT_TRUE(la.Run());
906
907 auto call = la.GetInstLifeIntervals(&INS(2));
908 auto null_check = la.GetInstLifeIntervals(&INS(4));
909 ASSERT_EQ(call->GetEnd(), null_check->GetBegin() + 1U);
910 }
911 } // namespace panda::compiler
912