Extend effectively unused argument removal to args with default values
Change-Id: I6b667f2d630a875a720427d89be0b83ae4ee733c
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index b55931c..59fde05 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
@@ -370,6 +370,10 @@
return predecessors.get(0);
}
+ public BasicBlock getPredecessor(int i) {
+ return getPredecessors().get(i);
+ }
+
public List<BasicBlock> getPredecessors() {
return ListUtils.unmodifiableForTesting(predecessors);
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Value.java b/src/main/java/com/android/tools/r8/ir/code/Value.java
index fbccb7c..5fc512f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Value.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Value.java
@@ -371,8 +371,17 @@
}
public Instruction singleUniqueUser() {
- assert ImmutableSet.copyOf(users).size() == 1;
- return users.getFirst();
+ assert hasSingleUniqueUser();
+ return firstUser();
+ }
+
+ public boolean hasSingleUniquePhiUser() {
+ return uniquePhiUsers().size() == 1;
+ }
+
+ public Phi singleUniquePhiUser() {
+ assert hasSingleUniquePhiUser();
+ return firstPhiUser();
}
public Set<Instruction> aliasedUsers() {
@@ -397,6 +406,11 @@
}
}
+ public Instruction firstUser() {
+ assert !users.isEmpty();
+ return users.getFirst();
+ }
+
public Phi firstPhiUser() {
assert !phiUsers.isEmpty();
return phiUsers.getFirst();
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
index 72e0051..e8b022d 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
@@ -35,7 +35,6 @@
import static com.android.tools.r8.utils.ObjectUtils.getBooleanOrElse;
import com.android.tools.r8.errors.CompilationError;
-import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AccessControl;
import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
import com.android.tools.r8.graph.AppView;
@@ -75,6 +74,7 @@
import com.android.tools.r8.ir.code.ConstClass;
import com.android.tools.r8.ir.code.ConstMethodHandle;
import com.android.tools.r8.ir.code.ConstMethodType;
+import com.android.tools.r8.ir.code.ConstNumber;
import com.android.tools.r8.ir.code.DexItemBasedConstString;
import com.android.tools.r8.ir.code.FieldGet;
import com.android.tools.r8.ir.code.FieldInstruction;
@@ -874,7 +874,7 @@
}
}
if (mayHaveUnreachableBlocks) {
- code.removeUnreachableBlocks(affectedValues, prunedValue -> affectedPhis.remove(prunedValue));
+ code.removeUnreachableBlocks(affectedValues, affectedPhis::remove);
}
affectedValues.narrowingWithAssumeRemoval(appView, code);
if (!affectedPhis.isEmpty()) {
@@ -884,7 +884,7 @@
nullCheckInserter.processWorklist();
code.removeAllDeadAndTrivialPhis();
code.removeRedundantBlocks();
- removeUnusedArguments(method, code, unusedArguments);
+ removeUnusedArguments(code, unusedArguments);
// Finalize cast and null check insertion.
interfaceTypeToClassTypeRewriterHelper.processWorklist();
@@ -1075,16 +1075,31 @@
return replacement;
}
- private void removeUnusedArguments(
- ProgramMethod method, IRCode code, Set<UnusedArgument> unusedArguments) {
+ private void removeUnusedArguments(IRCode code, Set<UnusedArgument> unusedArguments) {
+ AffectedValues affectedValues = new AffectedValues();
for (UnusedArgument unusedArgument : unusedArguments) {
+ InstructionListIterator instructionIterator =
+ unusedArgument.getBlock().listIterator(code, unusedArgument);
if (unusedArgument.outValue().hasAnyUsers()) {
- throw new Unreachable("Unused argument with users in " + method.toSourceString());
+ // This is an unused argument with a default value. The unused argument is an operand of the
+ // phi. This use is eliminated after constant propagation + branch pruning. We eliminate the
+ // UnusedArgument instruction early by replacing it with a const 0.
+ assert unusedArgument.outValue().hasPhiUsers();
+ assert !unusedArgument.outValue().hasUsers();
+ assert !unusedArgument.outValue().hasDebugUsers();
+ TypeElement type = unusedArgument.outValue().getType();
+ instructionIterator.replaceCurrentInstruction(
+ ConstNumber.builder()
+ .setFreshOutValue(code, type.isReferenceType() ? TypeElement.getNull() : type)
+ .setPosition(Position.none())
+ .setValue(0)
+ .build(),
+ affectedValues);
+ } else {
+ instructionIterator.removeOrReplaceByDebugLocalRead();
}
- InstructionListIterator instructionIterator = unusedArgument.getBlock().listIterator(code);
- instructionIterator.nextUntil(instruction -> instruction == unusedArgument);
- instructionIterator.removeOrReplaceByDebugLocalRead();
}
+ affectedValues.narrowingWithAssumeRemoval(appView, code);
}
private Deque<GraphLensInterval> getUnappliedLenses(ProgramMethod method) {
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 2273dbb..e0563ca 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
@@ -134,7 +134,7 @@
codeScanner.scan(method, code, abstractValueSupplier, pathConstraintSupplier, timing);
assert effectivelyUnusedArgumentsAnalysis != null;
- effectivelyUnusedArgumentsAnalysis.scan(method, code);
+ effectivelyUnusedArgumentsAnalysis.scan(method, code, pathConstraintSupplier);
assert reprocessingCriteriaCollection != null;
reprocessingCriteriaCollection.analyzeArgumentUses(method, code);
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 1231d76..54cf0b1 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
@@ -19,6 +19,10 @@
MethodParameter getSingleOpenVariable();
+ default boolean isArgumentBitSetCompareNode() {
+ return false;
+ }
+
default boolean isUnknown() {
return false;
}
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 fb4c465..62455d4 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
@@ -5,7 +5,9 @@
import com.android.tools.r8.ir.analysis.value.AbstractValue;
import com.android.tools.r8.ir.analysis.value.AbstractValueFactory;
+import com.android.tools.r8.ir.analysis.value.SingleNumberValue;
import com.android.tools.r8.ir.code.IfType;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodParameter;
import java.util.Objects;
import java.util.function.IntFunction;
@@ -33,6 +35,20 @@
}
@Override
+ public boolean isArgumentBitSetCompareNode() {
+ if (!type.isEqualsOrNotEquals() || !(operand instanceof ComputationTreeLogicalBinopAndNode)) {
+ return false;
+ }
+ ComputationTreeLogicalBinopAndNode andOperand = (ComputationTreeLogicalBinopAndNode) operand;
+ return andOperand.left instanceof MethodParameter
+ && andOperand.right instanceof SingleNumberValue;
+ }
+
+ public ComputationTreeUnopCompareNode negate() {
+ return new ComputationTreeUnopCompareNode(operand, type.inverted());
+ }
+
+ @Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
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 1eec104..860f3d4 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
@@ -11,12 +11,18 @@
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.graph.PrunedItems;
+import com.android.tools.r8.ir.analysis.path.PathConstraintSupplier;
+import com.android.tools.r8.ir.analysis.path.state.ConcretePathConstraintAnalysisState;
import com.android.tools.r8.ir.code.Argument;
+import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodParameter;
+import com.android.tools.r8.optimize.argumentpropagation.computation.ComputationTreeNode;
+import com.android.tools.r8.optimize.argumentpropagation.computation.ComputationTreeUnopCompareNode;
import com.android.tools.r8.optimize.argumentpropagation.utils.ParameterRemovalUtils;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.ListUtils;
@@ -28,6 +34,7 @@
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
+import java.util.function.Consumer;
/**
* Analysis to find arguments that are effectively unused. The analysis first computes the
@@ -68,6 +75,14 @@
private final AppView<AppInfoWithLiveness> appView;
+ // If the condition for a given method parameter evaluates to true then the parameter is unused,
+ // regardless (!) of the constraints for the method parameter in `constraints`. If the condition
+ // evaluates to false, the method parameter can still be unused if all the constraints for the
+ // method parameter are unused.
+ //
+ // All constraints in this map are currently on the form `(arg & const) != 0`.
+ private final Map<MethodParameter, ComputationTreeNode> conditions = new ConcurrentHashMap<>();
+
// Maps each method parameter p to the method parameters that must be effectively unused in order
// for the method parameter p to be effectively unused.
private final Map<MethodParameter, Set<MethodParameter>> constraints = new ConcurrentHashMap<>();
@@ -107,7 +122,8 @@
});
}
- public void scan(ProgramMethod method, IRCode code) {
+ public void scan(
+ ProgramMethod method, IRCode code, PathConstraintSupplier pathConstraintSupplier) {
// If this method is not subject to optimization, then don't compute effectively unused
// constraints for the method parameters.
if (isUnoptimizable(method)) {
@@ -117,31 +133,57 @@
while (argumentIterator.hasNext()) {
Argument argument = argumentIterator.next();
Value argumentValue = argument.outValue();
- Set<MethodParameter> effectivelyUnusedConstraints =
- computeEffectivelyUnusedConstraints(method, argument, argumentValue);
- if (effectivelyUnusedConstraints != null && !effectivelyUnusedConstraints.isEmpty()) {
- MethodParameter methodParameter = new MethodParameter(method, argument.getIndex());
- assert !constraints.containsKey(methodParameter);
- constraints.put(methodParameter, effectivelyUnusedConstraints);
- }
+ computeEffectivelyUnusedConstraints(
+ method,
+ argument,
+ argumentValue,
+ pathConstraintSupplier,
+ effectivelyUnusedCondition -> {
+ MethodParameter methodParameter = new MethodParameter(method, argument.getIndex());
+ assert !conditions.containsKey(methodParameter);
+ conditions.put(methodParameter, effectivelyUnusedCondition);
+ },
+ effectivelyUnusedConstraints -> {
+ MethodParameter methodParameter = new MethodParameter(method, argument.getIndex());
+ assert !constraints.containsKey(methodParameter);
+ constraints.put(methodParameter, effectivelyUnusedConstraints);
+ });
}
}
- private Set<MethodParameter> computeEffectivelyUnusedConstraints(
- ProgramMethod method, Argument argument, Value argumentValue) {
- if (method.getDefinition().isInstanceInitializer() && argumentValue.isThis()) {
- return null;
- }
+ private void computeEffectivelyUnusedConstraints(
+ ProgramMethod method,
+ Argument argument,
+ Value argumentValue,
+ PathConstraintSupplier pathConstraintSupplier,
+ Consumer<ComputationTreeNode> effectivelyUnusedConditionsConsumer,
+ Consumer<Set<MethodParameter>> effectivelyUnusedConstraintsConsumer) {
if (!ParameterRemovalUtils.canRemoveUnusedParameter(appView, method, argument.getIndex())) {
- return null;
+ return;
}
- if (!argumentValue.getType().isClassType()
- || argumentValue.hasDebugUsers()
- || argumentValue.hasPhiUsers()) {
- return null;
+ if (!argumentValue.getType().isClassType() || argumentValue.hasDebugUsers()) {
+ return;
+ }
+ Value usedValue;
+ if (argumentValue.hasPhiUsers()) {
+ // If the argument has one or more phi users, we check if there is a single phi due to a
+ // default value for the argument. If so, we record this condition and mark the users of the
+ // phi as effectively unused argument constraints for the current argument.
+ if (!computeEffectivelyUnusedCondition(
+ argumentValue, pathConstraintSupplier, effectivelyUnusedConditionsConsumer)) {
+ return;
+ }
+ assert argumentValue.hasSingleUniquePhiUser();
+ Phi user = argumentValue.singleUniquePhiUser();
+ if (user.hasDebugUsers() || user.hasPhiUsers()) {
+ return;
+ }
+ usedValue = user;
+ } else {
+ usedValue = argumentValue;
}
Set<MethodParameter> effectivelyUnusedConstraints = new HashSet<>();
- for (Instruction user : argumentValue.uniqueUsers()) {
+ for (Instruction user : usedValue.uniqueUsers()) {
if (user.isInvokeMethod()) {
InvokeMethod invoke = user.asInvokeMethod();
ProgramMethod resolvedMethod =
@@ -150,29 +192,68 @@
.unsafeResolveMethodDueToDexFormatLegacy(invoke.getInvokedMethod())
.getResolvedProgramMethod();
if (resolvedMethod == null || isUnoptimizable(resolvedMethod)) {
- return null;
+ return;
}
int dependentArgumentIndex =
ListUtils.uniqueIndexMatching(invoke.arguments(), value -> value == argumentValue);
if (dependentArgumentIndex < 0
|| !ParameterRemovalUtils.canRemoveUnusedParameter(
appView, resolvedMethod, dependentArgumentIndex)) {
- return null;
+ return;
}
effectivelyUnusedConstraints.add(
new MethodParameter(resolvedMethod, dependentArgumentIndex));
} else {
- return null;
+ return;
}
}
- return effectivelyUnusedConstraints;
+ if (!effectivelyUnusedConstraints.isEmpty()) {
+ effectivelyUnusedConstraintsConsumer.accept(effectivelyUnusedConstraints);
+ }
+ }
+
+ private boolean computeEffectivelyUnusedCondition(
+ Value argumentValue,
+ PathConstraintSupplier pathConstraintSupplier,
+ Consumer<ComputationTreeNode> effectivelyUnusedConditionsConsumer) {
+ assert argumentValue.hasPhiUsers();
+ if (argumentValue.hasUsers() || !argumentValue.hasSingleUniquePhiUser()) {
+ return false;
+ }
+ Phi phi = argumentValue.singleUniquePhiUser();
+ if (phi.getOperands().size() != 2) {
+ return false;
+ }
+ BasicBlock block = phi.getBlock();
+ ConcretePathConstraintAnalysisState leftState =
+ pathConstraintSupplier.getPathConstraint(block.getPredecessor(0)).asConcreteState();
+ ConcretePathConstraintAnalysisState rightState =
+ pathConstraintSupplier.getPathConstraint(block.getPredecessor(1)).asConcreteState();
+ if (leftState == null || rightState == null) {
+ return false;
+ }
+ // 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()) {
+ return false;
+ }
+ // Extract the state corresponding to the program path where the argument is unused. If the
+ // condition evaluates to false on this program path then negate the condition.
+ ConcretePathConstraintAnalysisState unusedState =
+ phi.getOperand(0) == argumentValue ? rightState : leftState;
+ if (unusedState.isNegated(condition)) {
+ condition = ((ComputationTreeUnopCompareNode) condition).negate();
+ }
+ effectivelyUnusedConditionsConsumer.accept(condition);
+ return true;
}
public void computeEffectivelyUnusedArguments(PrunedItems prunedItems) {
// Build a graph where nodes are method parameters and there is an edge from method parameter p0
// to method parameter p1 if the removal of p0 depends on the removal of p1.
EffectivelyUnusedArgumentsGraph dependenceGraph =
- EffectivelyUnusedArgumentsGraph.create(appView, constraints, prunedItems);
+ EffectivelyUnusedArgumentsGraph.create(appView, conditions, constraints, prunedItems);
// Remove all unoptimizable method parameters from the graph, as well as all nodes that depend
// on a node that is unoptimable.
@@ -221,7 +302,9 @@
for (int argumentIndex = 0;
argumentIndex < method.getDefinition().getNumberOfArguments();
argumentIndex++) {
- constraints.remove(new MethodParameter(method, argumentIndex));
+ MethodParameter methodParameter = new MethodParameter(method, argumentIndex);
+ conditions.remove(methodParameter);
+ constraints.remove(methodParameter);
}
}
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsGraph.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsGraph.java
index 1f795ad..22de2db 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsGraph.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsGraph.java
@@ -9,8 +9,11 @@
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.graph.PrunedItems;
+import com.android.tools.r8.ir.analysis.value.AbstractValue;
+import com.android.tools.r8.ir.optimize.info.CallSiteOptimizationInfo;
import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodParameter;
+import com.android.tools.r8.optimize.argumentpropagation.computation.ComputationTreeNode;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.WorkList;
import com.android.tools.r8.utils.dfs.DFSStack;
@@ -38,9 +41,33 @@
public static EffectivelyUnusedArgumentsGraph create(
AppView<AppInfoWithLiveness> appView,
+ Map<MethodParameter, ComputationTreeNode> conditions,
Map<MethodParameter, Set<MethodParameter>> constraints,
PrunedItems prunedItems) {
EffectivelyUnusedArgumentsGraph graph = new EffectivelyUnusedArgumentsGraph(appView);
+ conditions.forEach(
+ (methodParameter, condition) -> {
+ ProgramMethod method =
+ asProgramMethodOrNull(appView.definitionFor(methodParameter.getMethod()));
+ if (method == null) {
+ assert false;
+ return;
+ }
+ // Evaluate the condition. If the condition evaluates to true, then create a graph node
+ // for the method parameter and delete all constraints. As a result, the node will not
+ // have any successors, meaning it is effectively unused.
+ CallSiteOptimizationInfo optimizationInfo =
+ method.getOptimizationInfo().getArgumentInfos();
+ if (optimizationInfo.isConcreteCallSiteOptimizationInfo()) {
+ AbstractValue result =
+ condition.evaluate(
+ optimizationInfo::getAbstractArgumentValue, appView.abstractValueFactory());
+ if (result.isTrue()) {
+ graph.getOrCreateNode(methodParameter);
+ constraints.remove(methodParameter);
+ }
+ }
+ });
constraints.forEach(
(methodParameter, constraintsForMethodParameter) -> {
EffectivelyUnusedArgumentsGraphNode node = graph.getOrCreateNode(methodParameter);
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 93c4be1..7eee8e6 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
@@ -71,11 +71,10 @@
.streamInstructions()
.noneMatch(
instruction -> instruction.isConstString("DefaultValueNeverUsed")));
- // TODO(b/302281503): This argument is never used and should be removed.
assertTrue(
mainMethodSubject
.streamInstructions()
- .anyMatch(
+ .noneMatch(
instruction ->
instruction.isConstString("Unused[DefaultValueAlwaysUsed]")));
