From b765a3f7f7b7c7efaab5fb331796b53439dbe04c Mon Sep 17 00:00:00 2001 From: Aart Bik Date: Thu, 10 May 2018 14:47:48 -0700 Subject: Refactoring LSE/LSA: introduce heap location type Rationale: This refactoring introduces data types to heap locations. This will allow better type disambiguation in the future. As a first showcase, it already removes rather error-prone "exceptional" code in LSE dealing with array types on null values. Furthermore, many LSA specific details started to "leak" into clients, which is also error-prone. This refactoring moves such details back into just LSA, where it belongs. Test: test-art-host,target Bug: b/77906240 Change-Id: Id327bbe86dde451a942c9c5f9e83054c36241882 --- compiler/optimizing/data_type.h | 15 +++ compiler/optimizing/load_store_analysis.h | 59 +++++++++--- compiler/optimizing/load_store_analysis_test.cc | 119 +++++++++++++----------- compiler/optimizing/load_store_elimination.cc | 119 +++++------------------- compiler/optimizing/scheduler.cc | 20 ++-- compiler/optimizing/scheduler.h | 8 +- compiler/optimizing/scheduler_test.cc | 24 ++--- 7 files changed, 174 insertions(+), 190 deletions(-) (limited to 'compiler') diff --git a/compiler/optimizing/data_type.h b/compiler/optimizing/data_type.h index be26e67af3..5ac6e46003 100644 --- a/compiler/optimizing/data_type.h +++ b/compiler/optimizing/data_type.h @@ -216,6 +216,21 @@ class DataType { Size(result_type) > Size(input_type); } + static Type ToSigned(Type type) { + switch (type) { + case Type::kUint8: + return Type::kInt8; + case Type::kUint16: + return Type::kInt16; + case Type::kUint32: + return Type::kInt32; + case Type::kUint64: + return Type::kInt64; + default: + return type; + } + } + static const char* PrettyDescriptor(Type type); private: diff --git a/compiler/optimizing/load_store_analysis.h b/compiler/optimizing/load_store_analysis.h index f84846d1b0..769a3f1b59 100644 --- a/compiler/optimizing/load_store_analysis.h +++ b/compiler/optimizing/load_store_analysis.h @@ -94,11 +94,13 @@ class HeapLocation : public ArenaObject { static constexpr int16_t kDeclaringClassDefIndexForArrays = -1; HeapLocation(ReferenceInfo* ref_info, + DataType::Type type, size_t offset, HInstruction* index, size_t vector_length, int16_t declaring_class_def_index) : ref_info_(ref_info), + type_(DataType::ToSigned(type)), offset_(offset), index_(index), vector_length_(vector_length), @@ -116,6 +118,7 @@ class HeapLocation : public ArenaObject { } ReferenceInfo* GetReferenceInfo() const { return ref_info_; } + DataType::Type GetType() const { return type_; } size_t GetOffset() const { return offset_; } HInstruction* GetIndex() const { return index_; } size_t GetVectorLength() const { return vector_length_; } @@ -149,6 +152,10 @@ class HeapLocation : public ArenaObject { private: // Reference for instance/static field, array element or vector data. ReferenceInfo* const ref_info_; + // Type of data residing at HeapLocation (always signed for integral + // data since e.g. a[i] and a[i] & 0xff are represented by differently + // signed types; char vs short are disambiguated through the reference). + const DataType::Type type_; // Offset of static/instance field. // Invalid when this HeapLocation is not field. const size_t offset_; @@ -237,19 +244,31 @@ class HeapLocationCollector : public HGraphVisitor { DCHECK(object != nullptr); DCHECK(field != nullptr); return FindHeapLocationIndex(FindReferenceInfoOf(HuntForOriginalReference(object)), + field->GetFieldType(), field->GetFieldOffset().SizeValue(), nullptr, HeapLocation::kScalar, field->GetDeclaringClassDefIndex()); } - size_t GetArrayHeapLocation(HInstruction* array, - HInstruction* index, - size_t vector_length = HeapLocation::kScalar) const { - DCHECK(array != nullptr); - DCHECK(index != nullptr); - DCHECK_GE(vector_length, HeapLocation::kScalar); + size_t GetArrayHeapLocation(HInstruction* instruction) const { + DCHECK(instruction != nullptr); + HInstruction* array = instruction->InputAt(0); + HInstruction* index = instruction->InputAt(1); + DataType::Type type = instruction->GetType(); + size_t vector_length = HeapLocation::kScalar; + if (instruction->IsArraySet()) { + type = instruction->AsArraySet()->GetComponentType(); + } else if (instruction->IsVecStore() || + instruction->IsVecLoad()) { + HVecOperation* vec_op = instruction->AsVecOperation(); + type = vec_op->GetPackedType(); + vector_length = vec_op->GetVectorLength(); + } else { + DCHECK(instruction->IsArrayGet()); + } return FindHeapLocationIndex(FindReferenceInfoOf(HuntForOriginalReference(array)), + type, HeapLocation::kInvalidFieldOffset, index, vector_length, @@ -279,13 +298,16 @@ class HeapLocationCollector : public HGraphVisitor { // In later analysis, ComputeMayAlias() and MayAlias() compute and tell whether // these indexes alias. size_t FindHeapLocationIndex(ReferenceInfo* ref_info, + DataType::Type type, size_t offset, HInstruction* index, size_t vector_length, int16_t declaring_class_def_index) const { + DataType::Type lookup_type = DataType::ToSigned(type); for (size_t i = 0; i < heap_locations_.size(); i++) { HeapLocation* loc = heap_locations_[i]; if (loc->GetReferenceInfo() == ref_info && + loc->GetType() == lookup_type && loc->GetOffset() == offset && loc->GetIndex() == index && loc->GetVectorLength() == vector_length && @@ -425,6 +447,7 @@ class HeapLocationCollector : public HGraphVisitor { } HeapLocation* GetOrCreateHeapLocation(HInstruction* ref, + DataType::Type type, size_t offset, HInstruction* index, size_t vector_length, @@ -432,10 +455,10 @@ class HeapLocationCollector : public HGraphVisitor { HInstruction* original_ref = HuntForOriginalReference(ref); ReferenceInfo* ref_info = GetOrCreateReferenceInfo(original_ref); size_t heap_location_idx = FindHeapLocationIndex( - ref_info, offset, index, vector_length, declaring_class_def_index); + ref_info, type, offset, index, vector_length, declaring_class_def_index); if (heap_location_idx == kHeapLocationNotFound) { HeapLocation* heap_loc = new (GetGraph()->GetAllocator()) - HeapLocation(ref_info, offset, index, vector_length, declaring_class_def_index); + HeapLocation(ref_info, type, offset, index, vector_length, declaring_class_def_index); heap_locations_.push_back(heap_loc); return heap_loc; } @@ -446,17 +469,23 @@ class HeapLocationCollector : public HGraphVisitor { if (field_info.IsVolatile()) { has_volatile_ = true; } + DataType::Type type = field_info.GetFieldType(); const uint16_t declaring_class_def_index = field_info.GetDeclaringClassDefIndex(); const size_t offset = field_info.GetFieldOffset().SizeValue(); return GetOrCreateHeapLocation(ref, + type, offset, nullptr, HeapLocation::kScalar, declaring_class_def_index); } - void VisitArrayAccess(HInstruction* array, HInstruction* index, size_t vector_length) { + void VisitArrayAccess(HInstruction* array, + HInstruction* index, + DataType::Type type, + size_t vector_length) { GetOrCreateHeapLocation(array, + type, HeapLocation::kInvalidFieldOffset, index, vector_length, @@ -510,28 +539,32 @@ class HeapLocationCollector : public HGraphVisitor { void VisitArrayGet(HArrayGet* instruction) OVERRIDE { HInstruction* array = instruction->InputAt(0); HInstruction* index = instruction->InputAt(1); - VisitArrayAccess(array, index, HeapLocation::kScalar); + DataType::Type type = instruction->GetType(); + VisitArrayAccess(array, index, type, HeapLocation::kScalar); CreateReferenceInfoForReferenceType(instruction); } void VisitArraySet(HArraySet* instruction) OVERRIDE { HInstruction* array = instruction->InputAt(0); HInstruction* index = instruction->InputAt(1); - VisitArrayAccess(array, index, HeapLocation::kScalar); + DataType::Type type = instruction->GetComponentType(); + VisitArrayAccess(array, index, type, HeapLocation::kScalar); has_heap_stores_ = true; } void VisitVecLoad(HVecLoad* instruction) OVERRIDE { HInstruction* array = instruction->InputAt(0); HInstruction* index = instruction->InputAt(1); - VisitArrayAccess(array, index, instruction->GetVectorLength()); + DataType::Type type = instruction->GetPackedType(); + VisitArrayAccess(array, index, type, instruction->GetVectorLength()); CreateReferenceInfoForReferenceType(instruction); } void VisitVecStore(HVecStore* instruction) OVERRIDE { HInstruction* array = instruction->InputAt(0); HInstruction* index = instruction->InputAt(1); - VisitArrayAccess(array, index, instruction->GetVectorLength()); + DataType::Type type = instruction->GetPackedType(); + VisitArrayAccess(array, index, type, instruction->GetVectorLength()); has_heap_stores_ = true; } diff --git a/compiler/optimizing/load_store_analysis_test.cc b/compiler/optimizing/load_store_analysis_test.cc index 56361a8c90..bfe7a4f72f 100644 --- a/compiler/optimizing/load_store_analysis_test.cc +++ b/compiler/optimizing/load_store_analysis_test.cc @@ -78,12 +78,16 @@ TEST_F(LoadStoreAnalysisTest, ArrayHeapLocations) { // 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, field, c1, vec, class_def); - size_t loc2 = heap_location_collector.FindHeapLocationIndex(ref, field, c2, vec, class_def); - size_t loc3 = heap_location_collector.FindHeapLocationIndex(ref, field, index, vec, class_def); + 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; @@ -246,28 +250,28 @@ TEST_F(LoadStoreAnalysisTest, ArrayIndexAliasingTest) { size_t loc2 = HeapLocationCollector::kHeapLocationNotFound; // Test alias: array[0] and array[1] - loc1 = heap_location_collector.GetArrayHeapLocation(array, c0); - loc2 = heap_location_collector.GetArrayHeapLocation(array, c1); + 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(array, add0); - loc2 = heap_location_collector.GetArrayHeapLocation(array, sub0); + 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(array, add1); - loc2 = heap_location_collector.GetArrayHeapLocation(array, sub1); + 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(array, add1); - loc2 = heap_location_collector.GetArrayHeapLocation(array, rev_sub1); + 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(array, add1); - loc2 = heap_location_collector.GetArrayHeapLocation(array, sub_neg1); + loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4); + loc2 = heap_location_collector.GetArrayHeapLocation(arr_set8); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); } @@ -409,70 +413,75 @@ TEST_F(LoadStoreAnalysisTest, ArrayAliasingTest) { size_t loc1, loc2; // Test alias: array[0] and array[0,1,2,3] - loc1 = heap_location_collector.GetArrayHeapLocation(array, c0); - loc2 = heap_location_collector.GetArrayHeapLocation(array, c0, 4); + 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(array, c0); - loc2 = heap_location_collector.GetArrayHeapLocation(array, c8, 4); + 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(array, c1); - loc2 = heap_location_collector.GetArrayHeapLocation(array, c8, 4); + 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(array, c1); - loc2 = heap_location_collector.GetArrayHeapLocation(array, c0, 4); + 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(array, c0, 4); - loc2 = heap_location_collector.GetArrayHeapLocation(array, c8, 4); + 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(array, c1, 4); - loc2 = heap_location_collector.GetArrayHeapLocation(array, c0, 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(array, c0); - loc2 = heap_location_collector.GetArrayHeapLocation(array, index, 4); + 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(array, index); - loc2 = heap_location_collector.GetArrayHeapLocation(array, c0, 4); + 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(array, index); - loc2 = heap_location_collector.GetArrayHeapLocation(array, index, 4); + 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(array, index); - loc2 = heap_location_collector.GetArrayHeapLocation(array, i_add8, 4); + 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(array, i_add6, 4); - loc2 = heap_location_collector.GetArrayHeapLocation(array, i_add8, 4); + 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(array, i_add6, 2); - loc2 = heap_location_collector.GetArrayHeapLocation(array, index, 4); + 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(array, i_add6, 2); - loc2 = heap_location_collector.GetArrayHeapLocation(array, i_add8, 4); + 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)); } @@ -563,33 +572,33 @@ TEST_F(LoadStoreAnalysisTest, ArrayIndexCalculationOverflowTest) { size_t loc2 = HeapLocationCollector::kHeapLocationNotFound; // Test alias: array[i+0x80000000] and array[i-0x80000000] - loc1 = heap_location_collector.GetArrayHeapLocation(array, add_0x80000000); - loc2 = heap_location_collector.GetArrayHeapLocation(array, sub_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(array, add_0x10); - loc2 = heap_location_collector.GetArrayHeapLocation(array, sub_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(array, add_0x7FFFFFFF); - loc2 = heap_location_collector.GetArrayHeapLocation(array, sub_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(array, add_0); - loc2 = heap_location_collector.GetArrayHeapLocation(array, sub_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(array, sub_0x80000000); - loc2 = heap_location_collector.GetArrayHeapLocation(array, sub_0x80000001); + 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(array, add_0); - loc2 = heap_location_collector.GetArrayHeapLocation(array, sub_0x80000000); + loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7); + loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); } @@ -647,10 +656,10 @@ TEST_F(LoadStoreAnalysisTest, TestHuntOriginalRef) { // 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, c1); - size_t loc2 = heap_location_collector.GetArrayHeapLocation(bound_type, c1); - size_t loc3 = heap_location_collector.GetArrayHeapLocation(null_check, c1); - size_t loc4 = heap_location_collector.GetArrayHeapLocation(inter_addr, c1); + 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); diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc index d598ff592d..35e64f75b9 100644 --- a/compiler/optimizing/load_store_elimination.cc +++ b/compiler/optimizing/load_store_elimination.cc @@ -160,7 +160,7 @@ class LSEVisitor : public HGraphDelegateVisitor { // Scan the list of removed loads to see if we can reuse `type_conversion`, if // the other removed load has the same substitute and type and is dominated - // by `type_conversioni`. + // by `type_conversion`. void TryToReuseTypeConversion(HInstruction* type_conversion, size_t index) { size_t size = removed_loads_.size(); HInstruction* load = removed_loads_[index]; @@ -542,16 +542,7 @@ class LSEVisitor : public HGraphDelegateVisitor { } } - void VisitGetLocation(HInstruction* instruction, - HInstruction* ref, - size_t offset, - HInstruction* index, - size_t vector_length, - int16_t declaring_class_def_index) { - HInstruction* original_ref = heap_location_collector_.HuntForOriginalReference(ref); - ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); - size_t idx = heap_location_collector_.FindHeapLocationIndex( - ref_info, offset, index, vector_length, declaring_class_def_index); + void VisitGetLocation(HInstruction* instruction, size_t idx) { DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); ScopedArenaVector& heap_values = heap_values_for_[instruction->GetBlock()->GetBlockId()]; @@ -569,23 +560,7 @@ class LSEVisitor : public HGraphDelegateVisitor { heap_values[idx] = instruction; KeepStoresIfAliasedToLocation(heap_values, idx); } else { - if (DataType::Kind(heap_value->GetType()) != DataType::Kind(instruction->GetType())) { - // The only situation where the same heap location has different type is when - // we do an array get on an instruction that originates from the null constant - // (the null could be behind a field access, an array access, a null check or - // a bound type). - // In order to stay properly typed on primitive types, we do not eliminate - // the array gets. - if (kIsDebugBuild) { - DCHECK(heap_value->IsArrayGet()) << heap_value->DebugName(); - DCHECK(instruction->IsArrayGet()) << instruction->DebugName(); - } - // Load isn't eliminated. Put the load as the value into the HeapLocation. - // This acts like GVN but with better aliasing analysis. - heap_values[idx] = instruction; - KeepStoresIfAliasedToLocation(heap_values, idx); - return; - } + // Load is eliminated. AddRemovedLoad(instruction, heap_value); TryRemovingNullCheck(instruction); } @@ -610,21 +585,11 @@ class LSEVisitor : public HGraphDelegateVisitor { return false; } - void VisitSetLocation(HInstruction* instruction, - HInstruction* ref, - size_t offset, - HInstruction* index, - size_t vector_length, - int16_t declaring_class_def_index, - HInstruction* value) { + void VisitSetLocation(HInstruction* instruction, size_t idx, HInstruction* value) { + DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); DCHECK(!IsStore(value)) << value->DebugName(); // value may already have a substitute. value = FindSubstitute(value); - HInstruction* original_ref = heap_location_collector_.HuntForOriginalReference(ref); - ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); - size_t idx = heap_location_collector_.FindHeapLocationIndex( - ref_info, offset, index, vector_length, declaring_class_def_index); - DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); ScopedArenaVector& heap_values = heap_values_for_[instruction->GetBlock()->GetBlockId()]; HInstruction* heap_value = heap_values[idx]; @@ -644,7 +609,8 @@ class LSEVisitor : public HGraphDelegateVisitor { } else if (!loop_info->IsIrreducible()) { // instruction is a store in the loop so the loop must do write. DCHECK(side_effects_.GetLoopEffects(loop_info->GetHeader()).DoesAnyWrite()); - if (ref_info->IsSingleton() && !loop_info->IsDefinedOutOfTheLoop(original_ref)) { + ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(idx)->GetReferenceInfo(); + if (ref_info->IsSingleton() && !loop_info->IsDefinedOutOfTheLoop(ref_info->GetReference())) { // original_ref is created inside the loop. Value stored to it isn't needed at // the loop header. This is true for outer loops also. possibly_redundant = true; @@ -686,79 +652,39 @@ class LSEVisitor : public HGraphDelegateVisitor { } void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { - HInstruction* obj = instruction->InputAt(0); - size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); - int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); - VisitGetLocation(instruction, - obj, - offset, - nullptr, - HeapLocation::kScalar, - declaring_class_def_index); + HInstruction* object = instruction->InputAt(0); + const FieldInfo& field = instruction->GetFieldInfo(); + VisitGetLocation(instruction, heap_location_collector_.GetFieldHeapLocation(object, &field)); } void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { - HInstruction* obj = instruction->InputAt(0); - size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); - int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); + HInstruction* object = instruction->InputAt(0); + const FieldInfo& field = instruction->GetFieldInfo(); HInstruction* value = instruction->InputAt(1); - VisitSetLocation(instruction, - obj, - offset, - nullptr, - HeapLocation::kScalar, - declaring_class_def_index, - value); + size_t idx = heap_location_collector_.GetFieldHeapLocation(object, &field); + VisitSetLocation(instruction, idx, value); } void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE { HInstruction* cls = instruction->InputAt(0); - size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); - int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); - VisitGetLocation(instruction, - cls, - offset, - nullptr, - HeapLocation::kScalar, - declaring_class_def_index); + const FieldInfo& field = instruction->GetFieldInfo(); + VisitGetLocation(instruction, heap_location_collector_.GetFieldHeapLocation(cls, &field)); } void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { HInstruction* cls = instruction->InputAt(0); - size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); - int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); - HInstruction* value = instruction->InputAt(1); - VisitSetLocation(instruction, - cls, - offset, - nullptr, - HeapLocation::kScalar, - declaring_class_def_index, - value); + const FieldInfo& field = instruction->GetFieldInfo(); + size_t idx = heap_location_collector_.GetFieldHeapLocation(cls, &field); + VisitSetLocation(instruction, idx, instruction->InputAt(1)); } void VisitArrayGet(HArrayGet* instruction) OVERRIDE { - HInstruction* array = instruction->InputAt(0); - HInstruction* index = instruction->InputAt(1); - VisitGetLocation(instruction, - array, - HeapLocation::kInvalidFieldOffset, - index, - HeapLocation::kScalar, - HeapLocation::kDeclaringClassDefIndexForArrays); + VisitGetLocation(instruction, heap_location_collector_.GetArrayHeapLocation(instruction)); } void VisitArraySet(HArraySet* instruction) OVERRIDE { - HInstruction* array = instruction->InputAt(0); - HInstruction* index = instruction->InputAt(1); - HInstruction* value = instruction->InputAt(2); - VisitSetLocation(instruction, - array, - HeapLocation::kInvalidFieldOffset, - index, - HeapLocation::kScalar, - HeapLocation::kDeclaringClassDefIndexForArrays, - value); + size_t idx = heap_location_collector_.GetArrayHeapLocation(instruction); + VisitSetLocation(instruction, idx, instruction->InputAt(2)); } void VisitDeoptimize(HDeoptimize* instruction) { @@ -971,6 +897,7 @@ bool LoadStoreElimination::Run() { lse_visitor.VisitBasicBlock(block); } lse_visitor.RemoveInstructions(); + return true; } diff --git a/compiler/optimizing/scheduler.cc b/compiler/optimizing/scheduler.cc index e014efaf5c..588ea03d69 100644 --- a/compiler/optimizing/scheduler.cc +++ b/compiler/optimizing/scheduler.cc @@ -70,19 +70,19 @@ static bool MayHaveReorderingDependency(SideEffects node, SideEffects other) { return false; } -size_t SchedulingGraph::ArrayAccessHeapLocation(HInstruction* array, HInstruction* index) const { +size_t SchedulingGraph::ArrayAccessHeapLocation(HInstruction* instruction) const { DCHECK(heap_location_collector_ != nullptr); - size_t heap_loc = heap_location_collector_->GetArrayHeapLocation(array, index); + size_t heap_loc = heap_location_collector_->GetArrayHeapLocation(instruction); // This array access should be analyzed and added to HeapLocationCollector before. DCHECK(heap_loc != HeapLocationCollector::kHeapLocationNotFound); return heap_loc; } -bool SchedulingGraph::ArrayAccessMayAlias(const HInstruction* node, - const HInstruction* other) const { +bool SchedulingGraph::ArrayAccessMayAlias(HInstruction* node, + HInstruction* other) const { DCHECK(heap_location_collector_ != nullptr); - size_t node_heap_loc = ArrayAccessHeapLocation(node->InputAt(0), node->InputAt(1)); - size_t other_heap_loc = ArrayAccessHeapLocation(other->InputAt(0), other->InputAt(1)); + size_t node_heap_loc = ArrayAccessHeapLocation(node); + size_t other_heap_loc = ArrayAccessHeapLocation(other); // For example: arr[0] and arr[0] if (node_heap_loc == other_heap_loc) { @@ -194,8 +194,8 @@ bool SchedulingGraph::FieldAccessMayAlias(const HInstruction* node, return true; } -bool SchedulingGraph::HasMemoryDependency(const HInstruction* node, - const HInstruction* other) const { +bool SchedulingGraph::HasMemoryDependency(HInstruction* node, + HInstruction* other) const { if (!MayHaveReorderingDependency(node->GetSideEffects(), other->GetSideEffects())) { return false; } @@ -264,8 +264,8 @@ bool SchedulingGraph::HasExceptionDependency(const HInstruction* node, // Check whether `node` depends on `other`, taking into account `SideEffect` // information and `CanThrow` information. -bool SchedulingGraph::HasSideEffectDependency(const HInstruction* node, - const HInstruction* other) const { +bool SchedulingGraph::HasSideEffectDependency(HInstruction* node, + HInstruction* other) const { if (HasMemoryDependency(node, other)) { return true; } diff --git a/compiler/optimizing/scheduler.h b/compiler/optimizing/scheduler.h index 51cd20aea9..8e98f192d8 100644 --- a/compiler/optimizing/scheduler.h +++ b/compiler/optimizing/scheduler.h @@ -310,12 +310,12 @@ class SchedulingGraph : public ValueObject { void AddOtherDependency(SchedulingNode* node, SchedulingNode* dependency) { AddDependency(node, dependency, /*is_data_dependency*/false); } - bool HasMemoryDependency(const HInstruction* node, const HInstruction* other) const; + bool HasMemoryDependency(HInstruction* node, HInstruction* other) const; bool HasExceptionDependency(const HInstruction* node, const HInstruction* other) const; - bool HasSideEffectDependency(const HInstruction* node, const HInstruction* other) const; - bool ArrayAccessMayAlias(const HInstruction* node, const HInstruction* other) const; + bool HasSideEffectDependency(HInstruction* node, HInstruction* other) const; + bool ArrayAccessMayAlias(HInstruction* node, HInstruction* other) const; bool FieldAccessMayAlias(const HInstruction* node, const HInstruction* other) const; - size_t ArrayAccessHeapLocation(HInstruction* array, HInstruction* index) const; + size_t ArrayAccessHeapLocation(HInstruction* instruction) const; size_t FieldAccessHeapLocation(HInstruction* obj, const FieldInfo* field) const; // Add dependencies nodes for the given `HInstruction`: inputs, environments, and side-effects. diff --git a/compiler/optimizing/scheduler_test.cc b/compiler/optimizing/scheduler_test.cc index fb15fc8975..d4cae72c7e 100644 --- a/compiler/optimizing/scheduler_test.cc +++ b/compiler/optimizing/scheduler_test.cc @@ -296,38 +296,38 @@ class SchedulerTest : public OptimizingUnitTest { size_t loc2 = HeapLocationCollector::kHeapLocationNotFound; // Test side effect dependency: array[0] and array[1] - loc1 = heap_location_collector.GetArrayHeapLocation(arr, c0); - loc2 = heap_location_collector.GetArrayHeapLocation(arr, c1); + loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0); + loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_1); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_1, arr_set_0)); // Test side effect dependency based on LSA analysis: array[i] and array[j] - loc1 = heap_location_collector.GetArrayHeapLocation(arr, i); - loc2 = heap_location_collector.GetArrayHeapLocation(arr, j); + loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i); + loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_j); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_i)); // Test side effect dependency based on LSA analysis: array[i] and array[i+0] - loc1 = heap_location_collector.GetArrayHeapLocation(arr, i); - loc2 = heap_location_collector.GetArrayHeapLocation(arr, add0); + loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i); + loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_add0); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_add0, arr_set_i)); // Test side effect dependency based on LSA analysis: array[i] and array[i-0] - loc1 = heap_location_collector.GetArrayHeapLocation(arr, i); - loc2 = heap_location_collector.GetArrayHeapLocation(arr, sub0); + loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i); + loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_sub0); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub0, arr_set_i)); // Test side effect dependency based on LSA analysis: array[i] and array[i+1] - loc1 = heap_location_collector.GetArrayHeapLocation(arr, i); - loc2 = heap_location_collector.GetArrayHeapLocation(arr, add1); + loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i); + loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_add1); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_add1, arr_set_i)); // Test side effect dependency based on LSA analysis: array[i+1] and array[i-1] - loc1 = heap_location_collector.GetArrayHeapLocation(arr, add1); - loc2 = heap_location_collector.GetArrayHeapLocation(arr, sub1); + loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_add1); + loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_sub1); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub1, arr_set_add1)); -- cgit v1.2.3-59-g8ed1b