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 4a85f38..35df2ef 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
@@ -584,16 +584,6 @@
     return ImmutableList.of();
   }
 
-  public Iterable<DexType> allInterfaces(DexItemFactory dexItemFactory) {
-    assert getTypeInfo(dexItemFactory.objectType).hierarchyLevel == ROOT_LEVEL;
-    return Iterables.filter(
-        getTypeInfo(dexItemFactory.objectType).directSubtypes, t -> getTypeInfo(t).isInterface());
-  }
-
-  public void forAllInterfaces(DexItemFactory factory, Consumer<DexType> f) {
-    allInterfaces(factory).forEach(f);
-  }
-
   public boolean isMissingOrHasMissingSuperType(DexType type) {
     DexClass clazz = definitionFor(type);
     return clazz == null || clazz.hasMissingSuperType(this);
diff --git a/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java b/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
index b3ac259..1f22804 100644
--- a/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
@@ -14,6 +14,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Sets;
 import java.io.PrintStream;
+import java.util.Collection;
 import java.util.Map;
 import java.util.Set;
 import java.util.function.Function;
@@ -35,7 +36,7 @@
     }
   }
 
-  FieldRenaming computeRenaming(Timing timing) {
+  FieldRenaming computeRenaming(Collection<DexClass> interfaces, Timing timing) {
     // Reserve names in all classes first. We do this in subtyping order so we do not
     // shadow a reserved field in subclasses. While there is no concept of virtual field
     // dispatch in Java, field resolution still traverses the super type chain and external
@@ -45,15 +46,14 @@
     timing.end();
     // Next, reserve field names in interfaces. These should only be static.
     timing.begin("reserve-interfaces");
-    appView
-        .appInfo()
-        .forAllInterfaces(
-            appView.dexItemFactory(), iface -> reserveNamesInSubtypes(iface, globalState));
+    for (DexClass iface : interfaces) {
+      reserveNamesInSubtypes(iface.type, globalState);
+    }
     timing.end();
     // Rename the definitions.
     timing.begin("rename-definitions");
     renameFieldsInClasses();
-    renameFieldsInInterfaces();
+    renameFieldsInInterfaces(interfaces);
     timing.end();
     // Rename the references that are not rebound to definitions for some reasons.
     timing.begin("rename-references");
@@ -120,17 +120,13 @@
     }
   }
 
-  private void renameFieldsInInterfaces() {
-    for (DexType interfaceType : appView.appInfo().allInterfaces(appView.dexItemFactory())) {
-      renameFieldsInInterface(interfaceType);
+  private void renameFieldsInInterfaces(Collection<DexClass> interfaces) {
+    for (DexClass iface : interfaces) {
+      renameFieldsInInterface(iface);
     }
   }
 
-  private void renameFieldsInInterface(DexType type) {
-    DexClass clazz = appView.definitionFor(type);
-    if (clazz == null) {
-      return;
-    }
+  private void renameFieldsInInterface(DexClass clazz) {
     assert clazz.isInterface();
     NamingState<DexType, ?> state = minifierState.getState(clazz.type);
     assert state != null;
diff --git a/src/main/java/com/android/tools/r8/naming/InterfaceMethodNameMinifier.java b/src/main/java/com/android/tools/r8/naming/InterfaceMethodNameMinifier.java
index 661711f..4ec7337 100644
--- a/src/main/java/com/android/tools/r8/naming/InterfaceMethodNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/InterfaceMethodNameMinifier.java
@@ -22,6 +22,7 @@
 import com.google.common.collect.Sets;
 import java.io.PrintStream;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashMap;
@@ -30,6 +31,7 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Map.Entry;
+import java.util.Objects;
 import java.util.Set;
 import java.util.stream.Collectors;
 
@@ -76,30 +78,30 @@
     return callSiteRenamings;
   }
 
-  private void reserveNamesInInterfaces() {
-    for (DexType type : appView.appInfo().allInterfaces(appView.dexItemFactory())) {
-      assert appView.appInfo().isInterface(type);
-      frontierState.allocateNamingStateAndReserve(type, type, null);
+  private void reserveNamesInInterfaces(Collection<DexClass> interfaces) {
+    for (DexClass iface : interfaces) {
+      assert iface.isInterface();
+      frontierState.allocateNamingStateAndReserve(iface.type, iface.type, null);
     }
   }
 
-  void assignNamesToInterfaceMethods(Timing timing) {
+  void assignNamesToInterfaceMethods(Timing timing, Collection<DexClass> interfaces) {
     // Reserve all the names that are required for interfaces.
-    reserveNamesInInterfaces();
+    reserveNamesInInterfaces(interfaces);
 
     // First compute a map from method signatures to a set of naming states for interfaces and
     // frontier states of classes that implement them. We add the frontier states so that we can
     // reserve the names for later method naming.
     timing.begin("Compute map");
-    for (DexType type : appView.appInfo().allInterfaces(appView.dexItemFactory())) {
-      assert appView.appInfo().isInterface(type);
-      DexClass clazz = appView.definitionFor(type);
-      if (clazz != null) {
-        assert clazz.isInterface();
-        Set<NamingState<DexProto, ?>> collectedStates = getReachableStates(type);
-        for (DexEncodedMethod method : shuffleMethods(clazz.methods(), appView.options())) {
-          addStatesToGlobalMapForMethod(method.method, collectedStates, type);
-        }
+    Set<DexType> allInterfaceTypes = new HashSet<>(interfaces.size());
+    for (DexClass iface : interfaces) {
+      allInterfaceTypes.add(iface.type);
+    }
+    for (DexClass iface : interfaces) {
+      Set<NamingState<DexProto, ?>> collectedStates =
+          getReachableStates(iface.type, allInterfaceTypes);
+      for (DexEncodedMethod method : shuffleMethods(iface.methods(), appView.options())) {
+        addStatesToGlobalMapForMethod(method.method, collectedStates, iface.type);
       }
     }
 
@@ -131,8 +133,8 @@
           callSites.put(callSite, implementedMethods.iterator().next().method);
           for (DexEncodedMethod method : implementedMethods) {
             DexType iface = method.method.holder;
-            assert appView.appInfo().isInterface(iface);
-            Set<NamingState<DexProto, ?>> collectedStates = getReachableStates(iface);
+            Set<NamingState<DexProto, ?>> collectedStates =
+                getReachableStates(iface, allInterfaceTypes);
             addStatesToGlobalMapForMethod(method.method, collectedStates, iface);
             callSiteMethods.add(equivalence.wrap(method.method));
           }
@@ -160,6 +162,7 @@
     // Go over every method and assign a name.
     timing.begin("Allocate names");
 
+    timing.begin("sort");
     // Sort the methods by the number of dependent states, so that we use short names for methods
     // that are referenced in many places.
     List<Wrapper<DexMethod>> interfaceMethods =
@@ -167,7 +170,9 @@
             .filter(wrapper -> unificationParent.getOrDefault(wrapper, wrapper).equals(wrapper))
             .sorted(appView.options().testing.minifier.createInterfaceMethodOrdering(this))
             .collect(Collectors.toList());
+    timing.end();
 
+    timing.begin("propogate");
     // Propagate reserved names to all states.
     List<Wrapper<DexMethod>> reservedInterfaceMethods =
         interfaceMethods.stream()
@@ -176,18 +181,24 @@
     for (Wrapper<DexMethod> key : reservedInterfaceMethods) {
       propagateReservedNames(key, unification);
     }
+    timing.end();
 
+    timing.begin("assert");
     // Verify that there is no more to propagate.
     assert reservedInterfaceMethods.stream()
         .noneMatch(key -> propagateReservedNames(key, unification));
+    timing.end();
 
+    timing.begin("assing interface");
     // Assign names to unreserved interface methods.
     for (Wrapper<DexMethod> key : interfaceMethods) {
       if (!reservedInterfaceMethods.contains(key)) {
         assignNameToInterfaceMethod(key, unification);
       }
     }
+    timing.end();
 
+    timing.begin("callsites");
     for (Entry<DexCallSite, DexMethod> entry : callSites.entrySet()) {
       DexMethod method = entry.getValue();
       DexString renamed = minifierState.getRenaming(method);
@@ -200,6 +211,7 @@
       }
     }
     timing.end();
+    timing.end(); // end compute map timing
   }
 
   private boolean propagateReservedNames(
@@ -280,6 +292,7 @@
 
   private void addStatesToGlobalMapForMethod(
       DexMethod method, Set<NamingState<DexProto, ?>> collectedStates, DexType originInterface) {
+    assert collectedStates.stream().noneMatch(Objects::isNull);
     Wrapper<DexMethod> key = equivalence.wrap(method);
     globalStateMap.computeIfAbsent(key, k -> new HashSet<>()).addAll(collectedStates);
     sourceMethodsMap.computeIfAbsent(key, k -> new HashSet<>()).add(method);
@@ -319,16 +332,14 @@
     return false;
   }
 
-  private Set<NamingState<DexProto, ?>> getReachableStates(DexType type) {
-    Set<DexType> reachableInterfaces = Sets.newIdentityHashSet();
-    reachableInterfaces.add(type);
-    collectSuperInterfaces(type, reachableInterfaces);
-    collectSubInterfaces(type, reachableInterfaces);
-
+  private Set<NamingState<DexProto, ?>> getReachableStates(DexType type, Set<DexType> allInterfaces) {
+    Set<DexType> reachableInterfaces = getReachableInterfaces(type, allInterfaces);
     Set<NamingState<DexProto, ?>> reachableStates = new HashSet<>();
     for (DexType reachableInterface : reachableInterfaces) {
       // Add the interface itself.
-      reachableStates.add(minifierState.getState(reachableInterface));
+      NamingState<DexProto, ?> ifaceState = minifierState.getState(reachableInterface);
+      assert ifaceState != null;
+      reachableStates.add(ifaceState);
 
       // And the frontiers that correspond to the classes that implement the interface.
       for (DexType frontier : appView.appInfo().allImplementsSubtypes(reachableInterface)) {
@@ -340,24 +351,36 @@
     return reachableStates;
   }
 
-  private void collectSuperInterfaces(DexType iface, Set<DexType> interfaces) {
+  private Set<DexType> getReachableInterfaces(DexType type, Set<DexType> allInterfaces) {
+    if (!allInterfaces.contains(type)) {
+      return Collections.emptySet();
+    }
+    Set<DexType> reachableInterfaces = Sets.newIdentityHashSet();
+    reachableInterfaces.add(type);
+    collectSuperInterfaces(type, reachableInterfaces, allInterfaces);
+    collectSubInterfaces(type, reachableInterfaces, allInterfaces);
+    return reachableInterfaces;
+  }
+
+  private void collectSuperInterfaces(
+      DexType iface, Set<DexType> reachable, Set<DexType> allInterfaces) {
     DexClass clazz = appView.definitionFor(iface);
-    // In cases where we lack the interface's definition, we can at least look at subtypes and
-    // tie those up to get proper naming.
     if (clazz != null) {
       for (DexType type : clazz.interfaces.values) {
-        if (interfaces.add(type)) {
-          collectSuperInterfaces(type, interfaces);
+        if (allInterfaces.contains(type) && reachable.add(type)) {
+          collectSuperInterfaces(type, reachable, allInterfaces);
         }
       }
     }
   }
 
-  private void collectSubInterfaces(DexType iface, Set<DexType> interfaces) {
+  private void collectSubInterfaces(
+      DexType iface, Set<DexType> reachableInterfaces, Set<DexType> allInterfaces) {
+    // In cases where we lack the interface's definition, we can at least look at subtypes and
+    // tie those up to get proper naming.
     for (DexType subtype : appView.appInfo().allExtendsSubtypes(iface)) {
-      assert appView.appInfo().isInterface(subtype);
-      if (interfaces.add(subtype)) {
-        collectSubInterfaces(subtype, interfaces);
+      if (allInterfaces.contains(subtype) && reachableInterfaces.add(subtype)) {
+        collectSubInterfaces(subtype, reachableInterfaces, allInterfaces);
       }
     }
   }
diff --git a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
index 15d550c..bb100cc 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
@@ -20,6 +20,7 @@
 import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.ImmutableMap;
 import java.io.PrintStream;
+import java.util.Collection;
 import java.util.HashMap;
 import java.util.IdentityHashMap;
 import java.util.Map;
@@ -128,7 +129,8 @@
     }
   }
 
-  MethodRenaming computeRenaming(Set<DexCallSite> desugaredCallSites, Timing timing) {
+  MethodRenaming computeRenaming(
+      Collection<DexClass> interfaces, Set<DexCallSite> desugaredCallSites, Timing timing) {
     // Phase 1: Reserve all the names that need to be kept and allocate linked state in the
     //          library part.
     timing.begin("Phase 1");
@@ -141,9 +143,8 @@
     InterfaceMethodNameMinifier interfaceMethodNameMinifier =
         new InterfaceMethodNameMinifier(
             appView, desugaredCallSites, equivalence, frontierState, minifierState);
-    interfaceMethodNameMinifier.assignNamesToInterfaceMethods(timing);
+    interfaceMethodNameMinifier.assignNamesToInterfaceMethods(timing, interfaces);
     timing.end();
-    // TODO(zerny): The traversals below should only traverse the reachable graph!
     // Phase 3: Assign names top-down by traversing the subtype hierarchy.
     timing.begin("Phase 3");
     assignNamesToClassesMethods(appView.dexItemFactory().objectType, false);
diff --git a/src/main/java/com/android/tools/r8/naming/Minifier.java b/src/main/java/com/android/tools/r8/naming/Minifier.java
index 6db6f61..411219b 100644
--- a/src/main/java/com/android/tools/r8/naming/Minifier.java
+++ b/src/main/java/com/android/tools/r8/naming/Minifier.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexCallSite;
+import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexString;
@@ -23,6 +24,7 @@
 import it.unimi.dsi.fastutil.objects.Object2IntLinkedOpenHashMap;
 import it.unimi.dsi.fastutil.objects.Object2IntMap;
 import java.util.Set;
+import java.util.TreeSet;
 
 public class Minifier {
 
@@ -36,6 +38,10 @@
 
   public NamingLens run(Timing timing) {
     assert appView.options().isMinifying();
+    timing.begin("ComputeInterfaces");
+    Set<DexClass> interfaces = new TreeSet<>((a, b) -> a.type.slowCompareTo(b.type));
+    interfaces.addAll(appView.appInfo().computeReachableInterfaces(desugaredCallSites));
+    timing.end();
     timing.begin("MinifyClasses");
     ClassNameMinifier classNameMinifier =
         new ClassNameMinifier(
@@ -54,7 +60,8 @@
     MemberNamingStrategy minifyMembers = new MinifierMemberNamingStrategy(appView.dexItemFactory());
     timing.begin("MinifyMethods");
     MethodRenaming methodRenaming =
-        new MethodNameMinifier(appView, minifyMembers).computeRenaming(desugaredCallSites, timing);
+        new MethodNameMinifier(appView, minifyMembers)
+            .computeRenaming(interfaces, desugaredCallSites, timing);
     timing.end();
 
     assert new MinifiedRenaming(appView, classRenaming, methodRenaming, FieldRenaming.empty())
@@ -62,7 +69,7 @@
 
     timing.begin("MinifyFields");
     FieldRenaming fieldRenaming =
-        new FieldNameMinifier(appView, minifyMembers).computeRenaming(timing);
+        new FieldNameMinifier(appView, minifyMembers).computeRenaming(interfaces, timing);
     timing.end();
 
     NamingLens lens = new MinifiedRenaming(appView, classRenaming, methodRenaming, fieldRenaming);
diff --git a/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java b/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
index caed777..1566997 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
@@ -34,6 +34,7 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.TreeSet;
 
 public class ProguardMapMinifier {
 
@@ -133,19 +134,23 @@
         classNameMinifier.computeRenaming(timing, syntheticCompanionClasses);
     timing.end();
 
+    Set<DexClass> interfaces = new TreeSet<>((a, b) -> a.type.slowCompareTo(b.type));
+    interfaces.addAll(appView.appInfo().computeReachableInterfaces(desugaredCallSites));
+
     ApplyMappingMemberNamingStrategy nameStrategy =
         new ApplyMappingMemberNamingStrategy(
             memberNames, appView.dexItemFactory(), appView.options().reporter);
     timing.begin("MinifyMethods");
     MethodRenaming methodRenaming =
-        new MethodNameMinifier(appView, nameStrategy).computeRenaming(desugaredCallSites, timing);
+        new MethodNameMinifier(appView, nameStrategy)
+            .computeRenaming(interfaces, desugaredCallSites, timing);
     // Amend the method renamings with the default interface methods.
     methodRenaming.renaming.putAll(defaultInterfaceMethodImplementationNames);
     timing.end();
 
     timing.begin("MinifyFields");
     FieldRenaming fieldRenaming =
-        new FieldNameMinifier(appView, nameStrategy).computeRenaming(timing);
+        new FieldNameMinifier(appView, nameStrategy).computeRenaming(interfaces, timing);
     timing.end();
 
     appView.options().reporter.failIfPendingErrors();
diff --git a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
index b08fad9..7ff727e 100644
--- a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
+++ b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
@@ -14,6 +14,7 @@
 import com.android.tools.r8.optimize.PublicizerLense.PublicizedLenseBuilder;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.Timing;
+import java.util.Collections;
 import java.util.LinkedHashSet;
 import java.util.Set;
 import java.util.concurrent.ExecutionException;
@@ -56,7 +57,9 @@
 
     // Phase 2: Visit classes and promote class/member to public if possible.
     timing.begin("Phase 2: promoteToPublic");
-    appView.appInfo().forAllInterfaces(appView.dexItemFactory(), this::publicizeType);
+    for (DexClass iface : appView.appInfo().computeReachableInterfaces(Collections.emptySet())) {
+      publicizeType(iface.type);
+    }
     publicizeType(appView.dexItemFactory().objectType);
     timing.end();
 
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 660de51..1a2b0e2 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -12,6 +12,7 @@
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DexTypeList;
@@ -28,8 +29,10 @@
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
 import it.unimi.dsi.fastutil.objects.Object2BooleanMap;
 import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import java.util.ArrayDeque;
 import java.util.Collection;
 import java.util.Collections;
+import java.util.Deque;
 import java.util.IdentityHashMap;
 import java.util.Map;
 import java.util.Objects;
@@ -540,6 +543,44 @@
     previous.markObsolete();
   }
 
+  public Collection<DexClass> computeReachableInterfaces(Set<DexCallSite> desugaredCallSites) {
+    Set<DexClass> interfaces = Sets.newIdentityHashSet();
+    Set<DexType> seen = Sets.newIdentityHashSet();
+    Deque<DexType> worklist = new ArrayDeque<>();
+    for (DexProgramClass clazz : classes()) {
+      worklist.add(clazz.type);
+    }
+    // TODO(b/129458850): Remove this once desugared classes are made part of the program classes.
+    for (DexCallSite callSite : desugaredCallSites) {
+      for (DexEncodedMethod method : lookupLambdaImplementedMethods(callSite)) {
+        worklist.add(method.method.holder);
+      }
+    }
+    for (DexCallSite callSite : callSites) {
+      for (DexEncodedMethod method : lookupLambdaImplementedMethods(callSite)) {
+        worklist.add(method.method.holder);
+      }
+    }
+    while (!worklist.isEmpty()) {
+      DexType type = worklist.pop();
+      if (!seen.add(type)) {
+        continue;
+      }
+      DexClass definition = definitionFor(type);
+      if (definition == null) {
+        continue;
+      }
+      if (definition.isInterface()) {
+        interfaces.add(definition);
+      }
+      if (definition.superType != null) {
+        worklist.add(definition.superType);
+      }
+      Collections.addAll(worklist, definition.interfaces.values);
+    }
+    return interfaces;
+  }
+
   public AppInfoWithLiveness withoutStaticFieldsWrites(Set<DexField> noLongerWrittenFields) {
     assert checkIfObsolete();
     if (noLongerWrittenFields.isEmpty()) {