diff --git a/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java b/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java
index c858748..945a773 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java
@@ -4,7 +4,8 @@
 
 package com.android.tools.r8.graph;
 
-import java.util.LinkedList;
+import java.util.ArrayDeque;
+import java.util.Deque;
 
 /* Specific subclass of AppInfo designed to support desugaring in D8. Desugaring requires a
  * minimal amount of knowledge in the overall program, provided through classpath. Basic
@@ -33,30 +34,56 @@
   }
 
   public boolean isSubtype(DexType subtype, DexType supertype) {
-    LinkedList<DexType> workList = new LinkedList<>();
-    workList.add(subtype);
+    assert subtype != null;
+    assert supertype != null;
+    return subtype == supertype || isStrictSubtypeOf(subtype, supertype);
+  }
+
+  public boolean isStrictSubtypeOf(DexType subtype, DexType supertype) {
+    assert subtype != null;
+    assert supertype != null;
+    if (subtype == supertype) {
+      return false;
+    }
+    // Treat object special: it is always the supertype even for broken hierarchies.
+    if (subtype == dexItemFactory().objectType) {
+      return false;
+    }
+    if (supertype == dexItemFactory().objectType) {
+      return true;
+    }
+    Deque<DexType> workList = new ArrayDeque<>();
+    workList.addFirst(subtype);
     while (!workList.isEmpty()) {
-      DexClass subtypeClass = definitionFor(subtype);
+      DexType type = workList.pollFirst();
+      DexClass subtypeClass = definitionFor(type);
       if (subtypeClass == null) {
-        // What to do here? Report missing type?
+        // Collect missing types for future reporting?
         continue;
       }
       if (subtypeClass.superType == supertype) {
         return true;
-      } else {
+      }
+      if (subtypeClass.superType != null) {
         workList.add(subtypeClass.superType);
       }
       for (DexType itf : subtypeClass.interfaces.values) {
         if (itf == supertype) {
           return true;
-        } else {
-          workList.add(itf);
         }
+        workList.add(itf);
       }
     }
+    // TODO(b/123506120): Report missing types when the predicate is inconclusive.
     return false;
   }
 
+  public boolean isRelatedBySubtyping(DexType type, DexType other) {
+    assert type.isClassType();
+    assert other.isClassType();
+    return isSubtype(type, other) || isSubtype(other, type);
+  }
+
   /**
    * Lookup static method following the super chain from the holder of {@code method}.
    *
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
index 71b2235..5c0e98c 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
@@ -467,90 +467,6 @@
     return !getTypeInfo(type).directSubtypes.isEmpty();
   }
 
-  public boolean isRelatedBySubtyping(DexType type, DexType other) {
-    assert type.isClassType();
-    assert other.isClassType();
-    return isSubtype(type, other) || isSubtype(other, type);
-  }
-
-  @Override
-  public boolean isSubtype(DexType subtype, DexType supertype) {
-    if (subtype == supertype || isStrictSubtypeOf(subtype, supertype)) {
-      return true;
-    }
-    if (synthesizedClasses.containsKey(subtype)) {
-      return isSynthesizedClassStrictSubtypeOf(subtype, supertype);
-    }
-    return false;
-  }
-
-  public boolean isStrictSubtypeOf(DexType subtype, DexType supertype) {
-    // For all erroneous cases, saying `no`---not a strict subtype---is conservative.
-    if (isStrictSubtypeOf(subtype, supertype, false)) {
-      return true;
-    }
-    if (synthesizedClasses.containsKey(subtype)) {
-      return isSynthesizedClassStrictSubtypeOf(subtype, supertype);
-    }
-    return false;
-  }
-
-  // Depending on optimizations, conservative answer of subtype relation may vary.
-  // Pass different `orElse` in that case.
-  private boolean isStrictSubtypeOf(DexType subtype, DexType supertype, boolean orElse) {
-    if (subtype == supertype) {
-      return false;
-    }
-    // Treat the object class special as it is always the supertype, even in the case of broken
-    // subtype chains.
-    if (subtype == dexItemFactory().objectType) {
-      return false;
-    }
-    if (supertype == dexItemFactory().objectType) {
-      return true;
-    }
-    TypeInfo subInfo = getTypeInfo(subtype);
-    if (subInfo.hierarchyLevel == INTERFACE_LEVEL) {
-      return isInterfaceSubtypeOf(subtype, supertype);
-    }
-    TypeInfo superInfo = getTypeInfo(supertype);
-    if (superInfo.hierarchyLevel == INTERFACE_LEVEL) {
-      return superInfo.directSubtypes.stream()
-          .anyMatch(superSubtype -> isSubtype(subtype, superSubtype));
-    }
-    return isSubtypeOfClass(subInfo, superInfo, orElse);
-  }
-
-  private boolean isInterfaceSubtypeOf(DexType candidate, DexType other) {
-    if (candidate == other || other == dexItemFactory().objectType) {
-      return true;
-    }
-    DexClass candidateHolder = definitionFor(candidate);
-    if (candidateHolder == null) {
-      return false;
-    }
-    for (DexType iface : candidateHolder.interfaces.values) {
-      assert getTypeInfo(iface).hierarchyLevel == INTERFACE_LEVEL;
-      if (isInterfaceSubtypeOf(iface, other)) {
-        return true;
-      }
-    }
-    return false;
-  }
-
-  private boolean isSubtypeOfClass(TypeInfo subInfo, TypeInfo superInfo, boolean orElse) {
-    if (superInfo.hierarchyLevel == UNKNOWN_LEVEL) {
-      // We have no definition for this class, hence it is not part of the hierarchy.
-      return orElse;
-    }
-    while (superInfo.hierarchyLevel < subInfo.hierarchyLevel) {
-      DexClass holder = definitionFor(subInfo.type);
-      assert holder != null && !holder.isInterface();
-      subInfo = getTypeInfo(holder.superType);
-    }
-    return subInfo.type == superInfo.type;
-  }
-
   /**
    * Apply the given function to all classes that directly extend this class.
    *