Limit the number of possible equivalence groups.
This CL hardcodes a limit on the number of actual groups for a given set
of potential equivalences to ensure that the quadratic behavior is not
hit. The expected groups should generally be small for a given type of
synthetics so this will not likely have an impact on size.
It would be beneficial to follow-up with a sorting-based implementation
and avoid the arbitrary limit.
Bug: b/237413146
Bug: b/236690153
Change-Id: Id4e57e83a5a0b1431e95753d605c52865c4b05b9
diff --git a/src/main/java/com/android/tools/r8/D8.java b/src/main/java/com/android/tools/r8/D8.java
index 9e46ebb..34f4de6 100644
--- a/src/main/java/com/android/tools/r8/D8.java
+++ b/src/main/java/com/android/tools/r8/D8.java
@@ -208,6 +208,7 @@
}
Timing timing = Timing.create("D8", options);
try {
+ timing.begin("Pre conversion");
// Synthetic assertion to check that testing assertions works and can be enabled.
assert forTesting(options, () -> !options.testing.testEnableTestAssertions);
@@ -246,9 +247,9 @@
if (options.testing.enableD8ResourcesPassThrough) {
appView.setAppServices(AppServices.builder(appView).build());
}
-
+ timing.end();
new IRConverter(appView, timing, printer).convert(appView, executor);
-
+ timing.begin("Post conversion");
if (options.printCfg) {
if (options.printCfgFile == null || options.printCfgFile.isEmpty()) {
System.out.print(printer.toString());
@@ -286,9 +287,22 @@
}
Marker.checkCompatibleDesugaredLibrary(markers, options.reporter);
- InspectorImpl.runInspections(options.outputInspections, appView.appInfo().classes());
- appView.setNamingLens(PrefixRewritingNamingLens.createPrefixRewritingNamingLens(appView));
- appView.setNamingLens(RecordRewritingNamingLens.createRecordRewritingNamingLens(appView));
+ timing.time(
+ "Run inspections",
+ () ->
+ InspectorImpl.runInspections(options.outputInspections, appView.appInfo().classes()));
+
+ timing.time(
+ "Create prefix rewriting lens",
+ () ->
+ appView.setNamingLens(
+ PrefixRewritingNamingLens.createPrefixRewritingNamingLens(appView)));
+
+ timing.time(
+ "Create record rewriting lens",
+ () ->
+ appView.setNamingLens(
+ RecordRewritingNamingLens.createRecordRewritingNamingLens(appView)));
if (options.isGeneratingDex()
&& hasDexResources
@@ -313,20 +327,34 @@
// Since tracing is not lens aware, this needs to be done prior to synthetic finalization
// which will construct a graph lens.
if (options.isGeneratingDex() && !options.mainDexKeepRules.isEmpty()) {
+ timing.begin("Generate main-dex list");
appView.dexItemFactory().clearTypeElementsCache();
MainDexInfo mainDexInfo =
new GenerateMainDexList(options)
.traceMainDex(
executor, appView.appInfo().app(), appView.appInfo().getMainDexInfo());
appView.setAppInfo(appView.appInfo().rebuildWithMainDexInfo(mainDexInfo));
+ timing.end();
}
- finalizeApplication(appView, executor);
+ timing.time("Finalize synthetics", () -> finalizeApplication(appView, executor, timing));
- HorizontalClassMerger.createForD8ClassMerging(appView).runIfNecessary(executor, timing);
+ timing.time(
+ "Horizontal merger",
+ () ->
+ HorizontalClassMerger.createForD8ClassMerging(appView)
+ .runIfNecessary(executor, timing));
- new GenericSignatureRewriter(appView).runForD8(appView.appInfo().classes(), executor);
- new KotlinMetadataRewriter(appView).runForD8(executor);
+ timing.time(
+ "Signature rewriter",
+ () ->
+ new GenericSignatureRewriter(appView)
+ .runForD8(appView.appInfo().classes(), executor));
+
+ timing.time(
+ "Kotlin metadata rewriter", () -> new KotlinMetadataRewriter(appView).runForD8(executor));
+
+ timing.end(); // post-converter
if (options.isGeneratingClassFiles()) {
new CfApplicationWriter(appView, marker).write(options.getClassFileConsumer(), inputApp);
@@ -366,9 +394,10 @@
appView.setAssumeInfoCollection(assumeInfoCollectionBuilder.build());
}
- private static void finalizeApplication(AppView<AppInfo> appView, ExecutorService executorService)
+ private static void finalizeApplication(
+ AppView<AppInfo> appView, ExecutorService executorService, Timing timing)
throws ExecutionException {
- SyntheticFinalization.finalize(appView, executorService);
+ SyntheticFinalization.finalize(appView, timing, executorService);
}
private static DexApplication rewriteNonDexInputs(
diff --git a/src/main/java/com/android/tools/r8/L8.java b/src/main/java/com/android/tools/r8/L8.java
index 1e0fc7c..1dddf3f 100644
--- a/src/main/java/com/android/tools/r8/L8.java
+++ b/src/main/java/com/android/tools/r8/L8.java
@@ -137,7 +137,7 @@
new IRConverter(appView, timing).convert(appView, executor);
- SyntheticFinalization.finalize(appView, executor);
+ SyntheticFinalization.finalize(appView, timing, executor);
appView.setNamingLens(PrefixRewritingNamingLens.createPrefixRewritingNamingLens(appView));
new GenericSignatureRewriter(appView).run(appView.appInfo().classes(), executor);
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index c75fbf2..b781d3a 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -718,9 +718,9 @@
appView.setGraphLens(MemberRebindingIdentityLensFactory.create(appView, executorService));
if (appView.appInfo().hasLiveness()) {
- SyntheticFinalization.finalizeWithLiveness(appView.withLiveness(), executorService);
+ SyntheticFinalization.finalizeWithLiveness(appView.withLiveness(), executorService, timing);
} else {
- SyntheticFinalization.finalizeWithClassHierarchy(appView, executorService);
+ SyntheticFinalization.finalizeWithClassHierarchy(appView, executorService, timing);
}
// Read any -applymapping input to allow for repackaging to not relocate the classes.
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 822fa38..cfb078e 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java
@@ -36,6 +36,7 @@
import com.android.tools.r8.utils.IterableUtils;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.SetUtils;
+import com.android.tools.r8.utils.Timing;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneRepresentativeMap;
@@ -63,6 +64,9 @@
public class SyntheticFinalization {
+ // TODO(b/237413146): Implement a non-quadratic grouping algorithm.
+ private static final int GROUP_COUNT_THRESHOLD = 10;
+
public static class Result {
public final CommittedItems commit;
public final NonIdentityGraphLens lens;
@@ -155,12 +159,13 @@
this.committed = committed;
}
- public static void finalize(AppView<AppInfo> appView, ExecutorService executorService)
+ public static void finalize(
+ AppView<AppInfo> appView, Timing timing, ExecutorService executorService)
throws ExecutionException {
assert !appView.appInfo().hasClassHierarchy();
assert !appView.appInfo().hasLiveness();
appView.options().testing.checkDeterminism(appView);
- Result result = appView.getSyntheticItems().computeFinalSynthetics(appView);
+ Result result = appView.getSyntheticItems().computeFinalSynthetics(appView, timing);
appView.setAppInfo(new AppInfo(result.commit, result.mainDexInfo));
if (result.lens != null) {
appView.setAppInfo(
@@ -177,11 +182,11 @@
}
public static void finalizeWithClassHierarchy(
- AppView<AppInfoWithClassHierarchy> appView, ExecutorService executorService)
+ AppView<AppInfoWithClassHierarchy> appView, ExecutorService executorService, Timing timing)
throws ExecutionException {
assert !appView.appInfo().hasLiveness();
appView.options().testing.checkDeterminism(appView);
- Result result = appView.getSyntheticItems().computeFinalSynthetics(appView);
+ Result result = appView.getSyntheticItems().computeFinalSynthetics(appView, timing);
appView.setAppInfo(appView.appInfo().rebuildWithClassHierarchy(result.commit));
appView.setAppInfo(appView.appInfo().rebuildWithMainDexInfo(result.mainDexInfo));
if (result.lens != null) {
@@ -199,10 +204,10 @@
}
public static void finalizeWithLiveness(
- AppView<AppInfoWithLiveness> appView, ExecutorService executorService)
+ AppView<AppInfoWithLiveness> appView, ExecutorService executorService, Timing timing)
throws ExecutionException {
appView.options().testing.checkDeterminism(appView);
- Result result = appView.getSyntheticItems().computeFinalSynthetics(appView);
+ Result result = appView.getSyntheticItems().computeFinalSynthetics(appView, timing);
appView.setAppInfo(appView.appInfo().rebuildWithMainDexInfo(result.mainDexInfo));
if (result.lens != null) {
appView.rewriteWithLensAndApplication(result.lens, result.commit.getApplication().asDirect());
@@ -213,7 +218,7 @@
appView.pruneItems(result.prunedItems, executorService);
}
- Result computeFinalSynthetics(AppView<?> appView) {
+ Result computeFinalSynthetics(AppView<?> appView, Timing timing) {
assert verifyNoNestedSynthetics(appView.dexItemFactory());
assert verifyOneSyntheticPerSyntheticClass();
DexApplication application;
@@ -227,9 +232,18 @@
Map<String, NumberGenerator> generators = new HashMap<>();
application =
buildLensAndProgram(
+ timing,
appView,
- computeEquivalences(appView, committed.getMethods(), generators, lensBuilder),
- computeEquivalences(appView, committed.getClasses(), generators, lensBuilder),
+ timing.time(
+ "Method equivalence",
+ () ->
+ computeEquivalences(
+ appView, committed.getMethods(), generators, lensBuilder, timing)),
+ timing.time(
+ "Class equivalence",
+ () ->
+ computeEquivalences(
+ appView, committed.getClasses(), generators, lensBuilder, timing)),
lensBuilder,
(clazz, reference) ->
finalClassesBuilder.put(clazz.getType(), ImmutableList.of(reference)),
@@ -289,13 +303,15 @@
AppView<?> appView,
ImmutableMap<DexType, List<R>> references,
Map<String, NumberGenerator> generators,
- Builder lensBuilder) {
+ Builder lensBuilder,
+ Timing timing) {
boolean intermediate = appView.options().intermediate;
Map<DexType, D> definitions = lookupDefinitions(appView, references);
ClassToFeatureSplitMap classToFeatureSplitMap =
appView.appInfo().hasClassHierarchy()
? appView.appInfo().withClassHierarchy().getClassToFeatureSplitMap()
: ClassToFeatureSplitMap.createEmptyClassToFeatureSplitMap();
+ timing.begin("Potential equivalences");
Collection<List<D>> potentialEquivalences =
computePotentialEquivalences(
definitions,
@@ -304,13 +320,15 @@
appView.graphLens(),
classToFeatureSplitMap,
synthetics);
+ timing.end();
return computeActualEquivalences(
potentialEquivalences,
generators,
appView,
intermediate,
classToFeatureSplitMap,
- lensBuilder);
+ lensBuilder,
+ timing);
}
private boolean isNotSyntheticType(DexType type) {
@@ -361,6 +379,7 @@
}
private static DexApplication buildLensAndProgram(
+ Timing timing,
AppView<?> appView,
Map<DexType, EquivalenceGroup<SyntheticMethodDefinition>> syntheticMethodGroups,
Map<DexType, EquivalenceGroup<SyntheticProgramClassDefinition>> syntheticClassGroups,
@@ -448,10 +467,12 @@
assert verifyNonRepresentativesRemovedFromApplication(application, syntheticClassGroups);
assert verifyNonRepresentativesRemovedFromApplication(application, syntheticMethodGroups);
+ timing.begin("Tree fixing");
DexApplication.Builder<?> builder = application.builder();
treeFixer.fixupClasses(deduplicatedClasses);
builder.replaceProgramClasses(treeFixer.fixupClasses(application.classes()));
application = builder.build();
+ timing.end();
}
DexString syntheticSourceFileName =
@@ -459,6 +480,7 @@
? appView.dexItemFactory().createString("R8$$SyntheticClass")
: appView.dexItemFactory().createString("D8$$SyntheticClass");
+ timing.begin("Add final synthetics");
// Add the synthesized from after repackaging which changed class definitions.
final DexApplication appForLookup = application;
syntheticClassGroups.forEach(
@@ -491,7 +513,9 @@
representative.getContext(),
syntheticMethodDefinition.getReference()));
});
+ timing.end();
+ timing.begin("Finish lens");
Iterables.<EquivalenceGroup<? extends SyntheticDefinition<?, ?, DexProgramClass>>>concat(
syntheticClassGroups.values(), syntheticMethodGroups.values())
.forEach(
@@ -511,6 +535,7 @@
lensBuilder.setRepresentative(rewrittenMethod, method);
}
}));
+ timing.end();
for (DexType key : syntheticMethodGroups.keySet()) {
assert application.definitionFor(key) != null;
@@ -557,9 +582,11 @@
AppView<?> appView,
boolean intermediate,
ClassToFeatureSplitMap classToFeatureSplitMap,
- Builder lensBuilder) {
+ Builder lensBuilder,
+ Timing timing) {
Map<String, List<EquivalenceGroup<T>>> groupsPerPrefix = new HashMap<>();
Map<DexType, EquivalenceGroup<T>> equivalences = new IdentityHashMap<>();
+ timing.begin("Groups");
potentialEquivalences.forEach(
members -> {
List<EquivalenceGroup<T>> groups =
@@ -581,6 +608,8 @@
}
}
});
+ timing.end();
+ timing.begin("External creation");
groupsPerPrefix.forEach(
(externalSyntheticTypePrefix, groups) -> {
Comparator<EquivalenceGroup<T>> comparator = this::compareForFinalGroupSorting;
@@ -613,6 +642,7 @@
equivalences.put(representativeType, group);
}
});
+ timing.end();
equivalences.forEach(
(representativeType, group) ->
group.forEach(
@@ -639,6 +669,9 @@
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, true));
+ }
boolean mustBeRepresentative = isPinned(appView, synthetic);
EquivalenceGroup<T> equivalenceGroup = null;
for (EquivalenceGroup<T> group : groups) {
diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
index 08d9d27..407e91d 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
@@ -43,6 +43,7 @@
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.StringDiagnostic;
+import com.android.tools.r8.utils.Timing;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Iterables;
@@ -1086,9 +1087,9 @@
// Finalization of synthetic items.
- Result computeFinalSynthetics(AppView<?> appView) {
+ Result computeFinalSynthetics(AppView<?> appView, Timing timing) {
assert !hasPendingSyntheticClasses();
return new SyntheticFinalization(appView.options(), this, committed)
- .computeFinalSynthetics(appView);
+ .computeFinalSynthetics(appView, timing);
}
}
