diff --git a/src/main/java/com/android/tools/r8/graph/ImmediateProgramSubtypingInfo.java b/src/main/java/com/android/tools/r8/graph/ImmediateProgramSubtypingInfo.java
index fa003ea..07102c1 100644
--- a/src/main/java/com/android/tools/r8/graph/ImmediateProgramSubtypingInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/ImmediateProgramSubtypingInfo.java
@@ -46,12 +46,12 @@
   }
 
   public void forEachImmediateSuperClass(
-      DexProgramClass clazz, BiConsumer<? super DexType, ? super DexClass> consumer) {
+      DexClass clazz, BiConsumer<? super DexType, ? super DexClass> consumer) {
     forEachImmediateSuperClassMatching(clazz, (supertype, superclass) -> true, consumer);
   }
 
   public void forEachImmediateSuperClassMatching(
-      DexProgramClass clazz,
+      DexClass clazz,
       BiPredicate<? super DexType, ? super DexClass> predicate,
       BiConsumer<? super DexType, ? super DexClass> consumer) {
     clazz.forEachImmediateSupertype(
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagator.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagator.java
index 45420b6..227851f 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagator.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagator.java
@@ -22,12 +22,10 @@
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.Timing;
 import com.google.common.collect.Sets;
-import java.util.Collection;
 import java.util.List;
 import java.util.Set;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
-import java.util.function.Consumer;
 
 /** Optimization that propagates information about arguments from call sites to method entries. */
 public class ArgumentPropagator {
@@ -143,8 +141,8 @@
     // methods with constant parameters to methods with the constant parameters removed.
     Set<DexProgramClass> affectedClasses = Sets.newConcurrentHashSet();
     ArgumentPropagatorGraphLens graphLens =
-        optimizeMethodParameters(
-            stronglyConnectedProgramComponents, affectedClasses::add, executorService);
+        new ArgumentPropagatorProgramOptimizer(appView, immediateSubtypingInfo)
+            .run(stronglyConnectedProgramComponents, affectedClasses::add, executorService);
 
     // Find all the code objects that need reprocessing.
     new ArgumentPropagatorMethodReprocessingEnqueuer(appView)
@@ -185,25 +183,4 @@
     reprocessingCriteriaCollection = null;
     timing.end();
   }
-
-  /** Called by {@link IRConverter} to optimize method definitions. */
-  private ArgumentPropagatorGraphLens optimizeMethodParameters(
-      List<Set<DexProgramClass>> stronglyConnectedProgramComponents,
-      Consumer<DexProgramClass> affectedClassConsumer,
-      ExecutorService executorService)
-      throws ExecutionException {
-    Collection<ArgumentPropagatorGraphLens.Builder> partialGraphLensBuilders =
-        ThreadUtils.processItemsWithResults(
-            stronglyConnectedProgramComponents,
-            classes ->
-                new ArgumentPropagatorProgramOptimizer(appView)
-                    .optimize(classes, affectedClassConsumer),
-            executorService);
-
-    // Merge all the partial, disjoint graph lens builders into a single graph lens.
-    ArgumentPropagatorGraphLens.Builder graphLensBuilder =
-        ArgumentPropagatorGraphLens.builder(appView);
-    partialGraphLensBuilders.forEach(graphLensBuilder::mergeDisjoint);
-    return graphLensBuilder.build();
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorProgramOptimizer.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorProgramOptimizer.java
index f469ddc..fa8114f 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorProgramOptimizer.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorProgramOptimizer.java
@@ -7,10 +7,13 @@
 import static com.android.tools.r8.utils.MapUtils.ignoreKey;
 
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexMethodSignature;
 import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
 import com.android.tools.r8.graph.ObjectAllocationInfoCollection;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.graph.RewrittenPrototypeDescription.ArgumentInfoCollection;
@@ -18,341 +21,428 @@
 import com.android.tools.r8.ir.analysis.value.AbstractValue;
 import com.android.tools.r8.ir.optimize.info.CallSiteOptimizationInfo;
 import com.android.tools.r8.ir.optimize.info.ConcreteCallSiteOptimizationInfo;
+import com.android.tools.r8.optimize.argumentpropagation.ArgumentPropagatorGraphLens.Builder;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.BooleanBox;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.Pair;
+import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.collections.DexMethodSignatureSet;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
 import it.unimi.dsi.fastutil.ints.IntArraySet;
 import it.unimi.dsi.fastutil.ints.IntSet;
 import it.unimi.dsi.fastutil.ints.IntSets;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
+import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
 import java.util.function.Consumer;
 import java.util.function.IntPredicate;
 
 public class ArgumentPropagatorProgramOptimizer {
 
   private final AppView<AppInfoWithLiveness> appView;
+  private final ImmediateProgramSubtypingInfo immediateSubtypingInfo;
 
-  private final DexItemFactory dexItemFactory;
+  private final Map<DexClass, DexMethodSignatureSet> libraryMethods = new ConcurrentHashMap<>();
 
-  private final InternalOptions options;
-
-  private final Map<DexMethodSignature, IntSet> removableVirtualMethodParameters = new HashMap<>();
-
-  // Reserved names, i.e., mappings from pairs (old method signature, number of removed arguments)
-  // to the new method signature for that method.
-  private final Map<DexMethodSignature, Map<IntSet, DexMethodSignature>> newMethodSignatures =
-      new HashMap<>();
-
-  // Occupied method signatures (inverse of reserved names). Used to effectively check if a given
-  // method signature is already reserved.
-  private final Map<DexMethodSignature, Pair<IntSet, DexMethodSignature>> occupiedMethodSignatures =
-      new HashMap<>();
-
-  public ArgumentPropagatorProgramOptimizer(AppView<AppInfoWithLiveness> appView) {
+  public ArgumentPropagatorProgramOptimizer(
+      AppView<AppInfoWithLiveness> appView, ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
     this.appView = appView;
-    this.dexItemFactory = appView.dexItemFactory();
-    this.options = appView.options();
+    this.immediateSubtypingInfo = immediateSubtypingInfo;
   }
 
-  // TODO(b/190154391): Remove unused parameters by simulating they are constant.
-  // TODO(b/190154391): Strengthen the static type of parameters.
-  // TODO(b/190154391): If we learn that a method returns a constant, then consider changing its
-  //  return type to void.
-  // TODO(b/69963623): If we optimize a method to be unconditionally throwing (because it has a
-  //  bottom parameter), then for each caller that becomes unconditionally throwing, we could
-  //  also enqueue the caller's callers for reprocessing. This would propagate the throwing
-  //  information to all call sites.
-  public ArgumentPropagatorGraphLens.Builder optimize(
-      Set<DexProgramClass> stronglyConnectedProgramClasses,
-      Consumer<DexProgramClass> affectedClassConsumer) {
-    // First reserve pinned method signatures.
-    reservePinnedMethodSignatures(stronglyConnectedProgramClasses);
+  public ArgumentPropagatorGraphLens run(
+      List<Set<DexProgramClass>> stronglyConnectedProgramComponents,
+      Consumer<DexProgramClass> affectedClassConsumer,
+      ExecutorService executorService)
+      throws ExecutionException {
+    Collection<Builder> partialGraphLensBuilders =
+        ThreadUtils.processItemsWithResults(
+            stronglyConnectedProgramComponents,
+            classes ->
+                new StronglyConnectedComponentOptimizer().optimize(classes, affectedClassConsumer),
+            executorService);
 
-    // To ensure that we preserve the overriding relationships between methods, we only remove a
-    // constant or unused parameter from a virtual method when it can be removed from all other
-    // virtual methods in the component with the same method signature.
-    computeRemovableVirtualMethodParameters(stronglyConnectedProgramClasses);
-
-    // Build a graph lens while visiting the classes in the component.
-    // TODO(b/190154391): Consider visiting the interfaces first, and then processing the
-    //  (non-interface) classes in top-down order to reduce the amount of reserved names.
-    ArgumentPropagatorGraphLens.Builder partialGraphLensBuilder =
+    // Merge all the partial, disjoint graph lens builders into a single graph lens.
+    ArgumentPropagatorGraphLens.Builder graphLensBuilder =
         ArgumentPropagatorGraphLens.builder(appView);
-    for (DexProgramClass clazz : stronglyConnectedProgramClasses) {
-      if (visitClass(clazz, partialGraphLensBuilder)) {
-        affectedClassConsumer.accept(clazz);
-      }
-    }
-    return partialGraphLensBuilder;
+    partialGraphLensBuilders.forEach(graphLensBuilder::mergeDisjoint);
+    return graphLensBuilder.build();
   }
 
-  private void reservePinnedMethodSignatures(Set<DexProgramClass> stronglyConnectedProgramClasses) {
-    DexMethodSignatureSet pinnedMethodSignatures = DexMethodSignatureSet.create();
-    for (DexProgramClass clazz : stronglyConnectedProgramClasses) {
-      clazz.forEachProgramMethod(
-          method -> {
-            if (!appView.getKeepInfo(method).isShrinkingAllowed(options)) {
-              pinnedMethodSignatures.add(method.getMethodSignature());
+  private DexMethodSignatureSet getOrComputeLibraryMethods(DexClass clazz) {
+    DexMethodSignatureSet libraryMethodsOnClass = libraryMethods.get(clazz);
+    if (libraryMethodsOnClass != null) {
+      return libraryMethodsOnClass;
+    }
+    return computeLibraryMethods(clazz);
+  }
+
+  private DexMethodSignatureSet computeLibraryMethods(DexClass clazz) {
+    DexMethodSignatureSet libraryMethodsOnClass = DexMethodSignatureSet.create();
+    immediateSubtypingInfo.forEachImmediateSuperClassMatching(
+        clazz,
+        (supertype, superclass) -> superclass != null,
+        (supertype, superclass) ->
+            libraryMethodsOnClass.addAll(getOrComputeLibraryMethods(superclass)));
+    clazz.forEachClassMethodMatching(
+        DexEncodedMethod::belongsToVirtualPool,
+        method -> libraryMethodsOnClass.add(method.getMethodSignature()));
+    libraryMethods.put(clazz, libraryMethodsOnClass);
+    return libraryMethodsOnClass;
+  }
+
+  public class StronglyConnectedComponentOptimizer {
+
+    private final DexItemFactory dexItemFactory;
+    private final InternalOptions options;
+
+    private final Map<DexMethodSignature, IntSet> removableVirtualMethodParameters =
+        new HashMap<>();
+
+    // Reserved names, i.e., mappings from pairs (old method signature, number of removed arguments)
+    // to the new method signature for that method.
+    private final Map<DexMethodSignature, Map<IntSet, DexMethodSignature>> newMethodSignatures =
+        new HashMap<>();
+
+    // Occupied method signatures (inverse of reserved names). Used to effectively check if a given
+    // method signature is already reserved.
+    private final Map<DexMethodSignature, Pair<IntSet, DexMethodSignature>>
+        occupiedMethodSignatures = new HashMap<>();
+
+    public StronglyConnectedComponentOptimizer() {
+      this.dexItemFactory = appView.dexItemFactory();
+      this.options = appView.options();
+    }
+
+    // TODO(b/190154391): Remove unused parameters by simulating they are constant.
+    // TODO(b/190154391): Strengthen the static type of parameters.
+    // TODO(b/190154391): If we learn that a method returns a constant, then consider changing its
+    //  return type to void.
+    // TODO(b/69963623): If we optimize a method to be unconditionally throwing (because it has a
+    //  bottom parameter), then for each caller that becomes unconditionally throwing, we could
+    //  also enqueue the caller's callers for reprocessing. This would propagate the throwing
+    //  information to all call sites.
+    // TODO(b/190154391): If we learn that a parameter of an instance initializer is constant, and
+    //  this parameter is assigned to a field on the class, and this field does not have any other
+    //  writes in the program, then we should replace all field reads by the constant value and
+    // prune
+    //  the field. Alternatively, we could consider building flow constraints for field assignments,
+    //  similarly to the way we deal with call chains in argument propagation. If a field is only
+    //  assigned the parameter of a given method, we would add the flow constraint "parameter p ->
+    //  field f".
+    public ArgumentPropagatorGraphLens.Builder optimize(
+        Set<DexProgramClass> stronglyConnectedProgramClasses,
+        Consumer<DexProgramClass> affectedClassConsumer) {
+      // First reserve pinned method signatures.
+      reservePinnedMethodSignatures(stronglyConnectedProgramClasses);
+
+      // To ensure that we preserve the overriding relationships between methods, we only remove a
+      // constant or unused parameter from a virtual method when it can be removed from all other
+      // virtual methods in the component with the same method signature.
+      computeRemovableVirtualMethodParameters(stronglyConnectedProgramClasses);
+
+      // Build a graph lens while visiting the classes in the component.
+      // TODO(b/190154391): Consider visiting the interfaces first, and then processing the
+      //  (non-interface) classes in top-down order to reduce the amount of reserved names.
+      ArgumentPropagatorGraphLens.Builder partialGraphLensBuilder =
+          ArgumentPropagatorGraphLens.builder(appView);
+      for (DexProgramClass clazz : stronglyConnectedProgramClasses) {
+        if (visitClass(clazz, partialGraphLensBuilder)) {
+          affectedClassConsumer.accept(clazz);
+        }
+      }
+      return partialGraphLensBuilder;
+    }
+
+    private void reservePinnedMethodSignatures(
+        Set<DexProgramClass> stronglyConnectedProgramClasses) {
+      DexMethodSignatureSet pinnedMethodSignatures = DexMethodSignatureSet.create();
+      Set<DexClass> seenLibraryClasses = Sets.newIdentityHashSet();
+      for (DexProgramClass clazz : stronglyConnectedProgramClasses) {
+        clazz.forEachProgramMethod(
+            method -> {
+              if (!appView.getKeepInfo(method).isShrinkingAllowed(options)) {
+                pinnedMethodSignatures.add(method.getMethodSignature());
+              }
+            });
+        immediateSubtypingInfo.forEachImmediateSuperClassMatching(
+            clazz,
+            (supertype, superclass) ->
+                superclass != null
+                    && !superclass.isProgramClass()
+                    && seenLibraryClasses.add(superclass),
+            (supertype, superclass) ->
+                pinnedMethodSignatures.addAll(getOrComputeLibraryMethods(superclass)));
+      }
+      pinnedMethodSignatures.forEach(
+          signature -> reserveMethodSignature(signature, signature, IntSets.EMPTY_SET));
+    }
+
+    private void reserveMethodSignature(
+        DexMethodSignature newMethodSignature,
+        DexMethodSignature originalMethodSignature,
+        IntSet removedParameterIndices) {
+      // Record that methods with the given signature and removed parameters should be mapped to the
+      // new signature.
+      newMethodSignatures
+          .computeIfAbsent(originalMethodSignature, ignoreKey(HashMap::new))
+          .put(removedParameterIndices, newMethodSignature);
+
+      // Record that the new method signature is used, by a method with the old signature that had
+      // the
+      // given removed parameters.
+      occupiedMethodSignatures.put(
+          newMethodSignature, new Pair<>(removedParameterIndices, originalMethodSignature));
+    }
+
+    private void computeRemovableVirtualMethodParameters(
+        Set<DexProgramClass> stronglyConnectedProgramClasses) {
+      // Group the virtual methods in the component by their signatures.
+      Map<DexMethodSignature, ProgramMethodSet> virtualMethodsBySignature =
+          computeVirtualMethodsBySignature(stronglyConnectedProgramClasses);
+      virtualMethodsBySignature.forEach(
+          (signature, methods) -> {
+            // Check that there are no keep rules that prohibit parameter removal from any of the
+            // methods.
+            if (Iterables.any(methods, method -> !isParameterRemovalAllowed(method))) {
+              return;
+            }
+
+            // Find the parameters that are constant or unused in all methods.
+            IntSet removableVirtualMethodParametersInAllMethods = new IntArraySet();
+            for (int parameterIndex = 1;
+                parameterIndex < signature.getProto().getArity() + 1;
+                parameterIndex++) {
+              if (canRemoveParameterFromVirtualMethods(parameterIndex, methods)) {
+                removableVirtualMethodParametersInAllMethods.add(parameterIndex);
+              }
+            }
+
+            // If any parameters could be removed, record it.
+            if (!removableVirtualMethodParametersInAllMethods.isEmpty()) {
+              removableVirtualMethodParameters.put(
+                  signature, removableVirtualMethodParametersInAllMethods);
             }
           });
     }
-    pinnedMethodSignatures.forEach(
-        signature -> reserveMethodSignature(signature, signature, IntSets.EMPTY_SET));
-  }
 
-  private void reserveMethodSignature(
-      DexMethodSignature newMethodSignature,
-      DexMethodSignature originalMethodSignature,
-      IntSet removedParameterIndices) {
-    // Record that methods with the given signature and removed parameters should be mapped to the
-    // new signature.
-    newMethodSignatures
-        .computeIfAbsent(originalMethodSignature, ignoreKey(HashMap::new))
-        .put(removedParameterIndices, newMethodSignature);
+    private Map<DexMethodSignature, ProgramMethodSet> computeVirtualMethodsBySignature(
+        Set<DexProgramClass> stronglyConnectedProgramClasses) {
+      Map<DexMethodSignature, ProgramMethodSet> virtualMethodsBySignature = new HashMap<>();
+      for (DexProgramClass clazz : stronglyConnectedProgramClasses) {
+        clazz.forEachProgramVirtualMethod(
+            method ->
+                virtualMethodsBySignature
+                    .computeIfAbsent(
+                        method.getMethodSignature(), ignoreKey(ProgramMethodSet::create))
+                    .add(method));
+      }
+      return virtualMethodsBySignature;
+    }
 
-    // Record that the new method signature is used, by a method with the old signature that had the
-    // given removed parameters.
-    occupiedMethodSignatures.put(
-        newMethodSignature, new Pair<>(removedParameterIndices, originalMethodSignature));
-  }
+    private boolean isParameterRemovalAllowed(ProgramMethod method) {
+      return appView.getKeepInfo(method).isParameterRemovalAllowed(options)
+          && !method.getDefinition().isLibraryMethodOverride().isPossiblyTrue();
+    }
 
-  private void computeRemovableVirtualMethodParameters(
-      Set<DexProgramClass> stronglyConnectedProgramClasses) {
-    // Group the virtual methods in the component by their signatures.
-    Map<DexMethodSignature, ProgramMethodSet> virtualMethodsBySignature =
-        computeVirtualMethodsBySignature(stronglyConnectedProgramClasses);
-    virtualMethodsBySignature.forEach(
-        (signature, methods) -> {
-          // Check that there are no keep rules that prohibit parameter removal from any of the
-          // methods.
-          if (Iterables.any(methods, method -> !isParameterRemovalAllowed(method))) {
-            return;
-          }
-
-          // Find the parameters that are constant or unused in all methods.
-          IntSet removableVirtualMethodParametersInAllMethods = new IntArraySet();
-          for (int parameterIndex = 1;
-              parameterIndex < signature.getProto().getArity() + 1;
-              parameterIndex++) {
-            if (canRemoveParameterFromVirtualMethods(parameterIndex, methods)) {
-              removableVirtualMethodParametersInAllMethods.add(parameterIndex);
+    private boolean canRemoveParameterFromVirtualMethods(
+        int parameterIndex, ProgramMethodSet methods) {
+      for (ProgramMethod method : methods) {
+        if (method.getDefinition().isAbstract()) {
+          DexProgramClass holder = method.getHolder();
+          if (holder.isInterface()) {
+            ObjectAllocationInfoCollection objectAllocationInfoCollection =
+                appView.appInfo().getObjectAllocationInfoCollection();
+            if (objectAllocationInfoCollection.isImmediateInterfaceOfInstantiatedLambda(holder)) {
+              return false;
             }
           }
-
-          // If any parameters could be removed, record it.
-          if (!removableVirtualMethodParametersInAllMethods.isEmpty()) {
-            removableVirtualMethodParameters.put(
-                signature, removableVirtualMethodParametersInAllMethods);
-          }
-        });
-  }
-
-  private Map<DexMethodSignature, ProgramMethodSet> computeVirtualMethodsBySignature(
-      Set<DexProgramClass> stronglyConnectedProgramClasses) {
-    Map<DexMethodSignature, ProgramMethodSet> virtualMethodsBySignature = new HashMap<>();
-    for (DexProgramClass clazz : stronglyConnectedProgramClasses) {
-      clazz.forEachProgramVirtualMethod(
-          method ->
-              virtualMethodsBySignature
-                  .computeIfAbsent(method.getMethodSignature(), ignoreKey(ProgramMethodSet::create))
-                  .add(method));
-    }
-    return virtualMethodsBySignature;
-  }
-
-  private boolean isParameterRemovalAllowed(ProgramMethod method) {
-    return appView.getKeepInfo(method).isParameterRemovalAllowed(options)
-        && !method.getDefinition().isLibraryMethodOverride().isPossiblyTrue();
-  }
-
-  private boolean canRemoveParameterFromVirtualMethods(
-      int parameterIndex, ProgramMethodSet methods) {
-    for (ProgramMethod method : methods) {
-      if (method.getDefinition().isAbstract()) {
-        DexProgramClass holder = method.getHolder();
-        if (holder.isInterface()) {
-          ObjectAllocationInfoCollection objectAllocationInfoCollection =
-              appView.appInfo().getObjectAllocationInfoCollection();
-          if (objectAllocationInfoCollection.isImmediateInterfaceOfInstantiatedLambda(holder)) {
-            return false;
-          }
-        }
-        // OK, this parameter can be removed.
-        continue;
-      }
-      CallSiteOptimizationInfo optimizationInfo =
-          method.getDefinition().getCallSiteOptimizationInfo();
-      if (optimizationInfo.isConcreteCallSiteOptimizationInfo()) {
-        ConcreteCallSiteOptimizationInfo concreteOptimizationInfo =
-            optimizationInfo.asConcreteCallSiteOptimizationInfo();
-        AbstractValue abstractValue =
-            concreteOptimizationInfo.getAbstractArgumentValue(parameterIndex);
-        if (abstractValue.isSingleValue()
-            && abstractValue.asSingleValue().isMaterializableInContext(appView, method)) {
-          // OK, this parameter has a constant value and can be removed.
+          // OK, this parameter can be removed.
           continue;
         }
-      }
-      return false;
-    }
-    return true;
-  }
-
-  // Returns true if the class was changed as a result of argument propagation.
-  private boolean visitClass(
-      DexProgramClass clazz, ArgumentPropagatorGraphLens.Builder partialGraphLensBuilder) {
-    BooleanBox affected = new BooleanBox();
-    clazz.forEachProgramMethod(
-        method -> {
-          ArgumentInfoCollection removableParameters =
-              method.getDefinition().belongsToDirectPool()
-                  ? computeRemovableParametersFromDirectMethod(method)
-                  : computeRemovableParametersFromVirtualMethod(method);
-          DexMethod newMethodSignature = getNewMethodSignature(method, removableParameters);
-          if (newMethodSignature != method.getReference()) {
-            partialGraphLensBuilder.recordMove(
-                method.getReference(), newMethodSignature, removableParameters);
-            affected.set();
+        CallSiteOptimizationInfo optimizationInfo =
+            method.getDefinition().getCallSiteOptimizationInfo();
+        if (optimizationInfo.isConcreteCallSiteOptimizationInfo()) {
+          ConcreteCallSiteOptimizationInfo concreteOptimizationInfo =
+              optimizationInfo.asConcreteCallSiteOptimizationInfo();
+          AbstractValue abstractValue =
+              concreteOptimizationInfo.getAbstractArgumentValue(parameterIndex);
+          if (abstractValue.isSingleValue()
+              && abstractValue.asSingleValue().isMaterializableInContext(appView, method)) {
+            // OK, this parameter has a constant value and can be removed.
+            continue;
           }
-        });
-    return affected.get();
-  }
-
-  private DexMethod getNewMethodSignature(
-      ProgramMethod method, ArgumentInfoCollection removableParameters) {
-    DexMethodSignature methodSignatureWithoutParametersRemoved = method.getMethodSignature();
-    IntSet removableParameterIndices = removableParameters.getKeys();
-
-    // Check if there is a reserved signature for this already.
-    DexMethodSignature reservedSignature =
-        newMethodSignatures
-            .getOrDefault(methodSignatureWithoutParametersRemoved, Collections.emptyMap())
-            .get(removableParameterIndices);
-    if (reservedSignature != null) {
-      return reservedSignature.withHolder(method.getHolderType(), dexItemFactory);
+        }
+        return false;
+      }
+      return true;
     }
 
-    DexMethod methodReferenceWithParametersRemoved =
-        removableParameters.rewriteMethod(method, dexItemFactory);
-    DexMethodSignature methodSignatureWithParametersRemoved =
-        methodReferenceWithParametersRemoved.getSignature();
+    // Returns true if the class was changed as a result of argument propagation.
+    private boolean visitClass(
+        DexProgramClass clazz, ArgumentPropagatorGraphLens.Builder partialGraphLensBuilder) {
+      BooleanBox affected = new BooleanBox();
+      clazz.forEachProgramMethod(
+          method -> {
+            ArgumentInfoCollection removableParameters =
+                method.getDefinition().belongsToDirectPool()
+                    ? computeRemovableParametersFromDirectMethod(method)
+                    : computeRemovableParametersFromVirtualMethod(method);
+            DexMethod newMethodSignature = getNewMethodSignature(method, removableParameters);
+            if (newMethodSignature != method.getReference()) {
+              partialGraphLensBuilder.recordMove(
+                  method.getReference(), newMethodSignature, removableParameters);
+              affected.set();
+            }
+          });
+      return affected.get();
+    }
 
-    // Find a method signature. First check if the current signature is available.
-    if (!occupiedMethodSignatures.containsKey(methodSignatureWithParametersRemoved)) {
+    private DexMethod getNewMethodSignature(
+        ProgramMethod method, ArgumentInfoCollection removableParameters) {
+      DexMethodSignature methodSignatureWithoutParametersRemoved = method.getMethodSignature();
+      IntSet removableParameterIndices = removableParameters.getKeys();
+
+      // Check if there is a reserved signature for this already.
+      DexMethodSignature reservedSignature =
+          newMethodSignatures
+              .getOrDefault(methodSignatureWithoutParametersRemoved, Collections.emptyMap())
+              .get(removableParameterIndices);
+      if (reservedSignature != null) {
+        return reservedSignature.withHolder(method.getHolderType(), dexItemFactory);
+      }
+
+      DexMethod methodReferenceWithParametersRemoved =
+          removableParameters.rewriteMethod(method, dexItemFactory);
+      DexMethodSignature methodSignatureWithParametersRemoved =
+          methodReferenceWithParametersRemoved.getSignature();
+
+      // Find a method signature. First check if the current signature is available.
+      if (!occupiedMethodSignatures.containsKey(methodSignatureWithParametersRemoved)) {
+        reserveMethodSignature(
+            methodSignatureWithParametersRemoved,
+            methodSignatureWithoutParametersRemoved,
+            removableParameterIndices);
+        return methodReferenceWithParametersRemoved;
+      }
+
+      Pair<IntSet, DexMethodSignature> occupant =
+          occupiedMethodSignatures.get(methodSignatureWithParametersRemoved);
+      // In this case we should have found a reserved method signature above.
+      assert !(occupant.getFirst().equals(removableParameterIndices)
+          && occupant.getSecond().equals(methodSignatureWithoutParametersRemoved));
+
+      // We need to find a new name for this method, since the signature is already occupied.
+      // TODO(b/190154391): Instead of generating a new name, we could also try permuting the order
+      // of
+      //  parameters.
+      DexMethod newMethod =
+          dexItemFactory.createFreshMethodNameWithoutHolder(
+              method.getName().toString(),
+              methodReferenceWithParametersRemoved.getProto(),
+              method.getHolderType(),
+              candidate -> {
+                Pair<IntSet, DexMethodSignature> candidateOccupant =
+                    occupiedMethodSignatures.get(candidate.getSignature());
+                if (candidateOccupant == null) {
+                  return true;
+                }
+                return candidateOccupant.getFirst().equals(removableParameterIndices)
+                    && candidateOccupant
+                        .getSecond()
+                        .equals(methodSignatureWithoutParametersRemoved);
+              });
+
+      // Reserve the newly generated method signature.
       reserveMethodSignature(
-          methodSignatureWithParametersRemoved,
+          newMethod.getSignature(),
           methodSignatureWithoutParametersRemoved,
           removableParameterIndices);
-      return methodReferenceWithParametersRemoved;
+
+      return newMethod;
     }
 
-    Pair<IntSet, DexMethodSignature> occupant =
-        occupiedMethodSignatures.get(methodSignatureWithParametersRemoved);
-    // In this case we should have found a reserved method signature above.
-    assert !(occupant.getFirst().equals(removableParameterIndices)
-        && occupant.getSecond().equals(methodSignatureWithoutParametersRemoved));
-
-    // We need to find a new name for this method, since the signature is already occupied.
-    // TODO(b/190154391): Instead of generating a new name, we could also try permuting the order of
-    //  parameters.
-    DexMethod newMethod =
-        dexItemFactory.createFreshMethodNameWithoutHolder(
-            method.getName().toString(),
-            methodReferenceWithParametersRemoved.getProto(),
-            method.getHolderType(),
-            candidate -> {
-              Pair<IntSet, DexMethodSignature> candidateOccupant =
-                  occupiedMethodSignatures.get(candidate.getSignature());
-              if (candidateOccupant == null) {
-                return true;
-              }
-              return candidateOccupant.getFirst().equals(removableParameterIndices)
-                  && candidateOccupant.getSecond().equals(methodSignatureWithoutParametersRemoved);
-            });
-
-    // Reserve the newly generated method signature.
-    reserveMethodSignature(
-        newMethod.getSignature(),
-        methodSignatureWithoutParametersRemoved,
-        removableParameterIndices);
-
-    return newMethod;
-  }
-
-  private ArgumentInfoCollection computeRemovableParametersFromDirectMethod(ProgramMethod method) {
-    assert method.getDefinition().belongsToDirectPool();
-    if (method.getDefinition().isInstanceInitializer()) {
+    private ArgumentInfoCollection computeRemovableParametersFromDirectMethod(
+        ProgramMethod method) {
+      assert method.getDefinition().belongsToDirectPool();
       // TODO(b/190154391): Allow parameter removal from initializers. We need to guarantee absence
       //  of collisions since initializers can't be renamed.
-      return ArgumentInfoCollection.empty();
-    }
-    return computeRemovableParametersFromMethod(method);
-  }
-
-  private ArgumentInfoCollection computeRemovableParametersFromVirtualMethod(ProgramMethod method) {
-    IntSet removableParameterIndices =
-        removableVirtualMethodParameters.getOrDefault(
-            method.getMethodSignature(), IntSets.EMPTY_SET);
-    if (removableParameterIndices.isEmpty()) {
-      return ArgumentInfoCollection.empty();
+      if (!appView.getKeepInfo(method).isParameterRemovalAllowed(options)
+          || method.getDefinition().isInstanceInitializer()) {
+        return ArgumentInfoCollection.empty();
+      }
+      return computeRemovableParametersFromMethod(method);
     }
 
-    if (method.getAccessFlags().isAbstract()) {
-      // Treat the parameters as unused.
+    private ArgumentInfoCollection computeRemovableParametersFromVirtualMethod(
+        ProgramMethod method) {
+      IntSet removableParameterIndices =
+          removableVirtualMethodParameters.getOrDefault(
+              method.getMethodSignature(), IntSets.EMPTY_SET);
+      if (removableParameterIndices.isEmpty()) {
+        return ArgumentInfoCollection.empty();
+      }
+
+      if (method.getAccessFlags().isAbstract()) {
+        // Treat the parameters as unused.
+        ArgumentInfoCollection.Builder removableParametersBuilder =
+            ArgumentInfoCollection.builder();
+        for (int removableParameterIndex : removableParameterIndices) {
+          removableParametersBuilder.addArgumentInfo(
+              removableParameterIndex,
+              RemovedArgumentInfo.builder()
+                  .setType(method.getArgumentType(removableParameterIndex))
+                  .build());
+        }
+        return removableParametersBuilder.build();
+      }
+
+      ArgumentInfoCollection removableParameters =
+          computeRemovableParametersFromMethod(method, removableParameterIndices::contains);
+      assert removableParameters.size() == removableParameterIndices.size();
+      return removableParameters;
+    }
+
+    private ArgumentInfoCollection computeRemovableParametersFromMethod(ProgramMethod method) {
+      return computeRemovableParametersFromMethod(method, parameterIndex -> true);
+    }
+
+    private ArgumentInfoCollection computeRemovableParametersFromMethod(
+        ProgramMethod method, IntPredicate removableParameterIndices) {
+      ConcreteCallSiteOptimizationInfo optimizationInfo =
+          method.getDefinition().getCallSiteOptimizationInfo().asConcreteCallSiteOptimizationInfo();
+      if (optimizationInfo == null) {
+        return ArgumentInfoCollection.empty();
+      }
+
       ArgumentInfoCollection.Builder removableParametersBuilder = ArgumentInfoCollection.builder();
-      for (int removableParameterIndex : removableParameterIndices) {
-        removableParametersBuilder.addArgumentInfo(
-            removableParameterIndex,
-            RemovedArgumentInfo.builder()
-                .setType(method.getArgumentType(removableParameterIndex))
-                .build());
+      for (int argumentIndex = method.getDefinition().getFirstNonReceiverArgumentIndex();
+          argumentIndex < method.getDefinition().getNumberOfArguments();
+          argumentIndex++) {
+        if (!removableParameterIndices.test(argumentIndex)) {
+          continue;
+        }
+        AbstractValue abstractValue = optimizationInfo.getAbstractArgumentValue(argumentIndex);
+        if (abstractValue.isSingleValue()
+            && abstractValue.asSingleValue().isMaterializableInContext(appView, method)) {
+          removableParametersBuilder.addArgumentInfo(
+              argumentIndex,
+              RemovedArgumentInfo.builder()
+                  .setSingleValue(abstractValue.asSingleValue())
+                  .setType(method.getArgumentType(argumentIndex))
+                  .build());
+        }
       }
       return removableParametersBuilder.build();
     }
-
-    ArgumentInfoCollection removableParameters =
-        computeRemovableParametersFromMethod(method, removableParameterIndices::contains);
-    assert removableParameters.size() == removableParameterIndices.size();
-    return removableParameters;
-  }
-
-  private ArgumentInfoCollection computeRemovableParametersFromMethod(ProgramMethod method) {
-    return computeRemovableParametersFromMethod(method, parameterIndex -> true);
-  }
-
-  private ArgumentInfoCollection computeRemovableParametersFromMethod(
-      ProgramMethod method, IntPredicate removableParameterIndices) {
-    ConcreteCallSiteOptimizationInfo optimizationInfo =
-        method.getDefinition().getCallSiteOptimizationInfo().asConcreteCallSiteOptimizationInfo();
-    if (optimizationInfo == null) {
-      return ArgumentInfoCollection.empty();
-    }
-
-    ArgumentInfoCollection.Builder removableParametersBuilder = ArgumentInfoCollection.builder();
-    for (int argumentIndex = method.getDefinition().getFirstNonReceiverArgumentIndex();
-        argumentIndex < method.getDefinition().getNumberOfArguments();
-        argumentIndex++) {
-      if (!removableParameterIndices.test(argumentIndex)) {
-        continue;
-      }
-      AbstractValue abstractValue = optimizationInfo.getAbstractArgumentValue(argumentIndex);
-      if (abstractValue.isSingleValue()
-          && abstractValue.asSingleValue().isMaterializableInContext(appView, method)) {
-        removableParametersBuilder.addArgumentInfo(
-            argumentIndex,
-            RemovedArgumentInfo.builder()
-                .setSingleValue(abstractValue.asSingleValue())
-                .setType(method.getArgumentType(argumentIndex))
-                .build());
-      }
-    }
-    return removableParametersBuilder.build();
   }
 }
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/reprocessingcriteria/ArgumentPropagatorReprocessingCriteriaCollection.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/reprocessingcriteria/ArgumentPropagatorReprocessingCriteriaCollection.java
index 301738e..68191f9 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/reprocessingcriteria/ArgumentPropagatorReprocessingCriteriaCollection.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/reprocessingcriteria/ArgumentPropagatorReprocessingCriteriaCollection.java
@@ -82,10 +82,13 @@
     }
 
     ParameterReprocessingCriteria.Builder builder = ParameterReprocessingCriteria.builder();
-    for (Instruction instruction : argument.outValue().aliasedUsers()) {
-      // TODO(b/190154391): Introduce analysis for usefulness of abstract value and nullability.
-      builder.setReprocessDueToAbstractValue().setReprocessDueToNullability();
 
+    // TODO(b/190154391): Introduce analysis for usefulness of abstract value and nullability.
+    if (argument.outValue().hasAnyUsers()) {
+      builder.setReprocessDueToAbstractValue().setReprocessDueToNullability();
+    }
+
+    for (Instruction instruction : argument.outValue().aliasedUsers()) {
       switch (instruction.opcode()) {
         case ASSUME:
         case IF:
diff --git a/src/test/java/com/android/tools/r8/optimize/argumentpropagation/CollisionWithLibraryMethodAfterConstantParameterRemovalTest.java b/src/test/java/com/android/tools/r8/optimize/argumentpropagation/CollisionWithLibraryMethodAfterConstantParameterRemovalTest.java
new file mode 100644
index 0000000..d12d4ea
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/optimize/argumentpropagation/CollisionWithLibraryMethodAfterConstantParameterRemovalTest.java
@@ -0,0 +1,89 @@
+// Copyright (c) 2021, 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.optimize.argumentpropagation;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static junit.framework.TestCase.assertEquals;
+import static junit.framework.TestCase.assertTrue;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverClassInline;
+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.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.FoundMethodSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+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 CollisionWithLibraryMethodAfterConstantParameterRemovalTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection parameters() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .addOptionsModification(
+            options ->
+                options
+                    .callSiteOptimizationOptions()
+                    .setEnableExperimentalArgumentPropagation(true))
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(
+            inspector -> {
+              ClassSubject aClassSubject = inspector.clazz(A.class);
+              assertThat(aClassSubject, isPresent());
+
+              MethodSubject toStringMethodSubject =
+                  aClassSubject.uniqueMethodThatMatches(FoundMethodSubject::isVirtual);
+              assertThat(toStringMethodSubject, isPresent());
+              assertEquals(0, toStringMethodSubject.getProgramMethod().getReference().getArity());
+              assertTrue(
+                  toStringMethodSubject
+                      .streamInstructions()
+                      .anyMatch(instruction -> instruction.isConstString("Hello world!")));
+            })
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("Hello world!", "false");
+  }
+
+  static class Main {
+
+    public static void main(String[] args) {
+      // If we change A.toString(String) to A.toString(), then we change the semantics of calling
+      // A.toString().
+      String libString = new A().toString();
+      String greetingString = new A().toString("Hello world!");
+      System.out.println(greetingString);
+      System.out.println(libString.equals(greetingString));
+    }
+  }
+
+  @NeverClassInline
+  static class A {
+
+    @NeverInline
+    public String toString(String whichOne) {
+      return System.currentTimeMillis() > 0 ? whichOne : null;
+    }
+  }
+}