Move FlowGraph classes to outer level and introduce a FlowGraphBuilder
Bug: b/296030319
Change-Id: I3badd107cbf38a6773184d6619396f7fcbd42c40
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 5fe2970..c207a11 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
@@ -5,7 +5,7 @@
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.DexField;
-import com.android.tools.r8.optimize.argumentpropagation.propagation.InFlowPropagator.FlowGraph;
+import com.android.tools.r8.optimize.argumentpropagation.propagation.FlowGraph;
import com.android.tools.r8.utils.InternalOptions;
import java.util.function.Supplier;
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/DefaultFieldValueJoiner.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/DefaultFieldValueJoiner.java
index 834f186..949bc53 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/DefaultFieldValueJoiner.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/DefaultFieldValueJoiner.java
@@ -11,8 +11,6 @@
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.conversion.MethodConversionOptions;
-import com.android.tools.r8.optimize.argumentpropagation.propagation.InFlowPropagator.FlowGraph;
-import com.android.tools.r8.optimize.argumentpropagation.propagation.InFlowPropagator.Node;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.IterableUtils;
import com.android.tools.r8.utils.ListUtils;
@@ -43,7 +41,7 @@
this.flowGraphs = flowGraphs;
}
- public Map<FlowGraph, Deque<Node>> joinDefaultFieldValuesForFieldsWithReadBeforeWrite(
+ public Map<FlowGraph, Deque<FlowGraphNode>> joinDefaultFieldValuesForFieldsWithReadBeforeWrite(
ExecutorService executorService) throws ExecutionException {
// Find all the fields where we need to determine if each field read is guaranteed to be
// dominated by a write.
@@ -192,14 +190,14 @@
}
}
- private Map<FlowGraph, Deque<Node>> updateFlowGraphs(
+ private Map<FlowGraph, Deque<FlowGraphNode>> updateFlowGraphs(
ProgramFieldSet fieldsWithLiveDefaultValue, ExecutorService executorService)
throws ExecutionException {
- Collection<Pair<FlowGraph, Deque<Node>>> worklists =
+ Collection<Pair<FlowGraph, Deque<FlowGraphNode>>> worklists =
ThreadUtils.processItemsWithResultsThatMatches(
flowGraphs,
flowGraph -> {
- Deque<Node> worklist = new ArrayDeque<>();
+ Deque<FlowGraphNode> worklist = new ArrayDeque<>();
flowGraph.forEachFieldNode(
node -> {
ProgramField field = node.getField();
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraph.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraph.java
new file mode 100644
index 0000000..01a65d2
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraph.java
@@ -0,0 +1,105 @@
+// Copyright (c) 2024, 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.propagation;
+
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.ir.conversion.IRConverter;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.BaseInFlow;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.FieldStateCollection;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.FieldValue;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.FlowGraphStateProvider;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodParameter;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodStateCollectionByReference;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ValueState;
+import com.android.tools.r8.optimize.argumentpropagation.utils.BidirectedGraph;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceMaps;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
+import java.util.Collection;
+import java.util.IdentityHashMap;
+import java.util.Map;
+import java.util.function.Consumer;
+import java.util.function.Supplier;
+
+public class FlowGraph extends BidirectedGraph<FlowGraphNode> implements FlowGraphStateProvider {
+
+ private final Map<DexField, FlowGraphFieldNode> fieldNodes;
+ private final Map<DexMethod, Int2ReferenceMap<FlowGraphParameterNode>> parameterNodes;
+
+ public FlowGraph(
+ Map<DexField, FlowGraphFieldNode> fieldNodes,
+ Map<DexMethod, Int2ReferenceMap<FlowGraphParameterNode>> parameterNodes) {
+ this.fieldNodes = fieldNodes;
+ this.parameterNodes = parameterNodes;
+ }
+
+ public FlowGraph(Collection<FlowGraphNode> nodes) {
+ this(new IdentityHashMap<>(), new IdentityHashMap<>());
+ for (FlowGraphNode node : nodes) {
+ if (node.isFieldNode()) {
+ FlowGraphFieldNode fieldNode = node.asFieldNode();
+ fieldNodes.put(fieldNode.getField().getReference(), fieldNode);
+ } else {
+ FlowGraphParameterNode parameterNode = node.asParameterNode();
+ parameterNodes
+ .computeIfAbsent(
+ parameterNode.getMethod().getReference(), ignoreKey(Int2ReferenceOpenHashMap::new))
+ .put(parameterNode.getParameterIndex(), parameterNode);
+ }
+ }
+ }
+
+ public static FlowGraphBuilder builder(
+ AppView<AppInfoWithLiveness> appView,
+ IRConverter converter,
+ FieldStateCollection fieldStates,
+ MethodStateCollectionByReference methodStates) {
+ return new FlowGraphBuilder(appView, converter, fieldStates, methodStates);
+ }
+
+ public void forEachFieldNode(Consumer<? super FlowGraphFieldNode> consumer) {
+ fieldNodes.values().forEach(consumer);
+ }
+
+ @Override
+ public void forEachNeighbor(FlowGraphNode node, Consumer<? super FlowGraphNode> consumer) {
+ node.getPredecessors().forEach(consumer);
+ node.getSuccessors().forEach(consumer);
+ }
+
+ @Override
+ public void forEachNode(Consumer<? super FlowGraphNode> consumer) {
+ forEachFieldNode(consumer);
+ parameterNodes.values().forEach(nodesForMethod -> nodesForMethod.values().forEach(consumer));
+ }
+
+ @Override
+ public ValueState getState(DexField field) {
+ return fieldNodes.get(field).getState();
+ }
+
+ @Override
+ public ValueState getState(BaseInFlow inFlow, Supplier<ValueState> defaultStateProvider) {
+ if (inFlow.isFieldValue()) {
+ FieldValue fieldValue = inFlow.asFieldValue();
+ return getState(fieldValue.getField());
+ } else {
+ assert inFlow.isMethodParameter();
+ MethodParameter methodParameter = inFlow.asMethodParameter();
+ FlowGraphParameterNode parameterNode =
+ parameterNodes
+ .getOrDefault(methodParameter.getMethod(), Int2ReferenceMaps.emptyMap())
+ .get(methodParameter.getIndex());
+ if (parameterNode != null) {
+ return parameterNode.getState();
+ }
+ return defaultStateProvider.get();
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphBuilder.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphBuilder.java
new file mode 100644
index 0000000..a998a15
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphBuilder.java
@@ -0,0 +1,296 @@
+// Copyright (c) 2024, 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.propagation;
+
+import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
+import static com.android.tools.r8.graph.ProgramField.asProgramFieldOrNull;
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
+
+import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.ProgramField;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.conversion.IRConverter;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.AbstractFunction;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.BaseInFlow;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteMonomorphicMethodState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteValueState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.FieldStateCollection;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.FieldValue;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.InFlow;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodParameter;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodStateCollectionByReference;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ValueState;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.TraversalContinuation;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
+import java.util.Collection;
+import java.util.IdentityHashMap;
+import java.util.List;
+import java.util.Map;
+
+public class FlowGraphBuilder {
+
+ private final AppView<AppInfoWithLiveness> appView;
+ private final IRConverter converter;
+ private final FieldStateCollection fieldStates;
+ private final MethodStateCollectionByReference methodStates;
+
+ private final Map<DexField, FlowGraphFieldNode> fieldNodes = new IdentityHashMap<>();
+ private final Map<DexMethod, Int2ReferenceMap<FlowGraphParameterNode>> parameterNodes =
+ new IdentityHashMap<>();
+
+ public FlowGraphBuilder(
+ AppView<AppInfoWithLiveness> appView,
+ IRConverter converter,
+ FieldStateCollection fieldStates,
+ MethodStateCollectionByReference methodStates) {
+ this.appView = appView;
+ this.converter = converter;
+ this.fieldStates = fieldStates;
+ this.methodStates = methodStates;
+ }
+
+ public FlowGraphBuilder addClasses(Collection<DexProgramClass> classes) {
+ for (DexProgramClass clazz : classes) {
+ add(clazz);
+ }
+ return this;
+ }
+
+ public FlowGraph build() {
+ return new FlowGraph(fieldNodes, parameterNodes);
+ }
+
+ private void add(DexProgramClass clazz) {
+ clazz.forEachProgramField(this::addField);
+ clazz.forEachProgramMethod(this::addMethodParameters);
+ }
+
+ private void addField(ProgramField field) {
+ ValueState fieldState = fieldStates.get(field);
+
+ // No need to create nodes for fields with no in-flow or no useful information.
+ if (fieldState.isBottom() || fieldState.isUnknown()) {
+ return;
+ }
+
+ ConcreteValueState concreteFieldState = fieldState.asConcrete();
+
+ // No need to create a node for a field that doesn't depend on any other nodes, unless some
+ // other node depends on this field, in which case that other node will lead to creation of a
+ // node for the current field.
+ if (!concreteFieldState.hasInFlow()) {
+ return;
+ }
+
+ FlowGraphFieldNode node = getOrCreateFieldNode(field, concreteFieldState);
+ for (InFlow inFlow : concreteFieldState.getInFlow()) {
+ if (addInFlow(inFlow, node).shouldBreak()) {
+ assert node.isUnknown();
+ break;
+ }
+ }
+
+ if (!node.getState().isUnknown()) {
+ assert node.getState() == concreteFieldState;
+ node.setState(concreteFieldState.clearInFlow());
+ }
+ }
+
+ private void addMethodParameters(ProgramMethod method) {
+ MethodState methodState = methodStates.get(method);
+
+ // No need to create nodes for parameters with no in-flow or no useful information.
+ if (methodState.isBottom() || methodState.isUnknown()) {
+ return;
+ }
+
+ // Add nodes for the parameters for which we have non-trivial information.
+ ConcreteMonomorphicMethodState monomorphicMethodState = methodState.asMonomorphic();
+ List<ValueState> parameterStates = monomorphicMethodState.getParameterStates();
+ for (int parameterIndex = 0; parameterIndex < parameterStates.size(); parameterIndex++) {
+ ValueState parameterState = parameterStates.get(parameterIndex);
+ addMethodParameter(method, parameterIndex, monomorphicMethodState, parameterState);
+ }
+ }
+
+ private void addMethodParameter(
+ ProgramMethod method,
+ int parameterIndex,
+ ConcreteMonomorphicMethodState methodState,
+ ValueState parameterState) {
+ // No need to create nodes for parameters with no in-parameters and parameters we don't know
+ // anything about.
+ if (parameterState.isBottom() || parameterState.isUnknown()) {
+ return;
+ }
+
+ ConcreteValueState concreteParameterState = parameterState.asConcrete();
+
+ // No need to create a node for a parameter that doesn't depend on any other parameters,
+ // unless some other node depends on this parameter, in which case that other node will lead
+ // to the creation of a node for the current parameter.
+ if (!concreteParameterState.hasInFlow()) {
+ return;
+ }
+
+ FlowGraphParameterNode node = getOrCreateParameterNode(method, parameterIndex, methodState);
+ for (InFlow inFlow : concreteParameterState.getInFlow()) {
+ if (addInFlow(inFlow, node).shouldBreak()) {
+ assert node.isUnknown();
+ break;
+ }
+ }
+
+ if (!node.getState().isUnknown()) {
+ assert node.getState() == concreteParameterState;
+ node.setState(concreteParameterState.clearInFlow());
+ }
+ }
+
+ // Returns BREAK if the current node has been set to unknown.
+ private TraversalContinuation<?, ?> addInFlow(InFlow inFlow, FlowGraphNode node) {
+ if (inFlow.isAbstractFunction()) {
+ return addInFlow(inFlow.asAbstractFunction(), node);
+ } else if (inFlow.isFieldValue()) {
+ return addInFlow(inFlow.asFieldValue(), node);
+ } else if (inFlow.isMethodParameter()) {
+ return addInFlow(inFlow.asMethodParameter(), node);
+ } else {
+ throw new Unreachable(inFlow.getClass().getTypeName());
+ }
+ }
+
+ private TraversalContinuation<?, ?> addInFlow(AbstractFunction inFlow, FlowGraphNode node) {
+ for (BaseInFlow baseInFlow : inFlow.getBaseInFlow()) {
+ TraversalContinuation<?, ?> traversalContinuation;
+ if (baseInFlow.isFieldValue()) {
+ traversalContinuation = addInFlow(baseInFlow.asFieldValue(), node, inFlow);
+ } else {
+ assert baseInFlow.isMethodParameter();
+ traversalContinuation = addInFlow(baseInFlow.asMethodParameter(), node, inFlow);
+ }
+ if (traversalContinuation.shouldBreak()) {
+ return traversalContinuation;
+ }
+ }
+ return TraversalContinuation.doContinue();
+ }
+
+ private TraversalContinuation<?, ?> addInFlow(FieldValue inFlow, FlowGraphNode node) {
+ return addInFlow(inFlow, node, AbstractFunction.identity());
+ }
+
+ private TraversalContinuation<?, ?> addInFlow(
+ FieldValue inFlow, FlowGraphNode node, AbstractFunction transferFunction) {
+ assert !node.isUnknown();
+
+ ProgramField field = asProgramFieldOrNull(appView.definitionFor(inFlow.getField()));
+ if (field == null) {
+ assert false;
+ return TraversalContinuation.doContinue();
+ }
+
+ ValueState fieldState = getFieldState(field, fieldStates);
+ if (fieldState.isUnknown()) {
+ // The current node depends on a field for which we don't know anything.
+ node.clearPredecessors();
+ node.setStateToUnknown();
+ return TraversalContinuation.doBreak();
+ }
+
+ FlowGraphFieldNode fieldNode = getOrCreateFieldNode(field, fieldState);
+ node.addPredecessor(fieldNode, transferFunction);
+ return TraversalContinuation.doContinue();
+ }
+
+ private TraversalContinuation<?, ?> addInFlow(MethodParameter inFlow, FlowGraphNode node) {
+ return addInFlow(inFlow, node, AbstractFunction.identity());
+ }
+
+ private TraversalContinuation<?, ?> addInFlow(
+ MethodParameter inFlow, FlowGraphNode node, AbstractFunction transferFunction) {
+ ProgramMethod enclosingMethod = getEnclosingMethod(inFlow);
+ if (enclosingMethod == null) {
+ // This is a parameter of a single caller inlined method. Since this method has been
+ // pruned, the call from inside the method no longer exists, and we can therefore safely
+ // skip it.
+ assert converter.getInliner().verifyIsPrunedDueToSingleCallerInlining(inFlow.getMethod());
+ return TraversalContinuation.doContinue();
+ }
+
+ MethodState enclosingMethodState = getMethodState(enclosingMethod, methodStates);
+ if (enclosingMethodState.isBottom()) {
+ // The current node takes a value from a dead method; no need to propagate any information
+ // from the dead assignment.
+ return TraversalContinuation.doContinue();
+ }
+
+ if (enclosingMethodState.isUnknown()) {
+ // The current node depends on a parameter for which we don't know anything.
+ node.clearPredecessors();
+ node.setStateToUnknown();
+ return TraversalContinuation.doBreak();
+ }
+
+ assert enclosingMethodState.isConcrete();
+ assert enclosingMethodState.asConcrete().isMonomorphic();
+
+ FlowGraphParameterNode predecessor =
+ getOrCreateParameterNode(
+ enclosingMethod, inFlow.getIndex(), enclosingMethodState.asConcrete().asMonomorphic());
+ node.addPredecessor(predecessor, transferFunction);
+ return TraversalContinuation.doContinue();
+ }
+
+ private FlowGraphFieldNode getOrCreateFieldNode(ProgramField field, ValueState fieldState) {
+ return fieldNodes.computeIfAbsent(
+ field.getReference(), ignoreKey(() -> new FlowGraphFieldNode(field, fieldState)));
+ }
+
+ private FlowGraphParameterNode getOrCreateParameterNode(
+ ProgramMethod method, int parameterIndex, ConcreteMonomorphicMethodState methodState) {
+ Int2ReferenceMap<FlowGraphParameterNode> parameterNodesForMethod =
+ parameterNodes.computeIfAbsent(
+ method.getReference(), ignoreKey(Int2ReferenceOpenHashMap::new));
+ return parameterNodesForMethod.compute(
+ parameterIndex,
+ (ignore, parameterNode) ->
+ parameterNode != null
+ ? parameterNode
+ : new FlowGraphParameterNode(
+ method, methodState, parameterIndex, method.getArgumentType(parameterIndex)));
+ }
+
+ private ProgramMethod getEnclosingMethod(MethodParameter methodParameter) {
+ DexMethod methodReference = methodParameter.getMethod();
+ return methodReference.lookupOnProgramClass(
+ asProgramClassOrNull(appView.definitionFor(methodParameter.getMethod().getHolderType())));
+ }
+
+ private ValueState getFieldState(ProgramField field, FieldStateCollection fieldStates) {
+ if (field == null) {
+ // Conservatively return unknown if for some reason we can't find the field.
+ assert false;
+ return ValueState.unknown();
+ }
+ return fieldStates.get(field);
+ }
+
+ private MethodState getMethodState(
+ ProgramMethod method, MethodStateCollectionByReference methodStates) {
+ if (method == null) {
+ // Conservatively return unknown if for some reason we can't find the method.
+ assert false;
+ return MethodState.unknown();
+ }
+ return methodStates.get(method);
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphFieldNode.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphFieldNode.java
new file mode 100644
index 0000000..c25ed35
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphFieldNode.java
@@ -0,0 +1,96 @@
+// Copyright (c) 2024, 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.propagation;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.ProgramField;
+import com.android.tools.r8.ir.analysis.type.DynamicType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
+import com.android.tools.r8.ir.analysis.type.TypeElement;
+import com.android.tools.r8.ir.analysis.value.AbstractValue;
+import com.android.tools.r8.ir.analysis.value.AbstractValueFactory;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteArrayTypeValueState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteClassTypeValueState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcretePrimitiveTypeValueState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.NonEmptyValueState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ValueState;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.Action;
+
+public class FlowGraphFieldNode extends FlowGraphNode {
+
+ private final ProgramField field;
+ private ValueState fieldState;
+
+ FlowGraphFieldNode(ProgramField field, ValueState fieldState) {
+ this.field = field;
+ this.fieldState = fieldState;
+ }
+
+ public ProgramField getField() {
+ return field;
+ }
+
+ @Override
+ DexType getStaticType() {
+ return field.getType();
+ }
+
+ void addDefaultValue(AppView<AppInfoWithLiveness> appView, Action onChangedAction) {
+ AbstractValueFactory abstractValueFactory = appView.abstractValueFactory();
+ AbstractValue defaultValue;
+ if (field.getAccessFlags().isStatic() && field.getDefinition().hasExplicitStaticValue()) {
+ defaultValue = field.getDefinition().getStaticValue().toAbstractValue(abstractValueFactory);
+ } else if (field.getType().isPrimitiveType()) {
+ defaultValue = abstractValueFactory.createZeroValue();
+ } else {
+ defaultValue = abstractValueFactory.createUncheckedNullValue();
+ }
+ NonEmptyValueState fieldStateToAdd;
+ if (field.getType().isArrayType()) {
+ Nullability defaultNullability = Nullability.definitelyNull();
+ fieldStateToAdd = ConcreteArrayTypeValueState.create(defaultNullability);
+ } else if (field.getType().isClassType()) {
+ assert defaultValue.isNull() || defaultValue.isSingleStringValue();
+ DynamicType dynamicType =
+ defaultValue.isNull()
+ ? DynamicType.definitelyNull()
+ : DynamicType.createExact(
+ TypeElement.stringClassType(appView, Nullability.definitelyNotNull()));
+ fieldStateToAdd = ConcreteClassTypeValueState.create(defaultValue, dynamicType);
+ } else {
+ assert field.getType().isPrimitiveType();
+ fieldStateToAdd = ConcretePrimitiveTypeValueState.create(defaultValue);
+ }
+ if (fieldStateToAdd.isConcrete()) {
+ addState(appView, fieldStateToAdd.asConcrete(), onChangedAction);
+ } else {
+ // We should always be able to map static field values to an unknown abstract value.
+ assert false;
+ setStateToUnknown();
+ onChangedAction.execute();
+ }
+ }
+
+ @Override
+ ValueState getState() {
+ return fieldState;
+ }
+
+ @Override
+ void setState(ValueState fieldState) {
+ this.fieldState = fieldState;
+ }
+
+ @Override
+ boolean isFieldNode() {
+ return true;
+ }
+
+ @Override
+ FlowGraphFieldNode asFieldNode() {
+ return this;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphNode.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphNode.java
new file mode 100644
index 0000000..4075465
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphNode.java
@@ -0,0 +1,144 @@
+// Copyright (c) 2024, 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.propagation;
+
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.AbstractFunction;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteValueState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.StateCloner;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ValueState;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.Action;
+import com.google.common.collect.Sets;
+import java.util.Deque;
+import java.util.HashSet;
+import java.util.IdentityHashMap;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.BiPredicate;
+
+public abstract class FlowGraphNode {
+
+ private final Set<FlowGraphNode> predecessors = Sets.newIdentityHashSet();
+ private final Map<FlowGraphNode, Set<AbstractFunction>> successors = new IdentityHashMap<>();
+
+ private boolean inWorklist = true;
+
+ void addState(
+ AppView<AppInfoWithLiveness> appView, ConcreteValueState stateToAdd, Action onChangedAction) {
+ ValueState oldState = getState();
+ ValueState newState =
+ oldState.mutableJoin(
+ appView, stateToAdd, getStaticType(), StateCloner.getCloner(), onChangedAction);
+ if (newState != oldState) {
+ setState(newState);
+ onChangedAction.execute();
+ }
+ }
+
+ abstract ValueState getState();
+
+ abstract DexType getStaticType();
+
+ abstract void setState(ValueState valueState);
+
+ void setStateToUnknown() {
+ setState(ValueState.unknown());
+ }
+
+ void addPredecessor(FlowGraphNode predecessor, AbstractFunction abstractFunction) {
+ predecessor.successors.computeIfAbsent(this, ignoreKey(HashSet::new)).add(abstractFunction);
+ predecessors.add(predecessor);
+ }
+
+ void clearPredecessors() {
+ for (FlowGraphNode predecessor : predecessors) {
+ predecessor.successors.remove(this);
+ }
+ predecessors.clear();
+ }
+
+ void clearPredecessors(FlowGraphNode cause) {
+ for (FlowGraphNode predecessor : predecessors) {
+ if (predecessor != cause) {
+ predecessor.successors.remove(this);
+ }
+ }
+ predecessors.clear();
+ }
+
+ Set<FlowGraphNode> getPredecessors() {
+ return predecessors;
+ }
+
+ boolean hasPredecessors() {
+ return !predecessors.isEmpty();
+ }
+
+ void clearDanglingSuccessors() {
+ successors.clear();
+ }
+
+ Set<FlowGraphNode> getSuccessors() {
+ return successors.keySet();
+ }
+
+ public void forEachSuccessor(BiConsumer<FlowGraphNode, Set<AbstractFunction>> consumer) {
+ successors.forEach(consumer);
+ }
+
+ public void removeSuccessorIf(BiPredicate<FlowGraphNode, Set<AbstractFunction>> predicate) {
+ successors.entrySet().removeIf(entry -> predicate.test(entry.getKey(), entry.getValue()));
+ }
+
+ boolean hasSuccessors() {
+ return !successors.isEmpty();
+ }
+
+ boolean isBottom() {
+ return getState().isBottom();
+ }
+
+ boolean isFieldNode() {
+ return false;
+ }
+
+ FlowGraphFieldNode asFieldNode() {
+ return null;
+ }
+
+ boolean isParameterNode() {
+ return false;
+ }
+
+ FlowGraphParameterNode asParameterNode() {
+ return null;
+ }
+
+ boolean isEffectivelyUnknown() {
+ return getState().isConcrete() && getState().asConcrete().isEffectivelyUnknown();
+ }
+
+ boolean isUnknown() {
+ return getState().isUnknown();
+ }
+
+ // No need to enqueue the affected node if it is already in the worklist or if it does not have
+ // any successors (i.e., the successor is a leaf).
+ void addToWorkList(Deque<FlowGraphNode> worklist) {
+ if (!inWorklist && hasSuccessors()) {
+ worklist.add(this);
+ inWorklist = true;
+ }
+ }
+
+ void unsetInWorklist() {
+ assert inWorklist;
+ inWorklist = false;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphParameterNode.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphParameterNode.java
new file mode 100644
index 0000000..b82cecf
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphParameterNode.java
@@ -0,0 +1,61 @@
+// Copyright (c) 2024, 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.propagation;
+
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteMonomorphicMethodState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ValueState;
+
+class FlowGraphParameterNode extends FlowGraphNode {
+
+ private final ProgramMethod method;
+ private final ConcreteMonomorphicMethodState methodState;
+ private final int parameterIndex;
+ private final DexType parameterType;
+
+ FlowGraphParameterNode(
+ ProgramMethod method,
+ ConcreteMonomorphicMethodState methodState,
+ int parameterIndex,
+ DexType parameterType) {
+ this.method = method;
+ this.methodState = methodState;
+ this.parameterIndex = parameterIndex;
+ this.parameterType = parameterType;
+ }
+
+ ProgramMethod getMethod() {
+ return method;
+ }
+
+ int getParameterIndex() {
+ return parameterIndex;
+ }
+
+ @Override
+ DexType getStaticType() {
+ return parameterType;
+ }
+
+ @Override
+ ValueState getState() {
+ return methodState.getParameterState(parameterIndex);
+ }
+
+ @Override
+ void setState(ValueState parameterState) {
+ methodState.setParameterState(parameterIndex, parameterState);
+ }
+
+ @Override
+ boolean isParameterNode() {
+ return true;
+ }
+
+ @Override
+ FlowGraphParameterNode asParameterNode() {
+ return this;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphWriter.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphWriter.java
index 7b438c4..8f60f27 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphWriter.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/FlowGraphWriter.java
@@ -5,10 +5,6 @@
import com.android.tools.r8.graph.ProgramField;
import com.android.tools.r8.graph.ProgramMethod;
-import com.android.tools.r8.optimize.argumentpropagation.propagation.InFlowPropagator.FieldNode;
-import com.android.tools.r8.optimize.argumentpropagation.propagation.InFlowPropagator.FlowGraph;
-import com.android.tools.r8.optimize.argumentpropagation.propagation.InFlowPropagator.Node;
-import com.android.tools.r8.optimize.argumentpropagation.propagation.InFlowPropagator.ParameterNode;
import com.google.common.annotations.VisibleForTesting;
import java.io.PrintStream;
@@ -33,7 +29,7 @@
out.println(" -> ");
}
- private void writeNode(PrintStream out, Node node) {
+ private void writeNode(PrintStream out, FlowGraphNode node) {
if (!node.hasSuccessors()) {
writeNodeLabel(out, node);
return;
@@ -46,7 +42,7 @@
});
}
- private void writeNodeLabel(PrintStream out, Node node) {
+ private void writeNodeLabel(PrintStream out, FlowGraphNode node) {
if (node.isFieldNode()) {
writeFieldNodeLabel(out, node.asFieldNode());
} else {
@@ -55,7 +51,7 @@
}
}
- private void writeFieldNodeLabel(PrintStream out, FieldNode node) {
+ private void writeFieldNodeLabel(PrintStream out, FlowGraphFieldNode node) {
out.print("\"");
ProgramField field = node.getField();
out.print(field.getHolderType().getSimpleName());
@@ -64,7 +60,7 @@
out.print("\"");
}
- private void writeParameterNodeLabel(PrintStream out, ParameterNode node) {
+ private void writeParameterNodeLabel(PrintStream out, FlowGraphParameterNode node) {
out.print("\"");
ProgramMethod method = node.getMethod();
out.print(method.getHolderType().getSimpleName());
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InFlowPropagator.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InFlowPropagator.java
index 5b1ccf2..894a54c 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InFlowPropagator.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InFlowPropagator.java
@@ -3,66 +3,29 @@
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.optimize.argumentpropagation.propagation;
-import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
-import static com.android.tools.r8.graph.ProgramField.asProgramFieldOrNull;
-import static com.android.tools.r8.utils.MapUtils.ignoreKey;
-
-import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DexField;
-import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexProgramClass;
-import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.graph.ProgramField;
import com.android.tools.r8.graph.ProgramMethod;
-import com.android.tools.r8.ir.analysis.type.DynamicType;
-import com.android.tools.r8.ir.analysis.type.Nullability;
-import com.android.tools.r8.ir.analysis.type.TypeElement;
-import com.android.tools.r8.ir.analysis.value.AbstractValue;
-import com.android.tools.r8.ir.analysis.value.AbstractValueFactory;
import com.android.tools.r8.ir.conversion.IRConverter;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.AbstractFunction;
-import com.android.tools.r8.optimize.argumentpropagation.codescanner.BaseInFlow;
-import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteArrayTypeValueState;
-import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteClassTypeValueState;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteMethodState;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteMonomorphicMethodState;
-import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcretePrimitiveTypeValueState;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteValueState;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.FieldStateCollection;
-import com.android.tools.r8.optimize.argumentpropagation.codescanner.FieldValue;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.FlowGraphStateProvider;
-import com.android.tools.r8.optimize.argumentpropagation.codescanner.InFlow;
-import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodParameter;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodState;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodStateCollectionByReference;
-import com.android.tools.r8.optimize.argumentpropagation.codescanner.NonEmptyValueState;
-import com.android.tools.r8.optimize.argumentpropagation.codescanner.StateCloner;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.ValueState;
-import com.android.tools.r8.optimize.argumentpropagation.utils.BidirectedGraph;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import com.android.tools.r8.utils.Action;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.ThreadUtils;
-import com.android.tools.r8.utils.TraversalContinuation;
-import com.google.common.collect.Sets;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceMaps;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
import java.util.ArrayDeque;
-import java.util.Collection;
import java.util.Deque;
-import java.util.HashSet;
-import java.util.IdentityHashMap;
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.function.BiConsumer;
-import java.util.function.BiPredicate;
-import java.util.function.Consumer;
-import java.util.function.Supplier;
public class InFlowPropagator {
@@ -94,7 +57,7 @@
// perform this analysis after having computed the initial fixpoint(s). The hypothesis is that
// many fields will have reached the unknown state after the initial fixpoint, meaning there is
// fewer fields to analyze.
- Map<FlowGraph, Deque<Node>> worklists =
+ Map<FlowGraph, Deque<FlowGraphNode>> worklists =
includeDefaultValuesInFieldStates(flowGraphs, executorService);
// Since the inclusion of default values changes the flow graphs, we need to repeat the
@@ -110,12 +73,16 @@
private List<FlowGraph> computeStronglyConnectedFlowGraphs() {
// Build a graph with an edge from parameter p -> parameter p' if all argument information for p
// must be included in the argument information for p'.
- FlowGraph flowGraph = new FlowGraph(appView.appInfo().classes());
- List<Set<Node>> stronglyConnectedComponents = flowGraph.computeStronglyConnectedComponents();
+ FlowGraph flowGraph =
+ FlowGraph.builder(appView, converter, fieldStates, methodStates)
+ .addClasses(appView.appInfo().classes())
+ .build();
+ List<Set<FlowGraphNode>> stronglyConnectedComponents =
+ flowGraph.computeStronglyConnectedComponents();
return ListUtils.map(stronglyConnectedComponents, FlowGraph::new);
}
- private Map<FlowGraph, Deque<Node>> includeDefaultValuesInFieldStates(
+ private Map<FlowGraph, Deque<FlowGraphNode>> includeDefaultValuesInFieldStates(
List<FlowGraph> flowGraphs, ExecutorService executorService) throws ExecutionException {
DefaultFieldValueJoiner joiner = new DefaultFieldValueJoiner(appView, flowGraphs);
return joiner.joinDefaultFieldValuesForFieldsWithReadBeforeWrite(executorService);
@@ -128,7 +95,7 @@
}
private void processWorklists(
- Map<FlowGraph, Deque<Node>> worklists, ExecutorService executorService)
+ Map<FlowGraph, Deque<FlowGraphNode>> worklists, ExecutorService executorService)
throws ExecutionException {
ThreadUtils.processMap(
worklists, this::process, appView.options().getThreadingModule(), executorService);
@@ -136,12 +103,12 @@
private void process(FlowGraph flowGraph) {
// Build a worklist containing all the nodes.
- Deque<Node> worklist = new ArrayDeque<>();
+ Deque<FlowGraphNode> worklist = new ArrayDeque<>();
flowGraph.forEachNode(worklist::add);
process(flowGraph, worklist);
}
- private void process(FlowGraph flowGraph, Deque<Node> worklist) {
+ private void process(FlowGraph flowGraph, Deque<FlowGraphNode> worklist) {
// Repeatedly propagate argument information through edges in the flow graph until there are no
// more changes.
// TODO(b/190154391): Consider a path p1 -> p2 -> p3 in the graph. If we process p2 first, then
@@ -149,19 +116,19 @@
// need to reprocess p2 and then p3. If we always process leaves in the graph first, we would
// process p1, then p2, then p3, and then be done.
while (!worklist.isEmpty()) {
- Node node = worklist.removeLast();
+ FlowGraphNode node = worklist.removeLast();
node.unsetInWorklist();
propagate(flowGraph, node, worklist);
}
}
- private void propagate(FlowGraph flowGraph, Node node, Deque<Node> worklist) {
+ private void propagate(FlowGraph flowGraph, FlowGraphNode node, Deque<FlowGraphNode> worklist) {
if (node.isBottom()) {
return;
}
if (node.isUnknown()) {
assert !node.hasPredecessors();
- for (Node successorNode : node.getSuccessors()) {
+ for (FlowGraphNode successorNode : node.getSuccessors()) {
assert !successorNode.isUnknown();
successorNode.clearPredecessors(node);
successorNode.setStateToUnknown();
@@ -173,7 +140,8 @@
}
}
- private void propagateNode(FlowGraph flowGraph, Node node, Deque<Node> worklist) {
+ private void propagateNode(
+ FlowGraph flowGraph, FlowGraphNode node, Deque<FlowGraphNode> worklist) {
ConcreteValueState state = node.getState().asConcrete();
node.removeSuccessorIf(
(successorNode, transferFunctions) -> {
@@ -230,562 +198,4 @@
methodStates.set(method, MethodState.unknown());
}
}
-
- public class FlowGraph extends BidirectedGraph<Node> implements FlowGraphStateProvider {
-
- private final Map<DexField, FieldNode> fieldNodes = new IdentityHashMap<>();
- private final Map<DexMethod, Int2ReferenceMap<ParameterNode>> parameterNodes =
- new IdentityHashMap<>();
-
- public FlowGraph(Iterable<DexProgramClass> classes) {
- classes.forEach(this::add);
- }
-
- public FlowGraph(Collection<Node> nodes) {
- for (Node node : nodes) {
- if (node.isFieldNode()) {
- FieldNode fieldNode = node.asFieldNode();
- fieldNodes.put(fieldNode.getField().getReference(), fieldNode);
- } else {
- ParameterNode parameterNode = node.asParameterNode();
- parameterNodes
- .computeIfAbsent(
- parameterNode.getMethod().getReference(),
- ignoreKey(Int2ReferenceOpenHashMap::new))
- .put(parameterNode.getParameterIndex(), parameterNode);
- }
- }
- }
-
- public void forEachFieldNode(Consumer<? super FieldNode> consumer) {
- fieldNodes.values().forEach(consumer);
- }
-
- @Override
- public void forEachNeighbor(Node node, Consumer<? super Node> consumer) {
- node.getPredecessors().forEach(consumer);
- node.getSuccessors().forEach(consumer);
- }
-
- @Override
- public void forEachNode(Consumer<? super Node> consumer) {
- forEachFieldNode(consumer);
- parameterNodes.values().forEach(nodesForMethod -> nodesForMethod.values().forEach(consumer));
- }
-
- private void add(DexProgramClass clazz) {
- clazz.forEachProgramField(this::addField);
- clazz.forEachProgramMethod(this::addMethodParameters);
- }
-
- private void addField(ProgramField field) {
- ValueState fieldState = fieldStates.get(field);
-
- // No need to create nodes for fields with no in-flow or no useful information.
- if (fieldState.isBottom() || fieldState.isUnknown()) {
- return;
- }
-
- ConcreteValueState concreteFieldState = fieldState.asConcrete();
-
- // No need to create a node for a field that doesn't depend on any other nodes, unless some
- // other node depends on this field, in which case that other node will lead to creation of a
- // node for the current field.
- if (!concreteFieldState.hasInFlow()) {
- return;
- }
-
- FieldNode node = getOrCreateFieldNode(field, concreteFieldState);
- for (InFlow inFlow : concreteFieldState.getInFlow()) {
- if (addInFlow(inFlow, node).shouldBreak()) {
- assert node.isUnknown();
- break;
- }
- }
-
- if (!node.getState().isUnknown()) {
- assert node.getState() == concreteFieldState;
- node.setState(concreteFieldState.clearInFlow());
- }
- }
-
- private void addMethodParameters(ProgramMethod method) {
- MethodState methodState = methodStates.get(method);
-
- // No need to create nodes for parameters with no in-flow or no useful information.
- if (methodState.isBottom() || methodState.isUnknown()) {
- return;
- }
-
- // Add nodes for the parameters for which we have non-trivial information.
- ConcreteMonomorphicMethodState monomorphicMethodState = methodState.asMonomorphic();
- List<ValueState> parameterStates = monomorphicMethodState.getParameterStates();
- for (int parameterIndex = 0; parameterIndex < parameterStates.size(); parameterIndex++) {
- ValueState parameterState = parameterStates.get(parameterIndex);
- addMethodParameter(method, parameterIndex, monomorphicMethodState, parameterState);
- }
- }
-
- private void addMethodParameter(
- ProgramMethod method,
- int parameterIndex,
- ConcreteMonomorphicMethodState methodState,
- ValueState parameterState) {
- // No need to create nodes for parameters with no in-parameters and parameters we don't know
- // anything about.
- if (parameterState.isBottom() || parameterState.isUnknown()) {
- return;
- }
-
- ConcreteValueState concreteParameterState = parameterState.asConcrete();
-
- // No need to create a node for a parameter that doesn't depend on any other parameters,
- // unless some other node depends on this parameter, in which case that other node will lead
- // to the creation of a node for the current parameter.
- if (!concreteParameterState.hasInFlow()) {
- return;
- }
-
- ParameterNode node = getOrCreateParameterNode(method, parameterIndex, methodState);
- for (InFlow inFlow : concreteParameterState.getInFlow()) {
- if (addInFlow(inFlow, node).shouldBreak()) {
- assert node.isUnknown();
- break;
- }
- }
-
- if (!node.getState().isUnknown()) {
- assert node.getState() == concreteParameterState;
- node.setState(concreteParameterState.clearInFlow());
- }
- }
-
- // Returns BREAK if the current node has been set to unknown.
- private TraversalContinuation<?, ?> addInFlow(InFlow inFlow, Node node) {
- if (inFlow.isAbstractFunction()) {
- return addInFlow(inFlow.asAbstractFunction(), node);
- } else if (inFlow.isFieldValue()) {
- return addInFlow(inFlow.asFieldValue(), node);
- } else if (inFlow.isMethodParameter()) {
- return addInFlow(inFlow.asMethodParameter(), node);
- } else {
- throw new Unreachable(inFlow.getClass().getTypeName());
- }
- }
-
- private TraversalContinuation<?, ?> addInFlow(AbstractFunction inFlow, Node node) {
- for (BaseInFlow baseInFlow : inFlow.getBaseInFlow()) {
- TraversalContinuation<?, ?> traversalContinuation;
- if (baseInFlow.isFieldValue()) {
- traversalContinuation = addInFlow(baseInFlow.asFieldValue(), node, inFlow);
- } else {
- assert baseInFlow.isMethodParameter();
- traversalContinuation = addInFlow(baseInFlow.asMethodParameter(), node, inFlow);
- }
- if (traversalContinuation.shouldBreak()) {
- return traversalContinuation;
- }
- }
- return TraversalContinuation.doContinue();
- }
-
- private TraversalContinuation<?, ?> addInFlow(FieldValue inFlow, Node node) {
- return addInFlow(inFlow, node, AbstractFunction.identity());
- }
-
- private TraversalContinuation<?, ?> addInFlow(
- FieldValue inFlow, Node node, AbstractFunction transferFunction) {
- assert !node.isUnknown();
-
- ProgramField field = asProgramFieldOrNull(appView.definitionFor(inFlow.getField()));
- if (field == null) {
- assert false;
- return TraversalContinuation.doContinue();
- }
-
- ValueState fieldState = getFieldState(field);
- if (fieldState.isUnknown()) {
- // The current node depends on a field for which we don't know anything.
- node.clearPredecessors();
- node.setStateToUnknown();
- return TraversalContinuation.doBreak();
- }
-
- FieldNode fieldNode = getOrCreateFieldNode(field, fieldState);
- node.addPredecessor(fieldNode, transferFunction);
- return TraversalContinuation.doContinue();
- }
-
- private TraversalContinuation<?, ?> addInFlow(MethodParameter inFlow, Node node) {
- return addInFlow(inFlow, node, AbstractFunction.identity());
- }
-
- private TraversalContinuation<?, ?> addInFlow(
- MethodParameter inFlow, Node node, AbstractFunction transferFunction) {
- ProgramMethod enclosingMethod = getEnclosingMethod(inFlow);
- if (enclosingMethod == null) {
- // This is a parameter of a single caller inlined method. Since this method has been
- // pruned, the call from inside the method no longer exists, and we can therefore safely
- // skip it.
- assert converter.getInliner().verifyIsPrunedDueToSingleCallerInlining(inFlow.getMethod());
- return TraversalContinuation.doContinue();
- }
-
- MethodState enclosingMethodState = getMethodState(enclosingMethod);
- if (enclosingMethodState.isBottom()) {
- // The current node takes a value from a dead method; no need to propagate any information
- // from the dead assignment.
- return TraversalContinuation.doContinue();
- }
-
- if (enclosingMethodState.isUnknown()) {
- // The current node depends on a parameter for which we don't know anything.
- node.clearPredecessors();
- node.setStateToUnknown();
- return TraversalContinuation.doBreak();
- }
-
- assert enclosingMethodState.isConcrete();
- assert enclosingMethodState.asConcrete().isMonomorphic();
-
- ParameterNode predecessor =
- getOrCreateParameterNode(
- enclosingMethod,
- inFlow.getIndex(),
- enclosingMethodState.asConcrete().asMonomorphic());
- node.addPredecessor(predecessor, transferFunction);
- return TraversalContinuation.doContinue();
- }
-
- private FieldNode getOrCreateFieldNode(ProgramField field, ValueState fieldState) {
- return fieldNodes.computeIfAbsent(
- field.getReference(), ignoreKey(() -> new FieldNode(field, fieldState)));
- }
-
- private ParameterNode getOrCreateParameterNode(
- ProgramMethod method, int parameterIndex, ConcreteMonomorphicMethodState methodState) {
- Int2ReferenceMap<ParameterNode> parameterNodesForMethod =
- parameterNodes.computeIfAbsent(
- method.getReference(), ignoreKey(Int2ReferenceOpenHashMap::new));
- return parameterNodesForMethod.compute(
- parameterIndex,
- (ignore, parameterNode) ->
- parameterNode != null
- ? parameterNode
- : new ParameterNode(
- method, methodState, parameterIndex, method.getArgumentType(parameterIndex)));
- }
-
- private ProgramMethod getEnclosingMethod(MethodParameter methodParameter) {
- DexMethod methodReference = methodParameter.getMethod();
- return methodReference.lookupOnProgramClass(
- asProgramClassOrNull(appView.definitionFor(methodParameter.getMethod().getHolderType())));
- }
-
- private ValueState getFieldState(ProgramField field) {
- if (field == null) {
- // Conservatively return unknown if for some reason we can't find the field.
- assert false;
- return ValueState.unknown();
- }
- return fieldStates.get(field);
- }
-
- private MethodState getMethodState(ProgramMethod method) {
- if (method == null) {
- // Conservatively return unknown if for some reason we can't find the method.
- assert false;
- return MethodState.unknown();
- }
- return methodStates.get(method);
- }
-
- @Override
- public ValueState getState(DexField field) {
- return fieldNodes.get(field).getState();
- }
-
- @Override
- public ValueState getState(BaseInFlow inFlow, Supplier<ValueState> defaultStateProvider) {
- if (inFlow.isFieldValue()) {
- FieldValue fieldValue = inFlow.asFieldValue();
- return getState(fieldValue.getField());
- } else {
- assert inFlow.isMethodParameter();
- MethodParameter methodParameter = inFlow.asMethodParameter();
- ParameterNode parameterNode =
- parameterNodes
- .getOrDefault(methodParameter.getMethod(), Int2ReferenceMaps.emptyMap())
- .get(methodParameter.getIndex());
- if (parameterNode != null) {
- return parameterNode.getState();
- }
- assert verifyMissingParameterStateIsBottom(methodParameter);
- return defaultStateProvider.get();
- }
- }
-
- private boolean verifyMissingParameterStateIsBottom(MethodParameter methodParameter) {
- ProgramMethod enclosingMethod = getEnclosingMethod(methodParameter);
- if (enclosingMethod == null) {
- assert converter
- .getInliner()
- .verifyIsPrunedDueToSingleCallerInlining(methodParameter.getMethod());
- return true;
- }
- MethodState enclosingMethodState = getMethodState(enclosingMethod);
- return enclosingMethodState.isBottom();
- }
- }
-
- public abstract static class Node {
-
- private final Set<Node> predecessors = Sets.newIdentityHashSet();
- private final Map<Node, Set<AbstractFunction>> successors = new IdentityHashMap<>();
-
- private boolean inWorklist = true;
-
- void addState(
- AppView<AppInfoWithLiveness> appView,
- ConcreteValueState stateToAdd,
- Action onChangedAction) {
- ValueState oldState = getState();
- ValueState newState =
- oldState.mutableJoin(
- appView, stateToAdd, getStaticType(), StateCloner.getCloner(), onChangedAction);
- if (newState != oldState) {
- setState(newState);
- onChangedAction.execute();
- }
- }
-
- abstract ValueState getState();
-
- abstract DexType getStaticType();
-
- abstract void setState(ValueState valueState);
-
- void setStateToUnknown() {
- setState(ValueState.unknown());
- }
-
- void addPredecessor(Node predecessor, AbstractFunction abstractFunction) {
- predecessor.successors.computeIfAbsent(this, ignoreKey(HashSet::new)).add(abstractFunction);
- predecessors.add(predecessor);
- }
-
- void clearPredecessors() {
- for (Node predecessor : predecessors) {
- predecessor.successors.remove(this);
- }
- predecessors.clear();
- }
-
- void clearPredecessors(Node cause) {
- for (Node predecessor : predecessors) {
- if (predecessor != cause) {
- predecessor.successors.remove(this);
- }
- }
- predecessors.clear();
- }
-
- Set<Node> getPredecessors() {
- return predecessors;
- }
-
- boolean hasPredecessors() {
- return !predecessors.isEmpty();
- }
-
- void clearDanglingSuccessors() {
- successors.clear();
- }
-
- Set<Node> getSuccessors() {
- return successors.keySet();
- }
-
- public void forEachSuccessor(BiConsumer<Node, Set<AbstractFunction>> consumer) {
- successors.forEach(consumer);
- }
-
- public void removeSuccessorIf(BiPredicate<Node, Set<AbstractFunction>> predicate) {
- successors.entrySet().removeIf(entry -> predicate.test(entry.getKey(), entry.getValue()));
- }
-
- boolean hasSuccessors() {
- return !successors.isEmpty();
- }
-
- boolean isBottom() {
- return getState().isBottom();
- }
-
- boolean isFieldNode() {
- return false;
- }
-
- FieldNode asFieldNode() {
- return null;
- }
-
- boolean isParameterNode() {
- return false;
- }
-
- ParameterNode asParameterNode() {
- return null;
- }
-
- boolean isEffectivelyUnknown() {
- return getState().isConcrete() && getState().asConcrete().isEffectivelyUnknown();
- }
-
- boolean isUnknown() {
- return getState().isUnknown();
- }
-
- // No need to enqueue the affected node if it is already in the worklist or if it does not have
- // any successors (i.e., the successor is a leaf).
- void addToWorkList(Deque<Node> worklist) {
- if (!inWorklist && hasSuccessors()) {
- worklist.add(this);
- inWorklist = true;
- }
- }
-
- void unsetInWorklist() {
- assert inWorklist;
- inWorklist = false;
- }
- }
-
- public static class FieldNode extends Node {
-
- private final ProgramField field;
- private ValueState fieldState;
-
- FieldNode(ProgramField field, ValueState fieldState) {
- this.field = field;
- this.fieldState = fieldState;
- }
-
- public ProgramField getField() {
- return field;
- }
-
- @Override
- DexType getStaticType() {
- return field.getType();
- }
-
- void addDefaultValue(AppView<AppInfoWithLiveness> appView, Action onChangedAction) {
- AbstractValueFactory abstractValueFactory = appView.abstractValueFactory();
- AbstractValue defaultValue;
- if (field.getAccessFlags().isStatic() && field.getDefinition().hasExplicitStaticValue()) {
- defaultValue = field.getDefinition().getStaticValue().toAbstractValue(abstractValueFactory);
- } else if (field.getType().isPrimitiveType()) {
- defaultValue = abstractValueFactory.createZeroValue();
- } else {
- defaultValue = abstractValueFactory.createUncheckedNullValue();
- }
- NonEmptyValueState fieldStateToAdd;
- if (field.getType().isArrayType()) {
- Nullability defaultNullability = Nullability.definitelyNull();
- fieldStateToAdd = ConcreteArrayTypeValueState.create(defaultNullability);
- } else if (field.getType().isClassType()) {
- assert defaultValue.isNull() || defaultValue.isSingleStringValue();
- DynamicType dynamicType =
- defaultValue.isNull()
- ? DynamicType.definitelyNull()
- : DynamicType.createExact(
- TypeElement.stringClassType(appView, Nullability.definitelyNotNull()));
- fieldStateToAdd = ConcreteClassTypeValueState.create(defaultValue, dynamicType);
- } else {
- assert field.getType().isPrimitiveType();
- fieldStateToAdd = ConcretePrimitiveTypeValueState.create(defaultValue);
- }
- if (fieldStateToAdd.isConcrete()) {
- addState(appView, fieldStateToAdd.asConcrete(), onChangedAction);
- } else {
- // We should always be able to map static field values to an unknown abstract value.
- assert false;
- setStateToUnknown();
- onChangedAction.execute();
- }
- }
-
- @Override
- ValueState getState() {
- return fieldState;
- }
-
- @Override
- void setState(ValueState fieldState) {
- this.fieldState = fieldState;
- }
-
- @Override
- boolean isFieldNode() {
- return true;
- }
-
- @Override
- FieldNode asFieldNode() {
- return this;
- }
- }
-
- static class ParameterNode extends Node {
-
- private final ProgramMethod method;
- private final ConcreteMonomorphicMethodState methodState;
- private final int parameterIndex;
- private final DexType parameterType;
-
- ParameterNode(
- ProgramMethod method,
- ConcreteMonomorphicMethodState methodState,
- int parameterIndex,
- DexType parameterType) {
- this.method = method;
- this.methodState = methodState;
- this.parameterIndex = parameterIndex;
- this.parameterType = parameterType;
- }
-
- ProgramMethod getMethod() {
- return method;
- }
-
- int getParameterIndex() {
- return parameterIndex;
- }
-
- @Override
- DexType getStaticType() {
- return parameterType;
- }
-
- @Override
- ValueState getState() {
- return methodState.getParameterState(parameterIndex);
- }
-
- @Override
- void setState(ValueState parameterState) {
- methodState.setParameterState(parameterIndex, parameterState);
- }
-
- @Override
- boolean isParameterNode() {
- return true;
- }
-
- @Override
- ParameterNode asParameterNode() {
- return this;
- }
- }
}
