diff options
Diffstat (limited to 'compiler/optimizing')
| -rw-r--r-- | compiler/optimizing/load_store_analysis.cc | 179 | ||||
| -rw-r--r-- | compiler/optimizing/load_store_analysis.h | 129 | ||||
| -rw-r--r-- | compiler/optimizing/load_store_analysis_test.cc | 272 | ||||
| -rw-r--r-- | compiler/optimizing/load_store_elimination.cc | 38 | ||||
| -rw-r--r-- | compiler/optimizing/scheduler.cc | 9 | ||||
| -rw-r--r-- | compiler/optimizing/scheduler_test.cc | 24 |
6 files changed, 482 insertions, 169 deletions
diff --git a/compiler/optimizing/load_store_analysis.cc b/compiler/optimizing/load_store_analysis.cc index 5a8ac59195..8b1812a6de 100644 --- a/compiler/optimizing/load_store_analysis.cc +++ b/compiler/optimizing/load_store_analysis.cc @@ -22,111 +22,130 @@ 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); +// Test if two integer ranges [l1,h1] and [l2,h2] overlap. +// Note that the ranges are inclusive on both ends. +// l1|------|h1 +// l2|------|h2 +static bool CanIntegerRangesOverlap(int64_t l1, int64_t h1, int64_t l2, int64_t h2) { + return std::max(l1, l2) <= std::min(h1, h2); +} - if (!idx1->IsAdd() && !idx1->IsSub()) { +static bool IsAddOrSub(const HInstruction* instruction) { + return instruction->IsAdd() || instruction->IsSub(); +} + +static bool CanBinaryOpAndIndexAlias(const HBinaryOperation* idx1, + const size_t vector_length1, + const HInstruction* idx2, + const size_t vector_length2) { + if (!IsAddOrSub(idx1)) { // We currently only support Add and Sub operations. return true; } - - HConstant* cst = idx1->GetConstantRight(); - if (cst == nullptr || cst->IsArithmeticZero()) { + if (idx1->AsBinaryOperation()->GetLeastConstantLeft() != idx2) { + // Cannot analyze [i+CONST1] and [j]. return true; } - - if (idx1->GetLeastConstantLeft() == idx2) { - // for example, array[idx1 + 1] and array[idx1] - return false; + if (!idx1->GetConstantRight()->IsIntConstant()) { + return true; } - return true; + // Since 'i' are the same in [i+CONST] and [i], + // further compare [CONST] and [0]. + int64_t l1 = idx1->IsAdd() ? + idx1->GetConstantRight()->AsIntConstant()->GetValue() : + -idx1->GetConstantRight()->AsIntConstant()->GetValue(); + int64_t l2 = 0; + int64_t h1 = l1 + (vector_length1 - 1); + int64_t h2 = l2 + (vector_length2 - 1); + return CanIntegerRangesOverlap(l1, h1, l2, h2); } -// 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]. +static bool CanBinaryOpsAlias(const HBinaryOperation* idx1, + const size_t vector_length1, + const HBinaryOperation* idx2, + const size_t vector_length2) { + if (!IsAddOrSub(idx1) || !IsAddOrSub(idx2)) { + // We currently only support Add and Sub operations. return true; } - - if (idx1_other != idx2_other) { - // For example, [j+1] and [k+1] MAY alias. + if (idx1->AsBinaryOperation()->GetLeastConstantLeft() != + idx2->AsBinaryOperation()->GetLeastConstantLeft()) { + // Cannot analyze [i+CONST1] and [j+CONST2]. 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()); + if (!idx1->GetConstantRight()->IsIntConstant() || + !idx2->GetConstantRight()->IsIntConstant()) { + return true; } - // All other cases, MAY alias. - return true; + // Since 'i' are the same in [i+CONST1] and [i+CONST2], + // further compare [CONST1] and [CONST2]. + int64_t l1 = idx1->IsAdd() ? + idx1->GetConstantRight()->AsIntConstant()->GetValue() : + -idx1->GetConstantRight()->AsIntConstant()->GetValue(); + int64_t l2 = idx2->IsAdd() ? + idx2->GetConstantRight()->AsIntConstant()->GetValue() : + -idx2->GetConstantRight()->AsIntConstant()->GetValue(); + int64_t h1 = l1 + (vector_length1 - 1); + int64_t h2 = l2 + (vector_length2 - 1); + return CanIntegerRangesOverlap(l1, h1, l2, h2); } -// 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 { +bool HeapLocationCollector::CanArrayElementsAlias(const HInstruction* idx1, + const size_t vector_length1, + const HInstruction* idx2, + const size_t vector_length2) const { DCHECK(idx1 != nullptr); DCHECK(idx2 != nullptr); + DCHECK_GE(vector_length1, HeapLocation::kScalar); + DCHECK_GE(vector_length2, HeapLocation::kScalar); + // [i] and [i]. 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; - } + // [CONST1] and [CONST2]. + if (idx1->IsIntConstant() && idx2->IsIntConstant()) { + int64_t l1 = idx1->AsIntConstant()->GetValue(); + int64_t l2 = idx2->AsIntConstant()->GetValue(); + // To avoid any overflow in following CONST+vector_length calculation, + // use int64_t instead of int32_t. + int64_t h1 = l1 + (vector_length1 - 1); + int64_t h2 = l2 + (vector_length2 - 1); + return CanIntegerRangesOverlap(l1, h1, l2, h2); + } + + // [i+CONST] and [i]. + if (idx1->IsBinaryOperation() && + idx1->AsBinaryOperation()->GetConstantRight() != nullptr && + idx1->AsBinaryOperation()->GetLeastConstantLeft() == idx2) { + return CanBinaryOpAndIndexAlias(idx1->AsBinaryOperation(), + vector_length1, + idx2, + vector_length2); + } + + // [i] and [i+CONST]. + if (idx2->IsBinaryOperation() && + idx2->AsBinaryOperation()->GetConstantRight() != nullptr && + idx2->AsBinaryOperation()->GetLeastConstantLeft() == idx1) { + return CanBinaryOpAndIndexAlias(idx2->AsBinaryOperation(), + vector_length2, + idx1, + vector_length1); + } + + // [i+CONST1] and [i+CONST2]. + if (idx1->IsBinaryOperation() && + idx1->AsBinaryOperation()->GetConstantRight() != nullptr && + idx2->IsBinaryOperation() && + idx2->AsBinaryOperation()->GetConstantRight() != nullptr) { + return CanBinaryOpsAlias(idx1->AsBinaryOperation(), + vector_length1, + idx2->AsBinaryOperation(), + vector_length2); } // By default, MAY alias. diff --git a/compiler/optimizing/load_store_analysis.h b/compiler/optimizing/load_store_analysis.h index 5a1df45914..999026cb6a 100644 --- a/compiler/optimizing/load_store_analysis.h +++ b/compiler/optimizing/load_store_analysis.h @@ -102,23 +102,26 @@ class ReferenceInfo : public ArenaObject<kArenaAllocLSA> { class HeapLocation : public ArenaObject<kArenaAllocLSA> { public: static constexpr size_t kInvalidFieldOffset = -1; - + // Default value for heap locations which are not vector data. + static constexpr size_t kScalar = 1; // TODO: more fine-grained array types. static constexpr int16_t kDeclaringClassDefIndexForArrays = -1; HeapLocation(ReferenceInfo* ref_info, size_t offset, HInstruction* index, + size_t vector_length, int16_t declaring_class_def_index) : ref_info_(ref_info), offset_(offset), index_(index), + vector_length_(vector_length), declaring_class_def_index_(declaring_class_def_index), value_killed_by_loop_side_effects_(true) { DCHECK(ref_info != nullptr); DCHECK((offset == kInvalidFieldOffset && index != nullptr) || (offset != kInvalidFieldOffset && index == nullptr)); - if (ref_info->IsSingleton() && !IsArrayElement()) { + if (ref_info->IsSingleton() && !IsArray()) { // Assume this location's value cannot be killed by loop side effects // until proven otherwise. value_killed_by_loop_side_effects_ = false; @@ -128,6 +131,7 @@ class HeapLocation : public ArenaObject<kArenaAllocLSA> { ReferenceInfo* GetReferenceInfo() const { return ref_info_; } size_t GetOffset() const { return offset_; } HInstruction* GetIndex() const { return index_; } + size_t GetVectorLength() const { return vector_length_; } // Returns the definition of declaring class' dex index. // It's kDeclaringClassDefIndexForArrays for an array element. @@ -135,7 +139,7 @@ class HeapLocation : public ArenaObject<kArenaAllocLSA> { return declaring_class_def_index_; } - bool IsArrayElement() const { + bool IsArray() const { return index_ != nullptr; } @@ -148,15 +152,26 @@ class HeapLocation : public ArenaObject<kArenaAllocLSA> { } private: - ReferenceInfo* const ref_info_; // reference for instance/static field or array access. - const size_t offset_; // offset of static/instance field. - HInstruction* const index_; // index of an array element. - const int16_t declaring_class_def_index_; // declaring class's def's dex index. - bool value_killed_by_loop_side_effects_; // value of this location may be killed by loop - // side effects because this location is stored - // into inside a loop. This gives - // better info on whether a singleton's location - // value may be killed by loop side effects. + // Reference for instance/static field, array element or vector data. + ReferenceInfo* const ref_info_; + // Offset of static/instance field. + // Invalid when this HeapLocation is not field. + const size_t offset_; + // Index of an array element or starting index of vector data. + // Invalid when this HeapLocation is not array. + HInstruction* const index_; + // Vector length of vector data. + // When this HeapLocation is not vector data, it's value is kScalar. + const size_t vector_length_; + // Declaring class's def's dex index. + // Invalid when this HeapLocation is not field access. + const int16_t declaring_class_def_index_; + + // Value of this location may be killed by loop side effects + // because this location is stored into inside a loop. + // This gives better info on whether a singleton's location + // value may be killed by loop side effects. + bool value_killed_by_loop_side_effects_; DISALLOW_COPY_AND_ASSIGN(HeapLocation); }; @@ -218,14 +233,26 @@ class HeapLocationCollector : public HGraphVisitor { return nullptr; } - size_t GetArrayAccessHeapLocation(HInstruction* array, HInstruction* index) const { + size_t GetFieldHeapLocation(HInstruction* object, const FieldInfo* field) const { + DCHECK(object != nullptr); + DCHECK(field != nullptr); + return FindHeapLocationIndex(FindReferenceInfoOf(HuntForOriginalReference(object)), + 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); - HInstruction* original_ref = HuntForOriginalReference(array); - ReferenceInfo* ref_info = FindReferenceInfoOf(original_ref); - return FindHeapLocationIndex(ref_info, + DCHECK_GE(vector_length, HeapLocation::kScalar); + return FindHeapLocationIndex(FindReferenceInfoOf(HuntForOriginalReference(array)), HeapLocation::kInvalidFieldOffset, index, + vector_length, HeapLocation::kDeclaringClassDefIndexForArrays); } @@ -242,15 +269,26 @@ class HeapLocationCollector : public HGraphVisitor { } // Find and return the heap location index in heap_locations_. + // NOTE: When heap locations are created, potentially aliasing/overlapping + // accesses are given different indexes. This find function also + // doesn't take aliasing/overlapping into account. For example, + // this function returns three different indexes for: + // - ref_info=array, index=i, vector_length=kScalar; + // - ref_info=array, index=i, vector_length=2; + // - ref_info=array, index=i, vector_length=4; + // In later analysis, ComputeMayAlias() and MayAlias() compute and tell whether + // these indexes alias. size_t FindHeapLocationIndex(ReferenceInfo* ref_info, size_t offset, HInstruction* index, + size_t vector_length, int16_t declaring_class_def_index) const { for (size_t i = 0; i < heap_locations_.size(); i++) { HeapLocation* loc = heap_locations_[i]; if (loc->GetReferenceInfo() == ref_info && loc->GetOffset() == offset && loc->GetIndex() == index && + loc->GetVectorLength() == vector_length && loc->GetDeclaringClassDefIndex() == declaring_class_def_index) { return i; } @@ -315,7 +353,10 @@ class HeapLocationCollector : public HGraphVisitor { return true; } - bool CanArrayIndicesAlias(const HInstruction* i1, const HInstruction* i2) const; + bool CanArrayElementsAlias(const HInstruction* idx1, + const size_t vector_length1, + const HInstruction* idx2, + const size_t vector_length2) 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 @@ -340,7 +381,7 @@ class HeapLocationCollector : public HGraphVisitor { HeapLocation* loc2 = heap_locations_[index2]; if (loc1->GetOffset() != loc2->GetOffset()) { // Either two different instance fields, or one is an instance - // field and the other is an array element. + // field and the other is an array data. return false; } if (loc1->GetDeclaringClassDefIndex() != loc2->GetDeclaringClassDefIndex()) { @@ -350,10 +391,12 @@ class HeapLocationCollector : public HGraphVisitor { if (!CanReferencesAlias(loc1->GetReferenceInfo(), loc2->GetReferenceInfo())) { return false; } - if (loc1->IsArrayElement() && loc2->IsArrayElement()) { - HInstruction* array_index1 = loc1->GetIndex(); - HInstruction* array_index2 = loc2->GetIndex(); - if (!CanArrayIndicesAlias(array_index1, array_index2)) { + if (loc1->IsArray() && loc2->IsArray()) { + HInstruction* idx1 = loc1->GetIndex(); + HInstruction* idx2 = loc2->GetIndex(); + size_t vector_length1 = loc1->GetVectorLength(); + size_t vector_length2 = loc2->GetVectorLength(); + if (!CanArrayElementsAlias(idx1, vector_length1, idx2, vector_length2)) { return false; } ReferenceInfo* ref_info = loc1->GetReferenceInfo(); @@ -383,14 +426,15 @@ class HeapLocationCollector : public HGraphVisitor { HeapLocation* GetOrCreateHeapLocation(HInstruction* ref, size_t offset, HInstruction* index, + size_t vector_length, int16_t declaring_class_def_index) { HInstruction* original_ref = HuntForOriginalReference(ref); ReferenceInfo* ref_info = GetOrCreateReferenceInfo(original_ref); size_t heap_location_idx = FindHeapLocationIndex( - ref_info, offset, index, declaring_class_def_index); + ref_info, offset, index, vector_length, declaring_class_def_index); if (heap_location_idx == kHeapLocationNotFound) { HeapLocation* heap_loc = new (GetGraph()->GetAllocator()) - HeapLocation(ref_info, offset, index, declaring_class_def_index); + HeapLocation(ref_info, offset, index, vector_length, declaring_class_def_index); heap_locations_.push_back(heap_loc); return heap_loc; } @@ -403,12 +447,19 @@ class HeapLocationCollector : public HGraphVisitor { } const uint16_t declaring_class_def_index = field_info.GetDeclaringClassDefIndex(); const size_t offset = field_info.GetFieldOffset().SizeValue(); - return GetOrCreateHeapLocation(ref, offset, nullptr, declaring_class_def_index); + return GetOrCreateHeapLocation(ref, + offset, + nullptr, + HeapLocation::kScalar, + declaring_class_def_index); } - void VisitArrayAccess(HInstruction* array, HInstruction* index) { - GetOrCreateHeapLocation(array, HeapLocation::kInvalidFieldOffset, - index, HeapLocation::kDeclaringClassDefIndexForArrays); + void VisitArrayAccess(HInstruction* array, HInstruction* index, size_t vector_length) { + GetOrCreateHeapLocation(array, + HeapLocation::kInvalidFieldOffset, + index, + vector_length, + HeapLocation::kDeclaringClassDefIndexForArrays); } void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { @@ -456,12 +507,30 @@ class HeapLocationCollector : public HGraphVisitor { // since we cannot accurately track the fields. void VisitArrayGet(HArrayGet* instruction) OVERRIDE { - VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1)); + HInstruction* array = instruction->InputAt(0); + HInstruction* index = instruction->InputAt(1); + VisitArrayAccess(array, index, HeapLocation::kScalar); CreateReferenceInfoForReferenceType(instruction); } void VisitArraySet(HArraySet* instruction) OVERRIDE { - VisitArrayAccess(instruction->InputAt(0), instruction->InputAt(1)); + HInstruction* array = instruction->InputAt(0); + HInstruction* index = instruction->InputAt(1); + VisitArrayAccess(array, index, 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()); + CreateReferenceInfoForReferenceType(instruction); + } + + void VisitVecStore(HVecStore* instruction) OVERRIDE { + HInstruction* array = instruction->InputAt(0); + HInstruction* index = instruction->InputAt(1); + VisitArrayAccess(array, index, 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 b41e1e4d00..56361a8c90 100644 --- a/compiler/optimizing/load_store_analysis_test.cc +++ b/compiler/optimizing/load_store_analysis_test.cc @@ -78,11 +78,12 @@ TEST_F(LoadStoreAnalysisTest, ArrayHeapLocations) { // Test queries on HeapLocationCollector's ref info and index records. ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(array); - size_t field_off = HeapLocation::kInvalidFieldOffset; + 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_off, c1, class_def); - size_t loc2 = heap_location_collector.FindHeapLocationIndex(ref, field_off, c2, class_def); - size_t loc3 = heap_location_collector.FindHeapLocationIndex(ref, field_off, index, class_def); + 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); // must find this reference info for array in HeapLocationCollector. ASSERT_TRUE(ref != nullptr); // must find these heap locations; @@ -167,10 +168,8 @@ TEST_F(LoadStoreAnalysisTest, FieldHeapLocations) { // Test queries on HeapLocationCollector's ref info and index records. ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(object); - size_t loc1 = heap_location_collector.FindHeapLocationIndex( - ref, 10, nullptr, kUnknownClassDefIndex); - size_t loc2 = heap_location_collector.FindHeapLocationIndex( - ref, 20, nullptr, kUnknownClassDefIndex); + 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. @@ -247,31 +246,236 @@ TEST_F(LoadStoreAnalysisTest, ArrayIndexAliasingTest) { 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); + loc1 = heap_location_collector.GetArrayHeapLocation(array, c0); + loc2 = heap_location_collector.GetArrayHeapLocation(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); + loc1 = heap_location_collector.GetArrayHeapLocation(array, add0); + loc2 = heap_location_collector.GetArrayHeapLocation(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); + loc1 = heap_location_collector.GetArrayHeapLocation(array, add1); + loc2 = heap_location_collector.GetArrayHeapLocation(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); + loc1 = heap_location_collector.GetArrayHeapLocation(array, add1); + loc2 = heap_location_collector.GetArrayHeapLocation(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); + loc1 = heap_location_collector.GetArrayHeapLocation(array, add1); + loc2 = heap_location_collector.GetArrayHeapLocation(array, sub_neg1); ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); } +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); + + LoadStoreAnalysis lsa(graph_); + 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(array, c0); + loc2 = heap_location_collector.GetArrayHeapLocation(array, c0, 4); + ASSERT_TRUE(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); + 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); + 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); + 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); + 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); + 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); + 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); + 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); + 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); + 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); + 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); + 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); + ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); +} + TEST_F(LoadStoreAnalysisTest, ArrayIndexCalculationOverflowTest) { HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); graph_->AddBlock(entry); @@ -359,33 +563,33 @@ TEST_F(LoadStoreAnalysisTest, ArrayIndexCalculationOverflowTest) { 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); + loc1 = heap_location_collector.GetArrayHeapLocation(array, add_0x80000000); + loc2 = heap_location_collector.GetArrayHeapLocation(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); + loc1 = heap_location_collector.GetArrayHeapLocation(array, add_0x10); + loc2 = heap_location_collector.GetArrayHeapLocation(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); + loc1 = heap_location_collector.GetArrayHeapLocation(array, add_0x7FFFFFFF); + loc2 = heap_location_collector.GetArrayHeapLocation(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); + loc1 = heap_location_collector.GetArrayHeapLocation(array, add_0); + loc2 = heap_location_collector.GetArrayHeapLocation(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); + loc1 = heap_location_collector.GetArrayHeapLocation(array, sub_0x80000000); + loc2 = heap_location_collector.GetArrayHeapLocation(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); + loc1 = heap_location_collector.GetArrayHeapLocation(array, add_0); + loc2 = heap_location_collector.GetArrayHeapLocation(array, sub_0x80000000); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); } @@ -443,10 +647,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.GetArrayAccessHeapLocation(array, c1); - size_t loc2 = heap_location_collector.GetArrayAccessHeapLocation(bound_type, c1); - size_t loc3 = heap_location_collector.GetArrayAccessHeapLocation(null_check, c1); - size_t loc4 = heap_location_collector.GetArrayAccessHeapLocation(inter_addr, c1); + 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); 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 c89961353b..8678fab655 100644 --- a/compiler/optimizing/load_store_elimination.cc +++ b/compiler/optimizing/load_store_elimination.cc @@ -302,11 +302,12 @@ class LSEVisitor : public HGraphDelegateVisitor { 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, declaring_class_def_index); + ref_info, offset, index, vector_length, declaring_class_def_index); DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); ScopedArenaVector<HInstruction*>& heap_values = heap_values_for_[instruction->GetBlock()->GetBlockId()]; @@ -367,12 +368,13 @@ class LSEVisitor : public HGraphDelegateVisitor { HInstruction* ref, size_t offset, HInstruction* index, + size_t vector_length, int16_t declaring_class_def_index, HInstruction* 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, declaring_class_def_index); + ref_info, offset, index, vector_length, declaring_class_def_index); DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); ScopedArenaVector<HInstruction*>& heap_values = heap_values_for_[instruction->GetBlock()->GetBlockId()]; @@ -446,7 +448,12 @@ class LSEVisitor : public HGraphDelegateVisitor { 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, declaring_class_def_index); + VisitGetLocation(instruction, + obj, + offset, + nullptr, + HeapLocation::kScalar, + declaring_class_def_index); } void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { @@ -454,14 +461,25 @@ class LSEVisitor : public HGraphDelegateVisitor { size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); HInstruction* value = instruction->InputAt(1); - VisitSetLocation(instruction, obj, offset, nullptr, declaring_class_def_index, value); + VisitSetLocation(instruction, + obj, + offset, + nullptr, + HeapLocation::kScalar, + declaring_class_def_index, + 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, declaring_class_def_index); + VisitGetLocation(instruction, + cls, + offset, + nullptr, + HeapLocation::kScalar, + declaring_class_def_index); } void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { @@ -469,7 +487,13 @@ class LSEVisitor : public HGraphDelegateVisitor { 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, declaring_class_def_index, value); + VisitSetLocation(instruction, + cls, + offset, + nullptr, + HeapLocation::kScalar, + declaring_class_def_index, + value); } void VisitArrayGet(HArrayGet* instruction) OVERRIDE { @@ -479,6 +503,7 @@ class LSEVisitor : public HGraphDelegateVisitor { array, HeapLocation::kInvalidFieldOffset, index, + HeapLocation::kScalar, HeapLocation::kDeclaringClassDefIndexForArrays); } @@ -490,6 +515,7 @@ class LSEVisitor : public HGraphDelegateVisitor { array, HeapLocation::kInvalidFieldOffset, index, + HeapLocation::kScalar, HeapLocation::kDeclaringClassDefIndexForArrays, value); } diff --git a/compiler/optimizing/scheduler.cc b/compiler/optimizing/scheduler.cc index 8cc376c3a6..bb28d50b56 100644 --- a/compiler/optimizing/scheduler.cc +++ b/compiler/optimizing/scheduler.cc @@ -72,7 +72,7 @@ static bool MayHaveReorderingDependency(SideEffects node, SideEffects other) { size_t SchedulingGraph::ArrayAccessHeapLocation(HInstruction* array, HInstruction* index) const { DCHECK(heap_location_collector_ != nullptr); - size_t heap_loc = heap_location_collector_->GetArrayAccessHeapLocation(array, index); + size_t heap_loc = heap_location_collector_->GetArrayHeapLocation(array, index); // This array access should be analyzed and added to HeapLocationCollector before. DCHECK(heap_loc != HeapLocationCollector::kHeapLocationNotFound); return heap_loc; @@ -153,12 +153,7 @@ size_t SchedulingGraph::FieldAccessHeapLocation(HInstruction* obj, const FieldIn DCHECK(field != nullptr); DCHECK(heap_location_collector_ != nullptr); - size_t heap_loc = heap_location_collector_->FindHeapLocationIndex( - heap_location_collector_->FindReferenceInfoOf( - heap_location_collector_->HuntForOriginalReference(obj)), - field->GetFieldOffset().SizeValue(), - nullptr, - field->GetDeclaringClassDefIndex()); + size_t heap_loc = heap_location_collector_->GetFieldHeapLocation(obj, field); // This field access should be analyzed and added to HeapLocationCollector before. DCHECK(heap_loc != HeapLocationCollector::kHeapLocationNotFound); diff --git a/compiler/optimizing/scheduler_test.cc b/compiler/optimizing/scheduler_test.cc index 75dce81550..104ebc79c2 100644 --- a/compiler/optimizing/scheduler_test.cc +++ b/compiler/optimizing/scheduler_test.cc @@ -294,38 +294,38 @@ class SchedulerTest : public OptimizingUnitTest { size_t loc2 = HeapLocationCollector::kHeapLocationNotFound; // Test side effect dependency: array[0] and array[1] - loc1 = heap_location_collector.GetArrayAccessHeapLocation(arr, c0); - loc2 = heap_location_collector.GetArrayAccessHeapLocation(arr, c1); + loc1 = heap_location_collector.GetArrayHeapLocation(arr, c0); + loc2 = heap_location_collector.GetArrayHeapLocation(arr, c1); 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.GetArrayAccessHeapLocation(arr, i); - loc2 = heap_location_collector.GetArrayAccessHeapLocation(arr, j); + loc1 = heap_location_collector.GetArrayHeapLocation(arr, i); + loc2 = heap_location_collector.GetArrayHeapLocation(arr, 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.GetArrayAccessHeapLocation(arr, i); - loc2 = heap_location_collector.GetArrayAccessHeapLocation(arr, add0); + loc1 = heap_location_collector.GetArrayHeapLocation(arr, i); + loc2 = heap_location_collector.GetArrayHeapLocation(arr, 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.GetArrayAccessHeapLocation(arr, i); - loc2 = heap_location_collector.GetArrayAccessHeapLocation(arr, sub0); + loc1 = heap_location_collector.GetArrayHeapLocation(arr, i); + loc2 = heap_location_collector.GetArrayHeapLocation(arr, 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.GetArrayAccessHeapLocation(arr, i); - loc2 = heap_location_collector.GetArrayAccessHeapLocation(arr, add1); + loc1 = heap_location_collector.GetArrayHeapLocation(arr, i); + loc2 = heap_location_collector.GetArrayHeapLocation(arr, 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.GetArrayAccessHeapLocation(arr, add1); - loc2 = heap_location_collector.GetArrayAccessHeapLocation(arr, sub1); + loc1 = heap_location_collector.GetArrayHeapLocation(arr, add1); + loc2 = heap_location_collector.GetArrayHeapLocation(arr, sub1); ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub1, arr_set_add1)); |