diff --git a/.gitignore b/.gitignore
index 2b1d423..5885615 100644
--- a/.gitignore
+++ b/.gitignore
@@ -143,6 +143,8 @@
 third_party/rhino-android-1.1.1.tar.gz
 third_party/sample_libraries
 third_party/sample_libraries.tar.gz
+third_party/tachiyomi
+third_party/tachiyomi.tar.gz
 third_party/youtube/*
 third_party/youtube-developer/20200415
 third_party/youtube-developer/20200415.tar.gz
diff --git a/build.gradle b/build.gradle
index 5c95cd6..12d14c9 100644
--- a/build.gradle
+++ b/build.gradle
@@ -333,7 +333,8 @@
                 "proguard/proguard5.2.1",
                 "proguard/proguard6.0.1",
                 "r8",
-                "r8mappings"
+                "r8mappings",
+                "tachiyomi"
         ],
         // All dex-vms have a fixed OS of Linux, as they are only supported on Linux, and will be run in a Docker
         // container on other platforms where supported.
@@ -884,25 +885,24 @@
     include "dalvik/**"
 }
 
-def generateR8LibKeepRules(name, r8Source, testSource, output) {
-    return tasks.create("generateR8LibKeepRules_" + name, Exec) {
-        doFirst {
-            standardOutput new FileOutputStream(output)
-        }
-        dependsOn r8WithRelocatedDeps
-        dependsOn r8Source
-        dependsOn testSource
-        dependsOn downloadOpenJDKrt
-        inputs.files ([r8WithRelocatedDeps.outputs, r8Source.outputs, testSource.outputs])
-        outputs.file output
-        commandLine baseR8CommandLine([
-                "printuses",
-                "--keeprules-allowobfuscation",
-                "third_party/openjdk/openjdk-rt-1.8/rt.jar",
-                r8Source.outputs.files[0],
-                testSource.outputs.files[0]])
-        workingDir = projectDir
+task generateR8LibKeepRules(type: Exec) {
+    doFirst {
+        // TODO(b/154785341): We should remove this.
+        standardOutput new FileOutputStream(r8LibGeneratedKeepRulesPath)
     }
+    dependsOn R8NoManifest
+    dependsOn r8WithRelocatedDeps
+    dependsOn testJar
+    dependsOn downloadOpenJDKrt
+    inputs.files ([r8WithRelocatedDeps.outputs, R8NoManifest.outputs, testJar.outputs])
+    outputs.file r8LibGeneratedKeepRulesPath
+    commandLine baseR8CommandLine([
+            "printuses",
+            "--keeprules-allowobfuscation",
+            "third_party/openjdk/openjdk-rt-1.8/rt.jar",
+            R8NoManifest.outputs.files[0],
+            testJar.outputs.files[0]])
+    workingDir = projectDir
 }
 
 task R8LibApiOnly {
@@ -911,35 +911,26 @@
 }
 
 task R8Lib {
-    def genRulesTask = generateR8LibKeepRules(
-            "Main",
-            R8NoManifest,
-            testJar,
-            r8LibGeneratedKeepRulesPath)
     dependsOn r8LibCreateTask(
             "Main",
-            ["src/main/keep.txt", "src/main/keep-applymapping.txt", genRulesTask.outputs.files[0]],
+            ["src/main/keep.txt",
+             "src/main/keep-applymapping.txt",
+             generateR8LibKeepRules.outputs.files[0]],
             R8NoManifest,
             r8LibPath,
-    ).dependsOn(genRulesTask)
+    ).dependsOn(generateR8LibKeepRules)
     outputs.file r8LibPath
 }
 
 task R8LibNoDeps {
-    def genRulesTask = generateR8LibKeepRules(
-            "NoDeps",
-            R8NoManifestNoDeps,
-            testJar,
-            r8LibGeneratedKeepRulesExcludeDepsPath
-    )
     dependsOn r8LibCreateTask(
             "NoDeps",
-            ["src/main/keep.txt", "src/main/keep-applymapping.txt", genRulesTask.outputs.files[0]],
+            ["src/main/keep.txt", "src/main/keep-applymapping.txt"],
             R8NoManifestNoDeps,
             r8LibExludeDepsPath,
             "--release",
             repackageDepsNoRelocate.outputs.files
-    ).dependsOn(repackageDepsNoRelocate, genRulesTask)
+    ).dependsOn(repackageDepsNoRelocate)
     outputs.file r8LibExludeDepsPath
 }
 
@@ -1730,48 +1721,26 @@
 task getJarsFromSupportLibs(type: GetJarsFromConfiguration) {
     setConfiguration(configurations.supportLibs)
 }
-def getR8LibSourceTask() {
-    if (project.hasProperty('r8lib')) {
-        return R8NoManifest
-    } else if (project.hasProperty('r8lib_no_deps')) {
-        return R8NoManifestNoDeps
-    }
-    return null
-}
-
-def getR8LibTask() {
-    if (project.hasProperty('r8lib')) {
-        return R8Lib
-    } else if (project.hasProperty('r8lib_no_deps')) {
-        return R8LibNoDeps
-    }
-    return null
-}
 
 task generateR8TestKeepRules {
     def path = "build/generated/r8tests-keep.txt"
     outputs.file path
-    if (getR8LibTask() != null) {
-        dependsOn getR8LibTask()
-        doLast {
-            file(path).write """-keep class ** { *; }
+    dependsOn R8Lib
+    doLast {
+        file(path).write """-keep class ** { *; }
 -dontshrink
 -dontoptimize
 -keepattributes *
--applymapping ${getR8LibTask().outputs.files[0]}.map
+-applymapping ${R8Lib.outputs.files[0]}.map
 """
-        }
     }
 }
 
 task buildR8LibCfTestDeps(type: Exec) {
-    if (getR8LibTask() == null) {
-        return
-    }
     def outputPath = "build/libs/r8libtestdeps-cf.jar"
     dependsOn downloadDeps
-    dependsOn getR8LibTask()
-    dependsOn getR8LibSourceTask()
+    dependsOn R8NoManifest
+    dependsOn R8Lib
     dependsOn generateR8TestKeepRules
     dependsOn testJar
     // Take all .jar files as libraries and append the generated test classes in classes/java/test.
@@ -1780,13 +1749,13 @@
     } + ["${buildDir}/classes/java/test"]
     inputs.files testJar.outputs.files +
             generateR8TestKeepRules.outputs.files +
-            getR8LibTask().outputs
+            R8Lib.outputs
     commandLine = r8CfCommandLine(
             testJar.outputs.files[0],
             outputPath,
             [generateR8TestKeepRules.outputs.files[0]],
-            ["--debug", "--classpath", getR8LibSourceTask().outputs.files[0]],
-            getR8LibSourceTask().outputs.files + addedLibraries)
+            ["--debug", "--classpath", R8NoManifest.outputs.files[0]],
+            R8NoManifest.outputs.files + addedLibraries)
     workingDir = projectDir
     outputs.file outputPath
 }
@@ -1794,17 +1763,15 @@
 task configureTestForR8Lib(type: Copy) {
     dependsOn testJar
     inputs.files buildR8LibCfTestDeps.outputs
-    if (getR8LibTask() != null) {
-        dependsOn getR8LibTask()
-        delete r8LibTestPath
-        from zipTree(buildR8LibCfTestDeps.outputs.files[0])
-        def examplesDir = file("build/test")
-        examplesDir.eachDir { dir ->
-            from ("${buildDir}/test/${dir.getName()}/classes")
-        }
-        from ("${buildDir}/runtime/examples")
-        into r8LibTestPath
+    dependsOn R8Lib
+    delete r8LibTestPath
+    from zipTree(buildR8LibCfTestDeps.outputs.files[0])
+    def examplesDir = file("build/test")
+    examplesDir.eachDir { dir ->
+        from ("${buildDir}/test/${dir.getName()}/classes")
     }
+    from ("${buildDir}/runtime/examples")
+    into r8LibTestPath
     outputs.dir r8LibTestPath
 }
 
@@ -1952,10 +1919,10 @@
     if (project.hasProperty('test_dir')) {
         systemProperty 'test_dir', project.property('test_dir')
     }
-    if (project.hasProperty('r8lib') || project.hasProperty('r8lib_no_deps')) {
+    if (project.hasProperty('r8lib')) {
         dependsOn configureTestForR8Lib
-        // R8lib should be used instead of the main output and all the tests in r8 should be mapped
-        // and exists in r8LibtestPath.
+        // R8lib should be used instead of the main output and all the tests in
+        // r8 should be mapped and exists in r8LibTestPath.
         classpath = sourceSets.test.runtimeClasspath.filter {
             !it.getAbsolutePath().contains("/build/")
         }
diff --git a/src/main/java/com/android/tools/r8/D8CommandParser.java b/src/main/java/com/android/tools/r8/D8CommandParser.java
index e9df325..aad3468 100644
--- a/src/main/java/com/android/tools/r8/D8CommandParser.java
+++ b/src/main/java/com/android/tools/r8/D8CommandParser.java
@@ -175,7 +175,7 @@
     boolean hasDefinedApiLevel = false;
     OrderedClassFileResourceProvider.Builder classpathBuilder =
         OrderedClassFileResourceProvider.builder();
-    String[] expandedArgs = FlagFile.expandFlagFiles(args, builder);
+    String[] expandedArgs = FlagFile.expandFlagFiles(args, builder::error);
     for (int i = 0; i < expandedArgs.length; i++) {
       String arg = expandedArgs[i].trim();
       String nextArg = null;
diff --git a/src/main/java/com/android/tools/r8/L8CommandParser.java b/src/main/java/com/android/tools/r8/L8CommandParser.java
index 976fb4a..90db2c6 100644
--- a/src/main/java/com/android/tools/r8/L8CommandParser.java
+++ b/src/main/java/com/android/tools/r8/L8CommandParser.java
@@ -92,7 +92,7 @@
     boolean hasDefinedApiLevel = false;
     OrderedClassFileResourceProvider.Builder classpathBuilder =
         OrderedClassFileResourceProvider.builder();
-    String[] expandedArgs = FlagFile.expandFlagFiles(args, builder);
+    String[] expandedArgs = FlagFile.expandFlagFiles(args, builder::error);
     for (int i = 0; i < expandedArgs.length; i++) {
       String arg = expandedArgs[i].trim();
       String nextArg = null;
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 17c6a0a..61c4930 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -28,6 +28,7 @@
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.graph.GraphLense.NestedGraphLense;
 import com.android.tools.r8.graph.InitClassLens;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.graph.analysis.ClassInitializerAssertionEnablingAnalysis;
 import com.android.tools.r8.graph.analysis.InitializedClassesInInstanceMethodsAnalysis;
 import com.android.tools.r8.inspector.internal.InspectorImpl;
@@ -292,8 +293,10 @@
       List<ProguardConfigurationRule> synthesizedProguardRules = new ArrayList<>();
       timing.begin("Strip unused code");
       Set<DexType> classesToRetainInnerClassAttributeFor = null;
-      Set<DexType> missingClasses = appView.appInfo().getMissingClasses();
+      Set<DexType> missingClasses = null;
       try {
+        // TODO(b/154849103): Find a better way to determine missing classes.
+        missingClasses = new SubtypingInfo(application.allClasses(), appView).getMissingClasses();
         missingClasses = filterMissingClasses(
             missingClasses, options.getProguardConfiguration().getDontWarnPatterns());
         if (!missingClasses.isEmpty()) {
@@ -385,7 +388,9 @@
                       removedClasses,
                       pruner.getMethodsToKeepForConfigurationDebugging()));
           appView.setAppServices(appView.appServices().prunedCopy(removedClasses));
-          new AbstractMethodRemover(appView.appInfo().withLiveness()).run();
+          new AbstractMethodRemover(
+                  appViewWithLiveness, appViewWithLiveness.appInfo().computeSubtypingInfo())
+              .run();
 
           AnnotationRemover annotationRemover =
               annotationRemoverBuilder
@@ -426,9 +431,11 @@
       appView.dexItemFactory().clearTypeElementsCache();
 
       if (options.getProguardConfiguration().isAccessModificationAllowed()) {
+        AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
+        SubtypingInfo subtypingInfo = appViewWithLiveness.appInfo().computeSubtypingInfo();
         GraphLense publicizedLense =
             ClassAndMemberPublicizer.run(
-                executorService, timing, application, appView.withLiveness());
+                executorService, timing, application, appViewWithLiveness, subtypingInfo);
         boolean changed = appView.setGraphLense(publicizedLense);
         if (changed) {
           // We can now remove visibility bridges. Note that we do not need to update the
@@ -494,11 +501,13 @@
         timing.end();
       }
       if (options.enableArgumentRemoval) {
+        SubtypingInfo subtypingInfo = appViewWithLiveness.appInfo().computeSubtypingInfo();
         if (options.enableUnusedArgumentRemoval) {
           timing.begin("UnusedArgumentRemoval");
           UnusedArgumentsGraphLense lens =
               new UnusedArgumentsCollector(
-                      appViewWithLiveness, new MethodPoolCollection(appViewWithLiveness))
+                      appViewWithLiveness,
+                      new MethodPoolCollection(appViewWithLiveness, subtypingInfo))
                   .run(executorService, timing);
           if (lens != null) {
             boolean changed = appView.setGraphLense(lens);
@@ -513,7 +522,10 @@
           timing.begin("UninstantiatedTypeOptimization");
           UninstantiatedTypeOptimizationGraphLense lens =
               new UninstantiatedTypeOptimization(appViewWithLiveness)
-                  .run(new MethodPoolCollection(appViewWithLiveness), executorService, timing);
+                  .run(
+                      new MethodPoolCollection(appViewWithLiveness, subtypingInfo),
+                      executorService,
+                      timing);
           if (lens != null) {
             boolean changed = appView.setGraphLense(lens);
             assert changed;
@@ -730,16 +742,12 @@
           // If proto shrinking is enabled, we need to reprocess every dynamicMethod(). This ensures
           // that proto fields that have been removed by the second round of tree shaking are also
           // removed from the proto schemas in the bytecode.
-          // TODO(b/112437944): Avoid iterating the entire application to post-process every
-          //  dynamicMethod() method.
           appView.withGeneratedMessageLiteShrinker(
               shrinker -> shrinker.postOptimizeDynamicMethods(converter, executorService, timing));
 
           // If proto shrinking is enabled, we need to post-process every
           // findLiteExtensionByNumber() method. This ensures that there are no references to dead
           // extensions that have been removed by the second round of tree shaking.
-          // TODO(b/112437944): Avoid iterating the entire application to post-process every
-          //  findLiteExtensionByNumber() method.
           appView.withGeneratedExtensionRegistryShrinker(
               shrinker ->
                   shrinker.postOptimizeGeneratedExtensionRegistry(
diff --git a/src/main/java/com/android/tools/r8/R8CommandParser.java b/src/main/java/com/android/tools/r8/R8CommandParser.java
index 84aa83e..f04f937 100644
--- a/src/main/java/com/android/tools/r8/R8CommandParser.java
+++ b/src/main/java/com/android/tools/r8/R8CommandParser.java
@@ -130,7 +130,7 @@
 
   private void parse(
       String[] args, Origin argsOrigin, R8Command.Builder builder, ParseState state) {
-    String[] expandedArgs = FlagFile.expandFlagFiles(args, builder);
+    String[] expandedArgs = FlagFile.expandFlagFiles(args, builder::error);
     for (int i = 0; i < expandedArgs.length; i++) {
       String arg = expandedArgs[i].trim();
       String nextArg = null;
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
index 75ee97e..794745f 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
@@ -3,148 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.graph;
 
-import static com.android.tools.r8.ir.desugar.LambdaRewriter.LAMBDA_GROUP_CLASS_NAME_PREFIX;
-
-import com.android.tools.r8.ir.desugar.LambdaDescriptor;
-import com.android.tools.r8.utils.SetUtils;
-import com.android.tools.r8.utils.WorkList;
-import com.google.common.annotations.VisibleForTesting;
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Iterables;
-import com.google.common.collect.Sets;
-import java.util.ArrayDeque;
 import java.util.Collection;
-import java.util.Collections;
-import java.util.Deque;
-import java.util.HashSet;
-import java.util.IdentityHashMap;
-import java.util.Map;
-import java.util.Set;
-import java.util.concurrent.ConcurrentHashMap;
-import java.util.concurrent.ConcurrentSkipListSet;
-import java.util.function.Consumer;
-import java.util.function.Function;
 
-public class AppInfoWithSubtyping extends AppInfoWithClassHierarchy
-    implements InstantiatedSubTypeInfo {
-
-  private static final int ROOT_LEVEL = 0;
-  private static final int UNKNOWN_LEVEL = -1;
-  private static final int INTERFACE_LEVEL = -2;
-  // Since most Java types has no sub-types, we can just share an empty immutable set until we need
-  // to add to it.
-  private static final Set<DexType> NO_DIRECT_SUBTYPE = ImmutableSet.of();
-
-  @Override
-  public void forEachInstantiatedSubType(
-      DexType type,
-      Consumer<DexProgramClass> subTypeConsumer,
-      Consumer<LambdaDescriptor> lambdaConsumer) {
-    WorkList<DexType> workList = WorkList.newIdentityWorkList();
-    workList.addIfNotSeen(type);
-    while (workList.hasNext()) {
-      DexType subType = workList.next();
-      DexProgramClass clazz = definitionForProgramType(subType);
-      if (clazz != null) {
-        subTypeConsumer.accept(clazz);
-      }
-      workList.addIfNotSeen(allImmediateSubtypes(subType));
-    }
-    // TODO(b/148769279): Change this when we have information about callsites.
-    //  This should effectively disappear once AppInfoWithLiveness implements support.
-  }
-
-  private static class TypeInfo {
-
-    private final DexType type;
-
-    int hierarchyLevel = UNKNOWN_LEVEL;
-    /**
-     * Set of direct subtypes. This set has to remain sorted to ensure determinism. The actual
-     * sorting is not important but {@link DexType#slowCompareTo(DexType)} works well.
-     */
-    Set<DexType> directSubtypes = NO_DIRECT_SUBTYPE;
-
-    // Caching what interfaces this type is implementing. This includes super-interface hierarchy.
-    Set<DexType> implementedInterfaces = null;
-
-    TypeInfo(DexType type) {
-      this.type = type;
-    }
-
-    @Override
-    public String toString() {
-      return "TypeInfo{" + type + ", level:" + hierarchyLevel + "}";
-    }
-
-    private void ensureDirectSubTypeSet() {
-      if (directSubtypes == NO_DIRECT_SUBTYPE) {
-        directSubtypes = new ConcurrentSkipListSet<>(DexType::slowCompareTo);
-      }
-    }
-
-    private void setLevel(int level) {
-      if (level == hierarchyLevel) {
-        return;
-      }
-      if (hierarchyLevel == INTERFACE_LEVEL) {
-        assert level == ROOT_LEVEL + 1;
-      } else if (level == INTERFACE_LEVEL) {
-        assert hierarchyLevel == ROOT_LEVEL + 1 || hierarchyLevel == UNKNOWN_LEVEL;
-        hierarchyLevel = INTERFACE_LEVEL;
-      } else {
-        assert hierarchyLevel == UNKNOWN_LEVEL;
-        hierarchyLevel = level;
-      }
-    }
-
-    synchronized void addDirectSubtype(TypeInfo subtypeInfo) {
-      assert hierarchyLevel != UNKNOWN_LEVEL;
-      ensureDirectSubTypeSet();
-      directSubtypes.add(subtypeInfo.type);
-      subtypeInfo.setLevel(hierarchyLevel + 1);
-    }
-
-    void tagAsSubtypeRoot() {
-      setLevel(ROOT_LEVEL);
-    }
-
-    void tagAsInterface() {
-      setLevel(INTERFACE_LEVEL);
-    }
-
-    public boolean isInterface() {
-      assert hierarchyLevel != UNKNOWN_LEVEL : "Program class missing: " + this;
-      assert type.isClassType();
-      return hierarchyLevel == INTERFACE_LEVEL;
-    }
-
-    public boolean isUnknown() {
-      return hierarchyLevel == UNKNOWN_LEVEL;
-    }
-
-    synchronized void addInterfaceSubtype(DexType type) {
-      // Interfaces all inherit from java.lang.Object. However, we assign a special level to
-      // identify them later on.
-      setLevel(INTERFACE_LEVEL);
-      ensureDirectSubTypeSet();
-      directSubtypes.add(type);
-    }
-  }
-
-  // Set of missing classes, discovered during subtypeMap computation.
-  private final Set<DexType> missingClasses = Sets.newIdentityHashSet();
-
-  // Map from types to their subtypes.
-  private final Map<DexType, ImmutableSet<DexType>> subtypeMap = new IdentityHashMap<>();
-
-  // Map from synthesized classes to their supertypes.
-  private final Map<DexType, ImmutableSet<DexType>> supertypesForSynthesizedClasses =
-      new ConcurrentHashMap<>();
-
-  // Map from types to their subtyping information.
-  private final Map<DexType, TypeInfo> typeInfo;
+public class AppInfoWithSubtyping extends AppInfoWithClassHierarchy {
 
   public AppInfoWithSubtyping(DirectMappedDexApplication application) {
     this(application, application.allClasses());
@@ -153,75 +14,13 @@
   public AppInfoWithSubtyping(
       DirectMappedDexApplication application, Collection<DexClass> classes) {
     super(application);
-    typeInfo = new ConcurrentHashMap<>();
-    // Recompute subtype map if we have modified the graph.
-    populateSubtypeMap(classes, application::definitionFor, application.dexItemFactory);
   }
 
   protected AppInfoWithSubtyping(AppInfoWithSubtyping previous) {
     super(previous);
-    missingClasses.addAll(previous.missingClasses);
-    subtypeMap.putAll(previous.subtypeMap);
-    supertypesForSynthesizedClasses.putAll(previous.supertypesForSynthesizedClasses);
-    typeInfo = new ConcurrentHashMap<>(previous.typeInfo);
     assert app() instanceof DirectMappedDexApplication;
   }
 
-  @Override
-  public void addSynthesizedClass(DexProgramClass synthesizedClass) {
-    super.addSynthesizedClass(synthesizedClass);
-    // Register synthesized type, which has two side effects:
-    //   1) Set the hierarchy level of synthesized type based on that of its super type,
-    //   2) Register the synthesized type as a subtype of the supertype.
-    //
-    // The first one makes method resolutions on that synthesized class free from assertion errors
-    // about unknown hierarchy level.
-    //
-    // For the second one, note that such addition is synchronized, but the retrieval of direct
-    // subtypes isn't. Thus, there is a chance of race conditions: utils that check/iterate direct
-    // subtypes, e.g., allImmediateSubtypes, hasSubTypes, etc., may not be able to see this new
-    // synthesized class. However, in practice, this would be okay because, in most cases,
-    // synthesized class's super type is Object, which in general has other subtypes in any way.
-    // Also, iterating all subtypes of Object usually happens before/after IR processing, i.e., as
-    // part of structural changes, such as bottom-up traversal to collect all method signatures,
-    // which are free from such race conditions. Another exceptional case is synthesized classes
-    // whose synthesis is isolated from IR processing. For example, lambda group class that merges
-    // lambdas with the same interface are synthesized/finalized even after post processing of IRs.
-    assert synthesizedClass.superType == dexItemFactory().objectType
-            || synthesizedClass.type.toString().contains(LAMBDA_GROUP_CLASS_NAME_PREFIX)
-        : "Make sure retrieval and iteration of sub types of `" + synthesizedClass.superType
-            + "` is guaranteed to be thread safe and able to see `" + synthesizedClass + "`";
-    registerNewType(synthesizedClass.type, synthesizedClass.superType);
-
-    // TODO(b/129458850): Remove when we no longer synthesize classes on-the-fly.
-    Set<DexType> visited = SetUtils.newIdentityHashSet(synthesizedClass.allImmediateSupertypes());
-    Deque<DexType> worklist = new ArrayDeque<>(visited);
-    while (!worklist.isEmpty()) {
-      DexType type = worklist.removeFirst();
-      assert visited.contains(type);
-
-      DexClass clazz = definitionFor(type);
-      if (clazz == null) {
-        continue;
-      }
-
-      for (DexType supertype : clazz.allImmediateSupertypes()) {
-        if (visited.add(supertype)) {
-          worklist.addLast(supertype);
-        }
-      }
-    }
-    if (!visited.isEmpty()) {
-      supertypesForSynthesizedClasses.put(synthesizedClass.type, ImmutableSet.copyOf(visited));
-    }
-  }
-
-  private boolean isSynthesizedClassStrictSubtypeOf(DexType synthesizedClass, DexType supertype) {
-    Set<DexType> supertypesOfSynthesizedClass =
-        supertypesForSynthesizedClasses.get(synthesizedClass);
-    return supertypesOfSynthesizedClass != null && supertypesOfSynthesizedClass.contains(supertype);
-  }
-
   private DirectMappedDexApplication getDirectApplication() {
     // TODO(herhut): Remove need for cast.
     return (DirectMappedDexApplication) app();
@@ -232,136 +31,6 @@
     return getDirectApplication().libraryClasses();
   }
 
-  public Set<DexType> getMissingClasses() {
-    assert checkIfObsolete();
-    return Collections.unmodifiableSet(missingClasses);
-  }
-
-  public Set<DexType> subtypes(DexType type) {
-    assert checkIfObsolete();
-    assert type.isClassType();
-    ImmutableSet<DexType> subtypes = subtypeMap.get(type);
-    return subtypes == null ? ImmutableSet.of() : subtypes;
-  }
-
-  private void populateSuperType(Map<DexType, Set<DexType>> map, DexType superType,
-      DexClass baseClass, Function<DexType, DexClass> definitions) {
-    if (superType != null) {
-      Set<DexType> set = map.computeIfAbsent(superType, ignore -> new HashSet<>());
-      if (set.add(baseClass.type)) {
-        // Only continue recursion if type has been added to set.
-        populateAllSuperTypes(map, superType, baseClass, definitions);
-      }
-    }
-  }
-
-  private TypeInfo getTypeInfo(DexType type) {
-    assert type != null;
-    return typeInfo.computeIfAbsent(type, TypeInfo::new);
-  }
-
-  private void populateAllSuperTypes(
-      Map<DexType, Set<DexType>> map,
-      DexType holder,
-      DexClass baseClass,
-      Function<DexType, DexClass> definitions) {
-    DexClass holderClass = definitions.apply(holder);
-    // Skip if no corresponding class is found.
-    if (holderClass != null) {
-      populateSuperType(map, holderClass.superType, baseClass, definitions);
-      if (holderClass.superType != null) {
-        getTypeInfo(holderClass.superType).addDirectSubtype(getTypeInfo(holder));
-      } else {
-        // We found java.lang.Object
-        assert dexItemFactory().objectType == holder;
-      }
-      for (DexType inter : holderClass.interfaces.values) {
-        populateSuperType(map, inter, baseClass, definitions);
-        getTypeInfo(inter).addInterfaceSubtype(holder);
-      }
-      if (holderClass.isInterface()) {
-        getTypeInfo(holder).tagAsInterface();
-      }
-    } else {
-      if (baseClass.isProgramClass() || baseClass.isClasspathClass()) {
-        missingClasses.add(holder);
-      }
-      // The subtype chain is broken, at least make this type a subtype of Object.
-      if (holder != dexItemFactory().objectType) {
-        getTypeInfo(dexItemFactory().objectType).addDirectSubtype(getTypeInfo(holder));
-      }
-    }
-  }
-
-  private void populateSubtypeMap(
-      Collection<DexClass> classes,
-      Function<DexType, DexClass> definitions,
-      DexItemFactory dexItemFactory) {
-    getTypeInfo(dexItemFactory.objectType).tagAsSubtypeRoot();
-    Map<DexType, Set<DexType>> map = new IdentityHashMap<>();
-    for (DexClass clazz : classes) {
-      populateAllSuperTypes(map, clazz.type, clazz, definitions);
-    }
-    for (Map.Entry<DexType, Set<DexType>> entry : map.entrySet()) {
-      subtypeMap.put(entry.getKey(), ImmutableSet.copyOf(entry.getValue()));
-    }
-    assert validateLevelsAreCorrect(definitions, dexItemFactory);
-  }
-
-  private boolean validateLevelsAreCorrect(
-      Function<DexType, DexClass> definitions, DexItemFactory dexItemFactory) {
-    Set<DexType> seenTypes = Sets.newIdentityHashSet();
-    Deque<DexType> worklist = new ArrayDeque<>();
-    DexType objectType = dexItemFactory.objectType;
-    worklist.add(objectType);
-    while (!worklist.isEmpty()) {
-      DexType next = worklist.pop();
-      DexClass nextHolder = definitions.apply(next);
-      DexType superType;
-      if (nextHolder == null) {
-        // We might lack the definition of Object, so guard against that.
-        superType = next == dexItemFactory.objectType ? null : dexItemFactory.objectType;
-      } else {
-        superType = nextHolder.superType;
-      }
-      assert !seenTypes.contains(next);
-      seenTypes.add(next);
-      TypeInfo nextInfo = getTypeInfo(next);
-      if (superType == null) {
-        assert nextInfo.hierarchyLevel == ROOT_LEVEL;
-      } else {
-        TypeInfo superInfo = getTypeInfo(superType);
-        assert superInfo.hierarchyLevel == nextInfo.hierarchyLevel - 1
-            || (superInfo.hierarchyLevel == ROOT_LEVEL
-                && nextInfo.hierarchyLevel == INTERFACE_LEVEL);
-        assert superInfo.directSubtypes.contains(next);
-      }
-      if (nextInfo.hierarchyLevel != INTERFACE_LEVEL) {
-        // Only traverse the class hierarchy subtypes, not interfaces.
-        worklist.addAll(nextInfo.directSubtypes);
-      } else if (nextHolder != null) {
-        // Test that the interfaces of this class are interfaces and have this class as subtype.
-        for (DexType iface : nextHolder.interfaces.values) {
-          TypeInfo ifaceInfo = getTypeInfo(iface);
-          assert ifaceInfo.directSubtypes.contains(next);
-          assert ifaceInfo.hierarchyLevel == INTERFACE_LEVEL;
-        }
-      }
-    }
-    return true;
-  }
-
-  private void registerNewType(DexType newType, DexType superType) {
-    assert checkIfObsolete();
-    // Register the relationship between this type and its superType.
-    getTypeInfo(superType).addDirectSubtype(getTypeInfo(newType));
-  }
-
-  @VisibleForTesting
-  public void registerNewTypeForTesting(DexType newType, DexType superType) {
-    registerNewType(newType, superType);
-  }
-
   @Override
   public boolean hasSubtyping() {
     assert checkIfObsolete();
@@ -373,46 +42,4 @@
     assert checkIfObsolete();
     return this;
   }
-
-  public Set<DexType> allImmediateSubtypes(DexType type) {
-    return getTypeInfo(type).directSubtypes;
-  }
-
-  public boolean hasSubtypes(DexType type) {
-    return !getTypeInfo(type).directSubtypes.isEmpty();
-  }
-
-  // TODO(b/139464956): Remove this method.
-  public Iterable<DexType> allImmediateExtendsSubtypes_(DexType type) {
-    TypeInfo info = getTypeInfo(type);
-    assert info.hierarchyLevel != UNKNOWN_LEVEL;
-    if (info.hierarchyLevel == INTERFACE_LEVEL) {
-      return Iterables.filter(info.directSubtypes, t -> getTypeInfo(t).isInterface());
-    } else if (info.hierarchyLevel == ROOT_LEVEL) {
-      // This is the object type. Filter out interfaces
-      return Iterables.filter(info.directSubtypes, t -> !getTypeInfo(t).isInterface());
-    } else {
-      return info.directSubtypes;
-    }
-  }
-
-  // TODO(b/139464956): Remove this method.
-  public Iterable<DexType> allImmediateImplementsSubtypes_(DexType type) {
-    TypeInfo info = getTypeInfo(type);
-    if (info.hierarchyLevel == INTERFACE_LEVEL) {
-      return Iterables.filter(info.directSubtypes, subtype -> !getTypeInfo(subtype).isInterface());
-    }
-    return ImmutableList.of();
-  }
-
-  // TODO(b/139464956): Remove this method.
-  public DexType getSingleSubtype_(DexType type) {
-    TypeInfo info = getTypeInfo(type);
-    assert info.hierarchyLevel != UNKNOWN_LEVEL;
-    if (info.directSubtypes.size() == 1) {
-      return Iterables.getFirst(info.directSubtypes, null);
-    } else {
-      return null;
-    }
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
index 3a55054..ef76217 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -324,7 +324,7 @@
   }
 
   public boolean canUseInitClass() {
-    return options.shouldRerunEnqueuer() && !initClassLens.isFinal();
+    return options.isShrinking() && !initClassLens.isFinal();
   }
 
   public InitClassLens initClassLens() {
diff --git a/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java b/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java
index f1cadda..9cdac51 100644
--- a/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java
+++ b/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java
@@ -7,9 +7,12 @@
 public class BottomUpClassHierarchyTraversal<T extends DexClass>
     extends ClassHierarchyTraversal<T, BottomUpClassHierarchyTraversal<T>> {
 
+  private final SubtypingInfo subtypingInfo;
+
   private BottomUpClassHierarchyTraversal(
-      AppView<? extends AppInfoWithSubtyping> appView, Scope scope) {
+      AppView<? extends AppInfoWithSubtyping> appView, SubtypingInfo subtypingInfo, Scope scope) {
     super(appView, scope);
+    this.subtypingInfo = subtypingInfo;
   }
 
   /**
@@ -17,8 +20,8 @@
    * classes) that are reachable from a given set of sources.
    */
   public static BottomUpClassHierarchyTraversal<DexClass> forAllClasses(
-      AppView<? extends AppInfoWithSubtyping> appView) {
-    return new BottomUpClassHierarchyTraversal<>(appView, Scope.ALL_CLASSES);
+      AppView<? extends AppInfoWithSubtyping> appView, SubtypingInfo subtypingInfo) {
+    return new BottomUpClassHierarchyTraversal<>(appView, subtypingInfo, Scope.ALL_CLASSES);
   }
 
   /**
@@ -26,8 +29,9 @@
    * given set of sources.
    */
   public static BottomUpClassHierarchyTraversal<DexProgramClass> forProgramClasses(
-      AppView<? extends AppInfoWithSubtyping> appView) {
-    return new BottomUpClassHierarchyTraversal<>(appView, Scope.ONLY_PROGRAM_CLASSES);
+      AppView<? extends AppInfoWithSubtyping> appView, SubtypingInfo subtypingInfo) {
+    return new BottomUpClassHierarchyTraversal<>(
+        appView, subtypingInfo, Scope.ONLY_PROGRAM_CLASSES);
   }
 
   @Override
@@ -51,7 +55,7 @@
     worklist.addFirst(clazzWithTypeT);
 
     // Add subtypes to worklist.
-    for (DexType subtype : appView.appInfo().allImmediateSubtypes(clazz.type)) {
+    for (DexType subtype : subtypingInfo.allImmediateSubtypes(clazz.type)) {
       DexClass definition = appView.definitionFor(subtype);
       if (definition != null) {
         if (scope != Scope.ONLY_PROGRAM_CLASSES || definition.isProgramClass()) {
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 221a19e..9085643 100644
--- a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
@@ -227,7 +227,7 @@
       if (appInfo.isPinned(type)) {
         return false;
       }
-      return !appInfo.hasSubtypes(type) || !appInfo.isInstantiatedIndirectly(this);
+      return !appInfo.isInstantiatedIndirectly(this);
     }
     return false;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java b/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
new file mode 100644
index 0000000..6c6e3ba
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
@@ -0,0 +1,317 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.graph;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
+import java.util.ArrayDeque;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashSet;
+import java.util.IdentityHashMap;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentSkipListSet;
+import java.util.function.Consumer;
+import java.util.function.Function;
+
+public class SubtypingInfo {
+
+  private static final int ROOT_LEVEL = 0;
+  private static final int UNKNOWN_LEVEL = -1;
+  private static final int INTERFACE_LEVEL = -2;
+  // Since most Java types has no sub-types, we can just share an empty immutable set until we
+  // need to add to it.
+  private static final Set<DexType> NO_DIRECT_SUBTYPE = ImmutableSet.of();
+  // Map from types to their subtyping information.
+  private final DexItemFactory factory;
+
+  private final Map<DexType, TypeInfo> typeInfo = new ConcurrentHashMap<>();
+
+  // Map from types to their subtypes.
+  private final Map<DexType, ImmutableSet<DexType>> subtypeMap = new IdentityHashMap<>();
+
+  // TODO(b/154849103): Don't compute these here.
+  // Set of missing classes, discovered during subtypeMap computation.
+  private final Set<DexType> missingClasses = Sets.newIdentityHashSet();
+
+  public SubtypingInfo(Collection<DexClass> classes, DexDefinitionSupplier definitions) {
+    factory = definitions.dexItemFactory();
+    // Recompute subtype map if we have modified the graph.
+    populateSubtypeMap(classes, definitions::definitionFor, factory);
+  }
+
+  private void populateSuperType(
+      Map<DexType, Set<DexType>> map,
+      DexType superType,
+      DexClass baseClass,
+      Function<DexType, DexClass> definitions) {
+    if (superType != null) {
+      Set<DexType> set = map.computeIfAbsent(superType, ignore -> new HashSet<>());
+      if (set.add(baseClass.type)) {
+        // Only continue recursion if type has been added to set.
+        populateAllSuperTypes(map, superType, baseClass, definitions);
+      }
+    }
+  }
+
+  private DexItemFactory dexItemFactory() {
+    return factory;
+  }
+
+  private TypeInfo getTypeInfo(DexType type) {
+    assert type != null;
+    return typeInfo.computeIfAbsent(type, TypeInfo::new);
+  }
+
+  private void populateAllSuperTypes(
+      Map<DexType, Set<DexType>> map,
+      DexType holder,
+      DexClass baseClass,
+      Function<DexType, DexClass> definitions) {
+    DexClass holderClass = definitions.apply(holder);
+    // Skip if no corresponding class is found.
+    if (holderClass != null) {
+      populateSuperType(map, holderClass.superType, baseClass, definitions);
+      if (holderClass.superType != null) {
+        getTypeInfo(holderClass.superType).addDirectSubtype(getTypeInfo(holder));
+      } else {
+        // We found java.lang.Object
+        assert dexItemFactory().objectType == holder;
+      }
+      for (DexType inter : holderClass.interfaces.values) {
+        populateSuperType(map, inter, baseClass, definitions);
+        getTypeInfo(inter).addInterfaceSubtype(holder);
+      }
+      if (holderClass.isInterface()) {
+        getTypeInfo(holder).tagAsInterface();
+      }
+    } else {
+      if (baseClass.isProgramClass() || baseClass.isClasspathClass()) {
+        missingClasses.add(holder);
+      }
+      // The subtype chain is broken, at least make this type a subtype of Object.
+      if (holder != dexItemFactory().objectType) {
+        getTypeInfo(dexItemFactory().objectType).addDirectSubtype(getTypeInfo(holder));
+      }
+    }
+  }
+
+  private void populateSubtypeMap(
+      Collection<DexClass> classes,
+      Function<DexType, DexClass> definitions,
+      DexItemFactory dexItemFactory) {
+    getTypeInfo(dexItemFactory.objectType).tagAsSubtypeRoot();
+    Map<DexType, Set<DexType>> map = new IdentityHashMap<>();
+    for (DexClass clazz : classes) {
+      populateAllSuperTypes(map, clazz.type, clazz, definitions);
+    }
+    for (Map.Entry<DexType, Set<DexType>> entry : map.entrySet()) {
+      subtypeMap.put(entry.getKey(), ImmutableSet.copyOf(entry.getValue()));
+    }
+    assert validateLevelsAreCorrect(definitions, dexItemFactory);
+  }
+
+  private boolean validateLevelsAreCorrect(
+      Function<DexType, DexClass> definitions, DexItemFactory dexItemFactory) {
+    Set<DexType> seenTypes = Sets.newIdentityHashSet();
+    Deque<DexType> worklist = new ArrayDeque<>();
+    DexType objectType = dexItemFactory.objectType;
+    worklist.add(objectType);
+    while (!worklist.isEmpty()) {
+      DexType next = worklist.pop();
+      DexClass nextHolder = definitions.apply(next);
+      DexType superType;
+      if (nextHolder == null) {
+        // We might lack the definition of Object, so guard against that.
+        superType = next == dexItemFactory.objectType ? null : dexItemFactory.objectType;
+      } else {
+        superType = nextHolder.superType;
+      }
+      assert !seenTypes.contains(next);
+      seenTypes.add(next);
+      TypeInfo nextInfo = getTypeInfo(next);
+      if (superType == null) {
+        assert nextInfo.hierarchyLevel == ROOT_LEVEL;
+      } else {
+        TypeInfo superInfo = getTypeInfo(superType);
+        assert superInfo.hierarchyLevel == nextInfo.hierarchyLevel - 1
+            || (superInfo.hierarchyLevel == ROOT_LEVEL
+                && nextInfo.hierarchyLevel == INTERFACE_LEVEL);
+        assert superInfo.directSubtypes.contains(next);
+      }
+      if (nextInfo.hierarchyLevel != INTERFACE_LEVEL) {
+        // Only traverse the class hierarchy subtypes, not interfaces.
+        worklist.addAll(nextInfo.directSubtypes);
+      } else if (nextHolder != null) {
+        // Test that the interfaces of this class are interfaces and have this class as subtype.
+        for (DexType iface : nextHolder.interfaces.values) {
+          TypeInfo ifaceInfo = getTypeInfo(iface);
+          assert ifaceInfo.directSubtypes.contains(next);
+          assert ifaceInfo.hierarchyLevel == INTERFACE_LEVEL;
+        }
+      }
+    }
+    return true;
+  }
+
+  public Set<DexType> getMissingClasses() {
+    return Collections.unmodifiableSet(missingClasses);
+  }
+
+  public Set<DexType> subtypes(DexType type) {
+    assert type.isClassType();
+    ImmutableSet<DexType> subtypes = subtypeMap.get(type);
+    return subtypes == null ? ImmutableSet.of() : subtypes;
+  }
+
+  public DexType getSingleDirectSubtype(DexType type) {
+    TypeInfo info = getTypeInfo(type);
+    assert info.hierarchyLevel != SubtypingInfo.UNKNOWN_LEVEL;
+    if (info.directSubtypes.size() == 1) {
+      return Iterables.getFirst(info.directSubtypes, null);
+    } else {
+      return null;
+    }
+  }
+
+  /**
+   * Apply the given function to all classes that directly extend this class.
+   *
+   * <p>If this class is an interface, then this method will visit all sub-interfaces. This deviates
+   * from the dex-file encoding, where subinterfaces "implement" their super interfaces. However, it
+   * is consistent with the source language.
+   */
+  public void forAllImmediateExtendsSubtypes(DexType type, Consumer<DexType> f) {
+    allImmediateExtendsSubtypes(type).forEach(f);
+  }
+
+  public Iterable<DexType> allImmediateExtendsSubtypes(DexType type) {
+    TypeInfo info = getTypeInfo(type);
+    assert info.hierarchyLevel != SubtypingInfo.UNKNOWN_LEVEL;
+    if (info.hierarchyLevel == SubtypingInfo.INTERFACE_LEVEL) {
+      return Iterables.filter(info.directSubtypes, t -> getTypeInfo(t).isInterface());
+    } else if (info.hierarchyLevel == SubtypingInfo.ROOT_LEVEL) {
+      // This is the object type. Filter out interfaces
+      return Iterables.filter(info.directSubtypes, t -> !getTypeInfo(t).isInterface());
+    } else {
+      return info.directSubtypes;
+    }
+  }
+
+  /**
+   * Apply the given function to all classes that directly implement this interface.
+   *
+   * <p>The implementation does not consider how the hierarchy is encoded in the dex file, where
+   * interfaces "implement" their super interfaces. Instead it takes the view of the source
+   * language, where interfaces "extend" their superinterface.
+   */
+  public void forAllImmediateImplementsSubtypes(DexType type, Consumer<DexType> f) {
+    allImmediateImplementsSubtypes(type).forEach(f);
+  }
+
+  public Iterable<DexType> allImmediateImplementsSubtypes(DexType type) {
+    TypeInfo info = getTypeInfo(type);
+    if (info.hierarchyLevel == SubtypingInfo.INTERFACE_LEVEL) {
+      return Iterables.filter(info.directSubtypes, subtype -> !getTypeInfo(subtype).isInterface());
+    }
+    return ImmutableList.of();
+  }
+
+  private static class TypeInfo {
+
+    private final DexType type;
+
+    int hierarchyLevel = UNKNOWN_LEVEL;
+    /**
+     * Set of direct subtypes. This set has to remain sorted to ensure determinism. The actual
+     * sorting is not important but {@link DexType#slowCompareTo(DexType)} works well.
+     */
+    Set<DexType> directSubtypes = NO_DIRECT_SUBTYPE;
+
+    TypeInfo(DexType type) {
+      this.type = type;
+    }
+
+    @Override
+    public String toString() {
+      return "TypeInfo{" + type + ", level:" + hierarchyLevel + "}";
+    }
+
+    private void ensureDirectSubTypeSet() {
+      if (directSubtypes == NO_DIRECT_SUBTYPE) {
+        directSubtypes = new ConcurrentSkipListSet<>(DexType::slowCompareTo);
+      }
+    }
+
+    private void setLevel(int level) {
+      if (level == hierarchyLevel) {
+        return;
+      }
+      if (hierarchyLevel == INTERFACE_LEVEL) {
+        assert level == ROOT_LEVEL + 1;
+      } else if (level == INTERFACE_LEVEL) {
+        assert hierarchyLevel == ROOT_LEVEL + 1 || hierarchyLevel == UNKNOWN_LEVEL;
+        hierarchyLevel = INTERFACE_LEVEL;
+      } else {
+        assert hierarchyLevel == UNKNOWN_LEVEL;
+        hierarchyLevel = level;
+      }
+    }
+
+    synchronized void addDirectSubtype(TypeInfo subtypeInfo) {
+      assert hierarchyLevel != UNKNOWN_LEVEL;
+      ensureDirectSubTypeSet();
+      directSubtypes.add(subtypeInfo.type);
+      subtypeInfo.setLevel(hierarchyLevel + 1);
+    }
+
+    void tagAsSubtypeRoot() {
+      setLevel(ROOT_LEVEL);
+    }
+
+    void tagAsInterface() {
+      setLevel(INTERFACE_LEVEL);
+    }
+
+    public boolean isInterface() {
+      assert hierarchyLevel != UNKNOWN_LEVEL : "Program class missing: " + this;
+      assert type.isClassType();
+      return hierarchyLevel == INTERFACE_LEVEL;
+    }
+
+    public boolean isUnknown() {
+      return hierarchyLevel == UNKNOWN_LEVEL;
+    }
+
+    synchronized void addInterfaceSubtype(DexType type) {
+      // Interfaces all inherit from java.lang.Object. However, we assign a special level to
+      // identify them later on.
+      setLevel(INTERFACE_LEVEL);
+      ensureDirectSubTypeSet();
+      directSubtypes.add(type);
+    }
+  }
+
+  public Set<DexType> allImmediateSubtypes(DexType type) {
+    return getTypeInfo(type).directSubtypes;
+  }
+
+  public boolean isUnknown(DexType type) {
+    return getTypeInfo(type).isUnknown();
+  }
+
+  public boolean hasSubtypes(DexType type) {
+    return !getTypeInfo(type).directSubtypes.isEmpty();
+  }
+
+  void registerNewType(DexType newType, DexType superType) {
+    // Register the relationship between this type and its superType.
+    getTypeInfo(superType).addDirectSubtype(getTypeInfo(newType));
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java
index b4e025c..3e493b7 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedExtensionRegistryShrinker.java
@@ -4,7 +4,6 @@
 
 package com.android.tools.r8.ir.analysis.proto;
 
-import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
 import static com.google.common.base.Predicates.not;
 
 import com.android.tools.r8.graph.AppView;
@@ -14,7 +13,6 @@
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItemFactory;
-import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.FieldAccessInfo;
@@ -176,16 +174,20 @@
   }
 
   private void forEachFindLiteExtensionByNumberMethod(Consumer<DexEncodedMethod> consumer) {
-    for (DexType type : appView.appInfo().subtypes(references.extensionRegistryLiteType)) {
-      DexProgramClass clazz = asProgramClassOrNull(appView.definitionFor(type));
-      if (clazz != null) {
-        for (DexEncodedMethod method : clazz.methods()) {
-          if (references.isFindLiteExtensionByNumberMethod(method.method)) {
-            consumer.accept(method);
-          }
-        }
-      }
-    }
+    appView
+        .appInfo()
+        .forEachInstantiatedSubType(
+            references.extensionRegistryLiteType,
+            clazz -> {
+              for (DexEncodedMethod method : clazz.methods()) {
+                if (references.isFindLiteExtensionByNumberMethod(method.method)) {
+                  consumer.accept(method);
+                }
+              }
+            },
+            lambda -> {
+              assert false;
+            });
   }
 
   public boolean isDeadProtoExtensionField(DexField field) {
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java
index 2914d30..2f152e8 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.EnumValueInfoMapCollection.EnumValueInfo;
 import com.android.tools.r8.graph.EnumValueInfoMapCollection.EnumValueInfoMap;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
 import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
 import com.android.tools.r8.ir.analysis.type.TypeElement;
@@ -117,17 +118,14 @@
 
   public static void addInliningHeuristicsForBuilderInlining(
       AppView<? extends AppInfoWithSubtyping> appView,
+      SubtypingInfo subtypingInfo,
       PredicateSet<DexType> alwaysClassInline,
       Set<DexType> neverMerge,
       Set<DexMethod> alwaysInline,
       Set<DexMethod> bypassClinitforInlining) {
     new RootSetExtension(
-            appView,
-            alwaysClassInline,
-            neverMerge,
-            alwaysInline,
-            bypassClinitforInlining)
-        .extend();
+            appView, alwaysClassInline, neverMerge, alwaysInline, bypassClinitforInlining)
+        .extend(subtypingInfo);
   }
 
   public void preprocessCallGraphBeforeCycleElimination(Map<DexMethod, Node> nodes) {
@@ -304,14 +302,14 @@
       this.bypassClinitforInlining = bypassClinitforInlining;
     }
 
-    void extend() {
+    void extend(SubtypingInfo subtypingInfo) {
       alwaysClassInlineGeneratedMessageLiteBuilders();
 
       // GeneratedMessageLite heuristics.
       alwaysInlineCreateBuilderFromGeneratedMessageLite();
 
       // * extends GeneratedMessageLite heuristics.
-      bypassClinitforInliningNewBuilderMethods();
+      bypassClinitforInliningNewBuilderMethods(subtypingInfo);
 
       // GeneratedMessageLite$Builder heuristics.
       alwaysInlineBuildPartialFromGeneratedMessageLiteExtendableBuilder();
@@ -326,8 +324,8 @@
                   .isStrictSubtypeOf(type, references.generatedMessageLiteBuilderType));
     }
 
-    private void bypassClinitforInliningNewBuilderMethods() {
-      for (DexType type : appView.appInfo().subtypes(references.generatedMessageLiteType)) {
+    private void bypassClinitforInliningNewBuilderMethods(SubtypingInfo subtypingInfo) {
+      for (DexType type : subtypingInfo.subtypes(references.generatedMessageLiteType)) {
         DexProgramClass clazz = appView.definitionFor(type).asProgramClass();
         if (clazz != null) {
           DexEncodedMethod newBuilderMethod =
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteShrinker.java
index 40b8cb5..4414507 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteShrinker.java
@@ -4,7 +4,6 @@
 
 package com.android.tools.r8.ir.analysis.proto;
 
-import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
 import static com.android.tools.r8.ir.analysis.proto.ProtoUtils.getInfoValueFromMessageInfoConstructionInvoke;
 import static com.android.tools.r8.ir.analysis.proto.ProtoUtils.getObjectsValueFromMessageInfoConstructionInvoke;
 import static com.android.tools.r8.ir.analysis.proto.ProtoUtils.setObjectsValueForMessageInfoConstructionInvoke;
@@ -14,8 +13,6 @@
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.graph.DexProgramClass;
-import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.analysis.proto.schema.ProtoMessageInfo;
 import com.android.tools.r8.ir.analysis.proto.schema.ProtoObject;
 import com.android.tools.r8.ir.analysis.type.Nullability;
@@ -94,18 +91,22 @@
 
   private void forEachDynamicMethod(Consumer<DexEncodedMethod> consumer) {
     DexItemFactory dexItemFactory = appView.dexItemFactory();
-    for (DexType type : appView.appInfo().subtypes(references.generatedMessageLiteType)) {
-      DexProgramClass clazz = asProgramClassOrNull(appView.definitionFor(type));
-      if (clazz != null) {
-        DexMethod dynamicMethod =
-            dexItemFactory.createMethod(
-                type, references.dynamicMethodProto, references.dynamicMethodName);
-        DexEncodedMethod encodedDynamicMethod = clazz.lookupVirtualMethod(dynamicMethod);
-        if (encodedDynamicMethod != null) {
-          consumer.accept(encodedDynamicMethod);
-        }
-      }
-    }
+    appView
+        .appInfo()
+        .forEachInstantiatedSubType(
+            references.generatedMessageLiteType,
+            clazz -> {
+              DexMethod dynamicMethod =
+                  dexItemFactory.createMethod(
+                      clazz.type, references.dynamicMethodProto, references.dynamicMethodName);
+              DexEncodedMethod encodedDynamicMethod = clazz.lookupVirtualMethod(dynamicMethod);
+              if (encodedDynamicMethod != null) {
+                consumer.accept(encodedDynamicMethod);
+              }
+            },
+            lambda -> {
+              assert false;
+            });
   }
 
   /**
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
index f356690..7c34ec5 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
@@ -98,6 +98,15 @@
     if (refinedReceiverLowerBoundType != null) {
       refinedReceiverLowerBound =
           asProgramClassOrNull(appView.definitionFor(refinedReceiverLowerBoundType.getClassType()));
+      // TODO(b/154822960): Check if the lower bound is a subtype of the upper bound.
+      if (refinedReceiverUpperBound != null
+          && refinedReceiverLowerBound != null
+          && !appView
+              .appInfo()
+              .isSubtype(refinedReceiverLowerBound.type, refinedReceiverUpperBound.type)) {
+        // We cannot trust the lower bound.
+        refinedReceiverLowerBound = null;
+      }
     }
     ResolutionResult resolutionResult = appView.appInfo().resolveMethod(method.holder, method);
     LookupResult lookupResult;
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
index 689bf8f..a5c4e81 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
@@ -4,8 +4,10 @@
 package com.android.tools.r8.ir.code;
 
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis;
 import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
@@ -82,10 +84,47 @@
             TypeAnalysis.getRefinedReceiverType(appViewWithLiveness, this);
         assert receiverLowerBoundType.getClassType() == refinedReceiverType
                 || receiverLowerBoundType.isBasedOnMissingClass(appViewWithLiveness)
+                || upperBoundAssumedByCallSiteOptimizationAndNoLongerInstantiated(
+                    appViewWithLiveness, refinedReceiverType, receiverLowerBoundType.getClassType())
             : "The receiver lower bound does not match the receiver type";
       }
     }
 
     return true;
   }
+
+  private boolean upperBoundAssumedByCallSiteOptimizationAndNoLongerInstantiated(
+      AppView<AppInfoWithLiveness> appViewWithLiveness,
+      DexType upperBoundType,
+      DexType lowerBoundType) {
+    // Check that information came from the CallSiteOptimization.
+    if (!getReceiver().getAliasedValue().isArgument()) {
+      return false;
+    }
+    // Check that the receiver information comes from a dynamic type.
+    if (!getReceiver().definition.isAssumeDynamicType()) {
+      return false;
+    }
+    // Now, it can be that the upper bound is more precise than the lower:
+    // class A { }
+    // class B extends A { }
+    //
+    // class Main {
+    //   new B();
+    // }
+    //
+    // Above, the callsite optimization will register that A.<init> will be called with an argument
+    // of type B and put B in as the dynamic upper bound type. However, we can also class-inline B,
+    // thereby removing the instantiation, making A effectively final.
+    // TODO(b/154822960): Perhaps we should not process this code at all?
+    DexProgramClass upperBound = appViewWithLiveness.definitionForProgramType(upperBoundType);
+    if (upperBound == null) {
+      return false;
+    }
+    if (appViewWithLiveness.appInfo().isInstantiatedDirectlyOrIndirectly(upperBound)) {
+      return false;
+    }
+    DexClass lowerBound = appViewWithLiveness.definitionFor(lowerBoundType);
+    return lowerBound != null && lowerBound.isEffectivelyFinal(appViewWithLiveness);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Value.java b/src/main/java/com/android/tools/r8/ir/code/Value.java
index ca2cdd4..87ee96f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Value.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Value.java
@@ -1171,6 +1171,16 @@
   }
 
   public ClassTypeElement getDynamicLowerBoundType(AppView<AppInfoWithLiveness> appView) {
+    // If it is a final or effectively-final class type, then we know the lower bound.
+    if (getType().isClassType()) {
+      ClassTypeElement classType = getType().asClassType();
+      DexType type = classType.getClassType();
+      DexClass clazz = appView.definitionFor(type);
+      if (clazz != null && clazz.isEffectivelyFinal(appView)) {
+        return classType;
+      }
+    }
+
     Value root = getAliasedValue();
     if (root.isPhi()) {
       return null;
@@ -1197,16 +1207,6 @@
           : lattice;
     }
 
-    // If it is a final or effectively-final class type, then we know the lower bound.
-    if (getType().isClassType()) {
-      ClassTypeElement classType = getType().asClassType();
-      DexType type = classType.getClassType();
-      DexClass clazz = appView.definitionFor(type);
-      if (clazz != null && clazz.isEffectivelyFinal(appView)) {
-        return classType;
-      }
-    }
-
     return null;
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
index 0d91bab..21228a9 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
@@ -26,6 +26,7 @@
 import static com.android.tools.r8.ir.code.Opcodes.MOVE_EXCEPTION;
 import static com.android.tools.r8.ir.code.Opcodes.NEW_ARRAY_EMPTY;
 import static com.android.tools.r8.ir.code.Opcodes.NEW_INSTANCE;
+import static com.android.tools.r8.ir.code.Opcodes.RETURN;
 import static com.android.tools.r8.ir.code.Opcodes.STATIC_GET;
 import static com.android.tools.r8.ir.code.Opcodes.STATIC_PUT;
 
@@ -80,6 +81,7 @@
 import com.android.tools.r8.ir.code.NewArrayEmpty;
 import com.android.tools.r8.ir.code.NewInstance;
 import com.android.tools.r8.ir.code.Phi;
+import com.android.tools.r8.ir.code.Return;
 import com.android.tools.r8.ir.code.StaticGet;
 import com.android.tools.r8.ir.code.StaticPut;
 import com.android.tools.r8.ir.code.Value;
@@ -491,6 +493,27 @@
             }
             break;
 
+          case RETURN:
+            {
+              Return ret = current.asReturn();
+              if (ret.isReturnVoid()) {
+                break;
+              }
+              DexType returnType = code.method.method.proto.returnType;
+              Value retValue = ret.returnValue();
+              DexType initialType =
+                  retValue.getType().isPrimitiveType()
+                      ? retValue.getType().asPrimitiveType().toDexType(factory)
+                      : factory.objectType; // Place holder, any reference type will do.
+              Value rewrittenValue =
+                  rewriteValueIfDefault(code, iterator, initialType, returnType, retValue);
+              if (retValue != rewrittenValue) {
+                Return newReturn = new Return(rewrittenValue);
+                iterator.replaceCurrentInstruction(newReturn);
+              }
+            }
+            break;
+
           default:
             if (current.hasOutValue()) {
               // For all other instructions, substitute any changed type.
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
index 49c8000..706cfa0 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
@@ -326,6 +326,9 @@
       if (options.minApiLevel < AndroidApiLevel.O.getLevel()) {
         initializeAndroidOMethodProviders(factory);
       }
+      if (options.minApiLevel < AndroidApiLevel.R.getLevel()) {
+        initializeAndroidRMethodProviders(factory);
+      }
 
       // The following providers are currently not implemented at any API level in Android.
       // They however require the Optional/Stream class to be present, either through desugared
@@ -1002,68 +1005,11 @@
               method, BackportedMethods::StringMethods_joinIterable, "joinIterable"));
     }
 
-    private void initializeJava9MethodProviders(DexItemFactory factory) {
-      // Math & StrictMath, which have some symmetric, binary-compatible APIs
-      DexType[] mathTypes = {factory.mathType, factory.strictMathType};
-      for (int i = 0; i < mathTypes.length; i++) {
-        DexType type = mathTypes[i];
-
-        // long {Math,StrictMath}.multiplyExact(long, int)
-        DexString name = factory.createString("multiplyExact");
-        DexProto proto = factory.createProto(factory.longType, factory.longType, factory.intType);
-        DexMethod method = factory.createMethod(type, proto, name);
-        addProvider(
-            new MethodGenerator(
-                method,
-                BackportedMethods::MathMethods_multiplyExactLongInt,
-                "multiplyExactLongInt"));
-
-        // long {Math,StrictMath}.multiplyFull(int, int)
-        name = factory.createString("multiplyFull");
-        proto = factory.createProto(factory.longType, factory.intType, factory.intType);
-        method = factory.createMethod(type, proto, name);
-        addProvider(new MethodGenerator(method, BackportedMethods::MathMethods_multiplyFull));
-
-        // long {Math,StrictMath}.multiplyHigh(long, long)
-        name = factory.createString("multiplyHigh");
-        proto = factory.createProto(factory.longType, factory.longType, factory.longType);
-        method = factory.createMethod(type, proto, name);
-        addProvider(new MethodGenerator(method, BackportedMethods::MathMethods_multiplyHigh));
-
-        // long {Math,StrictMath}.floorDiv(long, int)
-        name = factory.createString("floorDiv");
-        proto = factory.createProto(factory.longType, factory.longType, factory.intType);
-        method = factory.createMethod(type, proto, name);
-        addProvider(
-            new MethodGenerator(
-                method, BackportedMethods::MathMethods_floorDivLongInt, "floorDivLongInt"));
-
-        // int {Math,StrictMath}.floorMod(long, int)
-        name = factory.createString("floorMod");
-        proto = factory.createProto(factory.intType, factory.longType, factory.intType);
-        method = factory.createMethod(type, proto, name);
-        addProvider(
-            new MethodGenerator(
-                method, BackportedMethods::MathMethods_floorModLongInt, "floorModLongInt"));
-      }
-
-      // Byte
-      DexType type = factory.boxedByteType;
-
-      // int Byte.compareUnsigned(byte, byte)
-      DexString name = factory.createString("compareUnsigned");
-      DexProto proto = factory.createProto(factory.intType, factory.byteType, factory.byteType);
-      DexMethod method = factory.createMethod(type, proto, name);
-      addProvider(new MethodGenerator(method, BackportedMethods::ByteMethods_compareUnsigned));
-
-      // Short
-      type = factory.boxedShortType;
-
-      // int Short.compareUnsigned(short, short)
-      name = factory.createString("compareUnsigned");
-      proto = factory.createProto(factory.intType, factory.shortType, factory.shortType);
-      method = factory.createMethod(type, proto, name);
-      addProvider(new MethodGenerator(method, BackportedMethods::ShortMethods_compareUnsigned));
+    private void initializeAndroidRMethodProviders(DexItemFactory factory) {
+      DexType type;
+      DexString name;
+      DexProto proto;
+      DexMethod method;
 
       // Objects
       type = factory.objectsType;
@@ -1172,6 +1118,70 @@
       addProvider(new MethodGenerator(method, BackportedMethods::CollectionMethods_mapEntry));
     }
 
+    private void initializeJava9MethodProviders(DexItemFactory factory) {
+      // Math & StrictMath, which have some symmetric, binary-compatible APIs
+      DexType[] mathTypes = {factory.mathType, factory.strictMathType};
+      for (int i = 0; i < mathTypes.length; i++) {
+        DexType type = mathTypes[i];
+
+        // long {Math,StrictMath}.multiplyExact(long, int)
+        DexString name = factory.createString("multiplyExact");
+        DexProto proto = factory.createProto(factory.longType, factory.longType, factory.intType);
+        DexMethod method = factory.createMethod(type, proto, name);
+        addProvider(
+            new MethodGenerator(
+                method,
+                BackportedMethods::MathMethods_multiplyExactLongInt,
+                "multiplyExactLongInt"));
+
+        // long {Math,StrictMath}.multiplyFull(int, int)
+        name = factory.createString("multiplyFull");
+        proto = factory.createProto(factory.longType, factory.intType, factory.intType);
+        method = factory.createMethod(type, proto, name);
+        addProvider(new MethodGenerator(method, BackportedMethods::MathMethods_multiplyFull));
+
+        // long {Math,StrictMath}.multiplyHigh(long, long)
+        name = factory.createString("multiplyHigh");
+        proto = factory.createProto(factory.longType, factory.longType, factory.longType);
+        method = factory.createMethod(type, proto, name);
+        addProvider(new MethodGenerator(method, BackportedMethods::MathMethods_multiplyHigh));
+
+        // long {Math,StrictMath}.floorDiv(long, int)
+        name = factory.createString("floorDiv");
+        proto = factory.createProto(factory.longType, factory.longType, factory.intType);
+        method = factory.createMethod(type, proto, name);
+        addProvider(
+            new MethodGenerator(
+                method, BackportedMethods::MathMethods_floorDivLongInt, "floorDivLongInt"));
+
+        // int {Math,StrictMath}.floorMod(long, int)
+        name = factory.createString("floorMod");
+        proto = factory.createProto(factory.intType, factory.longType, factory.intType);
+        method = factory.createMethod(type, proto, name);
+        addProvider(
+            new MethodGenerator(
+                method, BackportedMethods::MathMethods_floorModLongInt, "floorModLongInt"));
+      }
+
+      // Byte
+      DexType type = factory.boxedByteType;
+
+      // int Byte.compareUnsigned(byte, byte)
+      DexString name = factory.createString("compareUnsigned");
+      DexProto proto = factory.createProto(factory.intType, factory.byteType, factory.byteType);
+      DexMethod method = factory.createMethod(type, proto, name);
+      addProvider(new MethodGenerator(method, BackportedMethods::ByteMethods_compareUnsigned));
+
+      // Short
+      type = factory.boxedShortType;
+
+      // int Short.compareUnsigned(short, short)
+      name = factory.createString("compareUnsigned");
+      proto = factory.createProto(factory.intType, factory.shortType, factory.shortType);
+      method = factory.createMethod(type, proto, name);
+      addProvider(new MethodGenerator(method, BackportedMethods::ShortMethods_compareUnsigned));
+    }
+
     private void initializeJava10MethodProviders(DexItemFactory factory) {
       // List
       DexType type = factory.listType;
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/MemberPoolCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/MemberPoolCollection.java
index 6e53d40..46ac1ce 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/MemberPoolCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/MemberPoolCollection.java
@@ -7,6 +7,7 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexMember;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.ThreadUtils;
@@ -32,11 +33,16 @@
 
   final Equivalence<R> equivalence;
   final AppView<AppInfoWithLiveness> appView;
+  final SubtypingInfo subtypingInfo;
   final Map<DexClass, MemberPool<R>> memberPools = new ConcurrentHashMap<>();
 
-  MemberPoolCollection(AppView<AppInfoWithLiveness> appView, Equivalence<R> equivalence) {
+  MemberPoolCollection(
+      AppView<AppInfoWithLiveness> appView,
+      Equivalence<R> equivalence,
+      SubtypingInfo subtypingInfo) {
     this.appView = appView;
     this.equivalence = equivalence;
+    this.subtypingInfo = subtypingInfo;
   }
 
   public void buildAll(ExecutorService executorService, Timing timing) throws ExecutionException {
@@ -128,33 +134,24 @@
     return superTypes;
   }
 
-  // TODO(jsjeon): maybe be part of AppInfoWithSubtyping?
   private Set<DexClass> getAllSubTypesExclusive(
       DexClass subject, Predicate<DexClass> stoppingCriterion) {
     Set<DexClass> subTypes = new HashSet<>();
     Deque<DexClass> worklist = new ArrayDeque<>();
-    appView
-        .appInfo()
-        .forAllImmediateExtendsSubtypes(
-            subject.type, type -> addNonNull(worklist, appView.definitionFor(type)));
-    appView
-        .appInfo()
-        .forAllImmediateImplementsSubtypes(
-            subject.type, type -> addNonNull(worklist, appView.definitionFor(type)));
+    subtypingInfo.forAllImmediateExtendsSubtypes(
+        subject.type, type -> addNonNull(worklist, appView.definitionFor(type)));
+    subtypingInfo.forAllImmediateImplementsSubtypes(
+        subject.type, type -> addNonNull(worklist, appView.definitionFor(type)));
     while (!worklist.isEmpty()) {
       DexClass clazz = worklist.pop();
       if (stoppingCriterion.test(clazz)) {
         continue;
       }
       if (subTypes.add(clazz)) {
-        appView
-            .appInfo()
-            .forAllImmediateExtendsSubtypes(
-                clazz.type, type -> addNonNull(worklist, appView.definitionFor(type)));
-        appView
-            .appInfo()
-            .forAllImmediateImplementsSubtypes(
-                clazz.type, type -> addNonNull(worklist, appView.definitionFor(type)));
+        subtypingInfo.forAllImmediateExtendsSubtypes(
+            clazz.type, type -> addNonNull(worklist, appView.definitionFor(type)));
+        subtypingInfo.forAllImmediateImplementsSubtypes(
+            clazz.type, type -> addNonNull(worklist, appView.definitionFor(type)));
       }
     }
     return subTypes;
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java
index 04b2874..593e827 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.MethodSignatureEquivalence;
 import com.google.common.base.Predicates;
@@ -33,14 +34,15 @@
 
   private final Predicate<DexEncodedMethod> methodTester;
 
-  public MethodPoolCollection(AppView<AppInfoWithLiveness> appView) {
-    super(appView, MethodSignatureEquivalence.get());
-    this.methodTester = Predicates.alwaysTrue();
+  public MethodPoolCollection(AppView<AppInfoWithLiveness> appView, SubtypingInfo subtypingInfo) {
+    this(appView, subtypingInfo, Predicates.alwaysTrue());
   }
 
   public MethodPoolCollection(
-      AppView<AppInfoWithLiveness> appView, Predicate<DexEncodedMethod> methodTester) {
-    super(appView, MethodSignatureEquivalence.get());
+      AppView<AppInfoWithLiveness> appView,
+      SubtypingInfo subtypingInfo,
+      Predicate<DexEncodedMethod> methodTester) {
+    super(appView, MethodSignatureEquivalence.get(), subtypingInfo);
     this.methodTester = methodTester;
   }
 
@@ -69,7 +71,7 @@
         }
       }
       if (clazz.isInterface()) {
-        for (DexType subtype : appView.appInfo().allImmediateSubtypes(clazz.type)) {
+        for (DexType subtype : subtypingInfo.allImmediateSubtypes(clazz.type)) {
           DexClass subClazz = appView.definitionFor(subtype);
           if (subClazz != null) {
             MemberPool<DexMethod> childPool =
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java
index 64a8c86..3b427cb 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java
@@ -119,8 +119,7 @@
       return null;
     }
     // Only consider effectively final class. Exception: new Base().getClass().
-    if (appView.appInfo().hasSubtypes(baseType)
-        && appView.appInfo().isInstantiatedIndirectly(clazz)
+    if (!clazz.isEffectivelyFinal(appView)
         && (in.isPhi() || !in.definition.isCreatingInstanceOrArray())) {
       return null;
     }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxer.java b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxer.java
index 61a7c13..d878322 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxer.java
@@ -136,7 +136,7 @@
             }
           }
           if (outValue.getType().isNullType()) {
-            addNullDependencies(outValue.uniqueUsers(), eligibleEnums);
+            addNullDependencies(code, outValue.uniqueUsers(), eligibleEnums);
           }
         } else {
           if (instruction.isInvokeMethod()) {
@@ -178,7 +178,7 @@
           }
         }
         if (phi.getType().isNullType()) {
-          addNullDependencies(phi.uniqueUsers(), eligibleEnums);
+          addNullDependencies(code, phi.uniqueUsers(), eligibleEnums);
         }
       }
     }
@@ -244,7 +244,7 @@
     eligibleEnums.add(constClass.getValue());
   }
 
-  private void addNullDependencies(Set<Instruction> uses, Set<DexType> eligibleEnums) {
+  private void addNullDependencies(IRCode code, Set<Instruction> uses, Set<DexType> eligibleEnums) {
     for (Instruction use : uses) {
       if (use.isInvokeMethod()) {
         InvokeMethod invokeMethod = use.asInvokeMethod();
@@ -260,12 +260,16 @@
             markEnumAsUnboxable(Reason.ENUM_METHOD_CALLED_WITH_NULL_RECEIVER, enumClass);
           }
         }
-      }
-      if (use.isFieldPut()) {
+      } else if (use.isFieldPut()) {
         DexType type = use.asFieldInstruction().getField().type;
         if (enumsUnboxingCandidates.containsKey(type)) {
           eligibleEnums.add(type);
         }
+      } else if (use.isReturn()) {
+        DexType returnType = code.method.method.proto.returnType;
+        if (enumsUnboxingCandidates.containsKey(returnType)) {
+          eligibleEnums.add(returnType);
+        }
       }
     }
   }
@@ -621,6 +625,7 @@
 
   public enum Reason {
     ELIGIBLE,
+    ANNOTATION,
     PINNED,
     DOWN_CAST,
     SUBTYPES,
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingCandidateAnalysis.java b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingCandidateAnalysis.java
index 1bda5d7..8f228b9 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingCandidateAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingCandidateAnalysis.java
@@ -42,6 +42,7 @@
         enumToUnboxCandidates.put(clazz.type, Sets.newConcurrentHashSet());
       }
     }
+    removeEnumsInAnnotations();
     removePinnedCandidates();
     return enumToUnboxCandidates;
   }
@@ -128,6 +129,30 @@
     return true;
   }
 
+  private void removeEnumsInAnnotations() {
+    for (DexProgramClass clazz : appView.appInfo().classes()) {
+      if (appView.appInfo().isSubtype(clazz.type, factory.annotationType)) {
+        removeEnumsInAnnotation(clazz);
+      }
+    }
+  }
+
+  private void removeEnumsInAnnotation(DexProgramClass clazz) {
+    // Browse annotation values types in search for enum.
+    // Each annotation value is represented by a virtual method.
+    for (DexEncodedMethod method : clazz.virtualMethods()) {
+      DexProto proto = method.method.proto;
+      assert proto.parameters.isEmpty();
+      DexType valueType = proto.returnType.toBaseType(appView.appInfo().dexItemFactory());
+      if (valueType.isClassType()
+          && enumToUnboxCandidates.containsKey(valueType)
+          && appView.appInfo().isSubtype(valueType, appView.appInfo().dexItemFactory().enumType)) {
+        enumUnboxer.reportFailure(valueType, Reason.ANNOTATION);
+        enumToUnboxCandidates.remove(valueType);
+      }
+    }
+  }
+
   private void removePinnedCandidates() {
     // A holder type, for field or method, should block enum unboxing only if the enum type is
     // also kept. This is to allow the keep rule -keepclassmembers to be used on enums while
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingRewriter.java
index 7b91c7e..383b03b 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingRewriter.java
@@ -193,7 +193,7 @@
           instruction = arrayAccess.withMemberType(MemberType.INT);
           iterator.replaceCurrentInstruction(instruction);
         }
-        assert validateArrayAccess(instruction.asArrayAccess());
+        assert validateArrayAccess(arrayAccess);
       }
     }
     assert code.isConsistentSSABeforeTypesAreCorrect();
@@ -202,6 +202,10 @@
 
   private boolean validateArrayAccess(ArrayAccess arrayAccess) {
     ArrayTypeElement arrayType = arrayAccess.array().getType().asArrayType();
+    if (arrayType == null) {
+      assert arrayAccess.array().getType().isNullType();
+      return true;
+    }
     assert arrayAccess.getMemberType() != MemberType.OBJECT
         || arrayType.getNesting() > 1
         || arrayType.getBaseType().isReferenceType();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldInitializationInfoCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldInitializationInfoCollection.java
index 6bf4c74..3ff1799 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldInitializationInfoCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldInitializationInfoCollection.java
@@ -44,8 +44,12 @@
 
     public void recordInitializationInfo(
         DexEncodedField field, InstanceFieldInitializationInfo info) {
-      assert !infos.containsKey(field.field);
-      infos.put(field.field, info);
+      recordInitializationInfo(field.field, info);
+    }
+
+    public void recordInitializationInfo(DexField field, InstanceFieldInitializationInfo info) {
+      assert !infos.containsKey(field);
+      infos.put(field, info);
     }
 
     public InstanceFieldInitializationInfoCollection build() {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/field/NonTrivialInstanceFieldInitializationInfoCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/info/field/NonTrivialInstanceFieldInitializationInfoCollection.java
index 7c7a563..2fe8a19 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/field/NonTrivialInstanceFieldInitializationInfoCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/field/NonTrivialInstanceFieldInitializationInfoCollection.java
@@ -10,7 +10,6 @@
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import java.util.IdentityHashMap;
 import java.util.Map;
 import java.util.function.BiConsumer;
 
@@ -55,13 +54,15 @@
   @Override
   public InstanceFieldInitializationInfoCollection rewrittenWithLens(
       AppView<AppInfoWithLiveness> appView, GraphLense lens) {
-    Map<DexField, InstanceFieldInitializationInfo> rewrittenInfos = new IdentityHashMap<>();
+    Builder builder = InstanceFieldInitializationInfoCollection.builder();
     infos.forEach(
         (field, info) -> {
           DexField rewrittenField = lens.lookupField(field);
           InstanceFieldInitializationInfo rewrittenInfo = info.rewrittenWithLens(appView, lens);
-          rewrittenInfos.put(rewrittenField, rewrittenInfo);
+          if (!rewrittenInfo.isUnknown()) {
+            builder.recordInitializationInfo(rewrittenField, rewrittenInfo);
+          }
         });
-    return new NonTrivialInstanceFieldInitializationInfoCollection(rewrittenInfos);
+    return builder.build();
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java
index ed3e72a..3311e1d 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java
@@ -157,9 +157,8 @@
                   || cls.instanceFields().size() > 0
                   // Only support classes directly extending java.lang.Object
                   || cls.superType != factory.objectType
-                  // Instead of requiring the class being final,
-                  // just ensure it does not have subtypes
-                  || appView.appInfo().hasSubtypes(cls.type)
+                  // The class must not have instantiated subtypes.
+                  || !cls.isEffectivelyFinal(appView)
                   // Staticizing classes implementing interfaces is more
                   // difficult, so don't support it until we really need it.
                   || !cls.interfaces.isEmpty()) {
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinClass.java b/src/main/java/com/android/tools/r8/kotlin/KotlinClass.java
index db37d8c..8be3f22 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinClass.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinClass.java
@@ -17,6 +17,7 @@
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.InnerClassAttribute;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.List;
@@ -72,7 +73,7 @@
   }
 
   @Override
-  void rewrite(AppView<AppInfoWithLiveness> appView, NamingLens lens) {
+  void rewrite(AppView<AppInfoWithLiveness> appView, SubtypingInfo subtypingInfo, NamingLens lens) {
     KotlinMetadataSynthesizer synthesizer = new KotlinMetadataSynthesizer(appView, lens, this);
     if (appView.options().enableKotlinMetadataRewritingForRenamedClasses
         && lens.lookupType(clazz.type, appView.dexItemFactory()) != clazz.type) {
@@ -128,7 +129,7 @@
     List<String> sealedSubclasses = kmClass.getSealedSubclasses();
     sealedSubclasses.clear();
     if (IS_SEALED.invoke(kmClass.getFlags())) {
-      for (DexType subtype : appView.appInfo().allImmediateSubtypes(clazz.type)) {
+      for (DexType subtype : subtypingInfo.allImmediateSubtypes(clazz.type)) {
         String classifier = synthesizer.toRenamedClassifier(subtype);
         if (classifier != null) {
           sealedSubclasses.add(classifier);
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinClassFacade.java b/src/main/java/com/android/tools/r8/kotlin/KotlinClassFacade.java
index fc3fbbe..2a60521 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinClassFacade.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinClassFacade.java
@@ -7,6 +7,7 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.DescriptorUtils;
@@ -42,7 +43,7 @@
   }
 
   @Override
-  void rewrite(AppView<AppInfoWithLiveness> appView, NamingLens lens) {
+  void rewrite(AppView<AppInfoWithLiveness> appView, SubtypingInfo subtypingInfo, NamingLens lens) {
     ListIterator<String> partClassIterator = partClassNames.listIterator();
     KotlinMetadataSynthesizer synthesizer = new KotlinMetadataSynthesizer(appView, lens, this);
     while (partClassIterator.hasNext()) {
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinClassPart.java b/src/main/java/com/android/tools/r8/kotlin/KotlinClassPart.java
index 90f265c..f0d15a4 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinClassPart.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinClassPart.java
@@ -7,6 +7,7 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.DescriptorUtils;
@@ -39,7 +40,7 @@
   }
 
   @Override
-  void rewrite(AppView<AppInfoWithLiveness> appView, NamingLens lens) {
+  void rewrite(AppView<AppInfoWithLiveness> appView, SubtypingInfo subtypingInfo, NamingLens lens) {
     DexType facadeClassType = appView.dexItemFactory().createType(
         DescriptorUtils.getDescriptorFromClassBinaryName(facadeClassName));
     KotlinMetadataSynthesizer synthesizer = new KotlinMetadataSynthesizer(appView, lens, this);
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinFile.java b/src/main/java/com/android/tools/r8/kotlin/KotlinFile.java
index 8ec966b..ae7eb41 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinFile.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinFile.java
@@ -6,6 +6,7 @@
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import kotlinx.metadata.KmPackage;
@@ -34,7 +35,7 @@
   }
 
   @Override
-  void rewrite(AppView<AppInfoWithLiveness> appView, NamingLens lens) {
+  void rewrite(AppView<AppInfoWithLiveness> appView, SubtypingInfo subtypingInfo, NamingLens lens) {
     if (!appView.options().enableKotlinMetadataRewritingForMembers) {
       return;
     }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinInfo.java
index e516ff9..ef1d2b6 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinInfo.java
@@ -12,6 +12,7 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.kotlin.KotlinMemberInfo.KotlinFieldInfo;
 import com.android.tools.r8.kotlin.KotlinMemberInfo.KotlinPropertyInfo;
 import com.android.tools.r8.kotlin.KotlinMetadataSynthesizer.KmPropertyGroup;
@@ -67,7 +68,8 @@
   // Subtypes will define how to rewrite metadata after shrinking and minification.
   // Subtypes that represent subtypes of {@link KmDeclarationContainer} can use
   // {@link #rewriteDeclarationContainer} below.
-  abstract void rewrite(AppView<AppInfoWithLiveness> appView, NamingLens lens);
+  abstract void rewrite(
+      AppView<AppInfoWithLiveness> appView, SubtypingInfo subtypingInfo, NamingLens lens);
 
   abstract KotlinClassHeader createHeader();
 
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataRewriter.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataRewriter.java
index f83796f..1c597dc 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataRewriter.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataRewriter.java
@@ -14,6 +14,7 @@
 import com.android.tools.r8.graph.DexValue.DexValueArray;
 import com.android.tools.r8.graph.DexValue.DexValueInt;
 import com.android.tools.r8.graph.DexValue.DexValueString;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.ThreadUtils;
@@ -63,6 +64,7 @@
   public void run(ExecutorService executorService) throws ExecutionException {
     // TODO(b/152283077): Don't disable the assert.
     appView.appInfo().disableDefinitionForAssert();
+    SubtypingInfo subtypingInfo = appView.appInfo().computeSubtypingInfo();
     ThreadUtils.processItems(
         appView.appInfo().classes(),
         clazz -> {
@@ -86,7 +88,7 @@
               return;
             }
 
-            kotlinInfo.rewrite(appView, lens);
+            kotlinInfo.rewrite(appView, subtypingInfo, lens);
 
             DexAnnotation newMeta = createKotlinMetadataAnnotation(kotlinInfo.createHeader());
             clazz.setAnnotations(
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClass.java b/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClass.java
index 8c4ccaf..ced14b9 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClass.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClass.java
@@ -6,6 +6,7 @@
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import kotlinx.metadata.jvm.KotlinClassHeader;
@@ -52,7 +53,7 @@
   }
 
   @Override
-  void rewrite(AppView<AppInfoWithLiveness> appView, NamingLens lens) {
+  void rewrite(AppView<AppInfoWithLiveness> appView, SubtypingInfo subtypingInfo, NamingLens lens) {
     // TODO(b/151194794): no idea yet!
     assert lens.lookupType(clazz.type, appView.dexItemFactory()) == clazz.type
             || appView.options().enableKotlinMetadataRewritingForRenamedClasses
diff --git a/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java b/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
index 5506792..c57a91a 100644
--- a/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
@@ -12,6 +12,7 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.FieldAccessInfo;
 import com.android.tools.r8.graph.FieldAccessInfoCollection;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.Timing;
@@ -30,12 +31,17 @@
 class FieldNameMinifier {
 
   private final AppView<AppInfoWithLiveness> appView;
+  private final SubtypingInfo subtypingInfo;
   private final Map<DexField, DexString> renaming = new IdentityHashMap<>();
   private Map<DexType, ReservedFieldNamingState> reservedNamingStates = new IdentityHashMap<>();
   private final MemberNamingStrategy strategy;
 
-  FieldNameMinifier(AppView<AppInfoWithLiveness> appView, MemberNamingStrategy strategy) {
+  FieldNameMinifier(
+      AppView<AppInfoWithLiveness> appView,
+      SubtypingInfo subtypingInfo,
+      MemberNamingStrategy strategy) {
     this.appView = appView;
+    this.subtypingInfo = subtypingInfo;
     this.strategy = strategy;
   }
 
@@ -107,7 +113,7 @@
               // For interfaces, propagate reserved names to all implementing classes.
               if (clazz.isInterface() && reservedNames != null) {
                 for (DexType implementationType :
-                    appView.appInfo().allImmediateImplementsSubtypes(clazz.type)) {
+                    subtypingInfo.allImmediateImplementsSubtypes(clazz.type)) {
                   DexClass implementation = appView.definitionFor(implementationType);
                   if (implementation != null) {
                     assert !implementation.isInterface();
@@ -135,7 +141,7 @@
   }
 
   private void propagateReservedFieldNamesUpwards() {
-    BottomUpClassHierarchyTraversal.forProgramClasses(appView)
+    BottomUpClassHierarchyTraversal.forProgramClasses(appView, subtypingInfo)
         .visit(
             appView.appInfo().classes(),
             clazz -> {
@@ -183,7 +189,7 @@
   }
 
   private void renameFieldsInInterfaces(Collection<DexClass> interfaces) {
-    InterfacePartitioning partioning = new InterfacePartitioning(appView);
+    InterfacePartitioning partioning = new InterfacePartitioning(this);
     for (Set<DexClass> partition : partioning.sortedPartitions(interfaces)) {
       renameFieldsInInterfacePartition(partition);
     }
@@ -216,8 +222,7 @@
 
     Set<DexType> visited = Sets.newIdentityHashSet();
     for (DexClass clazz : partition) {
-      for (DexType implementationType :
-          appView.appInfo().allImmediateImplementsSubtypes(clazz.type)) {
+      for (DexType implementationType : subtypingInfo.allImmediateImplementsSubtypes(clazz.type)) {
         if (!visited.add(implementationType)) {
           continue;
         }
@@ -283,11 +288,13 @@
 
   static class InterfacePartitioning {
 
+    private final FieldNameMinifier minfier;
     private final AppView<AppInfoWithLiveness> appView;
     private final Set<DexType> visited = Sets.newIdentityHashSet();
 
-    InterfacePartitioning(AppView<AppInfoWithLiveness> appView) {
-      this.appView = appView;
+    InterfacePartitioning(FieldNameMinifier minifier) {
+      this.minfier = minifier;
+      appView = minifier.appView;
     }
 
     private List<Set<DexClass>> sortedPartitions(Collection<DexClass> interfaces) {
@@ -327,7 +334,7 @@
         if (clazz.isInterface()) {
           partition.add(clazz);
 
-          for (DexType subtype : appView.appInfo().allImmediateSubtypes(type)) {
+          for (DexType subtype : minfier.subtypingInfo.allImmediateSubtypes(type)) {
             if (visited.add(subtype)) {
               worklist.add(subtype);
             }
@@ -336,7 +343,7 @@
           if (visited.add(clazz.superType)) {
             worklist.add(clazz.superType);
           }
-          for (DexType subclass : appView.appInfo().allImmediateExtendsSubtypes(type)) {
+          for (DexType subclass : minfier.subtypingInfo.allImmediateExtendsSubtypes(type)) {
             if (visited.add(subclass)) {
               worklist.add(subclass);
             }
diff --git a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
index 9f72270..cdb9166 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.Timing;
@@ -115,6 +116,7 @@
   }
 
   private final AppView<AppInfoWithLiveness> appView;
+  private final SubtypingInfo subtypingInfo;
   private final MemberNamingStrategy strategy;
 
   private final Map<DexMethod, DexString> renaming = new IdentityHashMap<>();
@@ -130,8 +132,12 @@
   private final MethodNamingState<?> rootNamingState;
   private final MethodReservationState<?> rootReservationState;
 
-  MethodNameMinifier(AppView<AppInfoWithLiveness> appView, MemberNamingStrategy strategy) {
+  MethodNameMinifier(
+      AppView<AppInfoWithLiveness> appView,
+      SubtypingInfo subtypingInfo,
+      MemberNamingStrategy strategy) {
     this.appView = appView;
+    this.subtypingInfo = subtypingInfo;
     this.strategy = strategy;
     rootReservationState = MethodReservationState.createRoot(getReservationKeyTransform());
     rootNamingState =
@@ -209,7 +215,7 @@
         assignNameToMethod(holder, method, namingState);
       }
     }
-    for (DexType subType : appView.appInfo().allImmediateExtendsSubtypes(type)) {
+    for (DexType subType : subtypingInfo.allImmediateExtendsSubtypes(type)) {
       assignNamesToClassesMethods(subType, namingState);
     }
   }
@@ -250,7 +256,7 @@
     // frontier forward. This will ensure all reservations are put on the library or classpath
     // frontier for the program path.
     DexClass holder = appView.definitionFor(type);
-    for (DexType subtype : appView.appInfo().allImmediateExtendsSubtypes(type)) {
+    for (DexType subtype : subtypingInfo.allImmediateExtendsSubtypes(type)) {
       reserveNamesInClasses(
           subtype,
           holder == null || holder.isNotProgramClass() ? subtype : libraryFrontier,
diff --git a/src/main/java/com/android/tools/r8/naming/Minifier.java b/src/main/java/com/android/tools/r8/naming/Minifier.java
index f2d7c1a..d83a0f0 100644
--- a/src/main/java/com/android/tools/r8/naming/Minifier.java
+++ b/src/main/java/com/android/tools/r8/naming/Minifier.java
@@ -16,6 +16,7 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.kotlin.KotlinMetadataRewriter;
 import com.android.tools.r8.naming.ClassNameMinifier.ClassNamingStrategy;
 import com.android.tools.r8.naming.ClassNameMinifier.ClassRenaming;
@@ -45,6 +46,7 @@
 
   public NamingLens run(ExecutorService executorService, Timing timing) throws ExecutionException {
     assert appView.options().isMinifying();
+    SubtypingInfo subtypingInfo = appView.appInfo().computeSubtypingInfo();
     timing.begin("ComputeInterfaces");
     Set<DexClass> interfaces = new TreeSet<>((a, b) -> a.type.slowCompareTo(b.type));
     interfaces.addAll(appView.appInfo().computeReachableInterfaces());
@@ -67,7 +69,8 @@
     MemberNamingStrategy minifyMembers = new MinifierMemberNamingStrategy(appView);
     timing.begin("MinifyMethods");
     MethodRenaming methodRenaming =
-        new MethodNameMinifier(appView, minifyMembers).computeRenaming(interfaces, timing);
+        new MethodNameMinifier(appView, subtypingInfo, minifyMembers)
+            .computeRenaming(interfaces, timing);
     timing.end();
 
     assert new MinifiedRenaming(appView, classRenaming, methodRenaming, FieldRenaming.empty())
@@ -75,7 +78,8 @@
 
     timing.begin("MinifyFields");
     FieldRenaming fieldRenaming =
-        new FieldNameMinifier(appView, minifyMembers).computeRenaming(interfaces, timing);
+        new FieldNameMinifier(appView, subtypingInfo, minifyMembers)
+            .computeRenaming(interfaces, timing);
     timing.end();
 
     NamingLens lens = new MinifiedRenaming(appView, classRenaming, methodRenaming, fieldRenaming);
diff --git a/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java b/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
index f4c32c6..9a30e79 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
@@ -15,6 +15,7 @@
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.ir.desugar.InterfaceMethodRewriter;
 import com.android.tools.r8.kotlin.KotlinMetadataRewriter;
 import com.android.tools.r8.naming.ClassNameMinifier.ClassRenaming;
@@ -87,19 +88,20 @@
   }
 
   public NamingLens run(ExecutorService executorService, Timing timing) throws ExecutionException {
+    AppInfoWithLiveness appInfo = appView.appInfo();
+    SubtypingInfo subtypingInfo = appInfo.computeSubtypingInfo();
 
     ArrayDeque<Map<DexReference, MemberNaming>> nonPrivateMembers = new ArrayDeque<>();
     Set<DexReference> notMappedReferences = new HashSet<>();
 
     timing.begin("MappingInterfaces");
     Set<DexClass> interfaces = new TreeSet<>((a, b) -> a.type.slowCompareTo(b.type));
-    AppInfoWithLiveness appInfo = appView.appInfo();
     Consumer<DexClass> consumer =
         dexClass -> {
           if (dexClass.isInterface()) {
             // Only visit top level interfaces because computeMapping will visit the hierarchy.
             if (dexClass.interfaces.isEmpty()) {
-              computeMapping(dexClass.type, nonPrivateMembers, notMappedReferences);
+              computeMapping(dexClass.type, nonPrivateMembers, notMappedReferences, subtypingInfo);
             }
             interfaces.add(dexClass);
           }
@@ -111,12 +113,12 @@
     timing.end();
 
     timing.begin("MappingClasses");
-    appInfo.forAllImmediateExtendsSubtypes(
+    subtypingInfo.forAllImmediateExtendsSubtypes(
         factory.objectType,
         subType -> {
           DexClass dexClass = appView.definitionFor(subType);
           if (dexClass != null && !dexClass.isInterface()) {
-            computeMapping(subType, nonPrivateMembers, notMappedReferences);
+            computeMapping(subType, nonPrivateMembers, notMappedReferences, subtypingInfo);
           }
         });
     assert nonPrivateMembers.isEmpty();
@@ -148,7 +150,8 @@
         new ApplyMappingMemberNamingStrategy(appView, memberNames);
     timing.begin("MinifyMethods");
     MethodRenaming methodRenaming =
-        new MethodNameMinifier(appView, nameStrategy).computeRenaming(interfaces, timing);
+        new MethodNameMinifier(appView, subtypingInfo, nameStrategy)
+            .computeRenaming(interfaces, timing);
     // Amend the method renamings with the default interface methods.
     methodRenaming.renaming.putAll(defaultInterfaceMethodImplementationNames);
     methodRenaming.renaming.putAll(additionalMethodNamings);
@@ -156,7 +159,8 @@
 
     timing.begin("MinifyFields");
     FieldRenaming fieldRenaming =
-        new FieldNameMinifier(appView, nameStrategy).computeRenaming(interfaces, timing);
+        new FieldNameMinifier(appView, subtypingInfo, nameStrategy)
+            .computeRenaming(interfaces, timing);
     fieldRenaming.renaming.putAll(additionalFieldNamings);
     timing.end();
 
@@ -180,7 +184,8 @@
   private void computeMapping(
       DexType type,
       Deque<Map<DexReference, MemberNaming>> buildUpNames,
-      Set<DexReference> notMappedReferences) {
+      Set<DexReference> notMappedReferences,
+      SubtypingInfo subtypingInfo) {
     ClassNamingForMapApplier classNaming = seedMapper.getClassNaming(type);
     DexClass dexClass = appView.definitionFor(type);
 
@@ -253,16 +258,14 @@
 
     if (nonPrivateMembers.size() > 0) {
       buildUpNames.addLast(nonPrivateMembers);
-      appView
-          .appInfo()
-          .forAllImmediateExtendsSubtypes(
-              type, subType -> computeMapping(subType, buildUpNames, notMappedReferences));
+      subtypingInfo.forAllImmediateExtendsSubtypes(
+          type,
+          subType -> computeMapping(subType, buildUpNames, notMappedReferences, subtypingInfo));
       buildUpNames.removeLast();
     } else {
-      appView
-          .appInfo()
-          .forAllImmediateExtendsSubtypes(
-              type, subType -> computeMapping(subType, buildUpNames, notMappedReferences));
+      subtypingInfo.forAllImmediateExtendsSubtypes(
+          type,
+          subType -> computeMapping(subType, buildUpNames, notMappedReferences, subtypingInfo));
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/naming/signature/GenericSignatureRewriter.java b/src/main/java/com/android/tools/r8/naming/signature/GenericSignatureRewriter.java
index 6e88574..eef8234 100644
--- a/src/main/java/com/android/tools/r8/naming/signature/GenericSignatureRewriter.java
+++ b/src/main/java/com/android/tools/r8/naming/signature/GenericSignatureRewriter.java
@@ -13,7 +13,6 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.Reporter;
@@ -32,17 +31,16 @@
 // TODO(b/129925954): Reimplement this by using the internal encoding and transformation logic.
 public class GenericSignatureRewriter {
 
-  private final AppView<AppInfoWithLiveness> appView;
+  private final AppView<?> appView;
   private final Map<DexType, DexString> renaming;
   private final InternalOptions options;
   private final Reporter reporter;
 
-  public GenericSignatureRewriter(AppView<AppInfoWithLiveness> appView) {
+  public GenericSignatureRewriter(AppView<?> appView) {
     this(appView, Maps.newIdentityHashMap());
   }
 
-  public GenericSignatureRewriter(
-      AppView<AppInfoWithLiveness> appView, Map<DexType, DexString> renaming) {
+  public GenericSignatureRewriter(AppView<?> appView, Map<DexType, DexString> renaming) {
     this.appView = appView;
     this.renaming = renaming;
     this.options = appView.options();
@@ -90,8 +88,7 @@
                               options.warningInvalidSignature(
                                   method, clazz.getOrigin(), signature, e))));
         },
-        executorService
-    );
+        executorService);
   }
 
   private DexAnnotationSet rewriteGenericSignatures(
@@ -113,8 +110,10 @@
         String signature = DexAnnotation.getSignature(annotation);
         try {
           parser.accept(signature);
+          String renamedSignature = collector.get();
+          assert verifyConsistentRenaming(parser, collector, renamedSignature);
           DexAnnotation signatureAnnotation =
-              DexAnnotation.createSignatureAnnotation(collector.get(), appView.dexItemFactory());
+              DexAnnotation.createSignatureAnnotation(renamedSignature, appView.dexItemFactory());
           rewrittenAnnotations[i] = signatureAnnotation;
         } catch (GenericSignatureFormatError e) {
           parseError.accept(signature, e);
@@ -144,6 +143,21 @@
     return new DexAnnotationSet(prunedAnnotations);
   }
 
+  /**
+   * Calling this method will clobber the parsed signature in the collector - ideally with the same
+   * string. Only use this after the original result has been collected.
+   */
+  private boolean verifyConsistentRenaming(
+      Consumer<String> parser, Supplier<String> collector, String renamedSignature) {
+    if (!options.testing.assertConsistentRenamingOfSignature) {
+      return true;
+    }
+    parser.accept(renamedSignature);
+    String reRenamedSignature = collector.get();
+    assert renamedSignature.equals(reRenamedSignature);
+    return true;
+  }
+
   private class GenericSignatureCollector implements GenericSignatureAction<DexType> {
     private StringBuilder renamedSignature;
     private final DexProgramClass currentClassContext;
@@ -187,7 +201,7 @@
       String originalDescriptor = getDescriptorFromClassBinaryName(name);
       DexType type =
           appView.graphLense().lookupType(appView.dexItemFactory().createType(originalDescriptor));
-      if (appView.appInfo().wasPruned(type)) {
+      if (appView.appInfo().hasLiveness() && appView.withLiveness().appInfo().wasPruned(type)) {
         type = appView.dexItemFactory().objectType;
       }
       DexString renamedDescriptor = renaming.getOrDefault(type, type.descriptor);
diff --git a/src/main/java/com/android/tools/r8/optimize/BridgeHoisting.java b/src/main/java/com/android/tools/r8/optimize/BridgeHoisting.java
index d3ca402..d4a5b7e 100644
--- a/src/main/java/com/android/tools/r8/optimize/BridgeHoisting.java
+++ b/src/main/java/com/android/tools/r8/optimize/BridgeHoisting.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.GraphLense.NestedGraphLense;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.ir.optimize.info.bridge.BridgeInfo;
 import com.android.tools.r8.ir.optimize.info.bridge.VirtualBridgeInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
@@ -61,9 +62,10 @@
   }
 
   public void run() {
-    BottomUpClassHierarchyTraversal.forProgramClasses(appView)
+    SubtypingInfo subtypingInfo = appView.appInfo().computeSubtypingInfo();
+    BottomUpClassHierarchyTraversal.forProgramClasses(appView, subtypingInfo)
         .excludeInterfaces()
-        .visit(appView.appInfo().classes(), this::processClass);
+        .visit(appView.appInfo().classes(), clazz -> processClass(clazz, subtypingInfo));
     if (!lensBuilder.isEmpty()) {
       BridgeHoistingLens lens = lensBuilder.build(appView);
       boolean changed = appView.setGraphLense(lens);
@@ -73,8 +75,8 @@
     }
   }
 
-  private void processClass(DexProgramClass clazz) {
-    Set<DexType> subtypes = appView.appInfo().allImmediateSubtypes(clazz.type);
+  private void processClass(DexProgramClass clazz, SubtypingInfo subtypingInfo) {
+    Set<DexType> subtypes = subtypingInfo.allImmediateSubtypes(clazz.type);
     Set<DexProgramClass> subclasses = new TreeSet<>((x, y) -> x.type.slowCompareTo(y.type));
     for (DexType subtype : subtypes) {
       DexProgramClass subclass = asProgramClassOrNull(appView.definitionFor(subtype));
diff --git a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
index a52d044..8315925 100644
--- a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
+++ b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
@@ -15,6 +15,7 @@
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.graph.InnerClassAttribute;
 import com.android.tools.r8.graph.MethodAccessFlags;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.ir.optimize.MethodPoolCollection;
 import com.android.tools.r8.optimize.PublicizerLense.PublicizedLenseBuilder;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
@@ -29,17 +30,22 @@
 
   private final DexApplication application;
   private final AppView<AppInfoWithLiveness> appView;
+  private final SubtypingInfo subtypingInfo;
   private final MethodPoolCollection methodPoolCollection;
 
   private final PublicizedLenseBuilder lenseBuilder = PublicizerLense.createBuilder();
 
   private ClassAndMemberPublicizer(
-      DexApplication application, AppView<AppInfoWithLiveness> appView) {
+      DexApplication application,
+      AppView<AppInfoWithLiveness> appView,
+      SubtypingInfo subtypingInfo) {
     this.application = application;
     this.appView = appView;
+    this.subtypingInfo = subtypingInfo;
     this.methodPoolCollection =
         // We will add private instance methods when we promote them.
-        new MethodPoolCollection(appView, MethodPoolCollection::excludesPrivateInstanceMethod);
+        new MethodPoolCollection(
+            appView, subtypingInfo, MethodPoolCollection::excludesPrivateInstanceMethod);
   }
 
   /**
@@ -52,9 +58,11 @@
       ExecutorService executorService,
       Timing timing,
       DexApplication application,
-      AppView<AppInfoWithLiveness> appView)
+      AppView<AppInfoWithLiveness> appView,
+      SubtypingInfo subtypingInfo)
       throws ExecutionException {
-    return new ClassAndMemberPublicizer(application, appView).run(executorService, timing);
+    return new ClassAndMemberPublicizer(application, appView, subtypingInfo)
+        .run(executorService, timing);
   }
 
   private GraphLense run(ExecutorService executorService, Timing timing)
@@ -102,7 +110,7 @@
       }
     }
 
-    appView.appInfo().forAllImmediateExtendsSubtypes(type, this::publicizeType);
+    subtypingInfo.forAllImmediateExtendsSubtypes(type, this::publicizeType);
   }
 
   private boolean publicizeMethod(DexClass holder, DexEncodedMethod encodedMethod) {
diff --git a/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java b/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java
index fdd4da0..1fcb9e0 100644
--- a/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java
@@ -3,9 +3,11 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.shaking;
 
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.shaking.ScopedDexMethodSet.AddMethodIfMoreVisibleResult;
 import java.util.ArrayList;
@@ -22,20 +24,22 @@
  */
 public class AbstractMethodRemover {
 
-  private final AppInfoWithLiveness appInfo;
+  private final AppView<AppInfoWithLiveness> appView;
+  private final SubtypingInfo subtypingInfo;
   private ScopedDexMethodSet scope = new ScopedDexMethodSet();
 
-  public AbstractMethodRemover(AppInfoWithLiveness appInfo) {
-    this.appInfo = appInfo;
+  public AbstractMethodRemover(AppView<AppInfoWithLiveness> appView, SubtypingInfo subtypingInfo) {
+    this.appView = appView;
+    this.subtypingInfo = subtypingInfo;
   }
 
   public void run() {
     assert scope.getParent() == null;
-    processClass(appInfo.dexItemFactory().objectType);
+    processClass(appView.dexItemFactory().objectType);
   }
 
   private void processClass(DexType type) {
-    DexClass holder = appInfo.definitionFor(type);
+    DexClass holder = appView.definitionFor(type);
     scope = scope.newNestedScope();
     if (holder != null && holder.isProgramClass()) {
       DexEncodedMethod[] newVirtualMethods = processMethods(holder.virtualMethods());
@@ -43,7 +47,8 @@
         holder.setVirtualMethods(newVirtualMethods);
       }
     }
-    appInfo.forAllImmediateExtendsSubtypes(type, this::processClass);
+    // TODO(b/154881041): Does this need the full subtype hierarchy of referenced types!?
+    subtypingInfo.forAllImmediateExtendsSubtypes(type, this::processClass);
     scope = scope.getParent();
   }
 
@@ -57,7 +62,7 @@
       DexEncodedMethod method = virtualMethods.get(i);
       if (scope.addMethodIfMoreVisible(method) != AddMethodIfMoreVisibleResult.NOT_ADDED
           || !method.accessFlags.isAbstract()
-          || appInfo.isPinned(method.method)) {
+          || appView.appInfo().isPinned(method.method)) {
         if (methods != null) {
           methods.add(method);
         }
diff --git a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
index c252c04..0de5218 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -36,6 +36,7 @@
 import com.android.tools.r8.graph.ObjectAllocationInfoCollectionImpl;
 import com.android.tools.r8.graph.PresortedComparable;
 import com.android.tools.r8.graph.ResolutionResult.SingleResolutionResult;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
 import com.android.tools.r8.ir.code.Invoke.Type;
 import com.android.tools.r8.ir.desugar.DesugaredLibraryAPIConverter;
@@ -677,46 +678,6 @@
     return result;
   }
 
-  // TODO(b/139464956): Reimplement using only reachable types.
-  public DexProgramClass getSingleDirectSubtype(DexProgramClass clazz) {
-    DexType subtype = super.getSingleSubtype_(clazz.type);
-    return subtype == null ? null : asProgramClassOrNull(definitionFor(subtype));
-  }
-
-  /**
-   * Apply the given function to all classes that directly extend this class.
-   *
-   * <p>If this class is an interface, then this method will visit all sub-interfaces. This deviates
-   * from the dex-file encoding, where subinterfaces "implement" their super interfaces. However, it
-   * is consistent with the source language.
-   */
-  // TODO(b/139464956): Reimplement using only reachable types.
-  public void forAllImmediateExtendsSubtypes(DexType type, Consumer<DexType> f) {
-    allImmediateExtendsSubtypes(type).forEach(f);
-  }
-
-  // TODO(b/139464956): Reimplement using only reachable types.
-  public Iterable<DexType> allImmediateExtendsSubtypes(DexType type) {
-    return super.allImmediateExtendsSubtypes_(type);
-  }
-
-  /**
-   * Apply the given function to all classes that directly implement this interface.
-   *
-   * <p>The implementation does not consider how the hierarchy is encoded in the dex file, where
-   * interfaces "implement" their super interfaces. Instead it takes the view of the source
-   * language, where interfaces "extend" their superinterface.
-   */
-  // TODO(b/139464956): Reimplement using only reachable types.
-  public void forAllImmediateImplementsSubtypes(DexType type, Consumer<DexType> f) {
-    allImmediateImplementsSubtypes(type).forEach(f);
-  }
-
-  // TODO(b/139464956): Reimplement using only reachable types.
-  public Iterable<DexType> allImmediateImplementsSubtypes(DexType type) {
-    return super.allImmediateImplementsSubtypes_(type);
-  }
-
   /**
    * Const-classes is a conservative set of types that may be lock-candidates and cannot be merged.
    * When using synchronized blocks, we cannot ensure that const-class locks will not flow in. This
@@ -1207,6 +1168,11 @@
       DexClass refinedLowerBoundClass = definitionFor(receiverLowerBoundType.getClassType());
       if (refinedLowerBoundClass != null) {
         refinedLowerBound = refinedLowerBoundClass.asProgramClass();
+        // TODO(b/154822960): Check if the lower bound is a subtype of the upper bound.
+        if (refinedLowerBound != null && !isSubtype(refinedLowerBound.type, refinedReceiverType)) {
+          // We cannot trust the lower bound, so null it out.
+          refinedLowerBound = null;
+        }
       }
     }
     LookupResultSuccess lookupResult =
@@ -1386,6 +1352,10 @@
     }
   }
 
+  public SubtypingInfo computeSubtypingInfo() {
+    return new SubtypingInfo(app().asDirect().allClasses(), this);
+  }
+
   public boolean mayHaveFinalizeMethodDirectlyOrIndirectly(ClassTypeElement type) {
     // Special case for java.lang.Object.
     if (type.getClassType() == dexItemFactory().objectType) {
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 1319195..4fb2fe2 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -65,6 +65,7 @@
 import com.android.tools.r8.graph.ResolutionResult;
 import com.android.tools.r8.graph.ResolutionResult.FailedResolutionResult;
 import com.android.tools.r8.graph.ResolutionResult.SingleResolutionResult;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.graph.UseRegistry.MethodHandleUse;
 import com.android.tools.r8.graph.analysis.DesugaredLibraryConversionWrapperAnalysis;
 import com.android.tools.r8.graph.analysis.EnqueuerAnalysis;
@@ -178,6 +179,7 @@
   // Don't hold a direct pointer to app info (use appView).
   private AppInfoWithSubtyping appInfo;
   private final AppView<AppInfoWithSubtyping> appView;
+  private final SubtypingInfo subtypingInfo;
   private final InternalOptions options;
   private RootSet rootSet;
   private ProguardClassFilter dontWarnPatterns;
@@ -349,6 +351,8 @@
     InternalOptions options = appView.options();
     this.appInfo = appView.appInfo();
     this.appView = appView.withSubtyping();
+    this.subtypingInfo =
+        new SubtypingInfo(appView.appInfo().app().asDirect().allClasses(), appView);
     this.forceProguardCompatibility = options.forceProguardCompatibility;
     this.graphReporter = new GraphReporter(appView, keptGraphConsumer);
     this.mode = mode;
@@ -3127,6 +3131,7 @@
           IfRuleEvaluator ifRuleEvaluator =
               new IfRuleEvaluator(
                   appView,
+                  subtypingInfo,
                   this,
                   executorService,
                   activeIfRules,
@@ -3539,7 +3544,8 @@
       // This is using appView.definitionFor() to avoid that we report reflectively accessed types
       // as missing.
       DexProgramClass clazz =
-          asProgramClassOrNull(appView.definitionFor(identifierItem.asDexType()));
+          asProgramClassOrNull(
+              appInfo().definitionForWithoutExistenceAssert(identifierItem.asDexType()));
       if (clazz == null) {
         return;
       }
diff --git a/src/main/java/com/android/tools/r8/shaking/IfRuleEvaluator.java b/src/main/java/com/android/tools/r8/shaking/IfRuleEvaluator.java
index fe81bb7..225aff0 100644
--- a/src/main/java/com/android/tools/r8/shaking/IfRuleEvaluator.java
+++ b/src/main/java/com/android/tools/r8/shaking/IfRuleEvaluator.java
@@ -15,6 +15,7 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.shaking.RootSetBuilder.ConsequentRootSet;
 import com.android.tools.r8.utils.InternalOptions.TestingOptions.ProguardIfRuleEvaluationData;
 import com.android.tools.r8.utils.ThreadUtils;
@@ -36,6 +37,7 @@
 public class IfRuleEvaluator {
 
   private final AppView<? extends AppInfoWithSubtyping> appView;
+  private final SubtypingInfo subtypingInfo;
   private final Enqueuer enqueuer;
   private final ExecutorService executorService;
   private final List<Future<?>> futures = new ArrayList<>();
@@ -44,11 +46,13 @@
 
   IfRuleEvaluator(
       AppView<? extends AppInfoWithSubtyping> appView,
+      SubtypingInfo subtypingInfo,
       Enqueuer enqueuer,
       ExecutorService executorService,
       Map<Wrapper<ProguardIfRule>, Set<ProguardIfRule>> ifRules,
       ConsequentRootSetBuilder rootSetBuilder) {
     this.appView = appView;
+    this.subtypingInfo = subtypingInfo;
     this.enqueuer = enqueuer;
     this.executorService = executorService;
     this.ifRules = ifRules;
@@ -71,7 +75,8 @@
           // -keep rule may vary (due to back references). So, we need to try all pairs of -if
           // rule and live types.
           for (DexProgramClass clazz :
-              ifRule.relevantCandidatesForRule(appView, appView.appInfo().classes())) {
+              ifRule.relevantCandidatesForRule(
+                  appView, subtypingInfo, appView.appInfo().classes())) {
             if (!isEffectivelyLive(clazz)) {
               continue;
             }
diff --git a/src/main/java/com/android/tools/r8/shaking/MainDexListBuilder.java b/src/main/java/com/android/tools/r8/shaking/MainDexListBuilder.java
index b92f82e..b46840b 100644
--- a/src/main/java/com/android/tools/r8/shaking/MainDexListBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/MainDexListBuilder.java
@@ -121,7 +121,8 @@
   }
 
   private boolean isEnum(DexType valueType) {
-    return appInfo.isSubtype(valueType, appInfo.dexItemFactory().enumType);
+    return valueType.isClassType()
+        && appInfo.isSubtype(valueType, appInfo.dexItemFactory().enumType);
   }
 
   private boolean isAnnotation(DexType valueType) {
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardConfigurationRule.java b/src/main/java/com/android/tools/r8/shaking/ProguardConfigurationRule.java
index d59c63e..edb901b 100644
--- a/src/main/java/com/android/tools/r8/shaking/ProguardConfigurationRule.java
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardConfigurationRule.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.position.Position;
 import com.android.tools.r8.utils.StringUtils;
@@ -82,7 +83,9 @@
   }
 
   Iterable<DexProgramClass> relevantCandidatesForRule(
-      AppView<? extends AppInfoWithSubtyping> appView, Iterable<DexProgramClass> defaultValue) {
+      AppView<? extends AppInfoWithSubtyping> appView,
+      SubtypingInfo subtypingInfo,
+      Iterable<DexProgramClass> defaultValue) {
     if (hasInheritanceClassName() && getInheritanceClassName().hasSpecificType()) {
       DexType type = getInheritanceClassName().getSpecificType();
       if (appView.verticallyMergedClasses() != null
@@ -92,9 +95,9 @@
         assert clazz != null && clazz.isProgramClass();
         return Iterables.concat(
             ImmutableList.of(clazz.asProgramClass()),
-            DexProgramClass.asProgramClasses(appView.appInfo().subtypes(type), appView));
+            DexProgramClass.asProgramClasses(subtypingInfo.subtypes(type), appView));
       } else {
-        return DexProgramClass.asProgramClasses(appView.appInfo().subtypes(type), appView);
+        return DexProgramClass.asProgramClasses(subtypingInfo.subtypes(type), appView);
       }
     }
     return defaultValue;
diff --git a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
index d8c8b07..2065def 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
@@ -30,6 +30,7 @@
 import com.android.tools.r8.graph.DirectMappedDexApplication;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.graph.ResolutionResult.SingleResolutionResult;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.ir.analysis.proto.GeneratedMessageLiteBuilderShrinker;
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.shaking.AnnotationMatchResult.AnnotationsIgnoredMatchResult;
@@ -77,6 +78,7 @@
 public class RootSetBuilder {
 
   private final AppView<? extends AppInfoWithSubtyping> appView;
+  private final SubtypingInfo subtypingInfo;
   private final DirectMappedDexApplication application;
   private final Iterable<? extends ProguardConfigurationRule> rules;
   private final Map<DexReference, Set<ProguardKeepRuleBase>> noShrinking = new IdentityHashMap<>();
@@ -117,15 +119,11 @@
       Iterable<? extends ProguardConfigurationRule> rules) {
     this.appView = appView;
     this.application = application.asDirect();
+    this.subtypingInfo = new SubtypingInfo(this.application.allClasses(), this.application);
     this.rules = rules;
     this.options = appView.options();
   }
 
-  public RootSetBuilder(
-      AppView<? extends AppInfoWithSubtyping> appView, Collection<ProguardIfRule> ifRules) {
-    this(appView, appView.appInfo().app(), ifRules);
-  }
-
   public RootSetBuilder(AppView<? extends AppInfoWithSubtyping> appView) {
     this(appView, appView.appInfo().app(), null);
   }
@@ -182,7 +180,7 @@
           if (!allRulesSatisfied(memberKeepRules, clazz)) {
             break;
           }
-          // fallthrough;
+          // fall through;
         case KEEP:
           markClass(clazz, rule, ifRule);
           preconditionSupplier = new HashMap<>();
@@ -275,7 +273,7 @@
         executorService.submit(
             () -> {
               for (DexProgramClass clazz :
-                  rule.relevantCandidatesForRule(appView, application.classes())) {
+                  rule.relevantCandidatesForRule(appView, subtypingInfo, application.classes())) {
                 process(clazz, rule, ifRule);
               }
               if (rule.applyToNonProgramClasses()) {
@@ -306,12 +304,13 @@
       application.timing.end();
     }
     if (!noSideEffects.isEmpty() || !assumedValues.isEmpty()) {
-      BottomUpClassHierarchyTraversal.forAllClasses(appView)
+      BottomUpClassHierarchyTraversal.forAllClasses(appView, subtypingInfo)
           .visit(appView.appInfo().classes(), this::propagateAssumeRules);
     }
     if (appView.options().protoShrinking().enableGeneratedMessageLiteBuilderShrinking) {
       GeneratedMessageLiteBuilderShrinker.addInliningHeuristicsForBuilderInlining(
           appView,
+          subtypingInfo,
           alwaysClassInline,
           neverMerge,
           alwaysInline,
@@ -349,7 +348,7 @@
   }
 
   private void propagateAssumeRules(DexClass clazz) {
-    Set<DexType> subTypes = appView.appInfo().allImmediateSubtypes(clazz.type);
+    Set<DexType> subTypes = subtypingInfo.allImmediateSubtypes(clazz.type);
     if (subTypes.isEmpty()) {
       return;
     }
@@ -615,7 +614,7 @@
     Set<DexType> visited = new HashSet<>();
     Deque<DexType> worklist = new ArrayDeque<>();
     // Intentionally skip the current `clazz`, assuming it's covered by markMatchingVisibleMethods.
-    worklist.addAll(appInfoWithSubtyping.allImmediateSubtypes(clazz.type));
+    worklist.addAll(subtypingInfo.allImmediateSubtypes(clazz.type));
 
     while (!worklist.isEmpty()) {
       DexType currentType = worklist.poll();
@@ -636,7 +635,7 @@
                 DexDefinition precondition = testAndGetPrecondition(method, preconditionSupplier);
                 markMethod(method, memberKeepRules, null, rule, precondition, ifRule);
               });
-      worklist.addAll(appInfoWithSubtyping.allImmediateSubtypes(currentClazz.type));
+      worklist.addAll(subtypingInfo.allImmediateSubtypes(currentClazz.type));
     }
   }
 
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 2fb7435..95fa85d 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.shaking;
 
+import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
 import static com.android.tools.r8.ir.code.Invoke.Type.DIRECT;
 import static com.android.tools.r8.ir.code.Invoke.Type.STATIC;
 
@@ -33,6 +34,7 @@
 import com.android.tools.r8.graph.ParameterAnnotationsList;
 import com.android.tools.r8.graph.ResolutionResult;
 import com.android.tools.r8.graph.RewrittenPrototypeDescription;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
 import com.android.tools.r8.graph.UseRegistry;
 import com.android.tools.r8.graph.classmerging.VerticallyMergedClasses;
@@ -186,6 +188,7 @@
   private final DexApplication application;
   private final AppInfoWithLiveness appInfo;
   private final AppView<AppInfoWithLiveness> appView;
+  private final SubtypingInfo subtypingInfo;
   private final ExecutorService executorService;
   private final MethodPoolCollection methodPoolCollection;
   private final Timing timing;
@@ -222,8 +225,9 @@
     this.application = application;
     this.appInfo = appView.appInfo();
     this.appView = appView;
+    this.subtypingInfo = appInfo.computeSubtypingInfo();
     this.executorService = executorService;
-    this.methodPoolCollection = new MethodPoolCollection(appView);
+    this.methodPoolCollection = new MethodPoolCollection(appView, subtypingInfo);
     this.renamedMembersLense = new VerticalClassMergerGraphLense.Builder(appView.dexItemFactory());
     this.timing = timing;
     this.mainDexClasses = mainDexClasses;
@@ -239,7 +243,11 @@
 
   private void initializeMergeCandidates(Iterable<DexProgramClass> classes) {
     for (DexProgramClass sourceClass : classes) {
-      DexProgramClass targetClass = appInfo.getSingleDirectSubtype(sourceClass);
+      DexType singleSubtype = subtypingInfo.getSingleDirectSubtype(sourceClass.type);
+      if (singleSubtype == null) {
+        continue;
+      }
+      DexProgramClass targetClass = asProgramClassOrNull(appView.definitionFor(singleSubtype));
       if (targetClass == null) {
         continue;
       }
@@ -532,8 +540,8 @@
 
     public OverloadedMethodSignaturesRetriever() {
       for (DexProgramClass mergeCandidate : mergeCandidates) {
-        DexProgramClass candidate = appInfo.getSingleDirectSubtype(mergeCandidate);
-        mergeeCandidates.add(candidate.type);
+        DexType singleSubtype = subtypingInfo.getSingleDirectSubtype(mergeCandidate.type);
+        mergeeCandidates.add(singleSubtype);
       }
     }
 
@@ -775,7 +783,8 @@
       return;
     }
 
-    DexProgramClass targetClass = appInfo.getSingleDirectSubtype(clazz);
+    DexType singleSubtype = subtypingInfo.getSingleDirectSubtype(clazz.type);
+    DexProgramClass targetClass = appView.definitionFor(singleSubtype).asProgramClass();
     assert isMergeCandidate(clazz, targetClass, pinnedTypes);
     assert !mergedClasses.containsKey(targetClass.type);
 
diff --git a/src/main/java/com/android/tools/r8/utils/FlagFile.java b/src/main/java/com/android/tools/r8/utils/FlagFile.java
index 319580d..df999e0 100644
--- a/src/main/java/com/android/tools/r8/utils/FlagFile.java
+++ b/src/main/java/com/android/tools/r8/utils/FlagFile.java
@@ -4,7 +4,7 @@
 
 package com.android.tools.r8.utils;
 
-import com.android.tools.r8.BaseCommand;
+import com.android.tools.r8.Diagnostic;
 import com.android.tools.r8.origin.Origin;
 import java.io.IOException;
 import java.nio.file.Files;
@@ -12,6 +12,7 @@
 import java.nio.file.Paths;
 import java.util.ArrayList;
 import java.util.List;
+import java.util.function.Consumer;
 
 public class FlagFile {
 
@@ -29,7 +30,7 @@
     }
   }
 
-  public static String[] expandFlagFiles(String[] args, BaseCommand.Builder builder) {
+  public static String[] expandFlagFiles(String[] args, Consumer<Diagnostic> errorConsumer) {
     List<String> flags = new ArrayList<>(args.length);
     for (String arg : args) {
       if (arg.startsWith("@")) {
@@ -38,7 +39,7 @@
           flags.addAll(Files.readAllLines(flagFilePath));
         } catch (IOException e) {
           Origin origin = new FlagFileOrigin(flagFilePath);
-          builder.error(new ExceptionDiagnostic(e, origin));
+          errorConsumer.accept(new ExceptionDiagnostic(e, origin));
         }
       } else {
         flags.add(arg);
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index b58e9d6..3e82b0d 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -1131,6 +1131,7 @@
         System.getProperty("com.android.tools.r8.trackDesugaredAPIConversions") != null;
     public boolean forceLibBackportsInL8CfToCf = false;
     public boolean enumUnboxingRewriteJavaCGeneratedMethod = false;
+    public boolean assertConsistentRenamingOfSignature = false;
 
     // TODO(b/144781417): This is disabled by default as some test apps appear to have such classes.
     public boolean allowNonAbstractClassesWithAbstractMethods = true;
diff --git a/src/test/java/com/android/tools/r8/KotlinCompilerTool.java b/src/test/java/com/android/tools/r8/KotlinCompilerTool.java
index 42cf72a..ff795bc 100644
--- a/src/test/java/com/android/tools/r8/KotlinCompilerTool.java
+++ b/src/test/java/com/android/tools/r8/KotlinCompilerTool.java
@@ -51,6 +51,7 @@
   private final KotlinTargetVersion targetVersion;
   private final List<Path> sources = new ArrayList<>();
   private final List<Path> classpath = new ArrayList<>();
+  private boolean useJvmAssertions;
   private Path output = null;
 
   private KotlinCompilerTool(
@@ -126,6 +127,11 @@
     return this;
   }
 
+  public KotlinCompilerTool setUseJvmAssertions(boolean useJvmAssertions) {
+    this.useJvmAssertions = useJvmAssertions;
+    return this;
+  }
+
   private Path getOrCreateOutputPath() throws IOException {
     return output != null ? output : state.getNewTempFolder().resolve("out.jar");
   }
@@ -150,6 +156,9 @@
     cmdline.add("-cp");
     cmdline.add(compiler.getPath().toString());
     cmdline.add(ToolHelper.K2JVMCompiler);
+    if (useJvmAssertions) {
+      cmdline.add("-Xassertions=jvm");
+    }
     cmdline.add("-jdk-home");
     cmdline.add(jdk.getJavaHome().toString());
     cmdline.add("-jvm-target");
diff --git a/src/test/java/com/android/tools/r8/TestBase.java b/src/test/java/com/android/tools/r8/TestBase.java
index 743a898..f172bb12f 100644
--- a/src/test/java/com/android/tools/r8/TestBase.java
+++ b/src/test/java/com/android/tools/r8/TestBase.java
@@ -1449,6 +1449,27 @@
     return buildOnDexRuntime(parameters, Arrays.asList(paths));
   }
 
+  public Path buildOnDexRuntime(TestParameters parameters, Class<?>... classes)
+      throws IOException, CompilationFailedException {
+    if (parameters.isDexRuntime()) {
+      return testForD8()
+          .addProgramClasses(classes)
+          .setMinApi(parameters.getApiLevel())
+          .compile()
+          .writeToZip();
+    }
+    Path path = temp.newFolder().toPath().resolve("classes.jar");
+    ArchiveConsumer consumer = new ArchiveConsumer(path);
+    for (Class clazz : classes) {
+      consumer.accept(
+          ByteDataView.of(ToolHelper.getClassAsBytes(clazz)),
+          DescriptorUtils.javaTypeToDescriptor(clazz.getTypeName()),
+          null);
+    }
+    consumer.finished(null);
+    return path;
+  }
+
   public static String binaryName(Class<?> clazz) {
     return DescriptorUtils.getBinaryNameFromJavaType(typeName(clazz));
   }
diff --git a/src/test/java/com/android/tools/r8/cf/GetClassLdcClassTest.java b/src/test/java/com/android/tools/r8/cf/GetClassLdcClassTest.java
index a083cdd..2c7d700 100644
--- a/src/test/java/com/android/tools/r8/cf/GetClassLdcClassTest.java
+++ b/src/test/java/com/android/tools/r8/cf/GetClassLdcClassTest.java
@@ -7,6 +7,8 @@
 import static org.junit.Assert.assertNotEquals;
 import static org.junit.Assert.assertTrue;
 
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.utils.StringUtils;
@@ -62,7 +64,11 @@
         .addProgramClassFileData(getDowngradedClass(TestClass.class))
         .setMinApi(parameters.getApiLevel())
         .addKeepMainRule(TestClass.class)
-        .addKeepClassAndMembersRules(Runner.class)
+        // We cannot keep class Runner, as that prohibits getClass optimization.
+        // Instead disable minification and inlining of the Runner class and method.
+        .noMinification()
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
         .run(parameters.getRuntime(), TestClass.class)
         .assertSuccessWithOutput(EXPECTED)
         .inspect(
@@ -82,7 +88,11 @@
         .addProgramClasses(TestClass.class)
         .setMinApi(parameters.getApiLevel())
         .addKeepMainRule(TestClass.class)
-        .addKeepClassAndMembersRules(Runner.class)
+        // We cannot keep class Runner, as that prohibits getClass optimization.
+        // Instead disable minification and inlining of the Runner class and method.
+        .noMinification()
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
         .run(parameters.getRuntime(), TestClass.class)
         .assertSuccessWithOutput(EXPECTED)
         .inspect(
@@ -117,8 +127,10 @@
     return transformer(clazz).setVersion(version).transform();
   }
 
+  @NeverClassInline
   static class Runner {
 
+    @NeverInline
     public void run() {
       System.out.println(getClass().getName());
     }
diff --git a/src/test/java/com/android/tools/r8/cf/MissingClassJoinsToObjectTest.java b/src/test/java/com/android/tools/r8/cf/MissingClassJoinsToObjectTest.java
new file mode 100644
index 0000000..81f1d09
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/cf/MissingClassJoinsToObjectTest.java
@@ -0,0 +1,87 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.cf;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.R8TestRunResult;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.utils.StringUtils;
+import java.nio.file.Path;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class MissingClassJoinsToObjectTest extends TestBase {
+
+  static final String EXPECTED = StringUtils.lines("A::foo");
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimes().withAllApiLevels().build();
+  }
+
+  public MissingClassJoinsToObjectTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  private List<Path> getRuntimeClasspath() throws Exception {
+    return buildOnDexRuntime(parameters, ToolHelper.getClassFileForTestClass(B.class));
+  }
+
+  @Test
+  public void testReference() throws Exception {
+    testForRuntime(parameters)
+        .addProgramClasses(TestClass.class, A.class, B.class)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    R8TestRunResult result =
+        testForR8(parameters.getBackend())
+            .enableInliningAnnotations()
+            .addProgramClasses(TestClass.class, A.class)
+            .addKeepMainRule(TestClass.class)
+            .setMinApi(parameters.getApiLevel())
+            .compile()
+            .addRunClasspathFiles(getRuntimeClasspath())
+            .run(parameters.getRuntime(), TestClass.class);
+    if (parameters.isCfRuntime()) {
+      // TODO(b/154792347): The analysis of types in the presence of undefined is incomplete.
+      result.assertFailureWithErrorThatThrows(VerifyError.class);
+    } else {
+      result.assertSuccessWithOutput(EXPECTED);
+    }
+  }
+
+  static class A {
+    @NeverInline
+    public void foo() {
+      System.out.println("A::foo");
+    }
+  }
+
+  // Missing at compile time.
+  static class B extends A {
+    // Intentionally empty.
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      // Due to the missing class B, the join is assigned Object.
+      A join = args.length == 0 ? new A() : new B();
+      // The call to Object::foo fails.
+      join.foo();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/desugar/backports/AbstractBackportTest.java b/src/test/java/com/android/tools/r8/desugar/backports/AbstractBackportTest.java
index 523a018..646dbf9 100644
--- a/src/test/java/com/android/tools/r8/desugar/backports/AbstractBackportTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/backports/AbstractBackportTest.java
@@ -28,7 +28,7 @@
 import org.junit.Test;
 
 abstract class AbstractBackportTest extends TestBase {
-  private final TestParameters parameters;
+  protected final TestParameters parameters;
   private final Class<?> targetClass;
   private final Class<?> testClass;
   private final Path testJar;
diff --git a/src/test/java/com/android/tools/r8/desugar/backports/ListBackportJava9Test.java b/src/test/java/com/android/tools/r8/desugar/backports/ListBackportJava9Test.java
index 03843cc0..0d55065 100644
--- a/src/test/java/com/android/tools/r8/desugar/backports/ListBackportJava9Test.java
+++ b/src/test/java/com/android/tools/r8/desugar/backports/ListBackportJava9Test.java
@@ -5,13 +5,16 @@
 package com.android.tools.r8.desugar.backports;
 
 import static com.android.tools.r8.utils.FileUtils.JAR_EXTENSION;
+import static org.hamcrest.CoreMatchers.containsString;
 
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestRuntime.CfVm;
 import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.utils.AndroidApiLevel;
 import java.nio.file.Path;
 import java.nio.file.Paths;
 import java.util.List;
+import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
 import org.junit.runners.Parameterized.Parameters;
@@ -29,9 +32,10 @@
 
   private static final Path TEST_JAR =
       Paths.get(ToolHelper.EXAMPLES_JAVA9_BUILD_DIR).resolve("backport" + JAR_EXTENSION);
+  private static final String TEST_CLASS = "backport.ListBackportJava9Main";
 
   public ListBackportJava9Test(TestParameters parameters) {
-    super(parameters, List.class, TEST_JAR, "backport.ListBackportJava9Main");
+    super(parameters, List.class, TEST_JAR, TEST_CLASS);
     // Note: None of the methods in this test exist in the latest android.jar. If/when they ship in
     // an actual API level, migrate these tests to ListBackportTest.
 
@@ -41,4 +45,20 @@
     ignoreInvokes("set");
     ignoreInvokes("size");
   }
+
+  @Test
+  public void desugaringApiLevelR() throws Exception {
+    // TODO(154759404): This test should start to fail when testing on an Android R VM.
+    if (parameters.getRuntime().isDex()
+        && parameters.getApiLevel().isGreaterThanOrEqualTo(AndroidApiLevel.Q)) {
+      testForD8()
+          .setMinApi(AndroidApiLevel.R)
+          .addProgramClasses(MiniAssert.class, IgnoreInvokes.class)
+          .addProgramFiles(TEST_JAR)
+          .setIncludeClassesChecksum(true)
+          .compile()
+          .run(parameters.getRuntime(), TEST_CLASS)
+          .assertFailureWithErrorThatMatches(containsString("java.lang.NoSuchMethodError"));
+    }
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/desugar/backports/MapBackportJava9Test.java b/src/test/java/com/android/tools/r8/desugar/backports/MapBackportJava9Test.java
index fb39b49..27cb824 100644
--- a/src/test/java/com/android/tools/r8/desugar/backports/MapBackportJava9Test.java
+++ b/src/test/java/com/android/tools/r8/desugar/backports/MapBackportJava9Test.java
@@ -4,18 +4,21 @@
 
 package com.android.tools.r8.desugar.backports;
 
+import static com.android.tools.r8.utils.FileUtils.JAR_EXTENSION;
+import static org.hamcrest.CoreMatchers.containsString;
+
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestRuntime.CfVm;
 import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.utils.AndroidApiLevel;
 import java.nio.file.Path;
 import java.nio.file.Paths;
 import java.util.Map;
+import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
 import org.junit.runners.Parameterized.Parameters;
 
-import static com.android.tools.r8.utils.FileUtils.JAR_EXTENSION;
-
 @RunWith(Parameterized.class)
 public class MapBackportJava9Test extends AbstractBackportTest {
   @Parameters(name = "{0}")
@@ -29,9 +32,10 @@
 
   private static final Path TEST_JAR =
       Paths.get(ToolHelper.EXAMPLES_JAVA9_BUILD_DIR).resolve("backport" + JAR_EXTENSION);
+  private static final String TEST_CLASS = "backport.MapBackportJava9Main";
 
   public MapBackportJava9Test(TestParameters parameters) {
-    super(parameters, Map.class, TEST_JAR, "backport.MapBackportJava9Main");
+    super(parameters, Map.class, TEST_JAR, TEST_CLASS);
     // Note: None of the methods in this test exist in the latest android.jar. If/when they ship in
     // an actual API level, migrate these tests to MapBackportTest.
 
@@ -41,4 +45,20 @@
     ignoreInvokes("put");
     ignoreInvokes("size");
   }
+
+  @Test
+  public void desugaringApiLevelR() throws Exception {
+    // TODO(154759404): This test should start to fail when testing on an Android R VM.
+    if (parameters.getRuntime().isDex()
+        && parameters.getApiLevel().isGreaterThanOrEqualTo(AndroidApiLevel.Q)) {
+      testForD8()
+          .setMinApi(AndroidApiLevel.R)
+          .addProgramClasses(MiniAssert.class, IgnoreInvokes.class)
+          .addProgramFiles(TEST_JAR)
+          .setIncludeClassesChecksum(true)
+          .compile()
+          .run(parameters.getRuntime(), TEST_CLASS)
+          .assertFailureWithErrorThatMatches(containsString("java.lang.NoSuchMethodError"));
+    }
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/desugar/backports/ObjectsBackportJava9Test.java b/src/test/java/com/android/tools/r8/desugar/backports/ObjectsBackportJava9Test.java
index ef8b990..09aef1e 100644
--- a/src/test/java/com/android/tools/r8/desugar/backports/ObjectsBackportJava9Test.java
+++ b/src/test/java/com/android/tools/r8/desugar/backports/ObjectsBackportJava9Test.java
@@ -4,17 +4,20 @@
 
 package com.android.tools.r8.desugar.backports;
 
+import static com.android.tools.r8.utils.FileUtils.JAR_EXTENSION;
+import static org.hamcrest.CoreMatchers.containsString;
+
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestRuntime.CfVm;
 import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.utils.AndroidApiLevel;
 import java.nio.file.Path;
 import java.nio.file.Paths;
+import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
 import org.junit.runners.Parameterized.Parameters;
 
-import static com.android.tools.r8.utils.FileUtils.JAR_EXTENSION;
-
 @RunWith(Parameterized.class)
 public final class ObjectsBackportJava9Test extends AbstractBackportTest {
   @Parameters(name = "{0}")
@@ -28,10 +31,27 @@
 
   private static final Path TEST_JAR =
       Paths.get(ToolHelper.EXAMPLES_JAVA9_BUILD_DIR).resolve("backport" + JAR_EXTENSION);
+  private static final String TEST_CLASS = "backport.ObjectsBackportJava9Main";
 
   public ObjectsBackportJava9Test(TestParameters parameters) {
-    super(parameters, Short.class, TEST_JAR, "backport.ObjectsBackportJava9Main");
+    super(parameters, Short.class, TEST_JAR, TEST_CLASS);
     // Note: None of the methods in this test exist in the latest android.jar. If/when they ship in
     // an actual API level, migrate these tests to ObjectsBackportTest.
   }
+
+  @Test
+  public void desugaringApiLevelR() throws Exception {
+    // TODO(154759404): This test should start to fail when testing on an Android R VM.
+    if (parameters.getRuntime().isDex()
+        && parameters.getApiLevel().isGreaterThanOrEqualTo(AndroidApiLevel.Q)) {
+      testForD8()
+          .setMinApi(AndroidApiLevel.R)
+          .addProgramClasses(MiniAssert.class, IgnoreInvokes.class)
+          .addProgramFiles(TEST_JAR)
+          .setIncludeClassesChecksum(true)
+          .compile()
+          .run(parameters.getRuntime(), TEST_CLASS)
+          .assertFailureWithErrorThatMatches(containsString("java.lang.NoSuchMethodError"));
+    }
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/desugar/backports/SetBackportJava9Test.java b/src/test/java/com/android/tools/r8/desugar/backports/SetBackportJava9Test.java
index 6947ff2..408b203 100644
--- a/src/test/java/com/android/tools/r8/desugar/backports/SetBackportJava9Test.java
+++ b/src/test/java/com/android/tools/r8/desugar/backports/SetBackportJava9Test.java
@@ -4,18 +4,21 @@
 
 package com.android.tools.r8.desugar.backports;
 
+import static com.android.tools.r8.utils.FileUtils.JAR_EXTENSION;
+import static org.hamcrest.CoreMatchers.containsString;
+
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestRuntime.CfVm;
 import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.utils.AndroidApiLevel;
 import java.nio.file.Path;
 import java.nio.file.Paths;
 import java.util.Set;
+import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
 import org.junit.runners.Parameterized.Parameters;
 
-import static com.android.tools.r8.utils.FileUtils.JAR_EXTENSION;
-
 @RunWith(Parameterized.class)
 public class SetBackportJava9Test extends AbstractBackportTest {
   @Parameters(name = "{0}")
@@ -29,9 +32,10 @@
 
   private static final Path TEST_JAR =
       Paths.get(ToolHelper.EXAMPLES_JAVA9_BUILD_DIR).resolve("backport" + JAR_EXTENSION);
+  private static final String TEST_CLASS = "backport.SetBackportJava9Main";
 
   public SetBackportJava9Test(TestParameters parameters) {
-    super(parameters, Set.class, TEST_JAR, "backport.SetBackportJava9Main");
+    super(parameters, Set.class, TEST_JAR, TEST_CLASS);
     // Note: None of the methods in this test exist in the latest android.jar. If/when they ship in
     // an actual API level, migrate these tests to SetBackportTest.
 
@@ -40,4 +44,20 @@
     ignoreInvokes("contains");
     ignoreInvokes("size");
   }
+
+  @Test
+  public void desugaringApiLevelR() throws Exception {
+    // TODO(154759404): This test should start to fail when testing on an Android R VM.
+    if (parameters.getRuntime().isDex()
+        && parameters.getApiLevel().isGreaterThanOrEqualTo(AndroidApiLevel.Q)) {
+      testForD8()
+          .setMinApi(AndroidApiLevel.R)
+          .addProgramClasses(MiniAssert.class, IgnoreInvokes.class)
+          .addProgramFiles(TEST_JAR)
+          .setIncludeClassesChecksum(true)
+          .compile()
+          .run(parameters.getRuntime(), TEST_CLASS)
+          .assertFailureWithErrorThatMatches(containsString("java.lang.NoSuchMethodError"));
+    }
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/desugar/backports/TestBackportedNotPresentInAndroidJar.java b/src/test/java/com/android/tools/r8/desugar/backports/TestBackportedNotPresentInAndroidJar.java
index e6fdf99..8096c47 100644
--- a/src/test/java/com/android/tools/r8/desugar/backports/TestBackportedNotPresentInAndroidJar.java
+++ b/src/test/java/com/android/tools/r8/desugar/backports/TestBackportedNotPresentInAndroidJar.java
@@ -35,9 +35,6 @@
         System.out.println("Skipping check for " + apiLevel);
         continue;
       }
-      if (apiLevel == AndroidApiLevel.R) {
-        continue;
-      }
       // Check that the backported methods for each API level are are not present in the
       // android.jar for that level.
       CodeInspector inspector = new CodeInspector(ToolHelper.getAndroidJar(apiLevel));
diff --git a/src/test/java/com/android/tools/r8/enumunboxing/AnnotationEnumUnboxingTest.java b/src/test/java/com/android/tools/r8/enumunboxing/AnnotationEnumUnboxingTest.java
new file mode 100644
index 0000000..7cc0930
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/enumunboxing/AnnotationEnumUnboxingTest.java
@@ -0,0 +1,129 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.enumunboxing;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestParameters;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.util.List;
+import org.junit.Assume;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class AnnotationEnumUnboxingTest extends EnumUnboxingTestBase {
+
+  private final TestParameters parameters;
+  private final boolean enumValueOptimization;
+  private final KeepRule enumKeepRules;
+
+  @Parameters(name = "{0} valueOpt: {1} keep: {2}")
+  public static List<Object[]> data() {
+    return enumUnboxingTestParameters();
+  }
+
+  public AnnotationEnumUnboxingTest(
+      TestParameters parameters, boolean enumValueOptimization, KeepRule enumKeepRules) {
+    this.parameters = parameters;
+    this.enumValueOptimization = enumValueOptimization;
+    this.enumKeepRules = enumKeepRules;
+  }
+
+  @Test
+  public void testEnumUnboxing() throws Exception {
+    Assume.assumeFalse(
+        "The methods values and valueOf are required for reflection.",
+        enumKeepRules.toString().equals("none"));
+    testForR8(parameters.getBackend())
+        .addInnerClasses(AnnotationEnumUnboxingTest.class)
+        .addKeepMainRule(Main.class)
+        .addKeepRules(enumKeepRules.getKeepRule())
+        .addKeepRules(
+            "-keep @interface"
+                + " com.android.tools.r8.enumunboxing."
+                + "AnnotationEnumUnboxingTest$ClassAnnotationDefault"
+                + " {  }",
+            "-keepattributes *Annotation*")
+        .enableNeverClassInliningAnnotations()
+        .enableInliningAnnotations()
+        .addOptionsModification(opt -> enableEnumOptions(opt, enumValueOptimization))
+        .allowDiagnosticInfoMessages()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspectDiagnosticMessages(
+            m -> {
+              assertEnumIsBoxed(MyEnumDefault.class, MyEnumDefault.class.getSimpleName(), m);
+              assertEnumIsBoxed(MyEnum.class, MyEnum.class.getSimpleName(), m);
+              assertEnumIsBoxed(
+                  MyEnumArrayDefault.class, MyEnumArrayDefault.class.getSimpleName(), m);
+              assertEnumIsBoxed(MyEnumArray.class, MyEnumArray.class.getSimpleName(), m);
+            })
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("print", "1", "1", "1", "1", "1", "0", "0", "0");
+  }
+
+  @Retention(RetentionPolicy.RUNTIME)
+  @interface ClassAnnotationDefault {
+    MyEnumDefault myEnumDefault() default MyEnumDefault.A;
+
+    MyEnum myEnum();
+
+    MyEnumArrayDefault[] myEnumArrayDefault() default {MyEnumArrayDefault.A, MyEnumArrayDefault.B};
+
+    MyEnumArray[] myEnumArray();
+  }
+
+  enum MyEnumDefault {
+    A,
+    B
+  }
+
+  enum MyEnum {
+    A,
+    B
+  }
+
+  enum MyEnumArrayDefault {
+    A,
+    B,
+    C
+  }
+
+  enum MyEnumArray {
+    A,
+    B,
+    C
+  }
+
+  @NeverClassInline
+  @ClassAnnotationDefault(
+      myEnum = MyEnum.B,
+      myEnumArray = {MyEnumArray.A, MyEnumArray.B})
+  private static class ClassDefault {
+    @NeverInline
+    void print() {
+      System.out.println("print");
+    }
+  }
+
+  static class Main {
+    public static void main(String[] args) {
+      new ClassDefault().print();
+      System.out.println(MyEnum.B.ordinal());
+      System.out.println(MyEnumDefault.B.ordinal());
+      System.out.println(MyEnumArray.B.ordinal());
+      System.out.println(MyEnumArrayDefault.B.ordinal());
+      ClassAnnotationDefault annotation =
+          (ClassAnnotationDefault) ClassDefault.class.getDeclaredAnnotations()[0];
+      System.out.println(annotation.myEnum().ordinal());
+      System.out.println(annotation.myEnumArray()[0].ordinal());
+      System.out.println(annotation.myEnumArrayDefault()[0].ordinal());
+      System.out.println(annotation.myEnumDefault().ordinal());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingReturnNullTest.java b/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingReturnNullTest.java
new file mode 100644
index 0000000..2a1be5f
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingReturnNullTest.java
@@ -0,0 +1,102 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.enumunboxing;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.utils.StringUtils;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class EnumUnboxingReturnNullTest extends EnumUnboxingTestBase {
+
+  private static final Class<?> ENUM_CLASS = MyEnum.class;
+  private static final String EXPECTED_RESULT =
+      StringUtils.lines(
+          "print1", "true", "print2", "true", "print2", "false", "0", "print3", "true");
+
+  private final TestParameters parameters;
+  private final boolean enumValueOptimization;
+  private final KeepRule enumKeepRules;
+
+  @Parameterized.Parameters(name = "{0} valueOpt: {1} keep: {2}")
+  public static List<Object[]> data() {
+    return enumUnboxingTestParameters();
+  }
+
+  public EnumUnboxingReturnNullTest(
+      TestParameters parameters, boolean enumValueOptimization, KeepRule enumKeepRules) {
+    this.parameters = parameters;
+    this.enumValueOptimization = enumValueOptimization;
+    this.enumKeepRules = enumKeepRules;
+  }
+
+  @Test
+  public void testEnumUnboxing() throws Exception {
+    Class<?> classToTest = ReturnNull.class;
+    testForR8(parameters.getBackend())
+        .addProgramClasses(classToTest, ENUM_CLASS)
+        .addKeepMainRule(classToTest)
+        .addKeepRules(enumKeepRules.getKeepRule())
+        .enableNeverClassInliningAnnotations()
+        .enableInliningAnnotations()
+        .addOptionsModification(opt -> enableEnumOptions(opt, enumValueOptimization))
+        .allowDiagnosticInfoMessages()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspectDiagnosticMessages(
+            m -> assertEnumIsUnboxed(ENUM_CLASS, classToTest.getSimpleName(), m))
+        .run(parameters.getRuntime(), classToTest)
+        .assertSuccessWithOutput(EXPECTED_RESULT);
+  }
+
+  @NeverClassInline
+  enum MyEnum {
+    A,
+    B,
+    C
+  }
+
+  static class ReturnNull {
+
+    public static void main(String[] args) {
+      MyEnum myEnum1 = printAndReturnNull();
+      System.out.println(myEnum1 == null);
+      MyEnum myEnum2 = printAndReturnMaybeNull(true);
+      System.out.println(myEnum2 == null);
+      MyEnum myEnum3 = printAndReturnMaybeNull(false);
+      System.out.println(myEnum3 == null);
+      System.out.println(MyEnum.A.ordinal());
+      MyEnum[] myEnums = printAndReturnNullArray();
+      System.out.println(myEnums == null);
+    }
+
+    @NeverInline
+    static MyEnum printAndReturnNull() {
+      System.out.println("print1");
+      return null;
+    }
+
+    @NeverInline
+    static MyEnum printAndReturnMaybeNull(boolean bool) {
+      System.out.println("print2");
+      if (bool) {
+        return null;
+      } else {
+        return MyEnum.B;
+      }
+    }
+
+    @NeverInline
+    static MyEnum[] printAndReturnNullArray() {
+      System.out.println("print3");
+      return null;
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreLookupTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreLookupTest.java
index 20ed6dc..183a37e 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreLookupTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreLookupTest.java
@@ -23,6 +23,8 @@
 import com.android.tools.r8.graph.LookupResult;
 import com.android.tools.r8.graph.LookupResult.LookupResultSuccess;
 import com.android.tools.r8.graph.ResolutionResult;
+import com.android.tools.r8.graph.SubtypingInfo;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.Timing;
@@ -32,6 +34,7 @@
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
 import org.junit.Before;
+import org.junit.Ignore;
 import org.junit.Test;
 
 public class R8GMSCoreLookupTest extends TestBase {
@@ -39,6 +42,7 @@
   private static final String APP_DIR = "third_party/gmscore/v5/";
   private DirectMappedDexApplication program;
   private AppView<? extends AppInfoWithSubtyping> appView;
+  private SubtypingInfo subtypingInfo;
 
   @Before
   public void readGMSCore() throws Exception {
@@ -58,6 +62,7 @@
     InternalOptions options = new InternalOptions();
     appView = AppView.createForR8(new AppInfoWithSubtyping(program), options);
     appView.setAppServices(AppServices.builder(appView).build());
+    subtypingInfo = new SubtypingInfo(program.allClasses(), program);
   }
 
   private AppInfoWithSubtyping appInfo() {
@@ -71,9 +76,10 @@
 
     // Check lookup targets with include method.
     ResolutionResult resolutionResult = appInfo().resolveMethodOnClass(clazz, method.method);
+    AppInfoWithLiveness appInfo = null; // TODO(b/154881041): Remove or compute liveness.
     LookupResult lookupResult =
         resolutionResult.lookupVirtualDispatchTargets(
-            clazz, appInfo(), appInfo(), dexReference -> false);
+            clazz, appInfo(), appInfo, dexReference -> false);
     assertTrue(lookupResult.isLookupResultSuccess());
     assertTrue(lookupResult.asLookupResultSuccess().contains(method));
   }
@@ -87,14 +93,15 @@
   }
 
   private void testInterfaceLookup(DexProgramClass clazz, DexEncodedMethod method) {
+    AppInfoWithLiveness appInfo = null; // TODO(b/154881041): Remove or compute liveness.
     LookupResultSuccess lookupResult =
         appInfo()
             .resolveMethodOnInterface(clazz, method.method)
-            .lookupVirtualDispatchTargets(clazz, appInfo(), appInfo(), dexReference -> false)
+            .lookupVirtualDispatchTargets(clazz, appInfo(), appInfo, dexReference -> false)
             .asLookupResultSuccess();
     assertNotNull(lookupResult);
     assertFalse(lookupResult.hasLambdaTargets());
-    if (appInfo().subtypes(method.holder()).stream()
+    if (subtypingInfo.subtypes(method.holder()).stream()
         .allMatch(t -> appInfo().definitionFor(t).isInterface())) {
       Counter counter = new Counter();
       lookupResult.forEach(
@@ -132,6 +139,7 @@
   }
 
   @Test
+  @Ignore("b/154881041: Does this test add value? If so it needs to compute a liveness app-info")
   public void testLookup() {
     program.classesWithDeterministicOrder().forEach(this::testLookup);
   }
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
index 5a8a80e..5d2814c 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
@@ -534,7 +534,6 @@
   @Test
   public void testSelfOrderWithoutSubtypingInfo() {
     DexType type = factory.createType("Lmy/Type;");
-    appView.withSubtyping().appInfo().registerNewTypeForTesting(type, factory.objectType);
     TypeElement nonNullType = fromDexType(type, Nullability.definitelyNotNull(), appView);
     ReferenceTypeElement nullableType =
         nonNullType.asReferenceType().getOrCreateVariant(Nullability.maybeNull());
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/dynamictype/DynamicUpperBoundWithEffectivelyFinalTest.java b/src/test/java/com/android/tools/r8/ir/optimize/dynamictype/DynamicUpperBoundWithEffectivelyFinalTest.java
new file mode 100644
index 0000000..5393409
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/dynamictype/DynamicUpperBoundWithEffectivelyFinalTest.java
@@ -0,0 +1,83 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.dynamictype;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import java.io.IOException;
+import java.util.concurrent.ExecutionException;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class DynamicUpperBoundWithEffectivelyFinalTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public DynamicUpperBoundWithEffectivelyFinalTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testR8() throws ExecutionException, CompilationFailedException, IOException {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(A.class, Base.class, Final.class, Main.class)
+        .addKeepMainRule(Main.class)
+        .addKeepClassRules(Final.class)
+        .addKeepClassAndMembersRules(Base.class)
+        .setMinApi(parameters.getApiLevel())
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("Hello World!");
+  }
+
+  @NeverClassInline
+  public static class A {
+
+    @Override
+    public String toString() {
+      return "Hello World!";
+    }
+  }
+
+  public abstract static class Base {
+
+    abstract A run();
+  }
+
+  @NeverClassInline
+  public static final class Final extends Base {
+
+    @Override
+    @NeverInline
+    A run() {
+      return new A();
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      System.out.println(runFinal(new Final()));
+    }
+
+    @NeverInline
+    public static A runFinal(Final fin) {
+      return fin.run();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/fields/singleton/SingletonFieldValuePropagationEnumTest.java b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/fields/singleton/SingletonFieldValuePropagationEnumTest.java
new file mode 100644
index 0000000..1463a01
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/fields/singleton/SingletonFieldValuePropagationEnumTest.java
@@ -0,0 +1,77 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.membervaluepropagation.fields.singleton;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class SingletonFieldValuePropagationEnumTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public SingletonFieldValuePropagationEnumTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(SingletonFieldValuePropagationEnumTest.class)
+        .addKeepMainRule(TestClass.class)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(this::inspect)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("A", "B", "C");
+  }
+
+  private void inspect(CodeInspector inspector) {
+    ClassSubject charactersClassSubject = inspector.clazz(Characters.class);
+    assertThat(charactersClassSubject, isPresent());
+    // TODO(b/150368955): Field value propagation should cause Characters.value to become dead.
+    assertEquals(1, charactersClassSubject.allInstanceFields().size());
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      System.out.println((char) Characters.A.get());
+      System.out.println((char) Characters.B.get());
+      System.out.println((char) Characters.C.get());
+    }
+  }
+
+  enum Characters {
+    A(65),
+    B(66),
+    C(67);
+
+    int value;
+
+    Characters(int value) {
+      this.value = value;
+    }
+
+    int get() {
+      return value;
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/fields/singleton/SingletonFieldValuePropagationEnumWithSubclassTest.java b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/fields/singleton/SingletonFieldValuePropagationEnumWithSubclassTest.java
new file mode 100644
index 0000000..3989c55
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/fields/singleton/SingletonFieldValuePropagationEnumWithSubclassTest.java
@@ -0,0 +1,92 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.membervaluepropagation.fields.singleton;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class SingletonFieldValuePropagationEnumWithSubclassTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public SingletonFieldValuePropagationEnumWithSubclassTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(SingletonFieldValuePropagationEnumWithSubclassTest.class)
+        .addKeepMainRule(TestClass.class)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(this::inspect)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("A", "B", "C");
+  }
+
+  private void inspect(CodeInspector inspector) {
+    ClassSubject charactersClassSubject = inspector.clazz(Characters.class);
+    assertThat(charactersClassSubject, isPresent());
+    // TODO(b/150368955): Field value propagation should cause Characters.value to become dead.
+    assertEquals(1, charactersClassSubject.allInstanceFields().size());
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      System.out.println((char) Characters.A.get());
+      System.out.println((char) Characters.B.get());
+      System.out.println((char) Characters.C.get());
+    }
+  }
+
+  enum Characters {
+    A(65) {
+      @Override
+      int get() {
+        return value;
+      }
+    },
+    B(66) {
+      @Override
+      int get() {
+        return value;
+      }
+    },
+    C(67) {
+      @Override
+      int get() {
+        return value;
+      }
+    };
+
+    int value;
+
+    Characters(int value) {
+      this.value = value;
+    }
+
+    int get() {
+      throw new RuntimeException();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/fields/singleton/SingletonFieldValuePropagationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/fields/singleton/SingletonFieldValuePropagationTest.java
new file mode 100644
index 0000000..371844e
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/fields/singleton/SingletonFieldValuePropagationTest.java
@@ -0,0 +1,90 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.membervaluepropagation.fields.singleton;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class SingletonFieldValuePropagationTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public SingletonFieldValuePropagationTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(SingletonFieldValuePropagationTest.class)
+        .addKeepMainRule(TestClass.class)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(this::inspect)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("A", "B", "C");
+  }
+
+  private void inspect(CodeInspector inspector) {
+    ClassSubject charactersClassSubject = inspector.clazz(Characters.class);
+    assertThat(charactersClassSubject, isPresent());
+    // TODO(b/150368955): Field value propagation should cause Characters.value to become dead.
+    assertEquals(1, charactersClassSubject.allInstanceFields().size());
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      System.out.println((char) Characters.getA().get());
+      System.out.println((char) Characters.getB().get());
+      System.out.println((char) Characters.getC().get());
+    }
+  }
+
+  static class Characters {
+
+    static Characters INSTANCE_A = new Characters(65);
+    static Characters INSTANCE_B = new Characters(66);
+    static Characters INSTANCE_C = new Characters(67);
+
+    int value;
+
+    Characters(int value) {
+      this.value = value;
+    }
+
+    static Characters getA() {
+      return INSTANCE_A;
+    }
+
+    static Characters getB() {
+      return INSTANCE_B;
+    }
+
+    static Characters getC() {
+      return INSTANCE_C;
+    }
+
+    int get() {
+      return value;
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassBaseAndSubTest.java b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassBaseAndSubTest.java
new file mode 100644
index 0000000..b5daa52
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassBaseAndSubTest.java
@@ -0,0 +1,76 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir.optimize.reflection;
+
+import static org.junit.Assert.assertFalse;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.InstructionSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class GetClassBaseAndSubTest extends TestBase {
+
+  static final String EXPECTED =
+      StringUtils.lines("class " + Base.class.getTypeName(), "class " + Sub.class.getTypeName());
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public GetClassBaseAndSubTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testReference() throws Exception {
+    testForRuntime(parameters)
+        .addInnerClasses(GetClassBaseAndSubTest.class)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .noMinification()
+        .addInnerClasses(GetClassBaseAndSubTest.class)
+        .addKeepMainRule(TestClass.class)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED)
+        .inspect(
+            inspector ->
+                assertFalse(
+                    inspector
+                        .clazz(TestClass.class)
+                        .mainMethod()
+                        .streamInstructions()
+                        .anyMatch(InstructionSubject::isConstClass)));
+  }
+
+  static class Base {}
+
+  static class Sub extends Base {}
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      Base baseWithBase = System.currentTimeMillis() > 0 ? new Base() : new Sub();
+      // Cannot be rewritten to const-class.
+      System.out.println(baseWithBase.getClass());
+      Base baseWithSub = System.currentTimeMillis() > 0 ? new Sub() : new Base();
+      // Cannot be rewritten to const-class.
+      System.out.println(baseWithSub.getClass());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassOnKeptClassTest.java b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassOnKeptClassTest.java
new file mode 100644
index 0000000..6e0e9e3
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassOnKeptClassTest.java
@@ -0,0 +1,97 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir.optimize.reflection;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.StringUtils;
+import java.util.concurrent.Callable;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class GetClassOnKeptClassTest extends TestBase {
+
+  static final String EXPECTED =
+      StringUtils.lines(
+          "class " + KeptClass.class.getTypeName(),
+          "class " + KeptClass.class.getTypeName(),
+          "class " + UnknownClass.class.getTypeName(),
+          "class " + UnknownClass.class.getTypeName());
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimes().withAllApiLevels().build();
+  }
+
+  public GetClassOnKeptClassTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testReference() throws Exception {
+    testForRuntime(parameters)
+        .addProgramClasses(KeptClass.class, UnknownClass.class, TestClass.class)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .enableInliningAnnotations()
+        .addProgramClasses(KeptClass.class, TestClass.class)
+        .addKeepMainRule(TestClass.class)
+        .addKeepClassRules(KeptClass.class)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .addRunClasspathFiles(buildOnDexRuntime(parameters, UnknownClass.class))
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED);
+  }
+
+  static class KeptClass implements Callable<Class<?>> {
+    @NeverInline
+    static Class<?> getClassMethod(KeptClass instance) {
+      // Nullable argument. Should not be rewritten to const-class to preserve NPE.
+      return instance.getClass();
+    }
+
+    @NeverInline
+    @Override
+    public Class<?> call() {
+      // Non-null `this` pointer.
+      return getClass();
+    }
+  }
+
+  static class UnknownClass extends KeptClass {
+    // Empty subtype of KeptClass.
+  }
+
+  static class TestClass {
+
+    static KeptClass getInstance(int i) throws Exception {
+      return i == 0
+          ? new KeptClass()
+          : (KeptClass)
+              Class.forName(TestClass.class.getName().replace("TestClass", "UnknownClass"))
+                  .getDeclaredConstructor()
+                  .newInstance();
+    }
+
+    public static void main(String[] args) throws Exception {
+      for (int i = 0; i < 2; i++) {
+        KeptClass instance = getInstance(args.length + i);
+        System.out.println(instance.call());
+        System.out.println(KeptClass.getClassMethod(instance));
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassTest.java b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassTest.java
index c2fa7fb..7807a9f 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassTest.java
@@ -9,30 +9,34 @@
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assume.assumeTrue;
 
-import com.android.tools.r8.D8TestRunResult;
+import com.android.tools.r8.CompilationMode;
 import com.android.tools.r8.ForceInline;
 import com.android.tools.r8.NeverInline;
-import com.android.tools.r8.R8TestRunResult;
 import com.android.tools.r8.TestParameters;
-import com.android.tools.r8.TestParametersCollection;
-import com.android.tools.r8.TestRunResult;
 import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import com.google.common.collect.ImmutableList;
+import java.util.List;
 import java.util.concurrent.Callable;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
 
-class GetClassTestMain implements Callable<Class<?>> {
+@RunWith(Parameterized.class)
+public class GetClassTest extends ReflectionOptimizerTestBase {
+
   static class Base {}
+
   static class Sub extends Base {}
+
   static class EffectivelyFinal {}
 
   static class Reflection implements Callable<Class<?>> {
+
     @ForceInline
     @Override
     public Class<?> call() {
@@ -40,96 +44,106 @@
     }
   }
 
-  @NeverInline
-  static Class<?> getMainClass(GetClassTestMain instance) {
-    // Nullable argument. Should not be rewritten to const-class to preserve NPE.
-    return instance.getClass();
+  static class GetClassTestMain implements Callable<Class<?>> {
+
+    @NeverInline
+    static Class<?> getMainClass(GetClassTestMain instance) {
+      // Nullable argument. Should not be rewritten to const-class to preserve NPE.
+      return instance.getClass();
+    }
+
+    @NeverInline
+    @Override
+    public Class<?> call() {
+      // Non-null `this` pointer.
+      return getClass();
+    }
   }
 
-  @NeverInline
-  @Override
-  public Class<?> call() {
-    // Non-null `this` pointer.
-    return getClass();
-  }
+  static class Main {
 
-  public static void main(String[] args) {
-    {
-      Base base = new Base();
-      // Not applicable in debug mode.
-      System.out.println(base.getClass());
-      // Can be rewritten to const-class always.
-      System.out.println(new Base().getClass());
-    }
+    public static void main(String[] args) {
+      {
+        Base base = new Base();
+        // Not applicable in debug mode.
+        System.out.println(base.getClass());
+        // Can be rewritten to const-class always.
+        System.out.println(new Base().getClass());
+      }
 
-    {
-      Base sub = new Sub();
-      // Not applicable in debug mode.
-      System.out.println(sub.getClass());
-    }
+      {
+        Base sub = new Sub();
+        // Not applicable in debug mode.
+        System.out.println(sub.getClass());
+      }
 
-    {
-      Base[] subs = new Sub[1];
-      // Not applicable in debug mode.
-      System.out.println(subs.getClass());
-    }
+      {
+        Base[] subs = new Sub[1];
+        // Not applicable in debug mode.
+        System.out.println(subs.getClass());
+      }
 
-    {
-      EffectivelyFinal ef = new EffectivelyFinal();
-      // Not applicable in debug mode.
-      System.out.println(ef.getClass());
-    }
+      {
+        EffectivelyFinal ef = new EffectivelyFinal();
+        // Not applicable in debug mode.
+        System.out.println(ef.getClass());
+      }
 
-    try {
-      // To not be recognized as un-instantiated class.
-      GetClassTestMain instance = new GetClassTestMain();
-      System.out.println(instance.call());
-      System.out.println(getMainClass(instance));
-
-      System.out.println(getMainClass(null));
-      throw new AssertionError("Should preserve NPE.");
-    } catch (NullPointerException e) {
-      // Expected
-    }
-
-    {
-      Reflection r = new Reflection();
-      // Not applicable in debug mode.
-      System.out.println(r.getClass());
       try {
-        // Can be rewritten to const-class after inlining.
-        System.out.println(r.call());
-      } catch (Throwable e) {
-        throw new AssertionError("Not expected any exceptions.");
+        // To not be recognized as un-instantiated class.
+        GetClassTestMain instance = new GetClassTestMain();
+        System.out.println(instance.call());
+        System.out.println(GetClassTestMain.getMainClass(instance));
+
+        System.out.println(GetClassTestMain.getMainClass(null));
+        throw new AssertionError("Should preserve NPE.");
+      } catch (NullPointerException e) {
+        // Expected
+      }
+
+      {
+        Reflection r = new Reflection();
+        // Not applicable in debug mode.
+        System.out.println(r.getClass());
+        try {
+          // Can be rewritten to const-class after inlining.
+          System.out.println(r.call());
+        } catch (Throwable e) {
+          throw new AssertionError("Not expected any exceptions.");
+        }
       }
     }
   }
-}
 
-@RunWith(Parameterized.class)
-public class GetClassTest extends ReflectionOptimizerTestBase {
-  private static final String JAVA_OUTPUT = StringUtils.lines(
-      "class com.android.tools.r8.ir.optimize.reflection.GetClassTestMain$Base",
-      "class com.android.tools.r8.ir.optimize.reflection.GetClassTestMain$Base",
-      "class com.android.tools.r8.ir.optimize.reflection.GetClassTestMain$Sub",
-      "class [Lcom.android.tools.r8.ir.optimize.reflection.GetClassTestMain$Sub;",
-      "class com.android.tools.r8.ir.optimize.reflection.GetClassTestMain$EffectivelyFinal",
-      "class com.android.tools.r8.ir.optimize.reflection.GetClassTestMain",
-      "class com.android.tools.r8.ir.optimize.reflection.GetClassTestMain",
-      "class com.android.tools.r8.ir.optimize.reflection.GetClassTestMain$Reflection",
-      "class com.android.tools.r8.ir.optimize.reflection.GetClassTestMain$Reflection"
-  );
-  private static final Class<?> MAIN = GetClassTestMain.class;
+  private static final String JAVA_OUTPUT =
+      StringUtils.lines(
+          ListUtils.map(
+              ImmutableList.of(
+                  Base.class.getTypeName(),
+                  Base.class.getTypeName(),
+                  Sub.class.getTypeName(),
+                  "[L" + Sub.class.getTypeName() + ";",
+                  EffectivelyFinal.class.getTypeName(),
+                  GetClassTestMain.class.getTypeName(),
+                  GetClassTestMain.class.getTypeName(),
+                  Reflection.class.getTypeName(),
+                  Reflection.class.getTypeName()),
+              l -> "class " + l));
 
-  @Parameterized.Parameters(name = "{0}")
-  public static TestParametersCollection data() {
-    return getTestParameters().withAllRuntimes().withAllApiLevels().build();
+  private static final Class<?> MAIN = Main.class;
+
+  @Parameterized.Parameters(name = "{0}, mode:{1}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        getTestParameters().withAllRuntimesAndApiLevels().build(), CompilationMode.values());
   }
 
   private final TestParameters parameters;
+  private final CompilationMode mode;
 
-  public GetClassTest(TestParameters parameters) {
+  public GetClassTest(TestParameters parameters, CompilationMode mode) {
     this.parameters = parameters;
+    this.mode = mode;
   }
 
   private void configure(InternalOptions options) {
@@ -140,109 +154,75 @@
   }
 
   @Test
-  public void testJVMOutput() throws Exception {
-    assumeTrue("Only run JVM reference on CF runtimes", parameters.isCfRuntime());
+  public void testJVM() throws Exception {
+    assumeTrue(
+        "Only run JVM reference on CF runtimes",
+        parameters.isCfRuntime() && mode == CompilationMode.DEBUG);
     testForJvm()
-        .addTestClasspath()
+        .addInnerClasses(GetClassTest.class)
         .run(parameters.getRuntime(), MAIN)
         .assertSuccessWithOutput(JAVA_OUTPUT);
   }
 
   private void test(
-      TestRunResult<?> result, boolean isR8, boolean isRelease) throws Exception {
-    CodeInspector codeInspector = result.inspector();
+      CodeInspector codeInspector,
+      boolean expectCallPresent,
+      int expectedGetClassCount,
+      int expectedConstClassCount) {
     ClassSubject mainClass = codeInspector.clazz(MAIN);
     MethodSubject mainMethod = mainClass.mainMethod();
     assertThat(mainMethod, isPresent());
-    int expectedCount = isR8 ? (isRelease ? 0 : 5) : 6;
-    assertEquals(expectedCount, countGetClass(mainMethod));
-    expectedCount = isR8 ? (isRelease ? (parameters.isCfRuntime() ? 8 : 6) : 1) : 0;
-    assertEquals(expectedCount, countConstClass(mainMethod));
+    assertEquals(expectedGetClassCount, countGetClass(mainMethod));
+    assertEquals(expectedConstClassCount, countConstClass(mainMethod));
 
-    boolean expectToBeOptimized = isR8 && isRelease;
-
-    MethodSubject getMainClass = mainClass.uniqueMethodWithName("getMainClass");
+    ClassSubject getterClass = codeInspector.clazz(GetClassTestMain.class);
+    MethodSubject getMainClass = getterClass.uniqueMethodWithName("getMainClass");
     assertThat(getMainClass, isPresent());
     // Because of nullable argument, getClass() should remain.
     assertEquals(1, countGetClass(getMainClass));
     assertEquals(0, countConstClass(getMainClass));
 
-    MethodSubject call = mainClass.method("java.lang.Class", "call", ImmutableList.of());
-    if (isR8 && isRelease) {
+    MethodSubject call = getterClass.method("java.lang.Class", "call", ImmutableList.of());
+    if (!expectCallPresent) {
       assertThat(call, not(isPresent()));
     } else {
       assertThat(call, isPresent());
       // Because of local, only R8 release mode can rewrite getClass() to const-class.
-      assertEquals(expectToBeOptimized ? 0 : 1, countGetClass(call));
-      assertEquals(expectToBeOptimized ? 1 : 0, countConstClass(call));
+      assertEquals(1, countGetClass(call));
+      assertEquals(0, countConstClass(call));
     }
   }
 
   @Test
   public void testD8() throws Exception {
     assumeTrue("Only run D8 for Dex backend", parameters.isDexRuntime());
-
-    // D8 debug.
-    D8TestRunResult result =
-        testForD8()
-            .debug()
-            .addProgramClassesAndInnerClasses(MAIN)
-            .addOptionsModification(this::configure)
-            .setMinApi(parameters.getApiLevel())
-            .run(parameters.getRuntime(), MAIN)
-            .assertSuccessWithOutput(JAVA_OUTPUT);
-    test(result, false, false);
-
-    // D8 release.
-    result =
-        testForD8()
-            .release()
-            .addProgramClassesAndInnerClasses(MAIN)
-            .addOptionsModification(this::configure)
-            .setMinApi(parameters.getApiLevel())
-            .run(parameters.getRuntime(), MAIN)
-            .assertSuccessWithOutput(JAVA_OUTPUT);
-    test(result, false, true);
+    testForD8()
+        .setMode(mode)
+        .addInnerClasses(GetClassTest.class)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), MAIN)
+        .assertSuccessWithOutput(JAVA_OUTPUT)
+        .inspect(inspector -> test(inspector, true, 6, 0));
   }
 
   @Test
   public void testR8() throws Exception {
-    // R8 debug, no minification.
-    R8TestRunResult result =
-        testForR8(parameters.getBackend())
-            .debug()
-            .addProgramClassesAndInnerClasses(MAIN)
-            .enableInliningAnnotations()
-            .addKeepMainRule(MAIN)
-            .noMinification()
-            .addOptionsModification(this::configure)
-            .setMinApi(parameters.getApiLevel())
-            .run(parameters.getRuntime(), MAIN);
-    test(result, true, false);
-
-    // R8 release, no minification.
-    result =
-        testForR8(parameters.getBackend())
-            .addProgramClassesAndInnerClasses(MAIN)
-            .enableInliningAnnotations()
-            .addKeepMainRule(MAIN)
-            .noMinification()
-            .addOptionsModification(this::configure)
-            .setMinApi(parameters.getApiLevel())
-            .run(parameters.getRuntime(), MAIN)
-            .assertSuccessWithOutput(JAVA_OUTPUT);
-    test(result, true, true);
-
-    // R8 release, minification.
-    result =
-        testForR8(parameters.getBackend())
-            .addProgramClassesAndInnerClasses(MAIN)
-            .enableInliningAnnotations()
-            .addKeepMainRule(MAIN)
-            .addOptionsModification(this::configure)
-            .setMinApi(parameters.getApiLevel())
-            // We are not checking output because it can't be matched due to minification. Just run.
-            .run(parameters.getRuntime(), MAIN);
-    test(result, true, true);
+    boolean isRelease = mode == CompilationMode.RELEASE;
+    boolean expectCallPresent = !isRelease;
+    int expectedGetClassCount = isRelease ? 0 : 5;
+    int expectedConstClassCount = isRelease ? (parameters.isCfRuntime() ? 8 : 6) : 1;
+    testForR8(parameters.getBackend())
+        .setMode(mode)
+        .addInnerClasses(GetClassTest.class)
+        .enableInliningAnnotations()
+        .addKeepMainRule(MAIN)
+        .noMinification()
+        .addOptionsModification(this::configure)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), MAIN)
+        .assertSuccessWithOutput(JAVA_OUTPUT)
+        .inspect(
+            inspector ->
+                test(inspector, expectCallPresent, expectedGetClassCount, expectedConstClassCount));
   }
 }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetNameTest.java b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetNameTest.java
index 6d9c2d7..848bf1d 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetNameTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetNameTest.java
@@ -21,6 +21,7 @@
 import com.google.common.collect.ImmutableList;
 import java.nio.file.Path;
 import java.util.Collection;
+import org.junit.Ignore;
 import org.junit.Test;
 
 class GetName0Class {
@@ -262,6 +263,7 @@
   }
 
   @Test
+  @Ignore("b/154813140: Invalidly assumes that getClass on kept classes can be optimized")
   public void testR8_pinning() throws Exception {
     // Pinning the test class.
     R8TestRunResult result =
@@ -280,6 +282,7 @@
   }
 
   @Test
+  @Ignore("b/154813140: Invalidly assumes that getClass on kept classes can be optimized")
   public void testR8_shallow_pinning() throws Exception {
     // Shallow pinning the test class.
     R8TestRunResult result =
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/switches/SwitchMapWithMissingFieldTest.java b/src/test/java/com/android/tools/r8/ir/optimize/switches/SwitchMapWithMissingFieldTest.java
index 796b3d9..707eb10 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/switches/SwitchMapWithMissingFieldTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/switches/SwitchMapWithMissingFieldTest.java
@@ -11,6 +11,8 @@
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.references.ClassReference;
 import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.utils.StringUtils;
+import java.io.File;
 import java.io.IOException;
 import java.nio.file.Path;
 import org.junit.Test;
@@ -58,10 +60,11 @@
   }
 
   private static Path getSwitchMapProgramFile() throws IOException {
+    String switchMapFileName =
+        StringUtils.join(File.separator, getSwitchMapClassReference().getBinaryName().split("/"))
+            + ".class";
     return getClassFilesForInnerClasses(SwitchMapWithMissingFieldTest.class).stream()
-        .filter(
-            file ->
-                file.toString().endsWith(getSwitchMapClassReference().getBinaryName() + ".class"))
+        .filter(file -> file.toString().endsWith(switchMapFileName))
         .findFirst()
         .get();
   }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/switches/SwitchMapWithUnexpectedFieldTest.java b/src/test/java/com/android/tools/r8/ir/optimize/switches/SwitchMapWithUnexpectedFieldTest.java
index 0679ef6..167cd47 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/switches/SwitchMapWithUnexpectedFieldTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/switches/SwitchMapWithUnexpectedFieldTest.java
@@ -11,6 +11,8 @@
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.references.ClassReference;
 import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.utils.StringUtils;
+import java.io.File;
 import java.io.IOException;
 import java.nio.file.Path;
 import org.junit.Test;
@@ -64,10 +66,11 @@
   }
 
   private static Path getSwitchMapProgramFile() throws IOException {
+    String switchMapFileName =
+        StringUtils.join(File.separator, getSwitchMapClassReference().getBinaryName().split("/"))
+            + ".class";
     return getClassFilesForInnerClasses(SwitchMapWithUnexpectedFieldTest.class).stream()
-        .filter(
-            file ->
-                file.toString().endsWith(getSwitchMapClassReference().getBinaryName() + ".class"))
+        .filter(file -> file.toString().endsWith(switchMapFileName))
         .findFirst()
         .get();
   }
diff --git a/src/test/java/com/android/tools/r8/naming/signature/GenericSignatureRenamingTest.java b/src/test/java/com/android/tools/r8/naming/signature/GenericSignatureRenamingTest.java
index 892b7d2..adf7ba7 100644
--- a/src/test/java/com/android/tools/r8/naming/signature/GenericSignatureRenamingTest.java
+++ b/src/test/java/com/android/tools/r8/naming/signature/GenericSignatureRenamingTest.java
@@ -4,59 +4,87 @@
 
 package com.android.tools.r8.naming.signature;
 
+import static org.junit.Assert.assertThrows;
+import static org.junit.Assume.assumeTrue;
+
 import com.android.tools.r8.CompilationMode;
 import com.android.tools.r8.R8TestBuilder;
 import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.shaking.ProguardKeepAttributes;
 import java.lang.reflect.ParameterizedType;
 import java.lang.reflect.Type;
 import java.lang.reflect.TypeVariable;
 import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
 
+@RunWith(Parameterized.class)
 public class GenericSignatureRenamingTest extends TestBase {
 
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public GenericSignatureRenamingTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
   @Test
   public void testJVM() throws Exception {
-    testForJvm().addTestClasspath().run(Main.class).assertSuccess();
-  }
-
-  @Test
-  public void testR8Dex() throws Exception {
-    test(testForR8(Backend.DEX));
-  }
-
-  @Test
-  public void testR8CompatDex() throws Exception {
-    test(testForR8Compat(Backend.DEX));
-  }
-
-  @Test
-  public void testR8DexNoMinify() throws Exception {
-    test(testForR8(Backend.DEX).addKeepRules("-dontobfuscate"));
-  }
-
-  @Test
-  public void testR8Cf() throws Exception {
-    test(testForR8(Backend.CF));
-  }
-
-  @Test
-  public void testR8CfNoMinify() throws Exception {
-    test(testForR8(Backend.CF).addKeepRules("-dontobfuscate"));
+    assumeTrue(parameters.isCfRuntime());
+    testForJvm().addTestClasspath().run(parameters.getRuntime(), Main.class).assertSuccess();
   }
 
   @Test
   public void testD8() throws Exception {
+    assumeTrue(parameters.isDexRuntime());
     testForD8()
         .addProgramClasses(Main.class)
         .addProgramClassesAndInnerClasses(A.class, B.class, CY.class, CYY.class)
         .setMode(CompilationMode.RELEASE)
+        .setMinApi(parameters.getApiLevel())
         .compile()
         .assertNoMessages()
-        .run(Main.class)
+        .run(parameters.getRuntime(), Main.class)
         .assertSuccess();
   }
 
+  @Test
+  public void testR8() throws Exception {
+    test(testForR8(parameters.getBackend()));
+  }
+
+  @Test
+  public void testR8Compat() throws Exception {
+    test(testForR8Compat(parameters.getBackend()));
+  }
+
+  @Test
+  public void testR8NoMinify() throws Exception {
+    test(testForR8(parameters.getBackend()).addKeepRules("-dontobfuscate"));
+  }
+
+  @Test
+  public void testR8WithAssertEnabled() {
+    // TODO(b/154793333): Enable assertions always when resolved.
+    assertThrows(
+        AssertionError.class,
+        () -> {
+          test(
+              testForR8(parameters.getBackend())
+                  .addKeepRules("-dontobfuscate")
+                  .addOptionsModification(
+                      internalOptions ->
+                          internalOptions.testing.assertConsistentRenamingOfSignature = true));
+        });
+  }
+
   private void test(R8TestBuilder<?> builder) throws Exception {
     builder
         .addKeepRules("-dontoptimize")
@@ -67,9 +95,10 @@
         .addProgramClasses(Main.class)
         .addProgramClassesAndInnerClasses(A.class, B.class, CY.class, CYY.class)
         .setMode(CompilationMode.RELEASE)
+        .setMinApi(parameters.getApiLevel())
         .compile()
         .assertNoMessages()
-        .run(Main.class)
+        .run(parameters.getRuntime(), Main.class)
         .assertSuccess();
   }
 }
@@ -92,6 +121,15 @@
     }
   }
 
+  class GenericInner<S extends T> {
+
+    private S s;
+
+    public GenericInner(S s) {
+      this.s = s;
+    }
+  }
+
   class Z extends Y {}
 
   static class S {}
@@ -107,6 +145,10 @@
   Y.ZZ newZZ() {
     return new Y().zz();
   }
+
+  public <S extends T> GenericInner<S> create(S s) {
+    return new GenericInner<>(s);
+  }
 }
 
 class B<T extends A<T>> {}
@@ -133,8 +175,11 @@
     CYY cyy = new CYY();
     A.S s = new A.S();
 
+    A<Object>.GenericInner<String> foo = new A<Object>().create("Foo");
+    Class<? extends A.GenericInner> aClass = foo.getClass();
+
     // Check if names of Z and ZZ shows A as a superclass.
-    Class classA = new A().getClass();
+    Class classA = A.class;
     String nameA = classA.getName();
 
     TypeVariable[] v = classA.getTypeParameters();
diff --git a/src/test/java/com/android/tools/r8/rewrite/assertions/AssertionConfigurationKotlinTest.java b/src/test/java/com/android/tools/r8/rewrite/assertions/AssertionConfigurationKotlinTest.java
index c2fdaa1..873788c 100644
--- a/src/test/java/com/android/tools/r8/rewrite/assertions/AssertionConfigurationKotlinTest.java
+++ b/src/test/java/com/android/tools/r8/rewrite/assertions/AssertionConfigurationKotlinTest.java
@@ -26,12 +26,14 @@
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
 import com.android.tools.r8.utils.codeinspector.InstructionSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import com.google.common.collect.ImmutableList;
 import java.nio.file.Path;
 import java.util.Collection;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.Objects;
 import org.junit.Assume;
 import org.junit.BeforeClass;
 import org.junit.Test;
@@ -45,41 +47,78 @@
 @RunWith(Parameterized.class)
 public class AssertionConfigurationKotlinTest extends KotlinTestBase implements Opcodes {
 
+  private static class KotlinCompilationKey {
+    KotlinTargetVersion targetVersion;
+    boolean useJvmAssertions;
+
+    private KotlinCompilationKey(KotlinTargetVersion targetVersion, boolean useJvmAssertions) {
+      this.targetVersion = targetVersion;
+      this.useJvmAssertions = useJvmAssertions;
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hash(targetVersion, useJvmAssertions);
+    }
+
+    @Override
+    public boolean equals(Object other) {
+      if (other == null) {
+        return false;
+      }
+      if (getClass() != other.getClass()) {
+        return false;
+      }
+      KotlinCompilationKey kotlinCompilationKey = (KotlinCompilationKey) other;
+      return targetVersion == kotlinCompilationKey.targetVersion
+          && useJvmAssertions == kotlinCompilationKey.useJvmAssertions;
+    }
+  }
+
   private static final Package pkg = AssertionConfigurationKotlinTest.class.getPackage();
   private static final String kotlintestclasesPackage = pkg.getName() + ".kotlintestclasses";
   private static final String testClassKt = kotlintestclasesPackage + ".TestClassKt";
   private static final String class1 = kotlintestclasesPackage + ".Class1";
   private static final String class2 = kotlintestclasesPackage + ".Class2";
 
-  private static final Map<KotlinTargetVersion, Path> kotlinClasses = new HashMap<>();
+  private static final Map<KotlinCompilationKey, Path> kotlinClasses = new HashMap<>();
   private final TestParameters parameters;
   private final boolean kotlinStdlibAsLibrary;
+  private final boolean useJvmAssertions;
+  private final KotlinCompilationKey kotlinCompilationKey;
 
-  @Parameterized.Parameters(name = "{0}, {1}, kotlin-stdlib as library: {2}")
+  @Parameterized.Parameters(name = "{0}, {1}, kotlin-stdlib as library: {2}, -Xassertions=jvm: {3}")
   public static Collection<Object[]> data() {
     return buildParameters(
         getTestParameters().withAllRuntimesAndApiLevels().build(),
         KotlinTargetVersion.values(),
+        BooleanUtils.values(),
         BooleanUtils.values());
   }
 
   public AssertionConfigurationKotlinTest(
       TestParameters parameters,
       KotlinTargetVersion targetVersion,
-      boolean kotlinStdlibAsClasspath) {
+      boolean kotlinStdlibAsClasspath,
+      boolean useJvmAssertions) {
     super(targetVersion);
     this.parameters = parameters;
     this.kotlinStdlibAsLibrary = kotlinStdlibAsClasspath;
+    this.useJvmAssertions = useJvmAssertions;
+    this.kotlinCompilationKey = new KotlinCompilationKey(targetVersion, useJvmAssertions);
   }
 
   @BeforeClass
   public static void compileKotlin() throws Exception {
     for (KotlinTargetVersion targetVersion : KotlinTargetVersion.values()) {
-      Path ktClasses =
-          kotlinc(KOTLINC, targetVersion)
-              .addSourceFiles(getKotlinFilesInTestPackage(pkg))
-              .compile();
-      kotlinClasses.put(targetVersion, ktClasses);
+      for (boolean useJvmAssertions : BooleanUtils.values()) {
+        Path ktClasses =
+            kotlinc(KOTLINC, targetVersion)
+                .addSourceFiles(getKotlinFilesInTestPackage(pkg))
+                .setUseJvmAssertions(useJvmAssertions)
+                .compile();
+        kotlinClasses.put(new KotlinCompilationKey(targetVersion, useJvmAssertions), ktClasses);
+      }
     }
   }
 
@@ -106,7 +145,7 @@
     if (kotlinStdlibAsLibrary) {
       testForD8()
           .addClasspathFiles(ToolHelper.getKotlinStdlibJar())
-          .addProgramFiles(kotlinClasses.get(targetVersion))
+          .addProgramFiles(kotlinClasses.get(kotlinCompilationKey))
           .setMinApi(parameters.getApiLevel())
           .apply(builderConsumer)
           .addRunClasspathFiles(kotlinStdlibLibraryForRuntime())
@@ -118,7 +157,7 @@
     } else {
       testForD8()
           .addProgramFiles(ToolHelper.getKotlinStdlibJar())
-          .addProgramFiles(kotlinClasses.get(targetVersion))
+          .addProgramFiles(kotlinClasses.get(kotlinCompilationKey))
           .setMinApi(parameters.getApiLevel())
           .apply(builderConsumer)
           .run(
@@ -147,7 +186,7 @@
     if (kotlinStdlibAsLibrary) {
       testForR8(parameters.getBackend())
           .addClasspathFiles(ToolHelper.getKotlinStdlibJar())
-          .addProgramFiles(kotlinClasses.get(targetVersion))
+          .addProgramFiles(kotlinClasses.get(kotlinCompilationKey))
           .addKeepMainRule(testClassKt)
           .addKeepClassAndMembersRules(class1, class2)
           .setMinApi(parameters.getApiLevel())
@@ -162,7 +201,7 @@
     } else {
       testForR8(parameters.getBackend())
           .addProgramFiles(ToolHelper.getKotlinStdlibJar())
-          .addProgramFiles(kotlinClasses.get(targetVersion))
+          .addProgramFiles(kotlinClasses.get(kotlinCompilationKey))
           .addKeepMainRule(testClassKt)
           .addKeepClassAndMembersRules(class1, class2)
           .setMinApi(parameters.getApiLevel())
@@ -225,7 +264,7 @@
       assert !kotlinStdlibAsLibrary;
       // With R8 the static-put of the kotlin._Assertions.INSTANCE field is removed as is not used.
       assertEquals(
-          (isR8 ? 1 : 2),
+          isR8 ? 1 : 2,
           subject
               .uniqueMethodWithName("<clinit>")
               .streamInstructions()
@@ -252,12 +291,17 @@
 
   private void checkAssertionCodeLeft(CodeInspector inspector, String clazz, boolean isR8) {
     ClassSubject subject = inspector.clazz(clazz);
-    assertThat(subject, isPresent());
-    if (subject.getOriginalName().equals("kotlin._Assertions")) {
+    if (clazz.equals("kotlin._Assertions")) {
       assert !kotlinStdlibAsLibrary;
+      if (isR8 && useJvmAssertions) {
+        // When JVM assertions are used the class kotlin._Assertions is unused.
+        assertThat(subject, not(isPresent()));
+        return;
+      }
+      assertThat(subject, isPresent());
       // With R8 the static-put of the kotlin._Assertions.INSTANCE field is removed as is not used.
       assertEquals(
-          (isR8 ? 1 : 2),
+          isR8 ? 1 : 2,
           subject
               .uniqueMethodWithName("<clinit>")
               .streamInstructions()
@@ -269,6 +313,13 @@
               .streamInstructions()
               .anyMatch(InstructionSubject::isConstNumber));
     } else {
+      assertThat(subject, isPresent());
+      MethodSubject clinit = subject.uniqueMethodWithName("<clinit>");
+      if (useJvmAssertions) {
+        assertTrue(clinit.streamInstructions().anyMatch(InstructionSubject::isStaticPut));
+      } else {
+        assertThat(clinit, not(isPresent()));
+      }
       assertTrue(
           subject
               .uniqueMethodWithName("m")
@@ -346,32 +397,90 @@
                 AssertionsConfiguration.Builder::enableAllAssertions),
         inspector -> checkAssertionCodeEnabled(inspector, true),
         allAssertionsExpectedLines());
-    // Enabling for the "kotlin._Assertions" class should enable all.
-    runD8Test(
-        builder ->
-            builder.addAssertionsConfiguration(
-                b -> b.setEnable().setScopeClass("kotlin._Assertions").build()),
-        inspector -> checkAssertionCodeEnabled(inspector, false),
-        allAssertionsExpectedLines());
-    runR8Test(
-        builder ->
-            builder.addAssertionsConfiguration(
-                b -> b.setEnable().setScopeClass("kotlin._Assertions").build()),
-        inspector -> checkAssertionCodeEnabled(inspector, true),
-        allAssertionsExpectedLines());
-    // Enabling for the "kotlin" package should enable all.
-    runD8Test(
-        builder ->
-            builder.addAssertionsConfiguration(
-                b -> b.setEnable().setScopePackage("kotlin").build()),
-        inspector -> checkAssertionCodeEnabled(inspector, false),
-        allAssertionsExpectedLines());
-    runR8Test(
-        builder ->
-            builder.addAssertionsConfiguration(
-                b -> b.setEnable().setScopePackage("kotlin").build()),
-        inspector -> checkAssertionCodeEnabled(inspector, true),
-        allAssertionsExpectedLines());
+    if (useJvmAssertions) {
+      // Enabling for the kotlin generated Java classes should enable all.
+      runD8Test(
+          builder ->
+              builder
+                  .addAssertionsConfiguration(b -> b.setEnable().setScopeClass(class1).build())
+                  .addAssertionsConfiguration(b -> b.setEnable().setScopeClass(class2).build()),
+          inspector -> {
+            // The default is applied to kotlin._Assertions (which for DEX is remove).
+            if (!kotlinStdlibAsLibrary) {
+              checkAssertionCodeRemoved(inspector, "kotlin._Assertions", false);
+            }
+            checkAssertionCodeEnabled(inspector, class1, false);
+            checkAssertionCodeEnabled(inspector, class2, false);
+          },
+          allAssertionsExpectedLines());
+    } else {
+      // Enabling for the class kotlin._Assertions should enable all.
+      runD8Test(
+          builder ->
+              builder.addAssertionsConfiguration(
+                  b -> b.setEnable().setScopeClass("kotlin._Assertions").build()),
+          inspector -> checkAssertionCodeEnabled(inspector, false),
+          allAssertionsExpectedLines());
+    }
+    if (useJvmAssertions) {
+      // Enabling for the kotlin generated Java classes should enable all.
+      runR8Test(
+          builder ->
+              builder
+                  .addAssertionsConfiguration(b -> b.setEnable().setScopeClass(class1).build())
+                  .addAssertionsConfiguration(b -> b.setEnable().setScopeClass(class2).build()),
+          inspector -> checkAssertionCodeEnabled(inspector, true),
+          allAssertionsExpectedLines());
+    } else {
+      // Enabling for the class kotlin._Assertions should enable all.
+      runR8Test(
+          builder ->
+              builder.addAssertionsConfiguration(
+                  b -> b.setEnable().setScopeClass("kotlin._Assertions").build()),
+          inspector -> checkAssertionCodeEnabled(inspector, true),
+          allAssertionsExpectedLines());
+    }
+    if (useJvmAssertions) {
+      // Enabling for the Java package for the kotlin test classes package should enable all.
+      runD8Test(
+          builder ->
+              builder.addAssertionsConfiguration(
+                  b -> b.setEnable().setScopePackage(kotlintestclasesPackage).build()),
+          inspector -> {
+            // The default is applied to kotlin._Assertions (which for DEX is remove).
+            if (!kotlinStdlibAsLibrary) {
+              checkAssertionCodeRemoved(inspector, "kotlin._Assertions", false);
+            }
+            checkAssertionCodeEnabled(inspector, class1, false);
+            checkAssertionCodeEnabled(inspector, class2, false);
+          },
+          allAssertionsExpectedLines());
+    } else {
+      // Enabling for the kotlin package (containing kotlin._Assertions) should enable all.
+      runD8Test(
+          builder ->
+              builder.addAssertionsConfiguration(
+                  b -> b.setEnable().setScopePackage("kotlin").build()),
+          inspector -> checkAssertionCodeEnabled(inspector, false),
+          allAssertionsExpectedLines());
+    }
+    if (useJvmAssertions) {
+      // Enabling for the Java package for the kotlin test classes package should enable all.
+      runR8Test(
+          builder ->
+              builder.addAssertionsConfiguration(
+                  b -> b.setEnable().setScopePackage(kotlintestclasesPackage).build()),
+          inspector -> checkAssertionCodeEnabled(inspector, true),
+          allAssertionsExpectedLines());
+    } else {
+      // Enabling for the kotlin package (containing kotlin._Assertions) should enable all.
+      runR8Test(
+          builder ->
+              builder.addAssertionsConfiguration(
+                  b -> b.setEnable().setScopePackage("kotlin").build()),
+          inspector -> checkAssertionCodeEnabled(inspector, true),
+          allAssertionsExpectedLines());
+    }
   }
 
   @Test
@@ -425,7 +534,7 @@
     Assume.assumeTrue(parameters.isDexRuntime());
     testForD8()
         .addProgramClassFileData(dumpModifiedKotlinAssertions())
-        .addProgramFiles(kotlinClasses.get(targetVersion))
+        .addProgramFiles(kotlinClasses.get(kotlinCompilationKey))
         .setMinApi(parameters.getApiLevel())
         .addAssertionsConfiguration(AssertionsConfiguration.Builder::passthroughAllAssertions)
         .run(
@@ -434,7 +543,7 @@
         .assertSuccessWithOutputLines(noAllAssertionsExpectedLines());
     testForD8()
         .addProgramClassFileData(dumpModifiedKotlinAssertions())
-        .addProgramFiles(kotlinClasses.get(targetVersion))
+        .addProgramFiles(kotlinClasses.get(kotlinCompilationKey))
         .setMinApi(parameters.getApiLevel())
         .addAssertionsConfiguration(AssertionsConfiguration.Builder::enableAllAssertions)
         .run(
@@ -443,7 +552,7 @@
         .assertSuccessWithOutputLines(allAssertionsExpectedLines());
     testForD8()
         .addProgramClassFileData(dumpModifiedKotlinAssertions())
-        .addProgramFiles(kotlinClasses.get(targetVersion))
+        .addProgramFiles(kotlinClasses.get(kotlinCompilationKey))
         .setMinApi(parameters.getApiLevel())
         .addAssertionsConfiguration(AssertionsConfiguration.Builder::disableAllAssertions)
         .run(
diff --git a/src/test/java/com/android/tools/r8/shaking/R8Shaking2LookupTest.java b/src/test/java/com/android/tools/r8/shaking/R8Shaking2LookupTest.java
index e64933b..35f67b2 100644
--- a/src/test/java/com/android/tools/r8/shaking/R8Shaking2LookupTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/R8Shaking2LookupTest.java
@@ -8,10 +8,11 @@
 import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.ToolHelper;
-import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.google.common.collect.ImmutableList;
 import java.io.IOException;
 import java.util.concurrent.ExecutionException;
@@ -23,25 +24,27 @@
   static final String APP_FILE_NAME = ToolHelper.EXAMPLES_BUILD_DIR + "shaking2/classes.dex";
   private DirectMappedDexApplication program;
   private DexItemFactory dexItemFactory;
-  private AppInfoWithSubtyping appInfo;
+  private AppInfoWithClassHierarchy appInfo;
+  private SubtypingInfo subtypingInfo;
 
   @Before
   public void readApp() throws IOException, ExecutionException {
     program = ToolHelper.buildApplication(ImmutableList.of(APP_FILE_NAME));
     dexItemFactory = program.dexItemFactory;
-    appInfo = new AppInfoWithSubtyping(program);
+    appInfo = new AppInfoWithClassHierarchy(program);
+    subtypingInfo = new SubtypingInfo(program.allClasses(), program);
   }
 
   private void validateSubtype(DexType super_type, DexType sub_type) {
     assertFalse(super_type.equals(sub_type));
-    assertTrue(appInfo.subtypes(super_type).contains(sub_type));
+    assertTrue(subtypingInfo.subtypes(super_type).contains(sub_type));
     assertTrue(appInfo.isSubtype(sub_type, super_type));
-    assertFalse(appInfo.subtypes(sub_type).contains(super_type));
+    assertFalse(subtypingInfo.subtypes(sub_type).contains(super_type));
     assertFalse(appInfo.isSubtype(super_type, sub_type));
   }
 
   private void validateSubtypeSize(DexType type, int size) {
-    assertEquals(size, appInfo.subtypes(type).size());
+    assertEquals(size, subtypingInfo.subtypes(type).size());
   }
 
   @Test
diff --git a/third_party/tachiyomi.tar.gz.sha1 b/third_party/tachiyomi.tar.gz.sha1
new file mode 100644
index 0000000..cf45571
--- /dev/null
+++ b/third_party/tachiyomi.tar.gz.sha1
@@ -0,0 +1 @@
+8ef393ca5ac25fb182071a274bf8f266753824b8
\ No newline at end of file
diff --git a/tools/run_on_app.py b/tools/run_on_app.py
index 1687797..ad9f63f 100755
--- a/tools/run_on_app.py
+++ b/tools/run_on_app.py
@@ -22,9 +22,11 @@
 import chrome_data
 import r8_data
 import iosched_data
+import tachiyomi_data
 
 TYPES = ['dex', 'deploy', 'proguarded']
-APPS = ['gmscore', 'nest', 'youtube', 'gmail', 'chrome', 'r8', 'iosched']
+APPS = [
+  'gmscore', 'nest', 'youtube', 'gmail', 'chrome', 'r8', 'iosched', 'tachiyomi']
 COMPILERS = ['d8', 'r8']
 COMPILER_BUILDS = ['full', 'lib']
 
@@ -207,6 +209,7 @@
       'gmail': gmail_data,
       'r8': r8_data,
       'iosched': iosched_data,
+      'tachiyomi': tachiyomi_data
   }
   # Check to ensure that we add all variants here.
   assert len(APPS) == len(data_providers)
@@ -388,6 +391,9 @@
   elif options.app == 'iosched':
     version = options.version or '2019'
     data = iosched_data
+  elif options.app == 'tachiyomi':
+    version = options.version or 'b15d2fe16864645055af6a745a62cc5566629798'
+    data = tachiyomi_data
   else:
     raise Exception("You need to specify '--app={}'".format('|'.join(APPS)))
   return version, data
@@ -480,7 +486,8 @@
                              or options.app == 'chrome'
                              or options.app == 'nest'
                              or options.app == 'r8'
-                             or options.app == 'iosched'):
+                             or options.app == 'iosched'
+                             or options.app == 'tachiyomi'):
     inputs = values['inputs']
 
   args.extend(['--output', outdir])
diff --git a/tools/run_on_as_app.py b/tools/run_on_as_app.py
index 6d7905e..94ef0dc 100755
--- a/tools/run_on_as_app.py
+++ b/tools/run_on_as_app.py
@@ -704,7 +704,15 @@
       app.name,
       shrinker,
       ' for recompilation' if keepRuleSynthesisForRecompilation else ''))
-
+  print('To compile locally: '
+        'tools/run_on_as_app.py --shrinker {} --r8-compilation-steps {} '
+        '--app {} {}'.format(
+            shrinker,
+            options.r8_compilation_steps,
+            app.name,
+            '--r8-compilation-steps-only'
+              if options.r8_compilation_steps_only else ''))
+  print('HINT: use --shrinker r8-nolib --no-build if you have a local R8.jar')
   # Add settings.gradle file if it is not present to prevent gradle from finding
   # the settings.gradle file in the r8 root when apps are placed under
   # $R8/build.
diff --git a/tools/tachiyomi_data.py b/tools/tachiyomi_data.py
new file mode 100644
index 0000000..5518cea
--- /dev/null
+++ b/tools/tachiyomi_data.py
@@ -0,0 +1,18 @@
+# Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+# for details. All rights reserved. Use of this source code is governed by a
+# BSD-style license that can be found in the LICENSE file.
+
+import os
+import utils
+
+BASE = os.path.join(utils.THIRD_PARTY, 'tachiyomi')
+
+VERSIONS = {
+  'b15d2fe16864645055af6a745a62cc5566629798': {
+    'deploy' : {
+        'inputs': [os.path.join(BASE, 'program.jar')],
+        'pgconf': [os.path.join(BASE, 'proguard.config')],
+        'libraries': [os.path.join(BASE, 'library.jar')],
+    },
+  },
+}