Only minify names based on interfaces that are derived by program classes.
The reduces hello world compilation time with R8 by about 15% and pathological
cases where the library path contains large collections by more than 80%.
A preliminary benchmark script is included.
Change-Id: I7571f981117b3711f54eda6c54a59854a5a0a3f2
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
index 4a85f38..35df2ef 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
@@ -584,16 +584,6 @@
return ImmutableList.of();
}
- public Iterable<DexType> allInterfaces(DexItemFactory dexItemFactory) {
- assert getTypeInfo(dexItemFactory.objectType).hierarchyLevel == ROOT_LEVEL;
- return Iterables.filter(
- getTypeInfo(dexItemFactory.objectType).directSubtypes, t -> getTypeInfo(t).isInterface());
- }
-
- public void forAllInterfaces(DexItemFactory factory, Consumer<DexType> f) {
- allInterfaces(factory).forEach(f);
- }
-
public boolean isMissingOrHasMissingSuperType(DexType type) {
DexClass clazz = definitionFor(type);
return clazz == null || clazz.hasMissingSuperType(this);
diff --git a/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java b/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
index b3ac259..1f22804 100644
--- a/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
@@ -14,6 +14,7 @@
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Sets;
import java.io.PrintStream;
+import java.util.Collection;
import java.util.Map;
import java.util.Set;
import java.util.function.Function;
@@ -35,7 +36,7 @@
}
}
- FieldRenaming computeRenaming(Timing timing) {
+ FieldRenaming computeRenaming(Collection<DexClass> interfaces, Timing timing) {
// Reserve names in all classes first. We do this in subtyping order so we do not
// shadow a reserved field in subclasses. While there is no concept of virtual field
// dispatch in Java, field resolution still traverses the super type chain and external
@@ -45,15 +46,14 @@
timing.end();
// Next, reserve field names in interfaces. These should only be static.
timing.begin("reserve-interfaces");
- appView
- .appInfo()
- .forAllInterfaces(
- appView.dexItemFactory(), iface -> reserveNamesInSubtypes(iface, globalState));
+ for (DexClass iface : interfaces) {
+ reserveNamesInSubtypes(iface.type, globalState);
+ }
timing.end();
// Rename the definitions.
timing.begin("rename-definitions");
renameFieldsInClasses();
- renameFieldsInInterfaces();
+ renameFieldsInInterfaces(interfaces);
timing.end();
// Rename the references that are not rebound to definitions for some reasons.
timing.begin("rename-references");
@@ -120,17 +120,13 @@
}
}
- private void renameFieldsInInterfaces() {
- for (DexType interfaceType : appView.appInfo().allInterfaces(appView.dexItemFactory())) {
- renameFieldsInInterface(interfaceType);
+ private void renameFieldsInInterfaces(Collection<DexClass> interfaces) {
+ for (DexClass iface : interfaces) {
+ renameFieldsInInterface(iface);
}
}
- private void renameFieldsInInterface(DexType type) {
- DexClass clazz = appView.definitionFor(type);
- if (clazz == null) {
- return;
- }
+ private void renameFieldsInInterface(DexClass clazz) {
assert clazz.isInterface();
NamingState<DexType, ?> state = minifierState.getState(clazz.type);
assert state != null;
diff --git a/src/main/java/com/android/tools/r8/naming/InterfaceMethodNameMinifier.java b/src/main/java/com/android/tools/r8/naming/InterfaceMethodNameMinifier.java
index 661711f..4ec7337 100644
--- a/src/main/java/com/android/tools/r8/naming/InterfaceMethodNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/InterfaceMethodNameMinifier.java
@@ -22,6 +22,7 @@
import com.google.common.collect.Sets;
import java.io.PrintStream;
import java.util.ArrayList;
+import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
@@ -30,6 +31,7 @@
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
+import java.util.Objects;
import java.util.Set;
import java.util.stream.Collectors;
@@ -76,30 +78,30 @@
return callSiteRenamings;
}
- private void reserveNamesInInterfaces() {
- for (DexType type : appView.appInfo().allInterfaces(appView.dexItemFactory())) {
- assert appView.appInfo().isInterface(type);
- frontierState.allocateNamingStateAndReserve(type, type, null);
+ private void reserveNamesInInterfaces(Collection<DexClass> interfaces) {
+ for (DexClass iface : interfaces) {
+ assert iface.isInterface();
+ frontierState.allocateNamingStateAndReserve(iface.type, iface.type, null);
}
}
- void assignNamesToInterfaceMethods(Timing timing) {
+ void assignNamesToInterfaceMethods(Timing timing, Collection<DexClass> interfaces) {
// Reserve all the names that are required for interfaces.
- reserveNamesInInterfaces();
+ reserveNamesInInterfaces(interfaces);
// First compute a map from method signatures to a set of naming states for interfaces and
// frontier states of classes that implement them. We add the frontier states so that we can
// reserve the names for later method naming.
timing.begin("Compute map");
- for (DexType type : appView.appInfo().allInterfaces(appView.dexItemFactory())) {
- assert appView.appInfo().isInterface(type);
- DexClass clazz = appView.definitionFor(type);
- if (clazz != null) {
- assert clazz.isInterface();
- Set<NamingState<DexProto, ?>> collectedStates = getReachableStates(type);
- for (DexEncodedMethod method : shuffleMethods(clazz.methods(), appView.options())) {
- addStatesToGlobalMapForMethod(method.method, collectedStates, type);
- }
+ Set<DexType> allInterfaceTypes = new HashSet<>(interfaces.size());
+ for (DexClass iface : interfaces) {
+ allInterfaceTypes.add(iface.type);
+ }
+ for (DexClass iface : interfaces) {
+ Set<NamingState<DexProto, ?>> collectedStates =
+ getReachableStates(iface.type, allInterfaceTypes);
+ for (DexEncodedMethod method : shuffleMethods(iface.methods(), appView.options())) {
+ addStatesToGlobalMapForMethod(method.method, collectedStates, iface.type);
}
}
@@ -131,8 +133,8 @@
callSites.put(callSite, implementedMethods.iterator().next().method);
for (DexEncodedMethod method : implementedMethods) {
DexType iface = method.method.holder;
- assert appView.appInfo().isInterface(iface);
- Set<NamingState<DexProto, ?>> collectedStates = getReachableStates(iface);
+ Set<NamingState<DexProto, ?>> collectedStates =
+ getReachableStates(iface, allInterfaceTypes);
addStatesToGlobalMapForMethod(method.method, collectedStates, iface);
callSiteMethods.add(equivalence.wrap(method.method));
}
@@ -160,6 +162,7 @@
// Go over every method and assign a name.
timing.begin("Allocate names");
+ timing.begin("sort");
// Sort the methods by the number of dependent states, so that we use short names for methods
// that are referenced in many places.
List<Wrapper<DexMethod>> interfaceMethods =
@@ -167,7 +170,9 @@
.filter(wrapper -> unificationParent.getOrDefault(wrapper, wrapper).equals(wrapper))
.sorted(appView.options().testing.minifier.createInterfaceMethodOrdering(this))
.collect(Collectors.toList());
+ timing.end();
+ timing.begin("propogate");
// Propagate reserved names to all states.
List<Wrapper<DexMethod>> reservedInterfaceMethods =
interfaceMethods.stream()
@@ -176,18 +181,24 @@
for (Wrapper<DexMethod> key : reservedInterfaceMethods) {
propagateReservedNames(key, unification);
}
+ timing.end();
+ timing.begin("assert");
// Verify that there is no more to propagate.
assert reservedInterfaceMethods.stream()
.noneMatch(key -> propagateReservedNames(key, unification));
+ timing.end();
+ timing.begin("assing interface");
// Assign names to unreserved interface methods.
for (Wrapper<DexMethod> key : interfaceMethods) {
if (!reservedInterfaceMethods.contains(key)) {
assignNameToInterfaceMethod(key, unification);
}
}
+ timing.end();
+ timing.begin("callsites");
for (Entry<DexCallSite, DexMethod> entry : callSites.entrySet()) {
DexMethod method = entry.getValue();
DexString renamed = minifierState.getRenaming(method);
@@ -200,6 +211,7 @@
}
}
timing.end();
+ timing.end(); // end compute map timing
}
private boolean propagateReservedNames(
@@ -280,6 +292,7 @@
private void addStatesToGlobalMapForMethod(
DexMethod method, Set<NamingState<DexProto, ?>> collectedStates, DexType originInterface) {
+ assert collectedStates.stream().noneMatch(Objects::isNull);
Wrapper<DexMethod> key = equivalence.wrap(method);
globalStateMap.computeIfAbsent(key, k -> new HashSet<>()).addAll(collectedStates);
sourceMethodsMap.computeIfAbsent(key, k -> new HashSet<>()).add(method);
@@ -319,16 +332,14 @@
return false;
}
- private Set<NamingState<DexProto, ?>> getReachableStates(DexType type) {
- Set<DexType> reachableInterfaces = Sets.newIdentityHashSet();
- reachableInterfaces.add(type);
- collectSuperInterfaces(type, reachableInterfaces);
- collectSubInterfaces(type, reachableInterfaces);
-
+ private Set<NamingState<DexProto, ?>> getReachableStates(DexType type, Set<DexType> allInterfaces) {
+ Set<DexType> reachableInterfaces = getReachableInterfaces(type, allInterfaces);
Set<NamingState<DexProto, ?>> reachableStates = new HashSet<>();
for (DexType reachableInterface : reachableInterfaces) {
// Add the interface itself.
- reachableStates.add(minifierState.getState(reachableInterface));
+ NamingState<DexProto, ?> ifaceState = minifierState.getState(reachableInterface);
+ assert ifaceState != null;
+ reachableStates.add(ifaceState);
// And the frontiers that correspond to the classes that implement the interface.
for (DexType frontier : appView.appInfo().allImplementsSubtypes(reachableInterface)) {
@@ -340,24 +351,36 @@
return reachableStates;
}
- private void collectSuperInterfaces(DexType iface, Set<DexType> interfaces) {
+ private Set<DexType> getReachableInterfaces(DexType type, Set<DexType> allInterfaces) {
+ if (!allInterfaces.contains(type)) {
+ return Collections.emptySet();
+ }
+ Set<DexType> reachableInterfaces = Sets.newIdentityHashSet();
+ reachableInterfaces.add(type);
+ collectSuperInterfaces(type, reachableInterfaces, allInterfaces);
+ collectSubInterfaces(type, reachableInterfaces, allInterfaces);
+ return reachableInterfaces;
+ }
+
+ private void collectSuperInterfaces(
+ DexType iface, Set<DexType> reachable, Set<DexType> allInterfaces) {
DexClass clazz = appView.definitionFor(iface);
- // In cases where we lack the interface's definition, we can at least look at subtypes and
- // tie those up to get proper naming.
if (clazz != null) {
for (DexType type : clazz.interfaces.values) {
- if (interfaces.add(type)) {
- collectSuperInterfaces(type, interfaces);
+ if (allInterfaces.contains(type) && reachable.add(type)) {
+ collectSuperInterfaces(type, reachable, allInterfaces);
}
}
}
}
- private void collectSubInterfaces(DexType iface, Set<DexType> interfaces) {
+ private void collectSubInterfaces(
+ DexType iface, Set<DexType> reachableInterfaces, Set<DexType> allInterfaces) {
+ // In cases where we lack the interface's definition, we can at least look at subtypes and
+ // tie those up to get proper naming.
for (DexType subtype : appView.appInfo().allExtendsSubtypes(iface)) {
- assert appView.appInfo().isInterface(subtype);
- if (interfaces.add(subtype)) {
- collectSubInterfaces(subtype, interfaces);
+ if (allInterfaces.contains(subtype) && reachableInterfaces.add(subtype)) {
+ collectSubInterfaces(subtype, reachableInterfaces, allInterfaces);
}
}
}
diff --git a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
index 15d550c..bb100cc 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
@@ -20,6 +20,7 @@
import com.google.common.base.Equivalence.Wrapper;
import com.google.common.collect.ImmutableMap;
import java.io.PrintStream;
+import java.util.Collection;
import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Map;
@@ -128,7 +129,8 @@
}
}
- MethodRenaming computeRenaming(Set<DexCallSite> desugaredCallSites, Timing timing) {
+ MethodRenaming computeRenaming(
+ Collection<DexClass> interfaces, Set<DexCallSite> desugaredCallSites, Timing timing) {
// Phase 1: Reserve all the names that need to be kept and allocate linked state in the
// library part.
timing.begin("Phase 1");
@@ -141,9 +143,8 @@
InterfaceMethodNameMinifier interfaceMethodNameMinifier =
new InterfaceMethodNameMinifier(
appView, desugaredCallSites, equivalence, frontierState, minifierState);
- interfaceMethodNameMinifier.assignNamesToInterfaceMethods(timing);
+ interfaceMethodNameMinifier.assignNamesToInterfaceMethods(timing, interfaces);
timing.end();
- // TODO(zerny): The traversals below should only traverse the reachable graph!
// Phase 3: Assign names top-down by traversing the subtype hierarchy.
timing.begin("Phase 3");
assignNamesToClassesMethods(appView.dexItemFactory().objectType, false);
diff --git a/src/main/java/com/android/tools/r8/naming/Minifier.java b/src/main/java/com/android/tools/r8/naming/Minifier.java
index 6db6f61..411219b 100644
--- a/src/main/java/com/android/tools/r8/naming/Minifier.java
+++ b/src/main/java/com/android/tools/r8/naming/Minifier.java
@@ -5,6 +5,7 @@
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexCallSite;
+import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexReference;
import com.android.tools.r8.graph.DexString;
@@ -23,6 +24,7 @@
import it.unimi.dsi.fastutil.objects.Object2IntLinkedOpenHashMap;
import it.unimi.dsi.fastutil.objects.Object2IntMap;
import java.util.Set;
+import java.util.TreeSet;
public class Minifier {
@@ -36,6 +38,10 @@
public NamingLens run(Timing timing) {
assert appView.options().isMinifying();
+ timing.begin("ComputeInterfaces");
+ Set<DexClass> interfaces = new TreeSet<>((a, b) -> a.type.slowCompareTo(b.type));
+ interfaces.addAll(appView.appInfo().computeReachableInterfaces(desugaredCallSites));
+ timing.end();
timing.begin("MinifyClasses");
ClassNameMinifier classNameMinifier =
new ClassNameMinifier(
@@ -54,7 +60,8 @@
MemberNamingStrategy minifyMembers = new MinifierMemberNamingStrategy(appView.dexItemFactory());
timing.begin("MinifyMethods");
MethodRenaming methodRenaming =
- new MethodNameMinifier(appView, minifyMembers).computeRenaming(desugaredCallSites, timing);
+ new MethodNameMinifier(appView, minifyMembers)
+ .computeRenaming(interfaces, desugaredCallSites, timing);
timing.end();
assert new MinifiedRenaming(appView, classRenaming, methodRenaming, FieldRenaming.empty())
@@ -62,7 +69,7 @@
timing.begin("MinifyFields");
FieldRenaming fieldRenaming =
- new FieldNameMinifier(appView, minifyMembers).computeRenaming(timing);
+ new FieldNameMinifier(appView, minifyMembers).computeRenaming(interfaces, timing);
timing.end();
NamingLens lens = new MinifiedRenaming(appView, classRenaming, methodRenaming, fieldRenaming);
diff --git a/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java b/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
index caed777..1566997 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
@@ -34,6 +34,7 @@
import java.util.List;
import java.util.Map;
import java.util.Set;
+import java.util.TreeSet;
public class ProguardMapMinifier {
@@ -133,19 +134,23 @@
classNameMinifier.computeRenaming(timing, syntheticCompanionClasses);
timing.end();
+ Set<DexClass> interfaces = new TreeSet<>((a, b) -> a.type.slowCompareTo(b.type));
+ interfaces.addAll(appView.appInfo().computeReachableInterfaces(desugaredCallSites));
+
ApplyMappingMemberNamingStrategy nameStrategy =
new ApplyMappingMemberNamingStrategy(
memberNames, appView.dexItemFactory(), appView.options().reporter);
timing.begin("MinifyMethods");
MethodRenaming methodRenaming =
- new MethodNameMinifier(appView, nameStrategy).computeRenaming(desugaredCallSites, timing);
+ new MethodNameMinifier(appView, nameStrategy)
+ .computeRenaming(interfaces, desugaredCallSites, timing);
// Amend the method renamings with the default interface methods.
methodRenaming.renaming.putAll(defaultInterfaceMethodImplementationNames);
timing.end();
timing.begin("MinifyFields");
FieldRenaming fieldRenaming =
- new FieldNameMinifier(appView, nameStrategy).computeRenaming(timing);
+ new FieldNameMinifier(appView, nameStrategy).computeRenaming(interfaces, timing);
timing.end();
appView.options().reporter.failIfPendingErrors();
diff --git a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
index b08fad9..7ff727e 100644
--- a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
+++ b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
@@ -14,6 +14,7 @@
import com.android.tools.r8.optimize.PublicizerLense.PublicizedLenseBuilder;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.Timing;
+import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.concurrent.ExecutionException;
@@ -56,7 +57,9 @@
// Phase 2: Visit classes and promote class/member to public if possible.
timing.begin("Phase 2: promoteToPublic");
- appView.appInfo().forAllInterfaces(appView.dexItemFactory(), this::publicizeType);
+ for (DexClass iface : appView.appInfo().computeReachableInterfaces(Collections.emptySet())) {
+ publicizeType(iface.type);
+ }
publicizeType(appView.dexItemFactory().objectType);
timing.end();
diff --git a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
index 660de51..1a2b0e2 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -12,6 +12,7 @@
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.DexReference;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.DexTypeList;
@@ -28,8 +29,10 @@
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import it.unimi.dsi.fastutil.objects.Object2BooleanMap;
import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Collections;
+import java.util.Deque;
import java.util.IdentityHashMap;
import java.util.Map;
import java.util.Objects;
@@ -540,6 +543,44 @@
previous.markObsolete();
}
+ public Collection<DexClass> computeReachableInterfaces(Set<DexCallSite> desugaredCallSites) {
+ Set<DexClass> interfaces = Sets.newIdentityHashSet();
+ Set<DexType> seen = Sets.newIdentityHashSet();
+ Deque<DexType> worklist = new ArrayDeque<>();
+ for (DexProgramClass clazz : classes()) {
+ worklist.add(clazz.type);
+ }
+ // TODO(b/129458850): Remove this once desugared classes are made part of the program classes.
+ for (DexCallSite callSite : desugaredCallSites) {
+ for (DexEncodedMethod method : lookupLambdaImplementedMethods(callSite)) {
+ worklist.add(method.method.holder);
+ }
+ }
+ for (DexCallSite callSite : callSites) {
+ for (DexEncodedMethod method : lookupLambdaImplementedMethods(callSite)) {
+ worklist.add(method.method.holder);
+ }
+ }
+ while (!worklist.isEmpty()) {
+ DexType type = worklist.pop();
+ if (!seen.add(type)) {
+ continue;
+ }
+ DexClass definition = definitionFor(type);
+ if (definition == null) {
+ continue;
+ }
+ if (definition.isInterface()) {
+ interfaces.add(definition);
+ }
+ if (definition.superType != null) {
+ worklist.add(definition.superType);
+ }
+ Collections.addAll(worklist, definition.interfaces.values);
+ }
+ return interfaces;
+ }
+
public AppInfoWithLiveness withoutStaticFieldsWrites(Set<DexField> noLongerWrittenFields) {
assert checkIfObsolete();
if (noLongerWrittenFields.isEmpty()) {
