Parallelize preprocessing for argument propagation
Change-Id: I3d0de595f438c6bf32fe1aec31c35628e1708d50
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 a1d1e2a..c00f43c 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
@@ -659,7 +659,7 @@
// Setup the argument propagator for the primary optimization pass.
appView.withArgumentPropagator(
- argumentPropagator -> argumentPropagator.initializeCodeScanner(timing));
+ argumentPropagator -> argumentPropagator.initializeCodeScanner(executorService, timing));
appView.withCallSiteOptimizationInfoPropagator(
optimization -> {
optimization.abandonCallSitePropagationForLambdaImplementationMethods(
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagator.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagator.java
index f8edd1e..2173883 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagator.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagator.java
@@ -4,6 +4,8 @@
package com.android.tools.r8.optimize.argumentpropagation;
+import static com.android.tools.r8.optimize.argumentpropagation.utils.StronglyConnectedProgramClasses.computeStronglyConnectedProgramClasses;
+
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexProgramClass;
@@ -18,7 +20,10 @@
import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodStateCollectionByReference;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.VirtualRootMethodsAnalysis;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.ThreadUtils;
import com.android.tools.r8.utils.Timing;
+import java.util.List;
+import java.util.Set;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
@@ -50,7 +55,8 @@
* Called by {@link IRConverter} *before* the primary optimization pass to setup the scanner for
* collecting argument information from the code objects.
*/
- public void initializeCodeScanner(Timing timing) {
+ public void initializeCodeScanner(ExecutorService executorService, Timing timing)
+ throws ExecutionException {
assert !appView.getSyntheticItems().hasPendingSyntheticClasses();
timing.begin("Argument propagator");
@@ -58,20 +64,25 @@
codeScanner = new ArgumentPropagatorCodeScanner(appView);
- // Disable argument propagation for methods that should not be optimized.
ImmediateProgramSubtypingInfo immediateSubtypingInfo =
ImmediateProgramSubtypingInfo.create(appView);
+ List<Set<DexProgramClass>> stronglyConnectedProgramClasses =
+ computeStronglyConnectedProgramClasses(appView, immediateSubtypingInfo);
+ ThreadUtils.processItems(
+ stronglyConnectedProgramClasses,
+ classes -> {
+ // Disable argument propagation for methods that should not be optimized by setting their
+ // method state to unknown.
+ new ArgumentPropagatorUnoptimizableMethods(
+ appView, immediateSubtypingInfo, codeScanner.getMethodStates())
+ .disableArgumentPropagationForUnoptimizableMethods(classes);
- // TODO(b/190154391): Consider computing the strongly connected components and running this in
- // parallel for each scc.
- new ArgumentPropagatorUnoptimizableMethods(
- appView, immediateSubtypingInfo, codeScanner.getMethodStates())
- .disableArgumentPropagationForUnoptimizableMethods(appView.appInfo().classes());
-
- // TODO(b/190154391): Consider computing the strongly connected components and running this in
- // parallel for each scc.
- new VirtualRootMethodsAnalysis(appView, immediateSubtypingInfo)
- .extendVirtualRootMethods(appView.appInfo().classes(), codeScanner);
+ // Compute the mapping from virtual methods to their root virtual method and the set of
+ // monomorphic virtual methods.
+ new VirtualRootMethodsAnalysis(appView, immediateSubtypingInfo)
+ .extendVirtualRootMethods(appView.appInfo().classes(), codeScanner);
+ },
+ executorService);
timing.end();
timing.end();
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorOptimizationInfoPopulator.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorOptimizationInfoPopulator.java
index 4548f35..6d4f3b7 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorOptimizationInfoPopulator.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorOptimizationInfoPopulator.java
@@ -4,6 +4,8 @@
package com.android.tools.r8.optimize.argumentpropagation;
+import static com.android.tools.r8.optimize.argumentpropagation.utils.StronglyConnectedProgramClasses.computeStronglyConnectedProgramClasses;
+
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexProgramClass;
@@ -25,9 +27,6 @@
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.ThreadUtils;
import com.android.tools.r8.utils.Timing;
-import com.android.tools.r8.utils.WorkList;
-import com.google.common.collect.Sets;
-import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ExecutionException;
@@ -56,40 +55,7 @@
ImmediateProgramSubtypingInfo.create(appView);
this.immediateSubtypingInfo = immediateSubtypingInfo;
this.stronglyConnectedComponents =
- computeStronglyConnectedComponents(appView, immediateSubtypingInfo);
- }
-
- /**
- * Computes the strongly connected components in the program class hierarchy (where extends and
- * implements edges are treated as bidirectional).
- *
- * <p>All strongly connected components can be processed in parallel.
- */
- private static List<Set<DexProgramClass>> computeStronglyConnectedComponents(
- AppView<AppInfoWithLiveness> appView, ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
- Set<DexProgramClass> seen = Sets.newIdentityHashSet();
- List<Set<DexProgramClass>> stronglyConnectedComponents = new ArrayList<>();
- for (DexProgramClass clazz : appView.appInfo().classes()) {
- if (seen.contains(clazz)) {
- continue;
- }
- Set<DexProgramClass> stronglyConnectedComponent =
- computeStronglyConnectedComponent(clazz, immediateSubtypingInfo);
- stronglyConnectedComponents.add(stronglyConnectedComponent);
- seen.addAll(stronglyConnectedComponent);
- }
- return stronglyConnectedComponents;
- }
-
- private static Set<DexProgramClass> computeStronglyConnectedComponent(
- DexProgramClass clazz, ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
- WorkList<DexProgramClass> worklist = WorkList.newIdentityWorkList(clazz);
- while (worklist.hasNext()) {
- DexProgramClass current = worklist.next();
- immediateSubtypingInfo.forEachImmediateProgramSuperClass(current, worklist::addIfNotSeen);
- worklist.addIfNotSeen(immediateSubtypingInfo.getSubclasses(current));
- }
- return worklist.getSeenSet();
+ computeStronglyConnectedProgramClasses(appView, immediateSubtypingInfo);
}
/**
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/utils/StronglyConnectedProgramClasses.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/utils/StronglyConnectedProgramClasses.java
new file mode 100644
index 0000000..25d28cb
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/utils/StronglyConnectedProgramClasses.java
@@ -0,0 +1,49 @@
+// Copyright (c) 2021, 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.optimize.argumentpropagation.utils;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.WorkList;
+import com.google.common.collect.Sets;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Set;
+
+public class StronglyConnectedProgramClasses {
+
+ /**
+ * Computes the strongly connected components in the program class hierarchy (where extends and
+ * implements edges are treated as bidirectional).
+ */
+ public static List<Set<DexProgramClass>> computeStronglyConnectedProgramClasses(
+ AppView<AppInfoWithLiveness> appView, ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
+ Set<DexProgramClass> seen = Sets.newIdentityHashSet();
+ List<Set<DexProgramClass>> stronglyConnectedComponents = new ArrayList<>();
+ for (DexProgramClass clazz : appView.appInfo().classes()) {
+ if (seen.contains(clazz)) {
+ continue;
+ }
+ Set<DexProgramClass> stronglyConnectedComponent =
+ internalComputeStronglyConnectedProgramClasses(clazz, immediateSubtypingInfo);
+ stronglyConnectedComponents.add(stronglyConnectedComponent);
+ seen.addAll(stronglyConnectedComponent);
+ }
+ return stronglyConnectedComponents;
+ }
+
+ private static Set<DexProgramClass> internalComputeStronglyConnectedProgramClasses(
+ DexProgramClass clazz, ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
+ WorkList<DexProgramClass> worklist = WorkList.newIdentityWorkList(clazz);
+ while (worklist.hasNext()) {
+ DexProgramClass current = worklist.next();
+ immediateSubtypingInfo.forEachImmediateProgramSuperClass(current, worklist::addIfNotSeen);
+ worklist.addIfNotSeen(immediateSubtypingInfo.getSubclasses(current));
+ }
+ return worklist.getSeenSet();
+ }
+}
