diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 5b08837..8ffd211 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -444,9 +444,7 @@
               .notifyTreePrunerFinished(Enqueuer.Mode.INITIAL_TREE_SHAKING);
 
           // Recompute the subtyping information.
-          new AbstractMethodRemover(
-                  appViewWithLiveness, appViewWithLiveness.appInfo().computeSubtypingInfo())
-              .run();
+          new AbstractMethodRemover(appViewWithLiveness).run();
 
           AnnotationRemover annotationRemover =
               annotationRemoverBuilder.build(appViewWithLiveness, prunedItems.getRemovedClasses());
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 a5854e2..51e9b02 100644
--- a/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java
@@ -3,13 +3,13 @@
 // 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 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.DexProgramClass;
-import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
 import com.android.tools.r8.graph.ProgramMethod;
-import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.shaking.ScopedDexMethodSet.AddMethodIfMoreVisibleResult;
 import java.util.HashSet;
 import java.util.Set;
@@ -26,28 +26,39 @@
 public class AbstractMethodRemover {
 
   private final AppView<AppInfoWithLiveness> appView;
-  private final SubtypingInfo subtypingInfo;
+  private final ImmediateProgramSubtypingInfo immediateSubtypingInfo;
+
   private ScopedDexMethodSet scope = new ScopedDexMethodSet();
 
-  public AbstractMethodRemover(AppView<AppInfoWithLiveness> appView, SubtypingInfo subtypingInfo) {
+  public AbstractMethodRemover(AppView<AppInfoWithLiveness> appView) {
     this.appView = appView;
-    this.subtypingInfo = subtypingInfo;
+    this.immediateSubtypingInfo = ImmediateProgramSubtypingInfo.create(appView);
   }
 
   public void run() {
-    assert scope.getParent() == null;
-    processClass(appView.dexItemFactory().objectType);
+    for (DexProgramClass clazz : appView.appInfo().classes()) {
+      assert scope.getParent() == null;
+      if (isRoot(clazz)) {
+        processClass(clazz);
+      }
+    }
     appView.notifyOptimizationFinishedForTesting();
   }
 
-  private void processClass(DexType type) {
-    DexClass holder = appView.definitionFor(type);
-    scope = scope.newNestedScope();
-    if (holder != null && holder.isProgramClass()) {
-      processMethods(holder.asProgramClass());
+  private boolean isRoot(DexProgramClass clazz) {
+    if (clazz.isInterface()) {
+      return false;
     }
-    // TODO(b/154881041): Does this need the full subtype hierarchy of referenced types!?
-    subtypingInfo.forAllImmediateExtendsSubtypes(type, this::processClass);
+    if (!clazz.hasSuperType()) {
+      return true;
+    }
+    return asProgramClassOrNull(appView.definitionFor(clazz.getSuperType(), clazz)) == null;
+  }
+
+  private void processClass(DexProgramClass clazz) {
+    scope = scope.newNestedScope();
+    processMethods(clazz);
+    immediateSubtypingInfo.getSubclasses(clazz).forEach(this::processClass);
     scope = scope.getParent();
   }
 
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 c522643..b701cdf 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -48,7 +48,6 @@
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.graph.PrunedItems;
 import com.android.tools.r8.graph.SingleDispatchTargetLookupResult;
-import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.graph.UnknownDispatchTargetLookupResult;
 import com.android.tools.r8.graph.lens.GraphLens;
 import com.android.tools.r8.graph.lens.NonIdentityGraphLens;
@@ -1448,10 +1447,6 @@
     return clazz.isNotProgramClass() || isInstantiatedInterface(clazz.asProgramClass());
   }
 
-  public SubtypingInfo computeSubtypingInfo() {
-    return SubtypingInfo.create(this);
-  }
-
   public boolean verifyNoIteratingOverPrunedClasses() {
     classes()
         .forEach(