1 /*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "load_store_analysis.h"
18 #include "nodes.h"
19 #include "optimizing_unit_test.h"
20
21 #include "gtest/gtest.h"
22
23 namespace art {
24
25 class LoadStoreAnalysisTest : public OptimizingUnitTest {
26 public:
LoadStoreAnalysisTest()27 LoadStoreAnalysisTest() : graph_(CreateGraph()) { }
28
29 HGraph* graph_;
30 };
31
TEST_F(LoadStoreAnalysisTest,ArrayHeapLocations)32 TEST_F(LoadStoreAnalysisTest, ArrayHeapLocations) {
33 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
34 graph_->AddBlock(entry);
35 graph_->SetEntryBlock(entry);
36
37 // entry:
38 // array ParameterValue
39 // index ParameterValue
40 // c1 IntConstant
41 // c2 IntConstant
42 // c3 IntConstant
43 // array_get1 ArrayGet [array, c1]
44 // array_get2 ArrayGet [array, c2]
45 // array_set1 ArraySet [array, c1, c3]
46 // array_set2 ArraySet [array, index, c3]
47 HInstruction* array = new (GetAllocator()) HParameterValue(
48 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
49 HInstruction* index = new (GetAllocator()) HParameterValue(
50 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
51 HInstruction* c1 = graph_->GetIntConstant(1);
52 HInstruction* c2 = graph_->GetIntConstant(2);
53 HInstruction* c3 = graph_->GetIntConstant(3);
54 HInstruction* array_get1 = new (GetAllocator()) HArrayGet(array, c1, DataType::Type::kInt32, 0);
55 HInstruction* array_get2 = new (GetAllocator()) HArrayGet(array, c2, DataType::Type::kInt32, 0);
56 HInstruction* array_set1 =
57 new (GetAllocator()) HArraySet(array, c1, c3, DataType::Type::kInt32, 0);
58 HInstruction* array_set2 =
59 new (GetAllocator()) HArraySet(array, index, c3, DataType::Type::kInt32, 0);
60 entry->AddInstruction(array);
61 entry->AddInstruction(index);
62 entry->AddInstruction(array_get1);
63 entry->AddInstruction(array_get2);
64 entry->AddInstruction(array_set1);
65 entry->AddInstruction(array_set2);
66
67 // Test HeapLocationCollector initialization.
68 // Should be no heap locations, no operations on the heap.
69 HeapLocationCollector heap_location_collector(graph_);
70 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U);
71 ASSERT_FALSE(heap_location_collector.HasHeapStores());
72
73 // Test that after visiting the graph_, it must see following heap locations
74 // array[c1], array[c2], array[index]; and it should see heap stores.
75 heap_location_collector.VisitBasicBlock(entry);
76 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 3U);
77 ASSERT_TRUE(heap_location_collector.HasHeapStores());
78
79 // Test queries on HeapLocationCollector's ref info and index records.
80 ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(array);
81 DataType::Type type = DataType::Type::kInt32;
82 size_t field = HeapLocation::kInvalidFieldOffset;
83 size_t vec = HeapLocation::kScalar;
84 size_t class_def = HeapLocation::kDeclaringClassDefIndexForArrays;
85 size_t loc1 = heap_location_collector.FindHeapLocationIndex(
86 ref, type, field, c1, vec, class_def);
87 size_t loc2 = heap_location_collector.FindHeapLocationIndex(
88 ref, type, field, c2, vec, class_def);
89 size_t loc3 = heap_location_collector.FindHeapLocationIndex(
90 ref, type, field, index, vec, class_def);
91 // must find this reference info for array in HeapLocationCollector.
92 ASSERT_TRUE(ref != nullptr);
93 // must find these heap locations;
94 // and array[1], array[2], array[3] should be different heap locations.
95 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
96 ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound);
97 ASSERT_TRUE(loc3 != HeapLocationCollector::kHeapLocationNotFound);
98 ASSERT_TRUE(loc1 != loc2);
99 ASSERT_TRUE(loc2 != loc3);
100 ASSERT_TRUE(loc1 != loc3);
101
102 // Test alias relationships after building aliasing matrix.
103 // array[1] and array[2] clearly should not alias;
104 // array[index] should alias with the others, because index is an unknow value.
105 heap_location_collector.BuildAliasingMatrix();
106 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
107 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc3));
108 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc3));
109
110 EXPECT_TRUE(CheckGraph(graph_));
111 }
112
TEST_F(LoadStoreAnalysisTest,FieldHeapLocations)113 TEST_F(LoadStoreAnalysisTest, FieldHeapLocations) {
114 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
115 graph_->AddBlock(entry);
116 graph_->SetEntryBlock(entry);
117
118 // entry:
119 // object ParameterValue
120 // c1 IntConstant
121 // set_field10 InstanceFieldSet [object, c1, 10]
122 // get_field10 InstanceFieldGet [object, 10]
123 // get_field20 InstanceFieldGet [object, 20]
124
125 HInstruction* c1 = graph_->GetIntConstant(1);
126 HInstruction* object = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
127 dex::TypeIndex(0),
128 0,
129 DataType::Type::kReference);
130 HInstanceFieldSet* set_field10 = new (GetAllocator()) HInstanceFieldSet(object,
131 c1,
132 nullptr,
133 DataType::Type::kInt32,
134 MemberOffset(10),
135 false,
136 kUnknownFieldIndex,
137 kUnknownClassDefIndex,
138 graph_->GetDexFile(),
139 0);
140 HInstanceFieldGet* get_field10 = new (GetAllocator()) HInstanceFieldGet(object,
141 nullptr,
142 DataType::Type::kInt32,
143 MemberOffset(10),
144 false,
145 kUnknownFieldIndex,
146 kUnknownClassDefIndex,
147 graph_->GetDexFile(),
148 0);
149 HInstanceFieldGet* get_field20 = new (GetAllocator()) HInstanceFieldGet(object,
150 nullptr,
151 DataType::Type::kInt32,
152 MemberOffset(20),
153 false,
154 kUnknownFieldIndex,
155 kUnknownClassDefIndex,
156 graph_->GetDexFile(),
157 0);
158 entry->AddInstruction(object);
159 entry->AddInstruction(set_field10);
160 entry->AddInstruction(get_field10);
161 entry->AddInstruction(get_field20);
162
163 // Test HeapLocationCollector initialization.
164 // Should be no heap locations, no operations on the heap.
165 HeapLocationCollector heap_location_collector(graph_);
166 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U);
167 ASSERT_FALSE(heap_location_collector.HasHeapStores());
168
169 // Test that after visiting the graph, it must see following heap locations
170 // object.field10, object.field20 and it should see heap stores.
171 heap_location_collector.VisitBasicBlock(entry);
172 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 2U);
173 ASSERT_TRUE(heap_location_collector.HasHeapStores());
174
175 // Test queries on HeapLocationCollector's ref info and index records.
176 ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(object);
177 size_t loc1 = heap_location_collector.GetFieldHeapLocation(object, &get_field10->GetFieldInfo());
178 size_t loc2 = heap_location_collector.GetFieldHeapLocation(object, &get_field20->GetFieldInfo());
179 // must find references info for object and in HeapLocationCollector.
180 ASSERT_TRUE(ref != nullptr);
181 // must find these heap locations.
182 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
183 ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound);
184 // different fields of same object.
185 ASSERT_TRUE(loc1 != loc2);
186 // accesses to different fields of the same object should not alias.
187 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
188
189 EXPECT_TRUE(CheckGraph(graph_));
190 }
191
TEST_F(LoadStoreAnalysisTest,ArrayIndexAliasingTest)192 TEST_F(LoadStoreAnalysisTest, ArrayIndexAliasingTest) {
193 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
194 graph_->AddBlock(entry);
195 graph_->SetEntryBlock(entry);
196 graph_->BuildDominatorTree();
197
198 HInstruction* array = new (GetAllocator()) HParameterValue(
199 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
200 HInstruction* index = new (GetAllocator()) HParameterValue(
201 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
202 HInstruction* c0 = graph_->GetIntConstant(0);
203 HInstruction* c1 = graph_->GetIntConstant(1);
204 HInstruction* c_neg1 = graph_->GetIntConstant(-1);
205 HInstruction* add0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c0);
206 HInstruction* add1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c1);
207 HInstruction* sub0 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c0);
208 HInstruction* sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c1);
209 HInstruction* sub_neg1 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c_neg1);
210 HInstruction* rev_sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, c1, index);
211 HInstruction* arr_set1 = new (GetAllocator()) HArraySet(array, c0, c0, DataType::Type::kInt32, 0);
212 HInstruction* arr_set2 = new (GetAllocator()) HArraySet(array, c1, c0, DataType::Type::kInt32, 0);
213 HInstruction* arr_set3 =
214 new (GetAllocator()) HArraySet(array, add0, c0, DataType::Type::kInt32, 0);
215 HInstruction* arr_set4 =
216 new (GetAllocator()) HArraySet(array, add1, c0, DataType::Type::kInt32, 0);
217 HInstruction* arr_set5 =
218 new (GetAllocator()) HArraySet(array, sub0, c0, DataType::Type::kInt32, 0);
219 HInstruction* arr_set6 =
220 new (GetAllocator()) HArraySet(array, sub1, c0, DataType::Type::kInt32, 0);
221 HInstruction* arr_set7 =
222 new (GetAllocator()) HArraySet(array, rev_sub1, c0, DataType::Type::kInt32, 0);
223 HInstruction* arr_set8 =
224 new (GetAllocator()) HArraySet(array, sub_neg1, c0, DataType::Type::kInt32, 0);
225
226 entry->AddInstruction(array);
227 entry->AddInstruction(index);
228 entry->AddInstruction(add0);
229 entry->AddInstruction(add1);
230 entry->AddInstruction(sub0);
231 entry->AddInstruction(sub1);
232 entry->AddInstruction(sub_neg1);
233 entry->AddInstruction(rev_sub1);
234
235 entry->AddInstruction(arr_set1); // array[0] = c0
236 entry->AddInstruction(arr_set2); // array[1] = c0
237 entry->AddInstruction(arr_set3); // array[i+0] = c0
238 entry->AddInstruction(arr_set4); // array[i+1] = c0
239 entry->AddInstruction(arr_set5); // array[i-0] = c0
240 entry->AddInstruction(arr_set6); // array[i-1] = c0
241 entry->AddInstruction(arr_set7); // array[1-i] = c0
242 entry->AddInstruction(arr_set8); // array[i-(-1)] = c0
243
244 LoadStoreAnalysis lsa(graph_);
245 lsa.Run();
246 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
247
248 // LSA/HeapLocationCollector should see those ArrayGet instructions.
249 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U);
250 ASSERT_TRUE(heap_location_collector.HasHeapStores());
251
252 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
253 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
254 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
255
256 // Test alias: array[0] and array[1]
257 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set1);
258 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set2);
259 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
260
261 // Test alias: array[i+0] and array[i-0]
262 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set3);
263 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set5);
264 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
265
266 // Test alias: array[i+1] and array[i-1]
267 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
268 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set6);
269 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
270
271 // Test alias: array[i+1] and array[1-i]
272 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
273 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set7);
274 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
275
276 // Test alias: array[i+1] and array[i-(-1)]
277 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
278 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set8);
279 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
280
281 EXPECT_TRUE(CheckGraphSkipRefTypeInfoChecks(graph_));
282 }
283
TEST_F(LoadStoreAnalysisTest,ArrayAliasingTest)284 TEST_F(LoadStoreAnalysisTest, ArrayAliasingTest) {
285 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
286 graph_->AddBlock(entry);
287 graph_->SetEntryBlock(entry);
288 graph_->BuildDominatorTree();
289
290 HInstruction* array = new (GetAllocator()) HParameterValue(
291 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
292 HInstruction* index = new (GetAllocator()) HParameterValue(
293 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
294 HInstruction* c0 = graph_->GetIntConstant(0);
295 HInstruction* c1 = graph_->GetIntConstant(1);
296 HInstruction* c6 = graph_->GetIntConstant(6);
297 HInstruction* c8 = graph_->GetIntConstant(8);
298
299 HInstruction* arr_set_0 = new (GetAllocator()) HArraySet(array,
300 c0,
301 c0,
302 DataType::Type::kInt32,
303 0);
304 HInstruction* arr_set_1 = new (GetAllocator()) HArraySet(array,
305 c1,
306 c0,
307 DataType::Type::kInt32,
308 0);
309 HInstruction* arr_set_i = new (GetAllocator()) HArraySet(array,
310 index,
311 c0,
312 DataType::Type::kInt32,
313 0);
314
315 HVecOperation* v1 = new (GetAllocator()) HVecReplicateScalar(GetAllocator(),
316 c1,
317 DataType::Type::kInt32,
318 4,
319 kNoDexPc);
320 HVecOperation* v2 = new (GetAllocator()) HVecReplicateScalar(GetAllocator(),
321 c1,
322 DataType::Type::kInt32,
323 2,
324 kNoDexPc);
325 HInstruction* i_add6 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c6);
326 HInstruction* i_add8 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c8);
327
328 HInstruction* vstore_0 = new (GetAllocator()) HVecStore(
329 GetAllocator(),
330 array,
331 c0,
332 v1,
333 DataType::Type::kInt32,
334 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
335 4,
336 kNoDexPc);
337 HInstruction* vstore_1 = new (GetAllocator()) HVecStore(
338 GetAllocator(),
339 array,
340 c1,
341 v1,
342 DataType::Type::kInt32,
343 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
344 4,
345 kNoDexPc);
346 HInstruction* vstore_8 = new (GetAllocator()) HVecStore(
347 GetAllocator(),
348 array,
349 c8,
350 v1,
351 DataType::Type::kInt32,
352 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
353 4,
354 kNoDexPc);
355 HInstruction* vstore_i = new (GetAllocator()) HVecStore(
356 GetAllocator(),
357 array,
358 index,
359 v1,
360 DataType::Type::kInt32,
361 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
362 4,
363 kNoDexPc);
364 HInstruction* vstore_i_add6 = new (GetAllocator()) HVecStore(
365 GetAllocator(),
366 array,
367 i_add6,
368 v1,
369 DataType::Type::kInt32,
370 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
371 4,
372 kNoDexPc);
373 HInstruction* vstore_i_add8 = new (GetAllocator()) HVecStore(
374 GetAllocator(),
375 array,
376 i_add8,
377 v1,
378 DataType::Type::kInt32,
379 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
380 4,
381 kNoDexPc);
382 HInstruction* vstore_i_add6_vlen2 = new (GetAllocator()) HVecStore(
383 GetAllocator(),
384 array,
385 i_add6,
386 v2,
387 DataType::Type::kInt32,
388 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
389 2,
390 kNoDexPc);
391
392 entry->AddInstruction(array);
393 entry->AddInstruction(index);
394
395 entry->AddInstruction(arr_set_0);
396 entry->AddInstruction(arr_set_1);
397 entry->AddInstruction(arr_set_i);
398 entry->AddInstruction(v1);
399 entry->AddInstruction(v2);
400 entry->AddInstruction(i_add6);
401 entry->AddInstruction(i_add8);
402 entry->AddInstruction(vstore_0);
403 entry->AddInstruction(vstore_1);
404 entry->AddInstruction(vstore_8);
405 entry->AddInstruction(vstore_i);
406 entry->AddInstruction(vstore_i_add6);
407 entry->AddInstruction(vstore_i_add8);
408 entry->AddInstruction(vstore_i_add6_vlen2);
409
410 LoadStoreAnalysis lsa(graph_);
411 lsa.Run();
412 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
413
414 // LSA/HeapLocationCollector should see those instructions.
415 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 10U);
416 ASSERT_TRUE(heap_location_collector.HasHeapStores());
417
418 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
419 size_t loc1, loc2;
420
421 // Test alias: array[0] and array[0,1,2,3]
422 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
423 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
424 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
425
426 // Test alias: array[0] and array[1,2,3,4]
427 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
428 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1);
429 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
430
431 // Test alias: array[0] and array[8,9,10,11]
432 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
433 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
434 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
435
436 // Test alias: array[1] and array[8,9,10,11]
437 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
438 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
439 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
440
441 // Test alias: array[1] and array[0,1,2,3]
442 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
443 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
444 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
445
446 // Test alias: array[0,1,2,3] and array[8,9,10,11]
447 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0);
448 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
449 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
450
451 // Test alias: array[0,1,2,3] and array[1,2,3,4]
452 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0);
453 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1);
454 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
455
456 // Test alias: array[0] and array[i,i+1,i+2,i+3]
457 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
458 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
459 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
460
461 // Test alias: array[i] and array[0,1,2,3]
462 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
463 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
464 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
465
466 // Test alias: array[i] and array[i,i+1,i+2,i+3]
467 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
468 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
469 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
470
471 // Test alias: array[i] and array[i+8,i+9,i+10,i+11]
472 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
473 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
474 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
475
476 // Test alias: array[i+6,i+7,i+8,i+9] and array[i+8,i+9,i+10,i+11]
477 // Test partial overlap.
478 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6);
479 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
480 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
481
482 // Test alias: array[i+6,i+7] and array[i,i+1,i+2,i+3]
483 // Test different vector lengths.
484 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2);
485 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
486 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
487
488 // Test alias: array[i+6,i+7] and array[i+8,i+9,i+10,i+11]
489 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2);
490 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
491 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
492 }
493
TEST_F(LoadStoreAnalysisTest,ArrayIndexCalculationOverflowTest)494 TEST_F(LoadStoreAnalysisTest, ArrayIndexCalculationOverflowTest) {
495 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
496 graph_->AddBlock(entry);
497 graph_->SetEntryBlock(entry);
498 graph_->BuildDominatorTree();
499
500 HInstruction* array = new (GetAllocator()) HParameterValue(
501 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
502 HInstruction* index = new (GetAllocator()) HParameterValue(
503 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
504
505 HInstruction* c0 = graph_->GetIntConstant(0);
506 HInstruction* c_0x80000000 = graph_->GetIntConstant(0x80000000);
507 HInstruction* c_0x10 = graph_->GetIntConstant(0x10);
508 HInstruction* c_0xFFFFFFF0 = graph_->GetIntConstant(0xFFFFFFF0);
509 HInstruction* c_0x7FFFFFFF = graph_->GetIntConstant(0x7FFFFFFF);
510 HInstruction* c_0x80000001 = graph_->GetIntConstant(0x80000001);
511
512 // `index+0x80000000` and `index-0x80000000` array indices MAY alias.
513 HInstruction* add_0x80000000 = new (GetAllocator()) HAdd(
514 DataType::Type::kInt32, index, c_0x80000000);
515 HInstruction* sub_0x80000000 = new (GetAllocator()) HSub(
516 DataType::Type::kInt32, index, c_0x80000000);
517 HInstruction* arr_set_1 = new (GetAllocator()) HArraySet(
518 array, add_0x80000000, c0, DataType::Type::kInt32, 0);
519 HInstruction* arr_set_2 = new (GetAllocator()) HArraySet(
520 array, sub_0x80000000, c0, DataType::Type::kInt32, 0);
521
522 // `index+0x10` and `index-0xFFFFFFF0` array indices MAY alias.
523 HInstruction* add_0x10 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c_0x10);
524 HInstruction* sub_0xFFFFFFF0 = new (GetAllocator()) HSub(
525 DataType::Type::kInt32, index, c_0xFFFFFFF0);
526 HInstruction* arr_set_3 = new (GetAllocator()) HArraySet(
527 array, add_0x10, c0, DataType::Type::kInt32, 0);
528 HInstruction* arr_set_4 = new (GetAllocator()) HArraySet(
529 array, sub_0xFFFFFFF0, c0, DataType::Type::kInt32, 0);
530
531 // `index+0x7FFFFFFF` and `index-0x80000001` array indices MAY alias.
532 HInstruction* add_0x7FFFFFFF = new (GetAllocator()) HAdd(
533 DataType::Type::kInt32, index, c_0x7FFFFFFF);
534 HInstruction* sub_0x80000001 = new (GetAllocator()) HSub(
535 DataType::Type::kInt32, index, c_0x80000001);
536 HInstruction* arr_set_5 = new (GetAllocator()) HArraySet(
537 array, add_0x7FFFFFFF, c0, DataType::Type::kInt32, 0);
538 HInstruction* arr_set_6 = new (GetAllocator()) HArraySet(
539 array, sub_0x80000001, c0, DataType::Type::kInt32, 0);
540
541 // `index+0` and `index-0` array indices MAY alias.
542 HInstruction* add_0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c0);
543 HInstruction* sub_0 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c0);
544 HInstruction* arr_set_7 = new (GetAllocator()) HArraySet(
545 array, add_0, c0, DataType::Type::kInt32, 0);
546 HInstruction* arr_set_8 = new (GetAllocator()) HArraySet(
547 array, sub_0, c0, DataType::Type::kInt32, 0);
548
549 entry->AddInstruction(array);
550 entry->AddInstruction(index);
551 entry->AddInstruction(add_0x80000000);
552 entry->AddInstruction(sub_0x80000000);
553 entry->AddInstruction(add_0x10);
554 entry->AddInstruction(sub_0xFFFFFFF0);
555 entry->AddInstruction(add_0x7FFFFFFF);
556 entry->AddInstruction(sub_0x80000001);
557 entry->AddInstruction(add_0);
558 entry->AddInstruction(sub_0);
559 entry->AddInstruction(arr_set_1);
560 entry->AddInstruction(arr_set_2);
561 entry->AddInstruction(arr_set_3);
562 entry->AddInstruction(arr_set_4);
563 entry->AddInstruction(arr_set_5);
564 entry->AddInstruction(arr_set_6);
565 entry->AddInstruction(arr_set_7);
566 entry->AddInstruction(arr_set_8);
567
568 LoadStoreAnalysis lsa(graph_);
569 lsa.Run();
570 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
571
572 // LSA/HeapLocationCollector should see those ArrayGet instructions.
573 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U);
574 ASSERT_TRUE(heap_location_collector.HasHeapStores());
575
576 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
577 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
578 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
579
580 // Test alias: array[i+0x80000000] and array[i-0x80000000]
581 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
582 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
583 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
584
585 // Test alias: array[i+0x10] and array[i-0xFFFFFFF0]
586 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_3);
587 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_4);
588 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
589
590 // Test alias: array[i+0x7FFFFFFF] and array[i-0x80000001]
591 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_5);
592 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6);
593 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
594
595 // Test alias: array[i+0] and array[i-0]
596 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7);
597 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_8);
598 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
599
600 // Should not alias:
601 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
602 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6);
603 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
604
605 // Should not alias:
606 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7);
607 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
608 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
609 }
610
TEST_F(LoadStoreAnalysisTest,TestHuntOriginalRef)611 TEST_F(LoadStoreAnalysisTest, TestHuntOriginalRef) {
612 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
613 graph_->AddBlock(entry);
614 graph_->SetEntryBlock(entry);
615
616 // Different ways where orignal array reference are transformed & passed to ArrayGet.
617 // ParameterValue --> ArrayGet
618 // ParameterValue --> BoundType --> ArrayGet
619 // ParameterValue --> BoundType --> NullCheck --> ArrayGet
620 // ParameterValue --> BoundType --> NullCheck --> IntermediateAddress --> ArrayGet
621 HInstruction* c1 = graph_->GetIntConstant(1);
622 HInstruction* array = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
623 dex::TypeIndex(0),
624 0,
625 DataType::Type::kReference);
626 HInstruction* array_get1 = new (GetAllocator()) HArrayGet(array,
627 c1,
628 DataType::Type::kInt32,
629 0);
630
631 HInstruction* bound_type = new (GetAllocator()) HBoundType(array);
632 HInstruction* array_get2 = new (GetAllocator()) HArrayGet(bound_type,
633 c1,
634 DataType::Type::kInt32,
635 0);
636
637 HInstruction* null_check = new (GetAllocator()) HNullCheck(bound_type, 0);
638 HInstruction* array_get3 = new (GetAllocator()) HArrayGet(null_check,
639 c1,
640 DataType::Type::kInt32,
641 0);
642
643 HInstruction* inter_addr = new (GetAllocator()) HIntermediateAddress(null_check, c1, 0);
644 HInstruction* array_get4 = new (GetAllocator()) HArrayGet(inter_addr,
645 c1,
646 DataType::Type::kInt32,
647 0);
648 entry->AddInstruction(array);
649 entry->AddInstruction(array_get1);
650 entry->AddInstruction(bound_type);
651 entry->AddInstruction(array_get2);
652 entry->AddInstruction(null_check);
653 entry->AddInstruction(array_get3);
654 entry->AddInstruction(inter_addr);
655 entry->AddInstruction(array_get4);
656
657 HeapLocationCollector heap_location_collector(graph_);
658 heap_location_collector.VisitBasicBlock(entry);
659
660 // Test that the HeapLocationCollector should be able to tell
661 // that there is only ONE array location, no matter how many
662 // times the original reference has been transformed by BoundType,
663 // NullCheck, IntermediateAddress, etc.
664 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 1U);
665 size_t loc1 = heap_location_collector.GetArrayHeapLocation(array_get1);
666 size_t loc2 = heap_location_collector.GetArrayHeapLocation(array_get2);
667 size_t loc3 = heap_location_collector.GetArrayHeapLocation(array_get3);
668 size_t loc4 = heap_location_collector.GetArrayHeapLocation(array_get4);
669 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
670 ASSERT_EQ(loc1, loc2);
671 ASSERT_EQ(loc1, loc3);
672 ASSERT_EQ(loc1, loc4);
673 }
674
675 } // namespace art
676