diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 7f77c6b..494a62b 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -431,6 +431,7 @@
       new SourceFileRewriter(appView.appInfo(), options).run();
       timing.end();
 
+      MainDexClasses mainDexClasses = MainDexClasses.NONE;
       if (!options.mainDexKeepRules.isEmpty()) {
         appView.setAppInfo(new AppInfoWithSubtyping(application));
         Enqueuer enqueuer = new Enqueuer(appView, options, true);
@@ -444,8 +445,7 @@
         // LiveTypes is the tracing result.
         Set<DexType> mainDexBaseClasses = new HashSet<>(mainDexAppInfo.liveTypes);
         // Calculate the automatic main dex list according to legacy multidex constraints.
-        MainDexClasses mainDexClasses =
-            new MainDexListBuilder(mainDexBaseClasses, application).run();
+        mainDexClasses = new MainDexListBuilder(mainDexBaseClasses, application).run();
         if (!mainDexRootSet.checkDiscarded.isEmpty()) {
           new DiscardedChecker(
                   mainDexRootSet, mainDexClasses.getClasses(), appView.appInfo(), options)
@@ -459,8 +459,6 @@
           ReasonPrinter reasonPrinter = enqueuer.getReasonPrinter(mainDexRootSet.reasonAsked);
           reasonPrinter.run(mainDexApplication);
         }
-        // Add automatic main dex classes to an eventual manual list of classes.
-        application = application.builder().addToMainDexList(mainDexClasses.getClasses()).build();
       }
 
       appView.setAppInfo(new AppInfoWithSubtyping(application));
@@ -484,12 +482,21 @@
             reasonPrinter.run(application);
             // Remove annotations that refer to types that no longer exist.
             new AnnotationRemover(appView.appInfo().withLiveness(), options).run();
+            if (!mainDexClasses.isEmpty()) {
+              // Remove types that no longer exists from the computed main dex list.
+              mainDexClasses = mainDexClasses.prunedCopy(appView.appInfo().withLiveness());
+            }
           }
         } finally {
           timing.end();
         }
       }
 
+      // Add automatic main dex classes to an eventual manual list of classes.
+      if (!options.mainDexKeepRules.isEmpty()) {
+        application = application.builder().addToMainDexList(mainDexClasses.getClasses()).build();
+      }
+
       // Only perform discard-checking if tree-shaking is turned on.
       if (options.enableTreeShaking && !rootSet.checkDiscarded.isEmpty()) {
         new DiscardedChecker(rootSet, application, options).run();
diff --git a/src/main/java/com/android/tools/r8/shaking/MainDexClasses.java b/src/main/java/com/android/tools/r8/shaking/MainDexClasses.java
index 3869db6..565a5df 100644
--- a/src/main/java/com/android/tools/r8/shaking/MainDexClasses.java
+++ b/src/main/java/com/android/tools/r8/shaking/MainDexClasses.java
@@ -7,13 +7,19 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Set;
+import java.util.function.Consumer;
+import java.util.function.Predicate;
 
 public class MainDexClasses {
 
+  public static MainDexClasses NONE = new MainDexClasses(ImmutableSet.of(), ImmutableSet.of());
+
   public static class Builder {
     public final AppInfo appInfo;
     public final Set<DexType> roots = Sets.newIdentityHashSet();
@@ -23,6 +29,12 @@
       this.appInfo = appInfo;
     }
 
+    public Builder addRoot(DexType type) {
+      assert isProgramClass(type) : type.toSourceString();
+      roots.add(type);
+      return this;
+    }
+
     public Builder addRoots(Collection<DexType> rootSet) {
       assert rootSet.stream().allMatch(this::isProgramClass);
       this.roots.addAll(rootSet);
@@ -50,21 +62,26 @@
   }
 
   // The classes in the root set.
-  private final Set<DexType> rootSet;
-  // Additional dependencies (direct dependencise and runtime annotations with enums).
+  private final Set<DexType> roots;
+  // Additional dependencies (direct dependencies and runtime annotations with enums).
   private final Set<DexType> dependencies;
   // All main dex classes.
   private final Set<DexType> classes;
 
-  private MainDexClasses(Set<DexType> rootSet, Set<DexType> dependencies) {
-    assert Sets.intersection(rootSet, dependencies).isEmpty();
-    this.rootSet = Collections.unmodifiableSet(rootSet);
+  private MainDexClasses(Set<DexType> roots, Set<DexType> dependencies) {
+    assert Sets.intersection(roots, dependencies).isEmpty();
+    this.roots = Collections.unmodifiableSet(roots);
     this.dependencies = Collections.unmodifiableSet(dependencies);
-    this.classes = Sets.union(rootSet, dependencies);
+    this.classes = Sets.union(roots, dependencies);
+  }
+
+  public boolean isEmpty() {
+    assert !roots.isEmpty() || dependencies.isEmpty();
+    return roots.isEmpty();
   }
 
   public Set<DexType> getRoots() {
-    return rootSet;
+    return roots;
   }
 
   public Set<DexType> getDependencies() {
@@ -75,6 +92,24 @@
     return classes;
   }
 
+  private void collectTypesMatching(
+      Set<DexType> types, Predicate<DexType> predicate, Consumer<DexType> consumer) {
+    types.forEach(
+        type -> {
+          if (predicate.test(type)) {
+            consumer.accept(type);
+          }
+        });
+  }
+
+  public MainDexClasses prunedCopy(AppInfoWithLiveness appInfo) {
+    Builder builder = builder(appInfo);
+    Predicate<DexType> wasPruned = appInfo::wasPruned;
+    collectTypesMatching(roots, wasPruned.negate(), builder::addRoot);
+    collectTypesMatching(dependencies, wasPruned.negate(), builder::addDependency);
+    return builder.build();
+  }
+
   public static Builder builder(AppInfo appInfo) {
     return new Builder(appInfo);
   }
diff --git a/src/test/java/com/android/tools/r8/R8TestBuilder.java b/src/test/java/com/android/tools/r8/R8TestBuilder.java
index ee0e8af..4404bae 100644
--- a/src/test/java/com/android/tools/r8/R8TestBuilder.java
+++ b/src/test/java/com/android/tools/r8/R8TestBuilder.java
@@ -10,10 +10,12 @@
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.InternalOptions;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collection;
 import java.util.List;
 import java.util.function.Consumer;
 import java.util.function.Supplier;
+import java.util.stream.Collectors;
 
 public class R8TestBuilder
     extends TestShrinkerBuilder<
@@ -64,6 +66,28 @@
     return self();
   }
 
+  public R8TestBuilder addMainDexRules(Collection<String> rules) {
+    builder.addMainDexRules(new ArrayList<>(rules), Origin.unknown());
+    return self();
+  }
+
+  public R8TestBuilder addMainDexRules(String... rules) {
+    return addMainDexRules(Arrays.asList(rules));
+  }
+
+  public R8TestBuilder addMainDexClassRules(Class<?>... classes) {
+    for (Class<?> clazz : classes) {
+      addMainDexRules("-keep class " + clazz.getTypeName());
+    }
+    return self();
+  }
+
+  public R8TestBuilder addMainDexListClasses(Class<?>... classes) {
+    builder.addMainDexClasses(
+        Arrays.stream(classes).map(Class::getTypeName).collect(Collectors.toList()));
+    return self();
+  }
+
   public R8TestBuilder enableInliningAnnotations() {
     if (!enableInliningAnnotations) {
       enableInliningAnnotations = true;
diff --git a/src/test/java/com/android/tools/r8/TestCompileResult.java b/src/test/java/com/android/tools/r8/TestCompileResult.java
index 34ffcaa..c750ded 100644
--- a/src/test/java/com/android/tools/r8/TestCompileResult.java
+++ b/src/test/java/com/android/tools/r8/TestCompileResult.java
@@ -96,7 +96,30 @@
         return this;
       }
     }
-    fail("No warning matches " + matcher.toString());
+    StringBuilder builder = new StringBuilder("No warning matches " + matcher.toString());
+    builder.append(System.lineSeparator());
+    if (getDiagnosticMessages().getWarnings().size() == 0) {
+      builder.append("There where no warnings.");
+    } else {
+      builder.append("There where " + getDiagnosticMessages().getWarnings().size() + " warnings:");
+      builder.append(System.lineSeparator());
+      for (int i = 0; i < getDiagnosticMessages().getWarnings().size(); i++) {
+        builder.append(getDiagnosticMessages().getWarnings().get(i).getDiagnosticMessage());
+        builder.append(System.lineSeparator());
+      }
+    }
+    fail(builder.toString());
+    return this;
+  }
+
+  public TestCompileResult<RR> assertNoWarningMessageThatMatches(Matcher<String> matcher) {
+    assertNotEquals(0, getDiagnosticMessages().getWarnings().size());
+    for (int i = 0; i < getDiagnosticMessages().getWarnings().size(); i++) {
+      String message = getDiagnosticMessages().getWarnings().get(i).getDiagnosticMessage();
+      if (matcher.matches(message)) {
+        fail("The warning: \"" + message + "\" + matches " + matcher + ".");
+      }
+    }
     return this;
   }
 
diff --git a/src/test/java/com/android/tools/r8/maindexlist/warnings/MainDexWarningsTest.java b/src/test/java/com/android/tools/r8/maindexlist/warnings/MainDexWarningsTest.java
new file mode 100644
index 0000000..e6ca563
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/maindexlist/warnings/MainDexWarningsTest.java
@@ -0,0 +1,101 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.maindexlist.warnings;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.containsString;
+import static org.junit.Assert.assertThat;
+
+import com.android.tools.r8.ForceInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.google.common.collect.ImmutableList;
+import java.util.List;
+import org.hamcrest.CoreMatchers;
+import org.junit.Test;
+
+public class MainDexWarningsTest extends TestBase {
+
+  private List<Class<?>> testClasses = ImmutableList.of(Main.class, Static.class, Static2.class);
+  private Class<?> mainClass = Main.class;
+
+  private void classStaticGone(CodeInspector inspector) {
+    assertThat(inspector.clazz(Static.class), CoreMatchers.not(isPresent()));
+    assertThat(inspector.clazz(Static2.class), CoreMatchers.not(isPresent()));
+  }
+
+  @Test
+  public void testNoWarningFromMainDexRules() throws Exception {
+    testForR8(Backend.DEX)
+        .setMinApi(AndroidApiLevel.K)
+        .enableInliningAnnotations()
+        .addProgramClasses(testClasses)
+        .addKeepMainRule(mainClass)
+        // Include main dex rule for class Static.
+        .addMainDexClassRules(Main.class, Static.class)
+        .compile()
+        .inspect(this::classStaticGone)
+        .assertNoMessages();
+  }
+
+  @Test
+  public void testWarningFromManualMainDexList() throws Exception {
+    testForR8(Backend.DEX)
+        .setMinApi(AndroidApiLevel.K)
+        .enableInliningAnnotations()
+        .addProgramClasses(testClasses)
+        .addKeepMainRule(mainClass)
+        // Include explicit main dex entry for class Static.
+        .addMainDexListClasses(Static.class)
+        .compile()
+        .inspect(this::classStaticGone)
+        .assertOnlyWarnings()
+        .assertWarningMessageThatMatches(containsString("Application does not contain"))
+        .assertWarningMessageThatMatches(containsString(Static.class.getTypeName()))
+        .assertWarningMessageThatMatches(containsString("as referenced in main-dex-list"));
+  }
+
+  @Test
+  public void testWarningFromManualMainDexListWithRuleAsWell() throws Exception {
+    testForR8(Backend.DEX)
+        .setMinApi(AndroidApiLevel.K)
+        .enableInliningAnnotations()
+        .addProgramClasses(testClasses)
+        .addKeepMainRule(mainClass)
+        // Include explicit main dex entry for class Static.
+        .addMainDexListClasses(Main.class, Static.class)
+        // Include main dex rule for class Static2.
+        .addMainDexClassRules(Static2.class)
+        .compile()
+        .inspect(this::classStaticGone)
+        .assertOnlyWarnings()
+        .assertWarningMessageThatMatches(containsString("Application does not contain"))
+        .assertWarningMessageThatMatches(containsString(Static.class.getTypeName()))
+        .assertWarningMessageThatMatches(containsString("as referenced in main-dex-list"))
+        .assertNoWarningMessageThatMatches(containsString(Static2.class.getTypeName()));
+  }
+}
+
+class Main {
+  public static void main(String[] args) {
+    System.out.println(Static.m());
+    System.out.println(Static2.m());
+  }
+}
+
+class Static {
+  @ForceInline
+  public static int m() {
+    return 1;
+  }
+}
+
+class Static2 {
+  @ForceInline
+  public static int m() {
+    return 1;
+  }
+}