diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
index a7c1351..0b6547e 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -14,6 +14,7 @@
 import com.android.tools.r8.ir.analysis.proto.GeneratedMessageLiteShrinker;
 import com.android.tools.r8.ir.analysis.proto.ProtoShrinker;
 import com.android.tools.r8.ir.analysis.value.AbstractValueFactory;
+import com.android.tools.r8.ir.conversion.MethodProcessingId;
 import com.android.tools.r8.ir.desugar.PrefixRewritingMapper;
 import com.android.tools.r8.ir.optimize.CallSiteOptimizationInfoPropagator;
 import com.android.tools.r8.ir.optimize.info.field.InstanceFieldInitializationInfoFactory;
@@ -49,6 +50,7 @@
   private final AbstractValueFactory abstractValueFactory = new AbstractValueFactory();
   private final InstanceFieldInitializationInfoFactory instanceFieldInitializationInfoFactory =
       new InstanceFieldInitializationInfoFactory();
+  private final MethodProcessingId.Factory methodProcessingIdFactory;
 
   // Desugared library prefix rewriter.
   public final PrefixRewritingMapper rewritePrefix;
@@ -89,6 +91,8 @@
     this.wholeProgramOptimizations = wholeProgramOptimizations;
     this.graphLense = GraphLense.getIdentityLense();
     this.initClassLens = InitClassLens.getDefault();
+    this.methodProcessingIdFactory =
+        new MethodProcessingId.Factory(options.testing.methodProcessingIdConsumer);
     this.options = options;
     this.rewritePrefix = mapper;
 
@@ -144,6 +148,10 @@
     return instanceFieldInitializationInfoFactory;
   }
 
+  public MethodProcessingId.Factory methodProcessingIdFactory() {
+    return methodProcessingIdFactory;
+  }
+
   public T appInfo() {
     assert !appInfo.hasClassHierarchy() || enableWholeProgramOptimizations();
     return appInfo;
diff --git a/src/main/java/com/android/tools/r8/graph/AssemblyWriter.java b/src/main/java/com/android/tools/r8/graph/AssemblyWriter.java
index a2a814a..9893684 100644
--- a/src/main/java/com/android/tools/r8/graph/AssemblyWriter.java
+++ b/src/main/java/com/android/tools/r8/graph/AssemblyWriter.java
@@ -7,6 +7,7 @@
 
 import com.android.tools.r8.ClassFileConsumer;
 import com.android.tools.r8.ir.conversion.IRConverter;
+import com.android.tools.r8.ir.conversion.MethodProcessingId;
 import com.android.tools.r8.ir.conversion.OneTimeMethodProcessor;
 import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackIgnore;
 import com.android.tools.r8.kotlin.Kotlin;
@@ -23,6 +24,8 @@
 
 public class AssemblyWriter extends DexByteCodeWriter {
 
+  private final MethodProcessingId.Factory methodProcessingIdFactory =
+      new MethodProcessingId.Factory();
   private final boolean writeAllClassInfo;
   private final boolean writeFields;
   private final boolean writeAnnotations;
@@ -137,11 +140,16 @@
 
   private void writeIR(ProgramMethod method, PrintStream ps) {
     CfgPrinter printer = new CfgPrinter();
-    new IRConverter(appInfo, options, timing, printer)
-        .processMethod(
-            method,
-            OptimizationFeedbackIgnore.getInstance(),
-            OneTimeMethodProcessor.getInstance());
+    IRConverter converter = new IRConverter(appInfo, options, timing, printer);
+    OneTimeMethodProcessor methodProcessor =
+        OneTimeMethodProcessor.create(method, methodProcessingIdFactory);
+    methodProcessor.forEachWave(
+        (ignore, methodProcesingId) ->
+            converter.processMethod(
+                method,
+                OptimizationFeedbackIgnore.getInstance(),
+                methodProcessor,
+                methodProcesingId));
     ps.println(printer.toString());
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java
index 400b509..c64dff4 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java
@@ -27,8 +27,8 @@
 import com.android.tools.r8.shaking.DefaultTreePrunerConfiguration;
 import com.android.tools.r8.shaking.Enqueuer;
 import com.android.tools.r8.shaking.TreePrunerConfiguration;
-import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.Timing;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
 import java.util.List;
@@ -153,13 +153,16 @@
       IRConverter converter, ExecutorService executorService, Timing timing)
       throws ExecutionException {
     timing.begin("[Proto] Post optimize generated extension registry");
-    ThreadUtils.processItems(
-        this::forEachFindLiteExtensionByNumberMethod,
-        method ->
+    SortedProgramMethodSet wave =
+        SortedProgramMethodSet.create(this::forEachFindLiteExtensionByNumberMethod);
+    OneTimeMethodProcessor methodProcessor = OneTimeMethodProcessor.create(wave, appView);
+    methodProcessor.forEachWave(
+        (method, methodProcessingId) ->
             converter.processMethod(
                 method,
                 OptimizationFeedbackIgnore.getInstance(),
-                OneTimeMethodProcessor.getInstance()),
+                methodProcessor,
+                methodProcessingId),
         executorService);
     timing.end();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteShrinker.java
index 7d74c63..6da2550 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteShrinker.java
@@ -32,8 +32,8 @@
 import com.android.tools.r8.ir.conversion.OneTimeMethodProcessor;
 import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackIgnore;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.Timing;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import java.util.List;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
@@ -78,13 +78,15 @@
       IRConverter converter, ExecutorService executorService, Timing timing)
       throws ExecutionException {
     timing.begin("[Proto] Post optimize dynamic methods");
-    ThreadUtils.processItems(
-        this::forEachDynamicMethod,
-        method ->
+    SortedProgramMethodSet wave = SortedProgramMethodSet.create(this::forEachDynamicMethod);
+    OneTimeMethodProcessor methodProcessor = OneTimeMethodProcessor.create(wave, appView);
+    methodProcessor.forEachWave(
+        (method, methodProcessingId) ->
             converter.processMethod(
                 method,
                 OptimizationFeedbackIgnore.getInstance(),
-                OneTimeMethodProcessor.getInstance()),
+                methodProcessor,
+                methodProcessingId),
         executorService);
     timing.end();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CallGraph.java b/src/main/java/com/android/tools/r8/ir/conversion/CallGraph.java
index a5842de..2084df9 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CallGraph.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CallGraph.java
@@ -10,7 +10,7 @@
 import com.android.tools.r8.ir.conversion.CallGraphBuilderBase.CycleEliminator.CycleEliminationResult;
 import com.android.tools.r8.ir.conversion.CallSiteInformation.CallGraphBasedCallSiteInformation;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import com.google.common.collect.Sets;
 import java.util.Iterator;
 import java.util.Set;
@@ -278,16 +278,16 @@
     return nodes.isEmpty();
   }
 
-  public ProgramMethodSet extractLeaves() {
+  public SortedProgramMethodSet extractLeaves() {
     return extractNodes(Node::isLeaf, Node::cleanCallersAndReadersForRemoval);
   }
 
-  public ProgramMethodSet extractRoots() {
+  public SortedProgramMethodSet extractRoots() {
     return extractNodes(Node::isRoot, Node::cleanCalleesAndWritersForRemoval);
   }
 
-  private ProgramMethodSet extractNodes(Predicate<Node> predicate, Consumer<Node> clean) {
-    ProgramMethodSet result = ProgramMethodSet.create();
+  private SortedProgramMethodSet extractNodes(Predicate<Node> predicate, Consumer<Node> clean) {
+    SortedProgramMethodSet result = SortedProgramMethodSet.create();
     Set<Node> removed = Sets.newIdentityHashSet();
     Iterator<Node> nodeIterator = nodes.iterator();
     while (nodeIterator.hasNext()) {
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CodeOptimization.java b/src/main/java/com/android/tools/r8/ir/conversion/CodeOptimization.java
index ce571d6..a10c562 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CodeOptimization.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CodeOptimization.java
@@ -21,10 +21,14 @@
   //  rewriting every affected optimization.
   // Note that a code optimization can be a collection of other code optimizations.
   // In that way, IRConverter will serve as the default full processing of all optimizations.
-  void optimize(IRCode code, OptimizationFeedback feedback, MethodProcessor methodProcessor);
+  void optimize(
+      IRCode code,
+      OptimizationFeedback feedback,
+      MethodProcessor methodProcessor,
+      MethodProcessingId methodProcessingId);
 
   static CodeOptimization from(Consumer<IRCode> consumer) {
-    return (code, feedback, methodProcessor) -> {
+    return (code, feedback, methodProcessor, methodProcessingId) -> {
       consumer.accept(code);
     };
   }
@@ -34,9 +38,9 @@
   }
 
   static CodeOptimization sequence(Collection<CodeOptimization> codeOptimizations) {
-    return (code, feedback, methodProcessor) -> {
+    return (code, feedback, methodProcessor, methodProcessingId) -> {
       for (CodeOptimization codeOptimization : codeOptimizations) {
-        codeOptimization.optimize(code, feedback, methodProcessor);
+        codeOptimization.optimize(code, feedback, methodProcessor, methodProcessingId);
       }
     };
   }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index 14a936d..71ff0c2 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -104,6 +104,7 @@
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import com.google.common.base.Suppliers;
 import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
@@ -641,7 +642,10 @@
             || !(options.passthroughDexCode && definition.getCode().isDexCode())) {
           // We do not process in call graph order, so anything could be a leaf.
           rewriteCode(
-              method, simpleOptimizationFeedback, OneTimeMethodProcessor.getInstance(method));
+              method,
+              simpleOptimizationFeedback,
+              OneTimeMethodProcessor.create(method, appView),
+              null);
         } else {
           assert definition.getCode().isDexCode();
         }
@@ -692,7 +696,8 @@
         outliner.createOutlineMethodIdentifierGenerator();
       }
       primaryMethodProcessor.forEachMethod(
-          method -> processMethod(method, feedback, primaryMethodProcessor),
+          (method, methodProcessingId) ->
+              processMethod(method, feedback, primaryMethodProcessor, methodProcessingId),
           this::waveStart,
           this::waveDone,
           timing,
@@ -1013,38 +1018,42 @@
   public void optimizeSynthesizedClass(
       DexProgramClass clazz, ExecutorService executorService)
       throws ExecutionException {
-    ProgramMethodSet methods = ProgramMethodSet.create();
-    clazz.forEachProgramMethod(methods::add);
     // Process the generated class, but don't apply any outlining.
+    SortedProgramMethodSet methods = SortedProgramMethodSet.create(clazz::forEachProgramMethod);
     processMethodsConcurrently(methods, executorService);
   }
 
   public void optimizeSynthesizedClasses(
       Collection<DexProgramClass> classes, ExecutorService executorService)
       throws ExecutionException {
-    ProgramMethodSet methods = ProgramMethodSet.create();
+    SortedProgramMethodSet methods = SortedProgramMethodSet.create();
     for (DexProgramClass clazz : classes) {
       clazz.forEachProgramMethod(methods::add);
     }
     processMethodsConcurrently(methods, executorService);
   }
 
-  public void optimizeSynthesizedMethod(ProgramMethod method) {
-    if (!method.getDefinition().isProcessed()) {
+  public void optimizeSynthesizedMethod(ProgramMethod synthesizedMethod) {
+    if (!synthesizedMethod.getDefinition().isProcessed()) {
       // Process the generated method, but don't apply any outlining.
-      processMethod(
-          method,
-          delayedOptimizationFeedback,
-          OneTimeMethodProcessor.getInstance());
+      OneTimeMethodProcessor methodProcessor =
+          OneTimeMethodProcessor.create(synthesizedMethod, appView);
+      methodProcessor.forEachWave(
+          (method, methodProcessingId) ->
+              processMethod(
+                  method, delayedOptimizationFeedback, methodProcessor, methodProcessingId));
     }
   }
 
-  public void processMethodsConcurrently(ProgramMethodSet methods, ExecutorService executorService)
-      throws ExecutionException {
-    if (!methods.isEmpty()) {
-      OneTimeMethodProcessor processor = OneTimeMethodProcessor.getInstance(methods);
-      processor.forEachWave(
-          method -> processMethod(method, delayedOptimizationFeedback, processor), executorService);
+  public void processMethodsConcurrently(
+      SortedProgramMethodSet wave, ExecutorService executorService) throws ExecutionException {
+    if (!wave.isEmpty()) {
+      OneTimeMethodProcessor methodProcessor = OneTimeMethodProcessor.create(wave, appView);
+      methodProcessor.forEachWave(
+          (method, methodProcessingId) ->
+              processMethod(
+                  method, delayedOptimizationFeedback, methodProcessor, methodProcessingId),
+          executorService);
     }
   }
 
@@ -1064,12 +1073,15 @@
 
   // TODO(b/140766440): Make this receive a list of CodeOptimizations to conduct.
   public Timing processMethod(
-      ProgramMethod method, OptimizationFeedback feedback, MethodProcessor methodProcessor) {
+      ProgramMethod method,
+      OptimizationFeedback feedback,
+      MethodProcessor methodProcessor,
+      MethodProcessingId methodProcessingId) {
     DexEncodedMethod definition = method.getDefinition();
     Code code = definition.getCode();
     boolean matchesMethodFilter = options.methodMatchesFilter(definition);
     if (code != null && matchesMethodFilter) {
-      return rewriteCode(method, feedback, methodProcessor);
+      return rewriteCode(method, feedback, methodProcessor, methodProcessingId);
     } else {
       // Mark abstract methods as processed as well.
       definition.markProcessed(ConstraintWithTarget.NEVER);
@@ -1086,15 +1098,21 @@
   }
 
   private Timing rewriteCode(
-      ProgramMethod method, OptimizationFeedback feedback, MethodProcessor methodProcessor) {
+      ProgramMethod method,
+      OptimizationFeedback feedback,
+      MethodProcessor methodProcessor,
+      MethodProcessingId methodProcessingId) {
     return ExceptionUtils.withOriginAttachmentHandler(
         method.getOrigin(),
         new MethodPosition(method.getReference()),
-        () -> rewriteCodeInternal(method, feedback, methodProcessor));
+        () -> rewriteCodeInternal(method, feedback, methodProcessor, methodProcessingId));
   }
 
   private Timing rewriteCodeInternal(
-      ProgramMethod method, OptimizationFeedback feedback, MethodProcessor methodProcessor) {
+      ProgramMethod method,
+      OptimizationFeedback feedback,
+      MethodProcessor methodProcessor,
+      MethodProcessingId methodProcessingId) {
     if (options.verbose) {
       options.reporter.info(
           new StringDiagnostic("Processing: " + method.toSourceString()));
@@ -1115,12 +1133,15 @@
       feedback.markProcessed(method.getDefinition(), ConstraintWithTarget.NEVER);
       return Timing.empty();
     }
-    return optimize(code, feedback, methodProcessor);
+    return optimize(code, feedback, methodProcessor, methodProcessingId);
   }
 
   // TODO(b/140766440): Convert all sub steps an implementer of CodeOptimization
   private Timing optimize(
-      IRCode code, OptimizationFeedback feedback, MethodProcessor methodProcessor) {
+      IRCode code,
+      OptimizationFeedback feedback,
+      MethodProcessor methodProcessor,
+      MethodProcessingId methodProcessingId) {
     ProgramMethod context = code.context();
     DexEncodedMethod method = context.getDefinition();
     DexProgramClass holder = context.getHolder();
@@ -1274,7 +1295,9 @@
       stringOptimizer.removeTrivialConversions(code);
       timing.end();
       timing.begin("Optimize library methods");
-      appView.libraryMethodOptimizer().optimize(code, feedback, methodProcessor);
+      appView
+          .libraryMethodOptimizer()
+          .optimize(code, feedback, methodProcessor, methodProcessingId);
       timing.end();
       assert code.isConsistentSSA();
     }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/MethodProcessingId.java b/src/main/java/com/android/tools/r8/ir/conversion/MethodProcessingId.java
new file mode 100644
index 0000000..60d970e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/conversion/MethodProcessingId.java
@@ -0,0 +1,77 @@
+// 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.ir.conversion;
+
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
+import java.util.function.BiConsumer;
+
+public class MethodProcessingId {
+
+  private final int primaryId;
+  private int secondaryId = 1;
+
+  private MethodProcessingId(int primaryId) {
+    this.primaryId = primaryId;
+  }
+
+  public String getAndIncrementId() {
+    String id = getId();
+    secondaryId++;
+    return id;
+  }
+
+  public String getId() {
+    if (secondaryId == 1) {
+      return Integer.toString(primaryId);
+    }
+    return primaryId + "$" + secondaryId;
+  }
+
+  public int getPrimaryId() {
+    return primaryId;
+  }
+
+  public static class Factory {
+
+    private final BiConsumer<ProgramMethod, MethodProcessingId> consumer;
+    private int nextId = 1;
+
+    public Factory() {
+      this(null);
+    }
+
+    public Factory(BiConsumer<ProgramMethod, MethodProcessingId> consumer) {
+      this.consumer = consumer;
+    }
+
+    public ReservedMethodProcessingIds reserveIds(SortedProgramMethodSet wave) {
+      ReservedMethodProcessingIds result = new ReservedMethodProcessingIds(nextId, wave.size());
+      nextId += wave.size();
+      return result;
+    }
+
+    public class ReservedMethodProcessingIds {
+
+      private final int firstReservedId;
+      private final int numberOfReservedIds;
+
+      public ReservedMethodProcessingIds(int firstReservedId, int numberOfReservedIds) {
+        this.firstReservedId = firstReservedId;
+        this.numberOfReservedIds = numberOfReservedIds;
+      }
+
+      public MethodProcessingId get(ProgramMethod method, int index) {
+        assert index >= 0;
+        assert index < numberOfReservedIds;
+        MethodProcessingId result = new MethodProcessingId(firstReservedId + index);
+        if (consumer != null) {
+          consumer.accept(method, result);
+        }
+        return result;
+      }
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OneTimeMethodProcessor.java b/src/main/java/com/android/tools/r8/ir/conversion/OneTimeMethodProcessor.java
index 071bfcb..00bad3b 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OneTimeMethodProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OneTimeMethodProcessor.java
@@ -3,10 +3,12 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.conversion;
 
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.conversion.MethodProcessingId.Factory.ReservedMethodProcessingIds;
 import com.android.tools.r8.utils.ThreadUtils;
-import com.android.tools.r8.utils.ThrowingConsumer;
-import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.ThrowingBiConsumer;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 
@@ -16,22 +18,34 @@
  */
 public class OneTimeMethodProcessor implements MethodProcessor {
 
-  private ProgramMethodSet wave;
+  private final MethodProcessingId.Factory methodProcessingIdFactory;
+  private final SortedProgramMethodSet wave;
 
-  private OneTimeMethodProcessor(ProgramMethodSet methodsToProcess) {
-    this.wave = methodsToProcess;
+  private OneTimeMethodProcessor(
+      MethodProcessingId.Factory methodProcessingIdFactory, SortedProgramMethodSet wave) {
+    this.methodProcessingIdFactory = methodProcessingIdFactory;
+    this.wave = wave;
   }
 
-  public static OneTimeMethodProcessor getInstance() {
-    return new OneTimeMethodProcessor(null);
+  public static OneTimeMethodProcessor create(ProgramMethod methodToProcess, AppView<?> appView) {
+    return create(methodToProcess, appView.methodProcessingIdFactory());
   }
 
-  public static OneTimeMethodProcessor getInstance(ProgramMethod methodToProcess) {
-    return new OneTimeMethodProcessor(ProgramMethodSet.create(methodToProcess));
+  public static OneTimeMethodProcessor create(
+      ProgramMethod methodToProcess, MethodProcessingId.Factory methodProcessingIdFactory) {
+    return new OneTimeMethodProcessor(
+        methodProcessingIdFactory, SortedProgramMethodSet.create(methodToProcess));
   }
 
-  public static OneTimeMethodProcessor getInstance(ProgramMethodSet methodsToProcess) {
-    return new OneTimeMethodProcessor(methodsToProcess);
+  public static OneTimeMethodProcessor create(
+      SortedProgramMethodSet methodsToProcess, AppView<?> appView) {
+    return create(methodsToProcess, appView.methodProcessingIdFactory());
+  }
+
+  public static OneTimeMethodProcessor create(
+      SortedProgramMethodSet methodsToProcess,
+      MethodProcessingId.Factory methodProcessingIdFactory) {
+    return new OneTimeMethodProcessor(methodProcessingIdFactory, methodsToProcess);
   }
 
   @Override
@@ -50,8 +64,22 @@
   }
 
   public <E extends Exception> void forEachWave(
-      ThrowingConsumer<ProgramMethod, E> consumer, ExecutorService executorService)
+      ThrowingBiConsumer<ProgramMethod, MethodProcessingId, E> consumer) throws E {
+    ReservedMethodProcessingIds methodProcessingIds = methodProcessingIdFactory.reserveIds(wave);
+    int i = 0;
+    for (ProgramMethod method : wave) {
+      consumer.accept(method, methodProcessingIds.get(method, i++));
+    }
+  }
+
+  public <E extends Exception> void forEachWave(
+      ThrowingBiConsumer<ProgramMethod, MethodProcessingId, E> consumer,
+      ExecutorService executorService)
       throws ExecutionException {
-    ThreadUtils.processItems(wave, consumer, executorService);
+    ReservedMethodProcessingIds methodProcessingIds = methodProcessingIdFactory.reserveIds(wave);
+    ThreadUtils.processItems(
+        wave,
+        (method, index) -> consumer.accept(method, methodProcessingIds.get(method, index)),
+        executorService);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/PostMethodProcessor.java b/src/main/java/com/android/tools/r8/ir/conversion/PostMethodProcessor.java
index 7c136f6..0b2476b 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/PostMethodProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/PostMethodProcessor.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.conversion.MethodProcessingId.Factory.ReservedMethodProcessingIds;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.info.OptimizationFeedback;
 import com.android.tools.r8.logging.Log;
@@ -18,6 +19,7 @@
 import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.collections.LongLivedProgramMethodSetBuilder;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import java.util.ArrayDeque;
 import java.util.Collection;
 import java.util.Deque;
@@ -31,8 +33,8 @@
 
   private final AppView<AppInfoWithLiveness> appView;
   private final Map<DexEncodedMethod, Collection<CodeOptimization>> methodsMap;
-  private final Deque<ProgramMethodSet> waves;
-  private ProgramMethodSet wave;
+  private final Deque<SortedProgramMethodSet> waves;
+  private SortedProgramMethodSet wave;
   private final ProgramMethodSet processed = ProgramMethodSet.create();
 
   private PostMethodProcessor(
@@ -141,13 +143,13 @@
     }
   }
 
-  private Deque<ProgramMethodSet> createWaves(AppView<?> appView, CallGraph callGraph) {
+  private Deque<SortedProgramMethodSet> createWaves(AppView<?> appView, CallGraph callGraph) {
     IROrdering shuffle = appView.options().testing.irOrdering;
-    Deque<ProgramMethodSet> waves = new ArrayDeque<>();
+    Deque<SortedProgramMethodSet> waves = new ArrayDeque<>();
 
     int waveCount = 1;
     while (!callGraph.isEmpty()) {
-      ProgramMethodSet wave = callGraph.extractRoots();
+      SortedProgramMethodSet wave = callGraph.extractRoots();
       waves.addLast(wave);
       if (Log.ENABLED && Log.isLoggingEnabledFor(PostMethodProcessor.class)) {
         Log.info(getClass(), "Wave #%d: %d", waveCount++, wave.size());
@@ -167,12 +169,15 @@
     while (!waves.isEmpty()) {
       wave = waves.removeFirst();
       assert wave.size() > 0;
+      ReservedMethodProcessingIds methodProcessingIds =
+          appView.methodProcessingIdFactory().reserveIds(wave);
       ThreadUtils.processItems(
           wave,
-          method -> {
+          (method, index) -> {
             Collection<CodeOptimization> codeOptimizations = methodsMap.get(method.getDefinition());
             assert codeOptimizations != null && !codeOptimizations.isEmpty();
-            forEachMethod(method, codeOptimizations, feedback);
+            forEachMethod(
+                method, codeOptimizations, feedback, methodProcessingIds.get(method, index));
           },
           executorService);
       processed.addAll(wave);
@@ -182,7 +187,8 @@
   private void forEachMethod(
       ProgramMethod method,
       Collection<CodeOptimization> codeOptimizations,
-      OptimizationFeedback feedback) {
+      OptimizationFeedback feedback,
+      MethodProcessingId methodProcessingId) {
     // TODO(b/140766440): Make IRConverter#process receive a list of CodeOptimization to conduct.
     //   Then, we can share IRCode creation there.
     if (appView.options().skipIR) {
@@ -196,7 +202,7 @@
     }
     // TODO(b/140768815): Reprocessing may trigger more methods to revisit. Update waves on-the-fly.
     for (CodeOptimization codeOptimization : codeOptimizations) {
-      codeOptimization.optimize(code, feedback, this);
+      codeOptimization.optimize(code, feedback, this, methodProcessingId);
     }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/PrimaryMethodProcessor.java b/src/main/java/com/android/tools/r8/ir/conversion/PrimaryMethodProcessor.java
index 2a138cb..10f34af 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/PrimaryMethodProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/PrimaryMethodProcessor.java
@@ -7,15 +7,18 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.conversion.CallGraph.Node;
+import com.android.tools.r8.ir.conversion.MethodProcessingId.Factory.ReservedMethodProcessingIds;
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.ThreadUtils;
-import com.android.tools.r8.utils.ThrowingFunction;
+import com.android.tools.r8.utils.ThrowingBiFunction;
 import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.Timing.TimingMerger;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import java.util.ArrayDeque;
+import java.util.Collection;
 import java.util.Deque;
 import java.util.Set;
 import java.util.concurrent.ExecutionException;
@@ -34,15 +37,17 @@
   }
 
   private final CallSiteInformation callSiteInformation;
+  private final MethodProcessingId.Factory methodProcessingIdFactory;
   private final PostMethodProcessor.Builder postMethodProcessorBuilder;
-  private final Deque<ProgramMethodSet> waves;
-  private ProgramMethodSet wave;
+  private final Deque<SortedProgramMethodSet> waves;
+  private SortedProgramMethodSet wave;
 
   private PrimaryMethodProcessor(
       AppView<AppInfoWithLiveness> appView,
       PostMethodProcessor.Builder postMethodProcessorBuilder,
       CallGraph callGraph) {
     this.callSiteInformation = callGraph.createCallSiteInformation(appView);
+    this.methodProcessingIdFactory = appView.methodProcessingIdFactory();
     this.postMethodProcessorBuilder = postMethodProcessorBuilder;
     this.waves = createWaves(appView, callGraph, callSiteInformation);
   }
@@ -73,15 +78,15 @@
     return callSiteInformation;
   }
 
-  private Deque<ProgramMethodSet> createWaves(
+  private Deque<SortedProgramMethodSet> createWaves(
       AppView<?> appView, CallGraph callGraph, CallSiteInformation callSiteInformation) {
     InternalOptions options = appView.options();
-    Deque<ProgramMethodSet> waves = new ArrayDeque<>();
+    Deque<SortedProgramMethodSet> waves = new ArrayDeque<>();
     Set<Node> nodes = callGraph.nodes;
     ProgramMethodSet reprocessing = ProgramMethodSet.create();
     int waveCount = 1;
     while (!nodes.isEmpty()) {
-      ProgramMethodSet wave = callGraph.extractLeaves();
+      SortedProgramMethodSet wave = callGraph.extractLeaves();
       wave.forEach(
           method -> {
             if (callSiteInformation.hasSingleCallSite(method)) {
@@ -112,7 +117,7 @@
    * processed at the same time is passed. This can be used to avoid races in concurrent processing.
    */
   <E extends Exception> void forEachMethod(
-      ThrowingFunction<ProgramMethod, Timing, E> consumer,
+      ThrowingBiFunction<ProgramMethod, MethodProcessingId, Timing, E> consumer,
       WaveStartAction waveStartAction,
       Consumer<ProgramMethodSet> waveDone,
       Timing timing,
@@ -124,15 +129,17 @@
       wave = waves.removeFirst();
       assert wave.size() > 0;
       waveStartAction.notifyWaveStart(wave);
-      merger.add(
+      ReservedMethodProcessingIds methodProcessingIds = methodProcessingIdFactory.reserveIds(wave);
+      Collection<Timing> timings =
           ThreadUtils.processItemsWithResults(
               wave,
-              method -> {
-                Timing time = consumer.apply(method);
+              (method, index) -> {
+                Timing time = consumer.apply(method, methodProcessingIds.get(method, index));
                 time.end();
                 return time;
               },
-              executorService));
+              executorService);
+      merger.add(timings);
       waveDone.accept(wave);
     }
     merger.end();
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/D8NestBasedAccessDesugaring.java b/src/main/java/com/android/tools/r8/ir/desugar/D8NestBasedAccessDesugaring.java
index f691760..e66d342 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/D8NestBasedAccessDesugaring.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/D8NestBasedAccessDesugaring.java
@@ -23,7 +23,7 @@
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.conversion.IRConverter;
 import com.android.tools.r8.utils.ThreadUtils;
-import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.List;
@@ -125,7 +125,7 @@
 
   private void optimizeDeferredBridgesConcurrently(
       ExecutorService executorService, IRConverter converter) throws ExecutionException {
-    ProgramMethodSet methods = ProgramMethodSet.create();
+    SortedProgramMethodSet methods = SortedProgramMethodSet.create();
     methods.addAll(bridges.values());
     methods.addAll(getFieldBridges.values());
     methods.addAll(putFieldBridges.values());
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryAPIConverter.java b/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryAPIConverter.java
index ca7fdec..88108f9 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryAPIConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryAPIConverter.java
@@ -33,7 +33,7 @@
 import com.android.tools.r8.utils.OptionalBool;
 import com.android.tools.r8.utils.StringDiagnostic;
 import com.android.tools.r8.utils.WorkList;
-import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
 import java.util.Collections;
@@ -284,19 +284,19 @@
     if (appView.enableWholeProgramOptimizations()) {
       return;
     }
-    ProgramMethodSet callbacks = generateCallbackMethods();
+    SortedProgramMethodSet callbacks = generateCallbackMethods();
     irConverter.processMethodsConcurrently(callbacks, executorService);
     wrapperSynthesizor.finalizeWrappersForD8(builder, irConverter, executorService);
   }
 
-  public ProgramMethodSet generateCallbackMethods() {
+  public SortedProgramMethodSet generateCallbackMethods() {
     if (appView.options().testing.trackDesugaredAPIConversions) {
       generateTrackDesugaredAPIWarnings(trackedAPIs, "");
       generateTrackDesugaredAPIWarnings(trackedCallBackAPIs, "callback ");
       trackedAPIs.clear();
       trackedCallBackAPIs.clear();
     }
-    ProgramMethodSet allCallbackMethods = ProgramMethodSet.create();
+    SortedProgramMethodSet allCallbackMethods = SortedProgramMethodSet.create();
     pendingCallBackMethods.forEach(
         (clazz, callbacks) -> {
           List<DexEncodedMethod> newVirtualMethods = new ArrayList<>();
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryRetargeter.java b/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryRetargeter.java
index 408b152..9d14d61 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryRetargeter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryRetargeter.java
@@ -29,7 +29,7 @@
 import com.android.tools.r8.ir.code.InvokeStatic;
 import com.android.tools.r8.ir.conversion.IRConverter;
 import com.android.tools.r8.utils.StringDiagnostic;
-import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
@@ -271,7 +271,7 @@
         map.putIfAbsent(emulatedDispatchMethod.holder, new ArrayList<>(1));
         map.get(emulatedDispatchMethod.holder).add(emulatedDispatchMethod);
       }
-      ProgramMethodSet addedMethods = ProgramMethodSet.create();
+      SortedProgramMethodSet addedMethods = SortedProgramMethodSet.create();
       for (DexProgramClass clazz : appView.appInfo().classes()) {
         if (clazz.superType == null) {
           assert clazz.type == appView.dexItemFactory().objectType : clazz.type.toSourceString();
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
index 878a5e0..79a8a40 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
@@ -47,7 +47,7 @@
 import com.android.tools.r8.utils.IterableUtils;
 import com.android.tools.r8.utils.Pair;
 import com.android.tools.r8.utils.StringDiagnostic;
-import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
 import java.util.Arrays;
@@ -112,7 +112,7 @@
 
   // All forwarding methods generated during desugaring. We don't synchronize access
   // to this collection since it is only filled in ClassProcessor running synchronously.
-  private final ProgramMethodSet synthesizedMethods = ProgramMethodSet.create();
+  private final SortedProgramMethodSet synthesizedMethods = SortedProgramMethodSet.create();
 
   // Caches default interface method info for already processed interfaces.
   private final Map<DexType, DefaultMethodsHelper.Collection> cache = new ConcurrentHashMap<>();
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
index aa47bdc..8a7b983 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
@@ -26,7 +26,7 @@
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.conversion.IRConverter;
 import com.android.tools.r8.utils.DescriptorUtils;
-import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
 import com.google.common.collect.ImmutableSet;
@@ -80,7 +80,7 @@
   private void synthesizeAccessibilityBridgesForLambdaClassesD8(
       Collection<LambdaClass> lambdaClasses, IRConverter converter, ExecutorService executorService)
       throws ExecutionException {
-    ProgramMethodSet nonDexAccessibilityBridges = ProgramMethodSet.create();
+    SortedProgramMethodSet nonDexAccessibilityBridges = SortedProgramMethodSet.create();
     for (LambdaClass lambdaClass : lambdaClasses) {
       // This call may cause originalMethodSignatures to be updated.
       ProgramMethod accessibilityBridge = lambdaClass.target.ensureAccessibilityIfNeeded(true);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
index 7a81f73..1dfaa39 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
@@ -53,7 +53,7 @@
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.ThrowingConsumer;
 import com.android.tools.r8.utils.collections.LongLivedProgramMethodSetBuilder;
-import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
 import com.google.common.collect.Sets;
@@ -454,7 +454,8 @@
     if (methodsToReprocess.isEmpty()) {
       return;
     }
-    ProgramMethodSet methods = methodsToReprocess.build(appView);
+    SortedProgramMethodSet methods =
+        methodsToReprocess.build(appView, ignore -> SortedProgramMethodSet.create());
     converter.processMethodsConcurrently(methods, executorService);
     assert methods.stream()
         .map(DexClassAndMethod::getDefinition)
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMemberOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMemberOptimizer.java
index 0c7393b..3a7e099 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMemberOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMemberOptimizer.java
@@ -17,6 +17,7 @@
 import com.android.tools.r8.ir.code.InvokeMethod;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.conversion.CodeOptimization;
+import com.android.tools.r8.ir.conversion.MethodProcessingId;
 import com.android.tools.r8.ir.conversion.MethodProcessor;
 import com.android.tools.r8.ir.optimize.info.OptimizationFeedback;
 import com.google.common.collect.Sets;
@@ -108,7 +109,10 @@
 
   @Override
   public void optimize(
-      IRCode code, OptimizationFeedback feedback, MethodProcessor methodProcessor) {
+      IRCode code,
+      OptimizationFeedback feedback,
+      MethodProcessor methodProcessor,
+      MethodProcessingId methodProcessingId) {
     Set<Value> affectedValues = Sets.newIdentityHashSet();
     InstructionListIterator instructionIterator = code.instructionListIterator();
     while (instructionIterator.hasNext()) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
index 5742de4..6a37390 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
@@ -32,6 +32,7 @@
 import com.android.tools.r8.ir.code.StaticPut;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.conversion.IRConverter;
+import com.android.tools.r8.ir.conversion.MethodProcessingId;
 import com.android.tools.r8.ir.conversion.MethodProcessor;
 import com.android.tools.r8.ir.conversion.OneTimeMethodProcessor;
 import com.android.tools.r8.ir.optimize.ClassInitializerDefaultsOptimization.ClassInitializerDefaultsResult;
@@ -43,6 +44,7 @@
 import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.TraversalContinuation;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
 import com.google.common.collect.ImmutableList;
@@ -69,7 +71,7 @@
   private final ClassStaticizer classStaticizer;
   private final IRConverter converter;
 
-  private final ProgramMethodSet methodsToReprocess = ProgramMethodSet.create();
+  private final SortedProgramMethodSet methodsToReprocess = SortedProgramMethodSet.create();
 
   // Optimization order matters, hence a collection that preserves orderings.
   private final Map<DexEncodedMethod, ImmutableList.Builder<BiConsumer<IRCode, MethodProcessor>>>
@@ -354,14 +356,16 @@
    */
   private void processMethodsConcurrently(
       OptimizationFeedback feedback, ExecutorService executorService) throws ExecutionException {
-    OneTimeMethodProcessor methodProcessor = OneTimeMethodProcessor.getInstance(methodsToReprocess);
+    OneTimeMethodProcessor methodProcessor =
+        OneTimeMethodProcessor.create(methodsToReprocess, appView);
     methodProcessor.forEachWave(
-        method ->
+        (method, methodProcessingId) ->
             forEachMethod(
                 method,
                 processingQueue.get(method.getDefinition()).build(),
                 feedback,
-                methodProcessor),
+                methodProcessor,
+                methodProcessingId),
         executorService);
     // TODO(b/140767158): No need to clear if we can do every thing in one go.
     methodsToReprocess.clear();
@@ -373,7 +377,8 @@
       ProgramMethod method,
       Collection<BiConsumer<IRCode, MethodProcessor>> codeOptimizations,
       OptimizationFeedback feedback,
-      OneTimeMethodProcessor methodProcessor) {
+      OneTimeMethodProcessor methodProcessor,
+      MethodProcessingId methodProcessingId) {
     IRCode code = method.buildIR(appView);
     codeOptimizations.forEach(codeOptimization -> codeOptimization.accept(code, methodProcessor));
     CodeRewriter.removeAssumeInstructions(appView, code);
diff --git a/src/main/java/com/android/tools/r8/shaking/ClassInitFieldSynthesizer.java b/src/main/java/com/android/tools/r8/shaking/ClassInitFieldSynthesizer.java
index 60bb9d7..64b1ef0 100644
--- a/src/main/java/com/android/tools/r8/shaking/ClassInitFieldSynthesizer.java
+++ b/src/main/java/com/android/tools/r8/shaking/ClassInitFieldSynthesizer.java
@@ -33,7 +33,7 @@
   }
 
   public void run(ExecutorService executorService) throws ExecutionException {
-    ThreadUtils.processItems(
+    ThreadUtils.processMap(
         appView.appInfo().initClassReferences, this::synthesizeClassInitField, executorService);
     appView.setInitClassLens(lensBuilder.build());
   }
diff --git a/src/main/java/com/android/tools/r8/utils/ForEachableUtils.java b/src/main/java/com/android/tools/r8/utils/ForEachableUtils.java
new file mode 100644
index 0000000..7f1a32b
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/ForEachableUtils.java
@@ -0,0 +1,12 @@
+// 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.utils;
+
+public class ForEachableUtils {
+
+  public static <T> ForEachable<T> empty() {
+    return consumer -> {};
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index e92effc..6b1fb12 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -37,6 +37,7 @@
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.inspector.internal.InspectorImpl;
 import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.conversion.MethodProcessingId;
 import com.android.tools.r8.ir.desugar.DesugaredLibraryConfiguration;
 import com.android.tools.r8.ir.optimize.Inliner;
 import com.android.tools.r8.origin.Origin;
@@ -48,7 +49,7 @@
 import com.android.tools.r8.shaking.ProguardConfigurationRule;
 import com.android.tools.r8.utils.IROrdering.IdentityIROrdering;
 import com.android.tools.r8.utils.IROrdering.NondeterministicIROrdering;
-import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.ImmutableList;
@@ -1092,7 +1093,9 @@
 
     public BiConsumer<AppInfoWithLiveness, Enqueuer.Mode> enqueuerInspector = null;
 
-    public Consumer<Deque<ProgramMethodSet>> waveModifier = waves -> {};
+    public BiConsumer<ProgramMethod, MethodProcessingId> methodProcessingIdConsumer = null;
+
+    public Consumer<Deque<SortedProgramMethodSet>> waveModifier = waves -> {};
 
     /**
      * If this flag is enabled, we will also compute the set of possible targets for invoke-
diff --git a/src/main/java/com/android/tools/r8/utils/ThreadUtils.java b/src/main/java/com/android/tools/r8/utils/ThreadUtils.java
index 1349732..5f704fa 100644
--- a/src/main/java/com/android/tools/r8/utils/ThreadUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ThreadUtils.java
@@ -21,49 +21,89 @@
   public static <T, R, E extends Exception> Collection<R> processItemsWithResults(
       Iterable<T> items, ThrowingFunction<T, R, E> consumer, ExecutorService executorService)
       throws ExecutionException {
-    return processItemsWithResults(items::forEach, consumer, executorService);
+    return processItemsWithResults(items, (item, i) -> consumer.apply(item), executorService);
   }
 
-  public static <T, U, R, E extends Exception> Collection<R> processItemsWithResults(
-      Map<T, U> items, ThrowingBiFunction<T, U, R, E> consumer, ExecutorService executorService)
+  public static <T, R, E extends Exception> Collection<R> processItemsWithResults(
+      Iterable<T> items,
+      ThrowingReferenceIntFunction<T, R, E> consumer,
+      ExecutorService executorService)
       throws ExecutionException {
-    return processItemsWithResults(
-        items.entrySet(), arg -> consumer.apply(arg.getKey(), arg.getValue()), executorService);
+    return processItemsWithResults(items::forEach, consumer, executorService);
   }
 
   public static <T, R, E extends Exception> Collection<R> processItemsWithResults(
       ForEachable<T> items, ThrowingFunction<T, R, E> consumer, ExecutorService executorService)
       throws ExecutionException {
+    return processItemsWithResults(items, (item, i) -> consumer.apply(item), executorService);
+  }
+
+  public static <T, R, E extends Exception> Collection<R> processItemsWithResults(
+      ForEachable<T> items,
+      ThrowingReferenceIntFunction<T, R, E> consumer,
+      ExecutorService executorService)
+      throws ExecutionException {
+    IntBox i = new IntBox();
     List<Future<R>> futures = new ArrayList<>();
-    items.forEach(item -> futures.add(executorService.submit(() -> consumer.apply(item))));
+    items.forEach(
+        item ->
+            futures.add(executorService.submit(() -> consumer.apply(item, i.getAndIncrement()))));
     return awaitFuturesWithResults(futures);
   }
 
   public static <T, E extends Exception> void processItems(
       Iterable<T> items, ThrowingConsumer<T, E> consumer, ExecutorService executorService)
       throws ExecutionException {
-    processItems(items::forEach, consumer, executorService);
+    processItems(items, (item, i) -> consumer.accept(item), executorService);
   }
 
-  public static <T, U, E extends Exception> void processItems(
-      Map<T, U> items, ThrowingBiConsumer<T, U, E> consumer, ExecutorService executorService)
+  public static <T, E extends Exception> void processItems(
+      Iterable<T> items,
+      ThrowingReferenceIntConsumer<T, E> consumer,
+      ExecutorService executorService)
       throws ExecutionException {
-    processItems(
-        items.entrySet(), arg -> consumer.accept(arg.getKey(), arg.getValue()), executorService);
+    processItems(items::forEach, consumer, executorService);
   }
 
   public static <T, E extends Exception> void processItems(
       ForEachable<T> items, ThrowingConsumer<T, E> consumer, ExecutorService executorService)
       throws ExecutionException {
+    processItems(items, (item, i) -> consumer.accept(item), executorService);
+  }
+
+  public static <T, E extends Exception> void processItems(
+      ForEachable<T> items,
+      ThrowingReferenceIntConsumer<T, E> consumer,
+      ExecutorService executorService)
+      throws ExecutionException {
     processItemsWithResults(
         items,
-        arg -> {
-          consumer.accept(arg);
+        (item, i) -> {
+          consumer.accept(item, i);
           return null;
         },
         executorService);
   }
 
+  public static <T, U, E extends Exception> void processMap(
+      Map<T, U> items, ThrowingBiConsumer<T, U, E> consumer, ExecutorService executorService)
+      throws ExecutionException {
+    processMapWithResults(
+        items,
+        (key, value) -> {
+          consumer.accept(key, value);
+          return null;
+        },
+        executorService);
+  }
+
+  public static <T, U, R, E extends Exception> Collection<R> processMapWithResults(
+      Map<T, U> items, ThrowingBiFunction<T, U, R, E> consumer, ExecutorService executorService)
+      throws ExecutionException {
+    return processItemsWithResults(
+        items.entrySet(), arg -> consumer.apply(arg.getKey(), arg.getValue()), executorService);
+  }
+
   public static void awaitFutures(Iterable<? extends Future<?>> futures)
       throws ExecutionException {
     Iterator<? extends Future<?>> futureIterator = futures.iterator();
diff --git a/src/main/java/com/android/tools/r8/utils/ThrowingReferenceIntConsumer.java b/src/main/java/com/android/tools/r8/utils/ThrowingReferenceIntConsumer.java
new file mode 100644
index 0000000..472a81c
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/ThrowingReferenceIntConsumer.java
@@ -0,0 +1,17 @@
+// Copyright (c) 2017, 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.utils;
+
+import java.util.function.BiConsumer;
+
+/**
+ * Similar to a {@link BiConsumer} but throws a single {@link Throwable}.
+ *
+ * @param <T> the type of the first argument
+ * @param <E> the type of the {@link Throwable}
+ */
+@FunctionalInterface
+public interface ThrowingReferenceIntConsumer<T, E extends Throwable> {
+  void accept(T t, int i) throws E;
+}
diff --git a/src/main/java/com/android/tools/r8/utils/ThrowingReferenceIntFunction.java b/src/main/java/com/android/tools/r8/utils/ThrowingReferenceIntFunction.java
new file mode 100644
index 0000000..0f63641
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/ThrowingReferenceIntFunction.java
@@ -0,0 +1,17 @@
+// 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.utils;
+
+import java.util.function.Function;
+
+/**
+ * Similar to a {@link Function} but throws a single {@link Throwable}.
+ *
+ * @param <T> the type of the input
+ * @param <E> the type of the {@link Throwable}
+ */
+@FunctionalInterface
+public interface ThrowingReferenceIntFunction<T, R, E extends Throwable> {
+  R apply(T t, int i) throws E;
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/LongLivedProgramMethodSetBuilder.java b/src/main/java/com/android/tools/r8/utils/collections/LongLivedProgramMethodSetBuilder.java
index b76c14c..954eae1 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/LongLivedProgramMethodSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/LongLivedProgramMethodSetBuilder.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.google.common.collect.Sets;
 import java.util.Set;
+import java.util.function.IntFunction;
 
 public class LongLivedProgramMethodSetBuilder {
 
@@ -27,7 +28,12 @@
   }
 
   public ProgramMethodSet build(AppView<AppInfoWithLiveness> appView) {
-    ProgramMethodSet result = ProgramMethodSet.create(methods.size());
+    return build(appView, ProgramMethodSet::create);
+  }
+
+  public <T extends ProgramMethodSet> T build(
+      AppView<AppInfoWithLiveness> appView, IntFunction<T> factory) {
+    T result = factory.apply(methods.size());
     for (DexMethod oldMethod : methods) {
       DexMethod method = appView.graphLense().getRenamedMethodSignature(oldMethod);
       DexProgramClass holder = appView.definitionForHolder(method).asProgramClass();
diff --git a/src/main/java/com/android/tools/r8/utils/collections/ProgramMethodSet.java b/src/main/java/com/android/tools/r8/utils/collections/ProgramMethodSet.java
index 1795899..14d938d 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/ProgramMethodSet.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/ProgramMethodSet.java
@@ -22,9 +22,10 @@
 
   private static final ProgramMethodSet EMPTY = new ProgramMethodSet(ImmutableMap.of());
 
+  private boolean deterministicOrdering = false;
   private Map<DexMethod, ProgramMethod> backing;
 
-  private ProgramMethodSet(Map<DexMethod, ProgramMethod> backing) {
+  ProgramMethodSet(Map<DexMethod, ProgramMethod> backing) {
     this.backing = backing;
   }
 
diff --git a/src/main/java/com/android/tools/r8/utils/collections/SortedProgramMethodSet.java b/src/main/java/com/android/tools/r8/utils/collections/SortedProgramMethodSet.java
new file mode 100644
index 0000000..4c6db49
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/SortedProgramMethodSet.java
@@ -0,0 +1,48 @@
+// 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.utils.collections;
+
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.utils.ForEachable;
+import com.android.tools.r8.utils.ForEachableUtils;
+import java.util.Comparator;
+import java.util.Set;
+import java.util.TreeMap;
+import java.util.TreeSet;
+
+public class SortedProgramMethodSet extends ProgramMethodSet {
+
+  private SortedProgramMethodSet(TreeMap<DexMethod, ProgramMethod> backing) {
+    super(backing);
+  }
+
+  public static SortedProgramMethodSet create() {
+    return create(ForEachableUtils.empty());
+  }
+
+  public static SortedProgramMethodSet create(ProgramMethod method) {
+    SortedProgramMethodSet result = create();
+    result.add(method);
+    return result;
+  }
+
+  public static SortedProgramMethodSet create(ForEachable<ProgramMethod> methods) {
+    SortedProgramMethodSet result =
+        new SortedProgramMethodSet(new TreeMap<>(DexMethod::slowCompareTo));
+    methods.forEach(result::add);
+    return result;
+  }
+
+  @Override
+  public Set<DexEncodedMethod> toDefinitionSet() {
+    Comparator<DexEncodedMethod> comparator =
+        (x, y) -> x.getReference().slowCompareTo(y.getReference());
+    Set<DexEncodedMethod> definitions = new TreeSet<>(comparator);
+    forEach(method -> definitions.add(method.getDefinition()));
+    return definitions;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/internal/CompilationTestBase.java b/src/test/java/com/android/tools/r8/internal/CompilationTestBase.java
index 07b1906..4685e38 100644
--- a/src/test/java/com/android/tools/r8/internal/CompilationTestBase.java
+++ b/src/test/java/com/android/tools/r8/internal/CompilationTestBase.java
@@ -38,6 +38,9 @@
 import com.android.tools.r8.utils.codeinspector.FoundMethodSubject;
 import com.google.common.io.ByteStreams;
 import com.google.common.io.Closer;
+import it.unimi.dsi.fastutil.ints.IntList;
+import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
+import it.unimi.dsi.fastutil.ints.IntSet;
 import java.io.File;
 import java.io.IOException;
 import java.io.InputStream;
@@ -376,4 +379,18 @@
       }
     }
   }
+
+  public void assertIdenticalMethodProcessingIds(
+      Map<String, IntList> methodProcessingIds, Map<String, IntList> otherMethodProcessingIds) {
+    assertEquals(methodProcessingIds, otherMethodProcessingIds);
+  }
+
+  public void assertUniqueMethodProcessingIds(Map<String, IntList> methodProcessingIds) {
+    IntSet seen = new IntOpenHashSet();
+    for (IntList ids : methodProcessingIds.values()) {
+      for (int id : ids) {
+        assertTrue(seen.add(id));
+      }
+    }
+  }
 }
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 cba792d..ec6f04b 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreDeterministicTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreDeterministicTest.java
@@ -13,14 +13,19 @@
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.IROrdering.NondeterministicIROrdering;
+import it.unimi.dsi.fastutil.ints.IntArrayList;
+import it.unimi.dsi.fastutil.ints.IntList;
 import java.nio.file.Path;
 import java.nio.file.Paths;
+import java.util.HashMap;
+import java.util.Map;
 import org.junit.Test;
 
 public class R8GMSCoreDeterministicTest extends GMSCoreCompilationTestBase {
 
   private static class CompilationResult {
     AndroidApp app;
+    Map<String, IntList> methodProcessingIds = new HashMap<>();
     String proguardMap;
   }
 
@@ -44,6 +49,13 @@
               options.threadCount = 1;
               // Ignore the missing classes.
               options.ignoreMissingClasses = true;
+              // Store the generated method processing ids.
+              options.testing.methodProcessingIdConsumer =
+                  (method, methodProcessingId) ->
+                      result
+                          .methodProcessingIds
+                          .computeIfAbsent(method.toSourceString(), ignore -> new IntArrayList())
+                          .add(methodProcessingId.getPrimaryId());
               // Store the generated Proguard map.
               options.proguardMapConsumer =
                   ToolHelper.consumeString(proguardMap -> result.proguardMap = proguardMap);
@@ -65,6 +77,8 @@
 
     // Verify that the result of the two compilations was the same.
     assertIdenticalApplications(result1.app, result2.app);
+    assertIdenticalMethodProcessingIds(result1.methodProcessingIds, result2.methodProcessingIds);
+    assertUniqueMethodProcessingIds(result1.methodProcessingIds);
     assertEquals(result1.proguardMap, result2.proguardMap);
   }
 }
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreLatestTreeShakeJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreLatestTreeShakeJarVerificationTest.java
index e8417f1..d9d4c20 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreLatestTreeShakeJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreLatestTreeShakeJarVerificationTest.java
@@ -9,7 +9,11 @@
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.utils.AndroidApp;
 import com.google.common.collect.ImmutableList;
+import it.unimi.dsi.fastutil.ints.IntArrayList;
+import it.unimi.dsi.fastutil.ints.IntList;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
 import org.junit.Test;
 
 public class R8GMSCoreLatestTreeShakeJarVerificationTest
@@ -23,6 +27,8 @@
     List<String> additionalProguardConfiguration =
         ImmutableList.of(
             ToolHelper.PROGUARD_SETTINGS_FOR_INTERNAL_APPS + "GmsCore_proguard.config");
+
+    Map<String, IntList> methodProcessingIds = new HashMap<>();
     AndroidApp app1 =
         buildAndTreeShakeFromDeployJar(
             CompilationMode.RELEASE,
@@ -31,9 +37,16 @@
             GMSCORE_LATEST_MAX_SIZE,
             additionalProguardConfiguration,
             options -> {
+              options.testing.methodProcessingIdConsumer =
+                  (method, methodProcessingId) ->
+                      methodProcessingIds
+                          .computeIfAbsent(method.toSourceString(), ignore -> new IntArrayList())
+                          .add(methodProcessingId.getPrimaryId());
               options.proguardMapConsumer =
                   ToolHelper.consumeString(proguardMap -> this.proguardMap1 = proguardMap);
             });
+
+    Map<String, IntList> otherMethodProcessingIds = new HashMap<>();
     AndroidApp app2 =
         buildAndTreeShakeFromDeployJar(
             CompilationMode.RELEASE,
@@ -42,12 +55,19 @@
             GMSCORE_LATEST_MAX_SIZE,
             additionalProguardConfiguration,
             options -> {
+              options.testing.methodProcessingIdConsumer =
+                  (method, methodProcessingId) ->
+                      otherMethodProcessingIds
+                          .computeIfAbsent(method.toSourceString(), ignore -> new IntArrayList())
+                          .add(methodProcessingId.getPrimaryId());
               options.proguardMapConsumer =
                   ToolHelper.consumeString(proguardMap -> this.proguardMap2 = proguardMap);
             });
 
     // Verify that the result of the two compilations was the same.
     assertIdenticalApplications(app1, app2);
+    assertIdenticalMethodProcessingIds(methodProcessingIds, otherMethodProcessingIds);
+    assertUniqueMethodProcessingIds(methodProcessingIds);
     assertEquals(proguardMap1, proguardMap2);
   }
 }
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 be62787..18d0060 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
@@ -11,7 +11,11 @@
 import com.android.tools.r8.R8RunArtTestsTest.CompilerUnderTest;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.utils.AndroidApp;
+import it.unimi.dsi.fastutil.ints.IntArrayList;
+import it.unimi.dsi.fastutil.ints.IntList;
 import java.io.File;
+import java.util.HashMap;
+import java.util.Map;
 import org.junit.Test;
 
 public class R8GMSCoreV10DeployJarVerificationTest extends GMSCoreDeployJarVerificationTest {
@@ -23,32 +27,50 @@
   public void buildFromDeployJar() throws Exception {
     // TODO(tamaskenez): set hasReference = true when we have the noshrink file for V10
     File tempFolder = temp.newFolder();
+
     File app1Zip = new File(tempFolder, "app1.zip");
-    File app2Zip = new File(tempFolder, "app2.zip");
+    Map<String, IntList> methodProcessingIds = new HashMap<>();
     AndroidApp app1 =
         buildFromDeployJar(
             CompilerUnderTest.R8,
             CompilationMode.RELEASE,
             GMSCoreCompilationTestBase.GMSCORE_V10_DIR,
             false,
-            options ->
-                options.proguardMapConsumer =
-                    ToolHelper.consumeString(proguardMap -> this.proguardMap1 = proguardMap),
+            options -> {
+              options.testing.methodProcessingIdConsumer =
+                  (method, methodProcessingId) ->
+                      methodProcessingIds
+                          .computeIfAbsent(method.toSourceString(), ignore -> new IntArrayList())
+                          .add(methodProcessingId.getPrimaryId());
+              options.proguardMapConsumer =
+                  ToolHelper.consumeString(proguardMap -> this.proguardMap1 = proguardMap);
+            },
             () -> new ArchiveConsumer(app1Zip.toPath(), true));
+
+    File app2Zip = new File(tempFolder, "app2.zip");
+    Map<String, IntList> otherMethodProcessingIds = new HashMap<>();
     AndroidApp app2 =
         buildFromDeployJar(
             CompilerUnderTest.R8,
             CompilationMode.RELEASE,
             GMSCoreCompilationTestBase.GMSCORE_V10_DIR,
             false,
-            options ->
-                options.proguardMapConsumer =
-                    ToolHelper.consumeString(proguardMap -> this.proguardMap2 = proguardMap),
+            options -> {
+              options.testing.methodProcessingIdConsumer =
+                  (method, methodProcessingId) ->
+                      otherMethodProcessingIds
+                          .computeIfAbsent(method.toSourceString(), ignore -> new IntArrayList())
+                          .add(methodProcessingId.getPrimaryId());
+              options.proguardMapConsumer =
+                  ToolHelper.consumeString(proguardMap -> this.proguardMap2 = proguardMap);
+            },
             () -> new ArchiveConsumer(app2Zip.toPath(), true));
 
     // Verify that the result of the two compilations was the same.
     assertIdenticalApplications(app1, app2);
     assertIdenticalZipFiles(app1Zip, app2Zip);
+    assertIdenticalMethodProcessingIds(methodProcessingIds, otherMethodProcessingIds);
+    assertUniqueMethodProcessingIds(methodProcessingIds);
     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 00a751a..772b75b 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
@@ -8,6 +8,10 @@
 import com.android.tools.r8.CompilationMode;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.utils.AndroidApp;
+import it.unimi.dsi.fastutil.ints.IntArrayList;
+import it.unimi.dsi.fastutil.ints.IntList;
+import java.util.HashMap;
+import java.util.Map;
 import org.junit.Test;
 
 public class R8GMSCoreV10TreeShakeJarVerificationTest
@@ -19,27 +23,43 @@
   @Test
   public void buildAndTreeShakeFromDeployJar() throws Exception {
     // TODO(tamaskenez): set hasReference = true when we have the noshrink file for V10
+    Map<String, IntList> methodProcessingIds = new HashMap<>();
     AndroidApp app1 =
         buildAndTreeShakeFromDeployJar(
             CompilationMode.RELEASE,
             GMSCORE_V10_DIR,
             false,
             GMSCORE_V10_MAX_SIZE,
-            options ->
-                options.proguardMapConsumer =
-                    ToolHelper.consumeString(proguardMap -> this.proguardMap1 = proguardMap));
+            options -> {
+              options.testing.methodProcessingIdConsumer =
+                  (method, methodProcessingId) ->
+                      methodProcessingIds
+                          .computeIfAbsent(method.toSourceString(), ignore -> new IntArrayList())
+                          .add(methodProcessingId.getPrimaryId());
+              options.proguardMapConsumer =
+                  ToolHelper.consumeString(proguardMap -> this.proguardMap1 = proguardMap);
+            });
+    Map<String, IntList> otherMethodProcessingIds = new HashMap<>();
     AndroidApp app2 =
         buildAndTreeShakeFromDeployJar(
             CompilationMode.RELEASE,
             GMSCORE_V10_DIR,
             false,
             GMSCORE_V10_MAX_SIZE,
-            options ->
-                options.proguardMapConsumer =
-                    ToolHelper.consumeString(proguardMap -> this.proguardMap2 = proguardMap));
+            options -> {
+              options.testing.methodProcessingIdConsumer =
+                  (method, methodProcessingId) ->
+                      otherMethodProcessingIds
+                          .computeIfAbsent(method.toSourceString(), ignore -> new IntArrayList())
+                          .add(methodProcessingId.getPrimaryId());
+              options.proguardMapConsumer =
+                  ToolHelper.consumeString(proguardMap -> this.proguardMap2 = proguardMap);
+            });
 
     // Verify that the result of the two compilations was the same.
     assertIdenticalApplications(app1, app2);
+    assertIdenticalMethodProcessingIds(methodProcessingIds, otherMethodProcessingIds);
+    assertUniqueMethodProcessingIds(methodProcessingIds);
     assertEquals(proguardMap1, proguardMap2);
   }
 }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/FieldWithDefaultValueAssignmentAfterDefaultsOptimizationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/FieldWithDefaultValueAssignmentAfterDefaultsOptimizationTest.java
index 8943139..faf62b7 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/FieldWithDefaultValueAssignmentAfterDefaultsOptimizationTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/FieldWithDefaultValueAssignmentAfterDefaultsOptimizationTest.java
@@ -12,6 +12,7 @@
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import java.util.Deque;
 import java.util.Optional;
 import org.junit.Test;
@@ -45,7 +46,7 @@
         .assertSuccessWithOutputLines("42");
   }
 
-  private void waveModifier(Deque<ProgramMethodSet> waves) {
+  private void waveModifier(Deque<SortedProgramMethodSet> waves) {
     ProgramMethodSet initialWave = waves.getFirst();
     Optional<ProgramMethod> printFieldMethod =
         initialWave.stream()
@@ -54,7 +55,7 @@
     assertTrue(printFieldMethod.isPresent());
     initialWave.remove(printFieldMethod.get().getDefinition());
 
-    ProgramMethodSet lastWave = ProgramMethodSet.create();
+    SortedProgramMethodSet lastWave = SortedProgramMethodSet.create();
     lastWave.add(printFieldMethod.get());
     waves.addLast(lastWave);
   }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/FieldWriteBeforeFieldReadTest.java b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/FieldWriteBeforeFieldReadTest.java
index b493f1d..f5b13eb 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/FieldWriteBeforeFieldReadTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/FieldWriteBeforeFieldReadTest.java
@@ -18,7 +18,7 @@
 import com.android.tools.r8.utils.IterableUtils;
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
-import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import java.util.function.Function;
 import java.util.function.Predicate;
 import org.junit.Test;
@@ -49,7 +49,7 @@
             options -> {
               options.testing.waveModifier =
                   (waves) -> {
-                    Function<String, Predicate<ProgramMethodSet>> wavePredicate =
+                    Function<String, Predicate<SortedProgramMethodSet>> wavePredicate =
                         methodName ->
                             wave ->
                                 wave.stream()