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 b73ba99..aa805a6 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
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.graph.PrunedItems;
 import com.android.tools.r8.ir.code.AbstractValueSupplier;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.conversion.IRConverter;
@@ -243,14 +244,16 @@
             stronglyConnectedProgramComponents,
             interfaceDispatchOutsideProgram)
         .propagateOptimizationInfo(executorService, timing);
+
     // TODO(b/296030319): Also publish the computed optimization information for fields.
-    new ArgumentPropagatorOptimizationInfoPopulator(
-            appView, converter, fieldStates, methodStates, postMethodProcessorBuilder)
-        .populateOptimizationInfo(executorService, timing);
+    PrunedItems prunedItems =
+        new ArgumentPropagatorOptimizationInfoPopulator(
+                appView, converter, fieldStates, methodStates, postMethodProcessorBuilder)
+            .populateOptimizationInfo(executorService, timing);
     timing.end();
 
     timing.begin("Compute unused arguments");
-    effectivelyUnusedArgumentsAnalysis.computeEffectivelyUnusedArguments();
+    effectivelyUnusedArgumentsAnalysis.computeEffectivelyUnusedArguments(prunedItems);
     effectivelyUnusedArgumentsAnalysis = null;
     timing.end();
   }
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorOptimizationInfoPopulator.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorOptimizationInfoPopulator.java
index 99249e3..d830831 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorOptimizationInfoPopulator.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorOptimizationInfoPopulator.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.ProgramField;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.graph.PrunedItems;
 import com.android.tools.r8.ir.analysis.type.DynamicType;
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.analysis.value.AbstractValue;
@@ -32,6 +33,7 @@
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.OptionalBool;
+import com.android.tools.r8.utils.SetUtils;
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
@@ -71,17 +73,19 @@
    * Computes an over-approximation of each parameter's value and type and stores the result in
    * {@link com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo}.
    */
-  void populateOptimizationInfo(ExecutorService executorService, Timing timing)
+  PrunedItems populateOptimizationInfo(ExecutorService executorService, Timing timing)
       throws ExecutionException {
     // The information stored on each method is now sound, and can be used as optimization info.
     timing.begin("Set optimization info");
-    setOptimizationInfo(executorService);
+    PrunedItems prunedItems = setOptimizationInfo(executorService);
     timing.end();
 
     assert methodStates.isEmpty();
+    return prunedItems;
   }
 
-  private void setOptimizationInfo(ExecutorService executorService) throws ExecutionException {
+  private PrunedItems setOptimizationInfo(ExecutorService executorService)
+      throws ExecutionException {
     ProgramMethodSet prunedMethods = ProgramMethodSet.createConcurrent();
     ThreadUtils.processItems(
         appView.appInfo().classes(),
@@ -94,6 +98,10 @@
     }
     converter.pruneItems(executorService);
     converter.waveDone(ProgramMethodSet.empty(), executorService);
+    return PrunedItems.builder()
+        .setPrunedApp(appView.app())
+        .setRemovedMethods(prunedMethods.toReferenceSet(SetUtils::newIdentityHashSet))
+        .build();
   }
 
   private ProgramMethodSet setOptimizationInfo(DexProgramClass clazz) {
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/VirtualRootMethodsAnalysisBase.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/VirtualRootMethodsAnalysisBase.java
index 0165f8e..c380eab 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/VirtualRootMethodsAnalysisBase.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/VirtualRootMethodsAnalysisBase.java
@@ -125,6 +125,10 @@
     boolean isMayDispatchOutsideProgramSet() {
       return mayDispatchOutsideProgram;
     }
+
+    boolean isOverriddenBy(VirtualRootMethod other) {
+      return overrides.contains(other);
+    }
   }
 
   private final Map<DexProgramClass, DexMethodSignatureMap<VirtualRootMethod>>
@@ -167,9 +171,35 @@
                         // forEachImmediateProgramSuperClass. Therefore, the current method is
                         // guaranteed to be an interface method when existing != null.
                         assert info.getMethod().getHolder().isInterface();
-                        if (!existing.getMethod().getHolder().isInterface()) {
+                        // Add the existing as a sibling of the current method (or vice versa).
+                        // Despite the fact that these two methods come from two different
+                        // extends/implements edges, the two methods may already be related by
+                        // overriding, as in the following example.
+                        //
+                        //   interface I { void m(); }
+                        //   interface J extends I { @Override default void m() { ... } }
+                        //   abstract class A implements I {}
+                        //   class B extends A implements J {}
+                        //
+                        // When processing the extends edge B->A, we will pull down the definition
+                        // of I.m(). Next, when processing the implements edge B->J we will pull
+                        // down the definition of J.m(). Since J.m() is an override of I.m() we
+                        // should avoid marking the two methods as siblings.
+                        if (info.isOverriddenBy(existing)) {
+                          return existing;
+                        }
+                        if (existing.isOverriddenBy(info)) {
+                          return info;
+                        }
+                        if (!existing.isAbstract()) {
                           existing.addSibling(info);
                           info.addOverride(existing);
+                          return existing;
+                        }
+                        if (existing.getMethod().getHolder().isInterface() && !info.isAbstract()) {
+                          info.addSibling(existing);
+                          existing.addOverride(info);
+                          return info;
                         }
                         return existing;
                       }
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InterfaceMethodArgumentPropagator.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InterfaceMethodArgumentPropagator.java
index 5fcd8db..6bc6ad0 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InterfaceMethodArgumentPropagator.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InterfaceMethodArgumentPropagator.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexMethodSignature;
 import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
 import com.android.tools.r8.graph.MethodResolutionResult;
 import com.android.tools.r8.graph.ProgramMethod;
@@ -154,7 +155,7 @@
 
                   MethodState transformedInterfaceMethodState =
                       transformInterfaceMethodStateForClassMethod(
-                          subclass, resolvedMethod, interfaceMethodState);
+                          appView, subclass, resolvedMethod, interfaceMethodState, methodStates);
                   if (!transformedInterfaceMethodState.isBottom()) {
                     methodStates.addMethodState(
                         appView, resolvedMethod, transformedInterfaceMethodState);
@@ -162,12 +163,23 @@
                 }));
   }
 
-  private MethodState transformInterfaceMethodStateForClassMethod(
-      DexProgramClass clazz, ProgramMethod resolvedMethod, MethodState methodState) {
-    if (!methodState.isPolymorphic()) {
-      return methodState.mutableCopy();
+  public static MethodState transformInterfaceMethodStateForClassMethod(
+      AppView<AppInfoWithLiveness> appView,
+      DexProgramClass clazz,
+      ProgramMethod resolvedMethod,
+      MethodState methodState,
+      MethodStateCollectionByReference methodStates) {
+    if (methodState.isBottom() || methodState.isUnknown()) {
+      return methodState;
     }
 
+    if (methodState.isMonomorphic()) {
+      assert false;
+      return MethodState.bottom();
+    }
+
+    assert methodState.isPolymorphic();
+
     // Rewrite the bounds of the polymorphic method state. If a given piece of argument information
     // should be propagated to the resolved method, we replace the type bounds by the holder of the
     // resolved method.
@@ -177,7 +189,16 @@
             appView,
             bounds -> {
               boolean shouldPropagateMethodStateForBounds;
-              if (bounds.isUnknown()) {
+              if (bounds.isExactClassType()) {
+                ClassTypeElement exactClassType = bounds.getExactClassType();
+                DexType exactType =
+                    exactClassType.getClassType().isIdenticalTo(appView.dexItemFactory().objectType)
+                            && exactClassType.getInterfaces().hasSingleKnownInterface()
+                        ? exactClassType.getInterfaces().getSingleKnownInterface()
+                        : exactClassType.getClassType();
+                shouldPropagateMethodStateForBounds =
+                    exactType.isIdenticalTo(resolvedMethod.getHolderType());
+              } else if (bounds.isUnknown()) {
                 shouldPropagateMethodStateForBounds = true;
               } else {
                 ClassTypeElement upperBound = bounds.getDynamicUpperBoundType().asClassType();
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/VirtualDispatchMethodArgumentPropagator.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/VirtualDispatchMethodArgumentPropagator.java
index 4b3349c..305d88d 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/VirtualDispatchMethodArgumentPropagator.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/VirtualDispatchMethodArgumentPropagator.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.optimize.argumentpropagation.propagation;
 
 import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
 import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
 import static com.android.tools.r8.utils.MapUtils.ignoreKey;
 
@@ -16,15 +17,19 @@
 import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
+import com.android.tools.r8.ir.analysis.type.DynamicType;
 import com.android.tools.r8.ir.analysis.type.DynamicTypeWithUpperBound;
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteMethodState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteMonomorphicMethodState;
 import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcretePolymorphicMethodState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteReceiverValueState;
 import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodState;
 import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodStateCollectionByReference;
 import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodStateCollectionBySignature;
 import com.android.tools.r8.optimize.argumentpropagation.codescanner.StateCloner;
 import com.android.tools.r8.optimize.argumentpropagation.codescanner.UnknownMethodState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ValueState;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.Collection;
 import java.util.HashMap;
@@ -70,12 +75,10 @@
       // Add the argument information that is active until a given lower bound.
       parentState.activeUntilLowerBound.forEach(
           (lowerBound, activeMethodState) -> {
-            if (lowerBound != superclass.getType()) {
-              // TODO(b/190154391): Verify that the lower bound is a subtype of the current.
-              //  Otherwise we carry this information to all subtypes although there is no need to.
-              activeUntilLowerBound
-                  .computeIfAbsent(lowerBound, ignoreKey(MethodStateCollectionBySignature::create))
-                  .addMethodStates(appView, activeMethodState);
+            TypeElement lowerBoundType = lowerBound.toTypeElement(appView);
+            TypeElement currentType = clazz.getType().toTypeElement(appView);
+            if (lowerBoundType.lessThanOrEqual(currentType, appView)) {
+              addActiveUntilLowerBound(lowerBound, activeMethodState);
             } else {
               // No longer active.
             }
@@ -85,68 +88,107 @@
       parentState.inactiveUntilUpperBound.forEach(
           (bounds, inactiveMethodStates) -> {
             ClassTypeElement upperBound = bounds.getDynamicUpperBoundType().asClassType();
-            if (shouldActivateMethodStateGuardedByBounds(upperBound, clazz, superclass)) {
-              // The upper bound is the current class, thus this inactive information now becomes
-              // active.
-              if (bounds.hasDynamicLowerBoundType()) {
-                activeUntilLowerBound
-                    .computeIfAbsent(
-                        bounds.getDynamicLowerBoundType().getClassType(),
-                        ignoreKey(MethodStateCollectionBySignature::create))
-                    .addMethodStates(appView, inactiveMethodStates);
-              } else {
-                active.addMethodStates(appView, inactiveMethodStates);
-              }
-
-              inactiveMethodStates.forEach(
-                  (signature, methodState) -> {
-                    SingleResolutionResult<?> resolutionResult =
-                        appView
-                            .appInfo()
-                            .resolveMethodOnLegacy(clazz, signature)
-                            .asSingleResolution();
-
-                    // Find the first virtual method in the super class hierarchy.
-                    while (resolutionResult != null
-                        && resolutionResult.getResolvedMethod().belongsToDirectPool()) {
-                      resolutionResult =
-                          appView
-                              .appInfo()
-                              .resolveMethodOnClassLegacy(
-                                  resolutionResult.getResolvedHolder().getSuperType(), signature)
-                              .asSingleResolution();
-                    }
-
-                    // Propagate the argument information to the method on the super class.
-                    if (resolutionResult != null
-                        && resolutionResult.getResolvedHolder().isProgramClass()
-                        && resolutionResult.getResolvedHolder() != clazz
-                        && resolutionResult.getResolvedMethod().hasCode()) {
-                      DexProgramClass resolvedHolder =
-                          resolutionResult.getResolvedHolder().asProgramClass();
-                      propagationStates
-                          .get(resolvedHolder)
-                          .activeUntilLowerBound
-                          .computeIfAbsent(
-                              resolvedHolder.getType(),
-                              ignoreKey(MethodStateCollectionBySignature::create))
-                          .addMethodState(
-                              appView, resolutionResult.getResolvedProgramMethod(), methodState);
-                    }
-                  });
-            } else {
+            if (!shouldActivateMethodStateGuardedByBounds(upperBound, clazz, superclass)) {
               // Still inactive.
               // TODO(b/190154391): Only carry this information downwards if the upper bound is a
               //  subtype of this class. Otherwise we carry this information to all subtypes,
               //  although clearly the information will never become active.
-              inactiveUntilUpperBound
-                  .computeIfAbsent(bounds, ignoreKey(MethodStateCollectionBySignature::create))
-                  .addMethodStates(appView, inactiveMethodStates);
+              addInactiveUntilUpperBound(bounds, inactiveMethodStates);
+              return;
             }
+
+            // The upper bound is the current class, thus this inactive information now becomes
+            // active.
+            if (bounds.hasDynamicLowerBoundType()) {
+              // For class methods with sibling interface methods, we can have lower bound type
+              // information on the sibling interface method. When this information is propagated
+              // down to the common subtype, then there is no need to propagate the information
+              // any further, since the common subtype is already below the lower bound.
+              //
+              // Note that this does not imply that the information stored on the sibling
+              // interface method is not applied. The information is propagated to the class
+              // method that implements the interface method below.
+              ClassTypeElement lowerBound = bounds.getDynamicLowerBoundType();
+              TypeElement currentType = clazz.getType().toTypeElement(appView);
+              if (lowerBound.lessThanOrEqual(currentType, appView)) {
+                DexType activeUntilLowerBoundType =
+                    lowerBound.getClassType().isIdenticalTo(appView.dexItemFactory().objectType)
+                            && lowerBound.getInterfaces().hasSingleKnownInterface()
+                        ? lowerBound.getInterfaces().getSingleKnownInterface()
+                        : lowerBound.getClassType();
+                addActiveUntilLowerBound(activeUntilLowerBoundType, inactiveMethodStates);
+              } else {
+                return;
+              }
+            } else {
+              active.addMethodStates(appView, inactiveMethodStates);
+            }
+
+            inactiveMethodStates.forEach(
+                (signature, methodState) -> {
+                  SingleResolutionResult<?> resolutionResult =
+                      appView
+                          .appInfo()
+                          .resolveMethodOnLegacy(clazz, signature)
+                          .asSingleResolution();
+
+                  // Find the first virtual method in the super class hierarchy.
+                  while (resolutionResult != null
+                      && resolutionResult.getResolvedMethod().belongsToDirectPool()) {
+                    resolutionResult =
+                        appView
+                            .appInfo()
+                            .resolveMethodOnClassLegacy(
+                                resolutionResult.getResolvedHolder().getSuperType(), signature)
+                            .asSingleResolution();
+                  }
+
+                  // Propagate the argument information to the method on the super class.
+                  if (resolutionResult != null
+                      && resolutionResult.getResolvedHolder().isProgramClass()
+                      && resolutionResult.getResolvedHolder() != clazz
+                      && resolutionResult.getResolvedMethod().hasCode()) {
+                    DexProgramClass resolvedHolder =
+                        resolutionResult.getResolvedHolder().asProgramClass();
+                    PropagationState propagationState = propagationStates.get(resolvedHolder);
+                    propagationState.addActiveUntilLowerBound(
+                        resolvedHolder.getType(),
+                        resolutionResult.getResolvedProgramMethod(),
+                        methodState);
+                  }
+                });
           });
     }
 
-    private MethodState computeMethodStateForPolymorhicMethod(ProgramMethod method) {
+    private void addActiveUntilLowerBound(
+        DexType lowerBound, ProgramMethod method, MethodState methodState) {
+      activeUntilLowerBound
+          .computeIfAbsent(lowerBound, ignoreKey(MethodStateCollectionBySignature::create))
+          .addMethodState(appView, method, methodState);
+    }
+
+    private void addActiveUntilLowerBound(
+        DexType lowerBound, MethodStateCollectionBySignature methodStates) {
+      activeUntilLowerBound
+          .computeIfAbsent(lowerBound, ignoreKey(MethodStateCollectionBySignature::create))
+          .addMethodStates(appView, methodStates);
+    }
+
+    private void addInactiveUntilUpperBound(
+        DynamicTypeWithUpperBound upperBound, ProgramMethod method, MethodState methodState) {
+      inactiveUntilUpperBound
+          .computeIfAbsent(upperBound, ignoreKey(MethodStateCollectionBySignature::create))
+          .addMethodState(appView, method, methodState);
+    }
+
+    private void addInactiveUntilUpperBound(
+        DynamicTypeWithUpperBound upperBound, MethodStateCollectionBySignature methodStates) {
+      inactiveUntilUpperBound
+          .computeIfAbsent(upperBound, ignoreKey(MethodStateCollectionBySignature::create))
+          .addMethodStates(appView, methodStates);
+    }
+
+    private MethodState computeMethodStateForPolymorphicMethod(ProgramMethod method) {
       assert method.getDefinition().isNonPrivateVirtualMethod();
       MethodState methodState = active.get(method).mutableCopy();
       if (!activeUntilLowerBound.isEmpty()) {
@@ -157,9 +199,56 @@
                   appView, methodSignature, methodStates.get(method), StateCloner.getCloner());
         }
       }
+      if (methodState.isMonomorphic()) {
+        ConcreteMonomorphicMethodState monomorphicMethodState = methodState.asMonomorphic();
+        ValueState receiverState = monomorphicMethodState.getParameterState(0);
+        if (receiverState.isReceiverState()) {
+          ConcreteReceiverValueState concreteReceiverState = receiverState.asReceiverState();
+          DynamicType dynamicType = concreteReceiverState.getDynamicType();
+          DynamicType refinedDynamicType = computeRefinedReceiverDynamicType(method, dynamicType);
+          if (!refinedDynamicType.equals(dynamicType)) {
+            monomorphicMethodState.setParameterState(
+                0,
+                refinedDynamicType.isNotNullType()
+                    ? ValueState.unknown()
+                    : new ConcreteReceiverValueState(
+                        refinedDynamicType, concreteReceiverState.copyInFlow()));
+          }
+        } else {
+          assert receiverState.isBottom() || receiverState.isUnknown();
+        }
+      }
       return methodState;
     }
 
+    private DynamicType computeRefinedReceiverDynamicType(
+        ProgramMethod method, DynamicType dynamicType) {
+      if (!dynamicType.isDynamicTypeWithUpperBound()) {
+        return dynamicType;
+      }
+      DynamicTypeWithUpperBound dynamicTypeWithUpperBound =
+          dynamicType.asDynamicTypeWithUpperBound();
+      TypeElement dynamicUpperBoundType = dynamicTypeWithUpperBound.getDynamicUpperBoundType();
+      TypeElement staticUpperBoundType =
+          method.getHolderType().toTypeElement(appView, definitelyNotNull());
+      if (dynamicUpperBoundType.lessThanOrEqualUpToNullability(staticUpperBoundType, appView)) {
+        DynamicType newDynamicType = dynamicType.withNullability(definitelyNotNull());
+        assert newDynamicType.equals(dynamicType)
+            || !dynamicType.getNullability().isDefinitelyNotNull();
+        return newDynamicType;
+      }
+      ClassTypeElement dynamicLowerBoundType = dynamicTypeWithUpperBound.getDynamicLowerBoundType();
+      if (dynamicLowerBoundType == null) {
+        return DynamicType.definitelyNotNull();
+      }
+      assert dynamicLowerBoundType.lessThanOrEqualUpToNullability(staticUpperBoundType, appView);
+      if (dynamicLowerBoundType.equalUpToNullability(staticUpperBoundType)) {
+        return DynamicType.createExact(dynamicLowerBoundType.asDefinitelyNotNull());
+      }
+      return DynamicType.create(
+          appView, staticUpperBoundType, dynamicLowerBoundType.asDefinitelyNotNull());
+    }
+
     @SuppressWarnings("ReferenceEquality")
     private boolean shouldActivateMethodStateGuardedByBounds(
         ClassTypeElement upperBound, DexProgramClass currentClass, DexProgramClass superClass) {
@@ -181,6 +270,15 @@
       // upper bound class type and the upper bound interface types.
       return classType.lessThanOrEqualUpToNullability(upperBound, appView);
     }
+
+    boolean verifyActiveUntilLowerBoundRelevance(DexProgramClass clazz) {
+      TypeElement currentType = clazz.getType().toTypeElement(appView);
+      for (DexType lowerBound : activeUntilLowerBound.keySet()) {
+        TypeElement lowerBoundType = lowerBound.toTypeElement(appView);
+        assert lowerBoundType.lessThanOrEqual(currentType, appView);
+      }
+      return true;
+    }
   }
 
   // For each class, stores the argument information for each virtual method on this class and all
@@ -251,12 +349,18 @@
                     if (bounds.hasDynamicLowerBoundType()) {
                       // TODO(b/190154391): Verify that the lower bound is a subtype of the current
                       //  class.
-                      propagationState
-                          .activeUntilLowerBound
-                          .computeIfAbsent(
-                              bounds.getDynamicLowerBoundType().getClassType(),
-                              ignoreKey(MethodStateCollectionBySignature::create))
-                          .addMethodState(appView, method, methodStateForBounds);
+                      ClassTypeElement lowerBound = bounds.getDynamicLowerBoundType();
+                      DexType activeUntilLowerBoundType =
+                          lowerBound
+                                      .getClassType()
+                                      .isIdenticalTo(appView.dexItemFactory().objectType)
+                                  && lowerBound.getInterfaces().hasSingleKnownInterface()
+                              ? lowerBound.getInterfaces().getSingleKnownInterface()
+                              : lowerBound.getClassType();
+                      assert !bounds.isExactClassType()
+                          || activeUntilLowerBoundType.isIdenticalTo(clazz.getType());
+                      propagationState.addActiveUntilLowerBound(
+                          activeUntilLowerBoundType, method, methodStateForBounds);
                     } else {
                       propagationState.active.addMethodState(appView, method, methodStateForBounds);
                     }
@@ -265,23 +369,20 @@
                         .getType()
                         .toTypeElement(appView)
                         .lessThanOrEqualUpToNullability(upperBound, appView);
-                    propagationState
-                        .inactiveUntilUpperBound
-                        .computeIfAbsent(
-                            bounds, ignoreKey(MethodStateCollectionBySignature::create))
-                        .addMethodState(appView, method, methodStateForBounds);
+                    propagationState.addInactiveUntilUpperBound(
+                        bounds, method, methodStateForBounds);
                   }
                 }
               });
         });
 
+    assert propagationState.verifyActiveUntilLowerBoundRelevance(clazz);
     propagationStates.put(clazz, propagationState);
   }
 
-  @SuppressWarnings("ReferenceEquality")
   private boolean isUpperBoundSatisfied(ClassTypeElement upperBound, DexProgramClass currentClass) {
     DexType upperBoundType =
-        upperBound.getClassType() == appView.dexItemFactory().objectType
+        upperBound.getClassType().isIdenticalTo(appView.dexItemFactory().objectType)
                 && upperBound.getInterfaces().hasSingleKnownInterface()
             ? upperBound.getInterfaces().getSingleKnownInterface()
             : upperBound.getClassType();
@@ -315,7 +416,7 @@
 
     // This is a polymorphic method and we need to compute the method state to account for dynamic
     // dispatch.
-    methodState = propagationState.computeMethodStateForPolymorhicMethod(method);
+    methodState = propagationState.computeMethodStateForPolymorphicMethod(method);
     assert !methodState.isConcrete() || methodState.asConcrete().isMonomorphic();
     methodStates.set(method, methodState);
   }
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsAnalysis.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsAnalysis.java
index d0ec5b6..07a8bc7 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsAnalysis.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.DexMethodSignature;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.graph.PrunedItems;
 import com.android.tools.r8.ir.code.Argument;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
@@ -168,11 +169,11 @@
     return effectivelyUnusedConstraints;
   }
 
-  public void computeEffectivelyUnusedArguments() {
+  public void computeEffectivelyUnusedArguments(PrunedItems prunedItems) {
     // Build a graph where nodes are method parameters and there is an edge from method parameter p0
     // to method parameter p1 if the removal of p0 depends on the removal of p1.
     EffectivelyUnusedArgumentsGraph dependenceGraph =
-        EffectivelyUnusedArgumentsGraph.create(appView, constraints);
+        EffectivelyUnusedArgumentsGraph.create(appView, constraints, prunedItems);
 
     // Remove all unoptimizable method parameters from the graph, as well as all nodes that depend
     // on a node that is unoptimable.
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsGraph.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsGraph.java
index 9fbd408..964fca7 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsGraph.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsGraph.java
@@ -8,6 +8,7 @@
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.graph.PrunedItems;
 import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
 import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodParameter;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
@@ -37,13 +38,14 @@
 
   public static EffectivelyUnusedArgumentsGraph create(
       AppView<AppInfoWithLiveness> appView,
-      Map<MethodParameter, Set<MethodParameter>> constraints) {
+      Map<MethodParameter, Set<MethodParameter>> constraints,
+      PrunedItems prunedItems) {
     EffectivelyUnusedArgumentsGraph graph = new EffectivelyUnusedArgumentsGraph(appView);
     constraints.forEach(
         (methodParameter, constraintsForMethodParameter) -> {
           EffectivelyUnusedArgumentsGraphNode node = graph.getOrCreateNode(methodParameter);
           for (MethodParameter constraint : constraintsForMethodParameter) {
-            graph.addConstraintEdge(node, constraint, constraints);
+            graph.addConstraintEdge(node, constraint, constraints, prunedItems);
           }
         });
     return graph;
@@ -52,12 +54,19 @@
   void addConstraintEdge(
       EffectivelyUnusedArgumentsGraphNode node,
       MethodParameter constraint,
-      Map<MethodParameter, Set<MethodParameter>> constraints) {
+      Map<MethodParameter, Set<MethodParameter>> constraints,
+      PrunedItems prunedItems) {
+    if (prunedItems.isRemoved(constraint.getMethod())) {
+      // The current parameter node is an argument to a method that has been removed by argument
+      // propagation. Therefore, this usage constraint is no longer blocking the removal of the
+      // parameter.
+      return;
+    }
+
     ProgramMethod dependencyMethod =
         asProgramMethodOrNull(appView.definitionFor(constraint.getMethod()));
     if (dependencyMethod == null) {
       assert false;
-      node.setUnoptimizable();
       return;
     }
 
diff --git a/src/main/java/com/android/tools/r8/utils/collections/DexClassAndMethodSetBase.java b/src/main/java/com/android/tools/r8/utils/collections/DexClassAndMethodSetBase.java
index 9b77365..8b19b02 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/DexClassAndMethodSetBase.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/DexClassAndMethodSetBase.java
@@ -175,6 +175,12 @@
     return definitions;
   }
 
+  public Set<DexMethod> toReferenceSet(IntFunction<Set<DexMethod>> factory) {
+    Set<DexMethod> definitions = factory.apply(size());
+    forEach(method -> definitions.add(method.getReference()));
+    return definitions;
+  }
+
   public void trimCapacityIfSizeLessThan(int expectedSize) {
     if (size() < expectedSize) {
       Map<DexMethod, T> newBacking = createBacking(size());
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/callsites/ArgumentPropagationWithInexactUpperBoundTest.java b/src/test/java/com/android/tools/r8/ir/optimize/callsites/ArgumentPropagationWithInexactUpperBoundTest.java
index 71acba4..7cd7781 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/callsites/ArgumentPropagationWithInexactUpperBoundTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/callsites/ArgumentPropagationWithInexactUpperBoundTest.java
@@ -6,7 +6,6 @@
 import static com.android.tools.r8.utils.codeinspector.CodeMatchers.invokesMethod;
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static org.hamcrest.MatcherAssert.assertThat;
-import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.NeverClassInline;
@@ -65,8 +64,7 @@
 
               MethodSubject aMethodSubject = aClassSubject.uniqueMethodWithOriginalName("m");
               assertThat(aMethodSubject, isPresent());
-              // TODO(b/296030319): Should be true.
-              assertFalse(aMethodSubject.streamInstructions().anyMatch(i -> i.isConstNumber(0)));
+              assertTrue(aMethodSubject.streamInstructions().anyMatch(i -> i.isConstNumber(0)));
 
               ClassSubject cClassSubject = inspector.clazz(C.class);
               assertThat(cClassSubject, isPresent());
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/callsites/SiblingInterfaceMethodPropagationWithLowerBoundTest.java b/src/test/java/com/android/tools/r8/ir/optimize/callsites/SiblingInterfaceMethodPropagationWithLowerBoundTest.java
index 2996f59..ef38d6e 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/callsites/SiblingInterfaceMethodPropagationWithLowerBoundTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/callsites/SiblingInterfaceMethodPropagationWithLowerBoundTest.java
@@ -5,7 +5,7 @@
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static org.hamcrest.MatcherAssert.assertThat;
-import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
@@ -58,8 +58,7 @@
 
               MethodSubject bMethodSubject = bClassSubject.uniqueMethodWithOriginalName("m");
               assertThat(bMethodSubject, isPresent());
-              // TODO(b/296030319): Should be true.
-              assertFalse(bMethodSubject.streamInstructions().anyMatch(i -> i.isConstNumber(2)));
+              assertTrue(bMethodSubject.streamInstructions().anyMatch(i -> i.isConstNumber(2)));
             })
         .run(parameters.getRuntime(), Main.class)
         .assertSuccess();