diff --git a/src/main/java/com/android/tools/r8/D8.java b/src/main/java/com/android/tools/r8/D8.java
index bd49aa1..5098368 100644
--- a/src/main/java/com/android/tools/r8/D8.java
+++ b/src/main/java/com/android/tools/r8/D8.java
@@ -155,7 +155,7 @@
 
       DexApplication app = new ApplicationReader(inputApp, options, timing).read(executor);
       PrefixRewritingMapper rewritePrefix =
-          options.desugaredLibraryConfiguration.createPrefixRewritingMapper(options.itemFactory);
+          options.desugaredLibraryConfiguration.createPrefixRewritingMapper(options);
       AppInfo appInfo =
           options.enableDesugaring ? new AppInfoWithClassHierarchy(app) : new AppInfo(app);
 
@@ -174,8 +174,8 @@
         }
       }
 
-      IRConverter converter =
-          new IRConverter(AppView.createForD8(appInfo, options, rewritePrefix), timing, printer);
+      AppView<?> appView = AppView.createForD8(appInfo, options, rewritePrefix);
+      IRConverter converter = new IRConverter(appView, timing, printer);
       app = converter.convert(app, executor);
 
       if (options.printCfg) {
@@ -220,7 +220,7 @@
               options,
               marker == null ? null : ImmutableList.copyOf(markers),
               GraphLense.getIdentityLense(),
-              PrefixRewritingNamingLens.createPrefixRewritingNamingLens(options, rewritePrefix),
+              PrefixRewritingNamingLens.createPrefixRewritingNamingLens(appView),
               null)
           .write(executor);
       options.printWarnings();
diff --git a/src/main/java/com/android/tools/r8/L8.java b/src/main/java/com/android/tools/r8/L8.java
index 45cb778f..87c15ab 100644
--- a/src/main/java/com/android/tools/r8/L8.java
+++ b/src/main/java/com/android/tools/r8/L8.java
@@ -114,7 +114,7 @@
 
       DexApplication app = new ApplicationReader(inputApp, options, timing).read(executor);
       PrefixRewritingMapper rewritePrefix =
-          options.desugaredLibraryConfiguration.createPrefixRewritingMapper(options.itemFactory);
+          options.desugaredLibraryConfiguration.createPrefixRewritingMapper(options);
 
       app = new L8TreePruner(options).prune(app, rewritePrefix);
       AppInfo appInfo = new AppInfoWithClassHierarchy(app);
@@ -134,7 +134,7 @@
               options,
               options.getMarker(Tool.L8),
               GraphLense.getIdentityLense(),
-              PrefixRewritingNamingLens.createPrefixRewritingNamingLens(options, rewritePrefix),
+              PrefixRewritingNamingLens.createPrefixRewritingNamingLens(appView),
               null)
           .write(options.getClassFileConsumer(), executor);
       options.printWarnings();
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index dbe1572..1c7774d 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -783,8 +783,7 @@
           application,
           appView,
           appView.graphLense(),
-          PrefixRewritingNamingLens.createPrefixRewritingNamingLens(
-              options, appView.rewritePrefix, namingLens),
+          PrefixRewritingNamingLens.createPrefixRewritingNamingLens(appView, namingLens),
           options,
           proguardMapSupplier);
 
diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
index 650bf61..1581a5e 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -70,8 +70,7 @@
         options,
         appInfo == null
             ? PrefixRewritingMapper.empty()
-            : options.desugaredLibraryConfiguration.createPrefixRewritingMapper(
-                options.itemFactory));
+            : options.desugaredLibraryConfiguration.createPrefixRewritingMapper(options));
   }
 
   private AppView(
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 8c632a2..acdad7d 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
@@ -507,13 +507,13 @@
       // They however require the Optional/Stream class to be present, either through
       // desugared libraries or natively. If Optional/Stream class is not present,
       // we do not desugar to avoid confusion in error messages.
-      if (appView.rewritePrefix.hasRewrittenType(factory.optionalType)
+      if (appView.rewritePrefix.hasRewrittenType(factory.optionalType, appView)
           || options.minApiLevel >= AndroidApiLevel.N.getLevel()) {
         initializeJava9OptionalMethodProviders(factory);
         initializeJava10OptionalMethodProviders(factory);
         initializeJava11OptionalMethodProviders(factory);
       }
-      if (appView.rewritePrefix.hasRewrittenType(factory.streamType)
+      if (appView.rewritePrefix.hasRewrittenType(factory.streamType, appView)
           || options.minApiLevel >= AndroidApiLevel.N.getLevel()) {
         initializeStreamMethodProviders(factory);
       }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryAPIConverter.java b/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryAPIConverter.java
index 4483eca..dc0e8d6 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryAPIConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryAPIConverter.java
@@ -101,7 +101,7 @@
         InvokeMethod invokeMethod = instruction.asInvokeMethod();
         DexMethod invokedMethod = invokeMethod.getInvokedMethod();
         // Rewriting is required only on calls to library methods which are not desugared.
-        if (appView.rewritePrefix.hasRewrittenType(invokedMethod.holder)
+        if (appView.rewritePrefix.hasRewrittenType(invokedMethod.holder, appView)
             || invokedMethod.holder.isArrayType()) {
           continue;
         }
@@ -111,7 +111,7 @@
         }
         // Library methods do not understand desugared types, hence desugared types have to be
         // converted around non desugared library calls for the invoke to resolve.
-        if (appView.rewritePrefix.hasRewrittenTypeInSignature(invokedMethod.proto)) {
+        if (appView.rewritePrefix.hasRewrittenTypeInSignature(invokedMethod.proto, appView)) {
           rewriteLibraryInvoke(code, invokeMethod, iterator, blockIterator);
         }
       }
@@ -131,7 +131,7 @@
     }
     DexMethod method = code.method.method;
     if (method.holder.isArrayType()
-        || !appView.rewritePrefix.hasRewrittenTypeInSignature(method.proto)
+        || !appView.rewritePrefix.hasRewrittenTypeInSignature(method.proto, appView)
         || appView
             .options()
             .desugaredLibraryConfiguration
@@ -173,7 +173,7 @@
       DexEncodedMethod dexEncodedMethod = dexClass.lookupVirtualMethod(method);
       if (dexEncodedMethod != null) {
         // In this case, the object will be wrapped.
-        if (appView.rewritePrefix.hasRewrittenType(dexClass.type)) {
+        if (appView.rewritePrefix.hasRewrittenType(dexClass.type, appView)) {
           return false;
         }
         foundOverrideToRewrite = true;
@@ -211,14 +211,14 @@
     DexType[] newParameters = originalMethod.proto.parameters.values.clone();
     int index = 0;
     for (DexType param : originalMethod.proto.parameters.values) {
-      if (appView.rewritePrefix.hasRewrittenType(param)) {
+      if (appView.rewritePrefix.hasRewrittenType(param, appView)) {
         newParameters[index] = vivifiedTypeFor(param, appView);
       }
       index++;
     }
     DexType returnType = originalMethod.proto.returnType;
     DexType newReturnType =
-        appView.rewritePrefix.hasRewrittenType(returnType)
+        appView.rewritePrefix.hasRewrittenType(returnType, appView)
             ? vivifiedTypeFor(returnType, appView)
             : returnType;
     DexProto newProto = appView.dexItemFactory().createProto(newReturnType, newParameters);
@@ -270,7 +270,7 @@
   }
 
   private void warnInvalidInvoke(DexType type, DexMethod invokedMethod, String debugString) {
-    DexType desugaredType = appView.rewritePrefix.rewrittenType(type);
+    DexType desugaredType = appView.rewritePrefix.rewrittenType(type, appView);
     appView
         .options()
         .reporter
@@ -310,7 +310,7 @@
     Instruction returnConversion = null;
     DexType newReturnType;
     DexType returnType = invokedMethod.proto.returnType;
-    if (appView.rewritePrefix.hasRewrittenType(returnType)) {
+    if (appView.rewritePrefix.hasRewrittenType(returnType, appView)) {
       if (canConvert(returnType)) {
         newReturnType = vivifiedTypeFor(returnType, appView);
         // Return conversion added only if return value is used.
@@ -332,7 +332,7 @@
     List<Instruction> parameterConversions = new ArrayList<>();
     List<Value> newInValues = new ArrayList<>();
     if (invokeMethod.isInvokeMethodWithReceiver()) {
-      assert !appView.rewritePrefix.hasRewrittenType(invokedMethod.holder);
+      assert !appView.rewritePrefix.hasRewrittenType(invokedMethod.holder, appView);
       newInValues.add(invokeMethod.asInvokeMethodWithReceiver().getReceiver());
     }
     int receiverShift = BooleanUtils.intValue(invokeMethod.isInvokeMethodWithReceiver());
@@ -340,7 +340,7 @@
     DexType[] newParameters = parameters.clone();
     for (int i = 0; i < parameters.length; i++) {
       DexType argType = parameters[i];
-      if (appView.rewritePrefix.hasRewrittenType(argType)) {
+      if (appView.rewritePrefix.hasRewrittenType(argType, appView)) {
         if (canConvert(argType)) {
           DexType argVivifiedType = vivifiedTypeFor(argType, appView);
           Value inValue = invokeMethod.inValues().get(i + receiverShift);
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryConfiguration.java b/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryConfiguration.java
index 3d0a59c..bdb4cd9 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryConfiguration.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryConfiguration.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.desugar.PrefixRewritingMapper.DesugarPrefixRewritingMapper;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.DescriptorUtils;
+import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.Pair;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
@@ -47,7 +48,7 @@
       Map<String, String> prefix) {
     return new DesugaredLibraryConfiguration(
         AndroidApiLevel.B,
-        false,
+        true,
         FALL_BACK_SYNTHESIZED_CLASSES_PACKAGE_PREFIX,
         prefix,
         ImmutableMap.of(),
@@ -95,10 +96,10 @@
     this.extraKeepRules = extraKeepRules;
   }
 
-  public PrefixRewritingMapper createPrefixRewritingMapper(DexItemFactory factory) {
+  public PrefixRewritingMapper createPrefixRewritingMapper(InternalOptions options) {
     return rewritePrefix.isEmpty()
         ? PrefixRewritingMapper.empty()
-        : new DesugarPrefixRewritingMapper(rewritePrefix, factory);
+        : new DesugarPrefixRewritingMapper(rewritePrefix, options);
   }
 
   public AndroidApiLevel getRequiredCompilationApiLevel() {
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
index 328d8e2..bcae8e7 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
@@ -393,7 +393,7 @@
     }
     // Since desugared library classes are desugared, no need to rewrite invokes which can target
     // only such classes program types.
-    if (appView.rewritePrefix.hasRewrittenType(dexClass.type)) {
+    if (appView.rewritePrefix.hasRewrittenType(dexClass.type, appView)) {
       return null;
     }
     DexEncodedMethod singleTarget =
@@ -438,7 +438,7 @@
     if (emulatedInterfaces.containsKey(clazz.type)) {
       return true;
     }
-    return appView.rewritePrefix.hasRewrittenType(clazz.type);
+    return appView.rewritePrefix.hasRewrittenType(clazz.type, appView);
   }
 
   boolean dontRewrite(DexMethod method) {
@@ -792,7 +792,7 @@
     for (DexClass clazz : appView.appInfo().classes()) {
       if (clazz.isInterface()) {
         DexType newType = inferEmulatedInterfaceName(clazz);
-        if (newType != null && !appView.rewritePrefix.hasRewrittenType(clazz.type)) {
+        if (newType != null && !appView.rewritePrefix.hasRewrittenType(clazz.type, appView)) {
           // We do not rewrite if it is already going to be rewritten using the a rewritingPrefix.
           addRewritePrefix(clazz.type, newType.toString());
           renameEmulatedInterfaces(clazz, newType);
@@ -1050,7 +1050,7 @@
   private void warnMissingType(DexMethod referencedFrom, DexType missing) {
     // Companion/Emulated interface/Conversion classes for desugared library won't be missing,
     // they are in the desugared library.
-    if (appView.rewritePrefix.hasRewrittenType(missing)
+    if (appView.rewritePrefix.hasRewrittenType(missing, appView)
         || DesugaredLibraryWrapperSynthesizer.isSynthesizedWrapper(missing)
         || isCompanionClassType(missing)
         || appView
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
index 6ae855c..2fd29e1 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
@@ -361,7 +361,8 @@
               lambdaClassType,
               new LambdaClass(this, accessedFrom, lambdaClassType, descriptor));
       if (getAppView().options().isDesugaredLibraryCompilation()) {
-        DexType rewrittenType = getAppView().rewritePrefix.rewrittenType(accessedFrom);
+        DexType rewrittenType =
+            getAppView().rewritePrefix.rewrittenType(accessedFrom, getAppView());
         if (rewrittenType == null) {
           rewrittenType =
               getAppView()
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/PrefixRewritingMapper.java b/src/main/java/com/android/tools/r8/ir/desugar/PrefixRewritingMapper.java
index 1549b58..1c3b6a2 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/PrefixRewritingMapper.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/PrefixRewritingMapper.java
@@ -5,11 +5,14 @@
 package com.android.tools.r8.ir.desugar;
 
 import com.android.tools.r8.errors.CompilationError;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.utils.DescriptorUtils;
+import com.android.tools.r8.utils.InternalOptions;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Sets;
 import java.util.Map;
@@ -22,20 +25,20 @@
     return new EmptyPrefixRewritingMapper();
   }
 
-  public abstract DexType rewrittenType(DexType type);
-
   public abstract void rewriteType(DexType type, DexType rewrittenType);
 
-  public boolean hasRewrittenType(DexType type) {
-    return rewrittenType(type) != null;
+  public abstract DexType rewrittenType(DexType type, AppView<?> appView);
+
+  public boolean hasRewrittenType(DexType type, AppView<?> appView) {
+    return rewrittenType(type, appView) != null;
   }
 
-  public boolean hasRewrittenTypeInSignature(DexProto proto) {
-    if (hasRewrittenType(proto.returnType)) {
+  public boolean hasRewrittenTypeInSignature(DexProto proto, AppView<?> appView) {
+    if (hasRewrittenType(proto.returnType, appView)) {
       return true;
     }
     for (DexType paramType : proto.parameters.values) {
-      if (hasRewrittenType(paramType)) {
+      if (hasRewrittenType(paramType, appView)) {
         return true;
       }
     }
@@ -50,9 +53,11 @@
     private final Map<DexType, DexType> rewritten = new ConcurrentHashMap<>();
     private final Map<DexString, DexString> initialPrefixes;
     private final DexItemFactory factory;
+    private final boolean l8Compilation;
 
-    public DesugarPrefixRewritingMapper(Map<String, String> prefixes, DexItemFactory factory) {
-      this.factory = factory;
+    public DesugarPrefixRewritingMapper(Map<String, String> prefixes, InternalOptions options) {
+      this.factory = options.itemFactory;
+      this.l8Compilation = options.isDesugaredLibraryCompilation();
       ImmutableMap.Builder<DexString, DexString> builder = ImmutableMap.builder();
       for (String key : prefixes.keySet()) {
         builder.put(toDescriptorPrefix(key), toDescriptorPrefix(prefixes.get(key)));
@@ -97,14 +102,34 @@
     }
 
     @Override
-    public DexType rewrittenType(DexType type) {
+    public DexType rewrittenType(DexType type, AppView<?> appView) {
+      assert appView != null || l8Compilation;
       if (notRewritten.contains(type)) {
         return null;
       }
       if (rewritten.containsKey(type)) {
         return rewritten.get(type);
       }
-      return computePrefix(type);
+      return computePrefix(type, appView);
+    }
+
+    // Besides L8 compilation, program types should not be rewritten.
+    private void failIfRewritingProgramType(DexType type, AppView<?> appView) {
+      if (l8Compilation) {
+        return;
+      }
+
+      DexType dexType = type.isArrayType() ? type.toBaseType(appView.dexItemFactory()) : type;
+      DexClass dexClass = appView.definitionFor(dexType);
+      if (dexClass != null && dexClass.isProgramClass()) {
+        appView
+            .options()
+            .reporter
+            .error(
+                "Cannot compile program class "
+                    + dexType
+                    + " since it conflicts with a desugared library rewriting rule.");
+      }
     }
 
     @Override
@@ -122,10 +147,11 @@
       rewritten.put(type, rewrittenType);
     }
 
-    private DexType computePrefix(DexType type) {
+    private DexType computePrefix(DexType type, AppView<?> appView) {
       DexString prefixToMatch = type.descriptor.withoutArray(factory);
       DexType result = lookup(type, prefixToMatch, initialPrefixes);
       if (result != null) {
+        failIfRewritingProgramType(type, appView);
         return result;
       }
       notRewritten.add(type);
@@ -155,7 +181,7 @@
   public static class EmptyPrefixRewritingMapper extends PrefixRewritingMapper {
 
     @Override
-    public DexType rewrittenType(DexType type) {
+    public DexType rewrittenType(DexType type, AppView<?> appView) {
       return null;
     }
 
diff --git a/src/main/java/com/android/tools/r8/ir/synthetic/DesugaredLibraryAPIConversionCfCodeProvider.java b/src/main/java/com/android/tools/r8/ir/synthetic/DesugaredLibraryAPIConversionCfCodeProvider.java
index 5597bb5..422bc2f 100644
--- a/src/main/java/com/android/tools/r8/ir/synthetic/DesugaredLibraryAPIConversionCfCodeProvider.java
+++ b/src/main/java/com/android/tools/r8/ir/synthetic/DesugaredLibraryAPIConversionCfCodeProvider.java
@@ -43,7 +43,7 @@
 
   boolean shouldConvert(
       DexType type, DesugaredLibraryAPIConverter converter, DexString methodName) {
-    if (!appView.rewritePrefix.hasRewrittenType(type)) {
+    if (!appView.rewritePrefix.hasRewrittenType(type, appView)) {
       return false;
     }
     if (converter.canConvert(type)) {
@@ -118,7 +118,7 @@
 
       DexType returnType = forwardMethod.proto.returnType;
       DexType forwardMethodReturnType =
-          appView.rewritePrefix.hasRewrittenType(returnType)
+          appView.rewritePrefix.hasRewrittenType(returnType, appView)
               ? vivifiedTypeFor(returnType)
               : returnType;
 
diff --git a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
index f12d958..8d2e79f 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
@@ -280,7 +280,7 @@
           state.reserveName(reservedName, method.method);
           // This is reserving names which after prefix rewriting will actually override a library
           // method.
-          if (appView.rewritePrefix.hasRewrittenTypeInSignature(method.method.proto)) {
+          if (appView.rewritePrefix.hasRewrittenTypeInSignature(method.method.proto, appView)) {
             state.reserveName(
                 reservedName,
                 DesugaredLibraryAPIConverter.methodWithVivifiedTypeInSignature(
diff --git a/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java b/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java
index e1dc8a6..777d006 100644
--- a/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java
+++ b/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.naming;
 
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexCallSite;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItem;
@@ -31,28 +32,27 @@
   final NamingLens namingLens;
   final InternalOptions options;
 
-  public static NamingLens createPrefixRewritingNamingLens(
-      InternalOptions options, PrefixRewritingMapper rewritePrefix) {
-    return createPrefixRewritingNamingLens(options, rewritePrefix, NamingLens.getIdentityLens());
+  public static NamingLens createPrefixRewritingNamingLens(AppView<?> appView) {
+    return createPrefixRewritingNamingLens(appView, NamingLens.getIdentityLens());
   }
 
   public static NamingLens createPrefixRewritingNamingLens(
-      InternalOptions options, PrefixRewritingMapper rewritePrefix, NamingLens namingLens) {
-    if (!rewritePrefix.isRewriting()) {
+      AppView<?> appView, NamingLens namingLens) {
+    if (!appView.rewritePrefix.isRewriting()) {
       return namingLens;
     }
-    return new PrefixRewritingNamingLens(namingLens, options, rewritePrefix);
+    return new PrefixRewritingNamingLens(namingLens, appView);
   }
 
-  public PrefixRewritingNamingLens(
-      NamingLens namingLens, InternalOptions options, PrefixRewritingMapper rewritePrefix) {
+  public PrefixRewritingNamingLens(NamingLens namingLens, AppView<?> appView) {
     this.namingLens = namingLens;
-    this.options = options;
+    this.options = appView.options();
     DexItemFactory itemFactory = options.itemFactory;
+    PrefixRewritingMapper rewritePrefix = appView.rewritePrefix;
     itemFactory.forAllTypes(
         type -> {
-          if (rewritePrefix.hasRewrittenType(type)) {
-            classRenaming.put(type, rewritePrefix.rewrittenType(type).descriptor);
+          if (rewritePrefix.hasRewrittenType(type, appView)) {
+            classRenaming.put(type, rewritePrefix.rewrittenType(type, appView).descriptor);
           }
         });
     // Verify that no type would have been renamed by both lenses.
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 1b76214..2884fcd 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -1645,7 +1645,7 @@
       // In the first enqueuer phase, the signature has not been desugared, so firstResolution
       // maintains the library override. In the second enqueuer phase, the signature has been
       // desugared, and the second resolution maintains the the library override.
-      if (appView.rewritePrefix.hasRewrittenTypeInSignature(method.method.proto)) {
+      if (appView.rewritePrefix.hasRewrittenTypeInSignature(method.method.proto, appView)) {
         DexMethod methodToResolve =
             DesugaredLibraryAPIConverter.methodWithVivifiedTypeInSignature(
                 method.method, method.method.holder, appView);
diff --git a/src/main/java/com/android/tools/r8/shaking/L8TreePruner.java b/src/main/java/com/android/tools/r8/shaking/L8TreePruner.java
index 20595c7..8e5e7a3 100644
--- a/src/main/java/com/android/tools/r8/shaking/L8TreePruner.java
+++ b/src/main/java/com/android/tools/r8/shaking/L8TreePruner.java
@@ -43,7 +43,7 @@
     }
     List<DexProgramClass> toKeep = new ArrayList<>();
     for (DexProgramClass aClass : app.classes()) {
-      if (rewritePrefix.hasRewrittenType(aClass.type)
+      if (rewritePrefix.hasRewrittenType(aClass.type, null)
           || emulatedInterfaces.contains(aClass.type)
           || interfaceImplementsEmulatedInterface(aClass, typeMap)) {
         toKeep.add(aClass);
diff --git a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/J$ExtensionTest.java b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/J$ExtensionTest.java
new file mode 100644
index 0000000..3c78730
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/J$ExtensionTest.java
@@ -0,0 +1,158 @@
+// Copyright (c) 2020, 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.desugaredlibrary;
+
+import static junit.framework.TestCase.assertTrue;
+import static junit.framework.TestCase.fail;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestRuntime;
+import com.android.tools.r8.TestRuntime.CfVm;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.DexVm.Version;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.BooleanUtils;
+import java.io.BufferedWriter;
+import java.io.File;
+import java.io.FileWriter;
+import java.io.IOException;
+import java.nio.file.Path;
+import java.util.List;
+import org.junit.Assume;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class J$ExtensionTest extends DesugaredLibraryTestBase {
+
+  private final TestParameters parameters;
+  private final boolean shrinkDesugaredLibrary;
+
+  private static final String MAIN_CLASS_NAME = "Main";
+  private static final String MAIN_CLASS =
+      "import java.time.LocalTimeAccess;\n"
+          + "public class Main {\n"
+          + "   public static void main(String[] args) throws Exception { \n"
+          + "     LocalTimeAccess.main(new String[0]);\n"
+          + "   }\n"
+          + "}";
+
+  private static final String TIME_CLASS =
+      "package java.time;\n"
+          + "\n"
+          + "import java.time.LocalTime;\n"
+          + "\n"
+          + "public class LocalTimeAccess {\n"
+          + "\n"
+          + "  public static void main(String[] args) throws Exception {\n"
+          + "    System.out.println(LocalTime.readExternal(null));\n"
+          + "  }\n"
+          + "}";
+  private static Path[] compiledClasses = new Path[2];
+
+  @Parameters(name = "{1}, shrinkDesugaredLibrary: {0}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        BooleanUtils.values(), getTestParameters().withAllRuntimes().withAllApiLevels().build());
+  }
+
+  public J$ExtensionTest(boolean shrinkDesugaredLibrary, TestParameters parameters) {
+    this.shrinkDesugaredLibrary = shrinkDesugaredLibrary;
+    this.parameters = parameters;
+  }
+
+  @BeforeClass
+  public static void compileClass() throws IOException {
+    Assume.assumeFalse(ToolHelper.isWindows());
+
+    File file1 = getStaticTemp().newFile("LocalTimeAccess.java");
+    BufferedWriter writer1 = new BufferedWriter(new FileWriter(file1));
+    writer1.write(TIME_CLASS);
+    writer1.close();
+    compiledClasses[0] =
+        javac(TestRuntime.getCheckedInJdk8(), getStaticTemp())
+            .addSourceFiles(file1.toPath())
+            .compile();
+
+    File file2 = getStaticTemp().newFile("Main.java");
+    BufferedWriter writer2 = new BufferedWriter(new FileWriter(file2));
+    writer2.write(MAIN_CLASS);
+    writer2.close();
+    compiledClasses[1] =
+        javac(TestRuntime.getCheckedInJdk8(), getStaticTemp())
+            .addSourceFiles(file2.toPath())
+            .addClasspathFiles(compiledClasses[0])
+            .compile();
+  }
+
+  @Test
+  public void testJ$ExtensionNoDesugaring() throws Exception {
+    Assume.assumeFalse(shrinkDesugaredLibrary);
+    String stderr;
+    if (parameters.isCfRuntime()) {
+      stderr =
+          testForJvm()
+              .addProgramFiles(compiledClasses)
+              .run(parameters.getRuntime(), MAIN_CLASS_NAME)
+              .assertFailure()
+              .getStdErr();
+    } else {
+      stderr =
+          testForD8()
+              .addProgramFiles(compiledClasses)
+              .setMinApi(parameters.getApiLevel())
+              .run(parameters.getRuntime(), MAIN_CLASS_NAME)
+              .assertFailure()
+              .getStdErr();
+    }
+    assertError(stderr);
+  }
+
+  private void assertError(String stderr) {
+    if (parameters.isCfRuntime() && parameters.getRuntime().asCf().getVm() == CfVm.JDK8) {
+      assertTrue(
+          stderr.contains("java.lang.SecurityException: Prohibited package name: java.time"));
+    } else if (parameters.isCfRuntime()) {
+      assertTrue(stderr.contains("java.lang.ClassNotFoundException: java.time.LocalTimeAccess"));
+    } else if (parameters
+        .getRuntime()
+        .asDex()
+        .getVm()
+        .getVersion()
+        .isOlderThanOrEqual(Version.V6_0_1)) {
+      assertTrue(stderr.contains("java.lang.NoClassDefFoundError"));
+    } else if (parameters.getRuntime().asDex().getVm().getVersion() == Version.V7_0_0) {
+      assertTrue(stderr.contains("java.lang.ClassNotFoundException"));
+    } else {
+      assertTrue(stderr.contains("java.lang.IllegalAccessError"));
+    }
+  }
+
+  @Test
+  public void testJ$ExtensionDesugaring() throws Exception {
+    Assume.assumeFalse(parameters.isCfRuntime());
+    // Above O no desugaring is required.
+    Assume.assumeTrue(parameters.getApiLevel().getLevel() < AndroidApiLevel.O.getLevel());
+    KeepRuleConsumer keepRuleConsumer = createKeepRuleConsumer(parameters);
+
+    try {
+      testForD8()
+          .addProgramFiles(compiledClasses)
+          .setMinApi(parameters.getApiLevel())
+          .enableCoreLibraryDesugaring(parameters.getApiLevel(), keepRuleConsumer)
+          .compile();
+      fail();
+    } catch (CompilationFailedException e) {
+      assertTrue(
+          e.getCause()
+              .getMessage()
+              .contains("Cannot compile program class java.time.LocalTimeAccess"));
+    }
+  }
+}