diff --git a/src/main/java/com/android/tools/r8/PrintUses.java b/src/main/java/com/android/tools/r8/PrintUses.java
index 25f4d3b..80b5ec7 100644
--- a/src/main/java/com/android/tools/r8/PrintUses.java
+++ b/src/main/java/com/android/tools/r8/PrintUses.java
@@ -364,7 +364,7 @@
         AppInfoWithClassHierarchy.createInitialAppInfoWithClassHierarchy(
             application,
             ClassToFeatureSplitMap.createEmptyClassToFeatureSplitMap(),
-            MainDexInfo.createEmptyMainDexClasses());
+            MainDexInfo.none());
   }
 
   private void analyze() {
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index eef9f3d..283e461 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -535,6 +535,9 @@
         }
       }
 
+      // Clear traced methods roots to not hold on to the main dex live method set.
+      appView.appInfo().getMainDexInfo().clearTracedMethodRoots();
+
       // None of the optimizations above should lead to the creation of type lattice elements.
       assert appView.dexItemFactory().verifyNoCachedTypeElements();
 
diff --git a/src/main/java/com/android/tools/r8/dex/ApplicationReader.java b/src/main/java/com/android/tools/r8/dex/ApplicationReader.java
index 23db0d9..21de6ac 100644
--- a/src/main/java/com/android/tools/r8/dex/ApplicationReader.java
+++ b/src/main/java/com/android/tools/r8/dex/ApplicationReader.java
@@ -199,7 +199,7 @@
   }
 
   public MainDexInfo readMainDexClasses(DexApplication app) {
-    MainDexInfo.Builder builder = MainDexInfo.builder();
+    MainDexInfo.Builder builder = MainDexInfo.none().builder();
     if (inputApp.hasMainDexList()) {
       for (StringResource resource : inputApp.getMainDexListResources()) {
         addToMainDexClasses(app, builder, MainDexListParser.parseList(resource, itemFactory));
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfo.java b/src/main/java/com/android/tools/r8/graph/AppInfo.java
index d8785d1..de3d976 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfo.java
@@ -28,7 +28,7 @@
   private final BooleanBox obsolete;
 
   public static AppInfo createInitialAppInfo(DexApplication application) {
-    return createInitialAppInfo(application, MainDexInfo.createEmptyMainDexClasses());
+    return createInitialAppInfo(application, MainDexInfo.none());
   }
 
   public static AppInfo createInitialAppInfo(DexApplication application, MainDexInfo mainDexInfo) {
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 954580b..b56d682 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -156,7 +156,7 @@
   }
 
   public static AppView<AppInfoWithClassHierarchy> createForR8(DexApplication application) {
-    return createForR8(application, MainDexInfo.createEmptyMainDexClasses());
+    return createForR8(application, MainDexInfo.none());
   }
 
   public static AppView<AppInfoWithClassHierarchy> createForR8(
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/PreserveMethodCharacteristics.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/PreserveMethodCharacteristics.java
index fcafba0..4a789ba 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/PreserveMethodCharacteristics.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/PreserveMethodCharacteristics.java
@@ -20,6 +20,7 @@
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
+import java.util.Objects;
 
 /**
  * Policy that enforces that methods are only merged if they have the same visibility and library
@@ -32,8 +33,10 @@
     private final MethodAccessFlags accessFlags;
     private final boolean isAssumeNoSideEffectsMethod;
     private final OptionalBool isLibraryMethodOverride;
+    private final boolean isMainDexRoot;
 
-    private MethodCharacteristics(boolean isAssumeNoSideEffectsMethod, DexEncodedMethod method) {
+    private MethodCharacteristics(
+        DexEncodedMethod method, boolean isAssumeNoSideEffectsMethod, boolean isMainDexRoot) {
       this.accessFlags =
           MethodAccessFlags.builder()
               .setPrivate(method.getAccessFlags().isPrivate())
@@ -44,17 +47,24 @@
               .build();
       this.isAssumeNoSideEffectsMethod = isAssumeNoSideEffectsMethod;
       this.isLibraryMethodOverride = method.isLibraryMethodOverride();
+      this.isMainDexRoot = isMainDexRoot;
     }
 
     static MethodCharacteristics create(
         AppView<AppInfoWithLiveness> appView, DexEncodedMethod method) {
       return new MethodCharacteristics(
-          appView.appInfo().isAssumeNoSideEffectsMethod(method.getReference()), method);
+          method,
+          appView.appInfo().isAssumeNoSideEffectsMethod(method.getReference()),
+          appView.appInfo().getMainDexInfo().isTracedMethodRoot(method.getReference()));
     }
 
     @Override
     public int hashCode() {
-      return (accessFlags.hashCode() << 2) | isLibraryMethodOverride.ordinal();
+      return Objects.hash(
+          accessFlags,
+          isAssumeNoSideEffectsMethod,
+          isLibraryMethodOverride.ordinal(),
+          isMainDexRoot);
     }
 
     @Override
@@ -68,7 +78,8 @@
       MethodCharacteristics characteristics = (MethodCharacteristics) obj;
       return accessFlags.equals(characteristics.accessFlags)
           && isAssumeNoSideEffectsMethod == characteristics.isAssumeNoSideEffectsMethod
-          && isLibraryMethodOverride == characteristics.isLibraryMethodOverride;
+          && isLibraryMethodOverride == characteristics.isLibraryMethodOverride
+          && isMainDexRoot == characteristics.isMainDexRoot;
     }
   }
 
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 9c672b1..682c3f8 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -3030,8 +3030,13 @@
     trace(executorService, timing);
     options.reporter.failIfPendingErrors();
     // Calculate the automatic main dex list according to legacy multidex constraints.
-    MainDexInfo.Builder builder = MainDexInfo.builder();
+    MainDexInfo.Builder builder = appView.appInfo().getMainDexInfo().builder();
     liveTypes.getItems().forEach(builder::addRoot);
+    if (mode.isInitialMainDexTracing()) {
+      liveMethods.getItems().forEach(method -> builder.addRoot(method.method));
+    } else {
+      assert appView.appInfo().getMainDexInfo().isTracedMethodRootsCleared();
+    }
     new MainDexListBuilder(appView, builder.getRoots(), builder).run();
     MainDexInfo previousMainDexInfo = appInfo.getMainDexInfo();
     return builder.build(previousMainDexInfo);
diff --git a/src/main/java/com/android/tools/r8/shaking/MainDexInfo.java b/src/main/java/com/android/tools/r8/shaking/MainDexInfo.java
index c95ea3b..e55cc9d 100644
--- a/src/main/java/com/android/tools/r8/shaking/MainDexInfo.java
+++ b/src/main/java/com/android/tools/r8/shaking/MainDexInfo.java
@@ -8,6 +8,7 @@
 import static com.android.tools.r8.utils.PredicateUtils.not;
 
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
@@ -18,6 +19,7 @@
 import com.android.tools.r8.utils.ConsumerUtils;
 import com.android.tools.r8.utils.SetUtils;
 import com.google.common.collect.Sets;
+import java.util.Collections;
 import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
@@ -25,7 +27,14 @@
 
 public class MainDexInfo {
 
-  private static final MainDexInfo NONE = new MainDexInfo(Sets.newIdentityHashSet());
+  private static final MainDexInfo NONE =
+      new MainDexInfo(
+          Collections.emptySet(),
+          Collections.emptySet(),
+          Collections.emptySet(),
+          Collections.emptySet(),
+          Collections.emptySet(),
+          false);
 
   public enum MainDexGroup {
     MAIN_DEX_LIST,
@@ -39,24 +48,38 @@
   private final Map<DexType, DexType> synthesizedClassesMap;
   // Traced roots are traced main dex references.
   private final Set<DexType> tracedRoots;
+  // Traced method roots are the methods visited from an initial main dex root set. The set is
+  // cleared after the mergers has run.
+  private Set<DexMethod> tracedMethodRoots;
   // Traced dependencies are those classes that are directly referenced from traced roots, but will
   // not be loaded before loading the remaining dex files.
   private final Set<DexType> tracedDependencies;
+  // Bit indicating if the traced methods are cleared.
+  private boolean tracedMethodRootsCleared = false;
 
   private MainDexInfo(Set<DexType> classList) {
     this(
-        classList, Sets.newIdentityHashSet(), Sets.newIdentityHashSet(), Sets.newIdentityHashSet());
+        classList,
+        Collections.emptySet(),
+        Collections.emptySet(),
+        Collections.emptySet(),
+        /* synthesized classes - cannot be emptyset */ Sets.newIdentityHashSet(),
+        false);
   }
 
   private MainDexInfo(
       Set<DexType> classList,
       Set<DexType> tracedRoots,
+      Set<DexMethod> tracedMethodRoots,
       Set<DexType> tracedDependencies,
-      Set<DexType> synthesizedClasses) {
+      Set<DexType> synthesizedClasses,
+      boolean tracedMethodRootsCleared) {
     this.classList = classList;
     this.tracedRoots = tracedRoots;
+    this.tracedMethodRoots = tracedMethodRoots;
     this.tracedDependencies = tracedDependencies;
     this.synthesizedClassesMap = new ConcurrentHashMap<>();
+    this.tracedMethodRootsCleared = tracedMethodRootsCleared;
     synthesizedClasses.forEach(type -> synthesizedClassesMap.put(type, type));
     assert tracedDependencies.stream().noneMatch(tracedRoots::contains);
     assert tracedRoots.containsAll(synthesizedClasses);
@@ -83,6 +106,12 @@
     return isTracedRoot(definition.getContextType());
   }
 
+  public boolean isTracedMethodRoot(DexMethod method) {
+    assert !tracedMethodRootsCleared : "Traced method roots are cleared after mergers has run";
+    assert isTracedRoot(method.holder) : "The caller should checked if the holder is a root";
+    return tracedMethodRoots.contains(method);
+  }
+
   private boolean isTracedRoot(DexReference reference) {
     return tracedRoots.contains(reference.getContextType());
   }
@@ -95,6 +124,15 @@
     return tracedDependencies.contains(reference.getContextType());
   }
 
+  public boolean isTracedMethodRootsCleared() {
+    return tracedMethodRootsCleared;
+  }
+
+  public void clearTracedMethodRoots() {
+    this.tracedMethodRootsCleared = true;
+    this.tracedMethodRoots = Sets.newIdentityHashSet();
+  }
+
   public boolean canRebindReference(ProgramMethod context, DexReference referenceToTarget) {
     MainDexGroup holderGroup = getMainDexGroupInternal(context);
     if (holderGroup == MainDexGroup.NOT_IN_MAIN_DEX
@@ -104,8 +142,7 @@
     }
     if (holderGroup == MainDexGroup.MAIN_DEX_LIST) {
       // If the holder is in the class list, we are not allowed to make any assumptions on the
-      // holder
-      // being a root or a dependency. Therefore we cannot merge.
+      // holder being a root or a dependency. Therefore we cannot merge.
       return false;
     }
     assert holderGroup == MAIN_DEX_ROOT;
@@ -199,7 +236,7 @@
       synthesizedClassesMap.computeIfAbsent(
           clazz.type,
           type -> {
-            classList.add(type);
+            tracedRoots.add(type);
             return type;
           });
     }
@@ -243,6 +280,12 @@
         .keySet()
         .forEach(type -> ifNotRemoved(type, removedClasses, modifiedSynthesized::add));
     tracedRoots.forEach(type -> ifNotRemoved(type, removedClasses, builder::addRoot));
+    // TODO(b/169927809): Methods could be pruned without the holder being pruned, however, one has
+    //  to have a reference for querying a root.
+    tracedMethodRoots.forEach(
+        method ->
+            ifNotRemoved(
+                method.getHolderType(), removedClasses, ignored -> builder.addRoot(method)));
     tracedDependencies.forEach(type -> ifNotRemoved(type, removedClasses, builder::addDependency));
     return builder.build(modifiedClassList, modifiedSynthesized);
   }
@@ -261,42 +304,43 @@
     classList.forEach(type -> modifiedClassList.add(lens.lookupType(type)));
     synthesizedClassesMap.keySet().forEach(type -> modifiedSynthesized.add(lens.lookupType(type)));
     tracedRoots.forEach(type -> builder.addRoot(lens.lookupType(type)));
+    tracedMethodRoots.forEach(method -> builder.addRoot(lens.getRenamedMethodSignature(method)));
     tracedDependencies.forEach(type -> builder.addDependency(lens.lookupType(type)));
     return builder.build(modifiedClassList, modifiedSynthesized);
   }
 
-  public static Builder builder() {
-    return new Builder();
-  }
-
-  public static MainDexInfo createEmptyMainDexClasses() {
-    return new MainDexInfo(
-        Sets.newIdentityHashSet(),
-        Sets.newIdentityHashSet(),
-        Sets.newIdentityHashSet(),
-        Sets.newIdentityHashSet());
+  public Builder builder() {
+    return new Builder(tracedMethodRootsCleared);
   }
 
   public static class Builder {
 
     private final Set<DexType> list = Sets.newIdentityHashSet();
     private final Set<DexType> roots = Sets.newIdentityHashSet();
+    private final Set<DexMethod> methodRoots = Sets.newIdentityHashSet();
     private final Set<DexType> dependencies = Sets.newIdentityHashSet();
+    private final boolean tracedMethodRootsCleared;
 
-    private Builder() {}
+    private Builder(boolean tracedMethodRootsCleared) {
+      this.tracedMethodRootsCleared = tracedMethodRootsCleared;
+    }
 
     public void addList(DexProgramClass clazz) {
       list.add(clazz.getType());
     }
 
     public void addRoot(DexProgramClass clazz) {
-      roots.add(clazz.getType());
+      addRoot(clazz.type);
     }
 
     public void addRoot(DexType type) {
       roots.add(type);
     }
 
+    public void addRoot(DexMethod method) {
+      methodRoots.add(method);
+    }
+
     public void addDependency(DexProgramClass clazz) {
       addDependency(clazz.getType());
     }
@@ -348,8 +392,10 @@
       return new MainDexInfo(
           classList,
           SetUtils.unionIdentityHashSet(roots, synthesizedClasses),
+          methodRoots,
           Sets.difference(dependencies, synthesizedClasses),
-          synthesizedClasses);
+          synthesizedClasses,
+          tracedMethodRootsCleared);
     }
 
     public MainDexInfo build(MainDexInfo previous) {
diff --git a/src/main/java/com/android/tools/r8/tracereferences/Tracer.java b/src/main/java/com/android/tools/r8/tracereferences/Tracer.java
index 2bac333..039f28d 100644
--- a/src/main/java/com/android/tools/r8/tracereferences/Tracer.java
+++ b/src/main/java/com/android/tools/r8/tracereferences/Tracer.java
@@ -236,7 +236,7 @@
         AppInfoWithClassHierarchy.createInitialAppInfoWithClassHierarchy(
             application,
             ClassToFeatureSplitMap.createEmptyClassToFeatureSplitMap(),
-            MainDexInfo.createEmptyMainDexClasses());
+            MainDexInfo.none());
   }
 
   void run(TraceReferencesConsumer consumer) {
diff --git a/src/test/java/com/android/tools/r8/TestBase.java b/src/test/java/com/android/tools/r8/TestBase.java
index 3df21b1..a80cc32 100644
--- a/src/test/java/com/android/tools/r8/TestBase.java
+++ b/src/test/java/com/android/tools/r8/TestBase.java
@@ -710,7 +710,7 @@
     return AppInfoWithClassHierarchy.createInitialAppInfoWithClassHierarchy(
         readApplicationForDexOutput(app, new InternalOptions()),
         ClassToFeatureSplitMap.createEmptyClassToFeatureSplitMap(),
-        MainDexInfo.createEmptyMainDexClasses());
+        MainDexInfo.none());
   }
 
   protected static AppView<AppInfoWithClassHierarchy> computeAppViewWithClassHierachy(
diff --git a/src/test/java/com/android/tools/r8/maindexlist/MainDexListMergeInRootTest.java b/src/test/java/com/android/tools/r8/maindexlist/MainDexListMergeInRootTest.java
index 7041c75..9451f9a 100644
--- a/src/test/java/com/android/tools/r8/maindexlist/MainDexListMergeInRootTest.java
+++ b/src/test/java/com/android/tools/r8/maindexlist/MainDexListMergeInRootTest.java
@@ -4,17 +4,13 @@
 
 package com.android.tools.r8.maindexlist;
 
-import static com.android.tools.r8.DiagnosticsMatcher.diagnosticMessage;
-import static com.android.tools.r8.utils.codeinspector.AssertUtils.assertFailsCompilation;
-import static org.hamcrest.CoreMatchers.containsString;
-import static org.junit.Assume.assumeTrue;
-
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.NoHorizontalClassMerging;
 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.HorizontallyMergedClassesInspector;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -27,7 +23,10 @@
 
   @Parameters(name = "{0}")
   public static TestParametersCollection data() {
-    return getTestParameters().withDexRuntimes().withAllApiLevels().build();
+    return getTestParameters()
+        .withDexRuntimes()
+        .withApiLevelsEndingAtExcluding(apiLevelWithNativeMultiDexSupport())
+        .build();
   }
 
   public MainDexListMergeInRootTest(TestParameters parameters) {
@@ -35,35 +34,26 @@
   }
 
   @Test
-  public void testMainDexTracing() {
-    assumeTrue(parameters.getDexRuntimeVersion().isDalvik());
-    assertFailsCompilation(
-        () ->
-            testForR8(parameters.getBackend())
-                .addProgramClasses(OutsideMainDex.class, InsideA.class, InsideB.class, Main.class)
-                .addKeepClassAndMembersRules(Main.class)
-                .setMinApi(parameters.getApiLevel())
-                .enableNeverClassInliningAnnotations()
-                .enableNoHorizontalClassMergingAnnotations()
-                .enableInliningAnnotations()
-                .noMinification()
-                .addMainDexRules(
-                    "-keep class "
-                        + Main.class.getTypeName()
-                        + " { public static void main(***); }")
-                .addOptionsModification(
-                    options -> {
-                      options.testing.checkForNotExpandingMainDexTracingResult = true;
-                    })
-                .compileWithExpectedDiagnostics(
-                    diagnostics -> {
-                      diagnostics.assertErrorsMatch(
-                          diagnosticMessage(
-                              containsString(
-                                  "Class com.android.tools.r8.maindexlist"
-                                      + ".MainDexListMergeInRootTest$OutsideMainDex"
-                                      + " was not a main dex root in the first round")));
-                    }));
+  public void testMainDexTracing() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(OutsideMainDex.class, InsideA.class, InsideB.class, Main.class)
+        .addKeepClassAndMembersRules(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .enableNeverClassInliningAnnotations()
+        .enableNoHorizontalClassMergingAnnotations()
+        .enableInliningAnnotations()
+        .noMinification()
+        .addMainDexRules(
+            "-keep class " + Main.class.getTypeName() + " { public static void main(***); }")
+        .addOptionsModification(
+            options -> {
+              options.testing.checkForNotExpandingMainDexTracingResult = true;
+            })
+        // TODO(b/178151906): See if we can merge the classes.
+        .addHorizontallyMergedClassesInspector(
+            HorizontallyMergedClassesInspector::assertNoClassesMerged)
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("InsideB::live0", "InsideA::live");
   }
 
   @NoHorizontalClassMerging
@@ -80,7 +70,7 @@
   public static class InsideA {
 
     public void bar() {
-      System.out.println("A::live");
+      System.out.println("InsideA::live");
     }
 
     /* Not a traced root */