diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index dbe1572..06fb565 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -313,7 +313,10 @@
                         options.getProguardConfiguration().getRules(), synthesizedProguardRules))
                 .run(executorService));
 
-        AppView<AppInfoWithLiveness> appViewWithLiveness = runEnqueuer(executorService, appView);
+        AnnotationRemover.Builder annotationRemoverBuilder =
+            options.isShrinking() ? AnnotationRemover.builder() : null;
+        AppView<AppInfoWithLiveness> appViewWithLiveness =
+            runEnqueuer(annotationRemoverBuilder, executorService, appView);
         assert appView.rootSet().verifyKeptFieldsAreAccessedAndLive(appViewWithLiveness.appInfo());
         assert appView.rootSet().verifyKeptMethodsAreTargetedAndLive(appViewWithLiveness.appInfo());
         assert appView.rootSet().verifyKeptTypesAreLive(appViewWithLiveness.appInfo());
@@ -352,14 +355,15 @@
                       pruner.getMethodsToKeepForConfigurationDebugging()));
           appView.setAppServices(appView.appServices().prunedCopy(pruner.getRemovedClasses()));
           new AbstractMethodRemover(appView.appInfo().withLiveness()).run();
+
+          AnnotationRemover annotationRemover =
+              annotationRemoverBuilder
+                  .computeClassesToRetainInnerClassAttributeFor(appViewWithLiveness)
+                  .build(appViewWithLiveness);
+          annotationRemover.ensureValid().run();
+          classesToRetainInnerClassAttributeFor =
+              annotationRemover.getClassesToRetainInnerClassAttributeFor();
         }
-
-        classesToRetainInnerClassAttributeFor =
-            AnnotationRemover.computeClassesToRetainInnerClassAttributeFor(appView.withLiveness());
-        new AnnotationRemover(appView.withLiveness(), classesToRetainInnerClassAttributeFor)
-            .ensureValid()
-            .run();
-
       } finally {
         timing.end();
       }
@@ -658,7 +662,9 @@
 
             // Remove annotations that refer to types that no longer exist.
             assert classesToRetainInnerClassAttributeFor != null;
-            new AnnotationRemover(appView.withLiveness(), classesToRetainInnerClassAttributeFor)
+            AnnotationRemover.builder()
+                .setClassesToRetainInnerClassAttributeFor(classesToRetainInnerClassAttributeFor)
+                .build(appView.withLiveness())
                 .run();
             if (!mainDexClasses.isEmpty()) {
               // Remove types that no longer exists from the computed main dex list.
@@ -800,10 +806,13 @@
     }
   }
 
-  private AppView<AppInfoWithLiveness> runEnqueuer(ExecutorService executorService,
-      AppView<AppInfoWithSubtyping> appView) throws ExecutionException {
+  private AppView<AppInfoWithLiveness> runEnqueuer(
+      AnnotationRemover.Builder annotationRemoverBuilder,
+      ExecutorService executorService,
+      AppView<AppInfoWithSubtyping> appView)
+      throws ExecutionException {
     Enqueuer enqueuer = EnqueuerFactory.createForInitialTreeShaking(appView);
-
+    enqueuer.setAnnotationRemoverBuilder(annotationRemoverBuilder);
     if (appView.options().enableInitializedClassesInInstanceMethodsAnalysis) {
       enqueuer.registerAnalysis(new InitializedClassesInInstanceMethodsAnalysis(appView));
     }
diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 53d04aa..1c15adc 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "2.0.39";
+  public static final String LABEL = "2.0.40";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java
index 7d63446..4040acd 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -8,6 +8,8 @@
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.kotlin.KotlinInfo;
 import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.shaking.AnnotationRemover;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.OptionalBool;
 import com.android.tools.r8.utils.PredicateUtils;
@@ -401,6 +403,11 @@
     setVirtualMethods(newVirtualMethods);
   }
 
+  public DexAnnotationSet liveAnnotations(AppView<AppInfoWithLiveness> appView) {
+    return annotations.keepIf(
+        annotation -> AnnotationRemover.shouldKeepAnnotation(appView, this, annotation));
+  }
+
   /**
    * For all annotations on the class and all annotations on its methods and fields apply the
    * specified consumer.
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index 41506ec..dd4e2c5 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -62,6 +62,8 @@
 import com.android.tools.r8.naming.MemberNaming.Signature;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.shaking.AnnotationRemover;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.OptionalBool;
 import com.android.tools.r8.utils.Pair;
@@ -256,6 +258,16 @@
     assert parameterAnnotationsList != null;
   }
 
+  public DexAnnotationSet liveAnnotations(AppView<AppInfoWithLiveness> appView) {
+    return annotations.keepIf(
+        annotation -> AnnotationRemover.shouldKeepAnnotation(appView, this, annotation));
+  }
+
+  public ParameterAnnotationsList liveParameterAnnotations(AppView<AppInfoWithLiveness> appView) {
+    return parameterAnnotationsList.keepIf(
+        annotation -> AnnotationRemover.shouldKeepAnnotation(appView, this, annotation));
+  }
+
   public OptionalBool isLibraryMethodOverride() {
     return isNonPrivateVirtualMethod() ? isLibraryMethodOverride : OptionalBool.FALSE;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
index a5e9d5c4..1450e78 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
@@ -241,8 +241,7 @@
         .forEachOrdered(
             lambda -> {
               try {
-                LambdaGroupId id =
-                    KotlinLambdaGroupIdFactory.create(kotlin, lambda, appView.options());
+                LambdaGroupId id = KotlinLambdaGroupIdFactory.create(appView, kotlin, lambda);
                 LambdaGroup group = groups.computeIfAbsent(id, LambdaGroupId::createGroup);
                 group.add(lambda);
                 lambdas.put(lambda.type, group);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/JStyleLambdaGroup.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/JStyleLambdaGroup.java
index 07c1b08..df6f812 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/JStyleLambdaGroup.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/JStyleLambdaGroup.java
@@ -6,6 +6,7 @@
 
 import com.android.tools.r8.code.ReturnVoid;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
@@ -21,6 +22,7 @@
 import com.android.tools.r8.ir.optimize.lambda.LambdaGroup;
 import com.android.tools.r8.ir.synthetic.SyntheticSourceCode;
 import com.android.tools.r8.kotlin.Kotlin;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.ThrowingConsumer;
 import com.google.common.collect.Lists;
 import java.util.List;
@@ -123,10 +125,16 @@
 
   // Specialized group id.
   final static class GroupId extends KotlinLambdaGroupId {
-    GroupId(String capture, DexType iface,
-        String pkg, String signature, DexEncodedMethod mainMethod,
-        InnerClassAttribute inner, EnclosingMethodAttribute enclosing) {
-      super(capture, iface, pkg, signature, mainMethod, inner, enclosing);
+    GroupId(
+        AppView<AppInfoWithLiveness> appView,
+        String capture,
+        DexType iface,
+        String pkg,
+        String signature,
+        DexEncodedMethod mainMethod,
+        InnerClassAttribute inner,
+        EnclosingMethodAttribute enclosing) {
+      super(appView, capture, iface, pkg, signature, mainMethod, inner, enclosing);
     }
 
     @Override
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/JStyleLambdaGroupIdFactory.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/JStyleLambdaGroupIdFactory.java
index 6957cb1..8f26df4 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/JStyleLambdaGroupIdFactory.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/JStyleLambdaGroupIdFactory.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.ir.optimize.lambda.kotlin;
 
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexType;
@@ -11,15 +12,17 @@
 import com.android.tools.r8.ir.optimize.lambda.LambdaGroup.LambdaStructureError;
 import com.android.tools.r8.ir.optimize.lambda.LambdaGroupId;
 import com.android.tools.r8.kotlin.Kotlin;
-import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
 
 final class JStyleLambdaGroupIdFactory extends KotlinLambdaGroupIdFactory {
   static final JStyleLambdaGroupIdFactory INSTANCE = new JStyleLambdaGroupIdFactory();
 
   @Override
-  LambdaGroupId validateAndCreate(Kotlin kotlin, DexClass lambda, InternalOptions options)
+  LambdaGroupId validateAndCreate(
+      AppView<AppInfoWithLiveness> appView, Kotlin kotlin, DexClass lambda)
       throws LambdaStructureError {
-    boolean accessRelaxed = options.getProguardConfiguration().isAccessModificationAllowed();
+    boolean accessRelaxed =
+        appView.options().getProguardConfiguration().isAccessModificationAllowed();
 
     assert lambda.hasKotlinInfo() && lambda.getKotlinInfo().isSyntheticClass();
     assert lambda.getKotlinInfo().asSyntheticClass().isJavaStyleLambda();
@@ -35,12 +38,18 @@
     String captureSignature = validateInstanceFields(lambda, accessRelaxed);
     validateDirectMethods(lambda);
     DexEncodedMethod mainMethod = validateVirtualMethods(lambda);
-    String genericSignature = validateAnnotations(kotlin, lambda);
+    String genericSignature = validateAnnotations(appView, kotlin, lambda);
     InnerClassAttribute innerClass = validateInnerClasses(lambda);
 
-    return new JStyleLambdaGroup.GroupId(captureSignature, iface,
+    return new JStyleLambdaGroup.GroupId(
+        appView,
+        captureSignature,
+        iface,
         accessRelaxed ? "" : lambda.type.getPackageDescriptor(),
-        genericSignature, mainMethod, innerClass, lambda.getEnclosingMethod());
+        genericSignature,
+        mainMethod,
+        innerClass,
+        lambda.getEnclosingMethod());
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KStyleLambdaGroup.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KStyleLambdaGroup.java
index 9e07c44..9f9e767 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KStyleLambdaGroup.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KStyleLambdaGroup.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.code.Const4;
 import com.android.tools.r8.code.ReturnVoid;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
@@ -24,6 +25,7 @@
 import com.android.tools.r8.ir.optimize.lambda.LambdaGroup;
 import com.android.tools.r8.ir.synthetic.SyntheticSourceCode;
 import com.android.tools.r8.kotlin.Kotlin;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.ThrowingConsumer;
 import com.google.common.collect.Lists;
 import java.util.List;
@@ -129,10 +131,16 @@
 
   // Specialized group id.
   final static class GroupId extends KotlinLambdaGroupId {
-    GroupId(String capture, DexType iface,
-        String pkg, String signature, DexEncodedMethod mainMethod,
-        InnerClassAttribute inner, EnclosingMethodAttribute enclosing) {
-      super(capture, iface, pkg, signature, mainMethod, inner, enclosing);
+    GroupId(
+        AppView<AppInfoWithLiveness> appView,
+        String capture,
+        DexType iface,
+        String pkg,
+        String signature,
+        DexEncodedMethod mainMethod,
+        InnerClassAttribute inner,
+        EnclosingMethodAttribute enclosing) {
+      super(appView, capture, iface, pkg, signature, mainMethod, inner, enclosing);
     }
 
     @Override
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KStyleLambdaGroupIdFactory.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KStyleLambdaGroupIdFactory.java
index 3d60e0f..eaf154c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KStyleLambdaGroupIdFactory.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KStyleLambdaGroupIdFactory.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.ir.optimize.lambda.kotlin;
 
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexType;
@@ -11,15 +12,17 @@
 import com.android.tools.r8.ir.optimize.lambda.LambdaGroup.LambdaStructureError;
 import com.android.tools.r8.ir.optimize.lambda.LambdaGroupId;
 import com.android.tools.r8.kotlin.Kotlin;
-import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
 
 final class KStyleLambdaGroupIdFactory extends KotlinLambdaGroupIdFactory {
   static final KotlinLambdaGroupIdFactory INSTANCE = new KStyleLambdaGroupIdFactory();
 
   @Override
-  LambdaGroupId validateAndCreate(Kotlin kotlin, DexClass lambda, InternalOptions options)
+  LambdaGroupId validateAndCreate(
+      AppView<AppInfoWithLiveness> appView, Kotlin kotlin, DexClass lambda)
       throws LambdaStructureError {
-    boolean accessRelaxed = options.getProguardConfiguration().isAccessModificationAllowed();
+    boolean accessRelaxed =
+        appView.options().getProguardConfiguration().isAccessModificationAllowed();
 
     assert lambda.hasKotlinInfo() && lambda.getKotlinInfo().isSyntheticClass();
     assert lambda.getKotlinInfo().asSyntheticClass().isKotlinStyleLambda();
@@ -35,12 +38,18 @@
     String captureSignature = validateInstanceFields(lambda, accessRelaxed);
     validateDirectMethods(lambda);
     DexEncodedMethod mainMethod = validateVirtualMethods(lambda);
-    String genericSignature = validateAnnotations(kotlin, lambda);
+    String genericSignature = validateAnnotations(appView, kotlin, lambda);
     InnerClassAttribute innerClass = validateInnerClasses(lambda);
 
-    return new KStyleLambdaGroup.GroupId(captureSignature, iface,
+    return new KStyleLambdaGroup.GroupId(
+        appView,
+        captureSignature,
+        iface,
         accessRelaxed ? "" : lambda.type.getPackageDescriptor(),
-        genericSignature, mainMethod, innerClass, lambda.getEnclosingMethod());
+        genericSignature,
+        mainMethod,
+        innerClass,
+        lambda.getEnclosingMethod());
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupId.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupId.java
index 996099b..7f24d79 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupId.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupId.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.ir.optimize.lambda.kotlin;
 
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexAnnotationSet;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexProto;
@@ -14,6 +15,7 @@
 import com.android.tools.r8.graph.ParameterAnnotationsList;
 import com.android.tools.r8.ir.optimize.lambda.LambdaGroup;
 import com.android.tools.r8.ir.optimize.lambda.LambdaGroupId;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
 
 abstract class KotlinLambdaGroupId implements LambdaGroupId {
   private static final int MISSING_INNER_CLASS_ATTRIBUTE = -1;
@@ -50,8 +52,15 @@
   // access from InnerClassAttribute.
   final int innerClassAccess;
 
-  KotlinLambdaGroupId(String capture, DexType iface, String pkg, String signature,
-      DexEncodedMethod mainMethod, InnerClassAttribute inner, EnclosingMethodAttribute enclosing) {
+  KotlinLambdaGroupId(
+      AppView<AppInfoWithLiveness> appView,
+      String capture,
+      DexType iface,
+      String pkg,
+      String signature,
+      DexEncodedMethod mainMethod,
+      InnerClassAttribute inner,
+      EnclosingMethodAttribute enclosing) {
     assert capture != null && iface != null && pkg != null && mainMethod != null;
     assert inner == null || (inner.isAnonymous() && inner.getOuter() == null);
     this.capture = capture;
@@ -60,8 +69,8 @@
     this.signature = signature;
     this.mainMethodName = mainMethod.method.name;
     this.mainMethodProto = mainMethod.method.proto;
-    this.mainMethodAnnotations = mainMethod.annotations;
-    this.mainMethodParamAnnotations = mainMethod.parameterAnnotationsList;
+    this.mainMethodAnnotations = mainMethod.liveAnnotations(appView);
+    this.mainMethodParamAnnotations = mainMethod.liveParameterAnnotations(appView);
     this.innerClassAccess = inner != null ? inner.getAccess() : MISSING_INNER_CLASS_ATTRIBUTE;
     this.enclosing = enclosing;
     this.hash = computeHashCode();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupIdFactory.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupIdFactory.java
index 568a8cb..18b4f00 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupIdFactory.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupIdFactory.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.ir.optimize.lambda.kotlin;
 
 import com.android.tools.r8.graph.AccessFlags;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexAnnotation;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedField;
@@ -15,7 +16,7 @@
 import com.android.tools.r8.ir.optimize.lambda.LambdaGroup.LambdaStructureError;
 import com.android.tools.r8.ir.optimize.lambda.LambdaGroupId;
 import com.android.tools.r8.kotlin.Kotlin;
-import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.List;
 
 public abstract class KotlinLambdaGroupIdFactory implements KotlinLambdaConstants {
@@ -29,19 +30,21 @@
   // At this point we only perform high-level checks before qualifying the lambda as a candidate
   // for merging and assigning lambda group id. We can NOT perform checks on method bodies since
   // they may not be converted yet, we'll do that in KStyleLambdaClassValidator.
-  public static LambdaGroupId create(Kotlin kotlin, DexClass lambda, InternalOptions options)
+  public static LambdaGroupId create(
+      AppView<AppInfoWithLiveness> appView, Kotlin kotlin, DexClass lambda)
       throws LambdaStructureError {
 
     assert lambda.hasKotlinInfo() && lambda.getKotlinInfo().isSyntheticClass();
     if (lambda.getKotlinInfo().asSyntheticClass().isKotlinStyleLambda()) {
-      return KStyleLambdaGroupIdFactory.INSTANCE.validateAndCreate(kotlin, lambda, options);
+      return KStyleLambdaGroupIdFactory.INSTANCE.validateAndCreate(appView, kotlin, lambda);
     }
 
     assert lambda.getKotlinInfo().asSyntheticClass().isJavaStyleLambda();
-    return JStyleLambdaGroupIdFactory.INSTANCE.validateAndCreate(kotlin, lambda, options);
+    return JStyleLambdaGroupIdFactory.INSTANCE.validateAndCreate(appView, kotlin, lambda);
   }
 
-  abstract LambdaGroupId validateAndCreate(Kotlin kotlin, DexClass lambda, InternalOptions options)
+  abstract LambdaGroupId validateAndCreate(
+      AppView<AppInfoWithLiveness> appView, Kotlin kotlin, DexClass lambda)
       throws LambdaStructureError;
 
   abstract void validateSuperclass(Kotlin kotlin, DexClass lambda) throws LambdaStructureError;
@@ -101,26 +104,25 @@
     return true;
   }
 
-  String validateAnnotations(Kotlin kotlin, DexClass lambda) throws LambdaStructureError {
+  String validateAnnotations(AppView<AppInfoWithLiveness> appView, Kotlin kotlin, DexClass lambda)
+      throws LambdaStructureError {
     String signature = null;
-    if (!lambda.annotations.isEmpty()) {
-      for (DexAnnotation annotation : lambda.annotations.annotations) {
-        if (DexAnnotation.isSignatureAnnotation(annotation, kotlin.factory)) {
-          signature = DexAnnotation.getSignature(annotation);
-          continue;
-        }
-
-        if (annotation.annotation.type == kotlin.metadata.kotlinMetadataType) {
-          // Ignore kotlin metadata on lambda classes. Metadata on synthetic
-          // classes exists but is not used in the current Kotlin version (1.2.21)
-          // and newly generated lambda _group_ class is not exactly a kotlin class.
-          continue;
-        }
-
-        assert !hasValidAnnotations(kotlin, lambda);
-        throw new LambdaStructureError(
-            "unexpected annotation: " + annotation.annotation.type.toSourceString());
+    for (DexAnnotation annotation : lambda.liveAnnotations(appView).annotations) {
+      if (DexAnnotation.isSignatureAnnotation(annotation, kotlin.factory)) {
+        signature = DexAnnotation.getSignature(annotation);
+        continue;
       }
+
+      if (annotation.annotation.type == kotlin.metadata.kotlinMetadataType) {
+        // Ignore kotlin metadata on lambda classes. Metadata on synthetic
+        // classes exists but is not used in the current Kotlin version (1.2.21)
+        // and newly generated lambda _group_ class is not exactly a kotlin class.
+        continue;
+      }
+
+      assert !hasValidAnnotations(kotlin, lambda);
+      throw new LambdaStructureError(
+          "unexpected annotation: " + annotation.annotation.type.toSourceString());
     }
     assert hasValidAnnotations(kotlin, lambda);
     return signature;
diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
index d13cc3b..6e04d4a 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
@@ -69,9 +69,7 @@
     this.packageObfuscationMode = options.getProguardConfiguration().getPackageObfuscationMode();
     this.isAccessModificationAllowed =
         options.getProguardConfiguration().isAccessModificationAllowed();
-    this.keepInnerClassStructure =
-        options.getProguardConfiguration().getKeepAttributes().signature
-            || options.getProguardConfiguration().getKeepAttributes().innerClasses;
+    this.keepInnerClassStructure = options.keepInnerClassStructure();
 
     // Initialize top-level naming state.
     topLevelState = new Namespace(
diff --git a/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java b/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java
index 8ea3d93..0c85641 100644
--- a/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java
+++ b/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java
@@ -83,7 +83,8 @@
     }
     int index = innerTypeMapped.lastIndexOf(separator);
     if (index < 0) {
-      assert options.getProguardConfiguration().hasApplyMappingFile()
+      assert !options.keepInnerClassStructure()
+              || options.getProguardConfiguration().hasApplyMappingFile()
           : innerType + " -> " + innerTypeMapped;
       String descriptor = lookupDescriptor(innerType).toString();
       return options.itemFactory.createString(
diff --git a/src/main/java/com/android/tools/r8/naming/signature/GenericSignatureRewriter.java b/src/main/java/com/android/tools/r8/naming/signature/GenericSignatureRewriter.java
index 45c59a8..7747eda 100644
--- a/src/main/java/com/android/tools/r8/naming/signature/GenericSignatureRewriter.java
+++ b/src/main/java/com/android/tools/r8/naming/signature/GenericSignatureRewriter.java
@@ -258,7 +258,7 @@
         int innerClassPos = enclosingRenamedBinaryName.length() + 1;
         if (innerClassPos < fullRenamedBinaryName.length()) {
           renamedSignature.append(fullRenamedBinaryName.substring(innerClassPos));
-        } else {
+        } else if (appView.options().keepInnerClassStructure()) {
           reporter.warning(
               new StringDiagnostic(
                   "Should have retained InnerClasses attribute of " + type + ".",
@@ -267,7 +267,7 @@
         }
       } else {
         // Did not find the class - keep the inner class name as is.
-        // TODO(110085899): Warn about missing classes in signatures?
+        // TODO(b/110085899): Warn about missing classes in signatures?
         renamedSignature.append(name);
       }
       return type;
diff --git a/src/main/java/com/android/tools/r8/shaking/AnnotationMatchResult.java b/src/main/java/com/android/tools/r8/shaking/AnnotationMatchResult.java
new file mode 100644
index 0000000..f5a3bbf
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/AnnotationMatchResult.java
@@ -0,0 +1,53 @@
+// Copyright (c) 2020, 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;
+
+import com.android.tools.r8.graph.DexAnnotation;
+
+public abstract class AnnotationMatchResult {
+
+  public boolean isConcreteAnnotationMatchResult() {
+    return false;
+  }
+
+  public ConcreteAnnotationMatchResult asConcreteAnnotationMatchResult() {
+    return null;
+  }
+
+  static class AnnotationsIgnoredMatchResult extends AnnotationMatchResult {
+
+    private static final AnnotationsIgnoredMatchResult INSTANCE =
+        new AnnotationsIgnoredMatchResult();
+
+    private AnnotationsIgnoredMatchResult() {}
+
+    public static AnnotationsIgnoredMatchResult getInstance() {
+      return INSTANCE;
+    }
+  }
+
+  static class ConcreteAnnotationMatchResult extends AnnotationMatchResult {
+
+    private final DexAnnotation matchedAnnotation;
+
+    public ConcreteAnnotationMatchResult(DexAnnotation matchedAnnotation) {
+      this.matchedAnnotation = matchedAnnotation;
+    }
+
+    public DexAnnotation getMatchedAnnotation() {
+      return matchedAnnotation;
+    }
+
+    @Override
+    public boolean isConcreteAnnotationMatchResult() {
+      return true;
+    }
+
+    @Override
+    public ConcreteAnnotationMatchResult asConcreteAnnotationMatchResult() {
+      return this;
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
index fd3e7f5..4136d1a 100644
--- a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
@@ -20,8 +20,8 @@
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.graph.InnerClassAttribute;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
-import java.util.Collections;
 import java.util.IdentityHashMap;
 import java.util.Map;
 import java.util.Set;
@@ -29,26 +29,50 @@
 public class AnnotationRemover {
 
   private final AppView<AppInfoWithLiveness> appView;
-  private final ProguardKeepAttributes keep;
+  private final Set<DexAnnotation> annotationsToRetain;
   private final Set<DexType> classesToRetainInnerClassAttributeFor;
+  private final ProguardKeepAttributes keep;
 
   public AnnotationRemover(
       AppView<AppInfoWithLiveness> appView, Set<DexType> classesToRetainInnerClassAttributeFor) {
+    this(appView, classesToRetainInnerClassAttributeFor, ImmutableSet.of());
+  }
+
+  private AnnotationRemover(
+      AppView<AppInfoWithLiveness> appView,
+      Set<DexType> classesToRetainInnerClassAttributeFor,
+      Set<DexAnnotation> annotationsToRetain) {
     this.appView = appView;
-    this.keep = appView.options().getProguardConfiguration().getKeepAttributes();
+    this.annotationsToRetain = annotationsToRetain;
     this.classesToRetainInnerClassAttributeFor = classesToRetainInnerClassAttributeFor;
+    this.keep = appView.options().getProguardConfiguration().getKeepAttributes();
+  }
+
+  public static Builder builder() {
+    return new Builder();
+  }
+
+  public Set<DexType> getClassesToRetainInnerClassAttributeFor() {
+    return classesToRetainInnerClassAttributeFor;
   }
 
   /** Used to filter annotations on classes, methods and fields. */
   private boolean filterAnnotations(DexDefinition holder, DexAnnotation annotation) {
-    return shouldKeepAnnotation(holder, annotation, isAnnotationTypeLive(annotation), appView);
+    return annotationsToRetain.contains(annotation)
+        || shouldKeepAnnotation(appView, holder, annotation, isAnnotationTypeLive(annotation));
   }
 
-  static boolean shouldKeepAnnotation(
+  public static boolean shouldKeepAnnotation(
+      AppView<AppInfoWithLiveness> appView, DexDefinition holder, DexAnnotation annotation) {
+    return shouldKeepAnnotation(
+        appView, holder, annotation, isAnnotationTypeLive(annotation, appView));
+  }
+
+  public static boolean shouldKeepAnnotation(
+      AppView<?> appView,
       DexDefinition holder,
       DexAnnotation annotation,
-      boolean isAnnotationTypeLive,
-      AppView<?> appView) {
+      boolean isAnnotationTypeLive) {
     ProguardKeepAttributes config =
         appView.options().getProguardConfiguration() != null
             ? appView.options().getProguardConfiguration().getKeepAttributes()
@@ -108,6 +132,11 @@
   }
 
   private boolean isAnnotationTypeLive(DexAnnotation annotation) {
+    return isAnnotationTypeLive(annotation, appView);
+  }
+
+  private static boolean isAnnotationTypeLive(
+      DexAnnotation annotation, AppView<AppInfoWithLiveness> appView) {
     DexType annotationType = annotation.annotation.type.toBaseType(appView.dexItemFactory());
     return appView.appInfo().isNonProgramTypeOrLiveProgramType(annotationType);
   }
@@ -116,6 +145,9 @@
    * Used to filter annotations on parameters.
    */
   private boolean filterParameterAnnotations(DexAnnotation annotation) {
+    if (annotationsToRetain.contains(annotation)) {
+      return true;
+    }
     switch (annotation.visibility) {
       case DexAnnotation.VISIBILITY_SYSTEM:
         return false;
@@ -165,68 +197,6 @@
     return false;
   }
 
-  public static Set<DexType> computeClassesToRetainInnerClassAttributeFor(
-      AppView<? extends AppInfoWithLiveness> appView) {
-    // In case of minification for certain inner classes we need to retain their InnerClass
-    // attributes because their minified name still needs to be in hierarchical format
-    // (enclosing$inner) otherwise the GenericSignatureRewriter can't produce the correct,
-    // renamed signature.
-
-    // More precisely:
-    // - we're going to retain the InnerClass attribute that refers to the same class as 'inner'
-    // - for live, inner, nonstatic classes
-    // - that are enclosed by a class with a generic signature.
-
-    // In compat mode we always keep all InnerClass attributes (if requested).
-    // If not requested we never keep any. In these cases don't compute eligible classes.
-    if (appView.options().forceProguardCompatibility
-        || !appView.options().getProguardConfiguration().getKeepAttributes().innerClasses) {
-      return Collections.emptySet();
-    }
-
-    // Build lookup table and set of the interesting classes.
-    // enclosingClasses.get(clazz) gives the enclosing class of 'clazz'
-    Map<DexType, DexProgramClass> enclosingClasses = new IdentityHashMap<>();
-    Set<DexProgramClass> genericClasses = Sets.newIdentityHashSet();
-
-    Iterable<DexProgramClass> programClasses = appView.appInfo().classes();
-    for (DexProgramClass clazz : programClasses) {
-      if (hasSignatureAnnotation(clazz, appView.dexItemFactory())) {
-        genericClasses.add(clazz);
-      }
-      for (InnerClassAttribute innerClassAttribute : clazz.getInnerClasses()) {
-        if ((innerClassAttribute.getAccess() & Constants.ACC_STATIC) == 0
-            && innerClassAttribute.getOuter() == clazz.type) {
-          enclosingClasses.put(innerClassAttribute.getInner(), clazz);
-        }
-      }
-    }
-
-    Set<DexType> result = Sets.newIdentityHashSet();
-    for (DexProgramClass clazz : programClasses) {
-      // If [clazz] is mentioned by a keep rule, it could be used for reflection, and we therefore
-      // need to keep the enclosing method and inner classes attributes, if requested.
-      if (appView.appInfo().isPinned(clazz.type)) {
-        for (InnerClassAttribute innerClassAttribute : clazz.getInnerClasses()) {
-          DexType inner = innerClassAttribute.getInner();
-          if (appView.appInfo().isNonProgramTypeOrLiveProgramType(inner)) {
-            result.add(inner);
-          }
-          DexType context = innerClassAttribute.getLiveContext(appView.appInfo());
-          if (context != null && appView.appInfo().isNonProgramTypeOrLiveProgramType(context)) {
-            result.add(context);
-          }
-        }
-      }
-      if (clazz.getInnerClassAttributeForThisClass() != null
-          && appView.appInfo().isNonProgramTypeOrLiveProgramType(clazz.type)
-          && hasGenericEnclosingClass(clazz, enclosingClasses, genericClasses)) {
-        result.add(clazz.type);
-      }
-    }
-    return result;
-  }
-
   public void run() {
     for (DexProgramClass clazz : appView.appInfo().classes()) {
       stripAttributes(clazz);
@@ -251,11 +221,11 @@
 
   private DexAnnotation rewriteAnnotation(DexDefinition holder, DexAnnotation original) {
     // Check if we should keep this annotation first.
-    if (!filterAnnotations(holder, original)) {
-      return null;
+    if (filterAnnotations(holder, original)) {
+      // Then, filter out values that refer to dead definitions.
+      return original.rewrite(this::rewriteEncodedAnnotation);
     }
-    // Then, filter out values that refer to dead definitions.
-    return original.rewrite(this::rewriteEncodedAnnotation);
+    return null;
   }
 
   private DexEncodedAnnotation rewriteEncodedAnnotation(DexEncodedAnnotation original) {
@@ -368,4 +338,91 @@
       }
     }
   }
+
+  public static class Builder {
+
+    /**
+     * The set of annotations that were matched by a conditional if rule. These are needed for the
+     * interpretation of if rules in the second round of tree shaking.
+     */
+    private final Set<DexAnnotation> annotationsToRetain = Sets.newIdentityHashSet();
+
+    private Set<DexType> classesToRetainInnerClassAttributeFor;
+
+    public Builder computeClassesToRetainInnerClassAttributeFor(
+        AppView<AppInfoWithLiveness> appView) {
+      assert classesToRetainInnerClassAttributeFor == null;
+      // In case of minification for certain inner classes we need to retain their InnerClass
+      // attributes because their minified name still needs to be in hierarchical format
+      // (enclosing$inner) otherwise the GenericSignatureRewriter can't produce the correct,
+      // renamed signature.
+
+      // More precisely:
+      // - we're going to retain the InnerClass attribute that refers to the same class as 'inner'
+      // - for live, inner, nonstatic classes
+      // - that are enclosed by a class with a generic signature.
+
+      // In compat mode we always keep all InnerClass attributes (if requested).
+      // If not requested we never keep any. In these cases don't compute eligible classes.
+      Set<DexType> result = Sets.newIdentityHashSet();
+      if (!appView.options().forceProguardCompatibility
+          && appView.options().getProguardConfiguration().getKeepAttributes().innerClasses) {
+        // Build lookup table and set of the interesting classes.
+        // enclosingClasses.get(clazz) gives the enclosing class of 'clazz'
+        Map<DexType, DexProgramClass> enclosingClasses = new IdentityHashMap<>();
+        Set<DexProgramClass> genericClasses = Sets.newIdentityHashSet();
+        for (DexProgramClass clazz : appView.appInfo().classes()) {
+          if (hasSignatureAnnotation(clazz, appView.dexItemFactory())) {
+            genericClasses.add(clazz);
+          }
+          for (InnerClassAttribute innerClassAttribute : clazz.getInnerClasses()) {
+            if ((innerClassAttribute.getAccess() & Constants.ACC_STATIC) == 0
+                && innerClassAttribute.getOuter() == clazz.type) {
+              enclosingClasses.put(innerClassAttribute.getInner(), clazz);
+            }
+          }
+        }
+        for (DexProgramClass clazz : appView.appInfo().classes()) {
+          // If [clazz] is mentioned by a keep rule, it could be used for reflection, and we
+          // therefore
+          // need to keep the enclosing method and inner classes attributes, if requested.
+          if (appView.appInfo().isPinned(clazz.type)) {
+            for (InnerClassAttribute innerClassAttribute : clazz.getInnerClasses()) {
+              DexType inner = innerClassAttribute.getInner();
+              if (appView.appInfo().isNonProgramTypeOrLiveProgramType(inner)) {
+                result.add(inner);
+              }
+              DexType context = innerClassAttribute.getLiveContext(appView.appInfo());
+              if (context != null && appView.appInfo().isNonProgramTypeOrLiveProgramType(context)) {
+                result.add(context);
+              }
+            }
+          }
+          if (clazz.getInnerClassAttributeForThisClass() != null
+              && appView.appInfo().isNonProgramTypeOrLiveProgramType(clazz.type)
+              && hasGenericEnclosingClass(clazz, enclosingClasses, genericClasses)) {
+            result.add(clazz.type);
+          }
+        }
+      }
+      classesToRetainInnerClassAttributeFor = result;
+      return this;
+    }
+
+    public Builder setClassesToRetainInnerClassAttributeFor(
+        Set<DexType> classesToRetainInnerClassAttributeFor) {
+      this.classesToRetainInnerClassAttributeFor = classesToRetainInnerClassAttributeFor;
+      return this;
+    }
+
+    public void retainAnnotation(DexAnnotation annotation) {
+      annotationsToRetain.add(annotation);
+    }
+
+    public AnnotationRemover build(AppView<AppInfoWithLiveness> appView) {
+      assert classesToRetainInnerClassAttributeFor != null;
+      return new AnnotationRemover(
+          appView, classesToRetainInnerClassAttributeFor, annotationsToRetain);
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/shaking/ConsequentRootSetBuilder.java b/src/main/java/com/android/tools/r8/shaking/ConsequentRootSetBuilder.java
new file mode 100644
index 0000000..2e5edba
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/ConsequentRootSetBuilder.java
@@ -0,0 +1,26 @@
+// Copyright (c) 2020, 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;
+
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.AppView;
+
+class ConsequentRootSetBuilder extends RootSetBuilder {
+
+  private final Enqueuer enqueuer;
+
+  ConsequentRootSetBuilder(AppView<? extends AppInfoWithSubtyping> appView, Enqueuer enqueuer) {
+    super(appView, appView.appInfo().app(), null);
+    this.enqueuer = enqueuer;
+  }
+
+  @Override
+  void handleMatchedAnnotation(AnnotationMatchResult annotationMatchResult) {
+    if (enqueuer.getMode().isInitialTreeShaking()
+        && annotationMatchResult.isConcreteAnnotationMatchResult()) {
+      enqueuer.retainAnnotationForFinalTreeShaking(
+          annotationMatchResult.asConcreteAnnotationMatchResult().getMatchedAnnotation());
+    }
+  }
+}
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 9a33da2..1a0bc08 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -144,6 +144,7 @@
   private RootSet rootSet;
   private ProguardClassFilter dontWarnPatterns;
   private final EnqueuerUseRegistryFactory useRegistryFactory;
+  private AnnotationRemover.Builder annotationRemoverBuilder;
 
   private final Map<DexMethod, Set<DexEncodedMethod>> virtualInvokes = new IdentityHashMap<>();
   private final Map<DexMethod, Set<DexEncodedMethod>> interfaceInvokes = new IdentityHashMap<>();
@@ -356,6 +357,10 @@
     return this;
   }
 
+  public void setAnnotationRemoverBuilder(AnnotationRemover.Builder annotationRemoverBuilder) {
+    this.annotationRemoverBuilder = annotationRemoverBuilder;
+  }
+
   private boolean isProgramClass(DexType type) {
     return getProgramClassOrNull(type) != null;
   }
@@ -1319,7 +1324,7 @@
     DexClass clazz = appView.definitionFor(type);
     boolean annotationTypeIsLibraryClass = clazz == null || clazz.isNotProgramClass();
     boolean isLive = annotationTypeIsLibraryClass || liveTypes.contains(clazz.asProgramClass());
-    if (!shouldKeepAnnotation(holder, annotation, isLive, appView)) {
+    if (!shouldKeepAnnotation(appView, holder, annotation, isLive)) {
       // Remember this annotation for later.
       if (!annotationTypeIsLibraryClass) {
         deferredAnnotations.computeIfAbsent(type, ignore -> new HashSet<>()).add(annotation);
@@ -2395,7 +2400,8 @@
               activeIfRules.computeIfAbsent(wrap, ignore -> new LinkedHashSet<>()).add(ifRule);
             }
           }
-          RootSetBuilder consequentSetBuilder = new RootSetBuilder(appView);
+          ConsequentRootSetBuilder consequentSetBuilder =
+              new ConsequentRootSetBuilder(appView, this);
           IfRuleEvaluator ifRuleEvaluator =
               new IfRuleEvaluator(
                   appView, this, executorService, activeIfRules, consequentSetBuilder);
@@ -2524,6 +2530,13 @@
     lambdaMethodsTargetedByInvokeDynamic.clear();
   }
 
+  void retainAnnotationForFinalTreeShaking(DexAnnotation annotation) {
+    assert mode.isInitialTreeShaking();
+    if (annotationRemoverBuilder != null) {
+      annotationRemoverBuilder.retainAnnotation(annotation);
+    }
+  }
+
   // Package protected due to entry point from worklist.
   void markMethodAsKept(DexProgramClass holder, DexEncodedMethod target, KeepReason reason) {
     DexMethod method = target.method;
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 c1dabc8..fe81bb7 100644
--- a/src/main/java/com/android/tools/r8/shaking/IfRuleEvaluator.java
+++ b/src/main/java/com/android/tools/r8/shaking/IfRuleEvaluator.java
@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.shaking;
 
+import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
+
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
@@ -14,6 +16,7 @@
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.shaking.RootSetBuilder.ConsequentRootSet;
+import com.android.tools.r8.utils.InternalOptions.TestingOptions.ProguardIfRuleEvaluationData;
 import com.android.tools.r8.utils.ThreadUtils;
 import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.ImmutableSet;
@@ -37,14 +40,14 @@
   private final ExecutorService executorService;
   private final List<Future<?>> futures = new ArrayList<>();
   private final Map<Wrapper<ProguardIfRule>, Set<ProguardIfRule>> ifRules;
-  private final RootSetBuilder rootSetBuilder;
+  private final ConsequentRootSetBuilder rootSetBuilder;
 
   IfRuleEvaluator(
       AppView<? extends AppInfoWithSubtyping> appView,
       Enqueuer enqueuer,
       ExecutorService executorService,
       Map<Wrapper<ProguardIfRule>, Set<ProguardIfRule>> ifRules,
-      RootSetBuilder rootSetBuilder) {
+      ConsequentRootSetBuilder rootSetBuilder) {
     this.appView = appView;
     this.enqueuer = enqueuer;
     this.executorService = executorService;
@@ -61,6 +64,8 @@
         while (it.hasNext()) {
           Map.Entry<Wrapper<ProguardIfRule>, Set<ProguardIfRule>> ifRuleEntry = it.next();
           ProguardIfRule ifRule = ifRuleEntry.getKey().get();
+          ProguardIfRuleEvaluationData ifRuleEvaluationData =
+              appView.options().testing.proguardIfRuleEvaluationData;
 
           // Depending on which types that trigger the -if rule, the application of the subsequent
           // -keep rule may vary (due to back references). So, we need to try all pairs of -if
@@ -73,12 +78,9 @@
 
             // Check if the class matches the if-rule.
             if (appView.options().testing.measureProguardIfRuleEvaluations) {
-              appView.options()
-                  .testing
-                  .proguardIfRuleEvaluationData
-                  .numberOfProguardIfRuleClassEvaluations++;
+              ifRuleEvaluationData.numberOfProguardIfRuleClassEvaluations++;
             }
-            if (evaluateClassForIfRule(ifRule, clazz, clazz)) {
+            if (evaluateClassForIfRule(ifRule, clazz)) {
               // When matching an if rule against a type, the if-rule are filled with the current
               // capture of wildcards. Propagate this down to member rules with same class part
               // equivalence.
@@ -88,10 +90,7 @@
                       memberRule -> {
                         registerClassCapture(memberRule, clazz, clazz);
                         if (appView.options().testing.measureProguardIfRuleEvaluations) {
-                          appView.options()
-                              .testing
-                              .proguardIfRuleEvaluationData
-                              .numberOfProguardIfRuleMemberEvaluations++;
+                          ifRuleEvaluationData.numberOfProguardIfRuleMemberEvaluations++;
                         }
                         return evaluateIfRuleMembersAndMaterialize(memberRule, clazz, clazz)
                             && canRemoveSubsequentKeepRule(memberRule);
@@ -99,33 +98,30 @@
             }
 
             // Check if one of the types that have been merged into `clazz` satisfies the if-rule.
-            if (appView.options().enableVerticalClassMerging
-                && appView.verticallyMergedClasses() != null) {
+            if (appView.verticallyMergedClasses() != null) {
               Iterable<DexType> sources =
                   appView.verticallyMergedClasses().getSourcesFor(clazz.type);
               for (DexType sourceType : sources) {
                 // Note that, although `sourceType` has been merged into `type`, the dex class for
                 // `sourceType` is still available until the second round of tree shaking. This
                 // way we can still retrieve the access flags of `sourceType`.
-                DexClass sourceClass = appView.definitionFor(sourceType);
-                assert sourceClass != null;
-                if (appView.options().testing.measureProguardIfRuleEvaluations) {
-                  appView.options()
-                      .testing
-                      .proguardIfRuleEvaluationData
-                      .numberOfProguardIfRuleClassEvaluations++;
+                DexProgramClass sourceClass =
+                    asProgramClassOrNull(appView.definitionFor(sourceType));
+                if (sourceClass == null) {
+                  assert false;
+                  continue;
                 }
-                if (evaluateClassForIfRule(ifRule, sourceClass, clazz)) {
+                if (appView.options().testing.measureProguardIfRuleEvaluations) {
+                  ifRuleEvaluationData.numberOfProguardIfRuleClassEvaluations++;
+                }
+                if (evaluateClassForIfRule(ifRule, sourceClass)) {
                   ifRuleEntry
                       .getValue()
                       .removeIf(
                           memberRule -> {
                             registerClassCapture(memberRule, sourceClass, clazz);
                             if (appView.options().testing.measureProguardIfRuleEvaluations) {
-                              appView.options()
-                                  .testing
-                                  .proguardIfRuleEvaluationData
-                                  .numberOfProguardIfRuleMemberEvaluations++;
+                              ifRuleEvaluationData.numberOfProguardIfRuleMemberEvaluations++;
                             }
                             return evaluateIfRuleMembersAndMaterialize(
                                     memberRule, sourceClass, clazz)
@@ -191,28 +187,25 @@
     return false;
   }
 
-  /**
-   * Determines if `sourceClass` satisfies the given if-rule class specification. If `sourceClass`
-   * has not been merged into another class, then `targetClass` is the same as `sourceClass`.
-   * Otherwise, `targetClass` denotes the class that `sourceClass` has been merged into.
-   */
-  private boolean evaluateClassForIfRule(
-      ProguardIfRule rule, DexClass sourceClass, DexClass targetClass) {
-    if (!RootSetBuilder.satisfyClassType(rule, sourceClass)) {
+  /** Determines if {@param clazz} satisfies the given if-rule class specification. */
+  private boolean evaluateClassForIfRule(ProguardIfRule rule, DexProgramClass clazz) {
+    if (!RootSetBuilder.satisfyClassType(rule, clazz)) {
       return false;
     }
-    if (!RootSetBuilder.satisfyAccessFlag(rule, sourceClass)) {
+    if (!RootSetBuilder.satisfyAccessFlag(rule, clazz)) {
       return false;
     }
-    if (!RootSetBuilder.satisfyAnnotation(rule, sourceClass)) {
+    AnnotationMatchResult annotationMatchResult = RootSetBuilder.satisfyAnnotation(rule, clazz);
+    if (annotationMatchResult == null) {
       return false;
     }
-    if (!rule.getClassNames().matches(sourceClass.type)) {
+    rootSetBuilder.handleMatchedAnnotation(annotationMatchResult);
+    if (!rule.getClassNames().matches(clazz.type)) {
       return false;
     }
     if (rule.hasInheritanceClassName()) {
       // Try another live type since the current one doesn't satisfy the inheritance rule.
-      return rootSetBuilder.satisfyInheritanceRule(sourceClass, rule);
+      return rootSetBuilder.satisfyInheritanceRule(clazz, rule);
     }
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardMemberRule.java b/src/main/java/com/android/tools/r8/shaking/ProguardMemberRule.java
index 93f36a2..a881b83 100644
--- a/src/main/java/com/android/tools/r8/shaking/ProguardMemberRule.java
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardMemberRule.java
@@ -16,6 +16,7 @@
 import com.google.common.collect.Iterables;
 import java.util.Collections;
 import java.util.List;
+import java.util.function.Consumer;
 import java.util.stream.Collectors;
 import java.util.stream.StreamSupport;
 
@@ -169,38 +170,45 @@
     return type;
   }
 
-  public boolean matches(DexEncodedField field, AppView<?> appView, DexStringCache stringCache) {
+  public boolean matches(
+      DexEncodedField field,
+      AppView<?> appView,
+      Consumer<AnnotationMatchResult> matchedAnnotationsConsumer,
+      DexStringCache stringCache) {
     DexField originalSignature = appView.graphLense().getOriginalFieldSignature(field.field);
     switch (getRuleType()) {
       case ALL:
       case ALL_FIELDS:
-        // Access flags check.
-        if (!getAccessFlags().containsAll(field.accessFlags)
-            || !getNegatedAccessFlags().containsNone(field.accessFlags)) {
-          break;
+        {
+          // Access flags check.
+          if (!getAccessFlags().containsAll(field.accessFlags)
+              || !getNegatedAccessFlags().containsNone(field.accessFlags)) {
+            break;
+          }
+          // Annotations check.
+          return RootSetBuilder.containsAnnotation(annotation, field, matchedAnnotationsConsumer);
         }
-        // Annotations check.
-        return RootSetBuilder.containsAnnotation(annotation, field);
+
       case FIELD:
-        // Name check.
-        String name = stringCache.lookupString(originalSignature.name);
-        if (!getName().matches(name)) {
-          break;
+        {
+          // Name check.
+          String name = stringCache.lookupString(originalSignature.name);
+          if (!getName().matches(name)) {
+            break;
+          }
+          // Access flags check.
+          if (!getAccessFlags().containsAll(field.accessFlags)
+              || !getNegatedAccessFlags().containsNone(field.accessFlags)) {
+            break;
+          }
+          // Type check.
+          if (!getType().matches(originalSignature.type, appView)) {
+            break;
+          }
+          // Annotations check
+          return RootSetBuilder.containsAnnotation(annotation, field, matchedAnnotationsConsumer);
         }
-        // Access flags check.
-        if (!getAccessFlags().containsAll(field.accessFlags)
-            || !getNegatedAccessFlags().containsNone(field.accessFlags)) {
-          break;
-        }
-        // Type check.
-        if (!getType().matches(originalSignature.type, appView)) {
-          break;
-        }
-        // Annotations check
-        if (!RootSetBuilder.containsAnnotation(annotation, field)) {
-          break;
-        }
-        return true;
+
       case ALL_METHODS:
       case CLINIT:
       case INIT:
@@ -211,7 +219,11 @@
     return false;
   }
 
-  public boolean matches(DexEncodedMethod method, AppView<?> appView, DexStringCache stringCache) {
+  public boolean matches(
+      DexEncodedMethod method,
+      AppView<?> appView,
+      Consumer<AnnotationMatchResult> matchedAnnotationsConsumer,
+      DexStringCache stringCache) {
     DexMethod originalSignature = appView.graphLense().getOriginalMethodSignature(method.method);
     switch (getRuleType()) {
       case ALL_METHODS:
@@ -219,53 +231,61 @@
           break;
         }
         // Fall through for all other methods.
+
       case ALL:
-        // Access flags check.
-        if (!getAccessFlags().containsAll(method.accessFlags)
-            || !getNegatedAccessFlags().containsNone(method.accessFlags)) {
-          break;
+        {
+          // Access flags check.
+          if (!getAccessFlags().containsAll(method.accessFlags)
+              || !getNegatedAccessFlags().containsNone(method.accessFlags)) {
+            break;
+          }
+          // Annotations check.
+          return RootSetBuilder.containsAnnotation(annotation, method, matchedAnnotationsConsumer);
         }
-        // Annotations check.
-        return RootSetBuilder.containsAnnotation(annotation, method);
+
       case METHOD:
         // Check return type.
         if (!type.matches(originalSignature.proto.returnType, appView)) {
           break;
         }
         // Fall through for access flags, name and arguments.
+
       case CONSTRUCTOR:
       case INIT:
       case CLINIT:
-        // Name check.
-        String name = stringCache.lookupString(originalSignature.name);
-        if (!getName().matches(name)) {
-          break;
-        }
-        // Access flags check.
-        if (!getAccessFlags().containsAll(method.accessFlags)
-            || !getNegatedAccessFlags().containsNone(method.accessFlags)) {
-          break;
-        }
-        // Annotations check.
-        if (!RootSetBuilder.containsAnnotation(annotation, method)) {
-          break;
-        }
-        // Parameter types check.
-        List<ProguardTypeMatcher> arguments = getArguments();
-        if (arguments.size() == 1 && arguments.get(0).isTripleDotPattern()) {
-          return true;
-        }
-        DexType[] parameters = originalSignature.proto.parameters.values;
-        if (parameters.length != arguments.size()) {
-          break;
-        }
-        for (int i = 0; i < parameters.length; i++) {
-          if (!arguments.get(i).matches(parameters[i], appView)) {
+        {
+          // Name check.
+          String name = stringCache.lookupString(originalSignature.name);
+          if (!getName().matches(name)) {
+            break;
+          }
+          // Access flags check.
+          if (!getAccessFlags().containsAll(method.accessFlags)
+              || !getNegatedAccessFlags().containsNone(method.accessFlags)) {
+            break;
+          }
+          // Annotations check.
+          if (!RootSetBuilder.containsAnnotation(annotation, method, matchedAnnotationsConsumer)) {
             return false;
           }
+          // Parameter types check.
+          List<ProguardTypeMatcher> arguments = getArguments();
+          if (arguments.size() == 1 && arguments.get(0).isTripleDotPattern()) {
+            return true;
+          }
+          DexType[] parameters = originalSignature.proto.parameters.values;
+          if (parameters.length != arguments.size()) {
+            break;
+          }
+          for (int i = 0; i < parameters.length; i++) {
+            if (!arguments.get(i).matches(parameters[i], appView)) {
+              return false;
+            }
+          }
+          // All parameters matched.
+          return true;
         }
-        // All parameters matched.
-        return true;
+
       case ALL_FIELDS:
       case FIELD:
         break;
@@ -408,5 +428,4 @@
     ruleBuilder.setRuleType(ProguardMemberType.ALL);
     return ruleBuilder.build();
   }
-
 }
diff --git a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
index f5fc58f..6ae1edb 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
@@ -27,6 +27,8 @@
 import com.android.tools.r8.graph.ResolutionResult.SingleResolutionResult;
 import com.android.tools.r8.ir.analysis.proto.GeneratedMessageLiteBuilderShrinker;
 import com.android.tools.r8.logging.Log;
+import com.android.tools.r8.shaking.AnnotationMatchResult.AnnotationsIgnoredMatchResult;
+import com.android.tools.r8.shaking.AnnotationMatchResult.ConcreteAnnotationMatchResult;
 import com.android.tools.r8.shaking.DelayedRootSetActionItem.InterfaceMethodSyntheticBridgeAction;
 import com.android.tools.r8.utils.ArrayUtils;
 import com.android.tools.r8.utils.Consumer3;
@@ -62,6 +64,7 @@
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Future;
+import java.util.function.Consumer;
 import java.util.function.Predicate;
 import java.util.stream.Collectors;
 
@@ -120,6 +123,10 @@
     this(appView, appView.appInfo().app(), null);
   }
 
+  void handleMatchedAnnotation(AnnotationMatchResult annotation) {
+    // Intentionally empty.
+  }
+
   // Process a class with the keep rule.
   private void process(
       DexClass clazz,
@@ -131,9 +138,11 @@
     if (!satisfyAccessFlag(rule, clazz)) {
       return;
     }
-    if (!satisfyAnnotation(rule, clazz)) {
+    AnnotationMatchResult annotationMatchResult = satisfyAnnotation(rule, clazz);
+    if (annotationMatchResult == null) {
       return;
     }
+    handleMatchedAnnotation(annotationMatchResult);
     // In principle it should make a difference whether the user specified in a class
     // spec that a class either extends or implements another type. However, proguard
     // seems not to care, so users have started to use this inconsistently. We are thus
@@ -143,96 +152,93 @@
       return;
     }
 
-    if (rule.getClassNames().matches(clazz.type)) {
-      Collection<ProguardMemberRule> memberKeepRules = rule.getMemberRules();
-      Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier;
-      if (rule instanceof ProguardKeepRule) {
-        if (clazz.isNotProgramClass()) {
-          return;
-        }
-        switch (((ProguardKeepRule) rule).getType()) {
-          case KEEP_CLASS_MEMBERS:
-            // Members mentioned at -keepclassmembers always depend on their holder.
-            preconditionSupplier = ImmutableMap.of(definition -> true, clazz);
-            markMatchingVisibleMethods(
-                clazz, memberKeepRules, rule, preconditionSupplier, false, ifRule);
-            markMatchingVisibleFields(
-                clazz, memberKeepRules, rule, preconditionSupplier, false, ifRule);
-            break;
-          case KEEP_CLASSES_WITH_MEMBERS:
-            if (!allRulesSatisfied(memberKeepRules, clazz)) {
-              break;
-            }
-            // fallthrough;
-          case KEEP:
-            markClass(clazz, rule, ifRule);
-            preconditionSupplier = new HashMap<>();
-            if (ifRule != null) {
-              // Static members in -keep are pinned no matter what.
-              preconditionSupplier.put(DexDefinition::isStaticMember, null);
-              // Instance members may need to be kept even though the holder is not instantiated.
-              preconditionSupplier.put(definition -> !definition.isStaticMember(), clazz);
-            } else {
-              // Members mentioned at -keep should always be pinned as long as that -keep rule is
-              // not triggered conditionally.
-              preconditionSupplier.put((definition -> true), null);
-            }
-            markMatchingVisibleMethods(
-                clazz, memberKeepRules, rule, preconditionSupplier, false, ifRule);
-            markMatchingVisibleFields(
-                clazz, memberKeepRules, rule, preconditionSupplier, false, ifRule);
-            break;
-          case CONDITIONAL:
-            throw new Unreachable("-if rule will be evaluated separately, not here.");
-        }
+    if (!rule.getClassNames().matches(clazz.type)) {
+      return;
+    }
+
+    Collection<ProguardMemberRule> memberKeepRules = rule.getMemberRules();
+    Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier;
+    if (rule instanceof ProguardKeepRule) {
+      if (clazz.isNotProgramClass()) {
         return;
       }
-      // Only the ordinary keep rules are supported in a conditional rule.
-      assert ifRule == null;
-      if (rule instanceof ProguardIfRule) {
-        throw new Unreachable("-if rule will be evaluated separately, not here.");
-      } else if (rule instanceof ProguardCheckDiscardRule) {
-        if (memberKeepRules.isEmpty()) {
-          markClass(clazz, rule, ifRule);
-        } else {
-          preconditionSupplier = ImmutableMap.of((definition -> true), clazz);
+      switch (((ProguardKeepRule) rule).getType()) {
+        case KEEP_CLASS_MEMBERS:
+          // Members mentioned at -keepclassmembers always depend on their holder.
+          preconditionSupplier = ImmutableMap.of(definition -> true, clazz);
           markMatchingVisibleMethods(
-              clazz, memberKeepRules, rule, preconditionSupplier, true, ifRule);
+              clazz, memberKeepRules, rule, preconditionSupplier, false, ifRule);
           markMatchingVisibleFields(
-              clazz, memberKeepRules, rule, preconditionSupplier, true, ifRule);
-        }
-      } else if (rule instanceof ProguardWhyAreYouKeepingRule) {
-        markClass(clazz, rule, ifRule);
-        markMatchingVisibleMethods(clazz, memberKeepRules, rule, null, true, ifRule);
-        markMatchingVisibleFields(clazz, memberKeepRules, rule, null, true, ifRule);
-      } else if (rule instanceof ProguardAssumeMayHaveSideEffectsRule
-          || rule instanceof ProguardAssumeNoSideEffectRule
-          || rule instanceof ProguardAssumeValuesRule) {
-        markMatchingVisibleMethods(clazz, memberKeepRules, rule, null, true, ifRule);
-        markMatchingOverriddenMethods(
-            appView.appInfo(), clazz, memberKeepRules, rule, null, true, ifRule);
-        markMatchingVisibleFields(clazz, memberKeepRules, rule, null, true, ifRule);
-      } else if (rule instanceof ClassMergingRule) {
-        if (allRulesSatisfied(memberKeepRules, clazz)) {
+              clazz, memberKeepRules, rule, preconditionSupplier, false, ifRule);
+          break;
+        case KEEP_CLASSES_WITH_MEMBERS:
+          if (!allRulesSatisfied(memberKeepRules, clazz)) {
+            break;
+          }
+          // fallthrough;
+        case KEEP:
           markClass(clazz, rule, ifRule);
-        }
-      } else if (rule instanceof InlineRule
-          || rule instanceof ConstantArgumentRule
-          || rule instanceof UnusedArgumentRule
-          || rule instanceof WhyAreYouNotInliningRule) {
-        markMatchingMethods(clazz, memberKeepRules, rule, null, ifRule);
-      } else if (rule instanceof ClassInlineRule) {
-        if (allRulesSatisfied(memberKeepRules, clazz)) {
-          markClass(clazz, rule, ifRule);
-        }
-      } else if (rule instanceof MemberValuePropagationRule) {
-        markMatchingVisibleMethods(clazz, memberKeepRules, rule, null, true, ifRule);
-        markMatchingVisibleFields(clazz, memberKeepRules, rule, null, true, ifRule);
-      } else {
-        assert rule instanceof ProguardIdentifierNameStringRule;
-        markMatchingFields(clazz, memberKeepRules, rule, null, ifRule);
-        markMatchingMethods(clazz, memberKeepRules, rule, null, ifRule);
+          preconditionSupplier = new HashMap<>();
+          if (ifRule != null) {
+            // Static members in -keep are pinned no matter what.
+            preconditionSupplier.put(DexDefinition::isStaticMember, null);
+            // Instance members may need to be kept even though the holder is not instantiated.
+            preconditionSupplier.put(definition -> !definition.isStaticMember(), clazz);
+          } else {
+            // Members mentioned at -keep should always be pinned as long as that -keep rule is
+            // not triggered conditionally.
+            preconditionSupplier.put((definition -> true), null);
+          }
+          markMatchingVisibleMethods(
+              clazz, memberKeepRules, rule, preconditionSupplier, false, ifRule);
+          markMatchingVisibleFields(
+              clazz, memberKeepRules, rule, preconditionSupplier, false, ifRule);
+          break;
+        case CONDITIONAL:
+          throw new Unreachable("-if rule will be evaluated separately, not here.");
       }
+      return;
+    }
+    // Only the ordinary keep rules are supported in a conditional rule.
+    assert ifRule == null;
+    if (rule instanceof ProguardIfRule) {
+      throw new Unreachable("-if rule will be evaluated separately, not here.");
+    } else if (rule instanceof ProguardCheckDiscardRule) {
+      if (memberKeepRules.isEmpty()) {
+        markClass(clazz, rule, ifRule);
+      } else {
+        preconditionSupplier = ImmutableMap.of((definition -> true), clazz);
+        markMatchingVisibleMethods(
+            clazz, memberKeepRules, rule, preconditionSupplier, true, ifRule);
+        markMatchingVisibleFields(clazz, memberKeepRules, rule, preconditionSupplier, true, ifRule);
+      }
+    } else if (rule instanceof ProguardWhyAreYouKeepingRule) {
+      markClass(clazz, rule, ifRule);
+      markMatchingVisibleMethods(clazz, memberKeepRules, rule, null, true, ifRule);
+      markMatchingVisibleFields(clazz, memberKeepRules, rule, null, true, ifRule);
+    } else if (rule instanceof ProguardAssumeMayHaveSideEffectsRule
+        || rule instanceof ProguardAssumeNoSideEffectRule
+        || rule instanceof ProguardAssumeValuesRule) {
+      markMatchingVisibleMethods(clazz, memberKeepRules, rule, null, true, ifRule);
+      markMatchingOverriddenMethods(
+          appView.appInfo(), clazz, memberKeepRules, rule, null, true, ifRule);
+      markMatchingVisibleFields(clazz, memberKeepRules, rule, null, true, ifRule);
+    } else if (rule instanceof InlineRule
+        || rule instanceof ConstantArgumentRule
+        || rule instanceof UnusedArgumentRule
+        || rule instanceof WhyAreYouNotInliningRule) {
+      markMatchingMethods(clazz, memberKeepRules, rule, null, ifRule);
+    } else if (rule instanceof ClassInlineRule || rule instanceof ClassMergingRule) {
+      if (allRulesSatisfied(memberKeepRules, clazz)) {
+        markClass(clazz, rule, ifRule);
+      }
+    } else if (rule instanceof MemberValuePropagationRule) {
+      markMatchingVisibleMethods(clazz, memberKeepRules, rule, null, true, ifRule);
+      markMatchingVisibleFields(clazz, memberKeepRules, rule, null, true, ifRule);
+    } else {
+      assert rule instanceof ProguardIdentifierNameStringRule;
+      markMatchingFields(clazz, memberKeepRules, rule, null, ifRule);
+      markMatchingMethods(clazz, memberKeepRules, rule, null, ifRule);
     }
   }
 
@@ -496,6 +502,10 @@
       this.ifRule = ifRule;
     }
 
+    void handleMatchedAnnotation(AnnotationMatchResult annotationMatchResult) {
+      // Intentionally empty.
+    }
+
     void run() {
       visitAllSuperInterfaces(originalClazz.type);
     }
@@ -522,7 +532,7 @@
           continue;
         }
         for (ProguardMemberRule rule : memberKeepRules) {
-          if (rule.matches(method, appView, dexStringCache)) {
+          if (rule.matches(method, appView, this::handleMatchedAnnotation, dexStringCache)) {
             tryAndKeepMethodOnClass(method, rule);
           }
         }
@@ -723,7 +733,7 @@
         && rule.getNegatedClassAccessFlags().containsNone(clazz.accessFlags);
   }
 
-  static boolean satisfyAnnotation(ProguardConfigurationRule rule, DexClass clazz) {
+  static AnnotationMatchResult satisfyAnnotation(ProguardConfigurationRule rule, DexClass clazz) {
     return containsAnnotation(rule.getClassAnnotation(), clazz);
   }
 
@@ -754,9 +764,13 @@
       // TODO(b/110141157): Should the vertical class merger move annotations from the source to
       // the target class? If so, it is sufficient only to apply the annotation-matcher to the
       // annotations of `class`.
-      if (rule.getInheritanceClassName().matches(clazz.type, appView)
-          && containsAnnotation(rule.getInheritanceAnnotation(), clazz)) {
-        return true;
+      if (rule.getInheritanceClassName().matches(clazz.type, appView)) {
+        AnnotationMatchResult annotationMatchResult =
+            containsAnnotation(rule.getInheritanceAnnotation(), clazz);
+        if (annotationMatchResult != null) {
+          handleMatchedAnnotation(annotationMatchResult);
+          return true;
+        }
       }
       type = clazz.superType;
     }
@@ -787,9 +801,13 @@
       // TODO(b/110141157): Should the vertical class merger move annotations from the source to
       // the target class? If so, it is sufficient only to apply the annotation-matcher to the
       // annotations of `ifaceClass`.
-      if (rule.getInheritanceClassName().matches(iface, appView)
-          && containsAnnotation(rule.getInheritanceAnnotation(), ifaceClass)) {
-        return true;
+      if (rule.getInheritanceClassName().matches(iface, appView)) {
+        AnnotationMatchResult annotationMatchResult =
+            containsAnnotation(rule.getInheritanceAnnotation(), ifaceClass);
+        if (annotationMatchResult != null) {
+          handleMatchedAnnotation(annotationMatchResult);
+          return true;
+        }
       }
       if (anyImplementedInterfaceMatchesImplementsRule(ifaceClass, rule)) {
         return true;
@@ -842,7 +860,7 @@
   boolean ruleSatisfiedByMethods(ProguardMemberRule rule, Iterable<DexEncodedMethod> methods) {
     if (rule.getRuleType().includesMethods()) {
       for (DexEncodedMethod method : methods) {
-        if (rule.matches(method, appView, dexStringCache)) {
+        if (rule.matches(method, appView, this::handleMatchedAnnotation, dexStringCache)) {
           return true;
         }
       }
@@ -853,7 +871,7 @@
   boolean ruleSatisfiedByFields(ProguardMemberRule rule, Iterable<DexEncodedField> fields) {
     if (rule.getRuleType().includesFields()) {
       for (DexEncodedField field : fields) {
-        if (rule.matches(field, appView, dexStringCache)) {
+        if (rule.matches(field, appView, this::handleMatchedAnnotation, dexStringCache)) {
           return true;
         }
       }
@@ -861,40 +879,56 @@
     return false;
   }
 
-  static boolean containsAnnotation(ProguardTypeMatcher classAnnotation, DexClass clazz) {
+  static AnnotationMatchResult containsAnnotation(
+      ProguardTypeMatcher classAnnotation, DexClass clazz) {
     return containsAnnotation(classAnnotation, clazz.annotations);
   }
 
-  static boolean containsAnnotation(ProguardTypeMatcher classAnnotation, DexEncodedMethod method) {
-    if (containsAnnotation(classAnnotation, method.annotations)) {
+  static boolean containsAnnotation(
+      ProguardTypeMatcher classAnnotation,
+      DexEncodedField field,
+      Consumer<AnnotationMatchResult> matchedAnnotationsConsumer) {
+    AnnotationMatchResult annotationMatchResult =
+        containsAnnotation(classAnnotation, field.annotations);
+    if (annotationMatchResult != null) {
+      matchedAnnotationsConsumer.accept(annotationMatchResult);
+      return true;
+    }
+    return false;
+  }
+
+  static boolean containsAnnotation(
+      ProguardTypeMatcher classAnnotation,
+      DexEncodedMethod method,
+      Consumer<AnnotationMatchResult> matchedAnnotationsConsumer) {
+    AnnotationMatchResult annotationMatchResult =
+        containsAnnotation(classAnnotation, method.annotations);
+    if (annotationMatchResult != null) {
+      matchedAnnotationsConsumer.accept(annotationMatchResult);
       return true;
     }
     for (int i = 0; i < method.parameterAnnotationsList.size(); i++) {
-      if (containsAnnotation(classAnnotation, method.parameterAnnotationsList.get(i))) {
+      annotationMatchResult =
+          containsAnnotation(classAnnotation, method.parameterAnnotationsList.get(i));
+      if (annotationMatchResult != null) {
+        matchedAnnotationsConsumer.accept(annotationMatchResult);
         return true;
       }
     }
     return false;
   }
 
-  static boolean containsAnnotation(ProguardTypeMatcher classAnnotation, DexEncodedField field) {
-    return containsAnnotation(classAnnotation, field.annotations);
-  }
-
-  private static boolean containsAnnotation(
+  private static AnnotationMatchResult containsAnnotation(
       ProguardTypeMatcher classAnnotation, DexAnnotationSet annotations) {
     if (classAnnotation == null) {
-      return true;
-    }
-    if (annotations.isEmpty()) {
-      return false;
+      return AnnotationsIgnoredMatchResult.getInstance();
     }
     for (DexAnnotation annotation : annotations.annotations) {
       if (classAnnotation.matches(annotation.annotation.type)) {
-        return true;
+        return new ConcreteAnnotationMatchResult(annotation);
       }
     }
-    return false;
+    return null;
   }
 
   private void markMethod(
@@ -910,7 +944,7 @@
       return;
     }
     for (ProguardMemberRule rule : rules) {
-      if (rule.matches(method, appView, dexStringCache)) {
+      if (rule.matches(method, appView, this::handleMatchedAnnotation, dexStringCache)) {
         if (Log.ENABLED) {
           Log.verbose(getClass(), "Marking method `%s` due to `%s { %s }`.", method, context,
               rule);
@@ -930,7 +964,7 @@
       DexDefinition precondition,
       ProguardIfRule ifRule) {
     for (ProguardMemberRule rule : rules) {
-      if (rule.matches(field, appView, dexStringCache)) {
+      if (rule.matches(field, appView, this::handleMatchedAnnotation, dexStringCache)) {
         if (Log.ENABLED) {
           Log.verbose(getClass(), "Marking field `%s` due to `%s { %s }`.", field, context,
               rule);
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 9ed931c..2de4c37 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -435,6 +435,11 @@
     return enableMinification;
   }
 
+  public boolean keepInnerClassStructure() {
+    return getProguardConfiguration().getKeepAttributes().signature
+        || getProguardConfiguration().getKeepAttributes().innerClasses;
+  }
+
   public boolean printCfg = false;
   public String printCfgFile;
   public boolean ignoreMissingClasses = false;
diff --git a/src/test/java/com/android/tools/r8/shaking/annotations/B149729626.java b/src/test/java/com/android/tools/r8/shaking/annotations/B149729626.java
index e0c497c..5b8f418 100644
--- a/src/test/java/com/android/tools/r8/shaking/annotations/B149729626.java
+++ b/src/test/java/com/android/tools/r8/shaking/annotations/B149729626.java
@@ -43,11 +43,7 @@
         .addKeepRules(
             "-keepclassmembers @" + Marker.class.getTypeName() + " class * {",
             "  <init>(...);",
-            "}",
-            // TODO(b/149729626): Should not be required.
-            "-keep class " + TestClass.class.getTypeName() + " { void makeMarkerLive(); }")
-        // TODO(b/149729626): Should not be required.
-        .addKeepRuntimeVisibleAnnotations()
+            "}")
         .setMinApi(parameters.getApiLevel())
         .compile()
         .inspect(this::inspect)
@@ -64,11 +60,7 @@
             "-if @" + Marker.class.getTypeName() + " class *",
             "-keep class <1> {",
             "  <init>(...);",
-            "}",
-            // TODO(b/149729626): Should not be required.
-            "-keep class " + TestClass.class.getTypeName() + " { void makeMarkerLive(); }")
-        // TODO(b/149729626): Should not be required.
-        .addKeepRuntimeVisibleAnnotations()
+            "}")
         .setMinApi(parameters.getApiLevel())
         .compile()
         .inspect(this::inspect)
@@ -99,10 +91,6 @@
     public static void main(String[] args) {
       System.out.println(Marked.class);
     }
-
-    static void makeMarkerLive() {
-      System.out.println(Marker.class);
-    }
   }
 
   @Target(ElementType.TYPE)