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 4d46084..d4ed94b 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
@@ -75,8 +75,12 @@
       }
     }
 
-    public Node[] getCalleesWithDeterministicOrder() {
-      return callees.toArray(Node.EMPTY_ARRAY);
+    public Set<Node> getCallersWithDeterministicOrder() {
+      return callers;
+    }
+
+    public Set<Node> getCalleesWithDeterministicOrder() {
+      return callees;
     }
 
     public int getNumberOfCallSites() {
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 699cd86..7606901 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
@@ -26,7 +26,6 @@
 import com.google.common.collect.Sets;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
-import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Deque;
@@ -345,20 +344,30 @@
 
       // The callees must be sorted before calling traverse recursively. This ensures that cycles
       // are broken the same way across multiple compilations.
-      Node[] callees = node.getCalleesWithDeterministicOrder();
+      Collection<Node> callees = node.getCalleesWithDeterministicOrder();
 
       if (options.testing.nondeterministicCycleElimination) {
-        reorderNodes(Arrays.asList(callees));
+        callees = reorderNodes(new ArrayList<>(callees));
       }
 
-      for (Node callee : callees) {
+      Iterator<Node> calleeIterator = callees.iterator();
+      while (calleeIterator.hasNext()) {
+        Node callee = calleeIterator.next();
         if (stackSet.contains(callee)) {
           // Found a cycle that needs to be eliminated.
           numberOfCycles++;
 
           if (edgeRemovalIsSafe(node, callee)) {
             // Break the cycle by removing the edge node->callee.
-            callee.removeCaller(node);
+            if (options.testing.nondeterministicCycleElimination) {
+              callee.removeCaller(node);
+            } else {
+              // Need to remove `callee` from `node.callees` using the iterator to prevent a
+              // ConcurrentModificationException. This is not needed when nondeterministic cycle
+              // elimination is enabled, because we iterate a copy of `node.callees` in that case.
+              calleeIterator.remove();
+              callee.getCallersWithDeterministicOrder().remove(node);
+            }
 
             if (Log.ENABLED) {
               Log.info(