diff --git a/src/main/java/com/android/tools/r8/D8.java b/src/main/java/com/android/tools/r8/D8.java
index 466a26f..e920ad3 100644
--- a/src/main/java/com/android/tools/r8/D8.java
+++ b/src/main/java/com/android/tools/r8/D8.java
@@ -148,10 +148,12 @@
     if (options.testing.dontCreateMarkerInD8) {
       return null;
     }
-    Marker marker = new Marker(Tool.D8)
-        .setVersion(Version.LABEL)
-        .setCompilationMode(options.debug ? CompilationMode.DEBUG : CompilationMode.RELEASE)
-        .setMinApi(options.minApiLevel);
+    Marker marker =
+        new Marker(Tool.D8)
+            .setVersion(Version.LABEL)
+            .setCompilationMode(options.debug ? CompilationMode.DEBUG : CompilationMode.RELEASE)
+            .setMinApi(options.minApiLevel)
+            .setBuildId(options.buildId);
     if (Version.isDev()) {
       marker.setSha1(VersionProperties.INSTANCE.getSha());
     }
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 75b0c81..36d4cf7 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -169,10 +169,14 @@
     if (options.hasMarker()) {
       return options.getMarker();
     }
-    Marker marker = new Marker(Tool.R8)
-        .setVersion(Version.LABEL)
-        .setCompilationMode(options.debug ? CompilationMode.DEBUG : CompilationMode.RELEASE)
-        .setMinApi(options.minApiLevel);
+    Marker marker =
+        new Marker(Tool.R8)
+            .setVersion(Version.LABEL)
+            .setCompilationMode(options.debug ? CompilationMode.DEBUG : CompilationMode.RELEASE)
+            .setBuildId(options.buildId);
+    if (!options.isGeneratingClassFiles()) {
+      marker.setMinApi(options.minApiLevel);
+    }
     if (Version.isDev()) {
       marker.setSha1(VersionProperties.INSTANCE.getSha());
     }
@@ -629,8 +633,7 @@
               namingLens,
               options.lineNumberOptimization == LineNumberOptimization.OFF);
       timing.end();
-      proguardMapSupplier =
-          ProguardMapSupplier.fromClassNameMapper(classNameMapper, options.minApiLevel);
+      proguardMapSupplier = ProguardMapSupplier.fromClassNameMapper(classNameMapper, options);
 
       // If a method filter is present don't produce output since the application is likely partial.
       if (options.hasMethodsFilter()) {
diff --git a/src/main/java/com/android/tools/r8/dex/Marker.java b/src/main/java/com/android/tools/r8/dex/Marker.java
index 3d977f6..41270da 100644
--- a/src/main/java/com/android/tools/r8/dex/Marker.java
+++ b/src/main/java/com/android/tools/r8/dex/Marker.java
@@ -21,6 +21,7 @@
   public static final String MIN_API = "min-api";
   public static final String SHA1 = "sha-1";
   public static final String COMPILATION_MODE = "compilation-mode";
+  public static final String BUILD_ID = "build-id";
 
   public enum Tool {D8, R8}
 
@@ -93,6 +94,16 @@
     return this;
   }
 
+  public String getBuildId() {
+    return jsonObject.get(BUILD_ID).getAsString();
+  }
+
+  public Marker setBuildId(String uuid) {
+    assert !jsonObject.has(BUILD_ID);
+    jsonObject.addProperty(BUILD_ID, uuid);
+    return this;
+  }
+
   @Override
   public String toString() {
     // In order to make printing of markers deterministic we sort the entries by key.
diff --git a/src/main/java/com/android/tools/r8/naming/ProguardMapSupplier.java b/src/main/java/com/android/tools/r8/naming/ProguardMapSupplier.java
index 5ee5891..d905116 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMapSupplier.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMapSupplier.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.Version;
 import com.android.tools.r8.graph.DexApplication;
+import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.VersionProperties;
 import java.io.ByteArrayOutputStream;
 import java.io.IOException;
@@ -18,39 +19,38 @@
   public static final String MARKER_KEY_COMPILER_VERSION = "compiler_version";
   public static final String MARKER_KEY_COMPILER_HASH = "compiler_hash";
   public static final String MARKER_KEY_MIN_API = "min_api";
+  public static final String MARKER_KEY_BUILD_ID = "build_id";
 
   public static ProguardMapSupplier fromClassNameMapper(
-      ClassNameMapper classNameMapper, int minApiLevel) {
-    return new ProguardMapSupplier(classNameMapper, minApiLevel);
+      ClassNameMapper classNameMapper, InternalOptions options) {
+    return new ProguardMapSupplier(true, classNameMapper, null, null, options);
   }
 
   public static ProguardMapSupplier fromNamingLens(
-      NamingLens namingLens, DexApplication dexApplication, int minApiLevel) {
-    return new ProguardMapSupplier(namingLens, dexApplication, minApiLevel);
+      NamingLens namingLens, DexApplication dexApplication, InternalOptions options) {
+    return new ProguardMapSupplier(false, null, namingLens, dexApplication, options);
   }
 
-  private ProguardMapSupplier(ClassNameMapper classNameMapper, int minApiLevel) {
-    this.useClassNameMapper = true;
+  public ProguardMapSupplier(
+      boolean useClassNameMapper,
+      ClassNameMapper classNameMapper,
+      NamingLens namingLens,
+      DexApplication application,
+      InternalOptions options) {
+    this.useClassNameMapper = useClassNameMapper;
     this.classNameMapper = classNameMapper;
-    this.namingLens = null;
-    this.application = null;
-    this.minApiLevel = minApiLevel;
-  }
-
-  private ProguardMapSupplier(
-      NamingLens namingLens, DexApplication dexApplication, int minApiLevel) {
-    this.useClassNameMapper = false;
-    this.classNameMapper = null;
     this.namingLens = namingLens;
-    this.application = dexApplication;
-    this.minApiLevel = minApiLevel;
+    this.application = application;
+    this.minApiLevel = options.isGeneratingClassFiles() ? null : options.minApiLevel;
+    this.buildId = options.buildId;
   }
 
   private final boolean useClassNameMapper;
   private final ClassNameMapper classNameMapper;
   private final NamingLens namingLens;
   private final DexApplication application;
-  private final int minApiLevel;
+  private final Integer minApiLevel;
+  private final String buildId;
 
   public String get() {
     String body = getBody();
@@ -61,23 +61,23 @@
     if (Version.isDev()) {
       shaLine = "# " + MARKER_KEY_COMPILER_HASH + ": " + VersionProperties.INSTANCE.getSha() + "\n";
     }
-    return "# "
-        + MARKER_KEY_COMPILER
-        + ": "
-        + MARKER_VALUE_COMPILER
-        + "\n"
-        + "# "
-        + MARKER_KEY_COMPILER_VERSION
-        + ": "
-        + Version.LABEL
-        + "\n"
-        + "# "
-        + MARKER_KEY_MIN_API
-        + ": "
-        + minApiLevel
-        + "\n"
-        + shaLine
-        + body;
+    StringBuilder builder = new StringBuilder();
+    builder.append(
+        "# "
+            + MARKER_KEY_COMPILER
+            + ": "
+            + MARKER_VALUE_COMPILER
+            + "\n"
+            + "# "
+            + MARKER_KEY_COMPILER_VERSION
+            + ": "
+            + Version.LABEL
+            + "\n");
+    if (minApiLevel != null) {
+      builder.append("# " + MARKER_KEY_MIN_API + ": " + minApiLevel + "\n");
+    }
+    builder.append(shaLine + "# " + MARKER_KEY_BUILD_ID + ": " + buildId + "\n" + body);
+    return builder.toString();
   }
 
   private String getBody() {
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index 3997982..09f2ef7 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -28,13 +28,16 @@
 import com.android.tools.r8.utils.IROrdering.NondeterministicIROrdering;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import java.nio.ByteBuffer;
 import java.nio.file.Path;
 import java.util.ArrayList;
+import java.util.Base64;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.TreeSet;
+import java.util.UUID;
 import java.util.function.Consumer;
 
 public class InternalOptions {
@@ -63,6 +66,19 @@
   public final List<DataResourceProvider> dataResourceProviders = new ArrayList<>();
   public DataResourceConsumer dataResourceConsumer;
 
+  // Generate 11-char unique random string using the UUID generator.
+  private static String generateBuildId() {
+    UUID uuid = UUID.randomUUID();
+    return Base64.getEncoder()
+        .withoutPadding()
+        .encodeToString(
+            ByteBuffer.allocate(8)
+                .putLong(uuid.getLeastSignificantBits() ^ uuid.getMostSignificantBits())
+                .array());
+  }
+
+  public final String buildId = generateBuildId();
+
   // Constructor for testing and/or other utilities.
   public InternalOptions() {
     reporter = new Reporter();
diff --git a/src/test/java/com/android/tools/r8/ExtractMarkerTest.java b/src/test/java/com/android/tools/r8/ExtractMarkerTest.java
index 6a47607..48482f8 100644
--- a/src/test/java/com/android/tools/r8/ExtractMarkerTest.java
+++ b/src/test/java/com/android/tools/r8/ExtractMarkerTest.java
@@ -4,24 +4,36 @@
 package com.android.tools.r8;
 
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
 import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.dex.Marker;
 import com.android.tools.r8.dex.Marker.Tool;
+import com.android.tools.r8.utils.InternalOptions;
 import java.nio.file.Paths;
 import java.util.Collection;
 import java.util.Set;
 import org.junit.Test;
 
 public class ExtractMarkerTest {
+  private static final String CLASS_FILE =
+      ToolHelper.EXAMPLES_BUILD_DIR + "classes/trivial/Trivial.class";
+
+  private static void verifyMarker(Marker marker, Tool tool) {
+    assertEquals(tool, marker.getTool());
+    assertEquals(Version.LABEL, marker.getVersion());
+    assertEquals(CompilationMode.DEBUG.toString().toLowerCase(), marker.getCompilationMode());
+    String anotherBuildId = new InternalOptions().buildId;
+    assertNotEquals(anotherBuildId, marker.getBuildId());
+  }
 
   @Test
   public void extractMarkerTestDex() throws CompilationFailedException {
-    String classFile = ToolHelper.EXAMPLES_BUILD_DIR + "classes/trivial/Trivial.class";
     boolean[] testExecuted = {false};
+
     D8.run(
         D8Command.builder()
-            .addProgramFiles(Paths.get(classFile))
+            .addProgramFiles(Paths.get(CLASS_FILE))
             .setProgramConsumer(
                 new DexIndexedConsumer.ForwardingConsumer(null) {
                   @Override
@@ -39,11 +51,7 @@
                     } catch (Exception e) {
                       throw new RuntimeException(e);
                     }
-                    assertEquals(Tool.D8, marker.getTool());
-                    assertEquals(Version.LABEL, marker.getVersion());
-                    assertEquals(
-                        CompilationMode.DEBUG.toString().toLowerCase(),
-                        marker.getCompilationMode());
+                    verifyMarker(marker, Tool.D8);
                     testExecuted[0] = true;
                   }
                 })
@@ -53,11 +61,10 @@
 
   @Test
   public void extractMarkerTestCf() throws CompilationFailedException {
-    String classFile = ToolHelper.EXAMPLES_BUILD_DIR + "classes/trivial/Trivial.class";
     boolean[] testExecuted = {false};
     R8.run(
         R8Command.builder()
-            .addProgramFiles(Paths.get(classFile))
+            .addProgramFiles(Paths.get(CLASS_FILE))
             .addLibraryFiles(ToolHelper.getJava8RuntimeJar())
             .setMode(CompilationMode.DEBUG)
             .setDisableTreeShaking(true)
@@ -75,11 +82,7 @@
                     } catch (Exception e) {
                       throw new RuntimeException(e);
                     }
-                    assertEquals(Tool.R8, marker.getTool());
-                    assertEquals(Version.LABEL, marker.getVersion());
-                    assertEquals(
-                        CompilationMode.DEBUG.toString().toLowerCase(),
-                        marker.getCompilationMode());
+                    verifyMarker(marker, Tool.R8);
                     testExecuted[0] = true;
                   }
                 })
diff --git a/src/test/java/com/android/tools/r8/ProguardMapMarkerTest.java b/src/test/java/com/android/tools/r8/ProguardMapMarkerTest.java
index 6310054..a3dedd9 100644
--- a/src/test/java/com/android/tools/r8/ProguardMapMarkerTest.java
+++ b/src/test/java/com/android/tools/r8/ProguardMapMarkerTest.java
@@ -6,55 +6,125 @@
 
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
 
+import com.android.tools.r8.dex.Marker;
 import com.android.tools.r8.naming.ProguardMapSupplier;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.VersionProperties;
 import java.nio.file.Paths;
+import java.util.Collection;
 import java.util.HashSet;
 import java.util.Set;
 import org.junit.Test;
 
 public class ProguardMapMarkerTest {
+  private static final int EXPECTED_NUMBER_OF_KEYS_DEX = 5;
+  private static final int EXPECTED_NUMBER_OF_KEYS_CF = 4;
+  private static final String CLASS_FILE =
+      ToolHelper.EXAMPLES_BUILD_DIR + "classes/trivial/Trivial.class";
+
   @Test
   public void proguardMapMarkerTest24() throws CompilationFailedException {
-    proguardMapMarkerTest(AndroidApiLevel.N);
+    proguardMapMarkerTestDex(AndroidApiLevel.N);
   }
 
   @Test
   public void proguardMapMarkerTest26() throws CompilationFailedException {
-    proguardMapMarkerTest(AndroidApiLevel.O);
+    proguardMapMarkerTestDex(AndroidApiLevel.O);
   }
 
-  private void proguardMapMarkerTest(AndroidApiLevel minApiLevel) throws CompilationFailedException {
-    String classFile = ToolHelper.EXAMPLES_BUILD_DIR + "classes/trivial/Trivial.class";
+  private static class BuildIds {
+    String fromProgram = null;
+    String fromMap = null;
+  }
+
+  private void proguardMapMarkerTestDex(AndroidApiLevel minApiLevel)
+      throws CompilationFailedException {
+    BuildIds buildIds = new BuildIds();
     R8.run(
         R8Command.builder()
-            .addProgramFiles(Paths.get(classFile))
+            .addProgramFiles(Paths.get(CLASS_FILE))
+            .setDisableTreeShaking(true)
             .setProgramConsumer(
-                new DexIndexedConsumer() {
+                new DexIndexedConsumer.ForwardingConsumer(null) {
                   @Override
                   public void accept(
                       int fileIndex,
                       ByteDataView data,
                       Set<String> descriptors,
-                      DiagnosticsHandler handler) {}
-
-                  @Override
-                  public void finished(DiagnosticsHandler handler) {}
+                      DiagnosticsHandler handler) {
+                    Marker marker;
+                    try {
+                      Collection<Marker> markers =
+                          ExtractMarker.extractMarkerFromDexProgramData(data.copyByteData());
+                      assertEquals(1, markers.size());
+                      marker = markers.iterator().next();
+                    } catch (Exception e) {
+                      throw new RuntimeException(e);
+                    }
+                    buildIds.fromProgram = marker.getBuildId();
+                  }
                 })
             .addLibraryFiles(ToolHelper.getAndroidJar(minApiLevel))
             .setMinApiLevel(minApiLevel.getLevel())
             .setProguardMapConsumer(
                 (proguardMap, handler) -> {
-                  verifyMarkers(proguardMap, minApiLevel.getLevel());
+                  buildIds.fromMap =
+                      verifyMarkersGetBuildId(
+                          proguardMap, minApiLevel.getLevel(), EXPECTED_NUMBER_OF_KEYS_DEX);
                 })
             .build());
+    verifyBuildIds(buildIds);
   }
 
-  private static void verifyMarkers(String proguardMap, int minApiLevel) {
+  private void verifyBuildIds(BuildIds buildIds) {
+    assertTrue(buildIds.fromProgram != null && buildIds.fromProgram.length() > 0);
+    assertTrue(buildIds.fromMap != null && buildIds.fromMap.length() > 0);
+    assertEquals(buildIds.fromMap, buildIds.fromProgram);
+  }
+
+  @Test
+  public void proguardMapMarkerTestCf() throws CompilationFailedException {
+    BuildIds buildIds = new BuildIds();
+    R8.run(
+        R8Command.builder()
+            .addProgramFiles(Paths.get(CLASS_FILE))
+            .setDisableTreeShaking(true)
+            .setProgramConsumer(
+                new ClassFileConsumer.ForwardingConsumer(null) {
+                  @Override
+                  public void accept(
+                      ByteDataView data, String descriptor, DiagnosticsHandler handler) {
+                    Marker marker;
+                    try {
+                      Collection<Marker> markers =
+                          ExtractMarker.extractMarkerFromClassProgramData(data.copyByteData());
+                      assertEquals(1, markers.size());
+                      marker = markers.iterator().next();
+                    } catch (Exception e) {
+                      throw new RuntimeException(e);
+                    }
+                    buildIds.fromProgram = marker.getBuildId();
+                  }
+                })
+            .addLibraryFiles(ToolHelper.getJava8RuntimeJar())
+            .setProguardMapConsumer(
+                (proguardMap, handler) -> {
+                  buildIds.fromMap =
+                      verifyMarkersGetBuildId(proguardMap, null, EXPECTED_NUMBER_OF_KEYS_CF);
+                })
+            .build());
+    verifyBuildIds(buildIds);
+  }
+
+  private static String verifyMarkersGetBuildId(
+      String proguardMap, Integer minApiLevel, int expectedNumberOfKeys) {
     String[] lines = proguardMap.split("\n");
     Set<String> keysFound = new HashSet<>();
+    String buildId = null;
     for (String line : lines) {
       if (!line.startsWith("#")) {
         continue;
@@ -71,14 +141,20 @@
       } else if (key.equals(ProguardMapSupplier.MARKER_KEY_COMPILER_VERSION)) {
         assertEquals(Version.LABEL, value);
       } else if (key.equals(ProguardMapSupplier.MARKER_KEY_MIN_API)) {
-        assertEquals(minApiLevel, Integer.parseInt(value));
+        assertNotNull(minApiLevel);
+        assertEquals(minApiLevel.intValue(), Integer.parseInt(value));
       } else if (key.equals(ProguardMapSupplier.MARKER_KEY_COMPILER_HASH)) {
         assertEquals(VersionProperties.INSTANCE.getSha(), value);
+      } else if (key.equals(ProguardMapSupplier.MARKER_KEY_BUILD_ID)) {
+        assertNull(buildId);
+        buildId = value;
       } else {
         continue;
       }
       assertFalse(keysFound.contains(key));
       keysFound.add(key);
     }
+    assertEquals(expectedNumberOfKeys, keysFound.size());
+    return buildId;
   }
 }