diff --git a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
index 28ca9fc..459fe7a 100644
--- a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
@@ -139,10 +139,20 @@
   }
 
   private void stripAttributes(DexProgramClass clazz) {
-    if (!keep.enclosingMethod && clazz.getEnclosingMethod() != null) {
+    // If [clazz] is mentioned by a keep rule, it could be used for reflection, and we therefore
+    // need to keep the enclosing method and inner classes attributes, if requested. In Proguard
+    // compatibility mode we keep these attributes independent of whether the given class is kept.
+    if (appInfo.isPinned(clazz.type) || options.forceProguardCompatibility) {
+      if (!keep.enclosingMethod) {
+        clazz.clearEnclosingMethod();
+      }
+      if (!keep.innerClasses) {
+        clazz.clearInnerClasses();
+      }
+    } else {
+      // These attributes are only relevant for reflection, and this class is not used for
+      // reflection. (Note that clearing these attributes can enable more vertical class merging.)
       clazz.clearEnclosingMethod();
-    }
-    if (!keep.innerClasses && !clazz.getInnerClasses().isEmpty()) {
       clazz.clearInnerClasses();
     }
   }
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..6f935ee 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;
@@ -1168,7 +1154,7 @@
     }
   }
 
-  private static class CollisionDetector {
+  private class CollisionDetector {
 
     private static final int NOT_FOUND = 1 << (Integer.SIZE - 1);
 
@@ -1193,27 +1179,30 @@
     }
 
     boolean mayCollide() {
+      timing.begin("collision detection");
       fillSeenPositions(invokes);
+      boolean result = false;
       // If the type is not used in methods at all, there cannot be any conflict.
-      if (seenPositions.isEmpty()) {
-        return false;
-      }
-      for (DexMethod method : invokes) {
-        Int2IntMap positionsMap = seenPositions.get(method.name);
-        if (positionsMap != null) {
-          int arity = method.getArity();
-          int previous = positionsMap.get(arity);
-          if (previous != NOT_FOUND) {
-            assert previous != 0;
-            int positions = computePositionsFor(method.proto, source, sourceProtoCache,
-                substituions);
-            if ((positions & previous) != 0) {
-              return true;
+      if (!seenPositions.isEmpty()) {
+        for (DexMethod method : invokes) {
+          Int2IntMap positionsMap = seenPositions.get(method.name);
+          if (positionsMap != null) {
+            int arity = method.getArity();
+            int previous = positionsMap.get(arity);
+            if (previous != NOT_FOUND) {
+              assert previous != 0;
+              int positions =
+                  computePositionsFor(method.proto, source, sourceProtoCache, substituions);
+              if ((positions & previous) != 0) {
+                result = true;
+                break;
+              }
             }
           }
         }
       }
-      return false;
+      timing.end();
+      return result;
     }
 
     private void fillSeenPositions(Collection<DexMethod> invokes) {
diff --git a/src/main/java/com/android/tools/r8/utils/Timing.java b/src/main/java/com/android/tools/r8/utils/Timing.java
index ff2aa68..e8cf59b 100644
--- a/src/main/java/com/android/tools/r8/utils/Timing.java
+++ b/src/main/java/com/android/tools/r8/utils/Timing.java
@@ -13,6 +13,8 @@
 // Finally a report is printed by:
 //     t.report();
 
+import java.util.LinkedHashMap;
+import java.util.Map;
 import java.util.Stack;
 
 public class Timing {
@@ -27,23 +29,28 @@
   static class Node {
     final String title;
 
-    final Stack<Node> sons = new Stack<>();
-    final long start_time;
-    long stop_time;
+    final Map<String, Node> children = new LinkedHashMap<>();
+    long duration = 0;
+    long start_time;
 
     Node(String title) {
       this.title = title;
       this.start_time = System.nanoTime();
-      this.stop_time = -1;
+    }
+
+    void restart() {
+      assert start_time == -1;
+      start_time = System.nanoTime();
     }
 
     void end() {
-      stop_time = System.nanoTime();
+      duration += System.nanoTime() - start_time;
+      start_time = -1;
       assert duration() >= 0;
     }
 
     long duration() {
-      return stop_time - start_time;
+      return duration;
     }
 
     @Override
@@ -66,15 +73,22 @@
         System.out.print("- ");
       }
       System.out.println(toString(top));
-      sons.forEach(p -> { p.report(depth + 1, top); });
+      children.values().forEach(p -> p.report(depth + 1, top));
     }
   }
 
 
   public void begin(String title) {
-    Node n = new Node(title);
-    stack.peek().sons.add(n);
-    stack.push(n);
+    Node parent = stack.peek();
+    Node child;
+    if (parent.children.containsKey(title)) {
+      child = parent.children.get(title);
+      child.restart();
+    } else {
+      child = new Node(title);
+      parent.children.put(title, child);
+    }
+    stack.push(child);
   }
 
   public void end() {
diff --git a/src/test/java/com/android/tools/r8/kotlin/KotlinLambdaMergingTest.java b/src/test/java/com/android/tools/r8/kotlin/KotlinLambdaMergingTest.java
index 08d43ae..e1431a6 100644
--- a/src/test/java/com/android/tools/r8/kotlin/KotlinLambdaMergingTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/KotlinLambdaMergingTest.java
@@ -31,7 +31,13 @@
       "-keepattributes InnerClasses,EnclosingMethod\n";
   private static final String KEEP_SIGNATURE_INNER_ENCLOSING =
       "-keepattributes Signature,InnerClasses,EnclosingMethod\n";
-  private Consumer<InternalOptions> optionsModifier = opts -> opts.enableClassInlining = false;
+  private Consumer<InternalOptions> optionsModifier =
+      opts -> {
+        opts.enableClassInlining = false;
+        // Ensure that enclosing method and inner class attributes are kept even on classes that are
+        // not explicitly mentioned by a keep rule.
+        opts.forceProguardCompatibility = true;
+      };
 
   abstract static class LambdaOrGroup {
     abstract boolean match(DexClass clazz);
diff --git a/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java b/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java
index c9488b4..b6a1ac6 100644
--- a/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java
@@ -18,6 +18,7 @@
 import com.android.tools.r8.utils.DexInspector.ClassSubject;
 import com.android.tools.r8.utils.DexInspector.FoundFieldSubject;
 import com.android.tools.r8.utils.DexInspector.FoundMethodSubject;
+import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.TestDescriptionWatcher;
 import com.google.common.collect.ImmutableList;
@@ -94,7 +95,8 @@
       String programFile,
       List<Path> jarLibraries,
       MinifyMode minify,
-      List<String> keepRulesFiles)
+      List<String> keepRulesFiles,
+      Consumer<InternalOptions> optionsConsumer)
       throws Exception {
     out = temp.getRoot().toPath().resolve("out.zip");
     proguardMap = temp.getRoot().toPath().resolve(DEFAULT_PROGUARD_MAP_FILE);
@@ -125,7 +127,14 @@
         throw new Unreachable();
     }
     ToolHelper.getAppBuilder(builder).addProgramFiles(Paths.get(programFile));
-    ToolHelper.runR8(builder.build(), options -> options.enableInlining = inline);
+    ToolHelper.runR8(
+        builder.build(),
+        options -> {
+          options.enableInlining = inline;
+          if (optionsConsumer != null) {
+            optionsConsumer.accept(options);
+          }
+        });
   }
 
   protected static void checkSameStructure(DexInspector ref, DexInspector inspector) {
@@ -163,6 +172,16 @@
       BiConsumer<DexInspector, DexInspector> dexComparator,
       List<String> keepRulesFiles)
       throws Exception {
+    runTest(inspection, outputComparator, dexComparator, keepRulesFiles, null);
+  }
+
+  protected void runTest(
+      Consumer<DexInspector> inspection,
+      BiConsumer<String, String> outputComparator,
+      BiConsumer<DexInspector, DexInspector> dexComparator,
+      List<String> keepRulesFiles,
+      Consumer<InternalOptions> optionsConsumer)
+      throws Exception {
     String originalDex = ToolHelper.TESTS_BUILD_DIR + name + "/classes.dex";
     String programFile;
     if (frontend == Frontend.DEX) {
@@ -183,7 +202,8 @@
               Paths.get(ToolHelper.EXAMPLES_BUILD_DIR + "shakinglib.jar"));
     }
 
-    generateTreeShakedVersion(backend, programFile, jarLibraries, minify, keepRulesFiles);
+    generateTreeShakedVersion(
+        backend, programFile, jarLibraries, minify, keepRulesFiles, optionsConsumer);
 
     if (backend == Backend.CF) {
       Path shakinglib = Paths.get(ToolHelper.EXAMPLES_BUILD_DIR, "shakinglib.jar");
diff --git a/src/test/java/com/android/tools/r8/shaking/examples/TreeShakingAnnotationremovalTest.java b/src/test/java/com/android/tools/r8/shaking/examples/TreeShakingAnnotationremovalTest.java
index d18210c..a235df5 100644
--- a/src/test/java/com/android/tools/r8/shaking/examples/TreeShakingAnnotationremovalTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/examples/TreeShakingAnnotationremovalTest.java
@@ -46,7 +46,12 @@
         TreeShakingAnnotationremovalTest::annotationRemovalHasNoInnerClassAnnotations,
         null,
         null,
-        ImmutableList.of("src/test/examples/annotationremoval/keep-rules.txt"));
+        ImmutableList.of("src/test/examples/annotationremoval/keep-rules.txt"),
+        options -> {
+          // To ensure that enclosing method and inner class attributes are kept even on classes
+          // that are not explicitly mentioned by a keep rule.
+          options.forceProguardCompatibility = true;
+        });
   }
 
   @Test
@@ -55,8 +60,12 @@
         TreeShakingAnnotationremovalTest::annotationRemovalHasAllInnerClassAnnotations,
         null,
         null,
-        ImmutableList.of(
-            "src/test/examples/annotationremoval/keep-rules-keep-innerannotation.txt"));
+        ImmutableList.of("src/test/examples/annotationremoval/keep-rules-keep-innerannotation.txt"),
+        options -> {
+          // To ensure that enclosing method and inner class attributes are kept even on classes
+          // that are not explicitly mentioned by a keep rule.
+          options.forceProguardCompatibility = true;
+        });
   }
 
   private static void annotationRemovalHasNoInnerClassAnnotations(DexInspector inspector) {