diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 0a23b2c..faebb92 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "2.1.70";
+  public static final String LABEL = "2.1.71";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/ClassTypeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/ClassTypeElement.java
index e71ef7d..edd1b91 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/ClassTypeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ClassTypeElement.java
@@ -16,6 +16,7 @@
 import java.util.Collections;
 import java.util.HashSet;
 import java.util.IdentityHashMap;
+import java.util.List;
 import java.util.Map;
 import java.util.Objects;
 import java.util.Queue;
@@ -132,7 +133,10 @@
     builder.append(" {");
     Set<DexType> interfaces = getInterfaces();
     if (interfaces != null) {
-      builder.append(interfaces.stream().map(DexType::toString).collect(Collectors.joining(", ")));
+      List<DexType> sortedInterfaces = new ArrayList<>(interfaces);
+      sortedInterfaces.sort(DexType::slowCompareTo);
+      builder.append(
+          sortedInterfaces.stream().map(DexType::toString).collect(Collectors.joining(", ")));
     }
     builder.append("}");
     return builder.toString();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/RedundantFieldLoadElimination.java b/src/main/java/com/android/tools/r8/ir/optimize/RedundantFieldLoadElimination.java
index ef81097..6fe5c98 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/RedundantFieldLoadElimination.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/RedundantFieldLoadElimination.java
@@ -99,6 +99,11 @@
       it.removeOrReplaceByDebugLocalRead();
       value.uniquePhiUsers().forEach(Phi::removeTrivialPhi);
     }
+
+    @Override
+    public String toString() {
+      return "ExistingValue(v" + value.getNumber() + ")";
+    }
   }
 
   private class MaterializableValue implements FieldValue {
@@ -361,7 +366,7 @@
 
     InstanceFieldInitializationInfoCollection fieldInitializationInfos =
         instanceInitializerInfo.fieldInitializationInfos();
-    fieldInitializationInfos.forEach(
+    fieldInitializationInfos.forEachWithDeterministicOrder(
         appView,
         (field, info) -> {
           if (!appView.appInfo().withLiveness().mayPropagateValueFor(field.field)) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/field/EmptyInstanceFieldInitializationInfoCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/info/field/EmptyInstanceFieldInitializationInfoCollection.java
index fd7a84f..271f225 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/field/EmptyInstanceFieldInitializationInfoCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/field/EmptyInstanceFieldInitializationInfoCollection.java
@@ -35,6 +35,13 @@
   }
 
   @Override
+  public void forEachWithDeterministicOrder(
+      DexDefinitionSupplier definitions,
+      BiConsumer<DexEncodedField, InstanceFieldInitializationInfo> consumer) {
+    // Intentionally empty.
+  }
+
+  @Override
   public InstanceFieldInitializationInfo get(DexEncodedField field) {
     return UnknownInstanceFieldInitializationInfo.getInstance();
   }
@@ -49,4 +56,9 @@
       AppView<AppInfoWithLiveness> appView, GraphLense lens) {
     return this;
   }
+
+  @Override
+  public String toString() {
+    return "EmptyInstanceFieldInitializationInfoCollection";
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldArgumentInitializationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldArgumentInitializationInfo.java
index 757eec8..fee31d5 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldArgumentInitializationInfo.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldArgumentInitializationInfo.java
@@ -43,4 +43,9 @@
     // initialization info.
     return this;
   }
+
+  @Override
+  public String toString() {
+    return "InstanceFieldArgumentInitializationInfo(argumentIndex=" + argumentIndex + ")";
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldInitializationInfoCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldInitializationInfoCollection.java
index 3ff1799..6e5e45c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldInitializationInfoCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldInitializationInfoCollection.java
@@ -10,8 +10,7 @@
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import java.util.IdentityHashMap;
-import java.util.Map;
+import java.util.TreeMap;
 import java.util.function.BiConsumer;
 
 /**
@@ -31,6 +30,10 @@
       DexDefinitionSupplier definitions,
       BiConsumer<DexEncodedField, InstanceFieldInitializationInfo> consumer);
 
+  public abstract void forEachWithDeterministicOrder(
+      DexDefinitionSupplier definitions,
+      BiConsumer<DexEncodedField, InstanceFieldInitializationInfo> consumer);
+
   public abstract InstanceFieldInitializationInfo get(DexEncodedField field);
 
   public abstract boolean isEmpty();
@@ -40,7 +43,8 @@
 
   public static class Builder {
 
-    Map<DexField, InstanceFieldInitializationInfo> infos = new IdentityHashMap<>();
+    TreeMap<DexField, InstanceFieldInitializationInfo> infos =
+        new TreeMap<>(DexField::slowCompareTo);
 
     public void recordInitializationInfo(
         DexEncodedField field, InstanceFieldInitializationInfo info) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldTypeInitializationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldTypeInitializationInfo.java
index 3bfce16..8e3b0b9 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldTypeInitializationInfo.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/field/InstanceFieldTypeInitializationInfo.java
@@ -87,4 +87,9 @@
     return Objects.equals(dynamicLowerBoundType, info.dynamicLowerBoundType)
         && Objects.equals(dynamicUpperBoundType, info.dynamicUpperBoundType);
   }
+
+  @Override
+  public String toString() {
+    return "InstanceFieldTypeInitializationInfo";
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/field/NonTrivialInstanceFieldInitializationInfoCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/info/field/NonTrivialInstanceFieldInitializationInfoCollection.java
index 2fe8a19..672471c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/field/NonTrivialInstanceFieldInitializationInfoCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/field/NonTrivialInstanceFieldInitializationInfoCollection.java
@@ -10,17 +10,20 @@
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import java.util.Map;
+import com.android.tools.r8.utils.StringUtils;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.TreeMap;
 import java.util.function.BiConsumer;
 
 /** See {@link InstanceFieldArgumentInitializationInfo}. */
 public class NonTrivialInstanceFieldInitializationInfoCollection
     extends InstanceFieldInitializationInfoCollection {
 
-  private final Map<DexField, InstanceFieldInitializationInfo> infos;
+  private final TreeMap<DexField, InstanceFieldInitializationInfo> infos;
 
   NonTrivialInstanceFieldInitializationInfoCollection(
-      Map<DexField, InstanceFieldInitializationInfo> infos) {
+      TreeMap<DexField, InstanceFieldInitializationInfo> infos) {
     assert !infos.isEmpty();
     assert infos.values().stream().noneMatch(InstanceFieldInitializationInfo::isUnknown);
     this.infos = infos;
@@ -42,6 +45,14 @@
   }
 
   @Override
+  public void forEachWithDeterministicOrder(
+      DexDefinitionSupplier definitions,
+      BiConsumer<DexEncodedField, InstanceFieldInitializationInfo> consumer) {
+    // We currently use a sorted backing and can therefore simply use forEach().
+    forEach(definitions, consumer);
+  }
+
+  @Override
   public InstanceFieldInitializationInfo get(DexEncodedField field) {
     return infos.getOrDefault(field.field, UnknownInstanceFieldInitializationInfo.getInstance());
   }
@@ -65,4 +76,13 @@
         });
     return builder.build();
   }
+
+  @Override
+  public String toString() {
+    List<String> strings = new ArrayList<>();
+    infos.forEach((field, info) -> strings.add(field.toSourceString() + " -> " + info));
+    return "NonTrivialInstanceFieldInitializationInfoCollection("
+        + StringUtils.join(strings, "; ")
+        + ")";
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/field/UnknownInstanceFieldInitializationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/field/UnknownInstanceFieldInitializationInfo.java
index b2b6ce9..5303c9e 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/field/UnknownInstanceFieldInitializationInfo.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/field/UnknownInstanceFieldInitializationInfo.java
@@ -33,4 +33,9 @@
       AppView<AppInfoWithLiveness> appView, GraphLense lens) {
     return this;
   }
+
+  @Override
+  public String toString() {
+    return "UnknownInstanceFieldInitializationInfo";
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/initializer/DefaultInstanceInitializerInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/initializer/DefaultInstanceInitializerInfo.java
index 4065fb0..05ad1bd 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/initializer/DefaultInstanceInitializerInfo.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/initializer/DefaultInstanceInitializerInfo.java
@@ -59,4 +59,9 @@
       AppView<AppInfoWithLiveness> appView, GraphLense lens) {
     return this;
   }
+
+  @Override
+  public String toString() {
+    return "DefaultInstanceInitializerInfo";
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/initializer/NonTrivialInstanceInitializerInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/initializer/NonTrivialInstanceInitializerInfo.java
index f549927..770b59c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/initializer/NonTrivialInstanceInitializerInfo.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/initializer/NonTrivialInstanceInitializerInfo.java
@@ -92,6 +92,11 @@
         lens.getRenamedMethodSignature(parent));
   }
 
+  @Override
+  public String toString() {
+    return "NonTrivialInstanceInitializerInfo(" + fieldInitializationInfos + ")";
+  }
+
   public static class Builder {
 
     private final InstanceFieldInitializationInfoCollection instanceFieldInitializationInfos;