From f555258861aea7df8af9c2241ab761227fd2f66a Mon Sep 17 00:00:00 2001 From: David Brazdil Date: Sun, 27 Dec 2015 13:36:12 +0000 Subject: [PATCH] ART: Create BoundType for CheckCast early ReferenceTypePropagation creates a BoundType for each CheckCast and replaces all dominated uses of the casted object with it. This does not include Phi uses on the boundary of the dominated scope, reducing typing precision. This patch creates the BoundType in Builder, causing SsaBuilder to replace uses of the object automatically. Bug: 26081304 Change-Id: I083979155cccb348071ff58cb9060a896ed7d2ac --- compiler/optimizing/builder.cc | 5 + compiler/optimizing/graph_checker.cc | 12 +++ compiler/optimizing/graph_checker.h | 1 + compiler/optimizing/nodes.cc | 27 ++++- compiler/optimizing/nodes.h | 23 ++--- compiler/optimizing/reference_type_propagation.cc | 117 +++++++++------------- test/554-checker-rtp-checkcast/expected.txt | 0 test/554-checker-rtp-checkcast/info.txt | 1 + test/554-checker-rtp-checkcast/src/Main.java | 73 ++++++++++++++ 9 files changed, 172 insertions(+), 87 deletions(-) create mode 100644 test/554-checker-rtp-checkcast/expected.txt create mode 100644 test/554-checker-rtp-checkcast/info.txt create mode 100644 test/554-checker-rtp-checkcast/src/Main.java diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc index 4dd0d26b8..1af684683 100644 --- a/compiler/optimizing/builder.cc +++ b/compiler/optimizing/builder.cc @@ -1817,7 +1817,12 @@ void HGraphBuilder::BuildTypeCheck(const Instruction& instruction, UpdateLocal(destination, current_block_->GetLastInstruction(), dex_pc); } else { DCHECK_EQ(instruction.Opcode(), Instruction::CHECK_CAST); + // We emit a CheckCast followed by a BoundType. CheckCast is a statement + // which may throw. If it succeeds BoundType sets the new type of `object` + // for all subsequent uses. current_block_->AddInstruction(new (arena_) HCheckCast(object, cls, check_kind, dex_pc)); + current_block_->AddInstruction(new (arena_) HBoundType(object, dex_pc)); + UpdateLocal(reference, current_block_->GetLastInstruction(), dex_pc); } } diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc index 3b93b2b57..6d0bdbe19 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -921,4 +921,16 @@ void SSAChecker::VisitConstant(HConstant* instruction) { } } +void SSAChecker::VisitBoundType(HBoundType* instruction) { + VisitInstruction(instruction); + + ScopedObjectAccess soa(Thread::Current()); + if (!instruction->GetUpperBound().IsValid()) { + AddError(StringPrintf( + "%s %d does not have a valid upper bound RTI.", + instruction->DebugName(), + instruction->GetId())); + } +} + } // namespace art diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h index d5ddbabc8..2e16bfe24 100644 --- a/compiler/optimizing/graph_checker.h +++ b/compiler/optimizing/graph_checker.h @@ -128,6 +128,7 @@ class SSAChecker : public GraphChecker { void VisitPackedSwitch(HPackedSwitch* instruction) OVERRIDE; void VisitBooleanNot(HBooleanNot* instruction) OVERRIDE; void VisitConstant(HConstant* instruction) OVERRIDE; + void VisitBoundType(HBoundType* instruction) OVERRIDE; void HandleBooleanInput(HInstruction* instruction, size_t input_index); diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index fc1222478..c85e57355 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -2060,6 +2060,16 @@ void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) { new_pre_header->SetTryCatchInformation(try_catch_info); } +static void CheckAgainstUpperBound(ReferenceTypeInfo rti, ReferenceTypeInfo upper_bound_rti) + SHARED_REQUIRES(Locks::mutator_lock_) { + if (rti.IsValid()) { + DCHECK(upper_bound_rti.IsSupertypeOf(rti)) + << " upper_bound_rti: " << upper_bound_rti + << " rti: " << rti; + DCHECK(!upper_bound_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes() || rti.IsExact()); + } +} + void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) { if (kIsDebugBuild) { DCHECK_EQ(GetType(), Primitive::kPrimNot); @@ -2068,16 +2078,23 @@ void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) { if (IsBoundType()) { // Having the test here spares us from making the method virtual just for // the sake of a DCHECK. - ReferenceTypeInfo upper_bound_rti = AsBoundType()->GetUpperBound(); - DCHECK(upper_bound_rti.IsSupertypeOf(rti)) - << " upper_bound_rti: " << upper_bound_rti - << " rti: " << rti; - DCHECK(!upper_bound_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes() || rti.IsExact()); + CheckAgainstUpperBound(rti, AsBoundType()->GetUpperBound()); } } reference_type_info_ = rti; } +void HBoundType::SetUpperBound(const ReferenceTypeInfo& upper_bound, bool can_be_null) { + if (kIsDebugBuild) { + ScopedObjectAccess soa(Thread::Current()); + DCHECK(upper_bound.IsValid()); + DCHECK(!upper_bound_.IsValid()) << "Upper bound should only be set once."; + CheckAgainstUpperBound(GetReferenceTypeInfo(), upper_bound); + } + upper_bound_ = upper_bound; + upper_can_be_null_ = can_be_null; +} + ReferenceTypeInfo::ReferenceTypeInfo() : type_handle_(TypeHandle()), is_exact_(false) {} ReferenceTypeInfo::ReferenceTypeInfo(TypeHandle type_handle, bool is_exact) diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 5b072cf71..dc54bdae2 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -240,7 +240,7 @@ class ReferenceTypeInfo : ValueObject { // Returns true if the type information provide the same amount of details. // Note that it does not mean that the instructions have the same actual type // (because the type can be the result of a merge). - bool IsEqual(ReferenceTypeInfo rti) SHARED_REQUIRES(Locks::mutator_lock_) { + bool IsEqual(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { if (!IsValid() && !rti.IsValid()) { // Invalid types are equal. return true; @@ -5431,24 +5431,19 @@ class HInstanceOf : public HExpression<2> { class HBoundType : public HExpression<1> { public: - // Constructs an HBoundType with the given upper_bound. - // Ensures that the upper_bound is valid. - HBoundType(HInstruction* input, - ReferenceTypeInfo upper_bound, - bool upper_can_be_null, - uint32_t dex_pc = kNoDexPc) + HBoundType(HInstruction* input, uint32_t dex_pc = kNoDexPc) : HExpression(Primitive::kPrimNot, SideEffects::None(), dex_pc), - upper_bound_(upper_bound), - upper_can_be_null_(upper_can_be_null), - can_be_null_(upper_can_be_null) { + upper_bound_(ReferenceTypeInfo::CreateInvalid()), + upper_can_be_null_(true), + can_be_null_(true) { DCHECK_EQ(input->GetType(), Primitive::kPrimNot); SetRawInputAt(0, input); - SetReferenceTypeInfo(upper_bound_); } - // GetUpper* should only be used in reference type propagation. + // {Get,Set}Upper* should only be used in reference type propagation. const ReferenceTypeInfo& GetUpperBound() const { return upper_bound_; } bool GetUpperCanBeNull() const { return upper_can_be_null_; } + void SetUpperBound(const ReferenceTypeInfo& upper_bound, bool can_be_null); void SetCanBeNull(bool can_be_null) { DCHECK(upper_can_be_null_ || !can_be_null); @@ -5466,10 +5461,10 @@ class HBoundType : public HExpression<1> { // if (x instanceof ClassX) { // // uper_bound_ will be ClassX // } - const ReferenceTypeInfo upper_bound_; + ReferenceTypeInfo upper_bound_; // Represents the top constraint that can_be_null_ cannot exceed (i.e. if this // is false then can_be_null_ cannot be true). - const bool upper_can_be_null_; + bool upper_can_be_null_; bool can_be_null_; DISALLOW_COPY_AND_ASSIGN(HBoundType); diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc index 8113e6512..e55061c92 100644 --- a/compiler/optimizing/reference_type_propagation.cc +++ b/compiler/optimizing/reference_type_propagation.cc @@ -56,6 +56,7 @@ class RTPVisitor : public HGraphDelegateVisitor { void VisitInvoke(HInvoke* instr) OVERRIDE; void VisitArrayGet(HArrayGet* instr) OVERRIDE; void VisitCheckCast(HCheckCast* instr) OVERRIDE; + void VisitBoundType(HBoundType* instr) OVERRIDE; void VisitNullCheck(HNullCheck* instr) OVERRIDE; void VisitFakeString(HFakeString* instr) OVERRIDE; void UpdateReferenceTypeInfo(HInstruction* instr, @@ -160,34 +161,6 @@ void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) { BoundTypeForIfInstanceOf(block); } -// Create a bound type for the given object narrowing the type as much as possible. -// The BoundType upper values for the super type and can_be_null will be taken from -// load_class.GetLoadedClassRTI() and upper_can_be_null. -static HBoundType* CreateBoundType(ArenaAllocator* arena, - HInstruction* obj, - HLoadClass* load_class, - bool upper_can_be_null) - SHARED_REQUIRES(Locks::mutator_lock_) { - ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo(); - ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); - DCHECK(class_rti.IsValid()); - HBoundType* bound_type = new (arena) HBoundType(obj, class_rti, upper_can_be_null); - // Narrow the type as much as possible. - if (class_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes()) { - bound_type->SetReferenceTypeInfo( - ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ true)); - } else if (obj_rti.IsValid() && class_rti.IsSupertypeOf(obj_rti)) { - bound_type->SetReferenceTypeInfo(obj_rti); - } else { - bound_type->SetReferenceTypeInfo( - ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false)); - } - if (upper_can_be_null) { - bound_type->SetCanBeNull(obj->CanBeNull()); - } - return bound_type; -} - // Check if we should create a bound type for the given object at the specified // position. Because of inlining and the fact we run RTP more than once and we // might have a HBoundType already. If we do, we should not create a new one. @@ -273,8 +246,8 @@ void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) { ReferenceTypeInfo object_rti = ReferenceTypeInfo::Create( object_class_handle_, /* is_exact */ true); if (ShouldCreateBoundType(insert_point, obj, object_rti, nullptr, notNullBlock)) { - bound_type = new (graph_->GetArena()) HBoundType( - obj, object_rti, /* bound_can_be_null */ false); + bound_type = new (graph_->GetArena()) HBoundType(obj); + bound_type->SetUpperBound(object_rti, /* bound_can_be_null */ false); if (obj->GetReferenceTypeInfo().IsValid()) { bound_type->SetReferenceTypeInfo(obj->GetReferenceTypeInfo()); } @@ -408,11 +381,8 @@ void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) { ScopedObjectAccess soa(Thread::Current()); HInstruction* insert_point = instanceOfTrueBlock->GetFirstInstruction(); if (ShouldCreateBoundType(insert_point, obj, class_rti, nullptr, instanceOfTrueBlock)) { - bound_type = CreateBoundType( - graph_->GetArena(), - obj, - load_class, - false /* InstanceOf ensures the object is not null. */); + bound_type = new (graph_->GetArena()) HBoundType(obj); + bound_type->SetUpperBound(class_rti, /* InstanceOf fails for null. */ false); instanceOfTrueBlock->InsertInstructionBefore(bound_type, insert_point); } else { // We already have a bound type on the position we would need to insert @@ -602,43 +572,54 @@ void RTPVisitor::VisitFakeString(HFakeString* instr) { instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(string_class_handle_, /* is_exact */ true)); } +void RTPVisitor::VisitBoundType(HBoundType* instr) { + ScopedObjectAccess soa(Thread::Current()); + + ReferenceTypeInfo class_rti = instr->GetUpperBound(); + if (class_rti.IsValid()) { + // Narrow the type as much as possible. + HInstruction* obj = instr->InputAt(0); + ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo(); + if (class_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes()) { + instr->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ true)); + } else if (obj_rti.IsValid() && class_rti.IsSupertypeOf(obj_rti)) { + instr->SetReferenceTypeInfo(obj_rti); + } else { + instr->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false)); + } + instr->SetCanBeNull(obj->CanBeNull() && instr->GetUpperCanBeNull()); + } else { + // The owner of the BoundType was already visited. If the class is unresolved, + // the BoundType should have been removed from the data flow and this method + // should remove it from the graph. + DCHECK(!instr->HasUses()); + instr->GetBlock()->RemoveInstruction(instr); + } +} + void RTPVisitor::VisitCheckCast(HCheckCast* check_cast) { + ScopedObjectAccess soa(Thread::Current()); + HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass(); ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); - { - ScopedObjectAccess soa(Thread::Current()); - if (!class_rti.IsValid()) { - // He have loaded an unresolved class. Don't bother bounding the type. - return; - } + HBoundType* bound_type = check_cast->GetNext()->AsBoundType(); + if (bound_type == nullptr || bound_type->GetUpperBound().IsValid()) { + // The next instruction is not an uninitialized BoundType. This must be + // an RTP pass after SsaBuilder and we do not need to do anything. + return; } - HInstruction* obj = check_cast->InputAt(0); - HBoundType* bound_type = nullptr; - for (HUseIterator it(obj->GetUses()); !it.Done(); it.Advance()) { - HInstruction* user = it.Current()->GetUser(); - if (check_cast->StrictlyDominates(user)) { - if (bound_type == nullptr) { - ScopedObjectAccess soa(Thread::Current()); - if (ShouldCreateBoundType(check_cast->GetNext(), obj, class_rti, check_cast, nullptr)) { - bound_type = CreateBoundType( - GetGraph()->GetArena(), - obj, - load_class, - true /* CheckCast succeeds for nulls. */); - check_cast->GetBlock()->InsertInstructionAfter(bound_type, check_cast); - } else { - // Update nullability of the existing bound type, which may not have known - // that its input was not null when it was being created. - bound_type = check_cast->GetNext()->AsBoundType(); - bound_type->SetCanBeNull(obj->CanBeNull()); - // We already have a bound type on the position we would need to insert - // the new one. The existing bound type should dominate all the users - // (dchecked) so there's no need to continue. - break; - } - } - user->ReplaceInput(bound_type, it.Current()->GetIndex()); - } + DCHECK_EQ(bound_type->InputAt(0), check_cast->InputAt(0)); + + if (class_rti.IsValid()) { + // This is the first run of RTP and class is resolved. + bound_type->SetUpperBound(class_rti, /* CheckCast succeeds for nulls. */ true); + } else { + // This is the first run of RTP and class is unresolved. Remove the binding. + // The instruction itself is removed in VisitBoundType so as to not + // invalidate HInstructionIterator. + bound_type->ReplaceWith(bound_type->InputAt(0)); } } diff --git a/test/554-checker-rtp-checkcast/expected.txt b/test/554-checker-rtp-checkcast/expected.txt new file mode 100644 index 000000000..e69de29bb diff --git a/test/554-checker-rtp-checkcast/info.txt b/test/554-checker-rtp-checkcast/info.txt new file mode 100644 index 000000000..2a6097108 --- /dev/null +++ b/test/554-checker-rtp-checkcast/info.txt @@ -0,0 +1 @@ +Tests that phis with check-casted reference type inputs are typed. diff --git a/test/554-checker-rtp-checkcast/src/Main.java b/test/554-checker-rtp-checkcast/src/Main.java new file mode 100644 index 000000000..607f71afb --- /dev/null +++ b/test/554-checker-rtp-checkcast/src/Main.java @@ -0,0 +1,73 @@ +/* + * 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. + */ + + +public class Main { + + public static Object returnIntArray() { return new int[10]; } + + /// CHECK-START: void Main.boundTypeForMergingPhi() ssa_builder (after) + /// CHECK-DAG: ArraySet [<>,{{i\d+}},{{i\d+}}] + /// CHECK-DAG: <> NullCheck [<>] + /// CHECK-DAG: <> Phi klass:int[] + + public static void boundTypeForMergingPhi() { + int[] array = new int[20]; + if (array.hashCode() > 5) { + array = (int[]) returnIntArray(); + } + array[0] = 14; + } + + /// CHECK-START: void Main.boundTypeForLoopPhi() ssa_builder (after) + /// CHECK-DAG: ArraySet [<>,{{i\d+}},{{i\d+}}] + /// CHECK-DAG: <> NullCheck [<>] + /// CHECK-DAG: <> Phi klass:int[] + + public static void boundTypeForLoopPhi() { + int[] array = new int[20]; + int i = 0; + while (i < 4) { + ++i; + array[i] = i; + if (i > 2) { + array = (int[]) returnIntArray(); + } + } + array[0] = 14; + } + + /// CHECK-START: void Main.boundTypeForCatchPhi() ssa_builder (after) + /// CHECK-DAG: ArraySet [<>,{{i\d+}},{{i\d+}}] + /// CHECK-DAG: <> NullCheck [<>] + /// CHECK-DAG: <> Phi is_catch_phi:true klass:int[] + + public static void boundTypeForCatchPhi() { + int[] array1 = new int[20]; + int[] array2 = (int[]) returnIntArray(); + + int[] catch_phi = array1; + try { + System.nanoTime(); + catch_phi = array2; + System.nanoTime(); + } catch (Throwable ex) { + catch_phi[0] = 14; + } + } + + public static void main(String[] args) { } +} -- 2.11.0