Reland "Group synthetics based on their ordering."
Bug: b/237413146
This reverts commit 12ab345c790393ae107b893f25aee28968f1e5f0.
Change-Id: I20855ddc11d580d0d43b05be1d44a3e6ecec7dfd
diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java
index 527cec3..6065527 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java
@@ -35,6 +35,7 @@
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.IterableUtils;
import com.android.tools.r8.utils.ListUtils;
+import com.android.tools.r8.utils.OptionalBool;
import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.Timing;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
@@ -53,6 +54,7 @@
import java.util.Comparator;
import java.util.HashMap;
import java.util.IdentityHashMap;
+import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
@@ -592,14 +594,12 @@
List<EquivalenceGroup<T>> groups =
groupEquivalent(appView, members, intermediate, classToFeatureSplitMap);
for (EquivalenceGroup<T> group : groups) {
- // If the group already has a representative, then this representative is pinned.
- // Otherwise, we select a deterministic representative.
- if (group.hasRepresentative()) {
+ // If the group has a pinned representative don't construct an external type.
+ if (group.isPinned(appView)) {
EquivalenceGroup<T> previous =
equivalences.put(group.getRepresentative().getHolder().getType(), group);
assert previous == null;
} else {
- group.selectDeterministicRepresentative();
groupsPerPrefix
.computeIfAbsent(
group.getRepresentative().getPrefixForExternalSyntheticType(),
@@ -666,52 +666,94 @@
List<T> potentialEquivalence,
boolean intermediate,
ClassToFeatureSplitMap classToFeatureSplitMap) {
- List<EquivalenceGroup<T>> groups = new ArrayList<>();
- // Each other member is in a shared group if it is actually equivalent to the first member.
- for (T synthetic : potentialEquivalence) {
- if (groups.size() > GROUP_COUNT_THRESHOLD) {
- return ListUtils.map(
- potentialEquivalence, m -> new EquivalenceGroup<>(m, isPinned(appView, m)));
+ // Fast path the singleton groups.
+ if (potentialEquivalence.size() == 1) {
+ return ImmutableList.of(EquivalenceGroup.singleton(potentialEquivalence.get(0)));
+ }
+ assert !potentialEquivalence.isEmpty();
+
+ // Sort the potential members and split them up into potential groups of members that are
+ // actually equal.
+ GraphLens graphLens = appView.graphLens();
+ boolean includeContext =
+ intermediate || appView.options().getStartupOptions().isStartupInstrumentationEnabled();
+ List<T> sortedPotentialMembers =
+ ListUtils.sort(
+ potentialEquivalence,
+ (a, b) -> a.compareTo(b, includeContext, graphLens, classToFeatureSplitMap));
+ List<List<T>> potentialGroups = new ArrayList<>();
+ {
+ List<T> currentGroup = new ArrayList<>();
+ T currentRepresentative = sortedPotentialMembers.get(0);
+ currentGroup.add(currentRepresentative);
+ for (int i = 1; i < sortedPotentialMembers.size(); i++) {
+ T member = sortedPotentialMembers.get(i);
+ if (!currentRepresentative.isEquivalentTo(
+ member, includeContext, graphLens, classToFeatureSplitMap)) {
+ potentialGroups.add(currentGroup);
+ currentGroup = new ArrayList<>();
+ currentRepresentative = member;
+ }
+ currentGroup.add(member);
}
- boolean mustBeRepresentative = isPinned(appView, synthetic);
- EquivalenceGroup<T> equivalenceGroup = null;
- for (EquivalenceGroup<T> group : groups) {
- boolean includeContext =
- intermediate || appView.options().getStartupOptions().isStartupInstrumentationEnabled();
- if (synthetic.isEquivalentTo(
- group.hasRepresentative()
- ? group.getRepresentative()
- : group.getFirstNonRepresentativeMember(),
- includeContext,
- appView.graphLens(),
- classToFeatureSplitMap)) {
- if (mustBeRepresentative && group.hasRepresentative()) {
- // Check if the current synthetic is smaller than the group's representative. If so,
- // then replace the representative, to ensure deterministic groups, and create a new
- // singleton group containing the old representative. Otherwise, just add a singleton
- // group containing the new synthetic.
- T representative = group.getRepresentative();
- if (representative
- .toReference()
- .getReference()
- .compareTo(synthetic.toReference().getReference())
- > 0) {
- group.replaceAndRemoveRepresentative(synthetic);
- synthetic = representative;
+ potentialGroups.add(currentGroup);
+ }
+
+ // Compute the actual groups by picking the group representatives. In cases of pinned members
+ // this may need to split out representatives into their own singleton groups.
+ List<EquivalenceGroup<T>> actualGroups = new ArrayList<>();
+ for (List<T> potentialGroup : potentialGroups) {
+ assert !potentialGroup.isEmpty();
+ if (potentialGroup.size() == 1) {
+ actualGroups.add(EquivalenceGroup.singleton(potentialGroup.get(0)));
+ continue;
+ }
+ List<T> forcedRepresentatives = null;
+ if (appView.enableWholeProgramOptimizations()) {
+ Iterator<T> it = potentialGroup.iterator();
+ while (it.hasNext()) {
+ T member = it.next();
+ boolean mustBeRepresentative = isPinned(appView, member);
+ if (mustBeRepresentative) {
+ if (forcedRepresentatives == null) {
+ forcedRepresentatives = new ArrayList<>();
}
- } else {
- equivalenceGroup = group;
+ forcedRepresentatives.add(member);
+ it.remove();
}
- break;
}
}
- if (equivalenceGroup != null) {
- equivalenceGroup.add(synthetic, mustBeRepresentative);
+ if (forcedRepresentatives != null) {
+ assert appView.enableWholeProgramOptimizations();
+ T representative =
+ findSmallestMember(
+ forcedRepresentatives,
+ other -> actualGroups.add(EquivalenceGroup.pinnedSingleton(other)));
+ actualGroups.add(EquivalenceGroup.pinnedGroup(representative, potentialGroup));
} else {
- groups.add(new EquivalenceGroup<>(synthetic, mustBeRepresentative));
+ List<T> members = new ArrayList<>(potentialGroup.size() - 1);
+ T representative = findSmallestMember(potentialGroup, members::add);
+ actualGroups.add(EquivalenceGroup.unpinnedGroup(representative, members));
}
}
- return groups;
+ return actualGroups;
+ }
+
+ private static <T extends SyntheticDefinition<?, T, ?>> T findSmallestMember(
+ List<T> members, Consumer<T> notSmallestCallback) {
+ assert !members.isEmpty();
+ T smallest = members.get(0);
+ for (int i = 1; i < members.size(); i++) {
+ T member = members.get(i);
+ if (member.toReference().getReference().compareTo(smallest.toReference().getReference())
+ < 0) {
+ notSmallestCallback.accept(smallest);
+ smallest = member;
+ } else {
+ notSmallestCallback.accept(member);
+ }
+ }
+ return smallest;
}
/**
@@ -846,28 +888,47 @@
private static class EquivalenceGroup<T extends SyntheticDefinition<?, T, ?>> {
// The members of the equivalence group, *excluding* the representative.
- private List<T> members = new ArrayList<>();
- private T representative;
+ private final List<T> members;
+ private final T representative;
+ private final OptionalBool pinned;
- EquivalenceGroup(T member, boolean isRepresentative) {
- add(member, isRepresentative);
+ static <T extends SyntheticDefinition<?, T, ?>> EquivalenceGroup<T> singleton(T member) {
+ return new EquivalenceGroup<>(member, ImmutableList.of(), OptionalBool.UNKNOWN);
}
- void add(T member, boolean isRepresentative) {
- if (isRepresentative) {
- assert !hasRepresentative();
- representative = member;
- } else {
- members.add(member);
+ static <T extends SyntheticDefinition<?, T, ?>> EquivalenceGroup<T> unpinnedGroup(
+ T representative, List<T> members) {
+ return new EquivalenceGroup<>(
+ representative, Collections.unmodifiableList(members), OptionalBool.FALSE);
+ }
+
+ static <T extends SyntheticDefinition<?, T, ?>> EquivalenceGroup<T> pinnedSingleton(T member) {
+ return new EquivalenceGroup<>(member, ImmutableList.of(), OptionalBool.TRUE);
+ }
+
+ static <T extends SyntheticDefinition<?, T, ?>> EquivalenceGroup<T> pinnedGroup(
+ T representative, List<T> members) {
+ return new EquivalenceGroup<>(
+ representative, Collections.unmodifiableList(members), OptionalBool.TRUE);
+ }
+
+ private EquivalenceGroup(T representative, List<T> members, OptionalBool pinned) {
+ assert representative != null;
+ assert members != null;
+ assert pinned != null;
+ this.members = members;
+ this.representative = representative;
+ this.pinned = pinned;
+ }
+
+ public boolean isPinned(AppView<?> appView) {
+ if (pinned.isTrue()) {
+ return true;
}
- }
-
- int compareToIncludingContext(
- EquivalenceGroup<T> other,
- GraphLens graphLens,
- ClassToFeatureSplitMap classToFeatureSplitMap) {
- return getRepresentative()
- .compareTo(other.getRepresentative(), true, graphLens, classToFeatureSplitMap);
+ if (pinned.isFalse()) {
+ return false;
+ }
+ return SyntheticFinalization.isPinned(appView, representative);
}
public void forEach(Consumer<T> consumer) {
@@ -879,64 +940,23 @@
members.forEach(consumer);
}
- T getFirstNonRepresentativeMember() {
- assert !members.isEmpty();
- return members.get(0);
- }
-
T getRepresentative() {
- assert hasRepresentative();
return representative;
}
- boolean hasRepresentative() {
- return representative != null;
- }
-
boolean isDerivedFromMainDexList(MainDexInfo mainDexInfo) {
return getRepresentative().getContext().isDerivedFromMainDexList(mainDexInfo)
|| Iterables.any(
members, member -> member.getContext().isDerivedFromMainDexList(mainDexInfo));
}
- void replaceAndRemoveRepresentative(T representative) {
- assert hasRepresentative();
- this.representative = representative;
- }
-
- void selectDeterministicRepresentative() {
- // Pick a deterministic member as representative.
- assert !hasRepresentative();
- int representativeIndex = 0;
- for (int i = 1; i < members.size(); i++) {
- T next = members.get(i);
- T representative = members.get(representativeIndex);
- if (next.toReference().getReference().compareTo(representative.toReference().getReference())
- < 0) {
- representativeIndex = i;
- }
- }
- T representative = members.get(representativeIndex);
- members.set(representativeIndex, ListUtils.last(members));
- ListUtils.removeLast(members);
- setRepresentative(representative);
- }
-
- void setRepresentative(T representative) {
- assert !hasRepresentative();
- this.representative = representative;
- }
-
@Override
public String toString() {
- if (hasRepresentative()) {
- return "EquivalenceGroup{ size = "
- + (members.size() + 1)
- + ", repr = "
- + getRepresentative()
- + " }";
- }
- return "EquivalenceGroup{ size = " + members.size() + " }";
+ return "EquivalenceGroup{ size = "
+ + (members.size() + 1)
+ + ", repr = "
+ + getRepresentative()
+ + " }";
}
}
}
diff --git a/src/main/java/com/android/tools/r8/utils/ListUtils.java b/src/main/java/com/android/tools/r8/utils/ListUtils.java
index 9c6e2a7..406d482 100644
--- a/src/main/java/com/android/tools/r8/utils/ListUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ListUtils.java
@@ -268,12 +268,26 @@
void accept(T item, int index);
}
+ public static <T> List<T> sort(List<T> items, Comparator<T> comparator) {
+ List<T> sorted = new ArrayList<>(items);
+ sorted.sort(comparator);
+ return sorted;
+ }
+
public static <T> void destructiveSort(List<T> items, Comparator<T> comparator) {
items.sort(comparator);
}
// Utility to add a slow verification of a comparator as part of sorting. Note that this
// should not generally be used in asserts unless the quadratic behavior can be tolerated.
+ public static <T> List<T> sortAndVerify(List<T> items, Comparator<T> comparator) {
+ List<T> sorted = sort(items, comparator);
+ assert verifyComparatorOnSortedList(sorted, comparator);
+ return sorted;
+ }
+
+ // Utility to add a slow verification of a comparator as part of sorting. Note that this
+ // should not generally be used in asserts unless the quadratic behavior can be tolerated.
public static <T> void destructiveSortAndVerify(List<T> items, Comparator<T> comparator) {
destructiveSort(items, comparator);
assert verifyComparatorOnSortedList(items, comparator);
