Ensure deterministic worklist processing
Fixes: b/338885156
Change-Id: Iab48b561857dc8a9362b59023b6aed87deeb36c2
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/CastAbstractFunction.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/CastAbstractFunction.java
index ee147a5..660c42a 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/CastAbstractFunction.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/CastAbstractFunction.java
@@ -38,6 +38,20 @@
}
@Override
+ public InFlowKind getKind() {
+ return InFlowKind.ABSTRACT_FUNCTION_CAST;
+ }
+
+ @Override
+ public int internalCompareToSameKind(InFlow other) {
+ CastAbstractFunction fn = other.asCastAbstractFunction();
+ if (inFlow != fn.inFlow) {
+ return inFlow.compareTo(fn.inFlow);
+ }
+ return type.compareTo(fn.type);
+ }
+
+ @Override
public boolean isCastAbstractFunction() {
return true;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/FieldValue.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/FieldValue.java
index af8ec1a..0b9e152 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/FieldValue.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/FieldValue.java
@@ -20,6 +20,16 @@
}
@Override
+ public InFlowKind getKind() {
+ return InFlowKind.FIELD;
+ }
+
+ @Override
+ public int internalCompareToSameKind(InFlow other) {
+ return field.compareTo(other.asFieldValue().getField());
+ }
+
+ @Override
public boolean isFieldValue() {
return true;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/IdentityAbstractFunction.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/IdentityAbstractFunction.java
index 1545a75..7b20e77 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/IdentityAbstractFunction.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/IdentityAbstractFunction.java
@@ -36,6 +36,17 @@
}
@Override
+ public InFlowKind getKind() {
+ return InFlowKind.ABSTRACT_FUNCTION_IDENTITY;
+ }
+
+ @Override
+ public int internalCompareToSameKind(InFlow inFlow) {
+ assert this == inFlow;
+ return 0;
+ }
+
+ @Override
public boolean isIdentity() {
return true;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/InFlow.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/InFlow.java
index 3c071be..e261214 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/InFlow.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/InFlow.java
@@ -7,7 +7,19 @@
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.optimize.compose.UpdateChangedFlagsAbstractFunction;
-public interface InFlow {
+public interface InFlow extends Comparable<InFlow> {
+
+ @Override
+ default int compareTo(InFlow inFlow) {
+ if (getKind() == inFlow.getKind()) {
+ return internalCompareToSameKind(inFlow);
+ }
+ return getKind().ordinal() - inFlow.getKind().ordinal();
+ }
+
+ int internalCompareToSameKind(InFlow inFlow);
+
+ InFlowKind getKind();
default boolean isAbstractFunction() {
return false;
@@ -65,6 +77,10 @@
return null;
}
+ default OrAbstractFunction asOrAbstractFunction() {
+ return null;
+ }
+
default boolean isUnknownAbstractFunction() {
return false;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/InFlowKind.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/InFlowKind.java
new file mode 100644
index 0000000..d516ee1
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/InFlowKind.java
@@ -0,0 +1,15 @@
+// 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.codescanner;
+
+public enum InFlowKind {
+ ABSTRACT_FUNCTION_CAST,
+ ABSTRACT_FUNCTION_IDENTITY,
+ ABSTRACT_FUNCTION_INSTANCE_FIELD_READ,
+ ABSTRACT_FUNCTION_OR,
+ ABSTRACT_FUNCTION_UNKNOWN,
+ ABSTRACT_FUNCTION_UPDATE_CHANGED_FLAGS,
+ FIELD,
+ METHOD_PARAMETER
+}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/InstanceFieldReadAbstractFunction.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/InstanceFieldReadAbstractFunction.java
index 366dea4..560f00d 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/InstanceFieldReadAbstractFunction.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/InstanceFieldReadAbstractFunction.java
@@ -63,11 +63,26 @@
}
@Override
+ public InFlowKind getKind() {
+ return InFlowKind.ABSTRACT_FUNCTION_INSTANCE_FIELD_READ;
+ }
+
+ @Override
public boolean hasSingleInFlow() {
return false;
}
@Override
+ public int internalCompareToSameKind(InFlow other) {
+ InstanceFieldReadAbstractFunction fn = other.asInstanceFieldReadAbstractFunction();
+ int result = receiver.compareTo(fn.receiver);
+ if (result == 0) {
+ result = field.compareTo(fn.field);
+ }
+ return result;
+ }
+
+ @Override
public boolean isInstanceFieldReadAbstractFunction() {
return true;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodParameter.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodParameter.java
index b8481e4..1c83bfa 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodParameter.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodParameter.java
@@ -7,6 +7,7 @@
import com.android.tools.r8.graph.DexClassAndMethod;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.utils.BooleanUtils;
import java.util.Objects;
public class MethodParameter implements BaseInFlow {
@@ -29,6 +30,11 @@
return new MethodParameter(method, index, true);
}
+ @Override
+ public InFlowKind getKind() {
+ return InFlowKind.METHOD_PARAMETER;
+ }
+
public DexMethod getMethod() {
return method;
}
@@ -42,6 +48,21 @@
}
@Override
+ public int internalCompareToSameKind(InFlow other) {
+ MethodParameter methodParameter = other.asMethodParameter();
+ int result = method.compareTo(methodParameter.method);
+ if (result == 0) {
+ result = index - methodParameter.index;
+ }
+ if (result == 0) {
+ result =
+ BooleanUtils.intValue(isMethodStatic)
+ - BooleanUtils.intValue(methodParameter.isMethodStatic);
+ }
+ return result;
+ }
+
+ @Override
public boolean isMethodParameter() {
return true;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/OrAbstractFunction.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/OrAbstractFunction.java
index ca1223f..c5f9cc5 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/OrAbstractFunction.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/OrAbstractFunction.java
@@ -27,6 +27,11 @@
}
@Override
+ public OrAbstractFunction asOrAbstractFunction() {
+ return this;
+ }
+
+ @Override
public ValueState apply(
AppView<AppInfoWithLiveness> appView,
FlowGraphStateProvider flowGraphStateProvider,
@@ -55,6 +60,21 @@
}
@Override
+ public InFlowKind getKind() {
+ return InFlowKind.ABSTRACT_FUNCTION_OR;
+ }
+
+ @Override
+ public int internalCompareToSameKind(InFlow other) {
+ OrAbstractFunction fn = other.asOrAbstractFunction();
+ int result = inFlow.compareTo(fn.inFlow);
+ if (result == 0) {
+ result = constant.getIntValue() - fn.constant.getIntValue();
+ }
+ return result;
+ }
+
+ @Override
@SuppressWarnings("EqualsGetClass")
public boolean equals(Object obj) {
if (this == obj) {
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/UnknownAbstractFunction.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/UnknownAbstractFunction.java
index f9ffd98..4a4a665 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/UnknownAbstractFunction.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/UnknownAbstractFunction.java
@@ -36,6 +36,17 @@
}
@Override
+ public InFlowKind getKind() {
+ return InFlowKind.ABSTRACT_FUNCTION_UNKNOWN;
+ }
+
+ @Override
+ public int internalCompareToSameKind(InFlow inFlow) {
+ assert this == inFlow;
+ return 0;
+ }
+
+ @Override
public boolean isUnknownAbstractFunction() {
return true;
}
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
index e0e8d9f..58ebf78 100644
--- 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
@@ -18,29 +18,30 @@
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.WorkList;
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.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.Set;
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;
+ private final LinkedHashMap<DexField, FlowGraphFieldNode> fieldNodes;
+ private final LinkedHashMap<DexMethod, Int2ReferenceMap<FlowGraphParameterNode>> parameterNodes;
public FlowGraph(
- Map<DexField, FlowGraphFieldNode> fieldNodes,
- Map<DexMethod, Int2ReferenceMap<FlowGraphParameterNode>> parameterNodes) {
+ LinkedHashMap<DexField, FlowGraphFieldNode> fieldNodes,
+ LinkedHashMap<DexMethod, Int2ReferenceMap<FlowGraphParameterNode>> parameterNodes) {
this.fieldNodes = fieldNodes;
this.parameterNodes = parameterNodes;
}
- public FlowGraph(Collection<FlowGraphNode> nodes) {
- this(new IdentityHashMap<>(), new IdentityHashMap<>());
+ public FlowGraph(LinkedHashSet<FlowGraphNode> nodes) {
+ this(new LinkedHashMap<>(), new LinkedHashMap<>());
for (FlowGraphNode node : nodes) {
if (node.isFieldNode()) {
FlowGraphFieldNode fieldNode = node.asFieldNode();
@@ -63,6 +64,11 @@
return new FlowGraphBuilder(appView, converter, fieldStates, methodStates);
}
+ @Override
+ public Set<FlowGraphNode> computeStronglyConnectedComponent(FlowGraphNode node) {
+ return computeStronglyConnectedComponent(node, WorkList.newWorkList(new LinkedHashSet<>()));
+ }
+
public void forEachFieldNode(Consumer<? super FlowGraphFieldNode> consumer) {
fieldNodes.values().forEach(consumer);
}
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
index 45ecb34..d564575 100644
--- 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
@@ -27,13 +27,14 @@
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.ListUtils;
import com.android.tools.r8.utils.TraversalContinuation;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMaps;
import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
-import java.util.IdentityHashMap;
+import java.util.Comparator;
+import java.util.LinkedHashMap;
import java.util.List;
-import java.util.Map;
public class FlowGraphBuilder {
@@ -42,9 +43,9 @@
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<>();
+ private final LinkedHashMap<DexField, FlowGraphFieldNode> fieldNodes = new LinkedHashMap<>();
+ private final LinkedHashMap<DexMethod, Int2ReferenceMap<FlowGraphParameterNode>> parameterNodes =
+ new LinkedHashMap<>();
public FlowGraphBuilder(
AppView<AppInfoWithLiveness> appView,
@@ -58,7 +59,7 @@
}
public FlowGraphBuilder addClasses() {
- appView.appInfo().classes().forEach(this::add);
+ appView.appInfo().classesWithDeterministicOrder().forEach(this::add);
return this;
}
@@ -94,7 +95,9 @@
}
FlowGraphFieldNode node = getOrCreateFieldNode(field, concreteFieldState);
- for (InFlow inFlow : concreteFieldState.getInFlow()) {
+ List<InFlow> inFlowWithDeterministicOrder =
+ ListUtils.sort(concreteFieldState.getInFlow(), Comparator.naturalOrder());
+ for (InFlow inFlow : inFlowWithDeterministicOrder) {
if (addInFlow(inFlow, node).shouldBreak()) {
assert node.isUnknown();
break;
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
index 7e9e448..7f9f0f0 100644
--- 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
@@ -16,19 +16,18 @@
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.LinkedHashMap;
+import java.util.LinkedHashSet;
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 final LinkedHashSet<FlowGraphNode> predecessors = new LinkedHashSet<>();
+ private final LinkedHashMap<FlowGraphNode, LinkedHashSet<AbstractFunction>> successors =
+ new LinkedHashMap<>();
@CheckDiscard private boolean debug = false;
@@ -76,7 +75,10 @@
}
void addPredecessor(FlowGraphNode predecessor, AbstractFunction abstractFunction) {
- predecessor.successors.computeIfAbsent(this, ignoreKey(HashSet::new)).add(abstractFunction);
+ predecessor
+ .successors
+ .computeIfAbsent(this, ignoreKey(LinkedHashSet::new))
+ .add(abstractFunction);
predecessors.add(predecessor);
}
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 2cdcf24..796f991 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
@@ -34,6 +34,7 @@
import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Deque;
+import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
@@ -98,7 +99,12 @@
.build();
List<Set<FlowGraphNode>> stronglyConnectedComponents =
flowGraph.computeStronglyConnectedComponents();
- return ListUtils.map(stronglyConnectedComponents, FlowGraph::new);
+ List<LinkedHashSet<FlowGraphNode>> stronglyConnectedComponentsWithDeterministicOrder =
+ ListUtils.map(
+ stronglyConnectedComponents,
+ stronglyConnectedComponent ->
+ (LinkedHashSet<FlowGraphNode>) stronglyConnectedComponent);
+ return ListUtils.map(stronglyConnectedComponentsWithDeterministicOrder, FlowGraph::new);
}
private Map<FlowGraph, Deque<FlowGraphNode>> includeDefaultValuesInFieldStates(
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/utils/BidirectedGraph.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/utils/BidirectedGraph.java
index b7442b5..9427213 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/utils/BidirectedGraph.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/utils/BidirectedGraph.java
@@ -37,11 +37,16 @@
}
public Set<T> computeStronglyConnectedComponent(T node) {
- WorkList<T> worklist = WorkList.newEqualityWorkList(node);
+ return computeStronglyConnectedComponent(node, WorkList.newEqualityWorkList());
+ }
+
+ protected Set<T> computeStronglyConnectedComponent(T node, WorkList<T> worklist) {
+ assert worklist.isEmpty();
+ worklist.addIfNotSeen(node);
while (worklist.hasNext()) {
T current = worklist.next();
forEachNeighbor(current, worklist::addIfNotSeen);
}
- return worklist.getSeenSet();
+ return worklist.getMutableSeenSet();
}
}
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 2d940e9..46c4d58 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
@@ -14,6 +14,7 @@
import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteValueState;
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.InFlowKind;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.OrAbstractFunction;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.ValueState;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
@@ -123,6 +124,16 @@
}
@Override
+ public InFlowKind getKind() {
+ return InFlowKind.ABSTRACT_FUNCTION_UPDATE_CHANGED_FLAGS;
+ }
+
+ @Override
+ public int internalCompareToSameKind(InFlow other) {
+ return inFlow.compareTo(other.asUpdateChangedFlagsAbstractFunction().inFlow);
+ }
+
+ @Override
public boolean isUpdateChangedFlagsAbstractFunction() {
return true;
}
