diff --git a/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationMatcher.java b/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationMatcher.java
index 0d7e1b2..13b1b4f 100644
--- a/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationMatcher.java
+++ b/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationMatcher.java
@@ -249,7 +249,7 @@
           // No valid match, so the rule is discarded. This should likely be a diagnostics info.
           return;
         }
-        if (!predicates.matchesClass(clazz, classPattern)) {
+        if (!predicates.matchesClass(clazz, classPattern, appInfo)) {
           // Invalid match for this class.
           return;
         }
@@ -257,7 +257,7 @@
       } else {
         // TODO(b/323816623): This repeated iteration on all classes must be avoided.
         for (DexProgramClass clazz : appInfo.classes()) {
-          if (predicates.matchesClass(clazz, classPattern)) {
+          if (predicates.matchesClass(clazz, classPattern, appInfo)) {
             continueWithClass(classIndex, clazz);
           }
         }
diff --git a/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationMatcherPredicates.java b/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationMatcherPredicates.java
index 364a17f..05cd43c 100644
--- a/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationMatcherPredicates.java
+++ b/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationMatcherPredicates.java
@@ -6,6 +6,7 @@
 
 import com.android.tools.r8.errors.Unimplemented;
 import com.android.tools.r8.graph.AccessFlags;
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.DexAnnotation;
 import com.android.tools.r8.graph.DexAnnotationSet;
 import com.android.tools.r8.graph.DexEncodedField;
@@ -38,6 +39,7 @@
 import com.android.tools.r8.keepanno.ast.KeepUnqualfiedClassNamePattern;
 import com.android.tools.r8.keepanno.ast.ModifierPattern;
 import com.android.tools.r8.keepanno.ast.OptionalPattern;
+import com.android.tools.r8.utils.TraversalContinuation;
 import java.util.List;
 
 public class KeepAnnotationMatcherPredicates {
@@ -48,10 +50,11 @@
     this.factory = factory;
   }
 
-  public boolean matchesClass(DexProgramClass clazz, KeepClassItemPattern classPattern) {
+  public boolean matchesClass(
+      DexProgramClass clazz, KeepClassItemPattern classPattern, AppInfoWithClassHierarchy appInfo) {
     return matchesClassName(clazz.getType(), classPattern.getClassNamePattern())
-        && matchesInstanceOfPattern(clazz, classPattern.getInstanceOfPattern())
-        && matchesAnnotatedBy(clazz.annotations(), classPattern.getAnnotatedByPattern());
+        && matchesAnnotatedBy(clazz.annotations(), classPattern.getAnnotatedByPattern())
+        && matchesInstanceOfPattern(clazz, classPattern.getInstanceOfPattern(), appInfo);
   }
 
   public boolean matchesClassName(DexType type, KeepQualifiedClassNamePattern pattern) {
@@ -83,11 +86,25 @@
   }
 
   private boolean matchesInstanceOfPattern(
-      DexProgramClass unusedClazz, KeepInstanceOfPattern pattern) {
+      DexProgramClass clazz, KeepInstanceOfPattern pattern, AppInfoWithClassHierarchy appInfo) {
     if (pattern.isAny()) {
       return true;
     }
-    throw new Unimplemented();
+    if (pattern.isInclusive()) {
+      if (matchesClassName(clazz.getType(), pattern.getClassNamePattern())) {
+        return true;
+      }
+    }
+    return appInfo
+        .traverseSuperTypes(
+            clazz,
+            (superType, unusedSubClass, unusedIsInterface) -> {
+              if (matchesClassName(superType, pattern.getClassNamePattern())) {
+                return TraversalContinuation.doBreak();
+              }
+              return TraversalContinuation.doContinue();
+            })
+        .isBreak();
   }
 
   public boolean matchesGeneralMember(DexEncodedMember<?, ?> member, KeepMemberPattern pattern) {
diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepInclusiveInstanceOfTest.java b/src/test/java/com/android/tools/r8/keepanno/KeepInclusiveInstanceOfTest.java
index 85809df..6643f76 100644
--- a/src/test/java/com/android/tools/r8/keepanno/KeepInclusiveInstanceOfTest.java
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepInclusiveInstanceOfTest.java
@@ -30,6 +30,7 @@
   @Test
   public void test() throws Exception {
     testForKeepAnno(parameters)
+        .enableNativeInterpretation()
         .addProgramClasses(getInputClasses())
         .addKeepMainRule(TestClass.class)
         .setExcludedOuterClass(getClass())
diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepNameAndInstanceOfTest.java b/src/test/java/com/android/tools/r8/keepanno/KeepNameAndInstanceOfTest.java
index b36cca3..27b12cf 100644
--- a/src/test/java/com/android/tools/r8/keepanno/KeepNameAndInstanceOfTest.java
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepNameAndInstanceOfTest.java
@@ -31,6 +31,7 @@
   @Test
   public void test() throws Exception {
     testForKeepAnno(parameters)
+        .enableNativeInterpretation()
         .addProgramClasses(getInputClasses())
         .addKeepMainRule(TestClass.class)
         .setExcludedOuterClass(getClass())