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