Group synthetics based on their ordering.
This replaces the quadratic placement by sorting the groups based on
order. Determinism is avoided as representatives are ordered base on
their unique and deterministic internal reference.
Bug: b/237413146
Change-Id: I2cfb9641daef81157f223ad63660e6a9eb88a614
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..7020d21 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,93 @@
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);
+ 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 +887,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 +939,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);
