Visit classes top-down during vertical class merging
Change-Id: I77d582a4dd939fb7c5b818deb21c166bd2455154
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 3239dbe..d587efe 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -42,8 +42,8 @@
import com.android.tools.r8.shaking.ReasonPrinter;
import com.android.tools.r8.shaking.RootSetBuilder;
import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
-import com.android.tools.r8.shaking.SimpleClassMerger;
import com.android.tools.r8.shaking.TreePruner;
+import com.android.tools.r8.shaking.VerticalClassMerger;
import com.android.tools.r8.shaking.protolite.ProtoLiteExtension;
import com.android.tools.r8.utils.AndroidApiLevel;
import com.android.tools.r8.utils.AndroidApp;
@@ -335,8 +335,8 @@
// Class merging requires inlining.
if (options.enableClassMerging && options.enableInlining) {
timing.begin("ClassMerger");
- SimpleClassMerger classMerger = new SimpleClassMerger(application,
- appInfo.withLiveness(), graphLense, timing);
+ VerticalClassMerger classMerger =
+ new VerticalClassMerger(application, appInfo.withLiveness(), graphLense, timing);
graphLense = classMerger.run();
timing.end();
diff --git a/src/main/java/com/android/tools/r8/shaking/SimpleClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
similarity index 86%
rename from src/main/java/com/android/tools/r8/shaking/SimpleClassMerger.java
rename to src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index c9d34ee..2377e3a 100644
--- a/src/main/java/com/android/tools/r8/shaking/SimpleClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -32,8 +32,10 @@
import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
import it.unimi.dsi.fastutil.objects.Reference2IntMap;
import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
+import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Collections;
+import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
@@ -46,13 +48,13 @@
/**
* Merges Supertypes with a single implementation into their single subtype.
- * <p>
- * A common use-case for this is to merge an interface into its single implementation.
- * <p>
- * The class merger only fixes the structure of the graph but leaves the actual instructions
+ *
+ * <p>A common use-case for this is to merge an interface into its single implementation.
+ *
+ * <p>The class merger only fixes the structure of the graph but leaves the actual instructions
* untouched. Fixup of instructions is deferred via a {@link GraphLense} to the Ir building phase.
*/
-public class SimpleClassMerger {
+public class VerticalClassMerger {
private final DexApplication application;
private final AppInfoWithLiveness appInfo;
@@ -63,8 +65,11 @@
private Collection<DexMethod> invokes;
private int numberOfMerges = 0;
- public SimpleClassMerger(DexApplication application, AppInfoWithLiveness appInfo,
- GraphLense graphLense, Timing timing) {
+ public VerticalClassMerger(
+ DexApplication application,
+ AppInfoWithLiveness appInfo,
+ GraphLense graphLense,
+ Timing timing) {
this.application = application;
this.appInfo = appInfo;
this.graphLense = graphLense;
@@ -135,46 +140,99 @@
return result;
}
+ private void addAncestorsToWorklist(
+ DexProgramClass clazz, Deque<DexProgramClass> worklist, Set<DexProgramClass> seenBefore) {
+ if (seenBefore.contains(clazz)) {
+ return;
+ }
+
+ worklist.addFirst(clazz);
+
+ // Add super classes to worklist.
+ if (clazz.superType != null) {
+ DexClass definition = appInfo.definitionFor(clazz.superType);
+ if (definition != null && definition.isProgramClass()) {
+ addAncestorsToWorklist(definition.asProgramClass(), worklist, seenBefore);
+ }
+ }
+
+ // Add super interfaces to worklist.
+ for (DexType interfaceType : clazz.interfaces.values) {
+ DexClass definition = appInfo.definitionFor(interfaceType);
+ if (definition != null && definition.isProgramClass()) {
+ addAncestorsToWorklist(definition.asProgramClass(), worklist, seenBefore);
+ }
+ }
+ }
+
private GraphLense mergeClasses(GraphLense graphLense) {
- for (DexProgramClass clazz : application.classes()) {
- if (isMergeCandidate(clazz)) {
- DexClass targetClass = appInfo.definitionFor(clazz.type.getSingleSubtype());
- if (appInfo.isPinned(targetClass.type)) {
- // We have to keep the target class intact, so we cannot merge it.
+ Iterable<DexProgramClass> classes = application.classesWithDeterministicOrder();
+ Deque<DexProgramClass> worklist = new ArrayDeque<>();
+ Set<DexProgramClass> seenBefore = new HashSet<>();
+
+ Iterator<DexProgramClass> classIterator = classes.iterator();
+
+ // Visit the program classes in a top-down order according to the class hierarchy.
+ while (classIterator.hasNext() || !worklist.isEmpty()) {
+ if (worklist.isEmpty()) {
+ // Add the ancestors of this class (including the class itself) to the worklist in such a
+ // way that all super types of the class come before the class itself.
+ addAncestorsToWorklist(classIterator.next(), worklist, seenBefore);
+ if (worklist.isEmpty()) {
continue;
}
- if (mergedClasses.containsKey(targetClass.type)) {
- // TODO(herhut): Traverse top-down.
- continue;
- }
- if (clazz.hasClassInitializer() && targetClass.hasClassInitializer()) {
- // TODO(herhut): Handle class initializers.
- if (Log.ENABLED) {
- Log.info(getClass(), "Cannot merge %s into %s due to static initializers.",
- clazz.toSourceString(), targetClass.toSourceString());
- }
- continue;
- }
- // Guard against the case where we have two methods that may get the same signature
- // if we replace types. This is rare, so we approximate and err on the safe side here.
- if (new CollisionDetector(clazz.type, targetClass.type, getInvokes(), mergedClasses)
- .mayCollide()) {
- if (Log.ENABLED) {
- Log.info(getClass(), "Cannot merge %s into %s due to conflict.", clazz.toSourceString(),
- targetClass.toSourceString());
- }
- continue;
- }
- boolean merged = new ClassMerger(clazz, targetClass).merge();
+ }
+
+ DexProgramClass clazz = worklist.removeFirst();
+ if (!seenBefore.add(clazz) || !isMergeCandidate(clazz)) {
+ continue;
+ }
+
+ DexClass targetClass = appInfo.definitionFor(clazz.type.getSingleSubtype());
+ assert !mergedClasses.containsKey(targetClass.type);
+ if (appInfo.isPinned(targetClass.type)) {
+ // We have to keep the target class intact, so we cannot merge it.
+ continue;
+ }
+ if (clazz.hasClassInitializer() && targetClass.hasClassInitializer()) {
+ // TODO(herhut): Handle class initializers.
if (Log.ENABLED) {
- if (merged) {
- numberOfMerges++;
- Log.info(getClass(), "Merged class %s into %s.", clazz.toSourceString(),
- targetClass.toSourceString());
- } else {
- Log.info(getClass(), "Aborted merge for class %s into %s.",
- clazz.toSourceString(), targetClass.toSourceString());
- }
+ Log.info(
+ getClass(),
+ "Cannot merge %s into %s due to static initializers.",
+ clazz.toSourceString(),
+ targetClass.toSourceString());
+ }
+ continue;
+ }
+ // Guard against the case where we have two methods that may get the same signature
+ // if we replace types. This is rare, so we approximate and err on the safe side here.
+ if (new CollisionDetector(clazz.type, targetClass.type, getInvokes(), mergedClasses)
+ .mayCollide()) {
+ if (Log.ENABLED) {
+ Log.info(
+ getClass(),
+ "Cannot merge %s into %s due to conflict.",
+ clazz.toSourceString(),
+ targetClass.toSourceString());
+ }
+ continue;
+ }
+ boolean merged = new ClassMerger(clazz, targetClass).merge();
+ if (Log.ENABLED) {
+ if (merged) {
+ numberOfMerges++;
+ Log.info(
+ getClass(),
+ "Merged class %s into %s.",
+ clazz.toSourceString(),
+ targetClass.toSourceString());
+ } else {
+ Log.info(
+ getClass(),
+ "Aborted merge for class %s into %s.",
+ clazz.toSourceString(),
+ targetClass.toSourceString());
}
}
}
