Version 1.5.33
Cherry-pick: Introduce heuristic for spurious call graph edges
CL: https://r8-review.googlesource.com/c/r8/+/38708
Add logging for the max depth in the call graph
CL: https://r8-review.googlesource.com/c/r8/+/38680
Cherry-pick: Introduce a max depth threshold for the cycle eliminator
CL: https://r8-review.googlesource.com/c/r8/+/38702
Bug: 133248798
Change-Id: I5eebf5a9ebb4a8e028e90d34fcbf8f6f737f72c6
diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 2a81346..d9a92af 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
// This field is accessed from release scripts using simple pattern matching.
// Therefore, changing this field could break our release scripts.
- public static final String LABEL = "1.5.32";
+ public static final String LABEL = "1.5.33";
private Version() {
}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CallGraph.java b/src/main/java/com/android/tools/r8/ir/conversion/CallGraph.java
index d4ed94b..ca9dae4 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CallGraph.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CallGraph.java
@@ -48,7 +48,11 @@
}
public void addCallerConcurrently(Node caller) {
- if (caller != this) {
+ addCallerConcurrently(caller, false);
+ }
+
+ public void addCallerConcurrently(Node caller, boolean likelySpuriousCallEdge) {
+ if (caller != this && !likelySpuriousCallEdge) {
synchronized (callers) {
callers.add(caller);
numberOfCallSites++;
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CallGraphBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/CallGraphBuilder.java
index 7606901..ad94ea4 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CallGraphBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CallGraphBuilder.java
@@ -115,8 +115,8 @@
private void addClassInitializerTarget(DexClass clazz) {
assert clazz != null;
- if (clazz.hasClassInitializer() && clazz.isProgramClass()) {
- addTarget(clazz.getClassInitializer());
+ if (clazz.isProgramClass() && clazz.hasClassInitializer()) {
+ addTarget(clazz.getClassInitializer(), false);
}
}
@@ -128,10 +128,10 @@
}
}
- private void addTarget(DexEncodedMethod callee) {
+ private void addTarget(DexEncodedMethod callee, boolean likelySpuriousCallEdge) {
if (!callee.accessFlags.isAbstract()) {
assert callee.isProgramMethod(appView);
- getOrCreateNode(callee).addCallerConcurrently(caller);
+ getOrCreateNode(callee).addCallerConcurrently(caller, likelySpuriousCallEdge);
}
}
@@ -158,7 +158,7 @@
if (type == Type.STATIC) {
addClassInitializerTarget(clazz);
}
- addTarget(singleTarget);
+ addTarget(singleTarget, false);
}
}
}
@@ -187,9 +187,11 @@
? appView.appInfo().lookupInterfaceTargets(method)
: appView.appInfo().lookupVirtualTargets(method));
if (possibleTargets != null) {
+ boolean likelySpuriousCallEdge =
+ possibleTargets.size() >= appView.options().callGraphLikelySpuriousCallEdgeThreshold;
for (DexEncodedMethod possibleTarget : possibleTargets) {
if (possibleTarget.isProgramMethod(appView)) {
- addTarget(possibleTarget);
+ addTarget(possibleTarget, likelySpuriousCallEdge);
}
}
}
@@ -305,6 +307,8 @@
// Set of nodes that have been visited entirely.
private Set<Node> marked = Sets.newIdentityHashSet();
+ private int currentDepth = 0;
+ private int maxDepth = 0;
private int numberOfCycles = 0;
public CycleEliminator(Collection<Node> nodes, InternalOptions options) {
@@ -320,21 +324,34 @@
public int breakCycles() {
// Break cycles in this call graph by removing edges causing cycles.
for (Node node : nodes) {
+ assert currentDepth == 0;
traverse(node);
}
int result = numberOfCycles;
+ if (Log.ENABLED) {
+ Log.info(getClass(), "# call graph cycles broken: %s", numberOfCycles);
+ Log.info(getClass(), "# max call graph depth: %s", maxDepth);
+ }
reset();
return result;
}
private void reset() {
+ assert currentDepth == 0;
assert stack.isEmpty();
assert stackSet.isEmpty();
marked.clear();
+ maxDepth = 0;
numberOfCycles = 0;
}
private void traverse(Node node) {
+ if (Log.ENABLED) {
+ if (currentDepth > maxDepth) {
+ maxDepth = currentDepth;
+ }
+ }
+
if (marked.contains(node)) {
// Already visited all nodes that can be reached from this node.
return;
@@ -353,7 +370,16 @@
Iterator<Node> calleeIterator = callees.iterator();
while (calleeIterator.hasNext()) {
Node callee = calleeIterator.next();
- if (stackSet.contains(callee)) {
+
+ // If we've exceeded the depth threshold, then treat it as if we have found a cycle. This
+ // ensures that we won't run into stack overflows when the call graph contains large call
+ // chains. This should have a negligible impact on code size as long as the threshold is
+ // large enough.
+ boolean foundCycle = stackSet.contains(callee);
+ boolean thresholdExceeded =
+ currentDepth >= options.callGraphCycleEliminatorMaxDepthThreshold
+ && edgeRemovalIsSafe(node, callee);
+ if (foundCycle || thresholdExceeded) {
// Found a cycle that needs to be eliminated.
numberOfCycles++;
@@ -377,6 +403,8 @@
callee.method.toSourceString());
}
} else {
+ assert foundCycle;
+
// The cycle has a method that is marked as force inline.
LinkedList<Node> cycle = extractCycle(callee);
@@ -411,7 +439,9 @@
recoverStack(cycle);
}
} else {
+ currentDepth++;
traverse(callee);
+ currentDepth--;
}
}
pop(node);
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index 7fafc4b..8ff922b 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -152,6 +152,14 @@
public boolean enableServiceLoaderRewriting = true;
// TODO(b/120138731): Enable this when it is worthwhile, e.g., combined with Class#forName.
public boolean enableNameReflectionOptimization = false;
+
+ // This defines the max depth threshold for the cycle eliminator. If the length of a call chain
+ // exceeds the threshold, we treat it as if we have found a cycle. This ensures that we won't run
+ // into stack overflows when the call graph contains large call chains. This should have a
+ // negligible impact on code size as long as the threshold is large enough.
+ public int callGraphCycleEliminatorMaxDepthThreshold = 256;
+ public int callGraphLikelySpuriousCallEdgeThreshold = 50;
+
public int classInliningInstructionLimit = 50;
// This defines the limit of instructions in the inlinee
public int inliningInstructionLimit = 3;