Remove use of subtyping info in bridge hoisting
Change-Id: I101c9c44cfb2c3fe11b8ab25c4e125da34b7de1e
diff --git a/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java b/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java
index b2ecd15..4205abc 100644
--- a/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java
+++ b/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java
@@ -4,16 +4,18 @@
package com.android.tools.r8.graph;
+import com.google.common.collect.Iterables;
+import java.util.Objects;
import java.util.function.Function;
public class BottomUpClassHierarchyTraversal<T extends DexClass>
extends ClassHierarchyTraversal<T, BottomUpClassHierarchyTraversal<T>> {
- private final Function<DexType, Iterable<DexType>> immediateSubtypesProvider;
+ private final Function<T, Iterable<T>> immediateSubtypesProvider;
private BottomUpClassHierarchyTraversal(
AppView<? extends AppInfoWithClassHierarchy> appView,
- Function<DexType, Iterable<DexType>> immediateSubtypesProvider,
+ Function<T, Iterable<T>> immediateSubtypesProvider,
Scope scope) {
super(appView, scope);
this.immediateSubtypesProvider = immediateSubtypesProvider;
@@ -26,16 +28,14 @@
public static BottomUpClassHierarchyTraversal<DexClass> forAllClasses(
AppView<? extends AppInfoWithClassHierarchy> appView, SubtypingInfo subtypingInfo) {
return new BottomUpClassHierarchyTraversal<>(
- appView, subtypingInfo::allImmediateSubtypes, Scope.ALL_CLASSES);
- }
-
- /**
- * Returns a visitor that can be used to visit all the program classes that are reachable from a
- * given set of sources.
- */
- public static BottomUpClassHierarchyTraversal<DexProgramClass> forProgramClasses(
- AppView<? extends AppInfoWithClassHierarchy> appView, SubtypingInfo subtypingInfo) {
- return forProgramClasses(appView, subtypingInfo::allImmediateSubtypes);
+ appView,
+ clazz ->
+ Iterables.filter(
+ Iterables.transform(
+ subtypingInfo.allImmediateSubtypes(clazz.getType()),
+ appView::contextIndependentDefinitionFor),
+ Objects::nonNull),
+ Scope.ALL_CLASSES);
}
/**
@@ -44,7 +44,17 @@
*/
public static BottomUpClassHierarchyTraversal<DexProgramClass> forProgramClasses(
AppView<? extends AppInfoWithClassHierarchy> appView,
- Function<DexType, Iterable<DexType>> immediateSubtypesProvider) {
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
+ return forProgramClasses(appView, immediateSubtypingInfo::getSubclasses);
+ }
+
+ /**
+ * Returns a visitor that can be used to visit all the program classes that are reachable from a
+ * given set of sources.
+ */
+ public static BottomUpClassHierarchyTraversal<DexProgramClass> forProgramClasses(
+ AppView<? extends AppInfoWithClassHierarchy> appView,
+ Function<DexProgramClass, Iterable<DexProgramClass>> immediateSubtypesProvider) {
return new BottomUpClassHierarchyTraversal<>(
appView, immediateSubtypesProvider, Scope.ONLY_PROGRAM_CLASSES);
}
@@ -70,12 +80,9 @@
worklist.addFirst(clazzWithTypeT);
// Add subtypes to worklist.
- for (DexType subtype : immediateSubtypesProvider.apply(clazz.getType())) {
- DexClass definition = definitionSupplier.contextIndependentDefinitionFor(subtype);
- if (definition != null) {
- if (scope != Scope.ONLY_PROGRAM_CLASSES || definition.isProgramClass()) {
- addDependentsToWorklist(definition);
- }
+ for (DexClass subclass : immediateSubtypesProvider.apply(clazzWithTypeT)) {
+ if (scope != Scope.ONLY_PROGRAM_CLASSES || subclass.isProgramClass()) {
+ addDependentsToWorklist(subclass);
}
}
}
diff --git a/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java b/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
index dace46c..1d27755 100644
--- a/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/SubtypingInfo.java
@@ -6,7 +6,6 @@
import static com.android.tools.r8.graph.DexApplication.classesWithDeterministicOrder;
import com.android.tools.r8.utils.structural.StructuralItem;
-import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Sets;
@@ -189,16 +188,6 @@
return subtypes == null ? ImmutableSet.of() : subtypes;
}
- public DexType getSingleDirectSubtype(DexType type) {
- TypeInfo info = getTypeInfo(type);
- assert info.hierarchyLevel != SubtypingInfo.UNKNOWN_LEVEL;
- if (info.directSubtypes.size() == 1) {
- return Iterables.getFirst(info.directSubtypes, null);
- } else {
- return null;
- }
- }
-
/**
* Apply the given function to all classes that directly extend this class.
*
@@ -223,25 +212,6 @@
}
}
- /**
- * Apply the given function to all classes that directly implement this interface.
- *
- * <p>The implementation does not consider how the hierarchy is encoded in the dex file, where
- * interfaces "implement" their super interfaces. Instead it takes the view of the source
- * language, where interfaces "extend" their superinterface.
- */
- public void forAllImmediateImplementsSubtypes(DexType type, Consumer<DexType> f) {
- allImmediateImplementsSubtypes(type).forEach(f);
- }
-
- public Iterable<DexType> allImmediateImplementsSubtypes(DexType type) {
- TypeInfo info = getTypeInfo(type);
- if (info.hierarchyLevel == SubtypingInfo.INTERFACE_LEVEL) {
- return Iterables.filter(info.directSubtypes, subtype -> !getTypeInfo(subtype).isInterface());
- }
- return ImmutableList.of();
- }
-
public Set<DexType> allImmediateSubtypes(DexType type) {
return getTypeInfo(type).directSubtypes;
}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
index 80b6dc7..9307f89 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
@@ -106,7 +106,13 @@
Timing timing)
throws ExecutionException {
// Run the policies on all program classes to produce a final grouping.
- List<Policy> policies = PolicyScheduler.getPolicies(appView, runtimeTypeCheckInfo);
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo =
+ appView.enableWholeProgramOptimizations()
+ ? ImmediateProgramSubtypingInfo.createWithDeterministicOrder(
+ appView.withClassHierarchy())
+ : null;
+ List<Policy> policies =
+ PolicyScheduler.getPolicies(appView, immediateSubtypingInfo, runtimeTypeCheckInfo);
Collection<HorizontalMergeGroup> groups =
new HorizontalClassMergerPolicyExecutor()
.run(getInitialGroups(), policies, executorService, timing);
@@ -127,11 +133,6 @@
// Ensure that all allocations of classes that end up needing a class id use a constructor on
// the class itself.
- ImmediateProgramSubtypingInfo immediateSubtypingInfo =
- appView.enableWholeProgramOptimizations()
- ? ImmediateProgramSubtypingInfo.createWithDeterministicOrder(
- appView.withClassHierarchy())
- : null;
new UndoConstructorInlining(appView, classMergerSharedData, immediateSubtypingInfo)
.runIfNecessary(groups, executorService, timing);
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyScheduler.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyScheduler.java
index 9e1a36e..cb7bda1 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyScheduler.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyScheduler.java
@@ -66,9 +66,12 @@
public class PolicyScheduler {
public static List<Policy> getPolicies(
- AppView<?> appView, RuntimeTypeCheckInfo runtimeTypeCheckInfo) {
+ AppView<?> appView,
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo,
+ RuntimeTypeCheckInfo runtimeTypeCheckInfo) {
if (appView.hasClassHierarchy()) {
- return getPoliciesForR8(appView.withClassHierarchy(), runtimeTypeCheckInfo);
+ return getPoliciesForR8(
+ appView.withClassHierarchy(), immediateSubtypingInfo, runtimeTypeCheckInfo);
} else {
return getPoliciesForD8(appView.withoutClassHierarchy());
}
@@ -87,11 +90,12 @@
private static List<Policy> getPoliciesForR8(
AppView<? extends AppInfoWithClassHierarchy> appView,
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo,
RuntimeTypeCheckInfo runtimeTypeCheckInfo) {
List<Policy> policies =
ImmutableList.<Policy>builder()
.addAll(getSingleClassPolicies(appView, runtimeTypeCheckInfo))
- .addAll(getMultiClassPolicies(appView, runtimeTypeCheckInfo))
+ .addAll(getMultiClassPolicies(appView, immediateSubtypingInfo, runtimeTypeCheckInfo))
.build();
policies = appView.options().testing.horizontalClassMergingPolicyRewriter.apply(policies);
assert verifyPolicyOrderingConstraints(policies);
@@ -195,6 +199,7 @@
private static List<Policy> getMultiClassPolicies(
AppView<? extends AppInfoWithClassHierarchy> appView,
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo,
RuntimeTypeCheckInfo runtimeTypeCheckInfo) {
ImmutableList.Builder<Policy> builder = ImmutableList.builder();
addRequiredMultiClassPolicies(appView, runtimeTypeCheckInfo, builder);
@@ -206,7 +211,7 @@
builder.add(new PreserveMethodCharacteristics(appView.withLiveness()));
}
builder.add(new MinimizeInstanceFieldCasts());
- addMultiClassPoliciesForInterfaceMerging(appView, builder);
+ addMultiClassPoliciesForInterfaceMerging(appView, immediateSubtypingInfo, builder);
return builder.add(new LimitClassGroups(appView), new FinalizeMergeGroup(appView)).build();
}
@@ -260,10 +265,11 @@
private static void addMultiClassPoliciesForInterfaceMerging(
AppView<? extends AppInfoWithClassHierarchy> appView,
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo,
ImmutableList.Builder<Policy> builder) {
builder.add(
new NoDefaultInterfaceMethodMerging(appView),
- new NoDefaultInterfaceMethodCollisions(appView),
+ new NoDefaultInterfaceMethodCollisions(appView, immediateSubtypingInfo),
new LimitInterfaceGroups(appView),
new OnlyDirectlyConnectedOrUnrelatedInterfaces(appView));
}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoDefaultInterfaceMethodCollisions.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoDefaultInterfaceMethodCollisions.java
index 801db59..f66d516 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoDefaultInterfaceMethodCollisions.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoDefaultInterfaceMethodCollisions.java
@@ -16,7 +16,7 @@
import com.android.tools.r8.graph.DexMethodSignature;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.graph.SubtypingInfo;
+import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
import com.android.tools.r8.horizontalclassmerging.HorizontalMergeGroup;
import com.android.tools.r8.horizontalclassmerging.MultiClassPolicyWithPreprocessing;
@@ -72,9 +72,13 @@
extends MultiClassPolicyWithPreprocessing<Map<DexType, InterfaceInfo>> {
private final AppView<? extends AppInfoWithClassHierarchy> appView;
+ private final ImmediateProgramSubtypingInfo immediateSubtypingInfo;
- public NoDefaultInterfaceMethodCollisions(AppView<? extends AppInfoWithClassHierarchy> appView) {
+ public NoDefaultInterfaceMethodCollisions(
+ AppView<? extends AppInfoWithClassHierarchy> appView,
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
this.appView = appView;
+ this.immediateSubtypingInfo = immediateSubtypingInfo;
}
@Override
@@ -144,8 +148,7 @@
@Override
public Map<DexType, InterfaceInfo> preprocess(
Collection<HorizontalMergeGroup> groups, ExecutorService executorService) {
- SubtypingInfo subtypingInfo = SubtypingInfo.create(appView);
- Collection<DexProgramClass> classesOfInterest = computeClassesOfInterest(subtypingInfo);
+ Collection<DexProgramClass> classesOfInterest = computeClassesOfInterest();
Map<DexType, DexMethodSignatureSet> inheritedClassMethodsPerClass =
computeInheritedClassMethodsPerProgramClass(classesOfInterest);
Map<DexType, Map<DexMethodSignature, Set<DexMethod>>> inheritedDefaultMethodsPerClass =
@@ -156,7 +159,7 @@
Map<DexType, Map<DexMethodSignature, Set<DexMethod>>>
defaultMethodsInheritedBySubclassesPerClass =
computeDefaultMethodsInheritedBySubclassesPerProgramClass(
- classesOfInterest, inheritedDefaultMethodsPerClass, groups, subtypingInfo);
+ classesOfInterest, inheritedDefaultMethodsPerClass, groups, immediateSubtypingInfo);
// Store the computed information for each interface that is subject to merging.
Map<DexType, InterfaceInfo> infos = new IdentityHashMap<>();
@@ -176,8 +179,7 @@
}
/** Returns the set of program classes that must be considered during preprocessing. */
- @SuppressWarnings("UnusedVariable")
- private Collection<DexProgramClass> computeClassesOfInterest(SubtypingInfo subtypingInfo) {
+ private Collection<DexProgramClass> computeClassesOfInterest() {
// TODO(b/173990042): Limit result to the set of classes that are in the same as one of
// the interfaces that is subject to merging.
return appView.appInfo().classes();
@@ -275,13 +277,13 @@
Collection<DexProgramClass> classesOfInterest,
Map<DexType, Map<DexMethodSignature, Set<DexMethod>>> inheritedDefaultMethodsPerClass,
Collection<HorizontalMergeGroup> groups,
- SubtypingInfo subtypingInfo) {
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
// Build a mapping from class types to their merge group.
- Map<DexType, Iterable<DexProgramClass>> classGroupsByType =
+ Map<DexProgramClass, Iterable<DexProgramClass>> classGroupsByClass =
MapUtils.newIdentityHashMap(
builder ->
Iterables.filter(groups, HorizontalMergeGroup::isClassGroup)
- .forEach(group -> group.forEach(clazz -> builder.put(clazz.getType(), group))));
+ .forEach(group -> group.forEach(clazz -> builder.put(clazz, group))));
// Copy the map from classes to their inherited default methods.
Map<DexType, Map<DexMethodSignature, Set<DexMethod>>>
@@ -298,15 +300,15 @@
// Therefore, it is important that we don't process any of A's supertypes until B has been
// processed, since that would lead to inadequate upwards propagation. To achieve this, we
// simulate that both A and B are subtypes of A's and B's supertypes.
- Function<DexType, Iterable<DexType>> immediateSubtypesProvider =
- type -> {
- Set<DexType> immediateSubtypesAfterClassMerging = Sets.newIdentityHashSet();
- for (DexType immediateSubtype : subtypingInfo.allImmediateSubtypes(type)) {
- Iterable<DexProgramClass> group = classGroupsByType.get(immediateSubtype);
+ Function<DexProgramClass, Iterable<DexProgramClass>> immediateSubtypesProvider =
+ clazz -> {
+ Set<DexProgramClass> immediateSubtypesAfterClassMerging = Sets.newIdentityHashSet();
+ for (DexProgramClass immediateSubclass : immediateSubtypingInfo.getSubclasses(clazz)) {
+ Iterable<DexProgramClass> group = classGroupsByClass.get(immediateSubclass);
if (group != null) {
- group.forEach(member -> immediateSubtypesAfterClassMerging.add(member.getType()));
+ group.forEach(immediateSubtypesAfterClassMerging::add);
} else {
- immediateSubtypesAfterClassMerging.add(immediateSubtype);
+ immediateSubtypesAfterClassMerging.add(immediateSubclass);
}
}
return immediateSubtypesAfterClassMerging;
@@ -321,7 +323,7 @@
defaultMethodsInheritedBySubclassesPerClass.getOrDefault(
clazz.getType(), emptyMap());
Iterable<DexProgramClass> group =
- classGroupsByType.getOrDefault(clazz.getType(), IterableUtils.singleton(clazz));
+ classGroupsByClass.getOrDefault(clazz, IterableUtils.singleton(clazz));
for (DexProgramClass member : group) {
for (DexType supertype : member.allImmediateSupertypes()) {
Map<DexMethodSignature, Set<DexMethod>>
diff --git a/src/main/java/com/android/tools/r8/optimize/bridgehoisting/BridgeHoisting.java b/src/main/java/com/android/tools/r8/optimize/bridgehoisting/BridgeHoisting.java
index 8e8fd00..185b0af 100644
--- a/src/main/java/com/android/tools/r8/optimize/bridgehoisting/BridgeHoisting.java
+++ b/src/main/java/com/android/tools/r8/optimize/bridgehoisting/BridgeHoisting.java
@@ -3,7 +3,6 @@
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.optimize.bridgehoisting;
-import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.BottomUpClassHierarchyTraversal;
@@ -12,16 +11,16 @@
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexProgramClass;
-import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
import com.android.tools.r8.graph.MethodAccessInfoCollection;
import com.android.tools.r8.graph.MethodResolutionResult;
import com.android.tools.r8.graph.ProgramMethod;
-import com.android.tools.r8.graph.SubtypingInfo;
import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackSimple;
import com.android.tools.r8.ir.optimize.info.bridge.BridgeInfo;
import com.android.tools.r8.ir.optimize.info.bridge.VirtualBridgeInfo;
import com.android.tools.r8.lightir.LirCode;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.MethodSignatureEquivalence;
import com.android.tools.r8.utils.Timing;
import com.google.common.base.Equivalence;
@@ -35,7 +34,6 @@
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
-import java.util.TreeSet;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
@@ -80,10 +78,11 @@
public void run(ExecutorService executorService, Timing timing) throws ExecutionException {
timing.begin("Bridge hoisting");
- SubtypingInfo subtypingInfo = appView.appInfo().computeSubtypingInfo();
- BottomUpClassHierarchyTraversal.forProgramClasses(appView, subtypingInfo)
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo =
+ ImmediateProgramSubtypingInfo.create(appView);
+ BottomUpClassHierarchyTraversal.forProgramClasses(appView, immediateSubtypingInfo)
.excludeInterfaces()
- .visit(appView.appInfo().classes(), clazz -> processClass(clazz, subtypingInfo));
+ .visit(appView.appInfo().classes(), clazz -> processClass(clazz, immediateSubtypingInfo));
if (!result.isEmpty()) {
BridgeHoistingLens lens = result.buildLens();
appView.rewriteWithLens(lens, executorService, timing);
@@ -113,22 +112,23 @@
timing.end();
}
- private void processClass(DexProgramClass clazz, SubtypingInfo subtypingInfo) {
- Set<DexType> subtypes = subtypingInfo.allImmediateSubtypes(clazz.type);
- Set<DexProgramClass> subclasses = new TreeSet<>(Comparator.comparing(DexClass::getType));
- for (DexType subtype : subtypes) {
- DexProgramClass subclass = asProgramClassOrNull(appView.definitionFor(subtype));
- if (subclass == null || !appView.testing().isEligibleForBridgeHoisting.test(subclass)) {
- continue;
+ private void processClass(
+ DexProgramClass clazz, ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
+ List<DexProgramClass> subclasses =
+ ListUtils.sort(
+ immediateSubtypingInfo.getSubclasses(clazz), Comparator.comparing(DexClass::getType));
+ List<DexProgramClass> eligibleSubclasses = new ArrayList<>(subclasses.size());
+ for (DexProgramClass subclass : subclasses) {
+ if (appView.testing().isEligibleForBridgeHoisting.test(subclass)) {
+ eligibleSubclasses.add(subclass);
}
- subclasses.add(subclass);
}
- for (Wrapper<DexMethod> candidate : getCandidatesForHoisting(subclasses)) {
- hoistBridgeIfPossible(candidate.get(), clazz, subclasses);
+ for (Wrapper<DexMethod> candidate : getCandidatesForHoisting(eligibleSubclasses)) {
+ hoistBridgeIfPossible(candidate.get(), clazz, eligibleSubclasses);
}
}
- private Set<Wrapper<DexMethod>> getCandidatesForHoisting(Set<DexProgramClass> subclasses) {
+ private Set<Wrapper<DexMethod>> getCandidatesForHoisting(List<DexProgramClass> subclasses) {
Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get();
Set<Wrapper<DexMethod>> candidates = new HashSet<>();
for (DexProgramClass subclass : subclasses) {
@@ -143,7 +143,7 @@
}
private void hoistBridgeIfPossible(
- DexMethod method, DexProgramClass clazz, Set<DexProgramClass> subclasses) {
+ DexMethod method, DexProgramClass clazz, List<DexProgramClass> subclasses) {
// If the method is defined on the parent class, we cannot hoist the bridge.
// TODO(b/153147967): If the declared method is abstract, we could replace it by the bridge.
// Add a test.
