"Revert^6 "CHA for interface method."""

Update test expectations for CHA tests flaking on no-dex2oat.

bug:36344221

This reverts commit 27ef25f084017421ca05508208f436b5fc11df73.

Change-Id: Ie92adc7a2ec3b3081a1c57d71f8c89247e58cd46

26 files changed, 880 insertions, 24 deletions

diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index eda26f1127..f7331452c6 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -360,7 +360,18 @@ ArtMethod* HInliner::TryCHADevirtualization(ArtMethod* resolved_method) {
     return nullptr;
   }
   PointerSize pointer_size = caller_compilation_unit_.GetClassLinker()->GetImagePointerSize();
-  return resolved_method->GetSingleImplementation(pointer_size);
+  ArtMethod* single_impl = resolved_method->GetSingleImplementation(pointer_size);
+  if (single_impl == nullptr) {
+    return nullptr;
+  }
+  if (single_impl->IsProxyMethod()) {
+    // Proxy method is a generic invoker that's not worth
+    // devirtualizing/inlining. It also causes issues when the proxy
+    // method is in another dex file if we try to rewrite invoke-interface to
+    // invoke-virtual because a proxy method doesn't have a real dex file.
+    return nullptr;
+  }
+  return single_impl;
 }
 
 bool HInliner::TryInline(HInvoke* invoke_instruction) {
@@ -1106,11 +1117,23 @@ bool HInliner::TryInlineAndReplace(HInvoke* invoke_instruction,
   HBasicBlock* bb_cursor = invoke_instruction->GetBlock();
   if (!TryBuildAndInline(invoke_instruction, method, receiver_type, &return_replacement)) {
     if (invoke_instruction->IsInvokeInterface()) {
+      DCHECK(!method->IsProxyMethod());
       // Turn an invoke-interface into an invoke-virtual. An invoke-virtual is always
       // better than an invoke-interface because:
       // 1) In the best case, the interface call has one more indirection (to fetch the IMT).
       // 2) We will not go to the conflict trampoline with an invoke-virtual.
       // TODO: Consider sharpening once it is not dependent on the compiler driver.
+
+      if (method->IsDefault() && !method->IsCopied()) {
+        // Changing to invoke-virtual cannot be done on an original default method
+        // since it's not in any vtable. Devirtualization by exact type/inline-cache
+        // always uses a method in the iftable which is never an original default
+        // method.
+        // On the other hand, inlining an original default method by CHA is fine.
+        DCHECK(cha_devirtualize);
+        return false;
+      }
+
       const DexFile& caller_dex_file = *caller_compilation_unit_.GetDexFile();
       uint32_t dex_method_index = FindMethodIndexIn(
           method, caller_dex_file, invoke_instruction->GetDexMethodIndex());
diff --git a/runtime/art_method.h b/runtime/art_method.h
index 2248c3bd9d..8f09cc6d03 100644
--- a/runtime/art_method.h
+++ b/runtime/art_method.h
@@ -691,7 +691,7 @@ class ArtMethod FINAL {
 
     // 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
-    // single-implementation of an abstract method.
+    // single-implementation of an abstract/interface 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 eaba01b2ce..7948c29e5d 100644
--- a/runtime/cha.cc
+++ b/runtime/cha.cc
@@ -210,7 +210,7 @@ void ClassHierarchyAnalysis::VerifyNonSingleImplementation(mirror::Class* verify
   }
 }
 
-void ClassHierarchyAnalysis::CheckSingleImplementationInfo(
+void ClassHierarchyAnalysis::CheckVirtualMethodSingleImplementationInfo(
     Handle<mirror::Class> klass,
     ArtMethod* virtual_method,
     ArtMethod* method_in_super,
@@ -290,8 +290,9 @@ void ClassHierarchyAnalysis::CheckSingleImplementationInfo(
       // A non-abstract method overrides an abstract method.
       if (method_in_super->GetSingleImplementation(pointer_size) == nullptr) {
         // Abstract method_in_super has no implementation yet.
-        // We need to grab cha_lock_ for further checking/updating due to possible
-        // races.
+        // We need to grab cha_lock_ since there may be multiple class linking
+        // going on that can check/modify the single-implementation flag/method
+        // of method_in_super.
         MutexLock cha_mu(Thread::Current(), *Locks::cha_lock_);
         if (!method_in_super->HasSingleImplementation()) {
           return;
@@ -362,6 +363,55 @@ void ClassHierarchyAnalysis::CheckSingleImplementationInfo(
   }
 }
 
+void ClassHierarchyAnalysis::CheckInterfaceMethodSingleImplementationInfo(
+    Handle<mirror::Class> klass,
+    ArtMethod* interface_method,
+    ArtMethod* implementation_method,
+    std::unordered_set<ArtMethod*>& invalidated_single_impl_methods,
+    PointerSize pointer_size) {
+  DCHECK(klass->IsInstantiable());
+  DCHECK(interface_method->IsAbstract() || interface_method->IsDefault());
+
+  if (!interface_method->HasSingleImplementation()) {
+    return;
+  }
+
+  if (implementation_method->IsAbstract()) {
+    // An instantiable class doesn't supply an implementation for
+    // interface_method. Invoking the interface method on the class will throw
+    // AbstractMethodError. This is an uncommon case, so we simply treat
+    // interface_method as not having single-implementation.
+    invalidated_single_impl_methods.insert(interface_method);
+    return;
+  }
+
+  // We need to grab cha_lock_ since there may be multiple class linking going
+  // on that can check/modify the single-implementation flag/method of
+  // interface_method.
+  MutexLock cha_mu(Thread::Current(), *Locks::cha_lock_);
+  // Do this check again after we grab cha_lock_.
+  if (!interface_method->HasSingleImplementation()) {
+    return;
+  }
+
+  ArtMethod* single_impl = interface_method->GetSingleImplementation(pointer_size);
+  if (single_impl == nullptr) {
+    // implementation_method becomes the first implementation for
+    // interface_method.
+    interface_method->SetSingleImplementation(implementation_method, pointer_size);
+    // Keep interface_method's single-implementation status.
+    return;
+  }
+  DCHECK(!single_impl->IsAbstract());
+  if (single_impl->GetDeclaringClass() == implementation_method->GetDeclaringClass()) {
+    // Same implementation. Since implementation_method may be a copy of a default
+    // method, we need to check the declaring class for equality.
+    return;
+  }
+  // Another implementation for interface_method.
+  invalidated_single_impl_methods.insert(interface_method);
+}
+
 void ClassHierarchyAnalysis::InitSingleImplementationFlag(Handle<mirror::Class> klass,
                                                           ArtMethod* method,
                                                           PointerSize pointer_size) {
@@ -382,6 +432,7 @@ void ClassHierarchyAnalysis::InitSingleImplementationFlag(Handle<mirror::Class>
       // Rare case, but we do accept it (such as 800-smali/smali/b_26143249.smali).
       // Do not attempt to devirtualize it.
       method->SetHasSingleImplementation(false);
+      DCHECK(method->GetSingleImplementation(pointer_size) == nullptr);
     } else {
       // Abstract method starts with single-implementation flag set and null
       // implementation method.
@@ -396,9 +447,15 @@ void ClassHierarchyAnalysis::InitSingleImplementationFlag(Handle<mirror::Class>
 }
 
 void ClassHierarchyAnalysis::UpdateAfterLoadingOf(Handle<mirror::Class> klass) {
+  PointerSize image_pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize();
   if (klass->IsInterface()) {
+    for (ArtMethod& method : klass->GetDeclaredVirtualMethods(image_pointer_size)) {
+      DCHECK(method.IsAbstract() || method.IsDefault());
+      InitSingleImplementationFlag(klass, &method, image_pointer_size);
+    }
     return;
   }
+
   mirror::Class* super_class = klass->GetSuperClass();
   if (super_class == nullptr) {
     return;
@@ -408,7 +465,6 @@ void ClassHierarchyAnalysis::UpdateAfterLoadingOf(Handle<mirror::Class> klass) {
   // is invalidated by linking `klass`.
   std::unordered_set<ArtMethod*> invalidated_single_impl_methods;
 
-  PointerSize image_pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize();
   // Do an entry-by-entry comparison of vtable contents with super's vtable.
   for (int32_t i = 0; i < super_class->GetVTableLength(); ++i) {
     ArtMethod* method = klass->GetVTableEntry(i, image_pointer_size);
@@ -418,33 +474,59 @@ void ClassHierarchyAnalysis::UpdateAfterLoadingOf(Handle<mirror::Class> klass) {
       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);
+        CheckVirtualMethodSingleImplementationInfo(klass,
+                                                   method,
+                                                   method_in_super,
+                                                   invalidated_single_impl_methods,
+                                                   image_pointer_size);
       }
       continue;
     }
     InitSingleImplementationFlag(klass, method, image_pointer_size);
-    CheckSingleImplementationInfo(klass,
-                                  method,
-                                  method_in_super,
-                                  invalidated_single_impl_methods,
-                                  image_pointer_size);
+    CheckVirtualMethodSingleImplementationInfo(klass,
+                                               method,
+                                               method_in_super,
+                                               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, image_pointer_size);
   }
 
-  Runtime* const runtime = Runtime::Current();
+  if (klass->IsInstantiable()) {
+    auto* iftable = klass->GetIfTable();
+    const size_t ifcount = klass->GetIfTableCount();
+    for (size_t i = 0; i < ifcount; ++i) {
+      mirror::Class* interface = iftable->GetInterface(i);
+      for (size_t j = 0, count = iftable->GetMethodArrayCount(i); j < count; ++j) {
+        ArtMethod* interface_method = interface->GetVirtualMethod(j, image_pointer_size);
+        mirror::PointerArray* method_array = iftable->GetMethodArray(i);
+        ArtMethod* implementation_method =
+            method_array->GetElementPtrSize<ArtMethod*>(j, image_pointer_size);
+        DCHECK(implementation_method != nullptr) << klass->PrettyClass();
+        CheckInterfaceMethodSingleImplementationInfo(klass,
+                                                     interface_method,
+                                                     implementation_method,
+                                                     invalidated_single_impl_methods,
+                                                     image_pointer_size);
+      }
+    }
+  }
+
+  InvalidateSingleImplementationMethods(invalidated_single_impl_methods);
+}
+
+void ClassHierarchyAnalysis::InvalidateSingleImplementationMethods(
+    std::unordered_set<ArtMethod*>& invalidated_single_impl_methods) {
   if (!invalidated_single_impl_methods.empty()) {
+    Runtime* const runtime = Runtime::Current();
     Thread *self = Thread::Current();
     // Method headers for compiled code to be invalidated.
     std::unordered_set<OatQuickMethodHeader*> dependent_method_headers;
+    PointerSize image_pointer_size =
+        Runtime::Current()->GetClassLinker()->GetImagePointerSize();
 
     {
       // We do this under cha_lock_. Committing code also grabs this lock to
diff --git a/runtime/cha.h b/runtime/cha.h
index a56a752d8c..99c49d2bca 100644
--- a/runtime/cha.h
+++ b/runtime/cha.h
@@ -117,11 +117,13 @@ class ClassHierarchyAnalysis {
                                     PointerSize pointer_size)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
+  // Check/update single-implementation info when one virtual method
+  // overrides another.
   // `virtual_method` in `klass` overrides `method_in_super`.
-  // This will invalidate some assumptions on single-implementation.
+  // This may invalidate some assumptions on single-implementation.
   // Append methods that should have their single-implementation flag invalidated
   // to `invalidated_single_impl_methods`.
-  void CheckSingleImplementationInfo(
+  void CheckVirtualMethodSingleImplementationInfo(
       Handle<mirror::Class> klass,
       ArtMethod* virtual_method,
       ArtMethod* method_in_super,
@@ -129,6 +131,23 @@ class ClassHierarchyAnalysis {
       PointerSize pointer_size)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
+  // Check/update single-implementation info when one method
+  // implements an interface method.
+  // `implementation_method` in `klass` implements `interface_method`.
+  // Append `interface_method` to `invalidated_single_impl_methods`
+  // if `interface_method` gets a new implementation.
+  void CheckInterfaceMethodSingleImplementationInfo(
+      Handle<mirror::Class> klass,
+      ArtMethod* interface_method,
+      ArtMethod* implementation_method,
+      std::unordered_set<ArtMethod*>& invalidated_single_impl_methods,
+      PointerSize pointer_size)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
+  void InvalidateSingleImplementationMethods(
+      std::unordered_set<ArtMethod*>& invalidated_single_impl_methods)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
   // 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`.
diff --git a/test/616-cha-abstract/src/Main.java b/test/616-cha-abstract/src/Main.java
index e1d7db170d..b33f575dec 100644
--- a/test/616-cha-abstract/src/Main.java
+++ b/test/616-cha-abstract/src/Main.java
@@ -39,8 +39,8 @@ class Main2 extends Main1 {
 }
 
 public class Main {
-  static Main1 sMain1;
-  static Main1 sMain2;
+  static Base sMain1;
+  static Base sMain2;
 
   static boolean sIsOptimizing = true;
   static boolean sHasJIT = true;
diff --git a/test/616-cha-interface-default/expected.txt b/test/616-cha-interface-default/expected.txt
new file mode 100644
index 0000000000..6a5618ebc6
--- /dev/null
+++ b/test/616-cha-interface-default/expected.txt
@@ -0,0 +1 @@
+JNI_OnLoad called
diff --git a/test/616-cha-interface-default/info.txt b/test/616-cha-interface-default/info.txt
new file mode 100644
index 0000000000..11baa1f0f2
--- /dev/null
+++ b/test/616-cha-interface-default/info.txt
@@ -0,0 +1,2 @@
+Test for Class Hierarchy Analysis (CHA) on interface method.
+Test it under multidex configuration to check cross-dex inlining.
diff --git a/test/616-cha-interface-default/multidex.jpp b/test/616-cha-interface-default/multidex.jpp
new file mode 100644
index 0000000000..b0d200ea38
--- /dev/null
+++ b/test/616-cha-interface-default/multidex.jpp
@@ -0,0 +1,3 @@
+Main:
+  @@com.android.jack.annotations.ForceInMainDex
+  class Main
diff --git a/test/616-cha-interface-default/run b/test/616-cha-interface-default/run
new file mode 100644
index 0000000000..d8b4f0d26c
--- /dev/null
+++ b/test/616-cha-interface-default/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-interface-default/src-multidex/Base.java b/test/616-cha-interface-default/src-multidex/Base.java
new file mode 100644
index 0000000000..2cbcb500c4
--- /dev/null
+++ b/test/616-cha-interface-default/src-multidex/Base.java
@@ -0,0 +1,41 @@
+/*
+ * 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.
+ */
+
+interface Base {
+  default public int foo(int i) {
+    if (i != 1) {
+      return -2;
+    }
+    return i + 10;
+  }
+
+  // Test default method that's not inlined.
+  default public int $noinline$bar() {
+    System.out.print("");
+    System.out.print("");
+    System.out.print("");
+    System.out.print("");
+    System.out.print("");
+    System.out.print("");
+    System.out.print("");
+    System.out.print("");
+    return -1;
+  }
+
+  default void printError(String msg) {
+    System.out.println(msg);
+  }
+}
diff --git a/test/616-cha-interface-default/src/Main.java b/test/616-cha-interface-default/src/Main.java
new file mode 100644
index 0000000000..951607d2cf
--- /dev/null
+++ b/test/616-cha-interface-default/src/Main.java
@@ -0,0 +1,176 @@
+/*
+ * 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.
+ */
+
+class Main1 implements Base {
+}
+
+class Main2 extends Main1 {
+  public void foobar() {}
+}
+
+class Main3 implements Base {
+  public int foo(int i) {
+    if (i != 3) {
+      printError("error3");
+    }
+    return -(i + 10);
+  }
+}
+
+public class Main {
+  static Base sMain1;
+  static Base sMain2;
+  static Base sMain3;
+
+  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);
+    }
+  }
+
+  static int getValue(Class<?> cls) {
+    if (cls == Main1.class || cls == Main2.class) {
+      return 1;
+    }
+    return 3;
+  }
+
+  // sMain1.foo()/sMain2.foo() will be always be Base.foo() before Main3 is loaded/linked.
+  // So sMain1.foo() can be devirtualized to Base.foo() and be inlined.
+  // After Dummy.createMain3() which links in Main3, live testImplement() on stack
+  // should be deoptimized.
+  static void testImplement(boolean createMain3, boolean wait, boolean setHasJIT) {
+    if (setHasJIT) {
+      if (isInterpreted()) {
+        sHasJIT = false;
+      }
+      return;
+    }
+
+    if (createMain3 && (sIsOptimizing || sHasJIT)) {
+      assertIsManaged();
+    }
+
+    if (sMain1.foo(getValue(sMain1.getClass())) != 11) {
+      System.out.println("11 expected.");
+    }
+    if (sMain1.$noinline$bar() != -1) {
+      System.out.println("-1 expected.");
+    }
+    if (sMain2.foo(getValue(sMain2.getClass())) != 11) {
+      System.out.println("11 expected.");
+    }
+
+    if (createMain3) {
+      // Wait for the other thread to start.
+      while (!sOtherThreadStarted);
+      // Create an Main2 instance and assign it to sMain2.
+      // sMain1 is kept the same.
+      sMain3 = Dummy.createMain3();
+      // 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 Main3 is linked by
+    // calling Dummy.createMain3(), 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.
+    if (sMain1.foo(getValue(sMain1.getClass())) != 11) {
+      System.out.println("11 expected.");
+    }
+    if ((createMain3 || wait) && sHasJIT && !sIsOptimizing) {
+      // This method should be deoptimized right after Main3 is created.
+      assertIsInterpreted();
+    }
+
+    if (sMain3 != null) {
+      if (sMain3.foo(getValue(sMain3.getClass())) != -13) {
+        System.out.println("-13 expected.");
+      }
+    }
+  }
+
+  // Test scenarios under which CHA-based devirtualization happens,
+  // and class loading that implements 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.
+    // sMain2 is an instance of Main2.
+    // Neither Main1 nor Main2 override default method Base.foo().
+    // Main3 hasn't bee loaded yet.
+    sMain1 = new Main1();
+    sMain2 = new Main2();
+
+    ensureJitCompiled(Main.class, "testImplement");
+    testImplement(false, false, true);
+
+    if (sHasJIT && !sIsOptimizing) {
+      assertSingleImplementation(Base.class, "foo", true);
+      assertSingleImplementation(Main1.class, "foo", true);
+    } else {
+      // Main3 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() {
+        testImplement(false, true, false);
+      }
+    }.start();
+
+    // This will create Main3 instance in the middle of testImplement().
+    testImplement(true, false, false);
+    assertSingleImplementation(Base.class, "foo", false);
+    assertSingleImplementation(Main1.class, "foo", true);
+    assertSingleImplementation(sMain3.getClass(), "foo", true);
+  }
+
+  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 createMain3() in another class to avoid class loading due to verifier.
+class Dummy {
+  static Base createMain3() {
+    return new Main3();
+  }
+}
diff --git a/test/616-cha-interface/expected.txt b/test/616-cha-interface/expected.txt
new file mode 100644
index 0000000000..6a5618ebc6
--- /dev/null
+++ b/test/616-cha-interface/expected.txt
@@ -0,0 +1 @@
+JNI_OnLoad called
diff --git a/test/616-cha-interface/info.txt b/test/616-cha-interface/info.txt
new file mode 100644
index 0000000000..1fd330afd4
--- /dev/null
+++ b/test/616-cha-interface/info.txt
@@ -0,0 +1 @@
+Test for Class Hierarchy Analysis (CHA) on interface method.
diff --git a/test/616-cha-interface/run b/test/616-cha-interface/run
new file mode 100644
index 0000000000..d8b4f0d26c
--- /dev/null
+++ b/test/616-cha-interface/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-interface/src/Main.java b/test/616-cha-interface/src/Main.java
new file mode 100644
index 0000000000..3c9349663d
--- /dev/null
+++ b/test/616-cha-interface/src/Main.java
@@ -0,0 +1,173 @@
+/*
+ * 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.
+ */
+
+interface Base {
+  void foo(int i);
+  void $noinline$bar();
+}
+
+class Main1 implements Base {
+  public void foo(int i) {
+    if (i != 1) {
+      printError("error1");
+    }
+  }
+
+  // Test rewriting invoke-interface into invoke-virtual when inlining fails.
+  public void $noinline$bar() {
+    System.out.print("");
+    System.out.print("");
+    System.out.print("");
+    System.out.print("");
+    System.out.print("");
+    System.out.print("");
+    System.out.print("");
+    System.out.print("");
+  }
+
+  void printError(String msg) {
+    System.out.println(msg);
+  }
+}
+
+class Main2 extends Main1 {
+  public void foo(int i) {
+    if (i != 2) {
+      printError("error2");
+    }
+  }
+}
+
+public class Main {
+  static Base sMain1;
+  static Base 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 testImplement() on stack
+  // should be deoptimized.
+  static void testImplement(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);
+    sMain1.$noinline$bar();
+
+    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, "testImplement");
+    testImplement(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() {
+        testImplement(false, true, false);
+      }
+    }.start();
+
+    // This will create Main2 instance in the middle of testImplement().
+    testImplement(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();
+  }
+}
diff --git a/test/616-cha-miranda/expected.txt b/test/616-cha-miranda/expected.txt
new file mode 100644
index 0000000000..6a5618ebc6
--- /dev/null
+++ b/test/616-cha-miranda/expected.txt
@@ -0,0 +1 @@
+JNI_OnLoad called
diff --git a/test/616-cha-miranda/info.txt b/test/616-cha-miranda/info.txt
new file mode 100644
index 0000000000..c46f33f613
--- /dev/null
+++ b/test/616-cha-miranda/info.txt
@@ -0,0 +1 @@
+Test for Class Hierarchy Analysis (CHA) on miranda method.
diff --git a/test/616-cha-miranda/run b/test/616-cha-miranda/run
new file mode 100644
index 0000000000..d8b4f0d26c
--- /dev/null
+++ b/test/616-cha-miranda/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-miranda/src/Main.java b/test/616-cha-miranda/src/Main.java
new file mode 100644
index 0000000000..e548482eb3
--- /dev/null
+++ b/test/616-cha-miranda/src/Main.java
@@ -0,0 +1,163 @@
+/*
+ * 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.
+ */
+
+interface Iface {
+  public void foo(int i);
+}
+
+abstract class Base implements Iface {
+  // Iface.foo(int) will be added as a miranda method.
+
+  void printError(String msg) {
+    System.out.println(msg);
+  }
+}
+
+class Main1 extends Base {
+  public void foo(int i) {
+    if (i != 1) {
+      printError("error1");
+    }
+  }
+}
+
+class Main2 extends Main1 {
+  public void foo(int i) {
+    if (i != 2) {
+      printError("error2");
+    }
+  }
+}
+
+public class Main {
+  static Base sMain1;
+  static Base 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();
+  }
+}
diff --git a/test/616-cha-proxy-method-inline/expected.txt b/test/616-cha-proxy-method-inline/expected.txt
new file mode 100644
index 0000000000..6a5618ebc6
--- /dev/null
+++ b/test/616-cha-proxy-method-inline/expected.txt
@@ -0,0 +1 @@
+JNI_OnLoad called
diff --git a/test/616-cha-proxy-method-inline/info.txt b/test/616-cha-proxy-method-inline/info.txt
new file mode 100644
index 0000000000..012685547c
--- /dev/null
+++ b/test/616-cha-proxy-method-inline/info.txt
@@ -0,0 +1 @@
+Test for Class Hierarchy Analysis (CHA) on inlining a cross-dex proxy method.
diff --git a/test/616-cha-proxy-method-inline/multidex.jpp b/test/616-cha-proxy-method-inline/multidex.jpp
new file mode 100644
index 0000000000..b0d200ea38
--- /dev/null
+++ b/test/616-cha-proxy-method-inline/multidex.jpp
@@ -0,0 +1,3 @@
+Main:
+  @@com.android.jack.annotations.ForceInMainDex
+  class Main
diff --git a/test/616-cha-proxy-method-inline/run b/test/616-cha-proxy-method-inline/run
new file mode 100644
index 0000000000..d8b4f0d26c
--- /dev/null
+++ b/test/616-cha-proxy-method-inline/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-proxy-method-inline/src-multidex/Foo.java b/test/616-cha-proxy-method-inline/src-multidex/Foo.java
new file mode 100644
index 0000000000..9deca3e646
--- /dev/null
+++ b/test/616-cha-proxy-method-inline/src-multidex/Foo.java
@@ -0,0 +1,19 @@
+/*
+ * 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.
+ */
+
+interface Foo {
+  public Object bar(Object obj);
+}
diff --git a/test/616-cha-proxy-method-inline/src/Main.java b/test/616-cha-proxy-method-inline/src/Main.java
new file mode 100644
index 0000000000..be7bc820b3
--- /dev/null
+++ b/test/616-cha-proxy-method-inline/src/Main.java
@@ -0,0 +1,70 @@
+/*
+ * 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.
+ */
+
+import java.lang.reflect.Method;
+import java.lang.reflect.InvocationTargetException;
+
+class DebugProxy implements java.lang.reflect.InvocationHandler {
+  private Object obj;
+  static Class<?>[] interfaces = {Foo.class};
+
+  public static Object newInstance(Object obj) {
+    return java.lang.reflect.Proxy.newProxyInstance(
+      Foo.class.getClassLoader(),
+      interfaces,
+      new DebugProxy(obj));
+  }
+
+  private DebugProxy(Object obj) {
+    this.obj = obj;
+  }
+
+  public Object invoke(Object proxy, Method m, Object[] args) throws Throwable {
+    Object result;
+    if (obj == null) {
+      return null;
+    }
+    try {
+      System.out.println("before invoking method " + m.getName());
+      result = m.invoke(obj, args);
+    } catch (InvocationTargetException e) {
+      throw e.getTargetException();
+    } catch (Exception e) {
+      throw new RuntimeException("unexpected invocation exception: " + e.getMessage());
+    } finally {
+      System.out.println("after invoking method " + m.getName());
+    }
+    return result;
+  }
+}
+
+public class Main {
+  public static void call(Foo foo) {
+    if (foo == null) {
+      return;
+    }
+    foo.bar(null);
+  }
+
+  public static void main(String[] args) {
+    System.loadLibrary(args[0]);
+    Foo foo = (Foo)DebugProxy.newInstance(null);
+    ensureJitCompiled(Main.class, "call");
+    call(foo);
+  }
+
+  private static native void ensureJitCompiled(Class<?> itf, String method_name);
+}
diff --git a/test/knownfailures.json b/test/knownfailures.json
index 2de34ca44f..abbdbb1f95 100644
--- a/test/knownfailures.json
+++ b/test/knownfailures.json
@@ -332,8 +332,11 @@
     {
         "tests": ["912-classes",
                   "616-cha",
-                  "616-cha-abstract"],
-        "bug": "http://b/36344364 http://b36344221",
+                  "616-cha-abstract",
+                  "616-cha-interface",
+                  "616-cha-miranda",
+                  "616-cha-proxy-method-inline"],
+        "bug": "http://b/36344364 http://b/36344221",
         "variant": "no-dex2oat | relocate-npatchoat"
     },
     {