diff options
| -rw-r--r-- | compiler/optimizing/graph_visualizer.cc | 14 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.h | 32 | ||||
| -rw-r--r-- | compiler/optimizing/optimizing_compiler.cc | 3 | ||||
| -rw-r--r-- | compiler/optimizing/reference_type_propagation.cc | 174 | ||||
| -rw-r--r-- | compiler/optimizing/reference_type_propagation.h | 6 | ||||
| -rw-r--r-- | test/450-checker-types/src/Main.java | 89 |
6 files changed, 268 insertions, 50 deletions
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc index afea40316c..46d821ef77 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -396,6 +396,11 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { return strcmp(pass_name_, name) == 0; } + bool IsReferenceTypePropagationPass() { + return strstr(pass_name_, ReferenceTypePropagation::kReferenceTypePropagationPassName) + != nullptr; + } + void PrintInstruction(HInstruction* instruction) { output_ << instruction->DebugName(); if (instruction->InputCount() > 0) { @@ -459,14 +464,13 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { } else { StartAttributeStream("loop") << "B" << info->GetHeader()->GetBlockId(); } - } else if (IsPass(ReferenceTypePropagation::kReferenceTypePropagationPassName) - && is_after_pass_) { + } else if (IsReferenceTypePropagationPass() && is_after_pass_) { if (instruction->GetType() == Primitive::kPrimNot) { if (instruction->IsLoadClass()) { ReferenceTypeInfo info = instruction->AsLoadClass()->GetLoadedClassRTI(); ScopedObjectAccess soa(Thread::Current()); if (info.GetTypeHandle().GetReference() != nullptr) { - StartAttributeStream("klass") << PrettyClass(info.GetTypeHandle().Get()); + StartAttributeStream("klass") << PrettyDescriptor(info.GetTypeHandle().Get()); } else { StartAttributeStream("klass") << "unresolved"; } @@ -476,8 +480,10 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { StartAttributeStream("klass") << "java.lang.Object"; } else { ScopedObjectAccess soa(Thread::Current()); - StartAttributeStream("klass") << PrettyClass(info.GetTypeHandle().Get()); + StartAttributeStream("klass") << PrettyDescriptor(info.GetTypeHandle().Get()); } + StartAttributeStream("can_be_null") + << std::boolalpha << instruction->CanBeNull() << std::noboolalpha; StartAttributeStream("exact") << std::boolalpha << info.IsExact() << std::noboolalpha; } } diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 7f446d4cf6..5c5cecc3d5 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -1596,6 +1596,7 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> { // Does not apply for all instructions, but having this at top level greatly // simplifies the null check elimination. + // TODO: Consider merging can_be_null into ReferenceTypeInfo. virtual bool CanBeNull() const { DCHECK_EQ(GetType(), Primitive::kPrimNot) << "CanBeNull only applies to reference types"; return true; @@ -4201,27 +4202,40 @@ class HInstanceOf : public HExpression<2> { class HBoundType : public HExpression<1> { public: - HBoundType(HInstruction* input, ReferenceTypeInfo bound_type) + HBoundType(HInstruction* input, ReferenceTypeInfo upper_bound, bool upper_can_be_null) : HExpression(Primitive::kPrimNot, SideEffects::None()), - bound_type_(bound_type) { + upper_bound_(upper_bound), + upper_can_be_null_(upper_can_be_null), + can_be_null_(upper_can_be_null) { DCHECK_EQ(input->GetType(), Primitive::kPrimNot); SetRawInputAt(0, input); } - const ReferenceTypeInfo& GetBoundType() const { return bound_type_; } + // GetUpper* should only be used in reference type propagation. + const ReferenceTypeInfo& GetUpperBound() const { return upper_bound_; } + bool GetUpperCanBeNull() const { return upper_can_be_null_; } - bool CanBeNull() const OVERRIDE { - // `null instanceof ClassX` always return false so we can't be null. - return false; + void SetCanBeNull(bool can_be_null) { + DCHECK(upper_can_be_null_ || !can_be_null); + can_be_null_ = can_be_null; } + bool CanBeNull() const OVERRIDE { return can_be_null_; } + DECLARE_INSTRUCTION(BoundType); private: // Encodes the most upper class that this instruction can have. In other words - // it is always the case that GetBoundType().IsSupertypeOf(GetReferenceType()). - // It is used to bound the type in cases like `if (x instanceof ClassX) {}` - const ReferenceTypeInfo bound_type_; + // it is always the case that GetUpperBound().IsSupertypeOf(GetReferenceType()). + // It is used to bound the type in cases like: + // if (x instanceof ClassX) { + // // uper_bound_ will be ClassX + // } + const 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 can_be_null_; DISALLOW_COPY_AND_ASSIGN(HBoundType); }; diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 1c0123e188..3f5e8e054f 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -399,7 +399,8 @@ static void RunOptimizations(HGraph* graph, InstructionSimplifier* simplify3 = new (arena) InstructionSimplifier( graph, stats, "instruction_simplifier_after_bce"); ReferenceTypePropagation* type_propagation2 = - new (arena) ReferenceTypePropagation(graph, handles); + new (arena) ReferenceTypePropagation( + graph, handles, "reference_type_propagation_after_inlining"); InstructionSimplifier* simplify4 = new (arena) InstructionSimplifier( graph, stats, "instruction_simplifier_before_codegen"); diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc index 68316c2618..9d0d412f28 100644 --- a/compiler/optimizing/reference_type_propagation.cc +++ b/compiler/optimizing/reference_type_propagation.cc @@ -38,6 +38,7 @@ class RTPVisitor : public HGraphDelegateVisitor { void VisitStaticFieldGet(HStaticFieldGet* instr) OVERRIDE; void VisitInvoke(HInvoke* instr) OVERRIDE; void VisitArrayGet(HArrayGet* instr) OVERRIDE; + void VisitCheckCast(HCheckCast* instr) OVERRIDE; void UpdateReferenceTypeInfo(HInstruction* instr, uint16_t type_idx, const DexFile& dex_file, @@ -78,6 +79,72 @@ 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(); + HBoundType* bound_type = new (arena) HBoundType(obj, class_rti, upper_can_be_null); + // Narrow the type as much as possible. + if (load_class->IsResolved() && class_rti.GetTypeHandle()->IsFinal()) { + bound_type->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ true)); + } else if (!load_class->IsResolved() || class_rti.IsSupertypeOf(obj_rti)) { + bound_type->SetReferenceTypeInfo(obj_rti); + } else { + bound_type->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false)); + } + 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. +// In this case we also assert that there are no other uses of the object (except +// the bound type) dominated by the specified dominator_instr or dominator_block. +static bool ShouldCreateBoundType(HInstruction* position, + HInstruction* obj, + ReferenceTypeInfo upper_bound, + HInstruction* dominator_instr, + HBasicBlock* dominator_block) + SHARED_REQUIRES(Locks::mutator_lock_) { + // If the position where we should insert the bound type is not already a + // a bound type then we need to create one. + if (position == nullptr || !position->IsBoundType()) { + return true; + } + + HBoundType* existing_bound_type = position->AsBoundType(); + if (existing_bound_type->GetUpperBound().IsSupertypeOf(upper_bound)) { + if (kIsDebugBuild) { + // Check that the existing HBoundType dominates all the uses. + for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) { + HInstruction* user = it.Current()->GetUser(); + if (dominator_instr != nullptr) { + DCHECK(!dominator_instr->StrictlyDominates(user) + || user == existing_bound_type + || existing_bound_type->StrictlyDominates(user)); + } else if (dominator_block != nullptr) { + DCHECK(!dominator_block->Dominates(user->GetBlock()) + || user == existing_bound_type + || existing_bound_type->StrictlyDominates(user)); + } + } + } + } else { + // TODO: if the current bound type is a refinement we could update the + // existing_bound_type with the a new upper limit. However, we also need to + // update its users and have access to the work list. + } + return false; +} + void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) { HIf* ifInstruction = block->GetLastInstruction()->AsIf(); if (ifInstruction == nullptr) { @@ -116,8 +183,19 @@ void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) { HInstruction* user = it.Current()->GetUser(); if (notNullBlock->Dominates(user->GetBlock())) { if (bound_type == nullptr) { - bound_type = new (graph_->GetArena()) HBoundType(obj, ReferenceTypeInfo::CreateTop(false)); - notNullBlock->InsertInstructionBefore(bound_type, notNullBlock->GetFirstInstruction()); + ScopedObjectAccess soa(Thread::Current()); + HInstruction* insert_point = notNullBlock->GetFirstInstruction(); + ReferenceTypeInfo object_rti = ReferenceTypeInfo::CreateTop(false); + if (ShouldCreateBoundType(insert_point, obj, object_rti, nullptr, notNullBlock)) { + bound_type = new (graph_->GetArena()) HBoundType( + obj, object_rti, /* bound_can_be_null */ false); + notNullBlock->InsertInstructionBefore(bound_type, insert_point); + } else { + // 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()); } @@ -171,25 +249,23 @@ void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) { HInstruction* user = it.Current()->GetUser(); if (instanceOfTrueBlock->Dominates(user->GetBlock())) { if (bound_type == nullptr) { + ScopedObjectAccess soa(Thread::Current()); HLoadClass* load_class = instanceOf->InputAt(1)->AsLoadClass(); - - ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo(); ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); - bound_type = new (graph_->GetArena()) HBoundType(obj, class_rti); - - // Narrow the type as much as possible. - { - ScopedObjectAccess soa(Thread::Current()); - if (!load_class->IsResolved() || class_rti.IsSupertypeOf(obj_rti)) { - bound_type->SetReferenceTypeInfo(obj_rti); - } else { - bound_type->SetReferenceTypeInfo( - ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false)); - } + 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. */); + instanceOfTrueBlock->InsertInstructionBefore(bound_type, insert_point); + } else { + // 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; } - - instanceOfTrueBlock->InsertInstructionBefore( - bound_type, instanceOfTrueBlock->GetFirstInstruction()); } user->ReplaceInput(bound_type, it.Current()->GetIndex()); } @@ -266,6 +342,35 @@ void RTPVisitor::VisitLoadClass(HLoadClass* instr) { instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(class_handle, /* is_exact */ true)); } +void RTPVisitor::VisitCheckCast(HCheckCast* check_cast) { + HInstruction* obj = check_cast->InputAt(0); + HBoundType* bound_type = nullptr; + for (HUseIterator<HInstruction*> 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()); + HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass(); + ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); + 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 { + // 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()); + } + } +} + void ReferenceTypePropagation::VisitPhi(HPhi* phi) { if (phi->GetType() != Primitive::kPrimNot) { return; @@ -362,9 +467,9 @@ void RTPVisitor::VisitArrayGet(HArrayGet* instr) { void ReferenceTypePropagation::UpdateBoundType(HBoundType* instr) { ReferenceTypeInfo new_rti = instr->InputAt(0)->GetReferenceTypeInfo(); // Be sure that we don't go over the bounded type. - ReferenceTypeInfo bound_rti = instr->GetBoundType(); - if (!bound_rti.IsSupertypeOf(new_rti)) { - new_rti = bound_rti; + ReferenceTypeInfo upper_bound_rti = instr->GetUpperBound(); + if (!upper_bound_rti.IsSupertypeOf(new_rti)) { + new_rti = upper_bound_rti; } instr->SetReferenceTypeInfo(new_rti); } @@ -394,19 +499,22 @@ void ReferenceTypePropagation::UpdatePhi(HPhi* instr) { bool ReferenceTypePropagation::UpdateNullability(HInstruction* instr) { DCHECK(instr->IsPhi() || instr->IsBoundType()); - if (!instr->IsPhi()) { - return false; - } - - HPhi* phi = instr->AsPhi(); - bool existing_can_be_null = phi->CanBeNull(); - bool new_can_be_null = false; - for (size_t i = 0; i < phi->InputCount(); i++) { - new_can_be_null |= phi->InputAt(i)->CanBeNull(); + bool existing_can_be_null = instr->CanBeNull(); + if (instr->IsPhi()) { + HPhi* phi = instr->AsPhi(); + bool new_can_be_null = false; + for (size_t i = 0; i < phi->InputCount(); i++) { + if (phi->InputAt(i)->CanBeNull()) { + new_can_be_null = true; + break; + } + } + phi->SetCanBeNull(new_can_be_null); + } else if (instr->IsBoundType()) { + HBoundType* bound_type = instr->AsBoundType(); + bound_type->SetCanBeNull(instr->InputAt(0)->CanBeNull() && bound_type->GetUpperCanBeNull()); } - phi->SetCanBeNull(new_can_be_null); - - return existing_can_be_null != new_can_be_null; + return existing_can_be_null != instr->CanBeNull(); } void ReferenceTypePropagation::ProcessWorklist() { diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h index 11f5ac91ca..32f5e09a6c 100644 --- a/compiler/optimizing/reference_type_propagation.h +++ b/compiler/optimizing/reference_type_propagation.h @@ -30,8 +30,10 @@ namespace art { */ class ReferenceTypePropagation : public HOptimization { public: - ReferenceTypePropagation(HGraph* graph, StackHandleScopeCollection* handles) - : HOptimization(graph, kReferenceTypePropagationPassName), + ReferenceTypePropagation(HGraph* graph, + StackHandleScopeCollection* handles, + const char* name = kReferenceTypePropagationPassName) + : HOptimization(graph, name), handles_(handles), worklist_(graph->GetArena(), kDefaultWorklistSize) {} diff --git a/test/450-checker-types/src/Main.java b/test/450-checker-types/src/Main.java index 014f59a506..6e1dfabe29 100644 --- a/test/450-checker-types/src/Main.java +++ b/test/450-checker-types/src/Main.java @@ -14,7 +14,6 @@ * limitations under the License. */ - interface Interface { void $noinline$f(); } @@ -52,6 +51,15 @@ class SubclassB extends Super { } } +class Generic<A> { + private A a = null; + public A get() { + return a; + } +} + +final class Final {} + public class Main { /// CHECK-START: void Main.testSimpleRemove() instruction_simplifier_after_types (before) @@ -395,6 +403,85 @@ public class Main { ((SubclassA)a[0]).$noinline$g(); } + private Generic<SubclassC> genericC = new Generic<SubclassC>(); + private Generic<Final> genericFinal = new Generic<Final>(); + + private SubclassC get() { + return genericC.get(); + } + + private Final getFinal() { + return genericFinal.get(); + } + + /// CHECK-START: SubclassC Main.inlineGenerics() reference_type_propagation (after) + /// CHECK: <<Invoke:l\d+>> InvokeStaticOrDirect klass:SubclassC + /// CHECK-NEXT: Return [<<Invoke>>] + + /// CHECK-START: SubclassC Main.inlineGenerics() reference_type_propagation_after_inlining (after) + /// CHECK: <<BoundType:l\d+>> BoundType klass:SubclassC + /// CHECK: Return [<<BoundType>>] + private SubclassC inlineGenerics() { + SubclassC c = get(); + return c; + } + + /// CHECK-START: Final Main.inlineGenericsFinal() reference_type_propagation (after) + /// CHECK: <<Invoke:l\d+>> InvokeStaticOrDirect klass:Final exact:true + /// CHECK-NEXT: Return [<<Invoke>>] + + /// CHECK-START: Final Main.inlineGenericsFinal() reference_type_propagation_after_inlining (after) + /// CHECK: <<BoundType:l\d+>> BoundType klass:Final exact:true + /// CHECK: Return [<<BoundType>>] + private Final inlineGenericsFinal() { + Final f = getFinal(); + return f; + } + + /// CHECK-START: void Main.boundOnlyOnceIfNotNull(java.lang.Object) reference_type_propagation_after_inlining (after) + /// CHECK: BoundType + /// CHECK-NOT: BoundType + private void boundOnlyOnceIfNotNull(Object o) { + if (o != null) { + o.toString(); + } + } + + /// CHECK-START: void Main.boundOnlyOnceIfInstanceOf(java.lang.Object) reference_type_propagation_after_inlining (after) + /// CHECK: BoundType + /// CHECK-NOT: BoundType + private void boundOnlyOnceIfInstanceOf(Object o) { + if (o instanceof Main) { + o.toString(); + } + } + + /// CHECK-START: Final Main.boundOnlyOnceCheckCast(Generic) reference_type_propagation_after_inlining (after) + /// CHECK: BoundType + /// CHECK-NOT: BoundType + private Final boundOnlyOnceCheckCast(Generic<Final> o) { + Final f = o.get(); + return f; + } + + /// CHECK-START: java.lang.String Main.checkcastPreserveNullCheck(java.lang.Object) reference_type_propagation_after_inlining (after) + /// CHECK: <<This:l\d+>> ParameterValue + /// CHECK: <<Param:l\d+>> ParameterValue + /// CHECK: <<Clazz:l\d+>> LoadClass + /// CHECK: CheckCast [<<Param>>,<<Clazz>>] + /// CHECK: BoundType [<<Param>>] can_be_null:true + + /// CHECK-START: java.lang.String Main.checkcastPreserveNullCheck(java.lang.Object) instruction_simplifier_after_types (after) + /// CHECK: <<This:l\d+>> ParameterValue + /// CHECK: <<Param:l\d+>> ParameterValue + /// CHECK: <<Clazz:l\d+>> LoadClass + /// CHECK: CheckCast [<<Param>>,<<Clazz>>] + /// CHECK: <<Bound:l\d+>> BoundType [<<Param>>] + /// CHECK: NullCheck [<<Bound>>] + public String checkcastPreserveNullCheck(Object a) { + return ((SubclassA)a).toString(); + } + public static void main(String[] args) { } } |