Update instantiatedHierarchy instead of rebuilding it in wave done.

Bug: b/422947619

Change-Id: I56adcb6fc3ed0eb118adf6dd5fb78e4ea9c73ec3
diff --git a/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java b/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
index f51757a..7ec7554 100644
--- a/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
+++ b/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.lens.GraphLens;
 import com.android.tools.r8.ir.conversion.LensCodeRewriterUtils;
 import com.android.tools.r8.ir.desugar.LambdaDescriptor;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.GraphReporter;
 import com.android.tools.r8.shaking.InstantiationReason;
 import com.android.tools.r8.shaking.KeepReason;
@@ -76,6 +77,9 @@
 
   public abstract void mutate(Consumer<Builder> mutator, AppInfo appInfo);
 
+  public abstract void removeNoLongerInstantiatedClasses(
+      Set<DexProgramClass> noLongerInstantiatedClasses, AppInfoWithLiveness appInfo);
+
   /**
    * True if a class type might be instantiated directly at the given type.
    *
@@ -350,6 +354,52 @@
       repopulateInstantiatedHierarchy(appInfo);
     }
 
+    @Override
+    public void removeNoLongerInstantiatedClasses(
+        Set<DexProgramClass> noLongerInstantiatedClasses, AppInfoWithLiveness appInfo) {
+      noLongerInstantiatedClasses.forEach(
+          clazz -> {
+            classesWithAllocationSiteTracking.remove(clazz);
+            classesWithoutAllocationSiteTracking.remove(clazz);
+            assert instantiatedHierarchy != null;
+            clearClass(appInfo, clazz);
+          });
+    }
+
+    private void clearClass(AppInfoWithLiveness appInfo, DexClass clz) {
+      clz.forEachImmediateSupertype(superType -> clearSupertype(superType, clz, appInfo));
+    }
+
+    private void clearSupertype(DexType superType, DexClass clz, AppInfoWithLiveness appInfo) {
+      Set<DexClass> instantiatedSubclasses = instantiatedHierarchy.get(superType);
+      if (instantiatedSubclasses == null) {
+        return;
+      }
+      instantiatedSubclasses.remove(clz);
+      if (!instantiatedSubclasses.isEmpty()) {
+        return;
+      }
+      instantiatedHierarchy.remove(superType);
+      // Check if the superclass needs to be cleared too.
+      if (instantiatedLambdas.containsKey(superType)) {
+        return;
+      }
+      DexClass superClass = appInfo.definitionFor(superType);
+      if (superClass == null) {
+        return;
+      }
+      if (superClass.isProgramClass()) {
+        DexProgramClass superProgramClass = superClass.asProgramClass();
+        if (classesWithAllocationSiteTracking.containsKey(superProgramClass)
+            || classesWithoutAllocationSiteTracking.contains(superProgramClass)
+            || interfacesWithUnknownSubtypeHierarchy.contains(superProgramClass)) {
+          return;
+        }
+      }
+      // The super class is no longer instantiated. Recursively remove it.
+      clearClass(appInfo, superClass);
+    }
+
     private boolean shouldTrackAllocationSitesForClass(
         DexProgramClass clazz, InstantiationReason instantiationReason) {
       if (!data.trackAllocationSites) {
@@ -479,12 +529,6 @@
       populateInstantiatedHierarchy(definitions, type);
     }
 
-    public void markNoLongerInstantiated(DexProgramClass clazz) {
-      classesWithAllocationSiteTracking.remove(clazz);
-      classesWithoutAllocationSiteTracking.remove(clazz);
-      instantiatedHierarchy = null;
-    }
-
     Builder rewrittenWithLens(
         ObjectAllocationInfoCollectionImpl objectAllocationInfos,
         DexDefinitionSupplier definitions,
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 2066b3a..25f2a95 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -739,9 +739,9 @@
     return objectAllocationInfoCollection;
   }
 
-  void mutateObjectAllocationInfoCollection(
-      Consumer<ObjectAllocationInfoCollectionImpl.Builder> mutator) {
-    objectAllocationInfoCollection.mutate(mutator, this);
+  void removeNoLongerInstantiatedClasses(Set<DexProgramClass> noLongerInstantiatedClasses) {
+    objectAllocationInfoCollection.removeNoLongerInstantiatedClasses(
+        noLongerInstantiatedClasses, this);
   }
 
   void removeFromSingleTargetLookupCache(DexClass clazz) {
diff --git a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLivenessModifier.java b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLivenessModifier.java
index 305d864..387b6db 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLivenessModifier.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLivenessModifier.java
@@ -34,8 +34,7 @@
   public void modify(AppInfoWithLiveness appInfo) {
     // Instantiated classes.
     noLongerInstantiatedClasses.forEach(appInfo::removeFromSingleTargetLookupCache);
-    appInfo.mutateObjectAllocationInfoCollection(
-        mutator -> noLongerInstantiatedClasses.forEach(mutator::markNoLongerInstantiated));
+    appInfo.removeNoLongerInstantiatedClasses(noLongerInstantiatedClasses);
     // Written fields.
     MutableFieldAccessInfoCollection<?, ? extends MutableFieldAccessInfo>
         fieldAccessInfoCollection = appInfo.getMutableFieldAccessInfoCollection();