Parallelize call graph construction
Change-Id: Id6ad17de6ebea2dd0402282b776e85de4e5e7442
diff --git a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
index 945b58b..f8d5d07 100644
--- a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
@@ -238,10 +238,16 @@
this.kotlinInfo = kotlinInfo;
}
+ public boolean hasFields() {
+ return instanceFields.length + staticFields.length > 0;
+ }
+
+ public boolean hasMethods() {
+ return directMethods.length + virtualMethods.length > 0;
+ }
+
public boolean hasMethodsOrFields() {
- int numberOfFields = staticFields().size() + instanceFields().size();
- int numberOfMethods = directMethods().size() + virtualMethods().size();
- return numberOfFields + numberOfMethods > 0;
+ return hasMethods() || hasFields();
}
public boolean hasAnnotations() {
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 767f0b2..e03f33c 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
@@ -15,12 +15,12 @@
import com.android.tools.r8.utils.ThrowingBiConsumer;
import com.google.common.collect.Sets;
import java.util.ArrayList;
-import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
+import java.util.TreeSet;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;
@@ -52,23 +52,29 @@
private int numberOfCallSites = 0;
// Outgoing calls from this method.
- private final Set<Node> callees = new LinkedHashSet<>();
+ private final Set<Node> callees = new TreeSet<>();
// Incoming calls to this method.
- private final Set<Node> callers = new LinkedHashSet<>();
+ private final Set<Node> callers = new TreeSet<>();
public Node(DexEncodedMethod method) {
this.method = method;
}
- public boolean isBridge() {
- return method.accessFlags.isBridge();
- }
-
- public void addCaller(Node caller) {
- callers.add(caller);
- caller.callees.add(this);
- numberOfCallSites++;
+ public void addCallerConcurrently(Node caller) {
+ if (caller != this) {
+ synchronized (callers) {
+ callers.add(caller);
+ numberOfCallSites++;
+ }
+ synchronized (caller.callees) {
+ caller.callees.add(this);
+ }
+ } else {
+ synchronized (callers) {
+ numberOfCallSites++;
+ }
+ }
}
public void removeCaller(Node caller) {
@@ -77,9 +83,7 @@
}
public Node[] getCalleesWithDeterministicOrder() {
- Node[] sorted = callees.toArray(Node.EMPTY_ARRAY);
- Arrays.sort(sorted);
- return sorted;
+ return callees.toArray(Node.EMPTY_ARRAY);
}
public boolean hasCallee(Node method) {
@@ -109,9 +113,6 @@
builder.append(" callees, ");
builder.append(callers.size());
builder.append(" callers");
- if (isBridge()) {
- builder.append(", bridge");
- }
builder.append(", invoke count ").append(numberOfCallSites);
builder.append(").\n");
if (callees.size() > 0) {
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 a19bf3c..15aefa7 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
@@ -16,10 +16,12 @@
import com.android.tools.r8.graph.GraphLense.GraphLenseLookupResult;
import com.android.tools.r8.graph.UseRegistry;
import com.android.tools.r8.ir.code.Invoke;
+import com.android.tools.r8.ir.code.Invoke.Type;
import com.android.tools.r8.ir.conversion.CallGraph.Node;
import com.android.tools.r8.logging.Log;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.ThreadUtils;
import com.android.tools.r8.utils.Timing;
import com.google.common.collect.Sets;
import java.util.ArrayDeque;
@@ -34,6 +36,9 @@
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;
public class CallGraphBuilder {
@@ -44,26 +49,36 @@
this.appView = appView;
}
- public CallGraph build(Timing timing) {
- for (DexProgramClass clazz : appView.appInfo().classesWithDeterministicOrder()) {
- processClass(clazz);
+ public CallGraph build(ExecutorService executorService, Timing timing) throws ExecutionException {
+ List<Future<?>> futures = new ArrayList<>();
+ for (DexProgramClass clazz : appView.appInfo().classes()) {
+ if (clazz.hasMethods()) {
+ futures.add(
+ executorService.submit(
+ () -> {
+ processClass(clazz);
+ return null; // we want a Callable not a Runnable to be able to throw
+ }));
+ }
}
+ ThreadUtils.awaitFutures(futures);
assert verifyAllMethodsWithCodeExists();
timing.begin("Cycle elimination");
- CycleEliminator cycleEliminator = new CycleEliminator(nodes.values(), appView.options());
+ // Sort the nodes for deterministic cycle elimination.
+ Set<Node> nodesWithDeterministicOrder = Sets.newTreeSet(nodes.values());
+ CycleEliminator cycleEliminator =
+ new CycleEliminator(nodesWithDeterministicOrder, appView.options());
cycleEliminator.breakCycles();
timing.end();
assert cycleEliminator.breakCycles() == 0; // This time the cycles should be gone.
- return new CallGraph(appView, Sets.newHashSet(nodes.values()));
+ return new CallGraph(appView, nodesWithDeterministicOrder);
}
private void processClass(DexProgramClass clazz) {
- for (DexEncodedMethod method : clazz.allMethodsSorted()) {
- processMethod(method);
- }
+ clazz.forEachMethod(this::processMethod);
}
private void processMethod(DexEncodedMethod method) {
@@ -73,7 +88,9 @@
}
private Node getOrCreateNode(DexEncodedMethod method) {
- return nodes.computeIfAbsent(method.method, ignore -> new Node(method));
+ synchronized (nodes) {
+ return nodes.computeIfAbsent(method.method, ignore -> new Node(method));
+ }
}
private boolean verifyAllMethodsWithCodeExists() {
@@ -111,7 +128,7 @@
private void addTarget(DexEncodedMethod callee) {
if (!callee.accessFlags.isAbstract()) {
- getOrCreateNode(callee).addCaller(caller);
+ getOrCreateNode(callee).addCallerConcurrently(caller);
}
}
@@ -131,7 +148,7 @@
}
}
- private void processInvoke(Invoke.Type type, DexMethod method) {
+ private void processInvoke(Type type, DexMethod method) {
DexEncodedMethod source = caller.method;
GraphLenseLookupResult result =
appView.graphLense().lookupMethod(method, source.method, type);
@@ -176,31 +193,31 @@
@Override
public boolean registerInvokeVirtual(DexMethod method) {
- processInvoke(Invoke.Type.VIRTUAL, method);
+ processInvoke(Type.VIRTUAL, method);
return false;
}
@Override
public boolean registerInvokeDirect(DexMethod method) {
- processInvoke(Invoke.Type.DIRECT, method);
+ processInvoke(Type.DIRECT, method);
return false;
}
@Override
public boolean registerInvokeStatic(DexMethod method) {
- processInvoke(Invoke.Type.STATIC, method);
+ processInvoke(Type.STATIC, method);
return false;
}
@Override
public boolean registerInvokeInterface(DexMethod method) {
- processInvoke(Invoke.Type.INTERFACE, method);
+ processInvoke(Type.INTERFACE, method);
return false;
}
@Override
public boolean registerInvokeSuper(DexMethod method) {
- processInvoke(Invoke.Type.SUPER, method);
+ processInvoke(Type.SUPER, method);
return false;
}
@@ -311,8 +328,8 @@
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.
+ // 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();
if (options.testing.nondeterministicCycleElimination) {
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 e617152..9775546 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
@@ -510,7 +510,8 @@
OptimizationFeedbackDelayed feedback = delayedOptimizationFeedback;
{
timing.begin("Build call graph");
- CallGraph callGraph = CallGraph.builder(appView.withLiveness()).build(timing);
+ CallGraph callGraph =
+ CallGraph.builder(appView.withLiveness()).build(executorService, timing);
timing.end();
timing.begin("IR conversion phase 1");
BiConsumer<IRCode, DexEncodedMethod> outlineHandler =
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
index accc3e5..5e15f69 100644
--- a/src/test/java/com/android/tools/r8/ir/callgraph/CycleEliminationTest.java
+++ b/src/test/java/com/android/tools/r8/ir/callgraph/CycleEliminationTest.java
@@ -57,8 +57,8 @@
for (Collection<Node> nodes : orderings) {
// Create a cycle between the two nodes.
- forceInlinedMethod.addCaller(method);
- method.addCaller(forceInlinedMethod);
+ forceInlinedMethod.addCallerConcurrently(method);
+ method.addCallerConcurrently(forceInlinedMethod);
// Check that the cycle eliminator finds the cycle.
CycleEliminator cycleEliminator = new CycleEliminator(nodes, new InternalOptions());
@@ -79,8 +79,8 @@
Node forceInlinedMethod = createForceInlinedNode("n2");
// Create a cycle between the two nodes.
- forceInlinedMethod.addCaller(method);
- method.addCaller(forceInlinedMethod);
+ forceInlinedMethod.addCallerConcurrently(method);
+ method.addCallerConcurrently(forceInlinedMethod);
CycleEliminator cycleEliminator =
new CycleEliminator(ImmutableList.of(method, forceInlinedMethod), new InternalOptions());
@@ -160,12 +160,12 @@
for (Configuration configuration : configurations) {
// Create a cycle between the three nodes.
- n2.addCaller(n1);
- n3.addCaller(n2);
- n1.addCaller(n3);
+ n2.addCallerConcurrently(n1);
+ n3.addCallerConcurrently(n2);
+ n1.addCallerConcurrently(n3);
// Create a cycle in the graph between node n1 and n2.
- n1.addCaller(n2);
+ n1.addCallerConcurrently(n2);
for (Node node : configuration.nodes) {
if (configuration.forceInline.contains(node)) {
