Merge commit '8eaf2af0894a26c245e457a8ff9abcadee3c67a7' into dev-release

Change-Id: I9f093ab87dd46d82e4671bd197f09b6bbe249125
diff --git a/d8_r8/main/build.gradle.kts b/d8_r8/main/build.gradle.kts
index d7746ac..f365f9f 100644
--- a/d8_r8/main/build.gradle.kts
+++ b/d8_r8/main/build.gradle.kts
@@ -298,6 +298,12 @@
              // com.android.tools.r8.
              "--map",
              "com.android.tools.r8.**->com.android.tools.r8",
+             // Add identify for the public annotation surface of keepanno
+             "--map",
+             "com.android.tools.r8.keepanno.annotations.**->com.android.tools.r8.keepanno.annotations",
+             // Explicitly move all other keepanno utilities.
+             "--map",
+             "com.android.tools.r8.keepanno.**->com.android.tools.r8.relocated.keepanno",
              "--map",
              "com.android.**->com.android.tools.r8.com.android",
              "--map",
diff --git a/d8_r8/test/build.gradle.kts b/d8_r8/test/build.gradle.kts
index c2f5a0b..cd93eb6 100644
--- a/d8_r8/test/build.gradle.kts
+++ b/d8_r8/test/build.gradle.kts
@@ -353,7 +353,7 @@
             "KEEP_ANNO_JAVAC_BUILD_DIR", keepAnnoCompileTask.getOutputs().getFiles().getAsPath())
     systemProperty("EXAMPLES_JAVA_11_JAVAC_BUILD_DIR",
             getRoot().resolveAll("build", "test", "examplesJava11", "classes"))
-    systemProperty("R8_RUNTIME_PATH", r8LibJar)
+    systemProperty("BUILD_PROP_R8_RUNTIME_PATH", r8LibJar)
     systemProperty("R8_DEPS", mainDepsJarTask.getSingleOutputFile())
     systemProperty("com.android.tools.r8.artprofilerewritingcompletenesscheck", "true")
 
diff --git a/d8_r8/test_modules/tests_bootstrap/build.gradle.kts b/d8_r8/test_modules/tests_bootstrap/build.gradle.kts
index f3dc100..0546ffa 100644
--- a/d8_r8/test_modules/tests_bootstrap/build.gradle.kts
+++ b/d8_r8/test_modules/tests_bootstrap/build.gradle.kts
@@ -81,7 +81,7 @@
                    layout.buildDirectory.dir("classes/java/test").get().toString())
     systemProperty("KEEP_ANNO_JAVAC_BUILD_DIR", keepAnnoCompileTask.outputs.files.getAsPath())
     systemProperty("R8_WITH_RELOCATED_DEPS", mainR8RelocatedTask.outputs.files.singleFile)
-    systemProperty("R8_RUNTIME_PATH", mainR8RelocatedTask.outputs.files.singleFile)
+    systemProperty("BUILD_PROP_R8_RUNTIME_PATH", mainR8RelocatedTask.outputs.files.singleFile)
   }
 
   val testJar by registering(Jar::class) {
diff --git a/d8_r8/test_modules/tests_java_8/build.gradle.kts b/d8_r8/test_modules/tests_java_8/build.gradle.kts
index 0d492cc..99e0219 100644
--- a/d8_r8/test_modules/tests_java_8/build.gradle.kts
+++ b/d8_r8/test_modules/tests_java_8/build.gradle.kts
@@ -137,10 +137,11 @@
     systemProperty("EXAMPLES_JAVA_11_JAVAC_BUILD_DIR",
                     getRoot().resolveAll("build", "test", "examplesJava11", "classes"))
     systemProperty(
-      "R8_RUNTIME_PATH",
+      "BUILD_PROP_R8_RUNTIME_PATH",
       mainCompileTask.outputs.files.getAsPath().split(File.pathSeparator)[0] +
         File.pathSeparator + mainDepsJarTask.outputs.files.singleFile +
         File.pathSeparator + getRoot().resolveAll("src", "main", "resources") +
+        File.pathSeparator + keepAnnoCompileTask.outputs.files.getAsPath().split(File.pathSeparator)[0] +
         File.pathSeparator + resourceShrinkerJavaCompileTask.outputs.files.getAsPath().split(File.pathSeparator)[0] +
         File.pathSeparator + resourceShrinkerKotlinCompileTask.outputs.files.getAsPath().split(File.pathSeparator)[1])
     systemProperty("R8_DEPS", mainDepsJarTask.outputs.files.singleFile)
@@ -161,6 +162,8 @@
     dependsOn(gradle.includedBuild("resourceshrinker").task(":jar"))
     from(testDependencies().map(::zipTree))
     from(resourceShrinkerDepsJarTask.outputs.getFiles().map(::zipTree))
+    from(keepAnnoJarTask.outputs.getFiles().map(::zipTree))
+    exclude("com/android/tools/r8/keepanno/annotations/**")
     duplicatesStrategy = DuplicatesStrategy.EXCLUDE
     archiveFileName.set("deps.jar")
   }
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReader.java b/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReader.java
index 85f651f..b76ac2e 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReader.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReader.java
@@ -89,6 +89,37 @@
 
   public static int ASM_VERSION = ASM9;
 
+  public static boolean isClassKeepAnnotation(String descriptor, boolean visible) {
+    return !visible && (isExtractedAnnotation(descriptor) || isEmbeddedAnnotation(descriptor));
+  }
+
+  public static boolean isFieldKeepAnnotation(String descriptor, boolean visible) {
+    return !visible && isEmbeddedAnnotation(descriptor);
+  }
+
+  public static boolean isMethodKeepAnnotation(String descriptor, boolean visible) {
+    return !visible && isEmbeddedAnnotation(descriptor);
+  }
+
+  private static boolean isExtractedAnnotation(String descriptor) {
+    return ExtractedAnnotations.DESCRIPTOR.equals(descriptor);
+  }
+
+  private static boolean isEmbeddedAnnotation(String descriptor) {
+    switch (descriptor) {
+      case AnnotationConstants.Edge.DESCRIPTOR:
+      case AnnotationConstants.UsesReflection.DESCRIPTOR:
+      case AnnotationConstants.ForApi.DESCRIPTOR:
+      case AnnotationConstants.UsedByReflection.DESCRIPTOR:
+      case AnnotationConstants.UsedByNative.DESCRIPTOR:
+      case AnnotationConstants.CheckRemoved.DESCRIPTOR:
+      case AnnotationConstants.CheckOptimizedOut.DESCRIPTOR:
+        return true;
+      default:
+        return false;
+    }
+  }
+
   public static List<KeepDeclaration> readKeepEdges(byte[] classFileBytes) {
     return internalReadKeepEdges(classFileBytes, true, false);
   }
@@ -107,6 +138,84 @@
     return declarations;
   }
 
+  public static AnnotationVisitor createClassKeepAnnotationVisitor(
+      String descriptor,
+      boolean visible,
+      boolean readEmbedded,
+      boolean readExtracted,
+      String className,
+      AnnotationParsingContext parsingContext,
+      Consumer<KeepDeclaration> callback) {
+    return KeepEdgeClassVisitor.createAnnotationVisitor(
+        descriptor,
+        visible,
+        readEmbedded,
+        readExtracted,
+        callback,
+        parsingContext,
+        className,
+        builder -> {
+          builder.setContextFromClassDescriptor(
+              KeepEdgeReaderUtils.getDescriptorFromClassTypeName(className));
+        });
+  }
+
+  public static AnnotationVisitor createFieldKeepAnnotationVisitor(
+      String descriptor,
+      boolean visible,
+      boolean readEmbedded,
+      boolean readExtracted,
+      String className,
+      String fieldName,
+      String fieldTypeDescriptor,
+      AnnotationParsingContext parsingContext,
+      Consumer<KeepDeclaration> callback) {
+    return KeepEdgeFieldVisitor.createAnnotationVisitor(
+        descriptor,
+        visible,
+        readEmbedded,
+        readExtracted,
+        callback::accept,
+        parsingContext,
+        className,
+        fieldName,
+        fieldTypeDescriptor,
+        builder -> {
+          builder.setContextFromFieldDescriptor(
+              KeepEdgeReaderUtils.getDescriptorFromClassTypeName(className),
+              fieldName,
+              fieldTypeDescriptor);
+        });
+  }
+
+  public static AnnotationVisitor createMethodKeepAnnotationVisitor(
+      String descriptor,
+      boolean visible,
+      boolean readEmbedded,
+      boolean readExtracted,
+      String className,
+      String methodName,
+      String methodDescriptor,
+      AnnotationParsingContext parsingContext,
+      Consumer<KeepDeclaration> callback) {
+    return KeepEdgeMethodVisitor.createAnnotationVisitor(
+        descriptor,
+        visible,
+        readEmbedded,
+        readExtracted,
+        callback::accept,
+        parsingContext,
+        className,
+        methodName,
+        methodDescriptor,
+        (KeepEdgeMetaInfo.Builder builder) -> {
+          builder.setContextFromMethodDescriptor(
+              KeepEdgeReaderUtils.getDescriptorFromClassTypeName(className),
+              methodName,
+              methodDescriptor);
+        });
+  }
+
   private static KeepClassItemReference classReferenceFromName(String className) {
     return KeepClassItemReference.fromClassNamePattern(
         KeepQualifiedClassNamePattern.exact(className));
@@ -223,7 +332,7 @@
         String[] interfaces) {
       super.visit(version, access, name, signature, superName, interfaces);
       className = binaryNameToTypeName(name);
-      parsingContext = new ClassParsingContext(className);
+      parsingContext = ClassParsingContext.fromName(className);
     }
 
     private AnnotationParsingContext annotationParsingContext(String descriptor) {
@@ -232,56 +341,62 @@
 
     @Override
     public AnnotationVisitor visitAnnotation(String descriptor, boolean visible) {
+      return createAnnotationVisitor(
+          descriptor,
+          visible,
+          readEmbedded,
+          readExtracted,
+          parent::accept,
+          annotationParsingContext(descriptor),
+          className,
+          this::setContext);
+    }
+
+    private static AnnotationVisitorBase createAnnotationVisitor(
+        String descriptor,
+        boolean visible,
+        boolean readEmbedded,
+        boolean readExtracted,
+        Consumer<KeepDeclaration> parent,
+        AnnotationParsingContext parsingContext,
+        String className,
+        Consumer<KeepEdgeMetaInfo.Builder> setContext) {
       // Skip any visible annotations as @KeepEdge is not runtime visible.
       if (visible) {
         return null;
       }
-      if (readExtracted && descriptor.equals(ExtractedAnnotations.DESCRIPTOR)) {
-        return new ExtractedAnnotationsVisitor(
-            annotationParsingContext(descriptor), parent::accept);
+
+      if (readExtracted && isExtractedAnnotation(descriptor)) {
+        return new ExtractedAnnotationsVisitor(parsingContext, parent::accept);
       }
-      if (!readEmbedded) {
+      if (!readEmbedded || !isEmbeddedAnnotation(descriptor)) {
         return null;
       }
       if (descriptor.equals(Edge.DESCRIPTOR)) {
-        return new KeepEdgeVisitor(
-            annotationParsingContext(descriptor), parent::accept, this::setContext);
+        return new KeepEdgeVisitor(parsingContext, parent::accept, setContext);
       }
       if (descriptor.equals(AnnotationConstants.UsesReflection.DESCRIPTOR)) {
         KeepClassItemPattern classItem =
             KeepClassItemPattern.builder()
                 .setClassNamePattern(KeepQualifiedClassNamePattern.exact(className))
                 .build();
-        return new UsesReflectionVisitor(
-            annotationParsingContext(descriptor), parent::accept, this::setContext, classItem);
+        return new UsesReflectionVisitor(parsingContext, parent::accept, setContext, classItem);
       }
-      if (descriptor.equals(AnnotationConstants.ForApi.DESCRIPTOR)) {
-        return new ForApiClassVisitor(
-            annotationParsingContext(descriptor), parent::accept, this::setContext, className);
+      if (descriptor.equals(ForApi.DESCRIPTOR)) {
+        return new ForApiClassVisitor(parsingContext, parent::accept, setContext, className);
       }
-      if (descriptor.equals(AnnotationConstants.UsedByReflection.DESCRIPTOR)
+      if (descriptor.equals(UsedByReflection.DESCRIPTOR)
           || descriptor.equals(AnnotationConstants.UsedByNative.DESCRIPTOR)) {
         return new UsedByReflectionClassVisitor(
-            annotationParsingContext(descriptor),
-            parent::accept,
-            this::setContext,
-            className);
+            parsingContext, parent::accept, setContext, className);
       }
       if (descriptor.equals(AnnotationConstants.CheckRemoved.DESCRIPTOR)) {
         return new CheckRemovedClassVisitor(
-            annotationParsingContext(descriptor),
-            parent::accept,
-            this::setContext,
-            className,
-            KeepCheckKind.REMOVED);
+            parsingContext, parent::accept, setContext, className, KeepCheckKind.REMOVED);
       }
       if (descriptor.equals(AnnotationConstants.CheckOptimizedOut.DESCRIPTOR)) {
         return new CheckRemovedClassVisitor(
-            annotationParsingContext(descriptor),
-            parent::accept,
-            this::setContext,
-            className,
-            KeepCheckKind.OPTIMIZED_OUT);
+            parsingContext, parent::accept, setContext, className, KeepCheckKind.OPTIMIZED_OUT);
       }
       return null;
     }
@@ -334,7 +449,8 @@
           new MethodParsingContext(classParsingContext, methodName, methodDescriptor);
     }
 
-    private KeepMemberItemPattern createMethodItemContext() {
+    private static KeepMemberItemPattern createMethodItemContext(
+        String className, String methodName, String methodDescriptor) {
       String returnTypeDescriptor = Type.getReturnType(methodDescriptor).getDescriptor();
       Type[] argumentTypes = Type.getArgumentTypes(methodDescriptor);
       KeepMethodParametersPattern.Builder builder = KeepMethodParametersPattern.builder();
@@ -363,50 +479,77 @@
 
     @Override
     public AnnotationVisitor visitAnnotation(String descriptor, boolean visible) {
+      return createAnnotationVisitor(
+          descriptor,
+          visible,
+          true,
+          false,
+          parent::accept,
+          annotationParsingContext(descriptor),
+          className,
+          methodName,
+          methodDescriptor,
+          this::setContext);
+    }
+
+    public static AnnotationVisitor createAnnotationVisitor(
+        String descriptor,
+        boolean visible,
+        boolean readEmbedded,
+        boolean readExtracted,
+        Consumer<KeepDeclaration> parent,
+        AnnotationParsingContext parsingContext,
+        String className,
+        String methodName,
+        String methodDescriptor,
+        Consumer<KeepEdgeMetaInfo.Builder> setContext) {
       // Skip any visible annotations as @KeepEdge is not runtime visible.
       if (visible) {
         return null;
       }
+      if (!readEmbedded) {
+        // Only the embedded annotations can be on methods.
+        return null;
+      }
       if (descriptor.equals(Edge.DESCRIPTOR)) {
-        return new KeepEdgeVisitor(
-            annotationParsingContext(descriptor), parent::accept, this::setContext);
+        return new KeepEdgeVisitor(parsingContext, parent::accept, setContext);
       }
       if (descriptor.equals(AnnotationConstants.UsesReflection.DESCRIPTOR)) {
         return new UsesReflectionVisitor(
-            annotationParsingContext(descriptor),
+            parsingContext,
             parent::accept,
-            this::setContext,
-            createMethodItemContext());
+            setContext,
+            createMethodItemContext(className, methodName, methodDescriptor));
       }
       if (descriptor.equals(AnnotationConstants.ForApi.DESCRIPTOR)) {
         return new ForApiMemberVisitor(
-            annotationParsingContext(descriptor),
+            parsingContext,
             parent::accept,
-            this::setContext,
-            createMethodItemContext());
+            setContext,
+            createMethodItemContext(className, methodName, methodDescriptor));
       }
       if (descriptor.equals(AnnotationConstants.UsedByReflection.DESCRIPTOR)
           || descriptor.equals(AnnotationConstants.UsedByNative.DESCRIPTOR)) {
         return new UsedByReflectionMemberVisitor(
-            annotationParsingContext(descriptor),
+            parsingContext,
             parent::accept,
-            this::setContext,
-            createMethodItemContext());
+            setContext,
+            createMethodItemContext(className, methodName, methodDescriptor));
       }
       if (descriptor.equals(AnnotationConstants.CheckRemoved.DESCRIPTOR)) {
         return new CheckRemovedMemberVisitor(
-            annotationParsingContext(descriptor),
+            parsingContext,
             parent::accept,
-            this::setContext,
-            createMethodItemContext(),
+            setContext,
+            createMethodItemContext(className, methodName, methodDescriptor),
             KeepCheckKind.REMOVED);
       }
       if (descriptor.equals(AnnotationConstants.CheckOptimizedOut.DESCRIPTOR)) {
         return new CheckRemovedMemberVisitor(
-            annotationParsingContext(descriptor),
+            parsingContext,
             parent::accept,
-            this::setContext,
-            createMethodItemContext(),
+            setContext,
+            createMethodItemContext(className, methodName, methodDescriptor),
             KeepCheckKind.OPTIMIZED_OUT);
       }
       return null;
@@ -422,7 +565,7 @@
     private final Parent<KeepEdge> parent;
     private final String className;
     private final String fieldName;
-    private final String fieldDescriptor;
+    private final String fieldTypeDescriptor;
     private final FieldParsingContext parsingContext;
 
     KeepEdgeFieldVisitor(
@@ -430,23 +573,24 @@
         Parent<KeepEdge> parent,
         String className,
         String fieldName,
-        String fieldDescriptor) {
+        String fieldTypeDescriptor) {
       super(ASM_VERSION);
       this.parent = parent;
       this.className = className;
       this.fieldName = fieldName;
-      this.fieldDescriptor = fieldDescriptor;
+      this.fieldTypeDescriptor = fieldTypeDescriptor;
       this.parsingContext =
-          new FieldParsingContext(classParsingContext, fieldName, fieldDescriptor);
+          new FieldParsingContext(classParsingContext, fieldName, fieldTypeDescriptor);
     }
 
     private AnnotationParsingContext annotationParsingContext(String descriptor) {
       return parsingContext.annotation(descriptor);
     }
 
-    private KeepMemberItemPattern createMemberItemContext() {
+    private static KeepMemberItemPattern createMemberItemContext(
+        String className, String fieldName, String fieldTypeDescriptor) {
       KeepFieldTypePattern typePattern =
-          KeepFieldTypePattern.fromType(KeepTypePattern.fromDescriptor(fieldDescriptor));
+          KeepFieldTypePattern.fromType(KeepTypePattern.fromDescriptor(fieldTypeDescriptor));
       return KeepMemberItemPattern.builder()
           .setClassReference(classReferenceFromName(className))
           .setMemberPattern(
@@ -459,39 +603,67 @@
 
     private void setContext(KeepEdgeMetaInfo.Builder builder) {
       builder.setContextFromFieldDescriptor(
-          KeepEdgeReaderUtils.getDescriptorFromJavaType(className), fieldName, fieldDescriptor);
+          KeepEdgeReaderUtils.getDescriptorFromJavaType(className), fieldName, fieldTypeDescriptor);
     }
 
     @Override
     public AnnotationVisitor visitAnnotation(String descriptor, boolean visible) {
+      return createAnnotationVisitor(
+          descriptor,
+          visible,
+          true,
+          false,
+          parent::accept,
+          annotationParsingContext(descriptor),
+          className,
+          fieldName,
+          fieldTypeDescriptor,
+          this::setContext);
+    }
+
+    public static AnnotationVisitor createAnnotationVisitor(
+        String descriptor,
+        boolean visible,
+        boolean readEmbedded,
+        boolean readExtracted,
+        Consumer<KeepEdge> parent,
+        AnnotationParsingContext parsingContext,
+        String className,
+        String fieldName,
+        String fieldTypeDescriptor,
+        Consumer<KeepEdgeMetaInfo.Builder> setContext) {
       // Skip any visible annotations as @KeepEdge is not runtime visible.
       if (visible) {
         return null;
       }
+      if (!readEmbedded) {
+        // Only the embedded annotations can be on fields.
+        return null;
+      }
       if (descriptor.equals(Edge.DESCRIPTOR)) {
-        return new KeepEdgeVisitor(annotationParsingContext(descriptor), parent, this::setContext);
+        return new KeepEdgeVisitor(parsingContext, parent::accept, setContext);
       }
       if (descriptor.equals(AnnotationConstants.UsesReflection.DESCRIPTOR)) {
         return new UsesReflectionVisitor(
-            annotationParsingContext(descriptor),
-            parent,
-            this::setContext,
-            createMemberItemContext());
+            parsingContext,
+            parent::accept,
+            setContext,
+            createMemberItemContext(className, fieldName, fieldTypeDescriptor));
       }
-      if (descriptor.equals(AnnotationConstants.ForApi.DESCRIPTOR)) {
+      if (descriptor.equals(ForApi.DESCRIPTOR)) {
         return new ForApiMemberVisitor(
-            annotationParsingContext(descriptor),
-            parent,
-            this::setContext,
-            createMemberItemContext());
+            parsingContext,
+            parent::accept,
+            setContext,
+            createMemberItemContext(className, fieldName, fieldTypeDescriptor));
       }
-      if (descriptor.equals(AnnotationConstants.UsedByReflection.DESCRIPTOR)
+      if (descriptor.equals(UsedByReflection.DESCRIPTOR)
           || descriptor.equals(AnnotationConstants.UsedByNative.DESCRIPTOR)) {
         return new UsedByReflectionMemberVisitor(
-            annotationParsingContext(descriptor),
-            parent,
-            this::setContext,
-            createMemberItemContext());
+            parsingContext,
+            parent::accept,
+            setContext,
+            createMemberItemContext(className, fieldName, fieldTypeDescriptor));
       }
       return null;
     }
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReaderUtils.java b/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReaderUtils.java
index 21645d5..78eddd6 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReaderUtils.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReaderUtils.java
@@ -20,7 +20,11 @@
   }
 
   public static String getDescriptorFromClassTypeName(String classTypeName) {
-    return "L" + getBinaryNameFromClassTypeName(classTypeName) + ";";
+    return getDescriptorFromBinaryName(getBinaryNameFromClassTypeName(classTypeName));
+  }
+
+  public static String getDescriptorFromBinaryName(String binaryName) {
+    return "L" + binaryName + ";";
   }
 
   public static String getJavaTypeFromDescriptor(String descriptor) {
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassItemReference.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassItemReference.java
index 5a3c7d5..34a97b6 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassItemReference.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassItemReference.java
@@ -5,6 +5,8 @@
 
 import java.util.Collection;
 import java.util.Collections;
+import java.util.function.Consumer;
+import java.util.function.Function;
 
 public abstract class KeepClassItemReference extends KeepItemReference {
 
@@ -28,6 +30,19 @@
     return this;
   }
 
+  public final <T> T applyClassItemReference(
+      Function<KeepBindingReference, T> onBinding, Function<KeepClassItemPattern, T> onPattern) {
+    if (isBindingReference()) {
+      return onBinding.apply(asBindingReference());
+    }
+    return onPattern.apply(asClassItemPattern());
+  }
+
+  public final void matchClassItemReference(
+      Consumer<KeepBindingReference> onBinding, Consumer<KeepClassItemPattern> onPattern) {
+    applyClassItemReference(AstUtils.toVoidFunction(onBinding), AstUtils.toVoidFunction(onPattern));
+  }
+
   public abstract Collection<KeepBindingReference> getBindingReferences();
 
   private static class ClassBinding extends KeepClassItemReference {
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepConstraint.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepConstraint.java
index 24ec53d..5368d5e 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepConstraint.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepConstraint.java
@@ -25,6 +25,8 @@
     return System.identityHashCode(this);
   }
 
+  public abstract void accept(KeepConstraintVisitor visitor);
+
   public abstract String getEnumValue();
 
   public KeepAnnotationPattern asAnnotationPattern() {
@@ -77,6 +79,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onLookup(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       builder.add(KeepOption.SHRINKING);
     }
@@ -98,6 +105,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onName(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       builder.add(KeepOption.OBFUSCATING);
     }
@@ -119,6 +131,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onVisibilityRelax(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       // The compiler currently satisfies that access is never restricted.
     }
@@ -140,6 +157,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onVisibilityRestrict(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       // We don't have directional rules so this prohibits any modification.
       builder.add(KeepOption.ACCESS_MODIFICATION);
@@ -162,6 +184,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onNeverInline(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       builder.add(KeepOption.OPTIMIZING);
     }
@@ -188,6 +215,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onClassInstantiate(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       builder.add(KeepOption.OPTIMIZING);
     }
@@ -214,6 +246,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onClassOpenHierarchy(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       builder.add(KeepOption.OPTIMIZING);
     }
@@ -240,6 +277,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onMethodInvoke(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       builder.add(KeepOption.OPTIMIZING);
     }
@@ -266,6 +308,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onMethodReplace(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       builder.add(KeepOption.OPTIMIZING);
     }
@@ -292,6 +339,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onFieldGet(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       builder.add(KeepOption.OPTIMIZING);
     }
@@ -318,6 +370,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onFieldSet(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       builder.add(KeepOption.OPTIMIZING);
     }
@@ -344,6 +401,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onFieldReplace(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       builder.add(KeepOption.OPTIMIZING);
     }
@@ -403,6 +465,11 @@
     }
 
     @Override
+    public void accept(KeepConstraintVisitor visitor) {
+      visitor.onAnnotation(this);
+    }
+
+    @Override
     public void convertToDisallowKeepOptions(KeepOptions.Builder builder) {
       // The annotation constraint only implies that annotations should remain, no restrictions
       // are on the item otherwise. Also, we can't restrict the rule to just the annotations being
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepConstraintVisitor.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepConstraintVisitor.java
new file mode 100644
index 0000000..f7db601
--- /dev/null
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepConstraintVisitor.java
@@ -0,0 +1,48 @@
+// Copyright (c) 2024, 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.keepanno.ast;
+
+import com.android.tools.r8.keepanno.ast.KeepConstraint.Annotation;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.ClassInstantiate;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.ClassOpenHierarchy;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.FieldGet;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.FieldReplace;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.FieldSet;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.Lookup;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.MethodInvoke;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.MethodReplace;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.Name;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.NeverInline;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.VisibilityRelax;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.VisibilityRestrict;
+
+public abstract class KeepConstraintVisitor {
+
+  public abstract void onLookup(Lookup constraint);
+
+  public abstract void onName(Name constraint);
+
+  public abstract void onVisibilityRelax(VisibilityRelax constraint);
+
+  public abstract void onVisibilityRestrict(VisibilityRestrict constraint);
+
+  public abstract void onNeverInline(NeverInline constraint);
+
+  public abstract void onClassInstantiate(ClassInstantiate constraint);
+
+  public abstract void onClassOpenHierarchy(ClassOpenHierarchy constraint);
+
+  public abstract void onMethodInvoke(MethodInvoke constraint);
+
+  public abstract void onMethodReplace(MethodReplace constraint);
+
+  public abstract void onFieldGet(FieldGet constraint);
+
+  public abstract void onFieldSet(FieldSet constraint);
+
+  public abstract void onFieldReplace(FieldReplace constraint);
+
+  public abstract void onAnnotation(Annotation constraint);
+}
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepConstraints.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepConstraints.java
index 746d22a..12f10b0 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepConstraints.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepConstraints.java
@@ -33,6 +33,10 @@
     return new Builder();
   }
 
+  public void forEachAccept(KeepConstraintVisitor visitor) {
+    getConstraints().forEach(c -> c.accept(visitor));
+  }
+
   public static class Builder {
 
     private boolean defaultAdditions = false;
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/ParsingContext.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/ParsingContext.java
index 5f6bb55..11eefa5 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/ParsingContext.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/ParsingContext.java
@@ -6,6 +6,7 @@
 
 import static com.android.tools.r8.keepanno.asm.KeepEdgeReaderUtils.getJavaTypeFromDescriptor;
 
+import com.android.tools.r8.keepanno.asm.KeepEdgeReaderUtils;
 import org.objectweb.asm.Type;
 
 public abstract class ParsingContext {
@@ -62,10 +63,19 @@
   public static class ClassParsingContext extends ParsingContext {
     private final String className;
 
-    public ClassParsingContext(String className) {
+    private ClassParsingContext(String className) {
       this.className = className;
     }
 
+    public static ClassParsingContext fromName(String className) {
+      return new ClassParsingContext(className);
+    }
+
+    public static ClassParsingContext fromDescriptor(String descriptor) {
+      return ClassParsingContext.fromName(
+          KeepEdgeReaderUtils.getJavaTypeFromDescriptor(descriptor));
+    }
+
     @Override
     public String getHolderName() {
       return className;
diff --git a/src/main/java/com/android/tools/r8/R8Command.java b/src/main/java/com/android/tools/r8/R8Command.java
index ca3f045..7597634 100644
--- a/src/main/java/com/android/tools/r8/R8Command.java
+++ b/src/main/java/com/android/tools/r8/R8Command.java
@@ -507,7 +507,7 @@
     }
 
     @Deprecated
-    public Builder setEnableExperimentalVersionedKeepEdgeAnnotations(boolean enable) {
+    public Builder setEnableExperimentalExtractedKeepAnnotations(boolean enable) {
       this.enableExperimentalVersionedKeepEdgeAnnotations = enable;
       return self();
     }
diff --git a/src/main/java/com/android/tools/r8/graph/DexType.java b/src/main/java/com/android/tools/r8/graph/DexType.java
index 4809783..f597df0 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -303,6 +303,11 @@
     return DescriptorUtils.isPrimitiveType(descriptor.getFirstByteAsChar());
   }
 
+  public char asPrimitiveTypeDescriptorChar() {
+    assert isPrimitiveType();
+    return descriptor.getFirstByteAsChar();
+  }
+
   public boolean isVoidType() {
     return descriptor.getFirstByteAsChar() == 'V';
   }
@@ -496,12 +501,25 @@
     return dexItemFactory.createType(descriptor.toArrayDescriptor(dimensions, dexItemFactory));
   }
 
+  public int getArrayTypeDimensions() {
+    for (int i = 0; i < descriptor.content.length; i++) {
+      if (descriptor.content[i] != '[') {
+        return i;
+      }
+    }
+    return 0;
+  }
+
   public DexType toArrayElementType(DexItemFactory dexItemFactory) {
-    assert isArrayType();
+    return toArrayElementAfterDimension(1, dexItemFactory);
+  }
+
+  public DexType toArrayElementAfterDimension(int dimension, DexItemFactory dexItemFactory) {
+    assert getArrayTypeDimensions() >= dimension;
     DexString newDesc =
         dexItemFactory.createString(
-            descriptor.size - 1,
-            Arrays.copyOfRange(descriptor.content, 1, descriptor.content.length));
+            descriptor.size - dimension,
+            Arrays.copyOfRange(descriptor.content, dimension, descriptor.content.length));
     return dexItemFactory.createType(newDesc);
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java b/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java
index 978932d..089194a 100644
--- a/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java
+++ b/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java
@@ -35,9 +35,11 @@
 import com.android.tools.r8.graph.GenericSignature.FieldTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
 import com.android.tools.r8.jar.CfApplicationWriter;
-import com.android.tools.r8.keepanno.asm.KeepEdgeReader.ExtractedAnnotationsVisitor;
-import com.android.tools.r8.keepanno.ast.AnnotationConstants.ExtractedAnnotations;
+import com.android.tools.r8.keepanno.asm.KeepEdgeReader;
+import com.android.tools.r8.keepanno.ast.ParsingContext.AnnotationParsingContext;
 import com.android.tools.r8.keepanno.ast.ParsingContext.ClassParsingContext;
+import com.android.tools.r8.keepanno.ast.ParsingContext.FieldParsingContext;
+import com.android.tools.r8.keepanno.ast.ParsingContext.MethodParsingContext;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.synthesis.SyntheticMarker;
 import com.android.tools.r8.utils.AsmUtils;
@@ -453,17 +455,24 @@
       return new CreateMethodVisitor(access, name, desc, signature, exceptions, this);
     }
 
+    public boolean shouldReadKeepAnnotations() {
+      // Only compilers configured to read annotations should process them.
+      // In all other instances (D8, relocater, etc.) they must be pass-through.
+      return application.options.testing.isKeepAnnotationsEnabled()
+          && classKind == ClassKind.PROGRAM;
+    }
+
     @Override
     public AnnotationVisitor visitAnnotation(String desc, boolean visible) {
-      if (!visible && ExtractedAnnotations.DESCRIPTOR.equals(desc)) {
-        if (!application.options.testing.enableExtractedKeepAnnotations) {
-          return null;
-        }
-        if (classKind != ClassKind.PROGRAM) {
-          return null;
-        }
-        return new ExtractedAnnotationsVisitor(
-            new ClassParsingContext(type.getName()).annotation(desc),
+      if (shouldReadKeepAnnotations() && KeepEdgeReader.isClassKeepAnnotation(desc, visible)) {
+        String className = type.getTypeName();
+        return KeepEdgeReader.createClassKeepAnnotationVisitor(
+            desc,
+            visible,
+            application.options.testing.enableEmbeddedKeepAnnotations,
+            application.options.testing.enableExtractedKeepAnnotations,
+            className,
+            ClassParsingContext.fromName(className).annotation(desc),
             application::addKeepDeclaration);
       }
       return createAnnotationVisitor(
@@ -660,7 +669,7 @@
     private final CreateDexClassVisitor<?> parent;
     private final int access;
     private final String name;
-    private final String desc;
+    private final String fieldTypeDescriptor;
     private final Object value;
     private final FieldTypeSignature fieldSignature;
     private List<DexAnnotation> annotations = null;
@@ -676,7 +685,7 @@
       this.parent = parent;
       this.access = access;
       this.name = name;
-      this.desc = desc;
+      this.fieldTypeDescriptor = desc;
       this.value = value;
       this.fieldSignature =
           parent.application.options.parseSignatureAttribute()
@@ -691,6 +700,24 @@
 
     @Override
     public AnnotationVisitor visitAnnotation(String desc, boolean visible) {
+      if (parent.shouldReadKeepAnnotations()
+          && KeepEdgeReader.isFieldKeepAnnotation(desc, visible)) {
+        String className = parent.type.getTypeName();
+        AnnotationParsingContext parsingContext =
+            new FieldParsingContext(
+                    ClassParsingContext.fromName(className), name, fieldTypeDescriptor)
+                .annotation(desc);
+        return KeepEdgeReader.createFieldKeepAnnotationVisitor(
+            desc,
+            visible,
+            parent.application.options.testing.enableEmbeddedKeepAnnotations,
+            parent.application.options.testing.enableExtractedKeepAnnotations,
+            className,
+            name,
+            fieldTypeDescriptor,
+            parsingContext,
+            parent.application::addKeepDeclaration);
+      }
       return createAnnotationVisitor(
           desc, visible, getAnnotations(), parent.application, DexAnnotation::new);
     }
@@ -705,7 +732,7 @@
     @Override
     public void visitEnd() {
       FieldAccessFlags flags = createFieldAccessFlags(access);
-      DexField dexField = parent.application.getField(parent.type, name, desc);
+      DexField dexField = parent.application.getField(parent.type, name, fieldTypeDescriptor);
       parent.application.checkFieldForRecord(dexField, parent.classKind);
       parent.application.checkFieldForMethodHandlesLookup(dexField, parent.classKind);
       parent.application.checkFieldForVarHandle(dexField, parent.classKind);
@@ -785,6 +812,7 @@
   private static class CreateMethodVisitor extends MethodVisitor {
 
     private final String name;
+    private final String methodDescriptor;
     final CreateDexClassVisitor<?> parent;
     private final int parameterCount;
     private List<DexAnnotation> annotations = null;
@@ -808,6 +836,7 @@
         CreateDexClassVisitor<?> parent) {
       super(ASM_VERSION);
       this.name = name;
+      this.methodDescriptor = desc;
       this.parent = parent;
       this.method = parent.application.getMethod(parent.type, name, desc);
       this.flags = createMethodAccessFlags(name, access);
@@ -834,6 +863,24 @@
 
     @Override
     public AnnotationVisitor visitAnnotation(String desc, boolean visible) {
+      if (parent.shouldReadKeepAnnotations()
+          && KeepEdgeReader.isMethodKeepAnnotation(desc, visible)) {
+        String className = parent.type.getTypeName();
+        AnnotationParsingContext parsingContext =
+            new MethodParsingContext(
+                    ClassParsingContext.fromName(className), name, methodDescriptor)
+                .annotation(desc);
+        return KeepEdgeReader.createMethodKeepAnnotationVisitor(
+            desc,
+            visible,
+            parent.application.options.testing.enableEmbeddedKeepAnnotations,
+            parent.application.options.testing.enableExtractedKeepAnnotations,
+            className,
+            name,
+            methodDescriptor,
+            parsingContext,
+            parent.application::addKeepDeclaration);
+      }
       return createAnnotationVisitor(
           desc, visible, getAnnotations(), parent.application, DexAnnotation::new);
     }
diff --git a/src/main/java/com/android/tools/r8/graph/UseRegistry.java b/src/main/java/com/android/tools/r8/graph/UseRegistry.java
index d7d1b0b..6238dd5 100644
--- a/src/main/java/com/android/tools/r8/graph/UseRegistry.java
+++ b/src/main/java/com/android/tools/r8/graph/UseRegistry.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.bytecodemetadata.BytecodeInstructionMetadata;
 import com.android.tools.r8.graph.lens.GraphLens;
 import com.android.tools.r8.ir.code.InvokeType;
+import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.utils.TraversalContinuation;
 import java.util.ListIterator;
 
@@ -60,6 +61,10 @@
     return continuation;
   }
 
+  public void registerInliningPosition(Position position) {
+    assert position.hasCallerPosition();
+  }
+
   public void registerRecordFieldValues(DexField[] fields) {
     registerTypeReference(appView.dexItemFactory().objectArrayType);
   }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
index 849e67a..2721861 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
@@ -17,8 +17,10 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
+import com.android.tools.r8.graph.MethodAccessInfoCollection;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.graph.PrunedItems;
+import com.android.tools.r8.horizontalclassmerging.VirtualMethodMerger.SuperMethodReference;
 import com.android.tools.r8.horizontalclassmerging.code.SyntheticInitializerConverter;
 import com.android.tools.r8.ir.conversion.LirConverter;
 import com.android.tools.r8.ir.conversion.MethodConversionOptions;
@@ -35,6 +37,7 @@
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.TraversalContinuation;
+import com.android.tools.r8.utils.collections.ProgramMethodMap;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.LinkedList;
@@ -196,13 +199,14 @@
     appView.setGraphLens(horizontalClassMergerGraphLens);
     codeProvider.setGraphLens(horizontalClassMergerGraphLens);
 
-    // Finalize synthetic code.
-    transformIncompleteCode(groups, horizontalClassMergerGraphLens, executorService);
-
     // Must rewrite AppInfoWithLiveness before pruning the merged classes, to ensure that allocation
     // sites, fields accesses, etc. are correctly transferred to the target classes.
     DexApplication newApplication = getNewApplication(mergedClasses);
     if (appView.enableWholeProgramOptimizations()) {
+      ProgramMethodMap<DexMethod> newNonReboundMethodReferences =
+          extractNonReboundMethodReferences(groups, horizontalClassMergerGraphLens);
+      // Finalize synthetic code.
+      transformIncompleteCode(groups, horizontalClassMergerGraphLens, executorService);
       // Prune keep info.
       AppView<AppInfoWithClassHierarchy> appViewWithClassHierarchy = appView.withClassHierarchy();
       KeepInfoCollection keepInfo = appView.getKeepInfo();
@@ -225,6 +229,8 @@
         }
         appView.clearCodeRewritings(executorService, timing);
       }
+      amendMethodAccessInfoCollection(
+          horizontalClassMergerGraphLens, newNonReboundMethodReferences);
     } else {
       assert mode.isFinal();
       SyntheticItems syntheticItems = appView.appInfo().getSyntheticItems();
@@ -288,6 +294,40 @@
             });
   }
 
+  private ProgramMethodMap<DexMethod> extractNonReboundMethodReferences(
+      Collection<HorizontalMergeGroup> groups, HorizontalClassMergerGraphLens lens) {
+    ProgramMethodMap<DexMethod> newNonReboundMethodReferences = ProgramMethodMap.create();
+    for (HorizontalMergeGroup group : groups) {
+      group
+          .getTarget()
+          .forEachProgramVirtualMethodMatching(
+              method ->
+                  method.hasCode()
+                      && method.getCode() instanceof IncompleteVirtuallyMergedMethodCode
+                      && ((IncompleteVirtuallyMergedMethodCode) method.getCode()).hasSuperMethod(),
+              method -> {
+                SuperMethodReference superMethodReference =
+                    ((IncompleteVirtuallyMergedMethodCode) method.getDefinition().getCode())
+                        .getSuperMethod();
+                newNonReboundMethodReferences.put(
+                    method, superMethodReference.getRewrittenReference(lens, method));
+              });
+    }
+    return newNonReboundMethodReferences;
+  }
+
+  private void amendMethodAccessInfoCollection(
+      HorizontalClassMergerGraphLens lens,
+      ProgramMethodMap<DexMethod> newNonReboundMethodReferences) {
+    MethodAccessInfoCollection.Modifier methodAccessInfoCollectionModifier =
+        appView.appInfoWithLiveness().getMethodAccessInfoCollection().modifier();
+    newNonReboundMethodReferences.forEach(
+        (context, reference) ->
+            // Reference is already lens rewritten.
+            methodAccessInfoCollectionModifier.registerInvokeSuperInContext(
+                reference, context.rewrittenWithLens(lens, lens.getPrevious(), appView)));
+  }
+
   private FieldAccessInfoCollectionModifier createFieldAccessInfoCollectionModifier(
       Collection<HorizontalMergeGroup> groups) {
     FieldAccessInfoCollectionModifier.Builder builder =
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/IncompleteVirtuallyMergedMethodCode.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/IncompleteVirtuallyMergedMethodCode.java
index e39290c..4b44559 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/IncompleteVirtuallyMergedMethodCode.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/IncompleteVirtuallyMergedMethodCode.java
@@ -146,12 +146,7 @@
       fallthroughTarget =
           lens.getNextMethodSignature(mappedMethods.get(mappedMethods.lastIntKey()));
     } else {
-      DexMethod reboundFallthroughTarget =
-          lens.lookupInvokeSuper(superMethod.getReboundReference(), method).getReference();
-      fallthroughTarget =
-          reboundFallthroughTarget.withHolder(
-              lens.getNextClassType(superMethod.getReference().getHolderType()),
-              appView.dexItemFactory());
+      fallthroughTarget = superMethod.getRewrittenReference(lens, method);
     }
     instructions.add(
         new CfInvoke(Opcodes.INVOKESPECIAL, fallthroughTarget, method.getHolder().isInterface()));
@@ -166,6 +161,14 @@
         lens, originalMethod.getHolderType(), maxStack, maxLocals, instructions);
   }
 
+  public boolean hasSuperMethod() {
+    return superMethod != null;
+  }
+
+  public SuperMethodReference getSuperMethod() {
+    return superMethod;
+  }
+
   @Override
   public LirCode<Integer> toLirCode(
       AppView<? extends AppInfoWithClassHierarchy> appView,
@@ -213,7 +216,7 @@
 
     // Emit switch.
     IntBidirectionalIterator classIdIterator = mappedMethods.keySet().iterator();
-    int[] keys = new int[mappedMethods.size() - BooleanUtils.intValue(superMethod == null)];
+    int[] keys = new int[mappedMethods.size() - BooleanUtils.intValue(!hasSuperMethod())];
     int[] targets = new int[keys.length];
     int nextTarget = instructionIndex - argumentValues.size() + 3;
     for (int i = 0; i < keys.length; i++) {
@@ -225,7 +228,10 @@
     instructionIndex++;
 
     // Emit switch fallthrough.
-    if (superMethod == null) {
+    if (hasSuperMethod()) {
+      lirBuilder.addInvokeSuper(
+          superMethod.getRewrittenReference(lens, method), argumentValues, false);
+    } else {
       DexMethod fallthroughTarget =
           lens.getNextMethodSignature(mappedMethods.get(mappedMethods.lastIntKey()));
       if (method.getHolder().isInterface()) {
@@ -233,14 +239,6 @@
       } else {
         lirBuilder.addInvokeVirtual(fallthroughTarget, argumentValues);
       }
-    } else {
-      DexMethod reboundFallthroughTarget =
-          lens.lookupInvokeSuper(superMethod.getReboundReference(), method).getReference();
-      DexMethod fallthroughTarget =
-          reboundFallthroughTarget.withHolder(
-              lens.getNextClassType(superMethod.getReference().getHolderType()),
-              appView.dexItemFactory());
-      lirBuilder.addInvokeSuper(fallthroughTarget, argumentValues, false);
     }
     if (method.getReturnType().isVoidType()) {
       lirBuilder.addReturnVoid();
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java
index 6175c5a..e166410 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java
@@ -38,12 +38,12 @@
       this.reboundReference = reboundReference;
     }
 
-    public DexMethod getReference() {
-      return reference;
-    }
-
-    public DexMethod getReboundReference() {
-      return reboundReference;
+    public DexMethod getRewrittenReference(
+        HorizontalClassMergerGraphLens lens, ProgramMethod context) {
+      DexMethod reboundFallthroughTarget =
+          lens.lookupInvokeSuper(reboundReference, context).getReference();
+      return reboundFallthroughTarget.withHolder(
+          lens.getNextClassType(reference.getHolderType()), lens.dexItemFactory());
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/lightir/LirCode.java b/src/main/java/com/android/tools/r8/lightir/LirCode.java
index 6f93b21..a4400f4 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirCode.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirCode.java
@@ -77,6 +77,8 @@
 
     public abstract Position getPosition(DexMethod method, boolean isD8R8Synthesized);
 
+    public abstract boolean hasCallerPosition();
+
     abstract int getOrder();
 
     abstract int internalAcceptCompareTo(PositionEntry other, CompareToVisitor visitor);
@@ -122,6 +124,11 @@
     }
 
     @Override
+    public boolean hasCallerPosition() {
+      return false;
+    }
+
+    @Override
     public Position getPosition(DexMethod method, boolean isD8R8Synthesized) {
       return (isD8R8Synthesized ? SyntheticPosition.builder() : SourcePosition.builder())
           .setMethod(method)
@@ -155,6 +162,11 @@
     }
 
     @Override
+    public boolean hasCallerPosition() {
+      return position.hasCallerPosition();
+    }
+
+    @Override
     public Position getPosition(DexMethod method, boolean isD8R8Synthesized) {
       return position;
     }
@@ -585,6 +597,13 @@
   @Override
   public void registerCodeReferences(ProgramMethod method, UseRegistry registry) {
     assert registry.getTraversalContinuation().shouldContinue();
+    for (PositionEntry positionEntry : positionTable) {
+      if (positionEntry.hasCallerPosition()) {
+        registry.registerInliningPosition(
+            positionEntry.getPosition(
+                method.getReference(), method.getDefinition().isD8R8Synthesized()));
+      }
+    }
     LirUseRegistryCallback<EV> registryCallbacks = new LirUseRegistryCallback<>(this, registry);
     for (LirInstructionView view : this) {
       if (metadataMap != null) {
diff --git a/src/main/java/com/android/tools/r8/shaking/DefaultEnqueuerUseRegistry.java b/src/main/java/com/android/tools/r8/shaking/DefaultEnqueuerUseRegistry.java
index 736f285..dd975f7 100644
--- a/src/main/java/com/android/tools/r8/shaking/DefaultEnqueuerUseRegistry.java
+++ b/src/main/java/com/android/tools/r8/shaking/DefaultEnqueuerUseRegistry.java
@@ -19,6 +19,7 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.code.Position;
 import java.util.ListIterator;
 
 public class DefaultEnqueuerUseRegistry extends ComputeApiLevelUseRegistry {
@@ -45,6 +46,12 @@
   }
 
   @Override
+  public void registerInliningPosition(Position position) {
+    super.registerInliningPosition(position);
+    enqueuer.traceMethodPosition(position, getContext());
+  }
+
+  @Override
   public void registerInitClass(DexType clazz) {
     super.registerInitClass(clazz);
     enqueuer.traceInitClass(clazz, getContext());
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 0dfda11..eee85a1 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -25,7 +25,6 @@
 import com.android.tools.r8.dex.IndexedItemCollection;
 import com.android.tools.r8.dex.code.CfOrDexInstruction;
 import com.android.tools.r8.errors.InterfaceDesugarMissingTypeDiagnostic;
-import com.android.tools.r8.errors.Unimplemented;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.experimental.graphinfo.GraphConsumer;
 import com.android.tools.r8.features.IsolatedFeatureSplitsChecker;
@@ -131,7 +130,6 @@
 import com.android.tools.r8.naming.identifiernamestring.IdentifierNameStringLookupResult;
 import com.android.tools.r8.naming.identifiernamestring.IdentifierNameStringTypeLookupResult;
 import com.android.tools.r8.origin.Origin;
-import com.android.tools.r8.position.Position;
 import com.android.tools.r8.profile.rewriting.ProfileCollectionAdditions;
 import com.android.tools.r8.shaking.AnnotationMatchResult.MatchedAnnotation;
 import com.android.tools.r8.shaking.DelayedRootSetActionItem.InterfaceMethodSyntheticBridgeAction;
@@ -154,6 +152,8 @@
 import com.android.tools.r8.shaking.RootSetUtils.RootSetBase;
 import com.android.tools.r8.shaking.RootSetUtils.RootSetBuilder;
 import com.android.tools.r8.shaking.ScopedDexMethodSet.AddMethodIfMoreVisibleResult;
+import com.android.tools.r8.shaking.rules.ApplicableRulesEvaluator;
+import com.android.tools.r8.shaking.rules.KeepAnnotationMatcher;
 import com.android.tools.r8.synthesis.SyntheticItems.SynthesizingContextOracle;
 import com.android.tools.r8.utils.Action;
 import com.android.tools.r8.utils.Box;
@@ -291,6 +291,7 @@
   private final Set<DexMember<?, ?>> identifierNameStrings = Sets.newIdentityHashSet();
 
   private List<KeepDeclaration> keepDeclarations = Collections.emptyList();
+  private ApplicableRulesEvaluator applicableRules = ApplicableRulesEvaluator.empty();
 
   /**
    * Tracks the dependency between a method and the super-method it calls, if any. Used to make
@@ -315,6 +316,10 @@
    */
   private final SetWithReportedReason<DexProgramClass> liveTypes = new SetWithReportedReason<>();
 
+  /** Set of effectively live items from the original program. */
+  // TODO(b/323816623): Add reason tracking.
+  private final Set<DexReference> effectivelyLiveOriginalReferences = SetUtils.newIdentityHashSet();
+
   /** Set of interfaces that have been transitioned to being instantiated indirectly. */
   private final Set<DexProgramClass> interfacesTransitionedToInstantiated =
       Sets.newIdentityHashSet();
@@ -1631,6 +1636,27 @@
         analysis -> analysis.traceInvokeVirtual(invokedMethod, resolutionResult, context));
   }
 
+  void traceMethodPosition(com.android.tools.r8.ir.code.Position position, ProgramMethod context) {
+    if (!options.testing.isKeepAnnotationsEnabled()) {
+      // Currently inlining is only intended for the evaluation of keep annotation edges.
+      return;
+    }
+    while (position.hasCallerPosition()) {
+      // Any inner position should not be non-synthetic user methods.
+      assert !position.isD8R8Synthesized();
+      DexMethod method = position.getMethod();
+      // TODO(b/325014359): It might be reasonable to reduce this map size by tracking which methods
+      //  actually are used in preconditions.
+      if (effectivelyLiveOriginalReferences.add(method)) {
+        effectivelyLiveOriginalReferences.add(method.getHolderType());
+      }
+      position = position.getCallerPosition();
+    }
+    // The outer-most position should be equal to the context.
+    // No need to trace this as the method is already traced since it is invoked.
+    assert context.getReference().isIdenticalTo(position.getMethod());
+  }
+
   void traceNewInstance(DexType type, ProgramMethod context) {
     boolean skipTracing =
         registerDeferredActionForDeadProtoBuilder(
@@ -3402,6 +3428,36 @@
     return liveTypes.contains(clazz);
   }
 
+  public boolean isEffectivelyLive(DexProgramClass clazz) {
+    if (isTypeLive(clazz)) {
+      return true;
+    }
+    if (mode.isInitialTreeShaking()) {
+      return false;
+    }
+    // TODO(b/325014359): Replace this by value tracking in instructions (akin to resource values).
+    for (DexEncodedField field : clazz.fields()) {
+      if (field.getOptimizationInfo().valueHasBeenPropagated()) {
+        return true;
+      }
+    }
+    // TODO(b/325014359): Replace this by value or position tracking.
+    //  We need to be careful not to throw away such values/positions.
+    for (DexEncodedMethod method : clazz.methods()) {
+      if (method.getOptimizationInfo().returnValueHasBeenPropagated()) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  public boolean isOriginalReferenceEffectivelyLive(DexReference reference) {
+    assert options.testing.isKeepAnnotationsEnabled();
+    // The effectively-live original set contains types, fields and methods witnessed by
+    // instructions, such as method inlining positions.
+    return effectivelyLiveOriginalReferences.contains(reference);
+  }
+
   public boolean isNonProgramTypeLive(DexClass clazz) {
     assert !clazz.isProgramClass();
     return liveNonProgramTypes.contains(clazz);
@@ -3744,17 +3800,18 @@
     includeMinimumKeepInfo(rootSet);
     timing.end();
 
+    assert applicableRules == ApplicableRulesEvaluator.empty();
     if (mode.isInitialTreeShaking()) {
-      // TODO(b/323816623): Start native interpretation here...
-      if (!keepDeclarations.isEmpty()) {
-        throw new Unimplemented("Native support for keep annotaitons pending");
-      }
+      applicableRules =
+          KeepAnnotationMatcher.computeInitialRules(
+              appInfo, keepDeclarations, options.getThreadingModule(), executorService);
       // Amend library methods with covariant return types.
       timing.begin("Model library");
       modelLibraryMethodsWithCovariantReturnTypes(appView);
       timing.end();
     } else if (appView.getKeepInfo() != null) {
       timing.begin("Retain keep info");
+      applicableRules = appView.getKeepInfo().getApplicableRules();
       EnqueuerEvent preconditionEvent = UnconditionalKeepInfoEvent.get();
       appView
           .getKeepInfo()
@@ -3767,10 +3824,12 @@
               this::applyMinimumKeepInfoWhenLiveOrTargeted);
       timing.end();
     }
+    timing.time("Unconditional rules", () -> applicableRules.evaluateUnconditionalRules(this));
     timing.begin("Enqueue all");
     enqueueAllIfNotShrinking();
     timing.end();
     timing.begin("Trace");
+    traceManifests(timing);
     trace(executorService, timing);
     timing.end();
     options.reporter.failIfPendingErrors();
@@ -3804,6 +3863,14 @@
     return result;
   }
 
+  private void traceManifests(Timing timing) {
+    if (options.isOptimizedResourceShrinking()) {
+      timing.begin("Trace AndroidManifest.xml files");
+      appView.getResourceShrinkerState().traceManifests();
+      timing.end();
+    }
+  }
+
   private void includeMinimumKeepInfo(RootSetBase rootSet) {
     rootSet
         .getDependentMinimumKeepInfo()
@@ -3814,6 +3881,14 @@
             this::recordDependentMinimumKeepInfo);
   }
 
+  public void includeMinimumKeepInfo(MinimumKeepInfoCollection minimumKeepInfo) {
+    minimumKeepInfo.forEach(
+        appView,
+        (i, j) -> recordDependentMinimumKeepInfo(EnqueuerEvent.unconditional(), i, j),
+        (i, j) -> recordDependentMinimumKeepInfo(EnqueuerEvent.unconditional(), i, j),
+        (i, j) -> recordDependentMinimumKeepInfo(EnqueuerEvent.unconditional(), i, j));
+  }
+
   private void applyMinimumKeepInfo(DexProgramClass clazz) {
     EnqueuerEvent preconditionEvent = UnconditionalKeepInfoEvent.get();
     KeepClassInfo.Joiner minimumKeepInfoForClass =
@@ -4380,6 +4455,8 @@
               : ImmutableSet.of(syntheticClass.getType());
         };
     amendKeepInfoWithCompanionMethods();
+    keepInfo.setMaterializedRules(applicableRules.getMaterializedRules());
+
     timing.begin("Rewrite with deferred results");
     deferredTracing.rewriteApplication(executorService);
     timing.end();
@@ -4567,6 +4644,8 @@
         // Continue fix-point processing if -if rules are enabled by items that newly became live.
         long numberOfLiveItemsAfterProcessing = getNumberOfLiveItems();
         if (numberOfLiveItemsAfterProcessing > numberOfLiveItems) {
+          timing.time("Conditional rules", () -> applicableRules.evaluateConditionalRules(this));
+
           // Build the mapping of active if rules. We use a single collection of if-rules to allow
           // removing if rules that have a constant sequent keep rule when they materialize.
           if (activeIfRules == null) {
@@ -4671,7 +4750,7 @@
                     context,
                     new InterfaceDesugarMissingTypeDiagnostic(
                         context.getOrigin(),
-                        Position.UNKNOWN,
+                        com.android.tools.r8.position.Position.UNKNOWN,
                         missing.asClassReference(),
                         context.getType().asClassReference(),
                         null)));
diff --git a/src/main/java/com/android/tools/r8/shaking/IfRuleEvaluator.java b/src/main/java/com/android/tools/r8/shaking/IfRuleEvaluator.java
index 933cc33..32ec312 100644
--- a/src/main/java/com/android/tools/r8/shaking/IfRuleEvaluator.java
+++ b/src/main/java/com/android/tools/r8/shaking/IfRuleEvaluator.java
@@ -12,7 +12,6 @@
 import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexDefinition;
 import com.android.tools.r8.graph.DexEncodedField;
-import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexReference;
@@ -178,23 +177,7 @@
   }
 
   private boolean isEffectivelyLive(DexProgramClass clazz) {
-    // A type is effectively live if (1) it is truly live, (2) the value of one of its fields has
-    // been inlined by the member value propagation, or (3) the return value of one of its methods
-    // has been forwarded by the member value propagation.
-    if (enqueuer.isTypeLive(clazz)) {
-      return true;
-    }
-    for (DexEncodedField field : clazz.fields()) {
-      if (field.getOptimizationInfo().valueHasBeenPropagated()) {
-        return true;
-      }
-    }
-    for (DexEncodedMethod method : clazz.methods()) {
-      if (method.getOptimizationInfo().returnValueHasBeenPropagated()) {
-        return true;
-      }
-    }
-    return false;
+    return enqueuer.isEffectivelyLive(clazz);
   }
 
   /** Determines if {@param clazz} satisfies the given if-rule class specification. */
diff --git a/src/main/java/com/android/tools/r8/shaking/KeepInfoCollection.java b/src/main/java/com/android/tools/r8/shaking/KeepInfoCollection.java
index 8100e4e..cd76ad3 100644
--- a/src/main/java/com/android/tools/r8/shaking/KeepInfoCollection.java
+++ b/src/main/java/com/android/tools/r8/shaking/KeepInfoCollection.java
@@ -29,6 +29,8 @@
 import com.android.tools.r8.graph.PrunedItems;
 import com.android.tools.r8.graph.lens.NonIdentityGraphLens;
 import com.android.tools.r8.shaking.KeepFieldInfo.Joiner;
+import com.android.tools.r8.shaking.rules.ApplicableRulesEvaluator;
+import com.android.tools.r8.shaking.rules.MaterializedRules;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.MapUtils;
@@ -264,6 +266,8 @@
 
   public abstract void writeToDirectory(Path directory) throws IOException;
 
+  public abstract ApplicableRulesEvaluator getApplicableRules();
+
   // Mutation interface for building up the keep info.
   public static class MutableKeepInfoCollection extends KeepInfoCollection {
 
@@ -278,6 +282,9 @@
     private final Map<DexField, KeepFieldInfo.Joiner> fieldRuleInstances;
     private final Map<DexMethod, KeepMethodInfo.Joiner> methodRuleInstances;
 
+    // Collection of materialized rules.
+    private MaterializedRules materializedRules;
+
     MutableKeepInfoCollection() {
       this(
           new IdentityHashMap<>(),
@@ -285,7 +292,8 @@
           new IdentityHashMap<>(),
           new IdentityHashMap<>(),
           new IdentityHashMap<>(),
-          new IdentityHashMap<>());
+          new IdentityHashMap<>(),
+          MaterializedRules.empty());
     }
 
     private MutableKeepInfoCollection(
@@ -294,13 +302,26 @@
         Map<DexField, KeepFieldInfo> keepFieldInfo,
         Map<DexType, KeepClassInfo.Joiner> classRuleInstances,
         Map<DexField, KeepFieldInfo.Joiner> fieldRuleInstances,
-        Map<DexMethod, KeepMethodInfo.Joiner> methodRuleInstances) {
+        Map<DexMethod, KeepMethodInfo.Joiner> methodRuleInstances,
+        MaterializedRules materializedRules) {
       this.keepClassInfo = keepClassInfo;
       this.keepMethodInfo = keepMethodInfo;
       this.keepFieldInfo = keepFieldInfo;
       this.classRuleInstances = classRuleInstances;
       this.fieldRuleInstances = fieldRuleInstances;
       this.methodRuleInstances = methodRuleInstances;
+      this.materializedRules = materializedRules;
+    }
+
+    public void setMaterializedRules(MaterializedRules materializedRules) {
+      assert this.materializedRules == MaterializedRules.empty();
+      assert materializedRules != null;
+      this.materializedRules = materializedRules;
+    }
+
+    @Override
+    public ApplicableRulesEvaluator getApplicableRules() {
+      return materializedRules.toApplicableRules();
     }
 
     public void removeKeepInfoForMergedClasses(PrunedItems prunedItems) {
@@ -360,12 +381,12 @@
               rewriteRuleInstances(
                   methodRuleInstances,
                   lens::getRenamedMethodSignature,
-                  KeepMethodInfo::newEmptyJoiner));
+                  KeepMethodInfo::newEmptyJoiner),
+              materializedRules.rewriteWithLens(lens));
       timing.end();
       return result;
     }
 
-    @SuppressWarnings("ReferenceEquality")
     private Map<DexType, KeepClassInfo> rewriteClassInfo(
         NonIdentityGraphLens lens, InternalOptions options, Timing timing) {
       timing.begin("Rewrite class info");
@@ -373,11 +394,11 @@
       keepClassInfo.forEach(
           (type, info) -> {
             DexType newType = lens.lookupType(type);
-            if (newType == options.dexItemFactory().intType) {
+            if (options.dexItemFactory().intType.isIdenticalTo(newType)) {
               assert !info.isPinned(options);
               return;
             }
-            assert newType == type
+            assert type.isIdenticalTo(newType)
                 || !info.isPinned(options)
                 || info.isMinificationAllowed(options)
                 || info.isRepackagingAllowed(options);
@@ -388,7 +409,6 @@
       return newClassInfo;
     }
 
-    @SuppressWarnings("ReferenceEquality")
     private Map<DexField, KeepFieldInfo> rewriteFieldInfo(
         NonIdentityGraphLens lens, InternalOptions options, Timing timing) {
       timing.begin("Rewrite field info");
@@ -396,7 +416,7 @@
       keepFieldInfo.forEach(
           (field, info) -> {
             DexField newField = lens.getRenamedFieldSignature(field);
-            assert newField.name == field.name
+            assert newField.name.isIdenticalTo(field.name)
                 || !info.isPinned(options)
                 || info.isMinificationAllowed(options);
             KeepFieldInfo previous = newFieldInfo.put(newField, info);
@@ -406,7 +426,7 @@
       return newFieldInfo;
     }
 
-    @SuppressWarnings({"ReferenceEquality", "UnusedVariable"})
+    @SuppressWarnings("UnusedVariable")
     private Map<DexMethod, KeepMethodInfo> rewriteMethodInfo(
         NonIdentityGraphLens lens, InternalOptions options, Timing timing) {
       timing.begin("Rewrite method info");
@@ -416,7 +436,7 @@
             DexMethod newMethod = lens.getRenamedMethodSignature(method);
             assert !info.isPinned(options)
                 || info.isMinificationAllowed(options)
-                || newMethod.name == method.name;
+                || newMethod.name.isIdenticalTo(method.name);
             assert !info.isPinned(options) || newMethod.getArity() == method.getArity();
             assert !info.isPinned(options)
                 || Streams.zip(
@@ -425,7 +445,7 @@
                         Object::equals)
                     .allMatch(x -> x);
             assert !info.isPinned(options)
-                || newMethod.getReturnType() == lens.lookupType(method.getReturnType());
+                || newMethod.getReturnType().isIdenticalTo(lens.lookupType(method.getReturnType()));
             KeepMethodInfo previous = newMethodInfo.put(newMethod, info);
             // TODO(b/169927809): Avoid collisions.
             // assert previous == null;
diff --git a/src/main/java/com/android/tools/r8/shaking/rules/ApplicableRulesEvaluator.java b/src/main/java/com/android/tools/r8/shaking/rules/ApplicableRulesEvaluator.java
new file mode 100644
index 0000000..ea65365
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/rules/ApplicableRulesEvaluator.java
@@ -0,0 +1,75 @@
+// Copyright (c) 2024, 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.rules;
+
+import com.android.tools.r8.shaking.Enqueuer;
+import com.android.tools.r8.shaking.MinimumKeepInfoCollection;
+import java.util.ArrayList;
+import java.util.concurrent.ConcurrentLinkedDeque;
+import java.util.function.Consumer;
+
+public abstract class ApplicableRulesEvaluator {
+
+  public static ApplicableRulesEvaluator empty() {
+    return EmptyEvaluator.INSTANCE;
+  }
+
+  public abstract void evaluateUnconditionalRules(Enqueuer enqueuer);
+
+  public abstract void evaluateConditionalRules(Enqueuer enqueuer);
+
+  public abstract MaterializedRules getMaterializedRules();
+
+  public static Builder initialRulesBuilder() {
+    return new Builder();
+  }
+
+  private static class EmptyEvaluator extends ApplicableRulesEvaluator {
+
+    private static EmptyEvaluator INSTANCE = new EmptyEvaluator();
+
+    private EmptyEvaluator() {}
+
+    @Override
+    public void evaluateUnconditionalRules(Enqueuer enqueuer) {
+      // Nothing to do.
+    }
+
+    @Override
+    public void evaluateConditionalRules(Enqueuer enqueuer) {
+      // Nothing to do.
+    }
+
+    @Override
+    public MaterializedRules getMaterializedRules() {
+      return MaterializedRules.empty();
+    }
+  }
+
+  public static class Builder {
+
+    private MinimumKeepInfoCollection rootConsequences =
+        MinimumKeepInfoCollection.createConcurrent();
+    private ConcurrentLinkedDeque<PendingInitialConditionalRule> rules =
+        new ConcurrentLinkedDeque<>();
+
+    private Builder() {}
+
+    public void addRootRule(Consumer<MinimumKeepInfoCollection> fn) {
+      fn.accept(rootConsequences);
+    }
+
+    public void addConditionalRule(PendingInitialConditionalRule rule) {
+      rules.add(rule);
+    }
+
+    public ApplicableRulesEvaluator build() {
+      if (rootConsequences.isEmpty() && rules.isEmpty()) {
+        return ApplicableRulesEvaluator.empty();
+      }
+      return new ApplicableRulesEvaluatorImpl<>(rootConsequences, new ArrayList<>(rules));
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/rules/ApplicableRulesEvaluatorImpl.java b/src/main/java/com/android/tools/r8/shaking/rules/ApplicableRulesEvaluatorImpl.java
new file mode 100644
index 0000000..c182c24
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/rules/ApplicableRulesEvaluatorImpl.java
@@ -0,0 +1,88 @@
+// Copyright (c) 2024, 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.rules;
+
+import com.android.tools.r8.shaking.Enqueuer;
+import com.android.tools.r8.shaking.MinimumKeepInfoCollection;
+import com.android.tools.r8.utils.ListUtils;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Objects;
+
+public class ApplicableRulesEvaluatorImpl<T> extends ApplicableRulesEvaluator {
+
+  private final MinimumKeepInfoCollection rootConsequences;
+
+  // TODO(b/323816623): Revaluate these numbers. They are set low/tight now to hit in tests.
+  private static final int reallocMinThreshold = 1;
+  private static final int reallocRatioThreshold = 10;
+  private int prunedCount = 0;
+  private List<PendingConditionalRuleBase<T>> pendingConditionalRules;
+
+  private final List<MaterializedConditionalRule> materializedRules = new ArrayList<>();
+
+  ApplicableRulesEvaluatorImpl(
+      MinimumKeepInfoCollection rootConsequences,
+      List<PendingConditionalRuleBase<T>> conditionalRules) {
+    assert !rootConsequences.isEmpty() || !conditionalRules.isEmpty();
+    this.rootConsequences = rootConsequences;
+    this.pendingConditionalRules = conditionalRules;
+  }
+
+  @Override
+  public void evaluateUnconditionalRules(Enqueuer enqueuer) {
+    assert materializedRules.isEmpty();
+    if (!rootConsequences.isEmpty()) {
+      enqueuer.includeMinimumKeepInfo(rootConsequences);
+    }
+  }
+
+  @Override
+  public void evaluateConditionalRules(Enqueuer enqueuer) {
+    if (pendingConditionalRules.isEmpty()) {
+      return;
+    }
+    // TODO(b/323816623): If we tracked newly live, we could speed up finding rules.
+    // TODO(b/323816623): Parallelize this.
+    for (int i = 0; i < pendingConditionalRules.size(); i++) {
+      PendingConditionalRuleBase<T> rule = pendingConditionalRules.get(i);
+      if (rule != null && rule.isSatisfiedAfterUpdate(enqueuer)) {
+        ++prunedCount;
+        pendingConditionalRules.set(i, null);
+        enqueuer.includeMinimumKeepInfo(rule.getConsequences());
+        materializedRules.add(rule.asMaterialized());
+      }
+    }
+
+    if (prunedCount == pendingConditionalRules.size()) {
+      assert ListUtils.all(pendingConditionalRules, Objects::isNull);
+      prunedCount = 0;
+      pendingConditionalRules = Collections.emptyList();
+      return;
+    }
+
+    int threshold =
+        Math.max(reallocMinThreshold, pendingConditionalRules.size() / reallocRatioThreshold);
+    if (prunedCount >= threshold) {
+      int newSize = pendingConditionalRules.size() - prunedCount;
+      List<PendingConditionalRuleBase<T>> newPending = new ArrayList<>(newSize);
+      for (PendingConditionalRuleBase<T> rule : pendingConditionalRules) {
+        if (rule != null) {
+          assert rule.isOutstanding();
+          newPending.add(rule);
+        }
+      }
+      assert newPending.size() == newSize;
+      prunedCount = 0;
+      pendingConditionalRules = newPending;
+    }
+  }
+
+  @Override
+  public MaterializedRules getMaterializedRules() {
+    return new MaterializedRules(rootConsequences, materializedRules);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationFakeProguardRule.java b/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationFakeProguardRule.java
new file mode 100644
index 0000000..2e28fcb
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationFakeProguardRule.java
@@ -0,0 +1,34 @@
+// Copyright (c) 2024, 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.rules;
+
+import com.android.tools.r8.keepanno.ast.KeepEdgeMetaInfo;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.position.Position;
+import com.android.tools.r8.shaking.ProguardClassType;
+import com.android.tools.r8.shaking.ProguardKeepRuleBase;
+
+// TODO(b/323816623): Make an interface to use in the keep-reason tracking.
+public class KeepAnnotationFakeProguardRule extends ProguardKeepRuleBase {
+
+  public KeepAnnotationFakeProguardRule(KeepEdgeMetaInfo metaInfo) {
+    super(
+        Origin.unknown(),
+        Position.UNKNOWN,
+        "keep-annotation",
+        null,
+        null,
+        null,
+        false,
+        ProguardClassType.CLASS,
+        null,
+        null,
+        null,
+        false,
+        null,
+        null,
+        null);
+  }
+}
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
new file mode 100644
index 0000000..ccac25a
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationMatcher.java
@@ -0,0 +1,491 @@
+// Copyright (c) 2024, 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.rules;
+
+import com.android.tools.r8.errors.Unimplemented;
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.ProgramDefinition;
+import com.android.tools.r8.graph.ProgramMember;
+import com.android.tools.r8.keepanno.ast.KeepBindingReference;
+import com.android.tools.r8.keepanno.ast.KeepBindings.KeepBindingSymbol;
+import com.android.tools.r8.keepanno.ast.KeepClassItemPattern;
+import com.android.tools.r8.keepanno.ast.KeepCondition;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.Annotation;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.ClassInstantiate;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.ClassOpenHierarchy;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.FieldGet;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.FieldReplace;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.FieldSet;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.Lookup;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.MethodInvoke;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.MethodReplace;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.Name;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.NeverInline;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.VisibilityRelax;
+import com.android.tools.r8.keepanno.ast.KeepConstraint.VisibilityRestrict;
+import com.android.tools.r8.keepanno.ast.KeepConstraintVisitor;
+import com.android.tools.r8.keepanno.ast.KeepConstraints;
+import com.android.tools.r8.keepanno.ast.KeepDeclaration;
+import com.android.tools.r8.keepanno.ast.KeepEdge;
+import com.android.tools.r8.keepanno.ast.KeepItemPattern;
+import com.android.tools.r8.keepanno.ast.KeepItemReference;
+import com.android.tools.r8.keepanno.ast.KeepMemberItemPattern;
+import com.android.tools.r8.keepanno.ast.KeepTarget;
+import com.android.tools.r8.shaking.KeepInfo.Joiner;
+import com.android.tools.r8.shaking.MinimumKeepInfoCollection;
+import com.android.tools.r8.threading.ThreadingModule;
+import com.android.tools.r8.utils.ListUtils;
+import com.android.tools.r8.utils.ThreadUtils;
+import com.google.common.collect.ImmutableList;
+import it.unimi.dsi.fastutil.ints.IntArrayList;
+import it.unimi.dsi.fastutil.ints.IntList;
+import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.function.Consumer;
+
+public class KeepAnnotationMatcher {
+
+  public static ApplicableRulesEvaluator computeInitialRules(
+      AppInfoWithClassHierarchy appInfo,
+      List<KeepDeclaration> keepDeclarations,
+      ThreadingModule threadingModule,
+      ExecutorService executorService)
+      throws ExecutionException {
+    KeepAnnotationMatcherPredicates predicates =
+        new KeepAnnotationMatcherPredicates(appInfo.dexItemFactory());
+    ApplicableRulesEvaluator.Builder builder = ApplicableRulesEvaluator.initialRulesBuilder();
+    ThreadUtils.processItems(
+        keepDeclarations,
+        declaration -> processDeclaration(declaration, appInfo, predicates, builder),
+        threadingModule,
+        executorService);
+    return builder.build();
+  }
+
+  private static void processDeclaration(
+      KeepDeclaration declaration,
+      AppInfoWithClassHierarchy appInfo,
+      KeepAnnotationMatcherPredicates predicates,
+      ApplicableRulesEvaluator.Builder builder) {
+    EdgeMatcher edgeMatcher = new EdgeMatcher(appInfo, predicates);
+    declaration.match(
+        edge ->
+            edgeMatcher.forEachMatch(
+                edge,
+                result -> {
+                  if (result.preconditions.isEmpty()) {
+                    builder.addRootRule(
+                        keepInfoCollection -> createKeepInfo(result, keepInfoCollection));
+                  } else {
+                    builder.addConditionalRule(
+                        new PendingInitialConditionalRule(
+                            result.preconditions,
+                            createKeepInfo(result, MinimumKeepInfoCollection.create())));
+                  }
+                }),
+        check -> {
+          throw new Unimplemented();
+        });
+  }
+
+  private static MinimumKeepInfoCollection createKeepInfo(
+      MatchResult result, MinimumKeepInfoCollection minimumKeepInfoCollection) {
+    ListUtils.forEachWithIndex(
+        result.consequences,
+        (item, i) -> {
+          Joiner<?, ?, ?> joiner =
+              minimumKeepInfoCollection.getOrCreateMinimumKeepInfoFor(item.getReference());
+          updateWithConstraints(item, joiner, result.constraints.get(i), result.edge);
+        });
+    return minimumKeepInfoCollection;
+  }
+
+  private static void updateWithConstraints(
+      ProgramDefinition item, Joiner<?, ?, ?> joiner, KeepConstraints constraints, KeepEdge edge) {
+    constraints.forEachAccept(
+        new KeepConstraintVisitor() {
+
+          @Override
+          public void onLookup(Lookup constraint) {
+            joiner.disallowShrinking();
+            joiner.addRule(new KeepAnnotationFakeProguardRule(edge.getMetaInfo()));
+          }
+
+          @Override
+          public void onName(Name constraint) {
+            joiner.disallowMinification();
+            if (item.isProgramClass()) {
+              joiner.asClassJoiner().disallowRepackaging();
+            }
+          }
+
+          @Override
+          public void onVisibilityRelax(VisibilityRelax constraint) {
+            // R8 will never restrict the access, so this constraint is implicitly maintained.
+          }
+
+          @Override
+          public void onVisibilityRestrict(VisibilityRestrict constraint) {
+            joiner.disallowAccessModification();
+          }
+
+          @Override
+          public void onNeverInline(NeverInline constraint) {
+            joiner.disallowOptimization();
+          }
+
+          @Override
+          public void onClassInstantiate(ClassInstantiate constraint) {
+            joiner.disallowOptimization();
+          }
+
+          @Override
+          public void onClassOpenHierarchy(ClassOpenHierarchy constraint) {
+            joiner.disallowOptimization();
+          }
+
+          @Override
+          public void onMethodInvoke(MethodInvoke constraint) {
+            joiner.disallowOptimization();
+          }
+
+          @Override
+          public void onMethodReplace(MethodReplace constraint) {
+            joiner.disallowOptimization();
+          }
+
+          @Override
+          public void onFieldGet(FieldGet constraint) {
+            joiner.disallowOptimization();
+          }
+
+          @Override
+          public void onFieldSet(FieldSet constraint) {
+            joiner.disallowOptimization();
+          }
+
+          @Override
+          public void onFieldReplace(FieldReplace constraint) {
+            joiner.disallowOptimization();
+          }
+
+          @Override
+          public void onAnnotation(Annotation constraint) {
+            joiner.disallowAnnotationRemoval();
+          }
+        });
+  }
+
+  public static class MatchResult {
+    private final KeepEdge edge;
+    private final List<ProgramDefinition> preconditions;
+    private final List<ProgramDefinition> consequences;
+    private final List<KeepConstraints> constraints;
+
+    public MatchResult(
+        KeepEdge edge,
+        List<ProgramDefinition> preconditions,
+        List<ProgramDefinition> consequences,
+        List<KeepConstraints> constraints) {
+      this.edge = edge;
+      this.preconditions = preconditions;
+      this.consequences = consequences;
+      this.constraints = constraints;
+    }
+  }
+
+  public static class EdgeMatcher {
+
+    private final AppInfoWithClassHierarchy appInfo;
+    private final KeepAnnotationMatcherPredicates predicates;
+
+    private NormalizedSchema schema;
+    private Assignment assignment;
+    private Consumer<MatchResult> callback;
+
+    public EdgeMatcher(
+        AppInfoWithClassHierarchy appInfo, KeepAnnotationMatcherPredicates predicates) {
+      this.appInfo = appInfo;
+      this.predicates = predicates;
+    }
+
+    public void forEachMatch(KeepEdge edge, Consumer<MatchResult> callback) {
+      this.callback = callback;
+      schema = new NormalizedSchema(edge);
+      assignment = new Assignment(schema);
+      findMatchingClass(0);
+      schema = null;
+      assignment = null;
+    }
+
+    private void foundMatch() {
+      callback.accept(assignment.createMatch(schema));
+    }
+
+    private void findMatchingClass(int classIndex) {
+      if (classIndex == schema.classes.size()) {
+        // All classes and their members are assigned, so report the assignment.
+        foundMatch();
+        return;
+      }
+      KeepClassItemPattern classPattern = schema.classes.get(classIndex);
+      if (!classPattern.getClassNamePattern().isExact()) {
+        throw new Unimplemented();
+      }
+      DexType type =
+          appInfo
+              .dexItemFactory()
+              .createType(classPattern.getClassNamePattern().getExactDescriptor());
+      DexProgramClass clazz = DexProgramClass.asProgramClassOrNull(appInfo.definitionFor(type));
+      if (clazz == null) {
+        // No valid match, so the rule is discarded. This should likely be a diagnostics info.
+        return;
+      }
+      if (!predicates.matchesClass(clazz, classPattern)) {
+        // Invalid match for this class.
+        return;
+      }
+      assignment.setClass(classIndex, clazz);
+      IntList classMemberIndexList = schema.classMembers.get(classIndex);
+      findMatchingMember(0, classMemberIndexList, clazz, classIndex + 1);
+    }
+
+    private void findMatchingMember(
+        int memberInHolderIndex,
+        IntList memberIndexTranslation,
+        DexProgramClass holder,
+        int nextClassIndex) {
+      if (memberInHolderIndex == memberIndexTranslation.size()) {
+        // All members of this class are assigned, continue search for the next class.
+        findMatchingClass(nextClassIndex);
+        return;
+      }
+      int nextMemberInHolderIndex = memberInHolderIndex + 1;
+      int memberIndex = memberIndexTranslation.getInt(memberInHolderIndex);
+      KeepMemberItemPattern memberItemPattern = schema.members.get(memberIndex);
+      memberItemPattern
+          .getMemberPattern()
+          .match(
+              generalMember -> {
+                if (!holder.hasMethodsOrFields()) {
+                  // The empty class can only match the "all member" pattern but with no assignment.
+                  if (generalMember.isAllMembers()) {
+                    assignment.setEmptyMemberMatch(memberIndex);
+                    findMatchingMember(
+                        nextMemberInHolderIndex, memberIndexTranslation, holder, nextClassIndex);
+                  }
+                  return;
+                }
+                if (!generalMember.isAllMembers()) {
+                  throw new Unimplemented();
+                }
+                holder.forEachProgramMember(
+                    f -> {
+                      assignment.setMember(memberIndex, f);
+                      findMatchingMember(
+                          nextMemberInHolderIndex, memberIndexTranslation, holder, nextClassIndex);
+                    });
+              },
+              fieldMember -> {
+                throw new Unimplemented();
+              },
+              methodMember -> {
+                holder.forEachProgramMethod(
+                    m -> {
+                      if (predicates.matchesMethod(methodMember, m)) {
+                        assignment.setMember(memberIndex, m);
+                        findMatchingMember(
+                            nextMemberInHolderIndex,
+                            memberIndexTranslation,
+                            holder,
+                            nextClassIndex);
+                      }
+                    });
+              });
+    }
+  }
+
+  /**
+   * The normalized edge schema maps an edge into integer indexed class patterns and member
+   * patterns. The preconditions and consequences are then index references to these pattern. Each
+   * index denotes the identity of an item, thus the same reference must share the same item found
+   * by a pattern.
+   */
+  private static class NormalizedSchema {
+
+    final KeepEdge edge;
+    final Reference2IntMap<KeepBindingSymbol> symbolToKey = new Reference2IntOpenHashMap<>();
+    final List<KeepClassItemPattern> classes = new ArrayList<>();
+    final List<KeepMemberItemPattern> members = new ArrayList<>();
+    final List<IntList> classMembers = new ArrayList<>();
+    final IntList preconditions = new IntArrayList();
+    final IntList consequences = new IntArrayList();
+    final List<KeepConstraints> constraints = new ArrayList<>();
+
+    public NormalizedSchema(KeepEdge edge) {
+      this.edge = edge;
+      edge.getPreconditions().forEach(this::addPrecondition);
+      edge.getConsequences().forEachTarget(this::addConsequence);
+      ListUtils.forEachWithIndex(
+          members,
+          (member, memberIndex) -> {
+            member
+                .getClassReference()
+                .matchClassItemReference(
+                    bindingReference -> {
+                      int classIndex = symbolToKey.getInt(bindingReference);
+                      classMembers.get(classIndex).add(memberIndex);
+                    },
+                    classItemPattern -> {
+                      // The member declares its own inline class so link it directly.
+                      IntArrayList memberList = new IntArrayList();
+                      memberList.add(memberIndex);
+                      classes.add(classItemPattern);
+                      classMembers.add(memberList);
+                    });
+          });
+    }
+
+    public static boolean isClassKeyReference(int keyRef) {
+      return keyRef >= 0;
+    }
+
+    private int encodeClassKey(int key) {
+      assert isClassKeyReference(key);
+      return key;
+    }
+
+    public static int decodeClassKeyReference(int key) {
+      assert isClassKeyReference(key);
+      return key;
+    }
+
+    private int encodeMemberKey(int key) {
+      assert key >= 0;
+      return -(key + 1);
+    }
+
+    public static int decodeMemberKeyReference(int key) {
+      assert !isClassKeyReference(key);
+      assert key < 0;
+      return -(key + 1);
+    }
+
+    private int defineItemReference(KeepItemReference reference) {
+      return reference.apply(this::defineBindingReference, this::defineItemPattern);
+    }
+
+    private int defineBindingReference(KeepBindingReference reference) {
+      return symbolToKey.computeIfAbsent(
+          reference.getName(),
+          symbol -> defineItemPattern(edge.getBindings().get(symbol).getItem()));
+    }
+
+    private int defineItemPattern(KeepItemPattern item) {
+      if (item.isClassItemPattern()) {
+        int key = classes.size();
+        classes.add(item.asClassItemPattern());
+        classMembers.add(new IntArrayList());
+        return encodeClassKey(key);
+      }
+      int key = members.size();
+      members.add(item.asMemberItemPattern());
+      return encodeMemberKey(key);
+    }
+
+    public void addPrecondition(KeepCondition condition) {
+      preconditions.add(defineItemReference(condition.getItem()));
+    }
+
+    private void addConsequence(KeepTarget target) {
+      consequences.add(defineItemReference(target.getItem()));
+      constraints.add(target.getConstraints());
+    }
+  }
+
+  /**
+   * The assignment contains the full matching of the pattern, if a matching was found. The
+   * assignment is mutable and updated during the search. When a match is found the required
+   * information must be copied over immediately by creating a match result.
+   */
+  private static class Assignment {
+
+    final List<DexProgramClass> classes;
+    final List<ProgramMember<?, ?>> members;
+    boolean hasEmptyMembers = false;
+
+    private Assignment(NormalizedSchema schema) {
+      classes = Arrays.asList(new DexProgramClass[schema.classes.size()]);
+      members = Arrays.asList(new ProgramMember<?, ?>[schema.members.size()]);
+    }
+
+    ProgramDefinition getItemForReference(int keyReference) {
+      if (NormalizedSchema.isClassKeyReference(keyReference)) {
+        return classes.get(NormalizedSchema.decodeClassKeyReference(keyReference));
+      }
+      return members.get(NormalizedSchema.decodeMemberKeyReference(keyReference));
+    }
+
+    void setClass(int index, DexProgramClass type) {
+      classes.set(index, type);
+    }
+
+    void setMember(int index, ProgramMember<?, ?> member) {
+      members.set(index, member);
+    }
+
+    void setEmptyMemberMatch(int index) {
+      hasEmptyMembers = true;
+      members.set(index, null);
+    }
+
+    public MatchResult createMatch(NormalizedSchema schema) {
+      return new MatchResult(
+          schema.edge,
+          schema.preconditions.isEmpty()
+              ? Collections.emptyList()
+              : getItemList(schema.preconditions),
+          getItemList(schema.consequences),
+          getConstraints(schema));
+    }
+
+    private List<ProgramDefinition> getItemList(IntList indexReferences) {
+      assert !indexReferences.isEmpty();
+      List<ProgramDefinition> definitions = new ArrayList<>(indexReferences.size());
+      for (int i = 0; i < indexReferences.size(); i++) {
+        ProgramDefinition item = getItemForReference(indexReferences.getInt(i));
+        assert item != null || hasEmptyMembers;
+        if (item != null) {
+          definitions.add(item);
+        }
+      }
+      return definitions;
+    }
+
+    private List<KeepConstraints> getConstraints(NormalizedSchema schema) {
+      if (!hasEmptyMembers) {
+        return schema.constraints;
+      }
+      // Since members may have a matching "empty" pattern, we need to prune those from the
+      // constraints, so it matches the consequence list.
+      ImmutableList.Builder<KeepConstraints> builder = ImmutableList.builder();
+      for (int i = 0; i < schema.consequences.size(); i++) {
+        ProgramDefinition item = getItemForReference(schema.consequences.getInt(i));
+        if (item != null) {
+          builder.add(schema.constraints.get(i));
+        }
+      }
+      return builder.build();
+    }
+  }
+}
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
new file mode 100644
index 0000000..45e8385
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/rules/KeepAnnotationMatcherPredicates.java
@@ -0,0 +1,170 @@
+// Copyright (c) 2024, 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.rules;
+
+import com.android.tools.r8.errors.Unimplemented;
+import com.android.tools.r8.graph.DexAnnotationSet;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexTypeList;
+import com.android.tools.r8.graph.MethodAccessFlags;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.keepanno.ast.KeepArrayTypePattern;
+import com.android.tools.r8.keepanno.ast.KeepClassItemPattern;
+import com.android.tools.r8.keepanno.ast.KeepInstanceOfPattern;
+import com.android.tools.r8.keepanno.ast.KeepMethodAccessPattern;
+import com.android.tools.r8.keepanno.ast.KeepMethodParametersPattern;
+import com.android.tools.r8.keepanno.ast.KeepMethodPattern;
+import com.android.tools.r8.keepanno.ast.KeepMethodReturnTypePattern;
+import com.android.tools.r8.keepanno.ast.KeepPrimitiveTypePattern;
+import com.android.tools.r8.keepanno.ast.KeepQualifiedClassNamePattern;
+import com.android.tools.r8.keepanno.ast.KeepStringPattern;
+import com.android.tools.r8.keepanno.ast.KeepTypePattern;
+import com.android.tools.r8.keepanno.ast.OptionalPattern;
+import java.util.List;
+
+public class KeepAnnotationMatcherPredicates {
+
+  private final DexItemFactory factory;
+
+  public KeepAnnotationMatcherPredicates(DexItemFactory factory) {
+    this.factory = factory;
+  }
+
+  public boolean matchesClass(DexProgramClass clazz, KeepClassItemPattern classPattern) {
+    return matchesClassName(clazz.getType(), classPattern.getClassNamePattern())
+        && matchesInstanceOfPattern(clazz, classPattern.getInstanceOfPattern())
+        && matchesAnnotatedBy(clazz.annotations(), classPattern.getAnnotatedByPattern());
+  }
+
+  public boolean matchesClassName(DexType type, KeepQualifiedClassNamePattern pattern) {
+    if (pattern.isAny()) {
+      return true;
+    }
+    if (pattern.isExact()) {
+      return type.toDescriptorString().equals(pattern.getExactDescriptor());
+    }
+    throw new Unimplemented();
+  }
+
+  private boolean matchesInstanceOfPattern(
+      DexProgramClass unusedClazz, KeepInstanceOfPattern pattern) {
+    if (pattern.isAny()) {
+      return true;
+    }
+    throw new Unimplemented();
+  }
+
+  public boolean matchesMethod(KeepMethodPattern methodPattern, ProgramMethod method) {
+    if (methodPattern.isAnyMethod()) {
+      return true;
+    }
+    return matchesName(method.getName(), methodPattern.getNamePattern().asStringPattern())
+        && matchesReturnType(method.getReturnType(), methodPattern.getReturnTypePattern())
+        && matchesParameters(method.getParameters(), methodPattern.getParametersPattern())
+        && matchesAnnotatedBy(method.getAnnotations(), methodPattern.getAnnotatedByPattern())
+        && matchesAccess(method.getAccessFlags(), methodPattern.getAccessPattern());
+  }
+
+  public boolean matchesAccess(MethodAccessFlags access, KeepMethodAccessPattern pattern) {
+    if (pattern.isAny()) {
+      return true;
+    }
+    throw new Unimplemented();
+  }
+
+  public boolean matchesAnnotatedBy(
+      DexAnnotationSet annotations, OptionalPattern<KeepQualifiedClassNamePattern> pattern) {
+    if (pattern.isAbsent()) {
+      return true;
+    }
+    throw new Unimplemented();
+  }
+
+  public boolean matchesParameters(DexTypeList parameters, KeepMethodParametersPattern pattern) {
+    if (pattern.isAny()) {
+      return true;
+    }
+    List<KeepTypePattern> patternList = pattern.asList();
+    if (parameters.size() != patternList.size()) {
+      return false;
+    }
+    int size = parameters.size();
+    for (int i = 0; i < size; i++) {
+      if (!matchesType(parameters.get(i), patternList.get(i))) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  public boolean matchesName(DexString name, KeepStringPattern namePattern) {
+    if (namePattern.isAny()) {
+      return true;
+    }
+    if (namePattern.isExact()) {
+      return namePattern.asExactString().equals(name.toString());
+    }
+    throw new Unimplemented();
+  }
+
+  public boolean matchesReturnType(
+      DexType returnType, KeepMethodReturnTypePattern returnTypePattern) {
+    if (returnTypePattern.isAny()) {
+      return true;
+    }
+    if (returnTypePattern.isVoid() && returnType.isVoidType()) {
+      return true;
+    }
+    return matchesType(returnType, returnTypePattern.asType());
+  }
+
+  public boolean matchesType(DexType type, KeepTypePattern pattern) {
+    return pattern.apply(
+        () -> true,
+        p -> matchesPrimitiveType(type, p),
+        p -> matchesArrayType(type, p),
+        p -> matchesClassType(type, p));
+  }
+
+  public boolean matchesClassType(DexType type, KeepQualifiedClassNamePattern pattern) {
+    if (!type.isClassType()) {
+      return false;
+    }
+    if (pattern.isAny()) {
+      return true;
+    }
+    if (pattern.isExact()) {
+      return pattern.getExactDescriptor().equals(type.toDescriptorString());
+    }
+    throw new Unimplemented();
+  }
+
+  public boolean matchesArrayType(DexType type, KeepArrayTypePattern pattern) {
+    if (!type.isArrayType()) {
+      return false;
+    }
+    if (pattern.isAny()) {
+      return true;
+    }
+    if (type.getArrayTypeDimensions() < pattern.getDimensions()) {
+      return false;
+    }
+    return matchesType(
+        type.toArrayElementAfterDimension(pattern.getDimensions(), factory), pattern.getBaseType());
+  }
+
+  public boolean matchesPrimitiveType(DexType type, KeepPrimitiveTypePattern pattern) {
+    if (!type.isPrimitiveType()) {
+      return false;
+    }
+    if (pattern.isAny()) {
+      return true;
+    }
+    return type.asPrimitiveTypeDescriptorChar() == pattern.getDescriptorChar();
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/rules/MaterializedConditionalRule.java b/src/main/java/com/android/tools/r8/shaking/rules/MaterializedConditionalRule.java
new file mode 100644
index 0000000..069b3c3
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/rules/MaterializedConditionalRule.java
@@ -0,0 +1,26 @@
+// Copyright (c) 2024, 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.rules;
+
+import com.android.tools.r8.graph.DexReference;
+import com.android.tools.r8.shaking.MinimumKeepInfoCollection;
+import java.util.List;
+
+public class MaterializedConditionalRule {
+
+  private final List<DexReference> preconditions;
+  private final MinimumKeepInfoCollection consequences;
+
+  MaterializedConditionalRule(
+      List<DexReference> preconditions, MinimumKeepInfoCollection consequences) {
+    assert !preconditions.isEmpty();
+    this.preconditions = preconditions;
+    this.consequences = consequences;
+  }
+
+  PendingConditionalRule asPendingRule() {
+    return new PendingConditionalRule(preconditions, consequences);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/rules/MaterializedRules.java b/src/main/java/com/android/tools/r8/shaking/rules/MaterializedRules.java
new file mode 100644
index 0000000..d12ce3d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/rules/MaterializedRules.java
@@ -0,0 +1,48 @@
+// Copyright (c) 2024, 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.rules;
+
+import com.android.tools.r8.graph.lens.NonIdentityGraphLens;
+import com.android.tools.r8.shaking.MinimumKeepInfoCollection;
+import com.android.tools.r8.utils.ListUtils;
+import java.util.Collections;
+import java.util.List;
+
+public class MaterializedRules {
+
+  private static final MaterializedRules EMPTY =
+      new MaterializedRules(MinimumKeepInfoCollection.empty(), Collections.emptyList());
+
+  private final MinimumKeepInfoCollection rootConsequences;
+  private final List<MaterializedConditionalRule> conditionalRules;
+
+  MaterializedRules(
+      MinimumKeepInfoCollection rootConsequences,
+      List<MaterializedConditionalRule> conditionalRules) {
+    this.rootConsequences = rootConsequences;
+    this.conditionalRules = conditionalRules;
+  }
+
+  public static MaterializedRules empty() {
+    return EMPTY;
+  }
+
+  public MaterializedRules rewriteWithLens(NonIdentityGraphLens lens) {
+    // The preconditions of these are not rewritten. We assume witnessing instructions
+    // to cary the original references to deem them effectively live.
+    // TODO(b/323816623): Do we need to rewrite the consequent sets? Or would the constraints
+    //  always ensure they remain if the keep info needs to be reapplied?
+    return this;
+  }
+
+  public ApplicableRulesEvaluator toApplicableRules() {
+    if (rootConsequences.isEmpty() && conditionalRules.isEmpty()) {
+      return ApplicableRulesEvaluator.empty();
+    }
+    return new ApplicableRulesEvaluatorImpl<>(
+        rootConsequences,
+        ListUtils.map(conditionalRules, MaterializedConditionalRule::asPendingRule));
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/rules/PendingConditionalRule.java b/src/main/java/com/android/tools/r8/shaking/rules/PendingConditionalRule.java
new file mode 100644
index 0000000..22d06ed
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/rules/PendingConditionalRule.java
@@ -0,0 +1,27 @@
+// Copyright (c) 2024, 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.rules;
+
+import com.android.tools.r8.graph.DexReference;
+import com.android.tools.r8.shaking.Enqueuer;
+import com.android.tools.r8.shaking.MinimumKeepInfoCollection;
+import java.util.List;
+
+public class PendingConditionalRule extends PendingConditionalRuleBase<DexReference> {
+
+  PendingConditionalRule(List<DexReference> preconditions, MinimumKeepInfoCollection consequences) {
+    super(preconditions, consequences);
+  }
+
+  @Override
+  DexReference getReference(DexReference item) {
+    return item;
+  }
+
+  @Override
+  boolean isSatisfied(DexReference item, Enqueuer enqueuer) {
+    return enqueuer.isOriginalReferenceEffectivelyLive(item);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/rules/PendingConditionalRuleBase.java b/src/main/java/com/android/tools/r8/shaking/rules/PendingConditionalRuleBase.java
new file mode 100644
index 0000000..5716e74
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/rules/PendingConditionalRuleBase.java
@@ -0,0 +1,67 @@
+// Copyright (c) 2024, 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.rules;
+
+import com.android.tools.r8.graph.DexReference;
+import com.android.tools.r8.shaking.Enqueuer;
+import com.android.tools.r8.shaking.MinimumKeepInfoCollection;
+import java.util.ArrayList;
+import java.util.List;
+
+public abstract class PendingConditionalRuleBase<T> {
+
+  private final List<T> outstandingPreconditions;
+  private final List<DexReference> satisfiedPreconditions;
+  private final MinimumKeepInfoCollection consequences;
+
+  PendingConditionalRuleBase(List<T> preconditions, MinimumKeepInfoCollection consequences) {
+    this.outstandingPreconditions = preconditions;
+    this.satisfiedPreconditions = new ArrayList<>(preconditions.size());
+    this.consequences = consequences;
+  }
+
+  abstract DexReference getReference(T item);
+
+  abstract boolean isSatisfied(T item, Enqueuer enqueuer);
+
+  MinimumKeepInfoCollection getConsequences() {
+    return consequences;
+  }
+
+  MaterializedConditionalRule asMaterialized() {
+    assert !isOutstanding();
+    return new MaterializedConditionalRule(satisfiedPreconditions, consequences);
+  }
+
+  final boolean isOutstanding() {
+    return !outstandingPreconditions.isEmpty();
+  }
+
+  final boolean isSatisfiedAfterUpdate(Enqueuer enqueuer) {
+    assert isOutstanding();
+    int newlySatisfied = 0;
+    for (T precondition : outstandingPreconditions) {
+      if (isSatisfied(precondition, enqueuer)) {
+        ++newlySatisfied;
+        satisfiedPreconditions.add(getReference(precondition));
+      }
+    }
+    // Not satisfied and nothing changed.
+    if (newlySatisfied == 0) {
+      return false;
+    }
+    // The rule is satisfied in full.
+    if (newlySatisfied == outstandingPreconditions.size()) {
+      outstandingPreconditions.clear();
+      return true;
+    }
+    // Partially satisfied.
+    // This is expected to be the uncommon case so the update to outstanding is delayed to here.
+    outstandingPreconditions.removeIf(
+        outstanding -> satisfiedPreconditions.contains(getReference(outstanding)));
+    assert isOutstanding();
+    return false;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/rules/PendingInitialConditionalRule.java b/src/main/java/com/android/tools/r8/shaking/rules/PendingInitialConditionalRule.java
new file mode 100644
index 0000000..8983f20
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/rules/PendingInitialConditionalRule.java
@@ -0,0 +1,37 @@
+// Copyright (c) 2024, 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.rules;
+
+import com.android.tools.r8.graph.DexReference;
+import com.android.tools.r8.graph.ProgramDefinition;
+import com.android.tools.r8.shaking.Enqueuer;
+import com.android.tools.r8.shaking.MinimumKeepInfoCollection;
+import java.util.List;
+
+public class PendingInitialConditionalRule extends PendingConditionalRuleBase<ProgramDefinition> {
+
+  PendingInitialConditionalRule(
+      List<ProgramDefinition> preconditions, MinimumKeepInfoCollection consequences) {
+    super(preconditions, consequences);
+    assert !preconditions.isEmpty();
+  }
+
+  @Override
+  DexReference getReference(ProgramDefinition item) {
+    return item.getReference();
+  }
+
+  @Override
+  boolean isSatisfied(ProgramDefinition item, Enqueuer enqueuer) {
+    if (item.isClass()) {
+      return enqueuer.isTypeLive(item.asClass());
+    }
+    if (item.isField()) {
+      return enqueuer.isFieldLive(item.asField());
+    }
+    assert item.isMethod();
+    return enqueuer.isMethodLive(item.asMethod());
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index f086c7c..6ea5e06 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -2181,6 +2181,11 @@
   public static class TestingOptions {
 
     public boolean enableExtractedKeepAnnotations = false;
+    public boolean enableEmbeddedKeepAnnotations = false;
+
+    public boolean isKeepAnnotationsEnabled() {
+      return enableExtractedKeepAnnotations || enableEmbeddedKeepAnnotations;
+    }
 
     public boolean enableNumberUnboxer = false;
     public boolean printNumberUnboxed = false;
diff --git a/src/main/java/com/android/tools/r8/utils/ListUtils.java b/src/main/java/com/android/tools/r8/utils/ListUtils.java
index 22d19f7..26feadb 100644
--- a/src/main/java/com/android/tools/r8/utils/ListUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ListUtils.java
@@ -318,6 +318,15 @@
 
   public static <T> boolean all(List<T> items, Predicate<T> predicate) {
     for (T item : items) {
+      if (!predicate.test(item)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  public static <T> boolean any(List<T> items, Predicate<T> predicate) {
+    for (T item : items) {
       if (predicate.test(item)) {
         return true;
       }
diff --git a/src/main/java/com/android/tools/r8/utils/ResourceShrinkerUtils.java b/src/main/java/com/android/tools/r8/utils/ResourceShrinkerUtils.java
index 2d4e961..41ad64f 100644
--- a/src/main/java/com/android/tools/r8/utils/ResourceShrinkerUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ResourceShrinkerUtils.java
@@ -55,7 +55,7 @@
     for (AndroidResourceInput androidResource : androidResources) {
       switch (androidResource.getKind()) {
         case MANIFEST:
-          state.setManifestProvider(
+          state.addManifestProvider(
               () -> wrapThrowingInputStreamResource(appView, androidResource));
           break;
         case RESOURCE_TABLE:
diff --git a/src/main/keep.txt b/src/main/keep.txt
index 2aba17e..83f70b1 100644
--- a/src/main/keep.txt
+++ b/src/main/keep.txt
@@ -29,7 +29,3 @@
 
 # Test in this class is using the class name to fing the original .java file.
 -keep class com.android.tools.r8.ir.desugar.varhandle.VarHandleDesugaringMethods
-
-# Keep everything in the annotations package of keepanno.
-# These are public API as they denote the supported annotations to be interpreted by R8.
--keep class com.android.tools.r8.keepanno.annotations.** { *; }
diff --git a/src/resourceshrinker/java/com/android/build/shrinker/ResourceTableUtil.kt b/src/resourceshrinker/java/com/android/build/shrinker/ResourceTableUtil.kt
index 4327997..88bb5e4 100644
--- a/src/resourceshrinker/java/com/android/build/shrinker/ResourceTableUtil.kt
+++ b/src/resourceshrinker/java/com/android/build/shrinker/ResourceTableUtil.kt
@@ -33,20 +33,28 @@
 
 internal fun Resources.ResourceTable.nullOutEntriesWithIds(ids: List<Int>)
     : Resources.ResourceTable {
+    return nullOutEntriesWithIds(ids, false)
+}
+
+internal fun Resources.ResourceTable.nullOutEntriesWithIds(
+    ids: List<Int>, pruneResourceNames: Boolean): Resources.ResourceTable {
     if (ids.isEmpty()) {
         return this
     }
     val packageMappings = calculatePackageMappings(ids)
     val tableBuilder = this.toBuilder()
-    tableBuilder.packageBuilderList.forEach{
+    tableBuilder.packageBuilderList.forEach {
         val typeMappings = packageMappings[it.packageId.id]
         if (typeMappings != null) {
-            it.typeBuilderList.forEach { type->
+            it.typeBuilderList.forEach { type ->
                 val entryList = typeMappings[type.typeId.id]
                 if (entryList != null) {
                     type.entryBuilderList.forEach { entry ->
                         if (entryList.contains(entry.entryId.id)) {
                             entry.clearConfigValue()
+                            if (pruneResourceNames) {
+                                entry.clearName();
+                            }
                             if (entry.hasOverlayableItem()) {
                                 entry.clearOverlayableItem()
                             }
diff --git a/src/resourceshrinker/java/com/android/build/shrinker/r8integration/R8ResourceShrinkerState.java b/src/resourceshrinker/java/com/android/build/shrinker/r8integration/R8ResourceShrinkerState.java
index d8c98c7..29a3399 100644
--- a/src/resourceshrinker/java/com/android/build/shrinker/r8integration/R8ResourceShrinkerState.java
+++ b/src/resourceshrinker/java/com/android/build/shrinker/r8integration/R8ResourceShrinkerState.java
@@ -38,6 +38,7 @@
 import java.io.IOException;
 import java.io.InputStream;
 import java.nio.file.Paths;
+import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.IdentityHashMap;
@@ -54,7 +55,7 @@
   private final R8ResourceShrinkerModel r8ResourceShrinkerModel;
   private final Map<String, Supplier<InputStream>> xmlFileProviders = new HashMap<>();
 
-  private Supplier<InputStream> manifestProvider;
+  private final List<Supplier<InputStream>> manifestProviders = new ArrayList<>();
   private final Map<String, Supplier<InputStream>> resfileProviders = new HashMap<>();
   private final Map<ResourceTable, FeatureSplit> resourceTables = new HashMap<>();
   private ClassReferenceCallback enqueuerCallback;
@@ -82,7 +83,7 @@
       return;
     }
     ResourceUsageModel.markReachable(resource);
-    traceXml(id);
+    traceXmlForResourceId(id);
     if (resource.references != null) {
       for (Resource reference : resource.references) {
         if (!reference.isReachable()) {
@@ -92,6 +93,12 @@
     }
   }
 
+  public void traceManifests() {
+    for (Supplier<InputStream> manifestProvider : manifestProviders) {
+      traceXml("AndroidManifest.xml", manifestProvider.get());
+    }
+  }
+
   public void setEnqueuerCallback(ClassReferenceCallback enqueuerCallback) {
     assert this.enqueuerCallback == null;
     this.enqueuerCallback = enqueuerCallback;
@@ -111,8 +118,8 @@
     return packageNames;
   }
 
-  public void setManifestProvider(Supplier<InputStream> manifestProvider) {
-    this.manifestProvider = manifestProvider;
+  public void addManifestProvider(Supplier<InputStream> manifestProvider) {
+    this.manifestProviders.add(manifestProvider);
   }
 
   public void addXmlFileProvider(Supplier<InputStream> inputStreamSupplier, String location) {
@@ -170,7 +177,8 @@
         (resourceTable, featureSplit) ->
             shrunkenTables.put(
                 featureSplit,
-                ResourceTableUtilKt.nullOutEntriesWithIds(resourceTable, resourceIdsToRemove)));
+                ResourceTableUtilKt.nullOutEntriesWithIds(
+                    resourceTable, resourceIdsToRemove, true)));
 
     return new ShrinkerResult(resEntriesToKeep, shrunkenTables);
   }
@@ -185,19 +193,24 @@
     return resEntriesToKeep.build();
   }
 
-  private void traceXml(int id) {
+  private void traceXmlForResourceId(int id) {
     String xmlFile = getResourceIdToXmlFiles().get(id);
     if (xmlFile != null) {
       InputStream inputStream = xmlFileProviders.get(xmlFile).get();
-      try {
-        XmlNode xmlNode = XmlNode.parseFrom(inputStream);
-        visitNode(xmlNode, xmlFile);
-      } catch (IOException e) {
-        throw new RuntimeException(e);
-      }
+      traceXml(xmlFile, inputStream);
     }
   }
 
+  private void traceXml(String xmlFile, InputStream inputStream) {
+    try {
+      XmlNode xmlNode = XmlNode.parseFrom(inputStream);
+      visitNode(xmlNode, xmlFile);
+    } catch (IOException e) {
+      errorHandler.apply(e);
+    }
+  }
+
+
   private void tryEnqueuerOnString(String possibleClass, String xmlName) {
     // There are a lot of xml tags and attributes that are evaluated over and over, if it is
     // not a class, ignore it.
@@ -264,11 +277,10 @@
   // Temporary to support updating the reachable entries from the manifest, we need to instead
   // trace these in the enqueuer.
   public void updateModelWithManifestReferences() throws IOException {
-    if (manifestProvider == null) {
-      return;
+    for (Supplier<InputStream> manifestProvider : manifestProviders) {
+      ProtoAndroidManifestUsageRecorderKt.recordUsagesFromNode(
+          XmlNode.parseFrom(manifestProvider.get()), r8ResourceShrinkerModel);
     }
-    ProtoAndroidManifestUsageRecorderKt.recordUsagesFromNode(
-        XmlNode.parseFrom(manifestProvider.get()), r8ResourceShrinkerModel);
   }
 
   public void updateModelWithKeepXmlReferences() throws IOException {
diff --git a/src/test/java/com/android/tools/r8/ExternalR8TestBuilder.java b/src/test/java/com/android/tools/r8/ExternalR8TestBuilder.java
index 52d8b52..247cb6a 100644
--- a/src/test/java/com/android/tools/r8/ExternalR8TestBuilder.java
+++ b/src/test/java/com/android/tools/r8/ExternalR8TestBuilder.java
@@ -38,7 +38,7 @@
         ExternalR8TestBuilder> {
 
   // The r8.jar to run.
-  private List<Path> r8Classpath = ToolHelper.getClasspathForR8();
+  private List<Path> r8Classpath = ToolHelper.getBuildPropR8RuntimePath();
 
   // Ordered list of program jar entries.
   private final List<Path> programJars = new ArrayList<>();
diff --git a/src/test/java/com/android/tools/r8/R8TestCompileResult.java b/src/test/java/com/android/tools/r8/R8TestCompileResult.java
index 8237f9b..7454ce3 100644
--- a/src/test/java/com/android/tools/r8/R8TestCompileResult.java
+++ b/src/test/java/com/android/tools/r8/R8TestCompileResult.java
@@ -9,6 +9,7 @@
 import static org.junit.Assert.assertNotNull;
 
 import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.androidresources.AndroidResourceTestingUtils;
 import com.android.tools.r8.androidresources.AndroidResourceTestingUtils.ResourceTableInspector;
 import com.android.tools.r8.dexsplitter.SplitterTestBase.SplitRunner;
 import com.android.tools.r8.profile.art.model.ExternalArtProfile;
@@ -173,6 +174,12 @@
     return self();
   }
 
+  public String dumpResources() throws IOException {
+    ProcessResult processResult = AndroidResourceTestingUtils.dumpWithAapt2(resourceShrinkerOutput);
+    assert processResult.exitCode == 0;
+    return processResult.stdout;
+  }
+
   public <E extends Throwable> R8TestCompileResult inspectShrunkenResourcesForFeature(
       Consumer<ResourceTableInspector> consumer, String featureName) throws IOException {
     Path path = resourceShrinkerOutputForFeatures.get(featureName);
diff --git a/src/test/java/com/android/tools/r8/ToolHelper.java b/src/test/java/com/android/tools/r8/ToolHelper.java
index 395f2ce..a06500a 100644
--- a/src/test/java/com/android/tools/r8/ToolHelper.java
+++ b/src/test/java/com/android/tools/r8/ToolHelper.java
@@ -110,6 +110,29 @@
     return current + "/";
   }
 
+  private static String getBuildProp(String prop) {
+    assert prop.startsWith("BUILD_PROP_");
+    String value = System.getProperty(prop);
+    assert value != null;
+    return value;
+  }
+
+  public static List<Path> getBuildPropR8RuntimePath() {
+    return ListUtils.map(
+        StringUtils.split(getBuildProp("BUILD_PROP_R8_RUNTIME_PATH"), File.pathSeparatorChar),
+        Paths::get);
+  }
+
+  public static String getExamplesJava11BuildDir() {
+    assert System.getProperty("EXAMPLES_JAVA_11_JAVAC_BUILD_DIR") != null;
+    return System.getProperty("EXAMPLES_JAVA_11_JAVAC_BUILD_DIR");
+  }
+
+  public static Path getKeepAnnoPath() {
+    assert System.getProperty("KEEP_ANNO_JAVAC_BUILD_DIR") != null;
+    return Paths.get(System.getProperty("KEEP_ANNO_JAVAC_BUILD_DIR").split(File.pathSeparator)[0]);
+  }
+
   public enum TestDataSourceSet {
     LEGACY(null),
     TESTS_JAVA_8("tests_java_8/build/classes/java/test"),
@@ -171,29 +194,6 @@
   public static final String EXAMPLES_JAVA11_JAR_DIR = TESTS_BUILD_DIR + "examplesJava11/";
   public static final String SMALI_BUILD_DIR = THIRD_PARTY_DIR + "smali/";
 
-  public static String getExamplesJava11BuildDir() {
-    assert System.getProperty("EXAMPLES_JAVA_11_JAVAC_BUILD_DIR") != null;
-    return System.getProperty("EXAMPLES_JAVA_11_JAVAC_BUILD_DIR");
-  }
-
-  public static Path getR8MainPath() {
-    assert System.getProperty("R8_RUNTIME_PATH") != null;
-    return Paths.get(System.getProperty("R8_RUNTIME_PATH"));
-  }
-
-  public static Path getRetracePath() {
-    return getR8MainPath();
-  }
-
-  public static Path getKeepAnnoPath() {
-    assert System.getProperty("KEEP_ANNO_JAVAC_BUILD_DIR") != null;
-    return Paths.get(System.getProperty("KEEP_ANNO_JAVAC_BUILD_DIR").split(File.pathSeparator)[0]);
-  }
-
-  public static List<Path> getClasspathForR8() {
-    return ImmutableList.of(getKeepAnnoPath(), getR8MainPath());
-  }
-
   public static final Path CHECKED_IN_R8_17_WITH_DEPS =
       Paths.get(THIRD_PARTY_DIR).resolve("r8").resolve("r8_with_deps_17.jar");
 
diff --git a/src/test/java/com/android/tools/r8/androidresources/AndroidManifestWithCodeReferences.java b/src/test/java/com/android/tools/r8/androidresources/AndroidManifestWithCodeReferences.java
new file mode 100644
index 0000000..24cc249
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/androidresources/AndroidManifestWithCodeReferences.java
@@ -0,0 +1,100 @@
+// Copyright (c) 2024, 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.androidresources;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresentAndNotRenamed;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.androidresources.AndroidResourceTestingUtils.AndroidTestResource;
+import com.android.tools.r8.androidresources.AndroidResourceTestingUtils.AndroidTestResourceBuilder;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+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 AndroidManifestWithCodeReferences extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection parameters() {
+    return getTestParameters().withDefaultDexRuntime().withAllApiLevels().build();
+  }
+
+  public static String MANIFEST_WITH_CLASS_REFERENCE =
+      "<?xml version=\"1.0\" encoding=\"utf-8\"?>\n"
+          + "<manifest xmlns:android=\"http://schemas.android.com/apk/res/android\"\n"
+          + "    xmlns:tools=\"http://schemas.android.com/tools\""
+          + "    package=\"com.android.tools.r8\""
+          + ">\n"
+          + "    <application\n"
+          + "        android:label=\"@string/app_name\">\n"
+          + "      <activity\n"
+          + "            android:name=\""
+          + Bar.class.getTypeName()
+          + "\"\n"
+          + "            android:exported=\"true\">\n"
+          + "            <intent-filter>\n"
+          + "                <action android:name=\"android.intent.action.MAIN\" />\n"
+          + "\n"
+          + "                <category android:name=\"android.intent.category.LAUNCHER\" />\n"
+          + "            </intent-filter>\n"
+          + "        </activity>\n"
+          + "    </application>\n"
+          + "</manifest>";
+
+  public static AndroidTestResource getTestResources(TemporaryFolder temp) throws Exception {
+    return new AndroidTestResourceBuilder()
+        .withManifest(MANIFEST_WITH_CLASS_REFERENCE)
+        .addStringValue("app_name", "The one and only.")
+        .build(temp);
+  }
+
+  @Test
+  public void testManifestReferences() throws Exception {
+    testForR8(parameters.getBackend())
+        .setMinApi(parameters)
+        .addProgramClasses(Bar.class)
+        .addAndroidResources(getTestResources(temp))
+        .enableOptimizedShrinking()
+        .compile()
+        .inspectShrunkenResources(
+            resourceTableInspector -> {
+              resourceTableInspector.assertContainsResourceWithName("string", "app_name");
+            })
+        .inspect(
+            codeInspector -> {
+              ClassSubject barClass = codeInspector.clazz(Bar.class);
+              assertThat(barClass, isPresentAndNotRenamed());
+              // We should have two and only two methods, the two constructors.
+              assertEquals(barClass.allMethods(MethodSubject::isInstanceInitializer).size(), 2);
+              assertEquals(barClass.allMethods().size(), 2);
+            });
+  }
+
+  // Only referenced from Manifest file
+  public static class Bar {
+    public Bar() {
+      System.out.println("init");
+    }
+
+    public Bar(String x) {
+      System.out.println("init with string");
+    }
+
+    public void bar() {
+      System.out.println("never kept");
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/androidresources/AndroidResourceTestingUtils.java b/src/test/java/com/android/tools/r8/androidresources/AndroidResourceTestingUtils.java
index b4a170a..df7461e 100644
--- a/src/test/java/com/android/tools/r8/androidresources/AndroidResourceTestingUtils.java
+++ b/src/test/java/com/android/tools/r8/androidresources/AndroidResourceTestingUtils.java
@@ -532,8 +532,12 @@
     }
   }
 
-  public static void dumpWithAapt2(Path path) throws IOException {
-    System.out.println(ToolHelper.runAapt2("dump", "resources", path.toString()));
+  public static ProcessResult dumpWithAapt2(Path path) throws IOException {
+    return ToolHelper.runAapt2("dump", "resources", path.toString());
+  }
+
+  public static void dumpWithAapt2ToStdout(Path path) throws IOException {
+    System.out.println(dumpWithAapt2(path));
   }
 
   public static void compileWithAapt2(
diff --git a/src/test/java/com/android/tools/r8/androidresources/TestNameRemovalInResourceTable.java b/src/test/java/com/android/tools/r8/androidresources/TestNameRemovalInResourceTable.java
new file mode 100644
index 0000000..b9d73a0
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/androidresources/TestNameRemovalInResourceTable.java
@@ -0,0 +1,106 @@
+// Copyright (c) 2024, 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.androidresources;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.R8TestBuilder;
+import com.android.tools.r8.R8TestCompileResult;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.androidresources.AndroidResourceTestingUtils.AndroidTestResource;
+import com.android.tools.r8.androidresources.AndroidResourceTestingUtils.AndroidTestResourceBuilder;
+import com.android.tools.r8.utils.BooleanUtils;
+import java.util.List;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+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 TestNameRemovalInResourceTable extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameter(1)
+  public boolean optimized;
+
+  @Parameters(name = "{0}, optimized: {1}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        getTestParameters().withDefaultDexRuntime().withAllApiLevels().build(),
+        BooleanUtils.values());
+  }
+
+  public static AndroidTestResource getTestResources(TemporaryFolder temp) throws Exception {
+    return new AndroidTestResourceBuilder()
+        .withSimpleManifestAndAppNameString()
+        .addRClassInitializeWithDefaultValues(R.string.class, R.drawable.class)
+        .build(temp);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    R8TestCompileResult r8TestCompileResult =
+        testForR8(parameters.getBackend())
+            .setMinApi(parameters)
+            .addProgramClasses(FooBar.class)
+            .addAndroidResources(getTestResources(temp))
+            .applyIf(optimized, R8TestBuilder::enableOptimizedShrinking)
+            .addKeepMainRule(FooBar.class)
+            .compile();
+    r8TestCompileResult
+        .inspectShrunkenResources(
+            resourceTableInspector -> {
+              resourceTableInspector.assertContainsResourceWithName("string", "bar");
+              resourceTableInspector.assertContainsResourceWithName("string", "foo");
+              resourceTableInspector.assertContainsResourceWithName("drawable", "foobar");
+              resourceTableInspector.assertDoesNotContainResourceWithName(
+                  "string", "unused_string");
+              resourceTableInspector.assertDoesNotContainResourceWithName(
+                  "drawable", "unused_drawable");
+            })
+        .run(parameters.getRuntime(), FooBar.class)
+        .assertSuccess();
+    String dumpResources = r8TestCompileResult.dumpResources();
+    if (optimized) {
+      assertFalse(dumpResources.contains("unused_string"));
+      assertFalse(dumpResources.contains("unused_drawable"));
+    } else {
+      assertTrue(dumpResources.contains("unused_string"));
+      assertTrue(dumpResources.contains("unused_drawable"));
+    }
+  }
+
+  public static class FooBar {
+
+    public static void main(String[] args) {
+      if (System.currentTimeMillis() == 0) {
+        System.out.println(R.drawable.foobar);
+        System.out.println(R.string.bar);
+        System.out.println(R.string.foo);
+      }
+    }
+  }
+
+  public static class R {
+
+    public static class string {
+
+      public static int bar;
+      public static int foo;
+      public static int unused_string;
+    }
+
+    public static class drawable {
+
+      public static int foobar;
+      public static int unused_drawable;
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/compilerapi/CompilerApiTestCollection.java b/src/test/java/com/android/tools/r8/compilerapi/CompilerApiTestCollection.java
index fb86105..c50b238 100644
--- a/src/test/java/com/android/tools/r8/compilerapi/CompilerApiTestCollection.java
+++ b/src/test/java/com/android/tools/r8/compilerapi/CompilerApiTestCollection.java
@@ -114,7 +114,7 @@
   // The API tests always link against the classpath that the test runner is using.
   @Override
   public List<Path> getTargetClasspath() {
-    return ToolHelper.getClasspathForR8();
+    return ToolHelper.getBuildPropR8RuntimePath();
   }
 
   // Some tests expectations can depend on the lib/nonlib and internal/external behavior.
diff --git a/src/test/java/com/android/tools/r8/keepanno/CheckOptimizedOutAnnotationTest.java b/src/test/java/com/android/tools/r8/keepanno/CheckOptimizedOutAnnotationTest.java
index 59915bc9..656bb6b 100644
--- a/src/test/java/com/android/tools/r8/keepanno/CheckOptimizedOutAnnotationTest.java
+++ b/src/test/java/com/android/tools/r8/keepanno/CheckOptimizedOutAnnotationTest.java
@@ -10,6 +10,7 @@
 import static org.hamcrest.CoreMatchers.containsString;
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
 import static org.junit.Assume.assumeFalse;
 import static org.junit.Assume.assumeTrue;
@@ -54,12 +55,12 @@
   }
 
   @Test
-  public void testR8Native() throws Throwable {
-    assumeTrue(parameters.isR8() && parameters.isNative());
+  public void testCurrentR8() throws Throwable {
+    assumeTrue(parameters.isR8() && parameters.isCurrentR8());
     testForKeepAnno(parameters)
         .addProgramClasses(getInputClasses())
         .addKeepMainRule(TestClass.class)
-        .applyIfR8Native(
+        .applyIfR8Current(
             b ->
                 b.allowDiagnosticWarningMessages()
                     .setDiagnosticsLevelModifier(
@@ -86,8 +87,9 @@
   }
 
   @Test
-  public void testR8Extract() throws Throwable {
-    assumeTrue(parameters.isR8() && !parameters.isNative());
+  public void testLegacyR8() throws Throwable {
+    assumeTrue(parameters.isR8() && !parameters.isCurrentR8());
+    assertTrue(parameters.isLegacyR8());
     try {
       testForKeepAnno(parameters)
           .addProgramClasses(getInputClasses())
diff --git a/src/test/java/com/android/tools/r8/keepanno/CheckRemovedAnnotationTest.java b/src/test/java/com/android/tools/r8/keepanno/CheckRemovedAnnotationTest.java
index b3bedf1..4010ef8 100644
--- a/src/test/java/com/android/tools/r8/keepanno/CheckRemovedAnnotationTest.java
+++ b/src/test/java/com/android/tools/r8/keepanno/CheckRemovedAnnotationTest.java
@@ -10,6 +10,7 @@
 import static org.hamcrest.CoreMatchers.containsString;
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
 import static org.junit.Assume.assumeFalse;
 import static org.junit.Assume.assumeTrue;
@@ -53,12 +54,12 @@
   }
 
   @Test
-  public void testR8Native() throws Exception {
-    assumeTrue(parameters.isR8() && parameters.isNative());
+  public void testCurrentR8() throws Exception {
+    assumeTrue(parameters.isR8() && parameters.isCurrentR8());
     testForKeepAnno(parameters)
         .addProgramClasses(getInputClasses())
         .addKeepMainRule(TestClass.class)
-        .applyIfR8Native(
+        .applyIfR8Current(
             b ->
                 b.allowDiagnosticWarningMessages()
                     .setDiagnosticsLevelModifier(
@@ -89,8 +90,9 @@
   }
 
   @Test
-  public void testR8Extract() throws Throwable {
-    assumeTrue(parameters.isR8() && !parameters.isNative());
+  public void testLegacyR8() throws Throwable {
+    assumeTrue(parameters.isR8() && !parameters.isCurrentR8());
+    assertTrue(parameters.isLegacyR8());
     try {
       testForKeepAnno(parameters)
           .addProgramClasses(getInputClasses())
diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepAnnoParameters.java b/src/test/java/com/android/tools/r8/keepanno/KeepAnnoParameters.java
index 53c7634..04e7bf8 100644
--- a/src/test/java/com/android/tools/r8/keepanno/KeepAnnoParameters.java
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepAnnoParameters.java
@@ -13,7 +13,8 @@
   public enum KeepAnnoConfig {
     REFERENCE,
     R8_DIRECT,
-    R8_EXTRACT,
+    R8_NORMALIZED,
+    R8_RULES,
     R8_LEGACY,
     PG;
   }
@@ -56,21 +57,27 @@
   }
 
   public boolean isR8() {
-    return config == KeepAnnoConfig.R8_DIRECT
-        || config == KeepAnnoConfig.R8_EXTRACT
-        || config == KeepAnnoConfig.R8_LEGACY;
+    return isCurrentR8() || isLegacyR8();
   }
 
   public boolean isPG() {
     return config == KeepAnnoConfig.PG;
   }
 
-  public boolean isNative() {
-    return config == KeepAnnoConfig.R8_DIRECT || config == KeepAnnoConfig.R8_EXTRACT;
+  public boolean isCurrentR8() {
+    return isNativeR8() || config == KeepAnnoConfig.R8_RULES;
   }
 
-  public boolean isExtract() {
-    return config == KeepAnnoConfig.R8_EXTRACT
+  public boolean isLegacyR8() {
+    return config == KeepAnnoConfig.R8_LEGACY;
+  }
+
+  public boolean isNativeR8() {
+    return config == KeepAnnoConfig.R8_DIRECT || config == KeepAnnoConfig.R8_NORMALIZED;
+  }
+
+  public boolean isExtractRules() {
+    return config == KeepAnnoConfig.R8_RULES
         || config == KeepAnnoConfig.R8_LEGACY
         || config == KeepAnnoConfig.PG;
   }
diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBase.java b/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBase.java
index 86d9529..35c00ff 100644
--- a/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBase.java
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBase.java
@@ -22,7 +22,9 @@
       keepAnnoParams.add(
           new KeepAnnoParameters(parameters, KeepAnnoParameters.KeepAnnoConfig.R8_DIRECT));
       keepAnnoParams.add(
-          new KeepAnnoParameters(parameters, KeepAnnoParameters.KeepAnnoConfig.R8_EXTRACT));
+          new KeepAnnoParameters(parameters, KeepAnnoParameters.KeepAnnoConfig.R8_NORMALIZED));
+      keepAnnoParams.add(
+          new KeepAnnoParameters(parameters, KeepAnnoParameters.KeepAnnoConfig.R8_RULES));
       keepAnnoParams.add(
           new KeepAnnoParameters(parameters, KeepAnnoParameters.KeepAnnoConfig.R8_LEGACY));
       if (parameters.isCfRuntime()) {
diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBuilder.java b/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBuilder.java
index e9d6b40..1105bd3 100644
--- a/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBuilder.java
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBuilder.java
@@ -17,6 +17,7 @@
 import com.android.tools.r8.ThrowableConsumer;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.graph.ClassAccessFlags;
+import com.android.tools.r8.keepanno.KeepAnnoParameters.KeepAnnoConfig;
 import com.android.tools.r8.keepanno.asm.KeepEdgeReader;
 import com.android.tools.r8.keepanno.asm.KeepEdgeWriter;
 import com.android.tools.r8.keepanno.ast.KeepDeclaration;
@@ -41,9 +42,9 @@
       case REFERENCE:
         return new ReferenceBuilder(params, temp);
       case R8_DIRECT:
-        return new R8NativeBuilder(false, params, temp);
-      case R8_EXTRACT:
-        return new R8NativeBuilder(true, params, temp);
+      case R8_NORMALIZED:
+      case R8_RULES:
+        return new R8NativeBuilder(params, temp);
       case R8_LEGACY:
         return new R8LegacyBuilder(params, temp);
       case PG:
@@ -96,7 +97,7 @@
     return this;
   }
 
-  public KeepAnnoTestBuilder applyIfR8Native(ThrowableConsumer<R8TestBuilder<?>> builderConsumer) {
+  public KeepAnnoTestBuilder applyIfR8Current(ThrowableConsumer<R8TestBuilder<?>> builderConsumer) {
     return this;
   }
 
@@ -104,12 +105,16 @@
     return this;
   }
 
+  public KeepAnnoTestBuilder enableNativeInterpretation() {
+    return this;
+  }
+
   public final KeepAnnoTestBuilder setExcludedOuterClass(Class<?> clazz) {
     return applyIfPG(b -> b.addDontWarn(clazz));
   }
 
   public final KeepAnnoTestBuilder allowUnusedProguardConfigurationRules() {
-    return applyIfR8Native(R8TestBuilder::allowUnusedProguardConfigurationRules);
+    return applyIfR8Current(R8TestBuilder::allowUnusedProguardConfigurationRules);
   }
 
   public final KeepAnnoTestBuilder allowAccessModification() {
@@ -163,26 +168,44 @@
 
     private final R8FullTestBuilder builder;
     private List<Consumer<R8TestCompileResult>> compileResultConsumers = new ArrayList<>();
-    private final boolean useEdgeExtraction;
+    private final boolean normalizeEdges;
+    private final boolean extractRules;
 
-    private R8NativeBuilder(
-        boolean useEdgeExtraction, KeepAnnoParameters params, TemporaryFolder temp) {
+    private R8NativeBuilder(KeepAnnoParameters params, TemporaryFolder temp) {
       super(params, temp);
       builder =
           TestBase.testForR8(temp, parameters().getBackend())
               .enableExperimentalKeepAnnotations()
               .setMinApi(parameters());
-      this.useEdgeExtraction = useEdgeExtraction;
-      if (useEdgeExtraction) {
+      extractRules = params.config() == KeepAnnoConfig.R8_RULES;
+      normalizeEdges = params.config() == KeepAnnoConfig.R8_NORMALIZED;
+      if (normalizeEdges) {
         builder.getBuilder().setEnableExperimentalKeepAnnotations(false);
-        builder.getBuilder().setEnableExperimentalVersionedKeepEdgeAnnotations(true);
+        builder.getBuilder().setEnableExperimentalExtractedKeepAnnotations(true);
       } else {
         builder.getBuilder().setEnableExperimentalKeepAnnotations(true);
-        builder.getBuilder().setEnableExperimentalVersionedKeepEdgeAnnotations(false);
+        builder.getBuilder().setEnableExperimentalExtractedKeepAnnotations(false);
       }
     }
 
     @Override
+    public KeepAnnoTestBuilder enableNativeInterpretation() {
+      if (extractRules) {
+        return this;
+      }
+      // This enables native interpretation of all keep annotations.
+      builder.addOptionsModification(
+          o -> {
+            o.testing.enableExtractedKeepAnnotations = true;
+            o.testing.enableEmbeddedKeepAnnotations = true;
+          });
+      // This disables all reading of annotations in the command reader.
+      builder.getBuilder().setEnableExperimentalKeepAnnotations(false);
+      builder.getBuilder().setEnableExperimentalExtractedKeepAnnotations(false);
+      return this;
+    }
+
+    @Override
     public KeepAnnoTestBuilder applyIfR8(
         ThrowableConsumer<TestShrinkerBuilder<?, ?, ?, ?, ?>> builderConsumer) {
       builderConsumer.acceptWithRuntimeException(builder);
@@ -190,7 +213,7 @@
     }
 
     @Override
-    public KeepAnnoTestBuilder applyIfR8Native(
+    public KeepAnnoTestBuilder applyIfR8Current(
         ThrowableConsumer<R8TestBuilder<?>> builderConsumer) {
       builderConsumer.acceptWithRuntimeException(builder);
       return this;
@@ -222,7 +245,7 @@
 
     private void extractAndAdd(byte[] classFileData) {
       builder.addProgramClassFileData(classFileData);
-      if (useEdgeExtraction) {
+      if (normalizeEdges) {
         List<KeepDeclaration> declarations = KeepEdgeReader.readKeepEdges(classFileData);
         if (!declarations.isEmpty()) {
           String binaryName =
diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepEmptyClassTest.java b/src/test/java/com/android/tools/r8/keepanno/KeepEmptyClassTest.java
index c1e5683..a80be3c 100644
--- a/src/test/java/com/android/tools/r8/keepanno/KeepEmptyClassTest.java
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepEmptyClassTest.java
@@ -3,8 +3,11 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno;
 
+import static com.android.tools.r8.utils.codeinspector.Matchers.isAbsent;
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresentAndNotRenamed;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresentAndRenamed;
 import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.keepanno.annotations.KeepItemKind;
 import com.android.tools.r8.keepanno.annotations.KeepTarget;
@@ -13,6 +16,7 @@
 import com.android.tools.r8.transformers.ClassFileTransformer.MethodPredicate;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
 import com.google.common.collect.ImmutableList;
 import java.util.List;
@@ -37,6 +41,7 @@
   @Test
   public void test() throws Exception {
     testForKeepAnno(parameters)
+        .enableNativeInterpretation()
         .addProgramClasses(getInputClasses())
         .addProgramClassFileData(
             transformer(B.class).removeMethods(MethodPredicate.all()).transform())
@@ -52,6 +57,18 @@
 
   private void checkOutput(CodeInspector inspector) {
     assertThat(inspector.clazz(B.class), isPresentAndNotRenamed());
+    ClassSubject classA = inspector.clazz(A.class);
+    if (parameters.isNativeR8()) {
+      assertThat(classA, isAbsent());
+    } else {
+      assertTrue(parameters.isExtractRules());
+      // PG and R8 with keep rules will keep the residual class.
+      assertThat(classA, isPresentAndRenamed());
+      // R8 using keep rules will soft-pin the precondition method too.
+      assertThat(
+          classA.uniqueMethodWithOriginalName("foo"),
+          parameters.isPG() ? isAbsent() : isPresentAndRenamed());
+    }
   }
 
   static class A {
@@ -59,7 +76,7 @@
     // Pattern includes any members
     @UsesReflection(@KeepTarget(classConstant = B.class, kind = KeepItemKind.CLASS_AND_MEMBERS))
     public void foo() throws Exception {
-      String typeName = B.class.getTypeName();
+      String typeName = B.class.getName();
       int memberCount = B.class.getDeclaredMethods().length + B.class.getDeclaredFields().length;
       System.out.println(typeName.substring(typeName.length() - 1) + ", #members: " + memberCount);
     }
diff --git a/src/test/java/com/android/tools/r8/keepanno/utils/KeepAnnoMarkdownGenerator.java b/src/test/java/com/android/tools/r8/keepanno/utils/KeepAnnoMarkdownGenerator.java
index b543b8d..f79c36e 100644
--- a/src/test/java/com/android/tools/r8/keepanno/utils/KeepAnnoMarkdownGenerator.java
+++ b/src/test/java/com/android/tools/r8/keepanno/utils/KeepAnnoMarkdownGenerator.java
@@ -4,36 +4,44 @@
 
 package com.android.tools.r8.keepanno.utils;
 
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.ANNOTATION_PATTERN;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.FIELD_ACCESS_FLAGS;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.FIELD_ACCESS_VALUES;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.KEEP_BINDING;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.KEEP_CONDITION;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.KEEP_CONSTRAINT;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.KEEP_CONSTRAINT_VALUES;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.KEEP_EDGE;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.KEEP_FOR_API;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.KEEP_ITEM_KIND;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.KEEP_ITEM_KIND_VALUES;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.KEEP_TARGET;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.MEMBER_ACCESS_FLAGS;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.MEMBER_ACCESS_VALUES;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.METHOD_ACCESS_FLAGS;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.METHOD_ACCESS_VALUES;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.STRING_PATTERN;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.TYPE_PATTERN;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.USED_BY_NATIVE;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.USED_BY_REFLECTION;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.USES_REFLECTION;
 import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.quote;
+import static com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.simpleName;
 
 import com.android.tools.r8.ToolHelper;
-import com.android.tools.r8.keepanno.annotations.AnnotationPattern;
-import com.android.tools.r8.keepanno.annotations.FieldAccessFlags;
-import com.android.tools.r8.keepanno.annotations.KeepBinding;
-import com.android.tools.r8.keepanno.annotations.KeepCondition;
-import com.android.tools.r8.keepanno.annotations.KeepConstraint;
-import com.android.tools.r8.keepanno.annotations.KeepEdge;
-import com.android.tools.r8.keepanno.annotations.KeepForApi;
-import com.android.tools.r8.keepanno.annotations.KeepItemKind;
-import com.android.tools.r8.keepanno.annotations.KeepTarget;
-import com.android.tools.r8.keepanno.annotations.MemberAccessFlags;
-import com.android.tools.r8.keepanno.annotations.MethodAccessFlags;
-import com.android.tools.r8.keepanno.annotations.StringPattern;
-import com.android.tools.r8.keepanno.annotations.TypePattern;
-import com.android.tools.r8.keepanno.annotations.UsedByNative;
-import com.android.tools.r8.keepanno.annotations.UsedByReflection;
-import com.android.tools.r8.keepanno.annotations.UsesReflection;
 import com.android.tools.r8.keepanno.doctests.ForApiDocumentationTest;
 import com.android.tools.r8.keepanno.doctests.MainMethodsDocumentationTest;
 import com.android.tools.r8.keepanno.doctests.UsesReflectionAnnotationsDocumentationTest;
 import com.android.tools.r8.keepanno.doctests.UsesReflectionDocumentationTest;
+import com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.EnumReference;
 import com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.Generator;
+import com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.Group;
+import com.android.tools.r8.keepanno.utils.KeepItemAnnotationGenerator.GroupMember;
+import com.android.tools.r8.references.ClassReference;
 import com.android.tools.r8.utils.FileUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.google.common.collect.ImmutableMap;
 import java.io.IOException;
-import java.lang.reflect.Field;
-import java.lang.reflect.Method;
 import java.nio.charset.StandardCharsets;
 import java.nio.file.Path;
 import java.util.ArrayList;
@@ -78,26 +86,28 @@
 
   public KeepAnnoMarkdownGenerator(Generator generator) {
     this.generator = generator;
-    typeLinkReplacements =
-        getTypeLinkReplacements(
-            // Annotations.
-            KeepEdge.class,
-            KeepBinding.class,
-            KeepTarget.class,
-            KeepCondition.class,
-            UsesReflection.class,
-            UsedByReflection.class,
-            UsedByNative.class,
-            KeepForApi.class,
-            StringPattern.class,
-            TypePattern.class,
-            AnnotationPattern.class,
-            // Enums.
-            KeepConstraint.class,
-            KeepItemKind.class,
-            MemberAccessFlags.class,
-            MethodAccessFlags.class,
-            FieldAccessFlags.class);
+    ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
+    // Annotations.
+    addAnnotationReplacements(KEEP_EDGE, builder, generator.getKeepEdgeGroups());
+    addAnnotationReplacements(KEEP_BINDING, builder, generator.getBindingGroups());
+    addAnnotationReplacements(KEEP_TARGET, builder, generator.getTargetGroups());
+    addAnnotationReplacements(KEEP_CONDITION, builder, generator.getConditionGroups());
+    addAnnotationReplacements(USES_REFLECTION, builder, generator.getUsesReflectionGroups());
+    addAnnotationReplacements(USED_BY_REFLECTION, builder, generator.getUsedByReflectionGroups());
+    addAnnotationReplacements(USED_BY_NATIVE, builder, generator.getUsedByNativeGroups());
+    addAnnotationReplacements(KEEP_FOR_API, builder, generator.getKeepForApiGroups());
+    addAnnotationReplacements(STRING_PATTERN, builder, generator.getStringPatternGroups());
+    addAnnotationReplacements(TYPE_PATTERN, builder, generator.getTypePatternGroups());
+    addAnnotationReplacements(ANNOTATION_PATTERN, builder, generator.getAnnotationPatternGroups());
+
+    // Enums.
+    addEnumReplacements(KEEP_ITEM_KIND, KEEP_ITEM_KIND_VALUES, builder);
+    addEnumReplacements(KEEP_CONSTRAINT, KEEP_CONSTRAINT_VALUES, builder);
+    addEnumReplacements(MEMBER_ACCESS_FLAGS, MEMBER_ACCESS_VALUES, builder);
+    addEnumReplacements(METHOD_ACCESS_FLAGS, METHOD_ACCESS_VALUES, builder);
+    addEnumReplacements(FIELD_ACCESS_FLAGS, FIELD_ACCESS_VALUES, builder);
+
+    typeLinkReplacements = builder.build();
     populateCodeAndDocReplacements(
         UsesReflectionDocumentationTest.class,
         UsesReflectionAnnotationsDocumentationTest.class,
@@ -105,37 +115,51 @@
         MainMethodsDocumentationTest.class);
   }
 
-  private Map<String, String> getTypeLinkReplacements(Class<?>... classes) {
-    ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
-    for (Class<?> clazz : classes) {
-      String prefix = "`@" + clazz.getSimpleName();
-      String suffix = "`";
-      if (clazz.isAnnotation()) {
-        builder.put(prefix + suffix, getMdAnnotationLink(clazz));
-        for (Method method : clazz.getDeclaredMethods()) {
-          builder.put(
-              prefix + "#" + method.getName() + suffix, getMdAnnotationPropertyLink(method));
-        }
-      } else if (clazz.isEnum()) {
-        builder.put(prefix + suffix, getMdEnumLink(clazz));
-        for (Field field : clazz.getDeclaredFields()) {
-          builder.put(prefix + "#" + field.getName() + suffix, getMdEnumFieldLink(field));
-        }
-      } else {
-        throw new RuntimeException("Unexpected type of class for doc links");
+  private static String getPrefix(ClassReference annoType) {
+    return "`@" + simpleName(annoType);
+  }
+
+  private static String getSuffix() {
+    return "`";
+  }
+
+  private void addAnnotationReplacements(
+      ClassReference annoType, ImmutableMap.Builder<String, String> builder, List<Group> groups) {
+    String prefix = getPrefix(annoType);
+    String suffix = getSuffix();
+    builder.put(prefix + suffix, getMdAnnotationLink(annoType));
+    for (Group group : groups) {
+      for (GroupMember member : group.members) {
+        builder.put(
+            prefix + "#" + member.name + suffix, getMdAnnotationPropertyLink(annoType, member));
       }
     }
-    return builder.build();
+  }
+
+  private void addEnumReplacements(
+      ClassReference enumType,
+      List<EnumReference> enumMembers,
+      ImmutableMap.Builder<String, String> builder) {
+    String prefix = getPrefix(enumType);
+    String suffix = getSuffix();
+    builder.put(prefix + suffix, getMdEnumLink(enumType));
+    for (EnumReference enumMember : enumMembers) {
+      builder.put(prefix + "#" + enumMember.name() + suffix, getMdEnumMemberLink(enumMember));
+    }
   }
 
   private void populateCodeAndDocReplacements(Class<?>... classes) {
+    for (Class<?> clazz : classes) {
+      Path sourceFile = ToolHelper.getSourceFileForTestClass(clazz);
+      extractMarkers(sourceFile);
+    }
+  }
+
+  private void extractMarkers(Path sourceFile) {
     try {
-      for (Class<?> clazz : classes) {
-        Path sourceFile = ToolHelper.getSourceFileForTestClass(clazz);
-        String text = FileUtils.readTextFile(sourceFile, StandardCharsets.UTF_8);
-        extractMarkers(text, INCLUDE_DOC_START, INCLUDE_DOC_END, docReplacements);
-        extractMarkers(text, INCLUDE_CODE_START, INCLUDE_CODE_END, codeReplacements);
-      }
+      String text = FileUtils.readTextFile(sourceFile, StandardCharsets.UTF_8);
+      extractMarkers(text, INCLUDE_DOC_START, INCLUDE_DOC_END, docReplacements);
+      extractMarkers(text, INCLUDE_CODE_START, INCLUDE_CODE_END, codeReplacements);
     } catch (IOException e) {
       throw new RuntimeException(e);
     }
@@ -167,30 +191,29 @@
     }
   }
 
-  private static String getClassJavaDocUrl(Class<?> clazz) {
+  private static String getClassJavaDocUrl(ClassReference clazz) {
     return JAVADOC_URL + clazz.getTypeName().replace('.', '/') + ".html";
   }
 
-  private String getMdAnnotationLink(Class<?> clazz) {
-    return "[@" + clazz.getSimpleName() + "](" + getClassJavaDocUrl(clazz) + ")";
+  private String getMdAnnotationLink(ClassReference clazz) {
+    return "[@" + simpleName(clazz) + "](" + getClassJavaDocUrl(clazz) + ")";
   }
 
-  private String getMdAnnotationPropertyLink(Method method) {
-    Class<?> clazz = method.getDeclaringClass();
-    String methodName = method.getName();
+  private String getMdAnnotationPropertyLink(ClassReference clazz, GroupMember method) {
+    String methodName = method.name;
     String url = getClassJavaDocUrl(clazz) + "#" + methodName + "()";
-    return "[@" + clazz.getSimpleName() + "." + methodName + "](" + url + ")";
+    return "[@" + simpleName(clazz) + "." + methodName + "](" + url + ")";
   }
 
-  private String getMdEnumLink(Class<?> clazz) {
-    return "[" + clazz.getSimpleName() + "](" + getClassJavaDocUrl(clazz) + ")";
+  private String getMdEnumLink(ClassReference clazz) {
+    return "[" + simpleName(clazz) + "](" + getClassJavaDocUrl(clazz) + ")";
   }
 
-  private String getMdEnumFieldLink(Field field) {
-    Class<?> clazz = field.getDeclaringClass();
-    String fieldName = field.getName();
-    String url = getClassJavaDocUrl(clazz) + "#" + fieldName;
-    return "[" + clazz.getSimpleName() + "." + fieldName + "](" + url + ")";
+  private String getMdEnumMemberLink(EnumReference enumMember) {
+    ClassReference clazz = enumMember.enumClass;
+    String enumName = enumMember.name();
+    String url = getClassJavaDocUrl(clazz) + "#" + enumName;
+    return "[" + simpleName(clazz) + "." + enumName + "](" + url + ")";
   }
 
   private void println() {
diff --git a/src/test/java/com/android/tools/r8/keepanno/utils/KeepItemAnnotationGenerator.java b/src/test/java/com/android/tools/r8/keepanno/utils/KeepItemAnnotationGenerator.java
index 325960e..bb5de23 100644
--- a/src/test/java/com/android/tools/r8/keepanno/utils/KeepItemAnnotationGenerator.java
+++ b/src/test/java/com/android/tools/r8/keepanno/utils/KeepItemAnnotationGenerator.java
@@ -47,7 +47,7 @@
         });
   }
 
-  private static class EnumReference {
+  public static class EnumReference {
     public final ClassReference enumClass;
     public final String enumValue;
 
@@ -70,27 +70,25 @@
 
   private static final ClassReference ANNOTATION_CONSTANTS = astClass("AnnotationConstants");
 
-  private static final ClassReference STRING_PATTERN = annoClass("StringPattern");
-  private static final ClassReference TYPE_PATTERN = annoClass("TypePattern");
-  private static final ClassReference CLASS_NAME_PATTERN = annoClass("ClassNamePattern");
-  private static final ClassReference INSTANCE_OF_PATTERN = annoClass("InstanceOfPattern");
-  private static final ClassReference ANNOTATION_PATTERN = annoClass("AnnotationPattern");
-  private static final ClassReference USES_REFLECTION = annoClass("UsesReflection");
-  private static final ClassReference USED_BY_REFLECTION = annoClass("UsedByReflection");
-  private static final ClassReference USED_BY_NATIVE = annoClass("UsedByNative");
-  private static final ClassReference CHECK_REMOVED = annoClass("CheckRemoved");
-  private static final ClassReference CHECK_OPTIMIZED_OUT = annoClass("CheckOptimizedOut");
-  private static final ClassReference EXTRACTED_KEEP_ANNOTATIONS =
-      annoClass("ExtractedKeepAnnotations");
-  private static final ClassReference EXTRACTED_KEEP_ANNOTATION =
-      annoClass("ExtractedKeepAnnotation");
-  private static final ClassReference KEEP_EDGE = annoClass("KeepEdge");
-  private static final ClassReference KEEP_BINDING = annoClass("KeepBinding");
-  private static final ClassReference KEEP_TARGET = annoClass("KeepTarget");
-  private static final ClassReference KEEP_CONDITION = annoClass("KeepCondition");
-  private static final ClassReference KEEP_FOR_API = annoClass("KeepForApi");
+  static final ClassReference STRING_PATTERN = annoClass("StringPattern");
+  static final ClassReference TYPE_PATTERN = annoClass("TypePattern");
+  static final ClassReference CLASS_NAME_PATTERN = annoClass("ClassNamePattern");
+  static final ClassReference INSTANCE_OF_PATTERN = annoClass("InstanceOfPattern");
+  static final ClassReference ANNOTATION_PATTERN = annoClass("AnnotationPattern");
+  static final ClassReference USES_REFLECTION = annoClass("UsesReflection");
+  static final ClassReference USED_BY_REFLECTION = annoClass("UsedByReflection");
+  static final ClassReference USED_BY_NATIVE = annoClass("UsedByNative");
+  static final ClassReference CHECK_REMOVED = annoClass("CheckRemoved");
+  static final ClassReference CHECK_OPTIMIZED_OUT = annoClass("CheckOptimizedOut");
+  static final ClassReference EXTRACTED_KEEP_ANNOTATIONS = annoClass("ExtractedKeepAnnotations");
+  static final ClassReference EXTRACTED_KEEP_ANNOTATION = annoClass("ExtractedKeepAnnotation");
+  static final ClassReference KEEP_EDGE = annoClass("KeepEdge");
+  static final ClassReference KEEP_BINDING = annoClass("KeepBinding");
+  static final ClassReference KEEP_TARGET = annoClass("KeepTarget");
+  static final ClassReference KEEP_CONDITION = annoClass("KeepCondition");
+  static final ClassReference KEEP_FOR_API = annoClass("KeepForApi");
 
-  private static final ClassReference KEEP_ITEM_KIND = annoClass("KeepItemKind");
+  public static final ClassReference KEEP_ITEM_KIND = annoClass("KeepItemKind");
   private static final EnumReference KIND_ONLY_CLASS = enumRef(KEEP_ITEM_KIND, "ONLY_CLASS");
   private static final EnumReference KIND_ONLY_MEMBERS = enumRef(KEEP_ITEM_KIND, "ONLY_MEMBERS");
   private static final EnumReference KIND_ONLY_METHODS = enumRef(KEEP_ITEM_KIND, "ONLY_METHODS");
@@ -101,7 +99,7 @@
       enumRef(KEEP_ITEM_KIND, "CLASS_AND_METHODS");
   private static final EnumReference KIND_CLASS_AND_FIELDS =
       enumRef(KEEP_ITEM_KIND, "CLASS_AND_FIELDS");
-  private static final List<EnumReference> KEEP_ITEM_KIND_VALUES =
+  public static final List<EnumReference> KEEP_ITEM_KIND_VALUES =
       ImmutableList.of(
           KIND_ONLY_CLASS,
           KIND_ONLY_MEMBERS,
@@ -111,7 +109,7 @@
           KIND_CLASS_AND_METHODS,
           KIND_CLASS_AND_FIELDS);
 
-  private static final ClassReference KEEP_CONSTRAINT = annoClass("KeepConstraint");
+  static final ClassReference KEEP_CONSTRAINT = annoClass("KeepConstraint");
   private static final EnumReference CONSTRAINT_LOOKUP = enumRef(KEEP_CONSTRAINT, "LOOKUP");
   private static final EnumReference CONSTRAINT_NAME = enumRef(KEEP_CONSTRAINT, "NAME");
   private static final EnumReference CONSTRAINT_VISIBILITY_RELAX =
@@ -134,7 +132,7 @@
       enumRef(KEEP_CONSTRAINT, "NEVER_INLINE");
   private static final EnumReference CONSTRAINT_CLASS_OPEN_HIERARCHY =
       enumRef(KEEP_CONSTRAINT, "CLASS_OPEN_HIERARCHY");
-  private static final List<EnumReference> KEEP_CONSTRAINT_VALUES =
+  static final List<EnumReference> KEEP_CONSTRAINT_VALUES =
       ImmutableList.of(
           CONSTRAINT_LOOKUP,
           CONSTRAINT_NAME,
@@ -150,7 +148,7 @@
           CONSTRAINT_NEVER_INLINE,
           CONSTRAINT_CLASS_OPEN_HIERARCHY);
 
-  private static final ClassReference MEMBER_ACCESS_FLAGS = annoClass("MemberAccessFlags");
+  static final ClassReference MEMBER_ACCESS_FLAGS = annoClass("MemberAccessFlags");
   private static final EnumReference MEMBER_ACCESS_PUBLIC = enumRef(MEMBER_ACCESS_FLAGS, "PUBLIC");
   private static final EnumReference MEMBER_ACCESS_PROTECTED =
       enumRef(MEMBER_ACCESS_FLAGS, "PROTECTED");
@@ -162,7 +160,7 @@
   private static final EnumReference MEMBER_ACCESS_FINAL = enumRef(MEMBER_ACCESS_FLAGS, "FINAL");
   private static final EnumReference MEMBER_ACCESS_SYNTHETIC =
       enumRef(MEMBER_ACCESS_FLAGS, "SYNTHETIC");
-  private static final List<EnumReference> MEMBER_ACCESS_VALUES =
+  static final List<EnumReference> MEMBER_ACCESS_VALUES =
       ImmutableList.of(
           MEMBER_ACCESS_PUBLIC,
           MEMBER_ACCESS_PROTECTED,
@@ -172,7 +170,7 @@
           MEMBER_ACCESS_FINAL,
           MEMBER_ACCESS_SYNTHETIC);
 
-  private static final ClassReference METHOD_ACCESS_FLAGS = annoClass("MethodAccessFlags");
+  static final ClassReference METHOD_ACCESS_FLAGS = annoClass("MethodAccessFlags");
   private static final EnumReference METHOD_ACCESS_SYNCHRONIZED =
       enumRef(METHOD_ACCESS_FLAGS, "SYNCHRONIZED");
   private static final EnumReference METHOD_ACCESS_BRIDGE = enumRef(METHOD_ACCESS_FLAGS, "BRIDGE");
@@ -181,7 +179,7 @@
       enumRef(METHOD_ACCESS_FLAGS, "ABSTRACT");
   private static final EnumReference METHOD_ACCESS_STRICT_FP =
       enumRef(METHOD_ACCESS_FLAGS, "STRICT_FP");
-  private static final List<EnumReference> METHOD_ACCESS_VALUES =
+  static final List<EnumReference> METHOD_ACCESS_VALUES =
       ImmutableList.of(
           METHOD_ACCESS_SYNCHRONIZED,
           METHOD_ACCESS_BRIDGE,
@@ -189,12 +187,12 @@
           METHOD_ACCESS_ABSTRACT,
           METHOD_ACCESS_STRICT_FP);
 
-  private static final ClassReference FIELD_ACCESS_FLAGS = annoClass("FieldAccessFlags");
+  static final ClassReference FIELD_ACCESS_FLAGS = annoClass("FieldAccessFlags");
   private static final EnumReference FIELD_ACCESS_VOLATILE =
       enumRef(FIELD_ACCESS_FLAGS, "VOLATILE");
   private static final EnumReference FIELD_ACCESS_TRANSIENT =
       enumRef(FIELD_ACCESS_FLAGS, "TRANSIENT");
-  private static final List<EnumReference> FIELD_ACCESS_VALUES =
+  static final List<EnumReference> FIELD_ACCESS_VALUES =
       ImmutableList.of(FIELD_ACCESS_VOLATILE, FIELD_ACCESS_TRANSIENT);
 
   private static final String DEFAULT_INVALID_STRING_PATTERN =
@@ -222,12 +220,12 @@
     return "\"" + str + "\"";
   }
 
-  private static String simpleName(ClassReference clazz) {
+  public static String simpleName(ClassReference clazz) {
     String binaryName = clazz.getBinaryName();
     return binaryName.substring(binaryName.lastIndexOf('/') + 1);
   }
 
-  private static class GroupMember extends DocPrinterBase<GroupMember> {
+  public static class GroupMember extends DocPrinterBase<GroupMember> {
 
     final String name;
     String valueType = null;
@@ -310,7 +308,7 @@
     }
   }
 
-  private static class Group {
+  public static class Group {
 
     final String name;
     final List<GroupMember> members = new ArrayList<>();
@@ -565,7 +563,7 @@
                   .defaultEmptyString());
     }
 
-    private Group typePatternGroup() {
+    public Group typePatternGroup() {
       return new Group("type-pattern")
           .addMember(
               new GroupMember("name")
@@ -1699,6 +1697,11 @@
       println("}");
     }
 
+    void generateGroupConstants(ClassReference annoType, List<Group> groups) {
+      generateAnnotationConstants(annoType);
+      groups.forEach(g -> g.generateConstants(this));
+    }
+
     private void generateAnnotationConstants(ClassReference clazz) {
       String desc = clazz.getDescriptor();
       println("public static final String DESCRIPTOR = " + quote(desc) + ";");
@@ -1747,59 +1750,77 @@
       println();
     }
 
+    List<Group> getKeepEdgeGroups() {
+      return ImmutableList.of(
+          createDescriptionGroup(),
+          createBindingsGroup(),
+          createPreconditionsGroup(),
+          createConsequencesGroup());
+    }
+
     private void generateKeepEdgeConstants() {
       println("public static final class Edge {");
-      withIndent(
-          () -> {
-            generateAnnotationConstants(KEEP_EDGE);
-            createDescriptionGroup().generateConstants(this);
-            createBindingsGroup().generateConstants(this);
-            createPreconditionsGroup().generateConstants(this);
-            createConsequencesGroup().generateConstants(this);
-          });
+      withIndent(() -> generateGroupConstants(KEEP_EDGE, getKeepEdgeGroups()));
       println("}");
       println();
     }
 
+    List<Group> getKeepForApiGroups() {
+      return ImmutableList.of(
+          createDescriptionGroup(), createAdditionalTargetsGroup("."), createMemberAccessGroup());
+    }
+
     private void generateKeepForApiConstants() {
       println("public static final class ForApi {");
-      withIndent(
-          () -> {
-            generateAnnotationConstants(KEEP_FOR_API);
-            createDescriptionGroup().generateConstants(this);
-            createAdditionalTargetsGroup(".").generateConstants(this);
-            createMemberAccessGroup().generateConstants(this);
-          });
+      withIndent(() -> generateGroupConstants(KEEP_FOR_API, getKeepForApiGroups()));
       println("}");
       println();
     }
 
+    List<Group> getUsesReflectionGroups() {
+      return ImmutableList.of(
+          createDescriptionGroup(),
+          createConsequencesAsValueGroup(),
+          createAdditionalPreconditionsGroup());
+    }
+
     private void generateUsesReflectionConstants() {
       println("public static final class UsesReflection {");
-      withIndent(
-          () -> {
-            generateAnnotationConstants(USES_REFLECTION);
-            createDescriptionGroup().generateConstants(this);
-            createConsequencesAsValueGroup().generateConstants(this);
-            createAdditionalPreconditionsGroup().generateConstants(this);
-          });
+      withIndent(() -> generateGroupConstants(USES_REFLECTION, getUsesReflectionGroups()));
       println("}");
       println();
     }
 
+    List<Group> getUsedByReflectionGroups() {
+      ImmutableList.Builder<Group> builder = ImmutableList.builder();
+      builder.addAll(getItemGroups());
+      builder.add(getKindGroup());
+      forEachExtraUsedByReflectionGroup(builder::add);
+      forEachKeepConstraintGroups(builder::add);
+      return builder.build();
+    }
+
+    private void forEachExtraUsedByReflectionGroup(Consumer<Group> fn) {
+      fn.accept(createDescriptionGroup());
+      fn.accept(createPreconditionsGroup());
+      fn.accept(createAdditionalTargetsGroup("."));
+    }
+
     private void generateUsedByReflectionConstants() {
       println("public static final class UsedByReflection {");
       withIndent(
           () -> {
             generateAnnotationConstants(USED_BY_REFLECTION);
-            createDescriptionGroup().generateConstants(this);
-            createPreconditionsGroup().generateConstants(this);
-            createAdditionalTargetsGroup(".").generateConstants(this);
+            forEachExtraUsedByReflectionGroup(g -> g.generateConstants(this));
           });
       println("}");
       println();
     }
 
+    List<Group> getUsedByNativeGroups() {
+      return getUsedByReflectionGroups();
+    }
+
     private void generateUsedByNativeConstants() {
       println("public static final class UsedByNative {");
       withIndent(
@@ -1831,39 +1852,48 @@
       println();
     }
 
+    private List<Group> getItemGroups() {
+      return ImmutableList.of(
+          // Bindings.
+          createClassBindingGroup(),
+          createMemberBindingGroup(),
+          // Classes.
+          createClassNamePatternGroup(),
+          createClassInstanceOfPatternGroup(),
+          createClassAnnotatedByPatternGroup(),
+          // Members.
+          createMemberAnnotatedByGroup(),
+          createMemberAccessGroup(),
+          // Methods.
+          createMethodAnnotatedByGroup(),
+          createMethodAccessGroup(),
+          createMethodNameGroup(),
+          createMethodReturnTypeGroup(),
+          createMethodParametersGroup(),
+          // Fields.
+          createFieldAnnotatedByGroup(),
+          createFieldAccessGroup(),
+          createFieldNameGroup(),
+          createFieldTypeGroup());
+    }
+
     private void generateItemConstants() {
       DocPrinter.printer()
           .setDocTitle("Item properties common to binding items, conditions and targets.")
           .printDoc(this::println);
       println("public static final class Item {");
-      withIndent(
-          () -> {
-            // Bindings.
-            createClassBindingGroup().generateConstants(this);
-            createMemberBindingGroup().generateConstants(this);
-            // Classes.
-            createClassNamePatternGroup().generateConstants(this);
-            createClassInstanceOfPatternGroup().generateConstants(this);
-            createClassAnnotatedByPatternGroup().generateConstants(this);
-            // Members.
-            createMemberAnnotatedByGroup().generateConstants(this);
-            createMemberAccessGroup().generateConstants(this);
-            // Methods.
-            createMethodAnnotatedByGroup().generateConstants(this);
-            createMethodAccessGroup().generateConstants(this);
-            createMethodNameGroup().generateConstants(this);
-            createMethodReturnTypeGroup().generateConstants(this);
-            createMethodParametersGroup().generateConstants(this);
-            // Fields.
-            createFieldAnnotatedByGroup().generateConstants(this);
-            createFieldAccessGroup().generateConstants(this);
-            createFieldNameGroup().generateConstants(this);
-            createFieldTypeGroup().generateConstants(this);
-          });
+      withIndent(() -> getItemGroups().forEach(g -> g.generateConstants(this)));
       println("}");
       println();
     }
 
+    List<Group> getBindingGroups() {
+      return ImmutableList.<Group>builder()
+          .addAll(getItemGroups())
+          .add(new Group("binding-name").addMember(bindingName()))
+          .build();
+    }
+
     private void generateBindingConstants() {
       println("public static final class Binding {");
       withIndent(
@@ -1875,6 +1905,10 @@
       println();
     }
 
+    List<Group> getConditionGroups() {
+      return getItemGroups();
+    }
+
     private void generateConditionConstants() {
       println("public static final class Condition {");
       withIndent(
@@ -1885,13 +1919,24 @@
       println();
     }
 
+    List<Group> getTargetGroups() {
+      ImmutableList.Builder<Group> builder = ImmutableList.builder();
+      builder.addAll(getItemGroups());
+      forEachExtraTargetGroup(builder::add);
+      return builder.build();
+    }
+
+    private void forEachExtraTargetGroup(Consumer<Group> fn) {
+      fn.accept(getKindGroup());
+      forEachKeepConstraintGroups(fn);
+    }
+
     private void generateTargetConstants() {
       println("public static final class Target {");
       withIndent(
           () -> {
             generateAnnotationConstants(KEEP_TARGET);
-            getKindGroup().generateConstants(this);
-            forEachKeepConstraintGroups(g -> g.generateConstants(this));
+            forEachExtraTargetGroup(g -> g.generateConstants(this));
           });
       println("}");
       println();
@@ -1997,25 +2042,32 @@
       println();
     }
 
+    List<Group> getStringPatternGroups() {
+      return ImmutableList.of(
+          stringPatternExactGroup(), stringPatternPrefixGroup(), stringPatternSuffixGroup());
+    }
+
     private void generateStringPatternConstants() {
       println("public static final class StringPattern {");
       withIndent(
           () -> {
             generateAnnotationConstants(STRING_PATTERN);
-            stringPatternExactGroup().generateConstants(this);
-            stringPatternPrefixGroup().generateConstants(this);
-            stringPatternSuffixGroup().generateConstants(this);
+            getStringPatternGroups().forEach(g -> g.generateConstants(this));
           });
       println("}");
       println();
     }
 
+    List<Group> getTypePatternGroups() {
+      return ImmutableList.of(typePatternGroup());
+    }
+
     private void generateTypePatternConstants() {
       println("public static final class TypePattern {");
       withIndent(
           () -> {
             generateAnnotationConstants(TYPE_PATTERN);
-            typePatternGroup().generateConstants(this);
+            getTypePatternGroups().forEach(g -> g.generateConstants((this)));
           });
       println("}");
       println();
@@ -2046,13 +2098,17 @@
       println();
     }
 
+    List<Group> getAnnotationPatternGroups() {
+      return ImmutableList.of(
+          annotationNameGroup(), new Group("retention").addMember(annotationRetention()));
+    }
+
     private void generateAnnotationPatternConstants() {
       println("public static final class AnnotationPattern {");
       withIndent(
           () -> {
             generateAnnotationConstants(ANNOTATION_PATTERN);
-            annotationNameGroup().generateConstants(this);
-            annotationRetention().generateConstants(this);
+            getAnnotationPatternGroups().forEach(g -> g.generateConstants(this));
           });
       println("}");
       println();
diff --git a/src/test/java/com/android/tools/r8/retrace/RetraceCommandLineTests.java b/src/test/java/com/android/tools/r8/retrace/RetraceCommandLineTests.java
index 2bc2ff9..2260cb6 100644
--- a/src/test/java/com/android/tools/r8/retrace/RetraceCommandLineTests.java
+++ b/src/test/java/com/android/tools/r8/retrace/RetraceCommandLineTests.java
@@ -346,7 +346,7 @@
       command.add(ToolHelper.getSystemJavaExecutable());
       command.add("-ea");
       command.add("-cp");
-      command.add(ToolHelper.getRetracePath().toString());
+      command.add(RetraceTests.getRetraceClasspath());
       command.add(mainEntryPointExternal);
       command.addAll(args);
       ProcessBuilder builder = new ProcessBuilder(command);
diff --git a/src/test/java/com/android/tools/r8/retrace/RetraceTests.java b/src/test/java/com/android/tools/r8/retrace/RetraceTests.java
index 95c8b5b..7212797 100644
--- a/src/test/java/com/android/tools/r8/retrace/RetraceTests.java
+++ b/src/test/java/com/android/tools/r8/retrace/RetraceTests.java
@@ -90,6 +90,7 @@
 import com.android.tools.r8.utils.BooleanUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.google.common.collect.ImmutableList;
+import java.io.File;
 import java.nio.charset.StandardCharsets;
 import java.nio.file.Files;
 import java.nio.file.Path;
@@ -515,6 +516,10 @@
     return runRetraceTest(stackTraceForTest, true);
   }
 
+  public static String getRetraceClasspath() {
+    return StringUtils.join(File.pathSeparator, ToolHelper.getBuildPropR8RuntimePath());
+  }
+
   private TestDiagnosticMessagesImpl runRetraceTest(
       StackTraceForTest stackTraceForTest, boolean allowExperimentalMapping) throws Exception {
     String expectedStackTrace =
@@ -541,7 +546,7 @@
       command.add(parameters.getRuntime().asCf().getJavaExecutable().toString());
       command.add("-ea");
       command.add("-cp");
-      command.add(ToolHelper.getRetracePath().toString());
+      command.add(getRetraceClasspath());
       if (allowExperimentalMapping) {
         command.add("-Dcom.android.tools.r8.experimentalmapping");
       }
diff --git a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiTestCollection.java b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiTestCollection.java
index 36aa7ce..ccee173 100644
--- a/src/test/java/com/android/tools/r8/retrace/api/RetraceApiTestCollection.java
+++ b/src/test/java/com/android/tools/r8/retrace/api/RetraceApiTestCollection.java
@@ -63,7 +63,7 @@
 
   @Override
   public List<Path> getTargetClasspath() {
-    return ImmutableList.of(ToolHelper.getRetracePath());
+    return ToolHelper.getBuildPropR8RuntimePath();
   }
 
   @Override