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;