Account for default interface methods in subclasses in bridge hoisting
When hoisting a virtual bridge m() from a class B to its superclass A, the virtual method is implicitly added to all subclasses of A. If there exists a subclass C of A, which implements an interface I that declares a default interface method m(), then bridge hoisting would change semantics since virtual class methods take precedence over default interface methods in resolution.
Bug: b/369040938
Change-Id: I5b425f2cde9c48e0a298af02f67eb83951473006
diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java
index e8bc0b7..c9a5078 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -569,6 +569,10 @@
return methodCollection.getMethod(method);
}
+ public DexEncodedMethod lookupMethod(DexMethodSignature method) {
+ return lookupMethod(method.getProto(), method.getName());
+ }
+
public DexEncodedMethod lookupMethod(DexProto methodProto, DexString methodName) {
return methodCollection.getMethod(methodProto, methodName);
}
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 617a1ed..a7203b9 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 com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.BottomUpClassHierarchyTraversal;
import com.android.tools.r8.graph.DexClass;
@@ -11,6 +10,7 @@
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.MethodResolutionResult;
import com.android.tools.r8.graph.ProgramMethod;
@@ -19,8 +19,11 @@
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.DepthFirstSearchWorkListBase.DepthFirstSearchWorkList;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.MethodSignatureEquivalence;
+import com.android.tools.r8.utils.TraversalContinuation;
+import com.android.tools.r8.utils.collections.DexMethodSignatureSet;
import com.android.tools.r8.utils.timing.Timing;
import com.google.common.base.Equivalence;
import com.google.common.base.Equivalence.Wrapper;
@@ -29,12 +32,14 @@
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
+import java.util.IdentityHashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
+import java.util.function.Function;
/**
* An optimization pass that hoists bridges upwards with the purpose of sharing redundant bridge
@@ -66,6 +71,16 @@
private final AppView<AppInfoWithLiveness> appView;
+ // Cache that for a given non-interface class stores the default interface methods present on the
+ // class and all of its subclasses.
+ private final Map<DexProgramClass, DexMethodSignatureSet>
+ defaultInterfaceMethodsInClassAndSubclassesCache = new IdentityHashMap<>();
+
+ // Cache that for a given interface stores the default methods on that interface and all of its
+ // transitive superinterfaces.
+ private final Map<DexClass, DexMethodSignatureSet> inheritedDefaultInterfaceMethodsCache =
+ new IdentityHashMap<>();
+
// Structure that keeps track of the changes for construction of the Proguard map and
// AppInfoWithLiveness maintenance.
private final BridgeHoistingResult result;
@@ -103,7 +118,7 @@
}
}
for (ProgramMethod candidate : getCandidatesForHoisting(eligibleSubclasses)) {
- hoistBridgeIfPossible(candidate, clazz, eligibleSubclasses);
+ hoistBridgeIfPossible(candidate, clazz, eligibleSubclasses, immediateSubtypingInfo);
}
}
@@ -125,7 +140,10 @@
}
private void hoistBridgeIfPossible(
- ProgramMethod method, DexProgramClass clazz, List<DexProgramClass> subclasses) {
+ ProgramMethod method,
+ DexProgramClass clazz,
+ List<DexProgramClass> subclasses,
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
// 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.
@@ -160,23 +178,38 @@
.appInfo()
.resolveMethodOnClassLegacy(subclass, methodReference)
.getSingleTarget();
- if (resolutionTarget == null || resolutionTarget.isAbstract()) {
- // The fact that this class does not declare the bridge (or the bridge is abstract) should
- // not prevent us from hoisting the bridge.
- //
- // Strictly speaking, there could be an invoke instruction that targets the bridge on this
- // subclass and fails with an AbstractMethodError or a NoSuchMethodError in the input
- // program. After hoisting the bridge to the superclass such an instruction would no
- // longer fail with an error in the generated program.
- //
- // If this ever turns out be an issue, it would be possible to track if there is an invoke
- // instruction targeting the bridge on this subclass that fails in the Enqueuer, but this
- // should never be the case in practice.
- continue;
+ if (resolutionTarget != null && !resolutionTarget.isAbstract()) {
+ // Hoisting would change the program behavior.
+ return;
}
- // Hoisting would change the program behavior.
- return;
+ if (appView.options().canUseDefaultAndStaticInterfaceMethods()) {
+ DexMethodSignatureSet defaultInterfaceMethodsBelowSubclass =
+ getOrComputeDefaultInterfaceMethodsOnClassAndSubclasses(
+ subclass, immediateSubtypingInfo);
+ if (defaultInterfaceMethodsBelowSubclass.contains(method)) {
+ // Hoisting would change the program behavior. Virtual methods on classes takes
+ // precedence over default interface methods. By hoisting the current bridge method to
+ // the superclass, we may change virtual calls that would previously have dispatched to
+ // a default interface method into calling the hoisted bridge method.
+ //
+ // See also b/369040938.
+ return;
+ }
+ }
+
+ // The fact that this class does not declare the bridge (or the bridge is abstract) should
+ // not prevent us from hoisting the bridge.
+ //
+ // Strictly speaking, there could be an invoke instruction that targets the bridge on this
+ // subclass and fails with an AbstractMethodError or a NoSuchMethodError in the input
+ // program. After hoisting the bridge to the superclass such an instruction would no
+ // longer fail with an error in the generated program.
+ //
+ // If this ever turns out be an issue, it would be possible to track if there is an invoke
+ // instruction targeting the bridge on this subclass that fails in the Enqueuer, but this
+ // should never be the case in practice.
+ continue;
}
BridgeInfo currentBridgeInfo = definition.getOptimizationInfo().getBridgeInfo();
@@ -320,4 +353,104 @@
return item;
});
}
+
+ private DexMethodSignatureSet getOrComputeDefaultInterfaceMethodsOnClassAndSubclasses(
+ DexProgramClass clazz, ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
+ if (!defaultInterfaceMethodsInClassAndSubclassesCache.containsKey(clazz)) {
+ new DefaultInterfaceMethodsTraversal(immediateSubtypingInfo).run(List.of(clazz));
+ }
+ DexMethodSignatureSet cachedResult =
+ defaultInterfaceMethodsInClassAndSubclassesCache.get(clazz);
+ assert cachedResult != null;
+ return cachedResult;
+ }
+
+ // A depth-first traversal over the class hierarchy that will collect and cache the default
+ // interface method present on a given class and its subclasses.
+ private class DefaultInterfaceMethodsTraversal
+ extends DepthFirstSearchWorkList<DexProgramClass, Void, Void> {
+
+ private final ImmediateProgramSubtypingInfo immediateSubtypingInfo;
+
+ DefaultInterfaceMethodsTraversal(ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
+ this.immediateSubtypingInfo = immediateSubtypingInfo;
+ }
+
+ @Override
+ protected TraversalContinuation<Void, Void> process(
+ DFSNode<DexProgramClass> node,
+ Function<DexProgramClass, DFSNode<DexProgramClass>> childNodeConsumer) {
+ // Enqueue unseen subclasses for processing.
+ DexProgramClass currentClass = node.getNode();
+ assert !currentClass.isInterface();
+ assert !defaultInterfaceMethodsInClassAndSubclassesCache.containsKey(currentClass);
+ for (DexProgramClass subclass : immediateSubtypingInfo.getSubclasses(currentClass)) {
+ if (!defaultInterfaceMethodsInClassAndSubclassesCache.containsKey(subclass)) {
+ DFSNode<DexProgramClass> unusedChildNode = childNodeConsumer.apply(subclass);
+ }
+ }
+ return TraversalContinuation.doContinue();
+ }
+
+ @Override
+ public TraversalContinuation<Void, Void> joiner(DFSNode<DexProgramClass> node) {
+ // All subclasses of the current class have now been processed.
+ DexProgramClass currentClass = node.getNode();
+ assert !currentClass.isInterface();
+ assert !defaultInterfaceMethodsInClassAndSubclassesCache.containsKey(currentClass);
+ // Compute the default interface methods that this class inherits from its implemented
+ // interfaces.
+ DexMethodSignatureSet defaultInterfaceMethods = DexMethodSignatureSet.create();
+ for (DexType implementedType : currentClass.getInterfaces()) {
+ DexClass implementedInterface = appView.definitionFor(implementedType);
+ if (implementedInterface != null) {
+ defaultInterfaceMethods.addAll(
+ getOrComputeInheritedDefaultInterfaceMethodsForInterface(implementedInterface));
+ }
+ }
+ // Include the default interface methods that are present on the class' subclasses.
+ for (DexProgramClass subclass : immediateSubtypingInfo.getSubclasses(currentClass)) {
+ DexMethodSignatureSet defaultInterfaceMethodsInSubclass =
+ defaultInterfaceMethodsInClassAndSubclassesCache.get(subclass);
+ assert defaultInterfaceMethodsInSubclass != null;
+ defaultInterfaceMethods.addAll(defaultInterfaceMethodsInSubclass);
+ }
+ // Remove all virtual methods declared by the class itself, since we are only interested in
+ // the occurrence of default interface method that are not overridden by a non-default
+ // interface method.
+ defaultInterfaceMethods.removeIf(m -> currentClass.lookupMethod(m) != null);
+ // Cache the computed result.
+ defaultInterfaceMethodsInClassAndSubclassesCache.put(currentClass, defaultInterfaceMethods);
+ return TraversalContinuation.doContinue();
+ }
+
+ // For a given interface, returns the default interface methods present on that interface and
+ // all transitive superinterfaces.
+ private DexMethodSignatureSet getOrComputeInheritedDefaultInterfaceMethodsForInterface(
+ DexClass itf) {
+ assert itf.isInterface();
+ // Check if we have already computed the default interface methods in the current interface
+ // and its superinterfaces.
+ DexMethodSignatureSet cachedResult = inheritedDefaultInterfaceMethodsCache.get(itf);
+ if (cachedResult != null) {
+ return cachedResult;
+ }
+ DexMethodSignatureSet inheritedDefaultInterfaceMethods = DexMethodSignatureSet.create();
+ // First add the default interface methods that are present on the interface directly.
+ for (DexEncodedMethod defaultInterfaceMethod :
+ itf.virtualMethods(DexEncodedMethod::hasCode)) {
+ inheritedDefaultInterfaceMethods.add(defaultInterfaceMethod);
+ }
+ // Then add the default interface methods that are present on the superinterfaces.
+ for (DexType implementedType : itf.getInterfaces()) {
+ DexClass implementedInterface = appView.definitionFor(implementedType);
+ if (implementedInterface != null) {
+ inheritedDefaultInterfaceMethods.addAll(
+ getOrComputeInheritedDefaultInterfaceMethodsForInterface(implementedInterface));
+ }
+ }
+ inheritedDefaultInterfaceMethodsCache.put(itf, inheritedDefaultInterfaceMethods);
+ return inheritedDefaultInterfaceMethods;
+ }
+ }
}
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/HorizontalClassMergingVirtualMethodMergingWithLibraryTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/HorizontalClassMergingVirtualMethodMergingWithLibraryTest.java
index e44992d..7861ac8 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/HorizontalClassMergingVirtualMethodMergingWithLibraryTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/HorizontalClassMergingVirtualMethodMergingWithLibraryTest.java
@@ -50,11 +50,7 @@
.enableNoVerticalClassMergingAnnotations()
.compile()
.run(parameters.getRuntime(), Main.class)
- .applyIf(
- parameters.canUseDefaultAndStaticInterfaceMethods(),
- // TODO(b/369040938): Disallow bridge hoisting of B.m().
- rr -> rr.assertSuccessWithOutputLines("A.bridgeTarget()", "A.bridgeTarget()"),
- rr -> rr.assertSuccessWithOutputLines("A.bridgeTarget()", "I.m()"));
+ .assertSuccessWithOutputLines("A.bridgeTarget()", "I.m()");
}
static class Main {
