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 f98f9b8..0541d7e 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -292,6 +292,22 @@
     return result;
   }
 
+  public DexEncodedMethod[] directMethodsSorted() {
+    DexEncodedMethod[] result = new DexEncodedMethod[directMethods.length];
+    System.arraycopy(directMethods, 0, result, 0, directMethods.length);
+    Arrays.sort(
+        result, (DexEncodedMethod a, DexEncodedMethod b) -> a.method.slowCompareTo(b.method));
+    return result;
+  }
+
+  public DexEncodedMethod[] virtualMethodsSorted() {
+    DexEncodedMethod[] result = new DexEncodedMethod[virtualMethods.length];
+    System.arraycopy(virtualMethods, 0, result, 0, virtualMethods.length);
+    Arrays.sort(
+        result, (DexEncodedMethod a, DexEncodedMethod b) -> a.method.slowCompareTo(b.method));
+    return result;
+  }
+
   public void virtualizeMethods(Set<DexEncodedMethod> privateInstanceMethods) {
     int vLen = virtualMethods.length;
     int dLen = directMethods.length;
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 ee1b64d..0edeb47 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
@@ -17,12 +17,10 @@
 import com.android.tools.r8.utils.MethodSignatureEquivalence;
 import com.android.tools.r8.utils.Timing;
 import com.google.common.base.Equivalence;
-import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
 import com.google.common.collect.ImmutableMap;
 import java.util.Collection;
-import java.util.HashMap;
 import java.util.IdentityHashMap;
 import java.util.Map;
 import java.util.Set;
@@ -76,9 +74,7 @@
  *
  * <p>In the final stage, we assign names to methods by traversing the subtype tree, now allocating
  * separate naming states for each class starting from the frontier. In the first swoop, we allocate
- * all non-private methods, updating naming states accordingly. In a second swoop, we then allocate
- * private methods, as those may safely use names that are used by a public method further down in
- * the subtyping tree.
+ * all non-private methods, updating naming states accordingly.
  *
  * <p>Finally, the computed renamings are returned as a map from {@link DexMethod} to {@link
  * DexString}. The MethodNameMinifier object should not be retained to ensure all intermediate state
@@ -183,7 +179,7 @@
     timing.end();
     // Phase 2: Reserve all the names that are required for interfaces, and then assign names to
     //          interface methods. These are assigned by finding a name that is free in all naming
-    //          states that may hold an implementation
+    //          states that may hold an implementation.
     timing.begin("Phase 2");
     InterfaceMethodNameMinifier interfaceMethodNameMinifier =
         new InterfaceMethodNameMinifier(
@@ -192,57 +188,50 @@
     timing.end();
     // Phase 3: Assign names top-down by traversing the subtype hierarchy.
     timing.begin("Phase 3");
-    assignNamesToClassesMethods(appView.dexItemFactory().objectType, false);
-    timing.end();
-    // Phase 4: Do the same for private methods.
-    timing.begin("Phase 4");
-    assignNamesToClassesMethods(appView.dexItemFactory().objectType, true);
+    assignNamesToClassesMethods(appView.dexItemFactory().objectType);
     timing.end();
 
     return new MethodRenaming(renaming, interfaceMethodNameMinifier.getCallSiteRenamings());
   }
 
-  private void assignNamesToClassesMethods(DexType type, boolean doPrivates) {
+  private void assignNamesToClassesMethods(DexType type) {
+    // 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);
     boolean shouldAssignName = holder != null && !alwaysReserveMemberNames(holder);
     if (shouldAssignName) {
-      Map<Wrapper<DexMethod>, DexString> renamingAtThisLevel = new HashMap<>();
       MethodNamingState<?> state =
           computeStateIfAbsent(type, k -> minifierState.getState(holder.superType).createChild());
-      for (DexEncodedMethod method : holder.allMethodsSorted()) {
-        assignNameToMethod(method, state, renamingAtThisLevel, doPrivates);
+      for (DexEncodedMethod method : holder.virtualMethodsSorted()) {
+        assignNameToMethod(method, state);
       }
-      if (!doPrivates) {
-        renamingAtThisLevel.forEach(
-            (key, candidate) -> {
-              DexMethod method = key.get();
-              state.addRenaming(method.name, method.proto, candidate);
-            });
+      for (DexEncodedMethod method : holder.directMethodsSorted()) {
+        assignNameToMethod(method, state);
       }
     }
-    appView
-        .appInfo()
-        .forAllExtendsSubtypes(type, subtype -> assignNamesToClassesMethods(subtype, doPrivates));
+    appView.appInfo().forAllExtendsSubtypes(type, subtype -> assignNamesToClassesMethods(subtype));
   }
 
-  private void assignNameToMethod(
-      DexEncodedMethod encodedMethod,
-      MethodNamingState<?> state,
-      Map<Wrapper<DexMethod>, DexString> renamingAtThisLevel,
-      boolean doPrivates) {
-    if (encodedMethod.accessFlags.isPrivate() != doPrivates) {
-      return;
-    }
+  private void assignNameToMethod(DexEncodedMethod encodedMethod, MethodNamingState<?> state) {
     if (encodedMethod.accessFlags.isConstructor()) {
       return;
     }
     DexMethod method = encodedMethod.method;
     if (!state.isReserved(method.name, method.proto)) {
-      DexString renamedName =
-          renamingAtThisLevel.computeIfAbsent(
-              equivalence.wrap(method),
-              key -> state.assignNewNameFor(method, method.name, method.proto));
+      DexString renamedName = state.assignNewNameFor(method, method.name, method.proto);
       renaming.put(method, renamedName);
+      if (!encodedMethod.accessFlags.isPrivate()) {
+        state.addRenaming(method.name, method.proto, renamedName);
+      }
     }
   }
 
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 56360c3..b691a5a 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNamingState.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNamingState.java
@@ -149,7 +149,8 @@
     private final InternalState parentInternalState;
     private Set<DexString> reservedNames = null;
     private Table<DexString, KeyType, DexString> renamings = null;
-    private int nameCount;
+    private int virtualNameCount;
+    private int directNameCount = 0;
     private final Iterator<String> dictionaryIterator;
 
     private InternalState(
@@ -158,8 +159,8 @@
         Iterator<String> dictionaryIterator) {
       this.itemFactory = itemFactory;
       this.parentInternalState = parentInternalState;
-      this.nameCount =
-          parentInternalState == null ? INITIAL_NAME_COUNT : parentInternalState.nameCount;
+      this.virtualNameCount =
+          parentInternalState == null ? INITIAL_NAME_COUNT : parentInternalState.virtualNameCount;
       this.dictionaryIterator = dictionaryIterator;
     }
 
@@ -188,19 +189,25 @@
       reservedNames.add(name);
     }
 
-    public int incrementAndGet() {
-      int parentNameCount = 0;
+    private boolean checkParentPublicNameCountIsLessThanOrEqual() {
+      int maxParentCount = 0;
       InternalState tmp = parentInternalState;
       while (tmp != null) {
-        if (tmp.nameCount > parentNameCount) {
-          parentNameCount = tmp.nameCount;
-        }
+        maxParentCount = Math.max(tmp.virtualNameCount, maxParentCount);
         tmp = tmp.parentInternalState;
       }
-      if (parentNameCount > nameCount) {
-        nameCount = parentNameCount;
+      assert maxParentCount <= virtualNameCount;
+      return true;
+    }
+
+    public int incrementAndGet(boolean isDirect) {
+      assert checkParentPublicNameCountIsLessThanOrEqual();
+      if (isDirect) {
+        return virtualNameCount + (directNameCount++);
+      } else {
+        assert directNameCount == 0;
+        return virtualNameCount++;
       }
-      return nameCount++;
     }
 
     DexString getAssignedNameFor(DexString original, KeyType proto) {
@@ -263,10 +270,14 @@
     void printLastName(String indentation, PrintStream out) {
       out.print(indentation);
       out.print("Last name: ");
-      if (nameCount > 1) {
-        out.print(StringUtils.numberToIdentifier(EMPTY_CHAR_ARRAY, nameCount - 1, false));
-        out.print(" (name count: ");
-        out.print(nameCount);
+      int index = virtualNameCount + directNameCount;
+      if (index > 1) {
+        out.print(StringUtils.numberToIdentifier(EMPTY_CHAR_ARRAY, index - 1, false));
+        out.print(" (public name count: ");
+        out.print(virtualNameCount);
+        out.print(")");
+        out.print(" (direct name count: ");
+        out.print(directNameCount);
         out.print(")");
       } else {
         out.print("<NONE>");
diff --git a/src/main/java/com/android/tools/r8/naming/Minifier.java b/src/main/java/com/android/tools/r8/naming/Minifier.java
index d0fcfa1..fdf6f93 100644
--- a/src/main/java/com/android/tools/r8/naming/Minifier.java
+++ b/src/main/java/com/android/tools/r8/naming/Minifier.java
@@ -6,6 +6,7 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexCallSite;
 import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexReference;
@@ -146,7 +147,9 @@
 
     @Override
     public DexString next(DexMethod method, MethodNamingState.InternalState internalState) {
-      int counter = internalState.incrementAndGet();
+      DexEncodedMethod encodedMethod = appView.definitionFor(method);
+      boolean isDirectOrStatic = encodedMethod.isDirectMethod() || encodedMethod.isStatic();
+      int counter = internalState.incrementAndGet(isDirectOrStatic);
       return appView.dexItemFactory()
           .createString(StringUtils.numberToIdentifier(EMPTY_CHAR_ARRAY, counter, false));
     }
diff --git a/src/test/java/com/android/tools/r8/naming/MethodNameMinificationPrivateNamedLastTest.java b/src/test/java/com/android/tools/r8/naming/MethodNameMinificationPrivateNamedLastTest.java
index 13d63e5..5ff5f4b 100644
--- a/src/test/java/com/android/tools/r8/naming/MethodNameMinificationPrivateNamedLastTest.java
+++ b/src/test/java/com/android/tools/r8/naming/MethodNameMinificationPrivateNamedLastTest.java
@@ -26,8 +26,8 @@
 
 /**
  * MethodNameMinificationPrivateNamedLastTest tests that private methods are named after public
- * methods. Public virtual methods may be overridden and used in the sub-class hierarchy and
- * therefore it is preferable to have their names as small as possible.
+ * methods. Private methods can be named freely and should not influence how public methods are
+ * named.
  */
 @RunWith(Parameterized.class)
 public class MethodNameMinificationPrivateNamedLastTest extends TestBase {
@@ -146,9 +146,7 @@
               assertEquals("b", cSubject.uniqueMethodWithName("m3").getFinalName());
               AnyOf<String> cPrivateNamesP = anyOf(is("c"), is("d"));
               assertThat(cSubject.uniqueMethodWithName("m2").getFinalName(), cPrivateNamesP);
-              // TODO(mkroghj) This is not working currently. See if it gets fixed by removing the
-              //  extra pass for private methods.
-              // assertThat(cSubject.uniqueMethodWithName("m4").getFinalName(), cPrivateNamesP);
+              assertThat(cSubject.uniqueMethodWithName("m4").getFinalName(), cPrivateNamesP);
             });
   }
 }