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
TEST_F(LoadStoreAnalysisTest,FieldHeapLocations)111 TEST_F(LoadStoreAnalysisTest, FieldHeapLocations) {
112 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
113 graph_->AddBlock(entry);
114 graph_->SetEntryBlock(entry);
115
116 // entry:
117 // object ParameterValue
118 // c1 IntConstant
119 // set_field10 InstanceFieldSet [object, c1, 10]
120 // get_field10 InstanceFieldGet [object, 10]
121 // get_field20 InstanceFieldGet [object, 20]
122
123 HInstruction* c1 = graph_->GetIntConstant(1);
124 HInstruction* object = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
125 dex::TypeIndex(0),
126 0,
127 DataType::Type::kReference);
128 HInstanceFieldSet* set_field10 = new (GetAllocator()) HInstanceFieldSet(object,
129 c1,
130 nullptr,
131 DataType::Type::kInt32,
132 MemberOffset(10),
133 false,
134 kUnknownFieldIndex,
135 kUnknownClassDefIndex,
136 graph_->GetDexFile(),
137 0);
138 HInstanceFieldGet* get_field10 = new (GetAllocator()) HInstanceFieldGet(object,
139 nullptr,
140 DataType::Type::kInt32,
141 MemberOffset(10),
142 false,
143 kUnknownFieldIndex,
144 kUnknownClassDefIndex,
145 graph_->GetDexFile(),
146 0);
147 HInstanceFieldGet* get_field20 = new (GetAllocator()) HInstanceFieldGet(object,
148 nullptr,
149 DataType::Type::kInt32,
150 MemberOffset(20),
151 false,
152 kUnknownFieldIndex,
153 kUnknownClassDefIndex,
154 graph_->GetDexFile(),
155 0);
156 entry->AddInstruction(object);
157 entry->AddInstruction(set_field10);
158 entry->AddInstruction(get_field10);
159 entry->AddInstruction(get_field20);
160
161 // Test HeapLocationCollector initialization.
162 // Should be no heap locations, no operations on the heap.
163 HeapLocationCollector heap_location_collector(graph_);
164 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U);
165 ASSERT_FALSE(heap_location_collector.HasHeapStores());
166
167 // Test that after visiting the graph, it must see following heap locations
168 // object.field10, object.field20 and it should see heap stores.
169 heap_location_collector.VisitBasicBlock(entry);
170 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 2U);
171 ASSERT_TRUE(heap_location_collector.HasHeapStores());
172
173 // Test queries on HeapLocationCollector's ref info and index records.
174 ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(object);
175 size_t loc1 = heap_location_collector.GetFieldHeapLocation(object, &get_field10->GetFieldInfo());
176 size_t loc2 = heap_location_collector.GetFieldHeapLocation(object, &get_field20->GetFieldInfo());
177 // must find references info for object and in HeapLocationCollector.
178 ASSERT_TRUE(ref != nullptr);
179 // must find these heap locations.
180 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
181 ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound);
182 // different fields of same object.
183 ASSERT_TRUE(loc1 != loc2);
184 // accesses to different fields of the same object should not alias.
185 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
186 }
187
TEST_F(LoadStoreAnalysisTest,ArrayIndexAliasingTest)188 TEST_F(LoadStoreAnalysisTest, ArrayIndexAliasingTest) {
189 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
190 graph_->AddBlock(entry);
191 graph_->SetEntryBlock(entry);
192 graph_->BuildDominatorTree();
193
194 HInstruction* array = new (GetAllocator()) HParameterValue(
195 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
196 HInstruction* index = new (GetAllocator()) HParameterValue(
197 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
198 HInstruction* c0 = graph_->GetIntConstant(0);
199 HInstruction* c1 = graph_->GetIntConstant(1);
200 HInstruction* c_neg1 = graph_->GetIntConstant(-1);
201 HInstruction* add0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c0);
202 HInstruction* add1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c1);
203 HInstruction* sub0 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c0);
204 HInstruction* sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c1);
205 HInstruction* sub_neg1 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c_neg1);
206 HInstruction* rev_sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, c1, index);
207 HInstruction* arr_set1 = new (GetAllocator()) HArraySet(array, c0, c0, DataType::Type::kInt32, 0);
208 HInstruction* arr_set2 = new (GetAllocator()) HArraySet(array, c1, c0, DataType::Type::kInt32, 0);
209 HInstruction* arr_set3 =
210 new (GetAllocator()) HArraySet(array, add0, c0, DataType::Type::kInt32, 0);
211 HInstruction* arr_set4 =
212 new (GetAllocator()) HArraySet(array, add1, c0, DataType::Type::kInt32, 0);
213 HInstruction* arr_set5 =
214 new (GetAllocator()) HArraySet(array, sub0, c0, DataType::Type::kInt32, 0);
215 HInstruction* arr_set6 =
216 new (GetAllocator()) HArraySet(array, sub1, c0, DataType::Type::kInt32, 0);
217 HInstruction* arr_set7 =
218 new (GetAllocator()) HArraySet(array, rev_sub1, c0, DataType::Type::kInt32, 0);
219 HInstruction* arr_set8 =
220 new (GetAllocator()) HArraySet(array, sub_neg1, c0, DataType::Type::kInt32, 0);
221
222 entry->AddInstruction(array);
223 entry->AddInstruction(index);
224 entry->AddInstruction(add0);
225 entry->AddInstruction(add1);
226 entry->AddInstruction(sub0);
227 entry->AddInstruction(sub1);
228 entry->AddInstruction(sub_neg1);
229 entry->AddInstruction(rev_sub1);
230
231 entry->AddInstruction(arr_set1); // array[0] = c0
232 entry->AddInstruction(arr_set2); // array[1] = c0
233 entry->AddInstruction(arr_set3); // array[i+0] = c0
234 entry->AddInstruction(arr_set4); // array[i+1] = c0
235 entry->AddInstruction(arr_set5); // array[i-0] = c0
236 entry->AddInstruction(arr_set6); // array[i-1] = c0
237 entry->AddInstruction(arr_set7); // array[1-i] = c0
238 entry->AddInstruction(arr_set8); // array[i-(-1)] = c0
239
240 LoadStoreAnalysis lsa(graph_);
241 lsa.Run();
242 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
243
244 // LSA/HeapLocationCollector should see those ArrayGet instructions.
245 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U);
246 ASSERT_TRUE(heap_location_collector.HasHeapStores());
247
248 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
249 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
250 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
251
252 // Test alias: array[0] and array[1]
253 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set1);
254 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set2);
255 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
256
257 // Test alias: array[i+0] and array[i-0]
258 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set3);
259 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set5);
260 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
261
262 // Test alias: array[i+1] and array[i-1]
263 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
264 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set6);
265 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
266
267 // Test alias: array[i+1] and array[1-i]
268 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
269 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set7);
270 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
271
272 // Test alias: array[i+1] and array[i-(-1)]
273 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4);
274 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set8);
275 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
276 }
277
TEST_F(LoadStoreAnalysisTest,ArrayAliasingTest)278 TEST_F(LoadStoreAnalysisTest, ArrayAliasingTest) {
279 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
280 graph_->AddBlock(entry);
281 graph_->SetEntryBlock(entry);
282 graph_->BuildDominatorTree();
283
284 HInstruction* array = new (GetAllocator()) HParameterValue(
285 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
286 HInstruction* index = new (GetAllocator()) HParameterValue(
287 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
288 HInstruction* c0 = graph_->GetIntConstant(0);
289 HInstruction* c1 = graph_->GetIntConstant(1);
290 HInstruction* c6 = graph_->GetIntConstant(6);
291 HInstruction* c8 = graph_->GetIntConstant(8);
292
293 HInstruction* arr_set_0 = new (GetAllocator()) HArraySet(array,
294 c0,
295 c0,
296 DataType::Type::kInt32,
297 0);
298 HInstruction* arr_set_1 = new (GetAllocator()) HArraySet(array,
299 c1,
300 c0,
301 DataType::Type::kInt32,
302 0);
303 HInstruction* arr_set_i = new (GetAllocator()) HArraySet(array,
304 index,
305 c0,
306 DataType::Type::kInt32,
307 0);
308
309 HVecOperation* v1 = new (GetAllocator()) HVecReplicateScalar(GetAllocator(),
310 c1,
311 DataType::Type::kInt32,
312 4,
313 kNoDexPc);
314 HVecOperation* v2 = new (GetAllocator()) HVecReplicateScalar(GetAllocator(),
315 c1,
316 DataType::Type::kInt32,
317 2,
318 kNoDexPc);
319 HInstruction* i_add6 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c6);
320 HInstruction* i_add8 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c8);
321
322 HInstruction* vstore_0 = new (GetAllocator()) HVecStore(
323 GetAllocator(),
324 array,
325 c0,
326 v1,
327 DataType::Type::kInt32,
328 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
329 4,
330 kNoDexPc);
331 HInstruction* vstore_1 = new (GetAllocator()) HVecStore(
332 GetAllocator(),
333 array,
334 c1,
335 v1,
336 DataType::Type::kInt32,
337 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
338 4,
339 kNoDexPc);
340 HInstruction* vstore_8 = new (GetAllocator()) HVecStore(
341 GetAllocator(),
342 array,
343 c8,
344 v1,
345 DataType::Type::kInt32,
346 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
347 4,
348 kNoDexPc);
349 HInstruction* vstore_i = new (GetAllocator()) HVecStore(
350 GetAllocator(),
351 array,
352 index,
353 v1,
354 DataType::Type::kInt32,
355 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
356 4,
357 kNoDexPc);
358 HInstruction* vstore_i_add6 = new (GetAllocator()) HVecStore(
359 GetAllocator(),
360 array,
361 i_add6,
362 v1,
363 DataType::Type::kInt32,
364 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
365 4,
366 kNoDexPc);
367 HInstruction* vstore_i_add8 = new (GetAllocator()) HVecStore(
368 GetAllocator(),
369 array,
370 i_add8,
371 v1,
372 DataType::Type::kInt32,
373 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
374 4,
375 kNoDexPc);
376 HInstruction* vstore_i_add6_vlen2 = new (GetAllocator()) HVecStore(
377 GetAllocator(),
378 array,
379 i_add6,
380 v2,
381 DataType::Type::kInt32,
382 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
383 2,
384 kNoDexPc);
385
386 entry->AddInstruction(array);
387 entry->AddInstruction(index);
388
389 entry->AddInstruction(arr_set_0);
390 entry->AddInstruction(arr_set_1);
391 entry->AddInstruction(arr_set_i);
392 entry->AddInstruction(v1);
393 entry->AddInstruction(v2);
394 entry->AddInstruction(i_add6);
395 entry->AddInstruction(i_add8);
396 entry->AddInstruction(vstore_0);
397 entry->AddInstruction(vstore_1);
398 entry->AddInstruction(vstore_8);
399 entry->AddInstruction(vstore_i);
400 entry->AddInstruction(vstore_i_add6);
401 entry->AddInstruction(vstore_i_add8);
402 entry->AddInstruction(vstore_i_add6_vlen2);
403
404 LoadStoreAnalysis lsa(graph_);
405 lsa.Run();
406 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
407
408 // LSA/HeapLocationCollector should see those instructions.
409 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 10U);
410 ASSERT_TRUE(heap_location_collector.HasHeapStores());
411
412 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
413 size_t loc1, loc2;
414
415 // Test alias: array[0] and array[0,1,2,3]
416 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
417 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
418 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
419
420 // Test alias: array[0] and array[1,2,3,4]
421 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
422 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1);
423 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
424
425 // Test alias: array[0] and array[8,9,10,11]
426 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
427 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
428 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
429
430 // Test alias: array[1] and array[8,9,10,11]
431 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
432 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
433 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
434
435 // Test alias: array[1] and array[0,1,2,3]
436 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
437 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
438 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
439
440 // Test alias: array[0,1,2,3] and array[8,9,10,11]
441 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0);
442 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8);
443 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
444
445 // Test alias: array[0,1,2,3] and array[1,2,3,4]
446 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0);
447 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1);
448 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
449
450 // Test alias: array[0] and array[i,i+1,i+2,i+3]
451 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0);
452 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
453 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
454
455 // Test alias: array[i] and array[0,1,2,3]
456 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
457 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0);
458 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
459
460 // Test alias: array[i] and array[i,i+1,i+2,i+3]
461 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
462 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
463 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
464
465 // Test alias: array[i] and array[i+8,i+9,i+10,i+11]
466 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
467 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
468 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
469
470 // Test alias: array[i+6,i+7,i+8,i+9] and array[i+8,i+9,i+10,i+11]
471 // Test partial overlap.
472 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6);
473 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
474 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
475
476 // Test alias: array[i+6,i+7] and array[i,i+1,i+2,i+3]
477 // Test different vector lengths.
478 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2);
479 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i);
480 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
481
482 // Test alias: array[i+6,i+7] and array[i+8,i+9,i+10,i+11]
483 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2);
484 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8);
485 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
486 }
487
TEST_F(LoadStoreAnalysisTest,ArrayIndexCalculationOverflowTest)488 TEST_F(LoadStoreAnalysisTest, ArrayIndexCalculationOverflowTest) {
489 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
490 graph_->AddBlock(entry);
491 graph_->SetEntryBlock(entry);
492 graph_->BuildDominatorTree();
493
494 HInstruction* array = new (GetAllocator()) HParameterValue(
495 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
496 HInstruction* index = new (GetAllocator()) HParameterValue(
497 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
498
499 HInstruction* c0 = graph_->GetIntConstant(0);
500 HInstruction* c_0x80000000 = graph_->GetIntConstant(0x80000000);
501 HInstruction* c_0x10 = graph_->GetIntConstant(0x10);
502 HInstruction* c_0xFFFFFFF0 = graph_->GetIntConstant(0xFFFFFFF0);
503 HInstruction* c_0x7FFFFFFF = graph_->GetIntConstant(0x7FFFFFFF);
504 HInstruction* c_0x80000001 = graph_->GetIntConstant(0x80000001);
505
506 // `index+0x80000000` and `index-0x80000000` array indices MAY alias.
507 HInstruction* add_0x80000000 = new (GetAllocator()) HAdd(
508 DataType::Type::kInt32, index, c_0x80000000);
509 HInstruction* sub_0x80000000 = new (GetAllocator()) HSub(
510 DataType::Type::kInt32, index, c_0x80000000);
511 HInstruction* arr_set_1 = new (GetAllocator()) HArraySet(
512 array, add_0x80000000, c0, DataType::Type::kInt32, 0);
513 HInstruction* arr_set_2 = new (GetAllocator()) HArraySet(
514 array, sub_0x80000000, c0, DataType::Type::kInt32, 0);
515
516 // `index+0x10` and `index-0xFFFFFFF0` array indices MAY alias.
517 HInstruction* add_0x10 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c_0x10);
518 HInstruction* sub_0xFFFFFFF0 = new (GetAllocator()) HSub(
519 DataType::Type::kInt32, index, c_0xFFFFFFF0);
520 HInstruction* arr_set_3 = new (GetAllocator()) HArraySet(
521 array, add_0x10, c0, DataType::Type::kInt32, 0);
522 HInstruction* arr_set_4 = new (GetAllocator()) HArraySet(
523 array, sub_0xFFFFFFF0, c0, DataType::Type::kInt32, 0);
524
525 // `index+0x7FFFFFFF` and `index-0x80000001` array indices MAY alias.
526 HInstruction* add_0x7FFFFFFF = new (GetAllocator()) HAdd(
527 DataType::Type::kInt32, index, c_0x7FFFFFFF);
528 HInstruction* sub_0x80000001 = new (GetAllocator()) HSub(
529 DataType::Type::kInt32, index, c_0x80000001);
530 HInstruction* arr_set_5 = new (GetAllocator()) HArraySet(
531 array, add_0x7FFFFFFF, c0, DataType::Type::kInt32, 0);
532 HInstruction* arr_set_6 = new (GetAllocator()) HArraySet(
533 array, sub_0x80000001, c0, DataType::Type::kInt32, 0);
534
535 // `index+0` and `index-0` array indices MAY alias.
536 HInstruction* add_0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c0);
537 HInstruction* sub_0 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c0);
538 HInstruction* arr_set_7 = new (GetAllocator()) HArraySet(
539 array, add_0, c0, DataType::Type::kInt32, 0);
540 HInstruction* arr_set_8 = new (GetAllocator()) HArraySet(
541 array, sub_0, c0, DataType::Type::kInt32, 0);
542
543 entry->AddInstruction(array);
544 entry->AddInstruction(index);
545 entry->AddInstruction(add_0x80000000);
546 entry->AddInstruction(sub_0x80000000);
547 entry->AddInstruction(add_0x10);
548 entry->AddInstruction(sub_0xFFFFFFF0);
549 entry->AddInstruction(add_0x7FFFFFFF);
550 entry->AddInstruction(sub_0x80000001);
551 entry->AddInstruction(add_0);
552 entry->AddInstruction(sub_0);
553 entry->AddInstruction(arr_set_1);
554 entry->AddInstruction(arr_set_2);
555 entry->AddInstruction(arr_set_3);
556 entry->AddInstruction(arr_set_4);
557 entry->AddInstruction(arr_set_5);
558 entry->AddInstruction(arr_set_6);
559 entry->AddInstruction(arr_set_7);
560 entry->AddInstruction(arr_set_8);
561
562 LoadStoreAnalysis lsa(graph_);
563 lsa.Run();
564 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
565
566 // LSA/HeapLocationCollector should see those ArrayGet instructions.
567 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U);
568 ASSERT_TRUE(heap_location_collector.HasHeapStores());
569
570 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
571 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
572 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
573
574 // Test alias: array[i+0x80000000] and array[i-0x80000000]
575 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1);
576 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
577 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
578
579 // Test alias: array[i+0x10] and array[i-0xFFFFFFF0]
580 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_3);
581 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_4);
582 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
583
584 // Test alias: array[i+0x7FFFFFFF] and array[i-0x80000001]
585 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_5);
586 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6);
587 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
588
589 // Test alias: array[i+0] and array[i-0]
590 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7);
591 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_8);
592 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
593
594 // Should not alias:
595 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
596 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6);
597 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
598
599 // Should not alias:
600 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7);
601 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2);
602 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
603 }
604
TEST_F(LoadStoreAnalysisTest,TestHuntOriginalRef)605 TEST_F(LoadStoreAnalysisTest, TestHuntOriginalRef) {
606 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
607 graph_->AddBlock(entry);
608 graph_->SetEntryBlock(entry);
609
610 // Different ways where orignal array reference are transformed & passed to ArrayGet.
611 // ParameterValue --> ArrayGet
612 // ParameterValue --> BoundType --> ArrayGet
613 // ParameterValue --> BoundType --> NullCheck --> ArrayGet
614 // ParameterValue --> BoundType --> NullCheck --> IntermediateAddress --> ArrayGet
615 HInstruction* c1 = graph_->GetIntConstant(1);
616 HInstruction* array = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
617 dex::TypeIndex(0),
618 0,
619 DataType::Type::kReference);
620 HInstruction* array_get1 = new (GetAllocator()) HArrayGet(array,
621 c1,
622 DataType::Type::kInt32,
623 0);
624
625 HInstruction* bound_type = new (GetAllocator()) HBoundType(array);
626 HInstruction* array_get2 = new (GetAllocator()) HArrayGet(bound_type,
627 c1,
628 DataType::Type::kInt32,
629 0);
630
631 HInstruction* null_check = new (GetAllocator()) HNullCheck(bound_type, 0);
632 HInstruction* array_get3 = new (GetAllocator()) HArrayGet(null_check,
633 c1,
634 DataType::Type::kInt32,
635 0);
636
637 HInstruction* inter_addr = new (GetAllocator()) HIntermediateAddress(null_check, c1, 0);
638 HInstruction* array_get4 = new (GetAllocator()) HArrayGet(inter_addr,
639 c1,
640 DataType::Type::kInt32,
641 0);
642 entry->AddInstruction(array);
643 entry->AddInstruction(array_get1);
644 entry->AddInstruction(bound_type);
645 entry->AddInstruction(array_get2);
646 entry->AddInstruction(null_check);
647 entry->AddInstruction(array_get3);
648 entry->AddInstruction(inter_addr);
649 entry->AddInstruction(array_get4);
650
651 HeapLocationCollector heap_location_collector(graph_);
652 heap_location_collector.VisitBasicBlock(entry);
653
654 // Test that the HeapLocationCollector should be able to tell
655 // that there is only ONE array location, no matter how many
656 // times the original reference has been transformed by BoundType,
657 // NullCheck, IntermediateAddress, etc.
658 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 1U);
659 size_t loc1 = heap_location_collector.GetArrayHeapLocation(array_get1);
660 size_t loc2 = heap_location_collector.GetArrayHeapLocation(array_get2);
661 size_t loc3 = heap_location_collector.GetArrayHeapLocation(array_get3);
662 size_t loc4 = heap_location_collector.GetArrayHeapLocation(array_get4);
663 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
664 ASSERT_EQ(loc1, loc2);
665 ASSERT_EQ(loc1, loc3);
666 ASSERT_EQ(loc1, loc4);
667 }
668
669 } // namespace art
670