diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 3293b0b..40f7230 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -1190,6 +1190,11 @@
       SubtypingInfo subtypingInfo,
       List<KeepDeclaration> keepDeclarations)
       throws ExecutionException {
+    timing.begin("Update subtyping info");
+    subtypingInfo.unsetTypeInfo();
+    subtypingInfo.update(appView);
+    assert subtypingInfo.verifyUpToDate(appView);
+    timing.end();
     timing.begin("Set up enqueuer");
     Enqueuer enqueuer =
         EnqueuerFactory.createForInitialTreeShaking(
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 1d27755..523caf6 100644
--- a/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
@@ -4,7 +4,9 @@
 package com.android.tools.r8.graph;
 
 import static com.android.tools.r8.graph.DexApplication.classesWithDeterministicOrder;
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
 
+import com.android.tools.r8.utils.WorkList;
 import com.android.tools.r8.utils.structural.StructuralItem;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
@@ -33,7 +35,7 @@
   // Map from types to their subtypes.
   private final Map<DexType, Set<DexType>> subtypeMap;
 
-  private final Map<DexType, TypeInfo> typeInfo;
+  private Map<DexType, TypeInfo> typeInfo;
 
   private final DexDefinitionSupplier definitionSupplier;
   private final DexItemFactory factory;
@@ -48,16 +50,38 @@
     factory = definitionSupplier.dexItemFactory();
   }
 
-  public static SubtypingInfo create(AppView<? extends AppInfoWithClassHierarchy> appView) {
-    return create(appView.appInfo());
+  public void update(AppView<? extends AppInfoWithClassHierarchy> appView) {
+    assert typeInfo == null : "Extending typeInfo not implemented";
+    if (!appView.getSyntheticItems().hasPendingSyntheticClasses()) {
+      return;
+    }
+    WorkList<DexType> worklist = WorkList.newIdentityWorkList();
+    for (DexClass clazz : appView.getSyntheticItems().getAllPendingSyntheticClasses()) {
+      worklist.addIfNotSeen(clazz.allImmediateSupertypes());
+      worklist.process(
+          supertype -> {
+            DexClass superclass = appView.definitionFor(supertype);
+            if (superclass == null) {
+              return;
+            }
+            subtypeMap.computeIfAbsent(supertype, ignoreKey(HashSet::new)).add(clazz.getType());
+            worklist.addIfNotSeen(superclass.allImmediateSupertypes());
+          });
+      worklist.clearSeen();
+    }
   }
 
-  public static SubtypingInfo create(AppInfoWithClassHierarchy appInfo) {
-    DirectMappedDexApplication directApp = appInfo.app().asDirect();
-    return create(
-        Iterables.concat(
-            directApp.programClasses(), directApp.classpathClasses(), directApp.libraryClasses()),
-        appInfo);
+  public SubtypingInfo unsetTypeInfo() {
+    typeInfo = null;
+    return this;
+  }
+
+  public static SubtypingInfo create(AppView<? extends AppInfoWithClassHierarchy> appView) {
+    AppInfoWithClassHierarchy appInfo = appView.appInfo();
+    DirectMappedDexApplication app = appInfo.app().asDirect();
+    Iterable<DexClass> classes =
+        Iterables.concat(app.programClasses(), app.classpathClasses(), app.libraryClasses());
+    return create(classes, appInfo);
   }
 
   public static SubtypingInfo create(
@@ -134,7 +158,6 @@
     for (DexClass clazz : classes) {
       populateAllSuperTypes(map, typeInfo, clazz.type, clazz, definitionSupplier);
     }
-    map.replaceAll((k, v) -> ImmutableSet.copyOf(v));
     assert validateLevelsAreCorrect(typeInfo, definitionSupplier);
   }
 
@@ -233,6 +256,38 @@
     return classesWithDeterministicOrder(interfaces);
   }
 
+  public boolean verifyUpToDate(AppView<AppInfoWithClassHierarchy> appView) {
+    DirectMappedDexApplication app = appView.app().asDirect();
+    Iterable<DexClass> classes =
+        Iterables.concat(app.programClasses(), app.classpathClasses(), app.libraryClasses());
+    for (DexClass clazz : classes) {
+      assert verifyUpToDate(appView, clazz);
+    }
+    // This does not check that the `typeInfo` is up-to-date.
+    assert typeInfo == null;
+    return true;
+  }
+
+  private boolean verifyUpToDate(AppView<AppInfoWithClassHierarchy> appView, DexClass clazz) {
+    WorkList<DexType> worklist = WorkList.newIdentityWorkList(clazz.allImmediateSupertypes());
+    worklist.process(
+        supertype -> {
+          DexClass superclass = appView.definitionFor(supertype);
+          if (superclass == null) {
+            return;
+          }
+          assert subtypes(supertype).contains(clazz.getType())
+                  || (clazz.isLibraryClass()
+                      && appView.definitionFor(clazz.getType()).isProgramClass())
+              : "Expected subtypes("
+                  + supertype.getTypeName()
+                  + ") to include "
+                  + clazz.getTypeName();
+          worklist.addIfNotSeen(superclass.allImmediateSupertypes());
+        });
+    return true;
+  }
+
   private static class TypeInfo {
 
     private final DexType type;
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 4d0f480..64690e7 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -4212,9 +4212,10 @@
     }
 
     // Commit the pending synthetics and recompute subtypes.
+    subtypingInfo.update(appView);
     appInfo = timing.time("Rebuild AppInfo", () -> appInfo.rebuildWithClassHierarchy(app -> app));
     appView.setAppInfo(appInfo);
-    subtypingInfo = timing.time("Create SubtypingInfo", () -> SubtypingInfo.create(appView));
+    assert subtypingInfo.verifyUpToDate(appView);
 
     // 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.
diff --git a/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java b/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
index 6a61237..bec8b29 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
@@ -754,7 +754,7 @@
                           resolutionMethod
                               .getDefinition()
                               .toForwardingMethod(originalClazz, appView)));
-          assert methodToKeepReference.equals(methodToKeep.getReference());
+          assert methodToKeepReference.isIdenticalTo(methodToKeep.getReference());
         } else {
           methodToKeep = resolutionMethod;
         }
diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
index e15699a..b5d4585 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
@@ -205,6 +205,14 @@
       }
       return Collections.unmodifiableList(allPending);
     }
+
+    Collection<DexClass> getAllClasses() {
+      List<DexClass> allPending = new ArrayList<>(definitions.size());
+      for (SyntheticDefinition<?, ?, ?> item : definitions.values()) {
+        allPending.add(item.getHolder());
+      }
+      return Collections.unmodifiableList(allPending);
+    }
   }
 
   private final State state;
@@ -443,6 +451,10 @@
     return pending.getAllProgramClasses();
   }
 
+  public Collection<DexClass> getAllPendingSyntheticClasses() {
+    return pending.getAllClasses();
+  }
+
   public boolean isCommittedSynthetic(DexType type) {
     return committed.containsType(type);
   }
diff --git a/src/test/testbase/java/com/android/tools/r8/TestBase.java b/src/test/testbase/java/com/android/tools/r8/TestBase.java
index a7c4dc6..94b4f19 100644
--- a/src/test/testbase/java/com/android/tools/r8/TestBase.java
+++ b/src/test/testbase/java/com/android/tools/r8/TestBase.java
@@ -969,18 +969,21 @@
     // Run the tree shaker to compute an instance of AppInfoWithLiveness.
     ExecutorService executor = Executors.newSingleThreadExecutor();
     ProfileCollectionAdditions profileCollectionAdditions = ProfileCollectionAdditions.nop();
-    SubtypingInfo subtypingInfo = SubtypingInfo.create(appView);
     RootSet rootSet =
         RootSet.builder(
                 appView,
                 profileCollectionAdditions,
-                subtypingInfo,
+                SubtypingInfo.create(appView),
                 appView.options().getProguardConfiguration().getRules())
             .build(executor);
     appView.setRootSet(rootSet);
+    appView.rebuildAppInfo();
     EnqueuerResult enqueuerResult =
         EnqueuerFactory.createForInitialTreeShaking(
-                appView, profileCollectionAdditions, executor, subtypingInfo)
+                appView,
+                profileCollectionAdditions,
+                executor,
+                SubtypingInfo.create(appView).unsetTypeInfo())
             .traceApplication(rootSet, executor, Timing.empty());
     executor.shutdown();
     // We do not run the tree pruner to ensure that the hierarchy is as designed and not modified