diff --git a/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
index ff771b7..6a5030e 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
@@ -107,7 +107,7 @@
         continue;
       }
 
-      DexMethod newMethod = provider.provideMethod(factory);
+      DexMethod newMethod = provider.provideMethod(appView);
       iterator.replaceCurrentInstruction(
           new InvokeStatic(newMethod, invoke.outValue(), invoke.inValues()));
 
@@ -162,7 +162,7 @@
       MethodProvider provider = methodProviders.get(key);
       methodProviders.remove(key);
       assert provider.requiresGenerationOfCode();
-      DexMethod method = provider.provideMethod(factory);
+      DexMethod method = provider.provideMethod(appView);
       // The utility class could have been synthesized, e.g., running R8 then D8,
       // or if already processed in this while loop.
       if (appView.definitionFor(method.holder) != null) {
@@ -914,7 +914,7 @@
       this.proto = proto;
     }
 
-    public abstract DexMethod provideMethod(DexItemFactory factory);
+    public abstract DexMethod provideMethod(AppView<?> appView);
 
     public abstract TemplateMethodCode generateTemplateMethod(
         InternalOptions options, DexMethod method);
@@ -936,10 +936,11 @@
     }
 
     @Override
-    public DexMethod provideMethod(DexItemFactory factory) {
+    public DexMethod provideMethod(AppView<?> appView) {
       if (dexMethod != null) {
         return dexMethod;
       }
+      DexItemFactory factory = appView.dexItemFactory();
       DexProto newProto =
           isStatic ? proto : factory.prependTypeToProto(factory.createType(clazz), proto);
       return dexMethod = factory.createMethod(newHolder, newProto, method);
@@ -978,14 +979,23 @@
     }
 
     @Override
-    public DexMethod provideMethod(DexItemFactory factory) {
+    public DexMethod provideMethod(AppView<?> appView) {
       if (dexMethod != null) {
         return dexMethod;
       }
+      DexItemFactory factory = appView.dexItemFactory();
       String unqualifiedName =
           DescriptorUtils.getUnqualifiedClassNameFromDescriptor(clazz.toString());
+      // Avoid duplicate class names between core lib dex file and program dex files.
+      String coreLibUtilitySuffix = appView.options().coreLibraryCompilation ? "$corelib" : "";
       String descriptor =
-          UTILITY_CLASS_DESCRIPTOR_PREFIX + '$' + unqualifiedName + '$' + methodName + ';';
+          UTILITY_CLASS_DESCRIPTOR_PREFIX
+              + '$'
+              + unqualifiedName
+              + coreLibUtilitySuffix
+              + '$'
+              + methodName
+              + ';';
       DexType clazz = factory.createType(descriptor);
       dexMethod = factory.createMethod(clazz, proto, method);
       return dexMethod;
diff --git a/src/test/java/com/android/tools/r8/desugar/corelib/DoubleUtilityClassTest.java b/src/test/java/com/android/tools/r8/desugar/corelib/DoubleUtilityClassTest.java
new file mode 100644
index 0000000..d4941ec
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/desugar/corelib/DoubleUtilityClassTest.java
@@ -0,0 +1,98 @@
+// Copyright (c) 2019, 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.desugar.corelib;
+
+import static org.hamcrest.core.IsNot.not;
+import static org.hamcrest.core.StringContains.containsString;
+
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import java.time.LocalDateTime;
+import java.time.ZoneOffset;
+import java.time.zone.ZoneOffsetTransition;
+import java.util.Objects;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+// In this test both the desugared library and the program have the same utility class.
+@RunWith(Parameterized.class)
+public class DoubleUtilityClassTest extends CoreLibDesugarTestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withDexRuntimes().withAllApiLevels().build();
+  }
+
+  public DoubleUtilityClassTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testDoubleUtility() throws Exception {
+    for (Class<?> executor : new Class<?>[] {ExecutorV1.class, ExecutorV2.class}) {
+      testForD8()
+          .addProgramClasses(executor)
+          .enableCoreLibraryDesugaring(parameters.getApiLevel())
+          .setMinApi(parameters.getApiLevel())
+          .compile()
+          .addDesugaredCoreLibraryRunClassPath(
+              this::buildDesugaredLibrary, parameters.getApiLevel())
+          .run(parameters.getRuntime(), executor)
+          .assertSuccess()
+          // Verification error on some Dalvik VMs (4,api 1;4,api 15;4.4,api 1).
+          .assertStderrMatches(
+              not(
+                  containsString(
+                      "(Lcom/android/tools/r8/desugar/corelib/DoubleUtilityClassTest$Executor; had"
+                          + " used a different"
+                          + " L$r8$backportedMethods$utility$Objects$requireNonNullMessage; during"
+                          + " pre-verification)  (dalvikvm)")));
+    }
+  }
+
+  // ExecutorV1 and V2 look the same, *but* only one of them triggers the verification
+  // error on Dalvik VMs.
+  public static class ExecutorV1 {
+
+    public static void main(String[] args) {
+      programCalls();
+    }
+
+    public static void programCalls() {
+      System.out.println(Objects.requireNonNull("string", "transition"));
+      System.out.println(Objects.hashCode("foo"));
+      System.out.println(Long.hashCode(1L));
+      System.out.println(Long.compareUnsigned(1L, 2L));
+      System.out.println(Integer.hashCode(1));
+      System.out.println(Double.hashCode(1.0));
+    }
+  }
+
+  public static class ExecutorV2 {
+
+    public static void main(String[] args) {
+      programCalls();
+      libraryCalls();
+    }
+
+    public static void libraryCalls() {
+      System.out.println(
+          ZoneOffsetTransition.of(
+              LocalDateTime.of(2008, 3, 9, 2, 0, 0, 0), ZoneOffset.UTC, ZoneOffset.MAX));
+    }
+
+    public static void programCalls() {
+      System.out.println(Objects.requireNonNull("string", "transition"));
+      System.out.println(Objects.hashCode("foo"));
+      System.out.println(Long.hashCode(1L));
+      System.out.println(Long.compareUnsigned(1L, 2L));
+      System.out.println(Integer.hashCode(1));
+      System.out.println(Double.hashCode(1.0));
+    }
+  }
+}