diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 71898e2..14cac77 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -700,17 +700,8 @@
       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()) {
-        new RedundantBridgeRemover(appView.withLiveness())
-            .run(memberRebindingIdentityLens, executorService);
-      } else {
-        // If we don't have AppInfoWithLiveness here, it must be because we are not shrinking. When
-        // we are not shrinking, we can't move visibility bridges. In principle, though, it would be
-        // possible to remove visibility bridges that have been synthesized by R8, but we currently
-        // do not have this information.
-        assert !options.isShrinking();
-      }
+      new RedundantBridgeRemover(appView.withLiveness())
+          .run(memberRebindingIdentityLens, executorService);
 
       if (appView.appInfo().hasLiveness()) {
         SyntheticFinalization.finalizeWithLiveness(appView.withLiveness(), executorService, timing);
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..78de6f7 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,10 @@
   static ClasspathOrLibraryClass asClasspathOrLibraryClass(DexClass clazz) {
     return clazz != null ? clazz.asClasspathOrLibraryClass() : null;
   }
+
+  DexEncodedMethod lookupMethod(DexMethod method);
+
+  DexEncodedMethod lookupVirtualMethod(DexMethod method);
+
+  Iterable<DexEncodedMethod> virtualMethods();
 }
diff --git a/src/main/java/com/android/tools/r8/graph/Code.java b/src/main/java/com/android/tools/r8/graph/Code.java
index d0417b4..675d2df 100644
--- a/src/main/java/com/android/tools/r8/graph/Code.java
+++ b/src/main/java/com/android/tools/r8/graph/Code.java
@@ -73,6 +73,10 @@
 
   public abstract String toString(DexEncodedMethod method, RetracerForCodePrinting retracer);
 
+  public boolean passThroughDesugarAndIRConversion() {
+    return false;
+  }
+
   public boolean isCfCode() {
     return false;
   }
@@ -125,6 +129,14 @@
     return false;
   }
 
+  public boolean isMemberRebindingBridgeCode() {
+    return false;
+  }
+
+  public MemberRebindingBridgeCode asMemberRebindingBridgeCode() {
+    return null;
+  }
+
   public ThrowNullCode asThrowNullCode() {
     return null;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DefaultInstanceInitializerCode.java b/src/main/java/com/android/tools/r8/graph/DefaultInstanceInitializerCode.java
index 165ff81..dc2949c 100644
--- a/src/main/java/com/android/tools/r8/graph/DefaultInstanceInitializerCode.java
+++ b/src/main/java/com/android/tools/r8/graph/DefaultInstanceInitializerCode.java
@@ -67,6 +67,11 @@
     return INSTANCE;
   }
 
+  @Override
+  public boolean passThroughDesugarAndIRConversion() {
+    return true;
+  }
+
   public static boolean canonicalizeCodeIfPossible(AppView<?> appView, ProgramMethod method) {
     if (hasDefaultInstanceInitializerCode(method, appView)) {
       method.setCode(get(), appView);
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 318b353..24cc86c 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/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index 411e5ee..2e2755d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -517,6 +517,12 @@
 
   public final DexType retentionType =
       createStaticallyKnownType("Ljava/lang/annotation/Retention;");
+  public final DexType recentlyNonNull =
+      createStaticallyKnownType("Landroidx/annotation/RecentlyNonNull;");
+  public final DexType recentlyNullable =
+      createStaticallyKnownType("Landroidx/annotation/RecentlyNullable;");
+  public final DexType nullable = createStaticallyKnownType("Landroidx/annotation/Nullable;");
+  public final DexType nonNull = createStaticallyKnownType("Landroidx/annotation/NonNull;");
   public final DexType runtimeExceptionType = createStaticallyKnownType(runtimeExceptionDescriptor);
   public final DexType assertionErrorType = createStaticallyKnownType(assertionErrorDescriptor);
   public final DexType throwableType = createStaticallyKnownType(throwableDescriptor);
diff --git a/src/main/java/com/android/tools/r8/graph/MemberRebindingBridgeCode.java b/src/main/java/com/android/tools/r8/graph/MemberRebindingBridgeCode.java
new file mode 100644
index 0000000..9c136e8
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/MemberRebindingBridgeCode.java
@@ -0,0 +1,202 @@
+// 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;
+
+import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.proto.RewrittenPrototypeDescription;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.InvokeSuper;
+import com.android.tools.r8.ir.code.NumberGenerator;
+import com.android.tools.r8.ir.code.Position;
+import com.android.tools.r8.ir.code.Position.SyntheticPosition;
+import com.android.tools.r8.ir.code.Return;
+import com.android.tools.r8.ir.conversion.IRBuilder;
+import com.android.tools.r8.ir.conversion.MethodConversionOptions.MutableMethodConversionOptions;
+import com.android.tools.r8.ir.conversion.MethodConversionOptions.ThrowingMethodConversionOptions;
+import com.android.tools.r8.ir.conversion.SyntheticStraightLineSourceCode;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.utils.ListUtils;
+import com.android.tools.r8.utils.RetracerForCodePrinting;
+import com.google.common.collect.ImmutableList;
+import java.util.List;
+import java.util.function.Consumer;
+
+public class MemberRebindingBridgeCode extends Code {
+
+  private final DexMethod target;
+  private final boolean isInterface;
+
+  private MemberRebindingBridgeCode(DexMethod target, boolean isInterface) {
+    this.target = target;
+    this.isInterface = isInterface;
+  }
+
+  @Override
+  public boolean isMemberRebindingBridgeCode() {
+    return true;
+  }
+
+  public DexMethod getTarget() {
+    return target;
+  }
+
+  public boolean getInterface() {
+    return isInterface;
+  }
+
+  @Override
+  public boolean passThroughDesugarAndIRConversion() {
+    return true;
+  }
+
+  @Override
+  public MemberRebindingBridgeCode asMemberRebindingBridgeCode() {
+    return this;
+  }
+
+  @Override
+  public IRCode buildIR(
+      ProgramMethod method,
+      AppView<?> appView,
+      Origin origin,
+      MutableMethodConversionOptions conversionOptions) {
+    DexMethod originalMethod =
+        appView.graphLens().getOriginalMethodSignature(method.getReference());
+    MemberRebindingBridgeSourceCode source =
+        new MemberRebindingBridgeSourceCode(originalMethod, this.target, isInterface);
+    return IRBuilder.create(method, appView, source, origin).build(method, conversionOptions);
+  }
+
+  @Override
+  public IRCode buildInliningIR(
+      ProgramMethod context,
+      ProgramMethod method,
+      AppView<?> appView,
+      GraphLens codeLens,
+      NumberGenerator valueNumberGenerator,
+      Position callerPosition,
+      Origin origin,
+      RewrittenPrototypeDescription protoChanges) {
+    DexMethod originalMethod =
+        appView.graphLens().getOriginalMethodSignature(method.getReference());
+    MemberRebindingBridgeSourceCode source =
+        new MemberRebindingBridgeSourceCode(
+            originalMethod, this.target, isInterface, callerPosition);
+    return IRBuilder.createForInlining(
+            method, appView, codeLens, source, origin, valueNumberGenerator, protoChanges)
+        .build(context, new ThrowingMethodConversionOptions(appView.options()));
+  }
+
+  @Override
+  public void registerCodeReferences(ProgramMethod method, UseRegistry registry) {
+    registry.registerInvokeSuper(this.target);
+  }
+
+  @Override
+  public void registerCodeReferencesForDesugaring(ClasspathMethod method, UseRegistry registry) {
+    registry.registerInvokeSuper(this.target);
+  }
+
+  @Override
+  public String toString() {
+    return "<member-rebinding-bridge-code>";
+  }
+
+  @Override
+  public String toString(DexEncodedMethod method, RetracerForCodePrinting retracer) {
+    StringBuilder builder = new StringBuilder();
+    if (method != null) {
+      builder.append(method.toSourceString()).append("\n");
+    }
+    return builder.append(this).toString();
+  }
+
+  @Override
+  public int estimatedDexCodeSizeUpperBoundInBytes() {
+    throw new Unreachable();
+  }
+
+  @Override
+  public boolean isEmptyVoidMethod() {
+    return false;
+  }
+
+  @Override
+  protected int computeHashCode() {
+    return System.identityHashCode(this);
+  }
+
+  @Override
+  protected boolean computeEquals(Object other) {
+    return this == other;
+  }
+
+  @Override
+  public boolean isSharedCodeObject() {
+    return true;
+  }
+
+  public static Builder builder() {
+    return new Builder();
+  }
+
+  static class MemberRebindingBridgeSourceCode extends SyntheticStraightLineSourceCode {
+
+    MemberRebindingBridgeSourceCode(DexMethod context, DexMethod method, boolean isInterface) {
+      this(context, method, isInterface, null);
+    }
+
+    MemberRebindingBridgeSourceCode(
+        DexMethod context, DexMethod method, boolean isInterface, Position callerPosition) {
+      super(
+          getInstructionBuilders(method, isInterface),
+          SyntheticPosition.builder()
+              .setLine(0)
+              .setMethod(context)
+              .setCallerPosition(callerPosition)
+              .build());
+    }
+
+    private static List<Consumer<IRBuilder>> getInstructionBuilders(
+        DexMethod method, boolean isInterface) {
+      return ImmutableList.of(
+          builder -> {
+            InvokeSuper invokeSuper =
+                InvokeSuper.builder()
+                    .setMethod(method)
+                    .setArguments(
+                        ListUtils.newArrayList(
+                            builder.getReceiverValue(), builder.getArgumentValues()))
+                    .setInterface(isInterface)
+                    .applyIf(
+                        !method.getReturnType().isVoidType(),
+                        b -> b.setFreshOutValue(builder.appView, builder))
+                    .build();
+            builder.add(invokeSuper);
+            builder.addReturn(new Return(invokeSuper.outValue()));
+          });
+    }
+  }
+
+  public static class Builder {
+
+    private DexMethod target;
+    private boolean isInterface;
+
+    public Builder setTarget(DexMethod target) {
+      this.target = target;
+      return this;
+    }
+
+    public Builder setInterface(boolean isInterface) {
+      this.isInterface = isInterface;
+      return this;
+    }
+
+    public MemberRebindingBridgeCode build() {
+      assert target != null;
+      return new MemberRebindingBridgeCode(target, isInterface);
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/graph/MethodAccessFlags.java b/src/main/java/com/android/tools/r8/graph/MethodAccessFlags.java
index 12da839..085d96d 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodAccessFlags.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodAccessFlags.java
@@ -7,6 +7,7 @@
 import com.google.common.collect.ImmutableList;
 import java.util.List;
 import java.util.function.BooleanSupplier;
+import java.util.function.Consumer;
 
 public class MethodAccessFlags extends AccessFlags<MethodAccessFlags> {
 
@@ -264,17 +265,17 @@
 
     public Builder set(int flag) {
       flags.set(flag);
-      return this;
+      return self();
     }
 
     public Builder setBridge() {
       flags.setBridge();
-      return this;
+      return self();
     }
 
     public Builder setConstructor() {
       flags.setConstructor();
-      return this;
+      return self();
     }
 
     public Builder setStrict(boolean value) {
@@ -283,7 +284,7 @@
       } else {
         flags.unsetStrict();
       }
-      return this;
+      return self();
     }
 
     public Builder setSynchronized(boolean value) {
@@ -292,7 +293,23 @@
       } else {
         flags.unsetSynchronized();
       }
-      return this;
+      return self();
+    }
+
+    public Builder setAbstract(boolean value) {
+      if (value) {
+        flags.setAbstract();
+      } else {
+        flags.unsetAbstract();
+      }
+      return self();
+    }
+
+    public Builder applyIf(boolean condition, Consumer<Builder> consumer) {
+      if (condition) {
+        consumer.accept(self());
+      }
+      return self();
     }
 
     @Override
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..5b84a81
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/analysis/EnqueuerLibraryOverrideAnalysis.java
@@ -0,0 +1,313 @@
+// 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/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index c99ee11..2cef6fe 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -47,6 +47,7 @@
 import java.util.Iterator;
 import java.util.List;
 import java.util.Set;
+import java.util.function.Consumer;
 import java.util.function.Function;
 import java.util.function.Predicate;
 
@@ -1685,6 +1686,18 @@
       return self();
     }
 
+    public B apply(Consumer<B> consumer) {
+      consumer.accept(self());
+      return self();
+    }
+
+    public B applyIf(boolean condition, Consumer<B> consumer) {
+      if (condition) {
+        consumer.accept(self());
+      }
+      return self();
+    }
+
     public B setPosition(Instruction other) {
       return setPosition(other.getPosition());
     }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java b/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java
index ae47eb6..0fd2dc9 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java
@@ -140,4 +140,28 @@
   void internalRegisterUse(UseRegistry<?> registry, DexClassAndMethod context) {
     registry.registerInvokeSuper(getInvokedMethod());
   }
+
+  public static Builder builder() {
+    return new Builder();
+  }
+
+  public static class Builder extends InvokeMethod.Builder<InvokeSuper.Builder, InvokeSuper> {
+
+    private boolean isInterface;
+
+    @Override
+    public InvokeSuper build() {
+      return amend(new InvokeSuper(method, outValue, arguments, isInterface));
+    }
+
+    public Builder setInterface(boolean isInterface) {
+      this.isInterface = isInterface;
+      return self();
+    }
+
+    @Override
+    public Builder self() {
+      return this;
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
index 4a29cb6..cb45923 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
@@ -114,6 +114,7 @@
 import com.android.tools.r8.ir.code.Throw;
 import com.android.tools.r8.ir.code.Ushr;
 import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.code.ValueFactory;
 import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.code.ValueTypeConstraint;
 import com.android.tools.r8.ir.code.Xor;
@@ -148,11 +149,11 @@
 /**
  * Builder object for constructing high-level IR from dex bytecode.
  *
- * <p>The generated IR is in SSA form. The SSA construction is based on the paper
- * "Simple and Efficient Construction of Static Single Assignment Form" available at
+ * <p>The generated IR is in SSA form. The SSA construction is based on the paper "Simple and
+ * Efficient Construction of Static Single Assignment Form" available at
  * http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf
  */
-public class IRBuilder {
+public class IRBuilder implements ValueFactory {
 
   public static final int INITIAL_BLOCK_OFFSET = -1;
 
@@ -181,6 +182,11 @@
     }
   }
 
+  @Override
+  public Value createValue(TypeElement type, DebugLocalInfo localInfo) {
+    return new Value(valueNumberGenerator.next(), type, localInfo);
+  }
+
   // SSA construction uses a worklist of basic blocks reachable from the entry and their
   // instruction offsets.
   private static class WorklistItem {
@@ -1830,7 +1836,7 @@
     addReturn(new Return());
   }
 
-  private void addReturn(Return ret) {
+  public void addReturn(Return ret) {
     // Attach the live locals to the return instruction to avoid a local change on monitor exit.
     attachLocalValues(ret);
     source.buildPostlude(this);
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index f85f8d5..73c4b37 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -1566,7 +1566,7 @@
     }
     Code code = method.getDefinition().getCode();
     assert !code.isThrowNullCode();
-    return code.isDefaultInstanceInitializerCode();
+    return code.passThroughDesugarAndIRConversion();
   }
 
   // Compute optimization info summary for the current method unless it is pinned
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/desugaredlibrary/apiconversion/DesugaredLibraryConversionCfProvider.java b/src/main/java/com/android/tools/r8/ir/desugar/desugaredlibrary/apiconversion/DesugaredLibraryConversionCfProvider.java
index 94bd06b..40d34cb 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/desugaredlibrary/apiconversion/DesugaredLibraryConversionCfProvider.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/desugaredlibrary/apiconversion/DesugaredLibraryConversionCfProvider.java
@@ -208,9 +208,7 @@
             .generateCfCode();
     DexEncodedMethod newMethod = wrapperSynthesizer.newSynthesizedMethod(methodToInstall, cfCode);
     newMethod.setCode(cfCode, DexEncodedMethod.NO_PARAMETER_INFO);
-    if (method.getDefinition().isLibraryMethodOverride().isTrue()) {
-      newMethod.setLibraryMethodOverride(OptionalBool.TRUE);
-    }
+    newMethod.setLibraryMethodOverride(OptionalBool.TRUE);
     ProgramMethod callback = new ProgramMethod(clazz, newMethod);
     assert eventConsumer != null;
     eventConsumer.acceptAPIConversionCallback(callback);
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/naming/IdentifierMinifier.java b/src/main/java/com/android/tools/r8/naming/IdentifierMinifier.java
index 0da73cf..4c47989 100644
--- a/src/main/java/com/android/tools/r8/naming/IdentifierMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/IdentifierMinifier.java
@@ -195,7 +195,9 @@
               instructions);
       code.asCfCode().setInstructions(newInstructions);
     } else {
-      assert code.isDefaultInstanceInitializerCode() || code.isThrowNullCode();
+      assert code.isDefaultInstanceInitializerCode()
+          || code.isThrowNullCode()
+          || code.isMemberRebindingBridgeCode();
     }
   }
 }
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 2ac83b2..79bbfe6 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
@@ -6,6 +6,7 @@
 import static com.android.tools.r8.utils.AndroidApiLevelUtils.isApiSafeForMemberRebinding;
 
 import com.android.tools.r8.androidapi.AndroidApiLevelCompute;
+import com.android.tools.r8.androidapi.ComputedApiLevel;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexClassAndField;
@@ -18,6 +19,8 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.FieldAccessInfoCollection;
 import com.android.tools.r8.graph.LibraryMethod;
+import com.android.tools.r8.graph.MemberRebindingBridgeCode;
+import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.graph.MethodAccessInfoCollection;
 import com.android.tools.r8.graph.MethodResolutionResult;
 import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
@@ -53,6 +56,7 @@
   private final InternalOptions options;
 
   private final MemberRebindingLens.Builder lensBuilder;
+  private final Map<DexMethod, DexClassAndMethod> insertedLibraryBridges = new IdentityHashMap<>();
 
   public MemberRebindingAnalysis(AppView<AppInfoWithLiveness> appView) {
     assert appView.graphLens().isContextFreeForMethods();
@@ -74,69 +78,66 @@
       return original;
     }
 
-    if (invokeType.isSuper() && options.canHaveSuperInvokeBug()) {
-      // To preserve semantics we should find the first library method on the boundary.
-      DexType firstLibraryTarget =
-          firstLibraryClassOrFirstInterfaceTarget(
-              resolutionResult.getResolvedHolder(),
-              appView,
-              resolvedMethod.getReference(),
-              original.getHolderType(),
-              DexClass::lookupMethod);
-      if (firstLibraryTarget == null) {
-        return original;
+    if (!invokeType.isSuper() || !options.canHaveSuperInvokeBug()) {
+      LibraryMethod eligibleLibraryMethod = null;
+      SingleResolutionResult<?> currentResolutionResult = resolutionResult;
+      while (currentResolutionResult != null) {
+        DexClassAndMethod currentResolvedMethod = currentResolutionResult.getResolutionPair();
+        if (canRebindDirectlyToLibraryMethod(
+            currentResolvedMethod,
+            currentResolutionResult.withInitialResolutionHolder(
+                currentResolutionResult.getResolvedHolder()),
+            contexts,
+            invokeType,
+            original)) {
+          eligibleLibraryMethod = currentResolvedMethod.asLibraryMethod();
+        }
+        if (appView.getAssumeInfoCollection().contains(currentResolvedMethod)) {
+          break;
+        }
+        DexClass currentResolvedHolder = currentResolvedMethod.getHolder();
+        if (resolvedMethod.getDefinition().belongsToVirtualPool()
+            && !currentResolvedHolder.isInterface()
+            && currentResolvedHolder.getSuperType() != null) {
+          currentResolutionResult =
+              appView
+                  .appInfo()
+                  .resolveMethodOnClassLegacy(currentResolvedHolder.getSuperType(), original)
+                  .asSingleResolution();
+        } else {
+          break;
+        }
       }
-      DexClass libraryHolder = appView.definitionFor(firstLibraryTarget);
-      if (libraryHolder == null) {
-        return original;
+      if (eligibleLibraryMethod != null) {
+        return eligibleLibraryMethod.getReference();
       }
-      if (libraryHolder == resolvedMethod.getHolder()) {
-        return resolvedMethod.getReference();
-      }
-      return resolvedMethod.getReference().withHolder(libraryHolder, appView.dexItemFactory());
     }
 
-    LibraryMethod eligibleLibraryMethod = null;
-    SingleResolutionResult<?> currentResolutionResult = resolutionResult;
-    while (currentResolutionResult != null) {
-      DexClassAndMethod currentResolvedMethod = currentResolutionResult.getResolutionPair();
-      if (canRebindDirectlyToLibraryMethod(
-          currentResolvedMethod,
-          currentResolutionResult.withInitialResolutionHolder(
-              currentResolutionResult.getResolvedHolder()),
-          contexts,
-          invokeType,
-          original)) {
-        eligibleLibraryMethod = currentResolvedMethod.asLibraryMethod();
-      }
-      if (appView.getAssumeInfoCollection().contains(currentResolvedMethod)) {
-        break;
-      }
-      DexClass currentResolvedHolder = currentResolvedMethod.getHolder();
-      if (resolvedMethod.getDefinition().belongsToVirtualPool()
-          && !currentResolvedHolder.isInterface()
-          && currentResolvedHolder.getSuperType() != null) {
-        currentResolutionResult =
-            appView
-                .appInfo()
-                .resolveMethodOnClassLegacy(currentResolvedHolder.getSuperType(), original)
-                .asSingleResolution();
-      } else {
-        break;
-      }
-    }
-    if (eligibleLibraryMethod != null) {
-      return eligibleLibraryMethod.getReference();
+    if (resolvedMethod.getDefinition().isStatic()) {
+      return original;
     }
 
-    DexType newHolder =
-        firstLibraryClassOrFirstInterfaceTarget(
-            resolvedMethod.getHolder(),
-            appView,
-            resolvedMethod.getReference(),
-            original.getHolderType(),
-            DexClass::lookupMethod);
-    return newHolder != null ? original.withHolder(newHolder, appView.dexItemFactory()) : original;
+    // If we could not find a valid library method to rebind to then create a bridge on the top most
+    // program class before crossing into library.
+    DexClass newHolder =
+        resolvedMethod.getHolder().isInterface()
+            ? firstProgramClassForTarget(
+                appView, resolvedMethod.getReference(), original.getHolderType())
+            : firstProgramClass(appView, original.getHolderType());
+    if (newHolder == null || newHolder.isNotProgramClass()) {
+      return original;
+    }
+    // We cannot insert default methods on interfaces after desugaring, so we return the resolved
+    // method.
+    if (newHolder.isInterface() && !options.canUseDefaultAndStaticInterfaceMethods()) {
+      return resolvedMethod.getReference();
+    }
+    if (!appView.getAssumeInfoCollection().get(resolvedMethod).isEmpty()) {
+      return original;
+    }
+    DexMethod bridge = original.withHolder(newHolder, appView.dexItemFactory());
+    insertedLibraryBridges.put(bridge, resolvedMethod);
+    return bridge;
   }
 
   private boolean canRebindDirectlyToLibraryMethod(
@@ -146,8 +147,8 @@
       Type invokeType,
       DexMethod original) {
     // TODO(b/194422791): It could potentially be that `original.holder` is not a subtype of
-    //  `original.holder` on all API levels, in which case it is not OK to rebind to the resolved
-    //  method.
+    //  `resolvedMethod.holder` on all API levels, in which case it is not OK to rebind to the
+    //  resolved method.
     return resolvedMethod.isLibraryMethod()
         && isAccessibleInAllContexts(resolvedMethod, resolutionResult, contexts)
         && !isInvokeSuperToInterfaceMethod(resolvedMethod, invokeType)
@@ -238,6 +239,34 @@
     return null;
   }
 
+  private static DexClass firstProgramClassForTarget(
+      DexDefinitionSupplier definitions, DexMethod target, DexType current) {
+    DexClass clazz = definitions.contextIndependentDefinitionFor(current);
+    if (clazz == null) {
+      return null;
+    }
+    DexEncodedMethod potential = clazz.lookupMethod(target);
+    if (potential != null) {
+      // Found, return type.
+      return clazz;
+    }
+    if (clazz.superType != null) {
+      DexClass matchingSuper = firstProgramClassForTarget(definitions, target, clazz.superType);
+      if (matchingSuper != null) {
+        // Found in supertype, return first program class.
+        return matchingSuper.isNotProgramClass() ? clazz : matchingSuper;
+      }
+    }
+    for (DexType iface : clazz.getInterfaces()) {
+      DexClass matchingIface = firstProgramClassForTarget(definitions, target, iface);
+      if (matchingIface != null) {
+        // Found in interface, return first program class.
+        return matchingIface.isNotProgramClass() ? clazz : matchingIface;
+      }
+    }
+    return null;
+  }
+
   private static DexType firstLibraryClass(DexDefinitionSupplier definitions, DexType bottom) {
     DexClass searchClass = definitions.contextIndependentDefinitionFor(bottom);
     while (searchClass != null && searchClass.isProgramClass()) {
@@ -247,6 +276,21 @@
     return searchClass != null ? searchClass.getType() : null;
   }
 
+  private static DexProgramClass firstProgramClass(
+      DexDefinitionSupplier definitions, DexType bottom) {
+    DexProgramClass searchClass =
+        DexProgramClass.asProgramClassOrNull(definitions.contextIndependentDefinitionFor(bottom));
+    while (searchClass != null && searchClass.isProgramClass()) {
+      DexClass superClass =
+          definitions.definitionFor(searchClass.getSuperType(), searchClass.asProgramClass());
+      if (superClass.isNotProgramClass()) {
+        return searchClass;
+      }
+      searchClass = superClass.asProgramClass();
+    }
+    return null;
+  }
+
   private MethodResolutionResult resolveMethodOnClass(DexMethod method) {
     return appView.appInfo().resolveMethodOnClassLegacy(method.holder, method);
   }
@@ -371,7 +415,7 @@
                       builder -> {
                         if (!targetDefinition.isAbstract()
                             && targetDefinition.getApiLevelForCode().isNotSetApiLevel()) {
-                          assert target.isLibraryMethod();
+                          assert !target.isProgramMethod();
                           builder.setApiLevelForCode(
                               appView
                                   .apiLevelCompute()
@@ -380,7 +424,8 @@
                                       appView.computedMinApiLevel()));
                         }
                         builder.setIsLibraryMethodOverrideIf(
-                            target.isLibraryMethod(), OptionalBool.TRUE);
+                            !target.isProgramMethod() && !targetDefinition.isStatic(),
+                            OptionalBool.TRUE);
                       });
               bridgeHolder.addMethod(bridgeMethodDefinition);
             }
@@ -512,9 +557,39 @@
     computeMethodRebinding(appInfo.getMethodAccessInfoCollection());
     recordNonReboundFieldAccesses(executorService);
     appInfo.getFieldAccessInfoCollection().flattenAccessContexts();
+    insertLibraryBridges();
     return lensBuilder.build();
   }
 
+  private void insertLibraryBridges() {
+    insertedLibraryBridges.forEach(
+        (method, resolvedMethod) -> {
+          assert !resolvedMethod.isProgramMethod();
+          DexProgramClass holder =
+              DexProgramClass.asProgramClassOrNull(appView.definitionFor(method.getHolderType()));
+          assert holder != null;
+          assert !holder.isInterface() || options.canUseDefaultAndStaticInterfaceMethods();
+          DexEncodedMethod resolvedDefinition = resolvedMethod.getDefinition();
+          holder.addMethod(
+              DexEncodedMethod.syntheticBuilder()
+                  .setMethod(method)
+                  .setApiLevelForDefinition(resolvedDefinition.getApiLevelForDefinition())
+                  // Since we could not member rebind to this definition it is at least higher than
+                  // min-api.
+                  .setApiLevelForCode(ComputedApiLevel.unknown())
+                  .setCode(
+                      MemberRebindingBridgeCode.builder()
+                          .setTarget(resolvedMethod.getDefinition().getReference())
+                          .setInterface(resolvedMethod.getHolder().isInterface())
+                          .build())
+                  .setAccessFlags(MethodAccessFlags.builder().setPublic().setSynthetic().build())
+                  .setClassFileVersion(resolvedDefinition.getClassFileVersion())
+                  .setDeprecated(resolvedDefinition.deprecated)
+                  .setIsLibraryMethodOverride(OptionalBool.TRUE)
+                  .build());
+        });
+  }
+
   private boolean verifyFieldAccessCollectionContainsAllNonReboundFieldReferences(
       ExecutorService executorService) throws ExecutionException {
     Set<DexField> nonReboundFieldReferences = computeNonReboundFieldReferences(executorService);
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..b46e1f9 100644
--- a/src/main/java/com/android/tools/r8/optimize/RedundantBridgeRemover.java
+++ b/src/main/java/com/android/tools/r8/optimize/RedundantBridgeRemover.java
@@ -5,6 +5,7 @@
 
 import static com.android.tools.r8.utils.ThreadUtils.processItems;
 
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexEncodedMethod;
@@ -19,8 +20,8 @@
 import com.android.tools.r8.ir.optimize.info.bridge.BridgeInfo;
 import com.android.tools.r8.optimize.InvokeSingleTargetExtractor.InvokeKind;
 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;
@@ -29,20 +30,23 @@
 
 public class RedundantBridgeRemover {
 
-  private final AppView<AppInfoWithLiveness> appView;
+  private final AppView<? extends AppInfoWithClassHierarchy> appView;
 
-  public RedundantBridgeRemover(AppView<AppInfoWithLiveness> appView) {
+  public RedundantBridgeRemover(AppView<? extends AppInfoWithClassHierarchy> appView) {
     this.appView = appView;
   }
 
   private DexClassAndMethod getTargetForRedundantBridge(ProgramMethod method) {
+    assert appView.hasLiveness();
     DexEncodedMethod definition = method.getDefinition();
     BridgeInfo bridgeInfo = definition.getOptimizationInfo().getBridgeInfo();
     boolean isBridge = definition.isBridge() || bridgeInfo != null;
+    // TODO(b/258176116): We can only remove bridges if they are marked as bridge or abstract.
     if (!isBridge || definition.isAbstract()) {
       return null;
     }
-    InvokeSingleTargetExtractor targetExtractor = new InvokeSingleTargetExtractor(appView, method);
+    InvokeSingleTargetExtractor targetExtractor =
+        new InvokeSingleTargetExtractor(appView.withLiveness(), method);
     method.registerCodeReferences(targetExtractor);
     DexMethod target = targetExtractor.getTarget();
     // javac-generated visibility forward bridge method has same descriptor (name, signature and
@@ -134,12 +138,27 @@
       RedundantBridgeRemovalLens.Builder lensBuilder, ExecutorService executorService)
       throws ExecutionException {
     Map<DexProgramClass, ProgramMethodSet> bridgesToRemove = new ConcurrentHashMap<>();
+    boolean hasLiveness = appView.hasLiveness();
+    // If we don't have AppInfoWithLiveness here, it must be because we are not shrinking. When we
+    // are not shrinking, we can't remove visibility bridges. In principle, though, it would be
+    // possible to remove visibility bridges that have been synthesized by R8, but we currently do
+    // not have this information.
+    assert hasLiveness || !appView.options().isShrinking();
     processItems(
         appView.appInfo().classes(),
         clazz -> {
           ProgramMethodSet bridgesToRemoveForClass = ProgramMethodSet.create();
           clazz.forEachProgramMethod(
               method -> {
+                DexEncodedMethod definition = method.getDefinition();
+                if (definition.getCode() != null
+                    && definition.getCode().isMemberRebindingBridgeCode()) {
+                  bridgesToRemoveForClass.add(method);
+                  return;
+                }
+                if (!hasLiveness) {
+                  return;
+                }
                 KeepMethodInfo keepInfo = appView.getKeepInfo(method);
                 if (!keepInfo.isShrinkingAllowed(appView.options())
                     || !keepInfo.isOptimizationAllowed(appView.options())) {
@@ -155,13 +174,19 @@
                   // 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
                   //  the target is not public, but still accessible to call sites.
                   boolean isEligibleForRetargeting =
                       appView.testing().enableRetargetingConstructorBridgeCalls
-                          || !method.getDefinition().isInstanceInitializer();
+                          || !definition.isInstanceInitializer();
                   if (isEligibleForRetargeting
                       && target.getAccessFlags().isPublic()
                       && target.getHolder().isPublic()) {
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 173c302..c7a45bc 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;
@@ -535,6 +536,10 @@
     return graphReporter;
   }
 
+  public Set<DexProgramClass> getLiveProgramTypes() {
+    return liveTypes.getItems();
+  }
+
   private EnqueuerUseRegistryFactory createUseRegistryFactory() {
     if (mode.isFinalTreeShaking()) {
       return appView.withGeneratedMessageLiteShrinker(
@@ -679,17 +684,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(
@@ -2869,10 +2863,7 @@
             } else {
               markLibraryAndClasspathMethodOverridesAsLive(instantiation, clazz);
             }
-            if (clazz.superType != null) {
-              worklist.addIfNotSeen(clazz.superType);
-            }
-            worklist.addIfNotSeen(clazz.interfaces);
+            clazz.forEachImmediateSupertype(worklist::addIfNotSeen);
           });
     }
   }
@@ -2969,7 +2960,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)) {
@@ -3001,11 +2992,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(
@@ -3618,6 +3604,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);
@@ -3640,8 +3629,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/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index b479808..33d8f24 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -52,6 +52,7 @@
 import com.android.tools.r8.graph.GraphLens.MethodLookupResult;
 import com.android.tools.r8.graph.GraphLens.NonIdentityGraphLens;
 import com.android.tools.r8.graph.LookupResult.LookupResultSuccess;
+import com.android.tools.r8.graph.MemberRebindingBridgeCode;
 import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.graph.MethodResolutionResult;
 import com.android.tools.r8.graph.ObjectAllocationInfoCollection;
@@ -802,6 +803,20 @@
               graphLens.getOriginalMethodSignature(implementationMethod);
           assert originalMethod == originalImplementationMethod;
           assert implementationMethod == renamedMethod;
+        } else if (encodedMethod.hasCode()
+            && encodedMethod.getCode().isMemberRebindingBridgeCode()
+            && renamedMethod != originalMethod) {
+          MemberRebindingBridgeCode memberRebindingBridgeCode =
+              encodedMethod.getCode().asMemberRebindingBridgeCode();
+          DexEncodedMethod resolvedMethod =
+              appView
+                  .appInfo()
+                  .resolveMethodOn(
+                      originalMethod.getHolderType(),
+                      originalMethod,
+                      memberRebindingBridgeCode.getInterface())
+                  .getResolvedMethod();
+          assert resolvedMethod.getReference() == memberRebindingBridgeCode.getTarget();
         } else {
           assert method == renamedMethod;
         }
@@ -857,8 +872,8 @@
                 .resolveMethodOnInterfaceLegacy(method.getHolderType(), method.getReference())
                 .lookupVirtualDispatchTargets(target, appInfo)
                 .asLookupResultSuccess();
-        assert lookupResult != null;
         if (lookupResult == null) {
+          assert false;
           return true;
         }
         if (lookupResult.contains(method)) {
@@ -1545,19 +1560,29 @@
       assert invocationTarget.isStatic()
           || invocationTarget.isNonPrivateVirtualMethod()
           || invocationTarget.isNonStaticPrivateMethod();
-      SynthesizedBridgeCode code =
-          new SynthesizedBridgeCode(
-              newMethod,
-              appView.graphLens().getOriginalMethodSignature(method.getReference()),
-              invocationTarget.getReference(),
-              invocationTarget.isStatic()
-                  ? STATIC
-                  : (invocationTarget.isNonPrivateVirtualMethod() ? VIRTUAL : DIRECT),
-              target.isInterface());
 
-      // Add the bridge to the list of synthesized bridges such that the method signatures will
-      // be updated by the end of vertical class merging.
-      synthesizedBridges.add(code);
+      Code code;
+      if (invocationTarget.getCode().isMemberRebindingBridgeCode()) {
+        // Duplicate the code object, it should never be emitted anyway. The bridge is also
+        // inserted for signatures defined in the library and these are not subject to be rewritten
+        // after.
+        code = invocationTarget.getCode();
+      } else {
+        SynthesizedBridgeCode bridgeCode =
+            new SynthesizedBridgeCode(
+                newMethod,
+                appView.graphLens().getOriginalMethodSignature(method.getReference()),
+                invocationTarget.getReference(),
+                invocationTarget.isStatic()
+                    ? STATIC
+                    : (invocationTarget.isNonPrivateVirtualMethod() ? VIRTUAL : DIRECT),
+                target.isInterface());
+
+        // Add the bridge to the list of synthesized bridges such that the method signatures will
+        // be updated by the end of vertical class merging.
+        synthesizedBridges.add(bridgeCode);
+        code = bridgeCode;
+      }
 
       CfVersion classFileVersion =
           method.hasClassFileVersion() ? method.getClassFileVersion() : null;
@@ -1998,6 +2023,10 @@
     return AbortReason.UNSAFE_INLINING;
   }
 
+  public Collection<DexType> getRemovedClasses() {
+    return Collections.unmodifiableCollection(mergedClasses.keySet());
+  }
+
   public class SingleTypeMapperGraphLens extends NonIdentityGraphLens {
 
     private final DexType source;
@@ -2412,8 +2441,4 @@
       };
     }
   }
-
-  public Collection<DexType> getRemovedClasses() {
-    return Collections.unmodifiableCollection(mergedClasses.keySet());
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/utils/ListUtils.java b/src/main/java/com/android/tools/r8/utils/ListUtils.java
index 406d482..33e4a3d 100644
--- a/src/main/java/com/android/tools/r8/utils/ListUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ListUtils.java
@@ -197,6 +197,16 @@
     return list;
   }
 
+  public static <T> ArrayList<T> newArrayList(T element, List<T> otherOrNull) {
+    int size = otherOrNull == null ? 1 : otherOrNull.size() + 1;
+    ArrayList<T> list = new ArrayList<>(size);
+    list.add(element);
+    if (otherOrNull != null) {
+      list.addAll(otherOrNull);
+    }
+    return list;
+  }
+
   public static <T> ArrayList<T> newArrayList(ForEachable<T> forEachable) {
     ArrayList<T> list = new ArrayList<>();
     forEachable.forEach(list::add);
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelIndirectTargetWithDifferentApiLevelTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelIndirectTargetWithDifferentApiLevelTest.java
index 3c2923d..e235a9e 100644
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelIndirectTargetWithDifferentApiLevelTest.java
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelIndirectTargetWithDifferentApiLevelTest.java
@@ -138,14 +138,7 @@
     if (isGreaterOrEqualToClassMethodMockLevel()) {
       runResult.assertSuccessWithOutputLines("LibraryClass::foo");
     } else if (isGreaterOrEqualToIfaceMockLevel()) {
-      if (isR8) {
-        runResult.assertFailureWithErrorThatThrows(NoSuchMethodError.class);
-      } else {
-        runResult.assertFailureWithErrorThatThrows(AbstractMethodError.class);
-      }
-    } else if (isR8 && parameters.isCfRuntime()) {
-      // TODO(b/254510678): R8 should not rebind to the library method.
-      runResult.assertFailureWithErrorThatThrows(NoClassDefFoundError.class);
+      runResult.assertFailureWithErrorThatThrows(AbstractMethodError.class);
     } else {
       runResult.assertSuccessWithOutputLines("Hello World");
     }
@@ -162,9 +155,7 @@
             inspector,
             parameters,
             Reference.method(
-                // TODO(b/254510678): Due to member rebinding, we rebind ProgramJoiner.foo() to
-                //  LibraryClass.foo().
-                Reference.classFromClass(isR8 ? LibraryClass.class : ProgramJoiner.class),
+                Reference.classFromClass(ProgramJoiner.class),
                 "foo",
                 Collections.emptyList(),
                 null));
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelIndirectTargetWithSameApiLevelTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelIndirectTargetWithSameApiLevelTest.java
index f6a0a49..d3af3d4 100644
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelIndirectTargetWithSameApiLevelTest.java
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelIndirectTargetWithSameApiLevelTest.java
@@ -125,9 +125,6 @@
   private void checkOutput(SingleTestRunResult<?> runResult, boolean isR8) {
     if (isGreaterOrEqualToMockLevel()) {
       runResult.assertSuccessWithOutputLines("LibraryClass::foo");
-    } else if (isR8 && parameters.isCfRuntime()) {
-      // TODO(b/254510678): R8 should not rebind to the library method.
-      runResult.assertFailureWithErrorThatThrows(NoClassDefFoundError.class);
     } else {
       runResult.assertSuccessWithOutputLines("Hello World");
     }
@@ -144,9 +141,7 @@
             inspector,
             parameters,
             Reference.method(
-                // TODO(b/254510678): Due to member rebinding, we rebind ProgramJoiner.foo() to
-                //  LibraryClass.foo().
-                Reference.classFromClass(isR8 ? LibraryClass.class : ProgramJoiner.class),
+                Reference.classFromClass(ProgramJoiner.class),
                 "foo",
                 Collections.emptyList(),
                 null));
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineSubTypeStaticReferenceTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineSubTypeStaticReferenceTest.java
index 19971c3..28a9abb 100644
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineSubTypeStaticReferenceTest.java
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineSubTypeStaticReferenceTest.java
@@ -20,7 +20,6 @@
 import com.android.tools.r8.testing.AndroidBuildVersion;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
-import java.lang.reflect.Method;
 import java.util.Collections;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -127,16 +126,11 @@
   }
 
   private void inspect(CodeInspector inspector, boolean isR8) throws Exception {
-    Method otherMethod = Sub.class.getMethod("otherMethod");
-    Method libraryMethod = LibraryClass.class.getMethod("foo");
-    // TODO(b/254510678): R8 should not member-rebind to a potential non-existing method.
     verifyThat(
             inspector,
             parameters,
-            isR8
-                ? Reference.methodFromMethod(libraryMethod)
-                : Reference.method(
-                    Reference.classFromClass(Sub.class), "foo", Collections.emptyList(), null))
+            Reference.method(
+                Reference.classFromClass(Sub.class), "foo", Collections.emptyList(), null))
         .isOutlinedFromUntil(Sub.class.getDeclaredMethod("otherMethod"), libraryApiLevel);
   }
 
diff --git a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/JavaTimeTest.java b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/JavaTimeTest.java
index d6ede8b..994d9cf 100644
--- a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/JavaTimeTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/JavaTimeTest.java
@@ -152,10 +152,12 @@
       String holder =
           libraryDesugaringSpecification.hasTimeDesugaring(parameters)
               ? "j$.time.temporal.TemporalAccessor"
-              : "java.time.temporal.TemporalAccessor";
+              : "com.android.tools.r8.desugar.desugaredlibrary.JavaTimeTest$TemporalAccessorImpl";
+      ClassSubject temporalAccessor = inspector.clazz(holder);
+      assertThat(temporalAccessor, isPresent());
       assertThat(
           inspector.clazz(TemporalAccessorImplSub.class).uniqueMethodWithFinalName("query"),
-          CodeMatchers.invokesMethod(null, holder, "query", null));
+          CodeMatchers.invokesMethod(null, temporalAccessor.getFinalName(), "query", null));
     } else {
       if (!parameters
               .getApiLevel()
diff --git a/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingFrontierTest.java b/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingFrontierTest.java
index 2584946..98bf6f6 100644
--- a/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingFrontierTest.java
+++ b/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingFrontierTest.java
@@ -4,7 +4,9 @@
 
 package com.android.tools.r8.memberrebinding;
 
+import static com.android.tools.r8.utils.codeinspector.CodeMatchers.invokesMethodWithHolderAndName;
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assume.assumeTrue;
 
@@ -14,7 +16,6 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
-import com.android.tools.r8.utils.codeinspector.CodeMatchers;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -43,7 +44,7 @@
         .compile()
         .apply(this::setupRunclasspath)
         .run(parameters.getRuntime(), Main.class)
-        .apply(result -> checkOutput(result, false));
+        .apply(this::checkOutput);
   }
 
   @Test
@@ -61,15 +62,13 @@
         .apply(this::setupRunclasspath)
         .inspect(
             inspector -> {
-              // TODO(b/254510678): We should not rebind to I.foo
               ClassSubject mainClass = inspector.clazz(Main.class);
               assertThat(mainClass, isPresent());
               MethodSubject foo = mainClass.mainMethod();
-              assertThat(
-                  foo, CodeMatchers.invokesMethodWithHolderAndName(typeName(I.class), "foo"));
+              assertThat(foo, not(invokesMethodWithHolderAndName(typeName(I.class), "foo")));
             })
         .run(parameters.getRuntime(), Main.class)
-        .apply(result -> checkOutput(result, true));
+        .apply(this::checkOutput);
   }
 
   private byte[] removeFooMethod(Class<?> clazz) throws Exception {
@@ -92,17 +91,12 @@
                     .addRunClasspathClassFileData(removeFooMethod(I.class)));
   }
 
-  private void checkOutput(SingleTestRunResult<?> runResult, boolean r8) {
+  private void checkOutput(SingleTestRunResult<?> runResult) {
     if (parameters.canUseDefaultAndStaticInterfaceMethods()) {
       runResult.assertSuccessWithOutputLines("I::foo");
       return;
     }
-    // TODO(b/254510678): We should not rebind to I.foo
-    if (r8) {
-      runResult.assertFailureWithErrorThatThrows(NoSuchMethodError.class);
-    } else {
-      runResult.assertSuccessWithOutputLines("Base::foo");
-    }
+    runResult.assertSuccessWithOutputLines("Base::foo");
   }
 
   private interface I {
diff --git a/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingTest.java b/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingTest.java
index 605ddf7..eb9a8dc 100644
--- a/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingTest.java
+++ b/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingTest.java
@@ -165,10 +165,13 @@
     assertTrue(iterator.next().holder().is("java.util.AbstractList"));
     assertTrue(iterator.next().holder().is("memberrebinding.subpackage.PublicClassInTheMiddle"));
     assertTrue(iterator.next().holder().is("memberrebinding.subpackage.PublicClassInTheMiddle"));
-    // For the next three - test that we re-bind to the lowest library class.
-    assertTrue(iterator.next().holder().is("memberrebindinglib.SubClass"));
-    assertTrue(iterator.next().holder().is("memberrebindinglib.SubClass"));
-    assertTrue(iterator.next().holder().is("memberrebindinglib.SubClass"));
+    // For the next three - test that we do not rebind but keep the static holder.
+    assertTrue(
+        iterator.next().holder().is("memberrebinding.SuperClassOfClassExtendsOtherLibraryClass"));
+    assertTrue(
+        iterator.next().holder().is("memberrebinding.SuperClassOfClassExtendsOtherLibraryClass"));
+    assertTrue(
+        iterator.next().holder().is("memberrebinding.SuperClassOfClassExtendsOtherLibraryClass"));
     // The next one is already precise.
     assertTrue(
         iterator.next().holder().is("memberrebinding.SuperClassOfClassExtendsOtherLibraryClass"));
@@ -177,8 +180,10 @@
     assertTrue(iterator.next().holder().is("memberrebindinglib.AnIndependentInterface"));
     // Some dispatches on classes.
     assertTrue(iterator.next().holder().is("java.lang.System"));
-    assertTrue(iterator.next().holder().is("memberrebindinglib.SubClass"));
-    assertTrue(iterator.next().holder().is("memberrebindinglib.ImplementedInProgramClass"));
+    assertTrue(
+        iterator.next().holder().is("memberrebinding.SuperClassOfClassExtendsOtherLibraryClass"));
+    assertTrue(
+        iterator.next().holder().is("memberrebinding.SuperClassOfClassExtendsOtherLibraryClass"));
     assertFalse(iterator.hasNext());
   }
 
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 d01d917..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
@@ -6,7 +6,6 @@
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
-import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.StringUtils;
 import com.google.common.collect.ImmutableList;
 import java.nio.file.Path;
@@ -62,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/resolution/duplicatedefinitions/MaximallySpecificSingleDominatingAfterJoinTest.java b/src/test/java/com/android/tools/r8/resolution/duplicatedefinitions/MaximallySpecificSingleDominatingAfterJoinTest.java
index cc39cfa..56095b3 100644
--- a/src/test/java/com/android/tools/r8/resolution/duplicatedefinitions/MaximallySpecificSingleDominatingAfterJoinTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/duplicatedefinitions/MaximallySpecificSingleDominatingAfterJoinTest.java
@@ -119,7 +119,11 @@
   @Test
   public void testR8() throws Exception {
     runTest(
-        testForR8(parameters.getBackend()).addKeepMainRule(Main.class), AbstractMethodError.class);
+        testForR8(parameters.getBackend()).addKeepMainRule(Main.class),
+        parameters.isDexRuntime() && parameters.getDexRuntimeVersion().isDalvik()
+            ? VerifyError.class
+            // TODO(b/214382176): Extend resolution to support multiple definition results.
+            : AbstractMethodError.class);
   }
 
   private void runTest(
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());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/transformers/ClassFileTransformer.java b/src/test/java/com/android/tools/r8/transformers/ClassFileTransformer.java
index 8108730..b72d822 100644
--- a/src/test/java/com/android/tools/r8/transformers/ClassFileTransformer.java
+++ b/src/test/java/com/android/tools/r8/transformers/ClassFileTransformer.java
@@ -1139,6 +1139,25 @@
         });
   }
 
+  public ClassFileTransformer removeCode(MethodPredicate predicate) {
+    return addMethodTransformer(
+        new MethodTransformer() {
+          @Override
+          public void visitCode() {
+            if (!MethodPredicate.testContext(predicate, getContext())) {
+              super.visitCode();
+            }
+          }
+
+          @Override
+          public void visitInsn(int opcode) {
+            if (!MethodPredicate.testContext(predicate, getContext())) {
+              super.visitInsn(opcode);
+            }
+          }
+        });
+  }
+
   public ClassFileTransformer transformInvokeDynamicInsnInMethod(
       String methodName, InvokeDynamicInsnTransform transform) {
     return addMethodTransformer(