From 15693bfdf9fa3ec79327a77b7e10315614d716cc Mon Sep 17 00:00:00 2001 From: David Brazdil Date: Wed, 16 Dec 2015 10:30:45 +0000 Subject: [PATCH] ART: Resolve ambiguous ArraySets Just like aget(-wide), the value operand of aput(-wide) bytecode instructions can be both int/long and float/double. This patch builds on the previous mechanism for resolving type of ArrayGets to type the values of ArraySets based on the reference type of the array. Bug: 22538329 Change-Id: Ic86abbb58de146692de04476b555010b6fcdd8b6 --- compiler/optimizing/induction_var_analysis_test.cc | 6 +- compiler/optimizing/licm_test.cc | 20 +++-- compiler/optimizing/load_store_elimination.cc | 28 ++----- compiler/optimizing/nodes.h | 2 +- compiler/optimizing/optimizing_compiler.cc | 4 +- compiler/optimizing/optimizing_compiler_stats.h | 4 +- compiler/optimizing/ssa_builder.cc | 96 +++++++++++++++------- compiler/optimizing/ssa_builder.h | 11 ++- .../smali/ArraySet.smali | 51 ++++++++++++ 9 files changed, 153 insertions(+), 69 deletions(-) create mode 100644 test/552-checker-primitive-typeprop/smali/ArraySet.smali diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc index 776c115e9..29a184565 100644 --- a/compiler/optimizing/induction_var_analysis_test.cc +++ b/compiler/optimizing/induction_var_analysis_test.cc @@ -85,6 +85,7 @@ class InductionVarAnalysisTest : public CommonCompilerTest { constant0_ = graph_->GetIntConstant(0); constant1_ = graph_->GetIntConstant(1); constant100_ = graph_->GetIntConstant(100); + float_constant0_ = graph_->GetFloatConstant(0.0f); induc_ = new (&allocator_) HLocal(n); entry_->AddInstruction(induc_); entry_->AddInstruction(new (&allocator_) HStoreLocal(induc_, constant0_)); @@ -156,8 +157,10 @@ class InductionVarAnalysisTest : public CommonCompilerTest { HInstruction* InsertArrayStore(HLocal* subscript, int d) { HInstruction* load = InsertInstruction( new (&allocator_) HLoadLocal(subscript, Primitive::kPrimInt), d); + // ArraySet is given a float value in order to avoid SsaBuilder typing + // it from the array's non-existent reference type info. return InsertInstruction(new (&allocator_) HArraySet( - parameter_, load, constant0_, Primitive::kPrimInt, 0), d); + parameter_, load, float_constant0_, Primitive::kPrimFloat, 0), d); } // Returns induction information of instruction in loop at depth d. @@ -187,6 +190,7 @@ class InductionVarAnalysisTest : public CommonCompilerTest { HInstruction* constant0_; HInstruction* constant1_; HInstruction* constant100_; + HInstruction* float_constant0_; HLocal* induc_; // "vreg_n", the "k" HLocal* tmp_; // "vreg_n+1" HLocal* dum_; // "vreg_n+2" diff --git a/compiler/optimizing/licm_test.cc b/compiler/optimizing/licm_test.cc index aa60fd646..2b63ec897 100644 --- a/compiler/optimizing/licm_test.cc +++ b/compiler/optimizing/licm_test.cc @@ -65,7 +65,8 @@ class LICMTest : public CommonCompilerTest { // Provide boiler-plate instructions. parameter_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); entry_->AddInstruction(parameter_); - constant_ = graph_->GetIntConstant(42); + int_constant_ = graph_->GetIntConstant(42); + float_constant_ = graph_->GetFloatConstant(42.0f); loop_preheader_->AddInstruction(new (&allocator_) HGoto()); loop_header_->AddInstruction(new (&allocator_) HIf(parameter_)); loop_body_->AddInstruction(new (&allocator_) HGoto()); @@ -95,7 +96,8 @@ class LICMTest : public CommonCompilerTest { HBasicBlock* exit_; HInstruction* parameter_; // "this" - HInstruction* constant_; + HInstruction* int_constant_; + HInstruction* float_constant_; }; // @@ -118,7 +120,7 @@ TEST_F(LICMTest, FieldHoisting) { 0); loop_body_->InsertInstructionBefore(get_field, loop_body_->GetLastInstruction()); HInstruction* set_field = new (&allocator_) HInstanceFieldSet( - parameter_, constant_, Primitive::kPrimInt, MemberOffset(20), + parameter_, int_constant_, Primitive::kPrimInt, MemberOffset(20), false, kUnknownFieldIndex, kUnknownClassDefIndex, graph_->GetDexFile(), dex_cache, 0); loop_body_->InsertInstructionBefore(set_field, loop_body_->GetLastInstruction()); @@ -167,11 +169,13 @@ TEST_F(LICMTest, ArrayHoisting) { BuildLoop(); // Populate the loop with instructions: set/get array with different types. + // ArrayGet is typed as kPrimByte and ArraySet given a float value in order to + // avoid SsaBuilder's typing of ambiguous array operations from reference type info. HInstruction* get_array = new (&allocator_) HArrayGet( - parameter_, constant_, Primitive::kPrimByte, 0); + parameter_, int_constant_, Primitive::kPrimByte, 0); loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction()); HInstruction* set_array = new (&allocator_) HArraySet( - parameter_, constant_, constant_, Primitive::kPrimShort, 0); + parameter_, int_constant_, float_constant_, Primitive::kPrimShort, 0); loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction()); EXPECT_EQ(get_array->GetBlock(), loop_body_); @@ -185,11 +189,13 @@ TEST_F(LICMTest, NoArrayHoisting) { BuildLoop(); // Populate the loop with instructions: set/get array with same types. + // ArrayGet is typed as kPrimByte and ArraySet given a float value in order to + // avoid SsaBuilder's typing of ambiguous array operations from reference type info. HInstruction* get_array = new (&allocator_) HArrayGet( - parameter_, constant_, Primitive::kPrimByte, 0); + parameter_, int_constant_, Primitive::kPrimByte, 0); loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction()); HInstruction* set_array = new (&allocator_) HArraySet( - parameter_, get_array, constant_, Primitive::kPrimByte, 0); + parameter_, get_array, float_constant_, Primitive::kPrimByte, 0); loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction()); EXPECT_EQ(get_array->GetBlock(), loop_body_); diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc index 727f2bb71..2b313f6b8 100644 --- a/compiler/optimizing/load_store_elimination.cc +++ b/compiler/optimizing/load_store_elimination.cc @@ -678,16 +678,6 @@ class LSEVisitor : public HGraphVisitor { } } - static bool IsIntFloatAlias(Primitive::Type type1, Primitive::Type type2) { - return (type1 == Primitive::kPrimFloat && type2 == Primitive::kPrimInt) || - (type2 == Primitive::kPrimFloat && type1 == Primitive::kPrimInt); - } - - static bool IsLongDoubleAlias(Primitive::Type type1, Primitive::Type type2) { - return (type1 == Primitive::kPrimDouble && type2 == Primitive::kPrimLong) || - (type2 == Primitive::kPrimDouble && type1 == Primitive::kPrimLong); - } - void VisitGetLocation(HInstruction* instruction, HInstruction* ref, size_t offset, @@ -716,22 +706,14 @@ class LSEVisitor : public HGraphVisitor { // Get the real heap value of the store. heap_value = store->InputAt(1); } - if ((heap_value != kUnknownHeapValue) && - // Keep the load due to possible I/F, J/D array aliasing. - // See b/22538329 for details. - !IsIntFloatAlias(heap_value->GetType(), instruction->GetType()) && - !IsLongDoubleAlias(heap_value->GetType(), instruction->GetType())) { - removed_loads_.push_back(instruction); - substitute_instructions_for_loads_.push_back(heap_value); - TryRemovingNullCheck(instruction); - return; - } - - // Load isn't eliminated. if (heap_value == kUnknownHeapValue) { - // Put the load as the value into the HeapLocation. + // 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; + } else { + removed_loads_.push_back(instruction); + substitute_instructions_for_loads_.push_back(heap_value); + TryRemovingNullCheck(instruction); } } diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index dc54bdae2..1a7cbdeb5 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -101,7 +101,7 @@ enum IfCondition { enum BuildSsaResult { kBuildSsaFailNonNaturalLoop, kBuildSsaFailThrowCatchLoop, - kBuildSsaFailAmbiguousArrayGet, + kBuildSsaFailAmbiguousArrayOp, kBuildSsaSuccess, }; diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 3f9e15120..3eb72744e 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -786,8 +786,8 @@ CodeGenerator* OptimizingCompiler::TryCompile(ArenaAllocator* arena, case kBuildSsaFailThrowCatchLoop: MaybeRecordStat(MethodCompilationStat::kNotCompiledThrowCatchLoop); break; - case kBuildSsaFailAmbiguousArrayGet: - MaybeRecordStat(MethodCompilationStat::kNotCompiledAmbiguousArrayGet); + case kBuildSsaFailAmbiguousArrayOp: + MaybeRecordStat(MethodCompilationStat::kNotCompiledAmbiguousArrayOp); break; case kBuildSsaSuccess: UNREACHABLE(); diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h index 4713514bb..bca1632e3 100644 --- a/compiler/optimizing/optimizing_compiler_stats.h +++ b/compiler/optimizing/optimizing_compiler_stats.h @@ -40,7 +40,7 @@ enum MethodCompilationStat { kNotCompiledBranchOutsideMethodCode, kNotCompiledNonNaturalLoop, kNotCompiledThrowCatchLoop, - kNotCompiledAmbiguousArrayGet, + kNotCompiledAmbiguousArrayOp, kNotCompiledHugeMethod, kNotCompiledLargeMethodNoBranches, kNotCompiledMalformedOpcode, @@ -108,7 +108,7 @@ class OptimizingCompilerStats { case kNotCompiledBranchOutsideMethodCode: name = "NotCompiledBranchOutsideMethodCode"; break; case kNotCompiledNonNaturalLoop : name = "NotCompiledNonNaturalLoop"; break; case kNotCompiledThrowCatchLoop : name = "NotCompiledThrowCatchLoop"; break; - case kNotCompiledAmbiguousArrayGet : name = "NotCompiledAmbiguousArrayGet"; break; + case kNotCompiledAmbiguousArrayOp : name = "NotCompiledAmbiguousArrayOp"; break; case kNotCompiledHugeMethod : name = "NotCompiledHugeMethod"; break; case kNotCompiledLargeMethodNoBranches : name = "NotCompiledLargeMethodNoBranches"; break; case kNotCompiledMalformedOpcode : name = "NotCompiledMalformedOpcode"; break; diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc index 9ea352dde..f6bab8efc 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -317,27 +317,15 @@ static HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { return equivalent; } -// Returns true if the array input of `aget` is either of type int[] or long[]. -// Should only be called on ArrayGets with ambiguous type (int/float, long/double) -// on arrays which were typed to an array class by RTP. -static bool IsArrayGetOnIntegralArray(HArrayGet* aget) SHARED_REQUIRES(Locks::mutator_lock_) { - ReferenceTypeInfo array_type = aget->GetArray()->GetReferenceTypeInfo(); +static Primitive::Type GetPrimitiveArrayComponentType(HInstruction* array) + SHARED_REQUIRES(Locks::mutator_lock_) { + ReferenceTypeInfo array_type = array->GetReferenceTypeInfo(); DCHECK(array_type.IsPrimitiveArrayClass()); - ReferenceTypeInfo::TypeHandle array_type_handle = array_type.GetTypeHandle(); - - bool is_integral_type; - if (Primitive::Is64BitType(aget->GetType())) { - is_integral_type = array_type_handle->GetComponentType()->IsPrimitiveLong(); - DCHECK(is_integral_type || array_type_handle->GetComponentType()->IsPrimitiveDouble()); - } else { - is_integral_type = array_type_handle->GetComponentType()->IsPrimitiveInt(); - DCHECK(is_integral_type || array_type_handle->GetComponentType()->IsPrimitiveFloat()); - } - return is_integral_type; + return array_type.GetTypeHandle()->GetComponentType()->GetPrimitiveType(); } -bool SsaBuilder::FixAmbiguousArrayGets() { - if (ambiguous_agets_.empty()) { +bool SsaBuilder::FixAmbiguousArrayOps() { + if (ambiguous_agets_.empty() && ambiguous_asets_.empty()) { return true; } @@ -351,13 +339,17 @@ bool SsaBuilder::FixAmbiguousArrayGets() { ScopedObjectAccess soa(Thread::Current()); for (HArrayGet* aget_int : ambiguous_agets_) { - if (!aget_int->GetArray()->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { + HInstruction* array = aget_int->GetArray(); + if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { // RTP did not type the input array. Bail. return false; } HArrayGet* aget_float = FindFloatOrDoubleEquivalentOfArrayGet(aget_int); - if (IsArrayGetOnIntegralArray(aget_int)) { + Primitive::Type array_type = GetPrimitiveArrayComponentType(array); + DCHECK_EQ(Primitive::Is64BitType(aget_int->GetType()), Primitive::Is64BitType(array_type)); + + if (Primitive::IsIntOrLongType(array_type)) { if (aget_float != nullptr) { // There is a float/double equivalent. We must replace it and re-run // primitive type propagation on all dependent instructions. @@ -366,6 +358,7 @@ bool SsaBuilder::FixAmbiguousArrayGets() { AddDependentInstructionsToWorklist(aget_int, &worklist); } } else { + DCHECK(Primitive::IsFloatingPointType(array_type)); if (aget_float == nullptr) { // This is a float/double ArrayGet but there were no typed uses which // would create the typed equivalent. Create it now. @@ -379,11 +372,47 @@ bool SsaBuilder::FixAmbiguousArrayGets() { AddDependentInstructionsToWorklist(aget_float, &worklist); } } - } - // Set a flag stating that types of ArrayGets have been resolved. This is used - // by GetFloatOrDoubleEquivalentOfArrayGet to report conflict. - agets_fixed_ = true; + // Set a flag stating that types of ArrayGets have been resolved. Requesting + // equivalent of the wrong type with GetFloatOrDoubleEquivalentOfArrayGet + // will fail from now on. + agets_fixed_ = true; + + for (HArraySet* aset : ambiguous_asets_) { + HInstruction* array = aset->GetArray(); + if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { + // RTP did not type the input array. Bail. + return false; + } + + HInstruction* value = aset->GetValue(); + Primitive::Type value_type = value->GetType(); + Primitive::Type array_type = GetPrimitiveArrayComponentType(array); + DCHECK_EQ(Primitive::Is64BitType(value_type), Primitive::Is64BitType(array_type)); + + if (Primitive::IsFloatingPointType(array_type)) { + if (!Primitive::IsFloatingPointType(value_type)) { + DCHECK(Primitive::IsIntegralType(value_type)); + // Array elements are floating-point but the value has not been replaced + // with its floating-point equivalent. The replacement must always + // succeed in code validated by the verifier. + HInstruction* equivalent = GetFloatOrDoubleEquivalent(value, array_type); + DCHECK(equivalent != nullptr); + aset->ReplaceInput(equivalent, /* input_index */ 2); + if (equivalent->IsPhi()) { + // Returned equivalent is a phi which may not have had its inputs + // replaced yet. We need to run primitive type propagation on it. + worklist.push_back(equivalent->AsPhi()); + } + } + } else { + // Array elements are integral and the value assigned to it initially + // was integral too. Nothing to do. + DCHECK(Primitive::IsIntegralType(array_type)); + DCHECK(Primitive::IsIntegralType(value_type)); + } + } + } if (!worklist.empty()) { ProcessPrimitiveTypePropagationWorklist(&worklist); @@ -429,10 +458,11 @@ BuildSsaResult SsaBuilder::BuildSsa() { ReferenceTypePropagation(GetGraph(), handles_).Run(); // 7) Step 1) duplicated ArrayGet instructions with ambiguous type (int/float - // or long/double). Now that RTP computed the type of the array input, the - // ambiguity can be resolved and the correct equivalent kept. - if (!FixAmbiguousArrayGets()) { - return kBuildSsaFailAmbiguousArrayGet; + // or long/double) and marked ArraySets with ambiguous input type. Now that RTP + // computed the type of the array input, the ambiguity can be resolved and the + // correct equivalents kept. + if (!FixAmbiguousArrayOps()) { + return kBuildSsaFailAmbiguousArrayOp; } // 8) Mark dead phis. This will mark phis which are not used by instructions @@ -702,7 +732,7 @@ HArrayGet* SsaBuilder::GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { // int/long. Requesting a float/double equivalent should lead to a conflict. if (kIsDebugBuild) { ScopedObjectAccess soa(Thread::Current()); - DCHECK(IsArrayGetOnIntegralArray(aget)); + DCHECK(Primitive::IsIntOrLongType(GetPrimitiveArrayComponentType(aget->GetArray()))); } return nullptr; } else { @@ -847,4 +877,12 @@ void SsaBuilder::VisitArrayGet(HArrayGet* aget) { VisitInstruction(aget); } +void SsaBuilder::VisitArraySet(HArraySet* aset) { + Primitive::Type type = aset->GetValue()->GetType(); + if (Primitive::IsIntOrLongType(type)) { + ambiguous_asets_.push_back(aset); + } + VisitInstruction(aset); +} + } // namespace art diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h index ed6f5cab5..0fcc3a130 100644 --- a/compiler/optimizing/ssa_builder.h +++ b/compiler/optimizing/ssa_builder.h @@ -56,6 +56,7 @@ class SsaBuilder : public HGraphVisitor { current_locals_(nullptr), loop_headers_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), ambiguous_agets_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), + ambiguous_asets_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), locals_for_(graph->GetBlocks().size(), ArenaVector(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) { @@ -75,6 +76,7 @@ class SsaBuilder : public HGraphVisitor { void VisitInstruction(HInstruction* instruction); void VisitTemporary(HTemporary* instruction); void VisitArrayGet(HArrayGet* aget); + void VisitArraySet(HArraySet* aset); static constexpr const char* kSsaBuilderPassName = "ssa_builder"; @@ -85,10 +87,10 @@ class SsaBuilder : public HGraphVisitor { void EquivalentPhisCleanup(); void RunPrimitiveTypePropagation(); - // Attempts to resolve types of aget and aget-wide instructions from reference - // type information on the input array. Returns false if the type of the array - // is unknown. - bool FixAmbiguousArrayGets(); + // Attempts to resolve types of aget(-wide) instructions and type values passed + // to aput(-wide) instructions from reference type information on the array + // input. Returns false if the type of an array is unknown. + bool FixAmbiguousArrayOps(); bool TypeInputsOfPhi(HPhi* phi, ArenaVector* worklist); bool UpdatePrimitiveType(HPhi* phi, ArenaVector* worklist); @@ -115,6 +117,7 @@ class SsaBuilder : public HGraphVisitor { ArenaVector loop_headers_; ArenaVector ambiguous_agets_; + ArenaVector ambiguous_asets_; // HEnvironment for each block. ArenaVector> locals_for_; diff --git a/test/552-checker-primitive-typeprop/smali/ArraySet.smali b/test/552-checker-primitive-typeprop/smali/ArraySet.smali new file mode 100644 index 000000000..57d8606ab --- /dev/null +++ b/test/552-checker-primitive-typeprop/smali/ArraySet.smali @@ -0,0 +1,51 @@ +# Copyright (C) 2015 The Android Open Source Project +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +.class public LArraySet; +.super Ljava/lang/Object; + +# Test ArraySet on int[] and float[] arrays. The input should be typed accordingly. +# Note that the input is a Phi to make sure primitive type propagation is re-run +# on the replaced inputs. + +## CHECK-START: void ArraySet.ambiguousSet(int[], float[], boolean) ssa_builder (after) +## CHECK-DAG: <> ParameterValue klass:int[] +## CHECK-DAG: <> IntConstant 0 +## CHECK-DAG: <> IntConstant 1073741824 +## CHECK-DAG: <> Phi [<>,<>] reg:0 +## CHECK-DAG: <> NullCheck [<>] +## CHECK-DAG: ArraySet [<>,{{i\d+}},<>] + +## CHECK-DAG: <> ParameterValue klass:float[] +## CHECK-DAG: <> FloatConstant 0 +## CHECK-DAG: <> FloatConstant 2 +## CHECK-DAG: <> Phi [<>,<>] reg:0 +## CHECK-DAG: <> NullCheck [<>] +## CHECK-DAG: ArraySet [<>,{{i\d+}},<>] + +.method public static ambiguousSet([I[FZ)V + .registers 8 + + const v0, 0x0 + if-eqz p2, :else + const v0, 0x40000000 + :else + # v0 = Phi [0.0f, 2.0f] + + const v1, 0x1 + aput v0, p0, v1 + aput v0, p1, v1 + + return-void +.end method -- 2.11.0