diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
index 4d3d50a..cfb13ae 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -514,6 +514,10 @@
     return options().testing;
   }
 
+  public boolean hasRootSet() {
+    return rootSet != null;
+  }
+
   public RootSet rootSet() {
     return rootSet;
   }
@@ -711,7 +715,10 @@
       setProguardCompatibilityActions(
           getProguardCompatibilityActions().withoutPrunedItems(prunedItems));
     }
-    if (mainDexRootSet != null) {
+    if (hasRootSet()) {
+      rootSet.pruneItems(prunedItems);
+    }
+    if (hasMainDexRootSet()) {
       setMainDexRootSet(mainDexRootSet.withoutPrunedItems(prunedItems));
     }
   }
diff --git a/src/main/java/com/android/tools/r8/graph/GraphLens.java b/src/main/java/com/android/tools/r8/graph/GraphLens.java
index f0675ba..9236d1f 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLens.java
@@ -284,6 +284,10 @@
 
   public abstract DexField getOriginalFieldSignature(DexField field);
 
+  public final DexMember<?, ?> getOriginalMemberSignature(DexMember<?, ?> member) {
+    return member.apply(this::getOriginalFieldSignature, this::getOriginalMethodSignature);
+  }
+
   public final DexMethod getOriginalMethodSignature(DexMethod method) {
     return getOriginalMethodSignature(method, null);
   }
@@ -572,7 +576,7 @@
   }
 
   public <R extends DexReference, T> Map<R, T> rewriteReferenceKeys(
-      Map<R, T> map, Function<List<T>, T> merge) {
+      Map<R, T> map, BiFunction<R, List<T>, T> merge) {
     Map<R, T> result = new IdentityHashMap<>();
     Map<R, List<T>> needsMerge = new IdentityHashMap<>();
     map.forEach(
@@ -593,7 +597,7 @@
         });
     needsMerge.forEach(
         (rewrittenReference, unmergedValues) -> {
-          T mergedValue = merge.apply(unmergedValues);
+          T mergedValue = merge.apply(rewrittenReference, unmergedValues);
           if (mergedValue != null) {
             result.put(rewrittenReference, mergedValue);
           }
diff --git a/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java b/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
index 459c008..aa5e4c8 100644
--- a/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
+++ b/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
@@ -19,8 +19,10 @@
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.IdentityHashMap;
+import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Set;
 import java.util.function.BiConsumer;
 import java.util.function.Consumer;
@@ -144,6 +146,25 @@
     return builder(true, null).rewrittenWithLens(this, definitions, lens).build(definitions);
   }
 
+  public ObjectAllocationInfoCollectionImpl withoutPrunedItems(PrunedItems prunedItems) {
+    if (prunedItems.hasRemovedMethods()) {
+      Iterator<Entry<DexProgramClass, Set<DexEncodedMethod>>> iterator =
+          classesWithAllocationSiteTracking.entrySet().iterator();
+      while (iterator.hasNext()) {
+        Entry<DexProgramClass, Set<DexEncodedMethod>> entry = iterator.next();
+        Set<DexEncodedMethod> allocationSites = entry.getValue();
+        allocationSites.removeIf(
+            allocationSite ->
+                prunedItems.getRemovedMethods().contains(allocationSite.getReference()));
+        if (allocationSites.isEmpty()) {
+          classesWithoutAllocationSiteTracking.add(entry.getKey());
+          iterator.remove();
+        }
+      }
+    }
+    return this;
+  }
+
   public void forEachInstantiatedSubType(
       DexType type,
       Consumer<DexProgramClass> onClass,
diff --git a/src/main/java/com/android/tools/r8/graph/PrunedItems.java b/src/main/java/com/android/tools/r8/graph/PrunedItems.java
index 4489421..4f901fd 100644
--- a/src/main/java/com/android/tools/r8/graph/PrunedItems.java
+++ b/src/main/java/com/android/tools/r8/graph/PrunedItems.java
@@ -55,6 +55,10 @@
     return removedMethods.contains(method) || removedClasses.contains(method.getHolderType());
   }
 
+  public boolean isRemoved(DexReference reference) {
+    return reference.apply(this::isRemoved, this::isRemoved, this::isRemoved);
+  }
+
   public boolean isRemoved(DexType type) {
     return removedClasses.contains(type);
   }
@@ -107,7 +111,7 @@
     private final Set<DexType> noLongerSyntheticItems = Sets.newIdentityHashSet();
     private Set<DexType> removedClasses = Sets.newIdentityHashSet();
     private final Set<DexField> removedFields = Sets.newIdentityHashSet();
-    private final Set<DexMethod> removedMethods = Sets.newIdentityHashSet();
+    private Set<DexMethod> removedMethods = Sets.newIdentityHashSet();
 
     public Builder setPrunedApp(DexApplication prunedApp) {
       this.prunedApp = prunedApp;
@@ -146,6 +150,11 @@
       return this;
     }
 
+    public Builder setRemovedMethods(Set<DexMethod> removedMethods) {
+      this.removedMethods = removedMethods;
+      return this;
+    }
+
     public PrunedItems build() {
       return new PrunedItems(
           prunedApp,
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java
index 2b12d6d..03a044d 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java
@@ -250,13 +250,7 @@
             MutableBidirectionalManyToOneRepresentativeMap<R, R> newMemberSignatures,
             MutableBidirectionalManyToOneRepresentativeMap<R, R> pendingNewMemberSignatureUpdates) {
       newMemberSignatures.removeAll(pendingNewMemberSignatureUpdates.keySet());
-      pendingNewMemberSignatureUpdates.forEachManyToOneMapping(
-          (keys, value, representative) -> {
-            newMemberSignatures.put(keys, value);
-            if (keys.size() > 1) {
-              newMemberSignatures.setRepresentative(value, representative);
-            }
-          });
+      newMemberSignatures.putAll(pendingNewMemberSignatureUpdates);
       pendingNewMemberSignatureUpdates.clear();
     }
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index e5c792f..f4a2cdc 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -595,7 +595,11 @@
     for (Instruction instruction : instructions()) {
       if (instruction.outValue != null && instruction.outValue.getType().isClassType()) {
         ClassTypeElement classTypeLattice = instruction.outValue.getType().asClassType();
-        assert !mergedClasses.hasBeenMergedIntoDifferentType(classTypeLattice.getClassType());
+        assert !mergedClasses.hasBeenMergedIntoDifferentType(classTypeLattice.getClassType())
+            : "Expected reference to "
+                + classTypeLattice.getClassType().getTypeName()
+                + " to be rewritten at instruction "
+                + instruction.toString();
         assert !classTypeLattice
             .getInterfaces()
             .anyMatch(
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index 07ba0ce..6ffe166 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -24,6 +24,7 @@
 import com.android.tools.r8.graph.DexTypeList;
 import com.android.tools.r8.graph.GraphLens;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.graph.PrunedItems;
 import com.android.tools.r8.ir.analysis.TypeChecker;
 import com.android.tools.r8.ir.analysis.VerifyTypesHelper;
 import com.android.tools.r8.ir.analysis.constant.SparseConditionalConstantPropagation;
@@ -112,10 +113,12 @@
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
 import com.google.common.base.Suppliers;
+import com.google.common.collect.Sets;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
+import java.util.Set;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.atomic.AtomicBoolean;
@@ -171,6 +174,7 @@
   private DexString highestSortingString;
 
   private List<Action> onWaveDoneActions = null;
+  private final Set<DexMethod> prunedMethodsInWave = Sets.newIdentityHashSet();
 
   private final List<DexString> neverMergePrefixes;
   // Use AtomicBoolean to satisfy TSAN checking (see b/153714743).
@@ -326,6 +330,10 @@
     this(AppView.createForD8(appInfo), timing, printer);
   }
 
+  public Inliner getInliner() {
+    return inliner;
+  }
+
   private void synthesizeBridgesForNestBasedAccessesOnClasspath(
       D8MethodProcessor methodProcessor, ExecutorService executorService)
       throws ExecutionException {
@@ -710,7 +718,7 @@
     appView.withArgumentPropagator(
         argumentPropagator ->
             argumentPropagator.tearDownCodeScanner(
-                postMethodProcessorBuilder, executorService, timing));
+                this, postMethodProcessorBuilder, executorService, timing));
     appView.withCallSiteOptimizationInfoPropagator(
         callSiteOptimizationInfoPropagator ->
             callSiteOptimizationInfoPropagator.enqueueMethodsForReprocessing(
@@ -844,7 +852,8 @@
     onWaveDoneActions = Collections.synchronizedList(new ArrayList<>());
   }
 
-  private void waveDone(ProgramMethodSet wave) {
+  private void waveDone(ProgramMethodSet wave, ExecutorService executorService)
+      throws ExecutionException {
     delayedOptimizationFeedback.refineAppInfoWithLiveness(appView.appInfo().withLiveness());
     delayedOptimizationFeedback.updateVisibleOptimizationInfo();
     if (options.enableFieldAssignmentTracker) {
@@ -858,6 +867,15 @@
     assert delayedOptimizationFeedback.noUpdatesLeft();
     onWaveDoneActions.forEach(com.android.tools.r8.utils.Action::execute);
     onWaveDoneActions = null;
+    if (!prunedMethodsInWave.isEmpty()) {
+      appView.pruneItems(
+          PrunedItems.builder()
+              .setRemovedMethods(prunedMethodsInWave)
+              .setPrunedApp(appView.appInfo().app())
+              .build(),
+          executorService);
+      prunedMethodsInWave.clear();
+    }
   }
 
   public void addWaveDoneAction(com.android.tools.r8.utils.Action action) {
@@ -1961,9 +1979,13 @@
     appView.withArgumentPropagator(argumentPropagator -> argumentPropagator.onMethodPruned(method));
     enumUnboxer.onMethodPruned(method);
     outliner.onMethodPruned(method);
+    if (classStaticizer != null) {
+      classStaticizer.onMethodPruned(method);
+    }
     if (inliner != null) {
       inliner.onMethodPruned(method);
     }
+    prunedMethodsInWave.add(method.getReference());
   }
 
   /**
@@ -1977,6 +1999,9 @@
         argumentPropagator -> argumentPropagator.onMethodCodePruned(method));
     enumUnboxer.onMethodCodePruned(method);
     outliner.onMethodCodePruned(method);
+    if (classStaticizer != null) {
+      classStaticizer.onMethodCodePruned(method);
+    }
     if (inliner != null) {
       inliner.onMethodCodePruned(method);
     }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/PrimaryMethodProcessor.java b/src/main/java/com/android/tools/r8/ir/conversion/PrimaryMethodProcessor.java
index bea221a..9998d53 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/PrimaryMethodProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/PrimaryMethodProcessor.java
@@ -23,7 +23,6 @@
 import java.util.Set;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
-import java.util.function.Consumer;
 
 /**
  * A {@link MethodProcessor} that processes methods in the whole program in a bottom-up manner,
@@ -36,6 +35,12 @@
     void notifyWaveStart(ProgramMethodSet wave);
   }
 
+  interface WaveDoneAction {
+
+    void notifyWaveDone(ProgramMethodSet wave, ExecutorService executorService)
+        throws ExecutionException;
+  }
+
   private final AppView<?> appView;
   private final CallSiteInformation callSiteInformation;
   private final Deque<SortedProgramMethodSet> waves;
@@ -110,7 +115,7 @@
   <E extends Exception> void forEachMethod(
       MethodAction<E> consumer,
       WaveStartAction waveStartAction,
-      Consumer<ProgramMethodSet> waveDone,
+      WaveDoneAction waveDoneAction,
       Timing timing,
       ExecutorService executorService)
       throws ExecutionException {
@@ -133,7 +138,7 @@
                 },
                 executorService);
         merger.add(timings);
-        waveDone.accept(wave);
+        waveDoneAction.notifyWaveDone(wave, executorService);
         prepareForWaveExtensionProcessing();
       } while (!wave.isEmpty());
     }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
index 32d2228..f0de604 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
@@ -98,6 +98,8 @@
   // pruned when the wave ends.
   private final Map<DexProgramClass, ProgramMethodSet> singleCallerInlinedMethodsInWave =
       new ConcurrentHashMap<>();
+  private final Set<DexMethod> singleCallerInlinedPrunedMethodsForTesting =
+      Sets.newIdentityHashSet();
 
   private final AvailableApiExceptions availableApiExceptions;
 
@@ -1268,10 +1270,13 @@
         (clazz, singleCallerInlinedMethodsForClass) -> {
           // Convert and remove virtual single caller inlined methods to abstract or throw null.
           singleCallerInlinedMethodsForClass.removeIf(
-              singleCallerInlinedMethod -> {
-                if (singleCallerInlinedMethod.getDefinition().belongsToVirtualPool() || true) {
-                  singleCallerInlinedMethod.convertToAbstractOrThrowNullMethod(appView);
-                  converter.onMethodCodePruned(singleCallerInlinedMethod);
+              method -> {
+                // TODO(b/203188583): Enable pruning of methods with generic signatures. For this to
+                //  work we need to pass in a seed to GenericSignatureContextBuilder.create in R8.
+                if (method.getDefinition().belongsToVirtualPool()
+                    || method.getDefinition().getGenericSignature().hasSignature()) {
+                  method.convertToAbstractOrThrowNullMethod(appView);
+                  converter.onMethodCodePruned(method);
                   return true;
                 }
                 return false;
@@ -1284,7 +1289,10 @@
                 .removeMethods(
                     singleCallerInlinedMethodsForClass.toDefinitionSet(
                         SetUtils::newIdentityHashSet));
-            singleCallerInlinedMethodsForClass.forEach(converter::onMethodPruned);
+            for (ProgramMethod method : singleCallerInlinedMethodsForClass) {
+              converter.onMethodPruned(method);
+              singleCallerInlinedPrunedMethodsForTesting.add(method.getReference());
+            }
           }
         });
     singleCallerInlinedMethodsInWave.clear();
@@ -1302,4 +1310,9 @@
     }
     return true;
   }
+
+  public boolean verifyIsPrunedDueToSingleCallerInlining(DexMethod method) {
+    assert singleCallerInlinedPrunedMethodsForTesting.contains(method);
+    return true;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java
index 748253f..30b0da1 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java
@@ -105,6 +105,8 @@
   final Map<CandidateInfo, LongLivedProgramMethodSetBuilder<?>> referencedFrom =
       new ConcurrentHashMap<>();
 
+  private final Set<DexMethod> prunedMethods = Sets.newIdentityHashSet();
+
   // The map storing all the potential candidates for staticizing.
   final ConcurrentHashMap<DexType, CandidateInfo> candidates = new ConcurrentHashMap<>();
 
@@ -114,6 +116,14 @@
     this.converter = converter;
   }
 
+  public void onMethodPruned(ProgramMethod method) {
+    onMethodCodePruned(method);
+  }
+
+  public void onMethodCodePruned(ProgramMethod method) {
+    prunedMethods.add(method.getReference());
+  }
+
   public void prepareForPrimaryOptimizationPass(GraphLens graphLensForPrimaryOptimizationPass) {
     collectCandidates();
     this.graphLensForOptimizationPass = graphLensForPrimaryOptimizationPass;
@@ -129,8 +139,11 @@
         .values()
         .forEach(
             referencedFromBuilder ->
-                referencedFromBuilder.rewrittenWithLens(graphLensForSecondaryOptimizationPass));
+                referencedFromBuilder
+                    .removeAll(prunedMethods)
+                    .rewrittenWithLens(graphLensForSecondaryOptimizationPass));
     this.graphLensForOptimizationPass = graphLensForSecondaryOptimizationPass;
+    prunedMethods.clear();
   }
 
   // Before doing any usage-based analysis we collect a set of classes that can be
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
index c73132f..806b057 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
@@ -237,9 +237,6 @@
         referencedFrom =
             referencedFromBuilder
                 .rewrittenWithLens(appView)
-                .removeIf(
-                    appView,
-                    method -> method.getOptimizationInfo().hasBeenInlinedIntoSingleCallSite())
                 .build(appView);
         materializedReferencedFromCollections.put(info, referencedFrom);
       } else {
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 158a8de..45f4984 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
@@ -130,6 +130,7 @@
   }
 
   public void tearDownCodeScanner(
+      IRConverter converter,
       PostMethodProcessor.Builder postMethodProcessorBuilder,
       ExecutorService executorService,
       Timing timing)
@@ -152,6 +153,7 @@
     Map<Set<DexProgramClass>, DexMethodSignatureSet> interfaceDispatchOutsideProgram =
         new IdentityHashMap<>();
     populateParameterOptimizationInfo(
+        converter,
         immediateSubtypingInfo,
         stronglyConnectedProgramComponents,
         (stronglyConnectedProgramComponent, signature) -> {
@@ -189,6 +191,7 @@
    * optimization info.
    */
   private void populateParameterOptimizationInfo(
+      IRConverter converter,
       ImmediateProgramSubtypingInfo immediateSubtypingInfo,
       List<Set<DexProgramClass>> stronglyConnectedProgramComponents,
       BiConsumer<Set<DexProgramClass>, DexMethodSignature> interfaceDispatchOutsideProgram,
@@ -209,7 +212,7 @@
             reprocessingCriteriaCollection,
             stronglyConnectedProgramComponents,
             interfaceDispatchOutsideProgram)
-        .populateOptimizationInfo(executorService, timing);
+        .populateOptimizationInfo(converter, executorService, timing);
     reprocessingCriteriaCollection = 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 5470ed5..e050de8 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
@@ -14,6 +14,7 @@
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.analysis.type.DynamicType;
 import com.android.tools.r8.ir.analysis.type.Nullability;
+import com.android.tools.r8.ir.conversion.IRConverter;
 import com.android.tools.r8.ir.optimize.info.ConcreteCallSiteOptimizationInfo;
 import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
 import com.android.tools.r8.ir.optimize.info.OptimizationFeedback;
@@ -82,7 +83,8 @@
    * 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)
+  void populateOptimizationInfo(
+      IRConverter converter, ExecutorService executorService, Timing timing)
       throws ExecutionException {
     // TODO(b/190154391): Propagate argument information to handle virtual dispatch.
     // TODO(b/190154391): To deal with arguments that are themselves passed as arguments to invoke
@@ -98,7 +100,7 @@
 
     // Solve the parameter flow constraints.
     timing.begin("Solve flow constraints");
-    new InParameterFlowPropagator(appView, methodStates).run(executorService);
+    new InParameterFlowPropagator(appView, converter, methodStates).run(executorService);
     timing.end();
 
     // The information stored on each method is now sound, and can be used as optimization info.
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InParameterFlowPropagator.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InParameterFlowPropagator.java
index 9b583c7..9b10015 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InParameterFlowPropagator.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InParameterFlowPropagator.java
@@ -12,6 +12,7 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.conversion.IRConverter;
 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.ConcreteParameterState;
@@ -42,11 +43,15 @@
 public class InParameterFlowPropagator {
 
   final AppView<AppInfoWithLiveness> appView;
+  final IRConverter converter;
   final MethodStateCollectionByReference methodStates;
 
   public InParameterFlowPropagator(
-      AppView<AppInfoWithLiveness> appView, MethodStateCollectionByReference methodStates) {
+      AppView<AppInfoWithLiveness> appView,
+      IRConverter converter,
+      MethodStateCollectionByReference methodStates) {
     this.appView = appView;
+    this.converter = converter;
     this.methodStates = methodStates;
   }
 
@@ -206,6 +211,16 @@
       ParameterNode node = getOrCreateParameterNode(method, parameterIndex, methodState);
       for (MethodParameter inParameter : concreteParameterState.getInParameters()) {
         ProgramMethod enclosingMethod = getEnclosingMethod(inParameter);
+        if (enclosingMethod == null) {
+          // This is a parameter of a single caller inlined method. Since this method has been
+          // pruned, the call from inside the method no longer exists, and we can therefore safely
+          // skip it.
+          assert converter
+              .getInliner()
+              .verifyIsPrunedDueToSingleCallerInlining(inParameter.getMethod());
+          continue;
+        }
+
         MethodState enclosingMethodState = getMethodState(enclosingMethod);
         if (enclosingMethodState.isBottom()) {
           // The current method is called from a dead method; no need to propagate any information
diff --git a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
index b0f3ea9..04728fb 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -355,7 +355,7 @@
         pruneMethods(previous.liveMethods, prunedItems, executorService, futures),
         previous.fieldAccessInfoCollection,
         previous.methodAccessInfoCollection,
-        previous.objectAllocationInfoCollection,
+        previous.objectAllocationInfoCollection.withoutPrunedItems(prunedItems),
         previous.callSites,
         extendPinnedItems(previous, prunedItems.getAdditionalPinnedItems()),
         previous.mayHaveSideEffects,
@@ -439,6 +439,7 @@
   private static <T> Set<T> pruneItems(
       Set<T> items, Set<T> removedItems, ExecutorService executorService, List<Future<?>> futures) {
     if (!removedItems.isEmpty()) {
+
       futures.add(
           ThreadUtils.processAsynchronously(
               () -> {
@@ -1271,10 +1272,14 @@
         lens.rewriteCallSites(callSites, definitionSupplier),
         keepInfo.rewrite(definitionSupplier, lens, application.options),
         // Take any rule in case of collisions.
-        lens.rewriteReferenceKeys(mayHaveSideEffects, ListUtils::first),
-        // Drop assume rules in case of collisions.
-        lens.rewriteReferenceKeys(noSideEffects, rules -> null),
-        lens.rewriteReferenceKeys(assumedValues, rules -> null),
+        lens.rewriteReferenceKeys(mayHaveSideEffects, (reference, rules) -> ListUtils.first(rules)),
+        // Take the assume rule from the representative in case of collisions.
+        lens.rewriteReferenceKeys(
+            noSideEffects,
+            (reference, rules) -> noSideEffects.get(lens.getOriginalMemberSignature(reference))),
+        lens.rewriteReferenceKeys(
+            assumedValues,
+            (reference, rules) -> assumedValues.get(lens.getOriginalMemberSignature(reference))),
         lens.rewriteReferences(alwaysInline),
         lens.rewriteReferences(neverInline),
         lens.rewriteReferences(neverInlineDueToSingleCaller),
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 5b0ff74..75998bb 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -129,7 +129,6 @@
 import com.android.tools.r8.shaking.ScopedDexMethodSet.AddMethodIfMoreVisibleResult;
 import com.android.tools.r8.synthesis.SyntheticItems.SynthesizingContextOracle;
 import com.android.tools.r8.utils.Action;
-import com.android.tools.r8.utils.BooleanBox;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.IteratorUtils;
 import com.android.tools.r8.utils.OptionalBool;
@@ -3726,11 +3725,11 @@
                 : missingClassesBuilder.assertNoMissingClasses(appView),
             SetUtils.mapIdentityHashSet(liveTypes.getItems(), DexProgramClass::getType),
             Enqueuer.toDescriptorSet(targetedMethods.getItems()),
-            Collections.unmodifiableSet(failedMethodResolutionTargets),
-            Collections.unmodifiableSet(failedFieldResolutionTargets),
-            Collections.unmodifiableSet(bootstrapMethods),
-            Collections.unmodifiableSet(methodsTargetedByInvokeDynamic),
-            Collections.unmodifiableSet(virtualMethodsTargetedByInvokeDirect),
+            failedMethodResolutionTargets,
+            failedFieldResolutionTargets,
+            bootstrapMethods,
+            methodsTargetedByInvokeDynamic,
+            virtualMethodsTargetedByInvokeDirect,
             toDescriptorSet(liveMethods.getItems()),
             // Filter out library fields and pinned fields, because these are read by default.
             fieldAccessInfoCollection,
@@ -3772,16 +3771,15 @@
     if (methods.isEmpty() || interfaceProcessor == null) {
       return methods;
     }
-    BooleanBox changed = new BooleanBox(false);
-    ImmutableSet.Builder<DexMethod> builder = ImmutableSet.builder();
+    Set<DexMethod> companionMethods = Sets.newIdentityHashSet();
     interfaceProcessor.forEachMethodToMove(
         (method, companion) -> {
           if (methods.contains(method)) {
-            changed.set(true);
-            builder.add(companion);
+            companionMethods.add(companion);
           }
         });
-    return changed.isTrue() ? builder.addAll(methods).build() : methods;
+    methods.addAll(companionMethods);
+    return methods;
   }
 
   private boolean verifyReferences(DexApplication app) {
@@ -3850,11 +3848,11 @@
 
   private static <D extends DexEncodedMember<D, R>, R extends DexMember<D, R>>
       Set<R> toDescriptorSet(Set<D> set) {
-    ImmutableSet.Builder<R> builder = new ImmutableSet.Builder<>();
+    Set<R> result = Sets.newIdentityHashSet();
     for (D item : set) {
-      builder.add(item.getReference());
+      result.add(item.getReference());
     }
-    return builder.build();
+    return result;
   }
 
   private static Object2BooleanMap<DexMember<?, ?>> joinIdentifierNameStrings(
diff --git a/src/main/java/com/android/tools/r8/shaking/MinimumKeepInfoCollection.java b/src/main/java/com/android/tools/r8/shaking/MinimumKeepInfoCollection.java
index ec1594a..8062beb 100644
--- a/src/main/java/com/android/tools/r8/shaking/MinimumKeepInfoCollection.java
+++ b/src/main/java/com/android/tools/r8/shaking/MinimumKeepInfoCollection.java
@@ -17,6 +17,7 @@
 import com.android.tools.r8.graph.ProgramDefinition;
 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.shaking.KeepInfo.Joiner;
 import com.android.tools.r8.utils.MapUtils;
 import java.util.Collections;
@@ -131,6 +132,10 @@
         });
   }
 
+  public void pruneItems(PrunedItems prunedItems) {
+    minimumKeepInfo.keySet().removeIf(prunedItems::isRemoved);
+  }
+
   public KeepClassInfo.Joiner remove(DexType clazz) {
     return (KeepClassInfo.Joiner) minimumKeepInfo.remove(clazz);
   }
diff --git a/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java b/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
index b105a80..03cff10 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
@@ -1740,6 +1740,17 @@
           });
     }
 
+    public void pruneItems(PrunedItems prunedItems) {
+      MinimumKeepInfoCollection unconditionalMinimumKeepInfo =
+          getDependentMinimumKeepInfo().getUnconditionalMinimumKeepInfoOrDefault(null);
+      if (unconditionalMinimumKeepInfo != null) {
+        unconditionalMinimumKeepInfo.pruneItems(prunedItems);
+        if (unconditionalMinimumKeepInfo.isEmpty()) {
+          getDependentMinimumKeepInfo().remove(UnconditionalKeepInfoEvent.get());
+        }
+      }
+    }
+
     void shouldNotBeMinified(ProgramDefinition definition) {
       getDependentMinimumKeepInfo()
           .getOrCreateUnconditionalMinimumKeepInfoFor(definition.getReference())
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index e157ff8..c44bdc9 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -1012,8 +1012,13 @@
         DexEncodedMethod shadowedBy = findMethodInTarget(virtualMethod);
         if (shadowedBy != null) {
           if (virtualMethod.isAbstract()) {
-            // Remove abstract/interface methods that are shadowed.
-            deferredRenamings.map(virtualMethod.getReference(), shadowedBy.getReference());
+            // Remove abstract/interface methods that are shadowed. The identity mapping below is
+            // needed to ensure we correctly fixup the mapping in case the signature refers to
+            // merged classes.
+            deferredRenamings
+                .map(virtualMethod.getReference(), shadowedBy.getReference())
+                .map(shadowedBy.getReference(), shadowedBy.getReference())
+                .recordMerge(virtualMethod.getReference(), shadowedBy.getReference());
 
             // The override now corresponds to the method in the parent, so unset its synthetic flag
             // if the method in the parent is not synthetic.
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java
index ea9f971..0464966 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java
@@ -16,9 +16,10 @@
 import com.android.tools.r8.graph.classmerging.VerticallyMergedClasses;
 import com.android.tools.r8.ir.code.Invoke.Type;
 import com.android.tools.r8.utils.IterableUtils;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
 import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
 import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
-import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneRepresentativeMap;
 import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
@@ -74,7 +75,7 @@
       Set<DexMethod> mergedMethods,
       Map<DexType, Map<DexMethod, GraphLensLookupResultProvider>>
           contextualVirtualToDirectMethodMaps,
-      BidirectionalOneToOneMap<DexMethod, DexMethod> newMethodSignatures,
+      BidirectionalManyToOneRepresentativeMap<DexMethod, DexMethod> newMethodSignatures,
       Map<DexMethod, DexMethod> originalMethodSignaturesForBridges) {
     super(appView, fieldMap, methodMap, mergedClasses.getForwardMap(), newMethodSignatures);
     this.appView = appView;
@@ -164,8 +165,8 @@
     private final Map<DexType, Map<DexMethod, GraphLensLookupResultProvider>>
         contextualVirtualToDirectMethodMaps = new IdentityHashMap<>();
 
-    private final MutableBidirectionalOneToOneMap<DexMethod, DexMethod> newMethodSignatures =
-        new BidirectionalOneToOneHashMap<>();
+    private final MutableBidirectionalManyToOneRepresentativeMap<DexMethod, DexMethod>
+        newMethodSignatures = BidirectionalManyToOneRepresentativeHashMap.newIdentityHashMap();
     private final Map<DexMethod, DexMethod> originalMethodSignaturesForBridges =
         new IdentityHashMap<>();
 
@@ -208,12 +209,17 @@
               context);
         }
       }
-      builder.newMethodSignatures.forEach(
-          (originalMethodSignature, renamedMethodSignature) ->
-              newBuilder.recordMove(
-                  originalMethodSignature,
-                  builder.getMethodSignatureAfterClassMerging(
-                      renamedMethodSignature, mergedClasses)));
+      builder.newMethodSignatures.forEachManyToOneMapping(
+          (originalMethodSignatures, renamedMethodSignature, representative) -> {
+            DexMethod methodSignatureAfterClassMerging =
+                builder.getMethodSignatureAfterClassMerging(renamedMethodSignature, mergedClasses);
+            newBuilder.newMethodSignatures.put(
+                originalMethodSignatures, methodSignatureAfterClassMerging);
+            if (originalMethodSignatures.size() > 1) {
+              newBuilder.newMethodSignatures.setRepresentative(
+                  methodSignatureAfterClassMerging, representative);
+            }
+          });
       for (Map.Entry<DexMethod, DexMethod> entry :
           builder.originalMethodSignaturesForBridges.entrySet()) {
         newBuilder.recordCreationOfBridgeMethod(
@@ -317,6 +323,12 @@
       return this;
     }
 
+    public void recordMerge(DexMethod from, DexMethod to) {
+      newMethodSignatures.put(from, to);
+      newMethodSignatures.put(to, to);
+      newMethodSignatures.setRepresentative(to, to);
+    }
+
     public void recordMove(DexMethod from, DexMethod to) {
       newMethodSignatures.put(from, to);
     }
@@ -336,7 +348,18 @@
       fieldMap.putAll(builder.fieldMap);
       methodMap.putAll(builder.methodMap);
       mergedMethodsBuilder.addAll(builder.mergedMethodsBuilder.build());
-      newMethodSignatures.putAll(builder.newMethodSignatures);
+      builder.newMethodSignatures.forEachManyToOneMapping(
+          (keys, value, representative) -> {
+            if (newMethodSignatures.containsValue(value)
+                && !newMethodSignatures.hasExplicitRepresentativeKey(value)) {
+              newMethodSignatures.setRepresentative(
+                  value, newMethodSignatures.getRepresentativeKey(value));
+            }
+            newMethodSignatures.put(keys, value);
+            if (keys.size() > 1 && !newMethodSignatures.hasExplicitRepresentativeKey(value)) {
+              newMethodSignatures.setRepresentative(value, representative);
+            }
+          });
       originalMethodSignaturesForBridges.putAll(builder.originalMethodSignaturesForBridges);
       for (DexType context : builder.contextualVirtualToDirectMethodMaps.keySet()) {
         Map<DexMethod, GraphLensLookupResultProvider> current =
diff --git a/src/main/java/com/android/tools/r8/utils/SetUtils.java b/src/main/java/com/android/tools/r8/utils/SetUtils.java
index a7305a2..f363c3da 100644
--- a/src/main/java/com/android/tools/r8/utils/SetUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/SetUtils.java
@@ -34,15 +34,16 @@
     return result;
   }
 
-  public static <T> Set<T> newIdentityHashSet(T element) {
-    Set<T> result = Sets.newIdentityHashSet();
-    result.add(element);
+  @SafeVarargs
+  public static <T> HashSet<T> newHashSet(T... elements) {
+    HashSet<T> result = new HashSet<>(elements.length);
+    Collections.addAll(result, elements);
     return result;
   }
 
-  public static <T> Set<T> newIdentityHashSet(T[] elements) {
+  public static <T> Set<T> newIdentityHashSet(T element) {
     Set<T> result = Sets.newIdentityHashSet();
-    Collections.addAll(result, elements);
+    result.add(element);
     return result;
   }
 
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneRepresentativeHashMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneRepresentativeHashMap.java
index bdd70c8..0887329 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneRepresentativeHashMap.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneRepresentativeHashMap.java
@@ -81,6 +81,17 @@
   }
 
   @Override
+  public void putAll(BidirectionalManyToOneRepresentativeMap<K, V> map) {
+    map.forEachManyToOneMapping(
+        (keys, value, representative) -> {
+          put(keys, value);
+          if (keys.size() > 1) {
+            setRepresentative(value, representative);
+          }
+        });
+  }
+
+  @Override
   public V remove(K key) {
     V value = super.remove(key);
     if (hasExplicitRepresentativeKey(value)) {
diff --git a/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneRepresentativeMap.java b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneRepresentativeMap.java
index 24f91ac..b80cc5b 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneRepresentativeMap.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneRepresentativeMap.java
@@ -8,6 +8,8 @@
 public interface MutableBidirectionalManyToOneRepresentativeMap<K, V>
     extends MutableBidirectionalManyToOneMap<K, V>, BidirectionalManyToOneRepresentativeMap<K, V> {
 
+  void putAll(BidirectionalManyToOneRepresentativeMap<K, V> map);
+
   K removeRepresentativeFor(V value);
 
   void setRepresentative(V value, K representative);
diff --git a/src/test/java/com/android/tools/r8/cf/bootstrap/BootstrapCurrentEqualityTest.java b/src/test/java/com/android/tools/r8/cf/bootstrap/BootstrapCurrentEqualityTest.java
index d1dc197..cdecb76 100644
--- a/src/test/java/com/android/tools/r8/cf/bootstrap/BootstrapCurrentEqualityTest.java
+++ b/src/test/java/com/android/tools/r8/cf/bootstrap/BootstrapCurrentEqualityTest.java
@@ -64,8 +64,8 @@
   @BeforeClass
   public static void beforeAll() throws Exception {
     if (data().stream().count() > 0) {
-      r8R8Debug = compileR8(CompilationMode.DEBUG);
       r8R8Release = compileR8(CompilationMode.RELEASE);
+      r8R8Debug = compileR8(CompilationMode.DEBUG);
     }
   }
 
diff --git a/src/test/java/com/android/tools/r8/classmerging/vertical/VerticalClassMergerTest.java b/src/test/java/com/android/tools/r8/classmerging/vertical/VerticalClassMergerTest.java
index 699bb50..7e98cdd 100644
--- a/src/test/java/com/android/tools/r8/classmerging/vertical/VerticalClassMergerTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/vertical/VerticalClassMergerTest.java
@@ -35,6 +35,7 @@
 import com.android.tools.r8.utils.AndroidApp.Builder;
 import com.android.tools.r8.utils.FileUtils;
 import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.SetUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
@@ -1065,15 +1066,17 @@
         };
     // SimpleInterface cannot be merged into SimpleInterfaceImpl because SimpleInterfaceImpl
     // is in a different package and is not public.
-    ImmutableSet<String> preservedClassNames =
-        ImmutableSet.of(
+    Set<String> preservedClassNames =
+        SetUtils.newHashSet(
             "classmerging.SimpleInterfaceAccessTest",
-            "classmerging.SimpleInterfaceAccessTest$1",
             "classmerging.SimpleInterfaceAccessTest$SimpleInterface",
             "classmerging.SimpleInterfaceAccessTest$OtherSimpleInterface",
             "classmerging.SimpleInterfaceAccessTest$OtherSimpleInterfaceImpl",
             "classmerging.pkg.SimpleInterfaceImplRetriever",
             "classmerging.pkg.SimpleInterfaceImplRetriever$SimpleInterfaceImpl");
+    if (parameters.isCfRuntime()) {
+      preservedClassNames.add("classmerging.SimpleInterfaceAccessTest$1");
+    }
     runTest(
         testForR8(parameters.getBackend())
             .addKeepRules(getProguardConfig(EXAMPLE_KEEP))
diff --git a/src/test/java/com/android/tools/r8/regress/b69825683/Regress69825683Test.java b/src/test/java/com/android/tools/r8/regress/b69825683/Regress69825683Test.java
index 7138094..01d1c30 100644
--- a/src/test/java/com/android/tools/r8/regress/b69825683/Regress69825683Test.java
+++ b/src/test/java/com/android/tools/r8/regress/b69825683/Regress69825683Test.java
@@ -62,14 +62,13 @@
 
     List<FoundClassSubject> classes = inspector.allClasses();
 
-    // Check that the synthetic class is still present.
-    assertEquals(3, classes.size());
+    // Check that the synthetic class is still present when generating class files.
+    assertEquals(parameters.isCfRuntime() ? 3 : 2, classes.size());
     assertEquals(
-        1,
+        parameters.isCfRuntime(),
         classes.stream()
             .map(FoundClassSubject::getOriginalName)
-            .filter(name -> name.endsWith("$1"))
-            .count());
+            .anyMatch(name -> name.endsWith("$1")));
   }
 
   @Test
@@ -94,13 +93,12 @@
 
     List<FoundClassSubject> classes = inspector.allClasses();
 
-    // Check that the synthetic class is still present.
-    assertEquals(3, classes.size());
+    // The synthetic class is still present when generating class files.
+    assertEquals(parameters.isCfRuntime() ? 3 : 2, classes.size());
     assertEquals(
-        1,
+        parameters.isCfRuntime(),
         classes.stream()
             .map(FoundClassSubject::getOriginalName)
-            .filter(name -> name.endsWith("$1"))
-            .count());
+            .anyMatch(name -> name.endsWith("$1")));
   }
 }
diff --git a/src/test/java/com/android/tools/r8/shaking/assumenosideeffects/StringBuildersAfterAssumenosideeffectsTest.java b/src/test/java/com/android/tools/r8/shaking/assumenosideeffects/StringBuildersAfterAssumenosideeffectsTest.java
index 2787932..b80febc 100644
--- a/src/test/java/com/android/tools/r8/shaking/assumenosideeffects/StringBuildersAfterAssumenosideeffectsTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/assumenosideeffects/StringBuildersAfterAssumenosideeffectsTest.java
@@ -28,7 +28,7 @@
 
   @Parameterized.Parameters(name = "{0}")
   public static TestParametersCollection data() {
-    return getTestParameters().withAllRuntimes().build();
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
   }
 
   private final TestParameters parameters;
@@ -51,7 +51,7 @@
             "  void info(...);",
             "}")
         .noMinification()
-        .setMinApi(parameters.getRuntime())
+        .setMinApi(parameters.getApiLevel())
         .run(parameters.getRuntime(), MAIN)
         .assertSuccessWithOutput(EXPECTED)
         .inspect(this::inspect);