diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 43fff83..12d6f8a 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.5.24";
+  public static final String LABEL = "1.5.25";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/MemberValuePropagation.java b/src/main/java/com/android/tools/r8/ir/optimize/MemberValuePropagation.java
index 44cdaf7..615b4c1 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/MemberValuePropagation.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/MemberValuePropagation.java
@@ -59,6 +59,20 @@
       this.type = type;
       this.rule = rule;
     }
+
+    @Override
+    public boolean equals(Object other) {
+      if (!(other instanceof ProguardMemberRuleLookup)) {
+        return false;
+      }
+      ProguardMemberRuleLookup otherLookup = (ProguardMemberRuleLookup) other;
+      return type == otherLookup.type && rule == otherLookup.rule;
+    }
+
+    @Override
+    public int hashCode() {
+      return type.ordinal() * 31 + rule.hashCode();
+    }
   }
 
   public MemberValuePropagation(AppView<AppInfoWithLiveness> appView) {
@@ -204,10 +218,15 @@
     if (!invokedHolder.isClassType()) {
       return;
     }
-    // TODO(b/130804193): search for all call targets and apply -assumenosideeffects if one of
-    //   call targets has a matching rule?
     DexEncodedMethod definition = current.lookupSingleTarget(appView, callingContext);
     ProguardMemberRuleLookup lookup = lookupMemberRule(definition);
+    if (lookup == null) {
+      // Since -assumenosideeffects rules are always applied to all overriding methods, we can
+      // simply check the target method, although this may be different from the dynamically
+      // targeted method.
+      DexEncodedMethod target = appView.definitionFor(invokedMethod);
+      lookup = lookupMemberRule(target);
+    }
     boolean invokeReplaced = false;
     if (lookup != null) {
       boolean outValueNullOrNotUsed = current.outValue() == null || !current.outValue().isUsed();
diff --git a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
index c32d23f..40152ab 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexAnnotation;
 import com.android.tools.r8.graph.DexAnnotationSet;
@@ -38,11 +39,13 @@
 import com.google.common.collect.Sets;
 import com.google.common.collect.Streams;
 import java.io.PrintStream;
+import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
+import java.util.Deque;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.IdentityHashMap;
@@ -181,6 +184,10 @@
       } else if (rule instanceof ProguardAssumeMayHaveSideEffectsRule
           || rule instanceof ProguardAssumeNoSideEffectRule) {
         markMatchingVisibleMethods(clazz, memberKeepRules, rule, null, true);
+        if (appView.appInfo().hasSubtyping()) {
+          markMatchingOverriddenMethods(
+              appView.appInfo().withSubtyping(), clazz, memberKeepRules, rule, null, true);
+        }
         markMatchingVisibleFields(clazz, memberKeepRules, rule, null, true);
       } else if (rule instanceof ClassMergingRule) {
         if (allRulesSatisfied(memberKeepRules, clazz)) {
@@ -488,7 +495,8 @@
       Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier,
       boolean includeLibraryClasses) {
     Set<Wrapper<DexMethod>> methodsMarked =
-        options.forceProguardCompatibility ? null : new HashSet<>();
+        options.forceProguardCompatibility || rule instanceof ProguardAssumeNoSideEffectRule
+            ? null : new HashSet<>();
     DexClass startingClass = clazz;
     while (clazz != null) {
       if (!includeLibraryClasses && clazz.isNotProgramClass()) {
@@ -515,6 +523,41 @@
     }
   }
 
+  private void markMatchingOverriddenMethods(
+      AppInfoWithSubtyping appInfoWithSubtyping,
+      DexClass clazz,
+      Collection<ProguardMemberRule> memberKeepRules,
+      ProguardConfigurationRule rule,
+      Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier,
+      boolean onlyIncludeProgramClasses) {
+    Set<DexType> visited = new HashSet<>();
+    Deque<DexType> worklist = new ArrayDeque<>();
+    // Intentionally skip the current `clazz`, assuming it's covered by markMatchingVisibleMethods.
+    worklist.addAll(appInfoWithSubtyping.allImmediateSubtypes(clazz.type));
+
+    while (!worklist.isEmpty()) {
+      DexType currentType = worklist.poll();
+      if (!visited.add(currentType)) {
+        continue;
+      }
+      DexClass currentClazz = appView.definitionFor(currentType);
+      if (currentClazz == null) {
+        continue;
+      }
+      if (!onlyIncludeProgramClasses && currentClazz.isNotProgramClass()) {
+        continue;
+      }
+      currentClazz
+          .virtualMethods()
+          .forEach(
+              method -> {
+                DexDefinition precondition = testAndGetPrecondition(method, preconditionSupplier);
+                markMethod(method, memberKeepRules, null, rule, precondition);
+              });
+      worklist.addAll(appInfoWithSubtyping.allImmediateSubtypes(currentClazz.type));
+    }
+  }
+
   private void markMatchingMethods(
       DexClass clazz,
       Collection<ProguardMemberRule> memberKeepRules,
diff --git a/src/test/java/com/android/tools/r8/shaking/assumenosideeffects/AssumenosideeffectsWithMultipleTargetsTest.java b/src/test/java/com/android/tools/r8/shaking/assumenosideeffects/AssumenosideeffectsWithMultipleTargetsTest.java
index 804fb9c..1d54c3c 100644
--- a/src/test/java/com/android/tools/r8/shaking/assumenosideeffects/AssumenosideeffectsWithMultipleTargetsTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/assumenosideeffects/AssumenosideeffectsWithMultipleTargetsTest.java
@@ -100,12 +100,6 @@
       throw new Unreachable();
     }
 
-    private static final String OUTPUT_WITH_INFO = StringUtils.lines(
-        "TestClass: message1",
-        "TestClass: message2",
-        "[TestClass] message3",
-        "The end"
-    );
     private static final String OUTPUT_WITH_PARTIAL_INFO = StringUtils.lines(
         "TestClass: message2",
         "The end"
@@ -121,8 +115,7 @@
       switch (this) {
         case RULE_THAT_DIRECTLY_REFERS_CLASS:
         case RULE_THAT_DIRECTLY_REFERS_INTERFACE:
-          // TODO(b/130804193): implicitly mark all call targets?
-          return OUTPUT_WITH_INFO;
+          return OUTPUT_WITHOUT_INFO;
         case RULE_WITH_IMPLEMENTS:
           return OUTPUT_WITH_PARTIAL_INFO;
         default:
@@ -136,37 +129,31 @@
 
       MethodSubject mainMethod = main.mainMethod();
       assertThat(mainMethod, isPresent());
-      int expectedInfoCallsInMainMethod = 0;
-      // TODO(b/130804193): implicitly mark all call targets?
-      if (isR8) {
-        switch (this) {
-          case RULE_THAT_DIRECTLY_REFERS_CLASS:
-          case RULE_THAT_DIRECTLY_REFERS_INTERFACE:
-            expectedInfoCallsInMainMethod = 2;
-            break;
-          case RULE_WITH_IMPLEMENTS:
-            expectedInfoCallsInMainMethod = 0;
-            break;
-          default:
-            throw new Unreachable();
-        }
-      }
       assertEquals(
-          expectedInfoCallsInMainMethod,
+          0,
           Streams.stream(mainMethod.iterateInstructions(
               i -> i.isInvoke() && i.getMethod().name.toString().equals("info"))).count());
 
       MethodSubject testInvokeInterface = main.uniqueMethodWithName("testInvokeInterface");
-      int expectedInfoCallsInInvokeInterfaceMethod = 0;
-      // Inlining of testInvokeInterface is out of control if !isR8.
       if (isR8) {
-        assertThat(testInvokeInterface, isPresent());
-        // TODO(b/130804193): implicitly mark all call targets?
-        expectedInfoCallsInInvokeInterfaceMethod = 1;
-        assertEquals(
-            expectedInfoCallsInInvokeInterfaceMethod,
-            Streams.stream(testInvokeInterface.iterateInstructions(
-                i -> i.isInvoke() && i.getMethod().name.toString().equals("info"))).count());
+        switch (this) {
+          case RULE_THAT_DIRECTLY_REFERS_CLASS:
+          case RULE_THAT_DIRECTLY_REFERS_INTERFACE:
+            assertThat(testInvokeInterface, not(isPresent()));
+            break;
+          case RULE_WITH_IMPLEMENTS:
+            assertThat(testInvokeInterface, isPresent());
+            // TODO(b/130804193): upwards propagation of member rules.
+            assertEquals(
+                1,
+                Streams.stream(testInvokeInterface.iterateInstructions(
+                    i -> i.isInvoke() && i.getMethod().name.toString().equals("info"))).count());
+            break;
+          default:
+            throw new Unreachable();
+        }
+      } else {
+        assertThat(testInvokeInterface, not(isPresent()));
       }
 
       FieldSubject tag = main.uniqueFieldWithName("TAG");