Merge "Utility to visit classes top-down"
diff --git a/src/main/java/com/android/tools/r8/graph/TopDownClassHierarchyTraversal.java b/src/main/java/com/android/tools/r8/graph/TopDownClassHierarchyTraversal.java
new file mode 100644
index 0000000..e8d6a4f
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/TopDownClassHierarchyTraversal.java
@@ -0,0 +1,70 @@
+// Copyright (c) 2018, 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.graph;
+
+import java.util.ArrayDeque;
+import java.util.Deque;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+import java.util.function.Consumer;
+
+public class TopDownClassHierarchyTraversal {
+
+ public static void visit(
+ AppView<? extends AppInfo> appView,
+ Iterable<DexProgramClass> classes,
+ Consumer<DexProgramClass> visitor) {
+ Deque<DexProgramClass> worklist = new ArrayDeque<>();
+ Set<DexProgramClass> visited = 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, visited, appView);
+ if (worklist.isEmpty()) {
+ continue;
+ }
+ }
+
+ DexProgramClass clazz = worklist.removeFirst();
+ if (visited.add(clazz)) {
+ visitor.accept(clazz);
+ }
+ }
+ }
+
+ private static void addAncestorsToWorklist(
+ DexProgramClass clazz,
+ Deque<DexProgramClass> worklist,
+ Set<DexProgramClass> visited,
+ AppView<? extends AppInfo> appView) {
+ if (visited.contains(clazz)) {
+ return;
+ }
+
+ worklist.addFirst(clazz);
+
+ // Add super classes to worklist.
+ if (clazz.superType != null) {
+ DexClass definition = appView.appInfo().definitionFor(clazz.superType);
+ if (definition != null && definition.isProgramClass()) {
+ addAncestorsToWorklist(definition.asProgramClass(), worklist, visited, appView);
+ }
+ }
+
+ // Add super interfaces to worklist.
+ for (DexType interfaceType : clazz.interfaces.values) {
+ DexClass definition = appView.appInfo().definitionFor(interfaceType);
+ if (definition != null && definition.isProgramClass()) {
+ addAncestorsToWorklist(definition.asProgramClass(), worklist, visited, appView);
+ }
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
index 71a249f..906451e 100644
--- a/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
@@ -5,16 +5,15 @@
package com.android.tools.r8.shaking;
import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexEncodedField;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexString;
-import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.GraphLense;
import com.android.tools.r8.graph.GraphLense.NestedGraphLense;
+import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
import com.android.tools.r8.logging.Log;
import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
import com.android.tools.r8.shaking.VerticalClassMerger.IllegalAccessDetector;
@@ -25,12 +24,8 @@
import com.google.common.collect.HashBiMap;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Streams;
-import java.util.ArrayDeque;
import java.util.Arrays;
-import java.util.Deque;
import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.function.Predicate;
@@ -64,74 +59,34 @@
this.appView = appView;
}
- // TODO(christofferqa): Share top-down traversal with vertical class merger.
public GraphLense run() {
- // Visit classes in top-down order.
- Deque<DexProgramClass> worklist = new ArrayDeque<>();
- Set<DexProgramClass> seenBefore = new HashSet<>();
-
- Iterator<DexProgramClass> classIterator =
- appView.appInfo().app.classesWithDeterministicOrder().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;
- }
- }
-
- DexProgramClass clazz = worklist.removeFirst();
- if (!seenBefore.add(clazz)) {
- continue;
- }
-
+ Iterable<DexProgramClass> classes = appView.appInfo().app.classesWithDeterministicOrder();
+ TopDownClassHierarchyTraversal.visit(appView, classes, clazz -> {
if (satisfiesMergeCriteria(clazz)) {
merge(clazz);
}
- }
-
- BiMap<DexField, DexField> originalFieldSignatures = fieldMapping.inverse();
- BiMap<DexMethod, DexMethod> originalMethodSignatures = methodMapping.inverse();
- return new NestedGraphLense(
- ImmutableMap.of(),
- methodMapping,
- fieldMapping,
- originalFieldSignatures,
- originalMethodSignatures,
- appView.graphLense(),
- appView.dexItemFactory());
+ });
+ return buildGraphLense();
}
- private void addAncestorsToWorklist(
- DexProgramClass clazz, Deque<DexProgramClass> worklist, Set<DexProgramClass> seenBefore) {
- if (seenBefore.contains(clazz)) {
- return;
+ private GraphLense buildGraphLense() {
+ if (!fieldMapping.isEmpty() || !methodMapping.isEmpty()) {
+ BiMap<DexField, DexField> originalFieldSignatures = fieldMapping.inverse();
+ BiMap<DexMethod, DexMethod> originalMethodSignatures = methodMapping.inverse();
+ return new NestedGraphLense(
+ ImmutableMap.of(),
+ methodMapping,
+ fieldMapping,
+ originalFieldSignatures,
+ originalMethodSignatures,
+ appView.graphLense(),
+ appView.dexItemFactory());
}
-
- worklist.addFirst(clazz);
-
- // Add super classes to worklist.
- if (clazz.superType != null) {
- DexClass definition = appView.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 = appView.appInfo().definitionFor(interfaceType);
- if (definition != null && definition.isProgramClass()) {
- addAncestorsToWorklist(definition.asProgramClass(), worklist, seenBefore);
- }
- }
+ return appView.graphLense();
}
- public boolean satisfiesMergeCriteria(DexProgramClass clazz) {
+ private boolean satisfiesMergeCriteria(DexProgramClass clazz) {
if (appView.appInfo().neverMerge.contains(clazz.type)) {
return false;
}
@@ -169,7 +124,7 @@
return true;
}
- public boolean merge(DexProgramClass clazz) {
+ private boolean merge(DexProgramClass clazz) {
assert satisfiesMergeCriteria(clazz);
String pkg = clazz.type.getPackageDescriptor();
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index df4c786..33ffc44 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -34,6 +34,7 @@
import com.android.tools.r8.graph.MethodAccessFlags;
import com.android.tools.r8.graph.ParameterAnnotationsList;
import com.android.tools.r8.graph.PresortedComparable;
+import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
import com.android.tools.r8.graph.UseRegistry;
import com.android.tools.r8.ir.code.Invoke.Type;
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
@@ -57,15 +58,12 @@
import it.unimi.dsi.fastutil.objects.Reference2BooleanOpenHashMap;
import it.unimi.dsi.fastutil.objects.Reference2IntMap;
import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
-import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
-import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
-import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
@@ -198,6 +196,7 @@
private final DexApplication application;
private final AppInfoWithLiveness appInfo;
+ private final AppView<? extends AppInfoWithLiveness> appView;
private final ExecutorService executorService;
private final GraphLense graphLense;
private final MethodPoolCollection methodPoolCollection;
@@ -231,6 +230,7 @@
Timing timing) {
this.application = application;
this.appInfo = appView.appInfo();
+ this.appView = appView;
this.executorService = executorService;
this.graphLense = appView.graphLense();
this.methodPoolCollection = new MethodPoolCollection(application);
@@ -584,7 +584,7 @@
}
}
- public GraphLense run() throws ExecutionException {
+ public GraphLense run() {
timing.begin("merge");
GraphLense mergingGraphLense = mergeClasses(graphLense);
timing.end();
@@ -604,108 +604,11 @@
return result;
}
- private void addCandidateAncestorsToWorklist(
- DexProgramClass clazz, Deque<DexProgramClass> worklist, Set<DexProgramClass> seenBefore) {
- if (seenBefore.contains(clazz)) {
- return;
- }
-
- if (mergeCandidates.contains(clazz)) {
- worklist.addFirst(clazz);
- }
-
- // Add super classes to worklist.
- if (clazz.superType != null) {
- DexClass definition = appInfo.definitionFor(clazz.superType);
- if (definition != null && definition.isProgramClass()) {
- addCandidateAncestorsToWorklist(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()) {
- addCandidateAncestorsToWorklist(definition.asProgramClass(), worklist, seenBefore);
- }
- }
- }
-
- private GraphLense mergeClasses(GraphLense graphLense) throws ExecutionException {
- Deque<DexProgramClass> worklist = new ArrayDeque<>();
- Set<DexProgramClass> seenBefore = new HashSet<>();
-
- int numberOfMerges = 0;
-
- Iterator<DexProgramClass> candidatesIterator = mergeCandidates.iterator();
-
+ private GraphLense mergeClasses(GraphLense graphLense) {
// Visit the program classes in a top-down order according to the class hierarchy.
- while (candidatesIterator.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.
- addCandidateAncestorsToWorklist(candidatesIterator.next(), worklist, seenBefore);
- if (worklist.isEmpty()) {
- continue;
- }
- }
-
- DexProgramClass clazz = worklist.removeFirst();
- assert isMergeCandidate(clazz, pinnedTypes);
- if (!seenBefore.add(clazz)) {
- continue;
- }
-
- DexProgramClass targetClass =
- appInfo.definitionFor(clazz.type.getSingleSubtype()).asProgramClass();
- assert !mergedClasses.containsKey(targetClass.type);
-
- boolean clazzOrTargetClassHasBeenMerged =
- mergedClassesInverse.containsKey(clazz.type)
- || mergedClassesInverse.containsKey(targetClass.type);
- if (clazzOrTargetClassHasBeenMerged) {
- if (!isStillMergeCandidate(clazz)) {
- continue;
- }
- } else {
- assert isStillMergeCandidate(clazz);
- }
-
- // 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).mayCollide()) {
- if (Log.ENABLED) {
- AbortReason.CONFLICT.printLogMessageForClass(clazz);
- }
- continue;
- }
-
- ClassMerger merger = new ClassMerger(clazz, targetClass);
- boolean merged = merger.merge();
- if (merged) {
- // Commit the changes to the graph lense.
- renamedMembersLense.merge(merger.getRenamings());
- synthesizedBridges.addAll(merger.getSynthesizedBridges());
- }
- 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());
- }
- }
- }
+ TopDownClassHierarchyTraversal.visit(appView, mergeCandidates, this::mergeClassIfPossible);
if (Log.ENABLED) {
- Log.debug(getClass(), "Merged %d classes.", numberOfMerges);
+ Log.debug(getClass(), "Merged %d classes.", mergedClasses.size());
}
return renamedMembersLense.build(graphLense, mergedClasses, synthesizedBridges, appInfo);
}
@@ -764,6 +667,66 @@
return false;
}
+ private void mergeClassIfPossible(DexProgramClass clazz) {
+ if (!mergeCandidates.contains(clazz)) {
+ return;
+ }
+
+ assert isMergeCandidate(clazz, pinnedTypes);
+
+ DexProgramClass targetClass =
+ appInfo.definitionFor(clazz.type.getSingleSubtype()).asProgramClass();
+ assert !mergedClasses.containsKey(targetClass.type);
+
+ boolean clazzOrTargetClassHasBeenMerged =
+ mergedClassesInverse.containsKey(clazz.type)
+ || mergedClassesInverse.containsKey(targetClass.type);
+ if (clazzOrTargetClassHasBeenMerged) {
+ if (!isStillMergeCandidate(clazz)) {
+ return;
+ }
+ } else {
+ assert isStillMergeCandidate(clazz);
+ }
+
+ // 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).mayCollide()) {
+ if (Log.ENABLED) {
+ AbortReason.CONFLICT.printLogMessageForClass(clazz);
+ }
+ return;
+ }
+
+ ClassMerger merger = new ClassMerger(clazz, targetClass);
+ boolean merged;
+ try {
+ merged = merger.merge();
+ } catch (ExecutionException e) {
+ throw new RuntimeException(e);
+ }
+ if (merged) {
+ // Commit the changes to the graph lense.
+ renamedMembersLense.merge(merger.getRenamings());
+ synthesizedBridges.addAll(merger.getSynthesizedBridges());
+ }
+ if (Log.ENABLED) {
+ if (merged) {
+ 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());
+ }
+ }
+ }
+
private boolean fieldResolutionMayChange(DexClass source, DexClass target) {
if (source.type == target.superType) {
// If there is a "iget Target.f" or "iput Target.f" instruction in target, and the class
