Merge "Separate interface method minification from class method minification"
diff --git a/src/main/java/com/android/tools/r8/graph/DexType.java b/src/main/java/com/android/tools/r8/graph/DexType.java
index 936f967..2ebccfe 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -15,6 +15,7 @@
import com.android.tools.r8.utils.DescriptorUtils;
import com.android.tools.r8.utils.InternalOptions.OutlineOptions;
import com.google.common.base.Predicates;
+import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Sets;
@@ -269,25 +270,23 @@
* language, where interfaces "extend" their superinterface.
*/
public void forAllImplementsSubtypes(Consumer<DexType> f) {
- if (hierarchyLevel != INTERFACE_LEVEL) {
- return;
+ allImplementsSubtypes().forEach(f);
+ }
+
+ public Iterable<DexType> allImplementsSubtypes() {
+ if (hierarchyLevel == INTERFACE_LEVEL) {
+ return Iterables.filter(directSubtypes, subtype -> !subtype.isInterface());
}
- for (DexType subtype : directSubtypes) {
- // Filter out other interfaces.
- if (subtype.hierarchyLevel != INTERFACE_LEVEL) {
- f.accept(subtype);
- }
- }
+ return ImmutableList.of();
+ }
+
+ public static Iterable<DexType> allInterfaces(DexItemFactory dexItemFactory) {
+ assert dexItemFactory.objectType.hierarchyLevel == ROOT_LEVEL;
+ return Iterables.filter(dexItemFactory.objectType.directSubtypes, DexType::isInterface);
}
public static void forAllInterfaces(DexItemFactory factory, Consumer<DexType> f) {
- DexType object = factory.objectType;
- assert object.hierarchyLevel == ROOT_LEVEL;
- for (DexType subtype : object.directSubtypes) {
- if (subtype.isInterface()) {
- f.accept(subtype);
- }
- }
+ allInterfaces(factory).forEach(f);
}
/**
diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
index e53f959..bc81538 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
@@ -96,7 +96,7 @@
// Initialize top-level naming state.
topLevelState = new Namespace(
getPackageBinaryNameFromJavaType(options.getProguardConfiguration().getPackagePrefix()));
- states.computeIfAbsent("", k -> topLevelState);
+ states.put("", topLevelState);
}
static class ClassRenaming {
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 90dbbdb..be339b6 100644
--- a/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
@@ -27,7 +27,7 @@
Function<DexType, ?> getKeyTransform() {
if (overloadAggressively) {
// Use the type as the key, hence reuse names per type.
- return a -> a;
+ return Function.identity();
} else {
// Always use the same key, hence do not reuse names per type.
return a -> Void.class;
@@ -97,7 +97,7 @@
if (clazz == null) {
return;
}
- NamingState<DexType, ?> state = getState(clazz.type);
+ NamingState<DexType, ?> state = minifierState.getState(clazz.type);
assert state != null;
clazz.forEachField(field -> renameField(field, state));
type.forAllExtendsSubtypes(this::renameFieldsInSubtypes);
@@ -106,9 +106,7 @@
private void renameField(DexEncodedField encodedField, NamingState<DexType, ?> state) {
DexField field = encodedField.field;
if (!state.isReserved(field.name, field.type)) {
- renaming.put(
- field,
- state.assignNewNameFor(field.name, field.type, useUniqueMemberNames));
+ renaming.put(field, state.assignNewNameFor(field.name, field.type, useUniqueMemberNames));
}
}
diff --git a/src/main/java/com/android/tools/r8/naming/InterfaceMethodNameMinifier.java b/src/main/java/com/android/tools/r8/naming/InterfaceMethodNameMinifier.java
new file mode 100644
index 0000000..718ce78
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/naming/InterfaceMethodNameMinifier.java
@@ -0,0 +1,310 @@
+// Copyright (c) 2019, 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.naming;
+
+import static com.android.tools.r8.naming.MethodNameMinifier.shuffleMethods;
+
+import com.android.tools.r8.graph.DexCallSite;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProto;
+import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.naming.MethodNameMinifier.FrontierState;
+import com.android.tools.r8.naming.MethodNameMinifier.MethodNamingState;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
+import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.Timing;
+import com.google.common.base.Equivalence;
+import com.google.common.base.Equivalence.Wrapper;
+import com.google.common.collect.Sets;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.IdentityHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+
+class InterfaceMethodNameMinifier {
+
+ private final AppInfoWithLiveness appInfo;
+ private final Set<DexCallSite> desugaredCallSites;
+ private final Equivalence<DexMethod> equivalence;
+ private final FrontierState frontierState;
+ private final MemberNameMinifier<DexMethod, DexProto>.State minifierState;
+ private final InternalOptions options;
+
+ private final Map<DexCallSite, DexString> callSiteRenamings = new IdentityHashMap<>();
+
+ /** A map from DexMethods to all the states linked to interfaces they appear in. */
+ private final Map<Wrapper<DexMethod>, Set<NamingState<DexProto, ?>>> globalStateMap =
+ new HashMap<>();
+
+ /** A map from DexMethods to the first interface state it was seen in. Used to pick good names. */
+ private final Map<Wrapper<DexMethod>, NamingState<DexProto, ?>> originStates = new HashMap<>();
+
+ /**
+ * A map from DexMethods to all the definitions seen. Needed as the Wrapper equalizes them all.
+ */
+ private final Map<Wrapper<DexMethod>, Set<DexMethod>> sourceMethodsMap = new HashMap<>();
+
+ InterfaceMethodNameMinifier(
+ AppInfoWithLiveness appInfo,
+ Set<DexCallSite> desugaredCallSites,
+ Equivalence<DexMethod> equivalence,
+ FrontierState frontierState,
+ MemberNameMinifier<DexMethod, DexProto>.State minifierState,
+ InternalOptions options) {
+ this.appInfo = appInfo;
+ this.desugaredCallSites = desugaredCallSites;
+ this.equivalence = equivalence;
+ this.frontierState = frontierState;
+ this.minifierState = minifierState;
+ this.options = options;
+ }
+
+ Map<DexCallSite, DexString> getCallSiteRenamings() {
+ return callSiteRenamings;
+ }
+
+ private void reserveNamesInInterfaces() {
+ for (DexType type : DexType.allInterfaces(appInfo.dexItemFactory)) {
+ assert type.isInterface();
+ frontierState.put(type, type);
+ frontierState.allocateNamingStateAndReserve(type, type, null);
+ }
+ }
+
+ void assignNamesToInterfaceMethods(Timing timing) {
+ // Reserve all the names that are required for interfaces.
+ reserveNamesInInterfaces();
+
+ // 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 : DexType.allInterfaces(appInfo.dexItemFactory)) {
+ assert type.isInterface();
+ DexClass clazz = appInfo.definitionFor(type);
+ if (clazz != null) {
+ assert clazz.isInterface();
+ Set<NamingState<DexProto, ?>> collectedStates = getReachableStates(type);
+ for (DexEncodedMethod method : shuffleMethods(clazz.methods(), options)) {
+ addStatesToGlobalMapForMethod(method, collectedStates, type);
+ }
+ }
+ }
+
+ // Collect the live call sites for multi-interface lambda expression renaming. For code with
+ // desugared lambdas this is a conservative estimate, as we don't track if the generated
+ // lambda classes survive into the output. As multi-interface lambda expressions are rare
+ // this is not a big deal.
+ Set<DexCallSite> liveCallSites = Sets.union(desugaredCallSites, appInfo.callSites);
+ // If the input program contains a multi-interface lambda expression that implements
+ // interface methods with different protos, we need to make sure that
+ // the implemented lambda methods are renamed to the same name.
+ // To achieve this, we map each DexCallSite that corresponds to a lambda expression to one of
+ // the DexMethods it implements, and we unify the DexMethods that need to be renamed together.
+ Map<DexCallSite, DexMethod> callSites = new IdentityHashMap<>();
+ // Union-find structure to keep track of methods that must be renamed together.
+ // Note that if the input does not use multi-interface lambdas,
+ // unificationParent will remain empty.
+ Map<Wrapper<DexMethod>, Wrapper<DexMethod>> unificationParent = new HashMap<>();
+ liveCallSites.forEach(
+ callSite -> {
+ Set<Wrapper<DexMethod>> callSiteMethods = new HashSet<>();
+ // Don't report errors, as the set of call sites is a conservative estimate, and can
+ // refer to interfaces which has been removed.
+ Set<DexEncodedMethod> implementedMethods =
+ appInfo.lookupLambdaImplementedMethods(callSite);
+ if (implementedMethods.isEmpty()) {
+ return;
+ }
+ callSites.put(callSite, implementedMethods.iterator().next().method);
+ for (DexEncodedMethod method : implementedMethods) {
+ DexType iface = method.method.holder;
+ assert iface.isInterface();
+ Set<NamingState<DexProto, ?>> collectedStates = getReachableStates(iface);
+ addStatesToGlobalMapForMethod(method, collectedStates, iface);
+ callSiteMethods.add(equivalence.wrap(method.method));
+ }
+ if (callSiteMethods.size() > 1) {
+ // Implemented interfaces have different return types. Unify them.
+ Wrapper<DexMethod> mainKey = callSiteMethods.iterator().next();
+ mainKey = unificationParent.getOrDefault(mainKey, mainKey);
+ for (Wrapper<DexMethod> key : callSiteMethods) {
+ unificationParent.put(key, mainKey);
+ }
+ }
+ });
+ Map<Wrapper<DexMethod>, Set<Wrapper<DexMethod>>> unification = new HashMap<>();
+ for (Wrapper<DexMethod> key : unificationParent.keySet()) {
+ // Find root with path-compression.
+ Wrapper<DexMethod> root = unificationParent.get(key);
+ while (unificationParent.get(root) != root) {
+ Wrapper<DexMethod> k = unificationParent.get(unificationParent.get(root));
+ unificationParent.put(root, k);
+ root = k;
+ }
+ unification.computeIfAbsent(root, k -> new HashSet<>()).add(key);
+ }
+ timing.end();
+ // Go over every method and assign a name.
+ timing.begin("Allocate names");
+ // 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>> methods = new ArrayList<>(globalStateMap.keySet());
+ methods.sort((a, b) -> globalStateMap.get(b).size() - globalStateMap.get(a).size());
+ for (Wrapper<DexMethod> key : methods) {
+ if (!unificationParent.getOrDefault(key, key).equals(key)) {
+ continue;
+ }
+ List<MethodNamingState> collectedStates = new ArrayList<>();
+ Set<DexMethod> sourceMethods = Sets.newIdentityHashSet();
+ for (Wrapper<DexMethod> k : unification.getOrDefault(key, Collections.singleton(key))) {
+ DexMethod unifiedMethod = k.get();
+ assert unifiedMethod != null;
+ sourceMethods.addAll(sourceMethodsMap.get(k));
+ for (NamingState<DexProto, ?> namingState : globalStateMap.get(k)) {
+ collectedStates.add(
+ new MethodNamingState(namingState, unifiedMethod.name, unifiedMethod.proto));
+ }
+ }
+ DexMethod method = key.get();
+ assert method != null;
+ MethodNamingState originState =
+ new MethodNamingState(originStates.get(key), method.name, method.proto);
+ assignNameForInterfaceMethodInAllStates(collectedStates, sourceMethods, originState);
+ }
+ for (Entry<DexCallSite, DexMethod> entry : callSites.entrySet()) {
+ DexMethod method = entry.getValue();
+ DexString renamed = minifierState.getRenaming(method);
+ if (originStates.get(equivalence.wrap(method)).isReserved(method.name, method.proto)) {
+ assert renamed == null;
+ callSiteRenamings.put(entry.getKey(), method.name);
+ } else {
+ assert renamed != null;
+ callSiteRenamings.put(entry.getKey(), renamed);
+ }
+ }
+ timing.end();
+ }
+
+ private void assignNameForInterfaceMethodInAllStates(
+ List<MethodNamingState> collectedStates,
+ Set<DexMethod> sourceMethods,
+ MethodNamingState originState) {
+ if (anyIsReserved(collectedStates)) {
+ // This method's name is reserved in at least one naming state, so reserve it everywhere.
+ for (MethodNamingState state : collectedStates) {
+ state.reserveName();
+ }
+ return;
+ }
+ // We use the origin state to allocate a name here so that we can reuse names between different
+ // unrelated interfaces. This saves some space. The alternative would be to use a global state
+ // for allocating names, which would save the work to search here.
+ DexString previousCandidate = null;
+ DexString candidate;
+ do {
+ candidate = originState.assignNewName();
+ // If the state returns the same candidate for two consecutive trials, it should be this case:
+ // 1) an interface method with the same signature (name, param) but different return type
+ // has been already renamed; and 2) -useuniqueclassmembernames is set.
+ // The option forces the naming state to return the same renamed name for the same signature.
+ // So, here we break the loop in an ad-hoc manner.
+ if (candidate != null && candidate == previousCandidate) {
+ assert minifierState.useUniqueMemberNames();
+ break;
+ }
+ for (MethodNamingState state : collectedStates) {
+ if (!state.isAvailable(candidate)) {
+ previousCandidate = candidate;
+ candidate = null;
+ break;
+ }
+ }
+ } while (candidate == null);
+ for (MethodNamingState state : collectedStates) {
+ state.addRenaming(candidate);
+ }
+ // Rename all methods in interfaces that gave rise to this renaming.
+ for (DexMethod sourceMethod : sourceMethods) {
+ minifierState.putRenaming(sourceMethod, candidate);
+ }
+ }
+
+ private void addStatesToGlobalMapForMethod(
+ DexEncodedMethod method,
+ Set<NamingState<DexProto, ?>> collectedStates,
+ DexType originInterface) {
+ Wrapper<DexMethod> key = equivalence.wrap(method.method);
+ Set<NamingState<DexProto, ?>> stateSet =
+ globalStateMap.computeIfAbsent(key, k -> new HashSet<>());
+ stateSet.addAll(collectedStates);
+ sourceMethodsMap.computeIfAbsent(key, k -> new HashSet<>()).add(method.method);
+ originStates.putIfAbsent(key, minifierState.getState(originInterface));
+ }
+
+ private boolean anyIsReserved(List<MethodNamingState> collectedStates) {
+ DexString name = collectedStates.get(0).getName();
+ Map<DexProto, Boolean> globalStateCache = new IdentityHashMap<>();
+ for (MethodNamingState state : collectedStates) {
+ assert state.getName() == name;
+ boolean isReservedInGlobalState =
+ globalStateCache.computeIfAbsent(
+ state.getProto(), proto -> minifierState.isReservedInGlobalState(name, proto));
+ // TODO(christofferqa): Should this be using logical OR instead?
+ if (isReservedInGlobalState && state.isReserved()) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ private Set<NamingState<DexProto, ?>> getReachableStates(DexType type) {
+ Set<DexType> interfaces = Sets.newIdentityHashSet();
+ interfaces.add(type);
+ collectSuperInterfaces(type, interfaces);
+ collectSubInterfaces(type, interfaces);
+ Set<NamingState<DexProto, ?>> reachableStates = new HashSet<>();
+ for (DexType iface : interfaces) {
+ // Add the interface itself
+ reachableStates.add(minifierState.getState(iface));
+ // And the frontiers that correspond to the classes that implement the interface.
+ for (DexType t : iface.allImplementsSubtypes()) {
+ NamingState<DexProto, ?> state = minifierState.getState(frontierState.get(t));
+ assert state != null;
+ reachableStates.add(state);
+ }
+ }
+ return reachableStates;
+ }
+
+ private void collectSuperInterfaces(DexType iface, Set<DexType> interfaces) {
+ DexClass clazz = appInfo.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);
+ }
+ }
+ }
+ }
+
+ private void collectSubInterfaces(DexType iface, Set<DexType> interfaces) {
+ for (DexType subtype : iface.allExtendsSubtypes()) {
+ assert subtype.isInterface();
+ if (interfaces.add(subtype)) {
+ collectSubInterfaces(subtype, interfaces);
+ }
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/naming/MemberNameMinifier.java b/src/main/java/com/android/tools/r8/naming/MemberNameMinifier.java
index 7f28744..8117dd5 100644
--- a/src/main/java/com/android/tools/r8/naming/MemberNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/MemberNameMinifier.java
@@ -9,6 +9,8 @@
import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
import com.android.tools.r8.utils.InternalOptions;
+import com.google.common.collect.BiMap;
+import com.google.common.collect.HashBiMap;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
@@ -22,11 +24,16 @@
protected final List<String> dictionary;
protected final Map<MemberType, DexString> renaming = new IdentityHashMap<>();
- protected final Map<DexType, NamingState<StateType, ?>> states = new IdentityHashMap<>();
protected final NamingState<StateType, ?> globalState;
protected final boolean useUniqueMemberNames;
protected final boolean overloadAggressively;
+ protected final State minifierState = new State();
+
+ // The use of a bidirectional map allows us to map a naming state to the type it represents,
+ // which is useful for debugging.
+ private final BiMap<DexType, NamingState<StateType, ?>> states = HashBiMap.create();
+
MemberNameMinifier(AppInfoWithLiveness appInfo, RootSet rootSet, InternalOptions options) {
this.appInfo = appInfo;
this.rootSet = rootSet;
@@ -46,7 +53,28 @@
return useUniqueMemberNames ? globalState : states.computeIfAbsent(type, f);
}
- protected NamingState<StateType, ?> getState(DexType type) {
- return useUniqueMemberNames ? globalState : states.get(type);
+ // A class that provides access to the minification state. An instance of this class is passed
+ // from the method name minifier to the interface method name minifier.
+ class State {
+
+ DexString getRenaming(MemberType key) {
+ return renaming.get(key);
+ }
+
+ void putRenaming(MemberType key, DexString value) {
+ renaming.put(key, value);
+ }
+
+ NamingState<StateType, ?> getState(DexType type) {
+ return useUniqueMemberNames ? globalState : states.get(type);
+ }
+
+ boolean isReservedInGlobalState(DexString name, StateType state) {
+ return globalState.isReserved(name, state);
+ }
+
+ boolean useUniqueMemberNames() {
+ return useUniqueMemberNames;
+ }
}
}
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 21e6bf9..4b67208 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
@@ -19,15 +19,9 @@
import com.google.common.base.Equivalence;
import com.google.common.base.Equivalence.Wrapper;
import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.Sets;
-import java.util.ArrayList;
-import java.util.Collections;
import java.util.HashMap;
-import java.util.HashSet;
import java.util.IdentityHashMap;
-import java.util.List;
import java.util.Map;
-import java.util.Map.Entry;
import java.util.Set;
import java.util.function.Function;
@@ -92,20 +86,15 @@
*/
class MethodNameMinifier extends MemberNameMinifier<DexMethod, DexProto> {
- private final Set<DexCallSite> desugaredCallSites;
-
private final Equivalence<DexMethod> equivalence;
- private final Map<DexCallSite, DexString> callSiteRenaming = new IdentityHashMap<>();
- private final Map<DexType, DexType> frontierMap = new IdentityHashMap<>();
+ private final FrontierState frontierState = new FrontierState();
MethodNameMinifier(
AppInfoWithLiveness appInfo,
RootSet rootSet,
- Set<DexCallSite> desugaredCallSites,
InternalOptions options) {
super(appInfo, rootSet, options);
- this.desugaredCallSites = desugaredCallSites;
equivalence =
overloadAggressively
? MethodSignatureEquivalence.get()
@@ -139,32 +128,32 @@
}
}
- MethodRenaming computeRenaming(Timing timing) {
+ MethodRenaming computeRenaming(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");
reserveNamesInClasses(
appInfo.dexItemFactory.objectType, appInfo.dexItemFactory.objectType, null);
timing.end();
- // Phase 2: Reserve all the names that are required for interfaces.
+ // Phase 2: Reserve all the names that are required for interfaces, and then assign names to
+ // interface methods. These are assigned by finding a name that is free in all naming
+ // states that may hold an implementation
timing.begin("Phase 2");
- DexType.forAllInterfaces(appInfo.dexItemFactory, this::reserveNamesInInterfaces);
+ InterfaceMethodNameMinifier interfaceMethodNameMinifier =
+ new InterfaceMethodNameMinifier(
+ appInfo, desugaredCallSites, equivalence, frontierState, minifierState, options);
+ interfaceMethodNameMinifier.assignNamesToInterfaceMethods(timing);
timing.end();
- // Phase 3: Assign names to interface methods. These are assigned by finding a name that is
- // free in all naming states that may hold an implementation.
+ // Phase 3: Assign names top-down by traversing the subtype hierarchy.
timing.begin("Phase 3");
- assignNamesToInterfaceMethods(timing);
- timing.end();
- // Phase 4: Assign names top-down by traversing the subtype hierarchy.
- timing.begin("Phase 4");
assignNamesToClassesMethods(appInfo.dexItemFactory.objectType, false);
timing.end();
// Phase 4: Do the same for private methods.
- timing.begin("Phase 5");
+ timing.begin("Phase 4");
assignNamesToClassesMethods(appInfo.dexItemFactory.objectType, true);
timing.end();
- return new MethodRenaming(renaming, callSiteRenaming);
+ return new MethodRenaming(renaming, interfaceMethodNameMinifier.getCallSiteRenamings());
}
private void assignNamesToClassesMethods(DexType type, boolean doPrivates) {
@@ -172,7 +161,7 @@
if (holder != null && !holder.isLibraryClass()) {
Map<Wrapper<DexMethod>, DexString> renamingAtThisLevel = new HashMap<>();
NamingState<DexProto, ?> state =
- computeStateIfAbsent(type, k -> getState(holder.superType).createChild());
+ computeStateIfAbsent(type, k -> minifierState.getState(holder.superType).createChild());
for (DexEncodedMethod method : holder.allMethodsSorted()) {
assignNameToMethod(method, state, renamingAtThisLevel, doPrivates);
}
@@ -206,249 +195,14 @@
}
}
- private Set<NamingState<DexProto, ?>> getReachableStates(DexType type) {
- Set<DexType> interfaces = Sets.newIdentityHashSet();
- interfaces.add(type);
- collectSuperInterfaces(type, interfaces);
- collectSubInterfaces(type, interfaces);
- Set<NamingState<DexProto, ?>> reachableStates = new HashSet<>();
- for (DexType iface : interfaces) {
- // Add the interface itself
- reachableStates.add(getState(iface));
- // And the frontiers that correspond to the classes that implement the interface.
- iface.forAllImplementsSubtypes(t -> {
- NamingState<DexProto, ?> state = getState(frontierMap.get(t));
- assert state != null;
- reachableStates.add(state);
- });
- }
- return reachableStates;
- }
-
- private void assignNamesToInterfaceMethods(Timing timing) {
- // 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");
- // A map from DexMethods to all the states linked to interfaces they appear in.
- Map<Wrapper<DexMethod>, Set<NamingState<DexProto, ?>>> globalStateMap = new HashMap<>();
- // A map from DexMethods to all the definitions seen. Needed as the Wrapper equalizes them all.
- Map<Wrapper<DexMethod>, Set<DexMethod>> sourceMethodsMap = new HashMap<>();
- // A map from DexMethods to the first interface state it was seen in. Used to pick good names.
- Map<Wrapper<DexMethod>, NamingState<DexProto, ?>> originStates = new HashMap<>();
- DexType.forAllInterfaces(
- appInfo.dexItemFactory,
- iface -> {
- assert iface.isInterface();
- DexClass clazz = appInfo.definitionFor(iface);
- if (clazz != null) {
- assert clazz.isInterface();
- Set<NamingState<DexProto, ?>> collectedStates = getReachableStates(iface);
- for (DexEncodedMethod method : shuffleMethods(clazz.methods())) {
- addStatesToGlobalMapForMethod(
- method, collectedStates, globalStateMap, sourceMethodsMap, originStates, iface);
- }
- }
- });
- // Collect the live call sites for multi-interface lambda expression renaming. For code with
- // desugared lambdas this is a conservative estimate, as we don't track if the generated
- // lambda classes survive into the output. As multi-interface lambda expressions are rare
- // this is not a big deal.
- Set<DexCallSite> liveCallSites = Sets.union(desugaredCallSites, appInfo.callSites);
- // If the input program contains a multi-interface lambda expression that implements
- // interface methods with different protos, we need to make sure that
- // the implemented lambda methods are renamed to the same name.
- // To achieve this, we map each DexCallSite that corresponds to a lambda expression to one of
- // the DexMethods it implements, and we unify the DexMethods that need to be renamed together.
- Map<DexCallSite, DexMethod> callSites = new IdentityHashMap<>();
- // Union-find structure to keep track of methods that must be renamed together.
- // Note that if the input does not use multi-interface lambdas,
- // unificationParent will remain empty.
- Map<Wrapper<DexMethod>, Wrapper<DexMethod>> unificationParent = new HashMap<>();
- liveCallSites.forEach(
- callSite -> {
- Set<Wrapper<DexMethod>> callSiteMethods = new HashSet<>();
- // Don't report errors, as the set of call sites is a conservative estimate, and can
- // refer to interfaces which has been removed.
- Set<DexEncodedMethod> implementedMethods =
- appInfo.lookupLambdaImplementedMethods(callSite);
- if (implementedMethods.isEmpty()) {
- return;
- }
- callSites.put(callSite, implementedMethods.iterator().next().method);
- for (DexEncodedMethod method : implementedMethods) {
- DexType iface = method.method.holder;
- assert iface.isInterface();
- Set<NamingState<DexProto, ?>> collectedStates = getReachableStates(iface);
- addStatesToGlobalMapForMethod(
- method, collectedStates, globalStateMap, sourceMethodsMap, originStates, iface);
- callSiteMethods.add(equivalence.wrap(method.method));
- }
- if (callSiteMethods.size() > 1) {
- // Implemented interfaces have different return types. Unify them.
- Wrapper<DexMethod> mainKey = callSiteMethods.iterator().next();
- mainKey = unificationParent.getOrDefault(mainKey, mainKey);
- for (Wrapper<DexMethod> key : callSiteMethods) {
- unificationParent.put(key, mainKey);
- }
- }
- });
- Map<Wrapper<DexMethod>, Set<Wrapper<DexMethod>>> unification = new HashMap<>();
- for (Wrapper<DexMethod> key : unificationParent.keySet()) {
- // Find root with path-compression.
- Wrapper<DexMethod> root = unificationParent.get(key);
- while (unificationParent.get(root) != root) {
- Wrapper<DexMethod> k = unificationParent.get(unificationParent.get(root));
- unificationParent.put(root, k);
- root = k;
- }
- unification.computeIfAbsent(root, k -> new HashSet<>()).add(key);
- }
- timing.end();
- // Go over every method and assign a name.
- timing.begin("Allocate names");
- // Sort the methods by the number of dependent states, so that we use short names for methods
- // references in many places.
- List<Wrapper<DexMethod>> methods = new ArrayList<>(globalStateMap.keySet());
- methods.sort((a, b) -> globalStateMap.get(b).size() - globalStateMap.get(a).size());
- for (Wrapper<DexMethod> key : methods) {
- if (!unificationParent.getOrDefault(key, key).equals(key)) {
- continue;
- }
- List<MethodNamingState> collectedStates = new ArrayList<>();
- Set<DexMethod> sourceMethods = Sets.newIdentityHashSet();
- for (Wrapper<DexMethod> k : unification.getOrDefault(key, Collections.singleton(key))) {
- DexMethod unifiedMethod = k.get();
- assert unifiedMethod != null;
- sourceMethods.addAll(sourceMethodsMap.get(k));
- for (NamingState<DexProto, ?> namingState : globalStateMap.get(k)) {
- collectedStates.add(
- new MethodNamingState(namingState, unifiedMethod.name, unifiedMethod.proto));
- }
- }
- DexMethod method = key.get();
- assert method != null;
- MethodNamingState originState =
- new MethodNamingState(originStates.get(key), method.name, method.proto);
- assignNameForInterfaceMethodInAllStates(collectedStates, sourceMethods, originState);
- }
- for (Entry<DexCallSite, DexMethod> entry : callSites.entrySet()) {
- DexMethod method = entry.getValue();
- DexString renamed = renaming.get(method);
- if (originStates.get(equivalence.wrap(method)).isReserved(method.name, method.proto)) {
- assert renamed == null;
- callSiteRenaming.put(entry.getKey(), method.name);
- } else {
- assert renamed != null;
- callSiteRenaming.put(entry.getKey(), renamed);
- }
- }
- timing.end();
- }
-
- private void collectSuperInterfaces(DexType iface, Set<DexType> interfaces) {
- DexClass clazz = appInfo.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);
- }
- }
- }
- }
-
- private void collectSubInterfaces(DexType iface, Set<DexType> interfaces) {
- iface.forAllExtendsSubtypes(subtype -> {
- assert subtype.isInterface();
- if (interfaces.add(subtype)) {
- collectSubInterfaces(subtype, interfaces);
- }
- });
- }
-
- private void addStatesToGlobalMapForMethod(
- DexEncodedMethod method,
- Set<NamingState<DexProto, ?>> collectedStates,
- Map<Wrapper<DexMethod>, Set<NamingState<DexProto, ?>>> globalStateMap,
- Map<Wrapper<DexMethod>, Set<DexMethod>> sourceMethodsMap,
- Map<Wrapper<DexMethod>, NamingState<DexProto, ?>> originStates,
- DexType originInterface) {
- Wrapper<DexMethod> key = equivalence.wrap(method.method);
- Set<NamingState<DexProto, ?>> stateSet =
- globalStateMap.computeIfAbsent(key, k -> new HashSet<>());
- stateSet.addAll(collectedStates);
- sourceMethodsMap.computeIfAbsent(key, k -> new HashSet<>()).add(method.method);
- originStates.putIfAbsent(key, getState(originInterface));
- }
-
- private void assignNameForInterfaceMethodInAllStates(
- List<MethodNamingState> collectedStates,
- Set<DexMethod> sourceMethods,
- MethodNamingState originState) {
- if (anyIsReserved(collectedStates)) {
- // This method's name is reserved in at least one naming state, so reserve it everywhere.
- for (MethodNamingState state : collectedStates) {
- state.reserveName();
- }
- return;
- }
- // We use the origin state to allocate a name here so that we can reuse names between different
- // unrelated interfaces. This saves some space. The alternative would be to use a global state
- // for allocating names, which would save the work to search here.
- DexString previousCandidate = null;
- DexString candidate;
- do {
- candidate = originState.assignNewNameFor(false);
- // If the state returns the same candidate for two consecutive trials, it should be this case:
- // 1) an interface method with the same signature (name, param) but different return type
- // has been already renamed; and 2) -useuniqueclassmembernames is set.
- // The option forces the naming state to return the same renamed name for the same signature.
- // So, here we break the loop in an ad-hoc manner.
- if (candidate != null && candidate == previousCandidate) {
- assert useUniqueMemberNames;
- break;
- }
- for (MethodNamingState state : collectedStates) {
- if (!state.isAvailable(candidate)) {
- previousCandidate = candidate;
- candidate = null;
- break;
- }
- }
- } while (candidate == null);
- for (MethodNamingState state : collectedStates) {
- state.addRenaming(candidate);
- }
- // Rename all methods in interfaces that gave rise to this renaming.
- for (DexMethod sourceMethod : sourceMethods) {
- renaming.put(sourceMethod, candidate);
- }
- }
-
- private boolean anyIsReserved(List<MethodNamingState> collectedStates) {
- DexString name = collectedStates.get(0).getName();
- Map<DexProto, Boolean> globalStateCache = new HashMap<>();
- for (MethodNamingState state : collectedStates) {
- assert state.getName() == name;
- if (globalStateCache.computeIfAbsent(
- state.getProto(), proto -> globalState.isReserved(name, proto))
- && state.isReserved()) {
- return true;
- }
- }
- return false;
- }
-
private void reserveNamesInClasses(
DexType type, DexType libraryFrontier, NamingState<DexProto, ?> parent) {
assert !type.isInterface();
- DexClass holder = appInfo.definitionFor(type);
NamingState<DexProto, ?> state =
- allocateNamingStateAndReserve(holder, type, libraryFrontier, parent);
+ frontierState.allocateNamingStateAndReserve(type, libraryFrontier, parent);
// If this is a library class (or effectively a library class as it is missing) move the
// frontier forward.
+ DexClass holder = appInfo.definitionFor(type);
type.forAllExtendsSubtypes(
subtype -> {
assert !subtype.isInterface();
@@ -459,32 +213,6 @@
});
}
- private void reserveNamesInInterfaces(DexType type) {
- assert type.isInterface();
- frontierMap.put(type, type);
- DexClass holder = appInfo.definitionFor(type);
- allocateNamingStateAndReserve(holder, type, type, null);
- }
-
- private NamingState<DexProto, ?> allocateNamingStateAndReserve(
- DexClass holder, DexType type, DexType libraryFrontier, NamingState<DexProto, ?> parent) {
- frontierMap.put(type, libraryFrontier);
- NamingState<DexProto, ?> state =
- computeStateIfAbsent(
- libraryFrontier,
- ignore -> parent == null
- ? NamingState.createRoot(
- appInfo.dexItemFactory, dictionary, getKeyTransform(), useUniqueMemberNames)
- : parent.createChild());
- if (holder != null) {
- boolean keepAll = holder.isLibraryClass() || holder.accessFlags.isAnnotation();
- for (DexEncodedMethod method : shuffleMethods(holder.methods())) {
- reserveNamesForMethod(method, keepAll, state);
- }
- }
- return state;
- }
-
private void reserveNamesForMethod(
DexEncodedMethod encodedMethod, boolean keepAll, NamingState<DexProto, ?> state) {
DexMethod method = encodedMethod.method;
@@ -494,12 +222,52 @@
}
}
+ class FrontierState {
+
+ private final Map<DexType, DexType> frontiers = new IdentityHashMap<>();
+
+ NamingState<DexProto, ?> allocateNamingStateAndReserve(
+ DexType type, DexType libraryFrontier, NamingState<DexProto, ?> parent) {
+ frontiers.put(type, libraryFrontier);
+
+ NamingState<DexProto, ?> state =
+ computeStateIfAbsent(
+ libraryFrontier,
+ ignore ->
+ parent == null
+ ? NamingState.createRoot(
+ appInfo.dexItemFactory,
+ dictionary,
+ getKeyTransform(),
+ useUniqueMemberNames)
+ : parent.createChild());
+
+ DexClass holder = appInfo.definitionFor(type);
+ if (holder != null) {
+ boolean keepAll = holder.isLibraryClass() || holder.accessFlags.isAnnotation();
+ for (DexEncodedMethod method : shuffleMethods(holder.methods(), options)) {
+ reserveNamesForMethod(method, keepAll, state);
+ }
+ }
+
+ return state;
+ }
+
+ public DexType get(DexType type) {
+ return frontiers.get(type);
+ }
+
+ public DexType put(DexType type, DexType frontier) {
+ return frontiers.put(type, frontier);
+ }
+ }
+
/**
* Capture a (name, proto)-pair for a {@link NamingState}. Each method methodState.METHOD(...)
* simply defers to parent.METHOD(name, proto, ...). This allows R8 to assign the same name to
* methods with different prototypes, which is needed for multi-interface lambdas.
*/
- private static class MethodNamingState {
+ static class MethodNamingState {
private final NamingState<DexProto, ?> parent;
private final DexString name;
@@ -512,8 +280,8 @@
this.proto = proto;
}
- DexString assignNewNameFor(boolean markAsUsed) {
- return parent.assignNewNameFor(name, proto, markAsUsed);
+ DexString assignNewName() {
+ return parent.assignNewNameFor(name, proto, false);
}
void reserveName() {
@@ -543,7 +311,8 @@
// Shuffles the given methods if assertions are enabled and deterministic debugging is disabled.
// Used to ensure that the generated output is deterministic.
- private Iterable<DexEncodedMethod> shuffleMethods(Iterable<DexEncodedMethod> methods) {
+ static Iterable<DexEncodedMethod> shuffleMethods(
+ Iterable<DexEncodedMethod> methods, InternalOptions options) {
return options.testing.irOrdering.order(methods);
}
}
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 becc643..5333125 100644
--- a/src/main/java/com/android/tools/r8/naming/Minifier.java
+++ b/src/main/java/com/android/tools/r8/naming/Minifier.java
@@ -64,8 +64,8 @@
timing.begin("MinifyMethods");
MethodRenaming methodRenaming =
- new MethodNameMinifier(appInfo, rootSet, desugaredCallSites, options)
- .computeRenaming(timing);
+ new MethodNameMinifier(appInfo, rootSet, options)
+ .computeRenaming(desugaredCallSites, timing);
timing.end();
assert new MinifiedRenaming(classRenaming, methodRenaming, FieldRenaming.empty(), appInfo)
diff --git a/src/main/java/com/android/tools/r8/naming/NamingState.java b/src/main/java/com/android/tools/r8/naming/NamingState.java
index 999579a..f0f1720 100644
--- a/src/main/java/com/android/tools/r8/naming/NamingState.java
+++ b/src/main/java/com/android/tools/r8/naming/NamingState.java
@@ -129,7 +129,7 @@
state.addRenaming(original, key, newName);
}
- private class InternalState {
+ class InternalState {
private static final int INITIAL_NAME_COUNT = 1;
private final char[] EMPTY_CHAR_ARRAY = new char[0];
