commit 658169482f01b2dadf2e6724a06128bc45904442
author Christoffer Quist Adamsen <christofferqa@google.com> Wed May 22 14:51:46 2019 +0200
committer Christoffer Quist Adamsen <christofferqa@google.com> Wed May 22 14:51:46 2019 +0200
tree 38b05e19483af9e44f9b1a3992348d1868d6149f
parent cfdf851c2ab7930f5ecdb5606944d679ba4a82b1

Introduce a max depth threshold for the cycle eliminator

Bug: 133248798
Change-Id: I9fabc2488ce5beb3f84c181aa3848787f69a64cf

src/main/java/com/android/tools/r8/ir/conversion/CallGraphBuilder.java

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 5a928f9..c014d1b 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
@@ -312,6 +312,7 @@
     // 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;
 
@@ -328,7 +329,8 @@
     public int breakCycles() {
       // Break cycles in this call graph by removing edges causing cycles.
       for (Node node : nodes) {
-        traverse(node, 0);
+        assert currentDepth == 0;
+        traverse(node);
       }
       int result = numberOfCycles;
       if (Log.ENABLED) {
@@ -340,6 +342,7 @@
     }
 
     private void reset() {
+      assert currentDepth == 0;
       assert stack.isEmpty();
       assert stackSet.isEmpty();
       marked.clear();
@@ -347,10 +350,10 @@
       numberOfCycles = 0;
     }
 
-    private void traverse(Node node, int depth) {
+    private void traverse(Node node) {
       if (Log.ENABLED) {
-        if (depth > maxDepth) {
-          maxDepth = depth;
+        if (currentDepth > maxDepth) {
+          maxDepth = currentDepth;
         }
       }
 
@@ -372,7 +375,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++;
 
@@ -396,6 +408,8 @@
                   callee.method.toSourceString());
             }
           } else {
+            assert foundCycle;
+
             // The cycle has a method that is marked as force inline.
             LinkedList<Node> cycle = extractCycle(callee);
 
@@ -430,7 +444,9 @@
             recoverStack(cycle);
           }
         } else {
-          traverse(callee, depth + 1);
+          currentDepth++;
+          traverse(callee);
+          currentDepth--;
         }
       }
       pop(node);

src/main/java/com/android/tools/r8/utils/InternalOptions.java

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 47a8b7f..cd82b98 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -164,6 +164,13 @@
   // TODO(b/120138731): Enable this when it is worthwhile, e.g., combined with Class#forName.
   public boolean enableNameReflectionOptimization = false;
   public boolean enableTreeShakingOfLibraryMethodOverrides = 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;