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