diff --git a/infra/config/global/cr-buildbucket.cfg b/infra/config/global/cr-buildbucket.cfg
index a804d02..b42f30e 100644
--- a/infra/config/global/cr-buildbucket.cfg
+++ b/infra/config/global/cr-buildbucket.cfg
@@ -305,12 +305,23 @@
       mixins: "normal"
       recipe {
         properties: "run_on_apps:True"
+        properties: "recompilation:False"
+      }
+    }
+    builders {
+      name: "linux-run-on-as-app-recompilation"
+      mixins: "linux"
+      mixins: "normal"
+      recipe {
+        properties: "run_on_apps:True"
+        properties: "recompilation:True"
       }
     }
     builders {
       name: "linux-run-on-as-app_release"
       mixins: "linux"
       mixins: "normal"
+      execution_timeout_secs: 25200  # 7h
       recipe {
         properties: "run_on_apps:True"
       }
diff --git a/infra/config/global/luci-milo.cfg b/infra/config/global/luci-milo.cfg
index 30b9ede..7bdd5c2 100644
--- a/infra/config/global/luci-milo.cfg
+++ b/infra/config/global/luci-milo.cfg
@@ -61,6 +61,11 @@
     short_name: "apps"
   }
   builders {
+    name: "buildbucket/luci.r8.ci/linux-run-on-as-app-recompilation"
+    category: "R8"
+    short_name: "apps-rec"
+  }
+  builders {
     name: "buildbucket/luci.r8.ci/linux-jctf"
     category: "R8"
     short_name: "jctf"
diff --git a/infra/config/global/luci-notify.cfg b/infra/config/global/luci-notify.cfg
index 16015f2..bcd03ba 100644
--- a/infra/config/global/luci-notify.cfg
+++ b/infra/config/global/luci-notify.cfg
@@ -119,6 +119,11 @@
     repository: "https://r8.googlesource.com/r8"
   }
   builders {
+    name: "linux-run-on-as-app-recompilation"
+    bucket: "ci"
+    repository: "https://r8.googlesource.com/r8"
+  }
+  builders {
     name: "linux-run-on-as-app_release"
     bucket: "ci"
     repository: "https://r8.googlesource.com/r8"
diff --git a/infra/config/global/luci-scheduler.cfg b/infra/config/global/luci-scheduler.cfg
index c55893a..5383ff2 100644
--- a/infra/config/global/luci-scheduler.cfg
+++ b/infra/config/global/luci-scheduler.cfg
@@ -35,6 +35,7 @@
   triggers: "linux-android-8.1.0"
   triggers: "linux-android-9.0.0"
   triggers: "linux-run-on-as-app"
+  triggers: "linux-run-on-as-app-recompilation"
   triggers: "linux-internal"
   triggers: "linux-jctf"
   triggers: "r8cf-linux-jctf"
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 56f69f7..c75c2fd 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -56,6 +56,7 @@
 import com.android.tools.r8.shaking.AbstractMethodRemover;
 import com.android.tools.r8.shaking.AnnotationRemover;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.DefaultTreePrunerConfiguration;
 import com.android.tools.r8.shaking.DiscardedChecker;
 import com.android.tools.r8.shaking.Enqueuer;
 import com.android.tools.r8.shaking.EnqueuerFactory;
@@ -68,6 +69,7 @@
 import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
 import com.android.tools.r8.shaking.StaticClassMerger;
 import com.android.tools.r8.shaking.TreePruner;
+import com.android.tools.r8.shaking.TreePrunerConfiguration;
 import com.android.tools.r8.shaking.VerticalClassMerger;
 import com.android.tools.r8.shaking.WhyAreYouKeepingConsumer;
 import com.android.tools.r8.utils.AndroidApiLevel;
@@ -346,10 +348,11 @@
         if (options.isShrinking()) {
           // Mark dead proto extensions fields as neither being read nor written. This step must
           // run prior to the tree pruner.
-          appView.withGeneratedExtensionRegistryShrinker(GeneratedExtensionRegistryShrinker::run);
+          appView.withGeneratedExtensionRegistryShrinker(
+              shrinker -> shrinker.run(enqueuer.getMode()));
 
-          TreePruner pruner = new TreePruner(application, appView.withLiveness());
-          application = pruner.run();
+          TreePruner pruner = new TreePruner(appViewWithLiveness);
+          application = pruner.run(application);
 
           // Recompute the subtyping information.
           appView.setAppInfo(
@@ -630,10 +633,13 @@
           if (options.isShrinking()) {
             // Mark dead proto extensions fields as neither being read nor written. This step must
             // run prior to the tree pruner.
-            appView.withGeneratedExtensionRegistryShrinker(GeneratedExtensionRegistryShrinker::run);
+            TreePrunerConfiguration treePrunerConfiguration =
+                appView.withGeneratedExtensionRegistryShrinker(
+                    shrinker -> shrinker.run(enqueuer.getMode()),
+                    DefaultTreePrunerConfiguration.getInstance());
 
-            TreePruner pruner = new TreePruner(application, appViewWithLiveness);
-            application = pruner.run();
+            TreePruner pruner = new TreePruner(appViewWithLiveness, treePrunerConfiguration);
+            application = pruner.run(application);
             if (options.usageInformationConsumer != null) {
               ExceptionUtils.withFinishedResourceHandler(
                   options.reporter, options.usageInformationConsumer);
diff --git a/src/main/java/com/android/tools/r8/dex/ApplicationReader.java b/src/main/java/com/android/tools/r8/dex/ApplicationReader.java
index 4549d8e..122e1c8 100644
--- a/src/main/java/com/android/tools/r8/dex/ApplicationReader.java
+++ b/src/main/java/com/android/tools/r8/dex/ApplicationReader.java
@@ -10,6 +10,7 @@
 
 import com.android.tools.r8.ClassFileResourceProvider;
 import com.android.tools.r8.DataResourceProvider;
+import com.android.tools.r8.Diagnostic;
 import com.android.tools.r8.ProgramResource;
 import com.android.tools.r8.ProgramResource.Kind;
 import com.android.tools.r8.ProgramResourceProvider;
@@ -42,6 +43,8 @@
 import com.android.tools.r8.utils.Timing;
 import java.io.IOException;
 import java.io.InputStream;
+import java.nio.file.Files;
+import java.nio.file.Path;
 import java.nio.file.Paths;
 import java.util.ArrayList;
 import java.util.Collection;
@@ -59,7 +62,7 @@
   private final InternalOptions options;
   private final DexItemFactory itemFactory;
   private final Timing timing;
-  private AndroidApp inputApp;
+  private final AndroidApp inputApp;
 
   public interface ProgramClassConflictResolver {
     DexProgramClass resolveClassConflict(DexProgramClass a, DexProgramClass b);
@@ -107,9 +110,30 @@
       ProgramClassConflictResolver resolver)
       throws IOException, ExecutionException {
     assert verifyMainDexOptionsCompatible(inputApp, options);
+    Path dumpOutput = null;
+    boolean cleanDump = false;
     if (options.dumpInputToFile != null) {
-      inputApp = dumpInputToFile(inputApp, options);
-      throw options.reporter.fatalError("Dumped compilation inputs to: " + options.dumpInputToFile);
+      dumpOutput = Paths.get(options.dumpInputToFile);
+    } else if (options.dumpInputToDirectory != null) {
+      dumpOutput =
+          Paths.get(options.dumpInputToDirectory).resolve("dump" + System.nanoTime() + ".zip");
+    } else if (options.testing.dumpAll) {
+      cleanDump = true;
+      dumpOutput = Paths.get("/tmp").resolve("dump" + System.nanoTime() + ".zip");
+    }
+    if (dumpOutput != null) {
+      timing.begin("ApplicationReader.dump");
+      dumpInputToFile(inputApp, dumpOutput, options);
+      if (cleanDump) {
+        Files.delete(dumpOutput);
+      }
+      timing.end();
+      Diagnostic message = new StringDiagnostic("Dumped compilation inputs to: " + dumpOutput);
+      if (options.dumpInputToFile != null) {
+        throw options.reporter.fatalError(message);
+      } else if (!cleanDump) {
+        options.reporter.info(message);
+      }
     }
     timing.begin("DexApplication.read");
     final LazyLoadedDexApplication.Builder builder =
@@ -145,9 +169,8 @@
     return builder.build();
   }
 
-  private static AndroidApp dumpInputToFile(AndroidApp app, InternalOptions options) {
-    return app.dump(
-        Paths.get(options.dumpInputToFile), options.getProguardConfiguration(), options.reporter);
+  private static void dumpInputToFile(AndroidApp app, Path output, InternalOptions options) {
+    app.dump(output, options.getProguardConfiguration(), options.reporter);
   }
 
   private static boolean verifyMainDexOptionsCompatible(
diff --git a/src/main/java/com/android/tools/r8/dex/ClassesChecksum.java b/src/main/java/com/android/tools/r8/dex/ClassesChecksum.java
index 540502b..ffdb9a4 100644
--- a/src/main/java/com/android/tools/r8/dex/ClassesChecksum.java
+++ b/src/main/java/com/android/tools/r8/dex/ClassesChecksum.java
@@ -18,7 +18,7 @@
   private static final char PREFIX_CHAR1 = '~';
   private static final char PREFIX_CHAR2 = '~';
 
-  private Object2LongMap<String> dictionary = null;
+  private final Object2LongMap<String> dictionary = new Object2LongOpenHashMap<>();
 
   public ClassesChecksum() {
     assert PREFIX.length() == 3;
@@ -27,14 +27,7 @@
     assert PREFIX.charAt(2) == PREFIX_CHAR2;
   }
 
-  private void ensureMap() {
-    if (dictionary == null) {
-      dictionary = new Object2LongOpenHashMap<>();
-    }
-  }
-
   private void append(JsonObject json) {
-    ensureMap();
     json.entrySet()
         .forEach(
             entry ->
@@ -42,7 +35,6 @@
   }
 
   public void addChecksum(String classDescriptor, long crc) {
-    ensureMap();
     dictionary.put(classDescriptor, crc);
   }
 
@@ -86,14 +78,15 @@
    * @param string String to check if definitely preceded the checksum marker.
    * @return If the string passed definitely preceded the checksum marker
    */
-  public static boolean definitelyPreceedChecksumMarker(DexString string) {
+  public static boolean definitelyPrecedesChecksumMarker(DexString string) {
     try {
       assert PREFIX.length() == 3;
-      char[] prefix = string.decodePrefix(3);
-      return prefix.length == 0
-          || (prefix.length == 1 && prefix[0] <= PREFIX_CHAR0)
-          || (prefix.length == 2 && prefix[0] == PREFIX_CHAR0 && prefix[1] <= PREFIX_CHAR1)
-          || (prefix.length == 3
+      char[] prefix = new char[PREFIX.length()];
+      int prefixLength = string.decodePrefix(prefix);
+      return prefixLength == 0
+          || (prefixLength == 1 && prefix[0] <= PREFIX_CHAR0)
+          || (prefixLength == 2 && prefix[0] == PREFIX_CHAR0 && prefix[1] <= PREFIX_CHAR1)
+          || (prefixLength == 3
               && prefix[0] == PREFIX_CHAR0
               && prefix[1] == PREFIX_CHAR1
               && prefix[2] < PREFIX_CHAR2);
diff --git a/src/main/java/com/android/tools/r8/dex/DexParser.java b/src/main/java/com/android/tools/r8/dex/DexParser.java
index 5989981..20678fe 100644
--- a/src/main/java/com/android/tools/r8/dex/DexParser.java
+++ b/src/main/java/com/android/tools/r8/dex/DexParser.java
@@ -64,8 +64,8 @@
 import com.android.tools.r8.utils.Pair;
 import com.google.common.io.ByteStreams;
 import it.unimi.dsi.fastutil.ints.Int2IntArrayMap;
-import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
-import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
 import it.unimi.dsi.fastutil.objects.Object2LongMap;
 import java.io.ByteArrayOutputStream;
 import java.io.IOException;
@@ -117,10 +117,10 @@
   private OffsetToObjectMapping indexedItems = new OffsetToObjectMapping();
 
   // Mapping from offset to code item;
-  private Int2ObjectMap<DexCode> codes = new Int2ObjectOpenHashMap<>();
+  private Int2ReferenceMap<DexCode> codes = new Int2ReferenceOpenHashMap<>();
 
   // Mapping from offset to dex item;
-  private Int2ObjectMap<Object> offsetMap = new Int2ObjectOpenHashMap<>();
+  private Int2ReferenceMap<Object> offsetMap = new Int2ReferenceOpenHashMap<>();
 
   // Factory to canonicalize certain dexitems.
   private final DexItemFactory dexItemFactory;
@@ -143,7 +143,7 @@
     }
 
     if (codes == null) {
-      codes = new Int2ObjectOpenHashMap<>();
+      codes = new Int2ReferenceOpenHashMap<>();
     }
 
     if (classKind == ClassKind.LIBRARY) {
@@ -950,7 +950,7 @@
     ClassesChecksum parsedChecksums = new ClassesChecksum();
     for (int i = stringIDs.length - 1; i >= 0; i--) {
       DexString value = indexedItems.getString(i);
-      if (ClassesChecksum.definitelyPreceedChecksumMarker(value)) {
+      if (ClassesChecksum.definitelyPrecedesChecksumMarker(value)) {
         break;
       }
       parsedChecksums.tryParseAndAppend(value);
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfo.java b/src/main/java/com/android/tools/r8/graph/AppInfo.java
index d569852..139a285 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfo.java
@@ -641,11 +641,6 @@
     return null;
   }
 
-  public void registerNewType(DexType newType, DexType superType) {
-    // We do not track subtyping relationships in the basic AppInfo. So do nothing.
-    assert checkIfObsolete();
-  }
-
   public boolean isInMainDexList(DexType type) {
     assert checkIfObsolete();
     return app.mainDexList.contains(type);
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
index faa25c2..fa4cea3 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
@@ -3,11 +3,14 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.graph;
 
+import static com.android.tools.r8.ir.desugar.LambdaRewriter.LAMBDA_GROUP_CLASS_NAME_PREFIX;
+
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.ir.analysis.type.ClassTypeLatticeElement;
 import com.android.tools.r8.ir.desugar.LambdaDescriptor;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.SetUtils;
+import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
@@ -48,7 +51,7 @@
     // Caching what interfaces this type is implementing. This includes super-interface hierarchy.
     Set<DexType> implementedInterfaces = null;
 
-    public TypeInfo(DexType type) {
+    TypeInfo(DexType type) {
       this.type = type;
     }
 
@@ -78,7 +81,7 @@
       }
     }
 
-    public synchronized void addDirectSubtype(TypeInfo subtypeInfo) {
+    synchronized void addDirectSubtype(TypeInfo subtypeInfo) {
       assert hierarchyLevel != UNKNOWN_LEVEL;
       ensureDirectSubTypeSet();
       directSubtypes.add(subtypeInfo.type);
@@ -149,6 +152,28 @@
   @Override
   public void addSynthesizedClass(DexProgramClass synthesizedClass) {
     super.addSynthesizedClass(synthesizedClass);
+    // Register synthesized type, which has two side effects:
+    //   1) Set the hierarchy level of synthesized type based on that of its super type,
+    //   2) Register the synthesized type as a subtype of the supertype.
+    //
+    // The first one makes method resolutions on that synthesized class free from assertion errors
+    // about unknown hierarchy level.
+    //
+    // For the second one, note that such addition is synchronized, but the retrieval of direct
+    // subtypes isn't. Thus, there is a chance of race conditions: utils that check/iterate direct
+    // subtypes, e.g., allImmediateSubtypes, hasSubTypes, etc., may not be able to see this new
+    // synthesized class. However, in practice, this would be okay because, in most cases,
+    // synthesized class's super type is Object, which in general has other subtypes in any way.
+    // Also, iterating all subtypes of Object usually happens before/after IR processing, i.e., as
+    // part of structural changes, such as bottom-up traversal to collect all method signatures,
+    // which are free from such race conditions. Another exceptional case is synthesized classes
+    // whose synthesis is isolated from IR processing. For example, lambda group class that merges
+    // lambdas with the same interface are synthesized/finalized even after post processing of IRs.
+    assert synthesizedClass.superType == dexItemFactory().objectType
+            || synthesizedClass.type.toString().contains(LAMBDA_GROUP_CLASS_NAME_PREFIX)
+        : "Make sure retrieval and iteration of sub types of `" + synthesizedClass.superType
+            + "` is guaranteed to be thread safe and able to see `" + synthesizedClass + "`";
+    registerNewType(synthesizedClass.type, synthesizedClass.superType);
 
     // TODO(b/129458850): Remove when we no longer synthesize classes on-the-fly.
     Set<DexType> visited = SetUtils.newIdentityHashSet(synthesizedClass.allImmediateSupertypes());
@@ -217,8 +242,11 @@
     return typeInfo.computeIfAbsent(type, TypeInfo::new);
   }
 
-  private void populateAllSuperTypes(Map<DexType, Set<DexType>> map, DexType holder,
-      DexClass baseClass, Function<DexType, DexClass> definitions) {
+  private void populateAllSuperTypes(
+      Map<DexType, Set<DexType>> map,
+      DexType holder,
+      DexClass baseClass,
+      Function<DexType, DexClass> definitions) {
     DexClass holderClass = definitions.apply(holder);
     // Skip if no corresponding class is found.
     if (holderClass != null) {
@@ -435,13 +463,17 @@
             || bootstrapMethod.asMethod() == dexItemFactory().stringConcatMethod);
   }
 
-  @Override
-  public void registerNewType(DexType newType, DexType superType) {
+  private void registerNewType(DexType newType, DexType superType) {
     assert checkIfObsolete();
     // Register the relationship between this type and its superType.
     getTypeInfo(superType).addDirectSubtype(getTypeInfo(newType));
   }
 
+  @VisibleForTesting
+  public void registerNewTypeForTesting(DexType newType, DexType superType) {
+    registerNewType(newType, superType);
+  }
+
   @Override
   public boolean hasSubtyping() {
     assert checkIfObsolete();
@@ -495,7 +527,7 @@
 
   // Depending on optimizations, conservative answer of subtype relation may vary.
   // Pass different `orElse` in that case.
-  public boolean isStrictSubtypeOf(DexType subtype, DexType supertype, boolean orElse) {
+  private boolean isStrictSubtypeOf(DexType subtype, DexType supertype, boolean orElse) {
     if (subtype == supertype) {
       return false;
     }
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index 776cbaf..b67931f 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -46,10 +46,8 @@
 import com.android.tools.r8.ir.optimize.Inliner.Reason;
 import com.android.tools.r8.ir.optimize.NestUtils;
 import com.android.tools.r8.ir.optimize.info.CallSiteOptimizationInfo;
-import com.android.tools.r8.ir.optimize.info.DefaultCallSiteOptimizationInfo;
 import com.android.tools.r8.ir.optimize.info.DefaultMethodOptimizationInfo;
 import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
-import com.android.tools.r8.ir.optimize.info.MutableCallSiteOptimizationInfo;
 import com.android.tools.r8.ir.optimize.info.UpdatableMethodOptimizationInfo;
 import com.android.tools.r8.ir.optimize.inliner.WhyAreYouNotInliningReporter;
 import com.android.tools.r8.ir.regalloc.RegisterAllocator;
@@ -134,8 +132,7 @@
   //   we need to maintain a set of states with (potentially different) contexts.
   private CompilationState compilationState = CompilationState.NOT_PROCESSED;
   private MethodOptimizationInfo optimizationInfo = DefaultMethodOptimizationInfo.DEFAULT_INSTANCE;
-  private CallSiteOptimizationInfo callSiteOptimizationInfo =
-      DefaultCallSiteOptimizationInfo.getInstance();
+  private CallSiteOptimizationInfo callSiteOptimizationInfo = CallSiteOptimizationInfo.BOTTOM;
   private int classFileVersion = -1;
 
   private DexEncodedMethod defaultInterfaceMethodImplementation = null;
@@ -1167,22 +1164,15 @@
     optimizationInfo = info;
   }
 
-  public CallSiteOptimizationInfo getCallSiteOptimizationInfo() {
+  public synchronized CallSiteOptimizationInfo getCallSiteOptimizationInfo() {
     checkIfObsolete();
     return callSiteOptimizationInfo;
   }
 
-  public synchronized MutableCallSiteOptimizationInfo getMutableCallSiteOptimizationInfo(
-      AppView<?> appView) {
+  public synchronized void joinCallSiteOptimizationInfo(
+      CallSiteOptimizationInfo other, AppView<?> appView) {
     checkIfObsolete();
-    if (callSiteOptimizationInfo.isDefaultCallSiteOptimizationInfo()) {
-      MutableCallSiteOptimizationInfo mutableOptimizationInfo =
-          new MutableCallSiteOptimizationInfo(this);
-      callSiteOptimizationInfo = mutableOptimizationInfo;
-      return mutableOptimizationInfo;
-    }
-    assert callSiteOptimizationInfo.isMutableCallSiteOptimizationInfo();
-    return callSiteOptimizationInfo.asMutableCallSiteOptimizationInfo();
+    callSiteOptimizationInfo = callSiteOptimizationInfo.join(other, appView, this);
   }
 
   public void copyMetadata(DexEncodedMethod from) {
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 dbeb35f..c7e1199 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -37,9 +37,9 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Streams;
-import it.unimi.dsi.fastutil.ints.Int2ObjectArrayMap;
-import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
-import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceArrayMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
@@ -69,11 +69,11 @@
       new ConcurrentHashMap<>();
 
   // DexDebugEvent Canonicalization.
-  private final Int2ObjectMap<AdvanceLine> advanceLines = new Int2ObjectOpenHashMap<>();
-  private final Int2ObjectMap<AdvancePC> advancePCs = new Int2ObjectOpenHashMap<>();
-  private final Int2ObjectMap<Default> defaults = new Int2ObjectOpenHashMap<>();
-  private final Int2ObjectMap<EndLocal> endLocals = new Int2ObjectOpenHashMap<>();
-  private final Int2ObjectMap<RestartLocal> restartLocals = new Int2ObjectOpenHashMap<>();
+  private final Int2ReferenceMap<AdvanceLine> advanceLines = new Int2ReferenceOpenHashMap<>();
+  private final Int2ReferenceMap<AdvancePC> advancePCs = new Int2ReferenceOpenHashMap<>();
+  private final Int2ReferenceMap<Default> defaults = new Int2ReferenceOpenHashMap<>();
+  private final Int2ReferenceMap<EndLocal> endLocals = new Int2ReferenceOpenHashMap<>();
+  private final Int2ReferenceMap<RestartLocal> restartLocals = new Int2ReferenceOpenHashMap<>();
   private final SetEpilogueBegin setEpilogueBegin = new SetEpilogueBegin();
   private final SetPrologueEnd setPrologueEnd = new SetPrologueEnd();
   private final Map<DexString, SetFile> setFiles = new HashMap<>();
@@ -1312,7 +1312,7 @@
 
   private static DexType[] applyClassMappingToDexTypes(
       DexType[] types, Function<DexType, DexType> mapping) {
-    Map<Integer, DexType> changed = new Int2ObjectArrayMap<>();
+    Map<Integer, DexType> changed = new Int2ReferenceArrayMap<>();
     for (int i = 0; i < types.length; i++) {
       DexType applied = mapping.apply(types[i]);
       if (applied != types[i]) {
diff --git a/src/main/java/com/android/tools/r8/graph/DexString.java b/src/main/java/com/android/tools/r8/graph/DexString.java
index a6591b4..131cee6 100644
--- a/src/main/java/com/android/tools/r8/graph/DexString.java
+++ b/src/main/java/com/android/tools/r8/graph/DexString.java
@@ -111,66 +111,35 @@
     return result;
   }
 
-  // Inspired from /dex/src/main/java/com/android/dex/Mutf8.java
   private String decode() throws UTFDataFormatException {
-    int s = 0;
-    int p = 0;
     char[] out = new char[size];
-    while (true) {
-      char a = (char) (content[p++] & 0xff);
-      if (a == 0) {
-        return new String(out, 0, s);
-      }
-      out[s] = a;
-      if (a < '\u0080') {
-        s++;
-      } else if ((a & 0xe0) == 0xc0) {
-        int b = content[p++] & 0xff;
-        if ((b & 0xC0) != 0x80) {
-          throw new UTFDataFormatException("bad second byte");
-        }
-        out[s++] = (char) (((a & 0x1F) << 6) | (b & 0x3F));
-      } else if ((a & 0xf0) == 0xe0) {
-        int b = content[p++] & 0xff;
-        int c = content[p++] & 0xff;
-        if (((b & 0xC0) != 0x80) || ((c & 0xC0) != 0x80)) {
-          throw new UTFDataFormatException("bad second or third byte");
-        }
-        out[s++] = (char) (((a & 0x0F) << 12) | ((b & 0x3F) << 6) | (c & 0x3F));
-      } else {
-        throw new UTFDataFormatException("bad byte");
-      }
-    }
+    int decodedLength = decodePrefix(out);
+    return new String(out, 0, decodedLength);
   }
 
-  public char[] decodePrefix(int prefixLength) throws UTFDataFormatException {
+  // Inspired from /dex/src/main/java/com/android/dex/Mutf8.java
+  public int decodePrefix(char[] out) throws UTFDataFormatException {
     int s = 0;
     int p = 0;
-    char[] out = new char[prefixLength];
+    int prefixLength = out.length;
     while (true) {
       char a = (char) (content[p++] & 0xff);
       if (a == 0) {
-        if (s == prefixLength) {
-          return out;
-        }
-        char[] result = new char[s];
-        System.arraycopy(out, 0, result, 0, s);
-        return result;
+        return s;
       }
       out[s] = a;
       if (a < '\u0080') {
-        s++;
-        if (s == prefixLength) {
-          return out;
+        if (++s == prefixLength) {
+          return s;
         }
       } else if ((a & 0xe0) == 0xc0) {
         int b = content[p++] & 0xff;
         if ((b & 0xC0) != 0x80) {
           throw new UTFDataFormatException("bad second byte");
         }
-        out[s++] = (char) (((a & 0x1F) << 6) | (b & 0x3F));
-        if (s == prefixLength) {
-          return out;
+        out[s] = (char) (((a & 0x1F) << 6) | (b & 0x3F));
+        if (++s == prefixLength) {
+          return s;
         }
       } else if ((a & 0xf0) == 0xe0) {
         int b = content[p++] & 0xff;
@@ -178,9 +147,9 @@
         if (((b & 0xC0) != 0x80) || ((c & 0xC0) != 0x80)) {
           throw new UTFDataFormatException("bad second or third byte");
         }
-        out[s++] = (char) (((a & 0x0F) << 12) | ((b & 0x3F) << 6) | (c & 0x3F));
-        if (s == prefixLength) {
-          return out;
+        out[s] = (char) (((a & 0x0F) << 12) | ((b & 0x3F) << 6) | (c & 0x3F));
+        if (++s == prefixLength) {
+          return s;
         }
       } else {
         throw new UTFDataFormatException("bad byte");
diff --git a/src/main/java/com/android/tools/r8/graph/DexValue.java b/src/main/java/com/android/tools/r8/graph/DexValue.java
index af70929..cbce2db 100644
--- a/src/main/java/com/android/tools/r8/graph/DexValue.java
+++ b/src/main/java/com/android/tools/r8/graph/DexValue.java
@@ -25,6 +25,7 @@
 import org.objectweb.asm.Type;
 
 public abstract class DexValue extends DexItem {
+
   public static final DexValue[] EMPTY_ARRAY = {};
 
   public static final UnknownDexValue UNKNOWN = UnknownDexValue.UNKNOWN;
@@ -72,6 +73,14 @@
     return false;
   }
 
+  public boolean isDexValueInt() {
+    return false;
+  }
+
+  public DexValueInt asDexValueInt() {
+    return null;
+  }
+
   public static DexValue fromAsmBootstrapArgument(
       Object value, JarApplicationReader application, DexType clazz) {
     if (value instanceof Integer) {
@@ -473,6 +482,16 @@
     }
 
     @Override
+    public boolean isDexValueInt() {
+      return true;
+    }
+
+    @Override
+    public DexValueInt asDexValueInt() {
+      return this;
+    }
+
+    @Override
     public Object asAsmEncodedObject() {
       return Integer.valueOf(value);
     }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java
index 624cf90..a5fbaaf 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java
@@ -14,19 +14,29 @@
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.FieldAccessInfo;
 import com.android.tools.r8.graph.FieldAccessInfoCollection;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.IRCodeUtils;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.StaticPut;
 import com.android.tools.r8.ir.conversion.IRConverter;
 import com.android.tools.r8.ir.conversion.OneTimeMethodProcessor;
 import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackIgnore;
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.DefaultTreePrunerConfiguration;
+import com.android.tools.r8.shaking.Enqueuer;
+import com.android.tools.r8.shaking.TreePrunerConfiguration;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.FileUtils;
 import com.google.common.base.Predicates;
 import com.google.common.collect.Sets;
 import java.io.IOException;
 import java.nio.file.Path;
+import java.util.ArrayList;
+import java.util.List;
 import java.util.Set;
 import java.util.function.Consumer;
 import java.util.function.Predicate;
@@ -66,6 +76,7 @@
   private final AppView<AppInfoWithLiveness> appView;
   private final ProtoReferences references;
 
+  private final Set<DexType> classesWithRemovedExtensionFields = Sets.newIdentityHashSet();
   private final Set<DexField> removedExtensionFields = Sets.newIdentityHashSet();
 
   GeneratedExtensionRegistryShrinker(
@@ -79,9 +90,63 @@
    * Will be run after tree shaking. This populates the set {@link #removedExtensionFields}. This
    * set is used by the member value propagation, which rewrites all reads of these fields by
    * const-null.
+   *
+   * <p>For the second round of tree pruning, this method will return a non-default {@link
+   * TreePrunerConfiguration} that specifies that all fields that are only referenced from a {@code
+   * findLiteExtensionByNumber()} method should be removed. This is safe because we will revisit all
+   * of these methods and replace the reads of these fields by null.
    */
-  public void run() {
-    forEachDeadProtoExtensionField(removedExtensionFields::add);
+  public TreePrunerConfiguration run(Enqueuer.Mode mode) {
+    forEachDeadProtoExtensionField(this::recordDeadProtoExtensionField);
+    return createTreePrunerConfiguration(mode);
+  }
+
+  private void recordDeadProtoExtensionField(DexField field) {
+    classesWithRemovedExtensionFields.add(field.holder);
+    removedExtensionFields.add(field);
+  }
+
+  private TreePrunerConfiguration createTreePrunerConfiguration(Enqueuer.Mode mode) {
+    if (mode.isFinalTreeShaking()) {
+      return new DefaultTreePrunerConfiguration() {
+
+        @Override
+        public boolean isReachableOrReferencedField(
+            AppInfoWithLiveness appInfo, DexEncodedField field) {
+          return !wasRemoved(field.field) && super.isReachableOrReferencedField(appInfo, field);
+        }
+      };
+    }
+    return DefaultTreePrunerConfiguration.getInstance();
+  }
+
+  /**
+   * If {@param method} is a class initializer that initializes a dead proto extension field, then
+   * forcefully remove the field assignment and all the code that contributes to the initialization
+   * of the value of the field assignment.
+   */
+  public void rewriteCode(DexEncodedMethod method, IRCode code) {
+    if (method.isClassInitializer()
+        && classesWithRemovedExtensionFields.contains(method.method.holder)
+        && code.metadata().mayHaveStaticPut()) {
+      rewriteClassInitializer(code);
+    }
+  }
+
+  private void rewriteClassInitializer(IRCode code) {
+    List<StaticPut> toBeRemoved = new ArrayList<>();
+    for (StaticPut staticPut : code.<StaticPut>instructions(Instruction::isStaticPut)) {
+      if (removedExtensionFields.contains(staticPut.getField())) {
+        toBeRemoved.add(staticPut);
+      }
+    }
+    for (StaticPut instruction : toBeRemoved) {
+      if (!instruction.hasBlock()) {
+        // Already removed.
+        continue;
+      }
+      IRCodeUtils.removeInstructionAndTransitiveInputsIfNotUsed(code, instruction);
+    }
   }
 
   public boolean wasRemoved(DexField field) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCodeUtils.java b/src/main/java/com/android/tools/r8/ir/code/IRCodeUtils.java
new file mode 100644
index 0000000..dfc3f0e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCodeUtils.java
@@ -0,0 +1,60 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.code;
+
+import com.android.tools.r8.utils.DequeUtils;
+import com.google.common.collect.Sets;
+import java.util.Deque;
+import java.util.Set;
+
+public class IRCodeUtils {
+
+  /**
+   * Removes the given instruction and all the instructions that are used to define the in-values of
+   * the given instruction, even if the instructions may have side effects (!).
+   *
+   * <p>Use with caution!
+   */
+  public static void removeInstructionAndTransitiveInputsIfNotUsed(
+      IRCode code, Instruction instruction) {
+    Set<InstructionOrPhi> removed = Sets.newIdentityHashSet();
+    Deque<InstructionOrPhi> worklist = DequeUtils.newArrayDeque(instruction);
+    while (!worklist.isEmpty()) {
+      InstructionOrPhi instructionOrPhi = worklist.removeFirst();
+      if (removed.contains(instructionOrPhi)) {
+        // Already removed.
+        continue;
+      }
+      if (instructionOrPhi.isPhi()) {
+        Phi current = instructionOrPhi.asPhi();
+        if (!current.hasUsers() && !current.hasDebugUsers()) {
+          boolean hasOtherPhiUserThanSelf = false;
+          for (Phi phiUser : current.uniquePhiUsers()) {
+            if (phiUser != current) {
+              hasOtherPhiUserThanSelf = true;
+              break;
+            }
+          }
+          if (!hasOtherPhiUserThanSelf) {
+            current.removeDeadPhi();
+            for (Value operand : current.getOperands()) {
+              worklist.add(operand.isPhi() ? operand.asPhi() : operand.definition);
+            }
+            removed.add(current);
+          }
+        }
+      } else {
+        Instruction current = instructionOrPhi.asInstruction();
+        if (!current.hasOutValue() || !current.outValue().hasAnyUsers()) {
+          current.getBlock().listIterator(code, current).removeOrReplaceByDebugLocalRead();
+          for (Value inValue : current.inValues()) {
+            worklist.add(inValue.isPhi() ? inValue.asPhi() : inValue.definition);
+          }
+          removed.add(current);
+        }
+      }
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index 1129616..8836361 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -604,6 +604,11 @@
     return true;
   }
 
+  @Override
+  public Instruction asInstruction() {
+    return this;
+  }
+
   public boolean isArrayGet() {
     return false;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstructionOrPhi.java b/src/main/java/com/android/tools/r8/ir/code/InstructionOrPhi.java
index 10110a0..e9a5347 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstructionOrPhi.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstructionOrPhi.java
@@ -10,7 +10,15 @@
     return false;
   }
 
+  default Instruction asInstruction() {
+    return null;
+  }
+
   default boolean isPhi() {
     return false;
   }
+
+  default Phi asPhi() {
+    return null;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Phi.java b/src/main/java/com/android/tools/r8/ir/code/Phi.java
index 47eb9d4..3252d67 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Phi.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Phi.java
@@ -224,11 +224,11 @@
     return true;
   }
 
-  public void removeTrivialPhi() {
-    removeTrivialPhi(null, null);
+  public boolean removeTrivialPhi() {
+    return removeTrivialPhi(null, null);
   }
 
-  public void removeTrivialPhi(IRBuilder builder, Set<Value> affectedValues) {
+  public boolean removeTrivialPhi(IRBuilder builder, Set<Value> affectedValues) {
     Value same = null;
     for (Value op : operands) {
       if (op == same || op == this) {
@@ -238,7 +238,7 @@
       if (same != null) {
         // Merged at least two values and is therefore not trivial.
         assert !isTrivialPhi();
-        return;
+        return false;
       }
       same = op;
     }
@@ -247,7 +247,7 @@
       // When doing if-simplification we remove blocks and we can end up with cyclic phis
       // of the form v1 = phi(v1, v1) in dead blocks. If we encounter that case we just
       // leave the phi in there and check at the end that there are no trivial phis.
-      return;
+      return false;
     }
     // Ensure that the value that replaces this phi is constrained to the type of this phi.
     if (builder != null && typeLattice.isPreciseType() && !typeLattice.isBottom()) {
@@ -286,6 +286,7 @@
     }
     // Get rid of the phi itself.
     block.removePhi(this);
+    return true;
   }
 
   public void removeDeadPhi() {
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CallGraphBuilderBase.java b/src/main/java/com/android/tools/r8/ir/conversion/CallGraphBuilderBase.java
index 1e0a60d..6af3446 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CallGraphBuilderBase.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CallGraphBuilderBase.java
@@ -330,7 +330,6 @@
     // Mapping from callee to the set of callers that were removed from the callee.
     private Map<Node, Set<Node>> removedEdges = new IdentityHashMap<>();
 
-    private int currentDepth = 0;
     private int maxDepth = 0;
 
     CycleEliminator(Collection<Node> nodes, InternalOptions options) {
@@ -345,10 +344,8 @@
 
     CycleEliminationResult breakCycles() {
       // Break cycles in this call graph by removing edges causing cycles.
-      for (Node node : nodes) {
-        assert currentDepth == 0;
-        traverse(node);
-      }
+      traverse();
+
       CycleEliminationResult result = new CycleEliminationResult(removedEdges);
       if (Log.ENABLED) {
         Log.info(getClass(), "# call graph cycles broken: %s", result.numberOfRemovedEdges());
@@ -359,7 +356,6 @@
     }
 
     private void reset() {
-      assert currentDepth == 0;
       assert stack.isEmpty();
       assert stackSet.isEmpty();
       marked.clear();
@@ -367,41 +363,114 @@
       removedEdges = new IdentityHashMap<>();
     }
 
-    private void traverse(Node node) {
-      if (Log.ENABLED) {
-        if (currentDepth > maxDepth) {
-          maxDepth = currentDepth;
+    private static class WorkItem {
+      boolean isNode() {
+        return false;
+      }
+
+      NodeWorkItem asNode() {
+        return null;
+      }
+
+      boolean isIterator() {
+        return false;
+      }
+
+      IteratorWorkItem asIterator() {
+        return null;
+      }
+    }
+
+    private static class NodeWorkItem extends WorkItem {
+      private final Node node;
+
+      NodeWorkItem(Node node) {
+        this.node = node;
+      }
+
+      @Override
+      boolean isNode() {
+        return true;
+      }
+
+      @Override
+      NodeWorkItem asNode() {
+        return this;
+      }
+    }
+
+    private static class IteratorWorkItem extends WorkItem {
+      private final Node caller;
+      private final Iterator<Node> callees;
+
+      IteratorWorkItem(Node caller, Iterator<Node> callees) {
+        this.caller = caller;
+        this.callees = callees;
+      }
+
+      @Override
+      boolean isIterator() {
+        return true;
+      }
+
+      @Override
+      IteratorWorkItem asIterator() {
+        return this;
+      }
+    }
+
+    private void traverse() {
+      Deque<WorkItem> workItems = new ArrayDeque<>(nodes.size());
+      for (Node node : nodes) {
+        workItems.addLast(new NodeWorkItem(node));
+      }
+      while (!workItems.isEmpty()) {
+        WorkItem workItem = workItems.removeFirst();
+        if (workItem.isNode()) {
+          Node node = workItem.asNode().node;
+          if (Log.ENABLED) {
+            if (stack.size() > maxDepth) {
+              maxDepth = stack.size();
+            }
+          }
+
+          if (marked.contains(node)) {
+            // Already visited all nodes that can be reached from this node.
+            continue;
+          }
+
+          push(node);
+
+          // The callees must be sorted before calling traverse recursively. This ensures that
+          // cycles are broken the same way across multiple compilations.
+          Collection<Node> callees = node.getCalleesWithDeterministicOrder();
+
+          if (options.testing.nondeterministicCycleElimination) {
+            callees = reorderNodes(new ArrayList<>(callees));
+          }
+          workItems.addFirst(new IteratorWorkItem(node, callees.iterator()));
+        } else {
+          assert workItem.isIterator();
+          IteratorWorkItem iteratorWorkItem = workItem.asIterator();
+          Node newCaller = iterateCallees(iteratorWorkItem.callees, iteratorWorkItem.caller);
+          if (newCaller != null) {
+            // We did not finish the work on this iterator, so add it again.
+            workItems.addFirst(iteratorWorkItem);
+            workItems.addFirst(new NodeWorkItem(newCaller));
+          } else {
+            assert !iteratorWorkItem.callees.hasNext();
+            pop(iteratorWorkItem.caller);
+            marked.add(iteratorWorkItem.caller);
+          }
         }
       }
+    }
 
-      if (marked.contains(node)) {
-        // Already visited all nodes that can be reached from this node.
-        return;
-      }
-
-      push(node);
-
-      // The callees must be sorted before calling traverse recursively. This ensures that cycles
-      // are broken the same way across multiple compilations.
-      Collection<Node> callees = node.getCalleesWithDeterministicOrder();
-
-      if (options.testing.nondeterministicCycleElimination) {
-        callees = reorderNodes(new ArrayList<>(callees));
-      }
-
-      Iterator<Node> calleeIterator = callees.iterator();
+    private Node iterateCallees(Iterator<Node> calleeIterator, Node node) {
       while (calleeIterator.hasNext()) {
         Node callee = calleeIterator.next();
-
-        // If we've exceeded the depth threshold, then treat it as if we have found a cycle. This
-        // ensures that we won't run into stack overflows when the call graph contains large call
-        // chains. This should have a negligible impact on code size as long as the threshold is
-        // large enough.
         boolean foundCycle = stackSet.contains(callee);
-        boolean thresholdExceeded =
-            currentDepth >= options.callGraphCycleEliminatorMaxDepthThreshold
-                && edgeRemovalIsSafe(node, callee);
-        if (foundCycle || thresholdExceeded) {
+        if (foundCycle) {
           // Found a cycle that needs to be eliminated.
           if (edgeRemovalIsSafe(node, callee)) {
             // Break the cycle by removing the edge node->callee.
@@ -461,13 +530,10 @@
             recoverStack(cycle);
           }
         } else {
-          currentDepth++;
-          traverse(callee);
-          currentDepth--;
+          return callee;
         }
       }
-      pop(node);
-      marked.add(node);
+      return null;
     }
 
     private void push(Node node) {
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java b/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java
index 6603015..28e95f8 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java
@@ -3,7 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.conversion;
 
-import static it.unimi.dsi.fastutil.ints.Int2ObjectSortedMaps.emptyMap;
+import static it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMaps.emptyMap;
 
 import com.android.tools.r8.cf.code.CfFrame;
 import com.android.tools.r8.cf.code.CfFrame.FrameType;
@@ -36,9 +36,9 @@
 import com.android.tools.r8.ir.conversion.IRBuilder.BlockInfo;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.InternalOutputMode;
-import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
-import it.unimi.dsi.fastutil.ints.Int2ObjectMap.Entry;
-import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceMap.Entry;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
@@ -136,10 +136,10 @@
     public static final LocalVariableList EMPTY = new LocalVariableList(0, 0, emptyMap());
     public final int startOffset;
     public final int endOffset;
-    public final Int2ObjectMap<DebugLocalInfo> locals;
+    public final Int2ReferenceMap<DebugLocalInfo> locals;
 
     private LocalVariableList(
-        int startOffset, int endOffset, Int2ObjectMap<DebugLocalInfo> locals) {
+        int startOffset, int endOffset, Int2ReferenceMap<DebugLocalInfo> locals) {
       this.startOffset = startOffset;
       this.endOffset = endOffset;
       this.locals = locals;
@@ -151,7 +151,7 @@
         Reference2IntMap<CfLabel> labelOffsets) {
       int startOffset = Integer.MIN_VALUE;
       int endOffset = Integer.MAX_VALUE;
-      Int2ObjectMap<DebugLocalInfo> currentLocals = null;
+      Int2ReferenceMap<DebugLocalInfo> currentLocals = null;
       for (LocalVariableInfo local : locals) {
         int start = labelOffsets.getInt(local.getStart());
         int end = labelOffsets.getInt(local.getEnd());
@@ -163,7 +163,7 @@
           continue;
         }
         if (currentLocals == null) {
-          currentLocals = new Int2ObjectOpenHashMap<>();
+          currentLocals = new Int2ReferenceOpenHashMap<>();
         }
         startOffset = Math.max(startOffset, start);
         endOffset = Math.min(endOffset, end);
@@ -181,17 +181,17 @@
       return locals.get(register);
     }
 
-    public Int2ObjectOpenHashMap<DebugLocalInfo> merge(LocalVariableList other) {
+    public Int2ReferenceOpenHashMap<DebugLocalInfo> merge(LocalVariableList other) {
       return merge(this, other);
     }
 
-    private static Int2ObjectOpenHashMap<DebugLocalInfo> merge(
+    private static Int2ReferenceOpenHashMap<DebugLocalInfo> merge(
         LocalVariableList a, LocalVariableList b) {
       if (a.locals.size() > b.locals.size()) {
         return merge(b, a);
       }
-      Int2ObjectOpenHashMap<DebugLocalInfo> result = new Int2ObjectOpenHashMap<>();
-      for (Entry<DebugLocalInfo> local : a.locals.int2ObjectEntrySet()) {
+      Int2ReferenceOpenHashMap<DebugLocalInfo> result = new Int2ReferenceOpenHashMap<>();
+      for (Entry<DebugLocalInfo> local : a.locals.int2ReferenceEntrySet()) {
         if (local.getValue().equals(b.getLocal(local.getIntKey()))) {
           result.put(local.getIntKey(), local.getValue());
         }
@@ -212,8 +212,8 @@
   private LocalVariableList cachedLocalVariableList;
   private int currentInstructionIndex;
   private boolean inPrelude;
-  private Int2ObjectMap<DebugLocalInfo> incomingLocals;
-  private Int2ObjectMap<DebugLocalInfo> outgoingLocals;
+  private Int2ReferenceMap<DebugLocalInfo> incomingLocals;
+  private Int2ReferenceMap<DebugLocalInfo> outgoingLocals;
   private Int2ReferenceMap<CfState.Snapshot> incomingState = new Int2ReferenceOpenHashMap<>();
   private final CanonicalPositions canonicalPositions;
   private final InternalOutputMode internalOutputMode;
@@ -385,7 +385,7 @@
     setLocalVariableLists();
     DexSourceCode.buildArgumentsWithUnusedArgumentStubs(builder, 0, method, state::write);
     // Add debug information for all locals at the initial label.
-    Int2ObjectMap<DebugLocalInfo> locals = getLocalVariables(0).locals;
+    Int2ReferenceMap<DebugLocalInfo> locals = getLocalVariables(0).locals;
     if (!locals.isEmpty()) {
       int firstLocalIndex = 0;
       if (!method.isStatic()) {
@@ -397,7 +397,7 @@
           firstLocalIndex++;
         }
       }
-      for (Entry<DebugLocalInfo> entry : locals.int2ObjectEntrySet()) {
+      for (Entry<DebugLocalInfo> entry : locals.int2ReferenceEntrySet()) {
         if (firstLocalIndex <= entry.getIntKey()) {
           builder.addDebugLocalStart(entry.getIntKey(), entry.getValue());
         }
@@ -470,16 +470,16 @@
         getCanonicalDebugPositionAtOffset(isExceptional ? successorOffset : predecessorOffset));
 
     // Manually compute the local variable change for the block transfer.
-    Int2ObjectMap<DebugLocalInfo> atSource = getLocalVariables(predecessorOffset).locals;
-    Int2ObjectMap<DebugLocalInfo> atTarget = getLocalVariables(successorOffset).locals;
+    Int2ReferenceMap<DebugLocalInfo> atSource = getLocalVariables(predecessorOffset).locals;
+    Int2ReferenceMap<DebugLocalInfo> atTarget = getLocalVariables(successorOffset).locals;
     if (!isExceptional) {
-      for (Entry<DebugLocalInfo> entry : atSource.int2ObjectEntrySet()) {
+      for (Entry<DebugLocalInfo> entry : atSource.int2ReferenceEntrySet()) {
         if (atTarget.get(entry.getIntKey()) != entry.getValue()) {
           builder.addDebugLocalEnd(entry.getIntKey(), entry.getValue());
         }
       }
     }
-    for (Entry<DebugLocalInfo> entry : atTarget.int2ObjectEntrySet()) {
+    for (Entry<DebugLocalInfo> entry : atTarget.int2ReferenceEntrySet()) {
       if (atSource.get(entry.getIntKey()) != entry.getValue()) {
         builder.addDebugLocalStart(entry.getIntKey(), entry.getValue());
       }
@@ -492,7 +492,7 @@
     // back-edge will explicitly keep locals live at that point.
     if (!hasExitingInstruction && code.getInstructions().get(predecessorOffset) instanceof CfGoto) {
       assert !isExceptional;
-      for (Entry<DebugLocalInfo> entry : atSource.int2ObjectEntrySet()) {
+      for (Entry<DebugLocalInfo> entry : atSource.int2ReferenceEntrySet()) {
         if (atTarget.get(entry.getIntKey()) == entry.getValue()) {
           builder.addDebugLocalEnd(entry.getIntKey(), entry.getValue());
         }
@@ -549,7 +549,7 @@
         for (int successorOffset : currentBlockInfo.exceptionalSuccessors) {
           live.putAll(getLocalVariables(successorOffset).locals);
         }
-        for (Entry<DebugLocalInfo> entry : incomingLocals.int2ObjectEntrySet()) {
+        for (Entry<DebugLocalInfo> entry : incomingLocals.int2ReferenceEntrySet()) {
           if (live.get(entry.getIntKey()) != entry.getValue()) {
             builder.addDebugLocalEnd(entry.getIntKey(), entry.getValue());
           }
@@ -687,7 +687,7 @@
 
   private void endLocals(IRBuilder builder) {
     assert localsChanged();
-    for (Entry<DebugLocalInfo> entry : incomingLocals.int2ObjectEntrySet()) {
+    for (Entry<DebugLocalInfo> entry : incomingLocals.int2ReferenceEntrySet()) {
       if (!entry.getValue().equals(outgoingLocals.get(entry.getIntKey()))) {
         builder.addDebugLocalEnd(entry.getIntKey(), entry.getValue());
       }
@@ -696,7 +696,7 @@
 
   private void startLocals(IRBuilder builder) {
     assert localsChanged();
-    for (Entry<DebugLocalInfo> entry : outgoingLocals.int2ObjectEntrySet()) {
+    for (Entry<DebugLocalInfo> entry : outgoingLocals.int2ReferenceEntrySet()) {
       if (!entry.getValue().equals(incomingLocals.get(entry.getIntKey()))) {
         Slot slot = state.read(entry.getIntKey());
         if (slot != null && slot.type != ValueType.fromDexType(entry.getValue().type)) {
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 358a7fe..9935044 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
@@ -939,8 +939,6 @@
       count++;
       result = appView.dexItemFactory().createType(DescriptorUtils.javaTypeToDescriptor(name));
     } while (appView.definitionFor(result) != null);
-    // Register the newly generated type in the subtyping hierarchy, if we have one.
-    appView.appInfo().registerNewType(result, appView.dexItemFactory().objectType);
     return result;
   }
 
@@ -1154,6 +1152,10 @@
 
     previous = printMethod(code, "IR after inserting assume instructions (SSA)", previous);
 
+    appView.withGeneratedExtensionRegistryShrinker(shrinker -> shrinker.rewriteCode(method, code));
+
+    previous = printMethod(code, "IR after generated extension registry shrinking (SSA)", previous);
+
     appView.withGeneratedMessageLiteShrinker(shrinker -> shrinker.run(method, code));
 
     previous = printMethod(code, "IR after generated message lite shrinking (SSA)", previous);
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
index 5edd98e..d52f02e 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
@@ -49,7 +49,6 @@
 import java.util.IdentityHashMap;
 import java.util.List;
 import java.util.Map;
-import java.util.Objects;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ExecutionException;
@@ -253,8 +252,7 @@
     if (!appView.options().encodeChecksums) {
       return DexProgramClass::invalidChecksumRequest;
     }
-    long hash = Objects.hash(method, method.getCode());
-    return c -> hash;
+    return c -> method.method.hashCode();
   }
 
   private MethodProvider getMethodProviderOrNull(DexMethod method) {
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaClass.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaClass.java
index 40932cb..9998c94 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaClass.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaClass.java
@@ -105,9 +105,6 @@
                 lambdaClassType,
                 factory.createProto(lambdaClassType, descriptor.captures.values),
                 rewriter.createInstanceMethodName);
-
-    // We have to register this new class as a subtype of object.
-    rewriter.converter.appView.appInfo().registerNewType(type, factory.objectType);
   }
 
   // Generate unique lambda class type for lambda descriptor and instantiation point context.
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CallSiteOptimizationInfoPropagator.java b/src/main/java/com/android/tools/r8/ir/optimize/CallSiteOptimizationInfoPropagator.java
index cbedf91..ab931cc 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CallSiteOptimizationInfoPropagator.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CallSiteOptimizationInfoPropagator.java
@@ -23,7 +23,7 @@
 import com.android.tools.r8.ir.conversion.CodeOptimization;
 import com.android.tools.r8.ir.conversion.PostOptimization;
 import com.android.tools.r8.ir.optimize.info.CallSiteOptimizationInfo;
-import com.android.tools.r8.ir.optimize.info.MutableCallSiteOptimizationInfo;
+import com.android.tools.r8.ir.optimize.info.ConcreteCallSiteOptimizationInfo;
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.google.common.collect.Sets;
@@ -80,9 +80,6 @@
       if (!instruction.isInvokeMethod() && !instruction.isInvokeCustom()) {
         continue;
       }
-      if (!MutableCallSiteOptimizationInfo.hasArgumentsToRecord(instruction.inValues())) {
-        continue;
-      }
       if (instruction.isInvokeMethod()) {
         InvokeMethod invoke = instruction.asInvokeMethod();
         if (invoke.isInvokeMethodWithDynamicDispatch()) {
@@ -102,7 +99,7 @@
           continue;
         }
         for (DexEncodedMethod target : targets) {
-          recordArgumentsIfNecessary(context, target, invoke.inValues());
+          recordArgumentsIfNecessary(target, invoke.inValues());
         }
       }
       // TODO(b/129458850): if lambda desugaring happens before IR processing, seeing invoke-custom
@@ -116,47 +113,62 @@
           continue;
         }
         for (DexEncodedMethod target : targets) {
-          recordArgumentsIfNecessary(context, target, instruction.inValues());
+          recordArgumentsIfNecessary(target, instruction.inValues());
         }
       }
     }
   }
 
-  private void recordArgumentsIfNecessary(
-      DexEncodedMethod context, DexEncodedMethod target, List<Value> inValues) {
+  // Record arguments for the given method if necessary.
+  // At the same time, if it decides to bail out, make the corresponding info immutable so that we
+  // can avoid recording arguments for the same method accidentally.
+  private void recordArgumentsIfNecessary(DexEncodedMethod target, List<Value> inValues) {
     assert !target.isObsolete();
-    if (target.shouldNotHaveCode() || target.method.getArity() == 0) {
+    if (target.getCallSiteOptimizationInfo().isTop()) {
       return;
     }
+    target.joinCallSiteOptimizationInfo(
+        computeCallSiteOptimizationInfoFromArguments(target, inValues), appView);
+  }
+
+  private CallSiteOptimizationInfo computeCallSiteOptimizationInfoFromArguments(
+      DexEncodedMethod target, List<Value> inValues) {
+    // No method body or no argument at all.
+    if (target.shouldNotHaveCode() || inValues.size() == 0) {
+      return CallSiteOptimizationInfo.TOP;
+    }
     // If pinned, that method could be invoked via reflection.
     if (appView.appInfo().isPinned(target.method)) {
-      return;
+      return CallSiteOptimizationInfo.TOP;
     }
     // If the method overrides a library method, it is unsure how the method would be invoked by
     // that library.
     if (target.isLibraryMethodOverride().isTrue()) {
-      return;
+      return CallSiteOptimizationInfo.TOP;
     }
     // If the program already has illegal accesses, method resolution results will reflect that too.
     // We should avoid recording arguments in that case. E.g., b/139823850: static methods can be a
     // result of virtual call targets, if that's the only method that matches name and signature.
     int argumentOffset = target.isStatic() ? 0 : 1;
     if (inValues.size() != argumentOffset + target.method.getArity()) {
-      return;
+      return CallSiteOptimizationInfo.BOTTOM;
     }
-    MutableCallSiteOptimizationInfo optimizationInfo =
-        target.getMutableCallSiteOptimizationInfo(appView);
-    optimizationInfo.recordArguments(appView, context, inValues);
+    return ConcreteCallSiteOptimizationInfo.fromArguments(appView, target, inValues);
   }
 
   // If collected call site optimization info has something useful, e.g., non-null argument,
   // insert corresponding assume instructions for arguments.
   public void applyCallSiteOptimizationInfo(
       IRCode code, CallSiteOptimizationInfo callSiteOptimizationInfo) {
-    if (mode != Mode.REVISIT
-        || !callSiteOptimizationInfo.hasUsefulOptimizationInfo(appView, code.method)) {
+    if (mode != Mode.REVISIT) {
       return;
     }
+    // TODO(b/139246447): Assert no BOTTOM left.
+    if (!callSiteOptimizationInfo.isConcreteCallSiteOptimizationInfo()) {
+      return;
+    }
+    assert callSiteOptimizationInfo.asConcreteCallSiteOptimizationInfo()
+        .hasUsefulOptimizationInfo(appView, code.method);
     Set<Value> affectedValues = Sets.newIdentityHashSet();
     List<Assume<?>> assumeInstructions = new LinkedList<>();
     List<ConstInstruction> constants = new LinkedList<>();
@@ -237,15 +249,18 @@
     for (DexProgramClass clazz : appView.appInfo().classes()) {
       for (DexEncodedMethod method : clazz.methods()) {
         assert !method.isObsolete();
-        if (method.shouldNotHaveCode()
-            || method.getCallSiteOptimizationInfo().isDefaultCallSiteOptimizationInfo()) {
+        if (method.shouldNotHaveCode()) {
+          assert !method.hasCode();
           continue;
         }
-        MutableCallSiteOptimizationInfo optimizationInfo =
-            method.getCallSiteOptimizationInfo().asMutableCallSiteOptimizationInfo();
-        if (optimizationInfo.hasUsefulOptimizationInfo(appView, method)) {
-          targetsToRevisit.add(method);
+        // TODO(b/139246447): Assert no BOTTOM left.
+        CallSiteOptimizationInfo callSiteOptimizationInfo = method.getCallSiteOptimizationInfo();
+        if (!callSiteOptimizationInfo.isConcreteCallSiteOptimizationInfo()) {
+          continue;
         }
+        assert callSiteOptimizationInfo.asConcreteCallSiteOptimizationInfo()
+            .hasUsefulOptimizationInfo(appView, method);
+        targetsToRevisit.add(method);
       }
     }
     if (revisitedMethods != null) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index f2c9031..ccf312a 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -98,8 +98,8 @@
 import it.unimi.dsi.fastutil.ints.Int2IntArrayMap;
 import it.unimi.dsi.fastutil.ints.Int2IntMap;
 import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
-import it.unimi.dsi.fastutil.ints.Int2ObjectAVLTreeMap;
-import it.unimi.dsi.fastutil.ints.Int2ObjectSortedMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap.Entry;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
@@ -460,7 +460,7 @@
 
   public static class SwitchBuilder extends InstructionBuilder<SwitchBuilder> {
     private Value value;
-    private final Int2ObjectSortedMap<BasicBlock> keyToTarget = new Int2ObjectAVLTreeMap<>();
+    private final Int2ReferenceSortedMap<BasicBlock> keyToTarget = new Int2ReferenceAVLTreeMap<>();
     private BasicBlock fallthrough;
 
     public SwitchBuilder(Position position) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java b/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java
index 7f055de..2ac3abd 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java
@@ -806,13 +806,13 @@
         includeInstruction(instruction);
         // Check if this instruction ends the outline.
         if (actualInstructions >= appView.options().outline.maxSize) {
-          candidate(start, index + 1);
+          candidate(start, index + 1, actualInstructions);
         } else {
           index++;
         }
       } else if (index > start) {
         // Do not add this instruction, candidate ends with previous instruction.
-        candidate(start, index);
+        candidate(start, index, actualInstructions);
       } else {
         // Restart search from next instruction.
         reset(index + 1);
@@ -1080,7 +1080,7 @@
 
     protected abstract void handle(int start, int end, Outline outline);
 
-    private void candidate(int start, int index) {
+    private void candidate(int start, int index, int actualInstructions) {
       List<Instruction> instructions = getInstructionArray();
       assert !instructions.get(start).isConstInstruction();
 
@@ -1100,13 +1100,7 @@
       }
 
       // Check if the candidate qualifies.
-      int nonConstInstructions = 0;
-      for (int i = start; i < end; i++) {
-        if (!instructions.get(i).isConstInstruction()) {
-          nonConstInstructions++;
-        }
-      }
-      if (nonConstInstructions < appView.options().outline.minSize) {
+      if (actualInstructions < appView.options().outline.minSize) {
         reset(start + 1);
         return;
       }
@@ -1359,7 +1353,6 @@
     // No need to sort the direct methods as they are generated in sorted order.
 
     // Build the outliner class.
-    DexType superType = appView.dexItemFactory().createType("Ljava/lang/Object;");
     DexTypeList interfaces = DexTypeList.empty();
     DexString sourceFile = appView.dexItemFactory().createString("outline");
     ClassAccessFlags accessFlags = ClassAccessFlags.fromSharedAccessFlags(Constants.ACC_PUBLIC);
@@ -1371,7 +1364,7 @@
         null,
         new SynthesizedOrigin("outlining", getClass()),
         accessFlags,
-        superType,
+        appView.dexItemFactory().objectType,
         interfaces,
         sourceFile,
         null,
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/BottomCallSiteOptimizationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/BottomCallSiteOptimizationInfo.java
new file mode 100644
index 0000000..20ee5df
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/BottomCallSiteOptimizationInfo.java
@@ -0,0 +1,16 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir.optimize.info;
+
+// Nothing is known about arguments at call sites.
+public class BottomCallSiteOptimizationInfo extends CallSiteOptimizationInfo {
+  static BottomCallSiteOptimizationInfo INSTANCE = new BottomCallSiteOptimizationInfo();
+
+  private BottomCallSiteOptimizationInfo() {}
+
+  @Override
+  public boolean isBottom() {
+    return true;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/CallSiteOptimizationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/CallSiteOptimizationInfo.java
index d82f6c5..c99f24c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/CallSiteOptimizationInfo.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/CallSiteOptimizationInfo.java
@@ -8,24 +8,44 @@
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.optimize.CallSiteOptimizationInfoPropagator;
 
+// A flat lattice structure:
+//   BOTTOM, TOP, and a lattice element that holds accumulated argument info.
 public abstract class CallSiteOptimizationInfo {
+  public static BottomCallSiteOptimizationInfo BOTTOM = BottomCallSiteOptimizationInfo.INSTANCE;
+  public static TopCallSiteOptimizationInfo TOP = TopCallSiteOptimizationInfo.INSTANCE;
 
-  public boolean isDefaultCallSiteOptimizationInfo() {
+  public boolean isBottom() {
     return false;
   }
 
-  public DefaultCallSiteOptimizationInfo asDefaultCallSiteOptimizationInfo() {
-    return null;
-  }
-
-  public boolean isMutableCallSiteOptimizationInfo() {
+  public boolean isTop() {
     return false;
   }
 
-  public MutableCallSiteOptimizationInfo asMutableCallSiteOptimizationInfo() {
+  public boolean isConcreteCallSiteOptimizationInfo() {
+    return false;
+  }
+
+  public ConcreteCallSiteOptimizationInfo asConcreteCallSiteOptimizationInfo() {
     return null;
   }
 
+  public CallSiteOptimizationInfo join(
+      CallSiteOptimizationInfo other, AppView<?> appView, DexEncodedMethod encodedMethod) {
+    if (isBottom()) {
+      return other;
+    }
+    if (other.isBottom()) {
+      return this;
+    }
+    if (isTop() || other.isTop()) {
+      return TOP;
+    }
+    assert isConcreteCallSiteOptimizationInfo() && other.isConcreteCallSiteOptimizationInfo();
+    return asConcreteCallSiteOptimizationInfo()
+        .join(other.asConcreteCallSiteOptimizationInfo(), appView, encodedMethod);
+  }
+
   /**
    * {@link CallSiteOptimizationInfoPropagator} will reprocess the call target if its collected call
    * site optimization info has something useful that can trigger more optimizations. For example,
@@ -37,7 +57,9 @@
   }
 
   // The index exactly matches with in values of invocation, i.e., even including receiver.
-  public abstract TypeLatticeElement getDynamicUpperBoundType(int argIndex);
+  public TypeLatticeElement getDynamicUpperBoundType(int argIndex) {
+    return null;
+  }
 
   // TODO(b/139246447): dynamic lower bound type?
 
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/ConcreteCallSiteOptimizationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/ConcreteCallSiteOptimizationInfo.java
new file mode 100644
index 0000000..3dc5875
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/ConcreteCallSiteOptimizationInfo.java
@@ -0,0 +1,167 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir.optimize.info;
+
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
+
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.ir.analysis.type.Nullability;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
+import com.android.tools.r8.ir.code.Value;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceArrayMap;
+import java.util.List;
+
+// Accumulated optimization info from call sites.
+public class ConcreteCallSiteOptimizationInfo extends CallSiteOptimizationInfo {
+
+  // inValues() size == DexMethod.arity + (isStatic ? 0 : 1) // receiver
+  // That is, this information takes into account the receiver as well.
+  private final int size;
+  private final Int2ReferenceArrayMap<TypeLatticeElement> dynamicUpperBoundTypes;
+
+  private ConcreteCallSiteOptimizationInfo(DexEncodedMethod encodedMethod) {
+    assert encodedMethod.method.getArity() + (encodedMethod.isStatic() ? 0 : 1) > 0;
+    this.size = encodedMethod.method.getArity() + (encodedMethod.isStatic() ? 0 : 1);
+    this.dynamicUpperBoundTypes = new Int2ReferenceArrayMap<>(size);
+  }
+
+  private ConcreteCallSiteOptimizationInfo(int size) {
+    this.size = size;
+    this.dynamicUpperBoundTypes = new Int2ReferenceArrayMap<>(size);
+  }
+
+  CallSiteOptimizationInfo join(
+      ConcreteCallSiteOptimizationInfo other, AppView<?> appView, DexEncodedMethod encodedMethod) {
+    assert this.size == other.size;
+    ConcreteCallSiteOptimizationInfo result = new ConcreteCallSiteOptimizationInfo(this.size);
+    assert result.dynamicUpperBoundTypes != null;
+    for (int i = 0; i < result.size; i++) {
+      TypeLatticeElement thisUpperBoundType = getDynamicUpperBoundType(i);
+      if (thisUpperBoundType == null) {
+        // This means the corresponding argument is primitive. The counterpart should be too.
+        assert other.getDynamicUpperBoundType(i) == null;
+        continue;
+      }
+      assert thisUpperBoundType.isReference();
+      TypeLatticeElement otherUpperBoundType = other.getDynamicUpperBoundType(i);
+      assert otherUpperBoundType != null && otherUpperBoundType.isReference();
+      result.dynamicUpperBoundTypes.put(
+          i, thisUpperBoundType.join(otherUpperBoundType, appView));
+    }
+    if (result.hasUsefulOptimizationInfo(appView, encodedMethod)) {
+      return result;
+    }
+    // As soon as we know the argument collection so far does not have any useful optimization info,
+    // move to TOP so that further collection can be simply skipped.
+    return TOP;
+  }
+
+  private TypeLatticeElement[] getStaticTypes(AppView<?> appView, DexEncodedMethod encodedMethod) {
+    int argOffset = encodedMethod.isStatic() ? 0 : 1;
+    int size = encodedMethod.method.getArity() + argOffset;
+    TypeLatticeElement[] staticTypes = new TypeLatticeElement[size];
+    if (!encodedMethod.isStatic()) {
+      staticTypes[0] =
+          TypeLatticeElement.fromDexType(
+              encodedMethod.method.holder, definitelyNotNull(), appView);
+    }
+    for (int i = 0; i < encodedMethod.method.getArity(); i++) {
+      staticTypes[i + argOffset] =
+          TypeLatticeElement.fromDexType(
+              encodedMethod.method.proto.parameters.values[i], maybeNull(), appView);
+    }
+    return staticTypes;
+  }
+
+  @Override
+  public boolean hasUsefulOptimizationInfo(AppView<?> appView, DexEncodedMethod encodedMethod) {
+    TypeLatticeElement[] staticTypes = getStaticTypes(appView, encodedMethod);
+    for (int i = 0; i < size; i++) {
+      if (!staticTypes[i].isReference()) {
+        continue;
+      }
+      TypeLatticeElement dynamicUpperBoundType = getDynamicUpperBoundType(i);
+      if (dynamicUpperBoundType == null) {
+        continue;
+      }
+      // To avoid the full join of type lattices below, separately check if the nullability of
+      // arguments is improved, and if so, we can eagerly conclude that we've collected useful
+      // call site information for this method.
+      Nullability nullability = dynamicUpperBoundType.nullability();
+      if (nullability.isDefinitelyNull()) {
+        return true;
+      }
+      // TODO(b/139246447): Similar to nullability, if dynamic lower bound type is available,
+      //   we stop here and regard that call sites of this method have useful info.
+      // In general, though, we're looking for (strictly) better dynamic types for arguments.
+      if (dynamicUpperBoundType.strictlyLessThan(staticTypes[i], appView)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  @Override
+  public TypeLatticeElement getDynamicUpperBoundType(int argIndex) {
+    assert 0 <= argIndex && argIndex < size;
+    return dynamicUpperBoundTypes.getOrDefault(argIndex, null);
+  }
+
+  public static CallSiteOptimizationInfo fromArguments(
+      AppView<? extends AppInfoWithSubtyping> appView,
+      DexEncodedMethod method,
+      List<Value> inValues) {
+    ConcreteCallSiteOptimizationInfo newCallSiteInfo = new ConcreteCallSiteOptimizationInfo(method);
+    assert newCallSiteInfo.size == inValues.size();
+    for (int i = 0; i < newCallSiteInfo.size; i++) {
+      Value arg = inValues.get(i);
+      // TODO(b/69963623): may need different place to store constants.
+      if (arg.getTypeLattice().isPrimitive()) {
+        continue;
+      }
+      assert arg.getTypeLattice().isReference();
+      newCallSiteInfo.dynamicUpperBoundTypes.put(i, arg.getDynamicUpperBoundType(appView));
+    }
+    if (newCallSiteInfo.hasUsefulOptimizationInfo(appView, method)) {
+      return newCallSiteInfo;
+    }
+    // As soon as we know the current call site does not have any useful optimization info,
+    // return TOP so that further collection can be simply skipped.
+    return TOP;
+  }
+
+  @Override
+  public boolean isConcreteCallSiteOptimizationInfo() {
+    return true;
+  }
+
+  @Override
+  public ConcreteCallSiteOptimizationInfo asConcreteCallSiteOptimizationInfo() {
+    return this;
+  }
+
+  @Override
+  public boolean equals(Object other) {
+    if (!(other instanceof ConcreteCallSiteOptimizationInfo)) {
+      return false;
+    }
+    ConcreteCallSiteOptimizationInfo otherInfo = (ConcreteCallSiteOptimizationInfo) other;
+    assert this.dynamicUpperBoundTypes != null;
+    return this.dynamicUpperBoundTypes.equals(otherInfo.dynamicUpperBoundTypes);
+  }
+
+  @Override
+  public int hashCode() {
+    assert this.dynamicUpperBoundTypes != null;
+    return System.identityHashCode(dynamicUpperBoundTypes);
+  }
+
+  @Override
+  public String toString() {
+    return dynamicUpperBoundTypes.toString();
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/DefaultCallSiteOptimizationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/DefaultCallSiteOptimizationInfo.java
deleted file mode 100644
index e67ec20..0000000
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/DefaultCallSiteOptimizationInfo.java
+++ /dev/null
@@ -1,33 +0,0 @@
-// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.ir.optimize.info;
-
-import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
-
-public class DefaultCallSiteOptimizationInfo extends CallSiteOptimizationInfo {
-
-  private static final DefaultCallSiteOptimizationInfo INSTANCE =
-      new DefaultCallSiteOptimizationInfo();
-
-  private DefaultCallSiteOptimizationInfo() {}
-
-  public static DefaultCallSiteOptimizationInfo getInstance() {
-    return INSTANCE;
-  }
-
-  @Override
-  public TypeLatticeElement getDynamicUpperBoundType(int argIndex) {
-    return null;
-  }
-
-  @Override
-  public boolean isDefaultCallSiteOptimizationInfo() {
-    return true;
-  }
-
-  @Override
-  public DefaultCallSiteOptimizationInfo asDefaultCallSiteOptimizationInfo() {
-    return this;
-  }
-}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/MutableCallSiteOptimizationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/MutableCallSiteOptimizationInfo.java
deleted file mode 100644
index c18624e..0000000
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/MutableCallSiteOptimizationInfo.java
+++ /dev/null
@@ -1,256 +0,0 @@
-// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.ir.optimize.info;
-
-import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
-import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
-
-import com.android.tools.r8.graph.AppInfoWithSubtyping;
-import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.ir.analysis.type.Nullability;
-import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
-import com.android.tools.r8.ir.code.Value;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceArrayMap;
-import java.util.List;
-import java.util.Map;
-import java.util.concurrent.ConcurrentHashMap;
-
-public class MutableCallSiteOptimizationInfo extends CallSiteOptimizationInfo {
-
-  // inValues() size == DexMethod.arity + (isStatic ? 0 : 1) // receiver
-  // That is, this information takes into account the receiver as well.
-  private final int size;
-  // Mappings from the calling context to argument collection. Note that, even in the same context,
-  // the corresponding method can be invoked multiple times with different arguments, hence join of
-  // argument collections.
-  private final Map<DexEncodedMethod, ArgumentCollection> callSiteInfos = new ConcurrentHashMap<>();
-  private ArgumentCollection cachedRepresentative = null;
-
-  private static class ArgumentCollection {
-
-    private final int size;
-    private final Int2ReferenceArrayMap<TypeLatticeElement> dynamicUpperBoundTypes;
-
-    private static final ArgumentCollection BOTTOM = new ArgumentCollection() {
-      @Override
-      public int hashCode() {
-        return System.identityHashCode(this);
-      }
-
-      @Override
-      public String toString() {
-        return "(BOTTOM)";
-      }
-    };
-
-    // Only used to create a canonical BOTTOM.
-    private ArgumentCollection() {
-      this.size = -1;
-      this.dynamicUpperBoundTypes = null;
-    }
-
-    ArgumentCollection(int size) {
-      this.size = size;
-      this.dynamicUpperBoundTypes = new Int2ReferenceArrayMap<>(size);
-    }
-
-    TypeLatticeElement getDynamicUpperBoundType(int index) {
-      assert dynamicUpperBoundTypes != null;
-      assert 0 <= index && index < size;
-      return dynamicUpperBoundTypes.getOrDefault(index, null);
-    }
-
-    ArgumentCollection join(ArgumentCollection other, AppView<?> appView) {
-      if (other == BOTTOM) {
-        return this;
-      }
-      if (this == BOTTOM) {
-        return other;
-      }
-      assert this.size == other.size;
-      ArgumentCollection result = new ArgumentCollection(this.size);
-      assert result.dynamicUpperBoundTypes != null;
-      for (int i = 0; i < result.size; i++) {
-        TypeLatticeElement thisUpperBoundType = this.getDynamicUpperBoundType(i);
-        if (thisUpperBoundType == null) {
-          // This means the corresponding argument is primitive. The counterpart should be too.
-          assert other.getDynamicUpperBoundType(i) == null;
-          continue;
-        }
-        assert thisUpperBoundType.isReference();
-        TypeLatticeElement otherUpperBoundType = other.getDynamicUpperBoundType(i);
-        assert otherUpperBoundType != null && otherUpperBoundType.isReference();
-        result.dynamicUpperBoundTypes.put(
-            i, thisUpperBoundType.join(otherUpperBoundType, appView));
-      }
-      return result;
-    }
-
-    @Override
-    public boolean equals(Object other) {
-      if (!(other instanceof ArgumentCollection)) {
-        return false;
-      }
-      ArgumentCollection otherCollection = (ArgumentCollection) other;
-      if (this == BOTTOM || otherCollection == BOTTOM) {
-        return this == BOTTOM && otherCollection == BOTTOM;
-      }
-      assert this.dynamicUpperBoundTypes != null;
-      return this.dynamicUpperBoundTypes.equals(otherCollection.dynamicUpperBoundTypes);
-    }
-
-    @Override
-    public int hashCode() {
-      assert this.dynamicUpperBoundTypes != null;
-      return System.identityHashCode(dynamicUpperBoundTypes);
-    }
-
-    @Override
-    public String toString() {
-      assert this.dynamicUpperBoundTypes != null;
-      return dynamicUpperBoundTypes.toString();
-    }
-  }
-
-  public MutableCallSiteOptimizationInfo(DexEncodedMethod encodedMethod) {
-    assert encodedMethod.method.getArity() > 0;
-    this.size = encodedMethod.method.getArity() + (encodedMethod.isStatic() ? 0 : 1);
-  }
-
-  private void computeCachedRepresentativeIfNecessary(AppView<?> appView) {
-    if (cachedRepresentative == null && !callSiteInfos.isEmpty()) {
-      synchronized (callSiteInfos) {
-        // Make sure collected information is not flushed out by other threads.
-        if (!callSiteInfos.isEmpty()) {
-          cachedRepresentative =
-              callSiteInfos.values().stream()
-                  .reduce(
-                      ArgumentCollection.BOTTOM,
-                      (prev, next) -> prev.join(next, appView),
-                      (prev, next) -> prev.join(next, appView));
-          // After creating a cached representative, flush out the collected information.
-          callSiteInfos.clear();
-        } else {
-          // If collected information is gone while waiting for the lock, make sure it's used to
-          // compute the cached representative.
-          assert cachedRepresentative != null;
-        }
-      }
-    }
-  }
-
-  private TypeLatticeElement[] getStaticTypes(AppView<?> appView, DexEncodedMethod encodedMethod) {
-    int argOffset = encodedMethod.isStatic() ? 0 : 1;
-    int size = encodedMethod.method.getArity() + argOffset;
-    TypeLatticeElement[] staticTypes = new TypeLatticeElement[size];
-    if (!encodedMethod.isStatic()) {
-      staticTypes[0] =
-          TypeLatticeElement.fromDexType(
-              encodedMethod.method.holder, definitelyNotNull(), appView);
-    }
-    for (int i = 0; i < encodedMethod.method.getArity(); i++) {
-      staticTypes[i + argOffset] =
-          TypeLatticeElement.fromDexType(
-              encodedMethod.method.proto.parameters.values[i], maybeNull(), appView);
-    }
-    return staticTypes;
-  }
-
-  @Override
-  public boolean hasUsefulOptimizationInfo(AppView<?> appView, DexEncodedMethod encodedMethod) {
-    computeCachedRepresentativeIfNecessary(appView);
-    TypeLatticeElement[] staticTypes = getStaticTypes(appView, encodedMethod);
-    for (int i = 0; i < size; i++) {
-      if (!staticTypes[i].isReference()) {
-        continue;
-      }
-      TypeLatticeElement dynamicUpperBoundType = getDynamicUpperBoundType(i);
-      if (dynamicUpperBoundType == null) {
-        continue;
-      }
-      // To avoid the full join of type lattices below, separately check if the nullability of
-      // arguments is improved, and if so, we can eagerly conclude that we've collected useful
-      // call site information for this method.
-      Nullability nullability = dynamicUpperBoundType.nullability();
-      if (nullability.isDefinitelyNull()) {
-        return true;
-      }
-      // TODO(b/139246447): Similar to nullability, if dynamic lower bound type is available,
-      //   we stop here and regard that call sites of this method have useful info.
-      // In general, though, we're looking for (strictly) better dynamic types for arguments.
-      if (dynamicUpperBoundType.strictlyLessThan(staticTypes[i], appView)) {
-        return true;
-      }
-    }
-    return false;
-  }
-
-  @Override
-  public TypeLatticeElement getDynamicUpperBoundType(int argIndex) {
-    assert 0 <= argIndex && argIndex < size;
-    if (cachedRepresentative == null) {
-      return null;
-    }
-    return cachedRepresentative.getDynamicUpperBoundType(argIndex);
-  }
-
-  public static boolean hasArgumentsToRecord(List<Value> inValues) {
-    // TODO(b/69963623): allow primitive types with compile-time constants.
-    for (Value v : inValues) {
-      if (v.getTypeLattice().isReference()) {
-        return true;
-      }
-    }
-    return false;
-  }
-
-  public void recordArguments(
-      AppView<? extends AppInfoWithSubtyping> appView,
-      DexEncodedMethod callingContext,
-      List<Value> inValues) {
-    assert cachedRepresentative == null;
-    assert size == inValues.size();
-    ArgumentCollection newCallSiteInfo = new ArgumentCollection(size);
-    for (int i = 0; i < size; i++) {
-      Value arg = inValues.get(i);
-      // TODO(b/69963623): may need different place to store constants.
-      if (arg.getTypeLattice().isPrimitive()) {
-        continue;
-      }
-      assert arg.getTypeLattice().isReference();
-      newCallSiteInfo.dynamicUpperBoundTypes.put(i, arg.getDynamicUpperBoundType(appView));
-    }
-    assert callingContext != null;
-    ArgumentCollection accumulatedArgumentCollection =
-        callSiteInfos.computeIfAbsent(callingContext, ignore -> ArgumentCollection.BOTTOM);
-    callSiteInfos.put(
-        callingContext, accumulatedArgumentCollection.join(newCallSiteInfo, appView));
-  }
-
-  @Override
-  public boolean isMutableCallSiteOptimizationInfo() {
-    return true;
-  }
-
-  @Override
-  public MutableCallSiteOptimizationInfo asMutableCallSiteOptimizationInfo() {
-    return this;
-  }
-
-  @Override
-  public String toString() {
-    if (cachedRepresentative != null) {
-      return cachedRepresentative.toString();
-    }
-    StringBuilder builder = new StringBuilder();
-    for (Map.Entry<DexEncodedMethod, ArgumentCollection> entry : callSiteInfos.entrySet()) {
-      builder.append(entry.getKey().toSourceString());
-      builder.append(" -> ");
-      builder.append(entry.getValue().toString());
-      builder.append(System.lineSeparator());
-    }
-    return builder.toString();
-  }
-}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/TopCallSiteOptimizationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/TopCallSiteOptimizationInfo.java
new file mode 100644
index 0000000..5e1fdd8
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/TopCallSiteOptimizationInfo.java
@@ -0,0 +1,16 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir.optimize.info;
+
+// Nothing should not be assumed about arguments at call sites.
+class TopCallSiteOptimizationInfo extends CallSiteOptimizationInfo {
+  static TopCallSiteOptimizationInfo INSTANCE = new TopCallSiteOptimizationInfo();
+
+  private TopCallSiteOptimizationInfo() {}
+
+  @Override
+  public boolean isTop() {
+    return true;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
index 57edf39..a165998 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
@@ -384,9 +384,6 @@
       group.compact();
       DexProgramClass lambdaGroupClass = group.synthesizeClass(appView.options());
       result.put(group, lambdaGroupClass);
-
-      // We have to register this new class as a subtype of object.
-      appView.appInfo().registerNewType(lambdaGroupClass.type, lambdaGroupClass.superType);
     }
     return result;
   }
diff --git a/src/main/java/com/android/tools/r8/shaking/DefaultTreePrunerConfiguration.java b/src/main/java/com/android/tools/r8/shaking/DefaultTreePrunerConfiguration.java
new file mode 100644
index 0000000..c33ec55
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/DefaultTreePrunerConfiguration.java
@@ -0,0 +1,24 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.shaking;
+
+import com.android.tools.r8.graph.DexEncodedField;
+
+public class DefaultTreePrunerConfiguration implements TreePrunerConfiguration {
+
+  private static final DefaultTreePrunerConfiguration INSTANCE =
+      new DefaultTreePrunerConfiguration();
+
+  public DefaultTreePrunerConfiguration() {}
+
+  public static DefaultTreePrunerConfiguration getInstance() {
+    return INSTANCE;
+  }
+
+  @Override
+  public boolean isReachableOrReferencedField(AppInfoWithLiveness appInfo, DexEncodedField field) {
+    return appInfo.isFieldRead(field) || appInfo.isFieldWritten(field);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 183151c..680cdf8 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -40,6 +40,7 @@
 import com.android.tools.r8.graph.PresortedComparable;
 import com.android.tools.r8.graph.ResolutionResult;
 import com.android.tools.r8.graph.ResolutionResult.SingleResolutionResult;
+import com.android.tools.r8.graph.UseRegistry.MethodHandleUse;
 import com.android.tools.r8.graph.analysis.EnqueuerAnalysis;
 import com.android.tools.r8.ir.analysis.proto.schema.ProtoEnqueuerExtension;
 import com.android.tools.r8.ir.code.ArrayPut;
@@ -581,488 +582,497 @@
     return isRead ? info.recordRead(field, context) : info.recordWrite(field, context);
   }
 
-  private class UseRegistry extends com.android.tools.r8.graph.UseRegistry {
+  void traceCallSite(DexCallSite callSite, DexEncodedMethod currentMethod) {
+    callSites.add(callSite);
 
-    private final DexProgramClass currentHolder;
-    private final DexEncodedMethod currentMethod;
-
-    private UseRegistry(DexItemFactory factory, DexProgramClass holder, DexEncodedMethod method) {
-      super(factory);
-      assert holder.type == method.method.holder;
-      this.currentHolder = holder;
-      this.currentMethod = method;
-    }
-
-    private KeepReasonWitness reportClassReferenced(DexProgramClass referencedClass) {
-      return graphReporter.reportClassReferencedFrom(referencedClass, currentMethod);
-    }
-
-    @Override
-    public boolean registerInvokeVirtual(DexMethod method) {
-      return registerInvokeVirtual(method, KeepReason.invokedFrom(currentHolder, currentMethod));
-    }
-
-    boolean registerInvokeVirtual(DexMethod method, KeepReason keepReason) {
-      if (method == appView.dexItemFactory().classMethods.newInstance
-          || method == appView.dexItemFactory().constructorMethods.newInstance) {
-        pendingReflectiveUses.add(currentMethod);
-      } else if (appView.dexItemFactory().classMethods.isReflectiveMemberLookup(method)) {
-        // Implicitly add -identifiernamestring rule for the Java reflection in use.
-        identifierNameStrings.add(method);
-        // Revisit the current method to implicitly add -keep rule for items with reflective access.
-        pendingReflectiveUses.add(currentMethod);
+    List<DexType> directInterfaces = LambdaDescriptor.getInterfaces(callSite, appInfo);
+    if (directInterfaces != null) {
+      for (DexType lambdaInstantiatedInterface : directInterfaces) {
+        markLambdaInstantiated(lambdaInstantiatedInterface, currentMethod);
       }
-      if (!registerMethodWithTargetAndContext(virtualInvokes, method, currentMethod)) {
-        return false;
-      }
-      if (Log.ENABLED) {
-        Log.verbose(getClass(), "Register invokeVirtual `%s`.", method);
-      }
-      workList.enqueueMarkReachableVirtualAction(method, keepReason);
-      return true;
-    }
-
-    @Override
-    public boolean registerInvokeDirect(DexMethod method) {
-      return registerInvokeDirect(method, KeepReason.invokedFrom(currentHolder, currentMethod));
-    }
-
-    boolean registerInvokeDirect(DexMethod method, KeepReason keepReason) {
-      if (!registerMethodWithTargetAndContext(directInvokes, method, currentMethod)) {
-        return false;
-      }
-      if (Log.ENABLED) {
-        Log.verbose(getClass(), "Register invokeDirect `%s`.", method);
-      }
-      handleInvokeOfDirectTarget(method, keepReason);
-      return true;
-    }
-
-    @Override
-    public boolean registerInvokeStatic(DexMethod method) {
-      return registerInvokeStatic(method, KeepReason.invokedFrom(currentHolder, currentMethod));
-    }
-
-    boolean registerInvokeStatic(DexMethod method, KeepReason keepReason) {
-      DexItemFactory dexItemFactory = appView.dexItemFactory();
-      if (dexItemFactory.classMethods.isReflectiveClassLookup(method)
-          || dexItemFactory.atomicFieldUpdaterMethods.isFieldUpdater(method)) {
-        // Implicitly add -identifiernamestring rule for the Java reflection in use.
-        identifierNameStrings.add(method);
-        // Revisit the current method to implicitly add -keep rule for items with reflective access.
-        pendingReflectiveUses.add(currentMethod);
-      }
-      // See comment in handleJavaLangEnumValueOf.
-      if (method == dexItemFactory.enumMethods.valueOf) {
-        pendingReflectiveUses.add(currentMethod);
-      }
-      // Handling of application services.
-      if (dexItemFactory.serviceLoaderMethods.isLoadMethod(method)) {
-        pendingReflectiveUses.add(currentMethod);
-      }
-      if (method == dexItemFactory.proxyMethods.newProxyInstance) {
-        pendingReflectiveUses.add(currentMethod);
-      }
-      if (!registerMethodWithTargetAndContext(staticInvokes, method, currentMethod)) {
-        return false;
-      }
-      if (Log.ENABLED) {
-        Log.verbose(getClass(), "Register invokeStatic `%s`.", method);
-      }
-      handleInvokeOfStaticTarget(method, keepReason);
-      return true;
-    }
-
-    @Override
-    public boolean registerInvokeInterface(DexMethod method) {
-      return registerInvokeInterface(method, KeepReason.invokedFrom(currentHolder, currentMethod));
-    }
-
-    boolean registerInvokeInterface(DexMethod method, KeepReason keepReason) {
-      if (!registerMethodWithTargetAndContext(interfaceInvokes, method, currentMethod)) {
-        return false;
-      }
-      if (Log.ENABLED) {
-        Log.verbose(getClass(), "Register invokeInterface `%s`.", method);
-      }
-      workList.enqueueMarkReachableInterfaceAction(method, keepReason);
-      return true;
-    }
-
-    @Override
-    public boolean registerInvokeSuper(DexMethod method) {
-      // We have to revisit super invokes based on the context they are found in. The same
-      // method descriptor will hit different targets, depending on the context it is used in.
-      DexMethod actualTarget = getInvokeSuperTarget(method, currentMethod);
-      if (!registerMethodWithTargetAndContext(superInvokes, method, currentMethod)) {
-        return false;
-      }
-      if (Log.ENABLED) {
-        Log.verbose(getClass(), "Register invokeSuper `%s`.", actualTarget);
-      }
-      workList.enqueueMarkReachableSuperAction(method, currentMethod);
-      return true;
-    }
-
-    @Override
-    public boolean registerInstanceFieldWrite(DexField field) {
-      if (!registerFieldWrite(field, currentMethod)) {
-        return false;
-      }
-
-      // Must mark the field as targeted even if it does not exist.
-      markFieldAsTargeted(field, currentMethod);
-
-      DexEncodedField encodedField = appInfo.resolveField(field);
-      if (encodedField == null) {
-        reportMissingField(field);
-        return false;
-      }
-
-      DexProgramClass clazz = getProgramClassOrNull(encodedField.field.holder);
-      if (clazz == null) {
-        return false;
-      }
-
-      if (Log.ENABLED) {
-        Log.verbose(getClass(), "Register Iput `%s`.", field);
-      }
-
-      // If it is written outside of the <init>s of its enclosing class, record it.
-      boolean isWrittenOutsideEnclosingInstanceInitializers =
-          currentMethod.method.holder != encodedField.field.holder
-              || !currentMethod.isInstanceInitializer();
-      if (isWrittenOutsideEnclosingInstanceInitializers) {
-        instanceFieldsWrittenOutsideEnclosingInstanceInitializers.add(encodedField.field);
-      }
-
-      // If unused interface removal is enabled, then we won't necessarily mark the actual holder of
-      // the field as live, if the holder is an interface.
-      if (appView.options().enableUnusedInterfaceRemoval) {
-        if (encodedField.field != field) {
-          markTypeAsLive(clazz, reportClassReferenced(clazz));
-          markTypeAsLive(encodedField.field.type, this::reportClassReferenced);
+    } else {
+      if (!appInfo.isStringConcat(callSite.bootstrapMethod)) {
+        if (options.reporter != null) {
+          Diagnostic message =
+              new StringDiagnostic(
+                  "Unknown bootstrap method " + callSite.bootstrapMethod,
+                  appInfo.originFor(currentMethod.method.holder));
+          options.reporter.warning(message);
         }
       }
+    }
 
-      KeepReason reason = KeepReason.fieldReferencedIn(currentMethod);
-      workList.enqueueMarkReachableFieldAction(clazz, encodedField, reason);
+    DexProgramClass bootstrapClass =
+        getProgramClassOrNull(callSite.bootstrapMethod.asMethod().holder);
+    if (bootstrapClass != null) {
+      bootstrapMethods.add(callSite.bootstrapMethod.asMethod());
+    }
+
+    LambdaDescriptor descriptor = LambdaDescriptor.tryInfer(callSite, appInfo);
+    if (descriptor == null) {
+      return;
+    }
+
+    // For call sites representing a lambda, we link the targeted method
+    // or field as if it were referenced from the current method.
+
+    DexMethodHandle implHandle = descriptor.implHandle;
+    assert implHandle != null;
+
+    DexMethod method = implHandle.asMethod();
+    if (descriptor.delegatesToLambdaImplMethod()) {
+      lambdaMethodsTargetedByInvokeDynamic.add(method);
+    }
+
+    if (!methodsTargetedByInvokeDynamic.add(method)) {
+      return;
+    }
+
+    switch (implHandle.type) {
+      case INVOKE_STATIC:
+        traceInvokeStaticFromLambda(method, currentMethod);
+        break;
+      case INVOKE_INTERFACE:
+        traceInvokeInterfaceFromLambda(method, currentMethod);
+        break;
+      case INVOKE_INSTANCE:
+        traceInvokeVirtualFromLambda(method, currentMethod);
+        break;
+      case INVOKE_DIRECT:
+        traceInvokeDirectFromLambda(method, currentMethod);
+        break;
+      case INVOKE_CONSTRUCTOR:
+        traceNewInstanceFromLambda(method.holder, currentMethod);
+        break;
+      default:
+        throw new Unreachable();
+    }
+
+    // In similar way as what transitionMethodsForInstantiatedClass does for existing
+    // classes we need to process classes dynamically created by runtime for lambdas.
+    // We make an assumption that such classes are inherited directly from java.lang.Object
+    // and implement all lambda interfaces.
+
+    if (directInterfaces == null) {
+      return;
+    }
+
+    // The set now contains all virtual methods on the type and its supertype that are reachable.
+    // In a second step, we now look at interfaces. We have to do this in this order due to JVM
+    // semantics for default methods. A default method is only reachable if it is not overridden
+    // in any superclass. Also, it is not defined which default method is chosen if multiple
+    // interfaces define the same default method. Hence, for every interface (direct or indirect),
+    // we have to look at the interface chain and mark default methods as reachable, not taking
+    // the shadowing of other interface chains into account.
+    // See https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3.3
+    ScopedDexMethodSet seen = new ScopedDexMethodSet();
+    for (DexType iface : directInterfaces) {
+      DexProgramClass ifaceClazz = getProgramClassOrNull(iface);
+      if (ifaceClazz != null) {
+        transitionDefaultMethodsForInstantiatedClass(iface, seen);
+      }
+    }
+  }
+
+  boolean traceCheckCast(DexType type, DexEncodedMethod currentMethod) {
+    return traceConstClassOrCheckCast(type, currentMethod);
+  }
+
+  boolean traceConstClass(DexType type, DexEncodedMethod currentMethod) {
+    // We conservatively group T.class and T[].class to ensure that we do not merge T with S if
+    // potential locks on T[].class and S[].class exists.
+    DexType baseType = type.toBaseType(appView.dexItemFactory());
+    if (baseType.isClassType()) {
+      DexProgramClass baseClass = getProgramClassOrNull(baseType);
+      if (baseClass != null) {
+        constClassReferences.add(baseType);
+      }
+    }
+    return traceConstClassOrCheckCast(type, currentMethod);
+  }
+
+  private boolean traceConstClassOrCheckCast(DexType type, DexEncodedMethod currentMethod) {
+    if (!forceProguardCompatibility) {
+      return traceTypeReference(type, currentMethod);
+    }
+    DexType baseType = type.toBaseType(appView.dexItemFactory());
+    if (baseType.isClassType()) {
+      DexProgramClass baseClass = getProgramClassOrNull(baseType);
+      if (baseClass != null) {
+        // Don't require any constructor, see b/112386012.
+        markClassAsInstantiatedWithCompatRule(
+            baseClass, graphReporter.reportCompatInstantiated(baseClass, currentMethod));
+      }
       return true;
     }
+    return false;
+  }
 
-    @Override
-    public boolean registerInstanceFieldRead(DexField field) {
-      if (!registerFieldRead(field, currentMethod)) {
-        return false;
-      }
-
-      // Must mark the field as targeted even if it does not exist.
-      markFieldAsTargeted(field, currentMethod);
-
-      DexEncodedField encodedField = appInfo.resolveField(field);
-      if (encodedField == null) {
-        reportMissingField(field);
-        return false;
-      }
-
-      DexProgramClass clazz = getProgramClassOrNull(encodedField.field.holder);
-      if (clazz == null) {
-        return false;
-      }
-
-      if (Log.ENABLED) {
-        Log.verbose(getClass(), "Register Iget `%s`.", field);
-      }
-
-      // If unused interface removal is enabled, then we won't necessarily mark the actual holder of
-      // the field as live, if the holder is an interface.
-      if (appView.options().enableUnusedInterfaceRemoval) {
-        if (encodedField.field != field) {
-          markTypeAsLive(clazz, reportClassReferenced(clazz));
-          markTypeAsLive(encodedField.field.type, this::reportClassReferenced);
-        }
-      }
-
-      workList.enqueueMarkReachableFieldAction(
-          clazz, encodedField, KeepReason.fieldReferencedIn(currentMethod));
-      return true;
-    }
-
-    @Override
-    public boolean registerNewInstance(DexType type) {
-      return registerNewInstance(type, currentMethod, KeepReason.instantiatedIn(currentMethod));
-    }
-
-    public boolean registerNewInstance(
-        DexType type, DexEncodedMethod context, KeepReason keepReason) {
+  void traceMethodHandle(
+      DexMethodHandle methodHandle, MethodHandleUse use, DexEncodedMethod currentMethod) {
+    // If a method handle is not an argument to a lambda metafactory it could flow to a
+    // MethodHandle.invokeExact invocation. For that to work, the receiver type cannot have
+    // changed and therefore we cannot perform member rebinding. For these handles, we maintain
+    // the receiver for the method handle. Therefore, we have to make sure that the receiver
+    // stays in the output (and is not class merged). To ensure that we treat the receiver
+    // as instantiated.
+    if (methodHandle.isMethodHandle() && use != MethodHandleUse.ARGUMENT_TO_LAMBDA_METAFACTORY) {
+      DexType type = methodHandle.asMethod().holder;
       DexProgramClass clazz = getProgramClassOrNull(type);
       if (clazz != null) {
-        if (clazz.isInterface()) {
-          markTypeAsLive(clazz, graphReporter.registerClass(clazz, keepReason));
+        KeepReason reason = KeepReason.methodHandleReferencedIn(currentMethod);
+        if (clazz.isInterface() && !clazz.accessFlags.isAnnotation()) {
+          markInterfaceAsInstantiated(clazz, graphReporter.registerClass(clazz, reason));
         } else {
-          markInstantiated(clazz, context, keepReason);
-        }
-      }
-      return true;
-    }
-
-    @Override
-    public boolean registerStaticFieldRead(DexField field) {
-      if (!registerFieldRead(field, currentMethod)) {
-        return false;
-      }
-
-      DexEncodedField encodedField = appInfo.resolveField(field);
-      if (encodedField == null) {
-        // Must mark the field as targeted even if it does not exist.
-        markFieldAsTargeted(field, currentMethod);
-        reportMissingField(field);
-        return false;
-      }
-
-      if (!isProgramClass(encodedField.field.holder)) {
-        // No need to trace into the non-program code.
-        return false;
-      }
-
-      if (Log.ENABLED) {
-        Log.verbose(getClass(), "Register Sget `%s`.", field);
-      }
-
-      if (appView.options().enableGeneratedExtensionRegistryShrinking) {
-        // If it is a dead proto extension field, don't trace onwards.
-        boolean skipTracing =
-            appView.withGeneratedExtensionRegistryShrinker(
-                shrinker ->
-                    shrinker.isDeadProtoExtensionField(encodedField, fieldAccessInfoCollection),
-                false);
-        if (skipTracing) {
-          return false;
-        }
-      }
-
-      if (encodedField.field != field) {
-        // Mark the non-rebound field access as targeted. Note that this should only be done if the
-        // field is not a dead proto field (in which case we bail-out above).
-        markFieldAsTargeted(field, currentMethod);
-      }
-
-      markStaticFieldAsLive(encodedField, KeepReason.fieldReferencedIn(currentMethod));
-      return true;
-    }
-
-    @Override
-    public boolean registerStaticFieldWrite(DexField field) {
-      if (!registerFieldWrite(field, currentMethod)) {
-        return false;
-      }
-
-      DexEncodedField encodedField = appInfo.resolveField(field);
-      if (encodedField == null) {
-        // Must mark the field as targeted even if it does not exist.
-        markFieldAsTargeted(field, currentMethod);
-        reportMissingField(field);
-        return false;
-      }
-
-      if (!isProgramClass(encodedField.field.holder)) {
-        // No need to trace into the non-program code.
-        return false;
-      }
-
-      if (Log.ENABLED) {
-        Log.verbose(getClass(), "Register Sput `%s`.", field);
-      }
-
-      if (appView.options().enableGeneratedExtensionRegistryShrinking) {
-        // If it is a dead proto extension field, don't trace onwards.
-        boolean skipTracing =
-            appView.withGeneratedExtensionRegistryShrinker(
-                shrinker ->
-                    shrinker.isDeadProtoExtensionField(encodedField, fieldAccessInfoCollection),
-                false);
-        if (skipTracing) {
-          return false;
-        }
-      }
-
-      // If it is written outside of the <clinit> of its enclosing class, record it.
-      boolean isWrittenOutsideEnclosingStaticInitializer =
-          currentMethod.method.holder != encodedField.field.holder
-              || !currentMethod.isClassInitializer();
-      if (isWrittenOutsideEnclosingStaticInitializer) {
-        staticFieldsWrittenOutsideEnclosingStaticInitializer.add(encodedField.field);
-      }
-
-      if (encodedField.field != field) {
-        // Mark the non-rebound field access as targeted. Note that this should only be done if the
-        // field is not a dead proto field (in which case we bail-out above).
-        markFieldAsTargeted(field, currentMethod);
-      }
-
-      markStaticFieldAsLive(encodedField, KeepReason.fieldReferencedIn(currentMethod));
-      return true;
-    }
-
-    @Override
-    public boolean registerConstClass(DexType type) {
-      // We conservatively group T.class and T[].class to ensure that we do not merge T with S if
-      // potential locks on T[].class and S[].class exists.
-      DexType baseType = type.toBaseType(appView.dexItemFactory());
-      if (baseType.isClassType()) {
-        DexProgramClass baseClass = getProgramClassOrNull(baseType);
-        if (baseClass != null) {
-          constClassReferences.add(baseType);
-        }
-      }
-      return registerConstClassOrCheckCast(type);
-    }
-
-    @Override
-    public boolean registerCheckCast(DexType type) {
-      return registerConstClassOrCheckCast(type);
-    }
-
-    @Override
-    public boolean registerTypeReference(DexType type) {
-      markTypeAsLive(type, this::reportClassReferenced);
-      return true;
-    }
-
-    @Override
-    public void registerMethodHandle(DexMethodHandle methodHandle, MethodHandleUse use) {
-      super.registerMethodHandle(methodHandle, use);
-      // If a method handle is not an argument to a lambda metafactory it could flow to a
-      // MethodHandle.invokeExact invocation. For that to work, the receiver type cannot have
-      // changed and therefore we cannot perform member rebinding. For these handles, we maintain
-      // the receiver for the method handle. Therefore, we have to make sure that the receiver
-      // stays in the output (and is not class merged). To ensure that we treat the receiver
-      // as instantiated.
-      if (methodHandle.isMethodHandle() && use != MethodHandleUse.ARGUMENT_TO_LAMBDA_METAFACTORY) {
-        DexType type = methodHandle.asMethod().holder;
-        DexProgramClass clazz = getProgramClassOrNull(type);
-        if (clazz != null) {
-          KeepReason reason = KeepReason.methodHandleReferencedIn(currentMethod);
-          if (clazz.isInterface() && !clazz.accessFlags.isAnnotation()) {
-            markInterfaceAsInstantiated(clazz, graphReporter.registerClass(clazz, reason));
-          } else {
-            markInstantiated(clazz, null, reason);
-          }
+          markInstantiated(clazz, null, reason);
         }
       }
     }
+  }
 
-    @Override
-    public void registerCallSite(DexCallSite callSite) {
-      callSites.add(callSite);
-      super.registerCallSite(callSite);
+  boolean traceTypeReference(DexType type, DexEncodedMethod currentMethod) {
+    markTypeAsLive(type, classReferencedFromReporter(currentMethod));
+    return true;
+  }
 
-      List<DexType> directInterfaces = LambdaDescriptor.getInterfaces(callSite, appInfo);
-      if (directInterfaces != null) {
-        for (DexType lambdaInstantiatedInterface : directInterfaces) {
-          markLambdaInstantiated(lambdaInstantiatedInterface, currentMethod);
-        }
-      } else {
-        if (!appInfo.isStringConcat(callSite.bootstrapMethod)) {
-          if (options.reporter != null) {
-            Diagnostic message =
-                new StringDiagnostic(
-                    "Unknown bootstrap method " + callSite.bootstrapMethod,
-                    appInfo.originFor(currentMethod.method.holder));
-            options.reporter.warning(message);
-          }
-        }
-      }
+  boolean traceInvokeDirect(
+      DexMethod invokedMethod, DexProgramClass currentHolder, DexEncodedMethod currentMethod) {
+    return traceInvokeDirect(
+        invokedMethod, currentMethod, KeepReason.invokedFrom(currentHolder, currentMethod));
+  }
 
-      DexProgramClass bootstrapClass =
-          getProgramClassOrNull(callSite.bootstrapMethod.asMethod().holder);
-      if (bootstrapClass != null) {
-        bootstrapMethods.add(callSite.bootstrapMethod.asMethod());
-      }
+  boolean traceInvokeDirectFromLambda(DexMethod invokedMethod, DexEncodedMethod currentMethod) {
+    return traceInvokeDirect(
+        invokedMethod, currentMethod, KeepReason.invokedFromLambdaCreatedIn(currentMethod));
+  }
 
-      LambdaDescriptor descriptor = LambdaDescriptor.tryInfer(callSite, appInfo);
-      if (descriptor == null) {
-        return;
-      }
-
-      // For call sites representing a lambda, we link the targeted method
-      // or field as if it were referenced from the current method.
-
-      DexMethodHandle implHandle = descriptor.implHandle;
-      assert implHandle != null;
-
-      DexMethod method = implHandle.asMethod();
-      if (descriptor.delegatesToLambdaImplMethod()) {
-        lambdaMethodsTargetedByInvokeDynamic.add(method);
-      }
-
-      if (!methodsTargetedByInvokeDynamic.add(method)) {
-        return;
-      }
-
-      switch (implHandle.type) {
-        case INVOKE_STATIC:
-          registerInvokeStatic(method, KeepReason.invokedFromLambdaCreatedIn(currentMethod));
-          break;
-        case INVOKE_INTERFACE:
-          registerInvokeInterface(method, KeepReason.invokedFromLambdaCreatedIn(currentMethod));
-          break;
-        case INVOKE_INSTANCE:
-          registerInvokeVirtual(method, KeepReason.invokedFromLambdaCreatedIn(currentMethod));
-          break;
-        case INVOKE_DIRECT:
-          registerInvokeDirect(method, KeepReason.invokedFromLambdaCreatedIn(currentMethod));
-          break;
-        case INVOKE_CONSTRUCTOR:
-          registerNewInstance(
-              method.holder, null, KeepReason.invokedFromLambdaCreatedIn(currentMethod));
-          break;
-        default:
-          throw new Unreachable();
-      }
-
-      // In similar way as what transitionMethodsForInstantiatedClass does for existing
-      // classes we need to process classes dynamically created by runtime for lambdas.
-      // We make an assumption that such classes are inherited directly from java.lang.Object
-      // and implement all lambda interfaces.
-
-      if (directInterfaces == null) {
-        return;
-      }
-
-      // The set now contains all virtual methods on the type and its supertype that are reachable.
-      // In a second step, we now look at interfaces. We have to do this in this order due to JVM
-      // semantics for default methods. A default method is only reachable if it is not overridden
-      // in any superclass. Also, it is not defined which default method is chosen if multiple
-      // interfaces define the same default method. Hence, for every interface (direct or indirect),
-      // we have to look at the interface chain and mark default methods as reachable, not taking
-      // the shadowing of other interface chains into account.
-      // See https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3.3
-      ScopedDexMethodSet seen = new ScopedDexMethodSet();
-      for (DexType iface : directInterfaces) {
-        DexProgramClass ifaceClazz = getProgramClassOrNull(iface);
-        if (ifaceClazz != null) {
-          transitionDefaultMethodsForInstantiatedClass(iface, seen);
-        }
-      }
-    }
-
-    private boolean registerConstClassOrCheckCast(DexType type) {
-      if (!forceProguardCompatibility) {
-        return registerTypeReference(type);
-      }
-      DexType baseType = type.toBaseType(appView.dexItemFactory());
-      if (baseType.isClassType()) {
-        DexProgramClass baseClass = getProgramClassOrNull(baseType);
-        if (baseClass != null) {
-          // Don't require any constructor, see b/112386012.
-          markClassAsInstantiatedWithCompatRule(
-              baseClass, graphReporter.reportCompatInstantiated(baseClass, currentMethod));
-        }
-        return true;
-      }
+  private boolean traceInvokeDirect(
+      DexMethod invokedMethod, DexEncodedMethod currentMethod, KeepReason reason) {
+    if (!registerMethodWithTargetAndContext(directInvokes, invokedMethod, currentMethod)) {
       return false;
     }
+    if (Log.ENABLED) {
+      Log.verbose(getClass(), "Register invokeDirect `%s`.", invokedMethod);
+    }
+    handleInvokeOfDirectTarget(invokedMethod, reason);
+    return true;
+  }
+
+  boolean traceInvokeInterface(
+      DexMethod invokedMethod, DexProgramClass currentHolder, DexEncodedMethod currentMethod) {
+    return traceInvokeInterface(
+        invokedMethod, currentMethod, KeepReason.invokedFrom(currentHolder, currentMethod));
+  }
+
+  boolean traceInvokeInterfaceFromLambda(DexMethod invokedMethod, DexEncodedMethod currentMethod) {
+    return traceInvokeInterface(
+        invokedMethod, currentMethod, KeepReason.invokedFromLambdaCreatedIn(currentMethod));
+  }
+
+  private boolean traceInvokeInterface(
+      DexMethod method, DexEncodedMethod currentMethod, KeepReason keepReason) {
+    if (!registerMethodWithTargetAndContext(interfaceInvokes, method, currentMethod)) {
+      return false;
+    }
+    if (Log.ENABLED) {
+      Log.verbose(getClass(), "Register invokeInterface `%s`.", method);
+    }
+    workList.enqueueMarkReachableInterfaceAction(method, keepReason);
+    return true;
+  }
+
+  boolean traceInvokeStatic(
+      DexMethod invokedMethod, DexProgramClass currentHolder, DexEncodedMethod currentMethod) {
+    return traceInvokeStatic(
+        invokedMethod, currentMethod, KeepReason.invokedFrom(currentHolder, currentMethod));
+  }
+
+  boolean traceInvokeStaticFromLambda(DexMethod invokedMethod, DexEncodedMethod currentMethod) {
+    return traceInvokeStatic(
+        invokedMethod, currentMethod, KeepReason.invokedFromLambdaCreatedIn(currentMethod));
+  }
+
+  private boolean traceInvokeStatic(
+      DexMethod invokedMethod, DexEncodedMethod currentMethod, KeepReason reason) {
+    DexItemFactory dexItemFactory = appView.dexItemFactory();
+    if (dexItemFactory.classMethods.isReflectiveClassLookup(invokedMethod)
+        || dexItemFactory.atomicFieldUpdaterMethods.isFieldUpdater(invokedMethod)) {
+      // Implicitly add -identifiernamestring rule for the Java reflection in use.
+      identifierNameStrings.add(invokedMethod);
+      // Revisit the current method to implicitly add -keep rule for items with reflective access.
+      pendingReflectiveUses.add(currentMethod);
+    }
+    // See comment in handleJavaLangEnumValueOf.
+    if (invokedMethod == dexItemFactory.enumMethods.valueOf) {
+      pendingReflectiveUses.add(currentMethod);
+    }
+    // Handling of application services.
+    if (dexItemFactory.serviceLoaderMethods.isLoadMethod(invokedMethod)) {
+      pendingReflectiveUses.add(currentMethod);
+    }
+    if (invokedMethod == dexItemFactory.proxyMethods.newProxyInstance) {
+      pendingReflectiveUses.add(currentMethod);
+    }
+    if (!registerMethodWithTargetAndContext(staticInvokes, invokedMethod, currentMethod)) {
+      return false;
+    }
+    if (Log.ENABLED) {
+      Log.verbose(getClass(), "Register invokeStatic `%s`.", invokedMethod);
+    }
+    handleInvokeOfStaticTarget(invokedMethod, reason);
+    return true;
+  }
+
+  boolean traceInvokeSuper(
+      DexMethod invokedMethod, DexProgramClass currentHolder, DexEncodedMethod currentMethod) {
+    // We have to revisit super invokes based on the context they are found in. The same
+    // method descriptor will hit different targets, depending on the context it is used in.
+    DexMethod actualTarget = getInvokeSuperTarget(invokedMethod, currentMethod);
+    if (!registerMethodWithTargetAndContext(superInvokes, invokedMethod, currentMethod)) {
+      return false;
+    }
+    if (Log.ENABLED) {
+      Log.verbose(getClass(), "Register invokeSuper `%s`.", actualTarget);
+    }
+    workList.enqueueMarkReachableSuperAction(invokedMethod, currentMethod);
+    return true;
+  }
+
+  boolean traceInvokeVirtual(
+      DexMethod invokedMethod, DexProgramClass currentHolder, DexEncodedMethod currentMethod) {
+    return traceInvokeVirtual(
+        invokedMethod, currentMethod, KeepReason.invokedFrom(currentHolder, currentMethod));
+  }
+
+  boolean traceInvokeVirtualFromLambda(DexMethod invokedMethod, DexEncodedMethod currentMethod) {
+    return traceInvokeVirtual(
+        invokedMethod, currentMethod, KeepReason.invokedFromLambdaCreatedIn(currentMethod));
+  }
+
+  private boolean traceInvokeVirtual(
+      DexMethod invokedMethod, DexEncodedMethod currentMethod, KeepReason reason) {
+    if (invokedMethod == appView.dexItemFactory().classMethods.newInstance
+        || invokedMethod == appView.dexItemFactory().constructorMethods.newInstance) {
+      pendingReflectiveUses.add(currentMethod);
+    } else if (appView.dexItemFactory().classMethods.isReflectiveMemberLookup(invokedMethod)) {
+      // Implicitly add -identifiernamestring rule for the Java reflection in use.
+      identifierNameStrings.add(invokedMethod);
+      // Revisit the current method to implicitly add -keep rule for items with reflective access.
+      pendingReflectiveUses.add(currentMethod);
+    }
+    if (!registerMethodWithTargetAndContext(virtualInvokes, invokedMethod, currentMethod)) {
+      return false;
+    }
+    if (Log.ENABLED) {
+      Log.verbose(getClass(), "Register invokeVirtual `%s`.", invokedMethod);
+    }
+    workList.enqueueMarkReachableVirtualAction(invokedMethod, reason);
+    return true;
+  }
+
+  boolean traceNewInstance(DexType type, DexEncodedMethod currentMethod) {
+    return traceNewInstance(type, currentMethod, KeepReason.instantiatedIn(currentMethod));
+  }
+
+  boolean traceNewInstanceFromLambda(DexType type, DexEncodedMethod currentMethod) {
+    return traceNewInstance(
+        type, currentMethod, KeepReason.invokedFromLambdaCreatedIn(currentMethod));
+  }
+
+  private boolean traceNewInstance(
+      DexType type, DexEncodedMethod currentMethod, KeepReason keepReason) {
+    DexProgramClass clazz = getProgramClassOrNull(type);
+    if (clazz != null) {
+      if (clazz.isInterface()) {
+        markTypeAsLive(clazz, graphReporter.registerClass(clazz, keepReason));
+      } else {
+        markInstantiated(clazz, currentMethod, keepReason);
+      }
+    }
+    return true;
+  }
+
+  boolean traceInstanceFieldRead(DexField field, DexEncodedMethod currentMethod) {
+    if (!registerFieldRead(field, currentMethod)) {
+      return false;
+    }
+
+    // Must mark the field as targeted even if it does not exist.
+    markFieldAsTargeted(field, currentMethod);
+
+    DexEncodedField encodedField = appInfo.resolveField(field);
+    if (encodedField == null) {
+      reportMissingField(field);
+      return false;
+    }
+
+    DexProgramClass clazz = getProgramClassOrNull(encodedField.field.holder);
+    if (clazz == null) {
+      return false;
+    }
+
+    if (Log.ENABLED) {
+      Log.verbose(getClass(), "Register Iget `%s`.", field);
+    }
+
+    // If unused interface removal is enabled, then we won't necessarily mark the actual holder of
+    // the field as live, if the holder is an interface.
+    if (appView.options().enableUnusedInterfaceRemoval) {
+      if (encodedField.field != field) {
+        markTypeAsLive(clazz, graphReporter.reportClassReferencedFrom(clazz, currentMethod));
+        markTypeAsLive(encodedField.field.type, classReferencedFromReporter(currentMethod));
+      }
+    }
+
+    workList.enqueueMarkReachableFieldAction(
+        clazz, encodedField, KeepReason.fieldReferencedIn(currentMethod));
+    return true;
+  }
+
+  boolean traceInstanceFieldWrite(DexField field, DexEncodedMethod currentMethod) {
+    if (!registerFieldWrite(field, currentMethod)) {
+      return false;
+    }
+
+    // Must mark the field as targeted even if it does not exist.
+    markFieldAsTargeted(field, currentMethod);
+
+    DexEncodedField encodedField = appInfo.resolveField(field);
+    if (encodedField == null) {
+      reportMissingField(field);
+      return false;
+    }
+
+    DexProgramClass clazz = getProgramClassOrNull(encodedField.field.holder);
+    if (clazz == null) {
+      return false;
+    }
+
+    if (Log.ENABLED) {
+      Log.verbose(getClass(), "Register Iput `%s`.", field);
+    }
+
+    // If it is written outside of the <init>s of its enclosing class, record it.
+    boolean isWrittenOutsideEnclosingInstanceInitializers =
+        currentMethod.method.holder != encodedField.field.holder
+            || !currentMethod.isInstanceInitializer();
+    if (isWrittenOutsideEnclosingInstanceInitializers) {
+      instanceFieldsWrittenOutsideEnclosingInstanceInitializers.add(encodedField.field);
+    }
+
+    // If unused interface removal is enabled, then we won't necessarily mark the actual holder of
+    // the field as live, if the holder is an interface.
+    if (appView.options().enableUnusedInterfaceRemoval) {
+      if (encodedField.field != field) {
+        markTypeAsLive(clazz, graphReporter.reportClassReferencedFrom(clazz, currentMethod));
+        markTypeAsLive(encodedField.field.type, classReferencedFromReporter(currentMethod));
+      }
+    }
+
+    KeepReason reason = KeepReason.fieldReferencedIn(currentMethod);
+    workList.enqueueMarkReachableFieldAction(clazz, encodedField, reason);
+    return true;
+  }
+
+  boolean traceStaticFieldRead(DexField field, DexEncodedMethod currentMethod) {
+    if (!registerFieldRead(field, currentMethod)) {
+      return false;
+    }
+
+    DexEncodedField encodedField = appInfo.resolveField(field);
+    if (encodedField == null) {
+      // Must mark the field as targeted even if it does not exist.
+      markFieldAsTargeted(field, currentMethod);
+      reportMissingField(field);
+      return false;
+    }
+
+    if (!isProgramClass(encodedField.field.holder)) {
+      // No need to trace into the non-program code.
+      return false;
+    }
+
+    if (Log.ENABLED) {
+      Log.verbose(getClass(), "Register Sget `%s`.", field);
+    }
+
+    if (appView.options().enableGeneratedExtensionRegistryShrinking) {
+      // If it is a dead proto extension field, don't trace onwards.
+      boolean skipTracing =
+          appView.withGeneratedExtensionRegistryShrinker(
+              shrinker ->
+                  shrinker.isDeadProtoExtensionField(encodedField, fieldAccessInfoCollection),
+              false);
+      if (skipTracing) {
+        return false;
+      }
+    }
+
+    if (encodedField.field != field) {
+      // Mark the non-rebound field access as targeted. Note that this should only be done if the
+      // field is not a dead proto field (in which case we bail-out above).
+      markFieldAsTargeted(field, currentMethod);
+    }
+
+    markStaticFieldAsLive(encodedField, KeepReason.fieldReferencedIn(currentMethod));
+    return true;
+  }
+
+  boolean traceStaticFieldWrite(DexField field, DexEncodedMethod currentMethod) {
+    if (!registerFieldWrite(field, currentMethod)) {
+      return false;
+    }
+
+    DexEncodedField encodedField = appInfo.resolveField(field);
+    if (encodedField == null) {
+      // Must mark the field as targeted even if it does not exist.
+      markFieldAsTargeted(field, currentMethod);
+      reportMissingField(field);
+      return false;
+    }
+
+    if (!isProgramClass(encodedField.field.holder)) {
+      // No need to trace into the non-program code.
+      return false;
+    }
+
+    if (Log.ENABLED) {
+      Log.verbose(getClass(), "Register Sput `%s`.", field);
+    }
+
+    if (appView.options().enableGeneratedExtensionRegistryShrinking) {
+      // If it is a dead proto extension field, don't trace onwards.
+      boolean skipTracing =
+          appView.withGeneratedExtensionRegistryShrinker(
+              shrinker ->
+                  shrinker.isDeadProtoExtensionField(encodedField, fieldAccessInfoCollection),
+              false);
+      if (skipTracing) {
+        return false;
+      }
+    }
+
+    // If it is written outside of the <clinit> of its enclosing class, record it.
+    boolean isWrittenOutsideEnclosingStaticInitializer =
+        currentMethod.method.holder != encodedField.field.holder
+            || !currentMethod.isClassInitializer();
+    if (isWrittenOutsideEnclosingStaticInitializer) {
+      staticFieldsWrittenOutsideEnclosingStaticInitializer.add(encodedField.field);
+    }
+
+    if (encodedField.field != field) {
+      // Mark the non-rebound field access as targeted. Note that this should only be done if the
+      // field is not a dead proto field (in which case we bail-out above).
+      markFieldAsTargeted(field, currentMethod);
+    }
+
+    markStaticFieldAsLive(encodedField, KeepReason.fieldReferencedIn(currentMethod));
+    return true;
+  }
+
+  private Function<DexProgramClass, KeepReasonWitness> classReferencedFromReporter(
+      DexEncodedMethod currentMethod) {
+    return clazz -> graphReporter.reportClassReferencedFrom(clazz, currentMethod);
   }
 
   private void transitionReachableVirtualMethods(DexProgramClass clazz, ScopedDexMethodSet seen) {
@@ -2472,7 +2482,7 @@
     processAnnotations(method, method.annotations.annotations);
     method.parameterAnnotationsList.forEachAnnotation(
         annotation -> processAnnotation(method, annotation));
-    method.registerCodeReferences(new UseRegistry(options.itemFactory, clazz, method));
+    method.registerCodeReferences(new EnqueuerUseRegistry(appView, clazz, method, this));
 
     // Add all dependent members to the workqueue.
     enqueueRootItems(rootSet.getDependentItems(method));
diff --git a/src/main/java/com/android/tools/r8/shaking/EnqueuerUseRegistry.java b/src/main/java/com/android/tools/r8/shaking/EnqueuerUseRegistry.java
new file mode 100644
index 0000000..acd10ed
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/EnqueuerUseRegistry.java
@@ -0,0 +1,111 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.shaking;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexCallSite;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexMethodHandle;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.UseRegistry;
+
+class EnqueuerUseRegistry extends UseRegistry {
+
+  private final DexProgramClass currentHolder;
+  private final DexEncodedMethod currentMethod;
+  private final Enqueuer enqueuer;
+
+  EnqueuerUseRegistry(
+      AppView<?> appView,
+      DexProgramClass currentHolder,
+      DexEncodedMethod currentMethod,
+      Enqueuer enqueuer) {
+    super(appView.dexItemFactory());
+    assert currentHolder.type == currentMethod.method.holder;
+    this.currentHolder = currentHolder;
+    this.currentMethod = currentMethod;
+    this.enqueuer = enqueuer;
+  }
+
+  @Override
+  public boolean registerInvokeVirtual(DexMethod invokedMethod) {
+    return enqueuer.traceInvokeVirtual(invokedMethod, currentHolder, currentMethod);
+  }
+
+  @Override
+  public boolean registerInvokeDirect(DexMethod invokedMethod) {
+    return enqueuer.traceInvokeDirect(invokedMethod, currentHolder, currentMethod);
+  }
+
+  @Override
+  public boolean registerInvokeStatic(DexMethod invokedMethod) {
+    return enqueuer.traceInvokeStatic(invokedMethod, currentHolder, currentMethod);
+  }
+
+  @Override
+  public boolean registerInvokeInterface(DexMethod invokedMethod) {
+    return enqueuer.traceInvokeInterface(invokedMethod, currentHolder, currentMethod);
+  }
+
+  @Override
+  public boolean registerInvokeSuper(DexMethod invokedMethod) {
+    return enqueuer.traceInvokeSuper(invokedMethod, currentHolder, currentMethod);
+  }
+
+  @Override
+  public boolean registerInstanceFieldWrite(DexField field) {
+    return enqueuer.traceInstanceFieldWrite(field, currentMethod);
+  }
+
+  @Override
+  public boolean registerInstanceFieldRead(DexField field) {
+    return enqueuer.traceInstanceFieldRead(field, currentMethod);
+  }
+
+  @Override
+  public boolean registerNewInstance(DexType type) {
+    return enqueuer.traceNewInstance(type, currentMethod);
+  }
+
+  @Override
+  public boolean registerStaticFieldRead(DexField field) {
+    return enqueuer.traceStaticFieldRead(field, currentMethod);
+  }
+
+  @Override
+  public boolean registerStaticFieldWrite(DexField field) {
+    return enqueuer.traceStaticFieldWrite(field, currentMethod);
+  }
+
+  @Override
+  public boolean registerConstClass(DexType type) {
+    return enqueuer.traceConstClass(type, currentMethod);
+  }
+
+  @Override
+  public boolean registerCheckCast(DexType type) {
+    return enqueuer.traceCheckCast(type, currentMethod);
+  }
+
+  @Override
+  public boolean registerTypeReference(DexType type) {
+    return enqueuer.traceTypeReference(type, currentMethod);
+  }
+
+  @Override
+  public void registerMethodHandle(DexMethodHandle methodHandle, MethodHandleUse use) {
+    super.registerMethodHandle(methodHandle, use);
+    enqueuer.traceMethodHandle(methodHandle, use, currentMethod);
+  }
+
+  @Override
+  public void registerCallSite(DexCallSite callSite) {
+    super.registerCallSite(callSite);
+    enqueuer.traceCallSite(callSite, currentMethod);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/TreePruner.java b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
index cccf0f4..b7e9923 100644
--- a/src/main/java/com/android/tools/r8/shaking/TreePruner.java
+++ b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
@@ -21,6 +21,7 @@
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.utils.ExceptionUtils;
 import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.Timing;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
 import java.util.Collection;
@@ -32,16 +33,20 @@
 
 public class TreePruner {
 
-  private final DexApplication application;
   private final AppView<AppInfoWithLiveness> appView;
+  private final TreePrunerConfiguration configuration;
   private final UsagePrinter usagePrinter;
   private final Set<DexType> prunedTypes = Sets.newIdentityHashSet();
   private final Set<DexMethod> methodsToKeepForConfigurationDebugging = Sets.newIdentityHashSet();
 
-  public TreePruner(DexApplication application, AppView<AppInfoWithLiveness> appView) {
+  public TreePruner(AppView<AppInfoWithLiveness> appView) {
+    this(appView, DefaultTreePrunerConfiguration.getInstance());
+  }
+
+  public TreePruner(AppView<AppInfoWithLiveness> appView, TreePrunerConfiguration configuration) {
     InternalOptions options = appView.options();
-    this.application = application;
     this.appView = appView;
+    this.configuration = configuration;
     this.usagePrinter =
         options.hasUsageInformationConsumer()
             ? new UsagePrinter(
@@ -51,13 +56,14 @@
             : UsagePrinter.DONT_PRINT;
   }
 
-  public DexApplication run() {
-    application.timing.begin("Pruning application...");
+  public DexApplication run(DexApplication application) {
+    Timing timing = application.timing;
+    timing.begin("Pruning application...");
     DexApplication result;
     try {
       result = removeUnused(application).build();
     } finally {
-      application.timing.end();
+      timing.end();
     }
     return result;
   }
@@ -309,7 +315,7 @@
   private DexEncodedField[] reachableFields(List<DexEncodedField> fields) {
     AppInfoWithLiveness appInfo = appView.appInfo();
     Predicate<DexEncodedField> isReachableOrReferencedField =
-        field -> appInfo.isFieldRead(field) || appInfo.isFieldWritten(field);
+        field -> configuration.isReachableOrReferencedField(appInfo, field);
     int firstUnreachable = firstUnreachableIndex(fields, isReachableOrReferencedField);
     // Return the original array if all fields are used.
     if (firstUnreachable == -1) {
diff --git a/src/main/java/com/android/tools/r8/shaking/TreePrunerConfiguration.java b/src/main/java/com/android/tools/r8/shaking/TreePrunerConfiguration.java
new file mode 100644
index 0000000..41edc42
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/TreePrunerConfiguration.java
@@ -0,0 +1,12 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.shaking;
+
+import com.android.tools.r8.graph.DexEncodedField;
+
+public interface TreePrunerConfiguration {
+
+  boolean isReachableOrReferencedField(AppInfoWithLiveness appInfo, DexEncodedField field);
+}
diff --git a/src/main/java/com/android/tools/r8/utils/AndroidApp.java b/src/main/java/com/android/tools/r8/utils/AndroidApp.java
index 14f705e..c4a37c2 100644
--- a/src/main/java/com/android/tools/r8/utils/AndroidApp.java
+++ b/src/main/java/com/android/tools/r8/utils/AndroidApp.java
@@ -31,6 +31,7 @@
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.errors.InternalCompilerError;
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.origin.ArchiveEntryOrigin;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.origin.PathOrigin;
 import com.android.tools.r8.shaking.FilteredClassPath;
@@ -38,9 +39,12 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.io.ByteStreams;
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
 import java.io.ByteArrayOutputStream;
 import java.io.IOException;
 import java.io.InputStream;
+import java.nio.charset.StandardCharsets;
 import java.nio.file.Files;
 import java.nio.file.NoSuchFileException;
 import java.nio.file.OpenOption;
@@ -52,12 +56,13 @@
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashMap;
-import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.TreeSet;
+import java.util.function.Consumer;
 import java.util.zip.ZipEntry;
+import java.util.zip.ZipInputStream;
 import java.util.zip.ZipOutputStream;
 import org.objectweb.asm.ClassVisitor;
 
@@ -68,6 +73,12 @@
  */
 public class AndroidApp {
 
+  private static final String dumpVersionFileName = "r8-version";
+  private static final String dumpProgramFileName = "program.jar";
+  private static final String dumpClasspathFileName = "classpath.jar";
+  private static final String dumpLibraryFileName = "library.jar";
+  private static final String dumpConfigFileName = "proguard.config";
+
   private final ImmutableList<ProgramResourceProvider> programResourceProviders;
   private final ImmutableMap<Resource, String> programResourcesMainDescriptor;
   private final ImmutableList<ClassFileResourceProvider> classpathResourceProviders;
@@ -395,50 +406,81 @@
     return programResourcesMainDescriptor.get(resource);
   }
 
-  public AndroidApp dump(Path output, ProguardConfiguration configuration, Reporter reporter) {
+  public void dump(Path output, ProguardConfiguration configuration, Reporter reporter) {
     int nextDexIndex = 0;
-    Builder builder = AndroidApp.builder(reporter);
     OpenOption[] openOptions =
         new OpenOption[] {StandardOpenOption.CREATE, StandardOpenOption.TRUNCATE_EXISTING};
     try (ZipOutputStream out = new ZipOutputStream(Files.newOutputStream(output, openOptions))) {
-      writeToZipStream(out, "r8-version", Version.getVersionString().getBytes(), ZipEntry.DEFLATED);
+      writeToZipStream(
+          out, dumpVersionFileName, Version.getVersionString().getBytes(), ZipEntry.DEFLATED);
       if (configuration != null) {
         String proguardConfig = configuration.getParsedConfiguration();
-        writeToZipStream(out, "proguard.config", proguardConfig.getBytes(), ZipEntry.DEFLATED);
+        writeToZipStream(out, dumpConfigFileName, proguardConfig.getBytes(), ZipEntry.DEFLATED);
       }
-      nextDexIndex = dumpProgramResources("program.jar", nextDexIndex, out, builder);
-      nextDexIndex =
-          dumpClassFileResources(
-              "classpath.jar", nextDexIndex, out, builder, classpathResourceProviders);
-      nextDexIndex =
-          dumpClassFileResources(
-              "library.jar", nextDexIndex, out, builder, libraryResourceProviders);
+      nextDexIndex = dumpProgramResources(dumpProgramFileName, nextDexIndex, out);
+      nextDexIndex = dumpClasspathResources(nextDexIndex, out);
+      nextDexIndex = dumpLibraryResources(nextDexIndex, out);
     } catch (IOException | ResourceException e) {
       reporter.fatalError(new StringDiagnostic("Failed to dump inputs"), e);
     }
-    return builder.build();
   }
 
-  private int dumpProgramResources(
-      String archiveName, int nextDexIndex, ZipOutputStream out, Builder builder)
+  private int dumpLibraryResources(int nextDexIndex, ZipOutputStream out)
+      throws IOException, ResourceException {
+    nextDexIndex =
+        dumpClassFileResources(dumpLibraryFileName, nextDexIndex, out, libraryResourceProviders);
+    return nextDexIndex;
+  }
+
+  private int dumpClasspathResources(int nextDexIndex, ZipOutputStream out)
+      throws IOException, ResourceException {
+    nextDexIndex =
+        dumpClassFileResources(
+            dumpClasspathFileName, nextDexIndex, out, classpathResourceProviders);
+    return nextDexIndex;
+  }
+
+  private static ClassFileResourceProvider createClassFileResourceProvider(
+      Map<String, ProgramResource> classPathResources) {
+    return new ClassFileResourceProvider() {
+      @Override
+      public Set<String> getClassDescriptors() {
+        return classPathResources.keySet();
+      }
+
+      @Override
+      public ProgramResource getProgramResource(String descriptor) {
+        return classPathResources.get(descriptor);
+      }
+    };
+  }
+
+  private Consumer<ProgramResource> createClassFileResourceConsumer(
+      Map<String, ProgramResource> classPathResources) {
+    return programResource -> {
+      assert programResource.getClassDescriptors().size() == 1;
+      String descriptor = programResource.getClassDescriptors().iterator().next();
+      classPathResources.put(descriptor, programResource);
+    };
+  }
+
+  private int dumpProgramResources(String archiveName, int nextDexIndex, ZipOutputStream out)
       throws IOException, ResourceException {
     try (ByteArrayOutputStream archiveByteStream = new ByteArrayOutputStream()) {
       try (ZipOutputStream archiveOutputStream = new ZipOutputStream(archiveByteStream)) {
-        Set<String> seen = new HashSet<>();
+        Object2IntMap<String> seen = new Object2IntOpenHashMap<>();
         Set<DataEntryResource> dataEntries = getDataEntryResourcesForTesting();
         for (DataEntryResource dataResource : dataEntries) {
-          builder.addDataResources(dataResource);
           String entryName = dataResource.getName();
           try (InputStream dataStream = dataResource.getByteStream()) {
             byte[] bytes = ByteStreams.toByteArray(dataStream);
-            writeToZipStream(out, entryName, bytes, ZipEntry.DEFLATED);
+            writeToZipStream(archiveOutputStream, entryName, bytes, ZipEntry.DEFLATED);
           }
         }
         for (ProgramResourceProvider provider : programResourceProviders) {
           for (ProgramResource programResource : provider.getProgramResources()) {
             nextDexIndex =
-                dumpProgramResource(
-                    builder, seen, nextDexIndex, archiveOutputStream, programResource);
+                dumpProgramResource(seen, nextDexIndex, archiveOutputStream, programResource);
           }
         }
       }
@@ -451,19 +493,17 @@
       String archiveName,
       int nextDexIndex,
       ZipOutputStream out,
-      Builder builder,
       ImmutableList<ClassFileResourceProvider> classpathResourceProviders)
       throws IOException, ResourceException {
     try (ByteArrayOutputStream archiveByteStream = new ByteArrayOutputStream()) {
       try (ZipOutputStream archiveOutputStream = new ZipOutputStream(archiveByteStream)) {
-        Set<String> seen = new HashSet<>();
+        Object2IntMap<String> seen = new Object2IntOpenHashMap<>();
         for (ClassFileResourceProvider provider : classpathResourceProviders) {
           for (String descriptor : provider.getClassDescriptors()) {
             ProgramResource programResource = provider.getProgramResource(descriptor);
             int oldDexIndex = nextDexIndex;
             nextDexIndex =
-                dumpProgramResource(
-                    builder, seen, nextDexIndex, archiveOutputStream, programResource);
+                dumpProgramResource(seen, nextDexIndex, archiveOutputStream, programResource);
             assert nextDexIndex == oldDexIndex;
           }
         }
@@ -474,33 +514,23 @@
   }
 
   private static int dumpProgramResource(
-      Builder builder,
-      Set<String> seen,
+      Object2IntMap<String> seen,
       int nextDexIndex,
       ZipOutputStream archiveOutputStream,
       ProgramResource programResource)
       throws ResourceException, IOException {
     byte[] bytes = ByteStreams.toByteArray(programResource.getByteStream());
-    Set<String> classDescriptors = programResource.getClassDescriptors();
-    if (classDescriptors.size() != 1 && programResource.getKind() == Kind.CF) {
-      classDescriptors = Collections.singleton(extractClassDescriptor(bytes));
-    }
-    if (programResource instanceof OneShotByteResource) {
-      builder.addProgramResources(
-          OneShotByteResource.create(
-              programResource.getKind(), programResource.getOrigin(), bytes, classDescriptors));
-
-    } else {
-      builder.addProgramResources(programResource);
-    }
     String entryName;
     if (programResource.getKind() == Kind.CF) {
+      Set<String> classDescriptors = programResource.getClassDescriptors();
       String classDescriptor =
-          classDescriptors.size() == 1
-              ? classDescriptors.iterator().next()
-              : extractClassDescriptor(bytes);
+          (classDescriptors == null || classDescriptors.size() != 1)
+              ? extractClassDescriptor(bytes)
+              : classDescriptors.iterator().next();
       String classFileName = DescriptorUtils.getClassFileName(classDescriptor);
-      entryName = seen.add(classDescriptor) ? classFileName : (classFileName + ".dup");
+      int dupCount = seen.getOrDefault(classDescriptor, 0);
+      seen.put(classDescriptor, dupCount + 1);
+      entryName = dupCount == 0 ? classFileName : (classFileName + "." + dupCount + ".dup");
     } else {
       assert programResource.getKind() == Kind.DEX;
       entryName = "classes" + nextDexIndex++ + ".dex";
@@ -585,6 +615,118 @@
       return reporter;
     }
 
+    public Builder addDump(Path dumpFile) throws IOException {
+      System.out.println("Reading dump from file: " + dumpFile);
+      Origin origin = new PathOrigin(dumpFile);
+      ZipUtils.iter(
+          dumpFile.toString(),
+          (entry, input) -> {
+            String name = entry.getName();
+            if (name.equals(dumpVersionFileName)) {
+              String content = new String(ByteStreams.toByteArray(input), StandardCharsets.UTF_8);
+              System.out.println("Dump produced by R8 version: " + content);
+            } else if (name.equals(dumpProgramFileName)) {
+              readProgramDump(origin, input);
+            } else if (name.equals(dumpClasspathFileName)) {
+              readClassFileDump(origin, input, this::addClasspathResourceProvider, "classpath");
+            } else if (name.equals(dumpLibraryFileName)) {
+              readClassFileDump(origin, input, this::addLibraryResourceProvider, "library");
+            } else {
+              System.out.println("WARNING: Unexpected dump file entry: " + entry.getName());
+            }
+          });
+      return this;
+    }
+
+    private void readClassFileDump(
+        Origin origin,
+        InputStream input,
+        Consumer<ClassFileResourceProvider> addProvider,
+        String inputType)
+        throws IOException {
+      Map<String, ProgramResource> resources = new HashMap<>();
+      try (ZipInputStream stream = new ZipInputStream(input)) {
+        ZipEntry entry;
+        while (null != (entry = stream.getNextEntry())) {
+          String name = entry.getName();
+          if (ZipUtils.isClassFile(name)) {
+            Origin entryOrigin = new ArchiveEntryOrigin(name, origin);
+            String descriptor = DescriptorUtils.guessTypeDescriptor(name);
+            ProgramResource resource =
+                OneShotByteResource.create(
+                    Kind.CF,
+                    entryOrigin,
+                    ByteStreams.toByteArray(stream),
+                    Collections.singleton(descriptor));
+            resources.put(descriptor, resource);
+          } else if (name.endsWith(".dup")) {
+            System.out.println("WARNING: Duplicate " + inputType + " resource: " + name);
+          } else {
+            System.out.println("WARNING: Unexpected " + inputType + " resource: " + name);
+          }
+        }
+      }
+      if (!resources.isEmpty()) {
+        addProvider.accept(createClassFileResourceProvider(resources));
+      }
+    }
+
+    private void readProgramDump(Origin origin, InputStream input) throws IOException {
+      List<ProgramResource> programResources = new ArrayList<>();
+      List<DataEntryResource> dataResources = new ArrayList<>();
+      try (ZipInputStream stream = new ZipInputStream(input)) {
+        ZipEntry entry;
+        while (null != (entry = stream.getNextEntry())) {
+          String name = entry.getName();
+          if (ZipUtils.isClassFile(name)) {
+            Origin entryOrigin = new ArchiveEntryOrigin(name, origin);
+            String descriptor = DescriptorUtils.guessTypeDescriptor(name);
+            ProgramResource resource =
+                OneShotByteResource.create(
+                    Kind.CF,
+                    entryOrigin,
+                    ByteStreams.toByteArray(stream),
+                    Collections.singleton(descriptor));
+            programResources.add(resource);
+          } else if (ZipUtils.isDexFile(name)) {
+            Origin entryOrigin = new ArchiveEntryOrigin(name, origin);
+            ProgramResource resource =
+                OneShotByteResource.create(
+                    Kind.DEX, entryOrigin, ByteStreams.toByteArray(stream), null);
+            programResources.add(resource);
+          } else if (name.endsWith(".dup")) {
+            System.out.println("WARNING: Duplicate program resource: " + name);
+          } else {
+            dataResources.add(
+                DataEntryResource.fromBytes(ByteStreams.toByteArray(stream), name, origin));
+          }
+        }
+      }
+      if (!programResources.isEmpty() || !dataResources.isEmpty()) {
+        addProgramResourceProvider(
+            new ProgramResourceProvider() {
+              @Override
+              public Collection<ProgramResource> getProgramResources() throws ResourceException {
+                return programResources;
+              }
+
+              @Override
+              public DataResourceProvider getDataResourceProvider() {
+                return dataResources.isEmpty()
+                    ? null
+                    : new DataResourceProvider() {
+                      @Override
+                      public void accept(Visitor visitor) throws ResourceException {
+                        for (DataEntryResource dataResource : dataResources) {
+                          visitor.visit(dataResource);
+                        }
+                      }
+                    };
+              }
+            });
+      }
+    }
+
     /** Add program file resources. */
     public Builder addProgramFiles(Path... files) {
       return addProgramFiles(Arrays.asList(files));
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 828e8d2..55b5150 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -177,6 +177,8 @@
   public boolean printMemory = System.getProperty("com.android.tools.r8.printmemory") != null;
 
   public String dumpInputToFile = System.getProperty("com.android.tools.r8.dumpinputtofile");
+  public String dumpInputToDirectory =
+      System.getProperty("com.android.tools.r8.dumpinputtodirectory");
 
   // Flag to toggle if DEX code objects should pass-through without IR processing.
   public boolean passthroughDexCode = false;
@@ -218,11 +220,6 @@
   public boolean encodeChecksums = false;
   public BiPredicate<String, Long> dexClassChecksumFilter = (name, checksum) -> true;
 
-  // This defines the max depth threshold for the cycle eliminator. If the length of a call chain
-  // exceeds the threshold, we treat it as if we have found a cycle. This ensures that we won't run
-  // into stack overflows when the call graph contains large call chains. This should have a
-  // negligible impact on code size as long as the threshold is large enough.
-  public int callGraphCycleEliminatorMaxDepthThreshold = 256;
   public int callGraphLikelySpuriousCallEdgeThreshold = 50;
 
   // TODO(b/141719453): The inlining limit at least should be consistent with normal inlining.
@@ -985,6 +982,10 @@
     public boolean enableForceNestBasedAccessDesugaringForTest = false;
     public boolean verifyKeptGraphInfo = false;
 
+    // Force each call of application read to dump its inputs to a file, which is subsequently
+    // deleted. Useful to check that our dump functionality does not cause compilation failure.
+    public boolean dumpAll = false;
+
     public boolean desugarLambdasThroughLensCodeRewriter() {
       return enableStatefulLambdaCreateInstanceMethod;
     }
diff --git a/src/test/java/com/android/tools/r8/AndroidAppDumpsTest.java b/src/test/java/com/android/tools/r8/AndroidAppDumpsTest.java
new file mode 100644
index 0000000..04c4bf2
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/AndroidAppDumpsTest.java
@@ -0,0 +1,183 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.DataResourceProvider.Visitor;
+import com.android.tools.r8.ProgramResource.Kind;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.Box;
+import com.android.tools.r8.utils.DescriptorUtils;
+import com.android.tools.r8.utils.Reporter;
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.nio.file.Path;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Set;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class AndroidAppDumpsTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  public AndroidAppDumpsTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    Reporter reporter = new Reporter();
+
+    String dataResourceName = "my-resource.bin";
+    byte[] dataResourceData = new byte[] {1, 2, 3};
+
+    Path dexForB =
+        testForD8().addProgramClasses(B.class).setMinApi(AndroidApiLevel.B).compile().writeToZip();
+
+    AndroidApp appIn =
+        AndroidApp.builder(reporter)
+            .addClassProgramData(ToolHelper.getClassAsBytes(A.class), origin("A"))
+            .addClassProgramData(ToolHelper.getClassAsBytes(A.class), origin("A"))
+            .addClassProgramData(ToolHelper.getClassAsBytes(A.class), origin("A"))
+            .addProgramFile(dexForB)
+            .addClasspathResourceProvider(provider(B.class))
+            .addClasspathResourceProvider(provider(B.class))
+            .addClasspathResourceProvider(provider(B.class))
+            .addLibraryResourceProvider(provider(C.class))
+            .addLibraryResourceProvider(provider(C.class))
+            .addLibraryResourceProvider(provider(C.class))
+            .addProgramResourceProvider(
+                createDataResourceProvider(
+                    dataResourceName, dataResourceData, origin(dataResourceName)))
+            .build();
+
+    Path dumpFile = temp.newFolder().toPath().resolve("dump.zip");
+    appIn.dump(dumpFile, null, reporter);
+
+    AndroidApp appOut = AndroidApp.builder(reporter).addDump(dumpFile).build();
+    assertEquals(1, appOut.getClassProgramResourcesForTesting().size());
+    assertEquals(
+        DescriptorUtils.javaTypeToDescriptor(A.class.getTypeName()),
+        appOut.getClassProgramResourcesForTesting().get(0).getClassDescriptors().iterator().next());
+
+    assertEquals(1, appOut.getDexProgramResourcesForTesting().size());
+
+    assertEquals(1, appOut.getClasspathResourceProviders().size());
+    assertEquals(
+        DescriptorUtils.javaTypeToDescriptor(B.class.getTypeName()),
+        appOut.getClasspathResourceProviders().get(0).getClassDescriptors().iterator().next());
+
+    assertEquals(1, appOut.getLibraryResourceProviders().size());
+    assertEquals(
+        DescriptorUtils.javaTypeToDescriptor(C.class.getTypeName()),
+        appOut.getLibraryResourceProviders().get(0).getClassDescriptors().iterator().next());
+
+    Box<Boolean> foundData = new Box<>(false);
+    for (ProgramResourceProvider provider : appOut.getProgramResourceProviders()) {
+      DataResourceProvider dataProvider = provider.getDataResourceProvider();
+      if (dataProvider != null) {
+        dataProvider.accept(
+            new Visitor() {
+              @Override
+              public void visit(DataDirectoryResource directory) {}
+
+              @Override
+              public void visit(DataEntryResource file) {
+                if (file.getName().equals(dataResourceName)) {
+                  foundData.set(true);
+                }
+              }
+            });
+      }
+    }
+    assertTrue(foundData.get());
+  }
+
+  private ProgramResourceProvider createDataResourceProvider(
+      String name, byte[] content, Origin origin) {
+    return new ProgramResourceProvider() {
+      @Override
+      public Collection<ProgramResource> getProgramResources() throws ResourceException {
+        return Collections.emptyList();
+      }
+
+      @Override
+      public DataResourceProvider getDataResourceProvider() {
+        return new DataResourceProvider() {
+          @Override
+          public void accept(Visitor visitor) throws ResourceException {
+            visitor.visit(
+                new DataEntryResource() {
+                  @Override
+                  public InputStream getByteStream() throws ResourceException {
+                    return new ByteArrayInputStream(content);
+                  }
+
+                  @Override
+                  public String getName() {
+                    return name;
+                  }
+
+                  @Override
+                  public Origin getOrigin() {
+                    return origin;
+                  }
+                });
+          }
+        };
+      }
+    };
+  }
+
+  private Origin origin(String name) {
+    return new Origin(Origin.root()) {
+      @Override
+      public String part() {
+        return name;
+      }
+    };
+  }
+
+  private ClassFileResourceProvider provider(Class<?> clazz) {
+    return new ClassFileResourceProvider() {
+      @Override
+      public Set<String> getClassDescriptors() {
+        return Collections.singleton(DescriptorUtils.javaTypeToDescriptor(clazz.getTypeName()));
+      }
+
+      @Override
+      public ProgramResource getProgramResource(String descriptor) {
+        try {
+          return ProgramResource.fromBytes(
+              origin(clazz.getTypeName()),
+              Kind.CF,
+              ToolHelper.getClassAsBytes(clazz),
+              getClassDescriptors());
+        } catch (IOException e) {
+          throw new RuntimeException(e);
+        }
+      }
+    };
+  }
+
+  public static class A {}
+
+  public static class B {}
+
+  public static class C {}
+}
diff --git a/src/test/java/com/android/tools/r8/DumpInputsTest.java b/src/test/java/com/android/tools/r8/DumpInputsTest.java
index 3c2d9b3..b8b3a04 100644
--- a/src/test/java/com/android/tools/r8/DumpInputsTest.java
+++ b/src/test/java/com/android/tools/r8/DumpInputsTest.java
@@ -10,10 +10,13 @@
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.ZipUtils;
+import java.io.IOException;
 import java.nio.file.Files;
 import java.nio.file.Path;
 import java.util.HashSet;
+import java.util.List;
 import java.util.Set;
+import java.util.stream.Collectors;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -35,7 +38,7 @@
   }
 
   @Test
-  public void test() throws Exception {
+  public void testDumpToFile() throws Exception {
     Path dump = temp.newFolder().toPath().resolve("dump.zip");
     try {
       testForExternalR8(parameters.getBackend())
@@ -44,26 +47,60 @@
           .addProgramClasses(TestClass.class)
           .compile();
     } catch (AssertionError e) {
-      assertTrue(Files.exists(dump));
-      Path unzipped = temp.newFolder().toPath();
-      ZipUtils.unzip(dump.toString(), unzipped.toFile());
-      assertTrue(Files.exists(unzipped.resolve("program.jar")));
-      assertTrue(Files.exists(unzipped.resolve("classpath.jar")));
-      assertTrue(Files.exists(unzipped.resolve("proguard.config")));
-      assertTrue(Files.exists(unzipped.resolve("r8-version")));
-      Set<String> entries = new HashSet<>();
-      ZipUtils.iter(
-          unzipped.resolve("program.jar").toString(),
-          (entry, input) -> entries.add(entry.getName()));
-      assertTrue(
-          entries.contains(
-              DescriptorUtils.getClassFileName(
-                  DescriptorUtils.javaTypeToDescriptor(TestClass.class.getTypeName()))));
+      verifyDump(dump, false, true);
       return;
     }
     fail("Expected external compilation to exit");
   }
 
+  @Test
+  public void testDumpToDirectory() throws Exception {
+    Path dumpDir = temp.newFolder().toPath();
+    testForR8(parameters.getBackend())
+        .addProgramClasses(TestClass.class)
+        // Setting a directory will allow compilation to continue.
+        // Ensure the compilation and run can actually succeed.
+        .addLibraryFiles(ToolHelper.getJava8RuntimeJar())
+        .addKeepMainRule(TestClass.class)
+        .addOptionsModification(options -> options.dumpInputToDirectory = dumpDir.toString())
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("Hello, world");
+    assertTrue(Files.isDirectory(dumpDir));
+    List<Path> paths = Files.walk(dumpDir, 1).collect(Collectors.toList());
+    boolean hasVerified = false;
+    for (Path path : paths) {
+      if (!path.equals(dumpDir)) {
+        // The non-external run here results in assert code calling application read.
+        verifyDump(path, false, false);
+        hasVerified = true;
+      }
+    }
+    assertTrue(hasVerified);
+  }
+
+  private void verifyDump(Path dumpFile, boolean hasClasspath, boolean hasProguardConfig)
+      throws IOException {
+    assertTrue(Files.exists(dumpFile));
+    Path unzipped = temp.newFolder().toPath();
+    ZipUtils.unzip(dumpFile.toString(), unzipped.toFile());
+    assertTrue(Files.exists(unzipped.resolve("r8-version")));
+    assertTrue(Files.exists(unzipped.resolve("program.jar")));
+    assertTrue(Files.exists(unzipped.resolve("library.jar")));
+    if (hasClasspath) {
+      assertTrue(Files.exists(unzipped.resolve("classpath.jar")));
+    }
+    if (hasProguardConfig) {
+      assertTrue(Files.exists(unzipped.resolve("proguard.config")));
+    }
+    Set<String> entries = new HashSet<>();
+    ZipUtils.iter(
+        unzipped.resolve("program.jar").toString(), (entry, input) -> entries.add(entry.getName()));
+    assertTrue(
+        entries.contains(
+            DescriptorUtils.getClassFileName(
+                DescriptorUtils.javaTypeToDescriptor(TestClass.class.getTypeName()))));
+  }
+
   static class TestClass {
     public static void main(String[] args) {
       System.out.println("Hello, world");
diff --git a/src/test/java/com/android/tools/r8/desugar/backports/AbstractBackportTest.java b/src/test/java/com/android/tools/r8/desugar/backports/AbstractBackportTest.java
index fee1235..190e7ee 100644
--- a/src/test/java/com/android/tools/r8/desugar/backports/AbstractBackportTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/backports/AbstractBackportTest.java
@@ -95,6 +95,7 @@
       testForD8()
           .setMinApi(parameters.getApiLevel())
           .apply(this::configureProgram)
+          .setIncludeClassesChecksum(true)
           .compile()
           .run(parameters.getRuntime(), testClassName)
           .assertSuccess()
diff --git a/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsFileWithNoClassesTest.java b/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsFileWithNoClassesTest.java
new file mode 100644
index 0000000..57fe4b3
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsFileWithNoClassesTest.java
@@ -0,0 +1,77 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.dexfilemerger;
+
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.CompilationMode;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import java.nio.file.Path;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class DexMergeChecksumsFileWithNoClassesTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withDexRuntimes().withAllApiLevels().build();
+  }
+
+  public DexMergeChecksumsFileWithNoClassesTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testChecksumWithNoClasses() throws Exception {
+    Path out1 =
+        testForD8()
+            .setMinApi(parameters.getApiLevel())
+            .setMode(CompilationMode.DEBUG)
+            .setIncludeClassesChecksum(true)
+            .setIntermediate(true)
+            .compile()
+            .inspect(this::checkContainsChecksums)
+            .writeToZip();
+
+    Path out2 =
+        testForD8()
+            .setMinApi(parameters.getApiLevel())
+            .setMode(CompilationMode.DEBUG)
+            .setIncludeClassesChecksum(true)
+            .addProgramClasses(TestClass.class)
+            .setIntermediate(true)
+            .compile()
+            .inspect(this::checkContainsChecksums)
+            .writeToZip();
+
+    testForD8()
+        .addProgramFiles(out1, out2)
+        .setIncludeClassesChecksum(true)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), TestClass.class)
+        .inspect(this::checkContainsChecksums);
+  }
+
+  private void checkContainsChecksums(CodeInspector inspector) {
+    inspector.getMarkers().forEach(m -> assertTrue(m.getHasChecksums()));
+    // It may be prudent to check that the dex file also has the encoding string, but that is
+    // not easily accessed.
+    inspector.allClasses().forEach(c -> c.getDexClass().asProgramClass().getChecksum());
+  }
+
+  public static class TestClass {
+
+    public static void main(String[] args) {
+      System.out.println("Hello world!");
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsHighSortingStrings.java b/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsHighSortingStrings.java
index e6a90ff..c5ad260 100644
--- a/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsHighSortingStrings.java
+++ b/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsHighSortingStrings.java
@@ -101,27 +101,28 @@
 
     DexItemFactory factory = new DexItemFactory();
     assertFalse(
-        ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("\uDB3F\uDFFD")));
+        ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("\uDB3F\uDFFD")));
     assertFalse(
-        ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~\uDB3F\uDFFD\"")));
+        ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~\uDB3F\uDFFD\"")));
     assertFalse(
-        ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~~\uDB3F\uDFFD")));
+        ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~\uDB3F\uDFFD")));
     assertFalse(
-        ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~~~\uDB3F\uDFFD")));
-    assertFalse(ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("\u007f")));
-    assertFalse(ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~\u007f")));
-    assertFalse(ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~~\u007f")));
-    assertFalse(ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~~~\u007f")));
-    assertFalse(ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~~~|")));
+        ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~~\uDB3F\uDFFD")));
+    assertFalse(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("\u007f")));
+    assertFalse(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~\u007f")));
+    assertFalse(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~\u007f")));
+    assertFalse(
+        ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~~\u007f")));
+    assertFalse(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~~|")));
 
-    assertTrue(ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~~}")));
-    assertTrue(ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~~")));
-    assertTrue(ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~}")));
-    assertTrue(ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~")));
-    assertTrue(ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("}")));
+    assertTrue(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~}")));
+    assertTrue(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~")));
+    assertTrue(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~}")));
+    assertTrue(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~")));
+    assertTrue(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("}")));
 
     // False negatives.
-    assertFalse(ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~~~")));
-    assertFalse(ClassesChecksum.definitelyPreceedChecksumMarker(factory.createString("~~~z")));
+    assertFalse(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~~")));
+    assertFalse(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~~z")));
   }
 }
diff --git a/src/test/java/com/android/tools/r8/internal/proto/Proto2ShrinkingTest.java b/src/test/java/com/android/tools/r8/internal/proto/Proto2ShrinkingTest.java
index dcba861..48dcf36 100644
--- a/src/test/java/com/android/tools/r8/internal/proto/Proto2ShrinkingTest.java
+++ b/src/test/java/com/android/tools/r8/internal/proto/Proto2ShrinkingTest.java
@@ -18,6 +18,7 @@
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
 import com.android.tools.r8.utils.codeinspector.analysis.ProtoApplicationStats;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
 import java.nio.file.Path;
 import java.util.List;
 import org.junit.Test;
@@ -59,7 +60,7 @@
     return buildParameters(
         BooleanUtils.values(),
         BooleanUtils.values(),
-        getTestParameters().withAllRuntimes().build());
+        getTestParameters().withAllRuntimesAndApiLevels().build());
   }
 
   public Proto2ShrinkingTest(
@@ -78,12 +79,6 @@
             .addKeepMainRule("proto2.TestClass")
             .addKeepRuleFiles(PROTOBUF_LITE_PROGUARD_RULES)
             .addKeepRules(alwaysInlineNewSingularGeneratedExtensionRule())
-            // TODO(b/112437944): Attempt to prove that DEFAULT_INSTANCE is non-null, such that the
-            //  following "assumenotnull" rule can be omitted.
-            .addKeepRules(
-                "-assumenosideeffects class " + EXT_C + " {",
-                "  private static final " + EXT_C + " DEFAULT_INSTANCE return 1..42;",
-                "}")
             .addOptionsModification(
                 options -> {
                   options.enableFieldBitAccessAnalysis = true;
@@ -94,7 +89,7 @@
             .allowAccessModification(allowAccessModification)
             .allowUnusedProguardConfigurationRules()
             .minification(enableMinification)
-            .setMinApi(parameters.getRuntime())
+            .setMinApi(parameters.getApiLevel())
             .compile()
             .inspect(
                 outputInspector -> {
@@ -133,11 +128,16 @@
                 "10",
                 "10");
 
+    DexItemFactory dexItemFactory = new DexItemFactory();
+    ProtoApplicationStats original = new ProtoApplicationStats(dexItemFactory, inputInspector);
+    ProtoApplicationStats actual =
+        new ProtoApplicationStats(dexItemFactory, result.inspector(), original);
+
+    assertEquals(
+        ImmutableSet.of(),
+        actual.getGeneratedExtensionRegistryStats().getSpuriouslyRetainedExtensionFields());
+
     if (ToolHelper.isLocalDevelopment()) {
-      DexItemFactory dexItemFactory = new DexItemFactory();
-      ProtoApplicationStats original = new ProtoApplicationStats(dexItemFactory, inputInspector);
-      ProtoApplicationStats actual =
-          new ProtoApplicationStats(dexItemFactory, result.inspector(), original);
       System.out.println(actual.getStats());
     }
   }
@@ -245,8 +245,8 @@
           ImmutableList.of(FLAGGED_OFF_EXTENSION, HAS_NO_USED_EXTENSIONS, EXT_B, EXT_C);
       for (String unusedExtensionName : unusedExtensionNames) {
         assertThat(inputInspector.clazz(unusedExtensionName), isPresent());
-        // TODO(b/143588134): Re-enable this assertion.
-        // assertThat(outputInspector.clazz(unusedExtensionName), not(isPresent()));
+        assertThat(
+            unusedExtensionName, outputInspector.clazz(unusedExtensionName), not(isPresent()));
       }
     }
   }
@@ -362,7 +362,7 @@
         .allowAccessModification(allowAccessModification)
         .allowUnusedProguardConfigurationRules()
         .minification(enableMinification)
-        .setMinApi(parameters.getRuntime())
+        .setMinApi(parameters.getApiLevel())
         .compile()
         .inspect(
             inspector ->
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
index 42908d2..3c47534 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
@@ -536,7 +536,7 @@
   @Test
   public void testSelfOrderWithoutSubtypingInfo() {
     DexType type = factory.createType("Lmy/Type;");
-    appView.withSubtyping().appInfo().registerNewType(type, factory.objectType);
+    appView.withSubtyping().appInfo().registerNewTypeForTesting(type, factory.objectType);
     TypeLatticeElement nonNullType = fromDexType(type, Nullability.definitelyNotNull(), appView);
     ReferenceTypeLatticeElement nullableType =
         nonNullType.asReferenceTypeLatticeElement().getOrCreateVariant(Nullability.maybeNull());
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/classinitializerdefaults/NonFinalFieldWithDefaultValueTest.java b/src/test/java/com/android/tools/r8/ir/optimize/classinitializerdefaults/NonFinalFieldWithDefaultValueTest.java
new file mode 100644
index 0000000..c9033f5
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/classinitializerdefaults/NonFinalFieldWithDefaultValueTest.java
@@ -0,0 +1,122 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.classinitializerdefaults;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.FieldSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class NonFinalFieldWithDefaultValueTest extends TestBase {
+
+  private final String EXPECTED_OUTPUT =
+      StringUtils.lines("Hello world (f1=1, f3=0)!", "1", "2", "3", "-1", "-2", "-3");
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withDexRuntimes().withAllApiLevels().build();
+  }
+
+  public NonFinalFieldWithDefaultValueTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testD8() throws Exception {
+    testForD8()
+        .addInnerClasses(NonFinalFieldWithDefaultValueTest.class)
+        .setMinApi(parameters.getApiLevel())
+        // Class initializer defaults optimization only runs in release mode.
+        .release()
+        .compile()
+        .inspect(this::inspect)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(NonFinalFieldWithDefaultValueTest.class)
+        .addKeepMainRule(TestClass.class)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(this::inspect)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT);
+  }
+
+  private void inspect(CodeInspector inspector) {
+    ClassSubject testClassSubject = inspector.clazz(TestClass.class);
+    assertThat(testClassSubject, isPresent());
+
+    // No instructions can read field f1 before it is assigned, and therefore, we can safely
+    // remove the static-put instruction and update the static value of the field.
+    FieldSubject f1FieldSubject = testClassSubject.uniqueFieldWithName("f1");
+    assertThat(f1FieldSubject, isPresent());
+    assertNotNull(f1FieldSubject.getField().getStaticValue());
+    assertTrue(f1FieldSubject.getField().getStaticValue().isDexValueInt());
+    assertEquals(1, f1FieldSubject.getField().getStaticValue().asDexValueInt().getValue());
+
+    // Field f3 is assigned after an instruction that could read it, and therefore, we cannot safely
+    // remove the static-put instruction and update the static value of the field.
+    FieldSubject f3FieldSubject = testClassSubject.uniqueFieldWithName("f3");
+    assertThat(f3FieldSubject, isPresent());
+    assertNotNull(f3FieldSubject.getField().getStaticValue());
+    assertTrue(f3FieldSubject.getField().getStaticValue().isDexValueInt());
+    assertEquals(0, f3FieldSubject.getField().getStaticValue().asDexValueInt().getValue());
+  }
+
+  static class TestClass {
+
+    static int f1 = 1;
+    static Greeter f2 = new Greeter(2);
+    static int f3 = 3;
+
+    public static void main(String[] args) {
+      System.out.println(f1);
+      System.out.println(f2.value);
+      System.out.println(f3);
+      updateFields();
+      System.out.println(f1);
+      System.out.println(f2.value);
+      System.out.println(f3);
+    }
+
+    @NeverInline
+    static void updateFields() {
+      f1 = -1;
+      f2.value = -2;
+      f3 = -3;
+    }
+  }
+
+  static class Greeter {
+
+    int value;
+
+    Greeter(int value) {
+      System.out.println("Hello world (f1=" + TestClass.f1 + ", f3=" + TestClass.f3 + ")!");
+      this.value = value;
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/unusedarguments/UnusedArgumentsInMethodThatImplementsInterfaceMethodOnSubTest.java b/src/test/java/com/android/tools/r8/ir/optimize/unusedarguments/UnusedArgumentsInMethodThatImplementsInterfaceMethodOnSubTest.java
new file mode 100644
index 0000000..25c2a61
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/unusedarguments/UnusedArgumentsInMethodThatImplementsInterfaceMethodOnSubTest.java
@@ -0,0 +1,77 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.unusedarguments;
+
+import static org.hamcrest.core.StringContains.containsString;
+
+import com.android.tools.r8.NeverMerge;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class UnusedArgumentsInMethodThatImplementsInterfaceMethodOnSubTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public UnusedArgumentsInMethodThatImplementsInterfaceMethodOnSubTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(UnusedArgumentsInMethodThatImplementsInterfaceMethodOnSubTest.class)
+        .addKeepMainRule(TestClass.class)
+        .enableMergeAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), TestClass.class)
+        // TODO(b/143934502): Should succeed with "Hello from A", "Hello from C".
+        .assertFailureWithErrorThatMatches(containsString("AbstractMethodError"));
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      for (I o : new I[] {new B(), new C()}) {
+        o.method(new Object());
+      }
+    }
+  }
+
+  interface I {
+
+    void method(Object o);
+  }
+
+  @NeverMerge
+  static class A {
+
+    public void method(Object unused) {
+      System.out.println("Hello from A");
+    }
+  }
+
+  static class B extends A implements I {}
+
+  static class C implements I {
+
+    @Override
+    public void method(Object o) {
+      if (o != null) {
+        System.out.println("Hello from C");
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/jasmin/JasminBuilder.java b/src/test/java/com/android/tools/r8/jasmin/JasminBuilder.java
index 99b2271..26f2030 100644
--- a/src/test/java/com/android/tools/r8/jasmin/JasminBuilder.java
+++ b/src/test/java/com/android/tools/r8/jasmin/JasminBuilder.java
@@ -98,9 +98,7 @@
     }
 
     private ClassBuilder(String name, String superName) {
-      this.name = name;
-      this.superName = superName;
-      this.interfaces = ImmutableList.of();
+      this(name , superName, new String[0]);
     }
 
     private ClassBuilder(String name, String superName, String... interfaces) {
diff --git a/src/test/java/com/android/tools/r8/shaking/methods/interfaces/AbstractInterfaceMethodsTest.java b/src/test/java/com/android/tools/r8/shaking/methods/interfaces/AbstractInterfaceMethodsTest.java
new file mode 100644
index 0000000..442fda4
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/methods/interfaces/AbstractInterfaceMethodsTest.java
@@ -0,0 +1,80 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.shaking.methods.interfaces;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assume.assumeTrue;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import java.io.IOException;
+import java.util.concurrent.ExecutionException;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+/**
+ * This tests is showing the issue filed in b/143590191. The expectations for the test should
+ * reflect the decisions to keep the interface method or not in the super interface.
+ */
+@RunWith(Parameterized.class)
+public class AbstractInterfaceMethodsTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public AbstractInterfaceMethodsTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testSingleInheritanceProguard()
+      throws CompilationFailedException, IOException, ExecutionException {
+    assumeTrue(parameters.isCfRuntime());
+    testForProguard()
+        .addProgramClasses(I.class, J.class)
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMethodRules(J.class, "void foo()")
+        .addKeepRules("-dontwarn")
+        .compile()
+        .inspect(AbstractInterfaceMethodsTest::inspectBaseInterfaceRemove);
+  }
+
+  @Test
+  public void testSingleInheritanceR8()
+      throws CompilationFailedException, IOException, ExecutionException {
+    // TODO(b/143590191): Fix expectation when resolved.
+    testForR8(parameters.getBackend())
+        .addProgramClasses(I.class, J.class)
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMethodRules(J.class, "void foo()")
+        .compile()
+        .inspect(AbstractInterfaceMethodsTest::inspectBaseInterfaceRemove);
+  }
+
+  private static void inspectBaseInterfaceRemove(CodeInspector inspector) {
+    ClassSubject clazz = inspector.clazz(J.class);
+    assertThat(clazz, isPresent());
+    assertThat(clazz.uniqueMethodWithName("foo"), not(isPresent()));
+    assertThat(inspector.clazz(I.class), not(isPresent()));
+  }
+
+  public interface I {
+    void foo();
+  }
+
+  public interface J extends I {}
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/methods/interfaces/AbstractMethodsTest.java b/src/test/java/com/android/tools/r8/shaking/methods/interfaces/DefaultInterfaceMethodsTest.java
similarity index 93%
rename from src/test/java/com/android/tools/r8/shaking/methods/interfaces/AbstractMethodsTest.java
rename to src/test/java/com/android/tools/r8/shaking/methods/interfaces/DefaultInterfaceMethodsTest.java
index 808ae73..c6feb05 100644
--- a/src/test/java/com/android/tools/r8/shaking/methods/interfaces/AbstractMethodsTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/methods/interfaces/DefaultInterfaceMethodsTest.java
@@ -28,7 +28,7 @@
  * reflect the decisions to keep the interface method or not in the super interface.
  */
 @RunWith(Parameterized.class)
-public class AbstractMethodsTest extends TestBase {
+public class DefaultInterfaceMethodsTest extends TestBase {
 
   private final TestParameters parameters;
 
@@ -37,7 +37,7 @@
     return getTestParameters().withAllRuntimesAndApiLevels().build();
   }
 
-  public AbstractMethodsTest(TestParameters parameters) {
+  public DefaultInterfaceMethodsTest(TestParameters parameters) {
     this.parameters = parameters;
   }
 
@@ -51,7 +51,7 @@
         .addKeepMethodRules(J.class, "void foo()")
         .addKeepRules("-dontwarn")
         .compile()
-        .inspect(AbstractMethodsTest::inspectBaseInterfaceRemove);
+        .inspect(DefaultInterfaceMethodsTest::inspectBaseInterfaceRemove);
   }
 
   @Test
@@ -62,7 +62,7 @@
         .setMinApi(parameters.getApiLevel())
         .addKeepMethodRules(J.class, "void foo()")
         .compile()
-        .inspect(AbstractMethodsTest::inspectBaseInterfaceRemove);
+        .inspect(DefaultInterfaceMethodsTest::inspectBaseInterfaceRemove);
   }
 
   private static void inspectBaseInterfaceRemove(CodeInspector inspector) {
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/AbsentClassSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/AbsentClassSubject.java
index e769a54..8e2f554 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/AbsentClassSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/AbsentClassSubject.java
@@ -49,6 +49,11 @@
   }
 
   @Override
+  public FieldSubject uniqueFieldWithFinalName(String name) {
+    return new AbsentFieldSubject();
+  }
+
+  @Override
   public boolean isAbstract() {
     throw new Unreachable("Cannot determine if an absent class is abstract");
   }
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/ClassSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/ClassSubject.java
index 4ed548e..8b8f519 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/ClassSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/ClassSubject.java
@@ -123,6 +123,8 @@
 
   public abstract FieldSubject uniqueFieldWithName(String name);
 
+  public abstract FieldSubject uniqueFieldWithFinalName(String name);
+
   public FoundClassSubject asFoundClassSubject() {
     return null;
   }
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/CodeInspector.java b/src/test/java/com/android/tools/r8/utils/codeinspector/CodeInspector.java
index 2a91e4b..2bc1dd4 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/CodeInspector.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/CodeInspector.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.cf.code.CfTryCatch;
 import com.android.tools.r8.code.Instruction;
 import com.android.tools.r8.dex.ApplicationReader;
+import com.android.tools.r8.dex.Marker;
 import com.android.tools.r8.errors.Unimplemented;
 import com.android.tools.r8.graph.CfCode;
 import com.android.tools.r8.graph.Code;
@@ -48,6 +49,7 @@
 import java.nio.file.Files;
 import java.nio.file.Path;
 import java.nio.file.Paths;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
 import java.util.Map;
@@ -391,6 +393,10 @@
     }
   }
 
+  public Collection<Marker> getMarkers() {
+    return dexItemFactory.extractMarkers();
+  }
+
   // Build the generic signature using the current mapping if any.
   class GenericSignatureGenerator implements GenericSignatureAction<String> {
 
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/FieldSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/FieldSubject.java
index c182f74..dc9940f 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/FieldSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/FieldSubject.java
@@ -26,6 +26,10 @@
     return this;
   }
 
+  public FoundFieldSubject asFoundFieldSubject() {
+    return null;
+  }
+
   @Override
   public boolean isFieldSubject() {
     return true;
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java
index d7e46b1..45276f4 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java
@@ -171,6 +171,18 @@
   }
 
   @Override
+  public FieldSubject uniqueFieldWithFinalName(String name) {
+    FieldSubject fieldSubject = null;
+    for (FoundFieldSubject candidate : allFields()) {
+      if (candidate.getFinalName().equals(name)) {
+        assert fieldSubject == null;
+        fieldSubject = candidate;
+      }
+    }
+    return fieldSubject != null ? fieldSubject : new AbsentFieldSubject();
+  }
+
+  @Override
   public FoundClassSubject asFoundClassSubject() {
     return this;
   }
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/FoundFieldSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/FoundFieldSubject.java
index a4d8210..f659abe 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/FoundFieldSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/FoundFieldSubject.java
@@ -27,6 +27,11 @@
   }
 
   @Override
+  public FoundFieldSubject asFoundFieldSubject() {
+    return this;
+  }
+
+  @Override
   public boolean isPublic() {
     return dexField.accessFlags.isPublic();
   }
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/analysis/ProtoApplicationStats.java b/src/test/java/com/android/tools/r8/utils/codeinspector/analysis/ProtoApplicationStats.java
index 4a0f63d..21e821d 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/analysis/ProtoApplicationStats.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/analysis/ProtoApplicationStats.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.FieldSubject;
 import com.android.tools.r8.utils.codeinspector.FoundClassSubject;
 import com.android.tools.r8.utils.codeinspector.FoundFieldSubject;
 import com.android.tools.r8.utils.codeinspector.FoundMethodSubject;
@@ -96,11 +97,15 @@
     }
   }
 
-  class GeneratedExtensionRegistryStats extends Stats {
+  public class GeneratedExtensionRegistryStats extends Stats {
 
     final Set<DexMethod> findLiteExtensionByNumberMethods = Sets.newIdentityHashSet();
-    final Set<DexType> retainedExtensions = Sets.newIdentityHashSet();
-    final Set<DexType> spuriouslyRetainedExtensions = Sets.newIdentityHashSet();
+    final Set<DexField> retainedExtensionFields = Sets.newIdentityHashSet();
+    final Set<DexField> spuriouslyRetainedExtensionFields = Sets.newIdentityHashSet();
+
+    public Set<DexField> getSpuriouslyRetainedExtensionFields() {
+      return spuriouslyRetainedExtensionFields;
+    }
 
     String getStats(
         GeneratedExtensionRegistryStats baseline, GeneratedExtensionRegistryStats original) {
@@ -109,8 +114,8 @@
           "  # findLiteExtensionByNumber() methods: "
               + progress(this, baseline, original, x -> x.findLiteExtensionByNumberMethods),
           "  # retained extensions: "
-              + progress(this, baseline, original, x -> x.retainedExtensions),
-          "  # spuriously retained extensions: " + spuriouslyRetainedExtensions.size());
+              + progress(this, baseline, original, x -> x.retainedExtensionFields),
+          "  # spuriously retained extension fields: " + spuriouslyRetainedExtensionFields.size());
     }
   }
 
@@ -181,8 +186,12 @@
                 }
                 FoundClassSubject extensionClassSubject =
                     inspector.clazz(field.holder.toSourceString()).asFoundClassSubject();
-                generatedExtensionRegistryStats.retainedExtensions.add(
-                    extensionClassSubject.getOriginalDexType(dexItemFactory));
+                FoundFieldSubject extensionFieldSubject =
+                    extensionClassSubject
+                        .uniqueFieldWithFinalName(field.name.toSourceString())
+                        .asFoundFieldSubject();
+                generatedExtensionRegistryStats.retainedExtensionFields.add(
+                    extensionFieldSubject.getOriginalDexField(dexItemFactory));
               }
             }
           }
@@ -203,15 +212,28 @@
     }
 
     if (original != null) {
-      for (DexType extensionType : original.generatedExtensionRegistryStats.retainedExtensions) {
-        if (!generatedExtensionRegistryStats.retainedExtensions.contains(extensionType)
-            && inspector.clazz(extensionType.toSourceString()).isPresent()) {
-          generatedExtensionRegistryStats.spuriouslyRetainedExtensions.add(extensionType);
+      for (DexField extensionField :
+          original.generatedExtensionRegistryStats.retainedExtensionFields) {
+        if (generatedExtensionRegistryStats.retainedExtensionFields.contains(extensionField)) {
+          continue;
+        }
+        ClassSubject classSubject = inspector.clazz(extensionField.holder.toSourceString());
+        if (!classSubject.isPresent()) {
+          continue;
+        }
+        FieldSubject fieldSubject =
+            classSubject.uniqueFieldWithName(extensionField.name.toSourceString());
+        if (fieldSubject.isPresent()) {
+          generatedExtensionRegistryStats.spuriouslyRetainedExtensionFields.add(extensionField);
         }
       }
     }
   }
 
+  public GeneratedExtensionRegistryStats getGeneratedExtensionRegistryStats() {
+    return generatedExtensionRegistryStats;
+  }
+
   public String getStats() {
     return StringUtils.lines(
         enumStats.getStats(null, original.enumStats),
diff --git a/tools/r8_release.py b/tools/r8_release.py
index 0048d52..0f129ec 100755
--- a/tools/r8_release.py
+++ b/tools/r8_release.py
@@ -80,20 +80,7 @@
         version_diff_output = subprocess.check_output([
           'git', 'diff', '%s..HEAD' % commithash])
 
-        invalid = version_change_diff(version_diff_output, "master", version)
-        if invalid:
-          print "Unexpected diff:"
-          print "=" * 80
-          print version_diff_output
-          print "=" * 80
-          accept_string = 'THE DIFF IS OK!'
-          input = raw_input(
-            "Accept the additonal diff as part of the release? "
-            "Type '%s' to accept: " % accept_string)
-          if input != accept_string:
-            print "You did not type '%s'" % accept_string
-            print 'Aborting dev release for %s' % version
-            sys.exit(1)
+        validate_version_change_diff(version_diff_output, "master", version)
 
         # Double check that we want to push the release.
         if not args.dry_run:
@@ -104,10 +91,7 @@
 
         maybe_check_call(args, [
           'git', 'push', 'origin', 'HEAD:%s' % R8_DEV_BRANCH])
-        maybe_check_call(args, [
-          'git', 'tag', '-a', version, '-m', '"%s"' % version])
-        maybe_check_call(args, [
-          'git', 'push', 'origin', 'refs/tags/%s' % version])
+        maybe_tag(args, version)
 
         return "%s dev version %s from hash %s" % (
           'DryRun: omitted publish of' if args.dry_run else 'Published',
@@ -117,6 +101,12 @@
   return make_release
 
 
+def maybe_tag(args, version):
+  maybe_check_call(args, [
+    'git', 'tag', '-a', version, '-m', '"%s"' % version])
+  maybe_check_call(args, [
+    'git', 'push', 'origin', 'refs/tags/%s' % version])
+
 def version_change_diff(diff, old_version, new_version):
   invalid_line = None
   for line in diff.splitlines():
@@ -128,6 +118,22 @@
       invalid_line = line
   return invalid_line
 
+def validate_version_change_diff(version_diff_output, old_version, new_version):
+  invalid = version_change_diff(version_diff_output, old_version, new_version)
+  if invalid:
+    print "Unexpected diff:"
+    print "=" * 80
+    print version_diff_output
+    print "=" * 80
+    accept_string = 'THE DIFF IS OK!'
+    input = raw_input(
+      "Accept the additonal diff as part of the release? "
+      "Type '%s' to accept: " % accept_string)
+    if input != accept_string:
+      print "You did not type '%s'" % accept_string
+      print 'Aborting dev release for %s' % version
+      sys.exit(1)
+
 
 def maybe_check_call(args, cmd):
   if args.dry_run:
@@ -344,6 +350,62 @@
   return release_google3
 
 
+def prepare_branch(args):
+  branch_version = args.new_dev_branch[0]
+  commithash = args.new_dev_branch[1]
+
+  current_semver = utils.check_basic_semver_version(
+    R8_DEV_BRANCH, ", current release branch version should be x.y", 2)
+  semver = utils.check_basic_semver_version(
+    branch_version, ", release branch version should be x.y", 2)
+  if not semver.larger_than(current_semver):
+    print ('New branch version "'
+      + branch_version
+      + '" must be strictly larger than the current "'
+      + R8_DEV_BRANCH
+      + '"')
+    sys.exit(1)
+
+  def make_branch(options):
+    subprocess.check_call(['git', 'branch', branch_version, commithash])
+
+    subprocess.check_call(['git', 'checkout', branch_version])
+
+    # Rewrite the version, commit and validate.
+    old_version = 'master'
+    full_version = branch_version + '.0-dev'
+    version_prefix = 'LABEL = "'
+    sed(version_prefix + old_version,
+      version_prefix + full_version,
+      R8_VERSION_FILE)
+
+    subprocess.check_call([
+      'git', 'commit', '-a', '-m', 'Version %s' % full_version])
+
+    version_diff_output = subprocess.check_output([
+      'git', 'diff', '%s..HEAD' % commithash])
+
+    validate_version_change_diff(version_diff_output, old_version, full_version)
+
+    # Double check that we want to create a new release branch.
+    if not options.dry_run:
+      input = raw_input('Create new branch for %s [y/N]:' % branch_version)
+      if input != 'y':
+        print 'Aborting new branch for %s' % branch_version
+        sys.exit(1)
+
+    maybe_check_call(options, [
+      'git', 'push', 'origin', 'HEAD:%s' % branch_version])
+    maybe_tag(options, full_version)
+
+    # TODO(sgjesse): Automate this part as well!
+    print ('REMEMBER TO UPDATE R8_DEV_BRANCH in tools/r8_release.py to "'
+      + full_version
+      + '"!!!')
+
+  return make_branch
+
+
 def parse_options():
   result = argparse.ArgumentParser(description='Release r8')
   group = result.add_mutually_exclusive_group()
@@ -351,6 +413,10 @@
                       help='The hash to use for the new dev version of R8')
   group.add_argument('--version',
                       help='The new version of R8 (e.g., 1.4.51)')
+  group.add_argument('--new-dev-branch',
+                      nargs=2,
+                      metavar=('VERSION', 'HASH'),
+                      help='Create a new branch starting a version line')
   result.add_argument('--no-sync', '--no_sync',
                       default=False,
                       action='store_true',
@@ -389,6 +455,12 @@
   args = parse_options()
   targets_to_run = []
 
+  if args.new_dev_branch:
+    if args.google3 or args.studio or args.aosp:
+      print 'Cannot create a branch and roll at the same time.'
+      sys.exit(1)
+    targets_to_run.append(prepare_branch(args))
+
   if args.dev_release:
     if args.google3 or args.studio or args.aosp:
       print 'Cannot create a dev release and roll at the same time.'
diff --git a/tools/run_on_as_app.py b/tools/run_on_as_app.py
index 8d7264b..d45364d 100755
--- a/tools/run_on_as_app.py
+++ b/tools/run_on_as_app.py
@@ -412,7 +412,8 @@
      print 'Running with wrapper that will kill java after'
 
  def __exit__(self, *_):
-   subprocess.call(['pkill', 'java'])
+   if self.active:
+     subprocess.call(['pkill', 'java'])
 
 def GetAllApps():
   apps = []
@@ -623,39 +624,45 @@
       apk_dest = None
 
       result = {}
-      try:
-        out_dir = os.path.join(checkout_dir, 'out', shrinker)
-        (apk_dest, profile_dest_dir, proguard_config_file) = \
-            BuildAppWithShrinker(
-                app, repo, shrinker, checkout_dir, out_dir, temp_dir,
-                options)
-        dex_size = ComputeSizeOfDexFilesInApk(apk_dest)
-        result['apk_dest'] = apk_dest
-        result['build_status'] = 'success'
-        result['dex_size'] = dex_size
-        result['profile_dest_dir'] = profile_dest_dir
+      proguard_config_file = None
+      if not options.r8_compilation_steps_only:
+        try:
+          out_dir = os.path.join(checkout_dir, 'out', shrinker)
+          (apk_dest, profile_dest_dir, res_proguard_config_file) = \
+              BuildAppWithShrinker(
+                  app, repo, shrinker, checkout_dir, out_dir, temp_dir,
+                  options)
+          proguard_config_file = res_proguard_config_file
+          dex_size = ComputeSizeOfDexFilesInApk(apk_dest)
+          result['apk_dest'] = apk_dest
+          result['build_status'] = 'success'
+          result['dex_size'] = dex_size
+          result['profile_dest_dir'] = profile_dest_dir
 
-        profile = as_utils.ParseProfileReport(profile_dest_dir)
-        result['profile'] = {
-            task_name:duration for task_name, duration in profile.iteritems()
-            if as_utils.IsGradleCompilerTask(task_name, shrinker)}
-      except Exception as e:
-        warn('Failed to build {} with {}'.format(app.name, shrinker))
-        if e:
-          print('Error: ' + str(e))
-        result['build_status'] = 'failed'
+          profile = as_utils.ParseProfileReport(profile_dest_dir)
+          result['profile'] = {
+              task_name:duration for task_name, duration in profile.iteritems()
+              if as_utils.IsGradleCompilerTask(task_name, shrinker)}
+        except Exception as e:
+          warn('Failed to build {} with {}'.format(app.name, shrinker))
+          if e:
+            print('Error: ' + str(e))
+          result['build_status'] = 'failed'
 
       if result.get('build_status') == 'success':
         if options.monkey:
           result['monkey_status'] = 'success' if RunMonkey(
               app, options, apk_dest) else 'failed'
 
+      if (result.get('build_status') == 'success'
+          or options.r8_compilation_steps_only):
         if 'r8' in shrinker and options.r8_compilation_steps > 1:
           result['recompilation_results'] = \
               ComputeRecompilationResults(
                   app, repo, options, checkout_dir, temp_dir, shrinker,
                   proguard_config_file)
 
+      if result.get('build_status') == 'success':
         if options.run_tests and app.has_instrumentation_tests:
           result['instrumentation_test_results'] = \
               ComputeInstrumentationTestResults(
@@ -851,15 +858,17 @@
   }
   recompilation_results.append(recompilation_result)
 
-  # Sanity check that keep rules have changed.
-  with open(ext_proguard_config_file) as new:
-    with open(proguard_config_file) as old:
-      assert(
-          sum(1 for line in new
-              if line.strip() and '-printconfiguration' not in line)
-          >
-          sum(1 for line in old
-              if line.strip() and '-printconfiguration' not in line))
+  # Sanity check that keep rules have changed. If we are only doing
+  # recompilation, the passed in proguard_config_file is None.
+  if proguard_config_file:
+    with open(ext_proguard_config_file) as new:
+      with open(proguard_config_file) as old:
+        assert(
+            sum(1 for line in new
+                if line.strip() and '-printconfiguration' not in line)
+            >
+            sum(1 for line in old
+                if line.strip() and '-printconfiguration' not in line))
 
   # Extract min-sdk and target-sdk
   (min_sdk, compile_sdk) = \
@@ -1017,22 +1026,24 @@
       continue
     result = result_per_shrinker.get(shrinker)
     build_status = result.get('build_status')
-    if build_status != 'success':
+    if build_status != 'success' and build_status is not None:
       app_error = True
       warn('  {}: {}'.format(shrinker, build_status))
-    else:
-      print('  {}:'.format(shrinker))
-      dex_size = result.get('dex_size')
-      msg = '    dex size: {}'.format(dex_size)
-      if dex_size != proguard_dex_size and proguard_dex_size >= 0:
-        msg = '{} ({}, {})'.format(
-            msg, dex_size - proguard_dex_size,
-            PercentageDiffAsString(proguard_dex_size, dex_size))
-        success(msg) if dex_size < proguard_dex_size else warn(msg)
-      else:
-        print(msg)
+      continue
 
-      profile = result.get('profile')
+    print('  {}:'.format(shrinker))
+    dex_size = result.get('dex_size')
+    msg = '    dex size: {}'.format(dex_size)
+    if dex_size != proguard_dex_size and proguard_dex_size >= 0:
+      msg = '{} ({}, {})'.format(
+          msg, dex_size - proguard_dex_size,
+          PercentageDiffAsString(proguard_dex_size, dex_size))
+      success(msg) if dex_size < proguard_dex_size else warn(msg)
+    else:
+      print(msg)
+
+    profile = result.get('profile')
+    if profile:
       duration = sum(profile.values())
       msg = '    performance: {}s'.format(duration)
       if duration != proguard_duration and proguard_duration > 0:
@@ -1046,53 +1057,53 @@
         for task_name, task_duration in profile.iteritems():
           print('      {}: {}s'.format(task_name, task_duration))
 
-      if options.monkey:
-        monkey_status = result.get('monkey_status')
-        if monkey_status != 'success':
-          app_error = True
-          warn('    monkey: {}'.format(monkey_status))
-        else:
-          success('    monkey: {}'.format(monkey_status))
+    if options.monkey:
+      monkey_status = result.get('monkey_status')
+      if monkey_status != 'success':
+        app_error = True
+        warn('    monkey: {}'.format(monkey_status))
+      else:
+        success('    monkey: {}'.format(monkey_status))
 
-      recompilation_results = result.get('recompilation_results', [])
-      i = 0
-      for recompilation_result in recompilation_results:
-        build_status = recompilation_result.get('build_status')
-        if build_status != 'success':
-          app_error = True
-          print('    recompilation #{}: {}'.format(i, build_status))
-        else:
-          dex_size = recompilation_result.get('dex_size')
-          print('    recompilation #{}'.format(i))
-          print('      dex size: {}'.format(dex_size))
-          if options.monkey:
-            monkey_status = recompilation_result.get('monkey_status')
-            msg = '      monkey: {}'.format(monkey_status)
-            if monkey_status == 'success':
-              success(msg)
-            elif monkey_status == 'skipped':
-              print(msg)
-            else:
-              warn(msg)
-        i += 1
+    recompilation_results = result.get('recompilation_results', [])
+    i = 0
+    for recompilation_result in recompilation_results:
+      build_status = recompilation_result.get('build_status')
+      if build_status != 'success':
+        app_error = True
+        print('    recompilation #{}: {}'.format(i, build_status))
+      else:
+        dex_size = recompilation_result.get('dex_size')
+        print('    recompilation #{}'.format(i))
+        print('      dex size: {}'.format(dex_size))
+        if options.monkey:
+          monkey_status = recompilation_result.get('monkey_status')
+          msg = '      monkey: {}'.format(monkey_status)
+          if monkey_status == 'success':
+            success(msg)
+          elif monkey_status == 'skipped':
+            print(msg)
+          else:
+            warn(msg)
+      i += 1
 
-      if options.run_tests and 'instrumentation_test_results' in result:
-        instrumentation_test_results = \
-            result.get('instrumentation_test_results')
-        succeeded = (
-            instrumentation_test_results.get('failures')
-                + instrumentation_test_results.get('errors')
-                + instrumentation_test_results.get('skipped')) == 0
-        if succeeded:
-          success('    tests: succeeded')
-        else:
-          app_error = True
-          warn(
-              '    tests: failed (failures: {}, errors: {}, skipped: {})'
-              .format(
-                  instrumentation_test_results.get('failures'),
-                  instrumentation_test_results.get('errors'),
-                  instrumentation_test_results.get('skipped')))
+    if options.run_tests and 'instrumentation_test_results' in result:
+      instrumentation_test_results = \
+          result.get('instrumentation_test_results')
+      succeeded = (
+          instrumentation_test_results.get('failures')
+              + instrumentation_test_results.get('errors')
+              + instrumentation_test_results.get('skipped')) == 0
+      if succeeded:
+        success('    tests: succeeded')
+      else:
+        app_error = True
+        warn(
+            '    tests: failed (failures: {}, errors: {}, skipped: {})'
+            .format(
+                instrumentation_test_results.get('failures'),
+                instrumentation_test_results.get('errors'),
+                instrumentation_test_results.get('skipped')))
 
   return app_error
 
@@ -1172,6 +1183,10 @@
                     help='Number of times R8 should be run on each app',
                     default=2,
                     type=int)
+  result.add_option('--r8-compilation-steps-only', '--r8_compilation_steps_only',
+                    help='Specify to only run compilation steps',
+                    default=False,
+                    action='store_true')
   result.add_option('--run-tests', '--run_tests',
                     help='Whether to run instrumentation tests',
                     default=False,
@@ -1215,6 +1230,8 @@
       warn('Skipping shrinker r8-nolib-full because a specific version '
           + 'of r8 was specified')
       options.shrinker.remove('r8-nolib-full')
+  assert not options.r8_compilation_steps_only \
+         or options.r8_compilation_steps > 1
   return (options, args)
 
 def clone_repositories(quiet):
diff --git a/tools/utils.py b/tools/utils.py
index 67ead07..733d190 100644
--- a/tools/utils.py
+++ b/tools/utils.py
@@ -579,12 +579,46 @@
     check_basic_semver_version(version, 'in ' + DESUGAR_CONFIGURATION)
     return version
 
+class SemanticVersion:
+  def __init__(self, major, minor, patch):
+    self.major = major
+    self.minor = minor
+    self.patch = patch
+    # Build metadata currently not suppported
+
+  def larger_than(self, other):
+    if self.major > other.major:
+      return True
+    if self.major == other.major and self.minor > other.minor:
+      return True
+    if self.patch:
+      return (self.major == other.major
+        and self.minor == other.minor
+        and self.patch > other.patch)
+    else:
+      return False
+
+
 # Check that the passed string is formatted as a basic semver version (x.y.z)
 # See https://semver.org/.
-def check_basic_semver_version(version, error_context = ''):
-    reg = re.compile('^([0-9]+)\\.([0-9]+)\\.([0-9]+)$')
-    if not reg.match(version):
+def check_basic_semver_version(version, error_context = '', components = 3):
+    regexp = '^'
+    for x in range(components):
+      regexp += '([0-9]+)'
+      if x < components - 1:
+        regexp += '\\.'
+    regexp += '$'
+    reg = re.compile(regexp)
+    match = reg.match(version)
+    if not match:
       raise Exception("Invalid version '"
             + version
             + "'"
             + (' ' + error_context) if len(error_context) > 0 else '')
+    if components == 2:
+      return SemanticVersion(int(match.group(1)), int(match.group(2)), None)
+    elif components == 3:
+      return SemanticVersion(
+        int(match.group(1)), int(match.group(2)), int(match.group(3)))
+    else:
+      raise Exception('Argument "components" must be 2 or 3')