Initial structure horizontal class merging
* `Merger` performs the overall task of horizontal class merging
* `Merger.run()` initially sorts the classes by field spec and then executes all policies on the groups of classes.
Uses `DexFieldSignature` to sort classes by signature.
* `Policy` is the abstract class for all horizontal class merging policies
* `SingleClassPolicy` and `MultiClassPolicy` abstract classes extending from Policy
* `PolicyExecutor` as abstract class for policy execution
* `SimplePolicyExecutor` as a reference implementation for a policy executor
Bug: 163311975
Change-Id: Idb27b1a9d4c6303f985b57212dff31bbe8fff420
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 39753be..4d1a076 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -39,6 +39,7 @@
import com.android.tools.r8.graph.SubtypingInfo;
import com.android.tools.r8.graph.analysis.ClassInitializerAssertionEnablingAnalysis;
import com.android.tools.r8.graph.analysis.InitializedClassesInInstanceMethodsAnalysis;
+import com.android.tools.r8.horizontalclassmerging.HorizontalClassMerger;
import com.android.tools.r8.inspector.internal.InspectorImpl;
import com.android.tools.r8.ir.conversion.IRConverter;
import com.android.tools.r8.ir.desugar.BackportedMethodRewriter;
@@ -541,6 +542,13 @@
}
timing.end();
}
+ if (options.enableHorizontalClassMerging) {
+ timing.begin("HorizontalClassMerger");
+ HorizontalClassMerger merger =
+ new HorizontalClassMerger(appViewWithLiveness, mainDexClasses);
+ merger.run();
+ timing.end();
+ }
// Only required for class merging, clear instance to save memory.
classMergingEnqueuerExtension = null;
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/FieldMultiset.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/FieldMultiset.java
new file mode 100644
index 0000000..37222de
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/FieldMultiset.java
@@ -0,0 +1,37 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.horizontalclassmerging;
+
+import com.android.tools.r8.graph.DexEncodedField;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
+import com.google.common.collect.HashMultiset;
+import com.google.common.collect.Multiset;
+
+public class FieldMultiset {
+
+ private final Multiset<DexType> fields = HashMultiset.create();
+
+ public FieldMultiset(DexProgramClass clazz) {
+ for (DexEncodedField field : clazz.instanceFields()) {
+ fields.add(field.type());
+ }
+ }
+
+ @Override
+ public int hashCode() {
+ return fields.hashCode();
+ }
+
+ @Override
+ public boolean equals(Object object) {
+ if (object instanceof FieldMultiset) {
+ FieldMultiset other = (FieldMultiset) object;
+ return fields.equals(other.fields);
+ } else {
+ return false;
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
new file mode 100644
index 0000000..56da905
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
@@ -0,0 +1,48 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.horizontalclassmerging;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.MainDexClasses;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Map;
+
+public class HorizontalClassMerger {
+
+ private final AppView<AppInfoWithLiveness> appView;
+ private final MainDexClasses mainDexClasses;
+
+ private final PolicyExecutor policyExecutor;
+
+ public HorizontalClassMerger(
+ AppView<AppInfoWithLiveness> appView, MainDexClasses mainDexClasses) {
+ this.appView = appView;
+ this.mainDexClasses = mainDexClasses;
+
+ Policy[] policies = {
+ // TODO: add policies
+ };
+ this.policyExecutor = new SimplePolicyExecutor(Arrays.asList(policies));
+ }
+
+ public Collection<Collection<DexProgramClass>> run() {
+ Map<FieldMultiset, Collection<DexProgramClass>> classes = new HashMap<>();
+
+ // Group classes by same field signature using the hash map.
+ for (DexProgramClass clazz : appView.appInfo().app().classesWithDeterministicOrder()) {
+ classes.computeIfAbsent(new FieldMultiset(clazz), ignore -> new ArrayList<>()).add(clazz);
+ }
+
+ // Run the policies on all collected classes to produce a final grouping.
+ Collection<Collection<DexProgramClass>> groups = policyExecutor.run(classes.values());
+
+ return groups;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/MultiClassPolicy.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/MultiClassPolicy.java
new file mode 100644
index 0000000..261e8d2
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/MultiClassPolicy.java
@@ -0,0 +1,21 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.horizontalclassmerging;
+
+import com.android.tools.r8.graph.DexProgramClass;
+import java.util.Collection;
+
+public abstract class MultiClassPolicy extends Policy {
+
+ /**
+ * Apply the multi class policy to a group of program classes.
+ *
+ * @param group This is a group of program classes which can currently still be merged.
+ * @return The same collection of program classes split into new groups of candidates which can be
+ * merged. If the policy detects no issues then `group` will be returned unchanged. If classes
+ * cannot be merged with any other classes they are returned as singleton lists.
+ */
+ public abstract Collection<Collection<DexProgramClass>> apply(Collection<DexProgramClass> group);
+}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/Policy.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/Policy.java
new file mode 100644
index 0000000..d8dea98
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/Policy.java
@@ -0,0 +1,11 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.horizontalclassmerging;
+
+/**
+ * The super class of all horizontal class merging policies. Most classes will either implement
+ * {@link SingleClassPolicy} or {@link MultiClassPolicy}.
+ */
+public abstract class Policy {}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyExecutor.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyExecutor.java
new file mode 100644
index 0000000..7ffaa1b
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyExecutor.java
@@ -0,0 +1,24 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.horizontalclassmerging;
+
+import com.android.tools.r8.graph.DexProgramClass;
+import java.util.Collection;
+
+public abstract class PolicyExecutor {
+ protected final Collection<Policy> policies;
+
+ public PolicyExecutor(Collection<Policy> policies) {
+ this.policies = policies;
+ }
+
+ /**
+ * Given an initial collection of class groups which can potentially be merged, run all of the
+ * policies registered to this policy executor on the class groups yielding a new collection of
+ * class groups.
+ */
+ public abstract Collection<Collection<DexProgramClass>> run(
+ Collection<Collection<DexProgramClass>> classes);
+}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/SimplePolicyExecutor.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/SimplePolicyExecutor.java
new file mode 100644
index 0000000..3e6254c
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/SimplePolicyExecutor.java
@@ -0,0 +1,63 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.horizontalclassmerging;
+
+import com.android.tools.r8.graph.DexProgramClass;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.stream.Collectors;
+
+/**
+ * This is a simple policy executor that ensures regular sequential execution of policies. It should
+ * primarily be readable and correct. The SimplePolicyExecutor should be a reference implementation,
+ * against which more efficient policy executors can be compared.
+ */
+public class SimplePolicyExecutor extends PolicyExecutor {
+ public SimplePolicyExecutor(Collection<Policy> policies) {
+ super(policies);
+ }
+
+ // TODO(b/165506334): if performing mutable operation ensure that linked lists are used
+ private Collection<Collection<DexProgramClass>> applySingleClassPolicy(
+ SingleClassPolicy policy, Collection<Collection<DexProgramClass>> groups) {
+ Iterator<Collection<DexProgramClass>> i = groups.iterator();
+ while (i.hasNext()) {
+ Collection<DexProgramClass> group = i.next();
+ Iterator<DexProgramClass> j = group.iterator();
+ while (j.hasNext()) {
+ DexProgramClass clazz = j.next();
+ if (!policy.canMerge(clazz)) {
+ j.remove();
+ }
+ }
+ if (group.isEmpty()) {
+ i.remove();
+ }
+ }
+ return groups;
+ }
+
+ private Collection<Collection<DexProgramClass>> applyMultiClassPolicy(
+ MultiClassPolicy policy, Collection<Collection<DexProgramClass>> groups) {
+ // For each group apply the multi class policy and add all the new groups together.
+ return groups.stream()
+ .flatMap(group -> policy.apply(group).stream())
+ .collect(Collectors.toList());
+ }
+
+ @Override
+ public Collection<Collection<DexProgramClass>> run(
+ Collection<Collection<DexProgramClass>> groups) {
+ for (Policy policy : policies) {
+ if (policy instanceof SingleClassPolicy) {
+ groups = applySingleClassPolicy((SingleClassPolicy) policy, groups);
+ } else if (policy instanceof MultiClassPolicy) {
+ groups = applyMultiClassPolicy((MultiClassPolicy) policy, groups);
+ }
+ }
+
+ return groups;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/SingleClassPolicy.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/SingleClassPolicy.java
new file mode 100644
index 0000000..b0757c5
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/SingleClassPolicy.java
@@ -0,0 +1,16 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.horizontalclassmerging;
+
+import com.android.tools.r8.graph.DexProgramClass;
+
+public abstract class SingleClassPolicy extends Policy {
+ /**
+ * Determine if {@param program} can be merged with any other classes.
+ *
+ * @return {@code false} if the class should not be merged, otherwise {@code true}.
+ */
+ public abstract boolean canMerge(DexProgramClass program);
+}
