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