Fixup method names without using global signature.

Change-Id: Ic1339245c19fde29f3dff7626edf6fbe63888407
diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java
index 443da46..45130dc 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -180,6 +180,10 @@
     return methodCollection.removeMethod(method);
   }
 
+  public void setDirectMethods(List<DexEncodedMethod> methods) {
+    setDirectMethods(methods.toArray(DexEncodedMethod.EMPTY_ARRAY));
+  }
+
   public void setDirectMethods(DexEncodedMethod[] methods) {
     methodCollection.setDirectMethods(methods);
   }
@@ -196,6 +200,10 @@
     methodCollection.addVirtualMethods(methods);
   }
 
+  public void setVirtualMethods(List<DexEncodedMethod> methods) {
+    setVirtualMethods(methods.toArray(DexEncodedMethod.EMPTY_ARRAY));
+  }
+
   public void setVirtualMethods(DexEncodedMethod[] methods) {
     methodCollection.setVirtualMethods(methods);
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index 85043c4..c353e8a 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -599,6 +599,14 @@
     return accessFlags.isSynthetic();
   }
 
+  public boolean belongsToDirectPool() {
+    return accessFlags.isStatic() || accessFlags.isPrivate() || accessFlags.isConstructor();
+  }
+
+  public boolean belongsToVirtualPool() {
+    return !belongsToDirectPool();
+  }
+
   @Override
   public KotlinMethodLevelInfo getKotlinMemberInfo() {
     return kotlinMemberInfo;
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index 8769114..6edd1e1 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -1780,7 +1780,7 @@
    *
    * @param tryString callback to check if the method name is in use.
    */
-  public <T extends DexMember<?, ?>> T createFreshMember(
+  public <T> T createFreshMember(
       Function<DexString, Optional<T>> tryString, String baseName, DexType holder) {
     int index = 0;
     while (true) {
@@ -1841,19 +1841,40 @@
       DexProto proto,
       DexType target,
       Predicate<DexMethod> isFresh) {
-    DexMethod method =
-        createFreshMember(
-            name -> {
-              DexMethod tryMethod = createMethod(target, proto, name);
-              if (isFresh.test(tryMethod)) {
-                return Optional.of(tryMethod);
-              } else {
-                return Optional.empty();
-              }
-            },
-            baseName,
-            holder);
-    return method;
+    return createFreshMember(
+        name -> {
+          DexMethod tryMethod = createMethod(target, proto, name);
+          if (isFresh.test(tryMethod)) {
+            return Optional.of(tryMethod);
+          } else {
+            return Optional.empty();
+          }
+        },
+        baseName,
+        holder);
+  }
+
+  /**
+   * Tries to find a method name for insertion into the class {@code target} of the form
+   * baseName$holder$n, where {@code baseName} and {@code holder} are supplied by the user, and
+   * {@code n} is picked to be the first number so that {@code isFresh.apply(method)} returns {@code
+   * true}.
+   *
+   * @param holder indicates where the method originates from.
+   */
+  public DexMethodSignature createFreshMethodSignatureName(
+      String baseName, DexType holder, DexProto proto, Predicate<DexMethodSignature> isFresh) {
+    return createFreshMember(
+        name -> {
+          DexMethodSignature trySignature = new DexMethodSignature(proto, name);
+          if (isFresh.test(trySignature)) {
+            return Optional.of(trySignature);
+          } else {
+            return Optional.empty();
+          }
+        },
+        baseName,
+        holder);
   }
 
   /**
diff --git a/src/main/java/com/android/tools/r8/graph/DexMember.java b/src/main/java/com/android/tools/r8/graph/DexMember.java
index 5c34e83..3041e01 100644
--- a/src/main/java/com/android/tools/r8/graph/DexMember.java
+++ b/src/main/java/com/android/tools/r8/graph/DexMember.java
@@ -27,6 +27,11 @@
   public abstract boolean match(D entry);
 
   @Override
+  public DexType getContextType() {
+    return holder;
+  }
+
+  @Override
   public boolean isDexMember() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexMethodSignature.java b/src/main/java/com/android/tools/r8/graph/DexMethodSignature.java
index cd77968..8b2fcc4 100644
--- a/src/main/java/com/android/tools/r8/graph/DexMethodSignature.java
+++ b/src/main/java/com/android/tools/r8/graph/DexMethodSignature.java
@@ -29,12 +29,20 @@
     return name;
   }
 
+  public DexMethodSignature withName(DexString name) {
+    return new DexMethodSignature(proto, name);
+  }
+
+  public DexMethodSignature withProto(DexProto proto) {
+    return new DexMethodSignature(proto, name);
+  }
+
   public DexMethod withHolder(ProgramDefinition definition, DexItemFactory dexItemFactory) {
     return withHolder(definition.getContextType(), dexItemFactory);
   }
 
-  public DexMethod withHolder(DexType holder, DexItemFactory dexItemFactory) {
-    return dexItemFactory.createMethod(holder, proto, name);
+  public DexMethod withHolder(DexReference reference, DexItemFactory dexItemFactory) {
+    return dexItemFactory.createMethod(reference.getContextType(), proto, name);
   }
 
   @Override
@@ -49,4 +57,36 @@
   public int hashCode() {
     return Objects.hash(proto, name);
   }
+
+  public DexType getReturnType() {
+    return proto.returnType;
+  }
+
+  public int getArity() {
+    return proto.getArity();
+  }
+
+  @Override
+  public String toString() {
+    return "Method Signature " + name + " " + proto.toString();
+  }
+
+  private String toSourceString() {
+    return toSourceString(false);
+  }
+
+  private String toSourceString(boolean includeReturnType) {
+    StringBuilder builder = new StringBuilder();
+    if (includeReturnType) {
+      builder.append(getReturnType().toSourceString()).append(" ");
+    }
+    builder.append(name).append("(");
+    for (int i = 0; i < getArity(); i++) {
+      if (i != 0) {
+        builder.append(", ");
+      }
+      builder.append(proto.parameters.values[i].toSourceString());
+    }
+    return builder.append(")").toString();
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/DexProto.java b/src/main/java/com/android/tools/r8/graph/DexProto.java
index 1eefc66..333be20 100644
--- a/src/main/java/com/android/tools/r8/graph/DexProto.java
+++ b/src/main/java/com/android/tools/r8/graph/DexProto.java
@@ -45,6 +45,10 @@
     return parameters.values[index];
   }
 
+  public int getArity() {
+    return parameters.size();
+  }
+
   @Override
   public int computeHashCode() {
     return shorty.hashCode()
diff --git a/src/main/java/com/android/tools/r8/graph/DexReference.java b/src/main/java/com/android/tools/r8/graph/DexReference.java
index c60efe5..3263b6d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexReference.java
+++ b/src/main/java/com/android/tools/r8/graph/DexReference.java
@@ -29,6 +29,8 @@
 
   public abstract void collectIndexedItems(IndexedItemCollection indexedItems);
 
+  public abstract DexType getContextType();
+
   public boolean isDexType() {
     return false;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexType.java b/src/main/java/com/android/tools/r8/graph/DexType.java
index b1892bf..72e632d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -52,6 +52,11 @@
     this.descriptor = descriptor;
   }
 
+  @Override
+  public DexType getContextType() {
+    return this;
+  }
+
   public DexString getDescriptor() {
     return descriptor;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java b/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
index 37a46f0..301352a 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
@@ -19,13 +19,11 @@
   abstract boolean verify();
 
   boolean belongsToDirectPool(DexEncodedMethod method) {
-    return method.accessFlags.isStatic()
-        || method.accessFlags.isPrivate()
-        || method.accessFlags.isConstructor();
+    return method.belongsToDirectPool();
   }
 
   boolean belongsToVirtualPool(DexEncodedMethod method) {
-    return !belongsToDirectPool(method);
+    return method.belongsToVirtualPool();
   }
 
   // Collection methods.
diff --git a/src/main/java/com/android/tools/r8/graph/ProgramDefinition.java b/src/main/java/com/android/tools/r8/graph/ProgramDefinition.java
index e96d26c..6c5ff48 100644
--- a/src/main/java/com/android/tools/r8/graph/ProgramDefinition.java
+++ b/src/main/java/com/android/tools/r8/graph/ProgramDefinition.java
@@ -16,6 +16,8 @@
 
   DexDefinition getDefinition();
 
+  DexReference getReference();
+
   Origin getOrigin();
 
   default boolean isProgramClass() {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java
index 3d58e73..79913ff 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java
@@ -22,6 +22,7 @@
 import com.android.tools.r8.shaking.FieldAccessInfoCollectionModifier;
 import com.android.tools.r8.utils.MethodSignatureEquivalence;
 import com.google.common.base.Equivalence.Wrapper;
+import com.google.common.base.Predicates;
 import com.google.common.collect.Iterables;
 import it.unimi.dsi.fastutil.objects.Reference2IntMap;
 import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
@@ -48,6 +49,7 @@
   private final HorizontallyMergedClasses.Builder mergedClassesBuilder;
   private final FieldAccessInfoCollectionModifier.Builder fieldAccessChangesBuilder;
 
+  private final ClassMethodsBuilder classMethodsBuilder = new ClassMethodsBuilder();
   private final Reference2IntMap<DexType> classIdentifiers = new Reference2IntOpenHashMap<>();
   private final ClassStaticFieldsMerger classStaticFieldsMerger;
   private final Collection<VirtualMethodMerger> virtualMethodMergers;
@@ -99,31 +101,33 @@
     }
   }
 
-  void merge(DexProgramClass toMerge) {
-    if (!toMerge.isFinal()) {
-      target.getAccessFlags().demoteFromFinal();
-    }
+  void mergeDirectMethods(SyntheticArgumentClass syntheticArgumentClass) {
+    mergeDirectMethods(target);
+    toMergeGroup.forEach(this::mergeDirectMethods);
 
+    mergeConstructors(syntheticArgumentClass);
+  }
+
+  void mergeDirectMethods(DexProgramClass toMerge) {
     toMerge.forEachProgramDirectMethod(
         method -> {
           DexEncodedMethod definition = method.getDefinition();
           assert !definition.isClassInitializer();
 
           if (!definition.isInstanceInitializer()) {
-            DexMethod newMethod = renameMethod(method);
-            // TODO(b/165000217): Add all methods to `target` in one go using addDirectMethods().
-            target.addDirectMethod(definition.toTypeSubstitutedMethod(newMethod));
-            lensBuilder.moveMethod(definition.getReference(), newMethod);
+            DexMethod newMethod = method.getReference().withHolder(target.type, dexItemFactory);
+            if (!classMethodsBuilder.isFresh(newMethod)) {
+              newMethod = renameDirectMethod(method);
+            }
+            classMethodsBuilder.addDirectMethod(definition.toTypeSubstitutedMethod(newMethod));
+            if (definition.getReference() != newMethod) {
+              lensBuilder.moveMethod(definition.getReference(), newMethod);
+            }
           }
         });
 
-    classStaticFieldsMerger.addFields(toMerge);
-
     // Clear the members of the class to be merged since they have now been moved to the target.
-    toMerge.setVirtualMethods(null);
-    toMerge.setDirectMethods(null);
-    toMerge.setInstanceFields(null);
-    toMerge.setStaticFields(null);
+    toMerge.getMethodCollection().clearDirectMethods();
   }
 
   /**
@@ -131,26 +135,33 @@
    *
    * @param method The class the method originally belonged to.
    */
-  DexMethod renameMethod(ProgramMethod method) {
+  DexMethod renameDirectMethod(ProgramMethod method) {
+    assert method.getDefinition().belongsToDirectPool();
     return dexItemFactory.createFreshMethodName(
         method.getDefinition().method.name.toSourceString(),
         method.getHolderType(),
         method.getDefinition().proto(),
         target.type,
-        tryMethod -> target.lookupMethod(tryMethod) == null);
+        classMethodsBuilder::isFresh);
   }
 
   void mergeConstructors(SyntheticArgumentClass syntheticArgumentClass) {
-    for (ConstructorMerger merger : constructorMergers) {
-      merger.merge(
-          lensBuilder, fieldAccessChangesBuilder, classIdentifiers, syntheticArgumentClass);
-    }
+    constructorMergers.forEach(
+        merger ->
+            merger.merge(
+                classMethodsBuilder,
+                lensBuilder,
+                fieldAccessChangesBuilder,
+                classIdentifiers,
+                syntheticArgumentClass));
   }
 
   void mergeVirtualMethods() {
-    for (VirtualMethodMerger merger : virtualMethodMergers) {
-      merger.merge(lensBuilder, fieldAccessChangesBuilder, classIdentifiers);
-    }
+    virtualMethodMergers.forEach(
+        merger ->
+            merger.merge(
+                classMethodsBuilder, lensBuilder, fieldAccessChangesBuilder, classIdentifiers));
+    toMergeGroup.forEach(clazz -> clazz.getMethodCollection().clearVirtualMethods());
   }
 
   void appendClassIdField() {
@@ -166,20 +177,37 @@
   }
 
   void mergeStaticFields() {
+    toMergeGroup.forEach(classStaticFieldsMerger::addFields);
     classStaticFieldsMerger.merge(target);
+    toMergeGroup.forEach(clazz -> clazz.setStaticFields(null));
+  }
+
+  void fixFinal() {
+    if (Iterables.any(toMergeGroup, Predicates.not(DexProgramClass::isFinal))) {
+      target.accessFlags.demoteFromFinal();
+    }
+  }
+
+  void mergeInstanceFields() {
+    // TODO: support instance field merging
+    assert Iterables.all(toMergeGroup, clazz -> !clazz.hasInstanceFields());
+
+    // The target should only have the class id field.
+    assert target.instanceFields().size() == 1;
   }
 
   public void mergeGroup(SyntheticArgumentClass syntheticArgumentClass) {
+    fixFinal();
     appendClassIdField();
 
-    mergedClassesBuilder.addMergeGroup(target, toMergeGroup);
-    for (DexProgramClass clazz : toMergeGroup) {
-      merge(clazz);
-    }
-
-    mergeConstructors(syntheticArgumentClass);
     mergeVirtualMethods();
+    mergeDirectMethods(syntheticArgumentClass);
+    classMethodsBuilder.setClassMethods(target);
+
     mergeStaticFields();
+    mergeInstanceFields();
+
+    mergedClassesBuilder.addMergeGroup(target, toMergeGroup);
   }
 
   public static class Builder {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMethodsBuilder.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMethodsBuilder.java
new file mode 100644
index 0000000..2516cad
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMethodsBuilder.java
@@ -0,0 +1,44 @@
+// Copyright (c) 2020, 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.horizontalclassmerging;
+
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.google.common.collect.Sets;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Set;
+
+public class ClassMethodsBuilder {
+  private Set<DexMethod> reservedMethods = Sets.newIdentityHashSet();
+  private List<DexEncodedMethod> virtualMethods = new ArrayList<>();
+  private List<DexEncodedMethod> directMethods = new ArrayList<>();
+
+  public void addVirtualMethod(DexEncodedMethod virtualMethod) {
+    virtualMethods.add(virtualMethod);
+    boolean added = reservedMethods.add(virtualMethod.getReference());
+    assert added;
+  }
+
+  public void addDirectMethod(DexEncodedMethod directMethod) {
+    directMethods.add(directMethod);
+    boolean added = reservedMethods.add(directMethod.getReference());
+    assert added;
+  }
+
+  public boolean isFresh(DexMethod method) {
+    return !reservedMethods.contains(method);
+  }
+
+  public void setClassMethods(DexProgramClass clazz) {
+    assert virtualMethods.stream().allMatch(method -> method.holder() == clazz.type);
+    assert virtualMethods.stream().allMatch(method -> method.belongsToVirtualPool());
+    assert directMethods.stream().allMatch(method -> method.holder() == clazz.type);
+    assert directMethods.stream().allMatch(method -> method.belongsToDirectPool());
+    clazz.setVirtualMethods(virtualMethods);
+    clazz.setDirectMethods(directMethods);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorMerger.java
index f6127d9..d15ed7e 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorMerger.java
@@ -115,18 +115,15 @@
     return constructors.size() == 1;
   }
 
-  private DexMethod moveConstructor(DexEncodedMethod constructor) {
+  private DexMethod moveConstructor(
+      ClassMethodsBuilder classMethodsBuilder, DexEncodedMethod constructor) {
     DexMethod method =
         dexItemFactory.createFreshMethodName(
             "constructor",
             constructor.holder(),
             constructor.proto(),
             target.type,
-            tryMethod -> target.lookupMethod(tryMethod) == null);
-
-    if (constructor.holder() == target.type) {
-      target.removeMethod(constructor.getReference());
-    }
+            classMethodsBuilder::isFresh);
 
     DexEncodedMethod encodedMethod = constructor.toTypeSubstitutedMethod(method);
     encodedMethod.getMutableOptimizationInfo().markForceInline();
@@ -134,7 +131,8 @@
     encodedMethod.accessFlags.unsetPublic();
     encodedMethod.accessFlags.unsetProtected();
     encodedMethod.accessFlags.setPrivate();
-    target.addDirectMethod(encodedMethod);
+    classMethodsBuilder.addDirectMethod(encodedMethod);
+
     return method;
   }
 
@@ -146,6 +144,7 @@
 
   /** Synthesize a new method which selects the constructor based on a parameter type. */
   void merge(
+      ClassMethodsBuilder classMethodsBuilder,
       HorizontalClassMergerGraphLens.Builder lensBuilder,
       FieldAccessInfoCollectionModifier.Builder fieldAccessChangesBuilder,
       Reference2IntMap<DexType> classIdentifiers,
@@ -159,7 +158,7 @@
         classFileVersion =
             CfVersion.maxAllowNull(classFileVersion, constructor.getClassFileVersion());
       }
-      DexMethod movedConstructor = moveConstructor(constructor);
+      DexMethod movedConstructor = moveConstructor(classMethodsBuilder, constructor);
       lensBuilder.mapMethod(movedConstructor, movedConstructor);
       lensBuilder.mapMethodInverse(constructor.method, movedConstructor);
       typeConstructorClassMap.put(
@@ -169,9 +168,9 @@
     DexMethod methodReferenceTemplate = generateReferenceMethodTemplate();
     DexMethod newConstructorReference =
         dexItemFactory.createInstanceInitializerWithFreshProto(
-            methodReferenceTemplate,
+            methodReferenceTemplate.withHolder(target.type, dexItemFactory),
             syntheticArgumentClass.getArgumentClass(),
-            tryMethod -> target.lookupMethod(tryMethod) == null);
+            classMethodsBuilder::isFresh);
     int extraNulls = newConstructorReference.getArity() - methodReferenceTemplate.getArity();
 
     DexMethod representativeConstructorReference = constructors.iterator().next().method;
@@ -221,7 +220,7 @@
     lensBuilder.recordExtraOriginalSignature(
         representativeConstructorReference, newConstructorReference);
 
-    target.addDirectMethod(newConstructor);
+    classMethodsBuilder.addDirectMethod(newConstructor);
 
     fieldAccessChangesBuilder.fieldWrittenByMethod(classIdField, newConstructorReference);
   }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
index 45f2ed1..d353849 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
@@ -64,19 +64,14 @@
     Map<FieldMultiset, List<DexProgramClass>> classes = new LinkedHashMap<>();
 
     // Group classes by same field signature using the hash map.
-    List<DexProgramClass> classesWithDeterministicOrder =
-        appView.appInfo().classesWithDeterministicOrder();
-    for (DexProgramClass clazz : classesWithDeterministicOrder) {
+    for (DexProgramClass clazz : appView.appInfo().classesWithDeterministicOrder()) {
       classes.computeIfAbsent(new FieldMultiset(clazz), ignore -> new ArrayList<>()).add(clazz);
     }
 
     // Run the policies on all collected classes to produce a final grouping.
     Collection<List<DexProgramClass>> groups =
         new SimplePolicyExecutor()
-            .run(
-                classes.values(),
-                getPolicies(
-                    classesWithDeterministicOrder, mainDexTracingResult, runtimeTypeCheckInfo));
+            .run(classes.values(), getPolicies(mainDexTracingResult, runtimeTypeCheckInfo));
     // If there are no groups, then end horizontal class merging.
     if (groups.isEmpty()) {
       appView.setHorizontallyMergedClasses(HorizontallyMergedClasses.empty());
@@ -110,7 +105,6 @@
   }
 
   private List<Policy> getPolicies(
-      List<DexProgramClass> classesWithDeterministicOrder,
       MainDexTracingResult mainDexTracingResult,
       RuntimeTypeCheckInfo runtimeTypeCheckInfo) {
     return ImmutableList.of(
@@ -133,7 +127,7 @@
         new NotVerticallyMergedIntoSubtype(appView),
         new NoRuntimeTypeChecks(runtimeTypeCheckInfo),
         new NotEntryPoint(appView.dexItemFactory()),
-        new PreventMethodImplementation(appView, classesWithDeterministicOrder),
+        new PreventMethodImplementation(appView),
         new DontInlinePolicy(appView, mainDexTracingResult),
         new PreventMergeIntoMainDex(appView, mainDexTracingResult),
         new AllInstantiatedOrUninstantiated(appView),
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/SubtypingForrestForClasses.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/SubtypingForrestForClasses.java
index a82f470..05440b4 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/SubtypingForrestForClasses.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/SubtypingForrestForClasses.java
@@ -35,10 +35,9 @@
   private final Collection<DexProgramClass> roots = new ArrayList<>();
   private final Map<DexProgramClass, List<DexProgramClass>> subtypeMap = new IdentityHashMap<>();
 
-  public SubtypingForrestForClasses(
-      AppView<AppInfoWithLiveness> appView, List<DexProgramClass> classesWithDeterministicOrder) {
+  public SubtypingForrestForClasses(AppView<AppInfoWithLiveness> appView) {
     this.appView = appView;
-    calculateSubtyping(classesWithDeterministicOrder);
+    calculateSubtyping(appView.appInfo().classes());
   }
 
   private DexProgramClass superClass(DexProgramClass clazz) {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
index 8cf6265..a7ce343 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexMethodSignature;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexString;
@@ -19,15 +20,12 @@
 import com.android.tools.r8.shaking.AnnotationFixer;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.FieldAccessInfoCollectionModifier;
-import com.android.tools.r8.utils.MethodSignatureEquivalence;
 import com.android.tools.r8.utils.OptionalBool;
-import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
 import java.util.Collections;
-import java.util.HashMap;
 import java.util.IdentityHashMap;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -49,7 +47,7 @@
   private final DexItemFactory dexItemFactory;
   private final BiMap<DexMethod, DexMethod> movedMethods = HashBiMap.create();
   private final SyntheticArgumentClass syntheticArgumentClass;
-  private final BiMap<Wrapper<DexMethod>, Wrapper<DexMethod>> reservedInterfaceSignatures =
+  private final BiMap<DexMethodSignature, DexMethodSignature> reservedInterfaceSignatures =
       HashBiMap.create();
 
   public TreeFixer(
@@ -124,11 +122,10 @@
     Iterables.filter(classes, DexProgramClass::isInterface).forEach(this::fixupInterfaceClass);
 
     classes.forEach(this::fixupProgramClassSuperType);
-    SubtypingForrestForClasses subtypingForrest = new SubtypingForrestForClasses(appView, classes);
+    SubtypingForrestForClasses subtypingForrest = new SubtypingForrestForClasses(appView);
     // TODO(b/170078037): parallelize this code segment.
     for (DexProgramClass root : subtypingForrest.getProgramRoots()) {
-      subtypingForrest.traverseNodeDepthFirst(
-          root, new IdentityHashMap<>(), this::fixupProgramClass);
+      subtypingForrest.traverseNodeDepthFirst(root, HashBiMap.create(), this::fixupProgramClass);
     }
 
     lensBuilder.remapMethods(movedMethods);
@@ -143,28 +140,24 @@
     clazz.superType = fixupType(clazz.superType);
   }
 
-  private Map<Wrapper<DexMethod>, DexString> fixupProgramClass(
-      DexProgramClass clazz, Map<Wrapper<DexMethod>, DexString> remappedVirtualMethods) {
+  private BiMap<DexMethodSignature, DexMethodSignature> fixupProgramClass(
+      DexProgramClass clazz, BiMap<DexMethodSignature, DexMethodSignature> remappedVirtualMethods) {
     assert !clazz.isInterface();
 
     // TODO(b/169395592): ensure merged classes have been removed using:
     //   assert !mergedClasses.hasBeenMergedIntoDifferentType(clazz.type);
 
-    Map<Wrapper<DexMethod>, DexString> remappedClassVirtualMethods =
-        new HashMap<>(remappedVirtualMethods);
+    BiMap<DexMethodSignature, DexMethodSignature> remappedClassVirtualMethods =
+        HashBiMap.create(remappedVirtualMethods);
 
-    Set<DexMethod> newVirtualMethodReferences = Sets.newIdentityHashSet();
+    Set<DexMethodSignature> newMethodReferences = Sets.newHashSet();
     clazz
         .getMethodCollection()
         .replaceAllVirtualMethods(
-            method ->
-                fixupVirtualMethod(
-                    remappedClassVirtualMethods, newVirtualMethodReferences, method));
-
-    Set<DexMethod> newDirectMethodReferences = Sets.newIdentityHashSet();
+            method -> fixupVirtualMethod(remappedClassVirtualMethods, newMethodReferences, method));
     clazz
         .getMethodCollection()
-        .replaceAllDirectMethods(method -> fixupDirectMethod(newDirectMethodReferences, method));
+        .replaceAllDirectMethods(method -> fixupDirectMethod(newMethodReferences, method));
 
     fixupFields(clazz.staticFields(), clazz::setStaticField);
     fixupFields(clazz.instanceFields(), clazz::setInstanceField);
@@ -184,23 +177,19 @@
       return method;
     }
 
-    MethodSignatureEquivalence equivalence = MethodSignatureEquivalence.get();
-    Wrapper<DexMethod> originalMethodSignature = equivalence.wrap(originalMethodReference);
-    Wrapper<DexMethod> newMethodSignature =
+    DexMethodSignature originalMethodSignature = originalMethodReference.getSignature();
+    DexMethodSignature newMethodSignature =
         reservedInterfaceSignatures.get(originalMethodSignature);
 
     if (newMethodSignature == null) {
-      newMethodSignature = equivalence.wrap(fixupMethodReference(originalMethodReference));
+      newMethodSignature = fixupMethodReference(originalMethodReference).getSignature();
 
       // If the signature is already reserved by another interface, find a fresh one.
       if (reservedInterfaceSignatures.containsValue(newMethodSignature)) {
         DexString name =
             dexItemFactory.createGloballyFreshMemberString(
                 originalMethodReference.getName().toSourceString());
-        newMethodSignature =
-            equivalence.wrap(
-                dexItemFactory.createMethod(
-                    newMethodSignature.get().holder, newMethodSignature.get().proto, name));
+        newMethodSignature = newMethodSignature.withName(name);
       }
 
       assert !reservedInterfaceSignatures.containsValue(newMethodSignature);
@@ -208,16 +197,14 @@
     }
 
     DexMethod newMethodReference =
-        newMethodSignature
-            .get()
-            .withHolder(originalMethodReference.getHolderType(), dexItemFactory);
+        newMethodSignature.withHolder(originalMethodReference, dexItemFactory);
     movedMethods.put(originalMethodReference, newMethodReference);
 
     return method.toTypeSubstitutedMethod(newMethodReference);
   }
 
   private void fixupInterfaceClass(DexProgramClass iface) {
-    Set<DexMethod> newDirectMethods = new LinkedHashSet<>();
+    Set<DexMethodSignature> newDirectMethods = new LinkedHashSet<>();
 
     assert iface.superType == dexItemFactory.objectType;
     iface.superType = mergedClasses.getMergeTargetOrDefault(iface.superType);
@@ -251,13 +238,14 @@
     return newMethod;
   }
 
-  private DexEncodedMethod fixupDirectMethod(Set<DexMethod> newMethods, DexEncodedMethod method) {
+  private DexEncodedMethod fixupDirectMethod(
+      Set<DexMethodSignature> newMethods, DexEncodedMethod method) {
     DexMethod originalMethodReference = method.getReference();
 
     // Fix all type references in the method prototype.
     DexMethod newMethodReference = fixupMethodReference(originalMethodReference);
 
-    if (newMethods.contains(newMethodReference)) {
+    if (newMethods.contains(newMethodReference.getSignature())) {
       // If the method collides with a direct method on the same class then rename it to a globally
       // fresh name and record the signature.
 
@@ -267,45 +255,44 @@
             dexItemFactory.createInstanceInitializerWithFreshProto(
                 newMethodReference,
                 syntheticArgumentClass.getArgumentClass(),
-                tryMethod -> !newMethods.contains(tryMethod));
+                tryMethod -> !newMethods.contains(tryMethod.getSignature()));
         int extraNulls = newMethodReference.getArity() - originalMethodReference.getArity();
         lensBuilder.addExtraParameters(
             originalMethodReference,
             Collections.nCopies(extraNulls, new ExtraUnusedNullParameter()));
       } else {
-        DexString newMethodName =
-            dexItemFactory.createGloballyFreshMemberString(
-                originalMethodReference.getName().toSourceString(), null);
         newMethodReference =
-            dexItemFactory.createMethod(
-                newMethodReference.holder, newMethodReference.proto, newMethodName);
+            dexItemFactory.createFreshMethodName(
+                newMethodReference.getName().toSourceString(),
+                null,
+                newMethodReference.proto,
+                newMethodReference.holder,
+                tryMethod ->
+                    !reservedInterfaceSignatures.containsValue(tryMethod.getSignature())
+                        && !newMethods.contains(tryMethod.getSignature()));
       }
     }
 
-    boolean changed = newMethods.add(newMethodReference);
+    boolean changed = newMethods.add(newMethodReference.getSignature());
     assert changed;
 
     return fixupProgramMethod(newMethodReference, method);
   }
 
-  private DexString lookupReservedVirtualName(
+  private DexMethodSignature lookupReservedVirtualName(
       DexMethod originalMethodReference,
-      Map<Wrapper<DexMethod>, DexString> renamedClassVirtualMethods) {
-    Wrapper<DexMethod> originalSignature =
-        MethodSignatureEquivalence.get().wrap(originalMethodReference);
+      BiMap<DexMethodSignature, DexMethodSignature> renamedClassVirtualMethods) {
+    DexMethodSignature originalSignature = originalMethodReference.getSignature();
 
     // Determine if the original method has been rewritten by a parent class
-    DexString renamedVirtualName =
-        renamedClassVirtualMethods != null
-            ? renamedClassVirtualMethods.get(originalSignature)
-            : null;
+    DexMethodSignature renamedVirtualName = renamedClassVirtualMethods.get(originalSignature);
 
     if (renamedVirtualName == null) {
       // Determine if there is a signature mapping.
-      Wrapper<DexMethod> mappedInterfaceSignature =
+      DexMethodSignature mappedInterfaceSignature =
           reservedInterfaceSignatures.get(originalSignature);
       if (mappedInterfaceSignature != null) {
-        renamedVirtualName = mappedInterfaceSignature.get().name;
+        renamedVirtualName = mappedInterfaceSignature;
       }
     } else {
       assert !reservedInterfaceSignatures.containsKey(originalSignature);
@@ -315,51 +302,57 @@
   }
 
   private DexEncodedMethod fixupVirtualMethod(
-      Map<Wrapper<DexMethod>, DexString> renamedClassVirtualMethods,
-      Set<DexMethod> newMethods,
+      BiMap<DexMethodSignature, DexMethodSignature> renamedClassVirtualMethods,
+      Set<DexMethodSignature> newMethods,
       DexEncodedMethod method) {
     DexMethod originalMethodReference = method.getReference();
-    Wrapper<DexMethod> originalSignature =
-        MethodSignatureEquivalence.get().wrap(originalMethodReference);
+    DexMethodSignature originalSignature = originalMethodReference.getSignature();
 
-    DexString renamedVirtualName =
+    DexMethodSignature renamedVirtualName =
         lookupReservedVirtualName(originalMethodReference, renamedClassVirtualMethods);
 
     // Fix all type references in the method prototype.
-    DexMethod newMethodReference = fixupMethodReference(originalMethodReference);
-    Wrapper<DexMethod> newSignature = MethodSignatureEquivalence.get().wrap(newMethodReference);
+    DexMethodSignature newSignature = fixupMethodSignature(originalSignature);
 
     if (renamedVirtualName != null) {
       // If the method was renamed in a parent, rename it in the child.
-      newMethodReference = newMethodReference.withName(renamedVirtualName, dexItemFactory);
+      newSignature = renamedVirtualName;
 
-      assert !newMethods.contains(newMethodReference);
+      assert !newMethods.contains(newSignature);
     } else if (reservedInterfaceSignatures.containsValue(newSignature)
-        || newMethods.contains(newMethodReference)) {
+        || newMethods.contains(newSignature)
+        || renamedClassVirtualMethods.containsValue(newSignature)) {
       // If the method potentially collides with an interface method or with another virtual method
       // rename it to a globally fresh name and record the name.
 
-      DexString newMethodName =
-          dexItemFactory.createGloballyFreshMemberString(
-              originalMethodReference.getName().toSourceString(), null);
-      newMethodReference = newMethodReference.withName(newMethodName, dexItemFactory);
+      newSignature =
+          dexItemFactory.createFreshMethodSignatureName(
+              originalMethodReference.getName().toSourceString(),
+              null,
+              newSignature.getProto(),
+              trySignature ->
+                  !reservedInterfaceSignatures.containsValue(trySignature)
+                      && !newMethods.contains(trySignature)
+                      && !renamedClassVirtualMethods.containsValue(trySignature));
 
       // Record signature renaming so that subclasses perform the identical rename.
-      renamedClassVirtualMethods.put(originalSignature, newMethodReference.getName());
+      renamedClassVirtualMethods.put(originalSignature, newSignature);
     } else {
       // There was no reserved name and the new signature is available.
 
       if (Iterables.any(
-          newMethodReference.proto.getParameterBaseTypes(dexItemFactory),
+          newSignature.getProto().getParameterBaseTypes(dexItemFactory),
           mergedClasses::isMergeTarget)) {
         // If any of the parameter types have been merged, record the signature mapping.
-        renamedClassVirtualMethods.put(originalSignature, newMethodReference.getName());
+        renamedClassVirtualMethods.put(originalSignature, newSignature);
       }
     }
 
-    boolean changed = newMethods.add(newMethodReference);
+    boolean changed = newMethods.add(newSignature);
     assert changed;
 
+    DexMethod newMethodReference =
+        newSignature.withHolder(fixupType(originalMethodReference.holder), dexItemFactory);
     return fixupProgramMethod(newMethodReference, method);
   }
 
@@ -406,6 +399,10 @@
         .createMethod(fixupType(method.holder), fixupProto(method.proto), method.name);
   }
 
+  private DexMethodSignature fixupMethodSignature(DexMethodSignature signature) {
+    return signature.withProto(fixupProto(signature.getProto()));
+  }
+
   private DexProto fixupProto(DexProto proto) {
     DexProto result = protoFixupCache.get(proto);
     if (result == null) {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java
index 22f7456..07a3172 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java
@@ -92,11 +92,15 @@
     }
   }
 
-  public int getArity() {
-    return methods.iterator().next().getReference().getArity();
+  public DexMethod getMethodReference() {
+    return methods.iterator().next().getReference();
   }
 
-  private DexMethod moveMethod(ProgramMethod oldMethod) {
+  public int getArity() {
+    return getMethodReference().getArity();
+  }
+
+  private DexMethod moveMethod(ClassMethodsBuilder classMethodsBuilder, ProgramMethod oldMethod) {
     DexMethod oldMethodReference = oldMethod.getReference();
     DexMethod method =
         dexItemFactory.createFreshMethodName(
@@ -104,18 +108,14 @@
             oldMethod.getHolderType(),
             oldMethodReference.proto,
             target.type,
-            tryMethod -> target.lookupMethod(tryMethod) == null);
-
-    if (oldMethod.getHolderType() == target.type) {
-      target.removeMethod(oldMethod.getReference());
-    }
+            classMethodsBuilder::isFresh);
 
     DexEncodedMethod encodedMethod = oldMethod.getDefinition().toTypeSubstitutedMethod(method);
     MethodAccessFlags flags = encodedMethod.accessFlags;
     flags.unsetProtected();
     flags.unsetPublic();
     flags.setPrivate();
-    target.addDirectMethod(encodedMethod);
+    classMethodsBuilder.addDirectMethod(encodedMethod);
 
     return encodedMethod.method;
   }
@@ -129,24 +129,26 @@
     return flags;
   }
 
-
   /**
    * If there is only a single method that does not override anything then it is safe to just move
    * it to the target type if it is not already in it.
    */
-  public void mergeTrivial(HorizontalClassMergerGraphLens.Builder lensBuilder) {
-    ProgramMethod method = methods.iterator().next();
+  public void mergeTrivial(
+      ClassMethodsBuilder classMethodsBuilder, HorizontalClassMergerGraphLens.Builder lensBuilder) {
+    DexEncodedMethod method = methods.iterator().next().getDefinition();
 
     if (method.getHolderType() != target.type) {
       // If the method is not in the target type, move it and record it in the lens.
-      DexEncodedMethod newMethod =
-          method.getDefinition().toRenamedHolderMethod(target.type, dexItemFactory);
-      target.addVirtualMethod(newMethod);
-      lensBuilder.moveMethod(method.getReference(), newMethod.getReference());
+      DexMethod originalReference = method.getReference();
+      method = method.toRenamedHolderMethod(target.type, dexItemFactory);
+      lensBuilder.moveMethod(originalReference, method.getReference());
     }
+
+    classMethodsBuilder.addVirtualMethod(method);
   }
 
   public void merge(
+      ClassMethodsBuilder classMethodsBuilder,
       HorizontalClassMergerGraphLens.Builder lensBuilder,
       FieldAccessInfoCollectionModifier.Builder fieldAccessChangesBuilder,
       Reference2IntMap classIdentifiers) {
@@ -155,7 +157,7 @@
 
     // Handle trivial merges.
     if (superMethod == null && methods.size() == 1) {
-      mergeTrivial(lensBuilder);
+      mergeTrivial(classMethodsBuilder, lensBuilder);
       return;
     }
 
@@ -167,7 +169,7 @@
         CfVersion methodVersion = method.getDefinition().getClassFileVersion();
         classFileVersion = CfVersion.maxAllowNull(classFileVersion, methodVersion);
       }
-      DexMethod newMethod = moveMethod(method);
+      DexMethod newMethod = moveMethod(classMethodsBuilder, method);
       lensBuilder.mapMethod(newMethod, newMethod);
       lensBuilder.mapMethodInverse(method.getReference(), newMethod);
       classIdToMethodMap.put(classIdentifiers.getInt(method.getHolderType()), newMethod);
@@ -183,7 +185,7 @@
             null,
             originalMethodReference.proto,
             originalMethodReference.getHolderType(),
-            tryMethod -> target.lookupMethod(tryMethod) == null);
+            classMethodsBuilder::isFresh);
 
     DexMethod newMethodReference =
         dexItemFactory.createMethod(target.type, templateReference.proto, templateReference.name);
@@ -211,7 +213,7 @@
     }
     lensBuilder.recordExtraOriginalSignature(bridgeMethodReference, newMethodReference);
 
-    target.addVirtualMethod(newMethod);
+    classMethodsBuilder.addVirtualMethod(newMethod);
 
     fieldAccessChangesBuilder.fieldReadByMethod(classIdField, newMethod.method);
   }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/PreventMethodImplementation.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/PreventMethodImplementation.java
index 091f436..b8083e1 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/PreventMethodImplementation.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/PreventMethodImplementation.java
@@ -119,11 +119,9 @@
     }
   }
 
-  public PreventMethodImplementation(
-      AppView<AppInfoWithLiveness> appView, List<DexProgramClass> classesWithDeterministicOrder) {
+  public PreventMethodImplementation(AppView<AppInfoWithLiveness> appView) {
     this.appView = appView;
-    this.subtypingForrestForClasses =
-        new SubtypingForrestForClasses(appView, classesWithDeterministicOrder);
+    this.subtypingForrestForClasses = new SubtypingForrestForClasses(appView);
   }
 
   enum MethodCategory {
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index fb85079..a294f1d 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -1110,8 +1110,8 @@
       target.forEachField(feedback::markFieldCannotBeKept);
       target.forEachMethod(feedback::markMethodCannotBeKept);
       // Step 3: Clear the members of the source class since they have now been moved to the target.
-      source.setDirectMethods(null);
-      source.setVirtualMethods(null);
+      source.getMethodCollection().clearDirectMethods();
+      source.getMethodCollection().clearVirtualMethods();
       source.setInstanceFields(null);
       source.setStaticFields(null);
       // Step 4: Record merging.
diff --git a/src/main/java/com/android/tools/r8/utils/ObjectUtils.java b/src/main/java/com/android/tools/r8/utils/ObjectUtils.java
index ac07151..1f3ad9d 100644
--- a/src/main/java/com/android/tools/r8/utils/ObjectUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ObjectUtils.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.utils;
 
+import java.util.function.Function;
 import java.util.function.Predicate;
 
 public class ObjectUtils {
@@ -14,4 +15,11 @@
     }
     return orElse;
   }
+
+  public static <S, T> T mapNotNull(S object, Function<? super S, ? extends T> fn) {
+    if (object != null) {
+      return fn.apply(object);
+    }
+    return null;
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/StaticAndVirtualMethodCollisionTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/StaticAndVirtualMethodCollisionTest.java
index 52b506f..edca180 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/StaticAndVirtualMethodCollisionTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/StaticAndVirtualMethodCollisionTest.java
@@ -4,9 +4,6 @@
 
 package com.android.tools.r8.classmerging.horizontal;
 
-import static com.android.tools.r8.utils.codeinspector.AssertUtils.assertFailsCompilationIf;
-import static org.hamcrest.CoreMatchers.containsString;
-import static org.hamcrest.MatcherAssert.assertThat;
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
@@ -22,24 +19,18 @@
 
   @Test
   public void test() throws Exception {
-    // TODO(b/172415620): Handle static/virtual method collisions.
-    assertFailsCompilationIf(
-        enableHorizontalClassMerging,
-        () ->
-            testForR8(parameters.getBackend())
-                .addInnerClasses(getClass())
-                .addKeepMainRule(Main.class)
-                .addOptionsModification(
-                    options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
-                .addHorizontallyMergedClassesInspectorIf(
-                    enableHorizontalClassMerging,
-                    inspector -> inspector.assertMergedInto(B.class, A.class))
-                .enableInliningAnnotations()
-                .enableNeverClassInliningAnnotations()
-                .setMinApi(parameters.getApiLevel())
-                .run(parameters.getRuntime(), Main.class)
-                .assertSuccessWithOutputLines("A.foo()", "A.bar()", "B.foo()", "B.bar()"),
-        e -> assertThat(e.getCause().getMessage(), containsString("Duplicate method")));
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .addOptionsModification(
+            options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
+        .addHorizontallyMergedClassesInspectorIf(
+            enableHorizontalClassMerging, inspector -> inspector.assertMergedInto(B.class, A.class))
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("A.foo()", "A.bar()", "B.foo()", "B.bar()");
   }
 
   static class Main {
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/TreeFixerSubClassCollisionTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/TreeFixerSubClassCollisionTest.java
index e5c6561..aad0efa 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/TreeFixerSubClassCollisionTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/TreeFixerSubClassCollisionTest.java
@@ -36,7 +36,8 @@
         .enableNoHorizontalClassMergingAnnotations()
         .setMinApi(parameters.getApiLevel())
         .run(parameters.getRuntime(), Main.class)
-        .assertSuccessWithOutputLines("print a: foo c a", "print b: foo c b", "print b: foo d b")
+        .assertSuccessWithOutputLines(
+            "print a: foo c a", "print b: foo c b", "print b: foo c b", "print b: foo d b")
         .inspect(
             codeInspector -> {
               assertThat(codeInspector.clazz(A.class), isPresent());
@@ -45,15 +46,19 @@
 
               ClassSubject cClassSubject = codeInspector.clazz(C.class);
               assertThat(cClassSubject, isPresent());
-              // C#foo(B) is renamed to C#foo$2(A) to not collide with D#foo$1(A).
+              // C#foo(B) is renamed to C#foo$1(A).
               if (enableHorizontalClassMerging) {
                 assertThat(cClassSubject.uniqueMethodWithFinalName("foo"), isPresent());
-                assertThat(cClassSubject.uniqueMethodWithFinalName("foo$2"), isPresent());
+                assertThat(cClassSubject.uniqueMethodWithFinalName("foo$1"), isPresent());
               }
 
               ClassSubject dClassSubject = codeInspector.clazz(D.class);
               assertThat(dClassSubject, isPresent());
-              assertThat(dClassSubject.uniqueMethodWithFinalName("foo$1"), isPresent());
+              // D#foo$1(B) is renamed to D#foo$2(A).
+              assertThat(
+                  dClassSubject.uniqueMethodWithFinalName(
+                      enableHorizontalClassMerging ? "foo$1$1" : "foo$1"),
+                  isPresent());
             });
   }
 
@@ -104,6 +109,7 @@
       c.foo(a);
       c.foo(b);
       D d = new D();
+      d.foo(b);
       d.foo$1(b);
     }
   }