Introduce a max depth threshold for the cycle eliminator
Bug: 133248798
Change-Id: I9fabc2488ce5beb3f84c181aa3848787f69a64cf
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..5fb2aee 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
@@ -305,6 +305,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,6 +322,7 @@
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;
@@ -328,6 +331,7 @@
}
private void reset() {
+ assert currentDepth == 0;
assert stack.isEmpty();
assert stackSet.isEmpty();
marked.clear();
@@ -335,6 +339,12 @@
}
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 +363,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 +396,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 +432,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..ecbda8a 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,13 @@
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 classInliningInstructionLimit = 50;
// This defines the limit of instructions in the inlinee
public int inliningInstructionLimit = 3;
