Unique names for overloads by separating naming and reservation

Newer ART-vms will output the PC of error instructions if no debug
line information is present along with the method. Having a lot of
overloads, which we normally generate to have as few strings as
possible, will make debugging more difficult or require us to put in
debug information since we cannot distinguish two methods with the
same name in a stack trace.

This CL changes this by generating unique names for all methods when
targeting DEX. This will add a few more strings to the method pool but
it seems like this is outweighed by savings to the debug info.

Bug: 37830524
Bug: 18629172
Bug: 144877828
Change-Id: I6a751483131c5163e7d197a9760545bb24335469
diff --git a/build.gradle b/build.gradle
index 1fd0955..d3b511c 100644
--- a/build.gradle
+++ b/build.gradle
@@ -838,7 +838,7 @@
     // Execute r8 commands against a stable r8 with relocated dependencies.
     // TODO(b/139725780): See if we can remove or lower the heap size (-Xmx6g).
     return [org.gradle.internal.jvm.Jvm.current().getJavaExecutable(),
-            "-Xmx6g", "-ea", "-jar", r8WithRelocatedDeps.outputs.files[0]] + args
+            "-Xmx8g", "-ea", "-jar", r8WithRelocatedDeps.outputs.files[0]] + args
 }
 
 def r8CfCommandLine(input, output, pgConfs = [], args = ["--release"], libs = []) {
diff --git a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
index 7af0752..f12d958 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
@@ -135,14 +135,15 @@
   MethodNameMinifier(AppView<AppInfoWithLiveness> appView, MemberNamingStrategy strategy) {
     this.appView = appView;
     this.strategy = strategy;
-    rootReservationState = MethodReservationState.createRoot(getKeyTransform());
+    rootReservationState = MethodReservationState.createRoot(getReservationKeyTransform());
     rootNamingState =
-        MethodNamingState.createRoot(getKeyTransform(), strategy, rootReservationState);
+        MethodNamingState.createRoot(getNamingKeyTransform(), strategy, rootReservationState);
     namingStates.put(null, rootNamingState);
   }
 
-  private Function<DexMethod, ?> getKeyTransform() {
-    if (appView.options().getProguardConfiguration().isOverloadAggressively()) {
+  private Function<DexMethod, ?> getReservationKeyTransform() {
+    if (appView.options().getProguardConfiguration().isOverloadAggressively()
+        && appView.options().isGeneratingClassFiles()) {
       // Use the full proto as key, hence reuse names based on full signature.
       return method -> method.proto;
     } else {
@@ -151,6 +152,12 @@
     }
   }
 
+  private Function<DexMethod, ?> getNamingKeyTransform() {
+    return appView.options().isGeneratingClassFiles()
+        ? getReservationKeyTransform()
+        : method -> null;
+  }
+
   static class MethodRenaming {
 
     final Map<DexMethod, DexString> renaming;
@@ -199,23 +206,9 @@
     MethodNamingState<?> namingState =
         namingStates.computeIfAbsent(
             type, ignore -> parentNamingState.createChild(reservationState));
-    // The names for direct methods should not contribute to the naming of methods in sub-types:
-    // class A {
-    //   public int foo() { ... }   --> a
-    //   private int bar() { ... }  --> b
-    // }
-    //
-    // class B extends A {
-    //   public int baz() { ... }   --> b
-    // }
-    //
-    // A simple way to ensure this is to process virtual methods first and then direct methods.
     DexClass holder = appView.definitionFor(type);
     if (holder != null && strategy.allowMemberRenaming(holder)) {
-      for (DexEncodedMethod method : holder.virtualMethodsSorted()) {
-        assignNameToMethod(holder, method, namingState);
-      }
-      for (DexEncodedMethod method : holder.directMethodsSorted()) {
+      for (DexEncodedMethod method : holder.allMethodsSorted()) {
         assignNameToMethod(holder, method, namingState);
       }
     }
@@ -239,9 +232,7 @@
     if (encodedMethod.method.name != newName) {
       renaming.put(encodedMethod.method, newName);
     }
-    if (!encodedMethod.isPrivateMethod()) {
-      state.addRenaming(newName, encodedMethod.method);
-    }
+    state.addRenaming(newName, encodedMethod.method);
   }
 
   private void reserveNamesInClasses() {
diff --git a/src/main/java/com/android/tools/r8/naming/MethodNamingState.java b/src/main/java/com/android/tools/r8/naming/MethodNamingState.java
index c6b7ee0..7926de0 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNamingState.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNamingState.java
@@ -6,6 +6,8 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.naming.MethodNamingState.InternalNewNameState;
+import com.android.tools.r8.utils.MethodSignatureEquivalence;
+import com.google.common.base.Equivalence.Wrapper;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Map;
@@ -72,8 +74,8 @@
   }
 
   boolean isAvailable(DexString candidate, DexMethod method) {
-    Set<DexString> usedBy = getUsedBy(candidate, method);
-    if (usedBy != null && usedBy.contains(method.name)) {
+    Set<Wrapper<DexMethod>> usedBy = getUsedBy(candidate, method);
+    if (usedBy != null && usedBy.contains(MethodSignatureEquivalence.get().wrap(method))) {
       return true;
     }
     boolean isReserved = reservationState.isReserved(candidate, method);
@@ -82,16 +84,13 @@
     }
     // We now have a reserved name. We therefore have to check if the reservation is
     // equal to candidate, otherwise the candidate is not available.
-    if (isReserved && usedBy == null) {
-      Set<DexString> methodReservedNames = reservationState.getReservedNamesFor(method);
-      return methodReservedNames != null && methodReservedNames.contains(candidate);
-    }
-    return false;
+    Set<DexString> methodReservedNames = reservationState.getReservedNamesFor(method);
+    return methodReservedNames != null && methodReservedNames.contains(candidate);
   }
 
-  private Set<DexString> getUsedBy(DexString name, DexMethod method) {
+  private Set<Wrapper<DexMethod>> getUsedBy(DexString name, DexMethod method) {
     InternalNewNameState internalState = getInternalState(method);
-    Set<DexString> nameUsedBy = null;
+    Set<Wrapper<DexMethod>> nameUsedBy = null;
     if (internalState != null) {
       nameUsedBy = internalState.getUsedBy(name);
     }
@@ -105,7 +104,7 @@
     DexString assignedName = null;
     InternalNewNameState internalState = getInternalState(method);
     if (internalState != null) {
-      assignedName = internalState.getAssignedName(method.name);
+      assignedName = internalState.getAssignedName(method);
     }
     if (assignedName == null && parentNamingState != null) {
       assignedName = parentNamingState.getAssignedName(method);
@@ -125,14 +124,13 @@
   static class InternalNewNameState implements InternalNamingState {
 
     private final InternalNewNameState parentInternalState;
-    private Map<DexString, DexString> originalToRenamedNames = new HashMap<>();
-    private Map<DexString, Set<DexString>> usedBy = new HashMap<>();
+    private Map<Wrapper<DexMethod>, DexString> originalToRenamedNames = new HashMap<>();
+    private Map<DexString, Set<Wrapper<DexMethod>>> usedBy = new HashMap<>();
 
     private static final int INITIAL_NAME_COUNT = 1;
     private static final int INITIAL_DICTIONARY_INDEX = 0;
 
-    private int virtualNameCount;
-    private int directNameCount = 0;
+    private int nameCount;
     private int dictionaryIndex;
 
     private InternalNewNameState(InternalNewNameState parentInternalState) {
@@ -141,8 +139,8 @@
           parentInternalState == null
               ? INITIAL_DICTIONARY_INDEX
               : parentInternalState.dictionaryIndex;
-      this.virtualNameCount =
-          parentInternalState == null ? INITIAL_NAME_COUNT : parentInternalState.virtualNameCount;
+      this.nameCount =
+          parentInternalState == null ? INITIAL_NAME_COUNT : parentInternalState.nameCount;
     }
 
     @Override
@@ -155,40 +153,35 @@
       return dictionaryIndex++;
     }
 
-    Set<DexString> getUsedBy(DexString name) {
+    Set<Wrapper<DexMethod>> getUsedBy(DexString name) {
       return usedBy.get(name);
     }
 
-    DexString getAssignedName(DexString originalName) {
-      return originalToRenamedNames.get(originalName);
+    DexString getAssignedName(DexMethod method) {
+      return originalToRenamedNames.get(MethodSignatureEquivalence.get().wrap(method));
     }
 
     void addRenaming(DexString newName, DexMethod method) {
-      originalToRenamedNames.put(method.name, newName);
-      usedBy.computeIfAbsent(newName, ignore -> new HashSet<>()).add(method.name);
+      final Wrapper<DexMethod> wrappedMethod = MethodSignatureEquivalence.get().wrap(method);
+      originalToRenamedNames.put(wrappedMethod, newName);
+      usedBy.computeIfAbsent(newName, ignore -> new HashSet<>()).add(wrappedMethod);
     }
 
     private boolean checkParentPublicNameCountIsLessThanOrEqual() {
       int maxParentCount = 0;
       InternalNewNameState tmp = parentInternalState;
       while (tmp != null) {
-        maxParentCount = Math.max(tmp.virtualNameCount, maxParentCount);
+        maxParentCount = Math.max(tmp.nameCount, maxParentCount);
         tmp = tmp.parentInternalState;
       }
-      assert maxParentCount <= virtualNameCount;
+      assert maxParentCount <= nameCount;
       return true;
     }
 
     @Override
     public int incrementNameIndex(boolean isDirectMethodCall) {
       assert checkParentPublicNameCountIsLessThanOrEqual();
-      if (isDirectMethodCall) {
-        return virtualNameCount + directNameCount++;
-      } else {
-        // TODO(b/144877828): is it guaranteed?
-        assert directNameCount == 0;
-        return virtualNameCount++;
-      }
+      return nameCount++;
     }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/naming/MethodReservationState.java b/src/main/java/com/android/tools/r8/naming/MethodReservationState.java
index ad5b8cc..2ce35f9 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodReservationState.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodReservationState.java
@@ -7,6 +7,8 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.naming.MethodReservationState.InternalReservationState;
+import com.android.tools.r8.utils.MethodSignatureEquivalence;
+import com.google.common.base.Equivalence.Wrapper;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Map;
@@ -36,7 +38,7 @@
 
   void reserveName(DexString reservedName, DexMethod method) {
     try {
-      getOrCreateInternalState(method).reserveName(method.name, reservedName);
+      getOrCreateInternalState(method).reserveName(method, reservedName);
     } catch (AssertionError err) {
       throw new RuntimeException(
           String.format(
@@ -61,7 +63,7 @@
     InternalReservationState internalState = getInternalState(method);
     Set<DexString> reservedName = null;
     if (internalState != null) {
-      reservedName = internalState.getAssignedNamesFor(method.name);
+      reservedName = internalState.getAssignedNamesFor(method);
     }
     if (reservedName == null && parentNamingState != null) {
       reservedName = parentNamingState.getReservedNamesFor(method);
@@ -75,28 +77,28 @@
   }
 
   static class InternalReservationState {
-    private Map<DexString, Set<DexString>> originalToReservedNames = null;
+    private Map<Wrapper<DexMethod>, Set<DexString>> originalToReservedNames = null;
     private Set<DexString> reservedNames = null;
 
     boolean isReserved(DexString name) {
       return reservedNames != null && reservedNames.contains(name);
     }
 
-    Set<DexString> getAssignedNamesFor(DexString original) {
-      Set<DexString> result = null;
-      if (originalToReservedNames != null) {
-        result = originalToReservedNames.get(original);
+    Set<DexString> getAssignedNamesFor(DexMethod method) {
+      if (originalToReservedNames == null) {
+        return null;
       }
-      return result;
+      return originalToReservedNames.get(MethodSignatureEquivalence.get().wrap(method));
     }
 
-    void reserveName(DexString originalName, DexString name) {
+    void reserveName(DexMethod method, DexString name) {
       if (reservedNames == null) {
         assert originalToReservedNames == null;
         originalToReservedNames = new HashMap<>();
         reservedNames = new HashSet<>();
       }
-      originalToReservedNames.computeIfAbsent(originalName, ignore -> new HashSet<>()).add(name);
+      final Wrapper<DexMethod> wrapped = MethodSignatureEquivalence.get().wrap(method);
+      originalToReservedNames.computeIfAbsent(wrapped, ignore -> new HashSet<>()).add(name);
       reservedNames.add(name);
     }
   }
diff --git a/src/main/java/com/android/tools/r8/utils/LineNumberOptimizer.java b/src/main/java/com/android/tools/r8/utils/LineNumberOptimizer.java
index 933f4fb..c7324da 100644
--- a/src/main/java/com/android/tools/r8/utils/LineNumberOptimizer.java
+++ b/src/main/java/com/android/tools/r8/utils/LineNumberOptimizer.java
@@ -303,6 +303,10 @@
           // deterministic behaviour: the algorithm will assign new line numbers in this order.
           // Methods with different names can share the same line numbers, that's why they don't
           // need to be sorted.
+          // If we are compiling to DEX we will try to not generate overloaded names. This saves
+          // space by allowing more debug-information to be canonicalized. If we have overloaded
+          // methods, we either did not rename them, we renamed them according to a supplied map or
+          // they may be bridges for interface methods with covariant return types.
           sortMethods(methods);
         }
 
diff --git a/src/test/java/com/android/tools/r8/TestRunResult.java b/src/test/java/com/android/tools/r8/TestRunResult.java
index e1ebfa2..bbc9d4e 100644
--- a/src/test/java/com/android/tools/r8/TestRunResult.java
+++ b/src/test/java/com/android/tools/r8/TestRunResult.java
@@ -129,9 +129,14 @@
     return new CodeInspector(app);
   }
 
-  public RR inspect(Consumer<CodeInspector> consumer)
+  public RR inspect(ThrowingConsumer<CodeInspector, NoSuchMethodException> consumer)
       throws IOException, ExecutionException {
-    consumer.accept(inspector());
+    CodeInspector inspector = inspector();
+    try {
+      consumer.accept(inspector);
+    } catch (NoSuchMethodException exception) {
+      throw new RuntimeException(exception);
+    }
     return self();
   }
 
diff --git a/src/test/java/com/android/tools/r8/cf/bootstrap/BootstrapCurrentEqualityTest.java b/src/test/java/com/android/tools/r8/cf/bootstrap/BootstrapCurrentEqualityTest.java
index 0ba8510..ddb0608 100644
--- a/src/test/java/com/android/tools/r8/cf/bootstrap/BootstrapCurrentEqualityTest.java
+++ b/src/test/java/com/android/tools/r8/cf/bootstrap/BootstrapCurrentEqualityTest.java
@@ -64,7 +64,7 @@
   private static Pair<Path, Path> r8R8Release;
 
   private final TestParameters parameters;
-  private static boolean testExternal = true;
+  private static boolean testExternal = false;
 
   @ClassRule public static TemporaryFolder testFolder = new TemporaryFolder();
 
diff --git a/src/test/java/com/android/tools/r8/naming/CovariantReturnTypeInSubInterfaceTest.java b/src/test/java/com/android/tools/r8/naming/CovariantReturnTypeInSubInterfaceTest.java
index 39747f0..8c50aa7 100644
--- a/src/test/java/com/android/tools/r8/naming/CovariantReturnTypeInSubInterfaceTest.java
+++ b/src/test/java/com/android/tools/r8/naming/CovariantReturnTypeInSubInterfaceTest.java
@@ -6,119 +6,106 @@
 import static com.android.tools.r8.utils.codeinspector.Matchers.isRenamed;
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
 
-import com.android.tools.r8.OutputMode;
 import com.android.tools.r8.TestBase;
-import com.android.tools.r8.ToolHelper;
-import com.android.tools.r8.ToolHelper.ProcessResult;
-import com.android.tools.r8.VmTestRunner;
-import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
-import com.google.common.collect.ImmutableList;
-import java.nio.file.Path;
-import java.util.List;
 import org.junit.Test;
 import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
 
-interface SuperInterface {
-  Super foo();
-}
-
-interface SubInterface extends SuperInterface {
-  @Override
-  Sub foo();
-}
-
-class Super {
-  protected int bar() {
-    return 0;
-  }
-}
-
-class Sub extends Super {
-  @Override
-  protected int bar() {
-    return 1;
-  }
-}
-
-class SuperImplementer implements SuperInterface {
-  @Override
-  public Super foo() {
-    return new Sub();
-  }
-}
-
-class SubImplementer extends SuperImplementer implements SubInterface {
-  @Override
-  public Sub foo() {
-    return (Sub) super.foo();
-  }
-}
-
-class TestMain {
-  public static void main(String[] args) {
-    SubImplementer subImplementer = new SubImplementer();
-    Super sup = subImplementer.foo();
-    System.out.print(sup.bar());
-  }
-}
-
-@RunWith(VmTestRunner.class)
+@RunWith(Parameterized.class)
 public class CovariantReturnTypeInSubInterfaceTest extends TestBase {
 
+  interface SuperInterface {
+    Super foo();
+  }
+
+  interface SubInterface extends SuperInterface {
+    @Override
+    Sub foo();
+  }
+
+  static class Super {
+    protected int bar() {
+      return 0;
+    }
+  }
+
+  static class Sub extends Super {
+    @Override
+    protected int bar() {
+      return 1;
+    }
+  }
+
+  static class SuperImplementer implements SuperInterface {
+    @Override
+    public Super foo() {
+      return new Sub();
+    }
+  }
+
+  static class SubImplementer extends SuperImplementer implements SubInterface {
+    @Override
+    public Sub foo() {
+      return (Sub) super.foo();
+    }
+  }
+
+  static class TestMain {
+    public static void main(String[] args) {
+      SubImplementer subImplementer = new SubImplementer();
+      Super sup = subImplementer.foo();
+      System.out.print(sup.bar());
+    }
+  }
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public CovariantReturnTypeInSubInterfaceTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
   private void test(boolean overloadAggressively) throws Exception {
-    String mainName = TestMain.class.getCanonicalName();
-    String aggressive =
-        overloadAggressively ? "-overloadaggressively" : "# Not overload aggressively";
-    List<String> config = ImmutableList.of(
-        "-printmapping",
-        aggressive,
-        "-keep class " + mainName + " {",
-        "  public void main(...);",
-        "}",
-        "-keep,allowobfuscation class **.Super* {",
-        "  <methods>;",
-        "}",
-        "-keep,allowobfuscation class **.Sub* {",
-        "  <methods>;",
-        "}"
-    );
-    AndroidApp app = readClasses(
-        SuperInterface.class,
-        SubInterface.class,
-        Super.class,
-        Sub.class,
-        SuperImplementer.class,
-        SubImplementer.class,
-        TestMain.class
-    );
-    AndroidApp processedApp =
-        compileWithR8(app, String.join(System.lineSeparator(), config), options -> {
-          options.enableInlining = false;
-        });
-    CodeInspector inspector = new CodeInspector(processedApp);
+    testForR8(parameters.getBackend())
+        .addInnerClasses(CovariantReturnTypeInSubInterfaceTest.class)
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMainRule(TestMain.class)
+        .addKeepRules(
+            "-keep,allowobfuscation class **.*$Super* { <methods>; }",
+            "-keep,allowobfuscation class **.*$Sub* { <methods>; }",
+            overloadAggressively ? "-overloadaggressively" : "# Not overload aggressively")
+        .addOptionsModification(internalOptions -> internalOptions.enableInlining = false)
+        .run(parameters.getRuntime(), TestMain.class)
+        .inspect(inspector -> inspect(inspector, overloadAggressively));
+  }
+
+  private void inspect(CodeInspector inspector, boolean overloadAggressively)
+      throws NoSuchMethodException {
     ClassSubject superInterface = inspector.clazz(SuperInterface.class);
     assertThat(superInterface, isRenamed());
-    MethodSubject foo1 = superInterface.method(
-        Super.class.getCanonicalName(), "foo", ImmutableList.of());
+    MethodSubject foo1 = superInterface.uniqueMethodWithName("foo");
     assertThat(foo1, isRenamed());
     ClassSubject subInterface = inspector.clazz(SubInterface.class);
     assertThat(subInterface, isRenamed());
-    MethodSubject foo2 = subInterface.method(
-        Sub.class.getCanonicalName(), "foo", ImmutableList.of());
+    MethodSubject foo2 = subInterface.method(SubInterface.class.getDeclaredMethod("foo"));
     assertThat(foo2, isRenamed());
-    assertEquals(foo1.getFinalName(), foo2.getFinalName());
-
-    ProcessResult javaResult = ToolHelper.runJava(ToolHelper.getClassPathForTests(), mainName);
-    assertEquals(0, javaResult.exitCode);
-    Path outDex = temp.getRoot().toPath().resolve("dex.zip");
-    processedApp.writeToZip(outDex, OutputMode.DexIndexed);
-    ProcessResult artResult = ToolHelper.runArtNoVerificationErrorsRaw(outDex.toString(), mainName);
-    assertEquals(0, artResult.exitCode);
-    assertEquals(javaResult.stdout, artResult.stdout);
+    if (overloadAggressively && parameters.isDexRuntime()) {
+      assertNotEquals(foo1.getFinalName(), foo2.getFinalName());
+    } else {
+      assertEquals(foo1.getFinalName(), foo2.getFinalName());
+    }
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/naming/CovariantReturnTypeTest.java b/src/test/java/com/android/tools/r8/naming/CovariantReturnTypeTest.java
index 1303232..6cb9837 100644
--- a/src/test/java/com/android/tools/r8/naming/CovariantReturnTypeTest.java
+++ b/src/test/java/com/android/tools/r8/naming/CovariantReturnTypeTest.java
@@ -87,6 +87,6 @@
         minifiedMethodNames.add(methodSubject.getFinalName());
       }
     }
-    assertEquals(3, minifiedMethodNames.size());
+    assertEquals(9, minifiedMethodNames.size());
   }
 }
diff --git a/src/test/java/com/android/tools/r8/naming/MethodNameMinificationPrivateNamedLastTest.java b/src/test/java/com/android/tools/r8/naming/MethodNameMinificationPrivateNamedLastTest.java
deleted file mode 100644
index 301fe07..0000000
--- a/src/test/java/com/android/tools/r8/naming/MethodNameMinificationPrivateNamedLastTest.java
+++ /dev/null
@@ -1,151 +0,0 @@
-// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-
-package com.android.tools.r8.naming;
-
-import static junit.framework.TestCase.assertEquals;
-import static org.hamcrest.MatcherAssert.assertThat;
-import static org.hamcrest.core.AnyOf.anyOf;
-import static org.hamcrest.core.Is.is;
-
-import com.android.tools.r8.CompilationFailedException;
-import com.android.tools.r8.NeverInline;
-import com.android.tools.r8.NeverMerge;
-import com.android.tools.r8.TestBase;
-import com.android.tools.r8.TestParameters;
-import com.android.tools.r8.TestParametersCollection;
-import com.android.tools.r8.utils.StringUtils;
-import com.android.tools.r8.utils.codeinspector.ClassSubject;
-import java.io.IOException;
-import java.util.concurrent.ExecutionException;
-import org.hamcrest.core.AnyOf;
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.Parameterized;
-
-/**
- * MethodNameMinificationPrivateNamedLastTest tests that private methods are named after public
- * methods. Private methods can be named freely and should not influence how public methods are
- * named.
- */
-@RunWith(Parameterized.class)
-public class MethodNameMinificationPrivateNamedLastTest extends TestBase {
-
-  public static final String EXPECTED_OUTPUT =
-      StringUtils.lines("A.m1", "A.m2", "B.m1", "B.m2", "B.m3", "C.m1", "C.m2", "C.m3", "C.m4");
-
-  @NeverMerge
-  public static class A {
-
-    @NeverInline
-    public void m1() {
-      System.out.println("A.m1");
-      m2();
-    }
-
-    @NeverInline
-    private void m2() {
-      System.out.println("A.m2");
-    }
-  }
-
-  @NeverMerge
-  public static class B extends A {
-
-    @NeverInline
-    public void m1() {
-      System.out.println("B.m1");
-      m2();
-    }
-
-    @NeverInline
-    private void m2() {
-      System.out.println("B.m2");
-    }
-
-    @NeverInline
-    public void m3() {
-      System.out.println("B.m3");
-    }
-  }
-
-  @NeverMerge
-  public static class C extends B {
-
-    @NeverInline
-    public void m1() {
-      System.out.println("C.m1");
-      m2();
-    }
-
-    @NeverInline
-    private void m2() {
-      System.out.println("C.m2");
-    }
-
-    @NeverInline
-    public void m3() {
-      System.out.println("C.m3");
-      m4();
-    }
-
-    @NeverInline
-    private void m4() {
-      System.out.println("C.m4");
-    }
-  }
-
-  public static class Runner {
-
-    public static void main(String[] args) {
-      A a = new A();
-      a.m1();
-      B b = new B();
-      b.m1();
-      b.m3();
-      C c = new C();
-      c.m1();
-      c.m3();
-    }
-  }
-
-  private TestParameters parameters;
-
-  @Parameterized.Parameters(name = "{0}")
-  public static TestParametersCollection data() {
-    return getTestParameters().withAllRuntimes().build();
-  }
-
-  public MethodNameMinificationPrivateNamedLastTest(TestParameters parameters) {
-    this.parameters = parameters;
-  }
-
-  @Test
-  public void testInheritedNamingState()
-      throws IOException, CompilationFailedException, ExecutionException {
-    testForR8(parameters.getBackend())
-        .addInnerClasses(MethodNameMinificationPrivateNamedLastTest.class)
-        .enableMergeAnnotations()
-        .enableInliningAnnotations()
-        .addKeepMainRule(Runner.class)
-        .setMinApi(parameters.getRuntime())
-        .compile()
-        .run(parameters.getRuntime(), Runner.class)
-        .assertSuccessWithOutput(EXPECTED_OUTPUT)
-        .inspect(
-            inspector -> {
-              assertEquals("a", inspector.clazz(A.class).uniqueMethodWithName("m1").getFinalName());
-              assertEquals("b", inspector.clazz(A.class).uniqueMethodWithName("m2").getFinalName());
-              assertEquals("a", inspector.clazz(B.class).uniqueMethodWithName("m1").getFinalName());
-              assertEquals("c", inspector.clazz(B.class).uniqueMethodWithName("m2").getFinalName());
-              assertEquals("b", inspector.clazz(B.class).uniqueMethodWithName("m3").getFinalName());
-              ClassSubject cSubject = inspector.clazz(C.class);
-              assertEquals("a", cSubject.uniqueMethodWithName("m1").getFinalName());
-              assertEquals("b", cSubject.uniqueMethodWithName("m3").getFinalName());
-              AnyOf<String> cPrivateNamesP = anyOf(is("c"), is("d"));
-              assertThat(cSubject.uniqueMethodWithName("m2").getFinalName(), cPrivateNamesP);
-              assertThat(cSubject.uniqueMethodWithName("m4").getFinalName(), cPrivateNamesP);
-            });
-  }
-}
diff --git a/src/test/java/com/android/tools/r8/naming/OverloadUniqueNameTest.java b/src/test/java/com/android/tools/r8/naming/OverloadUniqueNameTest.java
new file mode 100644
index 0000000..6d9f975
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/naming/OverloadUniqueNameTest.java
@@ -0,0 +1,205 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.naming;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static junit.framework.TestCase.assertEquals;
+import static junit.framework.TestCase.assertTrue;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.transformers.ClassTransformer;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.FoundMethodSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import java.io.IOException;
+import java.lang.reflect.Method;
+import java.util.HashSet;
+import java.util.Set;
+import java.util.concurrent.ExecutionException;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+import org.objectweb.asm.MethodVisitor;
+
+@RunWith(Parameterized.class)
+public class OverloadUniqueNameTest extends TestBase {
+
+  public static class A {
+    public void foo(int i) {}
+
+    public void foo(Object o) {}
+  }
+
+  public static class B extends A {
+
+    // This is here to ensure that foo is not visited first when iterating sorted methods.
+    public void baz(int i) {}
+
+    // This is an override, so it needs to have the same name as A.foo(int).
+    @Override
+    public void foo(int i) {}
+
+    public void foo(boolean b) {}
+
+    public void foo(int i, int j) {}
+
+    private void foo(char c) {}
+
+    private static void foo(String s) {}
+  }
+
+  private interface I1 {
+
+    void foo(long l);
+  }
+
+  private interface I2 {
+
+    void bar(long l);
+
+    void foo(long l);
+  }
+
+  public static class C extends B implements I1, I2 {
+
+    @Override
+    public void bar(long l) {}
+
+    @Override
+    // This method should be named according to I1.foo() and I2.foo().
+    public void foo(long l) {}
+
+    @Override
+    public void foo(int i) {}
+  }
+
+  private interface I3 {
+    void foo(long l);
+  }
+
+  private interface I4 extends I3 {
+    @Override
+    void foo(long l);
+  }
+
+  public static class LambdaTest {
+
+    public static void lambdaInterface() {
+      I1 lambda = ((I1 & I3) l -> {});
+    }
+  }
+
+  public static class ReturnType {
+
+    int foo() { // <-- changed to int foo() to test overloading on return type
+      System.out.println("int foo();");
+      return 0;
+    }
+
+    void rewrite(int dummy) {
+      System.out.println("void foo();");
+    }
+  }
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  public OverloadUniqueNameTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws CompilationFailedException, IOException, ExecutionException {
+    testForR8(Backend.DEX)
+        .addProgramClasses(
+            A.class, B.class, I1.class, I2.class, C.class, I3.class, I4.class, LambdaTest.class)
+        .addKeepAllClassesRuleWithAllowObfuscation()
+        .compile()
+        .inspect(
+            codeInspector -> {
+              inspectUniqueMethodsInClass(codeInspector, I1.class);
+              inspectUniqueMethodsInClass(codeInspector, I2.class);
+              inspectUniqueMethodsInClass(codeInspector, I3.class);
+              inspectUniqueMethodsInClass(codeInspector, I4.class);
+              inspectUniqueMethodsInClass(codeInspector, A.class);
+              inspectUniqueMethodsInClass(codeInspector, B.class);
+              inspectUniqueMethodsInClass(codeInspector, C.class);
+
+              // Ensure that virtual overrides in the class hierarchy has the same name.
+              final MethodSubject aFoo = codeInspector.clazz(A.class).method("void", "foo", "int");
+              final MethodSubject bFoo = codeInspector.clazz(B.class).method("void", "foo", "int");
+              assertEquals(aFoo.getFinalName(), bFoo.getFinalName());
+              final MethodSubject cFoo = codeInspector.clazz(C.class).method("void", "foo", "int");
+              assertEquals(aFoo.getFinalName(), cFoo.getFinalName());
+
+              // Ensure that all SAM interfaces has same method name.
+              final MethodSubject i1Foo = codeInspector.clazz(I1.class).uniqueMethodWithName("foo");
+              final MethodSubject i2Foo = codeInspector.clazz(I2.class).uniqueMethodWithName("foo");
+              assertEquals(i1Foo.getFinalName(), i2Foo.getFinalName());
+              final MethodSubject i3Foo = codeInspector.clazz(I3.class).uniqueMethodWithName("foo");
+              assertEquals(i1Foo.getFinalName(), i3Foo.getFinalName());
+
+              // Ensure C has the correct name for the interface method.
+              final MethodSubject cIFoo =
+                  codeInspector.clazz(C.class).method("void", "foo", "long");
+              assertEquals(cIFoo.getFinalName(), i1Foo.getFinalName());
+
+              // Ensure that I4.foo(int) has the same name as I3.foo(int).
+              final MethodSubject i4Foo = codeInspector.clazz(I4.class).uniqueMethodWithName("foo");
+              assertEquals(i3Foo.getFinalName(), i4Foo.getFinalName());
+            });
+  }
+
+  @Test
+  public void testReturnType() throws IOException, CompilationFailedException, ExecutionException {
+    testForR8(Backend.DEX)
+        .addProgramClassFileData(
+            transformer(ReturnType.class)
+                .addClassTransformer(
+                    new ClassTransformer() {
+                      @Override
+                      public MethodVisitor visitMethod(
+                          int access,
+                          String name,
+                          String descriptor,
+                          String signature,
+                          String[] exceptions) {
+                        if (name.equals("rewrite")) {
+                          return super.visitMethod(access, "foo", "()V", signature, exceptions);
+                        }
+                        return super.visitMethod(access, name, descriptor, signature, exceptions);
+                      }
+                    })
+                .transform())
+        .addKeepAllClassesRuleWithAllowObfuscation()
+        .compile()
+        .inspect(
+            codeInspector -> {
+              Set<String> seenMethodNames = new HashSet<>();
+              for (FoundMethodSubject method : codeInspector.clazz(ReturnType.class).allMethods()) {
+                assertTrue(seenMethodNames.add(method.getFinalName()));
+              }
+            });
+  }
+
+  private void inspectUniqueMethodsInClass(CodeInspector inspector, Class<?> clazz) {
+    Set<String> newNames = new HashSet<>();
+    for (Method method : clazz.getDeclaredMethods()) {
+      final MethodSubject methodSubject = inspector.method(method);
+      assertThat(methodSubject, isPresent());
+      assertTrue(methodSubject.isRenamed());
+      assertTrue(newNames.add(methodSubject.getFinalName()));
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/naming/overloadaggressively/OverloadAggressivelyTest.java b/src/test/java/com/android/tools/r8/naming/overloadaggressively/OverloadAggressivelyTest.java
index e034df6..ff61668 100644
--- a/src/test/java/com/android/tools/r8/naming/overloadaggressively/OverloadAggressivelyTest.java
+++ b/src/test/java/com/android/tools/r8/naming/overloadaggressively/OverloadAggressivelyTest.java
@@ -7,6 +7,7 @@
 import static org.junit.Assert.assertNotEquals;
 import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertTrue;
+import static org.junit.Assume.assumeTrue;
 
 import com.android.tools.r8.R8Command;
 import com.android.tools.r8.TestBase;
@@ -214,6 +215,7 @@
 
   @Test
   public void testMethodResolution_aggressively() throws Exception {
+    assumeTrue(backend == Backend.CF);
     methodResolution(true);
   }
 
diff --git a/src/test/java/com/android/tools/r8/naming/overloadaggressively/ValidNameConflictTest.java b/src/test/java/com/android/tools/r8/naming/overloadaggressively/ValidNameConflictTest.java
index eade0a5..3d9645d 100644
--- a/src/test/java/com/android/tools/r8/naming/overloadaggressively/ValidNameConflictTest.java
+++ b/src/test/java/com/android/tools/r8/naming/overloadaggressively/ValidNameConflictTest.java
@@ -93,7 +93,8 @@
                 "  invokevirtual java/lang/Class/getDeclaredFields()[Ljava/lang/reflect/Field;"),
             ImmutableList.of(
                 "  aconst_null",
-                "  invokevirtual java/lang/reflect/Field/get(Ljava/lang/Object;)Ljava/lang/Object;")));
+                "  invokevirtual"
+                    + " java/lang/reflect/Field/get(Ljava/lang/Object;)Ljava/lang/Object;")));
     return builder;
   }
 
@@ -266,7 +267,7 @@
     MethodSubject m2 = clazz.method("java.lang.Object", REPEATED_NAME, ImmutableList.of());
     assertTrue(m2.isPresent());
     assertTrue(m2.isRenamed());
-    assertEquals(m1.getFinalName(), m2.getFinalName());
+    assertNotEquals(m1.getFinalName(), m2.getFinalName());
 
     ProcessResult output = runRaw(app, CLASS_NAME);
     assertEquals(0, output.exitCode);
@@ -296,7 +297,11 @@
     MethodSubject m2 = clazz.method("java.lang.Object", REPEATED_NAME, ImmutableList.of());
     assertTrue(m2.isPresent());
     assertTrue(m2.isRenamed());
-    assertEquals(m1.getFinalName(), m2.getFinalName());
+    if (backend == Backend.DEX) {
+      assertNotEquals(m1.getFinalName(), m2.getFinalName());
+    } else {
+      assertEquals(m1.getFinalName(), m2.getFinalName());
+    }
 
     ProcessResult output = runRaw(app, CLASS_NAME);
     assertEquals(0, output.exitCode);
@@ -410,7 +415,7 @@
     MethodSubject m2 = sup.method("java.lang.Object", REPEATED_NAME, ImmutableList.of());
     assertTrue(m2.isPresent());
     assertTrue(m2.isRenamed());
-    assertEquals(m1.getFinalName(), m2.getFinalName());
+    assertNotEquals(m1.getFinalName(), m2.getFinalName());
 
     ClassSubject sub = codeInspector.clazz(ANOTHER_CLASS);
     assertTrue(sub.isPresent());
@@ -420,7 +425,7 @@
     MethodSubject subM2 = sub.method("java.lang.Object", REPEATED_NAME, ImmutableList.of());
     assertTrue(subM2.isPresent());
     assertTrue(subM2.isRenamed());
-    assertEquals(subM1.getFinalName(), subM2.getFinalName());
+    assertNotEquals(subM1.getFinalName(), subM2.getFinalName());
 
     // No matter what, overloading methods should be renamed to the same name.
     assertEquals(m1.getFinalName(), subM1.getFinalName());
@@ -455,7 +460,11 @@
     MethodSubject m2 = sup.method("java.lang.Object", REPEATED_NAME, ImmutableList.of());
     assertTrue(m2.isPresent());
     assertTrue(m2.isRenamed());
-    assertEquals(m1.getFinalName(), m2.getFinalName());
+    if (backend == Backend.DEX) {
+      assertNotEquals(m1.getFinalName(), m2.getFinalName());
+    } else {
+      assertEquals(m1.getFinalName(), m2.getFinalName());
+    }
 
     ClassSubject sub = codeInspector.clazz(ANOTHER_CLASS);
     assertTrue(sub.isPresent());
@@ -465,7 +474,11 @@
     MethodSubject subM2 = sub.method("java.lang.Object", REPEATED_NAME, ImmutableList.of());
     assertTrue(subM2.isPresent());
     assertTrue(subM2.isRenamed());
-    assertEquals(subM1.getFinalName(), subM2.getFinalName());
+    if (backend == Backend.DEX) {
+      assertNotEquals(subM1.getFinalName(), subM2.getFinalName());
+    } else {
+      assertEquals(subM1.getFinalName(), subM2.getFinalName());
+    }
 
     // No matter what, overloading methods should be renamed to the same name.
     assertEquals(m1.getFinalName(), subM1.getFinalName());
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/ClassSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/ClassSubject.java
index 705337c..d7f09cb 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/ClassSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/ClassSubject.java
@@ -74,6 +74,10 @@
     return method(returnType, name, ImmutableList.of());
   }
 
+  public MethodSubject method(String returnType, String name, String... parameters) {
+    return method(returnType, name, Arrays.asList(parameters));
+  }
+
   public abstract MethodSubject method(String returnType, String name, List<String> parameters);
 
   public abstract MethodSubject uniqueMethodWithName(String name);