diff --git a/src/main/java/com/android/tools/r8/GenerateMainDexList.java b/src/main/java/com/android/tools/r8/GenerateMainDexList.java
index 0bb17c7..42290d2 100644
--- a/src/main/java/com/android/tools/r8/GenerateMainDexList.java
+++ b/src/main/java/com/android/tools/r8/GenerateMainDexList.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.shaking.Enqueuer;
 import com.android.tools.r8.shaking.EnqueuerFactory;
 import com.android.tools.r8.shaking.MainDexClasses;
@@ -54,8 +55,10 @@
 
       MainDexListBuilder.checkForAssumedLibraryTypes(appView.appInfo());
 
+      SubtypingInfo subtypingInfo = new SubtypingInfo(application.allClasses(), application);
+
       RootSet mainDexRootSet =
-          new RootSetBuilder(appView, application, options.mainDexKeepRules).run(executor);
+          new RootSetBuilder(appView, subtypingInfo, options.mainDexKeepRules).run(executor);
 
       GraphConsumer graphConsumer = options.mainDexKeptGraphConsumer;
       WhyAreYouKeepingConsumer whyAreYouKeepingConsumer = null;
@@ -64,7 +67,8 @@
         graphConsumer = whyAreYouKeepingConsumer;
       }
 
-      Enqueuer enqueuer = EnqueuerFactory.createForMainDexTracing(appView, graphConsumer);
+      Enqueuer enqueuer =
+          EnqueuerFactory.createForMainDexTracing(appView, subtypingInfo, graphConsumer);
       Set<DexProgramClass> liveTypes = enqueuer.traceMainDex(mainDexRootSet, executor, timing);
       // LiveTypes is the result.
       MainDexClasses mainDexClasses = new MainDexListBuilder(liveTypes, application).run();
diff --git a/src/main/java/com/android/tools/r8/PrintSeeds.java b/src/main/java/com/android/tools/r8/PrintSeeds.java
index fb4edb5..7c2302a 100644
--- a/src/main/java/com/android/tools/r8/PrintSeeds.java
+++ b/src/main/java/com/android/tools/r8/PrintSeeds.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.AppServices;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.Enqueuer;
 import com.android.tools.r8.shaking.EnqueuerFactory;
@@ -89,10 +90,11 @@
       AppView<? extends AppInfoWithClassHierarchy> appView =
           AppView.createForR8(new AppInfoWithClassHierarchy(application), options);
       appView.setAppServices(AppServices.builder(appView).build());
+      SubtypingInfo subtypingInfo = new SubtypingInfo(application.allClasses(), application);
       RootSet rootSet =
-          new RootSetBuilder(appView, application, options.getProguardConfiguration().getRules())
+          new RootSetBuilder(appView, subtypingInfo, options.getProguardConfiguration().getRules())
               .run(executor);
-      Enqueuer enqueuer = EnqueuerFactory.createForInitialTreeShaking(appView);
+      Enqueuer enqueuer = EnqueuerFactory.createForInitialTreeShaking(appView, subtypingInfo);
       AppInfoWithLiveness appInfo =
           enqueuer.traceApplication(
               rootSet, options.getProguardConfiguration().getDontWarnPatterns(), executor, timing);
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index e82c7eb..30201ce 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -334,11 +334,11 @@
                     options.itemFactory, AndroidApiLevel.getAndroidApiLevel(options.minApiLevel)));
           }
         }
-
+        SubtypingInfo subtypingInfo = new SubtypingInfo(application.allClasses(), application);
         appView.setRootSet(
             new RootSetBuilder(
                     appView,
-                    application,
+                    subtypingInfo,
                     Iterables.concat(
                         options.getProguardConfiguration().getRules(), synthesizedProguardRules))
                 .run(executorService));
@@ -346,7 +346,7 @@
         AnnotationRemover.Builder annotationRemoverBuilder =
             options.isShrinking() ? AnnotationRemover.builder() : null;
         AppView<AppInfoWithLiveness> appViewWithLiveness =
-            runEnqueuer(annotationRemoverBuilder, executorService, appView);
+            runEnqueuer(annotationRemoverBuilder, executorService, appView, subtypingInfo);
         application = appViewWithLiveness.appInfo().app().asDirect();
         assert appView.rootSet().verifyKeptFieldsAreAccessedAndLive(appViewWithLiveness.appInfo());
         assert appView.rootSet().verifyKeptMethodsAreTargetedAndLive(appViewWithLiveness.appInfo());
@@ -414,11 +414,14 @@
       if (!options.mainDexKeepRules.isEmpty()) {
         assert appView.graphLense().isIdentityLense();
         // Find classes which may have code executed before secondary dex files installation.
+        SubtypingInfo subtypingInfo =
+            new SubtypingInfo(appView.appInfo().app().asDirect().allClasses(), appView);
         mainDexRootSet =
-            new RootSetBuilder(appView, application, options.mainDexKeepRules).run(executorService);
+            new RootSetBuilder(appView, subtypingInfo, options.mainDexKeepRules)
+                .run(executorService);
         // Live types is the tracing result.
         Set<DexProgramClass> mainDexBaseClasses =
-            EnqueuerFactory.createForMainDexTracing(appView)
+            EnqueuerFactory.createForMainDexTracing(appView, subtypingInfo)
                 .traceMainDex(mainDexRootSet, executorService, timing);
         // Calculate the automatic main dex list according to legacy multidex constraints.
         mainDexClasses = new MainDexListBuilder(mainDexBaseClasses, application).run();
@@ -608,7 +611,10 @@
         }
 
         Enqueuer enqueuer =
-            EnqueuerFactory.createForMainDexTracing(appView, mainDexKeptGraphConsumer);
+            EnqueuerFactory.createForMainDexTracing(
+                appView,
+                new SubtypingInfo(application.allClasses(), application),
+                mainDexKeptGraphConsumer);
         // Find classes which may have code executed before secondary dex files installation.
         // Live types is the tracing result.
         Set<DexProgramClass> mainDexBaseClasses =
@@ -657,7 +663,11 @@
           }
 
           Enqueuer enqueuer =
-              EnqueuerFactory.createForFinalTreeShaking(appView, keptGraphConsumer, missingClasses);
+              EnqueuerFactory.createForFinalTreeShaking(
+                  appView,
+                  new SubtypingInfo(application.allClasses(), application),
+                  keptGraphConsumer,
+                  missingClasses);
           appView.setAppInfo(
               enqueuer
                   .traceApplication(
@@ -863,9 +873,10 @@
   private AppView<AppInfoWithLiveness> runEnqueuer(
       AnnotationRemover.Builder annotationRemoverBuilder,
       ExecutorService executorService,
-      AppView<AppInfoWithClassHierarchy> appView)
+      AppView<AppInfoWithClassHierarchy> appView,
+      SubtypingInfo subtypingInfo)
       throws ExecutionException {
-    Enqueuer enqueuer = EnqueuerFactory.createForInitialTreeShaking(appView);
+    Enqueuer enqueuer = EnqueuerFactory.createForInitialTreeShaking(appView, subtypingInfo);
     enqueuer.setAnnotationRemoverBuilder(annotationRemoverBuilder);
     if (appView.options().enableInitializedClassesInInstanceMethodsAnalysis) {
       enqueuer.registerAnalysis(new InitializedClassesInInstanceMethodsAnalysis(appView));
@@ -921,11 +932,17 @@
     // If there is no kept-graph info, re-run the enqueueing to compute it.
     if (whyAreYouKeepingConsumer == null) {
       whyAreYouKeepingConsumer = new WhyAreYouKeepingConsumer(null);
+      SubtypingInfo subtypingInfo =
+          new SubtypingInfo(appView.appInfo().app().asDirect().allClasses(), appView);
       if (forMainDex) {
-        enqueuer = EnqueuerFactory.createForMainDexTracing(appView, whyAreYouKeepingConsumer);
+        enqueuer =
+            EnqueuerFactory.createForMainDexTracing(
+                appView, subtypingInfo, whyAreYouKeepingConsumer);
         enqueuer.traceMainDex(rootSet, executorService, timing);
       } else {
-        enqueuer = EnqueuerFactory.createForWhyAreYouKeeping(appView, whyAreYouKeepingConsumer);
+        enqueuer =
+            EnqueuerFactory.createForWhyAreYouKeeping(
+                appView, subtypingInfo, whyAreYouKeepingConsumer);
         enqueuer.traceApplication(
             rootSet,
             options.getProguardConfiguration().getDontWarnPatterns(),
diff --git a/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java b/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
index 6c6e3ba..662ccb0 100644
--- a/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
@@ -14,6 +14,7 @@
 import java.util.HashSet;
 import java.util.IdentityHashMap;
 import java.util.Map;
+import java.util.Objects;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ConcurrentSkipListSet;
@@ -46,6 +47,18 @@
     populateSubtypeMap(classes, definitions::definitionFor, factory);
   }
 
+  public boolean verifyEquals(Collection<DexClass> classes, DexDefinitionSupplier definitions) {
+    SubtypingInfo subtypingInfo = new SubtypingInfo(classes, definitions);
+    assert typeInfo.equals(subtypingInfo.typeInfo);
+    assert subtypeMap.keySet().equals(subtypingInfo.subtypeMap.keySet());
+    subtypeMap.forEach(
+        (key, value) -> {
+          assert subtypingInfo.subtypeMap.get(key).equals(value);
+        });
+    assert missingClasses.equals(subtypingInfo.missingClasses);
+    return true;
+  }
+
   private void populateSuperType(
       Map<DexType, Set<DexType>> map,
       DexType superType,
@@ -239,6 +252,20 @@
     }
 
     @Override
+    public int hashCode() {
+      return Objects.hash(type, directSubtypes);
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      if (!(obj instanceof TypeInfo)) {
+        return false;
+      }
+      TypeInfo other = (TypeInfo) obj;
+      return other.type == type && other.directSubtypes.equals(directSubtypes);
+    }
+
+    @Override
     public String toString() {
       return "TypeInfo{" + type + ", level:" + hierarchyLevel + "}";
     }
diff --git a/src/main/java/com/android/tools/r8/shaking/ConsequentRootSetBuilder.java b/src/main/java/com/android/tools/r8/shaking/ConsequentRootSetBuilder.java
index ddb649c..8288bde 100644
--- a/src/main/java/com/android/tools/r8/shaking/ConsequentRootSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/ConsequentRootSetBuilder.java
@@ -5,14 +5,17 @@
 
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.SubtypingInfo;
 
 class ConsequentRootSetBuilder extends RootSetBuilder {
 
   private final Enqueuer enqueuer;
 
   ConsequentRootSetBuilder(
-      AppView<? extends AppInfoWithClassHierarchy> appView, Enqueuer enqueuer) {
-    super(appView, appView.appInfo().app(), null);
+      AppView<? extends AppInfoWithClassHierarchy> appView,
+      SubtypingInfo subtypingInfo,
+      Enqueuer enqueuer) {
+    super(appView, subtypingInfo, null);
     this.enqueuer = enqueuer;
   }
 
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 61e7ea4..5540e34 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -178,7 +178,7 @@
   // Don't hold a direct pointer to app info (use appView).
   private AppInfoWithClassHierarchy appInfo;
   private final AppView<AppInfoWithClassHierarchy> appView;
-  private final SubtypingInfo subtypingInfo;
+  private SubtypingInfo subtypingInfo;
   private final InternalOptions options;
   private RootSet rootSet;
   private ProguardClassFilter dontWarnPatterns;
@@ -344,14 +344,15 @@
 
   Enqueuer(
       AppView<? extends AppInfoWithClassHierarchy> appView,
+      SubtypingInfo subtypingInfo,
       GraphConsumer keptGraphConsumer,
       Mode mode) {
     assert appView.appServices() != null;
     InternalOptions options = appView.options();
     this.appInfo = appView.appInfo();
     this.appView = appView.withClassHierarchy();
-    this.subtypingInfo =
-        new SubtypingInfo(appView.appInfo().app().asDirect().allClasses(), appView);
+    this.subtypingInfo = subtypingInfo;
+    assert subtypingInfo.verifyEquals(appView.appInfo().app().asDirect().allClasses(), appView);
     this.forceProguardCompatibility = options.forceProguardCompatibility;
     this.graphReporter = new GraphReporter(appView, keptGraphConsumer);
     this.mode = mode;
@@ -2724,8 +2725,10 @@
     // Now all additions are computed, the application is atomically extended with those additions.
     Builder appBuilder = appInfo.app().asDirect().builder();
     additions.amendApplication(appBuilder);
-    appInfo = new AppInfoWithClassHierarchy(appBuilder.build());
+    DirectMappedDexApplication app = appBuilder.build();
+    appInfo = new AppInfoWithClassHierarchy(app);
     appView.setAppInfo(appInfo);
+    subtypingInfo = new SubtypingInfo(app.allClasses(), app);
 
     // Finally once all synthesized items "exist" it is now safe to continue tracing. The new work
     // items are enqueued and the fixed point will continue once this subroutine returns.
@@ -3110,7 +3113,7 @@
             }
           }
           ConsequentRootSetBuilder consequentSetBuilder =
-              new ConsequentRootSetBuilder(appView, this);
+              new ConsequentRootSetBuilder(appView, subtypingInfo, this);
           IfRuleEvaluator ifRuleEvaluator =
               new IfRuleEvaluator(
                   appView,
@@ -3222,7 +3225,7 @@
   }
 
   private ConsequentRootSet computeDelayedInterfaceMethodSyntheticBridges() {
-    RootSetBuilder builder = new RootSetBuilder(appView);
+    RootSetBuilder builder = new RootSetBuilder(appView, subtypingInfo);
     for (DelayedRootSetActionItem delayedRootSetActionItem : rootSet.delayedRootSetActionItems) {
       if (delayedRootSetActionItem.isInterfaceMethodSyntheticBridgeAction()) {
         handleInterfaceMethodSyntheticBridgeAction(
diff --git a/src/main/java/com/android/tools/r8/shaking/EnqueuerFactory.java b/src/main/java/com/android/tools/r8/shaking/EnqueuerFactory.java
index ddc5f62..743f0df 100644
--- a/src/main/java/com/android/tools/r8/shaking/EnqueuerFactory.java
+++ b/src/main/java/com/android/tools/r8/shaking/EnqueuerFactory.java
@@ -8,21 +8,24 @@
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.shaking.Enqueuer.Mode;
 import java.util.Set;
 
 public class EnqueuerFactory {
 
   public static Enqueuer createForInitialTreeShaking(
-      AppView<? extends AppInfoWithClassHierarchy> appView) {
-    return new Enqueuer(appView, null, Mode.INITIAL_TREE_SHAKING);
+      AppView<? extends AppInfoWithClassHierarchy> appView, SubtypingInfo subtypingInfo) {
+    return new Enqueuer(appView, subtypingInfo, null, Mode.INITIAL_TREE_SHAKING);
   }
 
   public static Enqueuer createForFinalTreeShaking(
       AppView<? extends AppInfoWithClassHierarchy> appView,
+      SubtypingInfo subtypingInfo,
       GraphConsumer keptGraphConsumer,
       Set<DexType> initialMissingTypes) {
-    Enqueuer enqueuer = new Enqueuer(appView, keptGraphConsumer, Mode.FINAL_TREE_SHAKING);
+    Enqueuer enqueuer =
+        new Enqueuer(appView, subtypingInfo, keptGraphConsumer, Mode.FINAL_TREE_SHAKING);
     appView.withProtoShrinker(
         shrinker -> enqueuer.setInitialDeadProtoTypes(shrinker.getDeadProtoTypes()));
     enqueuer.setInitialMissingTypes(initialMissingTypes);
@@ -30,17 +33,21 @@
   }
 
   public static Enqueuer createForMainDexTracing(
-      AppView<? extends AppInfoWithClassHierarchy> appView) {
-    return createForMainDexTracing(appView, null);
+      AppView<? extends AppInfoWithClassHierarchy> appView, SubtypingInfo subtypingInfo) {
+    return createForMainDexTracing(appView, subtypingInfo, null);
   }
 
   public static Enqueuer createForMainDexTracing(
-      AppView<? extends AppInfoWithClassHierarchy> appView, GraphConsumer keptGraphConsumer) {
-    return new Enqueuer(appView, keptGraphConsumer, Mode.MAIN_DEX_TRACING);
+      AppView<? extends AppInfoWithClassHierarchy> appView,
+      SubtypingInfo subtypingInfo,
+      GraphConsumer keptGraphConsumer) {
+    return new Enqueuer(appView, subtypingInfo, keptGraphConsumer, Mode.MAIN_DEX_TRACING);
   }
 
   public static Enqueuer createForWhyAreYouKeeping(
-      AppView<? extends AppInfoWithClassHierarchy> appView, GraphConsumer keptGraphConsumer) {
-    return new Enqueuer(appView, keptGraphConsumer, Mode.WHY_ARE_YOU_KEEPING);
+      AppView<? extends AppInfoWithClassHierarchy> appView,
+      SubtypingInfo subtypingInfo,
+      GraphConsumer keptGraphConsumer) {
+    return new Enqueuer(appView, subtypingInfo, keptGraphConsumer, Mode.WHY_ARE_YOU_KEEPING);
   }
 }
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 88c9fe2..058693e 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
@@ -115,17 +115,19 @@
 
   public RootSetBuilder(
       AppView<? extends AppInfoWithClassHierarchy> appView,
-      DexApplication application,
+      SubtypingInfo subtypingInfo,
       Iterable<? extends ProguardConfigurationRule> rules) {
     this.appView = appView;
-    this.application = application.asDirect();
-    this.subtypingInfo = new SubtypingInfo(this.application.allClasses(), this.application);
+    this.subtypingInfo = subtypingInfo;
+    this.application = appView.appInfo().app().asDirect();
     this.rules = rules;
     this.options = appView.options();
+    assert subtypingInfo.verifyEquals(this.application.allClasses(), this.application);
   }
 
-  public RootSetBuilder(AppView<? extends AppInfoWithClassHierarchy> appView) {
-    this(appView, appView.appInfo().app(), null);
+  public RootSetBuilder(
+      AppView<? extends AppInfoWithClassHierarchy> appView, SubtypingInfo subtypingInfo) {
+    this(appView, subtypingInfo, null);
   }
 
   void handleMatchedAnnotation(AnnotationMatchResult annotation) {
diff --git a/src/test/java/com/android/tools/r8/TestBase.java b/src/test/java/com/android/tools/r8/TestBase.java
index 6c3ed35..7c3ddff 100644
--- a/src/test/java/com/android/tools/r8/TestBase.java
+++ b/src/test/java/com/android/tools/r8/TestBase.java
@@ -34,6 +34,7 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
 import com.android.tools.r8.graph.SmaliWriter;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.jasmin.JasminBuilder;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.references.ClassReference;
@@ -618,15 +619,16 @@
     AppView<AppInfoWithClassHierarchy> appView = computeAppViewWithSubtyping(app);
     // Run the tree shaker to compute an instance of AppInfoWithLiveness.
     ExecutorService executor = Executors.newSingleThreadExecutor();
-    DexApplication application = appView.appInfo().app();
+    DirectMappedDexApplication application = appView.appInfo().app().asDirect();
+    SubtypingInfo subtypingInfo = new SubtypingInfo(application.allClasses(), application);
     RootSet rootSet =
         new RootSetBuilder(
                 appView,
-                application,
+                subtypingInfo,
                 proguardConfigurationRulesGenerator.apply(appView.appInfo().dexItemFactory()))
             .run(executor);
     AppInfoWithLiveness appInfoWithLiveness =
-        EnqueuerFactory.createForInitialTreeShaking(appView)
+        EnqueuerFactory.createForInitialTreeShaking(appView, subtypingInfo)
             .traceApplication(rootSet, ProguardClassFilter.empty(), executor, application.timing);
     // We do not run the tree pruner to ensure that the hierarchy is as designed and not modified
     // due to liveness.
diff --git a/src/test/java/com/android/tools/r8/ir/InlineTest.java b/src/test/java/com/android/tools/r8/ir/InlineTest.java
index dc0585a..a2246c0 100644
--- a/src/test/java/com/android/tools/r8/ir/InlineTest.java
+++ b/src/test/java/com/android/tools/r8/ir/InlineTest.java
@@ -11,6 +11,8 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DirectMappedDexApplication;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
@@ -47,18 +49,20 @@
       MethodSubject method,
       List<IRCode> additionalCode)
       throws ExecutionException {
+    DirectMappedDexApplication directApp = application.asDirect();
     AppView<AppInfoWithClassHierarchy> appView =
-        AppView.createForR8(new AppInfoWithClassHierarchy(application.asDirect()), options);
+        AppView.createForR8(new AppInfoWithClassHierarchy(directApp), options);
     appView.setAppServices(AppServices.builder(appView).build());
     ExecutorService executorService = ThreadUtils.getExecutorService(options);
+    SubtypingInfo subtypingInfo = new SubtypingInfo(directApp.allClasses(), directApp);
     appView.setRootSet(
         new RootSetBuilder(
                 appView,
-                application,
+                subtypingInfo,
                 ImmutableList.of(ProguardKeepRule.defaultKeepAllRule(unused -> {})))
             .run(executorService));
     Timing timing = Timing.empty();
-    Enqueuer enqueuer = EnqueuerFactory.createForInitialTreeShaking(appView);
+    Enqueuer enqueuer = EnqueuerFactory.createForInitialTreeShaking(appView, subtypingInfo);
     appView.setAppInfo(
         enqueuer.traceApplication(
             appView.rootSet(), ProguardClassFilter.empty(), executorService, timing));
diff --git a/src/test/java/com/android/tools/r8/ir/conversion/PartialCallGraphTest.java b/src/test/java/com/android/tools/r8/ir/conversion/PartialCallGraphTest.java
index 5f07b54..1ea4e67 100644
--- a/src/test/java/com/android/tools/r8/ir/conversion/PartialCallGraphTest.java
+++ b/src/test/java/com/android/tools/r8/ir/conversion/PartialCallGraphTest.java
@@ -10,21 +10,15 @@
 import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertTrue;
 
-import com.android.tools.r8.dex.ApplicationReader;
-import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
-import com.android.tools.r8.graph.AppServices;
 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.DirectMappedDexApplication;
 import com.android.tools.r8.ir.conversion.CallGraph.Node;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import com.android.tools.r8.shaking.Enqueuer;
-import com.android.tools.r8.shaking.EnqueuerFactory;
 import com.android.tools.r8.shaking.ProguardConfigurationParser;
-import com.android.tools.r8.shaking.RootSetBuilder;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.Reporter;
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.Timing;
 import com.google.common.collect.ImmutableList;
@@ -36,33 +30,24 @@
 
 public class PartialCallGraphTest extends CallGraphTestBase {
   private final AppView<AppInfoWithLiveness> appView;
-  private final InternalOptions options = new InternalOptions();
-  private final ExecutorService executorService = ThreadUtils.getExecutorService(options);
+  private final InternalOptions options;
+  private final ExecutorService executorService;
 
   public PartialCallGraphTest() throws Exception {
-    Timing timing = Timing.empty();
     AndroidApp app = testForD8().addProgramClasses(TestClass.class).compile().app;
-    DirectMappedDexApplication application =
-        new ApplicationReader(app, options, timing).read().toDirect();
-    AppView<AppInfoWithClassHierarchy> appView =
-        AppView.createForR8(new AppInfoWithClassHierarchy(application), options);
-    appView.setAppServices(AppServices.builder(appView).build());
-    ProguardConfigurationParser parser =
-        new ProguardConfigurationParser(appView.dexItemFactory(), options.reporter);
-    parser.parse(
-        createConfigurationForTesting(
-            ImmutableList.of("-keep class ** { void m1(); void m5(); }")));
-    appView.setRootSet(
-        new RootSetBuilder(
-            appView, application, parser.getConfig().getRules()).run(executorService));
-    Enqueuer enqueuer = EnqueuerFactory.createForInitialTreeShaking(appView);
     this.appView =
-        appView.setAppInfo(
-            enqueuer.traceApplication(
-                appView.rootSet(),
-                parser.getConfig().getDontWarnPatterns(),
-                executorService,
-                timing));
+        computeAppViewWithLiveness(
+            app,
+            factory -> {
+              ProguardConfigurationParser parser =
+                  new ProguardConfigurationParser(factory, new Reporter());
+              parser.parse(
+                  createConfigurationForTesting(
+                      ImmutableList.of("-keep class ** { void m1(); void m5(); }")));
+              return parser.getConfig().getRules();
+            });
+    this.options = appView.options();
+    this.executorService = ThreadUtils.getExecutorService(options);
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/naming/NamingTestBase.java b/src/test/java/com/android/tools/r8/naming/NamingTestBase.java
index 74bae45..385911c 100644
--- a/src/test/java/com/android/tools/r8/naming/NamingTestBase.java
+++ b/src/test/java/com/android/tools/r8/naming/NamingTestBase.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
+import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.shaking.Enqueuer;
 import com.android.tools.r8.shaking.EnqueuerFactory;
 import com.android.tools.r8.shaking.ProguardConfiguration;
@@ -61,6 +62,7 @@
   protected NamingLens runMinifier(List<Path> configPaths) throws ExecutionException {
     ProguardConfiguration configuration =
         ToolHelper.loadProguardConfiguration(dexItemFactory, configPaths);
+
     InternalOptions options = new InternalOptions(configuration, new Reporter());
     options.programConsumer = DexIndexedConsumer.emptyConsumer();
 
@@ -68,11 +70,12 @@
 
     AppView<AppInfoWithClassHierarchy> appView =
         AppView.createForR8(new AppInfoWithClassHierarchy(program), options);
+    SubtypingInfo subtypingInfo = new SubtypingInfo(program.allClasses(), program);
     appView.setRootSet(
-        new RootSetBuilder(appView, program, configuration.getRules()).run(executor));
+        new RootSetBuilder(appView, subtypingInfo, configuration.getRules()).run(executor));
     appView.setAppServices(AppServices.builder(appView).build());
 
-    Enqueuer enqueuer = EnqueuerFactory.createForInitialTreeShaking(appView);
+    Enqueuer enqueuer = EnqueuerFactory.createForInitialTreeShaking(appView, subtypingInfo);
     appView.setAppInfo(
         enqueuer.traceApplication(
             appView.rootSet(), configuration.getDontWarnPatterns(), executor, timing));