diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
index ca6c387..27a4893 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
@@ -126,8 +126,8 @@
         if (current.isInvokeSuper()) {
           InvokeSuper invoke = current.asInvokeSuper();
 
-          // Check if the instruction can be rewritten to invoke-super. This allows inlining of the
-          // enclosing method into contexts outside the current class.
+          // Check if the instruction can be rewritten to invoke-virtual. This allows inlining of
+          // the enclosing method into contexts outside the current class.
           if (options.testing.enableInvokeSuperToInvokeVirtualRewriting) {
             DexClassAndMethod singleTarget = invoke.lookupSingleTarget(appView, context);
             if (singleTarget != null) {
@@ -150,16 +150,19 @@
 
           // Rebind the invoke to the most specific target.
           DexMethod invokedMethod = invoke.getInvokedMethod();
-          DexClassAndMethod reboundTarget = rebindSuperInvokeToMostSpecific(invokedMethod, context);
-          if (reboundTarget != null
-              && reboundTarget.getReference() != invokedMethod
-              && !isRebindingNewClassIntoMainDex(context, reboundTarget.getReference())) {
-            it.replaceCurrentInstruction(
-                new InvokeSuper(
-                    reboundTarget.getReference(),
-                    invoke.outValue(),
-                    invoke.arguments(),
-                    reboundTarget.getHolder().isInterface()));
+          DexClass reboundTargetClass = rebindSuperInvokeToMostSpecific(invokedMethod, context);
+          if (reboundTargetClass != null) {
+            DexMethod reboundMethod =
+                invokedMethod.withHolder(reboundTargetClass, appView.dexItemFactory());
+            if (reboundMethod != invokedMethod
+                && !isRebindingNewClassIntoMainDex(context, reboundMethod)) {
+              it.replaceCurrentInstruction(
+                  new InvokeSuper(
+                      reboundMethod,
+                      invoke.outValue(),
+                      invoke.arguments(),
+                      reboundTargetClass.isInterface()));
+            }
           }
           continue;
         }
@@ -318,8 +321,7 @@
   }
 
   /** This rebinds invoke-super instructions to their most specific target. */
-  private DexClassAndMethod rebindSuperInvokeToMostSpecific(
-      DexMethod target, ProgramMethod context) {
+  private DexClass rebindSuperInvokeToMostSpecific(DexMethod target, ProgramMethod context) {
     DexClassAndMethod method = appView.appInfo().lookupSuperTarget(target, context);
     if (method == null) {
       return null;
@@ -336,7 +338,20 @@
       return null;
     }
 
-    return method;
+    if (method.getHolder().isLibraryClass()) {
+      // We've found a library class as the new holder of the method. Since the library can only
+      // rebind to the library class boundary. Search from the target upwards until we find a
+      // library class.
+      DexClass lowerBound = appView.definitionFor(target.getHolderType(), context);
+      while (lowerBound != null
+          && lowerBound.isProgramClass()
+          && lowerBound != method.getHolder()) {
+        lowerBound = appView.definitionFor(lowerBound.superType, lowerBound.asProgramClass());
+      }
+      return lowerBound;
+    }
+
+    return method.getHolder();
   }
 
   /**
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/DevirtualizeLibrarySuperTest.java b/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/DevirtualizeLibrarySuperTest.java
index cc04e23..e82bd6e 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/DevirtualizeLibrarySuperTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/DevirtualizeLibrarySuperTest.java
@@ -6,13 +6,13 @@
 
 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 com.android.tools.r8.NeverInline;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
-import com.android.tools.r8.ToolHelper.DexVm.Version;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import org.junit.Test;
@@ -46,15 +46,11 @@
         .compile()
         .inspect(
             inspector -> {
-              if (parameters.isCfRuntime()) {
-                return;
-              }
               MethodSubject fooMethod = inspector.clazz(Main.class).uniqueMethodWithName("foo");
               assertThat(fooMethod, isPresent());
-              // TODO(b/209060415): Should not have a static holder of `LibraryOverride`.
               assertThat(
                   fooMethod,
-                  invokesMethodWithHolderAndName(LibraryOverride.class.getTypeName(), "foo"));
+                  not(invokesMethodWithHolderAndName(LibraryOverride.class.getTypeName(), "foo")));
             })
         .applyIf(
             hasNewLibraryHierarchyOnClassPath,
@@ -71,16 +67,7 @@
                         .transform()))
         .run(parameters.getRuntime(), Main.class)
         .assertSuccessWithOutputLinesIf(hasNewLibraryHierarchyOnClassPath, "LibraryOverride::foo")
-        // TODO(b/209060415): Should not fail.
-        .applyIf(
-            !hasNewLibraryHierarchyOnClassPath,
-            result -> {
-              result.assertFailureWithErrorThatThrows(
-                  (parameters.getDexRuntimeVersion().isDalvik()
-                          || parameters.getDexRuntimeVersion().isNewerThanOrEqual(Version.V12_0_0)
-                      ? NoClassDefFoundError.class
-                      : VerifyError.class));
-            });
+        .assertSuccessWithOutputLinesIf(!hasNewLibraryHierarchyOnClassPath, "Library::foo");
   }
 
   public static class Library {