diff --git a/build.gradle b/build.gradle
index 99c4865..58b0aaf 100644
--- a/build.gradle
+++ b/build.gradle
@@ -2,11 +2,12 @@
 // 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.
 import org.gradle.internal.os.OperatingSystem
-import utils.Utils;
+import utils.Utils
 
 apply plugin: 'java'
 apply plugin: 'idea'
 apply plugin: 'jacoco'
+apply plugin: 'com.google.protobuf'
 
 apply from: 'copyAdditionalJctfCommonFiles.gradle'
 
@@ -14,6 +15,15 @@
     mavenCentral()
 }
 
+buildscript {
+    repositories {
+        mavenCentral()
+    }
+    dependencies {
+        classpath 'com.google.protobuf:protobuf-gradle-plugin:0.8.1'
+    }
+}
+
 // Custom source set for example tests and generated tests.
 sourceSets {
     test {
@@ -38,7 +48,12 @@
     }
     examples {
         java {
-            srcDirs = ['src/test/examples']
+            srcDirs = ['src/test/examples', 'build/generated/source/proto/examples/javalite/' ]
+        }
+        proto {
+            srcDirs = [
+                    'src/test/examples',
+            ]
         }
         output.resourcesDir = 'build/classes/examples'
     }
@@ -97,6 +112,31 @@
     jctfTestsCompile 'junit:junit:4.12'
     jctfTestsCompile sourceSets.jctfCommon.output
     examplesAndroidOCompile group: 'org.ow2.asm', name: 'asm', version: '5.1'
+    examplesCompile 'com.google.protobuf:protobuf-lite:3.0.0'
+    examplesRuntime 'com.google.protobuf:protobuf-lite:3.0.0'
+}
+
+protobuf {
+    protoc {
+        // Download from repositories
+        artifact = 'com.google.protobuf:protoc:3.0.0'
+    }
+    plugins {
+        javalite {
+            artifact = 'com.google.protobuf:protoc-gen-javalite:3.0.0'
+        }
+    }
+    generateProtoTasks {
+        all().each { task ->
+            task.builtins {
+                // Disable the java code generator, as we want javalite only.
+                remove java
+            }
+            task.plugins {
+                javalite {}
+            }
+        }
+    }
 }
 
 def osString = OperatingSystem.current().isLinux() ? "linux" :
@@ -464,16 +504,26 @@
 task buildExampleJars {
     dependsOn downloadProguard
     def examplesDir = file("src/test/examples")
+    def protoSourceDir = file("build/generated/source/proto/examples/javalite")
     def proguardScript
     if (OperatingSystem.current().isWindows()) {
         proguardScript = "third_party/proguard/proguard5.2.1/bin/proguard.bat"
     } else {
         proguardScript = "third_party/proguard/proguard5.2.1/bin/proguard.sh"
     }
-    task "compile_examples"(type: JavaCompile) {
-        source = fileTree(dir: examplesDir, include: '**/*.java')
+    task extractExamplesRuntime(type: Sync) {
+        dependsOn configurations.examplesRuntime
+        from configurations.examplesRuntime.collect { zipTree(it) }
+        include "**/*.class"
+        includeEmptyDirs false
+        into "$buildDir/runtime/examples/"
+    }
+
+    task "compile_examples"(type: JavaCompile, dependsOn: "generateExamplesProto") {
+        source examplesDir, protoSourceDir
+        include "**/*.java"
         destinationDir = file("build/test/examples/classes")
-        classpath = sourceSets.main.compileClasspath
+        classpath = sourceSets.examples.compileClasspath
         sourceCompatibility = JavaVersion.VERSION_1_7
         targetCompatibility = JavaVersion.VERSION_1_7
         options.compilerArgs += ["-Xlint:-options"]
@@ -483,6 +533,15 @@
         def exampleOutputDir = file("build/test/examples");
         def jarName = "${name}.jar"
         dependsOn "jar_example_${name}"
+        dependsOn "extractExamplesRuntime"
+        def runtimeDependencies = copySpec { }
+        if (!fileTree(dir: dir, include: '**/*.proto').empty) {
+            // If we have any proto use, we have to include those classes and the runtime.
+            runtimeDependencies = copySpec {
+                from "$buildDir/runtime/examples/"
+                include "com/google/protobuf/**/*.class"
+            }
+        }
         // The "throwing" test verifies debugging/stack info on the post-proguarded output.
         def proguardConfigPath = "${dir}/proguard.cfg"
         if (new File(proguardConfigPath).exists()) {
@@ -490,7 +549,9 @@
                 archiveName = "${name}_pre_proguard.jar"
                 destinationDir = exampleOutputDir
                 from "build/test/examples/classes"
-                include "**/" + name + "/**/*.class"
+                include name + "/**/*.class"
+                with runtimeDependencies
+                includeEmptyDirs false
             }
             def jarPath = files(tasks.getByPath("pre_proguard_example_${name}")).files.first();
             def proguardJarPath = "${exampleOutputDir}/${jarName}"
@@ -519,7 +580,9 @@
                 archiveName = jarName
                 destinationDir = exampleOutputDir
                 from "build/test/examples/classes"
-                include "**/" + name + "/**/*.class"
+                include name + "/**/*.class"
+                with runtimeDependencies
+                includeEmptyDirs false
             }
         }
     }
diff --git a/src/main/java/com/android/tools/r8/compatdx/CompatDx.java b/src/main/java/com/android/tools/r8/compatdx/CompatDx.java
index a547d12..b77493f 100644
--- a/src/main/java/com/android/tools/r8/compatdx/CompatDx.java
+++ b/src/main/java/com/android/tools/r8/compatdx/CompatDx.java
@@ -294,9 +294,12 @@
       multiDex = options.has(spec.multiDex);
       mainDexList = options.valueOf(spec.mainDexList);
       minimalMainDex = options.has(spec.minimalMainDex);
-      minApiLevel = options.has(spec.minApiLevel)
-              ? options.valueOf(spec.minApiLevel)
-              : Constants.DEFAULT_ANDROID_API;
+      if (options.has(spec.minApiLevel)) {
+        List<Integer> allMinApiLevels = options.valuesOf(spec.minApiLevel);
+        minApiLevel = allMinApiLevels.get(allMinApiLevels.size() - 1);
+      } else {
+        minApiLevel = Constants.DEFAULT_ANDROID_API;
+      }
       inputList = options.valueOf(spec.inputList);
       inputs = ImmutableList.copyOf(options.valuesOf(spec.inputs));
       maxIndexNumber = options.valueOf(spec.maxIndexNumber);
diff --git a/src/main/java/com/android/tools/r8/graph/Code.java b/src/main/java/com/android/tools/r8/graph/Code.java
index dca5e02..84d6d5d 100644
--- a/src/main/java/com/android/tools/r8/graph/Code.java
+++ b/src/main/java/com/android/tools/r8/graph/Code.java
@@ -34,15 +34,15 @@
   }
 
   public DexCode asDexCode() {
-    throw new Unreachable();
+    throw new Unreachable(getClass().getCanonicalName() + ".asDexCode()");
   }
 
   public JarCode asJarCode() {
-    throw new Unreachable();
+    throw new Unreachable(getClass().getCanonicalName() + ".asJarCode()");
   }
 
   public OutlineCode asOutlineCode() {
-    throw new Unreachable();
+    throw new Unreachable(getClass().getCanonicalName() + ".asOutlineCode()");
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/graph/DexAnnotation.java b/src/main/java/com/android/tools/r8/graph/DexAnnotation.java
index 55aa9868..1afd77e 100644
--- a/src/main/java/com/android/tools/r8/graph/DexAnnotation.java
+++ b/src/main/java/com/android/tools/r8/graph/DexAnnotation.java
@@ -16,19 +16,6 @@
 import java.util.List;
 
 public class DexAnnotation extends DexItem {
-  // Dex system annotations.
-  // See https://source.android.com/devices/tech/dalvik/dex-format.html#system-annotation
-  private static final String ANNOTATION_DEFAULT_DESCRIPTOR =
-      "Ldalvik/annotation/AnnotationDefault;";
-  private static final String ENCLOSING_CLASS_DESCRIPTOR = "Ldalvik/annotation/EnclosingClass;";
-  private static final String ENCLOSING_METHOD_DESCRIPTOR = "Ldalvik/annotation/EnclosingMethod;";
-  private static final String INNER_CLASS_DESCRIPTOR = "Ldalvik/annotation/InnerClass;";
-  private static final String MEMBER_CLASSES_DESCRIPTOR = "Ldalvik/annotation/MemberClasses;";
-  private static final String METHOD_PARAMETERS_DESCRIPTOR = "Ldalvik/annotation/MethodParameters;";
-  private static final String SIGNATURE_DESCRIPTOR = "Ldalvik/annotation/Signature;";
-  private static final String SOURCE_DEBUG_EXTENSION = "Ldalvik/annotation/SourceDebugExtension;";
-  private static final String THROWS_DESCRIPTOR = "Ldalvik/annotation/Throws;";
-
   public static final int VISIBILITY_BUILD = 0x00;
   public static final int VISIBILITY_RUNTIME = 0x01;
   public static final int VISIBILITY_SYSTEM = 0x02;
@@ -74,37 +61,36 @@
 
   public static DexAnnotation createEnclosingClassAnnotation(DexType enclosingClass,
       DexItemFactory factory) {
-    return createSystemValueAnnotation(ENCLOSING_CLASS_DESCRIPTOR, factory,
+    return createSystemValueAnnotation(factory.annotationEnclosingClass, factory,
         new DexValueType(enclosingClass));
   }
 
   public static DexAnnotation createEnclosingMethodAnnotation(DexMethod enclosingMethod,
       DexItemFactory factory) {
-    return createSystemValueAnnotation(ENCLOSING_METHOD_DESCRIPTOR, factory,
+    return createSystemValueAnnotation(factory.annotationEnclosingMethod, factory,
         new DexValueMethod(enclosingMethod));
   }
 
-  public static boolean isEnclosingClassAnnotation(DexAnnotation annotation) {
-    return annotation.annotation.type.toDescriptorString().equals(ENCLOSING_CLASS_DESCRIPTOR);
+  public static boolean isEnclosingClassAnnotation(DexAnnotation annotation,
+      DexItemFactory factory) {
+    return annotation.annotation.type == factory.annotationEnclosingClass;
   }
 
-  public static boolean isEnclosingMethodAnnotation(DexAnnotation annotation) {
-    return annotation.annotation.type.toDescriptorString().equals(ENCLOSING_METHOD_DESCRIPTOR);
+  public static boolean isEnclosingMethodAnnotation(DexAnnotation annotation,
+      DexItemFactory factory) {
+    return annotation.annotation.type == factory.annotationEnclosingMethod;
   }
 
-  public static boolean isEnclosingAnnotation(DexAnnotation annotation) {
-    return isEnclosingClassAnnotation(annotation) || isEnclosingMethodAnnotation(annotation);
-  }
-
-  public static boolean isInnerClassesAnnotation(DexAnnotation annotation) {
-    return annotation.annotation.type.toDescriptorString().equals(MEMBER_CLASSES_DESCRIPTOR)
-        || annotation.annotation.type.toDescriptorString().equals(INNER_CLASS_DESCRIPTOR);
+  public static boolean isInnerClassesAnnotation(DexAnnotation annotation,
+      DexItemFactory factory) {
+    return annotation.annotation.type == factory.annotationMemberClasses
+        || annotation.annotation.type == factory.annotationInnerClass;
   }
 
   public static DexAnnotation createInnerClassAnnotation(String clazz, int access,
       DexItemFactory factory) {
     return new DexAnnotation(VISIBILITY_SYSTEM,
-        new DexEncodedAnnotation(factory.createType(INNER_CLASS_DESCRIPTOR),
+        new DexEncodedAnnotation(factory.annotationInnerClass,
             new DexAnnotationElement[]{
                 new DexAnnotationElement(
                     factory.createString("accessFlags"),
@@ -123,14 +109,14 @@
     for (int i = 0; i < classes.size(); i++) {
       values[i] = new DexValueType(classes.get(i));
     }
-    return createSystemValueAnnotation(MEMBER_CLASSES_DESCRIPTOR, factory,
+    return createSystemValueAnnotation(factory.annotationMemberClasses, factory,
         new DexValueArray(values));
   }
 
   public static DexAnnotation createSourceDebugExtensionAnnotation(DexValue value,
       DexItemFactory factory) {
     return new DexAnnotation(VISIBILITY_SYSTEM,
-        new DexEncodedAnnotation(factory.createType(SOURCE_DEBUG_EXTENSION),
+        new DexEncodedAnnotation(factory.annotationSourceDebugExtension,
             new DexAnnotationElement[] {
               new DexAnnotationElement(factory.createString("value"), value)
             }));
@@ -140,7 +126,7 @@
       DexValue[] accessFlags, DexItemFactory factory) {
     assert names.length == accessFlags.length;
     return new DexAnnotation(VISIBILITY_SYSTEM,
-        new DexEncodedAnnotation(factory.createType(METHOD_PARAMETERS_DESCRIPTOR),
+        new DexEncodedAnnotation(factory.annotationMethodParameters,
             new DexAnnotationElement[]{
                 new DexAnnotationElement(
                     factory.createString("names"),
@@ -153,7 +139,7 @@
 
   public static DexAnnotation createAnnotationDefaultAnnotation(DexType type,
       List<DexAnnotationElement> defaults, DexItemFactory factory) {
-    return createSystemValueAnnotation(ANNOTATION_DEFAULT_DESCRIPTOR, factory,
+    return createSystemValueAnnotation(factory.annotationDefault, factory,
         new DexValueAnnotation(
             new DexEncodedAnnotation(type,
                 defaults.toArray(new DexAnnotationElement[defaults.size()])))
@@ -161,34 +147,38 @@
   }
 
   public static DexAnnotation createSignatureAnnotation(String signature, DexItemFactory factory) {
-    return createSystemValueAnnotation(SIGNATURE_DESCRIPTOR, factory,
+    return createSystemValueAnnotation(factory.annotationSignature, factory,
         compressSignature(signature, factory));
   }
 
   public static DexAnnotation createThrowsAnnotation(DexValue[] exceptions,
       DexItemFactory factory) {
-    return createSystemValueAnnotation(THROWS_DESCRIPTOR, factory, new DexValueArray(exceptions));
+    return createSystemValueAnnotation(factory.annotationThrows, factory,
+        new DexValueArray(exceptions));
   }
 
-  private static DexAnnotation createSystemValueAnnotation(String desc, DexItemFactory factory,
+  private static DexAnnotation createSystemValueAnnotation(DexType type, DexItemFactory factory,
       DexValue value) {
     return new DexAnnotation(VISIBILITY_SYSTEM,
-        new DexEncodedAnnotation(factory.createType(desc), new DexAnnotationElement[] {
+        new DexEncodedAnnotation(type, new DexAnnotationElement[]{
             new DexAnnotationElement(factory.createString("value"), value)
         }));
   }
 
-  public static boolean isThrowingAnnotation(DexAnnotation annotation) {
-    return annotation.annotation.type.toDescriptorString().equals(THROWS_DESCRIPTOR);
+  public static boolean isThrowingAnnotation(DexAnnotation annotation,
+      DexItemFactory factory) {
+    return annotation.annotation.type == factory.annotationThrows;
   }
 
-  public static boolean isSignatureAnnotation(DexAnnotation annotation) {
-    return annotation.annotation.type.toDescriptorString().equals(SIGNATURE_DESCRIPTOR);
+  public static boolean isSignatureAnnotation(DexAnnotation annotation,
+      DexItemFactory factory) {
+    return annotation.annotation.type == factory.annotationSignature;
   }
 
 
-  public static boolean isSourceDebugExtension(DexAnnotation annotation) {
-    return annotation.annotation.type.toDescriptorString().equals(SOURCE_DEBUG_EXTENSION);
+  public static boolean isSourceDebugExtension(DexAnnotation annotation,
+      DexItemFactory factory) {
+    return annotation.annotation.type == factory.annotationSourceDebugExtension;
   }
 
   /**
diff --git a/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java b/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java
index 04e94d7..e91e1f0 100644
--- a/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java
+++ b/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java
@@ -68,6 +68,15 @@
     sorted = hashCode();
   }
 
+  public DexAnnotation getFirstMatching(DexType type) {
+    for (DexAnnotation annotation : annotations) {
+      if (annotation.annotation.type == type) {
+        return annotation;
+      }
+    }
+    return null;
+  }
+
   private int sortedHashCode() {
     int hashCode = hashCode();
     return hashCode == UNSORTED ? 1 : hashCode;
diff --git a/src/main/java/com/android/tools/r8/graph/DexApplication.java b/src/main/java/com/android/tools/r8/graph/DexApplication.java
index ca702fe..d84dd8c 100644
--- a/src/main/java/com/android/tools/r8/graph/DexApplication.java
+++ b/src/main/java/com/android/tools/r8/graph/DexApplication.java
@@ -25,7 +25,6 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
-import java.util.Hashtable;
 import java.util.IdentityHashMap;
 import java.util.List;
 import java.util.Map;
@@ -87,7 +86,8 @@
   }
 
   public List<DexProgramClass> classes() {
-    List<DexProgramClass> classes = programClasses.collectLoadedClasses();
+    programClasses.forceLoad(type -> true);
+    List<DexProgramClass> classes = programClasses.getAllClasses();
     assert reorderClasses(classes);
     return classes;
   }
@@ -110,16 +110,16 @@
 
     // program classes are supposed to be loaded, but force-loading them is no-op.
     programClasses.forceLoad(type -> true);
-    programClasses.collectLoadedClasses().forEach(clazz -> loaded.put(clazz.type, clazz));
+    programClasses.getAllClasses().forEach(clazz -> loaded.put(clazz.type, clazz));
 
     if (classpathClasses != null) {
       classpathClasses.forceLoad(type -> !loaded.containsKey(type));
-      classpathClasses.collectLoadedClasses().forEach(clazz -> loaded.put(clazz.type, clazz));
+      classpathClasses.getAllClasses().forEach(clazz -> loaded.putIfAbsent(clazz.type, clazz));
     }
 
     if (libraryClasses != null) {
       libraryClasses.forceLoad(type -> !loaded.containsKey(type));
-      libraryClasses.collectLoadedClasses().forEach(clazz -> loaded.put(clazz.type, clazz));
+      libraryClasses.getAllClasses().forEach(clazz -> loaded.putIfAbsent(clazz.type, clazz));
     }
 
     return loaded;
@@ -192,7 +192,7 @@
    * <p>If no directory is provided everything is written to System.out.
    */
   public void disassemble(Path outputDir, InternalOptions options) {
-    for (DexProgramClass clazz : programClasses.collectLoadedClasses()) {
+    for (DexProgramClass clazz : programClasses.getAllClasses()) {
       for (DexEncodedMethod method : clazz.virtualMethods()) {
         if (options.methodMatchesFilter(method)) {
           disassemble(method, getProguardMap(), outputDir);
@@ -246,7 +246,7 @@
    * Write smali source for the application code on the provided PrintStream.
    */
   public void smali(InternalOptions options, PrintStream ps) {
-    List<DexProgramClass> classes = programClasses.collectLoadedClasses();
+    List<DexProgramClass> classes = programClasses.getAllClasses();
     classes.sort(Comparator.comparing(DexProgramClass::toSourceString));
     boolean firstClass = true;
     for (DexClass clazz : classes) {
@@ -322,7 +322,7 @@
     }
 
     public Builder(DexApplication application) {
-      programClasses = application.programClasses.collectLoadedClasses();
+      programClasses = application.programClasses.getAllClasses();
       classpathClasses = application.classpathClasses;
       libraryClasses = application.libraryClasses;
       proguardMap = application.proguardMap;
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 023cfb0..5b1b0f3 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -10,6 +10,7 @@
 
 import com.google.common.base.MoreObjects;
 
+import java.util.Arrays;
 import java.util.function.Consumer;
 
 public abstract class DexClass extends DexItem {
@@ -83,6 +84,17 @@
     }
   }
 
+  public DexEncodedMethod[] allMethodsSorted() {
+    int vLen = virtualMethods().length;
+    int dLen = directMethods().length;
+    DexEncodedMethod[] result = new DexEncodedMethod[vLen+dLen];
+    System.arraycopy(virtualMethods(), 0, result, 0, vLen);
+    System.arraycopy(directMethods(), 0, result, vLen, dLen);
+    Arrays.sort(result,
+        (DexEncodedMethod a, DexEncodedMethod b) -> a.method.slowCompareTo(b.method));
+    return result;
+  }
+
   public DexEncodedField[] staticFields() {
     return MoreObjects.firstNonNull(staticFields, NO_FIELDS);
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexClasspathClass.java b/src/main/java/com/android/tools/r8/graph/DexClasspathClass.java
index dd5efbb..036b8bc 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClasspathClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClasspathClass.java
@@ -7,8 +7,9 @@
 import com.android.tools.r8.dex.IndexedItemCollection;
 import com.android.tools.r8.dex.MixedSectionCollection;
 import com.android.tools.r8.errors.Unreachable;
+import java.util.function.Supplier;
 
-public class DexClasspathClass extends DexClass {
+public class DexClasspathClass extends DexClass implements Supplier<DexClasspathClass> {
 
   public DexClasspathClass(DexType type, Resource.Kind origin, DexAccessFlags accessFlags,
       DexType superType, DexTypeList interfaces, DexString sourceFile, DexAnnotationSet annotations,
@@ -43,4 +44,9 @@
   public DexClasspathClass asClasspathClass() {
     return this;
   }
+
+  @Override
+  public DexClasspathClass get() {
+    return this;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index 5dff4b4..36d732d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -129,8 +129,8 @@
   public DexType annotationType = createType(annotationDescriptor);
   public DexType throwableType = createType(throwableDescriptor);
 
-  public DexType stringBuilderType = createType(createString("Ljava/lang/StringBuilder;"));
-  public DexType stringBufferType = createType(createString("Ljava/lang/StringBuffer;"));
+  public DexType stringBuilderType = createType("Ljava/lang/StringBuilder;");
+  public DexType stringBufferType = createType("Ljava/lang/StringBuffer;");
 
   public StringBuildingMethods stringBuilderMethods = new StringBuildingMethods(stringBuilderType);
   public StringBuildingMethods stringBufferMethods = new StringBuildingMethods(stringBufferType);
@@ -140,6 +140,21 @@
   public ThrowableMethods throwableMethods = new ThrowableMethods();
   public ClassMethods classMethods = new ClassMethods();
 
+  // Dex system annotations.
+  // See https://source.android.com/devices/tech/dalvik/dex-format.html#system-annotation
+  public final DexType annotationDefault = createType("Ldalvik/annotation/AnnotationDefault;");
+  public final DexType annotationEnclosingClass = createType("Ldalvik/annotation/EnclosingClass;");
+  public final DexType annotationEnclosingMethod = createType(
+      "Ldalvik/annotation/EnclosingMethod;");
+  public final DexType annotationInnerClass = createType("Ldalvik/annotation/InnerClass;");
+  public final DexType annotationMemberClasses = createType("Ldalvik/annotation/MemberClasses;");
+  public final DexType annotationMethodParameters = createType(
+      "Ldalvik/annotation/MethodParameters;");
+  public final DexType annotationSignature = createType("Ldalvik/annotation/Signature;");
+  public final DexType annotationSourceDebugExtension = createType(
+      "Ldalvik/annotation/SourceDebugExtension;");
+  public final DexType annotationThrows = createType("Ldalvik/annotation/Throws;");
+
   public void clearSubtypeInformation() {
     types.values().forEach(DexType::clearSubtypeInformation);
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java b/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java
index c1b9205..0c8ce8c 100644
--- a/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java
@@ -7,8 +7,9 @@
 import com.android.tools.r8.dex.IndexedItemCollection;
 import com.android.tools.r8.dex.MixedSectionCollection;
 import com.android.tools.r8.errors.Unreachable;
+import java.util.function.Supplier;
 
-public class DexLibraryClass extends DexClass {
+public class DexLibraryClass extends DexClass implements Supplier<DexLibraryClass> {
 
   public DexLibraryClass(DexType type, Resource.Kind origin, DexAccessFlags accessFlags,
       DexType superType, DexTypeList interfaces, DexString sourceFile, DexAnnotationSet annotations,
@@ -48,4 +49,9 @@
   public DexLibraryClass asLibraryClass() {
     return this;
   }
+
+  @Override
+  public DexLibraryClass get() {
+    return this;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
index f93a7da..a38c9cb 100644
--- a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
@@ -7,8 +7,9 @@
 import com.android.tools.r8.dex.IndexedItemCollection;
 import com.android.tools.r8.dex.MixedSectionCollection;
 import java.util.Arrays;
+import java.util.function.Supplier;
 
-public class DexProgramClass extends DexClass {
+public class DexProgramClass extends DexClass implements Supplier<DexProgramClass> {
 
   private DexEncodedArray staticValues;
 
@@ -152,4 +153,9 @@
     directMethods = Arrays.copyOf(directMethods, directMethods.length + 1);
     directMethods[directMethods.length - 1] = staticMethod;
   }
+
+  @Override
+  public DexProgramClass get() {
+    return this;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
index a6b3fd0..c65b370 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
@@ -428,7 +428,11 @@
     }
 
     // Insert inlinee blocks into the IR code.
-    inlinee.blocks.forEach(blocksIterator::add);
+    int blockNumber = code.getHighestBlockNumber() + 1;
+    for (BasicBlock bb : inlinee.blocks) {
+      bb.setNumber(blockNumber++);
+      blocksIterator.add(bb);
+    }
 
     // If the invoke block had catch handlers copy those down to all inlined blocks.
     if (invokeBlock.hasCatchHandlers()) {
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 c96bf92..e1e9a99 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
@@ -17,6 +17,7 @@
 import java.util.List;
 import java.util.ListIterator;
 import java.util.Set;
+import java.util.stream.Collectors;
 
 public class IRCode {
 
@@ -135,6 +136,7 @@
   }
 
   public boolean isConsistentGraph() {
+    assert consistentBlockNumbering();
     assert consistentPredecessorSuccessors();
     assert consistentCatchHandlers();
     assert consistentBlockInstructions();
@@ -263,6 +265,12 @@
     return true;
   }
 
+  public boolean consistentBlockNumbering() {
+    return blocks.stream()
+        .collect(Collectors.groupingBy(BasicBlock::getNumber, Collectors.counting()))
+        .entrySet().stream().noneMatch((bb2count) -> bb2count.getValue() > 1);
+  }
+
   private boolean consistentBlockInstructions() {
     for (BasicBlock block : blocks) {
       for (Instruction instruction : block.getInstructions()) {
@@ -378,4 +386,8 @@
   public ConstNumber createFalse() {
     return new ConstNumber(ConstType.INT, createValue(MoveType.SINGLE), 0);
   }
+
+  public final int getHighestBlockNumber() {
+    return blocks.stream().max(Comparator.comparingInt(BasicBlock::getNumber)).get().getNumber();
+  }
 }
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 4d8eee1..f4406c0 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
@@ -19,9 +19,9 @@
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
-import java.util.Collections;
+import java.util.Arrays;
 import java.util.HashMap;
-import java.util.IdentityHashMap;
+import java.util.HashSet;
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -52,10 +52,10 @@
     private boolean isSelfRecursive = false;
 
     // Outgoing calls from this method.
-    public final Set<Node> callees = new LinkedHashSet<>();
+    private final Set<Node> callees = new LinkedHashSet<>();
 
     // Incoming calls to this method.
-    public final Set<Node> callers = new LinkedHashSet<>();
+    private final Set<Node> callers = new LinkedHashSet<>();
 
     private Node(DexEncodedMethod method) {
       this.method = method;
@@ -81,10 +81,6 @@
       return callees.isEmpty();
     }
 
-    int callDegree() {
-      return callees.size();
-    }
-
     @Override
     public int hashCode() {
       return method.hashCode();
@@ -133,75 +129,35 @@
     }
   }
 
-  public class Leaves {
-
-    private final List<DexEncodedMethod> leaves;
-    private final boolean brokeCycles;
-    private final Map<DexEncodedMethod, Set<DexEncodedMethod>> cycleBreakingCalls;
-
-    private Leaves(List<DexEncodedMethod> leaves, boolean brokeCycles,
-        Map<DexEncodedMethod, Set<DexEncodedMethod>> cycleBreakingCalls) {
-      this.leaves = leaves;
-      this.brokeCycles = brokeCycles;
-      this.cycleBreakingCalls = cycleBreakingCalls;
-      assert brokeCycles == (cycleBreakingCalls.size() != 0);
-    }
-
-    public int size() {
-      return leaves.size();
-    }
-
-    public List<DexEncodedMethod> getLeaves() {
-      return leaves;
-    }
-
-    public boolean hasBrokeCycles() {
-      return brokeCycles;
-    }
-
-    /**
-     * Calls that were broken to produce the leaves.
-     *
-     * If {@link Leaves#breakCycles()} return <code>true</code> this provides the calls for each
-     * leaf that were broken.
-     *
-     * NOTE: The broken calls are not confined to the set of leaves.
-     */
-    public Map<DexEncodedMethod, Set<DexEncodedMethod>> getCycleBreakingCalls() {
-      return cycleBreakingCalls;
-    }
-
-    @Override
-    public String toString() {
-      StringBuilder builder = new StringBuilder();
-      builder.append("Leaves: ");
-      builder.append(leaves.size());
-      builder.append("\n");
-      builder.append(brokeCycles ? "Call cycles broken" : "No call cycles broken");
-      return builder.toString();
-    }
-  }
-
   private final Map<DexEncodedMethod, Node> nodes = new LinkedHashMap<>();
   private final Map<DexEncodedMethod, Set<DexEncodedMethod>> breakers = new HashMap<>();
 
+  // Returns whether the method->callee edge has been removed from the call graph
+  // to break a cycle in the call graph.
+  public boolean isBreaker(DexEncodedMethod method, DexEncodedMethod callee) {
+    Set<DexEncodedMethod> value = breakers.get(method);
+    return (value != null) && value.contains(callee);
+  }
+
   private List<Node> leaves = null;
   private Set<DexEncodedMethod> singleCallSite = Sets.newIdentityHashSet();
   private Set<DexEncodedMethod> doubleCallSite = Sets.newIdentityHashSet();
 
   public static CallGraph build(DexApplication application, AppInfoWithSubtyping appInfo,
       GraphLense graphLense) {
-
     CallGraph graph = new CallGraph();
-    for (DexClass clazz : application.classes()) {
-      clazz.forEachMethod( method -> {
+    DexClass[] classes = application.classes().toArray(new DexClass[application.classes().size()]);
+    Arrays.sort(classes, (DexClass a, DexClass b) -> a.type.slowCompareTo(b.type));
+    for (DexClass clazz : classes) {
+      for (DexEncodedMethod method : clazz.allMethodsSorted()) {
         Node node = graph.ensureMethodNode(method);
         InvokeExtractor extractor = new InvokeExtractor(appInfo, graphLense, node, graph);
         method.registerReachableDefinitions(extractor);
-      });
+      }
     }
-
     assert allMethodsExists(application, graph);
+    graph.breakCycles();
+    assert graph.breakCycles() == 0;  // This time the cycles should be gone.
     graph.fillCallSiteSets(appInfo);
     graph.fillInitialLeaves();
     return graph;
@@ -258,7 +214,6 @@
 
   /**
    * Remove all leaves (nodes with an call (outgoing) degree of 0).
-   * <p>
    *
    * @return List of {@link DexEncodedMethod} of the leaves removed.
    */
@@ -282,73 +237,62 @@
    * leave is returned if the graph is not empty.
    * <p>
    *
-   * @return object with the leaves as a List of {@link DexEncodedMethod} and <code>boolean</code>
-   * indication of whether cycles were broken to produce leaves. <code>null</code> if the graph is
-   * empty.
+   * @return  List of {@link DexEncodedMethod}.
    */
-  public Leaves pickLeaves() {
-    boolean cyclesBroken = false;
-    Map<DexEncodedMethod, Set<DexEncodedMethod>> brokenCalls = Collections.emptyMap();
+  List<DexEncodedMethod> extractLeaves() {
     if (isEmpty()) {
       return null;
     }
     List<DexEncodedMethod> leaves = removeLeaves();
-    if (leaves.size() == 0) {
-      // The graph had no more leaves, so break cycles to construct leaves.
-      brokenCalls = breakCycles();
-      cyclesBroken = true;
-      leaves = removeLeaves();
-    }
     assert leaves.size() > 0;
-    for (DexEncodedMethod leaf : leaves) {
-      assert !leaf.isProcessed();
-    }
-    return new Leaves(leaves, cyclesBroken, brokenCalls);
+    leaves.forEach( leaf -> { assert !leaf.isProcessed(); });
+    return leaves;
   }
 
-  /**
-   * Break some cycles in the graph by removing edges.
-   * <p>
-   * This will find the lowest call (outgoing) degree in the graph. Then go through all nodes with
-   * that call (outgoing) degree, and remove all call (outgoing) edges from nodes with that call
-   * (outgoing) degree.
-   * <p>
-   * It will avoid removing edges from bridge-methods if possible.
-   * <p>
-   * Returns the calls that were broken.
-   */
-  private Map<DexEncodedMethod, Set<DexEncodedMethod>> breakCycles() {
-    Map<DexEncodedMethod, Set<DexEncodedMethod>> brokenCalls = new IdentityHashMap<>();
-    // Break non bridges with degree 1.
-    int minDegree = nodes.size();
-    for (Node node : nodes.values()) {
-      // Break cycles and add all leaves created in the process.
-      if (!node.isBridge() && node.callDegree() <= 1) {
-        assert node.callDegree() == 1;
-        Set<DexEncodedMethod> calls = removeAllCalls(node);
-        leaves.add(node);
-        brokenCalls.put(node.method, calls);
-      } else {
-        minDegree = Integer.min(minDegree, node.callDegree());
+  private int traverse(Node node, HashSet<Node> stack, HashSet<Node> marked) {
+    int numberOfCycles = 0;
+    if (!marked.contains(node)) {
+      assert !stack.contains(node);
+      stack.add(node);
+      ArrayList<Node> toBeRemoved = null;
+      // Sort the callees before calling traverse recursively.
+      // This will ensure cycles are broken the same way across
+      // multiple invocations of the R8 compiler.
+      Node[] callees = node.callees.toArray(new Node[node.callees.size()]);
+      Arrays.sort(callees, (Node a, Node b) -> a.method.method.slowCompareTo(b.method.method));
+      for (Node callee : callees) {
+        if (stack.contains(callee)) {
+          if (toBeRemoved == null) {
+            toBeRemoved = new ArrayList<>();
+          }
+          // We have a cycle; break it by removing node->callee.
+          toBeRemoved.add(callee);
+          callee.callers.remove(node);
+          breakers.computeIfAbsent(node.method, ignore -> new HashSet<>()).add(callee.method);
+        } else {
+          numberOfCycles += traverse(callee, stack, marked);
+        }
       }
-    }
-
-    // Return if new leaves were created.
-    if (leaves.size() > 0) {
-      return brokenCalls;
-    }
-
-    // Break methods with the found minimum degree and add all leaves created in the process.
-    for (Node node : nodes.values()) {
-      if (node.callDegree() <= minDegree) {
-        assert node.callDegree() == minDegree;
-        Set<DexEncodedMethod> calls = removeAllCalls(node);
-        leaves.add(node);
-        brokenCalls.put(node.method, calls);
+      if (toBeRemoved != null) {
+        numberOfCycles += toBeRemoved.size();
+        node.callees.removeAll(toBeRemoved);
       }
+      stack.remove(node);
+      marked.add(node);
     }
-    assert leaves.size() > 0;
-    return brokenCalls;
+    return numberOfCycles;
+  }
+
+  private int breakCycles() {
+    // Break cycles in this call graph by removing edges causing cycles.
+    // The remove edges are stored in @breakers.
+    int numberOfCycles = 0;
+    HashSet<Node> stack = new HashSet<>();
+    HashSet<Node> marked = new HashSet<>();
+    for(Node node : nodes.values()) {
+      numberOfCycles += traverse(node, stack, marked);
+    }
+    return numberOfCycles;
   }
 
   synchronized private Node ensureMethodNode(DexEncodedMethod method) {
@@ -367,16 +311,6 @@
     callee.invokeCount++;
   }
 
-  private Set<DexEncodedMethod> removeAllCalls(Node node) {
-    Set<DexEncodedMethod> calls = Sets.newIdentityHashSet();
-    for (Node call : node.callees) {
-      calls.add(call.method);
-      call.callers.remove(node);
-    }
-    node.callees.clear();
-    return calls;
-  }
-
   private void remove(Node node, List<Node> leaves) {
     assert node != null;
     for (Node caller : node.callers) {
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
index 4ce2c4c..ba63d80 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
@@ -270,6 +270,8 @@
   private List<Value> debugLocalReads = new ArrayList<>();
   private List<Value> debugLocalEnds = new ArrayList<>();
 
+  private int nextBlockNumber = 0;
+
   public IRBuilder(DexEncodedMethod method, SourceCode source, InternalOptions options) {
     this(method, source, new ValueNumberGenerator(), options);
   }
@@ -350,15 +352,14 @@
 
     // Process normal blocks reachable from the entry block using a worklist of reachable
     // blocks.
-    int blockNumber = 0;
     addToWorklist(currentBlock, 0);
-    blockNumber = processWorklist(blockNumber);
+    processWorklist();
 
     // Check that the last block is closed and does not fall off the end.
     assert currentBlock == null;
 
     // Handle where a catch handler hits the same block as the fallthrough.
-    blockNumber = handleFallthroughToCatchBlock(blockNumber);
+    handleFallthroughToCatchBlock();
 
     // Verify that we have properly filled all blocks
     // Must be after handle-catch (which has delayed edges),
@@ -366,7 +367,7 @@
     assert verifyFilledPredecessors();
 
     // If there are multiple returns create an exit block.
-    blockNumber = handleExitBlock(blockNumber);
+    handleExitBlock();
 
     // Clear all reaching definitions to free up memory (and avoid invalid use).
     for (BasicBlock block : blocks) {
@@ -437,14 +438,14 @@
     return true;
   }
 
-  private int processWorklist(int blockNumber) {
+  private void processWorklist() {
     for (WorklistItem item = ssaWorklist.poll(); item != null; item = ssaWorklist.poll()) {
       if (item.block.isFilled()) {
         continue;
       }
       setCurrentBlock(item.block);
       blocks.add(currentBlock);
-      currentBlock.setNumber(blockNumber++);
+      currentBlock.setNumber(nextBlockNumber++);
       // Build IR for each dex instruction in the block.
       for (int i = item.firstInstructionIndex; i < source.instructionCount(); ++i) {
         if (currentBlock == null) {
@@ -461,7 +462,6 @@
         source.buildInstruction(this, i);
       }
     }
-    return blockNumber;
   }
 
   // Helper to resolve switch payloads and build switch instructions (dex code only).
@@ -1536,6 +1536,7 @@
       return;
     }
     BasicBlock block = new BasicBlock();
+    block.setNumber(nextBlockNumber++);
     blocks.add(block);
     block.incrementUnfilledPredecessorCount();
     int freshOffset = INITIAL_BLOCK_OFFSET - 1;
@@ -1721,7 +1722,7 @@
     closeCurrentBlock();
   }
 
-  int handleExitBlock(int blockNumber) {
+  void handleExitBlock() {
     if (exitBlocks.size() > 0) {
       // Create and populate the exit block if needed (eg, synchronized support for jar).
       setCurrentBlock(new BasicBlock());
@@ -1730,11 +1731,11 @@
       if (currentBlock.getInstructions().isEmpty() && exitBlocks.size() == 1) {
         normalExitBlock = exitBlocks.get(0);
         setCurrentBlock(null);
-        return blockNumber;
+        return;
       }
       // Commit to creating the new exit block.
       normalExitBlock = currentBlock;
-      normalExitBlock.setNumber(blockNumber++);
+      normalExitBlock.setNumber(nextBlockNumber++);
       blocks.add(normalExitBlock);
       // Add the return instruction possibly creating a phi of return values.
       Return origReturn = exitBlocks.get(0).exit().asReturn();
@@ -1776,10 +1777,9 @@
         phi.addOperands(operands);
       }
     }
-    return blockNumber;
   }
 
-  private int handleFallthroughToCatchBlock(int blockNumber) {
+  private void handleFallthroughToCatchBlock() {
     // When a catch handler for a block goes to the same block as the fallthrough for that
     // block the graph only has one edge there. In these cases we add an additional block so the
     // catch edge goes through that and then make the fallthrough go through a new direct edge.
@@ -1788,7 +1788,7 @@
       BasicBlock target = pair.second;
 
       // New block with one unfilled predecessor.
-      BasicBlock newBlock = BasicBlock.createGotoBlock(target, blockNumber++);
+      BasicBlock newBlock = BasicBlock.createGotoBlock(target, nextBlockNumber++);
       blocks.add(newBlock);
       newBlock.incrementUnfilledPredecessorCount();
 
@@ -1808,7 +1808,6 @@
       }
       target.filledPredecessor(this);
     }
-    return blockNumber;
   }
 
   /**
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 98a2619..a345ddf 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
@@ -37,7 +37,7 @@
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.Timing;
-import com.google.common.collect.ImmutableList;
+
 import com.google.common.collect.ImmutableSet;
 import java.util.ArrayList;
 import java.util.List;
@@ -277,50 +277,21 @@
     // Process the application identifying outlining candidates.
     timing.begin("IR conversion phase 1");
     OptimizationFeedback directFeedback = new OptimizationFeedbackDirect();
-    OptimizationFeedbackDelayed delayedFeedback = new OptimizationFeedbackDelayed();
     while (!callGraph.isEmpty()) {
-      CallGraph.Leaves leaves = callGraph.pickLeaves();
-      List<DexEncodedMethod> methods = leaves.getLeaves();
+      List<DexEncodedMethod> methods = callGraph.extractLeaves();
       assert methods.size() > 0;
-      List<Future<?>> futures = new ArrayList<>();
-
       // For testing we have the option to determine the processing order of the methods.
       if (options.testing.irOrdering != null) {
-        methods = options.testing.irOrdering.apply(methods, leaves);
+        methods = options.testing.irOrdering.apply(methods);
       }
-
-      while (methods.size() > 0) {
-        // Process the methods on multiple threads. If cycles where broken collect the
-        // optimization feedback to reprocess methods affected by it. This is required to get
-        // deterministic behaviour, as the processing order within each set of leaves is
-        // non-deterministic.
-
-        // Due to a race condition, we serialize processing of methods if cycles are broken.
-        // TODO(bak)
-        if (leaves.hasBrokeCycles()) {
-          for (DexEncodedMethod method : methods) {
-            processMethod(method,
-                leaves.hasBrokeCycles() ? delayedFeedback : directFeedback,
-                outliner == null ? Outliner::noProcessing : outliner::identifyCandidates);
-          }
-        } else {
-          for (DexEncodedMethod method : methods) {
-            futures.add(executorService.submit(() -> {
-              processMethod(method,
-                  leaves.hasBrokeCycles() ? delayedFeedback : directFeedback,
-                  outliner == null ? Outliner::noProcessing : outliner::identifyCandidates);
-            }));
-          }
-          ThreadUtils.awaitFutures(futures);
-        }
-        if (leaves.hasBrokeCycles()) {
-          // If cycles in the call graph were broken, then re-process all methods which are
-          // affected by the optimization feedback of other methods in this group.
-          methods = delayedFeedback.applyAndClear(methods, leaves);
-        } else {
-          methods = ImmutableList.of();
-        }
+      List<Future<?>> futures = new ArrayList<>();
+      for (DexEncodedMethod method : methods) {
+        futures.add(executorService.submit(() -> {
+          processMethod(method, directFeedback,
+              outliner == null ? Outliner::noProcessing : outliner::identifyCandidates);
+        }));
       }
+      ThreadUtils.awaitFutures(futures);
     }
     timing.end();
 
@@ -550,7 +521,7 @@
     feedback.markProcessed(method, state);
   }
 
-  private void updateHighestSortingStrings(DexEncodedMethod method) {
+  private synchronized void updateHighestSortingStrings(DexEncodedMethod method) {
     DexString highestSortingReferencedString = method.getCode().asDexCode().highestSortingString;
     if (highestSortingReferencedString != null) {
       if (highestSortingString == null
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java
deleted file mode 100644
index a8c81ef..0000000
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java
+++ /dev/null
@@ -1,116 +0,0 @@
-// 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.ir.conversion;
-
-import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.ir.optimize.Inliner.Constraint;
-import com.google.common.collect.Maps;
-import com.google.common.collect.Sets;
-import it.unimi.dsi.fastutil.objects.Reference2IntMap;
-import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
-import it.unimi.dsi.fastutil.objects.Reference2LongMap;
-import it.unimi.dsi.fastutil.objects.Reference2LongOpenHashMap;
-import java.util.ArrayList;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-public class OptimizationFeedbackDelayed implements OptimizationFeedback {
-
-  private Reference2IntMap<DexEncodedMethod> returnsArgument = new Reference2IntOpenHashMap<>();
-  private Reference2LongMap<DexEncodedMethod> returnsConstant = new Reference2LongOpenHashMap<>();
-  private Set<DexEncodedMethod> neverReturnsNull = Sets.newIdentityHashSet();
-  private Map<DexEncodedMethod, Constraint> inliningConstraints = Maps.newIdentityHashMap();
-
-  @Override
-  synchronized public void methodReturnsArgument(DexEncodedMethod method, int argument) {
-    if (method.getOptimizationInfo().returnsArgument()) {
-      assert method.getOptimizationInfo().getReturnedArgument() == argument;
-      return;
-    }
-    assert !returnsArgument.containsKey(method);
-    returnsArgument.put(method, argument);
-  }
-
-  @Override
-  synchronized public void methodReturnsConstant(DexEncodedMethod method, long value) {
-    if (method.getOptimizationInfo().returnsConstant()) {
-      assert method.getOptimizationInfo().getReturnedConstant() == value;
-      return;
-    }
-    assert !returnsConstant.containsKey(method);
-    returnsConstant.put(method, value);
-  }
-
-  @Override
-  synchronized public void methodNeverReturnsNull(DexEncodedMethod method) {
-    if (method.getOptimizationInfo().neverReturnsNull()) {
-      return;
-    }
-    assert !neverReturnsNull.contains(method);
-    neverReturnsNull.add(method);
-  }
-
-  @Override
-  public void markProcessed(DexEncodedMethod method, Constraint state) {
-    if (state == Constraint.NEVER) {
-      assert method.cannotInline();
-      method.markProcessed(state);
-    } else {
-      inliningConstraints.put(method, state);
-    }
-  }
-
-  private <T> boolean setsOverlap(Set<T> set1, Set<T> set2) {
-    for (T element : set1) {
-      if (set2.contains(element)) {
-        return true;
-      }
-    }
-    return false;
-  }
-
-  /**
-   * Apply the optimization feedback.
-   *
-   * Returns the methods from the passed in list that could be affected by applying the
-   * optimization feedback.
-   */
-  public List<DexEncodedMethod> applyAndClear(
-      List<DexEncodedMethod> processed, CallGraph.Leaves leaves) {
-    returnsArgument.forEach(DexEncodedMethod::markReturnsArgument);
-    returnsConstant.forEach(DexEncodedMethod::markReturnsConstant);
-    neverReturnsNull.forEach(DexEncodedMethod::markNeverReturnsNull);
-
-    // Collect all methods affected by the optimization feedback applied.
-    Set<DexEncodedMethod> all = Sets.newIdentityHashSet();
-    all.addAll(returnsArgument.keySet());
-    all.addAll(returnsConstant.keySet());
-    all.addAll(neverReturnsNull);
-    inliningConstraints.forEach((method, constraint) -> {
-      boolean changed = method.markProcessed(constraint);
-      if (changed) {
-        all.add(method);
-      }
-    });
-
-    // Collect the processed methods which could be affected by the applied optimization feedback.
-    List<DexEncodedMethod> result = new ArrayList<>();
-    for (DexEncodedMethod method : processed) {
-      Set<DexEncodedMethod> calls = leaves.getCycleBreakingCalls().get(method);
-      if (setsOverlap(calls, all)) {
-        result.add(method);
-      }
-    }
-
-    // Clear the collected optimization feedback.
-    returnsArgument.clear();
-    returnsConstant.clear();
-    neverReturnsNull.clear();
-    inliningConstraints.clear();
-
-    return result;
-  }
-}
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 6d69817..4ede5a8 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
@@ -284,6 +284,10 @@
               if (block.hasCatchHandlers() && inlinee.getNormalExitBlock() == null) {
                 continue;
               }
+              if (callGraph.isBreaker(method, target)) {
+                // Make sure we don't inline a call graph breaker.
+                continue;
+              }
               // If this code did not go through the full pipeline, apply inlining to make sure
               // that force inline targets get processed.
               if (!target.isProcessed()) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/InliningOracle.java b/src/main/java/com/android/tools/r8/ir/optimize/InliningOracle.java
index 4b93d8d..446b75a 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/InliningOracle.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/InliningOracle.java
@@ -66,6 +66,7 @@
       assert !candidate.getOptimizationInfo().forceInline();
       return null;
     }
+
     if (candidate.accessFlags.isSynchronized()) {
       // Don't inline if target is synchronized.
       if (info != null) {
@@ -73,6 +74,12 @@
       }
       return null;
     }
+
+    if (callGraph.isBreaker(method, candidate)) {
+      // Cycle breaker so abort to preserve compilation order.
+      return null;
+    }
+
     if (!inliner.hasInliningAccess(method, candidate)) {
       if (info != null) {
         info.exclude(invoke, "Inlinee candidate does not have right access flags");
@@ -154,6 +161,11 @@
       return null;
     }
 
+    if (callGraph.isBreaker(method, target)) {
+      // Cycle breaker so abort to preserve compilation order.
+      return null;
+    }
+
     // Abort inlining attempt if method -> target access is not right.
     if (!inliner.hasInliningAccess(method, target)) {
       if (info != null) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/PeepholeOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/PeepholeOptimizer.java
index de81dfe..9a70864 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/PeepholeOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/PeepholeOptimizer.java
@@ -42,6 +42,7 @@
   private static void shareIdenticalBlockSuffix(IRCode code, RegisterAllocator allocator) {
     Collection<BasicBlock> blocks = code.blocks;
     do {
+      int startNumberOfNewBlock = code.getHighestBlockNumber() + 1;
       Map<BasicBlock, BasicBlock> newBlocks = new IdentityHashMap<>();
       for (BasicBlock block : blocks) {
         InstructionEquivalence equivalence = new InstructionEquivalence(allocator);
@@ -79,7 +80,7 @@
                 commonSuffixSize, sharedSuffixSizeExcludingExit(firstPred, pred, allocator));
           }
           assert commonSuffixSize >= 1;
-          int blockNumber = code.blocks.size() + newBlocks.size();
+          int blockNumber = startNumberOfNewBlock + newBlocks.size();
           BasicBlock newBlock = createAndInsertBlockForSuffix(
               blockNumber, commonSuffixSize, predsWithSameLastInstruction, block);
           newBlocks.put(predsWithSameLastInstruction.get(0), newBlock);
diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
index 7c12590..9f26fb5 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
@@ -3,14 +3,17 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.naming;
 
+import com.android.tools.r8.graph.DexAnnotation;
 import com.android.tools.r8.graph.DexClass;
-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.graph.DexValue;
+import com.android.tools.r8.graph.DexValue.DexValueType;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
+import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.StringUtils;
-import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 import java.util.Collections;
@@ -29,30 +32,31 @@
 
   private final Map<DexType, DexString> renaming = Maps.newIdentityHashMap();
   private final Map<String, NamingState> states = new HashMap<>();
-  final List<String> dictionary;
+  private final List<String> dictionary;
+  private final boolean keepInnerClassStructure;
 
   public ClassNameMinifier(AppInfoWithLiveness appInfo, RootSet rootSet, String packagePrefix,
-      List<String> dictionary) {
+      List<String> dictionary, boolean keepInnerClassStructure) {
     this.appInfo = appInfo;
     this.rootSet = rootSet;
     this.packagePrefix = packagePrefix;
     this.dictionary = dictionary;
+    this.keepInnerClassStructure = keepInnerClassStructure;
   }
 
   public Map<DexType, DexString> computeRenaming() {
+    Iterable<DexProgramClass> classes = appInfo.classes();
     // Collect names we have to keep.
     for (DexClass clazz : appInfo.classes()) {
       if (rootSet.noObfuscation.contains(clazz)) {
         assert !renaming.containsKey(clazz.type);
-        renaming.put(clazz.type, clazz.type.descriptor);
-        usedTypeNames.add(clazz.type.descriptor);
+        registerClassAsUsed(clazz.type);
       }
     }
     for (DexClass clazz : appInfo.classes()) {
       if (!renaming.containsKey(clazz.type)) {
-        String packageName = getPackageNameFor(clazz);
-        NamingState state = getStateFor(packageName);
-        renaming.put(clazz.type, state.nextTypeName());
+        DexString renamed = computeName(clazz);
+        renaming.put(clazz.type, renamed);
       }
     }
     appInfo.dexItemFactory.forAllTypes(this::renameArrayTypeIfNeeded);
@@ -60,6 +64,63 @@
     return Collections.unmodifiableMap(renaming);
   }
 
+  /**
+   * Registers the given type as used.
+   * <p>
+   * When {@link #keepInnerClassStructure} is true, keeping the name of an inner class will
+   * automatically also keep the name of the outer class, as otherwise the structure would be
+   * invalidated.
+   */
+  private void registerClassAsUsed(DexType type) {
+    renaming.put(type, type.descriptor);
+    usedTypeNames.add(type.descriptor);
+    if (keepInnerClassStructure) {
+      DexType outerClass = getOutClassForType(type);
+      if (outerClass != null) {
+        if (!renaming.containsKey(outerClass)) {
+          // The outer class was not previously kept. We have to do this now.
+          registerClassAsUsed(outerClass);
+        }
+      }
+    }
+  }
+
+  private DexType getOutClassForType(DexType type) {
+    DexClass clazz = appInfo.definitionFor(type);
+    if (clazz == null) {
+      return null;
+    }
+    DexAnnotation annotation =
+        clazz.annotations.getFirstMatching(appInfo.dexItemFactory.annotationEnclosingClass);
+    if (annotation != null) {
+      assert annotation.annotation.elements.length == 1;
+      DexValue value = annotation.annotation.elements[0].value;
+      return ((DexValueType) value).value;
+    }
+    // We do not need to preserve the names for local or anonymous classes, as they do not result
+    // in a member type declaration and hence cannot be referenced as nested classes in
+    // method signatures.
+    // See https://docs.oracle.com/javase/specs/jls/se7/html/jls-8.html#jls-8.5.
+    return null;
+  }
+
+  private DexString computeName(DexClass clazz) {
+    NamingState state = null;
+    if (keepInnerClassStructure) {
+      // When keeping the nesting structure of inner classes, we have to insert the name
+      // of the outer class for the $ prefix.
+      DexType outerClass = getOutClassForType(clazz.type);
+      if (outerClass != null) {
+        state = getStateForOuterClass(outerClass);
+      }
+    }
+    if (state == null) {
+      String packageName = getPackageNameFor(clazz);
+      state = getStateFor(packageName);
+    }
+    return state.nextTypeName();
+  }
+
   private String getPackageNameFor(DexClass clazz) {
     if ((packagePrefix == null) || rootSet.keepPackageName.contains(clazz)) {
       return clazz.type.getPackageDescriptor();
@@ -72,6 +133,27 @@
     return states.computeIfAbsent(packageName, NamingState::new);
   }
 
+  private NamingState getStateForOuterClass(DexType outer) {
+    String prefix = DescriptorUtils
+        .getClassBinaryNameFromDescriptor(outer.toDescriptorString());
+    return states.computeIfAbsent(prefix, k -> {
+      // Create a naming state with this classes renaming as prefix.
+      DexString renamed = renaming.get(outer);
+      if (renamed == null) {
+        // The outer class has not been renamed yet, so rename the outer class first.
+        DexClass outerClass = appInfo.definitionFor(outer);
+        if (outerClass == null) {
+          renamed = outer.descriptor;
+        } else {
+          renamed = computeName(outerClass);
+          renaming.put(outer, renamed);
+        }
+      }
+      String binaryName = DescriptorUtils.getClassBinaryNameFromDescriptor(renamed.toString());
+      return new NamingState(binaryName, "$");
+    });
+  }
+
   private void renameArrayTypeIfNeeded(DexType type) {
     if (type.isArrayType()) {
       DexType base = type.toBaseType(appInfo.dexItemFactory);
@@ -92,11 +174,18 @@
   private class NamingState {
 
     private final char[] packagePrefix;
+    private final String separator;
     private int typeCounter = 1;
     private Iterator<String> dictionaryIterator;
 
     NamingState(String packageName) {
-      this.packagePrefix = ("L" + packageName + (packageName.isEmpty() ? "" : "/")).toCharArray();
+      this(packageName, "/");
+    }
+
+    NamingState(String packageName, String separator) {
+      this.packagePrefix = ("L" + packageName + (packageName.isEmpty() ? "" : separator))
+          .toCharArray();
+      this.separator = separator;
       this.dictionaryIterator = dictionary.iterator();
     }
 
diff --git a/src/main/java/com/android/tools/r8/naming/Minifier.java b/src/main/java/com/android/tools/r8/naming/Minifier.java
index 9e81102..025002d 100644
--- a/src/main/java/com/android/tools/r8/naming/Minifier.java
+++ b/src/main/java/com/android/tools/r8/naming/Minifier.java
@@ -42,7 +42,8 @@
     timing.begin("MinifyClasses");
     Map<DexType, DexString> classRenaming =
         new ClassNameMinifier(
-            appInfo, rootSet, options.packagePrefix, options.classObfuscationDictionary)
+            appInfo, rootSet, options.packagePrefix, options.classObfuscationDictionary,
+            options.attributeRemoval.signature)
             .computeRenaming();
     timing.end();
     timing.begin("MinifyMethods");
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 e60f241..3ab231c 100644
--- a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.DexAnnotationSetRefList;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.android.tools.r8.utils.InternalOptions;
@@ -42,21 +43,24 @@
       case DexAnnotation.VISIBILITY_SYSTEM:
         // EnclosingClass and InnerClass are used in Dalvik to represent the InnerClasses
         // attribute section from class files.
-        if (keep.innerClasses &&
-            (DexAnnotation.isInnerClassesAnnotation(annotation) ||
-                DexAnnotation.isEnclosingClassAnnotation(annotation))) {
+        DexItemFactory factory = appInfo.dexItemFactory;
+        if (keep.innerClasses
+            && (DexAnnotation.isInnerClassesAnnotation(annotation, factory) ||
+                DexAnnotation.isEnclosingClassAnnotation(annotation, factory))) {
           return true;
         }
-        if (keep.enclosingMethod && DexAnnotation.isEnclosingMethodAnnotation(annotation)) {
+        if (keep.enclosingMethod
+            && DexAnnotation.isEnclosingMethodAnnotation(annotation, factory)) {
           return true;
         }
-        if (keep.exceptions && DexAnnotation.isThrowingAnnotation(annotation)) {
+        if (keep.exceptions && DexAnnotation.isThrowingAnnotation(annotation, factory)) {
           return true;
         }
-        if (keep.signature && DexAnnotation.isSignatureAnnotation(annotation)) {
+        if (keep.signature && DexAnnotation.isSignatureAnnotation(annotation, factory)) {
           return true;
         }
-        if (keep.sourceDebugExtension && DexAnnotation.isSourceDebugExtension(annotation)) {
+        if (keep.sourceDebugExtension
+            && DexAnnotation.isSourceDebugExtension(annotation, factory)) {
           return true;
         }
         return false;
diff --git a/src/main/java/com/android/tools/r8/utils/ClassMap.java b/src/main/java/com/android/tools/r8/utils/ClassMap.java
index 91adca4..9677473 100644
--- a/src/main/java/com/android/tools/r8/utils/ClassMap.java
+++ b/src/main/java/com/android/tools/r8/utils/ClassMap.java
@@ -4,17 +4,19 @@
 package com.android.tools.r8.utils;
 
 import com.android.tools.r8.errors.CompilationError;
+import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.ClassKind;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexType;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
-import java.util.Collection;
 import java.util.IdentityHashMap;
+import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.function.Predicate;
+import java.util.function.Supplier;
 
 /**
  * Represents a collection of classes. Collection can be fully loaded,
@@ -25,13 +27,17 @@
   // resources provided by different resource providers.
   //
   // NOTE: all access must be synchronized on `classes`.
-  private final Map<DexType, Value<T>> classes;
+  private final Map<DexType, Supplier<T>> classes;
 
-  // Class provider if available. In case it's `null`, all classes of
-  // the collection must be pre-populated in `classes`.
-  private final ClassProvider<T> classProvider;
+  // Class provider if available.
+  //
+  // If the class provider is `null` it indicates that all classes are already present
+  // in a map referenced by `classes` and thus the collection is fully loaded.
+  //
+  // NOTE: all access must be synchronized on `classes`.
+  private ClassProvider<T> classProvider;
 
-  ClassMap(Map<DexType, Value<T>> classes, ClassProvider<T> classProvider) {
+  ClassMap(Map<DexType, Supplier<T>> classes, ClassProvider<T> classProvider) {
     this.classes = classes == null ? new IdentityHashMap<>() : classes;
     this.classProvider = classProvider;
     assert this.classProvider == null || this.classProvider.getClassKind() == getClassKind();
@@ -40,6 +46,9 @@
   /** Resolves a class conflict by selecting a class, may generate compilation error. */
   abstract T resolveClassConflict(T a, T b);
 
+  /** Return supplier for preloaded class. */
+  abstract Supplier<T> getTransparentSupplier(T clazz);
+
   /** Kind of the classes supported by this collection. */
   abstract ClassKind getClassKind();
 
@@ -53,115 +62,175 @@
 
   /** Returns a definition for a class or `null` if there is no such class in the collection. */
   public T get(DexType type) {
-    final Value<T> value = getOrCreateValue(type);
+    Supplier<T> supplier;
 
-    if (value == null) {
-      return null;
-    }
-
-    if (!value.ready) {
-      // Load the value in a context synchronized on value instance. This way
-      // we avoid locking the whole collection during expensive resource loading
-      // and classes construction operations.
-      synchronized (value) {
-        if (!value.ready) {
-          assert classProvider != null : "getOrCreateValue() created "
-              + "Value for missing type when there is no classProvider.";
-          classProvider.collectClass(type, clazz -> {
-            assert clazz != null;
-            assert getClassKind().isOfKind(clazz);
-            assert !value.ready;
-
-            if (clazz.type != type) {
-              throw new CompilationError("Class content provided for type descriptor "
-                  + type.toSourceString() + " actually defines class " + clazz.type
-                  .toSourceString());
-            }
-
-            if (value.clazz == null) {
-              value.clazz = clazz;
-            } else {
-              // The class resolution *may* generate a compilation error as one of
-              // possible resolutions. In this case we leave `value` in (false, null)
-              // state so in rare case of another thread trying to get the same class
-              // before this error is propagated it will get the same conflict.
-              T oldClass = value.clazz;
-              value.clazz = null;
-              value.clazz = resolveClassConflict(oldClass, clazz);
-            }
-          });
-          value.ready = true;
-        }
-      }
-    }
-
-    assert value.ready;
-    return value.clazz;
-  }
-
-  private Value<T> getOrCreateValue(DexType type) {
     synchronized (classes) {
-      Value<T> value = classes.get(type);
-      if (value == null && classProvider != null) {
-        value = new Value<>();
-        classes.put(type, value);
+      supplier = classes.get(type);
+
+      // Get class supplier, create it if it does not
+      // exist and the collection is NOT fully loaded.
+      if (supplier == null) {
+        if (classProvider == null) {
+          // There is no supplier, but the collection is fully loaded.
+          return null;
+        }
+
+        supplier = new ConcurrentClassLoader<>(this, this.classProvider, type);
+        classes.put(type, supplier);
       }
-      return value;
     }
+
+    return supplier.get();
   }
 
-  /**
-   * Returns currently loaded classes.
-   *
-   * Method is assumed to be called when the collection is fully loaded,
-   * otherwise only a subset of potentially loaded classes may be returned.
-   */
-  public List<T> collectLoadedClasses() {
+  /** Returns all classes from the collection. The collection must be force-loaded. */
+  public List<T> getAllClasses() {
     List<T> loadedClasses = new ArrayList<>();
     synchronized (classes) {
-      for (Value<T> value : classes.values()) {
-        // NOTE: value mutations are NOT synchronized on `classes`, here we actually
-        // can see value which is not ready yet. Since everything that exists should
-        // be guaranteed by the caller to be loaded at this point, this can only happen
-        // if the code references classes that do not exist. Therefore, if the value is
-        // not ready here, we know that the loaded value will be 'null' once it is ready.
-        if (value.ready && value.clazz != null) {
-          loadedClasses.add(value.clazz);
-        }
+      if (classProvider != null) {
+        throw new Unreachable("Getting all classes from not fully loaded collection.");
+      }
+      for (Supplier<T> supplier : classes.values()) {
+        // Since the class map is fully loaded, all suppliers must be
+        // loaded and non-null.
+        T clazz = supplier.get();
+        assert clazz != null;
+        loadedClasses.add(clazz);
       }
     }
     return loadedClasses;
   }
 
-  /** Forces loading of all the classes satisfying the criteria specified. */
+  /**
+   * Forces loading of all the classes satisfying the criteria specified.
+   *
+   * NOTE: after this method finishes, the class map is considered to be fully-loaded
+   * and thus sealed. This has one side-effect: if we filter out some of the classes
+   * with `load` predicate, these classes will never be loaded.
+   */
   public void forceLoad(Predicate<DexType> load) {
-    if (classProvider != null) {
-      Set<DexType> loaded = Sets.newIdentityHashSet();
-      synchronized (classes) {
-        loaded.addAll(classes.keySet());
+    Set<DexType> knownClasses;
+    ClassProvider<T> classProvider;
+
+    synchronized (classes) {
+      classProvider = this.classProvider;
+      if (classProvider == null) {
+        return;
       }
-      Collection<DexType> types = classProvider.collectTypes();
-      for (DexType type : types) {
-        if (load.test(type) && !loaded.contains(type)) {
-          get(type); // force-load type.
+
+      // Collects the types which might be represented in fully loaded class map.
+      knownClasses = Sets.newIdentityHashSet();
+      knownClasses.addAll(classes.keySet());
+    }
+
+    // Add all types the class provider provides. Note that it may take time for class
+    // provider to collect these types, so ve do it outside synchronized context.
+    knownClasses.addAll(classProvider.collectTypes());
+
+    // Make sure all the types in `knownClasses` are loaded.
+    //
+    // We just go and touch every class, thus triggering their loading if they
+    // are not loaded so far. In case the class has already been loaded,
+    // touching the class will be a no-op with minimal overhead.
+    for (DexType type : knownClasses) {
+      if (load.test(type)) {
+        get(type);
+      }
+    }
+
+    synchronized (classes) {
+      if (this.classProvider == null) {
+        return; // Has been force-loaded concurrently.
+      }
+
+      // We avoid calling get() on a class supplier unless we know it was loaded.
+      // At this time `classes` may have more types then `knownClasses`, but for
+      // all extra classes we expect the supplier to return 'null' after loading.
+      Iterator<Map.Entry<DexType, Supplier<T>>> iterator = classes.entrySet().iterator();
+      while (iterator.hasNext()) {
+        Map.Entry<DexType, Supplier<T>> e = iterator.next();
+
+        if (knownClasses.contains(e.getKey())) {
+          // Get the class (it is expected to be loaded by this time).
+          T clazz = e.getValue().get();
+          if (clazz != null) {
+            // Since the class is already loaded, get rid of possible wrapping suppliers.
+            assert clazz.type == e.getKey();
+            e.setValue(getTransparentSupplier(clazz));
+            continue;
+          }
         }
+
+        // If the type is not in `knownClasses` or resolves to `null`,
+        // just remove the record from the map.
+        iterator.remove();
       }
+
+      // Mark the class map as fully loaded.
+      this.classProvider = null;
     }
   }
 
-  // Represents a value in the class map.
-  final static class Value<T> {
-    volatile boolean ready;
-    T clazz;
+  // Supplier implementing a thread-safe loader for a class loaded from a
+  // class provider. Helps avoid synchronizing on the whole class map
+  // when loading a class.
+  private static class ConcurrentClassLoader<T extends DexClass> implements Supplier<T> {
+    private ClassMap<T> classMap;
+    private ClassProvider<T> provider;
+    private DexType type;
 
-    Value() {
-      ready = false;
-      clazz = null;
+    private T clazz = null;
+    private volatile boolean ready = false;
+
+    ConcurrentClassLoader(ClassMap<T> classMap, ClassProvider<T> provider, DexType type) {
+      this.classMap = classMap;
+      this.provider = provider;
+      this.type = type;
     }
 
-    Value(T clazz) {
-      this.clazz = clazz;
-      this.ready = true;
+    @Override
+    public T get() {
+      if (ready) {
+        return clazz;
+      }
+
+      synchronized (this) {
+        if (!ready) {
+          assert classMap != null && provider != null && type != null;
+          provider.collectClass(type, createdClass -> {
+            assert createdClass != null;
+            assert classMap.getClassKind().isOfKind(createdClass);
+            assert !ready;
+
+            if (createdClass.type != type) {
+              throw new CompilationError(
+                  "Class content provided for type descriptor " + type.toSourceString() +
+                      " actually defines class " + createdClass.type.toSourceString());
+            }
+
+            if (clazz == null) {
+              clazz = createdClass;
+            } else {
+              // The class resolution *may* generate a compilation error as one of
+              // possible resolutions. In this case we leave `value` in (false, null)
+              // state so in rare case of another thread trying to get the same class
+              // before this error is propagated it will get the same conflict.
+              T oldClass = clazz;
+              clazz = null;
+              clazz = classMap.resolveClassConflict(oldClass, createdClass);
+            }
+          });
+
+          classMap = null;
+          provider = null;
+          type = null;
+          ready = true;
+        }
+      }
+
+      assert ready;
+      assert classMap == null && provider == null && type == null;
+      return clazz;
     }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/utils/ClasspathClassCollection.java b/src/main/java/com/android/tools/r8/utils/ClasspathClassCollection.java
index ee00c39..45002d0 100644
--- a/src/main/java/com/android/tools/r8/utils/ClasspathClassCollection.java
+++ b/src/main/java/com/android/tools/r8/utils/ClasspathClassCollection.java
@@ -6,6 +6,7 @@
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.graph.ClassKind;
 import com.android.tools.r8.graph.DexClasspathClass;
+import java.util.function.Supplier;
 
 /** Represents a collection of classpath classes. */
 public class ClasspathClassCollection extends ClassMap<DexClasspathClass> {
@@ -19,6 +20,11 @@
   }
 
   @Override
+  Supplier<DexClasspathClass> getTransparentSupplier(DexClasspathClass clazz) {
+    return clazz;
+  }
+
+  @Override
   ClassKind getClassKind() {
     return ClassKind.CLASSPATH;
   }
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 9d6cfa5..7155a13 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -15,6 +15,7 @@
 import java.nio.file.Path;
 import java.util.List;
 import java.util.function.BiFunction;
+import java.util.function.Function;
 
 public class InternalOptions {
 
@@ -140,8 +141,7 @@
   }
 
   public static class TestingOptions {
-
-    public BiFunction<List<DexEncodedMethod>, CallGraph.Leaves, List<DexEncodedMethod>> irOrdering;
+    public Function<List<DexEncodedMethod>, List<DexEncodedMethod>> irOrdering;
   }
 
   public static class AttributeRemovalOptions {
@@ -251,15 +251,18 @@
 
     public void ensureValid(boolean isMinifying) {
       if (innerClasses && !enclosingMethod) {
-        throw new CompilationError("Attribute InnerClasses implies EnclosingMethod attribute. " +
-            "Check -keepattributes directive.");
+        throw new CompilationError("Attribute InnerClasses requires EnclosingMethod attribute. "
+            + "Check -keepattributes directive.");
       } else if (!innerClasses && enclosingMethod) {
-        throw new CompilationError("Attribute EnclosingMethod requires InnerClasses attribute. " +
-            "Check -keepattributes directive.");
+        throw new CompilationError("Attribute EnclosingMethod requires InnerClasses attribute. "
+            + "Check -keepattributes directive.");
+      } else if (signature && !innerClasses) {
+        throw new CompilationError("Attribute Signature requires InnerClasses attribute. Check "
+            + "-keepattributes directive.");
       } else if (signature && isMinifying) {
         // TODO(38188583): Allow this once we can minify signatures.
-        throw new CompilationError("Attribute Signature cannot be kept when minifying. " +
-            "Check -keepattributes directive.");
+        throw new CompilationError("Attribute Signature cannot be kept when minifying. "
+            + "Check -keepattributes directive.");
       }
     }
   }
diff --git a/src/main/java/com/android/tools/r8/utils/LibraryClassCollection.java b/src/main/java/com/android/tools/r8/utils/LibraryClassCollection.java
index e11e660..c94d7be 100644
--- a/src/main/java/com/android/tools/r8/utils/LibraryClassCollection.java
+++ b/src/main/java/com/android/tools/r8/utils/LibraryClassCollection.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexLibraryClass;
 import com.android.tools.r8.logging.Log;
+import java.util.function.Supplier;
 
 /** Represents a collection of library classes. */
 public class LibraryClassCollection extends ClassMap<DexLibraryClass> {
@@ -31,6 +32,11 @@
   }
 
   @Override
+  Supplier<DexLibraryClass> getTransparentSupplier(DexLibraryClass clazz) {
+    return clazz;
+  }
+
+  @Override
   ClassKind getClassKind() {
     return ClassKind.LIBRARY;
   }
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 a37eb92..590ba83 100644
--- a/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java
+++ b/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java
@@ -11,25 +11,20 @@
 import com.android.tools.r8.ir.desugar.LambdaRewriter;
 import java.util.IdentityHashMap;
 import java.util.List;
+import java.util.function.Supplier;
 
 /** Represents a collection of library classes. */
 public class ProgramClassCollection extends ClassMap<DexProgramClass> {
   public static ProgramClassCollection create(List<DexProgramClass> classes) {
     // We have all classes preloaded, but not necessarily without conflicts.
-    IdentityHashMap<DexType, Value<DexProgramClass>> map = new IdentityHashMap<>();
+    IdentityHashMap<DexType, Supplier<DexProgramClass>> map = new IdentityHashMap<>();
     for (DexProgramClass clazz : classes) {
-      Value<DexProgramClass> value = map.get(clazz.type);
-      if (value == null) {
-        value = new Value<>(clazz);
-        map.put(clazz.type, value);
-      } else {
-        value.clazz = resolveClassConflictImpl(value.clazz, clazz);
-      }
+      map.merge(clazz.type, clazz, (a, b) -> resolveClassConflictImpl(a.get(), b.get()));
     }
     return new ProgramClassCollection(map);
   }
 
-  private ProgramClassCollection(IdentityHashMap<DexType, Value<DexProgramClass>> classes) {
+  private ProgramClassCollection(IdentityHashMap<DexType, Supplier<DexProgramClass>> classes) {
     super(classes, null);
   }
 
@@ -44,6 +39,11 @@
   }
 
   @Override
+  Supplier<DexProgramClass> getTransparentSupplier(DexProgramClass clazz) {
+    return clazz;
+  }
+
+  @Override
   ClassKind getClassKind() {
     return ClassKind.PROGRAM;
   }
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreDeterministicTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreDeterministicTest.java
index 74f9ef9..8fdcfa5 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreDeterministicTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreDeterministicTest.java
@@ -12,7 +12,6 @@
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.ir.conversion.CallGraph;
 import com.android.tools.r8.shaking.ProguardRuleParserException;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.OutputMode;
@@ -29,7 +28,7 @@
 
 public class R8GMSCoreDeterministicTest extends GMSCoreCompilationTestBase {
 
-  public List<DexEncodedMethod> shuffle(List<DexEncodedMethod> methods, CallGraph.Leaves leaves) {
+  public List<DexEncodedMethod> shuffle(List<DexEncodedMethod> methods) {
     Collections.shuffle(methods);
     return methods;
   }
diff --git a/src/test/java/com/android/tools/r8/ir/deterministic/DeterministicProcessingTest.java b/src/test/java/com/android/tools/r8/ir/deterministic/DeterministicProcessingTest.java
deleted file mode 100644
index d5f70cc..0000000
--- a/src/test/java/com/android/tools/r8/ir/deterministic/DeterministicProcessingTest.java
+++ /dev/null
@@ -1,130 +0,0 @@
-// 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.ir.deterministic;
-
-import static org.junit.Assert.assertArrayEquals;
-import static org.junit.Assert.assertEquals;
-
-import com.android.tools.r8.CompilationException;
-import com.android.tools.r8.R8Command;
-import com.android.tools.r8.ToolHelper;
-import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.ir.conversion.CallGraph;
-import com.android.tools.r8.shaking.ProguardRuleParserException;
-import com.android.tools.r8.smali.SmaliTestBase;
-import com.android.tools.r8.utils.AndroidApp;
-import com.android.tools.r8.utils.DexInspector;
-import java.io.IOException;
-import java.nio.file.Paths;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.List;
-import java.util.concurrent.ExecutionException;
-import org.junit.Test;
-
-public class DeterministicProcessingTest extends SmaliTestBase {
-  public List<DexEncodedMethod> shuffle(List<DexEncodedMethod> methods, CallGraph.Leaves leaves) {
-    Collections.shuffle(methods);
-    return methods;
-  }
-
-  // This test will process the code a number of times each time shuffling the order in which
-  // the methods are processed. It does not do a exhaustive probing of all permutations, so if
-  // this fails it might not fail consistently, but under all circumstances a failure does reveal
-  // non-determinism in the IR-processing.
-  @Test
-  public void shuffleOrderTest()
-      throws IOException, ExecutionException, ProguardRuleParserException, CompilationException {
-    final int ITERATIONS = 25;
-    R8Command.Builder builder =
-        R8Command.builder()
-            .addProgramFiles(ToolHelper.getClassFileForTestClass(TestClass.class))
-            .addLibraryFiles(Paths.get(ToolHelper.getDefaultAndroidJar()));
-    byte[] expectedDex = null;
-    for (int i = 0; i < ITERATIONS; i++) {
-      AndroidApp result =
-          ToolHelper.runR8(
-              builder.build(), options -> {
-                // For this test just do random shuffle.
-                options.testing.irOrdering = this::shuffle;
-                // Only use one thread to process to process in the order decided by the callback.
-                options.numberOfThreads = 1;
-              });
-      List<byte[]> dex = result.writeToMemory();
-      assertEquals(1, dex.size());
-      if (i == 0) {
-        assert expectedDex == null;
-        expectedDex = dex.get(0);
-      } else {
-        assertArrayEquals(expectedDex, dex.get(0));
-      }
-    }
-  }
-
-  // Global variables used by the shuffler callback.
-  int iteration = 0;
-  Class testClass = null;
-
-  public List<DexEncodedMethod> permutationsOfTwo(
-      List<DexEncodedMethod> methods, CallGraph.Leaves leaves) {
-    if (!leaves.hasBrokeCycles()) {
-      return methods;
-    }
-    methods.sort(Comparator.comparing(DexEncodedMethod::qualifiedName));
-    assertEquals(2, methods.size());
-    String className = testClass.getTypeName();
-    // Check that we are permutating the expected methods.
-    assertEquals(className + ".a", methods.get(0).qualifiedName());
-    assertEquals(className + ".b", methods.get(1).qualifiedName());
-    if (iteration == 1) {
-      Collections.swap(methods, 0, 1);
-    }
-    return methods;
-  }
-
-  public void runTest(Class clazz, boolean inline) throws Exception {
-    final int ITERATIONS = 2;
-    testClass = clazz;
-    R8Command.Builder builder =
-        R8Command.builder()
-            .addProgramFiles(ToolHelper.getClassFileForTestClass(clazz))
-            .addLibraryFiles(Paths.get(ToolHelper.getDefaultAndroidJar()));
-    List<byte[]> results = new ArrayList<>();
-    for (iteration = 0; iteration < ITERATIONS; iteration++) {
-      AndroidApp result =
-          ToolHelper.runR8(
-              builder.build(), options -> {
-                options.inlineAccessors = inline;
-                // Callback to determine IR processing order.
-                options.testing.irOrdering = this::permutationsOfTwo;
-                // Only use one thread to process to process in the order decided by the callback.
-                options.numberOfThreads = 1;
-              });
-      List<byte[]> dex = result.writeToMemory();
-      DexInspector x = new DexInspector(result);
-      assertEquals(1, dex.size());
-      results.add(dex.get(0));
-    }
-    for (int i = 0; i < ITERATIONS - 1; i++) {
-      assertArrayEquals(results.get(i), results.get(i + 1));
-    }
-  }
-
-  @Test
-  public void testReturnArguments() throws Exception {
-    runTest(TestClassReturnsArgument.class, false);
-  }
-
-  @Test
-  public void testReturnConstant() throws Exception {
-    runTest(TestClassReturnsConstant.class, false);
-  }
-
-  @Test
-  public void testInline() throws Exception {
-    runTest(TestClassInline.class, true);
-  }
-}
diff --git a/src/test/java/com/android/tools/r8/ir/deterministic/TestClass.java b/src/test/java/com/android/tools/r8/ir/deterministic/TestClass.java
deleted file mode 100644
index 5bbfa51..0000000
--- a/src/test/java/com/android/tools/r8/ir/deterministic/TestClass.java
+++ /dev/null
@@ -1,70 +0,0 @@
-// 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.ir.deterministic;
-
-public class TestClass {
-
-  // This will be inlined, causing some of the calls below to go away providing more
-  // inlining opportunities.
-  public static boolean alwaysFalse() {
-    return false;
-  }
-
-  public static int a0() {
-    return b0();
-  }
-
-  public static int b0() {
-    if (alwaysFalse()) {
-      a0();
-      return 0;
-    }
-    return 1;
-  }
-
-  public static int a1() {
-    return b1();
-  }
-
-  public static int b1() {
-    if (alwaysFalse()) {
-      a1();
-      return 0;
-    }
-    return 1;
-  }
-
-  public static int a2() {
-    return b2();
-  }
-
-  public static int b2() {
-    return c2();
-  }
-
-  public static int c2() {
-    if (alwaysFalse()) {
-      a2();
-      return 0;
-    }
-    return 1;
-  }
-
-  public static int a3() {
-    return b3();
-  }
-
-  public static int b3() {
-    return c3();
-  }
-
-  public static int c3() {
-    if (alwaysFalse()) {
-      a3();
-      return 0;
-    }
-    return 1;
-  }
-}
diff --git a/src/test/java/com/android/tools/r8/ir/deterministic/TestClassInline.java b/src/test/java/com/android/tools/r8/ir/deterministic/TestClassInline.java
deleted file mode 100644
index aa50f02..0000000
--- a/src/test/java/com/android/tools/r8/ir/deterministic/TestClassInline.java
+++ /dev/null
@@ -1,24 +0,0 @@
-// 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.ir.deterministic;
-
-public class TestClassInline {
-
-  public static boolean alwaysFalse() {
-    return false;
-  }
-
-  public static int a() {
-    return b();
-  }
-
-  public static int b() {
-    if (alwaysFalse()) {
-      a();
-      return 0;
-    }
-    return 1;
-  }
-}
diff --git a/src/test/java/com/android/tools/r8/ir/deterministic/TestClassReturnsArgument.java b/src/test/java/com/android/tools/r8/ir/deterministic/TestClassReturnsArgument.java
deleted file mode 100644
index ac70401..0000000
--- a/src/test/java/com/android/tools/r8/ir/deterministic/TestClassReturnsArgument.java
+++ /dev/null
@@ -1,19 +0,0 @@
-// 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.ir.deterministic;
-
-import java.util.Random;
-
-public class TestClassReturnsArgument {
-
-  public static int a(int x) {
-    return b(new Random().nextInt());
-  }
-
-  public static int b(int x) {
-    a(1);
-    return x;
-  }
-}
diff --git a/src/test/java/com/android/tools/r8/ir/deterministic/TestClassReturnsConstant.java b/src/test/java/com/android/tools/r8/ir/deterministic/TestClassReturnsConstant.java
deleted file mode 100644
index 7d63f60..0000000
--- a/src/test/java/com/android/tools/r8/ir/deterministic/TestClassReturnsConstant.java
+++ /dev/null
@@ -1,19 +0,0 @@
-// 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.ir.deterministic;
-
-import java.util.Random;
-
-public class TestClassReturnsConstant {
-
-  public static int a(int x) {
-    return b(new Random().nextInt());
-  }
-
-  public static int b(int x) {
-    a(x);
-    return 1;
-  }
-}
diff --git a/third_party/gradle/gradle.tar.gz.sha1 b/third_party/gradle/gradle.tar.gz.sha1
index 008d84c..c9f900a 100644
--- a/third_party/gradle/gradle.tar.gz.sha1
+++ b/third_party/gradle/gradle.tar.gz.sha1
@@ -1 +1 @@
-1d118f48ff995b7eca95f3655293ea959779a6c0
\ No newline at end of file
+2d9bb7b50771ad8252cdcf83a1a9648af7eee837
\ No newline at end of file
diff --git a/tools/gradle.py b/tools/gradle.py
index 488dc87..14b5f34 100755
--- a/tools/gradle.py
+++ b/tools/gradle.py
@@ -14,6 +14,7 @@
 
 GRADLE_DIR = os.path.join(utils.REPO_ROOT, 'third_party', 'gradle')
 GRADLE_SHA1 = os.path.join(GRADLE_DIR, 'gradle.tar.gz.sha1')
+GRADLE_TGZ = os.path.join(GRADLE_DIR, 'gradle.tar.gz')
 if utils.IsWindows():
   GRADLE = os.path.join(GRADLE_DIR, 'gradle', 'bin', 'gradle.bat')
 else:
@@ -27,9 +28,12 @@
   sys.stdout.flush()
 
 def EnsureGradle():
-  if not os.path.exists(GRADLE):
-    # Bootstrap gradle, everything else is controlled using gradle.
+  if not os.path.exists(GRADLE) or os.path.getmtime(GRADLE_TGZ) < os.path.getmtime(GRADLE_SHA1):
+    # Bootstrap or update gradle, everything else is controlled using gradle.
     utils.DownloadFromGoogleCloudStorage(GRADLE_SHA1)
+    # Update the mtime of the tar file to make sure we do not run again unless
+    # there is an update.
+    os.utime(GRADLE_TGZ, None)
   else:
     print 'gradle.py: Gradle binary present'
 
diff --git a/tools/run_on_app.py b/tools/run_on_app.py
index d7db7fb..a091e1c 100755
--- a/tools/run_on_app.py
+++ b/tools/run_on_app.py
@@ -4,6 +4,7 @@
 # BSD-style license that can be found in the LICENSE file.
 
 from __future__ import print_function
+from glob import glob
 import optparse
 import os
 import sys
@@ -74,14 +75,18 @@
                     'the run.')
   result.add_option('--print-runtimeraw',
                     metavar='BENCHMARKNAME',
-                    help='Prints the line \'<BENCHMARKNAME>(RunTimeRaw):' +
-                         ' <elapsed> ms\' at the end where <elapsed> is' +
-                         ' the elapsed time in milliseconds.')
+                    help='Print the line \'<BENCHMARKNAME>(RunTimeRaw):' +
+                        ' <elapsed> ms\' at the end where <elapsed> is' +
+                        ' the elapsed time in milliseconds.')
   result.add_option('--print-memoryuse',
                     metavar='BENCHMARKNAME',
-                    help='Prints the line \'<BENCHMARKNAME>(MemoryUse):' +
-                         ' <mem>\' at the end where <mem> is the peak' +
-                         ' peak resident set size (VmHWM) in bytes.')
+                    help='Print the line \'<BENCHMARKNAME>(MemoryUse):' +
+                        ' <mem>\' at the end where <mem> is the peak' +
+                        ' peak resident set size (VmHWM) in bytes.')
+  result.add_option('--print-dexsegments',
+                    metavar='BENCHMARKNAME',
+                    help='Print the sizes of individual dex segments as ' +
+                        '\'<BENCHMARKNAME>-<segment>(CodeSize): <bytes>\'')
   return result.parse_args()
 
 # Most apps have the -printmapping and -printseeds in the Proguard
@@ -207,5 +212,9 @@
     print('{}(RunTimeRaw): {} ms'
         .format(options.print_runtimeraw, 1000.0 * (time.time() - t0)))
 
+  if options.print_dexsegments:
+    dex_files = glob(os.path.join(outdir, '*.dex'))
+    utils.print_dexsegments(options.print_dexsegments, dex_files)
+
 if __name__ == '__main__':
   sys.exit(main())
diff --git a/tools/run_proguard_dx_on_gmscore.py b/tools/run_proguard_dx_on_gmscore.py
index de716b0..06f56f9 100755
--- a/tools/run_proguard_dx_on_gmscore.py
+++ b/tools/run_proguard_dx_on_gmscore.py
@@ -6,6 +6,7 @@
 # Run ProGuard and the DX or CompatDX (= D8) tool on GmsCore V10.
 
 from __future__ import print_function
+from glob import glob
 from os import makedirs
 from os.path import exists, join
 from subprocess import check_call
@@ -37,18 +38,22 @@
       default = os.getcwd())
   parser.add_argument('--print-runtimeraw',
       metavar = 'BENCHMARKNAME',
-      help = 'Prints the line \'<BENCHMARKNAME>(RunTimeRaw): <elapsed>' +
+      help = 'Print the line \'<BENCHMARKNAME>(RunTimeRaw): <elapsed>' +
              ' ms\' at the end where <elapsed> is the elapsed time in' +
              ' milliseconds.')
   parser.add_argument('--print-memoryuse',
       metavar='BENCHMARKNAME',
-      help='Prints the line \'<BENCHMARKNAME>(MemoryUse):' +
+      help='Print the line \'<BENCHMARKNAME>(MemoryUse):' +
            ' <mem>\' at the end where <mem> is the peak' +
            ' peak resident set size (VmHWM) in bytes.')
   parser.add_argument('--compatdx',
       help = 'Use CompatDx (D8) instead of DX.',
       default = False,
       action = 'store_true')
+  parser.add_argument('--print-dexsegments',
+      metavar = 'BENCHMARKNAME',
+      help = 'Print the sizes of individual dex segments as ' +
+          '\'<BENCHMARKNAME>-<segment>(CodeSize): <bytes>\'')
   return parser.parse_args()
 
 def Main():
@@ -113,5 +118,9 @@
     print('{}(RunTimeRaw): {} ms'
         .format(options.print_runtimeraw, 1000.0 * (time.time() - t0)))
 
+  if options.print_dexsegments:
+    dex_files = glob(os.path.join(outdir, '*.dex'))
+    utils.print_dexsegments(options.print_dexsegments, dex_files)
+
 if __name__ == '__main__':
   sys.exit(Main())
diff --git a/tools/test_android_cts.py b/tools/test_android_cts.py
index 606611d..4ef8039 100755
--- a/tools/test_android_cts.py
+++ b/tools/test_android_cts.py
@@ -246,8 +246,7 @@
     print('Comparing test results to baseline:\n')
 
     passing_tests = consistently_passing_tests_from_test_results([results_xml])
-    baseline_results = \
-        [f for f in glob(join(CTS_BASELINE_FILES_DIR, '*.xml'))]
+    baseline_results = glob(join(CTS_BASELINE_FILES_DIR, '*.xml'))
     assert len(baseline_results) != 0
 
     passing_tests_in_baseline = \
diff --git a/tools/test_framework.py b/tools/test_framework.py
index 57279bf..04a12d3 100755
--- a/tools/test_framework.py
+++ b/tools/test_framework.py
@@ -35,9 +35,6 @@
     'goyt_160525751')
 FRAMEWORK_JAR = os.path.join('third_party', 'framework',
     'framework_160115954.jar')
-DEX_SEGMENTS_JAR = os.path.join(utils.REPO_ROOT, 'build', 'libs',
-    'dexsegments.jar')
-DEX_SEGMENTS_RESULT_PATTERN = re.compile('- ([^:]+): ([0-9]+)')
 MIN_SDK_VERSION = '24'
 
 def parse_arguments():
@@ -61,27 +58,6 @@
       action = 'store_true')
   return parser.parse_args()
 
-# Return a dictionary: {segment_name -> segments_size}
-def getDexSegmentSizes(dex_files):
-  assert len(dex_files) > 0
-  cmd = ['java', '-jar', DEX_SEGMENTS_JAR]
-  cmd.extend(dex_files)
-  utils.PrintCmd(cmd)
-  output = subprocess.check_output(cmd)
-
-  matches = DEX_SEGMENTS_RESULT_PATTERN.findall(output)
-
-  if matches is None or len(matches) == 0:
-    raise Exception('DexSegments failed to return any output for' \
-        ' these files: {}'.format(dex_files))
-
-  result = {}
-
-  for match in matches:
-    result[match[0]] = int(match[1])
-
-  return result
-
 def Main():
   args = parse_arguments()
 
@@ -136,9 +112,7 @@
     print('{}-Total(CodeSize): {}'
       .format(args.name, code_size))
 
-    for segment_name, size in getDexSegmentSizes(dex_files).items():
-      print('{}-{}(CodeSize): {}'
-          .format(args.name, segment_name, size))
+    utils.print_dexsegments(args.name, dex_files)
 
 if __name__ == '__main__':
   sys.exit(Main())
diff --git a/tools/utils.py b/tools/utils.py
index 2564adc..dfc35d7 100644
--- a/tools/utils.py
+++ b/tools/utils.py
@@ -15,6 +15,9 @@
 TOOLS_DIR = os.path.abspath(os.path.normpath(os.path.join(__file__, '..')))
 REPO_ROOT = os.path.realpath(os.path.join(TOOLS_DIR, '..'))
 MEMORY_USE_TMP_FILE = 'memory_use.tmp'
+DEX_SEGMENTS_JAR = os.path.join(REPO_ROOT, 'build', 'libs',
+    'dexsegments.jar')
+DEX_SEGMENTS_RESULT_PATTERN = re.compile('- ([^:]+): ([0-9]+)')
 
 def PrintCmd(s):
   if type(s) is list:
@@ -140,4 +143,30 @@
                   .format(unit))
   if result is None:
     raise Exception('No memory usage found in log: {}'.format(logfile))
-  return result
\ No newline at end of file
+  return result
+
+# Return a dictionary: {segment_name -> segments_size}
+def getDexSegmentSizes(dex_files):
+  assert len(dex_files) > 0
+  cmd = ['java', '-jar', DEX_SEGMENTS_JAR]
+  cmd.extend(dex_files)
+  PrintCmd(cmd)
+  output = subprocess.check_output(cmd)
+
+  matches = DEX_SEGMENTS_RESULT_PATTERN.findall(output)
+
+  if matches is None or len(matches) == 0:
+    raise Exception('DexSegments failed to return any output for' \
+        ' these files: {}'.format(dex_files))
+
+  result = {}
+
+  for match in matches:
+    result[match[0]] = int(match[1])
+
+  return result
+
+def print_dexsegments(prefix, dex_files):
+  for segment_name, size in getDexSegmentSizes(dex_files).items():
+    print('{}-{}(CodeSize): {}'
+        .format(prefix, segment_name, size))