diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index e02ccfb..f35ee68 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -361,6 +361,17 @@
 
         appView.rootSet().checkAllRulesAreUsed(options);
 
+        // Compute the main dex rootset that will be the base of first and final main dex tracing
+        // before pruning the application.
+        if (!options.mainDexKeepRules.isEmpty()) {
+          assert appView.graphLens().isIdentityLens();
+          // Find classes which may have code executed before secondary dex files installation.
+          MainDexRootSet mainDexRootSet =
+              MainDexRootSet.builder(appView, subtypingInfo, options.mainDexKeepRules)
+                  .build(executorService);
+          appView.setMainDexRootSet(mainDexRootSet);
+          appView.appInfo().unsetObsolete();
+        }
         if (options.proguardSeedsConsumer != null) {
           ByteArrayOutputStream bytes = new ByteArrayOutputStream();
           PrintStream out = new PrintStream(bytes);
@@ -423,6 +434,7 @@
       // Build conservative main dex content after first round of tree shaking. This is used
       // by certain optimizations to avoid introducing additional class references into main dex
       // classes, as that can cause the final number of main dex methods to grow.
+      // TODO(b/190941270): See if we can move this up before treepruning.
       performInitialMainDexTracing(appView, executorService);
 
       // The class type lattice elements include information about the interfaces that a class
@@ -853,16 +865,12 @@
       return;
     }
     assert appView.graphLens().isIdentityLens();
-    // Find classes which may have code executed before secondary dex files installation.
-    SubtypingInfo subtypingInfo = new SubtypingInfo(appView);
-    MainDexRootSet mainDexRootSet =
-        MainDexRootSet.builder(appView, subtypingInfo, options.mainDexKeepRules)
-            .build(executorService);
-    appView.setMainDexRootSet(mainDexRootSet);
-    appView.appInfo().unsetObsolete();
-    // Live types is the tracing result.
+
+    // Find classes which may have code executed before secondary dex files installation by
+    // computing from the initially computed main dex root set.
     MainDexInfo mainDexInfo =
-        EnqueuerFactory.createForInitialMainDexTracing(appView, executorService, subtypingInfo)
+        EnqueuerFactory.createForInitialMainDexTracing(
+                appView, executorService, new SubtypingInfo(appView))
             .traceMainDex(executorService, timing);
     appView.setAppInfo(appView.appInfo().rebuildWithMainDexInfo(mainDexInfo));
   }
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 72a0a0b..e4890a0 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
@@ -149,6 +149,10 @@
       this(appView, subtypingInfo, null);
     }
 
+    boolean isMainDexRootSetBuilder() {
+      return false;
+    }
+
     void handleMatchedAnnotation(AnnotationMatchResult annotation) {
       // Intentionally empty.
     }
@@ -517,7 +521,8 @@
       //  fullmode.
       if (clazz.isProgramClass()
           && rule.isProguardKeepRule()
-          && !rule.asProguardKeepRule().getModifiers().allowsShrinking) {
+          && !rule.asProguardKeepRule().getModifiers().allowsShrinking
+          && !isMainDexRootSetBuilder()) {
         new SynthesizeMissingInterfaceMethodsForMemberRules(
                 clazz.asProgramClass(), memberKeepRules, rule, preconditionSupplier, ifRule)
             .run();
@@ -2241,6 +2246,11 @@
     }
 
     @Override
+    boolean isMainDexRootSetBuilder() {
+      return true;
+    }
+
+    @Override
     public MainDexRootSet build(ExecutorService executorService) throws ExecutionException {
       // Call the super builder to have if-tests calculated automatically.
       RootSet rootSet = super.build(executorService);
diff --git a/src/test/java/com/android/tools/r8/TestCompileResult.java b/src/test/java/com/android/tools/r8/TestCompileResult.java
index 827684d..3bb1ffd 100644
--- a/src/test/java/com/android/tools/r8/TestCompileResult.java
+++ b/src/test/java/com/android/tools/r8/TestCompileResult.java
@@ -42,6 +42,7 @@
 import java.util.List;
 import java.util.Set;
 import java.util.concurrent.ExecutionException;
+import java.util.function.BiConsumer;
 import java.util.function.Consumer;
 import java.util.function.Function;
 import java.util.stream.Collectors;
@@ -118,6 +119,12 @@
     return self();
   }
 
+  public final CR inspectMainDexClasses(BiConsumer<CodeInspector, Set<String>> consumer)
+      throws IOException {
+    consumer.accept(inspector(), getMainDexClasses());
+    return self();
+  }
+
   public abstract String getStdout();
 
   public abstract String getStderr();
diff --git a/src/test/java/com/android/tools/r8/maindexlist/MainDexRemovedAnnotationTest.java b/src/test/java/com/android/tools/r8/maindexlist/MainDexRemovedAnnotationTest.java
index 67b113c..589a1e2 100644
--- a/src/test/java/com/android/tools/r8/maindexlist/MainDexRemovedAnnotationTest.java
+++ b/src/test/java/com/android/tools/r8/maindexlist/MainDexRemovedAnnotationTest.java
@@ -13,6 +13,7 @@
 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 java.lang.annotation.ElementType;
 import java.lang.annotation.Retention;
 import java.lang.annotation.RetentionPolicy;
@@ -43,7 +44,7 @@
   @Test
   public void testMainDexTracing() throws Exception {
     testForR8(parameters.getBackend())
-        .addProgramClasses(MainDex.class, Inside.class, Main.class)
+        .addProgramClasses(MainDex.class, Inside.class, Dead.class, Main.class)
         .addKeepClassAndMembersRules(Main.class)
         .setMinApi(parameters.getApiLevel())
         .enableInliningAnnotations()
@@ -51,13 +52,11 @@
         .collectMainDexClasses()
         .compile()
         .inspectMainDexClasses(
-            mainDexClasses -> {
-              // TODO(b/190623364): Should not be empty.
-              assertTrue(mainDexClasses.isEmpty());
-            })
-        .inspect(
-            codeInspector -> {
-              assertThat(codeInspector.clazz(MainDex.class), not(isPresent()));
+            (inspector, mainDexClasses) -> {
+              ClassSubject inside = inspector.clazz(Inside.class);
+              assertThat(inside, isPresent());
+              assertTrue(mainDexClasses.contains(inside.getFinalName()));
+              assertThat(inspector.clazz(MainDex.class), not(isPresent()));
             })
         .run(parameters.getRuntime(), Main.class)
         .assertSuccessWithOutputLines("Hello World!");
@@ -76,6 +75,11 @@
     }
   }
 
+  @MainDex
+  public static class Dead {
+    // Will be removed during first round of tree-pruning.
+  }
+
   public static class Main {
 
     public static void main(String[] args) {