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 89681f0..0ed998a 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
@@ -311,7 +311,11 @@
     if (newResolutionResult == null
         || newResolutionResult
             .isAccessibleForVirtualDispatchFrom(context, appView.appInfo())
-            .isPossiblyFalse()) {
+            .isPossiblyFalse()
+        || !newResolutionResult
+            .getResolvedMethod()
+            .getAccessFlags()
+            .isAtLeastAsVisibleAs(resolutionResult.getResolvedMethod().getAccessFlags())) {
       return target;
     }
 
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/PrivateOverridePublicizerDevirtualizerTest.java b/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/PrivateOverridePublicizerDevirtualizerTest.java
index bef0cd5..86739dc 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/PrivateOverridePublicizerDevirtualizerTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/PrivateOverridePublicizerDevirtualizerTest.java
@@ -5,13 +5,11 @@
 package com.android.tools.r8.ir.optimize.devirtualize;
 
 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.NeverClassInline;
 import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.NoVerticalClassMerging;
-import com.android.tools.r8.R8TestRunResult;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
@@ -48,33 +46,25 @@
 
   @Test
   public void testR8() throws Exception {
-    R8TestRunResult runResult =
-        testForR8(parameters.getBackend())
-            .addInnerClasses(PrivateOverridePublicizerDevirtualizerTest.class)
-            .enableInliningAnnotations()
-            .enableNoVerticalClassMergingAnnotations()
-            .enableNeverClassInliningAnnotations()
-            .addKeepMainRule(Main.class)
-            .allowAccessModification()
-            .noMinification()
-            .setMinApi(parameters.getApiLevel())
-            .compile()
-            .inspect(
-                inspector -> {
-                  ClassSubject classA = inspector.clazz(A.class);
-                  assertThat(classA, isPresent());
-                  MethodSubject fooA = classA.uniqueMethodWithName("foo");
-                  // TODO(b/173812804): This should not be removed.
-                  assertThat(fooA, not(isPresent()));
-                })
-            .run(parameters.getRuntime(), Main.class);
-    if (parameters.isDexRuntime()) {
-      // TODO(b/173812804): This should not fail verification
-      runResult.assertFailureWithErrorThatThrows(VerifyError.class);
-    } else {
-      // TODO(b/173812804): This should have been A::foo, B::foo.
-      runResult.assertSuccessWithOutputLines("B::foo", "B::foo");
-    }
+    testForR8(parameters.getBackend())
+        .addInnerClasses(PrivateOverridePublicizerDevirtualizerTest.class)
+        .enableInliningAnnotations()
+        .enableNoVerticalClassMergingAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .addKeepMainRule(Main.class)
+        .allowAccessModification()
+        .noMinification()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(
+            inspector -> {
+              ClassSubject classA = inspector.clazz(A.class);
+              assertThat(classA, isPresent());
+              MethodSubject fooA = classA.uniqueMethodWithName("foo");
+              assertThat(fooA, isPresent());
+            })
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(EXPECTED);
   }
 
   @NeverClassInline