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;
   }