Refactor member pool collection.
Change-Id: I9b3a4a6dfc457258613f033f6e05e5cc195be0de
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/MemberPoolCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/MemberPoolCollection.java
new file mode 100644
index 0000000..f593f45
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/MemberPoolCollection.java
@@ -0,0 +1,212 @@
+// 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.ir.optimize;
+
+import com.android.tools.r8.graph.Descriptor;
+import com.android.tools.r8.graph.DexApplication;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.utils.ThreadUtils;
+import com.android.tools.r8.utils.Timing;
+import com.google.common.base.Equivalence;
+import com.google.common.base.Equivalence.Wrapper;
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Deque;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Future;
+import java.util.function.Predicate;
+
+// Per-class collection of member signatures.
+public abstract class MemberPoolCollection<T extends Descriptor> {
+
+ final Equivalence<T> equivalence;
+ final DexApplication application;
+ final Map<DexClass, MemberPool<T>> memberPools = new ConcurrentHashMap<>();
+
+ MemberPoolCollection(DexApplication application, Equivalence<T> equivalence) {
+ this.application = application;
+ this.equivalence = equivalence;
+ }
+
+ public void buildAll(ExecutorService executorService, Timing timing) throws ExecutionException {
+ timing.begin("Building member pool collection");
+ try {
+ List<Future<?>> futures = new ArrayList<>();
+ List<? extends DexClass> classes = application.classes();
+ submitAll(classes, futures, executorService);
+ ThreadUtils.awaitFutures(futures);
+ } finally {
+ timing.end();
+ }
+ }
+
+ public MemberPool<T> buildForHierarchy(
+ DexClass clazz, ExecutorService executorService, Timing timing) throws ExecutionException {
+ timing.begin("Building member pool collection");
+ try {
+ List<Future<?>> futures = new ArrayList<>();
+ submitAll(
+ getAllSuperTypesInclusive(clazz, memberPools::containsKey), futures, executorService);
+ submitAll(getAllSubTypesExclusive(clazz, memberPools::containsKey), futures, executorService);
+ ThreadUtils.awaitFutures(futures);
+ } finally {
+ timing.end();
+ }
+ return get(clazz);
+ }
+
+ public boolean hasPool(DexClass clazz) {
+ return memberPools.containsKey(clazz);
+ }
+
+ public MemberPool<T> get(DexClass clazz) {
+ assert hasPool(clazz);
+ return memberPools.get(clazz);
+ }
+
+ public boolean markIfNotSeen(DexClass clazz, T reference) {
+ MemberPool<T> memberPool = get(clazz);
+ Wrapper<T> key = equivalence.wrap(reference);
+ if (memberPool.hasSeen(key)) {
+ return true;
+ }
+ memberPool.seen(key);
+ return false;
+ }
+
+ private void submitAll(
+ Iterable<? extends DexClass> classes,
+ List<Future<?>> futures,
+ ExecutorService executorService) {
+ for (DexClass clazz : classes) {
+ futures.add(executorService.submit(computeMemberPoolForClass(clazz)));
+ }
+ }
+
+ abstract Runnable computeMemberPoolForClass(DexClass clazz);
+
+ // TODO(jsjeon): maybe be part of AppInfoWithSubtyping?
+ private Set<DexClass> getAllSuperTypesInclusive(
+ DexClass subject, Predicate<DexClass> stoppingCriterion) {
+ Set<DexClass> superTypes = new HashSet<>();
+ Deque<DexClass> worklist = new ArrayDeque<>();
+ worklist.add(subject);
+ while (!worklist.isEmpty()) {
+ DexClass clazz = worklist.pop();
+ if (stoppingCriterion.test(clazz)) {
+ continue;
+ }
+ if (superTypes.add(clazz)) {
+ if (clazz.superType != null) {
+ addNonNull(worklist, application.definitionFor(clazz.superType));
+ }
+ for (DexType interfaceType : clazz.interfaces.values) {
+ addNonNull(worklist, application.definitionFor(interfaceType));
+ }
+ }
+ }
+ return superTypes;
+ }
+
+ // TODO(jsjeon): maybe be part of AppInfoWithSubtyping?
+ private Set<DexClass> getAllSubTypesExclusive(
+ DexClass subject, Predicate<DexClass> stoppingCriterion) {
+ Set<DexClass> subTypes = new HashSet<>();
+ Deque<DexClass> worklist = new ArrayDeque<>();
+ subject.type.forAllExtendsSubtypes(
+ type -> addNonNull(worklist, application.definitionFor(type)));
+ subject.type.forAllImplementsSubtypes(
+ type -> addNonNull(worklist, application.definitionFor(type)));
+ while (!worklist.isEmpty()) {
+ DexClass clazz = worklist.pop();
+ if (stoppingCriterion.test(clazz)) {
+ continue;
+ }
+ if (subTypes.add(clazz)) {
+ clazz.type.forAllExtendsSubtypes(
+ type -> addNonNull(worklist, application.definitionFor(type)));
+ clazz.type.forAllImplementsSubtypes(
+ type -> addNonNull(worklist, application.definitionFor(type)));
+ }
+ }
+ return subTypes;
+ }
+
+ public static class MemberPool<T> {
+ private Equivalence<T> equivalence;
+ private MemberPool<T> superType;
+ private final Set<MemberPool<T>> interfaces = new HashSet<>();
+ private final Set<MemberPool<T>> subTypes = new HashSet<>();
+ private final Set<Wrapper<T>> memberPool = new HashSet<>();
+
+ MemberPool(Equivalence<T> equivalence) {
+ this.equivalence = equivalence;
+ }
+
+ synchronized void linkSupertype(MemberPool<T> superType) {
+ assert this.superType == null;
+ this.superType = superType;
+ }
+
+ synchronized void linkSubtype(MemberPool<T> subType) {
+ boolean added = subTypes.add(subType);
+ assert added;
+ }
+
+ synchronized void linkInterface(MemberPool<T> itf) {
+ boolean added = interfaces.add(itf);
+ assert added;
+ }
+
+ public void seen(T descriptor) {
+ seen(equivalence.wrap(descriptor));
+ }
+
+ public synchronized void seen(Wrapper<T> descriptor) {
+ boolean added = memberPool.add(descriptor);
+ assert added;
+ }
+
+ public boolean hasSeen(T descriptor) {
+ return hasSeen(equivalence.wrap(descriptor));
+ }
+
+ public boolean hasSeen(Wrapper<T> descriptor) {
+ return hasSeenUpwardRecursive(descriptor) || hasSeenDownwardRecursive(descriptor);
+ }
+
+ public boolean hasSeenDirectly(T descriptor) {
+ return hasSeenDirectly(equivalence.wrap(descriptor));
+ }
+
+ public boolean hasSeenDirectly(Wrapper<T> descriptor) {
+ return memberPool.contains(descriptor);
+ }
+
+ private boolean hasSeenUpwardRecursive(Wrapper<T> descriptor) {
+ return memberPool.contains(descriptor)
+ || (superType != null && superType.hasSeenUpwardRecursive(descriptor))
+ || interfaces.stream().anyMatch(itf -> itf.hasSeenUpwardRecursive(descriptor));
+ }
+
+ private boolean hasSeenDownwardRecursive(Wrapper<T> reference) {
+ return memberPool.contains(reference)
+ || subTypes.stream().anyMatch(subType -> subType.hasSeenDownwardRecursive(reference));
+ }
+ }
+
+ private static <T> void addNonNull(Collection<T> collection, T item) {
+ if (item != null) {
+ collection.add(item);
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java
index ca38f09..68b32ea 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java
@@ -7,93 +7,30 @@
import com.android.tools.r8.graph.DexApplication;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.utils.MethodSignatureEquivalence;
-import com.android.tools.r8.utils.ThreadUtils;
-import com.android.tools.r8.utils.Timing;
-import com.google.common.base.Equivalence;
-import com.google.common.base.Equivalence.Wrapper;
-import java.util.ArrayDeque;
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Deque;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-import java.util.concurrent.ConcurrentHashMap;
-import java.util.concurrent.ExecutionException;
-import java.util.concurrent.ExecutorService;
-import java.util.concurrent.Future;
-import java.util.function.Predicate;
// Per-class collection of method signatures.
//
-// Example use case: to determine if a certain method can be publicized or not.
-public class MethodPoolCollection {
-
- private static final Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get();
-
- private final DexApplication application;
- private final Map<DexClass, MethodPool> methodPools = new ConcurrentHashMap<>();
+// Example use cases:
+// *) in publicizer,
+// to determine if a private method does not collide with methods in that class hierarchy.
+// *) in vertical class merger,
+// before moving a default interface method to its subtype, check if it does not collide with one
+// in the given class hierarchy.
+// *) in uninstantiated type optimizer,
+// to avoid signature collisions while discarding unused return type or parameters.
+// TODO(b/66369976): to determine if a certain method can be made `final`.
+public class MethodPoolCollection extends MemberPoolCollection<DexMethod> {
public MethodPoolCollection(DexApplication application) {
- this.application = application;
+ super(application, MethodSignatureEquivalence.get());
}
- public void buildAll(ExecutorService executorService, Timing timing) throws ExecutionException {
- timing.begin("Building method pool collection");
- try {
- List<Future<?>> futures = new ArrayList<>();
- @SuppressWarnings("unchecked")
- List<DexClass> classes = (List) application.classes();
- submitAll(classes, futures, executorService);
- ThreadUtils.awaitFutures(futures);
- } finally {
- timing.end();
- }
- }
-
- public MethodPool buildForHierarchy(
- DexClass clazz, ExecutorService executorService, Timing timing) throws ExecutionException {
- timing.begin("Building method pool collection");
- try {
- List<Future<?>> futures = new ArrayList<>();
- submitAll(
- getAllSuperTypesInclusive(clazz, methodPools::containsKey), futures, executorService);
- submitAll(getAllSubTypesExclusive(clazz, methodPools::containsKey), futures, executorService);
- ThreadUtils.awaitFutures(futures);
- } finally {
- timing.end();
- }
- return get(clazz);
- }
-
- public MethodPool get(DexClass clazz) {
- assert methodPools.containsKey(clazz);
- return methodPools.get(clazz);
- }
-
- public boolean markIfNotSeen(DexClass clazz, DexMethod method) {
- MethodPool methodPool = get(clazz);
- Wrapper<DexMethod> key = equivalence.wrap(method);
- if (methodPool.hasSeen(key)) {
- return true;
- }
- methodPool.seen(key);
- return false;
- }
-
- private void submitAll(
- Iterable<DexClass> classes, List<Future<?>> futures, ExecutorService executorService) {
- for (DexClass clazz : classes) {
- futures.add(executorService.submit(computeMethodPoolPerClass(clazz)));
- }
- }
-
- private Runnable computeMethodPoolPerClass(DexClass clazz) {
+ @Override
+ Runnable computeMemberPoolForClass(DexClass clazz) {
return () -> {
- MethodPool methodPool = methodPools.computeIfAbsent(clazz, k -> new MethodPool());
+ MemberPool<DexMethod> methodPool =
+ memberPools.computeIfAbsent(clazz, k -> new MemberPool<>(equivalence));
clazz.forEachMethod(
encodedMethod -> {
// We will add private instance methods when we promote them.
@@ -104,7 +41,8 @@
if (clazz.superType != null) {
DexClass superClazz = application.definitionFor(clazz.superType);
if (superClazz != null) {
- MethodPool superPool = methodPools.computeIfAbsent(superClazz, k -> new MethodPool());
+ MemberPool<DexMethod> superPool =
+ memberPools.computeIfAbsent(superClazz, k -> new MemberPool<>(equivalence));
superPool.linkSubtype(methodPool);
methodPool.linkSupertype(superPool);
}
@@ -114,7 +52,8 @@
implementer -> {
DexClass subClazz = application.definitionFor(implementer);
if (subClazz != null) {
- MethodPool childPool = methodPools.computeIfAbsent(subClazz, k -> new MethodPool());
+ MemberPool<DexMethod> childPool =
+ memberPools.computeIfAbsent(subClazz, k -> new MemberPool<>(equivalence));
childPool.linkInterface(methodPool);
}
});
@@ -122,106 +61,4 @@
};
}
- private Set<DexClass> getAllSuperTypesInclusive(
- DexClass subject, Predicate<DexClass> stoppingCriterion) {
- Set<DexClass> superTypes = new HashSet<>();
- Deque<DexClass> worklist = new ArrayDeque<>();
- worklist.add(subject);
- while (!worklist.isEmpty()) {
- DexClass clazz = worklist.pop();
- if (stoppingCriterion.test(clazz)) {
- continue;
- }
- if (superTypes.add(clazz)) {
- if (clazz.superType != null) {
- addNonNull(worklist, application.definitionFor(clazz.superType));
- }
- for (DexType interfaceType : clazz.interfaces.values) {
- addNonNull(worklist, application.definitionFor(interfaceType));
- }
- }
- }
- return superTypes;
- }
-
- private Set<DexClass> getAllSubTypesExclusive(
- DexClass subject, Predicate<DexClass> stoppingCriterion) {
- Set<DexClass> subTypes = new HashSet<>();
- Deque<DexClass> worklist = new ArrayDeque<>();
- subject.type.forAllExtendsSubtypes(
- type -> addNonNull(worklist, application.definitionFor(type)));
- subject.type.forAllImplementsSubtypes(
- type -> addNonNull(worklist, application.definitionFor(type)));
- while (!worklist.isEmpty()) {
- DexClass clazz = worklist.pop();
- if (stoppingCriterion.test(clazz)) {
- continue;
- }
- if (subTypes.add(clazz)) {
- clazz.type.forAllExtendsSubtypes(
- type -> addNonNull(worklist, application.definitionFor(type)));
- clazz.type.forAllImplementsSubtypes(
- type -> addNonNull(worklist, application.definitionFor(type)));
- }
- }
- return subTypes;
- }
-
- public static class MethodPool {
- private MethodPool superType;
- private final Set<MethodPool> interfaces = new HashSet<>();
- private final Set<MethodPool> subTypes = new HashSet<>();
- private final Set<Wrapper<DexMethod>> methodPool = new HashSet<>();
-
- private MethodPool() {}
-
- synchronized void linkSupertype(MethodPool superType) {
- assert this.superType == null;
- this.superType = superType;
- }
-
- synchronized void linkSubtype(MethodPool subType) {
- boolean added = subTypes.add(subType);
- assert added;
- }
-
- synchronized void linkInterface(MethodPool itf) {
- boolean added = interfaces.add(itf);
- assert added;
- }
-
- public void seen(DexMethod method) {
- seen(MethodSignatureEquivalence.get().wrap(method));
- }
-
- public synchronized void seen(Wrapper<DexMethod> method) {
- boolean added = methodPool.add(method);
- assert added;
- }
-
- public boolean hasSeen(Wrapper<DexMethod> method) {
- return hasSeenUpwardRecursive(method) || hasSeenDownwardRecursive(method);
- }
-
- public boolean hasSeenDirectly(Wrapper<DexMethod> method) {
- return methodPool.contains(method);
- }
-
- private boolean hasSeenUpwardRecursive(Wrapper<DexMethod> method) {
- return methodPool.contains(method)
- || (superType != null && superType.hasSeenUpwardRecursive(method))
- || interfaces.stream().anyMatch(itf -> itf.hasSeenUpwardRecursive(method));
- }
-
- private boolean hasSeenDownwardRecursive(Wrapper<DexMethod> method) {
- return methodPool.contains(method)
- || subTypes.stream().anyMatch(subType -> subType.hasSeenDownwardRecursive(method));
- }
- }
-
- private static <T> void addNonNull(Collection<T> collection, T item) {
- if (item != null) {
- collection.add(item);
- }
- }
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java b/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
index e41593f..4cc3207 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
@@ -37,7 +37,7 @@
import com.android.tools.r8.ir.code.Position;
import com.android.tools.r8.ir.code.Throw;
import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.optimize.MethodPoolCollection.MethodPool;
+import com.android.tools.r8.ir.optimize.MemberPoolCollection.MemberPool;
import com.android.tools.r8.logging.Log;
import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
import com.android.tools.r8.utils.InternalOptions;
@@ -139,7 +139,7 @@
appView,
appView.appInfo().classes(),
clazz -> {
- MethodPool methodPool = methodPoolCollection.get(clazz);
+ MemberPool<DexMethod> methodPool = methodPoolCollection.get(clazz);
if (clazz.isInterface()) {
// Do not allow changing the prototype of methods that override an interface method.
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 fd90187..fe10045 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -36,8 +36,8 @@
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;
+import com.android.tools.r8.ir.optimize.MemberPoolCollection.MemberPool;
import com.android.tools.r8.ir.optimize.MethodPoolCollection;
-import com.android.tools.r8.ir.optimize.MethodPoolCollection.MethodPool;
import com.android.tools.r8.ir.synthetic.AbstractSynthesizedCode;
import com.android.tools.r8.ir.synthetic.ForwardMethodSourceCode;
import com.android.tools.r8.logging.Log;
@@ -941,7 +941,7 @@
// due to the way invoke-super works on default interface methods. In order to be able
// to hit this method directly after the merge, we need to make it public, and find a
// method name that does not collide with one in the hierarchy of this class.
- MethodPool methodPoolForTarget =
+ MemberPool<DexMethod> methodPoolForTarget =
methodPoolCollection.buildForHierarchy(target, executorService, timing);
resultingDirectMethod =
renameMethod(
