diff --git a/src/main/java/com/android/tools/r8/graph/ClasspathOrLibraryClass.java b/src/main/java/com/android/tools/r8/graph/ClasspathOrLibraryClass.java
index d666539..d6787b8 100644
--- a/src/main/java/com/android/tools/r8/graph/ClasspathOrLibraryClass.java
+++ b/src/main/java/com/android/tools/r8/graph/ClasspathOrLibraryClass.java
@@ -15,4 +15,8 @@
   static ClasspathOrLibraryClass asClasspathOrLibraryClass(DexClass clazz) {
     return clazz != null ? clazz.asClasspathOrLibraryClass() : null;
   }
+
+  DexEncodedMethod lookupVirtualMethod(DexMethod method);
+
+  Iterable<DexEncodedMethod> virtualMethods();
 }
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index 761298d..749d320 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -365,6 +365,10 @@
     this.isLibraryMethodOverride = isLibraryMethodOverride;
   }
 
+  public void clearLibraryOverride() {
+    isLibraryMethodOverride = OptionalBool.UNKNOWN;
+  }
+
   public boolean isProgramMethod(DexDefinitionSupplier definitions) {
     if (getReference().holder.isClassType()) {
       DexClass clazz = definitions.definitionFor(getReference().holder);
diff --git a/src/main/java/com/android/tools/r8/graph/MethodResolutionResult.java b/src/main/java/com/android/tools/r8/graph/MethodResolutionResult.java
index 8c949fe..ef7586a 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodResolutionResult.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodResolutionResult.java
@@ -183,6 +183,12 @@
   public abstract LookupMethodTarget lookupVirtualDispatchTarget(
       DexClass dynamicInstance, AppInfoWithClassHierarchy appInfo);
 
+  public abstract LookupMethodTarget lookupVirtualDispatchTarget(
+      DexClass dynamicInstance,
+      AppInfoWithClassHierarchy appInfo,
+      Consumer<DexType> typeCausingFailureConsumer,
+      Consumer<? super DexEncodedMethod> methodCausingFailureConsumer);
+
   public abstract LookupTarget lookupVirtualDispatchTarget(
       LambdaDescriptor lambdaInstance,
       AppInfoWithClassHierarchy appInfo,
@@ -548,9 +554,9 @@
                 lookupVirtualDispatchTarget(
                     subClass,
                     appInfo,
-                    resolvedHolder.type,
                     resultBuilder::addTypeCausingFailure,
-                    resultBuilder::addMethodCausingFailure);
+                    resultBuilder::addMethodCausingFailure,
+                    resolvedHolder.type);
             if (lookupTarget != null) {
               incompleteness.checkDexClassAndMethod(lookupTarget);
               addVirtualDispatchTarget(lookupTarget, resolvedHolder.isInterface(), resultBuilder);
@@ -698,7 +704,21 @@
     public LookupMethodTarget lookupVirtualDispatchTarget(
         DexClass dynamicInstance, AppInfoWithClassHierarchy appInfo) {
       return lookupVirtualDispatchTarget(
-          dynamicInstance, appInfo, initialResolutionHolder.type, emptyConsumer(), emptyConsumer());
+          dynamicInstance, appInfo, emptyConsumer(), emptyConsumer());
+    }
+
+    @Override
+    public LookupMethodTarget lookupVirtualDispatchTarget(
+        DexClass dynamicInstance,
+        AppInfoWithClassHierarchy appInfo,
+        Consumer<DexType> typeCausingFailureConsumer,
+        Consumer<? super DexEncodedMethod> methodCausingFailureConsumer) {
+      return lookupVirtualDispatchTarget(
+          dynamicInstance,
+          appInfo,
+          typeCausingFailureConsumer,
+          methodCausingFailureConsumer,
+          initialResolutionHolder.type);
     }
 
     @Override
@@ -724,9 +744,9 @@
     private LookupMethodTarget lookupVirtualDispatchTarget(
         DexClass dynamicInstance,
         AppInfoWithClassHierarchy appInfo,
-        DexType resolutionHolder,
         Consumer<DexType> typeCausingFailureConsumer,
-        Consumer<? super DexEncodedMethod> methodCausingFailureConsumer) {
+        Consumer<? super DexEncodedMethod> methodCausingFailureConsumer,
+        DexType resolutionHolder) {
       assert appInfo.isSubtype(dynamicInstance.type, resolutionHolder)
           : dynamicInstance.type + " is not a subtype of " + resolutionHolder;
       // TODO(b/148591377): Enable this assertion.
@@ -1030,6 +1050,15 @@
     }
 
     @Override
+    public LookupMethodTarget lookupVirtualDispatchTarget(
+        DexClass dynamicInstance,
+        AppInfoWithClassHierarchy appInfo,
+        Consumer<DexType> typeCausingFailureConsumer,
+        Consumer<? super DexEncodedMethod> methodCausingFailureConsumer) {
+      return null;
+    }
+
+    @Override
     public LookupTarget lookupVirtualDispatchTarget(
         LambdaDescriptor lambdaInstance,
         AppInfoWithClassHierarchy appInfo,
@@ -1411,6 +1440,15 @@
     }
 
     @Override
+    public DexClassAndMethod lookupVirtualDispatchTarget(
+        DexClass dynamicInstance,
+        AppInfoWithClassHierarchy appInfo,
+        Consumer<DexType> typeCausingFailureConsumer,
+        Consumer<? super DexEncodedMethod> methodCausingFailureConsumer) {
+      throw new Unreachable("Should not be called on MultipleFieldResolutionResult");
+    }
+
+    @Override
     public LookupTarget lookupVirtualDispatchTarget(
         LambdaDescriptor lambdaInstance,
         AppInfoWithClassHierarchy appInfo,
diff --git a/src/main/java/com/android/tools/r8/graph/analysis/EnqueuerLibraryOverrideAnalysis.java b/src/main/java/com/android/tools/r8/graph/analysis/EnqueuerLibraryOverrideAnalysis.java
new file mode 100644
index 0000000..4fa9eda
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/analysis/EnqueuerLibraryOverrideAnalysis.java
@@ -0,0 +1,314 @@
+// Copyright (c) 2022, 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.analysis;
+
+import static com.android.tools.r8.utils.ConsumerUtils.emptyConsumer;
+
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.ClasspathOrLibraryClass;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.LookupMethodTarget;
+import com.android.tools.r8.graph.ObjectAllocationInfoCollectionImpl;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.shaking.Enqueuer;
+import com.android.tools.r8.utils.DepthFirstSearchWorkListBase.StatefulDepthFirstSearchWorkList;
+import com.android.tools.r8.utils.OptionalBool;
+import com.android.tools.r8.utils.TraversalContinuation;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.IdentityHashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.Function;
+
+public class EnqueuerLibraryOverrideAnalysis extends EnqueuerAnalysis {
+
+  private final Set<ClasspathOrLibraryClass> setWithSingleJavaLangObject;
+
+  private final Map<DexClass, LibraryMethodOverridesInHierarchy> libraryClassesInHierarchyCache =
+      new IdentityHashMap<>();
+  private final AppView<? extends AppInfoWithClassHierarchy> appView;
+
+  public EnqueuerLibraryOverrideAnalysis(AppView<? extends AppInfoWithClassHierarchy> appView) {
+    this.appView = appView;
+    DexClass javaLangObjectClass = appView.definitionFor(appView.dexItemFactory().objectType);
+    if (javaLangObjectClass != null && javaLangObjectClass.isNotProgramClass()) {
+      setWithSingleJavaLangObject =
+          ImmutableSet.of(javaLangObjectClass.asClasspathOrLibraryClass());
+    } else {
+      setWithSingleJavaLangObject = Collections.emptySet();
+    }
+  }
+
+  @Override
+  public void done(Enqueuer enqueuer) {
+    Set<DexProgramClass> liveProgramTypes = enqueuer.getLiveProgramTypes();
+    ObjectAllocationInfoCollectionImpl objectAllocationInfoCollection =
+        enqueuer.getObjectAllocationInfoCollection();
+    liveProgramTypes.forEach(
+        liveProgramType -> {
+          if (!objectAllocationInfoCollection.isInstantiatedDirectly(liveProgramType)) {
+            return;
+          }
+          // Abstract classes cannot be instantiated.
+          if (liveProgramType.isAbstract()) {
+            return;
+          }
+          markLibraryOverridesForProgramClass(liveProgramType);
+        });
+  }
+
+  private void markLibraryOverridesForProgramClass(DexProgramClass programClass) {
+    LibraryMethodOverridesInHierarchy libraryMethodOverridesInHierarchy =
+        ensureLibraryClassesPopulatedForProgramClass(programClass);
+    AppInfoWithClassHierarchy appInfoWithClassHierarchy = appView.appInfo();
+    libraryMethodOverridesInHierarchy.forEachOverriddenMethod(
+        (libraryClass, method) ->
+            appInfoWithClassHierarchy
+                .resolveMethodOn(libraryClass.asDexClass(), method.getReference())
+                .forEachMethodResolutionResult(
+                    result -> {
+                      LookupMethodTarget lookupTarget =
+                          result.lookupVirtualDispatchTarget(
+                              programClass,
+                              appInfoWithClassHierarchy,
+                              emptyConsumer(),
+                              failingMethod -> {
+                                DexClass holderClass =
+                                    appInfoWithClassHierarchy.definitionFor(
+                                        failingMethod.getContextType());
+                                if (holderClass != null && holderClass.isProgramClass()) {
+                                  failingMethod.setLibraryMethodOverride(OptionalBool.TRUE);
+                                }
+                              });
+                      if (lookupTarget != null) {
+                        DexEncodedMethod definition = lookupTarget.getDefinition();
+                        definition.setLibraryMethodOverride(OptionalBool.TRUE);
+                      }
+                    }));
+  }
+
+  /***
+   * Populating the library state for an instantiated program class is done by a DFS
+   * algorithm where we compute all library classes in the hierarchy and then, when doing
+   * backtracking, we check if a program method has a corresponding definition in one of its library
+   * classes. If a program method potentially overrides a library method we keep track of it for
+   * simulating virtual dispatch on it later.
+   *
+   * A special care has to be taken here when interfaces contributing to classes later in the
+   * hierarchy than the override:
+   * <pre>
+   * class ProgramA {
+   *   foo() {...}
+   * }
+   *
+   * interface Lib {
+   *   foo();
+   * }
+   *
+   * class ProgramB extends ProgramA implements Lib { }
+   * </pre>
+   *
+   * This pattern does not satisfy the DFS algorithm since ProgramB do not directly override any
+   * methods in Lib. As a consequence we always consider all interface methods to be overridden. In
+   * general this is almost always the case since we do not see many default library methods in the
+   * library.
+   *
+   * @return the computed library method override state for this program class.
+   */
+  private LibraryMethodOverridesInHierarchy ensureLibraryClassesPopulatedForProgramClass(
+      DexProgramClass clazz) {
+    new StatefulDepthFirstSearchWorkList<DexClass, LibraryMethodOverridesInHierarchy, Void>() {
+
+      @Override
+      @SuppressWarnings("ReturnValueIgnored")
+      protected TraversalContinuation<Void, LibraryMethodOverridesInHierarchy> process(
+          DFSNodeWithState<DexClass, LibraryMethodOverridesInHierarchy> node,
+          Function<DexClass, DFSNodeWithState<DexClass, LibraryMethodOverridesInHierarchy>>
+              childNodeConsumer) {
+        DexClass clazz = node.getNode();
+        LibraryMethodOverridesInHierarchy libraryMethodOverridesInHierarchy =
+            libraryClassesInHierarchyCache.get(clazz);
+        if (libraryMethodOverridesInHierarchy != null) {
+          node.setState(libraryMethodOverridesInHierarchy);
+        } else {
+          clazz.forEachImmediateSupertype(
+              superType ->
+                  appView
+                      .contextIndependentDefinitionForWithResolutionResult(superType)
+                      .forEachClassResolutionResult(childNodeConsumer::apply));
+        }
+        return TraversalContinuation.doContinue();
+      }
+
+      @Override
+      protected TraversalContinuation<Void, LibraryMethodOverridesInHierarchy> joiner(
+          DFSNodeWithState<DexClass, LibraryMethodOverridesInHierarchy> node,
+          List<DFSNodeWithState<DexClass, LibraryMethodOverridesInHierarchy>> childStates) {
+        DexClass clazz = node.getNode();
+        if (node.getState() == null) {
+          LibraryMethodOverridesInHierarchy.Builder builder =
+              LibraryMethodOverridesInHierarchy.builder();
+          childStates.forEach(childState -> builder.addParentState(childState.getState()));
+          if (clazz.isNotProgramClass()) {
+            builder.addLibraryClass(clazz.asClasspathOrLibraryClass());
+          }
+          builder.buildLibraryClasses(setWithSingleJavaLangObject);
+          if (clazz.isProgramClass()) {
+            clazz
+                .asProgramClass()
+                .virtualProgramMethods()
+                .forEach(builder::addLibraryOverridesForMethod);
+          }
+          LibraryMethodOverridesInHierarchy newState = builder.build();
+          node.setState(newState);
+          LibraryMethodOverridesInHierarchy oldState =
+              libraryClassesInHierarchyCache.put(clazz, newState);
+          assert oldState == null;
+        }
+        return TraversalContinuation.doContinue();
+      }
+    }.run(clazz);
+
+    return libraryClassesInHierarchyCache.get(clazz);
+  }
+
+  /***
+   * The LibraryMethodOverridesInHierarchy keeps track of the library classes and the potential
+   * overridden library methods for each class in the hierarchy of a class. The libraryClasses are
+   * a flattened list of all library classes that exists in the hierarchy and the overriden library
+   * methods is a map of methods that may be overridden for the current class.
+   */
+  private static class LibraryMethodOverridesInHierarchy {
+
+    private final List<LibraryMethodOverridesInHierarchy> parentStates;
+    private final Set<ClasspathOrLibraryClass> libraryClasses;
+    private final Map<DexEncodedMethod, ClasspathOrLibraryClass> overriddenLibraryMethods;
+
+    private LibraryMethodOverridesInHierarchy(
+        List<LibraryMethodOverridesInHierarchy> parentStates,
+        Set<ClasspathOrLibraryClass> libraryClasses,
+        Map<DexEncodedMethod, ClasspathOrLibraryClass> overriddenLibraryMethods) {
+      this.parentStates = parentStates;
+      this.libraryClasses = libraryClasses;
+      this.overriddenLibraryMethods = overriddenLibraryMethods;
+    }
+
+    public void forEachOverriddenMethod(
+        BiConsumer<ClasspathOrLibraryClass, DexEncodedMethod> consumer) {
+      forEachOverriddenMethod(consumer, Sets.newIdentityHashSet());
+    }
+
+    private void forEachOverriddenMethod(
+        BiConsumer<ClasspathOrLibraryClass, DexEncodedMethod> consumer,
+        Set<DexEncodedMethod> seen) {
+      overriddenLibraryMethods.forEach(
+          (method, clazz) -> {
+            if (seen.add(method)) {
+              consumer.accept(clazz, method);
+            }
+          });
+      parentStates.forEach(parentState -> parentState.forEachOverriddenMethod(consumer, seen));
+    }
+
+    public static Builder builder() {
+      return new Builder();
+    }
+
+    public static class Builder {
+
+      private Map<DexEncodedMethod, ClasspathOrLibraryClass> overriddenLibraryMethods;
+      private Set<ClasspathOrLibraryClass> libraryClasses;
+      private final List<LibraryMethodOverridesInHierarchy> parentStates = new ArrayList<>();
+      private boolean hasBuildLibraryClasses = false;
+
+      public void addParentState(LibraryMethodOverridesInHierarchy state) {
+        assert !hasBuildLibraryClasses;
+        parentStates.add(state);
+      }
+
+      public void addLibraryClass(ClasspathOrLibraryClass libraryClass) {
+        ensureLibraryClasses();
+        libraryClasses.add(libraryClass);
+        if (libraryClass.isInterface()) {
+          ensureOverriddenLibraryMethods();
+          libraryClass
+              .virtualMethods()
+              .forEach(
+                  virtualMethod ->
+                      overriddenLibraryMethods.putIfAbsent(virtualMethod, libraryClass));
+        }
+      }
+
+      private void ensureLibraryClasses() {
+        if (libraryClasses == null) {
+          libraryClasses = new LinkedHashSet<>();
+        }
+      }
+
+      private void buildLibraryClasses(Set<ClasspathOrLibraryClass> setWithSingleJavaLangObject) {
+        if (libraryClasses != null) {
+          parentStates.forEach(parentState -> libraryClasses.addAll(parentState.libraryClasses));
+        } else if (parentStates.size() == 1) {
+          libraryClasses = parentStates.get(0).libraryClasses;
+        } else {
+          libraryClasses = new LinkedHashSet<>();
+          for (LibraryMethodOverridesInHierarchy parentState : parentStates) {
+            libraryClasses.addAll(parentState.libraryClasses);
+          }
+          if (libraryClasses.size() == 1) {
+            assert libraryClasses.equals(setWithSingleJavaLangObject);
+            libraryClasses = setWithSingleJavaLangObject;
+          }
+        }
+        hasBuildLibraryClasses = true;
+      }
+
+      private void addLibraryOverridesForMethod(ProgramMethod method) {
+        assert hasBuildLibraryClasses;
+        DexMethod reference = method.getReference();
+        libraryClasses.forEach(
+            libraryClass -> {
+              if (libraryClass.isInterface()) {
+                // All interface methods are already added when visiting.
+                return;
+              }
+              DexEncodedMethod libraryMethod = libraryClass.lookupVirtualMethod(reference);
+              if (libraryMethod != null) {
+                addOverriddenMethod(libraryClass, libraryMethod);
+              }
+            });
+      }
+
+      private void addOverriddenMethod(ClasspathOrLibraryClass clazz, DexEncodedMethod method) {
+        ensureOverriddenLibraryMethods();
+        ClasspathOrLibraryClass existing = overriddenLibraryMethods.put(method, clazz);
+        assert existing == null;
+      }
+
+      private void ensureOverriddenLibraryMethods() {
+        if (overriddenLibraryMethods == null) {
+          overriddenLibraryMethods = new IdentityHashMap<>();
+        }
+      }
+
+      public LibraryMethodOverridesInHierarchy build() {
+        return new LibraryMethodOverridesInHierarchy(
+            parentStates,
+            libraryClasses,
+            overriddenLibraryMethods == null ? Collections.emptyMap() : overriddenLibraryMethods);
+      }
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java
index 5f0bea9..5377ecb 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java
@@ -608,11 +608,6 @@
       }
 
       @Override
-      protected List<Void> getFinalStateForRoots(Collection<? extends StringBuilderNode> roots) {
-        return null;
-      }
-
-      @Override
       public TraversalContinuation<Void, Void> joiner(DFSNode<StringBuilderNode> node) {
         StringBuilderNode node1 = node.getNode();
         processingOrder.add(node1);
diff --git a/src/main/java/com/android/tools/r8/optimize/RedundantBridgeRemover.java b/src/main/java/com/android/tools/r8/optimize/RedundantBridgeRemover.java
index 5cbb1b6..222ead9 100644
--- a/src/main/java/com/android/tools/r8/optimize/RedundantBridgeRemover.java
+++ b/src/main/java/com/android/tools/r8/optimize/RedundantBridgeRemover.java
@@ -21,6 +21,7 @@
 import com.android.tools.r8.optimize.redundantbridgeremoval.RedundantBridgeRemovalLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.KeepMethodInfo;
+import com.android.tools.r8.utils.OptionalBool;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import java.util.Map;
 import java.util.concurrent.ConcurrentHashMap;
@@ -140,6 +141,7 @@
           ProgramMethodSet bridgesToRemoveForClass = ProgramMethodSet.create();
           clazz.forEachProgramMethod(
               method -> {
+                DexEncodedMethod definition = method.getDefinition();
                 KeepMethodInfo keepInfo = appView.getKeepInfo(method);
                 if (!keepInfo.isShrinkingAllowed(appView.options())
                     || !keepInfo.isOptimizationAllowed(appView.options())) {
@@ -155,6 +157,12 @@
                   // Record that the redundant bridge should be removed.
                   bridgesToRemoveForClass.add(method);
 
+                  // When removing a bridge we have to mark if the target is a library override.
+                  if (definition.isLibraryMethodOverride().isTrue()) {
+                    target.getDefinition().clearLibraryOverride();
+                    target.getDefinition().setLibraryMethodOverride(OptionalBool.TRUE);
+                  }
+
                   // Rewrite invokes to the bridge to the target if it is accessible.
                   // TODO(b/173751869): Consider enabling this for constructors as well.
                   // TODO(b/245882297): Refine these visibility checks so that we also rewrite when
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 6c5c07b..5131441 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -95,6 +95,7 @@
 import com.android.tools.r8.graph.analysis.EnqueuerFieldAccessAnalysis;
 import com.android.tools.r8.graph.analysis.EnqueuerInstanceOfAnalysis;
 import com.android.tools.r8.graph.analysis.EnqueuerInvokeAnalysis;
+import com.android.tools.r8.graph.analysis.EnqueuerLibraryOverrideAnalysis;
 import com.android.tools.r8.graph.analysis.GetArrayOfMissingTypeVerifyErrorWorkaround;
 import com.android.tools.r8.graph.analysis.InvokeVirtualToInterfaceVerifyErrorWorkaround;
 import com.android.tools.r8.ir.analysis.proto.ProtoEnqueuerUseRegistry;
@@ -537,6 +538,10 @@
     return graphReporter;
   }
 
+  public Set<DexProgramClass> getLiveProgramTypes() {
+    return liveTypes.getItems();
+  }
+
   private EnqueuerUseRegistryFactory createUseRegistryFactory() {
     if (mode.isFinalTreeShaking()) {
       return appView.withGeneratedMessageLiteShrinker(
@@ -681,17 +686,6 @@
     return definitionFor(type, context, this::recordNonProgramClass, this::reportMissingClass);
   }
 
-  public DexLibraryClass definitionForLibraryClassOrIgnore(DexType type) {
-    assert type.isClassType();
-    ClassResolutionResult classResolutionResult =
-        appInfo().contextIndependentDefinitionForWithResolutionResult(type);
-    return classResolutionResult.hasClassResolutionResult()
-            && !classResolutionResult.isMultipleClassResolutionResult()
-        ? DexLibraryClass.asLibraryClassOrNull(
-            classResolutionResult.toSingleClassWithProgramOverLibrary())
-        : null;
-  }
-
   public boolean hasAlternativeLibraryDefinition(DexProgramClass programClass) {
     ClassResolutionResult classResolutionResult =
         internalDefinitionFor(
@@ -2871,10 +2865,7 @@
             } else {
               markLibraryAndClasspathMethodOverridesAsLive(instantiation, clazz);
             }
-            if (clazz.superType != null) {
-              worklist.addIfNotSeen(clazz.superType);
-            }
-            worklist.addIfNotSeen(clazz.interfaces);
+            clazz.forEachImmediateSupertype(worklist::addIfNotSeen);
           });
     }
   }
@@ -2971,7 +2962,7 @@
       // class comment of DesugaredLibraryAPIConverter and vivifiedType logic.
       // In the first enqueuer phase, the signature has not been desugared, so firstResolution
       // maintains the library override. In the second enqueuer phase, the signature has been
-      // desugared, and the second resolution maintains the the library override.
+      // desugared, and the second resolution maintains the library override.
       if (instantiation.isClass()
           && appView.typeRewriter.hasRewrittenTypeInSignature(
               method.getReference().proto, appView)) {
@@ -3003,11 +2994,6 @@
         method ->
             graphReporter.reportLibraryMethodAsLive(
                 instantiation, method, libraryOrClasspathClass));
-    if (instantiation.isClass()) {
-      // TODO(b/149976493): We need to mark these for lambdas too!
-      markOverridesAsLibraryMethodOverrides(
-          instantiation.asClass(), lookup.asMethodTarget().getDefinition().getReference());
-    }
   }
 
   private void markOverridesAsLibraryMethodOverrides(
@@ -3620,6 +3606,9 @@
     if (options.apiModelingOptions().enableLibraryApiModeling) {
       registerAnalysis(new ApiModelAnalysis(appView));
     }
+    if (!mode.isMainDexTracing()) {
+      registerAnalysis(new EnqueuerLibraryOverrideAnalysis(appView));
+    }
 
     // Transfer the minimum keep info from the root set into the Enqueuer state.
     includeMinimumKeepInfo(rootSet);
@@ -3642,8 +3631,8 @@
     enqueueAllIfNotShrinking();
     trace(executorService, timing);
     options.reporter.failIfPendingErrors();
-    finalizeLibraryMethodOverrideInformation();
     analyses.forEach(analyses -> analyses.done(this));
+    finalizeLibraryMethodOverrideInformation();
     assert verifyKeptGraph();
     if (mode.isInitialTreeShaking() && forceProguardCompatibility) {
       appView.setProguardCompatibilityActions(proguardCompatibilityActionsBuilder.build());
diff --git a/src/test/java/com/android/tools/r8/regress/b149890887/MissingLibraryTargetTest.java b/src/test/java/com/android/tools/r8/regress/b149890887/MissingLibraryTargetTest.java
index 1dab89f..8c4d936 100644
--- a/src/test/java/com/android/tools/r8/regress/b149890887/MissingLibraryTargetTest.java
+++ b/src/test/java/com/android/tools/r8/regress/b149890887/MissingLibraryTargetTest.java
@@ -61,7 +61,7 @@
         .addKeepMainRule(MAIN)
         .addClasspathClasses(LIBRARY)
         .setMinApi(parameters.getApiLevel())
-        .addKeepRules("-dontwarn")
+        .addDontWarn(MissingLibraryClass.class)
         .compile()
         .addRunClasspathFiles(runtimeClasspath())
         .run(parameters.getRuntime(), MAIN)
diff --git a/src/test/java/com/android/tools/r8/resolution/duplicatedefinitions/MaximallySpecificMultipleOnCompleteTest.java b/src/test/java/com/android/tools/r8/resolution/duplicatedefinitions/MaximallySpecificMultipleOnCompleteTest.java
index e220b6e..f452c4b 100644
--- a/src/test/java/com/android/tools/r8/resolution/duplicatedefinitions/MaximallySpecificMultipleOnCompleteTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/duplicatedefinitions/MaximallySpecificMultipleOnCompleteTest.java
@@ -139,7 +139,6 @@
     @Override
     default void foo() {
       System.out.println("J_Program::foo");
-      ;
     }
   }
 
@@ -147,7 +146,6 @@
     @Override
     default void foo() {
       System.out.println("J_Library::foo");
-      ;
     }
   }
 
diff --git a/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideInInterfaceMarkingTest.java b/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideInInterfaceMarkingTest.java
index 42268b2..ac11d72 100644
--- a/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideInInterfaceMarkingTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideInInterfaceMarkingTest.java
@@ -4,7 +4,7 @@
 
 package com.android.tools.r8.shaking;
 
-import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertEquals;
 
 import com.android.tools.r8.NoVerticalClassMerging;
 import com.android.tools.r8.TestBase;
@@ -14,6 +14,7 @@
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.utils.OptionalBool;
 import java.util.AbstractList;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -49,17 +50,17 @@
   private void verifyLibraryOverrideInformation(AppInfoWithLiveness appInfo, Enqueuer.Mode mode) {
     DexItemFactory dexItemFactory = appInfo.dexItemFactory();
     verifyIsEmptyMarkedAsOverridingLibraryMethod(
-        appInfo, dexItemFactory.createType(descriptor(A.class)));
+        appInfo, dexItemFactory.createType(descriptor(A.class)), OptionalBool.TRUE);
     verifyIsEmptyMarkedAsOverridingLibraryMethod(
-        appInfo, dexItemFactory.createType(descriptor(I.class)));
+        appInfo, dexItemFactory.createType(descriptor(I.class)), OptionalBool.FALSE);
   }
 
   private void verifyIsEmptyMarkedAsOverridingLibraryMethod(
-      AppInfoWithLiveness appInfo, DexType type) {
+      AppInfoWithLiveness appInfo, DexType type, OptionalBool expected) {
     DexProgramClass clazz = appInfo.definitionFor(type).asProgramClass();
     DexEncodedMethod method =
         clazz.lookupVirtualMethod(m -> m.getReference().name.toString().equals("isEmpty"));
-    assertTrue(method.isLibraryMethodOverride().isTrue());
+    assertEquals(expected, method.isLibraryMethodOverride());
   }
 
   static class TestClass {
diff --git a/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideInLambdaMarkingTest.java b/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideInLambdaMarkingTest.java
index 563a312..928a2fc 100644
--- a/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideInLambdaMarkingTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideInLambdaMarkingTest.java
@@ -4,7 +4,8 @@
 
 package com.android.tools.r8.shaking;
 
-import static org.junit.Assert.assertTrue;
+import static com.android.tools.r8.CollectorsUtils.toSingle;
+import static org.junit.Assert.assertEquals;
 
 import com.android.tools.r8.NoVerticalClassMerging;
 import com.android.tools.r8.TestBase;
@@ -15,6 +16,7 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.shaking.Enqueuer.Mode;
+import com.android.tools.r8.utils.OptionalBool;
 import java.util.Iterator;
 import java.util.Spliterator;
 import java.util.function.Consumer;
@@ -52,21 +54,29 @@
   private void verifyLibraryOverrideInformation(AppInfoWithLiveness appInfo, Mode mode) {
     DexItemFactory dexItemFactory = appInfo.dexItemFactory();
     verifyIteratorMethodMarkedAsOverridingLibraryMethod(
-        appInfo, dexItemFactory.createType(descriptor(I.class)));
+        appInfo, dexItemFactory.createType(descriptor(I.class)), OptionalBool.FALSE);
     verifyIteratorMethodMarkedAsOverridingLibraryMethod(
-        appInfo, dexItemFactory.createType(descriptor(J.class)));
+        appInfo, dexItemFactory.createType(descriptor(J.class)), OptionalBool.FALSE);
+    if (parameters.isDexRuntime()) {
+      DexProgramClass lambda =
+          appInfo.classes().stream()
+              .filter(x -> x.toSourceString().contains("$InternalSyntheticLambda"))
+              .collect(toSingle());
+      verifyIteratorMethodMarkedAsOverridingLibraryMethod(
+          appInfo, lambda.getType(), OptionalBool.TRUE);
+    }
   }
 
   private void verifyIteratorMethodMarkedAsOverridingLibraryMethod(
-      AppInfoWithLiveness appInfo, DexType type) {
+      AppInfoWithLiveness appInfo, DexType type, OptionalBool expected) {
     DexProgramClass clazz = appInfo.definitionFor(type).asProgramClass();
     DexEncodedMethod method =
         clazz.lookupVirtualMethod(m -> m.getReference().name.toString().equals("iterator"));
     // TODO(b/149976493): Mark library overrides from lambda instances.
     if (parameters.isCfRuntime()) {
-      assertTrue(method.isLibraryMethodOverride().isFalse());
+      assertEquals(OptionalBool.FALSE, method.isLibraryMethodOverride());
     } else {
-      assertTrue(method.isLibraryMethodOverride().isTrue());
+      assertEquals(expected, method.isLibraryMethodOverride());
     }
   }
 
diff --git a/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideMarkingTest.java b/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideMarkingTest.java
index a7908c2..188d4aa 100644
--- a/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideMarkingTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideMarkingTest.java
@@ -6,7 +6,6 @@
 
 import static com.google.common.base.Predicates.alwaysTrue;
 import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.NoVerticalClassMerging;
 import com.android.tools.r8.TestBase;
@@ -16,6 +15,7 @@
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.utils.OptionalBool;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -49,17 +49,17 @@
   private void verifyLibraryOverrideInformation(AppInfoWithLiveness appInfo, Enqueuer.Mode mode) {
     DexItemFactory dexItemFactory = appInfo.dexItemFactory();
     verifySingleVirtualMethodMarkedAsOverridingLibraryMethod(
-        appInfo, dexItemFactory.createType(descriptor(A.class)));
+        appInfo, dexItemFactory.createType(descriptor(A.class)), OptionalBool.FALSE);
     verifySingleVirtualMethodMarkedAsOverridingLibraryMethod(
-        appInfo, dexItemFactory.createType(descriptor(B.class)));
+        appInfo, dexItemFactory.createType(descriptor(B.class)), OptionalBool.TRUE);
   }
 
   private void verifySingleVirtualMethodMarkedAsOverridingLibraryMethod(
-      AppInfoWithLiveness appInfo, DexType type) {
+      AppInfoWithLiveness appInfo, DexType type, OptionalBool expected) {
     DexProgramClass clazz = appInfo.definitionFor(type).asProgramClass();
     assertEquals(1, clazz.getMethodCollection().numberOfVirtualMethods());
     DexEncodedMethod method = clazz.lookupVirtualMethod(alwaysTrue());
-    assertTrue(method.isLibraryMethodOverride().isTrue());
+    assertEquals(expected, method.isLibraryMethodOverride());
   }
 
   static class TestClass {
diff --git a/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideAbstractTest.java b/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideAbstractTest.java
new file mode 100644
index 0000000..c7f3e23
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideAbstractTest.java
@@ -0,0 +1,105 @@
+// Copyright (c) 2022, 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.shaking.librarymethodoverride;
+
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.Enqueuer;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class LibraryMethodOverrideAbstractTest extends TestBase {
+
+  @Parameter() public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void testRuntime() throws Exception {
+    testForRuntime(parameters)
+        .addProgramClasses(SubProgramClass.class, Main.class)
+        .addProgramClassFileData(
+            transformer(ProgramClass.class).removeMethodsWithName("foo").transform())
+        .addLibraryClasses(LibraryClass.class)
+        .addRunClasspathFiles(buildOnDexRuntime(parameters, LibraryClass.class))
+        .run(parameters.getRuntime(), Main.class)
+        .assertFailureWithErrorThatThrows(AbstractMethodError.class);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(SubProgramClass.class, Main.class)
+        .addProgramClassFileData(
+            transformer(ProgramClass.class).removeMethodsWithName("foo").transform())
+        .addDefaultRuntimeLibrary(parameters)
+        .addLibraryClasses(LibraryClass.class)
+        .addOptionsModification(
+            options -> options.testing.enqueuerInspector = this::verifyLibraryOverrideInformation)
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMainRule(Main.class)
+        .compile()
+        .addBootClasspathClasses(LibraryClass.class)
+        .run(parameters.getRuntime(), Main.class)
+        .assertFailureWithErrorThatThrows(AbstractMethodError.class);
+  }
+
+  private void verifyLibraryOverrideInformation(AppInfoWithLiveness appInfo, Enqueuer.Mode mode) {
+    if (mode.isInitialTreeShaking()) {
+      DexItemFactory dexItemFactory = appInfo.dexItemFactory();
+      DexProgramClass clazz =
+          appInfo
+              .definitionFor(dexItemFactory.createType(descriptor(SubProgramClass.class)))
+              .asProgramClass();
+      DexEncodedMethod method =
+          clazz.lookupVirtualMethod(m -> m.getReference().name.toString().equals("foo"));
+      assertTrue(method.isLibraryMethodOverride().isTrue());
+    }
+  }
+
+  public abstract static class LibraryClass {
+
+    abstract void foo();
+
+    public static void callFoo(LibraryClass libraryClass) {
+      libraryClass.foo();
+    }
+  }
+
+  public abstract static class SubProgramClass extends LibraryClass {
+
+    @Override
+    abstract void foo();
+  }
+
+  public static class ProgramClass extends SubProgramClass {
+
+    @Override
+    void foo() {
+      throw new RuntimeException("Should have been removed.");
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      LibraryClass.callFoo(new ProgramClass());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideDefaultMethodICCETest.java b/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideDefaultMethodICCETest.java
new file mode 100644
index 0000000..aa8ca52
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideDefaultMethodICCETest.java
@@ -0,0 +1,139 @@
+// Copyright (c) 2022, 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.shaking.librarymethodoverride;
+
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.TestRuntime.CfVm;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.Enqueuer;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class LibraryMethodOverrideDefaultMethodICCETest extends TestBase {
+
+  @Parameter() public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void testRuntime() throws Exception {
+    testForRuntime(parameters)
+        .addProgramClasses(Main.class, ProgramI.class, ProgramJ.class)
+        .addProgramClassFileData(
+            transformer(ProgramClass.class)
+                .setImplements(LibraryInterface.class, ProgramI.class, ProgramJ.class)
+                .transform())
+        .addLibraryClasses(LibraryInterface.class, LibraryCaller.class)
+        .addRunClasspathFiles(
+            buildOnDexRuntime(parameters, LibraryInterface.class, LibraryCaller.class))
+        .run(parameters.getRuntime(), Main.class)
+        .assertFailureWithErrorThatThrowsIf(
+            parameters.isCfRuntime() && parameters.getRuntime().asCf().isOlderThan(CfVm.JDK11),
+            IncompatibleClassChangeError.class)
+        .assertFailureWithErrorThatThrowsIf(
+            parameters.isCfRuntime()
+                && parameters.getRuntime().asCf().isNewerThanOrEqual(CfVm.JDK11),
+            AbstractMethodError.class)
+        .assertFailureWithErrorThatThrowsIf(
+            parameters.isDexRuntime(), IncompatibleClassChangeError.class);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(Main.class, ProgramI.class, ProgramJ.class)
+        .addProgramClassFileData(
+            transformer(ProgramClass.class)
+                .setImplements(LibraryInterface.class, ProgramI.class, ProgramJ.class)
+                .transform())
+        .addDefaultRuntimeLibrary(parameters)
+        .addLibraryClasses(LibraryInterface.class, LibraryCaller.class)
+        .addOptionsModification(
+            options -> options.testing.enqueuerInspector = this::verifyLibraryOverrideInformation)
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMainRule(Main.class)
+        .addDontObfuscate()
+        .compile()
+        .addBootClasspathClasses(LibraryInterface.class, LibraryCaller.class)
+        .run(parameters.getRuntime(), Main.class)
+        .assertFailureWithErrorThatThrowsIf(
+            parameters.canUseDefaultAndStaticInterfaceMethods(), AbstractMethodError.class)
+        .assertFailureWithErrorThatThrowsIf(
+            !parameters.canUseDefaultAndStaticInterfaceMethods(),
+            IncompatibleClassChangeError.class);
+  }
+
+  private void verifyLibraryOverrideInformation(AppInfoWithLiveness appInfo, Enqueuer.Mode mode) {
+    if (mode.isInitialTreeShaking()) {
+      if (parameters.canUseDefaultAndStaticInterfaceMethods()) {
+        verifyMethodFooOnHolderIsSetAsLibraryOverride(appInfo, ProgramI.class);
+        verifyMethodFooOnHolderIsSetAsLibraryOverride(appInfo, ProgramJ.class);
+      } else {
+        verifyMethodFooOnHolderIsSetAsLibraryOverride(appInfo, ProgramClass.class);
+      }
+    }
+  }
+
+  private void verifyMethodFooOnHolderIsSetAsLibraryOverride(
+      AppInfoWithLiveness appInfo, Class<?> programClass) {
+    DexItemFactory dexItemFactory = appInfo.dexItemFactory();
+    DexProgramClass clazz =
+        appInfo.definitionFor(dexItemFactory.createType(descriptor(programClass))).asProgramClass();
+    DexEncodedMethod method =
+        clazz.lookupVirtualMethod(m -> m.getReference().name.toString().equals("foo"));
+    assertTrue(method.isLibraryMethodOverride().isTrue());
+  }
+
+  public interface LibraryInterface {
+
+    void foo();
+  }
+
+  public static class LibraryCaller {
+
+    public static void callFoo(LibraryInterface iface) {
+      iface.foo();
+    }
+  }
+
+  public interface ProgramI extends LibraryInterface {
+
+    @Override
+    default void foo() {
+      System.out.println("ProgramI::foo");
+    }
+  }
+
+  public interface ProgramJ extends LibraryInterface {
+
+    @Override
+    default void foo() {
+      System.out.println("ProgramJ::foo");
+    }
+  }
+
+  public static class ProgramClass implements LibraryInterface, ProgramI /* ,ProgramJ */ {}
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      LibraryCaller.callFoo(new ProgramClass());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideDefaultMethodTest.java b/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideDefaultMethodTest.java
index 939b14a..046c2e5 100644
--- a/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideDefaultMethodTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideDefaultMethodTest.java
@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.shaking.librarymethodoverride;
 
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.TestBase;
@@ -58,13 +60,26 @@
 
   private void verifyLibraryOverrideInformation(AppInfoWithLiveness appInfo, Enqueuer.Mode mode) {
     DexItemFactory dexItemFactory = appInfo.dexItemFactory();
-    DexProgramClass clazz =
+    DexProgramClass programI =
         appInfo
             .definitionFor(dexItemFactory.createType(descriptor(ProgramI.class)))
             .asProgramClass();
-    DexEncodedMethod method =
-        clazz.lookupVirtualMethod(m -> m.getReference().name.toString().equals("foo"));
-    assertTrue(method.isLibraryMethodOverride().isTrue());
+    DexEncodedMethod programIFoo =
+        programI.lookupVirtualMethod(m -> m.getReference().name.toString().equals("foo"));
+    assertEquals(
+        parameters.canUseDefaultAndStaticInterfaceMethods(),
+        programIFoo.isLibraryMethodOverride().isTrue());
+    DexProgramClass programClass =
+        appInfo
+            .definitionFor(dexItemFactory.createType(descriptor(ProgramClass.class)))
+            .asProgramClass();
+    DexEncodedMethod programClassFoo =
+        programClass.lookupVirtualMethod(m -> m.getReference().name.toString().equals("foo"));
+    if (parameters.canUseDefaultAndStaticInterfaceMethods()) {
+      assertNull(programClassFoo);
+    } else {
+      assertTrue(programClassFoo.isLibraryMethodOverride().isTrue());
+    }
   }
 
   public interface LibraryI {
diff --git a/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideOfClassMethodWithInterfaceTest.java b/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideOfClassMethodWithInterfaceTest.java
index 247b780..4524dd7 100644
--- a/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideOfClassMethodWithInterfaceTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideOfClassMethodWithInterfaceTest.java
@@ -66,8 +66,7 @@
             .asProgramClass();
     DexEncodedMethod method =
         clazz.lookupVirtualMethod(m -> m.getReference().name.toString().equals("foo"));
-    // TODO(b/259531498): We should not mark the interface method as overriding.
-    assertTrue(method.isLibraryMethodOverride().isTrue());
+    assertTrue(method.isLibraryMethodOverride().isFalse());
   }
 
   public abstract static class LibraryClass {
diff --git a/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideOfSuperClassNotInHierarchyTest.java b/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideOfSuperClassNotInHierarchyTest.java
new file mode 100644
index 0000000..c9c8bf8
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/librarymethodoverride/LibraryMethodOverrideOfSuperClassNotInHierarchyTest.java
@@ -0,0 +1,120 @@
+// Copyright (c) 2022, 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.shaking.librarymethodoverride;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.Enqueuer;
+import com.android.tools.r8.utils.OptionalBool;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class LibraryMethodOverrideOfSuperClassNotInHierarchyTest extends TestBase {
+
+  private final String[] EXPECTED = new String[] {"SecondProgramClass::foo"};
+
+  @Parameter() public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void testRuntime() throws Exception {
+    testForRuntime(parameters)
+        .addProgramClasses(
+            FirstProgramClass.class, SecondProgramClass.class, ThirdProgramClass.class, Main.class)
+        .addLibraryClasses(LibraryClass.class, LibraryInterface.class)
+        .addRunClasspathFiles(
+            buildOnDexRuntime(parameters, LibraryClass.class, LibraryInterface.class))
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(EXPECTED);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(
+            FirstProgramClass.class, SecondProgramClass.class, ThirdProgramClass.class, Main.class)
+        .addDefaultRuntimeLibrary(parameters)
+        .addLibraryClasses(LibraryClass.class, LibraryInterface.class)
+        .addOptionsModification(
+            options -> options.testing.enqueuerInspector = this::verifyLibraryOverrideInformation)
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMainRule(Main.class)
+        .compile()
+        .addBootClasspathClasses(LibraryClass.class, LibraryInterface.class)
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(EXPECTED);
+  }
+
+  private void verifyLibraryOverrideInformation(AppInfoWithLiveness appInfo, Enqueuer.Mode mode) {
+    if (!mode.isInitialTreeShaking()) {
+      return;
+    }
+    DexItemFactory dexItemFactory = appInfo.dexItemFactory();
+    DexProgramClass clazz =
+        appInfo
+            .definitionFor(dexItemFactory.createType(descriptor(FirstProgramClass.class)))
+            .asProgramClass();
+    DexEncodedMethod method =
+        clazz.lookupVirtualMethod(m -> m.getReference().name.toString().equals("foo"));
+    assertEquals(OptionalBool.FALSE, method.isLibraryMethodOverride());
+    clazz =
+        appInfo
+            .definitionFor(dexItemFactory.createType(descriptor(SecondProgramClass.class)))
+            .asProgramClass();
+    method = clazz.lookupVirtualMethod(m -> m.getReference().name.toString().equals("foo"));
+    assertEquals(OptionalBool.TRUE, method.isLibraryMethodOverride());
+  }
+
+  public interface LibraryInterface {
+
+    void foo();
+  }
+
+  public static class LibraryClass {
+
+    public static void callFoo(LibraryInterface i) {
+      i.foo();
+    }
+  }
+
+  public static class FirstProgramClass {
+
+    public void foo() {
+      System.out.println("FirstProgramClass::foo");
+    }
+  }
+
+  public static class SecondProgramClass extends FirstProgramClass {
+
+    @Override
+    public void foo() {
+      System.out.println("SecondProgramClass::foo");
+    }
+  }
+
+  public static class ThirdProgramClass extends SecondProgramClass implements LibraryInterface {}
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      LibraryClass.callFoo(new ThirdProgramClass());
+    }
+  }
+}