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/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/lightir/LirCode.java b/src/main/java/com/android/tools/r8/lightir/LirCode.java
index 5090346..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;
     }
@@ -586,8 +598,10 @@
   public void registerCodeReferences(ProgramMethod method, UseRegistry registry) {
     assert registry.getTraversalContinuation().shouldContinue();
     for (PositionEntry positionEntry : positionTable) {
-      if (positionEntry instanceof StructuredPositionEntry) {
-        registry.registerInliningPosition(((StructuredPositionEntry) positionEntry).position);
+      if (positionEntry.hasCallerPosition()) {
+        registry.registerInliningPosition(
+            positionEntry.getPosition(
+                method.getReference(), method.getDefinition().isD8R8Synthesized()));
       }
     }
     LirUseRegistryCallback<EV> registryCallbacks = new LirUseRegistryCallback<>(this, registry);
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 1d2e7b8..760cede 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;
@@ -153,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;
@@ -290,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
@@ -3797,17 +3799,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()
@@ -3820,6 +3823,7 @@
               this::applyMinimumKeepInfoWhenLiveOrTargeted);
       timing.end();
     }
+    timing.time("Unconditional rules", () -> applicableRules.evaluateUnconditionalRules(this));
     timing.begin("Enqueue all");
     enqueueAllIfNotShrinking();
     timing.end();
@@ -3867,6 +3871,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 =
@@ -4433,6 +4445,8 @@
               : ImmutableSet.of(syntheticClass.getType());
         };
     amendKeepInfoWithCompanionMethods();
+    keepInfo.setMaterializedRules(applicableRules.getMaterializedRules());
+
     timing.begin("Rewrite with deferred results");
     deferredTracing.rewriteApplication(executorService);
     timing.end();
@@ -4620,6 +4634,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) {
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/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/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBuilder.java b/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBuilder.java
index e9d6b40..9a3c1e8 100644
--- a/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBuilder.java
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBuilder.java
@@ -104,6 +104,10 @@
     return this;
   }
 
+  public KeepAnnoTestBuilder enableNativeInterpretation() {
+    return this;
+  }
+
   public final KeepAnnoTestBuilder setExcludedOuterClass(Class<?> clazz) {
     return applyIfPG(b -> b.addDontWarn(clazz));
   }
@@ -175,14 +179,25 @@
       this.useEdgeExtraction = useEdgeExtraction;
       if (useEdgeExtraction) {
         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 (useEdgeExtraction) {
+        // This enables native interpretation of the extracted edges.
+        builder.addOptionsModification(o -> o.testing.enableExtractedKeepAnnotations = true);
+        // This disables converting the extracted edges to PG rules in the command reader.
+        builder.getBuilder().setEnableExperimentalExtractedKeepAnnotations(false);
+      }
+      return this;
+    }
+
+    @Override
     public KeepAnnoTestBuilder applyIfR8(
         ThrowableConsumer<TestShrinkerBuilder<?, ?, ?, ?, ?>> builderConsumer) {
       builderConsumer.acceptWithRuntimeException(builder);
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..44306ed 100644
--- a/src/test/java/com/android/tools/r8/keepanno/KeepEmptyClassTest.java
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepEmptyClassTest.java
@@ -37,6 +37,7 @@
   @Test
   public void test() throws Exception {
     testForKeepAnno(parameters)
+        .enableNativeInterpretation()
         .addProgramClasses(getInputClasses())
         .addProgramClassFileData(
             transformer(B.class).removeMethods(MethodPredicate.all()).transform())