diff --git a/src/test/java/com/android/tools/r8/TestShrinkerBuilder.java b/src/test/java/com/android/tools/r8/TestShrinkerBuilder.java
index acd96aa..83f1fbb 100644
--- a/src/test/java/com/android/tools/r8/TestShrinkerBuilder.java
+++ b/src/test/java/com/android/tools/r8/TestShrinkerBuilder.java
@@ -119,6 +119,24 @@
     return addKeepRules("-dontshrink");
   }
 
+  public T addDontNote(Class<?>... classes) {
+    for (Class<?> clazz : classes) {
+      addDontNote(clazz.getTypeName());
+    }
+    return self();
+  }
+
+  public T addDontNote(Collection<String> classes) {
+    for (String clazz : classes) {
+      addKeepRules("-dontnote " + clazz);
+    }
+    return self();
+  }
+
+  public T addDontNote(String... classes) {
+    return addDontNote(Arrays.asList(classes));
+  }
+
   public T addDontWarn(Class<?>... classes) {
     for (Class<?> clazz : classes) {
       addDontWarn(clazz.getTypeName());
diff --git a/src/test/java/com/android/tools/r8/shaking/keep/ExtendsMissingClassDirectTest.java b/src/test/java/com/android/tools/r8/shaking/keep/ExtendsMissingClassDirectTest.java
new file mode 100644
index 0000000..a7c5297
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/keep/ExtendsMissingClassDirectTest.java
@@ -0,0 +1,70 @@
+// Copyright (c) 2021, 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.shaking.keep;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.ProguardVersion;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.TestShrinkerBuilder;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.google.common.collect.ImmutableList;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ExtendsMissingClassDirectTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    run(testForR8(Backend.CF).allowUnusedProguardConfigurationRules());
+  }
+
+  @Test
+  public void testProguard() throws Exception {
+    run(
+        testForProguard(ProguardVersion.V7_0_0)
+            .addDontWarn(MissingClass.class)
+            .addDontWarn(ExtendsMissingClassDirectTest.class));
+  }
+
+  private <T extends TestShrinkerBuilder<?, ?, ?, ?, T>> void run(T builder) throws Exception {
+    builder
+        .addProgramClasses(Main.class, A.class)
+        .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.LATEST))
+        .addKeepMainRule(Main.class)
+        .addKeepRules("-keep class ** extends " + MissingClass.class.getTypeName())
+        .compile()
+        .inspect(
+            inspector ->
+                assertEquals(
+                    ImmutableList.of(inspector.clazz(Main.class)), inspector.allClasses()));
+  }
+
+  static class MissingClass {}
+
+  static class A extends MissingClass {}
+
+  static class Main {
+
+    public static void main(String[] args) {
+      System.out.println("Hello, world!");
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/keep/ExtendsMissingClassTransitiveTest.java b/src/test/java/com/android/tools/r8/shaking/keep/ExtendsMissingClassTransitiveTest.java
new file mode 100644
index 0000000..2f7bcd4
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/keep/ExtendsMissingClassTransitiveTest.java
@@ -0,0 +1,72 @@
+// Copyright (c) 2021, 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.shaking.keep;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.ProguardVersion;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.TestShrinkerBuilder;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.google.common.collect.ImmutableList;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ExtendsMissingClassTransitiveTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    run(testForR8(Backend.CF).allowUnusedProguardConfigurationRules());
+  }
+
+  @Test
+  public void testProguard() throws Exception {
+    run(
+        testForProguard(ProguardVersion.V7_0_0)
+            .addDontWarn(MissingClass.class)
+            .addDontWarn(ExtendsMissingClassTransitiveTest.class));
+  }
+
+  private <T extends TestShrinkerBuilder<?, ?, ?, ?, T>> void run(T builder) throws Exception {
+    builder
+        .addProgramClasses(Main.class, A.class, B.class)
+        .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.LATEST))
+        .addKeepMainRule(Main.class)
+        .addKeepRules("-keep class ** extends " + MissingClass.class.getTypeName())
+        .compile()
+        .inspect(
+            inspector ->
+                assertEquals(
+                    ImmutableList.of(inspector.clazz(Main.class)), inspector.allClasses()));
+  }
+
+  static class MissingClass {}
+
+  static class A extends MissingClass {}
+
+  static class B extends A {}
+
+  static class Main {
+
+    public static void main(String[] args) {
+      System.out.println("Hello, world!");
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/keep/ImplementsMissingClassDirectTest.java b/src/test/java/com/android/tools/r8/shaking/keep/ImplementsMissingClassDirectTest.java
new file mode 100644
index 0000000..a4724aa
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/keep/ImplementsMissingClassDirectTest.java
@@ -0,0 +1,70 @@
+// Copyright (c) 2021, 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.shaking.keep;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.ProguardVersion;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.TestShrinkerBuilder;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.google.common.collect.ImmutableList;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ImplementsMissingClassDirectTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    run(testForR8(Backend.CF).allowUnusedProguardConfigurationRules());
+  }
+
+  @Test
+  public void testProguard() throws Exception {
+    run(
+        testForProguard(ProguardVersion.V7_0_0)
+            .addDontWarn(MissingInterface.class)
+            .addDontWarn(ImplementsMissingClassDirectTest.class));
+  }
+
+  private <T extends TestShrinkerBuilder<?, ?, ?, ?, T>> void run(T builder) throws Exception {
+    builder
+        .addProgramClasses(Main.class, A.class)
+        .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.LATEST))
+        .addKeepMainRule(Main.class)
+        .addKeepRules("-keep class ** implements " + MissingInterface.class.getTypeName())
+        .compile()
+        .inspect(
+            inspector ->
+                assertEquals(
+                    ImmutableList.of(inspector.clazz(Main.class)), inspector.allClasses()));
+  }
+
+  interface MissingInterface {}
+
+  static class A implements MissingInterface {}
+
+  static class Main {
+
+    public static void main(String[] args) {
+      System.out.println("Hello, world!");
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/keep/ImplementsMissingClassTransitiveTest.java b/src/test/java/com/android/tools/r8/shaking/keep/ImplementsMissingClassTransitiveTest.java
new file mode 100644
index 0000000..a087d90
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/keep/ImplementsMissingClassTransitiveTest.java
@@ -0,0 +1,72 @@
+// Copyright (c) 2021, 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.shaking.keep;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.ProguardVersion;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.TestShrinkerBuilder;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.google.common.collect.ImmutableList;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ImplementsMissingClassTransitiveTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    run(testForR8(Backend.CF).allowUnusedProguardConfigurationRules());
+  }
+
+  @Test
+  public void testProguard() throws Exception {
+    run(
+        testForProguard(ProguardVersion.V7_0_0)
+            .addDontWarn(MissingInterface.class)
+            .addDontWarn(ImplementsMissingClassTransitiveTest.class));
+  }
+
+  private <T extends TestShrinkerBuilder<?, ?, ?, ?, T>> void run(T builder) throws Exception {
+    builder
+        .addProgramClasses(Main.class, A.class, B.class)
+        .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.LATEST))
+        .addKeepMainRule(Main.class)
+        .addKeepRules("-keep class ** implements " + MissingInterface.class.getTypeName())
+        .compile()
+        .inspect(
+            inspector ->
+                assertEquals(
+                    ImmutableList.of(inspector.clazz(Main.class)), inspector.allClasses()));
+  }
+
+  interface MissingInterface {}
+
+  static class A implements MissingInterface {}
+
+  static class B extends A {}
+
+  static class Main {
+
+    public static void main(String[] args) {
+      System.out.println("Hello, world!");
+    }
+  }
+}