Add fix-point calculation to the enqueuer for instantiated classes
The set of instantiated classes are build during enqueuing. Checks
dependent on the set of instantiated methods need to be handled in a
fix-point fashion.
Items rejected due to classes not being instantated, are now tracked. After
each tracing iteration these items are checked again if new instantiated
classes have been discovered in that iteration.
Bug: 68696348
Change-Id: I41410dae85a031aec1adc3f6b8a5883de9017042
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 67add9c..4c30d36 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -160,6 +160,12 @@
*/
private final Map<DexType, Set<DexAnnotation>> deferredAnnotations = new IdentityHashMap<>();
+ /**
+ * Methods that have been seen as not reachable due to related classes not being instantiated.
+ * As more instantiated types are collected this set needs to be re-visited.
+ */
+ private List<DexEncodedMethod> pendingAdditionalInstantiatedTypes = new ArrayList<>();
+
public Enqueuer(AppInfoWithSubtyping appInfo, InternalOptions options) {
this.appInfo = appInfo;
this.options = options;
@@ -679,33 +685,39 @@
SetWithReason<DexEncodedMethod> reachable = reachableVirtualMethods
.computeIfAbsent(encodedMethod.method.holder, (ignore) -> new SetWithReason<>());
if (reachable.add(encodedMethod, reason)) {
- // If the holder type is instantiated, the method is live. Otherwise check whether we find
- // a subtype that does not shadow this methods but is instantiated.
- // Note that library classes are always considered instantiated, as we do not know where
- // they are instantiated.
- if (isInstantiatedOrHasInstantiatedSubtype(encodedMethod.method.holder)) {
- if (instantiatedTypes.contains(encodedMethod.method.holder)) {
- markVirtualMethodAsLive(encodedMethod,
- KeepReason.reachableFromLiveType(encodedMethod.method.holder));
- } else {
- Deque<DexType> worklist = new ArrayDeque<>();
- fillWorkList(worklist, encodedMethod.method.holder);
- while (!worklist.isEmpty()) {
- DexType current = worklist.pollFirst();
- DexClass currentHolder = appInfo.definitionFor(current);
- if (currentHolder == null
- || currentHolder.findVirtualTarget(encodedMethod.method) != null) {
- continue;
- }
- if (instantiatedTypes.contains(current)) {
- markVirtualMethodAsLive(encodedMethod, KeepReason.reachableFromLiveType(current));
- break;
- }
- fillWorkList(worklist, current);
- }
+ handleIsInstantiatedOrHasInstantiatedSubtype(encodedMethod);
+ }
+ }
+ }
+
+ private void handleIsInstantiatedOrHasInstantiatedSubtype(DexEncodedMethod encodedMethod) {
+ // If the holder type is instantiated, the method is live. Otherwise check whether we find
+ // a subtype that does not shadow this methods but is instantiated.
+ // Note that library classes are always considered instantiated, as we do not know where
+ // they are instantiated.
+ if (isInstantiatedOrHasInstantiatedSubtype(encodedMethod.method.holder)) {
+ if (instantiatedTypes.contains(encodedMethod.method.holder)) {
+ markVirtualMethodAsLive(encodedMethod,
+ KeepReason.reachableFromLiveType(encodedMethod.method.holder));
+ } else {
+ Deque<DexType> worklist = new ArrayDeque<>();
+ fillWorkList(worklist, encodedMethod.method.holder);
+ while (!worklist.isEmpty()) {
+ DexType current = worklist.pollFirst();
+ DexClass currentHolder = appInfo.definitionFor(current);
+ if (currentHolder == null
+ || currentHolder.findVirtualTarget(encodedMethod.method) != null) {
+ continue;
}
+ if (instantiatedTypes.contains(current)) {
+ markVirtualMethodAsLive(encodedMethod, KeepReason.reachableFromLiveType(current));
+ break;
+ }
+ fillWorkList(worklist, current);
}
}
+ } else {
+ pendingAdditionalInstantiatedTypes.add(encodedMethod);
}
}
@@ -778,38 +790,22 @@
private AppInfoWithLiveness trace(Timing timing) {
timing.begin("Grow the tree.");
try {
- while (!workList.isEmpty()) {
- Action action = workList.poll();
- switch (action.kind) {
- case MARK_INSTANTIATED:
- processNewlyInstantiatedClass((DexClass) action.target, action.reason);
- break;
- case MARK_REACHABLE_FIELD:
- markFieldAsReachable((DexField) action.target, action.reason);
- break;
- case MARK_REACHABLE_VIRTUAL:
- markVirtualMethodAsReachable((DexMethod) action.target, false, action.reason);
- break;
- case MARK_REACHABLE_INTERFACE:
- markVirtualMethodAsReachable((DexMethod) action.target, true, action.reason);
- break;
- case MARK_REACHABLE_SUPER:
- markSuperMethodAsReachable((DexMethod) action.target,
- (DexEncodedMethod) action.context);
- break;
- case MARK_METHOD_KEPT:
- markMethodAsKept((DexEncodedMethod) action.target, action.reason);
- break;
- case MARK_FIELD_KEPT:
- markFieldAsKept((DexEncodedField) action.target, action.reason);
- break;
- case MARK_METHOD_LIVE:
- processNewlyLiveMethod(((DexEncodedMethod) action.target), action.reason);
- break;
- default:
- throw new IllegalArgumentException(action.kind.toString());
+ int instantiatedTypesCount = 0;
+ while (true) {
+ doTrace();
+ // If methods where not considered due to relevant types not being instantiated reconsider
+ // if more instantiated types where collected.
+ if (pendingAdditionalInstantiatedTypes.size() > 0
+ && instantiatedTypes.items.size() > instantiatedTypesCount) {
+ instantiatedTypesCount = instantiatedTypes.items.size();
+ List<DexEncodedMethod> reconsider = pendingAdditionalInstantiatedTypes;
+ pendingAdditionalInstantiatedTypes = new ArrayList<>();
+ reconsider.forEach(this::handleIsInstantiatedOrHasInstantiatedSubtype);
+ } else {
+ break;
}
}
+
if (Log.ENABLED) {
Set<DexEncodedMethod> allLive = Sets.newIdentityHashSet();
for (Entry<DexType, SetWithReason<DexEncodedMethod>> entry : reachableVirtualMethods
@@ -837,6 +833,41 @@
return new AppInfoWithLiveness(appInfo, this);
}
+ private void doTrace() {
+ while (!workList.isEmpty()) {
+ Action action = workList.poll();
+ switch (action.kind) {
+ case MARK_INSTANTIATED:
+ processNewlyInstantiatedClass((DexClass) action.target, action.reason);
+ break;
+ case MARK_REACHABLE_FIELD:
+ markFieldAsReachable((DexField) action.target, action.reason);
+ break;
+ case MARK_REACHABLE_VIRTUAL:
+ markVirtualMethodAsReachable((DexMethod) action.target, false, action.reason);
+ break;
+ case MARK_REACHABLE_INTERFACE:
+ markVirtualMethodAsReachable((DexMethod) action.target, true, action.reason);
+ break;
+ case MARK_REACHABLE_SUPER:
+ markSuperMethodAsReachable((DexMethod) action.target,
+ (DexEncodedMethod) action.context);
+ break;
+ case MARK_METHOD_KEPT:
+ markMethodAsKept((DexEncodedMethod) action.target, action.reason);
+ break;
+ case MARK_FIELD_KEPT:
+ markFieldAsKept((DexEncodedField) action.target, action.reason);
+ break;
+ case MARK_METHOD_LIVE:
+ processNewlyLiveMethod(((DexEncodedMethod) action.target), action.reason);
+ break;
+ default:
+ throw new IllegalArgumentException(action.kind.toString());
+ }
+ }
+ }
+
private void markMethodAsKept(DexEncodedMethod target, KeepReason reason) {
DexClass holder = appInfo.definitionFor(target.method.holder);
// If this method no longer has a corresponding class then we have shaken it away before.
