diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index 3586d6d..9cc1b53 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -754,6 +754,10 @@
       forceInline = true;
     }
 
+    private void unsetForceInline() {
+      forceInline = false;
+    }
+
     private void markPublicized() {
       publicized = true;
     }
@@ -835,6 +839,10 @@
     ensureMutableOI().markForceInline();
   }
 
+  public synchronized void unsetForceInline() {
+    ensureMutableOI().unsetForceInline();
+  }
+
   synchronized public void markPublicized() {
     ensureMutableOI().markPublicized();
   }
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 650757e..382dd64 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
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.ir.conversion;
 
+import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
@@ -15,16 +16,23 @@
 import com.android.tools.r8.graph.GraphLense.GraphLenseLookupResult;
 import com.android.tools.r8.graph.UseRegistry;
 import com.android.tools.r8.ir.code.Invoke.Type;
+import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.ThrowingBiConsumer;
+import com.android.tools.r8.utils.Timing;
 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;
+import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
+import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -56,7 +64,7 @@
     this.shuffle = options.testing.irOrdering;
   }
 
-  private static class Node {
+  public static class Node {
 
     public final DexEncodedMethod method;
     private int invokeCount = 0;
@@ -68,7 +76,7 @@
     // Incoming calls to this method.
     private final Set<Node> callers = new LinkedHashSet<>();
 
-    private Node(DexEncodedMethod method) {
+    public Node(DexEncodedMethod method) {
       this.method = method;
     }
 
@@ -76,19 +84,20 @@
       return method.accessFlags.isBridge();
     }
 
-    private void addCallee(Node method) {
+    public void addCallee(Node method) {
       callees.add(method);
+      method.callers.add(this);
     }
 
-    private void addCaller(Node method) {
-      callers.add(method);
+    public boolean hasCallee(Node method) {
+      return callees.contains(method);
     }
 
     boolean isSelfRecursive() {
       return isSelfRecursive;
     }
 
-    boolean isLeaf() {
+    public boolean isLeaf() {
       return callees.isEmpty();
     }
 
@@ -96,7 +105,7 @@
     public String toString() {
       StringBuilder builder = new StringBuilder();
       builder.append("MethodNode for: ");
-      builder.append(method.qualifiedName());
+      builder.append(method.toSourceString());
       builder.append(" (");
       builder.append(callees.size());
       builder.append(" callees, ");
@@ -114,7 +123,7 @@
         builder.append("Callees:\n");
         for (Node call : callees) {
           builder.append("  ");
-          builder.append(call.method.qualifiedName());
+          builder.append(call.method.toSourceString());
           builder.append("\n");
         }
       }
@@ -122,7 +131,7 @@
         builder.append("Callers:\n");
         for (Node caller : callers) {
           builder.append("  ");
-          builder.append(caller.method.qualifiedName());
+          builder.append(caller.method.toSourceString());
           builder.append("\n");
         }
       }
@@ -136,8 +145,12 @@
   private final Set<DexEncodedMethod> singleCallSite = Sets.newIdentityHashSet();
   private final Set<DexEncodedMethod> doubleCallSite = Sets.newIdentityHashSet();
 
-  public static CallGraph build(DexApplication application, AppInfoWithLiveness appInfo,
-      GraphLense graphLense, InternalOptions options) {
+  public static CallGraph build(
+      DexApplication application,
+      AppInfoWithLiveness appInfo,
+      GraphLense graphLense,
+      InternalOptions options,
+      Timing timing) {
     CallGraph graph = new CallGraph(options);
     DexClass[] classes = application.classes().toArray(new DexClass[application.classes().size()]);
     Arrays.sort(classes, (DexClass a, DexClass b) -> a.type.slowCompareTo(b.type));
@@ -149,8 +162,13 @@
       }
     }
     assert allMethodsExists(application, graph);
-    graph.breakCycles();
-    assert graph.breakCycles() == 0;  // This time the cycles should be gone.
+
+    timing.begin("Cycle elimination");
+    CycleEliminator cycleEliminator = new CycleEliminator(graph.nodes.values(), options);
+    cycleEliminator.breakCycles();
+    timing.end();
+    assert cycleEliminator.breakCycles() == 0; // This time the cycles should be gone.
+
     graph.fillCallSiteSets(appInfo);
     return graph;
   }
@@ -196,9 +214,10 @@
 
   /**
    * Extract the next set of leaves (nodes with an call (outgoing) degree of 0) if any.
-   * <p>
-   * All nodes in the graph are extracted if called repeatedly until null is returned.
-   * Please note that there are no cycles in this graph (see {@link #breakCycles}).
+   *
+   * <p>All nodes in the graph are extracted if called repeatedly until null is returned. Please
+   * note that there are no cycles in this graph (see {@link CycleEliminator#breakCycles}).
+   *
    * <p>
    */
   private Set<DexEncodedMethod> extractLeaves() {
@@ -215,48 +234,197 @@
         .collect(Collectors.toCollection(LinkedHashSet::new)));
   }
 
-  private int traverse(Node node, Set<Node> stack, Set<Node> marked) {
-    int numberOfCycles = 0;
-    if (!marked.contains(node)) {
-      assert !stack.contains(node);
-      stack.add(node);
-      ArrayList<Node> toBeRemoved = null;
-      // Sort the callees before calling traverse recursively.
-      // This will ensure cycles are broken the same way across
-      // multiple invocations of the R8 compiler.
+  public static class CycleEliminator {
+
+    public static final String CYCLIC_FORCE_INLINING_MESSAGE =
+        "Unable to satisfy force inlining constraints due to cyclic force inlining";
+
+    private static class CallEdge {
+
+      private final Node caller;
+      private final Node callee;
+
+      public CallEdge(Node caller, Node callee) {
+        this.caller = caller;
+        this.callee = callee;
+      }
+    }
+
+    private final Collection<Node> nodes;
+    private final InternalOptions options;
+
+    // DFS stack.
+    private Deque<Node> stack = new ArrayDeque<>();
+
+    // Set of nodes on the DFS stack.
+    private Set<Node> stackSet = Sets.newIdentityHashSet();
+
+    // Set of nodes that have been visited entirely.
+    private Set<Node> marked = Sets.newIdentityHashSet();
+
+    private int numberOfCycles = 0;
+
+    public CycleEliminator(Collection<Node> nodes, InternalOptions options) {
+      this.options = options;
+
+      // Call to reorderNodes must happen after assigning options.
+      this.nodes =
+          options.testing.nondeterministicCycleElimination
+              ? reorderNodes(new ArrayList<>(nodes))
+              : nodes;
+    }
+
+    public int breakCycles() {
+      // Break cycles in this call graph by removing edges causing cycles.
+      for (Node node : nodes) {
+        traverse(node);
+      }
+      int result = numberOfCycles;
+      reset();
+      return result;
+    }
+
+    private void reset() {
+      assert stack.isEmpty();
+      assert stackSet.isEmpty();
+      marked.clear();
+      numberOfCycles = 0;
+    }
+
+    private void traverse(Node node) {
+      if (marked.contains(node)) {
+        // Already visited all nodes that can be reached from this node.
+        return;
+      }
+
+      push(node);
+
+      // Sort the callees before calling traverse recursively. This will ensure cycles are broken
+      // the same way across multiple invocations of the R8 compiler.
       Node[] callees = node.callees.toArray(new Node[node.callees.size()]);
       Arrays.sort(callees, (Node a, Node b) -> a.method.method.slowCompareTo(b.method.method));
+      if (options.testing.nondeterministicCycleElimination) {
+        reorderNodes(Arrays.asList(callees));
+      }
+
       for (Node callee : callees) {
-        if (stack.contains(callee)) {
-          if (toBeRemoved == null) {
-            toBeRemoved = new ArrayList<>();
+        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.callers.remove(node);
+            node.callees.remove(callee);
+
+            if (Log.ENABLED) {
+              Log.info(
+                  CallGraph.class,
+                  "Removed call edge from method '%s' to '%s'",
+                  node.method.toSourceString(),
+                  callee.method.toSourceString());
+            }
+          } else {
+            // The cycle has a method that is marked as force inline.
+            LinkedList<Node> cycle = extractCycle(callee);
+
+            if (Log.ENABLED) {
+              Log.info(
+                  CallGraph.class, "Extracted cycle to find an edge that can safely be removed");
+            }
+
+            // Break the cycle by finding an edge that can be removed without breaking force
+            // inlining. If that is not possible, this call fails with a compilation error.
+            CallEdge edge = findCallEdgeForRemoval(cycle);
+
+            // The edge will be null if this cycle has already been eliminated as a result of
+            // another cycle elimination.
+            if (edge != null) {
+              assert edgeRemovalIsSafe(edge.caller, edge.callee);
+
+              // Break the cycle by removing the edge caller->callee.
+              edge.caller.callees.remove(edge.callee);
+              edge.callee.callers.remove(edge.caller);
+
+              if (Log.ENABLED) {
+                Log.info(
+                    CallGraph.class,
+                    "Removed call edge from force inlined method '%s' to '%s' to ensure that "
+                        + "force inlining will succeed",
+                    node.method.toSourceString(),
+                    callee.method.toSourceString());
+              }
+            }
+
+            // Recover the stack.
+            recoverStack(cycle);
           }
-          // We have a cycle; break it by removing node->callee.
-          toBeRemoved.add(callee);
-          callee.callers.remove(node);
         } else {
-          numberOfCycles += traverse(callee, stack, marked);
+          traverse(callee);
         }
       }
-      if (toBeRemoved != null) {
-        numberOfCycles += toBeRemoved.size();
-        node.callees.removeAll(toBeRemoved);
-      }
-      stack.remove(node);
+      pop(node);
       marked.add(node);
     }
-    return numberOfCycles;
-  }
 
-  private int breakCycles() {
-    // Break cycles in this call graph by removing edges causing cycles.
-    int numberOfCycles = 0;
-    Set<Node> stack = Sets.newIdentityHashSet();
-    Set<Node> marked = Sets.newIdentityHashSet();
-    for (Node node : nodes.values()) {
-      numberOfCycles += traverse(node, stack, marked);
+    private void push(Node node) {
+      stack.push(node);
+      boolean changed = stackSet.add(node);
+      assert changed;
     }
-    return numberOfCycles;
+
+    private void pop(Node node) {
+      Node popped = stack.pop();
+      assert popped == node;
+      boolean changed = stackSet.remove(node);
+      assert changed;
+    }
+
+    private LinkedList<Node> extractCycle(Node entry) {
+      LinkedList<Node> cycle = new LinkedList<>();
+      do {
+        assert !stack.isEmpty();
+        cycle.add(stack.pop());
+      } while (cycle.getLast() != entry);
+      return cycle;
+    }
+
+    private CallEdge findCallEdgeForRemoval(LinkedList<Node> extractedCycle) {
+      Node callee = extractedCycle.getLast();
+      for (Node caller : extractedCycle) {
+        if (!caller.callees.contains(callee)) {
+          // No need to break any edges since this cycle has already been broken previously.
+          assert !callee.callers.contains(caller);
+          return null;
+        }
+        if (edgeRemovalIsSafe(caller, callee)) {
+          return new CallEdge(caller, callee);
+        }
+        callee = caller;
+      }
+      throw new CompilationError(CYCLIC_FORCE_INLINING_MESSAGE);
+    }
+
+    private static boolean edgeRemovalIsSafe(Node caller, Node callee) {
+      // All call edges where the callee is a method that should be force inlined must be kept,
+      // to guarantee that the IR converter will process the callee before the caller.
+      return !callee.method.getOptimizationInfo().forceInline();
+    }
+
+    private void recoverStack(LinkedList<Node> extractedCycle) {
+      Iterator<Node> descendingIt = extractedCycle.descendingIterator();
+      while (descendingIt.hasNext()) {
+        stack.push(descendingIt.next());
+      }
+    }
+
+    private Collection<Node> reorderNodes(List<Node> nodes) {
+      assert options.testing.nondeterministicCycleElimination;
+      if (!InternalOptions.DETERMINISTIC_DEBUGGING) {
+        Collections.shuffle(nodes);
+      }
+      return nodes;
+    }
   }
 
   synchronized private Node ensureMethodNode(DexEncodedMethod method) {
@@ -268,7 +436,6 @@
     assert callee != null;
     if (caller != callee) {
       caller.addCallee(callee);
-      callee.addCaller(caller);
     } else {
       caller.isSelfRecursive = true;
     }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index 3ea97e4..a803de2 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -401,8 +401,8 @@
     OptimizationFeedback directFeedback = new OptimizationFeedbackDirect();
     {
       timing.begin("Build call graph");
-      CallGraph callGraph = CallGraph
-          .build(application, appInfo.withLiveness(), graphLense, options);
+      CallGraph callGraph =
+          CallGraph.build(application, appInfo.withLiveness(), graphLense, options, timing);
       timing.end();
       timing.begin("IR conversion phase 1");
       BiConsumer<IRCode, DexEncodedMethod> outlineHandler =
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 3909dfd..93a80b6 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -447,6 +447,7 @@
     public boolean placeExceptionalBlocksLast = false;
     public boolean dontCreateMarkerInD8 = false;
     public boolean forceJumboStringProcessing = false;
+    public boolean nondeterministicCycleElimination = false;
     public Set<Inliner.Reason> validInliningReasons = null;
     public boolean suppressExperimentalCfBackendWarning = false;
   }
diff --git a/src/test/examples/classmerging/CallGraphCycleTest.java b/src/test/examples/classmerging/CallGraphCycleTest.java
new file mode 100644
index 0000000..40347d6
--- /dev/null
+++ b/src/test/examples/classmerging/CallGraphCycleTest.java
@@ -0,0 +1,30 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package classmerging;
+
+public class CallGraphCycleTest {
+
+  public static void main(String[] args) {
+    new B(true);
+  }
+
+  public static class A {
+
+    public A(boolean instantiateB) {
+      if (instantiateB) {
+        new B(false);
+      }
+      System.out.println("A(" + instantiateB + ")");
+    }
+  }
+
+  public static class B extends A {
+
+    public B(boolean instantiateBinA) {
+      super(instantiateBinA);
+      System.out.println("B(" + instantiateBinA + ")");
+    }
+  }
+}
diff --git a/src/test/examples/classmerging/keep-rules.txt b/src/test/examples/classmerging/keep-rules.txt
index 4ba014e..37a3010 100644
--- a/src/test/examples/classmerging/keep-rules.txt
+++ b/src/test/examples/classmerging/keep-rules.txt
@@ -7,6 +7,9 @@
 -keep public class classmerging.Test {
   public static void main(...);
 }
+-keep public class classmerging.CallGraphCycleTest {
+  public static void main(...);
+}
 -keep public class classmerging.ClassWithNativeMethodTest {
   public static void main(...);
 }
diff --git a/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java b/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
index b6489b0..7635f0c 100644
--- a/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
@@ -70,6 +70,7 @@
     options.enableClassMerging = true;
     options.enableClassInlining = false;
     options.enableMinification = false;
+    options.testing.nondeterministicCycleElimination = true;
   }
 
   private void runR8(Path proguardConfig, Consumer<InternalOptions> optionsConsumer)
@@ -115,6 +116,29 @@
     }
   }
 
+  // This test has a cycle in the call graph consisting of the methods A.<init> and B.<init>.
+  // When nondeterministicCycleElimination is enabled, we shuffle the nodes in the call graph
+  // before the cycle elimination. Therefore, it is nondeterministic if the cycle detector will
+  // detect the cycle upon the call edge A.<init> to B.<init>, or B.<init> to A.<init>. In order
+  // increase the likelihood that this test encounters both orderings, the test is repeated 5 times.
+  // Assuming that the chance of observing one of the two orderings is 50%, this test therefore has
+  // approximately 3% chance of succeeding although there is an issue.
+  @Test
+  public void testCallGraphCycle() throws Exception {
+    String main = "classmerging.CallGraphCycleTest";
+    Path[] programFiles =
+        new Path[] {
+          CF_DIR.resolve("CallGraphCycleTest.class"),
+          CF_DIR.resolve("CallGraphCycleTest$A.class"),
+          CF_DIR.resolve("CallGraphCycleTest$B.class")
+        };
+    Set<String> preservedClassNames =
+        ImmutableSet.of("classmerging.CallGraphCycleTest", "classmerging.CallGraphCycleTest$B");
+    for (int i = 0; i < 5; i++) {
+      runTest(main, programFiles, preservedClassNames::contains);
+    }
+  }
+
   @Test
   public void testConflictInGeneratedName() throws Exception {
     String main = "classmerging.ConflictInGeneratedNameTest";
diff --git a/src/test/java/com/android/tools/r8/ir/callgraph/CycleEliminationTest.java b/src/test/java/com/android/tools/r8/ir/callgraph/CycleEliminationTest.java
new file mode 100644
index 0000000..56699e3
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/callgraph/CycleEliminationTest.java
@@ -0,0 +1,214 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.callgraph;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.errors.CompilationError;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.ir.conversion.CallGraph.CycleEliminator;
+import com.android.tools.r8.ir.conversion.CallGraph.Node;
+import com.android.tools.r8.utils.InternalOptions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import java.util.Set;
+import java.util.function.BooleanSupplier;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.ExpectedException;
+
+public class CycleEliminationTest extends TestBase {
+
+  private static class Configuration {
+
+    final Collection<Node> nodes;
+    final Set<Node> forceInline;
+    final BooleanSupplier test;
+
+    Configuration(Collection<Node> nodes, Set<Node> forceInline, BooleanSupplier test) {
+      this.nodes = nodes;
+      this.forceInline = forceInline;
+      this.test = test;
+    }
+  }
+
+  private DexItemFactory dexItemFactory = new DexItemFactory();
+
+  @Rule public final ExpectedException exception = ExpectedException.none();
+
+  @Test
+  public void testSimpleCycle() {
+    Node method = createNode("n1");
+    Node forceInlinedMethod = createForceInlinedNode("n2");
+
+    Iterable<Collection<Node>> orderings =
+        ImmutableList.of(
+            ImmutableList.of(method, forceInlinedMethod),
+            ImmutableList.of(forceInlinedMethod, method));
+
+    for (Collection<Node> nodes : orderings) {
+      // Create a cycle between the two nodes.
+      method.addCallee(forceInlinedMethod);
+      forceInlinedMethod.addCallee(method);
+
+      // Check that the cycle eliminator finds the cycle.
+      CycleEliminator cycleEliminator = new CycleEliminator(nodes, new InternalOptions());
+      assertEquals(1, cycleEliminator.breakCycles());
+
+      // The edge from method to forceInlinedMethod should be removed to ensure that force inlining
+      // will work.
+      assertTrue(forceInlinedMethod.isLeaf());
+
+      // Check that the cycle eliminator agrees that there are no more cycles left.
+      assertEquals(0, cycleEliminator.breakCycles());
+    }
+  }
+
+  @Test
+  public void testSimpleCycleWithCyclicForceInlining() {
+    Node method = createForceInlinedNode("n1");
+    Node forceInlinedMethod = createForceInlinedNode("n2");
+
+    // Create a cycle between the two nodes.
+    method.addCallee(forceInlinedMethod);
+    forceInlinedMethod.addCallee(method);
+
+    CycleEliminator cycleEliminator =
+        new CycleEliminator(ImmutableList.of(method, forceInlinedMethod), new InternalOptions());
+
+    exception.expect(CompilationError.class);
+    exception.expectMessage(CycleEliminator.CYCLIC_FORCE_INLINING_MESSAGE);
+
+    // Should throw because force inlining will fail.
+    cycleEliminator.breakCycles();
+  }
+
+  @Test
+  public void testGraphWithNestedCycles() {
+    Node n1 = createNode("n1");
+    Node n2 = createNode("n2");
+    Node n3 = createNode("n3");
+
+    BooleanSupplier canInlineN1 =
+        () -> {
+          // The node n1 should be force inlined into n2 and n3, so these edges must be kept.
+          assertTrue(n2.hasCallee(n1));
+          assertTrue(n3.hasCallee(n1));
+          // Furthermore, the edge from n1 to n2 must be removed.
+          assertFalse(n1.hasCallee(n2));
+          return true;
+        };
+
+    BooleanSupplier canInlineN3 =
+        () -> {
+          // The node n3 should be force inlined into n2, so this edge must be kept.
+          assertTrue(n2.hasCallee(n3));
+          // Furthermore, one of the edges n1 -> n2 and n3 -> n1 must be removed.
+          assertFalse(n1.hasCallee(n2) && n3.hasCallee(n1));
+          return true;
+        };
+
+    BooleanSupplier canInlineN1N3 =
+        () -> {
+          // The edge n1 -> n2 must be removed.
+          assertFalse(n1.hasCallee(n2));
+          // Check that both can be force inlined.
+          return canInlineN1.getAsBoolean() && canInlineN3.getAsBoolean();
+        };
+
+    List<Collection<Node>> orderings =
+        ImmutableList.of(
+            ImmutableList.of(n1, n2, n3),
+            ImmutableList.of(n1, n3, n2),
+            ImmutableList.of(n2, n1, n3),
+            ImmutableList.of(n2, n3, n1),
+            ImmutableList.of(n3, n1, n2),
+            ImmutableList.of(n3, n2, n1));
+
+    List<Configuration> configurations = new ArrayList<>();
+    // All orderings, where no methods are marked as force inline.
+    orderings
+        .stream()
+        .map(ordering -> new Configuration(ordering, ImmutableSet.of(), null))
+        .forEach(configurations::add);
+    // All orderings, where n1 is marked as force inline
+    // (the configuration where n2 is marked as force inline is symmetric).
+    orderings
+        .stream()
+        .map(ordering -> new Configuration(ordering, ImmutableSet.of(n1), canInlineN1))
+        .forEach(configurations::add);
+    // All orderings, where n3 is marked as force inline.
+    orderings
+        .stream()
+        .map(ordering -> new Configuration(ordering, ImmutableSet.of(n3), canInlineN3))
+        .forEach(configurations::add);
+    // All orderings, where n1 and n3 are marked as force inline.
+    orderings
+        .stream()
+        .map(ordering -> new Configuration(ordering, ImmutableSet.of(n1, n3), canInlineN1N3))
+        .forEach(configurations::add);
+
+    for (Configuration configuration : configurations) {
+      // Create a cycle between the three nodes.
+      n1.addCallee(n2);
+      n2.addCallee(n3);
+      n3.addCallee(n1);
+
+      // Create a cycle in the graph between node n1 and n2.
+      n2.addCallee(n1);
+
+      for (Node node : configuration.nodes) {
+        if (configuration.forceInline.contains(node)) {
+          node.method.markForceInline();
+        } else {
+          node.method.unsetForceInline();
+        }
+      }
+
+      // Check that the cycle eliminator finds the cycles.
+      CycleEliminator cycleEliminator =
+          new CycleEliminator(configuration.nodes, new InternalOptions());
+      int numberOfCycles = cycleEliminator.breakCycles();
+      if (numberOfCycles == 1) {
+        // If only one cycle was removed, then it must be the edge from n1 -> n2 that was removed.
+        assertTrue(n1.isLeaf());
+      } else {
+        // Check that the cycle eliminator found both cycles.
+        assertEquals(2, numberOfCycles);
+      }
+
+      // Check that the cycle eliminator agrees that there are no more cycles left.
+      assertEquals(0, cycleEliminator.breakCycles());
+
+      // Check that force inlining is guaranteed to succeed.
+      if (configuration.test != null) {
+        assertTrue(configuration.test.getAsBoolean());
+      }
+    }
+  }
+
+  private Node createNode(String methodName) {
+    DexMethod signature =
+        dexItemFactory.createMethod(
+            dexItemFactory.objectType,
+            dexItemFactory.createProto(dexItemFactory.voidType),
+            methodName);
+    return new Node(new DexEncodedMethod(signature, null, null, null, null));
+  }
+
+  private Node createForceInlinedNode(String methodName) {
+    Node node = createNode(methodName);
+    node.method.markForceInline();
+    return node;
+  }
+}