Merge "Fix tests on Windows"
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 eb8574d..9a44dde 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -763,6 +763,10 @@
forceInline = true;
}
+ private void unsetForceInline() {
+ forceInline = false;
+ }
+
private void markPublicized() {
publicized = true;
}
@@ -848,6 +852,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 9433887..33531da 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
@@ -417,8 +417,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;
+ }
+}
diff --git a/src/test/java/com/android/tools/r8/neverreturnsnormally/NeverReturnsNormallyTest.java b/src/test/java/com/android/tools/r8/neverreturnsnormally/NeverReturnsNormallyTest.java
index c929eaf..878cb7c 100644
--- a/src/test/java/com/android/tools/r8/neverreturnsnormally/NeverReturnsNormallyTest.java
+++ b/src/test/java/com/android/tools/r8/neverreturnsnormally/NeverReturnsNormallyTest.java
@@ -16,6 +16,7 @@
import com.android.tools.r8.utils.AndroidApp;
import com.android.tools.r8.utils.DexInspector;
import com.android.tools.r8.utils.DexInspector.ClassSubject;
+import com.android.tools.r8.utils.DexInspector.DexInstructionSubject;
import com.android.tools.r8.utils.DexInspector.InstructionSubject;
import com.android.tools.r8.utils.DexInspector.InvokeInstructionSubject;
import com.android.tools.r8.utils.DexInspector.MethodSubject;
@@ -82,7 +83,8 @@
assertTrue(insn.isInvoke());
assertTrue(((InvokeInstructionSubject) insn)
.invokedMethod().name.toString().equals("throwNpe"));
- assertTrue(nextInstruction(instructions).isConst4());
+ insn = nextInstruction(instructions);
+ assertTrue(insn instanceof DexInstructionSubject && ((DexInstructionSubject) insn).isConst4());
assertTrue(nextInstruction(instructions).isThrow());
assertFalse(instructions.hasNext());
@@ -105,7 +107,8 @@
assertTrue(((InvokeInstructionSubject) insn)
.invokedMethod().name.toString().equals("throwNpe"));
}
- assertTrue(nextInstruction(instructions).isConst4());
+ insn = nextInstruction(instructions);
+ assertTrue(insn instanceof DexInstructionSubject && ((DexInstructionSubject) insn).isConst4());
assertTrue(nextInstruction(instructions).isThrow());
assertFalse(instructions.hasNext());
@@ -119,7 +122,8 @@
assertTrue(insn.isInvoke());
assertTrue(((InvokeInstructionSubject) insn)
.invokedMethod().name.toString().equals("innerNotReachable"));
- assertTrue(nextInstruction(instructions).isConst4());
+ insn = nextInstruction(instructions);
+ assertTrue(insn instanceof DexInstructionSubject && ((DexInstructionSubject) insn).isConst4());
assertTrue(nextInstruction(instructions).isThrow());
assertFalse(instructions.hasNext());
}
diff --git a/src/test/java/com/android/tools/r8/utils/DexInspector.java b/src/test/java/com/android/tools/r8/utils/DexInspector.java
index 955d1ee..059a24a 100644
--- a/src/test/java/com/android/tools/r8/utils/DexInspector.java
+++ b/src/test/java/com/android/tools/r8/utils/DexInspector.java
@@ -54,6 +54,7 @@
import com.android.tools.r8.code.SputWide;
import com.android.tools.r8.code.Throw;
import com.android.tools.r8.dex.ApplicationReader;
+import com.android.tools.r8.graph.Code;
import com.android.tools.r8.graph.DexAnnotation;
import com.android.tools.r8.graph.DexAnnotationElement;
import com.android.tools.r8.graph.DexAnnotationSet;
@@ -81,6 +82,7 @@
import com.android.tools.r8.naming.signature.GenericSignatureAction;
import com.android.tools.r8.naming.signature.GenericSignatureParser;
import com.android.tools.r8.smali.SmaliBuilder;
+import com.android.tools.r8.utils.DexInspector.FieldAccessInstructionSubject;
import com.google.common.collect.BiMap;
import com.google.common.collect.ImmutableList;
import java.io.IOException;
@@ -106,8 +108,6 @@
private final ClassNameMapper mapping;
private final BiMap<String, String> originalToObfuscatedMapping;
- private final InstructionSubjectFactory factory = new InstructionSubjectFactory();
-
public static MethodSignature MAIN =
new MethodSignature("main", "void", new String[]{"java.lang.String[]"});
@@ -304,18 +304,18 @@
return obfuscatedType;
}
- public abstract class Subject {
+ public abstract static class Subject {
public abstract boolean isPresent();
public abstract boolean isRenamed();
}
- public abstract class AnnotationSubject extends Subject {
+ public abstract static class AnnotationSubject extends Subject {
public abstract DexEncodedAnnotation getAnnotation();
}
- public class FoundAnnotationSubject extends AnnotationSubject {
+ public static class FoundAnnotationSubject extends AnnotationSubject {
private final DexAnnotation annotation;
@@ -339,7 +339,7 @@
}
}
- public class AbsentAnnotationSubject extends AnnotationSubject {
+ public static class AbsentAnnotationSubject extends AnnotationSubject {
@Override
public boolean isPresent() {
@@ -357,8 +357,7 @@
}
}
-
- public abstract class ClassSubject extends Subject {
+ public abstract static class ClassSubject extends Subject {
public abstract void forAllMethods(Consumer<FoundMethodSubject> inspection);
@@ -737,7 +736,7 @@
}
}
- public abstract class MemberSubject extends Subject {
+ public abstract static class MemberSubject extends Subject {
public abstract boolean isPublic();
@@ -760,7 +759,7 @@
}
}
- public abstract class MethodSubject extends MemberSubject {
+ public abstract static class MethodSubject extends MemberSubject {
public abstract boolean isAbstract();
@@ -970,7 +969,7 @@
@Override
public Iterator<InstructionSubject> iterateInstructions() {
- return new InstructionIterator(this);
+ return createInstructionIterator(this);
}
@Override
@@ -985,7 +984,7 @@
}
}
- public abstract class FieldSubject extends MemberSubject {
+ public abstract static class FieldSubject extends MemberSubject {
public abstract boolean hasExplicitStaticValue();
public abstract DexEncodedField getField();
@@ -999,7 +998,7 @@
public abstract String getFinalSignatureAttribute();
}
- public class AbsentFieldSubject extends FieldSubject {
+ public static class AbsentFieldSubject extends FieldSubject {
@Override
public boolean isPublic() {
@@ -1192,91 +1191,139 @@
}
}
- private class InstructionSubjectFactory {
+ public interface InstructionSubject {
+ boolean isFieldAccess();
- InstructionSubject create(Instruction instruction) {
- if (isInvoke(instruction)) {
- return new InvokeInstructionSubject(this, instruction);
- } else if (isFieldAccess(instruction)) {
- return new FieldAccessInstructionSubject(this, instruction);
- } else {
- return new InstructionSubject(this, instruction);
- }
+ boolean isInvokeVirtual();
+
+ boolean isInvokeInterface();
+
+ boolean isInvokeDirect();
+
+ boolean isInvokeSuper();
+
+ boolean isInvokeStatic();
+
+ boolean isNop();
+
+ boolean isConstString();
+
+ boolean isConstString(String value);
+
+ boolean isGoto();
+
+ boolean isIfNez();
+
+ boolean isIfEqz();
+
+ boolean isReturnVoid();
+
+ boolean isThrow();
+
+ default boolean isInvoke() {
+ return isInvokeVirtual()
+ || isInvokeInterface()
+ || isInvokeDirect()
+ || isInvokeSuper()
+ || isInvokeStatic();
+ }
+ }
+
+ public InstructionSubject createInstructionSubject(Instruction instruction) {
+ DexInstructionSubject dexInst = new DexInstructionSubject(instruction);
+ if (dexInst.isInvoke()) {
+ return new InvokeDexInstructionSubject(instruction);
+ } else if (dexInst.isFieldAccess()) {
+ return new FieldAccessDexInstructionSubject(instruction);
+ } else {
+ return dexInst;
+ }
+ }
+
+ public class DexInstructionSubject implements InstructionSubject {
+ protected Instruction instruction;
+
+ public DexInstructionSubject(Instruction instruction) {
+ this.instruction = instruction;
}
- boolean isInvoke(Instruction instruction) {
- return isInvokeVirtual(instruction)
- || isInvokeInterface(instruction)
- || isInvokeDirect(instruction)
- || isInvokeSuper(instruction)
- || isInvokeStatic(instruction);
+ @Override
+ public boolean isFieldAccess() {
+ return isInstanceGet() || isInstancePut() || isStaticGet() || isStaticSet();
}
- boolean isInvokeVirtual(Instruction instruction) {
+ @Override
+ public boolean isInvokeVirtual() {
return instruction instanceof InvokeVirtual || instruction instanceof InvokeVirtualRange;
}
- boolean isInvokeInterface(Instruction instruction) {
+ @Override
+ public boolean isInvokeInterface() {
return instruction instanceof InvokeInterface || instruction instanceof InvokeInterfaceRange;
}
- boolean isInvokeDirect(Instruction instruction) {
+ @Override
+ public boolean isInvokeDirect() {
return instruction instanceof InvokeDirect || instruction instanceof InvokeDirectRange;
}
- boolean isInvokeSuper(Instruction instruction) {
+ @Override
+ public boolean isInvokeSuper() {
return instruction instanceof InvokeSuper || instruction instanceof InvokeSuperRange;
}
- boolean isInvokeStatic(Instruction instruction) {
+ @Override
+ public boolean isInvokeStatic() {
return instruction instanceof InvokeStatic || instruction instanceof InvokeStaticRange;
}
- boolean isNop(Instruction instruction) {
+ @Override
+ public boolean isNop() {
return instruction instanceof Nop;
}
- boolean isGoto(Instruction instruction) {
- return instruction instanceof Goto;
- }
-
- boolean isReturnVoid(Instruction instruction) {
- return instruction instanceof ReturnVoid;
- }
-
- boolean isConst4(Instruction instruction) {
- return instruction instanceof Const4;
- }
-
- boolean isThrow(Instruction instruction) {
- return instruction instanceof Throw;
- }
-
- boolean isConstString(Instruction instruction) {
+ @Override
+ public boolean isConstString() {
return instruction instanceof ConstString;
}
- boolean isConstString(Instruction instruction, String value) {
+ @Override
+ public boolean isConstString(String value) {
return instruction instanceof ConstString
&& ((ConstString) instruction).BBBB.toSourceString().equals(value);
}
- boolean isIfNez(Instruction instruction) {
+ @Override
+ public boolean isGoto() {
+
+ return instruction instanceof Goto;
+ }
+
+ @Override
+ public boolean isIfNez() {
return instruction instanceof IfNez;
}
- boolean isIfEqz(Instruction instruction) {
+ @Override
+ public boolean isIfEqz() {
return instruction instanceof IfEqz;
}
- boolean isFieldAccess(Instruction instruction) {
- return isInstanceGet(instruction)
- || isInstancePut(instruction)
- || isStaticGet(instruction)
- || isStaticSet(instruction);
+ @Override
+ public boolean isReturnVoid() {
+ return instruction instanceof ReturnVoid;
}
- boolean isInstanceGet(Instruction instruction) {
+ @Override
+ public boolean isThrow() {
+ return instruction instanceof Throw;
+ }
+
+ public boolean isConst4() {
+ return instruction instanceof Const4;
+ }
+
+ public boolean isInstanceGet() {
return instruction instanceof Iget
|| instruction instanceof IgetBoolean
|| instruction instanceof IgetByte
@@ -1286,7 +1333,7 @@
|| instruction instanceof IgetObject;
}
- boolean isInstancePut(Instruction instruction) {
+ public boolean isInstancePut() {
return instruction instanceof Iput
|| instruction instanceof IputBoolean
|| instruction instanceof IputByte
@@ -1296,7 +1343,7 @@
|| instruction instanceof IputObject;
}
- boolean isStaticGet(Instruction instruction) {
+ public boolean isStaticGet() {
return instruction instanceof Sget
|| instruction instanceof SgetBoolean
|| instruction instanceof SgetByte
@@ -1306,7 +1353,7 @@
|| instruction instanceof SgetObject;
}
- boolean isStaticSet(Instruction instruction) {
+ public boolean isStaticSet() {
return instruction instanceof Sput
|| instruction instanceof SputBoolean
|| instruction instanceof SputByte
@@ -1317,89 +1364,21 @@
}
}
- public class InstructionSubject {
+ public interface InvokeInstructionSubject extends InstructionSubject {
+ TypeSubject holder();
- protected final InstructionSubjectFactory factory;
- protected final Instruction instruction;
-
- protected InstructionSubject(InstructionSubjectFactory factory, Instruction instruction) {
- this.factory = factory;
- this.instruction = instruction;
- }
-
- public boolean isInvoke() {
- return factory.isInvoke(instruction);
- }
-
- public boolean isFieldAccess() {
- return factory.isFieldAccess(instruction);
- }
-
- public boolean isInvokeVirtual() {
- return factory.isInvokeVirtual(instruction);
- }
-
- public boolean isInvokeInterface() {
- return factory.isInvokeInterface(instruction);
- }
-
- public boolean isInvokeDirect() {
- return factory.isInvokeDirect(instruction);
- }
-
- public boolean isInvokeSuper() {
- return factory.isInvokeSuper(instruction);
- }
-
- public boolean isInvokeStatic() {
- return factory.isInvokeStatic(instruction);
- }
-
- boolean isFieldAccess(Instruction instruction) {
- return factory.isFieldAccess(instruction);
- }
-
- public boolean isNop() {
- return factory.isNop(instruction);
- }
-
- public boolean isConstString() {
- return factory.isConstString(instruction);
- }
-
- public boolean isConstString(String value) {
- return factory.isConstString(instruction, value);
- }
-
- public boolean isGoto() {
- return factory.isGoto(instruction);
- }
-
- public boolean isIfNez() {
- return factory.isIfNez(instruction);
- }
-
- public boolean isIfEqz() {
- return factory.isIfEqz(instruction);
- }
-
- public boolean isReturnVoid() {
- return factory.isReturnVoid(instruction);
- }
-
- public boolean isConst4() {
- return factory.isConst4(instruction);
- }
-
- public boolean isThrow() {
- return factory.isThrow(instruction);
- }
+ DexMethod invokedMethod();
}
- public class InvokeInstructionSubject extends InstructionSubject {
+ public interface FieldAccessInstructionSubject extends InstructionSubject {
+ TypeSubject holder();
+ }
- InvokeInstructionSubject(InstructionSubjectFactory factory, Instruction instruction) {
- super(factory, instruction);
+ public class InvokeDexInstructionSubject extends DexInstructionSubject
+ implements InvokeInstructionSubject {
+
+ public InvokeDexInstructionSubject(Instruction instruction) {
+ super(instruction);
assert isInvoke();
}
@@ -1408,156 +1387,41 @@
}
public DexMethod invokedMethod() {
- if (instruction instanceof InvokeVirtual) {
- return ((InvokeVirtual) instruction).getMethod();
- }
- if (instruction instanceof InvokeVirtualRange) {
- return ((InvokeVirtualRange) instruction).getMethod();
- }
- if (instruction instanceof InvokeInterface) {
- return ((InvokeInterface) instruction).getMethod();
- }
- if (instruction instanceof InvokeInterfaceRange) {
- return ((InvokeInterfaceRange) instruction).getMethod();
- }
- if (instruction instanceof InvokeDirect) {
- return ((InvokeDirect) instruction).getMethod();
- }
- if (instruction instanceof InvokeDirectRange) {
- return ((InvokeDirectRange) instruction).getMethod();
- }
- if (instruction instanceof InvokeSuper) {
- return ((InvokeSuper) instruction).getMethod();
- }
- if (instruction instanceof InvokeSuperRange) {
- return ((InvokeSuperRange) instruction).getMethod();
- }
- if (instruction instanceof InvokeDirect) {
- return ((InvokeDirect) instruction).getMethod();
- }
- if (instruction instanceof InvokeDirectRange) {
- return ((InvokeDirectRange) instruction).getMethod();
- }
- if (instruction instanceof InvokeStatic) {
- return ((InvokeStatic) instruction).getMethod();
- }
- if (instruction instanceof InvokeStaticRange) {
- return ((InvokeStaticRange) instruction).getMethod();
- }
- assert false;
- return null;
+ return instruction.getMethod();
}
}
- public class FieldAccessInstructionSubject extends InstructionSubject {
+ public class FieldAccessDexInstructionSubject extends DexInstructionSubject
+ implements FieldAccessInstructionSubject {
- FieldAccessInstructionSubject(InstructionSubjectFactory factory, Instruction instruction) {
- super(factory, instruction);
+ public FieldAccessDexInstructionSubject(Instruction instruction) {
+ super(instruction);
assert isFieldAccess();
}
public TypeSubject holder() {
- return new TypeSubject(accessedField().getHolder());
- }
-
- public DexField accessedField() {
- if (instruction instanceof Iget) {
- return ((Iget) instruction).getField();
- }
- if (instruction instanceof IgetBoolean) {
- return ((IgetBoolean) instruction).getField();
- }
- if (instruction instanceof IgetByte) {
- return ((IgetByte) instruction).getField();
- }
- if (instruction instanceof IgetShort) {
- return ((IgetShort) instruction).getField();
- }
- if (instruction instanceof IgetChar) {
- return ((IgetChar) instruction).getField();
- }
- if (instruction instanceof IgetWide) {
- return ((IgetWide) instruction).getField();
- }
- if (instruction instanceof IgetObject) {
- return ((IgetObject) instruction).getField();
- }
- if (instruction instanceof Iput) {
- return ((Iput) instruction).getField();
- }
- if (instruction instanceof IputBoolean) {
- return ((IputBoolean) instruction).getField();
- }
- if (instruction instanceof IputByte) {
- return ((IputByte) instruction).getField();
- }
- if (instruction instanceof IputShort) {
- return ((IputShort) instruction).getField();
- }
- if (instruction instanceof IputChar) {
- return ((IputChar) instruction).getField();
- }
- if (instruction instanceof IputWide) {
- return ((IputWide) instruction).getField();
- }
- if (instruction instanceof IputObject) {
- return ((IputObject) instruction).getField();
- }
- if (instruction instanceof Sget) {
- return ((Sget) instruction).getField();
- }
- if (instruction instanceof SgetBoolean) {
- return ((SgetBoolean) instruction).getField();
- }
- if (instruction instanceof SgetByte) {
- return ((SgetByte) instruction).getField();
- }
- if (instruction instanceof SgetShort) {
- return ((SgetShort) instruction).getField();
- }
- if (instruction instanceof SgetChar) {
- return ((SgetChar) instruction).getField();
- }
- if (instruction instanceof SgetWide) {
- return ((SgetWide) instruction).getField();
- }
- if (instruction instanceof SgetObject) {
- return ((SgetObject) instruction).getField();
- }
- if (instruction instanceof Sput) {
- return ((Sput) instruction).getField();
- }
- if (instruction instanceof SputBoolean) {
- return ((SputBoolean) instruction).getField();
- }
- if (instruction instanceof SputByte) {
- return ((SputByte) instruction).getField();
- }
- if (instruction instanceof SputShort) {
- return ((SputShort) instruction).getField();
- }
- if (instruction instanceof SputChar) {
- return ((SputChar) instruction).getField();
- }
- if (instruction instanceof SputWide) {
- return ((SputWide) instruction).getField();
- }
- if (instruction instanceof SputObject) {
- return ((SputObject) instruction).getField();
- }
- assert false;
- return null;
+ return new TypeSubject(instruction.getField().getHolder());
}
}
- private class InstructionIterator implements Iterator<InstructionSubject> {
+ private interface InstructionIterator extends Iterator<InstructionSubject> {}
+
+ private InstructionIterator createInstructionIterator(MethodSubject method) {
+ Code code = method.getMethod().getCode();
+ assert code != null && code.isDexCode();
+ return new DexInstructionIterator(method);
+ }
+
+ private class DexInstructionIterator implements InstructionIterator {
private final DexCode code;
private int index;
- InstructionIterator(MethodSubject method) {
+ DexInstructionIterator(MethodSubject method) {
assert method.isPresent();
- this.code = method.getMethod().getCode().asDexCode();
+ Code code = method.getMethod().getCode();
+ assert code != null && code.isDexCode();
+ this.code = code.asDexCode();
this.index = 0;
}
@@ -1571,7 +1435,7 @@
if (index == code.instructions.length) {
throw new NoSuchElementException();
}
- return factory.create(code.instructions[index++]);
+ return createInstructionSubject(code.instructions[index++]);
}
}
@@ -1582,7 +1446,7 @@
private InstructionSubject pendingNext = null;
FilteredInstructionIterator(MethodSubject method, Predicate<InstructionSubject> predicate) {
- this.iterator = new InstructionIterator(method);
+ this.iterator = createInstructionIterator(method);
this.predicate = predicate;
hasNext();
}
