CHA for abstract methods.
Add the ability to devirtualize abstract method invocation if
an abstract method has only one implementation. Only support in JIT
mode currently.
Test: new testcase and ART_TEST_JIT=true m -j20 test-art-host-run-test
Change-Id: I43da03a9fa9a73840f5eaf207c6611e0913a7f66
diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index 4109345..b3b1903 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -2341,6 +2341,16 @@
void ImageWriter::CopyAndFixupMethod(ArtMethod* orig,
ArtMethod* copy,
const ImageInfo& image_info) {
+ if (orig->IsAbstract()) {
+ // Ignore the single-implementation info for abstract method.
+ // Do this on orig instead of copy, otherwise there is a crash due to methods
+ // are copied before classes.
+ // TODO: handle fixup of single-implementation method for abstract method.
+ orig->SetHasSingleImplementation(false);
+ orig->SetSingleImplementation(
+ nullptr, Runtime::Current()->GetClassLinker()->GetImagePointerSize());
+ }
+
memcpy(copy, orig, ArtMethod::Size(target_ptr_size_));
copy->SetDeclaringClass(GetImageAddress(orig->GetDeclaringClassUnchecked()));
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 5d40f75..7772e8f 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -304,7 +304,8 @@
// We do not support HDeoptimize in OSR methods.
return nullptr;
}
- return resolved_method->GetSingleImplementation();
+ PointerSize pointer_size = caller_compilation_unit_.GetClassLinker()->GetImagePointerSize();
+ return resolved_method->GetSingleImplementation(pointer_size);
}
bool HInliner::TryInline(HInvoke* invoke_instruction) {
diff --git a/runtime/art_method.cc b/runtime/art_method.cc
index d7d39af..92f3727 100644
--- a/runtime/art_method.cc
+++ b/runtime/art_method.cc
@@ -55,15 +55,13 @@
extern "C" void art_quick_invoke_static_stub(ArtMethod*, uint32_t*, uint32_t, Thread*, JValue*,
const char*);
-ArtMethod* ArtMethod::GetSingleImplementation() {
+ArtMethod* ArtMethod::GetSingleImplementation(PointerSize pointer_size) {
DCHECK(!IsNative());
if (!IsAbstract()) {
// A non-abstract's single implementation is itself.
return this;
}
- // TODO: add single-implementation logic for abstract method by storing it
- // in ptr_sized_fields_.
- return nullptr;
+ return reinterpret_cast<ArtMethod*>(GetDataPtrSize(pointer_size));
}
ArtMethod* ArtMethod::FromReflectedMethod(const ScopedObjectAccessAlreadyRunnable& soa,
diff --git a/runtime/art_method.h b/runtime/art_method.h
index 17f343d..a33111a 100644
--- a/runtime/art_method.h
+++ b/runtime/art_method.h
@@ -456,7 +456,7 @@
}
}
- ArtMethod* GetSingleImplementation()
+ ArtMethod* GetSingleImplementation(PointerSize pointer_size)
REQUIRES_SHARED(Locks::mutator_lock_);
ALWAYS_INLINE void SetSingleImplementation(ArtMethod* method, PointerSize pointer_size) {
@@ -684,7 +684,8 @@
ArtMethod** dex_cache_resolved_methods_;
// Pointer to JNI function registered to this method, or a function to resolve the JNI function,
- // or the profiling data for non-native methods, or an ImtConflictTable.
+ // or the profiling data for non-native methods, or an ImtConflictTable, or the
+ // single-implementation of an abstract method.
void* data_;
// Method dispatch from quick compiled code invokes this pointer which may cause bridging into
diff --git a/runtime/cha.cc b/runtime/cha.cc
index d94b091..a1ad585 100644
--- a/runtime/cha.cc
+++ b/runtime/cha.cc
@@ -185,7 +185,8 @@
};
void ClassHierarchyAnalysis::VerifyNonSingleImplementation(mirror::Class* verify_class,
- uint16_t verify_index) {
+ uint16_t verify_index,
+ ArtMethod* excluded_method) {
// Grab cha_lock_ to make sure all single-implementation updates are seen.
PointerSize image_pointer_size =
Runtime::Current()->GetClassLinker()->GetImagePointerSize();
@@ -195,9 +196,11 @@
return;
}
ArtMethod* verify_method = verify_class->GetVTableEntry(verify_index, image_pointer_size);
- DCHECK(!verify_method->HasSingleImplementation())
- << "class: " << verify_class->PrettyClass()
- << " verify_method: " << verify_method->PrettyMethod(true);
+ if (verify_method != excluded_method) {
+ DCHECK(!verify_method->HasSingleImplementation())
+ << "class: " << verify_class->PrettyClass()
+ << " verify_method: " << verify_method->PrettyMethod(true);
+ }
verify_class = verify_class->GetSuperClass();
}
}
@@ -206,41 +209,152 @@
Handle<mirror::Class> klass,
ArtMethod* virtual_method,
ArtMethod* method_in_super,
- std::unordered_set<ArtMethod*>& invalidated_single_impl_methods) {
+ std::unordered_set<ArtMethod*>& invalidated_single_impl_methods,
+ PointerSize pointer_size) {
// TODO: if klass is not instantiable, virtual_method isn't invocable yet so
// even if it overrides, it doesn't invalidate single-implementation
// assumption.
- DCHECK_NE(virtual_method, method_in_super);
+ DCHECK((virtual_method != method_in_super) || virtual_method->IsAbstract());
DCHECK(method_in_super->GetDeclaringClass()->IsResolved()) << "class isn't resolved";
// If virtual_method doesn't come from a default interface method, it should
// be supplied by klass.
- DCHECK(virtual_method->IsCopied() ||
+ DCHECK(virtual_method == method_in_super ||
+ virtual_method->IsCopied() ||
virtual_method->GetDeclaringClass() == klass.Get());
- // A new virtual_method should set method_in_super to
- // non-single-implementation (if not set already).
- // We don't grab cha_lock_. Single-implementation flag won't be set to true
- // again once it's set to false.
+ // To make updating single-implementation flags simple, we always maintain the following
+ // invariant:
+ // Say all virtual methods in the same vtable slot, starting from the bottom child class
+ // to super classes, is a sequence of unique methods m3, m2, m1, ... (after removing duplicate
+ // methods for inherited methods).
+ // For example for the following class hierarchy,
+ // class A { void m() { ... } }
+ // class B extends A { void m() { ... } }
+ // class C extends B {}
+ // class D extends C { void m() { ... } }
+ // the sequence is D.m(), B.m(), A.m().
+ // The single-implementation status for that sequence of methods begin with one or two true's,
+ // then become all falses. The only case where two true's are possible is for one abstract
+ // method m and one non-abstract method mImpl that overrides method m.
+ // With the invariant, when linking in a new class, we only need to at most update one or
+ // two methods in the sequence for their single-implementation status, in order to maintain
+ // the invariant.
+
if (!method_in_super->HasSingleImplementation()) {
// method_in_super already has multiple implementations. All methods in the
// same vtable slots in its super classes should have
// non-single-implementation already.
if (kIsDebugBuild) {
VerifyNonSingleImplementation(klass->GetSuperClass()->GetSuperClass(),
- method_in_super->GetMethodIndex());
+ method_in_super->GetMethodIndex(),
+ nullptr /* excluded_method */);
}
return;
}
// Native methods don't have single-implementation flag set.
DCHECK(!method_in_super->IsNative());
- // Invalidate method_in_super's single-implementation status.
- invalidated_single_impl_methods.insert(method_in_super);
+
+ uint16_t method_index = method_in_super->GetMethodIndex();
+ if (method_in_super->IsAbstract()) {
+ if (kIsDebugBuild) {
+ // An abstract method should have made all methods in the same vtable
+ // slot above it in the class hierarchy having non-single-implementation.
+ mirror::Class* super_super = klass->GetSuperClass()->GetSuperClass();
+ VerifyNonSingleImplementation(super_super,
+ method_index,
+ method_in_super);
+ }
+
+ if (virtual_method->IsAbstract()) {
+ // SUPER: abstract, VIRTUAL: abstract.
+ if (method_in_super == virtual_method) {
+ DCHECK(klass->IsInstantiable());
+ // An instantiable subclass hasn't provided a concrete implementation of
+ // the abstract method. Invoking method_in_super may throw AbstractMethodError.
+ // This is an uncommon case, so we simply treat method_in_super as not
+ // having single-implementation.
+ invalidated_single_impl_methods.insert(method_in_super);
+ return;
+ } else {
+ // One abstract method overrides another abstract method. This is an uncommon
+ // case. We simply treat method_in_super as not having single-implementation.
+ invalidated_single_impl_methods.insert(method_in_super);
+ return;
+ }
+ } else {
+ // SUPER: abstract, VIRTUAL: non-abstract.
+ // A non-abstract method overrides an abstract method.
+ if (method_in_super->GetSingleImplementation(pointer_size) == nullptr) {
+ // Abstract method_in_super gets its first implementation. Keep it as having
+ // single-implementation and record that single implementation.
+ DCHECK(method_in_super->HasSingleImplementation());
+ method_in_super->SetSingleImplementation(virtual_method, pointer_size);
+ return;
+ } else {
+ // Abstract method_in_super already got one implementation.
+ // Invalidate method_in_super's single-implementation status.
+ invalidated_single_impl_methods.insert(method_in_super);
+ return;
+ }
+ }
+ } else {
+ if (virtual_method->IsAbstract()) {
+ // SUPER: non-abstract, VIRTUAL: abstract.
+ // An abstract method overrides a non-abstract method. This is an uncommon
+ // case, we simply treat both methods as not having single-implementation.
+ invalidated_single_impl_methods.insert(virtual_method);
+ // Fall-through to handle invalidating method_in_super of its
+ // single-implementation status.
+ }
+
+ // SUPER: non-abstract, VIRTUAL: non-abstract/abstract(fall-through from previous if).
+ // Invalidate method_in_super's single-implementation status.
+ invalidated_single_impl_methods.insert(method_in_super);
+
+ // method_in_super might be the single-implementation of another abstract method,
+ // which should be also invalidated of its single-implementation status.
+ mirror::Class* super_super = klass->GetSuperClass()->GetSuperClass();
+ while (super_super != nullptr &&
+ method_index < super_super->GetVTableLength()) {
+ ArtMethod* method_in_super_super = super_super->GetVTableEntry(method_index, pointer_size);
+ if (method_in_super_super != method_in_super) {
+ if (method_in_super_super->IsAbstract()) {
+ if (method_in_super_super->HasSingleImplementation()) {
+ // Invalidate method_in_super's single-implementation status.
+ invalidated_single_impl_methods.insert(method_in_super_super);
+ // No need to further traverse up the class hierarchy since if there
+ // are cases that one abstract method overrides another method, we
+ // should have made that method having non-single-implementation already.
+ } else {
+ // method_in_super_super is already non-single-implementation.
+ // No need to further traverse up the class hierarchy.
+ }
+ } else {
+ DCHECK(!method_in_super_super->HasSingleImplementation());
+ // No need to further traverse up the class hierarchy since two non-abstract
+ // methods (method_in_super and method_in_super_super) should have set all
+ // other methods (abstract or not) in the vtable slot to be non-single-implementation.
+ }
+
+ if (kIsDebugBuild) {
+ VerifyNonSingleImplementation(super_super->GetSuperClass(),
+ method_index,
+ method_in_super_super);
+ }
+ // No need to go any further.
+ return;
+ } else {
+ super_super = super_super->GetSuperClass();
+ }
+ }
+ }
}
void ClassHierarchyAnalysis::InitSingleImplementationFlag(Handle<mirror::Class> klass,
- ArtMethod* method) {
+ ArtMethod* method,
+ PointerSize pointer_size) {
DCHECK(method->IsCopied() || method->GetDeclaringClass() == klass.Get());
if (klass->IsFinal() || method->IsFinal()) {
// Final classes or methods do not need CHA for devirtualization.
@@ -253,16 +367,21 @@
// cannot be inlined. It's not worthwhile to devirtualize the
// call which can add a deoptimization point.
DCHECK(!method->HasSingleImplementation());
+ } else if (method->IsAbstract()) {
+ if (method->GetDeclaringClass()->IsInstantiable()) {
+ // Rare case, but we do accept it (such as 800-smali/smali/b_26143249.smali).
+ // Do not attempt to devirtualize it.
+ method->SetHasSingleImplementation(false);
+ } else {
+ // Abstract method starts with single-implementation flag set and null
+ // implementation method.
+ method->SetHasSingleImplementation(true);
+ DCHECK(method->GetSingleImplementation(pointer_size) == nullptr);
+ }
} else {
method->SetHasSingleImplementation(true);
- if (method->IsAbstract()) {
- // There is no real implementation yet.
- // TODO: implement single-implementation logic for abstract methods.
- DCHECK(method->GetSingleImplementation() == nullptr);
- } else {
- // Single implementation of non-abstract method is itself.
- DCHECK_EQ(method->GetSingleImplementation(), method);
- }
+ // Single implementation of non-abstract method is itself.
+ DCHECK_EQ(method->GetSingleImplementation(pointer_size), method);
}
}
@@ -286,19 +405,29 @@
ArtMethod* method_in_super = super_class->GetVTableEntry(i, image_pointer_size);
if (method == method_in_super) {
// vtable slot entry is inherited from super class.
+ if (method->IsAbstract() && klass->IsInstantiable()) {
+ // An instantiable class that inherits an abstract method is treated as
+ // supplying an implementation that throws AbstractMethodError.
+ CheckSingleImplementationInfo(klass,
+ method,
+ method_in_super,
+ invalidated_single_impl_methods,
+ image_pointer_size);
+ }
continue;
}
- InitSingleImplementationFlag(klass, method);
+ InitSingleImplementationFlag(klass, method, image_pointer_size);
CheckSingleImplementationInfo(klass,
method,
method_in_super,
- invalidated_single_impl_methods);
+ invalidated_single_impl_methods,
+ image_pointer_size);
}
// For new virtual methods that don't override.
for (int32_t i = super_class->GetVTableLength(); i < klass->GetVTableLength(); ++i) {
ArtMethod* method = klass->GetVTableEntry(i, image_pointer_size);
- InitSingleImplementationFlag(klass, method);
+ InitSingleImplementationFlag(klass, method, image_pointer_size);
}
Runtime* const runtime = Runtime::Current();
diff --git a/runtime/cha.h b/runtime/cha.h
index ada5c89..a56a752 100644
--- a/runtime/cha.h
+++ b/runtime/cha.h
@@ -112,7 +112,9 @@
void UpdateAfterLoadingOf(Handle<mirror::Class> klass) REQUIRES_SHARED(Locks::mutator_lock_);
private:
- void InitSingleImplementationFlag(Handle<mirror::Class> klass, ArtMethod* method)
+ void InitSingleImplementationFlag(Handle<mirror::Class> klass,
+ ArtMethod* method,
+ PointerSize pointer_size)
REQUIRES_SHARED(Locks::mutator_lock_);
// `virtual_method` in `klass` overrides `method_in_super`.
@@ -123,12 +125,16 @@
Handle<mirror::Class> klass,
ArtMethod* virtual_method,
ArtMethod* method_in_super,
- std::unordered_set<ArtMethod*>& invalidated_single_impl_methods)
+ std::unordered_set<ArtMethod*>& invalidated_single_impl_methods,
+ PointerSize pointer_size)
REQUIRES_SHARED(Locks::mutator_lock_);
- // Verify all methods in the same vtable slot from verify_class and its supers
- // don't have single-implementation.
- void VerifyNonSingleImplementation(mirror::Class* verify_class, uint16_t verify_index)
+ // For all methods in vtable slot at `verify_index` of `verify_class` and its
+ // superclasses, single-implementation status should be false, except if the
+ // method is `excluded_method`.
+ void VerifyNonSingleImplementation(mirror::Class* verify_class,
+ uint16_t verify_index,
+ ArtMethod* excluded_method)
REQUIRES_SHARED(Locks::mutator_lock_);
// A map that maps a method to a set of compiled code that assumes that method has a
diff --git a/test/616-cha-abstract/expected.txt b/test/616-cha-abstract/expected.txt
new file mode 100644
index 0000000..6a5618e
--- /dev/null
+++ b/test/616-cha-abstract/expected.txt
@@ -0,0 +1 @@
+JNI_OnLoad called
diff --git a/test/616-cha-abstract/info.txt b/test/616-cha-abstract/info.txt
new file mode 100644
index 0000000..4f7e013
--- /dev/null
+++ b/test/616-cha-abstract/info.txt
@@ -0,0 +1 @@
+Test for Class Hierarchy Analysis (CHA) on abstract method.
diff --git a/test/616-cha-abstract/run b/test/616-cha-abstract/run
new file mode 100644
index 0000000..d8b4f0d
--- /dev/null
+++ b/test/616-cha-abstract/run
@@ -0,0 +1,18 @@
+#!/bin/bash
+#
+# Copyright (C) 2017 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.
+
+# Run without an app image to prevent the classes to be loaded at startup.
+exec ${RUN} "${@}" --no-app-image
diff --git a/test/616-cha-abstract/src/Main.java b/test/616-cha-abstract/src/Main.java
new file mode 100644
index 0000000..e1d7db1
--- /dev/null
+++ b/test/616-cha-abstract/src/Main.java
@@ -0,0 +1,159 @@
+/*
+ * Copyright (C) 2017 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.
+ */
+
+abstract class Base {
+ abstract void foo(int i);
+
+ void printError(String msg) {
+ System.out.println(msg);
+ }
+}
+
+class Main1 extends Base {
+ void foo(int i) {
+ if (i != 1) {
+ printError("error1");
+ }
+ }
+}
+
+class Main2 extends Main1 {
+ void foo(int i) {
+ if (i != 2) {
+ printError("error2");
+ }
+ }
+}
+
+public class Main {
+ static Main1 sMain1;
+ static Main1 sMain2;
+
+ static boolean sIsOptimizing = true;
+ static boolean sHasJIT = true;
+ static volatile boolean sOtherThreadStarted;
+
+ private static void assertSingleImplementation(Class<?> clazz, String method_name, boolean b) {
+ if (hasSingleImplementation(clazz, method_name) != b) {
+ System.out.println(clazz + "." + method_name +
+ " doesn't have single implementation value of " + b);
+ }
+ }
+
+ // sMain1.foo() will be always be Main1.foo() before Main2 is loaded/linked.
+ // So sMain1.foo() can be devirtualized to Main1.foo() and be inlined.
+ // After Dummy.createMain2() which links in Main2, live testOverride() on stack
+ // should be deoptimized.
+ static void testOverride(boolean createMain2, boolean wait, boolean setHasJIT) {
+ if (setHasJIT) {
+ if (isInterpreted()) {
+ sHasJIT = false;
+ }
+ return;
+ }
+
+ if (createMain2 && (sIsOptimizing || sHasJIT)) {
+ assertIsManaged();
+ }
+
+ sMain1.foo(sMain1.getClass() == Main1.class ? 1 : 2);
+
+ if (createMain2) {
+ // Wait for the other thread to start.
+ while (!sOtherThreadStarted);
+ // Create an Main2 instance and assign it to sMain2.
+ // sMain1 is kept the same.
+ sMain2 = Dummy.createMain2();
+ // Wake up the other thread.
+ synchronized(Main.class) {
+ Main.class.notify();
+ }
+ } else if (wait) {
+ // This is the other thread.
+ synchronized(Main.class) {
+ sOtherThreadStarted = true;
+ // Wait for Main2 to be linked and deoptimization is triggered.
+ try {
+ Main.class.wait();
+ } catch (Exception e) {
+ }
+ }
+ }
+
+ // There should be a deoptimization here right after Main2 is linked by
+ // calling Dummy.createMain2(), even though sMain1 didn't change.
+ // The behavior here would be different if inline-cache is used, which
+ // doesn't deoptimize since sMain1 still hits the type cache.
+ sMain1.foo(sMain1.getClass() == Main1.class ? 1 : 2);
+ if ((createMain2 || wait) && sHasJIT && !sIsOptimizing) {
+ // This method should be deoptimized right after Main2 is created.
+ assertIsInterpreted();
+ }
+
+ if (sMain2 != null) {
+ sMain2.foo(sMain2.getClass() == Main1.class ? 1 : 2);
+ }
+ }
+
+ // Test scenarios under which CHA-based devirtualization happens,
+ // and class loading that overrides a method can invalidate compiled code.
+ public static void main(String[] args) {
+ System.loadLibrary(args[0]);
+
+ if (isInterpreted()) {
+ sIsOptimizing = false;
+ }
+
+ // sMain1 is an instance of Main1. Main2 hasn't bee loaded yet.
+ sMain1 = new Main1();
+
+ ensureJitCompiled(Main.class, "testOverride");
+ testOverride(false, false, true);
+
+ if (sHasJIT && !sIsOptimizing) {
+ assertSingleImplementation(Base.class, "foo", true);
+ assertSingleImplementation(Main1.class, "foo", true);
+ } else {
+ // Main2 is verified ahead-of-time so it's linked in already.
+ }
+
+ // Create another thread that also calls sMain1.foo().
+ // Try to test suspend and deopt another thread.
+ new Thread() {
+ public void run() {
+ testOverride(false, true, false);
+ }
+ }.start();
+
+ // This will create Main2 instance in the middle of testOverride().
+ testOverride(true, false, false);
+ assertSingleImplementation(Base.class, "foo", false);
+ assertSingleImplementation(Main1.class, "foo", false);
+ }
+
+ private static native void ensureJitCompiled(Class<?> itf, String method_name);
+ private static native void assertIsInterpreted();
+ private static native void assertIsManaged();
+ private static native boolean isInterpreted();
+ private static native boolean hasSingleImplementation(Class<?> clazz, String method_name);
+}
+
+// Put createMain2() in another class to avoid class loading due to verifier.
+class Dummy {
+ static Main1 createMain2() {
+ return new Main2();
+ }
+}