/* * Copyright (C) 2017 The Android Open Source Project * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #include "load_store_analysis.h" #include "nodes.h" #include "optimizing_unit_test.h" #include "gtest/gtest.h" namespace art { class LoadStoreAnalysisTest : public OptimizingUnitTest { public: LoadStoreAnalysisTest() : graph_(CreateGraph()) { } HGraph* graph_; }; TEST_F(LoadStoreAnalysisTest, ArrayHeapLocations) { HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); graph_->AddBlock(entry); graph_->SetEntryBlock(entry); // entry: // array ParameterValue // index ParameterValue // c1 IntConstant // c2 IntConstant // c3 IntConstant // array_get1 ArrayGet [array, c1] // array_get2 ArrayGet [array, c2] // array_set1 ArraySet [array, c1, c3] // array_set2 ArraySet [array, index, c3] HInstruction* array = new (GetAllocator()) HParameterValue( graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); HInstruction* index = new (GetAllocator()) HParameterValue( graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32); HInstruction* c1 = graph_->GetIntConstant(1); HInstruction* c2 = graph_->GetIntConstant(2); HInstruction* c3 = graph_->GetIntConstant(3); HInstruction* array_get1 = new (GetAllocator()) HArrayGet(array, c1, DataType::Type::kInt32, 0); HInstruction* array_get2 = new (GetAllocator()) HArrayGet(array, c2, DataType::Type::kInt32, 0); HInstruction* array_set1 = new (GetAllocator()) HArraySet(array, c1, c3, DataType::Type::kInt32, 0); HInstruction* array_set2 = new (GetAllocator()) HArraySet(array, index, c3, DataType::Type::kInt32, 0); entry->AddInstruction(array); entry->AddInstruction(index); entry->AddInstruction(array_get1); entry->AddInstruction(array_get2); entry->AddInstruction(array_set1); entry->AddInstruction(array_set2); // Test HeapLocationCollector initialization. // Should be no heap locations, no operations on the heap. ScopedArenaAllocator allocator(graph_->GetArenaStack()); HeapLocationCollector heap_location_collector(graph_, &allocator); ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U); ASSERT_FALSE(heap_location_collector.HasHeapStores()); // Test that after visiting the graph_, it must see following heap locations // array[c1], array[c2], array[index]; and it should see heap stores. heap_location_collector.VisitBasicBlock(entry); ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 3U); ASSERT_TRUE(heap_location_collector.HasHeapStores()); // Test queries on HeapLocationCollector's ref info and index records. ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(array); DataType::Type type = DataType::Type::kInt32; size_t field = HeapLocation::kInvalidFieldOffset; size_t vec = HeapLocation::kScalar; size_t class_def = HeapLocation::kDeclaringClassDefIndexForArrays; size_t loc1 = heap_location_collector.FindHeapLocationIndex( ref, type, field, c1, vec, class_def); size_t loc2 = heap_location_collector.FindHeapLocationIndex( ref, type, field, c2, vec, class_def); size_t loc3 = heap_location_collector.FindHeapLocationIndex( ref, type, field, index, vec, class_def); // must find this reference info for array in HeapLocationCollector. ASSERT_TRUE(ref != nullptr); // must find these heap locations; // and array[1], array[2], array[3] should be different heap locations. ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound); ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound); ASSERT_TRUE(loc3 != HeapLocationCollector::kHeapLocationNotFound); ASSERT_TRUE(loc1 != loc2); ASSERT_TRUE(loc2 != loc3); ASSERT_TRUE(loc1 != loc3); // Test alias relationships after building aliasing matrix. // array[1] and array[2] clearly should not alias; // array[index] should alias with the others, because index is an unknow value. heap_location_collector.BuildAliasingMatrix(); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc3)); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc3)); EXPECT_TRUE(CheckGraph(graph_)); } TEST_F(LoadStoreAnalysisTest, FieldHeapLocations) { HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); graph_->AddBlock(entry); graph_->SetEntryBlock(entry); // entry: // object ParameterValue // c1 IntConstant // set_field10 InstanceFieldSet [object, c1, 10] // get_field10 InstanceFieldGet [object, 10] // get_field20 InstanceFieldGet [object, 20] HInstruction* c1 = graph_->GetIntConstant(1); HInstruction* object = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); HInstanceFieldSet* set_field10 = new (GetAllocator()) HInstanceFieldSet(object, c1, nullptr, DataType::Type::kInt32, MemberOffset(10), false, kUnknownFieldIndex, kUnknownClassDefIndex, graph_->GetDexFile(), 0); HInstanceFieldGet* get_field10 = new (GetAllocator()) HInstanceFieldGet(object, nullptr, DataType::Type::kInt32, MemberOffset(10), false, kUnknownFieldIndex, kUnknownClassDefIndex, graph_->GetDexFile(), 0); HInstanceFieldGet* get_field20 = new (GetAllocator()) HInstanceFieldGet(object, nullptr, DataType::Type::kInt32, MemberOffset(20), false, kUnknownFieldIndex, kUnknownClassDefIndex, graph_->GetDexFile(), 0); entry->AddInstruction(object); entry->AddInstruction(set_field10); entry->AddInstruction(get_field10); entry->AddInstruction(get_field20); // Test HeapLocationCollector initialization. // Should be no heap locations, no operations on the heap. ScopedArenaAllocator allocator(graph_->GetArenaStack()); HeapLocationCollector heap_location_collector(graph_, &allocator); ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U); ASSERT_FALSE(heap_location_collector.HasHeapStores()); // Test that after visiting the graph, it must see following heap locations // object.field10, object.field20 and it should see heap stores. heap_location_collector.VisitBasicBlock(entry); ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 2U); ASSERT_TRUE(heap_location_collector.HasHeapStores()); // Test queries on HeapLocationCollector's ref info and index records. ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(object); size_t loc1 = heap_location_collector.GetFieldHeapLocation(object, &get_field10->GetFieldInfo()); size_t loc2 = heap_location_collector.GetFieldHeapLocation(object, &get_field20->GetFieldInfo()); // must find references info for object and in HeapLocationCollector. ASSERT_TRUE(ref != nullptr); // must find these heap locations. ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound); ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound); // different fields of same object. ASSERT_TRUE(loc1 != loc2); // accesses to different fields of the same object should not alias. ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); EXPECT_TRUE(CheckGraph(graph_)); } TEST_F(LoadStoreAnalysisTest, ArrayIndexAliasingTest) { HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); graph_->AddBlock(entry); graph_->SetEntryBlock(entry); graph_->BuildDominatorTree(); HInstruction* array = new (GetAllocator()) HParameterValue( graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); HInstruction* index = new (GetAllocator()) HParameterValue( graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32); HInstruction* c0 = graph_->GetIntConstant(0); HInstruction* c1 = graph_->GetIntConstant(1); HInstruction* c_neg1 = graph_->GetIntConstant(-1); HInstruction* add0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c0); HInstruction* add1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c1); HInstruction* sub0 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c0); HInstruction* sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c1); HInstruction* sub_neg1 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c_neg1); HInstruction* rev_sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, c1, index); HInstruction* arr_set1 = new (GetAllocator()) HArraySet(array, c0, c0, DataType::Type::kInt32, 0); HInstruction* arr_set2 = new (GetAllocator()) HArraySet(array, c1, c0, DataType::Type::kInt32, 0); HInstruction* arr_set3 = new (GetAllocator()) HArraySet(array, add0, c0, DataType::Type::kInt32, 0); HInstruction* arr_set4 = new (GetAllocator()) HArraySet(array, add1, c0, DataType::Type::kInt32, 0); HInstruction* arr_set5 = new (GetAllocator()) HArraySet(array, sub0, c0, DataType::Type::kInt32, 0); HInstruction* arr_set6 = new (GetAllocator()) HArraySet(array, sub1, c0, DataType::Type::kInt32, 0); HInstruction* arr_set7 = new (GetAllocator()) HArraySet(array, rev_sub1, c0, DataType::Type::kInt32, 0); HInstruction* arr_set8 = new (GetAllocator()) HArraySet(array, sub_neg1, c0, DataType::Type::kInt32, 0); entry->AddInstruction(array); entry->AddInstruction(index); entry->AddInstruction(add0); entry->AddInstruction(add1); entry->AddInstruction(sub0); entry->AddInstruction(sub1); entry->AddInstruction(sub_neg1); entry->AddInstruction(rev_sub1); entry->AddInstruction(arr_set1); // array[0] = c0 entry->AddInstruction(arr_set2); // array[1] = c0 entry->AddInstruction(arr_set3); // array[i+0] = c0 entry->AddInstruction(arr_set4); // array[i+1] = c0 entry->AddInstruction(arr_set5); // array[i-0] = c0 entry->AddInstruction(arr_set6); // array[i-1] = c0 entry->AddInstruction(arr_set7); // array[1-i] = c0 entry->AddInstruction(arr_set8); // array[i-(-1)] = c0 ScopedArenaAllocator allocator(graph_->GetArenaStack()); LoadStoreAnalysis lsa(graph_, &allocator); lsa.Run(); const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector(); // LSA/HeapLocationCollector should see those ArrayGet instructions. ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U); ASSERT_TRUE(heap_location_collector.HasHeapStores()); // Test queries on HeapLocationCollector's aliasing matrix after load store analysis. size_t loc1 = HeapLocationCollector::kHeapLocationNotFound; size_t loc2 = HeapLocationCollector::kHeapLocationNotFound; // Test alias: array[0] and array[1] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set1); loc2 = heap_location_collector.GetArrayHeapLocation(arr_set2); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i+0] and array[i-0] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set3); loc2 = heap_location_collector.GetArrayHeapLocation(arr_set5); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i+1] and array[i-1] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4); loc2 = heap_location_collector.GetArrayHeapLocation(arr_set6); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i+1] and array[1-i] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4); loc2 = heap_location_collector.GetArrayHeapLocation(arr_set7); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i+1] and array[i-(-1)] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4); loc2 = heap_location_collector.GetArrayHeapLocation(arr_set8); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); EXPECT_TRUE(CheckGraphSkipRefTypeInfoChecks(graph_)); } TEST_F(LoadStoreAnalysisTest, ArrayAliasingTest) { HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); graph_->AddBlock(entry); graph_->SetEntryBlock(entry); graph_->BuildDominatorTree(); HInstruction* array = new (GetAllocator()) HParameterValue( graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); HInstruction* index = new (GetAllocator()) HParameterValue( graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32); HInstruction* c0 = graph_->GetIntConstant(0); HInstruction* c1 = graph_->GetIntConstant(1); HInstruction* c6 = graph_->GetIntConstant(6); HInstruction* c8 = graph_->GetIntConstant(8); HInstruction* arr_set_0 = new (GetAllocator()) HArraySet(array, c0, c0, DataType::Type::kInt32, 0); HInstruction* arr_set_1 = new (GetAllocator()) HArraySet(array, c1, c0, DataType::Type::kInt32, 0); HInstruction* arr_set_i = new (GetAllocator()) HArraySet(array, index, c0, DataType::Type::kInt32, 0); HVecOperation* v1 = new (GetAllocator()) HVecReplicateScalar(GetAllocator(), c1, DataType::Type::kInt32, 4, kNoDexPc); HVecOperation* v2 = new (GetAllocator()) HVecReplicateScalar(GetAllocator(), c1, DataType::Type::kInt32, 2, kNoDexPc); HInstruction* i_add6 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c6); HInstruction* i_add8 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c8); HInstruction* vstore_0 = new (GetAllocator()) HVecStore( GetAllocator(), array, c0, v1, DataType::Type::kInt32, SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 4, kNoDexPc); HInstruction* vstore_1 = new (GetAllocator()) HVecStore( GetAllocator(), array, c1, v1, DataType::Type::kInt32, SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 4, kNoDexPc); HInstruction* vstore_8 = new (GetAllocator()) HVecStore( GetAllocator(), array, c8, v1, DataType::Type::kInt32, SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 4, kNoDexPc); HInstruction* vstore_i = new (GetAllocator()) HVecStore( GetAllocator(), array, index, v1, DataType::Type::kInt32, SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 4, kNoDexPc); HInstruction* vstore_i_add6 = new (GetAllocator()) HVecStore( GetAllocator(), array, i_add6, v1, DataType::Type::kInt32, SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 4, kNoDexPc); HInstruction* vstore_i_add8 = new (GetAllocator()) HVecStore( GetAllocator(), array, i_add8, v1, DataType::Type::kInt32, SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 4, kNoDexPc); HInstruction* vstore_i_add6_vlen2 = new (GetAllocator()) HVecStore( GetAllocator(), array, i_add6, v2, DataType::Type::kInt32, SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 2, kNoDexPc); entry->AddInstruction(array); entry->AddInstruction(index); entry->AddInstruction(arr_set_0); entry->AddInstruction(arr_set_1); entry->AddInstruction(arr_set_i); entry->AddInstruction(v1); entry->AddInstruction(v2); entry->AddInstruction(i_add6); entry->AddInstruction(i_add8); entry->AddInstruction(vstore_0); entry->AddInstruction(vstore_1); entry->AddInstruction(vstore_8); entry->AddInstruction(vstore_i); entry->AddInstruction(vstore_i_add6); entry->AddInstruction(vstore_i_add8); entry->AddInstruction(vstore_i_add6_vlen2); ScopedArenaAllocator allocator(graph_->GetArenaStack()); LoadStoreAnalysis lsa(graph_, &allocator); lsa.Run(); const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector(); // LSA/HeapLocationCollector should see those instructions. ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 10U); ASSERT_TRUE(heap_location_collector.HasHeapStores()); // Test queries on HeapLocationCollector's aliasing matrix after load store analysis. size_t loc1, loc2; // Test alias: array[0] and array[0,1,2,3] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[0] and array[1,2,3,4] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[0] and array[8,9,10,11] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[1] and array[8,9,10,11] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[1] and array[0,1,2,3] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[0,1,2,3] and array[8,9,10,11] loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[0,1,2,3] and array[1,2,3,4] loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[0] and array[i,i+1,i+2,i+3] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i] and array[0,1,2,3] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i] and array[i,i+1,i+2,i+3] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i] and array[i+8,i+9,i+10,i+11] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i+6,i+7,i+8,i+9] and array[i+8,i+9,i+10,i+11] // Test partial overlap. loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i+6,i+7] and array[i,i+1,i+2,i+3] // Test different vector lengths. loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i+6,i+7] and array[i+8,i+9,i+10,i+11] loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2); loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); } TEST_F(LoadStoreAnalysisTest, ArrayIndexCalculationOverflowTest) { HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); graph_->AddBlock(entry); graph_->SetEntryBlock(entry); graph_->BuildDominatorTree(); HInstruction* array = new (GetAllocator()) HParameterValue( graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); HInstruction* index = new (GetAllocator()) HParameterValue( graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32); HInstruction* c0 = graph_->GetIntConstant(0); HInstruction* c_0x80000000 = graph_->GetIntConstant(0x80000000); HInstruction* c_0x10 = graph_->GetIntConstant(0x10); HInstruction* c_0xFFFFFFF0 = graph_->GetIntConstant(0xFFFFFFF0); HInstruction* c_0x7FFFFFFF = graph_->GetIntConstant(0x7FFFFFFF); HInstruction* c_0x80000001 = graph_->GetIntConstant(0x80000001); // `index+0x80000000` and `index-0x80000000` array indices MAY alias. HInstruction* add_0x80000000 = new (GetAllocator()) HAdd( DataType::Type::kInt32, index, c_0x80000000); HInstruction* sub_0x80000000 = new (GetAllocator()) HSub( DataType::Type::kInt32, index, c_0x80000000); HInstruction* arr_set_1 = new (GetAllocator()) HArraySet( array, add_0x80000000, c0, DataType::Type::kInt32, 0); HInstruction* arr_set_2 = new (GetAllocator()) HArraySet( array, sub_0x80000000, c0, DataType::Type::kInt32, 0); // `index+0x10` and `index-0xFFFFFFF0` array indices MAY alias. HInstruction* add_0x10 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c_0x10); HInstruction* sub_0xFFFFFFF0 = new (GetAllocator()) HSub( DataType::Type::kInt32, index, c_0xFFFFFFF0); HInstruction* arr_set_3 = new (GetAllocator()) HArraySet( array, add_0x10, c0, DataType::Type::kInt32, 0); HInstruction* arr_set_4 = new (GetAllocator()) HArraySet( array, sub_0xFFFFFFF0, c0, DataType::Type::kInt32, 0); // `index+0x7FFFFFFF` and `index-0x80000001` array indices MAY alias. HInstruction* add_0x7FFFFFFF = new (GetAllocator()) HAdd( DataType::Type::kInt32, index, c_0x7FFFFFFF); HInstruction* sub_0x80000001 = new (GetAllocator()) HSub( DataType::Type::kInt32, index, c_0x80000001); HInstruction* arr_set_5 = new (GetAllocator()) HArraySet( array, add_0x7FFFFFFF, c0, DataType::Type::kInt32, 0); HInstruction* arr_set_6 = new (GetAllocator()) HArraySet( array, sub_0x80000001, c0, DataType::Type::kInt32, 0); // `index+0` and `index-0` array indices MAY alias. HInstruction* add_0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c0); HInstruction* sub_0 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c0); HInstruction* arr_set_7 = new (GetAllocator()) HArraySet( array, add_0, c0, DataType::Type::kInt32, 0); HInstruction* arr_set_8 = new (GetAllocator()) HArraySet( array, sub_0, c0, DataType::Type::kInt32, 0); entry->AddInstruction(array); entry->AddInstruction(index); entry->AddInstruction(add_0x80000000); entry->AddInstruction(sub_0x80000000); entry->AddInstruction(add_0x10); entry->AddInstruction(sub_0xFFFFFFF0); entry->AddInstruction(add_0x7FFFFFFF); entry->AddInstruction(sub_0x80000001); entry->AddInstruction(add_0); entry->AddInstruction(sub_0); entry->AddInstruction(arr_set_1); entry->AddInstruction(arr_set_2); entry->AddInstruction(arr_set_3); entry->AddInstruction(arr_set_4); entry->AddInstruction(arr_set_5); entry->AddInstruction(arr_set_6); entry->AddInstruction(arr_set_7); entry->AddInstruction(arr_set_8); ScopedArenaAllocator allocator(graph_->GetArenaStack()); LoadStoreAnalysis lsa(graph_, &allocator); lsa.Run(); const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector(); // LSA/HeapLocationCollector should see those ArrayGet instructions. ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U); ASSERT_TRUE(heap_location_collector.HasHeapStores()); // Test queries on HeapLocationCollector's aliasing matrix after load store analysis. size_t loc1 = HeapLocationCollector::kHeapLocationNotFound; size_t loc2 = HeapLocationCollector::kHeapLocationNotFound; // Test alias: array[i+0x80000000] and array[i-0x80000000] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1); loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i+0x10] and array[i-0xFFFFFFF0] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_3); loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_4); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i+0x7FFFFFFF] and array[i-0x80000001] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_5); loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Test alias: array[i+0] and array[i-0] loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7); loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_8); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); // Should not alias: loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_2); loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); // Should not alias: loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7); loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); } TEST_F(LoadStoreAnalysisTest, TestHuntOriginalRef) { HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); graph_->AddBlock(entry); graph_->SetEntryBlock(entry); // Different ways where orignal array reference are transformed & passed to ArrayGet. // ParameterValue --> ArrayGet // ParameterValue --> BoundType --> ArrayGet // ParameterValue --> BoundType --> NullCheck --> ArrayGet // ParameterValue --> BoundType --> NullCheck --> IntermediateAddress --> ArrayGet HInstruction* c1 = graph_->GetIntConstant(1); HInstruction* array = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); HInstruction* array_get1 = new (GetAllocator()) HArrayGet(array, c1, DataType::Type::kInt32, 0); HInstruction* bound_type = new (GetAllocator()) HBoundType(array); HInstruction* array_get2 = new (GetAllocator()) HArrayGet(bound_type, c1, DataType::Type::kInt32, 0); HInstruction* null_check = new (GetAllocator()) HNullCheck(bound_type, 0); HInstruction* array_get3 = new (GetAllocator()) HArrayGet(null_check, c1, DataType::Type::kInt32, 0); HInstruction* inter_addr = new (GetAllocator()) HIntermediateAddress(null_check, c1, 0); HInstruction* array_get4 = new (GetAllocator()) HArrayGet(inter_addr, c1, DataType::Type::kInt32, 0); entry->AddInstruction(array); entry->AddInstruction(array_get1); entry->AddInstruction(bound_type); entry->AddInstruction(array_get2); entry->AddInstruction(null_check); entry->AddInstruction(array_get3); entry->AddInstruction(inter_addr); entry->AddInstruction(array_get4); ScopedArenaAllocator allocator(graph_->GetArenaStack()); HeapLocationCollector heap_location_collector(graph_, &allocator); heap_location_collector.VisitBasicBlock(entry); // Test that the HeapLocationCollector should be able to tell // that there is only ONE array location, no matter how many // times the original reference has been transformed by BoundType, // NullCheck, IntermediateAddress, etc. ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 1U); size_t loc1 = heap_location_collector.GetArrayHeapLocation(array_get1); size_t loc2 = heap_location_collector.GetArrayHeapLocation(array_get2); size_t loc3 = heap_location_collector.GetArrayHeapLocation(array_get3); size_t loc4 = heap_location_collector.GetArrayHeapLocation(array_get4); ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound); ASSERT_EQ(loc1, loc2); ASSERT_EQ(loc1, loc3); ASSERT_EQ(loc1, loc4); } } // namespace art