Make Outlining deterministic.
This change ensures that we alway process methods in callgraph order.
Bug:
Change-Id: Id338a58c08df2433ff3068b38842b4d42cffc79c
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 70e156b..48c8eb0 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
@@ -17,15 +17,23 @@
import com.android.tools.r8.ir.code.Invoke;
import com.android.tools.r8.ir.code.Invoke.Type;
import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
+import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.ThreadUtils;
import com.google.common.collect.Sets;
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Future;
+import java.util.function.Consumer;
+import java.util.function.Function;
import java.util.stream.Collectors;
/**
@@ -45,6 +53,10 @@
*/
public class CallGraph {
+ private CallGraph(InternalOptions options) {
+ this.shuffle = options.testing.irOrdering;
+ }
+
private static class Node {
public final DexEncodedMethod method;
@@ -121,6 +133,7 @@
private final Map<DexEncodedMethod, Node> nodes = new LinkedHashMap<>();
private final Map<DexEncodedMethod, Set<DexEncodedMethod>> breakers = new HashMap<>();
+ private final Function<List<DexEncodedMethod>, List<DexEncodedMethod>> shuffle;
// Returns whether the method->callee edge has been removed from the call graph
// to break a cycle in the call graph.
@@ -133,8 +146,8 @@
private Set<DexEncodedMethod> doubleCallSite = Sets.newIdentityHashSet();
public static CallGraph build(DexApplication application, AppInfoWithSubtyping appInfo,
- GraphLense graphLense) {
- CallGraph graph = new CallGraph();
+ GraphLense graphLense, InternalOptions options) {
+ 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));
for (DexClass clazz : classes) {
@@ -185,7 +198,9 @@
private static boolean allMethodsExists(DexApplication application, CallGraph graph) {
for (DexProgramClass clazz : application.classes()) {
- clazz.forEachMethod(method -> { assert graph.nodes.get(method) != null; });
+ clazz.forEachMethod(method -> {
+ assert graph.nodes.get(method) != null;
+ });
}
return true;
}
@@ -197,19 +212,19 @@
* Please note that there are no cycles in this graph (see {@link #breakCycles}).
* <p>
*
- * @return List of {@link DexEncodedMethod}.
+ * @return List of {@link DexEncodedMethod}.
*/
- List<DexEncodedMethod> extractLeaves() {
+ private List<DexEncodedMethod> extractLeaves() {
if (isEmpty()) {
- return null;
+ return Collections.emptyList();
}
// First identify all leaves before removing them from the graph.
List<Node> leaves = nodes.values().stream().filter(Node::isLeaf).collect(Collectors.toList());
- leaves.forEach( leaf -> {
- leaf.callers.forEach( caller -> caller.callees.remove(leaf));
+ leaves.forEach(leaf -> {
+ leaf.callers.forEach(caller -> caller.callees.remove(leaf));
nodes.remove(leaf.method);
});
- return leaves.stream().map( leaf -> leaf.method).collect(Collectors.toList());
+ return shuffle.apply(leaves.stream().map(leaf -> leaf.method).collect(Collectors.toList()));
}
private int traverse(Node node, Set<Node> stack, Set<Node> marked) {
@@ -253,7 +268,7 @@
int numberOfCycles = 0;
Set<Node> stack = Sets.newIdentityHashSet();
Set<Node> marked = Sets.newIdentityHashSet();
- for(Node node : nodes.values()) {
+ for (Node node : nodes.values()) {
numberOfCycles += traverse(node, stack, marked);
}
return numberOfCycles;
@@ -279,6 +294,21 @@
return nodes.size() == 0;
}
+ public void forEachMethod(Consumer<DexEncodedMethod> consumer, ExecutorService executorService)
+ throws ExecutionException {
+ while (!isEmpty()) {
+ List<DexEncodedMethod> methods = extractLeaves();
+ assert methods.size() > 0;
+ List<Future<?>> futures = new ArrayList<>();
+ for (DexEncodedMethod method : methods) {
+ futures.add(executorService.submit(() -> {
+ consumer.accept(method);
+ }));
+ }
+ ThreadUtils.awaitFutures(futures);
+ }
+ }
+
public void dump() {
nodes.forEach((m, n) -> System.out.println(n + "\n"));
}
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 8e613c0..a4bb015 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
@@ -266,7 +266,7 @@
removeLambdaDeserializationMethods();
timing.begin("Build call graph");
- callGraph = CallGraph.build(application, appInfo.withSubtyping(), graphLense);
+ callGraph = CallGraph.build(application, appInfo.withSubtyping(), graphLense, options);
timing.end();
// The process is in two phases.
@@ -278,22 +278,10 @@
// Process the application identifying outlining candidates.
timing.begin("IR conversion phase 1");
OptimizationFeedback directFeedback = new OptimizationFeedbackDirect();
- while (!callGraph.isEmpty()) {
- List<DexEncodedMethod> methods = callGraph.extractLeaves();
- assert methods.size() > 0;
- // For testing we have the option to determine the processing order of the methods.
- if (options.testing.irOrdering != null) {
- methods = options.testing.irOrdering.apply(methods);
- }
- List<Future<?>> futures = new ArrayList<>();
- for (DexEncodedMethod method : methods) {
- futures.add(executorService.submit(() -> {
+ callGraph.forEachMethod(method -> {
processMethod(method, directFeedback,
outliner == null ? Outliner::noProcessing : outliner::identifyCandidates);
- }));
- }
- ThreadUtils.awaitFutures(futures);
- }
+ }, executorService);
timing.end();
// Build a new application with jumbo string info.
@@ -314,13 +302,20 @@
// add the outline support class IF needed.
DexProgramClass outlineClass = prepareOutlining();
if (outlineClass != null) {
- // Process the selected methods for outlining.
- for (DexEncodedMethod method : outliner.getMethodsSelectedForOutlining()) {
+ // We need a new call graph to ensure deterministic order and also processing inside out
+ // to get maximal inlining. Use a identity lense, as the code has been rewritten.
+ callGraph = CallGraph
+ .build(application, appInfo.withSubtyping(), GraphLense.getIdentityLense(), options);
+ Set<DexEncodedMethod> outlineMethods = outliner.getMethodsSelectedForOutlining();
+ callGraph.forEachMethod(method -> {
+ if (!outlineMethods.contains(method)) {
+ return;
+ }
// This is the second time we compile this method first mark it not processed.
assert !method.getCode().isOutlineCode();
processMethod(method, ignoreOptimizationFeedback, outliner::applyOutliningCandidate);
assert method.isProcessed();
- }
+ }, executorService);
builder.addSynthesizedClass(outlineClass, true);
clearDexMethodCompilationState(outlineClass);
}
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 9b5e007..fa5177b 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -142,7 +142,9 @@
}
public static class TestingOptions {
- public Function<List<DexEncodedMethod>, List<DexEncodedMethod>> irOrdering;
+
+ public Function<List<DexEncodedMethod>, List<DexEncodedMethod>> irOrdering
+ = Function.identity();
}
public static class AttributeRemovalOptions {
diff --git a/src/test/java/com/android/tools/r8/maindexlist/MainDexListTests.java b/src/test/java/com/android/tools/r8/maindexlist/MainDexListTests.java
index 714792d..3d59ab9 100644
--- a/src/test/java/com/android/tools/r8/maindexlist/MainDexListTests.java
+++ b/src/test/java/com/android/tools/r8/maindexlist/MainDexListTests.java
@@ -232,7 +232,7 @@
@Test
public void checkDeterminism() throws Exception {
// Synthesize a dex containing a few empty classes including some in the default package.
- // Everything can fit easaly in a single dex file.
+ // Everything can fit easily in a single dex file.
String[] classes = {
"A",
"B",
