Split out reachable library methods and report as library edges.
Bug: 120959039
Change-Id: I917ae6aed746ab3cfa7b829205e3372485aebc46
diff --git a/src/main/java/com/android/tools/r8/experimental/graphinfo/GraphEdgeInfo.java b/src/main/java/com/android/tools/r8/experimental/graphinfo/GraphEdgeInfo.java
index 214d103..e028a0b 100644
--- a/src/main/java/com/android/tools/r8/experimental/graphinfo/GraphEdgeInfo.java
+++ b/src/main/java/com/android/tools/r8/experimental/graphinfo/GraphEdgeInfo.java
@@ -72,7 +72,8 @@
case ReferencedInAnnotation:
return "referenced in annotation";
case IsLibraryMethod:
- return "defined in library";
+ // TODO(b/120959039): It would be good to also surface the defining library type.
+ return "defined in library method overridden by";
case MethodHandleUseFrom:
return "referenced by method handle";
default:
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 35cd3d1..bbdd93f 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -68,6 +68,7 @@
import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
import com.android.tools.r8.shaking.ScopedDexMethodSet.AddMethodIfMoreVisibleResult;
import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.StringDiagnostic;
import com.android.tools.r8.utils.Timing;
import com.google.common.collect.ImmutableList;
@@ -177,6 +178,11 @@
*/
private final Map<DexType, SetWithReason<DexEncodedMethod>> reachableVirtualMethods = Maps
.newIdentityHashMap();
+
+ // TODO(b/139464956): Lazily compute library dependencies.
+ private final Map<DexType, Map<DexEncodedMethod, Set<DexType>>>
+ reachableVirtualMethodsFromLibraries = Maps.newIdentityHashMap();
+
/**
* Tracks the dependency between a method and the super-method it calls, if any. Used to make
* super methods become live when they become reachable from a live sub-method.
@@ -848,12 +854,7 @@
// runtime. Illegal dispatch situations and the corresponding exceptions are already handled
// by the reachability logic.
ScopedDexMethodSet seen = new ScopedDexMethodSet();
- SetWithReason<DexEncodedMethod> reachableMethods =
- reachableVirtualMethods.get(instantiatedType);
- if (reachableMethods != null) {
- transitionNonAbstractMethodsToLiveAndShadow(
- reachableMethods.getItems(), instantiatedType, seen);
- }
+ transitionReachableVirtualMethods(instantiatedType, seen);
Collections.addAll(allInterfaces, clazz.interfaces.values);
// The set now contains all virtual methods on the type and its supertype that are reachable.
@@ -895,6 +896,30 @@
}
}
+ private void transitionReachableVirtualMethods(DexType type, ScopedDexMethodSet seen) {
+ SetWithReason<DexEncodedMethod> reachableMethods = reachableVirtualMethods.get(type);
+ if (reachableMethods != null) {
+ transitionNonAbstractMethodsToLiveAndShadow(type, reachableMethods, seen);
+ }
+ Map<DexEncodedMethod, Set<DexType>> libraryMethods =
+ reachableVirtualMethodsFromLibraries.get(type);
+ if (libraryMethods == null) {
+ return;
+ }
+ for (Entry<DexEncodedMethod, Set<DexType>> entry : libraryMethods.entrySet()) {
+ DexEncodedMethod encodedMethod = entry.getKey();
+ if (seen.addMethod(encodedMethod)) {
+ // Abstract methods do shadow implementations but they cannot be live, as they have no
+ // code.
+ // TODO(b/120959039): The edge registration needs to be per interface.
+ KeepReason reason = KeepReason.isLibraryMethod(type, entry.getValue().iterator().next());
+ if (!encodedMethod.accessFlags.isAbstract()) {
+ markVirtualMethodAsLive(encodedMethod, reason);
+ }
+ }
+ }
+ }
+
private DexMethod getInvokeSuperTarget(DexMethod method, DexEncodedMethod currentMethod) {
DexClass methodHolderClass = appView.definitionFor(method.holder);
if (methodHolderClass != null && methodHolderClass.isInterface()) {
@@ -1265,11 +1290,7 @@
// We only have to look at virtual methods here, as only those can actually be executed at
// runtime. Illegal dispatch situations and the corresponding exceptions are already handled
// by the reachability logic.
- SetWithReason<DexEncodedMethod> reachableMethods = reachableVirtualMethods.get(type);
- if (reachableMethods != null) {
- transitionNonAbstractMethodsToLiveAndShadow(reachableMethods.getItems(), instantiatedType,
- seen);
- }
+ transitionReachableVirtualMethods(type, seen);
Collections.addAll(interfaces, clazz.interfaces.values);
type = clazz.superType;
} while (type != null && !instantiatedTypes.contains(type));
@@ -1300,25 +1321,21 @@
return;
}
assert clazz.accessFlags.isInterface();
- SetWithReason<DexEncodedMethod> reachableMethods = reachableVirtualMethods.get(iface);
- if (reachableMethods != null) {
- transitionNonAbstractMethodsToLiveAndShadow(
- reachableMethods.getItems(), instantiatedType, seen.newNestedScope());
- }
+ transitionReachableVirtualMethods(iface, seen.newNestedScope());
for (DexType subInterface : clazz.interfaces.values) {
transitionDefaultMethodsForInstantiatedClass(subInterface, instantiatedType, seen);
}
}
- private void transitionNonAbstractMethodsToLiveAndShadow(Iterable<DexEncodedMethod> reachable,
- DexType instantiatedType, ScopedDexMethodSet seen) {
- for (DexEncodedMethod encodedMethod : reachable) {
+ private void transitionNonAbstractMethodsToLiveAndShadow(
+ DexType type, SetWithReason<DexEncodedMethod> reachable, ScopedDexMethodSet seen) {
+ for (DexEncodedMethod encodedMethod : reachable.getItems()) {
if (seen.addMethod(encodedMethod)) {
// Abstract methods do shadow implementations but they cannot be live, as they have no
// code.
+ // TODO(b/120959039): The reasons need to be stored and then forwarded here!
if (!encodedMethod.accessFlags.isAbstract()) {
- markVirtualMethodAsLive(encodedMethod,
- KeepReason.reachableFromLiveType(instantiatedType));
+ markVirtualMethodAsLive(encodedMethod, KeepReason.reachableFromLiveType(type));
}
}
}
@@ -1564,7 +1581,7 @@
private void markVirtualMethodAsReachable(
DexMethod method, boolean interfaceInvoke, KeepReason reason) {
- markVirtualMethodAsReachable(method, interfaceInvoke, reason, (x, y) -> true, null);
+ markVirtualMethodAsReachable(method, interfaceInvoke, reason, (x, y) -> true, null, false);
}
private void markVirtualMethodAsReachable(
@@ -1572,7 +1589,8 @@
boolean interfaceInvoke,
KeepReason reason,
BiPredicate<DexProgramClass, DexEncodedMethod> possibleTargetsFilter,
- Consumer<DexEncodedMethod> possibleTargetsConsumer) {
+ Consumer<DexEncodedMethod> possibleTargetsConsumer,
+ boolean isLibraryEnqueueing) {
if (!virtualTargetsMarkedAsReachable.add(method)) {
return;
}
@@ -1625,12 +1643,23 @@
continue;
}
- // TODO(b/120959039): The reachable.add test might be hiding other paths to the method.
- SetWithReason<DexEncodedMethod> reachable =
- reachableVirtualMethods.computeIfAbsent(
- possibleTarget.holder, ignore -> newSetWithoutReasonReporter());
- if (!reachable.add(encodedPossibleTarget, reason)) {
- continue;
+ if (isLibraryEnqueueing) {
+ Map<DexEncodedMethod, Set<DexType>> entry =
+ reachableVirtualMethodsFromLibraries.computeIfAbsent(
+ possibleTarget.holder, ignore -> Maps.newIdentityHashMap());
+ Set<DexType> libraryTypes = entry.get(encodedPossibleTarget);
+ if (libraryTypes != null) {
+ libraryTypes.add(method.holder);
+ continue;
+ }
+ entry.put(encodedPossibleTarget, SetUtils.newIdentityHashSet(method.holder, 2));
+ } else {
+ SetWithReason<DexEncodedMethod> reachable =
+ reachableVirtualMethods.computeIfAbsent(
+ possibleTarget.holder, ignore -> newSetWithoutReasonReporter());
+ if (!reachable.add(encodedPossibleTarget, reason)) {
+ continue;
+ }
}
// Abstract methods cannot be live.
@@ -2036,14 +2065,17 @@
Log.verbose(
getClass(), "Marking all methods of library class `%s` as reachable.", clazz.type);
}
+ // TODO(b/139464956, b/124480748): Remove this 'reason'. Lazy load libraries and no reporting.
+ KeepReason reason = KeepReason.isLibraryMethod(clazz.type, clazz.type);
for (DexEncodedMethod encodedMethod : clazz.virtualMethods()) {
- markMethodAsTargeted(encodedMethod, KeepReason.isLibraryMethod());
+ markMethodAsTargeted(encodedMethod, reason);
markVirtualMethodAsReachable(
encodedMethod.method,
clazz.isInterface(),
- KeepReason.isLibraryMethod(),
+ reason,
this::shouldMarkLibraryMethodOverrideAsReachable,
- DexEncodedMethod::setLibraryMethodOverride);
+ DexEncodedMethod::setLibraryMethodOverride,
+ true);
}
}
@@ -2715,10 +2747,15 @@
registerEdge(getAnnotationGraphNode(annotation.annotation.type), reason);
}
+ private boolean isNonProgramClass(DexType type) {
+ DexClass clazz = appView.definitionFor(type);
+ return clazz == null || clazz.isNotProgramClass();
+ }
+
private void registerMethod(DexEncodedMethod method, KeepReason reason) {
- if (reason.edgeKind() == EdgeKind.IsLibraryMethod) {
+ if (reason.edgeKind() == EdgeKind.IsLibraryMethod && isNonProgramClass(method.method.holder)) {
// Don't report edges to actual library methods.
- // TODO(b/120959039): Make sure we do have edges to methods overwriting library methods!
+ // TODO(b/120959039): This should be dead code once no library classes are ever enqueued.
return;
}
assert getSourceNode(reason) != null;
diff --git a/src/main/java/com/android/tools/r8/shaking/KeepReason.java b/src/main/java/com/android/tools/r8/shaking/KeepReason.java
index 673326c..3dfec87 100644
--- a/src/main/java/com/android/tools/r8/shaking/KeepReason.java
+++ b/src/main/java/com/android/tools/r8/shaking/KeepReason.java
@@ -67,8 +67,8 @@
return new InvokedFromLambdaCreatedIn(method);
}
- public static KeepReason isLibraryMethod() {
- return IsLibraryMethod.getInstance();
+ public static KeepReason isLibraryMethod(DexType implementer, DexType libraryType) {
+ return new IsLibraryMethod(implementer, libraryType);
}
public static KeepReason fieldReferencedIn(DexEncodedMethod method) {
@@ -350,14 +350,14 @@
}
}
- private static class IsLibraryMethod extends KeepReason {
+ public static class IsLibraryMethod extends KeepReason {
- private static final IsLibraryMethod instance = new IsLibraryMethod();
+ private final DexType implementer;
+ private final DexType libraryType;
- private IsLibraryMethod() {}
-
- public static IsLibraryMethod getInstance() {
- return instance;
+ private IsLibraryMethod(DexType implementer, DexType libraryType) {
+ this.implementer = implementer;
+ this.libraryType = libraryType;
}
@Override
@@ -367,7 +367,7 @@
@Override
public GraphNode getSourceNode(Enqueuer enqueuer) {
- return null;
+ return enqueuer.getClassGraphNode(implementer);
}
}
diff --git a/src/main/java/com/android/tools/r8/utils/SetUtils.java b/src/main/java/com/android/tools/r8/utils/SetUtils.java
index 185cfbd..190b744 100644
--- a/src/main/java/com/android/tools/r8/utils/SetUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/SetUtils.java
@@ -5,6 +5,8 @@
package com.android.tools.r8.utils;
import com.google.common.collect.Sets;
+import java.util.Collections;
+import java.util.IdentityHashMap;
import java.util.Set;
public class SetUtils {
@@ -20,4 +22,14 @@
c.forEach(result::add);
return result;
}
+
+ public static <T> Set<T> newIdentityHashSet(int capacity) {
+ return Collections.newSetFromMap(new IdentityHashMap<>(capacity));
+ }
+
+ public static <T> Set<T> newIdentityHashSet(T element, int capacity) {
+ Set<T> result = newIdentityHashSet(capacity);
+ result.add(element);
+ return result;
+ }
}
diff --git a/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptByLibraryMethod.java b/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptByLibraryMethod.java
new file mode 100644
index 0000000..0bab978
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptByLibraryMethod.java
@@ -0,0 +1,94 @@
+// 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.shaking.keptgraph;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.utils.graphinspector.GraphInspector;
+import java.util.ArrayList;
+import java.util.Collection;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class KeptByLibraryMethod extends TestBase {
+
+ // Library
+
+ public abstract static class Drawable {
+ abstract void draw();
+ }
+
+ public static class Scene {
+ private Collection<Drawable> drawables = new ArrayList<>();
+
+ public void register(Drawable drawable) {
+ drawables.add(drawable);
+ }
+
+ public void drawScene() {
+ for (Drawable drawable : drawables) {
+ drawable.draw();
+ }
+ }
+ }
+
+ // Program
+
+ public static class MyShape extends Drawable {
+
+ @Override
+ void draw() {
+ System.out.println("MyShape was drawn!");
+ }
+ }
+
+ public static class Main {
+
+ public static void main(String[] args) {
+ Scene scene = new Scene();
+ scene.register(new MyShape());
+ scene.drawScene();
+ }
+ }
+
+ // Test runner
+
+ @Parameters(name = "{0}")
+ public static TestParametersCollection data() {
+ return getTestParameters().withCfRuntimes().build();
+ }
+
+ private final TestParameters parameters;
+
+ public KeptByLibraryMethod(TestParameters parameters) {
+ this.parameters = parameters;
+ }
+
+ @Test
+ public void test() throws Exception {
+ GraphInspector inspector =
+ testForR8(parameters.getBackend())
+ .enableGraphInspector()
+ .addKeepMainRule(Main.class)
+ .addLibraryClasses(Scene.class, Drawable.class)
+ .addLibraryFiles(TestBase.runtimeJar(parameters.getBackend()))
+ .addProgramClasses(Main.class, MyShape.class)
+ .compile()
+ // The use of classpath classes is unsupported for DEX runtimes currently.
+ .addRunClasspathClasses(Scene.class, Drawable.class)
+ .run(parameters.getRuntime(), Main.class)
+ .assertSuccessWithOutputLines("MyShape was drawn!")
+ .graphInspector();
+
+ inspector
+ .method(Reference.methodFromMethod(MyShape.class.getDeclaredMethod("draw")))
+ .assertPresent()
+ .assertKeptByLibraryMethod(inspector.clazz(Reference.classFromClass(MyShape.class)));
+ }
+}
diff --git a/src/test/java/com/android/tools/r8/utils/graphinspector/GraphInspector.java b/src/test/java/com/android/tools/r8/utils/graphinspector/GraphInspector.java
index 4729766..2ada844 100644
--- a/src/test/java/com/android/tools/r8/utils/graphinspector/GraphInspector.java
+++ b/src/test/java/com/android/tools/r8/utils/graphinspector/GraphInspector.java
@@ -46,6 +46,8 @@
public static final EdgeKindPredicate invokedFrom = new EdgeKindPredicate(EdgeKind.InvokedFrom);
public static final EdgeKindPredicate reflectedFrom =
new EdgeKindPredicate(EdgeKind.ReflectiveUseFrom);
+ public static final EdgeKindPredicate isLibraryMethod =
+ new EdgeKindPredicate(EdgeKind.IsLibraryMethod);
private final EdgeKind edgeKind;
@@ -131,6 +133,8 @@
public abstract boolean isKeptBy(QueryNode node);
+ public abstract boolean isKeptByLibraryMethod(QueryNode node);
+
public abstract boolean isSatisfiedBy(QueryNode node);
abstract String getNodeDescription();
@@ -226,6 +230,17 @@
return this;
}
+ public QueryNode assertKeptByLibraryMethod(QueryNode node) {
+ assertTrue(
+ "Invalid call to assertKeptBy with: " + node.getNodeDescription(), node.isPresent());
+ assertTrue(
+ errorMessage(
+ "kept by library method on " + node.getNodeDescription(),
+ "was not kept by a library method"),
+ isKeptByLibraryMethod(node));
+ return this;
+ }
+
public abstract String getKeptGraphString();
}
@@ -294,6 +309,12 @@
}
@Override
+ public boolean isKeptByLibraryMethod(QueryNode node) {
+ fail("Invalid call to isKeptByLibrary on " + getNodeDescription());
+ throw new Unreachable();
+ }
+
+ @Override
public boolean isSatisfiedBy(QueryNode node) {
fail("Invalid call to isTriggeredBy on " + getNodeDescription());
throw new Unreachable();
@@ -389,6 +410,20 @@
}
@Override
+ public boolean isKeptByLibraryMethod(QueryNode node) {
+ assert graphNode instanceof MethodGraphNode;
+ if (!(node instanceof QueryNodeImpl)) {
+ return false;
+ }
+ QueryNodeImpl impl = (QueryNodeImpl) node;
+ return filterSources(
+ (source, infos) ->
+ impl.graphNode == source && EdgeKindPredicate.isLibraryMethod.test(infos))
+ .findFirst()
+ .isPresent();
+ }
+
+ @Override
public boolean isSatisfiedBy(QueryNode node) {
assertTrue(
"Invalid call to isTriggeredBy on non-keep rule node: " + graphNode,
