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 4383f00..2fdb279 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -389,6 +389,10 @@
     return getReference().getParameters();
   }
 
+  public DexType getReturnType() {
+    return getReference().getReturnType();
+  }
+
   public DexMethodSignature getSignature() {
     return new DexMethodSignature(getReference());
   }
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 4024023..02aea63 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -11,6 +11,7 @@
 import static com.android.tools.r8.naming.IdentifierNameStringUtils.identifyIdentifier;
 import static com.android.tools.r8.naming.IdentifierNameStringUtils.isReflectionMethod;
 import static com.android.tools.r8.utils.FunctionUtils.ignoreArgument;
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
 import static java.util.Collections.emptySet;
 
 import com.android.tools.r8.Diagnostic;
@@ -111,14 +112,15 @@
 import com.android.tools.r8.naming.identifiernamestring.IdentifierNameStringTypeLookupResult;
 import com.android.tools.r8.shaking.AnnotationMatchResult.MatchedAnnotation;
 import com.android.tools.r8.shaking.DelayedRootSetActionItem.InterfaceMethodSyntheticBridgeAction;
+import com.android.tools.r8.shaking.EnqueuerEvent.ClassEnqueuerEvent;
+import com.android.tools.r8.shaking.EnqueuerEvent.InstantiatedClassEnqueuerEvent;
+import com.android.tools.r8.shaking.EnqueuerEvent.LiveClassEnqueuerEvent;
 import com.android.tools.r8.shaking.EnqueuerWorklist.EnqueuerAction;
 import com.android.tools.r8.shaking.GraphReporter.KeepReasonWitness;
-import com.android.tools.r8.shaking.KeepInfo.Joiner;
 import com.android.tools.r8.shaking.KeepInfoCollection.MutableKeepInfoCollection;
 import com.android.tools.r8.shaking.RootSetUtils.ConsequentRootSet;
 import com.android.tools.r8.shaking.RootSetUtils.ConsequentRootSetBuilder;
 import com.android.tools.r8.shaking.RootSetUtils.ItemsWithRules;
-import com.android.tools.r8.shaking.RootSetUtils.MutableItemsWithRules;
 import com.android.tools.r8.shaking.RootSetUtils.RootSet;
 import com.android.tools.r8.shaking.RootSetUtils.RootSetBuilder;
 import com.android.tools.r8.shaking.ScopedDexMethodSet.AddMethodIfMoreVisibleResult;
@@ -135,7 +137,9 @@
 import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.Visibility;
 import com.android.tools.r8.utils.WorkList;
+import com.android.tools.r8.utils.collections.ProgramFieldMap;
 import com.android.tools.r8.utils.collections.ProgramFieldSet;
+import com.android.tools.r8.utils.collections.ProgramMethodMap;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.ImmutableSet;
@@ -283,6 +287,10 @@
    */
   private final SetWithReportedReason<DexProgramClass> liveTypes = new SetWithReportedReason<>();
 
+  /** Set of interfaces that have been transitioned to being instantiated indirectly. */
+  private final Set<DexProgramClass> interfacesTransitionedToInstantiated =
+      Sets.newIdentityHashSet();
+
   /** Set of classes whose initializer may execute. */
   private final SetWithReportedReason<DexProgramClass> initializedClasses =
       new SetWithReportedReason<>();
@@ -378,6 +386,30 @@
   private final MutableKeepInfoCollection keepInfo = new MutableKeepInfoCollection();
 
   /**
+   * The minimum keep info for classes, fields, and methods. The minimum keep info for a program
+   * item should be applied to the {@link KeepInfo} of that item when the item becomes live.
+   */
+  private final Map<DexProgramClass, KeepClassInfo.Joiner> minimumKeepClassInfo =
+      new IdentityHashMap<>();
+
+  private final ProgramFieldMap<KeepFieldInfo.Joiner> minimumKeepFieldInfo =
+      ProgramFieldMap.create();
+  private final ProgramMethodMap<KeepMethodInfo.Joiner> minimumKeepMethodInfo =
+      ProgramMethodMap.create();
+
+  /**
+   * Conditional minimum keep info for classes, fields, and methods, which should only be applied if
+   * the outermost {@link EnqueuerEvent} is triggered during tracing (e.g., class X becomes live).
+   */
+  private final Map<EnqueuerEvent, Map<DexProgramClass, KeepClassInfo.Joiner>>
+      dependentMinimumKeepClassInfo = new HashMap<>();
+
+  private final Map<EnqueuerEvent, ProgramFieldMap<KeepFieldInfo.Joiner>>
+      dependentMinimumKeepFieldInfo = new HashMap<>();
+  private final Map<EnqueuerEvent, ProgramMethodMap<KeepMethodInfo.Joiner>>
+      dependentMinimumKeepMethodInfo = new HashMap<>();
+
+  /**
    * A set of seen const-class references that serve as an initial lock-candidate set and will
    * prevent class merging.
    */
@@ -863,10 +895,6 @@
         method, graphReporter.reportKeepMethod(precondition, rules, method.getDefinition()));
   }
 
-  private void enqueueRootItem(ProgramDefinition item, Set<ProguardKeepRuleBase> rules) {
-    internalEnqueueRootItem(item, rules, null);
-  }
-
   private void internalEnqueueRootItem(
       ProgramDefinition item, Set<ProguardKeepRuleBase> rules, DexDefinition precondition) {
     if (item.isProgramClass()) {
@@ -1830,7 +1858,9 @@
       enqueueFirstNonSerializableClassInitializer(clazz, reason);
     }
 
-    checkDefinitionForSoftPinning(clazz);
+    // Update keep info.
+    applyMinimumKeepInfo(clazz);
+    applyMinimumKeepInfoDependentOn(new LiveClassEnqueuerEvent(clazz));
 
     processAnnotations(clazz);
 
@@ -2622,16 +2652,46 @@
   }
 
   private void transitionDependentItemsForInstantiatedItem(DexProgramClass clazz) {
-    do {
-      // Handle keep rules that are dependent on the class being instantiated.
-      rootSet.forEachDependentNonStaticMember(clazz, appView, this::enqueueDependentMember);
+    WorkList<DexProgramClass> interfacesToTransition =
+        WorkList.newWorkList(interfacesTransitionedToInstantiated);
+    if (clazz.getAccessFlags().isInterface()) {
+      interfacesToTransition.addIfNotSeen(clazz);
+    } else {
+      do {
+        // Handle keep rules that are dependent on the class being instantiated.
+        rootSet.forEachDependentNonStaticMember(clazz, appView, this::enqueueDependentMember);
+        applyMinimumKeepInfoDependentOn(new InstantiatedClassEnqueuerEvent(clazz));
 
-      // Visit the super type.
-      clazz =
-          clazz.superType != null
-              ? asProgramClassOrNull(appView.definitionFor(clazz.superType))
-              : null;
-    } while (clazz != null && !objectAllocationInfoCollection.isInstantiatedDirectly(clazz));
+        for (DexType interfaceType : clazz.getInterfaces()) {
+          DexProgramClass interfaceClass =
+              asProgramClassOrNull(definitionFor(interfaceType, clazz));
+          if (interfaceClass != null) {
+            interfacesToTransition.addIfNotSeen(interfaceClass);
+          }
+        }
+
+        // Visit the super type.
+        clazz =
+            clazz.superType != null
+                ? asProgramClassOrNull(appView.definitionFor(clazz.superType))
+                : null;
+      } while (clazz != null && !objectAllocationInfoCollection.isInstantiatedDirectly(clazz));
+    }
+
+    while (interfacesToTransition.hasNext()) {
+      DexProgramClass interfaceClass = interfacesToTransition.next();
+      rootSet.forEachDependentNonStaticMember(
+          interfaceClass, appView, this::enqueueDependentMember);
+      applyMinimumKeepInfoDependentOn(new InstantiatedClassEnqueuerEvent(interfaceClass));
+
+      for (DexType indirectInterfaceType : interfaceClass.getInterfaces()) {
+        DexProgramClass indirectInterfaceClass =
+            asProgramClassOrNull(definitionFor(indirectInterfaceType, interfaceClass));
+        if (indirectInterfaceClass != null) {
+          interfacesToTransition.addIfNotSeen(indirectInterfaceClass);
+        }
+      }
+    }
   }
 
   private void transitionUnusedInterfaceToLive(DexProgramClass clazz) {
@@ -2670,11 +2730,12 @@
       traceFieldDefinition(field);
     }
 
+    // Update keep info.
+    applyMinimumKeepInfo(field);
+
     // Add all dependent members to the workqueue.
     enqueueRootItems(rootSet.getDependentItems(field.getDefinition()));
 
-    checkDefinitionForSoftPinning(field);
-
     // Notify analyses.
     analyses.forEach(analysis -> analysis.processNewlyLiveField(field, context));
   }
@@ -2773,6 +2834,27 @@
         : info.isWritten();
   }
 
+  public boolean isPreconditionForMinimumKeepInfoSatisfied(EnqueuerEvent preconditionEvent) {
+    if (preconditionEvent == null) {
+      return true;
+    }
+    if (preconditionEvent.isClassEvent()) {
+      ClassEnqueuerEvent classEvent = preconditionEvent.asClassEvent();
+      DexProgramClass clazz = asProgramClassOrNull(appView.definitionFor(classEvent.getType()));
+      if (clazz == null) {
+        return false;
+      }
+      if (preconditionEvent.isLiveClassEvent()) {
+        return liveTypes.contains(clazz);
+      }
+      if (preconditionEvent.isInstantiatedClassEvent()) {
+        return objectAllocationInfoCollection.isInstantiatedDirectlyOrHasInstantiatedSubtype(clazz);
+      }
+    }
+    assert false;
+    return false;
+  }
+
   public boolean isMemberLive(DexEncodedMember<?, ?> member) {
     assert member != null;
     return member.isDexEncodedField()
@@ -2808,7 +2890,7 @@
   }
 
   public void forAllLiveClasses(Consumer<DexProgramClass> consumer) {
-    liveTypes.items.forEach(consumer);
+    liveTypes.getItems().forEach(consumer);
   }
 
   private void markVirtualMethodAsReachable(
@@ -3046,29 +3128,26 @@
     if (appView.options().apiModelingOptions().enableApiCallerIdentification) {
       registerAnalysis(new ApiModelAnalysis(appView, apiReferenceLevelCache));
     }
+
+    // Transfer the minimum keep info from the root set into the Enqueuer state.
+    rootSet.forEachMinimumKeepInfo(
+        appView,
+        this::recordDependentMinimumKeepInfo,
+        this::recordDependentMinimumKeepInfo,
+        this::recordDependentMinimumKeepInfo);
+
     if (mode.isInitialTreeShaking()) {
       // This is simulating the effect of the "root set" applied rules.
       // This is done only in the initial pass, in subsequent passes the "rules" are reapplied
       // by iterating the instances.
-      assert appView.options().isAnnotationRemovalEnabled()
-          || rootSet.noAnnotationRemoval.isEmpty();
-      assert appView.options().isMinificationEnabled() || rootSet.noObfuscation.isEmpty();
-      for (DexReference reference : rootSet.noAnnotationRemoval) {
-        keepInfo.evaluateRule(reference, appInfo, Joiner::disallowAnnotationRemoval);
-      }
-      for (DexReference reference : rootSet.noObfuscation) {
-        keepInfo.evaluateRule(reference, appInfo, Joiner::disallowMinification);
-      }
     } else if (appView.getKeepInfo() != null) {
       appView
           .getKeepInfo()
-          .getRuleInstances()
-          .forEach(
-              (reference, rules) -> {
-                for (Consumer<Joiner<?, ?, ?>> rule : rules) {
-                  keepInfo.evaluateRule(reference, appInfo, rule);
-                }
-              });
+          .forEachRuleInstance(
+              appView,
+              this::applyMinimumKeepInfoWhenLive,
+              this::applyMinimumKeepInfoWhenLive,
+              this::applyMinimumKeepInfoWhenLiveOrTargeted);
     }
     if (appView.options().isShrinking() || appView.options().getProguardConfiguration() == null) {
       enqueueRootItems(rootSet.noShrinking);
@@ -3106,18 +3185,133 @@
     return createEnqueuerResult(appInfo);
   }
 
+  private void applyMinimumKeepInfo(DexProgramClass clazz) {
+    KeepClassInfo.Joiner minimumKeepInfoForClass = minimumKeepClassInfo.remove(clazz);
+    if (minimumKeepInfoForClass != null) {
+      keepInfo.joinClass(clazz, info -> info.merge(minimumKeepInfoForClass));
+    }
+  }
+
+  private void applyMinimumKeepInfoWhenLive(
+      DexProgramClass clazz, KeepClassInfo.Joiner minimumKeepInfo) {
+    if (liveTypes.contains(clazz)) {
+      keepInfo.joinClass(clazz, info -> info.merge(minimumKeepInfo));
+    } else {
+      minimumKeepClassInfo
+          .computeIfAbsent(clazz, ignoreKey(KeepClassInfo::newEmptyJoiner))
+          .merge(minimumKeepInfo);
+    }
+  }
+
+  private void recordDependentMinimumKeepInfo(
+      EnqueuerEvent preconditionEvent,
+      DexProgramClass clazz,
+      KeepClassInfo.Joiner minimumKeepInfo) {
+    if (isPreconditionForMinimumKeepInfoSatisfied(preconditionEvent)) {
+      applyMinimumKeepInfoWhenLive(clazz, minimumKeepInfo);
+    } else {
+      dependentMinimumKeepClassInfo
+          .computeIfAbsent(preconditionEvent, ignoreKey(IdentityHashMap::new))
+          .computeIfAbsent(clazz, ignoreKey(KeepClassInfo::newEmptyJoiner))
+          .merge(minimumKeepInfo);
+    }
+  }
+
+  private void applyMinimumKeepInfo(ProgramField field) {
+    KeepFieldInfo.Joiner minimumKeepInfoForField = minimumKeepFieldInfo.remove(field);
+    if (minimumKeepInfoForField != null) {
+      keepInfo.joinField(field, info -> info.merge(minimumKeepInfoForField));
+    }
+  }
+
+  private void applyMinimumKeepInfoWhenLive(
+      ProgramField field, KeepFieldInfo.Joiner minimumKeepInfo) {
+    if (liveFields.contains(field)) {
+      keepInfo.joinField(field, info -> info.merge(minimumKeepInfo));
+    } else {
+      minimumKeepFieldInfo
+          .computeIfAbsent(field, ignoreKey(KeepFieldInfo::newEmptyJoiner))
+          .merge(minimumKeepInfo);
+    }
+  }
+
+  private void recordDependentMinimumKeepInfo(
+      EnqueuerEvent preconditionEvent, ProgramField field, KeepFieldInfo.Joiner minimumKeepInfo) {
+    if (isPreconditionForMinimumKeepInfoSatisfied(preconditionEvent)) {
+      applyMinimumKeepInfoWhenLive(field, minimumKeepInfo);
+    } else {
+      dependentMinimumKeepFieldInfo
+          .computeIfAbsent(preconditionEvent, ignoreKey(ProgramFieldMap::create))
+          .computeIfAbsent(field, ignoreKey(KeepFieldInfo::newEmptyJoiner))
+          .merge(minimumKeepInfo);
+    }
+  }
+
+  private void applyMinimumKeepInfo(ProgramMethod method) {
+    KeepMethodInfo.Joiner minimumKeepInfoForMethod = minimumKeepMethodInfo.remove(method);
+    if (minimumKeepInfoForMethod != null) {
+      keepInfo.joinMethod(method, info -> info.merge(minimumKeepInfoForMethod));
+    }
+  }
+
+  private void applyMinimumKeepInfoWhenLiveOrTargeted(
+      ProgramMethod method, KeepMethodInfo.Joiner minimumKeepInfo) {
+    if (liveMethods.contains(method) || targetedMethods.contains(method)) {
+      keepInfo.joinMethod(method, info -> info.merge(minimumKeepInfo));
+    } else {
+      minimumKeepMethodInfo
+          .computeIfAbsent(method, ignoreKey(KeepMethodInfo::newEmptyJoiner))
+          .merge(minimumKeepInfo);
+    }
+  }
+
+  private void recordDependentMinimumKeepInfo(
+      EnqueuerEvent preconditionEvent,
+      ProgramMethod method,
+      KeepMethodInfo.Joiner minimumKeepInfo) {
+    if (isPreconditionForMinimumKeepInfoSatisfied(preconditionEvent)) {
+      applyMinimumKeepInfoWhenLiveOrTargeted(method, minimumKeepInfo);
+    } else {
+      dependentMinimumKeepMethodInfo
+          .computeIfAbsent(preconditionEvent, ignoreKey(ProgramMethodMap::create))
+          .computeIfAbsent(method, ignoreKey(KeepMethodInfo::newEmptyJoiner))
+          .merge(minimumKeepInfo);
+    }
+  }
+
+  private void applyMinimumKeepInfoDependentOn(EnqueuerEvent precondition) {
+    Map<DexProgramClass, KeepClassInfo.Joiner> minimumKeepClassInfoDependentOnPrecondition =
+        dependentMinimumKeepClassInfo.remove(precondition);
+    if (minimumKeepClassInfoDependentOnPrecondition != null) {
+      minimumKeepClassInfoDependentOnPrecondition.forEach(this::applyMinimumKeepInfoWhenLive);
+    }
+
+    ProgramFieldMap<KeepFieldInfo.Joiner> minimumKeepFieldInfoDependentOnPrecondition =
+        dependentMinimumKeepFieldInfo.remove(precondition);
+    if (minimumKeepFieldInfoDependentOnPrecondition != null) {
+      minimumKeepFieldInfoDependentOnPrecondition.forEach(this::applyMinimumKeepInfoWhenLive);
+    }
+
+    ProgramMethodMap<KeepMethodInfo.Joiner> minimumKeepMethodInfoDependentOnPrecondition =
+        dependentMinimumKeepMethodInfo.remove(precondition);
+    if (minimumKeepMethodInfoDependentOnPrecondition != null) {
+      minimumKeepMethodInfoDependentOnPrecondition.forEach(
+          this::applyMinimumKeepInfoWhenLiveOrTargeted);
+    }
+  }
+
   private void keepClassWithRules(DexProgramClass clazz, Set<ProguardKeepRuleBase> rules) {
     keepInfo.joinClass(clazz, info -> applyKeepRules(clazz, rules, info));
   }
 
-  private void keepMethodWithRules(ProgramMethod method, Set<ProguardKeepRuleBase> rules) {
-    keepInfo.joinMethod(method, info -> applyKeepRules(method, rules, info));
-  }
-
   private void keepFieldWithRules(ProgramField field, Set<ProguardKeepRuleBase> rules) {
     keepInfo.joinField(field, info -> applyKeepRules(field, rules, info));
   }
 
+  private void keepMethodWithRules(ProgramMethod method, Set<ProguardKeepRuleBase> rules) {
+    keepInfo.joinMethod(method, info -> applyKeepRules(method, rules, info));
+  }
+
   private void applyKeepRules(
       ProgramDefinition definition,
       Set<ProguardKeepRuleBase> rules,
@@ -3674,8 +3868,8 @@
         Set<DexEncodedMethod> reachableNotLive = Sets.difference(allLive, liveMethods.getItems());
         Log.debug(getClass(), "%s methods are reachable but not live", reachableNotLive.size());
         Log.info(getClass(), "Only reachable: %s", reachableNotLive);
-        SetView<DexEncodedMethod> targetedButNotLive = Sets
-            .difference(targetedMethods.getItems(), liveMethods.getItems());
+        SetView<DexEncodedMethod> targetedButNotLive =
+            Sets.difference(targetedMethods.getItems(), liveMethods.getItems());
         Log.debug(getClass(), "%s methods are targeted but not live", targetedButNotLive.size());
         Log.info(getClass(), "Targeted but not live: %s", targetedButNotLive);
       }
@@ -3715,7 +3909,7 @@
   }
 
   private long getNumberOfLiveItems() {
-    long result = liveTypes.items.size();
+    long result = liveTypes.getItems().size();
     result += liveMethods.items.size();
     result += liveFields.fields.size();
     return result;
@@ -3746,31 +3940,18 @@
             enqueueRootItems(dependentItems);
           }
         });
-    consequentRootSet.dependentSoftPinned.forEach(
-        (reference, dependentItems) -> {
-          if (isLiveProgramReference(reference)) {
-            dependentItems.forEachReference(
-                item -> {
-                  if (isLiveProgramReference(item)) {
-                    keepInfo.joinInfo(item, appView, Joiner::pin);
-                  }
-                });
-          }
-        });
 
     // TODO(b/132600955): This modifies the root set. Should the consequent be persistent?
     rootSet.addConsequentRootSet(consequentRootSet, addNoShrinking);
-    if (mode.isInitialTreeShaking()) {
-      for (DexReference reference : consequentRootSet.noAnnotationRemoval) {
-        keepInfo.evaluateRule(reference, appView, Joiner::disallowAnnotationRemoval);
-      }
-      for (DexReference reference : consequentRootSet.noObfuscation) {
-        keepInfo.evaluateRule(reference, appView, Joiner::disallowMinification);
-      }
-      consequentRootSet.softPinned.forEachReference(
-          reference -> keepInfo.evaluateRule(reference, appView, Joiner::pin));
-    }
+
     enqueueRootItems(consequentRootSet.noShrinking);
+
+    consequentRootSet.forEachMinimumKeepInfo(
+        appView,
+        this::recordDependentMinimumKeepInfo,
+        this::recordDependentMinimumKeepInfo,
+        this::recordDependentMinimumKeepInfo);
+
     // Check for compatibility rules indicating that the holder must be implicitly kept.
     if (forceProguardCompatibility) {
       consequentRootSet.dependentKeepClassCompatRule.forEach(
@@ -3783,19 +3964,6 @@
     }
   }
 
-  private boolean isLiveProgramReference(DexReference reference) {
-    if (reference.isDexType()) {
-      DexProgramClass clazz =
-          DexProgramClass.asProgramClassOrNull(appInfo().definitionFor(reference.asDexType()));
-      return clazz != null && isTypeLive(clazz);
-    }
-    DexMember<?, ?> member = reference.asDexMember();
-    DexProgramClass holder =
-        DexProgramClass.asProgramClassOrNull(appInfo().definitionFor(member.holder));
-    ProgramMember<?, ?> programMember = member.lookupOnProgramClass(holder);
-    return programMember != null && isMemberLive(programMember.getDefinition());
-  }
-
   private ConsequentRootSet computeDelayedInterfaceMethodSyntheticBridges() {
     RootSetBuilder builder = RootSet.builder(appView, subtypingInfo);
     for (DelayedRootSetActionItem delayedRootSetActionItem : rootSet.delayedRootSetActionItems) {
@@ -4016,7 +4184,6 @@
   }
 
   void traceMethodDefinitionExcludingCode(ProgramMethod method) {
-    checkDefinitionForSoftPinning(method);
     markReferencedTypesAsLive(method);
     processAnnotations(method);
     method
@@ -4024,6 +4191,9 @@
         .getParameterAnnotations()
         .forEachAnnotation(
             annotation -> processAnnotation(method, annotation, AnnotatedKind.PARAMETER));
+
+    // Update keep info.
+    applyMinimumKeepInfo(method);
   }
 
   private void traceNonDesugaredCode(ProgramMethod method) {
@@ -4043,22 +4213,6 @@
     analyses.forEach(analysis -> analysis.processTracedCode(method, registry));
   }
 
-  private void checkDefinitionForSoftPinning(ProgramDefinition definition) {
-    DexReference reference = definition.getReference();
-    Set<ProguardKeepRuleBase> softPinRules = rootSet.softPinned.getRulesForReference(reference);
-    if (softPinRules != null) {
-      assert softPinRules.stream().noneMatch(r -> r.getModifiers().allowsOptimization);
-      keepInfo.joinInfo(reference, appInfo, Joiner::pin);
-    }
-    // Identify dependent soft pinning.
-    MutableItemsWithRules items = rootSet.dependentSoftPinned.get(definition.getContextType());
-    if (items != null && items.containsReference(reference)) {
-      assert items.getRulesForReference(reference).stream()
-          .noneMatch(r -> r.getModifiers().allowsOptimization);
-      keepInfo.joinInfo(reference, appInfo, Joiner::pin);
-    }
-  }
-
   private void markReferencedTypesAsLive(ProgramMethod method) {
     markTypeAsLive(method.getHolder(), method);
     markParameterAndReturnTypesAsLive(method);
@@ -4575,30 +4729,6 @@
     }
   }
 
-  private static class SetWithReason<T> {
-
-    private final Set<T> items = Sets.newIdentityHashSet();
-
-    private final BiConsumer<T, KeepReason> register;
-
-    public SetWithReason(BiConsumer<T, KeepReason> register) {
-      this.register = register;
-    }
-
-    boolean add(T item, KeepReason reason) {
-      register.accept(item, reason);
-      return items.add(item);
-    }
-
-    boolean contains(T item) {
-      return items.contains(item);
-    }
-
-    Set<T> getItems() {
-      return Collections.unmodifiableSet(items);
-    }
-  }
-
   private class AnnotationReferenceMarker implements IndexedItemCollection {
 
     private final ProgramDefinition context;
diff --git a/src/main/java/com/android/tools/r8/shaking/EnqueuerEvent.java b/src/main/java/com/android/tools/r8/shaking/EnqueuerEvent.java
new file mode 100644
index 0000000..6f68a59
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/EnqueuerEvent.java
@@ -0,0 +1,126 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.shaking;
+
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
+
+public abstract class EnqueuerEvent {
+
+  public boolean isClassEvent() {
+    return false;
+  }
+
+  public ClassEnqueuerEvent asClassEvent() {
+    return null;
+  }
+
+  public boolean isLiveClassEvent() {
+    return false;
+  }
+
+  public LiveClassEnqueuerEvent asLiveClassEvent() {
+    return null;
+  }
+
+  public boolean isInstantiatedClassEvent() {
+    return false;
+  }
+
+  public InstantiatedClassEnqueuerEvent asInstantiatedClassEvent() {
+    return null;
+  }
+
+  public abstract static class ClassEnqueuerEvent extends EnqueuerEvent {
+
+    private final DexType clazz;
+
+    public ClassEnqueuerEvent(DexProgramClass clazz) {
+      this.clazz = clazz.getType();
+    }
+
+    public DexType getType() {
+      return clazz;
+    }
+
+    @Override
+    public boolean isClassEvent() {
+      return true;
+    }
+
+    @Override
+    public ClassEnqueuerEvent asClassEvent() {
+      return this;
+    }
+  }
+
+  public static class LiveClassEnqueuerEvent extends ClassEnqueuerEvent {
+
+    public LiveClassEnqueuerEvent(DexProgramClass clazz) {
+      super(clazz);
+    }
+
+    @Override
+    public boolean isLiveClassEvent() {
+      return true;
+    }
+
+    @Override
+    public LiveClassEnqueuerEvent asLiveClassEvent() {
+      return this;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      if (obj == this) {
+        return true;
+      }
+      if (obj instanceof LiveClassEnqueuerEvent) {
+        LiveClassEnqueuerEvent event = (LiveClassEnqueuerEvent) obj;
+        return getType() == event.getType();
+      }
+      return false;
+    }
+
+    @Override
+    public int hashCode() {
+      return (getType().hashCode() << 1) | 0;
+    }
+  }
+
+  public static class InstantiatedClassEnqueuerEvent extends ClassEnqueuerEvent {
+
+    public InstantiatedClassEnqueuerEvent(DexProgramClass clazz) {
+      super(clazz);
+    }
+
+    @Override
+    public boolean isInstantiatedClassEvent() {
+      return true;
+    }
+
+    @Override
+    public InstantiatedClassEnqueuerEvent asInstantiatedClassEvent() {
+      return this;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      if (obj == this) {
+        return true;
+      }
+      if (obj instanceof InstantiatedClassEnqueuerEvent) {
+        InstantiatedClassEnqueuerEvent event = (InstantiatedClassEnqueuerEvent) obj;
+        return getType() == event.getType();
+      }
+      return false;
+    }
+
+    @Override
+    public int hashCode() {
+      return (getType().hashCode() << 1) | 1;
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/GlobalKeepInfoConfiguration.java b/src/main/java/com/android/tools/r8/shaking/GlobalKeepInfoConfiguration.java
index cd2df59..1eeaa21 100644
--- a/src/main/java/com/android/tools/r8/shaking/GlobalKeepInfoConfiguration.java
+++ b/src/main/java/com/android/tools/r8/shaking/GlobalKeepInfoConfiguration.java
@@ -12,6 +12,8 @@
 
   boolean isMinificationEnabled();
 
+  boolean isOptimizationEnabled();
+
   boolean isAccessModificationEnabled();
 
   boolean isRepackagingEnabled();
diff --git a/src/main/java/com/android/tools/r8/shaking/KeepClassInfo.java b/src/main/java/com/android/tools/r8/shaking/KeepClassInfo.java
index 3110521..dc4a931 100644
--- a/src/main/java/com/android/tools/r8/shaking/KeepClassInfo.java
+++ b/src/main/java/com/android/tools/r8/shaking/KeepClassInfo.java
@@ -27,6 +27,10 @@
     return BOTTOM;
   }
 
+  public static Joiner newEmptyJoiner() {
+    return bottom().joiner();
+  }
+
   private KeepClassInfo(Builder builder) {
     super(builder);
   }
@@ -127,6 +131,17 @@
     }
 
     @Override
+    public Joiner asClassJoiner() {
+      return this;
+    }
+
+    @Override
+    public Joiner merge(Joiner joiner) {
+      // Should be extended to merge the fields of this class in case any are added.
+      return super.merge(joiner);
+    }
+
+    @Override
     Joiner self() {
       return this;
     }
diff --git a/src/main/java/com/android/tools/r8/shaking/KeepFieldInfo.java b/src/main/java/com/android/tools/r8/shaking/KeepFieldInfo.java
index 30e79e2..0c54589 100644
--- a/src/main/java/com/android/tools/r8/shaking/KeepFieldInfo.java
+++ b/src/main/java/com/android/tools/r8/shaking/KeepFieldInfo.java
@@ -20,6 +20,10 @@
     return BOTTOM;
   }
 
+  public static Joiner newEmptyJoiner() {
+    return bottom().joiner();
+  }
+
   private KeepFieldInfo(Builder builder) {
     super(builder);
   }
@@ -89,6 +93,17 @@
     }
 
     @Override
+    public Joiner asFieldJoiner() {
+      return this;
+    }
+
+    @Override
+    public Joiner merge(Joiner joiner) {
+      // Should be extended to merge the fields of this class in case any are added.
+      return super.merge(joiner);
+    }
+
+    @Override
     Joiner self() {
       return this;
     }
diff --git a/src/main/java/com/android/tools/r8/shaking/KeepInfo.java b/src/main/java/com/android/tools/r8/shaking/KeepInfo.java
index 0d5fc1b..b795aab 100644
--- a/src/main/java/com/android/tools/r8/shaking/KeepInfo.java
+++ b/src/main/java/com/android/tools/r8/shaking/KeepInfo.java
@@ -6,6 +6,7 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.EnclosingMethodAttribute;
 import com.android.tools.r8.shaking.KeepInfo.Builder;
+import java.util.function.Consumer;
 
 /** Keep information that can be associated with any item, i.e., class, method or field. */
 public abstract class KeepInfo<B extends Builder<B, K>, K extends KeepInfo<B, K>> {
@@ -14,6 +15,8 @@
   private final boolean allowAccessModification;
   private final boolean allowAnnotationRemoval;
   private final boolean allowMinification;
+  private final boolean allowOptimization;
+  private final boolean allowShrinking;
   private final boolean requireAccessModificationForRepackaging;
 
   private KeepInfo(
@@ -21,11 +24,15 @@
       boolean allowAccessModification,
       boolean allowAnnotationRemoval,
       boolean allowMinification,
+      boolean allowOptimization,
+      boolean allowShrinking,
       boolean requireAccessModificationForRepackaging) {
     this.pinned = pinned;
     this.allowAccessModification = allowAccessModification;
     this.allowAnnotationRemoval = allowAnnotationRemoval;
     this.allowMinification = allowMinification;
+    this.allowOptimization = allowOptimization;
+    this.allowShrinking = allowShrinking;
     this.requireAccessModificationForRepackaging = requireAccessModificationForRepackaging;
   }
 
@@ -35,6 +42,8 @@
         builder.isAccessModificationAllowed(),
         builder.isAnnotationRemovalAllowed(),
         builder.isMinificationAllowed(),
+        builder.isOptimizationAllowed(),
+        builder.isShrinkingAllowed(),
         builder.isAccessModificationRequiredForRepackaging());
   }
 
@@ -61,7 +70,7 @@
    */
   @Deprecated
   public boolean isPinned() {
-    return pinned;
+    return pinned || !allowOptimization;
   }
 
   /**
@@ -79,6 +88,34 @@
   }
 
   /**
+   * True if an item may be optimized (i.e., the item is not soft pinned).
+   *
+   * <p>This method requires knowledge of the global configuration as that can override the concrete
+   * value on a given item.
+   */
+  public boolean isOptimizationAllowed(GlobalKeepInfoConfiguration configuration) {
+    return configuration.isOptimizationEnabled() && internalIsOptimizationAllowed();
+  }
+
+  boolean internalIsOptimizationAllowed() {
+    return allowOptimization;
+  }
+
+  /**
+   * True if an item is subject to shrinking (i.e., tree shaking).
+   *
+   * <p>This method requires knowledge of the global configuration as that can override the concrete
+   * value on a given item.
+   */
+  public boolean isShrinkingAllowed(GlobalKeepInfoConfiguration configuration) {
+    return configuration.isTreeShakingEnabled() && internalIsShrinkingAllowed();
+  }
+
+  boolean internalIsShrinkingAllowed() {
+    return allowShrinking;
+  }
+
+  /**
    * True if an item may be repackaged.
    *
    * <p>This method requires knowledge of the global configuration as that can override the concrete
@@ -156,7 +193,11 @@
     // An item is less, aka, lower in the lattice, if each of its attributes is at least as
     // permissive of that on other.
     return (!pinned || other.isPinned())
-        && (allowAccessModification || !other.internalIsAccessModificationAllowed());
+        && (allowAccessModification || !other.internalIsAccessModificationAllowed())
+        && (allowAnnotationRemoval || !other.internalIsAnnotationRemovalAllowed())
+        && (allowMinification || !other.internalIsMinificationAllowed())
+        && (allowOptimization || !other.internalIsOptimizationAllowed())
+        && (allowShrinking || !other.internalIsShrinkingAllowed());
   }
 
   /** Builder to construct an arbitrary keep info object. */
@@ -177,6 +218,8 @@
     private boolean allowAccessModification;
     private boolean allowAnnotationRemoval;
     private boolean allowMinification;
+    private boolean allowOptimization;
+    private boolean allowShrinking;
     private boolean requireAccessModificationForRepackaging;
 
     Builder() {
@@ -189,6 +232,8 @@
       allowAccessModification = original.internalIsAccessModificationAllowed();
       allowAnnotationRemoval = original.internalIsAnnotationRemovalAllowed();
       allowMinification = original.internalIsMinificationAllowed();
+      allowOptimization = original.internalIsOptimizationAllowed();
+      allowShrinking = original.internalIsShrinkingAllowed();
       requireAccessModificationForRepackaging =
           original.internalIsAccessModificationRequiredForRepackaging();
     }
@@ -198,6 +243,8 @@
       disallowAccessModification();
       disallowAnnotationRemoval();
       disallowMinification();
+      disallowOptimization();
+      disallowShrinking();
       requireAccessModificationForRepackaging();
       return self();
     }
@@ -207,6 +254,8 @@
       allowAccessModification();
       allowAnnotationRemoval();
       allowMinification();
+      allowOptimization();
+      allowShrinking();
       unsetRequireAccessModificationForRepackaging();
       return self();
     }
@@ -231,6 +280,8 @@
           && isAccessModificationAllowed() == other.internalIsAccessModificationAllowed()
           && isAnnotationRemovalAllowed() == other.internalIsAnnotationRemovalAllowed()
           && isMinificationAllowed() == other.internalIsMinificationAllowed()
+          && isOptimizationAllowed() == other.internalIsOptimizationAllowed()
+          && isShrinkingAllowed() == other.internalIsShrinkingAllowed()
           && isAccessModificationRequiredForRepackaging()
               == other.internalIsAccessModificationRequiredForRepackaging();
     }
@@ -255,6 +306,14 @@
       return allowMinification;
     }
 
+    public boolean isOptimizationAllowed() {
+      return allowOptimization;
+    }
+
+    public boolean isShrinkingAllowed() {
+      return allowShrinking;
+    }
+
     public B setPinned(boolean pinned) {
       this.pinned = pinned;
       return self();
@@ -281,6 +340,32 @@
       return setAllowMinification(false);
     }
 
+    public B setAllowOptimization(boolean allowOptimization) {
+      this.allowOptimization = allowOptimization;
+      return self();
+    }
+
+    public B allowOptimization() {
+      return setAllowOptimization(true);
+    }
+
+    public B disallowOptimization() {
+      return setAllowOptimization(false);
+    }
+
+    public B setAllowShrinking(boolean allowShrinking) {
+      this.allowShrinking = allowShrinking;
+      return self();
+    }
+
+    public B allowShrinking() {
+      return setAllowShrinking(true);
+    }
+
+    public B disallowShrinking() {
+      return setAllowShrinking(false);
+    }
+
     public B setRequireAccessModificationForRepackaging(
         boolean requireAccessModificationForRepackaging) {
       this.requireAccessModificationForRepackaging = requireAccessModificationForRepackaging;
@@ -328,12 +413,35 @@
 
     abstract J self();
 
-    private final Builder<B, K> builder;
+    final Builder<B, K> builder;
 
     Joiner(Builder<B, K> builder) {
       this.builder = builder;
     }
 
+    public J applyIf(boolean condition, Consumer<J> thenConsumer) {
+      if (condition) {
+        thenConsumer.accept(self());
+      }
+      return self();
+    }
+
+    public KeepClassInfo.Joiner asClassJoiner() {
+      return null;
+    }
+
+    public KeepFieldInfo.Joiner asFieldJoiner() {
+      return null;
+    }
+
+    public KeepMethodInfo.Joiner asMethodJoiner() {
+      return null;
+    }
+
+    public boolean isBottom() {
+      return builder.isEqualTo(builder.getBottomInfo());
+    }
+
     public boolean isTop() {
       return builder.isEqualTo(builder.getTopInfo());
     }
@@ -363,11 +471,35 @@
       return self();
     }
 
+    public J disallowOptimization() {
+      builder.disallowOptimization();
+      return self();
+    }
+
+    public J disallowShrinking() {
+      builder.disallowShrinking();
+      return self();
+    }
+
     public J requireAccessModificationForRepackaging() {
       builder.requireAccessModificationForRepackaging();
       return self();
     }
 
+    public J merge(J joiner) {
+      Builder<B, K> builder = joiner.builder;
+      applyIf(builder.isPinned(), Joiner::pin);
+      applyIf(!builder.isAccessModificationAllowed(), Joiner::disallowAccessModification);
+      applyIf(!builder.isAnnotationRemovalAllowed(), Joiner::disallowAnnotationRemoval);
+      applyIf(!builder.isMinificationAllowed(), Joiner::disallowMinification);
+      applyIf(!builder.isOptimizationAllowed(), Joiner::disallowOptimization);
+      applyIf(!builder.isShrinkingAllowed(), Joiner::disallowShrinking);
+      applyIf(
+          builder.isAccessModificationRequiredForRepackaging(),
+          Joiner::requireAccessModificationForRepackaging);
+      return self();
+    }
+
     public K join() {
       K joined = builder.build();
       K original = builder.original;
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 ddd5bfc..71068d2 100644
--- a/src/main/java/com/android/tools/r8/shaking/KeepInfoCollection.java
+++ b/src/main/java/com/android/tools/r8/shaking/KeepInfoCollection.java
@@ -4,8 +4,11 @@
 package com.android.tools.r8.shaking;
 
 import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
 
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMember;
@@ -22,17 +25,25 @@
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.shaking.KeepFieldInfo.Joiner;
 import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.MapUtils;
 import com.google.common.collect.Streams;
-import java.util.ArrayList;
 import java.util.IdentityHashMap;
-import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.function.BiConsumer;
 import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.Supplier;
 
 // Non-mutable collection of keep information pertaining to a program.
 public abstract class KeepInfoCollection {
 
+  abstract void forEachRuleInstance(
+      AppView<? extends AppInfoWithClassHierarchy> appView,
+      BiConsumer<DexProgramClass, KeepClassInfo.Joiner> classRuleInstanceConsumer,
+      BiConsumer<ProgramField, KeepFieldInfo.Joiner> fieldRuleInstanceConsumer,
+      BiConsumer<ProgramMethod, KeepMethodInfo.Joiner> methodRuleInstanceConsumer);
+
   // TODO(b/157538235): This should not be bottom.
   private static KeepClassInfo keepInfoForNonProgramClass() {
     return KeepClassInfo.bottom();
@@ -48,8 +59,6 @@
     return KeepFieldInfo.bottom();
   }
 
-  abstract Map<DexReference, List<Consumer<KeepInfo.Joiner<?, ?, ?>>>> getRuleInstances();
-
   /**
    * Base accessor for keep info on a class.
    *
@@ -195,13 +204,17 @@
     private final Map<DexField, KeepFieldInfo> keepFieldInfo;
 
     // Map of applied rules for which keys may need to be mutated.
-    private final Map<DexReference, List<Consumer<KeepInfo.Joiner<?, ?, ?>>>> ruleInstances;
+    private final Map<DexType, KeepClassInfo.Joiner> classRuleInstances;
+    private final Map<DexField, KeepFieldInfo.Joiner> fieldRuleInstances;
+    private final Map<DexMethod, KeepMethodInfo.Joiner> methodRuleInstances;
 
     MutableKeepInfoCollection() {
       this(
           new IdentityHashMap<>(),
           new IdentityHashMap<>(),
           new IdentityHashMap<>(),
+          new IdentityHashMap<>(),
+          new IdentityHashMap<>(),
           new IdentityHashMap<>());
     }
 
@@ -209,11 +222,15 @@
         Map<DexType, KeepClassInfo> keepClassInfo,
         Map<DexMethod, KeepMethodInfo> keepMethodInfo,
         Map<DexField, KeepFieldInfo> keepFieldInfo,
-        Map<DexReference, List<Consumer<KeepInfo.Joiner<?, ?, ?>>>> ruleInstances) {
+        Map<DexType, KeepClassInfo.Joiner> classRuleInstances,
+        Map<DexField, KeepFieldInfo.Joiner> fieldRuleInstances,
+        Map<DexMethod, KeepMethodInfo.Joiner> methodRuleInstances) {
       this.keepClassInfo = keepClassInfo;
       this.keepMethodInfo = keepMethodInfo;
       this.keepFieldInfo = keepFieldInfo;
-      this.ruleInstances = ruleInstances;
+      this.classRuleInstances = classRuleInstances;
+      this.fieldRuleInstances = fieldRuleInstances;
+      this.methodRuleInstances = methodRuleInstances;
     }
 
     public void removeKeepInfoForPrunedItems(Set<DexType> removedClasses) {
@@ -265,42 +282,96 @@
             KeepFieldInfo previous = newFieldInfo.put(newField, info);
             assert previous == null;
           });
-      Map<DexReference, List<Consumer<KeepInfo.Joiner<?, ?, ?>>>> newRuleInstances =
-          new IdentityHashMap<>(ruleInstances.size());
-      ruleInstances.forEach(
-          (reference, consumers) -> {
-            DexReference newReference;
-            if (reference.isDexType()) {
-              DexType newType = lens.lookupType(reference.asDexType());
-              if (!newType.isClassType()) {
-                assert newType.isIntType() : "Expected only enum unboxing type changes.";
-                return;
-              }
-              newReference = newType;
-            } else if (reference.isDexMethod()) {
-              newReference = lens.getRenamedMethodSignature(reference.asDexMethod());
-            } else {
-              assert reference.isDexField();
-              newReference = lens.getRenamedFieldSignature(reference.asDexField());
-            }
-            newRuleInstances.put(newReference, consumers);
-          });
       return new MutableKeepInfoCollection(
-          newClassInfo, newMethodInfo, newFieldInfo, newRuleInstances);
+          newClassInfo,
+          newMethodInfo,
+          newFieldInfo,
+          rewriteRuleInstances(
+              classRuleInstances,
+              clazz -> {
+                DexType rewritten = lens.lookupType(clazz);
+                if (rewritten.isClassType()) {
+                  return rewritten;
+                }
+                assert rewritten.isIntType();
+                return null;
+              },
+              KeepClassInfo::newEmptyJoiner),
+          rewriteRuleInstances(
+              fieldRuleInstances, lens::getRenamedFieldSignature, KeepFieldInfo::newEmptyJoiner),
+          rewriteRuleInstances(
+              methodRuleInstances,
+              lens::getRenamedMethodSignature,
+              KeepMethodInfo::newEmptyJoiner));
+    }
+
+    private static <R, J extends KeepInfo.Joiner<J, ?, ?>> Map<R, J> rewriteRuleInstances(
+        Map<R, J> ruleInstances, Function<R, R> rewriter, Supplier<J> newEmptyJoiner) {
+      return MapUtils.transform(
+          ruleInstances,
+          IdentityHashMap::new,
+          rewriter,
+          Function.identity(),
+          (joiner, otherJoiner) -> newEmptyJoiner.get().merge(joiner).merge(otherJoiner));
     }
 
     @Override
-    Map<DexReference, List<Consumer<KeepInfo.Joiner<?, ?, ?>>>> getRuleInstances() {
-      return ruleInstances;
+    void forEachRuleInstance(
+        AppView<? extends AppInfoWithClassHierarchy> appView,
+        BiConsumer<DexProgramClass, KeepClassInfo.Joiner> classRuleInstanceConsumer,
+        BiConsumer<ProgramField, KeepFieldInfo.Joiner> fieldRuleInstanceConsumer,
+        BiConsumer<ProgramMethod, KeepMethodInfo.Joiner> methodRuleInstanceConsumer) {
+      classRuleInstances.forEach(
+          (type, ruleInstance) -> {
+            DexProgramClass clazz = asProgramClassOrNull(appView.definitionFor(type));
+            if (clazz != null) {
+              classRuleInstanceConsumer.accept(clazz, ruleInstance);
+            }
+          });
+      fieldRuleInstances.forEach(
+          (fieldReference, ruleInstance) -> {
+            DexProgramClass holder =
+                asProgramClassOrNull(appView.definitionFor(fieldReference.getHolderType()));
+            ProgramField field = holder.lookupProgramField(fieldReference);
+            if (field != null) {
+              fieldRuleInstanceConsumer.accept(field, ruleInstance);
+            }
+          });
+      methodRuleInstances.forEach(
+          (methodReference, ruleInstance) -> {
+            DexProgramClass holder =
+                asProgramClassOrNull(appView.definitionFor(methodReference.getHolderType()));
+            ProgramMethod method = holder.lookupProgramMethod(methodReference);
+            if (method != null) {
+              methodRuleInstanceConsumer.accept(method, ruleInstance);
+            }
+          });
     }
 
-    void evaluateRule(
-        DexReference reference,
-        DexDefinitionSupplier definitions,
-        Consumer<KeepInfo.Joiner<?, ?, ?>> fn) {
-      joinInfo(reference, definitions, fn);
-      if (!getInfo(reference, definitions).isBottom()) {
-        ruleInstances.computeIfAbsent(reference, k -> new ArrayList<>()).add(fn);
+    void evaluateClassRule(DexProgramClass clazz, KeepClassInfo.Joiner minimumKeepInfo) {
+      if (!minimumKeepInfo.isBottom()) {
+        joinClass(clazz, joiner -> joiner.merge(minimumKeepInfo));
+        classRuleInstances
+            .computeIfAbsent(clazz.getType(), ignoreKey(KeepClassInfo::newEmptyJoiner))
+            .merge(minimumKeepInfo);
+      }
+    }
+
+    void evaluateFieldRule(ProgramField field, KeepFieldInfo.Joiner minimumKeepInfo) {
+      if (!minimumKeepInfo.isBottom()) {
+        joinField(field, joiner -> joiner.merge(minimumKeepInfo));
+        fieldRuleInstances
+            .computeIfAbsent(field.getReference(), ignoreKey(KeepFieldInfo::newEmptyJoiner))
+            .merge(minimumKeepInfo);
+      }
+    }
+
+    void evaluateMethodRule(ProgramMethod method, KeepMethodInfo.Joiner minimumKeepInfo) {
+      if (!minimumKeepInfo.isBottom()) {
+        joinMethod(method, joiner -> joiner.merge(minimumKeepInfo));
+        methodRuleInstances
+            .computeIfAbsent(method.getReference(), ignoreKey(KeepMethodInfo::newEmptyJoiner))
+            .merge(minimumKeepInfo);
       }
     }
 
@@ -321,9 +392,10 @@
       return keepFieldInfo.getOrDefault(field.getReference(), KeepFieldInfo.bottom());
     }
 
-    public void joinClass(DexProgramClass clazz, Consumer<KeepClassInfo.Joiner> fn) {
+    public void joinClass(DexProgramClass clazz, Consumer<? super KeepClassInfo.Joiner> fn) {
       KeepClassInfo info = getClassInfo(clazz);
       if (info.isTop()) {
+        assert info == KeepClassInfo.top();
         return;
       }
       KeepClassInfo.Joiner joiner = info.joiner();
@@ -334,34 +406,6 @@
       }
     }
 
-    public void joinInfo(
-        DexReference reference,
-        DexDefinitionSupplier definitions,
-        Consumer<KeepInfo.Joiner<?, ?, ?>> fn) {
-      if (reference.isDexType()) {
-        DexType type = reference.asDexType();
-        DexProgramClass clazz = asProgramClassOrNull(definitions.definitionFor(type));
-        if (clazz != null) {
-          joinClass(clazz, fn::accept);
-        }
-      } else if (reference.isDexMethod()) {
-        DexMethod method = reference.asDexMethod();
-        DexProgramClass clazz = asProgramClassOrNull(definitions.definitionFor(method.holder));
-        ProgramMethod definition = method.lookupOnProgramClass(clazz);
-        if (definition != null) {
-          joinMethod(definition, fn::accept);
-        }
-      } else {
-        assert reference.isDexField();
-        DexField field = reference.asDexField();
-        DexProgramClass clazz = asProgramClassOrNull(definitions.definitionFor(field.holder));
-        ProgramField definition = field.lookupOnProgramClass(clazz);
-        if (definition != null) {
-          joinField(definition, fn::accept);
-        }
-      }
-    }
-
     public void keepClass(DexProgramClass clazz) {
       joinClass(clazz, KeepInfo.Joiner::top);
     }
@@ -370,9 +414,10 @@
       joinClass(clazz, KeepInfo.Joiner::pin);
     }
 
-    public void joinMethod(ProgramMethod method, Consumer<KeepMethodInfo.Joiner> fn) {
+    public void joinMethod(ProgramMethod method, Consumer<? super KeepMethodInfo.Joiner> fn) {
       KeepMethodInfo info = getMethodInfo(method);
-      if (info == KeepMethodInfo.top()) {
+      if (info.isTop()) {
+        assert info == KeepMethodInfo.top();
         return;
       }
       KeepMethodInfo.Joiner joiner = info.joiner();
@@ -423,9 +468,10 @@
       }
     }
 
-    public void joinField(ProgramField field, Consumer<KeepFieldInfo.Joiner> fn) {
+    public void joinField(ProgramField field, Consumer<? super KeepFieldInfo.Joiner> fn) {
       KeepFieldInfo info = getFieldInfo(field);
       if (info.isTop()) {
+        assert info == KeepFieldInfo.top();
         return;
       }
       Joiner joiner = info.joiner();
diff --git a/src/main/java/com/android/tools/r8/shaking/KeepMethodInfo.java b/src/main/java/com/android/tools/r8/shaking/KeepMethodInfo.java
index daeeaf0..1669a40 100644
--- a/src/main/java/com/android/tools/r8/shaking/KeepMethodInfo.java
+++ b/src/main/java/com/android/tools/r8/shaking/KeepMethodInfo.java
@@ -20,6 +20,10 @@
     return BOTTOM;
   }
 
+  public static Joiner newEmptyJoiner() {
+    return bottom().joiner();
+  }
+
   private KeepMethodInfo(Builder builder) {
     super(builder);
   }
@@ -89,6 +93,17 @@
     }
 
     @Override
+    public Joiner asMethodJoiner() {
+      return this;
+    }
+
+    @Override
+    public Joiner merge(Joiner joiner) {
+      // Should be extended to merge the fields of this class in case any are added.
+      return super.merge(joiner);
+    }
+
+    @Override
     Joiner self() {
       return this;
     }
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardKeepRuleModifiers.java b/src/main/java/com/android/tools/r8/shaking/ProguardKeepRuleModifiers.java
index 63c0787..3021c88 100644
--- a/src/main/java/com/android/tools/r8/shaking/ProguardKeepRuleModifiers.java
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardKeepRuleModifiers.java
@@ -82,6 +82,15 @@
     return new Builder();
   }
 
+  public boolean isBottom() {
+    return allowsAccessModification
+        && allowsAnnotationRemoval
+        && allowsObfuscation
+        && allowsOptimization
+        && allowsShrinking
+        && !includeDescriptorClasses;
+  }
+
   @Override
   public boolean equals(Object o) {
     if (!(o instanceof ProguardKeepRuleModifiers)) {
diff --git a/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java b/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
index e622ca7..28094a1 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetUtils.java
@@ -5,6 +5,8 @@
 
 import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
 import static com.android.tools.r8.utils.LensUtils.rewriteAndApplyIfNotPrimitiveType;
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
+import static java.util.Collections.emptyMap;
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.AssumeNoSideEffectsRuleForObjectMembersDiagnostic;
@@ -34,6 +36,7 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
 import com.android.tools.r8.graph.GraphLens;
+import com.android.tools.r8.graph.ProgramField;
 import com.android.tools.r8.graph.ProgramMember;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.graph.PrunedItems;
@@ -46,6 +49,9 @@
 import com.android.tools.r8.shaking.AnnotationMatchResult.ConcreteAnnotationMatchResult;
 import com.android.tools.r8.shaking.AnnotationMatchResult.MatchedAnnotation;
 import com.android.tools.r8.shaking.DelayedRootSetActionItem.InterfaceMethodSyntheticBridgeAction;
+import com.android.tools.r8.shaking.EnqueuerEvent.InstantiatedClassEnqueuerEvent;
+import com.android.tools.r8.shaking.EnqueuerEvent.LiveClassEnqueuerEvent;
+import com.android.tools.r8.shaking.KeepInfo.Joiner;
 import com.android.tools.r8.utils.ArrayUtils;
 import com.android.tools.r8.utils.Consumer3;
 import com.android.tools.r8.utils.InternalOptions;
@@ -54,6 +60,7 @@
 import com.android.tools.r8.utils.PredicateSet;
 import com.android.tools.r8.utils.StringDiagnostic;
 import com.android.tools.r8.utils.ThreadUtils;
+import com.android.tools.r8.utils.TriConsumer;
 import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
@@ -89,6 +96,39 @@
 
 public class RootSetUtils {
 
+  static void modifyMinimumKeepInfo(
+      Map<DexReference, KeepInfo.Joiner<?, ?, ?>> minimumKeepInfo,
+      DexDefinition definition,
+      Consumer<Joiner<?, ?, ?>> consumer) {
+    modifyMinimumKeepInfo(minimumKeepInfo, definition.getReference(), consumer);
+  }
+
+  static void modifyMinimumKeepInfo(
+      Map<DexReference, KeepInfo.Joiner<?, ?, ?>> minimumKeepInfo,
+      DexReference reference,
+      Consumer<Joiner<?, ?, ?>> consumer) {
+    Joiner<?, ?, ?> joiner =
+        minimumKeepInfo.computeIfAbsent(
+            reference,
+            key ->
+                key.apply(
+                    clazz -> KeepClassInfo.newEmptyJoiner(),
+                    field -> KeepFieldInfo.newEmptyJoiner(),
+                    method -> KeepMethodInfo.newEmptyJoiner()));
+    consumer.accept(joiner);
+    assert !joiner.isBottom();
+  }
+
+  static void modifyDependentMinimumKeepInfo(
+      Map<EnqueuerEvent, Map<DexReference, KeepInfo.Joiner<?, ?, ?>>> dependentMinimumKeepInfo,
+      EnqueuerEvent event,
+      DexDefinition dependent,
+      Consumer<Joiner<?, ?, ?>> consumer) {
+    Map<DexReference, KeepInfo.Joiner<?, ?, ?>> minimumKeepInfoForDependants =
+        dependentMinimumKeepInfo.computeIfAbsent(event, ignoreKey(IdentityHashMap::new));
+    modifyMinimumKeepInfo(minimumKeepInfoForDependants, dependent, consumer);
+  }
+
   public static class RootSetBuilder {
 
     private final AppView<? extends AppInfoWithClassHierarchy> appView;
@@ -96,9 +136,10 @@
     private final DirectMappedDexApplication application;
     private final Iterable<? extends ProguardConfigurationRule> rules;
     private final MutableItemsWithRules noShrinking = new MutableItemsWithRules();
-    private final MutableItemsWithRules softPinned = new MutableItemsWithRules();
-    private final Set<DexReference> noAnnotationRemoval = Sets.newIdentityHashSet();
-    private final Set<DexReference> noObfuscation = Sets.newIdentityHashSet();
+    private final Map<DexReference, KeepInfo.Joiner<?, ?, ?>> minimumKeepInfo =
+        new IdentityHashMap<>();
+    private final Map<EnqueuerEvent, Map<DexReference, KeepInfo.Joiner<?, ?, ?>>>
+        dependentMinimumKeepInfo = new HashMap<>();
     private final LinkedHashMap<DexReference, DexReference> reasonAsked = new LinkedHashMap<>();
     private final LinkedHashMap<DexReference, DexReference> checkDiscarded = new LinkedHashMap<>();
     private final Set<DexMethod> alwaysInline = Sets.newIdentityHashSet();
@@ -119,8 +160,6 @@
     private final Set<DexReference> neverPropagateValue = Sets.newIdentityHashSet();
     private final Map<DexReference, MutableItemsWithRules> dependentNoShrinking =
         new IdentityHashMap<>();
-    private final Map<DexReference, MutableItemsWithRules> dependentSoftPinned =
-        new IdentityHashMap<>();
     private final Map<DexType, Set<ProguardKeepRuleBase>> dependentKeepClassCompatRule =
         new IdentityHashMap<>();
     private final Map<DexReference, ProguardMemberRule> mayHaveSideEffects =
@@ -191,7 +230,7 @@
       }
 
       Collection<ProguardMemberRule> memberKeepRules = rule.getMemberRules();
-      Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier;
+      Map<Predicate<DexDefinition>, DexProgramClass> preconditionSupplier;
       if (rule instanceof ProguardKeepRule) {
         if (clazz.isNotProgramClass()) {
           return;
@@ -199,7 +238,7 @@
         switch (((ProguardKeepRule) rule).getType()) {
           case KEEP_CLASS_MEMBERS:
             // Members mentioned at -keepclassmembers always depend on their holder.
-            preconditionSupplier = ImmutableMap.of(definition -> true, clazz);
+            preconditionSupplier = ImmutableMap.of(definition -> true, clazz.asProgramClass());
             markMatchingVisibleMethods(
                 clazz, memberKeepRules, rule, preconditionSupplier, false, ifRule);
             markMatchingVisibleFields(
@@ -217,7 +256,8 @@
               // 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);
+              preconditionSupplier.put(
+                  definition -> !definition.isStaticMember(), clazz.asProgramClass());
             } else {
               // Members mentioned at -keep should always be pinned as long as that -keep rule is
               // not triggered conditionally.
@@ -238,10 +278,16 @@
       if (rule instanceof ProguardIfRule) {
         throw new Unreachable("-if rule will be evaluated separately, not here.");
       } else if (rule instanceof ProguardCheckDiscardRule) {
-        if (memberKeepRules.isEmpty()) {
+        if (!clazz.isProgramClass()) {
+          appView
+              .reporter()
+              .warning(
+                  new StringDiagnostic(
+                      "The rule `" + rule + "` matches a class not in the program."));
+        } else if (memberKeepRules.isEmpty()) {
           markClass(clazz, rule, ifRule);
         } else {
-          preconditionSupplier = ImmutableMap.of((definition -> true), clazz);
+          preconditionSupplier = ImmutableMap.of((definition -> true), clazz.asProgramClass());
           markMatchingVisibleMethods(
               clazz, memberKeepRules, rule, preconditionSupplier, true, ifRule);
           markMatchingVisibleFields(
@@ -353,13 +399,10 @@
       assert Sets.intersection(neverInline, alwaysInline).isEmpty()
               && Sets.intersection(neverInline, forceInline).isEmpty()
           : "A method cannot be marked as both -neverinline and -forceinline/-alwaysinline.";
-      assert appView.options().isAnnotationRemovalEnabled() || noAnnotationRemoval.isEmpty();
-      assert appView.options().isMinificationEnabled() || noObfuscation.isEmpty();
       return new RootSet(
           noShrinking,
-          softPinned,
-          noAnnotationRemoval,
-          noObfuscation,
+          minimumKeepInfo,
+          dependentMinimumKeepInfo,
           ImmutableList.copyOf(reasonAsked.values()),
           ImmutableList.copyOf(checkDiscarded.values()),
           alwaysInline,
@@ -382,7 +425,6 @@
           noSideEffects,
           assumedValues,
           dependentNoShrinking,
-          dependentSoftPinned,
           dependentKeepClassCompatRule,
           identifierNameStrings,
           ifRules,
@@ -455,24 +497,23 @@
           neverInlineDueToSingleCaller,
           neverClassInline,
           noShrinking,
-          softPinned,
-          noAnnotationRemoval,
-          noObfuscation,
+          minimumKeepInfo,
+          dependentMinimumKeepInfo,
           dependentNoShrinking,
-          dependentSoftPinned,
           dependentKeepClassCompatRule,
           Lists.newArrayList(delayedRootSetActionItems));
     }
 
-    private static DexDefinition testAndGetPrecondition(
+    private static DexProgramClass testAndGetPrecondition(
         DexDefinition definition,
-        Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier) {
+        Map<Predicate<DexDefinition>, DexProgramClass> preconditionSupplier) {
       if (preconditionSupplier == null) {
         return null;
       }
-      DexDefinition precondition = null;
+      DexProgramClass precondition = null;
       boolean conditionEverMatched = false;
-      for (Entry<Predicate<DexDefinition>, DexDefinition> entry : preconditionSupplier.entrySet()) {
+      for (Entry<Predicate<DexDefinition>, DexProgramClass> entry :
+          preconditionSupplier.entrySet()) {
         if (entry.getKey().test(definition)) {
           precondition = entry.getValue();
           conditionEverMatched = true;
@@ -489,7 +530,7 @@
         DexClass clazz,
         Collection<ProguardMemberRule> memberKeepRules,
         ProguardConfigurationRule rule,
-        Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier,
+        Map<Predicate<DexDefinition>, DexProgramClass> preconditionSupplier,
         boolean includeLibraryClasses,
         ProguardIfRule ifRule) {
       Set<Wrapper<DexMethod>> methodsMarked =
@@ -509,7 +550,7 @@
                     || (method.isStatic() && !method.isPrivate() && !method.isInitializer())
                     || options.forceProguardCompatibility,
             method -> {
-              DexDefinition precondition =
+              DexProgramClass precondition =
                   testAndGetPrecondition(method.getDefinition(), preconditionSupplier);
               markMethod(method, memberKeepRules, methodsMarked, rule, precondition, ifRule);
             });
@@ -542,7 +583,7 @@
       private final DexProgramClass originalClazz;
       private final Collection<ProguardMemberRule> memberKeepRules;
       private final ProguardConfigurationRule context;
-      private final Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier;
+      private final Map<Predicate<DexDefinition>, DexProgramClass> preconditionSupplier;
       private final ProguardIfRule ifRule;
       private final Set<Wrapper<DexMethod>> seenMethods = Sets.newHashSet();
       private final Set<DexType> seenTypes = Sets.newIdentityHashSet();
@@ -551,7 +592,7 @@
           DexProgramClass originalClazz,
           Collection<ProguardMemberRule> memberKeepRules,
           ProguardConfigurationRule context,
-          Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier,
+          Map<Predicate<DexDefinition>, DexProgramClass> preconditionSupplier,
           ProguardIfRule ifRule) {
         assert context.isProguardKeepRule();
         assert !context.asProguardKeepRule().getModifiers().allowsShrinking;
@@ -643,7 +684,7 @@
                         context,
                         rule);
                   }
-                  DexDefinition precondition =
+                  DexProgramClass precondition =
                       testAndGetPrecondition(methodToKeep.getDefinition(), preconditionSupplier);
                   rootSetBuilder.addItemToSets(
                       methodToKeep.getDefinition(), context, rule, precondition, ifRule);
@@ -661,7 +702,7 @@
         DexClass clazz,
         Collection<ProguardMemberRule> memberKeepRules,
         ProguardConfigurationRule rule,
-        Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier,
+        Map<Predicate<DexDefinition>, DexProgramClass> preconditionSupplier,
         boolean onlyIncludeProgramClasses,
         ProguardIfRule ifRule) {
       Set<DexType> visited = new HashSet<>();
@@ -685,7 +726,7 @@
         currentClazz.forEachClassMethodMatching(
             DexEncodedMethod::belongsToVirtualPool,
             method -> {
-              DexDefinition precondition =
+              DexProgramClass precondition =
                   testAndGetPrecondition(method.getDefinition(), preconditionSupplier);
               markMethod(method, memberKeepRules, null, rule, precondition, ifRule);
             });
@@ -697,11 +738,11 @@
         DexClass clazz,
         Collection<ProguardMemberRule> memberKeepRules,
         ProguardConfigurationRule rule,
-        Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier,
+        Map<Predicate<DexDefinition>, DexProgramClass> preconditionSupplier,
         ProguardIfRule ifRule) {
       clazz.forEachClassMethod(
           method -> {
-            DexDefinition precondition =
+            DexProgramClass precondition =
                 testAndGetPrecondition(method.getDefinition(), preconditionSupplier);
             markMethod(method, memberKeepRules, null, rule, precondition, ifRule);
           });
@@ -711,7 +752,7 @@
         DexClass clazz,
         Collection<ProguardMemberRule> memberKeepRules,
         ProguardConfigurationRule rule,
-        Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier,
+        Map<Predicate<DexDefinition>, DexProgramClass> preconditionSupplier,
         boolean includeLibraryClasses,
         ProguardIfRule ifRule) {
       while (clazz != null) {
@@ -720,7 +761,7 @@
         }
         clazz.forEachClassField(
             field -> {
-              DexDefinition precondition =
+              DexProgramClass precondition =
                   testAndGetPrecondition(field.getDefinition(), preconditionSupplier);
               markField(field, memberKeepRules, rule, precondition, ifRule);
             });
@@ -732,11 +773,11 @@
         DexClass clazz,
         Collection<ProguardMemberRule> memberKeepRules,
         ProguardConfigurationRule rule,
-        Map<Predicate<DexDefinition>, DexDefinition> preconditionSupplier,
+        Map<Predicate<DexDefinition>, DexProgramClass> preconditionSupplier,
         ProguardIfRule ifRule) {
       clazz.forEachClassField(
           field -> {
-            DexDefinition precondition =
+            DexProgramClass precondition =
                 testAndGetPrecondition(field.getDefinition(), preconditionSupplier);
             markField(field, memberKeepRules, rule, precondition, ifRule);
           });
@@ -1037,7 +1078,7 @@
         Collection<ProguardMemberRule> rules,
         Set<Wrapper<DexMethod>> methodsMarked,
         ProguardConfigurationRule context,
-        DexDefinition precondition,
+        DexProgramClass precondition,
         ProguardIfRule ifRule) {
       if (methodsMarked != null
           && methodsMarked.contains(MethodSignatureEquivalence.get().wrap(method.getReference()))) {
@@ -1062,7 +1103,7 @@
         DexClassAndField field,
         Collection<ProguardMemberRule> rules,
         ProguardConfigurationRule context,
-        DexDefinition precondition,
+        DexProgramClass precondition,
         ProguardIfRule ifRule) {
       for (ProguardMemberRule rule : rules) {
         if (rule.matches(field, appView, this::handleMatchedAnnotation, dexStringCache)) {
@@ -1081,7 +1122,12 @@
       addItemToSets(clazz, rule, null, null, ifRule);
     }
 
-    private void includeDescriptor(DexDefinition item, DexType type, ProguardKeepRuleBase context) {
+    // TODO(b/192636793): This needs to use the precondition.
+    private void includeDescriptor(
+        DexDefinition item,
+        DexType type,
+        ProguardKeepRuleBase context,
+        DexProgramClass precondition) {
       if (type.isVoidType()) {
         return;
       }
@@ -1091,30 +1137,33 @@
       if (type.isPrimitiveType()) {
         return;
       }
-      DexClass definition = appView.definitionFor(type);
-      if (definition == null || definition.isNotProgramClass()) {
+      DexProgramClass clazz = asProgramClassOrNull(appView.definitionFor(type));
+      if (clazz == null) {
         return;
       }
+
       // Keep the type if the item is also kept.
       dependentNoShrinking
           .computeIfAbsent(item.getReference(), x -> new MutableItemsWithRules())
           .addClassWithRule(type, context);
-      // Unconditionally add to no-obfuscation, as that is only checked for surviving items.
+
+      // Disable minification for the type.
       if (appView.options().isMinificationEnabled()) {
-        noObfuscation.add(type);
+        modifyMinimumKeepInfo(minimumKeepInfo, clazz, Joiner::disallowMinification);
       }
     }
 
-    private void includeDescriptorClasses(DexDefinition item, ProguardKeepRuleBase context) {
+    private void includeDescriptorClasses(
+        DexDefinition item, ProguardKeepRuleBase context, DexProgramClass precondition) {
       if (item.isDexEncodedMethod()) {
-        DexMethod method = item.asDexEncodedMethod().getReference();
-        includeDescriptor(item, method.proto.returnType, context);
-        for (DexType value : method.proto.parameters.values) {
-          includeDescriptor(item, value, context);
+        DexEncodedMethod method = item.asDexEncodedMethod();
+        includeDescriptor(item, method.getReturnType(), context, precondition);
+        for (DexType value : method.getParameters()) {
+          includeDescriptor(item, value, context, precondition);
         }
       } else if (item.isDexEncodedField()) {
-        DexField field = item.asDexEncodedField().getReference();
-        includeDescriptor(item, field.type, context);
+        DexEncodedField field = item.asDexEncodedField();
+        includeDescriptor(item, field.getType(), context, precondition);
       } else {
         assert item.isDexClass();
       }
@@ -1124,7 +1173,7 @@
         DexDefinition item,
         ProguardConfigurationRule context,
         ProguardMemberRule rule,
-        DexDefinition precondition,
+        DexProgramClass precondition,
         ProguardIfRule ifRule) {
       if (context instanceof ProguardKeepRule) {
         if (item.isDexEncodedField()) {
@@ -1173,8 +1222,14 @@
 
         // The reason for keeping should link to the conditional rule as a whole, if present.
         ProguardKeepRuleBase keepRule = ifRule != null ? ifRule : (ProguardKeepRuleBase) context;
+
         // The modifiers are specified on the actual keep rule (ie, the consequent/context).
         ProguardKeepRuleModifiers modifiers = ((ProguardKeepRule) context).getModifiers();
+        if (modifiers.isBottom()) {
+          // This rule is a no-op.
+          return;
+        }
+
         // In compatibility mode, for a match on instance members a referenced class becomes live.
         if (options.forceProguardCompatibility
             && !modifiers.allowsShrinking
@@ -1187,6 +1242,10 @@
             context.markAsUsed();
           }
         }
+
+        // TODO(b/192636793): Remove the noShrinking and dependentNoShrinking collections. A
+        //  prerequisite for this is that the ProguardKeepRule instances are added to the KeepInfo,
+        //  since this is needed for the -whyareyoukeeping graph.
         if (!modifiers.allowsShrinking) {
           if (precondition != null) {
             dependentNoShrinking
@@ -1196,31 +1255,63 @@
             noShrinking.addReferenceWithRule(item.getReference(), keepRule);
           }
           context.markAsUsed();
-        } else if (!modifiers.allowsOptimization) {
-          if (precondition != null) {
-            dependentSoftPinned
-                .computeIfAbsent(precondition.getReference(), x -> new MutableItemsWithRules())
-                .addReferenceWithRule(item.getReference(), keepRule);
-          } else {
-            softPinned.addReferenceWithRule(item.getReference(), keepRule);
-          }
         }
-        if (!modifiers.allowsOptimization) {
-          // The -dontoptimize flag has only effect through the keep all rule, but we still
-          // need to mark the rule as used.
-          context.markAsUsed();
+
+        EnqueuerEvent preconditionEvent;
+        if (precondition != null) {
+          preconditionEvent =
+              item.getAccessFlags().isStatic()
+                  ? new LiveClassEnqueuerEvent(precondition)
+                  : new InstantiatedClassEnqueuerEvent(precondition);
+        } else {
+          preconditionEvent = null;
         }
 
         if (appView.options().isAnnotationRemovalEnabled() && !modifiers.allowsAnnotationRemoval) {
-          noAnnotationRemoval.add(item.getReference());
+          if (precondition != null) {
+            modifyDependentMinimumKeepInfo(
+                dependentMinimumKeepInfo,
+                preconditionEvent,
+                item,
+                Joiner::disallowAnnotationRemoval);
+          } else {
+            modifyMinimumKeepInfo(minimumKeepInfo, item, Joiner::disallowAnnotationRemoval);
+          }
           context.markAsUsed();
         }
+
         if (appView.options().isMinificationEnabled() && !modifiers.allowsObfuscation) {
-          noObfuscation.add(item.getReference());
+          if (precondition != null) {
+            modifyDependentMinimumKeepInfo(
+                dependentMinimumKeepInfo, preconditionEvent, item, Joiner::disallowMinification);
+          } else {
+            modifyMinimumKeepInfo(minimumKeepInfo, item, Joiner::disallowMinification);
+          }
           context.markAsUsed();
         }
+
+        if (appView.options().isOptimizationEnabled() && !modifiers.allowsOptimization) {
+          if (precondition != null) {
+            modifyDependentMinimumKeepInfo(
+                dependentMinimumKeepInfo, preconditionEvent, item, Joiner::disallowOptimization);
+          } else {
+            modifyMinimumKeepInfo(minimumKeepInfo, item, Joiner::disallowOptimization);
+          }
+          context.markAsUsed();
+        }
+
+        if (appView.options().isShrinking() && !modifiers.allowsShrinking) {
+          if (precondition != null) {
+            modifyDependentMinimumKeepInfo(
+                dependentMinimumKeepInfo, preconditionEvent, item, Joiner::disallowShrinking);
+          } else {
+            modifyMinimumKeepInfo(minimumKeepInfo, item, Joiner::disallowShrinking);
+          }
+          context.markAsUsed();
+        }
+
         if (modifiers.includeDescriptorClasses) {
-          includeDescriptorClasses(item, keepRule);
+          includeDescriptorClasses(item, keepRule, precondition);
           context.markAsUsed();
         }
       } else if (context instanceof ProguardAssumeMayHaveSideEffectsRule) {
@@ -1436,11 +1527,9 @@
     final Set<DexMethod> neverInlineDueToSingleCaller;
     final Set<DexType> neverClassInline;
     final MutableItemsWithRules noShrinking;
-    final MutableItemsWithRules softPinned;
-    final Set<DexReference> noAnnotationRemoval;
-    final Set<DexReference> noObfuscation;
+    final Map<DexReference, KeepInfo.Joiner<?, ?, ?>> minimumKeepInfo;
+    final Map<EnqueuerEvent, Map<DexReference, KeepInfo.Joiner<?, ?, ?>>> dependentMinimumKeepInfo;
     final Map<DexReference, MutableItemsWithRules> dependentNoShrinking;
-    final Map<DexReference, MutableItemsWithRules> dependentSoftPinned;
     final Map<DexType, Set<ProguardKeepRuleBase>> dependentKeepClassCompatRule;
     final List<DelayedRootSetActionItem> delayedRootSetActionItems;
 
@@ -1449,22 +1538,18 @@
         Set<DexMethod> neverInlineDueToSingleCaller,
         Set<DexType> neverClassInline,
         MutableItemsWithRules noShrinking,
-        MutableItemsWithRules softPinned,
-        Set<DexReference> noAnnotationRemoval,
-        Set<DexReference> noObfuscation,
+        Map<DexReference, KeepInfo.Joiner<?, ?, ?>> minimumKeepInfo,
+        Map<EnqueuerEvent, Map<DexReference, KeepInfo.Joiner<?, ?, ?>>> dependentMinimumKeepInfo,
         Map<DexReference, MutableItemsWithRules> dependentNoShrinking,
-        Map<DexReference, MutableItemsWithRules> dependentSoftPinned,
         Map<DexType, Set<ProguardKeepRuleBase>> dependentKeepClassCompatRule,
         List<DelayedRootSetActionItem> delayedRootSetActionItems) {
       this.neverInline = neverInline;
       this.neverInlineDueToSingleCaller = neverInlineDueToSingleCaller;
       this.neverClassInline = neverClassInline;
       this.noShrinking = noShrinking;
-      this.softPinned = softPinned;
-      this.noAnnotationRemoval = noAnnotationRemoval;
-      this.noObfuscation = noObfuscation;
+      this.minimumKeepInfo = minimumKeepInfo;
+      this.dependentMinimumKeepInfo = dependentMinimumKeepInfo;
       this.dependentNoShrinking = dependentNoShrinking;
-      this.dependentSoftPinned = dependentSoftPinned;
       this.dependentKeepClassCompatRule = dependentKeepClassCompatRule;
       this.delayedRootSetActionItems = delayedRootSetActionItems;
     }
@@ -1573,6 +1658,54 @@
     Set<ProguardKeepRuleBase> getDependentKeepClassCompatRule(DexType type) {
       return dependentKeepClassCompatRule.get(type);
     }
+
+    public void forEachMinimumKeepInfo(
+        AppView<? extends AppInfoWithClassHierarchy> appView,
+        TriConsumer<EnqueuerEvent, DexProgramClass, KeepClassInfo.Joiner> classConsumer,
+        TriConsumer<EnqueuerEvent, ProgramField, KeepFieldInfo.Joiner> fieldConsumer,
+        TriConsumer<EnqueuerEvent, ProgramMethod, KeepMethodInfo.Joiner> methodConsumer) {
+      internalForEachMinimumKeepInfo(
+          appView, minimumKeepInfo, null, classConsumer, fieldConsumer, methodConsumer);
+      dependentMinimumKeepInfo.forEach(
+          (precondition, minimumKeepInfoForDependents) ->
+              internalForEachMinimumKeepInfo(
+                  appView,
+                  minimumKeepInfoForDependents,
+                  precondition,
+                  classConsumer,
+                  fieldConsumer,
+                  methodConsumer));
+    }
+
+    private static void internalForEachMinimumKeepInfo(
+        AppView<? extends AppInfoWithClassHierarchy> appView,
+        Map<DexReference, KeepInfo.Joiner<?, ?, ?>> minimumKeepInfo,
+        EnqueuerEvent precondition,
+        TriConsumer<EnqueuerEvent, DexProgramClass, KeepClassInfo.Joiner> classConsumer,
+        TriConsumer<EnqueuerEvent, ProgramField, KeepFieldInfo.Joiner> fieldConsumer,
+        TriConsumer<EnqueuerEvent, ProgramMethod, KeepMethodInfo.Joiner> methodConsumer) {
+      minimumKeepInfo.forEach(
+          (reference, joiner) -> {
+            DexProgramClass contextClass =
+                asProgramClassOrNull(appView.definitionFor(reference.getContextType()));
+            if (contextClass != null) {
+              reference.accept(
+                  clazz -> classConsumer.accept(precondition, contextClass, joiner.asClassJoiner()),
+                  fieldReference -> {
+                    ProgramField field = contextClass.lookupProgramField(fieldReference);
+                    if (field != null) {
+                      fieldConsumer.accept(precondition, field, joiner.asFieldJoiner());
+                    }
+                  },
+                  methodReference -> {
+                    ProgramMethod method = contextClass.lookupProgramMethod(methodReference);
+                    if (method != null) {
+                      methodConsumer.accept(precondition, method, joiner.asMethodJoiner());
+                    }
+                  });
+            }
+          });
+    }
   }
 
   abstract static class ItemsWithRules {
@@ -1626,8 +1759,7 @@
   static class MutableItemsWithRules extends ItemsWithRules {
 
     private static final ItemsWithRules EMPTY =
-        new MutableItemsWithRules(
-            Collections.emptyMap(), Collections.emptyMap(), Collections.emptyMap());
+        new MutableItemsWithRules(emptyMap(), emptyMap(), emptyMap());
 
     final Map<DexType, Set<ProguardKeepRuleBase>> classesWithRules;
     final Map<DexField, Set<ProguardKeepRuleBase>> fieldsWithRules;
@@ -1864,9 +1996,8 @@
 
     private RootSet(
         MutableItemsWithRules noShrinking,
-        MutableItemsWithRules softPinned,
-        Set<DexReference> noAnnotationRemoval,
-        Set<DexReference> noObfuscation,
+        Map<DexReference, KeepInfo.Joiner<?, ?, ?>> minimumKeepInfo,
+        Map<EnqueuerEvent, Map<DexReference, KeepInfo.Joiner<?, ?, ?>>> dependentMinimumKeepInfo,
         ImmutableList<DexReference> reasonAsked,
         ImmutableList<DexReference> checkDiscarded,
         Set<DexMethod> alwaysInline,
@@ -1889,7 +2020,6 @@
         Map<DexMember<?, ?>, ProguardMemberRule> noSideEffects,
         Map<DexMember<?, ?>, ProguardMemberRule> assumedValues,
         Map<DexReference, MutableItemsWithRules> dependentNoShrinking,
-        Map<DexReference, MutableItemsWithRules> dependentSoftPinned,
         Map<DexType, Set<ProguardKeepRuleBase>> dependentKeepClassCompatRule,
         Set<DexReference> identifierNameStrings,
         Set<ProguardIfRule> ifRules,
@@ -1899,11 +2029,9 @@
           neverInlineDueToSingleCaller,
           neverClassInline,
           noShrinking,
-          softPinned,
-          noAnnotationRemoval,
-          noObfuscation,
+          minimumKeepInfo,
+          dependentMinimumKeepInfo,
           dependentNoShrinking,
-          dependentSoftPinned,
           dependentKeepClassCompatRule,
           delayedRootSetActionItems);
       this.reasonAsked = reasonAsked;
@@ -1948,13 +2076,10 @@
       neverInline.addAll(consequentRootSet.neverInline);
       neverInlineDueToSingleCaller.addAll(consequentRootSet.neverInlineDueToSingleCaller);
       neverClassInline.addAll(consequentRootSet.neverClassInline);
-      noAnnotationRemoval.addAll(consequentRootSet.noAnnotationRemoval);
-      noObfuscation.addAll(consequentRootSet.noObfuscation);
       if (addNoShrinking) {
         noShrinking.addAll(consequentRootSet.noShrinking);
       }
       addDependentItems(consequentRootSet.dependentNoShrinking, dependentNoShrinking);
-      addDependentItems(consequentRootSet.dependentSoftPinned, dependentSoftPinned);
       consequentRootSet.dependentKeepClassCompatRule.forEach(
           (type, rules) ->
               dependentKeepClassCompatRule
@@ -2015,7 +2140,7 @@
     }
 
     void shouldNotBeMinified(DexReference reference) {
-      noObfuscation.add(reference);
+      modifyMinimumKeepInfo(minimumKeepInfo, reference, Joiner::disallowMinification);
     }
 
     public boolean verifyKeptFieldsAreAccessedAndLive(AppInfoWithLiveness appInfo) {
@@ -2156,8 +2281,6 @@
       StringBuilder builder = new StringBuilder();
       builder.append("RootSet");
       builder.append("\nnoShrinking: " + noShrinking.size());
-      builder.append("\nnoAnnotationRemoval: " + noAnnotationRemoval.size());
-      builder.append("\nnoObfuscation: " + noObfuscation.size());
       builder.append("\nreasonAsked: " + reasonAsked.size());
       builder.append("\ncheckDiscarded: " + checkDiscarded.size());
       builder.append("\nnoSideEffects: " + noSideEffects.size());
@@ -2212,11 +2335,9 @@
         Set<DexMethod> neverInlineDueToSingleCaller,
         Set<DexType> neverClassInline,
         MutableItemsWithRules noShrinking,
-        MutableItemsWithRules softPinned,
-        Set<DexReference> noAnnotationRemoval,
-        Set<DexReference> noObfuscation,
+        Map<DexReference, KeepInfo.Joiner<?, ?, ?>> minimumKeepInfo,
+        Map<EnqueuerEvent, Map<DexReference, KeepInfo.Joiner<?, ?, ?>>> dependentMinimumKeepInfo,
         Map<DexReference, MutableItemsWithRules> dependentNoShrinking,
-        Map<DexReference, MutableItemsWithRules> dependentSoftPinned,
         Map<DexType, Set<ProguardKeepRuleBase>> dependentKeepClassCompatRule,
         List<DelayedRootSetActionItem> delayedRootSetActionItems) {
       super(
@@ -2224,11 +2345,9 @@
           neverInlineDueToSingleCaller,
           neverClassInline,
           noShrinking,
-          softPinned,
-          noAnnotationRemoval,
-          noObfuscation,
+          minimumKeepInfo,
+          dependentMinimumKeepInfo,
           dependentNoShrinking,
-          dependentSoftPinned,
           dependentKeepClassCompatRule,
           delayedRootSetActionItems);
     }
@@ -2280,9 +2399,8 @@
         List<DelayedRootSetActionItem> delayedRootSetActionItems) {
       super(
           noShrinking,
-          new MutableItemsWithRules(),
-          Collections.emptySet(),
-          Collections.emptySet(),
+          emptyMap(),
+          emptyMap(),
           reasonAsked,
           checkDiscarded,
           Collections.emptySet(),
@@ -2301,12 +2419,11 @@
           Collections.emptySet(),
           Collections.emptySet(),
           Collections.emptySet(),
-          Collections.emptyMap(),
-          Collections.emptyMap(),
-          Collections.emptyMap(),
+          emptyMap(),
+          emptyMap(),
+          emptyMap(),
           dependentNoShrinking,
-          Collections.emptyMap(),
-          Collections.emptyMap(),
+          emptyMap(),
           Collections.emptySet(),
           ifRules,
           delayedRootSetActionItems);
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 af2b4ad..c478c54 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -602,6 +602,11 @@
   }
 
   @Override
+  public boolean isOptimizationEnabled() {
+    return isOptimizing();
+  }
+
+  @Override
   public boolean isRepackagingEnabled() {
     return proguardConfiguration.getPackageObfuscationMode().isSome()
         && (isMinifying() || testing.repackageWithNoMinification);
diff --git a/src/main/java/com/android/tools/r8/utils/MapUtils.java b/src/main/java/com/android/tools/r8/utils/MapUtils.java
index fc39146..ba04d86 100644
--- a/src/main/java/com/android/tools/r8/utils/MapUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/MapUtils.java
@@ -32,25 +32,6 @@
     return ignore -> supplier.get();
   }
 
-  public static <K, V> Map<K, V> map(
-      Map<K, V> map,
-      IntFunction<Map<K, V>> factory,
-      Function<K, K> keyMapping,
-      Function<V, V> valueMapping,
-      BiFunction<V, V, V> valueMerger) {
-    Map<K, V> result = factory.apply(map.size());
-    map.forEach(
-        (key, value) -> {
-          K newKey = keyMapping.apply(key);
-          V newValue = valueMapping.apply(value);
-          V existingValue = result.put(newKey, newValue);
-          if (existingValue != null) {
-            result.put(newKey, valueMerger.apply(existingValue, newValue));
-          }
-        });
-    return result;
-  }
-
   public static <K, V> IdentityHashMap<K, V> newIdentityHashMap(BiForEachable<K, V> forEachable) {
     IdentityHashMap<K, V> map = new IdentityHashMap<>();
     forEachable.forEach(map::put);
@@ -65,4 +46,26 @@
     return StringUtils.join(
         ",", map.entrySet(), entry -> entry.getKey() + ":" + entry.getValue(), BraceType.TUBORG);
   }
+
+  public static <K, V> Map<K, V> transform(
+      Map<K, V> map,
+      IntFunction<Map<K, V>> factory,
+      Function<K, K> keyMapping,
+      Function<V, V> valueMapping,
+      BiFunction<V, V, V> valueMerger) {
+    Map<K, V> result = factory.apply(map.size());
+    map.forEach(
+        (key, value) -> {
+          K newKey = keyMapping.apply(key);
+          if (newKey == null) {
+            return;
+          }
+          V newValue = valueMapping.apply(value);
+          V existingValue = result.put(newKey, newValue);
+          if (existingValue != null) {
+            result.put(newKey, valueMerger.apply(existingValue, newValue));
+          }
+        });
+    return result;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/utils/ProgramFieldEquivalence.java b/src/main/java/com/android/tools/r8/utils/ProgramFieldEquivalence.java
new file mode 100644
index 0000000..193df46
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/ProgramFieldEquivalence.java
@@ -0,0 +1,29 @@
+// 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.utils;
+
+import com.android.tools.r8.graph.ProgramField;
+import com.google.common.base.Equivalence;
+
+public class ProgramFieldEquivalence extends Equivalence<ProgramField> {
+
+  private static final ProgramFieldEquivalence INSTANCE = new ProgramFieldEquivalence();
+
+  private ProgramFieldEquivalence() {}
+
+  public static ProgramFieldEquivalence get() {
+    return INSTANCE;
+  }
+
+  @Override
+  protected boolean doEquivalent(ProgramField field, ProgramField other) {
+    return field.getDefinition() == other.getDefinition();
+  }
+
+  @Override
+  protected int doHash(ProgramField field) {
+    return field.getReference().hashCode();
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/ProgramFieldMap.java b/src/main/java/com/android/tools/r8/utils/collections/ProgramFieldMap.java
new file mode 100644
index 0000000..24f7e05
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/ProgramFieldMap.java
@@ -0,0 +1,28 @@
+// 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.utils.collections;
+
+import com.android.tools.r8.graph.ProgramField;
+import com.android.tools.r8.utils.ProgramFieldEquivalence;
+import com.google.common.base.Equivalence.Wrapper;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.function.Supplier;
+
+public class ProgramFieldMap<V> extends ProgramMemberMap<ProgramField, V> {
+
+  private ProgramFieldMap(Supplier<Map<Wrapper<ProgramField>, V>> backingFactory) {
+    super(backingFactory);
+  }
+
+  public static <V> ProgramFieldMap<V> create() {
+    return new ProgramFieldMap<>(HashMap::new);
+  }
+
+  @Override
+  Wrapper<ProgramField> wrap(ProgramField method) {
+    return ProgramFieldEquivalence.get().wrap(method);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/ProgramMemberMap.java b/src/main/java/com/android/tools/r8/utils/collections/ProgramMemberMap.java
new file mode 100644
index 0000000..43daf74
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/ProgramMemberMap.java
@@ -0,0 +1,57 @@
+// 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.utils.collections;
+
+import com.android.tools.r8.graph.ProgramMember;
+import com.google.common.base.Equivalence.Wrapper;
+import java.util.Map;
+import java.util.function.BiConsumer;
+import java.util.function.BiPredicate;
+import java.util.function.Function;
+import java.util.function.Supplier;
+
+public abstract class ProgramMemberMap<K extends ProgramMember<?, ?>, V> {
+
+  private final Map<Wrapper<K>, V> backing;
+
+  ProgramMemberMap(Supplier<Map<Wrapper<K>, V>> backingFactory) {
+    backing = backingFactory.get();
+  }
+
+  public void clear() {
+    backing.clear();
+  }
+
+  public V computeIfAbsent(K member, Function<K, V> fn) {
+    return backing.computeIfAbsent(wrap(member), key -> fn.apply(key.get()));
+  }
+
+  public void forEach(BiConsumer<K, V> consumer) {
+    backing.forEach((wrapper, value) -> consumer.accept(wrapper.get(), value));
+  }
+
+  public V get(K member) {
+    return backing.get(wrap(member));
+  }
+
+  public boolean isEmpty() {
+    return backing.isEmpty();
+  }
+
+  public V put(K member, V value) {
+    Wrapper<K> wrapper = wrap(member);
+    return backing.put(wrapper, value);
+  }
+
+  public V remove(K member) {
+    return backing.remove(wrap(member));
+  }
+
+  public void removeIf(BiPredicate<K, V> predicate) {
+    backing.entrySet().removeIf(entry -> predicate.test(entry.getKey().get(), entry.getValue()));
+  }
+
+  abstract Wrapper<K> wrap(K member);
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/ProgramMethodMap.java b/src/main/java/com/android/tools/r8/utils/collections/ProgramMethodMap.java
index b2f61fd..a3e1b6b 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/ProgramMethodMap.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/ProgramMethodMap.java
@@ -8,20 +8,14 @@
 import com.android.tools.r8.utils.ProgramMethodEquivalence;
 import com.google.common.base.Equivalence.Wrapper;
 import java.util.HashMap;
-import java.util.LinkedHashMap;
 import java.util.Map;
 import java.util.concurrent.ConcurrentHashMap;
-import java.util.function.BiConsumer;
-import java.util.function.BiPredicate;
-import java.util.function.Function;
 import java.util.function.Supplier;
 
-public class ProgramMethodMap<V> {
-
-  private final Map<Wrapper<ProgramMethod>, V> backing;
+public class ProgramMethodMap<V> extends ProgramMemberMap<ProgramMethod, V> {
 
   private ProgramMethodMap(Supplier<Map<Wrapper<ProgramMethod>, V>> backingFactory) {
-    backing = backingFactory.get();
+    super(backingFactory);
   }
 
   public static <V> ProgramMethodMap<V> create() {
@@ -32,36 +26,8 @@
     return new ProgramMethodMap<>(ConcurrentHashMap::new);
   }
 
-  public static <V> ProgramMethodMap<V> createLinked() {
-    return new ProgramMethodMap<>(LinkedHashMap::new);
-  }
-
-  public void clear() {
-    backing.clear();
-  }
-
-  public V computeIfAbsent(ProgramMethod method, Function<ProgramMethod, V> fn) {
-    return backing.computeIfAbsent(wrap(method), key -> fn.apply(key.get()));
-  }
-
-  public void forEach(BiConsumer<ProgramMethod, V> consumer) {
-    backing.forEach((wrapper, value) -> consumer.accept(wrapper.get(), value));
-  }
-
-  public boolean isEmpty() {
-    return backing.isEmpty();
-  }
-
-  public V put(ProgramMethod method, V value) {
-    Wrapper<ProgramMethod> wrapper = ProgramMethodEquivalence.get().wrap(method);
-    return backing.put(wrapper, value);
-  }
-
-  public void removeIf(BiPredicate<ProgramMethod, V> predicate) {
-    backing.entrySet().removeIf(entry -> predicate.test(entry.getKey().get(), entry.getValue()));
-  }
-
-  private static Wrapper<ProgramMethod> wrap(ProgramMethod method) {
+  @Override
+  Wrapper<ProgramMethod> wrap(ProgramMethod method) {
     return ProgramMethodEquivalence.get().wrap(method);
   }
 }