From 1d5006c34d75758752bf3499892e3d5beb11d5dc Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Wed, 3 Jun 2015 15:04:32 +0100 Subject: [PATCH] Support for inlining virtual and interface calls. Also had to change the pass order to get reference type propagation before the inliner. Change-Id: I4bf3bbb2d17c7d9cab632cfdd96adad8368bdfea --- compiler/optimizing/inliner.cc | 108 +++++++++++++++++++-- compiler/optimizing/inliner.h | 5 +- compiler/optimizing/optimizing_compiler.cc | 12 ++- compiler/optimizing/reference_type_propagation.cc | 17 ++-- compiler/optimizing/reference_type_propagation.h | 7 +- test/444-checker-nce/src/Main.java | 16 +-- .../src/Main.java | 6 +- test/490-checker-inline/expected.txt | 0 test/490-checker-inline/info.txt | 1 + test/490-checker-inline/src/Main.java | 52 ++++++++++ 10 files changed, 192 insertions(+), 32 deletions(-) create mode 100644 test/490-checker-inline/expected.txt create mode 100644 test/490-checker-inline/info.txt create mode 100644 test/490-checker-inline/src/Main.java diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc index 83f8d83bc..b26afd1ca 100644 --- a/compiler/optimizing/inliner.cc +++ b/compiler/optimizing/inliner.cc @@ -27,6 +27,7 @@ #include "mirror/class_loader.h" #include "mirror/dex_cache.h" #include "nodes.h" +#include "reference_type_propagation.h" #include "register_allocator.h" #include "ssa_phi_elimination.h" #include "scoped_thread_state_change.h" @@ -57,7 +58,7 @@ void HInliner::Run() { next_block = (i == blocks.Size() - 1) ? nullptr : blocks.Get(i + 1); for (HInstruction* instruction = block->GetFirstInstruction(); instruction != nullptr;) { HInstruction* next = instruction->GetNext(); - HInvokeStaticOrDirect* call = instruction->AsInvokeStaticOrDirect(); + HInvoke* call = instruction->AsInvoke(); // As long as the call is not intrinsified, it is worth trying to inline. if (call != nullptr && call->GetIntrinsic() == Intrinsics::kNone) { // We use the original invoke type to ensure the resolution of the called method @@ -76,6 +77,79 @@ void HInliner::Run() { } } +static bool IsMethodOrDeclaringClassFinal(ArtMethod* method) + SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { + return method->IsFinal() || method->GetDeclaringClass()->IsFinal(); +} + +/** + * Given the `resolved_method` looked up in the dex cache, try to find + * the actual runtime target of an interface or virtual call. + * Return nullptr if the runtime target cannot be proven. + */ +static ArtMethod* FindVirtualOrInterfaceTarget(HInvoke* invoke, ArtMethod* resolved_method) + SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { + if (IsMethodOrDeclaringClassFinal(resolved_method)) { + // No need to lookup further, the resolved method will be the target. + return resolved_method; + } + + HInstruction* receiver = invoke->InputAt(0); + if (receiver->IsNullCheck()) { + // Due to multiple levels of inlining within the same pass, it might be that + // null check does not have the reference type of the actual receiver. + receiver = receiver->InputAt(0); + } + ReferenceTypeInfo info = receiver->GetReferenceTypeInfo(); + if (info.IsTop()) { + // We have no information on the receiver. + return nullptr; + } else if (!info.IsExact()) { + // We currently only support inlining with known receivers. + // TODO: Remove this check, we should be able to inline final methods + // on unknown receivers. + return nullptr; + } else if (info.GetTypeHandle()->IsInterface()) { + // Statically knowing that the receiver has an interface type cannot + // help us find what is the target method. + return nullptr; + } + + ClassLinker* cl = Runtime::Current()->GetClassLinker(); + size_t pointer_size = cl->GetImagePointerSize(); + if (invoke->IsInvokeInterface()) { + resolved_method = info.GetTypeHandle()->FindVirtualMethodForInterface( + resolved_method, pointer_size); + } else { + DCHECK(invoke->IsInvokeVirtual()); + resolved_method = info.GetTypeHandle()->FindVirtualMethodForVirtual( + resolved_method, pointer_size); + } + + if (resolved_method == nullptr) { + // The information we had on the receiver was not enough to find + // the target method. Since we check above the exact type of the receiver, + // the only reason this can happen is an IncompatibleClassChangeError. + return nullptr; + } else if (resolved_method->IsAbstract()) { + // The information we had on the receiver was not enough to find + // the target method. Since we check above the exact type of the receiver, + // the only reason this can happen is an IncompatibleClassChangeError. + return nullptr; + } else if (IsMethodOrDeclaringClassFinal(resolved_method)) { + // A final method has to be the target method. + return resolved_method; + } else if (info.IsExact()) { + // If we found a method and the receiver's concrete type is statically + // known, we know for sure the target. + return resolved_method; + } else { + // Even if we did find a method, the receiver type was not enough to + // statically find the runtime target. + return nullptr; + } +} + bool HInliner::TryInline(HInvoke* invoke_instruction, uint32_t method_index, InvokeType invoke_type) const { @@ -83,19 +157,34 @@ bool HInliner::TryInline(HInvoke* invoke_instruction, const DexFile& caller_dex_file = *caller_compilation_unit_.GetDexFile(); VLOG(compiler) << "Try inlining " << PrettyMethod(method_index, caller_dex_file); - StackHandleScope<3> hs(soa.Self()); - Handle dex_cache( - hs.NewHandle(caller_compilation_unit_.GetClassLinker()->FindDexCache(caller_dex_file))); - Handle class_loader(hs.NewHandle( - soa.Decode(caller_compilation_unit_.GetClassLoader()))); - ArtMethod* resolved_method(compiler_driver_->ResolveMethod( - soa, dex_cache, class_loader, &caller_compilation_unit_, method_index, invoke_type)); + ArtMethod* resolved_method = nullptr; + { + // Don't keep this handle scope on stack, otherwise we cannot do a reference type + // propagation while inlining. + StackHandleScope<2> hs(soa.Self()); + Handle dex_cache( + hs.NewHandle(caller_compilation_unit_.GetClassLinker()->FindDexCache(caller_dex_file))); + Handle class_loader(hs.NewHandle( + soa.Decode(caller_compilation_unit_.GetClassLoader()))); + resolved_method = compiler_driver_->ResolveMethod( + soa, dex_cache, class_loader, &caller_compilation_unit_, method_index, invoke_type); + } if (resolved_method == nullptr) { VLOG(compiler) << "Method cannot be resolved " << PrettyMethod(method_index, caller_dex_file); return false; } + if (!invoke_instruction->IsInvokeStaticOrDirect()) { + resolved_method = FindVirtualOrInterfaceTarget(invoke_instruction, resolved_method); + if (resolved_method == nullptr) { + VLOG(compiler) << "Interface or virtual call to " + << PrettyMethod(method_index, caller_dex_file) + << "could not be statically determined"; + return false; + } + } + bool same_dex_file = true; const DexFile& outer_dex_file = *outer_compilation_unit_.GetDexFile(); if (resolved_method->GetDexFile()->GetLocation().compare(outer_dex_file.GetLocation()) != 0) { @@ -238,11 +327,13 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, // Run simple optimizations on the graph. HDeadCodeElimination dce(callee_graph, stats_); HConstantFolding fold(callee_graph); + ReferenceTypePropagation type_propagation(callee_graph, handles_); InstructionSimplifier simplify(callee_graph, stats_); HOptimization* optimizations[] = { &dce, &fold, + &type_propagation, &simplify, }; @@ -256,6 +347,7 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, outer_compilation_unit_, dex_compilation_unit, compiler_driver_, + handles_, stats_, depth_ + 1); inliner.Run(); diff --git a/compiler/optimizing/inliner.h b/compiler/optimizing/inliner.h index b86c1ed50..ca713329f 100644 --- a/compiler/optimizing/inliner.h +++ b/compiler/optimizing/inliner.h @@ -34,13 +34,15 @@ class HInliner : public HOptimization { const DexCompilationUnit& outer_compilation_unit, const DexCompilationUnit& caller_compilation_unit, CompilerDriver* compiler_driver, + StackHandleScopeCollection* handles, OptimizingCompilerStats* stats, size_t depth = 0) : HOptimization(outer_graph, true, kInlinerPassName, stats), outer_compilation_unit_(outer_compilation_unit), caller_compilation_unit_(caller_compilation_unit), compiler_driver_(compiler_driver), - depth_(depth) {} + depth_(depth), + handles_(handles) {} void Run() OVERRIDE; @@ -57,6 +59,7 @@ class HInliner : public HOptimization { const DexCompilationUnit& caller_compilation_unit_; CompilerDriver* const compiler_driver_; const size_t depth_; + StackHandleScopeCollection* const handles_; DISALLOW_COPY_AND_ASSIGN(HInliner); }; diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index f6ef2f7e8..bf0b9fac0 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -326,7 +326,7 @@ static void RunOptimizations(HGraph* graph, InstructionSimplifier simplify1(graph, stats); HBooleanSimplifier boolean_simplify(graph); - HInliner inliner(graph, dex_compilation_unit, dex_compilation_unit, driver, stats); + HInliner inliner(graph, dex_compilation_unit, dex_compilation_unit, driver, handles, stats); HConstantFolding fold2(graph, "constant_folding_after_inlining"); SideEffectsAnalysis side_effects(graph); @@ -335,6 +335,8 @@ static void RunOptimizations(HGraph* graph, BoundsCheckElimination bce(graph); ReferenceTypePropagation type_propagation(graph, handles); InstructionSimplifier simplify2(graph, stats, "instruction_simplifier_after_types"); + InstructionSimplifier simplify3(graph, stats, "last_instruction_simplifier"); + ReferenceTypePropagation type_propagation2(graph, handles); IntrinsicsRecognizer intrinsics(graph, driver); @@ -343,7 +345,12 @@ static void RunOptimizations(HGraph* graph, &dce1, &fold1, &simplify1, + &type_propagation, + &simplify2, &inliner, + // Run another type propagation phase: inlining will open up more opprotunities + // to remove checkast/instanceof and null checks. + &type_propagation2, // BooleanSimplifier depends on the InstructionSimplifier removing redundant // suspend checks to recognize empty blocks. &boolean_simplify, @@ -352,8 +359,7 @@ static void RunOptimizations(HGraph* graph, &gvn, &licm, &bce, - &type_propagation, - &simplify2, + &simplify3, &dce2, }; diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc index 4f1f45769..4edadef1a 100644 --- a/compiler/optimizing/reference_type_propagation.cc +++ b/compiler/optimizing/reference_type_propagation.cc @@ -166,31 +166,34 @@ void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) { } } -void ReferenceTypePropagation::SetClassAsTypeInfo(HInstruction* instr, mirror::Class* klass) { +void ReferenceTypePropagation::SetClassAsTypeInfo(HInstruction* instr, + mirror::Class* klass, + bool is_exact) { if (klass != nullptr) { ScopedObjectAccess soa(Thread::Current()); MutableHandle handle = handles_->NewHandle(klass); - instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(handle, true)); + instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(handle, is_exact)); } } void ReferenceTypePropagation::UpdateReferenceTypeInfo(HInstruction* instr, uint16_t type_idx, - const DexFile& dex_file) { + const DexFile& dex_file, + bool is_exact) { DCHECK_EQ(instr->GetType(), Primitive::kPrimNot); ScopedObjectAccess soa(Thread::Current()); mirror::DexCache* dex_cache = Runtime::Current()->GetClassLinker()->FindDexCache(dex_file); // Get type from dex cache assuming it was populated by the verifier. - SetClassAsTypeInfo(instr, dex_cache->GetResolvedType(type_idx)); + SetClassAsTypeInfo(instr, dex_cache->GetResolvedType(type_idx), is_exact); } void ReferenceTypePropagation::VisitNewInstance(HNewInstance* instr) { - UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile()); + UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true); } void ReferenceTypePropagation::VisitNewArray(HNewArray* instr) { - UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile()); + UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true); } void ReferenceTypePropagation::UpdateFieldAccessTypeInfo(HInstruction* instr, @@ -206,7 +209,7 @@ void ReferenceTypePropagation::UpdateFieldAccessTypeInfo(HInstruction* instr, ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), dex_cache); DCHECK(field != nullptr); mirror::Class* klass = field->GetType(); - SetClassAsTypeInfo(instr, klass); + SetClassAsTypeInfo(instr, klass, /* is_exact */ false); } void ReferenceTypePropagation::VisitInstanceFieldGet(HInstanceFieldGet* instr) { diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h index 74e425fb3..0a1d4c496 100644 --- a/compiler/optimizing/reference_type_propagation.h +++ b/compiler/optimizing/reference_type_propagation.h @@ -46,14 +46,17 @@ class ReferenceTypePropagation : public HOptimization { void VisitPhi(HPhi* phi); void VisitBasicBlock(HBasicBlock* block); void UpdateFieldAccessTypeInfo(HInstruction* instr, const FieldInfo& info); - void SetClassAsTypeInfo(HInstruction* instr, mirror::Class* klass); + void SetClassAsTypeInfo(HInstruction* instr, mirror::Class* klass, bool is_exact); void UpdateBoundType(HBoundType* bound_type) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); void UpdatePhi(HPhi* phi) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); void BoundTypeForIfNotNull(HBasicBlock* block); void BoundTypeForIfInstanceOf(HBasicBlock* block); - void UpdateReferenceTypeInfo(HInstruction* instr, uint16_t type_idx, const DexFile& dex_file); + void UpdateReferenceTypeInfo(HInstruction* instr, + uint16_t type_idx, + const DexFile& dex_file, + bool is_exact); void VisitInstanceFieldGet(HInstanceFieldGet* instr); void VisitStaticFieldGet(HStaticFieldGet* instr); diff --git a/test/444-checker-nce/src/Main.java b/test/444-checker-nce/src/Main.java index 6ac0cad7e..32122e4dc 100644 --- a/test/444-checker-nce/src/Main.java +++ b/test/444-checker-nce/src/Main.java @@ -27,37 +27,37 @@ public class Main { return m.g(); } - /// CHECK-START: Main Main.thisTest() instruction_simplifier (before) + /// CHECK-START: Main Main.thisTest() ssa_builder (after) /// CHECK: NullCheck /// CHECK: InvokeStaticOrDirect - /// CHECK-START: Main Main.thisTest() instruction_simplifier (after) + /// CHECK-START: Main Main.thisTest() instruction_simplifier_after_types (after) /// CHECK-NOT: NullCheck /// CHECK: InvokeStaticOrDirect public Main thisTest() { return g(); } - /// CHECK-START: Main Main.newInstanceRemoveTest() instruction_simplifier (before) + /// CHECK-START: Main Main.newInstanceRemoveTest() ssa_builder (after) /// CHECK: NewInstance /// CHECK: NullCheck /// CHECK: InvokeStaticOrDirect /// CHECK: NullCheck /// CHECK: InvokeStaticOrDirect - /// CHECK-START: Main Main.newInstanceRemoveTest() instruction_simplifier (after) + /// CHECK-START: Main Main.newInstanceRemoveTest() instruction_simplifier_after_types (after) /// CHECK-NOT: NullCheck public Main newInstanceRemoveTest() { Main m = new Main(); return m.g(); } - /// CHECK-START: Main Main.newArrayRemoveTest() instruction_simplifier (before) + /// CHECK-START: Main Main.newArrayRemoveTest() ssa_builder (after) /// CHECK: NewArray /// CHECK: NullCheck /// CHECK: ArrayGet - /// CHECK-START: Main Main.newArrayRemoveTest() instruction_simplifier (after) + /// CHECK-START: Main Main.newArrayRemoveTest() instruction_simplifier_after_types (after) /// CHECK: NewArray /// CHECK-NOT: NullCheck /// CHECK: ArrayGet @@ -178,10 +178,10 @@ public class Main { return n.g(); } - /// CHECK-START: Main Main.scopeRemoveTest(int, Main) instruction_simplifier (before) + /// CHECK-START: Main Main.scopeRemoveTest(int, Main) ssa_builder (after) /// CHECK: NullCheck - /// CHECK-START: Main Main.scopeRemoveTest(int, Main) instruction_simplifier (after) + /// CHECK-START: Main Main.scopeRemoveTest(int, Main) instruction_simplifier_after_types (after) /// CHECK-NOT: NullCheck public Main scopeRemoveTest(int count, Main a) { Main m = null; diff --git a/test/458-checker-instruction-simplification/src/Main.java b/test/458-checker-instruction-simplification/src/Main.java index ad5fc8ef9..ef18f64a3 100644 --- a/test/458-checker-instruction-simplification/src/Main.java +++ b/test/458-checker-instruction-simplification/src/Main.java @@ -933,18 +933,18 @@ public class Main { * remove the second. */ - /// CHECK-START: boolean Main.NotNotBool(boolean) instruction_simplifier_after_types (before) + /// CHECK-START: boolean Main.NotNotBool(boolean) last_instruction_simplifier (before) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> BooleanNot [<>] /// CHECK-DAG: <> BooleanNot [<>] /// CHECK-DAG: Return [<>] - /// CHECK-START: boolean Main.NotNotBool(boolean) instruction_simplifier_after_types (after) + /// CHECK-START: boolean Main.NotNotBool(boolean) last_instruction_simplifier (after) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: BooleanNot [<>] /// CHECK-DAG: Return [<>] - /// CHECK-START: boolean Main.NotNotBool(boolean) instruction_simplifier_after_types (after) + /// CHECK-START: boolean Main.NotNotBool(boolean) last_instruction_simplifier (after) /// CHECK: BooleanNot /// CHECK-NOT: BooleanNot diff --git a/test/490-checker-inline/expected.txt b/test/490-checker-inline/expected.txt new file mode 100644 index 000000000..e69de29bb diff --git a/test/490-checker-inline/info.txt b/test/490-checker-inline/info.txt new file mode 100644 index 000000000..0e42d771f --- /dev/null +++ b/test/490-checker-inline/info.txt @@ -0,0 +1 @@ +Check that we inline virtual and interface calls. diff --git a/test/490-checker-inline/src/Main.java b/test/490-checker-inline/src/Main.java new file mode 100644 index 000000000..21a01897e --- /dev/null +++ b/test/490-checker-inline/src/Main.java @@ -0,0 +1,52 @@ +/* + * 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. + */ + +interface Itf { + public void invokeInterface(); +} + +public class Main implements Itf { + + public void invokeInterface () { + } + + public void invokeVirtual() { + } + + public static Main createMain() { + return new Main(); + } + + public static Itf createItf() { + return new Main(); + } + + /// CHECK-START: void Main.testMethod() inliner (before) + /// CHECK-DAG: InvokeVirtual + /// CHECK-DAG: InvokeInterface + + /// CHECK-START: void Main.testMethod() inliner (after) + /// CHECK-NOT: Invoke{{.*}} + + public static void testMethod() { + createMain().invokeVirtual(); + createItf().invokeInterface(); + } + + public static void main(String[] args) { + testMethod(); + } +} -- 2.11.0