diff options
Diffstat (limited to 'compiler/optimizing')
-rw-r--r-- | compiler/optimizing/load_store_analysis.cc | 111 | ||||
-rw-r--r-- | compiler/optimizing/load_store_analysis.h | 20 | ||||
-rw-r--r-- | compiler/optimizing/load_store_analysis_test.cc | 194 |
3 files changed, 319 insertions, 6 deletions
diff --git a/compiler/optimizing/load_store_analysis.cc b/compiler/optimizing/load_store_analysis.cc index f2ee345c8c..5a8ac59195 100644 --- a/compiler/optimizing/load_store_analysis.cc +++ b/compiler/optimizing/load_store_analysis.cc @@ -22,6 +22,117 @@ namespace art { // The number of heap locations for most of the methods stays below this threshold. constexpr size_t kMaxNumberOfHeapLocations = 32; +// Check if array indices array[idx1 +/- CONST] and array[idx2] MAY alias. +static bool BinaryOpAndIndexMayAlias(const HBinaryOperation* idx1, const HInstruction* idx2) { + DCHECK(idx1 != nullptr); + DCHECK(idx2 != nullptr); + + if (!idx1->IsAdd() && !idx1->IsSub()) { + // We currently only support Add and Sub operations. + return true; + } + + HConstant* cst = idx1->GetConstantRight(); + if (cst == nullptr || cst->IsArithmeticZero()) { + return true; + } + + if (idx1->GetLeastConstantLeft() == idx2) { + // for example, array[idx1 + 1] and array[idx1] + return false; + } + + return true; +} + +// Check if Add and Sub MAY alias when used as indices in arrays. +static bool BinaryOpsMayAlias(const HBinaryOperation* idx1, const HBinaryOperation* idx2) { + DCHECK(idx1!= nullptr); + DCHECK(idx2 != nullptr); + + HConstant* idx1_cst = idx1->GetConstantRight(); + HInstruction* idx1_other = idx1->GetLeastConstantLeft(); + HConstant* idx2_cst = idx2->GetConstantRight(); + HInstruction* idx2_other = idx2->GetLeastConstantLeft(); + + if (idx1_cst == nullptr || idx1_other == nullptr || + idx2_cst == nullptr || idx2_other == nullptr) { + // We only analyze patterns like [i +/- CONST]. + return true; + } + + if (idx1_other != idx2_other) { + // For example, [j+1] and [k+1] MAY alias. + return true; + } + + if ((idx1->IsAdd() && idx2->IsAdd()) || + (idx1->IsSub() && idx2->IsSub())) { + return idx1_cst->AsIntConstant()->GetValue() == idx2_cst->AsIntConstant()->GetValue(); + } + + if ((idx1->IsAdd() && idx2->IsSub()) || + (idx1->IsSub() && idx2->IsAdd())) { + // [i + CONST1] and [i - CONST2] MAY alias iff CONST1 == -CONST2. + // By checking CONST1 == -CONST2, following cases are handled: + // - Zero constants case [i+0] and [i-0] is handled. + // - Overflow cases are handled, for example: + // [i+0x80000000] and [i-0x80000000]; + // [i+0x10] and [i-0xFFFFFFF0]. + // - Other cases [i+CONST1] and [i-CONST2] without any overflow is handled. + return idx1_cst->AsIntConstant()->GetValue() == -(idx2_cst->AsIntConstant()->GetValue()); + } + + // All other cases, MAY alias. + return true; +} + +// The following array index cases are handled: +// [i] and [i] +// [CONST1] and [CONST2] +// [i] and [i+CONST] +// [i] and [i-CONST] +// [i+CONST1] and [i+CONST2] +// [i-CONST1] and [i-CONST2] +// [i+CONST1] and [i-CONST2] +// [i-CONST1] and [i+CONST2] +// For other complicated cases, we rely on other passes like GVN and simpilfier +// to optimize these cases before this pass. +// For example: [i+j+k+10] and [i+k+10+j] shall be optimized to [i7+10] and [i7+10]. +bool HeapLocationCollector::CanArrayIndicesAlias(const HInstruction* idx1, + const HInstruction* idx2) const { + DCHECK(idx1 != nullptr); + DCHECK(idx2 != nullptr); + + if (idx1 == idx2) { + // [i] and [i] + return true; + } + if (idx1->IsIntConstant() && idx2->IsIntConstant()) { + // [CONST1] and [CONST2] + return idx1->AsIntConstant()->GetValue() == idx2->AsIntConstant()->GetValue(); + } + + if (idx1->IsBinaryOperation() && !BinaryOpAndIndexMayAlias(idx1->AsBinaryOperation(), idx2)) { + // [i] and [i+/-CONST] + return false; + } + if (idx2->IsBinaryOperation() && !BinaryOpAndIndexMayAlias(idx2->AsBinaryOperation(), idx1)) { + // [i+/-CONST] and [i] + return false; + } + + if (idx1->IsBinaryOperation() && idx2->IsBinaryOperation()) { + // [i+/-CONST1] and [i+/-CONST2] + if (!BinaryOpsMayAlias(idx1->AsBinaryOperation(), idx2->AsBinaryOperation())) { + return false; + } + } + + // By default, MAY alias. + return true; +} + void LoadStoreAnalysis::Run() { for (HBasicBlock* block : graph_->GetReversePostOrder()) { heap_location_collector_.VisitBasicBlock(block); diff --git a/compiler/optimizing/load_store_analysis.h b/compiler/optimizing/load_store_analysis.h index 4e940f30bf..86fb8e0165 100644 --- a/compiler/optimizing/load_store_analysis.h +++ b/compiler/optimizing/load_store_analysis.h @@ -214,6 +214,17 @@ class HeapLocationCollector : public HGraphVisitor { return nullptr; } + size_t GetArrayAccessHeapLocation(HInstruction* array, HInstruction* index) const { + DCHECK(array != nullptr); + DCHECK(index != nullptr); + HInstruction* original_ref = HuntForOriginalReference(array); + ReferenceInfo* ref_info = FindReferenceInfoOf(original_ref); + return FindHeapLocationIndex(ref_info, + HeapLocation::kInvalidFieldOffset, + index, + HeapLocation::kDeclaringClassDefIndexForArrays); + } + bool HasHeapStores() const { return has_heap_stores_; } @@ -300,6 +311,8 @@ class HeapLocationCollector : public HGraphVisitor { return true; } + bool CanArrayIndicesAlias(const HInstruction* i1, const HInstruction* i2) const; + // `index1` and `index2` are indices in the array of collected heap locations. // Returns the position in the bit vector that tracks whether the two heap // locations may alias. @@ -336,12 +349,7 @@ class HeapLocationCollector : public HGraphVisitor { if (loc1->IsArrayElement() && loc2->IsArrayElement()) { HInstruction* array_index1 = loc1->GetIndex(); HInstruction* array_index2 = loc2->GetIndex(); - DCHECK(array_index1 != nullptr); - DCHECK(array_index2 != nullptr); - if (array_index1->IsIntConstant() && - array_index2->IsIntConstant() && - array_index1->AsIntConstant()->GetValue() != array_index2->AsIntConstant()->GetValue()) { - // Different constant indices do not alias. + if (!CanArrayIndicesAlias(array_index1, array_index2)) { return false; } ReferenceInfo* ref_info = loc1->GetReferenceInfo(); diff --git a/compiler/optimizing/load_store_analysis_test.cc b/compiler/optimizing/load_store_analysis_test.cc index 24187777f6..81344b52f6 100644 --- a/compiler/optimizing/load_store_analysis_test.cc +++ b/compiler/optimizing/load_store_analysis_test.cc @@ -184,4 +184,198 @@ TEST_F(LoadStoreAnalysisTest, FieldHeapLocations) { ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); } +TEST_F(LoadStoreAnalysisTest, ArrayIndexAliasingTest) { + HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); + graph_->AddBlock(entry); + graph_->SetEntryBlock(entry); + graph_->BuildDominatorTree(); + + HInstruction* array = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot); + HInstruction* index = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(1), 1, Primitive::kPrimInt); + HInstruction* c0 = graph_->GetIntConstant(0); + HInstruction* c1 = graph_->GetIntConstant(1); + HInstruction* c_neg1 = graph_->GetIntConstant(-1); + HInstruction* add0 = new (&allocator_) HAdd(Primitive::kPrimInt, index, c0); + HInstruction* add1 = new (&allocator_) HAdd(Primitive::kPrimInt, index, c1); + HInstruction* sub0 = new (&allocator_) HSub(Primitive::kPrimInt, index, c0); + HInstruction* sub1 = new (&allocator_) HSub(Primitive::kPrimInt, index, c1); + HInstruction* sub_neg1 = new (&allocator_) HSub(Primitive::kPrimInt, index, c_neg1); + HInstruction* rev_sub1 = new (&allocator_) HSub(Primitive::kPrimInt, c1, index); + HInstruction* arr_set1 = new (&allocator_) HArraySet(array, c0, c0, Primitive::kPrimInt, 0); + HInstruction* arr_set2 = new (&allocator_) HArraySet(array, c1, c0, Primitive::kPrimInt, 0); + HInstruction* arr_set3 = new (&allocator_) HArraySet(array, add0, c0, Primitive::kPrimInt, 0); + HInstruction* arr_set4 = new (&allocator_) HArraySet(array, add1, c0, Primitive::kPrimInt, 0); + HInstruction* arr_set5 = new (&allocator_) HArraySet(array, sub0, c0, Primitive::kPrimInt, 0); + HInstruction* arr_set6 = new (&allocator_) HArraySet(array, sub1, c0, Primitive::kPrimInt, 0); + HInstruction* arr_set7 = new (&allocator_) HArraySet(array, rev_sub1, c0, Primitive::kPrimInt, 0); + HInstruction* arr_set8 = new (&allocator_) HArraySet(array, sub_neg1, c0, Primitive::kPrimInt, 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 + + LoadStoreAnalysis lsa(graph_); + 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.GetArrayAccessHeapLocation(array, c0); + loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, c1); + ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); + + // Test alias: array[i+0] and array[i-0] + loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add0); + loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub0); + ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); + + // Test alias: array[i+1] and array[i-1] + loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add1); + loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub1); + ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); + + // Test alias: array[i+1] and array[1-i] + loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add1); + loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, rev_sub1); + ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); + + // Test alias: array[i+1] and array[i-(-1)] + loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add1); + loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_neg1); + ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); +} + +TEST_F(LoadStoreAnalysisTest, ArrayIndexCalculationOverflowTest) { + HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); + graph_->AddBlock(entry); + graph_->SetEntryBlock(entry); + graph_->BuildDominatorTree(); + + HInstruction* array = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot); + HInstruction* index = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(1), 1, Primitive::kPrimInt); + + 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 (&allocator_) HAdd(Primitive::kPrimInt, index, c_0x80000000); + HInstruction* sub_0x80000000 = new (&allocator_) HSub(Primitive::kPrimInt, index, c_0x80000000); + HInstruction* arr_set_1 = new (&allocator_) HArraySet( + array, add_0x80000000, c0, Primitive::kPrimInt, 0); + HInstruction* arr_set_2 = new (&allocator_) HArraySet( + array, sub_0x80000000, c0, Primitive::kPrimInt, 0); + + // `index+0x10` and `index-0xFFFFFFF0` array indices MAY alias. + HInstruction* add_0x10 = new (&allocator_) HAdd(Primitive::kPrimInt, index, c_0x10); + HInstruction* sub_0xFFFFFFF0 = new (&allocator_) HSub(Primitive::kPrimInt, index, c_0xFFFFFFF0); + HInstruction* arr_set_3 = new (&allocator_) HArraySet( + array, add_0x10, c0, Primitive::kPrimInt, 0); + HInstruction* arr_set_4 = new (&allocator_) HArraySet( + array, sub_0xFFFFFFF0, c0, Primitive::kPrimInt, 0); + + // `index+0x7FFFFFFF` and `index-0x80000001` array indices MAY alias. + HInstruction* add_0x7FFFFFFF = new (&allocator_) HAdd(Primitive::kPrimInt, index, c_0x7FFFFFFF); + HInstruction* sub_0x80000001 = new (&allocator_) HSub(Primitive::kPrimInt, index, c_0x80000001); + HInstruction* arr_set_5 = new (&allocator_) HArraySet( + array, add_0x7FFFFFFF, c0, Primitive::kPrimInt, 0); + HInstruction* arr_set_6 = new (&allocator_) HArraySet( + array, sub_0x80000001, c0, Primitive::kPrimInt, 0); + + // `index+0` and `index-0` array indices MAY alias. + HInstruction* add_0 = new (&allocator_) HAdd(Primitive::kPrimInt, index, c0); + HInstruction* sub_0 = new (&allocator_) HSub(Primitive::kPrimInt, index, c0); + HInstruction* arr_set_7 = new (&allocator_) HArraySet(array, add_0, c0, Primitive::kPrimInt, 0); + HInstruction* arr_set_8 = new (&allocator_) HArraySet(array, sub_0, c0, Primitive::kPrimInt, 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); + + LoadStoreAnalysis lsa(graph_); + 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.GetArrayAccessHeapLocation(array, add_0x80000000); + loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0x80000000); + ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); + + // Test alias: array[i+0x10] and array[i-0xFFFFFFF0] + loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add_0x10); + loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0xFFFFFFF0); + ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); + + // Test alias: array[i+0x7FFFFFFF] and array[i-0x80000001] + loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add_0x7FFFFFFF); + loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0x80000001); + ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); + + // Test alias: array[i+0] and array[i-0] + loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add_0); + loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0); + ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); + + // Should not alias: + loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0x80000000); + loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0x80000001); + ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); + + // Should not alias: + loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add_0); + loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0x80000000); + ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); +} + } // namespace art |