diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index d42c68b..20e8d57 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -112,6 +112,8 @@
   private final Set<DexField> protoLiteFields = Sets.newIdentityHashSet();
   private final Set<DexItem> identifierNameStrings = Sets.newIdentityHashSet();
 
+  /** Set of method signatures used in invoke-super instructions that cannot not be resolved. */
+  private final Set<DexMethod> brokenSuperInvokes = Sets.newIdentityHashSet();
   /**
    * This map keeps a view of all virtual methods that are reachable from virtual invokes. A method
    * is reachable even if no live subtypes exist, so this is not sufficient for inclusion in the
@@ -1018,6 +1020,7 @@
     DexEncodedMethod resolutionTarget = appInfo.resolveMethod(method.holder, method)
         .asResultOfResolve();
     if (resolutionTarget == null) {
+      brokenSuperInvokes.add(method);
       reportMissingMethod(method);
       return;
     }
@@ -1517,6 +1520,8 @@
      * Set of all methods referenced in static invokes;
      */
     public final SortedSet<DexMethod> staticInvokes;
+    /** Set of method signatures used in invoke-super instructions that cannot not be resolved. */
+    public final SortedSet<DexMethod> brokenSuperInvokes;
     /**
      * Set of all items that have to be kept independent of whether they are used.
      */
@@ -1583,6 +1588,8 @@
       this.superInvokes = joinInvokedMethods(enqueuer.superInvokes, TargetWithContext::getTarget);
       this.directInvokes = joinInvokedMethods(enqueuer.directInvokes);
       this.staticInvokes = joinInvokedMethods(enqueuer.staticInvokes);
+      this.brokenSuperInvokes =
+          ImmutableSortedSet.copyOf(DexMethod::slowCompareTo, enqueuer.brokenSuperInvokes);
       this.noSideEffects = enqueuer.rootSet.noSideEffects;
       this.assumedValues = enqueuer.rootSet.assumedValues;
       this.alwaysInline = enqueuer.rootSet.alwaysInline;
@@ -1621,6 +1628,7 @@
       this.superInvokes = previous.superInvokes;
       this.directInvokes = previous.directInvokes;
       this.staticInvokes = previous.staticInvokes;
+      this.brokenSuperInvokes = previous.brokenSuperInvokes;
       this.protoLiteFields = previous.protoLiteFields;
       this.alwaysInline = previous.alwaysInline;
       this.identifierNameStrings = previous.identifierNameStrings;
@@ -1657,6 +1665,7 @@
       this.superInvokes = rewriteMethodsConservatively(previous.superInvokes, lense);
       this.directInvokes = rewriteMethodsConservatively(previous.directInvokes, lense);
       this.staticInvokes = rewriteMethodsConservatively(previous.staticInvokes, lense);
+      this.brokenSuperInvokes = rewriteMethodsConservatively(previous.brokenSuperInvokes, lense);
       this.prunedTypes = rewriteItems(previous.prunedTypes, lense::lookupType);
       // TODO(herhut): Migrate these to Descriptors, as well.
       assert lense.assertNotModified(previous.noSideEffects.keySet());
@@ -1703,6 +1712,7 @@
       this.superInvokes = previous.superInvokes;
       this.directInvokes = previous.directInvokes;
       this.staticInvokes = previous.staticInvokes;
+      this.brokenSuperInvokes = previous.brokenSuperInvokes;
       this.protoLiteFields = previous.protoLiteFields;
       this.alwaysInline = previous.alwaysInline;
       this.identifierNameStrings = previous.identifierNameStrings;
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index 222f979..a34f1b9 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -6,7 +6,6 @@
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo.ResolutionResult;
-import com.android.tools.r8.graph.DefaultUseRegistry;
 import com.android.tools.r8.graph.DexAnnotationSet;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexClass;
@@ -177,37 +176,24 @@
     extractPinnedItems(appInfo.alwaysInline, pinnedTypes, AbortReason.ALWAYS_INLINE);
     extractPinnedItems(appInfo.noSideEffects.keySet(), pinnedTypes, AbortReason.NO_SIDE_EFFECTS);
 
-    for (DexProgramClass clazz : classes) {
-      for (DexEncodedMethod method : clazz.methods()) {
-        // Avoid merging two types if this could remove a NoSuchMethodError, as illustrated by the
-        // following example. (Alternatively, it would be possible to merge A and B and rewrite the
-        // "invoke-super A.m" instruction into "invoke-super Object.m" to preserve the error. This
-        // situation should generally not occur in practice, though.)
-        //
-        //   class A {}
-        //   class B extends A {
-        //     public void m() {}
-        //   }
-        //   class C extends A {
-        //     public void m() {
-        //       invoke-super "A.m" <- should yield NoSuchMethodError, cannot merge A and B
-        //     }
-        //   }
-        if (!method.isStaticMethod()) {
-          method.registerCodeReferences(
-              new DefaultUseRegistry() {
-                @Override
-                public boolean registerInvokeSuper(DexMethod target) {
-                  DexClass targetClass = appInfo.definitionFor(target.getHolder());
-                  if (targetClass != null
-                      && targetClass.isProgramClass()
-                      && targetClass.lookupVirtualMethod(target) == null) {
-                    pinnedTypes.add(target.getHolder());
-                  }
-                  return true;
-                }
-              });
-        }
+    // Avoid merging two types if this could remove a NoSuchMethodError, as illustrated by the
+    // following example. (Alternatively, it would be possible to merge A and B and rewrite the
+    // "invoke-super A.m" instruction into "invoke-super Object.m" to preserve the error. This
+    // situation should generally not occur in practice, though.)
+    //
+    //   class A {}
+    //   class B extends A {
+    //     public void m() {}
+    //   }
+    //   class C extends A {
+    //     public void m() {
+    //       invoke-super "A.m" <- should yield NoSuchMethodError, cannot merge A and B
+    //     }
+    //   }
+    for (DexMethod signature : appInfo.brokenSuperInvokes) {
+      DexClass targetClass = appInfo.definitionFor(signature.holder);
+      if (targetClass != null && targetClass.isProgramClass()) {
+        pinnedTypes.add(signature.holder);
       }
     }
     return pinnedTypes;