diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java b/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java
index c5d366a..6414e13 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java
@@ -35,7 +35,7 @@
 public class ClassNameMapper implements ProguardMap {
 
   public static class Builder extends ProguardMap.Builder {
-    final ImmutableMap.Builder<String, ClassNamingForNameMapper.Builder> mapBuilder;
+    private final ImmutableMap.Builder<String, ClassNamingForNameMapper.Builder> mapBuilder;
 
     private Builder() {
       mapBuilder = ImmutableMap.builder();
diff --git a/src/main/java/com/android/tools/r8/naming/ClassNamingForNameMapper.java b/src/main/java/com/android/tools/r8/naming/ClassNamingForNameMapper.java
index 34fdd9d..9c61a7a 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNamingForNameMapper.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNamingForNameMapper.java
@@ -14,6 +14,7 @@
 import java.io.Writer;
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
@@ -172,20 +173,20 @@
   private final ImmutableMap<MethodSignature, MemberNaming> methodMembers;
   private final ImmutableMap<FieldSignature, MemberNaming> fieldMembers;
 
-  /** Map of obfuscated name -> MappedRangesOfName */
-  public final Map<String, MappedRangesOfName> mappedRangesByName;
+  /** Map of renamed name -> MappedRangesOfName */
+  public final Map<String, MappedRangesOfName> mappedRangesByRenamedName;
 
   private ClassNamingForNameMapper(
       String renamedName,
       String originalName,
       Map<MethodSignature, MemberNaming> methodMembers,
       Map<FieldSignature, MemberNaming> fieldMembers,
-      Map<String, MappedRangesOfName> mappedRangesByName) {
+      Map<String, MappedRangesOfName> mappedRangesByRenamedName) {
     this.renamedName = renamedName;
     this.originalName = originalName;
     this.methodMembers = ImmutableMap.copyOf(methodMembers);
     this.fieldMembers = ImmutableMap.copyOf(fieldMembers);
-    this.mappedRangesByName = mappedRangesByName;
+    this.mappedRangesByRenamedName = mappedRangesByRenamedName;
   }
 
   @Override
@@ -273,16 +274,13 @@
         });
 
     // Sort MappedRanges by sequence number to restore construction order (original Proguard-map
-    // input)
-    List<MappedRange> rangeList = new ArrayList<>();
-    for (MappedRangesOfName ranges : mappedRangesByName.values()) {
-      rangeList.addAll(ranges.mappedRanges);
+    // input).
+    List<MappedRange> mappedRangesSorted = new ArrayList<>();
+    for (MappedRangesOfName ranges : mappedRangesByRenamedName.values()) {
+      mappedRangesSorted.addAll(ranges.mappedRanges);
     }
-    rangeList.sort(
-        (lhs, rhs) -> {
-          return lhs.sequenceNumber - rhs.sequenceNumber;
-        });
-    for (MappedRange range : rangeList) {
+    mappedRangesSorted.sort(Comparator.comparingInt(range -> range.sequenceNumber));
+    for (MappedRange range : mappedRangesSorted) {
       writer.append("    ").append(range.toString()).append('\n');
     }
   }
@@ -313,7 +311,7 @@
         && renamedName.equals(that.renamedName)
         && methodMembers.equals(that.methodMembers)
         && fieldMembers.equals(that.fieldMembers)
-        && mappedRangesByName.equals(that.mappedRangesByName);
+        && mappedRangesByRenamedName.equals(that.mappedRangesByRenamedName);
   }
 
   @Override
@@ -322,7 +320,7 @@
     result = 31 * result + renamedName.hashCode();
     result = 31 * result + methodMembers.hashCode();
     result = 31 * result + fieldMembers.hashCode();
-    result = 31 * result + mappedRangesByName.hashCode();
+    result = 31 * result + mappedRangesByRenamedName.hashCode();
     return result;
   }
 
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 5163772..6d12230 100644
--- a/src/main/java/com/android/tools/r8/utils/LineNumberOptimizer.java
+++ b/src/main/java/com/android/tools/r8/utils/LineNumberOptimizer.java
@@ -212,8 +212,8 @@
         continue;
       }
 
-      IdentityHashMap<DexString, List<DexEncodedMethod>> methodsByName =
-          groupMethodsByName(namingLens, clazz);
+      IdentityHashMap<DexString, List<DexEncodedMethod>> methodsByRenamedName =
+          groupMethodsByRenamedName(namingLens, clazz);
 
       // At this point we don't know if we really need to add this class to the builder.
       // It depends on whether any methods/fields are renamed or some methods contain positions.
@@ -232,8 +232,11 @@
       // First transfer renamed fields to classNamingBuilder.
       addFieldsToClassNaming(namingLens, clazz, onDemandClassNamingBuilder);
 
-      // Then process the methods.
-      for (List<DexEncodedMethod> methods : methodsByName.values()) {
+      // Then process the methods, ordered by renamed name.
+      List<DexString> renamedMethodNames = new ArrayList<>(methodsByRenamedName.keySet());
+      renamedMethodNames.sort(DexString::slowCompareTo);
+      for (DexString methodName : renamedMethodNames) {
+        List<DexEncodedMethod> methods = methodsByRenamedName.get(methodName);
         if (methods.size() > 1) {
           // If there are multiple methods with the same name (overloaded) then sort them for
           // deterministic behaviour: the algorithm will assign new line numbers in this order.
@@ -393,27 +396,18 @@
         });
   }
 
-  private static IdentityHashMap<DexString, List<DexEncodedMethod>> groupMethodsByName(
+  private static IdentityHashMap<DexString, List<DexEncodedMethod>> groupMethodsByRenamedName(
       NamingLens namingLens, DexProgramClass clazz) {
-    IdentityHashMap<DexString, List<DexEncodedMethod>> methodsByName =
+    IdentityHashMap<DexString, List<DexEncodedMethod>> methodsByRenamedName =
         new IdentityHashMap<>(clazz.directMethods().length + clazz.virtualMethods().length);
-    clazz.forEachMethod(
-        method -> {
-          // Add method only if renamed or contains positions.
-          if (namingLens.lookupName(method.method) != method.method.name
-              || doesContainPositions(method)) {
-            methodsByName.compute(
-                method.method.name,
-                (name, methods) -> {
-                  if (methods == null) {
-                    methods = new ArrayList<>();
-                  }
-                  methods.add(method);
-                  return methods;
-                });
-          }
-        });
-    return methodsByName;
+    for (DexEncodedMethod method : clazz.methods()) {
+      // Add method only if renamed or contains positions.
+      DexString renamedName = namingLens.lookupName(method.method);
+      if (renamedName != method.method.name || doesContainPositions(method)) {
+        methodsByRenamedName.computeIfAbsent(renamedName, key -> new ArrayList<>()).add(method);
+      }
+    }
+    return methodsByRenamedName;
   }
 
   private static boolean doesContainPositions(DexEncodedMethod method) {
diff --git a/src/test/java/com/android/tools/r8/debug/DebugTestBase.java b/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
index 5707812..97f6820 100644
--- a/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
+++ b/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
@@ -630,7 +630,7 @@
           return null;
         }
         ClassNamingForNameMapper.MappedRangesOfName ranges =
-            classNaming.mappedRangesByName.get(obfuscatedMethodName);
+            classNaming.mappedRangesByRenamedName.get(obfuscatedMethodName);
         if (ranges == null) {
           return null;
         }
@@ -694,7 +694,7 @@
           return null;
         }
         ClassNamingForNameMapper.MappedRangesOfName ranges =
-            classNaming.mappedRangesByName.get(obfuscatedMethodName);
+            classNaming.mappedRangesByRenamedName.get(obfuscatedMethodName);
         if (ranges == null) {
           return null;
         }
diff --git a/src/test/java/com/android/tools/r8/debuginfo/InliningWithoutPositionsTestRunner.java b/src/test/java/com/android/tools/r8/debuginfo/InliningWithoutPositionsTestRunner.java
index 0f8ac65..ce84f51 100644
--- a/src/test/java/com/android/tools/r8/debuginfo/InliningWithoutPositionsTestRunner.java
+++ b/src/test/java/com/android/tools/r8/debuginfo/InliningWithoutPositionsTestRunner.java
@@ -185,7 +185,7 @@
     ClassNamingForNameMapper classNaming = mapper.getClassNaming(TEST_PACKAGE + "." + TEST_CLASS);
     assertNotNull(classNaming);
 
-    MappedRangesOfName rangesForMain = classNaming.mappedRangesByName.get("main");
+    MappedRangesOfName rangesForMain = classNaming.mappedRangesByRenamedName.get("main");
     assertNotNull(rangesForMain);
 
     List<MappedRange> frames = rangesForMain.allRangesForLine(expectedLineNumber);
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreDeterministicTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreDeterministicTest.java
index abc7a73..6ae151e 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreDeterministicTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreDeterministicTest.java
@@ -3,13 +3,14 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.internal;
 
+import static junit.framework.TestCase.assertEquals;
+
 import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.DexIndexedConsumer;
 import com.android.tools.r8.OutputMode;
 import com.android.tools.r8.R8Command;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.shaking.ProguardRuleParserException;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.AndroidApp;
 import com.beust.jcommander.internal.Lists;
@@ -20,52 +21,60 @@
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Set;
-import java.util.concurrent.ExecutionException;
 import org.junit.Test;
 
 public class R8GMSCoreDeterministicTest extends GMSCoreCompilationTestBase {
 
-  public Set<DexEncodedMethod> shuffle(Set<DexEncodedMethod> methods) {
+  private static class CompilationResult {
+    AndroidApp app;
+    String proguardMap;
+  }
+
+  private static Set<DexEncodedMethod> shuffle(Set<DexEncodedMethod> methods) {
     List<DexEncodedMethod> toShuffle = Lists.newArrayList(methods);
     Collections.shuffle(toShuffle);
     return new LinkedHashSet<>(toShuffle);
   }
 
-  private AndroidApp doRun()
-      throws IOException, ProguardRuleParserException, ExecutionException,
-      CompilationFailedException {
+  private CompilationResult doRun() throws IOException, CompilationFailedException {
     R8Command command =
         R8Command.builder()
             .addProgramFiles(Paths.get(GMSCORE_V7_DIR, GMSCORE_APK))
             .setProgramConsumer(DexIndexedConsumer.emptyConsumer())
             .setMinApiLevel(AndroidApiLevel.L.getLevel())
             .build();
-    return ToolHelper.runR8(
-        command,
-        options -> {
-          // For this test just do random shuffle.
-          options.testing.irOrdering = this::shuffle;
-          // Only use one thread to process to process in the order decided by the callback.
-          options.numberOfThreads = 1;
-          // Ignore the missing classes.
-          options.ignoreMissingClasses = true;
-        });
+    CompilationResult result = new CompilationResult();
+    result.app =
+        ToolHelper.runR8(
+            command,
+            options -> {
+              // For this test just do random shuffle.
+              options.testing.irOrdering = R8GMSCoreDeterministicTest::shuffle;
+              // Only use one thread to process to process in the order decided by the callback.
+              options.numberOfThreads = 1;
+              // Ignore the missing classes.
+              options.ignoreMissingClasses = true;
+              // Store the generated Proguard map.
+              options.proguardMapConsumer =
+                  (proguardMap, handler) -> result.proguardMap = proguardMap;
+            });
+    return result;
   }
 
   @Test
   public void deterministic() throws Exception {
-
     // Run two independent compilations.
-    AndroidApp app1 = doRun();
-    AndroidApp app2 = doRun();
+    CompilationResult result1 = doRun();
+    CompilationResult result2 = doRun();
 
     // Check that the generated bytecode runs through the dex2oat verifier with no errors.
     Path combinedInput = temp.getRoot().toPath().resolve("all.jar");
     Path oatFile = temp.getRoot().toPath().resolve("all.oat");
-    app1.writeToZip(combinedInput, OutputMode.DexIndexed);
+    result1.app.writeToZip(combinedInput, OutputMode.DexIndexed);
     ToolHelper.runDex2Oat(combinedInput, oatFile);
 
     // Verify that the result of the two compilations was the same.
-    assertIdenticalApplications(app1, app2);
+    assertIdenticalApplications(result1.app, result2.app);
+    assertEquals(result1.proguardMap, result2.proguardMap);
   }
 }
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
index 6adf680..d881185 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.internal;
 
+import static org.junit.Assert.assertEquals;
+
 import com.android.tools.r8.CompilationMode;
 import com.android.tools.r8.R8RunArtTestsTest.CompilerUnderTest;
 import com.android.tools.r8.utils.AndroidApp;
@@ -11,17 +13,33 @@
 
 public class R8GMSCoreV10DeployJarVerificationTest extends GMSCoreDeployJarVerificationTest {
 
+  private String proguardMap1 = null;
+  private String proguardMap2 = null;
+
   @Test
   public void buildFromDeployJar() throws Exception {
     // TODO(tamaskenez): set hasReference = true when we have the noshrink file for V10
-    AndroidApp app1 = buildFromDeployJar(
-        CompilerUnderTest.R8, CompilationMode.RELEASE,
-        GMSCoreCompilationTestBase.GMSCORE_V10_DIR, false);
-    AndroidApp app2 = buildFromDeployJar(
-        CompilerUnderTest.R8, CompilationMode.RELEASE,
-        GMSCoreCompilationTestBase.GMSCORE_V10_DIR, false);
+    AndroidApp app1 =
+        buildFromDeployJar(
+            CompilerUnderTest.R8,
+            CompilationMode.RELEASE,
+            GMSCoreCompilationTestBase.GMSCORE_V10_DIR,
+            false,
+            options ->
+                options.proguardMapConsumer =
+                    (proguardMap, handler) -> this.proguardMap1 = proguardMap);
+    AndroidApp app2 =
+        buildFromDeployJar(
+            CompilerUnderTest.R8,
+            CompilationMode.RELEASE,
+            GMSCoreCompilationTestBase.GMSCORE_V10_DIR,
+            false,
+            options ->
+                options.proguardMapConsumer =
+                    (proguardMap, handler) -> this.proguardMap2 = proguardMap);
 
     // Verify that the result of the two compilations was the same.
     assertIdenticalApplications(app1, app2);
+    assertEquals(proguardMap1, proguardMap2);
   }
 }
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
index ae470c6..4374d0e 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.internal;
 
+import static org.junit.Assert.assertEquals;
+
 import com.android.tools.r8.CompilationMode;
 import com.android.tools.r8.utils.AndroidApp;
 import org.junit.Test;
@@ -10,15 +12,33 @@
 public class R8GMSCoreV10TreeShakeJarVerificationTest
     extends R8GMSCoreTreeShakeJarVerificationTest {
 
+  private String proguardMap1 = null;
+  private String proguardMap2 = null;
+
   @Test
   public void buildAndTreeShakeFromDeployJar() throws Exception {
     // TODO(tamaskenez): set hasReference = true when we have the noshrink file for V10
-    AndroidApp app1 = buildAndTreeShakeFromDeployJar(
-        CompilationMode.RELEASE, GMSCORE_V10_DIR, false, GMSCORE_V10_MAX_SIZE, null);
-    AndroidApp app2 = buildAndTreeShakeFromDeployJar(
-        CompilationMode.RELEASE, GMSCORE_V10_DIR, false, GMSCORE_V10_MAX_SIZE, null);
+    AndroidApp app1 =
+        buildAndTreeShakeFromDeployJar(
+            CompilationMode.RELEASE,
+            GMSCORE_V10_DIR,
+            false,
+            GMSCORE_V10_MAX_SIZE,
+            options ->
+                options.proguardMapConsumer =
+                    (proguardMap, handler) -> this.proguardMap1 = proguardMap);
+    AndroidApp app2 =
+        buildAndTreeShakeFromDeployJar(
+            CompilationMode.RELEASE,
+            GMSCORE_V10_DIR,
+            false,
+            GMSCORE_V10_MAX_SIZE,
+            options ->
+                options.proguardMapConsumer =
+                    (proguardMap, handler) -> this.proguardMap2 = proguardMap);
 
     // Verify that the result of the two compilations was the same.
     assertIdenticalApplications(app1, app2);
+    assertEquals(proguardMap1, proguardMap2);
   }
 }