diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index 3c3533a..79d8789 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -1354,7 +1354,7 @@
     DexClass newHolder = definitions.definitionFor(newMethodReference.getHolderType());
     assert newHolder != null;
     DexEncodedMethod newMethod = newHolder.lookupMethod(newMethodReference);
-    assert newMethod != null;
+    assert newMethod != null : newMethodReference.toSourceString();
     return newMethod;
   }
 
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 19ebb99..3e96a43 100644
--- a/src/main/java/com/android/tools/r8/graph/PrunedItems.java
+++ b/src/main/java/com/android/tools/r8/graph/PrunedItems.java
@@ -4,11 +4,14 @@
 
 package com.android.tools.r8.graph;
 
+import com.android.tools.r8.utils.DequeUtils;
 import com.android.tools.r8.utils.SetUtils;
 import com.google.common.collect.Sets;
 import java.util.Collection;
+import java.util.Deque;
 import java.util.IdentityHashMap;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.function.Consumer;
@@ -255,6 +258,9 @@
     }
 
     public PrunedItems build() {
+      if (hasFullyInlinedMethods()) {
+        compressInliningPaths();
+      }
       return new PrunedItems(
           prunedApp,
           additionalPinnedItems,
@@ -264,6 +270,38 @@
           removedFields,
           removedMethods);
     }
+
+    private void compressInliningPaths() {
+      Map<DexMethod, ProgramMethod> fullyInlinedMethodsUpdate = new IdentityHashMap<>();
+      for (Entry<DexMethod, ProgramMethod> entry : fullyInlinedMethods.entrySet()) {
+        DexMethod innermostCallee = entry.getKey();
+        if (fullyInlinedMethodsUpdate.containsKey(innermostCallee)) {
+          // Already processed as a result of previously processing a callee of the current callee.
+          continue;
+        }
+        ProgramMethod innermostCaller = entry.getValue();
+        ProgramMethod outermostCaller = fullyInlinedMethods.get(innermostCaller.getReference());
+        if (outermostCaller == null) {
+          continue;
+        }
+        Deque<DexMethod> fullyInlinedMethodChain =
+            DequeUtils.newArrayDeque(innermostCallee, innermostCaller.getReference());
+        while (true) {
+          DexMethod currentCallee = outermostCaller.getReference();
+          ProgramMethod currentCaller = fullyInlinedMethods.get(currentCallee);
+          if (currentCaller == null) {
+            break;
+          }
+          fullyInlinedMethodChain.addLast(currentCallee);
+          outermostCaller = currentCaller;
+        }
+        assert !removedMethods.contains(outermostCaller.getReference());
+        for (DexMethod callee : fullyInlinedMethodChain) {
+          fullyInlinedMethodsUpdate.put(callee, outermostCaller);
+        }
+      }
+      fullyInlinedMethods.putAll(fullyInlinedMethodsUpdate);
+    }
   }
 
   public static class ConcurrentBuilder extends Builder {
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/PrimaryR8IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/PrimaryR8IRConverter.java
index ae766bd..436969d 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/PrimaryR8IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/PrimaryR8IRConverter.java
@@ -263,17 +263,12 @@
       onWaveDoneActions.forEach(com.android.tools.r8.utils.Action::execute);
       onWaveDoneActions = null;
     }
-    if (prunedItemsBuilder.hasFullyInlinedMethods() || prunedItemsBuilder.hasRemovedMethods()) {
-      appView.pruneItems(
-          prunedItemsBuilder.setPrunedApp(appView.app()).build(), executorService, timing);
-      prunedItemsBuilder.clearFullyInlinedMethods();
-      prunedItemsBuilder.clearRemovedMethods();
-    }
   }
 
   private void lastWaveDone(
       PostMethodProcessor.Builder postMethodProcessorBuilder, ExecutorService executorService)
       throws ExecutionException {
+    pruneItems(executorService);
     if (assertionErrorTwoArgsConstructorRewriter != null) {
       assertionErrorTwoArgsConstructorRewriter.onLastWaveDone(postMethodProcessorBuilder);
       assertionErrorTwoArgsConstructorRewriter = null;
@@ -289,4 +284,13 @@
     // Ensure determinism of method-to-reprocess set.
     appView.testing().checkDeterminism(postMethodProcessorBuilder::dump);
   }
+
+  public void pruneItems(ExecutorService executorService) throws ExecutionException {
+    if (prunedItemsBuilder.hasFullyInlinedMethods() || prunedItemsBuilder.hasRemovedMethods()) {
+      appView.pruneItems(
+          prunedItemsBuilder.setPrunedApp(appView.app()).build(), executorService, timing);
+      prunedItemsBuilder.clearFullyInlinedMethods();
+      prunedItemsBuilder.clearRemovedMethods();
+    }
+  }
 }
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 0b947a3..4a19396 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
@@ -88,6 +88,7 @@
       converter.onMethodPruned(prunedMethod);
       postMethodProcessorBuilder.remove(prunedMethod, appView.graphLens());
     }
+    converter.pruneItems(executorService);
     converter.waveDone(ProgramMethodSet.empty(), executorService);
   }
 
diff --git a/src/main/java/com/android/tools/r8/utils/DequeUtils.java b/src/main/java/com/android/tools/r8/utils/DequeUtils.java
index 6745d6b..986a6a2 100644
--- a/src/main/java/com/android/tools/r8/utils/DequeUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/DequeUtils.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.utils;
 
 import java.util.ArrayDeque;
+import java.util.Collections;
 import java.util.Deque;
 
 public class DequeUtils {
@@ -14,4 +15,10 @@
     deque.add(element);
     return deque;
   }
+
+  public static <T> Deque<T> newArrayDeque(T... elements) {
+    Deque<T> deque = new ArrayDeque<>();
+    Collections.addAll(deque, elements);
+    return deque;
+  }
 }