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 b2ecd15..4205abc 100644
--- a/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java
+++ b/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java
@@ -4,16 +4,18 @@
 
 package com.android.tools.r8.graph;
 
+import com.google.common.collect.Iterables;
+import java.util.Objects;
 import java.util.function.Function;
 
 public class BottomUpClassHierarchyTraversal<T extends DexClass>
     extends ClassHierarchyTraversal<T, BottomUpClassHierarchyTraversal<T>> {
 
-  private final Function<DexType, Iterable<DexType>> immediateSubtypesProvider;
+  private final Function<T, Iterable<T>> immediateSubtypesProvider;
 
   private BottomUpClassHierarchyTraversal(
       AppView<? extends AppInfoWithClassHierarchy> appView,
-      Function<DexType, Iterable<DexType>> immediateSubtypesProvider,
+      Function<T, Iterable<T>> immediateSubtypesProvider,
       Scope scope) {
     super(appView, scope);
     this.immediateSubtypesProvider = immediateSubtypesProvider;
@@ -26,16 +28,14 @@
   public static BottomUpClassHierarchyTraversal<DexClass> forAllClasses(
       AppView<? extends AppInfoWithClassHierarchy> appView, SubtypingInfo subtypingInfo) {
     return new BottomUpClassHierarchyTraversal<>(
-        appView, subtypingInfo::allImmediateSubtypes, Scope.ALL_CLASSES);
-  }
-
-  /**
-   * Returns a visitor that can be used to visit all the program classes that are reachable from a
-   * given set of sources.
-   */
-  public static BottomUpClassHierarchyTraversal<DexProgramClass> forProgramClasses(
-      AppView<? extends AppInfoWithClassHierarchy> appView, SubtypingInfo subtypingInfo) {
-    return forProgramClasses(appView, subtypingInfo::allImmediateSubtypes);
+        appView,
+        clazz ->
+            Iterables.filter(
+                Iterables.transform(
+                    subtypingInfo.allImmediateSubtypes(clazz.getType()),
+                    appView::contextIndependentDefinitionFor),
+                Objects::nonNull),
+        Scope.ALL_CLASSES);
   }
 
   /**
@@ -44,7 +44,17 @@
    */
   public static BottomUpClassHierarchyTraversal<DexProgramClass> forProgramClasses(
       AppView<? extends AppInfoWithClassHierarchy> appView,
-      Function<DexType, Iterable<DexType>> immediateSubtypesProvider) {
+      ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
+    return forProgramClasses(appView, immediateSubtypingInfo::getSubclasses);
+  }
+
+  /**
+   * Returns a visitor that can be used to visit all the program classes that are reachable from a
+   * given set of sources.
+   */
+  public static BottomUpClassHierarchyTraversal<DexProgramClass> forProgramClasses(
+      AppView<? extends AppInfoWithClassHierarchy> appView,
+      Function<DexProgramClass, Iterable<DexProgramClass>> immediateSubtypesProvider) {
     return new BottomUpClassHierarchyTraversal<>(
         appView, immediateSubtypesProvider, Scope.ONLY_PROGRAM_CLASSES);
   }
@@ -70,12 +80,9 @@
     worklist.addFirst(clazzWithTypeT);
 
     // Add subtypes to worklist.
-    for (DexType subtype : immediateSubtypesProvider.apply(clazz.getType())) {
-      DexClass definition = definitionSupplier.contextIndependentDefinitionFor(subtype);
-      if (definition != null) {
-        if (scope != Scope.ONLY_PROGRAM_CLASSES || definition.isProgramClass()) {
-          addDependentsToWorklist(definition);
-        }
+    for (DexClass subclass : immediateSubtypesProvider.apply(clazzWithTypeT)) {
+      if (scope != Scope.ONLY_PROGRAM_CLASSES || subclass.isProgramClass()) {
+        addDependentsToWorklist(subclass);
       }
     }
   }
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 dace46c..1d27755 100644
--- a/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
@@ -6,7 +6,6 @@
 import static com.android.tools.r8.graph.DexApplication.classesWithDeterministicOrder;
 
 import com.android.tools.r8.utils.structural.StructuralItem;
-import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
@@ -189,16 +188,6 @@
     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.
    *
@@ -223,25 +212,6 @@
     }
   }
 
-  /**
-   * 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();
-  }
-
   public Set<DexType> allImmediateSubtypes(DexType type) {
     return getTypeInfo(type).directSubtypes;
   }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
index 80b6dc7..9307f89 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
@@ -106,7 +106,13 @@
       Timing timing)
       throws ExecutionException {
     // Run the policies on all program classes to produce a final grouping.
-    List<Policy> policies = PolicyScheduler.getPolicies(appView, runtimeTypeCheckInfo);
+    ImmediateProgramSubtypingInfo immediateSubtypingInfo =
+        appView.enableWholeProgramOptimizations()
+            ? ImmediateProgramSubtypingInfo.createWithDeterministicOrder(
+                appView.withClassHierarchy())
+            : null;
+    List<Policy> policies =
+        PolicyScheduler.getPolicies(appView, immediateSubtypingInfo, runtimeTypeCheckInfo);
     Collection<HorizontalMergeGroup> groups =
         new HorizontalClassMergerPolicyExecutor()
             .run(getInitialGroups(), policies, executorService, timing);
@@ -127,11 +133,6 @@
 
     // Ensure that all allocations of classes that end up needing a class id use a constructor on
     // the class itself.
-    ImmediateProgramSubtypingInfo immediateSubtypingInfo =
-        appView.enableWholeProgramOptimizations()
-            ? ImmediateProgramSubtypingInfo.createWithDeterministicOrder(
-                appView.withClassHierarchy())
-            : null;
     new UndoConstructorInlining(appView, classMergerSharedData, immediateSubtypingInfo)
         .runIfNecessary(groups, executorService, timing);
 
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyScheduler.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyScheduler.java
index 9e1a36e..cb7bda1 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyScheduler.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyScheduler.java
@@ -66,9 +66,12 @@
 public class PolicyScheduler {
 
   public static List<Policy> getPolicies(
-      AppView<?> appView, RuntimeTypeCheckInfo runtimeTypeCheckInfo) {
+      AppView<?> appView,
+      ImmediateProgramSubtypingInfo immediateSubtypingInfo,
+      RuntimeTypeCheckInfo runtimeTypeCheckInfo) {
     if (appView.hasClassHierarchy()) {
-      return getPoliciesForR8(appView.withClassHierarchy(), runtimeTypeCheckInfo);
+      return getPoliciesForR8(
+          appView.withClassHierarchy(), immediateSubtypingInfo, runtimeTypeCheckInfo);
     } else {
       return getPoliciesForD8(appView.withoutClassHierarchy());
     }
@@ -87,11 +90,12 @@
 
   private static List<Policy> getPoliciesForR8(
       AppView<? extends AppInfoWithClassHierarchy> appView,
+      ImmediateProgramSubtypingInfo immediateSubtypingInfo,
       RuntimeTypeCheckInfo runtimeTypeCheckInfo) {
     List<Policy> policies =
         ImmutableList.<Policy>builder()
             .addAll(getSingleClassPolicies(appView, runtimeTypeCheckInfo))
-            .addAll(getMultiClassPolicies(appView, runtimeTypeCheckInfo))
+            .addAll(getMultiClassPolicies(appView, immediateSubtypingInfo, runtimeTypeCheckInfo))
             .build();
     policies = appView.options().testing.horizontalClassMergingPolicyRewriter.apply(policies);
     assert verifyPolicyOrderingConstraints(policies);
@@ -195,6 +199,7 @@
 
   private static List<Policy> getMultiClassPolicies(
       AppView<? extends AppInfoWithClassHierarchy> appView,
+      ImmediateProgramSubtypingInfo immediateSubtypingInfo,
       RuntimeTypeCheckInfo runtimeTypeCheckInfo) {
     ImmutableList.Builder<Policy> builder = ImmutableList.builder();
     addRequiredMultiClassPolicies(appView, runtimeTypeCheckInfo, builder);
@@ -206,7 +211,7 @@
       builder.add(new PreserveMethodCharacteristics(appView.withLiveness()));
     }
     builder.add(new MinimizeInstanceFieldCasts());
-    addMultiClassPoliciesForInterfaceMerging(appView, builder);
+    addMultiClassPoliciesForInterfaceMerging(appView, immediateSubtypingInfo, builder);
     return builder.add(new LimitClassGroups(appView), new FinalizeMergeGroup(appView)).build();
   }
 
@@ -260,10 +265,11 @@
 
   private static void addMultiClassPoliciesForInterfaceMerging(
       AppView<? extends AppInfoWithClassHierarchy> appView,
+      ImmediateProgramSubtypingInfo immediateSubtypingInfo,
       ImmutableList.Builder<Policy> builder) {
     builder.add(
         new NoDefaultInterfaceMethodMerging(appView),
-        new NoDefaultInterfaceMethodCollisions(appView),
+        new NoDefaultInterfaceMethodCollisions(appView, immediateSubtypingInfo),
         new LimitInterfaceGroups(appView),
         new OnlyDirectlyConnectedOrUnrelatedInterfaces(appView));
   }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoDefaultInterfaceMethodCollisions.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoDefaultInterfaceMethodCollisions.java
index 801db59..f66d516 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoDefaultInterfaceMethodCollisions.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoDefaultInterfaceMethodCollisions.java
@@ -16,7 +16,7 @@
 import com.android.tools.r8.graph.DexMethodSignature;
 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.graph.ImmediateProgramSubtypingInfo;
 import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
 import com.android.tools.r8.horizontalclassmerging.HorizontalMergeGroup;
 import com.android.tools.r8.horizontalclassmerging.MultiClassPolicyWithPreprocessing;
@@ -72,9 +72,13 @@
     extends MultiClassPolicyWithPreprocessing<Map<DexType, InterfaceInfo>> {
 
   private final AppView<? extends AppInfoWithClassHierarchy> appView;
+  private final ImmediateProgramSubtypingInfo immediateSubtypingInfo;
 
-  public NoDefaultInterfaceMethodCollisions(AppView<? extends AppInfoWithClassHierarchy> appView) {
+  public NoDefaultInterfaceMethodCollisions(
+      AppView<? extends AppInfoWithClassHierarchy> appView,
+      ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
     this.appView = appView;
+    this.immediateSubtypingInfo = immediateSubtypingInfo;
   }
 
   @Override
@@ -144,8 +148,7 @@
   @Override
   public Map<DexType, InterfaceInfo> preprocess(
       Collection<HorizontalMergeGroup> groups, ExecutorService executorService) {
-    SubtypingInfo subtypingInfo = SubtypingInfo.create(appView);
-    Collection<DexProgramClass> classesOfInterest = computeClassesOfInterest(subtypingInfo);
+    Collection<DexProgramClass> classesOfInterest = computeClassesOfInterest();
     Map<DexType, DexMethodSignatureSet> inheritedClassMethodsPerClass =
         computeInheritedClassMethodsPerProgramClass(classesOfInterest);
     Map<DexType, Map<DexMethodSignature, Set<DexMethod>>> inheritedDefaultMethodsPerClass =
@@ -156,7 +159,7 @@
     Map<DexType, Map<DexMethodSignature, Set<DexMethod>>>
         defaultMethodsInheritedBySubclassesPerClass =
             computeDefaultMethodsInheritedBySubclassesPerProgramClass(
-                classesOfInterest, inheritedDefaultMethodsPerClass, groups, subtypingInfo);
+                classesOfInterest, inheritedDefaultMethodsPerClass, groups, immediateSubtypingInfo);
 
     // Store the computed information for each interface that is subject to merging.
     Map<DexType, InterfaceInfo> infos = new IdentityHashMap<>();
@@ -176,8 +179,7 @@
   }
 
   /** Returns the set of program classes that must be considered during preprocessing. */
-  @SuppressWarnings("UnusedVariable")
-  private Collection<DexProgramClass> computeClassesOfInterest(SubtypingInfo subtypingInfo) {
+  private Collection<DexProgramClass> computeClassesOfInterest() {
     // TODO(b/173990042): Limit result to the set of classes that are in the same as one of
     //  the interfaces that is subject to merging.
     return appView.appInfo().classes();
@@ -275,13 +277,13 @@
           Collection<DexProgramClass> classesOfInterest,
           Map<DexType, Map<DexMethodSignature, Set<DexMethod>>> inheritedDefaultMethodsPerClass,
           Collection<HorizontalMergeGroup> groups,
-          SubtypingInfo subtypingInfo) {
+          ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
     // Build a mapping from class types to their merge group.
-    Map<DexType, Iterable<DexProgramClass>> classGroupsByType =
+    Map<DexProgramClass, Iterable<DexProgramClass>> classGroupsByClass =
         MapUtils.newIdentityHashMap(
             builder ->
                 Iterables.filter(groups, HorizontalMergeGroup::isClassGroup)
-                    .forEach(group -> group.forEach(clazz -> builder.put(clazz.getType(), group))));
+                    .forEach(group -> group.forEach(clazz -> builder.put(clazz, group))));
 
     // Copy the map from classes to their inherited default methods.
     Map<DexType, Map<DexMethodSignature, Set<DexMethod>>>
@@ -298,15 +300,15 @@
     // Therefore, it is important that we don't process any of A's supertypes until B has been
     // processed, since that would lead to inadequate upwards propagation. To achieve this, we
     // simulate that both A and B are subtypes of A's and B's supertypes.
-    Function<DexType, Iterable<DexType>> immediateSubtypesProvider =
-        type -> {
-          Set<DexType> immediateSubtypesAfterClassMerging = Sets.newIdentityHashSet();
-          for (DexType immediateSubtype : subtypingInfo.allImmediateSubtypes(type)) {
-            Iterable<DexProgramClass> group = classGroupsByType.get(immediateSubtype);
+    Function<DexProgramClass, Iterable<DexProgramClass>> immediateSubtypesProvider =
+        clazz -> {
+          Set<DexProgramClass> immediateSubtypesAfterClassMerging = Sets.newIdentityHashSet();
+          for (DexProgramClass immediateSubclass : immediateSubtypingInfo.getSubclasses(clazz)) {
+            Iterable<DexProgramClass> group = classGroupsByClass.get(immediateSubclass);
             if (group != null) {
-              group.forEach(member -> immediateSubtypesAfterClassMerging.add(member.getType()));
+              group.forEach(immediateSubtypesAfterClassMerging::add);
             } else {
-              immediateSubtypesAfterClassMerging.add(immediateSubtype);
+              immediateSubtypesAfterClassMerging.add(immediateSubclass);
             }
           }
           return immediateSubtypesAfterClassMerging;
@@ -321,7 +323,7 @@
                   defaultMethodsInheritedBySubclassesPerClass.getOrDefault(
                       clazz.getType(), emptyMap());
               Iterable<DexProgramClass> group =
-                  classGroupsByType.getOrDefault(clazz.getType(), IterableUtils.singleton(clazz));
+                  classGroupsByClass.getOrDefault(clazz, IterableUtils.singleton(clazz));
               for (DexProgramClass member : group) {
                 for (DexType supertype : member.allImmediateSupertypes()) {
                   Map<DexMethodSignature, Set<DexMethod>>
diff --git a/src/main/java/com/android/tools/r8/optimize/bridgehoisting/BridgeHoisting.java b/src/main/java/com/android/tools/r8/optimize/bridgehoisting/BridgeHoisting.java
index 8e8fd00..185b0af 100644
--- a/src/main/java/com/android/tools/r8/optimize/bridgehoisting/BridgeHoisting.java
+++ b/src/main/java/com/android/tools/r8/optimize/bridgehoisting/BridgeHoisting.java
@@ -3,7 +3,6 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.optimize.bridgehoisting;
 
-import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.BottomUpClassHierarchyTraversal;
@@ -12,16 +11,16 @@
 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.graph.ImmediateProgramSubtypingInfo;
 import com.android.tools.r8.graph.MethodAccessInfoCollection;
 import com.android.tools.r8.graph.MethodResolutionResult;
 import com.android.tools.r8.graph.ProgramMethod;
-import com.android.tools.r8.graph.SubtypingInfo;
 import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackSimple;
 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.lightir.LirCode;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.MethodSignatureEquivalence;
 import com.android.tools.r8.utils.Timing;
 import com.google.common.base.Equivalence;
@@ -35,7 +34,6 @@
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;
-import java.util.TreeSet;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 
@@ -80,10 +78,11 @@
 
   public void run(ExecutorService executorService, Timing timing) throws ExecutionException {
     timing.begin("Bridge hoisting");
-    SubtypingInfo subtypingInfo = appView.appInfo().computeSubtypingInfo();
-    BottomUpClassHierarchyTraversal.forProgramClasses(appView, subtypingInfo)
+    ImmediateProgramSubtypingInfo immediateSubtypingInfo =
+        ImmediateProgramSubtypingInfo.create(appView);
+    BottomUpClassHierarchyTraversal.forProgramClasses(appView, immediateSubtypingInfo)
         .excludeInterfaces()
-        .visit(appView.appInfo().classes(), clazz -> processClass(clazz, subtypingInfo));
+        .visit(appView.appInfo().classes(), clazz -> processClass(clazz, immediateSubtypingInfo));
     if (!result.isEmpty()) {
       BridgeHoistingLens lens = result.buildLens();
       appView.rewriteWithLens(lens, executorService, timing);
@@ -113,22 +112,23 @@
     timing.end();
   }
 
-  private void processClass(DexProgramClass clazz, SubtypingInfo subtypingInfo) {
-    Set<DexType> subtypes = subtypingInfo.allImmediateSubtypes(clazz.type);
-    Set<DexProgramClass> subclasses = new TreeSet<>(Comparator.comparing(DexClass::getType));
-    for (DexType subtype : subtypes) {
-      DexProgramClass subclass = asProgramClassOrNull(appView.definitionFor(subtype));
-      if (subclass == null || !appView.testing().isEligibleForBridgeHoisting.test(subclass)) {
-        continue;
+  private void processClass(
+      DexProgramClass clazz, ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
+    List<DexProgramClass> subclasses =
+        ListUtils.sort(
+            immediateSubtypingInfo.getSubclasses(clazz), Comparator.comparing(DexClass::getType));
+    List<DexProgramClass> eligibleSubclasses = new ArrayList<>(subclasses.size());
+    for (DexProgramClass subclass : subclasses) {
+      if (appView.testing().isEligibleForBridgeHoisting.test(subclass)) {
+        eligibleSubclasses.add(subclass);
       }
-      subclasses.add(subclass);
     }
-    for (Wrapper<DexMethod> candidate : getCandidatesForHoisting(subclasses)) {
-      hoistBridgeIfPossible(candidate.get(), clazz, subclasses);
+    for (Wrapper<DexMethod> candidate : getCandidatesForHoisting(eligibleSubclasses)) {
+      hoistBridgeIfPossible(candidate.get(), clazz, eligibleSubclasses);
     }
   }
 
-  private Set<Wrapper<DexMethod>> getCandidatesForHoisting(Set<DexProgramClass> subclasses) {
+  private Set<Wrapper<DexMethod>> getCandidatesForHoisting(List<DexProgramClass> subclasses) {
     Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get();
     Set<Wrapper<DexMethod>> candidates = new HashSet<>();
     for (DexProgramClass subclass : subclasses) {
@@ -143,7 +143,7 @@
   }
 
   private void hoistBridgeIfPossible(
-      DexMethod method, DexProgramClass clazz, Set<DexProgramClass> subclasses) {
+      DexMethod method, DexProgramClass clazz, List<DexProgramClass> subclasses) {
     // If the method is defined on the parent class, we cannot hoist the bridge.
     // TODO(b/153147967): If the declared method is abstract, we could replace it by the bridge.
     //  Add a test.