diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index d394692..812fec2 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 = "1.3.27";
+  public static final String LABEL = "1.3.28";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java b/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
index 19ca504..b85fe37 100644
--- a/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
+++ b/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
@@ -489,7 +489,9 @@
 
   private static String writeMainDexList(DexApplication application, NamingLens namingLens) {
     StringBuilder builder = new StringBuilder();
-    application.mainDexList.forEach(
+    List<DexType> list = new ArrayList<>(application.mainDexList);
+    list.sort(DexType::slowCompareTo);
+    list.forEach(
         type -> builder.append(mapMainDexListName(type, namingLens)).append('\n'));
     return builder.toString();
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexAnnotation.java b/src/main/java/com/android/tools/r8/graph/DexAnnotation.java
index 73ac7fb..eda695d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexAnnotation.java
+++ b/src/main/java/com/android/tools/r8/graph/DexAnnotation.java
@@ -18,7 +18,7 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
-import java.util.Set;
+import java.util.TreeSet;
 
 public class DexAnnotation extends DexItem {
   public static final int VISIBILITY_BUILD = 0x00;
@@ -355,7 +355,7 @@
   }
 
   public static DexAnnotation createAnnotationSynthesizedClassMap(
-      Set<DexType> synthesized,
+      TreeSet<DexType> synthesized,
       DexItemFactory dexItemFactory) {
     DexValueType[] values = synthesized.stream()
         .map(DexValueType::new)
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index 6890595..00d8bdf 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -77,6 +77,7 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.TreeSet;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
@@ -393,7 +394,10 @@
     for (Map.Entry<DexProgramClass, Collection<DexProgramClass>> entry :
         originalToSynthesized.asMap().entrySet()) {
       DexProgramClass original = entry.getKey();
-      Set<DexType> synthesized = new HashSet<>();
+      // Use a tree set to make sure that we have an ordering on the types.
+      // These types are put in an array in annotations in the output and we
+      // need a consistent ordering on them.
+      TreeSet<DexType> synthesized = new TreeSet<>(DexType::slowCompareTo);
       entry.getValue()
           .stream()
           .map(dexProgramClass -> dexProgramClass.type)
diff --git a/src/test/java/com/android/tools/r8/regress/b117849037/B117849037.java b/src/test/java/com/android/tools/r8/regress/b117849037/B117849037.java
new file mode 100644
index 0000000..3d6c967
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/regress/b117849037/B117849037.java
@@ -0,0 +1,116 @@
+// Copyright (c) 2018 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.regress.b117849037;
+
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.D8Command;
+import com.android.tools.r8.OutputMode;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.utils.AndroidApp;
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.util.Arrays;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+
+interface MyConsumer<T> {
+  void accept(T element);
+}
+
+class TestClass {
+  public static void doStuff(MyConsumer<String> consumer) {
+    consumer.accept("a");
+    consumer.accept("b");
+    consumer.accept("c");
+  }
+
+  public static void add1(String s) {
+    System.out.println(s + 1);
+  }
+
+  public static void add2(String s) {
+    System.out.println(s + 2);
+  }
+
+  public static void add3(String s) {
+    System.out.println(s + 3);
+  }
+
+  public static void add4(String s) {
+    System.out.println(s + 4);
+  }
+
+  public static void add5(String s) {
+    System.out.println(s + 5);
+  }
+
+  public static void add6(String s) {
+    System.out.println(s + 6);
+  }
+
+  public static void add7(String s) {
+    System.out.println(s + 7);
+  }
+
+  public static void add8(String s) {
+    System.out.println(s + 8);
+  }
+
+  public static void add9(String s) {
+    System.out.println(s + 9);
+  }
+
+  public static void add10(String s) {
+    System.out.println(s + 10);
+  }
+
+  public static void main() {
+    doStuff(Object::hashCode);
+    doStuff(Object::toString);
+    doStuff(String::length);
+    doStuff(String::trim);
+    doStuff(TestClass::add1);
+    doStuff(TestClass::add2);
+    doStuff(TestClass::add3);
+    doStuff(TestClass::add4);
+    doStuff(TestClass::add5);
+    doStuff(TestClass::add6);
+    doStuff(TestClass::add7);
+    doStuff(TestClass::add8);
+    doStuff(TestClass::add9);
+    doStuff(TestClass::add10);
+  }
+}
+
+public class B117849037 extends TestBase {
+
+  @Rule
+  public TemporaryFolder folder = new TemporaryFolder();
+
+  public void compile(Path output) throws CompilationFailedException, IOException {
+    AndroidApp app =
+        ToolHelper.runD8(
+            D8Command.builder()
+                .addClassProgramData(ToolHelper.getClassAsBytes(TestClass.class), Origin.unknown())
+                .addClassProgramData(ToolHelper.getClassAsBytes(MyConsumer.class), Origin.unknown())
+                .setIntermediate(true));
+    app.writeToZip(output, OutputMode.DexIndexed);
+  }
+
+  @Test
+  public void testConsistentSynthesizedMapOutput() throws IOException, CompilationFailedException {
+    Path file1 = folder.getRoot().toPath().resolve("classes1.jar");
+    Path file2 = folder.getRoot().toPath().resolve("classes2.jar");
+    compile(file1);
+    compile(file2);
+    assertTrue(Arrays.equals(Files.readAllBytes(file1), Files.readAllBytes(file2)));
+  }
+}