Merge commit '4b113c4fd6690c15b6741629f7a29be4b433e81c' into dev-release
diff --git a/.gitignore b/.gitignore
index 5885615..ec03160 100644
--- a/.gitignore
+++ b/.gitignore
@@ -92,10 +92,12 @@
 third_party/jsr223-api-1.0.tar.gz
 third_party/junit
 third_party/junit.tar.gz
-third_party/kotlin
-third_party/kotlin-compiler-1.3.41
-third_party/kotlin-compiler-1.3.41.tar.gz
-third_party/kotlin.tar.gz
+third_party/kotlin/kotlin-compiler-1.3.11.tar.gz
+third_party/kotlin/kotlin-compiler-1.3.11
+third_party/kotlin/kotlin-compiler-1.3.41.tar.gz
+third_party/kotlin/kotlin-compiler-1.3.41
+third_party/kotlin/kotlin-compiler-1.3.72.tar.gz
+third_party/kotlin/kotlin-compiler-1.3.72
 third_party/nest/*
 third_party/openjdk/desugar_jdk_libs
 third_party/openjdk/desugar_jdk_libs.tar.gz
diff --git a/build.gradle b/build.gradle
index 8d1eb6b..90ad4ab 100644
--- a/build.gradle
+++ b/build.gradle
@@ -43,7 +43,7 @@
     gsonVersion = '2.7'
     junitVersion = '4.13-beta-2'
     mockitoVersion = '2.10.0'
-    kotlinVersion = '1.3.41'
+    kotlinVersion = '1.3.72'
     kotlinExtMetadataJVMVersion = '0.1.0'
     smaliVersion = '2.2b4'
     errorproneVersion = '2.3.2'
@@ -324,8 +324,9 @@
                 "jsr223-api-1.0",
                 "rhino-1.7.10",
                 "rhino-android-1.1.1",
-                "kotlin",
-                "kotlin-compiler-1.3.41",
+                "kotlin/kotlin-compiler-1.3.11",
+                "kotlin/kotlin-compiler-1.3.41",
+                "kotlin/kotlin-compiler-1.3.72",
                 "openjdk/openjdk-rt-1.8",
                 "openjdk/desugar_jdk_libs",
                 "openjdk/jdk-11-test",
@@ -1134,7 +1135,7 @@
     }
     def kotlinResourcesDir = file("src/test/debugTestResourcesKotlin")
     def kotlinHostJar = "debug_test_resources_kotlin.jar"
-    task "jar_debugTestResourcesKotlin"(type: kotlin.Kotlinc) {
+    task "jar_debugTestResourcesKotlin"(type: kotlin.Kotlinc, dependsOn: downloadDeps) {
         source = fileTree(dir: kotlinResourcesDir, include: '**/*.kt')
         destination = file("build/test/${kotlinHostJar}")
     }
diff --git a/buildSrc/src/main/java/kotlin/Kotlinc.java b/buildSrc/src/main/java/kotlin/Kotlinc.java
index 68924ae..efb39aa 100644
--- a/buildSrc/src/main/java/kotlin/Kotlinc.java
+++ b/buildSrc/src/main/java/kotlin/Kotlinc.java
@@ -28,8 +28,9 @@
       ? "kotlinc.bat"
       : "kotlinc";
 
-  private static final Path kotlincExecPath = Paths
-      .get("third_party", "kotlin", "kotlinc", "bin", kotlincExecName);
+  private static final Path kotlincExecPath =
+      Paths.get(
+          "third_party", "kotlin", "kotlin-compiler-1.3.72", "kotlinc", "bin", kotlincExecName);
 
   enum KotlinTargetVersion {
     JAVA_6("1.6"),
diff --git a/src/main/java/com/android/tools/r8/JarDiff.java b/src/main/java/com/android/tools/r8/JarDiff.java
index 1460cda..817b461 100644
--- a/src/main/java/com/android/tools/r8/JarDiff.java
+++ b/src/main/java/com/android/tools/r8/JarDiff.java
@@ -13,7 +13,6 @@
 import com.android.tools.r8.origin.PathOrigin;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.StreamUtils;
-import java.io.ByteArrayInputStream;
 import java.io.IOException;
 import java.nio.file.Path;
 import java.nio.file.Paths;
@@ -156,7 +155,7 @@
 
     Collector collector = new Collector();
     JarClassFileReader reader = new JarClassFileReader(applicationReader, collector);
-    reader.read(new PathOrigin(path), ClassKind.PROGRAM, new ByteArrayInputStream(bytes));
+    reader.read(new PathOrigin(path), ClassKind.PROGRAM, bytes);
     return collector.get().asProgramClass();
   }
 
diff --git a/src/main/java/com/android/tools/r8/ProgramResource.java b/src/main/java/com/android/tools/r8/ProgramResource.java
index ffeb558..72667ac 100644
--- a/src/main/java/com/android/tools/r8/ProgramResource.java
+++ b/src/main/java/com/android/tools/r8/ProgramResource.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.origin.PathOrigin;
+import com.android.tools.r8.utils.StreamUtils;
 import java.io.ByteArrayInputStream;
 import java.io.IOException;
 import java.io.InputStream;
@@ -58,6 +59,15 @@
   /** Get the bytes of the program resource. */
   InputStream getByteStream() throws ResourceException;
 
+  /** Optional getter to obtain the bytes of the program resource as an array. */
+  default byte[] getBytes() throws ResourceException {
+    try {
+      return StreamUtils.StreamToByteArrayClose(getByteStream());
+    } catch (IOException e) {
+      throw new ResourceException(getOrigin(), e);
+    }
+  }
+
   /**
    * Get the set of class descriptors for classes defined by this resource.
    *
@@ -102,6 +112,15 @@
     }
 
     @Override
+    public byte[] getBytes() throws ResourceException {
+      try {
+        return Files.readAllBytes(file);
+      } catch (IOException e) {
+        throw new ResourceException(getOrigin(), e);
+      }
+    }
+
+    @Override
     public Set<String> getClassDescriptors() {
       return classDescriptors;
     }
@@ -139,6 +158,11 @@
     }
 
     @Override
+    public byte[] getBytes() throws ResourceException {
+      return bytes;
+    }
+
+    @Override
     public Set<String> getClassDescriptors() {
       return classDescriptors;
     }
diff --git a/src/main/java/com/android/tools/r8/R8Command.java b/src/main/java/com/android/tools/r8/R8Command.java
index 3e9ae7e..895c680 100644
--- a/src/main/java/com/android/tools/r8/R8Command.java
+++ b/src/main/java/com/android/tools/r8/R8Command.java
@@ -909,10 +909,11 @@
             getAssertionsConfiguration());
 
     // When generating class files the build is "intermediate" and we cannot pollute the namespace
-    // with the a hard-coded outline class. Doing so would prohibit subsequent merging of two
-    // R8 produced libraries.
+    // with the a hard-coded outline / enum unboxing utility class. Doing so would prohibit
+    // subsequent merging of two R8 produced libraries.
     if (internal.isGeneratingClassFiles()) {
       internal.outline.enabled = false;
+      internal.enableEnumUnboxing = false;
     }
 
     // EXPERIMENTAL flags.
diff --git a/src/main/java/com/android/tools/r8/dex/ApplicationReader.java b/src/main/java/com/android/tools/r8/dex/ApplicationReader.java
index 679b698..8890a4d 100644
--- a/src/main/java/com/android/tools/r8/dex/ApplicationReader.java
+++ b/src/main/java/com/android/tools/r8/dex/ApplicationReader.java
@@ -42,7 +42,6 @@
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.Timing;
 import java.io.IOException;
-import java.io.InputStream;
 import java.nio.file.Files;
 import java.nio.file.Path;
 import java.nio.file.Paths;
@@ -293,12 +292,9 @@
         futures.add(
             executorService.submit(
                 () -> {
-                  try (InputStream is = input.getByteStream()) {
-                    reader.read(input.getOrigin(), classKind, is);
-                  }
-                  // No other way to have a void callable, but we want the IOException from the
-                  // previous
-                  // line to be wrapped into an ExecutionException.
+                  reader.read(input, classKind);
+                  // No other way to have a void callable, but we want the IOException from read
+                  // to be wrapped into an ExecutionException.
                   return null;
                 }));
       }
diff --git a/src/main/java/com/android/tools/r8/dex/FileWriter.java b/src/main/java/com/android/tools/r8/dex/FileWriter.java
index bd4c6da..c4040a2 100644
--- a/src/main/java/com/android/tools/r8/dex/FileWriter.java
+++ b/src/main/java/com/android/tools/r8/dex/FileWriter.java
@@ -51,6 +51,7 @@
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.DexVersion;
 import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.IterableUtils;
 import com.android.tools.r8.utils.LebUtils;
 import com.google.common.collect.Sets;
 import it.unimi.dsi.fastutil.objects.Object2IntLinkedOpenHashMap;
@@ -633,8 +634,8 @@
   }
 
   private void writeEncodedMethods(
-      List<DexEncodedMethod> unsortedMethods, boolean isSharedSynthetic) {
-    List<DexEncodedMethod> methods = new ArrayList<>(unsortedMethods);
+      Iterable<DexEncodedMethod> unsortedMethods, boolean isSharedSynthetic) {
+    List<DexEncodedMethod> methods = IterableUtils.toNewArrayList(unsortedMethods);
     methods.sort((a, b) -> a.method.slowCompareTo(b.method, namingLens));
     int currentOffset = 0;
     for (DexEncodedMethod method : methods) {
@@ -666,8 +667,8 @@
     mixedSectionOffsets.setOffsetFor(clazz, dest.position());
     dest.putUleb128(clazz.staticFields().size());
     dest.putUleb128(clazz.instanceFields().size());
-    dest.putUleb128(clazz.directMethods().size());
-    dest.putUleb128(clazz.virtualMethods().size());
+    dest.putUleb128(clazz.getMethodCollection().numberOfDirectMethods());
+    dest.putUleb128(clazz.getMethodCollection().numberOfVirtualMethods());
     writeEncodedFields(clazz.staticFields());
     writeEncodedFields(clazz.instanceFields());
     boolean isSharedSynthetic = clazz.getSynthesizedFrom().size() > 1;
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/graph/DexByteCodeWriter.java b/src/main/java/com/android/tools/r8/graph/DexByteCodeWriter.java
index c83010d..d24a75b 100644
--- a/src/main/java/com/android/tools/r8/graph/DexByteCodeWriter.java
+++ b/src/main/java/com/android/tools/r8/graph/DexByteCodeWriter.java
@@ -78,8 +78,7 @@
 
   private boolean anyMethodMatches(DexClass clazz) {
     return !options.hasMethodsFilter()
-        || clazz.virtualMethods().stream().anyMatch(options::methodMatchesFilter)
-        || clazz.directMethods().stream().anyMatch(options::methodMatchesFilter);
+        || clazz.getMethodCollection().hasMethods(options::methodMatchesFilter);
   }
 
   private void writeClass(DexProgramClass clazz, PrintStream ps) {
diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java
index 5bcb25c..c2cdc32 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -138,7 +138,7 @@
     throw new Unreachable();
   }
 
-  public List<DexEncodedMethod> directMethods() {
+  public Iterable<DexEncodedMethod> directMethods() {
     return methodCollection.directMethods();
   }
 
@@ -158,7 +158,7 @@
     methodCollection.setDirectMethods(methods);
   }
 
-  public List<DexEncodedMethod> virtualMethods() {
+  public Iterable<DexEncodedMethod> virtualMethods() {
     return methodCollection.virtualMethods();
   }
 
@@ -411,6 +411,11 @@
     return methodCollection.getMethod(method);
   }
 
+  /** Find method in this class matching {@param method}. */
+  public DexEncodedMethod lookupMethod(Predicate<DexEncodedMethod> predicate) {
+    return methodCollection.getMethod(predicate);
+  }
+
   public DexEncodedMethod lookupSignaturePolymorphicMethod(
       DexString methodName, DexItemFactory factory) {
     if (type != factory.methodHandleType && type != factory.varHandleType) {
@@ -817,7 +822,7 @@
 
   public boolean isValid(InternalOptions options) {
     assert verifyNoAbstractMethodsOnNonAbstractClasses(virtualMethods(), options);
-    assert !isInterface() || virtualMethods().stream().noneMatch(DexEncodedMethod::isFinal);
+    assert !isInterface() || !getMethodCollection().hasVirtualMethods(DexEncodedMethod::isFinal);
     assert verifyCorrectnessOfFieldHolders(fields());
     assert verifyNoDuplicateFields();
     assert methodCollection.verify();
diff --git a/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java b/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java
index eb17913..0b5795d 100644
--- a/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java
+++ b/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java
@@ -11,7 +11,9 @@
 import static org.objectweb.asm.Opcodes.V1_6;
 import static org.objectweb.asm.Opcodes.V9;
 
+import com.android.tools.r8.ProgramResource;
 import com.android.tools.r8.ProgramResource.Kind;
+import com.android.tools.r8.ResourceException;
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.errors.Unreachable;
@@ -41,12 +43,8 @@
 import com.android.tools.r8.utils.StringUtils;
 import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.Iterables;
-import java.io.BufferedInputStream;
-import java.io.IOException;
-import java.io.InputStream;
 import java.nio.ByteBuffer;
 import java.util.ArrayList;
-import java.util.Arrays;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Objects;
@@ -83,26 +81,21 @@
     this.classConsumer = classConsumer;
   }
 
-  public void read(Origin origin, ClassKind classKind, InputStream input) throws IOException {
-    if (!input.markSupported()) {
-      input = new BufferedInputStream(input);
-    }
-    byte[] header = new byte[CLASSFILE_HEADER.length];
-    input.mark(header.length);
-    int size = 0;
-    while (size < header.length) {
-      int read = input.read(header, size, header.length - size);
-      if (read < 0) {
-        throw new CompilationError("Invalid empty classfile", origin);
-      }
-      size += read;
-    }
-    if (!Arrays.equals(CLASSFILE_HEADER, header)) {
-      throw new CompilationError("Invalid classfile header", origin);
-    }
-    input.reset();
+  public void read(ProgramResource resource, ClassKind classKind) throws ResourceException {
+    read(resource.getOrigin(), classKind, resource.getBytes());
+  }
 
-    ClassReader reader = new ClassReader(input);
+  public void read(Origin origin, ClassKind classKind, byte[] bytes) {
+    if (bytes.length < CLASSFILE_HEADER.length) {
+      throw new CompilationError("Invalid empty classfile", origin);
+    }
+    for (int i = 0; i < CLASSFILE_HEADER.length; i++) {
+      if (bytes[i] != CLASSFILE_HEADER[i]) {
+        throw new CompilationError("Invalid classfile header", origin);
+      }
+    }
+
+    ClassReader reader = new ClassReader(bytes);
 
     int parsingOptions = SKIP_FRAMES | SKIP_CODE;
 
diff --git a/src/main/java/com/android/tools/r8/graph/MethodCollection.java b/src/main/java/com/android/tools/r8/graph/MethodCollection.java
index ac2685a..14655d5 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodCollection.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodCollection.java
@@ -2,13 +2,11 @@
 
 import static com.google.common.base.Predicates.alwaysTrue;
 
-import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.IterableUtils;
 import com.android.tools.r8.utils.TraversalContinuation;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
-import java.util.Collections;
 import java.util.List;
 import java.util.Set;
 import java.util.function.Consumer;
@@ -22,7 +20,7 @@
   private static final int ARRAY_BACKING_THRESHOLD = 30;
 
   private final DexClass holder;
-  private final MethodCollectionBacking backing;
+  private MethodCollectionBacking backing;
   private DexEncodedMethod cachedClassInitializer = DexEncodedMethod.SENTINEL;
 
   public MethodCollection(
@@ -50,6 +48,26 @@
     // Nothing to do.
   }
 
+  public boolean hasMethods(Predicate<DexEncodedMethod> predicate) {
+    return getMethod(predicate) != null;
+  }
+
+  public boolean hasDirectMethods() {
+    return hasDirectMethods(alwaysTrue());
+  }
+
+  public boolean hasDirectMethods(Predicate<DexEncodedMethod> predicate) {
+    return backing.getDirectMethod(predicate) != null;
+  }
+
+  public boolean hasVirtualMethods() {
+    return hasVirtualMethods(alwaysTrue());
+  }
+
+  public boolean hasVirtualMethods(Predicate<DexEncodedMethod> predicate) {
+    return backing.getVirtualMethod(predicate) != null;
+  }
+
   public int numberOfDirectMethods() {
     return backing.numberOfDirectMethods();
   }
@@ -123,17 +141,11 @@
     return sorted;
   }
 
-  public List<DexEncodedMethod> directMethods() {
-    if (InternalOptions.assertionsEnabled()) {
-      return Collections.unmodifiableList(backing.directMethods());
-    }
+  public Iterable<DexEncodedMethod> directMethods() {
     return backing.directMethods();
   }
 
-  public List<DexEncodedMethod> virtualMethods() {
-    if (InternalOptions.assertionsEnabled()) {
-      return Collections.unmodifiableList(backing.virtualMethods());
-    }
+  public Iterable<DexEncodedMethod> virtualMethods() {
     return backing.virtualMethods();
   }
 
@@ -141,6 +153,11 @@
     return backing.getMethod(method);
   }
 
+  public DexEncodedMethod getMethod(Predicate<DexEncodedMethod> predicate) {
+    DexEncodedMethod result = backing.getDirectMethod(predicate);
+    return result != null ? result : backing.getVirtualMethod(predicate);
+  }
+
   public DexEncodedMethod getDirectMethod(DexMethod method) {
     return backing.getDirectMethod(method);
   }
@@ -274,6 +291,11 @@
         .shouldBreak();
   }
 
+  public void useSortedBacking() {
+    assert size() == 0;
+    backing = MethodMapBacking.createSorted();
+  }
+
   public boolean verify() {
     forEachMethod(
         method -> {
diff --git a/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java b/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
index 56ab228..2ce0cd8 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
@@ -7,7 +7,6 @@
 
 import com.android.tools.r8.utils.TraversalContinuation;
 import java.util.Collection;
-import java.util.List;
 import java.util.Set;
 import java.util.function.Consumer;
 import java.util.function.Function;
@@ -65,9 +64,9 @@
 
   abstract Iterable<DexEncodedMethod> methods();
 
-  abstract List<DexEncodedMethod> directMethods();
+  abstract Iterable<DexEncodedMethod> directMethods();
 
-  abstract List<DexEncodedMethod> virtualMethods();
+  abstract Iterable<DexEncodedMethod> virtualMethods();
 
   // Lookup methods.
 
diff --git a/src/main/java/com/android/tools/r8/graph/MethodMapBacking.java b/src/main/java/com/android/tools/r8/graph/MethodMapBacking.java
index d34ba36..18257c1 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodMapBacking.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodMapBacking.java
@@ -4,14 +4,15 @@
 package com.android.tools.r8.graph;
 
 import com.android.tools.r8.utils.Box;
+import com.android.tools.r8.utils.IteratorUtils;
 import com.android.tools.r8.utils.MethodSignatureEquivalence;
 import com.android.tools.r8.utils.TraversalContinuation;
 import com.google.common.base.Equivalence.Wrapper;
 import it.unimi.dsi.fastutil.objects.Object2ReferenceLinkedOpenHashMap;
 import it.unimi.dsi.fastutil.objects.Object2ReferenceMap;
-import java.util.ArrayList;
+import it.unimi.dsi.fastutil.objects.Object2ReferenceRBTreeMap;
 import java.util.Collection;
-import java.util.List;
+import java.util.Comparator;
 import java.util.Map.Entry;
 import java.util.Set;
 import java.util.function.Function;
@@ -22,7 +23,16 @@
   private Object2ReferenceMap<Wrapper<DexMethod>, DexEncodedMethod> methodMap;
 
   public MethodMapBacking() {
-    this.methodMap = createMap();
+    this(createMap());
+  }
+
+  private MethodMapBacking(Object2ReferenceMap<Wrapper<DexMethod>, DexEncodedMethod> methodMap) {
+    this.methodMap = methodMap;
+  }
+
+  public static MethodMapBacking createSorted() {
+    Comparator<Wrapper<DexMethod>> comparator = (x, y) -> x.get().slowCompareTo(y.get());
+    return new MethodMapBacking(new Object2ReferenceRBTreeMap<>(comparator));
   }
 
   private static Object2ReferenceMap<Wrapper<DexMethod>, DexEncodedMethod> createMap() {
@@ -107,27 +117,13 @@
   }
 
   @Override
-  List<DexEncodedMethod> directMethods() {
-    List<DexEncodedMethod> methods = new ArrayList<>(size());
-    forEachMethod(
-        method -> {
-          if (belongsToDirectPool(method)) {
-            methods.add(method);
-          }
-        });
-    return methods;
+  Iterable<DexEncodedMethod> directMethods() {
+    return () -> IteratorUtils.filter(methodMap.values().iterator(), this::belongsToDirectPool);
   }
 
   @Override
-  List<DexEncodedMethod> virtualMethods() {
-    List<DexEncodedMethod> methods = new ArrayList<>(size());
-    forEachMethod(
-        method -> {
-          if (belongsToVirtualPool(method)) {
-            methods.add(method);
-          }
-        });
-    return methods;
+  Iterable<DexEncodedMethod> virtualMethods() {
+    return () -> IteratorUtils.filter(methodMap.values().iterator(), this::belongsToVirtualPool);
   }
 
   @Override
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/GeneratedMessageLiteBuilderShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java
index a11b346..deadfa0 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java
@@ -153,7 +153,8 @@
 
     ProtoInliningReasonStrategy inliningReasonStrategy =
         new ProtoInliningReasonStrategy(appView, new FixedInliningReasonStrategy(Reason.NEVER));
-    inliner.performInlining(method, code, feedback, methodProcessor, inliningReasonStrategy);
+    inliner.performInlining(
+        method, code, feedback, methodProcessor, Timing.empty(), inliningReasonStrategy);
 
     // Run the enum optimization to optimize all Enum.ordinal() invocations. This is required to
     // get rid of the enum switch in dynamicMethod().
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/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index a37e369..4a6a082 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -1024,11 +1024,11 @@
     return builder.build();
   }
 
-  public ListIterator<BasicBlock> listIterator() {
+  public BasicBlockIterator listIterator() {
     return new BasicBlockIterator(this);
   }
 
-  public ListIterator<BasicBlock> listIterator(int index) {
+  public BasicBlockIterator listIterator(int index) {
     return new BasicBlockIterator(this, index);
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java b/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
index 095db29..1bc6ba6 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
@@ -3,13 +3,10 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
-import static com.android.tools.r8.optimize.MemberRebindingAnalysis.isMemberVisibleFromOriginalContext;
-
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.code.InvokeDirectRange;
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
@@ -23,8 +20,6 @@
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
-import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
-import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.ArrayList;
 import java.util.List;
@@ -160,64 +155,6 @@
   }
 
   @Override
-  public boolean instructionMayHaveSideEffects(
-      AppView<?> appView, ProgramMethod context, SideEffectAssumption assumption) {
-    if (appView.options().debug) {
-      return true;
-    }
-
-    // Check if it could throw a NullPointerException as a result of the receiver being null.
-    Value receiver = getReceiver();
-    if (!assumption.canAssumeReceiverIsNotNull() && receiver.getType().isNullable()) {
-      return true;
-    }
-
-    // Check if it is a call to one of library methods that are known to be side-effect free.
-    Predicate<InvokeMethod> noSideEffectsPredicate =
-        appView.dexItemFactory().libraryMethodsWithoutSideEffects.get(getInvokedMethod());
-    if (noSideEffectsPredicate != null && noSideEffectsPredicate.test(this)) {
-      return false;
-    }
-
-    // Find the target and check if the invoke may have side effects.
-    if (!appView.appInfo().hasLiveness()) {
-      return true;
-    }
-
-    AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
-    DexEncodedMethod target = lookupSingleTarget(appViewWithLiveness, context);
-    if (target == null) {
-      return true;
-    }
-
-    // Verify that the target method is accessible in the current context.
-    if (!isMemberVisibleFromOriginalContext(
-        appView, context, target.holder(), target.accessFlags)) {
-      return true;
-    }
-
-    // Verify that the target method does not have side-effects.
-    DexClass clazz = appView.definitionFor(target.holder());
-    if (clazz == null) {
-      assert false : "Expected to be able to find the enclosing class of a method definition";
-      return true;
-    }
-
-    if (appViewWithLiveness.appInfo().noSideEffects.containsKey(target.method)) {
-      return false;
-    }
-
-    MethodOptimizationInfo optimizationInfo = target.getOptimizationInfo();
-    if (target.isInstanceInitializer()) {
-      InstanceInitializerInfo initializerInfo = optimizationInfo.getInstanceInitializerInfo();
-      if (!initializerInfo.mayHaveOtherSideEffectsThanInstanceFieldAssignments()) {
-        return false;
-      }
-    }
-    return optimizationInfo.mayHaveSideEffects();
-  }
-
-  @Override
   public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
     ProgramMethod context = code.context();
     if (instructionMayHaveSideEffects(appView, context)) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
index dbee028..950d1bc 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
@@ -12,6 +12,7 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.graph.ResolutionResult;
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis;
 import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
 import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
@@ -19,9 +20,12 @@
 import com.android.tools.r8.ir.optimize.DefaultInliningOracle;
 import com.android.tools.r8.ir.optimize.Inliner.InlineAction;
 import com.android.tools.r8.ir.optimize.Inliner.Reason;
+import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
+import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
 import com.android.tools.r8.ir.optimize.inliner.WhyAreYouNotInliningReporter;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.List;
+import java.util.function.Predicate;
 
 public abstract class InvokeMethodWithReceiver extends InvokeMethod {
 
@@ -144,4 +148,76 @@
     DexClass lowerBound = appViewWithLiveness.definitionFor(lowerBoundType);
     return lowerBound != null && lowerBound.isEffectivelyFinal(appViewWithLiveness);
   }
+
+  @Override
+  public boolean instructionMayHaveSideEffects(
+      AppView<?> appView, ProgramMethod context, SideEffectAssumption assumption) {
+    if (appView.options().debug) {
+      return true;
+    }
+
+    // Check if it could throw a NullPointerException as a result of the receiver being null.
+    Value receiver = getReceiver();
+    if (!assumption.canAssumeReceiverIsNotNull() && receiver.getType().isNullable()) {
+      return true;
+    }
+
+    if (getInvokedMethod().holder.isArrayType()
+        && getInvokedMethod().match(appView.dexItemFactory().objectMembers.clone)) {
+      return !isInvokeVirtual();
+    }
+
+    // Check if it is a call to one of library methods that are known to be side-effect free.
+    Predicate<InvokeMethod> noSideEffectsPredicate =
+        appView.dexItemFactory().libraryMethodsWithoutSideEffects.get(getInvokedMethod());
+    if (noSideEffectsPredicate != null && noSideEffectsPredicate.test(this)) {
+      return false;
+    }
+
+    if (!appView.enableWholeProgramOptimizations()) {
+      return true;
+    }
+
+    assert appView.appInfo().hasLiveness();
+    AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
+
+    ResolutionResult resolutionResult =
+        appViewWithLiveness.appInfo().resolveMethod(getInvokedMethod(), isInvokeInterface());
+    if (resolutionResult.isFailedResolution()) {
+      return true;
+    }
+
+    // Verify that the target method is accessible in the current context.
+    if (resolutionResult
+        .isAccessibleFrom(context, appViewWithLiveness.appInfo())
+        .isPossiblyFalse()) {
+      return true;
+    }
+
+    // Find the target and check if the invoke may have side effects.
+    DexEncodedMethod target = lookupSingleTarget(appViewWithLiveness, context);
+    if (target == null) {
+      return true;
+    }
+
+    // Verify that the target method does not have side-effects.
+    if (appViewWithLiveness.appInfo().noSideEffects.containsKey(target.method)) {
+      return false;
+    }
+
+    MethodOptimizationInfo optimizationInfo = target.getOptimizationInfo();
+    if (target.isInstanceInitializer()) {
+      InstanceInitializerInfo initializerInfo = optimizationInfo.getInstanceInitializerInfo();
+      if (!initializerInfo.mayHaveOtherSideEffectsThanInstanceFieldAssignments()) {
+        return !isInvokeDirect();
+      }
+    }
+
+    return optimizationInfo.mayHaveSideEffects();
+  }
+
+  @Override
+  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
+    return !instructionMayHaveSideEffects(appView, code.context());
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java b/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java
index 69111fc..4739d83 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java
@@ -3,8 +3,6 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
-import static com.android.tools.r8.optimize.MemberRebindingAnalysis.isMemberVisibleFromOriginalContext;
-
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.code.InvokeVirtualRange;
 import com.android.tools.r8.graph.AppView;
@@ -23,7 +21,6 @@
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.List;
-import java.util.function.Predicate;
 
 public class InvokeVirtual extends InvokeMethodWithReceiver {
 
@@ -147,66 +144,4 @@
     return ClassInitializationAnalysis.InstructionUtils.forInvokeVirtual(
         this, clazz, context, appView, mode, assumption);
   }
-
-  @Override
-  public boolean instructionMayHaveSideEffects(
-      AppView<?> appView, ProgramMethod context, SideEffectAssumption assumption) {
-    if (!appView.enableWholeProgramOptimizations()) {
-      return true;
-    }
-
-    if (appView.options().debug) {
-      return true;
-    }
-
-    // Check if it could throw a NullPointerException as a result of the receiver being null.
-    Value receiver = getReceiver();
-    if (!assumption.canAssumeReceiverIsNotNull() && receiver.getType().isNullable()) {
-      return true;
-    }
-
-    if (getInvokedMethod().holder.isArrayType()
-        && getInvokedMethod().match(appView.dexItemFactory().objectMembers.clone)) {
-      return false;
-    }
-
-    // Check if it is a call to one of library methods that are known to be side-effect free.
-    Predicate<InvokeMethod> noSideEffectsPredicate =
-        appView.dexItemFactory().libraryMethodsWithoutSideEffects.get(getInvokedMethod());
-    if (noSideEffectsPredicate != null && noSideEffectsPredicate.test(this)) {
-      return false;
-    }
-
-    // Find the target and check if the invoke may have side effects.
-    if (appView.appInfo().hasLiveness()) {
-      AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
-      DexEncodedMethod target = lookupSingleTarget(appViewWithLiveness, context);
-      if (target == null) {
-        return true;
-      }
-
-      // Verify that the target method is accessible in the current context.
-      if (!isMemberVisibleFromOriginalContext(
-          appView, context, target.holder(), target.accessFlags)) {
-        return true;
-      }
-
-      // Verify that the target method does not have side-effects.
-      boolean targetMayHaveSideEffects;
-      if (appViewWithLiveness.appInfo().noSideEffects.containsKey(target.method)) {
-        targetMayHaveSideEffects = false;
-      } else {
-        targetMayHaveSideEffects = target.getOptimizationInfo().mayHaveSideEffects();
-      }
-
-      return targetMayHaveSideEffects;
-    }
-
-    return true;
-  }
-
-  @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return !instructionMayHaveSideEffects(appView, code.context());
-  }
 }
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..9822c48 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();
@@ -1202,7 +1223,7 @@
     if (serviceLoaderRewriter != null) {
       assert appView.appInfo().hasLiveness();
       timing.begin("Rewrite service loaders");
-      serviceLoaderRewriter.rewrite(code);
+      serviceLoaderRewriter.rewrite(code, methodProcessingId);
       timing.end();
     }
 
@@ -1229,7 +1250,7 @@
     previous = printMethod(code, "IR after disable assertions (SSA)", previous);
 
     timing.begin("Insert assume instructions");
-    CodeRewriter.insertAssumeInstructions(code, assumers);
+    CodeRewriter.insertAssumeInstructions(code, assumers, timing);
     timing.end();
 
     previous = printMethod(code, "IR after inserting assume instructions (SSA)", previous);
@@ -1246,7 +1267,7 @@
 
     if (!isDebugMode && options.enableInlining && inliner != null) {
       timing.begin("Inlining");
-      inliner.performInlining(code.context(), code, feedback, methodProcessor);
+      inliner.performInlining(code.context(), code, feedback, methodProcessor, timing);
       timing.end();
       assert code.verifyTypes(appView);
     }
@@ -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..8e7cfea
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/conversion/MethodProcessingId.java
@@ -0,0 +1,83 @@
+// 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.InternalOptions;
+import com.android.tools.r8.utils.collections.ProgramMethodSet;
+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;
+
+      private final ProgramMethodSet seen =
+          InternalOptions.assertionsEnabled() ? ProgramMethodSet.createConcurrent() : null;
+
+      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;
+        assert seen.add(method);
+        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/ClassProcessor.java b/src/main/java/com/android/tools/r8/ir/desugar/ClassProcessor.java
index 72f630b..b32ab3b 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/ClassProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/ClassProcessor.java
@@ -28,11 +28,9 @@
 import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableList.Builder;
-import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashSet;
 import java.util.IdentityHashMap;
-import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.function.BiConsumer;
@@ -234,15 +232,13 @@
     assert iface.superType == dexItemFactory.objectType;
     // Add non-library default methods as well as those for desugared library classes.
     if (!iface.isLibraryClass() || (needsLibraryInfo() && rewriter.isInDesugaredLibrary(iface))) {
-      List<DexEncodedMethod> methods = iface.virtualMethods();
-      List<Wrapper<DexMethod>> additions = new ArrayList<>(methods.size());
-      for (DexEncodedMethod method : methods) {
-        if (method.isDefaultMethod()) {
-          additions.add(equivalence.wrap(method.method));
-        }
+      Set<Wrapper<DexMethod>> additions =
+          new HashSet<>(iface.getMethodCollection().numberOfVirtualMethods());
+      for (DexEncodedMethod method : iface.virtualMethods(DexEncodedMethod::isDefaultMethod)) {
+        additions.add(equivalence.wrap(method.method));
       }
       if (!additions.isEmpty()) {
-        signatures = signatures.merge(MethodSignatures.create(new HashSet<>(additions)));
+        signatures = signatures.merge(MethodSignatures.create(additions));
       }
     }
     return signatures;
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 1f6af29..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
@@ -44,9 +44,10 @@
 import com.android.tools.r8.position.MethodPosition;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.InternalOptions;
+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;
@@ -111,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<>();
@@ -888,6 +889,10 @@
     theInterface.setDirectMethods(renameHolder(theInterface.directMethods(), renamedInterface));
   }
 
+  private DexEncodedMethod[] renameHolder(Iterable<DexEncodedMethod> methods, DexType newName) {
+    return renameHolder(IterableUtils.toNewArrayList(methods), newName);
+  }
+
   private DexEncodedMethod[] renameHolder(List<DexEncodedMethod> methods, DexType newName) {
     DexEncodedMethod[] newMethods = new DexEncodedMethod[methods.size()];
     for (int i = 0; i < newMethods.length; i++) {
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java
index f1a499a..a277a71 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java
@@ -115,7 +115,7 @@
     }
 
     // If at least one bridge method was removed then update the table.
-    if (remainingMethods.size() < iface.virtualMethods().size()) {
+    if (remainingMethods.size() < iface.getMethodCollection().numberOfVirtualMethods()) {
       iface.setVirtualMethods(remainingMethods.toArray(DexEncodedMethod.EMPTY_ARRAY));
     }
     remainingMethods.clear();
@@ -181,7 +181,7 @@
         }
       }
     }
-    if (remainingMethods.size() < iface.directMethods().size()) {
+    if (remainingMethods.size() < iface.getMethodCollection().numberOfDirectMethods()) {
       iface.setDirectMethods(remainingMethods.toArray(DexEncodedMethod.EMPTY_ARRAY));
     }
 
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/AliasIntroducer.java b/src/main/java/com/android/tools/r8/ir/optimize/AliasIntroducer.java
index 7219eb0..cdb1699 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/AliasIntroducer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/AliasIntroducer.java
@@ -3,15 +3,19 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.optimize;
 
+import static com.google.common.base.Predicates.alwaysTrue;
+
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.ir.code.Assume;
 import com.android.tools.r8.ir.code.Assume.NoAssumption;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionListIterator;
 import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.utils.Timing;
 import com.google.common.collect.Sets;
 import java.util.ListIterator;
 import java.util.Set;
@@ -25,8 +29,16 @@
   }
 
   @Override
+  public void insertAssumeInstructions(IRCode code, Timing timing) {
+    insertAssumeInstructionsInBlocks(code, code.listIterator(), alwaysTrue(), timing);
+  }
+
+  @Override
   public void insertAssumeInstructionsInBlocks(
-      IRCode code, ListIterator<BasicBlock> blockIterator, Predicate<BasicBlock> blockTester) {
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      Predicate<BasicBlock> blockTester,
+      Timing timing) {
     while (blockIterator.hasNext()) {
       BasicBlock block = blockIterator.next();
       if (blockTester.test(block)) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Assumer.java b/src/main/java/com/android/tools/r8/ir/optimize/Assumer.java
index 334a606..78c3012 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Assumer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Assumer.java
@@ -5,19 +5,21 @@
 
 import com.android.tools.r8.ir.code.Assume;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.IRCode;
-import com.google.common.base.Predicates;
-import java.util.ListIterator;
+import com.android.tools.r8.utils.Timing;
 import java.util.function.Predicate;
 
 /**
  * One that assumes. Inherited tracker/optimization insert necessary variants of {@link Assume}.
  */
 public interface Assumer {
-  default void insertAssumeInstructions(IRCode code) {
-    insertAssumeInstructionsInBlocks(code, code.listIterator(), Predicates.alwaysTrue());
-  }
+
+  void insertAssumeInstructions(IRCode code, Timing timing);
 
   void insertAssumeInstructionsInBlocks(
-      IRCode code, ListIterator<BasicBlock> blockIterator, Predicate<BasicBlock> blockTester);
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      Predicate<BasicBlock> blockTester,
+      Timing timing);
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index 29a0c32..22a211b 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -8,6 +8,7 @@
 import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
 import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
 import static com.android.tools.r8.optimize.MemberRebindingAnalysis.isTypeVisibleFromContext;
+import static com.google.common.base.Predicates.alwaysTrue;
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.CompilationError;
@@ -84,6 +85,7 @@
 import com.android.tools.r8.utils.InternalOutputMode;
 import com.android.tools.r8.utils.LongInterval;
 import com.android.tools.r8.utils.SetUtils;
+import com.android.tools.r8.utils.Timing;
 import com.google.common.base.Equivalence;
 import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.base.Suppliers;
@@ -157,11 +159,19 @@
     this.dexItemFactory = appView.dexItemFactory();
   }
 
-  public static void insertAssumeInstructions(IRCode code, Collection<Assumer> assumers) {
+  public static void insertAssumeInstructions(
+      IRCode code, Collection<Assumer> assumers, Timing timing) {
+    insertAssumeInstructionsInBlocks(code, assumers, alwaysTrue(), timing);
+  }
+
+  public static void insertAssumeInstructionsInBlocks(
+      IRCode code, Collection<Assumer> assumers, Predicate<BasicBlock> blockTester, Timing timing) {
+    timing.begin("Insert assume instructions");
     for (Assumer assumer : assumers) {
-      assumer.insertAssumeInstructions(code);
+      assumer.insertAssumeInstructionsInBlocks(code, code.listIterator(), blockTester, timing);
       assert code.isConsistentSSA();
     }
+    timing.end();
   }
 
   public static void removeAssumeInstructions(AppView<?> appView, IRCode code) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java b/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java
index 4b8ee00..5893a3b 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java
@@ -38,12 +38,11 @@
 import com.android.tools.r8.shaking.MainDexDirectReferenceTracer;
 import com.android.tools.r8.utils.BooleanUtils;
 import com.android.tools.r8.utils.InternalOptions;
-import com.android.tools.r8.utils.IteratorUtils;
+import com.android.tools.r8.utils.Timing;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
 import java.util.BitSet;
 import java.util.List;
-import java.util.ListIterator;
 import java.util.Set;
 
 public final class DefaultInliningOracle implements InliningOracle, InliningStrategy {
@@ -396,7 +395,7 @@
       if (Log.ENABLED) {
         Log.verbose(getClass(), "Forcing extra inline on " + target.toSourceString());
       }
-      inliner.performInlining(target, inlinee, feedback, methodProcessor);
+      inliner.performInlining(target, inlinee, feedback, methodProcessor, Timing.empty());
     }
   }
 
@@ -675,22 +674,6 @@
     instructionAllowance -= Inliner.numberOfInstructions(inlinee.code);
   }
 
-  private void insertAssumeInstructionsToInlinee(
-      Assumer assumer,
-      IRCode code,
-      BasicBlock block,
-      ListIterator<BasicBlock> blockIterator,
-      Set<BasicBlock> inlineeBlocks) {
-    // Move the cursor back to where the first inlinee block was added.
-    while (blockIterator.hasPrevious() && blockIterator.previous() != block) {
-      // Do nothing.
-    }
-    assert IteratorUtils.peekNext(blockIterator) == block;
-
-    assumer.insertAssumeInstructionsInBlocks(code, blockIterator, inlineeBlocks::contains);
-    assert !blockIterator.hasNext();
-  }
-
   @Override
   public DexType getReceiverTypeIfKnown(InvokeMethod invoke) {
     return null; // Maybe improve later.
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/DynamicTypeOptimization.java b/src/main/java/com/android/tools/r8/ir/optimize/DynamicTypeOptimization.java
index cbcbd2e..4aabc5b 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/DynamicTypeOptimization.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/DynamicTypeOptimization.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.ir.optimize;
 
 import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+import static com.google.common.base.Predicates.alwaysTrue;
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexEncodedField;
@@ -16,6 +17,7 @@
 import com.android.tools.r8.ir.code.Assume;
 import com.android.tools.r8.ir.code.Assume.DynamicTypeAssumption;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionListIterator;
@@ -26,6 +28,7 @@
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.Timing;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.ListIterator;
@@ -40,14 +43,24 @@
   }
 
   @Override
+  public void insertAssumeInstructions(IRCode code, Timing timing) {
+    insertAssumeInstructionsInBlocks(code, code.listIterator(), alwaysTrue(), timing);
+  }
+
+  @Override
   public void insertAssumeInstructionsInBlocks(
-      IRCode code, ListIterator<BasicBlock> blockIterator, Predicate<BasicBlock> blockTester) {
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      Predicate<BasicBlock> blockTester,
+      Timing timing) {
+    timing.begin("Insert assume dynamic type instructions");
     while (blockIterator.hasNext()) {
       BasicBlock block = blockIterator.next();
       if (blockTester.test(block)) {
         insertAssumeDynamicTypeInstructionsInBlock(code, blockIterator, block);
       }
     }
+    timing.end();
   }
 
   // TODO(b/127461806): Should also insert AssumeDynamicType instructions after instanceof
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
index bb58ce1..c17efb4 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
@@ -26,6 +26,7 @@
 import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.CatchHandlers.CatchHandler;
 import com.android.tools.r8.ir.code.ConstClass;
 import com.android.tools.r8.ir.code.IRCode;
@@ -63,6 +64,7 @@
 import com.android.tools.r8.utils.IteratorUtils;
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.SetUtils;
+import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
@@ -76,7 +78,6 @@
 import java.util.ListIterator;
 import java.util.Map;
 import java.util.Set;
-import java.util.function.Consumer;
 
 public class Inliner implements PostOptimization {
 
@@ -858,22 +859,31 @@
       ProgramMethod method,
       IRCode code,
       Map<? extends InvokeMethod, InliningInfo> invokesToInline,
-      InliningIRProvider inliningIRProvider) {
+      InliningIRProvider inliningIRProvider,
+      Timing timing) {
     ForcedInliningOracle oracle = new ForcedInliningOracle(appView, method, invokesToInline);
     performInliningImpl(
-        oracle, oracle, method, code, OptimizationFeedbackIgnore.getInstance(), inliningIRProvider);
+        oracle,
+        oracle,
+        method,
+        code,
+        OptimizationFeedbackIgnore.getInstance(),
+        inliningIRProvider,
+        timing);
   }
 
   public void performInlining(
       ProgramMethod method,
       IRCode code,
       OptimizationFeedback feedback,
-      MethodProcessor methodProcessor) {
+      MethodProcessor methodProcessor,
+      Timing timing) {
     performInlining(
         method,
         code,
         feedback,
         methodProcessor,
+        timing,
         createDefaultInliningReasonStrategy(methodProcessor));
   }
 
@@ -882,6 +892,7 @@
       IRCode code,
       OptimizationFeedback feedback,
       MethodProcessor methodProcessor,
+      Timing timing,
       InliningReasonStrategy inliningReasonStrategy) {
     InternalOptions options = appView.options();
     DefaultInliningOracle oracle =
@@ -894,7 +905,7 @@
     InliningIRProvider inliningIRProvider =
         new InliningIRProvider(appView, method, code, methodProcessor);
     assert inliningIRProvider.verifyIRCacheIsEmpty();
-    performInliningImpl(oracle, oracle, method, code, feedback, inliningIRProvider);
+    performInliningImpl(oracle, oracle, method, code, feedback, inliningIRProvider, timing);
   }
 
   public InliningReasonStrategy createDefaultInliningReasonStrategy(
@@ -941,10 +952,11 @@
       ProgramMethod context,
       IRCode code,
       OptimizationFeedback feedback,
-      InliningIRProvider inliningIRProvider) {
+      InliningIRProvider inliningIRProvider,
+      Timing timing) {
     AssumeDynamicTypeRemover assumeDynamicTypeRemover = new AssumeDynamicTypeRemover(appView, code);
     Set<BasicBlock> blocksToRemove = Sets.newIdentityHashSet();
-    ListIterator<BasicBlock> blockIterator = code.listIterator();
+    BasicBlockIterator blockIterator = code.listIterator();
     ClassInitializationAnalysis classInitializationAnalysis =
         new ClassInitializationAnalysis(appView, code);
     Deque<BasicBlock> inlineeStack = new ArrayDeque<>();
@@ -1045,10 +1057,10 @@
           }
 
           classInitializationAnalysis.notifyCodeHasChanged();
-          postProcessInlineeBlocks(code, inlinee.code, blockIterator, block);
+          postProcessInlineeBlocks(code, inlinee.code, blockIterator, block, timing);
 
           // The synthetic and bridge flags are maintained only if the inlinee has also these flags.
-          if (context.getDefinition().isBridge() && !inlinee.code.method().accessFlags.isBridge()) {
+          if (context.getDefinition().isBridge() && !inlinee.code.method().isBridge()) {
             context.getDefinition().accessFlags.demoteFromBridge();
           }
           if (context.getDefinition().accessFlags.isSynthetic()
@@ -1122,7 +1134,11 @@
 
   /** Applies member rebinding to the inlinee and inserts assume instructions. */
   private void postProcessInlineeBlocks(
-      IRCode code, IRCode inlinee, ListIterator<BasicBlock> blockIterator, BasicBlock block) {
+      IRCode code,
+      IRCode inlinee,
+      BasicBlockIterator blockIterator,
+      BasicBlock block,
+      Timing timing) {
     InternalOptions options = appView.options();
     boolean skip =
         !(options.enableDynamicTypeOptimization
@@ -1146,20 +1162,19 @@
     // Introduce aliases only to the inlinee blocks.
     if (options.testing.forceAssumeNoneInsertion) {
       applyAssumerToInlinee(
-          new AliasIntroducer(appView), code, blockIterator, block, inlineeBlocks);
+          new AliasIntroducer(appView), code, blockIterator, block, inlineeBlocks, timing);
     }
 
     // Add non-null IRs only to the inlinee blocks.
     if (options.enableNonNullTracking) {
-      Consumer<BasicBlock> splitBlockConsumer = inlineeBlocks::add;
-      Assumer nonNullTracker = new NonNullTracker(appView, splitBlockConsumer);
-      applyAssumerToInlinee(nonNullTracker, code, blockIterator, block, inlineeBlocks);
+      Assumer nonNullTracker = new NonNullTracker(appView);
+      applyAssumerToInlinee(nonNullTracker, code, blockIterator, block, inlineeBlocks, timing);
     }
 
     // Add dynamic type assumptions only to the inlinee blocks.
     if (options.enableDynamicTypeOptimization) {
       applyAssumerToInlinee(
-          new DynamicTypeOptimization(appView), code, blockIterator, block, inlineeBlocks);
+          new DynamicTypeOptimization(appView), code, blockIterator, block, inlineeBlocks, timing);
     }
     // Restore the old state of the iterator.
     rewindBlockIteratorToFirstInlineeBlock(blockIterator, state);
@@ -1169,11 +1184,12 @@
   private void applyAssumerToInlinee(
       Assumer assumer,
       IRCode code,
-      ListIterator<BasicBlock> blockIterator,
+      BasicBlockIterator blockIterator,
       BasicBlock block,
-      Set<BasicBlock> inlineeBlocks) {
+      Set<BasicBlock> inlineeBlocks,
+      Timing timing) {
     rewindBlockIteratorToFirstInlineeBlock(blockIterator, block);
-    assumer.insertAssumeInstructionsInBlocks(code, blockIterator, inlineeBlocks::contains);
+    assumer.insertAssumeInstructionsInBlocks(code, blockIterator, inlineeBlocks::contains, timing);
     assert !blockIterator.hasNext();
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/NonNullTracker.java b/src/main/java/com/android/tools/r8/ir/optimize/NonNullTracker.java
index 406c09c..59f5772 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/NonNullTracker.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/NonNullTracker.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.ir.optimize;
 
 import static com.android.tools.r8.ir.code.DominatorTree.Assumption.MAY_HAVE_UNREACHABLE_BLOCKS;
+import static com.google.common.base.Predicates.alwaysTrue;
 
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
@@ -16,6 +17,7 @@
 import com.android.tools.r8.ir.code.Assume;
 import com.android.tools.r8.ir.code.Assume.NonNullAssumption;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.DominatorTree;
 import com.android.tools.r8.ir.code.FieldInstruction;
 import com.android.tools.r8.ir.code.IRCode;
@@ -28,6 +30,7 @@
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.optimize.info.FieldOptimizationInfo;
 import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
+import com.android.tools.r8.utils.Timing;
 import com.google.common.collect.Sets;
 import it.unimi.dsi.fastutil.ints.IntArrayList;
 import it.unimi.dsi.fastutil.ints.IntList;
@@ -58,8 +61,26 @@
   }
 
   @Override
+  public void insertAssumeInstructions(IRCode code, Timing timing) {
+    insertAssumeInstructionsInBlocks(code, code.listIterator(), alwaysTrue(), timing);
+  }
+
+  @Override
   public void insertAssumeInstructionsInBlocks(
-      IRCode code, ListIterator<BasicBlock> blockIterator, Predicate<BasicBlock> blockTester) {
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      Predicate<BasicBlock> blockTester,
+      Timing timing) {
+    timing.begin("Insert assume not null instructions");
+    internalInsertAssumeInstructionsInBlocks(code, blockIterator, blockTester, timing);
+    timing.end();
+  }
+
+  private void internalInsertAssumeInstructionsInBlocks(
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      Predicate<BasicBlock> blockTester,
+      Timing timing) {
     Set<Value> affectedValues = Sets.newIdentityHashSet();
     Set<Value> knownToBeNonNullValues = Sets.newIdentityHashSet();
     while (blockIterator.hasNext()) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/ServiceLoaderRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/ServiceLoaderRewriter.java
index a2d21c3..d0ad73a 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/ServiceLoaderRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/ServiceLoaderRewriter.java
@@ -19,6 +19,7 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DexTypeList;
 import com.android.tools.r8.graph.MethodAccessFlags;
+import com.android.tools.r8.graph.MethodCollection;
 import com.android.tools.r8.graph.ParameterAnnotationsList;
 import com.android.tools.r8.ir.code.ConstClass;
 import com.android.tools.r8.ir.code.IRCode;
@@ -27,6 +28,7 @@
 import com.android.tools.r8.ir.code.InvokeStatic;
 import com.android.tools.r8.ir.code.InvokeVirtual;
 import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.conversion.MethodProcessingId;
 import com.android.tools.r8.ir.desugar.ServiceLoaderSourceCode;
 import com.android.tools.r8.origin.SynthesizedOrigin;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
@@ -35,7 +37,6 @@
 import java.util.Collections;
 import java.util.List;
 import java.util.concurrent.ConcurrentHashMap;
-import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.atomic.AtomicReference;
 
 /**
@@ -74,8 +75,6 @@
   private ConcurrentHashMap<DexType, DexEncodedMethod> synthesizedServiceLoaders =
       new ConcurrentHashMap<>();
 
-  private AtomicInteger atomicInteger = new AtomicInteger(0);
-
   private final AppView<? extends AppInfoWithLiveness> appView;
 
   public ServiceLoaderRewriter(AppView<? extends AppInfoWithLiveness> appView) {
@@ -86,7 +85,7 @@
     return synthesizedClass.get();
   }
 
-  public void rewrite(IRCode code) {
+  public void rewrite(IRCode code, MethodProcessingId methodProcessingId) {
     DexItemFactory factory = appView.dexItemFactory();
     InstructionListIterator instructionIterator = code.instructionListIterator();
     while (instructionIterator.hasNext()) {
@@ -172,7 +171,8 @@
           synthesizedServiceLoaders.computeIfAbsent(
               constClass.getValue(),
               service -> {
-                DexEncodedMethod addedMethod = createSynthesizedMethod(service, classes);
+                DexEncodedMethod addedMethod =
+                    createSynthesizedMethod(service, classes, methodProcessingId);
                 if (appView.options().isGeneratingClassFiles()) {
                   addedMethod.upgradeClassFileVersion(code.method().getClassFileVersion());
                 }
@@ -184,27 +184,34 @@
     }
   }
 
-  private DexEncodedMethod createSynthesizedMethod(DexType serviceType, List<DexClass> classes) {
+  private DexEncodedMethod createSynthesizedMethod(
+      DexType serviceType, List<DexClass> classes, MethodProcessingId methodProcessingId) {
+    MethodCollection methodCollection = getOrSetSynthesizedClass().getMethodCollection();
+    String methodNamePrefix = SERVICE_LOADER_METHOD_PREFIX_NAME + "$";
     DexProto proto = appView.dexItemFactory().createProto(appView.dexItemFactory().iteratorType);
-    DexMethod method =
-        appView
-            .dexItemFactory()
-            .createMethod(
-                appView.dexItemFactory().serviceLoaderRewrittenClassType,
-                proto,
-                SERVICE_LOADER_METHOD_PREFIX_NAME + atomicInteger.incrementAndGet());
-    MethodAccessFlags methodAccess =
-        MethodAccessFlags.fromSharedAccessFlags(Constants.ACC_PUBLIC | Constants.ACC_STATIC, false);
-    DexEncodedMethod encodedMethod =
-        new DexEncodedMethod(
-            method,
-            methodAccess,
-            DexAnnotationSet.empty(),
-            ParameterAnnotationsList.empty(),
-            ServiceLoaderSourceCode.generate(serviceType, classes, appView.dexItemFactory()),
-            true);
-    getOrSetSynthesizedClass().addDirectMethod(encodedMethod);
-    return encodedMethod;
+    synchronized (methodCollection) {
+      DexMethod methodReference;
+      do {
+        methodReference =
+            appView
+                .dexItemFactory()
+                .createMethod(
+                    appView.dexItemFactory().serviceLoaderRewrittenClassType,
+                    proto,
+                    methodNamePrefix + methodProcessingId.getAndIncrementId());
+      } while (methodCollection.getMethod(methodReference) != null);
+      DexEncodedMethod method =
+          new DexEncodedMethod(
+              methodReference,
+              MethodAccessFlags.fromSharedAccessFlags(
+                  Constants.ACC_PUBLIC | Constants.ACC_STATIC, false),
+              DexAnnotationSet.empty(),
+              ParameterAnnotationsList.empty(),
+              ServiceLoaderSourceCode.generate(serviceType, classes, appView.dexItemFactory()),
+              true);
+      methodCollection.addDirectMethod(method);
+      return method;
+    }
   }
 
   private DexProgramClass getOrSetSynthesizedClass() {
@@ -215,30 +222,33 @@
     ChecksumSupplier checksumSupplier = DexProgramClass::invalidChecksumRequest;
     DexProgramClass clazz =
         synthesizedClass.updateAndGet(
-            existingClazz -> {
-              if (existingClazz != null) {
-                return existingClazz;
+            existingClass -> {
+              if (existingClass != null) {
+                return existingClass;
               }
-              return new DexProgramClass(
-                  appView.dexItemFactory().serviceLoaderRewrittenClassType,
-                  null,
-                  new SynthesizedOrigin("Service Loader desugaring", getClass()),
-                  ClassAccessFlags.fromDexAccessFlags(
-                      Constants.ACC_FINAL | Constants.ACC_SYNTHETIC | Constants.ACC_PUBLIC),
-                  appView.dexItemFactory().objectType,
-                  DexTypeList.empty(),
-                  appView.dexItemFactory().createString("ServiceLoader"),
-                  null,
-                  Collections.emptyList(),
-                  null,
-                  Collections.emptyList(),
-                  DexAnnotationSet.empty(),
-                  DexEncodedField.EMPTY_ARRAY, // Static fields.
-                  DexEncodedField.EMPTY_ARRAY, // Instance fields.
-                  DexEncodedMethod.EMPTY_ARRAY,
-                  DexEncodedMethod.EMPTY_ARRAY, // Virtual methods.
-                  appView.dexItemFactory().getSkipNameValidationForTesting(),
-                  checksumSupplier);
+              DexProgramClass newClass =
+                  new DexProgramClass(
+                      appView.dexItemFactory().serviceLoaderRewrittenClassType,
+                      null,
+                      new SynthesizedOrigin("Service Loader desugaring", getClass()),
+                      ClassAccessFlags.fromDexAccessFlags(
+                          Constants.ACC_FINAL | Constants.ACC_SYNTHETIC | Constants.ACC_PUBLIC),
+                      appView.dexItemFactory().objectType,
+                      DexTypeList.empty(),
+                      appView.dexItemFactory().createString("ServiceLoader"),
+                      null,
+                      Collections.emptyList(),
+                      null,
+                      Collections.emptyList(),
+                      DexAnnotationSet.empty(),
+                      DexEncodedField.EMPTY_ARRAY, // Static fields.
+                      DexEncodedField.EMPTY_ARRAY, // Instance fields.
+                      DexEncodedMethod.EMPTY_ARRAY,
+                      DexEncodedMethod.EMPTY_ARRAY, // Virtual methods.
+                      appView.dexItemFactory().getSkipNameValidationForTesting(),
+                      checksumSupplier);
+              newClass.getMethodCollection().useSortedBacking();
+              return newClass;
             });
     assert clazz != null;
     appView.appInfo().addSynthesizedClass(clazz);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java
index 9318acb..5e378c2 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java
@@ -58,6 +58,7 @@
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.Pair;
 import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
@@ -430,7 +431,8 @@
       return false;
     }
     // Inline extra methods.
-    inliner.performForcedInlining(method, code, extraMethodCalls, inliningIRProvider);
+    inliner.performForcedInlining(
+        method, code, extraMethodCalls, inliningIRProvider, Timing.empty());
     return true;
   }
 
@@ -444,7 +446,8 @@
         .map(InvokeMethodWithReceiver::getReceiver)
         .allMatch(receivers::isReceiverAlias);
 
-    inliner.performForcedInlining(method, code, methodCallsOnInstance, inliningIRProvider);
+    inliner.performForcedInlining(
+        method, code, methodCallsOnInstance, inliningIRProvider, Timing.empty());
 
     // In case we are class inlining an object allocation that does not inherit directly from
     // java.lang.Object, we need keep force inlining the constructor until we reach
@@ -488,7 +491,8 @@
           }
         }
         if (!methodCallsOnInstance.isEmpty()) {
-          inliner.performForcedInlining(method, code, methodCallsOnInstance, inliningIRProvider);
+          inliner.performForcedInlining(
+              method, code, methodCallsOnInstance, inliningIRProvider, Timing.empty());
         }
       } while (!methodCallsOnInstance.isEmpty());
     }
@@ -539,7 +543,8 @@
 
     assert !methodCallsOnInstance.isEmpty();
 
-    inliner.performForcedInlining(method, code, methodCallsOnInstance, inliningIRProvider);
+    inliner.performForcedInlining(
+        method, code, methodCallsOnInstance, inliningIRProvider, Timing.empty());
     return true;
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingCandidateAnalysis.java b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingCandidateAnalysis.java
index d138d95..7ae1ffa 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingCandidateAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingCandidateAnalysis.java
@@ -71,7 +71,7 @@
       enumUnboxer.reportFailure(clazz.type, Reason.UNEXPECTED_STATIC_FIELD);
       return false;
     }
-    if (!clazz.virtualMethods().isEmpty()) {
+    if (clazz.getMethodCollection().hasVirtualMethods()) {
       enumUnboxer.reportFailure(clazz.type, Reason.VIRTUAL_METHOD);
       return false;
     }
@@ -89,7 +89,7 @@
     //     public static ** valueOf(java.lang.String);
     // }
     // In general there will be 4 methods, unless the enum keep rule is not present.
-    if (clazz.directMethods().size() > 4) {
+    if (clazz.getMethodCollection().numberOfDirectMethods() > 4) {
       enumUnboxer.reportFailure(clazz.type, Reason.UNEXPECTED_DIRECT_METHOD);
       return false;
     }
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..35add7f 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
@@ -52,8 +52,9 @@
 import com.android.tools.r8.utils.StringDiagnostic;
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.ThrowingConsumer;
+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 com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
 import com.google.common.collect.Sets;
@@ -168,7 +169,7 @@
 
       assert invokesToInline.size() > 1;
 
-      inliner.performForcedInlining(method, code, invokesToInline, provider);
+      inliner.performForcedInlining(method, code, invokesToInline, provider, Timing.empty());
     }
   }
 
@@ -454,7 +455,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 1e7fb3c..ac915a5 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);
@@ -381,7 +386,7 @@
   }
 
   private void insertAssumeInstructions(IRCode code, MethodProcessor methodProcessor) {
-    CodeRewriter.insertAssumeInstructions(code, converter.assumers);
+    CodeRewriter.insertAssumeInstructions(code, converter.assumers, Timing.empty());
   }
 
   private BiConsumer<IRCode, MethodProcessor> collectOptimizationInfo(
@@ -812,28 +817,32 @@
     hostClass.setStaticFields(newFields);
 
     // Process static methods.
-    List<DexEncodedMethod> extraMethods = candidateClass.directMethods();
-    if (!extraMethods.isEmpty()) {
-      List<DexEncodedMethod> newMethods = new ArrayList<>(extraMethods.size());
-      for (DexEncodedMethod method : extraMethods) {
-        DexEncodedMethod newMethod = method.toTypeSubstitutedMethod(
-            factory().createMethod(hostType, method.method.proto, method.method.name));
-        newMethods.add(newMethod);
-        // If the old method from the candidate class has been staticized,
-        if (staticizedMethods.remove(method)) {
-          // Properly update staticized methods to reprocess, i.e., add the corresponding one that
-          // has just been migrated to the host class.
-          staticizedMethods.createAndAdd(hostClass, newMethod);
-        }
-        DexMethod originalMethod = methodMapping.inverse().get(method.method);
-        if (originalMethod == null) {
-          methodMapping.put(method.method, newMethod.method);
-        } else {
-          methodMapping.put(originalMethod, newMethod.method);
-        }
-      }
-      hostClass.addDirectMethods(newMethods);
+    if (!candidateClass.getMethodCollection().hasDirectMethods()) {
+      return;
     }
+
+    Iterable<DexEncodedMethod> extraMethods = candidateClass.directMethods();
+    List<DexEncodedMethod> newMethods =
+        new ArrayList<>(candidateClass.getMethodCollection().numberOfDirectMethods());
+    for (DexEncodedMethod method : extraMethods) {
+      DexEncodedMethod newMethod =
+          method.toTypeSubstitutedMethod(
+              factory().createMethod(hostType, method.method.proto, method.method.name));
+      newMethods.add(newMethod);
+      // If the old method from the candidate class has been staticized,
+      if (staticizedMethods.remove(method)) {
+        // Properly update staticized methods to reprocess, i.e., add the corresponding one that
+        // has just been migrated to the host class.
+        staticizedMethods.createAndAdd(hostClass, newMethod);
+      }
+      DexMethod originalMethod = methodMapping.inverse().get(method.method);
+      if (originalMethod == null) {
+        methodMapping.put(method.method, newMethod.method);
+      } else {
+        methodMapping.put(originalMethod, newMethod.method);
+      }
+    }
+    hostClass.addDirectMethods(newMethods);
   }
 
   private DexField mapCandidateField(DexField field, DexType candidateType, DexType hostType) {
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java b/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java
index f52f65e..a1ad70f 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.kotlin;
 
+import static com.android.tools.r8.kotlin.KotlinMetadataUtils.INVALID_KOTLIN_INFO;
 import static com.android.tools.r8.kotlin.KotlinMetadataUtils.NO_KOTLIN_INFO;
 
 import com.android.tools.r8.graph.DexAnnotation;
@@ -36,6 +37,7 @@
                     + clazz.type.toSourceString()
                     + " has malformed kotlin.Metadata: "
                     + e.getMessage()));
+        return INVALID_KOTLIN_INFO;
       } catch (Throwable e) {
         reporter.info(
             new StringDiagnostic(
@@ -43,6 +45,7 @@
                     + clazz.type.toSourceString()
                     + "'s kotlin.Metadata: "
                     + e.getMessage()));
+        return INVALID_KOTLIN_INFO;
       }
     }
     return NO_KOTLIN_INFO;
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataRewriter.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataRewriter.java
index b3c167f..31818e8 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataRewriter.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataRewriter.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.kotlin;
 
+import static com.android.tools.r8.kotlin.KotlinMetadataUtils.INVALID_KOTLIN_INFO;
 import static com.android.tools.r8.kotlin.KotlinMetadataUtils.NO_KOTLIN_INFO;
 
 import com.android.tools.r8.graph.AppView;
@@ -73,9 +74,12 @@
           KotlinClassLevelInfo kotlinInfo = clazz.getKotlinInfo();
           DexAnnotation oldMeta =
               clazz.annotations().getFirstMatching(kotlin.metadata.kotlinMetadataType);
+          if (kotlinInfo == INVALID_KOTLIN_INFO) {
+            // Maintain invalid kotlin info for classes.
+            return;
+          }
           if (kotlinInfo == NO_KOTLIN_INFO) {
-            // TODO(b/154346948): Track invalid meta-data objects such that we can enable this
-            // assert oldMeta == null;
+            assert oldMeta == null;
             return;
           }
           if (oldMeta != null) {
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataUtils.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataUtils.java
index fb173a2..e846c14 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataUtils.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataUtils.java
@@ -27,11 +27,23 @@
 
 public class KotlinMetadataUtils {
 
-  public static final NoKotlinInfo NO_KOTLIN_INFO = new NoKotlinInfo();
+  public static final NoKotlinInfo NO_KOTLIN_INFO = new NoKotlinInfo("NO_KOTLIN_INFO");
+  public static final NoKotlinInfo INVALID_KOTLIN_INFO = new NoKotlinInfo("INVALID_KOTLIN_INFO");
 
   private static class NoKotlinInfo
       implements KotlinClassLevelInfo, KotlinFieldLevelInfo, KotlinMethodLevelInfo {
 
+    private final String name;
+
+    private NoKotlinInfo(String name) {
+      this.name = name;
+    }
+
+    @Override
+    public String toString() {
+      return name;
+    }
+
     @Override
     public KotlinClassHeader rewrite(
         DexClass clazz, AppView<AppInfoWithLiveness> appView, NamingLens namingLens) {
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClassInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClassInfo.java
index cc11647..af02060 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClassInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClassInfo.java
@@ -10,7 +10,6 @@
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.Reporter;
-import kotlinx.metadata.InconsistentKotlinMetadataException;
 import kotlinx.metadata.KmLambda;
 import kotlinx.metadata.jvm.KotlinClassHeader;
 import kotlinx.metadata.jvm.KotlinClassMetadata;
@@ -43,12 +42,8 @@
       Reporter reporter) {
     KmLambda lambda = null;
     if (syntheticClass.isLambda()) {
-      try {
-        lambda = syntheticClass.toKmLambda();
-        assert lambda != null;
-      } catch (InconsistentKotlinMetadataException ex) {
-        // TODO(b/155534905): Gracefully handle these errors by retaining the original object.
-      }
+      lambda = syntheticClass.toKmLambda();
+      assert lambda != null;
     }
     return new KotlinSyntheticClassInfo(
         lambda != null
diff --git a/src/main/java/com/android/tools/r8/naming/MinifiedNameMapPrinter.java b/src/main/java/com/android/tools/r8/naming/MinifiedNameMapPrinter.java
deleted file mode 100644
index 0fdeebc..0000000
--- a/src/main/java/com/android/tools/r8/naming/MinifiedNameMapPrinter.java
+++ /dev/null
@@ -1,117 +0,0 @@
-// Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.naming;
-
-import com.android.tools.r8.graph.DexApplication;
-import com.android.tools.r8.graph.DexEncodedField;
-import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.graph.DexField;
-import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.graph.DexProgramClass;
-import com.android.tools.r8.graph.DexString;
-import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.naming.MemberNaming.MethodSignature;
-import com.android.tools.r8.utils.DescriptorUtils;
-import com.google.common.collect.Sets;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.List;
-import java.util.Set;
-
-public class MinifiedNameMapPrinter {
-
-  private static final String NEW_LINE = "\n";
-  private final DexApplication application;
-  private final NamingLens namingLens;
-  private final Set<DexType> seenTypes = Sets.newIdentityHashSet();
-
-  public MinifiedNameMapPrinter(DexApplication application, NamingLens namingLens) {
-    this.application = application;
-    this.namingLens = namingLens;
-  }
-
-  private <T> T[] sortedCopy(T[] source, Comparator<? super T> comparator) {
-    T copy[] = Arrays.copyOf(source, source.length);
-    Arrays.sort(copy, comparator);
-    return copy;
-  }
-
-  private <T> List<T> sortedCopy(List<T> source, Comparator<? super T> comparator) {
-    List<T> copy = new ArrayList<>(source);
-    Collections.sort(copy, comparator);
-    return copy;
-  }
-
-  private void writeClass(DexProgramClass clazz, StringBuilder out) {
-    seenTypes.add(clazz.type);
-    DexString descriptor = namingLens.lookupDescriptor(clazz.type);
-    out.append(DescriptorUtils.descriptorToJavaType(clazz.type.descriptor.toSourceString()));
-    out.append(" -> ");
-    out.append(DescriptorUtils.descriptorToJavaType(descriptor.toSourceString()));
-    out.append(":").append(NEW_LINE);
-    writeFields(sortedCopy(
-        clazz.instanceFields(), Comparator.comparing(DexEncodedField::toSourceString)), out);
-    writeFields(sortedCopy(
-        clazz.staticFields(), Comparator.comparing(DexEncodedField::toSourceString)), out);
-    writeMethods(sortedCopy(
-        clazz.directMethods(), Comparator.comparing(DexEncodedMethod::toSourceString)), out);
-    writeMethods(sortedCopy(
-        clazz.virtualMethods(), Comparator.comparing(DexEncodedMethod::toSourceString)), out);
-  }
-
-  private void writeType(DexType type, StringBuilder out) {
-    if (type.isClassType() && seenTypes.add(type)) {
-      DexString descriptor = namingLens.lookupDescriptor(type);
-      out.append(DescriptorUtils.descriptorToJavaType(type.descriptor.toSourceString()));
-      out.append(" -> ");
-      out.append(DescriptorUtils.descriptorToJavaType(descriptor.toSourceString()));
-      out.append(":").append(NEW_LINE);
-    }
-  }
-
-  private void writeFields(List<DexEncodedField> fields, StringBuilder out) {
-    for (DexEncodedField encodedField : fields) {
-      DexField field = encodedField.field;
-      DexString renamed = namingLens.lookupName(field);
-      if (renamed != field.name) {
-        out.append("    ");
-        out.append(field.type.toSourceString());
-        out.append(" ");
-        out.append(field.name.toSourceString());
-        out.append(" -> ");
-        out.append(renamed.toSourceString()).append(NEW_LINE);
-      }
-    }
-  }
-
-  private void writeMethod(MethodSignature signature, String renamed, StringBuilder out) {
-    out.append("    ");
-    out.append(signature.toString());
-    out.append(" -> ");
-    out.append(renamed).append(NEW_LINE);
-  }
-
-  private void writeMethods(List<DexEncodedMethod> methods, StringBuilder out) {
-    for (DexEncodedMethod encodedMethod : methods) {
-      DexMethod method = encodedMethod.method;
-      DexString renamed = namingLens.lookupName(method);
-      if (renamed != method.name) {
-        MethodSignature signature = MethodSignature.fromDexMethod(method);
-        String renamedSourceString = renamed.toSourceString();
-        writeMethod(signature, renamedSourceString, out);
-      }
-    }
-  }
-
-  public void write(StringBuilder out) {
-    // First write out all classes that have been renamed.
-    List<DexProgramClass> classes = new ArrayList<>(application.classes());
-    classes.sort(Comparator.comparing(DexProgramClass::toSourceString));
-    classes.forEach(clazz -> writeClass(clazz, out));
-    // Now write out all types only mentioned in descriptors that have been renamed.
-    namingLens.forAllRenamedTypes(type -> writeType(type, out));
-  }
-}
diff --git a/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java b/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java
index 1fcb9e0..b64646d 100644
--- a/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.shaking.ScopedDexMethodSet.AddMethodIfMoreVisibleResult;
+import com.android.tools.r8.utils.IterableUtils;
 import java.util.ArrayList;
 import java.util.List;
 
@@ -42,7 +43,8 @@
     DexClass holder = appView.definitionFor(type);
     scope = scope.newNestedScope();
     if (holder != null && holder.isProgramClass()) {
-      DexEncodedMethod[] newVirtualMethods = processMethods(holder.virtualMethods());
+      DexEncodedMethod[] newVirtualMethods =
+          processMethods(IterableUtils.ensureUnmodifiableList(holder.virtualMethods()));
       if (newVirtualMethods != null) {
         holder.setVirtualMethods(newVirtualMethods);
       }
diff --git a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
index 4bb1b2b..584b84b 100644
--- a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
@@ -251,8 +251,9 @@
     }
     assert definition.isInterface();
     boolean liveGetter =
-        definition.virtualMethods().stream()
-            .anyMatch(method -> method.method.name == original.name);
+        definition
+            .getMethodCollection()
+            .hasVirtualMethods(method -> method.method.name == original.name);
     return liveGetter ? original : null;
   }
 
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/shaking/StaticClassMerger.java b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
index dc69de3..a96194f 100644
--- a/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
@@ -31,6 +31,7 @@
 import com.google.common.collect.Streams;
 import java.util.ArrayList;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -267,8 +268,7 @@
       // TODO(b/141452765): Allow class merging between classes in features.
       return MergeGroup.DONT_MERGE;
     }
-    if (clazz.staticFields().size() + clazz.directMethods().size() + clazz.virtualMethods().size()
-        == 0) {
+    if (clazz.staticFields().size() + clazz.getMethodCollection().size() == 0) {
       return MergeGroup.DONT_MERGE;
     }
     if (clazz.instanceFields().size() > 0) {
@@ -278,10 +278,10 @@
         .anyMatch(field -> appView.appInfo().isPinned(field.field))) {
       return MergeGroup.DONT_MERGE;
     }
-    if (clazz.directMethods().stream().anyMatch(DexEncodedMethod::isInitializer)) {
+    if (clazz.getMethodCollection().hasDirectMethods(DexEncodedMethod::isInitializer)) {
       return MergeGroup.DONT_MERGE;
     }
-    if (!clazz.virtualMethods().stream().allMatch(DexEncodedMethod::isPrivateMethod)) {
+    if (clazz.getMethodCollection().hasVirtualMethods(method -> !method.isPrivateMethod())) {
       return MergeGroup.DONT_MERGE;
     }
     if (clazz.isInANest()) {
@@ -427,12 +427,12 @@
       return false;
     }
     // Check that all of the members are private or public.
-    if (!clazz.directMethods().stream()
-        .allMatch(method -> method.accessFlags.isPrivate() || method.accessFlags.isPublic())) {
+    if (clazz
+        .getMethodCollection()
+        .hasDirectMethods(method -> !method.isPrivate() && !method.isPublic())) {
       return false;
     }
-    if (!clazz.staticFields().stream()
-        .allMatch(field -> field.accessFlags.isPrivate() || field.accessFlags.isPublic())) {
+    if (!clazz.staticFields().stream().allMatch(field -> field.isPrivate() || field.isPublic())) {
       return false;
     }
 
@@ -440,7 +440,7 @@
     // virtual methods are private. Therefore, we don't need to consider check if there are any
     // package-private or protected instance fields or virtual methods here.
     assert clazz.instanceFields().size() == 0;
-    assert clazz.virtualMethods().stream().allMatch(method -> method.accessFlags.isPrivate());
+    assert !clazz.getMethodCollection().hasVirtualMethods(method -> !method.isPrivate());
 
     // Check that no methods access package-private or protected members.
     IllegalAccessDetector registry = new IllegalAccessDetector(appView, clazz);
@@ -489,20 +489,20 @@
   }
 
   private List<DexEncodedMethod> mergeMethods(
-      List<DexEncodedMethod> sourceMethods,
-      List<DexEncodedMethod> targetMethods,
+      Iterable<DexEncodedMethod> sourceMethods,
+      Iterable<DexEncodedMethod> targetMethods,
       DexProgramClass targetClass) {
     // Move source methods to result one by one, renaming them if needed.
     MethodSignatureEquivalence equivalence = MethodSignatureEquivalence.get();
-    Set<Wrapper<DexMethod>> existingMethods =
-        targetMethods.stream()
-            .map(targetMethod -> equivalence.wrap(targetMethod.method))
-            .collect(Collectors.toSet());
+    Set<Wrapper<DexMethod>> existingMethods = new HashSet<>();
+    for (DexEncodedMethod targetMethod : targetMethods) {
+      existingMethods.add(equivalence.wrap(targetMethod.method));
+    }
 
     Predicate<DexMethod> availableMethodSignatures =
         method -> !existingMethods.contains(equivalence.wrap(method));
 
-    List<DexEncodedMethod> newMethods = new ArrayList<>(sourceMethods.size());
+    List<DexEncodedMethod> newMethods = new ArrayList<>();
     for (DexEncodedMethod sourceMethod : sourceMethods) {
       DexEncodedMethod sourceMethodAfterMove =
           renameMethodIfNeeded(sourceMethod, targetClass, availableMethodSignatures);
diff --git a/src/main/java/com/android/tools/r8/shaking/TreePruner.java b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
index 6f2010c..6560ebc 100644
--- a/src/main/java/com/android/tools/r8/shaking/TreePruner.java
+++ b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
@@ -21,6 +21,7 @@
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.utils.ExceptionUtils;
 import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.IterableUtils;
 import com.android.tools.r8.utils.Timing;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
@@ -254,6 +255,10 @@
     return -1;
   }
 
+  private DexEncodedMethod[] reachableMethods(Iterable<DexEncodedMethod> methods, DexClass clazz) {
+    return reachableMethods(IterableUtils.ensureUnmodifiableList(methods), clazz);
+  }
+
   private DexEncodedMethod[] reachableMethods(List<DexEncodedMethod> methods, DexClass clazz) {
     AppInfoWithLiveness appInfo = appView.appInfo();
     InternalOptions options = appView.options();
diff --git a/src/main/java/com/android/tools/r8/utils/ClassProvider.java b/src/main/java/com/android/tools/r8/utils/ClassProvider.java
index 47d273b..40d5087 100644
--- a/src/main/java/com/android/tools/r8/utils/ClassProvider.java
+++ b/src/main/java/com/android/tools/r8/utils/ClassProvider.java
@@ -15,8 +15,6 @@
 import com.google.common.collect.ImmutableListMultimap;
 import com.google.common.collect.Multimap;
 import com.google.common.collect.Sets;
-import com.google.common.io.Closer;
-import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.List;
@@ -96,12 +94,11 @@
       String descriptor = type.descriptor.toString();
       ProgramResource resource = provider.getProgramResource(descriptor);
       if (resource != null) {
-        try (Closer closer = Closer.create()) {
+        try {
           JarClassFileReader classReader =
               new JarClassFileReader(reader, classKind.bridgeConsumer(classConsumer));
-          classReader.read(
-              resource.getOrigin(), classKind, closer.register(resource.getByteStream()));
-        } catch (ResourceException | IOException e) {
+          classReader.read(resource, classKind);
+        } catch (ResourceException e) {
           throw new CompilationError("Failed to load class: " + descriptor, e);
         }
       }
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/IntBox.java b/src/main/java/com/android/tools/r8/utils/IntBox.java
index 9f4ac85..ebb92ca 100644
--- a/src/main/java/com/android/tools/r8/utils/IntBox.java
+++ b/src/main/java/com/android/tools/r8/utils/IntBox.java
@@ -22,6 +22,10 @@
     return value++;
   }
 
+  public void increment() {
+    value++;
+  }
+
   public void set(int value) {
     this.value = value;
   }
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/IterableUtils.java b/src/main/java/com/android/tools/r8/utils/IterableUtils.java
index ea35dfb..af3208f 100644
--- a/src/main/java/com/android/tools/r8/utils/IterableUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/IterableUtils.java
@@ -4,10 +4,23 @@
 
 package com.android.tools.r8.utils;
 
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
 import java.util.function.Predicate;
 
 public class IterableUtils {
 
+  public static <T> List<T> ensureUnmodifiableList(Iterable<T> iterable) {
+    List<T> list;
+    if (iterable instanceof List<?>) {
+      list = (List<T>) iterable;
+    } else {
+      list = toNewArrayList(iterable);
+    }
+    return Collections.unmodifiableList(list);
+  }
+
   public static <T> int firstIndexMatching(Iterable<T> iterable, Predicate<T> tester) {
     int i = 0;
     for (T element : iterable) {
@@ -19,7 +32,21 @@
     return -1;
   }
 
-  public static <T> Iterable<T> filter(Iterable<T> methods, Predicate<T> predicate) {
-    return () -> IteratorUtils.filter(methods.iterator(), predicate);
+  public static <T> Iterable<T> filter(Iterable<T> iterable, Predicate<T> predicate) {
+    return () -> IteratorUtils.filter(iterable.iterator(), predicate);
+  }
+
+  public static <T> int size(Iterable<T> iterable) {
+    int result = 0;
+    for (T element : iterable) {
+      result++;
+    }
+    return result;
+  }
+
+  public static <T> List<T> toNewArrayList(Iterable<T> iterable) {
+    List<T> result = new ArrayList<>();
+    iterable.forEach(result::add);
+    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 d62402b..a785262b 100644
--- a/src/main/java/com/android/tools/r8/utils/LineNumberOptimizer.java
+++ b/src/main/java/com/android/tools/r8/utils/LineNumberOptimizer.java
@@ -540,7 +540,7 @@
   private static IdentityHashMap<DexString, List<DexEncodedMethod>> groupMethodsByRenamedName(
       GraphLense graphLens, NamingLens namingLens, DexProgramClass clazz) {
     IdentityHashMap<DexString, List<DexEncodedMethod>> methodsByRenamedName =
-        new IdentityHashMap<>(clazz.directMethods().size() + clazz.virtualMethods().size());
+        new IdentityHashMap<>(clazz.getMethodCollection().size());
     for (DexEncodedMethod encodedMethod : clazz.methods()) {
       // Add method only if renamed, moved, or contains positions.
       DexMethod method = encodedMethod.method;
diff --git a/src/main/java/com/android/tools/r8/utils/OneShotByteResource.java b/src/main/java/com/android/tools/r8/utils/OneShotByteResource.java
index 1dfbc64..070e9df 100644
--- a/src/main/java/com/android/tools/r8/utils/OneShotByteResource.java
+++ b/src/main/java/com/android/tools/r8/utils/OneShotByteResource.java
@@ -43,8 +43,13 @@
 
   @Override
   public InputStream getByteStream() throws ResourceException {
+    return new ByteArrayInputStream(getBytes());
+  }
+
+  @Override
+  public byte[] getBytes() throws ResourceException {
     assert bytes != null;
-    InputStream result = new ByteArrayInputStream(bytes);
+    byte[] result = bytes;
     bytes = null;
     return result;
   }
diff --git a/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java b/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java
index 3681a77..dd5b43a 100644
--- a/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java
+++ b/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java
@@ -90,8 +90,9 @@
   }
 
   private static boolean assertEqualClasses(DexProgramClass a, DexProgramClass b) {
-    assert a.virtualMethods().size() == b.virtualMethods().size();
-    assert a.directMethods().size() == b.directMethods().size();
+    assert a.getMethodCollection().numberOfDirectMethods()
+        == b.getMethodCollection().numberOfDirectMethods();
+    assert a.getMethodCollection().size() == b.getMethodCollection().size();
     return true;
   }
 }
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..2a16dbf 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,91 @@
   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 indexSupplier = new IntBox();
     List<Future<R>> futures = new ArrayList<>();
-    items.forEach(item -> futures.add(executorService.submit(() -> consumer.apply(item))));
+    items.forEach(
+        item -> {
+          int index = indexSupplier.getAndIncrement();
+          futures.add(executorService.submit(() -> consumer.apply(item, index)));
+        });
     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/KotlinCompilerTool.java b/src/test/java/com/android/tools/r8/KotlinCompilerTool.java
index ff795bc..ca9abd4 100644
--- a/src/test/java/com/android/tools/r8/KotlinCompilerTool.java
+++ b/src/test/java/com/android/tools/r8/KotlinCompilerTool.java
@@ -43,7 +43,13 @@
   public static KotlinCompiler KOTLINC =
       new KotlinCompiler(
           "kotlinc",
-          Paths.get(ToolHelper.THIRD_PARTY_DIR, "kotlin", "kotlinc", "lib", "kotlin-compiler.jar"));
+          Paths.get(
+              ToolHelper.THIRD_PARTY_DIR,
+              "kotlin",
+              "kotlin-compiler-1.3.72",
+              "kotlinc",
+              "lib",
+              "kotlin-compiler.jar"));
 
   private final CfRuntime jdk;
   private final TestState state;
diff --git a/src/test/java/com/android/tools/r8/KotlinTestBase.java b/src/test/java/com/android/tools/r8/KotlinTestBase.java
index 1a6a428..6cd9cfd 100644
--- a/src/test/java/com/android/tools/r8/KotlinTestBase.java
+++ b/src/test/java/com/android/tools/r8/KotlinTestBase.java
@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8;
 
+import static org.hamcrest.CoreMatchers.containsString;
+
 import com.android.tools.r8.ToolHelper.KotlinTargetVersion;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.FileUtils;
@@ -12,6 +14,7 @@
 import java.nio.file.Paths;
 import java.util.List;
 import java.util.stream.Collectors;
+import org.hamcrest.Matcher;
 
 public abstract class KotlinTestBase extends TestBase {
 
@@ -66,4 +69,8 @@
   protected Path getMappingfile(String folder, String mappingFileName) {
     return Paths.get(ToolHelper.TESTS_DIR, RSRC, folder, mappingFileName);
   }
+
+  protected static Matcher<String> expectedInfoMessagesFromKotlinStdLib() {
+    return containsString("No VersionRequirement");
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/OrderedClassFileResourceProviderTest.java b/src/test/java/com/android/tools/r8/OrderedClassFileResourceProviderTest.java
index dc497c4..5256efd 100644
--- a/src/test/java/com/android/tools/r8/OrderedClassFileResourceProviderTest.java
+++ b/src/test/java/com/android/tools/r8/OrderedClassFileResourceProviderTest.java
@@ -56,6 +56,11 @@
     }
 
     @Override
+    public byte[] getBytes() throws ResourceException {
+      return null;
+    }
+
+    @Override
     public Set<String> getClassDescriptors() {
       return null;
     }
diff --git a/src/test/java/com/android/tools/r8/R8RunExamplesAndroidOTest.java b/src/test/java/com/android/tools/r8/R8RunExamplesAndroidOTest.java
index 5eb1ad48..9252555 100644
--- a/src/test/java/com/android/tools/r8/R8RunExamplesAndroidOTest.java
+++ b/src/test/java/com/android/tools/r8/R8RunExamplesAndroidOTest.java
@@ -164,7 +164,7 @@
         .withBuilderTransformation(ToolHelper::allowTestProguardOptions)
         .withBuilderTransformation(
             b -> b.addProguardConfiguration(PROGUARD_OPTIONS_N_PLUS, Origin.unknown()))
-        .withDexCheck(inspector -> checkLambdaCount(inspector, 33, "lambdadesugaringnplus"))
+        .withDexCheck(inspector -> checkLambdaCount(inspector, 35, "lambdadesugaringnplus"))
         .run();
 
     test("lambdadesugaringnplus", "lambdadesugaringnplus", "LambdasWithStaticAndDefaultMethods")
@@ -188,7 +188,7 @@
         .withBuilderTransformation(ToolHelper::allowTestProguardOptions)
         .withBuilderTransformation(
             b -> b.addProguardConfiguration(PROGUARD_OPTIONS_N_PLUS, Origin.unknown()))
-        .withDexCheck(inspector -> checkLambdaCount(inspector, 33, "lambdadesugaringnplus"))
+        .withDexCheck(inspector -> checkLambdaCount(inspector, 35, "lambdadesugaringnplus"))
         .run();
 
     test("lambdadesugaringnplus", "lambdadesugaringnplus", "LambdasWithStaticAndDefaultMethods")
diff --git a/src/test/java/com/android/tools/r8/R8UnreachableCodeTest.java b/src/test/java/com/android/tools/r8/R8UnreachableCodeTest.java
index fd9259f..2daa0a9 100644
--- a/src/test/java/com/android/tools/r8/R8UnreachableCodeTest.java
+++ b/src/test/java/com/android/tools/r8/R8UnreachableCodeTest.java
@@ -48,7 +48,7 @@
             AppView.createForR8(new AppInfoWithClassHierarchy(application), options), null);
     converter.optimize();
     DexProgramClass clazz = application.classes().iterator().next();
-    assertEquals(4, clazz.directMethods().size());
+    assertEquals(4, clazz.getMethodCollection().numberOfDirectMethods());
     for (DexEncodedMethod method : clazz.directMethods()) {
       if (!method.method.name.toString().equals("main")) {
         assertEquals(2, method.getCode().asDexCode().instructions.length);
diff --git a/src/test/java/com/android/tools/r8/ToolHelper.java b/src/test/java/com/android/tools/r8/ToolHelper.java
index c992015..f19c7ce 100644
--- a/src/test/java/com/android/tools/r8/ToolHelper.java
+++ b/src/test/java/com/android/tools/r8/ToolHelper.java
@@ -134,13 +134,17 @@
   public static final String RHINO_ANDROID_JAR =
       "third_party/rhino-android-1.1.1/rhino-android-1.1.1.jar";
   public static final String RHINO_JAR = "third_party/rhino-1.7.10/rhino-1.7.10.jar";
-  static final String KT_PRELOADER = "third_party/kotlin/kotlinc/lib/kotlin-preloader.jar";
-  public static final String KT_COMPILER = "third_party/kotlin/kotlinc/lib/kotlin-compiler.jar";
+  static final String KT_PRELOADER =
+      "third_party/kotlin/kotlin-compiler-1.3.72/kotlinc/lib/kotlin-preloader.jar";
+  public static final String KT_COMPILER =
+      "third_party/kotlin/kotlin-compiler-1.3.72/kotlinc/lib/kotlin-compiler.jar";
   public static final String K2JVMCompiler = "org.jetbrains.kotlin.cli.jvm.K2JVMCompiler";
-  public static final String KT_STDLIB = "third_party/kotlin/kotlinc/lib/kotlin-stdlib.jar";
-  public static final String KT_REFLECT = "third_party/kotlin/kotlinc/lib/kotlin-reflect.jar";
+  public static final String KT_STDLIB =
+      "third_party/kotlin/kotlin-compiler-1.3.72/kotlinc/lib/kotlin-stdlib.jar";
+  public static final String KT_REFLECT =
+      "third_party/kotlin/kotlin-compiler-1.3.72/kotlinc/lib/kotlin-reflect.jar";
   public static final String KT_SCRIPT_RT =
-      "third_party/kotlin/kotlinc/lib/kotlin-script-runtime.jar";
+      "third_party/kotlin/kotlin-compiler-1.3.72/kotlinc/lib/kotlin-script-runtime.jar";
   private static final String ANDROID_JAR_PATTERN = "third_party/android_jar/lib-v%d/android.jar";
   private static final AndroidApiLevel DEFAULT_MIN_SDK = AndroidApiLevel.I;
 
@@ -758,8 +762,8 @@
     }
     // Search for an android jar.
     for (AndroidApiLevel level : AndroidApiLevel.getAndroidApiLevelsSorted()) {
-      if (level.getLevel() >= apiLevel.getLevel() && hasAndroidJar(apiLevel)) {
-        return getAndroidJar(apiLevel.getLevel());
+      if (level.getLevel() >= apiLevel.getLevel() && hasAndroidJar(level)) {
+        return getAndroidJar(level.getLevel());
       }
     }
     return getAndroidJar(AndroidApiLevel.LATEST);
diff --git a/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/NonSuperclassBridgeHoistingTest.java b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/NonSuperclassBridgeHoistingTest.java
index 9c4a0d6..87310d2 100644
--- a/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/NonSuperclassBridgeHoistingTest.java
+++ b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/NonSuperclassBridgeHoistingTest.java
@@ -5,7 +5,7 @@
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static org.hamcrest.MatcherAssert.assertThat;
-import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
@@ -55,7 +55,7 @@
   private void inspect(CodeInspector inspector) {
     ClassSubject aClassSubject = inspector.clazz(A.class);
     assertThat(aClassSubject, isPresent());
-    assertEquals(0, aClassSubject.getDexProgramClass().virtualMethods().size());
+    assertFalse(aClassSubject.getDexProgramClass().getMethodCollection().hasVirtualMethods());
 
     ClassSubject b1ClassSubject = inspector.clazz(B.class);
     assertThat(b1ClassSubject, isPresent());
diff --git a/src/test/java/com/android/tools/r8/cf/IdenticalCatchHandlerTest.java b/src/test/java/com/android/tools/r8/cf/IdenticalCatchHandlerTest.java
index e0818bb..8d25f23 100644
--- a/src/test/java/com/android/tools/r8/cf/IdenticalCatchHandlerTest.java
+++ b/src/test/java/com/android/tools/r8/cf/IdenticalCatchHandlerTest.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.cf;
 
+import static com.google.common.base.Predicates.alwaysTrue;
 import static org.junit.Assert.assertEquals;
 
 import com.android.tools.r8.ClassFileConsumer;
@@ -72,7 +73,7 @@
   private int countCatchHandlers(AndroidApp inputApp) throws Exception {
     CodeInspector inspector = new CodeInspector(inputApp);
     DexProgramClass dexClass = inspector.clazz(TestClass.class).getDexProgramClass();
-    Code code = dexClass.virtualMethods().get(0).getCode();
+    Code code = dexClass.lookupVirtualMethod(alwaysTrue()).getCode();
     if (code.isCfCode()) {
       CfCode cfCode = code.asCfCode();
       Set<CfLabel> targets = Sets.newIdentityHashSet();
diff --git a/src/test/java/com/android/tools/r8/cf/NonidenticalCatchHandlerTest.java b/src/test/java/com/android/tools/r8/cf/NonidenticalCatchHandlerTest.java
index fcb172b..a2e6005 100644
--- a/src/test/java/com/android/tools/r8/cf/NonidenticalCatchHandlerTest.java
+++ b/src/test/java/com/android/tools/r8/cf/NonidenticalCatchHandlerTest.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.cf;
 
+import static com.google.common.base.Predicates.alwaysTrue;
 import static org.junit.Assert.assertEquals;
 
 import com.android.tools.r8.ClassFileConsumer;
@@ -71,7 +72,7 @@
   private int countCatchHandlers(AndroidApp inputApp) throws Exception {
     CodeInspector inspector = new CodeInspector(inputApp);
     DexProgramClass dexClass = inspector.clazz(TestClass.class).getDexProgramClass();
-    Code code = dexClass.virtualMethods().get(0).getCode();
+    Code code = dexClass.lookupVirtualMethod(alwaysTrue()).getCode();
     if (code.isCfCode()) {
       CfCode cfCode = code.asCfCode();
       Set<CfLabel> targets = Sets.newIdentityHashSet();
diff --git a/src/test/java/com/android/tools/r8/cfmethodgeneration/MethodGenerationBase.java b/src/test/java/com/android/tools/r8/cfmethodgeneration/MethodGenerationBase.java
index 9cffd4e..164259f 100644
--- a/src/test/java/com/android/tools/r8/cfmethodgeneration/MethodGenerationBase.java
+++ b/src/test/java/com/android/tools/r8/cfmethodgeneration/MethodGenerationBase.java
@@ -21,7 +21,6 @@
 import com.google.common.collect.ImmutableList;
 import java.io.File;
 import java.io.IOException;
-import java.io.InputStream;
 import java.io.PrintStream;
 import java.nio.file.Files;
 import java.nio.file.Path;
@@ -108,9 +107,7 @@
               }
             });
     for (Class<?> clazz : getMethodTemplateClasses()) {
-      try (InputStream stream = Files.newInputStream(ToolHelper.getClassFileForTestClass(clazz))) {
-        reader.read(Origin.unknown(), ClassKind.PROGRAM, stream);
-      }
+      reader.read(Origin.unknown(), ClassKind.PROGRAM, ToolHelper.getClassAsBytes(clazz));
     }
   }
 
diff --git a/src/test/java/com/android/tools/r8/debug/KotlinInlineTest.java b/src/test/java/com/android/tools/r8/debug/KotlinInlineTest.java
index 8d209b0..894e7d5 100644
--- a/src/test/java/com/android/tools/r8/debug/KotlinInlineTest.java
+++ b/src/test/java/com/android/tools/r8/debug/KotlinInlineTest.java
@@ -147,7 +147,7 @@
 
   private static String mangleLambdaNameFromInlineScope(String functionName, int lambdaId) {
     assert lambdaId > 0;
-    return "$i$a$" + lambdaId + "$" + functionName;
+    return "$i$a$" + functionName + "$" + lambdaId;
   }
 
   private static String mangleLvNameFromInlineScope(String lvName, int inlineDepth) {
@@ -167,59 +167,74 @@
         DEBUGGEE_CLASS,
         breakpoint(DEBUGGEE_CLASS, inliningMethodName),
         run(),
-        inspect(s -> {
-          assertEquals(inliningMethodName, s.getMethodName());
-          assertEquals(16, s.getLineNumber());
-          s.checkLocal("this");
-        }),
+        inspect(
+            s -> {
+              assertEquals(inliningMethodName, s.getMethodName());
+              assertEquals(16, s.getLineNumber());
+              s.checkLocal("this");
+            }),
         stepInto(),
-        inspect(s -> {
-          // We must have stepped into the code of the inlined method but the actual current method
-          // did not change.
-          assertEquals(inliningMethodName, s.getMethodName());
-          // TODO(shertz) get the original line if JSR45 is supported by the targeted ART runtime.
-          s.checkLocal("this");
-        }),
+        inspect(
+            s -> {
+              // We must have stepped into the code of the inlined method but the actual current
+              // method
+              // did not change.
+              assertEquals(inliningMethodName, s.getMethodName());
+              // TODO(shertz) get the original line if JSR45 is supported by the targeted ART
+              // runtime.
+              s.checkLocal("this");
+            }),
         stepInto(),
-        inspect(s -> {
-          assertEquals(inliningMethodName, s.getMethodName());
-          assertEquals(17, s.getLineNumber());
-          s.checkLocal("this");
-        }),
+        inspect(
+            s -> {
+              assertEquals(inliningMethodName, s.getMethodName());
+              assertEquals(17, s.getLineNumber());
+              s.checkLocal("this");
+            }),
         stepInto(),
-        inspect(s -> {
-          assertEquals(inliningMethodName, s.getMethodName());
-          assertEquals(18, s.getLineNumber());
-          s.checkLocal("this");
-          s.checkLocal("inA", Value.createInt(1));
-          // This is a "hidden" lv added by Kotlin (which is neither initialized nor used).
-          s.checkLocal(mangleFunctionNameFromInlineScope("inlinedA"));
-          s.checkLocal(mangleLambdaNameFromInlineScope("inlinedA", 1));
-        }),
+        inspect(
+            s -> {
+              assertEquals(inliningMethodName, s.getMethodName());
+              assertEquals(18, s.getLineNumber());
+              s.checkLocal("this");
+              s.checkLocal("inA", Value.createInt(1));
+              // This is a "hidden" lv added by Kotlin (which is neither initialized nor used).
+              s.checkLocal(mangleFunctionNameFromInlineScope("inlinedA"));
+              s.checkLocal(
+                  mangleLambdaNameFromInlineScope(
+                      "-inlinedA-KotlinInline$invokeInlinedFunctions", 1));
+            }),
         stepInto(),
-        inspect(s -> {
-          // We must have stepped into the code of the second inlined method but the actual current
-          // method did not change.
-          assertEquals(inliningMethodName, s.getMethodName());
-          // TODO(shertz) get the original line if JSR45 is supported by the targeted ART runtime.
-          s.checkLocal("this");
-        }),
+        inspect(
+            s -> {
+              // We must have stepped into the code of the second inlined method but the actual
+              // current
+              // method did not change.
+              assertEquals(inliningMethodName, s.getMethodName());
+              // TODO(shertz) get the original line if JSR45 is supported by the targeted ART
+              // runtime.
+              s.checkLocal("this");
+            }),
         stepInto(),
-        inspect(s -> {
-          assertEquals(inliningMethodName, s.getMethodName());
-          assertEquals(19, s.getLineNumber());
-          s.checkLocal("this");
-        }),
+        inspect(
+            s -> {
+              assertEquals(inliningMethodName, s.getMethodName());
+              assertEquals(19, s.getLineNumber());
+              s.checkLocal("this");
+            }),
         stepInto(),
-        inspect(s -> {
-          assertEquals(inliningMethodName, s.getMethodName());
-          assertEquals(20, s.getLineNumber());
-          s.checkLocal("this");
-          s.checkLocal("inB", Value.createInt(2));
-          // This is a "hidden" lv added by Kotlin (which is neither initialized nor used).
-          s.checkLocal(mangleFunctionNameFromInlineScope("inlinedB"));
-          s.checkLocal(mangleLambdaNameFromInlineScope("inlinedB", 1));
-        }),
+        inspect(
+            s -> {
+              assertEquals(inliningMethodName, s.getMethodName());
+              assertEquals(20, s.getLineNumber());
+              s.checkLocal("this");
+              s.checkLocal("inB", Value.createInt(2));
+              // This is a "hidden" lv added by Kotlin (which is neither initialized nor used).
+              s.checkLocal(mangleFunctionNameFromInlineScope("inlinedB"));
+              s.checkLocal(
+                  mangleLambdaNameFromInlineScope(
+                      "-inlinedB-KotlinInline$invokeInlinedFunctions$1", 1));
+            }),
         run());
   }
 
@@ -239,7 +254,7 @@
 
     // Local variables that represent the scope (start,end) of lambda's code that has been inlined.
     final String inlinee2_lambda1_inlineScope = mangleLambdaNameFromInlineScope("inlinee2", 1);
-    final String inlinee2_lambda2_inlineScope = mangleLambdaNameFromInlineScope("inlinee2", 2);
+    final String inlinee2_lambda2_inlineScope = "$i$a$-inlinee2-KotlinInline$inlinee1$1$iv";
     final String c_mangledLvName = mangleLvNameFromInlineScope("c", 1);
     final String left_mangledLvName = mangleLvNameFromInlineScope("left", 1);
     final String right_mangledLvName = mangleLvNameFromInlineScope("right", 1);
@@ -250,11 +265,12 @@
         DEBUGGEE_CLASS,
         breakpoint(DEBUGGEE_CLASS, inliningMethodName),
         run(),
-        inspect(s -> {
-          assertEquals(inliningMethodName, s.getMethodName());
-          assertEquals(52, s.getLineNumber());
-          s.checkLocal("this");
-        }),
+        inspect(
+            s -> {
+              assertEquals(inliningMethodName, s.getMethodName());
+              assertEquals(52, s.getLineNumber());
+              s.checkLocal("this");
+            }),
         checkLocal("this"),
         checkNoLocals("l1", "l2"),
         stepOver(),
@@ -268,10 +284,11 @@
         // We jumped into 1st inlinee but the current method is the same
         checkMethod(DEBUGGEE_CLASS, inliningMethodName),
         checkLocal(inlinee1_inlineScope),
-        inspect(state -> {
-          assertEquals(SOURCE_FILE, state.getSourceFile());
-          assertTrue(state.getLineNumber() > maxLineNumber);
-        }),
+        inspect(
+            state -> {
+              assertEquals(SOURCE_FILE, state.getSourceFile());
+              assertTrue(state.getLineNumber() > maxLineNumber);
+            }),
         checkNoLocal(c_mangledLvName),
         stepInto(),
         checkLocal(c_mangledLvName),
@@ -279,10 +296,11 @@
         // We jumped into 2nd inlinee which is nested in the 1st inlinee
         checkLocal(inlinee2_inlineScope),
         checkLocal(inlinee1_inlineScope),
-        inspect(state -> {
-          assertEquals(SOURCE_FILE, state.getSourceFile());
-          assertTrue(state.getLineNumber() > maxLineNumber);
-        }),
+        inspect(
+            state -> {
+              assertEquals(SOURCE_FILE, state.getSourceFile());
+              assertTrue(state.getLineNumber() > maxLineNumber);
+            }),
         // We must see the local variable "p" with a 2-level inline depth.
         checkLocal(p_mangledLvName),
         checkNoLocals(left_mangledLvName, right_mangledLvName),
@@ -293,10 +311,10 @@
         // Enter the inlined lambda
         stepInto(),
         checkLocal(p_mangledLvName),
-        checkLocal(inlinee2_lambda1_inlineScope),
+        checkLocal(inlinee2_lambda2_inlineScope),
         checkNoLocals(left_mangledLvName, right_mangledLvName),
         stepInto(),
-        checkLocal(inlinee2_lambda1_inlineScope),
+        checkLocal(inlinee2_lambda2_inlineScope),
         checkLocal(left_mangledLvName),
         checkNoLocal(right_mangledLvName),
         stepInto(),
@@ -307,14 +325,14 @@
         checkLine(SOURCE_FILE, 34),
         stepOut(),
         // We're back to the inline section, at the end of the lambda
-        inspect(state -> {
-          assertEquals(SOURCE_FILE, state.getSourceFile());
-          assertTrue(state.getLineNumber() > maxLineNumber);
-        }),
+        inspect(
+            state -> {
+              assertEquals(SOURCE_FILE, state.getSourceFile());
+              assertTrue(state.getLineNumber() > maxLineNumber);
+            }),
         checkLocal(inlinee1_inlineScope),
         checkLocal(inlinee2_inlineScope),
-        checkLocal(inlinee2_lambda1_inlineScope),
-        checkNoLocal(inlinee2_lambda2_inlineScope),
+        checkLocal(inlinee2_lambda2_inlineScope),
         stepInto(),
         // We're in inlinee2, after the call to the inlined lambda.
         checkLocal(inlinee1_inlineScope),
@@ -349,7 +367,7 @@
         checkLocal(inlinee1_inlineScope),
         checkLocal(inlinee2_inlineScope),
         checkNoLocal(inlinee2_lambda1_inlineScope),
-        checkLocal(inlinee2_lambda2_inlineScope),
+        checkNoLocal(inlinee2_lambda2_inlineScope),
         // Enter the call to "foo"
         stepInto(),
         checkMethod(DEBUGGEE_CLASS, "foo"),
diff --git a/src/test/java/com/android/tools/r8/debug/KotlinStdLibCompilationTest.java b/src/test/java/com/android/tools/r8/debug/KotlinStdLibCompilationTest.java
index 96ae9d6..ae1c81c 100644
--- a/src/test/java/com/android/tools/r8/debug/KotlinStdLibCompilationTest.java
+++ b/src/test/java/com/android/tools/r8/debug/KotlinStdLibCompilationTest.java
@@ -13,8 +13,6 @@
 import com.android.tools.r8.TestParametersBuilder;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.ToolHelper;
-import java.nio.file.Path;
-import java.nio.file.Paths;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -23,14 +21,6 @@
 @RunWith(Parameterized.class)
 public class KotlinStdLibCompilationTest extends TestBase {
 
-  private static final Path KOTLIN_STDLIB =
-      Paths.get(
-          ToolHelper.THIRD_PARTY_DIR,
-          "kotlin-compiler-1.3.41",
-          "kotlinc",
-          "lib",
-          "kotlin-stdlib.jar");
-
   private final TestParameters parameters;
 
   @Parameters(name = "{0}")
@@ -46,7 +36,7 @@
   public void testD8() throws CompilationFailedException {
     assumeTrue(parameters.isDexRuntime());
     testForD8()
-        .addProgramFiles(KOTLIN_STDLIB)
+        .addProgramFiles(ToolHelper.getKotlinStdlibJar())
         .setMinApi(parameters.getApiLevel())
         .compileWithExpectedDiagnostics(TestDiagnosticMessages::assertNoMessages);
   }
@@ -54,7 +44,7 @@
   @Test
   public void testR8() throws CompilationFailedException {
     testForR8(parameters.getBackend())
-        .addProgramFiles(KOTLIN_STDLIB)
+        .addProgramFiles(ToolHelper.getKotlinStdlibJar())
         .noMinification()
         .noTreeShaking()
         .addKeepAllAttributes()
diff --git a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/conversiontests/ConversionIntroduceInterfaceMethodTest.java b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/conversiontests/ConversionIntroduceInterfaceMethodTest.java
index 83dc73e..14f3ded 100644
--- a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/conversiontests/ConversionIntroduceInterfaceMethodTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/conversiontests/ConversionIntroduceInterfaceMethodTest.java
@@ -12,6 +12,7 @@
 import com.android.tools.r8.desugar.desugaredlibrary.DesugaredLibraryTestBase;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.BooleanUtils;
+import com.android.tools.r8.utils.IterableUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
 import com.android.tools.r8.utils.codeinspector.FoundClassSubject;
@@ -103,9 +104,10 @@
     assertEquals(
         "Missing duplicated forEach",
         2,
-        myCollection.getDexProgramClass().virtualMethods().stream()
-            .filter(m -> m.method.name.toString().equals("forEach"))
-            .count());
+        IterableUtils.size(
+            myCollection
+                .getDexProgramClass()
+                .virtualMethods(m -> m.method.name.toString().equals("forEach"))));
   }
 
   private void assertWrapperMethodsPresent(CodeInspector inspector) {
diff --git a/src/test/java/com/android/tools/r8/enumunboxing/DoubleProcessingEnumUnboxingTest.java b/src/test/java/com/android/tools/r8/enumunboxing/DoubleProcessingEnumUnboxingTest.java
new file mode 100644
index 0000000..7582177
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/enumunboxing/DoubleProcessingEnumUnboxingTest.java
@@ -0,0 +1,117 @@
+// 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.enumunboxing;
+
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.R8TestRunResult;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.enumunboxing.examplelib1.JavaLibrary1;
+import com.android.tools.r8.ir.optimize.enums.EnumUnboxingRewriter;
+import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.utils.BooleanUtils;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import java.nio.file.Path;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+// In this test enum unboxing is performed once cf to cf then once cf to dex. The enum unboxing
+// utility class is required in both cases, and R8 should not conflict with multiple synthesized
+// classes.
+@RunWith(Parameterized.class)
+public class DoubleProcessingEnumUnboxingTest extends EnumUnboxingTestBase {
+  private final TestParameters parameters;
+  private final boolean enumValueOptimization;
+  private final KeepRule enumKeepRules;
+  private final boolean minification;
+
+  @Parameters(name = "{0} valueOpt: {1} keep: {2} minif: {3}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        getTestParameters().withDexRuntimes().withAllApiLevels().build(),
+        BooleanUtils.values(),
+        getAllEnumKeepRules(),
+        BooleanUtils.values());
+  }
+
+  public DoubleProcessingEnumUnboxingTest(
+      TestParameters parameters,
+      boolean enumValueOptimization,
+      KeepRule enumKeepRules,
+      boolean minification) {
+    this.parameters = parameters;
+    this.enumValueOptimization = enumValueOptimization;
+    this.enumKeepRules = enumKeepRules;
+    this.minification = minification;
+  }
+
+  @Test
+  public void testEnumUnboxing() throws Exception {
+    // Compile the lib cf to cf.
+    Path javaLibShrunk =
+        testForR8(Backend.CF)
+            .addProgramClasses(JavaLibrary1.class, JavaLibrary1.LibEnum1.class)
+            .addKeepMethodRules(
+                Reference.methodFromMethod(JavaLibrary1.class.getDeclaredMethod("libCall")))
+            .addKeepRules(enumKeepRules.getKeepRule())
+            .enableNeverClassInliningAnnotations()
+            .enableInliningAnnotations()
+            .minification(minification)
+            .setMinApi(parameters.getApiLevel())
+            .compile()
+            .writeToZip();
+    // Compile the app with the lib.
+    R8TestRunResult run =
+        testForR8(parameters.getBackend())
+            .addProgramClasses(App.class, App.AppEnum.class)
+            .addProgramFiles(javaLibShrunk)
+            .addKeepMainRule(App.class)
+            .addKeepRules(enumKeepRules.getKeepRule())
+            .enableNeverClassInliningAnnotations()
+            .enableInliningAnnotations()
+            .addOptionsModification(opt -> enableEnumOptions(opt, enumValueOptimization))
+            .allowDiagnosticInfoMessages()
+            .setMinApi(parameters.getApiLevel())
+            .compile()
+            .inspect(this::assertUtilityClassPresent)
+            .inspectDiagnosticMessages(
+                m -> assertEnumIsUnboxed(App.AppEnum.class, App.class.getSimpleName(), m))
+            .run(parameters.getRuntime(), App.class)
+            .assertSuccess();
+    assertLines2By2Correct(run.getStdOut());
+  }
+
+  private void assertUtilityClassPresent(CodeInspector codeInspector) {
+    assertTrue(
+        codeInspector.allClasses().stream()
+            .anyMatch(
+                c ->
+                    c.getOriginalName()
+                        .contains(EnumUnboxingRewriter.ENUM_UNBOXING_UTILITY_CLASS_NAME)));
+  }
+
+  static class App {
+    @NeverClassInline
+    enum AppEnum {
+      A,
+      B
+    }
+
+    @NeverInline
+    static AppEnum getEnum() {
+      return System.currentTimeMillis() > 0 ? AppEnum.A : AppEnum.B;
+    }
+
+    public static void main(String[] args) {
+      System.out.println(getEnum().ordinal());
+      System.out.println(0);
+      JavaLibrary1.libCall();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/enumunboxing/DoubleProcessingMergeEnumUnboxingTest.java b/src/test/java/com/android/tools/r8/enumunboxing/DoubleProcessingMergeEnumUnboxingTest.java
new file mode 100644
index 0000000..e5f3913
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/enumunboxing/DoubleProcessingMergeEnumUnboxingTest.java
@@ -0,0 +1,122 @@
+// 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.enumunboxing;
+
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.R8TestRunResult;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.enumunboxing.examplelib1.JavaLibrary1;
+import com.android.tools.r8.enumunboxing.examplelib2.JavaLibrary2;
+import com.android.tools.r8.ir.optimize.enums.EnumUnboxingRewriter;
+import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.utils.BooleanUtils;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import java.nio.file.Path;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+// In this test enum unboxing is performed twice cf to cf then once cf to dex. The enum unboxing
+// utility class is required in all the cases, and R8 should not conflict with multiple enum
+// unboxing utility synthesized classes provided as input.
+@RunWith(Parameterized.class)
+public class DoubleProcessingMergeEnumUnboxingTest extends EnumUnboxingTestBase {
+  private final TestParameters parameters;
+  private final boolean enumValueOptimization;
+  private final KeepRule enumKeepRules;
+  private final boolean minification;
+
+  @Parameters(name = "{0} valueOpt: {1} keep: {2} minif: {3}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        getTestParameters().withDexRuntimes().withAllApiLevels().build(),
+        BooleanUtils.values(),
+        getAllEnumKeepRules(),
+        BooleanUtils.values());
+  }
+
+  public DoubleProcessingMergeEnumUnboxingTest(
+      TestParameters parameters,
+      boolean enumValueOptimization,
+      KeepRule enumKeepRules,
+      boolean minification) {
+    this.parameters = parameters;
+    this.enumValueOptimization = enumValueOptimization;
+    this.enumKeepRules = enumKeepRules;
+    this.minification = minification;
+  }
+
+  @Test
+  public void testEnumUnboxing() throws Exception {
+    // Compile the lib cf to cf.
+    Path javaLibShrunk1 = compileLibrary(JavaLibrary1.class, JavaLibrary1.LibEnum1.class);
+    Path javaLibShrunk2 = compileLibrary(JavaLibrary2.class, JavaLibrary2.LibEnum2.class);
+    // Compile the app with the lib.
+    R8TestRunResult run =
+        testForR8(parameters.getBackend())
+            .addProgramClasses(App.class, App.AppEnum.class)
+            .addProgramFiles(javaLibShrunk1, javaLibShrunk2)
+            .addKeepMainRule(App.class)
+            .addKeepRules(enumKeepRules.getKeepRule())
+            .enableNeverClassInliningAnnotations()
+            .enableInliningAnnotations()
+            .addOptionsModification(opt -> enableEnumOptions(opt, enumValueOptimization))
+            .allowDiagnosticInfoMessages()
+            .setMinApi(parameters.getApiLevel())
+            .compile()
+            .inspect(this::assertUtilityClassPresent)
+            .inspectDiagnosticMessages(
+                m -> assertEnumIsUnboxed(App.AppEnum.class, App.class.getSimpleName(), m))
+            .run(parameters.getRuntime(), App.class)
+            .assertSuccess();
+    assertLines2By2Correct(run.getStdOut());
+  }
+
+  private Path compileLibrary(Class<?> libClass, Class<?> enumLibClass) throws Exception {
+    return testForR8(Backend.CF)
+        .addProgramClasses(libClass, enumLibClass)
+        .addKeepMethodRules(Reference.methodFromMethod(libClass.getDeclaredMethod("libCall")))
+        .addKeepRules(enumKeepRules.getKeepRule())
+        .enableNeverClassInliningAnnotations()
+        .enableInliningAnnotations()
+        .minification(minification)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .writeToZip();
+  }
+
+  private void assertUtilityClassPresent(CodeInspector codeInspector) {
+    assertTrue(
+        codeInspector.allClasses().stream()
+            .anyMatch(
+                c ->
+                    c.getOriginalName()
+                        .contains(EnumUnboxingRewriter.ENUM_UNBOXING_UTILITY_CLASS_NAME)));
+  }
+
+  static class App {
+    @NeverClassInline
+    enum AppEnum {
+      A,
+      B
+    }
+
+    @NeverInline
+    static AppEnum getEnum() {
+      return System.currentTimeMillis() > 0 ? AppEnum.A : AppEnum.B;
+    }
+
+    public static void main(String[] args) {
+      System.out.println(getEnum().ordinal());
+      System.out.println(0);
+      JavaLibrary1.libCall();
+      JavaLibrary2.libCall();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingTestBase.java b/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingTestBase.java
index 9f7b5bd..11ab1ae 100644
--- a/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingTestBase.java
+++ b/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingTestBase.java
@@ -94,7 +94,7 @@
 
   static List<Object[]> enumUnboxingTestParameters() {
     return buildParameters(
-        getTestParameters().withAllRuntimesAndApiLevels().withAllApiLevels().build(),
+        getTestParameters().withDexRuntimes().withAllApiLevels().build(),
         BooleanUtils.values(),
         KEEP_ENUM);
   }
diff --git a/src/test/java/com/android/tools/r8/enumunboxing/FailingEnumUnboxingTest.java b/src/test/java/com/android/tools/r8/enumunboxing/FailingEnumUnboxingTest.java
index 0441cbf..2cfe861 100644
--- a/src/test/java/com/android/tools/r8/enumunboxing/FailingEnumUnboxingTest.java
+++ b/src/test/java/com/android/tools/r8/enumunboxing/FailingEnumUnboxingTest.java
@@ -88,7 +88,12 @@
     assertTrue(inspector.clazz(EnumInstanceField.class).uniqueFieldWithName("a").isPresent());
 
     assertEquals(
-        5, inspector.clazz(EnumStaticMethod.class).getDexProgramClass().directMethods().size());
+        5,
+        inspector
+            .clazz(EnumStaticMethod.class)
+            .getDexProgramClass()
+            .getMethodCollection()
+            .numberOfDirectMethods());
     assertEquals(1, inspector.clazz(EnumVirtualMethod.class).virtualMethods().size());
   }
 
diff --git a/src/test/java/com/android/tools/r8/enumunboxing/examplelib1/JavaLibrary1.java b/src/test/java/com/android/tools/r8/enumunboxing/examplelib1/JavaLibrary1.java
new file mode 100644
index 0000000..2431724
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/enumunboxing/examplelib1/JavaLibrary1.java
@@ -0,0 +1,27 @@
+// 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.enumunboxing.examplelib1;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+
+public class JavaLibrary1 {
+
+  @NeverClassInline
+  public enum LibEnum1 {
+    A,
+    B
+  }
+
+  @NeverInline
+  private static LibEnum1 getEnum() {
+    return System.currentTimeMillis() > 0 ? LibEnum1.A : LibEnum1.B;
+  }
+
+  public static void libCall() {
+    System.out.println(getEnum().ordinal());
+    System.out.println(0);
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/enumunboxing/examplelib2/JavaLibrary2.java b/src/test/java/com/android/tools/r8/enumunboxing/examplelib2/JavaLibrary2.java
new file mode 100644
index 0000000..5266214
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/enumunboxing/examplelib2/JavaLibrary2.java
@@ -0,0 +1,27 @@
+// 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.enumunboxing.examplelib2;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+
+public class JavaLibrary2 {
+
+  @NeverClassInline
+  public enum LibEnum2 {
+    A,
+    B
+  }
+
+  @NeverInline
+  private static LibEnum2 getEnum() {
+    return System.currentTimeMillis() > 0 ? LibEnum2.A : LibEnum2.B;
+  }
+
+  public static void libCall() {
+    System.out.println(getEnum().ordinal());
+    System.out.println(0);
+  }
+}
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..b165f4b 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;
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..b7bff95 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreLatestTreeShakeJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreLatestTreeShakeJarVerificationTest.java
@@ -4,12 +4,18 @@
 package com.android.tools.r8.internal;
 
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.CompilationMode;
 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.IntOpenHashSet;
+import it.unimi.dsi.fastutil.ints.IntSet;
 import java.util.List;
+import java.util.Map;
+import java.util.concurrent.ConcurrentHashMap;
 import org.junit.Test;
 
 public class R8GMSCoreLatestTreeShakeJarVerificationTest
@@ -23,6 +29,8 @@
     List<String> additionalProguardConfiguration =
         ImmutableList.of(
             ToolHelper.PROGUARD_SETTINGS_FOR_INTERNAL_APPS + "GmsCore_proguard.config");
+
+    Map<String, IntSet> methodProcessingIds = new ConcurrentHashMap<>();
     AndroidApp app1 =
         buildAndTreeShakeFromDeployJar(
             CompilationMode.RELEASE,
@@ -31,9 +39,17 @@
             GMSCORE_LATEST_MAX_SIZE,
             additionalProguardConfiguration,
             options -> {
+              options.testing.methodProcessingIdConsumer =
+                  (method, methodProcessingId) ->
+                      assertTrue(
+                          methodProcessingIds
+                              .computeIfAbsent(
+                                  method.toSourceString(), ignore -> new IntOpenHashSet(4))
+                              .add(methodProcessingId.getPrimaryId()));
               options.proguardMapConsumer =
                   ToolHelper.consumeString(proguardMap -> this.proguardMap1 = proguardMap);
             });
+
     AndroidApp app2 =
         buildAndTreeShakeFromDeployJar(
             CompilationMode.RELEASE,
@@ -42,12 +58,23 @@
             GMSCORE_LATEST_MAX_SIZE,
             additionalProguardConfiguration,
             options -> {
+              options.testing.methodProcessingIdConsumer =
+                  (method, methodProcessingId) -> {
+                    String key = method.toSourceString();
+                    IntSet ids = methodProcessingIds.get(key);
+                    assertNotNull(ids);
+                    assertTrue(ids.remove(methodProcessingId.getPrimaryId()));
+                    if (ids.isEmpty()) {
+                      methodProcessingIds.remove(key);
+                    }
+                  };
               options.proguardMapConsumer =
                   ToolHelper.consumeString(proguardMap -> this.proguardMap2 = proguardMap);
             });
 
     // Verify that the result of the two compilations was the same.
     assertIdenticalApplications(app1, app2);
+    assertTrue(methodProcessingIds.isEmpty());
     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..98bc7ce 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
@@ -5,13 +5,19 @@
 package com.android.tools.r8.internal;
 
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.CompilationMode;
 import com.android.tools.r8.DexIndexedConsumer.ArchiveConsumer;
 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.IntOpenHashSet;
+import it.unimi.dsi.fastutil.ints.IntSet;
 import java.io.File;
+import java.util.Map;
+import java.util.concurrent.ConcurrentHashMap;
 import org.junit.Test;
 
 public class R8GMSCoreV10DeployJarVerificationTest extends GMSCoreDeployJarVerificationTest {
@@ -23,32 +29,55 @@
   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, IntSet> methodProcessingIds = new ConcurrentHashMap<>();
     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) ->
+                      assertTrue(
+                          methodProcessingIds
+                              .computeIfAbsent(
+                                  method.toSourceString(), ignore -> new IntOpenHashSet(4))
+                              .add(methodProcessingId.getPrimaryId()));
+              options.proguardMapConsumer =
+                  ToolHelper.consumeString(proguardMap -> this.proguardMap1 = proguardMap);
+            },
             () -> new ArchiveConsumer(app1Zip.toPath(), true));
+
+    File app2Zip = new File(tempFolder, "app2.zip");
     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) -> {
+                    String key = method.toSourceString();
+                    IntSet ids = methodProcessingIds.get(key);
+                    assertNotNull(ids);
+                    assertTrue(ids.remove(methodProcessingId.getPrimaryId()));
+                    if (ids.isEmpty()) {
+                      methodProcessingIds.remove(key);
+                    }
+                  };
+              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);
+    assertTrue(methodProcessingIds.isEmpty());
     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..198ae76 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
@@ -4,10 +4,16 @@
 package com.android.tools.r8.internal;
 
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
 
 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.IntOpenHashSet;
+import it.unimi.dsi.fastutil.ints.IntSet;
+import java.util.Map;
+import java.util.concurrent.ConcurrentHashMap;
 import org.junit.Test;
 
 public class R8GMSCoreV10TreeShakeJarVerificationTest
@@ -19,27 +25,48 @@
   @Test
   public void buildAndTreeShakeFromDeployJar() throws Exception {
     // TODO(tamaskenez): set hasReference = true when we have the noshrink file for V10
+    Map<String, IntSet> methodProcessingIds = new ConcurrentHashMap<>();
     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) ->
+                      assertTrue(
+                          methodProcessingIds
+                              .computeIfAbsent(
+                                  method.toSourceString(), ignore -> new IntOpenHashSet(4))
+                              .add(methodProcessingId.getPrimaryId()));
+              options.proguardMapConsumer =
+                  ToolHelper.consumeString(proguardMap -> this.proguardMap1 = proguardMap);
+            });
     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) -> {
+                    String key = method.toSourceString();
+                    IntSet ids = methodProcessingIds.get(key);
+                    assertNotNull(ids);
+                    assertTrue(ids.remove(methodProcessingId.getPrimaryId()));
+                    if (ids.isEmpty()) {
+                      methodProcessingIds.remove(key);
+                    }
+                  };
+              options.proguardMapConsumer =
+                  ToolHelper.consumeString(proguardMap -> this.proguardMap2 = proguardMap);
+            });
 
     // Verify that the result of the two compilations was the same.
     assertIdenticalApplications(app1, app2);
+    assertTrue(methodProcessingIds.isEmpty());
     assertEquals(proguardMap1, proguardMap2);
   }
 }
diff --git a/src/test/java/com/android/tools/r8/invalid/DuplicateDefinitionsTest.java b/src/test/java/com/android/tools/r8/invalid/DuplicateDefinitionsTest.java
index 3c3aee6..90771b4 100644
--- a/src/test/java/com/android/tools/r8/invalid/DuplicateDefinitionsTest.java
+++ b/src/test/java/com/android/tools/r8/invalid/DuplicateDefinitionsTest.java
@@ -59,11 +59,11 @@
     assertThat(clazz, isPresent());
 
     // There are two direct methods, but only because one is <init>.
-    assertEquals(2, clazz.getDexProgramClass().directMethods().size());
+    assertEquals(2, clazz.getDexProgramClass().getMethodCollection().numberOfDirectMethods());
     assertThat(clazz.method("void", "<init>", ImmutableList.of()), isPresent());
 
     // There is only one virtual method.
-    assertEquals(1, clazz.getDexProgramClass().virtualMethods().size());
+    assertEquals(1, clazz.getDexProgramClass().getMethodCollection().numberOfVirtualMethods());
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/NullabilityTest.java b/src/test/java/com/android/tools/r8/ir/analysis/type/NullabilityTest.java
index 1bee09a..ce6df5c 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/type/NullabilityTest.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/NullabilityTest.java
@@ -32,6 +32,7 @@
 import com.android.tools.r8.ir.optimize.nonnull.NonNullAfterInvoke;
 import com.android.tools.r8.naming.MemberNaming.MethodSignature;
 import com.android.tools.r8.utils.DescriptorUtils;
+import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import com.google.common.collect.ImmutableMap;
@@ -50,7 +51,7 @@
     CodeInspector codeInspector = new CodeInspector(appView.appInfo().app());
     MethodSubject fooSubject = codeInspector.clazz(mainClass.getName()).method(signature);
     IRCode irCode = fooSubject.buildIR();
-    new NonNullTracker(appView).insertAssumeInstructions(irCode);
+    new NonNullTracker(appView).insertAssumeInstructions(irCode, Timing.empty());
     inspector.accept(appView, irCode);
     verifyLastInvoke(irCode, npeCaught);
   }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/NonNullTrackerTest.java b/src/test/java/com/android/tools/r8/ir/optimize/NonNullTrackerTest.java
index 3d28b08..06305cf 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/NonNullTrackerTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/NonNullTrackerTest.java
@@ -20,6 +20,7 @@
 import com.android.tools.r8.ir.optimize.nonnull.NonNullAfterInvoke;
 import com.android.tools.r8.ir.optimize.nonnull.NonNullAfterNullCheck;
 import com.android.tools.r8.naming.MemberNaming.MethodSignature;
+import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import java.util.function.Consumer;
@@ -41,7 +42,7 @@
 
     NonNullTracker nonNullTracker = new NonNullTracker(appView);
 
-    nonNullTracker.insertAssumeInstructions(code);
+    nonNullTracker.insertAssumeInstructions(code, Timing.empty());
     assertTrue(code.isConsistentSSA());
     checkCountOfNonNull(code, expectedNumberOfNonNull);
 
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/R8InliningTest.java b/src/test/java/com/android/tools/r8/ir/optimize/R8InliningTest.java
index 5daa849..d474dad 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/R8InliningTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/R8InliningTest.java
@@ -100,7 +100,7 @@
             .addProgramFiles(getInputFile())
             .setOutput(out, outputMode(parameters.getBackend()))
             .addProguardConfigurationFiles(Paths.get(KEEP_RULES_FILE))
-            .addLibraryFiles(TestBase.runtimeJar(parameters.getBackend()))
+            .addLibraryFiles(ToolHelper.getMostRecentAndroidJar())
             .setDisableMinification(true);
     if (mapFile != null) {
       commandBuilder.setProguardMapOutputPath(mapFile);
@@ -379,6 +379,6 @@
       }
     }
     assertEquals(1, instanceGetCount);
-    assertEquals(0, invokeCount);
+    assertEquals(BooleanUtils.intValue(parameters.isCfRuntime()), invokeCount);
   }
 }
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()
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/NameThenLengthTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/NameThenLengthTest.java
index b7ccc01..add1003 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/NameThenLengthTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/NameThenLengthTest.java
@@ -70,7 +70,7 @@
 
   @Parameterized.Parameters(name = "{0}")
   public static TestParametersCollection data() {
-    return getTestParameters().withAllRuntimes().build();
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
   }
 
   private final TestParameters parameters;
@@ -140,7 +140,7 @@
             .debug()
             .addProgramClasses(MAIN)
             .addOptionsModification(this::configure)
-            .setMinApi(parameters.getRuntime())
+            .setMinApi(parameters.getApiLevel())
             .run(parameters.getRuntime(), MAIN)
             .assertSuccessWithOutput(JAVA_OUTPUT);
     test(result, 2, 0, 2, 0);
@@ -150,11 +150,11 @@
             .release()
             .addProgramClasses(MAIN)
             .addOptionsModification(this::configure)
-            .setMinApi(parameters.getRuntime())
+            .setMinApi(parameters.getApiLevel())
             .run(parameters.getRuntime(), MAIN)
             .assertSuccessWithOutput(JAVA_OUTPUT);
     // TODO(b/125303292): NAME_LENGTH is still not computed at compile time.
-    test(result, 1, 1, 0, 1);
+    test(result, 1, 0, 0, 1);
   }
 
   @Test
@@ -166,7 +166,7 @@
             .addKeepMainRule(MAIN)
             .noMinification()
             .addOptionsModification(this::configure)
-            .setMinApi(parameters.getRuntime())
+            .setMinApi(parameters.getApiLevel())
             .run(parameters.getRuntime(), MAIN)
             .assertSuccessWithOutput(JAVA_OUTPUT);
     // No canonicalization in CF.
diff --git a/src/test/java/com/android/tools/r8/kotlin/ProcessKotlinStdlibTest.java b/src/test/java/com/android/tools/r8/kotlin/ProcessKotlinStdlibTest.java
index 4c45d3c..195b536 100644
--- a/src/test/java/com/android/tools/r8/kotlin/ProcessKotlinStdlibTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/ProcessKotlinStdlibTest.java
@@ -31,12 +31,15 @@
         getTestParameters().withAllRuntimes().build(), KotlinTargetVersion.values());
   }
 
-  private void test(Collection<String> rules) throws Exception {
-    test(rules, null);
+  private void test(Collection<String> rules, boolean expectInvalidFoo) throws Exception {
+    test(rules, expectInvalidFoo, null);
   }
 
   private void test(
-      Collection<String> rules, ThrowableConsumer<R8FullTestBuilder> consumer) throws Exception {
+      Collection<String> rules,
+      boolean expectInvalidDebugInfo,
+      ThrowableConsumer<R8FullTestBuilder> consumer)
+      throws Exception {
     testForR8(parameters.getBackend())
         .addProgramFiles(ToolHelper.getKotlinStdlibJar())
         .addKeepRules(rules)
@@ -49,53 +52,56 @@
 
   @Test
   public void testAsIs() throws Exception {
-    test(ImmutableList.of("-dontshrink", "-dontoptimize", "-dontobfuscate"));
+    test(ImmutableList.of("-dontshrink", "-dontoptimize", "-dontobfuscate"), true);
   }
 
   @Test
   public void testDontShrinkAndDontOptimize() throws Exception {
-    test(ImmutableList.of("-dontshrink", "-dontoptimize"));
+    test(ImmutableList.of("-dontshrink", "-dontoptimize"), true);
   }
 
   @Test
   public void testDontShrinkAndDontOptimizeDifferently() throws Exception {
-     test(
-         ImmutableList.of("-keep,allowobfuscation class **.*Exception*"),
-         tb -> {
-           tb.noTreeShaking();
-           tb.addOptionsModification(o -> {
-             // Randomly choose a couple of optimizations.
-             o.enableClassInlining = false;
-             o.enableLambdaMerging = false;
-             o.enableValuePropagation = false;
-           });
-         });
+    test(
+        ImmutableList.of("-keep,allowobfuscation class **.*Exception*"),
+        true,
+        tb -> {
+          tb.noTreeShaking();
+          tb.addOptionsModification(
+              o -> {
+                // Randomly choose a couple of optimizations.
+                o.enableClassInlining = false;
+                o.enableLambdaMerging = false;
+                o.enableValuePropagation = false;
+              });
+        });
   }
 
   @Test
   public void testDontShrinkAndDontObfuscate() throws Exception {
-    test(ImmutableList.of("-dontshrink", "-dontobfuscate"));
+    test(ImmutableList.of("-dontshrink", "-dontobfuscate"), true);
   }
 
   @Test
   public void testDontShrink() throws Exception {
-    test(ImmutableList.of("-dontshrink"));
+    test(ImmutableList.of("-dontshrink"), true);
   }
 
   @Test
   public void testDontShrinkDifferently() throws Exception {
     test(
         ImmutableList.of("-keep,allowobfuscation class **.*Exception*"),
+        true,
         tb -> tb.noTreeShaking());
   }
 
   @Test
   public void testDontOptimize() throws Exception {
-    test(ImmutableList.of("-dontoptimize"));
+    test(ImmutableList.of("-dontoptimize"), false);
   }
 
   @Test
   public void testDontObfuscate() throws Exception {
-    test(ImmutableList.of("-dontobfuscate"));
+    test(ImmutableList.of("-dontobfuscate"), false);
   }
 }
diff --git a/src/test/java/com/android/tools/r8/kotlin/lambda/KotlinLambdaMergingTest.java b/src/test/java/com/android/tools/r8/kotlin/lambda/KotlinLambdaMergingTest.java
index 6aac431..2498467 100644
--- a/src/test/java/com/android/tools/r8/kotlin/lambda/KotlinLambdaMergingTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/lambda/KotlinLambdaMergingTest.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.kotlin.lambda;
 
+import static com.google.common.base.Predicates.alwaysTrue;
 import static junit.framework.TestCase.assertEquals;
 import static junit.framework.TestCase.assertTrue;
 import static org.junit.Assert.assertFalse;
@@ -213,7 +214,9 @@
           if (check.match(clazz)) {
             // Validate static initializer.
             if (check instanceof Group) {
-              assertEquals(clazz.directMethods().size(), ((Group) check).singletons == 0 ? 1 : 2);
+              assertEquals(
+                  clazz.getMethodCollection().numberOfDirectMethods(),
+                  ((Group) check).singletons == 0 ? 1 : 2);
             }
 
             list.remove(clazz);
@@ -258,8 +261,8 @@
     } else {
       assertTrue(isJStyleLambdaOrGroup(clazz));
       // Taking the number of any virtual method parameters seems to be good enough.
-      assertTrue(clazz.virtualMethods().size() > 0);
-      return clazz.virtualMethods().get(0).method.proto.parameters.size();
+      assertTrue(clazz.getMethodCollection().hasVirtualMethods());
+      return clazz.lookupVirtualMethod(alwaysTrue()).method.proto.parameters.size();
     }
     fail("Failed to get arity for " + clazz.type.descriptor.toString());
     throw new AssertionError();
diff --git a/src/test/java/com/android/tools/r8/kotlin/metadata/KotlinMetadataTestBase.java b/src/test/java/com/android/tools/r8/kotlin/metadata/KotlinMetadataTestBase.java
index f3feb33..87b5d10 100644
--- a/src/test/java/com/android/tools/r8/kotlin/metadata/KotlinMetadataTestBase.java
+++ b/src/test/java/com/android/tools/r8/kotlin/metadata/KotlinMetadataTestBase.java
@@ -3,13 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.kotlin.metadata;
 
-import static org.hamcrest.CoreMatchers.anyOf;
-import static org.hamcrest.CoreMatchers.containsString;
-
 import com.android.tools.r8.ToolHelper.KotlinTargetVersion;
 import com.android.tools.r8.kotlin.AbstractR8KotlinTestBase;
 import com.android.tools.r8.utils.DescriptorUtils;
-import org.hamcrest.Matcher;
 
 abstract class KotlinMetadataTestBase extends AbstractR8KotlinTestBase {
 
@@ -31,8 +27,4 @@
 
   static final String KT_FUNCTION1 = "Lkotlin/Function1;";
   static final String KT_COMPARABLE = "Lkotlin/Comparable;";
-
-  static Matcher<String> expectedInfoMessagesFromKotlinStdLib() {
-    return anyOf(containsString("Invalid descriptor"), containsString("No VersionRequirement"));
-  }
 }
diff --git a/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInTypeArgumentsTest.java b/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInTypeArgumentsTest.java
index 2e3dd21..bed423f 100644
--- a/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInTypeArgumentsTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInTypeArgumentsTest.java
@@ -16,6 +16,7 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.ToolHelper.KotlinTargetVersion;
+import com.android.tools.r8.ToolHelper.ProcessResult;
 import com.android.tools.r8.shaking.ProguardKeepAttributes;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
@@ -148,21 +149,19 @@
             .inspect(this::inspect)
             .writeToZip();
 
-    Path mainJar =
+    // TODO(b/152306391): Reified type-parameters are not flagged correctly.
+    ProcessResult mainResult =
         kotlinc(parameters.getRuntime().asCf(), KOTLINC, targetVersion)
             .addClasspathFiles(libJar)
             .addSourceFiles(getKotlinFileInTest(PKG_PREFIX + "/typeargument_app", "main"))
-            .compile();
-
-    // TODO(b/152306391): Reified type-parameters are not flagged correctly.
-    testForJvm()
-        .addRunClasspathFiles(ToolHelper.getKotlinStdlibJar(), libJar)
-        .addClasspath(mainJar)
-        .run(parameters.getRuntime(), PKG + ".typeargument_app.MainKt")
-        .assertFailureWithErrorThatMatches(
-            containsString(
-                "This function has a reified type parameter and thus can only be inlined at"
-                    + " compilation time, not called directly"));
+            .setOutputPath(temp.newFolder().toPath())
+            .compileRaw();
+    assertEquals(1, mainResult.exitCode);
+    assertThat(
+        mainResult.stderr,
+        containsString(
+            "org.jetbrains.kotlin.codegen.CompilationException: "
+                + "Back-end (JVM) Internal error: wrong bytecode generated"));
   }
 
   private void inspect(CodeInspector inspector) {
diff --git a/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewritePassThroughTest.java b/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewritePassThroughTest.java
index 32a0e6b..4826e1a 100644
--- a/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewritePassThroughTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewritePassThroughTest.java
@@ -50,12 +50,8 @@
         .addProgramFiles(ToolHelper.getKotlinStdlibJar())
         .setMinApi(parameters.getApiLevel())
         .addKeepAllClassesRule()
-        .addKeepRules("-keep class kotlin.Metadata")
         .addKeepAttributes(ProguardKeepAttributes.RUNTIME_VISIBLE_ANNOTATIONS)
         .compile()
-        // TODO(b/155536535): Enable this assert.
-        // .assertAllInfoMessagesMatch(expectedInfoMessagesFromKotlinStdLib())
-        // .assertInfosCount(5)
         .inspect(this::inspect);
   }
 
@@ -75,7 +71,8 @@
       KotlinClassHeader rewrittenHeader = rewrittenMetadata.getHeader();
       assertEquals(originalHeader.getKind(), rewrittenHeader.getKind());
       // TODO(b/154199572): Should we check for meta-data version?
-      assertEquals(originalHeader.getPackageName(), rewrittenHeader.getPackageName());
+      // TODO(b/156290606): Check if we should assert the package names are equal.
+      // assertEquals(originalHeader.getPackageName(), rewrittenHeader.getPackageName());
       // We cannot assert equality of the data since it may be ordered differently. Instead we use
       // the KotlinMetadataWriter.
       String expected = KotlinMetadataWriter.kotlinMetadataToString("", originalMetadata);
diff --git a/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataStripTest.java b/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataStripTest.java
index 94edd94..aa0fcf8 100644
--- a/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataStripTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataStripTest.java
@@ -53,13 +53,11 @@
             .addKeepRules("-keep class kotlin.Metadata")
             // TODO(b/151194540): if this option is settled down, this test is meaningless.
             .addOptionsModification(o -> o.enableKotlinMetadataRewritingForRenamedClasses = false)
-            .allowDiagnosticMessages()
+            .allowDiagnosticWarningMessages()
             .setMinApi(parameters.getApiLevel())
             .compile()
             .assertAllWarningMessagesMatch(
                 equalTo("Resource 'META-INF/MANIFEST.MF' already exists."))
-            .assertAllInfoMessagesMatch(expectedInfoMessagesFromKotlinStdLib())
-            .assertNoErrorMessages()
             .run(parameters.getRuntime(), mainClassName);
     CodeInspector inspector = result.inspector();
     ClassSubject clazz = inspector.clazz(mainClassName);
diff --git a/src/test/java/com/android/tools/r8/naming/EnumMinificationKotlinTest.java b/src/test/java/com/android/tools/r8/naming/EnumMinificationKotlinTest.java
index 7e15524..39cf142 100644
--- a/src/test/java/com/android/tools/r8/naming/EnumMinificationKotlinTest.java
+++ b/src/test/java/com/android/tools/r8/naming/EnumMinificationKotlinTest.java
@@ -5,8 +5,8 @@
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static org.hamcrest.CoreMatchers.equalTo;
+import static org.hamcrest.CoreMatchers.not;
 import static org.hamcrest.MatcherAssert.assertThat;
-import static org.junit.Assert.assertEquals;
 
 import com.android.tools.r8.KotlinTestBase;
 import com.android.tools.r8.TestParameters;
@@ -14,9 +14,6 @@
 import com.android.tools.r8.utils.BooleanUtils;
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
-import com.android.tools.r8.utils.codeinspector.InstructionSubject;
-import com.android.tools.r8.utils.codeinspector.MethodSubject;
-import com.google.common.collect.Streams;
 import java.util.Collection;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -62,12 +59,7 @@
             .run(parameters.getRuntime(), MAIN_CLASS_NAME)
             .inspector();
     ClassSubject enumClass = inspector.clazz(ENUM_CLASS_NAME);
-    assertThat(enumClass, isPresent());
-    assertEquals(minify, enumClass.isRenamed());
-    MethodSubject clinit = enumClass.clinit();
-    assertThat(clinit, isPresent());
-    assertEquals(0,
-        Streams.stream(clinit.iterateInstructions(InstructionSubject::isThrow)).count());
+    // TODO(b/156340144): Check why the ENUM_CLASS_NAME is not present.
+    assertThat(enumClass, not(isPresent()));
   }
-
 }
diff --git a/src/test/java/com/android/tools/r8/shaking/AsterisksTest.java b/src/test/java/com/android/tools/r8/shaking/AsterisksTest.java
index 7261198..b7017e7 100644
--- a/src/test/java/com/android/tools/r8/shaking/AsterisksTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/AsterisksTest.java
@@ -100,7 +100,7 @@
     assertThat(classSubject, isPresent());
     assertThat(classSubject, not(isRenamed()));
     DexClass clazz = classSubject.getDexProgramClass();
-    assertEquals(3, clazz.virtualMethods().size());
+    assertEquals(3, clazz.getMethodCollection().numberOfVirtualMethods());
     for (DexEncodedMethod encodedMethod : clazz.virtualMethods()) {
       assertTrue(encodedMethod.method.name.toString().startsWith("foo"));
       MethodSubject methodSubject =
@@ -141,7 +141,7 @@
     assertThat(classSubject, isPresent());
     assertThat(classSubject, not(isRenamed()));
     DexClass clazz = classSubject.getDexProgramClass();
-    assertEquals(3, clazz.virtualMethods().size());
+    assertEquals(3, clazz.getMethodCollection().numberOfVirtualMethods());
     for (DexEncodedMethod encodedMethod : clazz.virtualMethods()) {
       assertTrue(encodedMethod.method.name.toString().startsWith("foo"));
       MethodSubject methodSubject =
@@ -163,7 +163,7 @@
     assertThat(classSubject, isPresent());
     assertThat(classSubject, not(isRenamed()));
     DexClass clazz = classSubject.getDexProgramClass();
-    assertEquals(3, clazz.virtualMethods().size());
+    assertEquals(3, clazz.getMethodCollection().numberOfVirtualMethods());
     for (DexEncodedMethod encodedMethod : clazz.virtualMethods()) {
       assertTrue(encodedMethod.method.name.toString().startsWith("foo"));
       MethodSubject methodSubject =
diff --git a/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideMarkingTest.java b/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideMarkingTest.java
index 4afc009..df8fdc4 100644
--- a/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideMarkingTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideMarkingTest.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.shaking;
 
+import static com.google.common.base.Predicates.alwaysTrue;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertTrue;
 
@@ -56,8 +57,8 @@
   private void verifySingleVirtualMethodMarkedAsOverridingLibraryMethod(
       AppInfoWithLiveness appInfo, DexType type) {
     DexProgramClass clazz = appInfo.definitionFor(type).asProgramClass();
-    assertEquals(1, clazz.virtualMethods().size());
-    DexEncodedMethod method = clazz.virtualMethods().get(0);
+    assertEquals(1, clazz.getMethodCollection().numberOfVirtualMethods());
+    DexEncodedMethod method = clazz.lookupVirtualMethod(alwaysTrue());
     assertTrue(method.isLibraryMethodOverride().isTrue());
   }
 
diff --git a/src/test/java/com/android/tools/r8/shaking/b134858535/EventPublisherTest.java b/src/test/java/com/android/tools/r8/shaking/b134858535/EventPublisherTest.java
index 29ab0f2..6d0d767 100644
--- a/src/test/java/com/android/tools/r8/shaking/b134858535/EventPublisherTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/b134858535/EventPublisherTest.java
@@ -20,7 +20,6 @@
 
   @Test
   public void testPrivateMethodsInLambdaClass() throws CompilationFailedException {
-    // TODO(b/155534905): Update expectation.
     testForR8(Backend.DEX)
         .addProgramClasses(Main.class, Interface.class)
         .addProgramClassFileData(EventPublisher$bDump.dump())
@@ -28,6 +27,5 @@
         .addKeepMainRule(Main.class)
         .setMinApi(AndroidApiLevel.L)
         .compile();
-    // .assertAllWarningMessagesMatch(containsString("Unrecognized Kotlin lambda"));
   }
 }
diff --git a/src/test/java/com/android/tools/r8/smali/OutlineTest.java b/src/test/java/com/android/tools/r8/smali/OutlineTest.java
index 09c1356..578376e 100644
--- a/src/test/java/com/android/tools/r8/smali/OutlineTest.java
+++ b/src/test/java/com/android/tools/r8/smali/OutlineTest.java
@@ -865,13 +865,12 @@
     CodeInspector inspector = new CodeInspector(processedApplication);
     ClassSubject clazz = inspector.clazz(OutlineOptions.CLASS_NAME);
     assertTrue(clazz.isPresent());
-    assertEquals(3, clazz.getDexProgramClass().directMethods().size());
+    assertEquals(3, clazz.getDexProgramClass().getMethodCollection().numberOfDirectMethods());
     // Collect the return types of the putlines for the body of method1 and method2.
     List<DexType> r = new ArrayList<>();
-    for (int i = 0; i < clazz.getDexProgramClass().directMethods().size(); i++) {
-      if (clazz.getDexProgramClass().directMethods().get(i).getCode().asDexCode().instructions[0]
-          instanceof InvokeVirtual) {
-        r.add(clazz.getDexProgramClass().directMethods().get(i).method.proto.returnType);
+    for (DexEncodedMethod directMethod : clazz.getDexProgramClass().directMethods()) {
+      if (directMethod.getCode().asDexCode().instructions[0] instanceof InvokeVirtual) {
+        r.add(directMethod.method.proto.returnType);
       }
     }
     assert r.size() == 2;
diff --git a/src/test/java/com/android/tools/r8/testing/ToolHelperTest.java b/src/test/java/com/android/tools/r8/testing/ToolHelperTest.java
new file mode 100644
index 0000000..b0e1ab2
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/testing/ToolHelperTest.java
@@ -0,0 +1,39 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.testing;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import java.nio.file.Path;
+import org.junit.Test;
+
+public class ToolHelperTest extends TestBase {
+
+  private void checkExpectedAndroidJar(Path androidJarPath, AndroidApiLevel apiLevel) {
+    assertEquals("android.jar", androidJarPath.getFileName().toString());
+    assertEquals(
+        "lib-v" + apiLevel.getLevel(),
+        androidJarPath.getName(androidJarPath.getNameCount() - 2).toString());
+  }
+
+  @Test
+  public void testGetFirstSupportedAndroidJar() throws Exception {
+    // Check some API levels for which the repo does not have android.jar.
+    checkExpectedAndroidJar(
+        ToolHelper.getFirstSupportedAndroidJar(AndroidApiLevel.B), AndroidApiLevel.I);
+    checkExpectedAndroidJar(
+        ToolHelper.getFirstSupportedAndroidJar(AndroidApiLevel.K_WATCH), AndroidApiLevel.L);
+    // All android.jar's for API level L are present.
+    for (AndroidApiLevel androidApiLevel : AndroidApiLevel.values()) {
+      if (androidApiLevel.isGreaterThanOrEqualTo(AndroidApiLevel.L)) {
+        checkExpectedAndroidJar(
+            ToolHelper.getFirstSupportedAndroidJar(androidApiLevel), androidApiLevel);
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/CodeInspector.java b/src/test/java/com/android/tools/r8/utils/codeinspector/CodeInspector.java
index 1f25605..39f7c44 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/CodeInspector.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/CodeInspector.java
@@ -193,7 +193,7 @@
   }
 
   static <S, T extends Subject> void forAll(
-      List<? extends S> items,
+      Iterable<? extends S> items,
       BiFunction<S, FoundClassSubject, ? extends T> constructor,
       FoundClassSubject clazz,
       Consumer<T> consumer) {
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java
index df3f287..7c0683f 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java
@@ -17,6 +17,7 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.kotlin.KotlinClassMetadataReader;
 import com.android.tools.r8.naming.ClassNamingForNameMapper;
 import com.android.tools.r8.naming.MemberNaming;
 import com.android.tools.r8.naming.MemberNaming.FieldSignature;
@@ -101,7 +102,7 @@
         : new FoundMethodSubject(codeInspector, encoded, this);
   }
 
-  private DexEncodedMethod findMethod(List<DexEncodedMethod> methods, DexMethod dexMethod) {
+  private DexEncodedMethod findMethod(Iterable<DexEncodedMethod> methods, DexMethod dexMethod) {
     for (DexEncodedMethod method : methods) {
       if (method.method.equals(dexMethod)) {
         return method;
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/KotlinClassMetadataReader.java b/src/test/java/com/android/tools/r8/utils/codeinspector/KotlinClassMetadataReader.java
deleted file mode 100644
index 73972f4..0000000
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/KotlinClassMetadataReader.java
+++ /dev/null
@@ -1,90 +0,0 @@
-// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.utils.codeinspector;
-
-import com.android.tools.r8.graph.DexAnnotationElement;
-import com.android.tools.r8.graph.DexEncodedAnnotation;
-import com.android.tools.r8.graph.DexString;
-import com.android.tools.r8.graph.DexValue;
-import com.android.tools.r8.graph.DexValue.DexValueArray;
-import com.android.tools.r8.kotlin.Kotlin;
-import java.util.IdentityHashMap;
-import java.util.Map;
-import kotlinx.metadata.jvm.KotlinClassHeader;
-import kotlinx.metadata.jvm.KotlinClassMetadata;
-
-// TODO(b/145824437): This is a dup of the same class in source to avoid the error while building
-//  keep rules for r8lib. Should be able to avoid this redundancy at build configuration level or
-//  change -printusage to apply mappings regarding relocated deps.
-class KotlinClassMetadataReader {
-  static KotlinClassMetadata toKotlinClassMetadata(
-      Kotlin kotlin, DexEncodedAnnotation metadataAnnotation) {
-    Map<DexString, DexAnnotationElement> elementMap = new IdentityHashMap<>();
-    for (DexAnnotationElement element : metadataAnnotation.elements) {
-      elementMap.put(element.name, element);
-    }
-
-    DexAnnotationElement kind = elementMap.get(kotlin.metadata.kind);
-    if (kind == null) {
-      throw new MetadataError("element 'k' is missing.");
-    }
-    Integer k = (Integer) kind.value.getBoxedValue();
-    DexAnnotationElement metadataVersion = elementMap.get(kotlin.metadata.metadataVersion);
-    int[] mv = metadataVersion == null ? null : getUnboxedIntArray(metadataVersion.value, "mv");
-    DexAnnotationElement bytecodeVersion = elementMap.get(kotlin.metadata.bytecodeVersion);
-    int[] bv = bytecodeVersion == null ? null : getUnboxedIntArray(bytecodeVersion.value, "bv");
-    DexAnnotationElement data1 = elementMap.get(kotlin.metadata.data1);
-    String[] d1 = data1 == null ? null : getUnboxedStringArray(data1.value, "d1");
-    DexAnnotationElement data2 = elementMap.get(kotlin.metadata.data2);
-    String[] d2 = data2 == null ? null : getUnboxedStringArray(data2.value, "d2");
-    DexAnnotationElement extraString = elementMap.get(kotlin.metadata.extraString);
-    String xs = extraString == null ? null : getUnboxedString(extraString.value, "xs");
-    DexAnnotationElement packageName = elementMap.get(kotlin.metadata.packageName);
-    String pn = packageName == null ? null : getUnboxedString(packageName.value, "pn");
-    DexAnnotationElement extraInt = elementMap.get(kotlin.metadata.extraInt);
-    Integer xi = extraInt == null ? null : (Integer) extraInt.value.getBoxedValue();
-
-    KotlinClassHeader header = new KotlinClassHeader(k, mv, bv, d1, d2, xs, pn, xi);
-    return KotlinClassMetadata.read(header);
-  }
-
-  private static int[] getUnboxedIntArray(DexValue v, String elementName) {
-    if (!v.isDexValueArray()) {
-      throw new MetadataError("invalid '" + elementName + "' value: " + v.toSourceString());
-    }
-    DexValueArray intArrayValue = v.asDexValueArray();
-    DexValue[] values = intArrayValue.getValues();
-    int[] result = new int [values.length];
-    for (int i = 0; i < values.length; i++) {
-      result[i] = (Integer) values[i].getBoxedValue();
-    }
-    return result;
-  }
-
-  private static String[] getUnboxedStringArray(DexValue v, String elementName) {
-    if (!v.isDexValueArray()) {
-      throw new MetadataError("invalid '" + elementName + "' value: " + v.toSourceString());
-    }
-    DexValueArray stringArrayValue = v.asDexValueArray();
-    DexValue[] values = stringArrayValue.getValues();
-    String[] result = new String [values.length];
-    for (int i = 0; i < values.length; i++) {
-      result[i] = getUnboxedString(values[i], elementName + "[" + i + "]");
-    }
-    return result;
-  }
-
-  private static String getUnboxedString(DexValue v, String elementName) {
-    if (!v.isDexValueString()) {
-      throw new MetadataError("invalid '" + elementName + "' value: " + v.toSourceString());
-    }
-    return v.asDexValueString().getValue().toString();
-  }
-
-  private static class MetadataError extends RuntimeException {
-    MetadataError(String cause) {
-      super(cause);
-    }
-  }
-}
diff --git a/third_party/kotlin-compiler-1.3.41.tar.gz.sha1 b/third_party/kotlin-compiler-1.3.41.tar.gz.sha1
deleted file mode 100644
index 0e0fc13..0000000
--- a/third_party/kotlin-compiler-1.3.41.tar.gz.sha1
+++ /dev/null
@@ -1 +0,0 @@
-af4830da8231a4ac4e900810bd3a100e7244b7d5
\ No newline at end of file
diff --git a/third_party/kotlin.tar.gz.sha1 b/third_party/kotlin.tar.gz.sha1
deleted file mode 100644
index df6fec5..0000000
--- a/third_party/kotlin.tar.gz.sha1
+++ /dev/null
@@ -1 +0,0 @@
-2675c63602dda3117651858e6a7cd63e432a8a1c
\ No newline at end of file
diff --git a/third_party/kotlin/kotlin-compiler-1.3.11.tar.gz.sha1 b/third_party/kotlin/kotlin-compiler-1.3.11.tar.gz.sha1
new file mode 100644
index 0000000..05e8466
--- /dev/null
+++ b/third_party/kotlin/kotlin-compiler-1.3.11.tar.gz.sha1
@@ -0,0 +1 @@
+b3ce5c6ba25ebbbbf62a49be56aad845eabae860
\ No newline at end of file
diff --git a/third_party/kotlin/kotlin-compiler-1.3.41.tar.gz.sha1 b/third_party/kotlin/kotlin-compiler-1.3.41.tar.gz.sha1
new file mode 100644
index 0000000..e9de3b3
--- /dev/null
+++ b/third_party/kotlin/kotlin-compiler-1.3.41.tar.gz.sha1
@@ -0,0 +1 @@
+8d2ddeeaaf4366a419627a31ef3276a6f96afe40
\ No newline at end of file
diff --git a/third_party/kotlin/kotlin-compiler-1.3.72.tar.gz.sha1 b/third_party/kotlin/kotlin-compiler-1.3.72.tar.gz.sha1
new file mode 100644
index 0000000..4bccd06
--- /dev/null
+++ b/third_party/kotlin/kotlin-compiler-1.3.72.tar.gz.sha1
@@ -0,0 +1 @@
+f055b7d8a394776586841cbd17b4f93535473f3b
\ No newline at end of file
diff --git a/tools/r8_release.py b/tools/r8_release.py
index ba87676..2f3c4fc 100755
--- a/tools/r8_release.py
+++ b/tools/r8_release.py
@@ -274,7 +274,8 @@
 
 
 def g4_open(file):
-  subprocess.check_call('g4 open %s' % file, shell=True)
+  if not os.access(file, os.W_OK):
+    subprocess.check_call('g4 open %s' % file, shell=True)
 
 
 def g4_change(version):
@@ -306,7 +307,7 @@
   assert args.version
   # Check if an existing client exists.
   if not args.use_existing_work_branch:
-    check_no_google3_client(args, 'update-r8')
+    check_no_google3_client(args, args.p4_client)
 
   def release_google3(options):
     print "Releasing for Google 3"
@@ -314,7 +315,7 @@
       return 'DryRun: omitting g3 release for %s' % options.version
 
     google3_base = subprocess.check_output(
-        ['p4', 'g4d', '-f', 'update-r8']).rstrip()
+        ['p4', 'g4d', '-f', args.p4_client]).rstrip()
     third_party_r8 = os.path.join(google3_base, 'third_party', 'java', 'r8')
     today = datetime.date.today()
     with utils.ChangedWorkingDirectory(third_party_r8):
@@ -700,6 +701,10 @@
                       default=False,
                       action='store_true',
                       help='Release for google 3')
+  result.add_argument('--p4-client',
+                      default='update-r8',
+                      metavar=('<client name>'),
+                      help='P4 client name for google 3')
   result.add_argument('--use-existing-work-branch', '--use_existing_work_branch',
                       default=False,
                       action='store_true',