diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java
index f10a654..717ac38d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -287,6 +287,10 @@
     return Iterables.filter(virtualMethods(), predicate::test);
   }
 
+  public void addVirtualMethod(DexEncodedMethod method) {
+    methodCollection.addVirtualMethod(method);
+  }
+
   public void addVirtualMethods(Collection<DexEncodedMethod> methods) {
     methodCollection.addVirtualMethods(methods);
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
index b49abbe..5e6c879 100644
--- a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
@@ -694,10 +694,6 @@
     methodCollection.addMethod(method);
   }
 
-  public void addVirtualMethod(DexEncodedMethod virtualMethod) {
-    methodCollection.addVirtualMethod(virtualMethod);
-  }
-
   public void replaceVirtualMethod(
       DexMethod virtualMethod, Function<DexEncodedMethod, DexEncodedMethod> replacement) {
     methodCollection.replaceVirtualMethod(virtualMethod, replacement);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryOptimizationInfoInitializer.java b/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryOptimizationInfoInitializer.java
index df2c436..0c41415 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryOptimizationInfoInitializer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryOptimizationInfoInitializer.java
@@ -6,7 +6,6 @@
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
-import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexItemFactory.EnumMembers;
@@ -14,7 +13,6 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.analysis.type.DynamicType;
 import com.android.tools.r8.ir.analysis.value.AbstractValueFactory;
-import com.android.tools.r8.ir.analysis.value.objectstate.ObjectState;
 import com.android.tools.r8.ir.optimize.info.LibraryOptimizationInfoInitializerFeedback;
 import com.android.tools.r8.ir.optimize.info.field.EmptyInstanceFieldInitializationInfoCollection;
 import com.android.tools.r8.ir.optimize.info.field.InstanceFieldInitializationInfoCollection;
@@ -87,16 +85,6 @@
     }
   }
 
-  private void modelStaticFinalLibraryFields(Set<DexEncodedField> finalLibraryFields) {
-    for (DexEncodedField field : finalLibraryFields) {
-      if (field.isStatic()) {
-        feedback.recordLibraryFieldHasAbstractValue(
-            field,
-            abstractValueFactory.createSingleFieldValue(field.getReference(), ObjectState.empty()));
-      }
-    }
-  }
-
   private void modelLibraryMethodsNonNullParamOrThrow() {
     dexItemFactory.libraryMethodsNonNullParamOrThrow.forEach(
         (method, nonNullParamOrThrow) -> {
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 c731f7d..ffd9e4e 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -16,6 +16,8 @@
 import static java.util.Collections.emptySet;
 
 import com.android.tools.r8.Diagnostic;
+import com.android.tools.r8.androidapi.ComputedApiLevel;
+import com.android.tools.r8.androidapi.CovariantReturnTypeMethods;
 import com.android.tools.r8.cf.code.CfInstruction;
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.contexts.CompilationContext.MethodProcessingContext;
@@ -72,6 +74,7 @@
 import com.android.tools.r8.graph.LookupMethodTarget;
 import com.android.tools.r8.graph.LookupResult;
 import com.android.tools.r8.graph.LookupTarget;
+import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.graph.MethodAccessInfoCollection;
 import com.android.tools.r8.graph.MethodResolutionResult;
 import com.android.tools.r8.graph.MethodResolutionResult.FailedResolutionResult;
@@ -673,6 +676,17 @@
     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(
@@ -3554,9 +3568,8 @@
     includeMinimumKeepInfo(rootSet);
 
     if (mode.isInitialTreeShaking()) {
-      // This is simulating the effect of the "root set" applied rules.
-      // This is done only in the initial pass, in subsequent passes the "rules" are reapplied
-      // by iterating the instances.
+      // Amend library methods with covariant return types.
+      modelLibraryMethodsWithCovariantReturnTypes();
     } else if (appView.getKeepInfo() != null) {
       EnqueuerEvent preconditionEvent = UnconditionalKeepInfoEvent.get();
       appView
@@ -3598,6 +3611,30 @@
             this::recordDependentMinimumKeepInfo);
   }
 
+  private void modelLibraryMethodsWithCovariantReturnTypes() {
+    CovariantReturnTypeMethods.registerMethodsWithCovariantReturnType(
+        appView.dexItemFactory(),
+        method -> {
+          DexLibraryClass libraryClass =
+              DexLibraryClass.asLibraryClassOrNull(
+                  appView.appInfo().definitionForWithoutExistenceAssert(method.getHolderType()));
+          if (libraryClass == null) {
+            return;
+          }
+          // Check if the covariant method exists on the class.
+          DexEncodedMethod covariantMethod = libraryClass.lookupMethod(method);
+          if (covariantMethod != null) {
+            return;
+          }
+          libraryClass.addVirtualMethod(
+              DexEncodedMethod.builder()
+                  .setMethod(method)
+                  .setAccessFlags(MethodAccessFlags.builder().setPublic().build())
+                  .setApiLevelForDefinition(ComputedApiLevel.notSet())
+                  .build());
+        });
+  }
+
   private void applyMinimumKeepInfo(DexProgramClass clazz) {
     EnqueuerEvent preconditionEvent = UnconditionalKeepInfoEvent.get();
     KeepClassInfo.Joiner minimumKeepInfoForClass =
diff --git a/src/main/java/com/android/tools/r8/shaking/MissingClasses.java b/src/main/java/com/android/tools/r8/shaking/MissingClasses.java
index 85a1b2a..1932bd0 100644
--- a/src/main/java/com/android/tools/r8/shaking/MissingClasses.java
+++ b/src/main/java/com/android/tools/r8/shaking/MissingClasses.java
@@ -7,6 +7,7 @@
 import static com.android.tools.r8.ir.desugar.desugaredlibrary.apiconversion.DesugaredLibraryAPIConverter.DESCRIPTOR_VIVIFIED_PREFIX;
 import static com.android.tools.r8.utils.collections.IdentityHashSetFromMap.newProgramDerivedContextSet;
 
+import com.android.tools.r8.androidapi.CovariantReturnTypeMethods;
 import com.android.tools.r8.diagnostic.MissingDefinitionsDiagnostic;
 import com.android.tools.r8.diagnostic.internal.DefinitionContextUtils;
 import com.android.tools.r8.diagnostic.internal.MissingClassInfoImpl;
@@ -292,6 +293,9 @@
                 addWithRewrittenType(
                     allowedMissingClasses, conversions.getTo().getHolderType(), appView);
               });
+      CovariantReturnTypeMethods.registerMethodsWithCovariantReturnType(
+          dexItemFactory,
+          method -> method.getReferencedTypes().forEach(allowedMissingClasses::add));
       return allowedMissingClasses.build();
     }
 
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelCovariantReturnTypeTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelCovariantReturnTypeTest.java
index 0726238..ddba615 100644
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelCovariantReturnTypeTest.java
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelCovariantReturnTypeTest.java
@@ -11,7 +11,6 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.references.Reference;
-import com.android.tools.r8.utils.AndroidApiLevel;
 import java.lang.reflect.Method;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ConcurrentHashMap.KeySetView;
@@ -40,9 +39,6 @@
     testForR8(parameters.getBackend())
         .addProgramClasses(Main.class)
         .setMinApi(parameters.getApiLevel())
-        .applyIf(
-            parameters.isDexRuntime() && parameters.getApiLevel().isLessThan(AndroidApiLevel.N),
-            b -> b.addDontWarn(KeySetView.class))
         .addKeepMainRule(Main.class)
         .apply(ApiModelingTestHelper::enableApiCallerIdentification)
         .apply(
diff --git a/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideCovariantTest.java b/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideCovariantTest.java
index 23febd2..59fcf6d 100644
--- a/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideCovariantTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/LibraryMethodOverrideCovariantTest.java
@@ -10,7 +10,6 @@
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
-import com.android.tools.r8.TestRunResult;
 import com.android.tools.r8.ToolHelper.DexVm.Version;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ConcurrentHashMap.KeySetView;
@@ -61,14 +60,10 @@
         .compile()
         .addRunClasspathFiles(buildOnDexRuntime(parameters, LibraryUser.class))
         .run(parameters.getRuntime(), Main.class)
-        .assertFailureWithErrorThatMatchesIf(
-            parameters.isCfRuntime(), containsString("Hello World"))
-        .assertFailureWithErrorThatThrowsIf(
-            !supportsKeySetView() && parameters.isDexRuntime(), NoSuchMethodError.class)
-        // TODO(b/234579501): We fail to keep the library method override.
         .applyIf(
-            parameters.isDexRuntime() && supportsKeySetView(),
-            TestRunResult::assertSuccessWithEmptyOutput);
+            supportsKeySetView(),
+            result -> result.assertFailureWithErrorThatMatches(containsString("Hello World")),
+            result -> result.assertFailureWithErrorThatThrows(NoSuchMethodError.class));
   }
 
   private byte[] getMainWithoutSyntheticBridgeForKeySet() throws Exception {