diff --git a/infra/config/global/generated/luci-scheduler.cfg b/infra/config/global/generated/luci-scheduler.cfg
index 58167f9..2c77bc7 100644
--- a/infra/config/global/generated/luci-scheduler.cfg
+++ b/infra/config/global/generated/luci-scheduler.cfg
@@ -403,7 +403,7 @@
   triggering_policy {
     kind: GREEDY_BATCHING
     max_concurrent_invocations: 1
-    max_batch_size: 1
+    max_batch_size: 20
   }
   buildbucket {
     server: "cr-buildbucket.appspot.com"
diff --git a/infra/config/global/main.star b/infra/config/global/main.star
index 303dffe..4949fc2 100755
--- a/infra/config/global/main.star
+++ b/infra/config/global/main.star
@@ -306,7 +306,7 @@
         triggering_policy = scheduler.policy(
             kind = scheduler.GREEDY_BATCHING_KIND,
             max_concurrent_invocations = 1,
-            max_batch_size = 1
+            max_batch_size = 1 if "release" in name else 20
         ),
         priority = 25,
         properties = {
diff --git a/src/main/java/com/android/tools/r8/FeatureSplit.java b/src/main/java/com/android/tools/r8/FeatureSplit.java
index 9b55bde..43e553c 100644
--- a/src/main/java/com/android/tools/r8/FeatureSplit.java
+++ b/src/main/java/com/android/tools/r8/FeatureSplit.java
@@ -44,6 +44,11 @@
         public boolean isBase() {
           return true;
         }
+
+        @Override
+        public boolean isStartupBase() {
+          return true;
+        }
       };
 
   private final ProgramConsumer programConsumer;
@@ -59,6 +64,10 @@
     return false;
   }
 
+  public boolean isStartupBase() {
+    return false;
+  }
+
   public List<ProgramResourceProvider> getProgramResourceProviders() {
     return programResourceProviders;
   }
diff --git a/src/main/java/com/android/tools/r8/androidapi/AndroidApiClass.java b/src/main/java/com/android/tools/r8/androidapi/AndroidApiClass.java
index 977a836..2477240 100644
--- a/src/main/java/com/android/tools/r8/androidapi/AndroidApiClass.java
+++ b/src/main/java/com/android/tools/r8/androidapi/AndroidApiClass.java
@@ -30,28 +30,28 @@
 
   public abstract int getMemberCount();
 
-  public TraversalContinuation<?> visitFields(
-      BiFunction<FieldReference, AndroidApiLevel, TraversalContinuation<?>> visitor) {
+  public TraversalContinuation<?, ?> visitFields(
+      BiFunction<FieldReference, AndroidApiLevel, TraversalContinuation<?, ?>> visitor) {
     return visitFields(visitor, classReference, 1);
   }
 
-  public TraversalContinuation<?> visitMethods(
-      BiFunction<MethodReference, AndroidApiLevel, TraversalContinuation<?>> visitor) {
+  public TraversalContinuation<?, ?> visitMethods(
+      BiFunction<MethodReference, AndroidApiLevel, TraversalContinuation<?, ?>> visitor) {
     return visitMethods(visitor, classReference, 1);
   }
 
-  protected abstract TraversalContinuation<?> visitFields(
-      BiFunction<FieldReference, AndroidApiLevel, TraversalContinuation<?>> visitor,
+  protected abstract TraversalContinuation<?, ?> visitFields(
+      BiFunction<FieldReference, AndroidApiLevel, TraversalContinuation<?, ?>> visitor,
       ClassReference holder,
       int minApiClass);
 
-  protected abstract TraversalContinuation<?> visitMethods(
-      BiFunction<MethodReference, AndroidApiLevel, TraversalContinuation<?>> visitor,
+  protected abstract TraversalContinuation<?, ?> visitMethods(
+      BiFunction<MethodReference, AndroidApiLevel, TraversalContinuation<?, ?>> visitor,
       ClassReference holder,
       int minApiClass);
 
-  protected TraversalContinuation<?> visitField(
-      BiFunction<FieldReference, AndroidApiLevel, TraversalContinuation<?>> visitor,
+  protected TraversalContinuation<?, ?> visitField(
+      BiFunction<FieldReference, AndroidApiLevel, TraversalContinuation<?, ?>> visitor,
       ClassReference holder,
       int minApiClass,
       int minApiField,
@@ -62,8 +62,8 @@
         getAndroidApiLevel(Integer.max(minApiClass, minApiField)));
   }
 
-  protected TraversalContinuation<?> visitMethod(
-      BiFunction<MethodReference, AndroidApiLevel, TraversalContinuation<?>> visitor,
+  protected TraversalContinuation<?, ?> visitMethod(
+      BiFunction<MethodReference, AndroidApiLevel, TraversalContinuation<?, ?>> visitor,
       ClassReference holder,
       int minApiClass,
       int minApiMethod,
diff --git a/src/main/java/com/android/tools/r8/dex/VirtualFile.java b/src/main/java/com/android/tools/r8/dex/VirtualFile.java
index 827f43bd..7f39bfc 100644
--- a/src/main/java/com/android/tools/r8/dex/VirtualFile.java
+++ b/src/main/java/com/android/tools/r8/dex/VirtualFile.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.dex;
 
 import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
+import static com.google.common.base.Predicates.alwaysFalse;
 
 import com.android.tools.r8.FeatureSplit;
 import com.android.tools.r8.debuginfo.DebugRepresentation;
@@ -29,6 +30,7 @@
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.MainDexInfo;
+import com.android.tools.r8.synthesis.SyntheticItems;
 import com.android.tools.r8.synthesis.SyntheticNaming;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.FileUtils;
@@ -39,20 +41,20 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterators;
 import com.google.common.collect.Sets;
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.IdentityHashMap;
 import java.util.Iterator;
-import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
-import java.util.TreeSet;
-import java.util.concurrent.Callable;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.function.Function;
@@ -62,12 +64,6 @@
 
   public static final int MAX_ENTRIES = Constants.U16BIT_MAX + 1;
 
-  /**
-   * When distributing classes across files we aim to leave some space. The amount of space left is
-   * driven by this constant.
-   */
-  private static final int MAX_PREFILL_ENTRIES = MAX_ENTRIES - 5000;
-
   private final int id;
   private final VirtualFileIndexedItemCollection indexedItems;
   private final IndexedItemTransaction transaction;
@@ -187,22 +183,6 @@
     return originalNames;
   }
 
-  private static String extractPrefixToken(int prefixLength, String className, boolean addStar) {
-    int index = 0;
-    int lastIndex = 0;
-    int segmentCount = 0;
-    while (lastIndex != -1 && segmentCount++ < prefixLength) {
-      index = lastIndex;
-      lastIndex = className.indexOf('.', index + 1);
-    }
-    String prefix = className.substring(0, index);
-    if (addStar && segmentCount >= prefixLength) {
-      // Full match, add a * to also match sub-packages.
-      prefix += ".*";
-    }
-    return prefix;
-  }
-
   private ObjectToOffsetMapping objectMapping = null;
 
   public ObjectToOffsetMapping getObjectMapping() {
@@ -427,38 +407,6 @@
       mainDexFile.throwIfFull(true, options.reporter);
     }
 
-    TreeSet<DexProgramClass> sortClassesByPackage(Set<DexProgramClass> classes,
-        Map<DexProgramClass, String> originalNames) {
-      TreeSet<DexProgramClass> sortedClasses = new TreeSet<>(
-          (DexProgramClass a, DexProgramClass b) -> {
-            String originalA = originalNames.get(a);
-            String originalB = originalNames.get(b);
-            int indexA = originalA.lastIndexOf('.');
-            int indexB = originalB.lastIndexOf('.');
-            if (indexA == -1 && indexB == -1) {
-              // Empty package, compare the class names.
-              return originalA.compareTo(originalB);
-            }
-            if (indexA == -1) {
-              // Empty package name comes first.
-              return -1;
-            }
-            if (indexB == -1) {
-              // Empty package name comes first.
-              return 1;
-            }
-            String prefixA = originalA.substring(0, indexA);
-            String prefixB = originalB.substring(0, indexB);
-            int result = prefixA.compareTo(prefixB);
-            if (result != 0) {
-              return result;
-            }
-            return originalA.compareTo(originalB);
-          });
-      sortedClasses.addAll(classes);
-      return sortedClasses;
-    }
-
     protected Map<FeatureSplit, Set<DexProgramClass>> removeFeatureSplitClassesGetMapping() {
       assert appView.appInfo().hasClassHierarchy() == appView.enableWholeProgramOptimizations();
       if (!appView.appInfo().hasClassHierarchy()) {
@@ -482,8 +430,8 @@
       return featureSplitClasses;
     }
 
-    protected void addFeatureSplitFiles(Map<FeatureSplit, Set<DexProgramClass>> featureSplitClasses)
-        throws IOException {
+    protected void addFeatureSplitFiles(
+        Map<FeatureSplit, Set<DexProgramClass>> featureSplitClasses) {
       if (featureSplitClasses.isEmpty()) {
         return;
       }
@@ -499,19 +447,15 @@
                 featureSplitSetEntry.getKey());
         virtualFiles.add(featureFile);
         addMarkers(featureFile);
-        Set<DexProgramClass> featureClasses =
-            sortClassesByPackage(featureSplitSetEntry.getValue(), originalNames);
         filesForDistribution = virtualFiles.subList(virtualFiles.size() - 1, virtualFiles.size());
-
         new PackageSplitPopulator(
                 filesForDistribution,
                 appView,
-                featureClasses,
+                featureSplitSetEntry.getValue(),
                 originalNames,
                 0,
-                writer.namingLens,
-                options)
-            .call();
+                writer.namingLens)
+            .run();
       }
     }
   }
@@ -564,18 +508,14 @@
                 executorService)
             .distribute();
       } else {
-        // Sort the remaining classes based on the original names.
-        // This with make classes from the same package be adjacent.
-        classes = sortClassesByPackage(classes, originalNames);
         new PackageSplitPopulator(
                 filesForDistribution,
                 appView,
                 classes,
                 originalNames,
                 fileIndexOffset,
-                writer.namingLens,
-                options)
-            .call();
+                writer.namingLens)
+            .run();
       }
       addFeatureSplitFiles(featureSplitClasses);
 
@@ -974,7 +914,100 @@
    * <p>The populator cycles through the files until all classes have been successfully placed and
    * adds new files to the passed in map if it can't fit in the existing files.
    */
-  private static class PackageSplitPopulator implements Callable<Map<String, Integer>> {
+  private static class PackageSplitPopulator {
+
+    static class PackageSplitClassPartioning {
+
+      // The set of startup classes, sorted by original names so that classes in the same package
+      // are adjacent. This is empty if no startup configuration is given.
+      private final List<DexProgramClass> startupClasses;
+
+      // The remaining set of classes that must be written, sorted by original names so that classes
+      // in the same package are adjacent.
+      private final List<DexProgramClass> nonStartupClasses;
+
+      private PackageSplitClassPartioning(
+          List<DexProgramClass> startupClasses, List<DexProgramClass> nonStartupClasses) {
+        this.startupClasses = startupClasses;
+        this.nonStartupClasses = nonStartupClasses;
+      }
+
+      public static PackageSplitClassPartioning create(
+          Collection<DexProgramClass> classes,
+          AppView<?> appView,
+          Map<DexProgramClass, String> originalNames) {
+        return create(
+            classes,
+            getClassesByPackageComparator(originalNames),
+            getStartupClassPredicate(appView));
+      }
+
+      private static PackageSplitClassPartioning create(
+          Collection<DexProgramClass> classes,
+          Comparator<DexProgramClass> comparator,
+          Predicate<DexProgramClass> startupClassPredicate) {
+        List<DexProgramClass> startupClasses = new ArrayList<>();
+        List<DexProgramClass> nonStartupClasses = new ArrayList<>(classes.size());
+        for (DexProgramClass clazz : classes) {
+          if (startupClassPredicate.test(clazz)) {
+            startupClasses.add(clazz);
+          } else {
+            nonStartupClasses.add(clazz);
+          }
+        }
+        startupClasses.sort(comparator);
+        nonStartupClasses.sort(comparator);
+        return new PackageSplitClassPartioning(startupClasses, nonStartupClasses);
+      }
+
+      private static Comparator<DexProgramClass> getClassesByPackageComparator(
+          Map<DexProgramClass, String> originalNames) {
+        return (a, b) -> {
+          String originalA = originalNames.get(a);
+          String originalB = originalNames.get(b);
+          int indexA = originalA.lastIndexOf('.');
+          int indexB = originalB.lastIndexOf('.');
+          if (indexA == -1 && indexB == -1) {
+            // Empty package, compare the class names.
+            return originalA.compareTo(originalB);
+          }
+          if (indexA == -1) {
+            // Empty package name comes first.
+            return -1;
+          }
+          if (indexB == -1) {
+            // Empty package name comes first.
+            return 1;
+          }
+          String prefixA = originalA.substring(0, indexA);
+          String prefixB = originalB.substring(0, indexB);
+          int result = prefixA.compareTo(prefixB);
+          if (result != 0) {
+            return result;
+          }
+          return originalA.compareTo(originalB);
+        };
+      }
+
+      private static Predicate<DexProgramClass> getStartupClassPredicate(AppView<?> appView) {
+        if (!appView.hasClassHierarchy()) {
+          return alwaysFalse();
+        }
+        ClassToFeatureSplitMap classToFeatureSplitMap =
+            appView.appInfo().withClassHierarchy().getClassToFeatureSplitMap();
+        SyntheticItems syntheticItems = appView.getSyntheticItems();
+        return clazz ->
+            classToFeatureSplitMap.getFeatureSplit(clazz, syntheticItems).isStartupBase();
+      }
+
+      public List<DexProgramClass> getStartupClasses() {
+        return startupClasses;
+      }
+
+      public List<DexProgramClass> getNonStartupClasses() {
+        return nonStartupClasses;
+      }
+    }
 
     /**
      * Android suggests com.company.product for package names, so the components will be at level 4
@@ -988,7 +1021,7 @@
      */
     private static final int MIN_FILL_FACTOR = 5;
 
-    private final List<DexProgramClass> classes;
+    private final PackageSplitClassPartioning classPartioning;
     private final Map<DexProgramClass, String> originalNames;
     private final DexItemFactory dexItemFactory;
     private final InternalOptions options;
@@ -997,15 +1030,14 @@
     PackageSplitPopulator(
         List<VirtualFile> files,
         AppView<?> appView,
-        Set<DexProgramClass> classes,
+        Collection<DexProgramClass> classes,
         Map<DexProgramClass, String> originalNames,
         int fileIndexOffset,
-        NamingLens namingLens,
-        InternalOptions options) {
-      this.classes = new ArrayList<>(classes);
+        NamingLens namingLens) {
+      this.classPartioning = PackageSplitClassPartioning.create(classes, appView, originalNames);
       this.originalNames = originalNames;
       this.dexItemFactory = appView.dexItemFactory();
-      this.options = options;
+      this.options = appView.options();
       this.cycler = new VirtualFileCycler(files, appView, namingLens, fileIndexOffset);
     }
 
@@ -1022,17 +1054,53 @@
     }
 
     private String getOriginalName(DexProgramClass clazz) {
-      return originalNames != null ? originalNames.get(clazz) : clazz.toString();
+      return originalNames.get(clazz);
     }
 
-    @Override
-    public Map<String, Integer> call() throws IOException {
+    public void run() {
+      addStartupClasses();
+      List<DexProgramClass> nonPackageClasses = addNonStartupClasses();
+      addNonPackageClasses(cycler, nonPackageClasses);
+    }
+
+    private void addStartupClasses() {
+      // In practice, all startup classes should fit in a single dex file, so optimistically try to
+      // commit the startup classes using a single transaction.
+      VirtualFile virtualFile = cycler.next();
+      for (DexProgramClass startupClass : classPartioning.getStartupClasses()) {
+        virtualFile.addClass(startupClass);
+      }
+
+      if (hasSpaceForTransaction(virtualFile, options)) {
+        virtualFile.commitTransaction();
+      } else {
+        virtualFile.abortTransaction();
+
+        // If the above failed, then add the startup classes one by one.
+        for (DexProgramClass startupClass : classPartioning.getStartupClasses()) {
+          virtualFile.addClass(startupClass);
+          if (hasSpaceForTransaction(virtualFile, options)) {
+            virtualFile.commitTransaction();
+          } else {
+            virtualFile.abortTransaction();
+            virtualFile = cycler.addFile();
+            virtualFile.addClass(startupClass);
+            assert hasSpaceForTransaction(virtualFile, options);
+            virtualFile.commitTransaction();
+          }
+        }
+      }
+
+      cycler.restart();
+    }
+
+    private List<DexProgramClass> addNonStartupClasses() {
       int prefixLength = MINIMUM_PREFIX_LENGTH;
       int transactionStartIndex = 0;
-      int fileStartIndex = 0;
       String currentPrefix = null;
-      Map<String, Integer> newPackageAssignments = new LinkedHashMap<>();
+      Object2IntMap<String> packageAssignments = new Object2IntOpenHashMap<>();
       VirtualFile current = cycler.next();
+      List<DexProgramClass> classes = classPartioning.getNonStartupClasses();
       List<DexProgramClass> nonPackageClasses = new ArrayList<>();
       for (int classIndex = 0; classIndex < classes.size(); classIndex++) {
         DexProgramClass clazz = classes.get(classIndex);
@@ -1040,10 +1108,9 @@
         if (!coveredByPrefix(originalName, currentPrefix)) {
           if (currentPrefix != null) {
             current.commitTransaction();
+            assert verifyPackageToVirtualFileAssignment(packageAssignments, currentPrefix, current);
             // Reset the cycler to again iterate over all files, starting with the current one.
             cycler.restart();
-            assert !newPackageAssignments.containsKey(currentPrefix);
-            newPackageAssignments.put(currentPrefix, current.id);
             // Try to reduce the prefix length if possible. Only do this on a successful commit.
             prefixLength = MINIMUM_PREFIX_LENGTH - 1;
           }
@@ -1067,58 +1134,93 @@
           }
           transactionStartIndex = classIndex;
         }
-        if (currentPrefix != null) {
-          assert clazz.superType != null || clazz.type == dexItemFactory.objectType;
-          current.addClass(clazz);
-        } else {
+
+        if (currentPrefix == null) {
           assert clazz.superType != null;
           // We don't have a package, add this to a list of classes that we will add last.
-          assert current.transaction.classes.isEmpty();
+          assert current.transaction.isEmpty();
           nonPackageClasses.add(clazz);
           continue;
         }
-        if (isFullEnough(current, options)) {
-          current.abortTransaction();
-          // We allow for a final rollback that has at most 20% of classes in it.
-          // This is a somewhat random number that was empirically chosen.
-          if (classIndex - transactionStartIndex > (classIndex - fileStartIndex) / MIN_FILL_FACTOR
-              && prefixLength < MAXIMUM_PREFIX_LENGTH) {
-            prefixLength++;
-          } else {
-            // Reset the state to after the last commit and cycle through files.
-            // The idea is that we do not increase the number of files, so it has to fit
-            // somewhere.
-            fileStartIndex = transactionStartIndex;
-            if (!cycler.hasNext()) {
-              // Special case where we simply will never be able to fit the current package into
-              // one dex file. This is currently the case for Strings in jumbo tests, see:
-              // b/33227518
-              if (current.transaction.getNumberOfClasses() == 0) {
-                for (int j = transactionStartIndex; j <= classIndex; j++) {
-                  nonPackageClasses.add(classes.get(j));
-                }
-                transactionStartIndex = classIndex + 1;
-              }
-              // All files are filled up to the 20% mark.
-              cycler.addFile();
-            }
-            current = cycler.next();
-          }
-          currentPrefix = null;
+
+        assert clazz.superType != null || clazz.type == dexItemFactory.objectType;
+        current.addClass(clazz);
+
+        if (hasSpaceForTransaction(current, options)) {
+          continue;
+        }
+
+        int numberOfClassesInTransaction = classIndex - transactionStartIndex + 1;
+        int numberOfClassesInVirtualFileWithTransaction = current.getNumberOfClasses();
+
+        current.abortTransaction();
+
+        // We allow for a final rollback that has at most 20% of classes in it.
+        // This is a somewhat random number that was empirically chosen.
+        if (numberOfClassesInTransaction
+                > numberOfClassesInVirtualFileWithTransaction / MIN_FILL_FACTOR
+            && prefixLength < MAXIMUM_PREFIX_LENGTH) {
           // Go back to previous start index.
           classIndex = transactionStartIndex - 1;
-          assert current != null;
+          currentPrefix = null;
+          prefixLength++;
+          continue;
         }
+
+        // Reset the state to after the last commit and cycle through files.
+        // The idea is that we do not increase the number of files, so it has to fit somewhere.
+        if (!cycler.hasNext()) {
+          // Special case where we simply will never be able to fit the current package into
+          // one dex file. This is currently the case for Strings in jumbo tests, see b/33227518.
+          if (current.isEmpty()) {
+            for (int j = transactionStartIndex; j <= classIndex; j++) {
+              nonPackageClasses.add(classes.get(j));
+            }
+            transactionStartIndex = classIndex + 1;
+          }
+          // All files are filled up to the 20% mark.
+          cycler.addFile();
+        }
+
+        // Go back to previous start index.
+        classIndex = transactionStartIndex - 1;
+        current = cycler.next();
+        currentPrefix = null;
+        prefixLength = MINIMUM_PREFIX_LENGTH;
       }
+
       current.commitTransaction();
-      assert !newPackageAssignments.containsKey(currentPrefix);
-      if (currentPrefix != null) {
-        newPackageAssignments.put(currentPrefix, current.id);
+      assert currentPrefix == null
+          || verifyPackageToVirtualFileAssignment(packageAssignments, currentPrefix, current);
+
+      return nonPackageClasses;
+    }
+
+    private static String extractPrefixToken(int prefixLength, String className, boolean addStar) {
+      int index = 0;
+      int lastIndex = 0;
+      int segmentCount = 0;
+      while (lastIndex != -1 && segmentCount++ < prefixLength) {
+        index = lastIndex;
+        lastIndex = className.indexOf('.', index + 1);
       }
-      if (nonPackageClasses.size() > 0) {
-        addNonPackageClasses(cycler, nonPackageClasses);
+      String prefix = className.substring(0, index);
+      if (addStar && segmentCount >= prefixLength) {
+        // Full match, add a * to also match sub-packages.
+        prefix += ".*";
       }
-      return newPackageAssignments;
+      return prefix;
+    }
+
+    private boolean verifyPackageToVirtualFileAssignment(
+        Object2IntMap<String> packageAssignments, String packageName, VirtualFile virtualFile) {
+      assert !packageAssignments.containsKey(packageName);
+      packageAssignments.put(packageName, virtualFile.getId());
+      return true;
+    }
+
+    private boolean hasSpaceForTransaction(VirtualFile current, InternalOptions options) {
+      return !isFullEnough(current, options);
     }
 
     private boolean isFullEnough(VirtualFile current, InternalOptions options) {
@@ -1131,6 +1233,9 @@
 
     private void addNonPackageClasses(
         VirtualFileCycler cycler, List<DexProgramClass> nonPackageClasses) {
+      if (nonPackageClasses.isEmpty()) {
+        return;
+      }
       cycler.restart();
       VirtualFile current;
       current = cycler.next();
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java b/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java
index f5cb1a3..4c28ff0 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java
@@ -148,12 +148,12 @@
   }
 
   /** Primitive traversal over all (non-interface) superclasses of a given type. */
-  public <T> TraversalContinuation<T> traverseSuperClasses(
-      DexClass clazz, TriFunction<DexType, DexClass, DexClass, TraversalContinuation<T>> fn) {
+  public <B> TraversalContinuation<B, ?> traverseSuperClasses(
+      DexClass clazz, TriFunction<DexType, DexClass, DexClass, TraversalContinuation<B, ?>> fn) {
     DexClass currentClass = clazz;
     while (currentClass != null && currentClass.getSuperType() != null) {
       DexClass superclass = definitionFor(currentClass.getSuperType());
-      TraversalContinuation<T> stepResult =
+      TraversalContinuation<B, ?> stepResult =
           fn.apply(currentClass.getSuperType(), superclass, currentClass);
       if (stepResult.shouldBreak()) {
         return stepResult;
@@ -170,8 +170,9 @@
    * given type is *not* visited. The function indicates if traversal should continue or break. The
    * result of the traversal is BREAK iff the function returned BREAK.
    */
-  public TraversalContinuation<?> traverseSuperTypes(
-      final DexClass clazz, TriFunction<DexType, DexClass, Boolean, TraversalContinuation<?>> fn) {
+  public TraversalContinuation<?, ?> traverseSuperTypes(
+      final DexClass clazz,
+      TriFunction<DexType, DexClass, Boolean, TraversalContinuation<?, ?>> fn) {
     // We do an initial zero-allocation pass over the class super chain as it does not require a
     // worklist/seen-set. Only if the traversal is not aborted and there actually are interfaces,
     // do we continue traversal over the interface types. This is assuming that the second pass
@@ -184,7 +185,8 @@
         if (currentClass.superType == null) {
           break;
         }
-        TraversalContinuation<?> stepResult = fn.apply(currentClass.superType, currentClass, false);
+        TraversalContinuation<?, ?> stepResult =
+            fn.apply(currentClass.superType, currentClass, false);
         if (stepResult.shouldBreak()) {
           return stepResult;
         }
@@ -203,7 +205,7 @@
       while (currentClass != null) {
         for (DexType iface : currentClass.interfaces.values) {
           if (seen.add(iface)) {
-            TraversalContinuation<?> stepResult = fn.apply(iface, currentClass, true);
+            TraversalContinuation<?, ?> stepResult = fn.apply(iface, currentClass, true);
             if (stepResult.shouldBreak()) {
               return stepResult;
             }
@@ -223,7 +225,7 @@
       if (definition != null) {
         for (DexType iface : definition.interfaces.values) {
           if (seen.add(iface)) {
-            TraversalContinuation<?> stepResult = fn.apply(iface, definition, true);
+            TraversalContinuation<?, ?> stepResult = fn.apply(iface, definition, true);
             if (stepResult.shouldBreak()) {
               return stepResult;
             }
@@ -317,7 +319,7 @@
     if (superclass.getType() == dexItemFactory().objectType) {
       return true;
     }
-    TraversalContinuation<Boolean> result =
+    TraversalContinuation<Boolean, ?> result =
         traverseSuperClasses(
             subclass,
             (currentType, currentClass, immediateSubclass) -> {
diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java
index e320709..4fac278 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -356,8 +356,8 @@
     staticFields(predicate).forEach(consumer);
   }
 
-  public TraversalContinuation<?> traverseFields(
-      Function<DexEncodedField, TraversalContinuation<?>> fn) {
+  public TraversalContinuation<?, ?> traverseFields(
+      Function<DexEncodedField, TraversalContinuation<?, ?>> fn) {
     for (DexEncodedField field : fields()) {
       if (fn.apply(field).shouldBreak()) {
         return TraversalContinuation.doBreak();
diff --git a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
index 354cc52..5e30d52 100644
--- a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
@@ -353,32 +353,33 @@
     return null;
   }
 
-  public TraversalContinuation<?> traverseProgramMembers(
-      Function<ProgramMember<?, ?>, TraversalContinuation<?>> fn) {
-    TraversalContinuation<?> continuation = traverseProgramFields(fn);
+  public TraversalContinuation<?, ?> traverseProgramMembers(
+      Function<ProgramMember<?, ?>, TraversalContinuation<?, ?>> fn) {
+    TraversalContinuation<?, ?> continuation = traverseProgramFields(fn);
     if (continuation.shouldContinue()) {
       return traverseProgramMethods(fn);
     }
     return TraversalContinuation.doBreak();
   }
 
-  public TraversalContinuation<?> traverseProgramFields(
-      Function<? super ProgramField, TraversalContinuation<?>> fn) {
+  public TraversalContinuation<?, ?> traverseProgramFields(
+      Function<? super ProgramField, TraversalContinuation<?, ?>> fn) {
     return traverseFields(field -> fn.apply(new ProgramField(this, field)));
   }
 
-  public TraversalContinuation<?> traverseProgramMethods(
-      Function<? super ProgramMethod, TraversalContinuation<?>> fn) {
+  public TraversalContinuation<?, ?> traverseProgramMethods(
+      Function<? super ProgramMethod, TraversalContinuation<?, ?>> fn) {
     return getMethodCollection().traverse(method -> fn.apply(new ProgramMethod(this, method)));
   }
 
-  public TraversalContinuation<?> traverseProgramInstanceInitializers(
-      Function<ProgramMethod, TraversalContinuation<?>> fn) {
+  public TraversalContinuation<?, ?> traverseProgramInstanceInitializers(
+      Function<ProgramMethod, TraversalContinuation<?, ?>> fn) {
     return traverseProgramMethods(fn, DexEncodedMethod::isInstanceInitializer);
   }
 
-  public TraversalContinuation<?> traverseProgramMethods(
-      Function<ProgramMethod, TraversalContinuation<?>> fn, Predicate<DexEncodedMethod> predicate) {
+  public TraversalContinuation<?, ?> traverseProgramMethods(
+      Function<ProgramMethod, TraversalContinuation<?, ?>> fn,
+      Predicate<DexEncodedMethod> predicate) {
     return getMethodCollection()
         .traverse(
             method ->
diff --git a/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java b/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java
index 4354f06..bb94a8e 100644
--- a/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java
+++ b/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java
@@ -130,9 +130,7 @@
     }
     reader.accept(
         new CreateDexClassVisitor<>(origin, classKind, reader.b, application, classConsumer),
-        new Attribute[] {
-          SyntheticMarker.getMarkerAttributePrototype(application.getFactory().getSyntheticNaming())
-        },
+        getAttributePrototypes(),
         parsingOptions);
 
     // Read marker.
@@ -152,6 +150,15 @@
     }
   }
 
+  private Attribute[] getAttributePrototypes() {
+    if (classKind == ClassKind.PROGRAM) {
+      return new Attribute[] {
+        SyntheticMarker.getMarkerAttributePrototype(application.getFactory().getSyntheticNaming())
+      };
+    }
+    return new Attribute[0];
+  }
+
   private static int cleanAccessFlags(int access) {
     // Clear the "synthetic attribute" and "deprecated" attribute-flags if present.
     return access & ~ACC_SYNTHETIC_ATTRIBUTE & ~ACC_DEPRECATED;
diff --git a/src/main/java/com/android/tools/r8/graph/MethodArrayBacking.java b/src/main/java/com/android/tools/r8/graph/MethodArrayBacking.java
index d00dca3..24c8b0a 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodArrayBacking.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodArrayBacking.java
@@ -71,15 +71,15 @@
   }
 
   @Override
-  TraversalContinuation<?> traverse(Function<DexEncodedMethod, TraversalContinuation<?>> fn) {
+  TraversalContinuation<?, ?> traverse(Function<DexEncodedMethod, TraversalContinuation<?, ?>> fn) {
     for (DexEncodedMethod method : directMethods) {
-      TraversalContinuation<?> stepResult = fn.apply(method);
+      TraversalContinuation<?, ?> stepResult = fn.apply(method);
       if (stepResult.shouldBreak()) {
         return stepResult;
       }
     }
     for (DexEncodedMethod method : virtualMethods) {
-      TraversalContinuation<?> stepResult = fn.apply(method);
+      TraversalContinuation<?, ?> stepResult = fn.apply(method);
       if (stepResult.shouldBreak()) {
         return stepResult;
       }
diff --git a/src/main/java/com/android/tools/r8/graph/MethodCollection.java b/src/main/java/com/android/tools/r8/graph/MethodCollection.java
index 1cb7d71..a31e669 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodCollection.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodCollection.java
@@ -117,8 +117,8 @@
     return backing.size();
   }
 
-  public TraversalContinuation<?> traverse(
-      Function<DexEncodedMethod, TraversalContinuation<?>> fn) {
+  public TraversalContinuation<?, ?> traverse(
+      Function<DexEncodedMethod, TraversalContinuation<?, ?>> fn) {
     return backing.traverse(fn);
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java b/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
index 8eacebe..b270516 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
@@ -38,8 +38,8 @@
 
   // Traversal methods.
 
-  abstract TraversalContinuation<?> traverse(
-      Function<DexEncodedMethod, TraversalContinuation<?>> fn);
+  abstract TraversalContinuation<?, ?> traverse(
+      Function<DexEncodedMethod, TraversalContinuation<?, ?>> fn);
 
   /**
    * Return a new backing mapped by the given function.
diff --git a/src/main/java/com/android/tools/r8/graph/MethodCollectionConcurrencyChecked.java b/src/main/java/com/android/tools/r8/graph/MethodCollectionConcurrencyChecked.java
index 17bbae3..0889c63 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodCollectionConcurrencyChecked.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodCollectionConcurrencyChecked.java
@@ -84,10 +84,10 @@
   }
 
   @Override
-  public TraversalContinuation<?> traverse(
-      Function<DexEncodedMethod, TraversalContinuation<?>> fn) {
+  public TraversalContinuation<?, ?> traverse(
+      Function<DexEncodedMethod, TraversalContinuation<?, ?>> fn) {
     assert assertReadEntry();
-    TraversalContinuation<?> result = super.traverse(fn);
+    TraversalContinuation<?, ?> result = super.traverse(fn);
     assert assertReadExit();
     return result;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/MethodMapBacking.java b/src/main/java/com/android/tools/r8/graph/MethodMapBacking.java
index eb5b9be..0e838b9 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodMapBacking.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodMapBacking.java
@@ -100,9 +100,9 @@
   }
 
   @Override
-  TraversalContinuation<?> traverse(Function<DexEncodedMethod, TraversalContinuation<?>> fn) {
+  TraversalContinuation<?, ?> traverse(Function<DexEncodedMethod, TraversalContinuation<?, ?>> fn) {
     for (Entry<DexMethodSignature, DexEncodedMethod> entry : methodMap.entrySet()) {
-      TraversalContinuation<?> result = fn.apply(entry.getValue());
+      TraversalContinuation<?, ?> result = fn.apply(entry.getValue());
       if (result.shouldBreak()) {
         return result;
       }
diff --git a/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollection.java b/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollection.java
index ef1de89..300bca7 100644
--- a/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollection.java
+++ b/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollection.java
@@ -34,10 +34,10 @@
 
   void forEachInstantiatedLambdaInterfaces(Consumer<DexType> consumer);
 
-  TraversalContinuation<?> traverseInstantiatedSubtypes(
+  TraversalContinuation<?, ?> traverseInstantiatedSubtypes(
       DexType type,
-      Function<DexProgramClass, TraversalContinuation<?>> onClass,
-      Function<LambdaDescriptor, TraversalContinuation<?>> onLambda,
+      Function<DexProgramClass, TraversalContinuation<?, ?>> onClass,
+      Function<LambdaDescriptor, TraversalContinuation<?, ?>> onLambda,
       AppInfo appInfo);
 
   ObjectAllocationInfoCollection rewrittenWithLens(
diff --git a/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java b/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
index 6b31147..1aa8117 100644
--- a/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
+++ b/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
@@ -184,10 +184,10 @@
   }
 
   @Override
-  public TraversalContinuation<?> traverseInstantiatedSubtypes(
+  public TraversalContinuation<?, ?> traverseInstantiatedSubtypes(
       DexType type,
-      Function<DexProgramClass, TraversalContinuation<?>> onClass,
-      Function<LambdaDescriptor, TraversalContinuation<?>> onLambda,
+      Function<DexProgramClass, TraversalContinuation<?, ?>> onClass,
+      Function<LambdaDescriptor, TraversalContinuation<?, ?>> onLambda,
       AppInfo appInfo) {
     WorkList<DexClass> worklist = WorkList.newIdentityWorkList();
     if (type == appInfo.dexItemFactory().objectType) {
diff --git a/src/main/java/com/android/tools/r8/graph/UseRegistry.java b/src/main/java/com/android/tools/r8/graph/UseRegistry.java
index 919d940..6e08e6c 100644
--- a/src/main/java/com/android/tools/r8/graph/UseRegistry.java
+++ b/src/main/java/com/android/tools/r8/graph/UseRegistry.java
@@ -15,7 +15,7 @@
   private final AppView<?> appView;
   private final T context;
 
-  private TraversalContinuation<?> continuation = TraversalContinuation.doContinue();
+  private TraversalContinuation<?, ?> continuation = TraversalContinuation.doContinue();
 
   public enum MethodHandleUse {
     ARGUMENT_TO_LAMBDA_METAFACTORY,
@@ -54,7 +54,7 @@
     return context.asMethod();
   }
 
-  public TraversalContinuation<?> getTraversalContinuation() {
+  public TraversalContinuation<?, ?> getTraversalContinuation() {
     return continuation;
   }
 
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/RespectPackageBoundaries.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/RespectPackageBoundaries.java
index 1573dde..5bc0f58 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/RespectPackageBoundaries.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/RespectPackageBoundaries.java
@@ -65,7 +65,7 @@
     // Check that all accesses from [clazz] to classes or members from the current package of
     // [clazz] will continue to work. This is guaranteed if the methods of [clazz] do not access
     // any private or protected classes or members from the current package of [clazz].
-    TraversalContinuation<?> result =
+    TraversalContinuation<?, ?> result =
         clazz.traverseProgramMethods(
             method -> {
               boolean foundIllegalAccess =
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/AbstractTransferFunction.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/AbstractTransferFunction.java
index af7a836..a3013e3 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/AbstractTransferFunction.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/AbstractTransferFunction.java
@@ -4,19 +4,17 @@
 
 package com.android.tools.r8.ir.analysis.framework.intraprocedural;
 
-import com.android.tools.r8.ir.code.BasicBlock;
-import com.android.tools.r8.ir.code.Instruction;
-
 /**
  * A transfer function that defines the abstract semantics of the instructions in the program
  * according to some abstract state {@link StateType}.
  */
-public interface AbstractTransferFunction<StateType extends AbstractState<StateType>> {
+public interface AbstractTransferFunction<
+    Block, Instruction, StateType extends AbstractState<StateType>> {
 
   TransferFunctionResult<StateType> apply(Instruction instruction, StateType state);
 
   default StateType computeBlockEntryState(
-      BasicBlock block, BasicBlock predecessor, StateType predecessorExitState) {
+      Block block, Block predecessor, StateType predecessorExitState) {
     return predecessorExitState;
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/ControlFlowGraph.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/ControlFlowGraph.java
new file mode 100644
index 0000000..5710f6e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/ControlFlowGraph.java
@@ -0,0 +1,42 @@
+// Copyright (c) 2022, 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.analysis.framework.intraprocedural;
+
+import com.android.tools.r8.utils.TraversalContinuation;
+import com.google.common.collect.Iterables;
+import java.util.Collection;
+import java.util.function.BiFunction;
+
+public interface ControlFlowGraph<Block, Instruction> {
+
+  Collection<Block> getPredecessors(Block block);
+
+  Collection<Block> getSuccessors(Block block);
+
+  default boolean hasUniquePredecessor(Block block) {
+    return getPredecessors(block).size() == 1;
+  }
+
+  default Block getUniquePredecessor(Block block) {
+    assert hasUniquePredecessor(block);
+    return Iterables.getOnlyElement(getPredecessors(block));
+  }
+
+  default boolean hasUniqueSuccessor(Block block) {
+    return getSuccessors(block).size() == 1;
+  }
+
+  default boolean hasUniqueSuccessorWithUniquePredecessor(Block block) {
+    return hasUniqueSuccessor(block) && getPredecessors(getUniqueSuccessor(block)).size() == 1;
+  }
+
+  default Block getUniqueSuccessor(Block block) {
+    assert hasUniqueSuccessor(block);
+    return Iterables.getOnlyElement(getSuccessors(block));
+  }
+
+  <BT, CT> TraversalContinuation<BT, CT> traverseInstructions(
+      Block block, BiFunction<Instruction, CT, TraversalContinuation<BT, CT>> fn, CT initialValue);
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/DataflowAnalysisResult.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/DataflowAnalysisResult.java
index a8a1832..8974bbf 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/DataflowAnalysisResult.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/DataflowAnalysisResult.java
@@ -24,8 +24,8 @@
     return false;
   }
 
-  public <StateType extends AbstractState<StateType>>
-      SuccessfulDataflowAnalysisResult<StateType> asSuccessfulAnalysisResult() {
+  public <Block, StateType extends AbstractState<StateType>>
+      SuccessfulDataflowAnalysisResult<Block, StateType> asSuccessfulAnalysisResult() {
     return null;
   }
 
@@ -33,12 +33,13 @@
     return false;
   }
 
-  public static class SuccessfulDataflowAnalysisResult<StateType extends AbstractState<StateType>>
+  public static class SuccessfulDataflowAnalysisResult<
+          Block, StateType extends AbstractState<StateType>>
       extends DataflowAnalysisResult {
 
-    private final Map<BasicBlock, StateType> blockExitStates;
+    private final Map<Block, StateType> blockExitStates;
 
-    public SuccessfulDataflowAnalysisResult(Map<BasicBlock, StateType> blockExitStates) {
+    public SuccessfulDataflowAnalysisResult(Map<Block, StateType> blockExitStates) {
       this.blockExitStates = blockExitStates;
     }
 
@@ -57,7 +58,7 @@
 
     @SuppressWarnings("unchecked")
     @Override
-    public SuccessfulDataflowAnalysisResult<StateType> asSuccessfulAnalysisResult() {
+    public SuccessfulDataflowAnalysisResult<Block, StateType> asSuccessfulAnalysisResult() {
       return this;
     }
   }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraProceduralDataflowAnalysisBase.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraProceduralDataflowAnalysisBase.java
new file mode 100644
index 0000000..969197f
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraProceduralDataflowAnalysisBase.java
@@ -0,0 +1,147 @@
+// Copyright (c) 2022, 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.analysis.framework.intraprocedural;
+
+import com.android.tools.r8.ir.analysis.framework.intraprocedural.DataflowAnalysisResult.FailedDataflowAnalysisResult;
+import com.android.tools.r8.ir.analysis.framework.intraprocedural.DataflowAnalysisResult.SuccessfulDataflowAnalysisResult;
+import com.android.tools.r8.utils.Timing;
+import com.android.tools.r8.utils.TraversalContinuation;
+import com.android.tools.r8.utils.WorkList;
+import java.util.IdentityHashMap;
+import java.util.Map;
+
+/**
+ * This defines a simple fixpoint solver for running an intraprocedural dataflow analysis.
+ *
+ * <p>The solver computes an {@link AbstractState} for each {@link Block} using the {@link
+ * AbstractTransferFunction} which defines the abstract semantics for each instruction.
+ *
+ * <p>Once the fixpoint is reached the analysis returns a {@link SuccessfulDataflowAnalysisResult}.
+ * If the supplied {@link AbstractTransferFunction} returns a {@link FailedTransferFunctionResult}
+ * for a given instruction and abstract state, then the analysis return a {@link
+ * FailedDataflowAnalysisResult}.
+ */
+public class IntraProceduralDataflowAnalysisBase<
+    Block, Instruction, StateType extends AbstractState<StateType>> {
+
+  final StateType bottom;
+
+  final ControlFlowGraph<Block, Instruction> cfg;
+
+  // The transfer function that defines the abstract semantics for each instruction.
+  final AbstractTransferFunction<Block, Instruction, StateType> transfer;
+
+  // The state of the analysis.
+  final Map<Block, StateType> blockExitStates = new IdentityHashMap<>();
+
+  // The entry states for each block that satisfies the predicate
+  // shouldCacheBlockEntryStateFor(block). These entry states can be computed from the exit states
+  // of the predecessors, but doing so can be expensive when a block has many predecessors.
+  final Map<Block, StateType> blockEntryStatesCache = new IdentityHashMap<>();
+
+  public IntraProceduralDataflowAnalysisBase(
+      StateType bottom,
+      ControlFlowGraph<Block, Instruction> cfg,
+      AbstractTransferFunction<Block, Instruction, StateType> transfer) {
+    this.bottom = bottom;
+    this.cfg = cfg;
+    this.transfer = transfer;
+  }
+
+  public DataflowAnalysisResult run(Block root) {
+    return run(root, Timing.empty());
+  }
+
+  public DataflowAnalysisResult run(Block root, Timing timing) {
+    return run(WorkList.newIdentityWorkList(root), timing);
+  }
+
+  private DataflowAnalysisResult run(WorkList<Block> worklist, Timing timing) {
+    while (worklist.hasNext()) {
+      Block initialBlock = worklist.next();
+      Block block = initialBlock;
+      Block end = null;
+      // Compute the abstract state upon entry to the basic block, by joining all the predecessor
+      // exit states.
+      StateType state =
+          timing.time("Compute block entry state", () -> computeBlockEntryState(initialBlock));
+
+      timing.begin("Compute transfers");
+      do {
+        TraversalContinuation<FailedDataflowAnalysisResult, StateType> traversalContinuation =
+            cfg.traverseInstructions(
+                block,
+                (instruction, previousState) -> {
+                  TransferFunctionResult<StateType> transferResult =
+                      transfer.apply(instruction, previousState);
+                  if (transferResult.isFailedTransferResult()) {
+                    timing.end();
+                    return TraversalContinuation.doBreak(new FailedDataflowAnalysisResult());
+                  }
+                  assert transferResult.isAbstractState();
+                  return TraversalContinuation.doContinue(transferResult.asAbstractState());
+                },
+                state);
+        if (traversalContinuation.isBreak()) {
+          return traversalContinuation.asBreak().getValue();
+        }
+        state = traversalContinuation.asContinue().getValue();
+        if (cfg.hasUniqueSuccessorWithUniquePredecessor(block)) {
+          block = cfg.getUniqueSuccessor(block);
+        } else {
+          end = block;
+          block = null;
+        }
+      } while (block != null);
+      timing.end();
+
+      // Update the block exit state, and re-enqueue all successor blocks if the abstract state
+      // changed.
+      if (setBlockExitState(end, state)) {
+        worklist.addAllIgnoringSeenSet(cfg.getSuccessors(end));
+      }
+
+      // Add the computed exit state to the entry state of each successor that satisfies the
+      // predicate shouldCacheBlockEntryStateFor(successor).
+      updateBlockEntryStateCacheForSuccessors(end, state);
+    }
+    return new SuccessfulDataflowAnalysisResult<>(blockExitStates);
+  }
+
+  StateType computeBlockEntryState(Block block) {
+    if (shouldCacheBlockEntryStateFor(block)) {
+      return blockEntryStatesCache.getOrDefault(block, bottom);
+    }
+    StateType result = bottom;
+    for (Block predecessor : cfg.getPredecessors(block)) {
+      StateType edgeState =
+          transfer.computeBlockEntryState(
+              block, predecessor, blockExitStates.getOrDefault(predecessor, bottom));
+      result = result.join(edgeState);
+    }
+    return result;
+  }
+
+  boolean setBlockExitState(Block block, StateType state) {
+    assert !cfg.hasUniqueSuccessorWithUniquePredecessor(block);
+    StateType previous = blockExitStates.put(block, state);
+    assert previous == null || state.isGreaterThanOrEquals(previous);
+    return !state.equals(previous);
+  }
+
+  void updateBlockEntryStateCacheForSuccessors(Block block, StateType state) {
+    for (Block successor : cfg.getSuccessors(block)) {
+      if (shouldCacheBlockEntryStateFor(successor)) {
+        StateType edgeState = transfer.computeBlockEntryState(successor, block, state);
+        StateType previous = blockEntryStatesCache.getOrDefault(successor, bottom);
+        blockEntryStatesCache.put(successor, previous.join(edgeState));
+      }
+    }
+  }
+
+  boolean shouldCacheBlockEntryStateFor(Block block) {
+    return cfg.getPredecessors(block).size() > 2;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java
index 4f00ef0..13a9c42 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java
@@ -4,130 +4,17 @@
 
 package com.android.tools.r8.ir.analysis.framework.intraprocedural;
 
-import com.android.tools.r8.ir.analysis.framework.intraprocedural.DataflowAnalysisResult.FailedDataflowAnalysisResult;
-import com.android.tools.r8.ir.analysis.framework.intraprocedural.DataflowAnalysisResult.SuccessfulDataflowAnalysisResult;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
-import com.android.tools.r8.utils.Timing;
-import com.android.tools.r8.utils.WorkList;
-import java.util.IdentityHashMap;
-import java.util.Map;
 
-/**
- * This defines a simple fixpoint solver for running an intraprocedural dataflow analysis.
- *
- * <p>The solver computes an {@link AbstractState} for each {@link BasicBlock} using the {@link
- * AbstractTransferFunction} which defines the abstract semantics for each instruction.
- *
- * <p>Once the fixpoint is reached the analysis returns a {@link SuccessfulDataflowAnalysisResult}.
- * If the supplied {@link AbstractTransferFunction} returns a {@link FailedTransferFunctionResult}
- * for a given instruction and abstract state, then the analysis return a {@link
- * FailedDataflowAnalysisResult}.
- */
-public class IntraproceduralDataflowAnalysis<StateType extends AbstractState<StateType>> {
-
-  private final StateType bottom;
-
-  // The transfer function that defines the abstract semantics for each instruction.
-  private final AbstractTransferFunction<StateType> transfer;
-
-  // The state of the analysis.
-  private final Map<BasicBlock, StateType> blockExitStates = new IdentityHashMap<>();
-
-  // The entry states for each block that satisfies the predicate
-  // shouldCacheBlockEntryStateFor(block). These entry states can be computed from the exit states
-  // of the predecessors, but doing so can be expensive when a block has many predecessors.
-  private final Map<BasicBlock, StateType> blockEntryStatesCache = new IdentityHashMap<>();
+public class IntraproceduralDataflowAnalysis<StateType extends AbstractState<StateType>>
+    extends IntraProceduralDataflowAnalysisBase<BasicBlock, Instruction, StateType> {
 
   public IntraproceduralDataflowAnalysis(
-      StateType bottom, AbstractTransferFunction<StateType> transfer) {
-    this.bottom = bottom;
-    this.transfer = transfer;
-  }
-
-  public DataflowAnalysisResult run(BasicBlock root) {
-    return run(root, Timing.empty());
-  }
-
-  public DataflowAnalysisResult run(BasicBlock root, Timing timing) {
-    return run(WorkList.newIdentityWorkList(root), timing);
-  }
-
-  private DataflowAnalysisResult run(WorkList<BasicBlock> worklist, Timing timing) {
-    while (worklist.hasNext()) {
-      BasicBlock initialBlock = worklist.next();
-      BasicBlock block = initialBlock;
-      BasicBlock end = null;
-      // Compute the abstract state upon entry to the basic block, by joining all the predecessor
-      // exit states.
-      StateType state =
-          timing.time("Compute block entry state", () -> computeBlockEntryState(initialBlock));
-
-      timing.begin("Compute transfers");
-      do {
-        for (Instruction instruction : block.getInstructions()) {
-          TransferFunctionResult<StateType> transferResult = transfer.apply(instruction, state);
-          if (transferResult.isFailedTransferResult()) {
-            timing.end();
-            return new FailedDataflowAnalysisResult();
-          }
-          assert transferResult.isAbstractState();
-          state = transferResult.asAbstractState();
-        }
-        if (block.hasUniqueSuccessorWithUniquePredecessor()) {
-          block = block.getUniqueSuccessor();
-        } else {
-          end = block;
-          block = null;
-        }
-      } while (block != null);
-      timing.end();
-
-      // Update the block exit state, and re-enqueue all successor blocks if the abstract state
-      // changed.
-      if (setBlockExitState(end, state)) {
-        worklist.addAllIgnoringSeenSet(end.getSuccessors());
-      }
-
-      // Add the computed exit state to the entry state of each successor that satisfies the
-      // predicate shouldCacheBlockEntryStateFor(successor).
-      updateBlockEntryStateCacheForSuccessors(end, state);
-    }
-    return new SuccessfulDataflowAnalysisResult<>(blockExitStates);
-  }
-
-  private StateType computeBlockEntryState(BasicBlock block) {
-    if (shouldCacheBlockEntryStateFor(block)) {
-      return blockEntryStatesCache.getOrDefault(block, bottom);
-    }
-    StateType result = bottom;
-    for (BasicBlock predecessor : block.getPredecessors()) {
-      StateType edgeState =
-          transfer.computeBlockEntryState(
-              block, predecessor, blockExitStates.getOrDefault(predecessor, bottom));
-      result = result.join(edgeState);
-    }
-    return result;
-  }
-
-  private boolean setBlockExitState(BasicBlock block, StateType state) {
-    assert !block.hasUniqueSuccessorWithUniquePredecessor();
-    StateType previous = blockExitStates.put(block, state);
-    assert previous == null || state.isGreaterThanOrEquals(previous);
-    return !state.equals(previous);
-  }
-
-  private void updateBlockEntryStateCacheForSuccessors(BasicBlock block, StateType state) {
-    for (BasicBlock successor : block.getSuccessors()) {
-      if (shouldCacheBlockEntryStateFor(successor)) {
-        StateType edgeState = transfer.computeBlockEntryState(successor, block, state);
-        StateType previous = blockEntryStatesCache.getOrDefault(successor, bottom);
-        blockEntryStatesCache.put(successor, previous.join(edgeState));
-      }
-    }
-  }
-
-  private boolean shouldCacheBlockEntryStateFor(BasicBlock block) {
-    return block.getPredecessors().size() > 2;
+      StateType bottom,
+      IRCode code,
+      AbstractTransferFunction<BasicBlock, Instruction, StateType> transfer) {
+    super(bottom, code, transfer);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index 01b08a8..1544bdd 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -16,6 +16,7 @@
 import com.android.tools.r8.graph.classmerging.MergedClassesCollection;
 import com.android.tools.r8.ir.analysis.TypeChecker;
 import com.android.tools.r8.ir.analysis.VerifyTypesHelper;
+import com.android.tools.r8.ir.analysis.framework.intraprocedural.ControlFlowGraph;
 import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
 import com.android.tools.r8.ir.analysis.type.Nullability;
 import com.android.tools.r8.ir.analysis.type.TypeElement;
@@ -33,6 +34,7 @@
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.SetUtils;
 import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.TraversalContinuation;
 import com.android.tools.r8.utils.WorkList;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
@@ -55,13 +57,14 @@
 import java.util.NoSuchElementException;
 import java.util.Queue;
 import java.util.Set;
+import java.util.function.BiFunction;
 import java.util.function.Consumer;
 import java.util.function.Function;
 import java.util.function.Predicate;
 import java.util.stream.Collectors;
 import java.util.stream.Stream;
 
-public class IRCode implements ValueFactory {
+public class IRCode implements ControlFlowGraph<BasicBlock, Instruction>, ValueFactory {
 
   private static final int MAX_MARKING_COLOR = 0x40000000;
 
@@ -1363,6 +1366,32 @@
     return blocks;
   }
 
+  @Override
+  public Collection<BasicBlock> getPredecessors(BasicBlock block) {
+    return block.getPredecessors();
+  }
+
+  @Override
+  public Collection<BasicBlock> getSuccessors(BasicBlock block) {
+    return block.getSuccessors();
+  }
+
+  @Override
+  public <BT, CT> TraversalContinuation<BT, CT> traverseInstructions(
+      BasicBlock block,
+      BiFunction<Instruction, CT, TraversalContinuation<BT, CT>> fn,
+      CT initialValue) {
+    TraversalContinuation<BT, CT> traversalContinuation =
+        TraversalContinuation.doContinue(initialValue);
+    for (Instruction instruction : block.getInstructions()) {
+      traversalContinuation = fn.apply(instruction, traversalContinuation.asContinue().getValue());
+      if (traversalContinuation.shouldBreak()) {
+        return traversalContinuation;
+      }
+    }
+    return traversalContinuation;
+  }
+
   /**
    * Returns the set of blocks that are reachable from the given source. The source itself is only
    * included if there is a path from the given block to itself.
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/apimodel/ApiInvokeOutlinerDesugaring.java b/src/main/java/com/android/tools/r8/ir/desugar/apimodel/ApiInvokeOutlinerDesugaring.java
index 06fadd9..0ef825c 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/apimodel/ApiInvokeOutlinerDesugaring.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/apimodel/ApiInvokeOutlinerDesugaring.java
@@ -127,7 +127,7 @@
     if (result != null) {
       return result;
     }
-    TraversalContinuation<DexEncodedMethod> traversalResult =
+    TraversalContinuation<DexEncodedMethod, ?> traversalResult =
         appView
             .appInfoForDesugaring()
             .traverseSuperClasses(
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 e011479..86578a2 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
@@ -132,6 +132,7 @@
 import java.util.Arrays;
 import java.util.BitSet;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.IdentityHashMap;
@@ -1231,7 +1232,6 @@
     AssumeRemover assumeRemover = new AssumeRemover(appView, code);
     boolean changed = false;
     boolean mayHaveRemovedTrivialPhi = false;
-    Set<Value> affectedValues = Sets.newIdentityHashSet();
     Set<BasicBlock> blocksToBeRemoved = Sets.newIdentityHashSet();
     ListIterator<BasicBlock> blockIterator = code.listIterator();
     while (blockIterator.hasNext()) {
@@ -1254,29 +1254,45 @@
         }
 
         MethodOptimizationInfo optimizationInfo = target.getDefinition().getOptimizationInfo();
-        if (optimizationInfo.returnsArgument()) {
-          int argumentIndex = optimizationInfo.getReturnedArgument();
-          // Replace the out value of the invoke with the argument and ignore the out value.
-          if (argumentIndex >= 0 && checkArgumentType(invoke, argumentIndex)) {
-            Value argument = invoke.arguments().get(argumentIndex);
-            Value outValue = invoke.outValue();
-            assert outValue.verifyCompatible(argument.outType());
-            // Make sure that we are only narrowing information here. Note, in cases where
-            // we cannot find the definition of types, computing lessThanOrEqual will
-            // return false unless it is object.
-            if (argument.getType().lessThanOrEqual(outValue.getType(), appView)) {
-              affectedValues.addAll(outValue.affectedValues());
-              assumeRemover.markAssumeDynamicTypeUsersForRemoval(outValue);
-              mayHaveRemovedTrivialPhi |= outValue.numberOfPhiUsers() > 0;
-              outValue.replaceUsers(argument);
-              invoke.setOutValue(null);
-              changed = true;
-            }
-          }
+        if (!optimizationInfo.returnsArgument()) {
+          continue;
+        }
+
+        int argumentIndex = optimizationInfo.getReturnedArgument();
+        // Replace the out value of the invoke with the argument and ignore the out value.
+        if (argumentIndex < 0 || !checkArgumentType(invoke, argumentIndex)) {
+          continue;
+        }
+
+        Value argument = invoke.arguments().get(argumentIndex);
+        Value outValue = invoke.outValue();
+        assert outValue.verifyCompatible(argument.outType());
+
+        // Make sure that we are only narrowing information here. Note, in cases where we cannot
+        // find the definition of types, computing lessThanOrEqual will return false unless it is
+        // object.
+        if (!argument.getType().lessThanOrEqual(outValue.getType(), appView)) {
+          continue;
+        }
+
+        Set<Value> affectedValues =
+            argument.getType().equals(outValue.getType())
+                ? Collections.emptySet()
+                : outValue.affectedValues();
+
+        assumeRemover.markAssumeDynamicTypeUsersForRemoval(outValue);
+        mayHaveRemovedTrivialPhi |= outValue.numberOfPhiUsers() > 0;
+        outValue.replaceUsers(argument);
+        invoke.setOutValue(null);
+        changed = true;
+
+        if (!affectedValues.isEmpty()) {
+          new TypeAnalysis(appView).narrowing(affectedValues);
         }
       }
     }
     assumeRemover.removeMarkedInstructions(blocksToBeRemoved).finish();
+    Set<Value> affectedValues = Sets.newIdentityHashSet();
     if (!blocksToBeRemoved.isEmpty()) {
       code.removeBlocks(blocksToBeRemoved);
       code.removeAllDeadAndTrivialPhis(affectedValues);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/SimpleDominatingEffectAnalysis.java b/src/main/java/com/android/tools/r8/ir/optimize/SimpleDominatingEffectAnalysis.java
index 572b153..75e94fb 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/SimpleDominatingEffectAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/SimpleDominatingEffectAnalysis.java
@@ -249,7 +249,7 @@
     new StatefulDepthFirstSearchWorkList<BasicBlock, ResultStateWithPartialBlocks>() {
 
       @Override
-      protected TraversalContinuation<?> process(
+      protected TraversalContinuation<?, ?> process(
           DFSNodeWithState<BasicBlock, ResultStateWithPartialBlocks> node,
           Function<BasicBlock, DFSNodeWithState<BasicBlock, ResultStateWithPartialBlocks>>
               childNodeConsumer) {
@@ -285,7 +285,7 @@
       }
 
       @Override
-      protected TraversalContinuation<?> joiner(
+      protected TraversalContinuation<?, ?> joiner(
           DFSNodeWithState<BasicBlock, ResultStateWithPartialBlocks> node,
           List<DFSNodeWithState<BasicBlock, ResultStateWithPartialBlocks>> childNodes) {
         ResultStateWithPartialBlocks resultState = node.getState();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/analysis/ClassInlinerMethodConstraintAnalysis.java b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/analysis/ClassInlinerMethodConstraintAnalysis.java
index 854188e..f45344f 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/analysis/ClassInlinerMethodConstraintAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/analysis/ClassInlinerMethodConstraintAnalysis.java
@@ -26,8 +26,8 @@
     // Analyze code.
     IntraproceduralDataflowAnalysis<ParameterUsages> analysis =
         new IntraproceduralDataflowAnalysis<>(
-            ParameterUsages.bottom(), new TransferFunction(appView, method, code));
-    SuccessfulDataflowAnalysisResult<ParameterUsages> result =
+            ParameterUsages.bottom(), code, new TransferFunction(appView, method, code));
+    SuccessfulDataflowAnalysisResult<?, ParameterUsages> result =
         timing.time(
             "Data flow analysis",
             () -> analysis.run(code.entryBlock(), timing).asSuccessfulAnalysisResult());
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/analysis/TransferFunction.java b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/analysis/TransferFunction.java
index 65c05e6..0e4a8dd 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/analysis/TransferFunction.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/analysis/TransferFunction.java
@@ -52,7 +52,8 @@
 import com.google.common.collect.Sets;
 import java.util.Set;
 
-class TransferFunction implements AbstractTransferFunction<ParameterUsages> {
+class TransferFunction
+    implements AbstractTransferFunction<BasicBlock, Instruction, ParameterUsages> {
 
   private static final AliasedValueConfiguration aliasedValueConfiguration =
       AssumeAndCheckCastAliasedValueConfiguration.getInstance();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendFlowAnalysis.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendFlowAnalysis.java
index 80066f3..1179c6d 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendFlowAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendFlowAnalysis.java
@@ -12,6 +12,7 @@
 import com.android.tools.r8.ir.analysis.framework.intraprocedural.IntraproceduralDataflowAnalysis;
 import com.android.tools.r8.ir.analysis.framework.intraprocedural.TransferFunctionResult;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InvokeMethod;
 import com.android.tools.r8.ir.code.InvokeVirtual;
@@ -39,10 +40,10 @@
    * loop.
    */
   static boolean hasAppendInstructionInLoop(
-      Value builder, StringBuilderOptimizationConfiguration configuration) {
+      IRCode code, Value builder, StringBuilderOptimizationConfiguration configuration) {
     IntraproceduralDataflowAnalysis<AbstractStateImpl> analysis =
         new IntraproceduralDataflowAnalysis<>(
-            AbstractStateImpl.bottom(), new TransferFunction(builder, configuration));
+            AbstractStateImpl.bottom(), code, new TransferFunction(builder, configuration));
     DataflowAnalysisResult result = analysis.run(builder.definition.getBlock());
     return result.isFailedAnalysisResult();
   }
@@ -121,7 +122,8 @@
    * <p>If a call to {@code toString()} on the builder i seen, then the abstract state is reset to
    * bottom.
    */
-  private static class TransferFunction implements AbstractTransferFunction<AbstractStateImpl> {
+  private static class TransferFunction
+      implements AbstractTransferFunction<BasicBlock, Instruction, AbstractStateImpl> {
 
     private final Value builder;
     private final StringBuilderOptimizationConfiguration configuration;
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizer.java
index b851f1e..7e0b884 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizer.java
@@ -722,7 +722,7 @@
         return null;
       }
       if (StringBuilderAppendFlowAnalysis.hasAppendInstructionInLoop(
-          builder, optimizationConfiguration)) {
+          code, builder, optimizationConfiguration)) {
         return null;
       }
       return StringUtils.join("", contents);
diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java b/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java
index 15a3b02..d67d177 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java
@@ -47,9 +47,15 @@
 
     private final Map<String, ClassNamingForNameMapper.Builder> mapping = new HashMap<>();
     private LinkedHashSet<MapVersionMappingInformation> mapVersions = new LinkedHashSet<>();
+    private final Set<String> buildForClass;
 
-    private Builder() {
+    private Builder(Set<String> buildForClass) {
+      this.buildForClass = buildForClass;
+    }
 
+    @Override
+    public boolean buildForClass(String typeName) {
+      return buildForClass == null || buildForClass.contains(typeName);
     }
 
     @Override
@@ -82,7 +88,11 @@
   }
 
   public static Builder builder() {
-    return new Builder();
+    return new Builder(null);
+  }
+
+  public static Builder builder(Set<String> buildForClass) {
+    return new Builder(buildForClass);
   }
 
   public static ClassNameMapper mapperFromFile(Path path) throws IOException {
@@ -146,6 +156,25 @@
     }
   }
 
+  public static ClassNameMapper mapperFromBufferedReaderWithFiltering(
+      BufferedReader reader,
+      DiagnosticsHandler diagnosticsHandler,
+      boolean allowEmptyMappedRanges,
+      boolean allowExperimentalMapping,
+      Set<String> buildForClass)
+      throws IOException {
+    try (ProguardMapReader proguardReader =
+        new ProguardMapReader(
+            reader,
+            diagnosticsHandler != null ? diagnosticsHandler : new Reporter(),
+            allowEmptyMappedRanges,
+            allowExperimentalMapping)) {
+      ClassNameMapper.Builder builder = ClassNameMapper.builder(buildForClass);
+      proguardReader.parse(builder);
+      return builder.build();
+    }
+  }
+
   private final ImmutableMap<String, ClassNamingForNameMapper> classNameMappings;
   private BiMapContainer<String, String> nameMapping;
   private final Map<Signature, Signature> signatureMap = new HashMap<>();
diff --git a/src/main/java/com/android/tools/r8/naming/ProguardMap.java b/src/main/java/com/android/tools/r8/naming/ProguardMap.java
index 6b95444..d1e7463 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMap.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMap.java
@@ -16,6 +16,10 @@
     abstract Builder setCurrentMapVersion(MapVersionMappingInformation mapVersion);
 
     abstract ProguardMap build();
+
+    public boolean buildForClass(String typeName) {
+      return true;
+    }
   }
 
   boolean hasMapping(DexType type);
diff --git a/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java b/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java
index b2cb740..3e6816b 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java
@@ -162,6 +162,10 @@
     return false;
   }
 
+  private boolean isClassMapping() {
+    return !isEmptyOrCommentLine(line) && line.endsWith(":");
+  }
+
   private static boolean hasFirstCharJsonBrace(String line, int commentCharIndex) {
     for (int i = commentCharIndex + 1; i < line.length(); i++) {
       char c = line.charAt(i);
@@ -258,11 +262,18 @@
       String after = parseType(false);
       skipWhitespace();
       expect(':');
-      ClassNaming.Builder currentClassBuilder =
-          mapBuilder.classNamingBuilder(after, before, getPosition());
-      skipWhitespace();
-      if (nextLine()) {
-        parseMemberMappings(currentClassBuilder);
+      if (mapBuilder.buildForClass(after)) {
+        ClassNaming.Builder currentClassBuilder =
+            mapBuilder.classNamingBuilder(after, before, getPosition());
+        skipWhitespace();
+        if (nextLine()) {
+          parseMemberMappings(currentClassBuilder);
+        }
+      } else {
+        do {
+          lineOffset = line.length();
+          nextLine();
+        } while (hasLine() && !isClassMapping());
       }
     }
   }
diff --git a/src/main/java/com/android/tools/r8/retrace/IllegalClassNameLookupException.java b/src/main/java/com/android/tools/r8/retrace/IllegalClassNameLookupException.java
new file mode 100644
index 0000000..702ed59
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/retrace/IllegalClassNameLookupException.java
@@ -0,0 +1,19 @@
+// Copyright (c) 2022, 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.retrace;
+
+public class IllegalClassNameLookupException extends RuntimeException {
+
+  private final String typeName;
+
+  public IllegalClassNameLookupException(String typeName) {
+    this.typeName = typeName;
+  }
+
+  @Override
+  public String getMessage() {
+    return "Illegal lookup of " + typeName + ".";
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/retrace/ProguardMappingProvider.java b/src/main/java/com/android/tools/r8/retrace/ProguardMappingProvider.java
index 6e8d4fc..e192003 100644
--- a/src/main/java/com/android/tools/r8/retrace/ProguardMappingProvider.java
+++ b/src/main/java/com/android/tools/r8/retrace/ProguardMappingProvider.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.retrace;
 
 import com.android.tools.r8.Keep;
+import com.android.tools.r8.references.ClassReference;
 import com.android.tools.r8.retrace.internal.ProguardMappingProviderBuilderImpl;
 
 @Keep
@@ -18,6 +19,10 @@
   public abstract static class Builder
       extends MappingProviderBuilder<ProguardMappingProvider, Builder> {
 
+    public abstract Builder registerUse(ClassReference classReference);
+
+    public abstract Builder allowLookupAllClasses();
+
     public abstract Builder setProguardMapProducer(ProguardMapProducer proguardMapProducer);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/retrace/Retrace.java b/src/main/java/com/android/tools/r8/retrace/Retrace.java
index 61ba441..01dc051 100644
--- a/src/main/java/com/android/tools/r8/retrace/Retrace.java
+++ b/src/main/java/com/android/tools/r8/retrace/Retrace.java
@@ -12,9 +12,12 @@
 import com.android.tools.r8.Version;
 import com.android.tools.r8.naming.ProguardMapSupplier.ProguardMapChecker;
 import com.android.tools.r8.naming.ProguardMapSupplier.ProguardMapChecker.VerifyMappingFileHashResult;
+import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.references.TypeReference;
 import com.android.tools.r8.retrace.RetraceCommand.Builder;
 import com.android.tools.r8.retrace.internal.RetraceAbortException;
 import com.android.tools.r8.retrace.internal.RetracerImpl;
+import com.android.tools.r8.retrace.internal.StackTraceElementStringProxy;
 import com.android.tools.r8.retrace.internal.StackTraceRegularExpressionParser;
 import com.android.tools.r8.utils.Box;
 import com.android.tools.r8.utils.ExceptionDiagnostic;
@@ -185,6 +188,17 @@
             throw new RetraceAbortException();
           }
         });
+    List<ST> parsed = ListUtils.map(stackTrace, stackTraceLineParser::parse);
+    return retraceStackTraceParsed(parsed);
+  }
+
+  /**
+   * Retraces a complete stack frame and returns a list of retraced stack traces.
+   *
+   * @param stackTrace the stack trace to be retrace
+   * @return list of potentially ambiguous stack traces.
+   */
+  public List<List<List<T>>> retraceStackTraceParsed(List<ST> stackTrace) {
     RetraceStackTraceElementProxyEquivalence<T, ST> equivalence =
         new RetraceStackTraceElementProxyEquivalence<>(isVerbose);
     List<List<List<T>>> finalResult = new ArrayList<>();
@@ -192,14 +206,13 @@
         stackTrace,
         RetraceStackTraceContext.empty(),
         (context, stackTraceLine) -> {
-          ST parsedLine = stackTraceLineParser.parse(stackTraceLine);
           List<Pair<RetraceStackTraceElementProxy<T, ST>, List<T>>> resultsForLine =
               new ArrayList<>();
           Box<List<T>> currentList = new Box<>();
           Set<Wrapper<RetraceStackTraceElementProxy<T, ST>>> seen = new HashSet<>();
           List<RetraceStackTraceContext> contexts = new ArrayList<>();
           RetraceStackTraceElementProxyResult<T, ST> retraceResult =
-              proxyRetracer.retrace(parsedLine, context);
+              proxyRetracer.retrace(stackTraceLine, context);
           retraceResult.stream()
               .forEach(
                   retracedElement -> {
@@ -213,7 +226,9 @@
                       }
                     }
                     if (currentList.isSet()) {
-                      currentList.get().add(parsedLine.toRetracedItem(retracedElement, isVerbose));
+                      currentList
+                          .get()
+                          .add(stackTraceLine.toRetracedItem(retracedElement, isVerbose));
                     }
                   });
           resultsForLine.sort(Comparator.comparing(Pair::getFirst));
@@ -309,17 +324,44 @@
         }
         return;
       }
-      timing.begin("Read proguard map");
       DiagnosticsHandler diagnosticsHandler = options.getDiagnosticsHandler();
-      // The setup of a retracer should likely also follow a builder pattern instead of having
-      // static create methods. That would avoid the need to method overload the construction here
-      // and the default create would become the default build of a retracer.
-      MappingProvider mappingProvider =
+      timing.begin("Parsing");
+      StackTraceRegularExpressionParser stackTraceLineParser =
+          new StackTraceRegularExpressionParser(options.getRegularExpression());
+      List<StackTraceElementStringProxy> parsedStackTrace = new ArrayList<>();
+      ListUtils.forEachWithIndex(
+          command.getStackTrace(),
+          (line, lineNumber) -> {
+            if (line == null) {
+              diagnosticsHandler.error(
+                  RetraceInvalidStackTraceLineDiagnostics.createNull(lineNumber));
+              throw new RetraceAbortException();
+            }
+            parsedStackTrace.add(stackTraceLineParser.parse(line));
+          });
+      timing.end();
+      timing.begin("Read proguard map");
+      ProguardMappingProvider.Builder mappingBuilder =
           ProguardMappingProvider.builder()
               .setProguardMapProducer(options.getProguardMapProducer())
               .setDiagnosticsHandler(diagnosticsHandler)
-              .setAllowExperimental(allowExperimentalMapping)
-              .build();
+              .setAllowExperimental(allowExperimentalMapping);
+      parsedStackTrace.forEach(
+          proxy -> {
+            if (proxy.hasClassName()) {
+              mappingBuilder.registerUse(proxy.getClassReference());
+            }
+            if (proxy.hasMethodArguments()) {
+              Arrays.stream(proxy.getMethodArguments().split(","))
+                  .forEach(typeName -> registerUseFromTypeReference(mappingBuilder, typeName));
+            }
+            if (proxy.hasFieldOrReturnType() && !proxy.getFieldOrReturnType().equals("void")) {
+              registerUseFromTypeReference(mappingBuilder, proxy.getFieldOrReturnType());
+            }
+          });
+      MappingProvider mappingProvider = mappingBuilder.build();
+      timing.end();
+      timing.begin("Retracing");
       RetracerImpl retracer =
           RetracerImpl.builder()
               .setMappingProvider(mappingProvider)
@@ -334,17 +376,16 @@
                       RetraceUnknownMapVersionDiagnostic.create(mapVersionInfo.getValue()));
                 }
               });
-      timing.end();
-      timing.begin("Report result");
       StringRetrace stringRetrace =
           new StringRetrace(
-              new StackTraceRegularExpressionParser(options.getRegularExpression()),
+              stackTraceLineParser,
               StackTraceElementProxyRetracer.createDefault(retracer),
               diagnosticsHandler,
               options.isVerbose());
-      command
-          .getRetracedStackTraceConsumer()
-          .accept(stringRetrace.retrace(command.getStackTrace()));
+      List<String> retraced = stringRetrace.retraceParsed(parsedStackTrace);
+      timing.end();
+      timing.begin("Report result");
+      command.getRetracedStackTraceConsumer().accept(retraced);
       timing.end();
       if (command.printTimes()) {
         timing.report();
@@ -355,6 +396,17 @@
     }
   }
 
+  private static void registerUseFromTypeReference(
+      ProguardMappingProvider.Builder builder, String typeName) {
+    TypeReference typeReference = Reference.typeFromTypeName(typeName);
+    if (typeReference.isArray()) {
+      typeReference = typeReference.asArray().getBaseType();
+    }
+    if (typeReference.isClass()) {
+      builder.registerUse(typeReference.asClass());
+    }
+  }
+
   public static void run(String[] args) throws RetraceFailedException {
     // To be compatible with standard retrace and remapper, we translate -arg into --arg.
     String[] mappedArgs = new String[args.length];
diff --git a/src/main/java/com/android/tools/r8/retrace/Retracer.java b/src/main/java/com/android/tools/r8/retrace/Retracer.java
index 9a4eadf..15d3b48 100644
--- a/src/main/java/com/android/tools/r8/retrace/Retracer.java
+++ b/src/main/java/com/android/tools/r8/retrace/Retracer.java
@@ -77,6 +77,7 @@
           ProguardMappingProvider.builder()
               .setProguardMapProducer(proguardMapProducer)
               .setDiagnosticsHandler(diagnosticsHandler)
+              .allowLookupAllClasses()
               .build();
       return Retracer.builder()
           .setMappingProvider(mappingProvider)
diff --git a/src/main/java/com/android/tools/r8/retrace/StringRetrace.java b/src/main/java/com/android/tools/r8/retrace/StringRetrace.java
index 29ee4d2..b5ed6ae 100644
--- a/src/main/java/com/android/tools/r8/retrace/StringRetrace.java
+++ b/src/main/java/com/android/tools/r8/retrace/StringRetrace.java
@@ -106,6 +106,43 @@
   }
 
   /**
+   * Retraces a list of parsed stack trace lines and returns a list. Ambiguous and inline frames
+   * will be appended automatically to the retraced string.
+   *
+   * @param stackTrace the incoming parsed stack trace
+   * @return the retraced stack trace
+   */
+  public List<String> retraceParsed(List<StackTraceElementStringProxy> stackTrace) {
+    List<String> retracedStrings = new ArrayList<>();
+    List<List<List<String>>> lists = retraceStackTraceParsed(stackTrace);
+    for (List<List<String>> newLines : lists) {
+      ListUtils.forEachWithIndex(
+          newLines,
+          (inlineFrames, ambiguousIndex) -> {
+            for (int i = 0; i < inlineFrames.size(); i++) {
+              String stackTraceLine = inlineFrames.get(i);
+              if (i == 0 && ambiguousIndex > 0) {
+                // We are reporting an ambiguous frame. To support retracing tools that retrace line
+                // by line we have to emit <OR> at the point of the first 'at ' if we can find it.
+                int indexToInsertOr = stackTraceLine.indexOf("at ");
+                if (indexToInsertOr < 0) {
+                  indexToInsertOr =
+                      Math.max(StringUtils.firstNonWhitespaceCharacter(stackTraceLine), 0);
+                }
+                retracedStrings.add(
+                    stackTraceLine.substring(0, indexToInsertOr)
+                        + "<OR> "
+                        + stackTraceLine.substring(indexToInsertOr));
+              } else {
+                retracedStrings.add(stackTraceLine);
+              }
+            }
+          });
+    }
+    return retracedStrings;
+  }
+
+  /**
    * Retraces a single stack trace line and returns the potential list of original frames
    *
    * @param stackTraceLine the stack trace line to retrace
diff --git a/src/main/java/com/android/tools/r8/retrace/internal/MappingProviderInternal.java b/src/main/java/com/android/tools/r8/retrace/internal/MappingProviderInternal.java
index c0739c0..1ff65a4 100644
--- a/src/main/java/com/android/tools/r8/retrace/internal/MappingProviderInternal.java
+++ b/src/main/java/com/android/tools/r8/retrace/internal/MappingProviderInternal.java
@@ -4,9 +4,13 @@
 
 package com.android.tools.r8.retrace.internal;
 
-import com.android.tools.r8.naming.ClassNameMapper;
+import com.android.tools.r8.naming.ClassNamingForNameMapper;
+import com.android.tools.r8.naming.mappinginformation.MapVersionMappingInformation;
+import java.util.Set;
 
 public abstract class MappingProviderInternal {
 
-  abstract ClassNameMapper getClassNameMapper();
+  abstract ClassNamingForNameMapper getClassNaming(String typeName);
+
+  abstract Set<MapVersionMappingInformation> getMapVersions();
 }
diff --git a/src/main/java/com/android/tools/r8/retrace/internal/ProguardMappingProviderBuilderImpl.java b/src/main/java/com/android/tools/r8/retrace/internal/ProguardMappingProviderBuilderImpl.java
index 8162f5c..e18adca 100644
--- a/src/main/java/com/android/tools/r8/retrace/internal/ProguardMappingProviderBuilderImpl.java
+++ b/src/main/java/com/android/tools/r8/retrace/internal/ProguardMappingProviderBuilderImpl.java
@@ -6,15 +6,20 @@
 
 import com.android.tools.r8.DiagnosticsHandler;
 import com.android.tools.r8.naming.ClassNameMapper;
+import com.android.tools.r8.references.ClassReference;
 import com.android.tools.r8.retrace.InvalidMappingFileException;
 import com.android.tools.r8.retrace.ProguardMapProducer;
 import com.android.tools.r8.retrace.ProguardMappingProvider;
 import java.io.BufferedReader;
+import java.util.HashSet;
+import java.util.Set;
 
 public class ProguardMappingProviderBuilderImpl extends ProguardMappingProvider.Builder {
 
   private ProguardMapProducer proguardMapProducer;
   private boolean allowExperimental = false;
+  private Set<String> allowedLookup = new HashSet<>();
+  private boolean allowLookupAllClasses = false;
   private DiagnosticsHandler diagnosticsHandler = new DiagnosticsHandler() {};
 
   @Override
@@ -36,6 +41,18 @@
   }
 
   @Override
+  public ProguardMappingProvider.Builder registerUse(ClassReference classReference) {
+    allowedLookup.add(classReference.getTypeName());
+    return self();
+  }
+
+  @Override
+  public ProguardMappingProvider.Builder allowLookupAllClasses() {
+    allowLookupAllClasses = true;
+    return self();
+  }
+
+  @Override
   public ProguardMappingProvider.Builder setProguardMapProducer(
       ProguardMapProducer proguardMapProducer) {
     this.proguardMapProducer = proguardMapProducer;
@@ -45,12 +62,23 @@
   @Override
   public ProguardMappingProvider build() {
     try {
-      return new ProguardMappingProviderImpl(
-          ClassNameMapper.mapperFromBufferedReader(
-              new BufferedReader(proguardMapProducer.get()),
-              diagnosticsHandler,
-              true,
-              allowExperimental));
+      if (allowLookupAllClasses) {
+        return new ProguardMappingProviderImpl(
+            ClassNameMapper.mapperFromBufferedReader(
+                new BufferedReader(proguardMapProducer.get()),
+                diagnosticsHandler,
+                true,
+                allowExperimental));
+      } else {
+        return new ProguardMappingProviderImpl(
+            ClassNameMapper.mapperFromBufferedReaderWithFiltering(
+                new BufferedReader(proguardMapProducer.get()),
+                diagnosticsHandler,
+                true,
+                allowExperimental,
+                allowedLookup),
+            allowedLookup);
+      }
     } catch (Exception e) {
       throw new InvalidMappingFileException(e);
     }
diff --git a/src/main/java/com/android/tools/r8/retrace/internal/ProguardMappingProviderImpl.java b/src/main/java/com/android/tools/r8/retrace/internal/ProguardMappingProviderImpl.java
index 8ea72fa..dcfe2cb 100644
--- a/src/main/java/com/android/tools/r8/retrace/internal/ProguardMappingProviderImpl.java
+++ b/src/main/java/com/android/tools/r8/retrace/internal/ProguardMappingProviderImpl.java
@@ -5,7 +5,11 @@
 package com.android.tools.r8.retrace.internal;
 
 import com.android.tools.r8.naming.ClassNameMapper;
+import com.android.tools.r8.naming.ClassNamingForNameMapper;
+import com.android.tools.r8.naming.mappinginformation.MapVersionMappingInformation;
+import com.android.tools.r8.retrace.IllegalClassNameLookupException;
 import com.android.tools.r8.retrace.ProguardMappingProvider;
+import java.util.Set;
 
 /**
  * IntelliJ highlights the class as being invalid because it cannot see getClassNameMapper is
@@ -14,13 +18,29 @@
 public class ProguardMappingProviderImpl extends ProguardMappingProvider {
 
   private final ClassNameMapper classNameMapper;
+  private final Set<String> allowedLookupTypeNames;
 
   public ProguardMappingProviderImpl(ClassNameMapper classNameMapper) {
+    this(classNameMapper, null);
+  }
+
+  public ProguardMappingProviderImpl(
+      ClassNameMapper classNameMapper, Set<String> allowedLookupTypeNames) {
     this.classNameMapper = classNameMapper;
+    this.allowedLookupTypeNames = allowedLookupTypeNames;
   }
 
   @Override
-  ClassNameMapper getClassNameMapper() {
-    return classNameMapper;
+  Set<MapVersionMappingInformation> getMapVersions() {
+    return classNameMapper.getMapVersions();
+  }
+
+  @Override
+  ClassNamingForNameMapper getClassNaming(String typeName) {
+    // TODO(b/226885646): Enable lookup check when there are no additional lookups.
+    if (false && !allowedLookupTypeNames.contains(typeName)) {
+      throw new IllegalClassNameLookupException(typeName);
+    }
+    return classNameMapper.getClassNaming(typeName);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/retrace/internal/RetraceUtils.java b/src/main/java/com/android/tools/r8/retrace/internal/RetraceUtils.java
index 920393b..c4ed860 100644
--- a/src/main/java/com/android/tools/r8/retrace/internal/RetraceUtils.java
+++ b/src/main/java/com/android/tools/r8/retrace/internal/RetraceUtils.java
@@ -75,6 +75,7 @@
     return clazz.substring(lastIndexOfPeriod + 1, endIndex);
   }
 
+  // TODO(b/226885646): Retracing of a source file should not be dependent on retraced information.
   public static RetracedSourceFile getSourceFileOrLookup(
       RetracedClassReference holder, RetraceClassElement context, Retracer retracer) {
     if (holder.equals(context.getRetracedClass())) {
diff --git a/src/main/java/com/android/tools/r8/retrace/internal/RetracerImpl.java b/src/main/java/com/android/tools/r8/retrace/internal/RetracerImpl.java
index b01aa7f..92e42f1 100644
--- a/src/main/java/com/android/tools/r8/retrace/internal/RetracerImpl.java
+++ b/src/main/java/com/android/tools/r8/retrace/internal/RetracerImpl.java
@@ -5,7 +5,6 @@
 package com.android.tools.r8.retrace.internal;
 
 import com.android.tools.r8.DiagnosticsHandler;
-import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.naming.mappinginformation.MapVersionMappingInformation;
 import com.android.tools.r8.references.ClassReference;
 import com.android.tools.r8.references.FieldReference;
@@ -22,13 +21,14 @@
 /** A default implementation for the retrace api using the ClassNameMapper defined in R8. */
 public class RetracerImpl implements Retracer {
 
-  private final ClassNameMapper classNameMapper;
+  private final MappingProviderInternal classNameMapperProvider;
   private final DiagnosticsHandler diagnosticsHandler;
 
-  private RetracerImpl(ClassNameMapper classNameMapper, DiagnosticsHandler diagnosticsHandler) {
-    this.classNameMapper = classNameMapper;
+  private RetracerImpl(
+      MappingProviderInternal classNameMapperProvider, DiagnosticsHandler diagnosticsHandler) {
+    this.classNameMapperProvider = classNameMapperProvider;
     this.diagnosticsHandler = diagnosticsHandler;
-    assert classNameMapper != null;
+    assert classNameMapperProvider != null;
   }
 
   public DiagnosticsHandler getDiagnosticsHandler() {
@@ -70,7 +70,7 @@
   @Override
   public RetraceClassResultImpl retraceClass(ClassReference classReference) {
     return RetraceClassResultImpl.create(
-        classReference, classNameMapper.getClassNaming(classReference.getTypeName()), this);
+        classReference, classNameMapperProvider.getClassNaming(classReference.getTypeName()), this);
   }
 
   @Override
@@ -84,7 +84,7 @@
   }
 
   public Set<MapVersionMappingInformation> getMapVersions() {
-    return classNameMapper.getMapVersions();
+    return classNameMapperProvider.getMapVersions();
   }
 
   public static Builder builder() {
@@ -112,8 +112,7 @@
 
     @Override
     public RetracerImpl build() {
-      return new RetracerImpl(
-          ((MappingProviderInternal) mappingProvider).getClassNameMapper(), diagnosticsHandler);
+      return new RetracerImpl(mappingProvider, diagnosticsHandler);
     }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardClassNameList.java b/src/main/java/com/android/tools/r8/shaking/ProguardClassNameList.java
index ffc2149..cc5d00b 100644
--- a/src/main/java/com/android/tools/r8/shaking/ProguardClassNameList.java
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardClassNameList.java
@@ -114,11 +114,11 @@
         });
   }
 
-  public abstract TraversalContinuation<?> traverseTypeMatchers(
-      Function<ProguardTypeMatcher, TraversalContinuation<?>> fn);
+  public abstract TraversalContinuation<?, ?> traverseTypeMatchers(
+      Function<ProguardTypeMatcher, TraversalContinuation<?, ?>> fn);
 
-  public final TraversalContinuation<?> traverseTypeMatchers(
-      Function<ProguardTypeMatcher, TraversalContinuation<?>> fn,
+  public final TraversalContinuation<?, ?> traverseTypeMatchers(
+      Function<ProguardTypeMatcher, TraversalContinuation<?, ?>> fn,
       Predicate<ProguardTypeMatcher> predicate) {
     return traverseTypeMatchers(
         matcher -> {
@@ -168,8 +168,8 @@
     }
 
     @Override
-    public TraversalContinuation<?> traverseTypeMatchers(
-        Function<ProguardTypeMatcher, TraversalContinuation<?>> fn) {
+    public TraversalContinuation<?, ?> traverseTypeMatchers(
+        Function<ProguardTypeMatcher, TraversalContinuation<?, ?>> fn) {
       return TraversalContinuation.doContinue();
     }
   }
@@ -236,8 +236,8 @@
     }
 
     @Override
-    public TraversalContinuation<?> traverseTypeMatchers(
-        Function<ProguardTypeMatcher, TraversalContinuation<?>> fn) {
+    public TraversalContinuation<?, ?> traverseTypeMatchers(
+        Function<ProguardTypeMatcher, TraversalContinuation<?, ?>> fn) {
       return fn.apply(className);
     }
   }
@@ -320,8 +320,8 @@
     }
 
     @Override
-    public TraversalContinuation<?> traverseTypeMatchers(
-        Function<ProguardTypeMatcher, TraversalContinuation<?>> fn) {
+    public TraversalContinuation<?, ?> traverseTypeMatchers(
+        Function<ProguardTypeMatcher, TraversalContinuation<?, ?>> fn) {
       for (ProguardTypeMatcher matcher : classNames) {
         if (fn.apply(matcher).shouldBreak()) {
           return TraversalContinuation.doBreak();
@@ -416,8 +416,8 @@
     }
 
     @Override
-    public TraversalContinuation<?> traverseTypeMatchers(
-        Function<ProguardTypeMatcher, TraversalContinuation<?>> fn) {
+    public TraversalContinuation<?, ?> traverseTypeMatchers(
+        Function<ProguardTypeMatcher, TraversalContinuation<?, ?>> fn) {
       for (ProguardTypeMatcher matcher : classNames.keySet()) {
         if (fn.apply(matcher).shouldBreak()) {
           return TraversalContinuation.doBreak();
diff --git a/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java b/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
index b10e649..484cd3a 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
@@ -1403,7 +1403,7 @@
           dependentMinimumKeepInfo.getUnconditionalMinimumKeepInfoOrDefault(
               MinimumKeepInfoCollection.empty());
       for (DexProgramClass clazz : classesWithCheckDiscardedMembers) {
-        TraversalContinuation<?> continueIfAllMembersMarkedAsCheckDiscarded =
+        TraversalContinuation<?, ?> continueIfAllMembersMarkedAsCheckDiscarded =
             clazz.traverseProgramMembers(
                 member ->
                     TraversalContinuation.continueIf(
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index 6cc5f84..9797f72 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -417,7 +417,7 @@
     // If there is a constructor in the target, make sure that all source constructors can be
     // inlined.
     if (!Iterables.isEmpty(targetClass.programInstanceInitializers())) {
-      TraversalContinuation<?> result =
+      TraversalContinuation<?, ?> result =
           sourceClass.traverseProgramInstanceInitializers(
               method -> {
                 AbortReason reason = disallowInlining(method, targetClass);
@@ -454,7 +454,7 @@
     // If there is an invoke-special to a default interface method and we are not merging into an
     // interface, then abort, since invoke-special to a virtual class method requires desugaring.
     if (sourceClass.isInterface() && !targetClass.isInterface()) {
-      TraversalContinuation<?> result =
+      TraversalContinuation<?, ?> result =
           sourceClass.traverseProgramMethods(
               method -> {
                 boolean foundInvokeSpecialToDefaultLibraryMethod =
@@ -586,7 +586,7 @@
     // Check that all accesses from [source] to classes or members from the current package of
     // [source] will continue to work. This is guaranteed if the methods of [source] do not access
     // any private or protected classes or members from the current package of [source].
-    TraversalContinuation<?> result =
+    TraversalContinuation<?, ?> result =
         source.traverseProgramMethods(
             method -> {
               boolean foundIllegalAccess =
diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java
index 3559fe3..05ce2e9 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java
@@ -84,18 +84,28 @@
   public final SyntheticKind ARRAY_CONVERSION = generator.forSingleMethod("$ArrayConversion");
   public final SyntheticKind API_MODEL_OUTLINE = generator.forSingleMethod("ApiModelOutline");
 
-  private final String versionHash;
   private final List<SyntheticKind> ALL_KINDS;
+  private String lazyVersionHash = null;
 
   public SyntheticNaming() {
-    generator.hasher.putString(Version.getVersionString(), StandardCharsets.UTF_8);
-    versionHash = generator.hasher.hash().toString();
     ALL_KINDS = generator.getAllKinds();
     generator = null;
   }
 
   public String getVersionHash() {
-    return versionHash;
+    if (lazyVersionHash == null) {
+      computeVersionHash();
+    }
+    return lazyVersionHash;
+  }
+
+  private void computeVersionHash() {
+    Hasher hasher = Hashing.sha256().newHasher();
+    hasher.putString(Version.getVersionString(), StandardCharsets.UTF_8);
+    for (SyntheticKind kind : ALL_KINDS) {
+      kind.hash(hasher);
+    }
+    lazyVersionHash = hasher.hash().toString();
   }
 
   public Collection<SyntheticKind> kinds() {
@@ -112,10 +122,8 @@
   private static class KindGenerator {
     private int nextId = 1;
     private List<SyntheticKind> kinds = new ArrayList<>();
-    private Hasher hasher = Hashing.sha256().newHasher();
 
     private SyntheticKind register(SyntheticKind kind) {
-      kind.hash(hasher);
       kinds.add(kind);
       if (kinds.size() != kind.getId()) {
         throw new Unreachable("Invalid synthetic kind id: " + kind.getId());
diff --git a/src/main/java/com/android/tools/r8/utils/DepthFirstSearchWorkListBase.java b/src/main/java/com/android/tools/r8/utils/DepthFirstSearchWorkListBase.java
index 6b5df9b..c9a56da 100644
--- a/src/main/java/com/android/tools/r8/utils/DepthFirstSearchWorkListBase.java
+++ b/src/main/java/com/android/tools/r8/utils/DepthFirstSearchWorkListBase.java
@@ -107,10 +107,10 @@
   abstract T createDfsNode(N node);
 
   /** The initial processing of a node during forward search */
-  abstract TraversalContinuation<?> internalOnVisit(T node);
+  abstract TraversalContinuation<?, ?> internalOnVisit(T node);
 
   /** The joining of state during backtracking of the algorithm. */
-  abstract TraversalContinuation<?> internalOnJoin(T node);
+  abstract TraversalContinuation<?, ?> internalOnJoin(T node);
 
   final T internalEnqueueNode(N value) {
     T dfsNode = createDfsNode(value);
@@ -121,13 +121,13 @@
   }
 
   @SafeVarargs
-  public final TraversalContinuation<?> run(N... roots) {
+  public final TraversalContinuation<?, ?> run(N... roots) {
     return run(Arrays.asList(roots));
   }
 
-  public final TraversalContinuation<?> run(Collection<N> roots) {
+  public final TraversalContinuation<?, ?> run(Collection<N> roots) {
     roots.forEach(this::internalEnqueueNode);
-    TraversalContinuation<?> continuation = TraversalContinuation.doContinue();
+    TraversalContinuation<?, ?> continuation = TraversalContinuation.doContinue();
     while (!workList.isEmpty()) {
       T node = workList.removeLast();
       if (node.isFinished()) {
@@ -161,7 +161,7 @@
      *     before but not finished there is a cycle.
      * @return A value describing if the DFS algorithm should continue to run.
      */
-    protected abstract TraversalContinuation<?> process(
+    protected abstract TraversalContinuation<?, ?> process(
         DFSNode<N> node, Function<N, DFSNode<N>> childNodeConsumer);
 
     @Override
@@ -170,12 +170,12 @@
     }
 
     @Override
-    TraversalContinuation<?> internalOnVisit(DFSNodeImpl<N> node) {
+    TraversalContinuation<?, ?> internalOnVisit(DFSNodeImpl<N> node) {
       return process(node, this::internalEnqueueNode);
     }
 
     @Override
-    protected TraversalContinuation<?> internalOnJoin(DFSNodeImpl<N> node) {
+    protected TraversalContinuation<?, ?> internalOnJoin(DFSNodeImpl<N> node) {
       return TraversalContinuation.doContinue();
     }
   }
@@ -195,7 +195,7 @@
      *     before but not finished there is a cycle.
      * @return A value describing if the DFS algorithm should continue to run.
      */
-    protected abstract TraversalContinuation<?> process(
+    protected abstract TraversalContinuation<?, ?> process(
         DFSNodeWithState<N, S> node, Function<N, DFSNodeWithState<N, S>> childNodeConsumer);
 
     /**
@@ -205,7 +205,7 @@
      * @param childStates The already computed child states.
      * @return A value describing if the DFS algorithm should continue to run.
      */
-    protected abstract TraversalContinuation<?> joiner(
+    protected abstract TraversalContinuation<?, ?> joiner(
         DFSNodeWithState<N, S> node, List<DFSNodeWithState<N, S>> childStates);
 
     @Override
@@ -214,7 +214,7 @@
     }
 
     @Override
-    TraversalContinuation<?> internalOnVisit(DFSNodeWithStateImpl<N, S> node) {
+    TraversalContinuation<?, ?> internalOnVisit(DFSNodeWithStateImpl<N, S> node) {
       List<DFSNodeWithState<N, S>> childStates = new ArrayList<>();
       List<DFSNodeWithState<N, S>> removedChildStates = childStateMap.put(node, childStates);
       assert removedChildStates == null;
@@ -228,7 +228,7 @@
     }
 
     @Override
-    protected TraversalContinuation<?> internalOnJoin(DFSNodeWithStateImpl<N, S> node) {
+    protected TraversalContinuation<?, ?> internalOnJoin(DFSNodeWithStateImpl<N, S> node) {
       return joiner(
           node,
           childStateMap.computeIfAbsent(
diff --git a/src/main/java/com/android/tools/r8/utils/DisjointSets.java b/src/main/java/com/android/tools/r8/utils/DisjointSets.java
index a39b482..d8e42b9 100644
--- a/src/main/java/com/android/tools/r8/utils/DisjointSets.java
+++ b/src/main/java/com/android/tools/r8/utils/DisjointSets.java
@@ -125,9 +125,6 @@
    * <p>Returns the representative for the union set.
    */
   public T unionWithMakeSet(T element1, T element2) {
-    if (element1.toString().contains("Enum") || element2.toString().contains("Enum")) {
-      System.out.println();
-    }
     if (element1 == element2) {
       return findOrMakeSet(element1);
     }
diff --git a/src/main/java/com/android/tools/r8/utils/TraversalContinuation.java b/src/main/java/com/android/tools/r8/utils/TraversalContinuation.java
index 5bd242f..19f89d8 100644
--- a/src/main/java/com/android/tools/r8/utils/TraversalContinuation.java
+++ b/src/main/java/com/android/tools/r8/utils/TraversalContinuation.java
@@ -7,34 +7,58 @@
 
 /** Two value continuation value to indicate the continuation of a loop/traversal. */
 /* This class is used for building up api class member traversals. */
-public abstract class TraversalContinuation<T> {
+public abstract class TraversalContinuation<TB, TC> {
 
   public boolean isBreak() {
-    return !isContinue();
+    return false;
+  }
+
+  public Break<TB, TC> asBreak() {
+    return null;
   }
 
   public boolean isContinue() {
     return false;
   }
 
-  public Break<T> asBreak() {
+  public Continue<TB, TC> asContinue() {
     return null;
   }
 
-  public static final class Continue<T> extends TraversalContinuation<T> {
-    private static final TraversalContinuation<?> CONTINUE = new Continue<Object>();
+  public static class Continue<TB, TC> extends TraversalContinuation<TB, TC> {
+    private static final TraversalContinuation<?, ?> CONTINUE_NO_VALUE =
+        new Continue<Object, Object>(null) {
+          @Override
+          public Object getValue() {
+            return new Unreachable(
+                "Invalid attempt at getting a value from a no-value continue state.");
+          }
+        };
 
-    private Continue() {}
+    private final TC value;
+
+    private Continue(TC value) {
+      this.value = value;
+    }
+
+    public TC getValue() {
+      return value;
+    }
 
     @Override
     public boolean isContinue() {
       return true;
     }
+
+    @Override
+    public Continue<TB, TC> asContinue() {
+      return this;
+    }
   }
 
-  public static class Break<T> extends TraversalContinuation<T> {
-    private static final TraversalContinuation<?> BREAK_NO_VALUE =
-        new Break<Object>(null) {
+  public static class Break<TB, TC> extends TraversalContinuation<TB, TC> {
+    private static final TraversalContinuation<?, ?> BREAK_NO_VALUE =
+        new Break<Object, Object>(null) {
           @Override
           public Object getValue() {
             return new Unreachable(
@@ -42,40 +66,50 @@
           }
         };
 
-    private final T value;
+    private final TB value;
 
-    private Break(T value) {
+    private Break(TB value) {
       this.value = value;
     }
 
-    public T getValue() {
+    public TB getValue() {
       return value;
     }
 
     @Override
-    public Break<T> asBreak() {
+    public boolean isBreak() {
+      return true;
+    }
+
+    @Override
+    public Break<TB, TC> asBreak() {
       return this;
     }
   }
 
-  public static TraversalContinuation<?> breakIf(boolean condition) {
+  public static TraversalContinuation<?, ?> breakIf(boolean condition) {
     return continueIf(!condition);
   }
 
-  public static TraversalContinuation<?> continueIf(boolean condition) {
+  public static TraversalContinuation<?, ?> continueIf(boolean condition) {
     return condition ? doContinue() : doBreak();
   }
 
   @SuppressWarnings("unchecked")
-  public static <T> TraversalContinuation<T> doContinue() {
-    return (TraversalContinuation<T>) Continue.CONTINUE;
+  public static <TB, TC> TraversalContinuation<TB, TC> doContinue() {
+    return (TraversalContinuation<TB, TC>) Continue.CONTINUE_NO_VALUE;
   }
 
-  public static TraversalContinuation<?> doBreak() {
-    return Break.BREAK_NO_VALUE;
+  public static <TB, TC> TraversalContinuation<TB, TC> doContinue(TC value) {
+    return new Continue<>(value);
   }
 
-  public static <T> TraversalContinuation<T> doBreak(T value) {
+  @SuppressWarnings("unchecked")
+  public static <TB, TC> TraversalContinuation<TB, TC> doBreak() {
+    return (TraversalContinuation<TB, TC>) Break.BREAK_NO_VALUE;
+  }
+
+  public static <TB, TC> TraversalContinuation<TB, TC> doBreak(TB value) {
     return new Break<>(value);
   }
 
diff --git a/src/test/java/com/android/tools/r8/benchmarks/BenchmarkCollectionPrinter.java b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkCollectionPrinter.java
index c7336f7..1a26aa7 100644
--- a/src/test/java/com/android/tools/r8/benchmarks/BenchmarkCollectionPrinter.java
+++ b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkCollectionPrinter.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.utils.CollectionUtils;
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.StringUtils.BraceType;
@@ -19,9 +20,11 @@
 import java.nio.file.Paths;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 
 public class BenchmarkCollectionPrinter {
 
@@ -100,29 +103,77 @@
           for (String benchmarkName : sortedNames) {
             List<BenchmarkConfig> benchmarkTargets = nameToTargets.get(benchmarkName);
             assert !benchmarkTargets.isEmpty();
-            scopeBraces(() -> printBenchmarkBlock(benchmarkName, benchmarkTargets));
+            if (benchmarkTargets.get(0).isSingleBenchmark()) {
+              scopeBraces(() -> printStandardBenchmarkBlock(benchmarkName, benchmarkTargets));
+            } else {
+              scopeBraces(() -> printGroupBenchmarkBlock(benchmarkName, benchmarkTargets));
+            }
           }
         });
     print("}");
   }
 
-  private void printBenchmarkBlock(String benchmarkName, List<BenchmarkConfig> benchmarkVariants)
-      throws IOException {
-    // Common properties that must be consistent among all the benchmark variants.
+  private String prettyMetrics(Collection<BenchmarkMetric> metrics) {
+    List<String> metricsStrings =
+        new ArrayList<>(ListUtils.map(metrics, BenchmarkMetric::getDartType));
+    metricsStrings.sort(String::compareTo);
+    return StringUtils.join(", ", metricsStrings, BraceType.SQUARE);
+  }
+
+  private void printStandardBenchmarkBlock(
+      String benchmarkName, List<BenchmarkConfig> benchmarkVariants) throws IOException {
     String suite = BenchmarkConfig.getCommonSuite(benchmarkVariants).getDartName();
-    List<String> metrics =
-        new ArrayList<>(
-            ListUtils.map(
-                BenchmarkConfig.getCommonMetrics(benchmarkVariants), BenchmarkMetric::getDartType));
-    metrics.sort(String::compareTo);
+    List<BenchmarkMetric> metrics =
+        new ArrayList<>(BenchmarkConfig.getCommonMetrics(benchmarkVariants));
+    if (BenchmarkConfig.getCommonHasTimeWarmup(benchmarkVariants)) {
+      metrics.add(BenchmarkMetric.StartupTime);
+    }
     printSemi("final name = " + quote(benchmarkName));
-    printSemi("final metrics = " + StringUtils.join(", ", metrics, BraceType.SQUARE));
+    printSemi("final metrics = " + prettyMetrics(metrics));
     printSemi("final benchmark = StandardBenchmark(name, metrics)");
     BenchmarkTimeout timeout = BenchmarkConfig.getCommonTimeout(benchmarkVariants);
     if (timeout != null) {
       printSemi("final timeout = const Duration(seconds: " + timeout.asSeconds() + ")");
       printSemi("ExecutionManagement.addTimeoutConstraint(timeout, benchmark: benchmark)");
     }
+    printBenchmarkVariantOptionBlock(benchmarkVariants);
+    printSemi(suite + ".addBenchmark(name)");
+  }
+
+  private void printGroupBenchmarkBlock(
+      String benchmarkName, List<BenchmarkConfig> benchmarkVariants) throws IOException {
+    String suite = BenchmarkConfig.getCommonSuite(benchmarkVariants).getDartName();
+    printSemi("final name = " + quote(benchmarkName));
+    printSemi("final benchmark = GroupBenchmark(name, [])");
+    BenchmarkTimeout timeout = BenchmarkConfig.getCommonTimeout(benchmarkVariants);
+    if (timeout != null) {
+      printSemi("final timeout = const Duration(seconds: " + timeout.asSeconds() + ")");
+      printSemi("ExecutionManagement.addTimeoutConstraint(timeout, benchmark: benchmark)");
+    }
+    printBenchmarkVariantOptionBlock(benchmarkVariants);
+    Map<String, Set<BenchmarkMetric>> subBenchmarks =
+        BenchmarkConfig.getCommonSubBenchmarks(benchmarkVariants);
+    Collection<String> subNames = CollectionUtils.sort(subBenchmarks.keySet(), String::compareTo);
+    for (String subName : subNames) {
+      scopeBraces(
+          () -> {
+            Set<BenchmarkMetric> subMetrics = subBenchmarks.get(subName);
+            printSemi("final subName = " + quote(subName));
+            printSemi("benchmark.addBenchmark(subName, " + prettyMetrics(subMetrics) + ")");
+            printSemi(suite + ".addBenchmark(subName)");
+          });
+    }
+    if (BenchmarkConfig.getCommonHasTimeWarmup(benchmarkVariants)) {
+      printSemi(
+          "benchmark.addBenchmark(name, "
+              + prettyMetrics(Collections.singletonList(BenchmarkMetric.StartupTime))
+              + ")");
+    }
+    printSemi(suite + ".addBenchmark(name)");
+  }
+
+  private void printBenchmarkVariantOptionBlock(List<BenchmarkConfig> benchmarkVariants)
+      throws IOException {
     for (BenchmarkConfig benchmark : benchmarkVariants) {
       scopeBraces(
           () -> {
@@ -153,7 +204,6 @@
             }
           });
     }
-    printSemi(suite + ".addBenchmark(name)");
   }
 
   private void addGolemResource(String name, Path tarball) throws IOException {
diff --git a/src/test/java/com/android/tools/r8/benchmarks/BenchmarkConfig.java b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkConfig.java
index 56ea759..b04a407 100644
--- a/src/test/java/com/android/tools/r8/benchmarks/BenchmarkConfig.java
+++ b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkConfig.java
@@ -3,12 +3,16 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.benchmarks;
 
-import com.android.tools.r8.errors.Unreachable;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collection;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.List;
+import java.util.Map;
+import java.util.Objects;
 import java.util.Set;
 import java.util.concurrent.TimeUnit;
 
@@ -18,9 +22,23 @@
     if (benchmark.getTarget().equals(other.getTarget())) {
       throw new BenchmarkConfigError("Duplicate benchmark name and target: " + benchmark);
     }
-    if (!benchmark.getMetrics().equals(other.getMetrics())) {
+    if (benchmark.isSingleBenchmark() != other.isSingleBenchmark()) {
       throw new BenchmarkConfigError(
-          "Inconsistent metrics for benchmarks: " + benchmark + " and " + other);
+          "Inconsistent single/group benchmark setup: " + benchmark + " and " + other);
+    }
+    Set<String> subNames =
+        Sets.union(benchmark.getSubBenchmarks().keySet(), other.getSubBenchmarks().keySet());
+    for (String subName : subNames) {
+      if (!Objects.equals(
+          benchmark.getSubBenchmarks().get(subName), other.getSubBenchmarks().get(subName))) {
+        throw new BenchmarkConfigError(
+            "Inconsistent metrics for sub-benchmark "
+                + subName
+                + " in benchmarks: "
+                + benchmark
+                + " and "
+                + other);
+      }
     }
     if (!benchmark.getSuite().equals(other.getSuite())) {
       throw new BenchmarkConfigError(
@@ -40,6 +58,15 @@
     return getConsistentRepresentative(variants).getSuite();
   }
 
+  public static boolean getCommonHasTimeWarmup(List<BenchmarkConfig> variants) {
+    return getConsistentRepresentative(variants).hasTimeWarmupRuns();
+  }
+
+  public static Map<String, Set<BenchmarkMetric>> getCommonSubBenchmarks(
+      List<BenchmarkConfig> variants) {
+    return getConsistentRepresentative(variants).getSubBenchmarks();
+  }
+
   // Use the largest configured timeout as the timeout for the full group.
   public static BenchmarkTimeout getCommonTimeout(List<BenchmarkConfig> variants) {
     BenchmarkTimeout timeout = null;
@@ -71,41 +98,63 @@
     private BenchmarkMethod method = null;
     private BenchmarkTarget target = null;
     private Set<BenchmarkMetric> metrics = new HashSet<>();
+    private Map<String, Set<BenchmarkMetric>> subBenchmarks = new HashMap<>();
     private BenchmarkSuite suite = BenchmarkSuite.getDefault();
     private Collection<BenchmarkDependency> dependencies = new ArrayList<>();
     private int fromRevision = -1;
     private BenchmarkTimeout timeout = null;
+    private boolean measureWarmup = false;
 
     private Builder() {}
 
     public BenchmarkConfig build() {
       if (name == null) {
-        throw new Unreachable("Benchmark name must be set");
+        throw new BenchmarkConfigError("Benchmark name must be set");
       }
       if (method == null) {
-        throw new Unreachable("Benchmark method must be set");
+        throw new BenchmarkConfigError("Benchmark method must be set");
       }
       if (target == null) {
-        throw new Unreachable("Benchmark target must be set");
-      }
-      if (metrics.isEmpty()) {
-        throw new Unreachable("Benchmark must have at least one metric to measure");
+        throw new BenchmarkConfigError("Benchmark target must be set");
       }
       if (suite == null) {
-        throw new Unreachable("Benchmark must have a suite");
+        throw new BenchmarkConfigError("Benchmark must have a suite");
       }
       if (fromRevision < 0) {
-        throw new Unreachable("Benchmark must specify from which golem revision it is valid");
+        throw new BenchmarkConfigError(
+            "Benchmark must specify from which golem revision it is valid");
+      }
+      if (!metrics.isEmpty()) {
+        if (subBenchmarks.containsKey(name)) {
+          throw new BenchmarkConfigError(
+              "Benchmark must not specify both direct metrics and a sub-benchmark of the same"
+                  + " name");
+        }
+        subBenchmarks.put(name, ImmutableSet.copyOf(metrics));
+      }
+      if (subBenchmarks.isEmpty()) {
+        throw new BenchmarkConfigError(
+            "Benchmark must have at least one metric / sub-benchmark to measure");
+      }
+      if (measureWarmup) {
+        for (Set<BenchmarkMetric> subMetrics : subBenchmarks.values()) {
+          if (subMetrics.contains(BenchmarkMetric.StartupTime)) {
+            throw new BenchmarkConfigError(
+                "Benchmark cannot both measure warmup and set metric: "
+                    + BenchmarkMetric.StartupTime);
+          }
+        }
       }
       return new BenchmarkConfig(
           name,
           method,
           target,
-          ImmutableSet.copyOf(metrics),
+          subBenchmarks,
           suite,
           fromRevision,
           dependencies,
-          timeout);
+          timeout,
+          measureWarmup);
     }
 
     public Builder setName(String name) {
@@ -134,7 +183,16 @@
     }
 
     public Builder measureWarmup() {
-      metrics.add(BenchmarkMetric.StartupTime);
+      measureWarmup = true;
+      return this;
+    }
+
+    public Builder addSubBenchmark(String name, BenchmarkMetric... metrics) {
+      return addSubBenchmark(name, new HashSet<>(Arrays.asList(metrics)));
+    }
+
+    public Builder addSubBenchmark(String name, Set<BenchmarkMetric> metrics) {
+      subBenchmarks.put(name, metrics);
       return this;
     }
 
@@ -165,28 +223,31 @@
 
   private final BenchmarkIdentifier id;
   private final BenchmarkMethod method;
-  private final ImmutableSet<BenchmarkMetric> metrics;
+  private final Map<String, Set<BenchmarkMetric>> benchmarks;
   private final BenchmarkSuite suite;
   private final Collection<BenchmarkDependency> dependencies;
   private final int fromRevision;
   private final BenchmarkTimeout timeout;
+  private final boolean measureWarmup;
 
   private BenchmarkConfig(
       String name,
       BenchmarkMethod benchmarkMethod,
       BenchmarkTarget target,
-      ImmutableSet<BenchmarkMetric> metrics,
+      Map<String, Set<BenchmarkMetric>> benchmarks,
       BenchmarkSuite suite,
       int fromRevision,
       Collection<BenchmarkDependency> dependencies,
-      BenchmarkTimeout timeout) {
+      BenchmarkTimeout timeout,
+      boolean measureWarmup) {
     this.id = new BenchmarkIdentifier(name, target);
     this.method = benchmarkMethod;
-    this.metrics = metrics;
+    this.benchmarks = benchmarks;
     this.suite = suite;
     this.fromRevision = fromRevision;
     this.dependencies = dependencies;
     this.timeout = timeout;
+    this.measureWarmup = measureWarmup;
   }
 
   public BenchmarkIdentifier getIdentifier() {
@@ -205,12 +266,19 @@
     return id.getTarget();
   }
 
-  public Set<BenchmarkMetric> getMetrics() {
-    return metrics;
+  public boolean isSingleBenchmark() {
+    return benchmarks.size() == 1 && benchmarks.containsKey(getName());
   }
 
-  public boolean hasMetric(BenchmarkMetric metric) {
-    return metrics.contains(metric);
+  public Map<String, Set<BenchmarkMetric>> getSubBenchmarks() {
+    return benchmarks;
+  }
+
+  public Set<BenchmarkMetric> getMetrics() {
+    if (!isSingleBenchmark()) {
+      throw new BenchmarkConfigError("Attempt to get single metrics set from group benchmark");
+    }
+    return benchmarks.get(getName());
   }
 
   public BenchmarkSuite getSuite() {
@@ -222,7 +290,7 @@
   }
 
   public boolean hasTimeWarmupRuns() {
-    return hasMetric(BenchmarkMetric.StartupTime);
+    return measureWarmup;
   }
 
   public Collection<BenchmarkDependency> getDependencies() {
diff --git a/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResults.java b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResults.java
index 51f9f3a..4fa9f24 100644
--- a/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResults.java
+++ b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResults.java
@@ -4,98 +4,25 @@
 package com.android.tools.r8.benchmarks;
 
 import com.android.tools.r8.benchmarks.BenchmarkRunner.ResultMode;
-import it.unimi.dsi.fastutil.longs.LongArrayList;
-import it.unimi.dsi.fastutil.longs.LongList;
 
-public class BenchmarkResults {
+public interface BenchmarkResults {
+  // Append a runtime result. This may be summed or averaged depending on the benchmark set up.
+  void addRuntimeResult(long result);
 
-  private final BenchmarkMetric runtimeMetric;
-  private final LongList runtimeResults = new LongArrayList();
-  private final LongList codeSizeResults = new LongArrayList();
+  // Append a code size result. This is always assumed to be identical if called multiple times.
+  void addCodeSizeResult(long result);
 
-  public static BenchmarkResults create() {
-    return new BenchmarkResults(false);
-  }
+  // Get the results collection for a "sub-benchmark" when defining a group of benchmarks.
+  // This will throw if called on a benchmark without sub-benchmarks.
+  BenchmarkResults getSubResults(String name);
 
-  public static BenchmarkResults createForWarmup() {
-    return new BenchmarkResults(true);
-  }
+  void printResults(ResultMode resultMode);
 
-  private BenchmarkResults(boolean isWarmupResults) {
-    this.runtimeMetric = isWarmupResults ? BenchmarkMetric.StartupTime : BenchmarkMetric.RunTimeRaw;
-  }
-
-  private boolean isWarmupResults() {
-    return runtimeMetric == BenchmarkMetric.StartupTime;
-  }
-
-  private String getName(BenchmarkConfig config) {
-    return config.getName();
-  }
-
-  public void addRuntimeResult(long result) {
-    runtimeResults.add(result);
-  }
-
-  public void addCodeSizeResult(long result) {
-    codeSizeResults.add(result);
-  }
-
-  private static void verifyMetric(BenchmarkMetric metric, boolean expected, boolean actual) {
-    if (expected != actual) {
-      throw new BenchmarkConfigError(
-          "Mismatched config and result for "
-              + metric.name()
-              + ". Expected by config: "
-              + expected
-              + ", but has result: "
-              + actual);
-    }
-  }
-
-  private void verifyConfigAndResults(BenchmarkConfig config) {
-    verifyMetric(
-        BenchmarkMetric.RunTimeRaw,
-        config.getMetrics().contains(BenchmarkMetric.RunTimeRaw),
-        !runtimeResults.isEmpty());
-    verifyMetric(
-        BenchmarkMetric.CodeSize,
-        config.getMetrics().contains(BenchmarkMetric.CodeSize),
-        !codeSizeResults.isEmpty());
-  }
-
-  public static String prettyTime(long nanoTime) {
+  static String prettyTime(long nanoTime) {
     return "" + (nanoTime / 1000000) + " ms";
   }
 
-  private void printRunTime(BenchmarkConfig config, long duration) {
-    String metric = runtimeMetric.name();
-    System.out.println(getName(config) + "(" + metric + "): " + prettyTime(duration));
-  }
-
-  private void printCodeSize(BenchmarkConfig config, long bytes) {
-    System.out.println(getName(config) + "(CodeSize): " + bytes);
-  }
-
-  public void printResults(ResultMode mode, BenchmarkConfig config) {
-    verifyConfigAndResults(config);
-    if (config.hasMetric(runtimeMetric)) {
-      long sum = runtimeResults.stream().mapToLong(l -> l).sum();
-      if (mode == ResultMode.SUM) {
-        printRunTime(config, sum);
-      } else if (mode == ResultMode.AVERAGE) {
-        printRunTime(config, sum / runtimeResults.size());
-      }
-    }
-    if (!isWarmupResults() && config.hasMetric(BenchmarkMetric.CodeSize)) {
-      long size = codeSizeResults.getLong(0);
-      for (int i = 1; i < codeSizeResults.size(); i++) {
-        if (size != codeSizeResults.getLong(i)) {
-          throw new RuntimeException(
-              "Unexpected code size difference: " + size + " and " + codeSizeResults.getLong(i));
-        }
-      }
-      printCodeSize(config, size);
-    }
+  static String prettyMetric(String name, BenchmarkMetric metric, String value) {
+    return name + "(" + metric.name() + "): " + value;
   }
 }
diff --git a/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResultsCollection.java b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResultsCollection.java
new file mode 100644
index 0000000..e9b205d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResultsCollection.java
@@ -0,0 +1,49 @@
+// Copyright (c) 2022, 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.benchmarks;
+
+import com.android.tools.r8.benchmarks.BenchmarkRunner.ResultMode;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+public class BenchmarkResultsCollection implements BenchmarkResults {
+
+  private final Map<String, BenchmarkResultsSingle> results;
+
+  public BenchmarkResultsCollection(Map<String, Set<BenchmarkMetric>> benchmarks) {
+    results = new HashMap<>(benchmarks.size());
+    benchmarks.forEach(
+        (name, metrics) -> results.put(name, new BenchmarkResultsSingle(name, metrics)));
+  }
+
+  public void addRuntimeResult(long result) {
+    throw new BenchmarkConfigError(
+        "Unexpected attempt to add a runtime result to a the root of a benchmark with"
+            + " sub-benchmarks");
+  }
+
+  public void addCodeSizeResult(long result) {
+    throw new BenchmarkConfigError(
+        "Unexpected attempt to add a runtime result to a the root of a benchmark with"
+            + " sub-benchmarks");
+  }
+
+  @Override
+  public BenchmarkResults getSubResults(String name) {
+    return results.get(name);
+  }
+
+  @Override
+  public void printResults(ResultMode mode) {
+    List<String> sorted = new ArrayList<>(results.keySet());
+    sorted.sort(String::compareTo);
+    for (String name : sorted) {
+      BenchmarkResultsSingle singleResults = results.get(name);
+      singleResults.printResults(mode);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResultsSingle.java b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResultsSingle.java
new file mode 100644
index 0000000..b3c19d9
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResultsSingle.java
@@ -0,0 +1,92 @@
+// Copyright (c) 2022, 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.benchmarks;
+
+import com.android.tools.r8.benchmarks.BenchmarkRunner.ResultMode;
+import it.unimi.dsi.fastutil.longs.LongArrayList;
+import it.unimi.dsi.fastutil.longs.LongList;
+import java.util.Set;
+
+public class BenchmarkResultsSingle implements BenchmarkResults {
+
+  private String name;
+  private final Set<BenchmarkMetric> metrics;
+  private final LongList runtimeResults = new LongArrayList();
+  private final LongList codeSizeResults = new LongArrayList();
+
+  public BenchmarkResultsSingle(String name, Set<BenchmarkMetric> metrics) {
+    this.name = name;
+    this.metrics = metrics;
+  }
+
+  @Override
+  public void addRuntimeResult(long result) {
+    verifyMetric(BenchmarkMetric.RunTimeRaw, metrics.contains(BenchmarkMetric.RunTimeRaw), true);
+    runtimeResults.add(result);
+  }
+
+  @Override
+  public void addCodeSizeResult(long result) {
+    verifyMetric(BenchmarkMetric.CodeSize, metrics.contains(BenchmarkMetric.CodeSize), true);
+    codeSizeResults.add(result);
+  }
+
+  @Override
+  public BenchmarkResults getSubResults(String name) {
+    throw new BenchmarkConfigError(
+        "Unexpected attempt to get sub-results for benchmark without sub-benchmarks");
+  }
+
+  private static void verifyMetric(BenchmarkMetric metric, boolean expected, boolean actual) {
+    if (expected != actual) {
+      throw new BenchmarkConfigError(
+          "Mismatched config and result for "
+              + metric.name()
+              + ". Expected by config: "
+              + expected
+              + ", but has result: "
+              + actual);
+    }
+  }
+
+  private void verifyConfigAndResults() {
+    verifyMetric(
+        BenchmarkMetric.RunTimeRaw,
+        metrics.contains(BenchmarkMetric.RunTimeRaw),
+        !runtimeResults.isEmpty());
+    verifyMetric(
+        BenchmarkMetric.CodeSize,
+        metrics.contains(BenchmarkMetric.CodeSize),
+        !codeSizeResults.isEmpty());
+  }
+
+  private void printRunTime(long duration) {
+    String value = BenchmarkResults.prettyTime(duration);
+    System.out.println(BenchmarkResults.prettyMetric(name, BenchmarkMetric.RunTimeRaw, value));
+  }
+
+  private void printCodeSize(long bytes) {
+    System.out.println(BenchmarkResults.prettyMetric(name, BenchmarkMetric.CodeSize, "" + bytes));
+  }
+
+  @Override
+  public void printResults(ResultMode mode) {
+    verifyConfigAndResults();
+    if (!runtimeResults.isEmpty()) {
+      long sum = runtimeResults.stream().mapToLong(l -> l).sum();
+      long result = mode == ResultMode.SUM ? sum : sum / runtimeResults.size();
+      printRunTime(result);
+    }
+    if (!codeSizeResults.isEmpty()) {
+      long size = codeSizeResults.getLong(0);
+      for (int i = 1; i < codeSizeResults.size(); i++) {
+        if (size != codeSizeResults.getLong(i)) {
+          throw new RuntimeException(
+              "Unexpected code size difference: " + size + " and " + codeSizeResults.getLong(i));
+        }
+      }
+      printCodeSize(size);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResultsWarmup.java b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResultsWarmup.java
new file mode 100644
index 0000000..d866577
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkResultsWarmup.java
@@ -0,0 +1,53 @@
+// Copyright (c) 2022, 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.benchmarks;
+
+import com.android.tools.r8.benchmarks.BenchmarkRunner.ResultMode;
+import it.unimi.dsi.fastutil.longs.LongArrayList;
+import it.unimi.dsi.fastutil.longs.LongList;
+
+public class BenchmarkResultsWarmup implements BenchmarkResults {
+
+  private final String name;
+  private final LongList runtimeResults = new LongArrayList();
+  private long codeSizeResult = -1;
+
+  public BenchmarkResultsWarmup(String name) {
+    this.name = name;
+  }
+
+  @Override
+  public void addRuntimeResult(long result) {
+    runtimeResults.add(result);
+  }
+
+  @Override
+  public void addCodeSizeResult(long result) {
+    if (codeSizeResult == -1) {
+      codeSizeResult = result;
+    }
+    if (codeSizeResult != result) {
+      throw new RuntimeException(
+          "Unexpected code size difference: " + result + " and " + codeSizeResult);
+    }
+  }
+
+  @Override
+  public BenchmarkResults getSubResults(String name) {
+    // When running warmups all results are amended to the single warmup result.
+    return this;
+  }
+
+  @Override
+  public void printResults(ResultMode mode) {
+    if (runtimeResults.isEmpty()) {
+      throw new BenchmarkConfigError("Expected runtime results for warmup run");
+    }
+    long sum = runtimeResults.stream().mapToLong(l -> l).sum();
+    long result = mode == ResultMode.SUM ? sum : sum / runtimeResults.size();
+    System.out.println(
+        BenchmarkResults.prettyMetric(
+            name, BenchmarkMetric.StartupTime, BenchmarkResults.prettyTime(result)));
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/benchmarks/BenchmarkRunner.java b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkRunner.java
index f0cb0b8..0f1384c 100644
--- a/src/test/java/com/android/tools/r8/benchmarks/BenchmarkRunner.java
+++ b/src/test/java/com/android/tools/r8/benchmarks/BenchmarkRunner.java
@@ -54,7 +54,7 @@
 
   public void run(BenchmarkRunnerFunction fn) throws Exception {
     long warmupTotalTime = 0;
-    BenchmarkResults warmupResults = BenchmarkResults.createForWarmup();
+    BenchmarkResults warmupResults = new BenchmarkResultsWarmup(config.getName());
     if (warmups > 0) {
       long start = System.nanoTime();
       for (int i = 0; i < warmups; i++) {
@@ -62,7 +62,10 @@
       }
       warmupTotalTime = System.nanoTime() - start;
     }
-    BenchmarkResults results = BenchmarkResults.create();
+    BenchmarkResults results =
+        config.isSingleBenchmark()
+            ? new BenchmarkResultsSingle(config.getName(), config.getMetrics())
+            : new BenchmarkResultsCollection(config.getSubBenchmarks());
     long start = System.nanoTime();
     for (int i = 0; i < iterations; i++) {
       fn.run(results);
@@ -76,11 +79,11 @@
     if (warmups > 0) {
       printMetaInfo("warmup", warmups, warmupTotalTime);
       if (config.hasTimeWarmupRuns()) {
-        warmupResults.printResults(resultMode, config);
+        warmupResults.printResults(resultMode);
       }
     }
     printMetaInfo("benchmark", iterations, benchmarkTotalTime);
-    results.printResults(resultMode, config);
+    results.printResults(resultMode);
     System.out.println();
   }
 
diff --git a/src/test/java/com/android/tools/r8/benchmarks/appdumps/AppDumpBenchmarkBuilder.java b/src/test/java/com/android/tools/r8/benchmarks/appdumps/AppDumpBenchmarkBuilder.java
index 683d4f5..f8b16df 100644
--- a/src/test/java/com/android/tools/r8/benchmarks/appdumps/AppDumpBenchmarkBuilder.java
+++ b/src/test/java/com/android/tools/r8/benchmarks/appdumps/AppDumpBenchmarkBuilder.java
@@ -11,12 +11,17 @@
 import com.android.tools.r8.benchmarks.BenchmarkDependency;
 import com.android.tools.r8.benchmarks.BenchmarkEnvironment;
 import com.android.tools.r8.benchmarks.BenchmarkMethod;
+import com.android.tools.r8.benchmarks.BenchmarkMetric;
 import com.android.tools.r8.benchmarks.BenchmarkSuite;
 import com.android.tools.r8.benchmarks.BenchmarkTarget;
 import com.android.tools.r8.dump.CompilerDump;
 import com.android.tools.r8.dump.DumpOptions;
 import java.io.IOException;
 import java.nio.file.Path;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
 import java.util.concurrent.TimeUnit;
 
 public class AppDumpBenchmarkBuilder {
@@ -28,6 +33,7 @@
   private String name;
   private BenchmarkDependency dumpDependency;
   private int fromRevision = -1;
+  private List<String> programPackages = new ArrayList<>();
 
   public void verify() {
     if (name == null) {
@@ -64,13 +70,22 @@
     return this;
   }
 
-  public BenchmarkConfig build() {
+  public AppDumpBenchmarkBuilder addProgramPackages(String... pkgs) {
+    return addProgramPackages(Arrays.asList(pkgs));
+  }
+
+  public AppDumpBenchmarkBuilder addProgramPackages(Collection<String> pkgs) {
+    programPackages.addAll(pkgs);
+    return this;
+  }
+
+  public BenchmarkConfig buildR8() {
     verify();
     return BenchmarkConfig.builder()
         .setName(name)
         .setTarget(BenchmarkTarget.R8_NON_COMPAT)
         .setSuite(BenchmarkSuite.OPENSOURCE_BENCHMARKS)
-        .setMethod(run(this))
+        .setMethod(runR8(this))
         .setFromRevision(fromRevision)
         .addDependency(dumpDependency)
         .measureRunTime()
@@ -79,12 +94,59 @@
         .build();
   }
 
+  public BenchmarkConfig buildIncrementalD8() {
+    verify();
+    if (programPackages.isEmpty()) {
+      throw new BenchmarkConfigError(
+          "Incremental benchmark should specifiy at least one program package");
+    }
+    return BenchmarkConfig.builder()
+        .setName(name)
+        .setTarget(BenchmarkTarget.D8)
+        .setSuite(BenchmarkSuite.OPENSOURCE_BENCHMARKS)
+        .setMethod(runIncrementalD8(this))
+        .setFromRevision(fromRevision)
+        .addDependency(dumpDependency)
+        .addSubBenchmark(nameForLibraryPart(), BenchmarkMetric.RunTimeRaw)
+        .addSubBenchmark(nameForProgramPart(), BenchmarkMetric.RunTimeRaw)
+        .addSubBenchmark(nameForMergePart(), BenchmarkMetric.RunTimeRaw)
+        .setTimeout(10, TimeUnit.MINUTES)
+        .build();
+  }
+
+  public BenchmarkConfig buildBatchD8() {
+    verify();
+    return BenchmarkConfig.builder()
+        .setName(name)
+        .setTarget(BenchmarkTarget.D8)
+        .setSuite(BenchmarkSuite.OPENSOURCE_BENCHMARKS)
+        .setMethod(runBatchD8(this))
+        .setFromRevision(fromRevision)
+        .addDependency(dumpDependency)
+        .measureRunTime()
+        .measureCodeSize()
+        .setTimeout(10, TimeUnit.MINUTES)
+        .build();
+  }
+
+  private String nameForLibraryPart() {
+    return name + "Library";
+  }
+
+  private String nameForProgramPart() {
+    return name + "Program";
+  }
+
+  private String nameForMergePart() {
+    return name + "Merge";
+  }
+
   private CompilerDump getExtractedDump(BenchmarkEnvironment environment) throws IOException {
     Path dump = dumpDependency.getRoot(environment).resolve("dump_app.zip");
     return CompilerDump.fromArchive(dump, environment.getTemp().newFolder().toPath());
   }
 
-  private static BenchmarkMethod run(AppDumpBenchmarkBuilder builder) {
+  private static BenchmarkMethod runR8(AppDumpBenchmarkBuilder builder) {
     return environment ->
         BenchmarkBase.runner(environment.getConfig())
             .setWarmupIterations(1)
@@ -93,7 +155,6 @@
                   CompilerDump dump = builder.getExtractedDump(environment);
                   DumpOptions dumpProperties = dump.getBuildProperties();
                   TestBase.testForR8(environment.getTemp(), Backend.DEX)
-                      // TODO(b/221811893): mock a typical setup of program providers from agp.
                       .addProgramFiles(dump.getProgramArchive())
                       .addLibraryFiles(dump.getLibraryArchive())
                       .addKeepRuleFiles(dump.getProguardConfigFile())
@@ -109,4 +170,62 @@
                       .benchmarkCodeSize(results);
                 });
   }
+
+  private static BenchmarkMethod runBatchD8(AppDumpBenchmarkBuilder builder) {
+    return environment ->
+        BenchmarkBase.runner(environment.getConfig())
+            .setWarmupIterations(1)
+            .run(
+                results -> {
+                  CompilerDump dump = builder.getExtractedDump(environment);
+                  DumpOptions dumpProperties = dump.getBuildProperties();
+                  TestBase.testForD8(environment.getTemp(), Backend.DEX)
+                      .addProgramFiles(dump.getProgramArchive())
+                      .addLibraryFiles(dump.getLibraryArchive())
+                      .setMinApi(dumpProperties.getMinApi())
+                      .benchmarkCompile(results)
+                      .benchmarkCodeSize(results);
+                });
+  }
+
+  private static BenchmarkMethod runIncrementalD8(AppDumpBenchmarkBuilder builder) {
+    return environment ->
+        BenchmarkBase.runner(environment.getConfig())
+            .setWarmupIterations(1)
+            .reportResultSum()
+            .run(
+                results -> {
+                  CompilerDump dump = builder.getExtractedDump(environment);
+                  DumpOptions dumpProperties = dump.getBuildProperties();
+                  PackageSplitResources resources =
+                      PackageSplitResources.create(
+                          environment.getTemp(), dump.getProgramArchive(), builder.programPackages);
+                  if (resources.getPackageFiles().isEmpty()) {
+                    throw new RuntimeException("Unexpected empty set of program package files");
+                  }
+
+                  TestBase.testForD8(environment.getTemp(), Backend.DEX)
+                      .addProgramFiles(resources.getOtherFiles())
+                      .addLibraryFiles(dump.getLibraryArchive())
+                      .setMinApi(dumpProperties.getMinApi())
+                      .benchmarkCompile(results.getSubResults(builder.nameForLibraryPart()));
+
+                  List<Path> programOutputs = new ArrayList<>();
+                  for (Path programFile : resources.getPackageFiles()) {
+                    programOutputs.add(
+                        TestBase.testForD8(environment.getTemp(), Backend.DEX)
+                            .addProgramFiles(programFile)
+                            .addLibraryFiles(dump.getLibraryArchive())
+                            .setMinApi(dumpProperties.getMinApi())
+                            .setIntermediate(true)
+                            .benchmarkCompile(results.getSubResults(builder.nameForProgramPart()))
+                            .writeToZip());
+                  }
+
+                  TestBase.testForD8(environment.getTemp(), Backend.DEX)
+                      .addProgramFiles(programOutputs)
+                      .setMinApi(dumpProperties.getMinApi())
+                      .benchmarkCompile(results.getSubResults(builder.nameForMergePart()));
+                });
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/benchmarks/appdumps/PackageSplitResources.java b/src/test/java/com/android/tools/r8/benchmarks/appdumps/PackageSplitResources.java
new file mode 100644
index 0000000..b0566ac
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/benchmarks/appdumps/PackageSplitResources.java
@@ -0,0 +1,68 @@
+// Copyright (c) 2022, 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.benchmarks.appdumps;
+
+import com.android.tools.r8.utils.FileUtils;
+import com.android.tools.r8.utils.ZipUtils;
+import java.io.File;
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.util.ArrayList;
+import java.util.List;
+import org.junit.rules.TemporaryFolder;
+
+public class PackageSplitResources {
+
+  private final List<Path> packageFiles;
+  private final List<Path> otherFiles;
+
+  public PackageSplitResources(List<Path> packageFiles, List<Path> otherFiles) {
+    this.packageFiles = packageFiles;
+    this.otherFiles = otherFiles;
+  }
+
+  public static PackageSplitResources create(
+      TemporaryFolder temp, Path archive, List<String> packagePrefixes) throws IOException {
+    Path unzipDir = temp.newFolder().toPath();
+    ZipUtils.unzip(archive, unzipDir);
+    List<Path> packageFiles = new ArrayList<>();
+    List<Path> otherFiles = new ArrayList<>();
+    Files.walk(unzipDir)
+        .forEachOrdered(
+            file -> {
+              if (FileUtils.isClassFile(file)) {
+                Path relative = unzipDir.relativize(file);
+                if (isInPackagePrefixes(relative, packagePrefixes)) {
+                  packageFiles.add(file);
+                } else {
+                  otherFiles.add(file);
+                }
+              }
+            });
+
+    return new PackageSplitResources(packageFiles, otherFiles);
+  }
+
+  private static boolean isInPackagePrefixes(Path file, List<String> programPackages) {
+    String str = file.toString();
+    if (File.separatorChar != '/') {
+      str = str.replace(File.separatorChar, '/');
+    }
+    for (String packagePrefix : programPackages) {
+      if (str.startsWith(packagePrefix)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  public List<Path> getPackageFiles() {
+    return packageFiles;
+  }
+
+  public List<Path> getOtherFiles() {
+    return otherFiles;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/benchmarks/appdumps/TiviBenchmarks.java b/src/test/java/com/android/tools/r8/benchmarks/appdumps/TiviBenchmarks.java
index 56b28d4..ca31ef6 100644
--- a/src/test/java/com/android/tools/r8/benchmarks/appdumps/TiviBenchmarks.java
+++ b/src/test/java/com/android/tools/r8/benchmarks/appdumps/TiviBenchmarks.java
@@ -34,6 +34,17 @@
             .setName("TiviApp")
             .setDumpDependencyPath(dump)
             .setFromRevision(12215)
-            .build());
+            .buildR8(),
+        AppDumpBenchmarkBuilder.builder()
+            .setName("TiviApp")
+            .setDumpDependencyPath(dump)
+            .setFromRevision(12370)
+            .buildBatchD8(),
+        AppDumpBenchmarkBuilder.builder()
+            .setName("TiviIncremental")
+            .setDumpDependencyPath(dump)
+            .setFromRevision(12370)
+            .addProgramPackages("app/tivi")
+            .buildIncrementalD8());
   }
 }
diff --git a/src/test/java/com/android/tools/r8/retrace/DuplicateMappingsTest.java b/src/test/java/com/android/tools/r8/retrace/DuplicateMappingsTest.java
index 7d2ec89..06899fd 100644
--- a/src/test/java/com/android/tools/r8/retrace/DuplicateMappingsTest.java
+++ b/src/test/java/com/android/tools/r8/retrace/DuplicateMappingsTest.java
@@ -44,7 +44,7 @@
                             + " com.android.tools.r8.retrace.a:",
                         "# {'id':'sourceFile','fileName':'foobarbaz.java'}",
                         "# {'id':'sourceFile','fileName':'foobarbaz2.java'}")))
-            .setStackTrace(ImmutableList.of())
+            .setStackTrace(ImmutableList.of(" at com.android.tools.r8.retrace.a.foo(Unknown)"))
             .setRetracedStackTraceConsumer(
                 strings -> {
                   // No need to do anything, we are just checking for diagnostics.
diff --git a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiInlineInOutlineTest.java b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiInlineInOutlineTest.java
index 4e8d81e..9ca6e87 100644
--- a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiInlineInOutlineTest.java
+++ b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiInlineInOutlineTest.java
@@ -66,6 +66,7 @@
       MappingProvider mappingProvider =
           ProguardMappingProvider.builder()
               .setProguardMapProducer(ProguardMapProducer.fromString(mapping))
+              .allowLookupAllClasses()
               .build();
       Retracer retracer = Retracer.builder().setMappingProvider(mappingProvider).build();
       List<RetraceFrameElement> outlineRetraced =
diff --git a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiOutlineInOutlineStackTrace.java b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiOutlineInOutlineStackTrace.java
index ca3bb00..650953c 100644
--- a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiOutlineInOutlineStackTrace.java
+++ b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiOutlineInOutlineStackTrace.java
@@ -74,6 +74,7 @@
       MappingProvider mappingProvider =
           ProguardMappingProvider.builder()
               .setProguardMapProducer(ProguardMapProducer.fromString(mapping))
+              .allowLookupAllClasses()
               .build();
       Retracer retracer = Retracer.builder().setMappingProvider(mappingProvider).build();
       // Retrace the first outline.
diff --git a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiOutlineInlineTest.java b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiOutlineInlineTest.java
index 4401dfa..1c67ac5 100644
--- a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiOutlineInlineTest.java
+++ b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiOutlineInlineTest.java
@@ -65,6 +65,7 @@
       MappingProvider mappingProvider =
           ProguardMappingProvider.builder()
               .setProguardMapProducer(ProguardMapProducer.fromString(mapping))
+              .allowLookupAllClasses()
               .build();
       Retracer retracer = Retracer.builder().setMappingProvider(mappingProvider).build();
       List<RetraceFrameElement> outlineRetraced =
diff --git a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiOutlineNoInlineTest.java b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiOutlineNoInlineTest.java
index 5ed27fae..d77819d 100644
--- a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiOutlineNoInlineTest.java
+++ b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiOutlineNoInlineTest.java
@@ -65,6 +65,7 @@
       MappingProvider mappingProvider =
           ProguardMappingProvider.builder()
               .setProguardMapProducer(ProguardMapProducer.fromString(mapping))
+              .allowLookupAllClasses()
               .build();
       Retracer retracer = Retracer.builder().setMappingProvider(mappingProvider).build();
       List<RetraceFrameElement> outlineRetraced =
diff --git a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiRewriteFrameInlineNpeResidualTest.java b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiRewriteFrameInlineNpeResidualTest.java
index 9cd18f5..6251b54 100644
--- a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiRewriteFrameInlineNpeResidualTest.java
+++ b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiRewriteFrameInlineNpeResidualTest.java
@@ -83,6 +83,7 @@
       MappingProvider mappingProvider =
           ProguardMappingProvider.builder()
               .setProguardMapProducer(ProguardMapProducer.fromString(mapping))
+              .allowLookupAllClasses()
               .build();
       Retracer retracer = Retracer.builder().setMappingProvider(mappingProvider).build();
       List<RetraceThrownExceptionElement> npeRetraced =
diff --git a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiRewriteFrameInlineNpeTest.java b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiRewriteFrameInlineNpeTest.java
index 61ddca6..6d3bd5b 100644
--- a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiRewriteFrameInlineNpeTest.java
+++ b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiRewriteFrameInlineNpeTest.java
@@ -64,6 +64,7 @@
           ProguardMappingProvider.builder()
               .setProguardMapProducer(ProguardMapProducer.fromString(mapping))
               .setDiagnosticsHandler(testDiagnosticsHandler)
+              .allowLookupAllClasses()
               .build();
       Retracer retracer =
           Retracer.builder()
diff --git a/src/test/java/com/android/tools/r8/retrace/stacktraces/InlineSourceFileContextStackTrace.java b/src/test/java/com/android/tools/r8/retrace/stacktraces/InlineSourceFileContextStackTrace.java
index f5943b5..eb1d9f3 100644
--- a/src/test/java/com/android/tools/r8/retrace/stacktraces/InlineSourceFileContextStackTrace.java
+++ b/src/test/java/com/android/tools/r8/retrace/stacktraces/InlineSourceFileContextStackTrace.java
@@ -40,9 +40,11 @@
   public List<String> retracedStackTrace() {
     return Arrays.asList(
         "  at com.google.appreduce.remapper.KotlinJavaSourceFileTestLibrary"
-            + ".throwsException(KotlinJavaSourceFileTestLibrary.kt:22)",
+            // TODO(b/226885646): Should be KotlinJavaSourceFileTestLibrary.kt
+            + ".throwsException(KotlinJavaSourceFileTestLibrary.java:22)",
         "  at com.google.appreduce.remapper.KotlinJavaSourceFileTestLibrary"
-            + ".callsThrowsException(KotlinJavaSourceFileTestLibrary.kt:19)",
+            // TODO(b/226885646): Should be KotlinJavaSourceFileTestLibrary.kt
+            + ".callsThrowsException(KotlinJavaSourceFileTestLibrary.java:19)",
         "  at com.google.appreduce.remapper.KotlinJavaSourceFileTestObject"
             + ".main(KotlinJavaSourceFileTestObject.java:32)");
   }
@@ -51,9 +53,11 @@
   public List<String> retraceVerboseStackTrace() {
     return Arrays.asList(
         "  at com.google.appreduce.remapper.KotlinJavaSourceFileTestLibrary"
-            + ".void throwsException()(KotlinJavaSourceFileTestLibrary.kt:22)",
+            // TODO(b/226885646): Should be KotlinJavaSourceFileTestLibrary.kt
+            + ".void throwsException()(KotlinJavaSourceFileTestLibrary.java:22)",
         "  at com.google.appreduce.remapper.KotlinJavaSourceFileTestLibrary"
-            + ".void callsThrowsException()(KotlinJavaSourceFileTestLibrary.kt:19)",
+            // TODO(b/226885646): Should be KotlinJavaSourceFileTestLibrary.kt
+            + ".void callsThrowsException()(KotlinJavaSourceFileTestLibrary.java:19)",
         "  at com.google.appreduce.remapper.KotlinJavaSourceFileTestObject"
             + ".void main(java.lang.String[])(KotlinJavaSourceFileTestObject.java:32)");
   }
diff --git a/third_party/retrace/binary_compatibility.tar.gz.sha1 b/third_party/retrace/binary_compatibility.tar.gz.sha1
index 431fdbe..30ac55d 100644
--- a/third_party/retrace/binary_compatibility.tar.gz.sha1
+++ b/third_party/retrace/binary_compatibility.tar.gz.sha1
@@ -1 +1 @@
-2ebfdd6c7d270471cb38baa355d5d137af2f7dd1
\ No newline at end of file
+c7b9bd1e5be6caa0e8a8cb6634b7fb73fd48ae8e
\ No newline at end of file
diff --git a/tools/compiledump.py b/tools/compiledump.py
index a7809ac..9f3d1b0 100755
--- a/tools/compiledump.py
+++ b/tools/compiledump.py
@@ -287,12 +287,12 @@
         args.append('-D' + name + '=' + value)
   return args
 
-def download_distribution(args, version, temp):
+def download_distribution(version, nolib, temp):
   if version == 'main':
-    return utils.R8_JAR if args.nolib else utils.R8LIB_JAR
+    return utils.R8_JAR if nolib else utils.R8LIB_JAR
   if version == 'source':
     return '%s:%s' % (utils.BUILD_JAVA_MAIN_DIR, utils.ALL_DEPS_JAR)
-  name = 'r8.jar' if args.nolib else 'r8lib.jar'
+  name = 'r8.jar' if nolib else 'r8lib.jar'
   source = archive.GetUploadDestination(version, name, is_hash(version))
   dest = os.path.join(temp, 'r8.jar')
   utils.download_file_from_cloud_storage(source, dest)
@@ -367,7 +367,7 @@
     out = determine_output(args, temp)
     min_api = determine_min_api(args, build_properties)
     classfile = determine_class_file(args, build_properties)
-    jar = args.r8_jar if args.r8_jar else download_distribution(args, version, temp)
+    jar = args.r8_jar if args.r8_jar else download_distribution(version, args.nolib, temp)
     if ':' not in jar and not os.path.exists(jar):
       error("Distribution does not exist: " + jar)
     wrapper_dir = prepare_wrapper(jar, temp, jdkhome)
diff --git a/tools/run_benchmark.py b/tools/run_benchmark.py
index 545ac5a..904b509 100755
--- a/tools/run_benchmark.py
+++ b/tools/run_benchmark.py
@@ -11,6 +11,7 @@
 import gradle
 import jdk
 import utils
+import compiledump
 
 NONLIB_BUILD_TARGET = 'R8WithRelocatedDeps'
 NONLIB_TEST_BUILD_TARGETS = [utils.R8_TESTS_TARGET, utils.R8_TESTS_DEPS_TARGET]
@@ -59,14 +60,20 @@
                       help='Print timing information from r8',
                       default=False,
                       action='store_true')
+  result.add_argument('--version', '-v',
+                      help='Use R8 version/hash for the run (default local build)',
+                      default=None)
   result.add_argument('--temp',
                       help='A directory to use for temporaries and outputs.',
                       default=None)
   return result.parse_known_args(argv)
 
-def main(argv):
+def main(argv, temp):
   (options, args) = parse_options(argv)
 
+  if options.temp:
+    temp = options.temp
+
   if options.golem:
     options.no_build = True
     if options.nolib:
@@ -74,14 +81,21 @@
       return 1
 
   if options.nolib:
+    testBuildTargets = NONLIB_TEST_BUILD_TARGETS
     buildTargets = [NONLIB_BUILD_TARGET] + NONLIB_TEST_BUILD_TARGETS
     r8jar = utils.R8_WITH_RELOCATED_DEPS_JAR
     testjars = [utils.R8_TESTS_DEPS_JAR, utils.R8_TESTS_JAR]
   else:
+    testBuildTargets = R8LIB_TEST_BUILD_TARGETS
     buildTargets = GOLEM_BUILD_TARGETS
     r8jar = utils.R8LIB_JAR
     testjars = [utils.R8LIB_TESTS_DEPS_JAR, utils.R8LIB_TESTS_JAR]
 
+  if options.version:
+    # r8 is downloaded so only test jar needs to be built.
+    buildTargets = testBuildTargets
+    r8jar = compiledump.download_distribution(options.version, options.nolib, temp)
+
   if not options.no_build:
     gradle.RunGradle(buildTargets + ['-Pno_internal'])
 
@@ -104,4 +118,5 @@
   return subprocess.check_call(cmd)
 
 if __name__ == '__main__':
-  sys.exit(main(sys.argv[1:]))
+  with utils.TempDir() as temp:
+    sys.exit(main(sys.argv[1:], temp))