diff --git a/.gitignore b/.gitignore
index 7b33dbf..d9cb978 100644
--- a/.gitignore
+++ b/.gitignore
@@ -49,6 +49,8 @@
 third_party/jdwp-tests
 third_party/kotlin.tar.gz
 third_party/kotlin
+third_party/nest/*
+!third_party/nest/*.sha1
 third_party/photos/*
 !third_party/photos/*.sha1
 third_party/proguard/*
diff --git a/build.gradle b/build.gradle
index 2276798..a542ea4 100644
--- a/build.gradle
+++ b/build.gradle
@@ -339,6 +339,7 @@
         "gmscore/gmscore_v9",
         "gmscore/gmscore_v10",
         "gmscore/latest",
+        "nest/nest_20180926_7c6cfb",
         "photos/2017-06-06",
         "youtube/youtube.android_12.10",
         "youtube/youtube.android_12.17",
diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java
index bbc5922..3df31fd 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -14,6 +14,7 @@
 import java.util.List;
 import java.util.Set;
 import java.util.function.Consumer;
+import java.util.function.Predicate;
 
 public abstract class DexClass extends DexDefinition {
 
@@ -432,6 +433,10 @@
     innerClasses.clear();
   }
 
+  public void removeInnerClasses(Predicate<InnerClassAttribute> predicate) {
+    innerClasses.removeIf(predicate::test);
+  }
+
   /** Returns kotlin class info if the class is synthesized by kotlin compiler. */
   public abstract KotlinInfo getKotlinInfo();
 
diff --git a/src/main/java/com/android/tools/r8/shaking/TreePruner.java b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
index 3ae9174..0400670 100644
--- a/src/main/java/com/android/tools/r8/shaking/TreePruner.java
+++ b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.InnerClassAttribute;
 import com.android.tools.r8.graph.KeyedDexItem;
 import com.android.tools.r8.graph.PresortedComparable;
 import com.android.tools.r8.logging.Log;
@@ -98,12 +99,18 @@
         clazz.setVirtualMethods(reachableMethods(clazz.virtualMethods(), clazz));
         clazz.setInstanceFields(reachableFields(clazz.instanceFields()));
         clazz.setStaticFields(reachableFields(clazz.staticFields()));
+        clazz.removeInnerClasses(this::isAttributeReferencingPrunedType);
         usagePrinter.visited();
       }
     }
     return newClasses;
   }
 
+  private boolean isAttributeReferencingPrunedType(InnerClassAttribute attr) {
+    return !appInfo.liveTypes.contains(attr.getInner())
+        || !appInfo.liveTypes.contains(attr.getOuter());
+  }
+
   private <S extends PresortedComparable<S>, T extends KeyedDexItem<S>> int firstUnreachableIndex(
       T[] items, Predicate<S> live) {
     for (int i = 0; i < items.length; i++) {
diff --git a/src/test/java/com/android/tools/r8/internal/CompilationTestBase.java b/src/test/java/com/android/tools/r8/internal/CompilationTestBase.java
index 2ec38b4..0607b0e 100644
--- a/src/test/java/com/android/tools/r8/internal/CompilationTestBase.java
+++ b/src/test/java/com/android/tools/r8/internal/CompilationTestBase.java
@@ -21,7 +21,6 @@
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.naming.MemberNaming.FieldSignature;
 import com.android.tools.r8.naming.MemberNaming.MethodSignature;
-import com.android.tools.r8.shaking.ProguardRuleParserException;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.AndroidAppConsumers;
@@ -48,6 +47,7 @@
 import java.util.concurrent.ExecutionException;
 import java.util.function.BiConsumer;
 import java.util.function.Consumer;
+import java.util.stream.Collectors;
 import org.junit.ComparisonFailure;
 import org.junit.Rule;
 import org.junit.rules.TemporaryFolder;
@@ -61,12 +61,11 @@
       CompilerUnderTest compiler,
       CompilationMode mode,
       String referenceApk,
-      String pgConf,
+      List<String> pgConfs,
       String input)
-      throws ExecutionException, IOException, ProguardRuleParserException,
-          CompilationFailedException {
+      throws ExecutionException, IOException, CompilationFailedException {
     return runAndCheckVerification(
-        compiler, mode, referenceApk, pgConf, null, Collections.singletonList(input));
+        compiler, mode, referenceApk, pgConfs, null, Collections.singletonList(input));
   }
 
   public AndroidApp runAndCheckVerification(D8Command.Builder builder, String referenceApk)
@@ -82,18 +81,18 @@
       CompilerUnderTest compiler,
       CompilationMode mode,
       String referenceApk,
-      String pgConf,
+      List<String> pgConfs,
       Consumer<InternalOptions> optionsConsumer,
       List<String> inputs)
-      throws ExecutionException, IOException, ProguardRuleParserException,
-      CompilationFailedException {
+      throws ExecutionException, IOException, CompilationFailedException {
     assertTrue(referenceApk == null || new File(referenceApk).exists());
     AndroidAppConsumers outputApp;
     if (compiler == CompilerUnderTest.R8) {
       R8Command.Builder builder = R8Command.builder();
       builder.addProgramFiles(ListUtils.map(inputs, Paths::get));
-      if (pgConf != null) {
-        builder.addProguardConfigurationFiles(Paths.get(pgConf));
+      if (pgConfs != null) {
+        builder.addProguardConfigurationFiles(
+            pgConfs.stream().map(Paths::get).collect(Collectors.toList()));
       }
       builder.setMode(mode);
       builder.setProgramConsumer(DexIndexedConsumer.emptyConsumer());
diff --git a/src/test/java/com/android/tools/r8/internal/D8PhotosVerificationTest.java b/src/test/java/com/android/tools/r8/internal/D8PhotosVerificationTest.java
index 390105e..4094bb7 100644
--- a/src/test/java/com/android/tools/r8/internal/D8PhotosVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/D8PhotosVerificationTest.java
@@ -6,7 +6,6 @@
 import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.CompilationMode;
 import com.android.tools.r8.R8RunArtTestsTest.CompilerUnderTest;
-import com.android.tools.r8.shaking.ProguardRuleParserException;
 import java.io.IOException;
 import java.util.concurrent.ExecutionException;
 import org.junit.Test;
@@ -16,8 +15,7 @@
       "third_party/photos/2017-06-06/PhotosEnglishOnlyLegacy_proguard.jar";
 
   public void runD8AndCheckVerification(CompilationMode mode, String version)
-      throws ProguardRuleParserException, ExecutionException, IOException,
-      CompilationFailedException {
+      throws ExecutionException, IOException, CompilationFailedException {
     runAndCheckVerification(CompilerUnderTest.D8, mode, version, null, version);
   }
 
diff --git a/src/test/java/com/android/tools/r8/internal/NestCompilationBase.java b/src/test/java/com/android/tools/r8/internal/NestCompilationBase.java
new file mode 100644
index 0000000..3328d0f
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/internal/NestCompilationBase.java
@@ -0,0 +1,12 @@
+// 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.internal;
+
+public abstract class NestCompilationBase extends CompilationTestBase {
+  static final String BASE = "third_party/nest/nest_20180926_7c6cfb/";
+  static final String DEPLOY_JAR = "obsidian-development-debug.jar";
+  static final String PG_CONF = "proguard/proguard.cfg";
+  static final String PG_CONF_NO_OPT = "proguard/proguard-no-optimizations.cfg";
+}
diff --git a/src/test/java/com/android/tools/r8/internal/NestTreeShakeJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/NestTreeShakeJarVerificationTest.java
new file mode 100644
index 0000000..ed7a5d8
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/internal/NestTreeShakeJarVerificationTest.java
@@ -0,0 +1,48 @@
+// 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.internal;
+
+import static org.hamcrest.CoreMatchers.containsString;
+import static org.junit.Assert.assertThat;
+import static org.junit.internal.matchers.ThrowableMessageMatcher.hasMessage;
+
+import com.android.tools.r8.CompilationMode;
+import com.android.tools.r8.R8RunArtTestsTest.CompilerUnderTest;
+import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.codeinspector.ClassHierarchyVerifier;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.google.common.collect.ImmutableList;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class NestTreeShakeJarVerificationTest extends NestCompilationBase {
+
+  @Test
+  public void buildAndTreeShakeFromDeployJar() throws Exception {
+    AndroidApp app =
+        runAndCheckVerification(
+            CompilerUnderTest.R8,
+            CompilationMode.RELEASE,
+            null,
+            ImmutableList.of(BASE + PG_CONF, BASE + PG_CONF_NO_OPT),
+            null,
+            ImmutableList.of(BASE + DEPLOY_JAR));
+
+
+    // Check that all non-abstract classes implement the abstract methods from their super types.
+    // This is a sanity check for the tree shaking and minification.
+    try {
+      CodeInspector inspector = new CodeInspector(app);
+      new ClassHierarchyVerifier(inspector, false).run();
+    } catch (AssertionError error) {
+      // TODO(b/115705526): Remove try-catch when bug is fixed.
+      assertThat(error, hasMessage(containsString("Non-abstract class")));
+      assertThat(error, hasMessage(containsString("must implement method")));
+      return;
+    }
+
+    Assert.fail("Unreachable");
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreTreeShakeJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreTreeShakeJarVerificationTest.java
index 2da83a6..bbfd381 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreTreeShakeJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreTreeShakeJarVerificationTest.java
@@ -21,15 +21,16 @@
       int maxSize,
       Consumer<InternalOptions> optionsConsumer)
       throws Exception {
-    AndroidApp app = runAndCheckVerification(
-        CompilerUnderTest.R8,
-        mode,
-        hasReference ? base + REFERENCE_APK : null,
-        base + PG_CONF,
-        optionsConsumer,
-        // Don't pass any inputs. The input will be read from the -injars in the Proguard
-        // configuration file.
-        ImmutableList.of());
+    AndroidApp app =
+        runAndCheckVerification(
+            CompilerUnderTest.R8,
+            mode,
+            hasReference ? base + REFERENCE_APK : null,
+            ImmutableList.of(base + PG_CONF),
+            optionsConsumer,
+            // Don't pass any inputs. The input will be read from the -injars in the Proguard
+            // configuration file.
+            ImmutableList.of());
     int bytes = applicationSize(app);
     assertTrue("Expected max size of " + maxSize + ", got " + bytes, bytes < maxSize);
     return app;
diff --git a/src/test/java/com/android/tools/r8/internal/YouTubeTreeShakeJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/YouTubeTreeShakeJarVerificationTest.java
index 4fa8497..20b1930 100644
--- a/src/test/java/com/android/tools/r8/internal/YouTubeTreeShakeJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/YouTubeTreeShakeJarVerificationTest.java
@@ -27,7 +27,7 @@
             CompilerUnderTest.R8,
             CompilationMode.RELEASE,
             BASE + APK,
-            BASE + PG_CONF,
+            ImmutableList.of(BASE + PG_CONF),
             options -> options.proguardMapConsumer = new FileConsumer(proguardMapPath),
             // Don't pass any inputs. The input will be read from the -injars in the Proguard
             // configuration file.
diff --git a/third_party/nest/nest_20180926_7c6cfb.tar.gz.sha1 b/third_party/nest/nest_20180926_7c6cfb.tar.gz.sha1
new file mode 100644
index 0000000..e10bb9e
--- /dev/null
+++ b/third_party/nest/nest_20180926_7c6cfb.tar.gz.sha1
@@ -0,0 +1 @@
+c948f5b97ca768f6190c3e7e1dbfe9044a743839
\ No newline at end of file
diff --git a/tools/nest_data.py b/tools/nest_data.py
new file mode 100644
index 0000000..af3e35a
--- /dev/null
+++ b/tools/nest_data.py
@@ -0,0 +1,36 @@
+# Copyright (c) 2017, 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.
+
+import os
+import utils
+
+THIRD_PARTY = os.path.join(utils.REPO_ROOT, 'third_party')
+ANDROID_L_API = '21'
+BASE = os.path.join(THIRD_PARTY, 'nest')
+
+V20180926_BASE = os.path.join(BASE, 'nest_20180926_7c6cfb')
+
+# NOTE: we always use android.jar for SDK v25, later we might want to revise it
+#       to use proper android.jar version for each of youtube version separately.
+ANDROID_JAR = os.path.join(THIRD_PARTY, 'android_jar', 'lib-v25', 'android.jar')
+
+VERSIONS = {
+  '20180926': {
+    'dex' : {
+      'inputs': [os.path.join(V20180926_BASE, 'obsidian-development-debug.apk')],
+      'libraries' : [ANDROID_JAR],
+      'min-api' : ANDROID_L_API,
+    },
+    'deploy' : {
+      'inputs': [os.path.join(V20180926_BASE, 'obsidian-development-debug.jar')],
+      'libraries' : [ANDROID_JAR],
+      'pgconf': [
+          os.path.join(V20180926_BASE, 'proguard', 'proguard.cfg'),
+          os.path.join(V20180926_BASE, 'proguard', 'proguard-no-optimizations.cfg'),
+          os.path.join(V20180926_BASE, 'proguard', 'proguard-ignore-warnings.cfg')],
+      # Build for native multi dex
+      'min-api' : ANDROID_L_API,
+    }
+  },
+}
diff --git a/tools/run_on_app.py b/tools/run_on_app.py
index 6e46397..83faf45 100755
--- a/tools/run_on_app.py
+++ b/tools/run_on_app.py
@@ -14,13 +14,14 @@
 import gmail_data
 import gmscore_data
 import golem
+import nest_data
 import toolhelper
 import utils
 import youtube_data
 import chrome_data
 
 TYPES = ['dex', 'deploy', 'proguarded']
-APPS = ['gmscore', 'youtube', 'gmail', 'chrome']
+APPS = ['gmscore', 'nest', 'youtube', 'gmail', 'chrome']
 COMPILERS = ['d8', 'r8']
 
 def ParseOptions(argv):
@@ -125,6 +126,7 @@
 def get_permutations():
   data_providers = {
       'gmscore': gmscore_data,
+      'nest': nest_data,
       'youtube': youtube_data,
       'chrome': chrome_data,
       'gmail': gmail_data
@@ -172,6 +174,9 @@
   if options.app == 'gmscore':
     options.version = options.version or 'v9'
     data = gmscore_data
+  elif options.app == 'nest':
+    options.version = options.version or '20180926'
+    data = nest_data
   elif options.app == 'youtube':
     options.version = options.version or '12.22'
     data = youtube_data
@@ -207,10 +212,12 @@
   values = version[options.type]
   inputs = None
   # For R8 'deploy' the JAR is located using the Proguard configuration
-  # -injars option. For chrome we don't have the injars in the proguard files.
+  # -injars option. For chrome and nest we don't have the injars in the
+  # proguard files.
   if 'inputs' in values and (options.compiler != 'r8'
                              or options.type != 'deploy'
-                             or options.app == 'chrome'):
+                             or options.app == 'chrome'
+                             or options.app == 'nest'):
     inputs = values['inputs']
 
   args.extend(['--output', outdir])