Remove MethodAccessInfoCollection

Fixes: b/326193898
Change-Id: I16f608d99bfe260aa3c667def662db45582fa244
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 8ffd211..fe43d5c 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -78,7 +78,6 @@
 import com.android.tools.r8.optimize.interfaces.analysis.CfOpenClosedInterfacesAnalysis;
 import com.android.tools.r8.optimize.proto.ProtoNormalizer;
 import com.android.tools.r8.optimize.redundantbridgeremoval.RedundantBridgeRemover;
-import com.android.tools.r8.optimize.redundantbridgeremoval.RedundantBridgeRemover.RedundantBridgeRemoverMode;
 import com.android.tools.r8.optimize.singlecaller.SingleCallerInliner;
 import com.android.tools.r8.origin.CommandLineOrigin;
 import com.android.tools.r8.origin.Origin;
@@ -487,16 +486,16 @@
       new NestReducer(appViewWithLiveness).run(executorService, timing);
 
       appView.setGraphLens(
-          MemberRebindingIdentityLensFactory.createFromAppInfo(appViewWithLiveness));
+          MemberRebindingIdentityLensFactory.create(appViewWithLiveness, executorService));
 
-      new MemberRebindingAnalysis(appViewWithLiveness).run();
+      new MemberRebindingAnalysis(appViewWithLiveness).run(executorService);
       appViewWithLiveness.appInfo().notifyMemberRebindingFinished(appViewWithLiveness);
 
       assert ArtProfileCompletenessChecker.verify(appView);
 
       AccessModifier.run(appViewWithLiveness, executorService, timing);
 
-      new RedundantBridgeRemover(appViewWithLiveness, RedundantBridgeRemoverMode.INITIAL)
+      new RedundantBridgeRemover(appViewWithLiveness)
           .setMustRetargetInvokesToTargetMethod()
           .run(executorService, timing);
 
@@ -683,14 +682,14 @@
       // Insert a member rebinding oracle in the graph to ensure that all subsequent rewritings of
       // the application has an applied oracle for looking up non-rebound references.
       MemberRebindingIdentityLens memberRebindingIdentityLens =
-          MemberRebindingIdentityLensFactory.createFromLir(appView, executorService);
+          MemberRebindingIdentityLensFactory.create(appView, executorService);
       appView.setGraphLens(memberRebindingIdentityLens);
 
       // Remove redundant bridges that have been inserted for member rebinding.
       // This can only be done if we have AppInfoWithLiveness.
       if (appView.appInfo().hasLiveness()) {
         timing.begin("Bridge remover");
-        new RedundantBridgeRemover(appView.withLiveness(), RedundantBridgeRemoverMode.FINAL)
+        new RedundantBridgeRemover(appView.withLiveness())
             .run(executorService, timing, memberRebindingIdentityLens);
         timing.end();
       } else {
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfo.java b/src/main/java/com/android/tools/r8/graph/AppInfo.java
index 3e624dd..07512e5 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfo.java
@@ -4,7 +4,6 @@
 package com.android.tools.r8.graph;
 
 import com.android.tools.r8.DesugarGraphConsumer;
-import com.android.tools.r8.classmerging.ClassMergerMode;
 import com.android.tools.r8.origin.GlobalSyntheticOrigin;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
@@ -294,8 +293,4 @@
         ? FieldResolutionResult.createSingleFieldResolutionResult(clazz, clazz, definition)
         : FieldResolutionResult.unknown();
   }
-
-  public void notifyVerticalClassMergerFinished(ClassMergerMode mode) {
-    // Intentionally empty.
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
index 56670bf..1290cc8 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -448,7 +448,7 @@
     setGraphLens(new ClearCodeRewritingGraphLens(withClassHierarchy()));
 
     MemberRebindingIdentityLens memberRebindingIdentityLens =
-        MemberRebindingIdentityLensFactory.createFromLir(withClassHierarchy(), executorService);
+        MemberRebindingIdentityLensFactory.create(withClassHierarchy(), executorService);
     setGraphLens(memberRebindingIdentityLens);
     timing.end();
   }
@@ -1113,17 +1113,6 @@
                 @Override
                 public void onJoin() {
                   appView.withClassHierarchy().setAppInfo(result);
-                  assert verifyLensRewriting();
-                }
-
-                private boolean verifyLensRewriting() {
-                  if (appView.hasLiveness()) {
-                    AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
-                    MethodAccessInfoCollection methodAccessInfoCollection =
-                        appViewWithLiveness.appInfo().getMethodAccessInfoCollection();
-                    assert methodAccessInfoCollection.verify(appViewWithLiveness);
-                  }
-                  return true;
                 }
               },
               new ThreadTask() {
diff --git a/src/main/java/com/android/tools/r8/graph/MethodAccessInfoCollection.java b/src/main/java/com/android/tools/r8/graph/MethodAccessInfoCollection.java
deleted file mode 100644
index 0701401..0000000
--- a/src/main/java/com/android/tools/r8/graph/MethodAccessInfoCollection.java
+++ /dev/null
@@ -1,508 +0,0 @@
-// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-
-package com.android.tools.r8.graph;
-
-import static com.android.tools.r8.utils.collections.ThrowingMap.isThrowingMap;
-
-import com.android.tools.r8.graph.lens.GraphLens;
-import com.android.tools.r8.graph.lens.MethodLookupResult;
-import com.android.tools.r8.ir.code.InvokeType;
-import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import com.android.tools.r8.shaking.Enqueuer;
-import com.android.tools.r8.utils.ConsumerUtils;
-import com.android.tools.r8.utils.Timing;
-import com.android.tools.r8.utils.collections.ProgramMethodSet;
-import com.android.tools.r8.utils.collections.ThrowingMap;
-import com.google.common.collect.Sets;
-import java.util.IdentityHashMap;
-import java.util.Iterator;
-import java.util.Map;
-import java.util.Map.Entry;
-import java.util.Set;
-import java.util.concurrent.ConcurrentHashMap;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Predicate;
-import java.util.function.Supplier;
-
-public class MethodAccessInfoCollection {
-
-  private Map<DexMethod, ProgramMethodSet> directInvokes;
-  private Map<DexMethod, ProgramMethodSet> interfaceInvokes;
-  private Map<DexMethod, ProgramMethodSet> staticInvokes;
-  private Map<DexMethod, ProgramMethodSet> superInvokes;
-  private Map<DexMethod, ProgramMethodSet> virtualInvokes;
-
-  private boolean fullyDestroyed = false;
-
-  private MethodAccessInfoCollection() {
-    this.directInvokes = ThrowingMap.get();
-    this.interfaceInvokes = ThrowingMap.get();
-    this.staticInvokes = ThrowingMap.get();
-    this.superInvokes = ThrowingMap.get();
-    this.virtualInvokes = ThrowingMap.get();
-    this.fullyDestroyed = true;
-  }
-
-  private MethodAccessInfoCollection(
-      Map<DexMethod, ProgramMethodSet> directInvokes,
-      Map<DexMethod, ProgramMethodSet> interfaceInvokes,
-      Map<DexMethod, ProgramMethodSet> staticInvokes,
-      Map<DexMethod, ProgramMethodSet> superInvokes,
-      Map<DexMethod, ProgramMethodSet> virtualInvokes) {
-    this.directInvokes = directInvokes;
-    this.interfaceInvokes = interfaceInvokes;
-    this.staticInvokes = staticInvokes;
-    this.superInvokes = superInvokes;
-    this.virtualInvokes = virtualInvokes;
-  }
-
-  public static ConcurrentBuilder concurrentBuilder() {
-    return new ConcurrentBuilder();
-  }
-
-  public static IdentityBuilder identityBuilder() {
-    return new IdentityBuilder();
-  }
-
-  public void destroy() {
-    assert !fullyDestroyed;
-    directInvokes = ThrowingMap.get();
-    interfaceInvokes = ThrowingMap.get();
-    staticInvokes = ThrowingMap.get();
-    superInvokes = ThrowingMap.get();
-    virtualInvokes = ThrowingMap.get();
-    fullyDestroyed = true;
-  }
-
-  public void destroyNonDirectNonSuperInvokes() {
-    interfaceInvokes = ThrowingMap.get();
-    staticInvokes = ThrowingMap.get();
-    virtualInvokes = ThrowingMap.get();
-  }
-
-  public void destroySuperInvokes() {
-    superInvokes = ThrowingMap.get();
-  }
-
-  public Modifier modifier() {
-    return new Modifier(
-        directInvokes, interfaceInvokes, staticInvokes, superInvokes, virtualInvokes);
-  }
-
-  public void forEachMethodReference(Consumer<DexMethod> method) {
-    Set<DexMethod> seen = Sets.newIdentityHashSet();
-    directInvokes.keySet().forEach(ConsumerUtils.acceptIfNotSeen(method, seen));
-    interfaceInvokes.keySet().forEach(ConsumerUtils.acceptIfNotSeen(method, seen));
-    staticInvokes.keySet().forEach(ConsumerUtils.acceptIfNotSeen(method, seen));
-    superInvokes.keySet().forEach(ConsumerUtils.acceptIfNotSeen(method, seen));
-    virtualInvokes.keySet().forEach(ConsumerUtils.acceptIfNotSeen(method, seen));
-  }
-
-  public void forEachDirectInvoke(
-      BiConsumer<? super DexMethod, ? super ProgramMethodSet> consumer) {
-    directInvokes.forEach(consumer);
-  }
-
-  public void forEachInterfaceInvoke(
-      BiConsumer<? super DexMethod, ? super ProgramMethodSet> consumer) {
-    interfaceInvokes.forEach(consumer);
-  }
-
-  public void forEachStaticInvoke(
-      BiConsumer<? super DexMethod, ? super ProgramMethodSet> consumer) {
-    staticInvokes.forEach(consumer);
-  }
-
-  public void forEachSuperInvoke(BiConsumer<? super DexMethod, ? super ProgramMethodSet> consumer) {
-    superInvokes.forEach(consumer);
-  }
-
-  public boolean hasSuperInvoke(DexMethod method) {
-    return !superInvokes.getOrDefault(method, ProgramMethodSet.empty()).isEmpty();
-  }
-
-  public void forEachSuperInvokeContext(DexMethod method, Consumer<ProgramMethod> consumer) {
-    superInvokes.getOrDefault(method, ProgramMethodSet.empty()).forEach(consumer);
-  }
-
-  public void forEachVirtualInvoke(
-      BiConsumer<? super DexMethod, ? super ProgramMethodSet> consumer) {
-    virtualInvokes.forEach(consumer);
-  }
-
-  public void forEachVirtualInvokeContext(DexMethod method, Consumer<ProgramMethod> consumer) {
-    virtualInvokes.getOrDefault(method, ProgramMethodSet.empty()).forEach(consumer);
-  }
-
-  public boolean isVirtualInvokesDestroyed() {
-    return isThrowingMap(virtualInvokes);
-  }
-
-  public MethodAccessInfoCollection rewrittenWithLens(
-      DexDefinitionSupplier definitions, GraphLens lens, Timing timing) {
-    timing.begin("Rewrite MethodAccessInfoCollection");
-    MethodAccessInfoCollection result;
-    if (fullyDestroyed) {
-      result = this;
-    } else if (isThrowingMap(interfaceInvokes)) {
-      assert isThrowingMap(staticInvokes);
-      assert isThrowingMap(virtualInvokes);
-      assert !isThrowingMap(directInvokes);
-      MethodAccessInfoCollection.Builder<?> builder = identityBuilder();
-      rewriteInvokesWithLens(builder, directInvokes, definitions, lens, InvokeType.DIRECT);
-      rewriteInvokesWithLens(builder, superInvokes, definitions, lens, InvokeType.DIRECT);
-      result = builder.build();
-      result.destroyNonDirectNonSuperInvokes();
-      if (isThrowingMap(superInvokes)) {
-        result.destroySuperInvokes();
-      }
-    } else {
-      MethodAccessInfoCollection.Builder<?> builder = identityBuilder();
-      rewriteInvokesWithLens(builder, directInvokes, definitions, lens, InvokeType.DIRECT);
-      rewriteInvokesWithLens(builder, interfaceInvokes, definitions, lens, InvokeType.INTERFACE);
-      rewriteInvokesWithLens(builder, staticInvokes, definitions, lens, InvokeType.STATIC);
-      rewriteInvokesWithLens(builder, superInvokes, definitions, lens, InvokeType.SUPER);
-      rewriteInvokesWithLens(builder, virtualInvokes, definitions, lens, InvokeType.VIRTUAL);
-      result = builder.build();
-    }
-    timing.end();
-    return result;
-  }
-
-  private static void rewriteInvokesWithLens(
-      MethodAccessInfoCollection.Builder<?> builder,
-      Map<DexMethod, ProgramMethodSet> invokes,
-      DexDefinitionSupplier definitions,
-      GraphLens lens,
-      InvokeType type) {
-    if (!isThrowingMap(invokes)) {
-      invokes.forEach(
-          (reference, contexts) -> {
-            ProgramMethodSet newContexts = contexts.rewrittenWithLens(definitions, lens);
-            for (ProgramMethod newContext : newContexts) {
-              MethodLookupResult methodLookupResult =
-                  lens.lookupMethod(reference, newContext.getReference(), type);
-              DexMethod newReference = methodLookupResult.getReference();
-              InvokeType newType = methodLookupResult.getType();
-              builder.registerInvokeInContext(newReference, newContext, newType);
-            }
-          });
-    }
-  }
-
-  public MethodAccessInfoCollection withoutPrunedContexts(PrunedItems prunedItems) {
-    if (!fullyDestroyed) {
-      pruneContexts(prunedItems, directInvokes);
-      pruneContexts(prunedItems, interfaceInvokes);
-      pruneContexts(prunedItems, staticInvokes);
-      pruneContexts(prunedItems, superInvokes);
-      pruneContexts(prunedItems, virtualInvokes);
-    }
-    return this;
-  }
-
-  private static void pruneContexts(
-      PrunedItems prunedItems, Map<DexMethod, ProgramMethodSet> invokes) {
-    if (isThrowingMap(invokes)) {
-      return;
-    }
-    invokes
-        .values()
-        .removeIf(
-            contexts -> {
-              contexts.removeIf(
-                  context -> {
-                    if (prunedItems.isRemoved(context.getReference())) {
-                      return true;
-                    }
-                    assert prunedItems.getPrunedApp().definitionFor(context.getReference()) != null
-                        : "Expected method to be present: "
-                            + context.getReference().toSourceString();
-                    return false;
-                  });
-              return contexts.isEmpty();
-            });
-  }
-
-  public MethodAccessInfoCollection withoutPrunedItems(PrunedItems prunedItems) {
-    if (!fullyDestroyed) {
-      pruneItems(prunedItems, directInvokes);
-      pruneItems(prunedItems, interfaceInvokes);
-      pruneItems(prunedItems, staticInvokes);
-      pruneItems(prunedItems, superInvokes);
-      pruneItems(prunedItems, virtualInvokes);
-    }
-    return this;
-  }
-
-  private static void pruneItems(
-      PrunedItems prunedItems, Map<DexMethod, ProgramMethodSet> invokes) {
-    if (isThrowingMap(invokes)) {
-      return;
-    }
-    Iterator<Entry<DexMethod, ProgramMethodSet>> iterator = invokes.entrySet().iterator();
-    while (iterator.hasNext()) {
-      Entry<DexMethod, ProgramMethodSet> entry = iterator.next();
-      if (prunedItems.isRemoved(entry.getKey())) {
-        iterator.remove();
-      } else {
-        ProgramMethodSet contexts = entry.getValue();
-        contexts.removeIf(
-            context -> {
-              if (prunedItems.isRemoved(context.getReference())) {
-                return true;
-              }
-              assert prunedItems.getPrunedApp().definitionFor(context.getReference()) != null
-                  : "Expected method to be present: " + context.getReference().toSourceString();
-              return false;
-            });
-        if (contexts.isEmpty()) {
-          iterator.remove();
-        }
-      }
-    }
-  }
-
-  public boolean verify(AppView<AppInfoWithLiveness> appView) {
-    assert !appView.options().getTestingOptions().enableVerticalClassMergerLensAssertion
-        || verifyNoNonResolving(appView);
-    return true;
-  }
-
-  public boolean verifyNoNonResolving(AppView<AppInfoWithLiveness> appView) {
-    verifyNoNonResolving(appView, directInvokes);
-    verifyNoNonResolving(appView, interfaceInvokes);
-    verifyNoNonResolving(appView, staticInvokes);
-    verifyNoNonResolving(appView, superInvokes);
-    verifyNoNonResolving(appView, virtualInvokes);
-    return true;
-  }
-
-  private void verifyNoNonResolving(
-      AppView<AppInfoWithLiveness> appView, Map<DexMethod, ?> invokes) {
-    if (!isThrowingMap(invokes)) {
-      for (DexMethod method : invokes.keySet()) {
-        MethodResolutionResult result =
-            appView.appInfo().unsafeResolveMethodDueToDexFormatLegacy(method);
-        assert !result.isFailedResolution()
-            : "Unexpected method that does not resolve: " + method.toSourceString();
-        assert !result.isSignaturePolymorphicResolution(method, appView.dexItemFactory())
-            : "Unexpected signature polymorphic resolution: " + method.toSourceString();
-      }
-    }
-  }
-
-  public abstract static class Builder<T extends Map<DexMethod, ProgramMethodSet>> {
-
-    private final T directInvokes;
-    private final T interfaceInvokes;
-    private final T staticInvokes;
-    private final T superInvokes;
-    private final T virtualInvokes;
-
-    private Builder(Supplier<T> factory) {
-      this(factory.get(), factory.get(), factory.get(), factory.get(), factory.get());
-    }
-
-    private Builder(
-        T directInvokes, T interfaceInvokes, T staticInvokes, T superInvokes, T virtualInvokes) {
-      this.directInvokes = directInvokes;
-      this.interfaceInvokes = interfaceInvokes;
-      this.staticInvokes = staticInvokes;
-      this.superInvokes = superInvokes;
-      this.virtualInvokes = virtualInvokes;
-    }
-
-    public T getDirectInvokes() {
-      return directInvokes;
-    }
-
-    public T getInterfaceInvokes() {
-      return interfaceInvokes;
-    }
-
-    public T getStaticInvokes() {
-      return staticInvokes;
-    }
-
-    public T getSuperInvokes() {
-      return superInvokes;
-    }
-
-    public T getVirtualInvokes() {
-      return virtualInvokes;
-    }
-
-    public boolean registerInvokeInContext(
-        DexMethod invokedMethod, ProgramMethod context, InvokeType type) {
-      switch (type) {
-        case DIRECT:
-          return registerInvokeDirectInContext(invokedMethod, context);
-        case INTERFACE:
-          return registerInvokeInterfaceInContext(invokedMethod, context);
-        case STATIC:
-          return registerInvokeStaticInContext(invokedMethod, context);
-        case SUPER:
-          return registerInvokeSuperInContext(invokedMethod, context);
-        case VIRTUAL:
-          return registerInvokeVirtualInContext(invokedMethod, context);
-        default:
-          assert false;
-          return false;
-      }
-    }
-
-    public boolean registerInvokeDirectInContext(DexMethod invokedMethod, ProgramMethod context) {
-      return registerInvokeMethodInContext(invokedMethod, context, directInvokes);
-    }
-
-    public void registerInvokeDirectInContexts(DexMethod invokedMethod, ProgramMethodSet contexts) {
-      registerInvokeMethodInContexts(invokedMethod, contexts, directInvokes);
-    }
-
-    public boolean registerInvokeInterfaceInContext(
-        DexMethod invokedMethod, ProgramMethod context) {
-      return registerInvokeMethodInContext(invokedMethod, context, interfaceInvokes);
-    }
-
-    public void registerInvokeInterfaceInContexts(
-        DexMethod invokedMethod, ProgramMethodSet contexts) {
-      registerInvokeMethodInContexts(invokedMethod, contexts, interfaceInvokes);
-    }
-
-    public boolean registerInvokeStaticInContext(DexMethod invokedMethod, ProgramMethod context) {
-      return registerInvokeMethodInContext(invokedMethod, context, staticInvokes);
-    }
-
-    public void registerInvokeStaticInContexts(DexMethod invokedMethod, ProgramMethodSet contexts) {
-      registerInvokeMethodInContexts(invokedMethod, contexts, staticInvokes);
-    }
-
-    public boolean registerInvokeSuperInContext(DexMethod invokedMethod, ProgramMethod context) {
-      return registerInvokeMethodInContext(invokedMethod, context, superInvokes);
-    }
-
-    public void registerInvokeSuperInContexts(DexMethod invokedMethod, ProgramMethodSet contexts) {
-      registerInvokeMethodInContexts(invokedMethod, contexts, superInvokes);
-    }
-
-    public boolean registerInvokeVirtualInContext(DexMethod invokedMethod, ProgramMethod context) {
-      return registerInvokeMethodInContext(invokedMethod, context, virtualInvokes);
-    }
-
-    public void registerInvokeVirtualInContexts(
-        DexMethod invokedMethod, ProgramMethodSet contexts) {
-      registerInvokeMethodInContexts(invokedMethod, contexts, virtualInvokes);
-    }
-
-    private static boolean registerInvokeMethodInContext(
-        DexMethod invokedMethod, ProgramMethod context, Map<DexMethod, ProgramMethodSet> invokes) {
-      return invokes
-          .computeIfAbsent(invokedMethod, ignore -> ProgramMethodSet.create())
-          .add(context);
-    }
-
-    private static void registerInvokeMethodInContexts(
-        DexMethod invokedMethod,
-        ProgramMethodSet contexts,
-        Map<DexMethod, ProgramMethodSet> invokes) {
-      ProgramMethodSet existingContexts = invokes.put(invokedMethod, contexts);
-      if (existingContexts != null) {
-        if (existingContexts.size() > contexts.size()) {
-          invokes.put(invokedMethod, existingContexts);
-          existingContexts.addAll(contexts);
-        } else {
-          contexts.addAll(existingContexts);
-        }
-      }
-    }
-
-    public void removeIf(Predicate<DexMethod> predicate) {
-      removeIf(predicate, directInvokes);
-      removeIf(predicate, interfaceInvokes);
-      removeIf(predicate, staticInvokes);
-      removeIf(predicate, superInvokes);
-      removeIf(predicate, virtualInvokes);
-    }
-
-    private static void removeIf(Predicate<DexMethod> predicate, Map<DexMethod, ?> invokes) {
-      invokes.keySet().removeIf(predicate);
-    }
-
-    public void removeNonResolving(
-        AppView<? extends AppInfoWithClassHierarchy> appView, Enqueuer enqueuer) {
-      // TODO(b/313365881): Should use non-legacy resolution, but this fails.
-      removeIf(
-          method -> {
-            MethodResolutionResult result =
-                appView.appInfo().unsafeResolveMethodDueToDexFormatLegacy(method);
-            if (result.isFailedResolution()
-                || result.isSignaturePolymorphicResolution(method, appView.dexItemFactory())) {
-              return true;
-            }
-            if (result.hasProgramResult()) {
-              ProgramMethod resolvedMethod = result.getResolvedProgramMethod();
-              // Guard against an unusual case where the invoke resolves to a program method but the
-              // invoke is invalid (e.g., invoke-interface to a non-interface), such that the
-              // resolved method is not retained after all.
-              if (!enqueuer.isMethodLive(resolvedMethod)
-                  && !enqueuer.isMethodTargeted(resolvedMethod)) {
-                return true;
-              }
-            }
-            return false;
-          });
-    }
-
-    public MethodAccessInfoCollection build() {
-      return new MethodAccessInfoCollection(
-          directInvokes, interfaceInvokes, staticInvokes, superInvokes, virtualInvokes);
-    }
-
-    public MethodAccessInfoCollection build(Enqueuer.Mode mode) {
-      if (mode.isInitialTreeShaking()) {
-        return build();
-      }
-      return new MethodAccessInfoCollection();
-    }
-  }
-
-  public static class ConcurrentBuilder
-      extends Builder<ConcurrentHashMap<DexMethod, ProgramMethodSet>> {
-
-    private ConcurrentBuilder() {
-      super(ConcurrentHashMap::new);
-    }
-  }
-
-  public static class IdentityBuilder
-      extends Builder<IdentityHashMap<DexMethod, ProgramMethodSet>> {
-
-    private IdentityBuilder() {
-      super(IdentityHashMap::new);
-    }
-  }
-
-  public static class Modifier extends Builder<Map<DexMethod, ProgramMethodSet>> {
-
-    private Modifier(
-        Map<DexMethod, ProgramMethodSet> directInvokes,
-        Map<DexMethod, ProgramMethodSet> interfaceInvokes,
-        Map<DexMethod, ProgramMethodSet> staticInvokes,
-        Map<DexMethod, ProgramMethodSet> superInvokes,
-        Map<DexMethod, ProgramMethodSet> virtualInvokes) {
-      super(directInvokes, interfaceInvokes, staticInvokes, superInvokes, virtualInvokes);
-    }
-
-    public void addAll(MethodAccessInfoCollection collection) {
-      collection.forEachDirectInvoke(this::registerInvokeDirectInContexts);
-      collection.forEachInterfaceInvoke(this::registerInvokeInterfaceInContexts);
-      collection.forEachStaticInvoke(this::registerInvokeStaticInContexts);
-      collection.forEachSuperInvoke(this::registerInvokeSuperInContexts);
-      collection.forEachVirtualInvoke(this::registerInvokeVirtualInContexts);
-    }
-  }
-}
diff --git a/src/main/java/com/android/tools/r8/graph/analysis/ClassInitializerAssertionEnablingAnalysis.java b/src/main/java/com/android/tools/r8/graph/analysis/ClassInitializerAssertionEnablingAnalysis.java
index 3c2e9f6..e5122b3 100644
--- a/src/main/java/com/android/tools/r8/graph/analysis/ClassInitializerAssertionEnablingAnalysis.java
+++ b/src/main/java/com/android/tools/r8/graph/analysis/ClassInitializerAssertionEnablingAnalysis.java
@@ -74,7 +74,8 @@
       EnqueuerWorklist worklist) {
     if (isUsingJavaAssertionsDisabledField(field) || isUsingKotlinAssertionsEnabledField(field)) {
       assertionHandlers.forEach(
-          assertionHandler -> worklist.enqueueTraceInvokeStaticAction(assertionHandler, context));
+          assertionHandler ->
+              worklist.enqueueTraceInvokeStaticAction(assertionHandler, context, null));
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/lens/GraphLens.java b/src/main/java/com/android/tools/r8/graph/lens/GraphLens.java
index 6bd07db..2aad1c9 100644
--- a/src/main/java/com/android/tools/r8/graph/lens/GraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/lens/GraphLens.java
@@ -394,6 +394,10 @@
     return null;
   }
 
+  public boolean isAccessModifierLens() {
+    return false;
+  }
+
   public boolean isAppliedLens() {
     return false;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java
index fc7866a..4c9ab2c 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java
@@ -173,7 +173,8 @@
                       references.generatedMessageLiteBuilderType, dynamicMethod);
                   worklist.enqueueTraceInvokeDirectAction(
                       references.generatedMessageLiteBuilderMethods.constructorMethod,
-                      dynamicMethod);
+                      dynamicMethod,
+                      null);
                 } else {
                   assert superClass.type == references.generatedMessageLiteExtendableBuilderType;
                   // Manually trace `new GeneratedMessageLite.ExtendableBuilder(DEFAULT_INSTANCE)`
@@ -182,7 +183,8 @@
                       references.generatedMessageLiteExtendableBuilderType, dynamicMethod);
                   worklist.enqueueTraceInvokeDirectAction(
                       references.generatedMessageLiteExtendableBuilderMethods.constructorMethod,
-                      dynamicMethod);
+                      dynamicMethod,
+                      null);
                 }
                 worklist.enqueueTraceStaticFieldRead(
                     references.getDefaultInstanceField(dynamicMethod.getHolder()), dynamicMethod);
diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
index f56f8bc..efc5ecb 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
@@ -4,10 +4,12 @@
 package com.android.tools.r8.optimize;
 
 import static com.android.tools.r8.utils.AndroidApiLevelUtils.isApiSafeForMemberRebinding;
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
 
 import com.android.tools.r8.androidapi.AndroidApiLevelCompute;
 import com.android.tools.r8.graph.AccessControl;
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DefaultUseRegistry;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexClassAndField;
 import com.android.tools.r8.graph.DexClassAndMethod;
@@ -18,16 +20,14 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.LibraryMethod;
-import com.android.tools.r8.graph.MethodAccessInfoCollection;
-import com.android.tools.r8.graph.MethodResolutionResult;
 import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.code.InvokeType;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import com.android.tools.r8.utils.BiForEachable;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.OptionalBool;
 import com.android.tools.r8.utils.Pair;
+import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.TriConsumer;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.google.common.collect.Iterables;
@@ -36,9 +36,10 @@
 import java.util.IdentityHashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
 import java.util.function.BiFunction;
-import java.util.function.Function;
 
 public class MemberRebindingAnalysis {
 
@@ -243,42 +244,116 @@
     return searchClass != null ? searchClass.getType() : null;
   }
 
-  private MethodResolutionResult resolveMethodOnClass(DexMethod method) {
-    return appView.appInfo().resolveMethodOnClassLegacy(method.holder, method);
+  private Map<InvokeType, NonReboundMethodAccessCollection>
+      computeNonReboundMethodAccessCollections(ExecutorService executorService)
+          throws ExecutionException {
+    Map<InvokeType, NonReboundMethodAccessCollection> nonReboundMethodAccessCollections =
+        new ConcurrentHashMap<>();
+    ThreadUtils.processItems(
+        appView.appInfo().classes(),
+        clazz -> {
+          Map<InvokeType, NonReboundMethodAccessCollection> classResult =
+              computeNonReboundMethodAccessCollections(clazz);
+          classResult.forEach(
+              (invokeType, nonReboundMethodAccessCollection) ->
+                  nonReboundMethodAccessCollections
+                      .computeIfAbsent(
+                          invokeType, ignoreKey(NonReboundMethodAccessCollection::createConcurrent))
+                      .mergeThreadLocalIntoShared(nonReboundMethodAccessCollection));
+        },
+        options.getThreadingModule(),
+        executorService);
+    return nonReboundMethodAccessCollections;
   }
 
-  private MethodResolutionResult resolveMethodOnInterface(DexMethod method) {
-    return appView.appInfo().resolveMethodOnInterfaceLegacy(method.holder, method);
+  private Map<InvokeType, NonReboundMethodAccessCollection>
+      computeNonReboundMethodAccessCollections(DexProgramClass clazz) {
+    Map<InvokeType, NonReboundMethodAccessCollection> nonReboundMethodAccessCollections =
+        new IdentityHashMap<>();
+    clazz.forEachProgramMethodMatching(
+        DexEncodedMethod::hasCode,
+        method ->
+            method.registerCodeReferences(
+                new DefaultUseRegistry<>(appView, method) {
+
+                  private final AppView<AppInfoWithLiveness> appViewWithLiveness =
+                      MemberRebindingAnalysis.this.appView;
+
+                  @Override
+                  public void registerInvokeDirect(DexMethod method) {
+                    // Intentionally empty.
+                  }
+
+                  @Override
+                  public void registerInvokeInterface(DexMethod method) {
+                    registerInvoke(
+                        InvokeType.INTERFACE,
+                        method,
+                        appViewWithLiveness
+                            .appInfo()
+                            .resolveMethodOnInterface(method.getHolderType(), method)
+                            .asSingleResolution());
+                  }
+
+                  @Override
+                  public void registerInvokeStatic(DexMethod method) {
+                    registerInvoke(
+                        InvokeType.STATIC,
+                        method,
+                        appViewWithLiveness
+                            .appInfo()
+                            .unsafeResolveMethodDueToDexFormat(method)
+                            .asSingleResolution());
+                  }
+
+                  @Override
+                  public void registerInvokeSuper(DexMethod method) {
+                    registerInvoke(
+                        InvokeType.SUPER,
+                        method,
+                        appViewWithLiveness
+                            .appInfo()
+                            .unsafeResolveMethodDueToDexFormat(method)
+                            .asSingleResolution());
+                  }
+
+                  @Override
+                  public void registerInvokeVirtual(DexMethod method) {
+                    registerInvoke(
+                        InvokeType.VIRTUAL,
+                        method,
+                        appViewWithLiveness
+                            .appInfo()
+                            .resolveMethodOnClassHolder(method)
+                            .asSingleResolution());
+                  }
+
+                  private void registerInvoke(
+                      InvokeType invokeType,
+                      DexMethod method,
+                      SingleResolutionResult<?> resolutionResult) {
+                    if (resolutionResult != null
+                        && resolutionResult
+                            .getResolvedMethod()
+                            .getReference()
+                            .isNotIdenticalTo(method)) {
+                      nonReboundMethodAccessCollections
+                          .computeIfAbsent(
+                              invokeType, ignoreKey(NonReboundMethodAccessCollection::create))
+                          .add(method, resolutionResult, getContext());
+                    }
+                  }
+                }));
+    return nonReboundMethodAccessCollections;
   }
 
-  private MethodResolutionResult resolveMethod(DexMethod method) {
-    return appView.appInfo().unsafeResolveMethodDueToDexFormatLegacy(method);
-  }
-
-  private void computeMethodRebinding(MethodAccessInfoCollection methodAccessInfoCollection) {
-    // Virtual invokes are on classes, so use class resolution.
-    computeMethodRebinding(
-        methodAccessInfoCollection::forEachVirtualInvoke,
-        this::resolveMethodOnClass,
-        InvokeType.VIRTUAL);
-    // Interface invokes are always on interfaces, so use interface resolution.
-    computeMethodRebinding(
-        methodAccessInfoCollection::forEachInterfaceInvoke,
-        this::resolveMethodOnInterface,
-        InvokeType.INTERFACE);
-    // Super invokes can be on both kinds, decide using the holder class.
-    computeMethodRebinding(
-        methodAccessInfoCollection::forEachSuperInvoke, this::resolveMethod, InvokeType.SUPER);
-    // Likewise static invokes.
-    computeMethodRebinding(
-        methodAccessInfoCollection::forEachStaticInvoke, this::resolveMethod, InvokeType.STATIC);
-  }
-
-  @SuppressWarnings("ReferenceEquality")
   private void computeMethodRebinding(
-      BiForEachable<DexMethod, ProgramMethodSet> methodsWithContexts,
-      Function<DexMethod, MethodResolutionResult> resolver,
-      InvokeType invokeType) {
+      Map<InvokeType, NonReboundMethodAccessCollection> nonReboundMethodAccessCollections) {
+    nonReboundMethodAccessCollections.forEach(this::computeMethodRebinding);
+  }
+
+  private void computeMethodRebinding(
+      InvokeType invokeType, NonReboundMethodAccessCollection nonReboundMethodAccessCollection) {
     Map<DexProgramClass, List<Pair<DexMethod, DexClassAndMethod>>> bridges =
         new IdentityHashMap<>();
     TriConsumer<DexProgramClass, DexMethod, DexClassAndMethod> addBridge =
@@ -287,28 +362,11 @@
                 .computeIfAbsent(bridgeHolder, k -> new ArrayList<>())
                 .add(new Pair<>(method, target));
 
-    methodsWithContexts.forEach(
-        (method, contexts) -> {
-          SingleResolutionResult<?> resolutionResult = resolver.apply(method).asSingleResolution();
-          if (resolutionResult == null) {
-            return;
-          }
-
-          if (method.getHolderType().isArrayType()) {
-            assert resolutionResult.getResolvedHolder().getType()
-                == appView.dexItemFactory().objectType;
-            lensBuilder.map(
-                method, resolutionResult.getResolvedMethod().getReference(), invokeType);
-            return;
-          }
-
+    nonReboundMethodAccessCollection.forEach(
+        (method, resolutionResult, contexts) -> {
           // TODO(b/128404854) Rebind to the lowest library class or program class. For now we allow
           //  searching in library for methods, but this should be done on classpath instead.
           DexClassAndMethod resolvedMethod = resolutionResult.getResolutionPair();
-          if (resolvedMethod.getReference() == method) {
-            return;
-          }
-
           DexClass initialResolutionHolder = resolutionResult.getInitialResolutionHolder();
           DexMethod bridgeMethod = null;
           if (initialResolutionHolder.isProgramClass()) {
@@ -390,7 +448,12 @@
               eventConsumer.acceptMemberRebindingBridgeMethod(
                   bridgeMethodDefinition.asProgramMethod(bridgeHolder), target);
             }
-            assert resolver.apply(method).getResolvedMethod().getReference() == bridgeMethod;
+            assert appView
+                .appInfo()
+                .unsafeResolveMethodDueToDexFormat(method)
+                .getResolvedMethod()
+                .getReference()
+                .isIdenticalTo(bridgeMethod);
           }
         });
   }
@@ -494,9 +557,11 @@
     return null;
   }
 
-  public void run() throws ExecutionException {
+  public void run(ExecutorService executorService) throws ExecutionException {
     AppInfoWithLiveness appInfo = appView.appInfo();
-    computeMethodRebinding(appInfo.getMethodAccessInfoCollection());
+    Map<InvokeType, NonReboundMethodAccessCollection> nonReboundMethodAccessCollections =
+        computeNonReboundMethodAccessCollections(executorService);
+    computeMethodRebinding(nonReboundMethodAccessCollections);
     appInfo.getFieldAccessInfoCollection().flattenAccessContexts();
     MemberRebindingLens memberRebindingLens = lensBuilder.build();
     appView.setGraphLens(memberRebindingLens);
@@ -504,4 +569,77 @@
     appView.dexItemFactory().clearTypeElementsCache();
     appView.notifyOptimizationFinishedForTesting();
   }
+
+  static class NonReboundMethodAccessCollection {
+
+    private final Map<DexMethod, NonReboundMethodAccessInfo> nonReboundMethodReferences;
+
+    private NonReboundMethodAccessCollection(
+        Map<DexMethod, NonReboundMethodAccessInfo> nonReboundMethodReferences) {
+      this.nonReboundMethodReferences = nonReboundMethodReferences;
+    }
+
+    public static NonReboundMethodAccessCollection create() {
+      return new NonReboundMethodAccessCollection(new IdentityHashMap<>());
+    }
+
+    public static NonReboundMethodAccessCollection createConcurrent() {
+      return new NonReboundMethodAccessCollection(new ConcurrentHashMap<>());
+    }
+
+    public void add(
+        DexMethod method, SingleResolutionResult<?> resolutionResult, ProgramMethod context) {
+      nonReboundMethodReferences
+          .computeIfAbsent(
+              method, ignoreKey(() -> NonReboundMethodAccessInfo.create(resolutionResult)))
+          .addContext(context);
+    }
+
+    public void forEach(
+        TriConsumer<DexMethod, SingleResolutionResult<?>, ProgramMethodSet> consumer) {
+      nonReboundMethodReferences.forEach(
+          (reference, info) -> consumer.accept(reference, info.resolutionResult, info.contexts));
+    }
+
+    public void mergeThreadLocalIntoShared(
+        NonReboundMethodAccessCollection nonReboundMethodAccessCollection) {
+      nonReboundMethodAccessCollection.forEach(
+          (method, resolutionResult, contexts) ->
+              nonReboundMethodReferences
+                  .computeIfAbsent(
+                      method,
+                      ignoreKey(
+                          () -> NonReboundMethodAccessInfo.createConcurrent(resolutionResult)))
+                  .addContexts(contexts));
+    }
+  }
+
+  static class NonReboundMethodAccessInfo {
+
+    private final SingleResolutionResult<?> resolutionResult;
+    private final ProgramMethodSet contexts;
+
+    NonReboundMethodAccessInfo(
+        SingleResolutionResult<?> resolutionResult, ProgramMethodSet contexts) {
+      this.resolutionResult = resolutionResult;
+      this.contexts = contexts;
+    }
+
+    public static NonReboundMethodAccessInfo create(SingleResolutionResult<?> resolutionResult) {
+      return new NonReboundMethodAccessInfo(resolutionResult, ProgramMethodSet.create());
+    }
+
+    public static NonReboundMethodAccessInfo createConcurrent(
+        SingleResolutionResult<?> resolutionResult) {
+      return new NonReboundMethodAccessInfo(resolutionResult, ProgramMethodSet.createConcurrent());
+    }
+
+    public void addContext(ProgramMethod context) {
+      this.contexts.add(context);
+    }
+
+    public void addContexts(ProgramMethodSet contexts) {
+      this.contexts.addAll(contexts);
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLensFactory.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLensFactory.java
index f2a6f2b..b0afc30 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLensFactory.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLensFactory.java
@@ -9,12 +9,9 @@
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexMember;
 import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.graph.FieldAccessInfoCollection;
-import com.android.tools.r8.graph.MethodAccessInfoCollection;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.graph.ReferencedMembersCollector;
 import com.android.tools.r8.graph.ReferencedMembersCollector.ReferencedMembersConsumer;
-import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ExecutionException;
@@ -22,16 +19,7 @@
 
 public class MemberRebindingIdentityLensFactory {
 
-  public static MemberRebindingIdentityLens createFromAppInfo(
-      AppView<AppInfoWithLiveness> appView) {
-    FieldAccessInfoCollection<?> fieldAccessInfoCollection =
-        appView.appInfo().getFieldAccessInfoCollection();
-    MethodAccessInfoCollection methodAccessInfoCollection =
-        appView.appInfo().getMethodAccessInfoCollection();
-    return create(appView, fieldAccessInfoCollection, methodAccessInfoCollection);
-  }
-
-  public static MemberRebindingIdentityLens createFromLir(
+  public static MemberRebindingIdentityLens create(
       AppView<? extends AppInfoWithClassHierarchy> appView, ExecutorService executorService)
       throws ExecutionException {
     MemberRebindingIdentityLens.Builder builder =
@@ -56,14 +44,4 @@
     new ReferencedMembersCollector(appView, consumer).run(executorService);
     return builder.build();
   }
-
-  public static MemberRebindingIdentityLens create(
-      AppView<? extends AppInfoWithClassHierarchy> appView,
-      FieldAccessInfoCollection<?> fieldAccessInfoCollection,
-      MethodAccessInfoCollection methodAccessInfoCollection) {
-    MemberRebindingIdentityLens.Builder builder = MemberRebindingIdentityLens.builder(appView);
-    fieldAccessInfoCollection.forEach(builder::recordNonReboundFieldAccesses);
-    methodAccessInfoCollection.forEachMethodReference(builder::recordMethodAccess);
-    return builder.build();
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/optimize/accessmodification/AccessModifierLens.java b/src/main/java/com/android/tools/r8/optimize/accessmodification/AccessModifierLens.java
index 81edcbf..e444bbe 100644
--- a/src/main/java/com/android/tools/r8/optimize/accessmodification/AccessModifierLens.java
+++ b/src/main/java/com/android/tools/r8/optimize/accessmodification/AccessModifierLens.java
@@ -46,6 +46,11 @@
   }
 
   @Override
+  public boolean isAccessModifierLens() {
+    return true;
+  }
+
+  @Override
   public DexMethod getNextMethodSignature(DexMethod method) {
     return methodMap.getOrDefault(method, method);
   }
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 185b0af..b5e328e 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
@@ -12,7 +12,6 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
 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.ir.optimize.info.OptimizationFeedbackSimple;
@@ -86,26 +85,6 @@
     if (!result.isEmpty()) {
       BridgeHoistingLens lens = result.buildLens();
       appView.rewriteWithLens(lens, executorService, timing);
-
-      // Record the invokes from the newly synthesized bridge methods in the method access info
-      // collection.
-      MethodAccessInfoCollection methodAccessInfoCollection =
-          appView.appInfo().getMethodAccessInfoCollection();
-      if (!methodAccessInfoCollection.isVirtualInvokesDestroyed()) {
-        MethodAccessInfoCollection.Modifier methodAccessInfoCollectionModifier =
-            methodAccessInfoCollection.modifier();
-        result.forEachHoistedBridge(
-            (bridge, bridgeInfo) -> {
-              if (bridgeInfo.isVirtualBridgeInfo()) {
-                DexMethod reference = bridgeInfo.asVirtualBridgeInfo().getInvokedMethod();
-                methodAccessInfoCollectionModifier.registerInvokeVirtualInContext(
-                    reference, bridge);
-              } else {
-                assert false;
-              }
-            });
-        methodAccessInfoCollection.verify(appView);
-      }
     }
 
     appView.notifyOptimizationFinishedForTesting();
diff --git a/src/main/java/com/android/tools/r8/optimize/redundantbridgeremoval/RedundantBridgeRemover.java b/src/main/java/com/android/tools/r8/optimize/redundantbridgeremoval/RedundantBridgeRemover.java
index 9c045cf..f79af09 100644
--- a/src/main/java/com/android/tools/r8/optimize/redundantbridgeremoval/RedundantBridgeRemover.java
+++ b/src/main/java/com/android/tools/r8/optimize/redundantbridgeremoval/RedundantBridgeRemover.java
@@ -40,14 +40,8 @@
 
 public class RedundantBridgeRemover {
 
-  public enum RedundantBridgeRemoverMode {
-    INITIAL,
-    FINAL
-  }
-
   private final AppView<AppInfoWithLiveness> appView;
   private final ImmediateProgramSubtypingInfo immediateSubtypingInfo;
-  private final RedundantBridgeRemoverMode mode;
   private final RedundantBridgeRemovalOptions redundantBridgeRemovalOptions;
 
   private final RedundantBridgeRemovalLens.Builder lensBuilder =
@@ -55,11 +49,9 @@
 
   private boolean mustRetargetInvokesToTargetMethod = false;
 
-  public RedundantBridgeRemover(
-      AppView<AppInfoWithLiveness> appView, RedundantBridgeRemoverMode mode) {
+  public RedundantBridgeRemover(AppView<AppInfoWithLiveness> appView) {
     this.appView = appView;
     this.immediateSubtypingInfo = ImmediateProgramSubtypingInfo.create(appView);
-    this.mode = mode;
     this.redundantBridgeRemovalOptions = appView.options().getRedundantBridgeRemovalOptions();
   }
 
@@ -167,7 +159,6 @@
       }
     }
     appView.notifyOptimizationFinishedForTesting();
-    appView.appInfo().notifyRedundantBridgeRemoverFinished(memberRebindingIdentityLens == null);
     timing.end();
   }
 
@@ -364,12 +355,6 @@
     }
 
     private boolean hasSuperInvoke(ProgramMethod method) {
-      if (mode == RedundantBridgeRemoverMode.INITIAL) {
-        return appView
-            .appInfo()
-            .getMethodAccessInfoCollection()
-            .hasSuperInvoke(method.getReference());
-      }
       return getOrCreateSuperTargets(method.getHolder()).contains(method);
     }
 
@@ -379,8 +364,7 @@
       }
       AppView<AppInfoWithLiveness> appViewWithLiveness = appView;
       superTargets = ProgramMethodSet.create();
-      WorkList<DexProgramClass> worklist =
-          WorkList.newIdentityWorkList(immediateSubtypingInfo.getSubclasses(root));
+      WorkList<DexProgramClass> worklist = WorkList.newIdentityWorkList(root);
       while (worklist.hasNext()) {
         DexProgramClass clazz = worklist.next();
         clazz.forEachProgramMethodMatching(
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 b701cdf..bcaeaa5 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -8,7 +8,6 @@
 import static com.android.tools.r8.utils.collections.ThrowingSet.isThrowingSet;
 
 import com.android.tools.r8.cf.CfVersion;
-import com.android.tools.r8.classmerging.ClassMergerMode;
 import com.android.tools.r8.features.ClassToFeatureSplitMap;
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
@@ -40,7 +39,6 @@
 import com.android.tools.r8.graph.LookupMethodTarget;
 import com.android.tools.r8.graph.LookupResult.LookupResultSuccess;
 import com.android.tools.r8.graph.LookupTarget;
-import com.android.tools.r8.graph.MethodAccessInfoCollection;
 import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
 import com.android.tools.r8.graph.ObjectAllocationInfoCollection;
 import com.android.tools.r8.graph.ObjectAllocationInfoCollectionImpl;
@@ -137,8 +135,6 @@
    */
   private final FieldAccessInfoCollectionImpl fieldAccessInfoCollection;
 
-  /** Set of all methods referenced in invokes along with their calling contexts. */
-  private final MethodAccessInfoCollection methodAccessInfoCollection;
   /** Information about instantiated classes and their allocation sites. */
   private final ObjectAllocationInfoCollectionImpl objectAllocationInfoCollection;
   /**
@@ -213,7 +209,6 @@
       Set<DexMethod> virtualMethodsTargetedByInvokeDirect,
       Set<DexMethod> liveMethods,
       FieldAccessInfoCollectionImpl fieldAccessInfoCollection,
-      MethodAccessInfoCollection methodAccessInfoCollection,
       ObjectAllocationInfoCollectionImpl objectAllocationInfoCollection,
       Map<DexCallSite, ProgramMethodSet> callSites,
       KeepInfoCollection keepInfo,
@@ -242,7 +237,6 @@
     this.virtualMethodsTargetedByInvokeDirect = virtualMethodsTargetedByInvokeDirect;
     this.liveMethods = liveMethods;
     this.fieldAccessInfoCollection = fieldAccessInfoCollection;
-    this.methodAccessInfoCollection = methodAccessInfoCollection;
     this.objectAllocationInfoCollection = objectAllocationInfoCollection;
     this.keepInfo = keepInfo;
     this.mayHaveSideEffects = mayHaveSideEffects;
@@ -279,7 +273,6 @@
         previous.virtualMethodsTargetedByInvokeDirect,
         previous.liveMethods,
         previous.fieldAccessInfoCollection,
-        previous.methodAccessInfoCollection,
         previous.objectAllocationInfoCollection,
         previous.callSites,
         previous.keepInfo,
@@ -317,7 +310,6 @@
         pruneMethods(previous.virtualMethodsTargetedByInvokeDirect, prunedItems, tasks),
         pruneMethods(previous.liveMethods, prunedItems, tasks),
         previous.fieldAccessInfoCollection.withoutPrunedItems(prunedItems),
-        previous.methodAccessInfoCollection.withoutPrunedContexts(prunedItems),
         previous.objectAllocationInfoCollection.withoutPrunedItems(prunedItems),
         pruneCallSites(previous.callSites, prunedItems),
         extendPinnedItems(previous, prunedItems.getAdditionalPinnedItems()),
@@ -446,23 +438,10 @@
     return map;
   }
 
-  @Override
-  public void notifyVerticalClassMergerFinished(ClassMergerMode mode) {
-    if (mode.isInitial()) {
-      getMethodAccessInfoCollection().destroy();
-    }
-  }
-
   public void notifyMemberRebindingFinished(AppView<AppInfoWithLiveness> appView) {
     getFieldAccessInfoCollection().restrictToProgram(appView);
   }
 
-  public void notifyRedundantBridgeRemoverFinished(boolean initial) {
-    if (initial) {
-      getMethodAccessInfoCollection().destroySuperInvokes();
-    }
-  }
-
   @Override
   public void notifyMinifierFinished() {
     liveMethods = ThrowingSet.get();
@@ -499,7 +478,6 @@
         virtualMethodsTargetedByInvokeDirect,
         liveMethods,
         fieldAccessInfoCollection,
-        methodAccessInfoCollection,
         objectAllocationInfoCollection,
         callSites,
         keepInfo,
@@ -573,7 +551,6 @@
     this.virtualMethodsTargetedByInvokeDirect = previous.virtualMethodsTargetedByInvokeDirect;
     this.liveMethods = previous.liveMethods;
     this.fieldAccessInfoCollection = previous.fieldAccessInfoCollection;
-    this.methodAccessInfoCollection = previous.methodAccessInfoCollection;
     this.objectAllocationInfoCollection = previous.objectAllocationInfoCollection;
     this.keepInfo = previous.keepInfo;
     this.mayHaveSideEffects = previous.mayHaveSideEffects;
@@ -831,11 +808,6 @@
     return fieldAccessInfoCollection;
   }
 
-  /** This method provides immutable access to `methodAccessInfoCollection`. */
-  public MethodAccessInfoCollection getMethodAccessInfoCollection() {
-    return methodAccessInfoCollection;
-  }
-
   /** This method provides immutable access to `objectAllocationInfoCollection`. */
   public ObjectAllocationInfoCollection getObjectAllocationInfoCollection() {
     return objectAllocationInfoCollection;
@@ -1128,7 +1100,6 @@
         lens.rewriteReferences(virtualMethodsTargetedByInvokeDirect),
         lens.rewriteReferences(liveMethods),
         fieldAccessInfoCollection.rewrittenWithLens(definitionSupplier, lens, timing),
-        methodAccessInfoCollection.rewrittenWithLens(definitionSupplier, lens, timing),
         objectAllocationInfoCollection.rewrittenWithLens(
             definitionSupplier, lens, appliedLens, timing),
         lens.rewriteCallSites(callSites, definitionSupplier, timing),
diff --git a/src/main/java/com/android/tools/r8/shaking/DefaultEnqueuerUseRegistry.java b/src/main/java/com/android/tools/r8/shaking/DefaultEnqueuerUseRegistry.java
index dd975f7..9e6fbf6 100644
--- a/src/main/java/com/android/tools/r8/shaking/DefaultEnqueuerUseRegistry.java
+++ b/src/main/java/com/android/tools/r8/shaking/DefaultEnqueuerUseRegistry.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.shaking;
 
 import static com.android.tools.r8.ir.desugar.records.RecordRewriterHelper.isInvokeDynamicOnRecord;
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
 
 import com.android.tools.r8.androidapi.AndroidApiLevelCompute;
 import com.android.tools.r8.dex.code.CfOrDexInstruction;
@@ -19,14 +20,26 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.code.InvokeType;
 import com.android.tools.r8.ir.code.Position;
+import com.google.common.collect.Sets;
+import java.util.IdentityHashMap;
 import java.util.ListIterator;
+import java.util.Map;
+import java.util.Set;
 
 public class DefaultEnqueuerUseRegistry extends ComputeApiLevelUseRegistry {
 
   protected final AppView<? extends AppInfoWithClassHierarchy> appViewWithClassHierarchy;
   protected final Enqueuer enqueuer;
 
+  private final Map<InvokeType, Set<DexMethod>> seenInvokes = new IdentityHashMap<>();
+  private Set<DexMethod> seenInvokeDirects = null;
+  private Set<DexMethod> seenInvokeInterfaces = null;
+  private Set<DexMethod> seenInvokeStatics = null;
+  private Set<DexMethod> seenInvokeSupers = null;
+  private Set<DexMethod> seenInvokeVirtuals = null;
+
   public DefaultEnqueuerUseRegistry(
       AppView<? extends AppInfoWithClassHierarchy> appViewWithClassHierarchy,
       ProgramMethod context,
@@ -45,6 +58,46 @@
     return getContext().getDefinition();
   }
 
+  boolean markInvokeDirectAsSeen(DexMethod invokedMethod) {
+    if (seenInvokeDirects == null) {
+      seenInvokeDirects =
+          seenInvokes.computeIfAbsent(InvokeType.DIRECT, ignoreKey(Sets::newIdentityHashSet));
+    }
+    return seenInvokeDirects.add(invokedMethod);
+  }
+
+  boolean markInvokeInterfaceAsSeen(DexMethod invokedMethod) {
+    if (seenInvokeInterfaces == null) {
+      seenInvokeInterfaces =
+          seenInvokes.computeIfAbsent(InvokeType.INTERFACE, ignoreKey(Sets::newIdentityHashSet));
+    }
+    return seenInvokeInterfaces.add(invokedMethod);
+  }
+
+  boolean markInvokeStaticAsSeen(DexMethod invokedMethod) {
+    if (seenInvokeStatics == null) {
+      seenInvokeStatics =
+          seenInvokes.computeIfAbsent(InvokeType.STATIC, ignoreKey(Sets::newIdentityHashSet));
+    }
+    return seenInvokeStatics.add(invokedMethod);
+  }
+
+  boolean markInvokeSuperAsSeen(DexMethod invokedMethod) {
+    if (seenInvokeSupers == null) {
+      seenInvokeSupers =
+          seenInvokes.computeIfAbsent(InvokeType.SUPER, ignoreKey(Sets::newIdentityHashSet));
+    }
+    return seenInvokeSupers.add(invokedMethod);
+  }
+
+  boolean markInvokeVirtualAsSeen(DexMethod invokedMethod) {
+    if (seenInvokeVirtuals == null) {
+      seenInvokeVirtuals =
+          seenInvokes.computeIfAbsent(InvokeType.VIRTUAL, ignoreKey(Sets::newIdentityHashSet));
+    }
+    return seenInvokeVirtuals.add(invokedMethod);
+  }
+
   @Override
   public void registerInliningPosition(Position position) {
     super.registerInliningPosition(position);
@@ -72,31 +125,31 @@
   @Override
   public void registerInvokeVirtual(DexMethod invokedMethod) {
     super.registerInvokeVirtual(invokedMethod);
-    enqueuer.traceInvokeVirtual(invokedMethod, getContext());
+    enqueuer.traceInvokeVirtual(invokedMethod, getContext(), this);
   }
 
   @Override
   public void registerInvokeDirect(DexMethod invokedMethod) {
     super.registerInvokeDirect(invokedMethod);
-    enqueuer.traceInvokeDirect(invokedMethod, getContext());
+    enqueuer.traceInvokeDirect(invokedMethod, getContext(), this);
   }
 
   @Override
   public void registerInvokeStatic(DexMethod invokedMethod) {
     super.registerInvokeStatic(invokedMethod);
-    enqueuer.traceInvokeStatic(invokedMethod, getContext());
+    enqueuer.traceInvokeStatic(invokedMethod, getContext(), this);
   }
 
   @Override
   public void registerInvokeInterface(DexMethod invokedMethod) {
     super.registerInvokeInterface(invokedMethod);
-    enqueuer.traceInvokeInterface(invokedMethod, getContext());
+    enqueuer.traceInvokeInterface(invokedMethod, getContext(), this);
   }
 
   @Override
   public void registerInvokeSuper(DexMethod invokedMethod) {
     super.registerInvokeSuper(invokedMethod);
-    enqueuer.traceInvokeSuper(invokedMethod, getContext());
+    enqueuer.traceInvokeSuper(invokedMethod, getContext(), this);
   }
 
   @Override
@@ -211,7 +264,7 @@
     } else {
       super.registerCallSiteBootstrapArgs(callSite, 0, callSite.bootstrapArgs.size());
     }
-    enqueuer.traceCallSite(callSite, getContext());
+    enqueuer.traceCallSite(callSite, getContext(), this);
   }
 
   @SuppressWarnings("HidingField")
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 c78d348..682b2df 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -75,7 +75,6 @@
 import com.android.tools.r8.graph.LookupMethodTarget;
 import com.android.tools.r8.graph.LookupResult;
 import com.android.tools.r8.graph.LookupTarget;
-import com.android.tools.r8.graph.MethodAccessInfoCollection;
 import com.android.tools.r8.graph.MethodResolutionResult;
 import com.android.tools.r8.graph.MethodResolutionResult.FailedResolutionResult;
 import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
@@ -197,7 +196,6 @@
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.function.BiConsumer;
-import java.util.function.BiPredicate;
 import java.util.function.Consumer;
 import java.util.function.Function;
 import java.util.function.Predicate;
@@ -283,8 +281,6 @@
 
   private final FieldAccessInfoCollectionImpl fieldAccessInfoCollection =
       new FieldAccessInfoCollectionImpl();
-  private final MethodAccessInfoCollection.IdentityBuilder methodAccessInfoCollection =
-      MethodAccessInfoCollection.identityBuilder();
   private final ObjectAllocationInfoCollectionImpl.Builder objectAllocationInfoCollection;
   private final Map<DexCallSite, ProgramMethodSet> callSites = new IdentityHashMap<>();
 
@@ -1118,16 +1114,6 @@
   // traversals.
   //
 
-  private boolean registerMethodWithTargetAndContext(
-      BiPredicate<DexMethod, ProgramMethod> registration, DexMethod method, ProgramMethod context) {
-    DexType baseHolder = method.holder.toBaseType(appView.dexItemFactory());
-    if (baseHolder.isClassType()) {
-      markTypeAsLive(baseHolder, context);
-      return registration.test(method, context);
-    }
-    return false;
-  }
-
   public boolean registerFieldRead(DexField field, ProgramMethod context) {
     return registerFieldAccess(field, context, true, false);
   }
@@ -1234,7 +1220,8 @@
     return isRead ? info.recordRead(field, context) : info.recordWrite(field, context);
   }
 
-  void traceCallSite(DexCallSite callSite, ProgramMethod context) {
+  void traceCallSite(
+      DexCallSite callSite, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
     // Do not lookup java.lang.invoke.LambdaMetafactory when compiling for DEX to avoid reporting
     // the class as missing.
     if (options.isGeneratingClassFiles() || !isLambdaMetafactoryMethod(callSite, appInfo())) {
@@ -1274,16 +1261,16 @@
     DexMethod method = implHandle.asMethod();
     switch (implHandle.type) {
       case INVOKE_STATIC:
-        traceInvokeStaticFromLambda(method, context);
+        traceInvokeStaticFromLambda(method, context, registry);
         break;
       case INVOKE_INTERFACE:
-        traceInvokeInterfaceFromLambda(method, context);
+        traceInvokeInterfaceFromLambda(method, context, registry);
         break;
       case INVOKE_INSTANCE:
-        traceInvokeVirtualFromLambda(method, context);
+        traceInvokeVirtualFromLambda(method, context, registry);
         break;
       case INVOKE_DIRECT:
-        traceInvokeDirectFromLambda(method, context);
+        traceInvokeDirectFromLambda(method, context, registry);
         break;
       case INVOKE_CONSTRUCTOR:
         traceNewInstanceFromLambda(method.holder, context);
@@ -1498,18 +1485,19 @@
         analysis -> analysis.traceExceptionGuard(type, clazz, currentMethod));
   }
 
-  void traceInvokeDirect(DexMethod invokedMethod, ProgramMethod context) {
+  void traceInvokeDirect(
+      DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
     boolean skipTracing =
         registerDeferredActionForDeadProtoBuilder(
             invokedMethod.holder,
             context,
-            () -> worklist.enqueueTraceInvokeDirectAction(invokedMethod, context));
+            () -> worklist.enqueueTraceInvokeDirectAction(invokedMethod, context, registry));
     if (skipTracing) {
       addDeadProtoTypeCandidate(invokedMethod.holder);
       return;
     }
 
-    traceInvokeDirect(invokedMethod, context, KeepReason.invokedFrom(context));
+    traceInvokeDirect(invokedMethod, context, registry, KeepReason.invokedFrom(context));
   }
 
   /** Returns true if a deferred action was registered. */
@@ -1526,51 +1514,73 @@
     return false;
   }
 
-  void traceInvokeDirectFromLambda(DexMethod invokedMethod, ProgramMethod context) {
-    traceInvokeDirect(invokedMethod, context, KeepReason.invokedFromLambdaCreatedIn(context));
+  void traceInvokeDirectFromLambda(
+      DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
+    traceInvokeDirect(
+        invokedMethod, context, registry, KeepReason.invokedFromLambdaCreatedIn(context));
   }
 
   private void traceInvokeDirect(
-      DexMethod invokedMethod, ProgramMethod context, KeepReason reason) {
-    if (!registerMethodWithTargetAndContext(
-        methodAccessInfoCollection::registerInvokeDirectInContext, invokedMethod, context)) {
+      DexMethod invokedMethod,
+      ProgramMethod context,
+      DefaultEnqueuerUseRegistry registry,
+      KeepReason reason) {
+    if (registry != null && !registry.markInvokeDirectAsSeen(invokedMethod)) {
       return;
     }
+    markTypeAsLive(invokedMethod.getHolderType(), context);
     MethodResolutionResult resolutionResult =
         handleInvokeOfDirectTarget(invokedMethod, context, reason);
     invokeAnalyses.forEach(
         analysis -> analysis.traceInvokeDirect(invokedMethod, resolutionResult, context));
   }
 
-  void traceInvokeInterface(DexMethod invokedMethod, ProgramMethod context) {
-    traceInvokeInterface(invokedMethod, context, KeepReason.invokedFrom(context));
+  void traceInvokeInterface(
+      DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
+    traceInvokeInterface(invokedMethod, context, registry, KeepReason.invokedFrom(context));
   }
 
-  void traceInvokeInterfaceFromLambda(DexMethod invokedMethod, ProgramMethod context) {
-    traceInvokeInterface(invokedMethod, context, KeepReason.invokedFromLambdaCreatedIn(context));
+  void traceInvokeInterfaceFromLambda(
+      DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
+    traceInvokeInterface(
+        invokedMethod, context, registry, KeepReason.invokedFromLambdaCreatedIn(context));
   }
 
   private void traceInvokeInterface(
-      DexMethod method, ProgramMethod context, KeepReason keepReason) {
-    if (!registerMethodWithTargetAndContext(
-        methodAccessInfoCollection::registerInvokeInterfaceInContext, method, context)) {
+      DexMethod invokedMethod,
+      ProgramMethod context,
+      DefaultEnqueuerUseRegistry registry,
+      KeepReason keepReason) {
+    if (registry != null && !registry.markInvokeInterfaceAsSeen(invokedMethod)) {
       return;
     }
-    MethodResolutionResult result = markVirtualMethodAsReachable(method, true, context, keepReason);
-    invokeAnalyses.forEach(analysis -> analysis.traceInvokeInterface(method, result, context));
+    markTypeAsLive(invokedMethod.getHolderType(), context);
+    MethodResolutionResult result =
+        markVirtualMethodAsReachable(invokedMethod, true, context, keepReason);
+    invokeAnalyses.forEach(
+        analysis -> analysis.traceInvokeInterface(invokedMethod, result, context));
   }
 
-  void traceInvokeStatic(DexMethod invokedMethod, ProgramMethod context) {
-    traceInvokeStatic(invokedMethod, context, KeepReason.invokedFrom(context));
+  void traceInvokeStatic(
+      DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
+    traceInvokeStatic(invokedMethod, context, registry, KeepReason.invokedFrom(context));
   }
 
-  void traceInvokeStaticFromLambda(DexMethod invokedMethod, ProgramMethod context) {
-    traceInvokeStatic(invokedMethod, context, KeepReason.invokedFromLambdaCreatedIn(context));
+  void traceInvokeStaticFromLambda(
+      DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
+    traceInvokeStatic(
+        invokedMethod, context, registry, KeepReason.invokedFromLambdaCreatedIn(context));
   }
 
   @SuppressWarnings("ReferenceEquality")
   private void traceInvokeStatic(
-      DexMethod invokedMethod, ProgramMethod context, KeepReason reason) {
+      DexMethod invokedMethod,
+      ProgramMethod context,
+      DefaultEnqueuerUseRegistry registry,
+      KeepReason reason) {
+    if (registry != null && !registry.markInvokeStaticAsSeen(invokedMethod)) {
+      return;
+    }
     DexItemFactory dexItemFactory = appView.dexItemFactory();
     if (dexItemFactory.classMethods.isReflectiveClassLookup(invokedMethod)
         || dexItemFactory.atomicFieldUpdaterMethods.isFieldUpdater(invokedMethod)) {
@@ -1590,37 +1600,44 @@
     if (invokedMethod == dexItemFactory.proxyMethods.newProxyInstance) {
       pendingReflectiveUses.add(context);
     }
-    if (!registerMethodWithTargetAndContext(
-        methodAccessInfoCollection::registerInvokeStaticInContext, invokedMethod, context)) {
-      return;
-    }
+    markTypeAsLive(invokedMethod.getHolderType(), context);
     MethodResolutionResult resolutionResult =
         handleInvokeOfStaticTarget(invokedMethod, context, reason);
     invokeAnalyses.forEach(
         analysis -> analysis.traceInvokeStatic(invokedMethod, resolutionResult, context));
   }
 
-  void traceInvokeSuper(DexMethod invokedMethod, ProgramMethod context) {
+  void traceInvokeSuper(
+      DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
     // We have to revisit super invokes based on the context they are found in. The same
     // method descriptor will hit different targets, depending on the context it is used in.
-    if (!registerMethodWithTargetAndContext(
-        methodAccessInfoCollection::registerInvokeSuperInContext, invokedMethod, context)) {
+    if (registry != null && !registry.markInvokeSuperAsSeen(invokedMethod)) {
       return;
     }
+    markTypeAsLive(invokedMethod.getHolderType(), context);
     worklist.enqueueMarkReachableSuperAction(invokedMethod, context);
   }
 
-  void traceInvokeVirtual(DexMethod invokedMethod, ProgramMethod context) {
-    traceInvokeVirtual(invokedMethod, context, KeepReason.invokedFrom(context));
+  void traceInvokeVirtual(
+      DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
+    traceInvokeVirtual(invokedMethod, context, registry, KeepReason.invokedFrom(context));
   }
 
-  void traceInvokeVirtualFromLambda(DexMethod invokedMethod, ProgramMethod context) {
-    traceInvokeVirtual(invokedMethod, context, KeepReason.invokedFromLambdaCreatedIn(context));
+  void traceInvokeVirtualFromLambda(
+      DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
+    traceInvokeVirtual(
+        invokedMethod, context, registry, KeepReason.invokedFromLambdaCreatedIn(context));
   }
 
   @SuppressWarnings("ReferenceEquality")
   private void traceInvokeVirtual(
-      DexMethod invokedMethod, ProgramMethod context, KeepReason reason) {
+      DexMethod invokedMethod,
+      ProgramMethod context,
+      DefaultEnqueuerUseRegistry registry,
+      KeepReason reason) {
+    if (registry != null && !registry.markInvokeVirtualAsSeen(invokedMethod)) {
+      return;
+    }
     if (invokedMethod == appView.dexItemFactory().classMethods.newInstance
         || invokedMethod == appView.dexItemFactory().constructorMethods.newInstance) {
       pendingReflectiveUses.add(context);
@@ -1630,10 +1647,7 @@
       // Revisit the current method to implicitly add -keep rule for items with reflective access.
       pendingReflectiveUses.add(context);
     }
-    if (!registerMethodWithTargetAndContext(
-        methodAccessInfoCollection::registerInvokeVirtualInContext, invokedMethod, context)) {
-      return;
-    }
+    markTypeAsLive(invokedMethod.getHolderType(), context);
     MethodResolutionResult resolutionResult =
         markVirtualMethodAsReachable(invokedMethod, false, context, reason);
     invokeAnalyses.forEach(
@@ -4396,9 +4410,6 @@
     assert fieldAccessInfoCollection.verifyMappingIsOneToOne();
     timing.end();
 
-    // Remove mappings for methods that don't resolve in the method access info collection.
-    methodAccessInfoCollection.removeNonResolving(appView, this);
-
     // Verify all references on the input app before synthesizing definitions.
     assert verifyReferences(appInfo.app());
 
@@ -4485,7 +4496,6 @@
             toDescriptorSet(liveMethods.getItems()),
             // Filter out library fields and pinned fields, because these are read by default.
             fieldAccessInfoCollection,
-            methodAccessInfoCollection.build(mode),
             objectAllocationInfoCollection.build(appInfo),
             callSites,
             keepInfo,
diff --git a/src/main/java/com/android/tools/r8/shaking/EnqueuerWorklist.java b/src/main/java/com/android/tools/r8/shaking/EnqueuerWorklist.java
index 45eee23..6d0c659 100644
--- a/src/main/java/com/android/tools/r8/shaking/EnqueuerWorklist.java
+++ b/src/main/java/com/android/tools/r8/shaking/EnqueuerWorklist.java
@@ -263,15 +263,18 @@
     private final DexMethod invokedMethod;
     // TODO(b/175854431): Avoid pushing context on worklist.
     private final ProgramMethod context;
+    private final DefaultEnqueuerUseRegistry registry;
 
-    TraceInvokeDirectAction(DexMethod invokedMethod, ProgramMethod context) {
+    TraceInvokeDirectAction(
+        DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
       this.invokedMethod = invokedMethod;
       this.context = context;
+      this.registry = registry;
     }
 
     @Override
     public void run(Enqueuer enqueuer) {
-      enqueuer.traceInvokeDirect(invokedMethod, context);
+      enqueuer.traceInvokeDirect(invokedMethod, context, registry);
     }
   }
 
@@ -279,15 +282,18 @@
     private final DexMethod invokedMethod;
     // TODO(b/175854431): Avoid pushing context on worklist.
     private final ProgramMethod context;
+    private final DefaultEnqueuerUseRegistry registry;
 
-    TraceInvokeStaticAction(DexMethod invokedMethod, ProgramMethod context) {
+    TraceInvokeStaticAction(
+        DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
       this.invokedMethod = invokedMethod;
       this.context = context;
+      this.registry = registry;
     }
 
     @Override
     public void run(Enqueuer enqueuer) {
-      enqueuer.traceInvokeStatic(invokedMethod, context);
+      enqueuer.traceInvokeStatic(invokedMethod, context, registry);
     }
   }
 
@@ -590,10 +596,10 @@
   public abstract void enqueueTraceDirectAndIndirectClassInitializers(DexProgramClass clazz);
 
   public abstract void enqueueTraceInvokeDirectAction(
-      DexMethod invokedMethod, ProgramMethod context);
+      DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry);
 
   public abstract void enqueueTraceInvokeStaticAction(
-      DexMethod invokedMethod, ProgramMethod context);
+      DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry);
 
   public abstract void enqueueTraceNewInstanceAction(DexType type, ProgramMethod context);
 
@@ -725,13 +731,15 @@
     }
 
     @Override
-    public void enqueueTraceInvokeDirectAction(DexMethod invokedMethod, ProgramMethod context) {
-      queue.add(new TraceInvokeDirectAction(invokedMethod, context));
+    public void enqueueTraceInvokeDirectAction(
+        DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
+      queue.add(new TraceInvokeDirectAction(invokedMethod, context, registry));
     }
 
     @Override
-    public void enqueueTraceInvokeStaticAction(DexMethod invokedMethod, ProgramMethod context) {
-      queue.add(new TraceInvokeStaticAction(invokedMethod, context));
+    public void enqueueTraceInvokeStaticAction(
+        DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
+      queue.add(new TraceInvokeStaticAction(invokedMethod, context, registry));
     }
 
     @Override
@@ -891,12 +899,14 @@
     }
 
     @Override
-    public void enqueueTraceInvokeDirectAction(DexMethod invokedMethod, ProgramMethod context) {
+    public void enqueueTraceInvokeDirectAction(
+        DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
       throw attemptToEnqueue("TraceInvokeDirectAction " + invokedMethod + " from " + context);
     }
 
     @Override
-    public void enqueueTraceInvokeStaticAction(DexMethod invokedMethod, ProgramMethod context) {
+    public void enqueueTraceInvokeStaticAction(
+        DexMethod invokedMethod, ProgramMethod context, DefaultEnqueuerUseRegistry registry) {
       throw attemptToEnqueue("TraceInvokeStaticAction " + invokedMethod + " from " + context);
     }
 
diff --git a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMerger.java
index 4b16a1c..943f954 100644
--- a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMerger.java
@@ -86,7 +86,6 @@
     }
     assert appView.hasVerticallyMergedClasses();
     assert ArtProfileCompletenessChecker.verify(appView);
-    appView.appInfo().notifyVerticalClassMergerFinished(mode);
     timing.end();
   }