High-level skeleton for new argument propagation
Bug: 190154391
Change-Id: I78b528ff2f546142d2ce788b749ed03821eb4b7e
diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
index b509c1f..225343b 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -28,6 +28,7 @@
import com.android.tools.r8.ir.optimize.info.field.InstanceFieldInitializationInfoFactory;
import com.android.tools.r8.ir.optimize.library.LibraryMemberOptimizer;
import com.android.tools.r8.ir.optimize.library.LibraryMethodSideEffectModelCollection;
+import com.android.tools.r8.optimize.argumentpropagation.ArgumentPropagator;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.shaking.KeepInfoCollection;
import com.android.tools.r8.shaking.LibraryModeledPredicate;
@@ -84,6 +85,7 @@
private final LibraryMethodSideEffectModelCollection libraryMethodSideEffectModelCollection;
// Optimizations.
+ private final ArgumentPropagator argumentPropagator;
private final CallSiteOptimizationInfoPropagator callSiteOptimizationInfoPropagator;
private final LibraryMemberOptimizer libraryMemberOptimizer;
private final ProtoShrinker protoShrinker;
@@ -121,9 +123,16 @@
this.rewritePrefix = mapper;
if (enableWholeProgramOptimizations() && options().callSiteOptimizationOptions().isEnabled()) {
- this.callSiteOptimizationInfoPropagator =
- new CallSiteOptimizationInfoPropagator(withLiveness());
+ if (options().callSiteOptimizationOptions().isExperimentalArgumentPropagationEnabled()) {
+ this.argumentPropagator = new ArgumentPropagator(withLiveness());
+ this.callSiteOptimizationInfoPropagator = null;
+ } else {
+ this.argumentPropagator = null;
+ this.callSiteOptimizationInfoPropagator =
+ new CallSiteOptimizationInfoPropagator(withLiveness());
+ }
} else {
+ this.argumentPropagator = null;
this.callSiteOptimizationInfoPropagator = null;
}
@@ -323,6 +332,13 @@
return callSiteOptimizationInfoPropagator;
}
+ public <E extends Throwable> void withArgumentPropagator(
+ ThrowingConsumer<ArgumentPropagator, E> consumer) throws E {
+ if (argumentPropagator != null) {
+ consumer.accept(argumentPropagator);
+ }
+ }
+
public <E extends Throwable> void withCallSiteOptimizationInfoPropagator(
ThrowingConsumer<CallSiteOptimizationInfoPropagator, E> consumer) throws E {
if (callSiteOptimizationInfoPropagator != null) {
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 b6e8153..4177124 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
@@ -98,6 +98,7 @@
import com.android.tools.r8.ir.regalloc.RegisterAllocator;
import com.android.tools.r8.logging.Log;
import com.android.tools.r8.naming.IdentifierNameStringMarker;
+import com.android.tools.r8.optimize.argumentpropagation.ArgumentPropagator;
import com.android.tools.r8.position.MethodPosition;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.shaking.LibraryMethodOverrideAnalysis;
@@ -678,6 +679,8 @@
printPhase("Primary optimization pass");
+ // Setup the argument propagator for the primary optimization pass.
+ appView.withArgumentPropagator(ArgumentPropagator::initializeCodeScanner);
appView.withCallSiteOptimizationInfoPropagator(
optimization -> {
optimization.abandonCallSitePropagationForLambdaImplementationMethods(
@@ -723,11 +726,20 @@
// Assure that no more optimization feedback left after primary processing.
assert feedback.noUpdatesLeft();
appView.setAllCodeProcessed();
+
// All the code has been processed so the rewriting required by the lenses is done everywhere,
// we clear lens code rewriting so that the lens rewriter can be re-executed in phase 2 if new
// lenses with code rewriting are added.
appView.clearCodeRewritings();
+ // Analyze the data collected by the argument propagator, use the analysis result to update
+ // the parameter optimization infos, and rewrite the application.
+ appView.withArgumentPropagator(
+ argumentPropagator -> {
+ argumentPropagator.populateParameterOptimizationInfo();
+ argumentPropagator.optimizeMethodParameters(postMethodProcessorBuilder);
+ });
+
if (libraryMethodOverrideAnalysis != null) {
libraryMethodOverrideAnalysis.finish();
}
@@ -1612,6 +1624,8 @@
MethodProcessor methodProcessor,
MutableMethodConversionOptions conversionOptions,
Timing timing) {
+ appView.withArgumentPropagator(
+ argumentPropagator -> argumentPropagator.scan(method, code, methodProcessor));
if (enumUnboxer != null && methodProcessor.isPrimaryMethodProcessor()) {
enumUnboxer.analyzeEnums(code, conversionOptions);
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
new file mode 100644
index 0000000..d7f5e52
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagator.java
@@ -0,0 +1,79 @@
+// 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;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.conversion.IRConverter;
+import com.android.tools.r8.ir.conversion.MethodProcessor;
+import com.android.tools.r8.ir.conversion.PostMethodProcessor;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+
+/** Optimization that propagates information about arguments from call sites to method entries. */
+public class ArgumentPropagator {
+
+ private final AppView<AppInfoWithLiveness> appView;
+
+ /**
+ * Collects information about arguments from call sites, meanwhile pruning redundant information.
+ *
+ * <p>The data held by this instance is incomplete and should not be used for optimization until
+ * processed by {@link ArgumentPropagatorOptimizationInfoPopulator}.
+ */
+ private ArgumentPropagatorCodeScanner codeScanner;
+
+ public ArgumentPropagator(AppView<AppInfoWithLiveness> appView) {
+ assert appView.enableWholeProgramOptimizations();
+ assert appView.options().isOptimizing();
+ assert appView.options().callSiteOptimizationOptions().isEnabled();
+ assert appView
+ .options()
+ .callSiteOptimizationOptions()
+ .isExperimentalArgumentPropagationEnabled();
+ this.appView = appView;
+ }
+
+ /**
+ * Called by {@link IRConverter} *before* the primary optimization pass to setup the scanner for
+ * collecting argument information from the code objects.
+ */
+ public void initializeCodeScanner() {
+ codeScanner = new ArgumentPropagatorCodeScanner(appView);
+ }
+
+ /** Called by {@link IRConverter} prior to finalizing methods. */
+ public void scan(ProgramMethod method, IRCode code, MethodProcessor methodProcessor) {
+ if (codeScanner != null) {
+ // TODO(b/190154391): Do we process synthetic methods using a OneTimeMethodProcessor
+ // during the primary optimization pass?
+ assert methodProcessor.isPrimaryMethodProcessor();
+ codeScanner.scan(method, code);
+ } else {
+ assert !methodProcessor.isPrimaryMethodProcessor();
+ }
+ }
+
+ /**
+ * Called by {@link IRConverter} *after* the primary optimization pass to populate the parameter
+ * optimization info.
+ */
+ public void populateParameterOptimizationInfo() {
+ assert appView.isAllCodeProcessed();
+ new ArgumentPropagatorOptimizationInfoPopulator()
+ .populateOptimizationInfo(codeScanner.getResult());
+ codeScanner = null;
+ }
+
+ /**
+ * Called by {@link IRConverter} to optimize method definitions. This also adds all methods that
+ * require reprocessing to {@param postMethodProcessorBuilder}.
+ */
+ public void optimizeMethodParameters(PostMethodProcessor.Builder postMethodProcessorBuilder) {
+ // TODO(b/190154391): Remove parameters with constant values.
+ // TODO(b/190154391): Remove unused parameters by simulating they are constant.
+ // TODO(b/190154391): Strengthen the static type of parameters.
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorCodeScanner.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorCodeScanner.java
new file mode 100644
index 0000000..7cb1c98
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorCodeScanner.java
@@ -0,0 +1,64 @@
+// 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;
+
+import com.android.tools.r8.errors.Unimplemented;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Analyzes each {@link IRCode} during the primary optimization to collect information about the
+ * arguments passed to method parameters.
+ *
+ * <p>State pruning is applied on-the-fly to avoid storing redundant information.
+ */
+class ArgumentPropagatorCodeScanner {
+
+ private final AppView<AppInfoWithLiveness> appView;
+
+ /**
+ * Maps each non-interface method to the upper most method in the super class chain with the same
+ * method signature. This only contains an entry for non-private virtual methods that override
+ * another method in the program.
+ */
+ private final Map<DexMethod, DexMethod> classMethodRoots;
+
+ /**
+ * The methods that are not subject to argument propagation. This includes (i) methods that are
+ * not subject to optimization due to -keep rules, (ii) classpath/library method overrides, and
+ * (iii) methods that are unlikely to benefit from argument propagation according to heuristics.
+ *
+ * <p>Argument propagation must also be disabled for lambda implementation methods unless we model
+ * the calls from lambda main methods synthesized by the JVM.
+ */
+ private final Set<DexMethod> unoptimizableMethods;
+
+ ArgumentPropagatorCodeScanner(AppView<AppInfoWithLiveness> appView) {
+ this.appView = appView;
+ this.classMethodRoots = computeClassMethodRoots();
+ this.unoptimizableMethods = computeUnoptimizableMethods();
+ }
+
+ private Map<DexMethod, DexMethod> computeClassMethodRoots() {
+ throw new Unimplemented();
+ }
+
+ private Set<DexMethod> computeUnoptimizableMethods() {
+ throw new Unimplemented();
+ }
+
+ ArgumentPropagatorCodeScannerResult getResult() {
+ throw new Unimplemented();
+ }
+
+ void scan(ProgramMethod method, IRCode code) {
+ throw new Unimplemented();
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorCodeScannerResult.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorCodeScannerResult.java
new file mode 100644
index 0000000..4143bfb
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorCodeScannerResult.java
@@ -0,0 +1,7 @@
+// 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;
+
+public class ArgumentPropagatorCodeScannerResult {}
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
new file mode 100644
index 0000000..d116411
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorOptimizationInfoPopulator.java
@@ -0,0 +1,28 @@
+// 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;
+
+import com.android.tools.r8.errors.Unimplemented;
+
+/**
+ * Propagates the argument flow information collected by the {@link ArgumentPropagatorCodeScanner}.
+ * This is needed to propagate argument information from call sites to all possible dispatch
+ * targets.
+ */
+public class ArgumentPropagatorOptimizationInfoPopulator {
+
+ /**
+ * Computes an over-approximation of each parameter's value and type and stores the result in
+ * {@link com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo}.
+ */
+ void populateOptimizationInfo(ArgumentPropagatorCodeScannerResult codeScannerResult) {
+ // TODO(b/190154391): Propagate argument information to handle virtual dispatch.
+ // TODO(b/190154391): To deal with arguments that are themselves passed as arguments to invoke
+ // instructions, build a flow graph where nodes are parameters and there is an edge from a
+ // parameter p1 to p2 if the value of p2 is at least the value of p1. Then propagate the
+ // collected argument information throughout the flow graph.
+ throw new Unimplemented();
+ }
+}
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 0a9c18a..5b57a6e 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -1247,6 +1247,10 @@
return enableConstantPropagation || enableTypePropagation;
}
+ public boolean isExperimentalArgumentPropagationEnabled() {
+ return false;
+ }
+
public boolean isConstantPropagationEnabled() {
return enableConstantPropagation;
}
