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/vn.h"
18 #include "optimizer/analysis/alias_analysis.h"
19
20 namespace panda::compiler {
21 class AliasAnalysisTest : public GraphTest {
22 };
23
24 /**
25 * foo (int *arr, int a1, int a2, int a3)
26 * int tmp;
27 * if (a3 < 0)
28 * tmp = arr[a1];
29 * else
30 * tmp = arr[a2];
31 * return tmp + arr[a1] + arr[a2];
32 *
33 * arr[a1] must alias the second arr[a1] and may alias arr[a2]
34 */
TEST_F(AliasAnalysisTest,SimpleLoad)35 TEST_F(AliasAnalysisTest, SimpleLoad)
36 {
37 GRAPH(GetGraph())
38 {
39 PARAMETER(0, 0).ref();
40 PARAMETER(1, 1).s64();
41 PARAMETER(2, 2).s64();
42 PARAMETER(3, 3).s64();
43 CONSTANT(4, 0);
44 BASIC_BLOCK(2, 3, 4)
45 {
46 INST(5, Opcode::Compare).b().Inputs(3, 4);
47 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
48 }
49 BASIC_BLOCK(4, 5)
50 {
51 INST(11, Opcode::LoadArray).s32().Inputs(0, 1);
52 }
53 BASIC_BLOCK(3, 5)
54 {
55 INST(17, Opcode::LoadArray).s32().Inputs(0, 2);
56 }
57 BASIC_BLOCK(5, -1)
58 {
59 INST(18, Opcode::Phi).s32().Inputs({{4, 11}, {3, 17}});
60
61 INST(23, Opcode::LoadArray).s32().Inputs(0, 1);
62
63 INST(28, Opcode::LoadArray).s32().Inputs(0, 2);
64
65 INST(29, Opcode::Add).s32().Inputs(28, 23);
66 INST(30, Opcode::Add).s32().Inputs(29, 18);
67 INST(31, Opcode::Return).s32().Inputs(30);
68 }
69 }
70
71 GetGraph()->RunPass<AliasAnalysis>();
72 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
73 GraphChecker(GetGraph()).Check();
74
75 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
76 ASSERT_EQ(alias.CheckRefAlias(&INS(0), &INS(0)), AliasType::MUST_ALIAS);
77 ASSERT_EQ(alias.CheckInstAlias(&INS(11), &INS(23)), AliasType::MUST_ALIAS);
78 ASSERT_EQ(alias.CheckInstAlias(&INS(17), &INS(28)), AliasType::MUST_ALIAS);
79 ASSERT_EQ(alias.CheckInstAlias(&INS(11), &INS(28)), AliasType::MAY_ALIAS);
80 ASSERT_EQ(alias.CheckInstAlias(&INS(17), &INS(23)), AliasType::MAY_ALIAS);
81 }
82
83 /**
84 * foo (int *arr, int a1, int a2, int a3)
85 * int tmp;
86 * if (a3 < 0)
87 * (NullCheck(arr) for arr[a1]);
88 * (BoundsCheck for a1)
89 * tmp = arr[a1];
90 * else
91 * (NullCheck(arr) for arr[a2]);
92 * (BoundsCheck for a2)
93 * tmp = arr[a2];
94 * (NullCheck(arr) for arr[a1]);
95 * (BoundsCheck for a1)
96 * (NullCheck(arr) for arr[a2]);
97 * (BoundsCheck for a2)
98 * return tmp + arr[a1] + arr[a2];
99 *
100 * arr[a1] must alias the second arr[a1] and may alias arr[a2]
101 */
TEST_F(AliasAnalysisTest,CompleteLoadArray)102 TEST_F(AliasAnalysisTest, CompleteLoadArray)
103 {
104 GRAPH(GetGraph())
105 {
106 PARAMETER(0, 0).ref();
107 PARAMETER(1, 1).s64();
108 PARAMETER(2, 2).s64();
109 PARAMETER(3, 3).s64();
110 CONSTANT(4, 0);
111 BASIC_BLOCK(2, 3, 4)
112 {
113 INST(5, Opcode::Compare).b().Inputs(3, 4);
114 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
115 }
116 BASIC_BLOCK(4, 5)
117 {
118 INST(7, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({2, 3, 4});
119 INST(8, Opcode::NullCheck).ref().Inputs(0, 7);
120 INST(9, Opcode::LenArray).s32().Inputs(8);
121 INST(10, Opcode::BoundsCheck).s32().Inputs(9, 1, 7);
122 INST(11, Opcode::LoadArray).s32().Inputs(8, 10);
123 }
124 BASIC_BLOCK(3, 5)
125 {
126 INST(13, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({2, 3, 4});
127 INST(14, Opcode::NullCheck).ref().Inputs(0, 13);
128 INST(15, Opcode::LenArray).s32().Inputs(14);
129 INST(16, Opcode::BoundsCheck).s32().Inputs(15, 2, 13);
130 INST(17, Opcode::LoadArray).s32().Inputs(14, 16);
131 }
132 BASIC_BLOCK(5, -1)
133 {
134 INST(18, Opcode::Phi).s32().Inputs({{4, 11}, {3, 17}});
135
136 INST(19, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({2, 3, 4});
137 INST(20, Opcode::NullCheck).ref().Inputs(0, 19);
138 INST(21, Opcode::LenArray).s32().Inputs(20);
139 INST(22, Opcode::BoundsCheck).s32().Inputs(21, 1, 19);
140 INST(23, Opcode::LoadArray).s32().Inputs(20, 22);
141
142 INST(24, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({2, 3, 4});
143 INST(25, Opcode::NullCheck).ref().Inputs(0, 24);
144 INST(26, Opcode::LenArray).s32().Inputs(25);
145 INST(27, Opcode::BoundsCheck).s32().Inputs(26, 2, 24);
146 INST(28, Opcode::LoadArray).s32().Inputs(25, 27);
147
148 INST(29, Opcode::Add).s32().Inputs(28, 23);
149 INST(30, Opcode::Add).s32().Inputs(29, 18);
150 INST(31, Opcode::Return).s32().Inputs(30);
151 }
152 }
153
154 GetGraph()->RunPass<AliasAnalysis>();
155 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
156 GraphChecker(GetGraph()).Check();
157
158 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
159 ASSERT_EQ(alias.CheckInstAlias(&INS(11), &INS(23)), AliasType::MUST_ALIAS);
160 ASSERT_EQ(alias.CheckInstAlias(&INS(17), &INS(28)), AliasType::MUST_ALIAS);
161 ASSERT_EQ(alias.CheckInstAlias(&INS(11), &INS(28)), AliasType::MAY_ALIAS);
162 ASSERT_EQ(alias.CheckInstAlias(&INS(17), &INS(23)), AliasType::MAY_ALIAS);
163 }
164
165 /**
166 * foo (int *arr, int a1)
167 * (NullCheck(arr) for arr[a1]);
168 * (BoundsCheck for a1)
169 * int tmp = arr[a1];
170 * if (tmp == 0)
171 * (NullCheck(arr) for arr[a1]);
172 * (BoundsCheck for a1)
173 * arr[a1] = tmp;
174 * return tmp;
175 *
176 * arr[a1] must alias the second arr[a1] and may alias arr[a2]
177 */
TEST_F(AliasAnalysisTest,LoadStoreAlias)178 TEST_F(AliasAnalysisTest, LoadStoreAlias)
179 {
180 GRAPH(GetGraph())
181 {
182 PARAMETER(0, 0).ref();
183 PARAMETER(1, 1).s64();
184 CONSTANT(8, 0);
185 BASIC_BLOCK(2, 3, 4)
186 {
187 INST(2, Opcode::SaveState).Inputs(0, 1, 1).SrcVregs({0, 1, 2});
188 INST(3, Opcode::NullCheck).ref().Inputs(0, 2);
189 INST(4, Opcode::LenArray).s32().Inputs(3);
190 INST(5, Opcode::BoundsCheck).s32().Inputs(4, 1, 2);
191 INST(6, Opcode::LoadArray).u64().Inputs(3, 5);
192 INST(7, Opcode::Compare).b().CC(CC_EQ).Inputs(6, 8);
193 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
194 }
195 BASIC_BLOCK(4, -1)
196 {
197 INST(10, Opcode::Return).s64().Inputs(6);
198 }
199 BASIC_BLOCK(3, -1)
200 {
201 INST(11, Opcode::SaveState).Inputs(0, 1, 6).SrcVregs({0, 1, 2});
202 INST(12, Opcode::NullCheck).ref().Inputs(0, 11);
203 INST(13, Opcode::LenArray).s32().Inputs(12);
204 INST(14, Opcode::BoundsCheck).s32().Inputs(13, 1, 11);
205 INST(15, Opcode::StoreArray).u64().Inputs(12, 14, 6);
206 INST(16, Opcode::Return).s64().Inputs(6);
207 }
208 }
209
210 GetGraph()->RunPass<AliasAnalysis>();
211 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
212 GraphChecker(GetGraph()).Check();
213
214 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
215 ASSERT_EQ(alias.CheckInstAlias(&INS(6), &INS(15)), AliasType::MUST_ALIAS);
216 }
217
218 /**
219 * foo (int *arr1, int *arr2, int a2, int a3)
220 * arr1[a2] = a3
221 * arr2[a3] = a2
222 *
223 * All parameters by default may be aliased by each other
224 */
TEST_F(AliasAnalysisTest,DifferentObjects)225 TEST_F(AliasAnalysisTest, DifferentObjects)
226 {
227 GRAPH(GetGraph())
228 {
229 PARAMETER(0, 0).ref();
230 PARAMETER(1, 1).ref();
231 PARAMETER(2, 2).s64();
232 PARAMETER(3, 3).s64();
233 BASIC_BLOCK(2, -1)
234 {
235 INST(4, Opcode::SaveState).Inputs(0, 1, 2, 3, 2).SrcVregs({0, 1, 2, 3, 4});
236 INST(5, Opcode::NullCheck).ref().Inputs(0, 4);
237 INST(6, Opcode::LenArray).s32().Inputs(5);
238 INST(7, Opcode::BoundsCheck).s32().Inputs(6, 3, 4);
239 INST(8, Opcode::StoreArray).u64().Inputs(5, 7, 2);
240
241 INST(9, Opcode::SaveState).Inputs(0, 1, 2, 3, 3).SrcVregs({0, 1, 2, 3, 4});
242 INST(10, Opcode::NullCheck).ref().Inputs(1, 9);
243 INST(11, Opcode::LenArray).s32().Inputs(10);
244 INST(12, Opcode::BoundsCheck).s32().Inputs(11, 2, 9);
245 INST(13, Opcode::StoreArray).u64().Inputs(10, 12, 3);
246
247 INST(14, Opcode::ReturnVoid);
248 }
249 }
250
251 GetGraph()->RunPass<AliasAnalysis>();
252 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
253 GraphChecker(GetGraph()).Check();
254
255 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
256 ASSERT_EQ(alias.CheckRefAlias(&INS(0), &INS(1)), AliasType::MAY_ALIAS);
257 ASSERT_EQ(alias.CheckInstAlias(&INS(8), &INS(13)), AliasType::MAY_ALIAS);
258 }
259
260 /**
261 * foo (int *arr, a1, a2)
262 * arr[a1] = a2;
263 * int *tmp = arr;
264 * return tmp[a1];
265 *
266 * tmp must alias arr
267 */
TEST_F(AliasAnalysisTest,ArrayToArray)268 TEST_F(AliasAnalysisTest, ArrayToArray)
269 {
270 GRAPH(GetGraph())
271 {
272 PARAMETER(0, 0).ref();
273 PARAMETER(1, 1).s64();
274 PARAMETER(2, 2).s64();
275 BASIC_BLOCK(2, -1)
276 {
277 INST(3, Opcode::SaveState).Inputs(0, 1, 2, 2).SrcVregs({1, 2, 3, 4});
278 INST(4, Opcode::NullCheck).ref().Inputs(0, 3);
279 INST(5, Opcode::LenArray).s32().Inputs(4);
280 INST(6, Opcode::BoundsCheck).s32().Inputs(5, 1, 3);
281 INST(7, Opcode::StoreArray).u64().Inputs(4, 6, 2);
282
283 INST(9, Opcode::SaveState).Inputs(0, 0, 1, 2, 2).SrcVregs({0, 1, 2, 3, 4});
284 INST(10, Opcode::NullCheck).ref().Inputs(0, 9);
285 INST(11, Opcode::LenArray).s32().Inputs(10);
286 INST(12, Opcode::BoundsCheck).s32().Inputs(11, 1, 9);
287 INST(13, Opcode::LoadArray).s64().Inputs(10, 12);
288 INST(14, Opcode::Return).s64().Inputs(13);
289 }
290 }
291
292 GetGraph()->RunPass<AliasAnalysis>();
293 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
294 GraphChecker(GetGraph()).Check();
295
296 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
297 ASSERT_EQ(alias.CheckInstAlias(&INS(7), &INS(13)), AliasType::MUST_ALIAS);
298 }
299
300 /**
301 * foo (int *arr0, int *arr1, a2)
302 * int *tmp;
303 * if (a2 == 0)
304 * tmp = arr0;
305 * else
306 * tmp = arr1;
307 * tmp[a2] = 0;
308 * return 0;
309 *
310 * tmp may alias arr0 and arr1
311 */
TEST_F(AliasAnalysisTest,PhiRef)312 TEST_F(AliasAnalysisTest, PhiRef)
313 {
314 GRAPH(GetGraph())
315 {
316 PARAMETER(0, 0).ref();
317 PARAMETER(1, 1).ref();
318 PARAMETER(2, 2).s64();
319 CONSTANT(4, 0).s64();
320 BASIC_BLOCK(2, 4, 3)
321 {
322 INST(3, Opcode::Compare).b().CC(CC_EQ).Inputs(2, 4);
323 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
324 }
325 BASIC_BLOCK(3, 4) {}
326 BASIC_BLOCK(4, -1)
327 {
328 INST(7, Opcode::Phi).ref().Inputs({{3, 0}, {2, 1}});
329 INST(8, Opcode::StoreArray).u64().Inputs(7, 2, 4);
330
331 INST(9, Opcode::Return).s64().Inputs(4);
332 }
333 }
334
335 GetGraph()->RunPass<AliasAnalysis>();
336 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
337 GraphChecker(GetGraph()).Check();
338
339 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
340 ASSERT_EQ(alias.CheckRefAlias(&INS(7), &INS(0)), AliasType::MAY_ALIAS);
341 ASSERT_EQ(alias.CheckRefAlias(&INS(7), &INS(1)), AliasType::MAY_ALIAS);
342 }
343
344 /**
345 * foo (int *arr0)
346 * int *x = new int[10];
347 * int tmp = arr0[0];
348 * x[0] = tmp;
349 * return x;
350 *
351 * arr0 and x are not aliasing
352 */
TEST_F(AliasAnalysisTest,NewWithArg)353 TEST_F(AliasAnalysisTest, NewWithArg)
354 {
355 GRAPH(GetGraph())
356 {
357 PARAMETER(0, 0).ref();
358 CONSTANT(1, 10).s64();
359 CONSTANT(2, 0).s64();
360
361 BASIC_BLOCK(2, -1)
362 {
363 INST(13, Opcode::SaveState).Inputs(1, 2, 0, 2).SrcVregs({0, 1, 2, 3});
364 INST(44, Opcode::LoadAndInitClass).ref().Inputs(13).TypeId(68);
365 INST(3, Opcode::NewArray).ref().Inputs(44, 1, 13);
366 INST(4, Opcode::SaveState).Inputs(1, 2, 3, 0, 2).SrcVregs({0, 1, 2, 3, 4});
367 INST(5, Opcode::NullCheck).ref().Inputs(0, 4);
368 INST(6, Opcode::LoadArray).u64().Inputs(5, 2);
369
370 INST(7, Opcode::SaveState).Inputs(1, 2, 3, 0, 6).SrcVregs({0, 1, 2, 3, 4});
371 INST(8, Opcode::NullCheck).ref().Inputs(3, 7);
372 INST(9, Opcode::StoreArray).u64().Inputs(8, 2, 6);
373 INST(10, Opcode::Return).ref().Inputs(3);
374 }
375 }
376
377 GetGraph()->RunPass<AliasAnalysis>();
378 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
379 GraphChecker(GetGraph()).Check();
380
381 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
382 ASSERT_EQ(alias.CheckRefAlias(&INS(3), &INS(0)), AliasType::NO_ALIAS);
383 ASSERT_EQ(alias.CheckInstAlias(&INS(6), &INS(9)), AliasType::NO_ALIAS);
384 }
385
386 /**
387 * foo (int *arr0)
388 * int *x = new int[10];
389 * x[0] = 0;
390 * bar (x); <- escaping call
391 * x[0] = 0;
392 *
393 * int tmp = arr0[0];
394 * x[0] = tmp;
395 * return x;
396 *
397 * arr0 and x may be aliased because x is escaping because of calling bar function.
398 */
TEST_F(AliasAnalysisTest,EscapingNewWithArg)399 TEST_F(AliasAnalysisTest, EscapingNewWithArg)
400 {
401 GRAPH(GetGraph())
402 {
403 PARAMETER(0, 0).ref();
404 CONSTANT(1, 10).s64();
405 CONSTANT(2, 0).s64();
406
407 BASIC_BLOCK(2, -1)
408 {
409 INST(20, Opcode::SaveState).Inputs(1, 2, 0, 2).SrcVregs({0, 1, 2, 3});
410 INST(44, Opcode::LoadAndInitClass).ref().Inputs(20).TypeId(68);
411 INST(3, Opcode::NewArray).ref().Inputs(44, 1, 20);
412 INST(11, Opcode::StoreArray).u64().Inputs(3, 2, 2);
413 INST(12, Opcode::CallStatic).ref().InputsAutoType(3, 20);
414 INST(13, Opcode::StoreArray).u64().Inputs(3, 2, 2);
415 INST(4, Opcode::SaveState).Inputs(1, 2, 3, 0, 2).SrcVregs({0, 1, 2, 3, 4});
416 INST(5, Opcode::NullCheck).ref().Inputs(0, 4);
417 INST(6, Opcode::LoadArray).u64().Inputs(5, 2);
418
419 INST(7, Opcode::SaveState).Inputs(1, 2, 3, 0, 6).SrcVregs({0, 1, 2, 3, 4});
420 INST(8, Opcode::NullCheck).ref().Inputs(3, 7);
421 INST(9, Opcode::StoreArray).u64().Inputs(8, 2, 6);
422 INST(10, Opcode::Return).ref().Inputs(3);
423 }
424 }
425
426 GetGraph()->RunPass<AliasAnalysis>();
427 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
428 GraphChecker(GetGraph()).Check();
429
430 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
431 ASSERT_EQ(alias.CheckRefAlias(&INS(3), &INS(0)), AliasType::MAY_ALIAS);
432 ASSERT_EQ(alias.CheckInstAlias(&INS(6), &INS(9)), AliasType::MAY_ALIAS);
433 }
434
435 /**
436 * foo (int **arr0)
437 * int *x = new int[10]
438 * arr0[0] = x; <-- potential escaping
439 * int *y = arr0[10];
440 * x[0] = y[0];
441 *
442 * The test aims to track escaping through a sequence of checks.
443 */
TEST_F(AliasAnalysisTest,EscapingWithChecks)444 TEST_F(AliasAnalysisTest, EscapingWithChecks)
445 {
446 GRAPH(GetGraph())
447 {
448 PARAMETER(0, 0).ref();
449 CONSTANT(1, 10).s64();
450 CONSTANT(2, 0).s64();
451
452 BASIC_BLOCK(2, -1)
453 {
454 INST(20, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
455 INST(44, Opcode::LoadAndInitClass).ref().Inputs(20).TypeId(68);
456 INST(9, Opcode::NewArray).ref().Inputs(44, 1, 20);
457 INST(10, Opcode::SaveState).Inputs(0, 1, 9).SrcVregs({0, 1, 9});
458
459 // At first glance it is an aritificial sequence of checks but it may
460 // happen if several inlinings occurs with multidimentional array operations
461 INST(11, Opcode::NullCheck).ref().Inputs(9, 10);
462 INST(12, Opcode::RefTypeCheck).ref().Inputs(11, 0, 10);
463 INST(15, Opcode::StoreArrayI).ref().Imm(0).Inputs(0, 12);
464 INST(16, Opcode::LoadArray).ref().Inputs(0, 1);
465
466 INST(17, Opcode::LoadArrayI).u32().Imm(0).Inputs(16);
467 INST(18, Opcode::StoreArrayI).u32().Imm(0).Inputs(9, 17);
468 INST(19, Opcode::ReturnVoid).v0id();
469 }
470 }
471
472 GetGraph()->RunPass<AliasAnalysis>();
473 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
474 GraphChecker(GetGraph()).Check();
475
476 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
477 ASSERT_EQ(alias.CheckInstAlias(&INS(17), &INS(18)), AliasType::MAY_ALIAS);
478 }
479
480 /**
481 * foo (int *arr0, int a1)
482 * int tmp;
483 * if (a1 == 0)
484 * tmp = arr0[a1 + 10];
485 * else
486 * tmp = 10;
487 * arr0[a1 + 10] = tmp;
488 * return tmp;
489 *
490 * both arr0[a1 + 10] must alias each other
491 */
TEST_F(AliasAnalysisTest,SimpleHeuristic)492 TEST_F(AliasAnalysisTest, SimpleHeuristic)
493 {
494 GRAPH(GetGraph())
495 {
496 PARAMETER(0, 0).ref();
497 PARAMETER(1, 1).s64();
498 CONSTANT(2, 10).s64();
499 CONSTANT(4, 0).s64();
500
501 BASIC_BLOCK(2, 4, 3)
502 {
503 INST(3, Opcode::Compare).b().CC(CC_EQ).Inputs(1, 4);
504 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
505 }
506 BASIC_BLOCK(3, 5)
507 {
508 INST(21, Opcode::AddI).s32().Imm(10ULL).Inputs(1);
509 INST(7, Opcode::SaveState).Inputs(21, 0, 1, 2).SrcVregs({5, 3, 4, 0});
510 INST(8, Opcode::NullCheck).ref().Inputs(0, 7);
511 INST(9, Opcode::LenArray).s32().Inputs(8);
512 INST(10, Opcode::BoundsCheck).s32().Inputs(9, 21, 7);
513 INST(11, Opcode::LoadArray).s64().Inputs(8, 10);
514 }
515 BASIC_BLOCK(4, 5)
516 {
517 INST(22, Opcode::AddI).s32().Imm(10ULL).Inputs(1);
518 INST(14, Opcode::SaveState).Inputs(1, 22, 0, 1, 2).SrcVregs({4, 2, 3, 0, 5});
519 INST(15, Opcode::NullCheck).ref().Inputs(0, 14);
520 INST(16, Opcode::LenArray).s32().Inputs(15);
521 INST(17, Opcode::BoundsCheck).s32().Inputs(16, 22, 14);
522 INST(18, Opcode::StoreArray).u64().Inputs(15, 17, 2);
523 }
524 BASIC_BLOCK(5, -1)
525 {
526 INST(19, Opcode::Phi).s64().Inputs({{3, 11}, {4, 2}});
527 INST(20, Opcode::Return).s64().Inputs(19);
528 }
529 }
530
531 GetGraph()->RunPass<ValNum>();
532 GetGraph()->RunPass<AliasAnalysis>();
533 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
534 GraphChecker(GetGraph()).Check();
535
536 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
537 ASSERT_EQ(alias.CheckInstAlias(&INS(11), &INS(18)), AliasType::MUST_ALIAS);
538 }
539
540 /**
541 * foo (int32_t *arr0, int64_t *arr1, int64_t a2, int32_t a3)
542 * arr0[a2] = a2;
543 * arr1[a2] = arr0[a3];
544 * return arr1[a3];
545 *
546 * arr0 cannot alias arr1 due to different types
547 */
TEST_F(AliasAnalysisTest,TypeComparison)548 TEST_F(AliasAnalysisTest, TypeComparison)
549 {
550 GRAPH(GetGraph())
551 {
552 PARAMETER(0, 0).ref(); // i32[]
553 PARAMETER(1, 1).ref(); // i64[]
554 PARAMETER(2, 2).s64();
555 PARAMETER(3, 3).s32();
556
557 BASIC_BLOCK(2, -1)
558 {
559 INST(4, Opcode::SaveState).Inputs(0, 1, 2, 3, 2).SrcVregs({0, 1, 2, 3, 4});
560 INST(5, Opcode::NullCheck).ref().Inputs(0, 4);
561 INST(6, Opcode::LenArray).s32().Inputs(5);
562 INST(7, Opcode::BoundsCheck).s32().Inputs(6, 2, 4);
563 INST(8, Opcode::StoreArray).u16().Inputs(5, 7, 2);
564
565 INST(9, Opcode::SaveState).Inputs(0, 1, 2, 3, 3).SrcVregs({0, 1, 2, 3, 4});
566 INST(12, Opcode::BoundsCheck).s32().Inputs(6, 3, 9);
567 INST(13, Opcode::LoadArray).u16().Inputs(5, 12);
568
569 INST(14, Opcode::SaveState).Inputs(0, 1, 2, 3, 13).SrcVregs({0, 1, 2, 3, 4});
570 INST(15, Opcode::NullCheck).ref().Inputs(1, 14);
571 INST(16, Opcode::LenArray).s32().Inputs(15);
572 INST(17, Opcode::BoundsCheck).s32().Inputs(16, 2, 14);
573 INST(18, Opcode::StoreArray).u32().Inputs(15, 17, 13);
574
575 INST(19, Opcode::SaveState).Inputs(0, 1, 2, 3, 3).SrcVregs({0, 1, 2, 3, 4});
576 INST(22, Opcode::BoundsCheck).s32().Inputs(16, 3, 19);
577 INST(23, Opcode::LoadArray).u32().Inputs(15, 22);
578 INST(25, Opcode::Return).s32().Inputs(23);
579 }
580 }
581
582 GetGraph()->RunPass<AliasAnalysis>();
583 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
584 GraphChecker(GetGraph()).Check();
585
586 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
587 ASSERT_EQ(alias.CheckInstAlias(&INS(8), &INS(13)), AliasType::MAY_ALIAS);
588 ASSERT_EQ(alias.CheckInstAlias(&INS(18), &INS(23)), AliasType::MAY_ALIAS);
589 ASSERT_EQ(alias.CheckInstAlias(&INS(8), &INS(18)), AliasType::NO_ALIAS);
590 ASSERT_EQ(alias.CheckInstAlias(&INS(8), &INS(23)), AliasType::NO_ALIAS);
591 ASSERT_EQ(alias.CheckInstAlias(&INS(13), &INS(18)), AliasType::NO_ALIAS);
592 ASSERT_EQ(alias.CheckInstAlias(&INS(13), &INS(23)), AliasType::NO_ALIAS);
593 }
594
595 /**
596 * .function i32 foo(i32[] a0, R1[] a1, R1[] a2) {
597 * movi v0, 0
598 * lda v0
599 * ldarr.obj a1
600 * starr.obj a2, v0
601 *
602 * lda v0
603 * ldarr a0
604 * return
605 * }
606 *
607 * Arrays of primitive types cannot alias arrays of ref type.
608 */
TEST_F(AliasAnalysisTest,TypeComparison2)609 TEST_F(AliasAnalysisTest, TypeComparison2)
610 {
611 GRAPH(GetGraph())
612 {
613 PARAMETER(0, 0).ref();
614 PARAMETER(1, 1).ref();
615 PARAMETER(2, 2).ref();
616 CONSTANT(3, 0x0).s64();
617 BASIC_BLOCK(2, -1)
618 {
619 INST(8, Opcode::LoadArray).ref().Inputs(1, 3);
620 INST(13, Opcode::StoreArray).ref().Inputs(2, 3, 8);
621 INST(18, Opcode::LoadArray).s32().Inputs(0, 3);
622 INST(19, Opcode::Return).s32().Inputs(18);
623 }
624 }
625
626 GetGraph()->RunPass<AliasAnalysis>();
627 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
628 GraphChecker(GetGraph()).Check();
629
630 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
631 ASSERT_EQ(alias.CheckInstAlias(&INS(8), &INS(13)), AliasType::MAY_ALIAS);
632 ASSERT_EQ(alias.CheckInstAlias(&INS(8), &INS(18)), AliasType::NO_ALIAS);
633 ASSERT_EQ(alias.CheckInstAlias(&INS(13), &INS(18)), AliasType::NO_ALIAS);
634 }
635
636 /**
637 * foo(int *arr0, int *arr1, int a2)
638 * arr0[0] = a2;
639 * arr0[1] = a2;
640 * arr1[0] = a2;
641 * arr0[a2] = arr0[1];
642 *
643 * arr0[0] and arr0[1] do not alias each other
644 * arr0[0] and arr1[0] may alias each other
645 * arr0[a2] and arr0[0] may alias each other
646 */
TEST_F(AliasAnalysisTest,LoadStoreImm)647 TEST_F(AliasAnalysisTest, LoadStoreImm)
648 {
649 GRAPH(GetGraph())
650 {
651 PARAMETER(0, 0).ref();
652 PARAMETER(1, 1).ref();
653 PARAMETER(2, 2).s64();
654
655 BASIC_BLOCK(2, -1)
656 {
657 INST(3, Opcode::SaveState).Inputs(2, 2, 0, 1).SrcVregs({5, 4, 2, 3});
658 INST(4, Opcode::NullCheck).ref().Inputs(0, 3);
659 INST(5, Opcode::LenArray).s32().Inputs(4);
660 INST(6, Opcode::BoundsCheckI).s32().Imm(0).Inputs(5, 3);
661 INST(7, Opcode::StoreArrayI).u64().Imm(0).Inputs(4, 2);
662
663 INST(8, Opcode::SaveState).Inputs(2, 2, 0, 1).SrcVregs({5, 4, 2, 3});
664 INST(9, Opcode::BoundsCheckI).s32().Imm(1).Inputs(5, 8);
665 INST(10, Opcode::StoreArrayI).u64().Imm(1).Inputs(4, 2);
666
667 INST(11, Opcode::SaveState).Inputs(2, 2, 0, 1).SrcVregs({5, 4, 2, 3});
668 INST(12, Opcode::NullCheck).ref().Inputs(1, 11);
669 INST(13, Opcode::LenArray).s32().Inputs(12);
670 INST(14, Opcode::BoundsCheckI).s32().Imm(0).Inputs(13, 11);
671 INST(15, Opcode::StoreArrayI).u64().Imm(0).Inputs(12, 2);
672
673 INST(16, Opcode::SaveState).Inputs(2, 1, 0).SrcVregs({4, 3, 2});
674 INST(17, Opcode::BoundsCheckI).s32().Imm(1).Inputs(5, 16);
675 INST(18, Opcode::LoadArrayI).u64().Imm(1).Inputs(4);
676
677 INST(19, Opcode::SaveState).Inputs(18, 2, 0, 1).SrcVregs({5, 4, 2, 3});
678 INST(20, Opcode::BoundsCheck).s32().Inputs(5, 2, 19);
679 INST(21, Opcode::StoreArray).u64().Inputs(4, 20, 18);
680
681 INST(22, Opcode::ReturnVoid).v0id();
682 }
683 }
684
685 GetGraph()->RunPass<AliasAnalysis>();
686 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
687 GraphChecker(GetGraph()).Check();
688
689 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
690 ASSERT_EQ(alias.CheckInstAlias(&INS(7), &INS(10)), AliasType::NO_ALIAS);
691 ASSERT_EQ(alias.CheckInstAlias(&INS(7), &INS(18)), AliasType::NO_ALIAS);
692 ASSERT_EQ(alias.CheckInstAlias(&INS(7), &INS(15)), AliasType::MAY_ALIAS);
693 ASSERT_EQ(alias.CheckInstAlias(&INS(7), &INS(21)), AliasType::MAY_ALIAS);
694 ASSERT_EQ(alias.CheckInstAlias(&INS(15), &INS(18)), AliasType::NO_ALIAS);
695 ASSERT_EQ(alias.CheckInstAlias(&INS(10), &INS(18)), AliasType::MUST_ALIAS);
696 }
697
698 /**
699 * .record R1 {}
700 * .record R3 {}
701 * .record R4 {
702 * R1 sf_r1 <static> # type_id = 349
703 * R1 sf_r2 <static> # type_id = 363
704 * R3 sf_r3 <static> # type_id = 377
705 * }
706 * .function void foo() {
707 * ldstatic R4.sf_r1
708 * sta.obj v0
709 * ldstatic R4.sf_r3
710 * sta.obj v1
711 * lda.obj v0
712 * ststatic R4.sf_r3
713 * lda.obj v1
714 * ststatic R4.sf_r2
715 * return.void
716 * }
717 *
718 * Static acceses MUST_ALIAS themselves and has NO_ALIAS with anything else
719 */
TEST_F(AliasAnalysisTest,StaticFields)720 TEST_F(AliasAnalysisTest, StaticFields)
721 {
722 GRAPH(GetGraph())
723 {
724 PARAMETER(0, 0).ref();
725 CONSTANT(5, 0x2a).s64();
726 BASIC_BLOCK(2, -1)
727 {
728 INST(9, Opcode::SaveState).Inputs(0).SrcVregs({0});
729 INST(6, Opcode::LoadAndInitClass).ref().Inputs(9).TypeId(0U);
730 INST(7, Opcode::LoadAndInitClass).ref().Inputs(9).TypeId(0U);
731 INST(8, Opcode::LoadAndInitClass).ref().Inputs(9).TypeId(0U);
732 INST(1, Opcode::LoadStatic).ref().Inputs(6).TypeId(349U);
733 INST(2, Opcode::LoadStatic).ref().Inputs(7).TypeId(377U);
734 INST(3, Opcode::StoreStatic).ref().Inputs(7, 1).TypeId(377U);
735 INST(4, Opcode::StoreStatic).ref().Inputs(8, 2).TypeId(363U);
736 INST(25, Opcode::ReturnVoid).v0id();
737 }
738 }
739
740 GetGraph()->RunPass<AliasAnalysis>();
741 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
742 GraphChecker(GetGraph()).Check();
743
744 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
745 /* Global variable must alias itself */
746 ASSERT_EQ(alias.CheckInstAlias(&INS(2), &INS(3)), AliasType::MUST_ALIAS);
747 ASSERT_EQ(alias.CheckInstAlias(&INS(1), &INS(2)), AliasType::NO_ALIAS);
748 ASSERT_EQ(alias.CheckInstAlias(&INS(1), &INS(4)), AliasType::NO_ALIAS);
749 ASSERT_EQ(alias.CheckInstAlias(&INS(2), &INS(4)), AliasType::NO_ALIAS);
750 }
751
752 /*
753 * .record R1 {}
754 * .record R7 {
755 * R9 ref<static> # type_id = 211
756 * }
757 * .record R8 {
758 * R9 ref $ type_id = 268
759 * }
760 * .record R9 {
761 * R1 ref # type_id = 242
762 * }
763 * .function R1 foo(R8 a0, R9 a1) {
764 * ldstatic R7.ref
765 * sta.obj v1
766 * ldobj v1, R9.ref
767 * sta.obj v0
768 *
769 * ldobj a0, R8.ref
770 * sta.obj v1
771 * ldobj v1, R9.ref
772 * stobj a1, R9.ref
773 *
774 * lda.obj v0
775 * return.obj
776 * }
777 *
778 * R7.ref MAY_ALIAS R9.ref from argument
779 */
TEST_F(AliasAnalysisTest,StaticFieldObject)780 TEST_F(AliasAnalysisTest, StaticFieldObject)
781 {
782 GRAPH(GetGraph())
783 {
784 PARAMETER(0, 0).ref();
785 PARAMETER(1, 1).ref();
786 BASIC_BLOCK(2, -1)
787 {
788 INST(16, Opcode::SaveState).Inputs(0, 1).SrcVregs({2, 3});
789 INST(9, Opcode::LoadAndInitClass).ref().Inputs(16).TypeId(0U);
790 INST(2, Opcode::LoadStatic).Inputs(9).ref().TypeId(211U);
791 INST(5, Opcode::LoadObject).ref().Inputs(2).TypeId(242U);
792 INST(8, Opcode::LoadObject).ref().Inputs(0).TypeId(268U);
793 INST(11, Opcode::LoadObject).ref().Inputs(8).TypeId(242U);
794 INST(14, Opcode::StoreObject).ref().Inputs(1, 11).TypeId(242U);
795 INST(15, Opcode::Return).ref().Inputs(5);
796 }
797 }
798
799 GetGraph()->RunPass<AliasAnalysis>();
800 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
801 GraphChecker(GetGraph()).Check();
802
803 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
804 ASSERT_EQ(alias.CheckInstAlias(&INS(14), &INS(11)), AliasType::MAY_ALIAS);
805 /* Static field can be asigned outside */
806 ASSERT_EQ(alias.CheckInstAlias(&INS(14), &INS(5)), AliasType::MAY_ALIAS);
807 }
808
809 /**
810 * .record R1 {}
811 * .record R2 {
812 * R1 if_r1 # type_id = 338
813 * R1 if_r2 # type_id = 352
814 * }
815 * .function void foo(R2 a0, R1 a1, R1 a2) {
816 * ldobj a0, R2.if_r1
817 * stobj a0, R2.if_r2
818 * lda.obj a1
819 * stobj a0, R2.if_r1
820 * return.void
821 * }
822 *
823 * Generally, if an object is not created in current scope it may alias any
824 * other object. However, different fields even of the same object do not alias
825 * each other.
826 */
TEST_F(AliasAnalysisTest,ObjectFields)827 TEST_F(AliasAnalysisTest, ObjectFields)
828 {
829 GRAPH(GetGraph())
830 {
831 PARAMETER(0, 0).ref();
832 PARAMETER(1, 1).ref();
833
834 BASIC_BLOCK(2, -1)
835 {
836 INST(2, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
837 INST(3, Opcode::NullCheck).ref().Inputs(0, 2);
838 INST(4, Opcode::LoadObject).ref().Inputs(3).TypeId(338U);
839
840 INST(5, Opcode::SaveState).Inputs(0, 1, 4).SrcVregs({0, 1, 2});
841 INST(6, Opcode::NullCheck).ref().Inputs(0, 5);
842 INST(7, Opcode::StoreObject).ref().Inputs(6, 4).TypeId(352U);
843
844 INST(8, Opcode::SaveState).Inputs(0, 1, 4).SrcVregs({0, 1, 2});
845 INST(9, Opcode::NullCheck).ref().Inputs(0, 8);
846 INST(10, Opcode::StoreObject).ref().Inputs(9, 1).TypeId(338U);
847
848 INST(11, Opcode::ReturnVoid).v0id();
849 }
850 }
851
852 GetGraph()->RunPass<AliasAnalysis>();
853 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
854 GraphChecker(GetGraph()).Check();
855
856 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
857 ASSERT_EQ(alias.CheckInstAlias(&INS(4), &INS(7)), AliasType::NO_ALIAS);
858 ASSERT_EQ(alias.CheckInstAlias(&INS(7), &INS(10)), AliasType::NO_ALIAS);
859 ASSERT_EQ(alias.CheckInstAlias(&INS(4), &INS(10)), AliasType::MUST_ALIAS);
860 }
861
862 /**
863 * .record R3 {
864 * R1 if_ref # type_id = 302
865 * }
866 * .record R4 {
867 * R3 if_r3 # type_id = 366
868 * }
869 * .function R3 init16(R4 a0, R1 a1) {
870 * ldobj a0, R4.if_r3
871 * sta.obj v1
872 * lda.obj a1
873 * stobj v1, R3.if_ref
874 *
875 * newobj v2, R4
876 * newobj v3, R3
877 * lda.obj v3
878 * stobj v2, R4.if_r3
879 * return.obj
880 * }
881 *
882 * Similar to ObjectFields test but the same fields has NO_ALIAS due to
883 * creation of the object in the current scope
884 */
TEST_F(AliasAnalysisTest,MoreObjectFields)885 TEST_F(AliasAnalysisTest, MoreObjectFields)
886 {
887 GRAPH(GetGraph())
888 {
889 PARAMETER(0, 0).ref();
890 PARAMETER(1, 1).ref();
891 BASIC_BLOCK(2, -1)
892 {
893 INST(2, Opcode::SaveState).Inputs(0, 1).SrcVregs({3, 4});
894 INST(3, Opcode::NullCheck).ref().Inputs(0, 2);
895 INST(4, Opcode::LoadObject).ref().Inputs(3).TypeId(366U);
896
897 INST(5, Opcode::SaveState).Inputs(4, 1).SrcVregs({1, 5});
898 INST(6, Opcode::NullCheck).ref().Inputs(4, 5);
899 INST(7, Opcode::StoreObject).ref().Inputs(6, 1).TypeId(302U);
900
901 INST(14, Opcode::LoadAndInitClass).ref().Inputs(5);
902 INST(8, Opcode::NewObject).ref().Inputs(14, 5);
903 INST(9, Opcode::NewObject).ref().Inputs(14, 5);
904 INST(10, Opcode::SaveState).Inputs(4, 8, 9).SrcVregs({1, 2, 5});
905 INST(11, Opcode::NullCheck).ref().Inputs(8, 10);
906 INST(12, Opcode::StoreObject).ref().Inputs(11, 9).TypeId(366U);
907 INST(13, Opcode::Return).ref().Inputs(9);
908 }
909 }
910
911 GetGraph()->RunPass<AliasAnalysis>();
912 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
913 GraphChecker(GetGraph()).Check();
914
915 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
916 ASSERT_EQ(alias.CheckInstAlias(&INS(4), &INS(12)), AliasType::NO_ALIAS);
917 ASSERT_EQ(alias.CheckInstAlias(&INS(4), &INS(7)), AliasType::NO_ALIAS);
918 ASSERT_EQ(alias.CheckInstAlias(&INS(7), &INS(12)), AliasType::NO_ALIAS);
919 }
920
921 /*
922 struct {
923 void *o1
924 void *o2
925 void *o3
926 } st
927
928 foo(uintptr *arr, int a1)
929 st.o1 = "my_str"
930 st.o2 = "your_str"
931 st.o3 = "my_str"
932
933 Values from pool MUST_ALIAS themselves
934 */
TEST_F(AliasAnalysisTest,PoolAlias)935 TEST_F(AliasAnalysisTest, PoolAlias)
936 {
937 uint32_t my_str_id = 0;
938 uint32_t your_str_id = 1;
939 GRAPH(GetGraph())
940 {
941 BASIC_BLOCK(2, -1)
942 {
943 INST(12, Opcode::SaveState).NoVregs();
944 INST(0, Opcode::LoadString).ref().Inputs(12).TypeId(my_str_id);
945 INST(9, Opcode::SaveState).Inputs(0).SrcVregs({0});
946 INST(6, Opcode::LoadAndInitClass).ref().Inputs(9);
947 INST(1, Opcode::StoreStatic).ref().Inputs(6, 0);
948
949 INST(13, Opcode::SaveState).Inputs(0).SrcVregs({0});
950 INST(2, Opcode::LoadString).ref().Inputs(13).TypeId(your_str_id);
951 INST(10, Opcode::SaveState).Inputs(2).SrcVregs({0});
952 INST(7, Opcode::LoadAndInitClass).ref().Inputs(10);
953 INST(3, Opcode::StoreStatic).ref().Inputs(7, 2);
954
955 INST(14, Opcode::SaveState).Inputs(2).SrcVregs({0});
956 INST(4, Opcode::LoadString).ref().Inputs(14).TypeId(my_str_id);
957 INST(11, Opcode::SaveState).Inputs(4).SrcVregs({0});
958 INST(8, Opcode::LoadAndInitClass).ref().Inputs(11);
959 INST(5, Opcode::StoreStatic).ref().Inputs(8, 4);
960
961 INST(21, Opcode::ReturnVoid).v0id();
962 }
963 }
964
965 GetGraph()->RunPass<AliasAnalysis>();
966 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
967 GraphChecker(GetGraph()).Check();
968
969 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
970 ASSERT_EQ(alias.CheckInstAlias(&INS(0), &INS(0)), AliasType::MUST_ALIAS);
971 ASSERT_EQ(alias.CheckInstAlias(&INS(0), &INS(2)), AliasType::NO_ALIAS);
972 ASSERT_EQ(alias.CheckInstAlias(&INS(0), &INS(4)), AliasType::MUST_ALIAS);
973 ASSERT_EQ(alias.CheckInstAlias(&INS(2), &INS(4)), AliasType::NO_ALIAS);
974 }
975
976 /*
977 * .function R1 foo(R1[][] a0, i64 a1) {
978 * lda a1
979 * ldarr.obj a0
980 * sta.obj v0
981 * lda a1
982 * ldarr.obj v0
983 * return.obj
984 * }
985 *
986 */
TEST_F(AliasAnalysisTest,NestedArrays)987 TEST_F(AliasAnalysisTest, NestedArrays)
988 {
989 GRAPH(GetGraph())
990 {
991 PARAMETER(0, 0).ref();
992 PARAMETER(1, 1).ref();
993 PARAMETER(2, 2).s64();
994 BASIC_BLOCK(2, -1)
995 {
996 INST(7, Opcode::LoadArray).ref().Inputs(0, 2);
997 INST(12, Opcode::LoadArray).ref().Inputs(7, 2);
998 INST(13, Opcode::Return).ref().Inputs(12);
999 }
1000 }
1001
1002 GetGraph()->RunPass<AliasAnalysis>();
1003 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1004 GraphChecker(GetGraph()).Check();
1005
1006 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1007 ASSERT_EQ(alias.CheckInstAlias(&INS(7), &INS(7)), AliasType::MUST_ALIAS);
1008 ASSERT_EQ(alias.CheckInstAlias(&INS(7), &INS(12)), AliasType::MAY_ALIAS);
1009 ASSERT_EQ(alias.CheckInstAlias(&INS(12), &INS(12)), AliasType::MUST_ALIAS);
1010 }
1011
1012 /**
1013 * Nested arrays with immediate indices.
1014 */
TEST_F(AliasAnalysisTest,NestedArraysImm)1015 TEST_F(AliasAnalysisTest, NestedArraysImm)
1016 {
1017 GRAPH(GetGraph())
1018 {
1019 PARAMETER(0, 0).ref();
1020 PARAMETER(1, 1).ref();
1021 PARAMETER(2, 2).s64();
1022 CONSTANT(5, 0x2a).s64();
1023 CONSTANT(6, 0x3a).s64();
1024 BASIC_BLOCK(2, -1)
1025 {
1026 INST(7, Opcode::LoadArray).ref().Inputs(0, 2);
1027 INST(12, Opcode::LoadArrayI).ref().Inputs(7).Imm(5);
1028 INST(13, Opcode::LoadArrayI).ref().Inputs(7).Imm(6);
1029 INST(14, Opcode::SaveState).Inputs(0, 12, 13).SrcVregs({0, 1, 2});
1030 INST(15, Opcode::NullCheck).ref().Inputs(12, 14);
1031 INST(16, Opcode::NullCheck).ref().Inputs(13, 14);
1032 INST(17, Opcode::ReturnVoid);
1033 }
1034 }
1035
1036 GetGraph()->RunPass<AliasAnalysis>();
1037 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1038 GraphChecker(GetGraph()).Check();
1039
1040 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1041 ASSERT_EQ(alias.CheckRefAlias(&INS(12), &INS(13)), AliasType::MAY_ALIAS);
1042 ASSERT_EQ(alias.CheckInstAlias(&INS(7), &INS(12)), AliasType::MAY_ALIAS);
1043 ASSERT_EQ(alias.CheckInstAlias(&INS(7), &INS(13)), AliasType::MAY_ALIAS);
1044 }
1045
1046 /*
1047 * .function void foo (i64[] a0, i64 a1, i64 a2) {
1048 * call.short GetArray
1049 * sta.obj v0
1050 * lda a2
1051 * starr.64 v0, a1
1052 * starr.64 a0, a1
1053 * return.void
1054 * }
1055 *
1056 * References obtained from calls are like parameters
1057 */
TEST_F(AliasAnalysisTest,StaticCall)1058 TEST_F(AliasAnalysisTest, StaticCall)
1059 {
1060 GRAPH(GetGraph())
1061 {
1062 PARAMETER(0, 0).ref();
1063 PARAMETER(1, 1).s64();
1064 PARAMETER(2, 2).s64();
1065 BASIC_BLOCK(2, -1)
1066 {
1067 INST(3, Opcode::SaveState).Inputs(0, 2).SrcVregs({1, 3});
1068 INST(4, Opcode::CallStatic).ref().Inputs({{DataType::NO_TYPE, 3}});
1069 INST(9, Opcode::StoreArray).u64().Inputs(4, 1, 2);
1070 INST(14, Opcode::StoreArray).u64().Inputs(0, 1, 2);
1071 INST(15, Opcode::ReturnVoid).v0id();
1072 }
1073 }
1074
1075 GetGraph()->RunPass<AliasAnalysis>();
1076 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1077 GraphChecker(GetGraph()).Check();
1078
1079 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1080 ASSERT_EQ(alias.CheckInstAlias(&INS(9), &INS(14)), AliasType::MAY_ALIAS);
1081 }
1082
1083 /*
1084 * .record R1 {
1085 * ref f
1086 * }
1087 * .function void init3(R1[] a0, R1 a1) {
1088 * movi v0, 23
1089 * movi v2, 39
1090 * lda v0
1091 * ldarr.obj a0
1092 * sta.obj v1
1093 * lda v2
1094 * ldarr.obj a0
1095 * sta.obj v3
1096 * ldobj.64 a1, R1.f
1097 * stobj.64 v1, R1.f
1098 * stobj.64 v3, R1.f
1099 * return.void
1100 * }
1101 *
1102 * Reference came from Load with immediate index
1103 */
TEST_F(AliasAnalysisTest,ImmediateRefLoad)1104 TEST_F(AliasAnalysisTest, ImmediateRefLoad)
1105 {
1106 GRAPH(GetGraph())
1107 {
1108 PARAMETER(0, 0).ref();
1109 PARAMETER(1, 1).ref();
1110 BASIC_BLOCK(2, -1)
1111 {
1112 INST(16, Opcode::LoadArrayI).ref().Inputs(0).Imm(0x17);
1113 INST(17, Opcode::LoadArrayI).ref().Inputs(0).Imm(0x27);
1114 INST(10, Opcode::LoadObject).ref().Inputs(1).TypeId(1);
1115 INST(13, Opcode::StoreObject).ref().Inputs(16, 10).TypeId(1);
1116 INST(14, Opcode::StoreObject).ref().Inputs(17, 10).TypeId(1);
1117 INST(15, Opcode::ReturnVoid).v0id();
1118 }
1119 }
1120
1121 GetGraph()->RunPass<AliasAnalysis>();
1122 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1123 GraphChecker(GetGraph()).Check();
1124
1125 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1126 ASSERT_EQ(alias.CheckInstAlias(&INS(10), &INS(13)), AliasType::MAY_ALIAS);
1127 ASSERT_EQ(alias.CheckRefAlias(&INS(16), &INS(17)), AliasType::MAY_ALIAS);
1128 }
1129
1130 /* Null pointer dereferences. */
TEST_F(AliasAnalysisTest,NullPtrLoads)1131 TEST_F(AliasAnalysisTest, NullPtrLoads)
1132 {
1133 GRAPH(GetGraph())
1134 {
1135 CONSTANT(0, nullptr).ref();
1136 BASIC_BLOCK(2, -1)
1137 {
1138 INST(1, Opcode::LoadArrayI).u64().Inputs(0).Imm(0);
1139 INST(2, Opcode::LoadArrayI).u64().Inputs(0).Imm(0);
1140 INST(3, Opcode::Add).u64().Inputs(1, 2);
1141 INST(4, Opcode::Return).u64().Inputs(3);
1142 }
1143 }
1144
1145 GetGraph()->RunPass<AliasAnalysis>();
1146 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1147 GraphChecker(GetGraph()).Check();
1148
1149 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1150 ASSERT_EQ(alias.CheckInstAlias(&INS(1), &INS(2)), AliasType::MUST_ALIAS);
1151 }
1152
1153 /* NullCheck in Phi inputs. */
TEST_F(AliasAnalysisTest,NullCheckPhiInput)1154 TEST_F(AliasAnalysisTest, NullCheckPhiInput)
1155 {
1156 GRAPH(GetGraph())
1157 {
1158 PARAMETER(0, 0).ref();
1159 PARAMETER(1, 1).ref();
1160 CONSTANT(7, nullptr).ref();
1161 BASIC_BLOCK(2, 3, 4)
1162 {
1163 INST(8, Opcode::Compare).b().Inputs(1, 7);
1164 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
1165 }
1166 BASIC_BLOCK(3, 4)
1167 {
1168 INST(5, Opcode::SaveState).Inputs(0, 1, 7).SrcVregs({0, 1, 2});
1169 INST(2, Opcode::NullCheck).ref().Inputs(0, 5);
1170 INST(3, Opcode::NullCheck).ref().Inputs(1, 5);
1171 INST(4, Opcode::CallVirtual)
1172 .v0id()
1173 .Inputs({{DataType::REFERENCE, 2}, {DataType::REFERENCE, 3}, {DataType::NO_TYPE, 5}});
1174 }
1175 BASIC_BLOCK(4, -1)
1176 {
1177 INST(10, Opcode::Phi).ref().Inputs({{3, 3}, {2, 7}});
1178 INST(11, Opcode::LoadArrayI).u64().Inputs(10).Imm(0);
1179 INST(12, Opcode::LoadArrayI).u64().Inputs(0).Imm(0);
1180 INST(13, Opcode::Add).u64().Inputs(11, 12);
1181 INST(14, Opcode::Return).u64().Inputs(13);
1182 }
1183 }
1184
1185 GetGraph()->RunPass<AliasAnalysis>();
1186 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1187 GraphChecker(GetGraph()).Check();
1188
1189 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1190 ASSERT_EQ(alias.CheckInstAlias(&INS(11), &INS(12)), AliasType::MAY_ALIAS);
1191 }
1192
1193 /**
1194 * Select instruction is very similar to Phi.
1195 */
TEST_F(AliasAnalysisTest,Select)1196 TEST_F(AliasAnalysisTest, Select)
1197 {
1198 GRAPH(GetGraph())
1199 {
1200 PARAMETER(0, 0).ref();
1201 PARAMETER(1, 1).ref();
1202 CONSTANT(2, 10).s64();
1203 CONSTANT(3, 0).s64();
1204
1205 BASIC_BLOCK(2, -1)
1206 {
1207 INST(13, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
1208 INST(44, Opcode::LoadAndInitClass).ref().Inputs(13).TypeId(68);
1209 INST(4, Opcode::NewArray).ref().Inputs(44, 2, 13);
1210 INST(5, Opcode::SelectImm)
1211 .ref()
1212 .SrcType(DataType::BOOL)
1213 .CC(CC_NE)
1214 .Imm(3)
1215 .Inputs(0, 1, 3)
1216 .SetFlag(compiler::inst_flags::NO_CSE)
1217 .SetFlag(compiler::inst_flags::NO_HOIST);
1218 INST(6, Opcode::SelectImm)
1219 .ref()
1220 .SrcType(DataType::BOOL)
1221 .CC(CC_NE)
1222 .Imm(3)
1223 .Inputs(5, 4, 3)
1224 .SetFlag(compiler::inst_flags::NO_CSE)
1225 .SetFlag(compiler::inst_flags::NO_HOIST);
1226 INST(10, Opcode::Return).ref().Inputs(6);
1227 }
1228 }
1229
1230 GetGraph()->RunPass<AliasAnalysis>();
1231 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1232 GraphChecker(GetGraph()).Check();
1233
1234 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1235 ASSERT_EQ(alias.CheckRefAlias(&INS(4), &INS(5)), AliasType::NO_ALIAS);
1236 ASSERT_EQ(alias.CheckRefAlias(&INS(4), &INS(6)), AliasType::MAY_ALIAS);
1237 ASSERT_EQ(alias.CheckRefAlias(&INS(0), &INS(5)), AliasType::MAY_ALIAS);
1238 ASSERT_EQ(alias.CheckRefAlias(&INS(1), &INS(5)), AliasType::MAY_ALIAS);
1239 ASSERT_EQ(alias.CheckRefAlias(&INS(0), &INS(6)), AliasType::MAY_ALIAS);
1240 ASSERT_EQ(alias.CheckRefAlias(&INS(1), &INS(6)), AliasType::MAY_ALIAS);
1241 }
1242
TEST_F(AliasAnalysisTest,LoadPairObject)1243 TEST_F(AliasAnalysisTest, LoadPairObject)
1244 {
1245 GRAPH(GetGraph())
1246 {
1247 PARAMETER(0, 0).ref();
1248 PARAMETER(1, 1).s64();
1249 BASIC_BLOCK(2, -1)
1250 {
1251 INST(12, Opcode::LoadArrayPair).ref().Inputs(0, 1);
1252 INST(14, Opcode::LoadPairPart).ref().Inputs(12).Imm(0x0);
1253 INST(13, Opcode::LoadPairPart).ref().Inputs(12).Imm(0x1);
1254 INST(15, Opcode::LoadObject).s32().Inputs(13).TypeId(42);
1255 INST(16, Opcode::LoadObject).s32().Inputs(14).TypeId(42);
1256 INST(17, Opcode::Add).s32().Inputs(15, 16);
1257 INST(18, Opcode::Return).s32().Inputs(17);
1258 }
1259 }
1260
1261 GetGraph()->RunPass<AliasAnalysis>();
1262 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1263 GraphChecker(GetGraph()).Check();
1264
1265 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1266 ASSERT_EQ(alias.CheckInstAlias(&INS(15), &INS(16)), AliasType::MAY_ALIAS);
1267 }
1268
TEST_F(AliasAnalysisTest,CatchPhi)1269 TEST_F(AliasAnalysisTest, CatchPhi)
1270 {
1271 GRAPH(GetGraph())
1272 {
1273 PARAMETER(0, 0).ref();
1274
1275 BASIC_BLOCK(2, 3, 4)
1276 {
1277 INST(2, Opcode::Try).CatchTypeIds({0xE1});
1278 }
1279 BASIC_BLOCK(3, -1)
1280 {
1281 INST(3, Opcode::SaveState).Inputs(0).SrcVregs({0});
1282 INST(4, Opcode::NullCheck).ref().Inputs(0, 3);
1283 INST(5, Opcode::LoadObject).ref().Inputs(4).TypeId(122);
1284 INST(6, Opcode::SaveState).Inputs(0, 5).SrcVregs({0, 5});
1285 INST(7, Opcode::NullCheck).ref().Inputs(5, 6);
1286 INST(9, Opcode::Return).ref().Inputs(7);
1287 }
1288 BASIC_BLOCK(4, -1)
1289 {
1290 INST(10, Opcode::CatchPhi).ref().Inputs(0, 5);
1291 INST(11, Opcode::Return).ref().Inputs(10);
1292 }
1293 }
1294
1295 GetGraph()->RunPass<AliasAnalysis>();
1296 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1297 GraphChecker(GetGraph()).Check();
1298
1299 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1300 ASSERT_EQ(alias.CheckRefAlias(&INS(10), &INS(0)), AliasType::MAY_ALIAS);
1301 ASSERT_EQ(alias.CheckRefAlias(&INS(10), &INS(5)), AliasType::MAY_ALIAS);
1302 }
1303
1304 /**
1305 * Test the assert that NullCheck is bypassed through RefTypeCheck
1306 */
TEST_F(AliasAnalysisTest,RefTypeCheck)1307 TEST_F(AliasAnalysisTest, RefTypeCheck)
1308 {
1309 GRAPH(GetGraph())
1310 {
1311 PARAMETER(0, 0).ref();
1312 PARAMETER(1, 1).ref();
1313 BASIC_BLOCK(2, 1)
1314 {
1315 INST(10, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
1316 INST(11, Opcode::NullCheck).ref().Inputs(1, 10);
1317 INST(14, Opcode::RefTypeCheck).ref().Inputs(0, 11, 10);
1318 INST(15, Opcode::StoreArrayI).ref().Imm(0).Inputs(0, 14);
1319
1320 INST(6, Opcode::ReturnVoid).v0id();
1321 }
1322 }
1323
1324 GetGraph()->RunPass<AliasAnalysis>();
1325 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1326 GraphChecker(GetGraph()).Check();
1327
1328 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1329 ASSERT_EQ(alias.CheckInstAlias(&INS(15), &INS(15)), AliasType::MUST_ALIAS);
1330 }
1331
1332 /**
1333 * The field access is determined by field reference (if present) rather than TypeId.
1334 */
TEST_F(AliasAnalysisTest,InheritedFields)1335 TEST_F(AliasAnalysisTest, InheritedFields)
1336 {
1337 RuntimeInterface::FieldPtr field = (void *)(0xDEADBEEF);
1338 GRAPH(GetGraph())
1339 {
1340 BASIC_BLOCK(2, 1)
1341 {
1342 INST(1, Opcode::SaveState).NoVregs();
1343 INST(2, Opcode::LoadAndInitClass).ref().Inputs(1);
1344 INST(3, Opcode::LoadStatic).ref().Inputs(2).TypeId(377U).ObjField(field);
1345 INST(4, Opcode::StoreStatic).ref().Inputs(2, 3).TypeId(378U).ObjField(field);
1346 INST(5, Opcode::ReturnVoid).v0id();
1347 }
1348 }
1349
1350 GetGraph()->RunPass<AliasAnalysis>();
1351 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1352 GraphChecker(GetGraph()).Check();
1353
1354 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1355 ASSERT_EQ(alias.CheckInstAlias(&INS(3), &INS(4)), AliasType::MUST_ALIAS);
1356 }
1357
TEST_F(AliasAnalysisTest,PairedAccessesAliasing)1358 TEST_F(AliasAnalysisTest, PairedAccessesAliasing)
1359 {
1360 GRAPH(GetGraph())
1361 {
1362 PARAMETER(0, 0).ref();
1363 PARAMETER(1, 1).s32();
1364 BASIC_BLOCK(2, 1)
1365 {
1366 INST(10, Opcode::LoadArrayPairI).ref().Imm(0x0).Inputs(0);
1367 INST(11, Opcode::LoadPairPart).ref().Imm(0x0).Inputs(10);
1368 INST(12, Opcode::LoadPairPart).ref().Imm(0x1).Inputs(10);
1369 INST(14, Opcode::LoadObject).ref().TypeId(3005).Inputs(12);
1370 INST(17, Opcode::StoreArrayI).s32().Imm(0x0).Inputs(14, 1);
1371 INST(18, Opcode::ReturnVoid).v0id();
1372 }
1373 }
1374
1375 GetGraph()->RunPass<AliasAnalysis>();
1376 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1377 GraphChecker(GetGraph()).Check();
1378
1379 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1380 ASSERT_EQ(alias.CheckInstAlias(&INS(17), &INS(17)), AliasType::MUST_ALIAS);
1381 }
1382
1383 /**
1384 * Volatile load does not quarantee that the same value would be loaded next time.
1385 */
TEST_F(AliasAnalysisTest,VolatileAliasing)1386 TEST_F(AliasAnalysisTest, VolatileAliasing)
1387 {
1388 GRAPH(GetGraph())
1389 {
1390 PARAMETER(0, 0).ref();
1391 PARAMETER(1, 1).ref();
1392 BASIC_BLOCK(2, 1)
1393 {
1394 INST(11, Opcode::LoadObject).ref().TypeId(3005).Volatile().Inputs(0);
1395 INST(12, Opcode::LoadObject).ref().TypeId(3005).Volatile().Inputs(0);
1396 INST(13, Opcode::LoadObject).s32().TypeId(4005).Inputs(11);
1397 INST(14, Opcode::LoadObject).s32().TypeId(4005).Inputs(12);
1398 INST(15, Opcode::Add).s32().Inputs(13, 14);
1399
1400 INST(16, Opcode::SaveState).Inputs(0).SrcVregs({0});
1401 INST(17, Opcode::LoadAndInitClass).ref().Inputs(16).TypeId(0U);
1402 INST(18, Opcode::LoadStatic).ref().TypeId(5005).Volatile().Inputs(17);
1403 INST(19, Opcode::LoadStatic).ref().TypeId(5005).Volatile().Inputs(17);
1404 INST(20, Opcode::LoadObject).s32().TypeId(4005).Inputs(18);
1405 INST(21, Opcode::LoadObject).s32().TypeId(4005).Inputs(19);
1406 INST(22, Opcode::Add).s32().Inputs(20, 21);
1407 INST(23, Opcode::Add).s32().Inputs(15, 22);
1408 INST(24, Opcode::Return).s32().Inputs(23);
1409 }
1410 }
1411
1412 GetGraph()->RunPass<AliasAnalysis>();
1413 EXPECT_TRUE(GetGraph()->IsAnalysisValid<AliasAnalysis>());
1414 GraphChecker(GetGraph()).Check();
1415
1416 AliasAnalysis &alias = GetGraph()->GetAnalysis<AliasAnalysis>();
1417 ASSERT_EQ(alias.CheckInstAlias(&INS(13), &INS(14)), AliasType::MAY_ALIAS);
1418 ASSERT_EQ(alias.CheckInstAlias(&INS(20), &INS(21)), AliasType::MAY_ALIAS);
1419 ASSERT_EQ(alias.CheckInstAlias(&INS(13), &INS(21)), AliasType::MAY_ALIAS);
1420 }
1421 } // namespace panda::compiler
1422