Support abstract computation trees in flow propagation
Change-Id: Iea3af64e2fdff18a256594489b88f06559a9ec58
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 b742d92..9f3483e 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -534,7 +534,6 @@
}
public ComposeReferences getComposeReferences() {
- assert options().getJetpackComposeOptions().isAnyOptimizationsEnabled();
if (composeReferences == null) {
composeReferences = new ComposeReferences(dexItemFactory());
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/path/state/ConcretePathConstraintAnalysisState.java b/src/main/java/com/android/tools/r8/ir/analysis/path/state/ConcretePathConstraintAnalysisState.java
index 7bcb650..28bdcf1 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/path/state/ConcretePathConstraintAnalysisState.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/path/state/ConcretePathConstraintAnalysisState.java
@@ -4,6 +4,7 @@
package com.android.tools.r8.ir.analysis.path.state;
import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.ir.analysis.value.AbstractValue;
import com.android.tools.r8.optimize.argumentpropagation.computation.ComputationTreeNode;
import java.util.Collections;
import java.util.HashMap;
@@ -62,26 +63,22 @@
@Override
public PathConstraintAnalysisState add(ComputationTreeNode pathConstraint, boolean negate) {
PathConstraintKind previousKind = pathConstraints.get(pathConstraint);
+ PathConstraintKind newKind;
if (previousKind != null) {
- if (previousKind == PathConstraintKind.DISABLED) {
- // There is a loop.
+ // There is a loop.
+ newKind = PathConstraintKind.DISABLED;
+ if (previousKind == newKind) {
return this;
}
- if (previousKind == PathConstraintKind.get(negate)) {
- // This branch is dominated by a previous if-condition that has the same branch condition,
- // e.g., if (x) { if (x) { ...
- return this;
- }
- // This branch is dominated by a previous if-condition that has the negated branch condition,
- // e.g., if (x) { if (!x) { ...
- return bottom();
+ } else {
+ newKind = PathConstraintKind.get(negate);
}
// No jumps can dominate the entry of their own block, so when adding the condition of a jump
// this cannot currently be active.
Map<ComputationTreeNode, PathConstraintKind> newPathConstraints =
new HashMap<>(pathConstraints.size() + 1);
newPathConstraints.putAll(pathConstraints);
- newPathConstraints.put(pathConstraint, PathConstraintKind.get(negate));
+ newPathConstraints.put(pathConstraint, newKind);
return new ConcretePathConstraintAnalysisState(newPathConstraints);
}
@@ -153,7 +150,7 @@
return pathConstraint;
}
}
- return null;
+ return AbstractValue.unknown();
}
public ConcretePathConstraintAnalysisState join(ConcretePathConstraintAnalysisState other) {
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/path/state/PathConstraintKind.java b/src/main/java/com/android/tools/r8/ir/analysis/path/state/PathConstraintKind.java
index 4e97d27..6891163 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/path/state/PathConstraintKind.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/path/state/PathConstraintKind.java
@@ -24,6 +24,9 @@
}
PathConstraintKind join(PathConstraintKind other) {
+ if (other == null) {
+ return this;
+ }
return this == other ? this : DISABLED;
}
}
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
index d3acc96..4f4cbfe 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorCodeScanner.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorCodeScanner.java
@@ -13,6 +13,7 @@
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
import com.android.tools.r8.graph.ProgramField;
+import com.android.tools.r8.graph.ProgramMember;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.ir.analysis.path.PathConstraintSupplier;
import com.android.tools.r8.ir.analysis.path.state.ConcretePathConstraintAnalysisState;
@@ -26,7 +27,6 @@
import com.android.tools.r8.ir.code.AbstractValueSupplier;
import com.android.tools.r8.ir.code.AliasedValueConfiguration;
import com.android.tools.r8.ir.code.AssumeAndCheckCastAliasedValueConfiguration;
-import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.CheckCast;
import com.android.tools.r8.ir.code.FieldGet;
import com.android.tools.r8.ir.code.FieldPut;
@@ -65,6 +65,7 @@
import com.android.tools.r8.optimize.argumentpropagation.codescanner.StateCloner;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.UnknownMethodState;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.ValueState;
+import com.android.tools.r8.optimize.argumentpropagation.computation.ComposableComputationTreeBuilder;
import com.android.tools.r8.optimize.argumentpropagation.computation.ComputationTreeNode;
import com.android.tools.r8.optimize.argumentpropagation.reprocessingcriteria.ArgumentPropagatorReprocessingCriteriaCollection;
import com.android.tools.r8.optimize.argumentpropagation.reprocessingcriteria.MethodReprocessingCriteria;
@@ -76,10 +77,9 @@
import com.android.tools.r8.utils.DeterminismChecker.LineCallback;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.Timing;
+import com.android.tools.r8.utils.TraversalUtils;
import com.android.tools.r8.utils.structural.StructuralItem;
import com.google.common.collect.Sets;
-import it.unimi.dsi.fastutil.objects.Object2IntMap;
-import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
@@ -241,8 +241,6 @@
protected final ProgramMethod context;
private final PathConstraintSupplier pathConstraintSupplier;
- private Object2IntMap<Phi> phiNumbering = null;
-
protected CodeScanner(
AbstractValueSupplier abstractValueSupplier,
IRCode code,
@@ -319,6 +317,7 @@
NonEmptyValueState inFlowState =
computeInFlowState(
field.getType(),
+ field,
value,
initialValue,
context,
@@ -379,6 +378,7 @@
// TODO(b/302281503): Canonicalize computed in flow.
private InFlow computeInFlow(
DexType staticType,
+ ProgramMember<?, ?> target,
Value value,
Value initialValue,
ProgramMethod context,
@@ -410,16 +410,23 @@
return castBaseInFlow(
widenBaseInFlow(staticType, fieldValueFactory.create(field), context), value);
} else if (value.isPhi()) {
+ // TODO(b/302281503): Replace IfThenElseAbstractFunction by ComputationTreeNode (?).
return computeIfThenElseAbstractFunction(value.asPhi(), valueStateSupplier);
+ } else if (target != null && appView.getComposeReferences().isComposable(target)) {
+ ComputationTreeNode node =
+ new ComposableComputationTreeBuilder(
+ appView, code, code.context(), methodParameterFactory, pathConstraintSupplier)
+ .getOrBuildComputationTree(value);
+ if (!node.isComputationLeaf() && TraversalUtils.hasNext(node::traverseBaseInFlow)) {
+ recordComputationTreePosition(node, value);
+ return node;
+ }
}
return null;
}
private IfThenElseAbstractFunction computeIfThenElseAbstractFunction(
Phi phi, Function<Value, NonEmptyValueState> valueStateSupplier) {
- if (!appView.testing().enableIfThenElseAbstractFunction) {
- return null;
- }
if (phi.getOperands().size() != 2 || !phi.hasOperandThatMatches(Value::isArgument)) {
return null;
}
@@ -437,11 +444,14 @@
ComputationTreeNode condition =
leftPredecessorPathConstraint.getDifferentiatingPathConstraint(
rightPredecessorPathConstraint);
- if (condition == null || condition.getSingleOpenVariable() == null) {
+ if (condition.getSingleOpenVariable() == null) {
return null;
}
NonEmptyValueState leftValue = valueStateSupplier.apply(phi.getOperand(0));
NonEmptyValueState rightValue = valueStateSupplier.apply(phi.getOperand(1));
+ if (leftValue.isUnknown() && rightValue.isUnknown()) {
+ return null;
+ }
IfThenElseAbstractFunction result =
leftPredecessorPathConstraint.isNegated(condition)
? new IfThenElseAbstractFunction(condition, rightValue, leftValue)
@@ -450,28 +460,25 @@
return result;
}
+ private void recordComputationTreePosition(ComputationTreeNode computation, Value value) {
+ inFlowComparatorBuilder.addComputationTreePosition(
+ computation,
+ SourcePosition.builder()
+ .setMethod(code.context().getReference())
+ .setLine(value.getNumber())
+ .build());
+ }
+
private void recordIfThenElsePosition(
IfThenElseAbstractFunction ifThenElseAbstractFunction, Phi phi) {
inFlowComparatorBuilder.addIfThenElsePosition(
ifThenElseAbstractFunction,
SourcePosition.builder()
.setMethod(code.context().getReference())
- .setLine(getOrCreatePhiNumbering().getInt(phi))
+ .setLine(phi.getNumber())
.build());
}
- private Object2IntMap<Phi> getOrCreatePhiNumbering() {
- if (phiNumbering == null) {
- phiNumbering = new Object2IntOpenHashMap<>();
- for (BasicBlock block : code.getBlocks()) {
- for (Phi phi : block.getPhis()) {
- phiNumbering.put(phi, phiNumbering.size());
- }
- }
- }
- return phiNumbering;
- }
-
private InFlow castBaseInFlow(InFlow inFlow, Value value) {
if (inFlow.isUnknown()) {
return inFlow;
@@ -501,12 +508,14 @@
private NonEmptyValueState computeInFlowState(
DexType staticType,
+ ProgramMember<?, ?> target,
Value value,
Value initialValue,
ProgramMethod context,
Function<Value, NonEmptyValueState> valueStateSupplier) {
assert value == initialValue || initialValue.getAliasedValue().isPhi();
- InFlow inFlow = computeInFlow(staticType, value, initialValue, context, valueStateSupplier);
+ InFlow inFlow =
+ computeInFlow(staticType, target, value, initialValue, context, valueStateSupplier);
if (inFlow == null) {
return null;
}
@@ -514,6 +523,7 @@
return ValueState.unknown();
}
assert inFlow.isBaseInFlow()
+ || inFlow.isAbstractComputation()
|| inFlow.isCastAbstractFunction()
|| inFlow.isIfThenElseAbstractFunction()
|| inFlow.isInstanceFieldReadAbstractFunction();
@@ -859,6 +869,7 @@
Value value,
Value initialValue,
ConcreteMonomorphicMethodStateOrBottom existingMethodState) {
+ assert invoke.isInvokeStatic() || argumentIndex > 0;
assert value == initialValue || initialValue.getAliasedValue().isPhi();
NonEmptyValueState modeledState =
modeling.modelParameterStateForArgumentToFunction(
@@ -884,6 +895,7 @@
NonEmptyValueState inFlowState =
computeInFlowState(
parameterType,
+ singleTarget,
value,
initialValue,
context,
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/BottomClassTypeValueState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/BottomClassTypeValueState.java
index 6eca904..478ec19 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/BottomClassTypeValueState.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/BottomClassTypeValueState.java
@@ -60,7 +60,6 @@
if (outStaticType != null) {
return WideningUtils.widenDynamicNonReceiverType(appView, joinedDynamicType, outStaticType);
} else {
- assert !joinedDynamicType.isUnknown();
return joinedDynamicType;
}
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/FlowGraphStateProvider.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/FlowGraphStateProvider.java
index 0d0be90..6d1dc8f 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/FlowGraphStateProvider.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/FlowGraphStateProvider.java
@@ -18,7 +18,8 @@
// If the abstract function needs to perform state lookups, we restrict state lookups to the
// declared base in flow. This is important for arriving at the correct fix point.
if (abstractFunction.usesFlowGraphStateProvider()) {
- assert abstractFunction.isIfThenElseAbstractFunction()
+ assert abstractFunction.isAbstractComputation()
+ || abstractFunction.isIfThenElseAbstractFunction()
|| abstractFunction.isInstanceFieldReadAbstractFunction();
return new FlowGraphStateProvider() {
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/IfThenElseAbstractFunction.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/IfThenElseAbstractFunction.java
index e8a04d9..dc1354f 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/IfThenElseAbstractFunction.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/IfThenElseAbstractFunction.java
@@ -21,6 +21,7 @@
* true, then `u` is chosen. If the abstract value is false, then `v` is chosen. Otherwise, the
* result is unknown.
*/
+// TODO(b/302281503): Replace this by a ComputationTreeNode.
// TODO(b/302281503): Evaluate the impact of using the join of `u` and `v` instead of unknown when
// the condition does not evaluate to true or false.
public class IfThenElseAbstractFunction implements AbstractFunction {
@@ -74,7 +75,6 @@
if (variableState == null) {
// TODO(b/302281503): Conservatively return unknown for now. Investigate exactly when this
// happens and whether we can return something more precise instead of unknown.
- assert false;
return AbstractValue.unknown();
}
AbstractValue variableValue = variableState.getAbstractValue(appView);
@@ -95,7 +95,6 @@
assert inFlow.isBaseInFlow();
ValueState inFlowState = flowGraphStateProvider.getState(inFlow.asBaseInFlow(), () -> null);
if (inFlowState == null) {
- assert false;
return ValueState.unknown();
}
// TODO(b/302281503): The IfThenElseAbstractFunction is only used on input to base in flow.
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/computation/ComputationTreeLogicalBinopAndNode.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/computation/ComputationTreeLogicalBinopAndNode.java
index 5bddb75..e31a8cd 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/computation/ComputationTreeLogicalBinopAndNode.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/computation/ComputationTreeLogicalBinopAndNode.java
@@ -30,7 +30,13 @@
Function<MethodParameter, AbstractValue> argumentAssignment) {
assert getNumericType().isInt();
AbstractValue leftValue = left.evaluate(appView, argumentAssignment);
+ if (leftValue.isBottom()) {
+ return leftValue;
+ }
AbstractValue rightValue = right.evaluate(appView, argumentAssignment);
+ if (rightValue.isBottom()) {
+ return rightValue;
+ }
return AbstractCalculator.andIntegers(appView, leftValue, rightValue);
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/computation/ComputationTreeNode.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/computation/ComputationTreeNode.java
index 9976148..c287cb1 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/computation/ComputationTreeNode.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/computation/ComputationTreeNode.java
@@ -81,6 +81,11 @@
boolean isComputationLeaf();
+ @Override
+ default boolean usesFlowGraphStateProvider() {
+ return true;
+ }
+
default String toStringWithParenthesis() {
if (isComputationLeaf()) {
return toString();
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/computation/ComputationTreeUnopCompareNode.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/computation/ComputationTreeUnopCompareNode.java
index 0b96bed..03559c9 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/computation/ComputationTreeUnopCompareNode.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/computation/ComputationTreeUnopCompareNode.java
@@ -34,6 +34,9 @@
AppView<AppInfoWithLiveness> appView,
Function<MethodParameter, AbstractValue> argumentAssignment) {
AbstractValue operandValue = operand.evaluate(appView, argumentAssignment);
+ if (operandValue.isBottom()) {
+ return operandValue;
+ }
return type.evaluate(operandValue, appView);
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsAnalysis.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsAnalysis.java
index 860f3d4..6e82b3b 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsAnalysis.java
@@ -235,7 +235,7 @@
// Find a condition that can be used to distinguish program paths coming from the two
// predecessors.
ComputationTreeNode condition = leftState.getDifferentiatingPathConstraint(rightState);
- if (condition == null || !condition.isArgumentBitSetCompareNode()) {
+ if (!condition.isArgumentBitSetCompareNode()) {
return false;
}
// Extract the state corresponding to the program path where the argument is unused. If the
diff --git a/src/main/java/com/android/tools/r8/optimize/compose/ComposeReferences.java b/src/main/java/com/android/tools/r8/optimize/compose/ComposeReferences.java
index e38f9a4..633008d 100644
--- a/src/main/java/com/android/tools/r8/optimize/compose/ComposeReferences.java
+++ b/src/main/java/com/android/tools/r8/optimize/compose/ComposeReferences.java
@@ -7,6 +7,7 @@
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.ProgramDefinition;
import com.android.tools.r8.graph.lens.GraphLens;
public class ComposeReferences {
@@ -42,6 +43,11 @@
this.updatedChangedFlagsMethod = updatedChangedFlagsMethod;
}
+ public boolean isComposable(ProgramDefinition definition) {
+ return definition.isProgramMethod()
+ && definition.asProgramMethod().getAnnotations().hasAnnotation(composableType);
+ }
+
public ComposeReferences rewrittenWithLens(GraphLens graphLens, GraphLens codeLens) {
return new ComposeReferences(
changedFieldName,
diff --git a/src/main/java/com/android/tools/r8/optimize/compose/UpdateChangedFlagsAbstractFunction.java b/src/main/java/com/android/tools/r8/optimize/compose/UpdateChangedFlagsAbstractFunction.java
index a353fa1..f7f9bba 100644
--- a/src/main/java/com/android/tools/r8/optimize/compose/UpdateChangedFlagsAbstractFunction.java
+++ b/src/main/java/com/android/tools/r8/optimize/compose/UpdateChangedFlagsAbstractFunction.java
@@ -24,6 +24,7 @@
import java.util.Objects;
import java.util.function.Function;
+// TODO(b/302281503): Change this to implement ComputationTreeNode instead?
public class UpdateChangedFlagsAbstractFunction implements AbstractFunction {
private static final int changedLowBitMask = 0b001_001_001_001_001_001_001_001_001_001_0;
diff --git a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
index bcfa888..0e2508f 100644
--- a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
@@ -142,7 +142,7 @@
.startsWith(options.itemFactory.dalvikAnnotationOptimizationPrefix)) {
return true;
}
- if (isComposableAnnotationToRetain(appView, annotation, kind, mode, options)) {
+ if (isComposableAnnotationToRetain(appView, annotation, kind, mode)) {
return true;
}
return shouldKeepNormalAnnotation(
@@ -309,13 +309,8 @@
}
private static boolean isComposableAnnotationToRetain(
- AppView<?> appView,
- DexAnnotation annotation,
- AnnotatedKind kind,
- Mode mode,
- InternalOptions options) {
- return options.getJetpackComposeOptions().isAnyOptimizationsEnabled()
- && mode.isInitialTreeShaking()
+ AppView<?> appView, DexAnnotation annotation, AnnotatedKind kind, Mode mode) {
+ return mode.isInitialTreeShaking()
&& kind.isMethod()
&& annotation
.getAnnotationType()
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 8abdba1..9f433ec 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -2461,7 +2461,6 @@
public boolean enableDeadSwitchCaseElimination = true;
public boolean enableEnqueuerDeferredTracingForReferenceFields =
System.getProperty("com.android.tools.r8.disableEnqueuerDeferredTracing") == null;
- public boolean enableIfThenElseAbstractFunction = false;
public boolean enableInvokeSuperToInvokeVirtualRewriting = true;
public boolean enableLegacyClassDefOrdering =
System.getProperty("com.android.tools.r8.enableLegacyClassDefOrdering") != null;
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/callsites/RestartLambdaPropagationWithDefaultArgumentTest.java b/src/test/java/com/android/tools/r8/ir/optimize/callsites/RestartLambdaPropagationWithDefaultArgumentTest.java
index 7eee8e6..63f24f0 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/callsites/RestartLambdaPropagationWithDefaultArgumentTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/callsites/RestartLambdaPropagationWithDefaultArgumentTest.java
@@ -41,8 +41,6 @@
testForR8(parameters.getBackend())
.addInnerClasses(getClass())
.addKeepMainRule(Main.class)
- .addOptionsModification(
- options -> options.getTestingOptions().enableIfThenElseAbstractFunction = true)
.enableInliningAnnotations()
.setMinApi(parameters)
.compile()
