Deterministic addition of nest members to processing waves.
Bug: b/231418706
Change-Id: I80039f955f624629bfab10bdc7881d0374a2bdc4
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java
index fe2c785..c9bbefe 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java
@@ -5,6 +5,7 @@
package com.android.tools.r8.ir.conversion;
import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexType;
@@ -13,12 +14,19 @@
import com.android.tools.r8.ir.desugar.CfInstructionDesugaringEventConsumer;
import com.android.tools.r8.ir.desugar.CfInstructionDesugaringEventConsumer.D8CfInstructionDesugaringEventConsumer;
import com.android.tools.r8.ir.desugar.itf.InterfaceProcessor;
+import com.android.tools.r8.utils.MapUtils;
import com.android.tools.r8.utils.ThreadUtils;
+import com.android.tools.r8.utils.collections.ImmutableDeque;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Sets;
+import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
+import java.util.Comparator;
+import java.util.Deque;
+import java.util.IdentityHashMap;
import java.util.List;
+import java.util.Map;
import java.util.Set;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
@@ -60,6 +68,48 @@
return resultBuilder.build();
}
+ private static Deque<List<DexProgramClass>> getDeterministicNestWaves(
+ Collection<DexProgramClass> classes) {
+ Map<DexType, List<DexProgramClass>> nestGroups = new IdentityHashMap<>();
+ for (DexProgramClass clazz : classes) {
+ if (clazz.isInANest()) {
+ nestGroups.computeIfAbsent(clazz.getNestHost(), k -> new ArrayList<>()).add(clazz);
+ }
+ }
+ if (nestGroups.isEmpty()) {
+ return ImmutableDeque.of();
+ }
+ int maxGroupSize = 0;
+ for (List<DexProgramClass> members : nestGroups.values()) {
+ maxGroupSize = Math.max(maxGroupSize, members.size());
+ members.sort(Comparator.comparing(DexClass::getType));
+ }
+ Deque<List<DexProgramClass>> processingList = new ArrayDeque<>(maxGroupSize);
+ for (int i = 0; i < maxGroupSize; i++) {
+ List<DexProgramClass> wave = new ArrayList<>(nestGroups.size());
+ final int index = i;
+ MapUtils.removeIf(
+ nestGroups,
+ (host, members) -> {
+ wave.add(members.get(index));
+ return index + 1 == members.size();
+ });
+ processingList.add(wave);
+ }
+ return processingList;
+ }
+
+ private static List<DexProgramClass> filterOutClassesInNests(
+ Collection<DexProgramClass> classes) {
+ List<DexProgramClass> filtered = new ArrayList<>(classes.size());
+ for (DexProgramClass clazz : classes) {
+ if (!clazz.isInANest()) {
+ filtered.add(clazz);
+ }
+ }
+ return filtered;
+ }
+
private void internalConvertClasses(
ClassConverterResult.Builder resultBuilder, ExecutorService executorService)
throws ExecutionException {
@@ -78,19 +128,21 @@
converter.prepareDesugaringForD8(executorService);
- while (!classes.isEmpty()) {
- Set<DexType> seenNestHosts = Sets.newIdentityHashSet();
- List<DexProgramClass> deferred = new ArrayList<>(classes.size() / 2);
- List<DexProgramClass> wave = new ArrayList<>(classes.size());
- for (DexProgramClass clazz : classes) {
- if (clazz.isInANest() && !seenNestHosts.add(clazz.getNestHost())) {
- deferred.add(clazz);
- } else {
- wave.add(clazz);
+ // When adding nest members to the wave we must do so deterministically.
+ Deque<List<DexProgramClass>> nestProcessingWaves = getDeterministicNestWaves(classes);
+ Collection<DexProgramClass> wave;
+ if (nestProcessingWaves.isEmpty()) {
+ wave = classes;
+ } else {
+ List<DexProgramClass> firstWave = filterOutClassesInNests(classes);
+ firstWave.addAll(nestProcessingWaves.removeFirst());
+ wave = firstWave;
+ }
- // TODO(b/179755192): Avoid marking classes as scheduled by building up waves of methods.
- methodProcessor.addScheduled(clazz);
- }
+ while (!wave.isEmpty()) {
+ // TODO(b/179755192): Avoid marking classes as scheduled by building up waves of methods.
+ for (DexProgramClass clazz : wave) {
+ methodProcessor.addScheduled(clazz);
}
D8CfInstructionDesugaringEventConsumer instructionDesugaringEventConsumer =
@@ -128,7 +180,11 @@
assert instructionDesugaringEventConsumer.verifyNothingToFinalize();
}
- classes = deferred;
+ if (!nestProcessingWaves.isEmpty()) {
+ wave = nestProcessingWaves.removeFirst();
+ } else {
+ break;
+ }
}
}
